Teach BasicAA::getModRefInfo(CallSite, CallSite) some

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

diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index 819035dbd25379e1f2ec3ed97694eb7899abcaad..ceed0ab54469d3ec8b343336db6867b1c99375a9 100644 (file)
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -18,6 +18,7 @@
 #include "llvm/Pass.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/OwningPtr.h"
 #include "llvm/ADT/PointerIntPair.h"
 
 namespace llvm {
@@ -28,6 +29,7 @@ namespace llvm {
   class AliasAnalysis;
   class TargetData;
   class MemoryDependenceAnalysis;
+  class PredIteratorCache;
   
   /// MemDepResult - A memory dependence query can return one of three different
   /// answers, described below.
@@ -151,6 +153,23 @@ namespace llvm {
     typedef std::pair<BasicBlock*, MemDepResult> NonLocalDepEntry;
     typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
   private:
+    /// ValueIsLoadPair - This is a pair<Value*, bool> where the bool is true if
+    /// the dependence is a read only dependence, false if read/write.
+    typedef PointerIntPair<Value*, 1, bool> ValueIsLoadPair;
+    
+    /// CachedNonLocalPointerInfo - This map stores the cached results of doing
+    /// a pointer lookup at the bottom of a block.  The key of this map is the
+    /// pointer+isload bit, the value is a list of <bb->result> mappings.
+    typedef DenseMap<ValueIsLoadPair,
+      std::pair<BasicBlock*, NonLocalDepInfo> > CachedNonLocalPointerInfo;
+    CachedNonLocalPointerInfo NonLocalPointerDeps;
+
+    // A map from instructions to their non-local pointer dependencies.
+    // The elements of the SmallPtrSet are ValueIsLoadPair's.
+    typedef DenseMap<Instruction*, 
+                     SmallPtrSet<void*, 4> > ReverseNonLocalPtrDepTy;
+    ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;
+
     
     /// PerInstNLInfo - This is the instruction we keep for each cached access
     /// that we have for an instruction.  The pointer is an owning pointer and
@@ -174,22 +193,18 @@ namespace llvm {
     /// Current AA implementation, just a cache.
     AliasAnalysis *AA;
     TargetData *TD;
+    OwningPtr<PredIteratorCache> PredCache;
   public:
-    MemoryDependenceAnalysis() : FunctionPass(&ID) {}
+    MemoryDependenceAnalysis();
+    ~MemoryDependenceAnalysis();
     static char ID;
 
     /// Pass Implementation stuff.  This doesn't do any analysis eagerly.
     bool runOnFunction(Function &);
     
     /// Clean up memory in between runs
-    void releaseMemory() {
-      LocalDeps.clear();
-      NonLocalDeps.clear();
-      NonLocalDeps.clear();
-      ReverseLocalDeps.clear();
-      ReverseNonLocalDeps.clear();
-    }
-
+    void releaseMemory();
+    
     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
     /// and Alias Analysis.
     ///
@@ -200,8 +215,8 @@ namespace llvm {
     /// this on non-memory instructions.
     MemDepResult getDependency(Instruction *QueryInst);
 
-    /// getNonLocalDependency - Perform a full dependency query for the
-    /// specified instruction, returning the set of blocks that the value is
+    /// getNonLocalCallDependency - Perform a full dependency query for the
+    /// specified call, returning the set of blocks that the value is
     /// potentially live across.  The returned set of results will include a
     /// "NonLocal" result for all blocks where the value is live across.
     ///
@@ -212,16 +227,14 @@ namespace llvm {
     /// invalidated on the next non-local query or when an instruction is
     /// removed.  Clients must copy this data if they want it around longer than
     /// that.
-    const NonLocalDepInfo &getNonLocalDependency(Instruction *QueryInst);
+    const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS);
     
     
     /// getNonLocalPointerDependency - Perform a full dependency query for an
     /// access to the specified (non-volatile) memory location, returning the
     /// set of instructions that either define or clobber the value.
     ///
-    /// This method assumes the pointer has a "NonLocal" dependency within BB
-    /// and assumes that Result is empty when you call it.
-    ///
+    /// This method assumes the pointer has a "NonLocal" dependency within BB.
     void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
                                       BasicBlock *BB,
                                      SmallVectorImpl<NonLocalDepEntry> &Result);
@@ -231,17 +244,24 @@ namespace llvm {
     void removeInstruction(Instruction *InstToRemove);
     
   private:
-    
-    /// getDependencyFrom - Return the instruction on which the memory location
-    /// '*Pointer' depends.  This starts scanning from the instruction before
-    /// the position indicated by ScanIt.
     MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize,
                                           bool isLoad, 
                                           BasicBlock::iterator ScanIt,
                                           BasicBlock *BB);
-    MemDepResult getCallSiteDependencyFrom(CallSite C,
+    MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall,
                                            BasicBlock::iterator ScanIt,
                                            BasicBlock *BB);
+    void getNonLocalPointerDepFromBB(Value *Pointer, uint64_t Size,
+                                     bool isLoad, BasicBlock *BB,
+                                     SmallVectorImpl<NonLocalDepEntry> &Result,
+                                     SmallPtrSet<BasicBlock*, 64> &Visited);
+    MemDepResult GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,
+                                         bool isLoad, BasicBlock *BB,
+                                         NonLocalDepInfo *Cache,
+                                         unsigned NumSortedEntries);
+
+    
+    void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
     
     /// verifyRemoved - Verify that the specified instruction does not occur
     /// in our internal data structures.