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