Index: llvm/trunk/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/trunk/lib/Analysis/ValueTracking.cpp
+++ llvm/trunk/lib/Analysis/ValueTracking.cpp
@@ -1240,6 +1240,18 @@
           KnownZero = APInt::getLowBitsSet(BitWidth,
                                            std::min(KnownZero2.countTrailingOnes(),
                                                     KnownZero3.countTrailingOnes()));
+
+          // If the operation is an addition that can't have signed overflow,
+          // then the sign bit is known to be zero if both input sign bits
+          // are zero. Similar for two negative inputs.
+          if (Opcode == Instruction::Add &&
+              cast<OverflowingBinaryOperator>(LU)->hasNoSignedWrap()) {
+            if (KnownZero2.isNegative() && KnownZero3.isNegative())
+              KnownZero.setBit(BitWidth-1);
+            if (KnownOne2.isNegative() && KnownOne3.isNegative())
+              KnownOne.setBit(BitWidth-1);
+          }
+
           break;
         }
       }
Index: llvm/trunk/test/Transforms/BBVectorize/loop1.ll
===================================================================
--- llvm/trunk/test/Transforms/BBVectorize/loop1.ll
+++ llvm/trunk/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
Index: llvm/trunk/test/Transforms/InstCombine/phi.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/phi.ll
+++ llvm/trunk/test/Transforms/InstCombine/phi.ll
@@ -879,3 +879,118 @@
   %cmp1 = icmp ne i32 %a.0, 0
   ret i1  %cmp1
 }
+
+
+; This test makes sure we can determine that the inputs to the sdiv in the loop
+; are non-negative and can become a udiv. This requires that we recognize that
+; the loop induction can never have its sign bit set.
+;
+; CHECK-LABEL: @phi_nsw_induction_sdiv_udiv
+; CHECK: udiv
+; CHECK: udiv
+define i32 @phi_nsw_induction_sdiv_udiv(i32 %NumElts, i32 %ScalarSize) {
+entry:
+  %div = udiv i32 128, %ScalarSize
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %Sum.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp ne i32 %i.0, %NumElts
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  ; this should become a udiv
+  %div1 = sdiv i32 %i.0, %div
+  %add = add nsw i32 %Sum.0, %div1
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 %Sum.0
+}
+
+
+; CHECK-LABEL: test_positive_nsw_recurrence
+; CHECK-NOT: bar
+; CHECK: foo
+; CHECK-NOT: bar
+; CHECK: ret
+define void @test_positive_nsw_recurrence(i32 %N) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp ne i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %and = and i32 %i.0, -2147483648
+  %tobool = icmp ne i32 %and, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  ; this call should be deleted as %i.0 can never be negative due to no signed wrap
+  call void @bar()
+  br label %if.end
+
+if.else:                                          ; preds = %for.body
+  call void @foo()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+; CHECK-LABEL: test_negative_nsw_recurrence
+; CHECK-NOT: foo
+; CHECK: bar
+; CHECK-NOT: foo
+; CHECK: ret
+define void @test_negative_nsw_recurrence(i32 %N) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ -1, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp ne i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %and = and i32 %i.0, -2147483648
+  %tobool = icmp ne i32 %and, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  call void @bar()
+  br label %if.end
+
+if.else:                                          ; preds = %for.body
+  ; this call should be deleted as %i.0 can never be positive due to no signed wrap
+  call void @foo()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %inc = add nsw i32 %i.0, -1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @bar()
+declare void @foo()