[misexpect] [WIP] Enable diagnostics for profitable llvm.expect annotations

[paulkirth]

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).

[paulkirth]

TODOs

1. Refactor code to live separately from MisExpect.cpp -- alternatively, we could leave them combined and rename the files to PGODiagUtils or something
2. Address Frontend Profiling
3. Support Sample Profiling -- this may be hard until we can track branch_weight provenance from llvm.expect
4. We should land the cleanups in D128860 and D128858 before landing this, since those should make the implementation cleaner.

[paulkirth]

Refactor an clean ups

[paulkirth]

Clean up code.

Replace code repitition w/ functions.
Refactor comon functionality to share between diagnostics

[paulkirth]

Small update

[paulkirth]

While WIP, this is far enough along that I'd like to start getting some feedback.

Outstanding Issues:

1. more/better tests (loops!)
2. Should we rename/reorg files+code?
3. audit data types (do we need 64-bit everywhere?)
4. Small code cleanups (MissingAnnotations belongs in it's own namespace)

One thing I'm considering here is if the missing annotation checks/diagnostics should be part of MisExpect or not. One option is to rename MisExpect.cpp something like ProfilingDiags.cpp or ExpectDiagnostics.cpp, and leave these implementations combined. Splitting this up also has some advantages, but then maybe the common bits will need to be extracted into a library.

llvm/lib/Transforms/Utils/MisExpect.cpp

293–301

This can probably be cleaned up/removed, since D131136 implements support for frontend profiling.

[paulkirth]

llvm/lib/Transforms/Utils/MisExpect.cpp

178–179

Needs a rebase, since this is now gone

[paulkirth]

Rebase

llvm/include/llvm/IR/LLVMContext.h

#undef LLVM_FIXED_MD_KIND
   /// Set if a code hotness metric should be included in optimization
   /// diagnostics.
   void setDiagnosticsHotnessRequested(bool Requested);
 
   bool getMisExpectWarningRequested() const;
   void setMisExpectWarningRequested(bool Requested);
   void setDiagnosticsMisExpectTolerance(Optional<uint64_t> 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.
   ///
   /// Three possible return values:
   /// 0            - threshold is disabled. Everything will be printed out.
   /// positive int - threshold is set.
   /// UINT64_MAX   - threshold is not yet set, and needs to be synced from

llvm/include/llvm/Transforms/Utils/MisExpect.h

 ///
 /// \param I The Instruction being checked
 /// \param RealWeights A vector of profile weights for each target block
 /// \param IsBackend A boolean describing if this is Frontend instrumentation
 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

llvm/lib/IR/LLVMContext.cpp

void LLVMContext::setDiagnosticsHotnessThreshold(Optional<uint64_t> Threshold) {
   pImpl->DiagnosticsHotnessThreshold = Threshold;
 }
 void LLVMContext::setMisExpectWarningRequested(bool Requested) {
   pImpl->MisExpectWarningRequested = Requested;
 }
 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);
 }
 void LLVMContext::setDiagnosticsMisExpectTolerance(
     Optional<uint64_t> Tolerance) {
   pImpl->DiagnosticsMisExpectTolerance = Tolerance;
 }
 uint64_t LLVMContext::getDiagnosticsMisExpectTolerance() const {

llvm/lib/IR/LLVMContextImpl.h

public:
   /// If threshold option is not specified, it is disabled (0) by default.
   Optional<uint64_t> DiagnosticsHotnessThreshold = 0;
 
   /// The percentage of difference between profiling branch weights and
   // llvm.expect branch weights to tolerate when emiting MisExpect diagnostics
   Optional<uint64_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;
 
   LLVMContext::YieldCallbackTy YieldCallback = nullptr;
   void *YieldOpaqueHandle = nullptr;
 
   DenseMap<const Value *, ValueName *> ValueNames;
 

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

for (const auto &ECI : EdgeCounts)
     Weights.push_back(scaleBranchCount(ECI, Scale));
 
   LLVM_DEBUG(dbgs() << "Weight is: "; for (const auto &W
                                            : Weights) {
     dbgs() << W << " ";
   } dbgs() << "\n";);
 
   misexpect::checkExpectAnnotations(*TI, Weights, /*IsFrontend=*/false);
+  misexpect::checkMissingAnnotations(*TI, Weights, /*IsFrontend=*/false);
 
   TI->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
   if (EmitBranchProbability) {
     std::string BrCondStr = getBranchCondString(TI);
     if (BrCondStr.empty())
       return;
 
     uint64_t WSum =

llvm/lib/Transforms/Utils/MisExpect.cpp

static cl::opt<bool> PGOWarnMisExpect(
     cl::desc("Use this option to turn on/off "
              "warnings about incorrect usage of llvm.expect intrinsics."));
 
 static cl::opt<unsigned> MisExpectTolerance(
     "misexpect-tolerance", cl::init(0),
     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<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 {
 
+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) {
   return std::max(static_cast<uint64_t>(MisExpectTolerance),
                   Ctx.getDiagnosticsMisExpectTolerance());
 }
void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx,
   Twine Msg(PerString);
   Instruction *Cond = getInstCondition(I);
   if (isMisExpectDiagEnabled(Ctx))
     Ctx.diagnose(DiagnosticInfoMisExpect(Cond, Msg));
   OptimizationRemarkEmitter ORE(I->getParent()->getParent());
   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 {
 namespace misexpect {
 
 // Helper function to extract branch weights into a vector
 Optional<SmallVector<uint32_t, 4>> extractWeights(Instruction *I,
                                                   LLVMContext &Ctx) {

 }
 
 // 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;
 }
 
 void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights,
                      ArrayRef<uint32_t> ExpectedWeights) {
   // 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.
void checkExpectAnnotations(Instruction &I,
                             const ArrayRef<uint32_t> ExistingWeights,
                             bool IsFrontendInstr) {
   if (IsFrontendInstr) {
     checkFrontendInstrumentation(I, ExistingWeights);
   } else {
     checkBackendInstrumentation(I, ExistingWeights);
   }
 }
+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 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<uint64_t>());
+  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<uint32_t> 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
 #undef DEBUG_TYPE

llvm/test/Transforms/PGOProfile/missing-annotation.ll

+; 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: "<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)