LLVM 19.0.0git
LowerExpectIntrinsic.cpp
Go to the documentation of this file.
1//===- LowerExpectIntrinsic.cpp - Lower expect intrinsic ------------------===//
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 pass lowers the 'expect' intrinsic to LLVM metadata.
10//
11//===----------------------------------------------------------------------===//
12
15#include "llvm/ADT/Statistic.h"
16#include "llvm/IR/BasicBlock.h"
17#include "llvm/IR/Constants.h"
18#include "llvm/IR/Function.h"
20#include "llvm/IR/Intrinsics.h"
21#include "llvm/IR/LLVMContext.h"
22#include "llvm/IR/MDBuilder.h"
26
27#include <cmath>
28
29using namespace llvm;
30
31#define DEBUG_TYPE "lower-expect-intrinsic"
32
33STATISTIC(ExpectIntrinsicsHandled,
34 "Number of 'expect' intrinsic instructions handled");
35
36// These default values are chosen to represent an extremely skewed outcome for
37// a condition, but they leave some room for interpretation by later passes.
38//
39// If the documentation for __builtin_expect() was made explicit that it should
40// only be used in extreme cases, we could make this ratio higher. As it stands,
41// programmers may be using __builtin_expect() / llvm.expect to annotate that a
42// branch is likely or unlikely to be taken.
43
44// WARNING: these values are internal implementation detail of the pass.
45// They should not be exposed to the outside of the pass, front-end codegen
46// should emit @llvm.expect intrinsics instead of using these weights directly.
47// Transforms should use TargetTransformInfo's getPredictableBranchThreshold().
49 "likely-branch-weight", cl::Hidden, cl::init(2000),
50 cl::desc("Weight of the branch likely to be taken (default = 2000)"));
52 "unlikely-branch-weight", cl::Hidden, cl::init(1),
53 cl::desc("Weight of the branch unlikely to be taken (default = 1)"));
54
55static std::tuple<uint32_t, uint32_t>
56getBranchWeight(Intrinsic::ID IntrinsicID, CallInst *CI, int BranchCount) {
57 if (IntrinsicID == Intrinsic::expect) {
58 // __builtin_expect
59 return std::make_tuple(LikelyBranchWeight.getValue(),
60 UnlikelyBranchWeight.getValue());
61 } else {
62 // __builtin_expect_with_probability
63 assert(CI->getNumOperands() >= 3 &&
64 "expect with probability must have 3 arguments");
65 auto *Confidence = cast<ConstantFP>(CI->getArgOperand(2));
66 double TrueProb = Confidence->getValueAPF().convertToDouble();
67 assert((TrueProb >= 0.0 && TrueProb <= 1.0) &&
68 "probability value must be in the range [0.0, 1.0]");
69 double FalseProb = (1.0 - TrueProb) / (BranchCount - 1);
70 uint32_t LikelyBW = ceil((TrueProb * (double)(INT32_MAX - 1)) + 1.0);
71 uint32_t UnlikelyBW = ceil((FalseProb * (double)(INT32_MAX - 1)) + 1.0);
72 return std::make_tuple(LikelyBW, UnlikelyBW);
73 }
74}
75
77 CallInst *CI = dyn_cast<CallInst>(SI.getCondition());
78 if (!CI)
79 return false;
80
81 Function *Fn = CI->getCalledFunction();
82 if (!Fn || (Fn->getIntrinsicID() != Intrinsic::expect &&
83 Fn->getIntrinsicID() != Intrinsic::expect_with_probability))
84 return false;
85
86 Value *ArgValue = CI->getArgOperand(0);
87 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
88 if (!ExpectedValue)
89 return false;
90
91 SwitchInst::CaseHandle Case = *SI.findCaseValue(ExpectedValue);
92 unsigned n = SI.getNumCases(); // +1 for default case.
93 uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;
94 std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =
95 getBranchWeight(Fn->getIntrinsicID(), CI, n + 1);
96
97 SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeightVal);
98
99 uint64_t Index = (Case == *SI.case_default()) ? 0 : Case.getCaseIndex() + 1;
100 Weights[Index] = LikelyBranchWeightVal;
101
102 misexpect::checkExpectAnnotations(SI, Weights, /*IsFrontend=*/true);
103
104 SI.setCondition(ArgValue);
105 setBranchWeights(SI, Weights);
106 return true;
107}
108
109/// Handler for PHINodes that define the value argument to an
110/// @llvm.expect call.
111///
112/// If the operand of the phi has a constant value and it 'contradicts'
113/// with the expected value of phi def, then the corresponding incoming
114/// edge of the phi is unlikely to be taken. Using that information,
115/// the branch probability info for the originating branch can be inferred.
116static void handlePhiDef(CallInst *Expect) {
117 Value &Arg = *Expect->getArgOperand(0);
118 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(Expect->getArgOperand(1));
119 if (!ExpectedValue)
120 return;
121 const APInt &ExpectedPhiValue = ExpectedValue->getValue();
122 bool ExpectedValueIsLikely = true;
123 Function *Fn = Expect->getCalledFunction();
124 // If the function is expect_with_probability, then we need to take the
125 // probability into consideration. For example, in
126 // expect.with.probability.i64(i64 %a, i64 1, double 0.0), the
127 // "ExpectedValue" 1 is unlikely. This affects probability propagation later.
128 if (Fn->getIntrinsicID() == Intrinsic::expect_with_probability) {
129 auto *Confidence = cast<ConstantFP>(Expect->getArgOperand(2));
130 double TrueProb = Confidence->getValueAPF().convertToDouble();
131 ExpectedValueIsLikely = (TrueProb > 0.5);
132 }
133
134 // Walk up in backward a list of instructions that
135 // have 'copy' semantics by 'stripping' the copies
136 // until a PHI node or an instruction of unknown kind
137 // is reached. Negation via xor is also handled.
138 //
139 // C = PHI(...);
140 // B = C;
141 // A = B;
142 // D = __builtin_expect(A, 0);
143 //
144 Value *V = &Arg;
146 while (!isa<PHINode>(V)) {
147 if (ZExtInst *ZExt = dyn_cast<ZExtInst>(V)) {
148 V = ZExt->getOperand(0);
149 Operations.push_back(ZExt);
150 continue;
151 }
152
153 if (SExtInst *SExt = dyn_cast<SExtInst>(V)) {
154 V = SExt->getOperand(0);
155 Operations.push_back(SExt);
156 continue;
157 }
158
159 BinaryOperator *BinOp = dyn_cast<BinaryOperator>(V);
160 if (!BinOp || BinOp->getOpcode() != Instruction::Xor)
161 return;
162
163 ConstantInt *CInt = dyn_cast<ConstantInt>(BinOp->getOperand(1));
164 if (!CInt)
165 return;
166
167 V = BinOp->getOperand(0);
168 Operations.push_back(BinOp);
169 }
170
171 // Executes the recorded operations on input 'Value'.
172 auto ApplyOperations = [&](const APInt &Value) {
173 APInt Result = Value;
174 for (auto *Op : llvm::reverse(Operations)) {
175 switch (Op->getOpcode()) {
176 case Instruction::Xor:
177 Result ^= cast<ConstantInt>(Op->getOperand(1))->getValue();
178 break;
179 case Instruction::ZExt:
180 Result = Result.zext(Op->getType()->getIntegerBitWidth());
181 break;
182 case Instruction::SExt:
183 Result = Result.sext(Op->getType()->getIntegerBitWidth());
184 break;
185 default:
186 llvm_unreachable("Unexpected operation");
187 }
188 }
189 return Result;
190 };
191
192 auto *PhiDef = cast<PHINode>(V);
193
194 // Get the first dominating conditional branch of the operand
195 // i's incoming block.
196 auto GetDomConditional = [&](unsigned i) -> BranchInst * {
197 BasicBlock *BB = PhiDef->getIncomingBlock(i);
198 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
199 if (BI && BI->isConditional())
200 return BI;
201 BB = BB->getSinglePredecessor();
202 if (!BB)
203 return nullptr;
204 BI = dyn_cast<BranchInst>(BB->getTerminator());
205 if (!BI || BI->isUnconditional())
206 return nullptr;
207 return BI;
208 };
209
210 // Now walk through all Phi operands to find phi oprerands with values
211 // conflicting with the expected phi output value. Any such operand
212 // indicates the incoming edge to that operand is unlikely.
213 for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) {
214
215 Value *PhiOpnd = PhiDef->getIncomingValue(i);
216 ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd);
217 if (!CI)
218 continue;
219
220 // Not an interesting case when IsUnlikely is false -- we can not infer
221 // anything useful when:
222 // (1) We expect some phi output and the operand value matches it, or
223 // (2) We don't expect some phi output (i.e. the "ExpectedValue" has low
224 // probability) and the operand value doesn't match that.
225 const APInt &CurrentPhiValue = ApplyOperations(CI->getValue());
226 if (ExpectedValueIsLikely == (ExpectedPhiValue == CurrentPhiValue))
227 continue;
228
229 BranchInst *BI = GetDomConditional(i);
230 if (!BI)
231 continue;
232
233 MDBuilder MDB(PhiDef->getContext());
234
235 // There are two situations in which an operand of the PhiDef comes
236 // from a given successor of a branch instruction BI.
237 // 1) When the incoming block of the operand is the successor block;
238 // 2) When the incoming block is BI's enclosing block and the
239 // successor is the PhiDef's enclosing block.
240 //
241 // Returns true if the operand which comes from OpndIncomingBB
242 // comes from outgoing edge of BI that leads to Succ block.
243 auto *OpndIncomingBB = PhiDef->getIncomingBlock(i);
244 auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) {
245 if (OpndIncomingBB == Succ)
246 // If this successor is the incoming block for this
247 // Phi operand, then this successor does lead to the Phi.
248 return true;
249 if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent())
250 // Otherwise, if the edge is directly from the branch
251 // to the Phi, this successor is the one feeding this
252 // Phi operand.
253 return true;
254 return false;
255 };
256 uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;
257 std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) = getBranchWeight(
258 Expect->getCalledFunction()->getIntrinsicID(), Expect, 2);
259 if (!ExpectedValueIsLikely)
260 std::swap(LikelyBranchWeightVal, UnlikelyBranchWeightVal);
261
262 if (IsOpndComingFromSuccessor(BI->getSuccessor(1)))
263 BI->setMetadata(LLVMContext::MD_prof,
264 MDB.createBranchWeights(LikelyBranchWeightVal,
265 UnlikelyBranchWeightVal));
266 else if (IsOpndComingFromSuccessor(BI->getSuccessor(0)))
267 BI->setMetadata(LLVMContext::MD_prof,
268 MDB.createBranchWeights(UnlikelyBranchWeightVal,
269 LikelyBranchWeightVal));
270 }
271}
272
273// Handle both BranchInst and SelectInst.
274template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
275
276 // Handle non-optimized IR code like:
277 // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1)
278 // %tobool = icmp ne i64 %expval, 0
279 // br i1 %tobool, label %if.then, label %if.end
280 //
281 // Or the following simpler case:
282 // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1)
283 // br i1 %expval, label %if.then, label %if.end
284
285 CallInst *CI;
286
287 ICmpInst *CmpI = dyn_cast<ICmpInst>(BSI.getCondition());
288 CmpInst::Predicate Predicate;
289 ConstantInt *CmpConstOperand = nullptr;
290 if (!CmpI) {
291 CI = dyn_cast<CallInst>(BSI.getCondition());
292 Predicate = CmpInst::ICMP_NE;
293 } else {
294 Predicate = CmpI->getPredicate();
295 if (Predicate != CmpInst::ICMP_NE && Predicate != CmpInst::ICMP_EQ)
296 return false;
297
298 CmpConstOperand = dyn_cast<ConstantInt>(CmpI->getOperand(1));
299 if (!CmpConstOperand)
300 return false;
301 CI = dyn_cast<CallInst>(CmpI->getOperand(0));
302 }
303
304 if (!CI)
305 return false;
306
307 uint64_t ValueComparedTo = 0;
308 if (CmpConstOperand) {
309 if (CmpConstOperand->getBitWidth() > 64)
310 return false;
311 ValueComparedTo = CmpConstOperand->getZExtValue();
312 }
313
314 Function *Fn = CI->getCalledFunction();
315 if (!Fn || (Fn->getIntrinsicID() != Intrinsic::expect &&
316 Fn->getIntrinsicID() != Intrinsic::expect_with_probability))
317 return false;
318
319 Value *ArgValue = CI->getArgOperand(0);
320 ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
321 if (!ExpectedValue)
322 return false;
323
324 MDBuilder MDB(CI->getContext());
325 MDNode *Node;
326
327 uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;
328 std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =
329 getBranchWeight(Fn->getIntrinsicID(), CI, 2);
330
331 SmallVector<uint32_t, 4> ExpectedWeights;
332 if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==
333 (Predicate == CmpInst::ICMP_EQ)) {
334 Node =
335 MDB.createBranchWeights(LikelyBranchWeightVal, UnlikelyBranchWeightVal);
336 ExpectedWeights = {LikelyBranchWeightVal, UnlikelyBranchWeightVal};
337 } else {
338 Node =
339 MDB.createBranchWeights(UnlikelyBranchWeightVal, LikelyBranchWeightVal);
340 ExpectedWeights = {UnlikelyBranchWeightVal, LikelyBranchWeightVal};
341 }
342
343 if (CmpI)
344 CmpI->setOperand(0, ArgValue);
345 else
346 BSI.setCondition(ArgValue);
347
348 misexpect::checkFrontendInstrumentation(BSI, ExpectedWeights);
349
350 BSI.setMetadata(LLVMContext::MD_prof, Node);
351
352 return true;
353}
354
356 if (BI.isUnconditional())
357 return false;
358
359 return handleBrSelExpect<BranchInst>(BI);
360}
361
363 bool Changed = false;
364
365 for (BasicBlock &BB : F) {
366 // Create "block_weights" metadata.
367 if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
368 if (handleBranchExpect(*BI))
369 ExpectIntrinsicsHandled++;
370 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
371 if (handleSwitchExpect(*SI))
372 ExpectIntrinsicsHandled++;
373 }
374
375 // Remove llvm.expect intrinsics. Iterate backwards in order
376 // to process select instructions before the intrinsic gets
377 // removed.
379 CallInst *CI = dyn_cast<CallInst>(&Inst);
380 if (!CI) {
381 if (SelectInst *SI = dyn_cast<SelectInst>(&Inst)) {
382 if (handleBrSelExpect(*SI))
383 ExpectIntrinsicsHandled++;
384 }
385 continue;
386 }
387
388 Function *Fn = CI->getCalledFunction();
389 if (Fn && (Fn->getIntrinsicID() == Intrinsic::expect ||
390 Fn->getIntrinsicID() == Intrinsic::expect_with_probability)) {
391 // Before erasing the llvm.expect, walk backward to find
392 // phi that define llvm.expect's first arg, and
393 // infer branch probability:
394 handlePhiDef(CI);
395 Value *Exp = CI->getArgOperand(0);
396 CI->replaceAllUsesWith(Exp);
397 CI->eraseFromParent();
398 Changed = true;
399 }
400 }
401 }
402
403 return Changed;
404}
405
410
411 return PreservedAnalyses::all();
412}
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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 bool handleBranchExpect(BranchInst &BI)
static std::tuple< uint32_t, uint32_t > getBranchWeight(Intrinsic::ID IntrinsicID, CallInst *CI, int BranchCount)
static bool handleBrSelExpect(BrSelInst &BSI)
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)"))
static bool handleSwitchExpect(SwitchInst &SI)
static bool lowerExpectIntrinsic(Function &F)
static void handlePhiDef(CallInst *Expect)
Handler for PHINodes that define the value argument to an @llvm.expect call.
The header file for the LowerExpectIntrinsic pass as used by the new pass manager.
#define F(x, y, z)
Definition: MD5.cpp:55
This file contains the declarations for profiling metadata utility functions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Class for arbitrary precision integers.
Definition: APInt.h:76
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:452
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:221
BinaryOps getOpcode() const
Definition: InstrTypes.h:486
Conditional or Unconditional Branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1715
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1660
This class represents a function call, abstracting a target machine's calling convention.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:966
@ ICMP_EQ
equal
Definition: InstrTypes.h:987
@ ICMP_NE
not equal
Definition: InstrTypes.h:988
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:1078
This is the shared class of boolean and integer constants.
Definition: Constants.h:80
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
Definition: Constants.h:148
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:154
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:145
This class represents an Operation in the Expression.
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:231
This instruction compares its operands according to the predicate given to the constructor.
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1636
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
Metadata node.
Definition: Metadata.h:1067
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
This class represents a sign extension of integer types.
This class represents the LLVM 'select' instruction.
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
unsigned getCaseIndex() const
Returns number of current case.
Multiway switch.
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
LLVM Value Representation.
Definition: Value.h:74
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
This class represents zero extension of integer types.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
void checkFrontendInstrumentation(Instruction &I, const ArrayRef< uint32_t > ExpectedWeights)
checkFrontendInstrumentation - compares PGO counters to the thresholds used for llvm....
Definition: MisExpect.cpp:194
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
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:656
void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Run the pass over the function.