LLVM  10.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"
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  uint64_t Index = (Case == *SI.case_default()) ? 0 : Case.getCaseIndex() + 1;
76  Weights[Index] = LikelyBranchWeight;
77 
78  SI.setMetadata(
79  LLVMContext::MD_misexpect,
80  MDBuilder(CI->getContext())
81  .createMisExpect(Index, LikelyBranchWeight, UnlikelyBranchWeight));
82 
83  SI.setCondition(ArgValue);
85 
86  SI.setMetadata(LLVMContext::MD_prof,
87  MDBuilder(CI->getContext()).createBranchWeights(Weights));
88 
89  return true;
90 }
91 
92 /// Handler for PHINodes that define the value argument to an
93 /// @llvm.expect call.
94 ///
95 /// If the operand of the phi has a constant value and it 'contradicts'
96 /// with the expected value of phi def, then the corresponding incoming
97 /// edge of the phi is unlikely to be taken. Using that information,
98 /// the branch probability info for the originating branch can be inferred.
99 static void handlePhiDef(CallInst *Expect) {
100  Value &Arg = *Expect->getArgOperand(0);
101  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(Expect->getArgOperand(1));
102  if (!ExpectedValue)
103  return;
104  const APInt &ExpectedPhiValue = ExpectedValue->getValue();
105 
106  // Walk up in backward a list of instructions that
107  // have 'copy' semantics by 'stripping' the copies
108  // until a PHI node or an instruction of unknown kind
109  // is reached. Negation via xor is also handled.
110  //
111  // C = PHI(...);
112  // B = C;
113  // A = B;
114  // D = __builtin_expect(A, 0);
115  //
116  Value *V = &Arg;
118  while (!isa<PHINode>(V)) {
119  if (ZExtInst *ZExt = dyn_cast<ZExtInst>(V)) {
120  V = ZExt->getOperand(0);
121  Operations.push_back(ZExt);
122  continue;
123  }
124 
125  if (SExtInst *SExt = dyn_cast<SExtInst>(V)) {
126  V = SExt->getOperand(0);
127  Operations.push_back(SExt);
128  continue;
129  }
130 
132  if (!BinOp || BinOp->getOpcode() != Instruction::Xor)
133  return;
134 
135  ConstantInt *CInt = dyn_cast<ConstantInt>(BinOp->getOperand(1));
136  if (!CInt)
137  return;
138 
139  V = BinOp->getOperand(0);
140  Operations.push_back(BinOp);
141  }
142 
143  // Executes the recorded operations on input 'Value'.
144  auto ApplyOperations = [&](const APInt &Value) {
145  APInt Result = Value;
146  for (auto Op : llvm::reverse(Operations)) {
147  switch (Op->getOpcode()) {
148  case Instruction::Xor:
149  Result ^= cast<ConstantInt>(Op->getOperand(1))->getValue();
150  break;
151  case Instruction::ZExt:
152  Result = Result.zext(Op->getType()->getIntegerBitWidth());
153  break;
154  case Instruction::SExt:
155  Result = Result.sext(Op->getType()->getIntegerBitWidth());
156  break;
157  default:
158  llvm_unreachable("Unexpected operation");
159  }
160  }
161  return Result;
162  };
163 
164  auto *PhiDef = cast<PHINode>(V);
165 
166  // Get the first dominating conditional branch of the operand
167  // i's incoming block.
168  auto GetDomConditional = [&](unsigned i) -> BranchInst * {
169  BasicBlock *BB = PhiDef->getIncomingBlock(i);
171  if (BI && BI->isConditional())
172  return BI;
173  BB = BB->getSinglePredecessor();
174  if (!BB)
175  return nullptr;
176  BI = dyn_cast<BranchInst>(BB->getTerminator());
177  if (!BI || BI->isUnconditional())
178  return nullptr;
179  return BI;
180  };
181 
182  // Now walk through all Phi operands to find phi oprerands with values
183  // conflicting with the expected phi output value. Any such operand
184  // indicates the incoming edge to that operand is unlikely.
185  for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) {
186 
187  Value *PhiOpnd = PhiDef->getIncomingValue(i);
188  ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd);
189  if (!CI)
190  continue;
191 
192  // Not an interesting case when IsUnlikely is false -- we can not infer
193  // anything useful when the operand value matches the expected phi
194  // output.
195  if (ExpectedPhiValue == ApplyOperations(CI->getValue()))
196  continue;
197 
198  BranchInst *BI = GetDomConditional(i);
199  if (!BI)
200  continue;
201 
202  MDBuilder MDB(PhiDef->getContext());
203 
204  // There are two situations in which an operand of the PhiDef comes
205  // from a given successor of a branch instruction BI.
206  // 1) When the incoming block of the operand is the successor block;
207  // 2) When the incoming block is BI's enclosing block and the
208  // successor is the PhiDef's enclosing block.
209  //
210  // Returns true if the operand which comes from OpndIncomingBB
211  // comes from outgoing edge of BI that leads to Succ block.
212  auto *OpndIncomingBB = PhiDef->getIncomingBlock(i);
213  auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) {
214  if (OpndIncomingBB == Succ)
215  // If this successor is the incoming block for this
216  // Phi operand, then this successor does lead to the Phi.
217  return true;
218  if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent())
219  // Otherwise, if the edge is directly from the branch
220  // to the Phi, this successor is the one feeding this
221  // Phi operand.
222  return true;
223  return false;
224  };
225 
226  if (IsOpndComingFromSuccessor(BI->getSuccessor(1)))
227  BI->setMetadata(
228  LLVMContext::MD_prof,
229  MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight));
230  else if (IsOpndComingFromSuccessor(BI->getSuccessor(0)))
231  BI->setMetadata(
232  LLVMContext::MD_prof,
233  MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight));
234  }
235 }
236 
237 // Handle both BranchInst and SelectInst.
238 template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
239 
240  // Handle non-optimized IR code like:
241  // %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1)
242  // %tobool = icmp ne i64 %expval, 0
243  // br i1 %tobool, label %if.then, label %if.end
244  //
245  // Or the following simpler case:
246  // %expval = call i1 @llvm.expect.i1(i1 %cmp, i1 1)
247  // br i1 %expval, label %if.then, label %if.end
248 
249  CallInst *CI;
250 
251  ICmpInst *CmpI = dyn_cast<ICmpInst>(BSI.getCondition());
253  ConstantInt *CmpConstOperand = nullptr;
254  if (!CmpI) {
255  CI = dyn_cast<CallInst>(BSI.getCondition());
256  Predicate = CmpInst::ICMP_NE;
257  } else {
258  Predicate = CmpI->getPredicate();
259  if (Predicate != CmpInst::ICMP_NE && Predicate != CmpInst::ICMP_EQ)
260  return false;
261 
262  CmpConstOperand = dyn_cast<ConstantInt>(CmpI->getOperand(1));
263  if (!CmpConstOperand)
264  return false;
265  CI = dyn_cast<CallInst>(CmpI->getOperand(0));
266  }
267 
268  if (!CI)
269  return false;
270 
271  uint64_t ValueComparedTo = 0;
272  if (CmpConstOperand) {
273  if (CmpConstOperand->getBitWidth() > 64)
274  return false;
275  ValueComparedTo = CmpConstOperand->getZExtValue();
276  }
277 
278  Function *Fn = CI->getCalledFunction();
279  if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect)
280  return false;
281 
282  Value *ArgValue = CI->getArgOperand(0);
283  ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
284  if (!ExpectedValue)
285  return false;
286 
287  MDBuilder MDB(CI->getContext());
288  MDNode *Node;
289  MDNode *ExpNode;
290 
291  if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==
292  (Predicate == CmpInst::ICMP_EQ)) {
293  Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight);
294  ExpNode = MDB.createMisExpect(0, LikelyBranchWeight, UnlikelyBranchWeight);
295  } else {
296  Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight);
297  ExpNode = MDB.createMisExpect(1, LikelyBranchWeight, UnlikelyBranchWeight);
298  }
299 
300  BSI.setMetadata(LLVMContext::MD_misexpect, ExpNode);
301 
302  if (CmpI)
303  CmpI->setOperand(0, ArgValue);
304  else
305  BSI.setCondition(ArgValue);
306 
308 
309  BSI.setMetadata(LLVMContext::MD_prof, Node);
310 
311  return true;
312 }
313 
314 static bool handleBranchExpect(BranchInst &BI) {
315  if (BI.isUnconditional())
316  return false;
317 
318  return handleBrSelExpect<BranchInst>(BI);
319 }
320 
322  bool Changed = false;
323 
324  for (BasicBlock &BB : F) {
325  // Create "block_weights" metadata.
326  if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
327  if (handleBranchExpect(*BI))
328  ExpectIntrinsicsHandled++;
329  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
330  if (handleSwitchExpect(*SI))
331  ExpectIntrinsicsHandled++;
332  }
333 
334  // Remove llvm.expect intrinsics. Iterate backwards in order
335  // to process select instructions before the intrinsic gets
336  // removed.
337  for (auto BI = BB.rbegin(), BE = BB.rend(); BI != BE;) {
338  Instruction *Inst = &*BI++;
339  CallInst *CI = dyn_cast<CallInst>(Inst);
340  if (!CI) {
341  if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
342  if (handleBrSelExpect(*SI))
343  ExpectIntrinsicsHandled++;
344  }
345  continue;
346  }
347 
348  Function *Fn = CI->getCalledFunction();
349  if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) {
350  // Before erasing the llvm.expect, walk backward to find
351  // phi that define llvm.expect's first arg, and
352  // infer branch probability:
353  handlePhiDef(CI);
354  Value *Exp = CI->getArgOperand(0);
355  CI->replaceAllUsesWith(Exp);
356  CI->eraseFromParent();
357  Changed = true;
358  }
359  }
360  }
361 
362  return Changed;
363 }
364 
367  if (lowerExpectIntrinsic(F))
368  return PreservedAnalyses::none();
369 
370  return PreservedAnalyses::all();
371 }
372 
373 namespace {
374 /// Legacy pass for lowering expect intrinsics out of the IR.
375 ///
376 /// When this pass is run over a function it uses expect intrinsics which feed
377 /// branches and switches to provide branch weight metadata for those
378 /// terminators. It then removes the expect intrinsics from the IR so the rest
379 /// of the optimizer can ignore them.
380 class LowerExpectIntrinsic : public FunctionPass {
381 public:
382  static char ID;
383  LowerExpectIntrinsic() : FunctionPass(ID) {
385  }
386 
387  bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); }
388 };
389 }
390 
391 char LowerExpectIntrinsic::ID = 0;
392 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect",
393  "Lower 'expect' Intrinsics", false, false)
394 
396  return new LowerExpectIntrinsic();
397 }
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:888
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:402
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:912
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:743
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:144
unsigned getBitWidth() const
getBitWidth - Return the bitwidth of this constant.
Definition: Constants.h:142
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1241
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:261
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:157
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:432
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:154
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:240
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:732
constexpr double e
Definition: MathExtras.h:57
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:160
#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:1222
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:807
void setCondition(Value *V)
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1287
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:332
CaseIt case_default()
Returns an iterator that points to the default case.
bool isUnconditional() const
Multiway switch.
LLVM Value Representation.
Definition: Value.h:74
A container for analyses that lazily runs them and caches their results.
static bool handleSwitchExpect(SwitchInst &SI)
void checkFrontendInstrumentation(Instruction &I)
checkClangInstrumentation - verify if llvm.expect matches PGO profile This function checks the fronte...
Definition: MisExpect.cpp:147
FunctionPass * createLowerExpectIntrinsicPass()
const BasicBlock * getParent() const
Definition: Instruction.h:66