Index: llvm/trunk/include/llvm/Analysis/DependenceAnalysis.h
===================================================================
--- llvm/trunk/include/llvm/Analysis/DependenceAnalysis.h
+++ llvm/trunk/include/llvm/Analysis/DependenceAnalysis.h
@@ -563,6 +563,11 @@
     /// bounds.
     bool isKnownLessThan(const SCEV *S, const SCEV *Size) const;
 
+    /// isKnownNonNegative - Compare to see if S is known not to be negative
+    /// Uses the fact that S comes from Ptr, which may be an inbound GEP,
+    /// Proving there is no wrapping going on.
+    bool isKnownNonNegative(const SCEV *S, const Value *Ptr) const;
+
     /// collectUpperBound - All subscripts are the same type (on my machine,
     /// an i64). The loop bound may be a smaller type. collectUpperBound
     /// find the bound, if available, and zero extends it to the Type T.
Index: llvm/trunk/lib/Analysis/DependenceAnalysis.cpp
===================================================================
--- llvm/trunk/lib/Analysis/DependenceAnalysis.cpp
+++ llvm/trunk/lib/Analysis/DependenceAnalysis.cpp
@@ -1027,6 +1027,25 @@
   return SE->isKnownNegative(LimitedBound);
 }
 
+bool DependenceInfo::isKnownNonNegative(const SCEV *S, const Value *Ptr) const {
+  bool Inbounds = false;
+  if (auto *SrcGEP = dyn_cast<GetElementPtrInst>(Ptr))
+    Inbounds = SrcGEP->isInBounds();
+  if (Inbounds) {
+    if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
+      if (AddRec->isAffine()) {
+        // We know S is for Ptr, the operand on a load/store, so doesn't wrap.
+        // If both parts are NonNegative, the end result will be NonNegative
+        if (SE->isKnownNonNegative(AddRec->getStart()) &&
+            SE->isKnownNonNegative(AddRec->getOperand(1)))
+          return true;
+      }
+    }
+  }
+
+  return SE->isKnownNonNegative(S);
+}
+
 // All subscripts are all the same type.
 // Loop bound may be smaller (e.g., a char).
 // Should zero extend loop bound, since it's always >= 0.
@@ -3292,13 +3311,13 @@
   // FIXME: It may be better to record these sizes and add them as constraints
   // to the dependency checks.
   for (int i = 1; i < size; ++i) {
-    if (!SE->isKnownNonNegative(SrcSubscripts[i]))
+    if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
       return false;
 
     if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
       return false;
 
-    if (!SE->isKnownNonNegative(DstSubscripts[i]))
+    if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
       return false;
 
     if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
Index: llvm/trunk/test/Analysis/DependenceAnalysis/DADelin.ll
===================================================================
--- llvm/trunk/test/Analysis/DependenceAnalysis/DADelin.ll
+++ llvm/trunk/test/Analysis/DependenceAnalysis/DADelin.ll
@@ -553,4 +553,38 @@
 
 for.end12:                                        ; preds = %for.inc10, %entry
   ret double undef
-}
\ No newline at end of file
+}
+
+
+; CHECK-LABEL: nonnegative
+define void @nonnegative(i32* nocapture %A, i32 %N) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - consistent output [0 0|<]!
+; CHECK: da analyze - none!
+entry:
+  %cmp44 = icmp eq i32 %N, 0
+  br i1 %cmp44, label %exit, label %for.outer
+
+for.outer:
+  %h.045 = phi i32 [ %add19, %for.latch ], [ 0, %entry ]
+  %mul = mul i32 %h.045, %N
+  br label %for.inner
+
+for.inner:
+  %i.043 = phi i32 [ 0, %for.outer ], [ %add16, %for.inner ]
+  %add = add i32 %i.043, %mul
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
+  store i32 1, i32* %arrayidx, align 4
+  store i32 2, i32* %arrayidx, align 4
+  %add16 = add nuw i32 %i.043, 1
+  %exitcond46 = icmp eq i32 %add16, %N
+  br i1 %exitcond46, label %for.latch, label %for.inner
+
+for.latch:
+  %add19 = add nuw i32 %h.045, 1
+  %exitcond47 = icmp eq i32 %add19, %N
+  br i1 %exitcond47, label %exit, label %for.outer
+
+exit:
+  ret void
+}