Speculatively revert r97010, "Add an argument to PHITranslateValue to specify

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

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index bf4689274b82ad7419a9e1d9760de82c5f86f1a8..164730c3ca06d0f61bef011cc8ea6ade7e28d92c 100644 (file)
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -674,6 +674,9 @@ namespace {
     ValueTable VN;
     DenseMap<BasicBlock*, ValueNumberScope*> localAvail;
 
+    // List of critical edges to be split between iterations.
+    SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
+
     // This transformation requires dominator postdominator info
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.addRequired<DominatorTree>();
@@ -701,6 +704,7 @@ namespace {
     Value *lookupNumber(BasicBlock *BB, uint32_t num);
     void cleanupGlobalSets();
     void verifyRemoved(const Instruction *I) const;
+    bool splitCriticalEdges();
   };
 
   char GVN::ID = 0;
@@ -1493,6 +1497,7 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
       V->takeName(LI);
     if (V->getType()->isPointerTy())
       MD->invalidateCachedPointerInfo(V);
+    VN.erase(LI);
     toErase.push_back(LI);
     NumGVNLoad++;
     return true;
@@ -1583,10 +1588,15 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
       continue;
     }
     PredLoads[Pred] = 0;
-    // We don't currently handle critical edges :(
+
     if (Pred->getTerminator()->getNumSuccessors() != 1) {
-      DEBUG(dbgs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '"
-            << Pred->getName() << "': " << *LI << '\n');
+      if (isa<IndirectBrInst>(Pred->getTerminator())) {
+        DEBUG(dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
+              << Pred->getName() << "': " << *LI << '\n');
+        return false;
+      }
+      unsigned SuccNum = GetSuccessorNumber(Pred, LoadBB);
+      toSplit.push_back(std::make_pair(Pred->getTerminator(), SuccNum));
       return false;
     }
   }
@@ -1697,6 +1707,8 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
     // Add the newly created load.
     ValuesPerBlock.push_back(AvailableValueInBlock::get(UnavailablePred,
                                                         NewLoad));
+    MD->invalidateCachedPointerInfo(LoadPtr);
+    DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
   }
 
   // Perform PHI construction.
@@ -1707,6 +1719,7 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
     V->takeName(LI);
   if (V->getType()->isPointerTy())
     MD->invalidateCachedPointerInfo(V);
+  VN.erase(LI);
   toErase.push_back(LI);
   NumPRELoad++;
   return true;
@@ -1767,6 +1780,7 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) {
       L->replaceAllUsesWith(AvailVal);
       if (AvailVal->getType()->isPointerTy())
         MD->invalidateCachedPointerInfo(AvailVal);
+      VN.erase(L);
       toErase.push_back(L);
       NumGVNLoad++;
       return true;
@@ -1812,6 +1826,7 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) {
     L->replaceAllUsesWith(StoredVal);
     if (StoredVal->getType()->isPointerTy())
       MD->invalidateCachedPointerInfo(StoredVal);
+    VN.erase(L);
     toErase.push_back(L);
     NumGVNLoad++;
     return true;
@@ -1841,6 +1856,7 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) {
     L->replaceAllUsesWith(AvailableVal);
     if (DepLI->getType()->isPointerTy())
       MD->invalidateCachedPointerInfo(DepLI);
+    VN.erase(L);
     toErase.push_back(L);
     NumGVNLoad++;
     return true;
@@ -1851,6 +1867,7 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) {
   // intervening stores, for example.
   if (isa<AllocaInst>(DepInst) || isMalloc(DepInst)) {
     L->replaceAllUsesWith(UndefValue::get(L->getType()));
+    VN.erase(L);
     toErase.push_back(L);
     NumGVNLoad++;
     return true;
@@ -1861,6 +1878,7 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) {
   if (IntrinsicInst* II = dyn_cast<IntrinsicInst>(DepInst)) {
     if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
       L->replaceAllUsesWith(UndefValue::get(L->getType()));
+      VN.erase(L);
       toErase.push_back(L);
       NumGVNLoad++;
       return true;
@@ -2004,6 +2022,8 @@ bool GVN::runOnFunction(Function& F) {
   while (ShouldContinue) {
     DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
     ShouldContinue = iterateOnFunction(F);
+    if (splitCriticalEdges())
+      ShouldContinue = true;
     Changed |= ShouldContinue;
     ++Iteration;
   }
@@ -2070,7 +2090,6 @@ bool GVN::processBlock(BasicBlock *BB) {
 /// 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;
   DenseMap<BasicBlock*, Value*> predMap;
   for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
        DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
@@ -2141,14 +2160,7 @@ bool GVN::performPRE(Function &F) {
       // 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) == CurrentBlock) {
-          SuccNum = i;
-          break;
-        }
-
+      unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
       if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
         toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
         continue;
@@ -2216,11 +2228,23 @@ 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);
+  if (splitCriticalEdges())
+    Changed = true;
 
-  return Changed || toSplit.size();
+  return Changed;
+}
+
+/// splitCriticalEdges - Split critical edges found during the previous
+/// iteration that may enable further optimization.
+bool GVN::splitCriticalEdges() {
+  if (toSplit.empty())
+    return false;
+  do {
+    std::pair<TerminatorInst*, unsigned> Edge = toSplit.pop_back_val();
+    SplitCriticalEdge(Edge.first, Edge.second, this);
+  } while (!toSplit.empty());
+  MD->invalidateCachedPredecessors();
+  return true;
 }
 
 /// iterateOnFunction - Executes one iteration of GVN