Add new BreakCriticalEdges pass

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

diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
index f67e6d671fa9d0ccab5625d3b0e511d24b13ac26..b84f1a378fa2970409e05a66e87ced6e050f01d7 100644 (file)
--- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
+++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
@@ -26,6 +26,9 @@
 #include "llvm/BasicBlock.h"
 #include "llvm/Constant.h"
 #include "llvm/Type.h"
+#include "Support/StatisticReporter.h"
+
+static Statistic<> NumPromoted("mem2reg\t\t- Number of alloca's promoted");
 
 using std::vector;
 using std::map;
@@ -44,17 +47,15 @@ namespace {
     map<BasicBlock*,vector<PHINode*> > NewPhiNodes; // the PhiNodes we're adding
 
   public:
-    const char *getPassName() const { return "Promote Memory to Register"; }
-
     // runOnFunction - To run this pass, first we calculate the alloca
     // instructions that are safe for promotion, then we promote each one.
     //
-    virtual bool runOnFunction(Function *F);
+    virtual bool runOnFunction(Function &F);
 
     // getAnalysisUsage - We need dominance frontiers
     //
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.addRequired(DominanceFrontier::ID);
+      AU.addRequired<DominanceFrontier>();
       AU.preservesCFG();
     }
 
@@ -62,9 +63,10 @@ namespace {
     void Traverse(BasicBlock *BB, BasicBlock *Pred, vector<Value*> &IncVals,
                   set<BasicBlock*> &Visited);
     bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx);
-    void FindSafeAllocas(Function *F);
+    void FindSafeAllocas(Function &F);
   };
 
+  RegisterOpt<PromotePass> X("mem2reg", "Promote Memory to Register");
 }  // end of anonymous namespace
 
 
@@ -74,37 +76,23 @@ namespace {
 static inline bool isSafeAlloca(const AllocaInst *AI) {
   if (AI->isArrayAllocation()) return false;
 
+  // Only allow direct loads and stores...
   for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end();
-       UI != UE; ++UI) {   // Loop over all of the uses of the alloca
-
-    // Only allow nonindexed memory access instructions...
-    if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(*UI)) {
-      if (MAI->getPointerOperand() != (Value*)AI)
-        return false;  // Reject stores of alloca pointer into some other loc.
-
-      if (MAI->hasIndices()) {  // indexed?
-        // Allow the access if there is only one index and the index is
-        // zero.
-        if (*MAI->idx_begin() != Constant::getNullValue(Type::UIntTy) ||
-            MAI->idx_begin()+1 != MAI->idx_end())
-          return false;
-      }
-    } else {
+       UI != UE; ++UI)     // Loop over all of the uses of the alloca
+    if (!isa<LoadInst>(*UI) && !isa<StoreInst>(*UI))
       return false;   // Not a load or store?
-    }
-  }
   
   return true;
 }
 
 // FindSafeAllocas - Find allocas that are safe to promote
 //
-void PromotePass::FindSafeAllocas(Function *F) {
-  BasicBlock *BB = F->getEntryNode();  // Get the entry node for the function
+void PromotePass::FindSafeAllocas(Function &F) {
+  BasicBlock &BB = F.getEntryNode();  // Get the entry node for the function
 
   // Look at all instructions in the entry node
-  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
-    if (AllocaInst *AI = dyn_cast<AllocaInst>(*I))       // Is it an alloca?
+  for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
+    if (AllocaInst *AI = dyn_cast<AllocaInst>(&*I))       // Is it an alloca?
       if (isSafeAlloca(AI)) {   // If safe alloca, add alloca to safe list
         AllocaLookup[AI] = Allocas.size();  // Keep reverse mapping
         Allocas.push_back(AI);
@@ -113,7 +101,7 @@ void PromotePass::FindSafeAllocas(Function *F) {
 
 
 
-bool PromotePass::runOnFunction(Function *F) {
+bool PromotePass::runOnFunction(Function &F) {
   // Calculate the set of safe allocas
   FindSafeAllocas(F);
 
@@ -175,7 +163,7 @@ bool PromotePass::runOnFunction(Function *F) {
   // and inserting the phi nodes we marked as necessary
   //
   set<BasicBlock*> Visited;         // The basic blocks we've already visited
-  Traverse(F->front(), 0, Values, Visited);
+  Traverse(F.begin(), 0, Values, Visited);
 
   // Remove all instructions marked by being placed in the KillList...
   //
@@ -183,10 +171,11 @@ bool PromotePass::runOnFunction(Function *F) {
     Instruction *I = KillList.back();
     KillList.pop_back();
 
-    I->getParent()->getInstList().remove(I);
-    delete I;
+    I->getParent()->getInstList().erase(I);
   }
 
+  NumPromoted += Allocas.size();
+
   // Purge data structurse so they are available the next iteration...
   Allocas.clear();
   AllocaLookup.clear();
@@ -207,14 +196,12 @@ bool PromotePass::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo) {
   // If the BB already has a phi node added for the i'th alloca then we're done!
   if (BBPNs[AllocaNo]) return false;
 
-  // Create a PhiNode using the dereferenced type...
+  // Create a PhiNode using the dereferenced type... and add the phi-node to the
+  // BasicBlock
   PHINode *PN = new PHINode(Allocas[AllocaNo]->getAllocatedType(),
-                            Allocas[AllocaNo]->getName()+".mem2reg");
+                            Allocas[AllocaNo]->getName()+".mem2reg",
+                            BB->begin());
   BBPNs[AllocaNo] = PN;
-
-  // Add the phi-node to the basic-block
-  BB->getInstList().push_front(PN);
-
   PhiNodes[AllocaNo].push_back(BB);
   return true;
 }
@@ -243,7 +230,7 @@ void PromotePass::Traverse(BasicBlock *BB, BasicBlock *Pred,
 
   // keep track of the value of each variable we're watching.. how?
   for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) {
-    Instruction *I = *II; //get the instruction
+    Instruction *I = II; // get the instruction
 
     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
       Value *Ptr = LI->getPointerOperand();