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 #include <algorithm>
  24
  25 namespace llvm {
  26
  27 class TargetRegisterInfo;
  28
  29 #ifndef NDEBUG
  30 // forward declaration
  31 template <unsigned Element> class SparseBitVector;
  32 typedef SparseBitVector<128> LiveVirtRegBitSet;
  33 #endif
  34
  35 /// Compare a live virtual register segment to a LiveIntervalUnion segment.
  36 inline bool
  37 overlap(const LiveRange &VRSeg,
  38         const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) {
  39   return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end;
  40 }
  41
  42 /// Union of live intervals that are strong candidates for coalescing into a
  43 /// single register (either physical or virtual depending on the context).  We
  44 /// expect the constituent live intervals to be disjoint, although we may
  45 /// eventually make exceptions to handle value-based interference.
  46 class LiveIntervalUnion {
  47   // A set of live virtual register segments that supports fast insertion,
  48   // intersection, and removal.
  49   // Mapping SlotIndex intervals to virtual register numbers.
  50   typedef IntervalMap<SlotIndex, LiveInterval*> LiveSegments;
  51
  52 public:
  53   // SegmentIter can advance to the next segment ordered by starting position
  54   // which may belong to a different live virtual register. We also must be able
  55   // to reach the current segment's containing virtual register.
  56   typedef LiveSegments::iterator SegmentIter;
  57
  58   // LiveIntervalUnions share an external allocator.
  59   typedef LiveSegments::Allocator Allocator;
  60
  61   class InterferenceResult;
  62   class Query;
  63
  64 private:
  65   const unsigned RepReg;  // representative register number
  66   LiveSegments Segments;  // union of virtual reg segments
  67
  68 public:
  69   LiveIntervalUnion(unsigned r, Allocator &a) : RepReg(r), Segments(a) {}
  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   // Add a live virtual register to this union and merge its segments.
  80   void unify(LiveInterval &VirtReg);
  81
  82   // Remove a live virtual register's segments from this union.
  83   void extract(LiveInterval &VirtReg);
  84
  85   // Print union, using TRI to translate register names
  86   void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
  87
  88 #ifndef NDEBUG
  89   // Verify the live intervals in this union and add them to the visited set.
  90   void verify(LiveVirtRegBitSet& VisitedVRegs);
  91 #endif
  92
  93   /// Cache a single interference test result in the form of two intersecting
  94   /// segments. This allows efficiently iterating over the interferences. The
  95   /// iteration logic is handled by LiveIntervalUnion::Query which may
  96   /// filter interferences depending on the type of query.
  97   class InterferenceResult {
  98     friend class Query;
  99
 100     LiveInterval::iterator VirtRegI; // current position in VirtReg
 101     SegmentIter LiveUnionI;          // current position in LiveUnion
 102
 103     // Internal ctor.
 104     InterferenceResult(LiveInterval::iterator VRegI, SegmentIter UnionI)
 105       : VirtRegI(VRegI), LiveUnionI(UnionI) {}
 106
 107   public:
 108     // Public default ctor.
 109     InterferenceResult(): VirtRegI(), LiveUnionI() {}
 110
 111     /// start - Return the start of the current overlap.
 112     SlotIndex start() const {
 113       return std::max(VirtRegI->start, LiveUnionI.start());
 114     }
 115
 116     /// stop - Return the end of the current overlap.
 117     SlotIndex stop() const {
 118       return std::min(VirtRegI->end, LiveUnionI.stop());
 119     }
 120
 121     /// interference - Return the register that is interfering here.
 122     LiveInterval *interference() const { return LiveUnionI.value(); }
 123
 124     // Note: this interface provides raw access to the iterators because the
 125     // result has no way to tell if it's valid to dereference them.
 126
 127     // Access the VirtReg segment.
 128     LiveInterval::iterator virtRegPos() const { return VirtRegI; }
 129
 130     // Access the LiveUnion segment.
 131     const SegmentIter &liveUnionPos() const { return LiveUnionI; }
 132
 133     bool operator==(const InterferenceResult &IR) const {
 134       return VirtRegI == IR.VirtRegI && LiveUnionI == IR.LiveUnionI;
 135     }
 136     bool operator!=(const InterferenceResult &IR) const {
 137       return !operator==(IR);
 138     }
 139
 140     void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
 141   };
 142
 143   /// Query interferences between a single live virtual register and a live
 144   /// interval union.
 145   class Query {
 146     LiveIntervalUnion *LiveUnion;
 147     LiveInterval *VirtReg;
 148     InterferenceResult FirstInterference;
 149     SmallVector<LiveInterval*,4> InterferingVRegs;
 150     bool CheckedFirstInterference;
 151     bool SeenAllInterferences;
 152     bool SeenUnspillableVReg;
 153
 154   public:
 155     Query(): LiveUnion(), VirtReg() {}
 156
 157     Query(LiveInterval *VReg, LiveIntervalUnion *LIU):
 158       LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false),
 159       SeenAllInterferences(false), SeenUnspillableVReg(false)
 160     {}
 161
 162     void clear() {
 163       LiveUnion = NULL;
 164       VirtReg = NULL;
 165       InterferingVRegs.clear();
 166       CheckedFirstInterference = false;
 167       SeenAllInterferences = false;
 168       SeenUnspillableVReg = false;
 169     }
 170
 171     void init(LiveInterval *VReg, LiveIntervalUnion *LIU) {
 172       assert(VReg && LIU && "Invalid arguments");
 173       if (VirtReg == VReg && LiveUnion == LIU) {
 174         // Retain cached results, e.g. firstInterference.
 175         return;
 176       }
 177       clear();
 178       LiveUnion = LIU;
 179       VirtReg = VReg;
 180     }
 181
 182     LiveInterval &virtReg() const {
 183       assert(VirtReg && "uninitialized");
 184       return *VirtReg;
 185     }
 186
 187     bool isInterference(const InterferenceResult &IR) const {
 188       if (IR.VirtRegI != VirtReg->end()) {
 189         assert(overlap(*IR.VirtRegI, IR.LiveUnionI) &&
 190                "invalid segment iterators");
 191         return true;
 192       }
 193       return false;
 194     }
 195
 196     // Does this live virtual register interfere with the union?
 197     bool checkInterference() { return isInterference(firstInterference()); }
 198
 199     // Get the first pair of interfering segments, or a noninterfering result.
 200     // This initializes the firstInterference_ cache.
 201     const InterferenceResult &firstInterference();
 202
 203     // Treat the result as an iterator and advance to the next interfering pair
 204     // of segments. Visiting each unique interfering pairs means that the same
 205     // VirtReg or LiveUnion segment may be visited multiple times.
 206     bool nextInterference(InterferenceResult &IR) const;
 207
 208     // Count the virtual registers in this union that interfere with this
 209     // query's live virtual register, up to maxInterferingRegs.
 210     unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX);
 211
 212     // Was this virtual register visited during collectInterferingVRegs?
 213     bool isSeenInterference(LiveInterval *VReg) const;
 214
 215     // Did collectInterferingVRegs collect all interferences?
 216     bool seenAllInterferences() const { return SeenAllInterferences; }
 217
 218     // Did collectInterferingVRegs encounter an unspillable vreg?
 219     bool seenUnspillableVReg() const { return SeenUnspillableVReg; }
 220
 221     // Vector generated by collectInterferingVRegs.
 222     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
 223       return InterferingVRegs;
 224     }
 225
 226     void print(raw_ostream &OS, const TargetRegisterInfo *TRI);
 227   private:
 228     Query(const Query&);          // DO NOT IMPLEMENT
 229     void operator=(const Query&); // DO NOT IMPLEMENT
 230
 231     // Private interface for queries
 232     void findIntersection(InterferenceResult &IR) const;
 233   };
 234 };
 235
 236 } // end namespace llvm
 237
 238 #endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION)