Don't insert nearly as many redundant phi nodes.

[oota-llvm.git] / lib / Transforms / Scalar / GVN.cpp

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index 2384e59ca0ea8c3e859485dc9b71b178cfbe8713..edd11e8e493b0dff793a18e7c4c49f80e1799925 100644 (file)
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -642,6 +642,10 @@ namespace {
     
     DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
     
+    typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
+    PhiMapType phiMap;
+    
+    
     // This transformation requires dominator postdominator info
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
@@ -726,19 +730,23 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
                                bool top_level) { 
                                  
   // If we have already computed this value, return the previously computed val.
-  Value *&V = Phis[BB];
-  if (V && ! top_level) return V;
+  DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
+  if (V != Phis.end() && !top_level) return V->second;
   
   BasicBlock* singlePred = BB->getSinglePredecessor();
-  if (singlePred)
-    return V = GetValueForBlock(singlePred, orig, Phis);
-  
+  if (singlePred) {
+    Value *ret = GetValueForBlock(singlePred, orig, Phis);
+    Phis[BB] = ret;
+    return ret;
+  }
   // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
   // now, then get values to fill in the incoming values for the PHI.
   PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle",
                             BB->begin());
   PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
-  V = PN;
+  
+  if (Phis.count(BB) == 0)
+    Phis.insert(std::make_pair(BB, PN));
   
   bool all_same = true;
   Value* first = 0;
@@ -776,6 +784,7 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
     return first;
   }
 
+  phiMap[orig->getPointerOperand()].insert(PN);
   return PN;
 }
 
@@ -787,6 +796,7 @@ bool GVN::processNonLocalLoad(LoadInst* L,
   MD.getNonLocalDependency(L, deps);
   
   DenseMap<BasicBlock*, Value*> repl;
+  
   for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
        I != E; ++I)
     if (I->second == MemoryDependenceAnalysis::None) {
@@ -795,24 +805,40 @@ bool GVN::processNonLocalLoad(LoadInst* L,
       continue;
     }else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
       if (S->getPointerOperand() == L->getPointerOperand())
-        repl.insert(std::make_pair(I->first, S->getOperand(0)));
+        repl[I->first] = S->getOperand(0);
       else
         return false;
     } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
       if (LD->getPointerOperand() == L->getPointerOperand())
-        repl.insert(std::make_pair(I->first, LD));
+        repl[I->first] = LD;
       else
         return false;
     } else {
       return false;
     }
   
+  SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
+  for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
+       I != E; ++I) {
+    if ((*I)->getParent() == L->getParent()) {
+      MD.removeInstruction(L);
+      L->replaceAllUsesWith(*I);
+      toErase.push_back(L);
+      NumGVNLoad++;
+      
+      return true;
+    } else {
+      repl.insert(std::make_pair((*I)->getParent(), *I));
+    }
+  }
+  
   SmallPtrSet<BasicBlock*, 4> visited;
   Value* v = GetValueForBlock(L->getParent(), L, repl, true);
   
   MD.removeInstruction(L);
   L->replaceAllUsesWith(v);
   toErase.push_back(L);
+  NumGVNLoad++;
 
   return true;
 }
@@ -913,6 +939,7 @@ bool GVN::runOnFunction(Function &F) {
   // Clean out global sets from any previous functions
   VN.clear();
   availableOut.clear();
+  phiMap.clear();
  
   bool changed_function = false;