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 99d913054df7e5446ae7eaf012dc995edca5ddf1..733e702506eed3b52e17369a891e956f9b6c5859 100644 (file)
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -18,9 +18,10 @@
 #define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
 
 #include "llvm/Pass.h"
+#include "llvm/Support/CallSite.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Compiler.h"
-#include <map>
 
 namespace llvm {
 
@@ -28,26 +29,53 @@ class Function;
 class FunctionPass;
 class Instruction;
 
-class VISIBILITY_HIDDEN MemoryDependenceAnalysis : public FunctionPass {
+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 depGraphLocal;
+
+    // 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;
+    
+    // A reverse mapping form dependencies to the non-local dependees.
+    reverseDepMapType reverseDepNonLocal;
     
-    DenseMap<Instruction*, std::pair<Instruction*, bool> > depGraphLocal;
-    std::multimap<Instruction*, Instruction*> reverseDep;
-  
   public:
+    // Special marker indicating that the query has no dependency
+    // in the specified block.
+    static Instruction* const NonLocal;
+    
+    // Special marker indicating that the query has no dependency at all
+    static Instruction* const None;
+    
     
-    static Instruction* NonLocal;
-    static Instruction* 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) {}
 
     /// Pass Implementation stuff.  This doesn't do any analysis.
     ///
-    bool runOnFunction(Function &) { 
+    bool runOnFunction(Function &) {return false; }
+    
+    /// Clean up memory in between runs
+    void releaseMemory() {
       depGraphLocal.clear();
+      depGraphNonLocal.clear();
       reverseDep.clear();
-      return false;
+      reverseDepNonLocal.clear();
     }
 
     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
@@ -56,12 +84,25 @@ class VISIBILITY_HIDDEN MemoryDependenceAnalysis : public FunctionPass {
     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
     
     /// getDependency - Return the instruction on which a memory operation
-    /// depends.
-    Instruction* getDependency(Instruction* query, bool local = true);
+    /// depends, starting with start.
+    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