class MachineDominatorTree

Declaration

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

Description

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:51

Inherits from: MachineFunctionPass

Member Variables

private SmallVector< llvm::MachineDominatorTree::CriticalEdge, 32> CriticalEdgesToSplit

Pile up all the critical edges to be split. The splitting of a critical edge is local and thus, it is possible to apply several of those changes at the same time.

private SmallSet<llvm::MachineBasicBlock*, 32> NewBBs

Remember all the basic blocks that are inserted during edge splitting. Invariant: NewBBs == all the basic blocks contained in the NewBB field of all the elements of CriticalEdgesToSplit. I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs such as BB == elt.NewBB.

private std::unique_ptr<MachineDomTree> DT

The DominatorTreeBase that is used to compute a normal dominator tree.

public static char ID

Method Overview

• public MachineDominatorTree()
• public MachineDominatorTree(llvm::MachineFunction & MF)
• public llvm::MachineDomTreeNode * addNewBlock(llvm::MachineBasicBlock * BB, llvm::MachineBasicBlock * DomBB)
• private void applySplitCriticalEdges() const
• public void calculate(llvm::MachineFunction & F)
• public void changeImmediateDominator(llvm::MachineDomTreeNode * N, llvm::MachineDomTreeNode * NewIDom)
• public void changeImmediateDominator(llvm::MachineBasicBlock * N, llvm::MachineBasicBlock * NewIDom)
• public bool dominates(const llvm::MachineInstr * A, const llvm::MachineInstr * B) const
• public bool dominates(const llvm::MachineDomTreeNode * A, const llvm::MachineDomTreeNode * B) const
• public bool dominates(const llvm::MachineBasicBlock * A, const llvm::MachineBasicBlock * B) const
• public void eraseNode(llvm::MachineBasicBlock * BB)
• public llvm::MachineBasicBlock * findNearestCommonDominator(llvm::MachineBasicBlock * A, llvm::MachineBasicBlock * B)
• public void getAnalysisUsage(llvm::AnalysisUsage & AU) const
• public llvm::MachineDomTree & getBase()
• public void getDescendants(llvm::MachineBasicBlock * A, SmallVectorImpl<llvm::MachineBasicBlock *> & Result)
• public llvm::MachineDomTreeNode * getNode(llvm::MachineBasicBlock * BB) const
• public llvm::MachineBasicBlock * getRoot() const
• public llvm::MachineDomTreeNode * getRootNode() const
• public bool isReachableFromEntry(const llvm::MachineBasicBlock * A)
• public void print(llvm::raw_ostream & OS, const llvm::Module *) const
• public bool properlyDominates(const llvm::MachineDomTreeNode * A, const llvm::MachineDomTreeNode * B) const
• public bool properlyDominates(const llvm::MachineBasicBlock * A, const llvm::MachineBasicBlock * B) const
• public void recordSplitCriticalEdge(llvm::MachineBasicBlock * FromBB, llvm::MachineBasicBlock * ToBB, llvm::MachineBasicBlock * NewBB)
• public void releaseMemory()
• public bool runOnMachineFunction(llvm::MachineFunction & F)
• public void splitBlock(llvm::MachineBasicBlock * NewBB)
• public void verifyAnalysis() const

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

¶MachineDominatorTree()

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:86

¶MachineDominatorTree(llvm::MachineFunction& MF)

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:87

Parameters

llvm::MachineFunction& MF

¶llvm::MachineDomTreeNode* addNewBlock(
    llvm::MachineBasicBlock* BB,
    llvm::MachineBasicBlock* DomBB)

Description

addNewBlock - Add a new node to the dominator tree information. This creates a new node as a child of DomBB dominator node,linking it into the children list of the immediate dominator.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:182

Parameters

llvm::MachineBasicBlock* BB

llvm::MachineBasicBlock* DomBB

¶void applySplitCriticalEdges() const

Description

Apply all the recorded critical edges to the DT. This updates the underlying DT information in a way that uses the fast query path of DT as much as possible.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:81

¶void calculate(llvm::MachineFunction& F)

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

Parameters

llvm::MachineFunction& F

¶void changeImmediateDominator(
    llvm::MachineDomTreeNode* N,
    llvm::MachineDomTreeNode* NewIDom)

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:197

Parameters

llvm::MachineDomTreeNode* N

llvm::MachineDomTreeNode* NewIDom

¶void changeImmediateDominator(
    llvm::MachineBasicBlock* N,
    llvm::MachineBasicBlock* NewIDom)

Description

changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:191

Parameters

llvm::MachineBasicBlock* N

llvm::MachineBasicBlock* NewIDom

¶bool dominates(const llvm::MachineInstr* A,
               const llvm::MachineInstr* B) const

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:133

Parameters

const llvm::MachineInstr* A

const llvm::MachineInstr* B

¶bool dominates(
    const llvm::MachineDomTreeNode* A,
    const llvm::MachineDomTreeNode* B) const

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:114

Parameters

const llvm::MachineDomTreeNode* A

const llvm::MachineDomTreeNode* B

¶bool dominates(
    const llvm::MachineBasicBlock* A,
    const llvm::MachineBasicBlock* B) const

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

Parameters

const llvm::MachineBasicBlock* A

const llvm::MachineBasicBlock* B

¶void eraseNode(llvm::MachineBasicBlock* BB)

Description

eraseNode - Removes a node from the dominator tree. Block must not dominate any other blocks. Removes node from its immediate dominator's children list. Deletes dominator node associated with basic block BB.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:206

Parameters

llvm::MachineBasicBlock* BB

¶llvm::MachineBasicBlock*
findNearestCommonDominator(
    llvm::MachineBasicBlock* A,
    llvm::MachineBasicBlock* B)

Description

findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B. If there is no such block then return NULL.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:160

Parameters

llvm::MachineBasicBlock* A

llvm::MachineBasicBlock* B

¶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/MachineDominators.h:98

Parameters

llvm::AnalysisUsage& AU

¶llvm::MachineDomTree& getBase()

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

¶void getDescendants(
    llvm::MachineBasicBlock* A,
    SmallVectorImpl<llvm::MachineBasicBlock*>&
        Result)

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

Parameters

llvm::MachineBasicBlock* A

SmallVectorImpl<llvm::MachineBasicBlock*>& Result

¶llvm::MachineDomTreeNode* getNode(
    llvm::MachineBasicBlock* BB) const

Description

getNode - return the (Post)DominatorTree node for the specified basic block. This is the same as using operator[] on this class.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:174

Parameters

llvm::MachineBasicBlock* BB

¶llvm::MachineBasicBlock* getRoot() const

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:100

¶llvm::MachineDomTreeNode* getRootNode() const

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:105

¶bool isReachableFromEntry(
    const llvm::MachineBasicBlock* A)

Description

isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it.

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

Parameters

const llvm::MachineBasicBlock* A

¶void print(llvm::raw_ostream& OS,
           const llvm::Module*) const

Description

print - Print out the internal state of the pass. This is called by Analyze to print out the contents of an analysis. Otherwise it is not necessary to implement this method. Beware that the module pointer MAY be null. This automatically forwards to a virtual function that does not provide the Module* in case the analysis doesn't need it it can just be ignored.

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

Parameters

llvm::raw_ostream& OS

const llvm::Module*

¶bool properlyDominates(
    const llvm::MachineDomTreeNode* A,
    const llvm::MachineDomTreeNode* B) const

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:146

Parameters

const llvm::MachineDomTreeNode* A

const llvm::MachineDomTreeNode* B

¶bool properlyDominates(
    const llvm::MachineBasicBlock* A,
    const llvm::MachineBasicBlock* B) const

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:152

Parameters

const llvm::MachineBasicBlock* A

const llvm::MachineBasicBlock* B

¶void recordSplitCriticalEdge(
    llvm::MachineBasicBlock* FromBB,
    llvm::MachineBasicBlock* ToBB,
    llvm::MachineBasicBlock* NewBB)

Description

Record that the critical edge (FromBB, ToBB) has been split with NewBB. This is best to use this method instead of directly update the underlying information, because this helps mitigating the number of time the DT information is invalidated.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:243

Parameters

llvm::MachineBasicBlock* FromBB

llvm::MachineBasicBlock* ToBB

llvm::MachineBasicBlock* NewBB

¶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/MachineDominators.h:225

¶bool runOnMachineFunction(
    llvm::MachineFunction& F)

Description

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

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:110

Parameters

llvm::MachineFunction& F

¶void splitBlock(llvm::MachineBasicBlock* NewBB)

Description

splitBlock - BB is split and now it has one successor. Update dominator tree to reflect this change.

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

Parameters

llvm::MachineBasicBlock* NewBB

¶void verifyAnalysis() const

Description

verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis information.

Declared at: llvm/include/llvm/CodeGen/MachineDominators.h:227