Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -799,6 +799,26 @@
   }
 }
 
+// Compute known sign bit from a shift operator, based on the known sign bit of
+// its first operand and the nsw flag. KnownZero2 and KnownOne2 are the computed
+// known bits of its first operand.
+static void computeKnownSignBitFromShift(Operator *I, 
+                                         APInt &KnownZero, APInt &KnownOne,
+                                         APInt &KnownZero2, APInt &KnownOne2) {
+  // If this is a left shift with nsw, then the shift produces a poison value
+  // if it shifts out any bits that disagree with the resultant sign bit.
+  // This means the result is either a poison value or has the same sign bit 
+  // as the first operand.
+  unsigned BitWidth = KnownZero.getBitWidth();
+  if (I->getOpcode() == Instruction::Shl && 
+      cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap()) {
+    if (KnownZero2.isNegative())
+        KnownZero |= APInt::getSignBit(BitWidth);
+    if (KnownOne2.isNegative())
+        KnownOne |= APInt::getSignBit(BitWidth);
+  }
+}
+
 // Compute known bits from a shift operator, including those with a
 // non-constant shift amount. KnownZero and KnownOne are the outputs of this
 // function. KnownZero2 and KnownOne2 are pre-allocated temporaries with the
@@ -817,9 +837,12 @@
   if (auto *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
     unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1);
 
-    computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
-    KnownZero = KZF(KnownZero, ShiftAmt);
-    KnownOne  = KOF(KnownOne, ShiftAmt);
+    computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
+    KnownZero = KZF(KnownZero2, ShiftAmt);
+    KnownOne  = KOF(KnownOne2, ShiftAmt);
+    
+    computeKnownSignBitFromShift(I, KnownZero, KnownOne, KnownZero2, KnownOne2);
+    
     return;
   }
 
@@ -874,6 +897,8 @@
     KnownOne  &= KOF(KnownOne2, ShiftAmt);
   }
 
+  computeKnownSignBitFromShift(I, KnownZero, KnownOne, KnownZero2, KnownOne2);
+
   // If there are no compatible shift amounts, then we've proven that the shift
   // amount must be >= the BitWidth, and the result is undefined. We could
   // return anything we'd like, but we need to make sure the sets of known bits
@@ -1259,7 +1284,25 @@
 
           KnownZero = APInt::getLowBitsSet(BitWidth,
                                            std::min(KnownZero2.countTrailingOnes(),
-                                                    KnownZero3.countTrailingOnes()));
+                                             KnownZero3.countTrailingOnes()));
+
+          auto OverflowOp = dyn_cast<OverflowingBinaryOperator>(LU);
+          if (OverflowOp && OverflowOp->hasNoSignedWrap()) {
+            // Initial value of recurrence is nonnegative, and we are adding a
+            // nonnegative number with nsw. The result can only be nonnegative
+            // or poison value regardless of the number of times we execute the 
+            // add in phi recurrence. Same argument applies for mul with 
+            // non-negative operands and sub with non-negative LHS and negative
+            // RHS.
+            if ((Opcode == Instruction::Add || Opcode == Instruction::Mul) &&
+                KnownZero3.isNegative() && KnownZero2.isNegative())
+              KnownZero |= APInt::getSignBit(BitWidth);
+
+            if (Opcode == Instruction::Sub && KnownZero3.isNegative() && 
+                KnownOne2.isNegative())
+              KnownZero |= APInt::getSignBit(BitWidth);
+          }
+
           break;
         }
       }
Index: test/Analysis/ValueTracking/known-non-negative.ll
===================================================================
--- test/Analysis/ValueTracking/known-non-negative.ll
+++ test/Analysis/ValueTracking/known-non-negative.ll
@@ -0,0 +1,29 @@
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; Induction variable is known to be non-negative
+define i32 @test_indvar_nonnegative() {
+; CHECK-LABEL: @test_indvar_nonnegative(
+; CHECK: br i1 true, label %for.end, label %for.body
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [0, %entry], [%inc, %for.body]
+  %inc = add nsw i32 %i, 1
+  %cmp = icmp sge i32 %i, 0
+  br i1 %cmp, label %for.end, label %for.body
+
+for.end:
+  ret i32 %i
+}
+
+; Result of left shifting a non-negative integer 
+; with nsw flag should also be non-negative
+define i1 @test_shift_nonnegative(i32 %a) {
+; CHECK-LABEL: @test_shift_nonnegative(
+; CHECK: ret i1 true
+  %b = lshr i32 %a, 2
+  %shift = shl nsw i32 %b, 3
+  %cmp = icmp sge i32 %shift, 0
+  ret i1 %cmp
+}
Index: test/Transforms/BBVectorize/loop1.ll
===================================================================
--- test/Transforms/BBVectorize/loop1.ll
+++ test/Transforms/BBVectorize/loop1.ll
@@ -83,7 +83,7 @@
 ; CHECK-UNRL: %add12 = fadd <2 x double> %add7, %mul11
 ; CHECK-UNRL: %4 = bitcast double* %arrayidx14 to <2 x double>*
 ; CHECK-UNRL: store <2 x double> %add12, <2 x double>* %4, align 8
-; CHECK-UNRL: %indvars.iv.next.1 = add nsw i64 %indvars.iv, 2
+; CHECK-UNRL: %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv, 2
 ; CHECK-UNRL: %lftr.wideiv.1 = trunc i64 %indvars.iv.next.1 to i32
 ; CHECK-UNRL: %exitcond.1 = icmp eq i32 %lftr.wideiv.1, 10
 ; CHECK-UNRL: br i1 %exitcond.1, label %for.end, label %for.body