LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - LiveInterval.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 127 193 65.8 %
Date: 2018-10-20 13:21:21 Functions: 17 42 40.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/CodeGen/LiveInterval.h - Interval representation ----*- 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             : // This file implements the LiveRange and LiveInterval classes.  Given some
      11             : // numbering of each the machine instructions an interval [i, j) is said to be a
      12             : // live range for register v if there is no instruction with number j' >= j
      13             : // such that v is live at j' and there is no instruction with number i' < i such
      14             : // that v is live at i'. In this implementation ranges can have holes,
      15             : // i.e. a range might look like [1,20), [50,65), [1000,1001).  Each
      16             : // individual segment is represented as an instance of LiveRange::Segment,
      17             : // and the whole range is represented as an instance of LiveRange.
      18             : //
      19             : //===----------------------------------------------------------------------===//
      20             : 
      21             : #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
      22             : #define LLVM_CODEGEN_LIVEINTERVAL_H
      23             : 
      24             : #include "llvm/ADT/ArrayRef.h"
      25             : #include "llvm/ADT/IntEqClasses.h"
      26             : #include "llvm/ADT/STLExtras.h"
      27             : #include "llvm/ADT/SmallVector.h"
      28             : #include "llvm/ADT/iterator_range.h"
      29             : #include "llvm/CodeGen/SlotIndexes.h"
      30             : #include "llvm/MC/LaneBitmask.h"
      31             : #include "llvm/Support/Allocator.h"
      32             : #include "llvm/Support/MathExtras.h"
      33             : #include <algorithm>
      34             : #include <cassert>
      35             : #include <cstddef>
      36             : #include <functional>
      37             : #include <memory>
      38             : #include <set>
      39             : #include <tuple>
      40             : #include <utility>
      41             : 
      42             : namespace llvm {
      43             : 
      44             :   class CoalescerPair;
      45             :   class LiveIntervals;
      46             :   class MachineRegisterInfo;
      47             :   class raw_ostream;
      48             : 
      49             :   /// VNInfo - Value Number Information.
      50             :   /// This class holds information about a machine level values, including
      51             :   /// definition and use points.
      52             :   ///
      53             :   class VNInfo {
      54             :   public:
      55             :     using Allocator = BumpPtrAllocator;
      56             : 
      57             :     /// The ID number of this value.
      58             :     unsigned id;
      59             : 
      60             :     /// The index of the defining instruction.
      61             :     SlotIndex def;
      62             : 
      63             :     /// VNInfo constructor.
      64     6088826 :     VNInfo(unsigned i, SlotIndex d) : id(i), def(d) {}
      65             : 
      66             :     /// VNInfo constructor, copies values from orig, except for the value number.
      67           0 :     VNInfo(unsigned i, const VNInfo &orig) : id(i), def(orig.def) {}
      68             : 
      69             :     /// Copy from the parameter into this VNInfo.
      70           0 :     void copyFrom(VNInfo &src) {
      71           4 :       def = src.def;
      72           0 :     }
      73             : 
      74             :     /// Returns true if this value is defined by a PHI instruction (or was,
      75             :     /// PHI instructions may have been eliminated).
      76             :     /// PHI-defs begin at a block boundary, all other defs begin at register or
      77             :     /// EC slots.
      78             :     bool isPHIDef() const { return def.isBlock(); }
      79             : 
      80             :     /// Returns true if this value is unused.
      81             :     bool isUnused() const { return !def.isValid(); }
      82             : 
      83             :     /// Mark this value as unused.
      84        9898 :     void markUnused() { def = SlotIndex(); }
      85             :   };
      86             : 
      87             :   /// Result of a LiveRange query. This class hides the implementation details
      88             :   /// of live ranges, and it should be used as the primary interface for
      89             :   /// examining live ranges around instructions.
      90             :   class LiveQueryResult {
      91             :     VNInfo *const EarlyVal;
      92             :     VNInfo *const LateVal;
      93             :     const SlotIndex EndPoint;
      94             :     const bool Kill;
      95             : 
      96             :   public:
      97             :     LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint,
      98             :                     bool Kill)
      99     1442878 :       : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill)
     100             :     {}
     101             : 
     102             :     /// Return the value that is live-in to the instruction. This is the value
     103             :     /// that will be read by the instruction's use operands. Return NULL if no
     104             :     /// value is live-in.
     105           0 :     VNInfo *valueIn() const {
     106           0 :       return EarlyVal;
     107             :     }
     108             : 
     109             :     /// Return true if the live-in value is killed by this instruction. This
     110             :     /// means that either the live range ends at the instruction, or it changes
     111             :     /// value.
     112           0 :     bool isKill() const {
     113           0 :       return Kill;
     114             :     }
     115             : 
     116             :     /// Return true if this instruction has a dead def.
     117             :     bool isDeadDef() const {
     118             :       return EndPoint.isDead();
     119             :     }
     120             : 
     121             :     /// Return the value leaving the instruction, if any. This can be a
     122             :     /// live-through value, or a live def. A dead def returns NULL.
     123             :     VNInfo *valueOut() const {
     124          16 :       return isDeadDef() ? nullptr : LateVal;
     125             :     }
     126             : 
     127             :     /// Returns the value alive at the end of the instruction, if any. This can
     128             :     /// be a live-through value, a live def or a dead def.
     129           0 :     VNInfo *valueOutOrDead() const {
     130           0 :       return LateVal;
     131             :     }
     132             : 
     133             :     /// Return the value defined by this instruction, if any. This includes
     134             :     /// dead defs, it is the value created by the instruction's def operands.
     135           0 :     VNInfo *valueDefined() const {
     136     5480087 :       return EarlyVal == LateVal ? nullptr : LateVal;
     137             :     }
     138             : 
     139             :     /// Return the end point of the last live range segment to interact with
     140             :     /// the instruction, if any.
     141             :     ///
     142             :     /// The end point is an invalid SlotIndex only if the live range doesn't
     143             :     /// intersect the instruction at all.
     144             :     ///
     145             :     /// The end point may be at or past the end of the instruction's basic
     146             :     /// block. That means the value was live out of the block.
     147           0 :     SlotIndex endPoint() const {
     148           0 :       return EndPoint;
     149             :     }
     150             :   };
     151             : 
     152             :   /// This class represents the liveness of a register, stack slot, etc.
     153             :   /// It manages an ordered list of Segment objects.
     154             :   /// The Segments are organized in a static single assignment form: At places
     155             :   /// where a new value is defined or different values reach a CFG join a new
     156             :   /// segment with a new value number is used.
     157             :   class LiveRange {
     158             :   public:
     159             :     /// This represents a simple continuous liveness interval for a value.
     160             :     /// The start point is inclusive, the end point exclusive. These intervals
     161             :     /// are rendered as [start,end).
     162             :     struct Segment {
     163             :       SlotIndex start;  // Start point of the interval (inclusive)
     164             :       SlotIndex end;    // End point of the interval (exclusive)
     165             :       VNInfo *valno = nullptr; // identifier for the value contained in this
     166             :                                // segment.
     167             : 
     168             :       Segment() = default;
     169             : 
     170             :       Segment(SlotIndex S, SlotIndex E, VNInfo *V)
     171     8650495 :         : start(S), end(E), valno(V) {
     172             :         assert(S < E && "Cannot create empty or backwards segment");
     173             :       }
     174             : 
     175             :       /// Return true if the index is covered by this segment.
     176    11055385 :       bool contains(SlotIndex I) const {
     177    11055385 :         return start <= I && I < end;
     178             :       }
     179             : 
     180             :       /// Return true if the given interval, [S, E), is covered by this segment.
     181             :       bool containsInterval(SlotIndex S, SlotIndex E) const {
     182             :         assert((S < E) && "Backwards interval?");
     183             :         return (start <= S && S < end) && (start < E && E <= end);
     184             :       }
     185             : 
     186             :       bool operator<(const Segment &Other) const {
     187     8322944 :         return std::tie(start, end) < std::tie(Other.start, Other.end);
     188             :       }
     189             :       bool operator==(const Segment &Other) const {
     190             :         return start == Other.start && end == Other.end;
     191             :       }
     192             : 
     193             :       void dump() const;
     194             :     };
     195             : 
     196             :     using Segments = SmallVector<Segment, 2>;
     197             :     using VNInfoList = SmallVector<VNInfo *, 2>;
     198             : 
     199             :     Segments segments;   // the liveness segments
     200             :     VNInfoList valnos;   // value#'s
     201             : 
     202             :     // The segment set is used temporarily to accelerate initial computation
     203             :     // of live ranges of physical registers in computeRegUnitRange.
     204             :     // After that the set is flushed to the segment vector and deleted.
     205             :     using SegmentSet = std::set<Segment>;
     206             :     std::unique_ptr<SegmentSet> segmentSet;
     207             : 
     208             :     using iterator = Segments::iterator;
     209             :     using const_iterator = Segments::const_iterator;
     210             : 
     211             :     iterator begin() { return segments.begin(); }
     212             :     iterator end()   { return segments.end(); }
     213             : 
     214             :     const_iterator begin() const { return segments.begin(); }
     215             :     const_iterator end() const  { return segments.end(); }
     216             : 
     217             :     using vni_iterator = VNInfoList::iterator;
     218             :     using const_vni_iterator = VNInfoList::const_iterator;
     219             : 
     220             :     vni_iterator vni_begin() { return valnos.begin(); }
     221             :     vni_iterator vni_end()   { return valnos.end(); }
     222             : 
     223             :     const_vni_iterator vni_begin() const { return valnos.begin(); }
     224             :     const_vni_iterator vni_end() const   { return valnos.end(); }
     225             : 
     226             :     /// Constructs a new LiveRange object.
     227     4451327 :     LiveRange(bool UseSegmentSet = false)
     228     4451327 :         : segmentSet(UseSegmentSet ? llvm::make_unique<SegmentSet>()
     229     4451327 :                                    : nullptr) {}
     230             : 
     231             :     /// Constructs a new LiveRange object by copying segments and valnos from
     232             :     /// another LiveRange.
     233      189974 :     LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) {
     234             :       assert(Other.segmentSet == nullptr &&
     235             :              "Copying of LiveRanges with active SegmentSets is not supported");
     236      189974 :       assign(Other, Allocator);
     237             :     }
     238             : 
     239             :     /// Copies values numbers and live segments from \p Other into this range.
     240      389621 :     void assign(const LiveRange &Other, BumpPtrAllocator &Allocator) {
     241      389621 :       if (this == &Other)
     242             :         return;
     243             : 
     244             :       assert(Other.segmentSet == nullptr &&
     245             :              "Copying of LiveRanges with active SegmentSets is not supported");
     246             :       // Duplicate valnos.
     247      808914 :       for (const VNInfo *VNI : Other.valnos)
     248      419293 :         createValueCopy(VNI, Allocator);
     249             :       // Now we can copy segments and remap their valnos.
     250      834121 :       for (const Segment &S : Other.segments)
     251      889000 :         segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
     252             :     }
     253             : 
     254             :     /// advanceTo - Advance the specified iterator to point to the Segment
     255             :     /// containing the specified position, or end() if the position is past the
     256             :     /// end of the range.  If no Segment contains this position, but the
     257             :     /// position is in a hole, this method returns an iterator pointing to the
     258             :     /// Segment immediately after the hole.
     259     1958541 :     iterator advanceTo(iterator I, SlotIndex Pos) {
     260             :       assert(I != end());
     261     1958541 :       if (Pos >= endIndex())
     262      521583 :         return end();
     263     5041245 :       while (I->end <= Pos) ++I;
     264             :       return I;
     265             :     }
     266             : 
     267    18690634 :     const_iterator advanceTo(const_iterator I, SlotIndex Pos) const {
     268             :       assert(I != end());
     269    18690634 :       if (Pos >= endIndex())
     270     1237497 :         return end();
     271    23278112 :       while (I->end <= Pos) ++I;
     272             :       return I;
     273             :     }
     274             : 
     275             :     /// find - Return an iterator pointing to the first segment that ends after
     276             :     /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster
     277             :     /// when searching large ranges.
     278             :     ///
     279             :     /// If Pos is contained in a Segment, that segment is returned.
     280             :     /// If Pos is in a hole, the following Segment is returned.
     281             :     /// If Pos is beyond endIndex, end() is returned.
     282             :     iterator find(SlotIndex Pos);
     283             : 
     284             :     const_iterator find(SlotIndex Pos) const {
     285    34521282 :       return const_cast<LiveRange*>(this)->find(Pos);
     286             :     }
     287             : 
     288             :     void clear() {
     289             :       valnos.clear();
     290             :       segments.clear();
     291             :     }
     292             : 
     293             :     size_t size() const {
     294      628487 :       return segments.size();
     295             :     }
     296             : 
     297          54 :     bool hasAtLeastOneValue() const { return !valnos.empty(); }
     298             : 
     299           0 :     bool containsOneValue() const { return valnos.size() == 1; }
     300             : 
     301    17445520 :     unsigned getNumValNums() const { return (unsigned)valnos.size(); }
     302             : 
     303             :     /// getValNumInfo - Returns pointer to the specified val#.
     304             :     ///
     305             :     inline VNInfo *getValNumInfo(unsigned ValNo) {
     306    31615639 :       return valnos[ValNo];
     307             :     }
     308             :     inline const VNInfo *getValNumInfo(unsigned ValNo) const {
     309     7951700 :       return valnos[ValNo];
     310             :     }
     311             : 
     312             :     /// containsValue - Returns true if VNI belongs to this range.
     313             :     bool containsValue(const VNInfo *VNI) const {
     314             :       return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id);
     315             :     }
     316             : 
     317             :     /// getNextValue - Create a new value number and return it.  MIIdx specifies
     318             :     /// the instruction that defines the value number.
     319     6074870 :     VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) {
     320             :       VNInfo *VNI =
     321     6074870 :         new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def);
     322     6074870 :       valnos.push_back(VNI);
     323     6074870 :       return VNI;
     324             :     }
     325             : 
     326             :     /// createDeadDef - Make sure the range has a value defined at Def.
     327             :     /// If one already exists, return it. Otherwise allocate a new value and
     328             :     /// add liveness for a dead def.
     329             :     VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc);
     330             : 
     331             :     /// Create a def of value @p VNI. Return @p VNI. If there already exists
     332             :     /// a definition at VNI->def, the value defined there must be @p VNI.
     333             :     VNInfo *createDeadDef(VNInfo *VNI);
     334             : 
     335             :     /// Create a copy of the given value. The new value will be identical except
     336             :     /// for the Value number.
     337           0 :     VNInfo *createValueCopy(const VNInfo *orig,
     338             :                             VNInfo::Allocator &VNInfoAllocator) {
     339             :       VNInfo *VNI =
     340           0 :         new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
     341           0 :       valnos.push_back(VNI);
     342           0 :       return VNI;
     343             :     }
     344             : 
     345             :     /// RenumberValues - Renumber all values in order of appearance and remove
     346             :     /// unused values.
     347             :     void RenumberValues();
     348             : 
     349             :     /// MergeValueNumberInto - This method is called when two value numbers
     350             :     /// are found to be equivalent.  This eliminates V1, replacing all
     351             :     /// segments with the V1 value number with the V2 value number.  This can
     352             :     /// cause merging of V1/V2 values numbers and compaction of the value space.
     353             :     VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
     354             : 
     355             :     /// Merge all of the live segments of a specific val# in RHS into this live
     356             :     /// range as the specified value number. The segments in RHS are allowed
     357             :     /// to overlap with segments in the current range, it will replace the
     358             :     /// value numbers of the overlaped live segments with the specified value
     359             :     /// number.
     360             :     void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo);
     361             : 
     362             :     /// MergeValueInAsValue - Merge all of the segments of a specific val#
     363             :     /// in RHS into this live range as the specified value number.
     364             :     /// The segments in RHS are allowed to overlap with segments in the
     365             :     /// current range, but only if the overlapping segments have the
     366             :     /// specified value number.
     367             :     void MergeValueInAsValue(const LiveRange &RHS,
     368             :                              const VNInfo *RHSValNo, VNInfo *LHSValNo);
     369             : 
     370   143896074 :     bool empty() const { return segments.empty(); }
     371             : 
     372             :     /// beginIndex - Return the lowest numbered slot covered.
     373             :     SlotIndex beginIndex() const {
     374             :       assert(!empty() && "Call to beginIndex() on empty range.");
     375    10693499 :       return segments.front().start;
     376             :     }
     377             : 
     378             :     /// endNumber - return the maximum point of the range of the whole,
     379             :     /// exclusive.
     380             :     SlotIndex endIndex() const {
     381             :       assert(!empty() && "Call to endIndex() on empty range.");
     382   105897788 :       return segments.back().end;
     383             :     }
     384             : 
     385             :     bool expiredAt(SlotIndex index) const {
     386             :       return index >= endIndex();
     387             :     }
     388             : 
     389    32296289 :     bool liveAt(SlotIndex index) const {
     390    32296289 :       const_iterator r = find(index);
     391    32296289 :       return r != end() && r->start <= index;
     392             :     }
     393             : 
     394             :     /// Return the segment that contains the specified index, or null if there
     395             :     /// is none.
     396             :     const Segment *getSegmentContaining(SlotIndex Idx) const {
     397             :       const_iterator I = FindSegmentContaining(Idx);
     398             :       return I == end() ? nullptr : &*I;
     399             :     }
     400             : 
     401             :     /// Return the live segment that contains the specified index, or null if
     402             :     /// there is none.
     403             :     Segment *getSegmentContaining(SlotIndex Idx) {
     404       66786 :       iterator I = FindSegmentContaining(Idx);
     405       66786 :       return I == end() ? nullptr : &*I;
     406             :     }
     407             : 
     408             :     /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
     409             :     VNInfo *getVNInfoAt(SlotIndex Idx) const {
     410     7961376 :       const_iterator I = FindSegmentContaining(Idx);
     411     7961376 :       return I == end() ? nullptr : I->valno;
     412             :     }
     413             : 
     414             :     /// getVNInfoBefore - Return the VNInfo that is live up to but not
     415             :     /// necessarilly including Idx, or NULL. Use this to find the reaching def
     416             :     /// used by an instruction at this SlotIndex position.
     417     3061636 :     VNInfo *getVNInfoBefore(SlotIndex Idx) const {
     418     3061636 :       const_iterator I = FindSegmentContaining(Idx.getPrevSlot());
     419     3061636 :       return I == end() ? nullptr : I->valno;
     420             :     }
     421             : 
     422             :     /// Return an iterator to the segment that contains the specified index, or
     423             :     /// end() if there is none.
     424     3625322 :     iterator FindSegmentContaining(SlotIndex Idx) {
     425     3625322 :       iterator I = find(Idx);
     426     3625322 :       return I != end() && I->start <= Idx ? I : end();
     427             :     }
     428             : 
     429    15030684 :     const_iterator FindSegmentContaining(SlotIndex Idx) const {
     430    15030684 :       const_iterator I = find(Idx);
     431    15030684 :       return I != end() && I->start <= Idx ? I : end();
     432             :     }
     433             : 
     434             :     /// overlaps - Return true if the intersection of the two live ranges is
     435             :     /// not empty.
     436             :     bool overlaps(const LiveRange &other) const {
     437      519135 :       if (other.empty())
     438             :         return false;
     439      514916 :       return overlapsFrom(other, other.begin());
     440             :     }
     441             : 
     442             :     /// overlaps - Return true if the two ranges have overlapping segments
     443             :     /// that are not coalescable according to CP.
     444             :     ///
     445             :     /// Overlapping segments where one range is defined by a coalescable
     446             :     /// copy are allowed.
     447             :     bool overlaps(const LiveRange &Other, const CoalescerPair &CP,
     448             :                   const SlotIndexes&) const;
     449             : 
     450             :     /// overlaps - Return true if the live range overlaps an interval specified
     451             :     /// by [Start, End).
     452             :     bool overlaps(SlotIndex Start, SlotIndex End) const;
     453             : 
     454             :     /// overlapsFrom - Return true if the intersection of the two live ranges
     455             :     /// is not empty.  The specified iterator is a hint that we can begin
     456             :     /// scanning the Other range starting at I.
     457             :     bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const;
     458             : 
     459             :     /// Returns true if all segments of the @p Other live range are completely
     460             :     /// covered by this live range.
     461             :     /// Adjacent live ranges do not affect the covering:the liverange
     462             :     /// [1,5](5,10] covers (3,7].
     463             :     bool covers(const LiveRange &Other) const;
     464             : 
     465             :     /// Add the specified Segment to this range, merging segments as
     466             :     /// appropriate.  This returns an iterator to the inserted segment (which
     467             :     /// may have grown since it was inserted).
     468             :     iterator addSegment(Segment S);
     469             : 
     470             :     /// Attempt to extend a value defined after @p StartIdx to include @p Use.
     471             :     /// Both @p StartIdx and @p Use should be in the same basic block. In case
     472             :     /// of subranges, an extension could be prevented by an explicit "undef"
     473             :     /// caused by a <def,read-undef> on a non-overlapping lane. The list of
     474             :     /// location of such "undefs" should be provided in @p Undefs.
     475             :     /// The return value is a pair: the first element is VNInfo of the value
     476             :     /// that was extended (possibly nullptr), the second is a boolean value
     477             :     /// indicating whether an "undef" was encountered.
     478             :     /// If this range is live before @p Use in the basic block that starts at
     479             :     /// @p StartIdx, and there is no intervening "undef", extend it to be live
     480             :     /// up to @p Use, and return the pair {value, false}. If there is no
     481             :     /// segment before @p Use and there is no "undef" between @p StartIdx and
     482             :     /// @p Use, return {nullptr, false}. If there is an "undef" before @p Use,
     483             :     /// return {nullptr, true}.
     484             :     std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
     485             :         SlotIndex StartIdx, SlotIndex Kill);
     486             : 
     487             :     /// Simplified version of the above "extendInBlock", which assumes that
     488             :     /// no register lanes are undefined by <def,read-undef> operands.
     489             :     /// If this range is live before @p Use in the basic block that starts
     490             :     /// at @p StartIdx, extend it to be live up to @p Use, and return the
     491             :     /// value. If there is no segment before @p Use, return nullptr.
     492             :     VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);
     493             : 
     494             :     /// join - Join two live ranges (this, and other) together.  This applies
     495             :     /// mappings to the value numbers in the LHS/RHS ranges as specified.  If
     496             :     /// the ranges are not joinable, this aborts.
     497             :     void join(LiveRange &Other,
     498             :               const int *ValNoAssignments,
     499             :               const int *RHSValNoAssignments,
     500             :               SmallVectorImpl<VNInfo *> &NewVNInfo);
     501             : 
     502             :     /// True iff this segment is a single segment that lies between the
     503             :     /// specified boundaries, exclusively. Vregs live across a backedge are not
     504             :     /// considered local. The boundaries are expected to lie within an extended
     505             :     /// basic block, so vregs that are not live out should contain no holes.
     506       61391 :     bool isLocal(SlotIndex Start, SlotIndex End) const {
     507       61391 :       return beginIndex() > Start.getBaseIndex() &&
     508       61391 :         endIndex() < End.getBoundaryIndex();
     509             :     }
     510             : 
     511             :     /// Remove the specified segment from this range.  Note that the segment
     512             :     /// must be a single Segment in its entirety.
     513             :     void removeSegment(SlotIndex Start, SlotIndex End,
     514             :                        bool RemoveDeadValNo = false);
     515             : 
     516             :     void removeSegment(Segment S, bool RemoveDeadValNo = false) {
     517         445 :       removeSegment(S.start, S.end, RemoveDeadValNo);
     518             :     }
     519             : 
     520             :     /// Remove segment pointed to by iterator @p I from this range.  This does
     521             :     /// not remove dead value numbers.
     522             :     iterator removeSegment(iterator I) {
     523             :       return segments.erase(I);
     524             :     }
     525             : 
     526             :     /// Query Liveness at Idx.
     527             :     /// The sub-instruction slot of Idx doesn't matter, only the instruction
     528             :     /// it refers to is considered.
     529    17680264 :     LiveQueryResult Query(SlotIndex Idx) const {
     530             :       // Find the segment that enters the instruction.
     531    17680264 :       const_iterator I = find(Idx.getBaseIndex());
     532             :       const_iterator E = end();
     533    17680264 :       if (I == E)
     534             :         return LiveQueryResult(nullptr, nullptr, SlotIndex(), false);
     535             : 
     536             :       // Is this an instruction live-in segment?
     537             :       // If Idx is the start index of a basic block, include live-in segments
     538             :       // that start at Idx.getBaseIndex().
     539             :       VNInfo *EarlyVal = nullptr;
     540             :       VNInfo *LateVal  = nullptr;
     541             :       SlotIndex EndPoint;
     542             :       bool Kill = false;
     543    16237386 :       if (I->start <= Idx.getBaseIndex()) {
     544    12578697 :         EarlyVal = I->valno;
     545    12578697 :         EndPoint = I->end;
     546             :         // Move to the potentially live-out segment.
     547    12578697 :         if (SlotIndex::isSameInstr(Idx, I->end)) {
     548             :           Kill = true;
     549     8536086 :           if (++I == E)
     550     6362835 :             return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
     551             :         }
     552             :         // Special case: A PHIDef value can have its def in the middle of a
     553             :         // segment if the value happens to be live out of the layout
     554             :         // predecessor.
     555             :         // Such a value is not live-in.
     556     6215862 :         if (EarlyVal->def == Idx.getBaseIndex())
     557             :           EarlyVal = nullptr;
     558             :       }
     559             :       // I now points to the segment that may be live-through, or defined by
     560             :       // this instr. Ignore segments starting after the current instr.
     561     9874551 :       if (!SlotIndex::isEarlierInstr(Idx, I->start)) {
     562     6891008 :         LateVal = I->valno;
     563     6891008 :         EndPoint = I->end;
     564             :       }
     565     9874551 :       return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
     566             :     }
     567             : 
     568             :     /// removeValNo - Remove all the segments defined by the specified value#.
     569             :     /// Also remove the value# from value# list.
     570             :     void removeValNo(VNInfo *ValNo);
     571             : 
     572             :     /// Returns true if the live range is zero length, i.e. no live segments
     573             :     /// span instructions. It doesn't pay to spill such a range.
     574     1473232 :     bool isZeroLength(SlotIndexes *Indexes) const {
     575     2245152 :       for (const Segment &S : segments)
     576     1656763 :         if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() <
     577             :             S.end.getBaseIndex())
     578             :           return false;
     579             :       return true;
     580             :     }
     581             : 
     582             :     // Returns true if any segment in the live range contains any of the
     583             :     // provided slot indexes.  Slots which occur in holes between
     584             :     // segments will not cause the function to return true.
     585             :     bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const;
     586             : 
     587             :     bool operator<(const LiveRange& other) const {
     588             :       const SlotIndex &thisIndex = beginIndex();
     589             :       const SlotIndex &otherIndex = other.beginIndex();
     590             :       return thisIndex < otherIndex;
     591             :     }
     592             : 
     593             :     /// Returns true if there is an explicit "undef" between @p Begin
     594             :     /// @p End.
     595           0 :     bool isUndefIn(ArrayRef<SlotIndex> Undefs, SlotIndex Begin,
     596             :                    SlotIndex End) const {
     597           0 :       return std::any_of(Undefs.begin(), Undefs.end(),
     598             :                 [Begin,End] (SlotIndex Idx) -> bool {
     599             :                   return Begin <= Idx && Idx < End;
     600           0 :                 });
     601             :     }
     602             : 
     603             :     /// Flush segment set into the regular segment vector.
     604             :     /// The method is to be called after the live range
     605             :     /// has been created, if use of the segment set was
     606             :     /// activated in the constructor of the live range.
     607             :     void flushSegmentSet();
     608             : 
     609             :     void print(raw_ostream &OS) const;
     610             :     void dump() const;
     611             : 
     612             :     /// Walk the range and assert if any invariants fail to hold.
     613             :     ///
     614             :     /// Note that this is a no-op when asserts are disabled.
     615             : #ifdef NDEBUG
     616           0 :     void verify() const {}
     617             : #else
     618             :     void verify() const;
     619             : #endif
     620             : 
     621             :   protected:
     622             :     /// Append a segment to the list of segments.
     623             :     void append(const LiveRange::Segment S);
     624             : 
     625             :   private:
     626             :     friend class LiveRangeUpdater;
     627             :     void addSegmentToSet(Segment S);
     628             :     void markValNoForDeletion(VNInfo *V);
     629             :   };
     630             : 
     631             :   inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
     632           4 :     LR.print(OS);
     633             :     return OS;
     634             :   }
     635             : 
     636             :   /// LiveInterval - This class represents the liveness of a register,
     637             :   /// or stack slot.
     638             :   class LiveInterval : public LiveRange {
     639             :   public:
     640             :     using super = LiveRange;
     641             : 
     642             :     /// A live range for subregisters. The LaneMask specifies which parts of the
     643             :     /// super register are covered by the interval.
     644             :     /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()).
     645      343282 :     class SubRange : public LiveRange {
     646             :     public:
     647             :       SubRange *Next = nullptr;
     648             :       LaneBitmask LaneMask;
     649             : 
     650             :       /// Constructs a new SubRange object.
     651      153312 :       SubRange(LaneBitmask LaneMask) : LaneMask(LaneMask) {}
     652             : 
     653             :       /// Constructs a new SubRange object by copying liveness from @p Other.
     654             :       SubRange(LaneBitmask LaneMask, const LiveRange &Other,
     655             :                BumpPtrAllocator &Allocator)
     656      189974 :         : LiveRange(Other, Allocator), LaneMask(LaneMask) {}
     657             : 
     658             :       void print(raw_ostream &OS) const;
     659             :       void dump() const;
     660             :     };
     661             : 
     662             :   private:
     663             :     SubRange *SubRanges = nullptr; ///< Single linked list of subregister live
     664             :                                    /// ranges.
     665             : 
     666             :   public:
     667             :     const unsigned reg;  // the register or stack slot of this interval.
     668             :     float weight;        // weight of this interval
     669             : 
     670     2887712 :     LiveInterval(unsigned Reg, float Weight) : reg(Reg), weight(Weight) {}
     671             : 
     672     2866773 :     ~LiveInterval() {
     673     2866773 :       clearSubRanges();
     674             :     }
     675             : 
     676             :     template<typename T>
     677             :     class SingleLinkedListIterator {
     678             :       T *P;
     679             : 
     680             :     public:
     681             :       SingleLinkedListIterator<T>(T *P) : P(P) {}
     682             : 
     683             :       SingleLinkedListIterator<T> &operator++() {
     684    35303608 :         P = P->Next;
     685             :         return *this;
     686             :       }
     687             :       SingleLinkedListIterator<T> operator++(int) {
     688             :         SingleLinkedListIterator res = *this;
     689             :         ++*this;
     690             :         return res;
     691             :       }
     692           0 :       bool operator!=(const SingleLinkedListIterator<T> &Other) {
     693           0 :         return P != Other.operator->();
     694             :       }
     695           0 :       bool operator==(const SingleLinkedListIterator<T> &Other) {
     696           0 :         return P == Other.operator->();
     697             :       }
     698           0 :       T &operator*() const {
     699           0 :         return *P;
     700             :       }
     701           0 :       T *operator->() const {
     702           0 :         return P;
     703             :       }
     704           0 :     };
     705           0 : 
     706             :     using subrange_iterator = SingleLinkedListIterator<SubRange>;
     707           0 :     using const_subrange_iterator = SingleLinkedListIterator<const SubRange>;
     708           0 : 
     709           0 :     subrange_iterator subrange_begin() {
     710           0 :       return subrange_iterator(SubRanges);
     711           0 :     }
     712           0 :     subrange_iterator subrange_end() {
     713           0 :       return subrange_iterator(nullptr);
     714           0 :     }
     715             : 
     716           0 :     const_subrange_iterator subrange_begin() const {
     717           0 :       return const_subrange_iterator(SubRanges);
     718             :     }
     719           0 :     const_subrange_iterator subrange_end() const {
     720           0 :       return const_subrange_iterator(nullptr);
     721             :     }
     722             : 
     723             :     iterator_range<subrange_iterator> subranges() {
     724     3982794 :       return make_range(subrange_begin(), subrange_end());
     725             :     }
     726             : 
     727           0 :     iterator_range<const_subrange_iterator> subranges() const {
     728     3187643 :       return make_range(subrange_begin(), subrange_end());
     729             :     }
     730           0 : 
     731           0 :     /// Creates a new empty subregister live range. The range is added at the
     732             :     /// beginning of the subrange list; subrange iterators stay valid.
     733             :     SubRange *createSubRange(BumpPtrAllocator &Allocator,
     734           0 :                              LaneBitmask LaneMask) {
     735           0 :       SubRange *Range = new (Allocator) SubRange(LaneMask);
     736             :       appendSubRange(Range);
     737           0 :       return Range;
     738           0 :     }
     739             : 
     740             :     /// Like createSubRange() but the new range is filled with a copy of the
     741             :     /// liveness information in @p CopyFrom.
     742     1182572 :     SubRange *createSubRangeFrom(BumpPtrAllocator &Allocator,
     743             :                                  LaneBitmask LaneMask,
     744             :                                  const LiveRange &CopyFrom) {
     745       64229 :       SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator);
     746      267890 :       appendSubRange(Range);
     747       64229 :       return Range;
     748             :     }
     749             : 
     750             :     /// Returns true if subregister liveness information is available.
     751      153312 :     bool hasSubRanges() const {
     752      108744 :       return SubRanges != nullptr;
     753      153312 :     }
     754             : 
     755      153312 :     /// Removes all subregister liveness information.
     756             :     void clearSubRanges();
     757             : 
     758             :     /// Removes all subranges without any segments (subranges without segments
     759             :     /// are not considered valid and should only exist temporarily).
     760      125745 :     void removeEmptySubRanges();
     761             : 
     762             :     /// getSize - Returns the sum of sizes of all the LiveRange's.
     763      125745 :     ///
     764             :     unsigned getSize() const;
     765      125745 : 
     766             :     /// isSpillable - Can this interval be spilled?
     767           0 :     bool isSpillable() const {
     768     2347894 :       return weight != huge_valf;
     769           0 :     }
     770           0 : 
     771             :     /// markNotSpillable - Mark interval as not spillable
     772           0 :     void markNotSpillable() {
     773      588383 :       weight = huge_valf;
     774           0 :     }
     775             : 
     776             :     /// For a given lane mask @p LaneMask, compute indexes at which the
     777             :     /// lane is marked undefined by subregister <def,read-undef> definitions.
     778             :     void computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs,
     779             :                                LaneBitmask LaneMask,
     780             :                                const MachineRegisterInfo &MRI,
     781             :                                const SlotIndexes &Indexes) const;
     782             : 
     783             :     /// Refines the subranges to support \p LaneMask. This may only be called
     784             :     /// for LI.hasSubrange()==true. Subregister ranges are split or created
     785           0 :     /// until \p LaneMask can be matched exactly. \p Mod is executed on the
     786      108206 :     /// matching subranges.
     787             :     ///
     788             :     /// Example:
     789             :     ///    Given an interval with subranges with lanemasks L0F00, L00F0 and
     790           0 :     ///    L000F, refining for mask L0018. Will split the L00F0 lane into
     791           2 :     ///    L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod
     792           0 :     ///    function will be applied to the L0010 and L0008 subranges.
     793             :     void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
     794             :                          std::function<void(LiveInterval::SubRange&)> Apply);
     795             : 
     796       10162 :     bool operator<(const LiveInterval& other) const {
     797       10162 :       const SlotIndex &thisIndex = beginIndex();
     798       10162 :       const SlotIndex &otherIndex = other.beginIndex();
     799       30486 :       return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg);
     800             :     }
     801             : 
     802             :     void print(raw_ostream &OS) const;
     803             :     void dump() const;
     804             : 
     805             :     /// Walks the interval and assert if any invariants fail to hold.
     806             :     ///
     807             :     /// Note that this is a no-op when asserts are disabled.
     808             : #ifdef NDEBUG
     809           0 :     void verify(const MachineRegisterInfo *MRI = nullptr) const {}
     810             : #else
     811             :     void verify(const MachineRegisterInfo *MRI = nullptr) const;
     812             : #endif
     813             : 
     814             :   private:
     815             :     /// Appends @p Range to SubRanges list.
     816           0 :     void appendSubRange(SubRange *Range) {
     817       64229 :       Range->Next = SubRanges;
     818       64229 :       SubRanges = Range;
     819           0 :     }
     820             : 
     821             :     /// Free memory held by SubRange.
     822             :     void freeSubRange(SubRange *S);
     823             :   };
     824             : 
     825             :   inline raw_ostream &operator<<(raw_ostream &OS,
     826             :                                  const LiveInterval::SubRange &SR) {
     827             :     SR.print(OS);
     828             :     return OS;
     829             :   }
     830             : 
     831             :   inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
     832           0 :     LI.print(OS);
     833             :     return OS;
     834           0 :   }
     835      279057 : 
     836      279057 :   raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S);
     837           0 : 
     838             :   inline bool operator<(SlotIndex V, const LiveRange::Segment &S) {
     839             :     return V < S.start;
     840             :   }
     841             : 
     842             :   inline bool operator<(const LiveRange::Segment &S, SlotIndex V) {
     843             :     return S.start < V;
     844             :   }
     845           4 : 
     846             :   /// Helper class for performant LiveRange bulk updates.
     847             :   ///
     848             :   /// Calling LiveRange::addSegment() repeatedly can be expensive on large
     849             :   /// live ranges because segments after the insertion point may need to be
     850           6 :   /// shifted. The LiveRangeUpdater class can defer the shifting when adding
     851             :   /// many segments in order.
     852             :   ///
     853             :   /// The LiveRange will be in an invalid state until flush() is called.
     854             :   class LiveRangeUpdater {
     855             :     LiveRange *LR;
     856             :     SlotIndex LastStart;
     857             :     LiveRange::iterator WriteI;
     858             :     LiveRange::iterator ReadI;
     859             :     SmallVector<LiveRange::Segment, 16> Spills;
     860             :     void mergeSpills();
     861             : 
     862             :   public:
     863             :     /// Create a LiveRangeUpdater for adding segments to LR.
     864             :     /// LR will temporarily be in an invalid state until flush() is called.
     865      441227 :     LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {}
     866             : 
     867      441227 :     ~LiveRangeUpdater() { flush(); }
     868             : 
     869             :     /// Add a segment to LR and coalesce when possible, just like
     870             :     /// LR.addSegment(). Segments should be added in increasing start order for
     871             :     /// best performance.
     872             :     void add(LiveRange::Segment);
     873             : 
     874             :     void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) {
     875     1741503 :       add(LiveRange::Segment(Start, End, VNI));
     876             :     }
     877             : 
     878             :     /// Return true if the LR is currently in an invalid state, and flush()
     879             :     /// needs to be called.
     880             :     bool isDirty() const { return LastStart.isValid(); }
     881             : 
     882             :     /// Flush the updater state to LR so it is valid and contains all added
     883     1035323 :     /// segments.
     884             :     void flush();
     885     1035323 : 
     886             :     /// Select a different destination live range.
     887             :     void setDest(LiveRange *lr) {
     888       79689 :       if (LR != lr && isDirty())
     889         123 :         flush();
     890       79689 :       LR = lr;
     891             :     }
     892             : 
     893       96748 :     /// Get the current destination live range.
     894             :     LiveRange *getDest() const { return LR; }
     895             : 
     896             :     void dump() const;
     897             :     void print(raw_ostream&) const;
     898             :   };
     899             : 
     900             :   inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) {
     901             :     X.print(OS);
     902             :     return OS;
     903             :   }
     904             : 
     905             :   /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
     906             :   /// LiveInterval into equivalence clases of connected components. A
     907             :   /// LiveInterval that has multiple connected components can be broken into
     908             :   /// multiple LiveIntervals.
     909             :   ///
     910             :   /// Given a LiveInterval that may have multiple connected components, run:
     911             :   ///
     912             :   ///   unsigned numComps = ConEQ.Classify(LI);
     913             :   ///   if (numComps > 1) {
     914             :   ///     // allocate numComps-1 new LiveIntervals into LIS[1..]
     915             :   ///     ConEQ.Distribute(LIS);
     916             :   /// }
     917             : 
     918             :   class ConnectedVNInfoEqClasses {
     919             :     LiveIntervals &LIS;
     920             :     IntEqClasses EqClass;
     921             : 
     922             :   public:
     923     1658116 :     explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {}
     924             : 
     925             :     /// Classify the values in \p LR into connected components.
     926             :     /// Returns the number of connected components.
     927             :     unsigned Classify(const LiveRange &LR);
     928             : 
     929             :     /// getEqClass - Classify creates equivalence classes numbered 0..N. Return
     930             :     /// the equivalence class assigned the VNI.
     931           0 :     unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; }
     932             : 
     933             :     /// Distribute values in \p LI into a separate LiveIntervals
     934             :     /// for each connected component. LIV must have an empty LiveInterval for
     935             :     /// each additional connected component. The first connected component is
     936             :     /// left in \p LI.
     937             :     void Distribute(LiveInterval &LI, LiveInterval *LIV[],
     938             :                     MachineRegisterInfo &MRI);
     939             :   };
     940             : 
     941       79904 : } // end namespace llvm
     942             : 
     943             : #endif // LLVM_CODEGEN_LIVEINTERVAL_H

Generated by: LCOV version 1.13