LLVM  12.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 
14 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/ADT/Statistic.h"
17 #include "llvm/IR/BasicBlock.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/Intrinsics.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/MDBuilder.h"
24 #include "llvm/IR/Metadata.h"
25 #include "llvm/InitializePasses.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Transforms/Scalar.h"
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "lower-expect-intrinsic"
33 
34 STATISTIC(ExpectIntrinsicsHandled,
35  "Number of 'expect' intrinsic instructions handled");
36 
37 // These default values are chosen to represent an extremely skewed outcome for
38 // a condition, but they leave some room for interpretation by later passes.
39 //
40 // If the documentation for __builtin_expect() was made explicit that it should
41 // only be used in extreme cases, we could make this ratio higher. As it stands,
42 // programmers may be using __builtin_expect() / llvm.expect to annotate that a
43 // branch is likely or unlikely to be taken.
44 //
45 // There is a known dependency on this ratio in CodeGenPrepare when transforming
46 // 'select' instructions. It may be worthwhile to hoist these values to some
47 // shared space, so they can be used directly by other passes.
48 
50  "likely-branch-weight", cl::Hidden, cl::init(2000),
51  cl::desc("Weight of the branch likely to be taken (default = 2000)"));
53  "unlikely-branch-weight", cl::Hidden, cl::init(1),
54  cl::desc("Weight of the branch unlikely to be taken (default = 1)"));
55 
56 static std::tuple<uint32_t, uint32_t>
57 getBranchWeight(Intrinsic::ID IntrinsicID, CallInst *CI, int BranchCount) {
58  if (IntrinsicID == Intrinsic::expect) {
59  // __builtin_expect
60  return std::make_tuple(LikelyBranchWeight.getValue(),
61  UnlikelyBranchWeight.getValue());
62  } else {
63  // __builtin_expect_with_probability
64  assert(CI->getNumOperands() >= 3 &&
65  "expect with probability must have 3 arguments");
66  ConstantFP *Confidence = dyn_cast<ConstantFP>(CI->getArgOperand(2));
67  double TrueProb = Confidence->getValueAPF().convertToDouble();
68  assert((TrueProb >= 0.0 && TrueProb <= 1.0) &&
69  "probability value must be in the range [0.0, 1.0]");
70  double FalseProb = (1.0 - TrueProb) / (BranchCount - 1);
71  uint32_t LikelyBW = ceil((TrueProb * (double)(INT32_MAX - 1)) + 1.0);
72  uint32_t UnlikelyBW = ceil((FalseProb * (double)(INT32_MAX - 1)) + 1.0);
73  return std::make_tuple(LikelyBW, UnlikelyBW);
74  }
75 }
76 
78  CallInst *CI = dyn_cast<CallInst>(SI.getCondition());
79  if (!CI)
80  return false;
81 
82  Function *Fn = CI->getCalledFunction();
83  if (!Fn || (Fn->getIntrinsicID() != Intrinsic::expect &&
84  Fn->getIntrinsicID() != Intrinsic::expect_with_probability))
85  return false;
86 
87  Value *ArgValue = CI->getArgOperand(0);
88  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
89  if (!ExpectedValue)
90  return false;
91 
92  SwitchInst::CaseHandle Case = *SI.findCaseValue(ExpectedValue);
93  unsigned n = SI.getNumCases(); // +1 for default case.
94  uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;
95  std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =
96  getBranchWeight(Fn->getIntrinsicID(), CI, n + 1);
97 
98  SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeightVal);
99 
100  uint64_t Index = (Case == *SI.case_default()) ? 0 : Case.getCaseIndex() + 1;
101  Weights[Index] = LikelyBranchWeightVal;
102 
103  SI.setCondition(ArgValue);
104 
105  SI.setMetadata(LLVMContext::MD_prof,
106  MDBuilder(CI->getContext()).createBranchWeights(Weights));
107 
108  return true;
109 }
110 
111 /// Handler for PHINodes that define the value argument to an
112 /// @llvm.expect call.
113 ///
114 /// If the operand of the phi has a constant value and it 'contradicts'
115 /// with the expected value of phi def, then the corresponding incoming
116 /// edge of the phi is unlikely to be taken. Using that information,
117 /// the branch probability info for the originating branch can be inferred.
118 static void handlePhiDef(CallInst *Expect) {
119  Value &Arg = *Expect->getArgOperand(0);
120  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(Expect->getArgOperand(1));
121  if (!ExpectedValue)
122  return;
123  const APInt &ExpectedPhiValue = ExpectedValue->getValue();
124 
125  // Walk up in backward a list of instructions that
126  // have 'copy' semantics by 'stripping' the copies
127  // until a PHI node or an instruction of unknown kind
128  // is reached. Negation via xor is also handled.
129  //
130  // C = PHI(...);
131  // B = C;
132  // A = B;
133  // D = __builtin_expect(A, 0);
134  //
135  Value *V = &Arg;
137  while (!isa<PHINode>(V)) {
138  if (ZExtInst *ZExt = dyn_cast<ZExtInst>(V)) {
139  V = ZExt->getOperand(0);
140  Operations.push_back(ZExt);
141  continue;
142  }
143 
144  if (SExtInst *SExt = dyn_cast<SExtInst>(V)) {
145  V = SExt->getOperand(0);
146  Operations.push_back(SExt);
147  continue;
148  }
149 
150  BinaryOperator *BinOp = dyn_cast<BinaryOperator>(V);
151  if (!BinOp || BinOp->getOpcode() != Instruction::Xor)
152  return;
153 
154  ConstantInt *CInt = dyn_cast<ConstantInt>(BinOp->getOperand(1));
155  if (!CInt)
156  return;
157 
158  V = BinOp->getOperand(0);
159  Operations.push_back(BinOp);
160  }
161 
162  // Executes the recorded operations on input 'Value'.
163  auto ApplyOperations = [&](const APInt &Value) {
164  APInt Result = Value;
165  for (auto Op : llvm::reverse(Operations)) {
166  switch (Op->getOpcode()) {
167  case Instruction::Xor:
168  Result ^= cast<ConstantInt>(Op->getOperand(1))->getValue();
169  break;
170  case Instruction::ZExt:
171  Result = Result.zext(Op->getType()->getIntegerBitWidth());
172  break;
173  case Instruction::SExt:
174  Result = Result.sext(Op->getType()->getIntegerBitWidth());
175  break;
176  default:
177  llvm_unreachable("Unexpected operation");
178  }
179  }
180  return Result;
181  };
182 
183  auto *PhiDef = cast<PHINode>(V);
184 
185  // Get the first dominating conditional branch of the operand
186  // i's incoming block.
187  auto GetDomConditional = [&](unsigned i) -> BranchInst * {
188  BasicBlock *BB = PhiDef->getIncomingBlock(i);
189  BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
190  if (BI && BI->isConditional())
191  return BI;
192  BB = BB->getSinglePredecessor();
193  if (!BB)
194  return nullptr;
195  BI = dyn_cast<BranchInst>(BB->getTerminator());
196  if (!BI || BI->isUnconditional())
197  return nullptr;
198  return BI;
199  };
200 
201  // Now walk through all Phi operands to find phi oprerands with values
202  // conflicting with the expected phi output value. Any such operand
203  // indicates the incoming edge to that operand is unlikely.
204  for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) {
205 
206  Value *PhiOpnd = PhiDef->getIncomingValue(i);
207  ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd);
208  if (!CI)
209  continue;
210 
211  // Not an interesting case when IsUnlikely is false -- we can not infer
212  // anything useful when the operand value matches the expected phi
213  // output.
214  if (ExpectedPhiValue == ApplyOperations(CI->getValue()))
215  continue;
216 
217  BranchInst *BI = GetDomConditional(i);
218  if (!BI)
219  continue;
220 
221  MDBuilder MDB(PhiDef->getContext());
222 
223  // There are two situations in which an operand of the PhiDef comes
224  // from a given successor of a branch instruction BI.
225  // 1) When the incoming block of the operand is the successor block;
226  // 2) When the incoming block is BI's enclosing block and the
227  // successor is the PhiDef's enclosing block.
228  //
229  // Returns true if the operand which comes from OpndIncomingBB
230  // comes from outgoing edge of BI that leads to Succ block.
231  auto *OpndIncomingBB = PhiDef->getIncomingBlock(i);
232  auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) {
233  if (OpndIncomingBB == Succ)
234  // If this successor is the incoming block for this
235  // Phi operand, then this successor does lead to the Phi.
236  return true;
237  if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent())
238  // Otherwise, if the edge is directly from the branch
239  // to the Phi, this successor is the one feeding this
240  // Phi operand.
241  return true;
242  return false;
243  };
244  uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;
245  std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) = getBranchWeight(
246  Expect->getCalledFunction()->getIntrinsicID(), Expect, 2);
247 
248  if (IsOpndComingFromSuccessor(BI->getSuccessor(1)))
249  BI->setMetadata(LLVMContext::MD_prof,
250  MDB.createBranchWeights(LikelyBranchWeightVal,
251  UnlikelyBranchWeightVal));
252  else if (IsOpndComingFromSuccessor(BI->getSuccessor(0)))
253  BI->setMetadata(LLVMContext::MD_prof,
254  MDB.createBranchWeights(UnlikelyBranchWeightVal,
255  LikelyBranchWeightVal));
256  }
257 }
258 
259 // Handle both BranchInst and SelectInst.
260 template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
261 
262  // Handle non-optimized IR code like:
263  // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1)
264  // %tobool = icmp ne i64 %expval, 0
265  // br i1 %tobool, label %if.then, label %if.end
266  //
267  // Or the following simpler case:
268  // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1)
269  // br i1 %expval, label %if.then, label %if.end
270 
271  CallInst *CI;
272 
273  ICmpInst *CmpI = dyn_cast<ICmpInst>(BSI.getCondition());
275  ConstantInt *CmpConstOperand = nullptr;
276  if (!CmpI) {
277  CI = dyn_cast<CallInst>(BSI.getCondition());
279  } else {
280  Predicate = CmpI->getPredicate();
282  return false;
283 
284  CmpConstOperand = dyn_cast<ConstantInt>(CmpI->getOperand(1));
285  if (!CmpConstOperand)
286  return false;
287  CI = dyn_cast<CallInst>(CmpI->getOperand(0));
288  }
289 
290  if (!CI)
291  return false;
292 
293  uint64_t ValueComparedTo = 0;
294  if (CmpConstOperand) {
295  if (CmpConstOperand->getBitWidth() > 64)
296  return false;
297  ValueComparedTo = CmpConstOperand->getZExtValue();
298  }
299 
300  Function *Fn = CI->getCalledFunction();
301  if (!Fn || (Fn->getIntrinsicID() != Intrinsic::expect &&
302  Fn->getIntrinsicID() != Intrinsic::expect_with_probability))
303  return false;
304 
305  Value *ArgValue = CI->getArgOperand(0);
306  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
307  if (!ExpectedValue)
308  return false;
309 
310  MDBuilder MDB(CI->getContext());
311  MDNode *Node;
312 
313  uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;
314  std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =
315  getBranchWeight(Fn->getIntrinsicID(), CI, 2);
316 
317  if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==
319  Node =
320  MDB.createBranchWeights(LikelyBranchWeightVal, UnlikelyBranchWeightVal);
321  } else {
322  Node =
323  MDB.createBranchWeights(UnlikelyBranchWeightVal, LikelyBranchWeightVal);
324  }
325 
326  if (CmpI)
327  CmpI->setOperand(0, ArgValue);
328  else
329  BSI.setCondition(ArgValue);
330 
331  BSI.setMetadata(LLVMContext::MD_prof, Node);
332 
333  return true;
334 }
335 
336 static bool handleBranchExpect(BranchInst &BI) {
337  if (BI.isUnconditional())
338  return false;
339 
340  return handleBrSelExpect<BranchInst>(BI);
341 }
342 
344  bool Changed = false;
345 
346  for (BasicBlock &BB : F) {
347  // Create "block_weights" metadata.
348  if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
349  if (handleBranchExpect(*BI))
350  ExpectIntrinsicsHandled++;
351  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
352  if (handleSwitchExpect(*SI))
353  ExpectIntrinsicsHandled++;
354  }
355 
356  // Remove llvm.expect intrinsics. Iterate backwards in order
357  // to process select instructions before the intrinsic gets
358  // removed.
359  for (auto BI = BB.rbegin(), BE = BB.rend(); BI != BE;) {
360  Instruction *Inst = &*BI++;
361  CallInst *CI = dyn_cast<CallInst>(Inst);
362  if (!CI) {
363  if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
364  if (handleBrSelExpect(*SI))
365  ExpectIntrinsicsHandled++;
366  }
367  continue;
368  }
369 
370  Function *Fn = CI->getCalledFunction();
371  if (Fn && (Fn->getIntrinsicID() == Intrinsic::expect ||
372  Fn->getIntrinsicID() == Intrinsic::expect_with_probability)) {
373  // Before erasing the llvm.expect, walk backward to find
374  // phi that define llvm.expect's first arg, and
375  // infer branch probability:
376  handlePhiDef(CI);
377  Value *Exp = CI->getArgOperand(0);
378  CI->replaceAllUsesWith(Exp);
379  CI->eraseFromParent();
380  Changed = true;
381  }
382  }
383  }
384 
385  return Changed;
386 }
387 
390  if (lowerExpectIntrinsic(F))
391  return PreservedAnalyses::none();
392 
393  return PreservedAnalyses::all();
394 }
395 
396 namespace {
397 /// Legacy pass for lowering expect intrinsics out of the IR.
398 ///
399 /// When this pass is run over a function it uses expect intrinsics which feed
400 /// branches and switches to provide branch weight metadata for those
401 /// terminators. It then removes the expect intrinsics from the IR so the rest
402 /// of the optimizer can ignore them.
403 class LowerExpectIntrinsic : public FunctionPass {
404 public:
405  static char ID;
406  LowerExpectIntrinsic() : FunctionPass(ID) {
408  }
409 
410  bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); }
411 };
412 }
413 
414 char LowerExpectIntrinsic::ID = 0;
415 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect",
416  "Lower 'expect' Intrinsics", false, false)
417 
419  return new LowerExpectIntrinsic();
420 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:395
This class represents zero extension of integer types.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This class represents a function call, abstracting a target machine's calling convention.
This file contains the declarations for metadata subclasses.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:868
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:870
F(f)
This class represents a sign extension of integer types.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Run the pass over the function.
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.cpp:148
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
unsigned getBitWidth() const
getBitWidth - Return the bitwidth of this constant.
Definition: Constants.h:138
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1323
This class represents the LLVM 'select' instruction.
static bool lowerExpectIntrinsic(Function &F)
unsigned getCaseIndex() const
Returns number of current case.
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:523
Value * getOperand(unsigned i) const
Definition: User.h:169
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
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:144
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
void initializeLowerExpectIntrinsicPass(PassRegistry &)
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
cl::opt< uint32_t > LikelyBranchWeight
Conditional or Unconditional Branch instruction.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:273
double convertToDouble() const
Definition: APFloat.h:1136
This instruction compares its operands according to the predicate given to the constructor.
constexpr double e
Definition: MathExtras.h:58
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1317
const APFloat & getValueAPF() const
Definition: Constants.h:312
unsigned getNumOperands() const
Definition: User.h:191
static bool handleBrSelExpect(BrSelInst &BSI)
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
cl::opt< uint32_t > UnlikelyBranchWeight
INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", "Lower 'expect' Intrinsics", false, false) FunctionPass *llvm
uint32_t Index
bool isConditional() const
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:195
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Class for arbitrary precision integers.
Definition: APInt.h:70
static void handlePhiDef(CallInst *Expect)
Handler for PHINodes that define the value argument to an @llvm.expect call.
static bool handleBranchExpect(BranchInst &BI)
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:799
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1378
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
The header file for the LowerExpectIntrinsic pass as used by the new pass manager.
bool isUnconditional() const
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:75
A container for analyses that lazily runs them and caches their results.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:338
static bool handleSwitchExpect(SwitchInst &SI)
Bitwise or logical XOR of integers.
static std::tuple< uint32_t, uint32_t > getBranchWeight(Intrinsic::ID IntrinsicID, CallInst *CI, int BranchCount)
FunctionPass * createLowerExpectIntrinsicPass()
const BasicBlock * getParent() const
Definition: Instruction.h:94