X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FADCE.cpp;h=e2e9e86216cde540bbc4536f86660ad47cb47857;hb=0006bd75201f340b95c1dbf71e50dc5de5ed9425;hp=56b219a585777ba3fe1a7d6349179f8cc41e1022;hpb=a61fab8c6d11bddeacec99c4b21278e1008fd08c;p=oota-llvm.git

diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp
index 56b219a5857..e2e9e86216c 100644
--- a/lib/Transforms/Scalar/ADCE.cpp
+++ b/lib/Transforms/Scalar/ADCE.cpp
@@ -10,23 +10,21 @@
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Type.h"
-#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/iTerminators.h"
 #include "llvm/iPHINode.h"
 #include "llvm/Constant.h"
 #include "llvm/Support/CFG.h"
 #include "Support/STLExtras.h"
 #include "Support/DepthFirstIterator.h"
-#include "Support/StatisticReporter.h"
+#include "Support/Statistic.h"
 #include <algorithm>
-#include <iostream>
 using std::cerr;
 using std::vector;
 
-static Statistic<> NumBlockRemoved("adce\t\t- Number of basic blocks removed");
-static Statistic<> NumInstRemoved ("adce\t\t- Number of instructions removed");
-
 namespace {
+  Statistic<> NumBlockRemoved("adce", "Number of basic blocks removed");
+  Statistic<> NumInstRemoved ("adce", "Number of instructions removed");
 
 //===----------------------------------------------------------------------===//
 // ADCE Class
@@ -55,8 +53,8 @@ public:
   // getAnalysisUsage - We require post dominance frontiers (aka Control
   // Dependence Graph)
   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.addRequired(PostDominatorTree::ID);
-    AU.addRequired(PostDominanceFrontier::ID);
+    AU.addRequired<PostDominatorTree>();
+    AU.addRequired<PostDominanceFrontier>();
   }
 
 
@@ -71,6 +69,12 @@ private:
 
   void markBlockAlive(BasicBlock *BB);
 
+
+  // dropReferencesOfDeadInstructionsInLiveBlock - Loop over all of the
+  // instructions in the specified basic block, dropping references on
+  // instructions that are dead according to LiveSet.
+  bool dropReferencesOfDeadInstructionsInLiveBlock(BasicBlock *BB);
+
   inline void markInstructionLive(Instruction *I) {
     if (LiveSet.count(I)) return;
     DEBUG(cerr << "Insn Live: " << I);
@@ -107,6 +111,32 @@ void ADCE::markBlockAlive(BasicBlock *BB) {
   markTerminatorLive(BB);
 }
 
+// dropReferencesOfDeadInstructionsInLiveBlock - Loop over all of the
+// instructions in the specified basic block, dropping references on
+// instructions that are dead according to LiveSet.
+bool ADCE::dropReferencesOfDeadInstructionsInLiveBlock(BasicBlock *BB) {
+  bool Changed = false;
+  for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; )
+    if (!LiveSet.count(I)) {              // Is this instruction alive?
+      I->dropAllReferences();             // Nope, drop references... 
+      if (PHINode *PN = dyn_cast<PHINode>(&*I)) {
+        // We don't want to leave PHI nodes in the program that have
+        // #arguments != #predecessors, so we remove them now.
+        //
+        PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
+        
+        // Delete the instruction...
+        I = BB->getInstList().erase(I);
+        Changed = true;
+      } else {
+        ++I;
+      }
+    } else {
+      ++I;
+    }
+  return Changed;
+}
+
 
 // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning
 // true if the function was modified.
@@ -192,13 +222,26 @@ bool ADCE::doADCE() {
   //
   PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
 
-  // If there are some blocks dead...
-  if (AliveBlocks.size() != Func->size()) {
-    // Insert a new entry node to eliminate the entry node as a special case.
-    BasicBlock *NewEntry = new BasicBlock();
-    NewEntry->getInstList().push_back(new BranchInst(&Func->front()));
-    Func->getBasicBlockList().push_front(NewEntry);
-    AliveBlocks.insert(NewEntry);    // This block is always alive!
+
+  if (AliveBlocks.size() == Func->size()) {  // No dead blocks?
+    for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
+      // Loop over all of the instructions in the function, telling dead
+      // instructions to drop their references.  This is so that the next sweep
+      // over the program can safely delete dead instructions without other dead
+      // instructions still refering to them.
+      //
+      dropReferencesOfDeadInstructionsInLiveBlock(I);
+    
+  } else {                                   // If there are some blocks dead...
+    // If the entry node is dead, insert a new entry node to eliminate the entry
+    // node as a special case.
+    //
+    if (!AliveBlocks.count(&Func->front())) {
+      BasicBlock *NewEntry = new BasicBlock();
+      NewEntry->getInstList().push_back(new BranchInst(&Func->front()));
+      Func->getBasicBlockList().push_front(NewEntry);
+      AliveBlocks.insert(NewEntry);    // This block is always alive!
+    }
     
     // Loop over all of the alive blocks in the function.  If any successor
     // blocks are not alive, we adjust the outgoing branches to branch to the
@@ -284,23 +327,7 @@ bool ADCE::doADCE() {
         // sweep over the program can safely delete dead instructions without
         // other dead instructions still refering to them.
         //
-        for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; )
-          if (!LiveSet.count(I)) {              // Is this instruction alive?
-            I->dropAllReferences();             // Nope, drop references... 
-            if (PHINode *PN = dyn_cast<PHINode>(&*I)) {
-              // We don't want to leave PHI nodes in the program that have
-              // #arguments != #predecessors, so we remove them now.
-              //
-              PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
-
-              // Delete the instruction...
-              I = BB->getInstList().erase(I);
-            } else {
-              ++I;
-            }
-          } else {
-            ++I;
-          }
+        dropReferencesOfDeadInstructionsInLiveBlock(BB);
       }
   }
 
@@ -324,9 +351,8 @@ bool ADCE::doADCE() {
         // Delete the old terminator instruction...
         BB->getInstList().pop_back();
         const Type *RetTy = Func->getReturnType();
-        Instruction *New = new ReturnInst(RetTy != Type::VoidTy ?
-                                          Constant::getNullValue(RetTy) : 0);
-        BB->getInstList().push_back(New);
+        BB->getInstList().push_back(new ReturnInst(RetTy != Type::VoidTy ?
+                                           Constant::getNullValue(RetTy) : 0));
       }
 
       BB->dropAllReferences();
@@ -341,9 +367,9 @@ bool ADCE::doADCE() {
   // instructions from alive blocks.
   //
   for (Function::iterator BI = Func->begin(); BI != Func->end(); )
-    if (!AliveBlocks.count(BI))
+    if (!AliveBlocks.count(BI)) {                // Delete dead blocks...
       BI = Func->getBasicBlockList().erase(BI);
-    else {
+    } else {                                     // Scan alive blocks...
       for (BasicBlock::iterator II = BI->begin(); II != --BI->end(); )
         if (!LiveSet.count(II)) {             // Is this instruction alive?
           // Nope... remove the instruction from it's basic block...