| //===--- 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."); |
| } |