blob: 6e47743ba33101517e1cbe5a53c5632bb221f5ed [file] [log] [blame]
//===--- AliasAnalysis.cpp - SIL Alias Analysis ---------------------------===//
// 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-aa"
#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
#include "swift/SIL/InstructionUtils.h"
#include "swift/SIL/Projection.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILModule.h"
#include "swift/SIL/SILValue.h"
#include "swift/SILOptimizer/Analysis/EscapeAnalysis.h"
#include "swift/SILOptimizer/Analysis/SideEffectAnalysis.h"
#include "swift/SILOptimizer/Analysis/ValueTracking.h"
#include "swift/SILOptimizer/PassManager/PassManager.h"
#include "swift/SILOptimizer/Utils/InstOptUtils.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace swift;
// The AliasAnalysis Cache must not grow beyond this size.
// We limit the size of the AA cache to 2**14 because we want to limit the
// memory usage of this cache.
static const int AliasAnalysisMaxCacheSize = 16384;
// AA Debugging
#ifndef NDEBUG
namespace {
enum class AAKind : unsigned {
} // end anonymous namespace
static llvm::cl::opt<AAKind>
DebugAAKinds("aa-kind", llvm::cl::desc("Alias Analysis Kinds:"),
"Do not perform any AA"),
static inline bool shouldRunAA() {
return unsigned(AAKind(DebugAAKinds));
static inline bool shouldRunTypedAccessTBAA() {
return unsigned(AAKind(DebugAAKinds)) & unsigned(AAKind::TypedAccessTBAA);
static inline bool shouldRunBasicAA() {
return unsigned(AAKind(DebugAAKinds)) & unsigned(AAKind::BasicAA);
// Utilities
using AliasResult = AliasAnalysis::AliasResult;
llvm::raw_ostream &swift::operator<<(llvm::raw_ostream &OS, AliasResult R) {
switch (R) {
case AliasResult::NoAlias: return OS << "NoAlias";
case AliasResult::MayAlias: return OS << "MayAlias";
case AliasResult::PartialAlias: return OS << "PartialAlias";
case AliasResult::MustAlias: return OS << "MustAlias";
llvm_unreachable("Unhandled AliasResult in switch.");
// Return the address of the directly accessed memory. If either the address is
// unknown, or any other memory is accessed via indirection, return an invalid
// SILValue.
SILValue getDirectlyAccessedMemory(SILInstruction *User) {
if (auto *LI = dyn_cast<LoadInst>(User)) {
return LI->getOperand();
if (auto *SI = dyn_cast<StoreInst>(User)) {
return SI->getDest();
return SILValue();
// Unequal Base Object AA
/// Return true if the given SILArgument is an argument to the first BB of a
/// function.
static bool isFunctionArgument(SILValue V) {
return isa<SILFunctionArgument>(V);
/// Return true if V is an object that at compile time can be uniquely
/// identified.
static bool isIdentifiableObject(SILValue V) {
if (isa<AllocationInst>(V) || isa<LiteralInst>(V))
return true;
if (isExclusiveArgument(V))
return true;
return false;
/// Return true if V1 and V2 are distinct objects that can be uniquely
/// identified at compile time.
static bool areDistinctIdentifiableObjects(SILValue V1, SILValue V2) {
// Do both values refer to the same global variable?
if (auto *GA1 = dyn_cast<GlobalAddrInst>(V1)) {
if (auto *GA2 = dyn_cast<GlobalAddrInst>(V2)) {
return GA1->getReferencedGlobal() != GA2->getReferencedGlobal();
if (isIdentifiableObject(V1) && isIdentifiableObject(V2))
return V1 != V2;
return false;
/// Returns true if both values are equal or yield the address of the same
/// global variable.
static bool isSameValueOrGlobal(SILValue V1, SILValue V2) {
if (V1 == V2)
return true;
// Do both values refer to the same global variable?
if (auto *GA1 = dyn_cast<GlobalAddrInst>(V1)) {
if (auto *GA2 = dyn_cast<GlobalAddrInst>(V2)) {
return GA1->getReferencedGlobal() == GA2->getReferencedGlobal();
return false;
/// Is this a literal which we know cannot refer to a global object?
/// FIXME: function_ref?
static bool isLocalLiteral(SILValue V) {
switch (V->getKind()) {
case ValueKind::IntegerLiteralInst:
case ValueKind::FloatLiteralInst:
case ValueKind::StringLiteralInst:
return true;
return false;
/// Is this a value that can be unambiguously identified as being defined at the
/// function level.
static bool isIdentifiedFunctionLocal(SILValue V) {
return isa<AllocationInst>(*V) || isExclusiveArgument(V) || isLocalLiteral(V);
/// Returns true if we can prove that the two input SILValues which do not equal
/// cannot alias.
static bool aliasUnequalObjects(SILValue O1, SILValue O2) {
assert(O1 != O2 && "This function should only be called on unequal values.");
// If O1 and O2 do not equal and they are both values that can be statically
// and uniquely identified, they cannot alias.
if (areDistinctIdentifiableObjects(O1, O2)) {
LLVM_DEBUG(llvm::dbgs() << " Found two unequal identified "
return true;
// Function arguments can't alias with things that are known to be
// unambiguously identified at the function level.
// Note that both function arguments must be identified. For example, an @in
// argument may be an interior pointer into a box that is passed separately as
// @owned. We must consider uses on the @in argument as potential uses of the
// @owned object.
if ((isFunctionArgument(O1) && isIdentifiedFunctionLocal(O2)) ||
(isFunctionArgument(O2) && isIdentifiedFunctionLocal(O1))) {
LLVM_DEBUG(llvm::dbgs() << " Found unequal function arg and "
"identified function local!\n");
return true;
// We failed to prove that the two objects are different.
return false;
// Projection Address AA
/// Uses a bunch of ad-hoc rules to disambiguate a GEP instruction against
/// another pointer. We know that V1 is a GEP, but we don't know anything about
/// V2. O1, O2 are getUnderlyingObject of V1, V2 respectively.
AliasResult AliasAnalysis::aliasAddressProjection(SILValue V1, SILValue V2,
SILValue O1, SILValue O2) {
// If V2 is also a gep instruction with a must-alias or not-aliasing base
// pointer, figure out if the indices of the GEPs tell us anything about the
// derived pointers.
if (!Projection::isAddressProjection(V2)) {
// Ok, V2 is not an address projection. See if V2 after stripping casts
// aliases O1. If so, then we know that V2 must partially alias V1 via a
// must alias relation on O1. This ensures that given an alloc_stack and a
// gep from that alloc_stack, we say that they partially alias.
if (isSameValueOrGlobal(O1, stripCasts(V2)))
return AliasResult::PartialAlias;
return AliasResult::MayAlias;
assert(!Projection::isAddressProjection(O1) &&
"underlying object may not be a projection");
assert(!Projection::isAddressProjection(O2) &&
"underlying object may not be a projection");
// Do the base pointers alias?
AliasResult BaseAlias = aliasInner(O1, O2);
// If the underlying objects are not aliased, the projected values are also
// not aliased.
if (BaseAlias == AliasResult::NoAlias)
return AliasResult::NoAlias;
// Let's do alias checking based on projections.
auto V1Path = ProjectionPath::getProjectionPath(O1, V1);
auto V2Path = ProjectionPath::getProjectionPath(O2, V2);
// getUnderlyingPath and findAddressProjectionPathBetweenValues disagree on
// what the base pointer of the two values are. Be conservative and return
// MayAlias.
// FIXME: The only way this should happen realistically is if there are
// casts in between two projection instructions. getUnderlyingObject will
// ignore that, while findAddressProjectionPathBetweenValues wont. The two
// solutions are to make address projections variadic (something on the wee
// horizon) or enable Projection to represent a cast as a special sort of
// projection.
if (!V1Path || !V2Path)
return AliasResult::MayAlias;
auto R = V1Path->computeSubSeqRelation(*V2Path);
// If all of the projections are equal (and they have the same base pointer),
// the two GEPs must be the same.
if (BaseAlias == AliasResult::MustAlias &&
R == SubSeqRelation_t::Equal)
return AliasResult::MustAlias;
// The two GEPs do not alias if they are accessing different fields, even if
// we don't know the base pointers. Different fields should not overlap.
// TODO: Replace this with a check on the computed subseq relation. See the
// TODO in computeSubSeqRelation.
if (V1Path->hasNonEmptySymmetricDifference(V2Path.getValue()))
return AliasResult::NoAlias;
// If one of the GEPs is a super path of the other then they partially
// alias.
if (BaseAlias == AliasResult::MustAlias &&
return AliasResult::PartialAlias;
// We failed to prove anything. Be conservative and return MayAlias.
return AliasResult::MayAlias;
/// Is this an instruction that can act as a type "oracle" allowing typed access
/// TBAA to know what the real types associated with the SILInstruction are.
static bool isTypedAccessOracle(SILInstruction *I) {
switch (I->getKind()) {
case SILInstructionKind::RefElementAddrInst:
case SILInstructionKind::RefTailAddrInst:
case SILInstructionKind::StructElementAddrInst:
case SILInstructionKind::TupleElementAddrInst:
case SILInstructionKind::UncheckedTakeEnumDataAddrInst:
case SILInstructionKind::LoadInst:
case SILInstructionKind::StoreInst:
case SILInstructionKind::AllocStackInst:
case SILInstructionKind::AllocBoxInst:
case SILInstructionKind::ProjectBoxInst:
case SILInstructionKind::DeallocStackInst:
case SILInstructionKind::DeallocBoxInst:
return true;
return false;
/// Return true if the given value is an instruction or block argument that is
/// known to produce a nonaliasing address with respect to TBAA rules (i.e. the
/// pointer is not type punned). The only way to produce an aliasing typed
/// address is with pointer_to_address (via UnsafePointer) or
/// unchecked_addr_cast (via Builtin.reinterpretCast). Consequently, if the
/// given value is directly derived from a memory location, it cannot
/// alias. Call arguments also cannot alias because they must follow \@in, @out,
/// @inout, or \@in_guaranteed conventions.
static bool isAccessedAddressTBAASafe(SILValue V) {
if (!V->getType().isAddress())
return false;
SILValue accessedAddress = getTypedAccessAddress(V);
if (isa<SILFunctionArgument>(accessedAddress))
return true;
if (auto *PtrToAddr = dyn_cast<PointerToAddressInst>(accessedAddress))
return PtrToAddr->isStrict();
switch (accessedAddress->getKind()) {
return false;
case ValueKind::AllocStackInst:
case ValueKind::ProjectBoxInst:
case ValueKind::RefElementAddrInst:
case ValueKind::RefTailAddrInst:
return true;
/// Look at the origin/user ValueBase of V to see if any of them are
/// TypedAccessOracle which enable one to ascertain via undefined behavior the
/// "true" type of the instruction.
static SILType findTypedAccessType(SILValue V) {
// First look at the origin of V and see if we have any instruction that is a
// typed oracle.
// TODO: MultiValueInstruction
if (auto *I = dyn_cast<SingleValueInstruction>(V))
if (isTypedAccessOracle(I))
return V->getType();
// Then look at any uses of V that potentially could act as a typed access
// oracle.
for (auto Use : V->getUses())
if (isTypedAccessOracle(Use->getUser()))
return V->getType();
// Otherwise return an empty SILType
return SILType();
SILType swift::computeTBAAType(SILValue V) {
if (isAccessedAddressTBAASafe(V))
return findTypedAccessType(V);
// FIXME: add ref_element_addr check here. TBAA says that objects cannot be
// type punned.
return SILType();
static bool typedAccessTBAABuiltinTypesMayAlias(SILType LTy, SILType RTy) {
assert(LTy != RTy && "LTy should have already been shown to not equal RTy to "
"call this function.");
// If either of our types are raw pointers, they may alias any builtin.
if (<BuiltinRawPointerType>() ||<BuiltinRawPointerType>())
return true;
// At this point, we have 3 possibilities:
// 1. (Pointer, Scalar): A pointer to a pointer can never alias a scalar.
// 2. (Pointer, Pointer): If we have two pointers to pointers, since we know
// that the two values do not equal due to previous AA calculations, one must
// be a native object and the other is an unknown object type (i.e. an objc
// object) which cannot alias.
// 3. (Scalar, Scalar): If we have two scalar pointers, since we know that the
// types are already not equal, we know that they cannot alias. For those
// unfamiliar even though BuiltinIntegerType/BuiltinFloatType are single
// classes, the AST represents each integer/float of different bit widths as
// different types, so equality of SILTypes allows us to know that they have
// different bit widths.
// Thus we can just return false since in none of the aforementioned cases we
// cannot alias, so return false.
return false;
/// return True if the types \p LTy and \p RTy may alias.
/// Currently this only implements typed access based TBAA. See the TBAA section
/// in the SIL reference manual.
static bool typedAccessTBAAMayAlias(SILType LTy, SILType RTy,
const SILFunction &F) {
#ifndef NDEBUG
if (!shouldRunTypedAccessTBAA())
return true;
// If the two types are the same they may alias.
if (LTy == RTy)
return true;
// Typed access based TBAA only occurs on pointers. If we reach this point and
// do not have a pointer, be conservative and return that the two types may
// alias.
if (!LTy.isAddress() || !RTy.isAddress())
return true;
// If the types have unbound generic arguments then we don't know
// the possible range of the type. A type such as $Array<Int> may
// alias $Array<T>. Right now we are conservative and we assume
// that $UnsafeMutablePointer<T> and $Int may alias.
if (LTy.hasArchetype() || RTy.hasArchetype())
return true;
// If either type is a protocol type, we don't know the underlying type so
// return may alias.
// FIXME: We could be significantly smarter here by using the protocol
// hierarchy.
if (LTy.isAnyExistentialType() || RTy.isAnyExistentialType())
return true;
// If either type is an address only type, bail so we are conservative.
if (LTy.isAddressOnly(F) || RTy.isAddressOnly(F))
return true;
// If both types are builtin types, handle them separately.
if (<BuiltinType>() &&<BuiltinType>())
return typedAccessTBAABuiltinTypesMayAlias(LTy, RTy);
// Otherwise, we know that at least one of our types is not a builtin
// type. If we have a builtin type, canonicalize it on the right.
if (<BuiltinType>())
std::swap(LTy, RTy);
// If RTy is a builtin raw pointer type, it can alias anything.
if (<BuiltinRawPointerType>())
return true;
ClassDecl *LTyClass = LTy.getClassOrBoundGenericClass();
// The Builtin reference types can alias any class instance.
if (LTyClass) {
if (<BuiltinNativeObjectType>() ||<BuiltinBridgeObjectType>()) {
return true;
auto &Mod = F.getModule();
// If one type is an aggregate and it contains the other type then the record
// reference may alias the aggregate reference.
if (LTy.aggregateContainsRecord(RTy, Mod, F.getTypeExpansionContext()) ||
RTy.aggregateContainsRecord(LTy, Mod, F.getTypeExpansionContext()))
return true;
// FIXME: All the code following could be made significantly more aggressive
// by saying that aggregates of the same type that do not contain each other
// cannot alias.
// Tuples do not alias non-tuples.
bool LTyTT =<TupleType>();
bool RTyTT =<TupleType>();
if ((LTyTT && !RTyTT) || (!LTyTT && RTyTT))
return false;
// Structs do not alias non-structs.
StructDecl *LTyStruct = LTy.getStructOrBoundGenericStruct();
StructDecl *RTyStruct = RTy.getStructOrBoundGenericStruct();
if ((LTyStruct && !RTyStruct) || (!LTyStruct && RTyStruct))
return false;
// Enums do not alias non-enums.
EnumDecl *LTyEnum = LTy.getEnumOrBoundGenericEnum();
EnumDecl *RTyEnum = RTy.getEnumOrBoundGenericEnum();
if ((LTyEnum && !RTyEnum) || (!LTyEnum && RTyEnum))
return false;
// Classes do not alias non-classes.
ClassDecl *RTyClass = RTy.getClassOrBoundGenericClass();
if ((LTyClass && !RTyClass) || (!LTyClass && RTyClass))
return false;
// Classes with separate class hierarchies do not alias.
if (!LTy.isBindableToSuperclassOf(RTy) && !RTy.isBindableToSuperclassOf(LTy))
return false;
// Otherwise be conservative and return that the two types may alias.
return true;
bool AliasAnalysis::typesMayAlias(SILType T1, SILType T2,
const SILFunction &F) {
// Both types need to be valid.
if (!T2 || !T1)
return true;
// Check if we've already computed the TBAA relation.
auto Key = std::make_pair(T1, T2);
auto Res = TypesMayAliasCache.find(Key);
if (Res != TypesMayAliasCache.end()) {
return Res->second;
bool MA = typedAccessTBAAMayAlias(T1, T2, F);
TypesMayAliasCache[Key] = MA;
return MA;
// Entry Points
/// The main AA entry point. Performs various analyses on V1, V2 in an attempt
/// to disambiguate the two values.
AliasResult AliasAnalysis::alias(SILValue V1, SILValue V2,
SILType TBAAType1, SILType TBAAType2) {
AliasKeyTy Key = toAliasKey(V1, V2, TBAAType1, TBAAType2);
// Check if we've already computed this result.
auto It = AliasCache.find(Key);
if (It != AliasCache.end()) {
return It->second;
// Flush the cache if the size of the cache is too large.
if (AliasCache.size() > AliasAnalysisMaxCacheSize) {
// Key is no longer valid as we cleared the AliasValueBaseToIndex.
Key = toAliasKey(V1, V2, TBAAType1, TBAAType2);
// Calculate the aliasing result and store it in the cache.
auto Result = aliasInner(V1, V2, TBAAType1, TBAAType2);
AliasCache[Key] = Result;
return Result;
/// Get the underlying object, looking through init_enum_data_addr and
/// init_existential_addr.
static SILValue stripInitEnumAndExistentialAddr(SILValue v) {
while (isa<InitEnumDataAddrInst>(v) || isa<InitExistentialAddrInst>(v)) {
v = getUnderlyingObject(cast<SingleValueInstruction>(v)->getOperand(0));
return v;
/// The main AA entry point. Performs various analyses on V1, V2 in an attempt
/// to disambiguate the two values.
AliasResult AliasAnalysis::aliasInner(SILValue V1, SILValue V2,
SILType TBAAType1,
SILType TBAAType2) {
#ifndef NDEBUG
// If alias analysis is disabled, always return may alias.
if (!shouldRunAA())
return AliasResult::MayAlias;
// If the two values equal, quickly return must alias.
if (isSameValueOrGlobal(V1, V2))
return AliasResult::MustAlias;
LLVM_DEBUG(llvm::dbgs() << "ALIAS ANALYSIS:\n V1: " << *V1
<< " V2: " << *V2);
// If this is SILUndef, return may alias.
if (!V1->getFunction())
return AliasResult::MayAlias;
// Pass in both the TBAA types so we can perform typed access TBAA and the
// actual types of V1, V2 so we can perform class based TBAA.
if (!typesMayAlias(TBAAType1, TBAAType2, *V1->getFunction()))
return AliasResult::NoAlias;
#ifndef NDEBUG
if (!shouldRunBasicAA())
return AliasResult::MayAlias;
// Strip off any casts on V1, V2.
V1 = stripCasts(V1);
V2 = stripCasts(V2);
LLVM_DEBUG(llvm::dbgs() << " After Cast Stripping V1:" << *V1);
LLVM_DEBUG(llvm::dbgs() << " After Cast Stripping V2:" << *V2);
// Ok, we need to actually compute an Alias Analysis result for V1, V2. Begin
// by finding the "base" of V1, V2 by stripping off all casts and GEPs.
SILValue O1 = getUnderlyingObject(V1);
SILValue O2 = getUnderlyingObject(V2);
LLVM_DEBUG(llvm::dbgs() << " Underlying V1:" << *O1);
LLVM_DEBUG(llvm::dbgs() << " Underlying V2:" << *O2);
// If the underlying objects are not equal, see if we can prove that they
// cannot be the same object. If we can, return No Alias.
// For this we even look through init_enum_data_addr and init_existential_addr.
SILValue StrippedO1 = stripInitEnumAndExistentialAddr(O1);
SILValue StrippedO2 = stripInitEnumAndExistentialAddr(O2);
if (StrippedO1 != StrippedO2 && aliasUnequalObjects(StrippedO1, StrippedO2))
return AliasResult::NoAlias;
// Ok, either O1, O2 are the same or we could not prove anything based off of
// their inequality.
// Next: ask escape analysis. This catches cases where we compare e.g. a
// non-escaping pointer with another (maybe escaping) pointer. Escape analysis
// uses the connection graph to check if the pointers may point to the same
// content.
// canPointToSameMemory must take the original pointers used for memory
// access, not the underlying object, because objects projections can be
// modeled by escape analysis as different content, and canPointToSameMemory
// assumes that only the pointer itself may be accessed here, not any other
// address that can be derived from this pointer.
if (!EA->canPointToSameMemory(V1, V2)) {
LLVM_DEBUG(llvm::dbgs() << " Found not-aliased objects based on "
"escape analysis\n");
return AliasResult::NoAlias;
// Now we climb up use-def chains and attempt to do tricks based off of GEPs.
// First if one instruction is a gep and the other is not, canonicalize our
// inputs so that V1 always is the instruction containing the GEP.
if (!Projection::isAddressProjection(V1) &&
Projection::isAddressProjection(V2)) {
std::swap(V1, V2);
std::swap(O1, O2);
// If V1 is an address projection, attempt to use information from the
// aggregate type tree to disambiguate it from V2.
if (Projection::isAddressProjection(V1)) {
AliasResult Result = aliasAddressProjection(V1, V2, O1, O2);
if (Result != AliasResult::MayAlias)
return Result;
// We could not prove anything. Be conservative and return that V1, V2 may
// alias.
return AliasResult::MayAlias;
bool AliasAnalysis::canApplyDecrementRefCount(FullApplySite FAS, SILValue Ptr) {
// If the connection graph is invalid due to a very large function, we also
// skip all other tests, which might take significant time for a very large
// function.
// This is a workaround for some quadratic complexity in ARCSequenceOpt.
// TODO: remove this check once ARCSequenceOpt is retired or the quadratic
// behavior is fixed.
auto *conGraph = EA->getConnectionGraph(FAS.getFunction());
if (!conGraph->isValid())
return true;
// Treat applications of no-return functions as decrementing ref counts. This
// causes the apply to become a sink barrier for ref count increments.
if (FAS.isCalleeNoReturn())
return true;
/// If the pointer cannot escape to the function we are done.
if (!EA->canEscapeTo(Ptr, FAS))
return false;
FunctionSideEffects ApplyEffects;
SEA->getCalleeEffects(ApplyEffects, FAS);
auto &GlobalEffects = ApplyEffects.getGlobalEffects();
if (ApplyEffects.mayReadRC() || GlobalEffects.mayRelease())
return true;
/// The function has no unidentified releases, so let's look at the arguments
// in detail.
for (unsigned Idx = 0, End = FAS.getNumArguments(); Idx < End; ++Idx) {
auto &ArgEffect = ApplyEffects.getParameterEffects()[Idx];
if (ArgEffect.mayRelease()) {
// The function may release this argument, so check if the pointer can
// escape to it.
if (EA->mayReleaseContent(FAS.getArgument(Idx), Ptr))
return true;
return false;
bool AliasAnalysis::canBuiltinDecrementRefCount(BuiltinInst *BI, SILValue Ptr) {
for (SILValue Arg : BI->getArguments()) {
// Exclude some types of arguments where Ptr can never escape to.
if (isa<MetatypeInst>(Arg))
if (Arg->getType().is<BuiltinIntegerType>())
// A builtin can only release an object if it can escape to one of the
// builtin's arguments. 'EscapeAnalysis::mayReleaseContent()' expects 'Arg'
// to be an owned reference and disallows addresses. Conservatively handle
// address type arguments as and conservatively treat all other values
// potential owned references.
if (Arg->getType().isAddress() || EA->mayReleaseContent(Arg, Ptr))
return true;
return false;
// If the deinit for releasedReference can release any values used by User, then
// this is an interference. (The retains that originally forced liveness of
// those values may have already been eliminated). Note that we only care about
// avoiding a dangling pointer. The memory side affects of Release are
// unordered.
// \p releasedReference must be a value that directly contains the references
// being released. It cannot be an address or other kind of pointer that
// indirectly releases a reference. Otherwise, the escape analysis query is
// invalid.
bool AliasAnalysis::mayValueReleaseInterfereWithInstruction(
SILInstruction *User, SILValue releasedReference) {
&& "an address is never a reference");
// If this instruction can not read or write any memory. Its OK.
if (!User->mayReadOrWriteMemory())
return false;
// Get a pointer to the memory directly accessed by 'Users' (either via an
// address or heap reference operand). If additional memory may be indirectly
// accessed by 'User', such as via an inout argument, then stop here because
// mayReleaseContent can only reason about one level of memory access.
// TODO: Handle @inout arguments by iterating over the apply arguments. For
// each argument find out if any reachable content can be released. This is
// slightly more involved than mayReleaseContent because it needs to check all
// connection graph nodes reachable from accessedPointer that don't pass
// through another stored reference.
SILValue accessedPointer = getDirectlyAccessedMemory(User);
if (!accessedPointer)
return true;
// If releasedReference can reach the first refcounted object reachable from
// accessedPointer, then releasing it early may destroy the object accessed by
// accessedPointer. Access to any objects beyond the first released refcounted
// object are irrelevant--they must already have sufficient refcount that they
// won't be released when releasing Ptr.
return EA->mayReleaseContent(releasedReference, accessedPointer);
void AliasAnalysis::initialize(SILPassManager *PM) {
SEA = PM->getAnalysis<SideEffectAnalysis>();
EA = PM->getAnalysis<EscapeAnalysis>();
SILAnalysis *swift::createAliasAnalysis(SILModule *M) {
return new AliasAnalysis(M);
AliasKeyTy AliasAnalysis::toAliasKey(SILValue V1, SILValue V2,
SILType Type1, SILType Type2) {
size_t idx1 = AliasValueBaseToIndex.getIndex(V1);
assert(idx1 != std::numeric_limits<size_t>::max() &&
"~0 index reserved for empty/tombstone keys");
size_t idx2 = AliasValueBaseToIndex.getIndex(V2);
assert(idx2 != std::numeric_limits<size_t>::max() &&
"~0 index reserved for empty/tombstone keys");
void *t1 = Type1.getOpaqueValue();
void *t2 = Type2.getOpaqueValue();
return {idx1, idx2, t1, t2};