Enable GVN Load PRE.

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

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index 6593b9c622370810dd6b12a8f87c39c06b70ca3f..810ef6b5622de248db5520895c823405aa89ca18 100644 (file)
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -10,7 +10,7 @@
 // This pass performs global value numbering to eliminate fully redundant
 // instructions.  It also performs simple dead load elimination.
 //
-// Note that this pass does the value numbering itself, it does not use the
+// Note that this pass does the value numbering itself; it does not use the
 // ValueNumbering analysis passes.
 //
 //===----------------------------------------------------------------------===//
@@ -48,7 +48,7 @@ STATISTIC(NumPRELoad,   "Number of loads PRE'd");
 
 static cl::opt<bool> EnablePRE("enable-pre",
                                cl::init(true), cl::Hidden);
-cl::opt<bool> EnableLoadPRE("enable-load-pre"/*, cl::init(true)*/);
+cl::opt<bool> EnableLoadPRE("enable-load-pre", cl::init(true));
 
 //===----------------------------------------------------------------------===//
 //                         ValueTable Class
@@ -1125,6 +1125,11 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
                                 LI->getAlignment(),
                                 UnavailablePred->getTerminator());
   
+  SmallPtrSet<Instruction*, 4> &p = phiMap[LI->getPointerOperand()];
+  for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
+       I != E; ++I)
+    ValuesPerBlock.push_back(std::make_pair((*I)->getParent(), *I));
+  
   DenseMap<BasicBlock*, Value*> BlockReplValues;
   BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end());
   BlockReplValues[UnavailablePred] = NewLoad;
@@ -1153,8 +1158,16 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) {
   MemDepResult dep = MD->getDependency(L);
   
   // If the value isn't available, don't do anything!
-  if (dep.isClobber())
+  if (dep.isClobber()) {
+    DEBUG(
+      // fast print dep, using operator<< on instruction would be too slow
+      DOUT << "GVN: load ";
+      WriteAsOperand(*DOUT.stream(), L);
+      Instruction *I = dep.getInst();
+      DOUT << " is clobbered by " << *I;
+    );
     return false;
+  }
 
   // If it is defined in another block, try harder.
   if (dep.isNonLocal())
@@ -1294,9 +1307,28 @@ bool GVN::processInstruction(Instruction *I,
   uint32_t nextNum = VN.getNextUnusedValueNumber();
   unsigned num = VN.lookup_or_add(I);
   
+  if (BranchInst* BI = dyn_cast<BranchInst>(I)) {
+    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
+    
+    if (!BI->isConditional() || isa<Constant>(BI->getCondition()))
+      return false;
+    
+    Value* branchCond = BI->getCondition();
+    uint32_t condVN = VN.lookup_or_add(branchCond);
+    
+    BasicBlock* trueSucc = BI->getSuccessor(0);
+    BasicBlock* falseSucc = BI->getSuccessor(1);
+    
+    if (trueSucc->getSinglePredecessor())
+      localAvail[trueSucc]->table[condVN] = ConstantInt::getTrue();
+    if (falseSucc->getSinglePredecessor())
+      localAvail[falseSucc]->table[condVN] = ConstantInt::getFalse();
+
+    return false;
+    
   // Allocations are always uniquely numbered, so we can save time and memory
-  // by fast failing them.
-  if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
+  // by fast failing them.  
+  } else if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
     localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
     return false;
   }
@@ -1405,18 +1437,11 @@ bool GVN::runOnFunction(Function& F) {
 
 
 bool GVN::processBlock(BasicBlock* BB) {
-  DomTreeNode* DTN = DT->getNode(BB);
   // FIXME: Kill off toErase by doing erasing eagerly in a helper function (and
   // incrementing BI before processing an instruction).
   SmallVector<Instruction*, 8> toErase;
   bool changed_function = false;
   
-  if (DTN->getIDom())
-    localAvail[BB] =
-                  new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]);
-  else
-    localAvail[BB] = new ValueNumberScope(0);
-  
   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
        BI != BE;) {
     changed_function |= processInstruction(BI, toErase);
@@ -1467,12 +1492,13 @@ bool GVN::performPRE(Function& F) {
     for (BasicBlock::iterator BI = CurrentBlock->begin(),
          BE = CurrentBlock->end(); BI != BE; ) {
       Instruction *CurInst = BI++;
-      
+
       if (isa<AllocationInst>(CurInst) || isa<TerminatorInst>(CurInst) ||
-          isa<PHINode>(CurInst) || CurInst->mayReadFromMemory() ||
-          CurInst->mayWriteToMemory() || isa<DbgInfoIntrinsic>(CurInst))
+          isa<PHINode>(CurInst) || (CurInst->getType() == Type::VoidTy) ||
+          CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
+          isa<DbgInfoIntrinsic>(CurInst))
         continue;
-      
+
       uint32_t valno = VN.lookup(CurInst);
       
       // Look for the predecessors for PRE opportunities.  We're
@@ -1606,6 +1632,15 @@ bool GVN::performPRE(Function& F) {
 bool GVN::iterateOnFunction(Function &F) {
   cleanupGlobalSets();
 
+  for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()),
+       DE = df_end(DT->getRootNode()); DI != DE; ++DI) {
+    if (DI->getIDom())
+      localAvail[DI->getBlock()] =
+                   new ValueNumberScope(localAvail[DI->getIDom()->getBlock()]);
+    else
+      localAvail[DI->getBlock()] = new ValueNumberScope(0);
+  }
+
   // Top-down walk of the dominator tree
   bool changed = false;
 #if 0