LLVM API Documentation

llvm::LiveInterval Class Reference

#include <LiveInterval.h>

Collaboration diagram for llvm::LiveInterval:
[legend]

List of all members.

Public Types

typedef SmallVector< LiveRange, 4 > Ranges
typedef SmallVector< VNInfo *, 4 > VNInfoList
typedef Ranges::iterator iterator
typedef Ranges::const_iterator const_iterator
typedef VNInfoList::iterator vni_iterator
typedef VNInfoList::const_iterator const_vni_iterator

Public Member Functions

 LiveInterval (unsigned Reg, float Weight, bool IsSS=false)
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
iterator advanceTo (iterator I, unsigned Pos)
void clear ()
bool isStackSlot () const
int getStackSlotIndex () const
bool hasAtLeastOneValue () const
bool containsOneValue () const
unsigned getNumValNums () const
VNInfo * getValNumInfo (unsigned ValNo)
const VNInfo * getValNumInfo (unsigned ValNo) const
VNInfo * getNextValue (unsigned MIIdx, MachineInstr *CopyMI, bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator)
VNInfo * createValueCopy (const VNInfo *orig, BumpPtrAllocator &VNInfoAllocator)
void addKills (VNInfo *VNI, const VNInfo::KillSet &kills)
bool isOnlyLROfValNo (const LiveRange *LR)
VNInfo * MergeValueNumberInto (VNInfo *V1, VNInfo *V2)
void MergeInClobberRanges (const LiveInterval &Clobbers, BumpPtrAllocator &VNInfoAllocator)
void MergeInClobberRange (unsigned Start, unsigned End, BumpPtrAllocator &VNInfoAllocator)
void MergeRangesInAsValue (const LiveInterval &RHS, VNInfo *LHSValNo)
void MergeValueInAsValue (const LiveInterval &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo)
void Copy (const LiveInterval &RHS, MachineRegisterInfo *MRI, BumpPtrAllocator &VNInfoAllocator)
bool empty () const
unsigned beginNumber () const
 beginNumber - Return the lowest numbered slot covered by interval.
unsigned endNumber () const
bool expiredAt (unsigned index) const
bool liveAt (unsigned index) const
bool liveBeforeAndAt (unsigned index) const
const LiveRange * getLiveRangeContaining (unsigned Idx) const
LiveRange * getLiveRangeContaining (unsigned Idx)
const_iterator FindLiveRangeContaining (unsigned Idx) const
iterator FindLiveRangeContaining (unsigned Idx)
VNInfo * findDefinedVNInfo (unsigned DefIdxOrReg) const
bool overlaps (const LiveInterval &other) const
bool overlaps (unsigned Start, unsigned End) const
bool overlapsFrom (const LiveInterval &other, const_iterator I) const
void addRange (LiveRange LR)
void join (LiveInterval &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVector< VNInfo *, 16 > &NewVNInfo, MachineRegisterInfo *MRI)
bool isInOneLiveRange (unsigned Start, unsigned End)
void removeRange (unsigned Start, unsigned End, bool RemoveDeadValNo=false)
void removeRange (LiveRange LR, bool RemoveDeadValNo=false)
void removeValNo (VNInfo *ValNo)
void scaleNumbering (unsigned factor)
unsigned getSize () const
void ComputeJoinedWeight (const LiveInterval &Other)
bool operator< (const LiveInterval &other) const
void print (std::ostream &OS, const TargetRegisterInfo *TRI=0) const
void print (std::ostream *OS, const TargetRegisterInfo *TRI=0) const
void print (raw_ostream &OS, const TargetRegisterInfo *TRI=0) const
void print (raw_ostream *OS, const TargetRegisterInfo *TRI=0) const
void dump () const

Static Public Member Functions

static void addKill (VNInfo *VNI, unsigned KillIdx, bool phiKill)
static bool removeKill (VNInfo *VNI, unsigned KillIdx)
static void removeKills (VNInfo *VNI, unsigned Start, unsigned End)
static bool isKill (const VNInfo *VNI, unsigned KillIdx)

Public Attributes

unsigned reg
float weight
Ranges ranges
VNInfoList valnos

Classes

struct  InstrSlots


Detailed Description

LiveInterval - This class represents some number of live ranges for a register or value. This class also contains a bit of register allocator state.

Definition at line 248 of file LiveInterval.h.


Member Typedef Documentation

Definition at line 251 of file LiveInterval.h.

Definition at line 252 of file LiveInterval.h.

typedef Ranges::iterator llvm::LiveInterval::iterator

Definition at line 285 of file LiveInterval.h.

typedef Ranges::const_iterator llvm::LiveInterval::const_iterator

Definition at line 289 of file LiveInterval.h.

typedef VNInfoList::iterator llvm::LiveInterval::vni_iterator

Definition at line 293 of file LiveInterval.h.

typedef VNInfoList::const_iterator llvm::LiveInterval::const_vni_iterator

Definition at line 297 of file LiveInterval.h.


Constructor & Destructor Documentation

llvm::LiveInterval::LiveInterval ( unsigned  Reg,
float  Weight,
bool  IsSS = false 
) [inline]

Definition at line 279 of file LiveInterval.h.

References reg.


Member Function Documentation

iterator llvm::LiveInterval::begin (  )  [inline]

iterator llvm::LiveInterval::end (  )  [inline]

const_iterator llvm::LiveInterval::begin (  )  const [inline]

Definition at line 290 of file LiveInterval.h.

References ranges.

const_iterator llvm::LiveInterval::end (  )  const [inline]

Definition at line 291 of file LiveInterval.h.

References ranges.

vni_iterator llvm::LiveInterval::vni_begin (  )  [inline]

vni_iterator llvm::LiveInterval::vni_end (  )  [inline]

const_vni_iterator llvm::LiveInterval::vni_begin (  )  const [inline]

Definition at line 298 of file LiveInterval.h.

References valnos.

const_vni_iterator llvm::LiveInterval::vni_end (  )  const [inline]

Definition at line 299 of file LiveInterval.h.

References valnos.

iterator llvm::LiveInterval::advanceTo ( iterator  I,
unsigned  Pos 
) [inline]

advanceTo - Advance the specified iterator to point to the LiveRange containing the specified position, or end() if the position is past the end of the interval. If no LiveRange contains this position, but the position is in a hole, this method returns an iterator pointing the the LiveRange immediately after the hole.

Definition at line 306 of file LiveInterval.h.

References end(), and endNumber().

void llvm::LiveInterval::clear (  )  [inline]

Definition at line 313 of file LiveInterval.h.

References ranges, and valnos.

bool llvm::LiveInterval::isStackSlot (  )  const [inline]

isStackSlot - Return true if this is a stack slot interval.

Definition at line 325 of file LiveInterval.h.

References reg.

Referenced by getStackSlotIndex(), and print().

int llvm::LiveInterval::getStackSlotIndex (  )  const [inline]

getStackSlotIndex - Return stack slot index if this is a stack slot interval.

Definition at line 331 of file LiveInterval.h.

References isStackSlot(), and reg.

Referenced by print().

bool llvm::LiveInterval::hasAtLeastOneValue (  )  const [inline]

Definition at line 336 of file LiveInterval.h.

References valnos.

Referenced by addStackInterval().

bool llvm::LiveInterval::containsOneValue (  )  const [inline]

Definition at line 338 of file LiveInterval.h.

References valnos.

unsigned llvm::LiveInterval::getNumValNums (  )  const [inline]

VNInfo* llvm::LiveInterval::getValNumInfo ( unsigned  ValNo  )  [inline]

getValNumInfo - Returns pointer to the specified val#.

Definition at line 344 of file LiveInterval.h.

References valnos.

Referenced by addStackInterval(), Copy(), and join().

const VNInfo* llvm::LiveInterval::getValNumInfo ( unsigned  ValNo  )  const [inline]

Definition at line 347 of file LiveInterval.h.

References valnos.

VNInfo* llvm::LiveInterval::getNextValue ( unsigned  MIIdx,
MachineInstr *  CopyMI,
bool  isDefAccurate,
BumpPtrAllocator &  VNInfoAllocator 
) [inline]

getNextValue - Create a new value number and return it. MIIdx specifies the instruction that defines the value number.

Definition at line 353 of file LiveInterval.h.

References llvm::BumpPtrAllocator::Allocate(), llvm::VNInfo::setIsDefAccurate(), and valnos.

Referenced by llvm::LiveIntervals::addIntervalsForSpillsFast(), llvm::LiveIntervals::addLiveRangeToEndOfBlock(), addStackInterval(), MergeInClobberRange(), and MergeInClobberRanges().

VNInfo* llvm::LiveInterval::createValueCopy ( const VNInfo *  orig,
BumpPtrAllocator &  VNInfoAllocator 
) [inline]

Create a copy of the given value. The new value will be identical except for the Value number.

Definition at line 369 of file LiveInterval.h.

References llvm::BumpPtrAllocator::Allocate(), and valnos.

Referenced by Copy().

static void llvm::LiveInterval::addKill ( VNInfo *  VNI,
unsigned  KillIdx,
bool  phiKill 
) [inline, static]

addKill - Add a kill instruction index to the specified value number.

Definition at line 382 of file LiveInterval.h.

References llvm::VNInfo::kills.

void llvm::LiveInterval::addKills ( VNInfo *  VNI,
const VNInfo::KillSet &  kills 
) [inline]

addKills - Add a number of kills into the VNInfo kill vector. If this interval is live at a kill point, then the kill is not added.

Definition at line 396 of file LiveInterval.h.

References llvm::RegState::Kill, llvm::VNInfo::KillInfo::killIdx, llvm::VNInfo::kills, and liveBeforeAndAt().

static bool llvm::LiveInterval::removeKill ( VNInfo *  VNI,
unsigned  KillIdx 
) [inline, static]

removeKill - Remove the specified kill from the list of kills of the specified val#.

Definition at line 410 of file LiveInterval.h.

References llvm::VNInfo::kills.

static void llvm::LiveInterval::removeKills ( VNInfo *  VNI,
unsigned  Start,
unsigned  End 
) [inline, static]

removeKills - Remove all the kills in specified range [Start, End] of the specified val#.

Definition at line 423 of file LiveInterval.h.

References E, and llvm::VNInfo::kills.

Referenced by removeRange().

static bool llvm::LiveInterval::isKill ( const VNInfo *  VNI,
unsigned  KillIdx 
) [inline, static]

isKill - Return true if the specified index is a kill of the specified val#.

Definition at line 435 of file LiveInterval.h.

References llvm::VNInfo::kills.

bool llvm::LiveInterval::isOnlyLROfValNo ( const LiveRange *  LR  )  [inline]

isOnlyLROfValNo - Return true if the specified live range is the only one defined by the its val#.

Definition at line 444 of file LiveInterval.h.

References begin(), E, end(), and llvm::LiveRange::valno.

VNInfo * LiveInterval::MergeValueNumberInto ( VNInfo *  V1,
VNInfo *  V2 
)

MergeValueNumberInto - This method is called when two value nubmers are found to be equivalent. This eliminates V1, replacing all LiveRanges with the V1 value number with the V2 value number. This can cause merging of V1/V2 values numbers and compaction of the value space.

MergeValueNumberInto - This method is called when two value nubmers are found to be equivalent. This eliminates V1, replacing all LiveRanges with the V1 value number with the V2 value number. This can cause merging of V1/V2 values numbers and compaction of the value space.

Definition at line 705 of file LiveInterval.cpp.

References begin(), llvm::VNInfo::copyFrom(), end(), getNumValNums(), llvm::VNInfo::id, Prev, ranges, llvm::VNInfo::setIsUnused(), std::swap(), and valnos.

void LiveInterval::MergeInClobberRanges ( const LiveInterval &  Clobbers,
BumpPtrAllocator &  VNInfoAllocator 
)

MergeInClobberRanges - For any live ranges that are not defined in the current interval, but are defined in the Clobbers interval, mark them used with an unknown definition value. Caller must pass in reference to VNInfoAllocator since it will create a new val#.

MergeInClobberRanges - For any live ranges that are not defined in the current interval, but are defined in the Clobbers interval, mark them used with an unknown definition value.

Definition at line 610 of file LiveInterval.cpp.

References begin(), E, empty(), End, llvm::DenseMap< KeyT, ValueT, KeyInfoT, ValueInfoT >::end(), end(), llvm::DenseMap< KeyT, ValueT, KeyInfoT, ValueInfoT >::find(), getNextValue(), if(), llvm::DenseMap< KeyT, ValueT, KeyInfoT, ValueInfoT >::insert(), and valnos.

void LiveInterval::MergeInClobberRange ( unsigned  Start,
unsigned  End,
BumpPtrAllocator &  VNInfoAllocator 
)

MergeInClobberRange - Same as MergeInClobberRanges except it merge in a single LiveRange only.

Definition at line 675 of file LiveInterval.cpp.

References begin(), end(), and getNextValue().

void LiveInterval::MergeRangesInAsValue ( const LiveInterval &  RHS,
VNInfo *  LHSValNo 
)

MergeValueInAsValue - Merge all of the live ranges of a specific val# in RHS into this live interval as the specified value number. The LiveRanges in RHS are allowed to overlap with LiveRanges in the current interval, it will replace the value numbers of the overlaped live ranges with the specified value number.

MergeRangesInAsValue - Merge all of the intervals in RHS into this live interval as the specified value number. The LiveRanges in RHS are allowed to overlap with LiveRanges in the current interval, but only if the overlapping LiveRanges have the specified value number.

Definition at line 525 of file LiveInterval.cpp.

References begin(), E, end(), InsertPos, and llvm::LiveRange::valno.

Referenced by addStackInterval().

void LiveInterval::MergeValueInAsValue ( const LiveInterval &  RHS,
const VNInfo *  RHSValNo,
VNInfo *  LHSValNo 
)

MergeValueInAsValue - Merge all of the live ranges of a specific val# in RHS into this live interval as the specified value number. The LiveRanges in RHS are allowed to overlap with LiveRanges in the current interval, but only if the overlapping LiveRanges have the specified value number.

MergeValueInAsValue - Merge all of the live ranges of a specific val# in RHS into this live interval as the specified value number. The LiveRanges in RHS are allowed to overlap with LiveRanges in the current interval, it will replace the value numbers of the overlaped live ranges with the specified value number.

Definition at line 543 of file LiveInterval.cpp.

References begin(), E, End, end(), getNumValNums(), llvm::VNInfo::id, llvm::SmallSet< T, N >::insert(), llvm::SmallVectorImpl< T >::push_back(), llvm::VNInfo::setIsUnused(), llvm::SmallVectorImpl< T >::size(), V1, and valnos.

void LiveInterval::Copy ( const LiveInterval &  RHS,
MachineRegisterInfo *  MRI,
BumpPtrAllocator &  VNInfoAllocator 
)

bool llvm::LiveInterval::empty (  )  const [inline]

unsigned llvm::LiveInterval::beginNumber (  )  const [inline]

beginNumber - Return the lowest numbered slot covered by interval.

Definition at line 494 of file LiveInterval.h.

References empty(), and ranges.

Referenced by operator<().

unsigned llvm::LiveInterval::endNumber (  )  const [inline]

endNumber - return the maximum point of the interval of the whole, exclusive.

Definition at line 502 of file LiveInterval.h.

References empty(), and ranges.

Referenced by advanceTo(), and expiredAt().

bool llvm::LiveInterval::expiredAt ( unsigned  index  )  const [inline]

Definition at line 508 of file LiveInterval.h.

References endNumber().

bool LiveInterval::liveAt ( unsigned  index  )  const

bool LiveInterval::liveBeforeAndAt ( unsigned  index  )  const

Definition at line 52 of file LiveInterval.cpp.

References ranges.

Referenced by addKills().

const LiveRange* llvm::LiveInterval::getLiveRangeContaining ( unsigned  Idx  )  const [inline]

getLiveRangeContaining - Return the live range that contains the specified index, or null if there is none.

Definition at line 521 of file LiveInterval.h.

References end(), and FindLiveRangeContaining().

LiveRange* llvm::LiveInterval::getLiveRangeContaining ( unsigned  Idx  )  [inline]

getLiveRangeContaining - Return the live range that contains the specified index, or null if there is none.

Definition at line 528 of file LiveInterval.h.

References end(), and FindLiveRangeContaining().

LiveInterval::const_iterator LiveInterval::FindLiveRangeContaining ( unsigned  Idx  )  const

FindLiveRangeContaining - Return an iterator to the live range that contains the specified index, or end() if there is none.

getLiveRangeContaining - Return the live range that contains the specified index, or null if there is none.

Definition at line 390 of file LiveInterval.cpp.

References begin(), end(), and ranges.

Referenced by getLiveRangeContaining(), and removeRange().

LiveInterval::iterator LiveInterval::FindLiveRangeContaining ( unsigned  Idx  ) 

FindLiveRangeContaining - Return an iterator to the live range that contains the specified index, or end() if there is none.

Definition at line 402 of file LiveInterval.cpp.

References begin(), and end().

VNInfo * LiveInterval::findDefinedVNInfo ( unsigned  DefIdxOrReg  )  const

findDefinedVNInfo - Find the VNInfo that's defined at the specified index (register interval) or defined by the specified register (stack inteval).

findDefinedVNInfo - Find the VNInfo that's defined at the specified index (register interval) or defined by the specified register (stack inteval).

Definition at line 415 of file LiveInterval.cpp.

References vni_begin(), and vni_end().

bool llvm::LiveInterval::overlaps ( const LiveInterval &  other  )  const [inline]

overlaps - Return true if the intersection of the two live intervals is not empty.

Definition at line 548 of file LiveInterval.h.

References begin(), and overlapsFrom().

Referenced by llvm::RegallocQuery::interfere().

bool LiveInterval::overlaps ( unsigned  Start,
unsigned  End 
) const

overlaps - Return true if the live interval overlaps a range specified by [Start, End).

overlaps - Return true if the live interval overlaps a range specified by [Start, End).

Definition at line 130 of file LiveInterval.cpp.

References begin(), E, and end().

bool LiveInterval::overlapsFrom ( const LiveInterval &  other,
const_iterator  I 
) const

overlapsFrom - Return true if the intersection of the two live intervals is not empty. The specified iterator is a hint that we can begin scanning the Other interval starting at I.

Definition at line 88 of file LiveInterval.cpp.

References begin(), end(), ranges, and std::swap().

Referenced by overlaps().

void llvm::LiveInterval::addRange ( LiveRange  LR  )  [inline]

addRange - Add the specified LiveRange to this interval, merging intervals as appropriate. This returns an iterator to the inserted live range (which may have grown since it was inserted.

Definition at line 564 of file LiveInterval.h.

References ranges.

Referenced by llvm::LiveIntervals::addIntervalsForSpillsFast(), llvm::LiveIntervals::addLiveRangeToEndOfBlock(), and Copy().

void LiveInterval::join ( LiveInterval &  Other,
const int *  LHSValNoAssignments,
const int *  RHSValNoAssignments,
SmallVector< VNInfo *, 16 > &  NewVNInfo,
MachineRegisterInfo *  MRI 
)

join - Join two live intervals (this, and other) together. This applies mappings to the value numbers in the LHS/RHS intervals as specified. If the intervals are not joinable, this aborts.

join - Join two live intervals (this, and other) together. This applies mappings to the value numbers in the LHS/RHS intervals as specified. If the intervals are not joinable, this aborts.

Definition at line 429 of file LiveInterval.cpp.

References begin(), ComputeJoinedWeight(), E, end(), getNumValNums(), llvm::MachineRegisterInfo::getRegAllocationHint(), getValNumInfo(), llvm::VNInfo::id, InsertPos, llvm::TargetRegisterInfo::isVirtualRegister(), llvm::SmallVectorImpl< T >::push_back(), ranges, reg, llvm::MachineRegisterInfo::setRegAllocationHint(), llvm::SmallVectorImpl< T >::size(), and valnos.

bool LiveInterval::isInOneLiveRange ( unsigned  Start,
unsigned  End 
)

isInOneLiveRange - Return true if the range specified is entirely in the a single LiveRange of the live interval.

isInOneLiveRange - Return true if the range specified is entirely in the a single LiveRange of the live interval.

Definition at line 267 of file LiveInterval.cpp.

References ranges.

Referenced by llvm::LiveIntervals::spillPhysRegAroundRegDefsUses().

void LiveInterval::removeRange ( unsigned  Start,
unsigned  End,
bool  RemoveDeadValNo = false 
)

removeRange - Remove the specified range from this interval. Note that the range must be a single LiveRange in its entirety.

removeRange - Remove the specified range from this interval. Note that the range must be in a single LiveRange in its entirety.

Definition at line 278 of file LiveInterval.cpp.

References begin(), end(), getNumValNums(), II, llvm::next(), ranges, removeKills(), llvm::VNInfo::setIsUnused(), and valnos.

Referenced by llvm::LiveIntervals::addIntervalsForSpills(), removeRange(), removeRange(), and llvm::LiveIntervals::spillPhysRegAroundRegDefsUses().

void llvm::LiveInterval::removeRange ( LiveRange  LR,
bool  RemoveDeadValNo = false 
) [inline]

Definition at line 584 of file LiveInterval.h.

References llvm::LiveRange::end, removeRange(), and llvm::LiveRange::start.

void LiveInterval::removeValNo ( VNInfo *  ValNo  ) 

removeValNo - Remove all the ranges defined by the specified value#. Also remove the value# from value# list.

removeValNo - Remove all the ranges defined by the specified value#. Also remove the value# from value# list.

Definition at line 340 of file LiveInterval.cpp.

References E, empty(), getNumValNums(), llvm::VNInfo::id, ranges, llvm::VNInfo::setIsUnused(), and valnos.

void LiveInterval::scaleNumbering ( unsigned  factor  ) 

scaleNumbering - Renumber VNI and ranges to provide gaps for new instructions.

scaleNumbering - Renumber VNI and ranges to provide gaps for new instructions.

Definition at line 365 of file LiveInterval.cpp.

References begin(), llvm::VNInfo::def, end(), llvm::VNInfo::isDefAccurate(), llvm::VNInfo::kills, llvm::LiveInterval::InstrSlots::scale(), vni_begin(), and vni_end().

unsigned LiveInterval::getSize (  )  const

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

Definition at line 789 of file LiveInterval.cpp.

References begin(), E, and end().

Referenced by llvm::LiveIntervals::getScaledIntervalSize().

void LiveInterval::ComputeJoinedWeight ( const LiveInterval &  Other  ) 

ComputeJoinedWeight - Set the weight of a live interval after Other has been merged into it.

ComputeJoinedWeight - Set the weight of a live interval Joined after Other has been merged into it.

Definition at line 798 of file LiveInterval.cpp.

References HUGE_VALF, llvm::TargetRegisterInfo::isPhysicalRegister(), reg, and weight.

Referenced by join().

bool llvm::LiveInterval::operator< ( const LiveInterval &  other  )  const [inline]

Definition at line 604 of file LiveInterval.h.

References beginNumber().

void LiveInterval::print ( std::ostream &  OS,
const TargetRegisterInfo *  TRI = 0 
) const

void llvm::LiveInterval::print ( std::ostream *  OS,
const TargetRegisterInfo *  TRI = 0 
) const [inline]

Definition at line 609 of file LiveInterval.h.

References print(), and TRI.

void LiveInterval::print ( raw_ostream &  OS,
const TargetRegisterInfo *  TRI = 0 
) const

void llvm::LiveInterval::print ( raw_ostream *  OS,
const TargetRegisterInfo *  TRI = 0 
) const [inline]

Definition at line 613 of file LiveInterval.h.

References print(), and TRI.

void LiveInterval::dump (  )  const

Definition at line 894 of file LiveInterval.cpp.

References llvm::errs().

Referenced by llvm::LiveIntervals::addIntervalsForSpillsFast().


Member Data Documentation


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