llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-transforms @llvm/pr-subscribers-pgo Author: Paul Kirth (ilovepi) <details> <summary>Changes</summary> Issue #<!-- -->56502 describes an enhancement related to the use of llvm.expect. The request is for a diagnostic mode that can identify branches that would benefit from the use of llvm.expect based on the branch_weights assigned from a PGO or sample profile. To support identify branches(or switches) that would benefit from the use of an llvm.expect intrinsic, we follow a similar checking pattern to that used in MisExpect, but only in cases where MisExpect diagnostics would not be used (i.e., when an llvm.expect intrinsic has already been used). --- Full diff: https://github.com/llvm/llvm-project/pull/96523.diff 8 Files Affected: - (modified) llvm/include/llvm/IR/LLVMContext.h (+2) - (modified) llvm/include/llvm/Target/TargetOptions.h (+4) - (modified) llvm/include/llvm/Transforms/Utils/MisExpect.h (+3) - (modified) llvm/lib/IR/LLVMContext.cpp (+6) - (modified) llvm/lib/IR/LLVMContextImpl.h (+4) - (modified) llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp (+1) - (modified) llvm/lib/Transforms/Utils/MisExpect.cpp (+137-36) - (added) llvm/test/Transforms/PGOProfile/missing-annotation.ll (+110) ``````````diff diff --git a/llvm/include/llvm/IR/LLVMContext.h b/llvm/include/llvm/IR/LLVMContext.h index 89ad6f1572c67..94e526d465c8e 100644 --- a/llvm/include/llvm/IR/LLVMContext.h +++ b/llvm/include/llvm/IR/LLVMContext.h @@ -212,6 +212,8 @@ class LLVMContext { void setMisExpectWarningRequested(bool Requested); void setDiagnosticsMisExpectTolerance(std::optional<uint32_t> Tolerance); uint32_t getDiagnosticsMisExpectTolerance() const; + bool getAnnotationDiagsRequested() const; + void setAnnotationDiagsRequested(bool Requested); /// Return the minimum hotness value a diagnostic would need in order /// to be included in optimization diagnostics. diff --git a/llvm/include/llvm/Target/TargetOptions.h b/llvm/include/llvm/Target/TargetOptions.h index d3464b5202ff3..447b86f69cfaa 100644 --- a/llvm/include/llvm/Target/TargetOptions.h +++ b/llvm/include/llvm/Target/TargetOptions.h @@ -377,6 +377,10 @@ namespace llvm { /// By default, it is set to false unsigned MisExpect : 1; + /// When set to true, enable MissingAnnotations diagnostics + /// By default, it is set to false + unsigned MissingAnnotations : 1; + /// When set to true, const objects with relocatable address values are put /// into the RO data section. unsigned XCOFFReadOnlyPointers : 1; diff --git a/llvm/include/llvm/Transforms/Utils/MisExpect.h b/llvm/include/llvm/Transforms/Utils/MisExpect.h index e9fba47c97a4d..118d859f93dd6 100644 --- a/llvm/include/llvm/Transforms/Utils/MisExpect.h +++ b/llvm/include/llvm/Transforms/Utils/MisExpect.h @@ -76,6 +76,9 @@ void checkExpectAnnotations(Instruction &I, const ArrayRef<uint32_t> ExistingWeights, bool IsFrontend); +void checkMissingAnnotations(Instruction &I, + const ArrayRef<uint32_t> ExistingWeights, + bool IsFrontendInstr); } // namespace misexpect } // namespace llvm diff --git a/llvm/lib/IR/LLVMContext.cpp b/llvm/lib/IR/LLVMContext.cpp index 8120cccace40b..e1a05c1347969 100644 --- a/llvm/lib/IR/LLVMContext.cpp +++ b/llvm/lib/IR/LLVMContext.cpp @@ -171,6 +171,12 @@ void LLVMContext::setDiagnosticsMisExpectTolerance( uint32_t LLVMContext::getDiagnosticsMisExpectTolerance() const { return pImpl->DiagnosticsMisExpectTolerance.value_or(0); } +void LLVMContext::setAnnotationDiagsRequested(bool Requested) { + pImpl->AnnotationsDiagsRequested = Requested; +} +bool LLVMContext::getAnnotationDiagsRequested() const { + return pImpl->AnnotationsDiagsRequested; +} bool LLVMContext::isDiagnosticsHotnessThresholdSetFromPSI() const { return !pImpl->DiagnosticsHotnessThreshold.has_value(); diff --git a/llvm/lib/IR/LLVMContextImpl.h b/llvm/lib/IR/LLVMContextImpl.h index 5f8df87149f04..59eb5eb29705d 100644 --- a/llvm/lib/IR/LLVMContextImpl.h +++ b/llvm/lib/IR/LLVMContextImpl.h @@ -1495,6 +1495,10 @@ class LLVMContextImpl { std::optional<uint32_t> DiagnosticsMisExpectTolerance = 0; bool MisExpectWarningRequested = false; + /// Enables Diagnostics for Missing llvm.expect annotations on extremely hot + /// branches + bool AnnotationsDiagsRequested = false; + /// The specialized remark streamer used by LLVM's OptimizationRemarkEmitter. std::unique_ptr<LLVMRemarkStreamer> LLVMRS; diff --git a/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp b/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp index 572d37a2b3e55..0fbf60194696a 100644 --- a/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp +++ b/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp @@ -2261,6 +2261,7 @@ void llvm::setProfMetadata(Module *M, Instruction *TI, } dbgs() << "\n";); misexpect::checkExpectAnnotations(*TI, Weights, /*IsFrontend=*/false); + misexpect::checkMissingAnnotations(*TI, Weights, /*IsFrontend=*/false); setBranchWeights(*TI, Weights, /*IsExpected=*/false); if (EmitBranchProbability) { diff --git a/llvm/lib/Transforms/Utils/MisExpect.cpp b/llvm/lib/Transforms/Utils/MisExpect.cpp index aef9d82db0424..933d9a146533d 100644 --- a/llvm/lib/Transforms/Utils/MisExpect.cpp +++ b/llvm/lib/Transforms/Utils/MisExpect.cpp @@ -30,7 +30,6 @@ #include "llvm/Transforms/Utils/MisExpect.h" #include "llvm/ADT/Twine.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" -#include "llvm/IR/Constants.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" @@ -65,9 +64,52 @@ static cl::opt<uint32_t> MisExpectTolerance( cl::desc("Prevents emitting diagnostics when profile counts are " "within N% of the threshold..")); +// Command line option to enable/disable the Remarks when profile data suggests +// that the llvm.expect intrinsic may be profitable +static cl::opt<bool> + PGOMissingAnnotations("pgo-missing-annotations", cl::init(false), + cl::Hidden, + cl::desc("Use this option to turn on/off suggestions " + "of missing llvm.expect intrinsics.")); } // namespace llvm namespace { +struct ProfDataSummary { + uint64_t Likely; + uint64_t Unlikely; + uint64_t RealTotal; + uint64_t NumUnlikely; +}; + +enum class DiagKind { + MisExpect, // Reports when llvm.expect usage is contradicted by PGO data + MissingExpect, // Reports when llvm.expect would be profitable +}; + +uint64_t getScaledThreshold(const ProfDataSummary &PDS) { + uint64_t TotalBranchWeight = PDS.Likely + (PDS.Unlikely * PDS.NumUnlikely); + + LLVM_DEBUG(dbgs() << "Total Branch Weight = " << TotalBranchWeight << "\n" + << "Likely Branch Weight = " << PDS.Likely << "\n"); + + // Failing this assert means that we have corrupted metadata. + assert((TotalBranchWeight >= PDS.Likely) && (TotalBranchWeight > 0) + && "TotalBranchWeight is less than the Likely branch weight"); + + // To determine our threshold value we need to obtain the branch probability + // for the weights added by llvm.expect and use that proportion to calculate + // our threshold based on the collected profile data. + BranchProbability LikelyProbablilty = + BranchProbability::getBranchProbability(PDS.Likely, TotalBranchWeight); + + return LikelyProbablilty.scale(PDS.RealTotal); +} + +bool isAnnotationDiagEnabled(LLVMContext &Ctx) { + LLVM_DEBUG(dbgs() << "PGOMissingAnnotations = " << PGOMissingAnnotations + << "\n"); + return PGOMissingAnnotations || Ctx.getAnnotationDiagsRequested(); +} bool isMisExpectDiagEnabled(LLVMContext &Ctx) { return PGOWarnMisExpect || Ctx.getMisExpectWarningRequested(); @@ -112,10 +154,64 @@ void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx, Instruction *Cond = getInstCondition(I); if (isMisExpectDiagEnabled(Ctx)) Ctx.diagnose(DiagnosticInfoMisExpect(Cond, Msg)); - OptimizationRemarkEmitter ORE(I->getParent()->getParent()); + OptimizationRemarkEmitter ORE(I->getFunction()); ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str()); } + +void emitMissingAnnotationDiag(Instruction *I) { + const auto *RemStr = + "Extremely hot condition. Consider adding llvm.expect intrinsic"; + Instruction *Cond = getInstCondition(I); + OptimizationRemarkEmitter ORE(I->getParent()->getParent()); + ORE.emit( + OptimizationRemark("missing-annotations", "missing-annotations", Cond) + << RemStr); +} + +uint64_t totalWeight(const ArrayRef<uint32_t> Weights) { + return std::accumulate(Weights.begin(), Weights.end(), (uint64_t)0, + std::plus<uint64_t>()); +} + +void scaleByTollerance(const Instruction &I, uint64_t &ScaledThreshold) { + // clamp tolerance range to [0, 100) + uint32_t Tolerance = getMisExpectTolerance(I.getContext()); + Tolerance = std::clamp(Tolerance, 0u, 99u); + + // Allow users to relax checking by N% i.e., if they use a 5% tolerance, + // then we check against 0.95*ScaledThreshold + if (Tolerance > 0) + ScaledThreshold *= (1.0 - Tolerance / 100.0); + + LLVM_DEBUG(dbgs() << "Scaled Threshold = " << ScaledThreshold << "\n"); +} + +void reportDiagnostics(Instruction &I, const ProfDataSummary &PDS, + uint32_t ProfiledWeight, DiagKind Kind) { + uint64_t ScaledThreshold = getScaledThreshold(PDS); + scaleByTollerance(I, ScaledThreshold); + + LLVM_DEBUG(dbgs() << "Total Branch Weight = " << PDS.RealTotal << "\n" + << "Scaled Threshold = " << ScaledThreshold << "\n" + << "Profiled Weight = " << ProfiledWeight << "\n" + << "Likely Branch Weight = " << PDS.Likely << "\n"); + // When the profile weight is outside the range, we emit the diagnostic + switch (Kind) { + case DiagKind::MisExpect: + if (ProfiledWeight < ScaledThreshold) { + emitMisexpectDiagnostic(&I, I.getContext(), ProfiledWeight, + PDS.RealTotal); + } + return; + case DiagKind::MissingExpect: + if (ProfiledWeight > ScaledThreshold) { + emitMissingAnnotationDiag(&I); + } + return; + }; +} + } // namespace namespace llvm { @@ -126,7 +222,7 @@ void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights, // To determine if we emit a diagnostic, we need to compare the branch weights // from the profile to those added by the llvm.expect intrinsic. // So first, we extract the "likely" and "unlikely" weights from - // ExpectedWeights And determine the correct weight in the profile to compare + // ExpectedWeights and determine the correct weight in the profile to compare // against. uint64_t LikelyBranchWeight = 0, UnlikelyBranchWeight = std::numeric_limits<uint32_t>::max(); @@ -143,39 +239,10 @@ void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights, } const uint64_t ProfiledWeight = RealWeights[MaxIndex]; - const uint64_t RealWeightsTotal = - std::accumulate(RealWeights.begin(), RealWeights.end(), (uint64_t)0, - std::plus<uint64_t>()); - const uint64_t NumUnlikelyTargets = RealWeights.size() - 1; - - uint64_t TotalBranchWeight = - LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets); - - // Failing this assert means that we have corrupted metadata. - assert((TotalBranchWeight >= LikelyBranchWeight) && (TotalBranchWeight > 0) && - "TotalBranchWeight is less than the Likely branch weight"); - - // To determine our threshold value we need to obtain the branch probability - // for the weights added by llvm.expect and use that proportion to calculate - // our threshold based on the collected profile data. - auto LikelyProbablilty = BranchProbability::getBranchProbability( - LikelyBranchWeight, TotalBranchWeight); - - uint64_t ScaledThreshold = LikelyProbablilty.scale(RealWeightsTotal); - - // clamp tolerance range to [0, 100) - auto Tolerance = getMisExpectTolerance(I.getContext()); - Tolerance = std::clamp(Tolerance, 0u, 99u); - - // Allow users to relax checking by N% i.e., if they use a 5% tolerance, - // then we check against 0.95*ScaledThreshold - if (Tolerance > 0) - ScaledThreshold *= (1.0 - Tolerance / 100.0); - - // When the profile weight is below the threshold, we emit the diagnostic - if (ProfiledWeight < ScaledThreshold) - emitMisexpectDiagnostic(&I, I.getContext(), ProfiledWeight, - RealWeightsTotal); + const ProfDataSummary PDS = {LikelyBranchWeight, UnlikelyBranchWeight, + totalWeight(RealWeights), + RealWeights.size() - 1}; + reportDiagnostics(I,PDS, ProfiledWeight, DiagKind::MisExpect); } void checkBackendInstrumentation(Instruction &I, @@ -211,6 +278,40 @@ void checkExpectAnnotations(Instruction &I, } } +void verifyMissingAnnotations(Instruction &I, ArrayRef<uint32_t> RealWeights) { + // To determine if we emit a diagnostic, we need to compare the branch weights + // from the profile to those that would be added by the llvm.expect intrinsic + // and compare it to the real profile to see if it would be profitable. + uint32_t ProfiledWeight = + *std::max_element(RealWeights.begin(), RealWeights.end()); + + const uint64_t LikelyBranchWeight = 2000; + const uint64_t UnlikelyBranchWeight = 1; + const ProfDataSummary PDS = {LikelyBranchWeight, UnlikelyBranchWeight, + totalWeight(RealWeights), + RealWeights.size() - 1}; + reportDiagnostics(I, PDS, ProfiledWeight, DiagKind::MissingExpect); +} + +void checkMissingAnnotations(Instruction &I, + const ArrayRef<uint32_t> ExistingWeights, + bool IsFrontendInstr) { + + // exit early if these diagnostics weren't requested + if (LLVM_LIKELY(!isAnnotationDiagEnabled(I.getContext()))) + return; + + if (IsFrontendInstr) { + // TODO: Frontend checking will have to be thought through, since we need + // to do the check on branches that don't have expect intrinsics + } else { + SmallVector<uint32_t> ExpectedWeights; + if (extractBranchWeights(I, ExpectedWeights)) + return; + verifyMissingAnnotations(I, ExistingWeights); + } +} + } // namespace misexpect } // namespace llvm #undef DEBUG_TYPE diff --git a/llvm/test/Transforms/PGOProfile/missing-annotation.ll b/llvm/test/Transforms/PGOProfile/missing-annotation.ll new file mode 100644 index 0000000000000..6b52302449900 --- /dev/null +++ b/llvm/test/Transforms/PGOProfile/missing-annotation.ll @@ -0,0 +1,110 @@ +; Test misexpect checks do not issue diagnostics when profiling weights and +; branch weights added by llvm.expect agree + +; RUN: llvm-profdata merge %S/Inputs/misexpect-branch-correct.proftext -o %t.profdata + +; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-missing-annotations -pass-remarks=missing-annotation -S 2>&1 | FileCheck %s --check-prefix=MISSING_ANNOTATION + +; MISSING_ANNOTATION: remark: misexpect-branch.c:22:0: Extremely hot condition. Consider adding llvm.expect intrinsic + +; CHECK-NOT: warning: {{.*}} +; CHECK-NOT: remark: {{.*}} +; CHECK: !{!"branch_weights", i32 0, i32 200000} + + +; ModuleID = 'misexpect-branch.c' +source_filename = "misexpect-branch.c" +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +@inner_loop = constant i32 100, align 4 +@outer_loop = constant i32 2000, align 4 + +; Function Attrs: nounwind +define i32 @bar() #0 !dbg !6 { +entry: + %rando = alloca i32, align 4 + %x = alloca i32, align 4 + %0 = bitcast i32* %rando to i8*, !dbg !9 + call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #4, !dbg !9 + %call = call i32 (...) @buzz(), !dbg !9 + store i32 %call, i32* %rando, align 4, !dbg !9, !tbaa !10 + %1 = bitcast i32* %x to i8*, !dbg !14 + call void @llvm.lifetime.start.p0i8(i64 4, i8* %1) #4, !dbg !14 + store i32 0, i32* %x, align 4, !dbg !14, !tbaa !10 + %2 = load i32, i32* %rando, align 4, !dbg !15, !tbaa !10 + %rem = srem i32 %2, 200000, !dbg !15 + %cmp = icmp eq i32 %rem, 0, !dbg !15 + %lnot = xor i1 %cmp, true, !dbg !15 + %lnot1 = xor i1 %lnot, true, !dbg !15 + %lnot.ext = zext i1 %lnot1 to i32, !dbg !15 + %conv = sext i32 %lnot.ext to i64, !dbg !15 + %tobool = icmp ne i64 %conv, 0, !dbg !15 + br i1 %tobool, label %if.then, label %if.else, !dbg !15 + +if.then: ; preds = %entry + %3 = load i32, i32* %rando, align 4, !dbg !16, !tbaa !10 + %call2 = call i32 @baz(i32 %3), !dbg !16 + store i32 %call2, i32* %x, align 4, !dbg !16, !tbaa !10 + br label %if.end, !dbg !17 + +if.else: ; preds = %entry + %call3 = call i32 @foo(i32 50), !dbg !18 + store i32 %call3, i32* %x, align 4, !dbg !18, !tbaa !10 + br label %if.end + +if.end: ; preds = %if.else, %if.then + %4 = load i32, i32* %x, align 4, !dbg !19, !tbaa !10 + %5 = bitcast i32* %x to i8*, !dbg !20 + call void @llvm.lifetime.end.p0i8(i64 4, i8* %5) #4, !dbg !20 + %6 = bitcast i32* %rando to i8*, !dbg !20 + call void @llvm.lifetime.end.p0i8(i64 4, i8* %6) #4, !dbg !20 + ret i32 %4, !dbg !19 +} + +; Function Attrs: argmemonly nounwind willreturn +declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1 + +declare i32 @buzz(...) #2 + +; Function Attrs: nounwind readnone willreturn +declare i64 @llvm.expect.i64(i64, i64) #3 + +declare i32 @baz(i32) #2 + +declare i32 @foo(i32) #2 + +; Function Attrs: argmemonly nounwind willreturn +declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1 + +attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #1 = { argmemonly nounwind willreturn } +attributes #2 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #3 = { nounwind readnone willreturn } +attributes #4 = { nounwind } + +!llvm.dbg.cu = !{!0} +!llvm.module.flags = !{!3, !4} +!llvm.ident = !{!5} + +!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 10.0.0 (trunk c20270bfffc9d6965219de339d66c61e9fe7d82d)", isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !2, nameTableKind: None) +!1 = !DIFile(filename: "<stdin>", directory: ".") +!2 = !{} +!3 = !{i32 2, !"Debug Info Version", i32 3} +!4 = !{i32 1, !"wchar_size", i32 4} +!5 = !{!"clang version 10.0.0 (trunk c20270bfffc9d6965219de339d66c61e9fe7d82d)"} +!6 = distinct !DISubprogram(name: "bar", scope: !7, file: !7, line: 19, type: !8, scopeLine: 19, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2) +!7 = !DIFile(filename: "misexpect-branch.c", directory: ".") +!8 = !DISubroutineType(types: !2) +!9 = !DILocation(line: 20, scope: !6) +!10 = !{!11, !11, i64 0} +!11 = !{!"int", !12, i64 0} +!12 = !{!"omnipotent char", !13, i64 0} +!13 = !{!"Simple C/C++ TBAA"} +!14 = !DILocation(line: 21, scope: !6) +!15 = !DILocation(line: 22, scope: !6) +!16 = !DILocation(line: 23, scope: !6) +!17 = !DILocation(line: 24, scope: !6) +!18 = !DILocation(line: 25, scope: !6) +!19 = !DILocation(line: 27, scope: !6) +!20 = !DILocation(line: 28, scope: !6) `````````` </details> https://github.com/llvm/llvm-project/pull/96523 _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
