blob: 5562946bd50b76987882b1e8a749f5521fa69329 [file] [log] [blame]
//===--- LoadCopyToLoadBorrowOpt.cpp --------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2020 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
///
/// Defines the main optimization that converts load [copy] -> load_borrow if we
/// can prove that the +1 is not actually needed and the memory loaded from is
/// never written to while the load [copy]'s object value is being used.
///
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "sil-semantic-arc-opts"
#include "OwnershipLiveRange.h"
#include "SemanticARCOptVisitor.h"
#include "swift/SIL/LinearLifetimeChecker.h"
#include "swift/SIL/MemAccessUtils.h"
#include "swift/SIL/OwnershipUtils.h"
#include "swift/SIL/Projection.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILValue.h"
#include "swift/SILOptimizer/Utils/ValueLifetime.h"
#include "llvm/Support/CommandLine.h"
using namespace swift;
using namespace swift::semanticarc;
//===----------------------------------------------------------------------===//
// Memory Analysis
//===----------------------------------------------------------------------===//
namespace {
/// A class that computes in a flow insensitive way if we can prove that our
/// storage is either never written to, or is initialized exactly once and never
/// written to again. In both cases, we can convert load [copy] -> load_borrow
/// safely.
class StorageGuaranteesLoadVisitor
: public AccessUseDefChainVisitor<StorageGuaranteesLoadVisitor> {
// The context that contains global state used across all semantic arc
// optimizations.
Context &ctx;
// The live range of the original load.
const OwnershipLiveRange &liveRange;
// The current address being visited.
SILValue currentAddress;
Optional<bool> isWritten;
public:
StorageGuaranteesLoadVisitor(Context &context, LoadInst *load,
const OwnershipLiveRange &liveRange)
: ctx(context), liveRange(liveRange), currentAddress(load->getOperand()) {
}
void answer(bool written) {
currentAddress = nullptr;
isWritten = written;
}
void next(SILValue address) { currentAddress = address; }
void visitNestedAccess(BeginAccessInst *access) {
// First see if we have read/modify. If we do not, just look through the
// nested access.
switch (access->getAccessKind()) {
case SILAccessKind::Init:
case SILAccessKind::Deinit:
return next(access->getOperand());
case SILAccessKind::Read:
case SILAccessKind::Modify:
break;
}
// Next check if our live range is completely in the begin/end access
// scope. If so, we may be able to use a load_borrow here!
SmallVector<Operand *, 8> endScopeUses;
transform(access->getEndAccesses(), std::back_inserter(endScopeUses),
[](EndAccessInst *eai) { return &eai->getAllOperands()[0]; });
SmallPtrSet<SILBasicBlock *, 4> visitedBlocks;
LinearLifetimeChecker checker(visitedBlocks, ctx.getDeadEndBlocks());
if (!checker.validateLifetime(access, endScopeUses,
liveRange.getAllConsumingUses())) {
// If we fail the linear lifetime check, then just recur:
return next(access->getOperand());
}
// Otherwise, if we have read, then we are done!
if (access->getAccessKind() == SILAccessKind::Read) {
return answer(false);
}
// If we have a modify, check if our value is /ever/ written to. If it is
// never actually written to, then we convert to a load_borrow.
auto result = ctx.addressToExhaustiveWriteListCache.get(access);
if (!result.hasValue()) {
return answer(true);
}
if (result.getValue().empty()) {
return answer(false);
}
return answer(true);
}
void visitArgumentAccess(SILFunctionArgument *arg) {
// If this load_copy is from an indirect in_guaranteed argument, then we
// know for sure that it will never be written to.
if (arg->hasConvention(SILArgumentConvention::Indirect_In_Guaranteed)) {
return answer(false);
}
// If we have an inout parameter that isn't ever actually written to, return
// false.
if (arg->getKnownParameterInfo().isIndirectMutating()) {
auto wellBehavedWrites = ctx.addressToExhaustiveWriteListCache.get(arg);
if (!wellBehavedWrites.hasValue()) {
return answer(true);
}
// No writes.
if (wellBehavedWrites->empty()) {
return answer(false);
}
// Ok, we have some writes. See if any of them are within our live
// range. If any are, we definitely can not promote to load_borrow.
SmallPtrSet<SILBasicBlock *, 4> visitedBlocks;
SmallVector<BeginAccessInst *, 16> foundBeginAccess;
LinearLifetimeChecker checker(visitedBlocks, ctx.getDeadEndBlocks());
SILValue introducerValue = liveRange.getIntroducer().value;
if (!checker.usesNotContainedWithinLifetime(introducerValue,
liveRange.getDestroyingUses(),
*wellBehavedWrites)) {
return answer(true);
}
// Finally, check if our live range is strictly contained within any of
// our scoped writes.
SmallVector<Operand *, 16> endAccessList;
for (Operand *use : *wellBehavedWrites) {
auto *bai = dyn_cast<BeginAccessInst>(use->getUser());
if (!bai) {
continue;
}
endAccessList.clear();
llvm::transform(
bai->getUsersOfType<EndAccessInst>(),
std::back_inserter(endAccessList),
[](EndAccessInst *eai) { return &eai->getAllOperands()[0]; });
visitedBlocks.clear();
// We know that our live range is based on a load [copy], so we know
// that our value must have a defining inst.
auto *definingInst =
cast<LoadInst>(introducerValue->getDefiningInstruction());
// Then if our defining inst is not in our bai, endAccessList region, we
// know that the two ranges must be disjoint, so continue.
if (!checker.validateLifetime(bai, endAccessList,
&definingInst->getAllOperands()[0])) {
continue;
}
// Otherwise, we do have an overlap, return true.
return answer(true);
}
// Otherwise, there isn't an overlap, so we don't write to it.
return answer(false);
}
// TODO: This should be extended:
//
// 1. We should be able to analyze in arguments and see if they are only
// ever destroyed at the end of the function. In such a case, we may be
// able to also to promote load [copy] from such args to load_borrow.
return answer(true);
}
void visitGlobalAccess(SILValue global) {
return answer(
!AccessedStorage(global, AccessedStorage::Global).isLetAccess());
}
void visitClassAccess(RefElementAddrInst *field) {
currentAddress = nullptr;
// We know a let property won't be written to if the base object is
// guaranteed for the duration of the access.
// For non-let properties conservatively assume they may be written to.
if (!field->getField()->isLet()) {
return answer(true);
}
// The lifetime of the `let` is guaranteed if it's dominated by the
// guarantee on the base. See if we can find a single borrow introducer for
// this object. If we could not find a single such borrow introducer, assume
// that our property is conservatively written to.
SILValue baseObject = field->getOperand();
auto value = getSingleBorrowIntroducingValue(baseObject);
if (!value) {
return answer(true);
}
// Ok, we have a single borrow introducing value. First do a quick check if
// we have a non-local scope that is a function argument. In such a case, we
// know statically that our let can not be written to in the current
// function. To be conservative, assume that all other non-local scopes
// write to memory.
if (!value->isLocalScope()) {
if (value->kind == BorrowedValueKind::SILFunctionArgument) {
return answer(false);
}
// TODO: Once we model Coroutine results as non-local scopes, we should be
// able to return false here for them as well.
return answer(true);
}
// TODO: This is disabled temporarily for guaranteed phi args just for
// staging purposes. Thus be conservative and assume true in these cases.
if (value->kind == BorrowedValueKind::Phi) {
return answer(true);
}
// Ok, we now know that we have a local scope whose lifetime we need to
// analyze. With that in mind, gather up the lifetime ending uses of our
// borrow scope introducing value and then use the linear lifetime checker
// to check whether the copied value is dominated by the lifetime of the
// borrow it's based on.
SmallVector<Operand *, 4> endScopeInsts;
value->visitLocalScopeEndingUses(
[&](Operand *use) { endScopeInsts.push_back(use); });
SmallPtrSet<SILBasicBlock *, 4> visitedBlocks;
LinearLifetimeChecker checker(visitedBlocks, ctx.getDeadEndBlocks());
// Returns true on success. So we invert.
bool foundError = !checker.validateLifetime(
baseObject, endScopeInsts, liveRange.getAllConsumingUses());
return answer(foundError);
}
// TODO: Handle other access kinds?
void visitBase(SILValue base, AccessedStorage::Kind kind) {
return answer(true);
}
void visitNonAccess(SILValue addr) { return answer(true); }
void visitCast(SingleValueInstruction *cast, Operand *parentAddr) {
return next(parentAddr->get());
}
void visitStorageCast(SingleValueInstruction *projectedAddr,
Operand *parentAddr) {
return next(parentAddr->get());
}
void visitAccessProjection(SingleValueInstruction *projectedAddr,
Operand *parentAddr) {
return next(parentAddr->get());
}
void visitPhi(SILPhiArgument *phi) {
// We shouldn't have address phis in OSSA SIL, so we don't need to recur
// through the predecessors here.
return answer(true);
}
/// See if we have an alloc_stack that is only written to once by an
/// initializing instruction.
void visitStackAccess(AllocStackInst *stack) {
SmallVector<Operand *, 8> destroyAddrOperands;
bool initialAnswer = isSingleInitAllocStack(stack, destroyAddrOperands);
if (!initialAnswer)
return answer(true);
// Then make sure that all of our load [copy] uses are within the
// destroy_addr.
SmallPtrSet<SILBasicBlock *, 4> visitedBlocks;
LinearLifetimeChecker checker(visitedBlocks, ctx.getDeadEndBlocks());
// Returns true on success. So we invert.
bool foundError = !checker.validateLifetime(
stack, destroyAddrOperands /*consuming users*/,
liveRange.getAllConsumingUses() /*non consuming users*/);
return answer(foundError);
}
bool doIt() {
while (currentAddress) {
visit(currentAddress);
}
return *isWritten;
}
};
} // namespace
static bool isWrittenTo(Context &ctx, LoadInst *load,
const OwnershipLiveRange &lr) {
StorageGuaranteesLoadVisitor visitor(ctx, load, lr);
return visitor.doIt();
}
//===----------------------------------------------------------------------===//
// Top Level Entrypoint
//===----------------------------------------------------------------------===//
// Convert a load [copy] from unique storage [read] that has all uses that can
// accept a guaranteed parameter to a load_borrow.
bool SemanticARCOptVisitor::visitLoadInst(LoadInst *li) {
// This optimization can use more complex analysis. We should do some
// experiments before enabling this by default as a guaranteed optimization.
if (ctx.onlyGuaranteedOpts)
return false;
// If we are not supposed to perform this transform, bail.
if (!ctx.shouldPerform(ARCTransformKind::LoadCopyToLoadBorrowPeephole))
return false;
if (li->getOwnershipQualifier() != LoadOwnershipQualifier::Copy)
return false;
// Ok, we have our load [copy]. Make sure its value is truly a dead live range
// implying it is only ever consumed by destroy_value instructions. If it is
// consumed, we need to pass off a +1 value, so bail.
//
// FIXME: We should consider if it is worth promoting a load [copy]
// -> load_borrow if we can put a copy_value on a cold path and thus
// eliminate RR traffic on a hot path.
OwnershipLiveRange lr(li);
if (bool(lr.hasUnknownConsumingUse()))
return false;
// Then check if our address is ever written to. If it is, then we cannot use
// the load_borrow because the stored value may be released during the loaded
// value's live range.
if (isWrittenTo(ctx, li, lr))
return false;
// Ok, we can perform our optimization. Convert the load [copy] into a
// load_borrow.
auto *lbi =
SILBuilderWithScope(li).createLoadBorrow(li->getLoc(), li->getOperand());
lr.insertEndBorrowsAtDestroys(lbi, getDeadEndBlocks(), ctx.lifetimeFrontier);
std::move(lr).convertToGuaranteedAndRAUW(lbi, getCallbacks());
return true;
}