1 //===- ADCE.cpp - Code to perform agressive dead code elimination ---------===//
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.
7 //===----------------------------------------------------------------------===//
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"
18 //===----------------------------------------------------------------------===//
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.
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
29 //===--------------------------------------------------------------------===//
30 // The public interface for this class
33 // ADCE Ctor - Save the method to operate on...
34 inline ADCE(Method *m) : M(m) {}
36 // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
37 // true if the method was modified.
40 //===--------------------------------------------------------------------===//
41 // The implementation of this class
44 inline void markInstructionLive(Instruction *I) {
45 if (LiveSet.count(I)) return;
46 cerr << "Insn Live: " << I;
48 WorkList.push_back(I);
51 inline void markTerminatorLive(const BasicBlock *BB) {
52 cerr << "Marking Term Live\n";
53 markInstructionLive((Instruction*)BB->back());
59 // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
60 // true if the method was modified.
63 // Iterate over all of the instructions in the method, eliminating trivially
64 // dead instructions, and marking instructions live that are known to be
67 for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) {
69 switch (I->getInstType()) {
70 case Instruction::Ret:
71 case Instruction::Call:
72 case Instruction::Store:
73 markInstructionLive(I);
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());
82 // Make sure to sync up the iterator again...
83 II.resyncInstructionIterator();
84 continue; // Don't increment the iterator past the current slot
88 ++II; // Increment the iterator
91 // Compute the control dependence graph...
92 cfg::DominanceFrontier CDG(cfg::DominatorSet(M, true));
94 cerr << "Processing work list\n";
96 // AliveBlocks - Set of basic blocks that we know have instructions that are
99 set<BasicBlock*> AliveBlocks;
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.
105 while (!WorkList.empty()) {
106 Instruction *I = WorkList.back(); // Get an instruction that became live...
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...
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));
124 for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) {
125 Instruction *Operand = I->getOperand(op)->castInstruction();
126 if (Operand) markInstructionLive(Operand);
130 // After the worklist is processed, loop through the instructions again,
131 // removing any that are not live... by the definition of the LiveSet.
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;
139 ++II; // Increment the iterator
146 // DoADCE - Execute the Agressive Dead Code Elimination Algorithm
148 bool opt::DoADCE(Method *M) {