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   // Get any virtual register that is assign to this physical unit
108   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<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(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)) {
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(1); }
160 
161     // Vector generated by collectInterferingVRegs.
162     const SmallVectorImpl<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