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/ADT/SmallVector.h"
  22 #include "llvm/CodeGen/LiveInterval.h"
  23 #include "llvm/CodeGen/SlotIndexes.h"
  24 #include <cassert>
  25 #include <limits>
  26
  27 namespace llvm {
  28
  29 class raw_ostream;
  30 class TargetRegisterInfo;
  31
  32 #ifndef NDEBUG
  33 // forward declaration
  34 template <unsigned Element> class SparseBitVector;
  35
  36 using LiveVirtRegBitSet = SparseBitVector<128>;
  37 #endif
  38
  39 /// Union of live intervals that are strong candidates for coalescing into a
  40 /// single register (either physical or virtual depending on the context).  We
  41 /// expect the constituent live intervals to be disjoint, although we may
  42 /// eventually make exceptions to handle value-based interference.
  43 class LiveIntervalUnion {
  44   // A set of live virtual register segments that supports fast insertion,
  45   // intersection, and removal.
  46   // Mapping SlotIndex intervals to virtual register numbers.
  47   using LiveSegments = IntervalMap<SlotIndex, LiveInterval*>;
  48
  49 public:
  50   // SegmentIter can advance to the next segment ordered by starting position
  51   // which may belong to a different live virtual register. We also must be able
  52   // to reach the current segment's containing virtual register.
  53   using SegmentIter = LiveSegments::iterator;
  54
  55   /// Const version of SegmentIter.
  56   using ConstSegmentIter = LiveSegments::const_iterator;
  57
  58   // LiveIntervalUnions share an external allocator.
  59   using Allocator = LiveSegments::Allocator;
  60
  61 private:
  62   unsigned Tag = 0;       // unique tag for current contents.
  63   LiveSegments Segments;  // union of virtual reg segments
  64
  65 public:
  66   explicit LiveIntervalUnion(Allocator &a) : 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   ConstSegmentIter begin() const { return Segments.begin(); }
  74   ConstSegmentIter end() const { return Segments.end(); }
  75   ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); }
  76
  77   bool empty() const { return Segments.empty(); }
  78   SlotIndex startIndex() const { return Segments.start(); }
  79
  80   // Provide public access to the underlying map to allow overlap iteration.
  81   using Map = LiveSegments;
  82   const Map &getMap() const { return Segments; }
  83
  84   /// getTag - Return an opaque tag representing the current state of the union.
  85   unsigned getTag() const { return Tag; }
  86
  87   /// changedSince - Return true if the union change since getTag returned tag.
  88   bool changedSince(unsigned tag) const { return tag != Tag; }
  89
  90   // Add a live virtual register to this union and merge its segments.
  91   void unify(LiveInterval &VirtReg, const LiveRange &Range);
  92
  93   // Remove a live virtual register's segments from this union.
  94   void extract(LiveInterval &VirtReg, const LiveRange &Range);
  95
  96   // Remove all inserted virtual registers.
  97   void clear() { Segments.clear(); ++Tag; }
  98
  99   // Print union, using TRI to translate register names
 100   void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
 101
 102 #ifndef NDEBUG
 103   // Verify the live intervals in this union and add them to the visited set.
 104   void verify(LiveVirtRegBitSet& VisitedVRegs);
 105 #endif
 106
 107   /// Query interferences between a single live virtual register and a live
 108   /// interval union.
 109   class Query {
 110     const LiveIntervalUnion *LiveUnion = nullptr;
 111     const LiveRange *LR = nullptr;
 112     LiveRange::const_iterator LRI;  ///< current position in LR
 113     ConstSegmentIter LiveUnionI;    ///< current position in LiveUnion
 114     SmallVector<LiveInterval*,4> InterferingVRegs;
 115     bool CheckedFirstInterference = false;
 116     bool SeenAllInterferences = false;
 117     unsigned Tag = 0;
 118     unsigned UserTag = 0;
 119
 120     void reset(unsigned NewUserTag, const LiveRange &NewLR,
 121                const LiveIntervalUnion &NewLiveUnion) {
 122       LiveUnion = &NewLiveUnion;
 123       LR = &NewLR;
 124       InterferingVRegs.clear();
 125       CheckedFirstInterference = false;
 126       SeenAllInterferences = false;
 127       Tag = NewLiveUnion.getTag();
 128       UserTag = NewUserTag;
 129     }
 130
 131   public:
 132     Query() = default;
 133     Query(const LiveRange &LR, const LiveIntervalUnion &LIU):
 134       LiveUnion(&LIU), LR(&LR) {}
 135     Query(const Query &) = delete;
 136     Query &operator=(const Query &) = delete;
 137
 138     void init(unsigned NewUserTag, const LiveRange &NewLR,
 139               const LiveIntervalUnion &NewLiveUnion) {
 140       if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion &&
 141           !NewLiveUnion.changedSince(Tag)) {
 142         // Retain cached results, e.g. firstInterference.
 143         return;
 144       }
 145       reset(NewUserTag, NewLR, NewLiveUnion);
 146     }
 147
 148     // Does this live virtual register interfere with the union?
 149     bool checkInterference() { return collectInterferingVRegs(1); }
 150
 151     // Count the virtual registers in this union that interfere with this
 152     // query's live virtual register, up to maxInterferingRegs.
 153     unsigned collectInterferingVRegs(
 154         unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max());
 155
 156     // Was this virtual register visited during collectInterferingVRegs?
 157     bool isSeenInterference(LiveInterval *VirtReg) const;
 158
 159     // Did collectInterferingVRegs collect all interferences?
 160     bool seenAllInterferences() const { return SeenAllInterferences; }
 161
 162     // Vector generated by collectInterferingVRegs.
 163     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
 164       return InterferingVRegs;
 165     }
 166   };
 167
 168   // Array of LiveIntervalUnions.
 169   class Array {
 170     unsigned Size = 0;
 171     LiveIntervalUnion *LIUs = nullptr;
 172
 173   public:
 174     Array() = default;
 175     ~Array() { clear(); }
 176
 177     // Initialize the array to have Size entries.
 178     // Reuse an existing allocation if the size matches.
 179     void init(LiveIntervalUnion::Allocator&, unsigned Size);
 180
 181     unsigned size() const { return Size; }
 182
 183     void clear();
 184
 185     LiveIntervalUnion& operator[](unsigned idx) {
 186       assert(idx <  Size && "idx out of bounds");
 187       return LIUs[idx];
 188     }
 189
 190     const LiveIntervalUnion& operator[](unsigned Idx) const {
 191       assert(Idx < Size && "Idx out of bounds");
 192       return LIUs[Idx];
 193     }
 194   };
 195 };
 196
 197 } // end namespace llvm
 198
 199 #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H