lib/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
  18 #define LLVM_CODEGEN_LIVEINTERVALUNION
  19
  20 #include "llvm/ADT/IntervalMap.h"
  21 #include "llvm/CodeGen/LiveInterval.h"
  22
  23 namespace llvm {
  24
  25 class MachineLoopRange;
  26 class TargetRegisterInfo;
  27
  28 #ifndef NDEBUG
  29 // forward declaration
  30 template <unsigned Element> class SparseBitVector;
  31 typedef SparseBitVector<128> LiveVirtRegBitSet;
  32 #endif
  33
  34 /// Compare a live virtual register segment to a LiveIntervalUnion segment.
  35 inline bool
  36 overlap(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.
  45 class 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
  51 public:
  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
  62 private:
  63   const unsigned RepReg;  // representative register number
  64   unsigned Tag;           // unique tag for current contents.
  65   LiveSegments Segments;  // union of virtual reg segments
  66
  67 public:
  68   LiveIntervalUnion(unsigned r, Allocator &a) : RepReg(r), Tag(0), Segments(a)
  69     {}
  70
  71   // Iterate over all segments in the union of live virtual registers ordered
  72   // by their starting position.
  73   SegmentIter begin() { return Segments.begin(); }
  74   SegmentIter end() { return Segments.end(); }
  75   SegmentIter find(SlotIndex x) { return Segments.find(x); }
  76   bool empty() const { return Segments.empty(); }
  77   SlotIndex startIndex() const { return Segments.start(); }
  78
  79   // Provide public access to the underlying map to allow overlap iteration.
  80   typedef LiveSegments Map;
  81   const Map &getMap() { return Segments; }
  82
  83   /// getTag - Return an opaque tag representing the current state of the union.
  84   unsigned getTag() const { return Tag; }
  85
  86   /// changedSince - Return true if the union change since getTag returned tag.
  87   bool changedSince(unsigned tag) const { return tag != Tag; }
  88
  89   // Add a live virtual register to this union and merge its segments.
  90   void unify(LiveInterval &VirtReg);
  91
  92   // Remove a live virtual register's segments from this union.
  93   void extract(LiveInterval &VirtReg);
  94
  95   // Remove all inserted virtual registers.
  96   void clear() { Segments.clear(); ++Tag; }
  97
  98   // Print union, using TRI to translate register names
  99   void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
 100
 101 #ifndef NDEBUG
 102   // Verify the live intervals in this union and add them to the visited set.
 103   void verify(LiveVirtRegBitSet& VisitedVRegs);
 104 #endif
 105
 106   /// Query interferences between a single live virtual register and a live
 107   /// interval union.
 108   class Query {
 109     LiveIntervalUnion *LiveUnion;
 110     LiveInterval *VirtReg;
 111     LiveInterval::iterator VirtRegI; // current position in VirtReg
 112     SegmentIter LiveUnionI;          // current position in LiveUnion
 113     SmallVector<LiveInterval*,4> InterferingVRegs;
 114     bool CheckedFirstInterference;
 115     bool SeenAllInterferences;
 116     bool SeenUnspillableVReg;
 117     unsigned Tag, UserTag;
 118
 119   public:
 120     Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {}
 121
 122     Query(LiveInterval *VReg, LiveIntervalUnion *LIU):
 123       LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false),
 124       SeenAllInterferences(false), SeenUnspillableVReg(false)
 125     {}
 126
 127     void clear() {
 128       LiveUnion = NULL;
 129       VirtReg = NULL;
 130       InterferingVRegs.clear();
 131       CheckedFirstInterference = false;
 132       SeenAllInterferences = false;
 133       SeenUnspillableVReg = false;
 134       Tag = 0;
 135       UserTag = 0;
 136     }
 137
 138     void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) {
 139       assert(VReg && LIU && "Invalid arguments");
 140       if (UserTag == UTag && VirtReg == VReg &&
 141           LiveUnion == LIU && !LIU->changedSince(Tag)) {
 142         // Retain cached results, e.g. firstInterference.
 143         return;
 144       }
 145       clear();
 146       LiveUnion = LIU;
 147       VirtReg = VReg;
 148       Tag = LIU->getTag();
 149       UserTag = UTag;
 150     }
 151
 152     LiveInterval &virtReg() const {
 153       assert(VirtReg && "uninitialized");
 154       return *VirtReg;
 155     }
 156
 157     // Does this live virtual register interfere with the union?
 158     bool checkInterference() { return collectInterferingVRegs(1); }
 159
 160     // Count the virtual registers in this union that interfere with this
 161     // query's live virtual register, up to maxInterferingRegs.
 162     unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX);
 163
 164     // Was this virtual register visited during collectInterferingVRegs?
 165     bool isSeenInterference(LiveInterval *VReg) const;
 166
 167     // Did collectInterferingVRegs collect all interferences?
 168     bool seenAllInterferences() const { return SeenAllInterferences; }
 169
 170     // Did collectInterferingVRegs encounter an unspillable vreg?
 171     bool seenUnspillableVReg() const { return SeenUnspillableVReg; }
 172
 173     // Vector generated by collectInterferingVRegs.
 174     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
 175       return InterferingVRegs;
 176     }
 177
 178     /// checkLoopInterference - Return true if there is interference overlapping
 179     /// Loop.
 180     bool checkLoopInterference(MachineLoopRange*);
 181
 182   private:
 183     Query(const Query&);          // DO NOT IMPLEMENT
 184     void operator=(const Query&); // DO NOT IMPLEMENT
 185   };
 186 };
 187
 188 } // end namespace llvm
 189
 190 #endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION)