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

SplitEditor - Edit machine code and LiveIntervals for live range splitting. More...

#include "CodeGen/SplitKit.h"

Public Types

enum  ComplementSpillMode { SM_Partition, SM_Size, SM_Speed }
 ComplementSpillMode - Select how the complement live range should be created. More...
 

Public Member Functions

 SplitEditor (SplitAnalysis &sa, AliasAnalysis &aa, LiveIntervals &lis, VirtRegMap &vrm, MachineDominatorTree &mdt, MachineBlockFrequencyInfo &mbfi)
 Create a new SplitEditor for editing the LiveInterval analyzed by SA. More...
 
void reset (LiveRangeEdit &, ComplementSpillMode=SM_Partition)
 reset - Prepare for a new split. More...
 
unsigned openIntv ()
 Create a new virtual register and live interval. More...
 
unsigned currentIntv () const
 currentIntv - Return the current interval index. More...
 
void selectIntv (unsigned Idx)
 selectIntv - Select a previously opened interval index. More...
 
SlotIndex enterIntvBefore (SlotIndex Idx)
 enterIntvBefore - Enter the open interval before the instruction at Idx. More...
 
SlotIndex enterIntvAfter (SlotIndex Idx)
 enterIntvAfter - Enter the open interval after the instruction at Idx. More...
 
SlotIndex enterIntvAtEnd (MachineBasicBlock &MBB)
 enterIntvAtEnd - Enter the open interval at the end of MBB. More...
 
void useIntv (const MachineBasicBlock &MBB)
 useIntv - indicate that all instructions in MBB should use OpenLI. More...
 
void useIntv (SlotIndex Start, SlotIndex End)
 useIntv - indicate that all instructions in range should use OpenLI. More...
 
SlotIndex leaveIntvAfter (SlotIndex Idx)
 leaveIntvAfter - Leave the open interval after the instruction at Idx. More...
 
SlotIndex leaveIntvBefore (SlotIndex Idx)
 leaveIntvBefore - Leave the open interval before the instruction at Idx. More...
 
SlotIndex leaveIntvAtTop (MachineBasicBlock &MBB)
 leaveIntvAtTop - Leave the interval at the top of MBB. More...
 
void overlapIntv (SlotIndex Start, SlotIndex End)
 overlapIntv - Indicate that all instructions in range should use the open interval, but also let the complement interval be live. More...
 
void finish (SmallVectorImpl< unsigned > *LRMap=nullptr)
 finish - after all the new live ranges have been created, compute the remaining live range, and rewrite instructions to use the new registers. More...
 
void dump () const
 dump - print the current interval mapping to dbgs(). More...
 
void splitSingleBlock (const SplitAnalysis::BlockInfo &BI)
 splitSingleBlock - Split CurLI into a separate live interval around the uses in a single block. More...
 
void splitLiveThroughBlock (unsigned MBBNum, unsigned IntvIn, SlotIndex LeaveBefore, unsigned IntvOut, SlotIndex EnterAfter)
 splitLiveThroughBlock - Split CurLI in the given block such that it enters the block in IntvIn and leaves it in IntvOut. More...
 
void splitRegInBlock (const SplitAnalysis::BlockInfo &BI, unsigned IntvIn, SlotIndex LeaveBefore)
 splitRegInBlock - Split CurLI in the given block such that it enters the block in IntvIn and leaves it on the stack (or not at all). More...
 
void splitRegOutBlock (const SplitAnalysis::BlockInfo &BI, unsigned IntvOut, SlotIndex EnterAfter)
 splitRegOutBlock - Split CurLI in the given block such that it enters the block on the stack (or isn't live-in at all) and leaves it in IntvOut. More...
 

Detailed Description

SplitEditor - Edit machine code and LiveIntervals for live range splitting.

Definition at line 241 of file SplitKit.h.

Member Enumeration Documentation

◆ ComplementSpillMode

ComplementSpillMode - Select how the complement live range should be created.

SplitEditor automatically creates interval 0 to contain anything that isn't added to another interval. This complement interval can get quite complicated, and it can sometimes be an advantage to allow it to overlap the other intervals. If it is going to spill anyway, no registers are wasted by keeping a value in two places at the same time.

Enumerator
SM_Partition 

SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other intervals, and the original interval is partitioned.

This may require a large number of back copies and extra PHI-defs. Only segments marked with overlapIntv will be overlapping.

SM_Size 

SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.

Copies to the complement interval are hoisted to their common dominator, so only one COPY is required per value in the complement interval. This also means that no extra PHI-defs need to be inserted in the complement interval.

SM_Speed 

SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.

This is very similar to SM_Size, but the complement interval may get some extra PHI-defs.

Definition at line 259 of file SplitKit.h.

Constructor & Destructor Documentation

◆ SplitEditor()

SplitEditor::SplitEditor ( SplitAnalysis sa,
AliasAnalysis aa,
LiveIntervals lis,
VirtRegMap vrm,
MachineDominatorTree mdt,
MachineBlockFrequencyInfo mbfi 
)

Create a new SplitEditor for editing the LiveInterval analyzed by SA.

Newly created intervals will be appended to newIntervals.

Definition at line 366 of file SplitKit.cpp.

Member Function Documentation

◆ currentIntv()

unsigned llvm::SplitEditor::currentIntv ( ) const
inline

currentIntv - Return the current interval index.

Definition at line 438 of file SplitKit.h.

References llvm::dump(), and llvm::WebAssembly::End.

◆ dump()

LLVM_DUMP_METHOD void SplitEditor::dump ( ) const

dump - print the current interval mapping to dbgs().

Definition at line 396 of file SplitKit.cpp.

References llvm::MachineInstrBuilder::addReg(), llvm::LaneBitmask::all(), llvm::LaneBitmask::any(), assert(), llvm::IntervalMap< KeyT, ValT, N, Traits >::begin(), llvm::BuildMI(), llvm::MachineInstr::bundleWithPred(), llvm::LiveRangeEdit::canRematerializeAt(), llvm::IntervalMap< SlotIndex, unsigned >::const_iterator, llvm::LiveRange::createDeadDef(), llvm::dbgs(), llvm::tgtok::Def, llvm::VNInfo::def, llvm::RegState::Define, DefMI, llvm::MachineInstr::defs(), E, llvm::IntervalMap< KeyT, ValT, N, Traits >::empty(), llvm::MCInstrInfo::get(), llvm::LiveRangeEdit::get(), llvm::LaneBitmask::getAll(), llvm::LiveIntervals::getInstructionFromIndex(), llvm::getInternalReadRegState(), llvm::LiveIntervals::getInterval(), llvm::MachineRegisterInfo::getMaxLaneMaskForVReg(), llvm::LaneBitmask::getNone(), llvm::LaneBitmask::getNumLanes(), llvm::MCRegisterInfo::getNumSubRegIndices(), llvm::VirtRegMap::getOriginal(), llvm::LiveRangeEdit::getParent(), llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::getPointer(), llvm::LiveRangeEdit::getReg(), llvm::MachineRegisterInfo::getRegClass(), llvm::SlotIndex::getRegSlot(), llvm::LiveIntervals::getSlotIndexes(), llvm::TargetRegisterInfo::getSubClassWithSubReg(), llvm::TargetRegisterInfo::getSubRegIndexLaneMask(), llvm::getUndefRegState(), llvm::LiveIntervals::getVNInfoAllocator(), llvm::LiveRange::getVNInfoAt(), llvm::LiveInterval::hasSubRanges(), I, llvm::VNInfo::id, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SlotIndexes::insertMachineInstrInMaps(), llvm::SlotIndex::isValid(), llvm_unreachable, llvm::LiveRangeEdit::Remat::OrigMI, llvm::X86II::PS, llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::LiveInterval::refineSubRanges(), llvm::LiveInterval::reg, llvm::LiveRangeEdit::rematerializeAt(), llvm::report_fatal_error(), llvm::NVPTX::PTXCvtMode::RM, llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::setInt(), and llvm::LiveInterval::subranges().

Referenced by enterIntvAtEnd(), leaveIntvAtTop(), overlapIntv(), and useIntv().

◆ enterIntvAfter()

SlotIndex SplitEditor::enterIntvAfter ( SlotIndex  Idx)

enterIntvAfter - Enter the open interval after the instruction at Idx.

Return the beginning of the new live range.

Definition at line 710 of file SplitKit.cpp.

References assert(), llvm::dbgs(), DEBUG, llvm::VNInfo::def, llvm::SlotIndex::getBoundaryIndex(), llvm::LiveIntervals::getInstructionFromIndex(), llvm::MachineInstr::getParent(), llvm::LiveRangeEdit::getParent(), llvm::LiveRange::getVNInfoAt(), llvm::VNInfo::id, and MI.

Referenced by splitLiveThroughBlock(), and splitRegOutBlock().

◆ enterIntvAtEnd()

SlotIndex SplitEditor::enterIntvAtEnd ( MachineBasicBlock MBB)

enterIntvAtEnd - Enter the open interval at the end of MBB.

Use the open interval from the inserted copy to the MBB end. Return the beginning of the new live range.

Definition at line 728 of file SplitKit.cpp.

References assert(), llvm::dbgs(), DEBUG, llvm::VNInfo::def, dump(), llvm::WebAssembly::End, llvm::SplitAnalysis::getLastSplitPointIter(), llvm::LiveIntervals::getMBBEndIdx(), llvm::MachineBasicBlock::getNumber(), llvm::LiveRangeEdit::getParent(), llvm::SlotIndex::getPrevSlot(), llvm::LiveRange::getVNInfoAt(), and llvm::IntervalMap< KeyT, ValT, N, Traits >::insert().

Referenced by splitLiveThroughBlock().

◆ enterIntvBefore()

SlotIndex SplitEditor::enterIntvBefore ( SlotIndex  Idx)

enterIntvBefore - Enter the open interval before the instruction at Idx.

If the parent interval is not live before Idx, a COPY is not inserted. Return the beginning of the new live range.

Definition at line 693 of file SplitKit.cpp.

References assert(), llvm::dbgs(), DEBUG, llvm::VNInfo::def, llvm::SlotIndex::getBaseIndex(), llvm::LiveIntervals::getInstructionFromIndex(), llvm::MachineInstr::getParent(), llvm::LiveRangeEdit::getParent(), llvm::LiveRange::getVNInfoAt(), llvm::VNInfo::id, and MI.

Referenced by splitLiveThroughBlock(), splitRegInBlock(), splitRegOutBlock(), and splitSingleBlock().

◆ finish()

void SplitEditor::finish ( SmallVectorImpl< unsigned > *  LRMap = nullptr)

finish - after all the new live ranges have been created, compute the remaining live range, and rewrite instructions to use the new registers.

Parameters
LRMapWhen not null, this vector will map each live range in Edit back to the indices returned by openIntv. There may be extra indices created by dead code elimination.

Definition at line 1429 of file SplitKit.cpp.

References assert(), llvm::SmallVectorImpl< T >::clear(), llvm::VNInfo::def, llvm::VNInfo::isUnused(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::LiveInterval::removeEmptySubRanges(), llvm::LiveRange::RenumberValues(), llvm::SmallVectorImpl< T >::resize(), llvm::SmallVectorTemplateCommon< T, typename >::size(), SM_Partition, SM_Size, and SM_Speed.

◆ leaveIntvAfter()

SlotIndex SplitEditor::leaveIntvAfter ( SlotIndex  Idx)

◆ leaveIntvAtTop()

SlotIndex SplitEditor::leaveIntvAtTop ( MachineBasicBlock MBB)

◆ leaveIntvBefore()

SlotIndex SplitEditor::leaveIntvBefore ( SlotIndex  Idx)

◆ openIntv()

unsigned SplitEditor::openIntv ( )

Create a new virtual register and live interval.

Return the interval index, starting from 1. Interval index 0 is the implicit complement interval.

Definition at line 675 of file SplitKit.cpp.

References llvm::LiveRangeEdit::createEmptyInterval(), llvm::LiveRangeEdit::empty(), and llvm::LiveRangeEdit::size().

Referenced by splitRegInBlock(), splitRegOutBlock(), and splitSingleBlock().

◆ overlapIntv()

void SplitEditor::overlapIntv ( SlotIndex  Start,
SlotIndex  End 
)

overlapIntv - Indicate that all instructions in range should use the open interval, but also let the complement interval be live.

This doubles the register pressure, but is sometimes required to deal with register uses after the last valid split point.

The Start index should be a return value from a leaveIntv* call, and End should be in the same basic block. The parent interval must have the same value across the range.

Definition at line 826 of file SplitKit.cpp.

References llvm::LiveRangeCalc::addLiveInBlock(), llvm::LiveRange::addSegment(), assert(), llvm::MachineBasicBlock::begin(), llvm::IntervalMap< KeyT, ValT, N, Traits >::begin(), llvm::LiveRangeCalc::calculateValues(), llvm::IntervalMap< SlotIndex, unsigned >::const_iterator, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), llvm::dbgs(), DEBUG, llvm::tgtok::Def, llvm::VNInfo::def, llvm::Depth, llvm::LiveRangeEdit::didRematerialize(), llvm::MachineDominatorTree::dominates(), dump(), llvm::SmallVectorBase::empty(), llvm::WebAssembly::End, llvm::MachineInstr::eraseFromParent(), llvm::LiveRange::extendInBlock(), llvm::MachineDominatorTree::findNearestCommonDominator(), llvm::LiveRangeEdit::get(), llvm::MachineBlockFrequencyInfo::getBlockFreq(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LiveIntervals::getInstructionFromIndex(), llvm::LiveIntervals::getInstructionIndex(), llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::getInt(), llvm::LiveIntervals::getInterval(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::SplitAnalysis::getLastSplitPointIter(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LiveIntervals::getMBBEndIdx(), llvm::LiveIntervals::getMBBFromIndex(), llvm::SlotIndexes::getMBBRange(), llvm::MachineBasicBlock::getNumber(), llvm::LiveRange::getNumValNums(), llvm::MachineInstr::getParent(), llvm::LiveRangeEdit::getParent(), llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::getPointer(), llvm::SlotIndex::getPrevSlot(), llvm::LiveRangeEdit::getReg(), llvm::SlotIndex::getRegSlot(), llvm::LiveIntervals::getSlotIndexes(), llvm::LiveRange::getValNumInfo(), llvm::LiveRange::getVNInfoAt(), llvm::LiveRange::getVNInfoBefore(), llvm::VNInfo::id, llvm::SmallVectorImpl< T >::insert(), llvm::IntervalMap< KeyT, ValT, N, Traits >::insert(), llvm::VNInfo::isPHIDef(), llvm::VNInfo::isUnused(), llvm::IntervalMap< SlotIndex, unsigned >::iterator, llvm::RegState::Kill, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::SplitAnalysis::Loops, Loops, llvm::max(), MI, llvm::PrintReg(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::LiveIntervals::RemoveMachineInstrFromMaps(), llvm::LiveIntervals::removeVRegDefAt(), llvm::LiveRangeCalc::setLiveOutValue(), llvm::SmallVectorTemplateCommon< T, typename >::size(), SM_Speed, and llvm::LiveRange::valnos.

Referenced by splitRegInBlock(), and splitSingleBlock().

◆ reset()

void SplitEditor::reset ( LiveRangeEdit LRE,
ComplementSpillMode  SM = SM_Partition 
)

◆ selectIntv()

void SplitEditor::selectIntv ( unsigned  Idx)

selectIntv - Select a previously opened interval index.

Definition at line 686 of file SplitKit.cpp.

References assert(), llvm::dbgs(), and DEBUG.

Referenced by splitLiveThroughBlock(), splitRegInBlock(), and splitRegOutBlock().

◆ splitLiveThroughBlock()

void SplitEditor::splitLiveThroughBlock ( unsigned  MBBNum,
unsigned  IntvIn,
SlotIndex  LeaveBefore,
unsigned  IntvOut,
SlotIndex  EnterAfter 
)

splitLiveThroughBlock - Split CurLI in the given block such that it enters the block in IntvIn and leaves it in IntvOut.

There may be uses in the block, but they will be ignored when placing split points.

Parameters
MBBNumBlock number.
IntvInInterval index entering the block.
LeaveBeforeWhen set, leave IntvIn before this point.
IntvOutInterval index leaving the block.
EnterAfterWhen set, enter IntvOut after this point.

Definition at line 1560 of file SplitKit.cpp.

References assert(), llvm::dbgs(), DEBUG, enterIntvAfter(), enterIntvAtEnd(), enterIntvBefore(), llvm::SlotIndex::getBaseIndex(), llvm::SlotIndex::getBoundaryIndex(), leaveIntvAtTop(), leaveIntvBefore(), selectIntv(), and useIntv().

◆ splitRegInBlock()

void SplitEditor::splitRegInBlock ( const SplitAnalysis::BlockInfo BI,
unsigned  IntvIn,
SlotIndex  LeaveBefore 
)

splitRegInBlock - Split CurLI in the given block such that it enters the block in IntvIn and leaves it on the stack (or not at all).

Split points are placed in a way that avoids putting uses in the stack interval. This may require creating a local interval when there is interference.

Parameters
BIBlock descriptor.
IntvInInterval index entering the block. Not 0.
LeaveBeforeWhen set, leave IntvIn before this point.

Definition at line 1663 of file SplitKit.cpp.

References assert(), llvm::dbgs(), DEBUG, enterIntvBefore(), llvm::SplitAnalysis::BlockInfo::FirstInstr, llvm::SlotIndex::getBoundaryIndex(), llvm::MachineBasicBlock::getNumber(), llvm::SplitAnalysis::BlockInfo::LastInstr, leaveIntvAfter(), leaveIntvBefore(), llvm::SplitAnalysis::BlockInfo::LiveIn, llvm::SplitAnalysis::BlockInfo::LiveOut, llvm::SplitAnalysis::BlockInfo::MBB, openIntv(), overlapIntv(), selectIntv(), and useIntv().

◆ splitRegOutBlock()

void SplitEditor::splitRegOutBlock ( const SplitAnalysis::BlockInfo BI,
unsigned  IntvOut,
SlotIndex  EnterAfter 
)

splitRegOutBlock - Split CurLI in the given block such that it enters the block on the stack (or isn't live-in at all) and leaves it in IntvOut.

Split points are placed to avoid interference and such that the uses are not in the stack interval. This may require creating a local interval when there is interference.

Parameters
BIBlock descriptor.
IntvOutInterval index leaving the block.
EnterAfterWhen set, enter IntvOut after this point.

Definition at line 1755 of file SplitKit.cpp.

References assert(), llvm::dbgs(), DEBUG, enterIntvAfter(), enterIntvBefore(), llvm::SplitAnalysis::BlockInfo::FirstInstr, llvm::SlotIndex::getBaseIndex(), llvm::MachineBasicBlock::getNumber(), llvm::SplitAnalysis::BlockInfo::LastInstr, llvm::SplitAnalysis::BlockInfo::LiveIn, llvm::SplitAnalysis::BlockInfo::LiveOut, llvm::SplitAnalysis::BlockInfo::MBB, openIntv(), selectIntv(), and useIntv().

◆ splitSingleBlock()

void SplitEditor::splitSingleBlock ( const SplitAnalysis::BlockInfo BI)

splitSingleBlock - Split CurLI into a separate live interval around the uses in a single block.

This is intended to be used as part of a larger split, and doesn't call finish().

Definition at line 1534 of file SplitKit.cpp.

References enterIntvBefore(), llvm::SplitAnalysis::BlockInfo::FirstInstr, llvm::MachineBasicBlock::getNumber(), llvm::SplitAnalysis::BlockInfo::LastInstr, leaveIntvAfter(), leaveIntvBefore(), llvm::SplitAnalysis::BlockInfo::LiveOut, llvm::SplitAnalysis::BlockInfo::MBB, openIntv(), overlapIntv(), and useIntv().

◆ useIntv() [1/2]

void SplitEditor::useIntv ( const MachineBasicBlock MBB)

useIntv - indicate that all instructions in MBB should use OpenLI.

Definition at line 747 of file SplitKit.cpp.

References llvm::LiveIntervals::getMBBEndIdx(), and llvm::LiveIntervals::getMBBStartIdx().

Referenced by splitLiveThroughBlock(), splitRegInBlock(), splitRegOutBlock(), and splitSingleBlock().

◆ useIntv() [2/2]

void SplitEditor::useIntv ( SlotIndex  Start,
SlotIndex  End 
)

useIntv - indicate that all instructions in range should use OpenLI.

Definition at line 751 of file SplitKit.cpp.

References assert(), llvm::dbgs(), DEBUG, dump(), and llvm::IntervalMap< KeyT, ValT, N, Traits >::insert().


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