Index: llvm/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/lib/Analysis/ValueTracking.cpp
+++ llvm/lib/Analysis/ValueTracking.cpp
@@ -2450,19 +2450,21 @@
   else if (const 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 (Q.IIQ.UseInstrInfo &&
-              (match(Induction, m_NSWAdd(m_Specific(PN), m_ConstantInt(X))) ||
-               match(Induction, m_NUWAdd(m_Specific(PN), m_ConstantInt(X)))) &&
-              !X->isNegative())
-            return true;
+    BinaryOperator *BO = nullptr;
+    Value *Start = nullptr, *Step = nullptr;
+    if (Q.IIQ.UseInstrInfo && matchSimpleRecurrence(PN, BO, Start, Step)) {
+      if (ConstantInt *StartCst = dyn_cast<ConstantInt>(Start)) {
+        if (!StartCst->isZero() && !StartCst->isNegative()) {
+          if (auto StepCst = dyn_cast<ConstantInt>(Step)) {
+            if (BO->getOpcode() == Instruction::Add &&
+                (BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) &&
+                !StepCst->isNegative())
+              return true;
+            if (BO->getOpcode() == Instruction::Mul &&
+                (BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) &&
+                !StepCst->isNegative() && !StepCst->isZero())
+              return true;
+          }
         }
       }
     }
Index: llvm/test/Analysis/ValueTracking/monotonic-phi.ll
===================================================================
--- llvm/test/Analysis/ValueTracking/monotonic-phi.ll
+++ llvm/test/Analysis/ValueTracking/monotonic-phi.ll
@@ -47,3 +47,33 @@
   ; CHECK: ret i1 false
   ret i1 %cmp
 }
+
+; CHECK-LABEL: @test4
+define i1 @test4(i8 %p, i8* %pq, i8 %n, i8 %r) {
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 2, %entry ], [ %next, %loop ]
+  %next = mul nsw i8 %A, 2
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %cmp = icmp eq i8 %A, 0
+  ; CHECK: ret i1 false
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @test5
+define i1 @test5(i8 %p, i8* %pq, i8 %n, i8 %r) {
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 2, %entry ], [ %next, %loop ]
+  %next = mul i8 %A, 2
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %cmp = icmp eq i8 %A, 0
+  ; CHECK: ret i1 %cmp
+  ret i1 %cmp
+}