/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopPredication.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- LoopPredication.cpp - Guard based loop predication pass -----------===// |
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 | | // The LoopPredication pass tries to convert loop variant range checks to loop |
10 | | // invariant by widening checks across loop iterations. For example, it will |
11 | | // convert |
12 | | // |
13 | | // for (i = 0; i < n; i++) { |
14 | | // guard(i < len); |
15 | | // ... |
16 | | // } |
17 | | // |
18 | | // to |
19 | | // |
20 | | // for (i = 0; i < n; i++) { |
21 | | // guard(n - 1 < len); |
22 | | // ... |
23 | | // } |
24 | | // |
25 | | // After this transformation the condition of the guard is loop invariant, so |
26 | | // loop-unswitch can later unswitch the loop by this condition which basically |
27 | | // predicates the loop by the widened condition: |
28 | | // |
29 | | // if (n - 1 < len) |
30 | | // for (i = 0; i < n; i++) { |
31 | | // ... |
32 | | // } |
33 | | // else |
34 | | // deoptimize |
35 | | // |
36 | | // It's tempting to rely on SCEV here, but it has proven to be problematic. |
37 | | // Generally the facts SCEV provides about the increment step of add |
38 | | // recurrences are true if the backedge of the loop is taken, which implicitly |
39 | | // assumes that the guard doesn't fail. Using these facts to optimize the |
40 | | // guard results in a circular logic where the guard is optimized under the |
41 | | // assumption that it never fails. |
42 | | // |
43 | | // For example, in the loop below the induction variable will be marked as nuw |
44 | | // basing on the guard. Basing on nuw the guard predicate will be considered |
45 | | // monotonic. Given a monotonic condition it's tempting to replace the induction |
46 | | // variable in the condition with its value on the last iteration. But this |
47 | | // transformation is not correct, e.g. e = 4, b = 5 breaks the loop. |
48 | | // |
49 | | // for (int i = b; i != e; i++) |
50 | | // guard(i u< len) |
51 | | // |
52 | | // One of the ways to reason about this problem is to use an inductive proof |
53 | | // approach. Given the loop: |
54 | | // |
55 | | // if (B(0)) { |
56 | | // do { |
57 | | // I = PHI(0, I.INC) |
58 | | // I.INC = I + Step |
59 | | // guard(G(I)); |
60 | | // } while (B(I)); |
61 | | // } |
62 | | // |
63 | | // where B(x) and G(x) are predicates that map integers to booleans, we want a |
64 | | // loop invariant expression M such the following program has the same semantics |
65 | | // as the above: |
66 | | // |
67 | | // if (B(0)) { |
68 | | // do { |
69 | | // I = PHI(0, I.INC) |
70 | | // I.INC = I + Step |
71 | | // guard(G(0) && M); |
72 | | // } while (B(I)); |
73 | | // } |
74 | | // |
75 | | // One solution for M is M = forall X . (G(X) && B(X)) => G(X + Step) |
76 | | // |
77 | | // Informal proof that the transformation above is correct: |
78 | | // |
79 | | // By the definition of guards we can rewrite the guard condition to: |
80 | | // G(I) && G(0) && M |
81 | | // |
82 | | // Let's prove that for each iteration of the loop: |
83 | | // G(0) && M => G(I) |
84 | | // And the condition above can be simplified to G(Start) && M. |
85 | | // |
86 | | // Induction base. |
87 | | // G(0) && M => G(0) |
88 | | // |
89 | | // Induction step. Assuming G(0) && M => G(I) on the subsequent |
90 | | // iteration: |
91 | | // |
92 | | // B(I) is true because it's the backedge condition. |
93 | | // G(I) is true because the backedge is guarded by this condition. |
94 | | // |
95 | | // So M = forall X . (G(X) && B(X)) => G(X + Step) implies G(I + Step). |
96 | | // |
97 | | // Note that we can use anything stronger than M, i.e. any condition which |
98 | | // implies M. |
99 | | // |
100 | | // When S = 1 (i.e. forward iterating loop), the transformation is supported |
101 | | // when: |
102 | | // * The loop has a single latch with the condition of the form: |
103 | | // B(X) = latchStart + X <pred> latchLimit, |
104 | | // where <pred> is u<, u<=, s<, or s<=. |
105 | | // * The guard condition is of the form |
106 | | // G(X) = guardStart + X u< guardLimit |
107 | | // |
108 | | // For the ult latch comparison case M is: |
109 | | // forall X . guardStart + X u< guardLimit && latchStart + X <u latchLimit => |
110 | | // guardStart + X + 1 u< guardLimit |
111 | | // |
112 | | // The only way the antecedent can be true and the consequent can be false is |
113 | | // if |
114 | | // X == guardLimit - 1 - guardStart |
115 | | // (and guardLimit is non-zero, but we won't use this latter fact). |
116 | | // If X == guardLimit - 1 - guardStart then the second half of the antecedent is |
117 | | // latchStart + guardLimit - 1 - guardStart u< latchLimit |
118 | | // and its negation is |
119 | | // latchStart + guardLimit - 1 - guardStart u>= latchLimit |
120 | | // |
121 | | // In other words, if |
122 | | // latchLimit u<= latchStart + guardLimit - 1 - guardStart |
123 | | // then: |
124 | | // (the ranges below are written in ConstantRange notation, where [A, B) is the |
125 | | // set for (I = A; I != B; I++ /*maywrap*/) yield(I);) |
126 | | // |
127 | | // forall X . guardStart + X u< guardLimit && |
128 | | // latchStart + X u< latchLimit => |
129 | | // guardStart + X + 1 u< guardLimit |
130 | | // == forall X . guardStart + X u< guardLimit && |
131 | | // latchStart + X u< latchStart + guardLimit - 1 - guardStart => |
132 | | // guardStart + X + 1 u< guardLimit |
133 | | // == forall X . (guardStart + X) in [0, guardLimit) && |
134 | | // (latchStart + X) in [0, latchStart + guardLimit - 1 - guardStart) => |
135 | | // (guardStart + X + 1) in [0, guardLimit) |
136 | | // == forall X . X in [-guardStart, guardLimit - guardStart) && |
137 | | // X in [-latchStart, guardLimit - 1 - guardStart) => |
138 | | // X in [-guardStart - 1, guardLimit - guardStart - 1) |
139 | | // == true |
140 | | // |
141 | | // So the widened condition is: |
142 | | // guardStart u< guardLimit && |
143 | | // latchStart + guardLimit - 1 - guardStart u>= latchLimit |
144 | | // Similarly for ule condition the widened condition is: |
145 | | // guardStart u< guardLimit && |
146 | | // latchStart + guardLimit - 1 - guardStart u> latchLimit |
147 | | // For slt condition the widened condition is: |
148 | | // guardStart u< guardLimit && |
149 | | // latchStart + guardLimit - 1 - guardStart s>= latchLimit |
150 | | // For sle condition the widened condition is: |
151 | | // guardStart u< guardLimit && |
152 | | // latchStart + guardLimit - 1 - guardStart s> latchLimit |
153 | | // |
154 | | // When S = -1 (i.e. reverse iterating loop), the transformation is supported |
155 | | // when: |
156 | | // * The loop has a single latch with the condition of the form: |
157 | | // B(X) = X <pred> latchLimit, where <pred> is u>, u>=, s>, or s>=. |
158 | | // * The guard condition is of the form |
159 | | // G(X) = X - 1 u< guardLimit |
160 | | // |
161 | | // For the ugt latch comparison case M is: |
162 | | // forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit |
163 | | // |
164 | | // The only way the antecedent can be true and the consequent can be false is if |
165 | | // X == 1. |
166 | | // If X == 1 then the second half of the antecedent is |
167 | | // 1 u> latchLimit, and its negation is latchLimit u>= 1. |
168 | | // |
169 | | // So the widened condition is: |
170 | | // guardStart u< guardLimit && latchLimit u>= 1. |
171 | | // Similarly for sgt condition the widened condition is: |
172 | | // guardStart u< guardLimit && latchLimit s>= 1. |
173 | | // For uge condition the widened condition is: |
174 | | // guardStart u< guardLimit && latchLimit u> 1. |
175 | | // For sge condition the widened condition is: |
176 | | // guardStart u< guardLimit && latchLimit s> 1. |
177 | | //===----------------------------------------------------------------------===// |
178 | | |
179 | | #include "llvm/Transforms/Scalar/LoopPredication.h" |
180 | | #include "llvm/ADT/Statistic.h" |
181 | | #include "llvm/Analysis/AliasAnalysis.h" |
182 | | #include "llvm/Analysis/BranchProbabilityInfo.h" |
183 | | #include "llvm/Analysis/GuardUtils.h" |
184 | | #include "llvm/Analysis/LoopInfo.h" |
185 | | #include "llvm/Analysis/LoopPass.h" |
186 | | #include "llvm/Analysis/ScalarEvolution.h" |
187 | | #include "llvm/Analysis/ScalarEvolutionExpander.h" |
188 | | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
189 | | #include "llvm/IR/Function.h" |
190 | | #include "llvm/IR/GlobalValue.h" |
191 | | #include "llvm/IR/IntrinsicInst.h" |
192 | | #include "llvm/IR/Module.h" |
193 | | #include "llvm/IR/PatternMatch.h" |
194 | | #include "llvm/Pass.h" |
195 | | #include "llvm/Support/Debug.h" |
196 | | #include "llvm/Transforms/Scalar.h" |
197 | | #include "llvm/Transforms/Utils/Local.h" |
198 | | #include "llvm/Transforms/Utils/LoopUtils.h" |
199 | | |
200 | | #define DEBUG_TYPE "loop-predication" |
201 | | |
202 | | STATISTIC(TotalConsidered, "Number of guards considered"); |
203 | | STATISTIC(TotalWidened, "Number of checks widened"); |
204 | | |
205 | | using namespace llvm; |
206 | | |
207 | | static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation", |
208 | | cl::Hidden, cl::init(true)); |
209 | | |
210 | | static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop", |
211 | | cl::Hidden, cl::init(true)); |
212 | | |
213 | | static cl::opt<bool> |
214 | | SkipProfitabilityChecks("loop-predication-skip-profitability-checks", |
215 | | cl::Hidden, cl::init(false)); |
216 | | |
217 | | // This is the scale factor for the latch probability. We use this during |
218 | | // profitability analysis to find other exiting blocks that have a much higher |
219 | | // probability of exiting the loop instead of loop exiting via latch. |
220 | | // This value should be greater than 1 for a sane profitability check. |
221 | | static cl::opt<float> LatchExitProbabilityScale( |
222 | | "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0), |
223 | | cl::desc("scale factor for the latch probability. Value should be greater " |
224 | | "than 1. Lower values are ignored")); |
225 | | |
226 | | static cl::opt<bool> PredicateWidenableBranchGuards( |
227 | | "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden, |
228 | | cl::desc("Whether or not we should predicate guards " |
229 | | "expressed as widenable branches to deoptimize blocks"), |
230 | | cl::init(true)); |
231 | | |
232 | | namespace { |
233 | | /// Represents an induction variable check: |
234 | | /// icmp Pred, <induction variable>, <loop invariant limit> |
235 | | struct LoopICmp { |
236 | | ICmpInst::Predicate Pred; |
237 | | const SCEVAddRecExpr *IV; |
238 | | const SCEV *Limit; |
239 | | LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV, |
240 | | const SCEV *Limit) |
241 | 420 | : Pred(Pred), IV(IV), Limit(Limit) {} |
242 | 212 | LoopICmp() {} |
243 | 0 | void dump() { |
244 | 0 | dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV |
245 | 0 | << ", Limit = " << *Limit << "\n"; |
246 | 0 | } |
247 | | }; |
248 | | |
249 | | class LoopPredication { |
250 | | AliasAnalysis *AA; |
251 | | ScalarEvolution *SE; |
252 | | BranchProbabilityInfo *BPI; |
253 | | |
254 | | Loop *L; |
255 | | const DataLayout *DL; |
256 | | BasicBlock *Preheader; |
257 | | LoopICmp LatchCheck; |
258 | | |
259 | | bool isSupportedStep(const SCEV* Step); |
260 | | Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI); |
261 | | Optional<LoopICmp> parseLoopLatchICmp(); |
262 | | |
263 | | /// Return an insertion point suitable for inserting a safe to speculate |
264 | | /// instruction whose only user will be 'User' which has operands 'Ops'. A |
265 | | /// trivial result would be the at the User itself, but we try to return a |
266 | | /// loop invariant location if possible. |
267 | | Instruction *findInsertPt(Instruction *User, ArrayRef<Value*> Ops); |
268 | | /// Same as above, *except* that this uses the SCEV definition of invariant |
269 | | /// which is that an expression *can be made* invariant via SCEVExpander. |
270 | | /// Thus, this version is only suitable for finding an insert point to be be |
271 | | /// passed to SCEVExpander! |
272 | | Instruction *findInsertPt(Instruction *User, ArrayRef<const SCEV*> Ops); |
273 | | |
274 | | /// Return true if the value is known to produce a single fixed value across |
275 | | /// all iterations on which it executes. Note that this does not imply |
276 | | /// speculation safety. That must be established seperately. |
277 | | bool isLoopInvariantValue(const SCEV* S); |
278 | | |
279 | | Value *expandCheck(SCEVExpander &Expander, Instruction *Guard, |
280 | | ICmpInst::Predicate Pred, const SCEV *LHS, |
281 | | const SCEV *RHS); |
282 | | |
283 | | Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander, |
284 | | Instruction *Guard); |
285 | | Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, |
286 | | LoopICmp RangeCheck, |
287 | | SCEVExpander &Expander, |
288 | | Instruction *Guard); |
289 | | Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, |
290 | | LoopICmp RangeCheck, |
291 | | SCEVExpander &Expander, |
292 | | Instruction *Guard); |
293 | | unsigned collectChecks(SmallVectorImpl<Value *> &Checks, Value *Condition, |
294 | | SCEVExpander &Expander, Instruction *Guard); |
295 | | bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander); |
296 | | bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander); |
297 | | // If the loop always exits through another block in the loop, we should not |
298 | | // predicate based on the latch check. For example, the latch check can be a |
299 | | // very coarse grained check and there can be more fine grained exit checks |
300 | | // within the loop. We identify such unprofitable loops through BPI. |
301 | | bool isLoopProfitableToPredicate(); |
302 | | |
303 | | public: |
304 | | LoopPredication(AliasAnalysis *AA, ScalarEvolution *SE, |
305 | | BranchProbabilityInfo *BPI) |
306 | 208 | : AA(AA), SE(SE), BPI(BPI){}; |
307 | | bool runOnLoop(Loop *L); |
308 | | }; |
309 | | |
310 | | class LoopPredicationLegacyPass : public LoopPass { |
311 | | public: |
312 | | static char ID; |
313 | 8 | LoopPredicationLegacyPass() : LoopPass(ID) { |
314 | 8 | initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry()); |
315 | 8 | } |
316 | | |
317 | 8 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
318 | 8 | AU.addRequired<BranchProbabilityInfoWrapperPass>(); |
319 | 8 | getLoopAnalysisUsage(AU); |
320 | 8 | } |
321 | | |
322 | 92 | bool runOnLoop(Loop *L, LPPassManager &LPM) override { |
323 | 92 | if (skipLoop(L)) |
324 | 0 | return false; |
325 | 92 | auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); |
326 | 92 | BranchProbabilityInfo &BPI = |
327 | 92 | getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI(); |
328 | 92 | auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); |
329 | 92 | LoopPredication LP(AA, SE, &BPI); |
330 | 92 | return LP.runOnLoop(L); |
331 | 92 | } |
332 | | }; |
333 | | |
334 | | char LoopPredicationLegacyPass::ID = 0; |
335 | | } // end namespace llvm |
336 | | |
337 | 36.0k | INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication", |
338 | 36.0k | "Loop predication", false, false) |
339 | 36.0k | INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass) |
340 | 36.0k | INITIALIZE_PASS_DEPENDENCY(LoopPass) |
341 | 36.0k | INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication", |
342 | | "Loop predication", false, false) |
343 | | |
344 | 0 | Pass *llvm::createLoopPredicationPass() { |
345 | 0 | return new LoopPredicationLegacyPass(); |
346 | 0 | } |
347 | | |
348 | | PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM, |
349 | | LoopStandardAnalysisResults &AR, |
350 | 116 | LPMUpdater &U) { |
351 | 116 | const auto &FAM = |
352 | 116 | AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager(); |
353 | 116 | Function *F = L.getHeader()->getParent(); |
354 | 116 | auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F); |
355 | 116 | LoopPredication LP(&AR.AA, &AR.SE, BPI); |
356 | 116 | if (!LP.runOnLoop(&L)) |
357 | 39 | return PreservedAnalyses::all(); |
358 | 77 | |
359 | 77 | return getLoopPassPreservedAnalyses(); |
360 | 77 | } |
361 | | |
362 | | Optional<LoopICmp> |
363 | 435 | LoopPredication::parseLoopICmp(ICmpInst *ICI) { |
364 | 435 | auto Pred = ICI->getPredicate(); |
365 | 435 | auto *LHS = ICI->getOperand(0); |
366 | 435 | auto *RHS = ICI->getOperand(1); |
367 | 435 | |
368 | 435 | const SCEV *LHSS = SE->getSCEV(LHS); |
369 | 435 | if (isa<SCEVCouldNotCompute>(LHSS)) |
370 | 0 | return None; |
371 | 435 | const SCEV *RHSS = SE->getSCEV(RHS); |
372 | 435 | if (isa<SCEVCouldNotCompute>(RHSS)) |
373 | 0 | return None; |
374 | 435 | |
375 | 435 | // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV |
376 | 435 | if (SE->isLoopInvariant(LHSS, L)) { |
377 | 35 | std::swap(LHS, RHS); |
378 | 35 | std::swap(LHSS, RHSS); |
379 | 35 | Pred = ICmpInst::getSwappedPredicate(Pred); |
380 | 35 | } |
381 | 435 | |
382 | 435 | const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS); |
383 | 435 | if (!AR || AR->getLoop() != L422 ) |
384 | 15 | return None; |
385 | 420 | |
386 | 420 | return LoopICmp(Pred, AR, RHSS); |
387 | 420 | } |
388 | | |
389 | | Value *LoopPredication::expandCheck(SCEVExpander &Expander, |
390 | | Instruction *Guard, |
391 | | ICmpInst::Predicate Pred, const SCEV *LHS, |
392 | 330 | const SCEV *RHS) { |
393 | 330 | Type *Ty = LHS->getType(); |
394 | 330 | assert(Ty == RHS->getType() && "expandCheck operands have different types?"); |
395 | 330 | |
396 | 330 | if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) { |
397 | 322 | IRBuilder<> Builder(Guard); |
398 | 322 | if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS)) |
399 | 7 | return Builder.getTrue(); |
400 | 315 | if (SE->isLoopEntryGuardedByCond(L, ICmpInst::getInversePredicate(Pred), |
401 | 315 | LHS, RHS)) |
402 | 6 | return Builder.getFalse(); |
403 | 317 | } |
404 | 317 | |
405 | 317 | Value *LHSV = Expander.expandCodeFor(LHS, Ty, findInsertPt(Guard, {LHS})); |
406 | 317 | Value *RHSV = Expander.expandCodeFor(RHS, Ty, findInsertPt(Guard, {RHS})); |
407 | 317 | IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV})); |
408 | 317 | return Builder.CreateICmp(Pred, LHSV, RHSV); |
409 | 317 | } |
410 | | |
411 | | |
412 | | // Returns true if its safe to truncate the IV to RangeCheckType. |
413 | | // When the IV type is wider than the range operand type, we can still do loop |
414 | | // predication, by generating SCEVs for the range and latch that are of the |
415 | | // same type. We achieve this by generating a SCEV truncate expression for the |
416 | | // latch IV. This is done iff truncation of the IV is a safe operation, |
417 | | // without loss of information. |
418 | | // Another way to achieve this is by generating a wider type SCEV for the |
419 | | // range check operand, however, this needs a more involved check that |
420 | | // operands do not overflow. This can lead to loss of information when the |
421 | | // range operand is of the form: add i32 %offset, %iv. We need to prove that |
422 | | // sext(x + y) is same as sext(x) + sext(y). |
423 | | // This function returns true if we can safely represent the IV type in |
424 | | // the RangeCheckType without loss of information. |
425 | | static bool isSafeToTruncateWideIVType(const DataLayout &DL, |
426 | | ScalarEvolution &SE, |
427 | | const LoopICmp LatchCheck, |
428 | 9 | Type *RangeCheckType) { |
429 | 9 | if (!EnableIVTruncation) |
430 | 0 | return false; |
431 | 9 | assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()) > |
432 | 9 | DL.getTypeSizeInBits(RangeCheckType) && |
433 | 9 | "Expected latch check IV type to be larger than range check operand " |
434 | 9 | "type!"); |
435 | 9 | // The start and end values of the IV should be known. This is to guarantee |
436 | 9 | // that truncating the wide type will not lose information. |
437 | 9 | auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit); |
438 | 9 | auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart()); |
439 | 9 | if (!Limit || !Start4 ) |
440 | 5 | return false; |
441 | 4 | // This check makes sure that the IV does not change sign during loop |
442 | 4 | // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE, |
443 | 4 | // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the |
444 | 4 | // IV wraps around, and the truncation of the IV would lose the range of |
445 | 4 | // iterations between 2^32 and 2^64. |
446 | 4 | bool Increasing; |
447 | 4 | if (!SE.isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing)) |
448 | 0 | return false; |
449 | 4 | // The active bits should be less than the bits in the RangeCheckType. This |
450 | 4 | // guarantees that truncating the latch check to RangeCheckType is a safe |
451 | 4 | // operation. |
452 | 4 | auto RangeCheckTypeBitSize = DL.getTypeSizeInBits(RangeCheckType); |
453 | 4 | return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize && |
454 | 4 | Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize; |
455 | 4 | } |
456 | | |
457 | | |
458 | | // Return an LoopICmp describing a latch check equivlent to LatchCheck but with |
459 | | // the requested type if safe to do so. May involve the use of a new IV. |
460 | | static Optional<LoopICmp> generateLoopLatchCheck(const DataLayout &DL, |
461 | | ScalarEvolution &SE, |
462 | | const LoopICmp LatchCheck, |
463 | 187 | Type *RangeCheckType) { |
464 | 187 | |
465 | 187 | auto *LatchType = LatchCheck.IV->getType(); |
466 | 187 | if (RangeCheckType == LatchType) |
467 | 178 | return LatchCheck; |
468 | 9 | // For now, bail out if latch type is narrower than range type. |
469 | 9 | if (DL.getTypeSizeInBits(LatchType) < DL.getTypeSizeInBits(RangeCheckType)) |
470 | 0 | return None; |
471 | 9 | if (!isSafeToTruncateWideIVType(DL, SE, LatchCheck, RangeCheckType)) |
472 | 5 | return None; |
473 | 4 | // We can now safely identify the truncated version of the IV and limit for |
474 | 4 | // RangeCheckType. |
475 | 4 | LoopICmp NewLatchCheck; |
476 | 4 | NewLatchCheck.Pred = LatchCheck.Pred; |
477 | 4 | NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>( |
478 | 4 | SE.getTruncateExpr(LatchCheck.IV, RangeCheckType)); |
479 | 4 | if (!NewLatchCheck.IV) |
480 | 0 | return None; |
481 | 4 | NewLatchCheck.Limit = SE.getTruncateExpr(LatchCheck.Limit, RangeCheckType); |
482 | 4 | LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType |
483 | 4 | << "can be represented as range check type:" |
484 | 4 | << *RangeCheckType << "\n"); |
485 | 4 | LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n"); |
486 | 4 | LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n"); |
487 | 4 | return NewLatchCheck; |
488 | 4 | } |
489 | | |
490 | 398 | bool LoopPredication::isSupportedStep(const SCEV* Step) { |
491 | 398 | return Step->isOne() || (40 Step->isAllOnesValue()40 && EnableCountDownLoop26 ); |
492 | 398 | } |
493 | | |
494 | | Instruction *LoopPredication::findInsertPt(Instruction *Use, |
495 | 629 | ArrayRef<Value*> Ops) { |
496 | 629 | for (Value *Op : Ops) |
497 | 1.17k | if (!L->isLoopInvariant(Op)) |
498 | 102 | return Use; |
499 | 629 | return Preheader->getTerminator()527 ; |
500 | 629 | } |
501 | | |
502 | | Instruction *LoopPredication::findInsertPt(Instruction *Use, |
503 | 634 | ArrayRef<const SCEV*> Ops) { |
504 | 634 | // Subtlety: SCEV considers things to be invariant if the value produced is |
505 | 634 | // the same across iterations. This is not the same as being able to |
506 | 634 | // evaluate outside the loop, which is what we actually need here. |
507 | 634 | for (const SCEV *Op : Ops) |
508 | 634 | if (!SE->isLoopInvariant(Op, L) || |
509 | 634 | !isSafeToExpandAt(Op, Preheader->getTerminator(), *SE)626 ) |
510 | 18 | return Use; |
511 | 634 | return Preheader->getTerminator()616 ; |
512 | 634 | } |
513 | | |
514 | 702 | bool LoopPredication::isLoopInvariantValue(const SCEV* S) { |
515 | 702 | // Handling expressions which produce invariant results, but *haven't* yet |
516 | 702 | // been removed from the loop serves two important purposes. |
517 | 702 | // 1) Most importantly, it resolves a pass ordering cycle which would |
518 | 702 | // otherwise need us to iteration licm, loop-predication, and either |
519 | 702 | // loop-unswitch or loop-peeling to make progress on examples with lots of |
520 | 702 | // predicable range checks in a row. (Since, in the general case, we can't |
521 | 702 | // hoist the length checks until the dominating checks have been discharged |
522 | 702 | // as we can't prove doing so is safe.) |
523 | 702 | // 2) As a nice side effect, this exposes the value of peeling or unswitching |
524 | 702 | // much more obviously in the IR. Otherwise, the cost modeling for other |
525 | 702 | // transforms would end up needing to duplicate all of this logic to model a |
526 | 702 | // check which becomes predictable based on a modeled peel or unswitch. |
527 | 702 | // |
528 | 702 | // The cost of doing so in the worst case is an extra fill from the stack in |
529 | 702 | // the loop to materialize the loop invariant test value instead of checking |
530 | 702 | // against the original IV which is presumable in a register inside the loop. |
531 | 702 | // Such cases are presumably rare, and hint at missing oppurtunities for |
532 | 702 | // other passes. |
533 | 702 | |
534 | 702 | if (SE->isLoopInvariant(S, L)) |
535 | 685 | // Note: This the SCEV variant, so the original Value* may be within the |
536 | 685 | // loop even though SCEV has proven it is loop invariant. |
537 | 685 | return true; |
538 | 17 | |
539 | 17 | // Handle a particular important case which SCEV doesn't yet know about which |
540 | 17 | // shows up in range checks on arrays with immutable lengths. |
541 | 17 | // TODO: This should be sunk inside SCEV. |
542 | 17 | if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) |
543 | 12 | if (const auto *LI = dyn_cast<LoadInst>(U->getValue())) |
544 | 12 | if (LI->isUnordered() && L->hasLoopInvariantOperands(LI)) |
545 | 10 | if (AA->pointsToConstantMemory(LI->getOperand(0)) || |
546 | 10 | LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr8 ) |
547 | 8 | return true; |
548 | 9 | return false; |
549 | 9 | } |
550 | | |
551 | | Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop( |
552 | | LoopICmp LatchCheck, LoopICmp RangeCheck, |
553 | 168 | SCEVExpander &Expander, Instruction *Guard) { |
554 | 168 | auto *Ty = RangeCheck.IV->getType(); |
555 | 168 | // Generate the widened condition for the forward loop: |
556 | 168 | // guardStart u< guardLimit && |
557 | 168 | // latchLimit <pred> guardLimit - 1 - guardStart + latchStart |
558 | 168 | // where <pred> depends on the latch condition predicate. See the file |
559 | 168 | // header comment for the reasoning. |
560 | 168 | // guardLimit - guardStart + latchStart - 1 |
561 | 168 | const SCEV *GuardStart = RangeCheck.IV->getStart(); |
562 | 168 | const SCEV *GuardLimit = RangeCheck.Limit; |
563 | 168 | const SCEV *LatchStart = LatchCheck.IV->getStart(); |
564 | 168 | const SCEV *LatchLimit = LatchCheck.Limit; |
565 | 168 | // Subtlety: We need all the values to be *invariant* across all iterations, |
566 | 168 | // but we only need to check expansion safety for those which *aren't* |
567 | 168 | // already guaranteed to dominate the guard. |
568 | 168 | if (!isLoopInvariantValue(GuardStart) || |
569 | 168 | !isLoopInvariantValue(GuardLimit) || |
570 | 168 | !isLoopInvariantValue(LatchStart)159 || |
571 | 168 | !isLoopInvariantValue(LatchLimit)159 ) { |
572 | 9 | LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); |
573 | 9 | return None; |
574 | 9 | } |
575 | 159 | if (!isSafeToExpandAt(LatchStart, Guard, *SE) || |
576 | 159 | !isSafeToExpandAt(LatchLimit, Guard, *SE)157 ) { |
577 | 6 | LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); |
578 | 6 | return None; |
579 | 6 | } |
580 | 153 | |
581 | 153 | // guardLimit - guardStart + latchStart - 1 |
582 | 153 | const SCEV *RHS = |
583 | 153 | SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart), |
584 | 153 | SE->getMinusSCEV(LatchStart, SE->getOne(Ty))); |
585 | 153 | auto LimitCheckPred = |
586 | 153 | ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred); |
587 | 153 | |
588 | 153 | LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n"); |
589 | 153 | LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n"); |
590 | 153 | LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n"); |
591 | 153 | |
592 | 153 | auto *LimitCheck = |
593 | 153 | expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS); |
594 | 153 | auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred, |
595 | 153 | GuardStart, GuardLimit); |
596 | 153 | IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck})); |
597 | 153 | return Builder.CreateAnd(FirstIterationCheck, LimitCheck); |
598 | 153 | } |
599 | | |
600 | | Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop( |
601 | | LoopICmp LatchCheck, LoopICmp RangeCheck, |
602 | 12 | SCEVExpander &Expander, Instruction *Guard) { |
603 | 12 | auto *Ty = RangeCheck.IV->getType(); |
604 | 12 | const SCEV *GuardStart = RangeCheck.IV->getStart(); |
605 | 12 | const SCEV *GuardLimit = RangeCheck.Limit; |
606 | 12 | const SCEV *LatchStart = LatchCheck.IV->getStart(); |
607 | 12 | const SCEV *LatchLimit = LatchCheck.Limit; |
608 | 12 | // Subtlety: We need all the values to be *invariant* across all iterations, |
609 | 12 | // but we only need to check expansion safety for those which *aren't* |
610 | 12 | // already guaranteed to dominate the guard. |
611 | 12 | if (!isLoopInvariantValue(GuardStart) || |
612 | 12 | !isLoopInvariantValue(GuardLimit) || |
613 | 12 | !isLoopInvariantValue(LatchStart) || |
614 | 12 | !isLoopInvariantValue(LatchLimit)) { |
615 | 0 | LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); |
616 | 0 | return None; |
617 | 0 | } |
618 | 12 | if (!isSafeToExpandAt(LatchStart, Guard, *SE) || |
619 | 12 | !isSafeToExpandAt(LatchLimit, Guard, *SE)) { |
620 | 0 | LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); |
621 | 0 | return None; |
622 | 0 | } |
623 | 12 | // The decrement of the latch check IV should be the same as the |
624 | 12 | // rangeCheckIV. |
625 | 12 | auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE); |
626 | 12 | if (RangeCheck.IV != PostDecLatchCheckIV) { |
627 | 0 | LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: " |
628 | 0 | << *PostDecLatchCheckIV |
629 | 0 | << " and RangeCheckIV: " << *RangeCheck.IV << "\n"); |
630 | 0 | return None; |
631 | 0 | } |
632 | 12 | |
633 | 12 | // Generate the widened condition for CountDownLoop: |
634 | 12 | // guardStart u< guardLimit && |
635 | 12 | // latchLimit <pred> 1. |
636 | 12 | // See the header comment for reasoning of the checks. |
637 | 12 | auto LimitCheckPred = |
638 | 12 | ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred); |
639 | 12 | auto *FirstIterationCheck = expandCheck(Expander, Guard, |
640 | 12 | ICmpInst::ICMP_ULT, |
641 | 12 | GuardStart, GuardLimit); |
642 | 12 | auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, |
643 | 12 | SE->getOne(Ty)); |
644 | 12 | IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck})); |
645 | 12 | return Builder.CreateAnd(FirstIterationCheck, LimitCheck); |
646 | 12 | } |
647 | | |
648 | | static void normalizePredicate(ScalarEvolution *SE, Loop *L, |
649 | 197 | LoopICmp& RC) { |
650 | 197 | // LFTR canonicalizes checks to the ICMP_NE/EQ form; normalize back to the |
651 | 197 | // ULT/UGE form for ease of handling by our caller. |
652 | 197 | if (ICmpInst::isEquality(RC.Pred) && |
653 | 197 | RC.IV->getStepRecurrence(*SE)->isOne()17 && |
654 | 197 | SE->isKnownPredicate(ICmpInst::ICMP_ULE, RC.IV->getStart(), RC.Limit)17 ) |
655 | 8 | RC.Pred = RC.Pred == ICmpInst::ICMP_NE ? |
656 | 8 | ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE0 ; |
657 | 197 | } |
658 | | |
659 | | |
660 | | /// If ICI can be widened to a loop invariant condition emits the loop |
661 | | /// invariant condition in the loop preheader and return it, otherwise |
662 | | /// returns None. |
663 | | Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI, |
664 | | SCEVExpander &Expander, |
665 | 229 | Instruction *Guard) { |
666 | 229 | LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n"); |
667 | 229 | LLVM_DEBUG(ICI->dump()); |
668 | 229 | |
669 | 229 | // parseLoopStructure guarantees that the latch condition is: |
670 | 229 | // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=. |
671 | 229 | // We are looking for the range checks of the form: |
672 | 229 | // i u< guardLimit |
673 | 229 | auto RangeCheck = parseLoopICmp(ICI); |
674 | 229 | if (!RangeCheck) { |
675 | 15 | LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n"); |
676 | 15 | return None; |
677 | 15 | } |
678 | 214 | LLVM_DEBUG(dbgs() << "Guard check:\n"); |
679 | 214 | LLVM_DEBUG(RangeCheck->dump()); |
680 | 214 | if (RangeCheck->Pred != ICmpInst::ICMP_ULT) { |
681 | 22 | LLVM_DEBUG(dbgs() << "Unsupported range check predicate(" |
682 | 22 | << RangeCheck->Pred << ")!\n"); |
683 | 22 | return None; |
684 | 22 | } |
685 | 192 | auto *RangeCheckIV = RangeCheck->IV; |
686 | 192 | if (!RangeCheckIV->isAffine()) { |
687 | 0 | LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n"); |
688 | 0 | return None; |
689 | 0 | } |
690 | 192 | auto *Step = RangeCheckIV->getStepRecurrence(*SE); |
691 | 192 | // We cannot just compare with latch IV step because the latch and range IVs |
692 | 192 | // may have different types. |
693 | 192 | if (!isSupportedStep(Step)) { |
694 | 5 | LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n"); |
695 | 5 | return None; |
696 | 5 | } |
697 | 187 | auto *Ty = RangeCheckIV->getType(); |
698 | 187 | auto CurrLatchCheckOpt = generateLoopLatchCheck(*DL, *SE, LatchCheck, Ty); |
699 | 187 | if (!CurrLatchCheckOpt) { |
700 | 5 | LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check " |
701 | 5 | "corresponding to range type: " |
702 | 5 | << *Ty << "\n"); |
703 | 5 | return None; |
704 | 5 | } |
705 | 182 | |
706 | 182 | LoopICmp CurrLatchCheck = *CurrLatchCheckOpt; |
707 | 182 | // At this point, the range and latch step should have the same type, but need |
708 | 182 | // not have the same value (we support both 1 and -1 steps). |
709 | 182 | assert(Step->getType() == |
710 | 182 | CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() && |
711 | 182 | "Range and latch steps should be of same type!"); |
712 | 182 | if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) { |
713 | 2 | LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n"); |
714 | 2 | return None; |
715 | 2 | } |
716 | 180 | |
717 | 180 | if (Step->isOne()) |
718 | 168 | return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck, |
719 | 168 | Expander, Guard); |
720 | 12 | else { |
721 | 12 | assert(Step->isAllOnesValue() && "Step should be -1!"); |
722 | 12 | return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck, |
723 | 12 | Expander, Guard); |
724 | 12 | } |
725 | 180 | } |
726 | | |
727 | | unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks, |
728 | | Value *Condition, |
729 | | SCEVExpander &Expander, |
730 | 204 | Instruction *Guard) { |
731 | 204 | unsigned NumWidened = 0; |
732 | 204 | // The guard condition is expected to be in form of: |
733 | 204 | // cond1 && cond2 && cond3 ... |
734 | 204 | // Iterate over subconditions looking for icmp conditions which can be |
735 | 204 | // widened across loop iterations. Widening these conditions remember the |
736 | 204 | // resulting list of subconditions in Checks vector. |
737 | 204 | SmallVector<Value *, 4> Worklist(1, Condition); |
738 | 204 | SmallPtrSet<Value *, 4> Visited; |
739 | 204 | Value *WideableCond = nullptr; |
740 | 826 | do { |
741 | 826 | Value *Condition = Worklist.pop_back_val(); |
742 | 826 | if (!Visited.insert(Condition).second) |
743 | 194 | continue; |
744 | 632 | |
745 | 632 | Value *LHS, *RHS; |
746 | 632 | using namespace llvm::PatternMatch; |
747 | 632 | if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) { |
748 | 311 | Worklist.push_back(LHS); |
749 | 311 | Worklist.push_back(RHS); |
750 | 311 | continue; |
751 | 311 | } |
752 | 321 | |
753 | 321 | if (match(Condition, |
754 | 321 | m_Intrinsic<Intrinsic::experimental_widenable_condition>())) { |
755 | 78 | // Pick any, we don't care which |
756 | 78 | WideableCond = Condition; |
757 | 78 | continue; |
758 | 78 | } |
759 | 243 | |
760 | 243 | if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) { |
761 | 229 | if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, |
762 | 165 | Guard)) { |
763 | 165 | Checks.push_back(NewRangeCheck.getValue()); |
764 | 165 | NumWidened++; |
765 | 165 | continue; |
766 | 165 | } |
767 | 78 | } |
768 | 78 | |
769 | 78 | // Save the condition as is if we can't widen it |
770 | 78 | Checks.push_back(Condition); |
771 | 826 | } while (!Worklist.empty()); |
772 | 204 | // At the moment, our matching logic for wideable conditions implicitly |
773 | 204 | // assumes we preserve the form: (br (and Cond, WC())). FIXME |
774 | 204 | // Note that if there were multiple calls to wideable condition in the |
775 | 204 | // traversal, we only need to keep one, and which one is arbitrary. |
776 | 204 | if (WideableCond) |
777 | 78 | Checks.push_back(WideableCond); |
778 | 204 | return NumWidened; |
779 | 204 | } |
780 | | |
781 | | bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard, |
782 | 126 | SCEVExpander &Expander) { |
783 | 126 | LLVM_DEBUG(dbgs() << "Processing guard:\n"); |
784 | 126 | LLVM_DEBUG(Guard->dump()); |
785 | 126 | |
786 | 126 | TotalConsidered++; |
787 | 126 | SmallVector<Value *, 4> Checks; |
788 | 126 | unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander, |
789 | 126 | Guard); |
790 | 126 | if (NumWidened == 0) |
791 | 42 | return false; |
792 | 84 | |
793 | 84 | TotalWidened += NumWidened; |
794 | 84 | |
795 | 84 | // Emit the new guard condition |
796 | 84 | IRBuilder<> Builder(findInsertPt(Guard, Checks)); |
797 | 84 | Value *AllChecks = Builder.CreateAnd(Checks); |
798 | 84 | auto *OldCond = Guard->getOperand(0); |
799 | 84 | Guard->setOperand(0, AllChecks); |
800 | 84 | RecursivelyDeleteTriviallyDeadInstructions(OldCond); |
801 | 84 | |
802 | 84 | LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n"); |
803 | 84 | return true; |
804 | 84 | } |
805 | | |
806 | | bool LoopPredication::widenWidenableBranchGuardConditions( |
807 | 78 | BranchInst *BI, SCEVExpander &Expander) { |
808 | 78 | assert(isGuardAsWidenableBranch(BI) && "Must be!"); |
809 | 78 | LLVM_DEBUG(dbgs() << "Processing guard:\n"); |
810 | 78 | LLVM_DEBUG(BI->dump()); |
811 | 78 | |
812 | 78 | TotalConsidered++; |
813 | 78 | SmallVector<Value *, 4> Checks; |
814 | 78 | unsigned NumWidened = collectChecks(Checks, BI->getCondition(), |
815 | 78 | Expander, BI); |
816 | 78 | if (NumWidened == 0) |
817 | 15 | return false; |
818 | 63 | |
819 | 63 | TotalWidened += NumWidened; |
820 | 63 | |
821 | 63 | // Emit the new guard condition |
822 | 63 | IRBuilder<> Builder(findInsertPt(BI, Checks)); |
823 | 63 | Value *AllChecks = Builder.CreateAnd(Checks); |
824 | 63 | auto *OldCond = BI->getCondition(); |
825 | 63 | BI->setCondition(AllChecks); |
826 | 63 | assert(isGuardAsWidenableBranch(BI) && |
827 | 63 | "Stopped being a guard after transform?"); |
828 | 63 | RecursivelyDeleteTriviallyDeadInstructions(OldCond); |
829 | 63 | |
830 | 63 | LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n"); |
831 | 63 | return true; |
832 | 63 | } |
833 | | |
834 | 208 | Optional<LoopICmp> LoopPredication::parseLoopLatchICmp() { |
835 | 208 | using namespace PatternMatch; |
836 | 208 | |
837 | 208 | BasicBlock *LoopLatch = L->getLoopLatch(); |
838 | 208 | if (!LoopLatch) { |
839 | 0 | LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n"); |
840 | 0 | return None; |
841 | 0 | } |
842 | 208 | |
843 | 208 | auto *BI = dyn_cast<BranchInst>(LoopLatch->getTerminator()); |
844 | 208 | if (!BI || !BI->isConditional()) { |
845 | 2 | LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n"); |
846 | 2 | return None; |
847 | 2 | } |
848 | 206 | BasicBlock *TrueDest = BI->getSuccessor(0); |
849 | 206 | assert( |
850 | 206 | (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) && |
851 | 206 | "One of the latch's destinations must be the header"); |
852 | 206 | |
853 | 206 | auto *ICI = dyn_cast<ICmpInst>(BI->getCondition()); |
854 | 206 | if (!ICI) { |
855 | 0 | LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n"); |
856 | 0 | return None; |
857 | 0 | } |
858 | 206 | auto Result = parseLoopICmp(ICI); |
859 | 206 | if (!Result) { |
860 | 0 | LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n"); |
861 | 0 | return None; |
862 | 0 | } |
863 | 206 | |
864 | 206 | if (TrueDest != L->getHeader()) |
865 | 7 | Result->Pred = ICmpInst::getInversePredicate(Result->Pred); |
866 | 206 | |
867 | 206 | // Check affine first, so if it's not we don't try to compute the step |
868 | 206 | // recurrence. |
869 | 206 | if (!Result->IV->isAffine()) { |
870 | 0 | LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n"); |
871 | 0 | return None; |
872 | 0 | } |
873 | 206 | |
874 | 206 | auto *Step = Result->IV->getStepRecurrence(*SE); |
875 | 206 | if (!isSupportedStep(Step)) { |
876 | 9 | LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n"); |
877 | 9 | return None; |
878 | 9 | } |
879 | 197 | |
880 | 197 | auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) { |
881 | 197 | if (Step->isOne()) { |
882 | 183 | return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT103 && |
883 | 183 | Pred != ICmpInst::ICMP_ULE35 && Pred != ICmpInst::ICMP_SLE30 ; |
884 | 183 | } else { |
885 | 14 | assert(Step->isAllOnesValue() && "Step should be -1!"); |
886 | 14 | return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT8 && |
887 | 14 | Pred != ICmpInst::ICMP_UGE6 && Pred != ICmpInst::ICMP_SGE2 ; |
888 | 14 | } |
889 | 197 | }; |
890 | 197 | |
891 | 197 | normalizePredicate(SE, L, *Result); |
892 | 197 | if (IsUnsupportedPredicate(Step, Result->Pred)) { |
893 | 10 | LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred |
894 | 10 | << ")!\n"); |
895 | 10 | return None; |
896 | 10 | } |
897 | 187 | |
898 | 187 | return Result; |
899 | 187 | } |
900 | | |
901 | | |
902 | 187 | bool LoopPredication::isLoopProfitableToPredicate() { |
903 | 187 | if (SkipProfitabilityChecks || !BPI) |
904 | 77 | return true; |
905 | 110 | |
906 | 110 | SmallVector<std::pair<BasicBlock *, BasicBlock *>, 8> ExitEdges; |
907 | 110 | L->getExitEdges(ExitEdges); |
908 | 110 | // If there is only one exiting edge in the loop, it is always profitable to |
909 | 110 | // predicate the loop. |
910 | 110 | if (ExitEdges.size() == 1) |
911 | 54 | return true; |
912 | 56 | |
913 | 56 | // Calculate the exiting probabilities of all exiting edges from the loop, |
914 | 56 | // starting with the LatchExitProbability. |
915 | 56 | // Heuristic for profitability: If any of the exiting blocks' probability of |
916 | 56 | // exiting the loop is larger than exiting through the latch block, it's not |
917 | 56 | // profitable to predicate the loop. |
918 | 56 | auto *LatchBlock = L->getLoopLatch(); |
919 | 56 | assert(LatchBlock && "Should have a single latch at this point!"); |
920 | 56 | auto *LatchTerm = LatchBlock->getTerminator(); |
921 | 56 | assert(LatchTerm->getNumSuccessors() == 2 && |
922 | 56 | "expected to be an exiting block with 2 succs!"); |
923 | 56 | unsigned LatchBrExitIdx = |
924 | 56 | LatchTerm->getSuccessor(0) == L->getHeader() ? 154 : 02 ; |
925 | 56 | BranchProbability LatchExitProbability = |
926 | 56 | BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx); |
927 | 56 | |
928 | 56 | // Protect against degenerate inputs provided by the user. Providing a value |
929 | 56 | // less than one, can invert the definition of profitable loop predication. |
930 | 56 | float ScaleFactor = LatchExitProbabilityScale; |
931 | 56 | if (ScaleFactor < 1) { |
932 | 0 | LLVM_DEBUG( |
933 | 0 | dbgs() |
934 | 0 | << "Ignored user setting for loop-predication-latch-probability-scale: " |
935 | 0 | << LatchExitProbabilityScale << "\n"); |
936 | 0 | LLVM_DEBUG(dbgs() << "The value is set to 1.0\n"); |
937 | 0 | ScaleFactor = 1.0; |
938 | 0 | } |
939 | 56 | const auto LatchProbabilityThreshold = |
940 | 56 | LatchExitProbability * ScaleFactor; |
941 | 56 | |
942 | 112 | for (const auto &ExitEdge : ExitEdges) { |
943 | 112 | BranchProbability ExitingBlockProbability = |
944 | 112 | BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second); |
945 | 112 | // Some exiting edge has higher probability than the latch exiting edge. |
946 | 112 | // No longer profitable to predicate. |
947 | 112 | if (ExitingBlockProbability > LatchProbabilityThreshold) |
948 | 4 | return false; |
949 | 112 | } |
950 | 56 | // Using BPI, we have concluded that the most probable way to exit from the |
951 | 56 | // loop is through the latch (or there's no profile information and all |
952 | 56 | // exits are equally likely). |
953 | 56 | return true52 ; |
954 | 56 | } |
955 | | |
956 | 208 | bool LoopPredication::runOnLoop(Loop *Loop) { |
957 | 208 | L = Loop; |
958 | 208 | |
959 | 208 | LLVM_DEBUG(dbgs() << "Analyzing "); |
960 | 208 | LLVM_DEBUG(L->dump()); |
961 | 208 | |
962 | 208 | Module *M = L->getHeader()->getModule(); |
963 | 208 | |
964 | 208 | // There is nothing to do if the module doesn't use guards |
965 | 208 | auto *GuardDecl = |
966 | 208 | M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard)); |
967 | 208 | bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty(); |
968 | 208 | auto *WCDecl = M->getFunction( |
969 | 208 | Intrinsic::getName(Intrinsic::experimental_widenable_condition)); |
970 | 208 | bool HasWidenableConditions = |
971 | 208 | PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty()81 ; |
972 | 208 | if (!HasIntrinsicGuards && !HasWidenableConditions81 ) |
973 | 0 | return false; |
974 | 208 | |
975 | 208 | DL = &M->getDataLayout(); |
976 | 208 | |
977 | 208 | Preheader = L->getLoopPreheader(); |
978 | 208 | if (!Preheader) |
979 | 0 | return false; |
980 | 208 | |
981 | 208 | auto LatchCheckOpt = parseLoopLatchICmp(); |
982 | 208 | if (!LatchCheckOpt) |
983 | 21 | return false; |
984 | 187 | LatchCheck = *LatchCheckOpt; |
985 | 187 | |
986 | 187 | LLVM_DEBUG(dbgs() << "Latch check:\n"); |
987 | 187 | LLVM_DEBUG(LatchCheck.dump()); |
988 | 187 | |
989 | 187 | if (!isLoopProfitableToPredicate()) { |
990 | 4 | LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n"); |
991 | 4 | return false; |
992 | 4 | } |
993 | 183 | // Collect all the guards into a vector and process later, so as not |
994 | 183 | // to invalidate the instruction iterator. |
995 | 183 | SmallVector<IntrinsicInst *, 4> Guards; |
996 | 183 | SmallVector<BranchInst *, 4> GuardsAsWidenableBranches; |
997 | 298 | for (const auto BB : L->blocks()) { |
998 | 298 | for (auto &I : *BB) |
999 | 2.70k | if (isGuard(&I)) |
1000 | 126 | Guards.push_back(cast<IntrinsicInst>(&I)); |
1001 | 298 | if (PredicateWidenableBranchGuards && |
1002 | 298 | isGuardAsWidenableBranch(BB->getTerminator())) |
1003 | 78 | GuardsAsWidenableBranches.push_back( |
1004 | 78 | cast<BranchInst>(BB->getTerminator())); |
1005 | 298 | } |
1006 | 183 | |
1007 | 183 | if (Guards.empty() && GuardsAsWidenableBranches.empty()75 ) |
1008 | 3 | return false; |
1009 | 180 | |
1010 | 180 | SCEVExpander Expander(*SE, *DL, "loop-predication"); |
1011 | 180 | |
1012 | 180 | bool Changed = false; |
1013 | 180 | for (auto *Guard : Guards) |
1014 | 126 | Changed |= widenGuardConditions(Guard, Expander); |
1015 | 180 | for (auto *Guard : GuardsAsWidenableBranches) |
1016 | 78 | Changed |= widenWidenableBranchGuardConditions(Guard, Expander); |
1017 | 180 | |
1018 | 180 | return Changed; |
1019 | 180 | } |