averello/swift-mirror
1
0
Fork 0
mirror of https://github.com/apple/swift.git synced 2025-12-14 20:36:38 +01:00
Code Issues Packages Projects Releases Wiki Activity
Files
constraintResolutionFix
swift-mirror/lib/SILOptimizer/Transforms/DeadCodeElimination.cpp
Nate Chandler aa85694237 [NFC] OSSACompleteLifetime: Renamed.
2025-08-18 09:45:19 -07:00

1084 lines
38 KiB
C++
Raw Permalink Blame History

//===--- 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/Basic/Assertions.h"
#include "swift/Basic/BlotSetVector.h"
#include "swift/SIL/BasicBlockBits.h"
#include "swift/SIL/DebugUtils.h"
#include "swift/SIL/MemAccessUtils.h"
#include "swift/SIL/NodeBits.h"
#include "swift/SIL/OSSACompleteLifetime.h"
#include "swift/SIL/OwnershipUtils.h"
#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/SILOptimizer/Analysis/DeadEndBlocksAnalysis.h"
#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "swift/SILOptimizer/Utils/BasicBlockOptUtils.h"
#include "swift/SILOptimizer/Utils/CFGOptUtils.h"
#include "swift/SILOptimizer/Utils/InstOptUtils.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.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) {
// Even though begin_access/destroy_value/copy_value/end_lifetime have
// side-effects, they can be DCE'ed if they do not have useful
// dependencies/reverse dependencies
if (isa<BeginAccessInst>(I) || isa<CopyValueInst>(I) ||
isa<DestroyValueInst>(I) || isa<EndLifetimeInst>(I) ||
isa<EndBorrowInst>(I))
return false;
if (isa<UnconditionalCheckedCastInst>(I)) {
return false;
}
// A load [copy] is okay to be DCE'ed if there are no useful dependencies
if (auto *load = dyn_cast<LoadInst>(I)) {
if (load->getOwnershipQualifier() == LoadOwnershipQualifier::Copy)
return false;
}
if (I->mayHaveSideEffects())
return true;
if (llvm::any_of(I->getResults(),
[](auto result) { return result->isLexical(); })) {
return true;
}
// Instructions which end the lifetimes of values which escape can only be
// deleted if compensating lifetime ends are added. Compensating lifetime
// ends are added by OSSACompleteLifetime when the def block of the value
// is different from the parent block of the instruction. But
// OSSACompleteLifetime requires that liveness be complete--that there are no
// pointer escapes. So we can't delete instructions which end the lifetime
// of values which escape to a pointer and whose parent blocks are different.
if (llvm::any_of(I->getAllOperands(), [I](Operand &operand) {
if (!operand.isLifetimeEnding())
return false;
auto value = operand.get();
if (isa<SILUndef>(value))
return false;
auto *insertionPoint = value->getDefiningInsertionPoint();
ASSERT(insertionPoint);
if (insertionPoint->getParent() == I->getParent())
return false;
return findPointerEscape(value);
})) {
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;
}
// Is useful if it's associating with a function argument
// If undef, it is useful and it doesn't cost anything.
if (isa<DebugValueInst>(I))
return isa<SILFunctionArgument>(I->getOperand(0))
|| isa<SILUndef>(I->getOperand(0));
// Don't delete allocation instructions in DCE.
if (isa<AllocRefInst>(I) || isa<AllocRefDynamicInst>(I)) {
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 {
typedef llvm::DomTreeNodeBase<SILBasicBlock> PostDomTreeNode;
SILFunction *F;
ValueSet LiveArguments;
InstructionSet LiveInstructions;
BasicBlockSet LiveBlocks;
llvm::SmallVector<SILInstruction *, 64> Worklist;
PostDominanceInfo *PDT;
DominanceInfo *DT;
DeadEndBlocks *deadEndBlocks;
llvm::DenseMap<SILBasicBlock *, ControllingInfo> ControllingInfoMap;
SmallBlotSetVector<SILValue, 8> valuesToComplete;
// 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
// inst_a is also 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 set of instructions dependent on it (inst_b).
llvm::DenseMap<SILValue, SmallPtrSet<SILInstruction *, 4>>
ReverseDependencies;
// guaranteedPhiDependencies tracks the dependency of reborrows and
// @guaranteed forwarding phis with its base value.
// If the base value is also passed along as a phi operand with the reborrow
// operand/GuaranteedForwardingPhi operand, we will have a new base value
// for the reborrow phi/@guaranteed forwarding phi.
using BaseValueSet = SmallPtrSet<SILValue, 8>;
llvm::DenseMap<SILPhiArgument *, BaseValueSet> guaranteedPhiDependencies;
/// Tracks if the pass changed branches.
bool BranchesChanged = false;
/// Tracks if the pass changed ApplyInsts.
bool CallsChanged = false;
bool precomputeControlInfo();
/// Populates borrow dependencies and disables DCE if needed.
void processBorrow(BorrowedValue borrow);
void markLive();
/// Record a reverse dependency from \p from to \p to meaning \p to is live
/// if \p from is also live.
void addReverseDependency(SILValue from, SILInstruction *to);
/// Starting from \p borrow find all reborrow and guaranteed phi dependencies
/// along with their base values.
void findGuaranteedPhiDependencies(BorrowedValue borrow);
bool removeDead();
void computeLevelNumbers(PostDomTreeNode *root);
bool hasInfiniteLoops();
void computePredecessorDependence();
void computeMinPredecessorLevels(PostDomTreeNode *root);
void insertControllingInfo(SILBasicBlock *Block, unsigned Level);
void markValueLive(SILValue V);
void markInstructionLive(SILInstruction *Inst);
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 *root,
llvm::SmallPtrSetImpl<SILBasicBlock *> &Controlling);
void collectControllingBlocks(SILBasicBlock *Block,
llvm::SmallPtrSetImpl<SILBasicBlock *> &);
SILBasicBlock *nearestUsefulPostDominator(SILBasicBlock *Block);
void replaceBranchWithJump(SILInstruction *Inst, SILBasicBlock *Block);
/// Insert lifetime ending instruction if defining value of \p op is live.
void endLifetimeOfLiveValue(Operand *op, SILInstruction *insertPt);
public:
DCE(SILFunction *F, PostDominanceInfo *PDT, DominanceInfo *DT,
DeadEndBlocks *deadEndBlocks)
: F(F), LiveArguments(F), LiveInstructions(F), LiveBlocks(F), PDT(PDT),
DT(DT), deadEndBlocks(deadEndBlocks) {}
/// The entry point to the transformation.
bool run() {
if (!precomputeControlInfo())
return false;
markLive();
return removeDead();
}
bool mustInvalidateCalls() const { return CallsChanged; }
bool mustInvalidateBranches() const { return BranchesChanged; }
};
// 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(SILValue V) {
if (SILInstruction *inst = V->getDefiningInstruction())
return markInstructionLive(inst);
if (isa<SILUndef>(V))
return;
LLVM_DEBUG(llvm::dbgs() << "Marking as live: " << *V);
auto *Arg = cast<SILArgument>(V);
if (!LiveArguments.insert(Arg))
return;
markControllingTerminatorsLive(Arg->getParent());
propagateLiveBlockArgument(Arg);
}
void DCE::markInstructionLive(SILInstruction *Inst) {
if (!LiveInstructions.insert(Inst))
return;
LLVM_DEBUG(llvm::dbgs() << "Marking as live: " << *Inst);
Worklist.push_back(Inst);
}
/// 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 BuiltinInst *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;
}
void DCE::processBorrow(BorrowedValue borrow) {
// Populate guaranteedPhiDependencies for this borrow
findGuaranteedPhiDependencies(borrow);
if (!borrow.hasReborrow()) {
return;
}
// If the borrow was not computed from another
// borrow, return.
SILValue baseValue;
if (auto *beginBorrow = dyn_cast<BeginBorrowInst>(*borrow)) {
auto borrowOp = beginBorrow->getOperand();
if (borrowOp->getOwnershipKind() != OwnershipKind::Guaranteed) {
return;
}
baseValue = borrowOp;
} else {
auto *loadBorrow = cast<LoadBorrowInst>(*borrow);
auto accessBase = AccessBase::compute(loadBorrow->getOperand());
if (!accessBase.isReference()) {
return;
}
baseValue = accessBase.getReference();
}
// If the borrow was computed from another
// borrow, disable DCE of the outer borrow.
// This is because, when a reborrow is dead, DCE has to insert
// end_borrows in predecessor blocks and it cannot yet handle borrow
// nesting.
// TODO: Instead of disabling DCE of outer borrow, consider inserting
// end_borrows inside-out.
SmallVector<SILValue, 4> roots;
findGuaranteedReferenceRoots(baseValue,
/*lookThroughNestedBorrows=*/false, roots);
// Visit the end_borrows of all the borrow scopes that this
// begin_borrow could be borrowing, and mark them live.
for (auto root : roots) {
visitTransitiveEndBorrows(root, [&](EndBorrowInst *endBorrow) {
markInstructionLive(endBorrow);
});
}
}
// Determine which instructions from this function we need to keep.
void DCE::markLive() {
// 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) {
switch (I.getKind()) {
case SILInstructionKind::CondFailInst: {
if (auto *Prod = getProducer(cast<CondFailInst>(&I))) {
addReverseDependency(Prod, &I);
} else {
markInstructionLive(&I);
}
break;
}
// The side-effects of fix_lifetime effect all references to the same
// object. It must be preserved to keep alive any potentially aliasing
// references. fix_lifetime can only be removed by proving that its
// operand is both a unique and a dead reference, but this makes more
// sense in DeadObjectElimination.
case SILInstructionKind::FixLifetimeInst: {
// If the operand is a trivial scalar value, then it has no aliases or
// side-effects. Consider handling this as an instruction
// canonicalization instead.
SILValue Op = I.getOperand(0);
if (!Op->getType().isAddress() && Op->getType().isTrivial(*F)) {
addReverseDependency(Op, &I);
} else {
markInstructionLive(&I);
}
break;
}
case SILInstructionKind::EndAccessInst: {
// An end_access is live only if it's begin_access is also live.
auto *beginAccess = cast<EndAccessInst>(&I)->getBeginAccess();
addReverseDependency(beginAccess, &I);
break;
}
case SILInstructionKind::DestroyValueInst: {
auto phi = PhiValue(I.getOperand(0));
// Disable DCE of phis which are lexical or may have a pointer escape.
if (phi && (phi->isLexical() || findPointerEscape(phi))) {
markInstructionLive(&I);
}
// The instruction is live only if it's operand value is also live
addReverseDependency(I.getOperand(0), &I);
break;
}
case SILInstructionKind::EndBorrowInst: {
auto phi = PhiValue(lookThroughBorrowedFromDef(I.getOperand(0)));
// If there is a pointer escape or phi is lexical, disable DCE.
if (phi && (findPointerEscape(phi) || phi->isLexical())) {
markInstructionLive(&I);
}
// The instruction is live only if it's operand value is also live
addReverseDependency(I.getOperand(0), &I);
break;
}
case SILInstructionKind::BorrowedFromInst: {
addReverseDependency(I.getOperand(0), &I);
break;
}
case SILInstructionKind::EndLifetimeInst: {
if (I.getOperand(0)->getType().isAddress()) {
// DCE cannot reason about values in memory.
markInstructionLive(&I);
break;
}
// The instruction is live only if it's operand value is also live
addReverseDependency(I.getOperand(0), &I);
break;
}
case SILInstructionKind::BeginBorrowInst: {
auto *borrowInst = cast<BeginBorrowInst>(&I);
processBorrow(BorrowedValue(borrowInst));
break;
}
case SILInstructionKind::LoadBorrowInst: {
auto *loadBorrowInst = cast<LoadBorrowInst>(&I);
processBorrow(BorrowedValue(loadBorrowInst));
break;
}
default:
if (seemsUseful(&I))
markInstructionLive(&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 if needed. See DCE::ReverseDependencies.
void DCE::addReverseDependency(SILValue from, SILInstruction *to) {
LLVM_DEBUG(llvm::dbgs() << "Adding reverse dependency from " << from << " to "
<< *to);
ReverseDependencies[from].insert(to);
}
void DCE::findGuaranteedPhiDependencies(BorrowedValue borrow) {
assert(borrow.kind == BorrowedValueKind::BeginBorrow ||
borrow.kind == BorrowedValueKind::LoadBorrow);
LLVM_DEBUG(llvm::dbgs() << "Finding @guaranteed phi dependencies of "
<< borrow << "\n");
auto visitDependentPhiBaseValuePair = [&](SILPhiArgument *phiArg,
SILValue baseValue) {
guaranteedPhiDependencies[phiArg].insert(baseValue);
};
// Find all dependencies starting from \p borrowInst and populate
// them in guaranteedPhiDependencies
if (borrow.kind == BorrowedValueKind::BeginBorrow) {
visitExtendedReborrowPhiBaseValuePairs(cast<BeginBorrowInst>(borrow.value),
visitDependentPhiBaseValuePair);
}
visitExtendedGuaranteedForwardingPhiBaseValuePairs(
borrow, visitDependentPhiBaseValuePair);
}
// 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.
markInstructionLive(Term);
switch (Term->getTermKind()) {
case TermKind::ReturnInst:
case TermKind::ThrowInst:
case TermKind::ThrowAddrInst:
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:
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::AwaitAsyncContinuationInst:
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))
markInstructionLive(DU->getUser());
// Mark all reverse dependencies on the Arg live
for (auto *depInst : ReverseDependencies.lookup(Arg)) {
markInstructionLive(depInst);
}
if (auto *phi = dyn_cast<SILPhiArgument>(Arg)) {
for (auto depVal : guaranteedPhiDependencies.lookup(phi)) {
markValueLive(depVal);
}
}
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) {
markControllingTerminatorsLive(I->getParent());
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))
markInstructionLive(DU->getUser());
// Handle all other reverse-dependency instructions, like cond_fail,
// fix_lifetime, destroy_value, etc. Only if the definition is alive, the
// user itself is alive.
for (auto res : I->getResults()) {
for (auto *depInst : ReverseDependencies.lookup(res)) {
markInstructionLive(depInst);
}
}
return;
}
switch (cast<TermInst>(I)->getTermKind()) {
case TermKind::BranchInst:
case TermKind::UnreachableInst:
case TermKind::UnwindInst:
case TermKind::ThrowAddrInst:
return;
case TermKind::ReturnInst:
case TermKind::ThrowInst:
case TermKind::CondBranchInst:
case TermKind::SwitchEnumInst:
case TermKind::SwitchEnumAddrInst:
case TermKind::DynamicMethodBranchInst:
markValueLive(I->getOperand(0));
return;
case TermKind::AwaitAsyncContinuationInst:
case TermKind::CheckedCastBranchInst:
case TermKind::CheckedCastAddrBranchInst:
case TermKind::TryApplyInst:
case TermKind::SwitchValueInst:
case TermKind::YieldInst:
for (auto &O : I->getAllOperands())
markValueLive(O.get());
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 &&
// In case the PostDomNode's block is null, it means it's not contained
// in LiveBlocks.
(!PostDomNode->getBlock() ||
!LiveBlocks.contains(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(!LiveArguments.contains(*A) && "Unexpected live block argument!");
Args.push_back(SILUndef::get(*A));
}
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;
}
void DCE::endLifetimeOfLiveValue(Operand *op, SILInstruction *insertPt) {
auto value = op->get();
if (SILInstruction *inst = value->getDefiningInstruction()) {
if (!LiveInstructions.contains(inst))
return;
} else if (auto *arg = dyn_cast<SILArgument>(value)) {
if (!LiveArguments.contains(arg))
return;
}
assert(op->isLifetimeEnding());
// If DCE is going to delete the block in which we have to insert a
// compensating lifetime end, let complete lifetimes utility handle it.
if (!LiveBlocks.contains(insertPt->getParent())) {
valuesToComplete.insert(lookThroughBorrowedFromDef(value));
return;
}
SILBuilderWithScope builder(insertPt);
if (value->getOwnershipKind() == OwnershipKind::Owned) {
auto *destroy = builder.createDestroyValue(
RegularLocation::getAutoGeneratedLocation(), value);
markInstructionLive(destroy);
}
if (value->getOwnershipKind() == OwnershipKind::Guaranteed) {
auto *endBorrow = builder.createEndBorrow(
RegularLocation::getAutoGeneratedLocation(), value);
markInstructionLive(endBorrow);
}
}
// Remove the instructions that are not potentially useful.
bool DCE::removeDead() {
bool Changed = false;
for (auto &BB : *F) {
for (unsigned i = 0; i < BB.getArguments().size();) {
auto *arg = BB.getArgument(i);
if (LiveArguments.contains(arg)) {
i++;
continue;
}
LLVM_DEBUG(llvm::dbgs() << "Removing dead argument:\n");
LLVM_DEBUG(arg->dump());
arg->replaceAllUsesWithUndef();
if (!F->hasOwnership() || arg->getOwnershipKind() == OwnershipKind::None) {
i++;
Changed = true;
BranchesChanged = true;
continue;
}
if (!arg->isPhi()) {
// We cannot delete a non phi. If it was @owned, insert a
// destroy_value, because its consuming user has already been marked
// dead and will be deleted.
// We do not have to end lifetime of a @guaranteed non phi arg.
if (arg->getOwnershipKind() == OwnershipKind::Owned) {
auto loc = RegularLocation::getAutoGeneratedLocation();
// insertPt is non-null because Undef is non-owned.
auto insertPt = getInsertAfterPoint(arg).value();
SILBuilderWithScope builder(insertPt);
auto *destroy = builder.createDestroyValue(loc, arg);
LiveInstructions.insert(destroy);
}
i++;
Changed = true;
BranchesChanged = true;
continue;
}
auto *phiArg = cast<SILPhiArgument>(arg);
// In OSSA, we have to delete a dead phi argument and insert destroy or
// end_borrow at its predecessors if the incoming values are live.
// This is not necessary in non-OSSA, and will infact be incorrect.
// Because, passing a value as a phi argument does not imply end of
// lifetime in non-OSSA.
for (auto *pred : BB.getPredecessorBlocks()) {
auto *predTerm = pred->getTerminator();
SILInstruction *insertPt = predTerm;
if (phiArg->isReborrow()) {
// If the phiArg is dead and had reborrow dependencies, its baseValue
// may also have been dead and a destroy_value of its baseValue may
// have been inserted before the pred's terminator. Make sure to
// adjust the insertPt before any destroy_value.
//
// FIXME: This code currently can reorder destroys, e.g., when the
// block already contains a destroy_value just before the
// terminator. Fix this by making note of the added
// destroy_value insts and only moving the insertion point
// before those that are newly added.
for (SILInstruction &predInst : llvm::reverse(*pred)) {
if (&predInst == predTerm)
continue;
if (!isa<DestroyValueInst>(&predInst)) {
break;
}
insertPt = &predInst;
}
}
auto *predOp = phiArg->getIncomingPhiOperand(pred);
if (predOp->isLifetimeEnding()) {
endLifetimeOfLiveValue(predOp, insertPt);
}
}
erasePhiArgument(
&BB, i, /*cleanupDeadPhiOps=*/true,
InstModCallbacks()
.onCreateNewInst([&](auto *inst) { markInstructionLive(inst); })
.onDelete([&](auto *inst) {
for (auto result : inst->getResults()) {
result = lookThroughBorrowedFromDef(result);
if (valuesToComplete.count(result)) {
valuesToComplete.erase(result);
}
}
inst->replaceAllUsesOfAllResultsWithUndef();
if (isa<ApplyInst>(inst))
CallsChanged = true;
++NumDeletedInsts;
inst->eraseFromParent();
}));
Changed = true;
BranchesChanged = true;
}
for (auto I = BB.begin(), E = BB.end(); I != E; ) {
auto *Inst = &*I;
++I;
if (LiveInstructions.contains(Inst) || isa<BranchInst>(Inst))
continue;
// We want to replace dead terminators with unconditional branches to
// the nearest post-dominator that has useful instructions.
if (auto *termInst = dyn_cast<TermInst>(Inst)) {
SILBasicBlock *postDom =
nearestUsefulPostDominator(termInst->getParent());
if (!postDom)
continue;
for (auto &op : termInst->getAllOperands()) {
if (op.isLifetimeEnding()) {
endLifetimeOfLiveValue(&op, termInst);
}
}
LLVM_DEBUG(llvm::dbgs() << "Replacing branch: ");
LLVM_DEBUG(termInst->dump());
LLVM_DEBUG(llvm::dbgs()
<< "with jump to: BB" << postDom->getDebugID() << "\n");
replaceBranchWithJump(termInst, postDom);
++NumDeletedInsts;
termInst->eraseFromParent();
BranchesChanged = true;
Changed = true;
continue;
}
++NumDeletedInsts;
LLVM_DEBUG(llvm::dbgs() << "Removing dead instruction:\n");
LLVM_DEBUG(Inst->dump());
if (F->hasOwnership()) {
for (auto &Op : Inst->getAllOperands()) {
if (Op.isLifetimeEnding()) {
endLifetimeOfLiveValue(&Op, Inst);
}
}
}
for (auto result : Inst->getResults()) {
result = lookThroughBorrowedFromDef(result);
if (valuesToComplete.count(result)) {
valuesToComplete.erase(result);
}
}
Inst->replaceAllUsesOfAllResultsWithUndef();
if (isa<ApplyInst>(Inst))
CallsChanged = true;
Inst->eraseFromParent();
Changed = true;
}
}
OSSACompleteLifetime completion(F, DT, *deadEndBlocks);
for (auto value : valuesToComplete) {
if (!value.has_value())
continue;
completion.completeOSSALifetime(*value,
OSSACompleteLifetime::Boundary::Liveness);
}
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() {
computeLevelNumbers(PDT->getRootNode());
if (hasInfiniteLoops())
return false;
computePredecessorDependence();
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.
void DCE::computeLevelNumbers(PostDomTreeNode *root) {
llvm::SmallVector<std::pair<PostDomTreeNode *, unsigned>, 32> workList;
workList.push_back({root, 0});
while (!workList.empty()) {
auto entry = workList.pop_back_val();
PostDomTreeNode *node = entry.first;
unsigned level = entry.second;
insertControllingInfo(node->getBlock(), level);
for (PostDomTreeNode *child : *node) {
workList.push_back({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() {
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() {
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);
}
}
}
// Assign the minimum post-dominator tree level to each node in the tree.
void DCE::computeMinPredecessorLevels(PostDomTreeNode *root) {
llvm::SmallVector<PostDomTreeNode *, 32> postDomOrder;
postDomOrder.reserve(ControllingInfoMap.size());
postDomOrder.push_back(root);
for (unsigned idx = 0; idx < postDomOrder.size(); ++idx) {
PostDomTreeNode *node = postDomOrder[idx];
for (PostDomTreeNode *child : *node) {
postDomOrder.push_back(child);
}
}
for (PostDomTreeNode *node : llvm::reverse(postDomOrder)) {
SILBasicBlock *block = node->getBlock();
assert(ControllingInfoMap.find(block) != ControllingInfoMap.end() &&
"Expected to have map entry for node!");
ControllingInfo &nodeInfo = ControllingInfoMap[block];
for (auto &pred : nodeInfo.ControllingPreds) {
nodeInfo.MinTreePredLevel = std::min(nodeInfo.MinTreePredLevel, pred.second);
}
if (PostDomTreeNode *parentNode = node->getIDom()) {
ControllingInfo &parentInfo = ControllingInfoMap[parentNode->getBlock()];
parentInfo.MinTreePredLevel = std::min(parentInfo.MinTreePredLevel, nodeInfo.MinTreePredLevel);
}
}
}
void DCE::collectControllingBlocksInTree(ControllingInfo &QueryInfo,
PostDomTreeNode *root,
llvm::SmallPtrSetImpl<SILBasicBlock *> &Controlling) {
llvm::SmallVector<PostDomTreeNode *, 32> workList;
workList.push_back(root);
while (!workList.empty()) {
PostDomTreeNode *node = workList.pop_back_val();
SILBasicBlock *block = node->getBlock();
assert(ControllingInfoMap.find(block) != ControllingInfoMap.end() &&
"Expected to have map entry for node!");
auto &nodeInfo = ControllingInfoMap[block];
if (nodeInfo.MinTreePredLevel > QueryInfo.Level)
continue;
for (auto &PredInfo : nodeInfo.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 (PostDomTreeNode *child : *node) {
workList.push_back(child);
}
}
}
// 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.contains(Block))
return;
LiveBlocks.insert(Block);
llvm::SmallPtrSet<SILBasicBlock *, 4> ControllingBlocks;
collectControllingBlocks(Block, ControllingBlocks);
for (auto BB : ControllingBlocks)
markInstructionLive(BB->getTerminator());
}
class DCEPass : public SILFunctionTransform {
public:
/// The entry point to the transformation.
void run() override {
SILFunction *F = getFunction();
LLVM_DEBUG(llvm::dbgs() << "*** DCE on function: " << F->getName()
<< " ***\n");
auto *PDA = PM->getAnalysis<PostDominanceAnalysis>();
PostDominanceInfo *PDT = PDA->get(F);
auto *DA = PM->getAnalysis<DominanceAnalysis>();
auto *DEA = getAnalysis<DeadEndBlocksAnalysis>();
// 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;
DCE dce(F, PDT, DA->get(F), DEA->get(F));
if (dce.run()) {
using InvalidationKind = SILAnalysis::InvalidationKind;
unsigned Inv = InvalidationKind::Instructions;
if (dce.mustInvalidateCalls())
Inv |= (unsigned)InvalidationKind::Calls;
if (dce.mustInvalidateBranches()) {
removeUnreachableBlocks(*F);
Inv |= (unsigned)InvalidationKind::Branches;
}
invalidateAnalysis(SILAnalysis::InvalidationKind(Inv));
}
}
};
} // end anonymous namespace
SILTransform *swift::createDCE() {
return new DCEPass();
}
Reference in New Issue View Git Blame Copy Permalink