blob: f0304bf681f524776544cf6a5281c27d6039d41c [file] [log] [blame]
//===--- RefCountState.h - Represents a Reference Count ---------*- C++ -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//
#ifndef SWIFT_SILOPTIMIZER_PASSMANAGER_ARC_REFCOUNTSTATE_H
#define SWIFT_SILOPTIMIZER_PASSMANAGER_ARC_REFCOUNTSTATE_H
#include "RCStateTransition.h"
#include "swift/Basic/BlotMapVector.h"
#include "swift/Basic/ImmutablePointerSet.h"
#include "swift/Basic/type_traits.h"
#include "swift/SIL/InstructionUtils.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILBasicBlock.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
#include "swift/SILOptimizer/Analysis/EpilogueARCAnalysis.h"
#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
#include <algorithm>
namespace swift {
class AliasAnalysis;
} // end namespace swift
//===----------------------------------------------------------------------===//
// Ref Count State
//===----------------------------------------------------------------------===//
namespace swift {
/// A struct that abstracts over reference counts manipulated by strong_retain,
/// retain_value, strong_release,
class RefCountState {
protected:
/// Return the SILValue that represents the RCRoot that we are
/// tracking.
SILValue RCRoot;
/// The last state transition that this RefCountState went through. None if we
/// have not see any transition on this ref count yet.
RCStateTransition Transition;
/// Was the pointer we are tracking known incremented when we visited the
/// current increment we are tracking? In that case we know that it is safe
/// to move the inner retain over instructions that may decrement ref counts
/// since the outer retain will keep the reference counted value alive.
bool KnownSafe = false;
public:
RefCountState() = default;
~RefCountState() = default;
RefCountState(const RefCountState &) = default;
RefCountState &operator=(const RefCountState &) = default;
RefCountState(RefCountState &&) = default;
RefCountState &operator=(RefCountState &&) = default;
/// Initializes/reinitialized the state for I. If we reinitialize we return
/// true.
bool initWithMutatorInst(ImmutablePointerSet<SILInstruction> *I,
RCIdentityFunctionInfo *RCFI) {
assert(I->size() == 1);
// Are we already tracking a ref count modification?
bool Nested = isTrackingRefCount();
Transition = RCStateTransition(I);
assert(Transition.isMutator() && "Expected I to be a mutator!\n");
// Initialize KnownSafe to a conservative false value.
KnownSafe = false;
// Initialize value.
RCRoot = RCFI->getRCIdentityRoot((*I->begin())->getOperand(0));
return Nested;
}
/// Uninitialize the current state.
void clear() {
KnownSafe = false;
}
/// Is this ref count initialized and tracking a ref count ptr.
bool isTrackingRefCount() const { return Transition.isValid(); }
/// Are we tracking an instruction currently? This returns false when given an
/// uninitialized ReferenceCountState.
bool isTrackingRefCountInst() const {
return Transition.isValid() && Transition.isMutator();
}
/// Are we tracking a source of ref counts? This currently means that we are
/// tracking an argument that is @owned. In the future this will include
/// return values of functions that are @owned.
bool isTrackingRefCountSource() const {
return Transition.isValid() && Transition.isEndPoint();
}
/// Return the increment we are tracking.
RCStateTransition::mutator_range getInstructions() const {
return Transition.getMutators();
}
/// Returns true if I is in the instructions we are tracking.
bool containsInstruction(SILInstruction *I) const {
return Transition.isValid() && Transition.containsMutator(I);
}
/// Return the value with reference semantics that is the operand of our
/// increment.
SILValue getRCRoot() const {
assert(RCRoot && "Value should never be null here");
return RCRoot;
}
/// Returns true if we have a valid value that we are tracking.
bool hasRCRoot() const {
return (bool)RCRoot;
}
/// This retain is known safe if the operand we are tracking was already known
/// incremented previously. This occurs when you have nested increments.
bool isKnownSafe() const { return KnownSafe; }
/// Set KnownSafe to true if \p NewValue is true. If \p NewValue is false,
/// this is a no-op.
void updateKnownSafe(bool NewValue) {
KnownSafe |= NewValue;
}
void clearKnownSafe() { KnownSafe = false; }
};
//===----------------------------------------------------------------------===//
// Bottom Up Ref Count State
//===----------------------------------------------------------------------===//
class BottomUpRefCountState : public RefCountState {
public:
/// Sequence of states that a value with reference semantics can go through
/// when visiting decrements bottom up. The reason why I have this separate
/// from TopDownSubstruct is I think it gives more clarity to the algorithm by
/// giving it typed form.
enum class LatticeState {
None, ///< The pointer has no information associated with it.
Decremented, ///< The pointer will be decremented.
MightBeUsed, ///< The pointer will be used and then at this point
/// be decremented
MightBeDecremented, ///< The pointer might be decremented again implying
/// that we cannot, without being known safe remove
/// this decrement.
};
private:
using SuperTy = RefCountState;
/// Current place in the sequence of the value.
LatticeState LatState = LatticeState::None;
/// True if we have seen a NonARCUser of this instruction. This means bottom
/// up assuming we have this property as a meet over all paths property, we
/// know that all releases we see are known safe.
bool FoundNonARCUser = false;
public:
BottomUpRefCountState() = default;
~BottomUpRefCountState() = default;
BottomUpRefCountState(const BottomUpRefCountState &) = default;
BottomUpRefCountState &operator=(const BottomUpRefCountState &) = default;
BottomUpRefCountState(BottomUpRefCountState &&) = default;
BottomUpRefCountState &operator=(BottomUpRefCountState &&) = default;
/// Getter for LatticeState
LatticeState getLatticeState() const {return LatState;}
/// Return true if the release can be moved to the retain.
bool isCodeMotionSafe() const {
return LatState != LatticeState::MightBeDecremented;
}
/// Initializes/reinitialized the state for I. If we reinitialize we return
/// true.
bool initWithMutatorInst(ImmutablePointerSet<SILInstruction> *I,
RCIdentityFunctionInfo *RCFI);
/// Update this reference count's state given the instruction \p I.
void
updateForSameLoopInst(SILInstruction *I,
AliasAnalysis *AA);
/// Remove "KnownSafe" on the BottomUpRefCountState, if we find a retain
/// instruction with another RCIdentity can pair with the previously visited
/// retain instruction.
void checkAndResetKnownSafety(
SILInstruction *I, SILValue VisitedRC,
std::function<bool(SILInstruction *)> checkIfRefCountInstIsMatched,
RCIdentityFunctionInfo *RCIA, AliasAnalysis *AA);
/// Update this reference count's state given the instruction \p I.
//
/// The main difference in between this routine and update for same loop inst
/// is that if we see any decrements on a value, we treat it as being
/// guaranteed used. We treat any uses as regular uses.
/// This function is conservative enough that the flow sensitive nature of
/// loop summarized instructions does not matter.
void updateForDifferentLoopInst(
SILInstruction *I,
AliasAnalysis *AA);
/// Attempt to merge \p Other into this ref count state. Return true if we
/// succeed and false otherwise.
bool merge(const BottomUpRefCountState &Other);
/// Returns true if the passed in ref count inst matches the ref count inst
/// we are tracking. This handles generically retains/release.
bool isRefCountInstMatchedToTrackedInstruction(SILInstruction *RefCountInst);
/// Uninitialize the current state.
void clear();
void dump();
private:
/// 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 mightRemoveMutators();
/// Can we guarantee that the given reference counted value has been modified?
bool isRefCountStateModified() const;
/// Returns true if given the current lattice state, do we care if the value
/// we are tracking is decremented.
bool valueCanBeDecrementedGivenLatticeState() const;
/// If advance the state's sequence appropriately for a decrement. If we do
/// advance return true. Otherwise return false.
bool handleDecrement();
/// 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 handlePotentialDecrement(SILInstruction *Decrement, AliasAnalysis *AA);
/// Returns true if given the current lattice state, do we care if the value
/// we are tracking is used.
bool valueCanBeUsedGivenLatticeState() const;
/// 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 handleUser();
/// 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
handlePotentialUser(SILInstruction *PotentialUser,
AliasAnalysis *AA);
/// Returns true if given the current lattice state, do we care if the value
/// we are tracking is used.
bool valueCanBeGuaranteedUsedGivenLatticeState() const;
/// 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 handleGuaranteedUser();
/// 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 handlePotentialGuaranteedUser(
SILInstruction *User,
AliasAnalysis *AA);
/// We have a matching ref count inst. Return true if we advance the sequence
/// and false otherwise.
bool handleRefCountInstMatch();
};
//===----------------------------------------------------------------------===//
// Top Down Ref Count State
//===----------------------------------------------------------------------===//
class TopDownRefCountState : public RefCountState {
public:
/// Sequence of states that a value with reference semantics can go through
/// when visiting decrements bottom up. The reason why I have this separate
/// from BottomUpRefCountState is I think it gives more clarity to the
/// algorithm by giving it typed form.
enum class LatticeState {
None, ///< The pointer has no information associated with it.
Incremented, ///< The pointer has been incremented.
MightBeDecremented, ///< The pointer has been incremented and might be
/// decremented. be decremented again implying
MightBeUsed, ///< The pointer has been incremented,
};
private:
using SuperTy = RefCountState;
/// Current place in the sequence of the value.
LatticeState LatState = LatticeState::None;
public:
TopDownRefCountState() = default;
~TopDownRefCountState() = default;
TopDownRefCountState(const TopDownRefCountState &) = default;
TopDownRefCountState &operator=(const TopDownRefCountState &) = default;
TopDownRefCountState(TopDownRefCountState &&) = default;
TopDownRefCountState &operator=(TopDownRefCountState &&) = default;
/// Getter for LatticeState
LatticeState getLatticeState() const {return LatState;}
/// Return true if the retain can be moved to the release.
bool isCodeMotionSafe() const {
return LatState != LatticeState::MightBeUsed;
}
/// Initializes/reinitialized the state for I. If we reinitialize we return
/// true.
bool initWithMutatorInst(ImmutablePointerSet<SILInstruction> *I,
RCIdentityFunctionInfo *RCFI);
/// Initialize the state given the consumed argument Arg.
void initWithArg(SILFunctionArgument *Arg);
/// Initialize this RefCountState with an instruction which introduces a new
/// ref count at +1.
void initWithEntranceInst(ImmutablePointerSet<SILInstruction> *I,
SILValue RCIdentity);
/// Uninitialize the current state.
void clear();
/// Update this reference count's state given the instruction \p I.
void
updateForSameLoopInst(SILInstruction *I,
AliasAnalysis *AA);
/// Remove "KnownSafe" on the TopDownRefCountState, if we find a retain
/// instruction with another RCIdentity can pair with the previously visited
/// retain instruction.
void checkAndResetKnownSafety(
SILInstruction *I, SILValue VisitedRC,
std::function<bool(SILInstruction *)> checkIfRefCountInstIsMatched,
RCIdentityFunctionInfo *RCIA, AliasAnalysis *AA);
/// Update this reference count's state given the instruction \p I.
///
/// The main difference in between this routine and update for same loop inst
/// is that if we see any decrements on a value, we treat it as being
/// guaranteed used. We treat any uses as regular uses.
/// This function is conservative enough that the flow sensitive nature of
/// loop summarized instructions does not matter.
void updateForDifferentLoopInst(
SILInstruction *I,
AliasAnalysis *AA);
/// Returns true if the passed in ref count inst matches the ref count inst
/// we are tracking. This handles generically retains/release.
bool isRefCountInstMatchedToTrackedInstruction(SILInstruction *RefCountInst);
/// Attempt to merge \p Other into this ref count state. Return true if we
/// succeed and false otherwise.
bool merge(const TopDownRefCountState &Other);
void dump();
private:
/// Can we guarantee that the given reference counted value has been modified?
bool isRefCountStateModified() const;
/// Returns true if given the current lattice state, do we care if the value
/// we are tracking is decremented.
bool valueCanBeDecrementedGivenLatticeState() const;
/// If advance the state's sequence appropriately for a decrement. If we do
/// advance return true. Otherwise return false.
bool handleDecrement();
/// 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 handlePotentialDecrement(
SILInstruction *PotentialDecrement,
AliasAnalysis *AA);
/// Returns true if given the current lattice state, do we care if the value
/// we are tracking is used.
bool valueCanBeUsedGivenLatticeState() const;
/// 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 handleUser();
/// 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 handlePotentialUser(SILInstruction *PotentialUser, AliasAnalysis *AA);
/// Returns true if given the current lattice state, do we care if the value
/// we are tracking is used.
bool valueCanBeGuaranteedUsedGivenLatticeState() const;
/// 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 handleGuaranteedUser();
/// 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 handlePotentialGuaranteedUser(
SILInstruction *PotentialGuaranteedUser,
AliasAnalysis *AA);
/// We have a matching ref count inst. Return true if we advance the sequence
/// and false otherwise.
bool handleRefCountInstMatch();
};
// These static asserts are here for performance reasons.
static_assert(IsTriviallyCopyable<BottomUpRefCountState>::value,
"All ref count states must be trivially copyable");
static_assert(IsTriviallyCopyable<TopDownRefCountState>::value,
"All ref count states must be trivially copyable");
} // end swift namespace
namespace llvm {
raw_ostream &operator<<(raw_ostream &OS,
swift::BottomUpRefCountState::LatticeState S);
raw_ostream &operator<<(raw_ostream &OS,
swift::TopDownRefCountState::LatticeState S);
} // end namespace llvm
#endif