LLVM  17.0.0git
MisExpect.cpp
Go to the documentation of this file.
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 
31 #include "llvm/ADT/Twine.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"
41 #include "llvm/Support/Debug.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
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 
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) {
73 }
74 
75 uint32_t getMisExpectTolerance(LLVMContext &Ctx) {
76  return std::max(static_cast<uint32_t>(MisExpectTolerance),
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))
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 
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.
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) {
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 
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 
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 
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
llvm::misexpect::checkFrontendInstrumentation
void checkFrontendInstrumentation(Instruction &I, const ArrayRef< uint32_t > ExpectedWeights)
checkFrontendInstrumentation - compares PGO counters to the thresholds used for llvm....
Definition: MisExpect.cpp:194
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LLVMContext::getMisExpectWarningRequested
bool getMisExpectWarningRequested() const
Definition: LLVMContext.cpp:149
double
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in and only one load from a constant double
Definition: README-SSE.txt:85
llvm::SmallVector< uint32_t >
llvm::PGOWarnMisExpect
static cl::opt< bool > PGOWarnMisExpect("pgo-warn-misexpect", cl::init(false), cl::Hidden, cl::desc("Use this option to turn on/off " "warnings about incorrect usage of llvm.expect intrinsics."))
OptimizationRemarkEmitter.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:138
DEBUG_TYPE
#define DEBUG_TYPE
Definition: MisExpect.cpp:48
llvm::BranchProbability::getBranchProbability
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
Definition: BranchProbability.cpp:53
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
UnlikelyBranchWeight
static cl::opt< uint32_t > UnlikelyBranchWeight("unlikely-branch-weight", cl::Hidden, cl::init(1), cl::desc("Weight of the branch unlikely to be taken (default = 1)"))
Instruction.h
CommandLine.h
llvm::formatv
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
Definition: FormatVariadic.h:251
Constants.h
Twine.h
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:41
llvm::DiagnosticInfoMisExpect
Diagnostic information for MisExpect analysis.
Definition: DiagnosticInfo.h:1036
FormatVariadic.h
BranchProbability.h
llvm::MisExpectTolerance
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.."))
llvm::cl::opt< bool >
llvm::LLVMContext::getDiagnosticsMisExpectTolerance
uint32_t getDiagnosticsMisExpectTolerance() const
Definition: LLVMContext.cpp:159
uint64_t
MisExpect.h
ProfDataUtils.h
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
llvm::misexpect::checkExpectAnnotations
void checkExpectAnnotations(Instruction &I, const ArrayRef< uint32_t > ExistingWeights, bool IsFrontend)
checkExpectAnnotations - compares PGO counters to the thresholds used for llvm.expect and warns if th...
Definition: MisExpect.cpp:202
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LikelyBranchWeight
static cl::opt< uint32_t > LikelyBranchWeight("likely-branch-weight", cl::Hidden, cl::init(2000), cl::desc("Weight of the branch likely to be taken (default = 2000)"))
llvm::misexpect::checkBackendInstrumentation
void checkBackendInstrumentation(Instruction &I, const llvm::ArrayRef< uint32_t > RealWeights)
checkBackendInstrumentation - compares PGO counters to the thresholds used for llvm....
Definition: MisExpect.cpp:186
llvm::ArrayRef< uint32_t >
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
uint32_t
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::AMDGPU::SendMsg::Msg
const CustomOperand< const MCSubtargetInfo & > Msg[]
Definition: AMDGPUAsmUtils.cpp:39
llvm::LLVMContext::diagnose
void diagnose(const DiagnosticInfo &DI)
Report a message to the currently installed diagnostic handler.
Definition: LLVMContext.cpp:248
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:151
llvm::misexpect::verifyMisExpect
void verifyMisExpect(Instruction &I, ArrayRef< uint32_t > RealWeights, const ArrayRef< uint32_t > ExpectedWeights)
veryifyMisExpect - compares RealWeights to the thresholds used for llvm.expect and warns if the PGO c...
Definition: MisExpect.cpp:123
DiagnosticInfo.h
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:689
Instructions.h
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
llvm::extractBranchWeights
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
Definition: ProfDataUtils.cpp:122
LLVMContext.h
llvm::cl::desc
Definition: CommandLine.h:411
Debug.h
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:152