Return "[SCEV] Prove implicaitons via AddRec start"

[mkazantsev]

Summary

If we know that some predicate is true for AddRec and an invariant
(w.r.t. this AddRec's loop), this fact is, in particular, true on the first
iteration. We can try to prove the facts we need using the start value.

The motivating example is proving things like

isImpliedCondOperands(>=, X, 0, {X,+,-1}, 0}

The initial version of the patch was reverted because it missed the check that
the predicate being proved is actually guarded by this check on 1st iteration.
If it was not executed on 1st iteration (but possibly executes after that), then
it is incorrect to use reasoning about IV start to prove it.

Added the test where the miscompile was seen. Unfortunately, my attempts
to reduce it with bugpoint did not succeed; it can further be reduced when
we understand how to do it without losing the initial bug's notion.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

9904

If Y is loop invariant, this obviously follows. And the more general form of (X,+,W) < Y ==> X < Y would also hold.

I'm struggling to convince myself this holds when Y is an arbitrary loop varying scev. I haven't found a counter example yet.

Could I ask you to split this into two patches? One for the invariant case since that's easy to reason about, and one for the varying Y case? I both want to think about that separately and have an easy patch to revert if needed.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9904

Do we need this for varying Y case?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9904

I just realized my code for NE and EQ is wrong.

Actually, there are two conceptually different cases here I want to emphasize.

The isImpliedCondOperandsViaAddRecStart(Pred, X, RHS, {X,+,W}, Y) (Y is a loop invariant) actually means two different things depending on the context.

If we query it in the loop, the known fact {X,+,W} Pred Y is true for IV on every iteration, in particular on the first iteration. So we can trivially make this descent.

If we query it *after* the loop, then the known fact {X,+,W} Pred Y means the following: after the loop has ended and the final value of this IndVar is computed, this predicate is true for this final value.

If we know that the IndVar was strictly reducing/increasing (steps 1/-1), then we can still make this transit: {X,+,-1} > Y on the first iteration and went down, but even on the last iteration it is still greater than Y. The fact that it was stronger than Y on the first iteration is even a stronger fact, but if it's enough then fine.

But this does not hold for NE.

Actually I do not want to deal with "queried after loop" at all. The logic there is too flacky. What I really want is that this fact is known in loop. I think this code should be in "isKnownOnEveryIteration".

[mkazantsev]

Ruled out "known after loop" case because it is something we do not want to deal with.

[reames]

LGTM

I'd missed the subtlety with the context. I'm glad you caught that!

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
 
   /// Return a predecessor of BB (which may not be an immediate predecessor)
   /// which has exactly one successor from which BB is reachable, or null if
   /// no such block is found.
   std::pair<const BasicBlock *, const BasicBlock *>
   getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
 
   /// Test whether the condition described by Pred, LHS, and RHS is true
-  /// whenever the given FoundCondValue value evaluates to true.
+  /// whenever the given FoundCondValue value evaluates to true in given
+  /// Context. If Context is nullptr, then the found predicate is true
+  /// everywhere.
   bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
-                     const Value *FoundCondValue, bool Inverse);
+                     const Value *FoundCondValue, bool Inverse,
+                     const Instruction *Context = nullptr);
 
   /// Test whether the condition described by Pred, LHS, and RHS is true
   /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
-  /// true.
+  /// true in given Context. If Context is nullptr, then the found predicate is
+  /// true everywhere.
   bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
                      ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
-                     const SCEV *FoundRHS);
+                     const SCEV *FoundRHS,
+                     const Instruction *Context = nullptr);
 
   /// Test whether the condition described by Pred, LHS, and RHS is true
   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
-  /// true.
+  /// true in given Context. If Context is nullptr, then the found predicate is
+  /// true everywhere.
   bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
                              const SCEV *RHS, const SCEV *FoundLHS,
-                             const SCEV *FoundRHS);
+                             const SCEV *FoundRHS,
+                             const Instruction *Context = nullptr);
 
   /// Test whether the condition described by Pred, LHS, and RHS is true
   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
   /// true. Here LHS is an operation that includes FoundLHS as one of its
   /// arguments.
   bool isImpliedViaOperations(ICmpInst::Predicate Pred,
                               const SCEV *LHS, const SCEV *RHS,
                               const SCEV *FoundLHS, const SCEV *FoundRHS,
bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
                                           const SCEV *LHS, const SCEV *RHS,
                                           const SCEV *FoundLHS,
                                           const SCEV *FoundRHS);
 
   /// Test whether the condition described by Pred, LHS, and RHS is true
   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
   /// true.
   ///
+  /// This routine tries to weaken the known condition basing on fact that
+  /// FoundLHS is an AddRec.
+  bool isImpliedCondOperandsViaAddRecStart(ICmpInst::Predicate Pred,
+                                           const SCEV *LHS, const SCEV *RHS,
+                                           const SCEV *FoundLHS,
+                                           const SCEV *FoundRHS,
+                                           const Instruction *Context);
+
+  /// Test whether the condition described by Pred, LHS, and RHS is true
+  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
+  /// true.
+  ///
   /// This routine tries to figure out predicate for Phis which are SCEVUnknown
   /// if it is true for every possible incoming value from their respective
   /// basic blocks.
   bool isImpliedViaMerge(ICmpInst::Predicate Pred,
                          const SCEV *LHS, const SCEV *RHS,
                          const SCEV *FoundLHS, const SCEV *FoundRHS,
                          unsigned Depth);
 

llvm/lib/Analysis/ScalarEvolution.cpp

if (ProvingStrictComparison) {
       if (ProvedNonStrictComparison && ProvedNonEquality)
         return true;
     }
     return false;
   };
 
   // Try to prove (Pred, LHS, RHS) using isImpliedCond.
   auto ProveViaCond = [&](const Value *Condition, bool Inverse) {
-    if (isImpliedCond(Pred, LHS, RHS, Condition, Inverse))
+    const Instruction *Context = &BB->front();
+    if (isImpliedCond(Pred, LHS, RHS, Condition, Inverse, Context))
       return true;
     if (ProvingStrictComparison) {
       if (!ProvedNonStrictComparison)
-        ProvedNonStrictComparison =
-            isImpliedCond(NonStrictPredicate, LHS, RHS, Condition, Inverse);
+        ProvedNonStrictComparison = isImpliedCond(NonStrictPredicate, LHS, RHS,
+                                                  Condition, Inverse, Context);
       if (!ProvedNonEquality)
-        ProvedNonEquality =
-            isImpliedCond(ICmpInst::ICMP_NE, LHS, RHS, Condition, Inverse);
+        ProvedNonEquality = isImpliedCond(ICmpInst::ICMP_NE, LHS, RHS,
+                                          Condition, Inverse, Context);
       if (ProvedNonStrictComparison && ProvedNonEquality)
         return true;
     }
     return false;
   };
 
   // Starting at the block's predecessor, climb up the predecessor chain, as long
   // as there are predecessors that can be found that have unique successors
assert(isAvailableAtLoopEntry(LHS, L) &&
          "LHS is not available at Loop Entry");
   assert(isAvailableAtLoopEntry(RHS, L) &&
          "RHS is not available at Loop Entry");
   return isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS);
 }
 
 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS,
-                                    const Value *FoundCondValue, bool Inverse) {
+                                    const Value *FoundCondValue, bool Inverse,
+                                    const Instruction *Context) {
   if (!PendingLoopPredicates.insert(FoundCondValue).second)
     return false;
 
   auto ClearOnExit =
       make_scope_exit([&]() { PendingLoopPredicates.erase(FoundCondValue); });
 
   // Recursively handle And and Or conditions.
   if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(FoundCondValue)) {
     if (BO->getOpcode() == Instruction::And) {
       if (!Inverse)
-        return isImpliedCond(Pred, LHS, RHS, BO->getOperand(0), Inverse) ||
-               isImpliedCond(Pred, LHS, RHS, BO->getOperand(1), Inverse);
+        return isImpliedCond(Pred, LHS, RHS, BO->getOperand(0), Inverse,
+                             Context) ||
+               isImpliedCond(Pred, LHS, RHS, BO->getOperand(1), Inverse,
+                             Context);
     } else if (BO->getOpcode() == Instruction::Or) {
       if (Inverse)
-        return isImpliedCond(Pred, LHS, RHS, BO->getOperand(0), Inverse) ||
-               isImpliedCond(Pred, LHS, RHS, BO->getOperand(1), Inverse);
+        return isImpliedCond(Pred, LHS, RHS, BO->getOperand(0), Inverse,
+                             Context) ||
+               isImpliedCond(Pred, LHS, RHS, BO->getOperand(1), Inverse,
+                             Context);
     }
   }
 
   const ICmpInst *ICI = dyn_cast<ICmpInst>(FoundCondValue);
   if (!ICI) return false;
 
   // Now that we found a conditional branch that dominates the loop or controls
   // the loop latch. Check to see if it is the comparison we are looking for.
   ICmpInst::Predicate FoundPred;
   if (Inverse)
     FoundPred = ICI->getInversePredicate();
   else
     FoundPred = ICI->getPredicate();
 
   const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
   const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
 
-  return isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS);
+  return isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS, Context);
 }
 
 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS,
                                     ICmpInst::Predicate FoundPred,
-                                    const SCEV *FoundLHS,
-                                    const SCEV *FoundRHS) {
+                                    const SCEV *FoundLHS, const SCEV *FoundRHS,
+                                    const Instruction *Context) {
   // Balance the types.
   if (getTypeSizeInBits(LHS->getType()) <
       getTypeSizeInBits(FoundLHS->getType())) {
     if (CmpInst::isSigned(Pred)) {
       LHS = getSignExtendExpr(LHS, FoundLHS->getType());
       RHS = getSignExtendExpr(RHS, FoundLHS->getType());
     } else {
       LHS = getZeroExtendExpr(LHS, FoundLHS->getType());
if (LHS == FoundRHS || RHS == FoundLHS) {
     } else {
       std::swap(LHS, RHS);
       Pred = ICmpInst::getSwappedPredicate(Pred);
     }
   }
 
   // Check whether the found predicate is the same as the desired predicate.
   if (FoundPred == Pred)
-    return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS);
+    return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, Context);
 
   // Check whether swapping the found predicate makes it the same as the
   // desired predicate.
   if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
     if (isa<SCEVConstant>(RHS))
-      return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS);
+      return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS, Context);
     else
-      return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred),
-                                   RHS, LHS, FoundLHS, FoundRHS);
+      return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred), RHS,
+                                   LHS, FoundLHS, FoundRHS, Context);
   }
 
   // Unsigned comparison is the same as signed comparison when both the operands
   // are non-negative.
   if (CmpInst::isUnsigned(FoundPred) &&
       CmpInst::getSignedPredicate(FoundPred) == Pred &&
       isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS))
-    return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS);
+    return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, Context);
 
   // Check if we can make progress by sharpening ranges.
   if (FoundPred == ICmpInst::ICMP_NE &&
       (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
 
     const SCEVConstant *C = nullptr;
     const SCEV *V = nullptr;
 
if (Min == C->getAPInt()) {
 
       APInt SharperMin = Min + 1;
 
       switch (Pred) {
         case ICmpInst::ICMP_SGE:
         case ICmpInst::ICMP_UGE:
           // We know V `Pred` SharperMin.  If this implies LHS `Pred`
           // RHS, we're done.
-          if (isImpliedCondOperands(Pred, LHS, RHS, V,
-                                    getConstant(SharperMin)))
+          if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
+                                    Context))
             return true;
           LLVM_FALLTHROUGH;
 
         case ICmpInst::ICMP_SGT:
         case ICmpInst::ICMP_UGT:
           // We know from the range information that (V `Pred` Min ||
           // V == Min).  We know from the guarding condition that !(V
           // == Min).  This gives us
           //
           //       V `Pred` Min || V == Min && !(V == Min)
           //   =>  V `Pred` Min
           //
           // If V `Pred` Min implies LHS `Pred` RHS, we're done.
 
-          if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min)))
+          if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min),
+                                    Context))
             return true;
           break;
 
         // `LHS < RHS` and `LHS <= RHS` are handled in the same way as `RHS > LHS` and `RHS >= LHS` respectively.
         case ICmpInst::ICMP_SLE:
         case ICmpInst::ICMP_ULE:
           if (isImpliedCondOperands(CmpInst::getSwappedPredicate(Pred), RHS,
-                                    LHS, V, getConstant(SharperMin)))
+                                    LHS, V, getConstant(SharperMin), Context))
             return true;
           LLVM_FALLTHROUGH;
 
         case ICmpInst::ICMP_SLT:
         case ICmpInst::ICMP_ULT:
           if (isImpliedCondOperands(CmpInst::getSwappedPredicate(Pred), RHS,
-                                    LHS, V, getConstant(Min)))
+                                    LHS, V, getConstant(Min), Context))
             return true;
           break;
 
         default:
           // No change
           break;
       }
     }
   }
 
   // Check whether the actual condition is beyond sufficient.
   if (FoundPred == ICmpInst::ICMP_EQ)
     if (ICmpInst::isTrueWhenEqual(Pred))
-      if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS))
+      if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, Context))
         return true;
   if (Pred == ICmpInst::ICMP_NE)
     if (!ICmpInst::isTrueWhenEqual(FoundPred))
-      if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS))
+      if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS,
+                                Context))
         return true;
 
   // Otherwise assume the worst.
   return false;
 }
 
 bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr,
                                      const SCEV *&L, const SCEV *&R,
Optional<APInt> ScalarEvolution::computeConstantDifference(const SCEV *More,
 
   // Compare (X + C1) vs (X + C2).
   if (C1 && C2 && RLess == RMore)
     return C2->getAPInt() - C1->getAPInt();
 
   return None;
 }
 
+bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
+    ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
+    const SCEV *FoundLHS, const SCEV *FoundRHS, const Instruction *Context) {
+  // Try to recognize the following pattern:
+  //
+  //   FoundRHS = ...
+  // ...
+  // loop:
+  //   FoundLHS = {Start,+,W}
+  // context_bb: // Basic block from the same loop
+  //   known(Pred, FoundLHS, FoundRHS)
+  //
+  // If some predicate is known in the context of a loop, it is also known on
+  // each iteration of this loop, including the first iteration. Therefore, in
+  // this case, `FoundLHS Pred FoundRHS` implies `Start Pred FoundRHS`. Try to
+  // prove the original pred using this fact.
+  if (!Context)
+    return false;
+  const BasicBlock *ContextBB = Context->getParent();
+  // Make sure AR varies in the context block.
+  if (auto *AR = dyn_cast<SCEVAddRecExpr>(FoundLHS)) {
+    const Loop *L = AR->getLoop();
+    // Make sure that context belongs to the loop and executes on 1st iteration
+    // (if it ever executes at all).
+    if (!L->contains(ContextBB) || !DT.dominates(ContextBB, L->getLoopLatch()))
+      return false;
+    if (!isAvailableAtLoopEntry(FoundRHS, AR->getLoop()))
+      return false;
+    return isImpliedCondOperands(Pred, LHS, RHS, AR->getStart(), FoundRHS);
+  }
+
+  if (auto *AR = dyn_cast<SCEVAddRecExpr>(FoundRHS)) {
+    const Loop *L = AR->getLoop();
+    // Make sure that context belongs to the loop and executes on 1st iteration
+    // (if it ever executes at all).
+    if (!L->contains(ContextBB) || !DT.dominates(ContextBB, L->getLoopLatch()))
+      return false;
+    if (!isAvailableAtLoopEntry(FoundLHS, AR->getLoop()))
+      return false;
+    return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, AR->getStart());
+  }
+
+  return false;
+}
+
 bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(
     ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
     const SCEV *FoundLHS, const SCEV *FoundRHS) {
   if (Pred != CmpInst::ICMP_SLT && Pred != CmpInst::ICMP_ULT)
     return false;
 
   const auto *AddRecLHS = dyn_cast<SCEVAddRecExpr>(LHS);
   if (!AddRecLHS)
if (RPhi && RPhi->getParent() == LBB) {
     }
   }
   return true;
 }
 
 bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
                                             const SCEV *LHS, const SCEV *RHS,
                                             const SCEV *FoundLHS,
-                                            const SCEV *FoundRHS) {
+                                            const SCEV *FoundRHS,
+                                            const Instruction *Context) {
   if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundLHS, FoundRHS))
     return true;
 
   if (isImpliedCondOperandsViaNoOverflow(Pred, LHS, RHS, FoundLHS, FoundRHS))
     return true;
 
+  if (isImpliedCondOperandsViaAddRecStart(Pred, LHS, RHS, FoundLHS, FoundRHS,
+                                          Context))
+    return true;
+
   return isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      FoundLHS, FoundRHS) ||
          // ~x < ~y --> x > y
          isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      getNotSCEV(FoundRHS),
                                      getNotSCEV(FoundLHS));
 }
 

llvm/test/Transforms/IndVarSimplify/addrec_no_exec_on_every_iteration.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -indvars -S | FileCheck %s
+; RUN: opt < %s -passes=indvars -S | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nofree norecurse nounwind uwtable
+define void @test(i8* nocapture readnone %arg, i8* noalias nocapture readnone %arg1, i8** noalias nocapture readnone %arg2, i8** noalias nocapture readonly %arg3, i64* noalias nocapture readnone %arg4) local_unnamed_addr #0 {
+; CHECK-LABEL: @test
+bb:
+  %tmp = bitcast i8** %arg3 to [1 x [4 x [10 x [5 x float]]]]**
+  %tmp5 = load [1 x [4 x [10 x [5 x float]]]]*, [1 x [4 x [10 x [5 x float]]]]** %tmp, align 8, !invariant.load !0, !dereferenceable !1, !align !2
+  %tmp6 = getelementptr inbounds i8*, i8** %arg3, i64 3
+  %tmp7 = load i8*, i8** %tmp6, align 8, !invariant.load !0, !dereferenceable !3, !align !2
+  %tmp8 = bitcast i8* %tmp7 to [10 x [5 x [2 x [1 x [2 x float]]]]]*
+  br label %bb9
+
+bb9:                                              ; preds = %bb33, %bb
+  %tmp10 = phi i64 [ 0, %bb ], [ %tmp34, %bb33 ]
+  %tmp11 = sub nsw i64 9, %tmp10
+  br label %bb12
+
+bb12:                                             ; preds = %bb30, %bb9
+  %tmp13 = phi i64 [ 0, %bb9 ], [ %tmp31, %bb30 ]
+  %tmp14 = sub nsw i64 4, %tmp13
+  br label %bb15
+
+bb15:                                             ; preds = %bb27, %bb12
+  %tmp16 = phi i64 [ 0, %bb12 ], [ %tmp28, %bb27 ]
+  %tmp17 = mul i64 %tmp16, -2
+  %tmp18 = add i64 %tmp17, 2
+  br label %bb19
+
+bb19:                                             ; preds = %bb19, %bb15
+  %tmp20 = phi i64 [ 0, %bb15 ], [ %tmp25, %bb19 ]
+  %tmp21 = add nuw nsw i64 %tmp18, %tmp20
+  %tmp22 = getelementptr inbounds [1 x [4 x [10 x [5 x float]]]], [1 x [4 x [10 x [5 x float]]]]* %tmp5, i64 0, i64 0, i64 %tmp21, i64 %tmp11, i64 %tmp14
+  %tmp23 = load float, float* %tmp22, align 4, !invariant.load !0, !noalias !4
+  %tmp24 = getelementptr inbounds [10 x [5 x [2 x [1 x [2 x float]]]]], [10 x [5 x [2 x [1 x [2 x float]]]]]* %tmp8, i64 0, i64 %tmp10, i64 %tmp13, i64 %tmp16, i64 0, i64 %tmp20
+  store float %tmp23, float* %tmp24, align 4, !alias.scope !4, !noalias !7
+  %tmp25 = add nuw nsw i64 %tmp20, 1
+  %tmp26 = icmp eq i64 %tmp20, 0
+  br i1 %tmp26, label %bb19, label %bb27
+
+bb27:                                             ; preds = %bb19
+  %tmp28 = add nuw nsw i64 %tmp16, 1
+  %tmp29 = icmp eq i64 %tmp16, 0
+  br i1 %tmp29, label %bb15, label %bb30
+
+bb30:                                             ; preds = %bb27
+  %tmp31 = add nuw nsw i64 %tmp13, 1
+  %tmp32 = icmp ugt i64 %tmp13, 3
+  br i1 %tmp32, label %bb33, label %bb12
+
+bb33:                                             ; preds = %bb30
+  %tmp34 = add nuw nsw i64 %tmp10, 1
+  %tmp35 = icmp ugt i64 %tmp10, 8
+  br i1 %tmp35, label %bb36, label %bb9
+
+bb36:                                             ; preds = %bb33
+  %tmp37 = getelementptr inbounds i8*, i8** %arg3, i64 1
+  %tmp38 = bitcast i8** %tmp37 to [1 x [4 x [6 x [7 x float]]]]**
+  %tmp39 = load [1 x [4 x [6 x [7 x float]]]]*, [1 x [4 x [6 x [7 x float]]]]** %tmp38, align 8, !invariant.load !0, !dereferenceable !10, !align !2
+  %tmp40 = getelementptr inbounds i8, i8* %tmp7, i64 800
+  %tmp41 = bitcast i8* %tmp40 to [2 x [6 x [7 x [2 x [1 x float]]]]]*
+  br label %bb42
+
+bb42:                                             ; preds = %bb63, %bb36
+  %tmp43 = phi i64 [ 0, %bb36 ], [ %tmp64, %bb63 ]
+  br label %bb44
+
+bb44:                                             ; preds = %bb60, %bb42
+  %tmp45 = phi i64 [ 0, %bb42 ], [ %tmp61, %bb60 ]
+  br label %bb46
+
+bb46:                                             ; preds = %bb57, %bb44
+  %tmp47 = phi i64 [ 0, %bb44 ], [ %tmp58, %bb57 ]
+  br label %bb48
+
+bb48:                                             ; preds = %bb48, %bb46
+  %tmp49 = phi i64 [ 0, %bb46 ], [ %tmp55, %bb48 ]
+  %tmp50 = shl nuw nsw i64 %tmp49, 1
+  %tmp51 = add nuw nsw i64 %tmp50, %tmp43
+  %tmp52 = getelementptr inbounds [1 x [4 x [6 x [7 x float]]]], [1 x [4 x [6 x [7 x float]]]]* %tmp39, i64 0, i64 0, i64 %tmp51, i64 %tmp45, i64 %tmp47
+  %tmp53 = load float, float* %tmp52, align 4, !invariant.load !0, !noalias !11
+  %tmp54 = getelementptr inbounds [2 x [6 x [7 x [2 x [1 x float]]]]], [2 x [6 x [7 x [2 x [1 x float]]]]]* %tmp41, i64 0, i64 %tmp43, i64 %tmp45, i64 %tmp47, i64 %tmp49, i64 0
+  store float %tmp53, float* %tmp54, align 4, !alias.scope !11, !noalias !12
+  %tmp55 = add nuw nsw i64 %tmp49, 1
+  %tmp56 = icmp eq i64 %tmp49, 0
+  br i1 %tmp56, label %bb48, label %bb57
+
+bb57:                                             ; preds = %bb48
+  %tmp58 = add nuw nsw i64 %tmp47, 1
+  %tmp59 = icmp ugt i64 %tmp47, 5
+  br i1 %tmp59, label %bb60, label %bb46
+
+bb60:                                             ; preds = %bb57
+  %tmp61 = add nuw nsw i64 %tmp45, 1
+  %tmp62 = icmp ugt i64 %tmp45, 4
+  br i1 %tmp62, label %bb63, label %bb44
+
+bb63:                                             ; preds = %bb60
+  %tmp64 = add nuw nsw i64 %tmp43, 1
+  %tmp65 = icmp eq i64 %tmp43, 0
+  br i1 %tmp65, label %bb42, label %bb66
+
+bb66:                                             ; preds = %bb63
+  %tmp67 = getelementptr inbounds i8, i8* %tmp7, i64 1472
+  %tmp68 = bitcast i8* %tmp67 to [2 x [1 x [2 x [2 x [2 x float]]]]]*
+  br label %bb69
+
+bb69:                                             ; preds = %bb140, %bb66
+  %tmp70 = phi i64 [ 0, %bb66 ], [ %tmp141, %bb140 ]
+  br label %bb71
+
+bb71:                                             ; preds = %bb137, %bb69
+  %tmp72 = phi i64 [ 0, %bb69 ], [ %tmp138, %bb137 ]
+  %tmp73 = shl nuw nsw i64 %tmp72, 1
+  %tmp74 = add nsw i64 %tmp73, -2
+  br label %bb75
+
+bb75:                                             ; preds = %bb134, %bb71
+  %tmp76 = phi i64 [ 0, %bb71 ], [ %tmp135, %bb134 ]
+  %tmp77 = add nsw i64 %tmp76, -1
+  br label %bb78
+
+bb78:                                             ; preds = %bb129, %bb75
+  %tmp79 = phi i64 [ 0, %bb75 ], [ %tmp132, %bb129 ]
+  br label %bb80
+
+bb80:                                             ; preds = %bb125, %bb78
+  %tmp81 = phi float [ 0.000000e+00, %bb78 ], [ %tmp126, %bb125 ]
+  %tmp82 = phi i64 [ 0, %bb78 ], [ %tmp127, %bb125 ]
+  %tmp83 = shl nuw nsw i64 %tmp82, 1
+  %tmp84 = add nsw i64 %tmp83, -1
+  %tmp85 = icmp ult i64 %tmp84, 10
+  %tmp86 = sub nsw i64 5, %tmp82
+  br i1 %tmp85, label %bb88, label %bb87
+
+bb87:                                             ; preds = %bb80
+  br label %bb124
+
+bb88:                                             ; preds = %bb80
+  br label %bb89
+
+bb89:                                             ; preds = %bb100, %bb88
+  %tmp90 = phi float [ %tmp101, %bb100 ], [ %tmp81, %bb88 ]
+  %tmp91 = phi i64 [ %tmp102, %bb100 ], [ 0, %bb88 ]
+  %tmp92 = add i64 %tmp74, %tmp91
+  %tmp93 = icmp ult i64 %tmp92, 5
+  %tmp94 = sub nsw i64 6, %tmp91
+  br i1 %tmp93, label %bb96, label %bb95
+
+bb95:                                             ; preds = %bb89
+  br label %bb99
+
+bb96:                                             ; preds = %bb89
+  br label %bb104
+
+bb97:                                             ; preds = %bb110
+  %tmp98 = phi float [ %tmp111, %bb110 ]
+  br label %bb100
+
+bb99:                                             ; preds = %bb95
+  br label %bb100
+
+bb100:                                            ; preds = %bb99, %bb97
+  %tmp101 = phi float [ %tmp98, %bb97 ], [ %tmp90, %bb99 ]
+  %tmp102 = add nuw nsw i64 %tmp91, 1
+  %tmp103 = icmp ugt i64 %tmp91, 5
+  br i1 %tmp103, label %bb122, label %bb89
+
+bb104:                                            ; preds = %bb110, %bb96
+  %tmp105 = phi float [ %tmp111, %bb110 ], [ %tmp90, %bb96 ]
+  %tmp106 = phi i64 [ %tmp112, %bb110 ], [ 0, %bb96 ]
+  %tmp107 = shl nuw nsw i64 %tmp106, 1
+  ; CHECK-NOT: %bugged = add nuw nsw
+  ; CHECK:     %bugged = add nsw
+  %bugged = add i64 %tmp77, %tmp107
+  %tmp109 = icmp ult i64 %bugged, 2
+  br i1 %tmp109, label %bb114, label %bb110
+
+bb110:                                            ; preds = %bb114, %bb104
+  %tmp111 = phi float [ %tmp121, %bb114 ], [ %tmp105, %bb104 ]
+  %tmp112 = add nuw nsw i64 %tmp106, 1
+  %tmp113 = icmp eq i64 %tmp106, 0
+  br i1 %tmp113, label %bb104, label %bb97
+
+bb114:                                            ; preds = %bb104
+  %tmp115 = sub nsw i64 1, %tmp106
+  %tmp116 = getelementptr inbounds [2 x [6 x [7 x [2 x [1 x float]]]]], [2 x [6 x [7 x [2 x [1 x float]]]]]* %tmp41, i64 0, i64 %tmp70, i64 %tmp86, i64 %tmp94, i64 %tmp115, i64 0
+  %tmp117 = getelementptr inbounds [10 x [5 x [2 x [1 x [2 x float]]]]], [10 x [5 x [2 x [1 x [2 x float]]]]]* %tmp8, i64 0, i64 %tmp84, i64 %tmp92, i64 %bugged, i64 0, i64 %tmp79
+  %tmp118 = load float, float* %tmp117, align 4, !alias.scope !4, !noalias !7
+  %tmp119 = load float, float* %tmp116, align 4, !alias.scope !11, !noalias !12
+  %tmp120 = fmul reassoc nsz contract float %tmp118, %tmp119
+  %tmp121 = fadd reassoc nsz contract float %tmp105, %tmp120
+  br label %bb110
+
+bb122:                                            ; preds = %bb100
+  %tmp123 = phi float [ %tmp101, %bb100 ]
+  br label %bb125
+
+bb124:                                            ; preds = %bb87
+  br label %bb125
+
+bb125:                                            ; preds = %bb124, %bb122
+  %tmp126 = phi float [ %tmp123, %bb122 ], [ %tmp81, %bb124 ]
+  %tmp127 = add nuw nsw i64 %tmp82, 1
+  %tmp128 = icmp ugt i64 %tmp82, 4
+  br i1 %tmp128, label %bb129, label %bb80
+
+bb129:                                            ; preds = %bb125
+  %tmp130 = phi float [ %tmp126, %bb125 ]
+  %tmp131 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 %tmp70, i64 0, i64 %tmp72, i64 %tmp76, i64 %tmp79
+  store float %tmp130, float* %tmp131, align 4, !alias.scope !13, !noalias !14
+  %tmp132 = add nuw nsw i64 %tmp79, 1
+  %tmp133 = icmp eq i64 %tmp79, 0
+  br i1 %tmp133, label %bb78, label %bb134
+
+bb134:                                            ; preds = %bb129
+  %tmp135 = add nuw nsw i64 %tmp76, 1
+  %tmp136 = icmp eq i64 %tmp76, 0
+  br i1 %tmp136, label %bb75, label %bb137
+
+bb137:                                            ; preds = %bb134
+  %tmp138 = add nuw nsw i64 %tmp72, 1
+  %tmp139 = icmp eq i64 %tmp72, 0
+  br i1 %tmp139, label %bb71, label %bb140
+
+bb140:                                            ; preds = %bb137
+  %tmp141 = add nuw nsw i64 %tmp70, 1
+  %tmp142 = icmp eq i64 %tmp70, 0
+  br i1 %tmp142, label %bb69, label %bb143
+
+bb143:                                            ; preds = %bb140
+  %tmp144 = getelementptr inbounds i8*, i8** %arg3, i64 2
+  %tmp145 = bitcast i8** %tmp144 to [4 x [2 x [1 x [2 x float]]]]**
+  %tmp146 = load [4 x [2 x [1 x [2 x float]]]]*, [4 x [2 x [1 x [2 x float]]]]** %tmp145, align 8, !invariant.load !0, !dereferenceable !16, !align !2
+  br label %bb147
+
+bb147:                                            ; preds = %bb143
+  br label %bb148
+
+bb148:                                            ; preds = %bb147
+  br label %bb149
+
+bb149:                                            ; preds = %bb148
+  %tmp150 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 0, i64 0, i64 0, i64 0, i64 0
+  %tmp151 = load float, float* %tmp150, align 4, !alias.scope !13, !noalias !14
+  %tmp152 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 0, i64 0, i64 0, i64 0
+  store float %tmp151, float* %tmp152, align 4, !alias.scope !17, !noalias !13
+  %tmp153 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 0, i64 0, i64 1, i64 0, i64 0
+  %tmp154 = load float, float* %tmp153, align 4, !alias.scope !13, !noalias !14
+  %tmp155 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 0, i64 0, i64 0, i64 1
+  store float %tmp154, float* %tmp155, align 4, !alias.scope !17, !noalias !13
+  br label %bb156
+
+bb156:                                            ; preds = %bb149
+  %tmp157 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 1, i64 0, i64 0, i64 0, i64 0
+  %tmp158 = load float, float* %tmp157, align 4, !alias.scope !13, !noalias !14
+  %tmp159 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 0, i64 1, i64 0, i64 0
+  store float %tmp158, float* %tmp159, align 4, !alias.scope !17, !noalias !13
+  %tmp160 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 1, i64 0, i64 1, i64 0, i64 0
+  %tmp161 = load float, float* %tmp160, align 4, !alias.scope !13, !noalias !14
+  %tmp162 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 0, i64 1, i64 0, i64 1
+  store float %tmp161, float* %tmp162, align 4, !alias.scope !17, !noalias !13
+  br label %bb163
+
+bb163:                                            ; preds = %bb156
+  br label %bb164
+
+bb164:                                            ; preds = %bb163
+  %tmp165 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 0, i64 0, i64 0, i64 0, i64 1
+  %tmp166 = load float, float* %tmp165, align 4, !alias.scope !13, !noalias !14
+  %tmp167 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 1, i64 0, i64 0, i64 0
+  store float %tmp166, float* %tmp167, align 4, !alias.scope !17, !noalias !13
+  %tmp168 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 0, i64 0, i64 1, i64 0, i64 1
+  %tmp169 = load float, float* %tmp168, align 4, !alias.scope !13, !noalias !14
+  %tmp170 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 1, i64 0, i64 0, i64 1
+  store float %tmp169, float* %tmp170, align 4, !alias.scope !17, !noalias !13
+  br label %bb171
+
+bb171:                                            ; preds = %bb164
+  %tmp172 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 1, i64 0, i64 0, i64 0, i64 1
+  %tmp173 = load float, float* %tmp172, align 4, !alias.scope !13, !noalias !14
+  %tmp174 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 1, i64 1, i64 0, i64 0
+  store float %tmp173, float* %tmp174, align 4, !alias.scope !17, !noalias !13
+  %tmp175 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 1, i64 0, i64 1, i64 0, i64 1
+  %tmp176 = load float, float* %tmp175, align 4, !alias.scope !13, !noalias !14
+  %tmp177 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 1, i64 1, i64 0, i64 1
+  store float %tmp176, float* %tmp177, align 4, !alias.scope !17, !noalias !13
+  br label %bb178
+
+bb178:                                            ; preds = %bb171
+  br label %bb179
+
+bb179:                                            ; preds = %bb178
+  %tmp180 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 0, i64 0, i64 0, i64 1, i64 0
+  %tmp181 = load float, float* %tmp180, align 4, !alias.scope !13, !noalias !14
+  %tmp182 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 2, i64 0, i64 0, i64 0
+  store float %tmp181, float* %tmp182, align 4, !alias.scope !17, !noalias !13
+  %tmp183 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 0, i64 0, i64 1, i64 1, i64 0
+  %tmp184 = load float, float* %tmp183, align 4, !alias.scope !13, !noalias !14
+  %tmp185 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 2, i64 0, i64 0, i64 1
+  store float %tmp184, float* %tmp185, align 4, !alias.scope !17, !noalias !13
+  br label %bb186
+
+bb186:                                            ; preds = %bb179
+  %tmp187 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 1, i64 0, i64 0, i64 1, i64 0
+  %tmp188 = load float, float* %tmp187, align 4, !alias.scope !13, !noalias !14
+  %tmp189 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 2, i64 1, i64 0, i64 0
+  store float %tmp188, float* %tmp189, align 4, !alias.scope !17, !noalias !13
+  %tmp190 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 1, i64 0, i64 1, i64 1, i64 0
+  %tmp191 = load float, float* %tmp190, align 4, !alias.scope !13, !noalias !14
+  %tmp192 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 2, i64 1, i64 0, i64 1
+  store float %tmp191, float* %tmp192, align 4, !alias.scope !17, !noalias !13
+  br label %bb193
+
+bb193:                                            ; preds = %bb186
+  br label %bb194
+
+bb194:                                            ; preds = %bb193
+  %tmp195 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 0, i64 0, i64 0, i64 1, i64 1
+  %tmp196 = load float, float* %tmp195, align 4, !alias.scope !13, !noalias !14
+  %tmp197 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 3, i64 0, i64 0, i64 0
+  store float %tmp196, float* %tmp197, align 4, !alias.scope !17, !noalias !13
+  %tmp198 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 0, i64 0, i64 1, i64 1, i64 1
+  %tmp199 = load float, float* %tmp198, align 4, !alias.scope !13, !noalias !14
+  %tmp200 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 3, i64 0, i64 0, i64 1
+  store float %tmp199, float* %tmp200, align 4, !alias.scope !17, !noalias !13
+  br label %bb201
+
+bb201:                                            ; preds = %bb194
+  %tmp202 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 1, i64 0, i64 0, i64 1, i64 1
+  %tmp203 = load float, float* %tmp202, align 4, !alias.scope !13, !noalias !14
+  %tmp204 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 3, i64 1, i64 0, i64 0
+  store float %tmp203, float* %tmp204, align 4, !alias.scope !17, !noalias !13
+  %tmp205 = getelementptr inbounds [2 x [1 x [2 x [2 x [2 x float]]]]], [2 x [1 x [2 x [2 x [2 x float]]]]]* %tmp68, i64 0, i64 1, i64 0, i64 1, i64 1, i64 1
+  %tmp206 = load float, float* %tmp205, align 4, !alias.scope !13, !noalias !14
+  %tmp207 = getelementptr inbounds [4 x [2 x [1 x [2 x float]]]], [4 x [2 x [1 x [2 x float]]]]* %tmp146, i64 0, i64 3, i64 1, i64 0, i64 1
+  store float %tmp206, float* %tmp207, align 4, !alias.scope !17, !noalias !13
+  ret void
+}
+
+attributes #0 = { nofree norecurse nounwind uwtable "denormal-fp-math"="preserve-sign" "no-frame-pointer-elim"="false" }
+
+!0 = !{}
+!1 = !{i64 800}
+!2 = !{i64 16}
+!3 = !{i64 1536}
+!4 = !{!5}
+!5 = !{!"buffer: {index:3, offset:0, size:800}", !6}
+!6 = !{!"XLA global AA domain"}
+!7 = !{!8, !9}
+!8 = !{!"buffer: {index:3, offset:800, size:672}", !6}
+!9 = !{!"buffer: {index:3, offset:1472, size:64}", !6}
+!10 = !{i64 672}
+!11 = !{!8}
+!12 = !{!5, !9}
+!13 = !{!9}
+!14 = !{!15, !5, !8}
+!15 = !{!"buffer: {index:2, offset:0, size:64}", !6}
+!16 = !{i64 64}
+!17 = !{!15}

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 
     const SCEV *BTC = SE.getBackedgeTakenCount(L);
     EXPECT_FALSE(isa<SCEVConstant>(BTC));
     const SCEV *MaxBTC = SE.getConstantMaxBackedgeTakenCount(L);
     EXPECT_EQ(cast<SCEVConstant>(MaxBTC)->getAPInt(), 15);
   });
 }
 
+TEST_F(ScalarEvolutionsTest, ImpliedViaAddRecStart) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(
+      "define void @foo(i32* %p) { "
+      "entry: "
+      "  %x = load i32, i32* %p, !range !0 "
+      "  br label %loop "
+      "loop: "
+      "  %iv = phi i32 [ %x, %entry], [%iv.next, %backedge] "
+      "  %ne.check = icmp ne i32 %iv, 0 "
+      "  br i1 %ne.check, label %backedge, label %exit "
+      "backedge: "
+      "  %iv.next = add i32 %iv, -1 "
+      "  br label %loop "
+      "exit:"
+      "  ret void "
+      "} "
+      "!0 = !{i32 0, i32 2147483647}",
+      Err, C);
+
+  ASSERT_TRUE(M && "Could not parse module?");
+  ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+    auto *X = SE.getSCEV(getInstructionByName(F, "x"));
+    auto *Context = getInstructionByName(F, "iv.next");
+    EXPECT_TRUE(SE.isKnownPredicateAt(ICmpInst::ICMP_NE, X,
+                                      SE.getZero(X->getType()), Context));
+  });
+}
+
+TEST_F(ScalarEvolutionsTest, UnsignedIsImpliedViaOperations) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M =
+      parseAssemblyString("define void @foo(i32* %p1, i32* %p2) { "
+                          "entry: "
+                          "  %x = load i32, i32* %p1, !range !0 "
+                          "  %cond = icmp ne i32 %x, 0 "
+                          "  br i1 %cond, label %guarded, label %exit "
+                          "guarded: "
+                          "  %y = add i32 %x, -1 "
+                          "  ret void "
+                          "exit: "
+                          "  ret void "
+                          "} "
+                          "!0 = !{i32 0, i32 2147483647}",
+                          Err, C);
+
+  ASSERT_TRUE(M && "Could not parse module?");
+  ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+    auto *X = SE.getSCEV(getInstructionByName(F, "x"));
+    auto *Y = SE.getSCEV(getInstructionByName(F, "y"));
+    auto *Guarded = getInstructionByName(F, "y")->getParent();
+    ASSERT_TRUE(Guarded);
+    EXPECT_TRUE(
+        SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_ULT, Y, X));
+    EXPECT_TRUE(
+        SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_UGT, X, Y));
+  });
+}
+
 }  // end namespace llvm