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/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index 067d8dae1d..ee9b1c5852 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -94,6 +94,7 @@ void initializeDCEPass(PassRegistry&);
 void initializeDSEPass(PassRegistry&);
 void initializeDeadInstEliminationPass(PassRegistry&);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
+void initializeDependenceAnalysisPass(PassRegistry&);
 void initializeDomOnlyPrinterPass(PassRegistry&);
 void initializeDomOnlyViewerPass(PassRegistry&);
 void initializeDomPrinterPass(PassRegistry&);