| //===--- LoopRegionAnalysis.h -----------------------------------*- 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 |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// Purpose |
| /// ======= |
| /// |
| /// This is an analysis that is an implementation of interval analysis in order |
| /// to allow for dataflow to be done in a structured way on the loop tree. The |
| /// facilities it provides are: |
| /// |
| /// 1. An abstraction called ``LoopRegion`` that abstracts over natural loops, |
| /// basic blocks, and the top level function. This is meant to provide a |
| /// function level pointer for summarizing information. |
| /// |
| /// 2. For each Region, if it has subregions (i.e. is not a Block), an RPO |
| /// ordering of the Subregions are provided. Loops in this RPO ordering have the |
| /// RPO number of their header. |
| /// |
| /// 3. Natural loops are defined by the loops that SILLoopInfo can find. Thus it |
| /// is useful to be able to know about loops that are not able to be found by |
| /// SILLoopInfo (i.e. irreducible loops). This information is computed by |
| /// finding all backedges and any backedge that is not recognized by SILLoopInfo |
| /// as a backedge has its head and tail region marked as unknown control flow |
| /// boundaries. This can be queries via the methods: |
| /// |
| /// - LoopRegion::isUnknownControlFlowEdgeHead(). |
| /// - LoopRegion::isUnknownControlFlowEdgeTail(). |
| /// |
| /// 4. Only loops with single back edges are supported by this analysis. If such |
| /// a loop is detected, we mark the head, tail of the edge as irreducible |
| /// control flow boundaries. To handle such loops, we rely on loop |
| /// canonicalization to transform the multiple backedge loops into multiple |
| /// loops with singular backedges or by merging the backedge blocks. |
| /// |
| /// Algorithm |
| /// ========= |
| /// |
| /// The main consideration here is that we want to ensure that we only traverse |
| /// the CFG once and reuse the information that is already provided via the loop |
| /// info analysis and the post order analysis. |
| /// |
| /// We begin by visiting each block in RPO order. During this RPO traversal, we: |
| /// |
| /// 1. Create LoopRegions for each block and wire up each block's predecessor |
| /// and successor blocks as predecessors/successors of the block's region. |
| /// |
| /// 2. Detect any backedges that are unknown to SILLoopInfo and mark the blocks |
| /// that form the head/tail of the backedge as unknown control flow boundaries. |
| /// |
| /// 3. We lookup/create the region for the innermost loop that contains the |
| /// block and add the block's region as a subregion of that loop. |
| /// |
| /// Then we perform a postorder DFS of the loop nest. The postorder provides the |
| /// inductive rule that all loops will be visited after all of their subloops |
| /// have been visited. If a Loop has no subloops (i.e. all subregions are |
| /// blocks), we do nothing. Otherwise, if the loop does have subloops, we visit |
| /// each subloop and do the following: |
| /// |
| /// 1. The region data structure of the header of the subloop still is the |
| /// successor of its predecessor outside of the subloop in the various block |
| /// datastructures. Rewire those regions to consider the loop to be their |
| /// successor instead and make each of those regions on of the predecessors of |
| /// the subloop. Then clear the predecessor list of the subloop's header |
| /// region. The header should have no predecessor edges after this operation |
| /// completes. |
| /// |
| /// 2. For each of the exiting regions of the subloop (that is the regions |
| /// inside the loop that leave the subloop): |
| /// |
| /// a. Replace each predecessor edge in the exiting block's successors with an |
| /// edge pointing at the subloop instead of at the exiting block and |
| /// vis-a-versa. |
| /// |
| /// b. Introduce a loop-escape edge from the exiting regions that associates |
| /// the specific successor number of the region with the loop successor edge |
| /// that we just created. By using this indirection, if the loop is an inner |
| /// loop and further acts as an exit from an outer loop, the region's |
| /// successor edge will be able to be used to traverse from the region -> |
| /// inner loop -> outer loop successor. (i). |
| /// |
| /// After this is complete, the exiting blocks should have no successor edges |
| /// going outside the loop. For each of the removed edges additionally we |
| /// introduce an "exiting edge". The reason this is necessary is to make it |
| /// easier to handle exits through |
| /// |
| /// 3. If the loop has multiple back edges, mark each of the backedges as |
| /// unknown control flow boundaries. |
| /// |
| /// We complete by performing the same operation on the top level function. |
| /// |
| /// After this is done, each level of the loop hierarchy should be able to be |
| /// treated from a dataflow perspective as its own separate function with only |
| /// one caller, the parent loop region (or the top level function), enabling |
| /// extremely aggressive operations (or even outlining). |
| /// |
| /// (i). The reason why this is important is to be able to handle exits to |
| /// trapping code. Trapping code will always be associated with the outer most |
| /// loop since it is an exit from all of the loops. Yet in ARC we need to be |
| /// able to find that region from For certain optimizations like ARC, we need to |
| /// be able to ignore these successor regions. By tracing up the loop nest |
| /// hierarchy by these loop exits, we can find the unreachable regions in the |
| /// parent and ignore them. This also allows us to be more precise about |
| /// hoisting retains/releases and avoid hoisting into such regions. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef SWIFT_SILOPTIMIZER_ANALYSIS_LOOPNESTANALYSIS_H |
| #define SWIFT_SILOPTIMIZER_ANALYSIS_LOOPNESTANALYSIS_H |
| |
| #include "swift/SILOptimizer/Analysis/Analysis.h" |
| #include "swift/Basic/BlotSetVector.h" |
| #include "swift/Basic/Range.h" |
| #include "swift/Basic/STLExtras.h" |
| #include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h" |
| #include "swift/SILOptimizer/Analysis/LoopAnalysis.h" |
| #include "swift/SILOptimizer/PassManager/PassManager.h" |
| #include "swift/SIL/LoopInfo.h" |
| #include "swift/SIL/SILBasicBlock.h" |
| #include "swift/SIL/SILFunction.h" |
| #include "llvm/Support/raw_ostream.h" |
| |
| namespace swift { |
| |
| /// A loop region is a data structure which represents one of a basic block, |
| /// loop, or function. |
| /// |
| /// In the case of a loop, function, it contains an internal |
| /// data structure that represents the subregions of the loop/function. This |
| /// data is tail allocated so that the basic block case is not penalized by |
| /// storing this unnecessary information. |
| class LoopRegion { |
| // FIXME: This should use llvm::TrailingObjects for its tail allocations, but |
| // that requires restructuring the file a bit. |
| |
| /// This is a data structure that is an unsigned integer with a top bit flag |
| /// that says whether it is an RPO ID for a BB Region or is an RPO ID of the |
| /// header BB of a Loop Region that used as a placeholder to ensure that the |
| /// Loop is visited in the proper RPO order. When the placeholder flag is hit, |
| /// the subloop array should be searched for the pair that has that flag as a |
| /// first element. The loop's flag will be the second element of the pair. |
| struct SubregionID { |
| static constexpr unsigned IDBitSize = (sizeof(unsigned) * CHAR_BIT) - 1; |
| static constexpr unsigned MaxID = (unsigned(1) << IDBitSize) - 1; |
| unsigned IsLoop : 1; |
| unsigned ID : IDBitSize; |
| |
| SubregionID(unsigned id, bool isloop) { |
| IsLoop = unsigned(isloop); |
| ID = id; |
| } |
| bool operator<(const SubregionID &Other) const { return ID < Other.ID; } |
| }; |
| /// These checks are just for performance. |
| static_assert(IsTriviallyCopyable<SubregionID>::value, |
| "Expected trivially copyable type"); |
| |
| struct SubregionData; |
| friend class LoopRegionFunctionInfo; |
| |
| public: |
| /// We operate in terms of FunctionTy, LoopTy, and BlockTy so that this can |
| /// potentially be ported to LLVM in the future. |
| using FunctionTy = SILFunction; |
| using LoopTy = SILLoop; |
| using BlockTy = SILBasicBlock; |
| |
| /// A tagged data structure that stores in its bottom bit whether or not the |
| /// successor edge is non-local (implying it goes through the parent region). |
| struct SuccessorID { |
| static constexpr unsigned NumTaggedBits = 2; |
| static constexpr unsigned IDBitSize = |
| (sizeof(unsigned) * CHAR_BIT) - NumTaggedBits; |
| static constexpr unsigned MaxID = (unsigned(1) << IDBitSize) - 1; |
| |
| private: |
| unsigned IsDead : 1; |
| |
| public: |
| unsigned IsNonLocal : 1; |
| unsigned ID : IDBitSize; |
| |
| SuccessorID(unsigned rawValue) |
| : IsDead(rawValue & 1), IsNonLocal((rawValue & 2) >> 1), |
| ID(rawValue >> 2) {} |
| SuccessorID(unsigned id, bool isnonlocal) |
| : IsDead(unsigned(false)), IsNonLocal(unsigned(isnonlocal)), ID(id) {} |
| |
| bool operator<(const SuccessorID &Other) const { return ID < Other.ID; } |
| bool operator==(const SuccessorID &Other) const { |
| return ID == Other.ID && IsNonLocal == Other.IsNonLocal && |
| IsDead == Other.IsDead; |
| } |
| bool operator!=(const SuccessorID &Other) const { |
| return !(*this == Other); |
| } |
| |
| unsigned asInt() const { return *reinterpret_cast<const unsigned *>(this); } |
| |
| struct ToLiveSucc { |
| Optional<SuccessorID> operator()(Optional<SuccessorID> ID) const { |
| return ID; |
| } |
| }; |
| |
| struct ToLiveLocalSucc { |
| Optional<unsigned> operator()(Optional<SuccessorID> ID) const { |
| if (!ID) |
| return None; |
| if ((*ID).IsNonLocal) |
| return None; |
| return (*ID).ID; |
| } |
| }; |
| |
| struct ToLiveNonLocalSucc { |
| Optional<unsigned> operator()(Optional<SuccessorID> ID) const { |
| if (!ID) |
| return None; |
| if (!(*ID).IsNonLocal) |
| return None; |
| return (*ID).ID; |
| } |
| }; |
| }; |
| // These checks are just for performance. |
| static_assert(IsTriviallyCopyable<SuccessorID>::value, |
| "Expected trivially copyable type"); |
| |
| /// An iterator that knows how to iterate over the subregion indices of a |
| /// region. |
| class subregion_iterator : |
| public std::iterator<std::bidirectional_iterator_tag, unsigned> { |
| friend struct SubregionData; |
| llvm::SmallVectorImpl<SubregionID>::const_iterator InnerIter; |
| const llvm::SmallVectorImpl<std::pair<unsigned, unsigned>> *Subloops; |
| |
| /// A flag that says that this iterator is an invalid iterator belonging to |
| /// a basic block. The iterator can only be compared against another invalid |
| /// iterator. Any other use causes an unreachable being hit. |
| /// |
| /// The reason this is needed is because basic blocks cannot have |
| /// subregions, yet many graph algorithms want to be able to iterate over |
| /// the subregions of a region regardless of whether it is a basic block, |
| /// loop, or function. By allowing for invalid iterators for basic blocks, |
| /// we can allow for this. |
| unsigned IsInvalid : 1; |
| |
| subregion_iterator( |
| llvm::SmallVectorImpl<SubregionID>::const_iterator iter, |
| const llvm::SmallVectorImpl<std::pair<unsigned, unsigned>> *subloops) |
| : InnerIter(iter), Subloops(subloops), IsInvalid(false) {} |
| |
| public: |
| using value_type = unsigned; |
| using reference = unsigned; |
| using pointer = void; |
| using iterator_category = std::bidirectional_iterator_tag; |
| using difference_type = int; |
| |
| /// Construct a subregion_iterator suitable for use with a basic block. It |
| /// does not contain any data and can only be compared against another |
| /// invalid iterator (for which it will return true). Any other usage |
| /// results in an unreachable being hit. |
| subregion_iterator() : InnerIter(), Subloops(), IsInvalid(true) {} |
| |
| /// Return the index of the current subregion index. |
| unsigned operator*() const { |
| if (IsInvalid) |
| llvm_unreachable("Invalid Iterator?!"); |
| auto ID = *InnerIter; |
| if (!ID.IsLoop) |
| return ID.ID; |
| for (auto &p : *Subloops) { |
| if (p.first == ID.ID) { |
| return p.second; |
| } |
| } |
| llvm_unreachable("Out of sync subloops array?!"); |
| } |
| |
| subregion_iterator &operator++() { |
| if (IsInvalid) |
| llvm_unreachable("Invalid Iterator?!"); |
| InnerIter++; |
| return *this; |
| } |
| subregion_iterator operator++(int) { |
| if (IsInvalid) |
| llvm_unreachable("Invalid Iterator?!"); |
| return subregion_iterator(InnerIter++, Subloops); |
| } |
| subregion_iterator &operator--() { |
| if (IsInvalid) |
| llvm_unreachable("Invalid Iterator?!"); |
| InnerIter--; |
| return *this; |
| } |
| subregion_iterator operator--(int) { |
| if (IsInvalid) |
| llvm_unreachable("Invalid Iterator?!"); |
| return subregion_iterator(InnerIter--, Subloops); |
| } |
| bool operator==(subregion_iterator rhs) const { |
| if (IsInvalid) { |
| if (rhs.IsInvalid) |
| return true; |
| llvm_unreachable("Invalid Iterator?!"); |
| } |
| return InnerIter == rhs.InnerIter; |
| } |
| bool operator!=(subregion_iterator rhs) const { return !(*this == rhs); } |
| }; |
| using subregion_reverse_iterator = std::reverse_iterator<subregion_iterator>; |
| |
| /// An iterator that knows how to iterate over the backedge indices of a |
| /// region. |
| class backedge_iterator |
| : public std::iterator<std::bidirectional_iterator_tag, unsigned> { |
| friend struct SubregionData; |
| using InnerIterTy = llvm::SmallVectorImpl<unsigned>::const_iterator; |
| llvm::Optional<InnerIterTy> InnerIter; |
| |
| backedge_iterator(llvm::SmallVectorImpl<unsigned>::const_iterator iter) |
| : InnerIter(iter) {} |
| |
| public: |
| using value_type = unsigned; |
| using reference = unsigned; |
| using pointer = void; |
| using iterator_category = std::bidirectional_iterator_tag; |
| using difference_type = int; |
| |
| /// Construct a backedge_iterator suitable for use with a basic block. It |
| /// does not contain any data and can only be compared against another |
| /// invalid iterator (for which it will return true). Any other usage |
| /// results in an unreachable being hit. |
| backedge_iterator() : InnerIter() {} |
| |
| bool hasValue() const { return InnerIter.hasValue(); } |
| |
| /// Return the index of the current backedge index. |
| unsigned operator*() const { return **InnerIter; } |
| |
| backedge_iterator &operator++() { |
| ++(*InnerIter); |
| return *this; |
| } |
| backedge_iterator operator++(int) { |
| backedge_iterator iter = *this; |
| ++iter; |
| return iter; |
| } |
| backedge_iterator &operator--() { |
| --(*InnerIter); |
| return *this; |
| } |
| backedge_iterator operator--(int) { |
| backedge_iterator iter = *this; |
| --iter; |
| return iter; |
| } |
| bool operator==(backedge_iterator rhs) const { |
| if (InnerIter.hasValue() != rhs.InnerIter.hasValue()) |
| llvm_unreachable("Comparing uncomparable iterators"); |
| // Now we know that the two either both have values or both do not have |
| // values. |
| if (!InnerIter.hasValue()) |
| return true; |
| return *InnerIter == *rhs.InnerIter; |
| } |
| bool operator!=(backedge_iterator rhs) const { return !(*this == rhs); } |
| }; |
| using backedge_reverse_iterator = std::reverse_iterator<backedge_iterator>; |
| |
| private: |
| /// A pointer to one of a Loop, Basic Block, or Function represented by this |
| /// region. |
| llvm::PointerUnion<FunctionTy *, LoopTy *, BlockTy *> Ptr; |
| |
| /// The ID of this region. |
| unsigned ID; |
| |
| /// The parent region of this ID if it exists. |
| llvm::Optional<unsigned> ParentID; |
| |
| /// The IDs of the predecessor regions of this region. |
| llvm::SmallVector<unsigned, 4> Preds; |
| |
| /// The IDs of the local and non-local successor regions of this region. |
| /// |
| /// Let R1 be this region. A local successor of R1 is a region R2 for which |
| /// the inner most parent region that contains R2 is the same as the inner |
| /// most parent region that contains R1. A local successor is represented by |
| /// its real ID. A non-local successor is represented by the index of the |
| /// non-local successor in this region's parent's successor list. |
| /// |
| /// Discussion: The reason that we have this separate representation is so |
| /// that if the non-local exit is to a block in a grand+-ancestor region of |
| /// this BB, we can represent each jump as individual non-local edges in |
| /// between loops. |
| /// |
| /// *NOTE* This list is not sorted, but cannot have any duplicate |
| /// elements. We have a check in LoopRegionFunctionInfo::verify to make sure |
| /// that this stays true. The reason why this is necessary is that subregions |
| /// of a loop, may have a non-local successor edge pointed at this region's |
| /// successor edge. If we were to sort these edges, we would need to update |
| /// those subregion edges as well which is strictly not necessary. |
| SmallBlotSetVector<SuccessorID, 8> Succs; |
| |
| /// True if this region the head of an edge that results from control flow |
| /// that we do not handle. |
| /// |
| /// Currently this includes irreducible control flow and loops with multiple |
| /// backedges. We rely on loop canonicalization to handle the multiple |
| /// backedge case. |
| bool IsUnknownControlFlowEdgeHead; |
| |
| /// True if this region the tail of an edge that results from control flow |
| /// that we do not handle. |
| /// |
| /// Currently this includes irreducible control flow and loops with multiple |
| /// backedges. We rely on loop canonicalization to handle the multiple |
| /// backedge case. |
| bool IsUnknownControlFlowEdgeTail; |
| |
| /// A tail allocated LoopSubregionData structure that is used to store state |
| /// about subregions of a loop. |
| /// |
| /// We tail allocate this onto LoopRegions for loops/functions so that in the |
| /// case of having a Block, we do not have any memory size overhead of these |
| /// SmallVectors, but at the same time have reasonable memory performance. In |
| /// the case of loops this overhead is acceptable since we shouldn't have many |
| /// loops (compared to Blocks). |
| struct SubregionData { |
| /// The RPO number of the header block of this loop or function. This is |
| /// used as the RPO number for the whole region. |
| unsigned RPONumOfHeaderBlock; |
| |
| /// The RPO number of the back edge blocks of this loop. We use a |
| /// SmallVector of size 1 since after loop canonicalization we will always |
| /// have exactly one back edge block. But we want to be correct even in a |
| /// non-canonicalized case implying that we need to be able to support |
| /// multiple backedge blocks. |
| llvm::SmallVector<unsigned, 1> BackedgeRegions; |
| |
| /// A list of subregion IDs of this region sorted in RPO order. |
| /// |
| /// This takes advantage of the fact that the ID of a basic block is the |
| /// block's RPO number. |
| /// |
| /// This contains IDs that represent both basic blocks and loops that are |
| /// subregions of this region. What is key to notice is that a loop is |
| /// represented by the RPO number of its header. We use an auxiliary map to |
| /// map the preheader's RPO number to the loop's ID. |
| llvm::SmallVector<SubregionID, 16> Subregions; |
| |
| /// A map from RPO number of a subregion loop's preheader to a subloop |
| /// regions id. This is necessary since we represent a loop in the |
| /// Subregions array by the RPO number of its header. |
| llvm::SmallVector<std::pair<unsigned, unsigned>, 2> Subloops; |
| |
| /// A list of subregions with non-local successors. This is the actual ID |
| /// of the subregion since we do not care about any ordering. |
| llvm::SmallVector<unsigned, 2> ExitingSubregions; |
| |
| subregion_iterator begin() const { |
| return subregion_iterator(Subregions.begin(), &Subloops); |
| } |
| subregion_iterator end() const { |
| return subregion_iterator(Subregions.end(), &Subloops); |
| } |
| subregion_reverse_iterator rbegin() const { |
| return subregion_reverse_iterator(end()); |
| } |
| subregion_reverse_iterator rend() const { |
| return subregion_reverse_iterator(begin()); |
| } |
| |
| unsigned size() const { return Subregions.size(); } |
| bool empty() const { return Subregions.empty(); } |
| |
| void addBlockSubregion(LoopRegion *R) { |
| assert(R->ID <= SubregionID::MaxID && "Unrepresentable ID"); |
| Subregions.push_back(SubregionID(R->ID, false)); |
| } |
| |
| void addLoopSubregion(LoopRegion *L, LoopRegion *Header) { |
| assert(Header->ID <= SubregionID::MaxID && "Unrepresentable ID"); |
| Subregions.push_back(SubregionID(Header->ID, true)); |
| Subloops.push_back({Header->ID, L->ID}); |
| } |
| |
| void addBackedgeSubregion(unsigned ID) { |
| if (count(BackedgeRegions, ID)) |
| return; |
| BackedgeRegions.push_back(ID); |
| } |
| |
| backedge_iterator backedge_begin() const { |
| return backedge_iterator(BackedgeRegions.begin()); |
| } |
| backedge_iterator backedge_end() const { |
| return backedge_iterator(BackedgeRegions.end()); |
| } |
| backedge_reverse_iterator backedge_rbegin() const { |
| return backedge_reverse_iterator(backedge_begin()); |
| } |
| backedge_reverse_iterator backedge_rend() const { |
| return backedge_reverse_iterator(backedge_end()); |
| } |
| bool backedge_empty() const { return BackedgeRegions.empty(); } |
| unsigned backedge_size() const { return BackedgeRegions.size(); } |
| |
| ArrayRef<unsigned> getBackedgeRegions() const { return BackedgeRegions; } |
| |
| /// Once we finish processing a loop, we sort its subregions so that they |
| /// are guaranteed to be in RPO order. This works because each BB's ID is |
| /// its RPO number and we represent loops by the RPO number of their |
| /// preheader (with a flag in the first bit to say to look in the subloop |
| /// array for the *real* ID of the loop). |
| /// |
| /// TODO: Is this necessary? We visit BBs in RPO order. This means that we |
| /// should always add BBs in RPO order to subregion lists, no? For now I am |
| /// going to sort just to be careful while bringing this up. |
| void sortSubregions() { std::sort(Subregions.begin(), Subregions.end()); } |
| }; |
| public: |
| ~LoopRegion(); |
| |
| /// These will assert if this is not a loop region. If this is a loop region, |
| /// the forward iterators will give the IDs of the subregions in RPO order. |
| /// The backward iterators will give the IDs of the subregions in PO order. |
| /// |
| /// The reason why all of this work is being done for subregions is because we |
| /// are working around the following contradiction: |
| /// |
| /// 1. There are not that many loops in a function so it makes sense to take |
| /// advantage of this to store more data that makes performing analysis easy |
| /// (such as the IDs of subregions of the loop in RPO order). |
| /// 2. There are a lot of BBs in a function so it makes sense to try to |
| /// minimize the amount of state stored for each BB. |
| /// 3. This is a data structure that attempts to generalize over both of them |
| /// without using dynamic dispatch. |
| /// |
| /// We use tail allocation of the extra data for loops so we do not incur the |
| /// memory cost of large SmallVectors for BBs. |
| subregion_iterator subregion_begin() const { |
| if (isBlock()) |
| return subregion_iterator(); |
| return getSubregionData().begin(); |
| } |
| |
| /// This is the end equivalent of subregion_begin(). Please see comment on |
| /// subregion_begin(). |
| subregion_iterator subregion_end() const { |
| if (isBlock()) |
| return subregion_iterator(); |
| return getSubregionData().end(); |
| } |
| |
| bool subregions_empty() const { |
| if (isBlock()) |
| return true; |
| return getSubregionData().empty(); |
| } |
| |
| unsigned subregions_size() const { |
| if (isBlock()) |
| return 0; |
| return getSubregionData().size(); |
| } |
| |
| subregion_reverse_iterator subregion_rbegin() const { |
| if (isBlock()) |
| return subregion_reverse_iterator(); |
| return getSubregionData().rbegin(); |
| } |
| |
| subregion_reverse_iterator subregion_rend() const { |
| if (isBlock()) |
| return subregion_reverse_iterator(); |
| return getSubregionData().rend(); |
| } |
| |
| iterator_range<subregion_iterator> getSubregions() const { |
| return {subregion_begin(), subregion_end()}; |
| } |
| |
| iterator_range<subregion_reverse_iterator> |
| getReverseSubregions() const { |
| return {subregion_rbegin(), subregion_rend()}; |
| } |
| |
| /// Returns true if \p R is an immediate subregion of this region. |
| bool containsSubregion(LoopRegion *R) { |
| auto End = subregion_end(); |
| return std::find(subregion_begin(), End, R->getID()) != End; |
| } |
| |
| /// Returns an ArrayRef containing IDs of the exiting subregions of this |
| /// region. The exit regions associated with the exiting subregions are the |
| /// end points of the non-local edges. This asserts if this is a region |
| /// representing a block. |
| ArrayRef<unsigned> getExitingSubregions() const { |
| return getSubregionData().ExitingSubregions; |
| } |
| |
| bool isBackedgeRegion(unsigned ID) const { |
| if (isBlock()) |
| return false; |
| return count(getSubregionData().getBackedgeRegions(), ID); |
| } |
| |
| ArrayRef<unsigned> getBackedgeRegions() const { |
| if (isBlock()) |
| return ArrayRef<unsigned>(); |
| return getSubregionData().getBackedgeRegions(); |
| } |
| |
| Optional<unsigned> getBackedgeRegion() const { |
| if (isBlock()) |
| return None; |
| auto bedge_begin = getSubregionData().backedge_begin(); |
| auto bedge_end = getSubregionData().backedge_end(); |
| if (bedge_begin == bedge_end) |
| return None; |
| return *bedge_begin; |
| } |
| |
| using backedge_iterator = backedge_iterator; |
| backedge_iterator backedge_begin() const { |
| if (isBlock()) |
| return backedge_iterator(); |
| return getSubregionData().backedge_begin(); |
| } |
| backedge_iterator backedge_end() const { |
| if (isBlock()) |
| return backedge_iterator(); |
| return getSubregionData().backedge_end(); |
| } |
| bool backedge_empty() const { |
| if (isBlock()) |
| return true; |
| return getSubregionData().backedge_empty(); |
| } |
| unsigned backedge_size() const { |
| if (isBlock()) |
| return 0; |
| return getSubregionData().backedge_size(); |
| } |
| |
| using pred_const_iterator = decltype(Preds)::const_iterator; |
| pred_const_iterator pred_begin() const { return Preds.begin(); } |
| pred_const_iterator pred_end() const { return Preds.end(); } |
| bool pred_empty() const { return Preds.empty(); } |
| unsigned pred_size() const { return Preds.size(); } |
| iterator_range<pred_const_iterator> getPreds() const { |
| return {pred_begin(), pred_end()}; |
| } |
| |
| using const_succ_iterator = decltype(Succs)::const_iterator; |
| const_succ_iterator succ_begin() const { return Succs.begin(); } |
| const_succ_iterator succ_end() const { return Succs.end(); } |
| bool succ_empty() const { return Succs.empty(); } |
| unsigned succ_size() const { return Succs.size(); } |
| |
| private: |
| using InnerSuccRange = iterator_range<decltype(Succs)::const_iterator>; |
| |
| public: |
| using SuccRange = |
| OptionalTransformRange<InnerSuccRange, SuccessorID::ToLiveSucc>; |
| using LocalSuccRange = |
| OptionalTransformRange<InnerSuccRange, SuccessorID::ToLiveLocalSucc>; |
| using NonLocalSuccRange = |
| OptionalTransformRange<InnerSuccRange, SuccessorID::ToLiveNonLocalSucc>; |
| SuccRange getSuccs() const; |
| LocalSuccRange getLocalSuccs() const; |
| NonLocalSuccRange getNonLocalSuccs() const; |
| |
| BlockTy *getBlock() const; |
| LoopTy *getLoop() const; |
| FunctionTy *getFunction() const; |
| |
| bool isBlock() const { return Ptr.is<BlockTy *>(); } |
| bool isLoop() const { return Ptr.is<LoopTy *>(); } |
| bool isFunction() const { return Ptr.is<FunctionTy *>(); } |
| |
| /// Is this the head of an edge that causes unknown control flow. |
| /// |
| /// This means that dataflow that enters the region must not propagate any |
| /// information into this region from predecessors. |
| bool isUnknownControlFlowEdgeHead() const { |
| return IsUnknownControlFlowEdgeHead; |
| } |
| |
| /// Is this the head of an edge that causes unknown control flow. |
| /// |
| /// This means that dataflow state must not be propagated out of this region. |
| bool isUnknownControlFlowEdgeTail() const { |
| return IsUnknownControlFlowEdgeTail; |
| } |
| |
| /// Returns the ID of this region in the region array. |
| /// |
| /// For basic blocks this is the RPO number of the basic block. This is done |
| /// just as a convenient way to compress our region data structures. |
| unsigned getID() const { return ID; } |
| |
| /// Return the ID of the parent region of this BB. Asserts if this is a |
| /// function region. |
| Optional<unsigned> getParentID() const { return ParentID; } |
| |
| unsigned getRPONumber() const { |
| if (isBlock()) |
| return getID(); |
| return getSubregionData().RPONumOfHeaderBlock; |
| } |
| |
| void dump() const; |
| void print(llvm::raw_ostream &os, bool insertSpaces = false) const; |
| void dumpName() const; |
| void printName(llvm::raw_ostream &os) const; |
| |
| private: |
| LoopRegion(LoopTy *L, unsigned Idx) |
| : Ptr(L), ID(Idx), ParentID(), Preds(), Succs(), |
| IsUnknownControlFlowEdgeHead(false), |
| IsUnknownControlFlowEdgeTail(false) {} |
| |
| LoopRegion(BlockTy *BB, unsigned Idx) |
| : Ptr(BB), ID(Idx), ParentID(), Preds(), Succs(), |
| IsUnknownControlFlowEdgeHead(false), |
| IsUnknownControlFlowEdgeTail(false) {} |
| |
| LoopRegion(FunctionTy *F, unsigned Idx) |
| : Ptr(F), ID(Idx), ParentID(), Preds(), Succs(), |
| IsUnknownControlFlowEdgeHead(false), |
| IsUnknownControlFlowEdgeTail(false) {} |
| |
| void setParent(LoopRegion *PR) { |
| assert(!isFunction() && "Functions cannot be subregions"); |
| assert(!PR->isBlock() && "BB regions cannot be parents of a region"); |
| ParentID = PR->getID(); |
| } |
| |
| void addPred(LoopRegion *LNR) { |
| assert(!isFunction() && "Functions cannot have predecessors"); |
| if (count(getPreds(), LNR->getID())) |
| return; |
| Preds.push_back(LNR->ID); |
| } |
| |
| unsigned addSucc(LoopRegion *Successor) { |
| assert(!isFunction() && "Functions cannot have successors"); |
| return Succs.insert(SuccessorID(Successor->getID(), false)).first; |
| } |
| |
| void replacePred(unsigned OldPredID, unsigned NewPredID) { |
| // Check if we already have NewPred in our list. If so, we just delete |
| // OldPredID. |
| if (count(Preds, NewPredID)) { |
| // If this becomes a performance issue due to copying/moving/etc (which it |
| // most likely will not), just use the marked dead model like successor |
| // does. |
| auto Iter = std::remove(Preds.begin(), Preds.end(), OldPredID); |
| Preds.erase(Iter); |
| return; |
| } |
| std::replace(Preds.begin(), Preds.end(), OldPredID, NewPredID); |
| } |
| |
| /// Replace OldSuccID by NewSuccID, just deleting OldSuccID if what NewSuccID |
| /// is already in the list. |
| void replaceSucc(SuccessorID OldSucc, SuccessorID NewSucc); |
| |
| /// Set the IsDead flag on all successors of this region that have an id \p |
| /// ID. |
| /// |
| /// Due to the creation of up-edges during loop region construction, we can |
| /// never actually remove successors. Instead we mark successors as being dead |
| /// and ignore such values when iterating. |
| void removeLocalSucc(unsigned ID) { Succs.erase(SuccessorID(ID, false)); } |
| |
| void addBlockSubregion(LoopRegion *R) { |
| assert(!isBlock() && "Blocks cannot have subregions"); |
| assert(R->isBlock() && "Assumed R was a basic block"); |
| R->setParent(this); |
| getSubregionData().addBlockSubregion(R); |
| } |
| |
| void addLoopSubregion(LoopRegion *L, LoopRegion *Header) { |
| assert(!isBlock() && "Blocks cannot have subregions"); |
| assert(L->isLoop() && "Assumed L was a loop"); |
| assert(Header->isBlock() && "Assumed Header was a loop"); |
| L->setParent(this); |
| getSubregionData().addLoopSubregion(L, Header); |
| } |
| |
| |
| SubregionData &getSubregionData() { |
| assert(!isBlock() && "BBs do not have subregion data"); |
| return reinterpret_cast<SubregionData &>(*(this + 1)); |
| } |
| |
| const SubregionData &getSubregionData() const { |
| assert(!isBlock() && "BBs do not have subregion data"); |
| return reinterpret_cast<const SubregionData &>(*(this + 1)); |
| } |
| }; |
| |
| } // end swift namespace |
| |
| namespace llvm { |
| |
| raw_ostream &operator<<(raw_ostream &os, swift::LoopRegion &LR); |
| raw_ostream &operator<<(raw_ostream &os, swift::LoopRegion::SuccessorID &S); |
| |
| template <> struct DenseMapInfo<swift::LoopRegion::SuccessorID> { |
| using Type = swift::LoopRegion::SuccessorID; |
| |
| static_assert(sizeof(Type) == sizeof(unsigned), |
| "Expected SuccessorID to be the size of an unsigned!"); |
| static inline Type getEmptyKey() { |
| return Type(DenseMapInfo<unsigned>::getEmptyKey()); |
| } |
| static inline Type getTombstoneKey() { |
| return Type(DenseMapInfo<unsigned>::getTombstoneKey()); |
| } |
| static unsigned getHashValue(const swift::LoopRegion::SuccessorID Val) { |
| return DenseMapInfo<unsigned>::getHashValue(Val.asInt()); |
| } |
| static bool isEqual(const swift::LoopRegion::SuccessorID LHS, |
| const swift::LoopRegion::SuccessorID RHS) { |
| return LHS == RHS; |
| } |
| }; |
| |
| } // end llvm namespace |
| |
| namespace swift { |
| |
| class LoopRegionFunctionInfo { |
| using RegionTy = LoopRegion; |
| using BlockTy = SILBasicBlock; |
| using LoopInfoTy = SILLoopInfo; |
| using LoopTy = SILLoop; |
| using FunctionTy = SILFunction; |
| |
| /// The function that this data structure contains loop regions for. |
| FunctionTy *F; |
| |
| /// A bump ptr allocator that we allocate regions from. |
| llvm::BumpPtrAllocator Allocator; |
| |
| /// The ID in the IDToRegionMap of the Region associated with \p F. |
| llvm::Optional<unsigned> FunctionRegionID; |
| |
| /// A map from a BB to the ID in the IDToRegionMap of the Region associated |
| /// with the BB. |
| /// |
| /// *NOTE* This ID is *also* the function level RPO number of the BB. |
| llvm::DenseMap<BlockTy *, unsigned> BBToIDMap; |
| |
| /// A map from a Loop to the ID in the IDToRegionMap of the Region associated |
| /// with the loop. |
| llvm::DenseMap<LoopTy *, unsigned> LoopToIDMap; |
| |
| /// A map from an unsigned integer ID to a region. |
| /// |
| /// *WARNING* Before modifying the initialization of this field of the data |
| /// structure please read the comment below: |
| /// |
| /// We assign IDs to BBs, Loops, and the top level Function, so that we can |
| /// abstract above the underlying type of any specific region. A key thing to |
| /// notice is that we always allocate regions associated with BBs before |
| /// regions associated with Loops or the top level function (1). The reason |
| /// that we do this is to ensure that each BBs ID is the RPO number of the BB |
| /// at the function level. This is done so we do not have to represent the RPO |
| /// numbers in a separate array. This means that when initializing this data |
| /// structure, we need to be careful about how we initialize regions in order |
| /// to preserve said property. |
| /// |
| /// In order to avoid having to initialize loop/function regions after BB |
| /// regions (which would cause us to have to visit BBs twice), we instead |
| /// allocate the memory for all of the BBs up front and set the pointer entry |
| /// to be nullptr. |
| /// |
| /// Then when we initialize BBRegions, we just assign the resulting Region's |
| /// pointer into the array using its RPO index rather than performing a |
| /// push_back. For regions associated with Loops, Functions we still perform a |
| /// push_back. This enables us to initialize regions for all types at the same |
| /// time while preserving said property. |
| /// |
| /// (1) Currently there is no work done to ensure that the creation of the |
| /// function level region will have any ordering with respect to the creation |
| /// of any of the loop regions. |
| std::vector<RegionTy *> IDToRegionMap; |
| |
| /// True if all BB regions have been created. Only in Debug Builds. Used to |
| /// fire asserts to make sure that: |
| /// |
| /// RegionTy *createRegion(SILBasicBlock *, unsigned) |
| /// |
| /// is only called in initializeBBRegions and everywhere else: |
| /// |
| /// RegionTy *getRegion(SILBasicBlock *) |
| /// |
| /// is called. |
| #ifndef NDEBUG |
| unsigned AllBBRegionsCreated : 1; |
| #endif |
| |
| public: |
| LoopRegionFunctionInfo(FunctionTy *F, PostOrderFunctionInfo *POI, |
| LoopInfoTy *LI); |
| ~LoopRegionFunctionInfo(); |
| |
| RegionTy *getRegion(unsigned RegionID) const { |
| return IDToRegionMap[RegionID]; |
| } |
| |
| RegionTy *getRegionForNonLocalSuccessor(const RegionTy *Child, |
| unsigned SuccID) const; |
| |
| Optional<unsigned> getGrandparentID(const RegionTy *GrandChild) { |
| if (auto ParentID = GrandChild->getParentID()) { |
| return getRegion(*ParentID)->getParentID(); |
| } |
| return None; |
| } |
| |
| /// Look up the region associated with this block and return it. Asserts if |
| /// the block does not have a region associated with it. |
| /// |
| /// Regions associated with blocks are only created by the function |
| /// createRegion(). FunctionTy and LoopTy have their RegionTys created via |
| /// getRegion() lazily. For more information read the documentation for |
| /// IDToRegionMap. |
| RegionTy *getRegion(BlockTy *BB) const; |
| |
| /// Return the RegionTy associated with \p F. Creates the region if it does |
| /// not exist yet. |
| RegionTy *getRegion(FunctionTy *F) const; |
| |
| /// Return the RegionTy associated with \p Loop. Creates the region if it does |
| /// not exist yet. |
| RegionTy *getRegion(LoopTy *Loop) const; |
| |
| using iterator = decltype(IDToRegionMap)::iterator; |
| using const_iterator = decltype(IDToRegionMap)::const_iterator; |
| iterator begin() { return IDToRegionMap.begin(); } |
| iterator end() { return IDToRegionMap.end(); } |
| const_iterator begin() const { return IDToRegionMap.begin(); } |
| const_iterator end() const { return IDToRegionMap.end(); } |
| unsigned size() const { return IDToRegionMap.size(); } |
| bool empty() const { return IDToRegionMap.empty(); } |
| iterator_range<const_iterator> getRegions() const { |
| return {begin(), end()}; |
| } |
| |
| RegionTy *getTopLevelRegion() const { return getRegion(F); } |
| FunctionTy *getFunction() const { return F; } |
| |
| void dump() const; |
| void print(llvm::raw_ostream &os) const; |
| void viewLoopRegions() const; |
| void verify(); |
| |
| private: |
| RegionTy *createRegion(BlockTy *BB, unsigned RPONum); |
| |
| /// Initialize regions for all basic blocks. |
| /// |
| /// This initializes all BBs to have their regular predecessors, successors in |
| /// the CFG ignoring BBs that are unreachable from the entry. During |
| /// initialization of loops, we modify these edges in the region graph by |
| /// removing and or substituting edges to loops for basic block edges. See |
| /// large comment at the top of the file. |
| void initializeBlockRegions(PostOrderFunctionInfo *PI, LoopInfoTy *LI); |
| |
| /// Initialize regions for all loops. |
| /// |
| /// This traverses the loop nest bottom up: |
| /// |
| /// 1. Removing backedges of loops. |
| /// 2. Changing header predecessors to be loop predecessors. |
| /// 3. Changing exiting block successors to be loop successors. |
| /// |
| /// For more information see large comment at the top of LoopRegionAnalysis.h. |
| void initializeLoopRegions(LoopInfoTy *LI); |
| |
| /// Initialize the subregions of a function, treating the function as a top |
| /// level loop. |
| void |
| initializeFunctionRegion(iterator_range<LoopInfoTy::iterator> TopLevelLoops); |
| |
| /// This is a refactored routine that handles common initialization of loops |
| /// and functions. |
| void |
| initializeLoopFunctionRegion(RegionTy *ParentRegion, |
| iterator_range<LoopInfoTy::iterator> SubLoops); |
| |
| /// This helper routine rewrites all predecessors of the header of \p Loop to |
| /// be predecessors of \p Loop and vis-a-versa. Returns the region for the |
| /// SubLoopHeaderRegion |
| RegionTy * |
| rewriteLoopHeaderPredecessors(LoopTy *Loop, RegionTy *LoopRegion); |
| |
| /// This helper routine rewrites all successors of loop region exiting blocks |
| /// to be successors of the loop. It also removes backedges and ignores |
| /// non-backedge edges in the loop. |
| void |
| rewriteLoopExitingBlockSuccessors(LoopTy *Loop, RegionTy *LoopRegion); |
| |
| /// This helper routine for a given block, creates successor edges in between |
| /// the block's region and all of the regions associated with the block's |
| /// successor blocks. |
| void initializeBlockRegionSuccessors(BlockTy *BB, RegionTy *BBRegion, |
| PostOrderFunctionInfo *PI); |
| |
| /// This helper method goes through the predecessors of the basic block \p |
| /// NonHeaderBB and determines if any of them are back edges. Since we know |
| /// that \p NonHeaderBB is a basic block that has not been identified by loop |
| /// info as a loop header, we know that these backedges are not known to us |
| /// via loop info. We treat them as irreducible control flow edges to be |
| /// conservative. In truth some of them may not be due to deficiencies in loop |
| /// info. |
| /// |
| /// TODO: This needs a better name. |
| void |
| markIrreducibleLoopPredecessorsOfNonLoopHeader(BlockTy *NonHeaderBB, |
| RegionTy *NonHeaderBBRegion, |
| PostOrderFunctionInfo *PI); |
| |
| /// This helper method takes in a loop that has multiple loop latches and |
| /// marks each of those loop latches as being unknown control flow tails. We |
| /// do not support loops with multiple loop latches and instead rely on loops |
| /// to be canonicalized to have one back edge. But we still need to be |
| /// conservatively correct. |
| /// |
| /// TODO: This needs a better name. |
| void |
| markMultipleLoopLatchLoopBackEdges(RegionTy *LoopHeaderRegion, |
| LoopTy *L, |
| PostOrderFunctionInfo *PI); |
| |
| /// Recursively visit all the descendants of Parent. If there is a non-local |
| /// successor edge path that points to a dead edge in Parent, mark the |
| /// descendant non-local successor edge as dead. |
| void propagateLivenessDownNonLocalSuccessorEdges(LoopRegion *Parent); |
| }; |
| |
| class LoopRegionAnalysis : public FunctionAnalysisBase<LoopRegionFunctionInfo> { |
| SILLoopAnalysis *SLA; |
| PostOrderAnalysis *POA; |
| |
| public: |
| LoopRegionAnalysis(SILModule *M) |
| : FunctionAnalysisBase<LoopRegionFunctionInfo>( |
| SILAnalysisKind::LoopRegion) {} |
| |
| LoopRegionAnalysis(const LoopRegionAnalysis &) = delete; |
| LoopRegionAnalysis &operator=(const LoopRegionAnalysis &) = delete; |
| |
| virtual ~LoopRegionAnalysis() {} |
| |
| virtual void initialize(SILPassManager *PM) override; |
| |
| static bool classof(const SILAnalysis *S) { |
| return S->getKind() == SILAnalysisKind::LoopRegion; |
| } |
| |
| virtual std::unique_ptr<LoopRegionFunctionInfo> |
| newFunctionAnalysis(SILFunction *F) override { |
| return llvm::make_unique<LoopRegionFunctionInfo>(F, POA->get(F), |
| SLA->get(F)); |
| } |
| |
| virtual bool shouldInvalidate(SILAnalysis::InvalidationKind K) override { |
| return K & InvalidationKind::Branches; |
| } |
| }; |
| |
| } // end namespace swift |
| |
| #endif |