734 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the Aggressive Dead Code Elimination pass. This pass10// optimistically assumes that all instructions are dead until proven otherwise,11// allowing it to eliminate dead computations that other DCE passes do not12// 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/MemorySSA.h"30#include "llvm/Analysis/PostDominators.h"31#include "llvm/IR/BasicBlock.h"32#include "llvm/IR/CFG.h"33#include "llvm/IR/DebugInfo.h"34#include "llvm/IR/DebugInfoMetadata.h"35#include "llvm/IR/DebugLoc.h"36#include "llvm/IR/Dominators.h"37#include "llvm/IR/Function.h"38#include "llvm/IR/IRBuilder.h"39#include "llvm/IR/InstIterator.h"40#include "llvm/IR/Instruction.h"41#include "llvm/IR/Instructions.h"42#include "llvm/IR/IntrinsicInst.h"43#include "llvm/IR/PassManager.h"44#include "llvm/IR/Use.h"45#include "llvm/IR/Value.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/Utils/Local.h"52#include <cassert>53#include <cstddef>54#include <utility>55 56using namespace llvm;57 58#define DEBUG_TYPE "adce"59 60STATISTIC(NumRemoved, "Number of instructions removed");61STATISTIC(NumBranchesRemoved, "Number of branch instructions removed");62 63// This is a temporary option until we change the interface to this pass based64// on optimization level.65static 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 other69// effect.70static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false),71 cl::Hidden);72 73namespace {74 75/// Information about Instructions76struct 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.85struct 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 114struct ADCEChanged {115 bool ChangedAnything = false;116 bool ChangedNonDebugInstr = false;117 bool ChangedControlFlow = false;118};119 120class AggressiveDeadCodeElimination {121 Function &F;122 123 // ADCE does not use DominatorTree per se, but it updates it to preserve the124 // analysis.125 DominatorTree *DT;126 PostDominatorTree &PDT;127 128 /// Mapping of blocks to associated information, an element in BlockInfoVec.129 /// Use MapVector to get deterministic iteration order.130 MapVector<BasicBlock *, BlockInfoType> BlockInfo;131 bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; }132 133 /// Mapping of instructions to associated information.134 DenseMap<Instruction *, InstInfoType> InstInfo;135 bool isLive(Instruction *I) { return InstInfo[I].Live; }136 137 /// Instructions known to be live where we need to mark138 /// reaching definitions as live.139 SmallVector<Instruction *, 128> Worklist;140 141 /// Debug info scopes around a live instruction.142 SmallPtrSet<const Metadata *, 32> AliveScopes;143 144 /// Set of blocks with not known to have live terminators.145 SmallSetVector<BasicBlock *, 16> BlocksWithDeadTerminators;146 147 /// The set of blocks which we have determined whose control148 /// dependence sources must be live and which have not had149 /// those dependences analyzed.150 SmallPtrSet<BasicBlock *, 16> NewLiveBlocks;151 152 /// Set up auxiliary data structures for Instructions and BasicBlocks and153 /// initialize the Worklist to the set of must-be-live Instruscions.154 void initialize();155 156 /// Return true for operations which are always treated as live.157 bool isAlwaysLive(Instruction &I);158 159 /// Return true for instrumentation instructions for value profiling.160 bool isInstrumentsConstant(Instruction &I);161 162 /// Propagate liveness to reaching definitions.163 void markLiveInstructions();164 165 /// Mark an instruction as live.166 void markLive(Instruction *I);167 168 /// Mark a block as live.169 void markLive(BlockInfoType &BB);170 void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); }171 172 /// Mark terminators of control predecessors of a PHI node live.173 void markPhiLive(PHINode *PN);174 175 /// Record the Debug Scopes which surround live debug information.176 void collectLiveScopes(const DILocalScope &LS);177 void collectLiveScopes(const DILocation &DL);178 179 /// Analyze dead branches to find those whose branches are the sources180 /// of control dependences impacting a live block. Those branches are181 /// marked live.182 void markLiveBranchesFromControlDependences();183 184 /// Remove instructions not marked live, return if any instruction was185 /// removed.186 ADCEChanged removeDeadInstructions();187 188 /// Identify connected sections of the control flow graph which have189 /// dead terminators and rewrite the control flow graph to remove them.190 bool updateDeadRegions();191 192 /// Set the BlockInfo::PostOrder field based on a post-order193 /// numbering of the reverse control flow graph.194 void computeReversePostOrder();195 196 /// Make the terminator of this block an unconditional branch to \p Target.197 void makeUnconditional(BasicBlock *BB, BasicBlock *Target);198 199public:200 AggressiveDeadCodeElimination(Function &F, DominatorTree *DT,201 PostDominatorTree &PDT)202 : F(F), DT(DT), PDT(PDT) {}203 204 ADCEChanged performDeadCodeElimination();205};206 207} // end anonymous namespace208 209ADCEChanged AggressiveDeadCodeElimination::performDeadCodeElimination() {210 initialize();211 markLiveInstructions();212 return removeDeadInstructions();213}214 215static bool isUnconditionalBranch(Instruction *Term) {216 auto *BR = dyn_cast<BranchInst>(Term);217 return BR && BR->isUnconditional();218}219 220void AggressiveDeadCodeElimination::initialize() {221 auto NumBlocks = F.size();222 223 // We will have an entry in the map for each block so we grow the224 // structure to twice that size to keep the load factor low in the hash table.225 BlockInfo.reserve(NumBlocks);226 size_t NumInsts = 0;227 228 // Iterate over blocks and initialize BlockInfoVec entries, count229 // instructions to size the InstInfo hash table.230 for (auto &BB : F) {231 NumInsts += BB.size();232 auto &Info = BlockInfo[&BB];233 Info.BB = &BB;234 Info.Terminator = BB.getTerminator();235 Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator);236 }237 238 // Initialize instruction map and set pointers to block info.239 InstInfo.reserve(NumInsts);240 for (auto &BBInfo : BlockInfo)241 for (Instruction &I : *BBInfo.second.BB)242 InstInfo[&I].Block = &BBInfo.second;243 244 // Since BlockInfoVec holds pointers into InstInfo and vice-versa, we may not245 // add any more elements to either after this point.246 for (auto &BBInfo : BlockInfo)247 BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator];248 249 // Collect the set of "root" instructions that are known live.250 for (Instruction &I : instructions(F))251 if (isAlwaysLive(I))252 markLive(&I);253 254 if (!RemoveControlFlowFlag)255 return;256 257 if (!RemoveLoops) {258 // This stores state for the depth-first iterator. In addition259 // to recording which nodes have been visited we also record whether260 // a node is currently on the "stack" of active ancestors of the current261 // node.262 using StatusMap = DenseMap<BasicBlock *, bool>;263 264 class DFState : public StatusMap {265 public:266 std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) {267 return StatusMap::insert(std::make_pair(BB, true));268 }269 270 // Invoked after we have visited all children of a node.271 void completed(BasicBlock *BB) { (*this)[BB] = false; }272 273 // Return true if \p BB is currently on the active stack274 // of ancestors.275 bool onStack(BasicBlock *BB) {276 auto Iter = find(BB);277 return Iter != end() && Iter->second;278 }279 } State;280 281 State.reserve(F.size());282 // Iterate over blocks in depth-first pre-order and283 // treat all edges to a block already seen as loop back edges284 // and mark the branch live it if there is a back edge.285 for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) {286 Instruction *Term = BB->getTerminator();287 if (isLive(Term))288 continue;289 290 for (auto *Succ : successors(BB))291 if (State.onStack(Succ)) {292 // back edge....293 markLive(Term);294 break;295 }296 }297 }298 299 // Mark blocks live if there is no path from the block to a300 // return of the function.301 // We do this by seeing which of the postdomtree root children exit the302 // program, and for all others, mark the subtree live.303 for (const auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {304 auto *BB = PDTChild->getBlock();305 auto &Info = BlockInfo[BB];306 // Real function return307 if (isa<ReturnInst>(Info.Terminator)) {308 LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()309 << '\n';);310 continue;311 }312 313 // This child is something else, like an infinite loop.314 for (auto *DFNode : depth_first(PDTChild))315 markLive(BlockInfo[DFNode->getBlock()].Terminator);316 }317 318 // Treat the entry block as always live319 auto *BB = &F.getEntryBlock();320 auto &EntryInfo = BlockInfo[BB];321 EntryInfo.Live = true;322 if (EntryInfo.UnconditionalBranch)323 markLive(EntryInfo.Terminator);324 325 // Build initial collection of blocks with dead terminators326 for (auto &BBInfo : BlockInfo)327 if (!BBInfo.second.terminatorIsLive())328 BlocksWithDeadTerminators.insert(BBInfo.second.BB);329}330 331bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) {332 // TODO -- use llvm::isInstructionTriviallyDead333 if (I.isEHPad() || I.mayHaveSideEffects()) {334 // Skip any value profile instrumentation calls if they are335 // instrumenting constants.336 if (isInstrumentsConstant(I))337 return false;338 return true;339 }340 if (!I.isTerminator())341 return false;342 if (RemoveControlFlowFlag && (isa<BranchInst>(I) || isa<SwitchInst>(I)))343 return false;344 return true;345}346 347// Check if this instruction is a runtime call for value profiling and348// if it's instrumenting a constant.349bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) {350 // TODO -- move this test into llvm::isInstructionTriviallyDead351 if (CallInst *CI = dyn_cast<CallInst>(&I))352 if (Function *Callee = CI->getCalledFunction())353 if (Callee->getName() == getInstrProfValueProfFuncName())354 if (isa<Constant>(CI->getArgOperand(0)))355 return true;356 return false;357}358 359void AggressiveDeadCodeElimination::markLiveInstructions() {360 // Propagate liveness backwards to operands.361 do {362 // Worklist holds newly discovered live instructions363 // where we need to mark the inputs as live.364 while (!Worklist.empty()) {365 Instruction *LiveInst = Worklist.pop_back_val();366 LLVM_DEBUG(dbgs() << "work live: "; LiveInst->dump(););367 368 for (Use &OI : LiveInst->operands())369 if (Instruction *Inst = dyn_cast<Instruction>(OI))370 markLive(Inst);371 372 if (auto *PN = dyn_cast<PHINode>(LiveInst))373 markPhiLive(PN);374 }375 376 // After data flow liveness has been identified, examine which branch377 // decisions are required to determine live instructions are executed.378 markLiveBranchesFromControlDependences();379 380 } while (!Worklist.empty());381}382 383void AggressiveDeadCodeElimination::markLive(Instruction *I) {384 auto &Info = InstInfo[I];385 if (Info.Live)386 return;387 388 LLVM_DEBUG(dbgs() << "mark live: "; I->dump());389 Info.Live = true;390 Worklist.push_back(I);391 392 // Collect the live debug info scopes attached to this instruction.393 if (const DILocation *DL = I->getDebugLoc())394 collectLiveScopes(*DL);395 396 // Mark the containing block live397 auto &BBInfo = *Info.Block;398 if (BBInfo.Terminator == I) {399 BlocksWithDeadTerminators.remove(BBInfo.BB);400 // For live terminators, mark destination blocks401 // live to preserve this control flow edges.402 if (!BBInfo.UnconditionalBranch)403 for (auto *BB : successors(I->getParent()))404 markLive(BB);405 }406 markLive(BBInfo);407}408 409void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) {410 if (BBInfo.Live)411 return;412 LLVM_DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n');413 BBInfo.Live = true;414 if (!BBInfo.CFLive) {415 BBInfo.CFLive = true;416 NewLiveBlocks.insert(BBInfo.BB);417 }418 419 // Mark unconditional branches at the end of live420 // blocks as live since there is no work to do for them later421 if (BBInfo.UnconditionalBranch)422 markLive(BBInfo.Terminator);423}424 425void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) {426 if (!AliveScopes.insert(&LS).second)427 return;428 429 if (isa<DISubprogram>(LS))430 return;431 432 // Tail-recurse through the scope chain.433 collectLiveScopes(cast<DILocalScope>(*LS.getScope()));434}435 436void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) {437 // Even though DILocations are not scopes, shove them into AliveScopes so we438 // don't revisit them.439 if (!AliveScopes.insert(&DL).second)440 return;441 442 // Collect live scopes from the scope chain.443 collectLiveScopes(*DL.getScope());444 445 // Tail-recurse through the inlined-at chain.446 if (const DILocation *IA = DL.getInlinedAt())447 collectLiveScopes(*IA);448}449 450void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) {451 auto &Info = BlockInfo[PN->getParent()];452 // Only need to check this once per block.453 if (Info.HasLivePhiNodes)454 return;455 Info.HasLivePhiNodes = true;456 457 // If a predecessor block is not live, mark it as control-flow live458 // which will trigger marking live branches upon which459 // that block is control dependent.460 for (auto *PredBB : predecessors(Info.BB)) {461 auto &Info = BlockInfo[PredBB];462 if (!Info.CFLive) {463 Info.CFLive = true;464 NewLiveBlocks.insert(PredBB);465 }466 }467}468 469void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {470 if (BlocksWithDeadTerminators.empty())471 return;472 473 LLVM_DEBUG({474 dbgs() << "new live blocks:\n";475 for (auto *BB : NewLiveBlocks)476 dbgs() << "\t" << BB->getName() << '\n';477 dbgs() << "dead terminator blocks:\n";478 for (auto *BB : BlocksWithDeadTerminators)479 dbgs() << "\t" << BB->getName() << '\n';480 });481 482 // The dominance frontier of a live block X in the reverse483 // control graph is the set of blocks upon which X is control484 // dependent. The following sequence computes the set of blocks485 // which currently have dead terminators that are control486 // dependence sources of a block which is in NewLiveBlocks.487 488 const SmallPtrSet<BasicBlock *, 16> BWDT(llvm::from_range,489 BlocksWithDeadTerminators);490 SmallVector<BasicBlock *, 32> IDFBlocks;491 ReverseIDFCalculator IDFs(PDT);492 IDFs.setDefiningBlocks(NewLiveBlocks);493 IDFs.setLiveInBlocks(BWDT);494 IDFs.calculate(IDFBlocks);495 NewLiveBlocks.clear();496 497 // Dead terminators which control live blocks are now marked live.498 for (auto *BB : IDFBlocks) {499 LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');500 markLive(BB->getTerminator());501 }502}503 504//===----------------------------------------------------------------------===//505//506// Routines to update the CFG and SSA information before removing dead code.507//508//===----------------------------------------------------------------------===//509ADCEChanged AggressiveDeadCodeElimination::removeDeadInstructions() {510 ADCEChanged Changed;511 // Updates control and dataflow around dead blocks512 Changed.ChangedControlFlow = updateDeadRegions();513 514 LLVM_DEBUG({515 for (Instruction &I : instructions(F)) {516 // Check if the instruction is alive.517 if (isLive(&I))518 continue;519 520 if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {521 // Check if the scope of this variable location is alive.522 if (AliveScopes.count(DII->getDebugLoc()->getScope()))523 continue;524 525 // If intrinsic is pointing at a live SSA value, there may be an526 // earlier optimization bug: if we know the location of the variable,527 // why isn't the scope of the location alive?528 for (Value *V : DII->location_ops()) {529 if (Instruction *II = dyn_cast<Instruction>(V)) {530 if (isLive(II)) {531 dbgs() << "Dropping debug info for " << *DII << "\n";532 break;533 }534 }535 }536 }537 }538 });539 540 // The inverse of the live set is the dead set. These are those instructions541 // that have no side effects and do not influence the control flow or return542 // value of the function, and may therefore be deleted safely.543 // NOTE: We reuse the Worklist vector here for memory efficiency.544 for (Instruction &I : llvm::reverse(instructions(F))) {545 // With "RemoveDIs" debug-info stored in DbgVariableRecord objects,546 // debug-info attached to this instruction, and drop any for scopes that547 // aren't alive, like the rest of this loop does. Extending support to548 // assignment tracking is future work.549 for (DbgRecord &DR : make_early_inc_range(I.getDbgRecordRange())) {550 // Avoid removing a DVR that is linked to instructions because it holds551 // information about an existing store.552 if (DbgVariableRecord *DVR = dyn_cast<DbgVariableRecord>(&DR);553 DVR && DVR->isDbgAssign())554 if (!at::getAssignmentInsts(DVR).empty())555 continue;556 if (AliveScopes.count(DR.getDebugLoc()->getScope()))557 continue;558 I.dropOneDbgRecord(&DR);559 }560 561 // Check if the instruction is alive.562 if (isLive(&I))563 continue;564 565 Changed.ChangedNonDebugInstr = true;566 567 // Prepare to delete.568 Worklist.push_back(&I);569 salvageDebugInfo(I);570 }571 572 for (Instruction *&I : Worklist)573 I->dropAllReferences();574 575 for (Instruction *&I : Worklist) {576 ++NumRemoved;577 I->eraseFromParent();578 }579 580 Changed.ChangedAnything = Changed.ChangedControlFlow || !Worklist.empty();581 582 return Changed;583}584 585// A dead region is the set of dead blocks with a common live post-dominator.586bool AggressiveDeadCodeElimination::updateDeadRegions() {587 LLVM_DEBUG({588 dbgs() << "final dead terminator blocks: " << '\n';589 for (auto *BB : BlocksWithDeadTerminators)590 dbgs() << '\t' << BB->getName()591 << (BlockInfo[BB].Live ? " LIVE\n" : "\n");592 });593 594 // Don't compute the post ordering unless we needed it.595 bool HavePostOrder = false;596 bool Changed = false;597 SmallVector<DominatorTree::UpdateType, 10> DeletedEdges;598 599 for (auto *BB : BlocksWithDeadTerminators) {600 auto &Info = BlockInfo[BB];601 if (Info.UnconditionalBranch) {602 InstInfo[Info.Terminator].Live = true;603 continue;604 }605 606 if (!HavePostOrder) {607 computeReversePostOrder();608 HavePostOrder = true;609 }610 611 // Add an unconditional branch to the successor closest to the612 // end of the function which insures a path to the exit for each613 // live edge.614 BlockInfoType *PreferredSucc = nullptr;615 for (auto *Succ : successors(BB)) {616 auto *Info = &BlockInfo[Succ];617 if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)618 PreferredSucc = Info;619 }620 assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&621 "Failed to find safe successor for dead branch");622 623 // Collect removed successors to update the (Post)DominatorTrees.624 SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;625 bool First = true;626 for (auto *Succ : successors(BB)) {627 if (!First || Succ != PreferredSucc->BB) {628 Succ->removePredecessor(BB);629 RemovedSuccessors.insert(Succ);630 } else631 First = false;632 }633 makeUnconditional(BB, PreferredSucc->BB);634 635 // Inform the dominators about the deleted CFG edges.636 for (auto *Succ : RemovedSuccessors) {637 // It might have happened that the same successor appeared multiple times638 // and the CFG edge wasn't really removed.639 if (Succ != PreferredSucc->BB) {640 LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"641 << BB->getName() << " -> " << Succ->getName()642 << "\n");643 DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});644 }645 }646 647 NumBranchesRemoved += 1;648 Changed = true;649 }650 651 if (!DeletedEdges.empty())652 DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager)653 .applyUpdates(DeletedEdges);654 655 return Changed;656}657 658// reverse top-sort order659void AggressiveDeadCodeElimination::computeReversePostOrder() {660 // This provides a post-order numbering of the reverse control flow graph661 // Note that it is incomplete in the presence of infinite loops but we don't662 // need numbers blocks which don't reach the end of the functions since663 // all branches in those blocks are forced live.664 665 // For each block without successors, extend the DFS from the block666 // backward through the graph667 SmallPtrSet<BasicBlock*, 16> Visited;668 unsigned PostOrder = 0;669 for (auto &BB : F) {670 if (!succ_empty(&BB))671 continue;672 for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited))673 BlockInfo[Block].PostOrder = PostOrder++;674 }675}676 677void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,678 BasicBlock *Target) {679 Instruction *PredTerm = BB->getTerminator();680 // Collect the live debug info scopes attached to this instruction.681 if (const DILocation *DL = PredTerm->getDebugLoc())682 collectLiveScopes(*DL);683 684 // Just mark live an existing unconditional branch685 if (isUnconditionalBranch(PredTerm)) {686 PredTerm->setSuccessor(0, Target);687 InstInfo[PredTerm].Live = true;688 return;689 }690 LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');691 NumBranchesRemoved += 1;692 IRBuilder<> Builder(PredTerm);693 auto *NewTerm = Builder.CreateBr(Target);694 InstInfo[NewTerm].Live = true;695 if (const DILocation *DL = PredTerm->getDebugLoc())696 NewTerm->setDebugLoc(DL);697 698 InstInfo.erase(PredTerm);699 PredTerm->eraseFromParent();700}701 702//===----------------------------------------------------------------------===//703//704// Pass Manager integration code705//706//===----------------------------------------------------------------------===//707PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {708 // ADCE does not need DominatorTree, but require DominatorTree here709 // to update analysis if it is already available.710 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);711 auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);712 ADCEChanged Changed =713 AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination();714 if (!Changed.ChangedAnything)715 return PreservedAnalyses::all();716 717 PreservedAnalyses PA;718 if (!Changed.ChangedControlFlow) {719 PA.preserveSet<CFGAnalyses>();720 if (!Changed.ChangedNonDebugInstr) {721 // Only removing debug instructions does not affect MemorySSA.722 //723 // Therefore we preserve MemorySSA when only removing debug instructions724 // since otherwise later passes may behave differently which then makes725 // the presence of debug info affect code generation.726 PA.preserve<MemorySSAAnalysis>();727 }728 }729 PA.preserve<DominatorTreeAnalysis>();730 PA.preserve<PostDominatorTreeAnalysis>();731 732 return PA;733}734