| //===--- DeadCodeElimination.cpp - Delete dead code ----------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "sil-dce" |
| #include "swift/SIL/SILArgument.h" |
| #include "swift/SIL/SILBasicBlock.h" |
| #include "swift/SIL/SILBuilder.h" |
| #include "swift/SIL/SILFunction.h" |
| #include "swift/SIL/SILUndef.h" |
| #include "swift/SIL/DebugUtils.h" |
| #include "swift/SILOptimizer/Analysis/DominanceAnalysis.h" |
| #include "swift/SILOptimizer/PassManager/Passes.h" |
| #include "swift/SILOptimizer/PassManager/Transforms.h" |
| #include "swift/SILOptimizer/Utils/Local.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| |
| using namespace swift; |
| |
| STATISTIC(NumBranchesPromoted, "Number of dead branches promoted to jumps"); |
| STATISTIC(NumDeletedInsts, "Number of instructions deleted"); |
| |
| namespace { |
| |
| // Without any complex analysis, does this instruction seem like |
| // something that we need to keep? |
| // FIXME: Reconcile the similarities between this and |
| // isInstructionTriviallyDead. |
| static bool seemsUseful(SILInstruction *I) { |
| if (I->mayHaveSideEffects()) |
| return true; |
| |
| if (auto *BI = dyn_cast<BuiltinInst>(I)) { |
| // Although the onFastPath builtin has no side-effects we don't want to |
| // remove it. |
| return BI->getBuiltinInfo().ID == BuiltinValueKind::OnFastPath; |
| } |
| |
| if (isa<UnreachableInst>(I)) |
| return true; |
| if (auto TI = dyn_cast<TermInst>(I)) { |
| if (TI->isFunctionExiting()) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| // We map from post-dominator tree node to a ControllingInfo struct |
| // which contains the post-dominator tree level of this node, along |
| // with the direct predecessors that this node is control-dependent |
| // on, and the minimum level number of any predecessor in the subtree |
| // below this node in the post-dominator tree. |
| struct ControllingInfo { |
| typedef std::pair<SILBasicBlock *, unsigned> PredInfo; |
| |
| SILBasicBlock *Block; |
| // The post-dominator tree level for this node. |
| unsigned Level; |
| llvm::SmallVector<PredInfo, 2> ControllingPreds; |
| unsigned MinTreePredLevel; |
| }; |
| |
| class DCE : public SILFunctionTransform { |
| typedef llvm::DomTreeNodeBase<SILBasicBlock> PostDomTreeNode; |
| |
| llvm::SmallPtrSet<SILNode *, 16> LiveValues; |
| llvm::SmallPtrSet<SILBasicBlock *, 16> LiveBlocks; |
| llvm::SmallVector<SILInstruction *, 64> Worklist; |
| PostDominanceInfo *PDT; |
| llvm::DenseMap<SILBasicBlock *, ControllingInfo> ControllingInfoMap; |
| |
| // Maps instructions which produce a failing condition (like overflow |
| // builtins) to the actual cond_fail instructions which handle the failure. |
| |
| // Dependencies which go in the reverse direction. Usually for a pair |
| // %1 = inst_a |
| // inst_b(%1) |
| // the dependency goes from inst_b to inst_a: if inst_b is alive then also |
| // inst_a is alive. |
| // For some instructions the dependency is exactly the other way round, e.g. |
| // %1 = inst_which_can_fail |
| // cond_fail(%1) |
| // In this case cond_fail is alive only if inst_which_can_fail is alive. |
| // The key of this map is the source of the dependency (inst_a), the |
| // value is the destination (inst_b). |
| llvm::DenseMap<SILInstruction *, SILInstruction *> ReverseDependencies; |
| |
| /// Tracks if the pass changed branches. |
| bool BranchesChanged; |
| /// Tracks if the pass changed ApplyInsts. |
| bool CallsChanged; |
| |
| /// The entry point to the transformation. |
| void run() override { |
| BranchesChanged = false; |
| CallsChanged = false; |
| |
| SILFunction *F = getFunction(); |
| |
| auto *DA = PM->getAnalysis<PostDominanceAnalysis>(); |
| PDT = DA->get(F); |
| |
| // If we have a function that consists of nothing but a |
| // structurally infinite loop like: |
| // while true {} |
| // we'll have an empty post dominator tree. |
| if (!PDT->getRootNode()) |
| return; |
| |
| LLVM_DEBUG(F->dump()); |
| LLVM_DEBUG(PDT->print(llvm::dbgs())); |
| |
| assert(Worklist.empty() && LiveValues.empty() && LiveBlocks.empty() && |
| ControllingInfoMap.empty() && ReverseDependencies.empty() && |
| "Expected to start with empty data structures!"); |
| |
| if (!precomputeControlInfo(*F)) { |
| LiveValues.clear(); |
| LiveBlocks.clear(); |
| ControllingInfoMap.clear(); |
| ReverseDependencies.clear(); |
| return; |
| } |
| |
| markLive(*F); |
| if (removeDead(*F)) { |
| using InvalidationKind = SILAnalysis::InvalidationKind; |
| |
| unsigned Inv = InvalidationKind::Instructions; |
| if (CallsChanged) Inv |= (unsigned) InvalidationKind::Calls; |
| if (BranchesChanged) Inv |= (unsigned) InvalidationKind::Branches; |
| |
| invalidateAnalysis(SILAnalysis::InvalidationKind(Inv)); |
| } |
| |
| LiveValues.clear(); |
| LiveBlocks.clear(); |
| ControllingInfoMap.clear(); |
| ReverseDependencies.clear(); |
| } |
| |
| bool precomputeControlInfo(SILFunction &F); |
| void markLive(SILFunction &F); |
| void addReverseDependency(SILInstruction *From, SILInstruction *To); |
| bool removeDead(SILFunction &F); |
| |
| void computeLevelNumbers(PostDomTreeNode *Node, unsigned Level); |
| bool hasInfiniteLoops(SILFunction &F); |
| void computePredecessorDependence(SILFunction &F); |
| unsigned computeMinPredecessorLevels(PostDomTreeNode *Node); |
| void insertControllingInfo(SILBasicBlock *Block, unsigned Level); |
| |
| void markValueLive(SILNode *V); |
| void markTerminatorArgsLive(SILBasicBlock *Pred, SILBasicBlock *Succ, |
| size_t ArgIndex); |
| void markControllingTerminatorsLive(SILBasicBlock *Block); |
| void propagateLiveBlockArgument(SILArgument *Arg); |
| void propagateLiveness(SILInstruction *I); |
| void collectControllingBlocksInTree(ControllingInfo &QueryInfo, |
| PostDomTreeNode *Node, |
| llvm::SmallPtrSetImpl<SILBasicBlock *> &Controlling); |
| void collectControllingBlocks(SILBasicBlock *Block, |
| llvm::SmallPtrSetImpl<SILBasicBlock *> &); |
| SILBasicBlock *nearestUsefulPostDominator(SILBasicBlock *Block); |
| void replaceBranchWithJump(SILInstruction *Inst, SILBasicBlock *Block); |
| |
| }; |
| |
| // Keep track of the fact that V is live and add it to our worklist |
| // so that we can process the values it depends on. |
| void DCE::markValueLive(SILNode *V) { |
| V = V->getRepresentativeSILNodeInObject(); |
| if (LiveValues.count(V) || isa<SILUndef>(V)) |
| return; |
| |
| LLVM_DEBUG(llvm::dbgs() << "Marking as live:\n"); |
| LLVM_DEBUG(V->dump()); |
| |
| LiveValues.insert(V); |
| |
| if (auto *Def = dyn_cast<SILInstruction>(V)) { |
| markControllingTerminatorsLive(Def->getParent()); |
| Worklist.push_back(Def); |
| return; |
| } |
| |
| // TODO: MultiValueInstruction |
| |
| assert(isa<SILArgument>(V) && |
| "Only expected instructions and arguments!"); |
| |
| auto *Arg = cast<SILArgument>(V); |
| markControllingTerminatorsLive(Arg->getParent()); |
| propagateLiveBlockArgument(Arg); |
| } |
| |
| /// Gets the producing instruction of a cond_fail condition. Currently these |
| /// are overflow builtins but may be extended to other instructions in the |
| /// future. |
| static SILInstruction *getProducer(CondFailInst *CFI) { |
| // Check for the pattern: |
| // %1 = builtin "some_operation_with_overflow" |
| // %2 = tuple_extract %1 |
| // %3 = cond_fail %2 |
| SILValue FailCond = CFI->getOperand(); |
| if (auto *TEI = dyn_cast<TupleExtractInst>(FailCond)) { |
| if (auto *BI = dyn_cast<BuiltinInst>(TEI->getOperand())) { |
| return BI; |
| } |
| } |
| return nullptr; |
| } |
| |
| // Determine which instructions from this function we need to keep. |
| void DCE::markLive(SILFunction &F) { |
| |
| // Find the initial set of instructions in this function that appear |
| // to be live in the sense that they are not trivially something we |
| // can delete by examining only that instruction. |
| for (auto &BB : F) { |
| for (auto &I : BB) { |
| if (auto *CFI = dyn_cast<CondFailInst>(&I)) { |
| // A cond_fail is only alive if its (identifiable) producer is alive. |
| if (SILInstruction *Prod = getProducer(CFI)) { |
| addReverseDependency(Prod, CFI); |
| } else { |
| markValueLive(CFI); |
| } |
| continue; |
| } |
| if (auto *FLI = dyn_cast<FixLifetimeInst>(&I)) { |
| // A fix_lifetime (with a non-address type) is only alive if it's |
| // definition is alive. |
| SILValue Op = FLI->getOperand(); |
| auto *OpInst = Op->getDefiningInstruction(); |
| if (OpInst && !Op->getType().isAddress()) { |
| addReverseDependency(OpInst, FLI); |
| } else { |
| markValueLive(FLI); |
| } |
| continue; |
| } |
| if (seemsUseful(&I)) |
| markValueLive(&I); |
| } |
| } |
| |
| // Now propagate liveness backwards from each instruction in our |
| // worklist, adding new instructions to the worklist as we discover |
| // more that we need to keep. |
| while (!Worklist.empty()) { |
| auto *I = Worklist.pop_back_val(); |
| propagateLiveness(I); |
| } |
| } |
| |
| // Records a reverse dependency. See DCE::ReverseDependencies. |
| void DCE::addReverseDependency(SILInstruction *From, SILInstruction *To) { |
| assert(!ReverseDependencies.lookup(To) && |
| "Target of reverse dependency already in map"); |
| SILInstruction *&Target = ReverseDependencies[From]; |
| SILInstruction *ExistingTarget = Target; |
| Target = To; |
| if (ExistingTarget) { |
| // Create a single linked chain if From has multiple targets. |
| ReverseDependencies[To] = ExistingTarget; |
| } |
| } |
| |
| // Mark as live the terminator argument at index ArgIndex in Pred that |
| // targets Succ. |
| void DCE::markTerminatorArgsLive(SILBasicBlock *Pred, |
| SILBasicBlock *Succ, |
| size_t ArgIndex) { |
| auto *Term = Pred->getTerminator(); |
| |
| // If the arguments are live, we need to keep the terminator that |
| // delivers those arguments. |
| markValueLive(Term); |
| |
| switch (Term->getTermKind()) { |
| case TermKind::ReturnInst: |
| case TermKind::ThrowInst: |
| case TermKind::UnwindInst: |
| case TermKind::YieldInst: |
| |
| case TermKind::UnreachableInst: |
| case TermKind::SwitchValueInst: |
| case TermKind::SwitchEnumAddrInst: |
| case TermKind::CheckedCastAddrBranchInst: |
| llvm_unreachable("Unexpected argument for terminator kind!"); |
| break; |
| |
| case TermKind::DynamicMethodBranchInst: |
| case TermKind::SwitchEnumInst: |
| case TermKind::CheckedCastBranchInst: |
| case TermKind::CheckedCastValueBranchInst: |
| assert(ArgIndex == 0 && "Expected a single argument!"); |
| |
| // We do not need to do anything with these. If the resulting |
| // argument is used at the destination these terminators will end |
| // up live, and then our normal liveness propagation will mark the |
| // single operand of these instructions as live. |
| break; |
| |
| case TermKind::BranchInst: |
| markValueLive(cast<BranchInst>(Term)->getArg(ArgIndex)); |
| break; |
| |
| case TermKind::CondBranchInst: { |
| auto *CondBr = cast<CondBranchInst>(Term); |
| |
| if (CondBr->getTrueBB() == Succ) { |
| auto TrueArgs = CondBr->getTrueArgs(); |
| markValueLive(TrueArgs[ArgIndex]); |
| } |
| |
| if (CondBr->getFalseBB() == Succ) { |
| auto FalseArgs = CondBr->getFalseArgs(); |
| markValueLive(FalseArgs[ArgIndex]); |
| } |
| |
| break; |
| } |
| case TermKind::TryApplyInst: { |
| assert(ArgIndex == 0 && "Expect a single argument!"); |
| break; |
| } |
| } |
| } |
| |
| // Propagate liveness back from Arg to the terminator arguments that |
| // supply its value. |
| void DCE::propagateLiveBlockArgument(SILArgument *Arg) { |
| // Conceptually, the dependency from a debug instruction to its definition |
| // is in reverse direction: Only if its definition (the Arg) is alive, also |
| // the debug_value instruction is alive. |
| for (Operand *DU : getDebugUses(Arg)) |
| markValueLive(DU->getUser()); |
| |
| if (isa<SILFunctionArgument>(Arg)) |
| return; |
| |
| auto *Block = Arg->getParent(); |
| auto ArgIndex = Arg->getIndex(); |
| |
| for (auto Pred : Block->getPredecessorBlocks()) |
| markTerminatorArgsLive(Pred, Block, ArgIndex); |
| } |
| |
| // Given an instruction which is considered live, propagate that liveness |
| // back to the instructions that produce values it consumes. |
| void DCE::propagateLiveness(SILInstruction *I) { |
| if (!isa<TermInst>(I)) { |
| for (auto &O : I->getAllOperands()) |
| markValueLive(O.get()); |
| |
| // Conceptually, the dependency from a debug instruction to its definition |
| // is in reverse direction: Only if its definition is alive, also the |
| // debug_value instruction is alive. |
| for (auto result : I->getResults()) |
| for (Operand *DU : getDebugUses(result)) |
| markValueLive(DU->getUser()); |
| |
| // Handle all other reverse-dependency instructions, like cond_fail and |
| // fix_lifetime. Only if the definition is alive, the user itself is alive. |
| if (SILInstruction *DepInst = ReverseDependencies.lookup(I)) { |
| markValueLive(DepInst); |
| } |
| return; |
| } |
| |
| switch (cast<TermInst>(I)->getTermKind()) { |
| case TermKind::BranchInst: |
| case TermKind::UnreachableInst: |
| case TermKind::UnwindInst: |
| return; |
| |
| case TermKind::ReturnInst: |
| case TermKind::ThrowInst: |
| case TermKind::CondBranchInst: |
| case TermKind::SwitchEnumInst: |
| case TermKind::SwitchEnumAddrInst: |
| case TermKind::DynamicMethodBranchInst: |
| case TermKind::CheckedCastBranchInst: |
| case TermKind::CheckedCastValueBranchInst: |
| markValueLive(I->getOperand(0)); |
| return; |
| |
| case TermKind::TryApplyInst: |
| case TermKind::SwitchValueInst: |
| case TermKind::YieldInst: |
| for (auto &O : I->getAllOperands()) |
| markValueLive(O.get()); |
| return; |
| |
| case TermKind::CheckedCastAddrBranchInst: |
| markValueLive(I->getOperand(0)); |
| markValueLive(I->getOperand(1)); |
| return; |
| } |
| llvm_unreachable("corrupt instruction!"); |
| } |
| |
| SILBasicBlock *DCE::nearestUsefulPostDominator(SILBasicBlock *Block) { |
| // Find the nearest post-dominator that has useful instructions. |
| auto *PostDomNode = PDT->getNode(Block)->getIDom(); |
| while (PostDomNode && !LiveBlocks.count(PostDomNode->getBlock())) |
| PostDomNode = PostDomNode->getIDom(); |
| |
| if (PostDomNode) |
| return PostDomNode->getBlock(); |
| return nullptr; |
| } |
| |
| // Replace the given conditional branching instruction with a plain |
| // jump (aka unconditional branch) to the destination block. |
| void DCE::replaceBranchWithJump(SILInstruction *Inst, SILBasicBlock *Block) { |
| ++NumBranchesPromoted; |
| |
| assert(Block && "Expected a destination block!"); |
| |
| assert((isa<CondBranchInst>(Inst) || |
| isa<SwitchValueInst>(Inst) || |
| isa<SwitchEnumInst>(Inst) || |
| isa<SwitchEnumAddrInst>(Inst) || |
| isa<DynamicMethodBranchInst>(Inst) || |
| isa<CheckedCastBranchInst>(Inst)) && |
| "Unexpected dead terminator kind!"); |
| |
| SILInstruction *Branch; |
| if (!Block->args_empty()) { |
| std::vector<SILValue> Args; |
| auto E = Block->args_end(); |
| for (auto A = Block->args_begin(); A != E; ++A) { |
| assert(!LiveValues.count(*A) && "Unexpected live block argument!"); |
| Args.push_back(SILUndef::get((*A)->getType(), (*A)->getModule())); |
| } |
| Branch = |
| SILBuilderWithScope(Inst).createBranch(Inst->getLoc(), Block, Args); |
| } else { |
| Branch = SILBuilderWithScope(Inst).createBranch(Inst->getLoc(), Block); |
| } |
| LLVM_DEBUG(llvm::dbgs() << "Inserted unconditional branch:\n"); |
| LLVM_DEBUG(Branch->dump()); |
| (void)Branch; |
| } |
| |
| // Remove the instructions that are not potentially useful. |
| bool DCE::removeDead(SILFunction &F) { |
| bool Changed = false; |
| |
| for (auto &BB : F) { |
| for (auto I = BB.args_begin(), E = BB.args_end(); I != E;) { |
| auto Inst = *I++; |
| if (LiveValues.count(Inst)) |
| continue; |
| |
| LLVM_DEBUG(llvm::dbgs() << "Removing dead argument:\n"); |
| LLVM_DEBUG(Inst->dump()); |
| |
| Inst->replaceAllUsesWithUndef(); |
| |
| Changed = true; |
| } |
| |
| for (auto I = BB.begin(), E = BB.end(); I != E; ) { |
| auto *Inst = &*I; |
| I++; |
| if (LiveValues.count(Inst) || isa<BranchInst>(Inst)) |
| continue; |
| |
| // We want to replace dead terminators with unconditional branches to |
| // the nearest post-dominator that has useful instructions. |
| if (isa<TermInst>(Inst)) { |
| SILBasicBlock *postDom = nearestUsefulPostDominator(Inst->getParent()); |
| if (!postDom) |
| continue; |
| |
| replaceBranchWithJump(Inst, postDom); |
| Inst->eraseFromParent(); |
| BranchesChanged = true; |
| Changed = true; |
| continue; |
| } |
| |
| ++NumDeletedInsts; |
| |
| LLVM_DEBUG(llvm::dbgs() << "Removing dead instruction:\n"); |
| LLVM_DEBUG(Inst->dump()); |
| |
| Inst->replaceAllUsesOfAllResultsWithUndef(); |
| |
| if (isa<ApplyInst>(Inst)) |
| CallsChanged = true; |
| |
| Inst->eraseFromParent(); |
| Changed = true; |
| } |
| } |
| |
| return Changed; |
| } |
| |
| // Precompute some information from the post-dominator tree to aid us |
| // in determining control dependence without generating a complete |
| // control dependence graph. Inspired by: |
| // Optimal control dependence and the Roman chariots problem |
| // TOPLAS, v19, issue 3, 1997 |
| // http://dx.doi.org/10.1145/256167.256217 |
| // |
| // For each node in the post-dominator tree we will compute: |
| // -- A level number. |
| // |
| // -- The list of immediate predecessors that this block is |
| // control-dependent on along with the level number in the |
| // post-dominator tree of each of those predecessors. |
| // |
| // -- The lowest level number of any predecessor below the given node |
| // in the post-dominator tree. This will be used to exit early in |
| // later control-dependence queries. |
| // |
| // Returns true upon success, false if nodes that are not present in the |
| // post-dominator tree are detected. |
| bool DCE::precomputeControlInfo(SILFunction &F) { |
| computeLevelNumbers(PDT->getRootNode(), 0); |
| if (hasInfiniteLoops(F)) |
| return false; |
| computePredecessorDependence(F); |
| computeMinPredecessorLevels(PDT->getRootNode()); |
| return true; |
| } |
| |
| void DCE::insertControllingInfo(SILBasicBlock *Block, unsigned Level) { |
| assert(ControllingInfoMap.find(Block) == ControllingInfoMap.end() && |
| "Unexpected map entry for node!"); |
| |
| ControllingInfo Info; |
| Info.Block = Block; |
| Info.Level = Level; |
| Info.MinTreePredLevel = -1; |
| |
| ControllingInfoMap[Block] = Info; |
| } |
| |
| // Assign a level number to each node in the post-dominator tree, and |
| void DCE::computeLevelNumbers(PostDomTreeNode *Node, unsigned Level) { |
| insertControllingInfo(Node->getBlock(), Level); |
| |
| for (auto Child = Node->begin(), End = Node->end(); Child != End; ++Child) |
| computeLevelNumbers(*Child, Level + 1); |
| } |
| |
| // Structurally infinite loops like: |
| // bb1: |
| // br bb1 |
| // are not present in the post-dominator tree. Their presence |
| // requires significant modifications to the way the rest of the |
| // algorithm works. They should be rare, so for now we'll do the most |
| // conservative thing and completely bail out, doing no dead code |
| // elimination. Note this will also hit for unreachable code, but |
| // presumably we'll run DCE at some point after removing unreachable |
| // code. |
| bool DCE::hasInfiniteLoops(SILFunction &F) { |
| for (auto &BB : F) |
| if (ControllingInfoMap.find(&BB) == ControllingInfoMap.end()) |
| return true; |
| |
| return false; |
| } |
| |
| // For each block, create a list of the direct predecessors that the |
| // block is control-dependent on. With each predecessor, also keep the |
| // level number of the predecessor in the post-dominator tree. |
| void DCE::computePredecessorDependence(SILFunction &F) { |
| for (auto &BB : F) { |
| assert(ControllingInfoMap.find(&BB) != ControllingInfoMap.end() |
| && "Expected to already have a map entry for block!"); |
| |
| for (auto Pred : BB.getPredecessorBlocks()) |
| if (!PDT->properlyDominates(&BB, Pred)) { |
| assert(ControllingInfoMap.find(Pred) != ControllingInfoMap.end() && |
| "Expected to already have a map entry for block!"); |
| |
| auto PredLevel = ControllingInfoMap[Pred].Level; |
| auto PredInfo = std::make_pair(Pred, PredLevel); |
| |
| auto &MapElement = ControllingInfoMap[&BB]; |
| MapElement.ControllingPreds.push_back(PredInfo); |
| } |
| } |
| } |
| |
| // Return the minimum post-dominator tree level of any of the |
| // direct controlling predecessors of this node or any child. |
| unsigned DCE::computeMinPredecessorLevels(PostDomTreeNode *Node) { |
| unsigned Min = -1; |
| |
| auto *Block = Node->getBlock(); |
| |
| assert(ControllingInfoMap.find(Block) != ControllingInfoMap.end() && |
| "Expected to have map entry for node!"); |
| |
| auto &MapElement = ControllingInfoMap[Block]; |
| for (auto &PredInfo : MapElement.ControllingPreds) |
| Min = std::min(Min, PredInfo.second); |
| |
| for (auto Child = Node->begin(), End = Node->end(); Child != End; ++Child) |
| Min = std::min(Min, computeMinPredecessorLevels(*Child)); |
| |
| MapElement.MinTreePredLevel = Min; |
| |
| return Min; |
| } |
| |
| void DCE::collectControllingBlocksInTree(ControllingInfo &QueryInfo, |
| PostDomTreeNode *Node, |
| llvm::SmallPtrSetImpl<SILBasicBlock *> &Controlling) { |
| auto *Block = Node->getBlock(); |
| |
| assert(ControllingInfoMap.find(Block) != ControllingInfoMap.end() && |
| "Expected to have map entry for node!"); |
| |
| auto &MapEntry = ControllingInfoMap[Block]; |
| if (MapEntry.MinTreePredLevel > QueryInfo.Level) |
| return; |
| |
| for (auto &PredInfo : MapEntry.ControllingPreds) |
| if (PredInfo.second <= QueryInfo.Level) { |
| assert(PDT->properlyDominates( |
| PDT->getNode(PredInfo.first)->getIDom()->getBlock(), |
| QueryInfo.Block) && |
| "Expected predecessor's post-dominator to post-dominate node."); |
| Controlling.insert(PredInfo.first); |
| } |
| |
| for (auto Child = Node->begin(), End = Node->end(); Child != End; ++Child) |
| collectControllingBlocksInTree(QueryInfo, (*Child), Controlling); |
| } |
| |
| // Walk the post-dominator tree from the query block down, building |
| // the set of blocks that the given block is control-dependent on. To |
| // determine control dependence we use some precomputed information |
| // about the direct predecessors that control each block, along with |
| // the level numbers in the post-dominator tree of those controlling |
| // predecessors. We can use the latter to terminate the walk down the |
| // dominator tree early. |
| void DCE::collectControllingBlocks(SILBasicBlock *Block, |
| llvm::SmallPtrSetImpl<SILBasicBlock *> &Controlling) { |
| // First add the blocks that QueryNode is directly control-dependent on. |
| assert(ControllingInfoMap.find(Block) != ControllingInfoMap.end() && |
| "Expected map entry for node!"); |
| auto &MapEntry = ControllingInfoMap[Block]; |
| |
| // Now walk the children looking for nodes that have controlling |
| // predecessors that have the same or lower level number in the |
| // post-dominator tree. |
| collectControllingBlocksInTree(MapEntry, PDT->getNode(Block), Controlling); |
| } |
| |
| void DCE::markControllingTerminatorsLive(SILBasicBlock *Block) { |
| if (LiveBlocks.count(Block)) |
| return; |
| |
| LiveBlocks.insert(Block); |
| |
| llvm::SmallPtrSet<SILBasicBlock *, 4> ControllingBlocks; |
| collectControllingBlocks(Block, ControllingBlocks); |
| |
| for (auto BB : ControllingBlocks) |
| markValueLive(BB->getTerminator()); |
| } |
| |
| } // end anonymous namespace |
| |
| SILTransform *swift::createDCE() { |
| return new DCE(); |
| } |