1 //===- DCE.cpp - Code to perform dead code elimination --------------------===//
3 // This file implements dead code elimination and basic block merging.
6 // * removes definitions with no uses (including unused constants)
7 // * removes basic blocks with no predecessors
8 // * merges a basic block into its predecessor if there is only one and the
9 // predecessor only has one successor.
11 // TODO: This should REALLY be recursive instead of iterative. Right now, we
12 // scan linearly through values, removing unused ones as we go. The problem is
13 // that this may cause other earlier values to become unused. To make sure that
14 // we get them all, we iterate until things stop changing. Instead, when
15 // removing a value, recheck all of its operands to see if they are now unused.
16 // Piece of cake, and more efficient as well.
18 //===----------------------------------------------------------------------===//
20 #include "llvm/Module.h"
21 #include "llvm/Method.h"
22 #include "llvm/BasicBlock.h"
23 #include "llvm/iTerminators.h"
24 #include "llvm/Opt/AllOpts.h"
28 static bool isDCEable(const Value *) { return true; }
31 struct BasicBlockDCE {
33 static bool isDCEable(const Instruction *I) {
34 return !I->hasSideEffects();
38 template<class ValueSubclass, class ItemParentType, class DCEController>
39 static bool RemoveUnusedDefs(ValueHolder<ValueSubclass, ItemParentType> &Vals,
40 DCEController DCEControl) {
42 typedef ValueHolder<ValueSubclass, ItemParentType> Container;
44 int Offset = DCEController::EndOffs;
45 for (Container::iterator DI = Vals.begin(); DI != Vals.end()-Offset; ) {
46 // Look for un"used" definitions...
47 if ((*DI)->use_empty() && DCEController::isDCEable(*DI)) {
49 delete Vals.remove(DI);
59 bool DoRemoveUnusedConstants(SymTabValue *S) {
61 ConstantPool &CP = S->getConstantPool();
62 for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI)
63 Changed |= RemoveUnusedDefs(**PI, ConstPoolDCE());
68 static void ReplaceUsesWithConstant(Instruction *I) {
69 // Get the method level constant pool
70 ConstantPool &CP = I->getParent()->getParent()->getConstantPool();
72 ConstPoolVal *CPV = 0;
73 ConstantPool::PlaneType *P;
74 if (!CP.getPlane(I->getType(), P)) { // Does plane exist?
76 if (!P->empty()) CPV = P->front();
79 if (CPV == 0) { // We don't have an existing constant to reuse. Just add one.
80 CPV = ConstPoolVal::getNullConstant(I->getType()); // Create a new constant
82 // Add the new value to the constant pool...
86 // Make all users of this instruction reference the constant instead
87 I->replaceAllUsesWith(CPV);
90 static bool DoDCEPass(Method *M) {
91 Method::BasicBlocksType::iterator BBIt;
92 Method::BasicBlocksType &BBs = M->getBasicBlocks();
95 // Loop through now and remove instructions that have no uses...
96 for (BBIt = BBs.begin(); BBIt != BBs.end(); BBIt++)
97 Changed |= RemoveUnusedDefs((*BBIt)->getInstList(), BasicBlockDCE());
99 // Scan through and remove basic blocks that have no predecessors (except,
100 // of course, the first one. :) (so skip first block)
102 for (BBIt = BBs.begin(), ++BBIt; BBIt != BBs.end(); BBIt++) {
103 BasicBlock *BB = *BBIt;
104 assert(BB->getTerminator() &&
105 "Degenerate basic block encountered!"); // Empty bb???
107 if (BB->pred_begin() == BB->pred_end() &&
108 !BB->hasConstantPoolReferences()) {
110 while (!BB->getInstList().empty()) {
111 Instruction *I = BB->getInstList().front();
112 // If this instruction is used, replace uses with an arbitrary
113 // constant value. Because control flow can't get here, we don't care
114 // what we replace the value with.
115 if (!I->use_empty()) ReplaceUsesWithConstant(I);
117 // Remove the instruction from the basic block
118 BasicBlock::InstListType::iterator f = BB->getInstList().begin();
119 delete BB->getInstList().remove(f);
122 delete BBs.remove(BBIt);
123 ++BBIt; // remove puts use on the previous block, we want the next one
128 // Loop through an merge basic blocks into their predecessor if there is only
129 // one, and if there is only one successor of the predecessor.
131 for (BBIt = BBs.begin(); BBIt != BBs.end(); BBIt++) {
132 BasicBlock *BB = *BBIt;
134 // Is there exactly one predecessor to this block?
135 BasicBlock::pred_iterator PI(BB->pred_begin());
136 if (PI != BB->pred_end() && ++PI == BB->pred_end() &&
137 !BB->hasConstantPoolReferences()) {
138 BasicBlock *Pred = *BB->pred_begin();
139 TerminatorInst *Term = Pred->getTerminator();
140 if (Term == 0) continue; // Err... malformed basic block!
142 // Is it an unconditional branch?
143 if (Term->getInstType() != Instruction::Br ||
144 !((BranchInst*)Term)->isUnconditional())
145 continue; // Nope, maybe next time...
149 // Make all branches to the predecessor now point to the successor...
150 Pred->replaceAllUsesWith(BB);
152 // Move all definitions in the predecessor to the successor...
153 BasicBlock::InstListType::iterator DI = Pred->getInstList().end();
154 assert(Pred->getTerminator() &&
155 "Degenerate basic block encountered!"); // Empty bb???
156 delete Pred->getInstList().remove(--DI); // Remove terminator
158 while (Pred->getInstList().begin() != (DI = Pred->getInstList().end())) {
159 Instruction *Def = Pred->getInstList().remove(--DI); // Remove from end
160 BB->getInstList().push_front(Def); // Add to front...
163 // Remove basic block from the method...
166 // Always inherit predecessors name if it exists...
167 if (Pred->hasName()) BB->setName(Pred->getName());
169 // So long you waste of a basic block you...
174 // Remove unused constants
175 Changed |= DoRemoveUnusedConstants(M);
180 // It is possible that we may require multiple passes over the code to fully
181 // eliminate dead code. Iterate until we are done.
183 bool DoDeadCodeElimination(Method *M) {
184 bool Changed = false;
185 while (DoDCEPass(M)) Changed = true;
189 bool DoDeadCodeElimination(Module *C) {
190 bool Val = ApplyOptToAllMethods(C, DoDeadCodeElimination);
191 while (DoRemoveUnusedConstants(C)) Val = true;