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