llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

   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   // Canonicalize to the `Index Pred Invariant` comparison
 283   if (IsLoopInvariant(LHS)) {
 284     std::swap(LHS, RHS);
 285     Pred = CmpInst::getSwappedPredicate(Pred);
 286   } else if (!IsLoopInvariant(RHS))
 287     // Both LHS and RHS are loop variant
 288     return false;
 289
 290   if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE, Index, End))
 291     return true;
 292
 293   if (reassociateSubLHS(L, LHS, RHS, Pred, SE, Index, End))
 294     return true;
 295
 296   // TODO: support ReassociateAddLHS
 297   return false;
 298 }
 299
 300 // Try to parse range check in the form of "IV vs Limit"
 301 bool InductiveRangeCheck::parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
 302                                               ICmpInst::Predicate Pred,
 303                                               ScalarEvolution &SE,
 304                                               const SCEVAddRecExpr *&Index,
 305                                               const SCEV *&End) {
 306
 307   auto SIntMaxSCEV = [&](Type *T) {
 308     unsigned BitWidth = cast<IntegerType>(T)->getBitWidth();
 309     return SE.getConstant(APInt::getSignedMaxValue(BitWidth));
 310   };
 311
 312   const auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(LHS));
 313   if (!AddRec)
 314     return false;
 315
 316   // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
 317   // We can potentially do much better here.
 318   // If we want to adjust upper bound for the unsigned range check as we do it
 319   // for signed one, we will need to pick Unsigned max
 320   switch (Pred) {
 321   default:
 322     return false;
 323
 324   case ICmpInst::ICMP_SGE:
 325     if (match(RHS, m_ConstantInt<0>())) {
 326       Index = AddRec;
 327       End = SIntMaxSCEV(Index->getType());
 328       return true;
 329     }
 330     return false;
 331
 332   case ICmpInst::ICMP_SGT:
 333     if (match(RHS, m_ConstantInt<-1>())) {
 334       Index = AddRec;
 335       End = SIntMaxSCEV(Index->getType());
 336       return true;
 337     }
 338     return false;
 339
 340   case ICmpInst::ICMP_SLT:
 341   case ICmpInst::ICMP_ULT:
 342     Index = AddRec;
 343     End = SE.getSCEV(RHS);
 344     return true;
 345
 346   case ICmpInst::ICMP_SLE:
 347   case ICmpInst::ICMP_ULE:
 348     const SCEV *One = SE.getOne(RHS->getType());
 349     const SCEV *RHSS = SE.getSCEV(RHS);
 350     bool Signed = Pred == ICmpInst::ICMP_SLE;
 351     if (SE.willNotOverflow(Instruction::BinaryOps::Add, Signed, RHSS, One)) {
 352       Index = AddRec;
 353       End = SE.getAddExpr(RHSS, One);
 354       return true;
 355     }
 356     return false;
 357   }
 358
 359   llvm_unreachable("default clause returns!");
 360 }
 361
 362 // Try to parse range check in the form of "IV - Offset vs Limit" or "Offset -
 363 // IV vs Limit"
 364 bool InductiveRangeCheck::reassociateSubLHS(
 365     Loop *L, Value *VariantLHS, Value *InvariantRHS, ICmpInst::Predicate Pred,
 366     ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) {
 367   Value *LHS, *RHS;
 368   if (!match(VariantLHS, m_Sub(m_Value(LHS), m_Value(RHS))))
 369     return false;
 370
 371   const SCEV *IV = SE.getSCEV(LHS);
 372   const SCEV *Offset = SE.getSCEV(RHS);
 373   const SCEV *Limit = SE.getSCEV(InvariantRHS);
 374
 375   bool OffsetSubtracted = false;
 376   if (SE.isLoopInvariant(IV, L))
 377     // "Offset - IV vs Limit"
 378     std::swap(IV, Offset);
 379   else if (SE.isLoopInvariant(Offset, L))
 380     // "IV - Offset vs Limit"
 381     OffsetSubtracted = true;
 382   else
 383     return false;
 384
 385   const auto *AddRec = dyn_cast<SCEVAddRecExpr>(IV);
 386   if (!AddRec)
 387     return false;
 388
 389   // In order to turn "IV - Offset < Limit" into "IV < Limit + Offset", we need
 390   // to be able to freely move values from left side of inequality to right side
 391   // (just as in normal linear arithmetics). Overflows make things much more
 392   // complicated, so we want to avoid this.
 393   //
 394   // Let's prove that the initial subtraction doesn't overflow with all IV's
 395   // values from the safe range constructed for that check.
 396   //
 397   // [Case 1] IV - Offset < Limit
 398   // It doesn't overflow if:
 399   //     SINT_MIN <= IV - Offset <= SINT_MAX
 400   // In terms of scaled SINT we need to prove:
 401   //     SINT_MIN + Offset <= IV <= SINT_MAX + Offset
 402   // Safe range will be constructed:
 403   //     0 <= IV < Limit + Offset
 404   // It means that 'IV - Offset' doesn't underflow, because:
 405   //     SINT_MIN + Offset < 0 <= IV
 406   // and doesn't overflow:
 407   //     IV < Limit + Offset <= SINT_MAX + Offset
 408   //
 409   // [Case 2] Offset - IV > Limit
 410   // It doesn't overflow if:
 411   //     SINT_MIN <= Offset - IV <= SINT_MAX
 412   // In terms of scaled SINT we need to prove:
 413   //     -SINT_MIN >= IV - Offset >= -SINT_MAX
 414   //     Offset - SINT_MIN >= IV >= Offset - SINT_MAX
 415   // Safe range will be constructed:
 416   //     0 <= IV < Offset - Limit
 417   // It means that 'Offset - IV' doesn't underflow, because
 418   //     Offset - SINT_MAX < 0 <= IV
 419   // and doesn't overflow:
 420   //     IV < Offset - Limit <= Offset - SINT_MIN
 421   //
 422   // For the computed upper boundary of the IV's range (Offset +/- Limit) we
 423   // don't know exactly whether it overflows or not. So if we can't prove this
 424   // fact at compile time, we scale boundary computations to a wider type with
 425   // the intention to add runtime overflow check.
 426
 427   auto getExprScaledIfOverflow = [&](Instruction::BinaryOps BinOp,
 428                                      const SCEV *LHS,
 429                                      const SCEV *RHS) -> const SCEV * {
 430     const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
 431                                               SCEV::NoWrapFlags, unsigned);
 432     switch (BinOp) {
 433     default:
 434       llvm_unreachable("Unsupported binary op");
 435     case Instruction::Add:
 436       Operation = &ScalarEvolution::getAddExpr;
 437       break;
 438     case Instruction::Sub:
 439       Operation = &ScalarEvolution::getMinusSCEV;
 440       break;
 441     }
 442
 443     if (SE.willNotOverflow(BinOp, ICmpInst::isSigned(Pred), LHS, RHS,
 444                            cast<Instruction>(VariantLHS)))
 445       return (SE.*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0);
 446
 447     // We couldn't prove that the expression does not overflow.
 448     // Than scale it to a wider type to check overflow at runtime.
 449     auto *Ty = cast<IntegerType>(LHS->getType());
 450     if (Ty->getBitWidth() > MaxTypeSizeForOverflowCheck)
 451       return nullptr;
 452
 453     auto WideTy = IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
 454     return (SE.*Operation)(SE.getSignExtendExpr(LHS, WideTy),
 455                            SE.getSignExtendExpr(RHS, WideTy), SCEV::FlagAnyWrap,
 456                            0);
 457   };
 458
 459   if (OffsetSubtracted)
 460     // "IV - Offset < Limit" -> "IV" < Offset + Limit
 461     Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Offset, Limit);
 462   else {
 463     // "Offset - IV > Limit" -> "IV" < Offset - Limit
 464     Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub, Offset, Limit);
 465     Pred = ICmpInst::getSwappedPredicate(Pred);
 466   }
 467
 468   if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
 469     // "Expr <= Limit" -> "Expr < Limit + 1"
 470     if (Pred == ICmpInst::ICMP_SLE && Limit)
 471       Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit,
 472                                       SE.getOne(Limit->getType()));
 473     if (Limit) {
 474       Index = AddRec;
 475       End = Limit;
 476       return true;
 477     }
 478   }
 479   return false;
 480 }
 481
 482 void InductiveRangeCheck::extractRangeChecksFromCond(
 483     Loop *L, ScalarEvolution &SE, Use &ConditionUse,
 484     SmallVectorImpl<InductiveRangeCheck> &Checks,
 485     SmallPtrSetImpl<Value *> &Visited) {
 486   Value *Condition = ConditionUse.get();
 487   if (!Visited.insert(Condition).second)
 488     return;
 489
 490   // TODO: Do the same for OR, XOR, NOT etc?
 491   if (match(Condition, m_LogicalAnd(m_Value(), m_Value()))) {
 492     extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
 493                                Checks, Visited);
 494     extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
 495                                Checks, Visited);
 496     return;
 497   }
 498
 499   ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
 500   if (!ICI)
 501     return;
 502
 503   const SCEV *End = nullptr;
 504   const SCEVAddRecExpr *IndexAddRec = nullptr;
 505   if (!parseRangeCheckICmp(L, ICI, SE, IndexAddRec, End))
 506     return;
 507
 508   assert(IndexAddRec && "IndexAddRec was not computed");
 509   assert(End && "End was not computed");
 510
 511   if ((IndexAddRec->getLoop() != L) || !IndexAddRec->isAffine())
 512     return;
 513
 514   InductiveRangeCheck IRC;
 515   IRC.End = End;
 516   IRC.Begin = IndexAddRec->getStart();
 517   IRC.Step = IndexAddRec->getStepRecurrence(SE);
 518   IRC.CheckUse = &ConditionUse;
 519   Checks.push_back(IRC);
 520 }
 521
 522 void InductiveRangeCheck::extractRangeChecksFromBranch(
 523     BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
 524     SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed) {
 525   if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
 526     return;
 527
 528   unsigned IndexLoopSucc = L->contains(BI->getSuccessor(0)) ? 0 : 1;
 529   assert(L->contains(BI->getSuccessor(IndexLoopSucc)) &&
 530          "No edges coming to loop?");
 531   BranchProbability LikelyTaken(15, 16);
 532
 533   if (!SkipProfitabilityChecks && BPI &&
 534       BPI->getEdgeProbability(BI->getParent(), IndexLoopSucc) < LikelyTaken)
 535     return;
 536
 537   // IRCE expects branch's true edge comes to loop. Invert branch for opposite
 538   // case.
 539   if (IndexLoopSucc != 0) {
 540     IRBuilder<> Builder(BI);
 541     InvertBranch(BI, Builder);
 542     if (BPI)
 543       BPI->swapSuccEdgesProbabilities(BI->getParent());
 544     Changed = true;
 545   }
 546
 547   SmallPtrSet<Value *, 8> Visited;
 548   InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
 549                                                   Checks, Visited);
 550 }
 551
 552 /// If the type of \p S matches with \p Ty, return \p S. Otherwise, return
 553 /// signed or unsigned extension of \p S to type \p Ty.
 554 static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
 555                                 bool Signed) {
 556   return Signed ? SE.getNoopOrSignExtend(S, Ty) : SE.getNoopOrZeroExtend(S, Ty);
 557 }
 558
 559 // Compute a safe set of limits for the main loop to run in -- effectively the
 560 // intersection of `Range' and the iteration space of the original loop.
 561 // Return std::nullopt if unable to compute the set of subranges.
 562 static std::optional<LoopConstrainer::SubRanges>
 563 calculateSubRanges(ScalarEvolution &SE, const Loop &L,
 564                    InductiveRangeCheck::Range &Range,
 565                    const LoopStructure &MainLoopStructure) {
 566   auto *RTy = cast<IntegerType>(Range.getType());
 567   // We only support wide range checks and narrow latches.
 568   if (!AllowNarrowLatchCondition && RTy != MainLoopStructure.ExitCountTy)
 569     return std::nullopt;
 570   if (RTy->getBitWidth() < MainLoopStructure.ExitCountTy->getBitWidth())
 571     return std::nullopt;
 572
 573   LoopConstrainer::SubRanges Result;
 574
 575   bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
 576   // I think we can be more aggressive here and make this nuw / nsw if the
 577   // addition that feeds into the icmp for the latch's terminating branch is nuw
 578   // / nsw.  In any case, a wrapping 2's complement addition is safe.
 579   const SCEV *Start = NoopOrExtend(SE.getSCEV(MainLoopStructure.IndVarStart),
 580                                    RTy, SE, IsSignedPredicate);
 581   const SCEV *End = NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
 582                                  SE, IsSignedPredicate);
 583
 584   bool Increasing = MainLoopStructure.IndVarIncreasing;
 585
 586   // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
 587   // [Smallest, GreatestSeen] is the range of values the induction variable
 588   // takes.
 589
 590   const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
 591
 592   const SCEV *One = SE.getOne(RTy);
 593   if (Increasing) {
 594     Smallest = Start;
 595     Greatest = End;
 596     // No overflow, because the range [Smallest, GreatestSeen] is not empty.
 597     GreatestSeen = SE.getMinusSCEV(End, One);
 598   } else {
 599     // These two computations may sign-overflow.  Here is why that is okay:
 600     //
 601     // We know that the induction variable does not sign-overflow on any
 602     // iteration except the last one, and it starts at `Start` and ends at
 603     // `End`, decrementing by one every time.
 604     //
 605     //  * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
 606     //    induction variable is decreasing we know that the smallest value
 607     //    the loop body is actually executed with is `INT_SMIN` == `Smallest`.
 608     //
 609     //  * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`.  In
 610     //    that case, `Clamp` will always return `Smallest` and
 611     //    [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
 612     //    will be an empty range.  Returning an empty range is always safe.
 613
 614     Smallest = SE.getAddExpr(End, One);
 615     Greatest = SE.getAddExpr(Start, One);
 616     GreatestSeen = Start;
 617   }
 618
 619   auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
 620     return IsSignedPredicate
 621                ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
 622                : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
 623   };
 624
 625   // In some cases we can prove that we don't need a pre or post loop.
 626   ICmpInst::Predicate PredLE =
 627       IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
 628   ICmpInst::Predicate PredLT =
 629       IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
 630
 631   bool ProvablyNoPreloop =
 632       SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
 633   if (!ProvablyNoPreloop)
 634     Result.LowLimit = Clamp(Range.getBegin());
 635
 636   bool ProvablyNoPostLoop =
 637       SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
 638   if (!ProvablyNoPostLoop)
 639     Result.HighLimit = Clamp(Range.getEnd());
 640
 641   return Result;
 642 }
 643
 644 /// Computes and returns a range of values for the induction variable (IndVar)
 645 /// in which the range check can be safely elided.  If it cannot compute such a
 646 /// range, returns std::nullopt.
 647 std::optional<InductiveRangeCheck::Range>
 648 InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
 649                                                const SCEVAddRecExpr *IndVar,
 650                                                bool IsLatchSigned) const {
 651   // We can deal when types of latch check and range checks don't match in case
 652   // if latch check is more narrow.
 653   auto *IVType = dyn_cast<IntegerType>(IndVar->getType());
 654   auto *RCType = dyn_cast<IntegerType>(getBegin()->getType());
 655   auto *EndType = dyn_cast<IntegerType>(getEnd()->getType());
 656   // Do not work with pointer types.
 657   if (!IVType || !RCType)
 658     return std::nullopt;
 659   if (IVType->getBitWidth() > RCType->getBitWidth())
 660     return std::nullopt;
 661
 662   // IndVar is of the form "A + B * I" (where "I" is the canonical induction
 663   // variable, that may or may not exist as a real llvm::Value in the loop) and
 664   // this inductive range check is a range check on the "C + D * I" ("C" is
 665   // getBegin() and "D" is getStep()).  We rewrite the value being range
 666   // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
 667   //
 668   // The actual inequalities we solve are of the form
 669   //
 670   //   0 <= M + 1 * IndVar < L given L >= 0  (i.e. N == 1)
 671   //
 672   // Here L stands for upper limit of the safe iteration space.
 673   // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
 674   // overflows when calculating (0 - M) and (L - M) we, depending on type of
 675   // IV's iteration space, limit the calculations by borders of the iteration
 676   // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
 677   // If we figured out that "anything greater than (-M) is safe", we strengthen
 678   // this to "everything greater than 0 is safe", assuming that values between
 679   // -M and 0 just do not exist in unsigned iteration space, and we don't want
 680   // to deal with overflown values.
 681
 682   if (!IndVar->isAffine())
 683     return std::nullopt;
 684
 685   const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned);
 686   const SCEVConstant *B = dyn_cast<SCEVConstant>(
 687       NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned));
 688   if (!B)
 689     return std::nullopt;
 690   assert(!B->isZero() && "Recurrence with zero step?");
 691
 692   const SCEV *C = getBegin();
 693   const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
 694   if (D != B)
 695     return std::nullopt;
 696
 697   assert(!D->getValue()->isZero() && "Recurrence with zero step?");
 698   unsigned BitWidth = RCType->getBitWidth();
 699   const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
 700   const SCEV *SIntMin = SE.getConstant(APInt::getSignedMinValue(BitWidth));
 701
 702   // Subtract Y from X so that it does not go through border of the IV
 703   // iteration space. Mathematically, it is equivalent to:
 704   //
 705   //    ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX).        [1]
 706   //
 707   // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
 708   // any width of bit grid). But after we take min/max, the result is
 709   // guaranteed to be within [INT_MIN, INT_MAX].
 710   //
 711   // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
 712   // values, depending on type of latch condition that defines IV iteration
 713   // space.
 714   auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
 715     // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
 716     // This is required to ensure that SINT_MAX - X does not overflow signed and
 717     // that X - Y does not overflow unsigned if Y is negative. Can we lift this
 718     // restriction and make it work for negative X either?
 719     if (IsLatchSigned) {
 720       // X is a number from signed range, Y is interpreted as signed.
 721       // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
 722       // thing we should care about is that we didn't cross SINT_MAX.
 723       // So, if Y is positive, we subtract Y safely.
 724       //   Rule 1: Y > 0 ---> Y.
 725       // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely.
 726       //   Rule 2: Y >=s (X - SINT_MAX) ---> Y.
 727       // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX).
 728       //   Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
 729       // It gives us smax(Y, X - SINT_MAX) to subtract in all cases.
 730       const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
 731       return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
 732                              SCEV::FlagNSW);
 733     } else
 734       // X is a number from unsigned range, Y is interpreted as signed.
 735       // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
 736       // thing we should care about is that we didn't cross zero.
 737       // So, if Y is negative, we subtract Y safely.
 738       //   Rule 1: Y <s 0 ---> Y.
 739       // If 0 <= Y <= X, we subtract Y safely.
 740       //   Rule 2: Y <=s X ---> Y.
 741       // If 0 <= X < Y, we should stop at 0 and can only subtract X.
 742       //   Rule 3: Y >s X ---> X.
 743       // It gives us smin(X, Y) to subtract in all cases.
 744       return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
 745   };
 746   const SCEV *M = SE.getMinusSCEV(C, A);
 747   const SCEV *Zero = SE.getZero(M->getType());
 748
 749   // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
 750   auto SCEVCheckNonNegative = [&](const SCEV *X) {
 751     const Loop *L = IndVar->getLoop();
 752     const SCEV *Zero = SE.getZero(X->getType());
 753     const SCEV *One = SE.getOne(X->getType());
 754     // Can we trivially prove that X is a non-negative or negative value?
 755     if (isKnownNonNegativeInLoop(X, L, SE))
 756       return One;
 757     else if (isKnownNegativeInLoop(X, L, SE))
 758       return Zero;
 759     // If not, we will have to figure it out during the execution.
 760     // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
 761     const SCEV *NegOne = SE.getNegativeSCEV(One);
 762     return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
 763   };
 764
 765   // This function returns SCEV equal to 1 if X will not overflow in terms of
 766   // range check type, 0 otherwise.
 767   auto SCEVCheckWillNotOverflow = [&](const SCEV *X) {
 768     // X doesn't overflow if SINT_MAX >= X.
 769     // Then if (SINT_MAX - X) >= 0, X doesn't overflow
 770     const SCEV *SIntMaxExt = SE.getSignExtendExpr(SIntMax, X->getType());
 771     const SCEV *OverflowCheck =
 772         SCEVCheckNonNegative(SE.getMinusSCEV(SIntMaxExt, X));
 773
 774     // X doesn't underflow if X >= SINT_MIN.
 775     // Then if (X - SINT_MIN) >= 0, X doesn't underflow
 776     const SCEV *SIntMinExt = SE.getSignExtendExpr(SIntMin, X->getType());
 777     const SCEV *UnderflowCheck =
 778         SCEVCheckNonNegative(SE.getMinusSCEV(X, SIntMinExt));
 779
 780     return SE.getMulExpr(OverflowCheck, UnderflowCheck);
 781   };
 782
 783   // FIXME: Current implementation of ClampedSubtract implicitly assumes that
 784   // X is non-negative (in sense of a signed value). We need to re-implement
 785   // this function in a way that it will correctly handle negative X as well.
 786   // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
 787   // end up with a negative X and produce wrong results. So currently we ensure
 788   // that if getEnd() is negative then both ends of the safe range are zero.
 789   // Note that this may pessimize elimination of unsigned range checks against
 790   // negative values.
 791   const SCEV *REnd = getEnd();
 792   const SCEV *EndWillNotOverflow = SE.getOne(RCType);
 793
 794   auto PrintRangeCheck = [&](raw_ostream &OS) {
 795     auto L = IndVar->getLoop();
 796     OS << "irce: in function ";
 797     OS << L->getHeader()->getParent()->getName();
 798     OS << ", in ";
 799     L->print(OS);
 800     OS << "there is range check with scaled boundary:\n";
 801     print(OS);
 802   };
 803
 804   if (EndType->getBitWidth() > RCType->getBitWidth()) {
 805     assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
 806     if (PrintScaledBoundaryRangeChecks)
 807       PrintRangeCheck(errs());
 808     // End is computed with extended type but will be truncated to a narrow one
 809     // type of range check. Therefore we need a check that the result will not
 810     // overflow in terms of narrow type.
 811     EndWillNotOverflow =
 812         SE.getTruncateExpr(SCEVCheckWillNotOverflow(REnd), RCType);
 813     REnd = SE.getTruncateExpr(REnd, RCType);
 814   }
 815
 816   const SCEV *RuntimeChecks =
 817       SE.getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
 818   const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
 819   const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), RuntimeChecks);
 820
 821   return InductiveRangeCheck::Range(Begin, End);
 822 }
 823
 824 static std::optional<InductiveRangeCheck::Range>
 825 IntersectSignedRange(ScalarEvolution &SE,
 826                      const std::optional<InductiveRangeCheck::Range> &R1,
 827                      const InductiveRangeCheck::Range &R2) {
 828   if (R2.isEmpty(SE, /* IsSigned */ true))
 829     return std::nullopt;
 830   if (!R1)
 831     return R2;
 832   auto &R1Value = *R1;
 833   // We never return empty ranges from this function, and R1 is supposed to be
 834   // a result of intersection. Thus, R1 is never empty.
 835   assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
 836          "We should never have empty R1!");
 837
 838   // TODO: we could widen the smaller range and have this work; but for now we
 839   // bail out to keep things simple.
 840   if (R1Value.getType() != R2.getType())
 841     return std::nullopt;
 842
 843   const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
 844   const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
 845
 846   // If the resulting range is empty, just return std::nullopt.
 847   auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
 848   if (Ret.isEmpty(SE, /* IsSigned */ true))
 849     return std::nullopt;
 850   return Ret;
 851 }
 852
 853 static std::optional<InductiveRangeCheck::Range>
 854 IntersectUnsignedRange(ScalarEvolution &SE,
 855                        const std::optional<InductiveRangeCheck::Range> &R1,
 856                        const InductiveRangeCheck::Range &R2) {
 857   if (R2.isEmpty(SE, /* IsSigned */ false))
 858     return std::nullopt;
 859   if (!R1)
 860     return R2;
 861   auto &R1Value = *R1;
 862   // We never return empty ranges from this function, and R1 is supposed to be
 863   // a result of intersection. Thus, R1 is never empty.
 864   assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
 865          "We should never have empty R1!");
 866
 867   // TODO: we could widen the smaller range and have this work; but for now we
 868   // bail out to keep things simple.
 869   if (R1Value.getType() != R2.getType())
 870     return std::nullopt;
 871
 872   const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
 873   const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
 874
 875   // If the resulting range is empty, just return std::nullopt.
 876   auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
 877   if (Ret.isEmpty(SE, /* IsSigned */ false))
 878     return std::nullopt;
 879   return Ret;
 880 }
 881
 882 PreservedAnalyses IRCEPass::run(Function &F, FunctionAnalysisManager &AM) {
 883   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 884   LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
 885   // There are no loops in the function. Return before computing other expensive
 886   // analyses.
 887   if (LI.empty())
 888     return PreservedAnalyses::all();
 889   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
 890   auto &BPI = AM.getResult<BranchProbabilityAnalysis>(F);
 891
 892   // Get BFI analysis result on demand. Please note that modification of
 893   // CFG invalidates this analysis and we should handle it.
 894   auto getBFI = [&F, &AM ]()->BlockFrequencyInfo & {
 895     return AM.getResult<BlockFrequencyAnalysis>(F);
 896   };
 897   InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
 898
 899   bool Changed = false;
 900   {
 901     bool CFGChanged = false;
 902     for (const auto &L : LI) {
 903       CFGChanged |= simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr,
 904                                  /*PreserveLCSSA=*/false);
 905       Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
 906     }
 907     Changed |= CFGChanged;
 908
 909     if (CFGChanged && !SkipProfitabilityChecks) {
 910       PreservedAnalyses PA = PreservedAnalyses::all();
 911       PA.abandon<BlockFrequencyAnalysis>();
 912       AM.invalidate(F, PA);
 913     }
 914   }
 915
 916   SmallPriorityWorklist<Loop *, 4> Worklist;
 917   appendLoopsToWorklist(LI, Worklist);
 918   auto LPMAddNewLoop = [&Worklist](Loop *NL, bool IsSubloop) {
 919     if (!IsSubloop)
 920       appendLoopsToWorklist(*NL, Worklist);
 921   };
 922
 923   while (!Worklist.empty()) {
 924     Loop *L = Worklist.pop_back_val();
 925     if (IRCE.run(L, LPMAddNewLoop)) {
 926       Changed = true;
 927       if (!SkipProfitabilityChecks) {
 928         PreservedAnalyses PA = PreservedAnalyses::all();
 929         PA.abandon<BlockFrequencyAnalysis>();
 930         AM.invalidate(F, PA);
 931       }
 932     }
 933   }
 934
 935   if (!Changed)
 936     return PreservedAnalyses::all();
 937   return getLoopPassPreservedAnalyses();
 938 }
 939
 940 bool
 941 InductiveRangeCheckElimination::isProfitableToTransform(const Loop &L,
 942                                                         LoopStructure &LS) {
 943   if (SkipProfitabilityChecks)
 944     return true;
 945   if (GetBFI) {
 946     BlockFrequencyInfo &BFI = (*GetBFI)();
 947     uint64_t hFreq = BFI.getBlockFreq(LS.Header).getFrequency();
 948     uint64_t phFreq = BFI.getBlockFreq(L.getLoopPreheader()).getFrequency();
 949     if (phFreq != 0 && hFreq != 0 && (hFreq / phFreq < MinRuntimeIterations)) {
 950       LLVM_DEBUG(dbgs() << "irce: could not prove profitability: "
 951                         << "the estimated number of iterations basing on "
 952                            "frequency info is " << (hFreq / phFreq) << "\n";);
 953       return false;
 954     }
 955     return true;
 956   }
 957
 958   if (!BPI)
 959     return true;
 960   BranchProbability ExitProbability =
 961       BPI->getEdgeProbability(LS.Latch, LS.LatchBrExitIdx);
 962   if (ExitProbability > BranchProbability(1, MinRuntimeIterations)) {
 963     LLVM_DEBUG(dbgs() << "irce: could not prove profitability: "
 964                       << "the exit probability is too big " << ExitProbability
 965                       << "\n";);
 966     return false;
 967   }
 968   return true;
 969 }
 970
 971 bool InductiveRangeCheckElimination::run(
 972     Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
 973   if (L->getBlocks().size() >= LoopSizeCutoff) {
 974     LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n");
 975     return false;
 976   }
 977
 978   BasicBlock *Preheader = L->getLoopPreheader();
 979   if (!Preheader) {
 980     LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
 981     return false;
 982   }
 983
 984   LLVMContext &Context = Preheader->getContext();
 985   SmallVector<InductiveRangeCheck, 16> RangeChecks;
 986   bool Changed = false;
 987
 988   for (auto *BBI : L->getBlocks())
 989     if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
 990       InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
 991                                                         RangeChecks, Changed);
 992
 993   if (RangeChecks.empty())
 994     return Changed;
 995
 996   auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
 997     OS << "irce: looking at loop "; L->print(OS);
 998     OS << "irce: loop has " << RangeChecks.size()
 999        << " inductive range checks: \n";
1000     for (InductiveRangeCheck &IRC : RangeChecks)
1001       IRC.print(OS);
1002   };
1003
1004   LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs()));
1005
1006   if (PrintRangeChecks)
1007     PrintRecognizedRangeChecks(errs());
1008
1009   const char *FailureReason = nullptr;
1010   std::optional<LoopStructure> MaybeLoopStructure =
1011       LoopStructure::parseLoopStructure(SE, *L, AllowUnsignedLatchCondition,
1012                                         FailureReason);
1013   if (!MaybeLoopStructure) {
1014     LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: "
1015                       << FailureReason << "\n";);
1016     return Changed;
1017   }
1018   LoopStructure LS = *MaybeLoopStructure;
1019   if (!isProfitableToTransform(*L, LS))
1020     return Changed;
1021   const SCEVAddRecExpr *IndVar =
1022       cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1023
1024   std::optional<InductiveRangeCheck::Range> SafeIterRange;
1025
1026   SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1027   // Basing on the type of latch predicate, we interpret the IV iteration range
1028   // as signed or unsigned range. We use different min/max functions (signed or
1029   // unsigned) when intersecting this range with safe iteration ranges implied
1030   // by range checks.
1031   auto IntersectRange =
1032       LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
1033
1034   for (InductiveRangeCheck &IRC : RangeChecks) {
1035     auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1036                                                 LS.IsSignedPredicate);
1037     if (Result) {
1038       auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1039       if (MaybeSafeIterRange) {
1040         assert(!MaybeSafeIterRange->isEmpty(SE, LS.IsSignedPredicate) &&
1041                "We should never return empty ranges!");
1042         RangeChecksToEliminate.push_back(IRC);
1043         SafeIterRange = *MaybeSafeIterRange;
1044       }
1045     }
1046   }
1047
1048   if (!SafeIterRange)
1049     return Changed;
1050
1051   std::optional<LoopConstrainer::SubRanges> MaybeSR =
1052       calculateSubRanges(SE, *L, *SafeIterRange, LS);
1053   if (!MaybeSR) {
1054     LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n");
1055     return false;
1056   }
1057
1058   LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
1059                      SafeIterRange->getBegin()->getType(), *MaybeSR);
1060
1061   if (LC.run()) {
1062     Changed = true;
1063
1064     auto PrintConstrainedLoopInfo = [L]() {
1065       dbgs() << "irce: in function ";
1066       dbgs() << L->getHeader()->getParent()->getName() << ": ";
1067       dbgs() << "constrained ";
1068       L->print(dbgs());
1069     };
1070
1071     LLVM_DEBUG(PrintConstrainedLoopInfo());
1072
1073     if (PrintChangedLoops)
1074       PrintConstrainedLoopInfo();
1075
1076     // Optimize away the now-redundant range checks.
1077
1078     for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1079       ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1080                                           ? ConstantInt::getTrue(Context)
1081                                           : ConstantInt::getFalse(Context);
1082       IRC.getCheckUse()->set(FoldedRangeCheck);
1083     }
1084   }
1085
1086   return Changed;
1087 }