Use the PotDoms map to memoize 'dominating value' lookup. With this patch,

LCSSA is still the slowest pass when gccas'ing 252.eon, but now it only takes
39s instead of 289s. :)

llvm-svn: 28776

1 files changed, 14 insertions, 17 deletions

diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp
index 3c70f735e88..01279d8f330 100644
--- a/llvm/lib/Transforms/Utils/LCSSA.cpp
+++ b/llvm/lib/Transforms/Utils/LCSSA.cpp
@@ -74,8 +74,12 @@ namespace {
   private:
     SetVector<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L);
     Instruction *getValueDominatingBlock(BasicBlock *BB,
+                                 std::map<BasicBlock*, Instruction*>& PotDoms) {
+      return getValueDominatingDTNode(DT->getNode(BB), PotDoms);
+    }
+    Instruction *getValueDominatingDTNode(DominatorTree::Node *Node,
                                   std::map<BasicBlock*, Instruction*>& PotDoms);
-                                  
+                                      
     /// inLoop - returns true if the given block is within the current loop
     const bool inLoop(BasicBlock* B) {
       return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
@@ -237,8 +241,8 @@ void LCSSA::processInstruction(Instruction* Instr,
         }
       }
     } else {
-       Value *NewVal = getValueDominatingBlock((*II)->getParent(), Phis);
-       (*II)->replaceUsesOfWith(Instr, NewVal);
+      Value *NewVal = getValueDominatingBlock((*II)->getParent(), Phis);
+      (*II)->replaceUsesOfWith(Instr, NewVal);
     }
   }
 }
@@ -275,19 +279,12 @@ SetVector<Instruction*> LCSSA::getLoopValuesUsedOutsideLoop(Loop *L) {
 
 /// getValueDominatingBlock - Return the value within the potential dominators
 /// map that dominates the given block.
-Instruction *LCSSA::getValueDominatingBlock(BasicBlock *BB,
-                                 std::map<BasicBlock*, Instruction*>& PotDoms) {
-  DominatorTree::Node* bbNode = DT->getNode(BB);
-  while (bbNode != 0) {
-    std::map<BasicBlock*, Instruction*>::iterator I =
-                                               PotDoms.find(bbNode->getBlock());
-    if (I != PotDoms.end()) {
-      return (*I).second;
-    }
-    bbNode = bbNode->getIDom();
-  }
-  
-  assert(0 && "No dominating value found.");
+Instruction *LCSSA::getValueDominatingDTNode(DominatorTree::Node *Node,
+                              std::map<BasicBlock*, Instruction*>& PotDoms) {
+  assert(Node != 0 && "Didn't find dom value?");
+  Instruction *&CacheSlot = PotDoms[Node->getBlock()];
+  if (CacheSlot) return CacheSlot;
   
-  return 0;
+  // Otherwise, return the value of the idom and remember this for next time.
+  return CacheSlot = getValueDominatingDTNode(Node->getIDom(), PotDoms);
 }