class TailDuplicator

Declaration

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

Description

Utility class to perform tail duplication.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:39

Member Variables

private const llvm::TargetInstrInfo* TII

private const llvm::TargetRegisterInfo* TRI

private const llvm::MachineBranchProbabilityInfo* MBPI

private const llvm::MachineModuleInfo* MMI

private llvm::MachineRegisterInfo* MRI

private llvm::MachineFunction* MF

private llvm::MBFIWrapper* MBFI

private llvm::ProfileSummaryInfo* PSI

private bool PreRegAlloc

private bool LayoutMode

private unsigned int TailDupSize

private SmallVector<llvm::Register, 16> SSAUpdateVRs

private DenseMap<llvm::Register, llvm::TailDuplicator::AvailableValsTy> SSAUpdateVals

Method Overview

• private void addSSAUpdateEntry(llvm::Register OrigReg, llvm::Register NewReg, llvm::MachineBasicBlock * BB)
• private void appendCopies(llvm::MachineBasicBlock * MBB, SmallVectorImpl<std::pair<Register, RegSubRegPair>> & CopyInfos, SmallVectorImpl<llvm::MachineInstr *> & Copies)
• private bool canCompletelyDuplicateBB(llvm::MachineBasicBlock & BB)
• public bool canTailDuplicate(llvm::MachineBasicBlock * TailBB, llvm::MachineBasicBlock * PredBB)
• private void duplicateInstruction(llvm::MachineInstr * MI, llvm::MachineBasicBlock * TailBB, llvm::MachineBasicBlock * PredBB, DenseMap<llvm::Register, llvm::TailDuplicator::RegSubRegPair> & LocalVRMap, const DenseSet<llvm::Register> & UsedByPhi)
• private bool duplicateSimpleBB(llvm::MachineBasicBlock * TailBB, SmallVectorImpl<llvm::MachineBasicBlock *> & TDBBs, const DenseSet<llvm::Register> & RegsUsedByPhi, SmallVectorImpl<llvm::MachineInstr *> & Copies)
• public void initMF(llvm::MachineFunction & MF, bool PreRegAlloc, const llvm::MachineBranchProbabilityInfo * MBPI, llvm::MBFIWrapper * MBFI, llvm::ProfileSummaryInfo * PSI, bool LayoutMode, unsigned int TailDupSize = 0)
• public static bool isSimpleBB(llvm::MachineBasicBlock * TailBB)
• private void processPHI(llvm::MachineInstr * MI, llvm::MachineBasicBlock * TailBB, llvm::MachineBasicBlock * PredBB, DenseMap<llvm::Register, llvm::TailDuplicator::RegSubRegPair> & LocalVRMap, SmallVectorImpl<std::pair<Register, RegSubRegPair>> & Copies, const DenseSet<llvm::Register> & UsedByPhi, bool Remove)
• private void removeDeadBlock(llvm::MachineBasicBlock * MBB, function_ref<void (llvm::MachineBasicBlock *)> * RemovalCallback = nullptr)
• public bool shouldTailDuplicate(bool IsSimple, llvm::MachineBasicBlock & TailBB)
• private bool tailDuplicate(bool IsSimple, llvm::MachineBasicBlock * TailBB, llvm::MachineBasicBlock * ForcedLayoutPred, SmallVectorImpl<llvm::MachineBasicBlock *> & TDBBs, SmallVectorImpl<llvm::MachineInstr *> & Copies, SmallVectorImpl<llvm::MachineBasicBlock *> * CandidatePtr)
• public bool tailDuplicateAndUpdate(bool IsSimple, llvm::MachineBasicBlock * MBB, llvm::MachineBasicBlock * ForcedLayoutPred, SmallVectorImpl<llvm::MachineBasicBlock *> * DuplicatedPreds = nullptr, function_ref<void (llvm::MachineBasicBlock *)> * RemovalCallback = nullptr, SmallVectorImpl<llvm::MachineBasicBlock *> * CandidatePtr = nullptr)
• public bool tailDuplicateBlocks()
• private void updateSuccessorsPHIs(llvm::MachineBasicBlock * FromBB, bool isDead, SmallVectorImpl<llvm::MachineBasicBlock *> & TDBBs, SmallSetVector<llvm::MachineBasicBlock *, 8> & Succs)

Methods

¶void addSSAUpdateEntry(
    llvm::Register OrigReg,
    llvm::Register NewReg,
    llvm::MachineBasicBlock* BB)

Description

Add a definition and source virtual registers pair for SSA update.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:101

Parameters

llvm::Register OrigReg

llvm::Register NewReg

llvm::MachineBasicBlock* BB

¶void appendCopies(
    llvm::MachineBasicBlock* MBB,
    SmallVectorImpl<
        std::pair<Register, RegSubRegPair>>&
        CopyInfos,
    SmallVectorImpl<llvm::MachineInstr*>& Copies)

Description

At the end of the block \p MBB generate COPY instructions between registers described by \p CopyInfos. Append resulting instructions to \p Copies.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:126

Parameters

llvm::MachineBasicBlock* MBB

SmallVectorImpl< std::pair<Register, RegSubRegPair>>& CopyInfos

SmallVectorImpl<llvm::MachineInstr*>& Copies

¶bool canCompletelyDuplicateBB(
    llvm::MachineBasicBlock& BB)

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:115

Parameters

llvm::MachineBasicBlock& BB

¶bool canTailDuplicate(
    llvm::MachineBasicBlock* TailBB,
    llvm::MachineBasicBlock* PredBB)

Description

Returns true if TailBB can successfully be duplicated into PredBB

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:82

Parameters

llvm::MachineBasicBlock* TailBB

llvm::MachineBasicBlock* PredBB

¶void duplicateInstruction(
    llvm::MachineInstr* MI,
    llvm::MachineBasicBlock* TailBB,
    llvm::MachineBasicBlock* PredBB,
    DenseMap<llvm::Register,
             llvm::TailDuplicator::RegSubRegPair>&
        LocalVRMap,
    const DenseSet<llvm::Register>& UsedByPhi)

Description

Duplicate a TailBB instruction to PredBB and update the source operands due to earlier PHI translation.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:108

Parameters

llvm::MachineInstr* MI

llvm::MachineBasicBlock* TailBB

llvm::MachineBasicBlock* PredBB

DenseMap<llvm::Register, llvm::TailDuplicator::RegSubRegPair>& LocalVRMap

const DenseSet<llvm::Register>& UsedByPhi

¶bool duplicateSimpleBB(
    llvm::MachineBasicBlock* TailBB,
    SmallVectorImpl<llvm::MachineBasicBlock*>&
        TDBBs,
    const DenseSet<llvm::Register>& RegsUsedByPhi,
    SmallVectorImpl<llvm::MachineInstr*>& Copies)

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:116

Parameters

llvm::MachineBasicBlock* TailBB

SmallVectorImpl<llvm::MachineBasicBlock*>& TDBBs

const DenseSet<llvm::Register>& RegsUsedByPhi

SmallVectorImpl<llvm::MachineInstr*>& Copies

¶void initMF(
    llvm::MachineFunction& MF,
    bool PreRegAlloc,
    const llvm::MachineBranchProbabilityInfo*
        MBPI,
    llvm::MBFIWrapper* MBFI,
    llvm::ProfileSummaryInfo* PSI,
    bool LayoutMode,
    unsigned int TailDupSize = 0)

Description

Prepare to run on a specific machine function.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:71

Parameters

llvm::MachineFunction& MF

- Function that will be processed

bool PreRegAlloc

- true if used before register allocation

const llvm::MachineBranchProbabilityInfo* MBPI

- Branch Probability Info. Used to propagate correct probabilities when modifying the CFG.

llvm::MBFIWrapper* MBFI

llvm::ProfileSummaryInfo* PSI

bool LayoutMode

- When true, don't use the existing layout to make decisions.

unsigned int TailDupSize = 0

- Maxmimum size of blocks to tail-duplicate. Zero default implies using the command line value TailDupSize.

¶static bool isSimpleBB(
    llvm::MachineBasicBlock* TailBB)

Description

True if this BB has only one unconditional jump.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:78

Parameters

llvm::MachineBasicBlock* TailBB

¶void processPHI(
    llvm::MachineInstr* MI,
    llvm::MachineBasicBlock* TailBB,
    llvm::MachineBasicBlock* PredBB,
    DenseMap<llvm::Register,
             llvm::TailDuplicator::RegSubRegPair>&
        LocalVRMap,
    SmallVectorImpl<
        std::pair<Register, RegSubRegPair>>&
        Copies,
    const DenseSet<llvm::Register>& UsedByPhi,
    bool Remove)

Description

Process PHI node in TailBB by turning it into a copy in PredBB. Remember the source register that's contributed by PredBB and update SSA update map.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:103

Parameters

llvm::MachineInstr* MI

llvm::MachineBasicBlock* TailBB

llvm::MachineBasicBlock* PredBB

DenseMap<llvm::Register, llvm::TailDuplicator::RegSubRegPair>& LocalVRMap

SmallVectorImpl< std::pair<Register, RegSubRegPair>>& Copies

const DenseSet<llvm::Register>& UsedByPhi

bool Remove

¶void removeDeadBlock(
    llvm::MachineBasicBlock* MBB,
    function_ref<void(llvm::MachineBasicBlock*)>*
        RemovalCallback = nullptr)

Description

Remove the specified dead machine basic block from the function, updating the CFG.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:130

Parameters

llvm::MachineBasicBlock* MBB

function_ref<void(llvm::MachineBasicBlock*)>* RemovalCallback = nullptr

¶bool shouldTailDuplicate(
    bool IsSimple,
    llvm::MachineBasicBlock& TailBB)

Description

Determine if it is profitable to duplicate this block.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:79

Parameters

bool IsSimple

llvm::MachineBasicBlock& TailBB

¶bool tailDuplicate(
    bool IsSimple,
    llvm::MachineBasicBlock* TailBB,
    llvm::MachineBasicBlock* ForcedLayoutPred,
    SmallVectorImpl<llvm::MachineBasicBlock*>&
        TDBBs,
    SmallVectorImpl<llvm::MachineInstr*>& Copies,
    SmallVectorImpl<llvm::MachineBasicBlock*>*
        CandidatePtr)

Description

If it is profitable, duplicate TailBB's contents in each of its predecessors.\p IsSimple result of isSimpleBB\p TailBB Block to be duplicated.\p ForcedLayoutPred When non-null, use this block as the layout predecessor instead of the previous block in MF's order.\p TDBBs A vector to keep track of all blocks tail-duplicated into.\p Copies A vector of copy instructions inserted. Used later to walk all the inserted copies and remove redundant ones.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:120

Parameters

bool IsSimple

llvm::MachineBasicBlock* TailBB

llvm::MachineBasicBlock* ForcedLayoutPred

SmallVectorImpl<llvm::MachineBasicBlock*>& TDBBs

SmallVectorImpl<llvm::MachineInstr*>& Copies

SmallVectorImpl<llvm::MachineBasicBlock*>* CandidatePtr

¶bool tailDuplicateAndUpdate(
    bool IsSimple,
    llvm::MachineBasicBlock* MBB,
    llvm::MachineBasicBlock* ForcedLayoutPred,
    SmallVectorImpl<llvm::MachineBasicBlock*>*
        DuplicatedPreds = nullptr,
    function_ref<void(llvm::MachineBasicBlock*)>*
        RemovalCallback = nullptr,
    SmallVectorImpl<llvm::MachineBasicBlock*>*
        CandidatePtr = nullptr)

Description

Tail duplicate a single basic block into its predecessors, and then clean up. If \p DuplicatePreds is not null, it will be updated to contain the list of predecessors that received a copy of \p MBB. If \p RemovalCallback is non-null. It will be called before MBB is deleted. If \p CandidatePtr is not null, duplicate into these blocks only.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:91

Parameters

bool IsSimple

llvm::MachineBasicBlock* MBB

llvm::MachineBasicBlock* ForcedLayoutPred

SmallVectorImpl<llvm::MachineBasicBlock*>* DuplicatedPreds = nullptr

function_ref<void(llvm::MachineBasicBlock*)>* RemovalCallback = nullptr

SmallVectorImpl<llvm::MachineBasicBlock*>* CandidatePtr = nullptr

¶bool tailDuplicateBlocks()

Description

Look for small blocks that are unconditionally branched to and do not fall through. Tail-duplicate their instructions into their predecessors to eliminate (dynamic) branches.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:77

¶void updateSuccessorsPHIs(
    llvm::MachineBasicBlock* FromBB,
    bool isDead,
    SmallVectorImpl<llvm::MachineBasicBlock*>&
        TDBBs,
    SmallSetVector<llvm::MachineBasicBlock*, 8>&
        Succs)

Description

After FromBB is tail duplicated into its predecessor blocks, the successors have gained new predecessors. Update the PHI instructions in them accordingly.

Declared at: llvm/include/llvm/CodeGen/TailDuplicator.h:112

Parameters

llvm::MachineBasicBlock* FromBB

bool isDead

SmallVectorImpl<llvm::MachineBasicBlock*>& TDBBs

SmallSetVector<llvm::MachineBasicBlock*, 8>& Succs