LLVM 20.0.0git
Classes | Public Types | Public Member Functions | List of all members
llvm::MachineDominatorTree Class Reference

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

#include "llvm/CodeGen/MachineDominators.h"

Inheritance diagram for llvm::MachineDominatorTree:
Inheritance graph
[legend]

Public Types

using Base = DomTreeBase< MachineBasicBlock >
 
- Public Types inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
enum class  VerificationLevel { Fast , Basic , Full }
 
using NodeTrait = DomTreeNodeTraits< NodeT >
 
using NodeType = typename NodeTrait::NodeType
 
using NodePtr = typename NodeTrait::NodePtr
 
using ParentPtr = typename NodeTrait::ParentPtr
 
using ParentType = std::remove_pointer_t< ParentPtr >
 
using UpdateType = cfg::Update< NodePtr >
 
using UpdateKind = cfg::UpdateKind
 
using root_iterator = typename SmallVectorImpl< NodeT * >::iterator
 Iteration over roots.
 
using const_root_iterator = typename SmallVectorImpl< NodeT * >::const_iterator
 

Public Member Functions

 MachineDominatorTree ()=default
 
 MachineDominatorTree (MachineFunction &MF)
 
bool invalidate (MachineFunction &, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &)
 Handle invalidation explicitly.
 
MachineDominatorTreegetBase ()
 
MachineBasicBlockgetRoot () const
 
MachineDomTreeNodegetRootNode () const
 
void calculate (MachineFunction &F)
 
bool dominates (const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
 
void getDescendants (MachineBasicBlock *A, SmallVectorImpl< MachineBasicBlock * > &Result)
 
bool dominates (const MachineBasicBlock *A, const MachineBasicBlock *B) const
 
bool dominates (const MachineInstr *A, const MachineInstr *B) const
 
bool properlyDominates (const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
 
bool properlyDominates (const MachineBasicBlock *A, const MachineBasicBlock *B) const
 
MachineBasicBlockfindNearestCommonDominator (MachineBasicBlock *A, MachineBasicBlock *B)
 findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
 
MachineDomTreeNodeoperator[] (MachineBasicBlock *BB) const
 
MachineDomTreeNodegetNode (MachineBasicBlock *BB) const
 getNode - return the (Post)DominatorTree node for the specified basic block.
 
MachineDomTreeNodeaddNewBlock (MachineBasicBlock *BB, MachineBasicBlock *DomBB)
 addNewBlock - Add a new node to the dominator tree information.
 
void changeImmediateDominator (MachineBasicBlock *N, MachineBasicBlock *NewIDom)
 changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes.
 
void changeImmediateDominator (MachineDomTreeNode *N, MachineDomTreeNode *NewIDom)
 
void eraseNode (MachineBasicBlock *BB)
 eraseNode - Removes a node from the dominator tree.
 
void splitBlock (MachineBasicBlock *NewBB)
 splitBlock - BB is split and now it has one successor.
 
bool isReachableFromEntry (const MachineBasicBlock *A)
 isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it.
 
void recordSplitCriticalEdge (MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, MachineBasicBlock *NewBB)
 Record that the critical edge (FromBB, ToBB) has been split with NewBB.
 
- Public Member Functions inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
 DominatorTreeBase ()=default
 
 DominatorTreeBase (DominatorTreeBase &&Arg)
 
DominatorTreeBaseoperator= (DominatorTreeBase &&RHS)
 
 DominatorTreeBase (const DominatorTreeBase &)=delete
 
DominatorTreeBaseoperator= (const DominatorTreeBase &)=delete
 
root_iterator root_begin ()
 
const_root_iterator root_begin () const
 
root_iterator root_end ()
 
const_root_iterator root_end () const
 
size_t root_size () const
 
iterator_range< root_iteratorroots ()
 
iterator_range< const_root_iteratorroots () const
 
bool isPostDominator () const
 isPostDominator - Returns true if analysis based of postdoms
 
bool compare (const DominatorTreeBase &Other) const
 compare - Return false if the other dominator tree base matches this dominator tree base.
 
DomTreeNodeBase< NodeT > * getNode (const NodeT *BB) const
 getNode - return the (Post)DominatorTree node for the specified basic block.
 
DomTreeNodeBase< NodeT > * operator[] (const NodeT *BB) const
 See getNode.
 
DomTreeNodeBase< NodeT > * getRootNode ()
 getRootNode - This returns the entry node for the CFG of the function.
 
const DomTreeNodeBase< NodeT > * getRootNode () const
 
void getDescendants (NodeT *R, SmallVectorImpl< NodeT * > &Result) const
 Get all nodes dominated by R, including R itself.
 
bool properlyDominates (const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
 properlyDominates - Returns true iff A dominates B and A != B.
 
bool properlyDominates (const NodeT *A, const NodeT *B) const
 
bool isReachableFromEntry (const NodeT *A) const
 isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it.
 
bool isReachableFromEntry (const DomTreeNodeBase< NodeT > *A) const
 
bool dominates (const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
 dominates - Returns true iff A dominates B.
 
bool dominates (const NodeT *A, const NodeT *B) const
 
NodeT * getRoot () const
 
NodeT * findNearestCommonDominator (NodeT *A, NodeT *B) const
 Find nearest common dominator basic block for basic block A and B.
 
const NodeT * findNearestCommonDominator (const NodeT *A, const NodeT *B) const
 
bool isVirtualRoot (const DomTreeNodeBase< NodeT > *A) const
 
void applyUpdates (ArrayRef< UpdateType > Updates)
 Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch update on the tree.
 
void applyUpdates (ArrayRef< UpdateType > Updates, ArrayRef< UpdateType > PostViewUpdates)
 
void insertEdge (NodeT *From, NodeT *To)
 Inform the dominator tree about a CFG edge insertion and update the tree.
 
void deleteEdge (NodeT *From, NodeT *To)
 Inform the dominator tree about a CFG edge deletion and update the tree.
 
DomTreeNodeBase< NodeT > * addNewBlock (NodeT *BB, NodeT *DomBB)
 Add a new node to the dominator tree information.
 
DomTreeNodeBase< NodeT > * setNewRoot (NodeT *BB)
 Add a new node to the forward dominator tree and make it a new root.
 
void changeImmediateDominator (DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
 changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes.
 
void changeImmediateDominator (NodeT *BB, NodeT *NewBB)
 
void eraseNode (NodeT *BB)
 eraseNode - Removes a node from the dominator tree.
 
void splitBlock (NodeT *NewBB)
 splitBlock - BB is split and now it has one successor.
 
void print (raw_ostream &O) const
 print - Convert to human readable form
 
void updateDFSNumbers () const
 updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
 
void recalculate (ParentType &Func)
 recalculate - compute a dominator tree for the given function
 
void recalculate (ParentType &Func, ArrayRef< UpdateType > Updates)
 
template<typename T = NodeT>
std::enable_if_t< GraphHasNodeNumbers< T * >, void > updateBlockNumbers ()
 Update dominator tree after renumbering blocks.
 
bool verify (VerificationLevel VL=VerificationLevel::Full) const
 verify - checks if the tree is correct.
 
void reset ()
 

Additional Inherited Members

- Static Public Attributes inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
static constexpr bool IsPostDominator = IsPostDom
 
static constexpr UpdateKind Insert = UpdateKind::Insert
 
static constexpr UpdateKind Delete = UpdateKind::Delete
 
- Protected Types inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
using DomTreeNodeStorageTy = SmallVector< std::unique_ptr< DomTreeNodeBase< NodeT > > >
 
- Protected Member Functions inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
void addRoot (NodeT *BB)
 
DomTreeNodeBase< NodeT > * createNode (NodeT *BB, DomTreeNodeBase< NodeT > *IDom=nullptr)
 
template<class N >
void Split (typename GraphTraits< N >::NodeRef NewBB)
 
void addRoot (MachineBasicBlock *MBB)
 
- Protected Attributes inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
SmallVector< NodeT *, IsPostDom ? 4 :1 > Roots
 
DomTreeNodeStorageTy DomTreeNodes
 
std::conditional_t<!GraphHasNodeNumbers< NodeT * >, DenseMap< const NodeT *, unsigned >, std::tuple<> > NodeNumberMap
 
DomTreeNodeBase< NodeT > * RootNode = nullptr
 
ParentPtr Parent = nullptr
 
bool DFSInfoValid = false
 
unsigned int SlowQueries = 0
 
unsigned BlockNumberEpoch = 0
 

Detailed Description

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

Definition at line 75 of file MachineDominators.h.

Member Typedef Documentation

◆ Base

Definition at line 106 of file MachineDominators.h.

Constructor & Destructor Documentation

◆ MachineDominatorTree() [1/2]

llvm::MachineDominatorTree::MachineDominatorTree ( )
default

◆ MachineDominatorTree() [2/2]

llvm::MachineDominatorTree::MachineDominatorTree ( MachineFunction MF)
inlineexplicit

Definition at line 109 of file MachineDominators.h.

Member Function Documentation

◆ addNewBlock()

MachineDomTreeNode * llvm::MachineDominatorTree::addNewBlock ( MachineBasicBlock BB,
MachineBasicBlock DomBB 
)
inline

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.

Definition at line 204 of file MachineDominators.h.

Referenced by loadMBUFScalarOperandsFromVGPR().

◆ calculate()

void MachineDominatorTree::calculate ( MachineFunction F)

◆ changeImmediateDominator() [1/2]

void llvm::MachineDominatorTree::changeImmediateDominator ( MachineBasicBlock N,
MachineBasicBlock NewIDom 
)
inline

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

Definition at line 213 of file MachineDominators.h.

References N.

Referenced by loadMBUFScalarOperandsFromVGPR().

◆ changeImmediateDominator() [2/2]

void llvm::MachineDominatorTree::changeImmediateDominator ( MachineDomTreeNode N,
MachineDomTreeNode NewIDom 
)
inline

Definition at line 219 of file MachineDominators.h.

References N.

◆ dominates() [1/3]

bool llvm::MachineDominatorTree::dominates ( const MachineBasicBlock A,
const MachineBasicBlock B 
) const
inline

Definition at line 147 of file MachineDominators.h.

References A, and B.

◆ dominates() [2/3]

bool llvm::MachineDominatorTree::dominates ( const MachineDomTreeNode A,
const MachineDomTreeNode B 
) const
inline

◆ dominates() [3/3]

bool llvm::MachineDominatorTree::dominates ( const MachineInstr A,
const MachineInstr B 
) const
inline

Definition at line 154 of file MachineDominators.h.

References A, B, llvm::MachineBasicBlock::begin(), and I.

◆ eraseNode()

void llvm::MachineDominatorTree::eraseNode ( MachineBasicBlock BB)
inline

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.

Definition at line 228 of file MachineDominators.h.

◆ findNearestCommonDominator()

MachineBasicBlock * llvm::MachineDominatorTree::findNearestCommonDominator ( MachineBasicBlock A,
MachineBasicBlock B 
)
inline

findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.

If there is no such block then return NULL.

Definition at line 182 of file MachineDominators.h.

References A, and B.

Referenced by hoistAndMergeSGPRInits().

◆ getBase()

MachineDominatorTree & llvm::MachineDominatorTree::getBase ( )
inline

◆ getDescendants()

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

Definition at line 141 of file MachineDominators.h.

References A.

◆ getNode()

MachineDomTreeNode * llvm::MachineDominatorTree::getNode ( MachineBasicBlock BB) const
inline

getNode - return the (Post)DominatorTree node for the specified basic block.

This is the same as using operator[] on this class.

Definition at line 196 of file MachineDominators.h.

Referenced by llvm::rdf::Liveness::getNearestAliasedRef(), and llvm::PhiLoweringHelper::lowerPhis().

◆ getRoot()

MachineBasicBlock * llvm::MachineDominatorTree::getRoot ( ) const
inline

Definition at line 123 of file MachineDominators.h.

◆ getRootNode()

MachineDomTreeNode * llvm::MachineDominatorTree::getRootNode ( ) const
inline

◆ invalidate()

bool MachineDominatorTree::invalidate ( MachineFunction ,
const PreservedAnalyses PA,
MachineFunctionAnalysisManager::Invalidator  
)

Handle invalidation explicitly.

Definition at line 60 of file MachineDominators.cpp.

References llvm::PreservedAnalyses::getChecker().

◆ isReachableFromEntry()

bool llvm::MachineDominatorTree::isReachableFromEntry ( const MachineBasicBlock A)
inline

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

Definition at line 242 of file MachineDominators.h.

References A.

◆ operator[]()

MachineDomTreeNode * llvm::MachineDominatorTree::operator[] ( MachineBasicBlock BB) const
inline

Definition at line 188 of file MachineDominators.h.

◆ properlyDominates() [1/2]

bool llvm::MachineDominatorTree::properlyDominates ( const MachineBasicBlock A,
const MachineBasicBlock B 
) const
inline

Definition at line 174 of file MachineDominators.h.

References A, and B.

◆ properlyDominates() [2/2]

bool llvm::MachineDominatorTree::properlyDominates ( const MachineDomTreeNode A,
const MachineDomTreeNode B 
) const
inline

◆ recordSplitCriticalEdge()

void llvm::MachineDominatorTree::recordSplitCriticalEdge ( MachineBasicBlock FromBB,
MachineBasicBlock ToBB,
MachineBasicBlock NewBB 
)
inline

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.

Note
Do not use this method with regular edges.
To benefit from the compile time improvement incurred by this method, the users of this method have to limit the queries to the DT interface between two edges splitting. In other words, they have to pack the splitting of critical edges as much as possible.

Definition at line 259 of file MachineDominators.h.

References assert(), llvm::SmallSet< T, N, C >::insert(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

◆ splitBlock()

void llvm::MachineDominatorTree::splitBlock ( MachineBasicBlock NewBB)
inline

splitBlock - BB is split and now it has one successor.

Update dominator tree to reflect this change.

Definition at line 235 of file MachineDominators.h.


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