[IndVars] Make loop varying predicates loop invariant.

[sanjoy]

Summary

Was D9784: "Remove loop variant range check when induction variable is
strictly increasing"

This change re-implements D9784 with the two differences:

1. It does not use SCEVExpander and does not generate new instructions. Instead, it does a quick local search for existing llvm::Values that it needs when modifying the icmp instruction.
2. It is more general -- it deals with both increasing and decreasing induction variables.

I've added all of the tests included with D9784, and two more.

As an example on what this change does (copied from D9784):

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))
  for (int i = M; i < N; i++)
    a[i] = 0;
}

I went back and forth on whether the top level logic should live in
SimplifyIndvar::eliminateIVComparison or be put into its own
routine. Right now I've put it under eliminateIVComparison because
even though the icmp is not *eliminated*, it no longer is an IV
comparison. I'm open to putting it in its own helper routine if you
think that is better.

[reames]

include/llvm/Analysis/ScalarEvolution.h

586 ↗

(On Diff #29948)

This part of the comment makes no sense to me. Typos?

593 ↗

(On Diff #29948)

You might want to note the ordering of the arguments to the comparison. You implicitly do it in the naming, but not in the comment.

919 ↗

(On Diff #29948)

I really can't tell from this comment what this function actually does.

lib/Analysis/ScalarEvolution.cpp

6619 ↗

(On Diff #29948)

If I'm reading this right, a strictly decreasing predicate can be converted to a strictly increasing one by just swapping the direction of the predicate right? That seems like it might form the basis for either s simplification in this code, it's caller, or possibly a useful assert.

6638 ↗

(On Diff #29948)

I don't think NonNegative is enough here. Don't you need Positive? i.e. what's would a zero step value mean?

6686 ↗

(On Diff #29948)

Early return preferred.

6704 ↗

(On Diff #29948)

I think I've convinced myself the reasoning here for an increasing predicate (false->true) is valid, but I'm struggling with the reasoning for the decreasing (true->false) case. In particular, the order of operands in the result seems suspicious.

... I convinced myself this is correct, but a better comment about why would help. In particular, you're relying on the fact that inverting a decreasing predicate creates an increasing one which switches at the same point. This is fine, but should be explained.

Also, is this robust against future enhancements to isMonotonicPredicate? I think it is, but how do we ensure that?

One natural case to handle would be an equals comparison. That's not monotonic, so I think we're fine... that would take the form of a weird unswitch (i.e. start..end doesn't include test value). What about the case where an equals comparison is monotonic precisely because it's controlling whether the induction variable is incremented? Does that cause us problems? We'd end with either an infinite loop or our weird "monotonic equal" being the guard on the backedge... I think we'd be fine. The infinite loop case is caught by the isLoopBackedgeGuardByCond, the backedge guard itself is caught by... well nothing?

So yeah, we do need to make sure we define this in such a way that the backedge guard itself can't be considered monotonic. Or at least include that test case to prevent future person from shooting themselves in the foot. :)

6705 ↗

(On Diff #29948)

This utility function is unfamilar to me. Does this imply that if the backedge executes, the condition must be true? Does it say anything about when the backedge is not taken? Might we have problems with two potential early exits and the wrong one being selected? (Given the condition is just made invariant, I think this would be fine...)

lib/Transforms/Utils/SimplifyIndVar.cpp

195 ↗

(On Diff #29948)

This looks correct, but rather restricted. Could we do something slightly more general? This might be a good follow up patch.

204 ↗

(On Diff #29948)

Is getting a SCEV for each incoming value expensive? I don't have a good mental cost model for this.

I might organize this as two loops with a break for clarity.

Or alternatively, put a break in for when both NewLHS and RHS are set.

212 ↗

(On Diff #29948)

Some info about those subtle tradeoffs?

Looking through the code, won't NewRHS either be S or X by definition?

I think we should only need to be finding the start index?

[sanjoy]

Sending in new patch shortly.

include/llvm/Analysis/ScalarEvolution.h

593 ↗

(On Diff #29948)

I have re-written this comment, please take a look.

919 ↗

(On Diff #29948)

Cleaned up the comment, PTAL.

lib/Analysis/ScalarEvolution.cpp

6619 ↗

(On Diff #29948)

I think that's a good idea. I'll split out a Impl version of this function and do the assert you suggested. The assertion won't work with the function as written because the case for UGT isn't symmetric -- I didn't fill in the other cases because an nuw unsigned decreasing variable does not make much sense in practice -- but there is no reason why I cannot add the missing cases.

6638 ↗

(On Diff #29948)

A zero step value means the induction variable is essentially a loop invariant value. We don't really depend on the predicate actually flipping from false to true (for increasing predicates), all we care about is that if the predicate changes then it only changes from false to true.

A zero step value in itself is not very useful, but there may be places where SCEV can prove X >= 0 but not prove X > 0, so it is helpful to be maximally general.

6705 ↗

(On Diff #29948)

Does this imply that if the backedge executes, the condition must be true?

Yes.

Does it say anything about when the backedge is not taken?

No.

Might we have problems with two potential early exits and the wrong one being selected?

I don't see how -- the condition should evaluate to whatever it was evaluating to before.

lib/Transforms/Utils/SimplifyIndVar.cpp

195 ↗

(On Diff #29948)

Yes. I think there is scope to extend this part to emit some basic arithmetic, but I think there is value in checking this in as is, and then taking stock of what cases we're still missing.

204 ↗

(On Diff #29948)

Is getting a SCEV for each incoming value expensive? I don't have a good mental cost model for this.

IIUC, internally, computing a SCEV for a PHINode or addition on a phinode also computes SCEV for all of its incoming values, so this should be just a hashtable lookup since we've already computed S. Having said that, I should not be calling getSCEV twice for no good reason, so I'll fix that.

Or alternatively, put a break in for when both NewLHS and RHS are set.

Done.

212 ↗

(On Diff #29948)

Some info about those subtle tradeoffs?

While I don't see making loop varying predicates loop invariant being a pessimization, it can be performance neutral in the worst case. If it is performance neutral then emitting extra instructions outside the loop to compute the loop invariant check's operands may be a pessimization overall.

Looking through the code, won't NewRHS either be S or X by definition?

I think we should only need to be finding the start index?

I don't see how I can do that without coupling this bit of code with the implementation of isLoopInvariantPredicate.

[sanjoy]

• address Philip's review
• add more tests

[reames]

LGTM w/comments addressed. I would prefer to have another set of eyes on it (Andy?,
Nick?) before submission though. I'm fairly sure of the algorithm involved, but am not entirely familiar with the code involved.

lib/Analysis/ScalarEvolution.cpp

6634 ↗

(On Diff #30220)

Rather than sharing the work, it might be cleaner to just put this block standalone in it's own scope and reuse the NDEBUG code even in debug. It makes it less likely you'll have a NDEBUG only error.

6677 ↗

(On Diff #30220)

Your reasoning about the zero case should be here in a comment. It makes perfect sense once explained, but isn't obvious from the code.

[atrick]

LGTM. Nice optimization.

lib/Analysis/ScalarEvolution.cpp

6634 ↗

(On Diff #30220)

I think it would be slightly preferable to have:

  bool Result = isMonotonicPredicateImpl(...);
#ifndef NDEBUG
  bool SwappedResult = ... 
  assert(...)
#endif
  return Result;

6677 ↗

(On Diff #30220)

Definitely.

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

namespace llvm {
   class ScalarEvolution;
   class DataLayout;
   class TargetLibraryInfo;
   class LLVMContext;
   class Loop;
   class LoopInfo;
   class Operator;
   class SCEVUnknown;
+  class SCEVAddRecExpr;
   class SCEV;
   template<> struct FoldingSetTrait<SCEV>;
 
   /// SCEV - This class represents an analyzed expression in the program.  These
   /// are opaque objects that the client is not allowed to do much with
   /// directly.
   ///
   class SCEV : public FoldingSetNode {
private:
     /// equivalent to proving no signed (resp. unsigned) wrap in
     /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
     /// (resp. `SCEVZeroExtendExpr`).
     ///
     template<typename ExtendOpTy>
     bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
                                    const Loop *L);
 
+    bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS,
+                                  ICmpInst::Predicate Pred, bool &Increasing);
+
+    /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
+    /// is monotonically increasing or decreasing.  In the former case set
+    /// `Increasing` to true and in the latter case set `Increasing` to false.
+    ///
+    /// A predicate is said to be monotonically increasing if may go from being
+    /// false to being true as the loop iterates, but never the other way
+    /// around.  A predicate is said to be monotonically decreasing if may go
+    /// from being true to being false as the loop iterates, but never the other
+    /// way around.
+    bool isMonotonicPredicate(const SCEVAddRecExpr *LHS,
+                              ICmpInst::Predicate Pred, bool &Increasing);
+
   public:
     static char ID; // Pass identification, replacement for typeid
     ScalarEvolution();
 
     LLVMContext &getContext() const { return F->getContext(); }
 
     /// isSCEVable - Test if values of the given type are analyzable within
     /// the SCEV framework. This primarily includes integer types, and it
public:
     bool isKnownNonZero(const SCEV *S);
 
     /// isKnownPredicate - Test if the given expression is known to satisfy
     /// the condition described by Pred, LHS, and RHS.
     ///
     bool isKnownPredicate(ICmpInst::Predicate Pred,
                           const SCEV *LHS, const SCEV *RHS);
 
+    /// Return true if the result of the predicate LHS `Pred` RHS is loop
+    /// invariant with respect to L.  Set InvariantPred, InvariantLHS and
+    /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
+    /// loop invariant form of LHS `Pred` RHS.
+    bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
+                                  const SCEV *RHS, const Loop *L,
+                                  ICmpInst::Predicate &InvariantPred,
+                                  const SCEV *&InvariantLHS,
+                                  const SCEV *&InvariantRHS);
+
     /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with
     /// predicate Pred. Return true iff any changes were made. If the
     /// operands are provably equal or unequal, LHS and RHS are set to
     /// the same value and Pred is set to either ICMP_EQ or ICMP_NE.
     ///
     bool SimplifyICmpOperands(ICmpInst::Predicate &Pred,
                               const SCEV *&LHS,
                               const SCEV *&RHS,

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
   }
   if (LeftGuarded && RightGuarded)
     return true;
 
   // Otherwise see what can be done with known constant ranges.
   return isKnownPredicateWithRanges(Pred, LHS, RHS);
 }
 
+bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS,
+                                           ICmpInst::Predicate Pred,
+                                           bool &Increasing) {
+  bool Result = isMonotonicPredicateImpl(LHS, Pred, Increasing);
+
+#ifndef NDEBUG
+  // Verify an invariant: inverting the predicate should turn a monotonically
+  // increasing change to a monotonically decreasing one, and vice versa.
+  bool IncreasingSwapped;
+  bool ResultSwapped = isMonotonicPredicateImpl(
+      LHS, ICmpInst::getSwappedPredicate(Pred), IncreasingSwapped);
+
+  assert(Result == ResultSwapped && "should be able to analyze both!");
+  if (ResultSwapped)
+    assert(Increasing == !IncreasingSwapped &&
+           "monotonicity should flip as we flip the predicate");
+#endif
+
+  return Result;
+}
+
+bool ScalarEvolution::isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS,
+                                               ICmpInst::Predicate Pred,
+                                               bool &Increasing) {
+  SCEV::NoWrapFlags FlagsRequired = SCEV::FlagAnyWrap;
+  bool IncreasingOnNonNegativeStep = false;
+
+  switch (Pred) {
+  default:
+    return false; // Conservative answer
+
+  case ICmpInst::ICMP_UGT:
+  case ICmpInst::ICMP_UGE:
+    FlagsRequired = SCEV::FlagNUW;
+    IncreasingOnNonNegativeStep = true;
+    break;
+
+  case ICmpInst::ICMP_ULT:
+  case ICmpInst::ICMP_ULE:
+    FlagsRequired = SCEV::FlagNUW;
+    IncreasingOnNonNegativeStep = false;
+    break;
+
+  case ICmpInst::ICMP_SGT:
+  case ICmpInst::ICMP_SGE:
+    FlagsRequired = SCEV::FlagNSW;
+    IncreasingOnNonNegativeStep = true;
+    break;
+
+  case ICmpInst::ICMP_SLT:
+  case ICmpInst::ICMP_SLE:
+    FlagsRequired = SCEV::FlagNSW;
+    IncreasingOnNonNegativeStep = false;
+    break;
+  }
+
+  if (!LHS->getNoWrapFlags(FlagsRequired))
+    return false;
+
+  // A zero step value for LHS means the induction variable is essentially a
+  // loop invariant value. We don't really depend on the predicate actually
+  // flipping from false to true (for increasing predicates, and the other way
+  // around for decreasing predicates), all we care about is that *if* the
+  // predicate changes then it only changes from false to true.
+  //
+  // A zero step value in itself is not very useful, but there may be places
+  // where SCEV can prove X >= 0 but not prove X > 0, so it is helpful to be
+  // as general as possible.
+
+  if (isKnownNonNegative(LHS->getStepRecurrence(*this))) {
+    Increasing = IncreasingOnNonNegativeStep;
+    return true;
+  }
+
+  if (isKnownNonPositive(LHS->getStepRecurrence(*this))) {
+    Increasing = !IncreasingOnNonNegativeStep;
+    return true;
+  }
+
+  return false;
+}
+
+bool ScalarEvolution::isLoopInvariantPredicate(
+    ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
+    ICmpInst::Predicate &InvariantPred, const SCEV *&InvariantLHS,
+    const SCEV *&InvariantRHS) {
+
+  // If there is a loop-invariant, force it into the RHS, otherwise bail out.
+  if (!isLoopInvariant(RHS, L)) {
+    if (!isLoopInvariant(LHS, L))
+      return false;
+
+    std::swap(LHS, RHS);
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+
+  const SCEVAddRecExpr *ArLHS = dyn_cast<SCEVAddRecExpr>(LHS);
+  if (!ArLHS || ArLHS->getLoop() != L)
+    return false;
+
+  bool Increasing;
+  if (!isMonotonicPredicate(ArLHS, Pred, Increasing))
+    return false;
+
+  // If the predicate "ArLHS `Pred` RHS" monotonically increases from false to
+  // true as the loop iterates, and the backedge is control dependent on
+  // "ArLHS `Pred` RHS" == true then we can reason as follows:
+  //
+  //   * if the predicate was false in the first iteration then the predicate
+  //     is never evaluated again, since the loop exits without taking the
+  //     backedge.
+  //   * if the predicate was true in the first iteration then it will
+  //     continue to be true for all future iterations since it is
+  //     monotonically increasing.
+  //
+  // For both the above possibilities, we can replace the loop varying
+  // predicate with its value on the first iteration of the loop (which is
+  // loop invariant).
+  //
+  // A similar reasoning applies for a monotonically decreasing predicate, by
+  // replacing true with false and false with true in the above two bullets.
+
+  auto P = Increasing ? Pred : ICmpInst::getInversePredicate(Pred);
+
+  if (!isLoopBackedgeGuardedByCond(L, P, LHS, RHS))
+    return false;
+
+  InvariantPred = Pred;
+  InvariantLHS = ArLHS->getStart();
+  InvariantRHS = RHS;
+  return true;
+}
+
 bool
 ScalarEvolution::isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
                                             const SCEV *LHS, const SCEV *RHS) {
   if (HasSameValue(LHS, RHS))
     return ICmpInst::isTrueWhenEqual(Pred);
 
   // This code is split out from isKnownPredicate because it is called from
   // within isLoopEntryGuardedByCond.

llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp

void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
   const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
   const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
 
   // Simplify unnecessary loops away.
   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
   S = SE->getSCEVAtScope(S, ICmpLoop);
   X = SE->getSCEVAtScope(X, ICmpLoop);
 
+  ICmpInst::Predicate InvariantPredicate;
+  const SCEV *InvariantLHS, *InvariantRHS;
+
+  const char *Verb = nullptr;
+
   // If the condition is always true or always false, replace it with
   // a constant value.
-  if (SE->isKnownPredicate(Pred, S, X))
+  if (SE->isKnownPredicate(Pred, S, X)) {
     ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
-  else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X))
+    DeadInsts.emplace_back(ICmp);
+    Verb = "Eliminated";
+  } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
     ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
-  else
+    DeadInsts.emplace_back(ICmp);
+    Verb = "Eliminated";
+  } else if (isa<PHINode>(IVOperand) &&
+             SE->isLoopInvariantPredicate(Pred, S, X, ICmpLoop,
+                                          InvariantPredicate, InvariantLHS,
+                                          InvariantRHS)) {
+
+    // Rewrite the comparision to a loop invariant comparision if it can be done
+    // cheaply, where cheaply means "we don't need to emit any new
+    // instructions".
+
+    Value *NewLHS = nullptr, *NewRHS = nullptr;
+
+    if (S == InvariantLHS || X == InvariantLHS)
+      NewLHS =
+          ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
+
+    if (S == InvariantRHS || X == InvariantRHS)
+      NewRHS =
+          ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
+
+    for (Value *Incoming : cast<PHINode>(IVOperand)->incoming_values()) {
+      if (NewLHS && NewRHS)
+        break;
+
+      const SCEV *IncomingS = SE->getSCEV(Incoming);
+
+      if (!NewLHS && IncomingS == InvariantLHS)
+        NewLHS = Incoming;
+      if (!NewRHS && IncomingS == InvariantRHS)
+        NewRHS = Incoming;
+    }
+
+    if (!NewLHS || !NewRHS)
+      // We could not find an existing value to replace either LHS or RHS.
+      // Generating new instructions has subtler tradeoffs, so avoid doing that
+      // for now.
       return;
 
-  DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
+    Verb = "Simplified";
+    ICmp->setPredicate(InvariantPredicate);
+    ICmp->setOperand(0, NewLHS);
+    ICmp->setOperand(1, NewRHS);
+  } else
+    return;
+
+  DEBUG(dbgs() << "INDVARS: " << Verb << " comparison: " << *ICmp << '\n');
   ++NumElimCmp;
   Changed = true;
-  DeadInsts.emplace_back(ICmp);
 }
 
 /// SimplifyIVUsers helper for eliminating useless
 /// remainder operations operating on an induction variable.
 void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
                                       Value *IVOperand,
                                       bool IsSigned) {
   // We're only interested in the case where we know something about

llvm/trunk/test/Transforms/IndVarSimplify/loop-invariant-conditions.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
+}
+
+define void @test4(i64 %start) {
+; CHECK-LABEL: @test4
+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 sgt i64 %start, -1
+  %cmp1 = icmp sgt i64 %indvars.iv, -1
+  br i1 %cmp1, label %loop, label %for.end
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+define void @test5(i64 %start) {
+; CHECK-LABEL: @test5
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
+  %indvars.iv.next = add nuw 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 ugt i64 %start, 100
+  %cmp1 = icmp ugt i64 %indvars.iv, 100
+  br i1 %cmp1, label %loop, label %for.end
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+define void @test6(i64 %start) {
+; CHECK-LABEL: @test6
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
+  %indvars.iv.next = add nuw 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 ult i64 %start, 100
+  %cmp1 = icmp ult i64 %indvars.iv, 100
+  br i1 %cmp1, label %for.end, label %loop
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+define void @test7(i64 %start, i64* %inc_ptr) {
+; CHECK-LABEL: @test7
+entry:
+  %inc = load i64, i64* %inc_ptr, !range !0
+  %ok = icmp sge i64 %inc, 0
+  br i1 %ok, label %loop, label %for.end
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, %inc
+; 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
+}
+
+!0 = !{i64 0, i64 100}
+
+; 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 @test1_neg(i64 %start) {
+; CHECK-LABEL: @test1_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 @test2_neg(i64 %start) {
+; CHECK-LABEL: @test2_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 @test3_neg(i64 %start) {
+; CHECK-LABEL: @test3_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
+}
+
+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 %for.end
+
+backedge:
+  ; prevent flattening, needed to make sure we're testing what we intend
+  call void @foo() 
+; CHECK: %cmp1 = icmp sgt i64 %indvars.iv, -1
+  %cmp1 = icmp sgt i64 %indvars.iv, -1
+
+; %cmp1 can be made loop invariant only if the branch below goes to
+; %the header when %cmp1 is true.
+  br i1 %cmp1, label %for.end, label %loop
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+define void @test5_neg(i64 %start, i64 %inc) {
+; CHECK-LABEL: @test5_neg
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, %inc
+; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -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 @test8(i64 %start, i64* %inc_ptr) {
+; CHECK-LABEL: @test8
+entry:
+  %inc = load i64, i64* %inc_ptr, !range !1
+  %ok = icmp sge i64 %inc, 0
+  br i1 %ok, label %loop, label %for.end
+
+loop:
+  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, %inc
+; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
+  %cmp1 = icmp slt i64 %indvars.iv, -1
+  br i1 %cmp1, label %for.end, label %loop
+
+for.end:                                          ; preds = %if.end, %entry
+  ret void
+}
+
+!1 = !{i64 -1, i64 100}
+
+
+declare void @foo()