diff --git a/llvm/include/llvm/IR/LLVMContext.h b/llvm/include/llvm/IR/LLVMContext.h --- a/llvm/include/llvm/IR/LLVMContext.h +++ b/llvm/include/llvm/IR/LLVMContext.h @@ -207,6 +207,8 @@ void setMisExpectWarningRequested(bool Requested); void setDiagnosticsMisExpectTolerance(Optional Tolerance); uint64_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/Transforms/Utils/MisExpect.h b/llvm/include/llvm/Transforms/Utils/MisExpect.h --- a/llvm/include/llvm/Transforms/Utils/MisExpect.h +++ b/llvm/include/llvm/Transforms/Utils/MisExpect.h @@ -76,6 +76,9 @@ const ArrayRef ExistingWeights, bool IsFrontend); +void checkMissingAnnotations(Instruction &I, + const ArrayRef ExistingWeights, + bool IsFrontendInstr); } // namespace misexpect } // namespace llvm diff --git a/llvm/lib/IR/LLVMContext.cpp b/llvm/lib/IR/LLVMContext.cpp --- a/llvm/lib/IR/LLVMContext.cpp +++ b/llvm/lib/IR/LLVMContext.cpp @@ -144,6 +144,12 @@ bool LLVMContext::getMisExpectWarningRequested() const { return pImpl->MisExpectWarningRequested; } +void LLVMContext::setAnnotationDiagsRequested(bool Requested) { + pImpl->AnnotationsDiagsRequested = Requested; +} +bool LLVMContext::getAnnotationDiagsRequested() const { + return pImpl->AnnotationsDiagsRequested; +} uint64_t LLVMContext::getDiagnosticsHotnessThreshold() const { return pImpl->DiagnosticsHotnessThreshold.value_or(UINT64_MAX); } diff --git a/llvm/lib/IR/LLVMContextImpl.h b/llvm/lib/IR/LLVMContextImpl.h --- a/llvm/lib/IR/LLVMContextImpl.h +++ b/llvm/lib/IR/LLVMContextImpl.h @@ -1390,6 +1390,10 @@ Optional 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 LLVMRS; diff --git a/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp b/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp --- a/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp +++ b/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp @@ -1977,6 +1977,7 @@ } dbgs() << "\n";); misexpect::checkExpectAnnotations(*TI, Weights, /*IsFrontend=*/false); + misexpect::checkMissingAnnotations(*TI, Weights, /*IsFrontend=*/false); TI->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights)); if (EmitBranchProbability) { diff --git a/llvm/lib/Transforms/Utils/MisExpect.cpp b/llvm/lib/Transforms/Utils/MisExpect.cpp --- a/llvm/lib/Transforms/Utils/MisExpect.cpp +++ b/llvm/lib/Transforms/Utils/MisExpect.cpp @@ -63,15 +63,66 @@ cl::desc("Prevents emiting diagnostics when profile counts are " "within N% of the threshold..")); +// Command line option to enable/disable the Remparks when profile data suggests +// that the llvm.expect intrinsic may be profitable +static cl::opt + 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, + MissingExpect, + None, +}; + +llvm::Optional 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"); + + // FIXME: When we've addressed sample profiling, restore the assertion + // + // We cannot calculate branch probability if either of these invariants aren't + // met. However, MisExpect diagnostics should not prevent code from compiling, + // so we simply forgo emitting diagnostics here, and return early. + if ((TotalBranchWeight == 0) || (TotalBranchWeight <= PDS.Likely)) + return None; + + // 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(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(); } -uint64_t getMisExpectTolerance(LLVMContext &Ctx) { +uint64_t getTolerance(LLVMContext &Ctx) { return std::max(static_cast(MisExpectTolerance), Ctx.getDiagnosticsMisExpectTolerance()); } @@ -114,20 +165,74 @@ ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str()); } -} // namespace +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-annotation", "missing-annotation", Cond) + << RemStr); +} -namespace llvm { -namespace misexpect { +uint64_t totalWeight(const ArrayRef Weights) { + return std::accumulate(Weights.begin(), Weights.end(), (uint64_t)0, + std::plus()); +} // TODO: when clang allows c++17, use std::clamp instead -uint32_t clamp(uint64_t value, uint32_t low, uint32_t hi) { - if (value > hi) - return hi; - if (value < low) - return low; - return value; +uint32_t clamp(uint64_t Value, uint32_t Low, uint32_t Hi) { + if (Value > Hi) + return Hi; + if (Value < Low) + return Low; + return Value; +} + +void scaleByTollerance(const Instruction &I, uint64_t &ScaledThreshold) { + // clamp tolerance range to [0, 100) + auto Tolerance = getTolerance(I.getContext()); + Tolerance = clamp(Tolerance, 0, 99); + + // 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) { + auto ScaledOpt = getScaledThreshold(PDS); + if (!ScaledOpt) + return; + uint64_t ScaledThreshold = ScaledOpt.value(); + scaleByTollerance(I, ScaledThreshold); + + // When the profile weight is below the threshold, 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; + case DiagKind::None: + // do some error stuff + return; + }; +} + +} // namespace + +namespace llvm { +namespace misexpect { + void verifyMisExpect(Instruction &I, ArrayRef RealWeights, ArrayRef ExpectedWeights) { // To determine if we emit a diagnostic, we need to compare the branch weights @@ -148,45 +253,11 @@ UnlikelyBranchWeight = V; } } - const uint64_t ProfiledWeight = RealWeights[MaxIndex]; - const uint64_t RealWeightsTotal = - std::accumulate(RealWeights.begin(), RealWeights.end(), (uint64_t)0, - std::plus()); - const uint64_t NumUnlikelyTargets = RealWeights.size() - 1; - - uint64_t TotalBranchWeight = - LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets); - - // FIXME: When we've addressed sample profiling, restore the assertion - // - // We cannot calculate branch probability if either of these invariants aren't - // met. However, MisExpect diagnostics should not prevent code from compiling, - // so we simply forgo emitting diagnostics here, and return early. - if ((TotalBranchWeight == 0) || (TotalBranchWeight <= LikelyBranchWeight)) - return; - - // 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 = clamp(Tolerance, 0, 99); - - // 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, @@ -214,6 +285,46 @@ checkBackendInstrumentation(I, ExistingWeights); } } +void verifyMissingAnnotations(Instruction &I, ArrayRef 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 ExistingWeights, + bool IsFrontendInstr) { + + // TODO: Ironically, this is probably a branch that should be marked UNLIKELY + // exit early if these diagnostics weren't requested + if (!isAnnotationDiagEnabled(I.getContext())) + return; + + if (IsFrontendInstr) { + // TODO: Fronend checking will have to be thought through, since we need + // to do the check on branches that don't have expect intrinsics + + // auto RealWeightsOpt = extractWeights(&I, I.getContext()); + // if (!RealWeightsOpt) + // return; + // auto RealWeights = RealWeightsOpt.getValue(); + // verifyMissingAnnotations(I, RealWeights, ExistingWeights); + } else { + SmallVector ExpectedWeights; + if (extractBranchWeights(I, ExpectedWeights)) + return; + verifyMissingAnnotations(I, ExistingWeights); + } +} } // namespace misexpect } // namespace llvm diff --git a/llvm/test/Transforms/PGOProfile/missing-annotation.ll b/llvm/test/Transforms/PGOProfile/missing-annotation.ll new file mode 100644 --- /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: "", 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)