xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp (revision 5678d1d98a348f315453555377ccb28821a2ffcd)
1 //===- InductiveRangeCheckElimination.cpp - -------------------------------===//
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 InductiveRangeCheckElimination pass splits a loop's iteration space into
10 // three disjoint ranges.  It does that in a way such that the loop running in
11 // the middle loop provably does not need range checks. As an example, it will
12 // convert
13 //
14 //   len = < known positive >
15 //   for (i = 0; i < n; i++) {
16 //     if (0 <= i && i < len) {
17 //       do_something();
18 //     } else {
19 //       throw_out_of_bounds();
20 //     }
21 //   }
22 //
23 // to
24 //
25 //   len = < known positive >
26 //   limit = smin(n, len)
27 //   // no first segment
28 //   for (i = 0; i < limit; i++) {
29 //     if (0 <= i && i < len) { // this check is fully redundant
30 //       do_something();
31 //     } else {
32 //       throw_out_of_bounds();
33 //     }
34 //   }
35 //   for (i = limit; i < n; i++) {
36 //     if (0 <= i && i < len) {
37 //       do_something();
38 //     } else {
39 //       throw_out_of_bounds();
40 //     }
41 //   }
42 //
43 //===----------------------------------------------------------------------===//
44 
45 #include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
46 #include "llvm/ADT/APInt.h"
47 #include "llvm/ADT/ArrayRef.h"
48 #include "llvm/ADT/PriorityWorklist.h"
49 #include "llvm/ADT/SmallPtrSet.h"
50 #include "llvm/ADT/SmallVector.h"
51 #include "llvm/ADT/StringRef.h"
52 #include "llvm/ADT/Twine.h"
53 #include "llvm/Analysis/BlockFrequencyInfo.h"
54 #include "llvm/Analysis/BranchProbabilityInfo.h"
55 #include "llvm/Analysis/LoopAnalysisManager.h"
56 #include "llvm/Analysis/LoopInfo.h"
57 #include "llvm/Analysis/ScalarEvolution.h"
58 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
59 #include "llvm/IR/BasicBlock.h"
60 #include "llvm/IR/CFG.h"
61 #include "llvm/IR/Constants.h"
62 #include "llvm/IR/DerivedTypes.h"
63 #include "llvm/IR/Dominators.h"
64 #include "llvm/IR/Function.h"
65 #include "llvm/IR/IRBuilder.h"
66 #include "llvm/IR/InstrTypes.h"
67 #include "llvm/IR/Instructions.h"
68 #include "llvm/IR/Metadata.h"
69 #include "llvm/IR/Module.h"
70 #include "llvm/IR/PatternMatch.h"
71 #include "llvm/IR/Type.h"
72 #include "llvm/IR/Use.h"
73 #include "llvm/IR/User.h"
74 #include "llvm/IR/Value.h"
75 #include "llvm/Support/BranchProbability.h"
76 #include "llvm/Support/Casting.h"
77 #include "llvm/Support/CommandLine.h"
78 #include "llvm/Support/Compiler.h"
79 #include "llvm/Support/Debug.h"
80 #include "llvm/Support/ErrorHandling.h"
81 #include "llvm/Support/raw_ostream.h"
82 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
83 #include "llvm/Transforms/Utils/Cloning.h"
84 #include "llvm/Transforms/Utils/LoopConstrainer.h"
85 #include "llvm/Transforms/Utils/LoopSimplify.h"
86 #include "llvm/Transforms/Utils/LoopUtils.h"
87 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
88 #include "llvm/Transforms/Utils/ValueMapper.h"
89 #include <algorithm>
90 #include <cassert>
91 #include <iterator>
92 #include <optional>
93 #include <utility>
94 
95 using namespace llvm;
96 using namespace llvm::PatternMatch;
97 
98 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
99                                         cl::init(64));
100 
101 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
102                                        cl::init(false));
103 
104 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
105                                       cl::init(false));
106 
107 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
108                                              cl::Hidden, cl::init(false));
109 
110 static cl::opt<unsigned> MinRuntimeIterations("irce-min-runtime-iterations",
111                                               cl::Hidden, cl::init(10));
112 
113 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
114                                                  cl::Hidden, cl::init(true));
115 
116 static cl::opt<bool> AllowNarrowLatchCondition(
117     "irce-allow-narrow-latch", cl::Hidden, cl::init(true),
118     cl::desc("If set to true, IRCE may eliminate wide range checks in loops "
119              "with narrow latch condition."));
120 
121 static cl::opt<unsigned> MaxTypeSizeForOverflowCheck(
122     "irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(32),
123     cl::desc(
124         "Maximum size of range check type for which can be produced runtime "
125         "overflow check of its limit's computation"));
126 
127 static cl::opt<bool>
128     PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks",
129                                    cl::Hidden, cl::init(false));
130 
131 #define DEBUG_TYPE "irce"
132 
133 namespace {
134 
135 /// An inductive range check is conditional branch in a loop with
136 ///
137 ///  1. a very cold successor (i.e. the branch jumps to that successor very
138 ///     rarely)
139 ///
140 ///  and
141 ///
142 ///  2. a condition that is provably true for some contiguous range of values
143 ///     taken by the containing loop's induction variable.
144 ///
145 class InductiveRangeCheck {
146 
147   const SCEV *Begin = nullptr;
148   const SCEV *Step = nullptr;
149   const SCEV *End = nullptr;
150   Use *CheckUse = nullptr;
151 
152   static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE,
153                                   const SCEVAddRecExpr *&Index,
154                                   const SCEV *&End);
155 
156   static void
157   extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
158                              SmallVectorImpl<InductiveRangeCheck> &Checks,
159                              SmallPtrSetImpl<Value *> &Visited);
160 
161   static bool parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
162                                   ICmpInst::Predicate Pred, ScalarEvolution &SE,
163                                   const SCEVAddRecExpr *&Index,
164                                   const SCEV *&End);
165 
166   static bool reassociateSubLHS(Loop *L, Value *VariantLHS, Value *InvariantRHS,
167                                 ICmpInst::Predicate Pred, ScalarEvolution &SE,
168                                 const SCEVAddRecExpr *&Index, const SCEV *&End);
169 
170 public:
171   const SCEV *getBegin() const { return Begin; }
172   const SCEV *getStep() const { return Step; }
173   const SCEV *getEnd() const { return End; }
174 
175   void print(raw_ostream &OS) const {
176     OS << "InductiveRangeCheck:\n";
177     OS << "  Begin: ";
178     Begin->print(OS);
179     OS << "  Step: ";
180     Step->print(OS);
181     OS << "  End: ";
182     End->print(OS);
183     OS << "\n  CheckUse: ";
184     getCheckUse()->getUser()->print(OS);
185     OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
186   }
187 
188   LLVM_DUMP_METHOD
189   void dump() {
190     print(dbgs());
191   }
192 
193   Use *getCheckUse() const { return CheckUse; }
194 
195   /// Represents an signed integer range [Range.getBegin(), Range.getEnd()).  If
196   /// R.getEnd() le R.getBegin(), then R denotes the empty range.
197 
198   class Range {
199     const SCEV *Begin;
200     const SCEV *End;
201 
202   public:
203     Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
204       assert(Begin->getType() == End->getType() && "ill-typed range!");
205     }
206 
207     Type *getType() const { return Begin->getType(); }
208     const SCEV *getBegin() const { return Begin; }
209     const SCEV *getEnd() const { return End; }
210     bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
211       if (Begin == End)
212         return true;
213       if (IsSigned)
214         return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
215       else
216         return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
217     }
218   };
219 
220   /// This is the value the condition of the branch needs to evaluate to for the
221   /// branch to take the hot successor (see (1) above).
222   bool getPassingDirection() { return true; }
223 
224   /// Computes a range for the induction variable (IndVar) in which the range
225   /// check is redundant and can be constant-folded away.  The induction
226   /// variable is not required to be the canonical {0,+,1} induction variable.
227   std::optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
228                                                  const SCEVAddRecExpr *IndVar,
229                                                  bool IsLatchSigned) const;
230 
231   /// Parse out a set of inductive range checks from \p BI and append them to \p
232   /// Checks.
233   ///
234   /// NB! There may be conditions feeding into \p BI that aren't inductive range
235   /// checks, and hence don't end up in \p Checks.
236   static void extractRangeChecksFromBranch(
237       BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
238       SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed);
239 };
240 
241 class InductiveRangeCheckElimination {
242   ScalarEvolution &SE;
243   BranchProbabilityInfo *BPI;
244   DominatorTree &DT;
245   LoopInfo &LI;
246 
247   using GetBFIFunc =
248       std::optional<llvm::function_ref<llvm::BlockFrequencyInfo &()>>;
249   GetBFIFunc GetBFI;
250 
251   // Returns true if it is profitable to do a transform basing on estimation of
252   // number of iterations.
253   bool isProfitableToTransform(const Loop &L, LoopStructure &LS);
254 
255 public:
256   InductiveRangeCheckElimination(ScalarEvolution &SE,
257                                  BranchProbabilityInfo *BPI, DominatorTree &DT,
258                                  LoopInfo &LI, GetBFIFunc GetBFI = std::nullopt)
259       : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
260 
261   bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop);
262 };
263 
264 } // end anonymous namespace
265 
266 /// Parse a single ICmp instruction, `ICI`, into a range check.  If `ICI` cannot
267 /// be interpreted as a range check, return false.  Otherwise set `Index` to the
268 /// SCEV being range checked, and set `End` to the upper or lower limit `Index`
269 /// is being range checked.
270 bool InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
271                                               ScalarEvolution &SE,
272                                               const SCEVAddRecExpr *&Index,
273                                               const SCEV *&End) {
274   auto IsLoopInvariant = [&SE, L](Value *V) {
275     return SE.isLoopInvariant(SE.getSCEV(V), L);
276   };
277 
278   ICmpInst::Predicate Pred = ICI->getPredicate();
279   Value *LHS = ICI->getOperand(0);
280   Value *RHS = ICI->getOperand(1);
281 
282   if (!LHS->getType()->isIntegerTy())
283     return false;
284 
285   // Canonicalize to the `Index Pred Invariant` comparison
286   if (IsLoopInvariant(LHS)) {
287     std::swap(LHS, RHS);
288     Pred = CmpInst::getSwappedPredicate(Pred);
289   } else if (!IsLoopInvariant(RHS))
290     // Both LHS and RHS are loop variant
291     return false;
292 
293   if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE, Index, End))
294     return true;
295 
296   if (reassociateSubLHS(L, LHS, RHS, Pred, SE, Index, End))
297     return true;
298 
299   // TODO: support ReassociateAddLHS
300   return false;
301 }
302 
303 // Try to parse range check in the form of "IV vs Limit"
304 bool InductiveRangeCheck::parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
305                                               ICmpInst::Predicate Pred,
306                                               ScalarEvolution &SE,
307                                               const SCEVAddRecExpr *&Index,
308                                               const SCEV *&End) {
309 
310   auto SIntMaxSCEV = [&](Type *T) {
311     unsigned BitWidth = cast<IntegerType>(T)->getBitWidth();
312     return SE.getConstant(APInt::getSignedMaxValue(BitWidth));
313   };
314 
315   const auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(LHS));
316   if (!AddRec)
317     return false;
318 
319   // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
320   // We can potentially do much better here.
321   // If we want to adjust upper bound for the unsigned range check as we do it
322   // for signed one, we will need to pick Unsigned max
323   switch (Pred) {
324   default:
325     return false;
326 
327   case ICmpInst::ICMP_SGE:
328     if (match(RHS, m_ConstantInt<0>())) {
329       Index = AddRec;
330       End = SIntMaxSCEV(Index->getType());
331       return true;
332     }
333     return false;
334 
335   case ICmpInst::ICMP_SGT:
336     if (match(RHS, m_ConstantInt<-1>())) {
337       Index = AddRec;
338       End = SIntMaxSCEV(Index->getType());
339       return true;
340     }
341     return false;
342 
343   case ICmpInst::ICMP_SLT:
344   case ICmpInst::ICMP_ULT:
345     Index = AddRec;
346     End = SE.getSCEV(RHS);
347     return true;
348 
349   case ICmpInst::ICMP_SLE:
350   case ICmpInst::ICMP_ULE:
351     const SCEV *One = SE.getOne(RHS->getType());
352     const SCEV *RHSS = SE.getSCEV(RHS);
353     bool Signed = Pred == ICmpInst::ICMP_SLE;
354     if (SE.willNotOverflow(Instruction::BinaryOps::Add, Signed, RHSS, One)) {
355       Index = AddRec;
356       End = SE.getAddExpr(RHSS, One);
357       return true;
358     }
359     return false;
360   }
361 
362   llvm_unreachable("default clause returns!");
363 }
364 
365 // Try to parse range check in the form of "IV - Offset vs Limit" or "Offset -
366 // IV vs Limit"
367 bool InductiveRangeCheck::reassociateSubLHS(
368     Loop *L, Value *VariantLHS, Value *InvariantRHS, ICmpInst::Predicate Pred,
369     ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) {
370   Value *LHS, *RHS;
371   if (!match(VariantLHS, m_Sub(m_Value(LHS), m_Value(RHS))))
372     return false;
373 
374   const SCEV *IV = SE.getSCEV(LHS);
375   const SCEV *Offset = SE.getSCEV(RHS);
376   const SCEV *Limit = SE.getSCEV(InvariantRHS);
377 
378   bool OffsetSubtracted = false;
379   if (SE.isLoopInvariant(IV, L))
380     // "Offset - IV vs Limit"
381     std::swap(IV, Offset);
382   else if (SE.isLoopInvariant(Offset, L))
383     // "IV - Offset vs Limit"
384     OffsetSubtracted = true;
385   else
386     return false;
387 
388   const auto *AddRec = dyn_cast<SCEVAddRecExpr>(IV);
389   if (!AddRec)
390     return false;
391 
392   // In order to turn "IV - Offset < Limit" into "IV < Limit + Offset", we need
393   // to be able to freely move values from left side of inequality to right side
394   // (just as in normal linear arithmetics). Overflows make things much more
395   // complicated, so we want to avoid this.
396   //
397   // Let's prove that the initial subtraction doesn't overflow with all IV's
398   // values from the safe range constructed for that check.
399   //
400   // [Case 1] IV - Offset < Limit
401   // It doesn't overflow if:
402   //     SINT_MIN <= IV - Offset <= SINT_MAX
403   // In terms of scaled SINT we need to prove:
404   //     SINT_MIN + Offset <= IV <= SINT_MAX + Offset
405   // Safe range will be constructed:
406   //     0 <= IV < Limit + Offset
407   // It means that 'IV - Offset' doesn't underflow, because:
408   //     SINT_MIN + Offset < 0 <= IV
409   // and doesn't overflow:
410   //     IV < Limit + Offset <= SINT_MAX + Offset
411   //
412   // [Case 2] Offset - IV > Limit
413   // It doesn't overflow if:
414   //     SINT_MIN <= Offset - IV <= SINT_MAX
415   // In terms of scaled SINT we need to prove:
416   //     -SINT_MIN >= IV - Offset >= -SINT_MAX
417   //     Offset - SINT_MIN >= IV >= Offset - SINT_MAX
418   // Safe range will be constructed:
419   //     0 <= IV < Offset - Limit
420   // It means that 'Offset - IV' doesn't underflow, because
421   //     Offset - SINT_MAX < 0 <= IV
422   // and doesn't overflow:
423   //     IV < Offset - Limit <= Offset - SINT_MIN
424   //
425   // For the computed upper boundary of the IV's range (Offset +/- Limit) we
426   // don't know exactly whether it overflows or not. So if we can't prove this
427   // fact at compile time, we scale boundary computations to a wider type with
428   // the intention to add runtime overflow check.
429 
430   auto getExprScaledIfOverflow = [&](Instruction::BinaryOps BinOp,
431                                      const SCEV *LHS,
432                                      const SCEV *RHS) -> const SCEV * {
433     const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
434                                               SCEV::NoWrapFlags, unsigned);
435     switch (BinOp) {
436     default:
437       llvm_unreachable("Unsupported binary op");
438     case Instruction::Add:
439       Operation = &ScalarEvolution::getAddExpr;
440       break;
441     case Instruction::Sub:
442       Operation = &ScalarEvolution::getMinusSCEV;
443       break;
444     }
445 
446     if (SE.willNotOverflow(BinOp, ICmpInst::isSigned(Pred), LHS, RHS,
447                            cast<Instruction>(VariantLHS)))
448       return (SE.*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0);
449 
450     // We couldn't prove that the expression does not overflow.
451     // Than scale it to a wider type to check overflow at runtime.
452     auto *Ty = cast<IntegerType>(LHS->getType());
453     if (Ty->getBitWidth() > MaxTypeSizeForOverflowCheck)
454       return nullptr;
455 
456     auto WideTy = IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
457     return (SE.*Operation)(SE.getSignExtendExpr(LHS, WideTy),
458                            SE.getSignExtendExpr(RHS, WideTy), SCEV::FlagAnyWrap,
459                            0);
460   };
461 
462   if (OffsetSubtracted)
463     // "IV - Offset < Limit" -> "IV" < Offset + Limit
464     Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Offset, Limit);
465   else {
466     // "Offset - IV > Limit" -> "IV" < Offset - Limit
467     Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub, Offset, Limit);
468     Pred = ICmpInst::getSwappedPredicate(Pred);
469   }
470 
471   if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
472     // "Expr <= Limit" -> "Expr < Limit + 1"
473     if (Pred == ICmpInst::ICMP_SLE && Limit)
474       Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit,
475                                       SE.getOne(Limit->getType()));
476     if (Limit) {
477       Index = AddRec;
478       End = Limit;
479       return true;
480     }
481   }
482   return false;
483 }
484 
485 void InductiveRangeCheck::extractRangeChecksFromCond(
486     Loop *L, ScalarEvolution &SE, Use &ConditionUse,
487     SmallVectorImpl<InductiveRangeCheck> &Checks,
488     SmallPtrSetImpl<Value *> &Visited) {
489   Value *Condition = ConditionUse.get();
490   if (!Visited.insert(Condition).second)
491     return;
492 
493   // TODO: Do the same for OR, XOR, NOT etc?
494   if (match(Condition, m_LogicalAnd(m_Value(), m_Value()))) {
495     extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
496                                Checks, Visited);
497     extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
498                                Checks, Visited);
499     return;
500   }
501 
502   ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
503   if (!ICI)
504     return;
505 
506   const SCEV *End = nullptr;
507   const SCEVAddRecExpr *IndexAddRec = nullptr;
508   if (!parseRangeCheckICmp(L, ICI, SE, IndexAddRec, End))
509     return;
510 
511   assert(IndexAddRec && "IndexAddRec was not computed");
512   assert(End && "End was not computed");
513 
514   if ((IndexAddRec->getLoop() != L) || !IndexAddRec->isAffine())
515     return;
516 
517   InductiveRangeCheck IRC;
518   IRC.End = End;
519   IRC.Begin = IndexAddRec->getStart();
520   IRC.Step = IndexAddRec->getStepRecurrence(SE);
521   IRC.CheckUse = &ConditionUse;
522   Checks.push_back(IRC);
523 }
524 
525 void InductiveRangeCheck::extractRangeChecksFromBranch(
526     BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
527     SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed) {
528   if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
529     return;
530 
531   unsigned IndexLoopSucc = L->contains(BI->getSuccessor(0)) ? 0 : 1;
532   assert(L->contains(BI->getSuccessor(IndexLoopSucc)) &&
533          "No edges coming to loop?");
534   BranchProbability LikelyTaken(15, 16);
535 
536   if (!SkipProfitabilityChecks && BPI &&
537       BPI->getEdgeProbability(BI->getParent(), IndexLoopSucc) < LikelyTaken)
538     return;
539 
540   // IRCE expects branch's true edge comes to loop. Invert branch for opposite
541   // case.
542   if (IndexLoopSucc != 0) {
543     IRBuilder<> Builder(BI);
544     InvertBranch(BI, Builder);
545     if (BPI)
546       BPI->swapSuccEdgesProbabilities(BI->getParent());
547     Changed = true;
548   }
549 
550   SmallPtrSet<Value *, 8> Visited;
551   InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
552                                                   Checks, Visited);
553 }
554 
555 /// If the type of \p S matches with \p Ty, return \p S. Otherwise, return
556 /// signed or unsigned extension of \p S to type \p Ty.
557 static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
558                                 bool Signed) {
559   return Signed ? SE.getNoopOrSignExtend(S, Ty) : SE.getNoopOrZeroExtend(S, Ty);
560 }
561 
562 // Compute a safe set of limits for the main loop to run in -- effectively the
563 // intersection of `Range' and the iteration space of the original loop.
564 // Return std::nullopt if unable to compute the set of subranges.
565 static std::optional<LoopConstrainer::SubRanges>
566 calculateSubRanges(ScalarEvolution &SE, const Loop &L,
567                    InductiveRangeCheck::Range &Range,
568                    const LoopStructure &MainLoopStructure) {
569   auto *RTy = cast<IntegerType>(Range.getType());
570   // We only support wide range checks and narrow latches.
571   if (!AllowNarrowLatchCondition && RTy != MainLoopStructure.ExitCountTy)
572     return std::nullopt;
573   if (RTy->getBitWidth() < MainLoopStructure.ExitCountTy->getBitWidth())
574     return std::nullopt;
575 
576   LoopConstrainer::SubRanges Result;
577 
578   bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
579   // I think we can be more aggressive here and make this nuw / nsw if the
580   // addition that feeds into the icmp for the latch's terminating branch is nuw
581   // / nsw.  In any case, a wrapping 2's complement addition is safe.
582   const SCEV *Start = NoopOrExtend(SE.getSCEV(MainLoopStructure.IndVarStart),
583                                    RTy, SE, IsSignedPredicate);
584   const SCEV *End = NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
585                                  SE, IsSignedPredicate);
586 
587   bool Increasing = MainLoopStructure.IndVarIncreasing;
588 
589   // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
590   // [Smallest, GreatestSeen] is the range of values the induction variable
591   // takes.
592 
593   const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
594 
595   const SCEV *One = SE.getOne(RTy);
596   if (Increasing) {
597     Smallest = Start;
598     Greatest = End;
599     // No overflow, because the range [Smallest, GreatestSeen] is not empty.
600     GreatestSeen = SE.getMinusSCEV(End, One);
601   } else {
602     // These two computations may sign-overflow.  Here is why that is okay:
603     //
604     // We know that the induction variable does not sign-overflow on any
605     // iteration except the last one, and it starts at `Start` and ends at
606     // `End`, decrementing by one every time.
607     //
608     //  * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
609     //    induction variable is decreasing we know that the smallest value
610     //    the loop body is actually executed with is `INT_SMIN` == `Smallest`.
611     //
612     //  * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`.  In
613     //    that case, `Clamp` will always return `Smallest` and
614     //    [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
615     //    will be an empty range.  Returning an empty range is always safe.
616 
617     Smallest = SE.getAddExpr(End, One);
618     Greatest = SE.getAddExpr(Start, One);
619     GreatestSeen = Start;
620   }
621 
622   auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
623     return IsSignedPredicate
624                ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
625                : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
626   };
627 
628   // In some cases we can prove that we don't need a pre or post loop.
629   ICmpInst::Predicate PredLE =
630       IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
631   ICmpInst::Predicate PredLT =
632       IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
633 
634   bool ProvablyNoPreloop =
635       SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
636   if (!ProvablyNoPreloop)
637     Result.LowLimit = Clamp(Range.getBegin());
638 
639   bool ProvablyNoPostLoop =
640       SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
641   if (!ProvablyNoPostLoop)
642     Result.HighLimit = Clamp(Range.getEnd());
643 
644   return Result;
645 }
646 
647 /// Computes and returns a range of values for the induction variable (IndVar)
648 /// in which the range check can be safely elided.  If it cannot compute such a
649 /// range, returns std::nullopt.
650 std::optional<InductiveRangeCheck::Range>
651 InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
652                                                const SCEVAddRecExpr *IndVar,
653                                                bool IsLatchSigned) const {
654   // We can deal when types of latch check and range checks don't match in case
655   // if latch check is more narrow.
656   auto *IVType = dyn_cast<IntegerType>(IndVar->getType());
657   auto *RCType = dyn_cast<IntegerType>(getBegin()->getType());
658   auto *EndType = dyn_cast<IntegerType>(getEnd()->getType());
659   // Do not work with pointer types.
660   if (!IVType || !RCType)
661     return std::nullopt;
662   if (IVType->getBitWidth() > RCType->getBitWidth())
663     return std::nullopt;
664 
665   // IndVar is of the form "A + B * I" (where "I" is the canonical induction
666   // variable, that may or may not exist as a real llvm::Value in the loop) and
667   // this inductive range check is a range check on the "C + D * I" ("C" is
668   // getBegin() and "D" is getStep()).  We rewrite the value being range
669   // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
670   //
671   // The actual inequalities we solve are of the form
672   //
673   //   0 <= M + 1 * IndVar < L given L >= 0  (i.e. N == 1)
674   //
675   // Here L stands for upper limit of the safe iteration space.
676   // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
677   // overflows when calculating (0 - M) and (L - M) we, depending on type of
678   // IV's iteration space, limit the calculations by borders of the iteration
679   // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
680   // If we figured out that "anything greater than (-M) is safe", we strengthen
681   // this to "everything greater than 0 is safe", assuming that values between
682   // -M and 0 just do not exist in unsigned iteration space, and we don't want
683   // to deal with overflown values.
684 
685   if (!IndVar->isAffine())
686     return std::nullopt;
687 
688   const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned);
689   const SCEVConstant *B = dyn_cast<SCEVConstant>(
690       NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned));
691   if (!B)
692     return std::nullopt;
693   assert(!B->isZero() && "Recurrence with zero step?");
694 
695   const SCEV *C = getBegin();
696   const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
697   if (D != B)
698     return std::nullopt;
699 
700   assert(!D->getValue()->isZero() && "Recurrence with zero step?");
701   unsigned BitWidth = RCType->getBitWidth();
702   const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
703   const SCEV *SIntMin = SE.getConstant(APInt::getSignedMinValue(BitWidth));
704 
705   // Subtract Y from X so that it does not go through border of the IV
706   // iteration space. Mathematically, it is equivalent to:
707   //
708   //    ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX).        [1]
709   //
710   // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
711   // any width of bit grid). But after we take min/max, the result is
712   // guaranteed to be within [INT_MIN, INT_MAX].
713   //
714   // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
715   // values, depending on type of latch condition that defines IV iteration
716   // space.
717   auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
718     // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
719     // This is required to ensure that SINT_MAX - X does not overflow signed and
720     // that X - Y does not overflow unsigned if Y is negative. Can we lift this
721     // restriction and make it work for negative X either?
722     if (IsLatchSigned) {
723       // X is a number from signed range, Y is interpreted as signed.
724       // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
725       // thing we should care about is that we didn't cross SINT_MAX.
726       // So, if Y is positive, we subtract Y safely.
727       //   Rule 1: Y > 0 ---> Y.
728       // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely.
729       //   Rule 2: Y >=s (X - SINT_MAX) ---> Y.
730       // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX).
731       //   Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
732       // It gives us smax(Y, X - SINT_MAX) to subtract in all cases.
733       const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
734       return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
735                              SCEV::FlagNSW);
736     } else
737       // X is a number from unsigned range, Y is interpreted as signed.
738       // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
739       // thing we should care about is that we didn't cross zero.
740       // So, if Y is negative, we subtract Y safely.
741       //   Rule 1: Y <s 0 ---> Y.
742       // If 0 <= Y <= X, we subtract Y safely.
743       //   Rule 2: Y <=s X ---> Y.
744       // If 0 <= X < Y, we should stop at 0 and can only subtract X.
745       //   Rule 3: Y >s X ---> X.
746       // It gives us smin(X, Y) to subtract in all cases.
747       return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
748   };
749   const SCEV *M = SE.getMinusSCEV(C, A);
750   const SCEV *Zero = SE.getZero(M->getType());
751 
752   // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
753   auto SCEVCheckNonNegative = [&](const SCEV *X) {
754     const Loop *L = IndVar->getLoop();
755     const SCEV *Zero = SE.getZero(X->getType());
756     const SCEV *One = SE.getOne(X->getType());
757     // Can we trivially prove that X is a non-negative or negative value?
758     if (isKnownNonNegativeInLoop(X, L, SE))
759       return One;
760     else if (isKnownNegativeInLoop(X, L, SE))
761       return Zero;
762     // If not, we will have to figure it out during the execution.
763     // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
764     const SCEV *NegOne = SE.getNegativeSCEV(One);
765     return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
766   };
767 
768   // This function returns SCEV equal to 1 if X will not overflow in terms of
769   // range check type, 0 otherwise.
770   auto SCEVCheckWillNotOverflow = [&](const SCEV *X) {
771     // X doesn't overflow if SINT_MAX >= X.
772     // Then if (SINT_MAX - X) >= 0, X doesn't overflow
773     const SCEV *SIntMaxExt = SE.getSignExtendExpr(SIntMax, X->getType());
774     const SCEV *OverflowCheck =
775         SCEVCheckNonNegative(SE.getMinusSCEV(SIntMaxExt, X));
776 
777     // X doesn't underflow if X >= SINT_MIN.
778     // Then if (X - SINT_MIN) >= 0, X doesn't underflow
779     const SCEV *SIntMinExt = SE.getSignExtendExpr(SIntMin, X->getType());
780     const SCEV *UnderflowCheck =
781         SCEVCheckNonNegative(SE.getMinusSCEV(X, SIntMinExt));
782 
783     return SE.getMulExpr(OverflowCheck, UnderflowCheck);
784   };
785 
786   // FIXME: Current implementation of ClampedSubtract implicitly assumes that
787   // X is non-negative (in sense of a signed value). We need to re-implement
788   // this function in a way that it will correctly handle negative X as well.
789   // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
790   // end up with a negative X and produce wrong results. So currently we ensure
791   // that if getEnd() is negative then both ends of the safe range are zero.
792   // Note that this may pessimize elimination of unsigned range checks against
793   // negative values.
794   const SCEV *REnd = getEnd();
795   const SCEV *EndWillNotOverflow = SE.getOne(RCType);
796 
797   auto PrintRangeCheck = [&](raw_ostream &OS) {
798     auto L = IndVar->getLoop();
799     OS << "irce: in function ";
800     OS << L->getHeader()->getParent()->getName();
801     OS << ", in ";
802     L->print(OS);
803     OS << "there is range check with scaled boundary:\n";
804     print(OS);
805   };
806 
807   if (EndType->getBitWidth() > RCType->getBitWidth()) {
808     assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
809     if (PrintScaledBoundaryRangeChecks)
810       PrintRangeCheck(errs());
811     // End is computed with extended type but will be truncated to a narrow one
812     // type of range check. Therefore we need a check that the result will not
813     // overflow in terms of narrow type.
814     EndWillNotOverflow =
815         SE.getTruncateExpr(SCEVCheckWillNotOverflow(REnd), RCType);
816     REnd = SE.getTruncateExpr(REnd, RCType);
817   }
818 
819   const SCEV *RuntimeChecks =
820       SE.getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
821   const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
822   const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), RuntimeChecks);
823 
824   return InductiveRangeCheck::Range(Begin, End);
825 }
826 
827 static std::optional<InductiveRangeCheck::Range>
828 IntersectSignedRange(ScalarEvolution &SE,
829                      const std::optional<InductiveRangeCheck::Range> &R1,
830                      const InductiveRangeCheck::Range &R2) {
831   if (R2.isEmpty(SE, /* IsSigned */ true))
832     return std::nullopt;
833   if (!R1)
834     return R2;
835   auto &R1Value = *R1;
836   // We never return empty ranges from this function, and R1 is supposed to be
837   // a result of intersection. Thus, R1 is never empty.
838   assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
839          "We should never have empty R1!");
840 
841   // TODO: we could widen the smaller range and have this work; but for now we
842   // bail out to keep things simple.
843   if (R1Value.getType() != R2.getType())
844     return std::nullopt;
845 
846   const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
847   const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
848 
849   // If the resulting range is empty, just return std::nullopt.
850   auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
851   if (Ret.isEmpty(SE, /* IsSigned */ true))
852     return std::nullopt;
853   return Ret;
854 }
855 
856 static std::optional<InductiveRangeCheck::Range>
857 IntersectUnsignedRange(ScalarEvolution &SE,
858                        const std::optional<InductiveRangeCheck::Range> &R1,
859                        const InductiveRangeCheck::Range &R2) {
860   if (R2.isEmpty(SE, /* IsSigned */ false))
861     return std::nullopt;
862   if (!R1)
863     return R2;
864   auto &R1Value = *R1;
865   // We never return empty ranges from this function, and R1 is supposed to be
866   // a result of intersection. Thus, R1 is never empty.
867   assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
868          "We should never have empty R1!");
869 
870   // TODO: we could widen the smaller range and have this work; but for now we
871   // bail out to keep things simple.
872   if (R1Value.getType() != R2.getType())
873     return std::nullopt;
874 
875   const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
876   const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
877 
878   // If the resulting range is empty, just return std::nullopt.
879   auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
880   if (Ret.isEmpty(SE, /* IsSigned */ false))
881     return std::nullopt;
882   return Ret;
883 }
884 
885 PreservedAnalyses IRCEPass::run(Function &F, FunctionAnalysisManager &AM) {
886   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
887   LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
888   // There are no loops in the function. Return before computing other expensive
889   // analyses.
890   if (LI.empty())
891     return PreservedAnalyses::all();
892   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
893   auto &BPI = AM.getResult<BranchProbabilityAnalysis>(F);
894 
895   // Get BFI analysis result on demand. Please note that modification of
896   // CFG invalidates this analysis and we should handle it.
897   auto getBFI = [&F, &AM ]()->BlockFrequencyInfo & {
898     return AM.getResult<BlockFrequencyAnalysis>(F);
899   };
900   InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
901 
902   bool Changed = false;
903   {
904     bool CFGChanged = false;
905     for (const auto &L : LI) {
906       CFGChanged |= simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr,
907                                  /*PreserveLCSSA=*/false);
908       Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
909     }
910     Changed |= CFGChanged;
911 
912     if (CFGChanged && !SkipProfitabilityChecks) {
913       PreservedAnalyses PA = PreservedAnalyses::all();
914       PA.abandon<BlockFrequencyAnalysis>();
915       AM.invalidate(F, PA);
916     }
917   }
918 
919   SmallPriorityWorklist<Loop *, 4> Worklist;
920   appendLoopsToWorklist(LI, Worklist);
921   auto LPMAddNewLoop = [&Worklist](Loop *NL, bool IsSubloop) {
922     if (!IsSubloop)
923       appendLoopsToWorklist(*NL, Worklist);
924   };
925 
926   while (!Worklist.empty()) {
927     Loop *L = Worklist.pop_back_val();
928     if (IRCE.run(L, LPMAddNewLoop)) {
929       Changed = true;
930       if (!SkipProfitabilityChecks) {
931         PreservedAnalyses PA = PreservedAnalyses::all();
932         PA.abandon<BlockFrequencyAnalysis>();
933         AM.invalidate(F, PA);
934       }
935     }
936   }
937 
938   if (!Changed)
939     return PreservedAnalyses::all();
940   return getLoopPassPreservedAnalyses();
941 }
942 
943 bool
944 InductiveRangeCheckElimination::isProfitableToTransform(const Loop &L,
945                                                         LoopStructure &LS) {
946   if (SkipProfitabilityChecks)
947     return true;
948   if (GetBFI) {
949     BlockFrequencyInfo &BFI = (*GetBFI)();
950     uint64_t hFreq = BFI.getBlockFreq(LS.Header).getFrequency();
951     uint64_t phFreq = BFI.getBlockFreq(L.getLoopPreheader()).getFrequency();
952     if (phFreq != 0 && hFreq != 0 && (hFreq / phFreq < MinRuntimeIterations)) {
953       LLVM_DEBUG(dbgs() << "irce: could not prove profitability: "
954                         << "the estimated number of iterations basing on "
955                            "frequency info is " << (hFreq / phFreq) << "\n";);
956       return false;
957     }
958     return true;
959   }
960 
961   if (!BPI)
962     return true;
963   BranchProbability ExitProbability =
964       BPI->getEdgeProbability(LS.Latch, LS.LatchBrExitIdx);
965   if (ExitProbability > BranchProbability(1, MinRuntimeIterations)) {
966     LLVM_DEBUG(dbgs() << "irce: could not prove profitability: "
967                       << "the exit probability is too big " << ExitProbability
968                       << "\n";);
969     return false;
970   }
971   return true;
972 }
973 
974 bool InductiveRangeCheckElimination::run(
975     Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
976   if (L->getBlocks().size() >= LoopSizeCutoff) {
977     LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n");
978     return false;
979   }
980 
981   BasicBlock *Preheader = L->getLoopPreheader();
982   if (!Preheader) {
983     LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
984     return false;
985   }
986 
987   LLVMContext &Context = Preheader->getContext();
988   SmallVector<InductiveRangeCheck, 16> RangeChecks;
989   bool Changed = false;
990 
991   for (auto *BBI : L->getBlocks())
992     if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
993       InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
994                                                         RangeChecks, Changed);
995 
996   if (RangeChecks.empty())
997     return Changed;
998 
999   auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1000     OS << "irce: looking at loop "; L->print(OS);
1001     OS << "irce: loop has " << RangeChecks.size()
1002        << " inductive range checks: \n";
1003     for (InductiveRangeCheck &IRC : RangeChecks)
1004       IRC.print(OS);
1005   };
1006 
1007   LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs()));
1008 
1009   if (PrintRangeChecks)
1010     PrintRecognizedRangeChecks(errs());
1011 
1012   const char *FailureReason = nullptr;
1013   std::optional<LoopStructure> MaybeLoopStructure =
1014       LoopStructure::parseLoopStructure(SE, *L, AllowUnsignedLatchCondition,
1015                                         FailureReason);
1016   if (!MaybeLoopStructure) {
1017     LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: "
1018                       << FailureReason << "\n";);
1019     return Changed;
1020   }
1021   LoopStructure LS = *MaybeLoopStructure;
1022   if (!isProfitableToTransform(*L, LS))
1023     return Changed;
1024   const SCEVAddRecExpr *IndVar =
1025       cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1026 
1027   std::optional<InductiveRangeCheck::Range> SafeIterRange;
1028 
1029   SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1030   // Basing on the type of latch predicate, we interpret the IV iteration range
1031   // as signed or unsigned range. We use different min/max functions (signed or
1032   // unsigned) when intersecting this range with safe iteration ranges implied
1033   // by range checks.
1034   auto IntersectRange =
1035       LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
1036 
1037   for (InductiveRangeCheck &IRC : RangeChecks) {
1038     auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1039                                                 LS.IsSignedPredicate);
1040     if (Result) {
1041       auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1042       if (MaybeSafeIterRange) {
1043         assert(!MaybeSafeIterRange->isEmpty(SE, LS.IsSignedPredicate) &&
1044                "We should never return empty ranges!");
1045         RangeChecksToEliminate.push_back(IRC);
1046         SafeIterRange = *MaybeSafeIterRange;
1047       }
1048     }
1049   }
1050 
1051   if (!SafeIterRange)
1052     return Changed;
1053 
1054   std::optional<LoopConstrainer::SubRanges> MaybeSR =
1055       calculateSubRanges(SE, *L, *SafeIterRange, LS);
1056   if (!MaybeSR) {
1057     LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n");
1058     return false;
1059   }
1060 
1061   LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
1062                      SafeIterRange->getBegin()->getType(), *MaybeSR);
1063 
1064   if (LC.run()) {
1065     Changed = true;
1066 
1067     auto PrintConstrainedLoopInfo = [L]() {
1068       dbgs() << "irce: in function ";
1069       dbgs() << L->getHeader()->getParent()->getName() << ": ";
1070       dbgs() << "constrained ";
1071       L->print(dbgs());
1072     };
1073 
1074     LLVM_DEBUG(PrintConstrainedLoopInfo());
1075 
1076     if (PrintChangedLoops)
1077       PrintConstrainedLoopInfo();
1078 
1079     // Optimize away the now-redundant range checks.
1080 
1081     for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1082       ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1083                                           ? ConstantInt::getTrue(Context)
1084                                           : ConstantInt::getFalse(Context);
1085       IRC.getCheckUse()->set(FoldedRangeCheck);
1086     }
1087   }
1088 
1089   return Changed;
1090 }
1091