LLVM  6.0.0svn
LowerExpectIntrinsic.cpp
Go to the documentation of this file.
1 //===- LowerExpectIntrinsic.cpp - Lower expect intrinsic ------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass lowers the 'expect' intrinsic to LLVM metadata.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/Statistic.h"
18 #include "llvm/IR/BasicBlock.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/Intrinsics.h"
23 #include "llvm/IR/LLVMContext.h"
24 #include "llvm/IR/MDBuilder.h"
25 #include "llvm/IR/Metadata.h"
26 #include "llvm/Pass.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Transforms/Scalar.h"
30 
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "lower-expect-intrinsic"
34 
35 STATISTIC(ExpectIntrinsicsHandled,
36  "Number of 'expect' intrinsic instructions handled");
37 
38 // These default values are chosen to represent an extremely skewed outcome for
39 // a condition, but they leave some room for interpretation by later passes.
40 //
41 // If the documentation for __builtin_expect() was made explicit that it should
42 // only be used in extreme cases, we could make this ratio higher. As it stands,
43 // programmers may be using __builtin_expect() / llvm.expect to annotate that a
44 // branch is likely or unlikely to be taken.
45 //
46 // There is a known dependency on this ratio in CodeGenPrepare when transforming
47 // 'select' instructions. It may be worthwhile to hoist these values to some
48 // shared space, so they can be used directly by other passes.
49 
51  "likely-branch-weight", cl::Hidden, cl::init(2000),
52  cl::desc("Weight of the branch likely to be taken (default = 2000)"));
54  "unlikely-branch-weight", cl::Hidden, cl::init(1),
55  cl::desc("Weight of the branch unlikely to be taken (default = 1)"));
56 
59  if (!CI)
60  return false;
61 
62  Function *Fn = CI->getCalledFunction();
63  if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect)
64  return false;
65 
66  Value *ArgValue = CI->getArgOperand(0);
67  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
68  if (!ExpectedValue)
69  return false;
70 
71  SwitchInst::CaseHandle Case = *SI.findCaseValue(ExpectedValue);
72  unsigned n = SI.getNumCases(); // +1 for default case.
74 
75  if (Case == *SI.case_default())
76  Weights[0] = LikelyBranchWeight;
77  else
78  Weights[Case.getCaseIndex() + 1] = LikelyBranchWeight;
79 
81  MDBuilder(CI->getContext()).createBranchWeights(Weights));
82 
83  SI.setCondition(ArgValue);
84  return true;
85 }
86 
87 /// Handler for PHINodes that define the value argument to an
88 /// @llvm.expect call.
89 ///
90 /// If the operand of the phi has a constant value and it 'contradicts'
91 /// with the expected value of phi def, then the corresponding incoming
92 /// edge of the phi is unlikely to be taken. Using that information,
93 /// the branch probability info for the originating branch can be inferred.
94 static void handlePhiDef(CallInst *Expect) {
95  Value &Arg = *Expect->getArgOperand(0);
96  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(Expect->getArgOperand(1));
97  if (!ExpectedValue)
98  return;
99  const APInt &ExpectedPhiValue = ExpectedValue->getValue();
100 
101  // Walk up in backward a list of instructions that
102  // have 'copy' semantics by 'stripping' the copies
103  // until a PHI node or an instruction of unknown kind
104  // is reached. Negation via xor is also handled.
105  //
106  // C = PHI(...);
107  // B = C;
108  // A = B;
109  // D = __builtin_expect(A, 0);
110  //
111  Value *V = &Arg;
113  while (!isa<PHINode>(V)) {
114  if (ZExtInst *ZExt = dyn_cast<ZExtInst>(V)) {
115  V = ZExt->getOperand(0);
116  Operations.push_back(ZExt);
117  continue;
118  }
119 
120  if (SExtInst *SExt = dyn_cast<SExtInst>(V)) {
121  V = SExt->getOperand(0);
122  Operations.push_back(SExt);
123  continue;
124  }
125 
127  if (!BinOp || BinOp->getOpcode() != Instruction::Xor)
128  return;
129 
130  ConstantInt *CInt = dyn_cast<ConstantInt>(BinOp->getOperand(1));
131  if (!CInt)
132  return;
133 
134  V = BinOp->getOperand(0);
135  Operations.push_back(BinOp);
136  }
137 
138  // Executes the recorded operations on input 'Value'.
139  auto ApplyOperations = [&](const APInt &Value) {
140  APInt Result = Value;
141  for (auto Op : llvm::reverse(Operations)) {
142  switch (Op->getOpcode()) {
143  case Instruction::Xor:
144  Result ^= cast<ConstantInt>(Op->getOperand(1))->getValue();
145  break;
146  case Instruction::ZExt:
147  Result = Result.zext(Op->getType()->getIntegerBitWidth());
148  break;
149  case Instruction::SExt:
150  Result = Result.sext(Op->getType()->getIntegerBitWidth());
151  break;
152  default:
153  llvm_unreachable("Unexpected operation");
154  }
155  }
156  return Result;
157  };
158 
159  auto *PhiDef = dyn_cast<PHINode>(V);
160 
161  // Get the first dominating conditional branch of the operand
162  // i's incoming block.
163  auto GetDomConditional = [&](unsigned i) -> BranchInst * {
164  BasicBlock *BB = PhiDef->getIncomingBlock(i);
166  if (BI && BI->isConditional())
167  return BI;
168  BB = BB->getSinglePredecessor();
169  if (!BB)
170  return nullptr;
171  BI = dyn_cast<BranchInst>(BB->getTerminator());
172  if (!BI || BI->isUnconditional())
173  return nullptr;
174  return BI;
175  };
176 
177  // Now walk through all Phi operands to find phi oprerands with values
178  // conflicting with the expected phi output value. Any such operand
179  // indicates the incoming edge to that operand is unlikely.
180  for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) {
181 
182  Value *PhiOpnd = PhiDef->getIncomingValue(i);
183  ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd);
184  if (!CI)
185  continue;
186 
187  // Not an interesting case when IsUnlikely is false -- we can not infer
188  // anything useful when the operand value matches the expected phi
189  // output.
190  if (ExpectedPhiValue == ApplyOperations(CI->getValue()))
191  continue;
192 
193  BranchInst *BI = GetDomConditional(i);
194  if (!BI)
195  continue;
196 
197  MDBuilder MDB(PhiDef->getContext());
198 
199  // There are two situations in which an operand of the PhiDef comes
200  // from a given successor of a branch instruction BI.
201  // 1) When the incoming block of the operand is the successor block;
202  // 2) When the incoming block is BI's enclosing block and the
203  // successor is the PhiDef's enclosing block.
204  //
205  // Returns true if the operand which comes from OpndIncomingBB
206  // comes from outgoing edge of BI that leads to Succ block.
207  auto *OpndIncomingBB = PhiDef->getIncomingBlock(i);
208  auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) {
209  if (OpndIncomingBB == Succ)
210  // If this successor is the incoming block for this
211  // Phi operand, then this successor does lead to the Phi.
212  return true;
213  if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent())
214  // Otherwise, if the edge is directly from the branch
215  // to the Phi, this successor is the one feeding this
216  // Phi operand.
217  return true;
218  return false;
219  };
220 
221  if (IsOpndComingFromSuccessor(BI->getSuccessor(1)))
222  BI->setMetadata(
224  MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight));
225  else if (IsOpndComingFromSuccessor(BI->getSuccessor(0)))
226  BI->setMetadata(
228  MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight));
229  }
230 }
231 
232 // Handle both BranchInst and SelectInst.
233 template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
234 
235  // Handle non-optimized IR code like:
236  // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1)
237  // %tobool = icmp ne i64 %expval, 0
238  // br i1 %tobool, label %if.then, label %if.end
239  //
240  // Or the following simpler case:
241  // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1)
242  // br i1 %expval, label %if.then, label %if.end
243 
244  CallInst *CI;
245 
246  ICmpInst *CmpI = dyn_cast<ICmpInst>(BSI.getCondition());
248  ConstantInt *CmpConstOperand = nullptr;
249  if (!CmpI) {
250  CI = dyn_cast<CallInst>(BSI.getCondition());
251  Predicate = CmpInst::ICMP_NE;
252  } else {
253  Predicate = CmpI->getPredicate();
254  if (Predicate != CmpInst::ICMP_NE && Predicate != CmpInst::ICMP_EQ)
255  return false;
256 
257  CmpConstOperand = dyn_cast<ConstantInt>(CmpI->getOperand(1));
258  if (!CmpConstOperand)
259  return false;
260  CI = dyn_cast<CallInst>(CmpI->getOperand(0));
261  }
262 
263  if (!CI)
264  return false;
265 
266  uint64_t ValueComparedTo = 0;
267  if (CmpConstOperand) {
268  if (CmpConstOperand->getBitWidth() > 64)
269  return false;
270  ValueComparedTo = CmpConstOperand->getZExtValue();
271  }
272 
273  Function *Fn = CI->getCalledFunction();
274  if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect)
275  return false;
276 
277  Value *ArgValue = CI->getArgOperand(0);
278  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
279  if (!ExpectedValue)
280  return false;
281 
282  MDBuilder MDB(CI->getContext());
283  MDNode *Node;
284 
285  if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==
286  (Predicate == CmpInst::ICMP_EQ))
287  Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight);
288  else
289  Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight);
290 
291  BSI.setMetadata(LLVMContext::MD_prof, Node);
292 
293  if (CmpI)
294  CmpI->setOperand(0, ArgValue);
295  else
296  BSI.setCondition(ArgValue);
297  return true;
298 }
299 
300 static bool handleBranchExpect(BranchInst &BI) {
301  if (BI.isUnconditional())
302  return false;
303 
304  return handleBrSelExpect<BranchInst>(BI);
305 }
306 
308  bool Changed = false;
309 
310  for (BasicBlock &BB : F) {
311  // Create "block_weights" metadata.
312  if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
313  if (handleBranchExpect(*BI))
314  ExpectIntrinsicsHandled++;
315  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
316  if (handleSwitchExpect(*SI))
317  ExpectIntrinsicsHandled++;
318  }
319 
320  // Remove llvm.expect intrinsics. Iterate backwards in order
321  // to process select instructions before the intrinsic gets
322  // removed.
323  for (auto BI = BB.rbegin(), BE = BB.rend(); BI != BE;) {
324  Instruction *Inst = &*BI++;
325  CallInst *CI = dyn_cast<CallInst>(Inst);
326  if (!CI) {
327  if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
328  if (handleBrSelExpect(*SI))
329  ExpectIntrinsicsHandled++;
330  }
331  continue;
332  }
333 
334  Function *Fn = CI->getCalledFunction();
335  if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) {
336  // Before erasing the llvm.expect, walk backward to find
337  // phi that define llvm.expect's first arg, and
338  // infer branch probability:
339  handlePhiDef(CI);
340  Value *Exp = CI->getArgOperand(0);
341  CI->replaceAllUsesWith(Exp);
342  CI->eraseFromParent();
343  Changed = true;
344  }
345  }
346  }
347 
348  return Changed;
349 }
350 
353  if (lowerExpectIntrinsic(F))
354  return PreservedAnalyses::none();
355 
356  return PreservedAnalyses::all();
357 }
358 
359 namespace {
360 /// \brief Legacy pass for lowering expect intrinsics out of the IR.
361 ///
362 /// When this pass is run over a function it uses expect intrinsics which feed
363 /// branches and switches to provide branch weight metadata for those
364 /// terminators. It then removes the expect intrinsics from the IR so the rest
365 /// of the optimizer can ignore them.
366 class LowerExpectIntrinsic : public FunctionPass {
367 public:
368  static char ID;
369  LowerExpectIntrinsic() : FunctionPass(ID) {
371  }
372 
373  bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); }
374 };
375 }
376 
377 char LowerExpectIntrinsic::ID = 0;
378 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect",
379  "Lower 'expect' Intrinsics", false, false)
380 
382  return new LowerExpectIntrinsic();
383 }
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:69
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:841
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:523
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:865
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:728
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:862
F(f)
This class represents a sign extension of integer types.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Run the pass over the function.
unsigned getBitWidth() const
getBitWidth - Return the bitwidth of this constant.
Definition: Constants.h:143
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:186
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:138
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
Value * getOperand(unsigned i) const
Definition: User.h:154
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:406
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:149
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:217
void initializeLowerExpectIntrinsicPass(PassRegistry &)
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:853
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
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:1214
static bool handleBrSelExpect(BrSelInst &BSI)
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:27
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:175
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
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)
amdgpu Simplify well known AMD library false Value Value * Arg
Function * getCalledFunction() const
Return the function called, or null if this is an indirect function invocation.
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:927
void setCondition(Value *V)
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
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:323
CaseIt case_default()
Returns an iterator that points to the default case.
bool isUnconditional() const
Multiway switch.
LLVM Value Representation.
Definition: Value.h:73
A container for analyses that lazily runs them and caches their results.
const TerminatorInst * 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:120
static bool handleSwitchExpect(SwitchInst &SI)
FunctionPass * createLowerExpectIntrinsicPass()
const BasicBlock * getParent() const
Definition: Instruction.h:66