6 files changed, 139 insertions, 2 deletions
diff --git a/lib/Analysis/LoopDependenceAnalysis.cpp b/lib/Analysis/LoopDependenceAnalysis.cpp
index b23459e81a..4912bf2759 100644
--- a/lib/Analysis/LoopDependenceAnalysis.cpp
+++ b/lib/Analysis/LoopDependenceAnalysis.cpp
@@ -40,6 +40,16 @@ static inline bool isMemRefInstr(const Value *I) {
   return isa<LoadInst>(I) || isa<StoreInst>(I);
 }
 
+static void getMemRefInstrs(
+    const Loop *L, SmallVectorImpl<Instruction*> &memrefs) {
+  for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
+      b != be; ++b)
+    for (BasicBlock::iterator i = (*b)->begin(), ie = (*b)->end();
+        i != ie; ++i)
+      if (isMemRefInstr(i))
+        memrefs.push_back(i);
+}
+
 //===----------------------------------------------------------------------===//
 //                             Dependence Testing
 //===----------------------------------------------------------------------===//
@@ -71,16 +81,30 @@ void LoopDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 }
 
 static void PrintLoopInfo(
-    raw_ostream &OS, const LoopDependenceAnalysis *LDA, const Loop *L) {
+    raw_ostream &OS, LoopDependenceAnalysis *LDA, const Loop *L) {
   if (!L->empty()) return; // ignore non-innermost loops
 
   OS << "Loop at depth " << L->getLoopDepth() << ", header block: ";
   WriteAsOperand(OS, L->getHeader(), false);
   OS << "\n";
+
+  SmallVector<Instruction*, 8> memrefs;
+  getMemRefInstrs(L, memrefs);
+  OS << "  Load/store instructions: " << memrefs.size() << "\n";
+  OS << "  Pairwise dependence results:\n";
+  for (SmallVector<Instruction*, 8>::const_iterator x = memrefs.begin(),
+      end = memrefs.end(); x != end; ++x)
+    for (SmallVector<Instruction*, 8>::const_iterator y = x + 1;
+        y != end; ++y)
+      if (LDA->isDependencePair(*x, *y))
+        OS << "\t" << (x - memrefs.begin()) << "," << (y - memrefs.begin())
+           << ": " << (LDA->depends(*x, *y) ? "dependent" : "independent")
+           << "\n";
 }
 
 void LoopDependenceAnalysis::print(raw_ostream &OS, const Module*) const {
-  PrintLoopInfo(OS, this, this->L);
+  // TODO: doc why const_cast is safe
+  PrintLoopInfo(OS, const_cast<LoopDependenceAnalysis*>(this), this->L);
 }
 
 void LoopDependenceAnalysis::print(std::ostream &OS, const Module *M) const {
diff --git a/test/Analysis/LoopDependenceAnalysis/dg.exp b/test/Analysis/LoopDependenceAnalysis/dg.exp
new file mode 100644
index 0000000000..f2005891a5
--- /dev/null
+++ b/test/Analysis/LoopDependenceAnalysis/dg.exp
@@ -0,0 +1,3 @@
+load_lib llvm.exp
+
+RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,c,cpp}]]
diff --git a/test/Analysis/LoopDependenceAnalysis/siv-strong1.ll b/test/Analysis/LoopDependenceAnalysis/siv-strong1.ll
new file mode 100644
index 0000000000..01f11137d7
--- /dev/null
+++ b/test/Analysis/LoopDependenceAnalysis/siv-strong1.ll
@@ -0,0 +1,30 @@
+; RUN: llvm-as < %s | opt -disable-output -analyze -lda > %t
+; RUN: grep {instructions: 3} %t | count 1
+; RUN: grep {0,2: dependent} %t | count 1
+; RUN: grep {1,2: dependent} %t | count 1
+
+; for (i = 0; i < 256; i++)
+;   x[i] = x[i] + y[i]
+
+@x = common global [256 x i32] zeroinitializer, align 4
+@y = common global [256 x i32] zeroinitializer, align 4
+
+define void @foo(...) nounwind {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
+  %y.addr = getelementptr [256 x i32]* @y, i64 0, i64 %i
+  %x.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i
+  %x = load i32* %x.addr
+  %y = load i32* %y.addr
+  %r = add i32 %y, %x
+  store i32 %r, i32* %x.addr
+  %i.next = add i64 %i, 1
+  %exitcond = icmp eq i64 %i.next, 256
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}
diff --git a/test/Analysis/LoopDependenceAnalysis/siv-strong2.ll b/test/Analysis/LoopDependenceAnalysis/siv-strong2.ll
new file mode 100644
index 0000000000..e64b92c3e7
--- /dev/null
+++ b/test/Analysis/LoopDependenceAnalysis/siv-strong2.ll
@@ -0,0 +1,31 @@
+; RUN: llvm-as < %s | opt -disable-output -analyze -lda > %t
+; RUN: grep {instructions: 3} %t | count 1
+; RUN: grep {0,2: dependent} %t | count 1
+; RUN: grep {1,2: dependent} %t | count 1
+
+; for (i = 0; i < 256; i++)
+;   x[i+1] = x[i] + y[i]
+
+@x = common global [256 x i32] zeroinitializer, align 4
+@y = common global [256 x i32] zeroinitializer, align 4
+
+define void @foo(...) nounwind {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
+  %y.ld.addr = getelementptr [256 x i32]* @y, i64 0, i64 %i
+  %x.ld.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i
+  %i.next = add i64 %i, 1
+  %x.st.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i.next
+  %x = load i32* %x.ld.addr
+  %y = load i32* %y.ld.addr
+  %r = add i32 %y, %x
+  store i32 %r, i32* %x.st.addr
+  %exitcond = icmp eq i64 %i.next, 256
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}
diff --git a/test/Analysis/LoopDependenceAnalysis/ziv1.ll b/test/Analysis/LoopDependenceAnalysis/ziv1.ll
new file mode 100644
index 0000000000..e42c0a08cb
--- /dev/null
+++ b/test/Analysis/LoopDependenceAnalysis/ziv1.ll
@@ -0,0 +1,23 @@
+; RUN: llvm-as < %s | opt -disable-output -analyze -lda > %t
+; RUN: grep {instructions: 2} %t | count 1
+; RUN: grep {0,1: dependent} %t | count 1
+
+; x[5] = x[6]
+
+@x = common global [256 x i32] zeroinitializer, align 4
+
+define void @foo(...) nounwind {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
+  %x = load i32* getelementptr ([256 x i32]* @x, i32 0, i64 6)
+  store i32 %x, i32* getelementptr ([256 x i32]* @x, i32 0, i64 5)
+  %i.next = add i64 %i, 1
+  %exitcond = icmp eq i64 %i.next, 256
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}
diff --git a/test/Analysis/LoopDependenceAnalysis/ziv2.ll b/test/Analysis/LoopDependenceAnalysis/ziv2.ll
new file mode 100644
index 0000000000..cecf3a750b
--- /dev/null
+++ b/test/Analysis/LoopDependenceAnalysis/ziv2.ll
@@ -0,0 +1,26 @@
+; RUN: llvm-as < %s | opt -disable-output -analyze -lda > %t
+; RUN: grep {instructions: 2} %t | count 1
+; RUN: grep {0,1: dependent} %t | count 1
+
+; x[c] = x[c+1] // with c being a loop-invariant constant
+
+@x = common global [256 x i32] zeroinitializer, align 4
+
+define void @foo(i64 %c0) nounwind {
+entry:
+  %c1 = add i64 %c0, 1
+  %x.ld.addr = getelementptr [256 x i32]* @x, i64 0, i64 %c0
+  %x.st.addr = getelementptr [256 x i32]* @x, i64 0, i64 %c1
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
+  %x = load i32* %x.ld.addr
+  store i32 %x, i32* %x.st.addr
+  %i.next = add i64 %i, 1
+  %exitcond = icmp eq i64 %i.next, 256
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}