1 | //===- JumpThreading.cpp - Thread control through conditional blocks ------===// |
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 file implements the Jump Threading pass. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #include "llvm/Transforms/Scalar/JumpThreading.h" |
14 | #include "llvm/ADT/DenseMap.h" |
15 | #include "llvm/ADT/DenseSet.h" |
16 | #include "llvm/ADT/MapVector.h" |
17 | #include "llvm/ADT/STLExtras.h" |
18 | #include "llvm/ADT/SmallPtrSet.h" |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/ADT/Statistic.h" |
21 | #include "llvm/Analysis/AliasAnalysis.h" |
22 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
23 | #include "llvm/Analysis/BranchProbabilityInfo.h" |
24 | #include "llvm/Analysis/CFG.h" |
25 | #include "llvm/Analysis/ConstantFolding.h" |
26 | #include "llvm/Analysis/GlobalsModRef.h" |
27 | #include "llvm/Analysis/GuardUtils.h" |
28 | #include "llvm/Analysis/InstructionSimplify.h" |
29 | #include "llvm/Analysis/LazyValueInfo.h" |
30 | #include "llvm/Analysis/Loads.h" |
31 | #include "llvm/Analysis/LoopInfo.h" |
32 | #include "llvm/Analysis/MemoryLocation.h" |
33 | #include "llvm/Analysis/PostDominators.h" |
34 | #include "llvm/Analysis/TargetLibraryInfo.h" |
35 | #include "llvm/Analysis/TargetTransformInfo.h" |
36 | #include "llvm/Analysis/ValueTracking.h" |
37 | #include "llvm/IR/BasicBlock.h" |
38 | #include "llvm/IR/CFG.h" |
39 | #include "llvm/IR/Constant.h" |
40 | #include "llvm/IR/ConstantRange.h" |
41 | #include "llvm/IR/Constants.h" |
42 | #include "llvm/IR/DataLayout.h" |
43 | #include "llvm/IR/DebugInfo.h" |
44 | #include "llvm/IR/Dominators.h" |
45 | #include "llvm/IR/Function.h" |
46 | #include "llvm/IR/InstrTypes.h" |
47 | #include "llvm/IR/Instruction.h" |
48 | #include "llvm/IR/Instructions.h" |
49 | #include "llvm/IR/IntrinsicInst.h" |
50 | #include "llvm/IR/Intrinsics.h" |
51 | #include "llvm/IR/LLVMContext.h" |
52 | #include "llvm/IR/MDBuilder.h" |
53 | #include "llvm/IR/Metadata.h" |
54 | #include "llvm/IR/Module.h" |
55 | #include "llvm/IR/PassManager.h" |
56 | #include "llvm/IR/PatternMatch.h" |
57 | #include "llvm/IR/ProfDataUtils.h" |
58 | #include "llvm/IR/Type.h" |
59 | #include "llvm/IR/Use.h" |
60 | #include "llvm/IR/Value.h" |
61 | #include "llvm/Support/BlockFrequency.h" |
62 | #include "llvm/Support/BranchProbability.h" |
63 | #include "llvm/Support/Casting.h" |
64 | #include "llvm/Support/CommandLine.h" |
65 | #include "llvm/Support/Debug.h" |
66 | #include "llvm/Support/raw_ostream.h" |
67 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
68 | #include "llvm/Transforms/Utils/Cloning.h" |
69 | #include "llvm/Transforms/Utils/Local.h" |
70 | #include "llvm/Transforms/Utils/SSAUpdater.h" |
71 | #include "llvm/Transforms/Utils/ValueMapper.h" |
72 | #include <algorithm> |
73 | #include <cassert> |
74 | #include <cstdint> |
75 | #include <iterator> |
76 | #include <memory> |
77 | #include <utility> |
78 | |
79 | using namespace llvm; |
80 | using namespace jumpthreading; |
81 | |
82 | #define DEBUG_TYPE "jump-threading" |
83 | |
84 | STATISTIC(NumThreads, "Number of jumps threaded" ); |
85 | STATISTIC(NumFolds, "Number of terminators folded" ); |
86 | STATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi" ); |
87 | |
88 | static cl::opt<unsigned> |
89 | BBDuplicateThreshold("jump-threading-threshold" , |
90 | cl::desc("Max block size to duplicate for jump threading" ), |
91 | cl::init(Val: 6), cl::Hidden); |
92 | |
93 | static cl::opt<unsigned> |
94 | ImplicationSearchThreshold( |
95 | "jump-threading-implication-search-threshold" , |
96 | cl::desc("The number of predecessors to search for a stronger " |
97 | "condition to use to thread over a weaker condition" ), |
98 | cl::init(Val: 3), cl::Hidden); |
99 | |
100 | static cl::opt<unsigned> PhiDuplicateThreshold( |
101 | "jump-threading-phi-threshold" , |
102 | cl::desc("Max PHIs in BB to duplicate for jump threading" ), cl::init(Val: 76), |
103 | cl::Hidden); |
104 | |
105 | static cl::opt<bool> ( |
106 | "jump-threading-across-loop-headers" , |
107 | cl::desc("Allow JumpThreading to thread across loop headers, for testing" ), |
108 | cl::init(Val: false), cl::Hidden); |
109 | |
110 | JumpThreadingPass::JumpThreadingPass(int T) { |
111 | DefaultBBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T); |
112 | } |
113 | |
114 | // Update branch probability information according to conditional |
115 | // branch probability. This is usually made possible for cloned branches |
116 | // in inline instances by the context specific profile in the caller. |
117 | // For instance, |
118 | // |
119 | // [Block PredBB] |
120 | // [Branch PredBr] |
121 | // if (t) { |
122 | // Block A; |
123 | // } else { |
124 | // Block B; |
125 | // } |
126 | // |
127 | // [Block BB] |
128 | // cond = PN([true, %A], [..., %B]); // PHI node |
129 | // [Branch CondBr] |
130 | // if (cond) { |
131 | // ... // P(cond == true) = 1% |
132 | // } |
133 | // |
134 | // Here we know that when block A is taken, cond must be true, which means |
135 | // P(cond == true | A) = 1 |
136 | // |
137 | // Given that P(cond == true) = P(cond == true | A) * P(A) + |
138 | // P(cond == true | B) * P(B) |
139 | // we get: |
140 | // P(cond == true ) = P(A) + P(cond == true | B) * P(B) |
141 | // |
142 | // which gives us: |
143 | // P(A) is less than P(cond == true), i.e. |
144 | // P(t == true) <= P(cond == true) |
145 | // |
146 | // In other words, if we know P(cond == true) is unlikely, we know |
147 | // that P(t == true) is also unlikely. |
148 | // |
149 | static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB) { |
150 | BranchInst *CondBr = dyn_cast<BranchInst>(Val: BB->getTerminator()); |
151 | if (!CondBr) |
152 | return; |
153 | |
154 | uint64_t TrueWeight, FalseWeight; |
155 | if (!extractBranchWeights(I: *CondBr, TrueVal&: TrueWeight, FalseVal&: FalseWeight)) |
156 | return; |
157 | |
158 | if (TrueWeight + FalseWeight == 0) |
159 | // Zero branch_weights do not give a hint for getting branch probabilities. |
160 | // Technically it would result in division by zero denominator, which is |
161 | // TrueWeight + FalseWeight. |
162 | return; |
163 | |
164 | // Returns the outgoing edge of the dominating predecessor block |
165 | // that leads to the PhiNode's incoming block: |
166 | auto GetPredOutEdge = |
167 | [](BasicBlock *IncomingBB, |
168 | BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> { |
169 | auto *PredBB = IncomingBB; |
170 | auto *SuccBB = PhiBB; |
171 | SmallPtrSet<BasicBlock *, 16> Visited; |
172 | while (true) { |
173 | BranchInst *PredBr = dyn_cast<BranchInst>(Val: PredBB->getTerminator()); |
174 | if (PredBr && PredBr->isConditional()) |
175 | return {PredBB, SuccBB}; |
176 | Visited.insert(Ptr: PredBB); |
177 | auto *SinglePredBB = PredBB->getSinglePredecessor(); |
178 | if (!SinglePredBB) |
179 | return {nullptr, nullptr}; |
180 | |
181 | // Stop searching when SinglePredBB has been visited. It means we see |
182 | // an unreachable loop. |
183 | if (Visited.count(Ptr: SinglePredBB)) |
184 | return {nullptr, nullptr}; |
185 | |
186 | SuccBB = PredBB; |
187 | PredBB = SinglePredBB; |
188 | } |
189 | }; |
190 | |
191 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
192 | Value *PhiOpnd = PN->getIncomingValue(i); |
193 | ConstantInt *CI = dyn_cast<ConstantInt>(Val: PhiOpnd); |
194 | |
195 | if (!CI || !CI->getType()->isIntegerTy(Bitwidth: 1)) |
196 | continue; |
197 | |
198 | BranchProbability BP = |
199 | (CI->isOne() ? BranchProbability::getBranchProbability( |
200 | Numerator: TrueWeight, Denominator: TrueWeight + FalseWeight) |
201 | : BranchProbability::getBranchProbability( |
202 | Numerator: FalseWeight, Denominator: TrueWeight + FalseWeight)); |
203 | |
204 | auto PredOutEdge = GetPredOutEdge(PN->getIncomingBlock(i), BB); |
205 | if (!PredOutEdge.first) |
206 | return; |
207 | |
208 | BasicBlock *PredBB = PredOutEdge.first; |
209 | BranchInst *PredBr = dyn_cast<BranchInst>(Val: PredBB->getTerminator()); |
210 | if (!PredBr) |
211 | return; |
212 | |
213 | uint64_t PredTrueWeight, PredFalseWeight; |
214 | // FIXME: We currently only set the profile data when it is missing. |
215 | // With PGO, this can be used to refine even existing profile data with |
216 | // context information. This needs to be done after more performance |
217 | // testing. |
218 | if (extractBranchWeights(I: *PredBr, TrueVal&: PredTrueWeight, FalseVal&: PredFalseWeight)) |
219 | continue; |
220 | |
221 | // We can not infer anything useful when BP >= 50%, because BP is the |
222 | // upper bound probability value. |
223 | if (BP >= BranchProbability(50, 100)) |
224 | continue; |
225 | |
226 | uint32_t Weights[2]; |
227 | if (PredBr->getSuccessor(i: 0) == PredOutEdge.second) { |
228 | Weights[0] = BP.getNumerator(); |
229 | Weights[1] = BP.getCompl().getNumerator(); |
230 | } else { |
231 | Weights[0] = BP.getCompl().getNumerator(); |
232 | Weights[1] = BP.getNumerator(); |
233 | } |
234 | setBranchWeights(I&: *PredBr, Weights); |
235 | } |
236 | } |
237 | |
238 | PreservedAnalyses JumpThreadingPass::run(Function &F, |
239 | FunctionAnalysisManager &AM) { |
240 | auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F); |
241 | // Jump Threading has no sense for the targets with divergent CF |
242 | if (TTI.hasBranchDivergence(F: &F)) |
243 | return PreservedAnalyses::all(); |
244 | auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F); |
245 | auto &LVI = AM.getResult<LazyValueAnalysis>(IR&: F); |
246 | auto &AA = AM.getResult<AAManager>(IR&: F); |
247 | auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F); |
248 | |
249 | bool Changed = |
250 | runImpl(F, FAM: &AM, TLI: &TLI, TTI: &TTI, LVI: &LVI, AA: &AA, |
251 | DTU: std::make_unique<DomTreeUpdater>( |
252 | args: &DT, args: nullptr, args: DomTreeUpdater::UpdateStrategy::Lazy), |
253 | BFI: std::nullopt, BPI: std::nullopt); |
254 | |
255 | if (!Changed) |
256 | return PreservedAnalyses::all(); |
257 | |
258 | |
259 | getDomTreeUpdater()->flush(); |
260 | |
261 | #if defined(EXPENSIVE_CHECKS) |
262 | assert(getDomTreeUpdater()->getDomTree().verify( |
263 | DominatorTree::VerificationLevel::Full) && |
264 | "DT broken after JumpThreading" ); |
265 | assert((!getDomTreeUpdater()->hasPostDomTree() || |
266 | getDomTreeUpdater()->getPostDomTree().verify( |
267 | PostDominatorTree::VerificationLevel::Full)) && |
268 | "PDT broken after JumpThreading" ); |
269 | #else |
270 | assert(getDomTreeUpdater()->getDomTree().verify( |
271 | DominatorTree::VerificationLevel::Fast) && |
272 | "DT broken after JumpThreading" ); |
273 | assert((!getDomTreeUpdater()->hasPostDomTree() || |
274 | getDomTreeUpdater()->getPostDomTree().verify( |
275 | PostDominatorTree::VerificationLevel::Fast)) && |
276 | "PDT broken after JumpThreading" ); |
277 | #endif |
278 | |
279 | return getPreservedAnalysis(); |
280 | } |
281 | |
282 | bool JumpThreadingPass::runImpl(Function &F_, FunctionAnalysisManager *FAM_, |
283 | TargetLibraryInfo *TLI_, |
284 | TargetTransformInfo *TTI_, LazyValueInfo *LVI_, |
285 | AliasAnalysis *AA_, |
286 | std::unique_ptr<DomTreeUpdater> DTU_, |
287 | std::optional<BlockFrequencyInfo *> BFI_, |
288 | std::optional<BranchProbabilityInfo *> BPI_) { |
289 | LLVM_DEBUG(dbgs() << "Jump threading on function '" << F_.getName() << "'\n" ); |
290 | F = &F_; |
291 | FAM = FAM_; |
292 | TLI = TLI_; |
293 | TTI = TTI_; |
294 | LVI = LVI_; |
295 | AA = AA_; |
296 | DTU = std::move(DTU_); |
297 | BFI = BFI_; |
298 | BPI = BPI_; |
299 | auto *GuardDecl = F->getParent()->getFunction( |
300 | Intrinsic::getName(Intrinsic::experimental_guard)); |
301 | HasGuards = GuardDecl && !GuardDecl->use_empty(); |
302 | |
303 | // Reduce the number of instructions duplicated when optimizing strictly for |
304 | // size. |
305 | if (BBDuplicateThreshold.getNumOccurrences()) |
306 | BBDupThreshold = BBDuplicateThreshold; |
307 | else if (F->hasFnAttribute(Attribute::MinSize)) |
308 | BBDupThreshold = 3; |
309 | else |
310 | BBDupThreshold = DefaultBBDupThreshold; |
311 | |
312 | // JumpThreading must not processes blocks unreachable from entry. It's a |
313 | // waste of compute time and can potentially lead to hangs. |
314 | SmallPtrSet<BasicBlock *, 16> Unreachable; |
315 | assert(DTU && "DTU isn't passed into JumpThreading before using it." ); |
316 | assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed." ); |
317 | DominatorTree &DT = DTU->getDomTree(); |
318 | for (auto &BB : *F) |
319 | if (!DT.isReachableFromEntry(A: &BB)) |
320 | Unreachable.insert(Ptr: &BB); |
321 | |
322 | if (!ThreadAcrossLoopHeaders) |
323 | findLoopHeaders(F&: *F); |
324 | |
325 | bool EverChanged = false; |
326 | bool Changed; |
327 | do { |
328 | Changed = false; |
329 | for (auto &BB : *F) { |
330 | if (Unreachable.count(Ptr: &BB)) |
331 | continue; |
332 | while (processBlock(BB: &BB)) // Thread all of the branches we can over BB. |
333 | Changed = ChangedSinceLastAnalysisUpdate = true; |
334 | |
335 | // Jump threading may have introduced redundant debug values into BB |
336 | // which should be removed. |
337 | if (Changed) |
338 | RemoveRedundantDbgInstrs(BB: &BB); |
339 | |
340 | // Stop processing BB if it's the entry or is now deleted. The following |
341 | // routines attempt to eliminate BB and locating a suitable replacement |
342 | // for the entry is non-trivial. |
343 | if (&BB == &F->getEntryBlock() || DTU->isBBPendingDeletion(DelBB: &BB)) |
344 | continue; |
345 | |
346 | if (pred_empty(BB: &BB)) { |
347 | // When processBlock makes BB unreachable it doesn't bother to fix up |
348 | // the instructions in it. We must remove BB to prevent invalid IR. |
349 | LLVM_DEBUG(dbgs() << " JT: Deleting dead block '" << BB.getName() |
350 | << "' with terminator: " << *BB.getTerminator() |
351 | << '\n'); |
352 | LoopHeaders.erase(V: &BB); |
353 | LVI->eraseBlock(BB: &BB); |
354 | DeleteDeadBlock(BB: &BB, DTU: DTU.get()); |
355 | Changed = ChangedSinceLastAnalysisUpdate = true; |
356 | continue; |
357 | } |
358 | |
359 | // processBlock doesn't thread BBs with unconditional TIs. However, if BB |
360 | // is "almost empty", we attempt to merge BB with its sole successor. |
361 | auto *BI = dyn_cast<BranchInst>(Val: BB.getTerminator()); |
362 | if (BI && BI->isUnconditional()) { |
363 | BasicBlock *Succ = BI->getSuccessor(i: 0); |
364 | if ( |
365 | // The terminator must be the only non-phi instruction in BB. |
366 | BB.getFirstNonPHIOrDbg(SkipPseudoOp: true)->isTerminator() && |
367 | // Don't alter Loop headers and latches to ensure another pass can |
368 | // detect and transform nested loops later. |
369 | !LoopHeaders.count(V: &BB) && !LoopHeaders.count(V: Succ) && |
370 | TryToSimplifyUncondBranchFromEmptyBlock(BB: &BB, DTU: DTU.get())) { |
371 | RemoveRedundantDbgInstrs(BB: Succ); |
372 | // BB is valid for cleanup here because we passed in DTU. F remains |
373 | // BB's parent until a DTU->getDomTree() event. |
374 | LVI->eraseBlock(BB: &BB); |
375 | Changed = ChangedSinceLastAnalysisUpdate = true; |
376 | } |
377 | } |
378 | } |
379 | EverChanged |= Changed; |
380 | } while (Changed); |
381 | |
382 | LoopHeaders.clear(); |
383 | return EverChanged; |
384 | } |
385 | |
386 | // Replace uses of Cond with ToVal when safe to do so. If all uses are |
387 | // replaced, we can remove Cond. We cannot blindly replace all uses of Cond |
388 | // because we may incorrectly replace uses when guards/assumes are uses of |
389 | // of `Cond` and we used the guards/assume to reason about the `Cond` value |
390 | // at the end of block. RAUW unconditionally replaces all uses |
391 | // including the guards/assumes themselves and the uses before the |
392 | // guard/assume. |
393 | static bool replaceFoldableUses(Instruction *Cond, Value *ToVal, |
394 | BasicBlock *KnownAtEndOfBB) { |
395 | bool Changed = false; |
396 | assert(Cond->getType() == ToVal->getType()); |
397 | // We can unconditionally replace all uses in non-local blocks (i.e. uses |
398 | // strictly dominated by BB), since LVI information is true from the |
399 | // terminator of BB. |
400 | if (Cond->getParent() == KnownAtEndOfBB) |
401 | Changed |= replaceNonLocalUsesWith(From: Cond, To: ToVal); |
402 | for (Instruction &I : reverse(C&: *KnownAtEndOfBB)) { |
403 | // Replace any debug-info record users of Cond with ToVal. |
404 | for (DbgVariableRecord &DVR : filterDbgVars(R: I.getDbgRecordRange())) |
405 | DVR.replaceVariableLocationOp(OldValue: Cond, NewValue: ToVal, AllowEmpty: true); |
406 | |
407 | // Reached the Cond whose uses we are trying to replace, so there are no |
408 | // more uses. |
409 | if (&I == Cond) |
410 | break; |
411 | // We only replace uses in instructions that are guaranteed to reach the end |
412 | // of BB, where we know Cond is ToVal. |
413 | if (!isGuaranteedToTransferExecutionToSuccessor(I: &I)) |
414 | break; |
415 | Changed |= I.replaceUsesOfWith(From: Cond, To: ToVal); |
416 | } |
417 | if (Cond->use_empty() && !Cond->mayHaveSideEffects()) { |
418 | Cond->eraseFromParent(); |
419 | Changed = true; |
420 | } |
421 | return Changed; |
422 | } |
423 | |
424 | /// Return the cost of duplicating a piece of this block from first non-phi |
425 | /// and before StopAt instruction to thread across it. Stop scanning the block |
426 | /// when exceeding the threshold. If duplication is impossible, returns ~0U. |
427 | static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI, |
428 | BasicBlock *BB, |
429 | Instruction *StopAt, |
430 | unsigned Threshold) { |
431 | assert(StopAt->getParent() == BB && "Not an instruction from proper BB?" ); |
432 | |
433 | // Do not duplicate the BB if it has a lot of PHI nodes. |
434 | // If a threadable chain is too long then the number of PHI nodes can add up, |
435 | // leading to a substantial increase in compile time when rewriting the SSA. |
436 | unsigned PhiCount = 0; |
437 | Instruction *FirstNonPHI = nullptr; |
438 | for (Instruction &I : *BB) { |
439 | if (!isa<PHINode>(Val: &I)) { |
440 | FirstNonPHI = &I; |
441 | break; |
442 | } |
443 | if (++PhiCount > PhiDuplicateThreshold) |
444 | return ~0U; |
445 | } |
446 | |
447 | /// Ignore PHI nodes, these will be flattened when duplication happens. |
448 | BasicBlock::const_iterator I(FirstNonPHI); |
449 | |
450 | // FIXME: THREADING will delete values that are just used to compute the |
451 | // branch, so they shouldn't count against the duplication cost. |
452 | |
453 | unsigned Bonus = 0; |
454 | if (BB->getTerminator() == StopAt) { |
455 | // Threading through a switch statement is particularly profitable. If this |
456 | // block ends in a switch, decrease its cost to make it more likely to |
457 | // happen. |
458 | if (isa<SwitchInst>(Val: StopAt)) |
459 | Bonus = 6; |
460 | |
461 | // The same holds for indirect branches, but slightly more so. |
462 | if (isa<IndirectBrInst>(Val: StopAt)) |
463 | Bonus = 8; |
464 | } |
465 | |
466 | // Bump the threshold up so the early exit from the loop doesn't skip the |
467 | // terminator-based Size adjustment at the end. |
468 | Threshold += Bonus; |
469 | |
470 | // Sum up the cost of each instruction until we get to the terminator. Don't |
471 | // include the terminator because the copy won't include it. |
472 | unsigned Size = 0; |
473 | for (; &*I != StopAt; ++I) { |
474 | |
475 | // Stop scanning the block if we've reached the threshold. |
476 | if (Size > Threshold) |
477 | return Size; |
478 | |
479 | // Bail out if this instruction gives back a token type, it is not possible |
480 | // to duplicate it if it is used outside this BB. |
481 | if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB)) |
482 | return ~0U; |
483 | |
484 | // Blocks with NoDuplicate are modelled as having infinite cost, so they |
485 | // are never duplicated. |
486 | if (const CallInst *CI = dyn_cast<CallInst>(Val&: I)) |
487 | if (CI->cannotDuplicate() || CI->isConvergent()) |
488 | return ~0U; |
489 | |
490 | if (TTI->getInstructionCost(U: &*I, CostKind: TargetTransformInfo::TCK_SizeAndLatency) == |
491 | TargetTransformInfo::TCC_Free) |
492 | continue; |
493 | |
494 | // All other instructions count for at least one unit. |
495 | ++Size; |
496 | |
497 | // Calls are more expensive. If they are non-intrinsic calls, we model them |
498 | // as having cost of 4. If they are a non-vector intrinsic, we model them |
499 | // as having cost of 2 total, and if they are a vector intrinsic, we model |
500 | // them as having cost 1. |
501 | if (const CallInst *CI = dyn_cast<CallInst>(Val&: I)) { |
502 | if (!isa<IntrinsicInst>(Val: CI)) |
503 | Size += 3; |
504 | else if (!CI->getType()->isVectorTy()) |
505 | Size += 1; |
506 | } |
507 | } |
508 | |
509 | return Size > Bonus ? Size - Bonus : 0; |
510 | } |
511 | |
512 | /// findLoopHeaders - We do not want jump threading to turn proper loop |
513 | /// structures into irreducible loops. Doing this breaks up the loop nesting |
514 | /// hierarchy and pessimizes later transformations. To prevent this from |
515 | /// happening, we first have to find the loop headers. Here we approximate this |
516 | /// by finding targets of backedges in the CFG. |
517 | /// |
518 | /// Note that there definitely are cases when we want to allow threading of |
519 | /// edges across a loop header. For example, threading a jump from outside the |
520 | /// loop (the preheader) to an exit block of the loop is definitely profitable. |
521 | /// It is also almost always profitable to thread backedges from within the loop |
522 | /// to exit blocks, and is often profitable to thread backedges to other blocks |
523 | /// within the loop (forming a nested loop). This simple analysis is not rich |
524 | /// enough to track all of these properties and keep it up-to-date as the CFG |
525 | /// mutates, so we don't allow any of these transformations. |
526 | void JumpThreadingPass::(Function &F) { |
527 | SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; |
528 | FindFunctionBackedges(F, Result&: Edges); |
529 | |
530 | for (const auto &Edge : Edges) |
531 | LoopHeaders.insert(V: Edge.second); |
532 | } |
533 | |
534 | /// getKnownConstant - Helper method to determine if we can thread over a |
535 | /// terminator with the given value as its condition, and if so what value to |
536 | /// use for that. What kind of value this is depends on whether we want an |
537 | /// integer or a block address, but an undef is always accepted. |
538 | /// Returns null if Val is null or not an appropriate constant. |
539 | static Constant *getKnownConstant(Value *Val, ConstantPreference Preference) { |
540 | if (!Val) |
541 | return nullptr; |
542 | |
543 | // Undef is "known" enough. |
544 | if (UndefValue *U = dyn_cast<UndefValue>(Val)) |
545 | return U; |
546 | |
547 | if (Preference == WantBlockAddress) |
548 | return dyn_cast<BlockAddress>(Val: Val->stripPointerCasts()); |
549 | |
550 | return dyn_cast<ConstantInt>(Val); |
551 | } |
552 | |
553 | /// computeValueKnownInPredecessors - Given a basic block BB and a value V, see |
554 | /// if we can infer that the value is a known ConstantInt/BlockAddress or undef |
555 | /// in any of our predecessors. If so, return the known list of value and pred |
556 | /// BB in the result vector. |
557 | /// |
558 | /// This returns true if there were any known values. |
559 | bool JumpThreadingPass::computeValueKnownInPredecessorsImpl( |
560 | Value *V, BasicBlock *BB, PredValueInfo &Result, |
561 | ConstantPreference Preference, DenseSet<Value *> &RecursionSet, |
562 | Instruction *CxtI) { |
563 | const DataLayout &DL = BB->getModule()->getDataLayout(); |
564 | |
565 | // This method walks up use-def chains recursively. Because of this, we could |
566 | // get into an infinite loop going around loops in the use-def chain. To |
567 | // prevent this, keep track of what (value, block) pairs we've already visited |
568 | // and terminate the search if we loop back to them |
569 | if (!RecursionSet.insert(V).second) |
570 | return false; |
571 | |
572 | // If V is a constant, then it is known in all predecessors. |
573 | if (Constant *KC = getKnownConstant(Val: V, Preference)) { |
574 | for (BasicBlock *Pred : predecessors(BB)) |
575 | Result.emplace_back(Args&: KC, Args&: Pred); |
576 | |
577 | return !Result.empty(); |
578 | } |
579 | |
580 | // If V is a non-instruction value, or an instruction in a different block, |
581 | // then it can't be derived from a PHI. |
582 | Instruction *I = dyn_cast<Instruction>(Val: V); |
583 | if (!I || I->getParent() != BB) { |
584 | |
585 | // Okay, if this is a live-in value, see if it has a known value at the any |
586 | // edge from our predecessors. |
587 | for (BasicBlock *P : predecessors(BB)) { |
588 | using namespace PatternMatch; |
589 | // If the value is known by LazyValueInfo to be a constant in a |
590 | // predecessor, use that information to try to thread this block. |
591 | Constant *PredCst = LVI->getConstantOnEdge(V, FromBB: P, ToBB: BB, CxtI); |
592 | // If I is a non-local compare-with-constant instruction, use more-rich |
593 | // 'getPredicateOnEdge' method. This would be able to handle value |
594 | // inequalities better, for example if the compare is "X < 4" and "X < 3" |
595 | // is known true but "X < 4" itself is not available. |
596 | CmpInst::Predicate Pred; |
597 | Value *Val; |
598 | Constant *Cst; |
599 | if (!PredCst && match(V, P: m_Cmp(Pred, L: m_Value(V&: Val), R: m_Constant(C&: Cst)))) { |
600 | auto Res = LVI->getPredicateOnEdge(Pred, V: Val, C: Cst, FromBB: P, ToBB: BB, CxtI); |
601 | if (Res != LazyValueInfo::Unknown) |
602 | PredCst = ConstantInt::getBool(Context&: V->getContext(), V: Res); |
603 | } |
604 | if (Constant *KC = getKnownConstant(Val: PredCst, Preference)) |
605 | Result.emplace_back(Args&: KC, Args&: P); |
606 | } |
607 | |
608 | return !Result.empty(); |
609 | } |
610 | |
611 | /// If I is a PHI node, then we know the incoming values for any constants. |
612 | if (PHINode *PN = dyn_cast<PHINode>(Val: I)) { |
613 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
614 | Value *InVal = PN->getIncomingValue(i); |
615 | if (Constant *KC = getKnownConstant(Val: InVal, Preference)) { |
616 | Result.emplace_back(Args&: KC, Args: PN->getIncomingBlock(i)); |
617 | } else { |
618 | Constant *CI = LVI->getConstantOnEdge(V: InVal, |
619 | FromBB: PN->getIncomingBlock(i), |
620 | ToBB: BB, CxtI); |
621 | if (Constant *KC = getKnownConstant(Val: CI, Preference)) |
622 | Result.emplace_back(Args&: KC, Args: PN->getIncomingBlock(i)); |
623 | } |
624 | } |
625 | |
626 | return !Result.empty(); |
627 | } |
628 | |
629 | // Handle Cast instructions. |
630 | if (CastInst *CI = dyn_cast<CastInst>(Val: I)) { |
631 | Value *Source = CI->getOperand(i_nocapture: 0); |
632 | PredValueInfoTy Vals; |
633 | computeValueKnownInPredecessorsImpl(V: Source, BB, Result&: Vals, Preference, |
634 | RecursionSet, CxtI); |
635 | if (Vals.empty()) |
636 | return false; |
637 | |
638 | // Convert the known values. |
639 | for (auto &Val : Vals) |
640 | if (Constant *Folded = ConstantFoldCastOperand(Opcode: CI->getOpcode(), C: Val.first, |
641 | DestTy: CI->getType(), DL)) |
642 | Result.emplace_back(Args&: Folded, Args&: Val.second); |
643 | |
644 | return !Result.empty(); |
645 | } |
646 | |
647 | if (FreezeInst *FI = dyn_cast<FreezeInst>(Val: I)) { |
648 | Value *Source = FI->getOperand(i_nocapture: 0); |
649 | computeValueKnownInPredecessorsImpl(V: Source, BB, Result, Preference, |
650 | RecursionSet, CxtI); |
651 | |
652 | erase_if(C&: Result, P: [](auto &Pair) { |
653 | return !isGuaranteedNotToBeUndefOrPoison(Pair.first); |
654 | }); |
655 | |
656 | return !Result.empty(); |
657 | } |
658 | |
659 | // Handle some boolean conditions. |
660 | if (I->getType()->getPrimitiveSizeInBits() == 1) { |
661 | using namespace PatternMatch; |
662 | if (Preference != WantInteger) |
663 | return false; |
664 | // X | true -> true |
665 | // X & false -> false |
666 | Value *Op0, *Op1; |
667 | if (match(V: I, P: m_LogicalOr(L: m_Value(V&: Op0), R: m_Value(V&: Op1))) || |
668 | match(V: I, P: m_LogicalAnd(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) { |
669 | PredValueInfoTy LHSVals, RHSVals; |
670 | |
671 | computeValueKnownInPredecessorsImpl(V: Op0, BB, Result&: LHSVals, Preference: WantInteger, |
672 | RecursionSet, CxtI); |
673 | computeValueKnownInPredecessorsImpl(V: Op1, BB, Result&: RHSVals, Preference: WantInteger, |
674 | RecursionSet, CxtI); |
675 | |
676 | if (LHSVals.empty() && RHSVals.empty()) |
677 | return false; |
678 | |
679 | ConstantInt *InterestingVal; |
680 | if (match(V: I, P: m_LogicalOr())) |
681 | InterestingVal = ConstantInt::getTrue(Context&: I->getContext()); |
682 | else |
683 | InterestingVal = ConstantInt::getFalse(Context&: I->getContext()); |
684 | |
685 | SmallPtrSet<BasicBlock*, 4> LHSKnownBBs; |
686 | |
687 | // Scan for the sentinel. If we find an undef, force it to the |
688 | // interesting value: x|undef -> true and x&undef -> false. |
689 | for (const auto &LHSVal : LHSVals) |
690 | if (LHSVal.first == InterestingVal || isa<UndefValue>(Val: LHSVal.first)) { |
691 | Result.emplace_back(Args&: InterestingVal, Args: LHSVal.second); |
692 | LHSKnownBBs.insert(Ptr: LHSVal.second); |
693 | } |
694 | for (const auto &RHSVal : RHSVals) |
695 | if (RHSVal.first == InterestingVal || isa<UndefValue>(Val: RHSVal.first)) { |
696 | // If we already inferred a value for this block on the LHS, don't |
697 | // re-add it. |
698 | if (!LHSKnownBBs.count(Ptr: RHSVal.second)) |
699 | Result.emplace_back(Args&: InterestingVal, Args: RHSVal.second); |
700 | } |
701 | |
702 | return !Result.empty(); |
703 | } |
704 | |
705 | // Handle the NOT form of XOR. |
706 | if (I->getOpcode() == Instruction::Xor && |
707 | isa<ConstantInt>(Val: I->getOperand(i: 1)) && |
708 | cast<ConstantInt>(Val: I->getOperand(i: 1))->isOne()) { |
709 | computeValueKnownInPredecessorsImpl(V: I->getOperand(i: 0), BB, Result, |
710 | Preference: WantInteger, RecursionSet, CxtI); |
711 | if (Result.empty()) |
712 | return false; |
713 | |
714 | // Invert the known values. |
715 | for (auto &R : Result) |
716 | R.first = ConstantExpr::getNot(C: R.first); |
717 | |
718 | return true; |
719 | } |
720 | |
721 | // Try to simplify some other binary operator values. |
722 | } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: I)) { |
723 | if (Preference != WantInteger) |
724 | return false; |
725 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: BO->getOperand(i_nocapture: 1))) { |
726 | PredValueInfoTy LHSVals; |
727 | computeValueKnownInPredecessorsImpl(V: BO->getOperand(i_nocapture: 0), BB, Result&: LHSVals, |
728 | Preference: WantInteger, RecursionSet, CxtI); |
729 | |
730 | // Try to use constant folding to simplify the binary operator. |
731 | for (const auto &LHSVal : LHSVals) { |
732 | Constant *V = LHSVal.first; |
733 | Constant *Folded = |
734 | ConstantFoldBinaryOpOperands(Opcode: BO->getOpcode(), LHS: V, RHS: CI, DL); |
735 | |
736 | if (Constant *KC = getKnownConstant(Val: Folded, Preference: WantInteger)) |
737 | Result.emplace_back(Args&: KC, Args: LHSVal.second); |
738 | } |
739 | } |
740 | |
741 | return !Result.empty(); |
742 | } |
743 | |
744 | // Handle compare with phi operand, where the PHI is defined in this block. |
745 | if (CmpInst *Cmp = dyn_cast<CmpInst>(Val: I)) { |
746 | if (Preference != WantInteger) |
747 | return false; |
748 | Type *CmpType = Cmp->getType(); |
749 | Value *CmpLHS = Cmp->getOperand(i_nocapture: 0); |
750 | Value *CmpRHS = Cmp->getOperand(i_nocapture: 1); |
751 | CmpInst::Predicate Pred = Cmp->getPredicate(); |
752 | |
753 | PHINode *PN = dyn_cast<PHINode>(Val: CmpLHS); |
754 | if (!PN) |
755 | PN = dyn_cast<PHINode>(Val: CmpRHS); |
756 | // Do not perform phi translation across a loop header phi, because this |
757 | // may result in comparison of values from two different loop iterations. |
758 | // FIXME: This check is broken if LoopHeaders is not populated. |
759 | if (PN && PN->getParent() == BB && !LoopHeaders.contains(V: BB)) { |
760 | const DataLayout &DL = PN->getModule()->getDataLayout(); |
761 | // We can do this simplification if any comparisons fold to true or false. |
762 | // See if any do. |
763 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
764 | BasicBlock *PredBB = PN->getIncomingBlock(i); |
765 | Value *LHS, *RHS; |
766 | if (PN == CmpLHS) { |
767 | LHS = PN->getIncomingValue(i); |
768 | RHS = CmpRHS->DoPHITranslation(CurBB: BB, PredBB); |
769 | } else { |
770 | LHS = CmpLHS->DoPHITranslation(CurBB: BB, PredBB); |
771 | RHS = PN->getIncomingValue(i); |
772 | } |
773 | Value *Res = simplifyCmpInst(Predicate: Pred, LHS, RHS, Q: {DL}); |
774 | if (!Res) { |
775 | if (!isa<Constant>(Val: RHS)) |
776 | continue; |
777 | |
778 | // getPredicateOnEdge call will make no sense if LHS is defined in BB. |
779 | auto LHSInst = dyn_cast<Instruction>(Val: LHS); |
780 | if (LHSInst && LHSInst->getParent() == BB) |
781 | continue; |
782 | |
783 | LazyValueInfo::Tristate |
784 | ResT = LVI->getPredicateOnEdge(Pred, V: LHS, |
785 | C: cast<Constant>(Val: RHS), FromBB: PredBB, ToBB: BB, |
786 | CxtI: CxtI ? CxtI : Cmp); |
787 | if (ResT == LazyValueInfo::Unknown) |
788 | continue; |
789 | Res = ConstantInt::get(Ty: Type::getInt1Ty(C&: LHS->getContext()), V: ResT); |
790 | } |
791 | |
792 | if (Constant *KC = getKnownConstant(Val: Res, Preference: WantInteger)) |
793 | Result.emplace_back(Args&: KC, Args&: PredBB); |
794 | } |
795 | |
796 | return !Result.empty(); |
797 | } |
798 | |
799 | // If comparing a live-in value against a constant, see if we know the |
800 | // live-in value on any predecessors. |
801 | if (isa<Constant>(Val: CmpRHS) && !CmpType->isVectorTy()) { |
802 | Constant *CmpConst = cast<Constant>(Val: CmpRHS); |
803 | |
804 | if (!isa<Instruction>(Val: CmpLHS) || |
805 | cast<Instruction>(Val: CmpLHS)->getParent() != BB) { |
806 | for (BasicBlock *P : predecessors(BB)) { |
807 | // If the value is known by LazyValueInfo to be a constant in a |
808 | // predecessor, use that information to try to thread this block. |
809 | LazyValueInfo::Tristate Res = |
810 | LVI->getPredicateOnEdge(Pred, V: CmpLHS, |
811 | C: CmpConst, FromBB: P, ToBB: BB, CxtI: CxtI ? CxtI : Cmp); |
812 | if (Res == LazyValueInfo::Unknown) |
813 | continue; |
814 | |
815 | Constant *ResC = ConstantInt::get(Ty: CmpType, V: Res); |
816 | Result.emplace_back(Args&: ResC, Args&: P); |
817 | } |
818 | |
819 | return !Result.empty(); |
820 | } |
821 | |
822 | // InstCombine can fold some forms of constant range checks into |
823 | // (icmp (add (x, C1)), C2). See if we have we have such a thing with |
824 | // x as a live-in. |
825 | { |
826 | using namespace PatternMatch; |
827 | |
828 | Value *AddLHS; |
829 | ConstantInt *AddConst; |
830 | if (isa<ConstantInt>(Val: CmpConst) && |
831 | match(V: CmpLHS, P: m_Add(L: m_Value(V&: AddLHS), R: m_ConstantInt(CI&: AddConst)))) { |
832 | if (!isa<Instruction>(Val: AddLHS) || |
833 | cast<Instruction>(Val: AddLHS)->getParent() != BB) { |
834 | for (BasicBlock *P : predecessors(BB)) { |
835 | // If the value is known by LazyValueInfo to be a ConstantRange in |
836 | // a predecessor, use that information to try to thread this |
837 | // block. |
838 | ConstantRange CR = LVI->getConstantRangeOnEdge( |
839 | V: AddLHS, FromBB: P, ToBB: BB, CxtI: CxtI ? CxtI : cast<Instruction>(Val: CmpLHS)); |
840 | // Propagate the range through the addition. |
841 | CR = CR.add(Other: AddConst->getValue()); |
842 | |
843 | // Get the range where the compare returns true. |
844 | ConstantRange CmpRange = ConstantRange::makeExactICmpRegion( |
845 | Pred, Other: cast<ConstantInt>(Val: CmpConst)->getValue()); |
846 | |
847 | Constant *ResC; |
848 | if (CmpRange.contains(CR)) |
849 | ResC = ConstantInt::getTrue(Ty: CmpType); |
850 | else if (CmpRange.inverse().contains(CR)) |
851 | ResC = ConstantInt::getFalse(Ty: CmpType); |
852 | else |
853 | continue; |
854 | |
855 | Result.emplace_back(Args&: ResC, Args&: P); |
856 | } |
857 | |
858 | return !Result.empty(); |
859 | } |
860 | } |
861 | } |
862 | |
863 | // Try to find a constant value for the LHS of a comparison, |
864 | // and evaluate it statically if we can. |
865 | PredValueInfoTy LHSVals; |
866 | computeValueKnownInPredecessorsImpl(V: I->getOperand(i: 0), BB, Result&: LHSVals, |
867 | Preference: WantInteger, RecursionSet, CxtI); |
868 | |
869 | for (const auto &LHSVal : LHSVals) { |
870 | Constant *V = LHSVal.first; |
871 | Constant *Folded = ConstantExpr::getCompare(pred: Pred, C1: V, C2: CmpConst); |
872 | if (Constant *KC = getKnownConstant(Val: Folded, Preference: WantInteger)) |
873 | Result.emplace_back(Args&: KC, Args: LHSVal.second); |
874 | } |
875 | |
876 | return !Result.empty(); |
877 | } |
878 | } |
879 | |
880 | if (SelectInst *SI = dyn_cast<SelectInst>(Val: I)) { |
881 | // Handle select instructions where at least one operand is a known constant |
882 | // and we can figure out the condition value for any predecessor block. |
883 | Constant *TrueVal = getKnownConstant(Val: SI->getTrueValue(), Preference); |
884 | Constant *FalseVal = getKnownConstant(Val: SI->getFalseValue(), Preference); |
885 | PredValueInfoTy Conds; |
886 | if ((TrueVal || FalseVal) && |
887 | computeValueKnownInPredecessorsImpl(V: SI->getCondition(), BB, Result&: Conds, |
888 | Preference: WantInteger, RecursionSet, CxtI)) { |
889 | for (auto &C : Conds) { |
890 | Constant *Cond = C.first; |
891 | |
892 | // Figure out what value to use for the condition. |
893 | bool KnownCond; |
894 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Cond)) { |
895 | // A known boolean. |
896 | KnownCond = CI->isOne(); |
897 | } else { |
898 | assert(isa<UndefValue>(Cond) && "Unexpected condition value" ); |
899 | // Either operand will do, so be sure to pick the one that's a known |
900 | // constant. |
901 | // FIXME: Do this more cleverly if both values are known constants? |
902 | KnownCond = (TrueVal != nullptr); |
903 | } |
904 | |
905 | // See if the select has a known constant value for this predecessor. |
906 | if (Constant *Val = KnownCond ? TrueVal : FalseVal) |
907 | Result.emplace_back(Args&: Val, Args&: C.second); |
908 | } |
909 | |
910 | return !Result.empty(); |
911 | } |
912 | } |
913 | |
914 | // If all else fails, see if LVI can figure out a constant value for us. |
915 | assert(CxtI->getParent() == BB && "CxtI should be in BB" ); |
916 | Constant *CI = LVI->getConstant(V, CxtI); |
917 | if (Constant *KC = getKnownConstant(Val: CI, Preference)) { |
918 | for (BasicBlock *Pred : predecessors(BB)) |
919 | Result.emplace_back(Args&: KC, Args&: Pred); |
920 | } |
921 | |
922 | return !Result.empty(); |
923 | } |
924 | |
925 | /// GetBestDestForBranchOnUndef - If we determine that the specified block ends |
926 | /// in an undefined jump, decide which block is best to revector to. |
927 | /// |
928 | /// Since we can pick an arbitrary destination, we pick the successor with the |
929 | /// fewest predecessors. This should reduce the in-degree of the others. |
930 | static unsigned getBestDestForJumpOnUndef(BasicBlock *BB) { |
931 | Instruction *BBTerm = BB->getTerminator(); |
932 | unsigned MinSucc = 0; |
933 | BasicBlock *TestBB = BBTerm->getSuccessor(Idx: MinSucc); |
934 | // Compute the successor with the minimum number of predecessors. |
935 | unsigned MinNumPreds = pred_size(BB: TestBB); |
936 | for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) { |
937 | TestBB = BBTerm->getSuccessor(Idx: i); |
938 | unsigned NumPreds = pred_size(BB: TestBB); |
939 | if (NumPreds < MinNumPreds) { |
940 | MinSucc = i; |
941 | MinNumPreds = NumPreds; |
942 | } |
943 | } |
944 | |
945 | return MinSucc; |
946 | } |
947 | |
948 | static bool hasAddressTakenAndUsed(BasicBlock *BB) { |
949 | if (!BB->hasAddressTaken()) return false; |
950 | |
951 | // If the block has its address taken, it may be a tree of dead constants |
952 | // hanging off of it. These shouldn't keep the block alive. |
953 | BlockAddress *BA = BlockAddress::get(BB); |
954 | BA->removeDeadConstantUsers(); |
955 | return !BA->use_empty(); |
956 | } |
957 | |
958 | /// processBlock - If there are any predecessors whose control can be threaded |
959 | /// through to a successor, transform them now. |
960 | bool JumpThreadingPass::processBlock(BasicBlock *BB) { |
961 | // If the block is trivially dead, just return and let the caller nuke it. |
962 | // This simplifies other transformations. |
963 | if (DTU->isBBPendingDeletion(DelBB: BB) || |
964 | (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock())) |
965 | return false; |
966 | |
967 | // If this block has a single predecessor, and if that pred has a single |
968 | // successor, merge the blocks. This encourages recursive jump threading |
969 | // because now the condition in this block can be threaded through |
970 | // predecessors of our predecessor block. |
971 | if (maybeMergeBasicBlockIntoOnlyPred(BB)) |
972 | return true; |
973 | |
974 | if (tryToUnfoldSelectInCurrBB(BB)) |
975 | return true; |
976 | |
977 | // Look if we can propagate guards to predecessors. |
978 | if (HasGuards && processGuards(BB)) |
979 | return true; |
980 | |
981 | // What kind of constant we're looking for. |
982 | ConstantPreference Preference = WantInteger; |
983 | |
984 | // Look to see if the terminator is a conditional branch, switch or indirect |
985 | // branch, if not we can't thread it. |
986 | Value *Condition; |
987 | Instruction *Terminator = BB->getTerminator(); |
988 | if (BranchInst *BI = dyn_cast<BranchInst>(Val: Terminator)) { |
989 | // Can't thread an unconditional jump. |
990 | if (BI->isUnconditional()) return false; |
991 | Condition = BI->getCondition(); |
992 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: Terminator)) { |
993 | Condition = SI->getCondition(); |
994 | } else if (IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Val: Terminator)) { |
995 | // Can't thread indirect branch with no successors. |
996 | if (IB->getNumSuccessors() == 0) return false; |
997 | Condition = IB->getAddress()->stripPointerCasts(); |
998 | Preference = WantBlockAddress; |
999 | } else { |
1000 | return false; // Must be an invoke or callbr. |
1001 | } |
1002 | |
1003 | // Keep track if we constant folded the condition in this invocation. |
1004 | bool ConstantFolded = false; |
1005 | |
1006 | // Run constant folding to see if we can reduce the condition to a simple |
1007 | // constant. |
1008 | if (Instruction *I = dyn_cast<Instruction>(Val: Condition)) { |
1009 | Value *SimpleVal = |
1010 | ConstantFoldInstruction(I, DL: BB->getModule()->getDataLayout(), TLI); |
1011 | if (SimpleVal) { |
1012 | I->replaceAllUsesWith(V: SimpleVal); |
1013 | if (isInstructionTriviallyDead(I, TLI)) |
1014 | I->eraseFromParent(); |
1015 | Condition = SimpleVal; |
1016 | ConstantFolded = true; |
1017 | } |
1018 | } |
1019 | |
1020 | // If the terminator is branching on an undef or freeze undef, we can pick any |
1021 | // of the successors to branch to. Let getBestDestForJumpOnUndef decide. |
1022 | auto *FI = dyn_cast<FreezeInst>(Val: Condition); |
1023 | if (isa<UndefValue>(Val: Condition) || |
1024 | (FI && isa<UndefValue>(Val: FI->getOperand(i_nocapture: 0)) && FI->hasOneUse())) { |
1025 | unsigned BestSucc = getBestDestForJumpOnUndef(BB); |
1026 | std::vector<DominatorTree::UpdateType> Updates; |
1027 | |
1028 | // Fold the branch/switch. |
1029 | Instruction *BBTerm = BB->getTerminator(); |
1030 | Updates.reserve(n: BBTerm->getNumSuccessors()); |
1031 | for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) { |
1032 | if (i == BestSucc) continue; |
1033 | BasicBlock *Succ = BBTerm->getSuccessor(Idx: i); |
1034 | Succ->removePredecessor(Pred: BB, KeepOneInputPHIs: true); |
1035 | Updates.push_back(x: {DominatorTree::Delete, BB, Succ}); |
1036 | } |
1037 | |
1038 | LLVM_DEBUG(dbgs() << " In block '" << BB->getName() |
1039 | << "' folding undef terminator: " << *BBTerm << '\n'); |
1040 | BranchInst::Create(IfTrue: BBTerm->getSuccessor(Idx: BestSucc), InsertBefore: BBTerm->getIterator()); |
1041 | ++NumFolds; |
1042 | BBTerm->eraseFromParent(); |
1043 | DTU->applyUpdatesPermissive(Updates); |
1044 | if (FI) |
1045 | FI->eraseFromParent(); |
1046 | return true; |
1047 | } |
1048 | |
1049 | // If the terminator of this block is branching on a constant, simplify the |
1050 | // terminator to an unconditional branch. This can occur due to threading in |
1051 | // other blocks. |
1052 | if (getKnownConstant(Val: Condition, Preference)) { |
1053 | LLVM_DEBUG(dbgs() << " In block '" << BB->getName() |
1054 | << "' folding terminator: " << *BB->getTerminator() |
1055 | << '\n'); |
1056 | ++NumFolds; |
1057 | ConstantFoldTerminator(BB, DeleteDeadConditions: true, TLI: nullptr, DTU: DTU.get()); |
1058 | if (auto *BPI = getBPI()) |
1059 | BPI->eraseBlock(BB); |
1060 | return true; |
1061 | } |
1062 | |
1063 | Instruction *CondInst = dyn_cast<Instruction>(Val: Condition); |
1064 | |
1065 | // All the rest of our checks depend on the condition being an instruction. |
1066 | if (!CondInst) { |
1067 | // FIXME: Unify this with code below. |
1068 | if (processThreadableEdges(Cond: Condition, BB, Preference, CxtI: Terminator)) |
1069 | return true; |
1070 | return ConstantFolded; |
1071 | } |
1072 | |
1073 | // Some of the following optimization can safely work on the unfrozen cond. |
1074 | Value *CondWithoutFreeze = CondInst; |
1075 | if (auto *FI = dyn_cast<FreezeInst>(Val: CondInst)) |
1076 | CondWithoutFreeze = FI->getOperand(i_nocapture: 0); |
1077 | |
1078 | if (CmpInst *CondCmp = dyn_cast<CmpInst>(Val: CondWithoutFreeze)) { |
1079 | // If we're branching on a conditional, LVI might be able to determine |
1080 | // it's value at the branch instruction. We only handle comparisons |
1081 | // against a constant at this time. |
1082 | if (Constant *CondConst = dyn_cast<Constant>(Val: CondCmp->getOperand(i_nocapture: 1))) { |
1083 | LazyValueInfo::Tristate Ret = |
1084 | LVI->getPredicateAt(Pred: CondCmp->getPredicate(), V: CondCmp->getOperand(i_nocapture: 0), |
1085 | C: CondConst, CxtI: BB->getTerminator(), |
1086 | /*UseBlockValue=*/false); |
1087 | if (Ret != LazyValueInfo::Unknown) { |
1088 | // We can safely replace *some* uses of the CondInst if it has |
1089 | // exactly one value as returned by LVI. RAUW is incorrect in the |
1090 | // presence of guards and assumes, that have the `Cond` as the use. This |
1091 | // is because we use the guards/assume to reason about the `Cond` value |
1092 | // at the end of block, but RAUW unconditionally replaces all uses |
1093 | // including the guards/assumes themselves and the uses before the |
1094 | // guard/assume. |
1095 | auto *CI = Ret == LazyValueInfo::True ? |
1096 | ConstantInt::getTrue(Ty: CondCmp->getType()) : |
1097 | ConstantInt::getFalse(Ty: CondCmp->getType()); |
1098 | if (replaceFoldableUses(Cond: CondCmp, ToVal: CI, KnownAtEndOfBB: BB)) |
1099 | return true; |
1100 | } |
1101 | |
1102 | // We did not manage to simplify this branch, try to see whether |
1103 | // CondCmp depends on a known phi-select pattern. |
1104 | if (tryToUnfoldSelect(CondCmp, BB)) |
1105 | return true; |
1106 | } |
1107 | } |
1108 | |
1109 | if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: BB->getTerminator())) |
1110 | if (tryToUnfoldSelect(SI, BB)) |
1111 | return true; |
1112 | |
1113 | // Check for some cases that are worth simplifying. Right now we want to look |
1114 | // for loads that are used by a switch or by the condition for the branch. If |
1115 | // we see one, check to see if it's partially redundant. If so, insert a PHI |
1116 | // which can then be used to thread the values. |
1117 | Value *SimplifyValue = CondWithoutFreeze; |
1118 | |
1119 | if (CmpInst *CondCmp = dyn_cast<CmpInst>(Val: SimplifyValue)) |
1120 | if (isa<Constant>(Val: CondCmp->getOperand(i_nocapture: 1))) |
1121 | SimplifyValue = CondCmp->getOperand(i_nocapture: 0); |
1122 | |
1123 | // TODO: There are other places where load PRE would be profitable, such as |
1124 | // more complex comparisons. |
1125 | if (LoadInst *LoadI = dyn_cast<LoadInst>(Val: SimplifyValue)) |
1126 | if (simplifyPartiallyRedundantLoad(LI: LoadI)) |
1127 | return true; |
1128 | |
1129 | // Before threading, try to propagate profile data backwards: |
1130 | if (PHINode *PN = dyn_cast<PHINode>(Val: CondInst)) |
1131 | if (PN->getParent() == BB && isa<BranchInst>(Val: BB->getTerminator())) |
1132 | updatePredecessorProfileMetadata(PN, BB); |
1133 | |
1134 | // Handle a variety of cases where we are branching on something derived from |
1135 | // a PHI node in the current block. If we can prove that any predecessors |
1136 | // compute a predictable value based on a PHI node, thread those predecessors. |
1137 | if (processThreadableEdges(Cond: CondInst, BB, Preference, CxtI: Terminator)) |
1138 | return true; |
1139 | |
1140 | // If this is an otherwise-unfoldable branch on a phi node or freeze(phi) in |
1141 | // the current block, see if we can simplify. |
1142 | PHINode *PN = dyn_cast<PHINode>(Val: CondWithoutFreeze); |
1143 | if (PN && PN->getParent() == BB && isa<BranchInst>(Val: BB->getTerminator())) |
1144 | return processBranchOnPHI(PN); |
1145 | |
1146 | // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify. |
1147 | if (CondInst->getOpcode() == Instruction::Xor && |
1148 | CondInst->getParent() == BB && isa<BranchInst>(Val: BB->getTerminator())) |
1149 | return processBranchOnXOR(BO: cast<BinaryOperator>(Val: CondInst)); |
1150 | |
1151 | // Search for a stronger dominating condition that can be used to simplify a |
1152 | // conditional branch leaving BB. |
1153 | if (processImpliedCondition(BB)) |
1154 | return true; |
1155 | |
1156 | return false; |
1157 | } |
1158 | |
1159 | bool JumpThreadingPass::processImpliedCondition(BasicBlock *BB) { |
1160 | auto *BI = dyn_cast<BranchInst>(Val: BB->getTerminator()); |
1161 | if (!BI || !BI->isConditional()) |
1162 | return false; |
1163 | |
1164 | Value *Cond = BI->getCondition(); |
1165 | // Assuming that predecessor's branch was taken, if pred's branch condition |
1166 | // (V) implies Cond, Cond can be either true, undef, or poison. In this case, |
1167 | // freeze(Cond) is either true or a nondeterministic value. |
1168 | // If freeze(Cond) has only one use, we can freely fold freeze(Cond) to true |
1169 | // without affecting other instructions. |
1170 | auto *FICond = dyn_cast<FreezeInst>(Val: Cond); |
1171 | if (FICond && FICond->hasOneUse()) |
1172 | Cond = FICond->getOperand(i_nocapture: 0); |
1173 | else |
1174 | FICond = nullptr; |
1175 | |
1176 | BasicBlock *CurrentBB = BB; |
1177 | BasicBlock *CurrentPred = BB->getSinglePredecessor(); |
1178 | unsigned Iter = 0; |
1179 | |
1180 | auto &DL = BB->getModule()->getDataLayout(); |
1181 | |
1182 | while (CurrentPred && Iter++ < ImplicationSearchThreshold) { |
1183 | auto *PBI = dyn_cast<BranchInst>(Val: CurrentPred->getTerminator()); |
1184 | if (!PBI || !PBI->isConditional()) |
1185 | return false; |
1186 | if (PBI->getSuccessor(i: 0) != CurrentBB && PBI->getSuccessor(i: 1) != CurrentBB) |
1187 | return false; |
1188 | |
1189 | bool CondIsTrue = PBI->getSuccessor(i: 0) == CurrentBB; |
1190 | std::optional<bool> Implication = |
1191 | isImpliedCondition(LHS: PBI->getCondition(), RHS: Cond, DL, LHSIsTrue: CondIsTrue); |
1192 | |
1193 | // If the branch condition of BB (which is Cond) and CurrentPred are |
1194 | // exactly the same freeze instruction, Cond can be folded into CondIsTrue. |
1195 | if (!Implication && FICond && isa<FreezeInst>(Val: PBI->getCondition())) { |
1196 | if (cast<FreezeInst>(Val: PBI->getCondition())->getOperand(i_nocapture: 0) == |
1197 | FICond->getOperand(i_nocapture: 0)) |
1198 | Implication = CondIsTrue; |
1199 | } |
1200 | |
1201 | if (Implication) { |
1202 | BasicBlock *KeepSucc = BI->getSuccessor(i: *Implication ? 0 : 1); |
1203 | BasicBlock *RemoveSucc = BI->getSuccessor(i: *Implication ? 1 : 0); |
1204 | RemoveSucc->removePredecessor(Pred: BB); |
1205 | BranchInst *UncondBI = BranchInst::Create(IfTrue: KeepSucc, InsertBefore: BI->getIterator()); |
1206 | UncondBI->setDebugLoc(BI->getDebugLoc()); |
1207 | ++NumFolds; |
1208 | BI->eraseFromParent(); |
1209 | if (FICond) |
1210 | FICond->eraseFromParent(); |
1211 | |
1212 | DTU->applyUpdatesPermissive(Updates: {{DominatorTree::Delete, BB, RemoveSucc}}); |
1213 | if (auto *BPI = getBPI()) |
1214 | BPI->eraseBlock(BB); |
1215 | return true; |
1216 | } |
1217 | CurrentBB = CurrentPred; |
1218 | CurrentPred = CurrentBB->getSinglePredecessor(); |
1219 | } |
1220 | |
1221 | return false; |
1222 | } |
1223 | |
1224 | /// Return true if Op is an instruction defined in the given block. |
1225 | static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB) { |
1226 | if (Instruction *OpInst = dyn_cast<Instruction>(Val: Op)) |
1227 | if (OpInst->getParent() == BB) |
1228 | return true; |
1229 | return false; |
1230 | } |
1231 | |
1232 | /// simplifyPartiallyRedundantLoad - If LoadI is an obviously partially |
1233 | /// redundant load instruction, eliminate it by replacing it with a PHI node. |
1234 | /// This is an important optimization that encourages jump threading, and needs |
1235 | /// to be run interlaced with other jump threading tasks. |
1236 | bool JumpThreadingPass::simplifyPartiallyRedundantLoad(LoadInst *LoadI) { |
1237 | // Don't hack volatile and ordered loads. |
1238 | if (!LoadI->isUnordered()) return false; |
1239 | |
1240 | // If the load is defined in a block with exactly one predecessor, it can't be |
1241 | // partially redundant. |
1242 | BasicBlock *LoadBB = LoadI->getParent(); |
1243 | if (LoadBB->getSinglePredecessor()) |
1244 | return false; |
1245 | |
1246 | // If the load is defined in an EH pad, it can't be partially redundant, |
1247 | // because the edges between the invoke and the EH pad cannot have other |
1248 | // instructions between them. |
1249 | if (LoadBB->isEHPad()) |
1250 | return false; |
1251 | |
1252 | Value *LoadedPtr = LoadI->getOperand(i_nocapture: 0); |
1253 | |
1254 | // If the loaded operand is defined in the LoadBB and its not a phi, |
1255 | // it can't be available in predecessors. |
1256 | if (isOpDefinedInBlock(Op: LoadedPtr, BB: LoadBB) && !isa<PHINode>(Val: LoadedPtr)) |
1257 | return false; |
1258 | |
1259 | // Scan a few instructions up from the load, to see if it is obviously live at |
1260 | // the entry to its block. |
1261 | BasicBlock::iterator BBIt(LoadI); |
1262 | bool IsLoadCSE; |
1263 | BatchAAResults BatchAA(*AA); |
1264 | // The dominator tree is updated lazily and may not be valid at this point. |
1265 | BatchAA.disableDominatorTree(); |
1266 | if (Value *AvailableVal = FindAvailableLoadedValue( |
1267 | Load: LoadI, ScanBB: LoadBB, ScanFrom&: BBIt, MaxInstsToScan: DefMaxInstsToScan, AA: &BatchAA, IsLoadCSE: &IsLoadCSE)) { |
1268 | // If the value of the load is locally available within the block, just use |
1269 | // it. This frequently occurs for reg2mem'd allocas. |
1270 | |
1271 | if (IsLoadCSE) { |
1272 | LoadInst *NLoadI = cast<LoadInst>(Val: AvailableVal); |
1273 | combineMetadataForCSE(K: NLoadI, J: LoadI, DoesKMove: false); |
1274 | LVI->forgetValue(V: NLoadI); |
1275 | }; |
1276 | |
1277 | // If the returned value is the load itself, replace with poison. This can |
1278 | // only happen in dead loops. |
1279 | if (AvailableVal == LoadI) |
1280 | AvailableVal = PoisonValue::get(T: LoadI->getType()); |
1281 | if (AvailableVal->getType() != LoadI->getType()) |
1282 | AvailableVal = CastInst::CreateBitOrPointerCast( |
1283 | S: AvailableVal, Ty: LoadI->getType(), Name: "" , InsertBefore: LoadI->getIterator()); |
1284 | LoadI->replaceAllUsesWith(V: AvailableVal); |
1285 | LoadI->eraseFromParent(); |
1286 | return true; |
1287 | } |
1288 | |
1289 | // Otherwise, if we scanned the whole block and got to the top of the block, |
1290 | // we know the block is locally transparent to the load. If not, something |
1291 | // might clobber its value. |
1292 | if (BBIt != LoadBB->begin()) |
1293 | return false; |
1294 | |
1295 | // If all of the loads and stores that feed the value have the same AA tags, |
1296 | // then we can propagate them onto any newly inserted loads. |
1297 | AAMDNodes AATags = LoadI->getAAMetadata(); |
1298 | |
1299 | SmallPtrSet<BasicBlock*, 8> PredsScanned; |
1300 | |
1301 | using AvailablePredsTy = SmallVector<std::pair<BasicBlock *, Value *>, 8>; |
1302 | |
1303 | AvailablePredsTy AvailablePreds; |
1304 | BasicBlock *OneUnavailablePred = nullptr; |
1305 | SmallVector<LoadInst*, 8> CSELoads; |
1306 | |
1307 | // If we got here, the loaded value is transparent through to the start of the |
1308 | // block. Check to see if it is available in any of the predecessor blocks. |
1309 | for (BasicBlock *PredBB : predecessors(BB: LoadBB)) { |
1310 | // If we already scanned this predecessor, skip it. |
1311 | if (!PredsScanned.insert(Ptr: PredBB).second) |
1312 | continue; |
1313 | |
1314 | BBIt = PredBB->end(); |
1315 | unsigned NumScanedInst = 0; |
1316 | Value *PredAvailable = nullptr; |
1317 | // NOTE: We don't CSE load that is volatile or anything stronger than |
1318 | // unordered, that should have been checked when we entered the function. |
1319 | assert(LoadI->isUnordered() && |
1320 | "Attempting to CSE volatile or atomic loads" ); |
1321 | // If this is a load on a phi pointer, phi-translate it and search |
1322 | // for available load/store to the pointer in predecessors. |
1323 | Type *AccessTy = LoadI->getType(); |
1324 | const auto &DL = LoadI->getModule()->getDataLayout(); |
1325 | MemoryLocation Loc(LoadedPtr->DoPHITranslation(CurBB: LoadBB, PredBB), |
1326 | LocationSize::precise(Value: DL.getTypeStoreSize(Ty: AccessTy)), |
1327 | AATags); |
1328 | PredAvailable = findAvailablePtrLoadStore( |
1329 | Loc, AccessTy, AtLeastAtomic: LoadI->isAtomic(), ScanBB: PredBB, ScanFrom&: BBIt, MaxInstsToScan: DefMaxInstsToScan, |
1330 | AA: &BatchAA, IsLoadCSE: &IsLoadCSE, NumScanedInst: &NumScanedInst); |
1331 | |
1332 | // If PredBB has a single predecessor, continue scanning through the |
1333 | // single predecessor. |
1334 | BasicBlock *SinglePredBB = PredBB; |
1335 | while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() && |
1336 | NumScanedInst < DefMaxInstsToScan) { |
1337 | SinglePredBB = SinglePredBB->getSinglePredecessor(); |
1338 | if (SinglePredBB) { |
1339 | BBIt = SinglePredBB->end(); |
1340 | PredAvailable = findAvailablePtrLoadStore( |
1341 | Loc, AccessTy, AtLeastAtomic: LoadI->isAtomic(), ScanBB: SinglePredBB, ScanFrom&: BBIt, |
1342 | MaxInstsToScan: (DefMaxInstsToScan - NumScanedInst), AA: &BatchAA, IsLoadCSE: &IsLoadCSE, |
1343 | NumScanedInst: &NumScanedInst); |
1344 | } |
1345 | } |
1346 | |
1347 | if (!PredAvailable) { |
1348 | OneUnavailablePred = PredBB; |
1349 | continue; |
1350 | } |
1351 | |
1352 | if (IsLoadCSE) |
1353 | CSELoads.push_back(Elt: cast<LoadInst>(Val: PredAvailable)); |
1354 | |
1355 | // If so, this load is partially redundant. Remember this info so that we |
1356 | // can create a PHI node. |
1357 | AvailablePreds.emplace_back(Args&: PredBB, Args&: PredAvailable); |
1358 | } |
1359 | |
1360 | // If the loaded value isn't available in any predecessor, it isn't partially |
1361 | // redundant. |
1362 | if (AvailablePreds.empty()) return false; |
1363 | |
1364 | // Okay, the loaded value is available in at least one (and maybe all!) |
1365 | // predecessors. If the value is unavailable in more than one unique |
1366 | // predecessor, we want to insert a merge block for those common predecessors. |
1367 | // This ensures that we only have to insert one reload, thus not increasing |
1368 | // code size. |
1369 | BasicBlock *UnavailablePred = nullptr; |
1370 | |
1371 | // If the value is unavailable in one of predecessors, we will end up |
1372 | // inserting a new instruction into them. It is only valid if all the |
1373 | // instructions before LoadI are guaranteed to pass execution to its |
1374 | // successor, or if LoadI is safe to speculate. |
1375 | // TODO: If this logic becomes more complex, and we will perform PRE insertion |
1376 | // farther than to a predecessor, we need to reuse the code from GVN's PRE. |
1377 | // It requires domination tree analysis, so for this simple case it is an |
1378 | // overkill. |
1379 | if (PredsScanned.size() != AvailablePreds.size() && |
1380 | !isSafeToSpeculativelyExecute(I: LoadI)) |
1381 | for (auto I = LoadBB->begin(); &*I != LoadI; ++I) |
1382 | if (!isGuaranteedToTransferExecutionToSuccessor(I: &*I)) |
1383 | return false; |
1384 | |
1385 | // If there is exactly one predecessor where the value is unavailable, the |
1386 | // already computed 'OneUnavailablePred' block is it. If it ends in an |
1387 | // unconditional branch, we know that it isn't a critical edge. |
1388 | if (PredsScanned.size() == AvailablePreds.size()+1 && |
1389 | OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) { |
1390 | UnavailablePred = OneUnavailablePred; |
1391 | } else if (PredsScanned.size() != AvailablePreds.size()) { |
1392 | // Otherwise, we had multiple unavailable predecessors or we had a critical |
1393 | // edge from the one. |
1394 | SmallVector<BasicBlock*, 8> PredsToSplit; |
1395 | SmallPtrSet<BasicBlock*, 8> AvailablePredSet; |
1396 | |
1397 | for (const auto &AvailablePred : AvailablePreds) |
1398 | AvailablePredSet.insert(Ptr: AvailablePred.first); |
1399 | |
1400 | // Add all the unavailable predecessors to the PredsToSplit list. |
1401 | for (BasicBlock *P : predecessors(BB: LoadBB)) { |
1402 | // If the predecessor is an indirect goto, we can't split the edge. |
1403 | if (isa<IndirectBrInst>(Val: P->getTerminator())) |
1404 | return false; |
1405 | |
1406 | if (!AvailablePredSet.count(Ptr: P)) |
1407 | PredsToSplit.push_back(Elt: P); |
1408 | } |
1409 | |
1410 | // Split them out to their own block. |
1411 | UnavailablePred = splitBlockPreds(BB: LoadBB, Preds: PredsToSplit, Suffix: "thread-pre-split" ); |
1412 | } |
1413 | |
1414 | // If the value isn't available in all predecessors, then there will be |
1415 | // exactly one where it isn't available. Insert a load on that edge and add |
1416 | // it to the AvailablePreds list. |
1417 | if (UnavailablePred) { |
1418 | assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 && |
1419 | "Can't handle critical edge here!" ); |
1420 | LoadInst *NewVal = new LoadInst( |
1421 | LoadI->getType(), LoadedPtr->DoPHITranslation(CurBB: LoadBB, PredBB: UnavailablePred), |
1422 | LoadI->getName() + ".pr" , false, LoadI->getAlign(), |
1423 | LoadI->getOrdering(), LoadI->getSyncScopeID(), |
1424 | UnavailablePred->getTerminator()->getIterator()); |
1425 | NewVal->setDebugLoc(LoadI->getDebugLoc()); |
1426 | if (AATags) |
1427 | NewVal->setAAMetadata(AATags); |
1428 | |
1429 | AvailablePreds.emplace_back(Args&: UnavailablePred, Args&: NewVal); |
1430 | } |
1431 | |
1432 | // Now we know that each predecessor of this block has a value in |
1433 | // AvailablePreds, sort them for efficient access as we're walking the preds. |
1434 | array_pod_sort(Start: AvailablePreds.begin(), End: AvailablePreds.end()); |
1435 | |
1436 | // Create a PHI node at the start of the block for the PRE'd load value. |
1437 | PHINode *PN = PHINode::Create(Ty: LoadI->getType(), NumReservedValues: pred_size(BB: LoadBB), NameStr: "" ); |
1438 | PN->insertBefore(InsertPos: LoadBB->begin()); |
1439 | PN->takeName(V: LoadI); |
1440 | PN->setDebugLoc(LoadI->getDebugLoc()); |
1441 | |
1442 | // Insert new entries into the PHI for each predecessor. A single block may |
1443 | // have multiple entries here. |
1444 | for (BasicBlock *P : predecessors(BB: LoadBB)) { |
1445 | AvailablePredsTy::iterator I = |
1446 | llvm::lower_bound(Range&: AvailablePreds, Value: std::make_pair(x&: P, y: (Value *)nullptr)); |
1447 | |
1448 | assert(I != AvailablePreds.end() && I->first == P && |
1449 | "Didn't find entry for predecessor!" ); |
1450 | |
1451 | // If we have an available predecessor but it requires casting, insert the |
1452 | // cast in the predecessor and use the cast. Note that we have to update the |
1453 | // AvailablePreds vector as we go so that all of the PHI entries for this |
1454 | // predecessor use the same bitcast. |
1455 | Value *&PredV = I->second; |
1456 | if (PredV->getType() != LoadI->getType()) |
1457 | PredV = CastInst::CreateBitOrPointerCast( |
1458 | S: PredV, Ty: LoadI->getType(), Name: "" , InsertBefore: P->getTerminator()->getIterator()); |
1459 | |
1460 | PN->addIncoming(V: PredV, BB: I->first); |
1461 | } |
1462 | |
1463 | for (LoadInst *PredLoadI : CSELoads) { |
1464 | combineMetadataForCSE(K: PredLoadI, J: LoadI, DoesKMove: true); |
1465 | LVI->forgetValue(V: PredLoadI); |
1466 | } |
1467 | |
1468 | LoadI->replaceAllUsesWith(V: PN); |
1469 | LoadI->eraseFromParent(); |
1470 | |
1471 | return true; |
1472 | } |
1473 | |
1474 | /// findMostPopularDest - The specified list contains multiple possible |
1475 | /// threadable destinations. Pick the one that occurs the most frequently in |
1476 | /// the list. |
1477 | static BasicBlock * |
1478 | findMostPopularDest(BasicBlock *BB, |
1479 | const SmallVectorImpl<std::pair<BasicBlock *, |
1480 | BasicBlock *>> &PredToDestList) { |
1481 | assert(!PredToDestList.empty()); |
1482 | |
1483 | // Determine popularity. If there are multiple possible destinations, we |
1484 | // explicitly choose to ignore 'undef' destinations. We prefer to thread |
1485 | // blocks with known and real destinations to threading undef. We'll handle |
1486 | // them later if interesting. |
1487 | MapVector<BasicBlock *, unsigned> DestPopularity; |
1488 | |
1489 | // Populate DestPopularity with the successors in the order they appear in the |
1490 | // successor list. This way, we ensure determinism by iterating it in the |
1491 | // same order in llvm::max_element below. We map nullptr to 0 so that we can |
1492 | // return nullptr when PredToDestList contains nullptr only. |
1493 | DestPopularity[nullptr] = 0; |
1494 | for (auto *SuccBB : successors(BB)) |
1495 | DestPopularity[SuccBB] = 0; |
1496 | |
1497 | for (const auto &PredToDest : PredToDestList) |
1498 | if (PredToDest.second) |
1499 | DestPopularity[PredToDest.second]++; |
1500 | |
1501 | // Find the most popular dest. |
1502 | auto MostPopular = llvm::max_element(Range&: DestPopularity, C: llvm::less_second()); |
1503 | |
1504 | // Okay, we have finally picked the most popular destination. |
1505 | return MostPopular->first; |
1506 | } |
1507 | |
1508 | // Try to evaluate the value of V when the control flows from PredPredBB to |
1509 | // BB->getSinglePredecessor() and then on to BB. |
1510 | Constant *JumpThreadingPass::evaluateOnPredecessorEdge(BasicBlock *BB, |
1511 | BasicBlock *PredPredBB, |
1512 | Value *V) { |
1513 | BasicBlock *PredBB = BB->getSinglePredecessor(); |
1514 | assert(PredBB && "Expected a single predecessor" ); |
1515 | |
1516 | if (Constant *Cst = dyn_cast<Constant>(Val: V)) { |
1517 | return Cst; |
1518 | } |
1519 | |
1520 | // Consult LVI if V is not an instruction in BB or PredBB. |
1521 | Instruction *I = dyn_cast<Instruction>(Val: V); |
1522 | if (!I || (I->getParent() != BB && I->getParent() != PredBB)) { |
1523 | return LVI->getConstantOnEdge(V, FromBB: PredPredBB, ToBB: PredBB, CxtI: nullptr); |
1524 | } |
1525 | |
1526 | // Look into a PHI argument. |
1527 | if (PHINode *PHI = dyn_cast<PHINode>(Val: V)) { |
1528 | if (PHI->getParent() == PredBB) |
1529 | return dyn_cast<Constant>(Val: PHI->getIncomingValueForBlock(BB: PredPredBB)); |
1530 | return nullptr; |
1531 | } |
1532 | |
1533 | // If we have a CmpInst, try to fold it for each incoming edge into PredBB. |
1534 | if (CmpInst *CondCmp = dyn_cast<CmpInst>(Val: V)) { |
1535 | if (CondCmp->getParent() == BB) { |
1536 | Constant *Op0 = |
1537 | evaluateOnPredecessorEdge(BB, PredPredBB, V: CondCmp->getOperand(i_nocapture: 0)); |
1538 | Constant *Op1 = |
1539 | evaluateOnPredecessorEdge(BB, PredPredBB, V: CondCmp->getOperand(i_nocapture: 1)); |
1540 | if (Op0 && Op1) { |
1541 | return ConstantExpr::getCompare(pred: CondCmp->getPredicate(), C1: Op0, C2: Op1); |
1542 | } |
1543 | } |
1544 | return nullptr; |
1545 | } |
1546 | |
1547 | return nullptr; |
1548 | } |
1549 | |
1550 | bool JumpThreadingPass::processThreadableEdges(Value *Cond, BasicBlock *BB, |
1551 | ConstantPreference Preference, |
1552 | Instruction *CxtI) { |
1553 | // If threading this would thread across a loop header, don't even try to |
1554 | // thread the edge. |
1555 | if (LoopHeaders.count(V: BB)) |
1556 | return false; |
1557 | |
1558 | PredValueInfoTy PredValues; |
1559 | if (!computeValueKnownInPredecessors(V: Cond, BB, Result&: PredValues, Preference, |
1560 | CxtI)) { |
1561 | // We don't have known values in predecessors. See if we can thread through |
1562 | // BB and its sole predecessor. |
1563 | return maybethreadThroughTwoBasicBlocks(BB, Cond); |
1564 | } |
1565 | |
1566 | assert(!PredValues.empty() && |
1567 | "computeValueKnownInPredecessors returned true with no values" ); |
1568 | |
1569 | LLVM_DEBUG(dbgs() << "IN BB: " << *BB; |
1570 | for (const auto &PredValue : PredValues) { |
1571 | dbgs() << " BB '" << BB->getName() |
1572 | << "': FOUND condition = " << *PredValue.first |
1573 | << " for pred '" << PredValue.second->getName() << "'.\n" ; |
1574 | }); |
1575 | |
1576 | // Decide what we want to thread through. Convert our list of known values to |
1577 | // a list of known destinations for each pred. This also discards duplicate |
1578 | // predecessors and keeps track of the undefined inputs (which are represented |
1579 | // as a null dest in the PredToDestList). |
1580 | SmallPtrSet<BasicBlock*, 16> SeenPreds; |
1581 | SmallVector<std::pair<BasicBlock*, BasicBlock*>, 16> PredToDestList; |
1582 | |
1583 | BasicBlock *OnlyDest = nullptr; |
1584 | BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL; |
1585 | Constant *OnlyVal = nullptr; |
1586 | Constant *MultipleVal = (Constant *)(intptr_t)~0ULL; |
1587 | |
1588 | for (const auto &PredValue : PredValues) { |
1589 | BasicBlock *Pred = PredValue.second; |
1590 | if (!SeenPreds.insert(Ptr: Pred).second) |
1591 | continue; // Duplicate predecessor entry. |
1592 | |
1593 | Constant *Val = PredValue.first; |
1594 | |
1595 | BasicBlock *DestBB; |
1596 | if (isa<UndefValue>(Val)) |
1597 | DestBB = nullptr; |
1598 | else if (BranchInst *BI = dyn_cast<BranchInst>(Val: BB->getTerminator())) { |
1599 | assert(isa<ConstantInt>(Val) && "Expecting a constant integer" ); |
1600 | DestBB = BI->getSuccessor(i: cast<ConstantInt>(Val)->isZero()); |
1601 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: BB->getTerminator())) { |
1602 | assert(isa<ConstantInt>(Val) && "Expecting a constant integer" ); |
1603 | DestBB = SI->findCaseValue(C: cast<ConstantInt>(Val))->getCaseSuccessor(); |
1604 | } else { |
1605 | assert(isa<IndirectBrInst>(BB->getTerminator()) |
1606 | && "Unexpected terminator" ); |
1607 | assert(isa<BlockAddress>(Val) && "Expecting a constant blockaddress" ); |
1608 | DestBB = cast<BlockAddress>(Val)->getBasicBlock(); |
1609 | } |
1610 | |
1611 | // If we have exactly one destination, remember it for efficiency below. |
1612 | if (PredToDestList.empty()) { |
1613 | OnlyDest = DestBB; |
1614 | OnlyVal = Val; |
1615 | } else { |
1616 | if (OnlyDest != DestBB) |
1617 | OnlyDest = MultipleDestSentinel; |
1618 | // It possible we have same destination, but different value, e.g. default |
1619 | // case in switchinst. |
1620 | if (Val != OnlyVal) |
1621 | OnlyVal = MultipleVal; |
1622 | } |
1623 | |
1624 | // If the predecessor ends with an indirect goto, we can't change its |
1625 | // destination. |
1626 | if (isa<IndirectBrInst>(Val: Pred->getTerminator())) |
1627 | continue; |
1628 | |
1629 | PredToDestList.emplace_back(Args&: Pred, Args&: DestBB); |
1630 | } |
1631 | |
1632 | // If all edges were unthreadable, we fail. |
1633 | if (PredToDestList.empty()) |
1634 | return false; |
1635 | |
1636 | // If all the predecessors go to a single known successor, we want to fold, |
1637 | // not thread. By doing so, we do not need to duplicate the current block and |
1638 | // also miss potential opportunities in case we dont/cant duplicate. |
1639 | if (OnlyDest && OnlyDest != MultipleDestSentinel) { |
1640 | if (BB->hasNPredecessors(N: PredToDestList.size())) { |
1641 | bool SeenFirstBranchToOnlyDest = false; |
1642 | std::vector <DominatorTree::UpdateType> Updates; |
1643 | Updates.reserve(n: BB->getTerminator()->getNumSuccessors() - 1); |
1644 | for (BasicBlock *SuccBB : successors(BB)) { |
1645 | if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) { |
1646 | SeenFirstBranchToOnlyDest = true; // Don't modify the first branch. |
1647 | } else { |
1648 | SuccBB->removePredecessor(Pred: BB, KeepOneInputPHIs: true); // This is unreachable successor. |
1649 | Updates.push_back(x: {DominatorTree::Delete, BB, SuccBB}); |
1650 | } |
1651 | } |
1652 | |
1653 | // Finally update the terminator. |
1654 | Instruction *Term = BB->getTerminator(); |
1655 | BranchInst::Create(IfTrue: OnlyDest, InsertBefore: Term->getIterator()); |
1656 | ++NumFolds; |
1657 | Term->eraseFromParent(); |
1658 | DTU->applyUpdatesPermissive(Updates); |
1659 | if (auto *BPI = getBPI()) |
1660 | BPI->eraseBlock(BB); |
1661 | |
1662 | // If the condition is now dead due to the removal of the old terminator, |
1663 | // erase it. |
1664 | if (auto *CondInst = dyn_cast<Instruction>(Val: Cond)) { |
1665 | if (CondInst->use_empty() && !CondInst->mayHaveSideEffects()) |
1666 | CondInst->eraseFromParent(); |
1667 | // We can safely replace *some* uses of the CondInst if it has |
1668 | // exactly one value as returned by LVI. RAUW is incorrect in the |
1669 | // presence of guards and assumes, that have the `Cond` as the use. This |
1670 | // is because we use the guards/assume to reason about the `Cond` value |
1671 | // at the end of block, but RAUW unconditionally replaces all uses |
1672 | // including the guards/assumes themselves and the uses before the |
1673 | // guard/assume. |
1674 | else if (OnlyVal && OnlyVal != MultipleVal) |
1675 | replaceFoldableUses(Cond: CondInst, ToVal: OnlyVal, KnownAtEndOfBB: BB); |
1676 | } |
1677 | return true; |
1678 | } |
1679 | } |
1680 | |
1681 | // Determine which is the most common successor. If we have many inputs and |
1682 | // this block is a switch, we want to start by threading the batch that goes |
1683 | // to the most popular destination first. If we only know about one |
1684 | // threadable destination (the common case) we can avoid this. |
1685 | BasicBlock *MostPopularDest = OnlyDest; |
1686 | |
1687 | if (MostPopularDest == MultipleDestSentinel) { |
1688 | // Remove any loop headers from the Dest list, threadEdge conservatively |
1689 | // won't process them, but we might have other destination that are eligible |
1690 | // and we still want to process. |
1691 | erase_if(C&: PredToDestList, |
1692 | P: [&](const std::pair<BasicBlock *, BasicBlock *> &PredToDest) { |
1693 | return LoopHeaders.contains(V: PredToDest.second); |
1694 | }); |
1695 | |
1696 | if (PredToDestList.empty()) |
1697 | return false; |
1698 | |
1699 | MostPopularDest = findMostPopularDest(BB, PredToDestList); |
1700 | } |
1701 | |
1702 | // Now that we know what the most popular destination is, factor all |
1703 | // predecessors that will jump to it into a single predecessor. |
1704 | SmallVector<BasicBlock*, 16> PredsToFactor; |
1705 | for (const auto &PredToDest : PredToDestList) |
1706 | if (PredToDest.second == MostPopularDest) { |
1707 | BasicBlock *Pred = PredToDest.first; |
1708 | |
1709 | // This predecessor may be a switch or something else that has multiple |
1710 | // edges to the block. Factor each of these edges by listing them |
1711 | // according to # occurrences in PredsToFactor. |
1712 | for (BasicBlock *Succ : successors(BB: Pred)) |
1713 | if (Succ == BB) |
1714 | PredsToFactor.push_back(Elt: Pred); |
1715 | } |
1716 | |
1717 | // If the threadable edges are branching on an undefined value, we get to pick |
1718 | // the destination that these predecessors should get to. |
1719 | if (!MostPopularDest) |
1720 | MostPopularDest = BB->getTerminator()-> |
1721 | getSuccessor(Idx: getBestDestForJumpOnUndef(BB)); |
1722 | |
1723 | // Ok, try to thread it! |
1724 | return tryThreadEdge(BB, PredBBs: PredsToFactor, SuccBB: MostPopularDest); |
1725 | } |
1726 | |
1727 | /// processBranchOnPHI - We have an otherwise unthreadable conditional branch on |
1728 | /// a PHI node (or freeze PHI) in the current block. See if there are any |
1729 | /// simplifications we can do based on inputs to the phi node. |
1730 | bool JumpThreadingPass::processBranchOnPHI(PHINode *PN) { |
1731 | BasicBlock *BB = PN->getParent(); |
1732 | |
1733 | // TODO: We could make use of this to do it once for blocks with common PHI |
1734 | // values. |
1735 | SmallVector<BasicBlock*, 1> PredBBs; |
1736 | PredBBs.resize(N: 1); |
1737 | |
1738 | // If any of the predecessor blocks end in an unconditional branch, we can |
1739 | // *duplicate* the conditional branch into that block in order to further |
1740 | // encourage jump threading and to eliminate cases where we have branch on a |
1741 | // phi of an icmp (branch on icmp is much better). |
1742 | // This is still beneficial when a frozen phi is used as the branch condition |
1743 | // because it allows CodeGenPrepare to further canonicalize br(freeze(icmp)) |
1744 | // to br(icmp(freeze ...)). |
1745 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
1746 | BasicBlock *PredBB = PN->getIncomingBlock(i); |
1747 | if (BranchInst *PredBr = dyn_cast<BranchInst>(Val: PredBB->getTerminator())) |
1748 | if (PredBr->isUnconditional()) { |
1749 | PredBBs[0] = PredBB; |
1750 | // Try to duplicate BB into PredBB. |
1751 | if (duplicateCondBranchOnPHIIntoPred(BB, PredBBs)) |
1752 | return true; |
1753 | } |
1754 | } |
1755 | |
1756 | return false; |
1757 | } |
1758 | |
1759 | /// processBranchOnXOR - We have an otherwise unthreadable conditional branch on |
1760 | /// a xor instruction in the current block. See if there are any |
1761 | /// simplifications we can do based on inputs to the xor. |
1762 | bool JumpThreadingPass::processBranchOnXOR(BinaryOperator *BO) { |
1763 | BasicBlock *BB = BO->getParent(); |
1764 | |
1765 | // If either the LHS or RHS of the xor is a constant, don't do this |
1766 | // optimization. |
1767 | if (isa<ConstantInt>(Val: BO->getOperand(i_nocapture: 0)) || |
1768 | isa<ConstantInt>(Val: BO->getOperand(i_nocapture: 1))) |
1769 | return false; |
1770 | |
1771 | // If the first instruction in BB isn't a phi, we won't be able to infer |
1772 | // anything special about any particular predecessor. |
1773 | if (!isa<PHINode>(Val: BB->front())) |
1774 | return false; |
1775 | |
1776 | // If this BB is a landing pad, we won't be able to split the edge into it. |
1777 | if (BB->isEHPad()) |
1778 | return false; |
1779 | |
1780 | // If we have a xor as the branch input to this block, and we know that the |
1781 | // LHS or RHS of the xor in any predecessor is true/false, then we can clone |
1782 | // the condition into the predecessor and fix that value to true, saving some |
1783 | // logical ops on that path and encouraging other paths to simplify. |
1784 | // |
1785 | // This copies something like this: |
1786 | // |
1787 | // BB: |
1788 | // %X = phi i1 [1], [%X'] |
1789 | // %Y = icmp eq i32 %A, %B |
1790 | // %Z = xor i1 %X, %Y |
1791 | // br i1 %Z, ... |
1792 | // |
1793 | // Into: |
1794 | // BB': |
1795 | // %Y = icmp ne i32 %A, %B |
1796 | // br i1 %Y, ... |
1797 | |
1798 | PredValueInfoTy XorOpValues; |
1799 | bool isLHS = true; |
1800 | if (!computeValueKnownInPredecessors(V: BO->getOperand(i_nocapture: 0), BB, Result&: XorOpValues, |
1801 | Preference: WantInteger, CxtI: BO)) { |
1802 | assert(XorOpValues.empty()); |
1803 | if (!computeValueKnownInPredecessors(V: BO->getOperand(i_nocapture: 1), BB, Result&: XorOpValues, |
1804 | Preference: WantInteger, CxtI: BO)) |
1805 | return false; |
1806 | isLHS = false; |
1807 | } |
1808 | |
1809 | assert(!XorOpValues.empty() && |
1810 | "computeValueKnownInPredecessors returned true with no values" ); |
1811 | |
1812 | // Scan the information to see which is most popular: true or false. The |
1813 | // predecessors can be of the set true, false, or undef. |
1814 | unsigned NumTrue = 0, NumFalse = 0; |
1815 | for (const auto &XorOpValue : XorOpValues) { |
1816 | if (isa<UndefValue>(Val: XorOpValue.first)) |
1817 | // Ignore undefs for the count. |
1818 | continue; |
1819 | if (cast<ConstantInt>(Val: XorOpValue.first)->isZero()) |
1820 | ++NumFalse; |
1821 | else |
1822 | ++NumTrue; |
1823 | } |
1824 | |
1825 | // Determine which value to split on, true, false, or undef if neither. |
1826 | ConstantInt *SplitVal = nullptr; |
1827 | if (NumTrue > NumFalse) |
1828 | SplitVal = ConstantInt::getTrue(Context&: BB->getContext()); |
1829 | else if (NumTrue != 0 || NumFalse != 0) |
1830 | SplitVal = ConstantInt::getFalse(Context&: BB->getContext()); |
1831 | |
1832 | // Collect all of the blocks that this can be folded into so that we can |
1833 | // factor this once and clone it once. |
1834 | SmallVector<BasicBlock*, 8> BlocksToFoldInto; |
1835 | for (const auto &XorOpValue : XorOpValues) { |
1836 | if (XorOpValue.first != SplitVal && !isa<UndefValue>(Val: XorOpValue.first)) |
1837 | continue; |
1838 | |
1839 | BlocksToFoldInto.push_back(Elt: XorOpValue.second); |
1840 | } |
1841 | |
1842 | // If we inferred a value for all of the predecessors, then duplication won't |
1843 | // help us. However, we can just replace the LHS or RHS with the constant. |
1844 | if (BlocksToFoldInto.size() == |
1845 | cast<PHINode>(Val&: BB->front()).getNumIncomingValues()) { |
1846 | if (!SplitVal) { |
1847 | // If all preds provide undef, just nuke the xor, because it is undef too. |
1848 | BO->replaceAllUsesWith(V: UndefValue::get(T: BO->getType())); |
1849 | BO->eraseFromParent(); |
1850 | } else if (SplitVal->isZero() && BO != BO->getOperand(i_nocapture: isLHS)) { |
1851 | // If all preds provide 0, replace the xor with the other input. |
1852 | BO->replaceAllUsesWith(V: BO->getOperand(i_nocapture: isLHS)); |
1853 | BO->eraseFromParent(); |
1854 | } else { |
1855 | // If all preds provide 1, set the computed value to 1. |
1856 | BO->setOperand(i_nocapture: !isLHS, Val_nocapture: SplitVal); |
1857 | } |
1858 | |
1859 | return true; |
1860 | } |
1861 | |
1862 | // If any of predecessors end with an indirect goto, we can't change its |
1863 | // destination. |
1864 | if (any_of(Range&: BlocksToFoldInto, P: [](BasicBlock *Pred) { |
1865 | return isa<IndirectBrInst>(Val: Pred->getTerminator()); |
1866 | })) |
1867 | return false; |
1868 | |
1869 | // Try to duplicate BB into PredBB. |
1870 | return duplicateCondBranchOnPHIIntoPred(BB, PredBBs: BlocksToFoldInto); |
1871 | } |
1872 | |
1873 | /// addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new |
1874 | /// predecessor to the PHIBB block. If it has PHI nodes, add entries for |
1875 | /// NewPred using the entries from OldPred (suitably mapped). |
1876 | static void addPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, |
1877 | BasicBlock *OldPred, |
1878 | BasicBlock *NewPred, |
1879 | DenseMap<Instruction*, Value*> &ValueMap) { |
1880 | for (PHINode &PN : PHIBB->phis()) { |
1881 | // Ok, we have a PHI node. Figure out what the incoming value was for the |
1882 | // DestBlock. |
1883 | Value *IV = PN.getIncomingValueForBlock(BB: OldPred); |
1884 | |
1885 | // Remap the value if necessary. |
1886 | if (Instruction *Inst = dyn_cast<Instruction>(Val: IV)) { |
1887 | DenseMap<Instruction*, Value*>::iterator I = ValueMap.find(Val: Inst); |
1888 | if (I != ValueMap.end()) |
1889 | IV = I->second; |
1890 | } |
1891 | |
1892 | PN.addIncoming(V: IV, BB: NewPred); |
1893 | } |
1894 | } |
1895 | |
1896 | /// Merge basic block BB into its sole predecessor if possible. |
1897 | bool JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB) { |
1898 | BasicBlock *SinglePred = BB->getSinglePredecessor(); |
1899 | if (!SinglePred) |
1900 | return false; |
1901 | |
1902 | const Instruction *TI = SinglePred->getTerminator(); |
1903 | if (TI->isSpecialTerminator() || TI->getNumSuccessors() != 1 || |
1904 | SinglePred == BB || hasAddressTakenAndUsed(BB)) |
1905 | return false; |
1906 | |
1907 | // If SinglePred was a loop header, BB becomes one. |
1908 | if (LoopHeaders.erase(V: SinglePred)) |
1909 | LoopHeaders.insert(V: BB); |
1910 | |
1911 | LVI->eraseBlock(BB: SinglePred); |
1912 | MergeBasicBlockIntoOnlyPred(BB, DTU: DTU.get()); |
1913 | |
1914 | // Now that BB is merged into SinglePred (i.e. SinglePred code followed by |
1915 | // BB code within one basic block `BB`), we need to invalidate the LVI |
1916 | // information associated with BB, because the LVI information need not be |
1917 | // true for all of BB after the merge. For example, |
1918 | // Before the merge, LVI info and code is as follows: |
1919 | // SinglePred: <LVI info1 for %p val> |
1920 | // %y = use of %p |
1921 | // call @exit() // need not transfer execution to successor. |
1922 | // assume(%p) // from this point on %p is true |
1923 | // br label %BB |
1924 | // BB: <LVI info2 for %p val, i.e. %p is true> |
1925 | // %x = use of %p |
1926 | // br label exit |
1927 | // |
1928 | // Note that this LVI info for blocks BB and SinglPred is correct for %p |
1929 | // (info2 and info1 respectively). After the merge and the deletion of the |
1930 | // LVI info1 for SinglePred. We have the following code: |
1931 | // BB: <LVI info2 for %p val> |
1932 | // %y = use of %p |
1933 | // call @exit() |
1934 | // assume(%p) |
1935 | // %x = use of %p <-- LVI info2 is correct from here onwards. |
1936 | // br label exit |
1937 | // LVI info2 for BB is incorrect at the beginning of BB. |
1938 | |
1939 | // Invalidate LVI information for BB if the LVI is not provably true for |
1940 | // all of BB. |
1941 | if (!isGuaranteedToTransferExecutionToSuccessor(BB)) |
1942 | LVI->eraseBlock(BB); |
1943 | return true; |
1944 | } |
1945 | |
1946 | /// Update the SSA form. NewBB contains instructions that are copied from BB. |
1947 | /// ValueMapping maps old values in BB to new ones in NewBB. |
1948 | void JumpThreadingPass::updateSSA( |
1949 | BasicBlock *BB, BasicBlock *NewBB, |
1950 | DenseMap<Instruction *, Value *> &ValueMapping) { |
1951 | // If there were values defined in BB that are used outside the block, then we |
1952 | // now have to update all uses of the value to use either the original value, |
1953 | // the cloned value, or some PHI derived value. This can require arbitrary |
1954 | // PHI insertion, of which we are prepared to do, clean these up now. |
1955 | SSAUpdater SSAUpdate; |
1956 | SmallVector<Use *, 16> UsesToRename; |
1957 | SmallVector<DbgValueInst *, 4> DbgValues; |
1958 | SmallVector<DbgVariableRecord *, 4> DbgVariableRecords; |
1959 | |
1960 | for (Instruction &I : *BB) { |
1961 | // Scan all uses of this instruction to see if it is used outside of its |
1962 | // block, and if so, record them in UsesToRename. |
1963 | for (Use &U : I.uses()) { |
1964 | Instruction *User = cast<Instruction>(Val: U.getUser()); |
1965 | if (PHINode *UserPN = dyn_cast<PHINode>(Val: User)) { |
1966 | if (UserPN->getIncomingBlock(U) == BB) |
1967 | continue; |
1968 | } else if (User->getParent() == BB) |
1969 | continue; |
1970 | |
1971 | UsesToRename.push_back(Elt: &U); |
1972 | } |
1973 | |
1974 | // Find debug values outside of the block |
1975 | findDbgValues(DbgValues, V: &I, DbgVariableRecords: &DbgVariableRecords); |
1976 | llvm::erase_if(C&: DbgValues, P: [&](const DbgValueInst *DbgVal) { |
1977 | return DbgVal->getParent() == BB; |
1978 | }); |
1979 | llvm::erase_if(C&: DbgVariableRecords, P: [&](const DbgVariableRecord *DbgVarRec) { |
1980 | return DbgVarRec->getParent() == BB; |
1981 | }); |
1982 | |
1983 | // If there are no uses outside the block, we're done with this instruction. |
1984 | if (UsesToRename.empty() && DbgValues.empty() && DbgVariableRecords.empty()) |
1985 | continue; |
1986 | LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n" ); |
1987 | |
1988 | // We found a use of I outside of BB. Rename all uses of I that are outside |
1989 | // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks |
1990 | // with the two values we know. |
1991 | SSAUpdate.Initialize(Ty: I.getType(), Name: I.getName()); |
1992 | SSAUpdate.AddAvailableValue(BB, V: &I); |
1993 | SSAUpdate.AddAvailableValue(BB: NewBB, V: ValueMapping[&I]); |
1994 | |
1995 | while (!UsesToRename.empty()) |
1996 | SSAUpdate.RewriteUse(U&: *UsesToRename.pop_back_val()); |
1997 | if (!DbgValues.empty() || !DbgVariableRecords.empty()) { |
1998 | SSAUpdate.UpdateDebugValues(I: &I, DbgValues); |
1999 | SSAUpdate.UpdateDebugValues(I: &I, DbgValues&: DbgVariableRecords); |
2000 | DbgValues.clear(); |
2001 | DbgVariableRecords.clear(); |
2002 | } |
2003 | |
2004 | LLVM_DEBUG(dbgs() << "\n" ); |
2005 | } |
2006 | } |
2007 | |
2008 | /// Clone instructions in range [BI, BE) to NewBB. For PHI nodes, we only clone |
2009 | /// arguments that come from PredBB. Return the map from the variables in the |
2010 | /// source basic block to the variables in the newly created basic block. |
2011 | DenseMap<Instruction *, Value *> |
2012 | JumpThreadingPass::cloneInstructions(BasicBlock::iterator BI, |
2013 | BasicBlock::iterator BE, BasicBlock *NewBB, |
2014 | BasicBlock *PredBB) { |
2015 | // We are going to have to map operands from the source basic block to the new |
2016 | // copy of the block 'NewBB'. If there are PHI nodes in the source basic |
2017 | // block, evaluate them to account for entry from PredBB. |
2018 | DenseMap<Instruction *, Value *> ValueMapping; |
2019 | |
2020 | // Retargets llvm.dbg.value to any renamed variables. |
2021 | auto RetargetDbgValueIfPossible = [&](Instruction *NewInst) -> bool { |
2022 | auto DbgInstruction = dyn_cast<DbgValueInst>(Val: NewInst); |
2023 | if (!DbgInstruction) |
2024 | return false; |
2025 | |
2026 | SmallSet<std::pair<Value *, Value *>, 16> OperandsToRemap; |
2027 | for (auto DbgOperand : DbgInstruction->location_ops()) { |
2028 | auto DbgOperandInstruction = dyn_cast<Instruction>(Val: DbgOperand); |
2029 | if (!DbgOperandInstruction) |
2030 | continue; |
2031 | |
2032 | auto I = ValueMapping.find(Val: DbgOperandInstruction); |
2033 | if (I != ValueMapping.end()) { |
2034 | OperandsToRemap.insert( |
2035 | V: std::pair<Value *, Value *>(DbgOperand, I->second)); |
2036 | } |
2037 | } |
2038 | |
2039 | for (auto &[OldOp, MappedOp] : OperandsToRemap) |
2040 | DbgInstruction->replaceVariableLocationOp(OldValue: OldOp, NewValue: MappedOp); |
2041 | return true; |
2042 | }; |
2043 | |
2044 | // Duplicate implementation of the above dbg.value code, using |
2045 | // DbgVariableRecords instead. |
2046 | auto RetargetDbgVariableRecordIfPossible = [&](DbgVariableRecord *DVR) { |
2047 | SmallSet<std::pair<Value *, Value *>, 16> OperandsToRemap; |
2048 | for (auto *Op : DVR->location_ops()) { |
2049 | Instruction *OpInst = dyn_cast<Instruction>(Val: Op); |
2050 | if (!OpInst) |
2051 | continue; |
2052 | |
2053 | auto I = ValueMapping.find(Val: OpInst); |
2054 | if (I != ValueMapping.end()) |
2055 | OperandsToRemap.insert(V: {OpInst, I->second}); |
2056 | } |
2057 | |
2058 | for (auto &[OldOp, MappedOp] : OperandsToRemap) |
2059 | DVR->replaceVariableLocationOp(OldValue: OldOp, NewValue: MappedOp); |
2060 | }; |
2061 | |
2062 | BasicBlock *RangeBB = BI->getParent(); |
2063 | |
2064 | // Clone the phi nodes of the source basic block into NewBB. The resulting |
2065 | // phi nodes are trivial since NewBB only has one predecessor, but SSAUpdater |
2066 | // might need to rewrite the operand of the cloned phi. |
2067 | for (; PHINode *PN = dyn_cast<PHINode>(Val&: BI); ++BI) { |
2068 | PHINode *NewPN = PHINode::Create(Ty: PN->getType(), NumReservedValues: 1, NameStr: PN->getName(), InsertAtEnd: NewBB); |
2069 | NewPN->addIncoming(V: PN->getIncomingValueForBlock(BB: PredBB), BB: PredBB); |
2070 | ValueMapping[PN] = NewPN; |
2071 | } |
2072 | |
2073 | // Clone noalias scope declarations in the threaded block. When threading a |
2074 | // loop exit, we would otherwise end up with two idential scope declarations |
2075 | // visible at the same time. |
2076 | SmallVector<MDNode *> NoAliasScopes; |
2077 | DenseMap<MDNode *, MDNode *> ClonedScopes; |
2078 | LLVMContext &Context = PredBB->getContext(); |
2079 | identifyNoAliasScopesToClone(Start: BI, End: BE, NoAliasDeclScopes&: NoAliasScopes); |
2080 | cloneNoAliasScopes(NoAliasDeclScopes: NoAliasScopes, ClonedScopes, Ext: "thread" , Context); |
2081 | |
2082 | auto CloneAndRemapDbgInfo = [&](Instruction *NewInst, Instruction *From) { |
2083 | auto DVRRange = NewInst->cloneDebugInfoFrom(From); |
2084 | for (DbgVariableRecord &DVR : filterDbgVars(R: DVRRange)) |
2085 | RetargetDbgVariableRecordIfPossible(&DVR); |
2086 | }; |
2087 | |
2088 | // Clone the non-phi instructions of the source basic block into NewBB, |
2089 | // keeping track of the mapping and using it to remap operands in the cloned |
2090 | // instructions. |
2091 | for (; BI != BE; ++BI) { |
2092 | Instruction *New = BI->clone(); |
2093 | New->setName(BI->getName()); |
2094 | New->insertInto(ParentBB: NewBB, It: NewBB->end()); |
2095 | ValueMapping[&*BI] = New; |
2096 | adaptNoAliasScopes(I: New, ClonedScopes, Context); |
2097 | |
2098 | CloneAndRemapDbgInfo(New, &*BI); |
2099 | |
2100 | if (RetargetDbgValueIfPossible(New)) |
2101 | continue; |
2102 | |
2103 | // Remap operands to patch up intra-block references. |
2104 | for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) |
2105 | if (Instruction *Inst = dyn_cast<Instruction>(Val: New->getOperand(i))) { |
2106 | DenseMap<Instruction *, Value *>::iterator I = ValueMapping.find(Val: Inst); |
2107 | if (I != ValueMapping.end()) |
2108 | New->setOperand(i, Val: I->second); |
2109 | } |
2110 | } |
2111 | |
2112 | // There may be DbgVariableRecords on the terminator, clone directly from |
2113 | // marker to marker as there isn't an instruction there. |
2114 | if (BE != RangeBB->end() && BE->hasDbgRecords()) { |
2115 | // Dump them at the end. |
2116 | DbgMarker *Marker = RangeBB->getMarker(It: BE); |
2117 | DbgMarker *EndMarker = NewBB->createMarker(It: NewBB->end()); |
2118 | auto DVRRange = EndMarker->cloneDebugInfoFrom(From: Marker, FromHere: std::nullopt); |
2119 | for (DbgVariableRecord &DVR : filterDbgVars(R: DVRRange)) |
2120 | RetargetDbgVariableRecordIfPossible(&DVR); |
2121 | } |
2122 | |
2123 | return ValueMapping; |
2124 | } |
2125 | |
2126 | /// Attempt to thread through two successive basic blocks. |
2127 | bool JumpThreadingPass::maybethreadThroughTwoBasicBlocks(BasicBlock *BB, |
2128 | Value *Cond) { |
2129 | // Consider: |
2130 | // |
2131 | // PredBB: |
2132 | // %var = phi i32* [ null, %bb1 ], [ @a, %bb2 ] |
2133 | // %tobool = icmp eq i32 %cond, 0 |
2134 | // br i1 %tobool, label %BB, label ... |
2135 | // |
2136 | // BB: |
2137 | // %cmp = icmp eq i32* %var, null |
2138 | // br i1 %cmp, label ..., label ... |
2139 | // |
2140 | // We don't know the value of %var at BB even if we know which incoming edge |
2141 | // we take to BB. However, once we duplicate PredBB for each of its incoming |
2142 | // edges (say, PredBB1 and PredBB2), we know the value of %var in each copy of |
2143 | // PredBB. Then we can thread edges PredBB1->BB and PredBB2->BB through BB. |
2144 | |
2145 | // Require that BB end with a Branch for simplicity. |
2146 | BranchInst *CondBr = dyn_cast<BranchInst>(Val: BB->getTerminator()); |
2147 | if (!CondBr) |
2148 | return false; |
2149 | |
2150 | // BB must have exactly one predecessor. |
2151 | BasicBlock *PredBB = BB->getSinglePredecessor(); |
2152 | if (!PredBB) |
2153 | return false; |
2154 | |
2155 | // Require that PredBB end with a conditional Branch. If PredBB ends with an |
2156 | // unconditional branch, we should be merging PredBB and BB instead. For |
2157 | // simplicity, we don't deal with a switch. |
2158 | BranchInst *PredBBBranch = dyn_cast<BranchInst>(Val: PredBB->getTerminator()); |
2159 | if (!PredBBBranch || PredBBBranch->isUnconditional()) |
2160 | return false; |
2161 | |
2162 | // If PredBB has exactly one incoming edge, we don't gain anything by copying |
2163 | // PredBB. |
2164 | if (PredBB->getSinglePredecessor()) |
2165 | return false; |
2166 | |
2167 | // Don't thread through PredBB if it contains a successor edge to itself, in |
2168 | // which case we would infinite loop. Suppose we are threading an edge from |
2169 | // PredPredBB through PredBB and BB to SuccBB with PredBB containing a |
2170 | // successor edge to itself. If we allowed jump threading in this case, we |
2171 | // could duplicate PredBB and BB as, say, PredBB.thread and BB.thread. Since |
2172 | // PredBB.thread has a successor edge to PredBB, we would immediately come up |
2173 | // with another jump threading opportunity from PredBB.thread through PredBB |
2174 | // and BB to SuccBB. This jump threading would repeatedly occur. That is, we |
2175 | // would keep peeling one iteration from PredBB. |
2176 | if (llvm::is_contained(Range: successors(BB: PredBB), Element: PredBB)) |
2177 | return false; |
2178 | |
2179 | // Don't thread across a loop header. |
2180 | if (LoopHeaders.count(V: PredBB)) |
2181 | return false; |
2182 | |
2183 | // Avoid complication with duplicating EH pads. |
2184 | if (PredBB->isEHPad()) |
2185 | return false; |
2186 | |
2187 | // Find a predecessor that we can thread. For simplicity, we only consider a |
2188 | // successor edge out of BB to which we thread exactly one incoming edge into |
2189 | // PredBB. |
2190 | unsigned ZeroCount = 0; |
2191 | unsigned OneCount = 0; |
2192 | BasicBlock *ZeroPred = nullptr; |
2193 | BasicBlock *OnePred = nullptr; |
2194 | for (BasicBlock *P : predecessors(BB: PredBB)) { |
2195 | // If PredPred ends with IndirectBrInst, we can't handle it. |
2196 | if (isa<IndirectBrInst>(Val: P->getTerminator())) |
2197 | continue; |
2198 | if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>( |
2199 | Val: evaluateOnPredecessorEdge(BB, PredPredBB: P, V: Cond))) { |
2200 | if (CI->isZero()) { |
2201 | ZeroCount++; |
2202 | ZeroPred = P; |
2203 | } else if (CI->isOne()) { |
2204 | OneCount++; |
2205 | OnePred = P; |
2206 | } |
2207 | } |
2208 | } |
2209 | |
2210 | // Disregard complicated cases where we have to thread multiple edges. |
2211 | BasicBlock *PredPredBB; |
2212 | if (ZeroCount == 1) { |
2213 | PredPredBB = ZeroPred; |
2214 | } else if (OneCount == 1) { |
2215 | PredPredBB = OnePred; |
2216 | } else { |
2217 | return false; |
2218 | } |
2219 | |
2220 | BasicBlock *SuccBB = CondBr->getSuccessor(i: PredPredBB == ZeroPred); |
2221 | |
2222 | // If threading to the same block as we come from, we would infinite loop. |
2223 | if (SuccBB == BB) { |
2224 | LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName() |
2225 | << "' - would thread to self!\n" ); |
2226 | return false; |
2227 | } |
2228 | |
2229 | // If threading this would thread across a loop header, don't thread the edge. |
2230 | // See the comments above findLoopHeaders for justifications and caveats. |
2231 | if (LoopHeaders.count(V: BB) || LoopHeaders.count(V: SuccBB)) { |
2232 | LLVM_DEBUG({ |
2233 | bool = LoopHeaders.count(BB); |
2234 | bool = LoopHeaders.count(SuccBB); |
2235 | dbgs() << " Not threading across " |
2236 | << (BBIsHeader ? "loop header BB '" : "block BB '" ) |
2237 | << BB->getName() << "' to dest " |
2238 | << (SuccIsHeader ? "loop header BB '" : "block BB '" ) |
2239 | << SuccBB->getName() |
2240 | << "' - it might create an irreducible loop!\n" ; |
2241 | }); |
2242 | return false; |
2243 | } |
2244 | |
2245 | // Compute the cost of duplicating BB and PredBB. |
2246 | unsigned BBCost = getJumpThreadDuplicationCost( |
2247 | TTI, BB, StopAt: BB->getTerminator(), Threshold: BBDupThreshold); |
2248 | unsigned PredBBCost = getJumpThreadDuplicationCost( |
2249 | TTI, BB: PredBB, StopAt: PredBB->getTerminator(), Threshold: BBDupThreshold); |
2250 | |
2251 | // Give up if costs are too high. We need to check BBCost and PredBBCost |
2252 | // individually before checking their sum because getJumpThreadDuplicationCost |
2253 | // return (unsigned)~0 for those basic blocks that cannot be duplicated. |
2254 | if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold || |
2255 | BBCost + PredBBCost > BBDupThreshold) { |
2256 | LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName() |
2257 | << "' - Cost is too high: " << PredBBCost |
2258 | << " for PredBB, " << BBCost << "for BB\n" ); |
2259 | return false; |
2260 | } |
2261 | |
2262 | // Now we are ready to duplicate PredBB. |
2263 | threadThroughTwoBasicBlocks(PredPredBB, PredBB, BB, SuccBB); |
2264 | return true; |
2265 | } |
2266 | |
2267 | void JumpThreadingPass::threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, |
2268 | BasicBlock *PredBB, |
2269 | BasicBlock *BB, |
2270 | BasicBlock *SuccBB) { |
2271 | LLVM_DEBUG(dbgs() << " Threading through '" << PredBB->getName() << "' and '" |
2272 | << BB->getName() << "'\n" ); |
2273 | |
2274 | // Build BPI/BFI before any changes are made to IR. |
2275 | bool HasProfile = doesBlockHaveProfileData(BB); |
2276 | auto *BFI = getOrCreateBFI(Force: HasProfile); |
2277 | auto *BPI = getOrCreateBPI(Force: BFI != nullptr); |
2278 | |
2279 | BranchInst *CondBr = cast<BranchInst>(Val: BB->getTerminator()); |
2280 | BranchInst *PredBBBranch = cast<BranchInst>(Val: PredBB->getTerminator()); |
2281 | |
2282 | BasicBlock *NewBB = |
2283 | BasicBlock::Create(Context&: PredBB->getContext(), Name: PredBB->getName() + ".thread" , |
2284 | Parent: PredBB->getParent(), InsertBefore: PredBB); |
2285 | NewBB->moveAfter(MovePos: PredBB); |
2286 | |
2287 | // Set the block frequency of NewBB. |
2288 | if (BFI) { |
2289 | assert(BPI && "It's expected BPI to exist along with BFI" ); |
2290 | auto NewBBFreq = BFI->getBlockFreq(BB: PredPredBB) * |
2291 | BPI->getEdgeProbability(Src: PredPredBB, Dst: PredBB); |
2292 | BFI->setBlockFreq(BB: NewBB, Freq: NewBBFreq); |
2293 | } |
2294 | |
2295 | // We are going to have to map operands from the original BB block to the new |
2296 | // copy of the block 'NewBB'. If there are PHI nodes in PredBB, evaluate them |
2297 | // to account for entry from PredPredBB. |
2298 | DenseMap<Instruction *, Value *> ValueMapping = |
2299 | cloneInstructions(BI: PredBB->begin(), BE: PredBB->end(), NewBB, PredBB: PredPredBB); |
2300 | |
2301 | // Copy the edge probabilities from PredBB to NewBB. |
2302 | if (BPI) |
2303 | BPI->copyEdgeProbabilities(Src: PredBB, Dst: NewBB); |
2304 | |
2305 | // Update the terminator of PredPredBB to jump to NewBB instead of PredBB. |
2306 | // This eliminates predecessors from PredPredBB, which requires us to simplify |
2307 | // any PHI nodes in PredBB. |
2308 | Instruction *PredPredTerm = PredPredBB->getTerminator(); |
2309 | for (unsigned i = 0, e = PredPredTerm->getNumSuccessors(); i != e; ++i) |
2310 | if (PredPredTerm->getSuccessor(Idx: i) == PredBB) { |
2311 | PredBB->removePredecessor(Pred: PredPredBB, KeepOneInputPHIs: true); |
2312 | PredPredTerm->setSuccessor(Idx: i, BB: NewBB); |
2313 | } |
2314 | |
2315 | addPHINodeEntriesForMappedBlock(PHIBB: PredBBBranch->getSuccessor(i: 0), OldPred: PredBB, NewPred: NewBB, |
2316 | ValueMap&: ValueMapping); |
2317 | addPHINodeEntriesForMappedBlock(PHIBB: PredBBBranch->getSuccessor(i: 1), OldPred: PredBB, NewPred: NewBB, |
2318 | ValueMap&: ValueMapping); |
2319 | |
2320 | DTU->applyUpdatesPermissive( |
2321 | Updates: {{DominatorTree::Insert, NewBB, CondBr->getSuccessor(i: 0)}, |
2322 | {DominatorTree::Insert, NewBB, CondBr->getSuccessor(i: 1)}, |
2323 | {DominatorTree::Insert, PredPredBB, NewBB}, |
2324 | {DominatorTree::Delete, PredPredBB, PredBB}}); |
2325 | |
2326 | updateSSA(BB: PredBB, NewBB, ValueMapping); |
2327 | |
2328 | // Clean up things like PHI nodes with single operands, dead instructions, |
2329 | // etc. |
2330 | SimplifyInstructionsInBlock(BB: NewBB, TLI); |
2331 | SimplifyInstructionsInBlock(BB: PredBB, TLI); |
2332 | |
2333 | SmallVector<BasicBlock *, 1> PredsToFactor; |
2334 | PredsToFactor.push_back(Elt: NewBB); |
2335 | threadEdge(BB, PredBBs: PredsToFactor, SuccBB); |
2336 | } |
2337 | |
2338 | /// tryThreadEdge - Thread an edge if it's safe and profitable to do so. |
2339 | bool JumpThreadingPass::tryThreadEdge( |
2340 | BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, |
2341 | BasicBlock *SuccBB) { |
2342 | // If threading to the same block as we come from, we would infinite loop. |
2343 | if (SuccBB == BB) { |
2344 | LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName() |
2345 | << "' - would thread to self!\n" ); |
2346 | return false; |
2347 | } |
2348 | |
2349 | // If threading this would thread across a loop header, don't thread the edge. |
2350 | // See the comments above findLoopHeaders for justifications and caveats. |
2351 | if (LoopHeaders.count(V: BB) || LoopHeaders.count(V: SuccBB)) { |
2352 | LLVM_DEBUG({ |
2353 | bool = LoopHeaders.count(BB); |
2354 | bool = LoopHeaders.count(SuccBB); |
2355 | dbgs() << " Not threading across " |
2356 | << (BBIsHeader ? "loop header BB '" : "block BB '" ) << BB->getName() |
2357 | << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '" ) |
2358 | << SuccBB->getName() << "' - it might create an irreducible loop!\n" ; |
2359 | }); |
2360 | return false; |
2361 | } |
2362 | |
2363 | unsigned JumpThreadCost = getJumpThreadDuplicationCost( |
2364 | TTI, BB, StopAt: BB->getTerminator(), Threshold: BBDupThreshold); |
2365 | if (JumpThreadCost > BBDupThreshold) { |
2366 | LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName() |
2367 | << "' - Cost is too high: " << JumpThreadCost << "\n" ); |
2368 | return false; |
2369 | } |
2370 | |
2371 | threadEdge(BB, PredBBs, SuccBB); |
2372 | return true; |
2373 | } |
2374 | |
2375 | /// threadEdge - We have decided that it is safe and profitable to factor the |
2376 | /// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB |
2377 | /// across BB. Transform the IR to reflect this change. |
2378 | void JumpThreadingPass::threadEdge(BasicBlock *BB, |
2379 | const SmallVectorImpl<BasicBlock *> &PredBBs, |
2380 | BasicBlock *SuccBB) { |
2381 | assert(SuccBB != BB && "Don't create an infinite loop" ); |
2382 | |
2383 | assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) && |
2384 | "Don't thread across loop headers" ); |
2385 | |
2386 | // Build BPI/BFI before any changes are made to IR. |
2387 | bool HasProfile = doesBlockHaveProfileData(BB); |
2388 | auto *BFI = getOrCreateBFI(Force: HasProfile); |
2389 | auto *BPI = getOrCreateBPI(Force: BFI != nullptr); |
2390 | |
2391 | // And finally, do it! Start by factoring the predecessors if needed. |
2392 | BasicBlock *PredBB; |
2393 | if (PredBBs.size() == 1) |
2394 | PredBB = PredBBs[0]; |
2395 | else { |
2396 | LLVM_DEBUG(dbgs() << " Factoring out " << PredBBs.size() |
2397 | << " common predecessors.\n" ); |
2398 | PredBB = splitBlockPreds(BB, Preds: PredBBs, Suffix: ".thr_comm" ); |
2399 | } |
2400 | |
2401 | // And finally, do it! |
2402 | LLVM_DEBUG(dbgs() << " Threading edge from '" << PredBB->getName() |
2403 | << "' to '" << SuccBB->getName() |
2404 | << ", across block:\n " << *BB << "\n" ); |
2405 | |
2406 | LVI->threadEdge(PredBB, OldSucc: BB, NewSucc: SuccBB); |
2407 | |
2408 | BasicBlock *NewBB = BasicBlock::Create(Context&: BB->getContext(), |
2409 | Name: BB->getName()+".thread" , |
2410 | Parent: BB->getParent(), InsertBefore: BB); |
2411 | NewBB->moveAfter(MovePos: PredBB); |
2412 | |
2413 | // Set the block frequency of NewBB. |
2414 | if (BFI) { |
2415 | assert(BPI && "It's expected BPI to exist along with BFI" ); |
2416 | auto NewBBFreq = |
2417 | BFI->getBlockFreq(BB: PredBB) * BPI->getEdgeProbability(Src: PredBB, Dst: BB); |
2418 | BFI->setBlockFreq(BB: NewBB, Freq: NewBBFreq); |
2419 | } |
2420 | |
2421 | // Copy all the instructions from BB to NewBB except the terminator. |
2422 | DenseMap<Instruction *, Value *> ValueMapping = |
2423 | cloneInstructions(BI: BB->begin(), BE: std::prev(x: BB->end()), NewBB, PredBB); |
2424 | |
2425 | // We didn't copy the terminator from BB over to NewBB, because there is now |
2426 | // an unconditional jump to SuccBB. Insert the unconditional jump. |
2427 | BranchInst *NewBI = BranchInst::Create(IfTrue: SuccBB, InsertAtEnd: NewBB); |
2428 | NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc()); |
2429 | |
2430 | // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the |
2431 | // PHI nodes for NewBB now. |
2432 | addPHINodeEntriesForMappedBlock(PHIBB: SuccBB, OldPred: BB, NewPred: NewBB, ValueMap&: ValueMapping); |
2433 | |
2434 | // Update the terminator of PredBB to jump to NewBB instead of BB. This |
2435 | // eliminates predecessors from BB, which requires us to simplify any PHI |
2436 | // nodes in BB. |
2437 | Instruction *PredTerm = PredBB->getTerminator(); |
2438 | for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) |
2439 | if (PredTerm->getSuccessor(Idx: i) == BB) { |
2440 | BB->removePredecessor(Pred: PredBB, KeepOneInputPHIs: true); |
2441 | PredTerm->setSuccessor(Idx: i, BB: NewBB); |
2442 | } |
2443 | |
2444 | // Enqueue required DT updates. |
2445 | DTU->applyUpdatesPermissive(Updates: {{DominatorTree::Insert, NewBB, SuccBB}, |
2446 | {DominatorTree::Insert, PredBB, NewBB}, |
2447 | {DominatorTree::Delete, PredBB, BB}}); |
2448 | |
2449 | updateSSA(BB, NewBB, ValueMapping); |
2450 | |
2451 | // At this point, the IR is fully up to date and consistent. Do a quick scan |
2452 | // over the new instructions and zap any that are constants or dead. This |
2453 | // frequently happens because of phi translation. |
2454 | SimplifyInstructionsInBlock(BB: NewBB, TLI); |
2455 | |
2456 | // Update the edge weight from BB to SuccBB, which should be less than before. |
2457 | updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile); |
2458 | |
2459 | // Threaded an edge! |
2460 | ++NumThreads; |
2461 | } |
2462 | |
2463 | /// Create a new basic block that will be the predecessor of BB and successor of |
2464 | /// all blocks in Preds. When profile data is available, update the frequency of |
2465 | /// this new block. |
2466 | BasicBlock *JumpThreadingPass::splitBlockPreds(BasicBlock *BB, |
2467 | ArrayRef<BasicBlock *> Preds, |
2468 | const char *Suffix) { |
2469 | SmallVector<BasicBlock *, 2> NewBBs; |
2470 | |
2471 | // Collect the frequencies of all predecessors of BB, which will be used to |
2472 | // update the edge weight of the result of splitting predecessors. |
2473 | DenseMap<BasicBlock *, BlockFrequency> FreqMap; |
2474 | auto *BFI = getBFI(); |
2475 | if (BFI) { |
2476 | auto *BPI = getOrCreateBPI(Force: true); |
2477 | for (auto *Pred : Preds) |
2478 | FreqMap.insert(KV: std::make_pair( |
2479 | x&: Pred, y: BFI->getBlockFreq(BB: Pred) * BPI->getEdgeProbability(Src: Pred, Dst: BB))); |
2480 | } |
2481 | |
2482 | // In the case when BB is a LandingPad block we create 2 new predecessors |
2483 | // instead of just one. |
2484 | if (BB->isLandingPad()) { |
2485 | std::string NewName = std::string(Suffix) + ".split-lp" ; |
2486 | SplitLandingPadPredecessors(OrigBB: BB, Preds, Suffix, Suffix2: NewName.c_str(), NewBBs); |
2487 | } else { |
2488 | NewBBs.push_back(Elt: SplitBlockPredecessors(BB, Preds, Suffix)); |
2489 | } |
2490 | |
2491 | std::vector<DominatorTree::UpdateType> Updates; |
2492 | Updates.reserve(n: (2 * Preds.size()) + NewBBs.size()); |
2493 | for (auto *NewBB : NewBBs) { |
2494 | BlockFrequency NewBBFreq(0); |
2495 | Updates.push_back(x: {DominatorTree::Insert, NewBB, BB}); |
2496 | for (auto *Pred : predecessors(BB: NewBB)) { |
2497 | Updates.push_back(x: {DominatorTree::Delete, Pred, BB}); |
2498 | Updates.push_back(x: {DominatorTree::Insert, Pred, NewBB}); |
2499 | if (BFI) // Update frequencies between Pred -> NewBB. |
2500 | NewBBFreq += FreqMap.lookup(Val: Pred); |
2501 | } |
2502 | if (BFI) // Apply the summed frequency to NewBB. |
2503 | BFI->setBlockFreq(BB: NewBB, Freq: NewBBFreq); |
2504 | } |
2505 | |
2506 | DTU->applyUpdatesPermissive(Updates); |
2507 | return NewBBs[0]; |
2508 | } |
2509 | |
2510 | bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) { |
2511 | const Instruction *TI = BB->getTerminator(); |
2512 | if (!TI || TI->getNumSuccessors() < 2) |
2513 | return false; |
2514 | |
2515 | return hasValidBranchWeightMD(I: *TI); |
2516 | } |
2517 | |
2518 | /// Update the block frequency of BB and branch weight and the metadata on the |
2519 | /// edge BB->SuccBB. This is done by scaling the weight of BB->SuccBB by 1 - |
2520 | /// Freq(PredBB->BB) / Freq(BB->SuccBB). |
2521 | void JumpThreadingPass::updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, |
2522 | BasicBlock *BB, |
2523 | BasicBlock *NewBB, |
2524 | BasicBlock *SuccBB, |
2525 | BlockFrequencyInfo *BFI, |
2526 | BranchProbabilityInfo *BPI, |
2527 | bool HasProfile) { |
2528 | assert(((BFI && BPI) || (!BFI && !BFI)) && |
2529 | "Both BFI & BPI should either be set or unset" ); |
2530 | |
2531 | if (!BFI) { |
2532 | assert(!HasProfile && |
2533 | "It's expected to have BFI/BPI when profile info exists" ); |
2534 | return; |
2535 | } |
2536 | |
2537 | // As the edge from PredBB to BB is deleted, we have to update the block |
2538 | // frequency of BB. |
2539 | auto BBOrigFreq = BFI->getBlockFreq(BB); |
2540 | auto NewBBFreq = BFI->getBlockFreq(BB: NewBB); |
2541 | auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(Src: BB, Dst: SuccBB); |
2542 | auto BBNewFreq = BBOrigFreq - NewBBFreq; |
2543 | BFI->setBlockFreq(BB, Freq: BBNewFreq); |
2544 | |
2545 | // Collect updated outgoing edges' frequencies from BB and use them to update |
2546 | // edge probabilities. |
2547 | SmallVector<uint64_t, 4> BBSuccFreq; |
2548 | for (BasicBlock *Succ : successors(BB)) { |
2549 | auto SuccFreq = (Succ == SuccBB) |
2550 | ? BB2SuccBBFreq - NewBBFreq |
2551 | : BBOrigFreq * BPI->getEdgeProbability(Src: BB, Dst: Succ); |
2552 | BBSuccFreq.push_back(Elt: SuccFreq.getFrequency()); |
2553 | } |
2554 | |
2555 | uint64_t MaxBBSuccFreq = *llvm::max_element(Range&: BBSuccFreq); |
2556 | |
2557 | SmallVector<BranchProbability, 4> BBSuccProbs; |
2558 | if (MaxBBSuccFreq == 0) |
2559 | BBSuccProbs.assign(NumElts: BBSuccFreq.size(), |
2560 | Elt: {1, static_cast<unsigned>(BBSuccFreq.size())}); |
2561 | else { |
2562 | for (uint64_t Freq : BBSuccFreq) |
2563 | BBSuccProbs.push_back( |
2564 | Elt: BranchProbability::getBranchProbability(Numerator: Freq, Denominator: MaxBBSuccFreq)); |
2565 | // Normalize edge probabilities so that they sum up to one. |
2566 | BranchProbability::normalizeProbabilities(Begin: BBSuccProbs.begin(), |
2567 | End: BBSuccProbs.end()); |
2568 | } |
2569 | |
2570 | // Update edge probabilities in BPI. |
2571 | BPI->setEdgeProbability(Src: BB, Probs: BBSuccProbs); |
2572 | |
2573 | // Update the profile metadata as well. |
2574 | // |
2575 | // Don't do this if the profile of the transformed blocks was statically |
2576 | // estimated. (This could occur despite the function having an entry |
2577 | // frequency in completely cold parts of the CFG.) |
2578 | // |
2579 | // In this case we don't want to suggest to subsequent passes that the |
2580 | // calculated weights are fully consistent. Consider this graph: |
2581 | // |
2582 | // check_1 |
2583 | // 50% / | |
2584 | // eq_1 | 50% |
2585 | // \ | |
2586 | // check_2 |
2587 | // 50% / | |
2588 | // eq_2 | 50% |
2589 | // \ | |
2590 | // check_3 |
2591 | // 50% / | |
2592 | // eq_3 | 50% |
2593 | // \ | |
2594 | // |
2595 | // Assuming the blocks check_* all compare the same value against 1, 2 and 3, |
2596 | // the overall probabilities are inconsistent; the total probability that the |
2597 | // value is either 1, 2 or 3 is 150%. |
2598 | // |
2599 | // As a consequence if we thread eq_1 -> check_2 to check_3, check_2->check_3 |
2600 | // becomes 0%. This is even worse if the edge whose probability becomes 0% is |
2601 | // the loop exit edge. Then based solely on static estimation we would assume |
2602 | // the loop was extremely hot. |
2603 | // |
2604 | // FIXME this locally as well so that BPI and BFI are consistent as well. We |
2605 | // shouldn't make edges extremely likely or unlikely based solely on static |
2606 | // estimation. |
2607 | if (BBSuccProbs.size() >= 2 && HasProfile) { |
2608 | SmallVector<uint32_t, 4> Weights; |
2609 | for (auto Prob : BBSuccProbs) |
2610 | Weights.push_back(Elt: Prob.getNumerator()); |
2611 | |
2612 | auto TI = BB->getTerminator(); |
2613 | setBranchWeights(I&: *TI, Weights); |
2614 | } |
2615 | } |
2616 | |
2617 | /// duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch |
2618 | /// to BB which contains an i1 PHI node and a conditional branch on that PHI. |
2619 | /// If we can duplicate the contents of BB up into PredBB do so now, this |
2620 | /// improves the odds that the branch will be on an analyzable instruction like |
2621 | /// a compare. |
2622 | bool JumpThreadingPass::duplicateCondBranchOnPHIIntoPred( |
2623 | BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs) { |
2624 | assert(!PredBBs.empty() && "Can't handle an empty set" ); |
2625 | |
2626 | // If BB is a loop header, then duplicating this block outside the loop would |
2627 | // cause us to transform this into an irreducible loop, don't do this. |
2628 | // See the comments above findLoopHeaders for justifications and caveats. |
2629 | if (LoopHeaders.count(V: BB)) { |
2630 | LLVM_DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName() |
2631 | << "' into predecessor block '" << PredBBs[0]->getName() |
2632 | << "' - it might create an irreducible loop!\n" ); |
2633 | return false; |
2634 | } |
2635 | |
2636 | unsigned DuplicationCost = getJumpThreadDuplicationCost( |
2637 | TTI, BB, StopAt: BB->getTerminator(), Threshold: BBDupThreshold); |
2638 | if (DuplicationCost > BBDupThreshold) { |
2639 | LLVM_DEBUG(dbgs() << " Not duplicating BB '" << BB->getName() |
2640 | << "' - Cost is too high: " << DuplicationCost << "\n" ); |
2641 | return false; |
2642 | } |
2643 | |
2644 | // And finally, do it! Start by factoring the predecessors if needed. |
2645 | std::vector<DominatorTree::UpdateType> Updates; |
2646 | BasicBlock *PredBB; |
2647 | if (PredBBs.size() == 1) |
2648 | PredBB = PredBBs[0]; |
2649 | else { |
2650 | LLVM_DEBUG(dbgs() << " Factoring out " << PredBBs.size() |
2651 | << " common predecessors.\n" ); |
2652 | PredBB = splitBlockPreds(BB, Preds: PredBBs, Suffix: ".thr_comm" ); |
2653 | } |
2654 | Updates.push_back(x: {DominatorTree::Delete, PredBB, BB}); |
2655 | |
2656 | // Okay, we decided to do this! Clone all the instructions in BB onto the end |
2657 | // of PredBB. |
2658 | LLVM_DEBUG(dbgs() << " Duplicating block '" << BB->getName() |
2659 | << "' into end of '" << PredBB->getName() |
2660 | << "' to eliminate branch on phi. Cost: " |
2661 | << DuplicationCost << " block is:" << *BB << "\n" ); |
2662 | |
2663 | // Unless PredBB ends with an unconditional branch, split the edge so that we |
2664 | // can just clone the bits from BB into the end of the new PredBB. |
2665 | BranchInst *OldPredBranch = dyn_cast<BranchInst>(Val: PredBB->getTerminator()); |
2666 | |
2667 | if (!OldPredBranch || !OldPredBranch->isUnconditional()) { |
2668 | BasicBlock *OldPredBB = PredBB; |
2669 | PredBB = SplitEdge(From: OldPredBB, To: BB); |
2670 | Updates.push_back(x: {DominatorTree::Insert, OldPredBB, PredBB}); |
2671 | Updates.push_back(x: {DominatorTree::Insert, PredBB, BB}); |
2672 | Updates.push_back(x: {DominatorTree::Delete, OldPredBB, BB}); |
2673 | OldPredBranch = cast<BranchInst>(Val: PredBB->getTerminator()); |
2674 | } |
2675 | |
2676 | // We are going to have to map operands from the original BB block into the |
2677 | // PredBB block. Evaluate PHI nodes in BB. |
2678 | DenseMap<Instruction*, Value*> ValueMapping; |
2679 | |
2680 | BasicBlock::iterator BI = BB->begin(); |
2681 | for (; PHINode *PN = dyn_cast<PHINode>(Val&: BI); ++BI) |
2682 | ValueMapping[PN] = PN->getIncomingValueForBlock(BB: PredBB); |
2683 | // Clone the non-phi instructions of BB into PredBB, keeping track of the |
2684 | // mapping and using it to remap operands in the cloned instructions. |
2685 | for (; BI != BB->end(); ++BI) { |
2686 | Instruction *New = BI->clone(); |
2687 | New->insertInto(ParentBB: PredBB, It: OldPredBranch->getIterator()); |
2688 | |
2689 | // Remap operands to patch up intra-block references. |
2690 | for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) |
2691 | if (Instruction *Inst = dyn_cast<Instruction>(Val: New->getOperand(i))) { |
2692 | DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Val: Inst); |
2693 | if (I != ValueMapping.end()) |
2694 | New->setOperand(i, Val: I->second); |
2695 | } |
2696 | |
2697 | // If this instruction can be simplified after the operands are updated, |
2698 | // just use the simplified value instead. This frequently happens due to |
2699 | // phi translation. |
2700 | if (Value *IV = simplifyInstruction( |
2701 | I: New, |
2702 | Q: {BB->getModule()->getDataLayout(), TLI, nullptr, nullptr, New})) { |
2703 | ValueMapping[&*BI] = IV; |
2704 | if (!New->mayHaveSideEffects()) { |
2705 | New->eraseFromParent(); |
2706 | New = nullptr; |
2707 | // Clone debug-info on the elided instruction to the destination |
2708 | // position. |
2709 | OldPredBranch->cloneDebugInfoFrom(From: &*BI, FromHere: std::nullopt, InsertAtHead: true); |
2710 | } |
2711 | } else { |
2712 | ValueMapping[&*BI] = New; |
2713 | } |
2714 | if (New) { |
2715 | // Otherwise, insert the new instruction into the block. |
2716 | New->setName(BI->getName()); |
2717 | // Clone across any debug-info attached to the old instruction. |
2718 | New->cloneDebugInfoFrom(From: &*BI); |
2719 | // Update Dominance from simplified New instruction operands. |
2720 | for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) |
2721 | if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(Val: New->getOperand(i))) |
2722 | Updates.push_back(x: {DominatorTree::Insert, PredBB, SuccBB}); |
2723 | } |
2724 | } |
2725 | |
2726 | // Check to see if the targets of the branch had PHI nodes. If so, we need to |
2727 | // add entries to the PHI nodes for branch from PredBB now. |
2728 | BranchInst *BBBranch = cast<BranchInst>(Val: BB->getTerminator()); |
2729 | addPHINodeEntriesForMappedBlock(PHIBB: BBBranch->getSuccessor(i: 0), OldPred: BB, NewPred: PredBB, |
2730 | ValueMap&: ValueMapping); |
2731 | addPHINodeEntriesForMappedBlock(PHIBB: BBBranch->getSuccessor(i: 1), OldPred: BB, NewPred: PredBB, |
2732 | ValueMap&: ValueMapping); |
2733 | |
2734 | updateSSA(BB, NewBB: PredBB, ValueMapping); |
2735 | |
2736 | // PredBB no longer jumps to BB, remove entries in the PHI node for the edge |
2737 | // that we nuked. |
2738 | BB->removePredecessor(Pred: PredBB, KeepOneInputPHIs: true); |
2739 | |
2740 | // Remove the unconditional branch at the end of the PredBB block. |
2741 | OldPredBranch->eraseFromParent(); |
2742 | if (auto *BPI = getBPI()) |
2743 | BPI->copyEdgeProbabilities(Src: BB, Dst: PredBB); |
2744 | DTU->applyUpdatesPermissive(Updates); |
2745 | |
2746 | ++NumDupes; |
2747 | return true; |
2748 | } |
2749 | |
2750 | // Pred is a predecessor of BB with an unconditional branch to BB. SI is |
2751 | // a Select instruction in Pred. BB has other predecessors and SI is used in |
2752 | // a PHI node in BB. SI has no other use. |
2753 | // A new basic block, NewBB, is created and SI is converted to compare and |
2754 | // conditional branch. SI is erased from parent. |
2755 | void JumpThreadingPass::unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, |
2756 | SelectInst *SI, PHINode *SIUse, |
2757 | unsigned Idx) { |
2758 | // Expand the select. |
2759 | // |
2760 | // Pred -- |
2761 | // | v |
2762 | // | NewBB |
2763 | // | | |
2764 | // |----- |
2765 | // v |
2766 | // BB |
2767 | BranchInst *PredTerm = cast<BranchInst>(Val: Pred->getTerminator()); |
2768 | BasicBlock *NewBB = BasicBlock::Create(Context&: BB->getContext(), Name: "select.unfold" , |
2769 | Parent: BB->getParent(), InsertBefore: BB); |
2770 | // Move the unconditional branch to NewBB. |
2771 | PredTerm->removeFromParent(); |
2772 | PredTerm->insertInto(ParentBB: NewBB, It: NewBB->end()); |
2773 | // Create a conditional branch and update PHI nodes. |
2774 | auto *BI = BranchInst::Create(IfTrue: NewBB, IfFalse: BB, Cond: SI->getCondition(), InsertAtEnd: Pred); |
2775 | BI->applyMergedLocation(LocA: PredTerm->getDebugLoc(), LocB: SI->getDebugLoc()); |
2776 | BI->copyMetadata(SrcInst: *SI, WL: {LLVMContext::MD_prof}); |
2777 | SIUse->setIncomingValue(i: Idx, V: SI->getFalseValue()); |
2778 | SIUse->addIncoming(V: SI->getTrueValue(), BB: NewBB); |
2779 | |
2780 | uint64_t TrueWeight = 1; |
2781 | uint64_t FalseWeight = 1; |
2782 | // Copy probabilities from 'SI' to created conditional branch in 'Pred'. |
2783 | if (extractBranchWeights(I: *SI, TrueVal&: TrueWeight, FalseVal&: FalseWeight) && |
2784 | (TrueWeight + FalseWeight) != 0) { |
2785 | SmallVector<BranchProbability, 2> BP; |
2786 | BP.emplace_back(Args: BranchProbability::getBranchProbability( |
2787 | Numerator: TrueWeight, Denominator: TrueWeight + FalseWeight)); |
2788 | BP.emplace_back(Args: BranchProbability::getBranchProbability( |
2789 | Numerator: FalseWeight, Denominator: TrueWeight + FalseWeight)); |
2790 | // Update BPI if exists. |
2791 | if (auto *BPI = getBPI()) |
2792 | BPI->setEdgeProbability(Src: Pred, Probs: BP); |
2793 | } |
2794 | // Set the block frequency of NewBB. |
2795 | if (auto *BFI = getBFI()) { |
2796 | if ((TrueWeight + FalseWeight) == 0) { |
2797 | TrueWeight = 1; |
2798 | FalseWeight = 1; |
2799 | } |
2800 | BranchProbability PredToNewBBProb = BranchProbability::getBranchProbability( |
2801 | Numerator: TrueWeight, Denominator: TrueWeight + FalseWeight); |
2802 | auto NewBBFreq = BFI->getBlockFreq(BB: Pred) * PredToNewBBProb; |
2803 | BFI->setBlockFreq(BB: NewBB, Freq: NewBBFreq); |
2804 | } |
2805 | |
2806 | // The select is now dead. |
2807 | SI->eraseFromParent(); |
2808 | DTU->applyUpdatesPermissive(Updates: {{DominatorTree::Insert, NewBB, BB}, |
2809 | {DominatorTree::Insert, Pred, NewBB}}); |
2810 | |
2811 | // Update any other PHI nodes in BB. |
2812 | for (BasicBlock::iterator BI = BB->begin(); |
2813 | PHINode *Phi = dyn_cast<PHINode>(Val&: BI); ++BI) |
2814 | if (Phi != SIUse) |
2815 | Phi->addIncoming(V: Phi->getIncomingValueForBlock(BB: Pred), BB: NewBB); |
2816 | } |
2817 | |
2818 | bool JumpThreadingPass::tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB) { |
2819 | PHINode *CondPHI = dyn_cast<PHINode>(Val: SI->getCondition()); |
2820 | |
2821 | if (!CondPHI || CondPHI->getParent() != BB) |
2822 | return false; |
2823 | |
2824 | for (unsigned I = 0, E = CondPHI->getNumIncomingValues(); I != E; ++I) { |
2825 | BasicBlock *Pred = CondPHI->getIncomingBlock(i: I); |
2826 | SelectInst *PredSI = dyn_cast<SelectInst>(Val: CondPHI->getIncomingValue(i: I)); |
2827 | |
2828 | // The second and third condition can be potentially relaxed. Currently |
2829 | // the conditions help to simplify the code and allow us to reuse existing |
2830 | // code, developed for tryToUnfoldSelect(CmpInst *, BasicBlock *) |
2831 | if (!PredSI || PredSI->getParent() != Pred || !PredSI->hasOneUse()) |
2832 | continue; |
2833 | |
2834 | BranchInst *PredTerm = dyn_cast<BranchInst>(Val: Pred->getTerminator()); |
2835 | if (!PredTerm || !PredTerm->isUnconditional()) |
2836 | continue; |
2837 | |
2838 | unfoldSelectInstr(Pred, BB, SI: PredSI, SIUse: CondPHI, Idx: I); |
2839 | return true; |
2840 | } |
2841 | return false; |
2842 | } |
2843 | |
2844 | /// tryToUnfoldSelect - Look for blocks of the form |
2845 | /// bb1: |
2846 | /// %a = select |
2847 | /// br bb2 |
2848 | /// |
2849 | /// bb2: |
2850 | /// %p = phi [%a, %bb1] ... |
2851 | /// %c = icmp %p |
2852 | /// br i1 %c |
2853 | /// |
2854 | /// And expand the select into a branch structure if one of its arms allows %c |
2855 | /// to be folded. This later enables threading from bb1 over bb2. |
2856 | bool JumpThreadingPass::tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { |
2857 | BranchInst *CondBr = dyn_cast<BranchInst>(Val: BB->getTerminator()); |
2858 | PHINode *CondLHS = dyn_cast<PHINode>(Val: CondCmp->getOperand(i_nocapture: 0)); |
2859 | Constant *CondRHS = cast<Constant>(Val: CondCmp->getOperand(i_nocapture: 1)); |
2860 | |
2861 | if (!CondBr || !CondBr->isConditional() || !CondLHS || |
2862 | CondLHS->getParent() != BB) |
2863 | return false; |
2864 | |
2865 | for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) { |
2866 | BasicBlock *Pred = CondLHS->getIncomingBlock(i: I); |
2867 | SelectInst *SI = dyn_cast<SelectInst>(Val: CondLHS->getIncomingValue(i: I)); |
2868 | |
2869 | // Look if one of the incoming values is a select in the corresponding |
2870 | // predecessor. |
2871 | if (!SI || SI->getParent() != Pred || !SI->hasOneUse()) |
2872 | continue; |
2873 | |
2874 | BranchInst *PredTerm = dyn_cast<BranchInst>(Val: Pred->getTerminator()); |
2875 | if (!PredTerm || !PredTerm->isUnconditional()) |
2876 | continue; |
2877 | |
2878 | // Now check if one of the select values would allow us to constant fold the |
2879 | // terminator in BB. We don't do the transform if both sides fold, those |
2880 | // cases will be threaded in any case. |
2881 | LazyValueInfo::Tristate LHSFolds = |
2882 | LVI->getPredicateOnEdge(Pred: CondCmp->getPredicate(), V: SI->getOperand(i_nocapture: 1), |
2883 | C: CondRHS, FromBB: Pred, ToBB: BB, CxtI: CondCmp); |
2884 | LazyValueInfo::Tristate RHSFolds = |
2885 | LVI->getPredicateOnEdge(Pred: CondCmp->getPredicate(), V: SI->getOperand(i_nocapture: 2), |
2886 | C: CondRHS, FromBB: Pred, ToBB: BB, CxtI: CondCmp); |
2887 | if ((LHSFolds != LazyValueInfo::Unknown || |
2888 | RHSFolds != LazyValueInfo::Unknown) && |
2889 | LHSFolds != RHSFolds) { |
2890 | unfoldSelectInstr(Pred, BB, SI, SIUse: CondLHS, Idx: I); |
2891 | return true; |
2892 | } |
2893 | } |
2894 | return false; |
2895 | } |
2896 | |
2897 | /// tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the |
2898 | /// same BB in the form |
2899 | /// bb: |
2900 | /// %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ... |
2901 | /// %s = select %p, trueval, falseval |
2902 | /// |
2903 | /// or |
2904 | /// |
2905 | /// bb: |
2906 | /// %p = phi [0, %bb1], [1, %bb2], [0, %bb3], [1, %bb4], ... |
2907 | /// %c = cmp %p, 0 |
2908 | /// %s = select %c, trueval, falseval |
2909 | /// |
2910 | /// And expand the select into a branch structure. This later enables |
2911 | /// jump-threading over bb in this pass. |
2912 | /// |
2913 | /// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold |
2914 | /// select if the associated PHI has at least one constant. If the unfolded |
2915 | /// select is not jump-threaded, it will be folded again in the later |
2916 | /// optimizations. |
2917 | bool JumpThreadingPass::tryToUnfoldSelectInCurrBB(BasicBlock *BB) { |
2918 | // This transform would reduce the quality of msan diagnostics. |
2919 | // Disable this transform under MemorySanitizer. |
2920 | if (BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory)) |
2921 | return false; |
2922 | |
2923 | // If threading this would thread across a loop header, don't thread the edge. |
2924 | // See the comments above findLoopHeaders for justifications and caveats. |
2925 | if (LoopHeaders.count(V: BB)) |
2926 | return false; |
2927 | |
2928 | for (BasicBlock::iterator BI = BB->begin(); |
2929 | PHINode *PN = dyn_cast<PHINode>(Val&: BI); ++BI) { |
2930 | // Look for a Phi having at least one constant incoming value. |
2931 | if (llvm::all_of(Range: PN->incoming_values(), |
2932 | P: [](Value *V) { return !isa<ConstantInt>(Val: V); })) |
2933 | continue; |
2934 | |
2935 | auto isUnfoldCandidate = [BB](SelectInst *SI, Value *V) { |
2936 | using namespace PatternMatch; |
2937 | |
2938 | // Check if SI is in BB and use V as condition. |
2939 | if (SI->getParent() != BB) |
2940 | return false; |
2941 | Value *Cond = SI->getCondition(); |
2942 | bool IsAndOr = match(V: SI, P: m_CombineOr(L: m_LogicalAnd(), R: m_LogicalOr())); |
2943 | return Cond && Cond == V && Cond->getType()->isIntegerTy(Bitwidth: 1) && !IsAndOr; |
2944 | }; |
2945 | |
2946 | SelectInst *SI = nullptr; |
2947 | for (Use &U : PN->uses()) { |
2948 | if (ICmpInst *Cmp = dyn_cast<ICmpInst>(Val: U.getUser())) { |
2949 | // Look for a ICmp in BB that compares PN with a constant and is the |
2950 | // condition of a Select. |
2951 | if (Cmp->getParent() == BB && Cmp->hasOneUse() && |
2952 | isa<ConstantInt>(Val: Cmp->getOperand(i_nocapture: 1 - U.getOperandNo()))) |
2953 | if (SelectInst *SelectI = dyn_cast<SelectInst>(Val: Cmp->user_back())) |
2954 | if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) { |
2955 | SI = SelectI; |
2956 | break; |
2957 | } |
2958 | } else if (SelectInst *SelectI = dyn_cast<SelectInst>(Val: U.getUser())) { |
2959 | // Look for a Select in BB that uses PN as condition. |
2960 | if (isUnfoldCandidate(SelectI, U.get())) { |
2961 | SI = SelectI; |
2962 | break; |
2963 | } |
2964 | } |
2965 | } |
2966 | |
2967 | if (!SI) |
2968 | continue; |
2969 | // Expand the select. |
2970 | Value *Cond = SI->getCondition(); |
2971 | if (!isGuaranteedNotToBeUndefOrPoison(V: Cond, AC: nullptr, CtxI: SI)) |
2972 | Cond = new FreezeInst(Cond, "cond.fr" , SI->getIterator()); |
2973 | MDNode *BranchWeights = getBranchWeightMDNode(I: *SI); |
2974 | Instruction *Term = |
2975 | SplitBlockAndInsertIfThen(Cond, SplitBefore: SI, Unreachable: false, BranchWeights); |
2976 | BasicBlock *SplitBB = SI->getParent(); |
2977 | BasicBlock *NewBB = Term->getParent(); |
2978 | PHINode *NewPN = PHINode::Create(Ty: SI->getType(), NumReservedValues: 2, NameStr: "" , InsertBefore: SI->getIterator()); |
2979 | NewPN->addIncoming(V: SI->getTrueValue(), BB: Term->getParent()); |
2980 | NewPN->addIncoming(V: SI->getFalseValue(), BB); |
2981 | SI->replaceAllUsesWith(V: NewPN); |
2982 | SI->eraseFromParent(); |
2983 | // NewBB and SplitBB are newly created blocks which require insertion. |
2984 | std::vector<DominatorTree::UpdateType> Updates; |
2985 | Updates.reserve(n: (2 * SplitBB->getTerminator()->getNumSuccessors()) + 3); |
2986 | Updates.push_back(x: {DominatorTree::Insert, BB, SplitBB}); |
2987 | Updates.push_back(x: {DominatorTree::Insert, BB, NewBB}); |
2988 | Updates.push_back(x: {DominatorTree::Insert, NewBB, SplitBB}); |
2989 | // BB's successors were moved to SplitBB, update DTU accordingly. |
2990 | for (auto *Succ : successors(BB: SplitBB)) { |
2991 | Updates.push_back(x: {DominatorTree::Delete, BB, Succ}); |
2992 | Updates.push_back(x: {DominatorTree::Insert, SplitBB, Succ}); |
2993 | } |
2994 | DTU->applyUpdatesPermissive(Updates); |
2995 | return true; |
2996 | } |
2997 | return false; |
2998 | } |
2999 | |
3000 | /// Try to propagate a guard from the current BB into one of its predecessors |
3001 | /// in case if another branch of execution implies that the condition of this |
3002 | /// guard is always true. Currently we only process the simplest case that |
3003 | /// looks like: |
3004 | /// |
3005 | /// Start: |
3006 | /// %cond = ... |
3007 | /// br i1 %cond, label %T1, label %F1 |
3008 | /// T1: |
3009 | /// br label %Merge |
3010 | /// F1: |
3011 | /// br label %Merge |
3012 | /// Merge: |
3013 | /// %condGuard = ... |
3014 | /// call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ] |
3015 | /// |
3016 | /// And cond either implies condGuard or !condGuard. In this case all the |
3017 | /// instructions before the guard can be duplicated in both branches, and the |
3018 | /// guard is then threaded to one of them. |
3019 | bool JumpThreadingPass::processGuards(BasicBlock *BB) { |
3020 | using namespace PatternMatch; |
3021 | |
3022 | // We only want to deal with two predecessors. |
3023 | BasicBlock *Pred1, *Pred2; |
3024 | auto PI = pred_begin(BB), PE = pred_end(BB); |
3025 | if (PI == PE) |
3026 | return false; |
3027 | Pred1 = *PI++; |
3028 | if (PI == PE) |
3029 | return false; |
3030 | Pred2 = *PI++; |
3031 | if (PI != PE) |
3032 | return false; |
3033 | if (Pred1 == Pred2) |
3034 | return false; |
3035 | |
3036 | // Try to thread one of the guards of the block. |
3037 | // TODO: Look up deeper than to immediate predecessor? |
3038 | auto *Parent = Pred1->getSinglePredecessor(); |
3039 | if (!Parent || Parent != Pred2->getSinglePredecessor()) |
3040 | return false; |
3041 | |
3042 | if (auto *BI = dyn_cast<BranchInst>(Val: Parent->getTerminator())) |
3043 | for (auto &I : *BB) |
3044 | if (isGuard(U: &I) && threadGuard(BB, Guard: cast<IntrinsicInst>(Val: &I), BI)) |
3045 | return true; |
3046 | |
3047 | return false; |
3048 | } |
3049 | |
3050 | /// Try to propagate the guard from BB which is the lower block of a diamond |
3051 | /// to one of its branches, in case if diamond's condition implies guard's |
3052 | /// condition. |
3053 | bool JumpThreadingPass::threadGuard(BasicBlock *BB, IntrinsicInst *Guard, |
3054 | BranchInst *BI) { |
3055 | assert(BI->getNumSuccessors() == 2 && "Wrong number of successors?" ); |
3056 | assert(BI->isConditional() && "Unconditional branch has 2 successors?" ); |
3057 | Value *GuardCond = Guard->getArgOperand(i: 0); |
3058 | Value *BranchCond = BI->getCondition(); |
3059 | BasicBlock *TrueDest = BI->getSuccessor(i: 0); |
3060 | BasicBlock *FalseDest = BI->getSuccessor(i: 1); |
3061 | |
3062 | auto &DL = BB->getModule()->getDataLayout(); |
3063 | bool TrueDestIsSafe = false; |
3064 | bool FalseDestIsSafe = false; |
3065 | |
3066 | // True dest is safe if BranchCond => GuardCond. |
3067 | auto Impl = isImpliedCondition(LHS: BranchCond, RHS: GuardCond, DL); |
3068 | if (Impl && *Impl) |
3069 | TrueDestIsSafe = true; |
3070 | else { |
3071 | // False dest is safe if !BranchCond => GuardCond. |
3072 | Impl = isImpliedCondition(LHS: BranchCond, RHS: GuardCond, DL, /* LHSIsTrue */ false); |
3073 | if (Impl && *Impl) |
3074 | FalseDestIsSafe = true; |
3075 | } |
3076 | |
3077 | if (!TrueDestIsSafe && !FalseDestIsSafe) |
3078 | return false; |
3079 | |
3080 | BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest; |
3081 | BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest; |
3082 | |
3083 | ValueToValueMapTy UnguardedMapping, GuardedMapping; |
3084 | Instruction *AfterGuard = Guard->getNextNode(); |
3085 | unsigned Cost = |
3086 | getJumpThreadDuplicationCost(TTI, BB, StopAt: AfterGuard, Threshold: BBDupThreshold); |
3087 | if (Cost > BBDupThreshold) |
3088 | return false; |
3089 | // Duplicate all instructions before the guard and the guard itself to the |
3090 | // branch where implication is not proved. |
3091 | BasicBlock *GuardedBlock = DuplicateInstructionsInSplitBetween( |
3092 | BB, PredBB: PredGuardedBlock, StopAt: AfterGuard, ValueMapping&: GuardedMapping, DTU&: *DTU); |
3093 | assert(GuardedBlock && "Could not create the guarded block?" ); |
3094 | // Duplicate all instructions before the guard in the unguarded branch. |
3095 | // Since we have successfully duplicated the guarded block and this block |
3096 | // has fewer instructions, we expect it to succeed. |
3097 | BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween( |
3098 | BB, PredBB: PredUnguardedBlock, StopAt: Guard, ValueMapping&: UnguardedMapping, DTU&: *DTU); |
3099 | assert(UnguardedBlock && "Could not create the unguarded block?" ); |
3100 | LLVM_DEBUG(dbgs() << "Moved guard " << *Guard << " to block " |
3101 | << GuardedBlock->getName() << "\n" ); |
3102 | // Some instructions before the guard may still have uses. For them, we need |
3103 | // to create Phi nodes merging their copies in both guarded and unguarded |
3104 | // branches. Those instructions that have no uses can be just removed. |
3105 | SmallVector<Instruction *, 4> ToRemove; |
3106 | for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI) |
3107 | if (!isa<PHINode>(Val: &*BI)) |
3108 | ToRemove.push_back(Elt: &*BI); |
3109 | |
3110 | BasicBlock::iterator InsertionPoint = BB->getFirstInsertionPt(); |
3111 | assert(InsertionPoint != BB->end() && "Empty block?" ); |
3112 | // Substitute with Phis & remove. |
3113 | for (auto *Inst : reverse(C&: ToRemove)) { |
3114 | if (!Inst->use_empty()) { |
3115 | PHINode *NewPN = PHINode::Create(Ty: Inst->getType(), NumReservedValues: 2); |
3116 | NewPN->addIncoming(V: UnguardedMapping[Inst], BB: UnguardedBlock); |
3117 | NewPN->addIncoming(V: GuardedMapping[Inst], BB: GuardedBlock); |
3118 | NewPN->insertBefore(InsertPos: InsertionPoint); |
3119 | Inst->replaceAllUsesWith(V: NewPN); |
3120 | } |
3121 | Inst->dropDbgRecords(); |
3122 | Inst->eraseFromParent(); |
3123 | } |
3124 | return true; |
3125 | } |
3126 | |
3127 | PreservedAnalyses JumpThreadingPass::getPreservedAnalysis() const { |
3128 | PreservedAnalyses PA; |
3129 | PA.preserve<LazyValueAnalysis>(); |
3130 | PA.preserve<DominatorTreeAnalysis>(); |
3131 | |
3132 | // TODO: We would like to preserve BPI/BFI. Enable once all paths update them. |
3133 | // TODO: Would be nice to verify BPI/BFI consistency as well. |
3134 | return PA; |
3135 | } |
3136 | |
3137 | template <typename AnalysisT> |
3138 | typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() { |
3139 | assert(FAM && "Can't run external analysis without FunctionAnalysisManager" ); |
3140 | |
3141 | // If there were no changes since last call to 'runExternalAnalysis' then all |
3142 | // analysis is either up to date or explicitly invalidated. Just go ahead and |
3143 | // run the "external" analysis. |
3144 | if (!ChangedSinceLastAnalysisUpdate) { |
3145 | assert(!DTU->hasPendingUpdates() && |
3146 | "Lost update of 'ChangedSinceLastAnalysisUpdate'?" ); |
3147 | // Run the "external" analysis. |
3148 | return &FAM->getResult<AnalysisT>(*F); |
3149 | } |
3150 | ChangedSinceLastAnalysisUpdate = false; |
3151 | |
3152 | auto PA = getPreservedAnalysis(); |
3153 | // TODO: This shouldn't be needed once 'getPreservedAnalysis' reports BPI/BFI |
3154 | // as preserved. |
3155 | PA.preserve<BranchProbabilityAnalysis>(); |
3156 | PA.preserve<BlockFrequencyAnalysis>(); |
3157 | // Report everything except explicitly preserved as invalid. |
3158 | FAM->invalidate(IR&: *F, PA); |
3159 | // Update DT/PDT. |
3160 | DTU->flush(); |
3161 | // Make sure DT/PDT are valid before running "external" analysis. |
3162 | assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast)); |
3163 | assert((!DTU->hasPostDomTree() || |
3164 | DTU->getPostDomTree().verify( |
3165 | PostDominatorTree::VerificationLevel::Fast))); |
3166 | // Run the "external" analysis. |
3167 | auto *Result = &FAM->getResult<AnalysisT>(*F); |
3168 | // Update analysis JumpThreading depends on and not explicitly preserved. |
3169 | TTI = &FAM->getResult<TargetIRAnalysis>(IR&: *F); |
3170 | TLI = &FAM->getResult<TargetLibraryAnalysis>(IR&: *F); |
3171 | AA = &FAM->getResult<AAManager>(IR&: *F); |
3172 | |
3173 | return Result; |
3174 | } |
3175 | |
3176 | BranchProbabilityInfo *JumpThreadingPass::getBPI() { |
3177 | if (!BPI) { |
3178 | assert(FAM && "Can't create BPI without FunctionAnalysisManager" ); |
3179 | BPI = FAM->getCachedResult<BranchProbabilityAnalysis>(IR&: *F); |
3180 | } |
3181 | return *BPI; |
3182 | } |
3183 | |
3184 | BlockFrequencyInfo *JumpThreadingPass::getBFI() { |
3185 | if (!BFI) { |
3186 | assert(FAM && "Can't create BFI without FunctionAnalysisManager" ); |
3187 | BFI = FAM->getCachedResult<BlockFrequencyAnalysis>(IR&: *F); |
3188 | } |
3189 | return *BFI; |
3190 | } |
3191 | |
3192 | // Important note on validity of BPI/BFI. JumpThreading tries to preserve |
3193 | // BPI/BFI as it goes. Thus if cached instance exists it will be updated. |
3194 | // Otherwise, new instance of BPI/BFI is created (up to date by definition). |
3195 | BranchProbabilityInfo *JumpThreadingPass::getOrCreateBPI(bool Force) { |
3196 | auto *Res = getBPI(); |
3197 | if (Res) |
3198 | return Res; |
3199 | |
3200 | if (Force) |
3201 | BPI = runExternalAnalysis<BranchProbabilityAnalysis>(); |
3202 | |
3203 | return *BPI; |
3204 | } |
3205 | |
3206 | BlockFrequencyInfo *JumpThreadingPass::getOrCreateBFI(bool Force) { |
3207 | auto *Res = getBFI(); |
3208 | if (Res) |
3209 | return Res; |
3210 | |
3211 | if (Force) |
3212 | BFI = runExternalAnalysis<BlockFrequencyAnalysis>(); |
3213 | |
3214 | return *BFI; |
3215 | } |
3216 | |