dependence analysis

Patch from Preston Briggs <preston.briggs@gmail.com>.

This is an updated version of the dependence-analysis patch, including an MIV
test based on Banerjee's inequalities.

It's a fairly complete implementation of the paper

    Practical Dependence Testing
    Gina Goff, Ken Kennedy, and Chau-Wen Tseng
    PLDI 1991

It cannot yet propagate constraints between coupled RDIV subscripts (discussed
in Section 5.3.2 of the paper).

It's organized as a FunctionPass with a single entry point that supports testing
for dependence between two instructions in a function. If there's no dependence,
it returns null. If there's a dependence, it returns a pointer to a Dependence
which can be queried about details (what kind of dependence, is it loop
independent, direction and distance vector entries, etc). I haven't included
every imaginable feature, but there's a good selection that should be adequate
for supporting many loop transformations. Of course, it can be extended as
necessary.

Included in the patch file are many test cases, commented with C code showing
the loops and array references.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165708 91177308-0d34-0410-b5e6-96231b3b80d8

16 files changed, 5522 insertions, 0 deletions

diff --git a/test/Analysis/DependenceAnalysis/Banerjee.ll b/test/Analysis/DependenceAnalysis/Banerjee.ll
new file mode 100644
index 0000000000..8865ee9401
--- /dev/null
+++ b/test/Analysis/DependenceAnalysis/Banerjee.ll
@@ -0,0 +1,595 @@
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
+
+; ModuleID = 'Banerjee.bc'
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.6.0"
+
+
+;;  for (long int i = 1; i <= 10; i++)
+;;    for (long int j = 1; j <= 10; j++) {
+;;      A[10*i + j] = ...
+;;      ... = A[10*i + j - 1];
+
+define void @banerjee0(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc7
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
+  %i.03 = phi i64 [ 1, %entry ], [ %inc8, %for.inc7 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 1, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 10
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 10
+  %add5 = add nsw i64 %mul4, %j.02
+  %sub = add nsw i64 %add5, -1
+  %arrayidx6 = getelementptr inbounds i64* %A, i64 %sub
+  %0 = load i64* %arrayidx6, align 8
+; CHECK: da analyze - flow [<= <>]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 11
+  br i1 %exitcond, label %for.body3, label %for.inc7
+
+for.inc7:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 10
+  %inc8 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc8, 11
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
+
+for.end9:                                         ; preds = %for.inc7
+  ret void
+}
+
+
+;;  for (long int i = 1; i <= n; i++)
+;;    for (long int j = 1; j <= m; j++) {
+;;      A[10*i + j] = ...
+;;      ... = 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
+
+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 ]
+  %1 = add i64 %m, 1
+  %cmp21 = icmp sgt i64 %m, 0
+  br i1 %cmp21, label %for.body3.preheader, label %for.inc7
+
+for.body3.preheader:                              ; preds = %for.cond1.preheader
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3.preheader, %for.body3
+  %j.03 = phi i64 [ %inc, %for.body3 ], [ 1, %for.body3.preheader ]
+  %B.addr.12 = phi i64* [ %incdec.ptr, %for.body3 ], [ %B.addr.06, %for.body3.preheader ]
+  %mul = mul nsw i64 %i.05, 10
+  %add = add nsw i64 %mul, %j.03
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.05, 10
+  %add5 = add nsw i64 %mul4, %j.03
+  %sub = add nsw i64 %add5, -1
+  %arrayidx6 = getelementptr inbounds i64* %A, i64 %sub
+  %2 = load i64* %arrayidx6, align 8
+; CHECK: da analyze - flow [* <>]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.12, i64 1
+  store i64 %2, i64* %B.addr.12, align 8
+  %inc = add nsw i64 %j.03, 1
+  %exitcond = icmp eq i64 %inc, %1
+  br i1 %exitcond, label %for.inc7.loopexit, label %for.body3
+
+for.inc7.loopexit:                                ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.06, i64 %m
+  br label %for.inc7
+
+for.inc7:                                         ; preds = %for.inc7.loopexit, %for.cond1.preheader
+  %B.addr.1.lcssa = phi i64* [ %B.addr.06, %for.cond1.preheader ], [ %scevgep, %for.inc7.loopexit ]
+  %inc8 = add nsw i64 %i.05, 1
+  %exitcond7 = icmp eq i64 %inc8, %0
+  br i1 %exitcond7, label %for.end9.loopexit, label %for.cond1.preheader
+
+for.end9.loopexit:                                ; preds = %for.inc7
+  br label %for.end9
+
+for.end9:                                         ; preds = %for.end9.loopexit, %entry
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 10; i++)
+;;    for (long int j = 0; j < 10; j++) {
+;;      A[10*i + j] = 0;
+;;      *B++ = A[10*i + j + 100];
+
+define void @banerjee2(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc8
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 10
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 10
+  %add5 = add nsw i64 %mul4, %j.02
+  %add6 = add nsw i64 %add5, 100
+  %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
+  %0 = load i64* %arrayidx7, align 8
+; CHECK: da analyze - none!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 10
+  br i1 %exitcond, label %for.body3, label %for.inc8
+
+for.inc8:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 10
+  %inc9 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc9, 10
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
+
+for.end10:                                        ; preds = %for.inc8
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 10; i++)
+;;    for (long int j = 0; j < 10; j++) {
+;;      A[10*i + j] = ...
+;;      ... = A[10*i + j + 99];
+
+define void @banerjee3(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc8
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 10
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 10
+  %add5 = add nsw i64 %mul4, %j.02
+  %add6 = add nsw i64 %add5, 99
+  %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
+  %0 = load i64* %arrayidx7, align 8
+; CHECK: da analyze - flow [> >]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 10
+  br i1 %exitcond, label %for.body3, label %for.inc8
+
+for.inc8:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 10
+  %inc9 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc9, 10
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
+
+for.end10:                                        ; preds = %for.inc8
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 10; i++)
+;;    for (long int j = 0; j < 10; j++) {
+;;      A[10*i + j] = ...
+;;      ... = A[10*i + j - 100];
+
+define void @banerjee4(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc7
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 10
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 10
+  %add5 = add nsw i64 %mul4, %j.02
+  %sub = add nsw i64 %add5, -100
+  %arrayidx6 = getelementptr inbounds i64* %A, i64 %sub
+  %0 = load i64* %arrayidx6, align 8
+; CHECK: da analyze - none!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 10
+  br i1 %exitcond, label %for.body3, label %for.inc7
+
+for.inc7:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 10
+  %inc8 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc8, 10
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
+
+for.end9:                                         ; preds = %for.inc7
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 10; i++)
+;;    for (long int j = 0; j < 10; j++) {
+;;      A[10*i + j] = ...
+;;      ... = A[10*i + j - 99];
+
+define void @banerjee5(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc7
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 10
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 10
+  %add5 = add nsw i64 %mul4, %j.02
+  %sub = add nsw i64 %add5, -99
+  %arrayidx6 = getelementptr inbounds i64* %A, i64 %sub
+  %0 = load i64* %arrayidx6, align 8
+; CHECK: da analyze - flow [< <]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 10
+  br i1 %exitcond, label %for.body3, label %for.inc7
+
+for.inc7:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 10
+  %inc8 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc8, 10
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
+
+for.end9:                                         ; preds = %for.inc7
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 10; i++)
+;;    for (long int j = 0; j < 10; j++) {
+;;      A[10*i + j] = ...
+;;      ... = A[10*i + j + 9];
+
+define void @banerjee6(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc8
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 10
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 10
+  %add5 = add nsw i64 %mul4, %j.02
+  %add6 = add nsw i64 %add5, 9
+  %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
+  %0 = load i64* %arrayidx7, align 8
+; CHECK: da analyze - flow [=> <>]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 10
+  br i1 %exitcond, label %for.body3, label %for.inc8
+
+for.inc8:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 10
+  %inc9 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc9, 10
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
+
+for.end10:                                        ; preds = %for.inc8
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 10; i++)
+;;    for (long int j = 0; j < 10; j++) {
+;;      A[10*i + j] = ...
+;;      ... = A[10*i + j + 10];
+
+define void @banerjee7(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc8
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 10
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 10
+  %add5 = add nsw i64 %mul4, %j.02
+  %add6 = add nsw i64 %add5, 10
+  %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
+  %0 = load i64* %arrayidx7, align 8
+; CHECK: da analyze - flow [> <=]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 10
+  br i1 %exitcond, label %for.body3, label %for.inc8
+
+for.inc8:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 10
+  %inc9 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc9, 10
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
+
+for.end10:                                        ; preds = %for.inc8
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 10; i++)
+;;    for (long int j = 0; j < 10; j++) {
+;;      A[10*i + j] = ...
+;;      ... = A[10*i + j + 11];
+
+define void @banerjee8(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc8
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 10
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 10
+  %add5 = add nsw i64 %mul4, %j.02
+  %add6 = add nsw i64 %add5, 11
+  %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
+  %0 = load i64* %arrayidx7, align 8
+; CHECK: da analyze - flow [> <>]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 10
+  br i1 %exitcond, label %for.body3, label %for.inc8
+
+for.inc8:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 10
+  %inc9 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc9, 10
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
+
+for.end10:                                        ; preds = %for.inc8
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 20; i++)
+;;    for (long int j = 0; j < 20; j++) {
+;;      A[30*i + 500*j] = ...
+;;      ... = 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
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc8
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 30
+  %mul4 = mul nsw i64 %j.02, 500
+  %add = add nsw i64 %mul, %mul4
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %0 = mul i64 %j.02, -500
+  %sub = add i64 %i.03, %0
+  %add6 = add nsw i64 %sub, 11
+  %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
+  %1 = load i64* %arrayidx7, align 8
+; CHECK: da analyze - flow [<= =|<]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %1, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 20
+  br i1 %exitcond, label %for.body3, label %for.inc8
+
+for.inc8:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 20
+  %inc9 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc9, 20
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
+
+for.end10:                                        ; preds = %for.inc8
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 20; i++)
+;;    for (long int j = 0; j < 20; j++) {
+;;      A[i + 500*j] = ...
+;;      ... = A[i - 500*j + 11];
+
+define void @banerjee10(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc7
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %j.02, 500
+  %add = add nsw i64 %i.03, %mul
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %0 = mul i64 %j.02, -500
+  %sub = add i64 %i.03, %0
+  %add5 = add nsw i64 %sub, 11
+  %arrayidx6 = getelementptr inbounds i64* %A, i64 %add5
+  %1 = load i64* %arrayidx6, align 8
+; CHECK: da analyze - flow [<> =]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %1, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 20
+  br i1 %exitcond, label %for.body3, label %for.inc7
+
+for.inc7:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 20
+  %inc8 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc8, 20
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
+
+for.end9:                                         ; preds = %for.inc7
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 20; i++)
+;;    for (long int j = 0; j < 20; j++) {
+;;      A[300*i + j] = ...
+;;      ... = A[250*i - j + 11];
+
+define void @banerjee11(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc7
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 300
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 250
+  %sub = sub nsw i64 %mul4, %j.02
+  %add5 = add nsw i64 %sub, 11
+  %arrayidx6 = getelementptr inbounds i64* %A, i64 %add5
+  %0 = load i64* %arrayidx6, align 8
+; CHECK: da analyze - flow [<= <>]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 20
+  br i1 %exitcond, label %for.body3, label %for.inc7
+
+for.inc7:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 20
+  %inc8 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc8, 20
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
+
+for.end9:                                         ; preds = %for.inc7
+  ret void
+}
+
+
+;;  for (long int i = 0; i < 20; i++)
+;;    for (long int j = 0; j < 20; j++) {
+;;      A[100*i + j] = ...
+;;      ... = A[100*i - j + 11];
+
+define void @banerjee12(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc7
+  %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
+  %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
+  %mul = mul nsw i64 %i.03, 100
+  %add = add nsw i64 %mul, %j.02
+  %arrayidx = getelementptr inbounds i64* %A, i64 %add
+  store i64 0, i64* %arrayidx, align 8
+  %mul4 = mul nsw i64 %i.03, 100
+  %sub = sub nsw i64 %mul4, %j.02
+  %add5 = add nsw i64 %sub, 11
+  %arrayidx6 = getelementptr inbounds i64* %A, i64 %add5
+  %0 = load i64* %arrayidx6, align 8
+; CHECK: da analyze - flow [= <>]!
+  %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
+  store i64 %0, i64* %B.addr.11, align 8
+  %inc = add nsw i64 %j.02, 1
+  %exitcond = icmp ne i64 %inc, 20
+  br i1 %exitcond, label %for.body3, label %for.inc7
+
+for.inc7:                                         ; preds = %for.body3
+  %scevgep = getelementptr i64* %B.addr.04, i64 20
+  %inc8 = add nsw i64 %i.03, 1
+  %exitcond5 = icmp ne i64 %inc8, 20
+  br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
+
+for.end9:                                         ; preds = %for.inc7
+  ret void
+}
diff --git a/test/Analysis/DependenceAnalysis/Coupled.ll b/test/Analysis/DependenceAnalysis/Coupled.ll
new file mode 100644
index 0000000000..60163fe7c2
--- /dev/null
+++ b/test/Analysis/DependenceAnalysis/Coupled.ll
@@ -0,0 +1,509 @@
+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
+
+; ModuleID = 'Coupled.bc'
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.6.0"
+
+
+;; for (long int i = 0; i < 50; i++)
+;;   A[i][i] = ...
+;;   ... = A[i + 10][i + 9]
+
+define void @couple0([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+  %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
+  %conv = trunc i64 %i.02 to i32
+  %arrayidx1 = getelementptr inbounds [100 x i32]* %A, i64 %i.02, i64 %i.02
+  store i32 %conv, i32* %arrayidx1, align 4
+  %add = add nsw i64 %i.02, 9
+  %add2 = add nsw i64 %i.02, 10
+  %arrayidx4 = getelementptr inbounds [100 x i32]* %A, i64 %add2, i64 %add
+  %0 = load i32* %arrayidx4, align 4
+; CHECK: da analyze - none!
+  %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
+  store i32 %0, i32* %B.addr.01, align 4
+  %inc = add nsw i64 %i.02, 1
+  %cmp = icmp slt i64 %inc, 50
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+
+;; for (long int i = 0; i < 50; i++)
+;;   A[i][i] = ...
+;;   ... = A[i + 9][i + 9]
+
+define void @couple1([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+  %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
+  %conv = trunc i64 %i.02 to i32
+  %arrayidx1 = getelementptr inbounds [100 x i32]* %A, i64 %i.02, i64 %i.02
+  store i32 %conv, i32* %arrayidx1, align 4
+  %add = add nsw i64 %i.02, 9
+  %add2 = add nsw i64 %i.02, 9
+  %arrayidx4 = getelementptr inbounds [100 x i32]* %A, i64 %add2, i64 %add
+  %0 = load i32* %arrayidx4, align 4
+; CHECK: da analyze - consistent flow [-9]!
+  %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
+  store i32 %0, i32* %B.addr.01, align 4
+  %inc = add nsw i64 %i.02, 1
+  %cmp = icmp slt i64 %inc, 50
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+
+;; for (long int i = 0; i < 50; i++)
+;;   A[3*i - 6][3*i - 6] = ...
+;;   ... = A[i][i]
+
+define void @couple2([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+  %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
+  %conv = trunc i64 %i.02 to i32
+  %mul = mul nsw i64 %i.02, 3
+  %sub = add nsw i64 %mul, -6
+  %mul1 = mul nsw i64 %i.02, 3
+  %sub2 = add nsw i64 %mul1, -6
+  %arrayidx3 = getelementptr inbounds [100 x i32]* %A, i64 %sub2, i64 %sub
+  store i32 %conv, i32* %arrayidx3, align 4
+  %arrayidx5 = getelementptr inbounds [100 x i32]* %A, i64 %i.02, i64 %i.02
+  %0 = load i32* %arrayidx5, align 4
+; CHECK: da analyze - flow [*|<]!
+  %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
+  store i32 %0, i32* %B.addr.01, align 4
+  %inc = add nsw i64 %i.02, 1
+  %cmp = icmp slt i64 %inc, 50
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+
+;; for (long int i = 0; i < 50; i++)
+;;   A[3*i - 6][3*i - 5] = ...
+;;   ... = A[i][i]
+
+define void @couple3([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+  %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
+  %conv = trunc i64 %i.02 to i32
+  %mul = mul nsw i64 %i.02, 3
+  %sub = add nsw i64 %mul, -5
+  %mul1 = mul nsw i64 %i.02, 3
+  %sub2 = add nsw i64 %mul1, -6
+  %arrayidx3 = getelementptr inbounds [100 x i32]* %A, i64 %sub2, i64 %sub
+  store i32 %conv, i32* %arrayidx3, align 4
+  %arrayidx5 = getelementptr inbounds [100 x i32]* %A, i64 %i.02, i64 %i.02
+  %0 = load i32* %arrayidx5, align 4
+; CHECK: da analyze - none!
+  %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
+  store i32 %0, i32* %B.addr.01, align 4
+  %inc = add nsw i64 %i.02, 1
+  %cmp = icmp slt i64 %inc, 50
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+
+;; for (long int i = 0; i < 50; i++)
+;;   A[3*i - 6][3*i - n] = ...
+;;   ... = A[i][i]
+
+define void @couple4([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+  %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
+  %conv = trunc i64 %i.02 to i32
+  %mul = mul nsw i64 %i.02, 3
+  %conv1 = sext i32 %n to i64
+  %sub = sub nsw i64 %mul, %conv1
+  %mul2 = mul nsw i64 %i.02, 3
+  %sub3 = add nsw i64 %mul2, -6
+  %arrayidx4 = getelementptr inbounds [100 x i32]* %A, i64 %sub3, i64 %sub
+  store i32 %conv, i32* %arrayidx4, align 4
+  %arrayidx6 = getelementptr inbounds [100 x i32]* %A, i64 %i.02, i64 %i.02
+  %0 = load i32* %arrayidx6, align 4
+; CHECK: da analyze - flow [*|<]!
+  %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
+  store i32 %0, i32* %B.addr.01, align 4
+  %inc = add nsw i64 %i.02, 1
+  %cmp = icmp slt i64 %inc, 50
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+
+;; for (long int i = 0; i < 50; i++)
+;;   A[3*i - n + 1][3*i - n] = ...
+;;   ... = A[i][i]
+
+define void @couple5([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+  %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
+  %conv = trunc i64 %i.02 to i32
+  %mul = mul nsw i64 %i.02, 3
+  %conv1 = sext i32 %n to i64
+  %sub = sub nsw i64 %mul, %conv1
+  %mul2 = mul nsw i64 %i.02, 3
+  %conv3 = sext i32 %n to i64
+  %sub4 = sub nsw i64 %mul2, %conv3
+  %add = add nsw i64 %sub4, 1
+  %arrayidx5 = getelementptr inbounds [100 x i32]* %A, i64 %add, i64 %sub
+  store i32 %conv, i32* %arrayidx5, align 4
+  %arrayidx7 = getelementptr inbounds [100 x i32]* %A, i64 %i.02, i64 %i.02
+  %0 = load i32* %arrayidx7, align 4
+; CHECK: da analyze - none!
+  %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
+  store i32 %0, i32* %B.addr.01, align 4
+  %inc = add nsw i64 %i.02, 1
+  %cmp = icmp slt i64 %inc, 50
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+
+;; for (long int i = 0; i < 50; i++)
+;;   A[i][3*i - 6] = ...
+;;   ... = A[i][i]
+
+define void @couple6([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+  %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
+  %conv = trunc i64 %i.02 to i32
+  %mul = mul nsw i64 %i.02, 3
+  %sub = add nsw i64 %mul, -6
+  %arrayidx1 = getelementptr inbounds [100 x i32]* %A, i64 %i.02, i64 %sub
+  store i32 %conv, i32* %arrayidx1, align 4
+  %arrayidx3 = getelementptr inbo