LLVM 20.0.0git
|
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree. More...
#include "llvm/CodeGen/MachineDominators.h"
Public Types | |
using | Base = DomTreeBase< MachineBasicBlock > |
![]() | |
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. | |
MachineDominatorTree & | getBase () |
MachineBasicBlock * | getRoot () const |
MachineDomTreeNode * | getRootNode () 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 |
MachineBasicBlock * | findNearestCommonDominator (MachineBasicBlock *A, MachineBasicBlock *B) |
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B. | |
MachineDomTreeNode * | operator[] (MachineBasicBlock *BB) const |
MachineDomTreeNode * | getNode (MachineBasicBlock *BB) const |
getNode - return the (Post)DominatorTree node for the specified basic block. | |
MachineDomTreeNode * | addNewBlock (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. | |
![]() | |
DominatorTreeBase ()=default | |
DominatorTreeBase (DominatorTreeBase &&Arg) | |
DominatorTreeBase & | operator= (DominatorTreeBase &&RHS) |
DominatorTreeBase (const DominatorTreeBase &)=delete | |
DominatorTreeBase & | operator= (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_iterator > | roots () |
iterator_range< const_root_iterator > | roots () 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<class T_ = NodeT> | |
std::enable_if_t< is_detected< has_number_t, T_ >::value, 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 constexpr bool | IsPostDominator = IsPostDom |
static constexpr UpdateKind | Insert = UpdateKind::Insert |
static constexpr UpdateKind | Delete = UpdateKind::Delete |
![]() | |
using | DomTreeNodeStorageTy = SmallVector< std::unique_ptr< DomTreeNodeBase< NodeT > > > |
![]() | |
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) |
![]() | |
SmallVector< NodeT *, IsPostDom ? 4 :1 > | Roots |
DomTreeNodeStorageTy | DomTreeNodes |
DenseMap< const NodeT *, unsigned > | NodeNumberMap |
DomTreeNodeBase< NodeT > * | RootNode = nullptr |
ParentPtr | Parent = nullptr |
bool | DFSInfoValid = false |
unsigned int | SlowQueries = 0 |
unsigned | BlockNumberEpoch = 0 |
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition at line 75 of file MachineDominators.h.
Definition at line 106 of file MachineDominators.h.
|
default |
|
inlineexplicit |
Definition at line 109 of file MachineDominators.h.
|
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().
void MachineDominatorTree::calculate | ( | MachineFunction & | F | ) |
Definition at line 98 of file MachineDominators.cpp.
References llvm::SmallVectorImpl< T >::clear(), F, and llvm::DominatorTreeBase< NodeT, IsPostDom >::recalculate().
|
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().
|
inline |
Definition at line 219 of file MachineDominators.h.
References N.
|
inline |
Definition at line 147 of file MachineDominators.h.
|
inline |
Definition at line 135 of file MachineDominators.h.
Referenced by llvm::CombinerHelper::dominates(), dominatesAllUsesOf(), hoistAndMergeSGPRInits(), INITIALIZE_PASS(), isReachable(), isReachableAmongDominated(), oneUseDominatesOtherUses(), replaceDominatedUses(), and sortBlocks().
|
inline |
Definition at line 154 of file MachineDominators.h.
References A, B, llvm::MachineBasicBlock::begin(), and I.
|
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.
|
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.
Referenced by hoistAndMergeSGPRInits().
|
inline |
Definition at line 118 of file MachineDominators.h.
Referenced by llvm::MachineLoopInfo::calculate(), llvm::AsmPrinter::emitFunctionBody(), llvm::PhiLoweringHelper::lowerPhis(), llvm::AMDGPURegBankSelect::runOnMachineFunction(), and splitBlock().
|
inline |
Definition at line 141 of file MachineDominators.h.
References A.
|
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().
|
inline |
Definition at line 123 of file MachineDominators.h.
|
inline |
Definition at line 128 of file MachineDominators.h.
Referenced by llvm::GraphTraits< MachineDominatorTree * >::getEntryNode().
bool MachineDominatorTree::invalidate | ( | MachineFunction & | , |
const PreservedAnalyses & | PA, | ||
MachineFunctionAnalysisManager::Invalidator & | |||
) |
Handle invalidation explicitly.
Definition at line 60 of file MachineDominators.cpp.
References llvm::PreservedAnalyses::getChecker().
|
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.
|
inline |
Definition at line 188 of file MachineDominators.h.
|
inline |
Definition at line 174 of file MachineDominators.h.
|
inline |
Definition at line 168 of file MachineDominators.h.
Referenced by llvm::rdf::Liveness::getAllReachingDefs(), hoistAndMergeSGPRInits(), and loadMBUFScalarOperandsFromVGPR().
|
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.
Definition at line 259 of file MachineDominators.h.
References assert(), llvm::SmallSet< T, N, C >::insert(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
|
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.