Finally re-apply r46959. This is made feasible by the combination

[oota-llvm.git] / lib / Analysis / MemoryDependenceAnalysis.cpp

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index e881f799a6788297073ed8c520beab21accfc6ff..d5b0afccb9b01c23aae116334727fa5c9cfabe11 100644 (file)
--- 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");
@@ -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();
@@ -96,7 +97,7 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C,
   BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
   BasicBlock::iterator QI = C.getInstruction();
   
-  // If the starting point was specifiy, use it
+  // If the starting point was specified, use it
   if (start) {
     QI = start;
     blockBegin = start->getParent()->begin();
@@ -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,
@@ -521,6 +528,10 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
       // If we have dep info for rem, set them to it
       BasicBlock::iterator RI = depGraphEntry->second.first;
       RI++;
+      
+      // If RI is rem, then we use rem's immediate successor.
+      if (RI == (BasicBlock::iterator)rem) RI++;
+      
       newDep = RI;
     } else if ( (depGraphEntry->second.first == NonLocal ||
                  depGraphEntry->second.first == None ) &&