LLVM  9.0.0svn
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/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 
58  if (!CI)
59  return false;
60 
61  Function *Fn = CI->getCalledFunction();
62  if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect)
63  return false;
64 
65  Value *ArgValue = CI->getArgOperand(0);
66  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
67  if (!ExpectedValue)
68  return false;
69 
70  SwitchInst::CaseHandle Case = *SI.findCaseValue(ExpectedValue);
71  unsigned n = SI.getNumCases(); // +1 for default case.
73 
74  if (Case == *SI.case_default())
75  Weights[0] = LikelyBranchWeight;
76  else
77  Weights[Case.getCaseIndex() + 1] = LikelyBranchWeight;
78 
80  MDBuilder(CI->getContext()).createBranchWeights(Weights));
81 
82  SI.setCondition(ArgValue);
83  return true;
84 }
85 
86 /// Handler for PHINodes that define the value argument to an
87 /// @llvm.expect call.
88 ///
89 /// If the operand of the phi has a constant value and it 'contradicts'
90 /// with the expected value of phi def, then the corresponding incoming
91 /// edge of the phi is unlikely to be taken. Using that information,
92 /// the branch probability info for the originating branch can be inferred.
93 static void handlePhiDef(CallInst *Expect) {
94  Value &Arg = *Expect->getArgOperand(0);
95  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(Expect->getArgOperand(1));
96  if (!ExpectedValue)
97  return;
98  const APInt &ExpectedPhiValue = ExpectedValue->getValue();
99 
100  // Walk up in backward a list of instructions that
101  // have 'copy' semantics by 'stripping' the copies
102  // until a PHI node or an instruction of unknown kind
103  // is reached. Negation via xor is also handled.
104  //
105  // C = PHI(...);
106  // B = C;
107  // A = B;
108  // D = __builtin_expect(A, 0);
109  //
110  Value *V = &Arg;
112  while (!isa<PHINode>(V)) {
113  if (ZExtInst *ZExt = dyn_cast<ZExtInst>(V)) {
114  V = ZExt->getOperand(0);
115  Operations.push_back(ZExt);
116  continue;
117  }
118 
119  if (SExtInst *SExt = dyn_cast<SExtInst>(V)) {
120  V = SExt->getOperand(0);
121  Operations.push_back(SExt);
122  continue;
123  }
124 
126  if (!BinOp || BinOp->getOpcode() != Instruction::Xor)
127  return;
128 
129  ConstantInt *CInt = dyn_cast<ConstantInt>(BinOp->getOperand(1));
130  if (!CInt)
131  return;
132 
133  V = BinOp->getOperand(0);
134  Operations.push_back(BinOp);
135  }
136 
137  // Executes the recorded operations on input 'Value'.
138  auto ApplyOperations = [&](const APInt &Value) {
139  APInt Result = Value;
140  for (auto Op : llvm::reverse(Operations)) {
141  switch (Op->getOpcode()) {
142  case Instruction::Xor:
143  Result ^= cast<ConstantInt>(Op->getOperand(1))->getValue();
144  break;
145  case Instruction::ZExt:
146  Result = Result.zext(Op->getType()->getIntegerBitWidth());
147  break;
148  case Instruction::SExt:
149  Result = Result.sext(Op->getType()->getIntegerBitWidth());
150  break;
151  default:
152  llvm_unreachable("Unexpected operation");
153  }
154  }
155  return Result;
156  };
157 
158  auto *PhiDef = dyn_cast<PHINode>(V);
159 
160  // Get the first dominating conditional branch of the operand
161  // i's incoming block.
162  auto GetDomConditional = [&](unsigned i) -> BranchInst * {
163  BasicBlock *BB = PhiDef->getIncomingBlock(i);
165  if (BI && BI->isConditional())
166  return BI;
167  BB = BB->getSinglePredecessor();
168  if (!BB)
169  return nullptr;
170  BI = dyn_cast<BranchInst>(BB->getTerminator());
171  if (!BI || BI->isUnconditional())
172  return nullptr;
173  return BI;
174  };
175 
176  // Now walk through all Phi operands to find phi oprerands with values
177  // conflicting with the expected phi output value. Any such operand
178  // indicates the incoming edge to that operand is unlikely.
179  for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) {
180 
181  Value *PhiOpnd = PhiDef->getIncomingValue(i);
182  ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd);
183  if (!CI)
184  continue;
185 
186  // Not an interesting case when IsUnlikely is false -- we can not infer
187  // anything useful when the operand value matches the expected phi
188  // output.
189  if (ExpectedPhiValue == ApplyOperations(CI->getValue()))
190  continue;
191 
192  BranchInst *BI = GetDomConditional(i);
193  if (!BI)
194  continue;
195 
196  MDBuilder MDB(PhiDef->getContext());
197 
198  // There are two situations in which an operand of the PhiDef comes
199  // from a given successor of a branch instruction BI.
200  // 1) When the incoming block of the operand is the successor block;
201  // 2) When the incoming block is BI's enclosing block and the
202  // successor is the PhiDef's enclosing block.
203  //
204  // Returns true if the operand which comes from OpndIncomingBB
205  // comes from outgoing edge of BI that leads to Succ block.
206  auto *OpndIncomingBB = PhiDef->getIncomingBlock(i);
207  auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) {
208  if (OpndIncomingBB == Succ)
209  // If this successor is the incoming block for this
210  // Phi operand, then this successor does lead to the Phi.
211  return true;
212  if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent())
213  // Otherwise, if the edge is directly from the branch
214  // to the Phi, this successor is the one feeding this
215  // Phi operand.
216  return true;
217  return false;
218  };
219 
220  if (IsOpndComingFromSuccessor(BI->getSuccessor(1)))
221  BI->setMetadata(
223  MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight));
224  else if (IsOpndComingFromSuccessor(BI->getSuccessor(0)))
225  BI->setMetadata(
227  MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight));
228  }
229 }
230 
231 // Handle both BranchInst and SelectInst.
232 template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
233 
234  // Handle non-optimized IR code like:
235  // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1)
236  // %tobool = icmp ne i64 %expval, 0
237  // br i1 %tobool, label %if.then, label %if.end
238  //
239  // Or the following simpler case:
240  // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1)
241  // br i1 %expval, label %if.then, label %if.end
242 
243  CallInst *CI;
244 
245  ICmpInst *CmpI = dyn_cast<ICmpInst>(BSI.getCondition());
247  ConstantInt *CmpConstOperand = nullptr;
248  if (!CmpI) {
249  CI = dyn_cast<CallInst>(BSI.getCondition());
250  Predicate = CmpInst::ICMP_NE;
251  } else {
252  Predicate = CmpI->getPredicate();
253  if (Predicate != CmpInst::ICMP_NE && Predicate != CmpInst::ICMP_EQ)
254  return false;
255 
256  CmpConstOperand = dyn_cast<ConstantInt>(CmpI->getOperand(1));
257  if (!CmpConstOperand)
258  return false;
259  CI = dyn_cast<CallInst>(CmpI->getOperand(0));
260  }
261 
262  if (!CI)
263  return false;
264 
265  uint64_t ValueComparedTo = 0;
266  if (CmpConstOperand) {
267  if (CmpConstOperand->getBitWidth() > 64)
268  return false;
269  ValueComparedTo = CmpConstOperand->getZExtValue();
270  }
271 
272  Function *Fn = CI->getCalledFunction();
273  if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect)
274  return false;
275 
276  Value *ArgValue = CI->getArgOperand(0);
277  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
278  if (!ExpectedValue)
279  return false;
280 
281  MDBuilder MDB(CI->getContext());
282  MDNode *Node;
283 
284  if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==
285  (Predicate == CmpInst::ICMP_EQ))
286  Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight);
287  else
288  Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight);
289 
290  BSI.setMetadata(LLVMContext::MD_prof, Node);
291 
292  if (CmpI)
293  CmpI->setOperand(0, ArgValue);
294  else
295  BSI.setCondition(ArgValue);
296  return true;
297 }
298 
299 static bool handleBranchExpect(BranchInst &BI) {
300  if (BI.isUnconditional())
301  return false;
302 
303  return handleBrSelExpect<BranchInst>(BI);
304 }
305 
307  bool Changed = false;
308 
309  for (BasicBlock &BB : F) {
310  // Create "block_weights" metadata.
311  if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
312  if (handleBranchExpect(*BI))
313  ExpectIntrinsicsHandled++;
314  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
315  if (handleSwitchExpect(*SI))
316  ExpectIntrinsicsHandled++;
317  }
318 
319  // Remove llvm.expect intrinsics. Iterate backwards in order
320  // to process select instructions before the intrinsic gets
321  // removed.
322  for (auto BI = BB.rbegin(), BE = BB.rend(); BI != BE;) {
323  Instruction *Inst = &*BI++;
324  CallInst *CI = dyn_cast<CallInst>(Inst);
325  if (!CI) {
326  if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
327  if (handleBrSelExpect(*SI))
328  ExpectIntrinsicsHandled++;
329  }
330  continue;
331  }
332 
333  Function *Fn = CI->getCalledFunction();
334  if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) {
335  // Before erasing the llvm.expect, walk backward to find
336  // phi that define llvm.expect's first arg, and
337  // infer branch probability:
338  handlePhiDef(CI);
339  Value *Exp = CI->getArgOperand(0);
340  CI->replaceAllUsesWith(Exp);
341  CI->eraseFromParent();
342  Changed = true;
343  }
344  }
345  }
346 
347  return Changed;
348 }
349 
352  if (lowerExpectIntrinsic(F))
353  return PreservedAnalyses::none();
354 
355  return PreservedAnalyses::all();
356 }
357 
358 namespace {
359 /// Legacy pass for lowering expect intrinsics out of the IR.
360 ///
361 /// When this pass is run over a function it uses expect intrinsics which feed
362 /// branches and switches to provide branch weight metadata for those
363 /// terminators. It then removes the expect intrinsics from the IR so the rest
364 /// of the optimizer can ignore them.
365 class LowerExpectIntrinsic : public FunctionPass {
366 public:
367  static char ID;
368  LowerExpectIntrinsic() : FunctionPass(ID) {
370  }
371 
372  bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); }
373 };
374 }
375 
376 char LowerExpectIntrinsic::ID = 0;
377 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect",
378  "Lower 'expect' Intrinsics", false, false)
379 
381  return new LowerExpectIntrinsic();
382 }
unsigned getNumCases() const
Return the number of &#39;cases&#39; in this switch instruction, excluding the default case.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:833
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:316
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...
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:857
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
Value * getCondition() const
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:705
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:863
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:137
unsigned getBitWidth() const
getBitWidth - Return the bitwidth of this constant.
Definition: Constants.h:142
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1155
This class represents the LLVM &#39;select&#39; instruction.
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:266
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:137
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
Value * getOperand(unsigned i) const
Definition: User.h:169
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
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 runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
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:148
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
void initializeLowerExpectIntrinsicPass(PassRegistry &)
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Conditional or Unconditional Branch instruction.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:646
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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 PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
#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:1225
static bool handleBrSelExpect(BrSelInst &BSI)
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", "Lower 'expect' Intrinsics", false, false) FunctionPass *llvm
bool isConditional() const
CaseIt findCaseValue(const ConstantInt *C)
Search all of the case values for the specified constant.
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:193
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Class for arbitrary precision integers.
Definition: APInt.h:69
static void handlePhiDef(CallInst *Expect)
Handler for PHINodes that define the value argument to an .expect call.
static bool handleBranchExpect(BranchInst &BI)
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:721
void setCondition(Value *V)
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1201
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
The header file for the LowerExpectIntrinsic pass as used by the new pass manager.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:322
CaseIt case_default()
Returns an iterator that points to the default case.
bool isUnconditional() const
Multiway switch.
LLVM Value Representation.
Definition: Value.h:72
A container for analyses that lazily runs them and caches their results.
static bool handleSwitchExpect(SwitchInst &SI)
FunctionPass * createLowerExpectIntrinsicPass()
const BasicBlock * getParent() const
Definition: Instruction.h:66