Teach BasicAA about noalias parameter attributes, but do it correctly this time.

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

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 4bd877142a2ba99213b59cd259ec0656cae838a8..a280fffb59b83ea16e71f66bb76de4445c808e56 100644 (file)
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -101,61 +101,62 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruc
   return NonLocal;
 }
 
-bool MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
+void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
                                               BasicBlock* block,
-                                              DenseMap<BasicBlock*, Value*>& resp,
-                                              SmallPtrSet<BasicBlock*, 4>& visited) {
-  if (resp.count(block))
-    return resp[block] != None;
+                                              DenseMap<BasicBlock*, Value*>& resp) {
+  SmallPtrSet<BasicBlock*, 4> visited;
+  SmallVector<BasicBlock*, 4> stack;
+  stack.push_back(block);
   
-  Instruction* localDep = getDependency(query, 0, block);
-  if (localDep != NonLocal) {
-    resp.insert(std::make_pair(block, localDep));
-    return true;
+  while (!stack.empty()) {
+    BasicBlock* BB = stack.back();
+    
+    visited.insert(BB);
+    
+    if (resp.count(BB)) {
+      stack.pop_back();
+      continue;
+    }
+    
+    if (BB != block) {
+      Instruction* localDep = getDependency(query, 0, BB);
+      if (localDep != NonLocal) {
+        resp.insert(std::make_pair(BB, localDep));
+        continue;
+      }
+    }
+    
+    bool predOnStack = false;
+    bool inserted = false;
+    for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+         PI != PE; ++PI)
+      if (!visited.count(*PI)) {
+        stack.push_back(*PI);
+        inserted = true;
+      } else
+        predOnStack = true;
+    
+    if (inserted)
+      continue;
+    else if (!inserted && !predOnStack) {
+      resp.insert(std::make_pair(BB, None));
+    } else if (!inserted && predOnStack){
+      resp.insert(std::make_pair(BB, NonLocal));
+    }
+    
+    stack.pop_back();
   }
-  
-  visited.insert(block);
-  
-  bool inserted = false;
-  bool predOnStack = false;
-  for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
-       PI != PE; ++PI)
-    if (!visited.count(*PI))
-      inserted |= nonLocalHelper(query, *PI, resp, visited);
-    else
-      predOnStack = true;
-
-  visited.erase(block);
-
-  if (!inserted && !predOnStack)
-    resp.insert(std::make_pair(block, None));
-  
-  return inserted;
 }
 
-bool MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
+void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
                                                      DenseMap<BasicBlock*, Value*>& resp) {
   Instruction* localDep = getDependency(query);
   if (localDep != NonLocal) {
     resp.insert(std::make_pair(query->getParent(), localDep));
-    return true;
-  }
-  
-  bool inserted = false;
-  SmallPtrSet<BasicBlock*, 4> visited;
-  visited.insert(query->getParent());
-  
-  BasicBlock* parent = query->getParent();
-  for (pred_iterator PI = pred_begin(parent), PE = pred_end(parent);
-       PI != PE; ++PI) {
-    if (!visited.count(*PI))
-      inserted |= nonLocalHelper(query, *PI, resp, visited);
+    return;
   }
   
-  if (!inserted)
-    resp.insert(std::make_pair(query->getParent(), None));
-  
-  return inserted;
+  nonLocalHelper(query, query->getParent(), resp);
 }
 
 /// getDependency - Return the instruction on which a memory operation
@@ -306,33 +307,40 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
   // Figure out the new dep for things that currently depend on rem
   Instruction* newDep = NonLocal;
-  if (depGraphLocal[rem].first != NonLocal &&
-      depGraphLocal[rem].second) {
-    // If we have dep info for rem, set them to it
-    BasicBlock::iterator RI = depGraphLocal[rem].first;
-    RI++;
-    newDep = RI;
-  } else if (depGraphLocal[rem].first == NonLocal &&
-             depGraphLocal[rem].second ) {
-    // If we have a confirmed non-local flag, use it
-    newDep = NonLocal;
-  } else {
-    // Otherwise, use the immediate successor of rem
-    // NOTE: This is because, when getDependence is called, it will first check
-    // the immediate predecessor of what is in the cache.
-    BasicBlock::iterator RI = rem;
-    RI++;
-    newDep = RI;
-  }
 
-  std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
-  while (I->first == rem) {
-    // Insert the new dependencies
-    // Mark it as unconfirmed as long as it is not the non-local flag
-    depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
-    reverseDep.erase(I);
-    I = reverseDep.find(rem);
+  depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
+  // We assume here that it's not in the reverse map if it's not in
+  // the dep map.  Checking it could be expensive, so don't do it.
+
+  if (depGraphEntry != depGraphLocal.end()) {
+    if (depGraphEntry->second.first != NonLocal &&
+        depGraphEntry->second.second) {
+      // If we have dep info for rem, set them to it
+      BasicBlock::iterator RI = depGraphEntry->second.first;
+      RI++;
+      newDep = RI;
+    } else if (depGraphEntry->second.first == NonLocal &&
+               depGraphEntry->second.second ) {
+      // If we have a confirmed non-local flag, use it
+      newDep = NonLocal;
+    } else {
+      // Otherwise, use the immediate successor of rem
+      // NOTE: This is because, when getDependence is called, it will first check
+      // the immediate predecessor of what is in the cache.
+      BasicBlock::iterator RI = rem;
+      RI++;
+      newDep = RI;
+    }
+    
+    std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
+    while (I != reverseDep.end() && I->first == rem) {
+      // Insert the new dependencies
+      // Mark it as unconfirmed as long as it is not the non-local flag
+      depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
+      reverseDep.erase(I);
+      I = reverseDep.find(rem);
+    }
   }
-  
+
   getAnalysis<AliasAnalysis>().deleteValue(rem);
 }