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_H
18 #define LLVM_CODEGEN_LIVEINTERVALUNION_H
20 #include "llvm/ADT/IntervalMap.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/CodeGen/LiveInterval.h"
23 #include "llvm/CodeGen/SlotIndexes.h"
30 class TargetRegisterInfo;
33 // forward declaration
34 template <unsigned Element> class SparseBitVector;
36 using LiveVirtRegBitSet = SparseBitVector<128>;
39 /// Union of live intervals that are strong candidates for coalescing into a
40 /// single register (either physical or virtual depending on the context). We
41 /// expect the constituent live intervals to be disjoint, although we may
42 /// eventually make exceptions to handle value-based interference.
43 class LiveIntervalUnion {
44 // A set of live virtual register segments that supports fast insertion,
45 // intersection, and removal.
46 // Mapping SlotIndex intervals to virtual register numbers.
47 using LiveSegments = IntervalMap<SlotIndex, LiveInterval*>;
50 // SegmentIter can advance to the next segment ordered by starting position
51 // which may belong to a different live virtual register. We also must be able
52 // to reach the current segment's containing virtual register.
53 using SegmentIter = LiveSegments::iterator;
55 /// Const version of SegmentIter.
56 using ConstSegmentIter = LiveSegments::const_iterator;
58 // LiveIntervalUnions share an external allocator.
59 using Allocator = LiveSegments::Allocator;
62 unsigned Tag = 0; // unique tag for current contents.
63 LiveSegments Segments; // union of virtual reg segments
66 explicit LiveIntervalUnion(Allocator &a) : Segments(a) {}
68 // Iterate over all segments in the union of live virtual registers ordered
69 // by their starting position.
70 SegmentIter begin() { return Segments.begin(); }
71 SegmentIter end() { return Segments.end(); }
72 SegmentIter find(SlotIndex x) { return Segments.find(x); }
73 ConstSegmentIter begin() const { return Segments.begin(); }
74 ConstSegmentIter end() const { return Segments.end(); }
75 ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); }
77 bool empty() const { return Segments.empty(); }
78 SlotIndex startIndex() const { return Segments.start(); }
80 // Provide public access to the underlying map to allow overlap iteration.
81 using Map = LiveSegments;
82 const Map &getMap() const { return Segments; }
84 /// getTag - Return an opaque tag representing the current state of the union.
85 unsigned getTag() const { return Tag; }
87 /// changedSince - Return true if the union change since getTag returned tag.
88 bool changedSince(unsigned tag) const { return tag != Tag; }
90 // Add a live virtual register to this union and merge its segments.
91 void unify(LiveInterval &VirtReg, const LiveRange &Range);
93 // Remove a live virtual register's segments from this union.
94 void extract(LiveInterval &VirtReg, const LiveRange &Range);
96 // Remove all inserted virtual registers.
97 void clear() { Segments.clear(); ++Tag; }
99 // Print union, using TRI to translate register names
100 void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
103 // Verify the live intervals in this union and add them to the visited set.
104 void verify(LiveVirtRegBitSet& VisitedVRegs);
107 /// Query interferences between a single live virtual register and a live
110 const LiveIntervalUnion *LiveUnion = nullptr;
111 const LiveRange *LR = nullptr;
112 LiveRange::const_iterator LRI; ///< current position in LR
113 ConstSegmentIter LiveUnionI; ///< current position in LiveUnion
114 SmallVector<LiveInterval*,4> InterferingVRegs;
115 bool CheckedFirstInterference = false;
116 bool SeenAllInterferences = false;
118 unsigned UserTag = 0;
120 void reset(unsigned NewUserTag, const LiveRange &NewLR,
121 const LiveIntervalUnion &NewLiveUnion) {
122 LiveUnion = &NewLiveUnion;
124 InterferingVRegs.clear();
125 CheckedFirstInterference = false;
126 SeenAllInterferences = false;
127 Tag = NewLiveUnion.getTag();
128 UserTag = NewUserTag;
133 Query(const LiveRange &LR, const LiveIntervalUnion &LIU):
134 LiveUnion(&LIU), LR(&LR) {}
135 Query(const Query &) = delete;
136 Query &operator=(const Query &) = delete;
138 void init(unsigned NewUserTag, const LiveRange &NewLR,
139 const LiveIntervalUnion &NewLiveUnion) {
140 if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion &&
141 !NewLiveUnion.changedSince(Tag)) {
142 // Retain cached results, e.g. firstInterference.
145 reset(NewUserTag, NewLR, NewLiveUnion);
148 // Does this live virtual register interfere with the union?
149 bool checkInterference() { return collectInterferingVRegs(1); }
151 // Count the virtual registers in this union that interfere with this
152 // query's live virtual register, up to maxInterferingRegs.
153 unsigned collectInterferingVRegs(
154 unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max());
156 // Was this virtual register visited during collectInterferingVRegs?
157 bool isSeenInterference(LiveInterval *VReg) const;
159 // Did collectInterferingVRegs collect all interferences?
160 bool seenAllInterferences() const { return SeenAllInterferences; }
162 // Vector generated by collectInterferingVRegs.
163 const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
164 return InterferingVRegs;
168 // Array of LiveIntervalUnions.
171 LiveIntervalUnion *LIUs = nullptr;
175 ~Array() { clear(); }
177 // Initialize the array to have Size entries.
178 // Reuse an existing allocation if the size matches.
179 void init(LiveIntervalUnion::Allocator&, unsigned Size);
181 unsigned size() const { return Size; }
185 LiveIntervalUnion& operator[](unsigned idx) {
186 assert(idx < Size && "idx out of bounds");
190 const LiveIntervalUnion& operator[](unsigned Idx) const {
191 assert(Idx < Size && "Idx out of bounds");
197 } // end namespace llvm
199 #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H