blob: cf11c5aed047d64820114c37cfd0a0c2bbe6cf79 [file] [log] [blame]
//===--- MemoryBehavior.cpp -----------------------------------------------===//
// This source file is part of the 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 for license information
// See for the list of Swift project authors
#define DEBUG_TYPE "sil-membehavior"
#include "swift/SIL/InstructionUtils.h"
#include "swift/SIL/MemAccessUtils.h"
#include "swift/SIL/SILVisitor.h"
#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
#include "swift/SILOptimizer/Analysis/EscapeAnalysis.h"
#include "swift/SILOptimizer/Analysis/SideEffectAnalysis.h"
#include "swift/SILOptimizer/Analysis/ValueTracking.h"
#include "llvm/Support/Debug.h"
using namespace swift;
// The MemoryBehavior Cache must not grow beyond this size.
// We limit the size of the MB cache to 2**14 because we want to limit the
// memory usage of this cache.
static const int MemoryBehaviorAnalysisMaxCacheSize = 16384;
// Memory Behavior Implementation
namespace {
using MemBehavior = SILInstruction::MemoryBehavior;
/// Visitor that determines the memory behavior of an instruction relative to a
/// specific SILValue (i.e. can the instruction cause the value to be read,
/// etc.).
/// TODO: Clarify what it means to return a MayHaveSideEffects result. Does this
/// mean that the instruction may release objects referenced by value 'V'?
/// Deallocate the an address contained in 'V'? Are any other code motion
/// barriers relevant here?
class MemoryBehaviorVisitor
: public SILInstructionVisitor<MemoryBehaviorVisitor, MemBehavior> {
AliasAnalysis *AA;
SideEffectAnalysis *SEA;
EscapeAnalysis *EA;
/// The value we are attempting to discover memory behavior relative to.
SILValue V;
/// Cache either the address of the access corresponding to memory at 'V', or
/// 'V' itself if it isn't recognized as part of an access. The cached value
/// is always a valid SILValue.
SILValue cachedValueAddress;
Optional<bool> cachedIsLetValue;
/// The SILType of the value.
Optional<SILType> TypedAccessTy;
MemoryBehaviorVisitor(AliasAnalysis *AA, SideEffectAnalysis *SEA,
EscapeAnalysis *EA, SILValue V)
: AA(AA), SEA(SEA), EA(EA), V(V) {}
SILType getValueTBAAType() {
if (!TypedAccessTy)
TypedAccessTy = computeTBAAType(V);
return *TypedAccessTy;
/// If 'V' is an address projection within a formal access, return the
/// canonical address of the formal access if possible without looking past
/// any storage casts. Otherwise, a "best-effort" address
/// If 'V' is an address, then the returned value is also an address.
SILValue getValueAddress() {
if (!cachedValueAddress) {
cachedValueAddress =
V->getType().isAddress() ? getTypedAccessAddress(V) : V;
return cachedValueAddress;
/// Return true if 'V's accessed address is that of a let variables.
bool isLetValue() {
if (!cachedIsLetValue) {
cachedIsLetValue =
V->getType().isAddress() && isLetAddress(getValueAddress());
return cachedIsLetValue.getValue();
// Return true is the given address (or pointer) may alias with 'V'.
bool mayAlias(SILValue opAddress) {
if (AA->isNoAlias(opAddress, V, computeTBAAType(opAddress),
getValueTBAAType())) {
<< "No alias: access " << opAddress << " value " << V);
return false;
<< "May alias: access " << opAddress << " value " << V);
return true;
MemBehavior visitValueBase(ValueBase *V) {
MemBehavior visitSILInstruction(SILInstruction *Inst) {
// If we do not have any more information, just use the general memory
// behavior implementation.
auto Behavior = Inst->getMemoryBehavior();
// If this is a regular read-write access then return the computed memory
// behavior.
if (!isLetValue())
return Behavior;
// If this is a read-only access to 'let variable'. Other side effects, such
// as releases of the object containing a 'let' property are still relevant.
switch (Behavior) {
case MemBehavior::MayReadWrite: return MemBehavior::MayRead;
case MemBehavior::MayWrite: return MemBehavior::None;
default: return Behavior;
MemBehavior visitBeginAccessInst(BeginAccessInst *beginAccess) {
switch (beginAccess->getAccessKind()) {
case SILAccessKind::Deinit:
// A [deinit] only directly reads from the object. The fact that it frees
// memory is modeled more precisely by the release operations within the
// deinit scope. Therefore, handle it like a [read] here...
case SILAccessKind::Read:
if (!mayAlias(beginAccess->getSource()))
return MemBehavior::None;
return MemBehavior::MayRead;
case SILAccessKind::Modify:
if (isLetValue()) {
assert(getAccessBase(beginAccess) != getValueAddress()
&& "let modification not allowed");
return MemBehavior::None;
// [modify] has a special case for ignoring 'let's, but otherwise is
// identical to an [init]...
case SILAccessKind::Init:
if (!mayAlias(beginAccess->getSource()))
return MemBehavior::None;
return MemBehavior::MayWrite;
llvm_unreachable("invalid access kind");
MemBehavior visitEndAccessInst(EndAccessInst *endAccess) {
return visitBeginAccessInst(endAccess->getBeginAccess());
MemBehavior visitLoadInst(LoadInst *LI);
MemBehavior visitStoreInst(StoreInst *SI);
MemBehavior visitCopyAddrInst(CopyAddrInst *CAI);
MemBehavior visitApplyInst(ApplyInst *AI);
MemBehavior visitTryApplyInst(TryApplyInst *AI);
MemBehavior visitBeginApplyInst(BeginApplyInst *AI);
MemBehavior visitEndApplyInst(EndApplyInst *EAI);
MemBehavior visitAbortApplyInst(AbortApplyInst *AAI);
MemBehavior getApplyBehavior(FullApplySite AS);
MemBehavior visitBuiltinInst(BuiltinInst *BI);
MemBehavior visitStrongReleaseInst(StrongReleaseInst *BI);
MemBehavior visitReleaseValueInst(ReleaseValueInst *BI);
MemBehavior visitDestroyValueInst(DestroyValueInst *DVI);
MemBehavior visitSetDeallocatingInst(SetDeallocatingInst *BI);
MemBehavior visitBeginCOWMutationInst(BeginCOWMutationInst *BCMI);
MemBehavior visit##Name##ReleaseInst(Name##ReleaseInst *BI);
#include "swift/AST/ReferenceStorage.def"
// Instructions which are none if our SILValue does not alias one of its
// arguments. If we cannot prove such a thing, return the relevant memory
// behavior.
MemBehavior visit##Name(Name *I) { \
for (Operand & Op : I->getAllOperands()) { \
if (mayAlias(Op.get())) \
return I->getMemoryBehavior(); \
} \
return MemBehavior::None; \
// Override simple behaviors where MayHaveSideEffects is too general and
// encompasses other behavior that is not read/write/ref count decrement
// behavior we care about.
#define SIMPLE_MEMBEHAVIOR_INST(Name, Behavior) \
MemBehavior visit##Name(Name *I) { return MemBehavior::Behavior; }
// Incrementing reference counts doesn't have an observable memory effect.
MemBehavior visit##Name(Name *I) { \
return MemBehavior::None; \
#define UNCHECKED_REF_STORAGE(Name, ...) \
#include "swift/AST/ReferenceStorage.def"
} // end anonymous namespace
MemBehavior MemoryBehaviorVisitor::visitLoadInst(LoadInst *LI) {
if (!mayAlias(LI->getOperand()))
return MemBehavior::None;
LLVM_DEBUG(llvm::dbgs() << " Could not prove that load inst does not alias "
"pointer. ");
if (LI->getOwnershipQualifier() == LoadOwnershipQualifier::Take) {
LLVM_DEBUG(llvm::dbgs() << "Is a take so return MayReadWrite.\n");
return MemBehavior::MayReadWrite;
LLVM_DEBUG(llvm::dbgs() << "Not a take so returning MayRead.\n");
return MemBehavior::MayRead;
MemBehavior MemoryBehaviorVisitor::visitStoreInst(StoreInst *SI) {
// No store besides the initialization of a "let"-variable
// can have any effect on the value of this "let" variable.
if (isLetValue() && (getAccessBase(SI->getDest()) != getValueAddress())) {
return MemBehavior::None;
// If the store dest cannot alias the pointer in question and we are not
// releasing anything due to an assign, then the specified value cannot be
// modified by the store.
if (!mayAlias(SI->getDest()) &&
SI->getOwnershipQualifier() != StoreOwnershipQualifier::Assign)
return MemBehavior::None;
// Otherwise, a store just writes.
LLVM_DEBUG(llvm::dbgs() << " Could not prove store does not alias inst. "
"Returning default mem behavior.\n");
return SI->getMemoryBehavior();
MemBehavior MemoryBehaviorVisitor::visitCopyAddrInst(CopyAddrInst *CAI) {
// If it's an assign to the destination, a destructor might be called on the
// old value. This can have any side effects.
// We could also check if it's a trivial type (which cannot have any side
// effect on destruction), but such copy_addr instructions are optimized to
// load/stores anyway, so it's probably not worth it.
if (!CAI->isInitializationOfDest())
return MemBehavior::MayHaveSideEffects;
bool mayWrite = mayAlias(CAI->getDest());
bool mayRead = mayAlias(CAI->getSrc());
if (mayRead) {
if (mayWrite)
return MemBehavior::MayReadWrite;
// A take is modelled as a write. See MemoryBehavior::MayWrite.
if (CAI->isTakeOfSrc())
return MemBehavior::MayReadWrite;
return MemBehavior::MayRead;
if (mayWrite)
return MemBehavior::MayWrite;
return MemBehavior::None;
MemBehavior MemoryBehaviorVisitor::visitBuiltinInst(BuiltinInst *BI) {
// If our callee is not a builtin, be conservative and return may have side
// effects.
if (!BI) {
return MemBehavior::MayHaveSideEffects;
// If the builtin is read none, it does not read or write memory.
if (!BI->mayReadOrWriteMemory()) {
LLVM_DEBUG(llvm::dbgs() << " Found apply of read none builtin. Returning"
" None.\n");
return MemBehavior::None;
// If the builtin is side effect free, then it can only read memory.
if (!BI->mayHaveSideEffects()) {
LLVM_DEBUG(llvm::dbgs() << " Found apply of side effect free builtin. "
"Returning MayRead.\n");
return MemBehavior::MayRead;
// FIXME: If the value (or any other values from the instruction that the
// value comes from) that we are tracking does not escape and we don't alias
// any of the arguments of the apply inst, we should be ok.
// Otherwise be conservative and return that we may have side effects.
LLVM_DEBUG(llvm::dbgs() << " Found apply of side effect builtin. "
"Returning MayHaveSideEffects.\n");
return MemBehavior::MayHaveSideEffects;
MemBehavior MemoryBehaviorVisitor::visitTryApplyInst(TryApplyInst *AI) {
return getApplyBehavior(AI);
MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
return getApplyBehavior(AI);
MemBehavior MemoryBehaviorVisitor::visitBeginApplyInst(BeginApplyInst *AI) {
return getApplyBehavior(AI);
MemBehavior MemoryBehaviorVisitor::visitEndApplyInst(EndApplyInst *EAI) {
return getApplyBehavior(EAI->getBeginApply());
MemBehavior MemoryBehaviorVisitor::visitAbortApplyInst(AbortApplyInst *AAI) {
return getApplyBehavior(AAI->getBeginApply());
/// Returns true if the \p address may have any users which let the address
/// escape in an unusual way, e.g. with an address_to_pointer instruction.
static bool hasEscapingUses(SILValue address, int &numChecks) {
for (Operand *use : address->getUses()) {
SILInstruction *user = use->getUser();
// Avoid quadratic complexity in corner cases. A limit of 24 is more than
// enough in most cases.
if (++numChecks > 24)
return true;
switch (user->getKind()) {
case SILInstructionKind::DebugValueAddrInst:
case SILInstructionKind::FixLifetimeInst:
case SILInstructionKind::LoadInst:
case SILInstructionKind::StoreInst:
case SILInstructionKind::CopyAddrInst:
case SILInstructionKind::DestroyAddrInst:
case SILInstructionKind::DeallocStackInst:
case SILInstructionKind::EndAccessInst:
// Those instructions have no result and cannot escape the address.
case SILInstructionKind::ApplyInst:
case SILInstructionKind::TryApplyInst:
case SILInstructionKind::BeginApplyInst:
// Apply instructions can not let an address escape either. It's not
// possible that an address, passed as an indirect parameter, escapes
// the function in any way (which is not unsafe and undefined behavior).
case SILInstructionKind::BeginAccessInst:
case SILInstructionKind::OpenExistentialAddrInst:
case SILInstructionKind::UncheckedTakeEnumDataAddrInst:
case SILInstructionKind::StructElementAddrInst:
case SILInstructionKind::TupleElementAddrInst:
case SILInstructionKind::UncheckedAddrCastInst:
// Check the uses of address projections.
if (hasEscapingUses(cast<SingleValueInstruction>(user), numChecks))
return true;
case SILInstructionKind::AddressToPointerInst:
// This is _the_ instruction which can let an address escape.
return true;
// To be conservative, also bail for anything we don't handle here.
return true;
return false;
MemBehavior MemoryBehaviorVisitor::getApplyBehavior(FullApplySite AS) {
// Do a quick check first: if V is directly passed to an in_guaranteed
// argument, we know that the function cannot write to it.
for (Operand &argOp : AS.getArgumentOperands()) {
if (argOp.get() == V &&
AS.getArgumentConvention(argOp) ==
swift::SILArgumentConvention::Indirect_In_Guaranteed) {
return MemBehavior::MayRead;
SILValue object = getUnderlyingObject(V);
int numUsesChecked = 0;
// For exclusive/local addresses we can do a quick and good check with alias
// analysis. For everything else we use escape analysis (see below).
// TODO: The check for not-escaping can probably done easier with the upcoming
// API of AccessStorage.
bool nonEscapingAddress =
(isa<AllocStackInst>(object) || isExclusiveArgument(object)) &&
!hasEscapingUses(object, numUsesChecked);
FunctionSideEffects applyEffects;
SEA->getCalleeEffects(applyEffects, AS);
MemBehavior behavior = MemBehavior::None;
MemBehavior globalBehavior = applyEffects.getGlobalEffects().getMemBehavior(
// If it's a non-escaping address, we don't care about the "global" effects
// of the called function.
if (!nonEscapingAddress)
behavior = globalBehavior;
// Check all parameter effects.
for (unsigned argIdx = 0, end = AS.getNumArguments();
argIdx < end && behavior < MemBehavior::MayHaveSideEffects;
++argIdx) {
SILValue arg = AS.getArgument(argIdx);
// In case the argument is not an address, alias analysis will always report
// a no-alias. Therefore we have to treat non-address arguments
// conservatively here. For example V could be a ref_element_addr of a
// reference argument. In this case V clearly "aliases" the argument, but
// this is not reported by alias analysis.
if ((!nonEscapingAddress && !arg->getType().isAddress()) ||
mayAlias(arg)) {
MemBehavior argBehavior = applyEffects.getArgumentBehavior(AS, argIdx);
behavior = combineMemoryBehavior(behavior, argBehavior);
if (behavior > MemBehavior::None) {
if (behavior > MemBehavior::MayRead && isLetValue())
behavior = MemBehavior::MayRead;
// Ask escape analysis.
if (!EA->canEscapeTo(V, AS))
behavior = MemBehavior::None;
LLVM_DEBUG(llvm::dbgs() << " Found apply, returning " << behavior << '\n');
return behavior;
MemoryBehaviorVisitor::visitStrongReleaseInst(StrongReleaseInst *SI) {
if (!EA->canEscapeTo(V, SI))
return MemBehavior::None;
return MemBehavior::MayHaveSideEffects;
MemBehavior \
MemoryBehaviorVisitor::visit##Name##ReleaseInst(Name##ReleaseInst *SI) { \
if (!EA->canEscapeTo(V, SI)) \
return MemBehavior::None; \
return MemBehavior::MayHaveSideEffects; \
#include "swift/AST/ReferenceStorage.def"
MemBehavior MemoryBehaviorVisitor::visitReleaseValueInst(ReleaseValueInst *SI) {
if (!EA->canEscapeTo(V, SI))
return MemBehavior::None;
return MemBehavior::MayHaveSideEffects;
MemoryBehaviorVisitor::visitDestroyValueInst(DestroyValueInst *DVI) {
if (!EA->canEscapeTo(V, DVI))
return MemBehavior::None;
return MemBehavior::MayHaveSideEffects;
MemBehavior MemoryBehaviorVisitor::visitSetDeallocatingInst(SetDeallocatingInst *SDI) {
return MemBehavior::None;
MemBehavior MemoryBehaviorVisitor::
visitBeginCOWMutationInst(BeginCOWMutationInst *BCMI) {
// begin_cow_mutation is defined to have side effects, because it has
// dependencies with instructions which retain the buffer operand.
// But it never interferes with any memory address.
return MemBehavior::None;
// Top Level Entrypoint
AliasAnalysis::computeMemoryBehavior(SILInstruction *Inst, SILValue V) {
MemBehaviorKeyTy Key = toMemoryBehaviorKey(Inst, V);
// Check if we've already computed this result.
auto It = MemoryBehaviorCache.find(Key);
if (It != MemoryBehaviorCache.end()) {
return It->second;
// Flush the cache if the size of the cache is too large.
if (MemoryBehaviorCache.size() > MemoryBehaviorAnalysisMaxCacheSize) {
// Key is no longer valid as we cleared the MemoryBehaviorNodeToIndex.
Key = toMemoryBehaviorKey(Inst, V);
// Calculate the aliasing result and store it in the cache.
auto Result = computeMemoryBehaviorInner(Inst, V);
MemoryBehaviorCache[Key] = Result;
return Result;
AliasAnalysis::computeMemoryBehaviorInner(SILInstruction *Inst, SILValue V) {
LLVM_DEBUG(llvm::dbgs() << "GET MEMORY BEHAVIOR FOR:\n " << *Inst << " "
<< *V);
assert(SEA && "SideEffectsAnalysis must be initialized!");
return MemoryBehaviorVisitor(this, SEA, EA, V).visit(Inst);
MemBehaviorKeyTy AliasAnalysis::toMemoryBehaviorKey(SILInstruction *V1,
SILValue V2) {
size_t idx1 =
assert(idx1 != std::numeric_limits<size_t>::max() &&
"~0 index reserved for empty/tombstone keys");
size_t idx2 = MemoryBehaviorNodeToIndex.getIndex(
assert(idx2 != std::numeric_limits<size_t>::max() &&
"~0 index reserved for empty/tombstone keys");
return {idx1, idx2};