lib/Transforms/Utils/MisExpect.cpp

   1 //===--- MisExpect.cpp - Check the use of llvm.expect with PGO data -------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This contains code to emit warnings for potentially incorrect usage of the
  10 // llvm.expect intrinsic. This utility extracts the threshold values from
  11 // metadata associated with the instrumented Branch or Switch instruction. The
  12 // threshold values are then used to determine if a warning should be emmited.
  13 //
  14 // MisExpect metadata is generated when llvm.expect intrinsics are lowered see
  15 // LowerExpectIntrinsic.cpp
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/Transforms/Utils/MisExpect.h"
  20 #include "llvm/ADT/Twine.h"
  21 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DiagnosticInfo.h"
  24 #include "llvm/IR/Instruction.h"
  25 #include "llvm/IR/Instructions.h"
  26 #include "llvm/IR/LLVMContext.h"
  27 #include "llvm/Support/BranchProbability.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/FormatVariadic.h"
  30 #include <cstdint>
  31 #include <functional>
  32 #include <numeric>
  33
  34 #define DEBUG_TYPE "misexpect"
  35
  36 using namespace llvm;
  37 using namespace misexpect;
  38
  39 namespace llvm {
  40
  41 // Command line option to enable/disable the warning when profile data suggests
  42 // a mismatch with the use of the llvm.expect intrinsic
  43 static cl::opt<bool> PGOWarnMisExpect(
  44     "pgo-warn-misexpect", cl::init(false), cl::Hidden,
  45     cl::desc("Use this option to turn on/off "
  46              "warnings about incorrect usage of llvm.expect intrinsics."));
  47
  48 } // namespace llvm
  49
  50 namespace {
  51
  52 Instruction *getOprndOrInst(Instruction *I) {
  53   assert(I != nullptr && "MisExpect target Instruction cannot be nullptr");
  54   Instruction *Ret = nullptr;
  55   if (auto *B = dyn_cast<BranchInst>(I)) {
  56     Ret = dyn_cast<Instruction>(B->getCondition());
  57   }
  58   // TODO: Find a way to resolve condition location for switches
  59   // Using the condition of the switch seems to often resolve to an earlier
  60   // point in the program, i.e. the calculation of the switch condition, rather
  61   // than the switches location in the source code. Thus, we should use the
  62   // instruction to get source code locations rather than the condition to
  63   // improve diagnostic output, such as the caret. If the same problem exists
  64   // for branch instructions, then we should remove this function and directly
  65   // use the instruction
  66   //
  67   // else if (auto S = dyn_cast<SwitchInst>(I)) {
  68   // Ret = I;
  69   //}
  70   return Ret ? Ret : I;
  71 }
  72
  73 void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx,
  74                              uint64_t ProfCount, uint64_t TotalCount) {
  75   double PercentageCorrect = (double)ProfCount / TotalCount;
  76   auto PerString =
  77       formatv("{0:P} ({1} / {2})", PercentageCorrect, ProfCount, TotalCount);
  78   auto RemStr = formatv(
  79       "Potential performance regression from use of the llvm.expect intrinsic: "
  80       "Annotation was correct on {0} of profiled executions.",
  81       PerString);
  82   Twine Msg(PerString);
  83   Instruction *Cond = getOprndOrInst(I);
  84   if (PGOWarnMisExpect)
  85     Ctx.diagnose(DiagnosticInfoMisExpect(Cond, Msg));
  86   OptimizationRemarkEmitter ORE(I->getParent()->getParent());
  87   ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str());
  88 }
  89
  90 } // namespace
  91
  92 namespace llvm {
  93 namespace misexpect {
  94
  95 void verifyMisExpect(Instruction *I, const SmallVector<uint32_t, 4> &Weights,
  96                      LLVMContext &Ctx) {
  97   if (auto *MisExpectData = I->getMetadata(LLVMContext::MD_misexpect)) {
  98     auto *MisExpectDataName = dyn_cast<MDString>(MisExpectData->getOperand(0));
  99     if (MisExpectDataName &&
 100         MisExpectDataName->getString().equals("misexpect")) {
 101       LLVM_DEBUG(llvm::dbgs() << "------------------\n");
 102       LLVM_DEBUG(llvm::dbgs()
 103                  << "Function: " << I->getFunction()->getName() << "\n");
 104       LLVM_DEBUG(llvm::dbgs() << "Instruction: " << *I << ":\n");
 105       LLVM_DEBUG(for (int Idx = 0, Size = Weights.size(); Idx < Size; ++Idx) {
 106         llvm::dbgs() << "Weights[" << Idx << "] = " << Weights[Idx] << "\n";
 107       });
 108
 109       // extract values from misexpect metadata
 110       const auto *IndexCint =
 111           mdconst::dyn_extract<ConstantInt>(MisExpectData->getOperand(1));
 112       const auto *LikelyCInt =
 113           mdconst::dyn_extract<ConstantInt>(MisExpectData->getOperand(2));
 114       const auto *UnlikelyCInt =
 115           mdconst::dyn_extract<ConstantInt>(MisExpectData->getOperand(3));
 116
 117       if (!IndexCint || !LikelyCInt || !UnlikelyCInt)
 118         return;
 119
 120       const uint64_t Index = IndexCint->getZExtValue();
 121       const uint64_t LikelyBranchWeight = LikelyCInt->getZExtValue();
 122       const uint64_t UnlikelyBranchWeight = UnlikelyCInt->getZExtValue();
 123       const uint64_t ProfileCount = Weights[Index];
 124       const uint64_t CaseTotal = std::accumulate(
 125           Weights.begin(), Weights.end(), (uint64_t)0, std::plus<uint64_t>());
 126       const uint64_t NumUnlikelyTargets = Weights.size() - 1;
 127
 128       const uint64_t TotalBranchWeight =
 129           LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets);
 130
 131       const llvm::BranchProbability LikelyThreshold(LikelyBranchWeight,
 132                                                     TotalBranchWeight);
 133       uint64_t ScaledThreshold = LikelyThreshold.scale(CaseTotal);
 134
 135       LLVM_DEBUG(llvm::dbgs()
 136                  << "Unlikely Targets: " << NumUnlikelyTargets << ":\n");
 137       LLVM_DEBUG(llvm::dbgs() << "Profile Count: " << ProfileCount << ":\n");
 138       LLVM_DEBUG(llvm::dbgs()
 139                  << "Scaled Threshold: " << ScaledThreshold << ":\n");
 140       LLVM_DEBUG(llvm::dbgs() << "------------------\n");
 141       if (ProfileCount < ScaledThreshold)
 142         emitMisexpectDiagnostic(I, Ctx, ProfileCount, CaseTotal);
 143     }
 144   }
 145 }
 146
 147 void checkFrontendInstrumentation(Instruction &I) {
 148   if (auto *MD = I.getMetadata(LLVMContext::MD_prof)) {
 149     unsigned NOps = MD->getNumOperands();
 150
 151     // Only emit misexpect diagnostics if at least 2 branch weights are present.
 152     // Less than 2 branch weights means that the profiling metadata is:
 153     //    1) incorrect/corrupted
 154     //    2) not branch weight metadata
 155     //    3) completely deterministic
 156     // In these cases we should not emit any diagnostic related to misexpect.
 157     if (NOps < 3)
 158       return;
 159
 160     // Operand 0 is a string tag "branch_weights"
 161     if (MDString *Tag = cast<MDString>(MD->getOperand(0))) {
 162       if (Tag->getString().equals("branch_weights")) {
 163         SmallVector<uint32_t, 4> RealWeights(NOps - 1);
 164         for (unsigned i = 1; i < NOps; i++) {
 165           ConstantInt *Value =
 166               mdconst::dyn_extract<ConstantInt>(MD->getOperand(i));
 167           RealWeights[i - 1] = Value->getZExtValue();
 168         }
 169         verifyMisExpect(&I, RealWeights, I.getContext());
 170       }
 171     }
 172   }
 173 }
 174
 175 } // namespace misexpect
 176 } // namespace llvm
 177 #undef DEBUG_TYPE