1249259Sdim//===-- LiveIntervalUnion.h - Live interval union data struct --*- C++ -*--===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// LiveIntervalUnion is a union of live segments across multiple live virtual 11249259Sdim// registers. This may be used during coalescing to represent a congruence 12249259Sdim// class, or during register allocation to model liveness of a physical 13249259Sdim// register. 14249259Sdim// 15249259Sdim//===----------------------------------------------------------------------===// 16249259Sdim 17249259Sdim#ifndef LLVM_CODEGEN_LIVEINTERVALUNION_H 18249259Sdim#define LLVM_CODEGEN_LIVEINTERVALUNION_H 19249259Sdim 20249259Sdim#include "llvm/ADT/IntervalMap.h" 21249259Sdim#include "llvm/CodeGen/LiveInterval.h" 22249259Sdim 23249259Sdimnamespace llvm { 24249259Sdim 25249259Sdimclass TargetRegisterInfo; 26249259Sdim 27249259Sdim#ifndef NDEBUG 28249259Sdim// forward declaration 29249259Sdimtemplate <unsigned Element> class SparseBitVector; 30249259Sdimtypedef SparseBitVector<128> LiveVirtRegBitSet; 31249259Sdim#endif 32249259Sdim 33249259Sdim/// Compare a live virtual register segment to a LiveIntervalUnion segment. 34249259Sdiminline bool 35249259Sdimoverlap(const LiveRange &VRSeg, 36249259Sdim const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) { 37249259Sdim return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end; 38249259Sdim} 39249259Sdim 40249259Sdim/// Union of live intervals that are strong candidates for coalescing into a 41249259Sdim/// single register (either physical or virtual depending on the context). We 42249259Sdim/// expect the constituent live intervals to be disjoint, although we may 43249259Sdim/// eventually make exceptions to handle value-based interference. 44249259Sdimclass LiveIntervalUnion { 45249259Sdim // A set of live virtual register segments that supports fast insertion, 46249259Sdim // intersection, and removal. 47249259Sdim // Mapping SlotIndex intervals to virtual register numbers. 48249259Sdim typedef IntervalMap<SlotIndex, LiveInterval*> LiveSegments; 49249259Sdim 50249259Sdimpublic: 51249259Sdim // SegmentIter can advance to the next segment ordered by starting position 52249259Sdim // which may belong to a different live virtual register. We also must be able 53249259Sdim // to reach the current segment's containing virtual register. 54249259Sdim typedef LiveSegments::iterator SegmentIter; 55249259Sdim 56249259Sdim // LiveIntervalUnions share an external allocator. 57249259Sdim typedef LiveSegments::Allocator Allocator; 58249259Sdim 59249259Sdim class Query; 60249259Sdim 61249259Sdimprivate: 62249259Sdim unsigned Tag; // unique tag for current contents. 63249259Sdim LiveSegments Segments; // union of virtual reg segments 64249259Sdim 65249259Sdimpublic: 66249259Sdim explicit LiveIntervalUnion(Allocator &a) : Tag(0), Segments(a) {} 67249259Sdim 68249259Sdim // Iterate over all segments in the union of live virtual registers ordered 69249259Sdim // by their starting position. 70249259Sdim SegmentIter begin() { return Segments.begin(); } 71249259Sdim SegmentIter end() { return Segments.end(); } 72249259Sdim SegmentIter find(SlotIndex x) { return Segments.find(x); } 73249259Sdim bool empty() const { return Segments.empty(); } 74249259Sdim SlotIndex startIndex() const { return Segments.start(); } 75249259Sdim 76249259Sdim // Provide public access to the underlying map to allow overlap iteration. 77249259Sdim typedef LiveSegments Map; 78249259Sdim const Map &getMap() { return Segments; } 79249259Sdim 80249259Sdim /// getTag - Return an opaque tag representing the current state of the union. 81249259Sdim unsigned getTag() const { return Tag; } 82249259Sdim 83249259Sdim /// changedSince - Return true if the union change since getTag returned tag. 84249259Sdim bool changedSince(unsigned tag) const { return tag != Tag; } 85249259Sdim 86249259Sdim // Add a live virtual register to this union and merge its segments. 87249259Sdim void unify(LiveInterval &VirtReg); 88249259Sdim 89249259Sdim // Remove a live virtual register's segments from this union. 90249259Sdim void extract(LiveInterval &VirtReg); 91249259Sdim 92249259Sdim // Remove all inserted virtual registers. 93249259Sdim void clear() { Segments.clear(); ++Tag; } 94249259Sdim 95249259Sdim // Print union, using TRI to translate register names 96249259Sdim void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; 97249259Sdim 98249259Sdim#ifndef NDEBUG 99249259Sdim // Verify the live intervals in this union and add them to the visited set. 100249259Sdim void verify(LiveVirtRegBitSet& VisitedVRegs); 101249259Sdim#endif 102249259Sdim 103249259Sdim /// Query interferences between a single live virtual register and a live 104249259Sdim /// interval union. 105249259Sdim class Query { 106249259Sdim LiveIntervalUnion *LiveUnion; 107249259Sdim LiveInterval *VirtReg; 108249259Sdim LiveInterval::iterator VirtRegI; // current position in VirtReg 109249259Sdim SegmentIter LiveUnionI; // current position in LiveUnion 110249259Sdim SmallVector<LiveInterval*,4> InterferingVRegs; 111249259Sdim bool CheckedFirstInterference; 112249259Sdim bool SeenAllInterferences; 113249259Sdim bool SeenUnspillableVReg; 114249259Sdim unsigned Tag, UserTag; 115249259Sdim 116249259Sdim public: 117249259Sdim Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {} 118249259Sdim 119249259Sdim Query(LiveInterval *VReg, LiveIntervalUnion *LIU): 120249259Sdim LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false), 121249259Sdim SeenAllInterferences(false), SeenUnspillableVReg(false) 122249259Sdim {} 123249259Sdim 124249259Sdim void clear() { 125249259Sdim LiveUnion = NULL; 126249259Sdim VirtReg = NULL; 127249259Sdim InterferingVRegs.clear(); 128249259Sdim CheckedFirstInterference = false; 129249259Sdim SeenAllInterferences = false; 130249259Sdim SeenUnspillableVReg = false; 131249259Sdim Tag = 0; 132249259Sdim UserTag = 0; 133249259Sdim } 134249259Sdim 135249259Sdim void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) { 136249259Sdim assert(VReg && LIU && "Invalid arguments"); 137249259Sdim if (UserTag == UTag && VirtReg == VReg && 138249259Sdim LiveUnion == LIU && !LIU->changedSince(Tag)) { 139249259Sdim // Retain cached results, e.g. firstInterference. 140249259Sdim return; 141249259Sdim } 142249259Sdim clear(); 143249259Sdim LiveUnion = LIU; 144249259Sdim VirtReg = VReg; 145249259Sdim Tag = LIU->getTag(); 146249259Sdim UserTag = UTag; 147249259Sdim } 148249259Sdim 149249259Sdim LiveInterval &virtReg() const { 150249259Sdim assert(VirtReg && "uninitialized"); 151249259Sdim return *VirtReg; 152249259Sdim } 153249259Sdim 154249259Sdim // Does this live virtual register interfere with the union? 155249259Sdim bool checkInterference() { return collectInterferingVRegs(1); } 156249259Sdim 157249259Sdim // Count the virtual registers in this union that interfere with this 158249259Sdim // query's live virtual register, up to maxInterferingRegs. 159249259Sdim unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX); 160249259Sdim 161249259Sdim // Was this virtual register visited during collectInterferingVRegs? 162249259Sdim bool isSeenInterference(LiveInterval *VReg) const; 163249259Sdim 164249259Sdim // Did collectInterferingVRegs collect all interferences? 165249259Sdim bool seenAllInterferences() const { return SeenAllInterferences; } 166249259Sdim 167249259Sdim // Did collectInterferingVRegs encounter an unspillable vreg? 168249259Sdim bool seenUnspillableVReg() const { return SeenUnspillableVReg; } 169249259Sdim 170249259Sdim // Vector generated by collectInterferingVRegs. 171249259Sdim const SmallVectorImpl<LiveInterval*> &interferingVRegs() const { 172249259Sdim return InterferingVRegs; 173249259Sdim } 174249259Sdim 175249259Sdim private: 176249259Sdim Query(const Query&) LLVM_DELETED_FUNCTION; 177249259Sdim void operator=(const Query&) LLVM_DELETED_FUNCTION; 178249259Sdim }; 179249259Sdim 180249259Sdim // Array of LiveIntervalUnions. 181249259Sdim class Array { 182249259Sdim unsigned Size; 183249259Sdim LiveIntervalUnion *LIUs; 184249259Sdim public: 185249259Sdim Array() : Size(0), LIUs(0) {} 186249259Sdim ~Array() { clear(); } 187249259Sdim 188249259Sdim // Initialize the array to have Size entries. 189249259Sdim // Reuse an existing allocation if the size matches. 190249259Sdim void init(LiveIntervalUnion::Allocator&, unsigned Size); 191249259Sdim 192249259Sdim unsigned size() const { return Size; } 193249259Sdim 194249259Sdim void clear(); 195249259Sdim 196249259Sdim LiveIntervalUnion& operator[](unsigned idx) { 197249259Sdim assert(idx < Size && "idx out of bounds"); 198249259Sdim return LIUs[idx]; 199249259Sdim } 200249259Sdim }; 201249259Sdim}; 202249259Sdim 203249259Sdim} // end namespace llvm 204249259Sdim 205249259Sdim#endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION_H) 206