eliminate some malloc traffic, this speeds up mem2reg by 3.4%.

[oota-llvm.git] / lib / Transforms / Utils / PromoteMemoryToRegister.cpp

diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
index a2573b83e23789b5adcf48aabacded8f25251b81..a25ea6b54de4d537d24e5f7f5e0e57b01c199a1a 100644 (file)
--- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
+++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
@@ -23,9 +23,11 @@
 #include "llvm/Instructions.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/AliasSetTracker.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/StableBasicBlockNumbering.h"
+#include "llvm/Support/Compiler.h"
 #include <algorithm>
 using namespace llvm;
 
@@ -52,11 +54,11 @@ bool llvm::isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) {
 }
 
 namespace {
-  struct PromoteMem2Reg {
+  struct VISIBILITY_HIDDEN PromoteMem2Reg {
     /// Allocas - The alloca instructions being promoted.
     ///
     std::vector<AllocaInst*> Allocas;
-    std::vector<AllocaInst*> &RetryList;
+    SmallVector<AllocaInst*, 16> &RetryList;
     DominatorTree &DT;
     DominanceFrontier &DF;
     const TargetData &TD;
@@ -89,7 +91,7 @@ namespace {
 
   public:
     PromoteMem2Reg(const std::vector<AllocaInst*> &A,
-                   std::vector<AllocaInst*> &Retry, DominatorTree &dt,
+                   SmallVector<AllocaInst*, 16> &Retry, DominatorTree &dt,
                    DominanceFrontier &df, const TargetData &td,
                    AliasSetTracker *ast)
       : Allocas(A), RetryList(Retry), DT(dt), DF(df), TD(td), AST(ast) {}
@@ -147,7 +149,7 @@ void PromoteMem2Reg::run() {
     if (AI->use_empty()) {
       // If there are no uses of the alloca, just delete it now.
       if (AST) AST->deleteValue(AI);
-      AI->getParent()->getInstList().erase(AI);
+      AI->eraseFromParent();
 
       // Remove the alloca from the Allocas list, since it has been processed
       Allocas[AllocaNum] = Allocas.back();
@@ -331,7 +333,7 @@ void PromoteMem2Reg::run() {
 
       if (AST && isa<PointerType>(PN->getType()))
         AST->deleteValue(PN);
-      PN->getParent()->getInstList().erase(PN);
+      PN->eraseFromParent();
     }
 
     // Keep the reverse mapping of the 'Allocas' array.
@@ -377,7 +379,7 @@ void PromoteMem2Reg::run() {
   // The renamer uses the Visited set to avoid infinite loops.  Clear it now.
   Visited.clear();
 
-  // Remove the allocas themselves from the function...
+  // Remove the allocas themselves from the function.
   for (unsigned i = 0, e = Allocas.size(); i != e; ++i) {
     Instruction *A = Allocas[i];
 
@@ -388,9 +390,41 @@ void PromoteMem2Reg::run() {
     if (!A->use_empty())
       A->replaceAllUsesWith(UndefValue::get(A->getType()));
     if (AST) AST->deleteValue(A);
-    A->getParent()->getInstList().erase(A);
+    A->eraseFromParent();
   }
 
+  
+  // Loop over all of the PHI nodes and see if there are any that we can get
+  // rid of because they merge all of the same incoming values.  This can
+  // happen due to undef values coming into the PHI nodes.  This process is
+  // iterative, because eliminating one PHI node can cause others to be removed.
+  bool EliminatedAPHI = true;
+  while (EliminatedAPHI) {
+    EliminatedAPHI = false;
+    
+    for (std::map<BasicBlock*, std::vector<PHINode *> >::iterator I =
+           NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) {
+      std::vector<PHINode*> &PNs = I->second;
+      for (unsigned i = 0, e = PNs.size(); i != e; ++i) {
+        if (!PNs[i]) continue;
+
+        // If this PHI node merges  one value and/or undefs, get the value.
+        if (Value *V = PNs[i]->hasConstantValue(true)) {
+          if (!isa<Instruction>(V) ||
+              properlyDominates(cast<Instruction>(V), PNs[i])) {
+            if (AST && isa<PointerType>(PNs[i]->getType()))
+              AST->deleteValue(PNs[i]);
+            PNs[i]->replaceAllUsesWith(V);
+            PNs[i]->eraseFromParent();
+            PNs[i] = 0;
+            EliminatedAPHI = true;
+            continue;
+          }
+        }
+      }
+    }
+  }
+  
   // At this point, the renamer has added entries to PHI nodes for all reachable
   // code.  Unfortunately, there may be blocks which are not reachable, which
   // the renamer hasn't traversed.  If this is the case, the PHI nodes may not
@@ -403,25 +437,11 @@ void PromoteMem2Reg::run() {
     std::vector<BasicBlock*> Preds(pred_begin(I->first), pred_end(I->first));
     std::vector<PHINode*> &PNs = I->second;
     assert(!PNs.empty() && "Empty PHI node list??");
-
-    // Loop over all of the PHI nodes and see if there are any that we can get
-    // rid of because they merge all of the same incoming values.  This can
-    // happen due to undef values coming into the PHI nodes.
     PHINode *SomePHI = 0;
     for (unsigned i = 0, e = PNs.size(); i != e; ++i)
       if (PNs[i]) {
-        if (Value *V = PNs[i]->hasConstantValue(true)) {
-          if (!isa<Instruction>(V) ||
-              properlyDominates(cast<Instruction>(V), PNs[i])) {
-            if (AST && isa<PointerType>(PNs[i]->getType()))
-              AST->deleteValue(PNs[i]);
-            PNs[i]->replaceAllUsesWith(V);
-            PNs[i]->eraseFromParent();
-            PNs[i] = 0;
-          }
-        }
-        if (PNs[i])
-          SomePHI = PNs[i];
+        SomePHI = PNs[i];
+        break;
       }
 
     // Only do work here if there the PHI nodes are missing incoming values.  We
@@ -717,11 +737,12 @@ void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
   // If there is nothing to do, bail out...
   if (Allocas.empty()) return;
 
-  std::vector<AllocaInst*> RetryList;
+  SmallVector<AllocaInst*, 16> RetryList;
   PromoteMem2Reg(Allocas, RetryList, DT, DF, TD, AST).run();
 
   // PromoteMem2Reg may not have been able to promote all of the allocas in one
   // pass, run it again if needed.
+  std::vector<AllocaInst*> NewAllocas;
   while (!RetryList.empty()) {
     // If we need to retry some allocas, this is due to there being no store
     // before a read in a local block.  To counteract this, insert a store of
@@ -733,8 +754,9 @@ void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
                     RetryList[i], ++BBI);
     }
 
-    std::vector<AllocaInst*> NewAllocas;
-    std::swap(NewAllocas, RetryList);
+    NewAllocas.assign(RetryList.begin(), RetryList.end());
+    RetryList.clear();
     PromoteMem2Reg(NewAllocas, RetryList, DT, DF, TD, AST).run();
+    NewAllocas.clear();
   }
 }