Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -1453,26 +1453,58 @@
             Opcode == Instruction::Mul) {
           Value *LL = LU->getOperand(0);
           Value *LR = LU->getOperand(1);
+          Value *NewL = nullptr;
           // Find a recurrence.
           if (LL == I)
-            L = LR;
+            NewL = LR;
           else if (LR == I)
-            L = LL;
-          else
+            NewL = LL;
+          if (NewL) {
+            // Ok, we have a PHI of the form L op= R. Check for low
+            // zero bits.
+            computeKnownBits(R, KnownZero2, KnownOne2, DL, Depth + 1, Q);
+
+            // We need to take the minimum number of known bits
+            APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
+            computeKnownBits(NewL, KnownZero3, KnownOne3, DL, Depth + 1, Q);
+
+            KnownZero = APInt::getLowBitsSet(
+                BitWidth, std::min(KnownZero2.countTrailingOnes(),
+                                   KnownZero3.countTrailingOnes()));
+          }
+        }
+        // Proving non-negativity is a useful fact. If the base is non-negative,
+        // look through a single-parent chain as far as possible to try and
+        // prove that this value is always non-negative.
+        if (isa<ConstantInt>(R) && !cast<ConstantInt>(R)->isNegative()) {
+          Value *V = L;
+          unsigned Countdown = 32;
+          while (Countdown--) {
+            Value *NewV, *Dummy;
+            ConstantInt *CI;
+            if (V == I) {
+              // We made it back to the PHI node, so this PHI is non-negative.
+              KnownZero.setBit(KnownZero.getBitWidth() - 1);
+              break;
+            }
+            if ((match(V, m_NSWAdd(m_Value(NewV), m_ConstantInt(CI))) ||
+                 match(V, m_NSWMul(m_Value(NewV), m_ConstantInt(CI)))) &&
+                !CI->isNegative()) {
+              V = NewV;
+              continue;
+            }
+            if ((match(V, m_Select(m_Value(Dummy), m_ConstantInt(CI),
+                                   m_Value(NewV))) ||
+                 match(V, m_Select(m_Value(Dummy), m_Value(NewV),
+                                   m_ConstantInt(CI)))) &&
+                !CI->isNegative()) {
+              V = NewV;
+              continue;
+            }
             break;
-          // Ok, we have a PHI of the form L op= R. Check for low
-          // zero bits.
-          computeKnownBits(R, KnownZero2, KnownOne2, DL, Depth + 1, Q);
-
-          // We need to take the minimum number of known bits
-          APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
-          computeKnownBits(L, KnownZero3, KnownOne3, DL, Depth + 1, Q);
-
-          KnownZero = APInt::getLowBitsSet(BitWidth,
-                                           std::min(KnownZero2.countTrailingOnes(),
-                                                    KnownZero3.countTrailingOnes()));
-          break;
+          }
         }
+        break;
       }
     }
 
Index: test/Analysis/ValueTracking/knownbits-phi.ll
===================================================================
--- /dev/null
+++ test/Analysis/ValueTracking/knownbits-phi.ll
@@ -0,0 +1,73 @@
+; RUN: opt -S -instsimplify < %s | FileCheck %s
+
+; CHECK-LABEL: @alwayspositive_loop1
+define i32 @alwayspositive_loop1(i32 %a) {
+entry:
+  br label %loop
+  
+loop:
+  %phi = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %c = add nsw i32 %phi, 2
+  %b = icmp sgt i32 %c, 52
+  %inc = add nsw i32 %c, 1
+  br i1 %b, label %exit, label %loop
+
+exit:
+; CHECK: ret i32 0
+  %d = lshr i32 %c, 31
+  ret i32 %d
+}
+
+; CHECK-LABEL: @alwayspositive_loop2
+define i32 @alwayspositive_loop2(i32 %a, i1 %cond) {
+entry:
+  br label %loop
+  
+loop:
+  %phi = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %c = select i1 %cond, i32 2, i32 %phi
+  %b = icmp sgt i32 %c, 52
+  %inc = add nsw i32 %c, 1
+  br i1 %b, label %exit, label %loop
+
+exit:
+; CHECK: ret i32 0
+  %d = lshr i32 %c, 31
+  ret i32 %d
+}
+
+; CHECK-LABEL: @alwayspositive_loop2_swapped
+define i32 @alwayspositive_loop2_swapped(i32 %a, i1 %cond) {
+entry:
+  br label %loop
+  
+loop:
+  %phi = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %c = select i1 %cond, i32 %phi, i32 2
+  %b = icmp sgt i32 %c, 52
+  %inc = add nsw i32 %c, 1
+  br i1 %b, label %exit, label %loop
+
+exit:
+; CHECK: ret i32 0
+  %d = lshr i32 %c, 31
+  ret i32 %d
+}
+
+; CHECK-LABEL: @alwayspositive_loop_mul
+define i32 @alwayspositive_loop_mul(i32 %a) {
+entry:
+  br label %loop
+  
+loop:
+  %phi = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %c = mul nsw i32 %phi, 3
+  %b = icmp sgt i32 %c, 52
+  %inc = add nsw i32 %c, 1
+  br i1 %b, label %exit, label %loop
+
+exit:
+; CHECK: ret i32 0
+  %d = lshr i32 %c, 31
+  ret i32 %d
+}