ADCE.cpp revision 1a84bd38efa9d3f638781e2502b2bee150a3471c
1//===- ADCE.cpp - Code to perform aggressive dead code elimination --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements "aggressive" dead code elimination. ADCE is DCe where 11// values are assumed to be dead until proven otherwise. This is similar to 12// SCCP, except applied to the liveness of values. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Transforms/Scalar.h" 17#include "llvm/Constants.h" 18#include "llvm/Instructions.h" 19#include "llvm/Analysis/AliasAnalysis.h" 20#include "llvm/Analysis/PostDominators.h" 21#include "llvm/Support/CFG.h" 22#include "llvm/Transforms/Utils/BasicBlockUtils.h" 23#include "llvm/Transforms/Utils/Local.h" 24#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/ADT/DepthFirstIterator.h" 27#include "llvm/ADT/Statistic.h" 28#include "llvm/ADT/STLExtras.h" 29#include <algorithm> 30using namespace llvm; 31 32namespace { 33 Statistic<> NumBlockRemoved("adce", "Number of basic blocks removed"); 34 Statistic<> NumInstRemoved ("adce", "Number of instructions removed"); 35 Statistic<> NumCallRemoved ("adce", "Number of calls and invokes removed"); 36 37//===----------------------------------------------------------------------===// 38// ADCE Class 39// 40// This class does all of the work of Aggressive Dead Code Elimination. 41// It's public interface consists of a constructor and a doADCE() method. 42// 43class ADCE : public FunctionPass { 44 Function *Func; // The function that we are working on 45 std::vector<Instruction*> WorkList; // Instructions that just became live 46 std::set<Instruction*> LiveSet; // The set of live instructions 47 48 //===--------------------------------------------------------------------===// 49 // The public interface for this class 50 // 51public: 52 // Execute the Aggressive Dead Code Elimination Algorithm 53 // 54 virtual bool runOnFunction(Function &F) { 55 Func = &F; 56 bool Changed = doADCE(); 57 assert(WorkList.empty()); 58 LiveSet.clear(); 59 return Changed; 60 } 61 // getAnalysisUsage - We require post dominance frontiers (aka Control 62 // Dependence Graph) 63 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 64 // We require that all function nodes are unified, because otherwise code 65 // can be marked live that wouldn't necessarily be otherwise. 66 AU.addRequired<UnifyFunctionExitNodes>(); 67 AU.addRequired<AliasAnalysis>(); 68 AU.addRequired<PostDominatorTree>(); 69 AU.addRequired<PostDominanceFrontier>(); 70 } 71 72 73 //===--------------------------------------------------------------------===// 74 // The implementation of this class 75 // 76private: 77 // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning 78 // true if the function was modified. 79 // 80 bool doADCE(); 81 82 void markBlockAlive(BasicBlock *BB); 83 84 85 // deleteDeadInstructionsInLiveBlock - Loop over all of the instructions in 86 // the specified basic block, deleting ones that are dead according to 87 // LiveSet. 88 bool deleteDeadInstructionsInLiveBlock(BasicBlock *BB); 89 90 TerminatorInst *convertToUnconditionalBranch(TerminatorInst *TI); 91 92 inline void markInstructionLive(Instruction *I) { 93 if (!LiveSet.insert(I).second) return; 94 DEBUG(std::cerr << "Insn Live: " << *I); 95 WorkList.push_back(I); 96 } 97 98 inline void markTerminatorLive(const BasicBlock *BB) { 99 DEBUG(std::cerr << "Terminator Live: " << *BB->getTerminator()); 100 markInstructionLive(const_cast<TerminatorInst*>(BB->getTerminator())); 101 } 102}; 103 104 RegisterOpt<ADCE> X("adce", "Aggressive Dead Code Elimination"); 105} // End of anonymous namespace 106 107FunctionPass *llvm::createAggressiveDCEPass() { return new ADCE(); } 108 109void ADCE::markBlockAlive(BasicBlock *BB) { 110 // Mark the basic block as being newly ALIVE... and mark all branches that 111 // this block is control dependent on as being alive also... 112 // 113 PostDominanceFrontier &CDG = getAnalysis<PostDominanceFrontier>(); 114 115 PostDominanceFrontier::const_iterator It = CDG.find(BB); 116 if (It != CDG.end()) { 117 // Get the blocks that this node is control dependent on... 118 const PostDominanceFrontier::DomSetType &CDB = It->second; 119 for_each(CDB.begin(), CDB.end(), // Mark all their terminators as live 120 bind_obj(this, &ADCE::markTerminatorLive)); 121 } 122 123 // If this basic block is live, and it ends in an unconditional branch, then 124 // the branch is alive as well... 125 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) 126 if (BI->isUnconditional()) 127 markTerminatorLive(BB); 128} 129 130// deleteDeadInstructionsInLiveBlock - Loop over all of the instructions in the 131// specified basic block, deleting ones that are dead according to LiveSet. 132bool ADCE::deleteDeadInstructionsInLiveBlock(BasicBlock *BB) { 133 bool Changed = false; 134 for (BasicBlock::iterator II = BB->begin(), E = --BB->end(); II != E; ) { 135 Instruction *I = II++; 136 if (!LiveSet.count(I)) { // Is this instruction alive? 137 if (!I->use_empty()) 138 I->replaceAllUsesWith(UndefValue::get(I->getType())); 139 140 // Nope... remove the instruction from it's basic block... 141 if (isa<CallInst>(I)) 142 ++NumCallRemoved; 143 else 144 ++NumInstRemoved; 145 BB->getInstList().erase(I); 146 Changed = true; 147 } 148 } 149 return Changed; 150} 151 152 153/// convertToUnconditionalBranch - Transform this conditional terminator 154/// instruction into an unconditional branch because we don't care which of the 155/// successors it goes to. This eliminate a use of the condition as well. 156/// 157TerminatorInst *ADCE::convertToUnconditionalBranch(TerminatorInst *TI) { 158 BranchInst *NB = new BranchInst(TI->getSuccessor(0), TI); 159 BasicBlock *BB = TI->getParent(); 160 161 // Remove entries from PHI nodes to avoid confusing ourself later... 162 for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i) 163 TI->getSuccessor(i)->removePredecessor(BB); 164 165 // Delete the old branch itself... 166 BB->getInstList().erase(TI); 167 return NB; 168} 169 170 171// doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning 172// true if the function was modified. 173// 174bool ADCE::doADCE() { 175 bool MadeChanges = false; 176 177 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 178 179 180 // Iterate over all invokes in the function, turning invokes into calls if 181 // they cannot throw. 182 for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) 183 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 184 if (Function *F = II->getCalledFunction()) 185 if (AA.onlyReadsMemory(F)) { 186 // The function cannot unwind. Convert it to a call with a branch 187 // after it to the normal destination. 188 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 189 std::string Name = II->getName(); II->setName(""); 190 Instruction *NewCall = new CallInst(F, Args, Name, II); 191 II->replaceAllUsesWith(NewCall); 192 new BranchInst(II->getNormalDest(), II); 193 194 // Update PHI nodes in the unwind destination 195 II->getUnwindDest()->removePredecessor(BB); 196 BB->getInstList().erase(II); 197 198 if (NewCall->use_empty()) { 199 BB->getInstList().erase(NewCall); 200 ++NumCallRemoved; 201 } 202 } 203 204 // Iterate over all of the instructions in the function, eliminating trivially 205 // dead instructions, and marking instructions live that are known to be 206 // needed. Perform the walk in depth first order so that we avoid marking any 207 // instructions live in basic blocks that are unreachable. These blocks will 208 // be eliminated later, along with the instructions inside. 209 // 210 std::set<BasicBlock*> ReachableBBs; 211 for (df_ext_iterator<BasicBlock*> 212 BBI = df_ext_begin(&Func->front(), ReachableBBs), 213 BBE = df_ext_end(&Func->front(), ReachableBBs); BBI != BBE; ++BBI) { 214 BasicBlock *BB = *BBI; 215 for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) { 216 Instruction *I = II++; 217 if (CallInst *CI = dyn_cast<CallInst>(I)) { 218 Function *F = CI->getCalledFunction(); 219 if (F && AA.onlyReadsMemory(F)) { 220 if (CI->use_empty()) { 221 BB->getInstList().erase(CI); 222 ++NumCallRemoved; 223 } 224 } else { 225 markInstructionLive(I); 226 } 227 } else if (I->mayWriteToMemory() || isa<ReturnInst>(I) || 228 isa<UnwindInst>(I) || isa<UnreachableInst>(I)) { 229 // FIXME: Unreachable instructions should not be marked intrinsically 230 // live here. 231 markInstructionLive(I); 232 } else if (isInstructionTriviallyDead(I)) { 233 // Remove the instruction from it's basic block... 234 BB->getInstList().erase(I); 235 ++NumInstRemoved; 236 } 237 } 238 } 239 240 // Check to ensure we have an exit node for this CFG. If we don't, we won't 241 // have any post-dominance information, thus we cannot perform our 242 // transformations safely. 243 // 244 PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 245 if (DT[&Func->getEntryBlock()] == 0) { 246 WorkList.clear(); 247 return MadeChanges; 248 } 249 250 // Scan the function marking blocks without post-dominance information as 251 // live. Blocks without post-dominance information occur when there is an 252 // infinite loop in the program. Because the infinite loop could contain a 253 // function which unwinds, exits or has side-effects, we don't want to delete 254 // the infinite loop or those blocks leading up to it. 255 for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) 256 if (DT[I] == 0 && ReachableBBs.count(I)) 257 for (pred_iterator PI = pred_begin(I), E = pred_end(I); PI != E; ++PI) 258 markInstructionLive((*PI)->getTerminator()); 259 260 DEBUG(std::cerr << "Processing work list\n"); 261 262 // AliveBlocks - Set of basic blocks that we know have instructions that are 263 // alive in them... 264 // 265 std::set<BasicBlock*> AliveBlocks; 266 267 // Process the work list of instructions that just became live... if they 268 // became live, then that means that all of their operands are necessary as 269 // well... make them live as well. 270 // 271 while (!WorkList.empty()) { 272 Instruction *I = WorkList.back(); // Get an instruction that became live... 273 WorkList.pop_back(); 274 275 BasicBlock *BB = I->getParent(); 276 if (!ReachableBBs.count(BB)) continue; 277 if (AliveBlocks.insert(BB).second) // Basic block not alive yet. 278 markBlockAlive(BB); // Make it so now! 279 280 // PHI nodes are a special case, because the incoming values are actually 281 // defined in the predecessor nodes of this block, meaning that the PHI 282 // makes the predecessors alive. 283 // 284 if (PHINode *PN = dyn_cast<PHINode>(I)) { 285 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 286 // If the incoming edge is clearly dead, it won't have control 287 // dependence information. Do not mark it live. 288 BasicBlock *PredBB = PN->getIncomingBlock(i); 289 if (ReachableBBs.count(PredBB)) { 290 // FIXME: This should mark the control dependent edge as live, not 291 // necessarily the predecessor itself! 292 if (AliveBlocks.insert(PredBB).second) 293 markBlockAlive(PN->getIncomingBlock(i)); // Block is newly ALIVE! 294 if (Instruction *Op = dyn_cast<Instruction>(PN->getIncomingValue(i))) 295 markInstructionLive(Op); 296 } 297 } 298 } else { 299 // Loop over all of the operands of the live instruction, making sure that 300 // they are known to be alive as well. 301 // 302 for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) 303 if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op))) 304 markInstructionLive(Operand); 305 } 306 } 307 308 DEBUG( 309 std::cerr << "Current Function: X = Live\n"; 310 for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I){ 311 std::cerr << I->getName() << ":\t" 312 << (AliveBlocks.count(I) ? "LIVE\n" : "DEAD\n"); 313 for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI){ 314 if (LiveSet.count(BI)) std::cerr << "X "; 315 std::cerr << *BI; 316 } 317 }); 318 319 // All blocks being live is a common case, handle it specially. 320 if (AliveBlocks.size() == Func->size()) { // No dead blocks? 321 for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) { 322 // Loop over all of the instructions in the function deleting instructions 323 // to drop their references. 324 deleteDeadInstructionsInLiveBlock(I); 325 326 // Check to make sure the terminator instruction is live. If it isn't, 327 // this means that the condition that it branches on (we know it is not an 328 // unconditional branch), is not needed to make the decision of where to 329 // go to, because all outgoing edges go to the same place. We must remove 330 // the use of the condition (because it's probably dead), so we convert 331 // the terminator to an unconditional branch. 332 // 333 TerminatorInst *TI = I->getTerminator(); 334 if (!LiveSet.count(TI)) 335 convertToUnconditionalBranch(TI); 336 } 337 338 return MadeChanges; 339 } 340 341 342 // If the entry node is dead, insert a new entry node to eliminate the entry 343 // node as a special case. 344 // 345 if (!AliveBlocks.count(&Func->front())) { 346 BasicBlock *NewEntry = new BasicBlock(); 347 new BranchInst(&Func->front(), NewEntry); 348 Func->getBasicBlockList().push_front(NewEntry); 349 AliveBlocks.insert(NewEntry); // This block is always alive! 350 LiveSet.insert(NewEntry->getTerminator()); // The branch is live 351 } 352 353 // Loop over all of the alive blocks in the function. If any successor 354 // blocks are not alive, we adjust the outgoing branches to branch to the 355 // first live postdominator of the live block, adjusting any PHI nodes in 356 // the block to reflect this. 357 // 358 for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) 359 if (AliveBlocks.count(I)) { 360 BasicBlock *BB = I; 361 TerminatorInst *TI = BB->getTerminator(); 362 363 // If the terminator instruction is alive, but the block it is contained 364 // in IS alive, this means that this terminator is a conditional branch on 365 // a condition that doesn't matter. Make it an unconditional branch to 366 // ONE of the successors. This has the side effect of dropping a use of 367 // the conditional value, which may also be dead. 368 if (!LiveSet.count(TI)) 369 TI = convertToUnconditionalBranch(TI); 370 371 // Loop over all of the successors, looking for ones that are not alive. 372 // We cannot save the number of successors in the terminator instruction 373 // here because we may remove them if we don't have a postdominator. 374 // 375 for (unsigned i = 0; i != TI->getNumSuccessors(); ++i) 376 if (!AliveBlocks.count(TI->getSuccessor(i))) { 377 // Scan up the postdominator tree, looking for the first 378 // postdominator that is alive, and the last postdominator that is 379 // dead... 380 // 381 PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)]; 382 PostDominatorTree::Node *NextNode = 0; 383 384 if (LastNode) { 385 NextNode = LastNode->getIDom(); 386 while (!AliveBlocks.count(NextNode->getBlock())) { 387 LastNode = NextNode; 388 NextNode = NextNode->getIDom(); 389 if (NextNode == 0) { 390 LastNode = 0; 391 break; 392 } 393 } 394 } 395 396 // There is a special case here... if there IS no post-dominator for 397 // the block we have nowhere to point our branch to. Instead, convert 398 // it to a return. This can only happen if the code branched into an 399 // infinite loop. Note that this may not be desirable, because we 400 // _are_ altering the behavior of the code. This is a well known 401 // drawback of ADCE, so in the future if we choose to revisit the 402 // decision, this is where it should be. 403 // 404 if (LastNode == 0) { // No postdominator! 405 if (!isa<InvokeInst>(TI)) { 406 // Call RemoveSuccessor to transmogrify the terminator instruction 407 // to not contain the outgoing branch, or to create a new 408 // terminator if the form fundamentally changes (i.e., 409 // unconditional branch to return). Note that this will change a 410 // branch into an infinite loop into a return instruction! 411 // 412 RemoveSuccessor(TI, i); 413 414 // RemoveSuccessor may replace TI... make sure we have a fresh 415 // pointer. 416 // 417 TI = BB->getTerminator(); 418 419 // Rescan this successor... 420 --i; 421 } else { 422 423 } 424 } else { 425 // Get the basic blocks that we need... 426 BasicBlock *LastDead = LastNode->getBlock(); 427 BasicBlock *NextAlive = NextNode->getBlock(); 428 429 // Make the conditional branch now go to the next alive block... 430 TI->getSuccessor(i)->removePredecessor(BB); 431 TI->setSuccessor(i, NextAlive); 432 433 // If there are PHI nodes in NextAlive, we need to add entries to 434 // the PHI nodes for the new incoming edge. The incoming values 435 // should be identical to the incoming values for LastDead. 436 // 437 for (BasicBlock::iterator II = NextAlive->begin(); 438 isa<PHINode>(II); ++II) { 439 PHINode *PN = cast<PHINode>(II); 440 if (LiveSet.count(PN)) { // Only modify live phi nodes 441 // Get the incoming value for LastDead... 442 int OldIdx = PN->getBasicBlockIndex(LastDead); 443 assert(OldIdx != -1 &&"LastDead is not a pred of NextAlive!"); 444 Value *InVal = PN->getIncomingValue(OldIdx); 445 446 // Add an incoming value for BB now... 447 PN->addIncoming(InVal, BB); 448 } 449 } 450 } 451 } 452 453 // Now loop over all of the instructions in the basic block, deleting 454 // dead instructions. This is so that the next sweep over the program 455 // can safely delete dead instructions without other dead instructions 456 // still referring to them. 457 // 458 deleteDeadInstructionsInLiveBlock(BB); 459 } 460 461 // Loop over all of the basic blocks in the function, dropping references of 462 // the dead basic blocks. We must do this after the previous step to avoid 463 // dropping references to PHIs which still have entries... 464 // 465 std::vector<BasicBlock*> DeadBlocks; 466 for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) 467 if (!AliveBlocks.count(BB)) { 468 // Remove PHI node entries for this block in live successor blocks. 469 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 470 if (!SI->empty() && isa<PHINode>(SI->front()) && AliveBlocks.count(*SI)) 471 (*SI)->removePredecessor(BB); 472 473 BB->dropAllReferences(); 474 MadeChanges = true; 475 DeadBlocks.push_back(BB); 476 } 477 478 NumBlockRemoved += DeadBlocks.size(); 479 480 // Now loop through all of the blocks and delete the dead ones. We can safely 481 // do this now because we know that there are no references to dead blocks 482 // (because they have dropped all of their references). 483 for (std::vector<BasicBlock*>::iterator I = DeadBlocks.begin(), 484 E = DeadBlocks.end(); I != E; ++I) 485 Func->getBasicBlockList().erase(*I); 486 487 return MadeChanges; 488} 489