[misexpect] Support diagnostics from frontend profile data

[paulkirth]

Summary

Adds support for suggesting profitable llvm.expect based on frontend
profiling instrumentation.

[paulkirth]

Fix tests and fronend integration

[paulkirth]

Rebase

[tejohnson]

I'm not sure of the status of these patches, since the base one is still marked "WIP". Some comments below on this patch, but are they all ready for review? If so, WIP should probably be removed from D129889.

llvm/include/llvm/Target/TargetOptions.h

366

Needs its own comment.

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

366

I take it a return value of false from then handle*Expect functions means there was not an expect? Would be good to note this in a comment (here and in the switch handling later). Also, suggest moving this down into lowerExpectIntrinsic to mirror where/how switch are handled.

llvm/lib/Transforms/Utils/MisExpect.cpp

311

It doesn't seem like this patch includes a test for this new invocation of verifyMissingAnnotations - can one be added?

317

Should these commented out lines be removed now?

llvm/include/llvm/Target/TargetOptions.h

public:
     unsigned JMCInstrument : 1;
 
     /// Enable the CFIFixup pass.
     unsigned EnableCFIFixup : 1;
 
     /// When set to true, enable MisExpect Diagnostics
     /// By default, it is set to false
     unsigned MisExpect : 1;
+    unsigned MissingAnnotations : 1;
 
     /// Name of the stack usage file (i.e., .su file) if user passes
     /// -fstack-usage. If empty, it can be implied that -fstack-usage is not
     /// passed on the command line.
     std::string StackUsageOutput;
 
     /// If greater than 0, override TargetLoweringBase::PrefLoopAlignment.
     unsigned LoopAlignment = 0;

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/ProfDataUtils.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/MisExpect.h"
 
 #include <cmath>
 
template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
   BSI.setMetadata(LLVMContext::MD_prof, Node);
 
   return true;
 }
 
 static bool handleBranchExpect(BranchInst &BI) {
   if (BI.isUnconditional())
     return false;
-
-  return handleBrSelExpect<BranchInst>(BI);
+  auto ret = handleBrSelExpect<BranchInst>(BI);
+  if (!ret) {
+    SmallVector<uint32_t> Weights;
+    if (extractBranchWeights(BI, Weights))
+      misexpect::checkMissingAnnotations(BI, Weights, /*isFrontend=*/true);
+  }
+  return ret;
 }
 
 static bool lowerExpectIntrinsic(Function &F) {
   bool Changed = false;
 
   for (BasicBlock &BB : F) {
     // Create "block_weights" metadata.
     if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
       if (handleBranchExpect(*BI))
         ExpectIntrinsicsHandled++;
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
       if (handleSwitchExpect(*SI))
         ExpectIntrinsicsHandled++;
+      else {
+        SmallVector<uint32_t> Weights;
+        if (extractBranchWeights(*SI, Weights))
+          misexpect::checkMissingAnnotations(*SI, Weights, /*isFrontend=*/true);
+      }
     }
 
     // Remove llvm.expect intrinsics. Iterate backwards in order
     // to process select instructions before the intrinsic gets
     // removed.
     for (Instruction &Inst : llvm::make_early_inc_range(llvm::reverse(BB))) {
       CallInst *CI = dyn_cast<CallInst>(&Inst);
       if (!CI) {

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<uint32_t> 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
+// 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
void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx,
   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-annotation", "missing-annotation", Cond)
-           << RemStr);
+  ORE.emit(
+      OptimizationRemark("missing-annotations", "missing-annotations", Cond)
 }
 
 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) {

 namespace llvm {
 namespace misexpect {
 
 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
+  // ExpectedWeights and determine the correct weight in the profile to compare
   // against.
   uint64_t LikelyBranchWeight = 0,
            UnlikelyBranchWeight = std::numeric_limits<uint32_t>::max();
   size_t MaxIndex = 0;
   for (size_t Idx = 0, End = ExpectedWeights.size(); Idx < End; Idx++) {
     uint32_t V = ExpectedWeights[Idx];
     if (LikelyBranchWeight < V) {
       LikelyBranchWeight = V;
if (IsFrontend) {
     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 that would be added by the llvm.expect intrinsic.
-  // And compare it to the real profile to see if it would be profitable.
+  // to see if adding an annotation 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) {
-
-  // TODO: Ironically, this is probably a branch that should be marked UNLIKELY
   //  exit early if these diagnostics weren't requested
-  if (!isAnnotationDiagEnabled(I.getContext()))
+  if (LLVM_LIKELY(!isAnnotationDiagEnabled(I.getContext())))
     return;
 
   if (IsFrontendInstr) {
-    // TODO: Fronend checking will have to be thought through, since we need
+    // TODO: Frontend checking will have to be thought through, since we need
     // to do the check on branches that don't have expect intrinsics
+    verifyMissingAnnotations(I, ExistingWeights);
 
     // auto RealWeightsOpt = extractWeights(&I, I.getContext());
     // if (!RealWeightsOpt)
     // return;
     // auto RealWeights = RealWeightsOpt.getValue();
     // verifyMissingAnnotations(I, RealWeights, ExistingWeights);
   } else {
     SmallVector<uint32_t> ExpectedWeights;
     if (extractBranchWeights(I, ExpectedWeights))
       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
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-missing-annotations -pass-remarks=missing-annotations -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}