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

1 files changed, 1 insertions, 0 deletions

diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp
index 87a75fd3b1..588206e915 100644
--- a/lib/Analysis/Analysis.cpp
+++ b/lib/Analysis/Analysis.cpp
@@ -31,6 +31,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeCFGOnlyViewerPass(Registry);
   initializeCFGOnlyPrinterPass(Registry);
   initializePrintDbgInfoPass(Registry);
+  initializeDependenceAnalysisPass(Registry);
   initializeDominanceFrontierPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);