Fix bug: ADCE/2003-01-22-PredecessorProblem.ll
[oota-llvm.git] / lib / Transforms / Scalar / ADCE.cpp
index 01046b00337cdca5baadbdb005586bd126048b20..24ccee60344bd76b9663b9ebbd1e1639d413d780 100644 (file)
-//===- ADCE.cpp - Code to perform agressive dead code elimination ---------===//
+//===- ADCE.cpp - Code to perform aggressive dead code elimination --------===//
 //
-// This file implements "agressive" dead code elimination.  ADCE is DCe where
+// This file implements "aggressive" dead code elimination.  ADCE is DCe where
 // values are assumed to be dead until proven otherwise.  This is similar to 
 // SCCP, except applied to the liveness of values.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Transforms/Scalar/DCE.h"
-#include "llvm/Instruction.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Type.h"
-#include "llvm/Analysis/Dominators.h"
-#include "llvm/Analysis/Writer.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 <set>
+#include "Support/Statistic.h"
 #include <algorithm>
-#include <iostream>
 using std::cerr;
+using std::vector;
 
-#define DEBUG_ADCE 1
+namespace {
+  Statistic<> NumBlockRemoved("adce", "Number of basic blocks removed");
+  Statistic<> NumInstRemoved ("adce", "Number of instructions removed");
 
 //===----------------------------------------------------------------------===//
 // ADCE Class
 //
-// This class does all of the work of Agressive Dead Code Elimination.
+// This class does all of the work of Aggressive Dead Code Elimination.
 // It's public interface consists of a constructor and a doADCE() method.
 //
-class ADCE {
-  Method *M;                            // The method that we are working on...
+class ADCE : public FunctionPass {
+  Function *Func;                       // The function that we are working on
   std::vector<Instruction*> WorkList;   // Instructions that just became live
   std::set<Instruction*>    LiveSet;    // The set of live instructions
-  bool MadeChanges;
 
   //===--------------------------------------------------------------------===//
   // The public interface for this class
   //
 public:
-  // ADCE Ctor - Save the method to operate on...
-  inline ADCE(Method *m) : M(m), MadeChanges(false) {}
+  // Execute the Aggressive Dead Code Elimination Algorithm
+  //
+  virtual bool runOnFunction(Function &F) {
+    Func = &F;
+    bool Changed = doADCE();
+    assert(WorkList.empty());
+    LiveSet.clear();
+    return Changed;
+  }
+  // getAnalysisUsage - We require post dominance frontiers (aka Control
+  // Dependence Graph)
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.addRequired<PostDominatorTree>();
+    AU.addRequired<PostDominanceFrontier>();
+  }
 
-  // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
-  // true if the method was modified.
-  bool doADCE();
 
   //===--------------------------------------------------------------------===//
   // The implementation of this class
   //
 private:
+  // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning
+  // true if the function was modified.
+  //
+  bool doADCE();
+
+  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;
-#ifdef DEBUG_ADCE
-    cerr << "Insn Live: " << I;
-#endif
+    DEBUG(cerr << "Insn Live: " << I);
     LiveSet.insert(I);
     WorkList.push_back(I);
   }
 
   inline void markTerminatorLive(const BasicBlock *BB) {
-#ifdef DEBUG_ADCE
-    cerr << "Terminat Live: " << BB->getTerminator();
-#endif
+    DEBUG(cerr << "Terminat Live: " << BB->getTerminator());
     markInstructionLive((Instruction*)BB->getTerminator());
   }
+};
+
+  RegisterOpt<ADCE> X("adce", "Aggressive Dead Code Elimination");
+} // End of anonymous namespace
 
-  // fixupCFG - Walk the CFG in depth first order, eliminating references to 
-  // dead blocks.
+Pass *createAggressiveDCEPass() { return new ADCE(); }
+
+void ADCE::markBlockAlive(BasicBlock *BB) {
+  // Mark the basic block as being newly ALIVE... and mark all branches that
+  // this block is control dependant on as being alive also...
   //
-  BasicBlock *fixupCFG(BasicBlock *Head, std::set<BasicBlock*> &VisitedBlocks,
-                      const std::set<BasicBlock*> &AliveBlocks);
-};
+  PostDominanceFrontier &CDG = getAnalysis<PostDominanceFrontier>();
+
+  PostDominanceFrontier::const_iterator It = CDG.find(BB);
+  if (It != CDG.end()) {
+    // Get the blocks that this node is control dependant on...
+    const PostDominanceFrontier::DomSetType &CDB = It->second;
+    for_each(CDB.begin(), CDB.end(),   // Mark all their terminators as live
+             bind_obj(this, &ADCE::markTerminatorLive));
+  }
+  
+  // If this basic block is live, then the terminator must be as well!
+  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 Agressive Dead Code Elimination algorithm, returning
-// true if the method was modified.
+// doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning
+// true if the function was modified.
 //
 bool ADCE::doADCE() {
-  // Compute the control dependence graph...  Note that this has a side effect
-  // on the CFG: a new return bb is added and all returns are merged here.
-  //
-  cfg::DominanceFrontier CDG(cfg::DominatorSet(M, true));
-
-#ifdef DEBUG_ADCE
-  cerr << "Method: " << M;
-#endif
+  bool MadeChanges = false;
 
-  // Iterate over all of the instructions in the method, eliminating trivially
+  // Iterate over all of the instructions in the function, eliminating trivially
   // dead instructions, and marking instructions live that are known to be 
   // needed.  Perform the walk in depth first order so that we avoid marking any
   // instructions live in basic blocks that are unreachable.  These blocks will
   // be eliminated later, along with the instructions inside.
   //
-  for (df_iterator<Method*> BBI = df_begin(M),
-                            BBE = df_end(M);
+  for (df_iterator<Function*> BBI = df_begin(Func), BBE = df_end(Func);
        BBI != BBE; ++BBI) {
     BasicBlock *BB = *BBI;
     for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) {
-      Instruction *I = *II;
-
-      if (I->hasSideEffects() || I->getOpcode() == Instruction::Ret) {
-       markInstructionLive(I);
+      if (II->hasSideEffects() || II->getOpcode() == Instruction::Ret) {
+       markInstructionLive(II);
+        ++II;  // Increment the inst iterator if the inst wasn't deleted
+      } else if (isInstructionTriviallyDead(II)) {
+        // Remove the instruction from it's basic block...
+        II = BB->getInstList().erase(II);
+        ++NumInstRemoved;
+        MadeChanges = true;
       } else {
-       // Check to see if anything is trivially dead
-       if (I->use_size() == 0 && I->getType() != Type::VoidTy) {
-         // Remove the instruction from it's basic block...
-         delete BB->getInstList().remove(II);
-         MadeChanges = true;
-         continue;  // Don't increment the iterator past the current slot
-       }
+        ++II;  // Increment the inst iterator if the inst wasn't deleted
       }
-
-      ++II;  // Increment the inst iterator if the inst wasn't deleted
     }
   }
 
-#ifdef DEBUG_ADCE
-  cerr << "Processing work list\n";
-#endif
+  DEBUG(cerr << "Processing work list\n");
 
   // AliveBlocks - Set of basic blocks that we know have instructions that are
   // alive in them...
@@ -134,171 +184,215 @@ bool ADCE::doADCE() {
     WorkList.pop_back();
 
     BasicBlock *BB = I->getParent();
-    if (AliveBlocks.count(BB) == 0) {   // Basic block not alive yet...
-      // Mark the basic block as being newly ALIVE... and mark all branches that
-      // this block is control dependant on as being alive also...
-      //
-      AliveBlocks.insert(BB);   // Block is now ALIVE!
-      cfg::DominanceFrontier::const_iterator It = CDG.find(BB);
-      if (It != CDG.end()) {
-       // Get the blocks that this node is control dependant on...
-       const cfg::DominanceFrontier::DomSetType &CDB = It->second;
-       for_each(CDB.begin(), CDB.end(),   // Mark all their terminators as live
-                bind_obj(this, &ADCE::markTerminatorLive));
-      }
-
-      // If this basic block is live, then the terminator must be as well!
-      markTerminatorLive(BB);
+    if (!AliveBlocks.count(BB)) {     // Basic block not alive yet...
+      AliveBlocks.insert(BB);         // Block is now ALIVE!
+      markBlockAlive(BB);             // Make it so now!
     }
 
+    // PHI nodes are a special case, because the incoming values are actually
+    // defined in the predecessor nodes of this block, meaning that the PHI
+    // makes the predecessors alive.
+    //
+    if (PHINode *PN = dyn_cast<PHINode>(I))
+      for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
+        if (!AliveBlocks.count(*PI)) {
+          AliveBlocks.insert(BB);         // Block is now ALIVE!
+          markBlockAlive(*PI);
+        }
+
     // Loop over all of the operands of the live instruction, making sure that
     // they are known to be alive as well...
     //
-    for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) {
+    for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op)
       if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op)))
        markInstructionLive(Operand);
-    }
   }
 
-#ifdef DEBUG_ADCE
-  cerr << "Current Method: X = Live\n";
-  for (Method::inst_iterator IL = M->inst_begin(); IL != M->inst_end(); ++IL) {
-    if (LiveSet.count(*IL)) cerr << "X ";
-    cerr << *IL;
+  if (DebugFlag) {
+    cerr << "Current Function: X = Live\n";
+    for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
+      for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI){
+        if (LiveSet.count(BI)) cerr << "X ";
+        cerr << *BI;
+      }
   }
-#endif
 
-  // After the worklist is processed, recursively walk the CFG in depth first
-  // order, patching up references to dead blocks...
+  // Find the first postdominator of the entry node that is alive.  Make it the
+  // new entry node...
   //
-  std::set<BasicBlock*> VisitedBlocks;
-  BasicBlock *EntryBlock = fixupCFG(M->front(), VisitedBlocks, AliveBlocks);
-  if (EntryBlock && EntryBlock != M->front()) {
-    if (isa<PHINode>(EntryBlock->front())) {
-      // Cannot make the first block be a block with a PHI node in it! Instead,
-      // strip the first basic block of the method to contain no instructions,
-      // then add a simple branch to the "real" entry node...
-      //
-      BasicBlock *E = M->front();
-      if (!isa<TerminatorInst>(E->front()) || // Check for an actual change...
-         cast<TerminatorInst>(E->front())->getNumSuccessors() != 1 ||
-         cast<TerminatorInst>(E->front())->getSuccessor(0) != EntryBlock) {
-       E->getInstList().delete_all();      // Delete all instructions in block
-       E->getInstList().push_back(new BranchInst(EntryBlock));
-       MadeChanges = true;
-      }
-      AliveBlocks.insert(E);
-
-      // Next we need to change any PHI nodes in the entry block to refer to the
-      // new predecessor node...
+  PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
 
 
-    } else {
-      // We need to move the new entry block to be the first bb of the method.
-      Method::iterator EBI = find(M->begin(), M->end(), EntryBlock);
-      std::swap(*EBI, *M->begin());// Exchange old location with start of method
-      MadeChanges = true;
+  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
+    // first live postdominator of the live block, adjusting any PHI nodes in
+    // the block to reflect this.
+    //
+    for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
+      if (AliveBlocks.count(I)) {
+        BasicBlock *BB = I;
+        TerminatorInst *TI = BB->getTerminator();
+      
+        // Loop over all of the successors, looking for ones that are not alive.
+        // We cannot save the number of successors in the terminator instruction
+        // here because we may remove them if we don't have a postdominator...
+        //
+        for (unsigned i = 0; i != TI->getNumSuccessors(); ++i)
+          if (!AliveBlocks.count(TI->getSuccessor(i))) {
+            // Scan up the postdominator tree, looking for the first
+            // postdominator that is alive, and the last postdominator that is
+            // dead...
+            //
+            PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)];
+
+            // There is a special case here... if there IS no post-dominator for
+            // the block we have no owhere to point our branch to.  Instead,
+            // convert it to a return.  This can only happen if the code
+            // branched into an infinite loop.  Note that this may not be
+            // desirable, because we _are_ altering the behavior of the code.
+            // This is a well known drawback of ADCE, so in the future if we
+            // choose to revisit the decision, this is where it should be.
+            //
+            if (LastNode == 0) {        // No postdominator!
+              // Call RemoveSuccessor to transmogrify the terminator instruction
+              // to not contain the outgoing branch, or to create a new
+              // terminator if the form fundementally changes (ie unconditional
+              // branch to return).  Note that this will change a branch into an
+              // infinite loop into a return instruction!
+              //
+              RemoveSuccessor(TI, i);
+
+              // RemoveSuccessor may replace TI... make sure we have a fresh
+              // pointer... and e variable.
+              //
+              TI = BB->getTerminator();
+
+              // Rescan this successor...
+              --i;
+            } else {
+              PostDominatorTree::Node *NextNode = LastNode->getIDom();
+
+              while (!AliveBlocks.count(NextNode->getNode())) {
+                LastNode = NextNode;
+                NextNode = NextNode->getIDom();
+              }
+            
+              // Get the basic blocks that we need...
+              BasicBlock *LastDead = LastNode->getNode();
+              BasicBlock *NextAlive = NextNode->getNode();
+
+              // Make the conditional branch now go to the next alive block...
+              TI->getSuccessor(i)->removePredecessor(BB);
+              TI->setSuccessor(i, NextAlive);
+
+              // If there are PHI nodes in NextAlive, we need to add entries to
+              // the PHI nodes for the new incoming edge.  The incoming values
+              // should be identical to the incoming values for LastDead.
+              //
+              for (BasicBlock::iterator II = NextAlive->begin();
+                   PHINode *PN = dyn_cast<PHINode>(&*II); ++II) {
+                // Get the incoming value for LastDead...
+                int OldIdx = PN->getBasicBlockIndex(LastDead);
+                assert(OldIdx != -1 && "LastDead is not a pred of NextAlive!");
+                Value *InVal = PN->getIncomingValue(OldIdx);
+                
+                // Add an incoming value for BB now...
+                PN->addIncoming(InVal, BB);
+              }
+            }
+          }
+
+        // Now loop over all of the instructions in the basic block, 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(BB);
+      }
   }
 
-  // Now go through and tell dead blocks to drop all of their references so they
-  // can be safely deleted.
-  //
-  for (Method::iterator BI = M->begin(), BE = M->end(); BI != BE; ++BI) {
-    BasicBlock *BB = *BI;
-    if (!AliveBlocks.count(BB)) {
-      BB->dropAllReferences();
-    }
+  // We make changes if there are any dead blocks in the function...
+  if (unsigned NumDeadBlocks = Func->size() - AliveBlocks.size()) {
+    MadeChanges = true;
+    NumBlockRemoved += NumDeadBlocks;
   }
 
-  // Now loop through all of the blocks and delete them.  We can safely do this
-  // now because we know that there are no references to dead blocks (because
-  // they have dropped all of their references...
+  // Loop over all of the basic blocks in the function, removing control flow
+  // edges to live blocks (also eliminating any entries in PHI functions in
+  // referenced blocks).
   //
-  for (Method::iterator BI = M->begin(); BI != M->end();) {
-    if (!AliveBlocks.count(*BI)) {
-      delete M->getBasicBlocks().remove(BI);
-      MadeChanges = true;
-      continue;                                     // Don't increment iterator
-    }
-    ++BI;                                           // Increment iterator...
-  }
-
-  return MadeChanges;
-}
-
-
-// fixupCFG - Walk the CFG in depth first order, eliminating references to 
-// dead blocks:
-//  If the BB is alive (in AliveBlocks):
-//   1. Eliminate all dead instructions in the BB
-//   2. Recursively traverse all of the successors of the BB:
-//      - If the returned successor is non-null, update our terminator to
-//         reference the returned BB
-//   3. Return 0 (no update needed)
-//
-//  If the BB is dead (not in AliveBlocks):
-//   1. Add the BB to the dead set
-//   2. Recursively traverse all of the successors of the block:
-//      - Only one shall return a nonnull value (or else this block should have
-//        been in the alive set).
-//   3. Return the nonnull child, or 0 if no non-null children.
-//
-BasicBlock *ADCE::fixupCFG(BasicBlock *BB, std::set<BasicBlock*> &VisitedBlocks,
-                          const std::set<BasicBlock*> &AliveBlocks) {
-  if (VisitedBlocks.count(BB)) return 0;   // Revisiting a node? No update.
-  VisitedBlocks.insert(BB);                // We have now visited this node!
-
-#ifdef DEBUG_ADCE
-  cerr << "Fixing up BB: " << BB;
-#endif
-
-  if (AliveBlocks.count(BB)) {             // Is the block alive?
-    // Yes it's alive: loop through and eliminate all dead instructions in block
-    for (BasicBlock::iterator II = BB->begin(); II != BB->end()-1; ) {
-      Instruction *I = *II;
-      if (!LiveSet.count(I)) {             // Is this instruction alive?
-       // Nope... remove the instruction from it's basic block...
-       delete BB->getInstList().remove(II);
-       MadeChanges = true;
-       continue;                          // Don't increment II
+  for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB)
+    if (!AliveBlocks.count(BB)) {
+      // Remove all outgoing edges from this basic block and convert the
+      // terminator into a return instruction.
+      vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
+      
+      if (!Succs.empty()) {
+        // Loop over all of the successors, removing this block from PHI node
+        // entries that might be in the block...
+        while (!Succs.empty()) {
+          Succs.back()->removePredecessor(BB);
+          Succs.pop_back();
+        }
+        
+        // Delete the old terminator instruction...
+        BB->getInstList().pop_back();
+        const Type *RetTy = Func->getReturnType();
+        BB->getInstList().push_back(new ReturnInst(RetTy != Type::VoidTy ?
+                                           Constant::getNullValue(RetTy) : 0));
       }
-      ++II;
     }
 
-    // Recursively traverse successors of this basic block.  
-    BasicBlock::succ_iterator SI = BB->succ_begin(), SE = BB->succ_end();
-    for (; SI != SE; ++SI) {
-      BasicBlock *Succ = *SI;
-      BasicBlock *Repl = fixupCFG(Succ, VisitedBlocks, AliveBlocks);
-      if (Repl && Repl != Succ) {          // We have to replace the successor
-       Succ->replaceAllUsesWith(Repl);
-       MadeChanges = true;
-      }
-    }
-    return BB;
-  } else {                                 // Otherwise the block is dead...
-    BasicBlock *ReturnBB = 0;              // Default to nothing live down here
-    
-    // Recursively traverse successors of this basic block.  
-    BasicBlock::succ_iterator SI = BB->succ_begin(), SE = BB->succ_end();
-    for (; SI != SE; ++SI) {
-      BasicBlock *RetBB = fixupCFG(*SI, VisitedBlocks, AliveBlocks);
-      if (RetBB) {
-       assert(ReturnBB == 0 && "One one live child allowed!");
-       ReturnBB = RetBB;
-      }
-    }
-    return ReturnBB;                       // Return the result of traversal
-  }
-}
 
+  // Loop over all of the basic blocks in the function, dropping references of
+  // the dead basic blocks.  We must do this after the previous step to avoid
+  // dropping references to PHIs which still have entries...
+  //
+  for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB)
+    if (!AliveBlocks.count(BB))
+      BB->dropAllReferences();
 
+  // Now loop through all of the blocks and delete the dead ones.  We can safely
+  // do this now because we know that there are no references to dead blocks
+  // (because they have dropped all of their references...  we also remove dead
+  // instructions from alive blocks.
+  //
+  for (Function::iterator BI = Func->begin(); BI != Func->end(); )
+    if (!AliveBlocks.count(BI)) {                // Delete dead blocks...
+      BI = Func->getBasicBlockList().erase(BI);
+    } 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...
+          II = BI->getInstList().erase(II);
+          ++NumInstRemoved;
+          MadeChanges = true;
+        } else {
+          ++II;
+        }
+
+      ++BI;                                           // Increment iterator...
+    }
 
-// doADCE - Execute the Agressive Dead Code Elimination Algorithm
-//
-bool AgressiveDCE::doADCE(Method *M) {
-  if (M->isExternal()) return false;
-  ADCE DCE(M);
-  return DCE.doADCE();
+  return MadeChanges;
 }