Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -1903,6 +1903,26 @@
         isKnownNonZero(SI->getFalseValue(), DL, Depth, Q))
       return true;
   }
+  // PHI
+  else if (PHINode *PN = dyn_cast<PHINode>(V)) {
+    // Try and detect a recurrence that monotonically increases from a
+    // starting value, as these are common as induction variables.
+    if (PN->getNumIncomingValues() == 2) {
+      Value *Start = PN->getIncomingValue(0);
+      Value *Induction = PN->getIncomingValue(1);
+      if (isa<ConstantInt>(Induction) && !isa<ConstantInt>(Start))
+        std::swap(Start, Induction);
+      if (ConstantInt *C = dyn_cast<ConstantInt>(Start)) {
+        if (!C->isZero() && !C->isNegative()) {
+          ConstantInt *X;
+          if ((match(Induction, m_NSWAdd(m_Specific(PN), m_ConstantInt(X))) ||
+               match(Induction, m_NUWAdd(m_Specific(PN), m_ConstantInt(X)))) &&
+              !X->isNegative())
+            return true;
+        }
+      }
+    }
+  }
 
   if (!BitWidth) return false;
   APInt KnownZero(BitWidth, 0);
Index: test/Analysis/ValueTracking/monotonic-phi.ll
===================================================================
--- /dev/null
+++ test/Analysis/ValueTracking/monotonic-phi.ll
@@ -0,0 +1,49 @@
+; RUN: opt -instsimplify -S < %s | FileCheck %s
+
+; CHECK-LABEL: @test1
+define i1 @test1(i8 %p, i8* %pq, i8 %n, i8 %r) {
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 1, %entry ], [ %next, %loop ]
+  %next = add nsw i8 %A, 1
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %add = or i8 %A, %r
+  %cmp = icmp eq i8 %add, 0
+  ; CHECK: ret i1 false
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @test2
+define i1 @test2(i8 %p, i8* %pq, i8 %n, i8 %r) {
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 1, %entry ], [ %next, %loop ]
+  %next = add i8 %A, 1
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %add = or i8 %A, %r
+  %cmp = icmp eq i8 %add, 0
+  ; CHECK-NOT: ret i1 false
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @test3
+define i1 @test3(i8 %p, i8* %pq, i8 %n, i8 %r) {
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 1, %entry ], [ %next, %loop ]
+  %next = add nuw i8 %A, 1
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %add = or i8 %A, %r
+  %cmp = icmp eq i8 %add, 0
+  ; CHECK: ret i1 false
+  ret i1 %cmp
+}