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/CodeGen/LiveInterval.h"
  21 #include <vector>
  22 #include <set>
  23
  24 namespace llvm {
  25
  26 #ifndef NDEBUG
  27 // forward declaration
  28 template <unsigned Element> class SparseBitVector;
  29 typedef SparseBitVector<128> LiveVirtRegBitSet;
  30 #endif
  31
  32 /// A LiveSegment is a copy of a LiveRange object used within
  33 /// LiveIntervalUnion. LiveSegment additionally contains a pointer to its
  34 /// original live virtual register (LiveInterval). This allows quick lookup of
  35 /// the live virtual register as we iterate over live segments in a union. Note
  36 /// that LiveRange is misnamed and actually represents only a single contiguous
  37 /// interval within a virtual register's liveness. To limit confusion, in this
  38 /// file we refer it as a live segment.
  39 ///
  40 /// Note: This currently represents a half-open interval [Start,End).
  41 /// If LiveRange is modified to represent a closed interval, so should this.
  42 struct LiveSegment {
  43   SlotIndex Start;
  44   SlotIndex End;
  45   LiveInterval *VirtReg;
  46
  47   LiveSegment(const LiveRange& LR, LiveInterval *VReg)
  48     : Start(LR.start), End(LR.end), VirtReg(VReg) {}
  49
  50   bool operator==(const LiveSegment &LS) const {
  51     return Start == LS.Start && End == LS.End && VirtReg == LS.VirtReg;
  52   }
  53
  54   bool operator!=(const LiveSegment &LS) const {
  55     return !operator==(LS);
  56   }
  57
  58   // Order segments by starting point only--we expect them to be disjoint.
  59   bool operator<(const LiveSegment &LS) const { return Start < LS.Start; }
  60
  61   void dump() const;
  62   void print(raw_ostream &OS) const;
  63 };
  64
  65 inline bool operator<(SlotIndex Idx, const LiveSegment &LS) {
  66   return Idx < LS.Start;
  67 }
  68
  69 inline bool operator<(const LiveSegment &LS, SlotIndex Idx) {
  70   return LS.Start < Idx;
  71 }
  72
  73 /// Compare a live virtual register segment to a LiveIntervalUnion segment.
  74 inline bool overlap(const LiveRange &VirtRegSegment,
  75                     const LiveSegment &LiveUnionSegment) {
  76   return VirtRegSegment.start < LiveUnionSegment.End &&
  77     LiveUnionSegment.Start < VirtRegSegment.end;
  78 }
  79
  80 template <> struct isPodLike<LiveSegment> { static const bool value = true; };
  81
  82 raw_ostream& operator<<(raw_ostream& OS, const LiveSegment &LS);
  83
  84 /// Abstraction to provide info for the representative register.
  85 class AbstractRegisterDescription {
  86 public:
  87   virtual const char *getName(unsigned Reg) const = 0;
  88   virtual ~AbstractRegisterDescription() {}
  89 };
  90
  91 /// Union of live intervals that are strong candidates for coalescing into a
  92 /// single register (either physical or virtual depending on the context).  We
  93 /// expect the constituent live intervals to be disjoint, although we may
  94 /// eventually make exceptions to handle value-based interference.
  95 class LiveIntervalUnion {
  96   // A set of live virtual register segments that supports fast insertion,
  97   // intersection, and removal.
  98   //
  99   // FIXME: std::set is a placeholder until we decide how to
 100   // efficiently represent it. Probably need to roll our own B-tree.
 101   typedef std::set<LiveSegment> LiveSegments;
 102
 103   // A set of live virtual registers. Elements have type LiveInterval, where
 104   // each element represents the liveness of a single live virtual register.
 105   // This is traditionally known as a live range, but we refer is as a live
 106   // virtual register to avoid confusing it with the misnamed LiveRange
 107   // class.
 108   typedef std::vector<LiveInterval*> LiveVRegs;
 109
 110 public:
 111   // SegmentIter can advance to the next segment ordered by starting position
 112   // which may belong to a different live virtual register. We also must be able
 113   // to reach the current segment's containing virtual register.
 114   typedef LiveSegments::iterator SegmentIter;
 115
 116   class InterferenceResult;
 117   class Query;
 118
 119 private:
 120   unsigned RepReg;        // representative register number
 121   LiveSegments Segments;  // union of virtual reg segements
 122
 123 public:
 124   // default ctor avoids placement new
 125   LiveIntervalUnion() : RepReg(0) {}
 126
 127   // Initialize the union by associating it with a representative register
 128   // number.
 129   void init(unsigned Reg) { RepReg = Reg; }
 130
 131   // Iterate over all segments in the union of live virtual registers ordered
 132   // by their starting position.
 133   SegmentIter begin() { return Segments.begin(); }
 134   SegmentIter end() { return Segments.end(); }
 135
 136   // Return an iterator to the first segment after or including begin that
 137   // intersects with LS.
 138   SegmentIter upperBound(SegmentIter SegBegin, const LiveSegment &LS);
 139
 140   // Add a live virtual register to this union and merge its segments.
 141   // Holds a nonconst reference to the VirtReg for later maniplution.
 142   void unify(LiveInterval &VirtReg);
 143
 144   // Remove a live virtual register's segments from this union.
 145   void extract(const LiveInterval &VirtReg);
 146
 147   void dump(const AbstractRegisterDescription *RegDesc) const;
 148
 149   // If tri != NULL, use it to decode RepReg
 150   void print(raw_ostream &OS, const AbstractRegisterDescription *RegDesc) const;
 151
 152 #ifndef NDEBUG
 153   // Verify the live intervals in this union and add them to the visited set.
 154   void verify(LiveVirtRegBitSet& VisitedVRegs);
 155 #endif
 156
 157   /// Cache a single interference test result in the form of two intersecting
 158   /// segments. This allows efficiently iterating over the interferences. The
 159   /// iteration logic is handled by LiveIntervalUnion::Query which may
 160   /// filter interferences depending on the type of query.
 161   class InterferenceResult {
 162     friend class Query;
 163
 164     LiveInterval::iterator VirtRegI; // current position in VirtReg
 165     SegmentIter LiveUnionI;          // current position in LiveUnion
 166
 167     // Internal ctor.
 168     InterferenceResult(LiveInterval::iterator VRegI, SegmentIter UnionI)
 169       : VirtRegI(VRegI), LiveUnionI(UnionI) {}
 170
 171   public:
 172     // Public default ctor.
 173     InterferenceResult(): VirtRegI(), LiveUnionI() {}
 174
 175     // Note: this interface provides raw access to the iterators because the
 176     // result has no way to tell if it's valid to dereference them.
 177
 178     // Access the VirtReg segment.
 179     LiveInterval::iterator virtRegPos() const { return VirtRegI; }
 180
 181     // Access the LiveUnion segment.
 182     SegmentIter liveUnionPos() const { return LiveUnionI; }
 183
 184     bool operator==(const InterferenceResult &IR) const {
 185       return VirtRegI == IR.VirtRegI && LiveUnionI == IR.LiveUnionI;
 186     }
 187     bool operator!=(const InterferenceResult &IR) const {
 188       return !operator==(IR);
 189     }
 190   };
 191
 192   /// Query interferences between a single live virtual register and a live
 193   /// interval union.
 194   class Query {
 195     LiveIntervalUnion *LiveUnion;
 196     LiveInterval *VirtReg;
 197     InterferenceResult FirstInterference;
 198     SmallVector<LiveInterval*,4> InterferingVRegs;
 199     bool SeenAllInterferences;
 200     bool SeenUnspillableVReg;
 201
 202   public:
 203     Query(): LiveUnion(), VirtReg() {}
 204
 205     Query(LiveInterval *VReg, LiveIntervalUnion *LIU):
 206       LiveUnion(LIU), VirtReg(VReg), SeenAllInterferences(false),
 207       SeenUnspillableVReg(false)
 208     {}
 209
 210     void clear() {
 211       LiveUnion = NULL;
 212       VirtReg = NULL;
 213       FirstInterference = InterferenceResult();
 214       InterferingVRegs.clear();
 215       SeenAllInterferences = false;
 216       SeenUnspillableVReg = false;
 217     }
 218
 219     void init(LiveInterval *VReg, LiveIntervalUnion *LIU) {
 220       if (VirtReg == VReg) {
 221         // We currently allow query objects to be reused acrossed live virtual
 222         // registers, but always for the same live interval union.
 223         assert(LiveUnion == LIU && "inconsistent initialization");
 224         // Retain cached results, e.g. firstInterference.
 225         return;
 226       }
 227       clear();
 228       LiveUnion = LIU;
 229       VirtReg = VReg;
 230     }
 231
 232     LiveInterval &virtReg() const {
 233       assert(VirtReg && "uninitialized");
 234       return *VirtReg;
 235     }
 236
 237     bool isInterference(const InterferenceResult &IR) const {
 238       if (IR.VirtRegI != VirtReg->end()) {
 239         assert(overlap(*IR.VirtRegI, *IR.LiveUnionI) &&
 240                "invalid segment iterators");
 241         return true;
 242       }
 243       return false;
 244     }
 245
 246     // Does this live virtual register interfere with the union?
 247     bool checkInterference() { return isInterference(firstInterference()); }
 248
 249     // Get the first pair of interfering segments, or a noninterfering result.
 250     // This initializes the firstInterference_ cache.
 251     InterferenceResult firstInterference();
 252
 253     // Treat the result as an iterator and advance to the next interfering pair
 254     // of segments. Visiting each unique interfering pairs means that the same
 255     // VirtReg or LiveUnion segment may be visited multiple times.
 256     bool nextInterference(InterferenceResult &IR) const;
 257
 258     // Count the virtual registers in this union that interfere with this
 259     // query's live virtual register, up to maxInterferingRegs.
 260     unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX);
 261
 262     // Was this virtual register visited during collectInterferingVRegs?
 263     bool isSeenInterference(LiveInterval *VReg) const;
 264
 265     // Did collectInterferingVRegs collect all interferences?
 266     bool seenAllInterferences() const { return SeenAllInterferences; }
 267
 268     // Did collectInterferingVRegs encounter an unspillable vreg?
 269     bool seenUnspillableVReg() const { return SeenUnspillableVReg; }
 270
 271     // Vector generated by collectInterferingVRegs.
 272     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
 273       return InterferingVRegs;
 274     }
 275
 276   private:
 277     Query(const Query&);          // DO NOT IMPLEMENT
 278     void operator=(const Query&); // DO NOT IMPLEMENT
 279
 280     // Private interface for queries
 281     void findIntersection(InterferenceResult &IR) const;
 282   };
 283 };
 284
 285 } // end namespace llvm
 286
 287 #endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION)