1 | //===- LiveIntervalUnion.h - Live interval union data struct ---*- C++ -*--===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // LiveIntervalUnion is a union of live segments across multiple live virtual |
10 | // registers. This may be used during coalescing to represent a congruence |
11 | // class, or during register allocation to model liveness of a physical |
12 | // register. |
13 | // |
14 | //===----------------------------------------------------------------------===// |
15 | |
16 | #ifndef LLVM_CODEGEN_LIVEINTERVALUNION_H |
17 | #define LLVM_CODEGEN_LIVEINTERVALUNION_H |
18 | |
19 | #include "llvm/ADT/IntervalMap.h" |
20 | #include "llvm/ADT/SmallVector.h" |
21 | #include "llvm/CodeGen/LiveInterval.h" |
22 | #include "llvm/CodeGen/SlotIndexes.h" |
23 | #include <cassert> |
24 | #include <limits> |
25 | |
26 | namespace llvm { |
27 | |
28 | class raw_ostream; |
29 | class TargetRegisterInfo; |
30 | |
31 | #ifndef NDEBUG |
32 | // forward declaration |
33 | template <unsigned Element> class SparseBitVector; |
34 | |
35 | using LiveVirtRegBitSet = SparseBitVector<128>; |
36 | #endif |
37 | |
38 | /// Union of live intervals that are strong candidates for coalescing into a |
39 | /// single register (either physical or virtual depending on the context). We |
40 | /// expect the constituent live intervals to be disjoint, although we may |
41 | /// eventually make exceptions to handle value-based interference. |
42 | class LiveIntervalUnion { |
43 | // A set of live virtual register segments that supports fast insertion, |
44 | // intersection, and removal. |
45 | // Mapping SlotIndex intervals to virtual register numbers. |
46 | using LiveSegments = IntervalMap<SlotIndex, const LiveInterval *>; |
47 | |
48 | public: |
49 | // SegmentIter can advance to the next segment ordered by starting position |
50 | // which may belong to a different live virtual register. We also must be able |
51 | // to reach the current segment's containing virtual register. |
52 | using SegmentIter = LiveSegments::iterator; |
53 | |
54 | /// Const version of SegmentIter. |
55 | using ConstSegmentIter = LiveSegments::const_iterator; |
56 | |
57 | // LiveIntervalUnions share an external allocator. |
58 | using Allocator = LiveSegments::Allocator; |
59 | |
60 | private: |
61 | unsigned Tag = 0; // unique tag for current contents. |
62 | LiveSegments Segments; // union of virtual reg segments |
63 | |
64 | public: |
65 | explicit LiveIntervalUnion(Allocator &a) : Segments(a) {} |
66 | |
67 | // Iterate over all segments in the union of live virtual registers ordered |
68 | // by their starting position. |
69 | SegmentIter begin() { return Segments.begin(); } |
70 | SegmentIter end() { return Segments.end(); } |
71 | SegmentIter find(SlotIndex x) { return Segments.find(x); } |
72 | ConstSegmentIter begin() const { return Segments.begin(); } |
73 | ConstSegmentIter end() const { return Segments.end(); } |
74 | ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); } |
75 | |
76 | bool empty() const { return Segments.empty(); } |
77 | SlotIndex startIndex() const { return Segments.start(); } |
78 | SlotIndex endIndex() const { return Segments.stop(); } |
79 | |
80 | // Provide public access to the underlying map to allow overlap iteration. |
81 | using Map = LiveSegments; |
82 | const Map &getMap() const { return Segments; } |
83 | |
84 | /// getTag - Return an opaque tag representing the current state of the union. |
85 | unsigned getTag() const { return Tag; } |
86 | |
87 | /// changedSince - Return true if the union change since getTag returned tag. |
88 | bool changedSince(unsigned tag) const { return tag != Tag; } |
89 | |
90 | // Add a live virtual register to this union and merge its segments. |
91 | void unify(const LiveInterval &VirtReg, const LiveRange &Range); |
92 | |
93 | // Remove a live virtual register's segments from this union. |
94 | void (const LiveInterval &VirtReg, const LiveRange &Range); |
95 | |
96 | // Remove all inserted virtual registers. |
97 | void clear() { Segments.clear(); ++Tag; } |
98 | |
99 | // Print union, using TRI to translate register names |
100 | void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; |
101 | |
102 | #ifndef NDEBUG |
103 | // Verify the live intervals in this union and add them to the visited set. |
104 | void verify(LiveVirtRegBitSet& VisitedVRegs); |
105 | #endif |
106 | |
107 | // Get any virtual register that is assign to this physical unit |
108 | const LiveInterval *getOneVReg() const; |
109 | |
110 | /// Query interferences between a single live virtual register and a live |
111 | /// interval union. |
112 | class Query { |
113 | const LiveIntervalUnion *LiveUnion = nullptr; |
114 | const LiveRange *LR = nullptr; |
115 | LiveRange::const_iterator LRI; ///< current position in LR |
116 | ConstSegmentIter LiveUnionI; ///< current position in LiveUnion |
117 | SmallVector<const LiveInterval *, 4> InterferingVRegs; |
118 | bool CheckedFirstInterference = false; |
119 | bool SeenAllInterferences = false; |
120 | unsigned Tag = 0; |
121 | unsigned UserTag = 0; |
122 | |
123 | // Count the virtual registers in this union that interfere with this |
124 | // query's live virtual register, up to maxInterferingRegs. |
125 | unsigned collectInterferingVRegs(unsigned MaxInterferingRegs); |
126 | |
127 | // Was this virtual register visited during collectInterferingVRegs? |
128 | bool isSeenInterference(const LiveInterval *VirtReg) const; |
129 | |
130 | public: |
131 | Query() = default; |
132 | Query(const LiveRange &LR, const LiveIntervalUnion &LIU) |
133 | : LiveUnion(&LIU), LR(&LR) {} |
134 | Query(const Query &) = delete; |
135 | Query &operator=(const Query &) = delete; |
136 | |
137 | void reset(unsigned NewUserTag, const LiveRange &NewLR, |
138 | const LiveIntervalUnion &NewLiveUnion) { |
139 | LiveUnion = &NewLiveUnion; |
140 | LR = &NewLR; |
141 | InterferingVRegs.clear(); |
142 | CheckedFirstInterference = false; |
143 | SeenAllInterferences = false; |
144 | Tag = NewLiveUnion.getTag(); |
145 | UserTag = NewUserTag; |
146 | } |
147 | |
148 | void init(unsigned NewUserTag, const LiveRange &NewLR, |
149 | const LiveIntervalUnion &NewLiveUnion) { |
150 | if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion && |
151 | !NewLiveUnion.changedSince(tag: Tag)) { |
152 | // Retain cached results, e.g. firstInterference. |
153 | return; |
154 | } |
155 | reset(NewUserTag, NewLR, NewLiveUnion); |
156 | } |
157 | |
158 | // Does this live virtual register interfere with the union? |
159 | bool checkInterference() { return collectInterferingVRegs(MaxInterferingRegs: 1); } |
160 | |
161 | // Vector generated by collectInterferingVRegs. |
162 | const SmallVectorImpl<const LiveInterval *> &interferingVRegs( |
163 | unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max()) { |
164 | if (!SeenAllInterferences || MaxInterferingRegs < InterferingVRegs.size()) |
165 | collectInterferingVRegs(MaxInterferingRegs); |
166 | return InterferingVRegs; |
167 | } |
168 | }; |
169 | |
170 | // Array of LiveIntervalUnions. |
171 | class Array { |
172 | unsigned Size = 0; |
173 | LiveIntervalUnion *LIUs = nullptr; |
174 | |
175 | public: |
176 | Array() = default; |
177 | ~Array() { clear(); } |
178 | |
179 | // Initialize the array to have Size entries. |
180 | // Reuse an existing allocation if the size matches. |
181 | void init(LiveIntervalUnion::Allocator&, unsigned Size); |
182 | |
183 | unsigned size() const { return Size; } |
184 | |
185 | void clear(); |
186 | |
187 | LiveIntervalUnion& operator[](unsigned idx) { |
188 | assert(idx < Size && "idx out of bounds" ); |
189 | return LIUs[idx]; |
190 | } |
191 | |
192 | const LiveIntervalUnion& operator[](unsigned Idx) const { |
193 | assert(Idx < Size && "Idx out of bounds" ); |
194 | return LIUs[Idx]; |
195 | } |
196 | }; |
197 | }; |
198 | |
199 | } // end namespace llvm |
200 | |
201 | #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H |
202 | |