contrib/llvm/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 LiveRange &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);
  88
  89   // Remove a live virtual register's segments from this union.
  90   void extract(LiveInterval &VirtReg);
  91
  92   // Remove all inserted virtual registers.
  93   void clear() { Segments.clear(); ++Tag; }
  94
  95   // Print union, using TRI to translate register names
  96   void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
  97
  98 #ifndef NDEBUG
  99   // Verify the live intervals in this union and add them to the visited set.
 100   void verify(LiveVirtRegBitSet& VisitedVRegs);
 101 #endif
 102
 103   /// Query interferences between a single live virtual register and a live
 104   /// interval union.
 105   class Query {
 106     LiveIntervalUnion *LiveUnion;
 107     LiveInterval *VirtReg;
 108     LiveInterval::iterator VirtRegI; // current position in VirtReg
 109     SegmentIter LiveUnionI;          // current position in LiveUnion
 110     SmallVector<LiveInterval*,4> InterferingVRegs;
 111     bool CheckedFirstInterference;
 112     bool SeenAllInterferences;
 113     bool SeenUnspillableVReg;
 114     unsigned Tag, UserTag;
 115
 116   public:
 117     Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {}
 118
 119     Query(LiveInterval *VReg, LiveIntervalUnion *LIU):
 120       LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false),
 121       SeenAllInterferences(false), SeenUnspillableVReg(false)
 122     {}
 123
 124     void clear() {
 125       LiveUnion = NULL;
 126       VirtReg = NULL;
 127       InterferingVRegs.clear();
 128       CheckedFirstInterference = false;
 129       SeenAllInterferences = false;
 130       SeenUnspillableVReg = false;
 131       Tag = 0;
 132       UserTag = 0;
 133     }
 134
 135     void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) {
 136       assert(VReg && LIU && "Invalid arguments");
 137       if (UserTag == UTag && VirtReg == VReg &&
 138           LiveUnion == LIU && !LIU->changedSince(Tag)) {
 139         // Retain cached results, e.g. firstInterference.
 140         return;
 141       }
 142       clear();
 143       LiveUnion = LIU;
 144       VirtReg = VReg;
 145       Tag = LIU->getTag();
 146       UserTag = UTag;
 147     }
 148
 149     LiveInterval &virtReg() const {
 150       assert(VirtReg && "uninitialized");
 151       return *VirtReg;
 152     }
 153
 154     // Does this live virtual register interfere with the union?
 155     bool checkInterference() { return collectInterferingVRegs(1); }
 156
 157     // Count the virtual registers in this union that interfere with this
 158     // query's live virtual register, up to maxInterferingRegs.
 159     unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX);
 160
 161     // Was this virtual register visited during collectInterferingVRegs?
 162     bool isSeenInterference(LiveInterval *VReg) const;
 163
 164     // Did collectInterferingVRegs collect all interferences?
 165     bool seenAllInterferences() const { return SeenAllInterferences; }
 166
 167     // Did collectInterferingVRegs encounter an unspillable vreg?
 168     bool seenUnspillableVReg() const { return SeenUnspillableVReg; }
 169
 170     // Vector generated by collectInterferingVRegs.
 171     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
 172       return InterferingVRegs;
 173     }
 174
 175   private:
 176     Query(const Query&) LLVM_DELETED_FUNCTION;
 177     void operator=(const Query&) LLVM_DELETED_FUNCTION;
 178   };
 179
 180   // Array of LiveIntervalUnions.
 181   class Array {
 182     unsigned Size;
 183     LiveIntervalUnion *LIUs;
 184   public:
 185     Array() : Size(0), LIUs(0) {}
 186     ~Array() { clear(); }
 187
 188     // Initialize the array to have Size entries.
 189     // Reuse an existing allocation if the size matches.
 190     void init(LiveIntervalUnion::Allocator&, unsigned Size);
 191
 192     unsigned size() const { return Size; }
 193
 194     void clear();
 195
 196     LiveIntervalUnion& operator[](unsigned idx) {
 197       assert(idx <  Size && "idx out of bounds");
 198       return LIUs[idx];
 199     }
 200   };
 201 };
 202
 203 } // end namespace llvm
 204
 205 #endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION_H)