path: root/lib/Transforms/Scalar/ADCE.cpp

//===- ADCE.cpp - Code to perform aggressive dead code elimination --------===//
//
// 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.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Type.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/Statistic.h"
#include <algorithm>
using std::cerr;
using std::vector;

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 Aggressive Dead Code Elimination.
// It's public interface consists of a constructor and a doADCE() method.
//
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

  //===--------------------------------------------------------------------===//
  // The public interface for this class
  //
public:
  // 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>();
  }


  //===--------------------------------------------------------------------===//
  // 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;
    DEBUG(cerr << "Insn Live: " << I);
    LiveSet.insert(I);
    WorkList.push_back(I);
  }

  inline void markTerminatorLive(const BasicBlock *BB) {
    DEBUG(cerr << "Terminat Live: " << BB->getTerminator());
    markInstructionLive((Instruction*)BB->getTerminator());
  }
};

  RegisterOpt<ADCE> X("adce", "Aggressive Dead Code Elimination");
} // End of anonymous namespace

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...
  //
  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 Aggressive Dead Code Elimination algorithm, returning
// true if the function was modified.
//
bool ADCE::doADCE() {
  bool MadeChanges = false;

  // 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<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; ) {
      if (II->mayWriteToMemory() || 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 {
        ++II;  // Increment the inst iterator if the inst wasn't deleted
      }
    }
  }

  DEBUG(cerr << "Processing work list\n");

  // AliveBlocks - Set of basic blocks that we know have instructions that are
  // alive in them...
  //
  std::set<BasicBlock*> AliveBlocks;

  // Process the work list of instructions that just became live... if they
  // became live, then that means that all of their operands are neccesary as
  // well... make them live as well.
  //
  while (!WorkList.empty()) {
    Instruction *I = WorkList.back(); // Get an instruction that became live...
    WorkList.pop_back();

    BasicBlock *BB = I->getParent();
    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)
      if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op)))
	markInstructionLive(Operand);
  }

  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;
      }
  }

  // Find the first postdominator of the entry node that is alive.  Make it the
  // new entry node...
  //
  PostDominatorTree &DT = getAnalysis<PostDominatorTree>();


  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())) {