| //===--- SILCombinerApplyVisitors.cpp -------------------------------------===// |
| // |
| // 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-combine" |
| #include "SILCombiner.h" |
| #include "swift/AST/GenericSignature.h" |
| #include "swift/AST/Module.h" |
| #include "swift/AST/SubstitutionMap.h" |
| #include "swift/Basic/Range.h" |
| #include "swift/SIL/DebugUtils.h" |
| #include "swift/SIL/DynamicCasts.h" |
| #include "swift/SIL/InstructionUtils.h" |
| #include "swift/SIL/PatternMatch.h" |
| #include "swift/SIL/SILBuilder.h" |
| #include "swift/SIL/SILVisitor.h" |
| #include "swift/SILOptimizer/Analysis/ARCAnalysis.h" |
| #include "swift/SILOptimizer/Analysis/AliasAnalysis.h" |
| #include "swift/SILOptimizer/Analysis/CFG.h" |
| #include "swift/SILOptimizer/Analysis/ValueTracking.h" |
| #include "swift/SILOptimizer/Utils/Existential.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| |
| using namespace swift; |
| using namespace swift::PatternMatch; |
| |
| /// Remove pointless reabstraction thunk closures. |
| /// partial_apply %reabstraction_thunk_typeAtoB( |
| /// partial_apply %reabstraction_thunk_typeBtoA %closure_typeB)) |
| /// -> |
| /// %closure_typeB |
| static bool foldInverseReabstractionThunks(PartialApplyInst *PAI, |
| SILCombiner *Combiner) { |
| auto PAIArg = isPartialApplyOfReabstractionThunk(PAI); |
| if (!PAIArg) |
| return false; |
| |
| auto *PAI2 = dyn_cast<PartialApplyInst>(PAIArg); |
| if (!PAI2) |
| return false; |
| |
| if (!hasOneNonDebugUse(PAI2)) |
| return false; |
| |
| auto PAI2Arg = isPartialApplyOfReabstractionThunk(PAI2); |
| if (!PAI2Arg) |
| return false; |
| |
| // The types must match. |
| if (PAI->getType() != PAI2->getArgument(0)->getType()) |
| return false; |
| |
| // Replace the partial_apply(partial_apply(X)) by X and remove the |
| // partial_applies. |
| |
| Combiner->replaceInstUsesWith(*PAI, PAI2->getArgument(0)); |
| Combiner->eraseInstFromFunction(*PAI); |
| assert(onlyHaveDebugUses(PAI2) && "Should not have any uses"); |
| Combiner->eraseInstFromFunction(*PAI2); |
| |
| return true; |
| } |
| |
| SILInstruction *SILCombiner::visitPartialApplyInst(PartialApplyInst *PAI) { |
| // partial_apply without any substitutions or arguments is just a |
| // thin_to_thick_function. |
| if (!PAI->hasSubstitutions() && (PAI->getNumArguments() == 0)) { |
| if (!PAI->isOnStack()) |
| return Builder.createThinToThickFunction(PAI->getLoc(), PAI->getCallee(), |
| PAI->getType()); |
| |
| // Remove dealloc_stack of partial_apply [stack]. |
| // Iterating while delete use a copy. |
| SmallVector<Operand *, 8> Uses(PAI->getUses()); |
| for (auto *Use : Uses) |
| if (auto *dealloc = dyn_cast<DeallocStackInst>(Use->getUser())) |
| eraseInstFromFunction(*dealloc); |
| auto *thinToThick = Builder.createThinToThickFunction( |
| PAI->getLoc(), PAI->getCallee(), PAI->getType()); |
| replaceInstUsesWith(*PAI, thinToThick); |
| eraseInstFromFunction(*PAI); |
| return nullptr; |
| } |
| |
| |
| // partial_apply %reabstraction_thunk_typeAtoB( |
| // partial_apply %reabstraction_thunk_typeBtoA %closure_typeB)) |
| // -> %closure_typeB |
| if (foldInverseReabstractionThunks(PAI, this)) |
| return nullptr; |
| |
| tryOptimizeApplyOfPartialApply(PAI); |
| |
| // Try to delete dead closures. |
| tryDeleteDeadClosure( |
| PAI, InstModCallbacks( |
| [this](SILInstruction *DeadInst) { |
| eraseInstFromFunction(*DeadInst); |
| }, |
| [this](SILInstruction *NewInst) { Worklist.add(NewInst); })); |
| return nullptr; |
| } |
| |
| // Helper class performing the apply{partial_apply(x,y)}(z) -> apply(z,x,y) |
| // peephole. |
| class PartialApplyCombiner { |
| // True if temporaries are not created yet. |
| bool isFirstTime = true; |
| |
| // partial_apply which is being processed. |
| PartialApplyInst *PAI; |
| |
| // Temporaries created as copies of alloc_stack arguments of |
| // the partial_apply. |
| SmallVector<SILValue, 8> Tmps; |
| |
| // Mapping from the original argument of partial_apply to |
| // the temporary containing its copy. |
| llvm::DenseMap<SILValue, SILValue> ArgToTmp; |
| |
| // Set of lifetime endpoints for this partial_apply. |
| // |
| // Used to find the last uses of partial_apply, which is need to insert |
| // releases/destroys of temporaries as early as possible. |
| ValueLifetimeAnalysis::Frontier PAFrontier; |
| |
| SILBuilder &Builder; |
| |
| SILCombiner *SilCombiner; |
| |
| bool processSingleApply(FullApplySite AI); |
| bool allocateTemporaries(); |
| void deallocateTemporaries(); |
| void releaseTemporaries(); |
| |
| public: |
| PartialApplyCombiner(PartialApplyInst *PAI, SILBuilder &Builder, |
| SILCombiner *SilCombiner) |
| : isFirstTime(true), PAI(PAI), Builder(Builder), |
| SilCombiner(SilCombiner) {} |
| SILInstruction *combine(); |
| }; |
| |
| /// Returns true on success. |
| bool PartialApplyCombiner::allocateTemporaries() { |
| // A partial_apply [stack]'s argument are not owned by the partial_apply and |
| // therefore their lifetime must outlive any uses. |
| if (PAI->isOnStack()) { |
| return true; |
| } |
| |
| // Copy the original arguments of the partial_apply into newly created |
| // temporaries and use these temporaries instead of the original arguments |
| // afterwards. |
| // |
| // This is done to "extend" the life-time of original partial_apply arguments, |
| // as they may be destroyed/deallocated before the last use by one of the |
| // apply instructions. |
| // |
| // TODO: Copy arguments of the partial_apply into new temporaries only if the |
| // lifetime of arguments ends before their uses by apply instructions. |
| bool needsReleases = false; |
| CanSILFunctionType PAITy = |
| PAI->getCallee()->getType().getAs<SILFunctionType>(); |
| |
| // Emit a destroy value for each captured closure argument. |
| ArrayRef<SILParameterInfo> Params = PAITy->getParameters(); |
| auto Args = PAI->getArguments(); |
| Params = Params.drop_front(Params.size() - Args.size()); |
| |
| llvm::SmallVector<std::pair<SILValue, uint16_t>, 8> ArgsToHandle; |
| for (unsigned i : indices(Args)) { |
| SILValue Arg = Args[i]; |
| SILParameterInfo Param = Params[i]; |
| if (Param.isIndirectMutating()) |
| continue; |
| |
| // Create a temporary and copy the argument into it, if: |
| // - the argument stems from an alloc_stack |
| // - the argument is consumed by the callee and is indirect |
| // (e.g. it is an @in argument) |
| if (isa<AllocStackInst>(Arg) |
| || (Param.isConsumed() |
| && PAI->getSubstCalleeConv().isSILIndirect(Param))) { |
| // If the argument has a dependent type, then we can not create a |
| // temporary for it at the beginning of the function, so we must bail. |
| // |
| // TODO: This is because we are inserting alloc_stack at the beginning/end |
| // of functions where the dependent type may not exist yet. |
| if (Arg->getType().hasOpenedExistential()) |
| return false; |
| |
| // If the temporary is non-trivial, we need to release it later. |
| if (!Arg->getType().isTrivial(PAI->getModule())) |
| needsReleases = true; |
| ArgsToHandle.push_back(std::make_pair(Arg, i)); |
| } |
| } |
| |
| if (needsReleases) { |
| // Compute the set of endpoints, which will be used to insert releases of |
| // temporaries. This may fail if the frontier is located on a critical edge |
| // which we may not split (no CFG changes in SILCombine). |
| ValueLifetimeAnalysis VLA(PAI); |
| if (!VLA.computeFrontier(PAFrontier, ValueLifetimeAnalysis::DontModifyCFG)) |
| return false; |
| } |
| |
| for (auto ArgWithIdx : ArgsToHandle) { |
| SILValue Arg = ArgWithIdx.first; |
| Builder.setInsertionPoint(PAI->getFunction()->begin()->begin()); |
| // Create a new temporary at the beginning of a function. |
| SILDebugVariable DbgVar(/*Constant*/ true, ArgWithIdx.second); |
| auto *Tmp = Builder.createAllocStack(PAI->getLoc(), Arg->getType(), DbgVar); |
| Builder.setInsertionPoint(PAI); |
| // Copy argument into this temporary. |
| Builder.createCopyAddr(PAI->getLoc(), Arg, Tmp, |
| IsTake_t::IsNotTake, |
| IsInitialization_t::IsInitialization); |
| |
| Tmps.push_back(Tmp); |
| ArgToTmp.insert(std::make_pair(Arg, Tmp)); |
| } |
| return true; |
| } |
| |
| /// Emit dealloc_stack for all temporaries. |
| void PartialApplyCombiner::deallocateTemporaries() { |
| // Insert dealloc_stack instructions at all function exit points. |
| for (SILBasicBlock &BB : *PAI->getFunction()) { |
| TermInst *Term = BB.getTerminator(); |
| if (!Term->isFunctionExiting()) |
| continue; |
| |
| for (auto Op : Tmps) { |
| Builder.setInsertionPoint(Term); |
| Builder.createDeallocStack(PAI->getLoc(), Op); |
| } |
| } |
| } |
| |
| /// Emit code to release/destroy temporaries. |
| void PartialApplyCombiner::releaseTemporaries() { |
| // Insert releases and destroy_addrs as early as possible, |
| // because we don't want to keep objects alive longer than |
| // its really needed. |
| for (auto Op : Tmps) { |
| auto TmpType = Op->getType().getObjectType(); |
| if (TmpType.isTrivial(PAI->getModule())) |
| continue; |
| for (auto *EndPoint : PAFrontier) { |
| Builder.setInsertionPoint(EndPoint); |
| if (!TmpType.isAddressOnly(PAI->getModule())) { |
| auto *Load = Builder.createLoad(PAI->getLoc(), Op, |
| LoadOwnershipQualifier::Unqualified); |
| Builder.createReleaseValue(PAI->getLoc(), Load, Builder.getDefaultAtomicity()); |
| } else { |
| Builder.createDestroyAddr(PAI->getLoc(), Op); |
| } |
| } |
| } |
| } |
| |
| /// Process an apply instruction which uses a partial_apply |
| /// as its callee. |
| /// Returns true on success. |
| bool PartialApplyCombiner::processSingleApply(FullApplySite AI) { |
| Builder.setInsertionPoint(AI.getInstruction()); |
| Builder.setCurrentDebugScope(AI.getDebugScope()); |
| |
| // Prepare the args. |
| SmallVector<SILValue, 8> Args; |
| // First the ApplyInst args. |
| for (auto Op : AI.getArguments()) |
| Args.push_back(Op); |
| |
| SILInstruction *InsertionPoint = &*Builder.getInsertionPoint(); |
| // Next, the partial apply args. |
| |
| // Pre-process partial_apply arguments only once, lazily. |
| if (isFirstTime) { |
| isFirstTime = false; |
| if (!allocateTemporaries()) |
| return false; |
| } |
| |
| // Now, copy over the partial apply args. |
| for (auto Op : PAI->getArguments()) { |
| auto Arg = Op; |
| // If there is new temporary for this argument, use it instead. |
| if (ArgToTmp.count(Arg)) { |
| Op = ArgToTmp.lookup(Arg); |
| } |
| Args.push_back(Op); |
| } |
| |
| Builder.setInsertionPoint(InsertionPoint); |
| Builder.setCurrentDebugScope(AI.getDebugScope()); |
| |
| // The thunk that implements the partial apply calls the closure function |
| // that expects all arguments to be consumed by the function. However, the |
| // captured arguments are not arguments of *this* apply, so they are not |
| // pre-incremented. When we combine the partial_apply and this apply into |
| // a new apply we need to retain all of the closure non-address type |
| // arguments. |
| auto ParamInfo = PAI->getSubstCalleeType()->getParameters(); |
| auto PartialApplyArgs = PAI->getArguments(); |
| // Set of arguments that need to be released after each invocation. |
| SmallVector<SILValue, 8> ToBeReleasedArgs; |
| for (unsigned i = 0, e = PartialApplyArgs.size(); i < e; ++i) { |
| SILValue Arg = PartialApplyArgs[i]; |
| if (!Arg->getType().isAddress()) { |
| // Retain the argument as the callee may consume it. |
| Arg = Builder.emitCopyValueOperation(PAI->getLoc(), Arg); |
| // For non consumed parameters (e.g. guaranteed), we also need to |
| // insert releases after each apply instruction that we create. |
| if (!ParamInfo[ParamInfo.size() - PartialApplyArgs.size() + i]. |
| isConsumed()) |
| ToBeReleasedArgs.push_back(Arg); |
| } |
| } |
| |
| auto Callee = PAI->getCallee(); |
| SubstitutionMap Subs = PAI->getSubstitutionMap(); |
| |
| // The partial_apply might be substituting in an open existential type. |
| Builder.addOpenedArchetypeOperands(PAI); |
| |
| FullApplySite NAI; |
| if (auto *TAI = dyn_cast<TryApplyInst>(AI)) |
| NAI = Builder.createTryApply(AI.getLoc(), Callee, Subs, Args, |
| TAI->getNormalBB(), TAI->getErrorBB()); |
| else |
| NAI = Builder.createApply(AI.getLoc(), Callee, Subs, Args, |
| cast<ApplyInst>(AI)->isNonThrowing()); |
| |
| // We also need to release the partial_apply instruction itself because it |
| // is consumed by the apply_instruction. |
| if (auto *TAI = dyn_cast<TryApplyInst>(AI)) { |
| Builder.setInsertionPoint(TAI->getNormalBB()->begin()); |
| for (auto Arg : ToBeReleasedArgs) { |
| Builder.emitDestroyValueOperation(PAI->getLoc(), Arg); |
| } |
| if (!PAI->hasCalleeGuaranteedContext()) |
| Builder.createStrongRelease(AI.getLoc(), PAI, |
| Builder.getDefaultAtomicity()); |
| Builder.setInsertionPoint(TAI->getErrorBB()->begin()); |
| // Release the non-consumed parameters. |
| for (auto Arg : ToBeReleasedArgs) { |
| Builder.emitDestroyValueOperation(PAI->getLoc(), Arg); |
| } |
| if (!PAI->hasCalleeGuaranteedContext()) |
| Builder.emitDestroyValueOperation(PAI->getLoc(), PAI); |
| Builder.setInsertionPoint(AI.getInstruction()); |
| } else { |
| // Release the non-consumed parameters. |
| for (auto Arg : ToBeReleasedArgs) { |
| Builder.emitDestroyValueOperation(PAI->getLoc(), Arg); |
| } |
| if (!PAI->hasCalleeGuaranteedContext()) |
| Builder.emitDestroyValueOperation(PAI->getLoc(), PAI); |
| } |
| |
| if (auto apply = dyn_cast<ApplyInst>(AI)) |
| SilCombiner->replaceInstUsesWith(*apply, |
| cast<ApplyInst>(NAI.getInstruction())); |
| SilCombiner->eraseInstFromFunction(*AI.getInstruction()); |
| return true; |
| } |
| |
| /// Perform the apply{partial_apply(x,y)}(z) -> apply(z,x,y) peephole |
| /// by iterating over all uses of the partial_apply and searching |
| /// for the pattern to transform. |
| SILInstruction *PartialApplyCombiner::combine() { |
| // We need to model @unowned_inner_pointer better before we can do the |
| // peephole here. |
| for (auto R : PAI->getSubstCalleeType()->getResults()) |
| if (R.getConvention() == ResultConvention::UnownedInnerPointer) |
| return nullptr; |
| |
| // Iterate over all uses of the partial_apply |
| // and look for applies that use it as a callee. |
| |
| // Worklist of operands. |
| SmallVector<Operand *, 8> Uses(PAI->getUses()); |
| |
| // Uses may grow in this loop. |
| for (size_t UseIndex = 0; UseIndex < Uses.size(); ++UseIndex) { |
| auto *Use = Uses[UseIndex]; |
| auto *User = Use->getUser(); |
| |
| // Recurse through conversions. |
| if (auto *CFI = dyn_cast<ConvertEscapeToNoEscapeInst>(User)) { |
| // TODO: Handle argument conversion. All the code in this file needs to be |
| // cleaned up and generalized. The argument conversion handling in |
| // optimizeApplyOfConvertFunctionInst should apply to any combine |
| // involving an apply, not just a specific pattern. |
| // |
| // For now, just handle conversion to @noescape, which is irrelevant for |
| // direct application of the closure. |
| auto ConvertCalleeTy = CFI->getType().castTo<SILFunctionType>(); |
| auto EscapingCalleeTy = |
| ConvertCalleeTy->getWithExtInfo( |
| ConvertCalleeTy->getExtInfo().withNoEscape(false)); |
| assert(Use->get()->getType().castTo<SILFunctionType>() == |
| EscapingCalleeTy); |
| (void)EscapingCalleeTy; |
| Uses.append(CFI->getUses().begin(), CFI->getUses().end()); |
| continue; |
| } |
| // Look through mark_dependence users of partial_apply [stack]. |
| if (auto *MD = dyn_cast<MarkDependenceInst>(User)) { |
| if (MD->getValue() == Use->get() && |
| MD->getValue()->getType().is<SILFunctionType>() && |
| MD->getValue()->getType().castTo<SILFunctionType>()->isNoEscape()) { |
| Uses.append(MD->getUses().begin(), MD->getUses().end()); |
| } |
| continue; |
| } |
| // If this use of a partial_apply is not |
| // an apply which uses it as a callee, bail. |
| auto AI = FullApplySite::isa(User); |
| if (!AI) |
| continue; |
| |
| if (AI.getCallee() != Use->get()) |
| continue; |
| |
| // We cannot handle generic apply yet. Bail. |
| if (AI.hasSubstitutions()) |
| continue; |
| |
| if (!processSingleApply(AI)) |
| return nullptr; |
| } |
| |
| // release/destroy and deallocate introduced temporaries. |
| if (!Tmps.empty()) { |
| releaseTemporaries(); |
| deallocateTemporaries(); |
| } |
| |
| return nullptr; |
| } |
| |
| /// Iterate over all uses of a given partial_apply and check |
| /// if any of those uses are apply instructions. Try to |
| /// combine those applies with this partial_apply. |
| SILInstruction * |
| SILCombiner::tryOptimizeApplyOfPartialApply(PartialApplyInst *PAI) { |
| |
| PartialApplyCombiner PACombiner(PAI, Builder, this); |
| return PACombiner.combine(); |
| } |
| |
| SILInstruction * |
| SILCombiner::optimizeApplyOfConvertFunctionInst(FullApplySite AI, |
| ConvertFunctionInst *CFI) { |
| // We only handle simplification of static function references. If we don't |
| // have one, bail. |
| SILValue funcOper = CFI->getOperand(); |
| if (auto *TTI = dyn_cast<ThinToThickFunctionInst>(funcOper)) |
| funcOper = TTI->getOperand(); |
| |
| auto *FRI = dyn_cast<FunctionRefInst>(funcOper); |
| if (!FRI) |
| return nullptr; |
| |
| // Grab our relevant callee types... |
| CanSILFunctionType SubstCalleeTy = AI.getSubstCalleeType(); |
| auto ConvertCalleeTy = funcOper->getType().castTo<SILFunctionType>(); |
| |
| // ... and make sure they have no unsubstituted generics. If they do, bail. |
| if (SubstCalleeTy->hasArchetype() || ConvertCalleeTy->hasArchetype()) |
| return nullptr; |
| |
| // Indirect results are not currently handled. |
| if (AI.hasIndirectSILResults()) |
| return nullptr; |
| |
| // Bail if the result type of the converted callee is different from the callee's |
| // result type of the apply instruction. |
| if (SubstCalleeTy->getAllResultsType() != ConvertCalleeTy->getAllResultsType()) { |
| return nullptr; |
| } |
| |
| // Ok, we can now perform our transformation. Grab AI's operands and the |
| // relevant types from the ConvertFunction function type and AI. |
| Builder.setCurrentDebugScope(AI.getDebugScope()); |
| OperandValueArrayRef Ops = AI.getArgumentsWithoutIndirectResults(); |
| SILFunctionConventions substConventions(SubstCalleeTy, FRI->getModule()); |
| SILFunctionConventions convertConventions(ConvertCalleeTy, FRI->getModule()); |
| auto oldOpTypes = substConventions.getParameterSILTypes(); |
| auto newOpTypes = convertConventions.getParameterSILTypes(); |
| |
| assert(Ops.size() == SubstCalleeTy->getNumParameters() |
| && "Ops and op types must have same size."); |
| assert(Ops.size() == ConvertCalleeTy->getNumParameters() |
| && "Ops and op types must have same size."); |
| |
| llvm::SmallVector<SILValue, 8> Args; |
| auto newOpI = newOpTypes.begin(); |
| auto oldOpI = oldOpTypes.begin(); |
| for (unsigned i = 0, e = Ops.size(); i != e; ++i, ++newOpI, ++oldOpI) { |
| SILValue Op = Ops[i]; |
| SILType OldOpType = *oldOpI; |
| SILType NewOpType = *newOpI; |
| |
| // Convert function takes refs to refs, address to addresses, and leaves |
| // other types alone. |
| if (OldOpType.isAddress()) { |
| assert(NewOpType.isAddress() && "Addresses should map to addresses."); |
| auto UAC = Builder.createUncheckedAddrCast(AI.getLoc(), Op, NewOpType); |
| Args.push_back(UAC); |
| } else if (OldOpType.getASTType() != NewOpType.getASTType()) { |
| auto URC = Builder.createUncheckedBitCast(AI.getLoc(), Op, NewOpType); |
| Args.push_back(URC); |
| } else { |
| Args.push_back(Op); |
| } |
| } |
| |
| // Create the new apply inst. |
| SILInstruction *NAI; |
| if (auto *TAI = dyn_cast<TryApplyInst>(AI)) |
| NAI = Builder.createTryApply(AI.getLoc(), FRI, |
| SubstitutionMap(), Args, |
| TAI->getNormalBB(), TAI->getErrorBB()); |
| else { |
| NAI = Builder.createApply(AI.getLoc(), FRI, SubstitutionMap(), Args, |
| cast<ApplyInst>(AI)->isNonThrowing()); |
| assert(FullApplySite::isa(NAI).getSubstCalleeType()->getAllResultsType() == |
| AI.getSubstCalleeType()->getAllResultsType() && |
| "Function types should be the same"); |
| } |
| return NAI; |
| } |
| |
| bool |
| SILCombiner::recursivelyCollectARCUsers(UserListTy &Uses, ValueBase *Value) { |
| // FIXME: We could probably optimize this case too |
| if (auto *AI = dyn_cast<ApplyInst>(Value)) |
| if (AI->hasIndirectResults()) |
| return false; |
| |
| for (auto *Use : Value->getUses()) { |
| SILInstruction *Inst = Use->getUser(); |
| if (isa<RefCountingInst>(Inst) || |
| isa<DebugValueInst>(Inst)) { |
| Uses.push_back(Inst); |
| continue; |
| } |
| if (isa<TupleExtractInst>(Inst) || |
| isa<StructExtractInst>(Inst) || |
| isa<PointerToAddressInst>(Inst)) { |
| Uses.push_back(Inst); |
| if (recursivelyCollectARCUsers(Uses, cast<SingleValueInstruction>(Inst))) |
| continue; |
| } |
| return false; |
| } |
| return true; |
| } |
| |
| bool SILCombiner::eraseApply(FullApplySite FAS, const UserListTy &Users) { |
| |
| // Compute the places where we have to insert release-instructions for the |
| // owned arguments. This must not be done before the result of the |
| // apply is destroyed. Therefore we compute the lifetime of the apply-result. |
| |
| // TODO: this is not required anymore when we have ownership SIL. But with |
| // the current SIL it can happen that the retain of a parameter is moved |
| // _after_ the apply. |
| // When we have ownership SIL we can just destroy the parameters at the apply |
| // location. |
| |
| ValueLifetimeAnalysis VLA(FAS.getInstruction(), Users); |
| ValueLifetimeAnalysis::Frontier Frontier; |
| if (Users.empty()) { |
| // If the call does not have any ARC-uses or if there is no return value at |
| // all, we insert the argument release instructions right before the call. |
| Frontier.push_back(FAS.getInstruction()); |
| } else { |
| if (!VLA.computeFrontier(Frontier, ValueLifetimeAnalysis::DontModifyCFG)) |
| return false; |
| // As we are extending the lifetimes of owned parameters, we have to make |
| // sure that no dealloc_ref instructions are within this extended liferange. |
| // It could be that the dealloc_ref is deallocating a parameter and then |
| // we would have a release after the dealloc. |
| if (VLA.containsDeallocRef(Frontier)) |
| return false; |
| } |
| |
| // Release and destroy any owned or in-arguments. |
| auto FuncType = FAS.getOrigCalleeType(); |
| assert(FuncType->getParameters().size() == FAS.getNumArguments() && |
| "mismatching number of arguments"); |
| for (SILInstruction *FrontierInst : Frontier) { |
| Builder.setInsertionPoint(FrontierInst); |
| for (int i = 0, e = FAS.getNumArguments(); i < e; ++i) { |
| SILParameterInfo PI = FuncType->getParameters()[i]; |
| auto Arg = FAS.getArgument(i); |
| switch (PI.getConvention()) { |
| case ParameterConvention::Indirect_In: |
| case ParameterConvention::Indirect_In_Constant: |
| Builder.createDestroyAddr(FAS.getLoc(), Arg); |
| break; |
| case ParameterConvention::Direct_Owned: |
| Builder.createReleaseValue(FAS.getLoc(), Arg, Builder.getDefaultAtomicity()); |
| break; |
| case ParameterConvention::Indirect_In_Guaranteed: |
| case ParameterConvention::Indirect_Inout: |
| case ParameterConvention::Indirect_InoutAliasable: |
| case ParameterConvention::Direct_Unowned: |
| case ParameterConvention::Direct_Guaranteed: |
| break; |
| } |
| } |
| } |
| |
| // Erase all of the reference counting instructions (in reverse order to have |
| // no dangling uses). |
| for (auto rit = Users.rbegin(), re = Users.rend(); rit != re; ++rit) |
| eraseInstFromFunction(**rit); |
| |
| // And the Apply itself. |
| eraseInstFromFunction(*FAS.getInstruction()); |
| |
| return true; |
| } |
| |
| SILInstruction * |
| SILCombiner::optimizeConcatenationOfStringLiterals(ApplyInst *AI) { |
| // String literals concatenation optimizer. |
| return tryToConcatenateStrings(AI, Builder); |
| } |
| |
| /// This routine replaces the old witness method inst with a new one. |
| void SILCombiner::replaceWitnessMethodInst( |
| WitnessMethodInst *WMI, SILBuilderContext &BuilderCtx, CanType ConcreteType, |
| const ProtocolConformanceRef ConformanceRef) { |
| SILBuilderWithScope WMIBuilder(WMI, BuilderCtx); |
| auto *NewWMI = WMIBuilder.createWitnessMethod( |
| WMI->getLoc(), ConcreteType, ConformanceRef, WMI->getMember(), |
| WMI->getType()); |
| WMI->replaceAllUsesWith(NewWMI); |
| if (WMI->use_empty()) |
| eraseInstFromFunction(*WMI); |
| } |
| |
| // This function determines concrete type of an opened existential argument |
| // using ProtocolConformanceAnalysis. The concrete type of the argument can be a |
| // class, struct, or an enum. |
| Optional<ConcreteOpenedExistentialInfo> |
| SILCombiner::buildConcreteOpenedExistentialInfoFromSoleConformingType( |
| Operand &ArgOperand) { |
| SILInstruction *AI = ArgOperand.getUser(); |
| SILModule &M = AI->getModule(); |
| |
| // SoleConformingType is only applicable in whole-module compilation. |
| if (!M.isWholeModule()) |
| return None; |
| |
| // Determine the protocol. |
| ProtocolDecl *PD = nullptr; |
| WitnessMethodInst *WMI = nullptr; |
| FullApplySite FAS = FullApplySite::isa(AI); |
| if (FAS && (WMI = dyn_cast<WitnessMethodInst>(FAS.getCallee())) && |
| (FAS.getSelfArgumentOperand().get() == ArgOperand.get())) { |
| // If the witness method mutates self, we cannot replace self. |
| // |
| // FIXME: Remove this out-dated check for mutating self. canReplaceCopiedArg |
| // is supposed to handle this case. |
| if (FAS.getOrigCalleeType()->getSelfParameter().isIndirectMutating()) |
| return None; |
| PD = WMI->getLookupProtocol(); |
| } else { |
| auto ArgType = ArgOperand.get()->getType(); |
| auto SwiftArgType = ArgType.getASTType(); |
| if (!ArgType.isExistentialType() || ArgType.isAnyObject() || |
| SwiftArgType->isAny()) |
| return None; |
| PD = dyn_cast<ProtocolDecl>(SwiftArgType->getAnyNominal()); |
| } |
| |
| if (!PD) |
| return None; |
| |
| // Determine the sole conforming type. |
| CanType ConcreteType; |
| if (!PCA->getSoleConformingType(PD, CHA, ConcreteType)) |
| return None; |
| |
| // Determine OpenedArchetypeDef and SubstituionMap. |
| ConcreteOpenedExistentialInfo COAI(ArgOperand, ConcreteType, PD); |
| if (!COAI.CEI) |
| return None; |
| |
| const OpenedArchetypeInfo &OAI = COAI.OAI; |
| ConcreteExistentialInfo &SoleCEI = *COAI.CEI; |
| assert(SoleCEI.isValid()); |
| |
| if (SoleCEI.ConcreteValue) |
| return COAI; |
| |
| // Create SIL type for the concrete type. |
| SILType concreteSILType = M.Types.getLoweredType(ConcreteType); |
| |
| // Prepare the code by adding UncheckedCast instructions that cast opened |
| // existentials to concrete types. Set the ConcreteValue of CEI. |
| if (auto *OER = dyn_cast<OpenExistentialRefInst>(OAI.OpenedArchetypeValue)) { |
| SoleCEI.ConcreteValue = |
| Builder.createUncheckedRefCast(OER->getLoc(), OER, concreteSILType); |
| return COAI; |
| } |
| if (auto *OEA = dyn_cast<OpenExistentialAddrInst>(OAI.OpenedArchetypeValue)) { |
| // Bail if ConcreteSILType is not the same SILType as the type stored in the |
| // existential after maximal reabstraction. |
| auto abstractionPattern = Lowering::AbstractionPattern::getOpaque(); |
| auto abstractTy = M.Types.getLoweredType(abstractionPattern, ConcreteType); |
| if (abstractTy != concreteSILType) |
| return None; |
| |
| SoleCEI.ConcreteValue = |
| Builder.createUncheckedAddrCast( |
| OEA->getLoc(), OEA, concreteSILType.getAddressType()); |
| return COAI; |
| } |
| // Bail if OpenArchetypeInfo recognizes any additional opened archetype |
| // producers. This shouldn't be hit currently because metatypes don't |
| // conform to protocols. |
| return None; |
| } |
| |
| // This function builds a ConcreteExistentialInfo by first following the data |
| // flow chain from the ArgOperand. Otherwise, we check if the operand is of |
| // protocol type that conforms to a single concrete type. |
| Optional<ConcreteOpenedExistentialInfo> |
| SILCombiner::buildConcreteOpenedExistentialInfo(Operand &ArgOperand) { |
| // Build a ConcreteOpenedExistentialInfo following the data flow chain of the |
| // ArgOperand through the open_existential backward to an init_existential. |
| ConcreteOpenedExistentialInfo COEI(ArgOperand); |
| if (COEI.CEI) |
| return COEI; |
| |
| // Use SoleConformingType information. |
| return buildConcreteOpenedExistentialInfoFromSoleConformingType(ArgOperand); |
| } |
| |
| // Build ConcreteExistentialInfo for every existential argument of an Apply |
| // instruction including Self. |
| void SILCombiner::buildConcreteOpenedExistentialInfos( |
| FullApplySite Apply, |
| llvm::SmallDenseMap<unsigned, ConcreteOpenedExistentialInfo> &COEIs, |
| SILBuilderContext &BuilderCtx, |
| SILOpenedArchetypesTracker &OpenedArchetypesTracker) { |
| for (unsigned ArgIdx = 0; ArgIdx < Apply.getNumArguments(); ArgIdx++) { |
| auto ArgASTType = Apply.getArgument(ArgIdx)->getType().getASTType(); |
| if (!ArgASTType->hasArchetype()) |
| continue; |
| |
| auto OptionalCOEI = |
| buildConcreteOpenedExistentialInfo(Apply.getArgumentOperands()[ArgIdx]); |
| if (!OptionalCOEI.hasValue()) |
| continue; |
| auto COEI = OptionalCOEI.getValue(); |
| assert(COEI.isValid()); |
| COEIs.try_emplace(ArgIdx, COEI); |
| |
| ConcreteExistentialInfo &CEI = *COEI.CEI; |
| if (CEI.ConcreteType->isOpenedExistential()) { |
| // Temporarily record this opened existential def in this local |
| // BuilderContext before rewriting any uses of the ConcreteType. |
| OpenedArchetypesTracker.addOpenedArchetypeDef( |
| cast<ArchetypeType>(CEI.ConcreteType), CEI.ConcreteTypeDef); |
| } |
| } |
| } |
| |
| /// Given an Apply and an argument value produced by InitExistentialAddrInst, |
| /// return true if the argument can be replaced by a copy of its value. |
| /// |
| /// FIXME: remove this helper when we can assume SIL opaque values. |
| static bool canReplaceCopiedArg(FullApplySite Apply, SILValue Arg, |
| DominanceAnalysis *DA, unsigned ArgIdx) { |
| auto *IEA = dyn_cast<InitExistentialAddrInst>(Arg); |
| // Only init_existential_addr may be copied. |
| if (!IEA) |
| return false; |
| |
| // If the witness method mutates Arg, we cannot replace Arg with |
| // the source of a copy. Otherwise the call would modify another value than |
| // the original argument. |
| auto origConv = Apply.getOrigCalleeConv(); |
| if (origConv.getParamInfoForSILArg(ArgIdx).isIndirectMutating()) |
| return false; |
| |
| auto *DT = DA->get(Apply.getFunction()); |
| auto *AI = Apply.getInstruction(); |
| SILValue existentialAddr = IEA->getOperand(); |
| |
| // If we peeked through an InitEnumDataAddr or some such, then don't assume we |
| // can reuse the copied value. It's likely destroyed by |
| // UncheckedTakeEnumDataInst before the copy. |
| auto *ASI = dyn_cast<AllocStackInst>(existentialAddr); |
| if (!ASI) |
| return false; |
| |
| // Return true only if the given value is guaranteed to be initialized across |
| // the given call site. |
| // |
| // It's possible for an address to be initialized/deinitialized/reinitialized. |
| // Rather than keeping track of liveness, we very conservatively check that |
| // all deinitialization occures after the call. |
| auto isDestroy = [](Operand *use) { |
| switch (use->getUser()->getKind()) { |
| default: |
| return false; |
| case SILInstructionKind::DestroyAddrInst: |
| case SILInstructionKind::DeinitExistentialAddrInst: |
| return true; |
| case SILInstructionKind::CopyAddrInst: { |
| auto *copy = cast<CopyAddrInst>(use->getUser()); |
| return copy->getSrc() == use->get() && copy->isTakeOfSrc(); |
| } |
| } |
| }; |
| for (auto use : existentialAddr->getUses()) { |
| SILInstruction *user = use->getUser(); |
| if (isDestroy(use)) { |
| if (!DT->properlyDominates(AI, user)) |
| return false; |
| } else { |
| // The caller has to guarantee that there are no other instructions which |
| // use the address. This is done in findInitExistential called from |
| // the constructor of ConcreteExistentialInfo. |
| assert(isa<CopyAddrInst>(user) || isa<InitExistentialAddrInst>(user) || |
| isa<OpenExistentialAddrInst>(user) || |
| isa<DeallocStackInst>(user) || |
| isa<ApplyInst>(user) || isa<TryApplyInst>(user) || |
| user->isDebugInstruction() && "Unexpected instruction"); |
| } |
| } |
| return true; |
| } |
| |
| // Check the legal conditions under which a Arg parameter (specified as ArgIdx) |
| // can be replaced with a concrete type. Concrete type info is passed as CEI |
| // argument. |
| bool SILCombiner::canReplaceArg(FullApplySite Apply, |
| const OpenedArchetypeInfo &OAI, |
| const ConcreteExistentialInfo &CEI, |
| unsigned ArgIdx) { |
| |
| // Don't specialize apply instructions that return the callee's Arg type, |
| // because this optimization does not know how to substitute types in the |
| // users of this apply. In the function type substitution below, all |
| // references to OpenedArchetype will be substituted. So walk to type to |
| // find all possible references, such as returning Optional<Arg>. |
| if (Apply.getType().getASTType().findIf( |
| [&OAI](Type t) -> bool { return t->isEqual(OAI.OpenedArchetype); })) { |
| return false; |
| } |
| // Bail out if any other arguments or indirect result that refer to the |
| // OpenedArchetype. The following optimization substitutes all occurrences |
| // of OpenedArchetype in the function signature, but will only rewrite the |
| // Arg operand. |
| // |
| // Note that the language does not allow Self to occur in contravariant |
| // position. However, SIL does allow this and it can happen as a result of |
| // upstream transformations. Since this is bail-out logic, it must handle |
| // all verifiable SIL. |
| |
| // This bailout check is also needed for non-Self arguments [including Self]. |
| unsigned NumApplyArgs = Apply.getNumArguments(); |
| for (unsigned Idx = 0; Idx < NumApplyArgs; Idx++) { |
| if (Idx == ArgIdx) |
| continue; |
| if (Apply.getArgument(Idx)->getType().getASTType().findIf( |
| [&OAI](Type t) -> bool { |
| return t->isEqual(OAI.OpenedArchetype); |
| })) { |
| return false; |
| } |
| } |
| // The apply can only be rewritten in terms of the concrete value if it is |
| // legal to pass that value as the Arg argument. |
| if (CEI.isConcreteValueCopied |
| && (!CEI.ConcreteValue |
| || !canReplaceCopiedArg(Apply, CEI.ConcreteValue, DA, ArgIdx))) { |
| return false; |
| } |
| // It is safe to replace Arg. |
| return true; |
| } |
| |
| /// Rewrite the given method apply instruction in terms of the provided conrete |
| /// type information. |
| /// |
| /// If the rewrite is successful, the original apply will be removed and the new |
| /// apply is returned. Otherwise, the original apply will not be removed and |
| /// nullptr is returned. |
| /// |
| /// Creates a new apply instruction that uses the concrete type instead of the |
| /// existential type. Type substitution will be performed from all occurrences |
| /// of CEI.OpenedArchetype to the replacement type CEI.ConcreteType within the |
| /// applied function type. The single self argument of the apply will be |
| /// rewritten. This helps the devirtualizer to replace witness_method by |
| /// class_method instructions and then devirtualize. |
| /// |
| /// Note that the substituted type, CEI.OpenedArchetype, is the same type as the |
| /// self argument for nonstatic methods, but for static methods self is the |
| /// metatype instead. For witness methods, CEI.OpenedArchetype is usually the |
| /// same as WMI->getLookupType() but differs in the unusual situation in which |
| /// the witness method is looked up using a different opened archetype. |
| /// |
| /// FIXME: Protocol methods (witness or default) that return Self will be given |
| /// a new return type. This implementation fails to update the type signature of |
| /// SSA uses in those cases. Currently we bail out on methods that return Self. |
| SILInstruction *SILCombiner::createApplyWithConcreteType( |
| FullApplySite Apply, |
| const llvm::SmallDenseMap<unsigned, ConcreteOpenedExistentialInfo> &COAIs, |
| SILBuilderContext &BuilderCtx) { |
| |
| // Ensure that the callee is polymorphic. |
| assert(Apply.getOrigCalleeType()->isPolymorphic()); |
| |
| // Create the new set of arguments to apply including their substitutions. |
| SubstitutionMap NewCallSubs = Apply.getSubstitutionMap(); |
| SmallVector<SILValue, 8> NewArgs; |
| bool UpdatedArgs = false; |
| unsigned ArgIdx = 0; |
| // Push the indirect result arguments. |
| for (unsigned EndIdx = Apply.getSubstCalleeConv().getSILArgIndexOfFirstParam(); |
| ArgIdx < EndIdx; ++ArgIdx) { |
| NewArgs.push_back(Apply.getArgument(ArgIdx)); |
| } |
| // Transform the parameter arguments. |
| for (unsigned EndIdx = Apply.getNumArguments(); ArgIdx < EndIdx; ++ArgIdx) { |
| auto ArgIt = COAIs.find(ArgIdx); |
| if (ArgIt == COAIs.end()) { |
| // Use the old argument if it does not have a valid concrete existential. |
| NewArgs.push_back(Apply.getArgument(ArgIdx)); |
| continue; |
| } |
| const OpenedArchetypeInfo &OAI = ArgIt->second.OAI; |
| const ConcreteExistentialInfo &CEI = *ArgIt->second.CEI; |
| assert(CEI.isValid()); |
| |
| // Check for Arg's concrete type propagation legality. |
| if (!canReplaceArg(Apply, OAI, CEI, ArgIdx)) { |
| NewArgs.push_back(Apply.getArgument(ArgIdx)); |
| continue; |
| } |
| UpdatedArgs = true; |
| // Ensure that we have a concrete value to propagate. |
| assert(CEI.ConcreteValue); |
| NewArgs.push_back(CEI.ConcreteValue); |
| // Form a new set of substitutions where the argument is |
| // replaced with a concrete type. |
| NewCallSubs = NewCallSubs.subst( |
| [&](SubstitutableType *type) -> Type { |
| if (type == OAI.OpenedArchetype) |
| return CEI.ConcreteType; |
| return type; |
| }, |
| [&](CanType origTy, Type substTy, |
| ProtocolDecl *proto) -> Optional<ProtocolConformanceRef> { |
| if (origTy->isEqual(OAI.OpenedArchetype)) { |
| assert(substTy->isEqual(CEI.ConcreteType)); |
| // Do a conformance lookup on this witness requirement using the |
| // existential's conformances. The witness requirement may be a |
| // base type of the existential's requirements. |
| return CEI.lookupExistentialConformance(proto); |
| } |
| return ProtocolConformanceRef(proto); |
| }); |
| } |
| |
| if (!UpdatedArgs) |
| return nullptr; |
| |
| // Now create the new apply instruction. |
| SILBuilderWithScope ApplyBuilder(Apply.getInstruction(), BuilderCtx); |
| FullApplySite NewApply; |
| if (auto *TAI = dyn_cast<TryApplyInst>(Apply)) |
| NewApply = ApplyBuilder.createTryApply( |
| Apply.getLoc(), Apply.getCallee(), NewCallSubs, NewArgs, |
| TAI->getNormalBB(), TAI->getErrorBB()); |
| else |
| NewApply = ApplyBuilder.createApply( |
| Apply.getLoc(), Apply.getCallee(), NewCallSubs, NewArgs, |
| cast<ApplyInst>(Apply)->isNonThrowing()); |
| |
| if (auto NewAI = dyn_cast<ApplyInst>(NewApply)) |
| replaceInstUsesWith(*cast<ApplyInst>(Apply.getInstruction()), NewAI); |
| |
| eraseInstFromFunction(*Apply.getInstruction()); |
| |
| return NewApply.getInstruction(); |
| } |
| |
| /// Rewrite a witness method's lookup type from an archetype to a concrete type. |
| /// Example: |
| /// %existential = alloc_stack $Protocol |
| /// %value = init_existential_addr %existential : $Concrete |
| /// copy_addr ... to %value |
| /// %witness = witness_method $@opened |
| /// apply %witness<T : Protocol>(%existential) |
| /// |
| /// ==> apply %witness<Concrete : Protocol>(%existential) |
| SILInstruction * |
| SILCombiner::propagateConcreteTypeOfInitExistential(FullApplySite Apply, |
| WitnessMethodInst *WMI) { |
| // Check if it is legal to perform the propagation. |
| if (WMI->getConformance().isConcrete()) |
| return nullptr; |
| |
| // If the lookup type is not an opened existential type, |
| // it cannot be made more concrete. |
| if (!WMI->getLookupType()->isOpenedExistential()) |
| return nullptr; |
| |
| // Try to derive the concrete type and the related conformance of self and |
| // other existential arguments by searching either for a preceding |
| // init_existential or looking up sole conforming type. |
| // |
| // buildConcreteOpenedExistentialInfo takes a SILBuilderContext because it may |
| // insert an uncheched cast to the concrete type, and it tracks the defintion |
| // of any opened archetype needed to use the concrete type. |
| SILBuilderContext BuilderCtx(Builder.getModule(), Builder.getTrackingList()); |
| SILOpenedArchetypesTracker OpenedArchetypesTracker(&Builder.getFunction()); |
| BuilderCtx.setOpenedArchetypesTracker(&OpenedArchetypesTracker); |
| llvm::SmallDenseMap<unsigned, ConcreteOpenedExistentialInfo> COEIs; |
| buildConcreteOpenedExistentialInfos(Apply, COEIs, BuilderCtx, |
| OpenedArchetypesTracker); |
| |
| // Bail, if no argument has a concrete existential to propagate. |
| if (COEIs.empty()) |
| return nullptr; |
| |
| auto SelfCOEIIt = |
| COEIs.find(Apply.getCalleeArgIndex(Apply.getSelfArgumentOperand())); |
| |
| // If no SelfCOEI is found, then just update the Apply with new COEIs for |
| // other arguments. |
| if (SelfCOEIIt == COEIs.end()) |
| return createApplyWithConcreteType(Apply, COEIs, BuilderCtx); |
| |
| auto &SelfCOEI = SelfCOEIIt->second; |
| assert(SelfCOEI.isValid()); |
| |
| const ConcreteExistentialInfo &SelfCEI = *SelfCOEI.CEI; |
| assert(SelfCEI.isValid()); |
| |
| // Get the conformance of the init_existential type, which is passed as the |
| // self argument, on the witness' protocol. |
| ProtocolConformanceRef SelfConformance = |
| *SelfCEI.lookupExistentialConformance(WMI->getLookupProtocol()); |
| |
| // Propagate the concrete type into a callee-operand, which is a |
| // witness_method instruction. It's ok to rewrite the witness method in terms |
| // of a concrete type without rewriting the apply itself. In fact, doing so |
| // may allow the Devirtualizer pass to finish the job. |
| // |
| // If we create a new instruction that’s the same as the old one we’ll |
| // cause an infinite loop: |
| // NewWMI will be added to the Builder’s tracker list. |
| // SILCombine, in turn, uses the tracker list to populate the worklist |
| // As such, if we don’t remove the witness method later on in the pass, we |
| // are stuck: |
| // We will re-create the same instruction and re-populate the worklist |
| // with it. |
| if (SelfCEI.ConcreteType != WMI->getLookupType() || |
| SelfConformance != WMI->getConformance()) { |
| replaceWitnessMethodInst(WMI, BuilderCtx, SelfCEI.ConcreteType, |
| SelfConformance); |
| } |
| |
| /// Create the new apply instruction using concrete types for arguments. |
| return createApplyWithConcreteType(Apply, COEIs, BuilderCtx); |
| } |
| |
| /// Rewrite a protocol extension lookup type from an archetype to a concrete |
| /// type. |
| /// Example: |
| /// %ref = alloc_ref $C |
| /// %existential = init_existential_ref %ref : $C : $C, $P |
| /// %opened = open_existential_ref %existential : $P to $@opened |
| /// %f = function_ref @defaultMethod |
| /// apply %f<@opened P>(%opened) |
| /// |
| /// ==> apply %f<C : P>(%ref) |
| SILInstruction * |
| SILCombiner::propagateConcreteTypeOfInitExistential(FullApplySite Apply) { |
| // This optimization requires a generic argument. |
| if (!Apply.hasSubstitutions()) |
| return nullptr; |
| |
| // Try to derive the concrete type and the related conformance of self and |
| // other existential arguments by searching either for a preceding |
| // init_existential or looking up sole conforming type. |
| llvm::SmallDenseMap<unsigned, ConcreteOpenedExistentialInfo> COEIs; |
| SILBuilderContext BuilderCtx(Builder.getModule(), Builder.getTrackingList()); |
| SILOpenedArchetypesTracker OpenedArchetypesTracker(&Builder.getFunction()); |
| BuilderCtx.setOpenedArchetypesTracker(&OpenedArchetypesTracker); |
| buildConcreteOpenedExistentialInfos(Apply, COEIs, BuilderCtx, |
| OpenedArchetypesTracker); |
| |
| // Bail, if no argument has a concrete existential to propagate. |
| if (COEIs.empty()) |
| return nullptr; |
| |
| return createApplyWithConcreteType(Apply, COEIs, BuilderCtx); |
| } |
| |
| /// Check that all users of the apply are retain/release ignoring one |
| /// user. |
| static bool |
| hasOnlyRetainReleaseUsers(ApplyInst *AI, SILInstruction *IgnoreUser, |
| SmallVectorImpl<SILInstruction *> &Users) { |
| for (auto *Use : getNonDebugUses(AI)) { |
| if (Use->getUser() == IgnoreUser) |
| continue; |
| |
| if (!isa<RetainValueInst>(Use->getUser()) && |
| !isa<ReleaseValueInst>(Use->getUser()) && |
| !isa<StrongRetainInst>(Use->getUser()) && |
| !isa<StrongReleaseInst>(Use->getUser())) |
| return false; |
| |
| Users.push_back(Use->getUser()); |
| } |
| return true; |
| }; |
| |
| /// We only know how to simulate reference call effects for unary |
| /// function calls that take their argument @owned or @guaranteed and return an |
| /// @owned value. |
| static bool knowHowToEmitReferenceCountInsts(ApplyInst *Call) { |
| if (Call->getNumArguments() != 1) |
| return false; |
| |
| FunctionRefInst *FRI = cast<FunctionRefInst>(Call->getCallee()); |
| SILFunction *F = FRI->getReferencedFunction(); |
| auto FnTy = F->getLoweredFunctionType(); |
| |
| // Look at the result type. |
| if (FnTy->getNumResults() != 1) |
| return false; |
| auto ResultInfo = FnTy->getResults()[0]; |
| if (ResultInfo.getConvention() != ResultConvention::Owned) |
| return false; |
| |
| // Look at the parameter. |
| auto Params = FnTy->getParameters(); |
| (void) Params; |
| assert(Params.size() == 1 && "Expect one parameter"); |
| auto ParamConv = FnTy->getParameters()[0].getConvention(); |
| |
| return ParamConv == ParameterConvention::Direct_Owned || |
| ParamConv == ParameterConvention::Direct_Guaranteed; |
| } |
| |
| /// Add reference counting operations equal to the effect of the call. |
| static void emitMatchingRCAdjustmentsForCall(ApplyInst *Call, SILValue OnX) { |
| FunctionRefInst *FRI = cast<FunctionRefInst>(Call->getCallee()); |
| SILFunction *F = FRI->getReferencedFunction(); |
| auto FnTy = F->getLoweredFunctionType(); |
| assert(FnTy->getNumResults() == 1); |
| auto ResultInfo = FnTy->getResults()[0]; |
| (void) ResultInfo; |
| |
| assert(ResultInfo.getConvention() == ResultConvention::Owned && |
| "Expect a @owned return"); |
| assert(Call->getNumArguments() == 1 && "Expect a unary call"); |
| |
| // Emit a retain for the @owned return. |
| SILBuilderWithScope Builder(Call); |
| Builder.createRetainValue(Call->getLoc(), OnX, Builder.getDefaultAtomicity()); |
| |
| // Emit a release for the @owned parameter, or none for a @guaranteed |
| // parameter. |
| auto Params = FnTy->getParameters(); |
| (void) Params; |
| assert(Params.size() == 1 && "Expect one parameter"); |
| auto ParamInfo = FnTy->getParameters()[0].getConvention(); |
| assert(ParamInfo == ParameterConvention::Direct_Owned || |
| ParamInfo == ParameterConvention::Direct_Guaranteed); |
| |
| if (ParamInfo == ParameterConvention::Direct_Owned) |
| Builder.createReleaseValue(Call->getLoc(), OnX, Builder.getDefaultAtomicity()); |
| } |
| |
| /// Replace an application of a cast composition f_inverse(f(x)) by x. |
| bool SILCombiner::optimizeIdentityCastComposition(ApplyInst *FInverse, |
| StringRef FInverseName, |
| StringRef FName) { |
| // Needs to have a known semantics. |
| if (!FInverse->hasSemantics(FInverseName)) |
| return false; |
| |
| // We need to know how to replace the call by reference counting instructions. |
| if (!knowHowToEmitReferenceCountInsts(FInverse)) |
| return false; |
| |
| // Need to have a matching 'f'. |
| auto *F = dyn_cast<ApplyInst>(FInverse->getArgument(0)); |
| if (!F) |
| return false; |
| if (!F->hasSemantics(FName)) |
| return false; |
| if (!knowHowToEmitReferenceCountInsts(F)) |
| return false; |
| |
| // The types must match. |
| if (F->getArgument(0)->getType() != FInverse->getType()) |
| return false; |
| |
| // Retains, releases of the result of F. |
| SmallVector<SILInstruction *, 16> RetainReleases; |
| if (!hasOnlyRetainReleaseUsers(F, FInverse, RetainReleases)) |
| return false; |
| |
| // Okay, now we know we can remove the calls. |
| auto X = F->getArgument(0); |
| |
| // Redirect f's result's retains/releases to affect x. |
| for (auto *User : RetainReleases) { |
| // X might not be strong_retain/release'able. Replace it by a |
| // retain/release_value on X instead. |
| if (isa<StrongRetainInst>(User)) { |
| SILBuilderWithScope Builder(User); |
| Builder.createRetainValue(User->getLoc(), X, |
| cast<StrongRetainInst>(User)->getAtomicity()); |
| eraseInstFromFunction(*User); |
| continue; |
| } |
| if (isa<StrongReleaseInst>(User)) { |
| SILBuilderWithScope Builder(User); |
| Builder.createReleaseValue(User->getLoc(), X, |
| cast<StrongReleaseInst>(User)->getAtomicity()); |
| eraseInstFromFunction(*User); |
| continue; |
| } |
| User->setOperand(0, X); |
| } |
| |
| // Simulate the reference count effects of the calls before removing |
| // them. |
| emitMatchingRCAdjustmentsForCall(F, X); |
| emitMatchingRCAdjustmentsForCall(FInverse, X); |
| |
| // Replace users of f_inverse by x. |
| replaceInstUsesWith(*FInverse, X); |
| |
| // Remove the calls. |
| eraseInstFromFunction(*FInverse); |
| eraseInstFromFunction(*F); |
| |
| return true; |
| } |
| |
| // Return a new apply with the specified callee. This creates a new apply rather |
| // than simply rewriting the callee operand because the apply's SubstCalleeType, |
| // derived from the callee and substitution list, may change. |
| FullApplySite SILCombiner::rewriteApplyCallee(FullApplySite apply, |
| SILValue callee) { |
| SmallVector<SILValue, 4> arguments; |
| for (SILValue arg : apply.getArguments()) |
| arguments.push_back(arg); |
| |
| Builder.addOpenedArchetypeOperands(apply.getInstruction()); |
| if (auto *TAI = dyn_cast<TryApplyInst>(apply)) { |
| return Builder.createTryApply(TAI->getLoc(), callee, |
| TAI->getSubstitutionMap(), arguments, |
| TAI->getNormalBB(), TAI->getErrorBB()); |
| } else { |
| return Builder.createApply(apply.getLoc(), callee, |
| apply.getSubstitutionMap(), arguments, |
| cast<ApplyInst>(apply)->isNonThrowing()); |
| } |
| } |
| |
| SILInstruction *SILCombiner::visitApplyInst(ApplyInst *AI) { |
| Builder.setCurrentDebugScope(AI->getDebugScope()); |
| // apply{partial_apply(x,y)}(z) -> apply(z,x,y) is triggered |
| // from visitPartialApplyInst(), so bail here. |
| if (isa<PartialApplyInst>(AI->getCallee())) |
| return nullptr; |
| |
| if (auto *CFI = dyn_cast<ConvertFunctionInst>(AI->getCallee())) |
| return optimizeApplyOfConvertFunctionInst(AI, CFI); |
| |
| // Optimize readonly functions with no meaningful users. |
| SILFunction *SF = AI->getReferencedFunction(); |
| if (SF && SF->getEffectsKind() < EffectsKind::ReleaseNone) { |
| UserListTy Users; |
| if (recursivelyCollectARCUsers(Users, AI)) { |
| if (eraseApply(AI, Users)) |
| return nullptr; |
| } |
| // We found a user that we can't handle. |
| } |
| |
| if (SF) { |
| if (SF->getEffectsKind() < EffectsKind::ReleaseNone) { |
| // Try to optimize string concatenation. |
| if (auto I = optimizeConcatenationOfStringLiterals(AI)) { |
| return I; |
| } |
| } |
| if (SF->hasSemanticsAttr("array.uninitialized")) { |
| UserListTy Users; |
| // If the uninitialized array is only written into then it can be removed. |
| if (recursivelyCollectARCUsers(Users, AI)) { |
| if (eraseApply(AI, Users)) |
| return nullptr; |
| } |
| } |
| } |
| |
| |
| // (apply (thin_to_thick_function f)) to (apply f) |
| if (auto *TTTFI = dyn_cast<ThinToThickFunctionInst>(AI->getCallee())) { |
| // We currently don't remove any possible retain associated with the thick |
| // function when rewriting the callsite. This should be ok because the |
| // ABI normally expects a guaranteed callee. |
| if (!AI->getOrigCalleeType()->isCalleeConsumed()) |
| return rewriteApplyCallee(AI, TTTFI->getOperand()).getInstruction(); |
| } |
| |
| // (apply (witness_method)) -> propagate information about |
| // a concrete type from init_existential_addr or init_existential_ref. |
| if (auto *WMI = dyn_cast<WitnessMethodInst>(AI->getCallee())) { |
| if (propagateConcreteTypeOfInitExistential(AI, WMI)) { |
| return nullptr; |
| } |
| } |
| |
| // (apply (function_ref method_from_protocol_extension)) -> |
| // propagate information about a concrete type from init_existential_addr or |
| // init_existential_ref. |
| if (isa<FunctionRefInst>(AI->getCallee())) { |
| if (propagateConcreteTypeOfInitExistential(AI)) { |
| return nullptr; |
| } |
| } |
| |
| // Optimize f_inverse(f(x)) -> x. |
| if (optimizeIdentityCastComposition(AI, "convertFromObjectiveC", |
| "convertToObjectiveC")) |
| return nullptr; |
| if (optimizeIdentityCastComposition(AI, "convertToObjectiveC", |
| "convertFromObjectiveC")) |
| return nullptr; |
| |
| return nullptr; |
| } |
| |
| bool SILCombiner:: |
| isTryApplyResultNotUsed(UserListTy &AcceptedUses, TryApplyInst *TAI) { |
| SILBasicBlock *NormalBB = TAI->getNormalBB(); |
| SILBasicBlock *ErrorBB = TAI->getErrorBB(); |
| |
| // The results of a try_apply are not only the normal and error return values, |
| // but also the decision whether it throws or not. Therefore we have to check |
| // if both, the normal and the error block, are empty and lead to a common |
| // destination block. |
| |
| // Check if the normal and error blocks have a common single successor. |
| auto *NormalBr = dyn_cast<BranchInst>(NormalBB->getTerminator()); |
| if (!NormalBr) |
| return false; |
| auto *ErrorBr = dyn_cast<BranchInst>(ErrorBB->getTerminator()); |
| if (!ErrorBr || ErrorBr->getDestBB() != NormalBr->getDestBB()) |
| return false; |
| |
| assert(NormalBr->getNumArgs() == ErrorBr->getNumArgs() && |
| "mismatching number of arguments for the same destination block"); |
| |
| // Check if both blocks pass the same arguments to the common destination. |
| for (unsigned Idx = 0, End = NormalBr->getNumArgs(); Idx < End; Idx++) { |
| if (NormalBr->getArg(Idx) != ErrorBr->getArg(Idx)) |
| return false; |
| } |
| |
| // Check if the normal and error results only have ARC operations as uses. |
| if (!recursivelyCollectARCUsers(AcceptedUses, NormalBB->getArgument(0))) |
| return false; |
| if (!recursivelyCollectARCUsers(AcceptedUses, ErrorBB->getArgument(0))) |
| return false; |
| |
| SmallPtrSet<SILInstruction *, 8> UsesSet; |
| for (auto *I : AcceptedUses) |
| UsesSet.insert(I); |
| |
| // Check if the normal and error blocks are empty, except the ARC uses. |
| for (auto &I : *NormalBB) { |
| if (!UsesSet.count(&I) && !isa<TermInst>(&I)) |
| return false; |
| } |
| for (auto &I : *ErrorBB) { |
| if (!UsesSet.count(&I) && !isa<TermInst>(&I)) |
| return false; |
| } |
| return true; |
| } |
| |
| SILInstruction *SILCombiner::visitTryApplyInst(TryApplyInst *AI) { |
| // apply{partial_apply(x,y)}(z) -> apply(z,x,y) is triggered |
| // from visitPartialApplyInst(), so bail here. |
| if (isa<PartialApplyInst>(AI->getCallee())) |
| return nullptr; |
| |
| if (auto *CFI = dyn_cast<ConvertFunctionInst>(AI->getCallee())) { |
| return optimizeApplyOfConvertFunctionInst(AI, CFI); |
| } |
| |
| // Optimize readonly functions with no meaningful users. |
| SILFunction *Fn = AI->getReferencedFunction(); |
| if (Fn && Fn->getEffectsKind() < EffectsKind::ReleaseNone) { |
| UserListTy Users; |
| if (isTryApplyResultNotUsed(Users, AI)) { |
| SILBasicBlock *BB = AI->getParent(); |
| SILBasicBlock *NormalBB = AI->getNormalBB(); |
| SILBasicBlock *ErrorBB = AI->getErrorBB(); |
| SILLocation Loc = AI->getLoc(); |
| const SILDebugScope *DS = AI->getDebugScope(); |
| if (eraseApply(AI, Users)) { |
| // Replace the try_apply with a cond_br false, which will be removed by |
| // SimplifyCFG. We don't want to modify the CFG in SILCombine. |
| Builder.setInsertionPoint(BB); |
| Builder.setCurrentDebugScope(DS); |
| auto *TrueLit = Builder.createIntegerLiteral(Loc, |
| SILType::getBuiltinIntegerType(1, Builder.getASTContext()), 0); |
| Builder.createCondBranch(Loc, TrueLit, NormalBB, ErrorBB); |
| |
| NormalBB->eraseArgument(0); |
| ErrorBB->eraseArgument(0); |
| return nullptr; |
| } |
| } |
| // We found a user that we can't handle. |
| } |
| |
| // (try_apply (thin_to_thick_function f)) to (try_apply f) |
| if (auto *TTTFI = dyn_cast<ThinToThickFunctionInst>(AI->getCallee())) { |
| // We currently don't remove any possible retain associated with the thick |
| // function when rewriting the callsite. This should be ok because the |
| // ABI normally expects a guaranteed callee. |
| if (!AI->getOrigCalleeType()->isCalleeConsumed()) |
| return rewriteApplyCallee(AI, TTTFI->getOperand()).getInstruction(); |
| } |
| |
| // (apply (witness_method)) -> propagate information about |
| // a concrete type from init_existential_addr or init_existential_ref. |
| if (auto *WMI = dyn_cast<WitnessMethodInst>(AI->getCallee())) { |
| if (propagateConcreteTypeOfInitExistential(AI, WMI)) { |
| return nullptr; |
| } |
| } |
| |
| // (apply (function_ref method_from_protocol_extension)) -> |
| // propagate information about a concrete type from init_existential_addr or |
| // init_existential_ref. |
| if (isa<FunctionRefInst>(AI->getCallee())) { |
| if (propagateConcreteTypeOfInitExistential(AI)) { |
| return nullptr; |
| } |
| } |
| |
| return nullptr; |
| } |