llvm/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's implementation relies on two assumptions about how branch weights
  15 // are managed in LLVM.
  16 //
  17 // 1) Frontend profiling weights are always in place before llvm.expect is
  18 // lowered in LowerExpectIntrinsic.cpp. Frontend based instrumentation therefore
  19 // needs to extract the branch weights and then compare them to the weights
  20 // being added by the llvm.expect intrinsic lowering.
  21 //
  22 // 2) Sampling and IR based profiles will *only* have branch weight metadata
  23 // before profiling data is consulted if they are from a lowered llvm.expect
  24 // intrinsic. These profiles thus always extract the expected weights and then
  25 // compare them to the weights collected during profiling to determine if a
  26 // diagnostic message is warranted.
  27 //
  28 //===----------------------------------------------------------------------===//
  29
  30 #include "llvm/Transforms/Utils/MisExpect.h"
  31 #include "llvm/ADT/Twine.h"
  32 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  33 #include "llvm/IR/Constants.h"
  34 #include "llvm/IR/DiagnosticInfo.h"
  35 #include "llvm/IR/Instruction.h"
  36 #include "llvm/IR/Instructions.h"
  37 #include "llvm/IR/LLVMContext.h"
  38 #include "llvm/IR/ProfDataUtils.h"
  39 #include "llvm/Support/BranchProbability.h"
  40 #include "llvm/Support/CommandLine.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/FormatVariadic.h"
  43 #include <algorithm>
  44 #include <cstdint>
  45 #include <functional>
  46 #include <numeric>
  47
  48 #define DEBUG_TYPE "misexpect"
  49
  50 using namespace llvm;
  51 using namespace misexpect;
  52
  53 namespace llvm {
  54
  55 // Command line option to enable/disable the warning when profile data suggests
  56 // a mismatch with the use of the llvm.expect intrinsic
  57 static cl::opt<bool> PGOWarnMisExpect(
  58     "pgo-warn-misexpect", cl::init(false), cl::Hidden,
  59     cl::desc("Use this option to turn on/off "
  60              "warnings about incorrect usage of llvm.expect intrinsics."));
  61
  62 static cl::opt<uint32_t> MisExpectTolerance(
  63     "misexpect-tolerance", cl::init(0),
  64     cl::desc("Prevents emiting diagnostics when profile counts are "
  65              "within N% of the threshold.."));
  66
  67 } // namespace llvm
  68
  69 namespace {
  70
  71 bool isMisExpectDiagEnabled(LLVMContext &Ctx) {
  72   return PGOWarnMisExpect || Ctx.getMisExpectWarningRequested();
  73 }
  74
  75 uint32_t getMisExpectTolerance(LLVMContext &Ctx) {
  76   return std::max(static_cast<uint32_t>(MisExpectTolerance),
  77                   Ctx.getDiagnosticsMisExpectTolerance());
  78 }
  79
  80 Instruction *getInstCondition(Instruction *I) {
  81   assert(I != nullptr && "MisExpect target Instruction cannot be nullptr");
  82   Instruction *Ret = nullptr;
  83   if (auto *B = dyn_cast<BranchInst>(I)) {
  84     Ret = dyn_cast<Instruction>(B->getCondition());
  85   }
  86   // TODO: Find a way to resolve condition location for switches
  87   // Using the condition of the switch seems to often resolve to an earlier
  88   // point in the program, i.e. the calculation of the switch condition, rather
  89   // than the switch's location in the source code. Thus, we should use the
  90   // instruction to get source code locations rather than the condition to
  91   // improve diagnostic output, such as the caret. If the same problem exists
  92   // for branch instructions, then we should remove this function and directly
  93   // use the instruction
  94   //
  95   else if (auto *S = dyn_cast<SwitchInst>(I)) {
  96     Ret = dyn_cast<Instruction>(S->getCondition());
  97   }
  98   return Ret ? Ret : I;
  99 }
 100
 101 void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx,
 102                              uint64_t ProfCount, uint64_t TotalCount) {
 103   double PercentageCorrect = (double)ProfCount / TotalCount;
 104   auto PerString =
 105       formatv("{0:P} ({1} / {2})", PercentageCorrect, ProfCount, TotalCount);
 106   auto RemStr = formatv(
 107       "Potential performance regression from use of the llvm.expect intrinsic: "
 108       "Annotation was correct on {0} of profiled executions.",
 109       PerString);
 110   Twine Msg(PerString);
 111   Instruction *Cond = getInstCondition(I);
 112   if (isMisExpectDiagEnabled(Ctx))
 113     Ctx.diagnose(DiagnosticInfoMisExpect(Cond, Msg));
 114   OptimizationRemarkEmitter ORE(I->getParent()->getParent());
 115   ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str());
 116 }
 117
 118 } // namespace
 119
 120 namespace llvm {
 121 namespace misexpect {
 122
 123 void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights,
 124                      ArrayRef<uint32_t> ExpectedWeights) {
 125   // To determine if we emit a diagnostic, we need to compare the branch weights
 126   // from the profile to those added by the llvm.expect intrinsic.
 127   // So first, we extract the "likely" and "unlikely" weights from
 128   // ExpectedWeights And determine the correct weight in the profile to compare
 129   // against.
 130   uint64_t LikelyBranchWeight = 0,
 131            UnlikelyBranchWeight = std::numeric_limits<uint32_t>::max();
 132   size_t MaxIndex = 0;
 133   for (size_t Idx = 0, End = ExpectedWeights.size(); Idx < End; Idx++) {
 134     uint32_t V = ExpectedWeights[Idx];
 135     if (LikelyBranchWeight < V) {
 136       LikelyBranchWeight = V;
 137       MaxIndex = Idx;
 138     }
 139     if (UnlikelyBranchWeight > V) {
 140       UnlikelyBranchWeight = V;
 141     }
 142   }
 143
 144   const uint64_t ProfiledWeight = RealWeights[MaxIndex];
 145   const uint64_t RealWeightsTotal =
 146       std::accumulate(RealWeights.begin(), RealWeights.end(), (uint64_t)0,
 147                       std::plus<uint64_t>());
 148   const uint64_t NumUnlikelyTargets = RealWeights.size() - 1;
 149
 150   uint64_t TotalBranchWeight =
 151       LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets);
 152
 153   // FIXME: When we've addressed sample profiling, restore the assertion
 154   //
 155   // We cannot calculate branch probability if either of these invariants aren't
 156   // met. However, MisExpect diagnostics should not prevent code from compiling,
 157   // so we simply forgo emitting diagnostics here, and return early.
 158   // assert((TotalBranchWeight >= LikelyBranchWeight) && (TotalBranchWeight > 0)
 159   //              && "TotalBranchWeight is less than the Likely branch weight");
 160   if ((TotalBranchWeight == 0) || (TotalBranchWeight <= LikelyBranchWeight))
 161     return;
 162
 163   // To determine our threshold value we need to obtain the branch probability
 164   // for the weights added by llvm.expect and use that proportion to calculate
 165   // our threshold based on the collected profile data.
 166   auto LikelyProbablilty = BranchProbability::getBranchProbability(
 167       LikelyBranchWeight, TotalBranchWeight);
 168
 169   uint64_t ScaledThreshold = LikelyProbablilty.scale(RealWeightsTotal);
 170
 171   // clamp tolerance range to [0, 100)
 172   auto Tolerance = getMisExpectTolerance(I.getContext());
 173   Tolerance = std::clamp(Tolerance, 0u, 99u);
 174
 175   // Allow users to relax checking by N%  i.e., if they use a 5% tolerance,
 176   // then we check against 0.95*ScaledThreshold
 177   if (Tolerance > 0)
 178     ScaledThreshold *= (1.0 - Tolerance / 100.0);
 179
 180   // When the profile weight is below the threshold, we emit the diagnostic
 181   if (ProfiledWeight < ScaledThreshold)
 182     emitMisexpectDiagnostic(&I, I.getContext(), ProfiledWeight,
 183                             RealWeightsTotal);
 184 }
 185
 186 void checkBackendInstrumentation(Instruction &I,
 187                                  const ArrayRef<uint32_t> RealWeights) {
 188   SmallVector<uint32_t> ExpectedWeights;
 189   if (!extractBranchWeights(I, ExpectedWeights))
 190     return;
 191   verifyMisExpect(I, RealWeights, ExpectedWeights);
 192 }
 193
 194 void checkFrontendInstrumentation(Instruction &I,
 195                                   const ArrayRef<uint32_t> ExpectedWeights) {
 196   SmallVector<uint32_t> RealWeights;
 197   if (!extractBranchWeights(I, RealWeights))
 198     return;
 199   verifyMisExpect(I, RealWeights, ExpectedWeights);
 200 }
 201
 202 void checkExpectAnnotations(Instruction &I,
 203                             const ArrayRef<uint32_t> ExistingWeights,
 204                             bool IsFrontend) {
 205   if (IsFrontend) {
 206     checkFrontendInstrumentation(I, ExistingWeights);
 207   } else {
 208     checkBackendInstrumentation(I, ExistingWeights);
 209   }
 210 }
 211
 212 } // namespace misexpect
 213 } // namespace llvm
 214 #undef DEBUG_TYPE