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