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