Core dominator tree base class. More...
#include "llvm/Support/GenericDomTree.h"
Public Types | |
| 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 | |
| DominatorTreeBase ()=default | |
| DominatorTreeBase (const DominatorTreeBase &)=delete | |
| DominatorTreeBase & | operator= (const DominatorTreeBase &)=delete |
| DominatorTreeBase (DominatorTreeBase &&Arg)=default | |
| DominatorTreeBase & | operator= (DominatorTreeBase &&RHS)=default |
| 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<typename IteratorTy> | |
| 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 = SmallVector<DomTreeNodeBase<NodeT> *> |
Protected Member Functions | |
| void | addRoot (NodeT *BB) |
| DomTreeNodeBase< NodeT > * | createNode (NodeT *BB, DomTreeNodeBase< NodeT > *IDom=nullptr) |
| template<class N> | |
| void | Split (typename GraphTraits< N >::NodeRef NewBB) |
Protected Attributes | |
| 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 |
| BumpPtrAllocatorImpl< MallocAllocator, SlabSize, SlabSize, 2 > | NodeAllocator |
| bool | DFSInfoValid = false |
| unsigned int | SlowQueries = 0 |
| unsigned | BlockNumberEpoch = 0 |
Static Protected Attributes | |
| static constexpr size_t | SlabSize = 8 * sizeof(DomTreeNodeBase<NodeT>) |
Friends | |
| struct | DomTreeBuilder::SemiNCAInfo< DominatorTreeBase > |
| template<class BlockT, class LoopT> | |
| class | LoopInfoBase |
Detailed Description
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 273 of file GenericDomTree.h.
Member Typedef Documentation
◆ const_root_iterator
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator |
Definition at line 338 of file GenericDomTree.h.
◆ DomTreeNodeStorageTy
|
protected |
Definition at line 297 of file GenericDomTree.h.
◆ NodePtr
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::NodePtr = typename NodeTrait::NodePtr |
Definition at line 279 of file GenericDomTree.h.
◆ NodeTrait
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::NodeTrait = DomTreeNodeTraits<NodeT> |
Definition at line 277 of file GenericDomTree.h.
◆ NodeType
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::NodeType = typename NodeTrait::NodeType |
Definition at line 278 of file GenericDomTree.h.
◆ ParentPtr
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::ParentPtr = typename NodeTrait::ParentPtr |
Definition at line 280 of file GenericDomTree.h.
◆ ParentType
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::ParentType = std::remove_pointer_t<ParentPtr> |
Definition at line 283 of file GenericDomTree.h.
◆ root_iterator
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::root_iterator = typename SmallVectorImpl<NodeT *>::iterator |
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 337 of file GenericDomTree.h.
◆ UpdateKind
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::UpdateKind = cfg::UpdateKind |
Definition at line 287 of file GenericDomTree.h.
◆ UpdateType
| using llvm::DominatorTreeBase< NodeT, IsPostDom >::UpdateType = cfg::Update<NodePtr> |
Definition at line 286 of file GenericDomTree.h.
Member Enumeration Documentation
◆ VerificationLevel
|
strong |
| Enumerator | |
|---|---|
| Fast | |
| Basic | |
| Full | |
Definition at line 291 of file GenericDomTree.h.
Constructor & Destructor Documentation
◆ DominatorTreeBase() [1/3]
|
default |
◆ DominatorTreeBase() [2/3]
|
delete |
◆ DominatorTreeBase() [3/3]
|
default |
Member Function Documentation
◆ addNewBlock()
|
inline |
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.
- Parameters
-
BB New node in CFG. DomBB CFG node that is dominator for BB.
- Returns
- New dominator tree node that represents new CFG node.
Definition at line 723 of file GenericDomTree.h.
Referenced by CloneLoopBlocks(), cloneLoopBlocks(), llvm::cloneLoopWithPreheader(), llvm::DominatorTreeBase< BlockT, false >::Split(), SplitBlockImpl(), llvm::UnrollAndJamLoop(), and llvm::UnrollLoop().
◆ addRoot()
|
inlineprotected |
Definition at line 951 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::setNewRoot().
◆ applyUpdates() [1/2]
|
inline |
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<T> and PostDomTreeBase<T> 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 648 of file GenericDomTree.h.
Referenced by llvm::MemorySSAUpdater::applyUpdates(), llvm::expandReductionViaLoop(), injectPendingInvariantConditions(), splitBlock(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().
◆ applyUpdates() [2/2]
|
inline |
- 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 659 of file GenericDomTree.h.
◆ changeImmediateDominator() [1/2]
|
inline |
changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes.
Definition at line 759 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::changeImmediateDominator(), cloneLoopBlocks(), llvm::cloneLoopWithPreheader(), ConnectEpilog(), ConnectProlog(), llvm::peelLoop(), simplifyOneLoop(), llvm::DominatorTreeBase< BlockT, false >::Split(), SplitBlockImpl(), splitLoopBound(), llvm::UnrollLoop(), and llvm::UnrollRuntimeLoopRemainder().
◆ changeImmediateDominator() [2/2]
|
inline |
Definition at line 766 of file GenericDomTree.h.
◆ compare()
|
inline |
compare - Return false if the other dominator tree base matches this dominator tree base.
Otherwise return true.
Definition at line 360 of file GenericDomTree.h.
◆ createNode()
|
inlineprotected |
Definition at line 953 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::addNewBlock(), and llvm::DominatorTreeBase< BlockT, false >::setNewRoot().
◆ deleteEdge()
|
inline |
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 706 of file GenericDomTree.h.
Referenced by DoFlattenLoopPair(), replaceArgumentUses(), and unswitchTrivialBranch().
◆ dominates() [1/2]
|
inline |
dominates - Returns true iff A dominates B.
Note that this is not a constant time operation!
Definition at line 503 of file GenericDomTree.h.
Referenced by llvm::LoopInfoBase< BlockT, LoopT >::analyze(), canonicalHeaderAndLatch(), llvm::VPlanTransforms::createHeaderPhiRecipes(), llvm::VPlanTransforms::cse(), handleUncountableExitsWithSideEffects(), llvm::VPBlockUtils::isHeader(), llvm::VPlanTransforms::materializeBroadcasts(), llvm::DominatorTreeBase< BlockT, false >::properlyDominates(), llvm::VPlanTransforms::replaceSymbolicStrides(), and llvm::DominatorTreeBase< BlockT, false >::Split().
◆ dominates() [2/2]
| bool llvm::DominatorTreeBase< NodeT, IsPostDom >::dominates | ( | const NodeT * | A, |
| const NodeT * | B ) const |
Definition at line 1046 of file GenericDomTree.h.
References A(), B(), dominates(), and getNode().
◆ eraseNode()
|
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 773 of file GenericDomTree.h.
Referenced by llvm::MergeBlockIntoPredecessor(), and simplifyOneLoop().
◆ findNearestCommonDominator() [1/3]
|
inline |
Definition at line 585 of file GenericDomTree.h.
◆ findNearestCommonDominator() [2/3]
|
inline |
Definition at line 598 of file GenericDomTree.h.
◆ findNearestCommonDominator() [3/3]
|
inline |
Find nearest common dominator basic block for basic block A and B.
A and B must have tree nodes.
Definition at line 555 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::findNearestCommonDominator(), llvm::DominatorTreeBase< BlockT, false >::findNearestCommonDominator(), hoistAndMergeSGPRInits(), and llvm::DominatorTreeBase< BlockT, false >::Split().
◆ getDescendants()
|
inline |
Get all nodes dominated by R, including R itself.
Definition at line 461 of file GenericDomTree.h.
Referenced by replaceArgumentUses().
◆ getNode()
|
inline |
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 437 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()
|
inline |
Definition at line 548 of file GenericDomTree.h.
Referenced by getFreezeInsertPt(), and nearest_common_dominatee().
◆ getRootNode() [1/2]
|
inline |
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 457 of file GenericDomTree.h.
Referenced by llvm::DominanceFrontierBase< BlockT, IsPostDom >::analyze(), llvm::LoopInfoBase< BlockT, LoopT >::analyze(), cleanupLocalDynamicTLS(), llvm::GraphTraits< DominatorTree * >::getEntryNode(), llvm::GraphTraits< MachineDominatorTree * >::getEntryNode(), llvm::GraphTraits< PostDominatorTree * >::getEntryNode(), inferAlignment(), llvm::DominatorTreeBase< BlockT, false >::print(), llvm::GuardWideningPass::run(), UpdateAnalysisInformation(), and llvm::DominatorTreeBase< BlockT, false >::updateDFSNumbers().
◆ getRootNode() [2/2]
|
inline |
Definition at line 458 of file GenericDomTree.h.
◆ insertEdge()
|
inline |
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 688 of file GenericDomTree.h.
Referenced by replaceArgumentUses(), and unswitchTrivialBranch().
◆ isPostDominator()
|
inline |
isPostDominator - Returns true if analysis based of postdoms
Definition at line 356 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::findNearestCommonDominator(), llvm::DominatorTreeBase< BlockT, false >::isReachableFromEntry(), llvm::DominatorTreeBase< BlockT, false >::isVirtualRoot(), and llvm::DominatorTreeBase< BlockT, false >::setNewRoot().
◆ isReachableFromEntry() [1/2]
|
inline |
Definition at line 498 of file GenericDomTree.h.
◆ isReachableFromEntry() [2/2]
|
inline |
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it.
Definition at line 492 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::dominates(), llvm::DominatorTreeBase< BlockT, false >::isReachableFromEntry(), llvm::DominatorTreeBase< BlockT, false >::Split(), and llvm::LoopBase< BasicBlock, Loop >::verifyLoopNest().
◆ isVirtualRoot()
|
inline |
Definition at line 593 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::findNearestCommonDominator().
◆ operator=() [1/2]
|
delete |
◆ operator=() [2/2]
|
default |
◆ operator[]()
|
inline |
See getNode.
Definition at line 446 of file GenericDomTree.h.
◆ print()
|
inline |
print - Convert to human readable form
Definition at line 811 of file GenericDomTree.h.
◆ properlyDominates() [1/2]
|
inline |
properlyDominates - Returns true iff A dominates B and A != B.
Note that this is not a constant time operation!
Definition at line 479 of file GenericDomTree.h.
Referenced by ConstructSSAForLoadSet(), hoistAndMergeSGPRInits(), hoistNonEntryAllocasToEntryBlock(), and isLoadInvariantInLoop().
◆ properlyDominates() [2/2]
| bool llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates | ( | const NodeT * | A, |
| const NodeT * | B ) const |
Definition at line 1054 of file GenericDomTree.h.
References A(), B(), dominates(), and getNode().
◆ recalculate() [1/2]
|
inline |
recalculate - compute a dominator tree for the given function
Definition at line 888 of file GenericDomTree.h.
Referenced by AddAliasScopeMetadata(), AddAlignmentAssumptions(), llvm::OptimizationRemarkEmitter::OptimizationRemarkEmitter(), llvm::DominatorTreeAnalysis::run(), llvm::PlaceSafepointsPass::runImpl(), and verifyConvergenceControl().
◆ recalculate() [2/2]
|
inline |
Definition at line 894 of file GenericDomTree.h.
◆ reset()
|
inline |
Definition at line 938 of file GenericDomTree.h.
◆ root_begin() [1/2]
|
inline |
Definition at line 340 of file GenericDomTree.h.
Referenced by llvm::DominanceFrontierBase< BlockT, IsPostDom >::analyze(), llvm::DominatorTreeBase< BlockT, false >::roots(), and llvm::DominatorTreeBase< BlockT, false >::roots().
◆ root_begin() [2/2]
|
inline |
Definition at line 341 of file GenericDomTree.h.
◆ root_end() [1/2]
|
inline |
Definition at line 342 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::roots(), and llvm::DominatorTreeBase< BlockT, false >::roots().
◆ root_end() [2/2]
|
inline |
Definition at line 343 of file GenericDomTree.h.
◆ root_size()
|
inline |
Definition at line 345 of file GenericDomTree.h.
Referenced by llvm::DominanceFrontierBase< BlockT, IsPostDom >::analyze().
◆ roots() [1/2]
|
inline |
Definition at line 347 of file GenericDomTree.h.
◆ roots() [2/2]
|
inline |
Definition at line 350 of file GenericDomTree.h.
◆ setNewRoot()
|
inline |
Add a new node to the forward dominator tree and make it a new root.
- Parameters
-
BB New node in CFG.
- Returns
- New dominator tree node that represents new CFG node.
Definition at line 736 of file GenericDomTree.h.
Referenced by UpdateAnalysisInformation().
◆ Split()
|
inlineprotected |
Definition at line 967 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< BlockT, false >::splitBlock().
◆ splitBlock()
|
inline |
splitBlock - BB is split and now it has one successor.
Update dominator tree to reflect this change.
Definition at line 802 of file GenericDomTree.h.
Referenced by insertUniqueBackedgeBlock(), and UpdateAnalysisInformation().
◆ updateBlockNumbers()
|
inline |
Update dominator tree after renumbering blocks.
Definition at line 902 of file GenericDomTree.h.
◆ updateDFSNumbers()
|
inline |
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
Definition at line 834 of file GenericDomTree.h.
Referenced by llvm::LoopInfoBase< BlockT, LoopT >::analyze(), llvm::DominatorTreeBase< BlockT, false >::dominates(), eliminateConstraints(), and llvm::isSafeToMoveBefore().
◆ verify()
|
inline |
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 934 of file GenericDomTree.h.
Referenced by fixIrreducible(), llvm::hoistRegion(), injectPendingInvariantConditions(), llvm::peelLoop(), llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopBoundSplitPass::run(), llvm::SimpleLoopUnswitchPass::run(), runImpl(), simplifyFunctionCFG(), splitLoopBound(), unifyLoopExits(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), and unswitchTrivialSwitch().
Friends And Related Symbol Documentation
◆ DomTreeBuilder::SemiNCAInfo< DominatorTreeBase >
|
friend |
Definition at line 318 of file GenericDomTree.h.
◆ LoopInfoBase
|
friend |
Definition at line 321 of file GenericDomTree.h.
Member Data Documentation
◆ BlockNumberEpoch
|
protected |
Definition at line 318 of file GenericDomTree.h.
◆ Delete
|
staticconstexpr |
Definition at line 289 of file GenericDomTree.h.
Referenced by llvm::MemorySSAUpdater::applyUpdates(), and unswitchTrivialSwitch().
◆ DFSInfoValid
|
mutableprotected |
Definition at line 316 of file GenericDomTree.h.
◆ DomTreeNodes
|
protected |
Definition at line 298 of file GenericDomTree.h.
◆ Insert
|
staticconstexpr |
Definition at line 288 of file GenericDomTree.h.
Referenced by llvm::MemorySSAUpdater::applyUpdates(), and unswitchTrivialSwitch().
◆ IsPostDominator
|
staticconstexpr |
Definition at line 284 of file GenericDomTree.h.
◆ NodeAllocator
|
protected |
Definition at line 314 of file GenericDomTree.h.
◆ NodeNumberMap
|
protected |
Definition at line 303 of file GenericDomTree.h.
◆ Parent
|
protected |
Definition at line 305 of file GenericDomTree.h.
Referenced by llvm::DominatorTree::DominatorTree().
◆ RootNode
|
protected |
Definition at line 304 of file GenericDomTree.h.
◆ Roots
|
protected |
Definition at line 295 of file GenericDomTree.h.
◆ SlabSize
|
staticconstexprprotected |
Definition at line 311 of file GenericDomTree.h.
◆ SlowQueries
|
mutableprotected |
Definition at line 317 of file GenericDomTree.h.
The documentation for this class was generated from the following files:
- include/llvm/ADT/GenericSSAContext.h
- include/llvm/Support/GenericDomTree.h
Generated on for LLVM by
1.14.0