LLVM  6.0.0svn
Classes | Public Types | Public Member Functions | Public Attributes | List of all members
llvm::LiveInterval Class Reference

LiveInterval - This class represents the liveness of a register, or stack slot. More...

#include "llvm/CodeGen/LiveInterval.h"

Inheritance diagram for llvm::LiveInterval:
Inheritance graph
[legend]
Collaboration diagram for llvm::LiveInterval:
Collaboration graph
[legend]

Classes

class  SingleLinkedListIterator
 
class  SubRange
 A live range for subregisters. More...
 

Public Types

using super = LiveRange
 
using subrange_iterator = SingleLinkedListIterator< SubRange >
 
using const_subrange_iterator = SingleLinkedListIterator< const SubRange >
 
- Public Types inherited from llvm::LiveRange
using Segments = SmallVector< Segment, 2 >
 
using VNInfoList = SmallVector< VNInfo *, 2 >
 
using SegmentSet = std::set< Segment >
 
using iterator = Segments::iterator
 
using const_iterator = Segments::const_iterator
 
using vni_iterator = VNInfoList::iterator
 
using const_vni_iterator = VNInfoList::const_iterator
 

Public Member Functions

 LiveInterval (unsigned Reg, float Weight)
 
 ~LiveInterval ()
 
subrange_iterator subrange_begin ()
 
subrange_iterator subrange_end ()
 
const_subrange_iterator subrange_begin () const
 
const_subrange_iterator subrange_end () const
 
iterator_range< subrange_iteratorsubranges ()
 
iterator_range< const_subrange_iteratorsubranges () const
 
SubRangecreateSubRange (BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
 Creates a new empty subregister live range. More...
 
SubRangecreateSubRangeFrom (BumpPtrAllocator &Allocator, LaneBitmask LaneMask, const LiveRange &CopyFrom)
 Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom. More...
 
bool hasSubRanges () const
 Returns true if subregister liveness information is available. More...
 
void clearSubRanges ()
 Removes all subregister liveness information. More...
 
void removeEmptySubRanges ()
 Removes all subranges without any segments (subranges without segments are not considered valid and should only exist temporarily). More...
 
unsigned getSize () const
 getSize - Returns the sum of sizes of all the LiveRange's. More...
 
bool isSpillable () const
 isSpillable - Can this interval be spilled? More...
 
void markNotSpillable ()
 markNotSpillable - Mark interval as not spillable More...
 
void computeSubRangeUndefs (SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
 For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister <def,read-undef> definitions. More...
 
void refineSubRanges (BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Mod)
 Refines the subranges to support LaneMask. More...
 
bool operator< (const LiveInterval &other) const
 
void print (raw_ostream &OS) const
 
void dump () const
 
void verify (const MachineRegisterInfo *MRI=nullptr) const
 Walks the interval and assert if any invariants fail to hold. More...
 
- Public Member Functions inherited from llvm::LiveRange
iterator begin ()
 
iterator end ()
 
const_iterator begin () const
 
const_iterator end () const
 
vni_iterator vni_begin ()
 
vni_iterator vni_end ()
 
const_vni_iterator vni_begin () const
 
const_vni_iterator vni_end () const
 
 LiveRange (bool UseSegmentSet=false)
 Constructs a new LiveRange object. More...
 
 LiveRange (const LiveRange &Other, BumpPtrAllocator &Allocator)
 Constructs a new LiveRange object by copying segments and valnos from another LiveRange. More...
 
void assign (const LiveRange &Other, BumpPtrAllocator &Allocator)
 Copies values numbers and live segments from Other into this range. More...
 
iterator advanceTo (iterator I, SlotIndex Pos)
 advanceTo - Advance the specified iterator to point to the Segment containing the specified position, or end() if the position is past the end of the range. More...
 
const_iterator advanceTo (const_iterator I, SlotIndex Pos) const
 
iterator find (SlotIndex Pos)
 find - Return an iterator pointing to the first segment that ends after Pos, or end(). More...
 
const_iterator find (SlotIndex Pos) const
 
void clear ()
 
size_t size () const
 
bool hasAtLeastOneValue () const
 
bool containsOneValue () const
 
unsigned getNumValNums () const
 
VNInfogetValNumInfo (unsigned ValNo)
 getValNumInfo - Returns pointer to the specified val#. More...
 
const VNInfogetValNumInfo (unsigned ValNo) const
 
bool containsValue (const VNInfo *VNI) const
 containsValue - Returns true if VNI belongs to this range. More...
 
VNInfogetNextValue (SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
 getNextValue - Create a new value number and return it. More...
 
VNInfocreateDeadDef (SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
 createDeadDef - Make sure the range has a value defined at Def. More...
 
VNInfocreateDeadDef (VNInfo *VNI)
 Create a def of value VNI. More...
 
VNInfocreateValueCopy (const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator)
 Create a copy of the given value. More...
 
void RenumberValues ()
 RenumberValues - Renumber all values in order of appearance and remove unused values. More...
 
VNInfoMergeValueNumberInto (VNInfo *V1, VNInfo *V2)
 MergeValueNumberInto - This method is called when two value numbers are found to be equivalent. More...
 
void MergeSegmentsInAsValue (const LiveRange &RHS, VNInfo *LHSValNo)
 Merge all of the live segments of a specific val# in RHS into this live range as the specified value number. More...
 
void MergeValueInAsValue (const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo)
 MergeValueInAsValue - Merge all of the segments of a specific val# in RHS into this live range as the specified value number. More...
 
bool empty () const
 
SlotIndex beginIndex () const
 beginIndex - Return the lowest numbered slot covered. More...
 
SlotIndex endIndex () const
 endNumber - return the maximum point of the range of the whole, exclusive. More...
 
bool expiredAt (SlotIndex index) const
 
bool liveAt (SlotIndex index) const
 
const SegmentgetSegmentContaining (SlotIndex Idx) const
 Return the segment that contains the specified index, or null if there is none. More...
 
SegmentgetSegmentContaining (SlotIndex Idx)
 Return the live segment that contains the specified index, or null if there is none. More...
 
VNInfogetVNInfoAt (SlotIndex Idx) const
 getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. More...
 
VNInfogetVNInfoBefore (SlotIndex Idx) const
 getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx, or NULL. More...
 
iterator FindSegmentContaining (SlotIndex Idx)
 Return an iterator to the segment that contains the specified index, or end() if there is none. More...
 
const_iterator FindSegmentContaining (SlotIndex Idx) const
 
bool overlaps (const LiveRange &other) const
 overlaps - Return true if the intersection of the two live ranges is not empty. More...
 
bool overlaps (const LiveRange &Other, const CoalescerPair &CP, const SlotIndexes &) const
 overlaps - Return true if the two ranges have overlapping segments that are not coalescable according to CP. More...
 
bool overlaps (SlotIndex Start, SlotIndex End) const
 overlaps - Return true if the live range overlaps an interval specified by [Start, End). More...
 
bool overlapsFrom (const LiveRange &Other, const_iterator I) const
 overlapsFrom - Return true if the intersection of the two live ranges is not empty. More...
 
bool covers (const LiveRange &Other) const
 Returns true if all segments of the Other live range are completely covered by this live range. More...
 
iterator addSegment (Segment S)
 Add the specified Segment to this range, merging segments as appropriate. More...
 
std::pair< VNInfo *, boolextendInBlock (ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Use)
 Attempt to extend a value defined after StartIdx to include Use. More...
 
VNInfoextendInBlock (SlotIndex StartIdx, SlotIndex Kill)
 Simplified version of the above "extendInBlock", which assumes that no register lanes are undefined by <def,read-undef> operands. More...
 
void join (LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo *> &NewVNInfo)
 join - Join two live ranges (this, and other) together. More...
 
bool isLocal (SlotIndex Start, SlotIndex End) const
 True iff this segment is a single segment that lies between the specified boundaries, exclusively. More...
 
void removeSegment (SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
 Remove the specified segment from this range. More...
 
void removeSegment (Segment S, bool RemoveDeadValNo=false)
 
iterator removeSegment (iterator I)
 Remove segment pointed to by iterator I from this range. More...
 
LiveQueryResult Query (SlotIndex Idx) const
 Query Liveness at Idx. More...
 
void removeValNo (VNInfo *ValNo)
 removeValNo - Remove all the segments defined by the specified value#. More...
 
bool isZeroLength (SlotIndexes *Indexes) const
 Returns true if the live range is zero length, i.e. More...
 
bool isLiveAtIndexes (ArrayRef< SlotIndex > Slots) const
 
bool operator< (const LiveRange &other) const
 
bool isUndefIn (ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
 Returns true if there is an explicit "undef" between Begin End. More...
 
void flushSegmentSet ()
 Flush segment set into the regular segment vector. More...
 
void print (raw_ostream &OS) const
 
void dump () const
 
void verify () const
 Walk the range and assert if any invariants fail to hold. More...
 

Public Attributes

const unsigned reg
 
float weight
 
- Public Attributes inherited from llvm::LiveRange
Segments segments
 
VNInfoList valnos
 
std::unique_ptr< SegmentSetsegmentSet
 

Additional Inherited Members

- Protected Member Functions inherited from llvm::LiveRange
void append (const LiveRange::Segment S)
 Append a segment to the list of segments. More...
 

Detailed Description

LiveInterval - This class represents the liveness of a register, or stack slot.

Definition at line 638 of file LiveInterval.h.

Member Typedef Documentation

◆ const_subrange_iterator

Definition at line 707 of file LiveInterval.h.

◆ subrange_iterator

Definition at line 706 of file LiveInterval.h.

◆ super

Definition at line 640 of file LiveInterval.h.

Constructor & Destructor Documentation

◆ LiveInterval()

llvm::LiveInterval::LiveInterval ( unsigned  Reg,
float  Weight 
)
inline

Definition at line 670 of file LiveInterval.h.

◆ ~LiveInterval()

llvm::LiveInterval::~LiveInterval ( )
inline

Definition at line 672 of file LiveInterval.h.

Member Function Documentation

◆ clearSubRanges()

void LiveInterval::clearSubRanges ( )

Removes all subregister liveness information.

Definition at line 874 of file LiveInterval.cpp.

Referenced by isTerminalReg().

◆ computeSubRangeUndefs()

void LiveInterval::computeSubRangeUndefs ( SmallVectorImpl< SlotIndex > &  Undefs,
LaneBitmask  LaneMask,
const MachineRegisterInfo MRI,
const SlotIndexes Indexes 
) const

◆ createSubRange()

SubRange* llvm::LiveInterval::createSubRange ( BumpPtrAllocator Allocator,
LaneBitmask  LaneMask 
)
inline

Creates a new empty subregister live range.

The range is added at the beginning of the subrange list; subrange iterators stay valid.

Definition at line 733 of file LiveInterval.h.

Referenced by llvm::ConnectedVNInfoEqClasses::Distribute().

◆ createSubRangeFrom()

SubRange* llvm::LiveInterval::createSubRangeFrom ( BumpPtrAllocator Allocator,
LaneBitmask  LaneMask,
const LiveRange CopyFrom 
)
inline

Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom.

Definition at line 742 of file LiveInterval.h.

Referenced by llvm::LiveRangeCalc::calculate(), and isDefInSubRange().

◆ dump()

LLVM_DUMP_METHOD void LiveInterval::dump ( ) const

Definition at line 1005 of file LiveInterval.cpp.

References llvm::dbgs().

Referenced by computeWeight(), and false::IntervalSorter::operator()().

◆ getSize()

unsigned LiveInterval::getSize ( ) const

getSize - Returns the sum of sizes of all the LiveRange's.

Definition at line 912 of file LiveInterval.cpp.

Referenced by llvm::createGreedyRegisterAllocator(), and llvm::VirtRegAuxInfo::weightCalcHelper().

◆ hasSubRanges()

bool llvm::LiveInterval::hasSubRanges ( ) const
inline

◆ isSpillable()

bool llvm::LiveInterval::isSpillable ( ) const
inline

isSpillable - Can this interval be spilled?

Definition at line 767 of file LiveInterval.h.

References llvm::huge_valf.

Referenced by llvm::createGreedyRegisterAllocator(), hasTiedDef(), isFullUndefDef(), and llvm::VirtRegAuxInfo::weightCalcHelper().

◆ markNotSpillable()

void llvm::LiveInterval::markNotSpillable ( )
inline

markNotSpillable - Mark interval as not spillable

Definition at line 772 of file LiveInterval.h.

References function, llvm::huge_valf, llvm::Mod, and MRI.

Referenced by llvm::LiveRangeEdit::createEmptyIntervalFrom(), and llvm::VirtRegAuxInfo::weightCalcHelper().

◆ operator<()

bool llvm::LiveInterval::operator< ( const LiveInterval other) const
inline

◆ print()

void LiveInterval::print ( raw_ostream OS) const

Definition at line 988 of file LiveInterval.cpp.

References print(), and llvm::printReg().

Referenced by llvm::operator<<().

◆ refineSubRanges()

void LiveInterval::refineSubRanges ( BumpPtrAllocator Allocator,
LaneBitmask  LaneMask,
std::function< void(LiveInterval::SubRange &)>  Mod 
)

Refines the subranges to support LaneMask.

This may only be called for LI.hasSubrange()==true. Subregister ranges are split or created until LaneMask can be matched exactly. Mod is executed on the matching subranges.

Example: Given an interval with subranges with lanemasks L0F00, L00F0 and L000F, refining for mask L0018. Will split the L00F0 lane into L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod function will be applied to the L0010 and L0008 subranges.

Definition at line 882 of file LiveInterval.cpp.

References llvm::LaneBitmask::any(), llvm::LiveInterval::SubRange::LaneMask, and llvm::LaneBitmask::none().

Referenced by addSegmentsWithValNo(), llvm::LiveRangeCalc::calculate(), llvm::SplitEditor::dump(), and isDefInSubRange().

◆ removeEmptySubRanges()

void LiveInterval::removeEmptySubRanges ( )

Removes all subranges without any segments (subranges without segments are not considered valid and should only exist temporarily).

Definition at line 855 of file LiveInterval.cpp.

References llvm::LiveRange::empty(), I, and llvm::LiveInterval::SubRange::Next.

Referenced by llvm::LiveRangeCalc::calculate(), llvm::ConnectedVNInfoEqClasses::Distribute(), llvm::LiveRangeEdit::eraseVirtReg(), llvm::SplitEditor::finish(), removeDeadSegment(), llvm::LiveIntervals::removeVRegDefAt(), llvm::LiveIntervals::shrinkToUses(), and subRangeLiveAt().

◆ subrange_begin() [1/2]

subrange_iterator llvm::LiveInterval::subrange_begin ( )
inline

Definition at line 709 of file LiveInterval.h.

◆ subrange_begin() [2/2]

const_subrange_iterator llvm::LiveInterval::subrange_begin ( ) const
inline

Definition at line 716 of file LiveInterval.h.

◆ subrange_end() [1/2]

subrange_iterator llvm::LiveInterval::subrange_end ( )
inline

Definition at line 712 of file LiveInterval.h.

◆ subrange_end() [2/2]

const_subrange_iterator llvm::LiveInterval::subrange_end ( ) const
inline

Definition at line 719 of file LiveInterval.h.

◆ subranges() [1/2]

iterator_range<subrange_iterator> llvm::LiveInterval::subranges ( )
inline

◆ subranges() [2/2]

iterator_range<const_subrange_iterator> llvm::LiveInterval::subranges ( ) const
inline

Definition at line 727 of file LiveInterval.h.

References llvm::make_range().

◆ verify()

void LiveInterval::verify ( const MachineRegisterInfo MRI = nullptr) const

Walks the interval and assert if any invariants fail to hold.

Note that this is a no-op when asserts are disabled.

Definition at line 1027 of file LiveInterval.cpp.

References assert(), llvm::LaneBitmask::getAll(), llvm::MachineRegisterInfo::getMaxLaneMaskForVReg(), llvm::BitmaskEnumDetail::Mask(), and verify.

Member Data Documentation

◆ reg

const unsigned llvm::LiveInterval::reg

◆ weight

float llvm::LiveInterval::weight

The documentation for this class was generated from the following files: