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 <set>
  13
  14 #include "llvm/Assembly/Writer.h"
  15
  16 //===----------------------------------------------------------------------===//
  17 // ADCE Class
  18 //
  19 // This class does all of the work of Agressive Dead Code Elimination.
  20 // It's public interface consists of a constructor and a doADCE() method.
  21 //
  22 class ADCE {
  23   Method *M;                            // The method that we are working on...
  24   vector<Instruction*>   WorkList;      // Instructions that just became live
  25   set<Instruction*>      LiveSet;       // The set of live instructions
  26
  27   //===--------------------------------------------------------------------===//
  28   // The public interface for this class
  29   //
  30 public:
  31   // ADCE Ctor - Save the method to operate on...
  32   inline ADCE(Method *m) : M(m) {}
  33
  34   // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
  35   // true if the method was modified.
  36   bool doADCE();
  37
  38   //===--------------------------------------------------------------------===//
  39   // The implementation of this class
  40   //
  41 private:
  42   inline void markInstructionLive(Instruction *I) {
  43     if (LiveSet.count(I)) return;
  44     cerr << "Insn Live: " << I;
  45     LiveSet.insert(I);
  46     WorkList.push_back(I);
  47   }
  48
  49
  50 };
  51
  52
  53
  54 // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
  55 // true if the method was modified.
  56 //
  57 bool ADCE::doADCE() {
  58   // Iterate over all of the instructions in the method, eliminating trivially
  59   // dead instructions, and marking instructions live that are known to be
  60   // needed.
  61   //
  62   for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) {
  63     Instruction *I = *II;
  64     switch (I->getInstType()) {
  65     case Instruction::Call:
  66     case Instruction::Store:
  67       markInstructionLive(I);
  68       break;
  69     default:
  70       if (I->getType() == Type::VoidTy) {
  71         markInstructionLive(I);   // Catches terminators and friends
  72       } else {
  73         if (I->use_size() == 0) { // Check to see if anything is trivially dead
  74           // Remove the instruction from it's basic block...
  75           BasicBlock *BB = I->getParent();
  76           delete BB->getInstList().remove(II.getInstructionIterator());
  77
  78           // Make sure to sync up the iterator again...
  79           II.resyncInstructionIterator();
  80           continue;  // Don't increment the iterator past the current slot
  81         }
  82       }
  83     }
  84
  85     ++II;  // Increment the iterator
  86   }
  87
  88
  89   cerr << "Processing work list\n";
  90
  91   // Process the work list of instructions that just became live... if they
  92   // became live, then that means that all of their operands are neccesary as
  93   // well... make them live as well.
  94   //
  95   while (!WorkList.empty()) {
  96     Instruction *I = WorkList.back();
  97     WorkList.pop_back();
  98
  99     for (unsigned op = 0; Value *Op = I->getOperand(op); ++op) {
 100       Instruction *Operand = Op->castInstruction();
 101       if (Operand) markInstructionLive(Operand);
 102     }
 103   }
 104
 105   // After the worklist is processed, loop through the instructions again,
 106   // removing any that are not live... by the definition of the LiveSet.
 107   //
 108   for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) {
 109     Instruction *I = *II;
 110     if (!LiveSet.count(I)) {
 111       cerr << "Instruction Dead: " << I;
 112     }
 113
 114     ++II;  // Increment the iterator
 115   }
 116
 117   return false;
 118 }
 119
 120
 121 // DoADCE - Execute the Agressive Dead Code Elimination Algorithm
 122 //
 123 bool opt::DoADCE(Method *M) {
 124   ADCE DCE(M);
 125   return DCE.doADCE();
 126 }