class SplitEditor

Declaration

class SplitEditor { /* full declaration omitted */ };

Description

SplitEditor - Edit machine code and LiveIntervals for live range splitting. - Create a SplitEditor from a SplitAnalysis. - Start a new live interval with openIntv. - Mark the places where the new interval is entered using enterIntv* - Mark the ranges where the new interval is used with useIntv* - Mark the places where the interval is exited with exitIntv*. - Finish the current interval with closeIntv and repeat from 2. - Rewrite instructions with finish().

Declared at: llvm/lib/CodeGen/SplitKit.h:258

Member Variables

private llvm::SplitAnalysis& SA

private llvm::LiveIntervals& LIS

private llvm::VirtRegMap& VRM

private llvm::MachineRegisterInfo& MRI

private llvm::MachineDominatorTree& MDT

private const llvm::TargetInstrInfo& TII

private const llvm::TargetRegisterInfo& TRI

private const llvm::MachineBlockFrequencyInfo& MBFI

private llvm::VirtRegAuxInfo& VRAI

private llvm::LiveRangeEdit* Edit = nullptr

Edit - The current parent register and new intervals created.

private unsigned int OpenIdx = 0

Index into Edit of the currently open interval. The index 0 is used for the complement, so the first interval started by openIntv will be 1.

private llvm::SplitEditor::ComplementSpillMode SpillMode = SM_Partition

The current spill mode, selected by reset().

private RegAssignMap::Allocator Allocator

Allocator for the interval map. This will eventually be shared with SlotIndexes and LiveIntervals.

private llvm::SplitEditor::RegAssignMap RegAssign

RegAssign - Map of the assigned register indexes. Edit.get(RegAssign.lookup(Idx)) is the register that should be live at Idx.

private llvm::SplitEditor::ValueMap Values

1. No entry - the value is not mapped to Edit.get(RegIdx). 2. (Null, false) - the value is mapped to multiple values in Edit.get(RegIdx). Each value is represented by a minimal live range at its def. The full live range can be inferred exactly from the range of RegIdx in RegAssign. 3. (Null, true). As above, but the ranges in RegAssign are too large, and the live range must be recomputed using ::extend(). 4. (VNI, false) The value is mapped to a single new value. The new value has no live ranges anywhere.

private llvm::LiveIntervalCalc[2] LICalc

LICalc - Cache for computing live ranges and SSA update. Each instance can only handle non-overlapping live ranges, so use a separate LiveIntervalCalc instance for the complement interval when in spill mode.

Method Overview

• public SplitEditor(llvm::SplitAnalysis & SA, llvm::LiveIntervals & LIS, llvm::VirtRegMap & VRM, llvm::MachineDominatorTree & MDT, llvm::MachineBlockFrequencyInfo & MBFI, llvm::VirtRegAuxInfo & VRAI)
• private void addDeadDef(llvm::LiveInterval & LI, llvm::VNInfo * VNI, bool Original)
• private llvm::SlotIndex buildCopy(llvm::Register FromReg, llvm::Register ToReg, llvm::LaneBitmask LaneMask, llvm::MachineBasicBlock & MBB, MachineBasicBlock::iterator InsertBefore, bool Late, unsigned int RegIdx)
• private llvm::SlotIndex buildSingleSubRegCopy(llvm::Register FromReg, llvm::Register ToReg, llvm::MachineBasicBlock & MB, MachineBasicBlock::iterator InsertBefore, unsigned int SubIdx, llvm::LiveInterval & DestLI, bool Late, llvm::SlotIndex Def)
• private void computeRedundantBackCopies(DenseSet<unsigned int> & NotToHoistSet, SmallVectorImpl<llvm::VNInfo *> & BackCopies)
• public unsigned int currentIntv() const
• private llvm::VNInfo * defFromParent(unsigned int RegIdx, const llvm::VNInfo * ParentVNI, llvm::SlotIndex UseIdx, llvm::MachineBasicBlock & MBB, MachineBasicBlock::iterator I)
• private llvm::VNInfo * defValue(unsigned int RegIdx, const llvm::VNInfo * ParentVNI, llvm::SlotIndex Idx, bool Original)
• private void deleteRematVictims()
• public void dump() const
• public llvm::SlotIndex enterIntvAfter(llvm::SlotIndex Idx)
• public llvm::SlotIndex enterIntvAtEnd(llvm::MachineBasicBlock & MBB)
• public llvm::SlotIndex enterIntvBefore(llvm::SlotIndex Idx)
• private void extendPHIKillRanges()
• private void extendPHIRange(llvm::MachineBasicBlock & B, llvm::LiveIntervalCalc & LIC, llvm::LiveRange & LR, llvm::LaneBitmask LM, ArrayRef<llvm::SlotIndex> Undefs)
• private llvm::MachineBasicBlock * findShallowDominator(llvm::MachineBasicBlock * MBB, llvm::MachineBasicBlock * DefMBB)
• public void finish(SmallVectorImpl<unsigned int> * LRMap = nullptr)
• private void forceRecompute(unsigned int RegIdx, const llvm::VNInfo & ParentVNI)
• private void forceRecomputeVNI(const llvm::VNInfo & ParentVNI)
• private llvm::LiveIntervalCalc & getLICalc(unsigned int RegIdx)
• private void hoistCopies()
• public llvm::SlotIndex leaveIntvAfter(llvm::SlotIndex Idx)
• public llvm::SlotIndex leaveIntvAtTop(llvm::MachineBasicBlock & MBB)
• public llvm::SlotIndex leaveIntvBefore(llvm::SlotIndex Idx)
• public unsigned int openIntv()
• public void overlapIntv(llvm::SlotIndex Start, llvm::SlotIndex End)
• private void removeBackCopies(SmallVectorImpl<llvm::VNInfo *> & Copies)
• public void reset(llvm::LiveRangeEdit &, llvm::SplitEditor::ComplementSpillMode = SM_Partition)
• private void rewriteAssigned(bool ExtendRanges)
• public void selectIntv(unsigned int Idx)
• public void splitLiveThroughBlock(unsigned int MBBNum, unsigned int IntvIn, llvm::SlotIndex LeaveBefore, unsigned int IntvOut, llvm::SlotIndex EnterAfter)
• public void splitRegInBlock(const SplitAnalysis::BlockInfo & BI, unsigned int IntvIn, llvm::SlotIndex LeaveBefore)
• public void splitRegOutBlock(const SplitAnalysis::BlockInfo & BI, unsigned int IntvOut, llvm::SlotIndex EnterAfter)
• public void splitSingleBlock(const SplitAnalysis::BlockInfo & BI)
• private bool transferValues()
• public void useIntv(llvm::SlotIndex Start, llvm::SlotIndex End)
• public void useIntv(const llvm::MachineBasicBlock & MBB)

Methods

¶SplitEditor(llvm::SplitAnalysis& SA,
            llvm::LiveIntervals& LIS,
            llvm::VirtRegMap& VRM,
            llvm::MachineDominatorTree& MDT,
            llvm::MachineBlockFrequencyInfo& MBFI,
            llvm::VirtRegAuxInfo& VRAI)

Description

Create a new SplitEditor for editing the LiveInterval analyzed by SA. Newly created intervals will be appended to newIntervals.

Declared at: llvm/lib/CodeGen/SplitKit.h:438

Parameters

llvm::SplitAnalysis& SA

llvm::LiveIntervals& LIS

llvm::VirtRegMap& VRM

llvm::MachineDominatorTree& MDT

llvm::MachineBlockFrequencyInfo& MBFI

llvm::VirtRegAuxInfo& VRAI

¶void addDeadDef(llvm::LiveInterval& LI,
                llvm::VNInfo* VNI,
                bool Original)

Description

Add a segment to the interval LI for the value number VNI. If LI has subranges, corresponding segments will be added to them as well, but with newly created value numbers. If Original is true, dead def will only be added a subrange of LI if the corresponding subrange of the original interval has a def at this index. Otherwise, all subranges of LI will be updated.

Declared at: llvm/lib/CodeGen/SplitKit.h:354

Parameters

llvm::LiveInterval& LI

llvm::VNInfo* VNI

bool Original

¶llvm::SlotIndex buildCopy(
    llvm::Register FromReg,
    llvm::Register ToReg,
    llvm::LaneBitmask LaneMask,
    llvm::MachineBasicBlock& MBB,
    MachineBasicBlock::iterator InsertBefore,
    bool Late,
    unsigned int RegIdx)

Description

Add a copy instruction copying \p FromReg to \p ToReg before\p InsertBefore. This can be invoked with a \p LaneMask which may make it necessary to construct a sequence of copies to cover it exactly.

Declared at: llvm/lib/CodeGen/SplitKit.h:427

Parameters

llvm::Register FromReg

llvm::Register ToReg

llvm::LaneBitmask LaneMask

llvm::MachineBasicBlock& MBB

MachineBasicBlock::iterator InsertBefore

bool Late

unsigned int RegIdx

¶llvm::SlotIndex buildSingleSubRegCopy(
    llvm::Register FromReg,
    llvm::Register ToReg,
    llvm::MachineBasicBlock& MB,
    MachineBasicBlock::iterator InsertBefore,
    unsigned int SubIdx,
    llvm::LiveInterval& DestLI,
    bool Late,
    llvm::SlotIndex Def)

Declared at: llvm/lib/CodeGen/SplitKit.h:431

Parameters

llvm::Register FromReg

llvm::Register ToReg

llvm::MachineBasicBlock& MB

MachineBasicBlock::iterator InsertBefore

unsigned int SubIdx

llvm::LiveInterval& DestLI

bool Late

llvm::SlotIndex Def

¶void computeRedundantBackCopies(
    DenseSet<unsigned int>& NotToHoistSet,
    SmallVectorImpl<llvm::VNInfo*>& BackCopies)

Description

Find out all the backCopies dominated by others.

Declared at: llvm/lib/CodeGen/SplitKit.h:393

Parameters

DenseSet<unsigned int>& NotToHoistSet

SmallVectorImpl<llvm::VNInfo*>& BackCopies

¶unsigned int currentIntv() const

Description

currentIntv - Return the current interval index.

Declared at: llvm/lib/CodeGen/SplitKit.h:451

¶llvm::VNInfo* defFromParent(
    unsigned int RegIdx,
    const llvm::VNInfo* ParentVNI,
    llvm::SlotIndex UseIdx,
    llvm::MachineBasicBlock& MBB,
    MachineBasicBlock::iterator I)

Description

defFromParent - Define Reg from ParentVNI at UseIdx using either rematerialization or a COPY from parent. Return the new value.

Declared at: llvm/lib/CodeGen/SplitKit.h:379

Parameters

unsigned int RegIdx

const llvm::VNInfo* ParentVNI

llvm::SlotIndex UseIdx

llvm::MachineBasicBlock& MBB

MachineBasicBlock::iterator I

¶llvm::VNInfo* defValue(
    unsigned int RegIdx,
    const llvm::VNInfo* ParentVNI,
    llvm::SlotIndex Idx,
    bool Original)

Description

defValue - define a value in RegIdx from ParentVNI at Idx. Idx does not have to be ParentVNI->def, but it must be contained within ParentVNI's live range in ParentLI. The new value is added to the value map. The value being defined may either come from rematerialization (or an inserted copy), or it may be coming from the original interval. The parameter Original should be true in the latter case, otherwise it should be false. Return the new LI value.

Declared at: llvm/lib/CodeGen/SplitKit.h:364

Parameters

unsigned int RegIdx

const llvm::VNInfo* ParentVNI

llvm::SlotIndex Idx

bool Original

¶void deleteRematVictims()

Description

deleteRematVictims - Delete defs that are dead after rematerializing.

Declared at: llvm/lib/CodeGen/SplitKit.h:422

¶void dump() const

Description

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

Declared at: llvm/lib/CodeGen/SplitKit.h:510

¶llvm::SlotIndex enterIntvAfter(
    llvm::SlotIndex Idx)

Description

enterIntvAfter - Enter the open interval after the instruction at Idx. Return the beginning of the new live range.

Declared at: llvm/lib/CodeGen/SplitKit.h:463

Parameters

llvm::SlotIndex Idx

¶llvm::SlotIndex enterIntvAtEnd(
    llvm::MachineBasicBlock& MBB)

Description

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.

Declared at: llvm/lib/CodeGen/SplitKit.h:468

Parameters

llvm::MachineBasicBlock& MBB

¶llvm::SlotIndex enterIntvBefore(
    llvm::SlotIndex Idx)

Description

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.

Declared at: llvm/lib/CodeGen/SplitKit.h:459

Parameters

llvm::SlotIndex Idx

¶void extendPHIKillRanges()

Description

extendPHIKillRanges - Extend the ranges of all values killed by original parent PHIDefs.

Declared at: llvm/lib/CodeGen/SplitKit.h:416

¶void extendPHIRange(
    llvm::MachineBasicBlock& B,
    llvm::LiveIntervalCalc& LIC,
    llvm::LiveRange& LR,
    llvm::LaneBitmask LM,
    ArrayRef<llvm::SlotIndex> Undefs)

Description

Live range @p LR corresponding to the lane Mask @p LM has a live PHI def at the beginning of block @p B. Extend the range @p LR of all predecessor values that reach this def. If @p LR is a subrange, the array @p Undefs is the set of all locations where it is undefined via <def ,read-undef> in other subranges for the same register.

Declared at: llvm/lib/CodeGen/SplitKit.h:410

Parameters

llvm::MachineBasicBlock& B

llvm::LiveIntervalCalc& LIC

llvm::LiveRange& LR

llvm::LaneBitmask LM

ArrayRef<llvm::SlotIndex> Undefs

¶llvm::MachineBasicBlock* findShallowDominator(
    llvm::MachineBasicBlock* MBB,
    llvm::MachineBasicBlock* DefMBB)

Description

getShallowDominator - Returns the least busy dominator of MBB that is also dominated by DefMBB. Busy is measured by loop depth.

Declared at: llvm/lib/CodeGen/SplitKit.h:389

Parameters

llvm::MachineBasicBlock* MBB

llvm::MachineBasicBlock* DefMBB

¶void finish(SmallVectorImpl<unsigned int>* LRMap =
                nullptr)

Description

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

Declared at: llvm/lib/CodeGen/SplitKit.h:507

Parameters

SmallVectorImpl<unsigned int>* LRMap = nullptr

When 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.

¶void forceRecompute(unsigned int RegIdx,
                    const llvm::VNInfo& ParentVNI)

Description

forceRecompute - Force the live range of ParentVNI in RegIdx to be recomputed by LiveRangeCalc::extend regardless of the number of defs. This is used for values whose live range doesn't match RegAssign exactly. They could have rematerialized, or back-copies may have been moved.

Declared at: llvm/lib/CodeGen/SplitKit.h:371

Parameters

unsigned int RegIdx

const llvm::VNInfo& ParentVNI

¶void forceRecomputeVNI(
    const llvm::VNInfo& ParentVNI)

Description

Calls forceRecompute() on any affected regidx and on ParentVNI predecessors in case of a phi definition.

Declared at: llvm/lib/CodeGen/SplitKit.h:375

Parameters

const llvm::VNInfo& ParentVNI

¶llvm::LiveIntervalCalc& getLICalc(
    unsigned int RegIdx)

Description

getLICalc - Return the LICalc to use for RegIdx. In spill mode, the complement interval can overlap the other intervals, so it gets its own LICalc instance. When not in spill mode, all intervals can share one.

Declared at: llvm/lib/CodeGen/SplitKit.h:344

Parameters

unsigned int RegIdx

¶void hoistCopies()

Description

Hoist back-copies to the complement interval. It tries to hoist all the back-copies to one BB if it is beneficial, or else simply remove redundant backcopies dominated by others.

Declared at: llvm/lib/CodeGen/SplitKit.h:399

¶llvm::SlotIndex leaveIntvAfter(
    llvm::SlotIndex Idx)

Description

leaveIntvAfter - Leave the open interval after the instruction at Idx. Return the end of the live range.

Declared at: llvm/lib/CodeGen/SplitKit.h:478

Parameters

llvm::SlotIndex Idx

¶llvm::SlotIndex leaveIntvAtTop(
    llvm::MachineBasicBlock& MBB)

Description

leaveIntvAtTop - Leave the interval at the top of MBB. Add liveness from the MBB top to the copy. Return the end of the live range.

Declared at: llvm/lib/CodeGen/SplitKit.h:487

Parameters

llvm::MachineBasicBlock& MBB

¶llvm::SlotIndex leaveIntvBefore(
    llvm::SlotIndex Idx)

Description

leaveIntvBefore - Leave the open interval before the instruction at Idx. Return the end of the live range.

Declared at: llvm/lib/CodeGen/SplitKit.h:482

Parameters

llvm::SlotIndex Idx

¶unsigned int openIntv()

Description

Create a new virtual register and live interval. Return the interval index, starting from 1. Interval index 0 is the implicit complement interval.

Declared at: llvm/lib/CodeGen/SplitKit.h:448

¶void overlapIntv(llvm::SlotIndex Start,
                 llvm::SlotIndex End)

Description

overlapIntv - Indicate that all instructions in range should use the open interval if End does not have tied-def usage of the register and in this case compliment interval is used. 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.

Declared at: llvm/lib/CodeGen/SplitKit.h:500

Parameters

llvm::SlotIndex Start

llvm::SlotIndex End

¶void removeBackCopies(
    SmallVectorImpl<llvm::VNInfo*>& Copies)

Description

removeBackCopies - Remove the copy instructions that defines the values in the vector in the complement interval.

Declared at: llvm/lib/CodeGen/SplitKit.h:385

Parameters

SmallVectorImpl<llvm::VNInfo*>& Copies

¶void reset(
    llvm::LiveRangeEdit&,
    llvm::SplitEditor::ComplementSpillMode =
        SM_Partition)

Description

reset - Prepare for a new split.

Declared at: llvm/lib/CodeGen/SplitKit.h:443

Parameters

llvm::LiveRangeEdit&

llvm::SplitEditor::ComplementSpillMode = SM_Partition

¶void rewriteAssigned(bool ExtendRanges)

Description

rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers.

Declared at: llvm/lib/CodeGen/SplitKit.h:419

Parameters

bool ExtendRanges

¶void selectIntv(unsigned int Idx)

Description

selectIntv - Select a previously opened interval index.

Declared at: llvm/lib/CodeGen/SplitKit.h:454

Parameters

unsigned int Idx

¶void splitLiveThroughBlock(
    unsigned int MBBNum,
    unsigned int IntvIn,
    llvm::SlotIndex LeaveBefore,
    unsigned int IntvOut,
    llvm::SlotIndex EnterAfter)

Description

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.

Declared at: llvm/lib/CodeGen/SplitKit.h:528

Parameters

unsigned int MBBNum

Block number.

unsigned int IntvIn

Interval index entering the block.

llvm::SlotIndex LeaveBefore

When set, leave IntvIn before this point.

unsigned int IntvOut

Interval index leaving the block.

llvm::SlotIndex EnterAfter

When set, enter IntvOut after this point.

¶void splitRegInBlock(
    const SplitAnalysis::BlockInfo& BI,
    unsigned int IntvIn,
    llvm::SlotIndex LeaveBefore)

Description

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.

Declared at: llvm/lib/CodeGen/SplitKit.h:540

Parameters

const SplitAnalysis::BlockInfo& BI

Block descriptor.

unsigned int IntvIn

Interval index entering the block. Not 0.

llvm::SlotIndex LeaveBefore

When set, leave IntvIn before this point.

¶void splitRegOutBlock(
    const SplitAnalysis::BlockInfo& BI,
    unsigned int IntvOut,
    llvm::SlotIndex EnterAfter)

Description

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.

Declared at: llvm/lib/CodeGen/SplitKit.h:552

Parameters

const SplitAnalysis::BlockInfo& BI

Block descriptor.

unsigned int IntvOut

Interval index leaving the block.

llvm::SlotIndex EnterAfter

When set, enter IntvOut after this point.

¶void splitSingleBlock(
    const SplitAnalysis::BlockInfo& BI)

Description

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().

Declared at: llvm/lib/CodeGen/SplitKit.h:517

Parameters

const SplitAnalysis::BlockInfo& BI

¶bool transferValues()

Description

transferValues - Transfer values to the new ranges. Return true if any ranges were skipped.

Declared at: llvm/lib/CodeGen/SplitKit.h:403

¶void useIntv(llvm::SlotIndex Start,
             llvm::SlotIndex End)

Description

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

Declared at: llvm/lib/CodeGen/SplitKit.h:474

Parameters

llvm::SlotIndex Start

llvm::SlotIndex End

¶void useIntv(const llvm::MachineBasicBlock& MBB)

Description

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

Declared at: llvm/lib/CodeGen/SplitKit.h:471

Parameters

const llvm::MachineBasicBlock& MBB