| //===--- OwnershipLiveRange.h ---------------------------------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2020 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_SEMANTICARC_OWNERSHIPLIVERANGE_H |
| #define SWIFT_SILOPTIMIZER_SEMANTICARC_OWNERSHIPLIVERANGE_H |
| |
| #include "swift/SIL/OwnershipUtils.h" |
| #include "swift/SILOptimizer/Utils/InstOptUtils.h" |
| #include "swift/SILOptimizer/Utils/ValueLifetime.h" |
| |
| namespace swift { |
| namespace semanticarc { |
| |
| /// This class represents an "extended live range" of an owned value. Such a |
| /// representation includes: |
| /// |
| /// 1. The owned introducing value. |
| /// 2. Any forwarding instructions that consume the introduced value |
| /// (transitively) and then propagate a new owned value. |
| /// 3. Transitive destroys on the forwarding instructions/destroys on the owned |
| /// introducing value. |
| /// 4. Any unknown consuming uses that are not understood by this code. |
| /// |
| /// This allows for this to be used to convert such a set of uses from using |
| /// owned ownership to using guaranteed ownership by converting the |
| /// destroy_value -> end_borrow and "flipping" the ownership of individual |
| /// forwarding instructions. |
| /// |
| /// NOTE: We do not look through "phi nodes" in the ownership graph (e.x.: real |
| /// phi arguments, struct, tuple). Instead we represent those as nodes in a |
| /// larger phi ownership web, connected via individual OwnershipLiveRange. |
| class LLVM_LIBRARY_VISIBILITY OwnershipLiveRange { |
| /// The value that we are computing the LiveRange for. Expected to be an owned |
| /// introducer and not to be forwarding. |
| OwnedValueIntroducer introducer; |
| |
| /// A vector that we store all of our uses into. |
| /// |
| /// Some properties of this array are: |
| /// |
| /// 1. It is only mutated in the constructor of LiveRange. |
| /// |
| /// 2. destroyingUses, ownershipForwardingUses, and unknownConsumingUses are |
| /// views into this array. We store the respective uses in the aforementioned |
| /// order. This is why it is important not to mutate consumingUses after we |
| /// construct the LiveRange since going from small -> large could invalidate |
| /// the uses. |
| SmallVector<Operand *, 6> consumingUses; |
| |
| /// A list of destroy_values of the live range. |
| /// |
| /// This is just a view into consuming uses. |
| ArrayRef<Operand *> destroyingUses; |
| |
| /// A list of forwarding instructions that forward owned ownership, but that |
| /// are also able to be converted to guaranteed ownership. |
| /// |
| /// If we are able to eliminate this LiveRange due to it being from a |
| /// guaranteed value, we must flip the ownership of all of these instructions |
| /// to guaranteed from owned. |
| /// |
| /// NOTE: Normally only destroying or consuming uses end the live range. We |
| /// copy these transitive uses as well into the consumingUses array since |
| /// transitive uses can extend a live range up to an unreachable block without |
| /// ultimately being consuming. In such a situation if we did not also store |
| /// this into consuming uses, we would not be able to ascertain just using the |
| /// "consumingUses" array the true lifetime of the OwnershipLiveRange. |
| /// |
| /// Corresponds to isOwnershipForwardingInst(...). |
| ArrayRef<Operand *> ownershipForwardingUses; |
| |
| /// Consuming uses that we were not able to understand as a forwarding |
| /// instruction or a destroy_value. These must be passed a strongly control |
| /// equivalent +1 value. |
| ArrayRef<Operand *> unknownConsumingUses; |
| |
| public: |
| OwnershipLiveRange(SILValue value); |
| OwnershipLiveRange(const OwnershipLiveRange &) = delete; |
| OwnershipLiveRange &operator=(const OwnershipLiveRange &) = delete; |
| |
| enum class HasConsumingUse_t { |
| No = 0, |
| YesButAllPhiArgs = 1, |
| Yes = 2, |
| }; |
| |
| /// Return true if v only has invalidating uses that are destroy_value. Such |
| /// an owned value is said to represent a dead "live range". |
| /// |
| /// Semantically this implies that a value is never passed off as +1 to memory |
| /// or another function implying it can be used everywhere at +0. |
| HasConsumingUse_t |
| hasUnknownConsumingUse(bool assumingFixedPoint = false) const; |
| |
| /// Return an array ref to /all/ consuming uses. Will include all 3 sorts of |
| /// consuming uses: destroying uses, forwarding consuming uses, and unknown |
| /// forwarding instruction. |
| ArrayRef<Operand *> getAllConsumingUses() const { return consumingUses; } |
| |
| ArrayRef<Operand *> getDestroyingUses() const { return destroyingUses; } |
| |
| private: |
| struct OperandToUser; |
| |
| public: |
| using DestroyingInstsRange = |
| TransformRange<ArrayRef<Operand *>, OperandToUser>; |
| DestroyingInstsRange getDestroyingInsts() const; |
| |
| using ConsumingInstsRange = |
| TransformRange<ArrayRef<Operand *>, OperandToUser>; |
| ConsumingInstsRange getAllConsumingInsts() const; |
| |
| /// If this LiveRange has a single destroying use, return that use. Otherwise, |
| /// return nullptr. |
| Operand *getSingleDestroyingUse() const { |
| if (destroyingUses.size() != 1) { |
| return nullptr; |
| } |
| return destroyingUses.front(); |
| } |
| |
| /// If this LiveRange has a single unknown destroying use, return that |
| /// use. Otherwise, return nullptr. |
| Operand *getSingleUnknownConsumingUse() const { |
| if (unknownConsumingUses.size() != 1) { |
| return nullptr; |
| } |
| return unknownConsumingUses.front(); |
| } |
| |
| OwnedValueIntroducer getIntroducer() const { return introducer; } |
| |
| ArrayRef<Operand *> getOwnershipForwardingUses() const { |
| return ownershipForwardingUses; |
| } |
| |
| void convertOwnedGeneralForwardingUsesToGuaranteed() &&; |
| |
| /// A consuming operation that: |
| /// |
| /// 1. If \p insertEndBorrows is true inserts end borrows at all |
| /// destroying insts locations. |
| /// |
| /// 2. Deletes all destroy_values. |
| /// |
| /// 3. RAUW value with newGuaranteedValue. |
| /// |
| /// 4. Convert all of the general forwarding instructions from |
| /// @owned -> @guaranteed. "Like Dominoes". |
| /// |
| /// 5. Leaves all of the unknown consuming users alone. It is up to |
| /// the caller to handle converting their ownership. |
| void convertToGuaranteedAndRAUW(SILValue newGuaranteedValue, |
| InstModCallbacks callbacks) &&; |
| |
| /// A consuming operation that in order: |
| /// |
| /// 1. Converts the phi argument to be guaranteed via setOwnership. |
| /// |
| /// 2. If this consumes a borrow, insert end_borrows at the relevant |
| /// destroy_values. |
| /// |
| /// 3. Deletes all destroy_values. |
| /// |
| /// 4. Converts all of the general forwarding instructions from @owned -> |
| /// @guaranteed. "Like Dominoes". |
| /// |
| /// NOTE: This leaves all of the unknown consuming users alone. It is up to |
| /// the caller to handle converting their ownership. |
| /// |
| /// NOTE: This routine leaves inserting begin_borrows for the incoming values |
| /// to the caller since those are not part of the LiveRange itself. |
| void convertJoinedLiveRangePhiToGuaranteed( |
| DeadEndBlocks &deadEndBlocks, ValueLifetimeAnalysis::Frontier &scratch, |
| InstModCallbacks callbacks) &&; |
| |
| /// Given a new guaranteed value, insert end_borrow for the newGuaranteedValue |
| /// at all of our destroy_values in prepration for converting from owned to |
| /// guaranteed. |
| /// |
| /// This is used when converting load [copy] -> load_borrow. |
| void insertEndBorrowsAtDestroys(SILValue newGuaranteedValue, |
| DeadEndBlocks &deadEndBlocks, |
| ValueLifetimeAnalysis::Frontier &scratch); |
| }; |
| |
| struct OwnershipLiveRange::OperandToUser { |
| OperandToUser() {} |
| |
| SILInstruction *operator()(const Operand *use) const { |
| auto *nonConstUse = const_cast<Operand *>(use); |
| return nonConstUse->getUser(); |
| } |
| }; |
| |
| } // namespace semanticarc |
| } // namespace swift |
| |
| #endif // SWIFT_SILOPTIMIZER_SEMANTICARC_OWNERSHIPLIVERANGE_H |