llvm::DominatorTreeBase

Synopsis

Declared in <llvm/Support/GenericDomTree.h>

template<
    typename NodeT,
    bool IsPostDom>
class DominatorTreeBase;

Description

This class is a generic template over graph nodes. It is instantiated for various graphs in the LLVM IR or in the code generator.

Type Aliases

Name	Description
`NodePtr`	Pointer to a CFG node / basic block.
`NodeTrait`	Node traits used to access parents and entry nodes.
`NodeType`	Concrete CFG node / basic-block type.
`ParentPtr`	Pointer to the parent of a CFG node (e.g. a Function).
`ParentType`	Type of the parent of a CFG node (e.g. Function).
`UpdateKind`	Kind of CFG update (insert or delete).
`UpdateType`	CFG update describing an edge insertion or deletion.
`const_root_iterator`	Const iterator over root CFG blocks.
`root_iterator`	Iteration over roots.

Enums

Name	Description
`VerificationLevel`	How thoroughly `verify` checks the tree.

Member Functions

Name	Description
`DominatorTreeBase` [constructor]	Constructors
`operator=`	Assignment operators
`addNewBlock`	Add a new node to the dominator tree information.
`applyUpdates`	`applyUpdates` overloads
`changeImmediateDominator`	`changeImmediateDominator` overloads
`compare`	Return true if this tree differs from `Other.`
`deleteEdge`	Inform the dominator tree about a CFG edge deletion and update the tree.
`dominates`	`dominates` overloads
`eraseNode`	Remove a leaf node for block `BB` from the dominator tree.
`findNearestCommonDominator`	`findNearestCommonDominator` overloads
`getDescendants`	Get all nodes dominated by `R,` including `R` itself.
`getNode`	Return the (post-)dominator tree node for basic block `BB.`
`getRoot`	Return the single root block of a forward dominator tree.
`getRootNode`	Return the root node of this (post-)dominator tree.
`insertEdge`	Inform the dominator tree about a CFG edge insertion and update the tree.
`isPostDominator`	Return true if this tree encodes post-dominance rather than dominance.
`isReachableFromEntry`	Return true if `A` is dominated by the entry block of its function.
`isVirtualRoot`	Return true if `A` is the virtual root of a post-dominator tree.
`operator[]`	Return the (post-)dominator tree node for basic block `BB.`
`print`	Print the dominator tree in human-readable form.
`properlyDominates`	`properlyDominates` overloads
`recalculate`	`recalculate` overloads
`reset`	Clear all tree nodes, roots, and allocator state.
`root_begin`	`root_begin` overloads
`root_end`	`root_end` overloads
`root_size`	Return the number of root blocks.
`roots`	`roots` overloads
`setNewRoot`	Add a new node to the forward dominator tree and make it a new root.
`splitBlock`	Update the tree after `NewBB` is split and has a single successor.
`updateBlockNumbers`	Update dominator tree after renumbering blocks.
`updateDFSNumbers`	updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
`verify`	Check whether the dominator tree is correct at the given verification level.

Static Data Members

Name	Description
`Delete`	CFG update kind for deleting an edge.
`Insert`	CFG update kind for inserting an edge.
`IsPostDominator`	True when this tree encodes post-dominance rather than dominance.

Protected Type Aliases

Name	Description
`DomTreeNodeStorageTy`	Storage type for the dense map from block number to tree node.

Protected Member Functions

Name	Description
`Split`	Update the tree after `NewBB` is split and has a single successor.
`addRoot`	Append `BB` to the list of root blocks.
`createNode`	Create a node for `BB` and link it under `IDom` when provided.
`createNodeUnlinked`	Create a node for `BB;` the caller must link it with addChild.

Protected Data Members

Name	Description
`BlockNumberEpoch`	Epoch of GraphTraits block numbers used when the tree was built/updated.
`DFSInfoValid`	True when DFS in/out numbers on nodes are currently valid.
`DomTreeNodes`	Tree nodes indexed by CFG block number (plus a slot for nullptr in PDT).
`NodeAllocator`	Allocator backing DomTreeNodeBase instances.
`Parent`	Parent of the CFG nodes (e.g. Function) this tree was built for.
`RootNode`	Root node of the dominator tree (possibly a virtual root for PDT).
`Roots`	Root CFG blocks of this (post-)dominator tree.
`SlowQueries`	Count of slow dominance queries since DFS numbers were last refreshed.

Protected Static Data Members

Name	Description
`SlabSize`	Bytes per bump-allocator slab used for tree nodes.

Friends

Name	Description
`llvm::LoopInfoBase`	Analysis that builds and owns the loop forest for a function.
`llvm::DomTreeBuilder::SemiNCAInfo`	Scratch state and algorithms for Semi-NCA dominator tree construction.

Derived Classes

Name	Description
`DominatorTree`	Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Template Parameters

Name	Description
NodeT	Graph node type (typically a basic-block type).
IsPostDom	True for a post-dominator tree; false for a dominator tree.