include/llvm/CodeGen/LiveIntervalUnion.h

   1 //===- LiveIntervalUnion.h - Live interval union data struct ---*- C++ -*--===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // LiveIntervalUnion is a union of live segments across multiple live virtual
  10 // registers. This may be used during coalescing to represent a congruence
  11 // class, or during register allocation to model liveness of a physical
  12 // register.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CODEGEN_LIVEINTERVALUNION_H
  17 #define LLVM_CODEGEN_LIVEINTERVALUNION_H
  18
  19 #include "llvm/ADT/IntervalMap.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/CodeGen/LiveInterval.h"
  22 #include "llvm/CodeGen/SlotIndexes.h"
  23 #include <cassert>
  24 #include <limits>
  25
  26 namespace llvm {
  27
  28 class raw_ostream;
  29 class TargetRegisterInfo;
  30
  31 #ifndef NDEBUG
  32 // forward declaration
  33 template <unsigned Element> class SparseBitVector;
  34
  35 using LiveVirtRegBitSet = SparseBitVector<128>;
  36 #endif
  37
  38 /// Union of live intervals that are strong candidates for coalescing into a
  39 /// single register (either physical or virtual depending on the context).  We
  40 /// expect the constituent live intervals to be disjoint, although we may
  41 /// eventually make exceptions to handle value-based interference.
  42 class LiveIntervalUnion {
  43   // A set of live virtual register segments that supports fast insertion,
  44   // intersection, and removal.
  45   // Mapping SlotIndex intervals to virtual register numbers.
  46   using LiveSegments = IntervalMap<SlotIndex, LiveInterval*>;
  47
  48 public:
  49   // SegmentIter can advance to the next segment ordered by starting position
  50   // which may belong to a different live virtual register. We also must be able
  51   // to reach the current segment's containing virtual register.
  52   using SegmentIter = LiveSegments::iterator;
  53
  54   /// Const version of SegmentIter.
  55   using ConstSegmentIter = LiveSegments::const_iterator;
  56
  57   // LiveIntervalUnions share an external allocator.
  58   using Allocator = LiveSegments::Allocator;
  59
  60 private:
  61   unsigned Tag = 0;       // unique tag for current contents.
  62   LiveSegments Segments;  // union of virtual reg segments
  63
  64 public:
  65   explicit LiveIntervalUnion(Allocator &a) : Segments(a) {}
  66
  67   // Iterate over all segments in the union of live virtual registers ordered
  68   // by their starting position.
  69   SegmentIter begin() { return Segments.begin(); }
  70   SegmentIter end() { return Segments.end(); }
  71   SegmentIter find(SlotIndex x) { return Segments.find(x); }
  72   ConstSegmentIter begin() const { return Segments.begin(); }
  73   ConstSegmentIter end() const { return Segments.end(); }
  74   ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); }
  75
  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   using Map = LiveSegments;
  81   const Map &getMap() const { 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, const LiveRange &Range);
  91
  92   // Remove a live virtual register's segments from this union.
  93   void extract(LiveInterval &VirtReg, const LiveRange &Range);
  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     const LiveIntervalUnion *LiveUnion = nullptr;
 110     const LiveRange *LR = nullptr;
 111     LiveRange::const_iterator LRI;  ///< current position in LR
 112     ConstSegmentIter LiveUnionI;    ///< current position in LiveUnion
 113     SmallVector<LiveInterval*,4> InterferingVRegs;
 114     bool CheckedFirstInterference = false;
 115     bool SeenAllInterferences = false;
 116     unsigned Tag = 0;
 117     unsigned UserTag = 0;
 118
 119     void reset(unsigned NewUserTag, const LiveRange &NewLR,
 120                const LiveIntervalUnion &NewLiveUnion) {
 121       LiveUnion = &NewLiveUnion;
 122       LR = &NewLR;
 123       InterferingVRegs.clear();
 124       CheckedFirstInterference = false;
 125       SeenAllInterferences = false;
 126       Tag = NewLiveUnion.getTag();
 127       UserTag = NewUserTag;
 128     }
 129
 130   public:
 131     Query() = default;
 132     Query(const LiveRange &LR, const LiveIntervalUnion &LIU):
 133       LiveUnion(&LIU), LR(&LR) {}
 134     Query(const Query &) = delete;
 135     Query &operator=(const Query &) = delete;
 136
 137     void init(unsigned NewUserTag, const LiveRange &NewLR,
 138               const LiveIntervalUnion &NewLiveUnion) {
 139       if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion &&
 140           !NewLiveUnion.changedSince(Tag)) {
 141         // Retain cached results, e.g. firstInterference.
 142         return;
 143       }
 144       reset(NewUserTag, NewLR, NewLiveUnion);
 145     }
 146
 147     // Does this live virtual register interfere with the union?
 148     bool checkInterference() { return collectInterferingVRegs(1); }
 149
 150     // Count the virtual registers in this union that interfere with this
 151     // query's live virtual register, up to maxInterferingRegs.
 152     unsigned collectInterferingVRegs(
 153         unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max());
 154
 155     // Was this virtual register visited during collectInterferingVRegs?
 156     bool isSeenInterference(LiveInterval *VirtReg) const;
 157
 158     // Did collectInterferingVRegs collect all interferences?
 159     bool seenAllInterferences() const { return SeenAllInterferences; }
 160
 161     // Vector generated by collectInterferingVRegs.
 162     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
 163       return InterferingVRegs;
 164     }
 165   };
 166
 167   // Array of LiveIntervalUnions.
 168   class Array {
 169     unsigned Size = 0;
 170     LiveIntervalUnion *LIUs = nullptr;
 171
 172   public:
 173     Array() = default;
 174     ~Array() { clear(); }
 175
 176     // Initialize the array to have Size entries.
 177     // Reuse an existing allocation if the size matches.
 178     void init(LiveIntervalUnion::Allocator&, unsigned Size);
 179
 180     unsigned size() const { return Size; }
 181
 182     void clear();
 183
 184     LiveIntervalUnion& operator[](unsigned idx) {
 185       assert(idx <  Size && "idx out of bounds");
 186       return LIUs[idx];
 187     }
 188
 189     const LiveIntervalUnion& operator[](unsigned Idx) const {
 190       assert(Idx < Size && "Idx out of bounds");
 191       return LIUs[Idx];
 192     }
 193   };
 194 };
 195
 196 } // end namespace llvm
 197
 198 #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H