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 }
128