lib/Transforms/Scalar/ADCE.cpp

   1 //===- ADCE.cpp - Code to perform agressive dead code elimination ---------===//
   2 //
   3 // This file implements "agressive" dead code elimination.  ADCE is DCe where
   4 // values are assumed to be dead until proven otherwise.  This is similar to
   5 // SCCP, except applied to the liveness of values.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Optimizations/DCE.h"
  10 #include "llvm/Instruction.h"
  11 #include "llvm/Type.h"
  12 #include "llvm/Analysis/Dominators.h"
  13 #include "llvm/Support/STLExtras.h"
  14 #include "llvm/Analysis/Writer.h"
  15 #include <set>
  16 #include <algorithm>
  17
  18 //===----------------------------------------------------------------------===//
  19 // ADCE Class
  20 //
  21 // This class does all of the work of Agressive Dead Code Elimination.
  22 // It's public interface consists of a constructor and a doADCE() method.
  23 //
  24 class ADCE {
  25   Method *M;                            // The method that we are working on...
  26   vector<Instruction*>   WorkList;      // Instructions that just became live
  27   set<Instruction*>      LiveSet;       // The set of live instructions
  28
  29   //===--------------------------------------------------------------------===//
  30   // The public interface for this class
  31   //
  32 public:
  33   // ADCE Ctor - Save the method to operate on...
  34   inline ADCE(Method *m) : M(m) {}
  35
  36   // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
  37   // true if the method was modified.
  38   bool doADCE();
  39
  40   //===--------------------------------------------------------------------===//
  41   // The implementation of this class
  42   //
  43 private:
  44   inline void markInstructionLive(Instruction *I) {
  45     if (LiveSet.count(I)) return;
  46     cerr << "Insn Live: " << I;
  47     LiveSet.insert(I);
  48     WorkList.push_back(I);
  49   }
  50
  51   inline void markTerminatorLive(const BasicBlock *BB) {
  52     cerr << "Marking Term Live\n";
  53     markInstructionLive((Instruction*)BB->back());
  54   }
  55 };
  56
  57
  58
  59 // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
  60 // true if the method was modified.
  61 //
  62 bool ADCE::doADCE() {
  63   // Iterate over all of the instructions in the method, eliminating trivially
  64   // dead instructions, and marking instructions live that are known to be
  65   // needed.
  66   //
  67   for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) {
  68     Instruction *I = *II;
  69     switch (I->getInstType()) {
  70     case Instruction::Ret:
  71     case Instruction::Call:
  72     case Instruction::Store:
  73       markInstructionLive(I);
  74       break;
  75     default:
  76       // Check to see if anything is trivially dead
  77       if (I->use_size() == 0 && I->getType() != Type::VoidTy) {
  78         // Remove the instruction from it's basic block...
  79         BasicBlock *BB = I->getParent();
  80         delete BB->getInstList().remove(II.getInstructionIterator());
  81
  82         // Make sure to sync up the iterator again...
  83         II.resyncInstructionIterator();
  84         continue;  // Don't increment the iterator past the current slot
  85       }
  86     }
  87
  88     ++II;  // Increment the iterator
  89   }
  90
  91   // Compute the control dependence graph...
  92   cfg::DominanceFrontier CDG(cfg::DominatorSet(M, true));
  93
  94   cerr << "Processing work list\n";
  95
  96   // AliveBlocks - Set of basic blocks that we know have instructions that are
  97   // alive in them...
  98   //
  99   set<BasicBlock*> AliveBlocks;
 100
 101   // Process the work list of instructions that just became live... if they
 102   // became live, then that means that all of their operands are neccesary as
 103   // well... make them live as well.
 104   //
 105   while (!WorkList.empty()) {
 106     Instruction *I = WorkList.back(); // Get an instruction that became live...
 107     WorkList.pop_back();
 108
 109     BasicBlock *BB = I->getParent();
 110     if (AliveBlocks.count(BB) == 0) {   // Basic block not alive yet...
 111       // Mark the basic block as being newly ALIVE... and mark all branches that
 112       // this block is control dependant on as being alive also...
 113       //
 114       AliveBlocks.insert(BB);   // Block is now ALIVE!
 115       cfg::DominanceFrontier::const_iterator It = CDG.find(BB);
 116       if (It != CDG.end()) {
 117         // Get the blocks that this node is control dependant on...
 118         const cfg::DominanceFrontier::DomSetType &CDB = It->second;
 119         for_each(CDB.begin(), CDB.end(),   // Mark all their terminators as live
 120                  bind_obj(this, &ADCE::markTerminatorLive));
 121       }
 122     }
 123
 124     for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) {
 125       Instruction *Operand = I->getOperand(op)->castInstruction();
 126       if (Operand) markInstructionLive(Operand);
 127     }
 128   }
 129
 130   // After the worklist is processed, loop through the instructions again,
 131   // removing any that are not live... by the definition of the LiveSet.
 132   //
 133   for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) {
 134     Instruction *I = *II;
 135     if (!LiveSet.count(I)) {
 136       cerr << "Instruction Dead: " << I;
 137     }
 138
 139     ++II;  // Increment the iterator
 140   }
 141
 142   return false;
 143 }
 144
 145
 146 // DoADCE - Execute the Agressive Dead Code Elimination Algorithm
 147 //
 148 bool opt::DoADCE(Method *M) {
 149   ADCE DCE(M);
 150   return DCE.doADCE();
 151 }