xref: /llvm-project/llvm/lib/Transforms/Scalar/LoopPredication.cpp (revision aa603c41caab63e246f4a4258c8b96e6ea06fdc9)
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/MemorySSA.h"
187 #include "llvm/Analysis/MemorySSAUpdater.h"
188 #include "llvm/Analysis/ScalarEvolution.h"
189 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
190 #include "llvm/IR/Function.h"
191 #include "llvm/IR/IntrinsicInst.h"
192 #include "llvm/IR/Module.h"
193 #include "llvm/IR/PatternMatch.h"
194 #include "llvm/IR/ProfDataUtils.h"
195 #include "llvm/InitializePasses.h"
196 #include "llvm/Pass.h"
197 #include "llvm/Support/CommandLine.h"
198 #include "llvm/Support/Debug.h"
199 #include "llvm/Transforms/Scalar.h"
200 #include "llvm/Transforms/Utils/GuardUtils.h"
201 #include "llvm/Transforms/Utils/Local.h"
202 #include "llvm/Transforms/Utils/LoopUtils.h"
203 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
204 #include <optional>
205 
206 #define DEBUG_TYPE "loop-predication"
207 
208 STATISTIC(TotalConsidered, "Number of guards considered");
209 STATISTIC(TotalWidened, "Number of checks widened");
210 
211 using namespace llvm;
212 
213 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
214                                         cl::Hidden, cl::init(true));
215 
216 static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop",
217                                         cl::Hidden, cl::init(true));
218 
219 static cl::opt<bool>
220     SkipProfitabilityChecks("loop-predication-skip-profitability-checks",
221                             cl::Hidden, cl::init(false));
222 
223 // This is the scale factor for the latch probability. We use this during
224 // profitability analysis to find other exiting blocks that have a much higher
225 // probability of exiting the loop instead of loop exiting via latch.
226 // This value should be greater than 1 for a sane profitability check.
227 static cl::opt<float> LatchExitProbabilityScale(
228     "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0),
229     cl::desc("scale factor for the latch probability. Value should be greater "
230              "than 1. Lower values are ignored"));
231 
232 static cl::opt<bool> PredicateWidenableBranchGuards(
233     "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden,
234     cl::desc("Whether or not we should predicate guards "
235              "expressed as widenable branches to deoptimize blocks"),
236     cl::init(true));
237 
238 static cl::opt<bool> InsertAssumesOfPredicatedGuardsConditions(
239     "loop-predication-insert-assumes-of-predicated-guards-conditions",
240     cl::Hidden,
241     cl::desc("Whether or not we should insert assumes of conditions of "
242              "predicated guards"),
243     cl::init(true));
244 
245 namespace {
246 /// Represents an induction variable check:
247 ///   icmp Pred, <induction variable>, <loop invariant limit>
248 struct LoopICmp {
249   ICmpInst::Predicate Pred;
250   const SCEVAddRecExpr *IV;
251   const SCEV *Limit;
252   LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
253            const SCEV *Limit)
254     : Pred(Pred), IV(IV), Limit(Limit) {}
255   LoopICmp() = default;
256   void dump() {
257     dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
258            << ", Limit = " << *Limit << "\n";
259   }
260 };
261 
262 class LoopPredication {
263   AliasAnalysis *AA;
264   DominatorTree *DT;
265   ScalarEvolution *SE;
266   LoopInfo *LI;
267   MemorySSAUpdater *MSSAU;
268 
269   Loop *L;
270   const DataLayout *DL;
271   BasicBlock *Preheader;
272   LoopICmp LatchCheck;
273 
274   bool isSupportedStep(const SCEV* Step);
275   std::optional<LoopICmp> parseLoopICmp(ICmpInst *ICI);
276   std::optional<LoopICmp> parseLoopLatchICmp();
277 
278   /// Return an insertion point suitable for inserting a safe to speculate
279   /// instruction whose only user will be 'User' which has operands 'Ops'.  A
280   /// trivial result would be the at the User itself, but we try to return a
281   /// loop invariant location if possible.
282   Instruction *findInsertPt(Instruction *User, ArrayRef<Value*> Ops);
283   /// Same as above, *except* that this uses the SCEV definition of invariant
284   /// which is that an expression *can be made* invariant via SCEVExpander.
285   /// Thus, this version is only suitable for finding an insert point to be be
286   /// passed to SCEVExpander!
287   Instruction *findInsertPt(const SCEVExpander &Expander, Instruction *User,
288                             ArrayRef<const SCEV *> Ops);
289 
290   /// Return true if the value is known to produce a single fixed value across
291   /// all iterations on which it executes.  Note that this does not imply
292   /// speculation safety.  That must be established separately.
293   bool isLoopInvariantValue(const SCEV* S);
294 
295   Value *expandCheck(SCEVExpander &Expander, Instruction *Guard,
296                      ICmpInst::Predicate Pred, const SCEV *LHS,
297                      const SCEV *RHS);
298 
299   std::optional<Value *> widenICmpRangeCheck(ICmpInst *ICI,
300                                              SCEVExpander &Expander,
301                                              Instruction *Guard);
302   std::optional<Value *>
303   widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
304                                       SCEVExpander &Expander,
305                                       Instruction *Guard);
306   std::optional<Value *>
307   widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
308                                       SCEVExpander &Expander,
309                                       Instruction *Guard);
310   unsigned widenChecks(SmallVectorImpl<Value *> &Checks, SCEVExpander &Expander,
311                        Instruction *Guard);
312   bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
313   bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander);
314   // If the loop always exits through another block in the loop, we should not
315   // predicate based on the latch check. For example, the latch check can be a
316   // very coarse grained check and there can be more fine grained exit checks
317   // within the loop.
318   bool isLoopProfitableToPredicate();
319 
320   bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter);
321 
322 public:
323   LoopPredication(AliasAnalysis *AA, DominatorTree *DT, ScalarEvolution *SE,
324                   LoopInfo *LI, MemorySSAUpdater *MSSAU)
325       : AA(AA), DT(DT), SE(SE), LI(LI), MSSAU(MSSAU){};
326   bool runOnLoop(Loop *L);
327 };
328 
329 class LoopPredicationLegacyPass : public LoopPass {
330 public:
331   static char ID;
332   LoopPredicationLegacyPass() : LoopPass(ID) {
333     initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry());
334   }
335 
336   void getAnalysisUsage(AnalysisUsage &AU) const override {
337     AU.addRequired<BranchProbabilityInfoWrapperPass>();
338     getLoopAnalysisUsage(AU);
339     AU.addPreserved<MemorySSAWrapperPass>();
340   }
341 
342   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
343     if (skipLoop(L))
344       return false;
345     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
346     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
347     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
348     auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
349     std::unique_ptr<MemorySSAUpdater> MSSAU;
350     if (MSSAWP)
351       MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
352     auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
353     LoopPredication LP(AA, DT, SE, LI, MSSAU ? MSSAU.get() : nullptr);
354     return LP.runOnLoop(L);
355   }
356 };
357 
358 char LoopPredicationLegacyPass::ID = 0;
359 } // end namespace
360 
361 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
362                       "Loop predication", false, false)
363 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
364 INITIALIZE_PASS_DEPENDENCY(LoopPass)
365 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
366                     "Loop predication", false, false)
367 
368 Pass *llvm::createLoopPredicationPass() {
369   return new LoopPredicationLegacyPass();
370 }
371 
372 PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM,
373                                            LoopStandardAnalysisResults &AR,
374                                            LPMUpdater &U) {
375   std::unique_ptr<MemorySSAUpdater> MSSAU;
376   if (AR.MSSA)
377     MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA);
378   LoopPredication LP(&AR.AA, &AR.DT, &AR.SE, &AR.LI,
379                      MSSAU ? MSSAU.get() : nullptr);
380   if (!LP.runOnLoop(&L))
381     return PreservedAnalyses::all();
382 
383   auto PA = getLoopPassPreservedAnalyses();
384   if (AR.MSSA)
385     PA.preserve<MemorySSAAnalysis>();
386   return PA;
387 }
388 
389 std::optional<LoopICmp> LoopPredication::parseLoopICmp(ICmpInst *ICI) {
390   auto Pred = ICI->getPredicate();
391   auto *LHS = ICI->getOperand(0);
392   auto *RHS = ICI->getOperand(1);
393 
394   const SCEV *LHSS = SE->getSCEV(LHS);
395   if (isa<SCEVCouldNotCompute>(LHSS))
396     return std::nullopt;
397   const SCEV *RHSS = SE->getSCEV(RHS);
398   if (isa<SCEVCouldNotCompute>(RHSS))
399     return std::nullopt;
400 
401   // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
402   if (SE->isLoopInvariant(LHSS, L)) {
403     std::swap(LHS, RHS);
404     std::swap(LHSS, RHSS);
405     Pred = ICmpInst::getSwappedPredicate(Pred);
406   }
407 
408   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
409   if (!AR || AR->getLoop() != L)
410     return std::nullopt;
411 
412   return LoopICmp(Pred, AR, RHSS);
413 }
414 
415 Value *LoopPredication::expandCheck(SCEVExpander &Expander,
416                                     Instruction *Guard,
417                                     ICmpInst::Predicate Pred, const SCEV *LHS,
418                                     const SCEV *RHS) {
419   Type *Ty = LHS->getType();
420   assert(Ty == RHS->getType() && "expandCheck operands have different types?");
421 
422   if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) {
423     IRBuilder<> Builder(Guard);
424     if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
425       return Builder.getTrue();
426     if (SE->isLoopEntryGuardedByCond(L, ICmpInst::getInversePredicate(Pred),
427                                      LHS, RHS))
428       return Builder.getFalse();
429   }
430 
431   Value *LHSV =
432       Expander.expandCodeFor(LHS, Ty, findInsertPt(Expander, Guard, {LHS}));
433   Value *RHSV =
434       Expander.expandCodeFor(RHS, Ty, findInsertPt(Expander, Guard, {RHS}));
435   IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV}));
436   return Builder.CreateICmp(Pred, LHSV, RHSV);
437 }
438 
439 // Returns true if its safe to truncate the IV to RangeCheckType.
440 // When the IV type is wider than the range operand type, we can still do loop
441 // predication, by generating SCEVs for the range and latch that are of the
442 // same type. We achieve this by generating a SCEV truncate expression for the
443 // latch IV. This is done iff truncation of the IV is a safe operation,
444 // without loss of information.
445 // Another way to achieve this is by generating a wider type SCEV for the
446 // range check operand, however, this needs a more involved check that
447 // operands do not overflow. This can lead to loss of information when the
448 // range operand is of the form: add i32 %offset, %iv. We need to prove that
449 // sext(x + y) is same as sext(x) + sext(y).
450 // This function returns true if we can safely represent the IV type in
451 // the RangeCheckType without loss of information.
452 static bool isSafeToTruncateWideIVType(const DataLayout &DL,
453                                        ScalarEvolution &SE,
454                                        const LoopICmp LatchCheck,
455                                        Type *RangeCheckType) {
456   if (!EnableIVTruncation)
457     return false;
458   assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()).getFixedValue() >
459              DL.getTypeSizeInBits(RangeCheckType).getFixedValue() &&
460          "Expected latch check IV type to be larger than range check operand "
461          "type!");
462   // The start and end values of the IV should be known. This is to guarantee
463   // that truncating the wide type will not lose information.
464   auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
465   auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
466   if (!Limit || !Start)
467     return false;
468   // This check makes sure that the IV does not change sign during loop
469   // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
470   // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
471   // IV wraps around, and the truncation of the IV would lose the range of
472   // iterations between 2^32 and 2^64.
473   if (!SE.getMonotonicPredicateType(LatchCheck.IV, LatchCheck.Pred))
474     return false;
475   // The active bits should be less than the bits in the RangeCheckType. This
476   // guarantees that truncating the latch check to RangeCheckType is a safe
477   // operation.
478   auto RangeCheckTypeBitSize =
479       DL.getTypeSizeInBits(RangeCheckType).getFixedValue();
480   return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
481          Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
482 }
483 
484 
485 // Return an LoopICmp describing a latch check equivlent to LatchCheck but with
486 // the requested type if safe to do so.  May involve the use of a new IV.
487 static std::optional<LoopICmp> generateLoopLatchCheck(const DataLayout &DL,
488                                                       ScalarEvolution &SE,
489                                                       const LoopICmp LatchCheck,
490                                                       Type *RangeCheckType) {
491 
492   auto *LatchType = LatchCheck.IV->getType();
493   if (RangeCheckType == LatchType)
494     return LatchCheck;
495   // For now, bail out if latch type is narrower than range type.
496   if (DL.getTypeSizeInBits(LatchType).getFixedValue() <
497       DL.getTypeSizeInBits(RangeCheckType).getFixedValue())
498     return std::nullopt;
499   if (!isSafeToTruncateWideIVType(DL, SE, LatchCheck, RangeCheckType))
500     return std::nullopt;
501   // We can now safely identify the truncated version of the IV and limit for
502   // RangeCheckType.
503   LoopICmp NewLatchCheck;
504   NewLatchCheck.Pred = LatchCheck.Pred;
505   NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
506       SE.getTruncateExpr(LatchCheck.IV, RangeCheckType));
507   if (!NewLatchCheck.IV)
508     return std::nullopt;
509   NewLatchCheck.Limit = SE.getTruncateExpr(LatchCheck.Limit, RangeCheckType);
510   LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType
511                     << "can be represented as range check type:"
512                     << *RangeCheckType << "\n");
513   LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
514   LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
515   return NewLatchCheck;
516 }
517 
518 bool LoopPredication::isSupportedStep(const SCEV* Step) {
519   return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop);
520 }
521 
522 Instruction *LoopPredication::findInsertPt(Instruction *Use,
523                                            ArrayRef<Value*> Ops) {
524   for (Value *Op : Ops)
525     if (!L->isLoopInvariant(Op))
526       return Use;
527   return Preheader->getTerminator();
528 }
529 
530 Instruction *LoopPredication::findInsertPt(const SCEVExpander &Expander,
531                                            Instruction *Use,
532                                            ArrayRef<const SCEV *> Ops) {
533   // Subtlety: SCEV considers things to be invariant if the value produced is
534   // the same across iterations.  This is not the same as being able to
535   // evaluate outside the loop, which is what we actually need here.
536   for (const SCEV *Op : Ops)
537     if (!SE->isLoopInvariant(Op, L) ||
538         !Expander.isSafeToExpandAt(Op, Preheader->getTerminator()))
539       return Use;
540   return Preheader->getTerminator();
541 }
542 
543 bool LoopPredication::isLoopInvariantValue(const SCEV* S) {
544   // Handling expressions which produce invariant results, but *haven't* yet
545   // been removed from the loop serves two important purposes.
546   // 1) Most importantly, it resolves a pass ordering cycle which would
547   // otherwise need us to iteration licm, loop-predication, and either
548   // loop-unswitch or loop-peeling to make progress on examples with lots of
549   // predicable range checks in a row.  (Since, in the general case,  we can't
550   // hoist the length checks until the dominating checks have been discharged
551   // as we can't prove doing so is safe.)
552   // 2) As a nice side effect, this exposes the value of peeling or unswitching
553   // much more obviously in the IR.  Otherwise, the cost modeling for other
554   // transforms would end up needing to duplicate all of this logic to model a
555   // check which becomes predictable based on a modeled peel or unswitch.
556   //
557   // The cost of doing so in the worst case is an extra fill from the stack  in
558   // the loop to materialize the loop invariant test value instead of checking
559   // against the original IV which is presumable in a register inside the loop.
560   // Such cases are presumably rare, and hint at missing oppurtunities for
561   // other passes.
562 
563   if (SE->isLoopInvariant(S, L))
564     // Note: This the SCEV variant, so the original Value* may be within the
565     // loop even though SCEV has proven it is loop invariant.
566     return true;
567 
568   // Handle a particular important case which SCEV doesn't yet know about which
569   // shows up in range checks on arrays with immutable lengths.
570   // TODO: This should be sunk inside SCEV.
571   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
572     if (const auto *LI = dyn_cast<LoadInst>(U->getValue()))
573       if (LI->isUnordered() && L->hasLoopInvariantOperands(LI))
574         if (!isModSet(AA->getModRefInfoMask(LI->getOperand(0))) ||
575             LI->hasMetadata(LLVMContext::MD_invariant_load))
576           return true;
577   return false;
578 }
579 
580 std::optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
581     LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander,
582     Instruction *Guard) {
583   auto *Ty = RangeCheck.IV->getType();
584   // Generate the widened condition for the forward loop:
585   //   guardStart u< guardLimit &&
586   //   latchLimit <pred> guardLimit - 1 - guardStart + latchStart
587   // where <pred> depends on the latch condition predicate. See the file
588   // header comment for the reasoning.
589   // guardLimit - guardStart + latchStart - 1
590   const SCEV *GuardStart = RangeCheck.IV->getStart();
591   const SCEV *GuardLimit = RangeCheck.Limit;
592   const SCEV *LatchStart = LatchCheck.IV->getStart();
593   const SCEV *LatchLimit = LatchCheck.Limit;
594   // Subtlety: We need all the values to be *invariant* across all iterations,
595   // but we only need to check expansion safety for those which *aren't*
596   // already guaranteed to dominate the guard.
597   if (!isLoopInvariantValue(GuardStart) ||
598       !isLoopInvariantValue(GuardLimit) ||
599       !isLoopInvariantValue(LatchStart) ||
600       !isLoopInvariantValue(LatchLimit)) {
601     LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
602     return std::nullopt;
603   }
604   if (!Expander.isSafeToExpandAt(LatchStart, Guard) ||
605       !Expander.isSafeToExpandAt(LatchLimit, Guard)) {
606     LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
607     return std::nullopt;
608   }
609 
610   // guardLimit - guardStart + latchStart - 1
611   const SCEV *RHS =
612       SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
613                      SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
614   auto LimitCheckPred =
615       ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred);
616 
617   LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
618   LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n");
619   LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
620 
621   auto *LimitCheck =
622       expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS);
623   auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred,
624                                           GuardStart, GuardLimit);
625   IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
626   return Builder.CreateFreeze(
627       Builder.CreateAnd(FirstIterationCheck, LimitCheck));
628 }
629 
630 std::optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
631     LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander,
632     Instruction *Guard) {
633   auto *Ty = RangeCheck.IV->getType();
634   const SCEV *GuardStart = RangeCheck.IV->getStart();
635   const SCEV *GuardLimit = RangeCheck.Limit;
636   const SCEV *LatchStart = LatchCheck.IV->getStart();
637   const SCEV *LatchLimit = LatchCheck.Limit;
638   // Subtlety: We need all the values to be *invariant* across all iterations,
639   // but we only need to check expansion safety for those which *aren't*
640   // already guaranteed to dominate the guard.
641   if (!isLoopInvariantValue(GuardStart) ||
642       !isLoopInvariantValue(GuardLimit) ||
643       !isLoopInvariantValue(LatchStart) ||
644       !isLoopInvariantValue(LatchLimit)) {
645     LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
646     return std::nullopt;
647   }
648   if (!Expander.isSafeToExpandAt(LatchStart, Guard) ||
649       !Expander.isSafeToExpandAt(LatchLimit, Guard)) {
650     LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
651     return std::nullopt;
652   }
653   // The decrement of the latch check IV should be the same as the
654   // rangeCheckIV.
655   auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
656   if (RangeCheck.IV != PostDecLatchCheckIV) {
657     LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
658                       << *PostDecLatchCheckIV
659                       << "  and RangeCheckIV: " << *RangeCheck.IV << "\n");
660     return std::nullopt;
661   }
662 
663   // Generate the widened condition for CountDownLoop:
664   // guardStart u< guardLimit &&
665   // latchLimit <pred> 1.
666   // See the header comment for reasoning of the checks.
667   auto LimitCheckPred =
668       ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred);
669   auto *FirstIterationCheck = expandCheck(Expander, Guard,
670                                           ICmpInst::ICMP_ULT,
671                                           GuardStart, GuardLimit);
672   auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,
673                                  SE->getOne(Ty));
674   IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
675   return Builder.CreateFreeze(
676       Builder.CreateAnd(FirstIterationCheck, LimitCheck));
677 }
678 
679 static void normalizePredicate(ScalarEvolution *SE, Loop *L,
680                                LoopICmp& RC) {
681   // LFTR canonicalizes checks to the ICMP_NE/EQ form; normalize back to the
682   // ULT/UGE form for ease of handling by our caller.
683   if (ICmpInst::isEquality(RC.Pred) &&
684       RC.IV->getStepRecurrence(*SE)->isOne() &&
685       SE->isKnownPredicate(ICmpInst::ICMP_ULE, RC.IV->getStart(), RC.Limit))
686     RC.Pred = RC.Pred == ICmpInst::ICMP_NE ?
687       ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE;
688 }
689 
690 /// If ICI can be widened to a loop invariant condition emits the loop
691 /// invariant condition in the loop preheader and return it, otherwise
692 /// returns std::nullopt.
693 std::optional<Value *>
694 LoopPredication::widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
695                                      Instruction *Guard) {
696   LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
697   LLVM_DEBUG(ICI->dump());
698 
699   // parseLoopStructure guarantees that the latch condition is:
700   //   ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
701   // We are looking for the range checks of the form:
702   //   i u< guardLimit
703   auto RangeCheck = parseLoopICmp(ICI);
704   if (!RangeCheck) {
705     LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
706     return std::nullopt;
707   }
708   LLVM_DEBUG(dbgs() << "Guard check:\n");
709   LLVM_DEBUG(RangeCheck->dump());
710   if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
711     LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
712                       << RangeCheck->Pred << ")!\n");
713     return std::nullopt;
714   }
715   auto *RangeCheckIV = RangeCheck->IV;
716   if (!RangeCheckIV->isAffine()) {
717     LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
718     return std::nullopt;
719   }
720   auto *Step = RangeCheckIV->getStepRecurrence(*SE);
721   // We cannot just compare with latch IV step because the latch and range IVs
722   // may have different types.
723   if (!isSupportedStep(Step)) {
724     LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
725     return std::nullopt;
726   }
727   auto *Ty = RangeCheckIV->getType();
728   auto CurrLatchCheckOpt = generateLoopLatchCheck(*DL, *SE, LatchCheck, Ty);
729   if (!CurrLatchCheckOpt) {
730     LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
731                          "corresponding to range type: "
732                       << *Ty << "\n");
733     return std::nullopt;
734   }
735 
736   LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
737   // At this point, the range and latch step should have the same type, but need
738   // not have the same value (we support both 1 and -1 steps).
739   assert(Step->getType() ==
740              CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
741          "Range and latch steps should be of same type!");
742   if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
743     LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
744     return std::nullopt;
745   }
746 
747   if (Step->isOne())
748     return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
749                                                Expander, Guard);
750   else {
751     assert(Step->isAllOnesValue() && "Step should be -1!");
752     return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
753                                                Expander, Guard);
754   }
755 }
756 
757 unsigned LoopPredication::widenChecks(SmallVectorImpl<Value *> &Checks,
758                                       SCEVExpander &Expander,
759                                       Instruction *Guard) {
760   unsigned NumWidened = 0;
761   for (auto &Check : Checks)
762     if (ICmpInst *ICI = dyn_cast<ICmpInst>(Check))
763       if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Guard)) {
764         NumWidened++;
765         Check = *NewRangeCheck;
766       }
767   return NumWidened;
768 }
769 
770 static SmallVector<Value *> extractChecksFromGuard(Instruction *Guard) {
771   LLVM_DEBUG(dbgs() << "Processing guard:\n");
772   LLVM_DEBUG(Guard->dump());
773 
774   SmallVector<Value *, 4> Checks;
775   parseWidenableGuard(Guard, Checks);
776   LLVM_DEBUG(dbgs() << "Found checks:\n");
777   std::for_each(Checks.begin(), Checks.end(), [](const Value *Check) {
778     LLVM_DEBUG(dbgs() << *Check << "\n");
779   });
780   return Checks;
781 }
782 
783 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
784                                            SCEVExpander &Expander) {
785   TotalConsidered++;
786   auto Checks = extractChecksFromGuard(Guard);
787   unsigned NumWidened = widenChecks(Checks, Expander, Guard);
788   if (NumWidened == 0)
789     return false;
790 
791   TotalWidened += NumWidened;
792 
793   // Emit the new guard condition
794   IRBuilder<> Builder(findInsertPt(Guard, Checks));
795   Value *AllChecks = Builder.CreateAnd(Checks);
796   auto *OldCond = Guard->getOperand(0);
797   Guard->setOperand(0, AllChecks);
798   if (InsertAssumesOfPredicatedGuardsConditions) {
799     Builder.SetInsertPoint(&*++BasicBlock::iterator(Guard));
800     Builder.CreateAssumption(OldCond);
801   }
802   RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU);
803 
804   LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
805   return true;
806 }
807 
808 bool LoopPredication::widenWidenableBranchGuardConditions(
809     BranchInst *BI, SCEVExpander &Expander) {
810   assert(isGuardAsWidenableBranch(BI) && "Must be!");
811 
812   Value *Cond, *WC;
813   BasicBlock *IfTrueBB, *IfFalseBB;
814   bool Parsed = parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB);
815   assert(Parsed && "Must be able to parse widenable branch");
816   (void)Parsed;
817 
818   TotalConsidered++;
819   auto Checks = extractChecksFromGuard(BI);
820   // At the moment, our matching logic for wideable conditions implicitly
821   // assumes we preserve the form: (br (and Cond, WC())).  FIXME
822   Checks.push_back(WC);
823   unsigned NumWidened = widenChecks(Checks, Expander, BI);
824   if (NumWidened == 0)
825     return false;
826 
827   TotalWidened += NumWidened;
828 
829   // Emit the new guard condition
830   IRBuilder<> Builder(findInsertPt(BI, Checks));
831   Value *AllChecks = Builder.CreateAnd(Checks);
832   auto *OldCond = BI->getCondition();
833   BI->setCondition(AllChecks);
834   if (InsertAssumesOfPredicatedGuardsConditions) {
835     Builder.SetInsertPoint(IfTrueBB, IfTrueBB->getFirstInsertionPt());
836     // If this block has other predecessors, we might not be able to use Cond.
837     // In this case, create a Phi where every other input is `true` and input
838     // from guard block is Cond.
839     Value *AssumeCond = Cond;
840     if (!IfTrueBB->getUniquePredecessor()) {
841       auto *GuardBB = BI->getParent();
842       auto *PN = Builder.CreatePHI(Cond->getType(), pred_size(IfTrueBB),
843                                    "assume.cond");
844       for (auto *Pred : predecessors(IfTrueBB))
845         PN->addIncoming(Pred == GuardBB ? Cond : Builder.getTrue(), Pred);
846       AssumeCond = PN;
847     }
848     Builder.CreateAssumption(AssumeCond);
849   }
850   RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU);
851   assert(isGuardAsWidenableBranch(BI) &&
852          "Stopped being a guard after transform?");
853 
854   LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
855   return true;
856 }
857 
858 std::optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
859   using namespace PatternMatch;
860 
861   BasicBlock *LoopLatch = L->getLoopLatch();
862   if (!LoopLatch) {
863     LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
864     return std::nullopt;
865   }
866 
867   auto *BI = dyn_cast<BranchInst>(LoopLatch->getTerminator());
868   if (!BI || !BI->isConditional()) {
869     LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
870     return std::nullopt;
871   }
872   BasicBlock *TrueDest = BI->getSuccessor(0);
873   assert(
874       (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) &&
875       "One of the latch's destinations must be the header");
876 
877   auto *ICI = dyn_cast<ICmpInst>(BI->getCondition());
878   if (!ICI) {
879     LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n");
880     return std::nullopt;
881   }
882   auto Result = parseLoopICmp(ICI);
883   if (!Result) {
884     LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
885     return std::nullopt;
886   }
887 
888   if (TrueDest != L->getHeader())
889     Result->Pred = ICmpInst::getInversePredicate(Result->Pred);
890 
891   // Check affine first, so if it's not we don't try to compute the step
892   // recurrence.
893   if (!Result->IV->isAffine()) {
894     LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
895     return std::nullopt;
896   }
897 
898   auto *Step = Result->IV->getStepRecurrence(*SE);
899   if (!isSupportedStep(Step)) {
900     LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
901     return std::nullopt;
902   }
903 
904   auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
905     if (Step->isOne()) {
906       return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
907              Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
908     } else {
909       assert(Step->isAllOnesValue() && "Step should be -1!");
910       return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
911              Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
912     }
913   };
914 
915   normalizePredicate(SE, L, *Result);
916   if (IsUnsupportedPredicate(Step, Result->Pred)) {
917     LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
918                       << ")!\n");
919     return std::nullopt;
920   }
921 
922   return Result;
923 }
924 
925 bool LoopPredication::isLoopProfitableToPredicate() {
926   if (SkipProfitabilityChecks)
927     return true;
928 
929   SmallVector<std::pair<BasicBlock *, BasicBlock *>, 8> ExitEdges;
930   L->getExitEdges(ExitEdges);
931   // If there is only one exiting edge in the loop, it is always profitable to
932   // predicate the loop.
933   if (ExitEdges.size() == 1)
934     return true;
935 
936   // Calculate the exiting probabilities of all exiting edges from the loop,
937   // starting with the LatchExitProbability.
938   // Heuristic for profitability: If any of the exiting blocks' probability of
939   // exiting the loop is larger than exiting through the latch block, it's not
940   // profitable to predicate the loop.
941   auto *LatchBlock = L->getLoopLatch();
942   assert(LatchBlock && "Should have a single latch at this point!");
943   auto *LatchTerm = LatchBlock->getTerminator();
944   assert(LatchTerm->getNumSuccessors() == 2 &&
945          "expected to be an exiting block with 2 succs!");
946   unsigned LatchBrExitIdx =
947       LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;
948   // We compute branch probabilities without BPI. We do not rely on BPI since
949   // Loop predication is usually run in an LPM and BPI is only preserved
950   // lossily within loop pass managers, while BPI has an inherent notion of
951   // being complete for an entire function.
952 
953   // If the latch exits into a deoptimize or an unreachable block, do not
954   // predicate on that latch check.
955   auto *LatchExitBlock = LatchTerm->getSuccessor(LatchBrExitIdx);
956   if (isa<UnreachableInst>(LatchTerm) ||
957       LatchExitBlock->getTerminatingDeoptimizeCall())
958     return false;
959 
960   // Latch terminator has no valid profile data, so nothing to check
961   // profitability on.
962   if (!hasValidBranchWeightMD(*LatchTerm))
963     return true;
964 
965   auto ComputeBranchProbability =
966       [&](const BasicBlock *ExitingBlock,
967           const BasicBlock *ExitBlock) -> BranchProbability {
968     auto *Term = ExitingBlock->getTerminator();
969     unsigned NumSucc = Term->getNumSuccessors();
970     if (MDNode *ProfileData = getValidBranchWeightMDNode(*Term)) {
971       SmallVector<uint32_t> Weights;
972       extractBranchWeights(ProfileData, Weights);
973       uint64_t Numerator = 0, Denominator = 0;
974       for (auto [i, Weight] : llvm::enumerate(Weights)) {
975         if (Term->getSuccessor(i) == ExitBlock)
976           Numerator += Weight;
977         Denominator += Weight;
978       }
979       return BranchProbability::getBranchProbability(Numerator, Denominator);
980     } else {
981       assert(LatchBlock != ExitingBlock &&
982              "Latch term should always have profile data!");
983       // No profile data, so we choose the weight as 1/num_of_succ(Src)
984       return BranchProbability::getBranchProbability(1, NumSucc);
985     }
986   };
987 
988   BranchProbability LatchExitProbability =
989       ComputeBranchProbability(LatchBlock, LatchExitBlock);
990 
991   // Protect against degenerate inputs provided by the user. Providing a value
992   // less than one, can invert the definition of profitable loop predication.
993   float ScaleFactor = LatchExitProbabilityScale;
994   if (ScaleFactor < 1) {
995     LLVM_DEBUG(
996         dbgs()
997         << "Ignored user setting for loop-predication-latch-probability-scale: "
998         << LatchExitProbabilityScale << "\n");
999     LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
1000     ScaleFactor = 1.0;
1001   }
1002   const auto LatchProbabilityThreshold = LatchExitProbability * ScaleFactor;
1003 
1004   for (const auto &ExitEdge : ExitEdges) {
1005     BranchProbability ExitingBlockProbability =
1006         ComputeBranchProbability(ExitEdge.first, ExitEdge.second);
1007     // Some exiting edge has higher probability than the latch exiting edge.
1008     // No longer profitable to predicate.
1009     if (ExitingBlockProbability > LatchProbabilityThreshold)
1010       return false;
1011   }
1012 
1013   // We have concluded that the most probable way to exit from the
1014   // loop is through the latch (or there's no profile information and all
1015   // exits are equally likely).
1016   return true;
1017 }
1018 
1019 /// If we can (cheaply) find a widenable branch which controls entry into the
1020 /// loop, return it.
1021 static BranchInst *FindWidenableTerminatorAboveLoop(Loop *L, LoopInfo &LI) {
1022   // Walk back through any unconditional executed blocks and see if we can find
1023   // a widenable condition which seems to control execution of this loop.  Note
1024   // that we predict that maythrow calls are likely untaken and thus that it's
1025   // profitable to widen a branch before a maythrow call with a condition
1026   // afterwards even though that may cause the slow path to run in a case where
1027   // it wouldn't have otherwise.
1028   BasicBlock *BB = L->getLoopPreheader();
1029   if (!BB)
1030     return nullptr;
1031   do {
1032     if (BasicBlock *Pred = BB->getSinglePredecessor())
1033       if (BB == Pred->getSingleSuccessor()) {
1034         BB = Pred;
1035         continue;
1036       }
1037     break;
1038   } while (true);
1039 
1040   if (BasicBlock *Pred = BB->getSinglePredecessor()) {
1041     auto *Term = Pred->getTerminator();
1042 
1043     Value *Cond, *WC;
1044     BasicBlock *IfTrueBB, *IfFalseBB;
1045     if (parseWidenableBranch(Term, Cond, WC, IfTrueBB, IfFalseBB) &&
1046         IfTrueBB == BB)
1047       return cast<BranchInst>(Term);
1048   }
1049   return nullptr;
1050 }
1051 
1052 /// Return the minimum of all analyzeable exit counts.  This is an upper bound
1053 /// on the actual exit count.  If there are not at least two analyzeable exits,
1054 /// returns SCEVCouldNotCompute.
1055 static const SCEV *getMinAnalyzeableBackedgeTakenCount(ScalarEvolution &SE,
1056                                                        DominatorTree &DT,
1057                                                        Loop *L) {
1058   SmallVector<BasicBlock *, 16> ExitingBlocks;
1059   L->getExitingBlocks(ExitingBlocks);
1060 
1061   SmallVector<const SCEV *, 4> ExitCounts;
1062   for (BasicBlock *ExitingBB : ExitingBlocks) {
1063     const SCEV *ExitCount = SE.getExitCount(L, ExitingBB);
1064     if (isa<SCEVCouldNotCompute>(ExitCount))
1065       continue;
1066     assert(DT.dominates(ExitingBB, L->getLoopLatch()) &&
1067            "We should only have known counts for exiting blocks that "
1068            "dominate latch!");
1069     ExitCounts.push_back(ExitCount);
1070   }
1071   if (ExitCounts.size() < 2)
1072     return SE.getCouldNotCompute();
1073   return SE.getUMinFromMismatchedTypes(ExitCounts);
1074 }
1075 
1076 /// This implements an analogous, but entirely distinct transform from the main
1077 /// loop predication transform.  This one is phrased in terms of using a
1078 /// widenable branch *outside* the loop to allow us to simplify loop exits in a
1079 /// following loop.  This is close in spirit to the IndVarSimplify transform
1080 /// of the same name, but is materially different widening loosens legality
1081 /// sharply.
1082 bool LoopPredication::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) {
1083   // The transformation performed here aims to widen a widenable condition
1084   // above the loop such that all analyzeable exit leading to deopt are dead.
1085   // It assumes that the latch is the dominant exit for profitability and that
1086   // exits branching to deoptimizing blocks are rarely taken. It relies on the
1087   // semantics of widenable expressions for legality. (i.e. being able to fall
1088   // down the widenable path spuriously allows us to ignore exit order,
1089   // unanalyzeable exits, side effects, exceptional exits, and other challenges
1090   // which restrict the applicability of the non-WC based version of this
1091   // transform in IndVarSimplify.)
1092   //
1093   // NOTE ON POISON/UNDEF - We're hoisting an expression above guards which may
1094   // imply flags on the expression being hoisted and inserting new uses (flags
1095   // are only correct for current uses).  The result is that we may be
1096   // inserting a branch on the value which can be either poison or undef.  In
1097   // this case, the branch can legally go either way; we just need to avoid
1098   // introducing UB.  This is achieved through the use of the freeze
1099   // instruction.
1100 
1101   SmallVector<BasicBlock *, 16> ExitingBlocks;
1102   L->getExitingBlocks(ExitingBlocks);
1103 
1104   if (ExitingBlocks.empty())
1105     return false; // Nothing to do.
1106 
1107   auto *Latch = L->getLoopLatch();
1108   if (!Latch)
1109     return false;
1110 
1111   auto *WidenableBR = FindWidenableTerminatorAboveLoop(L, *LI);
1112   if (!WidenableBR)
1113     return false;
1114 
1115   const SCEV *LatchEC = SE->getExitCount(L, Latch);
1116   if (isa<SCEVCouldNotCompute>(LatchEC))
1117     return false; // profitability - want hot exit in analyzeable set
1118 
1119   // At this point, we have found an analyzeable latch, and a widenable
1120   // condition above the loop.  If we have a widenable exit within the loop
1121   // (for which we can't compute exit counts), drop the ability to further
1122   // widen so that we gain ability to analyze it's exit count and perform this
1123   // transform.  TODO: It'd be nice to know for sure the exit became
1124   // analyzeable after dropping widenability.
1125   bool ChangedLoop = false;
1126 
1127   for (auto *ExitingBB : ExitingBlocks) {
1128     if (LI->getLoopFor(ExitingBB) != L)
1129       continue;
1130 
1131     auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1132     if (!BI)
1133       continue;
1134 
1135     Use *Cond, *WC;
1136     BasicBlock *IfTrueBB, *IfFalseBB;
1137     if (parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB) &&
1138         L->contains(IfTrueBB)) {
1139       WC->set(ConstantInt::getTrue(IfTrueBB->getContext()));
1140       ChangedLoop = true;
1141     }
1142   }
1143   if (ChangedLoop)
1144     SE->forgetLoop(L);
1145 
1146   // The insertion point for the widening should be at the widenably call, not
1147   // at the WidenableBR. If we do this at the widenableBR, we can incorrectly
1148   // change a loop-invariant condition to a loop-varying one.
1149   auto *IP = cast<Instruction>(WidenableBR->getCondition());
1150 
1151   // The use of umin(all analyzeable exits) instead of latch is subtle, but
1152   // important for profitability.  We may have a loop which hasn't been fully
1153   // canonicalized just yet.  If the exit we chose to widen is provably never
1154   // taken, we want the widened form to *also* be provably never taken.  We
1155   // can't guarantee this as a current unanalyzeable exit may later become
1156   // analyzeable, but we can at least avoid the obvious cases.
1157   const SCEV *MinEC = getMinAnalyzeableBackedgeTakenCount(*SE, *DT, L);
1158   if (isa<SCEVCouldNotCompute>(MinEC) || MinEC->getType()->isPointerTy() ||
1159       !SE->isLoopInvariant(MinEC, L) ||
1160       !Rewriter.isSafeToExpandAt(MinEC, IP))
1161     return ChangedLoop;
1162 
1163   Rewriter.setInsertPoint(IP);
1164   IRBuilder<> B(IP);
1165 
1166   bool InvalidateLoop = false;
1167   Value *MinECV = nullptr; // lazily generated if needed
1168   for (BasicBlock *ExitingBB : ExitingBlocks) {
1169     // If our exiting block exits multiple loops, we can only rewrite the
1170     // innermost one.  Otherwise, we're changing how many times the innermost
1171     // loop runs before it exits.
1172     if (LI->getLoopFor(ExitingBB) != L)
1173       continue;
1174 
1175     // Can't rewrite non-branch yet.
1176     auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1177     if (!BI)
1178       continue;
1179 
1180     // If already constant, nothing to do.
1181     if (isa<Constant>(BI->getCondition()))
1182       continue;
1183 
1184     const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1185     if (isa<SCEVCouldNotCompute>(ExitCount) ||
1186         ExitCount->getType()->isPointerTy() ||
1187         !Rewriter.isSafeToExpandAt(ExitCount, WidenableBR))
1188       continue;
1189 
1190     const bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
1191     BasicBlock *ExitBB = BI->getSuccessor(ExitIfTrue ? 0 : 1);
1192     if (!ExitBB->getPostdominatingDeoptimizeCall())
1193       continue;
1194 
1195     /// Here we can be fairly sure that executing this exit will most likely
1196     /// lead to executing llvm.experimental.deoptimize.
1197     /// This is a profitability heuristic, not a legality constraint.
1198 
1199     // If we found a widenable exit condition, do two things:
1200     // 1) fold the widened exit test into the widenable condition
1201     // 2) fold the branch to untaken - avoids infinite looping
1202 
1203     Value *ECV = Rewriter.expandCodeFor(ExitCount);
1204     if (!MinECV)
1205       MinECV = Rewriter.expandCodeFor(MinEC);
1206     Value *RHS = MinECV;
1207     if (ECV->getType() != RHS->getType()) {
1208       Type *WiderTy = SE->getWiderType(ECV->getType(), RHS->getType());
1209       ECV = B.CreateZExt(ECV, WiderTy);
1210       RHS = B.CreateZExt(RHS, WiderTy);
1211     }
1212     assert(!Latch || DT->dominates(ExitingBB, Latch));
1213     Value *NewCond = B.CreateICmp(ICmpInst::ICMP_UGT, ECV, RHS);
1214     // Freeze poison or undef to an arbitrary bit pattern to ensure we can
1215     // branch without introducing UB.  See NOTE ON POISON/UNDEF above for
1216     // context.
1217     NewCond = B.CreateFreeze(NewCond);
1218 
1219     widenWidenableBranch(WidenableBR, NewCond);
1220 
1221     Value *OldCond = BI->getCondition();
1222     BI->setCondition(ConstantInt::get(OldCond->getType(), !ExitIfTrue));
1223     InvalidateLoop = true;
1224   }
1225 
1226   if (InvalidateLoop)
1227     // We just mutated a bunch of loop exits changing there exit counts
1228     // widely.  We need to force recomputation of the exit counts given these
1229     // changes.  Note that all of the inserted exits are never taken, and
1230     // should be removed next time the CFG is modified.
1231     SE->forgetLoop(L);
1232 
1233   // Always return `true` since we have moved the WidenableBR's condition.
1234   return true;
1235 }
1236 
1237 bool LoopPredication::runOnLoop(Loop *Loop) {
1238   L = Loop;
1239 
1240   LLVM_DEBUG(dbgs() << "Analyzing ");
1241   LLVM_DEBUG(L->dump());
1242 
1243   Module *M = L->getHeader()->getModule();
1244 
1245   // There is nothing to do if the module doesn't use guards
1246   auto *GuardDecl =
1247       M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
1248   bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
1249   auto *WCDecl = M->getFunction(
1250       Intrinsic::getName(Intrinsic::experimental_widenable_condition));
1251   bool HasWidenableConditions =
1252       PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty();
1253   if (!HasIntrinsicGuards && !HasWidenableConditions)
1254     return false;
1255 
1256   DL = &M->getDataLayout();
1257 
1258   Preheader = L->getLoopPreheader();
1259   if (!Preheader)
1260     return false;
1261 
1262   auto LatchCheckOpt = parseLoopLatchICmp();
1263   if (!LatchCheckOpt)
1264     return false;
1265   LatchCheck = *LatchCheckOpt;
1266 
1267   LLVM_DEBUG(dbgs() << "Latch check:\n");
1268   LLVM_DEBUG(LatchCheck.dump());
1269 
1270   if (!isLoopProfitableToPredicate()) {
1271     LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
1272     return false;
1273   }
1274   // Collect all the guards into a vector and process later, so as not
1275   // to invalidate the instruction iterator.
1276   SmallVector<IntrinsicInst *, 4> Guards;
1277   SmallVector<BranchInst *, 4> GuardsAsWidenableBranches;
1278   for (const auto BB : L->blocks()) {
1279     for (auto &I : *BB)
1280       if (isGuard(&I))
1281         Guards.push_back(cast<IntrinsicInst>(&I));
1282     if (PredicateWidenableBranchGuards &&
1283         isGuardAsWidenableBranch(BB->getTerminator()))
1284       GuardsAsWidenableBranches.push_back(
1285           cast<BranchInst>(BB->getTerminator()));
1286   }
1287 
1288   SCEVExpander Expander(*SE, *DL, "loop-predication");
1289   bool Changed = false;
1290   for (auto *Guard : Guards)
1291     Changed |= widenGuardConditions(Guard, Expander);
1292   for (auto *Guard : GuardsAsWidenableBranches)
1293     Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1294   Changed |= predicateLoopExits(L, Expander);
1295 
1296   if (MSSAU && VerifyMemorySSA)
1297     MSSAU->getMemorySSA()->verifyMemorySSA();
1298   return Changed;
1299 }
1300