Remove loop variant range check when induction variable is strictly increasing

[reames]

Summary

Given a range check on an induction variable, we can convert that range check to a loop invariant check against the starting value of the induction variable if the check would fail on the first iteration or not at all. This creates a check which is easily unswitched and thus effectively removes the range check from within the loop entirely.

Given C code:
for(int i = M; i < N; i++) // i is known not to overflow

if (i < 0) break;
a[i] = 0;

}
This transformation produces:
for(int i = M; i < N; i++)

if (M < 0) break;
a[i] = 0;

}
Which can be unswitched into:
if (M < 0) break;
for(int i = M; i < N; i++)

a[i] = 0;

}

I'm not entirely sure this is done in the best place. I couldn't really find a more natural fit for it, but the bit of code walking the use of each candidate induction variable didn't really seem elegant. Suggestions on a better way to structure this are very welcome.

[sanjoy]

I think this is okay to commit, but I'll wait for Andy to take a look.

lib/Transforms/Utils/SimplifyIndVar.cpp

189

Might want to just assert(BI->isConditional()) here, since it uses an icmp.

194

Do you need to check / assert that BI is itself within the loop? I think you can just assert it if DominatesBackedges(BI, L, DT) since BI uses ICmp which uses an induction variable.

[atrick]

This is great.

I will say that it's not very nice to call SCEVExpander within the SimplifyIndvar utility on an arbitrary SCEV value. We can't control what SCEVExpander will do outside the loop. I think the SimplifyIndvars utility should be limited to folding instructions within the loop, and possibly cloning an IV increment, but not inserting code outside the loop. I can't think of any value in doing this inside SimplifyIndvar--it won't expose other simplification. I do agree that this optimization belongs in the indvars pass, but it could probably be a separate sub-pass over the loop's terminators.

As always, I'm nervous about using SCExpander in general. I'm not sure if we should have any checks for whether the start value can be safely or profitably materialized (see the terrible isSafeToExpand hack). It may be ok since we similary expand AddRecs and start values in WidenIV and LoopVectorize, but I can't say for sure. Just as an contrasting example implementation, if you wanted to be very conservative, you could find an existing loop phi whose initial value is your desired AddRec start with a constant offset. Then you can ask SCEVExpander to materialize that existing value wrapped in SCEVUnknown plus the offset (always safe).

At any rate, when using SCEVExpander it should be explicit and obvious at the top-level of the pass, not buried in a utility that can be called anywhere. That way it's easier to see that almost arbitrary IR rewriting may happen at that point (hopefully it's at least limited to adding new instructions, but without bounding the expression it can do some surprising things).

[sanjoy]

This has been moved to D11278

[reames]

Sanjoy has implemented a better version of this based on Andy's review comments over in http://reviews.llvm.org/D11278

lib/Transforms/Utils/SimplifyIndVar.cpp

 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/IVUsers.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "indvars"
 
 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
 STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
 STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
 
 namespace {
   /// This is a utility for simplifying induction variables
   /// based on ScalarEvolution. It is the primary instrument of the
   /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
   /// other loop passes that preserve SCEV.
   class SimplifyIndvar {
     Loop             *L;
     LoopInfo         *LI;
     ScalarEvolution  *SE;
+    const DominatorTree    *DT = nullptr; // may be null!
 
     SmallVectorImpl<WeakVH> &DeadInsts;
 
     bool Changed;
 
   public:
     SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LoopInfo *LI,
+                   const DominatorTree* DT,
                    SmallVectorImpl<WeakVH> &Dead, IVUsers *IVU = nullptr)
-        : L(Loop), LI(LI), SE(SE), DeadInsts(Dead), Changed(false) {
+      : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
       assert(LI && "IV simplification requires LoopInfo");
     }
 
     bool hasChanged() const { return Changed; }
 
     /// Iteratively perform simplification on a worklist of users of the
     /// specified induction variable. This is the top-level driver that applies
     /// all simplicitions to users of an IV.
Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
 
   ++NumElimOperand;
   Changed = true;
   if (IVOperand->use_empty())
     DeadInsts.push_back(IVOperand);
   return IVSrc;
 }
 
+static bool IsStrictlyIncreasing(ScalarEvolution *SE,
+                                 const SCEVAddRecExpr *AddRecS) {
+  if (SCEV::FlagNSW & AddRecS->getNoWrapFlags()) {
+    const SCEV *Step = AddRecS->getStepRecurrence(*SE);
+    if (SE->isKnownPositive(Step))
+      return true;
+  }
+  return false;
+}
+
+static bool DominatesBackedges(Instruction *I, Loop *L,
+                               const DominatorTree &DT) {
+  
+  SmallVector<BasicBlock*, 8> Latches;
+  L->getLoopLatches(Latches);
+
+  // Verify that this instuction must execute if any backedge does
+  for (BasicBlock *Latch : Latches)
+    if (!DT.dominates(I->getParent(), Latch)) {
+      return false;
+    }
+
+  return true;
+}
+
+/// Returns true if the given comparison is used by a branch which is known to
+/// exit the loop if the value is true, and that branch is known to execute on
+/// the first iteration if the loop executes at all.
+static bool ControlsExitOnFirstIteration(ICmpInst *ICmp, Loop *L,
+                                         const DominatorTree &DT) {
+  // Avoid walking uses if we can cheaply tell ICmp's uses can't dominate all
+  // backedges. 
+  if (!DominatesBackedges(ICmp, L, DT))
+    return false;
+  for (User *U : ICmp->users()) {
+    auto *BI = dyn_cast<BranchInst>(U);
+    if (!BI || BI->isUnconditional())
+      continue;
+    if (L->contains(BI->getSuccessor(0)))
+      continue;
+    if (DominatesBackedges(BI, L, DT))
+      return true;
+  }
+  return false;
+}
+
+
 /// SimplifyIVUsers helper for eliminating useless
 /// comparisons against an induction variable.
 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
   unsigned IVOperIdx = 0;
   ICmpInst::Predicate Pred = ICmp->getPredicate();
   if (IVOperand != ICmp->getOperand(0)) {
     // Swapped
     assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
   X = SE->getSCEVAtScope(X, ICmpLoop);
 
   // If the condition is always true or always false, replace it with
   // a constant value.
   if (SE->isKnownPredicate(Pred, S, X))
     ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
   else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X))
     ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
-  else
+  else if (auto *AddRecS = dyn_cast<SCEVAddRecExpr>(S)) {
+    // If we have a conditional loop exit which is controlled by a SLT or SLE
+    // comparison on a strictly increasing induction variable, we know that the
+    // exit must be taken on the first iteration it executes, or not at all.
+    // This transformation is currently limited to when we can prove that the
+    // conditional exit executes on the first iteration of the loop so that we
+    // can convert the guard to a loop invariant one on the entry value of
+    // induction variable.  This results in a guard which is easily unswitched
+    // by LoopUnswitch.  The generalized case requiring loop iteration space
+    // splitting is handled by IRCE.
+    // TODO: handle ULT, ULE comparisons
+    // TODO: extend this to strictly decreasing loops
+    if ((Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) &&
+        IsStrictlyIncreasing(SE, AddRecS) &&
+        DT && ControlsExitOnFirstIteration(ICmp, L, *DT)) {
+      const SCEV *Start = AddRecS->getStart();        
+      assert(SE->isLoopInvariant(Start, L));
+      const DataLayout &DL = ICmp->getModule()->getDataLayout();
+      SCEVExpander Expander(*SE, DL, "indvarsi");
+      Value *V = Expander.expandCodeFor(Start, IVOperand->getType(),
+                                        L->getLoopPreheader()->getTerminator());
+      DEBUG(dbgs() << "INDVARS: Converting loop variant check " << *ICmp
+            << " to loop invariant\n");
+      ICmp->replaceUsesOfWith(IVOperand, V);
+      ++NumElimCmp;
+      Changed = true;
+    }
+    // Don't fall through into the code to eliminate the comparison entirely,
+    // we haven't met it's preconditions.
+    return;
+  } else
     return;
-
   DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
   ++NumElimCmp;
   Changed = true;
   DeadInsts.push_back(ICmp);
 }
 
 /// SimplifyIVUsers helper for eliminating useless
 /// remainder operations operating on an induction variable.
while (!SimpleIVUsers.empty()) {
     std::pair<Instruction*, Instruction*> UseOper =
       SimpleIVUsers.pop_back_val();
     Instruction *UseInst = UseOper.first;
 
     // Bypass back edges to avoid extra work.
     if (UseInst == CurrIV) continue;
 
     if (V && V->shouldSplitOverflowInstrinsics()) {
-      UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree());
+      UseInst = splitOverflowIntrinsic(UseInst, DT);
       if (!UseInst)
         continue;
     }
 
     Instruction *IVOperand = UseOper.second;
     for (unsigned N = 0; IVOperand; ++N) {
       assert(N <= Simplified.size() && "runaway iteration");
 

 void IVVisitor::anchor() { }
 
 /// Simplify instructions that use this induction variable
 /// by using ScalarEvolution to analyze the IV's recurrence.
 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM,
                        SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
 {
   LoopInfo *LI = &LPM->getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LI, Dead);
+  const DominatorTree *DT = V ? V->getDomTree() : nullptr;
+  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LI, DT, Dead);
   SIV.simplifyUsers(CurrIV, V);
   return SIV.hasChanged();
 }
 
 /// Simplify users of induction variables within this
 /// loop. This does not actually change or add IVs.
 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM,
                      SmallVectorImpl<WeakVH> &Dead) {
   bool Changed = false;
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
     Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, LPM, Dead);
   }
   return Changed;
 }
 
 } // namespace llvm

test/Transforms/IndVarSimplify/strictly-increasing.ll

+; RUN: opt -S -indvars %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test1(i64 %start) {
+; CHECK-LABEL: @test1
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, 1
+; CHECK: %cmp1 = icmp slt i64 %start, -1
+  %cmp1 = icmp slt i64 %indvars.iv, -1
+  br i1 %cmp1, label %for.end, label %loop
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+define void @test2(i64 %start) {
+; CHECK-LABEL: @test2
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, 1
+; CHECK: %cmp1 = icmp sle i64 %start, -1
+  %cmp1 = icmp sle i64 %indvars.iv, -1
+  br i1 %cmp1, label %for.end, label %loop
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+; As long as the test dominates the backedge, we're good
+define void @test3(i64 %start) {
+; CHECK-LABEL: @test3
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, 1
+  %cmp = icmp eq i64 %indvars.iv.next, 25
+  br i1 %cmp, label %backedge, label %for.end
+
+backedge:
+  ; prevent flattening, needed to make sure we're testing what we intend
+  call void @foo() 
+; CHECK: %cmp1 = icmp slt i64 %start, -1
+  %cmp1 = icmp slt i64 %indvars.iv, -1
+  br i1 %cmp1, label %for.end, label %loop
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+; Negative test - we can't show that the internal branch executes, so we can't
+; fold the test to a loop invariant one.
+define void @test4_neg(i64 %start) {
+; CHECK-LABEL: @test4_neg
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, 1
+  %cmp = icmp eq i64 %indvars.iv.next, 25
+  br i1 %cmp, label %backedge, label %skip
+skip:
+  ; prevent flattening, needed to make sure we're testing what we intend
+  call void @foo() 
+; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
+  %cmp1 = icmp slt i64 %indvars.iv, -1
+  br i1 %cmp1, label %for.end, label %backedge
+backedge:
+  ; prevent flattening, needed to make sure we're testing what we intend
+  call void @foo() 
+  br label %loop
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+; Slightly subtle version of @test4 where the icmp dominates the backedge,
+; but the exit branch doesn't.  
+define void @test5_neg(i64 %start) {
+; CHECK-LABEL: @test5_neg
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, 1
+  %cmp = icmp eq i64 %indvars.iv.next, 25
+; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
+  %cmp1 = icmp slt i64 %indvars.iv, -1
+  br i1 %cmp, label %backedge, label %skip
+skip:
+  ; prevent flattening, needed to make sure we're testing what we intend
+  call void @foo() 
+  br i1 %cmp1, label %for.end, label %backedge
+backedge:
+  ; prevent flattening, needed to make sure we're testing what we intend
+  call void @foo() 
+  br label %loop
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+; The branch has to exit the loop if the condition is true
+define void @test6_neg(i64 %start) {
+; CHECK-LABEL: @test6_neg
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, 1
+; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
+  %cmp1 = icmp slt i64 %indvars.iv, -1
+  br i1 %cmp1, label %loop, label %for.end
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+
+declare void @foo()