| //===--- AllocBoxToStack.cpp - Promote alloc_box to alloc_stack -----------===// |
| // |
| // 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 "allocbox-to-stack" |
| #include "swift/AST/DiagnosticsSIL.h" |
| #include "swift/Basic/BlotMapVector.h" |
| #include "swift/SIL/ApplySite.h" |
| #include "swift/SIL/Dominance.h" |
| #include "swift/SIL/SILArgument.h" |
| #include "swift/SIL/SILBuilder.h" |
| #include "swift/SIL/SILCloner.h" |
| #include "swift/SILOptimizer/PassManager/Passes.h" |
| #include "swift/SILOptimizer/PassManager/Transforms.h" |
| #include "swift/SILOptimizer/Utils/InstOptUtils.h" |
| #include "swift/SILOptimizer/Utils/SILOptFunctionBuilder.h" |
| #include "swift/SILOptimizer/Utils/SpecializationMangler.h" |
| #include "swift/SILOptimizer/Utils/StackNesting.h" |
| #include "swift/SILOptimizer/Utils/ValueLifetime.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| using namespace swift; |
| |
| STATISTIC(NumStackPromoted, "Number of alloc_box's promoted to the stack"); |
| |
| // MaxLocalApplyRecurDepth limits the recursive analysis depth while |
| // checking if a box can be promoted to stack. This is currently set to 4, a |
| // limit assumed to be sufficient to handle typical call chain of local |
| // functions through which a box can be passed. |
| static llvm::cl::opt<unsigned> MaxLocalApplyRecurDepth( |
| "max-local-apply-recur-depth", llvm::cl::init(4), |
| llvm::cl::desc("Max recursive depth for analyzing local functions")); |
| |
| static llvm::cl::opt<bool> AllocBoxToStackAnalyzeApply( |
| "allocbox-to-stack-analyze-apply", llvm::cl::init(true), |
| llvm::cl::desc("Analyze functions into while alloc_box is passed")); |
| |
| //===-----------------------------------------------------------------------===// |
| // SIL Utilities for alloc_box Promotion |
| //===----------------------------------------------------------------------===// |
| |
| static SILValue stripOffCopyValue(SILValue V) { |
| while (auto *CVI = dyn_cast<CopyValueInst>(V)) { |
| V = CVI->getOperand(); |
| } |
| return V; |
| } |
| |
| /// Returns True if the operand or one of its users is captured. |
| static bool useCaptured(Operand *UI) { |
| auto *User = UI->getUser(); |
| |
| // These instructions do not cause the address to escape. |
| if (isa<DebugValueInst>(User) || isa<DebugValueAddrInst>(User) |
| || isa<StrongReleaseInst>(User) || isa<StrongRetainInst>(User) |
| || isa<DestroyValueInst>(User)) |
| return false; |
| |
| if (auto *Store = dyn_cast<StoreInst>(User)) { |
| if (Store->getDest() == UI->get()) |
| return false; |
| } else if (auto *Assign = dyn_cast<AssignInst>(User)) { |
| if (Assign->getDest() == UI->get()) |
| return false; |
| } |
| |
| return true; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Liveness for alloc_box Promotion |
| //===----------------------------------------------------------------------===// |
| |
| // Is any successor of BB in the LiveIn set? |
| static bool successorHasLiveIn(SILBasicBlock *BB, |
| SmallPtrSetImpl<SILBasicBlock *> &LiveIn) { |
| for (auto &Succ : BB->getSuccessors()) |
| if (LiveIn.count(Succ)) |
| return true; |
| |
| return false; |
| } |
| |
| // Propagate liveness backwards from an initial set of blocks in our |
| // LiveIn set. |
| static void propagateLiveness(SmallPtrSetImpl<SILBasicBlock *> &LiveIn, |
| SILBasicBlock *DefBB) { |
| |
| // First populate a worklist of predecessors. |
| SmallVector<SILBasicBlock *, 64> Worklist; |
| for (auto *BB : LiveIn) |
| for (auto Pred : BB->getPredecessorBlocks()) |
| Worklist.push_back(Pred); |
| |
| // Now propagate liveness backwards until we hit the alloc_box. |
| while (!Worklist.empty()) { |
| auto *BB = Worklist.pop_back_val(); |
| |
| // If it's already in the set, then we've already queued and/or |
| // processed the predecessors. |
| if (BB == DefBB || !LiveIn.insert(BB).second) |
| continue; |
| |
| for (auto Pred : BB->getPredecessorBlocks()) |
| Worklist.push_back(Pred); |
| } |
| } |
| |
| // Walk backwards in BB looking for strong_release, destroy_value, or |
| // dealloc_box of the given value, and add it to releases. |
| static bool addLastRelease(SILValue V, SILBasicBlock *BB, |
| SmallVectorImpl<SILInstruction *> &Releases) { |
| for (auto I = BB->rbegin(); I != BB->rend(); ++I) { |
| if (isa<StrongReleaseInst>(*I) || isa<DeallocBoxInst>(*I) || |
| isa<DestroyValueInst>(*I)) { |
| if (stripOffCopyValue(I->getOperand(0)) != V) |
| continue; |
| |
| Releases.push_back(&*I); |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| // Find the final releases of the alloc_box along any given path. |
| // These can include paths from a release back to the alloc_box in a |
| // loop. |
| static bool getFinalReleases(SILValue Box, |
| SmallVectorImpl<SILInstruction *> &Releases) { |
| SmallPtrSet<SILBasicBlock *, 16> LiveIn; |
| SmallPtrSet<SILBasicBlock *, 16> UseBlocks; |
| |
| auto *DefBB = Box->getParentBlock(); |
| |
| auto seenRelease = false; |
| SILInstruction *OneRelease = nullptr; |
| |
| // We'll treat this like a liveness problem where the alloc_box is |
| // the def. Each block that has a use of the owning pointer has the |
| // value live-in unless it is the block with the alloc_box. |
| SmallVector<Operand *, 32> Worklist(Box->use_begin(), Box->use_end()); |
| while (!Worklist.empty()) { |
| auto *Op = Worklist.pop_back_val(); |
| auto *User = Op->getUser(); |
| auto *BB = User->getParent(); |
| |
| if (isa<ProjectBoxInst>(User)) |
| continue; |
| |
| if (BB != DefBB) |
| LiveIn.insert(BB); |
| |
| // Also keep track of the blocks with uses. |
| UseBlocks.insert(BB); |
| |
| // If we have a copy value or a mark_uninitialized, add its uses to the work |
| // list and continue. |
| if (isa<MarkUninitializedInst>(User) || isa<CopyValueInst>(User)) { |
| llvm::copy(cast<SingleValueInstruction>(User)->getUses(), |
| std::back_inserter(Worklist)); |
| continue; |
| } |
| |
| // Try to speed up the trivial case of single release/dealloc. |
| if (isa<StrongReleaseInst>(User) || isa<DeallocBoxInst>(User) || |
| isa<DestroyValueInst>(User)) { |
| if (!seenRelease) |
| OneRelease = User; |
| else |
| OneRelease = nullptr; |
| |
| seenRelease = true; |
| } |
| } |
| |
| // Only a single release/dealloc? We're done! |
| if (OneRelease) { |
| Releases.push_back(OneRelease); |
| return true; |
| } |
| |
| propagateLiveness(LiveIn, DefBB); |
| |
| // Now examine each block we saw a use in. If it has no successors |
| // that are in LiveIn, then the last use in the block is the final |
| // release/dealloc. |
| for (auto *BB : UseBlocks) |
| if (!successorHasLiveIn(BB, LiveIn)) |
| if (!addLastRelease(Box, BB, Releases)) |
| return false; |
| |
| return true; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // alloc_box Escape Analysis |
| //===----------------------------------------------------------------------===// |
| |
| /// This is a list we use to store a set of indices. We create the set by |
| /// sorting, uniquing at the appropriate time. The reason why it makes sense to |
| /// just use a sorted vector with std::count is because generally functions do |
| /// not have that many arguments and even fewer promoted arguments. |
| using ArgIndexList = SmallVector<unsigned, 8>; |
| |
| static bool partialApplyEscapes(SILValue V, bool examineApply); |
| |
| /// Could this operand to an apply escape that function by being |
| /// stored or returned? |
| static bool applyArgumentEscapes(FullApplySite Apply, Operand *O) { |
| SILFunction *F = Apply.getReferencedFunctionOrNull(); |
| // If we cannot examine the function body, assume the worst. |
| if (!F || F->empty()) |
| return true; |
| |
| // Check the uses of the operand, but do not recurse down into other |
| // apply instructions. |
| auto calleeArg = F->getArgument(Apply.getCalleeArgIndex(*O)); |
| return partialApplyEscapes(calleeArg, /* examineApply = */ false); |
| } |
| |
| static bool partialApplyEscapes(SILValue V, bool examineApply) { |
| SILModuleConventions ModConv(*V->getModule()); |
| SmallVector<Operand *, 32> Worklist(V->use_begin(), V->use_end()); |
| while (!Worklist.empty()) { |
| Operand *Op = Worklist.pop_back_val(); |
| |
| // These instructions do not cause the address to escape. |
| if (!useCaptured(Op)) |
| continue; |
| |
| auto *User = Op->getUser(); |
| |
| // If we have a copy_value, the copy value does not cause an escape, but its |
| // uses might do so... so add the copy_value's uses to the worklist and |
| // continue. |
| if (auto CVI = dyn_cast<CopyValueInst>(User)) { |
| llvm::copy(CVI->getUses(), std::back_inserter(Worklist)); |
| continue; |
| } |
| |
| if (auto Apply = FullApplySite::isa(User)) { |
| // Applying a function does not cause the function to escape. |
| if (!Apply.isArgumentOperand(*Op)) |
| continue; |
| |
| // apply instructions do not capture the pointer when it is passed |
| // indirectly |
| if (Apply.getArgumentConvention(*Op).isIndirectConvention()) |
| continue; |
| |
| // Optionally drill down into an apply to see if the operand is |
| // captured in or returned from the apply. |
| if (examineApply && !applyArgumentEscapes(Apply, Op)) |
| continue; |
| } |
| |
| // partial_apply instructions do not allow the pointer to escape |
| // when it is passed indirectly, unless the partial_apply itself |
| // escapes |
| if (auto *PartialApply = dyn_cast<PartialApplyInst>(User)) { |
| auto Args = PartialApply->getArguments(); |
| auto Params = PartialApply->getSubstCalleeType()->getParameters(); |
| Params = Params.slice(Params.size() - Args.size(), Args.size()); |
| if (ModConv.isSILIndirect(Params[Op->getOperandNumber() - 1])) { |
| if (partialApplyEscapes(PartialApply, /*examineApply = */ true)) |
| return true; |
| continue; |
| } |
| } |
| |
| return true; |
| } |
| |
| return false; |
| } |
| |
| static SILInstruction *recursivelyFindBoxOperandsPromotableToAddress( |
| SILValue Box, bool inAppliedFunction, SmallVectorImpl<Operand *> &, |
| SmallPtrSetImpl<SILFunction *> &, unsigned CurrentRecurDepth); |
| |
| /// checkLocalApplyBody - Check the body of an apply's callee to see |
| /// if the box pointer argument passed to it has uses that would |
| /// disqualify it from being promoted to a stack location. Return |
| /// true if this apply will not block our promoting the box. |
| static bool checkLocalApplyBody(Operand *O, |
| SmallVectorImpl<Operand *> &PromotedOperands, |
| SmallPtrSetImpl<SILFunction *> &VisitedCallees, |
| unsigned CurrentRecurDepth) { |
| SILFunction *F = ApplySite(O->getUser()).getReferencedFunctionOrNull(); |
| // If we cannot examine the function body, assume the worst. |
| if (!F || F->empty()) |
| return false; |
| |
| // Since this function can be called recursively while analyzing the same box, |
| // mark the callee as visited, so that we don't end up in a recursive cycle. |
| auto iter = VisitedCallees.insert(F); |
| if (!iter.second) |
| return false; |
| |
| auto calleeArg = F->getArgument(ApplySite(O->getUser()).getCalleeArgIndex(*O)); |
| auto res = !recursivelyFindBoxOperandsPromotableToAddress( |
| calleeArg, |
| /* inAppliedFunction = */ true, PromotedOperands, VisitedCallees, |
| CurrentRecurDepth + 1); |
| return res; |
| } |
| |
| // Returns true if a callee is eligible to be cloned and rewritten for |
| // AllocBoxToStack opt. We don't want to increase code size, so this is |
| // restricted only for private local functions currently. |
| static bool isOptimizableApplySite(ApplySite Apply) { |
| if (!AllocBoxToStackAnalyzeApply) { |
| // turned off explicitly |
| return false; |
| } |
| auto callee = Apply.getReferencedFunctionOrNull(); |
| if (!callee) { |
| return false; |
| } |
| |
| // Callee should be optimizable. |
| if (!callee->shouldOptimize()) |
| return false; |
| |
| // External function definitions. |
| if (!callee->isDefinition()) |
| return false; |
| |
| // Do not optimize always_inlinable functions. |
| if (callee->getInlineStrategy() == Inline_t::AlwaysInline) |
| return false; |
| |
| if (callee->getLinkage() != SILLinkage::Private) |
| return false; |
| |
| return true; |
| } |
| |
| /// Validate that the uses of a pointer to a box do not eliminate it from |
| /// consideration for promotion to a stack element. Return the instruction with |
| /// the unexpected use if we find one. |
| /// If a box has ApplySite users, we recursively examine the callees to check |
| /// for unexpected use of the box argument. If all the callees through which the |
| /// box is passed don't have any unexpected uses, `PromotedOperands` will be |
| /// populated with the box arguments in DFS order. |
| static SILInstruction *recursivelyFindBoxOperandsPromotableToAddress( |
| SILValue Box, bool inAppliedFunction, |
| SmallVectorImpl<Operand *> &PromotedOperands, |
| SmallPtrSetImpl<SILFunction *> &VisitedCallees, |
| unsigned CurrentRecurDepth = 0) { |
| assert((Box->getType().is<SILBoxType>() |
| || Box->getType() |
| == SILType::getNativeObjectType(Box->getType().getASTContext())) |
| && "Expected an object pointer!"); |
| |
| SmallVector<Operand *, 4> LocalPromotedOperands; |
| |
| // Scan all of the uses of the retain count value, collecting all |
| // the releases and validating that we don't have an unexpected |
| // user. |
| SmallVector<Operand *, 32> Worklist(Box->use_begin(), Box->use_end()); |
| while (!Worklist.empty()) { |
| auto *Op = Worklist.pop_back_val(); |
| auto *User = Op->getUser(); |
| |
| // Retains and releases are fine. Deallocs are fine if we're not |
| // examining a function that the alloc_box was passed into. |
| // Projections are fine as well. |
| if (isa<StrongRetainInst>(User) || isa<StrongReleaseInst>(User) || |
| isa<ProjectBoxInst>(User) || isa<DestroyValueInst>(User) || |
| (!inAppliedFunction && isa<DeallocBoxInst>(User))) |
| continue; |
| |
| // If our user instruction is a copy_value or a mark_uninitialized, visit |
| // the users recursively. |
| if (isa<MarkUninitializedInst>(User) || isa<CopyValueInst>(User)) { |
| llvm::copy(cast<SingleValueInstruction>(User)->getUses(), |
| std::back_inserter(Worklist)); |
| continue; |
| } |
| |
| if (auto Apply = ApplySite::isa(User)) { |
| if (CurrentRecurDepth > MaxLocalApplyRecurDepth) { |
| return User; |
| } |
| switch (Apply.getKind()) { |
| case ApplySiteKind::PartialApplyInst: { |
| if (checkLocalApplyBody(Op, LocalPromotedOperands, VisitedCallees, |
| CurrentRecurDepth) && |
| !partialApplyEscapes(cast<PartialApplyInst>(User), |
| /* examineApply = */ true)) { |
| LocalPromotedOperands.push_back(Op); |
| continue; |
| } |
| break; |
| } |
| case ApplySiteKind::ApplyInst: |
| case ApplySiteKind::BeginApplyInst: |
| case ApplySiteKind::TryApplyInst: |
| if (isOptimizableApplySite(Apply) && |
| checkLocalApplyBody(Op, LocalPromotedOperands, VisitedCallees, |
| CurrentRecurDepth)) { |
| LocalPromotedOperands.push_back(Op); |
| continue; |
| } |
| } |
| } |
| |
| return User; |
| } |
| |
| PromotedOperands.append(LocalPromotedOperands.begin(), |
| LocalPromotedOperands.end()); |
| return nullptr; |
| } |
| |
| template <typename... T, typename... U> |
| static InFlightDiagnostic diagnose(ASTContext &Context, SourceLoc loc, |
| Diag<T...> diag, U &&... args) { |
| return Context.Diags.diagnose(loc, diag, std::forward<U>(args)...); |
| } |
| |
| /// canPromoteAllocBox - Can we promote this alloc_box to an alloc_stack? |
| static bool canPromoteAllocBox(AllocBoxInst *ABI, |
| SmallVectorImpl<Operand *> &PromotedOperands) { |
| SmallPtrSet<SILFunction *, 8> VisitedCallees; |
| // Scan all of the uses of the address of the box to see if any |
| // disqualifies the box from being promoted to the stack. |
| if (auto *User = recursivelyFindBoxOperandsPromotableToAddress( |
| ABI, |
| /* inAppliedFunction = */ false, PromotedOperands, VisitedCallees, |
| /* CurrentRecurDepth = */ 0)) { |
| (void)User; |
| // Otherwise, we have an unexpected use. |
| LLVM_DEBUG(llvm::dbgs() << "*** Failed to promote alloc_box in @" |
| << ABI->getFunction()->getName() << ": " << *ABI |
| << " Due to user: " << *User << "\n"); |
| |
| // Check if the vardecl has a "boxtostack.mustbeonstack" attribute. If so, |
| // emit a diagnostic. |
| if (auto *decl = ABI->getDecl()) { |
| if (decl->hasSemanticsAttr("boxtostack.mustbeonstack")) { |
| auto allocDiag = |
| diag::box_to_stack_cannot_promote_box_to_stack_due_to_escape_alloc; |
| diagnose(ABI->getModule().getASTContext(), ABI->getLoc().getSourceLoc(), |
| allocDiag); |
| auto escapeNote = diag:: |
| box_to_stack_cannot_promote_box_to_stack_due_to_escape_location; |
| diagnose(ABI->getModule().getASTContext(), |
| User->getLoc().getSourceLoc(), escapeNote); |
| } |
| } |
| |
| return false; |
| } |
| |
| // Okay, it looks like this value doesn't escape. |
| return true; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // alloc_box Promotion |
| //===----------------------------------------------------------------------===// |
| |
| namespace { |
| // Pass context and per-function analysis results. |
| struct AllocBoxToStackState { |
| SILFunctionTransform *T; |
| bool CFGChanged = false; |
| |
| SmallVector<AllocBoxInst *, 8> Promotable; |
| SmallVector<Operand *, 8> PromotedOperands; |
| |
| AllocBoxToStackState(SILFunctionTransform *T) : T(T) {} |
| }; |
| } // anonymous namespace |
| |
| static void replaceProjectBoxUsers(SILValue HeapBox, SILValue StackBox) { |
| SmallVector<Operand *, 8> Worklist(HeapBox->use_begin(), HeapBox->use_end()); |
| while (!Worklist.empty()) { |
| auto *Op = Worklist.pop_back_val(); |
| if (auto *PBI = dyn_cast<ProjectBoxInst>(Op->getUser())) { |
| // This may result in an alloc_stack being used by begin_access [dynamic]. |
| PBI->replaceAllUsesWith(StackBox); |
| continue; |
| } |
| |
| auto *CVI = dyn_cast<CopyValueInst>(Op->getUser()); |
| if (!CVI) |
| continue; |
| llvm::copy(CVI->getUses(), std::back_inserter(Worklist)); |
| } |
| } |
| |
| /// rewriteAllocBoxAsAllocStack - Replace uses of the alloc_box with a |
| /// new alloc_stack, but do not delete the alloc_box yet. |
| static bool rewriteAllocBoxAsAllocStack(AllocBoxInst *ABI) { |
| LLVM_DEBUG(llvm::dbgs() << "*** Promoting alloc_box to stack: " << *ABI); |
| |
| SILValue HeapBox = ABI; |
| Optional<MarkUninitializedInst::Kind> Kind; |
| if (HeapBox->hasOneUse()) { |
| auto *User = HeapBox->getSingleUse()->getUser(); |
| if (auto *MUI = dyn_cast<MarkUninitializedInst>(User)) { |
| HeapBox = MUI; |
| Kind = MUI->getMarkUninitializedKind(); |
| } |
| } |
| |
| SmallVector<SILInstruction *, 4> FinalReleases; |
| if (!getFinalReleases(HeapBox, FinalReleases)) |
| return false; |
| |
| // Promote this alloc_box to an alloc_stack. Insert the alloc_stack |
| // at the beginning of the function. |
| SILBuilderWithScope Builder(ABI); |
| assert(ABI->getBoxType()->getLayout()->getFields().size() == 1 |
| && "rewriting multi-field box not implemented"); |
| auto *ASI = Builder.createAllocStack( |
| ABI->getLoc(), |
| getSILBoxFieldType(TypeExpansionContext(*ABI->getFunction()), |
| ABI->getBoxType(), ABI->getModule().Types, 0), |
| ABI->getVarInfo(), ABI->hasDynamicLifetime()); |
| |
| // Transfer a mark_uninitialized if we have one. |
| SILValue StackBox = ASI; |
| if (Kind) { |
| StackBox = |
| Builder.createMarkUninitialized(ASI->getLoc(), ASI, Kind.getValue()); |
| } |
| |
| // Replace all uses of the address of the box's contained value with |
| // the address of the stack location. |
| replaceProjectBoxUsers(HeapBox, StackBox); |
| |
| assert(ABI->getBoxType()->getLayout()->getFields().size() == 1 |
| && "promoting multi-field box not implemented"); |
| auto &Lowering = ABI->getFunction()->getTypeLowering( |
| getSILBoxFieldType(TypeExpansionContext(*ABI->getFunction()), |
| ABI->getBoxType(), ABI->getModule().Types, 0)); |
| auto Loc = CleanupLocation::get(ABI->getLoc()); |
| |
| for (auto LastRelease : FinalReleases) { |
| SILBuilderWithScope Builder(LastRelease); |
| if (!isa<DeallocBoxInst>(LastRelease)&& !Lowering.isTrivial()) { |
| // For non-trivial types, insert destroys for each final release-like |
| // instruction we found that isn't an explicit dealloc_box. |
| Builder.emitDestroyAddrAndFold(Loc, StackBox); |
| } |
| Builder.createDeallocStack(Loc, ASI); |
| } |
| |
| // Remove any retain and release instructions. Since all uses of project_box |
| // are gone, this only walks through uses of the box itself (the retain count |
| // pointer). |
| SmallVector<SILInstruction *, 8> Worklist; |
| std::transform(ABI->use_begin(), ABI->use_end(), std::back_inserter(Worklist), |
| [](Operand *Op) -> SILInstruction * { return Op->getUser(); }); |
| while (!Worklist.empty()) { |
| auto *User = Worklist.pop_back_val(); |
| |
| // Look through any mark_uninitialized, copy_values. |
| if (isa<MarkUninitializedInst>(User) || isa<CopyValueInst>(User)) { |
| auto Inst = cast<SingleValueInstruction>(User); |
| llvm::transform(Inst->getUses(), std::back_inserter(Worklist), |
| [](Operand *Op) -> SILInstruction * { |
| return Op->getUser(); |
| }); |
| Inst->replaceAllUsesWithUndef(); |
| Inst->eraseFromParent(); |
| continue; |
| } |
| |
| assert(isa<StrongReleaseInst>(User) || isa<StrongRetainInst>(User) || |
| isa<DeallocBoxInst>(User) || isa<ProjectBoxInst>(User) || |
| isa<DestroyValueInst>(User)); |
| |
| User->eraseFromParent(); |
| } |
| |
| return true; |
| } |
| |
| namespace { |
| |
| /// A SILCloner subclass which clones a closure function while |
| /// promoting some of its box parameters to stack addresses. |
| class PromotedParamCloner : public SILClonerWithScopes<PromotedParamCloner> { |
| friend class SILInstructionVisitor<PromotedParamCloner>; |
| friend class SILCloner<PromotedParamCloner>; |
| |
| SILFunction *Orig; |
| ArgIndexList &PromotedArgIndices; |
| SmallVector<SILValue, 4> NewPromotedArgs; |
| |
| // The values in the original function that are promoted to stack |
| // references. |
| SmallPtrSet<SILValue, 4> OrigPromotedParameters; |
| |
| public: |
| PromotedParamCloner(SILOptFunctionBuilder &FuncBuilder, SILFunction *Orig, |
| IsSerialized_t Serialized, |
| ArgIndexList &PromotedArgIndices, StringRef ClonedName); |
| |
| void populateCloned(); |
| |
| SILFunction *getCloned() { return &getBuilder().getFunction(); } |
| |
| private: |
| static SILFunction *initCloned(SILOptFunctionBuilder &FuncBuilder, |
| SILFunction *Orig, IsSerialized_t Serialized, |
| ArgIndexList &PromotedArgIndices, |
| StringRef ClonedName); |
| |
| void visitStrongReleaseInst(StrongReleaseInst *Inst); |
| void visitDestroyValueInst(DestroyValueInst *Inst); |
| void visitStrongRetainInst(StrongRetainInst *Inst); |
| void visitCopyValueInst(CopyValueInst *Inst); |
| void visitProjectBoxInst(ProjectBoxInst *Inst); |
| void checkNoPromotedBoxInApply(ApplySite Apply); |
| #define APPLYSITE_INST(Name, Parent) void visit##Name(Name *Inst); |
| #include "swift/SIL/SILNodes.def" |
| }; |
| } // end anonymous namespace |
| |
| PromotedParamCloner::PromotedParamCloner(SILOptFunctionBuilder &FuncBuilder, |
| SILFunction *Orig, |
| IsSerialized_t Serialized, |
| ArgIndexList &PromotedArgIndices, |
| StringRef ClonedName) |
| : SILClonerWithScopes<PromotedParamCloner>(*initCloned( |
| FuncBuilder, Orig, Serialized, PromotedArgIndices, ClonedName)), |
| Orig(Orig), PromotedArgIndices(PromotedArgIndices) { |
| NewPromotedArgs.reserve(PromotedArgIndices.size()); |
| assert(Orig->getDebugScope()->getParentFunction() != |
| getCloned()->getDebugScope()->getParentFunction()); |
| } |
| |
| static std::string getClonedName(SILFunction *F, IsSerialized_t Serialized, |
| ArgIndexList &PromotedArgIndices) { |
| auto P = Demangle::SpecializationPass::AllocBoxToStack; |
| Mangle::FunctionSignatureSpecializationMangler Mangler(P, Serialized, F); |
| for (unsigned i : PromotedArgIndices) { |
| Mangler.setArgumentBoxToStack(i); |
| } |
| return Mangler.mangle(); |
| } |
| |
| /// Create the function corresponding to the clone of the |
| /// original closure with the signature modified to reflect promoted |
| /// parameters (which are specified by PromotedArgIndices). |
| SILFunction *PromotedParamCloner::initCloned(SILOptFunctionBuilder &FuncBuilder, |
| SILFunction *Orig, |
| IsSerialized_t Serialized, |
| ArgIndexList &PromotedArgIndices, |
| StringRef ClonedName) { |
| SILModule &M = Orig->getModule(); |
| |
| SmallVector<SILParameterInfo, 4> ClonedInterfaceArgTys; |
| |
| // Generate a new parameter list with deleted parameters removed. |
| SILFunctionType *OrigFTI = Orig->getLoweredFunctionType(); |
| unsigned Index = Orig->getConventions().getSILArgIndexOfFirstParam(); |
| for (auto ¶m : OrigFTI->getParameters()) { |
| if (count(PromotedArgIndices, Index)) { |
| auto boxTy = param.getSILStorageInterfaceType().castTo<SILBoxType>(); |
| assert(boxTy->getLayout()->getFields().size() == 1 |
| && "promoting compound box not implemented"); |
| SILType paramTy; |
| { |
| auto &TC = Orig->getModule().Types; |
| paramTy = getSILBoxFieldType(TypeExpansionContext(*Orig), boxTy, TC, 0); |
| } |
| auto promotedParam = SILParameterInfo(paramTy.getASTType(), |
| ParameterConvention::Indirect_InoutAliasable); |
| ClonedInterfaceArgTys.push_back(promotedParam); |
| } else { |
| ClonedInterfaceArgTys.push_back(param); |
| } |
| ++Index; |
| } |
| |
| // Create the new function type for the cloned function with some of |
| // the parameters promoted. |
| auto ClonedTy = SILFunctionType::get( |
| OrigFTI->getInvocationGenericSignature(), OrigFTI->getExtInfo(), |
| OrigFTI->getCoroutineKind(), OrigFTI->getCalleeConvention(), |
| ClonedInterfaceArgTys, OrigFTI->getYields(), OrigFTI->getResults(), |
| OrigFTI->getOptionalErrorResult(), OrigFTI->getPatternSubstitutions(), |
| OrigFTI->getInvocationSubstitutions(), M.getASTContext(), |
| OrigFTI->getWitnessMethodConformanceOrInvalid()); |
| |
| assert((Orig->isTransparent() || Orig->isBare() || Orig->getLocation()) |
| && "SILFunction missing location"); |
| assert((Orig->isTransparent() || Orig->isBare() || Orig->getDebugScope()) |
| && "SILFunction missing DebugScope"); |
| assert(!Orig->isGlobalInit() && "Global initializer cannot be cloned"); |
| auto *Fn = FuncBuilder.createFunction( |
| swift::getSpecializedLinkage(Orig, Orig->getLinkage()), ClonedName, |
| ClonedTy, Orig->getGenericEnvironment(), Orig->getLocation(), |
| Orig->isBare(), Orig->isTransparent(), Serialized, IsNotDynamic, |
| Orig->getEntryCount(), Orig->isThunk(), Orig->getClassSubclassScope(), |
| Orig->getInlineStrategy(), Orig->getEffectsKind(), Orig, |
| Orig->getDebugScope()); |
| for (auto &Attr : Orig->getSemanticsAttrs()) { |
| Fn->addSemanticsAttr(Attr); |
| } |
| if (!Orig->hasOwnership()) { |
| Fn->setOwnershipEliminated(); |
| } |
| return Fn; |
| } |
| |
| /// Populate the body of the cloned closure, modifying instructions as |
| /// necessary to take into consideration the removed parameters. |
| void |
| PromotedParamCloner::populateCloned() { |
| SILFunction *Cloned = getCloned(); |
| |
| // Create arguments for the entry block |
| SILBasicBlock *OrigEntryBB = &*Orig->begin(); |
| SILBasicBlock *ClonedEntryBB = Cloned->createBasicBlock(); |
| |
| SmallVector<SILValue, 4> entryArgs; |
| entryArgs.reserve(OrigEntryBB->getArguments().size()); |
| |
| // Initialize all NewPromotedArgs slots to an invalid value. |
| NewPromotedArgs.resize(OrigEntryBB->getArguments().size()); |
| |
| unsigned ArgNo = 0; |
| auto I = OrigEntryBB->args_begin(), E = OrigEntryBB->args_end(); |
| while (I != E) { |
| if (count(PromotedArgIndices, ArgNo)) { |
| // Create a new argument with the promoted type. |
| auto boxTy = (*I)->getType().castTo<SILBoxType>(); |
| assert(boxTy->getLayout()->getFields().size() == 1 |
| && "promoting multi-field boxes not implemented yet"); |
| auto promotedTy = getSILBoxFieldType(TypeExpansionContext(*Cloned), boxTy, |
| Cloned->getModule().Types, 0); |
| auto *promotedArg = |
| ClonedEntryBB->createFunctionArgument(promotedTy, (*I)->getDecl()); |
| OrigPromotedParameters.insert(*I); |
| |
| NewPromotedArgs[ArgNo] = promotedArg; |
| // We only promote boxes used in apply or projections or copy/destroy |
| // value operations. |
| // We should never see an apply user of the box, because we rewrite the |
| // applies and specialize the callees in dfs order. |
| // Projection users are folded when visited and copy/destroy operations |
| // are ignored. |
| entryArgs.push_back(SILValue()); |
| } else { |
| // Create a new argument which copies the original argument. |
| entryArgs.push_back(ClonedEntryBB->createFunctionArgument( |
| (*I)->getType(), (*I)->getDecl())); |
| } |
| ++ArgNo; |
| ++I; |
| } |
| |
| // Visit original BBs in depth-first preorder, starting with the |
| // entry block, cloning all instructions and terminators. |
| cloneFunctionBody(Orig, ClonedEntryBB, entryArgs); |
| } |
| |
| /// Handle a strong_release instruction during cloning of a closure; if |
| /// it is a strong release of a promoted box argument, then it is replaced with |
| /// a ReleaseValue of the new object type argument, otherwise it is handled |
| /// normally. |
| void |
| PromotedParamCloner::visitStrongReleaseInst(StrongReleaseInst *Inst) { |
| // If it's a release of a promoted parameter, just drop the instruction. |
| if (OrigPromotedParameters.count(Inst->getOperand())) |
| return; |
| |
| SILCloner<PromotedParamCloner>::visitStrongReleaseInst(Inst); |
| } |
| |
| /// Handle a strong_release instruction during cloning of a closure; if |
| /// it is a strong release of a promoted box argument, then it is replaced with |
| /// a ReleaseValue of the new object type argument, otherwise it is handled |
| /// normally. |
| void PromotedParamCloner::visitDestroyValueInst(DestroyValueInst *Inst) { |
| // If we are a destroy of a promoted parameter, just drop the instruction. We |
| // look through copy_value to preserve current behavior. |
| SILInstruction *Tmp = Inst; |
| while (auto *CopyOp = dyn_cast<CopyValueInst>(Tmp->getOperand(0))) { |
| Tmp = CopyOp; |
| } |
| |
| if (OrigPromotedParameters.count(Tmp->getOperand(0))) |
| return; |
| |
| SILCloner<PromotedParamCloner>::visitDestroyValueInst(Inst); |
| } |
| |
| void |
| PromotedParamCloner::visitStrongRetainInst(StrongRetainInst *Inst) { |
| // If it's a retain of a promoted parameter, just drop the instruction. |
| if (OrigPromotedParameters.count(Inst->getOperand())) |
| return; |
| |
| SILCloner<PromotedParamCloner>::visitStrongRetainInst(Inst); |
| } |
| |
| void PromotedParamCloner::visitCopyValueInst(CopyValueInst *cvi) { |
| // If it's a copy of a promoted parameter, just drop the instruction. |
| auto *tmp = cvi; |
| while (auto *copyOp = dyn_cast<CopyValueInst>(tmp->getOperand())) { |
| tmp = copyOp; |
| } |
| if (OrigPromotedParameters.count(tmp->getOperand())) |
| return; |
| |
| SILCloner<PromotedParamCloner>::visitCopyValueInst(cvi); |
| } |
| |
| void PromotedParamCloner::visitProjectBoxInst(ProjectBoxInst *pbi) { |
| // If it's a projection of a promoted parameter (or a copy_value of a promoted |
| // parameter), drop the instruction. Its uses will be replaced by the |
| // promoted address. |
| SILValue box = pbi->getOperand(); |
| while (auto *copyOp = dyn_cast<CopyValueInst>(box)) { |
| box = copyOp->getOperand(); |
| } |
| if (OrigPromotedParameters.count(box)) { |
| auto *origArg = cast<SILFunctionArgument>(box); |
| recordFoldedValue(pbi, NewPromotedArgs[origArg->getIndex()]); |
| return; |
| } |
| |
| SILCloner<PromotedParamCloner>::visitProjectBoxInst(pbi); |
| } |
| |
| // While cloning during specialization, make sure apply instructions do not have |
| // box arguments that need to be promoted. |
| // This is an assertion in debug builds only. The reason why this should never |
| // be true is that we have cloned our callees in DFS order meaning that any of |
| // our callees that had a promotable box will have already have been promoted |
| // away by the time this runs. |
| void PromotedParamCloner::checkNoPromotedBoxInApply(ApplySite Apply) { |
| #ifndef NDEBUG |
| for (auto &O : Apply.getArgumentOperands()) { |
| assert(OrigPromotedParameters.count(O.get()) == 0); |
| } |
| #endif |
| } |
| void PromotedParamCloner::visitApplyInst(ApplyInst *Inst) { |
| checkNoPromotedBoxInApply(Inst); |
| SILCloner<PromotedParamCloner>::visitApplyInst(Inst); |
| } |
| void PromotedParamCloner::visitBeginApplyInst(BeginApplyInst *Inst) { |
| checkNoPromotedBoxInApply(Inst); |
| SILCloner<PromotedParamCloner>::visitBeginApplyInst(Inst); |
| } |
| void PromotedParamCloner::visitPartialApplyInst(PartialApplyInst *Inst) { |
| checkNoPromotedBoxInApply(Inst); |
| SILCloner<PromotedParamCloner>::visitPartialApplyInst(Inst); |
| } |
| void PromotedParamCloner::visitTryApplyInst(TryApplyInst *Inst) { |
| checkNoPromotedBoxInApply(Inst); |
| SILCloner<PromotedParamCloner>::visitTryApplyInst(Inst); |
| } |
| |
| /// Specialize ApplySite by promoting the parameters indicated by |
| /// indices. We expect these parameters to be replaced by stack address |
| /// references. |
| static SILInstruction * |
| specializeApplySite(SILOptFunctionBuilder &FuncBuilder, ApplySite Apply, |
| ArgIndexList &PromotedCalleeArgIndices, |
| AllocBoxToStackState &pass) { |
| auto *FRI = cast<FunctionRefInst>(Apply.getCallee()); |
| assert(FRI && "Expected a direct ApplySite"); |
| auto *F = FRI->getReferencedFunctionOrNull(); |
| assert(F && "Expected a referenced function!"); |
| |
| IsSerialized_t Serialized = IsNotSerialized; |
| if (Apply.getFunction()->isSerialized()) |
| Serialized = IsSerializable; |
| |
| std::string ClonedName = |
| getClonedName(F, Serialized, PromotedCalleeArgIndices); |
| |
| auto &M = Apply.getModule(); |
| |
| SILFunction *ClonedFn; |
| if (auto *PrevFn = M.lookUpFunction(ClonedName)) { |
| assert(PrevFn->isSerialized() == Serialized); |
| ClonedFn = PrevFn; |
| } else { |
| // Clone the function the existing ApplySite references. |
| PromotedParamCloner Cloner(FuncBuilder, F, Serialized, |
| PromotedCalleeArgIndices, |
| ClonedName); |
| Cloner.populateCloned(); |
| ClonedFn = Cloner.getCloned(); |
| pass.T->addFunctionToPassManagerWorklist(ClonedFn, F); |
| } |
| |
| // Now create the new ApplySite using the cloned function. |
| SmallVector<SILValue, 16> Args; |
| |
| ValueLifetimeAnalysis::Frontier PAFrontier; |
| |
| // Promote the arguments that need promotion. |
| for (auto &O : Apply.getArgumentOperands()) { |
| auto CalleeArgIndex = ApplySite(O.getUser()).getCalleeArgIndex(O); |
| if (!count(PromotedCalleeArgIndices, CalleeArgIndex)) { |
| Args.push_back(O.get()); |
| continue; |
| } |
| |
| SILValue Box = O.get(); |
| assert((isa<SingleValueInstruction>(Box) && isa<AllocBoxInst>(Box) || |
| isa<CopyValueInst>(Box) || |
| isa<SILFunctionArgument>(Box)) && |
| "Expected either an alloc box or a copy of an alloc box or a " |
| "function argument"); |
| SILBuilderWithScope::insertAfter(Box, [&](SILBuilder &B) { |
| Args.push_back(B.createProjectBox(Box.getLoc(), Box, 0)); |
| }); |
| |
| // For a partial_apply, if this argument is promoted, it is a box that we're |
| // turning into an address because we've proven we can keep this value on |
| // the stack. The partial_apply had ownership of this box so we must now |
| // release it explicitly when the partial_apply is released. |
| if (Apply.getKind() == ApplySiteKind::PartialApplyInst) { |
| if (PAFrontier.empty()) { |
| auto *PAI = cast<PartialApplyInst>(Apply); |
| ValueLifetimeAnalysis VLA(PAI, PAI->getUses()); |
| pass.CFGChanged |= !VLA.computeFrontier( |
| PAFrontier, ValueLifetimeAnalysis::AllowToModifyCFG); |
| assert(!PAFrontier.empty() && |
| "partial_apply must have at least one use " |
| "to release the returned function"); |
| } |
| |
| // Insert destroys of the box at each point where the partial_apply |
| // becomes dead. |
| for (SILInstruction *FrontierInst : PAFrontier) { |
| SILBuilderWithScope Builder(FrontierInst); |
| Builder.emitDestroyValueOperation(Apply.getLoc(), Box); |
| } |
| } |
| } |
| |
| auto ApplyInst = Apply.getInstruction(); |
| SILBuilderWithScope Builder(ApplyInst); |
| |
| // Build the function_ref and ApplySite. |
| SILValue FunctionRef = Builder.createFunctionRef(Apply.getLoc(), ClonedFn); |
| switch (Apply.getKind()) { |
| case ApplySiteKind::PartialApplyInst: { |
| auto *PAI = cast<PartialApplyInst>(ApplyInst); |
| return Builder.createPartialApply( |
| Apply.getLoc(), FunctionRef, Apply.getSubstitutionMap(), Args, |
| PAI->getType().getAs<SILFunctionType>()->getCalleeConvention(), |
| PAI->isOnStack(), |
| GenericSpecializationInformation::create(ApplyInst, Builder)); |
| } |
| case ApplySiteKind::ApplyInst: |
| return Builder.createApply( |
| Apply.getLoc(), FunctionRef, Apply.getSubstitutionMap(), Args, |
| GenericSpecializationInformation::create(ApplyInst, Builder)); |
| case ApplySiteKind::BeginApplyInst: |
| return Builder.createBeginApply( |
| Apply.getLoc(), FunctionRef, Apply.getSubstitutionMap(), Args, |
| GenericSpecializationInformation::create(ApplyInst, Builder)); |
| case ApplySiteKind::TryApplyInst: { |
| auto TAI = cast<TryApplyInst>(Apply); |
| return Builder.createTryApply( |
| Apply.getLoc(), FunctionRef, Apply.getSubstitutionMap(), Args, |
| TAI->getNormalBB(), TAI->getErrorBB(), |
| GenericSpecializationInformation::create(ApplyInst, Builder)); |
| } |
| } |
| llvm_unreachable("unhandled apply inst kind!"); |
| } |
| |
| static void rewriteApplySites(AllocBoxToStackState &pass) { |
| swift::SmallBlotMapVector<ApplySite, ArgIndexList, 8> AppliesToSpecialize; |
| ArgIndexList Indices; |
| |
| // Build a map from the ApplySite to the indices of the operands |
| // that will be promoted in our rewritten version. |
| for (auto *O : pass.PromotedOperands) { |
| auto User = O->getUser(); |
| auto Apply = ApplySite(User); |
| |
| auto CalleeArgIndexNumber = Apply.getCalleeArgIndex(*O); |
| |
| Indices.clear(); |
| Indices.push_back(CalleeArgIndexNumber); |
| |
| // AllocBoxStack opt promotes boxes passed to a chain of applies when it is |
| // safe to do so. All such applies have to be specialized to take pointer |
| // arguments instead of box arguments. This has to be done in dfs order. |
| |
| // PromotedOperands is already populated in dfs order by |
| // `recursivelyFindBoxOperandsPromotableToAddress` w.r.t a single alloc_box. |
| // AppliesToSpecialize is then populated in the order of PromotedOperands. |
| // If multiple alloc_boxes are passed to the same apply instruction, then |
| // the apply instruction can appear multiple times in AppliesToSpecialize. |
| // Only its last appearance is maintained and previous appearances are |
| // blotted. |
| auto iterAndSuccess = |
| AppliesToSpecialize.insert(std::make_pair(Apply, Indices)); |
| if (!iterAndSuccess.second) { |
| // Blot the previously inserted apply and insert at the end with updated |
| // indices |
| auto OldIndices = iterAndSuccess.first->getValue().second; |
| OldIndices.push_back(CalleeArgIndexNumber); |
| AppliesToSpecialize.erase(iterAndSuccess.first); |
| AppliesToSpecialize.insert(std::make_pair(Apply, OldIndices)); |
| } |
| } |
| |
| // Clone the referenced function of each ApplySite, removing the |
| // operands that we will not need, and remove the existing |
| // ApplySite. |
| SILOptFunctionBuilder FuncBuilder(*pass.T); |
| for (auto &It : AppliesToSpecialize) { |
| if (!It.hasValue()) { |
| continue; |
| } |
| auto Apply = It.getValue().first; |
| auto Indices = It.getValue().second; |
| // Sort the indices and unique them. |
| sortUnique(Indices); |
| |
| auto *Replacement = specializeApplySite(FuncBuilder, Apply, Indices, pass); |
| assert(Apply.getKind() == ApplySite(Replacement).getKind()); |
| Apply.getInstruction()->replaceAllUsesPairwiseWith(Replacement); |
| |
| auto *FRI = cast<FunctionRefInst>(Apply.getCallee()); |
| Apply.getInstruction()->eraseFromParent(); |
| |
| // TODO: Erase from module if there are no more uses. |
| if (FRI->use_empty()) |
| FRI->eraseFromParent(); |
| } |
| } |
| |
| /// Clone closure bodies and rewrite partial applies. Returns the number of |
| /// alloc_box allocations promoted. |
| static unsigned rewritePromotedBoxes(AllocBoxToStackState &pass) { |
| // First we'll rewrite any ApplySite that we can to remove |
| // the box container pointer from the operands. |
| rewriteApplySites(pass); |
| |
| unsigned Count = 0; |
| auto rend = pass.Promotable.rend(); |
| for (auto I = pass.Promotable.rbegin(); I != rend; ++I) { |
| auto *ABI = *I; |
| if (rewriteAllocBoxAsAllocStack(ABI)) { |
| ++Count; |
| ABI->eraseFromParent(); |
| } |
| } |
| return Count; |
| } |
| |
| namespace { |
| class AllocBoxToStack : public SILFunctionTransform { |
| /// The entry point to the transformation. |
| void run() override { |
| // Don't rerun on deserialized functions. Nothing should have changed. |
| if (getFunction()->wasDeserializedCanonical()) |
| return; |
| |
| AllocBoxToStackState pass(this); |
| for (auto &BB : *getFunction()) { |
| for (auto &I : BB) |
| if (auto *ABI = dyn_cast<AllocBoxInst>(&I)) |
| if (canPromoteAllocBox(ABI, pass.PromotedOperands)) |
| pass.Promotable.push_back(ABI); |
| } |
| |
| if (!pass.Promotable.empty()) { |
| auto Count = rewritePromotedBoxes(pass); |
| NumStackPromoted += Count; |
| if (Count) { |
| StackNesting SN; |
| if (SN.correctStackNesting(getFunction()) == StackNesting::Changes::CFG) |
| pass.CFGChanged = true; |
| } |
| |
| invalidateAnalysis( |
| pass.CFGChanged |
| ? SILAnalysis::InvalidationKind::FunctionBody |
| : SILAnalysis::InvalidationKind::CallsAndInstructions); |
| } |
| } |
| }; |
| } // end anonymous namespace |
| |
| SILTransform *swift::createAllocBoxToStack() { |
| return new AllocBoxToStack(); |
| } |