mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
77dd9b2992
In many places, we're interested in whether a type with archetypes *might be* a superclass of another type with the right bindings, particularly in the optimizer. Provide a separate Type::isBindableToSuperclassOf method that performs this check. Use it in the devirtualizer to fix rdar://problem/24993618. Using it might unblock other places where the optimizer is conservative, but we can fix those separately.
724 lines
26 KiB
C++
724 lines
26 KiB
C++
//===--- AliasAnalysis.cpp - SIL Alias Analysis ---------------------------===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See http://swift.org/LICENSE.txt for license information
|
|
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#define DEBUG_TYPE "sil-aa"
|
|
#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
|
|
#include "swift/SILOptimizer/Analysis/ValueTracking.h"
|
|
#include "swift/SILOptimizer/Analysis/SideEffectAnalysis.h"
|
|
#include "swift/SILOptimizer/Analysis/EscapeAnalysis.h"
|
|
#include "swift/SILOptimizer/Utils/Local.h"
|
|
#include "swift/SILOptimizer/PassManager/PassManager.h"
|
|
#include "swift/SIL/Projection.h"
|
|
#include "swift/SIL/SILValue.h"
|
|
#include "swift/SIL/SILInstruction.h"
|
|
#include "swift/SIL/SILArgument.h"
|
|
#include "swift/SIL/SILFunction.h"
|
|
#include "swift/SIL/SILModule.h"
|
|
#include "swift/SIL/InstructionUtils.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 {
|
|
None=0,
|
|
BasicAA=1,
|
|
TypedAccessTBAA=2,
|
|
All=3,
|
|
};
|
|
|
|
} // end anonymous namespace
|
|
|
|
static llvm::cl::opt<AAKind>
|
|
DebugAAKinds("aa", llvm::cl::desc("Alias Analysis Kinds:"),
|
|
llvm::cl::init(AAKind::All),
|
|
llvm::cl::values(clEnumValN(AAKind::None,
|
|
"none",
|
|
"Do not perform any AA"),
|
|
clEnumValN(AAKind::BasicAA,
|
|
"basic-aa",
|
|
"basic-aa"),
|
|
clEnumValN(AAKind::TypedAccessTBAA,
|
|
"typed-access-tb-aa",
|
|
"typed-access-tb-aa"),
|
|
clEnumValN(AAKind::All,
|
|
"all",
|
|
"all"),
|
|
clEnumValEnd));
|
|
|
|
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);
|
|
}
|
|
|
|
#endif
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// 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";
|
|
}
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// 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) {
|
|
auto *Arg = dyn_cast<SILArgument>(V);
|
|
if (!Arg)
|
|
return false;
|
|
return Arg->isFunctionArg();
|
|
}
|
|
|
|
/// 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 (isNotAliasingArgument(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;
|
|
default:
|
|
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) || isNotAliasingArgument(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)) {
|
|
DEBUG(llvm::dbgs() << " Found two unequal identified "
|
|
"objects.\n");
|
|
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))) {
|
|
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 &&
|
|
isStrictSubSeqRelation(R))
|
|
return AliasResult::PartialAlias;
|
|
|
|
// We failed to prove anything. Be conservative and return MayAlias.
|
|
return AliasResult::MayAlias;
|
|
}
|
|
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// TBAA
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
/// 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 ValueKind::RefElementAddrInst:
|
|
case ValueKind::StructElementAddrInst:
|
|
case ValueKind::TupleElementAddrInst:
|
|
case ValueKind::UncheckedTakeEnumDataAddrInst:
|
|
case ValueKind::LoadInst:
|
|
case ValueKind::StoreInst:
|
|
case ValueKind::AllocStackInst:
|
|
case ValueKind::AllocBoxInst:
|
|
case ValueKind::ProjectBoxInst:
|
|
case ValueKind::DeallocStackInst:
|
|
case ValueKind::DeallocBoxInst:
|
|
return true;
|
|
default:
|
|
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.
|
|
///
|
|
/// FIXME: pointer_to_address should contain a flag that indicates whether the
|
|
/// address is aliasing. Currently, we aggressively assume that
|
|
/// pointer-to-address is never used for type punning, which is not yet
|
|
/// clearly specified by our UnsafePointer API.
|
|
static bool isAddressRootTBAASafe(SILValue V) {
|
|
if (auto *Arg = dyn_cast<SILArgument>(V))
|
|
return Arg->isFunctionArg();
|
|
|
|
switch (V->getKind()) {
|
|
default:
|
|
return false;
|
|
case ValueKind::AllocStackInst:
|
|
case ValueKind::AllocBoxInst:
|
|
case ValueKind::PointerToAddressInst:
|
|
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.
|
|
if (auto *I = dyn_cast<SILInstruction>(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 (isAddressRootTBAASafe(getUnderlyingObject(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,
|
|
SILModule &Mod) {
|
|
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 (LTy.is<BuiltinRawPointerType>() || RTy.is<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;
|
|
}
|
|
|
|
/// \brief 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, SILModule &Mod) {
|
|
#ifndef NDEBUG
|
|
if (!shouldRunTypedAccessTBAA())
|
|
return true;
|
|
#endif
|
|
|
|
// 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(Mod) || RTy.isAddressOnly(Mod))
|
|
return true;
|
|
|
|
// If both types are builtin types, handle them separately.
|
|
if (LTy.is<BuiltinType>() && RTy.is<BuiltinType>())
|
|
return typedAccessTBAABuiltinTypesMayAlias(LTy, RTy, Mod);
|
|
|
|
// 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 (LTy.is<BuiltinType>())
|
|
std::swap(LTy, RTy);
|
|
|
|
// If RTy is a builtin raw pointer type, it can alias anything.
|
|
if (RTy.is<BuiltinRawPointerType>())
|
|
return true;
|
|
|
|
ClassDecl *LTyClass = LTy.getClassOrBoundGenericClass();
|
|
|
|
// The Builtin reference types can alias any class instance.
|
|
if (LTyClass) {
|
|
if (RTy.is<BuiltinUnknownObjectType>() ||
|
|
RTy.is<BuiltinNativeObjectType>() ||
|
|
RTy.is<BuiltinBridgeObjectType>()) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
// 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) ||
|
|
RTy.aggregateContainsRecord(LTy, Mod))
|
|
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 = LTy.is<TupleType>();
|
|
bool RTyTT = RTy.is<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) {
|
|
// 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, *Mod);
|
|
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) {
|
|
AliasCache.clear();
|
|
AliasValueBaseToIndex.clear();
|
|
|
|
// 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;
|
|
}
|
|
|
|
/// 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;
|
|
#endif
|
|
|
|
// If the two values equal, quickly return must alias.
|
|
if (isSameValueOrGlobal(V1, V2))
|
|
return AliasResult::MustAlias;
|
|
|
|
DEBUG(llvm::dbgs() << "ALIAS ANALYSIS:\n V1: " << *V1
|
|
<< " V2: " << *V2);
|
|
|
|
// 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))
|
|
return AliasResult::NoAlias;
|
|
|
|
#ifndef NDEBUG
|
|
if (!shouldRunBasicAA())
|
|
return AliasResult::MayAlias;
|
|
#endif
|
|
|
|
// Strip off any casts on V1, V2.
|
|
V1 = stripCasts(V1);
|
|
V2 = stripCasts(V2);
|
|
DEBUG(llvm::dbgs() << " After Cast Stripping V1:" << *V1);
|
|
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);
|
|
DEBUG(llvm::dbgs() << " Underlying V1:" << *O1);
|
|
DEBUG(llvm::dbgs() << " Underlying V2:" << *O2);
|
|
|
|
// If O1 and O2 do not equal, see if we can prove that they cannot be the
|
|
// same object. If we can, return No Alias.
|
|
if (O1 != O2 && aliasUnequalObjects(O1, O2))
|
|
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.
|
|
// Note that escape analysis must work with the original pointers and not the
|
|
// underlying objects because it treats projections differently.
|
|
if (!EA->canPointToSameMemory(V1, V2)) {
|
|
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) {
|
|
// Treat applications of @noreturn functions as decrementing ref counts. This
|
|
// causes the apply to become a sink barrier for ref count increments.
|
|
if (FAS.getCallee()->getType().getAs<SILFunctionType>()->isNoReturn())
|
|
return true;
|
|
|
|
/// If the pointer cannot escape to the function we are done.
|
|
if (!EA->canEscapeTo(Ptr, FAS))
|
|
return false;
|
|
|
|
SideEffectAnalysis::FunctionEffects ApplyEffects;
|
|
SEA->getEffects(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->canEscapeToValue(Ptr, FAS.getArgument(Idx)))
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool AliasAnalysis::canBuiltinDecrementRefCount(BuiltinInst *BI, SILValue Ptr) {
|
|
for (SILValue Arg : BI->getArguments()) {
|
|
// A builtin can only release an object if it can escape to one of the
|
|
// builtin's arguments.
|
|
if (EA->canEscapeToValue(Ptr, Arg))
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool swift::isLetPointer(SILValue V) {
|
|
// Traverse the "access" path for V and check that it starts with "let"
|
|
// and everything along this path is a value-type (i.e. struct or tuple).
|
|
|
|
// Is this an address of a "let" class member?
|
|
if (auto *REA = dyn_cast<RefElementAddrInst>(V))
|
|
return REA->getField()->isLet();
|
|
|
|
// Is this an address of a global "let"?
|
|
if (auto *GAI = dyn_cast<GlobalAddrInst>(V)) {
|
|
auto *GlobalDecl = GAI->getReferencedGlobal()->getDecl();
|
|
return GlobalDecl && GlobalDecl->isLet();
|
|
}
|
|
|
|
// Is this an address of a struct "let" member?
|
|
if (auto *SEA = dyn_cast<StructElementAddrInst>(V))
|
|
// Check if it is a "let" in the parent struct.
|
|
// Check if its parent is a "let".
|
|
return isLetPointer(SEA->getOperand());
|
|
|
|
|
|
// Check if a parent of a tuple is a "let"
|
|
if (TupleElementAddrInst *TEA = dyn_cast<TupleElementAddrInst>(V))
|
|
return isLetPointer(TEA->getOperand());
|
|
|
|
return false;
|
|
}
|
|
|
|
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};
|
|
}
|