[WIP] Demo how SCEV is more powerful than value tracking

[mkazantsev]

Summary

We should consider improving value tracking.

llvm/lib/Transforms/Scalar/LICM.cpp

 // compile time.
 cl::opt<unsigned> llvm::SetLicmMssaNoAccForPromotionCap(
     "licm-mssa-max-acc-promotion", cl::init(250), cl::Hidden,
     cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
              "effect. When MSSA in LICM is enabled, then this is the maximum "
              "number of accesses allowed to be present in a loop in order to "
              "enable memory promotion."));
 
+static cl::opt<bool> ProveViaSCEV(
+    "licm-use-scalar-evolution", cl::Hidden, cl::init(false),
+    cl::desc("Allows LICM to use Scalar Evolution analyzis for inferring facts."));
+
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 static bool isNotUsedOrFoldableInLoop(const Instruction &I, const Loop *CurLoop,
                                       const LoopSafetyInfo *SafetyInfo,
                                       TargetTransformInfo *TTI,
                                       bool &FoldableInLoop, bool LoopNestMode);
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
                   MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
static bool pointerInvalidatedByLoop(MemorySSA *MSSA, MemoryUse *MU,
                                      SinkAndHoistLICMFlags &Flags,
                                      bool InvariantGroup);
 static bool pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA,
                                       MemoryUse &MU);
 /// Aggregates various functions for hoisting computations out of loop.
 static bool hoistArithmetics(Instruction &I, Loop &L,
                              ICFLoopSafetyInfo &SafetyInfo,
                              MemorySSAUpdater &MSSAU, AssumptionCache *AC,
-                             DominatorTree *DT);
+                             DominatorTree *DT, ScalarEvolution *SE);
 static Instruction *cloneInstructionInExitBlock(
     Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
     const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU);
 
 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
                              MemorySSAUpdater &MSSAU);
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
for (Instruction &I : llvm::make_early_inc_range(*BB)) {
           assert(DT->dominates(PN, BB) && "Conditional PHIs not expected");
           Changed = true;
           continue;
         }
       }
 
       // Try to reassociate instructions so that part of computations can be
       // done out of loop.
-      if (hoistArithmetics(I, *CurLoop, *SafetyInfo, MSSAU, AC, DT)) {
+      if (hoistArithmetics(I, *CurLoop, *SafetyInfo, MSSAU, AC, DT, ProveViaSCEV ? SE : nullptr)) {
         Changed = true;
         continue;
       }
 
       // Remember possibly hoistable branches so we can actually hoist them
       // later if needed.
       if (BranchInst *BI = dyn_cast<BranchInst>(&I))
         CFH.registerPossiblyHoistableBranch(BI);
static bool hoistGEP(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
   return true;
 }
 
 /// Try to turn things like "LV + C1 < C2" into "LV < C2 - C1". Here
 /// C1 and C2 are loop invariants and LV is a loop-variant.
 static bool hoistAdd(ICmpInst::Predicate Pred, Value *VariantLHS,
                      Value *InvariantRHS, ICmpInst &ICmp, Loop &L,
                      ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU,
-                     AssumptionCache *AC, DominatorTree *DT) {
+                     AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE) {
   assert(ICmpInst::isSigned(Pred) && "Not supported yet!");
   assert(!L.isLoopInvariant(VariantLHS) && "Precondition.");
   assert(L.isLoopInvariant(InvariantRHS) && "Precondition.");
 
   // Try to represent VariantLHS as sum of invariant and variant operands.
   using namespace PatternMatch;
   Value *VariantOp, *InvariantOp;
   if (!match(VariantLHS, m_NSWAdd(m_Value(VariantOp), m_Value(InvariantOp))))
     return false;
 
   // LHS itself is a loop-variant, try to represent it in the form:
   // "VariantOp + InvariantOp". If it is possible, then we can reassociate.
   if (L.isLoopInvariant(VariantOp))
     std::swap(VariantOp, InvariantOp);
   if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
     return false;
 
   // In order to turn "LV + C1 < C2" into "LV < C2 - C1", we need to be able to
   // freely move values from left side of inequality to right side (just as in
   // normal linear arithmetics). Overflows make things much more complicated, so
   // we want to avoid this.
   auto &DL = L.getHeader()->getModule()->getDataLayout();
-  bool ProvedNoOverflowAfterReassociate =
-      computeOverflowForSignedSub(InvariantRHS, InvariantOp, DL, AC, &ICmp,
-                                  DT) == llvm::OverflowResult::NeverOverflows;
-  if (!ProvedNoOverflowAfterReassociate)
+  auto ProvedNoOverflowAfterReassociate = [&]() {
+    if (computeOverflowForSignedSub(InvariantRHS, InvariantOp, DL, AC, &ICmp,
+                                    DT) == llvm::OverflowResult::NeverOverflows)
+      return true;
+    if (SE) {
+      const SCEV *RHSS = SE->getSCEV(InvariantRHS);
+      const SCEV *InvariantOpS = SE->getSCEV(InvariantOp);
+      if (SE->willNotOverflow(Instruction::BinaryOps::Sub, /*Signed*/ true,
+                              RHSS, InvariantOpS, &ICmp))
+        return true;
+    }
+
+    return false;
+  };
+  if (!ProvedNoOverflowAfterReassociate())
     return false;
   auto *Preheader = L.getLoopPreheader();
   assert(Preheader && "Loop is not in simplify form?");
   IRBuilder<> Builder(Preheader->getTerminator());
   Value *NewCmpOp = Builder.CreateSub(InvariantRHS, InvariantOp, "invariant.op",
                                       /*HasNUW*/ false, /*HasNSW*/ true);
   ICmp.setPredicate(Pred);
   ICmp.setOperand(0, VariantOp);
   ICmp.setOperand(1, NewCmpOp);
   eraseInstruction(cast<Instruction>(*VariantLHS), SafetyInfo, MSSAU);
   return true;
 }
 
 /// Try to reassociate and hoist the following two patterns:
 /// LV - C1 < C2 --> LV < C1 + C2,
 /// C1 - LV < C2 --> LV > C1 - C2.
 static bool hoistSub(ICmpInst::Predicate Pred, Value *VariantLHS,
                      Value *InvariantRHS, ICmpInst &ICmp, Loop &L,
                      ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU,
-                     AssumptionCache *AC, DominatorTree *DT) {
+                     AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE) {
   assert(ICmpInst::isSigned(Pred) && "Not supported yet!");
   assert(!L.isLoopInvariant(VariantLHS) && "Precondition.");
   assert(L.isLoopInvariant(InvariantRHS) && "Precondition.");
 
   // Try to represent VariantLHS as sum of invariant and variant operands.
   using namespace PatternMatch;
   Value *VariantOp, *InvariantOp;
   if (!match(VariantLHS, m_NSWSub(m_Value(VariantOp), m_Value(InvariantOp))))
if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
     return false;
 
   // In order to turn "LV - C1 < C2" into "LV < C2 + C1", we need to be able to
   // freely move values from left side of inequality to right side (just as in
   // normal linear arithmetics). Overflows make things much more complicated, so
   // we want to avoid this. Likewise, for "C1 - LV < C2" we need to prove that
   // "C1 - C2" does not overflow.
   auto &DL = L.getHeader()->getModule()->getDataLayout();
-  bool ProvedNoOverflowAfterReassociate =
-      VariantSubtracted
-          ? (computeOverflowForSignedSub(InvariantOp, InvariantRHS, DL, AC,
-                                         &ICmp, DT) ==
-             llvm::OverflowResult::NeverOverflows)
-          : (computeOverflowForSignedAdd(InvariantOp, InvariantRHS, DL, AC,
-                                         &ICmp, DT) ==
-             llvm::OverflowResult::NeverOverflows);
-  if (!ProvedNoOverflowAfterReassociate)
+  auto ProvedNoOverflowAfterReassociate = [&]() {
+    if (VariantSubtracted) {
+      if (computeOverflowForSignedSub(InvariantOp, InvariantRHS, DL, AC, &ICmp,
+                                      DT) ==
+          llvm::OverflowResult::NeverOverflows)
+        return true;
+    } else {
+      if (computeOverflowForSignedAdd(InvariantOp, InvariantRHS, DL, AC, &ICmp,
+                                      DT) ==
+        return true;
+    }
+
+    if (SE) {
+      const SCEV *RHSS = SE->getSCEV(InvariantRHS);
+      const SCEV *InvariantOpS = SE->getSCEV(InvariantOp);
+      if (VariantSubtracted) {
+        if (SE->willNotOverflow(Instruction::BinaryOps::Sub, /*Signed*/ true,
+                                InvariantOpS, RHSS, &ICmp))
+          return true;
+      } else {
+        if (SE->willNotOverflow(Instruction::BinaryOps::Add, /*Signed*/ true,
+                                InvariantOpS, RHSS, &ICmp))
+          return true;
+      }
+    }
+
+    return false;
+  };
+  if (!ProvedNoOverflowAfterReassociate())
     return false;
   auto *Preheader = L.getLoopPreheader();
   assert(Preheader && "Loop is not in simplify form?");
   IRBuilder<> Builder(Preheader->getTerminator());
   Value *NewCmpOp =
       VariantSubtracted
           ? Builder.CreateSub(InvariantOp, InvariantRHS, "invariant.op",
                               /*HasNUW*/ false, /*HasNSW*/ true)
           : Builder.CreateAdd(InvariantOp, InvariantRHS, "invariant.op",
                               /*HasNUW*/ false, /*HasNSW*/ true);
   ICmp.setPredicate(Pred);
   ICmp.setOperand(0, VariantOp);
   ICmp.setOperand(1, NewCmpOp);
   eraseInstruction(cast<Instruction>(*VariantLHS), SafetyInfo, MSSAU);
   return true;
 }
 
 /// Reassociate and hoist add/sub expressions.
 static bool hoistAddSub(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
                         MemorySSAUpdater &MSSAU, AssumptionCache *AC,
-                        DominatorTree *DT) {
+                        DominatorTree *DT, ScalarEvolution *SE) {
   using namespace PatternMatch;
   ICmpInst::Predicate Pred;
   Value *LHS, *RHS;
   if (!match(&I, m_ICmp(Pred, m_Value(LHS), m_Value(RHS))))
     return false;
 
   // TODO: Support unsigned predicates?
   if (!ICmpInst::isSigned(Pred))
     return false;
 
   // Put variant operand to LHS position.
   if (L.isLoopInvariant(LHS)) {
     std::swap(LHS, RHS);
     Pred = ICmpInst::getSwappedPredicate(Pred);
   }
   // We want to delete the initial operation after reassociation, so only do it
   // if it has no other uses.
   if (L.isLoopInvariant(LHS) || !L.isLoopInvariant(RHS) || !LHS->hasOneUse())
     return false;
 
   // TODO: We could go with smarter context, taking common dominator of all I's
   // users instead of I itself.
-  if (hoistAdd(Pred, LHS, RHS, cast<ICmpInst>(I), L, SafetyInfo, MSSAU, AC, DT))
+  if (hoistAdd(Pred, LHS, RHS, cast<ICmpInst>(I), L, SafetyInfo, MSSAU, AC, DT, SE))
     return true;
 
-  if (hoistSub(Pred, LHS, RHS, cast<ICmpInst>(I), L, SafetyInfo, MSSAU, AC, DT))
+  if (hoistSub(Pred, LHS, RHS, cast<ICmpInst>(I), L, SafetyInfo, MSSAU, AC, DT, SE))
     return true;
 
   return false;
 }
 
 static bool hoistArithmetics(Instruction &I, Loop &L,
                              ICFLoopSafetyInfo &SafetyInfo,
                              MemorySSAUpdater &MSSAU, AssumptionCache *AC,
-                             DominatorTree *DT) {
+                             DominatorTree *DT, ScalarEvolution *SE) {
   // Optimize complex patterns, such as (x < INV1 && x < INV2), turning them
   // into (x < min(INV1, INV2)), and hoisting the invariant part of this
   // expression out of the loop.
   if (hoistMinMax(I, L, SafetyInfo, MSSAU)) {
     ++NumHoisted;
     ++NumMinMaxHoisted;
     return true;
   }
 
   // Try to hoist GEPs by reassociation.
   if (hoistGEP(I, L, SafetyInfo, MSSAU, AC, DT)) {
     ++NumHoisted;
     ++NumGEPsHoisted;
     return true;
   }
 
   // Try to hoist add/sub's by reassociation.
-  if (hoistAddSub(I, L, SafetyInfo, MSSAU, AC, DT)) {
+  if (hoistAddSub(I, L, SafetyInfo, MSSAU, AC, DT, SE)) {
     ++NumHoisted;
     ++NumAddSubHoisted;
     return true;
   }
 
   return false;
 }
 
 /// Little predicate that returns true if the specified basic block is in
 /// a subloop of the current one, not the current one itself.
 ///
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
   return LI->getLoopFor(BB) != CurLoop;
 }

llvm/test/Transforms/LICM/hoist-add-sub.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -S -passes=licm -verify-memoryssa < %s | FileCheck %s
+; RUN: opt -S -passes=licm -verify-memoryssa -licm-use-scalar-evolution < %s | FileCheck %s  --check-prefixes=USE_SCEV
 
 ; x - iv < 4 ==> iv > x - 4
 define i32 @test_01(ptr %p, ptr %x_p, ptr %length_p) {
 ; CHECK-LABEL: define i32 @test_01
 ; CHECK-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4, !range [[RNG0]]

 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ;
+; USE_SCEV-LABEL: define i32 @test_01
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4, !range [[RNG0:![0-9]+]]
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4, !range [[RNG0]]
+; USE_SCEV-NEXT:    [[INVARIANT_OP:%.*]] = sub nsw i32 [[X]], 4
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp sgt i32 [[IV]], [[INVARIANT_OP]]
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+;
 entry:
   %x = load i32, ptr %x_p, !range !0
   %length = load i32, ptr %length_p, !range !0
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %arith = sub nsw i32 %x, %iv

 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failed:
 ; CHECK-NEXT:    ret i32 -2
 ;
+; USE_SCEV-LABEL: define i32 @test_01a
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4
+; USE_SCEV-NEXT:    [[PRECOND_1:%.*]] = icmp sge i32 [[X]], 0
+; USE_SCEV-NEXT:    [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0
+; USE_SCEV-NEXT:    [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]]
+; USE_SCEV-NEXT:    br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]]
+; USE_SCEV:       loop.preheader:
+; USE_SCEV-NEXT:    [[INVARIANT_OP:%.*]] = sub nsw i32 [[X]], 4
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp sgt i32 [[IV]], [[INVARIANT_OP]]
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+; USE_SCEV:       failed:
+; USE_SCEV-NEXT:    ret i32 -2
+;
 entry:
   %x = load i32, ptr %x_p
   %length = load i32, ptr %length_p
   %precond_1 = icmp sge i32 %x, 0
   %precond_2 = icmp sge i32 %length, 0
   %precond = and i1 %precond_1, %precond_2
   br i1 %precond, label %loop, label %failed
 

 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ;
+; USE_SCEV-LABEL: define i32 @test_01_neg
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4, !range [[RNG0]]
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; USE_SCEV-NEXT:    [[ARITH:%.*]] = sub nsw i32 [[X]], [[IV]]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp slt i32 [[ARITH]], 4
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+;
 entry:
   %x = load i32, ptr %x_p
   %length = load i32, ptr %length_p, !range !0
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %arith = sub nsw i32 %x, %iv

 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ;
+; USE_SCEV-LABEL: define i32 @test_02
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4, !range [[RNG0]]
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4, !range [[RNG0]]
+; USE_SCEV-NEXT:    [[INVARIANT_OP:%.*]] = sub nsw i32 4, [[X]]
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_OP]]
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+;
 entry:
   %x = load i32, ptr %x_p, !range !0
   %length = load i32, ptr %length_p, !range !0
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %arith = add nsw i32 %x, %iv

 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failed:
 ; CHECK-NEXT:    ret i32 -2
 ;
+; USE_SCEV-LABEL: define i32 @test_02a
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4
+; USE_SCEV-NEXT:    [[PRECOND_1:%.*]] = icmp sge i32 [[X]], 0
+; USE_SCEV-NEXT:    [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0
+; USE_SCEV-NEXT:    [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]]
+; USE_SCEV-NEXT:    br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]]
+; USE_SCEV:       loop.preheader:
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; USE_SCEV-NEXT:    [[ARITH:%.*]] = add nsw i32 [[X]], [[IV]]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp slt i32 [[ARITH]], 4
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+; USE_SCEV:       failed:
+; USE_SCEV-NEXT:    ret i32 -2
+;
 entry:
   %x = load i32, ptr %x_p
   %length = load i32, ptr %length_p
   %precond_1 = icmp sge i32 %x, 0
   %precond_2 = icmp sge i32 %length, 0
   %precond = and i1 %precond_1, %precond_2
   br i1 %precond, label %loop, label %failed
 

 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ;
+; USE_SCEV-LABEL: define i32 @test_03
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4, !range [[RNG1:![0-9]+]]
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4, !range [[RNG0]]
+; USE_SCEV-NEXT:    [[INVARIANT_OP:%.*]] = add nsw i32 [[X]], 4
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_OP]]
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+;
 entry:
   %x = load i32, ptr %x_p, !range !1
   %length = load i32, ptr %length_p, !range !0
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %arith = sub nsw i32 %iv, %x

 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failed:
 ; CHECK-NEXT:    ret i32 -2
 ;
+; USE_SCEV-LABEL: define i32 @test_03a
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4
+; USE_SCEV-NEXT:    [[PRECOND_1:%.*]] = icmp ult i32 [[X]], 2147483640
+; USE_SCEV-NEXT:    [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0
+; USE_SCEV-NEXT:    [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]]
+; USE_SCEV-NEXT:    br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]]
+; USE_SCEV:       loop.preheader:
+; USE_SCEV-NEXT:    [[INVARIANT_OP:%.*]] = add nsw i32 [[X]], 4
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_OP]]
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+; USE_SCEV:       failed:
+; USE_SCEV-NEXT:    ret i32 -2
+;
 entry:
   %x = load i32, ptr %x_p
   %length = load i32, ptr %length_p
   %precond_1 = icmp ult i32 %x, 2147483640
   %precond_2 = icmp sge i32 %length, 0
   %precond = and i1 %precond_1, %precond_2
   br i1 %precond, label %loop, label %failed
 

 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ;
+; USE_SCEV-LABEL: define i32 @test_04
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4, !range [[RNG0]]
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4, !range [[RNG0]]
+; USE_SCEV-NEXT:    [[INVARIANT_OP:%.*]] = sub nsw i32 4, [[X]]
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_OP]]
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+;
 entry:
   %x = load i32, ptr %x_p, !range !0
   %length = load i32, ptr %length_p, !range !0
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %arith = add nsw i32 %iv, %x

 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ; CHECK:       out_of_bounds:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failed:
 ; CHECK-NEXT:    ret i32 -2
 ;
+; USE_SCEV-LABEL: define i32 @test_04a
+; USE_SCEV-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
+; USE_SCEV-NEXT:  entry:
+; USE_SCEV-NEXT:    [[X:%.*]] = load i32, ptr [[X_P]], align 4
+; USE_SCEV-NEXT:    [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4
+; USE_SCEV-NEXT:    [[PRECOND_1:%.*]] = icmp sge i32 [[X]], 0
+; USE_SCEV-NEXT:    [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0
+; USE_SCEV-NEXT:    [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]]
+; USE_SCEV-NEXT:    br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]]
+; USE_SCEV:       loop.preheader:
+; USE_SCEV-NEXT:    br label [[LOOP:%.*]]
+; USE_SCEV:       loop:
+; USE_SCEV-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; USE_SCEV-NEXT:    [[ARITH:%.*]] = add nsw i32 [[IV]], [[X]]
+; USE_SCEV-NEXT:    [[X_CHECK:%.*]] = icmp slt i32 [[ARITH]], 4
+; USE_SCEV-NEXT:    br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
+; USE_SCEV:       backedge:
+; USE_SCEV-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
+; USE_SCEV-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
+; USE_SCEV-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
+; USE_SCEV-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
+; USE_SCEV-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; USE_SCEV:       exit:
+; USE_SCEV-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
+; USE_SCEV-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; USE_SCEV:       out_of_bounds:
+; USE_SCEV-NEXT:    ret i32 -1
+; USE_SCEV:       failed:
+; USE_SCEV-NEXT:    ret i32 -2
+;
 entry:
   %x = load i32, ptr %x_p
   %length = load i32, ptr %length_p
   %precond_1 = icmp sge i32 %x, 0
   %precond_2 = icmp sge i32 %length, 0
   %precond = and i1 %precond_1, %precond_2
   br i1 %precond, label %loop, label %failed