mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
f9b524b1cb
The main changes are: *) Rewrite everything in swift. So far, parts of memory-behavior analysis were already implemented in swift. Now everything is done in swift and lives in `AliasAnalysis.swift`. This is a big code simplification. *) Support many more instructions in the memory-behavior analysis - especially OSSA instructions, like `begin_borrow`, `end_borrow`, `store_borrow`, `load_borrow`. The computation of end_borrow effects is now much more precise. Also, partial_apply is now handled more precisely. *) Simplify and reduce type-based alias analysis (TBAA). The complexity of the old TBAA comes from old days where the language and SIL didn't have strict aliasing and exclusivity rules (e.g. for inout arguments). Now TBAA is only needed for code using unsafe pointers. The new TBAA handles this - and not more. Note that TBAA for classes is already done in `AccessBase.isDistinct`. *) Handle aliasing in `begin_access [modify]` scopes. We already supported truly immutable scopes like `begin_access [read]` or `ref_element_addr [immutable]`. For `begin_access [modify]` we know that there are no other reads or writes to the access-address within the scope. *) Don't cache memory-behavior results. It turned out that the hit-miss rate was pretty bad (~ 1:7). The overhead of the cache lookup took as long as recomputing the memory behavior.
1009 lines
35 KiB
C++
1009 lines
35 KiB
C++
//===--- RefCountState.cpp ------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift.org 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 https://swift.org/LICENSE.txt for license information
|
|
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#define DEBUG_TYPE "arc-sequence-opts"
|
|
#include "RefCountState.h"
|
|
#include "RCStateTransition.h"
|
|
#include "swift/Basic/Assertions.h"
|
|
#include "llvm/Support/Compiler.h"
|
|
#include "llvm/Support/Debug.h"
|
|
|
|
using namespace swift;
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// Lattice State Merging
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
static inline BottomUpRefCountState::LatticeState
|
|
MergeBottomUpLatticeStates(BottomUpRefCountState::LatticeState L1,
|
|
BottomUpRefCountState::LatticeState L2) {
|
|
using LatticeState = BottomUpRefCountState::LatticeState;
|
|
// If both states equal, return the first.
|
|
if (L1 == L2)
|
|
return L1;
|
|
|
|
// If either are none, return None.
|
|
if (L1 == LatticeState::None || L2 == LatticeState::None)
|
|
return LatticeState::None;
|
|
|
|
// Canonicalize.
|
|
if (unsigned(L1) > unsigned(L2))
|
|
std::swap(L1, L2);
|
|
|
|
// Choose the side further along in the sequence.
|
|
if ((L1 == LatticeState::Decremented || L1 == LatticeState::MightBeUsed) ||
|
|
(L2 == LatticeState::MightBeUsed ||
|
|
L2 == LatticeState::MightBeDecremented))
|
|
return L2;
|
|
|
|
// Otherwise, we don't know what happened, be conservative and return none.
|
|
return LatticeState::None;
|
|
}
|
|
|
|
static inline TopDownRefCountState::LatticeState
|
|
MergeTopDownLatticeStates(TopDownRefCountState::LatticeState L1,
|
|
TopDownRefCountState::LatticeState L2) {
|
|
using LatticeState = TopDownRefCountState::LatticeState;
|
|
// If both states equal, return the first.
|
|
if (L1 == L2)
|
|
return L1;
|
|
|
|
// If either are none, return None.
|
|
if (L1 == LatticeState::None || L2 == LatticeState::None)
|
|
return LatticeState::None;
|
|
|
|
// Canonicalize.
|
|
if (unsigned(L1) > unsigned(L2))
|
|
std::swap(L1, L2);
|
|
|
|
// Choose the side further along in the sequence.
|
|
if ((L1 == LatticeState::Incremented ||
|
|
L1 == LatticeState::MightBeDecremented) ||
|
|
(L2 == LatticeState::MightBeDecremented ||
|
|
L2 == LatticeState::MightBeUsed))
|
|
return L2;
|
|
|
|
// Otherwise, we don't know what happened, return none.
|
|
return LatticeState::None;
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// Bottom Up Ref Count State
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
/// Initializes/reinitialized the state for I. If we reinitialize we return
|
|
/// true.
|
|
bool BottomUpRefCountState::initWithMutatorInst(
|
|
ImmutablePointerSet<SILInstruction *> *I, RCIdentityFunctionInfo *RCFI) {
|
|
assert(I->size() == 1);
|
|
SILInstruction *Inst = *I->begin();
|
|
assert((isa<StrongReleaseInst>(Inst) || isa<ReleaseValueInst>(Inst)) &&
|
|
"strong_release and release_value are only supported.");
|
|
(void) Inst;
|
|
|
|
bool NestingDetected = SuperTy::initWithMutatorInst(I, RCFI);
|
|
|
|
// If we know that there is another decrement on the same pointer that has
|
|
// not been matched up to an increment, then the pointer must have a
|
|
// reference count of at least 2 before this decrement. This implies it is
|
|
// known safe.
|
|
KnownSafe = NestingDetected;
|
|
|
|
// If we saw a non arc user that will keep this value alive, set known safe
|
|
// since we will not move non-arc instructions.
|
|
KnownSafe |= FoundNonARCUser;
|
|
|
|
// Set our lattice state to be decremented.
|
|
LatState = LatticeState::Decremented;
|
|
|
|
return NestingDetected;
|
|
}
|
|
|
|
/// Return true if we *might* remove this instruction.
|
|
///
|
|
/// This is a conservative query given the information we know, so as we
|
|
/// perform the dataflow it may change value.
|
|
bool BottomUpRefCountState::mightRemoveMutators() {
|
|
if (LatState == LatticeState::None)
|
|
return false;
|
|
|
|
// We will not remove mutators if we have a might be decremented value that
|
|
// is not known safe.
|
|
return isCodeMotionSafe() || isKnownSafe();
|
|
}
|
|
|
|
/// Uninitialize the current state.
|
|
void BottomUpRefCountState::clear() {
|
|
// If we cannot conservatively prove that the given RefCountState will not
|
|
// be removed, be conservative and clear the transition state, so we do not
|
|
// propagate KnownSafety forward.
|
|
if (mightRemoveMutators())
|
|
Transition = RCStateTransition();
|
|
LatState = LatticeState::None;
|
|
SuperTy::clear();
|
|
}
|
|
|
|
/// If advance the state's sequence appropriately for a decrement. If we do
|
|
/// advance return true. Otherwise return false.
|
|
bool BottomUpRefCountState::isRefCountStateModified() const {
|
|
switch (LatState) {
|
|
case LatticeState::Decremented:
|
|
return true;
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::MightBeUsed:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled TermKind in switch.");
|
|
}
|
|
|
|
/// Returns true if given the current lattice state, do we care if the value
|
|
/// we are tracking is decremented.
|
|
bool BottomUpRefCountState::valueCanBeDecrementedGivenLatticeState() const {
|
|
switch (LatState) {
|
|
case LatticeState::MightBeUsed:
|
|
return true;
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::Decremented:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// If advance the state's sequence appropriately for a decrement. If we do
|
|
/// advance return true. Otherwise return false.
|
|
bool BottomUpRefCountState::handleDecrement() {
|
|
switch (LatState) {
|
|
case LatticeState::MightBeUsed:
|
|
LatState = LatticeState::MightBeDecremented;
|
|
return true;
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::Decremented:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Returns true if given the current lattice state, do we care if the value we
|
|
/// are tracking is used.
|
|
bool BottomUpRefCountState::valueCanBeUsedGivenLatticeState() const {
|
|
switch (LatState) {
|
|
case LatticeState::Decremented:
|
|
return true;
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::MightBeUsed:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Given the current lattice state, if we have seen a use, advance the
|
|
/// lattice state. Return true if we do so and false otherwise.
|
|
bool BottomUpRefCountState::handleUser() {
|
|
assert(valueCanBeUsedGivenLatticeState() &&
|
|
"Must be able to be used at this point of the lattice.");
|
|
|
|
// Advance the sequence...
|
|
switch (LatState) {
|
|
case LatticeState::Decremented:
|
|
LatState = LatticeState::MightBeUsed;
|
|
return true;
|
|
case LatticeState::MightBeUsed:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::None:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Returns true if given the current lattice state, do we care if the value
|
|
/// we are tracking is used.
|
|
bool BottomUpRefCountState::
|
|
valueCanBeGuaranteedUsedGivenLatticeState() const {
|
|
switch (LatState) {
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeDecremented:
|
|
return false;
|
|
case LatticeState::Decremented:
|
|
case LatticeState::MightBeUsed:
|
|
return true;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Given the current lattice state, if we have seen a use, advance the
|
|
/// lattice state. Return true if we do so and false otherwise.
|
|
bool BottomUpRefCountState::handleGuaranteedUser() {
|
|
assert(valueCanBeGuaranteedUsedGivenLatticeState() &&
|
|
"Must be able to be used at this point of the lattice.");
|
|
|
|
// Advance the sequence...
|
|
switch (LatState) {
|
|
case LatticeState::Decremented: {
|
|
LatState = LatticeState::MightBeDecremented;
|
|
return true;
|
|
}
|
|
case LatticeState::MightBeUsed:
|
|
LatState = LatticeState::MightBeDecremented;
|
|
return true;
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::None:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
// Returns true if the passed in ref count inst matches the ref count inst
|
|
// we are tracking. This handles generically retains/release.
|
|
bool BottomUpRefCountState::isRefCountInstMatchedToTrackedInstruction(
|
|
SILInstruction *RefCountInst) {
|
|
// If we are not tracking any state transitions bail.
|
|
if (!Transition.isValid())
|
|
return false;
|
|
|
|
// Otherwise, ask the transition state if this instruction causes a
|
|
// transition that can be matched with the transition in order to eliminate
|
|
// the transition.
|
|
if (!Transition.matchingInst(RefCountInst))
|
|
return false;
|
|
|
|
return handleRefCountInstMatch();
|
|
}
|
|
|
|
/// We have a matching ref count inst. Return true if we advance the sequence
|
|
/// and false otherwise.
|
|
bool BottomUpRefCountState::handleRefCountInstMatch() {
|
|
// Otherwise modify the state appropriately in preparation for removing the
|
|
// increment, decrement pair.
|
|
switch (LatState) {
|
|
case LatticeState::None:
|
|
return false;
|
|
case LatticeState::Decremented:
|
|
case LatticeState::MightBeUsed:
|
|
case LatticeState::MightBeDecremented:
|
|
return true;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
bool BottomUpRefCountState::merge(const BottomUpRefCountState &Other) {
|
|
|
|
auto NewState = MergeBottomUpLatticeStates(LatState, Other.LatState);
|
|
LLVM_DEBUG(llvm::dbgs() << " Performing BottomUp Merge.\n");
|
|
LLVM_DEBUG(llvm::dbgs() << " Left: " << LatState << "; Right: "
|
|
<< Other.LatState << "; Result: " << NewState <<"\n");
|
|
LLVM_DEBUG(llvm::dbgs() << " V: ";
|
|
if (hasRCRoot())
|
|
getRCRoot()->dump();
|
|
else
|
|
llvm::dbgs() << "\n";
|
|
llvm::dbgs() << " OtherV: ";
|
|
if (Other.hasRCRoot())
|
|
Other.getRCRoot()->dump();
|
|
else
|
|
llvm::dbgs() << "\n");
|
|
|
|
LatState = NewState;
|
|
KnownSafe &= Other.KnownSafe;
|
|
FoundNonARCUser &= Other.FoundNonARCUser;
|
|
|
|
// If we're doing a merge on a path that's previously seen a partial merge,
|
|
// conservatively drop the sequence, to avoid doing partial RR elimination. If
|
|
// the branch predicates for the two merge differ, mixing them is unsafe since
|
|
// they are not control dependent.
|
|
//
|
|
// TODO: Add support for working around control dependence issues.
|
|
if (LatState == BottomUpRefCountState::LatticeState::None) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Found LatticeState::None. "
|
|
"Clearing State!\n");
|
|
clear();
|
|
return false;
|
|
}
|
|
|
|
if (!Transition.isValid() || !Other.Transition.isValid() ||
|
|
!Transition.merge(Other.Transition)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Failed merge!\n");
|
|
clear();
|
|
return false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
// Check if PotentialGuaranteedUser can use the reference count associated with
|
|
// the value we are tracking. If so advance the state's sequence appropriately
|
|
// and return true. Otherwise return false.
|
|
bool BottomUpRefCountState::handlePotentialGuaranteedUser(
|
|
SILInstruction *PotentialGuaranteedUser, AliasAnalysis *AA) {
|
|
// If we are not tracking a ref count, just return false.
|
|
if (!isTrackingRefCount())
|
|
return false;
|
|
|
|
// If at the current lattice state, we don't care if the value we are
|
|
// tracking can be decremented or used, just return false.
|
|
//
|
|
// This causes us to only perform alias queries when we are at a lattice
|
|
// state where the alias queries will actually be used.
|
|
if (!valueCanBeGuaranteedUsedGivenLatticeState())
|
|
return false;
|
|
|
|
// If we can prove that Other cannot use the pointer we are tracking,
|
|
// return...
|
|
if (!mayGuaranteedUseValue(PotentialGuaranteedUser, getRCRoot(), AA))
|
|
return false;
|
|
|
|
// If we can prove that the pointer we are tracking cannot be decremented,
|
|
// return. On return, BottomUpRefCountState::handlePotentialUser can correctly
|
|
// handle transition of refcount state. It transitions from a Decrement
|
|
// refcount state to a MightBeUsed refcount state
|
|
if (!mayDecrementRefCount(PotentialGuaranteedUser, getRCRoot(), AA)) {
|
|
return false;
|
|
}
|
|
|
|
// Instructions that we do not recognize (and thus will not move) and that
|
|
// *must* use RCIdentity, implies we are always known safe as long as meet
|
|
// over all path constraints are satisfied.
|
|
if (isRCStateTransitionUnknown(PotentialGuaranteedUser->asSILNode()))
|
|
if (mustUseValue(PotentialGuaranteedUser, getRCRoot(), AA))
|
|
FoundNonARCUser = true;
|
|
|
|
// Otherwise, update the ref count state given the guaranteed user.
|
|
return handleGuaranteedUser();
|
|
}
|
|
|
|
/// Check if PotentialDecrement can decrement the reference count associated
|
|
/// with the value we are tracking. If so advance the state's sequence
|
|
/// appropriately and return true. Otherwise return false.
|
|
bool BottomUpRefCountState::handlePotentialDecrement(
|
|
SILInstruction *PotentialDecrement, AliasAnalysis *AA) {
|
|
// If we are not tracking a ref count, just return false.
|
|
if (!isTrackingRefCount())
|
|
return false;
|
|
|
|
// If at the current lattice state, we don't care if the value we are
|
|
// tracking can be decremented, just return false.
|
|
//
|
|
// This causes us to only perform alias queries when we are at a lattice
|
|
// state where the alias queries will actually be used.
|
|
if (!valueCanBeDecrementedGivenLatticeState())
|
|
return false;
|
|
|
|
// If we can prove that Other cannot use the pointer we are tracking,
|
|
// return...
|
|
if (!mayDecrementRefCount(PotentialDecrement, getRCRoot(), AA))
|
|
return false;
|
|
|
|
// Otherwise, allow the CRTP substruct to update itself given we have a
|
|
// potential decrement.
|
|
return handleDecrement();
|
|
}
|
|
|
|
// Check if PotentialUser could be a use of the reference counted value that
|
|
// requires user to be alive. If so advance the state's sequence
|
|
// appropriately and return true. Otherwise return false.
|
|
bool BottomUpRefCountState::handlePotentialUser(SILInstruction *PotentialUser,
|
|
AliasAnalysis *AA) {
|
|
|
|
// If we are not tracking a ref count, just return false.
|
|
if (!isTrackingRefCount())
|
|
return false;
|
|
|
|
// If at the current lattice state, we don't care if the value we are
|
|
// tracking can be used, just return false.
|
|
//
|
|
// This causes us to only perform alias queries when we are at a lattice
|
|
// state where the alias queries will actually be used.
|
|
if (!valueCanBeUsedGivenLatticeState())
|
|
return false;
|
|
|
|
if (!mayHaveSymmetricInterference(PotentialUser, getRCRoot(), AA))
|
|
return false;
|
|
|
|
// Instructions that we do not recognize (and thus will not move) and that
|
|
// *must* use RCIdentity, implies we are always known safe as long as meet
|
|
// over all path constraints are satisfied.
|
|
if (isRCStateTransitionUnknown(PotentialUser->asSILNode()))
|
|
if (mustUseValue(PotentialUser, getRCRoot(), AA))
|
|
FoundNonARCUser = true;
|
|
|
|
return handleUser();
|
|
}
|
|
|
|
void BottomUpRefCountState::updateForSameLoopInst(SILInstruction *I,
|
|
AliasAnalysis *AA) {
|
|
// If this state is not tracking anything, there is nothing to update.
|
|
if (!isTrackingRefCount())
|
|
return;
|
|
|
|
// Check if the instruction we are visiting could potentially use our
|
|
// instruction in a way that requires us to guarantee the lifetime of the
|
|
// pointer up to this point. This has the effect of performing a use and a
|
|
// decrement.
|
|
if (handlePotentialGuaranteedUser(I, AA)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Found Potential Guaranteed Use:\n "
|
|
<< getRCRoot());
|
|
return;
|
|
}
|
|
|
|
// Check if the instruction we are visiting could potentially decrement
|
|
// the reference counted value we are tracking... in a manner that could
|
|
// cause us to change states. If we do change states continue...
|
|
if (handlePotentialDecrement(I, AA)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Found Potential Decrement:\n "
|
|
<< getRCRoot());
|
|
return;
|
|
}
|
|
|
|
// Otherwise check if the reference counted value we are tracking
|
|
// could be used by the given instruction.
|
|
if (!handlePotentialUser(I, AA))
|
|
return;
|
|
LLVM_DEBUG(llvm::dbgs() << " Found Potential Use:\n "
|
|
<< getRCRoot());
|
|
}
|
|
|
|
// Remove "KnownSafe" on the BottomUpRefCountState. If we find another unmatched
|
|
// retain instruction with a different aliasing RCIdentity or the same
|
|
// RCIdentity in the child region in the loop case.
|
|
void BottomUpRefCountState::checkAndResetKnownSafety(
|
|
SILInstruction *I, SILValue VisitedRC,
|
|
std::function<bool(SILInstruction *)> checkIfRefCountInstIsMatched,
|
|
RCIdentityFunctionInfo *RCIA, AliasAnalysis *AA) {
|
|
assert(VisitedRC);
|
|
// If the RefCountState was not marked "KnownSafe", there is nothing to do.
|
|
if (!isKnownSafe())
|
|
return;
|
|
assert(Transition.getKind() == RCStateTransitionKind::StrongDecrement);
|
|
// We only care about retain instructions that can potentially pair with a
|
|
// previously visited release.
|
|
if (!(isa<StrongRetainInst>(I) || isa<RetainValueInst>(I)))
|
|
return;
|
|
SILValue VisitingRC = RCIA->getRCIdentityRoot(I->getOperand(0));
|
|
assert(VisitingRC);
|
|
// If the visiting retain instruction was not already pair with a release
|
|
// instruction, return.
|
|
if (checkIfRefCountInstIsMatched(I))
|
|
return;
|
|
// If the VisitingRC and VisitedRC do not alias, they cannot be incorrectly
|
|
// paired.
|
|
if (!AA->mayAlias(VisitingRC, VisitedRC))
|
|
return;
|
|
LLVM_DEBUG(llvm::dbgs() << "Clearing KnownSafe for: ");
|
|
LLVM_DEBUG(VisitedRC->dump());
|
|
clearKnownSafe();
|
|
}
|
|
|
|
// This function is conservative enough that the flow sensitive nature of
|
|
// loop summarized instructions does not matter.
|
|
void BottomUpRefCountState::updateForDifferentLoopInst(SILInstruction *I,
|
|
AliasAnalysis *AA) {
|
|
// If we are not tracking anything, bail.
|
|
if (!isTrackingRefCount())
|
|
return;
|
|
|
|
if (valueCanBeGuaranteedUsedGivenLatticeState()) {
|
|
// Any instruction that may need guaranteed use or may decrement the
|
|
// refcount will turn off CodeMotionSafety
|
|
if (mayGuaranteedUseValue(I, getRCRoot(), AA) ||
|
|
mayDecrementRefCount(I, getRCRoot(), AA)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Found potential guaranteed use:\n "
|
|
<< getRCRoot());
|
|
handleGuaranteedUser();
|
|
return;
|
|
}
|
|
}
|
|
|
|
// We can just handle potential users normally, since if we handle the user we
|
|
// already saw a decrement implying that we will treat this like a guaranteed
|
|
// use.
|
|
if (!handlePotentialUser(I, AA))
|
|
return;
|
|
LLVM_DEBUG(llvm::dbgs() << " Found Potential Use:\n "
|
|
<< getRCRoot());
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// Top Down Ref Count State
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
/// Initializes/reinitialized the state for I. If we reinitialize we return
|
|
/// true.
|
|
bool TopDownRefCountState::initWithMutatorInst(
|
|
ImmutablePointerSet<SILInstruction *> *I, RCIdentityFunctionInfo *RCFI) {
|
|
assert(I->size() == 1);
|
|
SILInstruction *Inst = *I->begin();
|
|
(void)Inst;
|
|
assert((isa<StrongRetainInst>(Inst) || isa<RetainValueInst>(Inst)) &&
|
|
"strong_retain and retain_value are only supported.");
|
|
|
|
bool NestingDetected = SuperTy::initWithMutatorInst(I, RCFI);
|
|
|
|
// This retain is known safe if the operand we are tracking was already
|
|
// known incremented previously. This occurs when you have nested
|
|
// increments.
|
|
KnownSafe = isRefCountStateModified();
|
|
|
|
// Set our lattice state to be incremented.
|
|
LatState = LatticeState::Incremented;
|
|
|
|
return NestingDetected;
|
|
}
|
|
|
|
/// Initialize this ref count state with the @owned Arg at +1.
|
|
void TopDownRefCountState::initWithArg(SILFunctionArgument *Arg) {
|
|
LatState = LatticeState::Incremented;
|
|
Transition = RCStateTransition(Arg);
|
|
assert(Transition.getKind() == RCStateTransitionKind::StrongEntrance &&
|
|
"Expected a strong entrance here");
|
|
RCRoot = Arg;
|
|
KnownSafe = false;
|
|
}
|
|
|
|
/// Initialize this RefCountState with an instruction which introduces a new
|
|
/// ref count at +1.
|
|
void TopDownRefCountState::initWithEntranceInst(
|
|
ImmutablePointerSet<SILInstruction *> *I, SILValue RCIdentity) {
|
|
LatState = LatticeState::Incremented;
|
|
Transition = RCStateTransition(I);
|
|
assert(Transition.getKind() == RCStateTransitionKind::StrongEntrance &&
|
|
"Expected a strong entrance here");
|
|
RCRoot = RCIdentity;
|
|
KnownSafe = false;
|
|
}
|
|
|
|
/// Uninitialize the current state.
|
|
void TopDownRefCountState::clear() {
|
|
Transition = RCStateTransition();
|
|
LatState = LatticeState::None;
|
|
SuperTy::clear();
|
|
}
|
|
|
|
/// Can we guarantee that the given reference counted value has been modified?
|
|
bool TopDownRefCountState::isRefCountStateModified() const {
|
|
switch (LatState) {
|
|
case LatticeState::Incremented:
|
|
return true;
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::MightBeUsed:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Returns true if given the current lattice state, do we care if the value
|
|
/// we are tracking is decremented.
|
|
bool TopDownRefCountState::valueCanBeDecrementedGivenLatticeState() const {
|
|
switch (LatState) {
|
|
case LatticeState::Incremented:
|
|
return true;
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::MightBeUsed:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// If advance the state's sequence appropriately for a decrement. If we do
|
|
/// advance return true. Otherwise return false.
|
|
bool TopDownRefCountState::handleDecrement() {
|
|
switch (LatState) {
|
|
case LatticeState::Incremented:
|
|
LatState = LatticeState::MightBeDecremented;
|
|
return true;
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::MightBeUsed:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Returns true if given the current lattice state, do we care if the value
|
|
/// we are tracking is used.
|
|
bool TopDownRefCountState::valueCanBeUsedGivenLatticeState() const {
|
|
switch (LatState) {
|
|
case LatticeState::MightBeDecremented:
|
|
return true;
|
|
case LatticeState::None:
|
|
case LatticeState::Incremented:
|
|
case LatticeState::MightBeUsed:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Given the current lattice state, if we have seen a use, advance the
|
|
/// lattice state. Return true if we do so and false otherwise.
|
|
bool TopDownRefCountState::handleUser() {
|
|
assert(valueCanBeUsedGivenLatticeState() &&
|
|
"Must be able to be used at this point of the lattice.");
|
|
|
|
// Otherwise advance the sequence...
|
|
switch (LatState) {
|
|
case LatticeState::MightBeDecremented:
|
|
LatState = LatticeState::MightBeUsed;
|
|
return true;
|
|
case LatticeState::Incremented:
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeUsed:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Returns true if given the current lattice state, do we care if the value
|
|
/// we are tracking is used.
|
|
bool
|
|
TopDownRefCountState::
|
|
valueCanBeGuaranteedUsedGivenLatticeState() const {
|
|
switch (LatState) {
|
|
case LatticeState::None:
|
|
case LatticeState::MightBeUsed:
|
|
return false;
|
|
case LatticeState::Incremented:
|
|
case LatticeState::MightBeDecremented:
|
|
return true;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
/// Given the current lattice state, if we have seen a use, advance the
|
|
/// lattice state. Return true if we do so and false otherwise.
|
|
bool TopDownRefCountState::handleGuaranteedUser() {
|
|
assert(valueCanBeGuaranteedUsedGivenLatticeState() &&
|
|
"Must be able to be used at this point of the lattice.");
|
|
// Advance the sequence...
|
|
switch (LatState) {
|
|
case LatticeState::Incremented: {
|
|
LatState = LatticeState::MightBeUsed;
|
|
return true;
|
|
}
|
|
case LatticeState::MightBeDecremented:
|
|
LatState = LatticeState::MightBeUsed;
|
|
return true;
|
|
case LatticeState::MightBeUsed:
|
|
case LatticeState::None:
|
|
return false;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
// Returns true if the passed in ref count inst matches the ref count inst
|
|
// we are tracking. This handles generically retains/release.
|
|
bool TopDownRefCountState::isRefCountInstMatchedToTrackedInstruction(
|
|
SILInstruction *RefCountInst) {
|
|
// If we are not tracking any state transitions bail.
|
|
if (!Transition.isValid())
|
|
return false;
|
|
|
|
// Otherwise, ask the transition state if this instruction causes a
|
|
// transition that can be matched with the transition in order to eliminate
|
|
// the transition.
|
|
if (!Transition.matchingInst(RefCountInst))
|
|
return false;
|
|
|
|
return handleRefCountInstMatch();
|
|
}
|
|
|
|
/// We have a matching ref count inst. Return true if we advance the sequence
|
|
/// and false otherwise.
|
|
bool TopDownRefCountState::handleRefCountInstMatch() {
|
|
// Otherwise modify the state appropriately in preparation for removing the
|
|
// increment, decrement pair.
|
|
switch (LatState) {
|
|
case LatticeState::None:
|
|
return false;
|
|
case LatticeState::Incremented:
|
|
case LatticeState::MightBeDecremented:
|
|
case LatticeState::MightBeUsed:
|
|
return true;
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
bool TopDownRefCountState::merge(const TopDownRefCountState &Other) {
|
|
auto NewState = MergeTopDownLatticeStates(LatState, Other.LatState);
|
|
LLVM_DEBUG(llvm::dbgs() << " Performing TopDown Merge.\n");
|
|
LLVM_DEBUG(llvm::dbgs() << " Left: " << LatState << "; Right: "
|
|
<< Other.LatState << "; Result: "
|
|
<< NewState << "\n");
|
|
LLVM_DEBUG(llvm::dbgs() << " V: ";
|
|
if (hasRCRoot())
|
|
getRCRoot()->dump();
|
|
else
|
|
llvm::dbgs() << "\n";
|
|
llvm::dbgs() << " OtherV: ";
|
|
if (Other.hasRCRoot())
|
|
Other.getRCRoot()->dump();
|
|
else
|
|
llvm::dbgs() << "\n");
|
|
|
|
LatState = NewState;
|
|
KnownSafe &= Other.KnownSafe;
|
|
|
|
// If we're doing a merge on a path that's previously seen a partial merge,
|
|
// conservatively drop the sequence, to avoid doing partial RR elimination. If
|
|
// the branch predicates for the two merge differ, mixing them is unsafe since
|
|
// they are not control dependent.
|
|
//
|
|
// TODO: Add support for determining control dependence.
|
|
if (LatState == TopDownRefCountState::LatticeState::None) {
|
|
clear();
|
|
LLVM_DEBUG(llvm::dbgs() << " Found LatticeState::None. "
|
|
"Clearing State!\n");
|
|
return false;
|
|
}
|
|
|
|
if (!Transition.isValid() || !Other.Transition.isValid() ||
|
|
!Transition.merge(Other.Transition)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Failed merge!\n");
|
|
clear();
|
|
return false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
// Check if PotentialGuaranteedUser can use the reference count associated with
|
|
// the value we are tracking. If so advance the state's sequence appropriately
|
|
// and return true. Otherwise return false.
|
|
bool TopDownRefCountState::handlePotentialGuaranteedUser(
|
|
SILInstruction *PotentialGuaranteedUser, AliasAnalysis *AA) {
|
|
// If we are not tracking a ref count, just return false.
|
|
if (!isTrackingRefCount())
|
|
return false;
|
|
|
|
// If at the current lattice state, we don't care if the value we are
|
|
// tracking can be decremented or used, just return false.
|
|
//
|
|
// This causes us to only perform alias queries when we are at a lattice
|
|
// state where the alias queries will actually be used.
|
|
if (!valueCanBeGuaranteedUsedGivenLatticeState())
|
|
return false;
|
|
|
|
// If we can prove that Other cannot use the pointer we are tracking,
|
|
// return...
|
|
if (!mayGuaranteedUseValue(PotentialGuaranteedUser, getRCRoot(), AA))
|
|
return false;
|
|
|
|
// If we can prove that the pointer we are tracking cannot be decremented,
|
|
// return. On return, TopDownRefCountState::handlePotentialUser can correctly
|
|
// handle transition of refcount state.
|
|
if (!mayDecrementRefCount(PotentialGuaranteedUser, getRCRoot(), AA)) {
|
|
return false;
|
|
}
|
|
|
|
// Otherwise, update our step given that we have a potential decrement.
|
|
return handleGuaranteedUser();
|
|
}
|
|
|
|
// Check if PotentialDecrement can decrement the reference count associated with
|
|
// the value we are tracking. If so advance the state's sequence appropriately
|
|
// and return true. Otherwise return false.
|
|
bool TopDownRefCountState::handlePotentialDecrement(
|
|
SILInstruction *PotentialDecrement, AliasAnalysis *AA) {
|
|
// If we are not tracking a ref count, just return false.
|
|
if (!isTrackingRefCount())
|
|
return false;
|
|
|
|
// If at the current lattice state, we don't care if the value we are
|
|
// tracking can be decremented, just return false.
|
|
//
|
|
// This causes us to only perform alias queries when we are at a lattice
|
|
// state where the alias queries will actually be used.
|
|
if (!valueCanBeDecrementedGivenLatticeState())
|
|
return false;
|
|
|
|
// If we can prove that Other cannot use the pointer we are tracking,
|
|
// return...
|
|
if (!mayDecrementRefCount(PotentialDecrement, getRCRoot(), AA))
|
|
return false;
|
|
|
|
// Otherwise, update our state given the potential decrement.
|
|
return handleDecrement();
|
|
}
|
|
|
|
// Check if PotentialUser could be a use of the reference counted value that
|
|
// requires user to be alive. If so advance the state's sequence appropriately
|
|
// and return true. Otherwise return false.
|
|
bool TopDownRefCountState::handlePotentialUser(SILInstruction *PotentialUser,
|
|
AliasAnalysis *AA) {
|
|
// If we are not tracking a ref count, just return false.
|
|
if (!isTrackingRefCount())
|
|
return false;
|
|
|
|
// If at the current lattice state, we don't care if the value we are
|
|
// tracking can be used, just return false.
|
|
//
|
|
// This causes us to only perform alias queries when we are at a lattice
|
|
// state where the alias queries will actually be used.
|
|
if (!valueCanBeUsedGivenLatticeState())
|
|
return false;
|
|
|
|
if (!mayHaveSymmetricInterference(PotentialUser, getRCRoot(), AA))
|
|
return false;
|
|
|
|
return handleUser();
|
|
}
|
|
|
|
void TopDownRefCountState::updateForSameLoopInst(SILInstruction *I,
|
|
AliasAnalysis *AA) {
|
|
// If we are not tracking anything, bail.
|
|
if (!isTrackingRefCount())
|
|
return;
|
|
|
|
// Check if the instruction we are visiting could potentially use our
|
|
// instruction in a way that requires us to guarantee the lifetime of the
|
|
// pointer up to this point. This has the effect of performing a use and a
|
|
// decrement.
|
|
if (handlePotentialGuaranteedUser(I, AA)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Found Potential Guaranteed Use:\n "
|
|
<< getRCRoot());
|
|
return;
|
|
}
|
|
|
|
// Check if the instruction we are visiting could potentially decrement
|
|
// the reference counted value we are tracking in a manner that could
|
|
// cause us to change states. If we do change states continue...
|
|
if (handlePotentialDecrement(I, AA)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Found Potential Decrement:\n "
|
|
<< getRCRoot());
|
|
return;
|
|
}
|
|
|
|
// Otherwise check if the reference counted value we are tracking
|
|
// could be used by the given instruction.
|
|
if (!handlePotentialUser(I, AA))
|
|
return;
|
|
LLVM_DEBUG(llvm::dbgs() << " Found Potential Use:\n "
|
|
<< getRCRoot());
|
|
}
|
|
|
|
// Remove "KnownSafe" on the TopDownRefCountState. If we find another unmatched
|
|
// release instruction with a different aliasing RCIdentity or the same
|
|
// RCIdentity in the child region in the loop case.
|
|
void TopDownRefCountState::checkAndResetKnownSafety(
|
|
SILInstruction *I, SILValue VisitedRC,
|
|
std::function<bool(SILInstruction *)> checkIfRefCountInstIsMatched,
|
|
RCIdentityFunctionInfo *RCIA, AliasAnalysis *AA) {
|
|
assert(VisitedRC);
|
|
// If the RefCountState was not marked "KnownSafe", there is nothing to do.
|
|
if (!isKnownSafe())
|
|
return;
|
|
assert(Transition.getKind() == RCStateTransitionKind::StrongIncrement);
|
|
// We only care about release instructions that can potentially pair with a
|
|
// previously visited retain.
|
|
if (!(isa<StrongReleaseInst>(I) || isa<ReleaseValueInst>(I)))
|
|
return;
|
|
SILValue VisitingRC = RCIA->getRCIdentityRoot(I->getOperand(0));
|
|
assert(VisitingRC);
|
|
// If the visiting release instruction was already pair with a retain
|
|
// instruction, return.
|
|
if (checkIfRefCountInstIsMatched(I))
|
|
return;
|
|
// If the VisitingRC and VisitedRC do not alias, they cannot be incorrectly
|
|
// paired.
|
|
if (!AA->mayAlias(VisitingRC, VisitedRC))
|
|
return;
|
|
LLVM_DEBUG(llvm::dbgs() << "Clearing KnownSafe for: ");
|
|
LLVM_DEBUG(VisitedRC->dump());
|
|
clearKnownSafe();
|
|
}
|
|
|
|
// This function is conservative enough that the flow sensitive nature of
|
|
// loop summarized instructions does not matter.
|
|
void TopDownRefCountState::updateForDifferentLoopInst(SILInstruction *I,
|
|
AliasAnalysis *AA) {
|
|
// If we are not tracking anything, bail.
|
|
if (!isTrackingRefCount())
|
|
return;
|
|
|
|
// Any instruction that may need guaranteed use or may decrement the
|
|
// refcount will turn off CodeMotionSafety
|
|
if (valueCanBeGuaranteedUsedGivenLatticeState()) {
|
|
if (mayGuaranteedUseValue(I, getRCRoot(), AA) ||
|
|
mayDecrementRefCount(I, getRCRoot(), AA)) {
|
|
LLVM_DEBUG(llvm::dbgs() << " Found potential guaranteed use!\n");
|
|
handleGuaranteedUser();
|
|
return;
|
|
}
|
|
}
|
|
|
|
if (!handlePotentialUser(I, AA))
|
|
return;
|
|
LLVM_DEBUG(llvm::dbgs() << " Found Potential Use:\n "
|
|
<< getRCRoot());
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// Printing Utilities
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
void BottomUpRefCountState::dump() {
|
|
llvm::dbgs() << LatState << " "
|
|
<< (isKnownSafe() ? "KnownSafe" : "NotKnownSafe") << " "
|
|
<< (isCodeMotionSafe() ? "CodeMotionSafe" : "NotCodeMotionSafe")
|
|
<< "\n";
|
|
llvm::dbgs() << "Matching Instructions:\n";
|
|
for (auto it : getInstructions()) {
|
|
it->dump();
|
|
}
|
|
}
|
|
void TopDownRefCountState::dump() {
|
|
llvm::dbgs() << LatState << " "
|
|
<< (isKnownSafe() ? "KnownSafe" : "NotKnownSafe") << " "
|
|
<< (isCodeMotionSafe() ? "CodeMotionSafe" : "NotCodeMotionSafe")
|
|
<< "\n";
|
|
llvm::dbgs() << "Matching Instructions:\n";
|
|
for (auto it : getInstructions()) {
|
|
it->dump();
|
|
}
|
|
}
|
|
|
|
namespace llvm {
|
|
|
|
raw_ostream &operator<<(raw_ostream &OS,
|
|
BottomUpRefCountState::LatticeState S) {
|
|
using LatticeState = BottomUpRefCountState::LatticeState;
|
|
switch (S) {
|
|
case LatticeState::None:
|
|
return OS << "None";
|
|
case LatticeState::Decremented:
|
|
return OS << "Decremented";
|
|
case LatticeState::MightBeUsed:
|
|
return OS << "MightBeUsed";
|
|
case LatticeState::MightBeDecremented:
|
|
return OS << "MightBeDecremented";
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
|
|
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
|
|
TopDownRefCountState::LatticeState S) {
|
|
using LatticeState = TopDownRefCountState::LatticeState;
|
|
switch (S) {
|
|
case LatticeState::None:
|
|
return OS << "None";
|
|
case LatticeState::Incremented:
|
|
return OS << "Incremented";
|
|
case LatticeState::MightBeUsed:
|
|
return OS << "MightBeUsed";
|
|
case LatticeState::MightBeDecremented:
|
|
return OS << "MightBeDecremented";
|
|
}
|
|
|
|
llvm_unreachable("Unhandled LatticeState in switch.");
|
|
}
|
|
} // end namespace llvm
|