diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -1373,7 +1373,7 @@
           else if (LR == I)
             L = LL;
           else
-            break;
+            continue;
           // Ok, we have a PHI of the form L op= R. Check for low
           // zero bits.
           computeKnownBits(R, Known2, Depth + 1, Q);
diff --git a/llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll b/llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll
@@ -0,0 +1,73 @@
+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+; Check that we can turn the icmp sle into icmp ult, regardless of the
+; order of the incoming values of the PHI node.
+
+declare i1 @cond()
+
+define void @phi_recurrence_start_first() {
+; CHECK-LABEL: define void @phi_recurrence_start_first() {
+; CHECK-LABEL: for.cond11:
+; CHECK-NEXT:   %i.1 = phi i32 [ %start, %if.then ], [ %step, %for.cond11 ]
+; CHECK-NEXT:   %cmp13 = icmp ult i32 %i.1, 100
+; CHECK-NEXT:   %step = add nsw i32 %i.1, 1
+; CHECK-NEXT:   br i1 %cmp13, label %for.cond11, label %while.end
+;
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %entry, %for.cond26
+  %cell.0 = phi i32 [ 0, %entry ], [ %start, %for.cond26 ]
+  %cond.v = call i1 @cond()
+  br i1 %cond.v, label %if.then, label %while.end
+
+if.then:                                          ; preds = %while.cond
+  %start = add nsw i32 %cell.0, 1
+  br i1 %cond.v, label %for.cond11, label %for.cond26
+
+for.cond11:                                       ; preds = %for.cond11, %if.then
+  %i.1 = phi i32 [ %start, %if.then ], [ %step, %for.cond11 ]
+  %cmp13 = icmp sle i32 %i.1, 99
+  %step = add nsw i32 %i.1, 1
+  br i1 %cmp13, label %for.cond11, label %while.end
+
+for.cond26:                                       ; preds = %if.then
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond, %for.cond11
+  ret void
+}
+
+define void @phi_recurrence_step_first() {
+; CHECK-LABEL: define void @phi_recurrence_step_first() {
+; CHECK-LABEL: for.cond11:
+; CHECK-NEXT:   %i.1 = phi i32 [ %start, %if.then ], [ %step, %for.cond11 ]
+; CHECK-NEXT:   %cmp13 = icmp ult i32 %i.1, 100
+; CHECK-NEXT:   %step = add nsw i32 %i.1, 1
+; CHECK-NEXT:   br i1 %cmp13, label %for.cond11, label %while.end
+;
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %entry, %for.cond26
+  %cell.0 = phi i32 [ 0, %entry ], [ %start, %for.cond26 ]
+  %cond.v = call i1 @cond()
+  br i1 %cond.v, label %if.then, label %while.end
+
+if.then:                                          ; preds = %while.cond
+  %start = add nsw i32 %cell.0, 1
+  br i1 %cond.v, label %for.cond11, label %for.cond26
+
+for.cond11:                                       ; preds = %for.cond11, %if.then
+  %i.1 = phi i32 [ %step, %for.cond11 ], [ %start, %if.then]
+  %cmp13 = icmp sle i32 %i.1, 99
+  %step = add nsw i32 %i.1, 1
+  br i1 %cmp13, label %for.cond11, label %while.end
+
+for.cond26:                                       ; preds = %if.then
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond, %for.cond11
+  ret void
+}
+