LLVM 20.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"
35#include "llvm/IR/Instruction.h"
37#include "llvm/IR/LLVMContext.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
50using namespace llvm;
51using namespace misexpect;
52
53namespace 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
62// Command line option for setting the diagnostic tolerance threshold
64 "misexpect-tolerance", cl::init(0),
65 cl::desc("Prevents emitting diagnostics when profile counts are "
66 "within N% of the threshold.."));
67
68} // namespace llvm
69
70namespace {
71
72bool isMisExpectDiagEnabled(LLVMContext &Ctx) {
74}
75
76uint32_t getMisExpectTolerance(LLVMContext &Ctx) {
77 return std::max(static_cast<uint32_t>(MisExpectTolerance),
79}
80
81Instruction *getInstCondition(Instruction *I) {
82 assert(I != nullptr && "MisExpect target Instruction cannot be nullptr");
83 Instruction *Ret = nullptr;
84 if (auto *B = dyn_cast<BranchInst>(I)) {
85 Ret = dyn_cast<Instruction>(B->getCondition());
86 }
87 // TODO: Find a way to resolve condition location for switches
88 // Using the condition of the switch seems to often resolve to an earlier
89 // point in the program, i.e. the calculation of the switch condition, rather
90 // than the switch's location in the source code. Thus, we should use the
91 // instruction to get source code locations rather than the condition to
92 // improve diagnostic output, such as the caret. If the same problem exists
93 // for branch instructions, then we should remove this function and directly
94 // use the instruction
95 //
96 else if (auto *S = dyn_cast<SwitchInst>(I)) {
97 Ret = dyn_cast<Instruction>(S->getCondition());
98 }
99 return Ret ? Ret : I;
100}
101
102void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx,
103 uint64_t ProfCount, uint64_t TotalCount) {
104 double PercentageCorrect = (double)ProfCount / TotalCount;
105 auto PerString =
106 formatv("{0:P} ({1} / {2})", PercentageCorrect, ProfCount, TotalCount);
107 auto RemStr = formatv(
108 "Potential performance regression from use of the llvm.expect intrinsic: "
109 "Annotation was correct on {0} of profiled executions.",
110 PerString);
111 Twine Msg(PerString);
112 Instruction *Cond = getInstCondition(I);
113 if (isMisExpectDiagEnabled(Ctx))
115 OptimizationRemarkEmitter ORE(I->getParent()->getParent());
116 ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str());
117}
118
119} // namespace
120
121namespace llvm {
122namespace misexpect {
123
125 ArrayRef<uint32_t> ExpectedWeights) {
126 // To determine if we emit a diagnostic, we need to compare the branch weights
127 // from the profile to those added by the llvm.expect intrinsic.
128 // So first, we extract the "likely" and "unlikely" weights from
129 // ExpectedWeights And determine the correct weight in the profile to compare
130 // against.
132 UnlikelyBranchWeight = std::numeric_limits<uint32_t>::max();
133 size_t MaxIndex = 0;
134 for (size_t Idx = 0, End = ExpectedWeights.size(); Idx < End; Idx++) {
135 uint32_t V = ExpectedWeights[Idx];
136 if (LikelyBranchWeight < V) {
138 MaxIndex = Idx;
139 }
140 if (UnlikelyBranchWeight > V) {
142 }
143 }
144
145 const uint64_t ProfiledWeight = RealWeights[MaxIndex];
146 const uint64_t RealWeightsTotal =
147 std::accumulate(RealWeights.begin(), RealWeights.end(), (uint64_t)0,
148 std::plus<uint64_t>());
149 const uint64_t NumUnlikelyTargets = RealWeights.size() - 1;
150
151 uint64_t TotalBranchWeight =
152 LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets);
153
154 // Failing this assert means that we have corrupted metadata.
155 assert((TotalBranchWeight >= LikelyBranchWeight) && (TotalBranchWeight > 0) &&
156 "TotalBranchWeight is less than the Likely branch weight");
157
158 // To determine our threshold value we need to obtain the branch probability
159 // for the weights added by llvm.expect and use that proportion to calculate
160 // our threshold based on the collected profile data.
161 auto LikelyProbablilty = BranchProbability::getBranchProbability(
162 LikelyBranchWeight, TotalBranchWeight);
163
164 uint64_t ScaledThreshold = LikelyProbablilty.scale(RealWeightsTotal);
165
166 // clamp tolerance range to [0, 100)
167 auto Tolerance = getMisExpectTolerance(I.getContext());
168 Tolerance = std::clamp(Tolerance, 0u, 99u);
169
170 // Allow users to relax checking by N% i.e., if they use a 5% tolerance,
171 // then we check against 0.95*ScaledThreshold
172 if (Tolerance > 0)
173 ScaledThreshold *= (1.0 - Tolerance / 100.0);
174
175 // When the profile weight is below the threshold, we emit the diagnostic
176 if (ProfiledWeight < ScaledThreshold)
177 emitMisexpectDiagnostic(&I, I.getContext(), ProfiledWeight,
178 RealWeightsTotal);
179}
180
182 const ArrayRef<uint32_t> RealWeights) {
183 // Backend checking assumes any existing weight comes from an `llvm.expect`
184 // intrinsic. However, SampleProfiling + ThinLTO add branch weights multiple
185 // times, leading to an invalid assumption in our checking. Backend checks
186 // should only operate on branch weights that carry the "!expected" field,
187 // since they are guaranteed to be added by the LowerExpectIntrinsic pass.
189 return;
190 SmallVector<uint32_t> ExpectedWeights;
191 if (!extractBranchWeights(I, ExpectedWeights))
192 return;
193 verifyMisExpect(I, RealWeights, ExpectedWeights);
194}
195
197 const ArrayRef<uint32_t> ExpectedWeights) {
198 SmallVector<uint32_t> RealWeights;
199 if (!extractBranchWeights(I, RealWeights))
200 return;
201 verifyMisExpect(I, RealWeights, ExpectedWeights);
202}
203
205 const ArrayRef<uint32_t> ExistingWeights,
206 bool IsFrontend) {
207 if (IsFrontend) {
208 checkFrontendInstrumentation(I, ExistingWeights);
209 } else {
210 checkBackendInstrumentation(I, ExistingWeights);
211 }
212}
213
214} // namespace misexpect
215} // namespace llvm
216#undef DEBUG_TYPE
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
bool End
Definition: ELF_riscv.cpp:480
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)"))
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)"))
#define I(x, y, z)
Definition: MD5.cpp:58
#define DEBUG_TYPE
Definition: MisExpect.cpp:48
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:154
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
iterator begin() const
Definition: ArrayRef.h:153
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
Diagnostic information for MisExpect analysis.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
bool getMisExpectWarningRequested() const
void diagnose(const DiagnosticInfo &DI)
Report a message to the currently installed diagnostic handler.
uint32_t getDiagnosticsMisExpectTolerance() const
The optimization diagnostic interface.
Diagnostic information for applied optimization remarks.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
void checkFrontendInstrumentation(Instruction &I, const ArrayRef< uint32_t > ExpectedWeights)
checkFrontendInstrumentation - compares PGO counters to the thresholds used for llvm....
Definition: MisExpect.cpp:196
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:204
void checkBackendInstrumentation(Instruction &I, const llvm::ArrayRef< uint32_t > RealWeights)
checkBackendInstrumentation - compares PGO counters to the thresholds used for llvm....
Definition: MisExpect.cpp:181
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:124
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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."))
auto formatv(const char *Fmt, Ts &&...Vals) -> formatv_object< decltype(std::make_tuple(support::detail::build_format_adapter(std::forward< Ts >(Vals))...))>
bool hasBranchWeightOrigin(const Instruction &I)
Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.
static cl::opt< uint32_t > MisExpectTolerance("misexpect-tolerance", cl::init(0), cl::desc("Prevents emitting diagnostics when profile counts are " "within N% of the threshold.."))
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.