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 @@ -73,5 +73,8 @@ 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,9 @@ 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 @@ -1966,6 +1966,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 @@ -62,10 +62,24 @@ 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 { +bool isAnnotationDiagEnabled(LLVMContext &Ctx) { + LLVM_DEBUG(dbgs() << "PGOMissingAnnotations = " << PGOMissingAnnotations + << "\n"); + return PGOMissingAnnotations || Ctx.getAnnotationDiagsRequested(); +} + bool isMisExpectDiagEnabled(LLVMContext &Ctx) { return PGOWarnMisExpect || Ctx.getMisExpectWarningRequested(); } @@ -113,6 +127,15 @@ ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str()); } +void emitMissingAnnotationDiag(Instruction *I) { + auto RemStr = + "Exremely 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 namespace llvm { @@ -243,6 +266,86 @@ 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 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 + // against. + uint64_t LikelyBranchWeight = 2000, UnlikelyBranchWeight = 1; + uint32_t ProfiledWeight = + *std::max_element(RealWeights.begin(), RealWeights.end()); + + 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); + + LLVM_DEBUG(dbgs() << "Total Branch Weight = " << TotalBranchWeight << "\n" + << "Likely Branch Weight = " << LikelyBranchWeight << "\n" + << "Profiled Weight = " << ProfiledWeight << "\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 <= 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); + + // TODO: maybe rename tolerance function + // 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); + + LLVM_DEBUG(dbgs() << "Scaled Threshold = " << ScaledThreshold << "\n"); + + // When the profile weight is below the threshold, we emit the diagnostic + if (ProfiledWeight > ScaledThreshold) + emitMissingAnnotationDiag(&I); +} + +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 { + auto ExpectedWeightsOpt = extractWeights(&I, I.getContext()); + if (ExpectedWeightsOpt) + 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: Exremely 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)