Correctly extract the ValueType from a VTSDNode.

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

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 11a80091085ea0f840d217a2b2b44731e02d0b03..538a394d46d7b3332f90a53651c30284279d65c7 100644 (file)
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -21,13 +21,20 @@
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Target/TargetData.h"
+#include "llvm/ADT/Statistic.h"
+
+#define DEBUG_TYPE "memdep"
 
 using namespace llvm;
 
+STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
+STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
+
 char MemoryDependenceAnalysis::ID = 0;
   
 Instruction* const MemoryDependenceAnalysis::NonLocal = (Instruction*)-3;
 Instruction* const MemoryDependenceAnalysis::None = (Instruction*)-4;
+Instruction* const MemoryDependenceAnalysis::Dirty = (Instruction*)-5;
   
 // Register this pass...
 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
@@ -128,6 +135,13 @@ void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
                                          DenseMap<BasicBlock*, Value*>& resp) {
   // Set of blocks that we've already visited in our DFS
   SmallPtrSet<BasicBlock*, 4> visited;
+  // If we're updating a dirtied cache entry, we don't need to reprocess
+  // already computed entries.
+  for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), 
+       E = resp.end(); I != E; ++I)
+    if (I->second != Dirty)
+      visited.insert(I->first);
+  
   // Current stack of the DFS
   SmallVector<BasicBlock*, 4> stack;
   stack.push_back(block);
@@ -204,18 +218,33 @@ void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
                                          DenseMap<BasicBlock*, Value*>& resp) {
   if (depGraphNonLocal.count(query)) {
-    resp = depGraphNonLocal[query];
-    return;
-  }
-  
-  // First check that we don't actually have a local dependency.
-  Instruction* localDep = getDependency(query);
-  if (localDep != NonLocal) {
-    resp.insert(std::make_pair(query->getParent(),localDep));
+    DenseMap<BasicBlock*, Value*>& cached = depGraphNonLocal[query];
+    NumCacheNonlocal++;
+    
+    SmallVector<BasicBlock*, 4> dirtied;
+    for (DenseMap<BasicBlock*, Value*>::iterator I = cached.begin(),
+         E = cached.end(); I != E; ++I)
+      if (I->second == Dirty)
+        dirtied.push_back(I->first);
+    
+    for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(),
+         E = dirtied.end(); I != E; ++I) {
+      Instruction* localDep = getDependency(query, 0, *I);
+      if (localDep != NonLocal)
+        cached[*I] = localDep;
+      else {
+        cached.erase(*I);
+        nonLocalHelper(query, *I, cached);
+      }
+    }
+    
+    resp = cached;
+    
     return;
-  }
+  } else
+    NumUncacheNonlocal++;
   
-  // If not, go ahead and search for non-local ones.
+  // If not, go ahead and search for non-local deps.
   nonLocalHelper(query, query->getParent(), resp);
   
   // Update the non-local dependency cache
@@ -424,11 +453,15 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
     reverseDep.erase(rem);
   }
   
-  if (depGraphNonLocal.count(rem)) {
+  if (reverseDepNonLocal.count(rem)) {
     SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[rem];
     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
          I != E; ++I)
-      depGraphNonLocal.erase(*I);
+      for (DenseMap<BasicBlock*, Value*>::iterator DI =
+           depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
+           DI != DE; ++DI)
+        if (DI->second == rem)
+          DI->second = Dirty;
     
     reverseDepNonLocal.erase(rem);
   }