include/llvm/CodeGen/LiveIntervalUnion.h

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