[DA] Delinearise AddRecs if we can prove they don't wrap

[dmgreen]

Summary

We can prove that some delinearized subscripts do not wrap around to become
negative by the fact that they are from inbound geps of load/store locations.
This helps improve the delinearisation in cases where we can't prove that they
are non-negative from SCEV alone.

[sebpop]

Looks good, please commit. Thanks!

[dmgreen]

Cheers!

llvm/trunk/include/llvm/Analysis/DependenceAnalysis.h

bool isKnownPredicate(ICmpInst::Predicate Pred,
                           const SCEV *Y) const;
 
     /// isKnownLessThan - Compare to see if S is less than Size
     /// Another wrapper for isKnownNegative(S - max(Size, 1)) with some extra
     /// checking if S is an AddRec and we can prove lessthan using the loop
     /// 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.
     /// (I zero extend since the bound should always be >= 0.)
     /// If no upper bound is available, return NULL.
     const SCEV *collectUpperBound(const Loop *l, Type *T) const;
 
     /// collectConstantUpperBound - Calls collectUpperBound(), then

llvm/trunk/lib/Analysis/DependenceAnalysis.cpp

bool DependenceInfo::isKnownLessThan(const SCEV *S, const SCEV *Size) const {
   }
 
   // Check using normal isKnownNegative
   const SCEV *LimitedBound =
       SE->getMinusSCEV(S, SE->getSMaxExpr(Size, SE->getOne(Size->getType())));
   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.
 // This routine collects upper bound and extends or truncates if needed.
 // Truncating is safe when subscripts are known not to wrap. Cases without
 // nowrap flags should have been rejected earlier.
 // Return null if no bound available.
 const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const {
bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
 
   // Statically check that the array bounds are in-range. The first subscript we
   // don't have a size for and it cannot overflow into another subscript, so is
   // always safe. The others need to be 0 <= subscript[i] < bound, for both src
   // and dst.
   // 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]))
       return false;
   }
 
   LLVM_DEBUG({
     dbgs() << "\nSrcSubscripts: ";

llvm/trunk/test/Analysis/DependenceAnalysis/DADelin.ll

 for.inc10:                                        ; preds = %for.body5, %for.body
   %indvars.iv.next33 = add nuw nsw i32 %indvars.iv32, 1
   %indvars.iv.next = add i16 %indvars.iv, %0
   %exitcond34 = icmp eq i32 %indvars.iv.next33, %wide.trip.count
   br i1 %exitcond34, label %for.end12, label %for.body
 
 for.end12:                                        ; preds = %for.inc10, %entry
   ret double undef
-}
+}
+
+
+; 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
+}