From 9a193fd8ae630478123938e12b56f84c5b2227b9 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Sun, 7 Dec 2008 02:56:57 +0000
Subject: [PATCH] Some internal refactoring to make it easier to cache results.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60650 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/MemoryDependenceAnalysis.h | 12 ++++---
 lib/Analysis/MemoryDependenceAnalysis.cpp        | 43 ++++++++++++++----------
 2 files changed, 34 insertions(+), 21 deletions(-)

diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index 819035dbd25..e2dd6629b74 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -151,7 +151,7 @@ namespace llvm {
     typedef std::pair<BasicBlock*, MemDepResult> NonLocalDepEntry;
     typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
   private:
-    
+   
     /// PerInstNLInfo - This is the instruction we keep for each cached access
     /// that we have for an instruction.  The pointer is an owning pointer and
     /// the bool indicates whether we have any dirty bits in the set.
@@ -219,9 +219,7 @@ namespace llvm {
     /// access to the specified (non-volatile) memory location, returning the
     /// set of instructions that either define or clobber the value.
     ///
-    /// This method assumes the pointer has a "NonLocal" dependency within BB
-    /// and assumes that Result is empty when you call it.
-    ///
+    /// This method assumes the pointer has a "NonLocal" dependency within BB.
     void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
                                       BasicBlock *BB,
                                      SmallVectorImpl<NonLocalDepEntry> &Result);
@@ -243,6 +241,12 @@ namespace llvm {
                                            BasicBlock::iterator ScanIt,
                                            BasicBlock *BB);
     
+    void getNonLocalPointerDepInternal(Value *Pointer, uint64_t Size,
+                                       bool isLoad, BasicBlock *BB,
+                                      SmallVectorImpl<NonLocalDepEntry> &Result,
+                                       SmallPtrSet<BasicBlock*, 64> &Visited);
+      
+    
     /// verifyRemoved - Verify that the specified instruction does not occur
     /// in our internal data structures.
     void verifyRemoved(Instruction *Inst) const;
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 9ac06c9ed7d..d74797c7cc0 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -437,53 +437,62 @@ MemoryDependenceAnalysis::getNonLocalDependency(Instruction *QueryInst) {
 void MemoryDependenceAnalysis::
 getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
                              SmallVectorImpl<NonLocalDepEntry> &Result) {
+  Result.clear();
+  
   // We know that the pointer value is live into FromBB find the def/clobbers
   // from presecessors.
-  SmallVector<std::pair<BasicBlock*, Value*>, 32> Worklist;
-  
-  for (pred_iterator PI = pred_begin(FromBB), E = pred_end(FromBB); PI != E;
-       ++PI)
-    // TODO: PHI TRANSLATE.
-    Worklist.push_back(std::make_pair(*PI, Pointer));
 
   const Type *EltTy = cast<PointerType>(Pointer->getType())->getElementType();
   uint64_t PointeeSize = TD->getTypeStoreSize(EltTy);
   
   // While we have blocks to analyze, get their values.
   SmallPtrSet<BasicBlock*, 64> Visited;
+  
+  for (pred_iterator PI = pred_begin(FromBB), E = pred_end(FromBB); PI != E;
+       ++PI) {
+    // TODO: PHI TRANSLATE.
+    getNonLocalPointerDepInternal(Pointer, PointeeSize, isLoad, *PI,
+                                  Result, Visited);
+  }
+}
+
+void MemoryDependenceAnalysis::
+getNonLocalPointerDepInternal(Value *Pointer, uint64_t PointeeSize,
+                              bool isLoad, BasicBlock *StartBB,
+                              SmallVectorImpl<NonLocalDepEntry> &Result,
+                              SmallPtrSet<BasicBlock*, 64> &Visited) {
+  SmallVector<BasicBlock*, 32> Worklist;
+  Worklist.push_back(StartBB);
+  
   while (!Worklist.empty()) {
-    FromBB = Worklist.back().first;
-    Pointer = Worklist.back().second;
-    Worklist.pop_back();
+    BasicBlock *BB = Worklist.pop_back_val();
     
     // Analyze the dependency of *Pointer in FromBB.  See if we already have
     // been here.
-    if (!Visited.insert(FromBB))
+    if (!Visited.insert(BB))
       continue;
     
     // FIXME: CACHE!
     
     MemDepResult Dep =
-      getPointerDependencyFrom(Pointer, PointeeSize, isLoad,
-                               FromBB->end(), FromBB);
+      getPointerDependencyFrom(Pointer, PointeeSize, isLoad, BB->end(), BB);
     
     // If we got a Def or Clobber, add this to the list of results.
     if (!Dep.isNonLocal()) {
-      Result.push_back(NonLocalDepEntry(FromBB, Dep));
+      Result.push_back(NonLocalDepEntry(BB, Dep));
       continue;
     }
     
     // Otherwise, we have to process all the predecessors of this block to scan
     // them as well.
-    for (pred_iterator PI = pred_begin(FromBB), E = pred_end(FromBB); PI != E;
-         ++PI)
+    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
       // TODO: PHI TRANSLATE.
-      Worklist.push_back(std::make_pair(*PI, Pointer));
+      Worklist.push_back(*PI);
+    }
   }
 }
 
 
-
 /// 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.
-- 
2.11.0