LLVM 19.0.0git
Public Types | Public Member Functions | List of all members
llvm::PostDominatorTree Class Reference

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominator tree. More...

#include "llvm/Analysis/PostDominators.h"

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

Public Types

using Base = PostDomTreeBase< BasicBlock >
 
- 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

 PostDominatorTree ()=default
 
 PostDominatorTree (Function &F)
 
bool invalidate (Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
 Handle invalidation explicitly.
 
bool dominates (const Instruction *I1, const Instruction *I2) const
 Return true if I1 dominates I2.
 
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
 
- 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)
 
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 DomTreeNodeMapType = DenseMap< NodeT *, std::unique_ptr< DomTreeNodeBase< NodeT > > >
 
- Protected Member Functions inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
void addRoot (NodeT *BB)
 
DomTreeNodeBase< NodeT > * createChild (NodeT *BB, DomTreeNodeBase< NodeT > *IDom)
 
DomTreeNodeBase< NodeT > * createNode (NodeT *BB)
 
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
 
DomTreeNodeMapType DomTreeNodes
 
DomTreeNodeBase< NodeT > * RootNode = nullptr
 
ParentPtr Parent = nullptr
 
bool DFSInfoValid = false
 
unsigned int SlowQueries = 0
 

Detailed Description

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominator tree.

Definition at line 28 of file PostDominators.h.

Member Typedef Documentation

◆ Base

Definition at line 30 of file PostDominators.h.

Constructor & Destructor Documentation

◆ PostDominatorTree() [1/2]

llvm::PostDominatorTree::PostDominatorTree ( )
default

◆ PostDominatorTree() [2/2]

llvm::PostDominatorTree::PostDominatorTree ( Function F)
inlineexplicit

Member Function Documentation

◆ dominates() [1/3]

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::dominates ( const DomTreeNodeBase< NodeT > *  A,
const DomTreeNodeBase< NodeT > *  B 
) const
inline

dominates - Returns true iff A dominates B.

Note that this is not a constant time operation!

Definition at line 432 of file GenericDomTree.h.

◆ dominates() [2/3]

bool PostDominatorTree::dominates ( const Instruction I1,
const Instruction I2 
) const

Return true if I1 dominates I2.

This checks if I2 comes before I1 if they belongs to the same basic block.

Definition at line 54 of file PostDominators.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::DominatorTreeBase< NodeT, IsPostDom >::dominates(), llvm::Instruction::getParent(), and I.

Referenced by llvm::memtag::forAllReachableExits(), llvm::isControlFlowEquivalent(), isFullPostDominator(), and llvm::nonStrictlyPostDominate().

◆ dominates() [3/3]

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::dominates ( const NodeT *  A,
const NodeT *  B 
) const

Definition at line 475 of file GenericDomTree.h.

◆ invalidate()

bool llvm::PostDominatorTree::invalidate ( Function F,
const PreservedAnalyses PA,
FunctionAnalysisManager::Invalidator  
)

Handle invalidation explicitly.


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