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"
15 #include "llvm/Analysis/Writer.h"
17 //===----------------------------------------------------------------------===//
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.
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
28 //===--------------------------------------------------------------------===//
29 // The public interface for this class
32 // ADCE Ctor - Save the method to operate on...
33 inline ADCE(Method *m) : M(m) {}
35 // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
36 // true if the method was modified.
39 //===--------------------------------------------------------------------===//
40 // The implementation of this class
43 inline void markInstructionLive(Instruction *I) {
44 if (LiveSet.count(I)) return;
45 cerr << "Insn Live: " << I;
47 WorkList.push_back(I);
55 // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
56 // true if the method was modified.
59 // Iterate over all of the instructions in the method, eliminating trivially
60 // dead instructions, and marking instructions live that are known to be
63 for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) {
65 switch (I->getInstType()) {
66 case Instruction::Call:
67 case Instruction::Store:
68 markInstructionLive(I);
71 if (I->getType() == Type::VoidTy) {
72 markInstructionLive(I); // Catches terminators and friends
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());
79 // Make sure to sync up the iterator again...
80 II.resyncInstructionIterator();
81 continue; // Don't increment the iterator past the current slot
86 ++II; // Increment the iterator
90 cerr << "Processing work list\n";
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.
96 while (!WorkList.empty()) {
97 Instruction *I = WorkList.back();
100 for (unsigned op = 0; Value *Op = I->getOperand(op); ++op) {
101 Instruction *Operand = Op->castInstruction();
102 if (Operand) markInstructionLive(Operand);
106 // After the worklist is processed, loop through the instructions again,
107 // removing any that are not live... by the definition of the LiveSet.
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;
115 ++II; // Increment the iterator
122 // DoADCE - Execute the Agressive Dead Code Elimination Algorithm
124 bool opt::DoADCE(Method *M) {