//===- ADCE.cpp - Code to perform dead code elimination -------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file implements the Aggressive Dead Code Elimination pass. This pass // optimistically assumes that all instructions are dead until proven otherwise, // allowing it to eliminate dead computations that other DCE passes do not // catch, particularly involving loop computations. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/ADCE.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/IteratedDominanceFrontier.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/DebugLoc.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/Use.h" #include "llvm/IR/Value.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/ProfileData/InstrProf.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" #include #include #include using namespace llvm; #define DEBUG_TYPE "adce" STATISTIC(NumRemoved, "Number of instructions removed"); STATISTIC(NumBranchesRemoved, "Number of branch instructions removed"); // This is a temporary option until we change the interface to this pass based // on optimization level. static cl::opt RemoveControlFlowFlag("adce-remove-control-flow", cl::init(true), cl::Hidden); // This option enables removing of may-be-infinite loops which have no other // effect. static cl::opt RemoveLoops("adce-remove-loops", cl::init(false), cl::Hidden); namespace { /// Information about Instructions struct InstInfoType { /// True if the associated instruction is live. bool Live = false; /// Quick access to information for block containing associated Instruction. struct BlockInfoType *Block = nullptr; }; /// Information about basic blocks relevant to dead code elimination. struct BlockInfoType { /// True when this block contains a live instructions. bool Live = false; /// True when this block ends in an unconditional branch. bool UnconditionalBranch = false; /// True when this block is known to have live PHI nodes. bool HasLivePhiNodes = false; /// Control dependence sources need to be live for this block. bool CFLive = false; /// Quick access to the LiveInfo for the terminator, /// holds the value &InstInfo[Terminator] InstInfoType *TerminatorLiveInfo = nullptr; /// Corresponding BasicBlock. BasicBlock *BB = nullptr; /// Cache of BB->getTerminator(). Instruction *Terminator = nullptr; /// Post-order numbering of reverse control flow graph. unsigned PostOrder; bool terminatorIsLive() const { return TerminatorLiveInfo->Live; } }; class AggressiveDeadCodeElimination { Function &F; // ADCE does not use DominatorTree per se, but it updates it to preserve the // analysis. DominatorTree *DT; PostDominatorTree &PDT; /// Mapping of blocks to associated information, an element in BlockInfoVec. /// Use MapVector to get deterministic iteration order. MapVector BlockInfo; bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; } /// Mapping of instructions to associated information. DenseMap InstInfo; bool isLive(Instruction *I) { return InstInfo[I].Live; } /// Instructions known to be live where we need to mark /// reaching definitions as live. SmallVector Worklist; /// Debug info scopes around a live instruction. SmallPtrSet AliveScopes; /// Set of blocks with not known to have live terminators. SmallSetVector BlocksWithDeadTerminators; /// The set of blocks which we have determined whose control /// dependence sources must be live and which have not had /// those dependences analyzed. SmallPtrSet NewLiveBlocks; /// Set up auxiliary data structures for Instructions and BasicBlocks and /// initialize the Worklist to the set of must-be-live Instruscions. void initialize(); /// Return true for operations which are always treated as live. bool isAlwaysLive(Instruction &I); /// Return true for instrumentation instructions for value profiling. bool isInstrumentsConstant(Instruction &I); /// Propagate liveness to reaching definitions. void markLiveInstructions(); /// Mark an instruction as live. void markLive(Instruction *I); /// Mark a block as live. void markLive(BlockInfoType &BB); void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); } /// Mark terminators of control predecessors of a PHI node live. void markPhiLive(PHINode *PN); /// Record the Debug Scopes which surround live debug information. void collectLiveScopes(const DILocalScope &LS); void collectLiveScopes(const DILocation &DL); /// Analyze dead branches to find those whose branches are the sources /// of control dependences impacting a live block. Those branches are /// marked live. void markLiveBranchesFromControlDependences(); /// Remove instructions not marked live, return if any instruction was /// removed. bool removeDeadInstructions(); /// Identify connected sections of the control flow graph which have /// dead terminators and rewrite the control flow graph to remove them. bool updateDeadRegions(); /// Set the BlockInfo::PostOrder field based on a post-order /// numbering of the reverse control flow graph. void computeReversePostOrder(); /// Make the terminator of this block an unconditional branch to \p Target. void makeUnconditional(BasicBlock *BB, BasicBlock *Target); public: AggressiveDeadCodeElimination(Function &F, DominatorTree *DT, PostDominatorTree &PDT) : F(F), DT(DT), PDT(PDT) {} bool performDeadCodeElimination(); }; } // end anonymous namespace bool AggressiveDeadCodeElimination::performDeadCodeElimination() { initialize(); markLiveInstructions(); return removeDeadInstructions(); } static bool isUnconditionalBranch(Instruction *Term) { auto *BR = dyn_cast(Term); return BR && BR->isUnconditional(); } void AggressiveDeadCodeElimination::initialize() { auto NumBlocks = F.size(); // We will have an entry in the map for each block so we grow the // structure to twice that size to keep the load factor low in the hash table. BlockInfo.reserve(NumBlocks); size_t NumInsts = 0; // Iterate over blocks and initialize BlockInfoVec entries, count // instructions to size the InstInfo hash table. for (auto &BB : F) { NumInsts += BB.size(); auto &Info = BlockInfo[&BB]; Info.BB = &BB; Info.Terminator = BB.getTerminator(); Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator); } // Initialize instruction map and set pointers to block info. InstInfo.reserve(NumInsts); for (auto &BBInfo : BlockInfo) for (Instruction &I : *BBInfo.second.BB) InstInfo[&I].Block = &BBInfo.second; // Since BlockInfoVec holds pointers into InstInfo and vice-versa, we may not // add any more elements to either after this point. for (auto &BBInfo : BlockInfo) BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator]; // Collect the set of "root" instructions that are known live. for (Instruction &I : instructions(F)) if (isAlwaysLive(I)) markLive(&I); if (!RemoveControlFlowFlag) return; if (!RemoveLoops) { // This stores state for the depth-first iterator. In addition // to recording which nodes have been visited we also record whether // a node is currently on the "stack" of active ancestors of the current // node. using StatusMap = DenseMap; class DFState : public StatusMap { public: std::pair insert(BasicBlock *BB) { return StatusMap::insert(std::make_pair(BB, true)); } // Invoked after we have visited all children of a node. void completed(BasicBlock *BB) { (*this)[BB] = false; } // Return true if \p BB is currently on the active stack // of ancestors. bool onStack(BasicBlock *BB) { auto Iter = find(BB); return Iter != end() && Iter->second; } } State; State.reserve(F.size()); // Iterate over blocks in depth-first pre-order and // treat all edges to a block already seen as loop back edges // and mark the branch live it if there is a back edge. for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) { Instruction *Term = BB->getTerminator(); if (isLive(Term)) continue; for (auto *Succ : successors(BB)) if (State.onStack(Succ)) { // back edge.... markLive(Term); break; } } } // Mark blocks live if there is no path from the block to a // return of the function. // We do this by seeing which of the postdomtree root children exit the // program, and for all others, mark the subtree live. for (auto &PDTChild : children(PDT.getRootNode())) { auto *BB = PDTChild->getBlock(); auto &Info = BlockInfo[BB]; // Real function return if (isa(Info.Terminator)) { LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName() << '\n';); continue; } // This child is something else, like an infinite loop. for (auto DFNode : depth_first(PDTChild)) markLive(BlockInfo[DFNode->getBlock()].Terminator); } // Treat the entry block as always live auto *BB = &F.getEntryBlock(); auto &EntryInfo = BlockInfo[BB]; EntryInfo.Live = true; if (EntryInfo.UnconditionalBranch) markLive(EntryInfo.Terminator); // Build initial collection of blocks with dead terminators for (auto &BBInfo : BlockInfo) if (!BBInfo.second.terminatorIsLive()) BlocksWithDeadTerminators.insert(BBInfo.second.BB); } bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) { // TODO -- use llvm::isInstructionTriviallyDead if (I.isEHPad() || I.mayHaveSideEffects()) { // Skip any value profile instrumentation calls if they are // instrumenting constants. if (isInstrumentsConstant(I)) return false; return true; } if (!I.isTerminator()) return false; if (RemoveControlFlowFlag && (isa(I) || isa(I))) return false; return true; } // Check if this instruction is a runtime call for value profiling and // if it's instrumenting a constant. bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) { // TODO -- move this test into llvm::isInstructionTriviallyDead if (CallInst *CI = dyn_cast(&I)) if (Function *Callee = CI->getCalledFunction()) if (Callee->getName().equals(getInstrProfValueProfFuncName())) if (isa(CI->getArgOperand(0))) return true; return false; } void AggressiveDeadCodeElimination::markLiveInstructions() { // Propagate liveness backwards to operands. do { // Worklist holds newly discovered live instructions // where we need to mark the inputs as live. while (!Worklist.empty()) { Instruction *LiveInst = Worklist.pop_back_val(); LLVM_DEBUG(dbgs() << "work live: "; LiveInst->dump();); for (Use &OI : LiveInst->operands()) if (Instruction *Inst = dyn_cast(OI)) markLive(Inst); if (auto *PN = dyn_cast(LiveInst)) markPhiLive(PN); } // After data flow liveness has been identified, examine which branch // decisions are required to determine live instructions are executed. markLiveBranchesFromControlDependences(); } while (!Worklist.empty()); } void AggressiveDeadCodeElimination::markLive(Instruction *I) { auto &Info = InstInfo[I]; if (Info.Live) return; LLVM_DEBUG(dbgs() << "mark live: "; I->dump()); Info.Live = true; Worklist.push_back(I); // Collect the live debug info scopes attached to this instruction. if (const DILocation *DL = I->getDebugLoc()) collectLiveScopes(*DL); // Mark the containing block live auto &BBInfo = *Info.Block; if (BBInfo.Terminator == I) { BlocksWithDeadTerminators.remove(BBInfo.BB); // For live terminators, mark destination blocks // live to preserve this control flow edges. if (!BBInfo.UnconditionalBranch) for (auto *BB : successors(I->getParent())) markLive(BB); } markLive(BBInfo); } void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) { if (BBInfo.Live) return; LLVM_DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n'); BBInfo.Live = true; if (!BBInfo.CFLive) { BBInfo.CFLive = true; NewLiveBlocks.insert(BBInfo.BB); } // Mark unconditional branches at the end of live // blocks as live since there is no work to do for them later if (BBInfo.UnconditionalBranch) markLive(BBInfo.Terminator); } void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) { if (!AliveScopes.insert(&LS).second) return; if (isa(LS)) return; // Tail-recurse through the scope chain. collectLiveScopes(cast(*LS.getScope())); } void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) { // Even though DILocations are not scopes, shove them into AliveScopes so we // don't revisit them. if (!AliveScopes.insert(&DL).second) return; // Collect live scopes from the scope chain. collectLiveScopes(*DL.getScope()); // Tail-recurse through the inlined-at chain. if (const DILocation *IA = DL.getInlinedAt()) collectLiveScopes(*IA); } void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) { auto &Info = BlockInfo[PN->getParent()]; // Only need to check this once per block. if (Info.HasLivePhiNodes) return; Info.HasLivePhiNodes = true; // If a predecessor block is not live, mark it as control-flow live // which will trigger marking live branches upon which // that block is control dependent. for (auto *PredBB : predecessors(Info.BB)) { auto &Info = BlockInfo[PredBB]; if (!Info.CFLive) { Info.CFLive = true; NewLiveBlocks.insert(PredBB); } } } void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() { if (BlocksWithDeadTerminators.empty()) return; LLVM_DEBUG({ dbgs() << "new live blocks:\n"; for (auto *BB : NewLiveBlocks) dbgs() << "\t" << BB->getName() << '\n'; dbgs() << "dead terminator blocks:\n"; for (auto *BB : BlocksWithDeadTerminators) dbgs() << "\t" << BB->getName() << '\n'; }); // The dominance frontier of a live block X in the reverse // control graph is the set of blocks upon which X is control // dependent. The following sequence computes the set of blocks // which currently have dead terminators that are control // dependence sources of a block which is in NewLiveBlocks. const SmallPtrSet BWDT{ BlocksWithDeadTerminators.begin(), BlocksWithDeadTerminators.end() }; SmallVector IDFBlocks; ReverseIDFCalculator IDFs(PDT); IDFs.setDefiningBlocks(NewLiveBlocks); IDFs.setLiveInBlocks(BWDT); IDFs.calculate(IDFBlocks); NewLiveBlocks.clear(); // Dead terminators which control live blocks are now marked live. for (auto *BB : IDFBlocks) { LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n'); markLive(BB->getTerminator()); } } //===----------------------------------------------------------------------===// // // Routines to update the CFG and SSA information before removing dead code. // //===----------------------------------------------------------------------===// bool AggressiveDeadCodeElimination::removeDeadInstructions() { // Updates control and dataflow around dead blocks bool RegionsUpdated = updateDeadRegions(); LLVM_DEBUG({ for (Instruction &I : instructions(F)) { // Check if the instruction is alive. if (isLive(&I)) continue; if (auto *DII = dyn_cast(&I)) { // Check if the scope of this variable location is alive. if (AliveScopes.count(DII->getDebugLoc()->getScope())) continue; // If intrinsic is pointing at a live SSA value, there may be an // earlier optimization bug: if we know the location of the variable, // why isn't the scope of the location alive? if (Value *V = DII->getVariableLocation()) if (Instruction *II = dyn_cast(V)) if (isLive(II)) dbgs() << "Dropping debug info for " << *DII << "\n"; } } }); // The inverse of the live set is the dead set. These are those instructions // that have no side effects and do not influence the control flow or return // value of the function, and may therefore be deleted safely. // NOTE: We reuse the Worklist vector here for memory efficiency. for (Instruction &I : instructions(F)) { // Check if the instruction is alive. if (isLive(&I)) continue; if (auto *DII = dyn_cast(&I)) { // Check if the scope of this variable location is alive. if (AliveScopes.count(DII->getDebugLoc()->getScope())) continue; // Fallthrough and drop the intrinsic. } // Prepare to delete. Worklist.push_back(&I); I.dropAllReferences(); } for (Instruction *&I : Worklist) { ++NumRemoved; I->eraseFromParent(); } return !Worklist.empty() || RegionsUpdated; } // A dead region is the set of dead blocks with a common live post-dominator. bool AggressiveDeadCodeElimination::updateDeadRegions() { LLVM_DEBUG({ dbgs() << "final dead terminator blocks: " << '\n'; for (auto *BB : BlocksWithDeadTerminators) dbgs() << '\t' << BB->getName() << (BlockInfo[BB].Live ? " LIVE\n" : "\n"); }); // Don't compute the post ordering unless we needed it. bool HavePostOrder = false; bool Changed = false; for (auto *BB : BlocksWithDeadTerminators) { auto &Info = BlockInfo[BB]; if (Info.UnconditionalBranch) { InstInfo[Info.Terminator].Live = true; continue; } if (!HavePostOrder) { computeReversePostOrder(); HavePostOrder = true; } // Add an unconditional branch to the successor closest to the // end of the function which insures a path to the exit for each // live edge. BlockInfoType *PreferredSucc = nullptr; for (auto *Succ : successors(BB)) { auto *Info = &BlockInfo[Succ]; if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder) PreferredSucc = Info; } assert((PreferredSucc && PreferredSucc->PostOrder > 0) && "Failed to find safe successor for dead branch"); // Collect removed successors to update the (Post)DominatorTrees. SmallPtrSet RemovedSuccessors; bool First = true; for (auto *Succ : successors(BB)) { if (!First || Succ != PreferredSucc->BB) { Succ->removePredecessor(BB); RemovedSuccessors.insert(Succ); } else First = false; } makeUnconditional(BB, PreferredSucc->BB); // Inform the dominators about the deleted CFG edges. SmallVector DeletedEdges; for (auto *Succ : RemovedSuccessors) { // It might have happened that the same successor appeared multiple times // and the CFG edge wasn't really removed. if (Succ != PreferredSucc->BB) { LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion" << BB->getName() << " -> " << Succ->getName() << "\n"); DeletedEdges.push_back({DominatorTree::Delete, BB, Succ}); } } DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager) .applyUpdates(DeletedEdges); NumBranchesRemoved += 1; Changed = true; } return Changed; } // reverse top-sort order void AggressiveDeadCodeElimination::computeReversePostOrder() { // This provides a post-order numbering of the reverse control flow graph // Note that it is incomplete in the presence of infinite loops but we don't // need numbers blocks which don't reach the end of the functions since // all branches in those blocks are forced live. // For each block without successors, extend the DFS from the block // backward through the graph SmallPtrSet Visited; unsigned PostOrder = 0; for (auto &BB : F) { if (!succ_empty(&BB)) continue; for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited)) BlockInfo[Block].PostOrder = PostOrder++; } } void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB, BasicBlock *Target) { Instruction *PredTerm = BB->getTerminator(); // Collect the live debug info scopes attached to this instruction. if (const DILocation *DL = PredTerm->getDebugLoc()) collectLiveScopes(*DL); // Just mark live an existing unconditional branch if (isUnconditionalBranch(PredTerm)) { PredTerm->setSuccessor(0, Target); InstInfo[PredTerm].Live = true; return; } LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n'); NumBranchesRemoved += 1; IRBuilder<> Builder(PredTerm); auto *NewTerm = Builder.CreateBr(Target); InstInfo[NewTerm].Live = true; if (const DILocation *DL = PredTerm->getDebugLoc()) NewTerm->setDebugLoc(DL); InstInfo.erase(PredTerm); PredTerm->eraseFromParent(); } //===----------------------------------------------------------------------===// // // Pass Manager integration code // //===----------------------------------------------------------------------===// PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) { // ADCE does not need DominatorTree, but require DominatorTree here // to update analysis if it is already available. auto *DT = FAM.getCachedResult(F); auto &PDT = FAM.getResult(F); if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination()) return PreservedAnalyses::all(); PreservedAnalyses PA; // TODO: We could track if we have actually done CFG changes. if (!RemoveControlFlowFlag) PA.preserveSet(); else { PA.preserve(); PA.preserve(); } PA.preserve(); return PA; } namespace { struct ADCELegacyPass : public FunctionPass { static char ID; // Pass identification, replacement for typeid ADCELegacyPass() : FunctionPass(ID) { initializeADCELegacyPassPass(*PassRegistry::getPassRegistry()); } bool runOnFunction(Function &F) override { if (skipFunction(F)) return false; // ADCE does not need DominatorTree, but require DominatorTree here // to update analysis if it is already available. auto *DTWP = getAnalysisIfAvailable(); auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; auto &PDT = getAnalysis().getPostDomTree(); return AggressiveDeadCodeElimination(F, DT, PDT) .performDeadCodeElimination(); } void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); if (!RemoveControlFlowFlag) AU.setPreservesCFG(); else { AU.addPreserved(); AU.addPreserved(); } AU.addPreserved(); } }; } // end anonymous namespace char ADCELegacyPass::ID = 0; INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination", false, false) INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination", false, false) FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }