Use information already present in the ValueTable to fast-fail when we know there...

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

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index bf2253fbd086c48d91b04351b492d2d10fa31ce2..86a8238ee425a5df8a19cffdb486262c4f06e6e9 100644 (file)
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -43,7 +43,7 @@ STATISTIC(NumGVNLoad, "Number of loads deleted");
 STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
 
 static cl::opt<bool> EnablePRE("enable-pre",
-                                cl::init(false), cl::Hidden);
+                               cl::init(false), cl::Hidden);
 
 //===----------------------------------------------------------------------===//
 //                         ValueTable Class
@@ -166,6 +166,7 @@ namespace {
       void setAliasAnalysis(AliasAnalysis* A) { AA = A; }
       void setMemDep(MemoryDependenceAnalysis* M) { MD = M; }
       void setDomTree(DominatorTree* D) { DT = D; }
+      uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
   };
 }
 
@@ -719,10 +720,11 @@ namespace {
     
     // This transformation requires dominator postdominator info
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.setPreservesCFG();
       AU.addRequired<DominatorTree>();
       AU.addRequired<MemoryDependenceAnalysis>();
       AU.addRequired<AliasAnalysis>();
+      
+      AU.addPreserved<DominatorTree>();
       AU.addPreserved<AliasAnalysis>();
       AU.addPreserved<MemoryDependenceAnalysis>();
     }
@@ -807,6 +809,11 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
   DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
   if (V != Phis.end() && !top_level) return V->second;
   
+  // If the block is unreachable, just return undef, since this path
+  // can't actually occur at runtime.
+  if (!getAnalysis<DominatorTree>().isReachableFromEntry(BB))
+    return Phis[BB] = UndefValue::get(orig->getType());
+  
   BasicBlock* singlePred = BB->getSinglePredecessor();
   if (singlePred) {
     Value *ret = GetValueForBlock(singlePred, orig, Phis);
@@ -1019,7 +1026,11 @@ bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad,
 }
 
 Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) {
-  ValueNumberScope* locals = localAvail[BB];
+  DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB);
+  if (I == localAvail.end())
+    return 0;
+  
+  ValueNumberScope* locals = I->second;
   
   while (locals) {
     DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num);
@@ -1048,11 +1059,12 @@ bool GVN::processInstruction(Instruction *I,
     return changed;
   }
   
+  uint32_t nextNum = VN.getNextUnusedValueNumber();
   unsigned num = VN.lookup_or_add(I);
   
   // Allocations are always uniquely numbered, so we can save time and memory
   // by fast failing them.
-  if (isa<AllocationInst>(I)) {
+  if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
     localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
     return false;
   }
@@ -1072,6 +1084,13 @@ bool GVN::processInstruction(Instruction *I,
     } else {
       localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
     }
+  
+  // If the number we were assigned was a brand new VN, then we don't
+  // need to do a lookup to see if the number already exists
+  // somewhere in the domtree: it can't!
+  } else if (num == nextNum) {
+    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
+    
   // Perform value-number based elimination
   } else if (Value* repl = lookupNumber(I->getParent(), num)) {
     // Remove it!
@@ -1082,7 +1101,7 @@ bool GVN::processInstruction(Instruction *I,
     I->replaceAllUsesWith(repl);
     toErase.push_back(I);
     return true;
-  } else if (!I->isTerminator()) {
+  } else {
     localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
   }
   
@@ -1167,9 +1186,9 @@ bool GVN::performPRE(Function& F) {
     
     for (BasicBlock::iterator BI = CurrentBlock->begin(),
          BE = CurrentBlock->end(); BI != BE; ) {
-      if (isa<AllocaInst>(BI) || isa<TerminatorInst>(BI) ||
-          isa<LoadInst>(BI) || isa<StoreInst>(BI) ||
-          isa<CallInst>(BI) || isa<PHINode>(BI)) {
+      if (isa<AllocationInst>(BI) || isa<TerminatorInst>(BI) ||
+          isa<PHINode>(BI) || BI->mayReadFromMemory() ||
+          BI->mayWriteToMemory()) {
         BI++;
         continue;
       }
@@ -1282,13 +1301,6 @@ bool GVN::performPRE(Function& F) {
         Phi->addIncoming(predMap[*PI], *PI);
       
       VN.add(Phi, valno);
-      
-      // The newly created PHI completely replaces the old instruction,
-      // so we need to update the maps to reflect this.
-      DomTreeNode* DTN = getAnalysis<DominatorTree>()[CurrentBlock];
-      for (DomTreeNode::iterator UI = DTN->begin(), UE = DTN->end();
-           UI != UE; ++UI)
-        localAvail[(*UI)->getBlock()]->table[valno] = Phi;
       localAvail[CurrentBlock]->table[valno] = Phi;
       
       BI->replaceAllUsesWith(Phi);
@@ -1328,7 +1340,7 @@ bool GVN::iterateOnFunction(Function &F) {
        DE = df_end(DT.getRootNode()); DI != DE; ++DI)
     changed |= processBlock(*DI);
   
-  if (!EnablePRE)
+  if (EnablePRE)
     changed |= performPRE(F);
   
   return changed;