X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryDependenceAnalysis.cpp;h=2012ab473c98a697650a37a94129bc67a0c1f347;hb=ebb5a971d903aa4479bb2a21472597319a9b0086;hp=36c18f0c0b5f642d94351c29e4e3ec29917b04b0;hpb=63aa160b27935433208c34080e0458ce287030bb;p=oota-llvm.git

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 36c18f0c0b5..2012ab473c9 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -28,14 +28,12 @@
 
 using namespace llvm;
 
-namespace {
-  // Control the calculation of non-local dependencies by only examining the
-  // predecessors if the basic block has less than X amount (50 by default).
-  cl::opt<int> 
-  PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50),
-            cl::desc("Control the calculation of non-local"
-                     "dependencies (default = 50)"));           
-}
+// Control the calculation of non-local dependencies by only examining the
+// predecessors if the basic block has less than X amount (50 by default).
+static cl::opt<int> 
+PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50),
+          cl::desc("Control the calculation of non-local"
+                   "dependencies (default = 50)"));           
 
 STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
 STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
@@ -48,7 +46,7 @@ Instruction* const MemoryDependenceAnalysis::Dirty = (Instruction*)-5;
   
 // Register this pass...
 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
-                                                "Memory Dependence Analysis");
+                                                "Memory Dependence Analysis", false, true);
 
 void MemoryDependenceAnalysis::ping(Instruction *D) {
   for (depMapType::iterator I = depGraphLocal.begin(), E = depGraphLocal.end();
@@ -60,6 +58,9 @@ void MemoryDependenceAnalysis::ping(Instruction *D) {
   for (nonLocalDepMapType::iterator I = depGraphNonLocal.begin(), E = depGraphNonLocal.end();
        I != E; ++I) {
     assert(I->first != D);
+    for (DenseMap<BasicBlock*, Value*>::iterator II = I->second.begin(),
+         EE = I->second.end(); II  != EE; ++II)
+      assert(II->second != D);
   }
 
   for (reverseDepMapType::iterator I = reverseDep.begin(), E = reverseDep.end();
@@ -99,11 +100,11 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C,
   // If the starting point was specifiy, use it
   if (start) {
     QI = start;
-    blockBegin = start->getParent()->end();
+    blockBegin = start->getParent()->begin();
   // If the starting point wasn't specified, but the block was, use it
   } else if (!start && block) {
     QI = block->end();
-    blockBegin = block->end();
+    blockBegin = block->begin();
   }
   
   // Walk backwards through the block, looking for dependencies
@@ -131,11 +132,10 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C,
       
       // FreeInsts erase the entire structure
       pointerSize = ~0UL;
-    } else if (isa<CallInst>(QI)) {
+    } else if (CallSite::get(QI).getInstruction() != 0) {
       AliasAnalysis::ModRefBehavior result =
                    AA.getModRefBehavior(CallSite::get(QI));
-      if (result != AliasAnalysis::DoesNotAccessMemory &&
-          result != AliasAnalysis::OnlyReadsMemory) {
+      if (result != AliasAnalysis::DoesNotAccessMemory) {
         if (!start && !block) {
           cachedResult.first = QI;
           cachedResult.second = true;
@@ -181,7 +181,9 @@ void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
   
   // Current stack of the DFS
   SmallVector<BasicBlock*, 4> stack;
-  stack.push_back(block);
+  for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
+       PI != PE; ++PI)
+    stack.push_back(*PI);
   
   // Do a basic DFS
   while (!stack.empty()) {
@@ -208,7 +210,7 @@ void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
     // If we re-encounter the starting block, we still need to search it
     // because there might be a dependency in the starting block AFTER
     // the position of the query.  This is necessary to get loops right.
-    } else if (BB == block && stack.size() > 1) {
+    } else if (BB == block) {
       visited.insert(BB);
       
       Instruction* localDep = getDependency(query, 0, BB);
@@ -280,6 +282,11 @@ void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
     
     resp = cached;
     
+    // Update the reverse non-local dependency cache
+    for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end();
+         I != E; ++I)
+      reverseDepNonLocal[I->second].insert(query);
+    
     return;
   } else
     NumUncacheNonlocal++;
@@ -296,7 +303,7 @@ void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
 }
 
 /// getDependency - Return the instruction on which a memory operation
-/// depends.  The local paramter indicates if the query should only
+/// depends.  The local parameter indicates if the query should only
 /// evaluate dependencies within the same basic block.
 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
                                                      Instruction* start,
@@ -457,6 +464,46 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
   return NonLocal;
 }
 
+/// dropInstruction - Remove an instruction from the analysis, making 
+/// absolutely conservative assumptions when updating the cache.  This is
+/// useful, for example when an instruction is changed rather than removed.
+void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
+  depMapType::iterator depGraphEntry = depGraphLocal.find(drop);
+  if (depGraphEntry != depGraphLocal.end())
+    reverseDep[depGraphEntry->second.first].erase(drop);
+  
+  // Drop dependency information for things that depended on this instr
+  SmallPtrSet<Instruction*, 4>& set = reverseDep[drop];
+  for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
+       I != E; ++I)
+    depGraphLocal.erase(*I);
+  
+  depGraphLocal.erase(drop);
+  reverseDep.erase(drop);
+  
+  for (DenseMap<BasicBlock*, Value*>::iterator DI =
+       depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end();
+       DI != DE; ++DI)
+    if (DI->second != None)
+      reverseDepNonLocal[DI->second].erase(drop);
+  
+  if (reverseDepNonLocal.count(drop)) {
+    SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[drop];
+    for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
+         I != E; ++I)
+      for (DenseMap<BasicBlock*, Value*>::iterator DI =
+           depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
+           DI != DE; ++DI)
+        if (DI->second == drop)
+          DI->second = Dirty;
+  }
+  
+  reverseDepNonLocal.erase(drop);
+  nonLocalDepMapType::iterator I = depGraphNonLocal.find(drop);
+  if (I != depGraphNonLocal.end())
+    depGraphNonLocal.erase(I);
+}
+
 /// removeInstruction - Remove an instruction from the dependence analysis,
 /// updating the dependence of instructions that previously depended on it.
 /// This method attempts to keep the cache coherent using the reverse map.
@@ -473,7 +520,7 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
   depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
 
   if (depGraphEntry != depGraphLocal.end()) {
-    reverseDep[depGraphLocal[rem].first].erase(rem);
+    reverseDep[depGraphEntry->second.first].erase(rem);
     
     if (depGraphEntry->second.first != NonLocal &&
         depGraphEntry->second.first != None &&