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