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/Tools/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 } 152