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