class ReachingDefAnalysis

Declaration

class ReachingDefAnalysis : public MachineFunctionPass { /* full declaration omitted */ };

Description

This class provides the reaching def analysis.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:69

Inherits from: MachineFunctionPass

Member Variables

private llvm::MachineFunction* MF

private const llvm::TargetRegisterInfo* TRI

private LoopTraversal::TraversalOrder TraversedMBBOrder

private unsigned int NumRegUnits

private llvm::ReachingDefAnalysis::LiveRegsDefInfo LiveRegs

private llvm::ReachingDefAnalysis::OutRegsInfoMap MBBOutRegsInfos

private int CurInstr

Current instruction number. The first instruction in each basic block is 0.

private DenseMap<llvm::MachineInstr*, int> InstIds

Maps instructions to their instruction Ids, relative to the beginning of their basic blocks.

private llvm::ReachingDefAnalysis::MBBReachingDefsInfo MBBReachingDefs

private const int ReachingDefDefaultVal = -(1 << 20)

Default values are 'nothing happened a long time ago'.

public static char ID

Method Overview

• public ReachingDefAnalysis()
• public void collectKilledOperands(llvm::MachineInstr * MI, llvm::ReachingDefAnalysis::InstSet & Dead) const
• private void enterBasicBlock(llvm::MachineBasicBlock * MBB)
• public void getAnalysisUsage(llvm::AnalysisUsage & AU) const
• public int getClearance(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• public void getGlobalReachingDefs(llvm::MachineInstr * MI, llvm::MCRegister PhysReg, llvm::ReachingDefAnalysis::InstSet & Defs) const
• public void getGlobalUses(llvm::MachineInstr * MI, llvm::MCRegister PhysReg, llvm::ReachingDefAnalysis::InstSet & Uses) const
• private llvm::MachineInstr * getInstFromId(llvm::MachineBasicBlock * MBB, int InstId) const
• public bool getLiveInUses(llvm::MachineBasicBlock * MBB, llvm::MCRegister PhysReg, llvm::ReachingDefAnalysis::InstSet & Uses) const
• public void getLiveOuts(llvm::MachineBasicBlock * MBB, llvm::MCRegister PhysReg, llvm::ReachingDefAnalysis::InstSet & Defs, llvm::ReachingDefAnalysis::BlockSet & VisitedBBs) const
• public void getLiveOuts(llvm::MachineBasicBlock * MBB, llvm::MCRegister PhysReg, llvm::ReachingDefAnalysis::InstSet & Defs) const
• public llvm::MachineInstr * getLocalLiveOutMIDef(llvm::MachineBasicBlock * MBB, llvm::MCRegister PhysReg) const
• public llvm::MachineInstr * getMIOperand(llvm::MachineInstr * MI, unsigned int Idx) const
• public llvm::MachineInstr * getMIOperand(llvm::MachineInstr * MI, llvm::MachineOperand & MO) const
• public int getReachingDef(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• private llvm::MachineInstr * getReachingLocalMIDef(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• public void getReachingLocalUses(llvm::MachineInstr * MI, llvm::MCRegister PhysReg, llvm::ReachingDefAnalysis::InstSet & Uses) const
• public llvm::MachineFunctionProperties getRequiredProperties() const
• public llvm::MachineInstr * getUniqueReachingMIDef(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• public bool hasLocalDefBefore(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• public bool hasSameReachingDef(llvm::MachineInstr * A, llvm::MachineInstr * B, llvm::MCRegister PhysReg) const
• public void init()
• public bool isReachingDefLiveOut(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• public bool isRegDefinedAfter(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• public bool isRegUsedAfter(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• public bool isSafeToDefRegAt(llvm::MachineInstr * MI, llvm::MCRegister PhysReg, llvm::ReachingDefAnalysis::InstSet & Ignore) const
• public bool isSafeToDefRegAt(llvm::MachineInstr * MI, llvm::MCRegister PhysReg) const
• private template <typename Iterator>bool isSafeToMove(llvm::MachineInstr * From, llvm::MachineInstr * To) const
• public bool isSafeToMoveBackwards(llvm::MachineInstr * From, llvm::MachineInstr * To) const
• public bool isSafeToMoveForwards(llvm::MachineInstr * From, llvm::MachineInstr * To) const
• public bool isSafeToRemove(llvm::MachineInstr * MI, llvm::ReachingDefAnalysis::InstSet & ToRemove) const
• public bool isSafeToRemove(llvm::MachineInstr * MI, llvm::ReachingDefAnalysis::InstSet & ToRemove, llvm::ReachingDefAnalysis::InstSet & Ignore) const
• private bool isSafeToRemove(llvm::MachineInstr * MI, llvm::ReachingDefAnalysis::InstSet & Visited, llvm::ReachingDefAnalysis::InstSet & ToRemove, llvm::ReachingDefAnalysis::InstSet & Ignore) const
• private void leaveBasicBlock(llvm::MachineBasicBlock * MBB)
• private void processBasicBlock(const LoopTraversal::TraversedMBBInfo & TraversedMBB)
• private void processDefs(llvm::MachineInstr *)
• public void releaseMemory()
• private void reprocessBasicBlock(llvm::MachineBasicBlock * MBB)
• public void reset()
• public bool runOnMachineFunction(llvm::MachineFunction & MF)
• public void traverse()

Inherited from MachineFunctionPass:

• public doInitialization
• protected getAnalysisUsage
• protected getClearedProperties
• protected getRequiredProperties
• protected getSetProperties
• protected runOnMachineFunction

Inherited from FunctionPass:

• public assignPassManager
• public createPrinterPass
• public getPotentialPassManagerType
• public runOnFunction
• protected skipFunction

Inherited from Pass:

• public assignPassManager
• public createPass
• public createPrinterPass
• public doFinalization
• public doInitialization
• public dump
• public dumpPassStructure
• public getAdjustedAnalysisPointer
• public getAnalysis
• public getAnalysis
• public getAnalysisID
• public getAnalysisID
• public getAnalysisIfAvailable
• public getAnalysisUsage
• public getAsImmutablePass
• public getAsPMDataManager
• public getPassID
• public getPassKind
• public getPassName
• public getPotentialPassManagerType
• public getResolver
• public lookupPassInfo
• public lookupPassInfo
• public mustPreserveAnalysisID
• public preparePassManager
• public print
• public releaseMemory
• public setResolver
• public verifyAnalysis

Methods

¶ReachingDefAnalysis()

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:113

¶void collectKilledOperands(
    llvm::MachineInstr* MI,
    llvm::ReachingDefAnalysis::InstSet& Dead)
    const

Description

Assuming MI is dead, recursively search the incoming operands which are killed by MI and collect those that would become dead.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:220

Parameters

llvm::MachineInstr* MI

llvm::ReachingDefAnalysis::InstSet& Dead

¶void enterBasicBlock(llvm::MachineBasicBlock* MBB)

Description

Set up LiveRegs by merging predecessor live-out values.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:244

Parameters

llvm::MachineBasicBlock* MBB

¶void getAnalysisUsage(
    llvm::AnalysisUsage& AU) const

Description

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this. For MachineFunctionPasses, calling AU.preservesCFG() indicates that the pass does not modify the MachineBasicBlock CFG.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:118

Parameters

llvm::AnalysisUsage& AU

¶int getClearance(llvm::MachineInstr* MI,
                 llvm::MCRegister PhysReg) const

Description

Provides the clearance - the number of instructions since the closest reaching def instuction of PhysReg that reaches MI.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:183

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶void getGlobalReachingDefs(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg,
    llvm::ReachingDefAnalysis::InstSet& Defs)
    const

Description

Collect all possible definitions of the value stored in PhysReg, which is used by MI.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:209

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

llvm::ReachingDefAnalysis::InstSet& Defs

¶void getGlobalUses(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg,
    llvm::ReachingDefAnalysis::InstSet& Uses)
    const

Description

Collect the users of the value stored in PhysReg, which is defined by MI.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:205

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

llvm::ReachingDefAnalysis::InstSet& Uses

¶llvm::MachineInstr* getInstFromId(
    llvm::MachineBasicBlock* MBB,
    int InstId) const

Description

Provides the MI, from the given block, corresponding to the Id or a nullptr if the id does not refer to the block.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:271

Parameters

llvm::MachineBasicBlock* MBB

int InstId

¶bool getLiveInUses(
    llvm::MachineBasicBlock* MBB,
    llvm::MCRegister PhysReg,
    llvm::ReachingDefAnalysis::InstSet& Uses)
    const

Description

For the given block, collect the instructions that use the live-in value of the provided register. Return whether the value is still live on exit.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:200

Parameters

llvm::MachineBasicBlock* MBB

llvm::MCRegister PhysReg

llvm::ReachingDefAnalysis::InstSet& Uses

¶void getLiveOuts(
    llvm::MachineBasicBlock* MBB,
    llvm::MCRegister PhysReg,
    llvm::ReachingDefAnalysis::InstSet& Defs,
    llvm::ReachingDefAnalysis::BlockSet&
        VisitedBBs) const

Description

Search MBB for a definition of PhysReg and insert it into Defs. If no definition is found, recursively search the predecessor blocks for them.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:192

Parameters

llvm::MachineBasicBlock* MBB

llvm::MCRegister PhysReg

llvm::ReachingDefAnalysis::InstSet& Defs

llvm::ReachingDefAnalysis::BlockSet& VisitedBBs

¶void getLiveOuts(
    llvm::MachineBasicBlock* MBB,
    llvm::MCRegister PhysReg,
    llvm::ReachingDefAnalysis::InstSet& Defs)
    const

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:194

Parameters

llvm::MachineBasicBlock* MBB

llvm::MCRegister PhysReg

llvm::ReachingDefAnalysis::InstSet& Defs

¶llvm::MachineInstr* getLocalLiveOutMIDef(
    llvm::MachineBasicBlock* MBB,
    llvm::MCRegister PhysReg) const

Description

Return the local MI that produces the live out value for PhysReg, or nullptr for a non-live out or non-local def.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:154

Parameters

llvm::MachineBasicBlock* MBB

llvm::MCRegister PhysReg

¶llvm::MachineInstr* getMIOperand(
    llvm::MachineInstr* MI,
    unsigned int Idx) const

Description

If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it. Otherwise return null.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:164

Parameters

llvm::MachineInstr* MI

unsigned int Idx

¶llvm::MachineInstr* getMIOperand(
    llvm::MachineInstr* MI,
    llvm::MachineOperand& MO) const

Description

If a single MachineInstr creates the reaching definition, for MIs MO, then return it. Otherwise return null.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:168

Parameters

llvm::MachineInstr* MI

llvm::MachineOperand& MO

¶int getReachingDef(llvm::MachineInstr* MI,
                   llvm::MCRegister PhysReg) const

Description

Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI, relative to the begining of MI's basic block.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:142

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶llvm::MachineInstr* getReachingLocalMIDef(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg) const

Description

Provides the instruction of the closest reaching def instruction of PhysReg that reaches MI, relative to the begining of MI's basic block.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:275

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶void getReachingLocalUses(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg,
    llvm::ReachingDefAnalysis::InstSet& Uses)
    const

Description

Provides the uses, in the same block as MI, of register that MI defines. This does not consider live-outs.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:187

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

llvm::ReachingDefAnalysis::InstSet& Uses

¶llvm::MachineFunctionProperties
getRequiredProperties() const

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:125

¶llvm::MachineInstr* getUniqueReachingMIDef(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg) const

Description

If a single MachineInstr creates the reaching definition, then return it. Otherwise return null.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:159

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶bool hasLocalDefBefore(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg) const

Description

Provide whether the register has been defined in the same basic block as, and before, MI.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:172

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶bool hasSameReachingDef(
    llvm::MachineInstr* A,
    llvm::MachineInstr* B,
    llvm::MCRegister PhysReg) const

Description

Return whether A and B use the same def of PhysReg.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:145

Parameters

llvm::MachineInstr* A

llvm::MachineInstr* B

llvm::MCRegister PhysReg

¶void init()

Description

Initialize data structures.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:135

¶bool isReachingDefLiveOut(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg) const

Description

Return whether the reaching def for MI also is live out of its parent block.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:150

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶bool isRegDefinedAfter(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg) const

Description

Return whether the given register is defined after MI.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:179

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶bool isRegUsedAfter(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg) const

Description

Return whether the given register is used after MI, whether it's a local use or a live out.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:176

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶bool isSafeToDefRegAt(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg,
    llvm::ReachingDefAnalysis::InstSet& Ignore)
    const

Description

Return whether a MachineInstr could be inserted at MI and safely define the given register without affecting the program, ignoring any effects on the provided instructions.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:239

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

llvm::ReachingDefAnalysis::InstSet& Ignore

¶bool isSafeToDefRegAt(
    llvm::MachineInstr* MI,
    llvm::MCRegister PhysReg) const

Description

Return whether a MachineInstr could be inserted at MI and safely define the given register without affecting the program.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:234

Parameters

llvm::MachineInstr* MI

llvm::MCRegister PhysReg

¶template <typename Iterator>
bool isSafeToMove(llvm::MachineInstr* From,
                  llvm::MachineInstr* To) const

Description

Utility function for isSafeToMoveForwards/Backwards.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:261

Templates

Iterator

Parameters

llvm::MachineInstr* From

llvm::MachineInstr* To

¶bool isSafeToMoveBackwards(
    llvm::MachineInstr* From,
    llvm::MachineInstr* To) const

Description

Return whether From can be moved backwards to just after To.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:216

Parameters

llvm::MachineInstr* From

llvm::MachineInstr* To

¶bool isSafeToMoveForwards(
    llvm::MachineInstr* From,
    llvm::MachineInstr* To) const

Description

Return whether From can be moved forwards to just before To.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:213

Parameters

llvm::MachineInstr* From

llvm::MachineInstr* To

¶bool isSafeToRemove(
    llvm::MachineInstr* MI,
    llvm::ReachingDefAnalysis::InstSet& ToRemove)
    const

Description

Return whether removing this instruction will have no effect on the program, returning the redundant use-def chain.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:224

Parameters

llvm::MachineInstr* MI

llvm::ReachingDefAnalysis::InstSet& ToRemove

¶bool isSafeToRemove(
    llvm::MachineInstr* MI,
    llvm::ReachingDefAnalysis::InstSet& ToRemove,
    llvm::ReachingDefAnalysis::InstSet& Ignore)
    const

Description

Return whether removing this instruction will have no effect on the program, ignoring the possible effects on some instructions, returning the redundant use-def chain.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:229

Parameters

llvm::MachineInstr* MI

llvm::ReachingDefAnalysis::InstSet& ToRemove

llvm::ReachingDefAnalysis::InstSet& Ignore

¶bool isSafeToRemove(
    llvm::MachineInstr* MI,
    llvm::ReachingDefAnalysis::InstSet& Visited,
    llvm::ReachingDefAnalysis::InstSet& ToRemove,
    llvm::ReachingDefAnalysis::InstSet& Ignore)
    const

Description

Return whether removing this instruction will have no effect on the program, ignoring the possible effects on some instructions, returning the redundant use-def chain.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:266

Parameters

llvm::MachineInstr* MI

llvm::ReachingDefAnalysis::InstSet& Visited

llvm::ReachingDefAnalysis::InstSet& ToRemove

llvm::ReachingDefAnalysis::InstSet& Ignore

¶void leaveBasicBlock(llvm::MachineBasicBlock* MBB)

Description

Update live-out values.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:247

Parameters

llvm::MachineBasicBlock* MBB

¶void processBasicBlock(
    const LoopTraversal::TraversedMBBInfo&
        TraversedMBB)

Description

Process he given basic block.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:250

Parameters

const LoopTraversal::TraversedMBBInfo& TraversedMBB

¶void processDefs(llvm::MachineInstr*)

Description

Update def-ages for registers defined by MI. Also break dependencies on partial defs and undef uses.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:257

Parameters

llvm::MachineInstr*

¶void releaseMemory()

Description

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memory when it is no longer needed. The default behavior of passes is to hold onto memory for the entire duration of their lifetime (which is the entire compile time). For pipelined passes, this is not a big deal because that memory gets recycled every time the pass is invoked on another program unit. For IP passes, it is more important to free memory when it is unused. Optionally implement this function to release pass memory when it is no longer used.

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

¶void reprocessBasicBlock(
    llvm::MachineBasicBlock* MBB)

Description

Process block that is part of a loop again.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:253

Parameters

llvm::MachineBasicBlock* MBB

¶void reset()

Description

Re-run the analysis.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:132

¶bool runOnMachineFunction(
    llvm::MachineFunction& MF)

Description

runOnMachineFunction - This method must be overloaded to perform the desired machine code transformation or analysis.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:123

Parameters

llvm::MachineFunction& MF

¶void traverse()

Description

Traverse the machine function, mapping definitions.

Declared at: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h:138