[DA] Use SCEV to conclude DVEntry::EQ in some cases.

[fhahn]

Summary

This is a very naive approach to conclude that both accesses to Arr1 in the
loop below access the same memory location.

void foo(unsigned **Arr1) {
  for (int i = 0; i < 1024; ++i)
    for(int j = 0; j < 1024; ++j)
      Arr1[j][i] = Arr1[j][i] 10;
}

By using SCEV, we can conclude that both accesses to Arr1 access the
same location in each loop iteration. I am probably missing something,
but this seems to work for loop variant accesses in the same loop.

It would be great if you could have a look and let me know what I am
missing :)

For SPEC2006 and the test-suite with LTO, this triggers in around 1100
cases. It also helps LoopInterchange to interchange a few more loops.

[tvvikram]

lib/Analysis/DependenceAnalysis.cpp

3707

Even I am facing a similar issue. What happens if the access is something like A[(i + j) * n] = A[(i + j) * n] + 10, where n can be 0. In this case, the dependence would be "*" and not "=" right? Maybe just checking if difference is zero wouldn't be enough but traversing the SCEV to see that it is simple/understandable would be necessary.

[fhahn]

lib/Analysis/DependenceAnalysis.cpp

3707

Right, thanks for having a look! isLoopInvariant is not enough, looks like we need something like "may be loop invariant" :) I'll update the patch.

[fhahn]

Added IsNotLoopInvariant helper to make sure the expressions we are comparing are not loop invariant, to avoid deducing EQ for scalar dependencies.

[philip.pfaffe]

This does not look correct. Consider the AA.ll testcase. Your change makes DA claim there is no output dependency on the load in %for.inner, but there is! Carried over the outer loop. So the result should be input[* =] (don't quote me on the syntax though).

[fhahn]

In D46201#1123382, @philip.pfaffe wrote:

This does not look correct. Consider the AA.ll testcase. Your change makes DA claim there is no output dependency on the load in %for.inner, but there is! Carried over the outer loop. So the result should be input[* =] (don't quote me on the syntax though).

Right, we should only set EQ for levels that with induction variables involved. I will update the patch

lib/Analysis/DependenceAnalysis.cpp

 STATISTIC(DeltaIndependence, "Delta independence");
 STATISTIC(DeltaPropagations, "Delta propagations");
 STATISTIC(GCDapplications, "GCD applications");
 STATISTIC(GCDsuccesses, "GCD successes");
 STATISTIC(GCDindependence, "GCD independence");
 STATISTIC(BanerjeeApplications, "Banerjee applications");
 STATISTIC(BanerjeeIndependence, "Banerjee independence");
 STATISTIC(BanerjeeSuccesses, "Banerjee successes");
+STATISTIC(SymbolicEQSuccesses, "Symbolic EQ successes");
 
 static cl::opt<bool>
 Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore,
             cl::desc("Try to delinearize array references."));
 
 //===----------------------------------------------------------------------===//
 // basics
 
for (unsigned VI : BV.set_bits()) {
     dbgs() << VI;
     if (BV.find_next(VI) >= 0)
       dbgs() << ' ';
   }
   dbgs() << "}\n";
 }
 #endif
 
+// Returns true if expression S is proven to be not loop invariant in loop
+// L. This stronger than just checking !SE->isLoopInvariant(), as
+// isLoopInvariant only returns true if the expression can be proven to be
+// loop invariant, but there are loop invariant expression that isLoopInvariant
+// might not be able to prove.
+static bool IsNotLoopInvariant(const SCEV *S, const Loop *L,
+                               ScalarEvolution *SE) {
+  switch (static_cast<SCEVTypes>(S->getSCEVType())) {
+  case scConstant:
+    return false;
+  case scTruncate:
+  case scZeroExtend:
+  case scSignExtend:
+    return IsNotLoopInvariant(cast<SCEVCastExpr>(S)->getOperand(), L, SE);
+  case scAddRecExpr: {
+    const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
+    // If L is the addrec's loop and it has a non-zero step, it is not loop
+    // invariant.
+    if (AR->getLoop() == L)
+      return SE->isKnownNonZero(AR->getStepRecurrence(*SE));
+    return false;
+  }
+  case scAddExpr:
+    // AddExpr are not loop invariant if any of the terms is not loop invariant.
+    return any_of(cast<SCEVNAryExpr>(S)->operands(), [L, SE](const SCEV *S) {
+      return IsNotLoopInvariant(S, L, SE);
+    });
+  case scMulExpr: {
+    // MulExpr is are not loop invariant if any of the terms is not loop
+    // invariant and we do not multiply with 0.
+    bool AnyNotInvariant = false;
+    bool AllInvariantNonZero = true;
+    for (const SCEV *Op : cast<SCEVNAryExpr>(S)->operands()) {
+      bool NotInvariant = IsNotLoopInvariant(Op, L, SE);
+      AnyNotInvariant |= NotInvariant;
+      AllInvariantNonZero &= NotInvariant || SE->isKnownNonZero(Op);
+    }
+
+    return AllInvariantNonZero && AnyNotInvariant;
+  }
+  default:
+    return false;
+  }
+}
+
 // depends -
 // Returns NULL if there is no dependence.
 // Otherwise, return a Dependence with as many details as possible.
 // Corresponds to Section 3.1 in the paper
 //
 //            Practical Dependence Testing
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
for (unsigned SI : Coupled.set_bits()) {
           break;
         updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
         if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
           return nullptr;
       }
     }
   }
 
+  // Try to conclude DVEntry::EQ, in case Src and Dst access the same memory
+  // location for loop dependent locations in the same loop.
+  Loop *SrcL = LI->getLoopFor(Src->getParent());
+  Loop *DstL = LI->getLoopFor(Dst->getParent());
+  if (SrcL == DstL && IsNotLoopInvariant(SrcSCEV, SrcL, SE) &&
+      IsNotLoopInvariant(DstSCEV, DstL, SE)) {
+    const SCEV *DiffSCEV = SE->getMinusSCEV(SrcSCEV, DstSCEV);
+    if (DiffSCEV->isZero()) {
+      for (unsigned i = 0; i < Result.Levels; i++)
+        Result.DV[i].Direction = Dependence::DVEntry::EQ;
+      SymbolicEQSuccesses++;
+    }
+  }
+
   // Make sure the Scalar flags are set correctly.
   SmallBitVector CompleteLoops(MaxLevels + 1);
   for (unsigned SI = 0; SI < Pairs; ++SI)
     CompleteLoops |= Pair[SI].Loops;
   for (unsigned II = 1; II <= CommonLevels; ++II)
     if (CompleteLoops[II])
       Result.DV[II - 1].Scalar = false;
 

test/Analysis/DependenceAnalysis/AA.ll

 ; CHECK: da analyze - none!
 define void @test_tbaa_diff(i32* %A, i16* %B) {
   store i32 1, i32* %A, !tbaa !5
   store i16 2, i16* %B, !tbaa !9
   ret void
 }
 
 ; CHECK-LABEL: tbaa_loop
-; CHECK: da analyze - input
-; CHECK: da analyze - none
-; CHECK: da analyze - output
+; CHECK: da analyze - none!
+; CHECK: da analyze - none!
+; CHECK: da analyze - none!
 define void @tbaa_loop(i32 %I, i32 %J, i32* nocapture %A, i16* nocapture readonly %B) {
 entry:
   %cmp = icmp ne i32 %J, 0
   %cmp122 = icmp ne i32 %I, 0
   %or.cond = and i1 %cmp, %cmp122
   br i1 %or.cond, label %for.outer.preheader, label %for.end
 
 for.outer.preheader:

test/Analysis/DependenceAnalysis/Banerjee.ll

 ;;      *B++ = A[10*i + j - 1];
 
 define void @banerjee1(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 entry:
   %cmp4 = icmp sgt i64 %n, 0
   br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end9
 
 ; CHECK: 'Dependence Analysis' for function 'banerjee1':
-; CHECK: da analyze - output [* *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [* <>]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [* *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - output [* *]!
+; CHECK: da analyze - none!
 
 ; DELIN: 'Dependence Analysis' for function 'banerjee1':
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [* <>]!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   %0 = add i64 %n, 1
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc7
   %B.addr.06 = phi i64* [ %B.addr.1.lcssa, %for.inc7 ], [ %B, %for.cond1.preheader.preheader ]
   %i.05 = phi i64 [ %inc8, %for.inc7 ], [ 1, %for.cond1.preheader.preheader ]

 ;;      A[30*i + 500*j] = 0;
 ;;      *B++ = A[i - 500*j + 11];
 
 define void @banerjee9(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; CHECK: 'Dependence Analysis' for function 'banerjee9':
-; CHECK: da analyze - output [* *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [<= =|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 ; DELIN: 'Dependence Analysis' for function 'banerjee9':
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [<= =|<]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc8
   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]

test/Analysis/DependenceAnalysis/GCD.ll

 ;;      A[2*i - 4*j] = i;
 ;;      *B++ = A[6*i + 8*j];
 
 define void @gcd0(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; DELIN-LABEL: gcd0
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [=> *|<]!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc8
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc8 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
   br label %for.body3
 

 ;;      A[2*i - 4*j] = i;
 ;;      *B++ = A[6*i + 8*j + 1];
 
 define void @gcd1(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; DELIN-LABEL: gcd1
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc9
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ]
   br label %for.body3
 

 ;;      A[2*i - 4*j + 1] = i;
 ;;      *B++ = A[6*i + 8*j];
 
 define void @gcd2(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; DELIN-LABEL: gcd2
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc9
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ]
   br label %for.body3
 

 ;;      A[i + 2*j] = i;
 ;;      *B++ = A[i + 2*j - 1];
 
 define void @gcd3(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; DELIN-LABEL: gcd3
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [<> *]!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc7
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc7 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
   br label %for.body3
 
entry:
   br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end12
 
 ; DELIN-LABEL: gcd6
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc10
   %i.06 = phi i64 [ %inc11, %for.inc10 ], [ 0, %for.cond1.preheader.preheader ]
   %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc10 ], [ %B, %for.cond1.preheader.preheader ]
   %cmp21 = icmp sgt i64 %n, 0

 
 define void @gcd7(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   %0 = zext i32 %n to i64
   %cmp4 = icmp sgt i32 %n, 0
   br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15
 
 ; DELIN-LABEL: gcd7
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [* *|<]!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc13
   %indvars.iv8 = phi i64 [ 0, %for.cond1.preheader.preheader ], [ %indvars.iv.next9, %for.inc13 ]
   %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
   %1 = add i32 %n, -1

 ;;      *B++ = A[n*8*i + 6*j + 1];
 
 define void @gcd8(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   %cmp4 = icmp sgt i32 %n, 0
   br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15
 
 ; DELIN-LABEL: gcd8
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [* *|<]!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc13
   %i.06 = phi i32 [ %inc14, %for.inc13 ], [ 0, %for.cond1.preheader.preheader ]
   %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
   %0 = add i32 %n, -1

 
 define void @gcd9(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   %0 = zext i32 %n to i64
   %cmp4 = icmp eq i32 %n, 0
   br i1 %cmp4, label %for.end15, label %for.cond1.preheader.preheader
 
 ; DELIN-LABEL: gcd9
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [* *|<]!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc13
   %indvars.iv8 = phi i64 [ 0, %for.cond1.preheader.preheader ], [ %indvars.iv.next9, %for.inc13 ]
   %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
   %1 = add i32 %n, -1

test/Analysis/DependenceAnalysis/Invariant.ll

 ; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
 
 ; Test for a bug, which caused an assert when an invalid
 ; SCEVAddRecExpr is created in addToCoefficient.
 
 ; CHECK-LABEL: foo
-; CHECK: da analyze - consistent input [S 0]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - input [* *|<]!
 ; CHECK: da analyze - none!
 
 define float @foo(float %g, [40 x float]* %rr) nounwind {
 entry:
   br label %for.cond1.preheader
 
 for.cond1.preheader:

test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll

 @a = global [10004 x [10004 x i32]] zeroinitializer, align 16
 
 ; Function Attrs: nounwind uwtable
 define void @coupled_miv_type_mismatch(i32 %n) #0 {
 ; DELIN-LABEL: 'Dependence Analysis' for function 'coupled_miv_type_mismatch'
 entry:
   br label %for.cond
 
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - anti [* *|<]!
 ; DELIN: da analyze - none!
 for.cond:                                         ; preds = %for.inc11, %entry
   %indvars.iv11 = phi i64 [ %indvars.iv.next12, %for.inc11 ], [ 1, %entry ]
   %exitcond14 = icmp ne i64 %indvars.iv11, 10000
   br i1 %exitcond14, label %for.cond1.preheader, label %for.end13
 
 for.cond1.preheader:                              ; preds = %for.cond

test/Analysis/DependenceAnalysis/PR21585.ll

for.body:
   %exitcond = icmp ne i64 %i.inc.ext, 100
   br i1 %exitcond, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 ; CHECK: none
 ; CHECK: anti
-; CHECK: output
+; CHECK: da analyze - consistent output [S]!
 
 
 ; Test for a bug, which caused an assert in ScalarEvolution because
 ; the Dependence Analyzer attempted to zero extend a type to a smaller
 ; type.
 
 ; void t(unsigned int *a, unsigned int n) {
 ;   for (unsigned int i = 0; i != n; i++) {
for.body:
   store i32 %0, i32* %arrayidx, align 4
   %inc = add i32 %i.02, 1
   %cmp = icmp eq i32 %inc, %n
   br i1 %cmp, label %for.end, label %for.body
 
 for.end:
   ret void
 }
-; CHECK: input
+; CHECK: da analyze - consistent input [S]!
+; CHECK: none
 ; CHECK: none
-; CHECK: output
 
 define void @i16_wrap(i64* %a) {
 entry:
   br label %for.body
 for.body:
   %i = phi i64 [0, %entry], [%i.inc, %for.inc]
   %i.tr = trunc i64 %i to i16
   %idx = getelementptr i64, i64* %a, i16 %i.tr
   %0 = load i64, i64* %idx
   %1 = add i64 %0, 1
 store i64 %1, i64* %idx
   br label %for.inc
 
 for.inc:
   %i.inc = add nuw i64 %i, 1
   %cmp = icmp ult i64 %i.inc, 17179869184
   br i1 %cmp, label %for.body, label %for.end
 for.end:
   ret void
 }
-; CHECK: input
+; CHECK: none
 ; CHECK: anti
-; CHECK: output
+; CHECK: none
 
 define void @i8_stride_wrap(i32* noalias %a, i32* noalias %b) {
 entry:
   br label %for.body
 for.body:
   %i = phi i32 [1,%entry], [%i.inc, %for.inc]
   %i.tr = trunc i32 %i to i8
   %idx = getelementptr i32, i32* %a, i8 %i.tr
   %idx.2 = getelementptr i32, i32* %b, i32 %i
   %0 = load i32, i32* %idx, align 4
   %1 = add i32 %0, 1
   store i32 %1, i32* %idx.2, align 4
   br label %for.inc
 
 for.inc:
   %i.inc = add nsw i32 %i, 256
   %exitcond = icmp ult i32 %i, 65536
   br i1 %exitcond, label %for.body, label %for.end
 
 for.end:
   ret void
 }
-; CHECK: input
+; CHECK: da analyze - consistent input [S]!
 ; CHECK: none
 ; CHECK: none

test/Analysis/DependenceAnalysis/Preliminary.ll

 ;;        *B++ = A[i + 3][j + 2][k + 1];
 
 define void @p2(i64 %n, [100 x [100 x i64]]* %A, i64* %B) nounwind uwtable ssp {
 entry:
   %cmp10 = icmp sgt i64 %n, 0
   br i1 %cmp10, label %for.cond1.preheader.preheader, label %for.end26
 
 ; CHECK-LABEL: p2
-; CHECK: da analyze - output [* * *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [* *|<]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [* * *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - output [* * *]!
+; CHECK: da analyze - none!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc24
   %B.addr.012 = phi i64* [ %B.addr.1.lcssa, %for.inc24 ], [ %B, %for.cond1.preheader.preheader ]
   %i.011 = phi i64 [ %inc25, %for.inc24 ], [ 0, %for.cond1.preheader.preheader ]
   %cmp26 = icmp sgt i64 %n, 0

 ;;    *B++ = A[i];
 
 define void @p4(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 entry:
   %cmp1 = icmp sgt i64 %n, 0
   br i1 %cmp1, label %for.body.preheader, label %for.end
 
 ; CHECK-LABEL: p4
-; CHECK: da analyze - output [*]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [*|<]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [*]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.body
   %i.03 = phi i8 [ %inc, %for.body ], [ 0, %for.body.preheader ]

 ;;    *B++ = A[i];
 
 define void @p5(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 entry:
   %cmp1 = icmp sgt i64 %n, 0
   br i1 %cmp1, label %for.body.preheader, label %for.end
 
 ; CHECK-LABEL: p5
-; CHECK: da analyze - output [*]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [*|<]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [*]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.body
   %i.03 = phi i16 [ %inc, %for.body ], [ 0, %for.body.preheader ]

test/Analysis/DependenceAnalysis/Propagating.ll

 ;;        A[j - i][i + 1][j + k] = i;
 ;;        *B++ = A[j - i][i][j + k];
 
 define void @prop1([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; CHECK-LABEL: prop1
-; CHECK: da analyze - output [* * *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [<> <> *]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [* * *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc18
   %B.addr.06 = phi i32* [ %B, %entry ], [ %scevgep7, %for.inc18 ]
   %i.05 = phi i64 [ 0, %entry ], [ %inc19, %for.inc18 ]
   br label %for.cond4.preheader
 

 ;;      A[i][2*j + i] = i;
 ;;      *B++ = A[i][2*j - i + 5];
 
 define void @prop3([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; CHECK-LABEL: prop3
-; CHECK: da analyze - output [* *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [<> *]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [* *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc9
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ]
   br label %for.body3
 

 ;;      A[4][j + 2] = i;
 ;;      *B++ = A[-2*i + 4][5*i + j];
 
 define void @prop8([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; CHECK-LABEL: prop8
-; CHECK: da analyze - consistent output [S 0]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [=> <]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc10
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc10 ]

 define void @prop9([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; CHECK-LABEL: prop9
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [<= <]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - consistent input [S 0]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc10
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc10 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc11, %for.inc10 ]
   br label %for.body3
 

test/Analysis/DependenceAnalysis/Separability.ll

 
 define void @sep0([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; CHECK: da analyze - output [= * * S]!
 ; CHECK: da analyze - flow [* * * *|<]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [* * S *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc22
   %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc22 ]
   %i.07 = phi i64 [ 0, %entry ], [ %inc23, %for.inc22 ]
   br label %for.cond4.preheader
 

 
 define void @sep1([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
 ; CHECK: da analyze - output [= * * S]!
 ; CHECK: da analyze - flow [* * * *|<]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [* * S *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc22
   %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc22 ]
   %i.07 = phi i64 [ 0, %entry ], [ %inc23, %for.inc22 ]
   br label %for.cond4.preheader
 

 ;;        for (long int l = 0; l < 50; l++) {
 ;;          A[i][i][i + k][l] = i;
 ;;          *B++ = A[10][i + 10][j + k][l + 10];
 
 define void @sep2([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
-; CHECK: da analyze - output [= S = =]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [* * * <>]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [= * * *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc26
   %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc26 ]
   %i.07 = phi i64 [ 0, %entry ], [ %inc27, %for.inc26 ]
   br label %for.cond4.preheader
 

 ;;        for (long int l = 0; l < 50; l++) {
 ;;          A[i][i][i + k][l + k] = i;
 ;;          *B++ = A[10][i + 10][j + k][l + 10];
 
 define void @sep3([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 
-; CHECK: da analyze - output [= S = =]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [* * * *|<]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - input [= * * *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc27
   %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc27 ]
   %i.07 = phi i64 [ 0, %entry ], [ %inc28, %for.inc27 ]
   br label %for.cond4.preheader
 

test/Analysis/DependenceAnalysis/Symbolic.ll

+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
+
+; void no_deps_interchange(unsigned **Arr) {
+;   for (int i = 0; i < 1024; ++i)
+;     for(int j = 0; j < 1024; ++j)
+;       Arr[j][i] += Arr[j][i] + 10;
+; }
+; CHECK-LABEL: 'Dependence Analysis' for function 'test1'
+; CHECK: da analyze - none!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - input [* *]!
+; CHECK: da analyze - anti [* *|<]!
+; CHECK: da analyze - output [* *]!
+
+define void @test1(i64** %Arr) {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %entry
+  %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.cond.cleanup3 ]
+  br label %for.body4
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+
+for.cond.cleanup3:                                ; preds = %for.body4
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %exitcond25 = icmp eq i64 %indvars.iv.next24, 1024
+  br i1 %exitcond25, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.body4:                                        ; preds = %for.body4, %for.cond1.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next.3, %for.body4 ]
+  %arrayidx = getelementptr inbounds i64*, i64** %Arr, i64 %indvars.iv
+  %0 = load i64*, i64** %arrayidx, align 8
+  %arrayidx6 = getelementptr inbounds i64, i64* %0, i64 %indvars.iv23
+  %1 = load i64, i64* %arrayidx6, align 4
+  %add7 = add i64 %1, 10
+  store i64 %add7, i64* %arrayidx6
+  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
+  %exitcond.3 = icmp eq i64 %indvars.iv.next.3, 1024
+  br i1 %exitcond.3, label %for.cond.cleanup3, label %for.body4
+}
+
+; void no_deps_interchange(unsigned **Arr) {
+;   for (int i = 0; i < 1024; ++i)
+;     for(int j = 0; j < 1024; ++j)
+;       Arr[i][j] += Arr[i][j] + 10;
+; }
+; CHECK-LABEL: 'Dependence Analysis' for function 'test2'
+; CHECK: da analyze - consistent input [0 S]!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - none!
+; CHECK: da analyze - anti [= =|<]!
+; CHECK: da analyze - none!
+
+define void @test2(i64** %Arr) {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %entry
+  %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.cond.cleanup3 ]
+  br label %for.body4
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+
+for.cond.cleanup3:                                ; preds = %for.body4
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %exitcond25 = icmp eq i64 %indvars.iv.next24, 1024
+  br i1 %exitcond25, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.body4:                                        ; preds = %for.body4, %for.cond1.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next.3, %for.body4 ]
+  %arrayidx = getelementptr inbounds i64*, i64** %Arr, i64 %indvars.iv23
+  %0 = load i64*, i64** %arrayidx, align 8
+  %arrayidx6 = getelementptr inbounds i64, i64* %0, i64 %indvars.iv
+  %1 = load i64, i64* %arrayidx6, align 4
+  %add7 = add i64 %1, 10
+  store i64 %add7, i64* %arrayidx6
+  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
+  %exitcond.3 = icmp eq i64 %indvars.iv.next.3, 1024
+  br i1 %exitcond.3, label %for.cond.cleanup3, label %for.body4
+}
+
+; Array index may be loop invariant (if N is 0), we cannot deduce a EQ
+; dependence.
+; void test3(unsigned *Arr, unsigned N) {
+;   for (int i = 0; i < 1024; ++i)
+;     for(int j = 0; j < 1024; ++j)
+;       Arr[(i + j) * N] += Arr[(i + j) * N] + 10;
+; }
+;
+; CHECK-LABEL: 'Dependence Analysis' for function 'test3'
+; CHECK:da analyze - input [* *]!
+; CHECK-NEXT: da analyze - anti [* *|<]!
+; CHECK-NEXT: da analyze - output [* *]!
+
+define void @test3(i64* nocapture %Arr, i64 %N) {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %entry
+  %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ]
+  br label %for.body4
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+
+for.cond.cleanup3:                                ; preds = %for.body4
+  %inc12 = add nuw nsw i64 %i.025, 1
+  %exitcond26 = icmp eq i64 %inc12, 1024
+  br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.body4:                                        ; preds = %for.body4, %for.cond1.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
+  %add = add i64 %indvars.iv, %i.025
+  %idxprom = mul i64 %add, %N
+  %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
+  %lv = load i64, i64* %arrayidx, align 4
+  %add10 = add i64 %lv, 10
+  store i64 %add10, i64* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
+}
+
+; Array index is guaranteed to not be loop invariant, we can deduce there is a
+; EQ dependence.
+; void test4(unsigned *Arr) {
+;   for (int i = 0; i < 1024; ++i)
+;     for(int j = 0; j < 1024; ++j)
+;       Arr[(i + j) * 1024] += Arr[(i + j) * 1024] + 10;
+; }
+;
+; CHECK-LABEL: 'Dependence Analysis' for function 'test4'
+; CHECK: da analyze - none!
+; CHECK-NEXT: da analyze - anti [= =|<]!
+; CHECK-NEXT: da analyze - none!
+define void @test4(i64* nocapture %Arr) {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %entry
+  %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ]
+  br label %for.body4
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+
+for.cond.cleanup3:                                ; preds = %for.body4
+  %inc12 = add nuw nsw i64 %i.025, 1
+  %exitcond26 = icmp eq i64 %inc12, 1024
+  br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.body4:                                        ; preds = %for.body4, %for.cond1.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
+  %add = add i64 %indvars.iv, %i.025
+  %idxprom = mul i64 %add, 1024
+  %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
+  %lv = load i64, i64* %arrayidx, align 4
+  %add10 = add i64 %lv, 10
+  store i64 %add10, i64* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
+}
+
+; Array index is guaranteed to not be loop invariant, we can deduce there is a
+; EQ dependence.
+; void test5(unsigned *Arr) {
+;   for (int i = 0; i < 1024; ++i)
+;     for(int j = 0; j < 1024; ++j)
+;       Arr[i * N + j] += Arr[i *N + j] + 10;
+; }
+;
+; CHECK-LABEL: 'Dependence Analysis' for function 'test5'
+; CHECK: da analyze - none!
+; CHECK-NEXT: da analyze - anti [= =|<]!
+; CHECK-NEXT: da analyze - none!
+
+define void @test5(i64* nocapture %Arr, i64 %N) {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %entry
+  %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ]
+  br label %for.body4
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+
+for.cond.cleanup3:                                ; preds = %for.body4
+  %inc12 = add nuw nsw i64 %i.025, 1
+  %exitcond26 = icmp eq i64 %inc12, 1024
+  br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.body4:                                        ; preds = %for.body4, %for.cond1.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
+  %mul = mul i64 %i.025, %N
+  %idxprom = add i64 %indvars.iv, %mul
+  %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
+  %lv = load i64, i64* %arrayidx, align 4
+  %add10 = add i64 %lv, 10
+  store i64 %add10, i64* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
+}
+
+; Array index may be loop invariant (if N is 0), we cannot deduce there is a
+; EQ dependence.
+; void test6(unsigned *Arr, unsigned N) {
+;   for (int i = 0; i < 1024; ++i)
+;     for(int j = 0; j < 1024; ++j)
+;       Arr[i + j * N] += Arr[i + j * N] + 10;
+; }
+;
+;
+; CHECK-LABEL: 'Dependence Analysis' for function 'test6'
+; CHECK:da analyze - input [* *]!
+; CHECK-NEXT: da analyze - anti [* *|<]!
+; CHECK-NEXT: da analyze - output [* *]!
+
+define void @test6(i64* nocapture %Arr, i64 %N) {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %entry
+  %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ]
+  br label %for.body4
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+
+for.cond.cleanup3:                                ; preds = %for.body4
+  %inc12 = add nuw nsw i64 %i.025, 1
+  %exitcond26 = icmp eq i64 %inc12, 1024
+  br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader
+
+for.body4:                                        ; preds = %for.body4, %for.cond1.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
+  %mul = mul i64 %indvars.iv, %N
+  %idxprom = add i64 %mul, %i.025
+  %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
+  %lv = load i64, i64* %arrayidx, align 4
+  %add10 = add i64 %lv, 10
+  store i64 %add10, i64* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
+}
+
+; Cannot deduce EQ dependence here, because subtracting induction variables
+; from the same loop might yield a constant.
+; void test7(unsigned *Arr) {
+;   unsigned j = 0;
+;   for (int i = 0; i < 1024; ++i) {
+;       Arr[1024 + (i - j)] += Arr[1024 + (i - j)] + 10;
+;       j++;
+;   }
+; }
+;
+; CHECK-LABEL: 'Dependence Analysis' for function 'test7'
+; CHECK: da analyze - consistent input [S]!
+; CHECK-NEXT: da analyze - consistent anti [S|<]!
+; CHECK-NEXT: da analyze - consistent output [S]!
+
+define void @test7(i64* nocapture %Arr, i64 %N) {
+entry:
+  br label %for.body4
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+
+for.body4:                                        ; preds = %for.body4, %for.cond1.preheader
+  %indvars.iv = phi i64 [ 0, %entry], [ %indvars.iv.next, %for.body4 ]
+  %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.body4 ]
+  %idxsub = sub i64 %i.025, %indvars.iv
+  %idxprom = add i64 1024, %idxsub
+  %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
+  %lv = load i64, i64* %arrayidx, align 4
+  %add10 = add i64 %lv, 10
+  store i64 %add10, i64* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  %inc12 = add nuw nsw i64 %i.025, 1
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body4
+}
+
+; We can deduce there is EQ dependence between accesses to c.
+; unsigned a[1024][1024];
+; unsigned b[1024][1024];
+; unsigned c[1024][1024];
+;
+; void test9(unsigned N) {
+;     for (unsigned j = 0; j < N; j++)
+;       for (unsigned k = 0; k < N; k++)
+;         for (unsigned i = 0; i < N; i++)
+;           c[i][j] = c[i][j] + a[i+1][k];
+;           a[i][k] = a[i+1][k];
+;           b[i][k] = b[j][k-1];
+; }
+
+; CHECK-LABEL: 'Dependence Analysis' for function 'test9'
+; CHECK: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - anti [= S =|<]!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - anti [S * *|<]!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - anti [S <> *]!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - none!
+;
+@a = global [1024 x [1024 x i64]] zeroinitializer, align 16
+@b = global [1024 x [1024 x i64]] zeroinitializer, align 16
+@c = global [1024 x [1024 x i64]] zeroinitializer, align 16
+
+define dso_local void @test9(i64 %N) local_unnamed_addr {
+entry:
+  %cmp49 = icmp sgt i64 %N, 0
+  br i1 %cmp49, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup
+
+for.cond5.preheader.lr.ph:                        ; preds = %entry, %for.cond.cleanup3
+  %indvars.iv55 = phi i64 [ %indvars.iv.next56, %for.cond.cleanup3 ], [ 0, %entry ]
+  br label %for.body8.lr.ph
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3, %entry
+  ret void
+
+for.body8.lr.ph:                                  ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
+  %indvars.iv51 = phi i64 [ 0, %for.cond5.preheader.lr.ph ], [ %indvars.iv.next52, %for.cond.cleanup7 ]
+  br label %for.body8
+
+for.cond.cleanup3:                                ; preds = %for.cond.cleanup7
+  %indvars.iv.next56 = add nuw nsw i64 %indvars.iv55, 1
+  %exitcond58 = icmp eq i64 %indvars.iv.next56, %N
+  br i1 %exitcond58, label %for.cond.cleanup, label %for.cond5.preheader.lr.ph
+
+for.cond.cleanup7:                                ; preds = %for.body8
+  %indvars.iv.next52 = add nuw nsw i64 %indvars.iv51, 1
+  %exitcond54 = icmp eq i64 %indvars.iv.next52, %N
+  br i1 %exitcond54, label %for.cond.cleanup3, label %for.body8.lr.ph
+
+for.body8:                                        ; preds = %for.body8, %for.body8.lr.ph
+  %indvars.iv = phi i64 [ 0, %for.body8.lr.ph ], [ %indvars.iv.next, %for.body8 ]
+  %arrayidx10 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @c, i64 0, i64 %indvars.iv, i64 %indvars.iv55
+  %arrayidx14 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @a, i64 0, i64 %indvars.iv, i64 %indvars.iv51
+  %i_next = add i64 %indvars.iv, 1
+  %arrayidx16 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @a, i64 0, i64 %i_next, i64 %indvars.iv51
+  %k_sub = sub i64 %indvars.iv51, 1
+  %arrayidx18 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @b, i64 0, i64 %indvars.iv, i64 %k_sub
+  %arrayidx20 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @b, i64 0, i64 %indvars.iv, i64 %indvars.iv51
+  %vc = load i64, i64* %arrayidx10, align 4
+  %va = load i64, i64* %arrayidx16, align 4
+  %vb = load i64, i64* %arrayidx18, align 4
+  %add = add nsw i64 %vc, %va
+  store i64 %add, i64* %arrayidx10, align 4
+  store i64 %va, i64* %arrayidx14, align 4
+  store i64 %vb, i64* %arrayidx20, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
+}

test/Analysis/DependenceAnalysis/SymbolicRDIV.ll

 ;;      *B++ = A[2*n2];
 
 define void @symbolicrdiv6(i32* %A, i32* %B, i64 %n1, i64 %n2) nounwind uwtable ssp {
 entry:
   %cmp4 = icmp eq i64 %n1, 0
   br i1 %cmp4, label %for.end7, label %for.cond1.preheader.preheader
 
 ; CHECK: 'Dependence Analysis' for function 'symbolicrdiv6'
-; CHECK: da analyze - output [* *]!
+; CHECK: da analyze - none!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - consistent input [S S]!
 ; CHECK: da analyze - confused!
-; CHECK: da analyze - output [* *]!
+; CHECK: da analyze - none!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc5
   %B.addr.06 = phi i32* [ %B.addr.1.lcssa, %for.inc5 ], [ %B, %for.cond1.preheader.preheader ]
   %i.05 = phi i64 [ %inc6, %for.inc5 ], [ 0, %for.cond1.preheader.preheader ]
   %cmp21 = icmp eq i64 %n2, 0

test/Analysis/DependenceAnalysis/WeakZeroSrcSIV.ll

 ;;    A[10] = i;
 ;;    *B++ = A[n*i + 10];
 
 define void @weakzerosrc1(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 entry:
   %cmp1 = icmp eq i64 %n, 0
   br i1 %cmp1, label %for.end, label %for.body.preheader
 
-; CHECK: da analyze - consistent output [S]!
+; CHECK: da analyze - consistent output [S]
 ; CHECK: da analyze - flow [p=>|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body

test/Transforms/LoopInterchange/currentLimitation.ll

  
 ;;--------------------------------------Test case 01------------------------------------
 ;; [FIXME] This loop though valid is currently not interchanged due to the limitation that we cannot split the inner loop latch due to multiple use of inner induction
 ;; variable.(used to increment the loop counter and to access A[j+1][i+1]
 ;;  for(int i=0;i<N-1;i++)
 ;;    for(int j=1;j<N-1;j++)
 ;;      A[j+1][i+1] = A[j+1][i+1] + k;
 
-; FIXME: Currently fails because of DA changes.
 ; IR-LABEL: @interchange_01
 ; IR-NOT: split
 
-; CHECK:      Name:            Dependence
+; CHECK:      Name:            UnsupportedInsBetweenInduction
 ; CHECK-NEXT: Function:        interchange_01
 
 define void @interchange_01(i32 %k, i32 %N) {
  entry:
    %sub = add nsw i32 %N, -1
    %cmp26 = icmp sgt i32 %N, 1
    br i1 %cmp26, label %for.cond1.preheader.lr.ph, label %for.end17
- 
  for.cond1.preheader.lr.ph:
    %cmp324 = icmp sgt i32 %sub, 1
    %0 = add i32 %N, -2
    %1 = sext i32 %sub to i64
    br label %for.cond1.preheader
- 
  for.cond.loopexit:
    %cmp = icmp slt i64 %indvars.iv.next29, %1
    br i1 %cmp, label %for.cond1.preheader, label %for.end17
- 
  for.cond1.preheader:
    %indvars.iv28 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next29, %for.cond.loopexit ]
    %indvars.iv.next29 = add nuw nsw i64 %indvars.iv28, 1
    br i1 %cmp324, label %for.body4, label %for.cond.loopexit
- 
  for.body4:
    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body4 ], [ 1, %for.cond1.preheader ]
    %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
    %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv.next, i64 %indvars.iv.next29
    %2 = load i32, i32* %arrayidx7
    %add8 = add nsw i32 %2, %k
    store i32 %add8, i32* %arrayidx7
    %lftr.wideiv = trunc i64 %indvars.iv to i32
    %exitcond = icmp eq i32 %lftr.wideiv, %0
    br i1 %exitcond, label %for.cond.loopexit, label %for.body4
- 
- for.end17: 
+ for.end17:
    ret void
 }
 
 ; When currently cannot interchange this loop, because transform currently
 ; expects the latches to be the exiting blocks too.
 
 ; IR-LABEL: @interchange_02
 ; IR-NOT: split

test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll

for.inc17:
   br i1 %exitcond38, label %for.end19, label %for.body3.lr.ph
 
 for.end19:
   ret void
 }
 
 ; CHECK: --- !Missed
 ; CHECK-NEXT: Pass:            loop-interchange
-; CHECK-NEXT: Name:            Dependence
+; CHECK-NEXT: Name:            InterchangeNotProfitable
 ; CHECK-NEXT: Function:        test01
-; CHECK-NEXT: Args:
-; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
-; CHECK-NEXT: ...
 
 ;;--------------------------------------Test case 02------------------------------------
 ;; [FIXME] This loop though valid is currently not interchanged due to the
 ;; limitation that we cannot split the inner loop latch due to multiple use of inner induction
 ;; variable.(used to increment the loop counter and to access A[j+1][i+1]
 ;;  for(int i=0;i<N-1;i++)
 ;;    for(int j=1;j<N-1;j++)
 ;;      A[j+1][i+1] = A[j+1][i+1] + k;
for.body4:
    br i1 %exitcond, label %for.cond.loopexit, label %for.body4
 
  for.end17:
    ret void
 }
 
 ; CHECK: --- !Missed
 ; CHECK-NEXT: Pass:            loop-interchange
-; CHECK-NEXT: Name:            Dependence
+; CHECK-NEXT: Name:            UnsupportedInsBetweenInduction
 ; CHECK-NEXT: Function:        test02
-; CHECK-NEXT: Args:
-; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
-; CHECK-NEXT: ...
 
 ;;-----------------------------------Test case 03-------------------------------
 ;; Test to make sure we can handle output dependencies.
 ;;
 ;;  for (int i = 0; i < 2; ++i)
 ;;    for(int j = 0; j < 3; ++j) {
 ;;      A[j][i] = i;
 ;;      A[j][i+1] = j;
for.inc15:
   br i1 %exitcond36, label %for.end17, label %for.body
 
 for.end17:
   ret void
 }
 
 ; CHECK: --- !Missed
 ; CHECK-NEXT: Pass:            loop-interchange
-; CHECK-NEXT: Name:            Dependence
+; CHECK-NEXT: Name:            NotTightlyNested
 ; CHECK-NEXT: Function:        test04
-; CHECK-NEXT: Args:
-; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
-; CHECK-NEXT: ...