Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
564 lines (487 sloc) 17.6 KB
//===--- InstructionUtils.cpp - Utilities for SIL instructions ------------===//
//
// 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-inst-utils"
#include "swift/SIL/InstructionUtils.h"
#include "swift/AST/SubstitutionMap.h"
#include "swift/Basic/NullablePtr.h"
#include "swift/SIL/DebugUtils.h"
#include "swift/SIL/Projection.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILBasicBlock.h"
#include "swift/SIL/SILVisitor.h"
using namespace swift;
/// Strip off casts/indexing insts/address projections from V until there is
/// nothing left to strip.
/// FIXME: Why don't we strip projections after stripping indexes?
SILValue swift::getUnderlyingObject(SILValue V) {
while (true) {
SILValue V2 = stripIndexingInsts(stripAddressProjections(stripCasts(V)));
if (V2 == V)
return V2;
V = V2;
}
}
/// Strip off casts and address projections into the interior of a value. Unlike
/// getUnderlyingObject, this does not find the root of a heap object--a class
/// property is itself an address root.
SILValue swift::getUnderlyingAddressRoot(SILValue V) {
while (true) {
SILValue V2 = stripIndexingInsts(stripCasts(V));
switch (V2->getKind()) {
case ValueKind::StructElementAddrInst:
case ValueKind::TupleElementAddrInst:
case ValueKind::UncheckedTakeEnumDataAddrInst:
V2 = cast<SingleValueInstruction>(V2)->getOperand(0);
break;
default:
break;
}
if (V2 == V)
return V2;
V = V2;
}
}
SILValue swift::getUnderlyingObjectStopAtMarkDependence(SILValue V) {
while (true) {
SILValue V2 = stripIndexingInsts(stripAddressProjections(stripCastsWithoutMarkDependence(V)));
if (V2 == V)
return V2;
V = V2;
}
}
static bool isRCIdentityPreservingCast(ValueKind Kind) {
switch (Kind) {
case ValueKind::UpcastInst:
case ValueKind::UncheckedRefCastInst:
case ValueKind::UnconditionalCheckedCastInst:
case ValueKind::UnconditionalCheckedCastValueInst:
case ValueKind::RefToBridgeObjectInst:
case ValueKind::BridgeObjectToRefInst:
return true;
default:
return false;
}
}
/// Return the underlying SILValue after stripping off identity SILArguments if
/// we belong to a BB with one predecessor.
SILValue swift::stripSinglePredecessorArgs(SILValue V) {
while (true) {
auto *A = dyn_cast<SILArgument>(V);
if (!A)
return V;
SILBasicBlock *BB = A->getParent();
// First try and grab the single predecessor of our parent BB. If we don't
// have one, bail.
SILBasicBlock *Pred = BB->getSinglePredecessorBlock();
if (!Pred)
return V;
// Then grab the terminator of Pred...
TermInst *PredTI = Pred->getTerminator();
// And attempt to find our matching argument.
//
// *NOTE* We can only strip things here if we know that there is no semantic
// change in terms of upcasts/downcasts/enum extraction since this is used
// by other routines here. This means that we can only look through
// cond_br/br.
//
// For instance, routines that use stripUpcasts() do not want to strip off a
// downcast that results from checked_cast_br.
if (auto *BI = dyn_cast<BranchInst>(PredTI)) {
V = BI->getArg(A->getIndex());
continue;
}
if (auto *CBI = dyn_cast<CondBranchInst>(PredTI)) {
if (SILValue Arg = CBI->getArgForDestBB(BB, A)) {
V = Arg;
continue;
}
}
return V;
}
}
SILValue swift::stripCastsWithoutMarkDependence(SILValue V) {
while (true) {
V = stripSinglePredecessorArgs(V);
auto K = V->getKind();
if (isRCIdentityPreservingCast(K) ||
K == ValueKind::UncheckedTrivialBitCastInst) {
V = cast<SingleValueInstruction>(V)->getOperand(0);
continue;
}
return V;
}
}
SILValue swift::stripCasts(SILValue V) {
while (true) {
V = stripSinglePredecessorArgs(V);
auto K = V->getKind();
if (isRCIdentityPreservingCast(K)
|| K == ValueKind::UncheckedTrivialBitCastInst
|| K == ValueKind::MarkDependenceInst) {
V = cast<SingleValueInstruction>(V)->getOperand(0);
continue;
}
return V;
}
}
SILValue swift::stripUpCasts(SILValue V) {
assert(V->getType().isClassOrClassMetatype() &&
"Expected class or class metatype!");
V = stripSinglePredecessorArgs(V);
while (auto upcast = dyn_cast<UpcastInst>(V))
V = stripSinglePredecessorArgs(upcast->getOperand());
return V;
}
SILValue swift::stripClassCasts(SILValue V) {
while (true) {
if (auto *UI = dyn_cast<UpcastInst>(V)) {
V = UI->getOperand();
continue;
}
if (auto *UCCI = dyn_cast<UnconditionalCheckedCastInst>(V)) {
V = UCCI->getOperand();
continue;
}
return V;
}
}
SILValue swift::stripAddressAccess(SILValue V) {
while (true) {
switch (V->getKind()) {
default:
return V;
case ValueKind::BeginBorrowInst:
case ValueKind::BeginAccessInst:
V = cast<SingleValueInstruction>(V)->getOperand(0);
}
}
}
SILValue swift::stripAddressProjections(SILValue V) {
while (true) {
V = stripSinglePredecessorArgs(V);
if (!Projection::isAddressProjection(V))
return V;
V = cast<SingleValueInstruction>(V)->getOperand(0);
}
}
SILValue swift::stripValueProjections(SILValue V) {
while (true) {
V = stripSinglePredecessorArgs(V);
if (!Projection::isObjectProjection(V))
return V;
V = cast<SingleValueInstruction>(V)->getOperand(0);
}
}
SILValue swift::stripIndexingInsts(SILValue V) {
while (true) {
if (!isa<IndexingInst>(V))
return V;
V = cast<IndexingInst>(V)->getBase();
}
}
SILValue swift::stripExpectIntrinsic(SILValue V) {
auto *BI = dyn_cast<BuiltinInst>(V);
if (!BI)
return V;
if (BI->getIntrinsicInfo().ID != llvm::Intrinsic::expect)
return V;
return BI->getArguments()[0];
}
SILValue swift::stripBorrow(SILValue V) {
if (auto *BBI = dyn_cast<BeginBorrowInst>(V))
return BBI->getOperand();
return V;
}
// All instructions handled here must propagate their first operand into their
// single result.
//
// This is guaranteed to handle all function-type converstions: ThinToThick,
// ConvertFunction, and ConvertEscapeToNoEscapeInst.
SingleValueInstruction *swift::getSingleValueCopyOrCast(SILInstruction *I) {
if (auto *convert = dyn_cast<ConversionInst>(I))
return convert;
switch (I->getKind()) {
default:
return nullptr;
case SILInstructionKind::CopyValueInst:
case SILInstructionKind::CopyBlockInst:
case SILInstructionKind::CopyBlockWithoutEscapingInst:
case SILInstructionKind::BeginBorrowInst:
case SILInstructionKind::BeginAccessInst:
case SILInstructionKind::MarkDependenceInst:
return cast<SingleValueInstruction>(I);
}
}
// Does this instruction terminate a SIL-level scope?
bool swift::isEndOfScopeMarker(SILInstruction *user) {
switch (user->getKind()) {
default:
return false;
case SILInstructionKind::EndAccessInst:
case SILInstructionKind::EndBorrowInst:
case SILInstructionKind::EndLifetimeInst:
return true;
}
}
bool swift::isIncidentalUse(SILInstruction *user) {
return isEndOfScopeMarker(user) || user->isDebugInstruction() ||
isa<FixLifetimeInst>(user);
}
bool swift::onlyAffectsRefCount(SILInstruction *user) {
switch (user->getKind()) {
default:
return false;
case SILInstructionKind::AutoreleaseValueInst:
case SILInstructionKind::DestroyValueInst:
case SILInstructionKind::ReleaseValueInst:
case SILInstructionKind::RetainValueInst:
case SILInstructionKind::StrongReleaseInst:
case SILInstructionKind::StrongRetainInst:
case SILInstructionKind::UnmanagedAutoreleaseValueInst:
case SILInstructionKind::UnmanagedReleaseValueInst:
case SILInstructionKind::UnmanagedRetainValueInst:
#define ALWAYS_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...) \
case SILInstructionKind::Name##RetainInst: \
case SILInstructionKind::Name##ReleaseInst: \
case SILInstructionKind::StrongRetain##Name##Inst:
#include "swift/AST/ReferenceStorage.def"
return true;
}
}
bool swift::mayCheckRefCount(SILInstruction *User) {
return isa<IsUniqueInst>(User) || isa<IsEscapingClosureInst>(User);
}
bool swift::isSanitizerInstrumentation(SILInstruction *Instruction) {
auto *BI = dyn_cast<BuiltinInst>(Instruction);
if (!BI)
return false;
Identifier Name = BI->getName();
if (Name == BI->getModule().getASTContext().getIdentifier("tsanInoutAccess"))
return true;
return false;
}
SILValue swift::isPartialApplyOfReabstractionThunk(PartialApplyInst *PAI) {
if (PAI->getNumArguments() != 1)
return SILValue();
auto *Fun = PAI->getReferencedFunction();
if (!Fun)
return SILValue();
// Make sure we have a reabstraction thunk.
if (Fun->isThunk() != IsReabstractionThunk)
return SILValue();
// The argument should be a closure.
auto Arg = PAI->getArgument(0);
if (!Arg->getType().is<SILFunctionType>() ||
(!Arg->getType().isReferenceCounted(PAI->getFunction()->getModule()) &&
Arg->getType().getAs<SILFunctionType>()->getRepresentation() !=
SILFunctionType::Representation::Thick))
return SILValue();
return Arg;
}
/// Given a block used as a noescape function argument, attempt to find all
/// Swift closures that invoking the block will call. The StoredClosures may not
/// actually be partial_apply instructions. They may be copied, block arguments,
/// or conversions. The caller must continue searching up the use-def chain.
static SILValue findClosureStoredIntoBlock(SILValue V) {
auto FnType = V->getType().castTo<SILFunctionType>();
assert(FnType->getRepresentation() == SILFunctionTypeRepresentation::Block);
(void)FnType;
// Given a no escape block argument to a function,
// pattern match to find the noescape closure that invoking the block
// will call:
// %noescape_closure = ...
// %wae_Thunk = function_ref @$withoutActuallyEscapingThunk
// %sentinel =
// partial_apply [callee_guaranteed] %wae_thunk(%noescape_closure)
// %noescaped_wrapped = mark_dependence %sentinel on %noescape_closure
// %storage = alloc_stack
// %storage_address = project_block_storage %storage
// store %noescaped_wrapped to [init] %storage_address
// %block = init_block_storage_header %storage invoke %thunk
// %arg = copy_block %block
InitBlockStorageHeaderInst *IBSHI = dyn_cast<InitBlockStorageHeaderInst>(V);
if (!IBSHI)
return nullptr;
SILValue BlockStorage = IBSHI->getBlockStorage();
auto *PBSI = BlockStorage->getSingleUserOfType<ProjectBlockStorageInst>();
assert(PBSI && "Couldn't find block storage projection");
auto *SI = PBSI->getSingleUserOfType<StoreInst>();
assert(SI && "Couldn't find single store of function into block storage");
auto *CV = dyn_cast<CopyValueInst>(SI->getSrc());
if (!CV)
return nullptr;
auto *WrappedNoEscape = dyn_cast<MarkDependenceInst>(CV->getOperand());
if (!WrappedNoEscape)
return nullptr;
auto Sentinel = dyn_cast<PartialApplyInst>(WrappedNoEscape->getValue());
if (!Sentinel)
return nullptr;
auto NoEscapeClosure = isPartialApplyOfReabstractionThunk(Sentinel);
if (WrappedNoEscape->getBase() != NoEscapeClosure)
return nullptr;
// This is the value of the closure to be invoked. To find the partial_apply
// itself, the caller must search the use-def chain.
return NoEscapeClosure;
}
/// Find all closures that may be propagated into the given function-type value.
///
/// Searches the use-def chain from the given value upward until a partial_apply
/// is reached. Populates `results` with the set of partial_apply instructions.
///
/// `funcVal` may be either a function type or an Optional function type. This
/// might be called on a directly applied value or on a call argument, which may
/// in turn be applied within the callee.
void swift::findClosuresForFunctionValue(
SILValue funcVal, TinyPtrVector<PartialApplyInst *> &results) {
SILType funcTy = funcVal->getType();
// Handle `Optional<@convention(block) @noescape (_)->(_)>`
if (auto optionalObjTy = funcTy.getOptionalObjectType())
funcTy = optionalObjTy;
assert(funcTy.is<SILFunctionType>());
SmallVector<SILValue, 4> worklist;
// Avoid exponential path exploration and prevent duplicate results.
llvm::SmallDenseSet<SILValue, 8> visited;
auto worklistInsert = [&](SILValue V) {
if (visited.insert(V).second)
worklist.push_back(V);
};
worklistInsert(funcVal);
while (!worklist.empty()) {
SILValue V = worklist.pop_back_val();
if (auto *I = V->getDefiningInstruction()) {
// Look through copies, borrows, and conversions.
//
// Handle copy_block and copy_block_without_actually_escaping before
// calling findClosureStoredIntoBlock.
if (SingleValueInstruction *SVI = getSingleValueCopyOrCast(I)) {
worklistInsert(SVI->getOperand(0));
continue;
}
}
// Look through Optionals.
if (V->getType().getOptionalObjectType()) {
auto *EI = dyn_cast<EnumInst>(V);
if (EI && EI->hasOperand()) {
worklistInsert(EI->getOperand());
}
// Ignore the .None case.
continue;
}
// Look through Phis.
//
// This should be done before calling findClosureStoredIntoBlock.
if (auto *arg = dyn_cast<SILPhiArgument>(V)) {
SmallVector<std::pair<SILBasicBlock *, SILValue>, 2> blockArgs;
arg->getIncomingPhiValues(blockArgs);
for (auto &blockAndArg : blockArgs)
worklistInsert(blockAndArg.second);
continue;
}
// Look through ObjC closures.
auto fnType = V->getType().getAs<SILFunctionType>();
if (fnType
&& fnType->getRepresentation() == SILFunctionTypeRepresentation::Block) {
if (SILValue storedClosure = findClosureStoredIntoBlock(V))
worklistInsert(storedClosure);
continue;
}
if (auto *PAI = dyn_cast<PartialApplyInst>(V)) {
SILValue thunkArg = isPartialApplyOfReabstractionThunk(PAI);
if (thunkArg) {
// Handle reabstraction thunks recursively. This may reabstract over
// @convention(block).
worklistInsert(thunkArg);
continue;
}
results.push_back(PAI);
continue;
}
// Ignore other unrecognized values that feed this applied argument.
}
}
namespace {
enum class OwnershipQualifiedKind {
NotApplicable,
Qualified,
Unqualified,
};
struct OwnershipQualifiedKindVisitor : SILInstructionVisitor<OwnershipQualifiedKindVisitor, OwnershipQualifiedKind> {
OwnershipQualifiedKind visitSILInstruction(SILInstruction *I) {
return OwnershipQualifiedKind::NotApplicable;
}
#define QUALIFIED_INST(CLASS) \
OwnershipQualifiedKind visit ## CLASS(CLASS *I) { \
return OwnershipQualifiedKind::Qualified; \
}
QUALIFIED_INST(EndBorrowInst)
QUALIFIED_INST(LoadBorrowInst)
QUALIFIED_INST(CopyValueInst)
QUALIFIED_INST(DestroyValueInst)
#define SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...) \
QUALIFIED_INST(Copy##Name##ValueInst)
#include "swift/AST/ReferenceStorage.def"
#undef QUALIFIED_INST
OwnershipQualifiedKind visitLoadInst(LoadInst *LI) {
if (LI->getOwnershipQualifier() == LoadOwnershipQualifier::Unqualified)
return OwnershipQualifiedKind::Unqualified;
return OwnershipQualifiedKind::Qualified;
}
OwnershipQualifiedKind visitStoreInst(StoreInst *SI) {
if (SI->getOwnershipQualifier() == StoreOwnershipQualifier::Unqualified)
return OwnershipQualifiedKind::Unqualified;
return OwnershipQualifiedKind::Qualified;
}
};
} // end anonymous namespace
bool FunctionOwnershipEvaluator::evaluate(SILInstruction *I) {
assert(I->getFunction() == F.get() && "Can not evaluate function ownership "
"implications of an instruction that "
"does not belong to the instruction "
"that we are evaluating");
switch (OwnershipQualifiedKindVisitor().visit(I)) {
case OwnershipQualifiedKind::Unqualified: {
// If we already know that the function has unqualified ownership, just
// return early.
if (!F.get()->hasOwnership())
return true;
// Ok, so we know at this point that we have qualified ownership. If we have
// seen any instructions with qualified ownership, we have an error since
// the function mixes qualified and unqualified instructions.
if (HasOwnershipQualifiedInstruction)
return false;
// Otherwise, set the function to have unqualified ownership. This will
// ensure that no more Qualified instructions can be added to the given
// function.
F.get()->setOwnershipEliminated();
return true;
}
case OwnershipQualifiedKind::Qualified: {
// First check if our function has unqualified ownership. If we already do
// have unqualified ownership, then we know that we have already seen an
// unqualified ownership instruction. This means the function has both
// qualified and unqualified instructions. =><=.
if (!F.get()->hasOwnership())
return false;
// Ok, at this point we know that we are still qualified. Since functions
// start as qualified, we need to set the HasOwnershipQualifiedInstructions
// so we do not need to look back through the function if we see an
// unqualified instruction later on.
HasOwnershipQualifiedInstruction = true;
return true;
}
case OwnershipQualifiedKind::NotApplicable: {
// Not Applicable instr
return true;
}
}
llvm_unreachable("Unhandled OwnershipQualifiedKind in switch.");
}