Cache dependence computation using FoldingSet.

This introduces an LDA-internal DependencePair class. The intention is,
that this is a place where dependence testers can store various results
such as SCEVs describing conflicting iterations, breaking conditions,
distance/direction vectors, etc.

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

1 files changed, 40 insertions, 4 deletions

diff --git a/include/llvm/Analysis/LoopDependenceAnalysis.h b/include/llvm/Analysis/LoopDependenceAnalysis.h
index 42e434efba..17bbf8be8b 100644
--- a/include/llvm/Analysis/LoopDependenceAnalysis.h
+++ b/include/llvm/Analysis/LoopDependenceAnalysis.h
@@ -20,7 +20,9 @@
 #ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
 #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
 
+#include "llvm/ADT/FoldingSet.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Support/Allocator.h"
 #include "llvm/Support/raw_ostream.h"
 #include <iosfwd>
 
@@ -32,24 +34,58 @@ class ScalarEvolution;
 class Value;
 
 class LoopDependenceAnalysis : public LoopPass {
-  Loop *L;
   AliasAnalysis *AA;
   ScalarEvolution *SE;
 
+  /// L - The loop we are currently analysing.
+  Loop *L;
+
+  /// TODO: doc
+  enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 };
+
+  /// DependencePair - Represents a data dependence relation between to memory
+  /// reference instructions.
+  ///
+  /// TODO: add subscripts vector
+  struct DependencePair : public FastFoldingSetNode {
+    Value *A;
+    Value *B;
+    DependenceResult Result;
+
+    DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) :
+        FastFoldingSetNode(ID), A(a), B(b), Result(Unknown) {}
+  };
+
+  /// findOrInsertDependencePair - Return true if a DependencePair for the
+  /// given Values already exists, false if a new DependencePair had to be
+  /// created. The third argument is set to the pair found or created.
+  bool findOrInsertDependencePair(Value*, Value*, DependencePair*&);
+
+  /// TODO: doc
+  void analysePair(DependencePair *P) const;
+
 public:
   static char ID; // Class identification, replacement for typeinfo
   LoopDependenceAnalysis() : LoopPass(&ID) {}
 
-  /// TODO: docs
+  /// isDependencePair - Check wether two values can possibly give rise to a
+  /// data dependence: that is the case if both are instructions accessing
+  /// memory and at least one of those accesses is a write.
   bool isDependencePair(const Value*, const Value*) const;
+
+  /// depends - Return a boolean indicating if there is a data dependence
+  /// between two instructions.
   bool depends(Value*, Value*);
 
   bool runOnLoop(Loop*, LPPassManager&);
-
+  virtual void releaseMemory();
   virtual void getAnalysisUsage(AnalysisUsage&) const;
-
   void print(raw_ostream&, const Module* = 0) const;
   virtual void print(std::ostream&, const Module* = 0) const;
+
+private:
+  FoldingSet<DependencePair> Pairs;
+  BumpPtrAllocator PairAllocator;
 }; // class LoopDependenceAnalysis