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, 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(LiveInterval &VirtReg, const LiveRange &Range);
92 
93   // Remove a live virtual register's segments from this union.
94   void extract(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   /// Query interferences between a single live virtual register and a live
108   /// interval union.
109   class Query {
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;
117     unsigned Tag = 0;
118     unsigned UserTag = 0;
119 
120     void reset(unsigned NewUserTag, const LiveRange &NewLR,
121                const LiveIntervalUnion &NewLiveUnion) {
122       LiveUnion = &NewLiveUnion;
123       LR = &NewLR;
124       InterferingVRegs.clear();
125       CheckedFirstInterference = false;
126       SeenAllInterferences = false;
127       Tag = NewLiveUnion.getTag();
128       UserTag = NewUserTag;
129     }
130 
131   public:
132     Query() = default;
133     Query(const LiveRange &LR, const LiveIntervalUnion &LIU):
134       LiveUnion(&LIU), LR(&LR) {}
135     Query(const Query &) = delete;
136     Query &operator=(const Query &) = delete;
137 
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.
143         return;
144       }
145       reset(NewUserTag, NewLR, NewLiveUnion);
146     }
147 
148     // Does this live virtual register interfere with the union?
149     bool checkInterference() { return collectInterferingVRegs(1); }
150 
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());
155 
156     // Was this virtual register visited during collectInterferingVRegs?
157     bool isSeenInterference(LiveInterval *VirtReg) const;
158 
159     // Did collectInterferingVRegs collect all interferences?
160     bool seenAllInterferences() const { return SeenAllInterferences; }
161 
162     // Vector generated by collectInterferingVRegs.
163     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
164       return InterferingVRegs;
165     }
166   };
167 
168   // Array of LiveIntervalUnions.
169   class Array {
170     unsigned Size = 0;
171     LiveIntervalUnion *LIUs = nullptr;
172 
173   public:
174     Array() = default;
175     ~Array() { clear(); }
176 
177     // Initialize the array to have Size entries.
178     // Reuse an existing allocation if the size matches.
179     void init(LiveIntervalUnion::Allocator&, unsigned Size);
180 
181     unsigned size() const { return Size; }
182 
183     void clear();
184 
185     LiveIntervalUnion& operator[](unsigned idx) {
186       assert(idx <  Size && "idx out of bounds");
187       return LIUs[idx];
188     }
189 
190     const LiveIntervalUnion& operator[](unsigned Idx) const {
191       assert(Idx < Size && "Idx out of bounds");
192       return LIUs[Idx];
193     }
194   };
195 };
196 
197 } // end namespace llvm
198 
199 #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H
200