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; // Check for recurrence with L and R flipped.
           // 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
--- a/llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll
+++ b/llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll
@@ -19,8 +19,8 @@
 ; CHECK-NEXT:    br i1 [[COND_V]], label [[FOR_COND11:%.*]], label [[FOR_COND26]]
 ; CHECK:       for.cond11:
 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[START]], [[IF_THEN]] ], [ [[STEP:%.*]], [[FOR_COND11]] ]
-; CHECK-NEXT:    [[CMP13:%.*]] = icmp slt i32 [[I_1]], 100
-; CHECK-NEXT:    [[STEP]] = add nsw i32 [[I_1]], 1
+; CHECK-NEXT:    [[CMP13:%.*]] = icmp ult i32 [[I_1]], 100
+; CHECK-NEXT:    [[STEP]] = add nuw nsw i32 [[I_1]], 1
 ; CHECK-NEXT:    br i1 [[CMP13]], label [[FOR_COND11]], label [[WHILE_END]]
 ; CHECK:       for.cond26:
 ; CHECK-NEXT:    br label [[WHILE_COND]]