Template-ize more of the DomTree internal implementation details. Only the calculate...

[oota-llvm.git] / include / llvm / Analysis / MemoryDependenceAnalysis.h

diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index ac6ffb642b8402ee1488c3b77b73758aad93b97e..733e702506eed3b52e17369a891e956f9b6c5859 100644 (file)
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -22,7 +22,6 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Compiler.h"
-#include <map>
 
 namespace llvm {
 
@@ -32,23 +31,37 @@ class Instruction;
 
 class MemoryDependenceAnalysis : public FunctionPass {
   private:
-
+    // A map from instructions to their dependency, with a boolean
+    // flags for whether this mapping is confirmed or not
     typedef DenseMap<Instruction*, std::pair<Instruction*, bool> > 
-    depMapType;
-
+            depMapType;
     depMapType depGraphLocal;
 
-    typedef std::multimap<Instruction*, Instruction*> reverseDepMapType;
+    // A map from instructions to their non-local dependencies.
+    typedef DenseMap<Instruction*, DenseMap<BasicBlock*, Value*> >
+            nonLocalDepMapType;
+    nonLocalDepMapType depGraphNonLocal;
+    
+    // A reverse mapping form dependencies to the dependees.  This is
+    // used when removing instructions to keep the cache coherent.
+    typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> >
+            reverseDepMapType;
     reverseDepMapType reverseDep;
-  
-    Instruction* getCallSiteDependency(CallSite C, Instruction* start,
-                                       bool local = true);
-    void nonLocalHelper(Instruction* query, BasicBlock* block,
-                        DenseMap<BasicBlock*, Value*>& resp);
+    
+    // A reverse mapping form dependencies to the non-local dependees.
+    reverseDepMapType reverseDepNonLocal;
+    
   public:
+    // Special marker indicating that the query has no dependency
+    // in the specified block.
+    static Instruction* const NonLocal;
     
-    static Instruction* NonLocal;
-    static Instruction* None;
+    // Special marker indicating that the query has no dependency at all
+    static Instruction* const None;
+    
+    
+    // Special marker indicating a dirty cache entry
+    static Instruction* const Dirty;
     
     static char ID; // Class identification, replacement for typeinfo
     MemoryDependenceAnalysis() : FunctionPass((intptr_t)&ID) {}
@@ -60,7 +73,9 @@ class MemoryDependenceAnalysis : public FunctionPass {
     /// Clean up memory in between runs
     void releaseMemory() {
       depGraphLocal.clear();
+      depGraphNonLocal.clear();
       reverseDep.clear();
+      reverseDepNonLocal.clear();
     }
 
     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
@@ -73,12 +88,21 @@ class MemoryDependenceAnalysis : public FunctionPass {
     Instruction* getDependency(Instruction* query, Instruction* start = 0,
                                BasicBlock* block = 0);
     
+    /// getNonLocalDependency - Fills the passed-in map with the non-local 
+    /// dependencies of the queries.  The map will contain NonLocal for
+    /// blocks between the query and its dependencies.
     void getNonLocalDependency(Instruction* query,
                                DenseMap<BasicBlock*, Value*>& resp);
     
     /// removeInstruction - Remove an instruction from the dependence analysis,
     /// updating the dependence of instructions that previously depended on it.
     void removeInstruction(Instruction* rem);
+    
+  private:
+    Instruction* getCallSiteDependency(CallSite C, Instruction* start,
+                                       BasicBlock* block);
+    void nonLocalHelper(Instruction* query, BasicBlock* block,
+                        DenseMap<BasicBlock*, Value*>& resp);
   };
 
 } // End llvm namespace