diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -10785,6 +10785,10 @@
       if (!dominates(RHS, IncBB))
         return false;
       const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
+      // Make sure L does not refer to a value from a potentially previous
+      // iteration of a loop.
+      if (!properlyDominates(L, IncBB))
+        return false;
       if (!ProvedEasily(L, RHS))
         return false;
     }
diff --git a/llvm/test/Transforms/IRCE/decrementing-loop.ll b/llvm/test/Transforms/IRCE/decrementing-loop.ll
--- a/llvm/test/Transforms/IRCE/decrementing-loop.ll
+++ b/llvm/test/Transforms/IRCE/decrementing-loop.ll
@@ -210,16 +210,17 @@
   ret void
 }
 
+; TODO: we need to be more careful when trying to look through phi nodes in
+; cycles, because the condition to prove may reference the previous value of
+; the phi. So we currently fail to optimize this case.
 ; Check that we can figure out that IV is non-negative via implication through
 ; two Phi nodes, one being AddRec.
 define void @test_05(i32* %a, i32* %a_len_ptr, i1 %cond) {
 
 ; CHECK-LABEL: test_05
-; CHECK:       mainloop:
-; CHECK-NEXT:    br label %loop
-; CHECK:       loop:
-; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
-; CHECK:       loop.preloop:
+; CHECK: entry:
+; CHECK:   br label %merge
+; CHECK-NOT: mainloop
 
  entry:
   %len.a = load i32, i32* %a_len_ptr, !range !0
diff --git a/llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll b/llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll
--- a/llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll
+++ b/llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll
@@ -453,7 +453,8 @@
 ; CHECK-NEXT:    br i1 [[INNER_COND]], label [[INNER]], label [[OUTER_EXITING_1:%.*]]
 ; CHECK:       outer.exiting.1:
 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X]], [[INNER]] ]
-; CHECK-NEXT:    br i1 false, label [[EXIT:%.*]], label [[OUTER_LATCH]]
+; CHECK-NEXT:    [[OUTER_COND_1:%.*]] = icmp sgt i32 [[X_LCSSA]], -1
+; CHECK-NEXT:    br i1 [[OUTER_COND_1]], label [[EXIT:%.*]], label [[OUTER_LATCH]]
 ; CHECK:       outer.latch:
 ; CHECK-NEXT:    [[IV_OUTER_NEXT]] = add nuw nsw i32 [[IV_OUTER]], 1
 ; CHECK-NEXT:    [[OUTER_COND_2:%.*]] = icmp ult i32 [[IV_OUTER]], 100