1 //===-- LiveIntervalUnion.h - Live interval union data struct --*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // LiveIntervalUnion is a union of live segments across multiple live virtual
11 // registers. This may be used during coalescing to represent a congruence
12 // class, or during register allocation to model liveness of a physical
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_CODEGEN_LIVEINTERVALUNION
18 #define LLVM_CODEGEN_LIVEINTERVALUNION
20 #include "llvm/CodeGen/LiveInterval.h"
26 // forward declaration
27 template <unsigned Element> class SparseBitVector;
28 typedef SparseBitVector<128> LiveVirtRegBitSet;
31 /// A LiveSegment is a copy of a LiveRange object used within
32 /// LiveIntervalUnion. LiveSegment additionally contains a pointer to its
33 /// original live virtual register (LiveInterval). This allows quick lookup of
34 /// the live virtual register as we iterate over live segments in a union. Note
35 /// that LiveRange is misnamed and actually represents only a single contiguous
36 /// interval within a virtual register's liveness. To limit confusion, in this
37 /// file we refer it as a live segment.
39 /// Note: This currently represents a half-open interval [Start,End).
40 /// If LiveRange is modified to represent a closed interval, so should this.
44 LiveInterval *VirtReg;
46 LiveSegment(const LiveRange& LR, LiveInterval *VReg)
47 : Start(LR.start), End(LR.end), VirtReg(VReg) {}
49 bool operator==(const LiveSegment &LS) const {
50 return Start == LS.Start && End == LS.End && VirtReg == LS.VirtReg;
53 bool operator!=(const LiveSegment &LS) const {
54 return !operator==(LS);
57 // Order segments by starting point only--we expect them to be disjoint.
58 bool operator<(const LiveSegment &LS) const { return Start < LS.Start; }
61 void print(raw_ostream &OS) const;
64 inline bool operator<(SlotIndex Idx, const LiveSegment &LS) {
65 return Idx < LS.Start;
68 inline bool operator<(const LiveSegment &LS, SlotIndex Idx) {
69 return LS.Start < Idx;
72 /// Compare a live virtual register segment to a LiveIntervalUnion segment.
73 inline bool overlap(const LiveRange &VirtRegSegment,
74 const LiveSegment &LiveUnionSegment) {
75 return VirtRegSegment.start < LiveUnionSegment.End &&
76 LiveUnionSegment.Start < VirtRegSegment.end;
79 template <> struct isPodLike<LiveSegment> { static const bool value = true; };
81 raw_ostream& operator<<(raw_ostream& OS, const LiveSegment &LS);
83 /// Abstraction to provide info for the representative register.
84 class AbstractRegisterDescription {
86 virtual const char *getName(unsigned Reg) const = 0;
87 virtual ~AbstractRegisterDescription() {}
90 /// Union of live intervals that are strong candidates for coalescing into a
91 /// single register (either physical or virtual depending on the context). We
92 /// expect the constituent live intervals to be disjoint, although we may
93 /// eventually make exceptions to handle value-based interference.
94 class LiveIntervalUnion {
95 // A set of live virtual register segments that supports fast insertion,
96 // intersection, and removal.
98 // FIXME: std::set is a placeholder until we decide how to
99 // efficiently represent it. Probably need to roll our own B-tree.
100 typedef std::set<LiveSegment> LiveSegments;
103 // SegmentIter can advance to the next segment ordered by starting position
104 // which may belong to a different live virtual register. We also must be able
105 // to reach the current segment's containing virtual register.
106 typedef LiveSegments::iterator SegmentIter;
108 class InterferenceResult;
112 unsigned RepReg; // representative register number
113 LiveSegments Segments; // union of virtual reg segements
116 // default ctor avoids placement new
117 LiveIntervalUnion() : RepReg(0) {}
119 // Initialize the union by associating it with a representative register
121 void init(unsigned Reg) { RepReg = Reg; }
123 // Iterate over all segments in the union of live virtual registers ordered
124 // by their starting position.
125 SegmentIter begin() { return Segments.begin(); }
126 SegmentIter end() { return Segments.end(); }
128 // Return an iterator to the first segment after or including begin that
129 // intersects with LS.
130 SegmentIter upperBound(SegmentIter SegBegin, const LiveSegment &LS);
132 // Add a live virtual register to this union and merge its segments.
133 // Holds a nonconst reference to the VirtReg for later maniplution.
134 void unify(LiveInterval &VirtReg);
136 // Remove a live virtual register's segments from this union.
137 void extract(const LiveInterval &VirtReg);
139 void dump(const AbstractRegisterDescription *RegDesc) const;
141 // If tri != NULL, use it to decode RepReg
142 void print(raw_ostream &OS, const AbstractRegisterDescription *RegDesc) const;
145 // Verify the live intervals in this union and add them to the visited set.
146 void verify(LiveVirtRegBitSet& VisitedVRegs);
149 /// Cache a single interference test result in the form of two intersecting
150 /// segments. This allows efficiently iterating over the interferences. The
151 /// iteration logic is handled by LiveIntervalUnion::Query which may
152 /// filter interferences depending on the type of query.
153 class InterferenceResult {
156 LiveInterval::iterator VirtRegI; // current position in VirtReg
157 SegmentIter LiveUnionI; // current position in LiveUnion
160 InterferenceResult(LiveInterval::iterator VRegI, SegmentIter UnionI)
161 : VirtRegI(VRegI), LiveUnionI(UnionI) {}
164 // Public default ctor.
165 InterferenceResult(): VirtRegI(), LiveUnionI() {}
167 // Note: this interface provides raw access to the iterators because the
168 // result has no way to tell if it's valid to dereference them.
170 // Access the VirtReg segment.
171 LiveInterval::iterator virtRegPos() const { return VirtRegI; }
173 // Access the LiveUnion segment.
174 SegmentIter liveUnionPos() const { return LiveUnionI; }
176 bool operator==(const InterferenceResult &IR) const {
177 return VirtRegI == IR.VirtRegI && LiveUnionI == IR.LiveUnionI;
179 bool operator!=(const InterferenceResult &IR) const {
180 return !operator==(IR);
184 /// Query interferences between a single live virtual register and a live
187 LiveIntervalUnion *LiveUnion;
188 LiveInterval *VirtReg;
189 InterferenceResult FirstInterference;
190 SmallVector<LiveInterval*,4> InterferingVRegs;
191 bool SeenAllInterferences;
192 bool SeenUnspillableVReg;
195 Query(): LiveUnion(), VirtReg() {}
197 Query(LiveInterval *VReg, LiveIntervalUnion *LIU):
198 LiveUnion(LIU), VirtReg(VReg), SeenAllInterferences(false),
199 SeenUnspillableVReg(false)
205 FirstInterference = InterferenceResult();
206 InterferingVRegs.clear();
207 SeenAllInterferences = false;
208 SeenUnspillableVReg = false;
211 void init(LiveInterval *VReg, LiveIntervalUnion *LIU) {
212 if (VirtReg == VReg) {
213 // We currently allow query objects to be reused acrossed live virtual
214 // registers, but always for the same live interval union.
215 assert(LiveUnion == LIU && "inconsistent initialization");
216 // Retain cached results, e.g. firstInterference.
224 LiveInterval &virtReg() const {
225 assert(VirtReg && "uninitialized");
229 bool isInterference(const InterferenceResult &IR) const {
230 if (IR.VirtRegI != VirtReg->end()) {
231 assert(overlap(*IR.VirtRegI, *IR.LiveUnionI) &&
232 "invalid segment iterators");
238 // Does this live virtual register interfere with the union?
239 bool checkInterference() { return isInterference(firstInterference()); }
241 // Get the first pair of interfering segments, or a noninterfering result.
242 // This initializes the firstInterference_ cache.
243 InterferenceResult firstInterference();
245 // Treat the result as an iterator and advance to the next interfering pair
246 // of segments. Visiting each unique interfering pairs means that the same
247 // VirtReg or LiveUnion segment may be visited multiple times.
248 bool nextInterference(InterferenceResult &IR) const;
250 // Count the virtual registers in this union that interfere with this
251 // query's live virtual register, up to maxInterferingRegs.
252 unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX);
254 // Was this virtual register visited during collectInterferingVRegs?
255 bool isSeenInterference(LiveInterval *VReg) const;
257 // Did collectInterferingVRegs collect all interferences?
258 bool seenAllInterferences() const { return SeenAllInterferences; }
260 // Did collectInterferingVRegs encounter an unspillable vreg?
261 bool seenUnspillableVReg() const { return SeenUnspillableVReg; }
263 // Vector generated by collectInterferingVRegs.
264 const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
265 return InterferingVRegs;
269 Query(const Query&); // DO NOT IMPLEMENT
270 void operator=(const Query&); // DO NOT IMPLEMENT
272 // Private interface for queries
273 void findIntersection(InterferenceResult &IR) const;
277 } // end namespace llvm
279 #endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION)