class DominatorTreeBase

Declaration

template <typename NodeT, bool IsPostDom>
class DominatorTreeBase { /* full declaration omitted */ };

Description

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.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:228

Templates

NodeT
bool IsPostDom

Member Variables

protected SmallVector<NodeT*, IsPostDom ? 4 : 1> Roots
protected llvm::DominatorTreeBase::DomTreeNodeMapType DomTreeNodes
protected DomTreeNodeBase<NodeT>* RootNode = nullptr
protected llvm::DominatorTreeBase::ParentPtr Parent = nullptr
protected bool DFSInfoValid = false
protected unsigned int SlowQueries = 0
public static const bool IsPostDominator = IsPostDom
public static const llvm::DominatorTreeBase::UpdateKind Insert = UpdateKind::Insert
public static const llvm::DominatorTreeBase::UpdateKind Delete = UpdateKind::Delete

Method Overview

Methods

DominatorTreeBase<NodeT, IsPostDom>(
    DominatorTreeBase<NodeT, IsPostDom>&& Arg)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:265

Parameters

DominatorTreeBase<NodeT, IsPostDom>&& Arg

DominatorTreeBase<NodeT, IsPostDom>(
    const DominatorTreeBase<NodeT, IsPostDom>&)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:286

Parameters

const DominatorTreeBase<NodeT, IsPostDom>& 

DominatorTreeBase<NodeT, IsPostDom>()

Declared at: llvm/include/llvm/Support/GenericDomTree.h:263

template <class N>
void Split(typename GraphTraits<N>::NodeRef NewBB)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:833

Templates

N

Parameters

typename GraphTraits<N>::NodeRef NewBB

DomTreeNodeBase<NodeT>* addNewBlock(NodeT* BB,
                                    NodeT* DomBB)

Description

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.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:619

Parameters

NodeT* BB
New node in CFG.
NodeT* DomBB
CFG node that is dominator for BB.

Returns

New dominator tree node that represents new CFG node.

void addRoot(NodeT* BB)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:816

Parameters

NodeT* BB

void applyUpdates(
    ArrayRef<llvm::DominatorTreeBase::UpdateType>
        Updates,
    ArrayRef<llvm::DominatorTreeBase::UpdateType>
        PostViewUpdates)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:555

Parameters

ArrayRef<llvm::DominatorTreeBase::UpdateType> Updates
An ordered sequence of updates to perform. The current CFG and the reverse of these updates provides the pre-view of the CFG.
ArrayRef<llvm::DominatorTreeBase::UpdateType> 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.

void applyUpdates(
    ArrayRef<llvm::DominatorTreeBase::UpdateType>
        Updates)

Description

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.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:544

Parameters

ArrayRef<llvm::DominatorTreeBase::UpdateType> Updates
An ordered sequence of updates to perform. The current CFG and the reverse of these updates provides the pre-view of the CFG.

void changeImmediateDominator(NodeT* BB,
                              NodeT* NewBB)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:662

Parameters

NodeT* BB
NodeT* NewBB

void changeImmediateDominator(
    DomTreeNodeBase<NodeT>* N,
    DomTreeNodeBase<NodeT>* NewIDom)

Description

changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:655

Parameters

DomTreeNodeBase<NodeT>* N
DomTreeNodeBase<NodeT>* NewIDom

bool compare(
    const DominatorTreeBase<NodeT, IsPostDom>&
        Other) const

Description

compare - Return false if the other dominator tree base matches this dominator tree base. Otherwise return true.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:317

Parameters

const DominatorTreeBase<NodeT, IsPostDom>& Other

DomTreeNodeBase<NodeT>* createChild(
    NodeT* BB,
    DomTreeNodeBase<NodeT>* IDom)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:818

Parameters

NodeT* BB
DomTreeNodeBase<NodeT>* IDom

DomTreeNodeBase<NodeT>* createNode(NodeT* BB)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:824

Parameters

NodeT* BB

void deleteEdge(NodeT* From, NodeT* To)

Description

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).

Declared at: llvm/include/llvm/Support/GenericDomTree.h:602

Parameters

NodeT* From
NodeT* To

bool dominatedBySlowTreeWalk(
    const DomTreeNodeBase<NodeT>* A,
    const DomTreeNodeBase<NodeT>* B) const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:886

Parameters

const DomTreeNodeBase<NodeT>* A
const DomTreeNodeBase<NodeT>* B

bool dominates(
    const DomTreeNodeBase<NodeT>* A,
    const DomTreeNodeBase<NodeT>* B) const

Description

dominates - Returns true iff A dominates B. Note that this is not a constant time operation!

Declared at: llvm/include/llvm/Support/GenericDomTree.h:416

Parameters

const DomTreeNodeBase<NodeT>* A
const DomTreeNodeBase<NodeT>* B

bool dominates(const NodeT* A,
               const NodeT* B) const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:459

Parameters

const NodeT* A
const NodeT* B

void eraseNode(NodeT* BB)

Description

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.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:669

Parameters

NodeT* BB

NodeT* findNearestCommonDominator(NodeT* A,
                                  NodeT* B) const

Description

Find nearest common dominator basic block for basic block A and B. A and B must have tree nodes.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:468

Parameters

NodeT* A
NodeT* B

const NodeT* findNearestCommonDominator(
    const NodeT* A,
    const NodeT* B) const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:497

Parameters

const NodeT* A
const NodeT* B

void getDescendants(
    NodeT* R,
    SmallVectorImpl<NodeT*>& Result) const

Description

Get all nodes dominated by R, including R itself.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:374

Parameters

NodeT* R
SmallVectorImpl<NodeT*>& Result

DomTreeNodeBase<NodeT>* getNode(
    const NodeT* BB) const

Description

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.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:351

Parameters

const NodeT* BB

NodeT* getRoot() const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:461

const DomTreeNodeBase<NodeT>* getRootNode() const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:371

DomTreeNodeBase<NodeT>* getRootNode()

Description

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.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:370

void insertEdge(NodeT* From, NodeT* To)

Description

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).

Declared at: llvm/include/llvm/Support/GenericDomTree.h:584

Parameters

NodeT* From
NodeT* To

bool isPostDominator() const

Description

isPostDominator - Returns true if analysis based of postdoms

Declared at: llvm/include/llvm/Support/GenericDomTree.h:313

bool isReachableFromEntry(
    const DomTreeNodeBase<NodeT>* A) const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:411

Parameters

const DomTreeNodeBase<NodeT>* A

bool isReachableFromEntry(const NodeT* A) const

Description

isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:405

Parameters

const NodeT* A

bool isVirtualRoot(
    const DomTreeNodeBase<NodeT>* A) const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:505

Parameters

const DomTreeNodeBase<NodeT>* A

void print(llvm::raw_ostream& O) const

Description

print - Convert to human readable form

Declared at: llvm/include/llvm/Support/GenericDomTree.h:709

Parameters

llvm::raw_ostream& O

bool properlyDominates(const NodeT* A,
                       const NodeT* B) const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:401

Parameters

const NodeT* A
const NodeT* B

bool properlyDominates(
    const DomTreeNodeBase<NodeT>* A,
    const DomTreeNodeBase<NodeT>* B) const

Description

properlyDominates - Returns true iff A dominates B and A != B. Note that this is not a constant time operation!

Declared at: llvm/include/llvm/Support/GenericDomTree.h:392

Parameters

const DomTreeNodeBase<NodeT>* A
const DomTreeNodeBase<NodeT>* B

void recalculate(
    llvm::DominatorTreeBase::ParentType& Func)

Description

recalculate - compute a dominator tree for the given function

Declared at: llvm/include/llvm/Support/GenericDomTree.h:778

Parameters

llvm::DominatorTreeBase::ParentType& Func

void recalculate(
    llvm::DominatorTreeBase::ParentType& Func,
    ArrayRef<llvm::DominatorTreeBase::UpdateType>
        Updates)

Declared at: llvm/include/llvm/Support/GenericDomTree.h:783

Parameters

llvm::DominatorTreeBase::ParentType& Func
ArrayRef<llvm::DominatorTreeBase::UpdateType> Updates

void reset()

Declared at: llvm/include/llvm/Support/GenericDomTree.h:806

llvm::DominatorTreeBase::const_root_iterator
root_begin() const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:298

llvm::DominatorTreeBase::root_iterator
root_begin()

Declared at: llvm/include/llvm/Support/GenericDomTree.h:297

llvm::DominatorTreeBase::const_root_iterator
root_end() const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:300

llvm::DominatorTreeBase::root_iterator root_end()

Declared at: llvm/include/llvm/Support/GenericDomTree.h:299

size_t root_size() const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:302

iterator_range<
    llvm::DominatorTreeBase::const_root_iterator>
roots() const

Declared at: llvm/include/llvm/Support/GenericDomTree.h:307

iterator_range<
    llvm::DominatorTreeBase::root_iterator>
roots()

Declared at: llvm/include/llvm/Support/GenericDomTree.h:304

DomTreeNodeBase<NodeT>* setNewRoot(NodeT* BB)

Description

Add a new node to the forward dominator tree and make it a new root.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:632

Parameters

NodeT* BB
New node in CFG.

Returns

New dominator tree node that represents new CFG node.

void splitBlock(NodeT* NewBB)

Description

splitBlock - BB is split and now it has one successor. Update dominator tree to reflect this change.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:700

Parameters

NodeT* NewBB

void updateDFSNumbers() const

Description

updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:732

bool verify(
    llvm::DominatorTreeBase::VerificationLevel
        VL = VerificationLevel::Full) const

Description

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).

Declared at: llvm/include/llvm/Support/GenericDomTree.h:802

Parameters

llvm::DominatorTreeBase::VerificationLevel VL = VerificationLevel::Full

void wipe()

Description

Wipe this tree's state without releasing any resources. This is essentially a post-move helper only. It leaves the object in an assignable and destroyable state, but otherwise invalid.

Declared at: llvm/include/llvm/Support/GenericDomTree.h:907