[DA] Fix assertion with loop exiting variables

[dmgreen]

Summary

Given code like:

for(i = ...)
  A[i] = 1;
A[i] = 2;

The scev for A[i]=2 is {A,+,4}<for>, even though it is outside the loop. This
can confuse DA into thinking it is in the loop, leading to it using a SIV test,
and asserting.

[dmgreen]

There may be a better way to fix this using getSCEVAtScope around line 3358, but my scev-fu isn't particularly strong and I'm still seeing asserts from it.

lib/Analysis/DependenceAnalysis.cpp

 
 // Examine the scev and return true iff it's linear.
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
                                        SmallBitVector &Loops) {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src);
   if (!AddRec)
     return isLoopInvariant(Src, LoopNest);
+  if (AddRec->getLoop()->getLoopDepth() >
+      (LoopNest ? LoopNest->getLoopDepth() : 0))
+    return false;
   const SCEV *Start = AddRec->getStart();
   const SCEV *Step = AddRec->getStepRecurrence(*SE);
   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
   if (!isa<SCEVCouldNotCompute>(UB)) {
     if (SE->getTypeSizeInBits(Start->getType()) <
         SE->getTypeSizeInBits(UB->getType())) {
       if (!AddRec->getNoWrapFlags())
         return false;

 
 // Examine the scev and return true iff it's linear.
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,
                                        SmallBitVector &Loops) {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst);
   if (!AddRec)
     return isLoopInvariant(Dst, LoopNest);
+  if (AddRec->getLoop()->getLoopDepth() >
+      (LoopNest ? LoopNest->getLoopDepth() : 0))
+    return false;
   const SCEV *Start = AddRec->getStart();
   const SCEV *Step = AddRec->getStepRecurrence(*SE);
   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
   if (!isa<SCEVCouldNotCompute>(UB)) {
     if (SE->getTypeSizeInBits(Start->getType()) <
         SE->getTypeSizeInBits(UB->getType())) {
       if (!AddRec->getNoWrapFlags())
         return false;

test/Analysis/DependenceAnalysis/LoopExitingIV.ll

+; RUN: opt < %s -da -analyze | FileCheck %s
+; Don't crash
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+; CHECK-LABEL: test
+define void @test(i32* nocapture %A, i32 %M) {
+; CHECK: da analyze - none!
+; CHECK: da analyze - output [|<]!
+; CHECK: da analyze - none!
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i
+  store i32 1, i32* %arrayidx, align 4
+  %inc = add nuw nsw i32 %i, 1
+  %exitcond = icmp eq i32 %inc, %M
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  %arrayidx1 = getelementptr inbounds i32, i32* %A, i32 %i
+  store i32 2, i32* %arrayidx1, align 4
+  ret void
+}
+
+; CHECK-LABEL: extraouterloop
+define void @extraouterloop(i32* nocapture %A, i32 %M) {
+; CHECK: da analyze - consistent output [S 0]!
+; CHECK: da analyze - output [*|<]!
+; CHECK: da analyze - output [*]!
+
+entry:
+  br label %for.outer
+
+for.outer:
+  %z = phi i32 [ 0, %entry ], [ %zinc, %for.end ]
+  br label %for.body
+
+for.body:
+  %i = phi i32 [ %inc, %for.body ], [ 0, %for.outer ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i
+  store i32 1, i32* %arrayidx, align 4
+  %inc = add nuw nsw i32 %i, 1
+  %exitcond = icmp eq i32 %inc, %M
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  %arrayidx1 = getelementptr inbounds i32, i32* %A, i32 %i
+  store i32 2, i32* %arrayidx1, align 4
+  %zinc = add i32 %z, 1
+  %zcmp = icmp ult i32 %zinc, 100
+  br i1 %zcmp, label %for.outer, label %exit
+
+exit:
+  ret void
+}