DCE.cpp revision f0604b84c7273fc2503454ecaa198eaee5b615bd
1//===- DCE.cpp - Code to perform dead code elimination --------------------===// 2// 3// This file implements dead code elimination and basic block merging. 4// 5// Specifically, this: 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. 10// * Eliminates PHI nodes for basic blocks with a single predecessor 11// * Eliminates a basic block that only contains an unconditional branch 12// * Eliminates method prototypes that are not referenced 13// 14// TODO: This should REALLY be worklist driven instead of iterative. Right now, 15// we scan linearly through values, removing unused ones as we go. The problem 16// is that this may cause other earlier values to become unused. To make sure 17// that we get them all, we iterate until things stop changing. Instead, when 18// removing a value, recheck all of its operands to see if they are now unused. 19// Piece of cake, and more efficient as well. 20// 21// Note, this is not trivial, because we have to worry about invalidating 22// iterators. :( 23// 24//===----------------------------------------------------------------------===// 25 26#include "llvm/Optimizations/DCE.h" 27#include "llvm/Support/STLExtras.h" 28#include "llvm/Module.h" 29#include "llvm/Method.h" 30#include "llvm/BasicBlock.h" 31#include "llvm/iTerminators.h" 32#include "llvm/iOther.h" 33#include "llvm/Assembly/Writer.h" 34#include <algorithm> 35 36struct ConstPoolDCE { 37 enum { EndOffs = 0 }; 38 static bool isDCEable(const ConstPoolVal *CPV) { 39 // TODO: The bytecode writer requires that all used types are in the 40 // constant pool for the current method. This is messy and is really 41 // irritating. FIXME 42 return CPV->getType() != Type::TypeTy; // Don't DCE Type plane constants! 43 } 44}; 45 46struct BasicBlockDCE { 47 enum { EndOffs = 1 }; 48 static bool isDCEable(const Instruction *I) { 49 return !I->hasSideEffects(); 50 } 51}; 52 53 54template<class Container, class DCEController> 55static bool RemoveUnusedDefs(Container &Vals, DCEController DCEControl) { 56 bool Changed = false; 57 int Offset = DCEController::EndOffs; 58 59 for (typename Container::iterator DI = Vals.begin(); 60 DI != Vals.end()-Offset; ) { 61 // Look for un"used" definitions... 62 if ((*DI)->use_empty() && DCEController::isDCEable(*DI)) { 63 // Bye bye 64 //cerr << "Removing: " << *DI; 65 delete Vals.remove(DI); 66 Changed = true; 67 } else { 68 ++DI; 69 } 70 } 71 return Changed; 72} 73 74// RemoveSingularPHIs - This removes PHI nodes from basic blocks that have only 75// a single predecessor. This means that the PHI node must only have a single 76// RHS value and can be eliminated. 77// 78// This routine is very simple because we know that PHI nodes must be the first 79// things in a basic block, if they are present. 80// 81static bool RemoveSingularPHIs(BasicBlock *BB) { 82 BasicBlock::pred_iterator PI(BB->pred_begin()); 83 if (PI == BB->pred_end() || ++PI != BB->pred_end()) 84 return false; // More than one predecessor... 85 86 Instruction *I = BB->front(); 87 if (!I->isPHINode()) return false; // No PHI nodes 88 89 //cerr << "Killing PHIs from " << BB; 90 //cerr << "Pred #0 = " << *BB->pred_begin(); 91 92 //cerr << "Method == " << BB->getParent(); 93 94 do { 95 PHINode *PN = (PHINode*)I; 96 assert(PN->getNumOperands() == 2 && "PHI node should only have one value!"); 97 Value *V = PN->getOperand(0); 98 99 PN->replaceAllUsesWith(V); // Replace PHI node with its single value. 100 delete BB->getInstList().remove(BB->begin()); 101 102 I = BB->front(); 103 } while (I->isPHINode()); 104 105 return true; // Yes, we nuked at least one phi node 106} 107 108static void ReplaceUsesWithConstant(Instruction *I) { 109 ConstPoolVal *CPV = ConstPoolVal::getNullConstant(I->getType()); 110 111 // Make all users of this instruction reference the constant instead 112 I->replaceAllUsesWith(CPV); 113} 114 115// PropogatePredecessors - This gets "Succ" ready to have the predecessors from 116// "BB". This is a little tricky because "Succ" has PHI nodes, which need to 117// have extra slots added to them to hold the merge edges from BB's 118// predecessors. 119// 120// Assumption: BB is the single predecessor of Succ. 121// 122static void PropogatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 123 assert(Succ->front()->isPHINode() && "Only works on PHId BBs!"); 124 125 // If there is more than one predecessor, and there are PHI nodes in 126 // the successor, then we need to add incoming edges for the PHI nodes 127 // 128 const vector<BasicBlock*> BBPreds(BB->pred_begin(), BB->pred_end()); 129 130 BasicBlock::iterator I = Succ->begin(); 131 do { // Loop over all of the PHI nodes in the successor BB 132 PHINode *PN = (PHINode*)*I; 133 Value *OldVal = PN->removeIncomingValue(BB); 134 assert(OldVal && "No entry in PHI for Pred BB!"); 135 136 for (vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 137 End = BBPreds.end(); PredI != End; ++PredI) { 138 // Add an incoming value for each of the new incoming values... 139 PN->addIncoming(OldVal, *PredI); 140 } 141 142 ++I; 143 } while ((*I)->isPHINode()); 144} 145 146 147// SimplifyCFG - This function is used to do simplification of a CFG. For 148// example, it adjusts branches to branches to eliminate the extra hop, it 149// eliminates unreachable basic blocks, and does other "peephole" optimization 150// of the CFG. It returns true if a modification was made, and returns an 151// iterator that designates the first element remaining after the block that 152// was deleted. 153// 154// WARNING: The entry node of a method may not be simplified. 155// 156bool opt::SimplifyCFG(Method::iterator &BBIt) { 157 BasicBlock *BB = *BBIt; 158 Method *M = BB->getParent(); 159 160 assert(BB && BB->getParent() && "Block not embedded in method!"); 161 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 162 assert(BB->getParent()->front() != BB && "Can't Simplify entry block!"); 163 164 165 // Remove basic blocks that have no predecessors... which are unreachable. 166 if (BB->pred_begin() == BB->pred_end() && 167 !BB->hasConstantPoolReferences()) { 168 //cerr << "Removing BB: \n" << BB; 169 170 // Loop through all of our successors and make sure they know that one 171 // of their predecessors is going away. 172 for_each(BB->succ_begin(), BB->succ_end(), 173 std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 174 175 while (!BB->empty()) { 176 Instruction *I = BB->back(); 177 // If this instruction is used, replace uses with an arbitrary 178 // constant value. Because control flow can't get here, we don't care 179 // what we replace the value with. Note that since this block is 180 // unreachable, and all values contained within it must dominate their 181 // uses, that all uses will eventually be removed. 182 if (!I->use_empty()) ReplaceUsesWithConstant(I); 183 184 // Remove the instruction from the basic block 185 delete BB->getInstList().pop_back(); 186 } 187 delete M->getBasicBlocks().remove(BBIt); 188 return true; 189 } 190 191 // Check to see if this block has no instructions and only a single 192 // successor. If so, replace block references with successor. 193 BasicBlock::succ_iterator SI(BB->succ_begin()); 194 if (SI != BB->succ_end() && ++SI == BB->succ_end()) { // One succ? 195 Instruction *I = BB->front(); 196 if (I->isTerminator()) { // Terminator is the only instruction! 197 BasicBlock *Succ = *BB->succ_begin(); // There is exactly one successor 198 //cerr << "Killing Trivial BB: \n" << BB; 199 200 if (Succ != BB) { // Arg, don't hurt infinite loops! 201 if (Succ->front()->isPHINode()) { 202 // If our successor has PHI nodes, then we need to update them to 203 // include entries for BB's predecessors, not for BB itself. 204 // 205 PropogatePredecessorsForPHIs(BB, Succ); 206 } 207 208 BB->replaceAllUsesWith(Succ); 209 BB = M->getBasicBlocks().remove(BBIt); 210 211 if (BB->hasName() && !Succ->hasName()) // Transfer name if we can 212 Succ->setName(BB->getName()); 213 delete BB; // Delete basic block 214 215 //cerr << "Method after removal: \n" << M; 216 return true; 217 } 218 } 219 } 220 221 // Merge basic blocks into their predecessor if there is only one pred, 222 // and if there is only one successor of the predecessor. 223 BasicBlock::pred_iterator PI(BB->pred_begin()); 224 if (PI != BB->pred_end() && *PI != BB && // Not empty? Not same BB? 225 ++PI == BB->pred_end() && !BB->hasConstantPoolReferences()) { 226 BasicBlock *Pred = *BB->pred_begin(); 227 TerminatorInst *Term = Pred->getTerminator(); 228 assert(Term != 0 && "malformed basic block without terminator!"); 229 230 // Does the predecessor block only have a single successor? 231 BasicBlock::succ_iterator SI(Pred->succ_begin()); 232 if (++SI == Pred->succ_end()) { 233 //cerr << "Merging: " << BB << "into: " << Pred; 234 235 // Delete the unconditianal branch from the predecessor... 236 BasicBlock::iterator DI = Pred->end(); 237 assert(Pred->getTerminator() && 238 "Degenerate basic block encountered!"); // Empty bb??? 239 delete Pred->getInstList().remove(--DI); // Destroy uncond branch 240 241 // Move all definitions in the succecessor to the predecessor... 242 while (!BB->empty()) { 243 DI = BB->begin(); 244 Instruction *Def = BB->getInstList().remove(DI); // Remove from front 245 Pred->getInstList().push_back(Def); // Add to end... 246 } 247 248 // Remove basic block from the method... and advance iterator to the 249 // next valid block... 250 BB = M->getBasicBlocks().remove(BBIt); 251 252 // Make all PHI nodes that refered to BB now refer to Pred as their 253 // source... 254 BB->replaceAllUsesWith(Pred); 255 256 // Inherit predecessors name if it exists... 257 if (BB->hasName() && !Pred->hasName()) Pred->setName(BB->getName()); 258 259 delete BB; // You ARE the weakest link... goodbye 260 return true; 261 } 262 } 263 264 return false; 265} 266 267static bool DoDCEPass(Method *M) { 268 Method::iterator BBIt, BBEnd = M->end(); 269 if (M->begin() == BBEnd) return false; // Nothing to do 270 bool Changed = false; 271 272 // Loop through now and remove instructions that have no uses... 273 for (BBIt = M->begin(); BBIt != BBEnd; ++BBIt) { 274 Changed |= RemoveUnusedDefs((*BBIt)->getInstList(), BasicBlockDCE()); 275 Changed |= RemoveSingularPHIs(*BBIt); 276 } 277 278 // Loop over all of the basic blocks (except the first one) and remove them 279 // if they are unneeded... 280 // 281 for (BBIt = M->begin(), ++BBIt; BBIt != M->end(); ) { 282 if (opt::SimplifyCFG(BBIt)) { 283 Changed = true; 284 } else { 285 ++BBIt; 286 } 287 } 288 289 return Changed; 290} 291 292 293// It is possible that we may require multiple passes over the code to fully 294// eliminate dead code. Iterate until we are done. 295// 296bool opt::DoDeadCodeElimination(Method *M) { 297 bool Changed = false; 298 while (DoDCEPass(M)) Changed = true; 299 return Changed; 300} 301 302bool opt::DoDeadCodeElimination(Module *Mod) { 303 bool Changed = false; 304 305 for (Module::iterator MI = Mod->begin(); MI != Mod->end(); ) { 306 Method *Meth = *MI; 307 if (!Meth->isExternal()) { // DCE normal methods 308 Changed |= DoDeadCodeElimination(Meth); 309 ++MI; // Next method please 310 } else if (Meth->use_size() == 0) { // No references to prototype? 311 //cerr << "Removing method proto: " << Meth->getName() << endl; 312 delete Mod->getMethodList().remove(MI); // Remove prototype 313 // Remove moves iterator to point to the next one automatically 314 } else { 315 ++MI; // Skip prototype in use. 316 } 317 } 318 319 return Changed; 320} 321