mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
00fa738209
In C++, we always expected to invoke the dtor for moved-from objects. This is not the case for swift. Fortunately, @inCxx calling convention is already expressing that the caller supposed to destroy the object. This fixes the missing dtor calls when calling C++ functions taking rvalue references. Fixes #77894. rdar://140786022
1319 lines
46 KiB
C++
1319 lines
46 KiB
C++
//===--- CopyForwarding.cpp - Forward local copies from caller to callee --===//
|
|
//
|
|
// 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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
//
|
|
// Eliminate local copies of either address-only or reference types.
|
|
//
|
|
// This opportunity frequently results from a calling convention that transfers
|
|
// object ownership from caller to callee. In this convention, the caller
|
|
// creates a local copy before passing it to the callee. If the original object
|
|
// is immediately destroyed after passing off the copy, then the copy was
|
|
// unnecessary. Removing the useless copy can be thought of as forwarding the
|
|
// original object directly to the call argument in place of the copy. Hence
|
|
// "copy forwarding".
|
|
//
|
|
// There are two classifications of types that copy forwarding applies to:
|
|
// address-only types and references.
|
|
//
|
|
// Useless copies of address-only types look like this:
|
|
//
|
|
// %copy = alloc_stack $T
|
|
// copy_addr %arg to [init] %copy : $*T
|
|
// %ret = apply %callee<T>(%copy) : $@convention(thin) <τ_0_0> (@in τ_0_0) -> ()
|
|
// dealloc_stack %copy : $*T
|
|
// destroy_addr %arg : $*T
|
|
//
|
|
// Eliminating the address-only copies eliminates a very expensive call to
|
|
// getGenericMetadata.
|
|
//
|
|
// Useless copies of references look like this:
|
|
//
|
|
// strong_retain %arg : $A
|
|
// %ret = apply %callee(%arg) : $@convention(thin) (@owned A) -> ()
|
|
// strong_release %arg : $A
|
|
//
|
|
// Eliminating the reference copies, avoids artificially bumping the refcount
|
|
// which could save a copy of all elements in a COW container.
|
|
//
|
|
// The actual analysis and optimization do not depend on the copy being linked
|
|
// to call arguments. Any obviously useless copy will be eliminated.
|
|
//
|
|
// TODO: Currently we only handle the address-only case, not the retain/release
|
|
// case.
|
|
//
|
|
// TODO: We should run this at -Onone even though it's not diagnostic.
|
|
//
|
|
// TODO: Currently we only handle cases in which one side of the copy is block
|
|
// local. Either:
|
|
// (1) Forward propagate: copy src -> dest; deinit(dest)
|
|
// (2) Backward propagate: init(src); copy src -> dest
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#define DEBUG_TYPE "copy-forwarding"
|
|
#include "swift/Basic/Assertions.h"
|
|
#include "swift/SIL/DebugUtils.h"
|
|
#include "swift/SIL/SILArgument.h"
|
|
#include "swift/SIL/SILBuilder.h"
|
|
#include "swift/SIL/SILVisitor.h"
|
|
#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
|
|
#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
|
|
#include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
|
|
#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
|
|
#include "swift/SILOptimizer/PassManager/Passes.h"
|
|
#include "swift/SILOptimizer/PassManager/Transforms.h"
|
|
#include "swift/SILOptimizer/Utils/CFGOptUtils.h"
|
|
#include "swift/SILOptimizer/Utils/DebugOptUtils.h"
|
|
#include "swift/SILOptimizer/Utils/ValueLifetime.h"
|
|
#include "llvm/ADT/SetVector.h"
|
|
#include "llvm/ADT/Statistic.h"
|
|
#include "llvm/Support/CommandLine.h"
|
|
#include "llvm/Support/Debug.h"
|
|
|
|
STATISTIC(NumCopyForward, "Number of copies removed via forward propagation");
|
|
STATISTIC(NumCopyBackward,
|
|
"Number of copies removed via backward propagation");
|
|
STATISTIC(NumDeadTemp, "Number of copies removed from unused temporaries");
|
|
|
|
using namespace swift;
|
|
|
|
// Temporary debugging flag until this pass is better tested.
|
|
static llvm::cl::opt<bool> EnableCopyForwarding("enable-copyforwarding",
|
|
llvm::cl::init(true));
|
|
|
|
/// \return true if the given copy source value can only be accessed via the
|
|
/// given def (this def uniquely identifies the object).
|
|
///
|
|
/// (1) An "in" argument.
|
|
/// (inouts are also nonaliased, but won't be destroyed in scope)
|
|
///
|
|
/// (2) A local alloc_stack variable.
|
|
static bool isIdentifiedSourceValue(SILValue Def) {
|
|
if (auto *Arg = dyn_cast<SILFunctionArgument>(Def)) {
|
|
// Check that the argument is passed as an in type. This means there are
|
|
// no aliases accessible within this function scope.
|
|
SILArgumentConvention Conv = Arg->getArgumentConvention();
|
|
switch (Conv) {
|
|
case SILArgumentConvention::Indirect_In:
|
|
case SILArgumentConvention::Indirect_In_Guaranteed:
|
|
return true;
|
|
default:
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping Def: Not an @in argument!\n");
|
|
return false;
|
|
}
|
|
}
|
|
|
|
if (isa<AllocStackInst>(Def))
|
|
return true;
|
|
|
|
return false;
|
|
}
|
|
|
|
/// \return true if the given copy dest value can only be accessed via the given
|
|
/// def (this def uniquely identifies the object).
|
|
///
|
|
/// (1) An "out" or inout argument.
|
|
///
|
|
/// (2) A local alloc_stack variable.
|
|
static bool isIdentifiedDestValue(SILValue Def) {
|
|
if (auto *Arg = dyn_cast<SILFunctionArgument>(Def)) {
|
|
// Check that the argument is passed as an out type. This means there are
|
|
// no aliases accessible within this function scope.
|
|
SILArgumentConvention Conv = Arg->getArgumentConvention();
|
|
switch (Conv) {
|
|
case SILArgumentConvention::Indirect_Inout:
|
|
case SILArgumentConvention::Indirect_Out:
|
|
return true;
|
|
default:
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping Def: Not an @in argument!\n");
|
|
return false;
|
|
}
|
|
}
|
|
|
|
if (isa<AllocStackInst>(Def))
|
|
return true;
|
|
|
|
return false;
|
|
}
|
|
|
|
/// Return the parameter convention used by Apply to pass an argument
|
|
/// indirectly via Address.
|
|
///
|
|
/// Set Oper to the Apply operand that passes Address.
|
|
static SILArgumentConvention getAddressArgConvention(ApplyInst *Apply,
|
|
SILValue Address,
|
|
Operand *&Oper) {
|
|
Oper = nullptr;
|
|
auto Args = Apply->getArgumentOperands();
|
|
for (auto ArgIdx : indices(Args)) {
|
|
if (Args[ArgIdx].get() != Address)
|
|
continue;
|
|
|
|
assert(!Oper && "Address can only be passed once as an indirection.");
|
|
Oper = &Args[ArgIdx];
|
|
#ifdef NDEBUG
|
|
break;
|
|
#endif
|
|
}
|
|
assert(Oper && "Address value not passed as an argument to this call.");
|
|
return ApplySite(Apply).getArgumentConvention(*Oper);
|
|
}
|
|
|
|
/// If the given instruction is a store, return the stored value.
|
|
static SILValue getStoredValue(SILInstruction *I) {
|
|
switch (I->getKind()) {
|
|
#define NEVER_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...) \
|
|
case SILInstructionKind::Store##Name##Inst:
|
|
#include "swift/AST/ReferenceStorage.def"
|
|
case SILInstructionKind::StoreInst:
|
|
case SILInstructionKind::StoreBorrowInst:
|
|
return I->getOperand(0);
|
|
default:
|
|
return SILValue();
|
|
}
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// Forward and backward copy propagation
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
// Visitor for visitAddressUsers.
|
|
namespace {
|
|
class AddressUserVisitor {
|
|
public:
|
|
virtual ~AddressUserVisitor() {}
|
|
|
|
virtual bool visitNormalUse(SILInstruction *user) = 0;
|
|
virtual bool visitTake(CopyAddrInst *copy) = 0;
|
|
virtual bool visitDestroy(DestroyAddrInst *destroy) = 0;
|
|
virtual bool visitDebugValue(DebugValueInst *debugValue) = 0;
|
|
};
|
|
} // namespace
|
|
|
|
/// Gather all instructions that use the given `address`
|
|
///
|
|
/// "Normal" uses are a allowlisted set of uses that guarantees the address is
|
|
/// only used as if it refers to a single value and all uses are accounted for
|
|
/// (no address projections).
|
|
///
|
|
/// Takes are "copy_addr [take]"
|
|
///
|
|
/// Destroys are "destroy_addr"
|
|
/// -
|
|
///
|
|
/// If we are unable to find all uses, for example, because we don't look
|
|
/// through struct_element_addr, then return false.
|
|
///
|
|
/// The collected use points will be consulted during forward and backward
|
|
/// copy propagation.
|
|
///
|
|
/// \param ignoredUser will be ignored if it is is non-null.
|
|
static bool visitAddressUsers(SILValue address, SILInstruction *ignoredUser,
|
|
AddressUserVisitor &visitor) {
|
|
for (Operand *use : address->getUses()) {
|
|
SILInstruction *UserInst = use->getUser();
|
|
if (UserInst == ignoredUser)
|
|
continue;
|
|
|
|
if (auto *Apply = dyn_cast<ApplyInst>(UserInst)) {
|
|
/// A call to materializeForSet exposes an address within the parent
|
|
/// object. However, we can rely on a subsequent mark_dependent
|
|
/// instruction to take that object as an operand, causing it to escape
|
|
/// for the purpose of this analysis.
|
|
assert(Apply->getSubstCalleeConv()
|
|
.getSILArgumentConvention(use->getOperandNumber()
|
|
- Apply->getArgumentOperandNumber())
|
|
.isIndirectConvention()
|
|
&& "copy_addr location should be passed indirect");
|
|
if (!visitor.visitNormalUse(UserInst))
|
|
return false;
|
|
|
|
continue;
|
|
}
|
|
if (auto *CopyInst = dyn_cast<CopyAddrInst>(UserInst)) {
|
|
if (CopyInst->getSrc() == use->get() && CopyInst->isTakeOfSrc()) {
|
|
if (!visitor.visitTake(CopyInst))
|
|
return false;
|
|
} else {
|
|
if (!visitor.visitNormalUse(CopyInst))
|
|
return false;
|
|
}
|
|
continue;
|
|
}
|
|
if (auto *Destroy = dyn_cast<DestroyAddrInst>(UserInst)) {
|
|
if (!visitor.visitDestroy(Destroy))
|
|
return false;
|
|
|
|
continue;
|
|
}
|
|
switch (UserInst->getKind()) {
|
|
case SILInstructionKind::LoadInst:
|
|
if (!visitor.visitNormalUse(UserInst))
|
|
return false;
|
|
|
|
break;
|
|
case SILInstructionKind::ExistentialMetatypeInst:
|
|
case SILInstructionKind::InjectEnumAddrInst:
|
|
case SILInstructionKind::StoreInst:
|
|
if (!visitor.visitNormalUse(UserInst))
|
|
return false;
|
|
break;
|
|
case SILInstructionKind::DebugValueInst:
|
|
if (auto *DV = DebugValueInst::hasAddrVal(UserInst)) {
|
|
if (!visitor.visitDebugValue(DV))
|
|
return false;
|
|
} else {
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping copy: use exposes def"
|
|
<< *UserInst);
|
|
return false;
|
|
}
|
|
break;
|
|
case SILInstructionKind::DeallocStackInst:
|
|
break;
|
|
default:
|
|
// Most likely one of:
|
|
// init_enum_data_addr
|
|
// open_existential_addr
|
|
// partial_apply
|
|
// struct_element_addr
|
|
// unchecked_take_enum_data_addr
|
|
//
|
|
// TODO: Peek through struct element users like COWArrayOpts.
|
|
//
|
|
// TODO: Attempt to analyze partial applies or run closure propagation
|
|
// first.
|
|
//
|
|
// TODO: assert that this list is consistent with
|
|
// isTransitiveEscapeInst().
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping copy: use exposes def"
|
|
<< *UserInst);
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
namespace {
|
|
/// Analyze an instruction that operates on the Address of a forward propagated
|
|
/// value.
|
|
///
|
|
/// Set Oper to the operand that may be safely replaced by an address
|
|
/// pointing to an equivalent value. If UserInst cannot be analyzed, Oper is set
|
|
/// to nullptr.
|
|
///
|
|
/// Return true if the instruction destroys the value at Address.
|
|
///
|
|
/// This checks for the following cases of deinit:
|
|
/// - 'in' argument
|
|
/// - copy_addr [take] src
|
|
/// - copy_addr [!init] dest
|
|
/// - destroy_addr
|
|
/// - unchecked_take_enum_data_addr
|
|
///
|
|
/// The copy_addr [!init] case is special because the operand cannot simply be
|
|
/// replaced with a new address without causing that location to be
|
|
/// reinitialized (after being deinitialized). The caller must check for and
|
|
/// handle this case.
|
|
///
|
|
/// This returns false and sets Oper to a valid operand if the instruction is a
|
|
/// projection of the value at the given address. The assumption is that we
|
|
/// cannot deinitialize memory via projections.
|
|
///
|
|
/// This returns true with Oper == nullptr for trivial stores (without a proper
|
|
/// deinit).
|
|
class AnalyzeForwardUse
|
|
: public SILInstructionVisitor<AnalyzeForwardUse, bool> {
|
|
public:
|
|
SILValue Address;
|
|
Operand *Oper;
|
|
|
|
AnalyzeForwardUse(SILValue Address): Address(Address), Oper(nullptr) {}
|
|
|
|
bool visitApplyInst(ApplyInst *Apply) {
|
|
switch (getAddressArgConvention(Apply, Address, Oper)) {
|
|
case SILArgumentConvention::Indirect_In:
|
|
return true;
|
|
case SILArgumentConvention::Indirect_In_Guaranteed:
|
|
case SILArgumentConvention::Indirect_In_CXX:
|
|
case SILArgumentConvention::Indirect_Inout:
|
|
case SILArgumentConvention::Indirect_InoutAliasable:
|
|
return false;
|
|
default:
|
|
llvm_unreachable("unexpected calling convention for copy_addr user");
|
|
}
|
|
}
|
|
bool visitCopyAddrInst(CopyAddrInst *CopyInst) {
|
|
if (CopyInst->getSrc() == Address) {
|
|
Oper = &CopyInst->getAllOperands()[CopyAddrInst::Src];
|
|
return CopyInst->isTakeOfSrc();
|
|
}
|
|
assert(!CopyInst->isInitializationOfDest() && "illegal reinitialization");
|
|
Oper = &CopyInst->getAllOperands()[CopyAddrInst::Dest];
|
|
return true;
|
|
}
|
|
bool visitStoreInst(StoreInst *Store) {
|
|
// Trivial values may be stored prior to the next deinit. A store is an
|
|
// implicit "deinit" with no operand to replace.
|
|
assert(Store->getOperand(0)->getType().isTrivial(*Store->getFunction()));
|
|
return true;
|
|
}
|
|
bool visitDestroyAddrInst(DestroyAddrInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return true;
|
|
}
|
|
bool visitUncheckedTakeEnumDataAddrInst(
|
|
UncheckedTakeEnumDataAddrInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return true;
|
|
}
|
|
bool visitExistentialMetatypeInst(ExistentialMetatypeInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
bool visitLoadInst(LoadInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
bool visitOpenExistentialAddrInst(OpenExistentialAddrInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
bool visitStructElementAddrInst(StructElementAddrInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
bool visitDebugValueInst(DebugValueInst *UserInst) {
|
|
if (UserInst->hasAddrVal()) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
bool visitInitEnumDataAddrInst(InitEnumDataAddrInst *UserInst) {
|
|
llvm_unreachable("illegal reinitialization");
|
|
}
|
|
bool visitInjectEnumAddrInst(InjectEnumAddrInst *UserInst) {
|
|
llvm_unreachable("illegal reinitialization");
|
|
}
|
|
bool visitSILInstruction(SILInstruction *UserInst) {
|
|
return false;
|
|
}
|
|
};
|
|
|
|
/// Analyze an instruction that operates on the Address of a backward propagated
|
|
/// value.
|
|
///
|
|
/// Set Oper to the operand that my be safely replaced by an address
|
|
/// pointing to an equivalent value. If UserInst cannot be analyzed, Oper is set
|
|
/// to nullptr.
|
|
///
|
|
/// Return true if the instruction initializes the value at Address.
|
|
///
|
|
/// We currently check for the following cases of init:
|
|
/// - 'out' argument
|
|
/// - copy_addr [init] dest
|
|
/// - copy_addr [!init] dest
|
|
/// - store
|
|
///
|
|
/// The copy_addr [!init] case is special because the operand cannot simply be
|
|
/// replaced with a new address without causing that location to be
|
|
/// deinitialized (before being initialized). The caller must check for and
|
|
/// handle this case.
|
|
///
|
|
/// This returns false and sets Oper to nullptr for projections of the value at
|
|
/// the given address. For example, init_enum_data_addr and struct_element_addr
|
|
/// may be part of a decoupled initialization sequence.
|
|
class AnalyzeBackwardUse
|
|
: public SILInstructionVisitor<AnalyzeBackwardUse, bool> {
|
|
public:
|
|
SILValue Address;
|
|
Operand *Oper;
|
|
|
|
AnalyzeBackwardUse(SILValue Address): Address(Address), Oper(nullptr) {}
|
|
|
|
bool visitApplyInst(ApplyInst *Apply) {
|
|
switch (getAddressArgConvention(Apply, Address, Oper)) {
|
|
case SILArgumentConvention::Indirect_Out:
|
|
return true;
|
|
case SILArgumentConvention::Indirect_Inout:
|
|
case SILArgumentConvention::Indirect_InoutAliasable:
|
|
case SILArgumentConvention::Indirect_In_Guaranteed:
|
|
return false;
|
|
case SILArgumentConvention::Indirect_In_CXX:
|
|
case SILArgumentConvention::Indirect_In:
|
|
llvm_unreachable("copy_addr src destroyed without reinitialization");
|
|
default:
|
|
llvm_unreachable("unexpected calling convention for copy_addr user");
|
|
}
|
|
}
|
|
bool visitCopyAddrInst(CopyAddrInst *CopyInst) {
|
|
if (CopyInst->getDest() == Address) {
|
|
Oper = &CopyInst->getAllOperands()[CopyAddrInst::Dest];
|
|
return true;
|
|
}
|
|
Oper = &CopyInst->getAllOperands()[CopyAddrInst::Src];
|
|
assert(!CopyInst->isTakeOfSrc() && "illegal deinitialization");
|
|
return false;
|
|
}
|
|
bool visitStoreInst(StoreInst *Store) {
|
|
Oper = &Store->getAllOperands()[StoreInst::Dest];
|
|
assert(Oper->get() == Address && "illegal store of an address");
|
|
return true;
|
|
}
|
|
bool visitExistentialMetatypeInst(ExistentialMetatypeInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
bool visitInjectEnumAddrInst(InjectEnumAddrInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
bool visitLoadInst(LoadInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
bool visitOpenExistentialAddrInst(OpenExistentialAddrInst *UserInst) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
bool visitDestroyAddrInst(DestroyAddrInst *UserInst) {
|
|
llvm_unreachable("illegal deinitialization");
|
|
}
|
|
bool visitUncheckedTakeEnumDataAddrInst(
|
|
UncheckedTakeEnumDataAddrInst *UserInst) {
|
|
llvm_unreachable("illegal deinitialization");
|
|
}
|
|
bool visitUncheckedRefCastAddrInst(
|
|
UncheckedRefCastAddrInst *UserInst) {
|
|
if (UserInst->getDest() == Address) {
|
|
Oper = &UserInst->getAllOperands()[UncheckedRefCastAddrInst::Dest];
|
|
}
|
|
return true;
|
|
}
|
|
bool visitDebugValueInst(DebugValueInst *UserInst) {
|
|
if (UserInst->hasAddrVal()) {
|
|
Oper = &UserInst->getOperandRef();
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
bool visitSILInstruction(SILInstruction *UserInst) {
|
|
return false;
|
|
}
|
|
};
|
|
|
|
class CopyForwarding {
|
|
// Per-function state.
|
|
PostOrderAnalysis *PostOrder;
|
|
DominanceAnalysis *DomAnalysis;
|
|
RCIdentityAnalysis *RCIAnalysis;
|
|
bool HasChanged;
|
|
bool HasChangedCFG;
|
|
|
|
// --- Per copied-def state ---
|
|
|
|
// Transient state for the current Def valid during forwardCopiesOf.
|
|
SILValue CurrentDef;
|
|
|
|
// Is the addressed defined by CurrentDef ever loaded from?
|
|
// This indicates that lifetime of any transitively referenced objects lives
|
|
// beyond the value's immediate uses.
|
|
bool IsSrcLoadedFrom;
|
|
|
|
// Does the address defined by CurrentDef have unrecognized uses of a
|
|
// nontrivial value stored at its address?
|
|
bool HasUnknownStoredValue;
|
|
|
|
bool HasForwardedToCopy;
|
|
SmallPtrSet<SILInstruction*, 16> SrcUserInsts;
|
|
SmallPtrSet<SILInstruction*, 4> SrcDebugValueInsts;
|
|
SmallVector<CopyAddrInst*, 4> TakePoints;
|
|
SmallVector<DestroyAddrInst*, 4> DestroyPoints;
|
|
SmallPtrSet<SILBasicBlock*, 32> DeadInBlocks;
|
|
|
|
// --- Per copy_addr state ---
|
|
CopyAddrInst *CurrentCopy = nullptr;
|
|
|
|
class CopySrcUserVisitor : public AddressUserVisitor {
|
|
CopyForwarding &CPF;
|
|
public:
|
|
CopySrcUserVisitor(CopyForwarding &CPF) : CPF(CPF) {}
|
|
|
|
virtual bool visitNormalUse(SILInstruction *user) override {
|
|
if (isa<LoadInst>(user))
|
|
CPF.IsSrcLoadedFrom = true;
|
|
|
|
if (SILValue storedValue = getStoredValue(user)) {
|
|
if (!CPF.markStoredValueUsers(storedValue))
|
|
CPF.HasUnknownStoredValue = true;
|
|
}
|
|
|
|
// Bail on multiple uses in the same instruction to avoid complexity.
|
|
return CPF.SrcUserInsts.insert(user).second;
|
|
}
|
|
virtual bool visitTake(CopyAddrInst *take) override {
|
|
if (take->getSrc() == take->getDest())
|
|
return false;
|
|
|
|
CPF.TakePoints.push_back(take);
|
|
return true;
|
|
}
|
|
virtual bool visitDestroy(DestroyAddrInst *destroy) override {
|
|
CPF.DestroyPoints.push_back(destroy);
|
|
return true;
|
|
}
|
|
virtual bool visitDebugValue(DebugValueInst *debugValue) override {
|
|
return CPF.SrcDebugValueInsts.insert(debugValue).second;
|
|
}
|
|
};
|
|
|
|
public:
|
|
CopyForwarding(PostOrderAnalysis *PO, DominanceAnalysis *DA,
|
|
RCIdentityAnalysis *RCIAnalysis)
|
|
: PostOrder(PO), DomAnalysis(DA), RCIAnalysis(RCIAnalysis),
|
|
HasChanged(false), HasChangedCFG(false),
|
|
IsSrcLoadedFrom(false), HasUnknownStoredValue(false),
|
|
HasForwardedToCopy(false), CurrentCopy(nullptr) {}
|
|
|
|
void reset(SILFunction *F) {
|
|
// Don't hoist destroy_addr globally in transparent functions. Avoid cloning
|
|
// destroy_addr instructions and splitting critical edges before mandatory
|
|
// diagnostic passes. For example, PredictableMemOps can no longer remove
|
|
// some alloc_stack cases after global destroy hoisting. CopyForwarding will
|
|
// be reapplied after the transparent function is inlined at which point
|
|
// global hoisting will be done.
|
|
if (HasChangedCFG) {
|
|
// We are only invalidating the analysis that we use internally.
|
|
// We'll invalidate the analysis that are used by other passes at the end.
|
|
DomAnalysis->invalidate(F, SILAnalysis::InvalidationKind::FunctionBody);
|
|
PostOrder->invalidate(F, SILAnalysis::InvalidationKind::FunctionBody);
|
|
RCIAnalysis->invalidate(F, SILAnalysis::InvalidationKind::FunctionBody);
|
|
}
|
|
CurrentDef = SILValue();
|
|
IsSrcLoadedFrom = false;
|
|
HasUnknownStoredValue = false;
|
|
HasForwardedToCopy = false;
|
|
SrcUserInsts.clear();
|
|
SrcDebugValueInsts.clear();
|
|
TakePoints.clear();
|
|
DestroyPoints.clear();
|
|
DeadInBlocks.clear();
|
|
CurrentCopy = nullptr;
|
|
}
|
|
|
|
bool hasChanged() const { return HasChanged; }
|
|
bool hasChangedCFG() const { return HasChangedCFG; }
|
|
|
|
/// Return true if CurrentDef has been forwarded through one copy into
|
|
/// another. This means we should iterate.
|
|
bool hasForwardedToCopy() const { return HasForwardedToCopy; }
|
|
|
|
void forwardCopiesOf(SILValue Def, SILFunction *F);
|
|
|
|
protected:
|
|
bool propagateCopy(CopyAddrInst *CopyInst);
|
|
CopyAddrInst *findCopyIntoDeadTemp(
|
|
CopyAddrInst *destCopy,
|
|
SmallVectorImpl<SILInstruction *> &debugInstsToDelete);
|
|
bool forwardDeadTempCopy(CopyAddrInst *destCopy);
|
|
bool forwardPropagateCopy();
|
|
bool backwardPropagateCopy();
|
|
|
|
bool isSourceDeadAtCopy();
|
|
|
|
typedef llvm::SmallSetVector<SILInstruction *, 16> UserVector;
|
|
bool doesCopyDominateDestUsers(const UserVector &DirectDestUses);
|
|
|
|
bool markStoredValueUsers(SILValue storedValue);
|
|
};
|
|
|
|
class CopyDestUserVisitor : public AddressUserVisitor {
|
|
SmallPtrSetImpl<SILInstruction *> &DestUsers;
|
|
|
|
public:
|
|
CopyDestUserVisitor(SmallPtrSetImpl<SILInstruction *> &DestUsers)
|
|
: DestUsers(DestUsers) {}
|
|
|
|
virtual bool visitNormalUse(SILInstruction *user) override {
|
|
// Bail on multiple uses in the same instruction to avoid complexity.
|
|
return DestUsers.insert(user).second;
|
|
}
|
|
virtual bool visitTake(CopyAddrInst *take) override {
|
|
return DestUsers.insert(take).second;
|
|
}
|
|
virtual bool visitDestroy(DestroyAddrInst *destroy) override {
|
|
return DestUsers.insert(destroy).second;
|
|
}
|
|
virtual bool visitDebugValue(DebugValueInst *debugValue) override {
|
|
return DestUsers.insert(debugValue).second;
|
|
}
|
|
};
|
|
} // end anonymous namespace
|
|
|
|
/// Attempt to forward, then backward propagate this copy.
|
|
///
|
|
/// The caller has already proven that lifetime of the value being copied ends
|
|
/// at the copy. (Either it is a [take] or is immediately destroyed).
|
|
///
|
|
///
|
|
/// If the forwarded copy is not an [init], then insert a destroy of the copy's
|
|
/// dest.
|
|
bool CopyForwarding::
|
|
propagateCopy(CopyAddrInst *CopyInst) {
|
|
if (!EnableCopyForwarding)
|
|
return false;
|
|
|
|
// CopyForwarding should be split into per-def-state vs. per-copy-state, but
|
|
// this hack is good enough for a pass that's going away "soon".
|
|
struct RAIISetCurrentCopy {
|
|
CopyAddrInst *&CurrentCopy;
|
|
|
|
RAIISetCurrentCopy(CopyAddrInst *&CurrentCopy, CopyAddrInst *CopyInst)
|
|
: CurrentCopy(CurrentCopy) {
|
|
assert(!CurrentCopy);
|
|
CurrentCopy = CopyInst;
|
|
}
|
|
~RAIISetCurrentCopy() {
|
|
CurrentCopy = nullptr;
|
|
}
|
|
};
|
|
RAIISetCurrentCopy setCurrentCopy(CurrentCopy, CopyInst);
|
|
|
|
// Handle copy-of-copy without analyzing uses.
|
|
// Assumes that CurrentCopy->getSrc() is dead after CurrentCopy.
|
|
assert(CurrentCopy->isTakeOfSrc());
|
|
if (forwardDeadTempCopy(CurrentCopy)) {
|
|
HasChanged = true;
|
|
++NumDeadTemp;
|
|
return true;
|
|
}
|
|
|
|
if (forwardPropagateCopy()) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Forwarding Copy:" << *CurrentCopy);
|
|
if (!CurrentCopy->isInitializationOfDest()) {
|
|
// Replace the original copy with a destroy.
|
|
SILBuilderWithScope(CurrentCopy)
|
|
.createDestroyAddr(CurrentCopy->getLoc(), CurrentCopy->getDest());
|
|
}
|
|
swift::salvageStoreDebugInfo(CurrentCopy, CurrentCopy->getSrc(),
|
|
CurrentCopy->getDest());
|
|
CurrentCopy->eraseFromParent();
|
|
HasChanged = true;
|
|
++NumCopyForward;
|
|
return true;
|
|
}
|
|
// Forward propagation failed. Attempt to backward propagate.
|
|
if (CurrentCopy->isInitializationOfDest() && backwardPropagateCopy()) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Reversing Copy:" << *CurrentCopy);
|
|
swift::salvageStoreDebugInfo(CurrentCopy, CurrentCopy->getDest(),
|
|
CurrentCopy->getSrc());
|
|
CurrentCopy->eraseFromParent();
|
|
HasChanged = true;
|
|
++NumCopyBackward;
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/// Find a copy into an otherwise dead temporary:
|
|
///
|
|
/// The given copy is copying out of the temporary
|
|
/// copy_addr %temp, %dest
|
|
///
|
|
/// Precondition: The lifetime of %temp ends at `destCopy`
|
|
/// (%temp is CurrentDef).
|
|
///
|
|
/// Find a previous copy:
|
|
/// copy_addr %src, %temp
|
|
///
|
|
/// Such that it is safe to forward its source into the source of
|
|
/// `destCopy`. i.e. `destCopy` can be safely rewritten as:
|
|
/// copy_addr %src, %dest
|
|
///
|
|
/// Otherwise return nullptr. No instructions are harmed in this analysis.
|
|
///
|
|
/// This can be checked with a simple instruction walk that ends at:
|
|
/// - an intervening instruction that may write to memory
|
|
/// - a use of the temporary, %temp
|
|
///
|
|
/// Unlike the forward and backward propagation that finds all use points, this
|
|
/// handles copies of address projections. By conservatively checking all
|
|
/// intervening instructions, it avoids the need to analyze projection paths.
|
|
CopyAddrInst *CopyForwarding::findCopyIntoDeadTemp(
|
|
CopyAddrInst *destCopy,
|
|
SmallVectorImpl<SILInstruction *> &debugInstsToDelete) {
|
|
auto tmpVal = destCopy->getSrc();
|
|
assert(tmpVal == CurrentDef);
|
|
assert(isIdentifiedSourceValue(tmpVal));
|
|
|
|
for (auto II = destCopy->getIterator(), IB = destCopy->getParent()->begin();
|
|
II != IB;) {
|
|
--II;
|
|
SILInstruction *UserInst = &*II;
|
|
if (auto *srcCopy = dyn_cast<CopyAddrInst>(UserInst)) {
|
|
if (srcCopy->getDest() == tmpVal)
|
|
return srcCopy;
|
|
}
|
|
// 'SrcUserInsts' consists of all users of the 'temp'
|
|
if (SrcUserInsts.count(UserInst))
|
|
return nullptr;
|
|
|
|
// Collect all debug_value w/ address value instructions between temp to
|
|
// dest copy and src to temp copy.
|
|
// On success, these debug_value instructions should be deleted.
|
|
if (isa<DebugValueInst>(UserInst)) {
|
|
// 'SrcDebugValueInsts' consists of all the debug users of 'temp'
|
|
if (SrcDebugValueInsts.count(UserInst))
|
|
debugInstsToDelete.push_back(UserInst);
|
|
continue;
|
|
}
|
|
|
|
if (UserInst->mayWriteToMemory())
|
|
return nullptr;
|
|
}
|
|
return nullptr;
|
|
}
|
|
|
|
/// Forward a copy into a dead temporary as identified by
|
|
/// `findCopyIntoDeadTemp`.
|
|
///
|
|
/// Returns true if the copy was successfully forwarded.
|
|
///
|
|
/// Old SIL:
|
|
/// copy_addr %src, %temp
|
|
/// copy_addr %temp, %dest
|
|
///
|
|
/// New SIL:
|
|
/// copy_addr %src, %dest
|
|
///
|
|
/// Precondition: `srcCopy->getDest()` == `destCopy->getSrc()`
|
|
/// Precondition: %src is unused between srcCopy and destCopy.
|
|
/// Precondition: The lifetime of %temp ends immediate after `destCopy`.
|
|
///
|
|
/// Postcondition:
|
|
/// - `srcCopy` is erased.
|
|
/// - Any initial value in %temp is destroyed at `srcCopy` position.
|
|
/// - %temp is uninitialized following `srcCopy` and subsequent instruction
|
|
/// attempts to destroy this uninitialized value.
|
|
bool CopyForwarding::
|
|
forwardDeadTempCopy(CopyAddrInst *destCopy) {
|
|
SmallVector<SILInstruction*, 2> debugInstsToDelete;
|
|
auto *srcCopy = findCopyIntoDeadTemp(CurrentCopy, debugInstsToDelete);
|
|
if (!srcCopy)
|
|
return false;
|
|
|
|
LLVM_DEBUG(llvm::dbgs() << " Temp Copy:" << *srcCopy
|
|
<< " to " << *destCopy);
|
|
|
|
assert(srcCopy->getDest() == destCopy->getSrc());
|
|
// This pattern can be trivially folded without affecting %temp destroys:
|
|
// copy_addr [...] %src, [init] %temp
|
|
// copy_addr [take] %temp, [...] %dest
|
|
|
|
// If copy into temp is not initializing, add a destroy:
|
|
// - copy_addr %src, %temp
|
|
// + destroy %temp
|
|
if (!srcCopy->isInitializationOfDest()) {
|
|
SILBuilderWithScope(srcCopy)
|
|
.createDestroyAddr(srcCopy->getLoc(), srcCopy->getDest());
|
|
}
|
|
|
|
// Salvage debug values before deleting them.
|
|
swift::salvageStoreDebugInfo(srcCopy, srcCopy->getSrc(), srcCopy->getDest());
|
|
|
|
// Delete all dead debug_value instructions
|
|
for (auto *deadDebugUser : debugInstsToDelete) {
|
|
deadDebugUser->eraseFromParent();
|
|
}
|
|
|
|
// `destCopy` is a take. It's safe to simply rewrite destCopy.
|
|
destCopy->setSrc(srcCopy->getSrc());
|
|
destCopy->setIsTakeOfSrc(srcCopy->isTakeOfSrc());
|
|
srcCopy->eraseFromParent();
|
|
return true;
|
|
}
|
|
|
|
/// Check that the lifetime of %src ends at the copy and is not reinitialized
|
|
/// thereafter with a new value.
|
|
bool CopyForwarding::isSourceDeadAtCopy() {
|
|
// A single copy_addr [take] %Src.
|
|
if (TakePoints.size() == 1 && DestroyPoints.empty() && SrcUserInsts.empty())
|
|
return true;
|
|
|
|
if (TakePoints.empty() && DestroyPoints.size() == 1 &&
|
|
SrcUserInsts.size() == 1) {
|
|
assert(*SrcUserInsts.begin() == CurrentCopy);
|
|
return true;
|
|
}
|
|
// For now just check for a single copy_addr that destroys its source.
|
|
return false;
|
|
}
|
|
|
|
/// Check that all immediate users of the destination address of the copy are
|
|
/// dominated by the copy. There is no path around copy that could initialize
|
|
/// %dest with a different value.
|
|
bool CopyForwarding::doesCopyDominateDestUsers(
|
|
const UserVector &DirectDestUsers) {
|
|
DominanceInfo *DT = DomAnalysis->get(CurrentCopy->getFunction());
|
|
for (auto *user : DirectDestUsers) {
|
|
// Check dominance of the parent blocks.
|
|
if (!DT->properlyDominates(CurrentCopy, user))
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
// Return true if all users were recognized.
|
|
//
|
|
// To find all SSA users of storedValue, we first find the RC root, then search
|
|
// past any instructions that may propagate the reference.
|
|
bool CopyForwarding::markStoredValueUsers(SILValue storedValue) {
|
|
auto *F = storedValue->getFunction();
|
|
|
|
if (storedValue->getType().isTrivial(*F))
|
|
return true;
|
|
|
|
// Find the RC root, peeking past things like struct_extract.
|
|
RCIdentityFunctionInfo *RCI = RCIAnalysis->get(F);
|
|
SILValue root = RCI->getRCIdentityRoot(storedValue);
|
|
|
|
SmallVector<SILInstruction *, 8> users;
|
|
RCI->getRCUsers(root, users);
|
|
|
|
for (SILInstruction *user : users) {
|
|
// Recognize any uses that have no results as normal uses. They cannot
|
|
// transitively propagate a reference.
|
|
if (user->getResults().empty()) {
|
|
continue;
|
|
}
|
|
// Recognize full applies as normal uses. They may transitively retain, but
|
|
// the caller cannot rely on that.
|
|
if (FullApplySite::isa(user)) {
|
|
continue;
|
|
}
|
|
// A single-valued use is nontransitive if its result is trivial.
|
|
if (auto *SVI = dyn_cast<SingleValueInstruction>(user)) {
|
|
if (SVI->getType().isTrivial(*F)) {
|
|
continue;
|
|
}
|
|
}
|
|
// Conservatively treat everything else as potentially transitively
|
|
// retaining the stored value.
|
|
LLVM_DEBUG(llvm::dbgs() << " Cannot reduce lifetime. May retain "
|
|
<< storedValue
|
|
<< " at: " << *user << "\n");
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Returns the associated dealloc_stack if \p ASI has a single dealloc_stack.
|
|
/// Usually this is the case, but the optimizations may generate something like:
|
|
/// %1 = alloc_stack
|
|
/// if (...) {
|
|
/// dealloc_stack %1
|
|
/// } else {
|
|
/// dealloc_stack %1
|
|
/// }
|
|
static DeallocStackInst *getSingleDealloc(AllocStackInst *ASI) {
|
|
return ASI->getSingleDeallocStack();
|
|
}
|
|
|
|
/// Perform forward copy-propagation. Find a set of uses that the given copy can
|
|
/// forward to and replace them with the copy's source.
|
|
///
|
|
/// We must only replace uses of this copy's value. To do this, we search
|
|
/// forward in the current block from the copy that initializes the value to the
|
|
/// point of deinitialization. Typically, this will be a point at which the
|
|
/// value is passed as an 'in' argument:
|
|
/// \code
|
|
/// %copy = alloc_stack $T
|
|
/// ...
|
|
/// CurrentBlock:
|
|
/// copy_addr %arg to [init] %copy : $*T
|
|
/// ...
|
|
/// %ret = apply %callee<T>(%copy) : $@convention(thin) <τ_0_0> (@in τ_0_0) -> ()
|
|
/// \endcode
|
|
///
|
|
/// If the last use (deinit) is a copy, replace it with a destroy+copy[init].
|
|
///
|
|
/// The caller has already guaranteed that the lifetime of the copy's source
|
|
/// ends at this copy. The copy is a [take].
|
|
bool CopyForwarding::forwardPropagateCopy() {
|
|
|
|
SILValue CopyDest = CurrentCopy->getDest();
|
|
// Require the copy dest to be a simple alloc_stack. This ensures that all
|
|
// instructions that may read from the destination address depend on CopyDest.
|
|
if (!isa<AllocStackInst>(CopyDest))
|
|
return false;
|
|
|
|
// Record all direct dest uses. Forward propagation doesn't care if they are
|
|
// projections or propagate the address in any way--their operand only needs
|
|
// to be substituted with the copy's source.
|
|
UserVector DirectDestUsers;
|
|
for (auto *Use : CopyDest->getUses()) {
|
|
auto *UserInst = Use->getUser();
|
|
if (UserInst == CurrentCopy)
|
|
continue;
|
|
|
|
if (isa<DeallocStackInst>(UserInst))
|
|
continue;
|
|
|
|
// Bail on multiple uses in the same instruction so that AnalyzeForwardUse
|
|
// does not need to deal with it.
|
|
if (!DirectDestUsers.insert(UserInst))
|
|
return false;
|
|
}
|
|
// Looking at
|
|
//
|
|
// copy_addr %Src, [init] %Dst
|
|
//
|
|
// We can reuse %Src if it is dead after the copy and not reinitialized. To
|
|
// know that we can safely replace all uses of %Dst with source we must know
|
|
// that it is uniquely named and cannot be accessed outside of the function
|
|
// (an alloc_stack instruction qualifies for this, an inout parameter does
|
|
// not). Additionally, we must know that all accesses to %Dst further on must
|
|
// have had this copy on their path (there might be reinitialization of %Dst
|
|
// later, but there must not be a path around this copy that reads from %Dst).
|
|
if (isSourceDeadAtCopy() && doesCopyDominateDestUsers(DirectDestUsers)) {
|
|
SILValue CopySrc = CurrentCopy->getSrc();
|
|
// Replace all uses of Dest with a use of Src.
|
|
for (SILInstruction *user : DirectDestUsers) {
|
|
for (Operand &oper : user->getAllOperands()) {
|
|
if (oper.get() != CopyDest)
|
|
continue;
|
|
|
|
// Rewrite both read and writes of CopyDest as CopySrc.
|
|
oper.set(CopySrc);
|
|
}
|
|
if (isa<CopyAddrInst>(user))
|
|
HasForwardedToCopy = true;
|
|
}
|
|
// The caller will Remove the destroy_addr of %src.
|
|
assert((DestroyPoints.empty() ||
|
|
(!CurrentCopy->isTakeOfSrc() && DestroyPoints.size() == 1)) &&
|
|
"Must only have one destroy");
|
|
|
|
// The caller will remove the copy_addr.
|
|
return true;
|
|
}
|
|
|
|
SILInstruction *DefDealloc = nullptr;
|
|
if (auto *ASI = dyn_cast<AllocStackInst>(CurrentDef)) {
|
|
DefDealloc = getSingleDealloc(ASI);
|
|
if (!DefDealloc) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping copy" << *CurrentCopy
|
|
<< " stack address has multiple uses.\n");
|
|
return false;
|
|
}
|
|
}
|
|
|
|
// Scan forward recording all operands that use CopyDest until we see the
|
|
// next deinit of CopyDest.
|
|
SmallVector<Operand*, 16> ValueUses;
|
|
auto SI = CurrentCopy->getIterator(), SE = CurrentCopy->getParent()->end();
|
|
for (++SI; SI != SE; ++SI) {
|
|
SILInstruction *UserInst = &*SI;
|
|
// If we see another use of Src, then the source location is reinitialized
|
|
// before the Dest location is deinitialized. So we really need the copy.
|
|
if (SrcUserInsts.count(UserInst)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping copy" << *CurrentCopy
|
|
<< " source used by" << *UserInst);
|
|
return false;
|
|
}
|
|
if (UserInst == DefDealloc) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping copy" << *CurrentCopy
|
|
<< " dealloc_stack before dest use.\n");
|
|
return false;
|
|
}
|
|
// Early check to avoid scanning unrelated instructions.
|
|
if (!DirectDestUsers.count(UserInst))
|
|
continue;
|
|
|
|
AnalyzeForwardUse AnalyzeUse(CopyDest);
|
|
bool seenDeinitOrStore = AnalyzeUse.visit(UserInst);
|
|
if (AnalyzeUse.Oper)
|
|
ValueUses.push_back(AnalyzeUse.Oper);
|
|
|
|
// If this is a deinit or store, we're done searching.
|
|
if (seenDeinitOrStore)
|
|
break;
|
|
|
|
// If this non-deinit instruction wasn't fully analyzed, bail-out.
|
|
if (!AnalyzeUse.Oper)
|
|
return false;
|
|
}
|
|
if (SI == SE)
|
|
return false;
|
|
|
|
// Convert a reinitialization of this address into a destroy, followed by an
|
|
// initialization. Replacing a copy with a destroy+init is not by itself
|
|
// profitable. However, it does allow eliminating the earlier copy, and we may
|
|
// later be able to eliminate this initialization copy.
|
|
if (auto Copy = dyn_cast<CopyAddrInst>(&*SI)) {
|
|
if (Copy->getDest() == CopyDest) {
|
|
assert(!Copy->isInitializationOfDest() && "expected a deinit");
|
|
|
|
DestroyAddrInst *Destroy =
|
|
SILBuilderWithScope(Copy).createDestroyAddr(Copy->getLoc(), CopyDest);
|
|
Copy->setIsInitializationOfDest(IsInitialization);
|
|
|
|
assert(ValueUses.back()->getUser() == Copy && "bad value use");
|
|
ValueUses.back() = &Destroy->getOperandRef();
|
|
}
|
|
}
|
|
// Now that a deinit was found, it is safe to substitute all recorded uses
|
|
// with the copy's source.
|
|
for (auto *Oper : ValueUses) {
|
|
Oper->set(CurrentCopy->getSrc());
|
|
if (isa<CopyAddrInst>(Oper->getUser()))
|
|
HasForwardedToCopy = true;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Given an address defined by 'Def', find the object root and all direct uses,
|
|
/// not including:
|
|
/// - 'Def' itself
|
|
/// - Transitive uses of 'Def' (listed elsewhere in DestUserInsts)
|
|
///
|
|
/// i.e. If Def is returned directly, RootUserInsts will be empty.
|
|
///
|
|
/// Return nullptr when the root != Def, and root has unrecognized uses.
|
|
///
|
|
/// If the returned root is not 'Def' itself, then 'Def' must be an address
|
|
/// projection that can be trivially rematerialized with the root as its
|
|
/// operand.
|
|
static ValueBase *
|
|
findAddressRootAndUsers(ValueBase *Def,
|
|
SmallPtrSetImpl<SILInstruction*> &RootUserInsts) {
|
|
switch (Def->getKind()) {
|
|
default:
|
|
return Def;
|
|
case ValueKind::InitEnumDataAddrInst:
|
|
case ValueKind::InitExistentialAddrInst:
|
|
auto InitInst = cast<SingleValueInstruction>(Def);
|
|
SILValue InitRoot = InitInst->getOperand(0);
|
|
|
|
CopyDestUserVisitor visitor(RootUserInsts);
|
|
if (!visitAddressUsers(InitRoot, InitInst, visitor))
|
|
return nullptr;
|
|
return InitRoot;
|
|
}
|
|
}
|
|
|
|
/// Perform backward copy-propagation. Find the initialization point of the
|
|
/// copy's source and replace the initializer's address with the copy's dest.
|
|
bool CopyForwarding::backwardPropagateCopy() {
|
|
|
|
SILValue CopySrc = CurrentCopy->getSrc();
|
|
ValueBase *CopyDestDef = CurrentCopy->getDest();
|
|
|
|
SmallPtrSet<SILInstruction *, 16> DestUserInsts;
|
|
CopyDestUserVisitor visitor(DestUserInsts);
|
|
if (!visitAddressUsers(CopyDestDef, CurrentCopy, visitor))
|
|
return false;
|
|
|
|
// RootUserInsts will contain any users of the same object not covered by
|
|
// DestUserInsts.
|
|
SmallPtrSet<SILInstruction*, 8> RootUserInsts;
|
|
ValueBase *CopyDestRoot = findAddressRootAndUsers(CopyDestDef, RootUserInsts);
|
|
if (!CopyDestRoot)
|
|
return false;
|
|
|
|
// Require the copy dest value to be identified by this address. This ensures
|
|
// that all instructions that may write to destination address depend on
|
|
// CopyDestRoot.
|
|
if (!isIdentifiedDestValue(CopyDestRoot))
|
|
return false;
|
|
|
|
// Scan backward recording all operands that use CopySrc until we see the
|
|
// most recent init of CopySrc.
|
|
bool seenInit = false;
|
|
bool seenCopyDestDef = false;
|
|
// ValueUses records the uses of CopySrc in reverse order.
|
|
SmallVector<Operand*, 16> ValueUses;
|
|
SmallVector<SILInstruction*, 4> DebugValueInstsToDelete;
|
|
auto SI = CurrentCopy->getIterator(), SE = CurrentCopy->getParent()->begin();
|
|
while (SI != SE) {
|
|
--SI;
|
|
SILInstruction *UserInst = &*SI;
|
|
if (UserInst == CopyDestDef->getDefiningInstruction())
|
|
seenCopyDestDef = true;
|
|
|
|
// If we see another use of Dest, then Dest is live after the Src location
|
|
// is initialized, so we really need the copy.
|
|
if (UserInst == CopyDestRoot->getDefiningInstruction()
|
|
|| DestUserInsts.count(UserInst)
|
|
|| RootUserInsts.count(UserInst)) {
|
|
if (DebugValueInst::hasAddrVal(UserInst)) {
|
|
DebugValueInstsToDelete.push_back(UserInst);
|
|
continue;
|
|
}
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping copy" << *CurrentCopy
|
|
<< " dest used by " << *UserInst);
|
|
return false;
|
|
}
|
|
// Early check to avoid scanning unrelated instructions.
|
|
if (!SrcUserInsts.count(UserInst)
|
|
&& !(isa<DebugValueInst>(UserInst)
|
|
&& SrcDebugValueInsts.count(UserInst)))
|
|
continue;
|
|
|
|
AnalyzeBackwardUse AnalyzeUse(CopySrc);
|
|
seenInit = AnalyzeUse.visit(UserInst);
|
|
// If this use cannot be analyzed, then abort.
|
|
if (!AnalyzeUse.Oper)
|
|
return false;
|
|
// Otherwise record the operand with the earliest use last in the list.
|
|
ValueUses.push_back(AnalyzeUse.Oper);
|
|
// If this is an init, we're done searching.
|
|
if (seenInit)
|
|
break;
|
|
}
|
|
if (!seenInit)
|
|
return false;
|
|
|
|
for (auto *DVAI : DebugValueInstsToDelete)
|
|
DVAI->eraseFromParent();
|
|
|
|
// Convert a reinitialization of this address into a destroy, followed by an
|
|
// initialization. Replacing a copy with a destroy+init is not by itself
|
|
// profitable. However, it does allow us to eliminate the later copy, and the
|
|
// init copy may be eliminated later.
|
|
if (auto Copy = dyn_cast<CopyAddrInst>(&*SI)) {
|
|
if (Copy->getDest() == CopySrc && !Copy->isInitializationOfDest()) {
|
|
SILBuilderWithScope(Copy).createDestroyAddr(Copy->getLoc(), CopySrc);
|
|
Copy->setIsInitializationOfDest(IsInitialization);
|
|
}
|
|
}
|
|
// Rematerialize the projection if needed by simply moving it.
|
|
if (seenCopyDestDef) {
|
|
CopyDestDef->getDefiningInstruction()->moveBefore(&*SI);
|
|
}
|
|
// Now that an init was found, it is safe to substitute all recorded uses
|
|
// with the copy's dest.
|
|
for (auto *Oper : ValueUses) {
|
|
if (auto *SI = dyn_cast<CopyAddrInst>(Oper->getUser())) {
|
|
HasForwardedToCopy = true;
|
|
// This instruction gets "replaced", so we need to salvage its previous
|
|
// debug info.
|
|
swift::salvageStoreDebugInfo(SI, SI->getSrc(), SI->getDest());
|
|
}
|
|
Oper->set(CurrentCopy->getDest());
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Perform CopyForwarding on the current Def.
|
|
void CopyForwarding::forwardCopiesOf(SILValue Def, SILFunction *F) {
|
|
reset(F);
|
|
CurrentDef = Def;
|
|
LLVM_DEBUG(llvm::dbgs() << "Analyzing copies of Def: " << Def);
|
|
CopySrcUserVisitor visitor(*this);
|
|
if (!visitAddressUsers(Def, nullptr, visitor))
|
|
return;
|
|
|
|
// Forward any copies that implicitly destroy CurrentDef.
|
|
for (auto *CopyInst : TakePoints) {
|
|
propagateCopy(CopyInst);
|
|
}
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// CopyForwardingPass
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
namespace {
|
|
#ifndef NDEBUG
|
|
static llvm::cl::opt<int> ForwardStart("copy-forward-start",
|
|
llvm::cl::init(0), llvm::cl::Hidden);
|
|
static llvm::cl::opt<int> ForwardStop("copy-forward-stop",
|
|
llvm::cl::init(-1), llvm::cl::Hidden);
|
|
#endif
|
|
|
|
class CopyForwardingPass : public SILFunctionTransform
|
|
{
|
|
void run() override {
|
|
if (!EnableCopyForwarding)
|
|
return;
|
|
|
|
// This pass assumes that the ownership lifetime of a value in a memory
|
|
// locations can be determined by analyzing operations on the memory
|
|
// address. However, in non-OSSA code, this is not guaranteed. For example,
|
|
// this is valid non-OSSA SIL:
|
|
//
|
|
// bb0(%0 : $AnyObject):
|
|
// %alloc1 = alloc_stack $AnyObject
|
|
// store %0 to %objaddr : $*AnyObject
|
|
// %ref = load %objaddr : $*AnyObject
|
|
// %alloc2 = alloc_stack $ObjWrapper
|
|
// # The in-memory reference is destroyed before retaining the loaded ref.
|
|
// copy_addr [take] %alloc1 to [init] %alloc2 : $*ObjWrapper
|
|
// retain_value %ref : $AnyObject
|
|
// destroy_addr %alloc2 : $*ObjWrapper
|
|
if (!getFunction()->hasOwnership())
|
|
return;
|
|
|
|
LLVM_DEBUG(llvm::dbgs() << "Copy Forwarding in Func "
|
|
<< getFunction()->getName() << "\n");
|
|
|
|
// Collect a set of identified objects (@in arg or alloc_stack) that are
|
|
// copied in this function.
|
|
llvm::SmallSetVector<SILValue, 16> CopiedDefs;
|
|
for (auto &BB : *getFunction())
|
|
for (auto II = BB.begin(), IE = BB.end(); II != IE; ++II) {
|
|
if (auto *CopyInst = dyn_cast<CopyAddrInst>(&*II)) {
|
|
SILValue Def = CopyInst->getSrc();
|
|
if (isIdentifiedSourceValue(Def))
|
|
CopiedDefs.insert(Def);
|
|
else {
|
|
LLVM_DEBUG(llvm::dbgs() << " Skipping Def: " << Def
|
|
<< " not an argument or local var!\n");
|
|
}
|
|
}
|
|
}
|
|
|
|
// Perform Copy Forwarding.
|
|
if (CopiedDefs.empty())
|
|
return;
|
|
|
|
auto *PO = getAnalysis<PostOrderAnalysis>();
|
|
auto *DA = getAnalysis<DominanceAnalysis>();
|
|
auto *RCIA = getAnalysis<RCIdentityAnalysis>();
|
|
auto Forwarding = CopyForwarding(PO, DA, RCIA);
|
|
|
|
for (SILValue Def : CopiedDefs) {
|
|
#ifndef NDEBUG
|
|
static unsigned NumDefs = 0;
|
|
++NumDefs;
|
|
if ((int)NumDefs < ForwardStart || NumDefs >= (unsigned)ForwardStop)
|
|
continue;
|
|
#endif
|
|
// Iterate to forward through chains of copies.
|
|
do {
|
|
Forwarding.forwardCopiesOf(Def, getFunction());
|
|
} while (Forwarding.hasForwardedToCopy());
|
|
}
|
|
if (Forwarding.hasChangedCFG()) {
|
|
// We've split critical edges so we can't preserve CFG.
|
|
invalidateAnalysis(SILAnalysis::InvalidationKind::FunctionBody);
|
|
} else {
|
|
invalidateAnalysis(SILAnalysis::InvalidationKind::CallsAndInstructions);
|
|
}
|
|
}
|
|
};
|
|
|
|
} // end anonymous namespace
|
|
|
|
SILTransform *swift::createCopyForwarding() {
|
|
return new CopyForwardingPass();
|
|
}
|