X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FGVN.cpp;h=edd11e8e493b0dff793a18e7c4c49f80e1799925;hb=a37226af81bf10ba9f23ef065d8efc58877d3dc3;hp=d7e622857aeb736fd75e5bca2f99d878dbaf0422;hpb=febc7e3613007a159943917734baa35cc1b1411d;p=oota-llvm.git

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index d7e622857ae..edd11e8e493 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -13,12 +13,14 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "gvn"
-#include "llvm/Value.h"
+
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/BasicBlock.h"
-#include "llvm/Instructions.h"
-#include "llvm/Function.h"
+#include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
+#include "llvm/Function.h"
+#include "llvm/Instructions.h"
+#include "llvm/Value.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
@@ -144,8 +146,13 @@ namespace {
 
 namespace llvm {
 template <> struct DenseMapKeyInfo<Expression> {
-  static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); }
-  static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); }
+  static inline Expression getEmptyKey() {
+    return Expression(Expression::EMPTY);
+  }
+  
+  static inline Expression getTombstoneKey() {
+    return Expression(Expression::TOMBSTONE);
+  }
   
   static unsigned getHashValue(const Expression e) {
     unsigned hash = e.opcode;
@@ -158,8 +165,8 @@ template <> struct DenseMapKeyInfo<Expression> {
             (unsigned)((uintptr_t)e.type >> 9) +
             hash * 37;
     
-    for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end();
-         I != E; ++I)
+    for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
+         E = e.varargs.end(); I != E; ++I)
       hash = *I + hash * 37;
     
     return hash;
@@ -556,6 +563,11 @@ void ValueTable::clear() {
   nextValueNumber = 1;
 }
 
+/// erase - Remove a value from the value numbering
+void ValueTable::erase(Value* V) {
+  valueNumbering.erase(V);
+}
+
 //===----------------------------------------------------------------------===//
 //                       ValueNumberedSet Class
 //===----------------------------------------------------------------------===//
@@ -630,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();
@@ -649,10 +665,11 @@ namespace {
                             ValueNumberedSet& currAvail,
                             DenseMap<Value*, LoadInst*>& lastSeenLoad,
                             SmallVector<Instruction*, 4>& toErase);
-    bool processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase);
-    Value *performPHIConstruction(BasicBlock *BB, LoadInst* orig,
-                                  DenseMap<BasicBlock*, Value*> &Phis,
-                                  SmallPtrSet<BasicBlock*, 4>& visited);
+    bool processNonLocalLoad(LoadInst* L,
+                             SmallVector<Instruction*, 4>& toErase);
+    Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
+                            DenseMap<BasicBlock*, Value*> &Phis,
+                            bool top_level = false);
     void dump(DenseMap<BasicBlock*, Value*>& d);
   };
   
@@ -706,94 +723,122 @@ void GVN::dump(DenseMap<BasicBlock*, Value*>& d) {
 }
 
 
-Value *GVN::performPHIConstruction(BasicBlock *BB, LoadInst* orig,
-                                   DenseMap<BasicBlock*, Value*> &Phis,
-                                   SmallPtrSet<BasicBlock*, 4>& visited) {
-  DenseMap<BasicBlock*, Value*>::iterator DI = Phis.find(BB);
-  if (DI != Phis.end())
-    return DI->second;
-  
-  unsigned numPreds = std::distance(pred_begin(BB), pred_end(BB));
+/// GetValueForBlock - Get the value to use within the specified basic block.
+/// available values are in Phis.
+Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
+                               DenseMap<BasicBlock*, Value*> &Phis,
+                               bool top_level) { 
+                                 
+  // If we have already computed this value, return the previously computed val.
+  DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
+  if (V != Phis.end() && !top_level) return V->second;
+  
+  BasicBlock* singlePred = BB->getSinglePredecessor();
+  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)));
+  
+  if (Phis.count(BB) == 0)
+    Phis.insert(std::make_pair(BB, PN));
+  
+  bool all_same = true;
+  Value* first = 0;
+  
+  // Fill in the incoming values for the block.
+  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+    Value* val = GetValueForBlock(*PI, orig, Phis);
+    if (first == 0)
+      first = val;
+    else if (all_same && first != val)
+      all_same = false;
+    
+    PN->addIncoming(val, *PI);
+  }
   
-  if (numPreds == 1) {
-    DenseMap<BasicBlock*, Value*>::iterator DI = Phis.find(BB);
-    if (DI != Phis.end()) {
-      Phis.insert(std::make_pair(BB, DI->second));
-      return DI->second;
-    } else {
-      visited.insert(BB);
-      Value* domV = performPHIConstruction(*pred_begin(BB), orig, Phis, visited);
-      visited.erase(BB);
-      
-      Phis.insert(std::make_pair(BB, domV));
-      return domV;
-    }
-  } else {
-    PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", BB->begin());
-    PN->reserveOperandSpace(numPreds);
-    Phis[BB] = PN;
-    
-    visited.insert(BB);
-    // Fill in the incoming values for the block.
-    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
-      if (!visited.count(*PI))
-        PN->addIncoming(performPHIConstruction(*PI, orig, Phis, visited), *PI);
-      else {
-        if (Phis[*PI])
-          PN->addIncoming(Phis[*PI], *PI);
-        else
-          PN->addIncoming(PN, *PI);
-      }
-    visited.erase(BB);
+  if (all_same) {
+    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
     
-    bool all_same = PN->getNumIncomingValues() != 1;
-    Value* first = PN->getIncomingValue(0);
-    for (unsigned i = 1; i < PN->getNumIncomingValues(); ++i)
-      all_same &= (PN->getIncomingValue(i) == first);
+    MD.removeInstruction(PN);
+    PN->replaceAllUsesWith(first);
     
-    if (all_same) {
-      PN->eraseFromParent();
-      Phis[BB] = first;
-      return first;
-    } else {
-      return PN;
-    }
+    SmallVector<BasicBlock*, 4> toRemove;
+    for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
+         E = Phis.end(); I != E; ++I)
+      if (I->second == PN)
+        toRemove.push_back(I->first);
+    for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(),
+         E= toRemove.end(); I != E; ++I)
+      Phis[*I] = first;
+    
+    PN->eraseFromParent();
+    
+    Phis[BB] = first;
+    
+    return first;
   }
+
+  phiMap[orig->getPointerOperand()].insert(PN);
+  return PN;
 }
 
-bool GVN::processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase) {
+bool GVN::processNonLocalLoad(LoadInst* L,
+                              SmallVector<Instruction*, 4>& toErase) {
   MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
   
   DenseMap<BasicBlock*, Value*> deps;
-  bool ret = MD.getNonLocalDependency(L, deps);
-  if (!ret)
-    return false;
+  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) {
       return false;
-    } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
+    } else if (I->second == MemoryDependenceAnalysis::NonLocal) {
+      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 = performPHIConstruction(L->getParent(), L, repl, visited);
+  Value* v = GetValueForBlock(L->getParent(), L, repl, true);
   
   MD.removeInstruction(L);
   L->replaceAllUsesWith(v);
   toErase.push_back(L);
+  NumGVNLoad++;
 
   return true;
 }
@@ -875,6 +920,7 @@ bool GVN::processInstruction(Instruction* I,
   if (currAvail.test(num)) {
     Value* repl = find_leader(currAvail, num);
     
+    VN.erase(I);
     I->replaceAllUsesWith(repl);
     toErase.push_back(I);
     return true;
@@ -893,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;
   
@@ -915,11 +962,15 @@ bool GVN::runOnFunction(Function &F) {
       currAvail = availableOut[DI->getIDom()->getBlock()];
 
     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
-         BI != BE; ++BI) {
-      changed_function |= processInstruction(BI, currAvail, lastSeenLoad, toErase);
+         BI != BE; ) {
+      changed_function |= processInstruction(BI, currAvail,
+                                             lastSeenLoad, toErase);
       
       NumGVNInstr += toErase.size();
       
+      // Avoid iterator invalidation
+      ++BI;
+      
       for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
            E = toErase.end(); I != E; ++I)
         (*I)->eraseFromParent();