LLVM: llvm::DominatorTreeBase< NodeT, IsPostDom > Class Template Reference (original) (raw)
Core dominator tree base class. More...
#include "[llvm/Support/GenericDomTree.h](GenericDomTree%5F8h%5Fsource.html)"
| Public Types | |
|---|---|
| enum class | VerificationLevel { Fast, Basic, Full } |
| using | NodeTrait = DomTreeNodeTraits |
| 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 | |
|---|---|
| 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 |
| template | |
| NodeT * | findNearestCommonDominator (iterator_range< IteratorTy > Nodes) 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 () |
| Static Public Attributes | |
|---|---|
| static constexpr bool | IsPostDominator = IsPostDom |
| static constexpr UpdateKind | Insert = UpdateKind::Insert |
| static constexpr UpdateKind | Delete = UpdateKind::Delete |
| Protected Types | |
|---|---|
| using | DomTreeNodeStorageTy |
| Protected Attributes | |
|---|---|
| SmallVector< NodeT *, IsPostDom ? 4 :1 > | Roots |
| DomTreeNodeStorageTy | DomTreeNodes |
| std::conditional_t< |
NodeNumberMap |
| DomTreeNodeBase< NodeT > * | RootNode = nullptr |
| ParentPtr | Parent = nullptr |
| bool | DFSInfoValid = false |
| unsigned int | SlowQueries = 0 |
| unsigned | BlockNumberEpoch = 0 |
template<typename NodeT, bool IsPostDom>
class llvm::DominatorTreeBase< NodeT, IsPostDom >
Core dominator tree base class.
This class is a generic template over graph nodes. It is instantiated for various graphs in the LLVM IR or in the code generator.
Definition at line 236 of file GenericDomTree.h.
◆ const_root_iterator
template<typename NodeT, bool IsPostDom>
◆ DomTreeNodeStorageTy
template<typename NodeT, bool IsPostDom>
Initial value:
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition at line 260 of file GenericDomTree.h.
◆ NodePtr
template<typename NodeT, bool IsPostDom>
◆ NodeTrait
template<typename NodeT, bool IsPostDom>
◆ NodeType
template<typename NodeT, bool IsPostDom>
◆ ParentPtr
template<typename NodeT, bool IsPostDom>
◆ ParentType
template<typename NodeT, bool IsPostDom>
◆ root_iterator
template<typename NodeT, bool IsPostDom>
Iteration over roots.
This may include multiple blocks if we are computing post dominators. For forward dominators, this will always be a single block (the entry block).
Definition at line 311 of file GenericDomTree.h.
◆ UpdateKind
template<typename NodeT, bool IsPostDom>
◆ UpdateType
template<typename NodeT, bool IsPostDom>
◆ VerificationLevel
template<typename NodeT, bool IsPostDom>
template<typename NodeT, bool IsPostDom>
◆ DominatorTreeBase() [2/3]
template<typename NodeT, bool IsPostDom>
◆ DominatorTreeBase() [3/3]
template<typename NodeT, bool IsPostDom>
◆ addNewBlock()
template<typename NodeT, bool IsPostDom>
◆ addRoot()
template<typename NodeT, bool IsPostDom>
◆ applyUpdates() [1/2]
template<typename NodeT, bool IsPostDom>
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch update on the tree.
This function should be used when there were multiple CFG updates after the last dominator tree update. It takes care of performing the updates in sync with the CFG and optimizes away the redundant operations that cancel each other. The functions expects the sequence of updates to be balanced. Eg.:
- {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because logically it results in a single insertions.
- {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make sense to insert the same edge twice.
What's more, the functions assumes that it's safe to ask every node in the CFG about its children and inverse children. This implies that deletions of CFG edges must not delete the CFG nodes before calling this function.
The applyUpdates function can reorder the updates and remove redundant ones internally (as long as it is done in a deterministic fashion). The batch updater is also able to detect sequences of zero and exactly one update – it's optimized to do less work in these cases.
Note that for postdominators it automatically takes care of applying updates on reverse edges internally (so there's no need to swap the From and To pointers when constructing DominatorTree::UpdateType). The type of updates is the same for DomTreeBase and PostDomTreeBase with the same template parameter T.
Parameters
| Updates | An ordered sequence of updates to perform. The current CFG and the reverse of these updates provides the pre-view of the CFG. |
|---|
Definition at line 611 of file GenericDomTree.h.
Referenced by llvm::MemorySSAUpdater::applyUpdates(), injectPendingInvariantConditions(), splitBlock(), unswitchNontrivialInvariants(), and unswitchTrivialSwitch().
◆ applyUpdates() [2/2]
template<typename NodeT, bool IsPostDom>
Parameters
| Updates | An ordered sequence of updates to perform. The current CFG and the reverse of these updates provides the pre-view of the CFG. |
|---|---|
| PostViewUpdates | An ordered sequence of update to perform in order to obtain a post-view of the CFG. The DT will be updated assuming the obtained PostViewCFG is the desired end state. |
Definition at line 622 of file GenericDomTree.h.
◆ changeImmediateDominator() [1/2]
template<typename NodeT, bool IsPostDom>
changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes.
Definition at line 722 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::changeImmediateDominator(), cloneLoopBlocks(), llvm::cloneLoopWithPreheader(), ConnectEpilog(), ConnectProlog(), loadMBUFScalarOperandsFromVGPR(), llvm::peelLoop(), simplifyOneLoop(), llvm::DominatorTreeBase< BlockT, false >::Split(), SplitBlockImpl(), splitLoopBound(), llvm::UnrollLoop(), and llvm::UnrollRuntimeLoopRemainder().
◆ changeImmediateDominator() [2/2]
template<typename NodeT, bool IsPostDom>
◆ compare()
template<typename NodeT, bool IsPostDom>
compare - Return false if the other dominator tree base matches this dominator tree base.
Otherwise return true.
Definition at line 334 of file GenericDomTree.h.
◆ createNode()
template<typename NodeT, bool IsPostDom>
◆ deleteEdge()
template<typename NodeT, bool IsPostDom>
Inform the dominator tree about a CFG edge deletion and update the tree.
This function has to be called just after making the update on the actual CFG. An internal functions checks if the edge doesn't exist in the CFG in DEBUG mode. There cannot be any other updates that the dominator tree doesn't know about.
Note that for postdominators it automatically takes care of deleting a reverse edge internally (so there's no need to swap the parameters).
Definition at line 669 of file GenericDomTree.h.
Referenced by DoFlattenLoopPair(), replaceArgumentUses(), and unswitchTrivialBranch().
◆ dominates() [1/2]
template<typename NodeT, bool IsPostDom>
◆ dominates() [2/2]
template<typename NodeT, bool IsPostDom>
◆ eraseNode()
template<typename NodeT, bool IsPostDom>
◆ findNearestCommonDominator() [1/3]
template<typename NodeT, bool IsPostDom>
◆ findNearestCommonDominator() [2/3]
template<typename NodeT, bool IsPostDom>
template
◆ findNearestCommonDominator() [3/3]
template<typename NodeT, bool IsPostDom>
◆ getDescendants()
template<typename NodeT, bool IsPostDom>
◆ getNode()
template<typename NodeT, bool IsPostDom>
getNode - return the (Post)DominatorTree node for the specified basic block.
This is the same as using operator[] on this class. The result may (but is not required to) be null for a forward (backwards) statically unreachable block.
Definition at line 400 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::addNewBlock(), llvm::LoopInfoBase< BlockT, LoopT >::analyze(), llvm::DominatorTreeBase< BlockT, false >::changeImmediateDominator(), checkAndReplaceCondition(), checkHoistValue(), CloneLoopBlocks(), cloneLoopBlocks(), llvm::cloneLoopWithPreheader(), llvm::collectChildrenInLoop(), collectUnswitchCandidatesWithInjections(), compareCmp(), computeBlocksDominatingExits(), containsUnconditionalCallSafepoint(), domTreeLevelBefore(), eliminateConstraints(), llvm::MustBeExecutedContextExplorer::findBackwardJoinPoint(), findBestInsertionSet(), llvm::MustBeExecutedContextExplorer::findForwardJoinPoint(), llvm::DominatorTreeBase< BlockT, false >::findNearestCommonDominator(), llvm::DominatorTreeBase< BlockT, false >::findNearestCommonDominator(), formLCSSAForInstructionsImpl(), llvm::DominatorTreeBase< BlockT, false >::getDescendants(), getDominatees(), getDominators(), llvm::hoistRegion(), hoistValue(), isGuaranteedNotToBeUndefOrPoison(), llvm::DominatorTreeBase< BlockT, false >::isReachableFromEntry(), loadCSE(), llvm::MergeBlockIntoPredecessor(), llvm::DominatorTreeBase< BlockT, false >::operator, llvm::peelLoop(), preheader(), llvm::SSAUpdaterBulk::RewriteAllUses(), llvm::GuardWideningPass::run(), llvm::DominatorTreeBase< BlockT, false >::setNewRoot(), shouldSplitOnPredicatedArgument(), simplifyOneLoop(), simplifyUsingControlFlow(), SinkInstruction(), llvm::sinkRegionForLoopNest(), llvm::DominatorTreeBase< BlockT, false >::Split(), SplitBlockImpl(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), and llvm::UnrollRuntimeLoopRemainder().
◆ getRoot()
template<typename NodeT, bool IsPostDom>
◆ getRootNode() [1/2]
template<typename NodeT, bool IsPostDom>
getRootNode - This returns the entry node for the CFG of the function.
If this tree represents the post-dominance relations for a function, however, this root may be a node with the block == NULL. This is the case when there are multiple exit nodes from a particular function. Consumers of post-dominance information must be capable of dealing with this possibility.
Definition at line 420 of file GenericDomTree.h.
Referenced by llvm::LoopInfoBase< BlockT, LoopT >::analyze(), llvm::GraphTraits< DominatorTree * >::getEntryNode(), llvm::GraphTraits< MachineDominatorTree * >::getEntryNode(), llvm::GraphTraits< PostDominatorTree * >::getEntryNode(), llvm::DominatorTreeBase< BlockT, false >::print(), llvm::GuardWideningPass::run(), UpdateAnalysisInformation(), and llvm::DominatorTreeBase< BlockT, false >::updateDFSNumbers().
◆ getRootNode() [2/2]
template<typename NodeT, bool IsPostDom>
◆ insertEdge()
template<typename NodeT, bool IsPostDom>
Inform the dominator tree about a CFG edge insertion and update the tree.
This function has to be called just before or just after making the update on the actual CFG. There cannot be any other updates that the dominator tree doesn't know about.
Note that for postdominators it automatically takes care of inserting a reverse edge internally (so there's no need to swap the parameters).
Definition at line 651 of file GenericDomTree.h.
Referenced by replaceArgumentUses(), and unswitchTrivialBranch().
◆ isPostDominator()
template<typename NodeT, bool IsPostDom>
◆ isReachableFromEntry() [1/2]
template<typename NodeT, bool IsPostDom>
◆ isReachableFromEntry() [2/2]
template<typename NodeT, bool IsPostDom>
◆ isVirtualRoot()
template<typename NodeT, bool IsPostDom>
◆ operator=() [1/2]
template<typename NodeT, bool IsPostDom>
◆ operator=() [2/2]
template<typename NodeT, bool IsPostDom>
◆ operator[]()
template<typename NodeT, bool IsPostDom>
◆ print()
template<typename NodeT, bool IsPostDom>
◆ properlyDominates() [1/2]
template<typename NodeT, bool IsPostDom>
◆ properlyDominates() [2/2]
template<typename NodeT, bool IsPostDom>
◆ recalculate() [1/2]
template<typename NodeT, bool IsPostDom>
◆ recalculate() [2/2]
template<typename NodeT, bool IsPostDom>
◆ reset()
template<typename NodeT, bool IsPostDom>
◆ root_begin() [1/2]
template<typename NodeT, bool IsPostDom>
◆ root_begin() [2/2]
template<typename NodeT, bool IsPostDom>
◆ root_end() [1/2]
template<typename NodeT, bool IsPostDom>
◆ root_end() [2/2]
template<typename NodeT, bool IsPostDom>
◆ root_size()
template<typename NodeT, bool IsPostDom>
◆ roots() [1/2]
template<typename NodeT, bool IsPostDom>
◆ roots() [2/2]
template<typename NodeT, bool IsPostDom>
◆ setNewRoot()
template<typename NodeT, bool IsPostDom>
Add a new node to the forward dominator tree and make it a new root.
Parameters
Returns
New dominator tree node that represents new CFG node.
Definition at line 699 of file GenericDomTree.h.
Referenced by UpdateAnalysisInformation().
◆ Split()
template<typename NodeT, bool IsPostDom>
template<class N>
◆ splitBlock()
template<typename NodeT, bool IsPostDom>
◆ updateBlockNumbers()
template<typename NodeT, bool IsPostDom>
template<typename T = NodeT>
◆ updateDFSNumbers()
template<typename NodeT, bool IsPostDom>
◆ verify()
template<typename NodeT, bool IsPostDom>
verify - checks if the tree is correct.
There are 3 level of verification:
- Full – verifies if the tree is correct by making sure all the properties (including the parent and the sibling property) hold. Takes O(N^3) time.
- Basic – checks if the tree is correct, but compares it to a freshly constructed tree instead of checking the sibling property. Takes O(N^2) time.
- Fast – checks basic tree structure and compares it with a freshly constructed tree. Takes O(N^2) time worst case, but is faster in practise (same as tree construction).
Definition at line 904 of file GenericDomTree.h.
Referenced by fixIrreducible(), llvm::hoistRegion(), injectPendingInvariantConditions(), llvm::peelLoop(), llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopBoundSplitPass::run(), llvm::SimpleLoopUnswitchPass::run(), runImpl(), simplifyFunctionCFG(), unifyLoopExits(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), and unswitchTrivialSwitch().
◆ DomTreeBuilder::SemiNCAInfo< DominatorTreeBase >
template<typename NodeT, bool IsPostDom>
◆ BlockNumberEpoch
template<typename NodeT, bool IsPostDom>
◆ Delete
template<typename NodeT, bool IsPostDom>
◆ DFSInfoValid
template<typename NodeT, bool IsPostDom>
◆ DomTreeNodes
template<typename NodeT, bool IsPostDom>
◆ Insert
template<typename NodeT, bool IsPostDom>
◆ IsPostDominator
template<typename NodeT, bool IsPostDom>
◆ NodeNumberMap
template<typename NodeT, bool IsPostDom>
◆ Parent
template<typename NodeT, bool IsPostDom>
◆ RootNode
template<typename NodeT, bool IsPostDom>
◆ Roots
template<typename NodeT, bool IsPostDom>
◆ SlowQueries
template<typename NodeT, bool IsPostDom>
The documentation for this class was generated from the following files:
- include/llvm/ADT/GenericSSAContext.h
- include/llvm/Support/GenericDomTree.h