1 //===- ADCE.cpp - Code to perform dead code elimination -------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the Aggressive Dead Code Elimination pass. This pass 10 // optimistically assumes that all instructions are dead until proven otherwise, 11 // allowing it to eliminate dead computations that other DCE passes do not 12 // catch, particularly involving loop computations. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/Transforms/Scalar/ADCE.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/DepthFirstIterator.h" 19 #include "llvm/ADT/GraphTraits.h" 20 #include "llvm/ADT/MapVector.h" 21 #include "llvm/ADT/PostOrderIterator.h" 22 #include "llvm/ADT/SetVector.h" 23 #include "llvm/ADT/SmallPtrSet.h" 24 #include "llvm/ADT/SmallVector.h" 25 #include "llvm/ADT/Statistic.h" 26 #include "llvm/Analysis/DomTreeUpdater.h" 27 #include "llvm/Analysis/GlobalsModRef.h" 28 #include "llvm/Analysis/IteratedDominanceFrontier.h" 29 #include "llvm/Analysis/PostDominators.h" 30 #include "llvm/IR/BasicBlock.h" 31 #include "llvm/IR/CFG.h" 32 #include "llvm/IR/DebugInfo.h" 33 #include "llvm/IR/DebugInfoMetadata.h" 34 #include "llvm/IR/DebugLoc.h" 35 #include "llvm/IR/Dominators.h" 36 #include "llvm/IR/Function.h" 37 #include "llvm/IR/IRBuilder.h" 38 #include "llvm/IR/InstIterator.h" 39 #include "llvm/IR/Instruction.h" 40 #include "llvm/IR/Instructions.h" 41 #include "llvm/IR/IntrinsicInst.h" 42 #include "llvm/IR/PassManager.h" 43 #include "llvm/IR/Use.h" 44 #include "llvm/IR/Value.h" 45 #include "llvm/InitializePasses.h" 46 #include "llvm/Pass.h" 47 #include "llvm/ProfileData/InstrProf.h" 48 #include "llvm/Support/Casting.h" 49 #include "llvm/Support/CommandLine.h" 50 #include "llvm/Support/Debug.h" 51 #include "llvm/Support/raw_ostream.h" 52 #include "llvm/Transforms/Scalar.h" 53 #include "llvm/Transforms/Utils/Local.h" 54 #include <cassert> 55 #include <cstddef> 56 #include <utility> 57 58 using namespace llvm; 59 60 #define DEBUG_TYPE "adce" 61 62 STATISTIC(NumRemoved, "Number of instructions removed"); 63 STATISTIC(NumBranchesRemoved, "Number of branch instructions removed"); 64 65 // This is a temporary option until we change the interface to this pass based 66 // on optimization level. 67 static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow", 68 cl::init(true), cl::Hidden); 69 70 // This option enables removing of may-be-infinite loops which have no other 71 // effect. 72 static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false), 73 cl::Hidden); 74 75 namespace { 76 77 /// Information about Instructions 78 struct InstInfoType { 79 /// True if the associated instruction is live. 80 bool Live = false; 81 82 /// Quick access to information for block containing associated Instruction. 83 struct BlockInfoType *Block = nullptr; 84 }; 85 86 /// Information about basic blocks relevant to dead code elimination. 87 struct BlockInfoType { 88 /// True when this block contains a live instructions. 89 bool Live = false; 90 91 /// True when this block ends in an unconditional branch. 92 bool UnconditionalBranch = false; 93 94 /// True when this block is known to have live PHI nodes. 95 bool HasLivePhiNodes = false; 96 97 /// Control dependence sources need to be live for this block. 98 bool CFLive = false; 99 100 /// Quick access to the LiveInfo for the terminator, 101 /// holds the value &InstInfo[Terminator] 102 InstInfoType *TerminatorLiveInfo = nullptr; 103 104 /// Corresponding BasicBlock. 105 BasicBlock *BB = nullptr; 106 107 /// Cache of BB->getTerminator(). 108 Instruction *Terminator = nullptr; 109 110 /// Post-order numbering of reverse control flow graph. 111 unsigned PostOrder; 112 113 bool terminatorIsLive() const { return TerminatorLiveInfo->Live; } 114 }; 115 116 class AggressiveDeadCodeElimination { 117 Function &F; 118 119 // ADCE does not use DominatorTree per se, but it updates it to preserve the 120 // analysis. 121 DominatorTree *DT; 122 PostDominatorTree &PDT; 123 124 /// Mapping of blocks to associated information, an element in BlockInfoVec. 125 /// Use MapVector to get deterministic iteration order. 126 MapVector<BasicBlock *, BlockInfoType> BlockInfo; 127 bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; } 128 129 /// Mapping of instructions to associated information. 130 DenseMap<Instruction *, InstInfoType> InstInfo; 131 bool isLive(Instruction *I) { return InstInfo[I].Live; } 132 133 /// Instructions known to be live where we need to mark 134 /// reaching definitions as live. 135 SmallVector<Instruction *, 128> Worklist; 136 137 /// Debug info scopes around a live instruction. 138 SmallPtrSet<const Metadata *, 32> AliveScopes; 139 140 /// Set of blocks with not known to have live terminators. 141 SmallSetVector<BasicBlock *, 16> BlocksWithDeadTerminators; 142 143 /// The set of blocks which we have determined whose control 144 /// dependence sources must be live and which have not had 145 /// those dependences analyzed. 146 SmallPtrSet<BasicBlock *, 16> NewLiveBlocks; 147 148 /// Set up auxiliary data structures for Instructions and BasicBlocks and 149 /// initialize the Worklist to the set of must-be-live Instruscions. 150 void initialize(); 151 152 /// Return true for operations which are always treated as live. 153 bool isAlwaysLive(Instruction &I); 154 155 /// Return true for instrumentation instructions for value profiling. 156 bool isInstrumentsConstant(Instruction &I); 157 158 /// Propagate liveness to reaching definitions. 159 void markLiveInstructions(); 160 161 /// Mark an instruction as live. 162 void markLive(Instruction *I); 163 164 /// Mark a block as live. 165 void markLive(BlockInfoType &BB); 166 void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); } 167 168 /// Mark terminators of control predecessors of a PHI node live. 169 void markPhiLive(PHINode *PN); 170 171 /// Record the Debug Scopes which surround live debug information. 172 void collectLiveScopes(const DILocalScope &LS); 173 void collectLiveScopes(const DILocation &DL); 174 175 /// Analyze dead branches to find those whose branches are the sources 176 /// of control dependences impacting a live block. Those branches are 177 /// marked live. 178 void markLiveBranchesFromControlDependences(); 179 180 /// Remove instructions not marked live, return if any instruction was 181 /// removed. 182 bool removeDeadInstructions(); 183 184 /// Identify connected sections of the control flow graph which have 185 /// dead terminators and rewrite the control flow graph to remove them. 186 bool updateDeadRegions(); 187 188 /// Set the BlockInfo::PostOrder field based on a post-order 189 /// numbering of the reverse control flow graph. 190 void computeReversePostOrder(); 191 192 /// Make the terminator of this block an unconditional branch to \p Target. 193 void makeUnconditional(BasicBlock *BB, BasicBlock *Target); 194 195 public: 196 AggressiveDeadCodeElimination(Function &F, DominatorTree *DT, 197 PostDominatorTree &PDT) 198 : F(F), DT(DT), PDT(PDT) {} 199 200 bool performDeadCodeElimination(); 201 }; 202 203 } // end anonymous namespace 204 205 bool AggressiveDeadCodeElimination::performDeadCodeElimination() { 206 initialize(); 207 markLiveInstructions(); 208 return removeDeadInstructions(); 209 } 210 211 static bool isUnconditionalBranch(Instruction *Term) { 212 auto *BR = dyn_cast<BranchInst>(Term); 213 return BR && BR->isUnconditional(); 214 } 215 216 void AggressiveDeadCodeElimination::initialize() { 217 auto NumBlocks = F.size(); 218 219 // We will have an entry in the map for each block so we grow the 220 // structure to twice that size to keep the load factor low in the hash table. 221 BlockInfo.reserve(NumBlocks); 222 size_t NumInsts = 0; 223 224 // Iterate over blocks and initialize BlockInfoVec entries, count 225 // instructions to size the InstInfo hash table. 226 for (auto &BB : F) { 227 NumInsts += BB.size(); 228 auto &Info = BlockInfo[&BB]; 229 Info.BB = &BB; 230 Info.Terminator = BB.getTerminator(); 231 Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator); 232 } 233 234 // Initialize instruction map and set pointers to block info. 235 InstInfo.reserve(NumInsts); 236 for (auto &BBInfo : BlockInfo) 237 for (Instruction &I : *BBInfo.second.BB) 238 InstInfo[&I].Block = &BBInfo.second; 239 240 // Since BlockInfoVec holds pointers into InstInfo and vice-versa, we may not 241 // add any more elements to either after this point. 242 for (auto &BBInfo : BlockInfo) 243 BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator]; 244 245 // Collect the set of "root" instructions that are known live. 246 for (Instruction &I : instructions(F)) 247 if (isAlwaysLive(I)) 248 markLive(&I); 249 250 if (!RemoveControlFlowFlag) 251 return; 252 253 if (!RemoveLoops) { 254 // This stores state for the depth-first iterator. In addition 255 // to recording which nodes have been visited we also record whether 256 // a node is currently on the "stack" of active ancestors of the current 257 // node. 258 using StatusMap = DenseMap<BasicBlock *, bool>; 259 260 class DFState : public StatusMap { 261 public: 262 std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) { 263 return StatusMap::insert(std::make_pair(BB, true)); 264 } 265 266 // Invoked after we have visited all children of a node. 267 void completed(BasicBlock *BB) { (*this)[BB] = false; } 268 269 // Return true if \p BB is currently on the active stack 270 // of ancestors. 271 bool onStack(BasicBlock *BB) { 272 auto Iter = find(BB); 273 return Iter != end() && Iter->second; 274 } 275 } State; 276 277 State.reserve(F.size()); 278 // Iterate over blocks in depth-first pre-order and 279 // treat all edges to a block already seen as loop back edges 280 // and mark the branch live it if there is a back edge. 281 for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) { 282 Instruction *Term = BB->getTerminator(); 283 if (isLive(Term)) 284 continue; 285 286 for (auto *Succ : successors(BB)) 287 if (State.onStack(Succ)) { 288 // back edge.... 289 markLive(Term); 290 break; 291 } 292 } 293 } 294 295 // Mark blocks live if there is no path from the block to a 296 // return of the function. 297 // We do this by seeing which of the postdomtree root children exit the 298 // program, and for all others, mark the subtree live. 299 for (const auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) { 300 auto *BB = PDTChild->getBlock(); 301 auto &Info = BlockInfo[BB]; 302 // Real function return 303 if (isa<ReturnInst>(Info.Terminator)) { 304 LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName() 305 << '\n';); 306 continue; 307 } 308 309 // This child is something else, like an infinite loop. 310 for (auto *DFNode : depth_first(PDTChild)) 311 markLive(BlockInfo[DFNode->getBlock()].Terminator); 312 } 313 314 // Treat the entry block as always live 315 auto *BB = &F.getEntryBlock(); 316 auto &EntryInfo = BlockInfo[BB]; 317 EntryInfo.Live = true; 318 if (EntryInfo.UnconditionalBranch) 319 markLive(EntryInfo.Terminator); 320 321 // Build initial collection of blocks with dead terminators 322 for (auto &BBInfo : BlockInfo) 323 if (!BBInfo.second.terminatorIsLive()) 324 BlocksWithDeadTerminators.insert(BBInfo.second.BB); 325 } 326 327 bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) { 328 // TODO -- use llvm::isInstructionTriviallyDead 329 if (I.isEHPad() || I.mayHaveSideEffects()) { 330 // Skip any value profile instrumentation calls if they are 331 // instrumenting constants. 332 if (isInstrumentsConstant(I)) 333 return false; 334 return true; 335 } 336 if (!I.isTerminator()) 337 return false; 338 if (RemoveControlFlowFlag && (isa<BranchInst>(I) || isa<SwitchInst>(I))) 339 return false; 340 return true; 341 } 342 343 // Check if this instruction is a runtime call for value profiling and 344 // if it's instrumenting a constant. 345 bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) { 346 // TODO -- move this test into llvm::isInstructionTriviallyDead 347 if (CallInst *CI = dyn_cast<CallInst>(&I)) 348 if (Function *Callee = CI->getCalledFunction()) 349 if (Callee->getName().equals(getInstrProfValueProfFuncName())) 350 if (isa<Constant>(CI->getArgOperand(0))) 351 return true; 352 return false; 353 } 354 355 void AggressiveDeadCodeElimination::markLiveInstructions() { 356 // Propagate liveness backwards to operands. 357 do { 358 // Worklist holds newly discovered live instructions 359 // where we need to mark the inputs as live. 360 while (!Worklist.empty()) { 361 Instruction *LiveInst = Worklist.pop_back_val(); 362 LLVM_DEBUG(dbgs() << "work live: "; LiveInst->dump();); 363 364 for (Use &OI : LiveInst->operands()) 365 if (Instruction *Inst = dyn_cast<Instruction>(OI)) 366 markLive(Inst); 367 368 if (auto *PN = dyn_cast<PHINode>(LiveInst)) 369 markPhiLive(PN); 370 } 371 372 // After data flow liveness has been identified, examine which branch 373 // decisions are required to determine live instructions are executed. 374 markLiveBranchesFromControlDependences(); 375 376 } while (!Worklist.empty()); 377 } 378 379 void AggressiveDeadCodeElimination::markLive(Instruction *I) { 380 auto &Info = InstInfo[I]; 381 if (Info.Live) 382 return; 383 384 LLVM_DEBUG(dbgs() << "mark live: "; I->dump()); 385 Info.Live = true; 386 Worklist.push_back(I); 387 388 // Collect the live debug info scopes attached to this instruction. 389 if (const DILocation *DL = I->getDebugLoc()) 390 collectLiveScopes(*DL); 391 392 // Mark the containing block live 393 auto &BBInfo = *Info.Block; 394 if (BBInfo.Terminator == I) { 395 BlocksWithDeadTerminators.remove(BBInfo.BB); 396 // For live terminators, mark destination blocks 397 // live to preserve this control flow edges. 398 if (!BBInfo.UnconditionalBranch) 399 for (auto *BB : successors(I->getParent())) 400 markLive(BB); 401 } 402 markLive(BBInfo); 403 } 404 405 void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) { 406 if (BBInfo.Live) 407 return; 408 LLVM_DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n'); 409 BBInfo.Live = true; 410 if (!BBInfo.CFLive) { 411 BBInfo.CFLive = true; 412 NewLiveBlocks.insert(BBInfo.BB); 413 } 414 415 // Mark unconditional branches at the end of live 416 // blocks as live since there is no work to do for them later 417 if (BBInfo.UnconditionalBranch) 418 markLive(BBInfo.Terminator); 419 } 420 421 void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) { 422 if (!AliveScopes.insert(&LS).second) 423 return; 424 425 if (isa<DISubprogram>(LS)) 426 return; 427 428 // Tail-recurse through the scope chain. 429 collectLiveScopes(cast<DILocalScope>(*LS.getScope())); 430 } 431 432 void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) { 433 // Even though DILocations are not scopes, shove them into AliveScopes so we 434 // don't revisit them. 435 if (!AliveScopes.insert(&DL).second) 436 return; 437 438 // Collect live scopes from the scope chain. 439 collectLiveScopes(*DL.getScope()); 440 441 // Tail-recurse through the inlined-at chain. 442 if (const DILocation *IA = DL.getInlinedAt()) 443 collectLiveScopes(*IA); 444 } 445 446 void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) { 447 auto &Info = BlockInfo[PN->getParent()]; 448 // Only need to check this once per block. 449 if (Info.HasLivePhiNodes) 450 return; 451 Info.HasLivePhiNodes = true; 452 453 // If a predecessor block is not live, mark it as control-flow live 454 // which will trigger marking live branches upon which 455 // that block is control dependent. 456 for (auto *PredBB : predecessors(Info.BB)) { 457 auto &Info = BlockInfo[PredBB]; 458 if (!Info.CFLive) { 459 Info.CFLive = true; 460 NewLiveBlocks.insert(PredBB); 461 } 462 } 463 } 464 465 void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() { 466 if (BlocksWithDeadTerminators.empty()) 467 return; 468 469 LLVM_DEBUG({ 470 dbgs() << "new live blocks:\n"; 471 for (auto *BB : NewLiveBlocks) 472 dbgs() << "\t" << BB->getName() << '\n'; 473 dbgs() << "dead terminator blocks:\n"; 474 for (auto *BB : BlocksWithDeadTerminators) 475 dbgs() << "\t" << BB->getName() << '\n'; 476 }); 477 478 // The dominance frontier of a live block X in the reverse 479 // control graph is the set of blocks upon which X is control 480 // dependent. The following sequence computes the set of blocks 481 // which currently have dead terminators that are control 482 // dependence sources of a block which is in NewLiveBlocks. 483 484 const SmallPtrSet<BasicBlock *, 16> BWDT{ 485 BlocksWithDeadTerminators.begin(), 486 BlocksWithDeadTerminators.end() 487 }; 488 SmallVector<BasicBlock *, 32> IDFBlocks; 489 ReverseIDFCalculator IDFs(PDT); 490 IDFs.setDefiningBlocks(NewLiveBlocks); 491 IDFs.setLiveInBlocks(BWDT); 492 IDFs.calculate(IDFBlocks); 493 NewLiveBlocks.clear(); 494 495 // Dead terminators which control live blocks are now marked live. 496 for (auto *BB : IDFBlocks) { 497 LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n'); 498 markLive(BB->getTerminator()); 499 } 500 } 501 502 //===----------------------------------------------------------------------===// 503 // 504 // Routines to update the CFG and SSA information before removing dead code. 505 // 506 //===----------------------------------------------------------------------===// 507 bool AggressiveDeadCodeElimination::removeDeadInstructions() { 508 // Updates control and dataflow around dead blocks 509 bool RegionsUpdated = updateDeadRegions(); 510 511 LLVM_DEBUG({ 512 for (Instruction &I : instructions(F)) { 513 // Check if the instruction is alive. 514 if (isLive(&I)) 515 continue; 516 517 if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) { 518 // Check if the scope of this variable location is alive. 519 if (AliveScopes.count(DII->getDebugLoc()->getScope())) 520 continue; 521 522 // If intrinsic is pointing at a live SSA value, there may be an 523 // earlier optimization bug: if we know the location of the variable, 524 // why isn't the scope of the location alive? 525 for (Value *V : DII->location_ops()) { 526 if (Instruction *II = dyn_cast<Instruction>(V)) { 527 if (isLive(II)) { 528 dbgs() << "Dropping debug info for " << *DII << "\n"; 529 break; 530 } 531 } 532 } 533 } 534 } 535 }); 536 537 // The inverse of the live set is the dead set. These are those instructions 538 // that have no side effects and do not influence the control flow or return 539 // value of the function, and may therefore be deleted safely. 540 // NOTE: We reuse the Worklist vector here for memory efficiency. 541 for (Instruction &I : llvm::reverse(instructions(F))) { 542 // Check if the instruction is alive. 543 if (isLive(&I)) 544 continue; 545 546 if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) { 547 // Avoid removing a dbg.assign that is linked to instructions because it 548 // holds information about an existing store. 549 if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII)) 550 if (!at::getAssignmentInsts(DAI).empty()) 551 continue; 552 // Check if the scope of this variable location is alive. 553 if (AliveScopes.count(DII->getDebugLoc()->getScope())) 554 continue; 555 556 // Fallthrough and drop the intrinsic. 557 } 558 559 // Prepare to delete. 560 Worklist.push_back(&I); 561 salvageDebugInfo(I); 562 } 563 564 for (Instruction *&I : Worklist) 565 I->dropAllReferences(); 566 567 for (Instruction *&I : Worklist) { 568 ++NumRemoved; 569 I->eraseFromParent(); 570 } 571 572 return !Worklist.empty() || RegionsUpdated; 573 } 574 575 // A dead region is the set of dead blocks with a common live post-dominator. 576 bool AggressiveDeadCodeElimination::updateDeadRegions() { 577 LLVM_DEBUG({ 578 dbgs() << "final dead terminator blocks: " << '\n'; 579 for (auto *BB : BlocksWithDeadTerminators) 580 dbgs() << '\t' << BB->getName() 581 << (BlockInfo[BB].Live ? " LIVE\n" : "\n"); 582 }); 583 584 // Don't compute the post ordering unless we needed it. 585 bool HavePostOrder = false; 586 bool Changed = false; 587 SmallVector<DominatorTree::UpdateType, 10> DeletedEdges; 588 589 for (auto *BB : BlocksWithDeadTerminators) { 590 auto &Info = BlockInfo[BB]; 591 if (Info.UnconditionalBranch) { 592 InstInfo[Info.Terminator].Live = true; 593 continue; 594 } 595 596 if (!HavePostOrder) { 597 computeReversePostOrder(); 598 HavePostOrder = true; 599 } 600 601 // Add an unconditional branch to the successor closest to the 602 // end of the function which insures a path to the exit for each 603 // live edge. 604 BlockInfoType *PreferredSucc = nullptr; 605 for (auto *Succ : successors(BB)) { 606 auto *Info = &BlockInfo[Succ]; 607 if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder) 608 PreferredSucc = Info; 609 } 610 assert((PreferredSucc && PreferredSucc->PostOrder > 0) && 611 "Failed to find safe successor for dead branch"); 612 613 // Collect removed successors to update the (Post)DominatorTrees. 614 SmallPtrSet<BasicBlock *, 4> RemovedSuccessors; 615 bool First = true; 616 for (auto *Succ : successors(BB)) { 617 if (!First || Succ != PreferredSucc->BB) { 618 Succ->removePredecessor(BB); 619 RemovedSuccessors.insert(Succ); 620 } else 621 First = false; 622 } 623 makeUnconditional(BB, PreferredSucc->BB); 624 625 // Inform the dominators about the deleted CFG edges. 626 for (auto *Succ : RemovedSuccessors) { 627 // It might have happened that the same successor appeared multiple times 628 // and the CFG edge wasn't really removed. 629 if (Succ != PreferredSucc->BB) { 630 LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion" 631 << BB->getName() << " -> " << Succ->getName() 632 << "\n"); 633 DeletedEdges.push_back({DominatorTree::Delete, BB, Succ}); 634 } 635 } 636 637 NumBranchesRemoved += 1; 638 Changed = true; 639 } 640 641 if (!DeletedEdges.empty()) 642 DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager) 643 .applyUpdates(DeletedEdges); 644 645 return Changed; 646 } 647 648 // reverse top-sort order 649 void AggressiveDeadCodeElimination::computeReversePostOrder() { 650 // This provides a post-order numbering of the reverse control flow graph 651 // Note that it is incomplete in the presence of infinite loops but we don't 652 // need numbers blocks which don't reach the end of the functions since 653 // all branches in those blocks are forced live. 654 655 // For each block without successors, extend the DFS from the block 656 // backward through the graph 657 SmallPtrSet<BasicBlock*, 16> Visited; 658 unsigned PostOrder = 0; 659 for (auto &BB : F) { 660 if (!succ_empty(&BB)) 661 continue; 662 for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited)) 663 BlockInfo[Block].PostOrder = PostOrder++; 664 } 665 } 666 667 void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB, 668 BasicBlock *Target) { 669 Instruction *PredTerm = BB->getTerminator(); 670 // Collect the live debug info scopes attached to this instruction. 671 if (const DILocation *DL = PredTerm->getDebugLoc()) 672 collectLiveScopes(*DL); 673 674 // Just mark live an existing unconditional branch 675 if (isUnconditionalBranch(PredTerm)) { 676 PredTerm->setSuccessor(0, Target); 677 InstInfo[PredTerm].Live = true; 678 return; 679 } 680 LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n'); 681 NumBranchesRemoved += 1; 682 IRBuilder<> Builder(PredTerm); 683 auto *NewTerm = Builder.CreateBr(Target); 684 InstInfo[NewTerm].Live = true; 685 if (const DILocation *DL = PredTerm->getDebugLoc()) 686 NewTerm->setDebugLoc(DL); 687 688 InstInfo.erase(PredTerm); 689 PredTerm->eraseFromParent(); 690 } 691 692 //===----------------------------------------------------------------------===// 693 // 694 // Pass Manager integration code 695 // 696 //===----------------------------------------------------------------------===// 697 PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) { 698 // ADCE does not need DominatorTree, but require DominatorTree here 699 // to update analysis if it is already available. 700 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F); 701 auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F); 702 if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination()) 703 return PreservedAnalyses::all(); 704 705 PreservedAnalyses PA; 706 // TODO: We could track if we have actually done CFG changes. 707 if (!RemoveControlFlowFlag) 708 PA.preserveSet<CFGAnalyses>(); 709 else { 710 PA.preserve<DominatorTreeAnalysis>(); 711 PA.preserve<PostDominatorTreeAnalysis>(); 712 } 713 return PA; 714 } 715 716 namespace { 717 718 struct ADCELegacyPass : public FunctionPass { 719 static char ID; // Pass identification, replacement for typeid 720 721 ADCELegacyPass() : FunctionPass(ID) { 722 initializeADCELegacyPassPass(*PassRegistry::getPassRegistry()); 723 } 724 725 bool runOnFunction(Function &F) override { 726 if (skipFunction(F)) 727 return false; 728 729 // ADCE does not need DominatorTree, but require DominatorTree here 730 // to update analysis if it is already available. 731 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 732 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; 733 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); 734 return AggressiveDeadCodeElimination(F, DT, PDT) 735 .performDeadCodeElimination(); 736 } 737 738 void getAnalysisUsage(AnalysisUsage &AU) const override { 739 AU.addRequired<PostDominatorTreeWrapperPass>(); 740 if (!RemoveControlFlowFlag) 741 AU.setPreservesCFG(); 742 else { 743 AU.addPreserved<DominatorTreeWrapperPass>(); 744 AU.addPreserved<PostDominatorTreeWrapperPass>(); 745 } 746 AU.addPreserved<GlobalsAAWrapperPass>(); 747 } 748 }; 749 750 } // end anonymous namespace 751 752 char ADCELegacyPass::ID = 0; 753 754 INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce", 755 "Aggressive Dead Code Elimination", false, false) 756 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) 757 INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination", 758 false, false) 759 760 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); } 761