averello/swift-mirror
1
0
Fork 0
mirror of https://github.com/apple/swift.git synced 2025-12-14 20:36:38 +01:00
Code Issues Packages Projects Releases Wiki Activity
Files
constraintResolutionFix
swift-mirror/lib/SILOptimizer/Mandatory/CapturePromotion.cpp
Andrew Trick e7000e4668 SIL: Add mark_dependence_addr
2025-03-25 23:02:42 -07:00

1661 lines
63 KiB
C++
Raw Permalink Blame History

//===--- CapturePromotion.cpp - Promotes closure captures -----------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2021 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
//
//===----------------------------------------------------------------------===//
///
/// \file
///
/// Promotes captures from 'inout' (i.e. by-reference) to by-value
/// ==============================================================
///
/// Swift's closure model is that all local variables are capture by reference.
/// This produces a very simple programming model which is great to use, but
/// relies on the optimizer to promote by-ref captures to by-value (i.e.
/// by-copy) captures for decent performance. Consider this simple example:
///
/// func foo(a : () -> ()) {} // assume this has an unknown body
///
/// func bar() {
/// var x = 42
///
/// foo({ print(x) })
/// }
///
/// Since x is captured by-ref by the closure, x must live on the heap. By
/// looking at bar without any knowledge of foo, we can know that it is safe to
/// promote this to a by-value capture, allowing x to live on the stack under
/// the following conditions:
///
/// 1. If x is not modified in the closure body and is only loaded.
/// 2. If we can prove that all mutations to x occur before the closure is
/// formed.
///
/// Under these conditions if x is loadable then we can even load the given
/// value and pass it as a scalar instead of an address.
///
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "sil-capture-promotion"
#include "swift/AST/DiagnosticsSIL.h"
#include "swift/AST/GenericEnvironment.h"
#include "swift/AST/SemanticAttrs.h"
#include "swift/Basic/Assertions.h"
#include "swift/Basic/FrozenMultiMap.h"
#include "swift/SIL/OwnershipUtils.h"
#include "swift/SIL/SILCloner.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/TypeSubstCloner.h"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "swift/SILOptimizer/Utils/SILOptFunctionBuilder.h"
#include "swift/SILOptimizer/Utils/SpecializationMangler.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include <tuple>
using namespace swift;
STATISTIC(NumCapturesPromoted, "Number of captures promoted");
namespace {
using IndicesSet = llvm::SmallSet<unsigned, 4>;
using PartialApplyIndicesMap = llvm::DenseMap<PartialApplyInst *, IndicesSet>;
} // anonymous namespace
//===----------------------------------------------------------------------===//
// Reachability Utilities
//===----------------------------------------------------------------------===//
namespace {
/// Transient reference to a block set within ReachabilityInfo.
///
/// This is a bitset that conveniently flattens into a matrix allowing bit-wise
/// operations without masking.
///
/// TODO: If this sticks around, maybe we'll make a BitMatrix ADT.
class ReachingBlockSet {
public:
enum { BITWORD_SIZE = (unsigned)sizeof(uint64_t) * CHAR_BIT };
constexpr static size_t numBitWordsForNumBlocks(unsigned NumBlocks) {
return (NumBlocks + BITWORD_SIZE - 1) / BITWORD_SIZE;
}
/// Transient reference to a reaching block matrix.
struct ReachingBlockMatrix {
uint64_t *bits;
unsigned numBitWords; // Words per row.
ReachingBlockMatrix() : bits(nullptr), numBitWords(0) {}
bool empty() const { return !bits; }
};
static ReachingBlockMatrix allocateMatrix(unsigned numBlocks) {
ReachingBlockMatrix m;
m.numBitWords = numBitWordsForNumBlocks(numBlocks);
m.bits = new uint64_t[numBlocks * m.numBitWords];
memset(m.bits, 0, numBlocks * m.numBitWords * sizeof(uint64_t));
return m;
}
static void deallocateMatrix(ReachingBlockMatrix &m) {
delete[] m.bits;
m.bits = nullptr;
m.numBitWords = 0;
}
static ReachingBlockSet allocateSet(unsigned numBlocks) {
ReachingBlockSet s;
s.numBitWords = numBitWordsForNumBlocks(numBlocks);
s.bits = new uint64_t[s.numBitWords];
return s;
}
static void deallocateSet(ReachingBlockSet &s) {
delete[] s.bits;
s.bits = nullptr;
s.numBitWords = 0;
}
private:
uint64_t *bits;
unsigned numBitWords;
public:
ReachingBlockSet() : bits(nullptr), numBitWords(0) {}
ReachingBlockSet(unsigned blockID, ReachingBlockMatrix &m)
: bits(&m.bits[blockID * m.numBitWords]), numBitWords(m.numBitWords) {}
bool test(unsigned id) const {
assert(id / BITWORD_SIZE < numBitWords && "block ID out-of-bounds");
unsigned int modulus = id % BITWORD_SIZE;
long shifted = 1L << modulus;
return bits[id / BITWORD_SIZE] & shifted;
}
void set(unsigned id) {
unsigned int modulus = id % BITWORD_SIZE;
long shifted = 1L << modulus;
assert(id / BITWORD_SIZE < numBitWords && "block ID out-of-bounds");
bits[id / BITWORD_SIZE] |= shifted;
}
ReachingBlockSet &operator|=(const ReachingBlockSet &rhs) {
for (unsigned i : range(numBitWords))
bits[i] |= rhs.bits[i];
return *this;
}
void clear() { memset(bits, 0, numBitWords * sizeof(uint64_t)); }
bool operator==(const ReachingBlockSet &rhs) const {
assert(numBitWords == rhs.numBitWords && "mismatched sets");
for (unsigned i : range(numBitWords))
if (bits[i] != rhs.bits[i])
return false;
return true;
}
bool operator!=(const ReachingBlockSet &rhs) const { return !(*this == rhs); }
ReachingBlockSet(const ReachingBlockSet &rhs)
: bits(rhs.bits), numBitWords(rhs.numBitWords) {}
const ReachingBlockSet &operator=(const ReachingBlockSet &RHS) {
assert(numBitWords == RHS.numBitWords && "mismatched sets");
for (unsigned i : range(numBitWords))
bits[i] = RHS.bits[i];
return *this;
}
};
/// Store the reachability matrix: ToBlock -> FromBlocks.
class ReachabilityInfo {
SILFunction *f;
llvm::DenseMap<SILBasicBlock *, unsigned> blockMap;
ReachingBlockSet::ReachingBlockMatrix matrix;
public:
ReachabilityInfo(SILFunction *f) : f(f) {}
~ReachabilityInfo() { ReachingBlockSet::deallocateMatrix(matrix); }
bool isComputed() const { return !matrix.empty(); }
bool isReachable(SILBasicBlock *From, SILBasicBlock *To);
private:
void compute();
};
} // end anonymous namespace
/// Compute ReachabilityInfo so that it can answer queries about
/// whether a given basic block in a function is reachable from another basic
/// block in the function.
///
/// FIXME: Computing global reachability requires initializing an N^2
/// bitset. This could be avoided by computing reachability on-the-fly
/// for each alloc_box by walking backward from mutations.
void ReachabilityInfo::compute() {
assert(!isComputed() && "already computed");
unsigned n = 0;
for (auto &block : *f)
blockMap.insert({&block, n++});
matrix = ReachingBlockSet::allocateMatrix(n);
ReachingBlockSet newSet = ReachingBlockSet::allocateSet(n);
LLVM_DEBUG(llvm::dbgs() << "Computing Reachability for " << f->getName()
<< " with " << n << " blocks.\n");
// Iterate to a fix point, two times for a topological DAG.
bool madeChange;
do {
madeChange = false;
// Visit all blocks in a predictable order, hopefully close to topological.
for (auto &block : *f) {
ReachingBlockSet curSet(blockMap[&block], matrix);
if (!madeChange) {
// If we have not detected a change yet, then calculate new
// reachabilities into a new bit vector so we can determine if any
// change has occurred.
newSet = curSet;
for (auto pi = block.pred_begin(), pe = block.pred_end(); pi != pe;
++pi) {
unsigned predID = blockMap[*pi];
ReachingBlockSet predSet(predID, matrix);
newSet |= predSet;
newSet.set(predID);
}
if (newSet != curSet) {
curSet = newSet;
madeChange = true;
}
} else {
// Otherwise, just update the existing reachabilities in-place.
for (auto *predBlock : block.getPredecessorBlocks()) {
unsigned predID = blockMap[predBlock];
ReachingBlockSet predSet(predID, matrix);
curSet |= predSet;
curSet.set(predID);
}
}
LLVM_DEBUG(llvm::dbgs()
<< " Block " << blockMap[&block] << " reached by ";
for (unsigned i
: range(n)) {
if (curSet.test(i))
llvm::dbgs() << i << " ";
} llvm::dbgs()
<< "\n");
}
} while (madeChange);
ReachingBlockSet::deallocateSet(newSet);
}
/// Return true if the To basic block is reachable from the From basic
/// block. A block is considered reachable from itself only if its entry can be
/// recursively reached from its own exit.
bool ReachabilityInfo::isReachable(SILBasicBlock *fromBlock,
SILBasicBlock *toBlock) {
if (!isComputed())
compute();
auto fi = blockMap.find(fromBlock), ti = blockMap.find(toBlock);
assert(fi != blockMap.end() && ti != blockMap.end());
ReachingBlockSet fromSet(ti->second, matrix);
return fromSet.test(fi->second);
}
//===----------------------------------------------------------------------===//
// ClosureCloner
//===----------------------------------------------------------------------===//
namespace {
/// A SILCloner subclass which clones a closure function while converting
/// one or more captures from 'inout' (by-reference) to by-value.
class ClosureCloner : public SILClonerWithScopes<ClosureCloner> {
public:
friend class SILInstructionVisitor<ClosureCloner>;
friend class SILCloner<ClosureCloner>;
ClosureCloner(SILOptFunctionBuilder &funcBuilder, SILFunction *orig,
SerializedKind_t serialized, StringRef clonedName,
IndicesSet &promotableIndices, ResilienceExpansion expansion);
void populateCloned();
SILFunction *getCloned() { return &getBuilder().getFunction(); }
static SILFunction *
constructClonedFunction(SILOptFunctionBuilder &funcBuilder,
PartialApplyInst *pai, FunctionRefInst *fri,
IndicesSet &promotableIndices,
ResilienceExpansion resilienceExpansion);
private:
static SILFunction *initCloned(SILOptFunctionBuilder &funcBuilder,
SILFunction *orig, SerializedKind_t serialized,
StringRef clonedName,
IndicesSet &promotableIndices,
ResilienceExpansion expansion);
SILValue getProjectBoxMappedVal(SILValue operandValue);
void visitDebugValueInst(DebugValueInst *inst);
void visitDestroyValueInst(DestroyValueInst *inst);
void visitStructElementAddrInst(StructElementAddrInst *inst);
void visitLoadInst(LoadInst *inst);
void visitLoadBorrowInst(LoadBorrowInst *inst);
void visitEndBorrowInst(EndBorrowInst *inst);
void visitProjectBoxInst(ProjectBoxInst *inst);
void visitBeginAccessInst(BeginAccessInst *inst);
void visitEndAccessInst(EndAccessInst *inst);
ResilienceExpansion resilienceExpansion;
SILFunction *origF;
IndicesSet &promotableIndices;
llvm::DenseMap<SILArgument *, SILValue> boxArgumentMap;
llvm::DenseMap<ProjectBoxInst *, SILValue> projectBoxArgumentMap;
};
} // end anonymous namespace
ClosureCloner::ClosureCloner(SILOptFunctionBuilder &funcBuilder,
SILFunction *orig, SerializedKind_t serialized,
StringRef clonedName,
IndicesSet &promotableIndices,
ResilienceExpansion resilienceExpansion)
: SILClonerWithScopes<ClosureCloner>(
*initCloned(funcBuilder, orig, serialized, clonedName,
promotableIndices, resilienceExpansion)),
origF(orig), promotableIndices(promotableIndices) {
assert(orig->getDebugScope()->Parent != getCloned()->getDebugScope()->Parent);
}
/// Compute the SILParameterInfo list for the new cloned closure.
///
/// Our goal as a result of this transformation is to:
///
/// 1. Let through all arguments not related to a promotable box.
/// 2. Replace container box value arguments for the cloned closure with the
/// transformed address or value argument.
static void
computeNewArgInterfaceTypes(SILFunction *f, IndicesSet &promotableIndices,
SmallVectorImpl<SILParameterInfo> &outTys,
ResilienceExpansion expansion) {
auto fnConv = f->getConventions();
auto parameters = fnConv.funcTy->getParameters();
LLVM_DEBUG(llvm::dbgs() << "Preparing New Args!\n");
auto &types = f->getModule().Types;
// For each parameter in the old function...
for (unsigned index : indices(parameters)) {
auto &param = parameters[index];
// The PromotableIndices index is expressed as the argument index (num
// indirect result + param index). Add back the num indirect results to get
// the arg index when working with PromotableIndices.
unsigned argIndex = index + fnConv.getSILArgIndexOfFirstParam();
LLVM_DEBUG(llvm::dbgs()
<< "Index: " << index << "; PromotableIndices: "
<< (promotableIndices.count(argIndex) ? "yes" : "no")
<< " Param: ";
param.print(llvm::dbgs()));
if (!promotableIndices.count(argIndex)) {
outTys.push_back(param);
continue;
}
// Perform the proper conversions and then add it to the new parameter list
// for the type.
assert(!param.isFormalIndirect());
auto paramTy =
param.getSILStorageType(fnConv.silConv.getModule(), fnConv.funcTy,
TypeExpansionContext::minimal());
auto paramBoxTy = paramTy.castTo<SILBoxType>();
assert(paramBoxTy->getLayout()->getFields().size() == 1 &&
"promoting compound box not implemented yet");
auto paramBoxedTy =
getSILBoxFieldType(TypeExpansionContext(*f), paramBoxTy, types, 0);
assert(expansion == f->getResilienceExpansion());
auto &paramTL = types.getTypeLowering(paramBoxedTy, *f);
ParameterConvention convention;
if (paramTL.isAddressOnly()) {
convention = ParameterConvention::Indirect_In;
} else if (paramTL.isTrivial()) {
convention = ParameterConvention::Direct_Unowned;
} else {
convention = param.isGuaranteedInCallee()
? ParameterConvention::Direct_Guaranteed
: ParameterConvention::Direct_Owned;
}
outTys.push_back(SILParameterInfo(paramBoxedTy.getASTType(), convention,
param.getOptions()));
}
}
static std::string getSpecializedName(SILFunction *f,
SerializedKind_t serialized,
IndicesSet &promotableIndices) {
auto p = Demangle::SpecializationPass::CapturePromotion;
Mangle::FunctionSignatureSpecializationMangler mangler(f->getASTContext(), p, serialized, f);
auto fnConv = f->getConventions();
for (unsigned argIdx = 0, endIdx = fnConv.getNumSILArguments();
argIdx < endIdx; ++argIdx) {
if (!promotableIndices.count(argIdx))
continue;
mangler.setArgumentBoxToValue(argIdx);
}
return mangler.mangle();
}
/// Create the function corresponding to the clone of the original
/// closure with the signature modified to reflect promotable captures (which
/// are given by PromotableIndices, such that each entry in the set is the
/// index of the box containing the variable in the closure's argument list, and
/// the address of the box's contents is the argument immediately following each
/// box argument); does not actually clone the body of the function
///
/// *NOTE* PromotableIndices only contains the container value of the box, not
/// the address value.
SILFunction *
ClosureCloner::initCloned(SILOptFunctionBuilder &functionBuilder,
SILFunction *orig, SerializedKind_t serialized,
StringRef clonedName, IndicesSet &promotableIndices,
ResilienceExpansion resilienceExpansion) {
SILModule &mod = orig->getModule();
// Compute the arguments for our new function.
SmallVector<SILParameterInfo, 4> clonedInterfaceArgTys;
computeNewArgInterfaceTypes(orig, promotableIndices, clonedInterfaceArgTys,
resilienceExpansion);
SILFunctionType *origFTI = orig->getLoweredFunctionType();
// Create the thin function type for the cloned closure.
auto clonedTy = SILFunctionType::get(
origFTI->getInvocationGenericSignature(), origFTI->getExtInfo(),
origFTI->getCoroutineKind(), origFTI->getCalleeConvention(),
clonedInterfaceArgTys, origFTI->getYields(), origFTI->getResults(),
origFTI->getOptionalErrorResult(),
origFTI->getPatternSubstitutions(),
origFTI->getInvocationSubstitutions(),
mod.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 = functionBuilder.createFunction(
orig->getLinkage(), clonedName, clonedTy, orig->getGenericEnvironment(),
orig->getLocation(), orig->isBare(), IsNotTransparent, serialized,
IsNotDynamic, IsNotDistributed, IsNotRuntimeAccessible,
orig->getEntryCount(), orig->isThunk(), orig->getClassSubclassScope(),
orig->getInlineStrategy(), orig->getEffectsKind(), orig,
orig->getDebugScope());
for (auto &attr : orig->getSemanticsAttrs())
fn->addSemanticsAttr(attr);
return fn;
}
/// Populate the body of the cloned closure, modifying instructions as
/// necessary to take into consideration the promoted capture(s)
void ClosureCloner::populateCloned() {
SILFunction *cloned = getCloned();
// Create arguments for the entry block
SILBasicBlock *origEntryBB = &*origF->begin();
SILBasicBlock *clonedEntryBB = cloned->createBasicBlock();
getBuilder().setInsertionPoint(clonedEntryBB);
SmallVector<SILValue, 4> entryArgs;
entryArgs.reserve(origEntryBB->getArguments().size());
unsigned argNo = 0;
auto ai = origEntryBB->args_begin(), ae = origEntryBB->args_end();
for (; ai != ae; ++argNo, ++ai) {
if (!promotableIndices.count(argNo)) {
// Simply create a new argument which copies the original argument
auto *mappedValue = clonedEntryBB->createFunctionArgument(
(*ai)->getType(), (*ai)->getDecl());
mappedValue->copyFlags(cast<SILFunctionArgument>(*ai));
entryArgs.push_back(mappedValue);
continue;
}
// Handle the case of a promoted capture argument.
auto boxTy = (*ai)->getType().castTo<SILBoxType>();
assert(boxTy->getLayout()->getFields().size() == 1 &&
"promoting compound box not implemented");
auto boxedTy = getSILBoxFieldType(TypeExpansionContext(*cloned), boxTy,
cloned->getModule().Types, 0)
.getObjectType();
auto *newArg =
clonedEntryBB->createFunctionArgument(boxedTy, (*ai)->getDecl());
newArg->copyFlags(cast<SILFunctionArgument>(*ai));
SILValue mappedValue = newArg;
// If SIL ownership is enabled, we need to perform a borrow here if we have
// a non-trivial value. We know that our value is not written to and it does
// not escape. The use of a borrow enforces this.
if (mappedValue->getOwnershipKind() != OwnershipKind::None) {
SILLocation loc(const_cast<ValueDecl *>((*ai)->getDecl()));
mappedValue = getBuilder().emitBeginBorrowOperation(loc, mappedValue);
}
entryArgs.push_back(mappedValue);
boxArgumentMap.insert(std::make_pair(*ai, mappedValue));
// Track the projections of the box.
for (auto *use : (*ai)->getUses()) {
if (auto *pbi = dyn_cast<ProjectBoxInst>(use->getUser())) {
projectBoxArgumentMap.insert(std::make_pair(pbi, mappedValue));
}
}
}
// Visit original BBs in depth-first preorder, starting with the
// entry block, cloning all instructions and terminators.
cloneFunctionBody(origF, clonedEntryBB, entryArgs);
}
SILFunction *ClosureCloner::constructClonedFunction(
SILOptFunctionBuilder &funcBuilder, PartialApplyInst *pai,
FunctionRefInst *fri, IndicesSet &promotableIndices,
ResilienceExpansion resilienceExpansion) {
SILFunction *f = pai->getFunction();
// Create the Cloned Name for the function.
SILFunction *origF = fri->getReferencedFunction();
SerializedKind_t serializedKind = f->getSerializedKind();
auto clonedName = getSpecializedName(origF, serializedKind, promotableIndices);
// If we already have such a cloned function in the module then just use it.
if (auto *prevF = f->getModule().lookUpFunction(clonedName)) {
assert(prevF->getSerializedKind() == serializedKind);
return prevF;
}
// Otherwise, create a new clone.
ClosureCloner cloner(funcBuilder, origF, serializedKind, clonedName,
promotableIndices, resilienceExpansion);
cloner.populateCloned();
return cloner.getCloned();
}
/// If this operand originates from a mapped ProjectBox, return the mapped
/// value. Otherwise return an invalid value.
SILValue ClosureCloner::getProjectBoxMappedVal(SILValue operandValue) {
if (auto *bai = dyn_cast<BeginAccessInst>(operandValue))
operandValue = bai->getSource();
if (auto *pbi = dyn_cast<ProjectBoxInst>(operandValue)) {
auto iter = projectBoxArgumentMap.find(pbi);
if (iter != projectBoxArgumentMap.end())
return iter->second;
}
return SILValue();
}
/// Handle a debug_value instruction during cloning of a closure;
/// if its operand is the promoted address argument then lower it to
/// another debug_value, otherwise it is handled normally.
void ClosureCloner::visitDebugValueInst(DebugValueInst *inst) {
if (inst->hasAddrVal())
if (SILValue value = getProjectBoxMappedVal(inst->getOperand())) {
getBuilder().setCurrentDebugScope(getOpScope(inst->getDebugScope()));
auto varInfo = *inst->getVarInfo();
if (varInfo.Scope)
varInfo.Scope = getOpScope(inst->getDebugScope());
getBuilder().createDebugValue(inst->getLoc(), value, varInfo);
return;
}
SILCloner<ClosureCloner>::visitDebugValueInst(inst);
}
/// Handle a destroy_value instruction during cloning of a closure; if it is a
/// destroy_value of a promoted box argument, then it is replaced with a
/// destroy_value of the new object type argument, otherwise it is handled
/// normally.
void ClosureCloner::visitDestroyValueInst(DestroyValueInst *inst) {
SILValue operand = inst->getOperand();
if (auto *arg = dyn_cast<SILArgument>(operand)) {
auto iter = boxArgumentMap.find(arg);
if (iter != boxArgumentMap.end()) {
// destroy_value of the box arguments get replaced with an end_borrow,
// destroy_value of the new object type argument.
SILFunction &f = getBuilder().getFunction();
auto &typeLowering = f.getTypeLowering(iter->second->getType());
SILBuilderWithPostProcess<ClosureCloner, 1> b(this, inst);
SILValue value = iter->second;
// We must have emitted a begin_borrow for any non-trivial value. Insert
// an end_borrow if so.
if (value->getOwnershipKind() != OwnershipKind::None) {
auto *bbi = cast<BeginBorrowInst>(value);
value = bbi->getOperand();
b.emitEndBorrowOperation(inst->getLoc(), bbi);
}
typeLowering.emitDestroyValue(b, inst->getLoc(), value);
return;
}
}
SILCloner<ClosureCloner>::visitDestroyValueInst(inst);
}
/// Handle an end_borrow instruction during cloning of a closure; if it is a
/// end_borrow from a load_borrow of a promoted box argument, then it is
/// deleted, otherwise it is handled normally.
void ClosureCloner::visitEndBorrowInst(EndBorrowInst *inst) {
SILValue operand = inst->getOperand();
if (auto *lbi = dyn_cast<LoadBorrowInst>(operand)) {
SILValue op = lbi->getOperand();
// When we check if we can do this, we only need to look through a single
// struct_element_addr since when checking if this is safe, we only look
// through a single struct_element_addr.
if (auto *sea = dyn_cast<StructElementAddrInst>(op))
op = sea->getOperand();
// If after optionally looking through a gep, we have our project_box, just
// eliminate the end_borrow.
if (getProjectBoxMappedVal(op))
return;
}
SILCloner<ClosureCloner>::visitEndBorrowInst(inst);
}
/// Handle a struct_element_addr instruction during cloning of a closure.
///
/// If its operand is the promoted address argument then ignore it, otherwise it
/// is handled normally.
void ClosureCloner::visitStructElementAddrInst(StructElementAddrInst *seai) {
if (getProjectBoxMappedVal(seai->getOperand()))
return;
SILCloner<ClosureCloner>::visitStructElementAddrInst(seai);
}
/// project_box of captured boxes can be eliminated.
void ClosureCloner::visitProjectBoxInst(ProjectBoxInst *pbi) {
if (auto *arg = dyn_cast<SILArgument>(pbi->getOperand()))
if (boxArgumentMap.count(arg))
return;
SILCloner<ClosureCloner>::visitProjectBoxInst(pbi);
}
/// If its operand is the promoted address argument then ignore it, otherwise it
/// is handled normally.
void ClosureCloner::visitBeginAccessInst(BeginAccessInst *bai) {
if (getProjectBoxMappedVal(bai->getSource()))
return;
SILCloner<ClosureCloner>::visitBeginAccessInst(bai);
}
/// If its operand is the promoted address argument then ignore it, otherwise it
/// is handled normally.
void ClosureCloner::visitEndAccessInst(EndAccessInst *eai) {
if (getProjectBoxMappedVal(eai->getBeginAccess()))
return;
SILCloner<ClosureCloner>::visitEndAccessInst(eai);
}
/// Handle a load_borrow instruction during cloning of a closure.
///
/// The two relevant cases are a direct load from a promoted address argument or
/// a load of a struct_element_addr of a promoted address argument.
void ClosureCloner::visitLoadBorrowInst(LoadBorrowInst *lbi) {
getBuilder().setCurrentDebugScope(getOpScope(lbi->getDebugScope()));
assert(lbi->getFunction()->hasOwnership() &&
"We should only see a load borrow in ownership qualified SIL");
if (SILValue value = getProjectBoxMappedVal(lbi->getOperand())) {
// Loads of the address argument get eliminated completely; the uses of
// the loads get mapped to uses of the new object type argument.
//
// We assume that the value is already guaranteed.
assert(
value->getOwnershipKind().isCompatibleWith(OwnershipKind::Guaranteed) &&
"Expected argument value to be guaranteed");
recordFoldedValue(lbi, value);
return;
}
auto *seai = dyn_cast<StructElementAddrInst>(lbi->getOperand());
if (!seai) {
SILCloner<ClosureCloner>::visitLoadBorrowInst(lbi);
return;
}
if (SILValue value = getProjectBoxMappedVal(seai->getOperand())) {
// Loads of a struct_element_addr of an argument get replaced with a
// struct_extract of the new passed in value. The value should be borrowed
// already, so we can just extract the value.
assert(
!getBuilder().getFunction().hasOwnership() ||
value->getOwnershipKind().isCompatibleWith(OwnershipKind::Guaranteed));
value = getBuilder().emitStructExtract(lbi->getLoc(), value,
seai->getField(), lbi->getType());
recordFoldedValue(lbi, value);
return;
}
SILCloner<ClosureCloner>::visitLoadBorrowInst(lbi);
return;
}
/// Handle a load instruction during cloning of a closure.
///
/// The two relevant cases are a direct load from a promoted address argument or
/// a load of a struct_element_addr of a promoted address argument.
void ClosureCloner::visitLoadInst(LoadInst *li) {
getBuilder().setCurrentDebugScope(getOpScope(li->getDebugScope()));
if (SILValue value = getProjectBoxMappedVal(li->getOperand())) {
// Loads of the address argument get eliminated completely; the uses of
// the loads get mapped to uses of the new object type argument.
//
// If we are compiling with SIL ownership, we need to take different
// behaviors depending on the type of load. Specifically, if we have a
// load [copy], then we need to add a copy_value here. If we have a take
// or trivial, we just propagate the value through.
if (li->getFunction()->hasOwnership() &&
li->getOwnershipQualifier() == LoadOwnershipQualifier::Copy) {
value = getBuilder().createCopyValue(li->getLoc(), value);
}
recordFoldedValue(li, value);
return;
}
auto *seai = dyn_cast<StructElementAddrInst>(li->getOperand());
if (!seai) {
SILCloner<ClosureCloner>::visitLoadInst(li);
return;
}
if (SILValue value = getProjectBoxMappedVal(seai->getOperand())) {
// Loads of a struct_element_addr of an argument get replaced with a
// struct_extract of the new passed in value. The value should be borrowed
// already, so we can just extract the value.
assert(
!getBuilder().getFunction().hasOwnership() ||
value->getOwnershipKind().isCompatibleWith(OwnershipKind::Guaranteed));
value = getBuilder().emitStructExtract(li->getLoc(), value,
seai->getField(), li->getType());
// If we were performing a load [copy], then we need to a perform a copy
// here since when cloning, we do not eliminate the destroy on the copied
// value.
if (li->getFunction()->hasOwnership() &&
li->getOwnershipQualifier() == LoadOwnershipQualifier::Copy) {
value = getBuilder().createCopyValue(li->getLoc(), value);
}
recordFoldedValue(li, value);
return;
}
SILCloner<ClosureCloner>::visitLoadInst(li);
}
//===----------------------------------------------------------------------===//
// EscapeMutationScanningState
//===----------------------------------------------------------------------===//
namespace {
struct EscapeMutationScanningState {
/// The list of mutations in the partial_apply caller that we found.
SmallVector<Operand *, 8> accumulatedMutations;
/// The list of escapes in the partial_apply caller/callee of the box that we
/// found.
SmallVector<Operand *, 8> accumulatedEscapes;
/// A multimap that maps partial applies to the set of operands in the partial
/// applies referenced function that the pass has identified as being the use
/// that caused the partial apply to capture our box.
///
/// We use a frozen multi-map since our algorithm first accumulates this info
/// and then wants to use it, perfect for the 2-stage frozen multi map.
SmallFrozenMultiMap<PartialApplyInst *, Operand *, 16>
accumulatedCaptureCausingUses;
/// A flag that we use to ensure that we only ever see 1 project_box on an
/// alloc_box.
bool sawProjectBoxInst;
/// The global partial_apply -> index map.
llvm::DenseMap<PartialApplyInst *, unsigned> &globalIndexMap;
};
} // end anonymous namespace
//===----------------------------------------------------------------------===//
// Partial Apply BoxArg Mutation/Escape/Capture Use Analysis
//===----------------------------------------------------------------------===//
static SILArgument *getBoxFromIndex(SILFunction *f, unsigned index) {
assert(f->isDefinition() && "Expected definition not external declaration!");
auto &entry = f->front();
return entry.getArgument(index);
}
static bool isNonMutatingLoad(SILInstruction *inst) {
if (isa<LoadBorrowInst>(inst))
return true;
auto *li = dyn_cast<LoadInst>(inst);
if (!li)
return false;
return li->getOwnershipQualifier() != LoadOwnershipQualifier::Take;
}
/// Given a partial_apply instruction and the argument index into its callee's
/// argument list of a box argument (which is followed by an argument for the
/// address of the box's contents), return true if this box has mutating
/// captures. Return false otherwise. All of the mutating captures that we find
/// are placed into \p accumulatedMutatingUses.
static bool
getPartialApplyArgMutationsAndEscapes(PartialApplyInst *pai,
SILArgument *boxArg,
EscapeMutationScanningState &state) {
SmallVector<ProjectBoxInst *, 2> projectBoxInsts;
// Conservatively do not allow any use of the box argument other than a
// strong_release or projection, since this is the pattern expected from
// SILGen.
SmallVector<Operand *, 32> incrementalEscapes;
SmallVector<Operand *, 32> incrementalCaptureCausingUses;
for (auto *use : boxArg->getUses()) {
if (isa<StrongReleaseInst>(use->getUser()) ||
isa<DestroyValueInst>(use->getUser()))
continue;
if (auto *pbi = dyn_cast<ProjectBoxInst>(use->getUser())) {
projectBoxInsts.push_back(pbi);
continue;
}
incrementalEscapes.push_back(use);
}
// Only allow loads of projections, either directly or via
// struct_element_addr instructions.
//
// TODO: This seems overly limited. Why not projections of tuples and other
// stuff? Also, why not recursive struct elements? This should be a helper
// function that mirrors isNonEscapingUse.
auto checkIfAddrUseMutating = [&](Operand *addrUse) -> bool {
unsigned initSize = incrementalEscapes.size();
auto *addrUser = addrUse->getUser();
if (auto *seai = dyn_cast<StructElementAddrInst>(addrUser)) {
for (auto *seaiUse : seai->getUses()) {
if (isNonMutatingLoad(seaiUse->getUser())) {
incrementalCaptureCausingUses.push_back(seaiUse);
} else {
incrementalEscapes.push_back(seaiUse);
}
}
return incrementalEscapes.size() != initSize;
}
if (isNonMutatingLoad(addrUser)) {
incrementalCaptureCausingUses.push_back(addrUse);
return false;
}
if (DebugValueInst::hasAddrVal(addrUser) ||
isa<MarkFunctionEscapeInst>(addrUser) || isa<EndAccessInst>(addrUser)) {
return false;
}
incrementalEscapes.push_back(addrUse);
return true;
};
for (auto *pbi : projectBoxInsts) {
for (auto *use : pbi->getUses()) {
if (auto *bai = dyn_cast<BeginAccessInst>(use->getUser())) {
for (auto *accessUseOper : bai->getUses()) {
checkIfAddrUseMutating(accessUseOper);
}
continue;
}
checkIfAddrUseMutating(use);
}
}
auto &accCaptureCausingUses = state.accumulatedCaptureCausingUses;
while (!incrementalCaptureCausingUses.empty())
accCaptureCausingUses.insert(pai,
incrementalCaptureCausingUses.pop_back_val());
if (incrementalEscapes.empty())
return false;
while (!incrementalEscapes.empty())
state.accumulatedEscapes.push_back(incrementalEscapes.pop_back_val());
return true;
}
bool isPartialApplyNonEscapingUser(Operand *currentOp, PartialApplyInst *pai,
EscapeMutationScanningState &state) {
LLVM_DEBUG(llvm::dbgs() << " Found partial: " << *pai);
unsigned opNo = currentOp->getOperandNumber();
assert(opNo != 0 && "Alloc box used as callee of partial apply?");
// If we've already seen this partial apply, then it means the same alloc box
// is being captured twice by the same closure, which is odd and unexpected:
// bail instead of trying to handle this case.
if (state.globalIndexMap.count(pai)) {
// TODO: Is it correct to treat this like an escape? We are just currently
// flagging all failures as warnings.
LLVM_DEBUG(llvm::dbgs() << " FAIL! Already seen.\n");
state.accumulatedEscapes.push_back(currentOp);
return false;
}
SILModule &mod = pai->getModule();
SILFunction *f = pai->getFunction();
auto closureType = pai->getType().castTo<SILFunctionType>();
SILFunctionConventions closureConv(closureType, mod);
// Calculate the index into the closure's argument list of the captured
// box pointer (the captured address is always the immediately following
// index so is not stored separately);
unsigned index = opNo - 1 + closureConv.getNumSILArguments();
auto *fn = pai->getReferencedFunctionOrNull();
// It is not safe to look at the content of dynamically replaceable functions
// since this pass looks at the content of Fn.
if (!fn || !fn->isDefinition() || fn->isDynamicallyReplaceable()) {
LLVM_DEBUG(llvm::dbgs() << " FAIL! Not a direct function definition "
"reference.\n");
state.accumulatedEscapes.push_back(currentOp);
return false;
}
SILArgument *boxArg = getBoxFromIndex(fn, index);
// For now, return false is the address argument is an address-only type,
// since we currently handle loadable types only.
// TODO: handle address-only types
// FIXME: Expansion
auto boxTy = boxArg->getType().castTo<SILBoxType>();
assert(boxTy->getLayout()->getFields().size() == 1 &&
"promoting compound box not implemented yet");
if (getSILBoxFieldType(TypeExpansionContext(*fn), boxTy, mod.Types, 0)
.isAddressOnly(*f)) {
LLVM_DEBUG(llvm::dbgs() << " FAIL! Box is an address only "
"argument!\n");
state.accumulatedEscapes.push_back(currentOp);
return false;
}
// Verify that this closure is known not to mutate the captured value; if
// it does, then conservatively refuse to promote any captures of this
// value.
if (getPartialApplyArgMutationsAndEscapes(pai, boxArg, state)) {
LLVM_DEBUG(llvm::dbgs() << " FAIL: Have a mutation or escape of a "
"partial apply arg?!\n");
return false;
}
// Record the index and continue.
LLVM_DEBUG(llvm::dbgs()
<< " Partial apply does not escape, may be optimizable!\n");
LLVM_DEBUG(llvm::dbgs() << " Index: " << index << "\n");
state.globalIndexMap.insert(std::make_pair(pai, index));
return true;
}
//===----------------------------------------------------------------------===//
// Project Box Escaping Use Analysis
//===----------------------------------------------------------------------===//
namespace {
class NonEscapingUserVisitor
: public SILInstructionVisitor<NonEscapingUserVisitor, bool> {
SmallVector<Operand *, 32> worklist;
SmallVectorImpl<Operand *> &accumulatedMutations;
SmallVectorImpl<Operand *> &accumulatedEscapes;
NullablePtr<Operand> currentOp;
public:
NonEscapingUserVisitor(Operand *initialOperand,
SmallVectorImpl<Operand *> &accumulatedMutations,
SmallVectorImpl<Operand *> &accumulatedEscapes)
: worklist(), accumulatedMutations(accumulatedMutations),
accumulatedEscapes(accumulatedEscapes), currentOp() {
worklist.push_back(initialOperand);
}
NonEscapingUserVisitor(const NonEscapingUserVisitor &) = delete;
NonEscapingUserVisitor &operator=(const NonEscapingUserVisitor &) = delete;
NonEscapingUserVisitor(NonEscapingUserVisitor &&) = delete;
NonEscapingUserVisitor &operator=(NonEscapingUserVisitor &&) = delete;
private:
void markCurrentOpAsMutation() {
accumulatedMutations.push_back(currentOp.get());
}
void markCurrentOpAsEscape() {
accumulatedEscapes.push_back(currentOp.get());
}
public:
bool compute() {
while (!worklist.empty()) {
currentOp = worklist.pop_back_val();
SILInstruction *user = currentOp.get()->getUser();
// Ignore type dependent operands.
if (user->isTypeDependentOperand(*(currentOp.get())))
continue;
// Then visit the specific user. This routine returns true if the value
// does not escape. In such a case, continue.
if (visit(user)) {
continue;
}
return false;
}
return true;
}
/// Visit a random value base.
///
/// These are considered to be escapes.
bool visitSILInstruction(SILInstruction *inst) {
LLVM_DEBUG(llvm::dbgs()
<< " FAIL! Have unknown escaping user: " << *inst);
markCurrentOpAsEscape();
return false;
}
#define ALWAYS_NON_ESCAPING_INST(INST) \
bool visit##INST##Inst(INST##Inst *) { return true; }
// Marking the boxed value as escaping is OK. It's just a DI annotation.
ALWAYS_NON_ESCAPING_INST(MarkFunctionEscape)
// These remaining instructions are ok and don't count as mutations.
ALWAYS_NON_ESCAPING_INST(StrongRetain)
ALWAYS_NON_ESCAPING_INST(Load)
ALWAYS_NON_ESCAPING_INST(StrongRelease)
ALWAYS_NON_ESCAPING_INST(DestroyValue)
ALWAYS_NON_ESCAPING_INST(EndBorrow)
ALWAYS_NON_ESCAPING_INST(DeallocBox)
ALWAYS_NON_ESCAPING_INST(EndAccess)
#undef ALWAYS_NON_ESCAPING_INST
bool visitApplyInst(ApplyInst *ai) {
auto argIndex = currentOp.get()->getOperandNumber() - 1;
SILFunctionConventions substConv(ai->getSubstCalleeType(), ai->getModule());
auto convention = substConv.getSILArgumentConvention(argIndex);
if (!convention.isIndirectConvention()) {
LLVM_DEBUG(llvm::dbgs()
<< " FAIL! Found non indirect apply user: " << *ai);
markCurrentOpAsEscape();
return false;
}
markCurrentOpAsMutation();
return true;
}
/// Add the Operands of a transitive use instruction to the worklist.
void addUsesToWorklist(SingleValueInstruction *svi) {
for (auto *use : svi->getUses()) {
worklist.push_back(use);
}
}
/// This is separate from the normal copy value handling since we are matching
/// the old behavior of non-top-level uses not being able to have partial
/// apply and project box uses.
struct detail {
enum IsMutating_t {
IsNotMutating = 0,
IsMutating = 1,
};
};
#define RECURSIVE_INST_VISITOR(MUTATING, INST) \
bool visit##INST##Inst(INST##Inst *i) { \
if (bool(detail::MUTATING)) { \
markCurrentOpAsMutation(); \
} \
addUsesToWorklist(i); \
return true; \
}
// *NOTE* It is important that we do not have copy_value here. The reason why
// is that we only want to handle copy_value directly of the alloc_box without
// going through any other instructions. This protects our optimization later
// on.
//
// Additionally, copy_value is not a valid use of any of the instructions that
// we allow through.
//
// TODO: Can we ever hit copy_values here? If we do, we may be missing
// opportunities.
RECURSIVE_INST_VISITOR(IsNotMutating, StructElementAddr)
RECURSIVE_INST_VISITOR(IsNotMutating, TupleElementAddr)
RECURSIVE_INST_VISITOR(IsNotMutating, InitEnumDataAddr)
RECURSIVE_INST_VISITOR(IsNotMutating, OpenExistentialAddr)
// begin_access may signify a modification, but is considered nonmutating
// because we will peek though it's uses to find the actual mutation.
RECURSIVE_INST_VISITOR(IsNotMutating, BeginAccess)
RECURSIVE_INST_VISITOR(IsMutating, UncheckedTakeEnumDataAddr)
#undef RECURSIVE_INST_VISITOR
bool visitCopyAddrInst(CopyAddrInst *cai) {
if (currentOp.get()->getOperandNumber() == CopyAddrInst::Dest ||
cai->isTakeOfSrc())
markCurrentOpAsMutation();
return true;
}
bool visitMarkUnresolvedMoveAddrInst(MarkUnresolvedMoveAddrInst *mai) {
if (currentOp.get()->getOperandNumber() == MarkUnresolvedMoveAddrInst::Dest)
markCurrentOpAsMutation();
return true;
}
bool visitStoreInst(StoreInst *si) {
if (currentOp.get()->getOperandNumber() != 1) {
LLVM_DEBUG(llvm::dbgs() << " FAIL! Found store of pointer: " << *si);
markCurrentOpAsEscape();
return false;
}
markCurrentOpAsMutation();
return true;
}
bool visitAssignInst(AssignInst *ai) {
if (currentOp.get()->getOperandNumber() != 1) {
LLVM_DEBUG(llvm::dbgs() << " FAIL! Found store of pointer: " << *ai);
markCurrentOpAsEscape();
return false;
}
markCurrentOpAsMutation();
return true;
}
};
} // end anonymous namespace
/// Given a use of an alloc_box instruction, return true if the use
/// definitely does not allow the box to escape; also, if the use is an
/// instruction which possibly mutates the contents of the box, then add it to
/// the Mutations vector.
static bool isNonEscapingUse(Operand *initialOp,
EscapeMutationScanningState &state) {
return NonEscapingUserVisitor(initialOp, state.accumulatedMutations,
state.accumulatedEscapes)
.compute();
}
static bool isProjectBoxNonEscapingUse(ProjectBoxInst *pbi,
EscapeMutationScanningState &state) {
LLVM_DEBUG(llvm::dbgs() << " Found project box: " << *pbi);
for (Operand *addrOp : pbi->getUses()) {
if (!isNonEscapingUse(addrOp, state)) {
LLVM_DEBUG(llvm::dbgs() << " FAIL! Has escaping user of addr:"
<< *addrOp->getUser());
return false;
}
}
return true;
}
//===----------------------------------------------------------------------===//
// Top Level AllocBox Escape/Mutation Analysis
//===----------------------------------------------------------------------===//
static bool findEscapeOrMutationUses(Operand *op,
EscapeMutationScanningState &state) {
SILInstruction *user = op->getUser();
if (auto *pai = dyn_cast<PartialApplyInst>(user)) {
return !isPartialApplyNonEscapingUser(op, pai, state);
}
// A mark_dependence user on a partial_apply is safe.
if (auto *userMDI = dyn_cast<MarkDependenceInst>(user)) {
if (userMDI->getBase() == op->get()) {
auto parent = userMDI->getValue();
while (auto *parentMDI = dyn_cast<MarkDependenceInst>(parent)) {
parent = parentMDI->getValue();
}
if (isa<PartialApplyInst>(parent))
return false;
state.accumulatedEscapes.push_back(
&userMDI->getOperandRef(MarkDependenceInst::Dependent));
return true;
}
}
if (auto *pbi = dyn_cast<ProjectBoxInst>(user)) {
// It is assumed in later code that we will only have 1 project_box. This
// can be seen since there is no code for reasoning about multiple
// boxes. Just put in the restriction so we are consistent.
if (state.sawProjectBoxInst)
return true;
state.sawProjectBoxInst = true;
return !isProjectBoxNonEscapingUse(pbi, state);
}
// Given a top level copy value use or mark_uninitialized, check all of its
// user operands as if they were apart of the use list of the base operand.
//
// This is a separate code path from the non escaping user visitor check since
// we want to be more conservative around non-top level copies (i.e. a copy
// derived from a projection like instruction). In fact such a thing may not
// even make any sense!
if (isa<CopyValueInst>(user) || isa<MarkUninitializedInst>(user) ||
isa<BeginBorrowInst>(user)) {
bool foundSomeMutations = false;
for (auto *use : cast<SingleValueInstruction>(user)->getUses()) {
foundSomeMutations |= findEscapeOrMutationUses(use, state);
}
return foundSomeMutations;
}
// Verify that this use does not otherwise allow the alloc_box to
// escape.
return isNonEscapingUse(op, state);
}
/// We found a capture of \p abi in concurrent closure \p pai that we can not
/// promote to a by value capture. Emit a nice warning (FIXME: error) to warn
/// the user and provide the following information in the compiler feedback:
///
/// 1. The source loc where the variable's box is written to.
///
/// 2. The source loc of the captured variable's declaration.
///
/// 3. The source loc of the start of the concurrent closure that caused the
/// variable to be captured.
///
/// 4. All places in the concurrent closure that triggered the box's
/// capture. NOTE: For objects these are load points. For address only things
/// it is still open for debate at this point.
static void diagnoseInvalidCaptureByConcurrentClosure(
AllocBoxInst *abi, PartialApplyInst *pai,
const EscapeMutationScanningState &state, SILInstruction *mutatingUser) {
auto captureCausingUses = state.accumulatedCaptureCausingUses.find(pai);
if (!captureCausingUses) {
llvm::errs() << "Didn't find capture causing use of partial apply: "
<< *pai;
llvm::errs() << "Original Func: " << pai->getFunction()->getName() << '\n';
llvm::errs() << "Partial Applied Func: "
<< pai->getReferencedFunctionOrNull()->getName() << '\n';
llvm::report_fatal_error("standard compiler error");
}
auto &astCtx = pai->getFunction()->getASTContext();
auto &de = astCtx.Diags;
auto varInfo = abi->getVarInfo();
StringRef name = "<unknown>";
if (varInfo) {
name = varInfo->Name;
}
de.diagnoseWithNotes(
de.diagnose(mutatingUser->getLoc().getSourceLoc(),
diag::capturepromotion_concurrentcapture_mutation, name),
[&]() {
de.diagnose(abi->getLoc().getSourceLoc(),
diag::capturepromotion_variable_defined_here);
de.diagnose(pai->getLoc().getSourceLoc(),
diag::capturepromotion_concurrentcapture_closure_here);
for (auto *use : *captureCausingUses) {
de.diagnose(
use->getUser()->getLoc().getSourceLoc(),
diag::capturepromotion_concurrentcapture_capturinguse_here);
}
});
}
/// Examine an alloc_box instruction, returning true if at least one
/// capture of the boxed variable is promotable. If so, then the pair of the
/// partial_apply instruction and the index of the box argument in the closure's
/// argument list is added to IM.
static bool
examineAllocBoxInst(AllocBoxInst *abi, ReachabilityInfo &ri,
llvm::DenseMap<PartialApplyInst *, unsigned> &im) {
LLVM_DEBUG(llvm::dbgs() << "Visiting alloc box: " << *abi);
EscapeMutationScanningState state{{}, {}, {}, false, im};
// Scan the box for escaping or mutating uses.
for (auto *use : abi->getUses()) {
findEscapeOrMutationUses(use, state);
}
if (!state.accumulatedEscapes.empty()) {
LLVM_DEBUG(llvm::dbgs()
<< "Found escaping uses! Can not optimize this alloc box?!\n");
while (!state.accumulatedEscapes.empty()) {
auto *escapingUse = state.accumulatedEscapes.pop_back_val();
LLVM_DEBUG(llvm::dbgs() << "Escaping use: " << *escapingUse->getUser());
}
return false;
}
state.accumulatedCaptureCausingUses.setFrozen();
LLVM_DEBUG(llvm::dbgs() << "We can optimize this alloc box!\n");
// Helper lambda function to determine if instruction b is strictly after
// instruction a, assuming both are in the same basic block.
auto isAfter = [](SILInstruction *a, SILInstruction *b) {
auto fIter = b->getParent()->begin();
auto bIter = b->getIterator();
auto aIter = a->getIterator();
while (bIter != fIter) {
--bIter;
if (aIter == bIter)
return true;
}
return false;
};
LLVM_DEBUG(llvm::dbgs()
<< "Checking for any mutations that invalidate captures...\n");
// Loop over all mutations to possibly invalidate captures.
for (auto *use : state.accumulatedMutations) {
auto iter = im.begin();
while (iter != im.end()) {
auto *user = use->getUser();
auto *pai = iter->first;
// The mutation invalidates a capture if it occurs in a block reachable
// from the block the partial_apply is in, or if it is in the same
// block is after the partial_apply.
if (ri.isReachable(pai->getParent(), user->getParent()) ||
(pai->getParent() == user->getParent() && isAfter(pai, user))) {
// If our partial apply is concurrent and we can not promote this, emit
// a warning that shows the variable, where the variable is captured,
// and the mutation that we found.
if (pai->getFunctionType()->isSendable()) {
diagnoseInvalidCaptureByConcurrentClosure(abi, pai, state, user);
}
LLVM_DEBUG(llvm::dbgs() << " Invalidating: " << *pai);
LLVM_DEBUG(llvm::dbgs() << " Because of user: " << *user);
auto prev = iter++;
im.erase(prev);
continue;
}
++iter;
}
// If there are no valid captures left, then stop.
if (im.empty()) {
LLVM_DEBUG(llvm::dbgs() << " Ran out of valid captures... bailing!\n");
return false;
}
}
LLVM_DEBUG(llvm::dbgs() << " We can optimize this box!\n");
return true;
}
/// For an alloc_box or iterated copy_value alloc_box, get or create the
/// project_box for the copy or original alloc_box.
///
/// There are two possible case here:
///
/// 1. It could be an alloc box.
/// 2. It could be an iterated copy_value from an alloc_box.
///
/// Some important constraints from our initial safety condition checks:
///
/// 1. We only see a project_box paired with an alloc_box. e.x.:
///
/// (project_box (alloc_box)).
///
/// 2. We only see a mark_uninitialized when paired with an (alloc_box,
/// project_box). e.x.:
///
/// (project_box (mark_uninitialized (alloc_box)))
///
/// The asserts are to make sure that if the initial safety condition check
/// is changed, this code is changed as well.
static SILValue getOrCreateProjectBoxHelper(SILValue partialOperand) {
// If we have a copy_value, just create a project_box on the copy and return.
if (auto *cvi = dyn_cast<CopyValueInst>(partialOperand)) {
SILBuilderWithScope b(std::next(cvi->getIterator()));
return b.createProjectBox(cvi->getLoc(), cvi, 0);
}
// Otherwise, handle the alloc_box case. If we have a mark_uninitialized on
// the box, we know that we will have a project_box of that value due to SIL
// verifier invariants.
SingleValueInstruction *box = cast<AllocBoxInst>(partialOperand);
if (auto *mui = box->getSingleUserOfType<MarkUninitializedInst>()) {
if (auto *pbi = mui->getSingleUserOfType<ProjectBoxInst>()) {
return pbi;
}
}
// Otherwise, create a new project_box.
SILBuilderWithScope b(std::next(box->getIterator()));
return b.createProjectBox(box->getLoc(), box, 0);
}
//===----------------------------------------------------------------------===//
// Top Level Processing of Partial Applies with AllocBox Args
//===----------------------------------------------------------------------===//
/// Change the base in mark_dependence.
static void
mapMarkDependenceArguments(SingleValueInstruction *root,
llvm::DenseMap<SILValue, SILValue> &map,
SmallVectorImpl<SILInstruction *> &toDelete) {
SmallVector<Operand *, 16> useWorklist(root->getUses());
for (auto *use : useWorklist) {
if (auto *mdi = dyn_cast<MarkDependenceInst>(use->getUser())) {
mapMarkDependenceArguments(mdi, map, toDelete);
auto iter = map.find(mdi->getBase());
if (iter != map.end()) {
mdi->setBase(iter->second);
}
// Remove mark_dependence on trivial values.
if (mdi->getBase()->getType().isTrivial(*mdi->getFunction())) {
mdi->replaceAllUsesWith(mdi->getValue());
toDelete.push_back(mdi);
}
}
}
}
/// Given a partial_apply instruction and a set of promotable indices,
/// clone the closure with the promoted captures and replace the partial_apply
/// with a partial_apply of the new closure, fixing up reference counting as
/// necessary. Also, if the closure is cloned, the cloned function is added to
/// the worklist.
static SILFunction *
processPartialApplyInst(SILOptFunctionBuilder &funcBuilder,
PartialApplyInst *pai, IndicesSet &promotableIndices,
SmallVectorImpl<SILFunction *> &worklist) {
SILFunction *f = pai->getFunction();
SILModule &mod = pai->getModule();
auto *fri = dyn_cast<FunctionRefInst>(pai->getCallee());
// Clone the closure with the given promoted captures.
SILFunction *clonedFn = ClosureCloner::constructClonedFunction(
funcBuilder, pai, fri, promotableIndices, f->getResilienceExpansion());
worklist.push_back(clonedFn);
// Mark the original partial apply function as deletable if it doesn't have
// uses later.
fri->getReferencedFunction()->addSemanticsAttr(semantics::DELETE_IF_UNUSED);
// Initialize a SILBuilder and create a function_ref referencing the cloned
// closure.
SILBuilderWithScope builder(pai);
SILValue fnVal = builder.createFunctionRef(pai->getLoc(), clonedFn);
// Populate the argument list for a new partial_apply instruction, taking into
// consideration any captures.
auto calleeFunctionTy = pai->getCallee()->getType().castTo<SILFunctionType>();
auto substCalleeFunctionTy = calleeFunctionTy;
if (pai->hasSubstitutions())
substCalleeFunctionTy = calleeFunctionTy->substGenericArgs(
mod, pai->getSubstitutionMap(), TypeExpansionContext(*f));
SILFunctionConventions calleeConv(substCalleeFunctionTy, mod);
auto calleePInfo = substCalleeFunctionTy->getParameters();
SILFunctionConventions paConv(pai->getType().castTo<SILFunctionType>(), mod);
unsigned firstIndex = paConv.getNumSILArguments();
unsigned opNo = 1;
unsigned opCount = pai->getNumOperands() - pai->getNumTypeDependentOperands();
SmallVector<SILValue, 16> args;
auto numIndirectResults = calleeConv.getNumIndirectSILResults();
llvm::DenseMap<SILValue, SILValue> capturedMap;
llvm::SmallSet<SILValue, 16> newCaptures;
for (; opNo != opCount; ++opNo) {
unsigned index = opNo - 1 + firstIndex;
if (!promotableIndices.count(index)) {
args.push_back(pai->getOperand(opNo));
continue;
}
// First the grab the box and projected_box for the box value.
//
// *NOTE* Box may be a copy_value.
SILValue box = pai->getOperand(opNo);
SILValue addr = getOrCreateProjectBoxHelper(box);
auto &typeLowering = f->getTypeLowering(addr->getType());
auto newCaptured =
typeLowering.emitLoadOfCopy(builder, pai->getLoc(), addr, IsNotTake);
args.push_back(newCaptured);
capturedMap[box] = newCaptured;
newCaptures.insert(newCaptured);
// A partial_apply [stack] does not own the captured argument but we must
// destroy the projected object. We will do so after having created the new
// partial_apply below.
if (pai->isOnStack())
continue;
// Cleanup the captured argument.
//
// *NOTE* If we initially had a box, then this is on the actual
// alloc_box. Otherwise, it is on the specific iterated copy_value that we
// started with.
SILParameterInfo cpInfo = calleePInfo[index - numIndirectResults];
assert(calleeConv.getSILType(cpInfo, builder.getTypeExpansionContext()) ==
box->getType() &&
"SILType of parameter info does not match type of parameter");
releasePartialApplyCapturedArg(builder, pai->getLoc(), box, cpInfo);
++NumCapturesPromoted;
}
// Create a new partial apply with the new arguments.
auto *newPAI = builder.createPartialApply(
pai->getLoc(), fnVal, pai->getSubstitutionMap(), args,
pai->getCalleeConvention(), pai->getResultIsolation(),
pai->isOnStack());
pai->replaceAllUsesWith(newPAI);
pai->eraseFromParent();
if (fri->use_empty()) {
fri->eraseFromParent();
// TODO: If this is the last use of the closure, and if it has internal
// linkage, we should remove it from the SILModule now.
}
if (newPAI->isOnStack()) {
// Insert destroy's of new captured arguments.
for (auto *use : newPAI->getUses()) {
if (auto *dsi = dyn_cast<DeallocStackInst>(use->getUser())) {
builder.setInsertionPoint(std::next(SILBasicBlock::iterator(dsi)));
insertDestroyOfCapturedArguments(
newPAI, builder,
[&](SILValue arg) -> SILValue {
return newCaptures.count(arg) ? arg : SILValue();
});
}
}
// Map the mark dependence arguments.
SmallVector<SILInstruction *, 16> toDelete;
mapMarkDependenceArguments(newPAI, capturedMap, toDelete);
for (auto *inst : toDelete)
inst->eraseFromParent();
}
return clonedFn;
}
static void constructMapFromPartialApplyToPromotableIndices(
SILFunction *f, PartialApplyIndicesMap &partialApplyIndicesAccumulator) {
ReachabilityInfo reachabilityInfo(f);
// This is a map from each partial apply to a single index which is a
// promotable box variable for the alloc_box currently being considered.
llvm::DenseMap<PartialApplyInst *, unsigned> incrementalIndexMap;
// Consider all alloc_box instructions in the function.
for (auto &block : *f) {
for (auto &inst : block) {
if (auto *abi = dyn_cast<AllocBoxInst>(&inst)) {
incrementalIndexMap.clear();
if (examineAllocBoxInst(abi, reachabilityInfo, incrementalIndexMap)) {
// If we are able to promote at least one capture of the alloc_box,
// then add the promotable index to the main map.
for (auto &indexPair : incrementalIndexMap)
partialApplyIndicesAccumulator[indexPair.first].insert(
indexPair.second);
}
LLVM_DEBUG(llvm::dbgs() << "\n");
}
}
}
}
//===----------------------------------------------------------------------===//
// Top Level Entrypoint
//===----------------------------------------------------------------------===//
namespace {
class CapturePromotionPass : public SILModuleTransform {
/// The entry point to the transformation.
void run() override {
SmallVector<SILFunction *, 128> worklist;
for (auto &f : *getModule()) {
if (f.wasDeserializedCanonical() || !f.hasOwnership())
continue;
processFunction(&f, worklist);
}
while (!worklist.empty()) {
auto *f = worklist.pop_back_val();
if (!f->hasOwnership())
continue;
processFunction(f, worklist);
}
}
void processFunction(SILFunction *f,
SmallVectorImpl<SILFunction *> &worklist);
};
} // end anonymous namespace
void CapturePromotionPass::processFunction(
SILFunction *func, SmallVectorImpl<SILFunction *> &worklist) {
assert(func->hasOwnership() &&
"Only can perform capture promotion on functions with ownership. All "
"functions in raw SIL should have OSSA now out of SILGen");
LLVM_DEBUG(llvm::dbgs() << "******** Performing Capture Promotion on: "
<< func->getName() << "********\n");
// This is a map from each partial apply to a set of indices of promotable
// box variables.
PartialApplyIndicesMap indicesMap;
constructMapFromPartialApplyToPromotableIndices(func, indicesMap);
// Do the actual promotions; all promotions on a single partial_apply are
// handled together.
SILOptFunctionBuilder funcBuilder(*this);
for (auto &indicesPair : indicesMap) {
PartialApplyInst *pai = indicesPair.first;
SILFunction *clonedFn =
processPartialApplyInst(funcBuilder, pai, indicesPair.second, worklist);
(void)clonedFn;
}
invalidateAnalysis(func, SILAnalysis::InvalidationKind::FunctionBody);
}
SILTransform *swift::createCapturePromotion() {
return new CapturePromotionPass();
}
Reference in New Issue View Git Blame Copy Permalink