Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -8694,8 +8694,30 @@
                                               const SCEVAddRecExpr *LHS,
                                               const SCEV *RHS) {
   const Loop *L = LHS->getLoop();
-  return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) &&
-         isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS);
+  // Check if the condition is met on the first iteration.
+  if (!isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS))
+    return false;
+
+  // If the backedge is guarded by condition for post-inc LHS, then we've
+  // proved that our predicate will be true on every iteration.
+  if (isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS))
+    return true;
+
+  // If the predicate is monotonic, and we've already proved it on the first
+  // iteration, it is enough to prove it on the last iteration.
+  bool Increasing = false;
+  if (isMonotonicPredicate(LHS, Pred, Increasing)) {
+    const SCEV *NumIters = getBackedgeTakenCount(L);
+    if (!isa<SCEVCouldNotCompute>(NumIters)) {
+      const SCEV *End = LHS->evaluateAtIteration(NumIters, *this);
+      if (isAvailableAtLoopEntry(End, L) &&
+          isLoopEntryGuardedByCond(L, Pred, End, RHS))
+        return true;
+    }
+  }
+
+  // Failed to prove anything, conservatively return false.
+  return false;
 }
 
 bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS,
Index: test/Transforms/IndVarSimplify/prove_via_monotonicity.ll
===================================================================
--- /dev/null
+++ test/Transforms/IndVarSimplify/prove_via_monotonicity.ll
@@ -0,0 +1,67 @@
+; RUN: opt -indvars -S < %s  | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Check that we can widen the indvar for the decrementing loop. Phi's range
+; doesn't give us enough information, so we have to prove it using monotonicity.
+
+define void @test_01(i32* %p, i32* %a) {
+
+; CHECK-LABEL: @test_01(
+; CHECK-NOT:     trunc
+
+entry:
+  %len = load i32, i32* %p, align 4, !range !0
+  %len.minus.1 = add nsw i32 %len, -1
+  %zero_check = icmp eq i32 %len, 0
+  br i1 %zero_check, label %loopexit, label %preheader
+
+preheader:
+  br label %loop
+
+loopexit:
+  ret void
+
+loop:
+  %iv = phi i32 [ %iv.next, %loop ], [ %len.minus.1, %preheader ]
+  ; CHECK: %indvars.iv = phi i64
+  %iv.wide = zext i32 %iv to i64
+  %el = getelementptr inbounds i32, i32* %a, i64 %iv.wide
+  store atomic i32 0, i32* %el unordered, align 4
+  %iv.next = add nsw i32 %iv, -1
+  ; CHECK: %loopcond = icmp slt i64 %indvars.iv, 1
+  %loopcond = icmp slt i32 %iv, 1
+  br i1 %loopcond, label %loopexit, label %loop
+}
+
+define void @test_02(i32* %p, i32* %a) {
+
+; CHECK-LABEL: @test_02(
+; CHECK-NOT:     trunc
+
+entry:
+  %len = load i32, i32* %p, align 4, !range !0
+  %len.minus.1 = add nsw i32 %len, -1
+  %zero_check = icmp eq i32 %len, 0
+  br i1 %zero_check, label %loopexit, label %preheader
+
+preheader:
+  br label %loop
+
+loopexit:
+  ret void
+
+loop:
+  %iv = phi i32 [ %iv.next, %loop ], [ %len.minus.1, %preheader ]
+  ; CHECK: %indvars.iv = phi i64
+  %iv.wide = zext i32 %iv to i64
+  %el = getelementptr inbounds i32, i32* %a, i64 %iv.wide
+  store atomic i32 0, i32* %el unordered, align 4
+  %iv.next = add nsw i32 %iv, -1
+  ; CHECK: %loopcond = icmp ult i64 %indvars.iv, 1
+  %loopcond = icmp ult i32 %iv, 1
+  br i1 %loopcond, label %loopexit, label %loop
+}
+
+!0 = !{i32 0, i32 2147483647}