X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FGVN.cpp;h=5564dbde1bfb311849d0648a87cf488780cc1adf;hb=2e9f0b1a323848f6d548c1e9eb16ece6a3881dbd;hp=c9eb24743280528e4fb6f18c383c8a315d5ec35f;hpb=b230372437183b8daffcd70fe784974ddf26d21b;p=oota-llvm.git

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index c9eb2474328..5564dbde1bf 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -32,14 +32,19 @@
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Support/CFG.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 using namespace llvm;
 
 STATISTIC(NumGVNInstr, "Number of instructions deleted");
 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);
+
 //===----------------------------------------------------------------------===//
 //                         ValueTable Class
 //===----------------------------------------------------------------------===//
@@ -687,6 +692,15 @@ namespace llvm {
   };
 }
 
+namespace {
+  struct VISIBILITY_HIDDEN ValueNumberScope {
+    ValueNumberScope* parent;
+    DenseMap<uint32_t, Value*> table;
+    
+    ValueNumberScope(ValueNumberScope* p) : parent(p) { }
+  };
+}
+
 namespace {
 
   class VISIBILITY_HIDDEN GVN : public FunctionPass {
@@ -697,7 +711,7 @@ namespace {
 
   private:
     ValueTable VN;
-    DenseMap<BasicBlock*, DenseMap<uint32_t, Value*> > localAvail;
+    DenseMap<BasicBlock*, ValueNumberScope*> localAvail;
     
     typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
     PhiMapType phiMap;
@@ -705,10 +719,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>();
     }
@@ -732,6 +747,7 @@ namespace {
     Value* CollapsePhi(PHINode* p);
     bool isSafeReplacement(PHINode* p, Instruction* inst);
     bool performPRE(Function& F);
+    Value* lookupNumber(BasicBlock* BB, uint32_t num);
   };
   
   char GVN::ID = 0;
@@ -1003,6 +1019,24 @@ bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad,
   return deletedLoad;
 }
 
+Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) {
+  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);
+    if (I != locals->table.end())
+      return I->second;
+    else
+      locals = locals->parent;
+  }
+  
+  return 0;
+}
+
 /// processInstruction - When calculating availability, handle an instruction
 /// by inserting it into the appropriate sets
 bool GVN::processInstruction(Instruction *I,
@@ -1013,7 +1047,7 @@ bool GVN::processInstruction(Instruction *I,
     
     if (!changed) {
       unsigned num = VN.lookup_or_add(L);
-      localAvail[I->getParent()].insert(std::make_pair(num, L));
+      localAvail[I->getParent()]->table.insert(std::make_pair(num, L));
     }
     
     return changed;
@@ -1024,7 +1058,7 @@ bool GVN::processInstruction(Instruction *I,
   // Allocations are always uniquely numbered, so we can save time and memory
   // by fast failing them.
   if (isa<AllocationInst>(I)) {
-    localAvail[I->getParent()].insert(std::make_pair(num, I));
+    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
     return false;
   }
   
@@ -1041,12 +1075,10 @@ bool GVN::processInstruction(Instruction *I,
       p->replaceAllUsesWith(constVal);
       toErase.push_back(p);
     } else {
-      localAvail[I->getParent()].insert(std::make_pair(num, I));
+      localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
     }
   // Perform value-number based elimination
-  } else if (localAvail[I->getParent()].count(num)) {
-    Value* repl = localAvail[I->getParent()][num];
-    
+  } else if (Value* repl = lookupNumber(I->getParent(), num)) {
     // Remove it!
     MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
     MD.removeInstruction(I);
@@ -1056,7 +1088,7 @@ bool GVN::processInstruction(Instruction *I,
     toErase.push_back(I);
     return true;
   } else if (!I->isTerminator()) {
-    localAvail[I->getParent()].insert(std::make_pair(num, I));
+    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
   }
   
   return false;
@@ -1090,8 +1122,10 @@ bool GVN::processBlock(DomTreeNode* DTN) {
   bool changed_function = false;
   
   if (DTN->getIDom())
-    localAvail.insert(std::make_pair(BB,
-                      localAvail[DTN->getIDom()->getBlock()]));
+    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;) {
@@ -1128,6 +1162,7 @@ bool GVN::processBlock(DomTreeNode* DTN) {
 /// control flow patterns and attempts to perform simple PRE at the join point.
 bool GVN::performPRE(Function& F) {
   bool changed = false;
+  SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
   for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
        DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
     BasicBlock* CurrentBlock = *DI;
@@ -1137,9 +1172,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;
       }
@@ -1155,19 +1190,29 @@ bool GVN::performPRE(Function& F) {
       unsigned numWith = 0;
       unsigned numWithout = 0;
       BasicBlock* PREPred = 0;
+      DenseMap<BasicBlock*, Value*> predMap;
       for (pred_iterator PI = pred_begin(CurrentBlock),
            PE = pred_end(CurrentBlock); PI != PE; ++PI) {
         // We're not interested in PRE where the block is its
-        // own predecessor.
-        if (*PI == CurrentBlock)
+        // own predecessor, on in blocks with predecessors
+        // that are not reachable.
+        if (*PI == CurrentBlock) {
+          numWithout = 2;
+          break;
+        } else if (!localAvail.count(*PI))  {
           numWithout = 2;
-          
-        if (!localAvail[*PI].count(valno)) {
+          break;
+        }
+        
+        DenseMap<uint32_t, Value*>::iterator predV = 
+                                            localAvail[*PI]->table.find(valno);
+        if (predV == localAvail[*PI]->table.end()) {
           PREPred = *PI;
           numWithout++;
-        } else if (localAvail[*PI][valno] == BI) {
+        } else if (predV->second == BI) {
           numWithout = 2;
         } else {
+          predMap[*PI] = predV->second;
           numWith++;
         }
       }
@@ -1179,6 +1224,24 @@ bool GVN::performPRE(Function& F) {
         continue;
       }
       
+      // We can't do PRE safely on a critical edge, so instead we schedule
+      // the edge to be split and perform the PRE the next time we iterate
+      // on the function.
+      unsigned succNum = 0;
+      for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors();
+           i != e; ++i)
+        if (PREPred->getTerminator()->getSuccessor(i) == PREPred) {
+          succNum = i;
+          break;
+        }
+        
+      if (isCriticalEdge(PREPred->getTerminator(), succNum)) {
+        toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum));
+        changed = true;
+        BI++;
+        continue;
+      }
+      
       // Instantiate the expression the in predecessor that lacked it.
       // Because we are going top-down through the block, all value numbers
       // will be available in the predecessor by the time we need them.  Any
@@ -1190,11 +1253,11 @@ bool GVN::performPRE(Function& F) {
         Value* op = BI->getOperand(i);
         if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op))
           PREInstr->setOperand(i, op);
-        else if (!localAvail[PREPred].count(VN.lookup(op))) {
+        else if (!lookupNumber(PREPred, VN.lookup(op))) {
           success = false;
           break;
         } else
-          PREInstr->setOperand(i, localAvail[PREPred][VN.lookup(op)]);
+          PREInstr->setOperand(i, lookupNumber(PREPred, VN.lookup(op)));
       }
       
       // Fail out if we encounter an operand that is not available in
@@ -1208,11 +1271,12 @@ bool GVN::performPRE(Function& F) {
       
       PREInstr->insertBefore(PREPred->getTerminator());
       PREInstr->setName(BI->getName() + ".pre");
+      predMap[PREPred] = PREInstr;
       VN.add(PREInstr, valno);
       NumGVNPRE++;
       
       // Update the availability map to include the new instruction.
-      localAvail[PREPred].insert(std::make_pair(valno, PREInstr));
+      localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr));
       
       // Create a PHI to make the value available in this block.
       PHINode* Phi = PHINode::Create(BI->getType(),
@@ -1220,20 +1284,13 @@ bool GVN::performPRE(Function& F) {
                                      CurrentBlock->begin());
       for (pred_iterator PI = pred_begin(CurrentBlock),
            PE = pred_end(CurrentBlock); PI != PE; ++PI)
-        Phi->addIncoming(localAvail[*PI][valno], *PI);
+        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.
-      for (DenseMap<BasicBlock*, DenseMap<uint32_t, Value*> >::iterator
-           UI = localAvail.begin(), UE = localAvail.end(); UI != UE; ++UI)
-        for (DenseMap<uint32_t, Value*>::iterator UUI = UI->second.begin(),
-             UUE = UI->second.end(); UUI != UUE; ++UUI)
-            if (UUI->second == BI)
-              UUI->second = Phi;
+      localAvail[CurrentBlock]->table[valno] = Phi;
       
       BI->replaceAllUsesWith(Phi);
+      VN.erase(BI);
       
       Instruction* erase = BI;
       BI++;
@@ -1243,6 +1300,10 @@ bool GVN::performPRE(Function& F) {
     }
   }
   
+  for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator
+       I = toSplit.begin(), E = toSplit.end(); I != E; ++I)
+    SplitCriticalEdge(I->first, I->second, this);
+  
   return changed;
 }
 
@@ -1250,9 +1311,13 @@ bool GVN::performPRE(Function& F) {
 bool GVN::iterateOnFunction(Function &F) {
   // Clean out global sets from any previous functions
   VN.clear();
-  localAvail.clear();
   phiMap.clear();
   
+  for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
+       I = localAvail.begin(), E = localAvail.end(); I != E; ++I)
+    delete I->second;
+  localAvail.clear();
+  
   DominatorTree &DT = getAnalysis<DominatorTree>();   
 
   // Top-down walk of the dominator tree
@@ -1260,7 +1325,9 @@ bool GVN::iterateOnFunction(Function &F) {
   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
        DE = df_end(DT.getRootNode()); DI != DE; ++DI)
     changed |= processBlock(*DI);
-    
-  changed |= performPRE(F);
+  
+  if (EnablePRE)
+    changed |= performPRE(F);
+  
   return changed;
 }