Home | History | Annotate | Download | only in CodeGen
      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)
    206