diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index 0b8dec8..067bbcb 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -37,12 +37,20 @@
             depMapType;
     depMapType depGraphLocal;
 
+    // A map from instructions to their non-local dependencies.
+    typedef DenseMap<Instruction*, DenseMap<BasicBlock*, Value*> >
+            nonLocalDepMapType;
+    nonLocalDepMapType depGraphNonLocal;
+    
     // A reverse mapping form dependencies to the dependees.  This is
     // used when removing instructions to keep the cache coherent.
-    typedef DenseMap<Instruction*, SmallPtrSet<Instruction*, 4> >
+    typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> >
             reverseDepMapType;
     reverseDepMapType reverseDep;
     
+    // A reverse mapping form dependencies to the non-local dependees.
+    reverseDepMapType reverseDepNonLocal;
+    
   public:
     // Special marker indicating that the query has no dependency
     // in the specified block.
@@ -61,7 +69,9 @@
     /// Clean up memory in between runs
     void releaseMemory() {
       depGraphLocal.clear();
+      depGraphNonLocal.clear();
       reverseDep.clear();
+      reverseDepNonLocal.clear();
     }
 
     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 605dca1..11a8009 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -203,6 +203,11 @@
 /// blocks between the query and its dependencies.
 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) {
@@ -212,6 +217,13 @@
   
   // If not, go ahead and search for non-local ones.
   nonLocalHelper(query, query->getParent(), resp);
+  
+  // Update the non-local dependency cache
+  for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end();
+       I != E; ++I) {
+    depGraphNonLocal[query].insert(*I);
+    reverseDepNonLocal[I->second].insert(query);
+  }
 }
 
 /// getDependency - Return the instruction on which a memory operation
@@ -380,8 +392,6 @@
   Instruction* newDep = NonLocal;
 
   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 &&
@@ -410,8 +420,18 @@
       // Mark it as unconfirmed as long as it is not the non-local flag
       depGraphLocal[*I] = std::make_pair(newDep, !newDep);
     }
+    
     reverseDep.erase(rem);
   }
+  
+  if (depGraphNonLocal.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);
+    
+    reverseDepNonLocal.erase(rem);
+  }
 
   getAnalysis<AliasAnalysis>().deleteValue(rem);
 }