#include "llvm/IR/DomTreeUpdater.h"

Public Types
enum	UpdateStrategy : unsigned char { UpdateStrategy::Eager = 0, UpdateStrategy::Lazy = 1 }

Public Member Functions
	DomTreeUpdater (UpdateStrategy Strategy_)

	DomTreeUpdater (DominatorTree &DT_, UpdateStrategy Strategy_)

	DomTreeUpdater (DominatorTree *DT_, UpdateStrategy Strategy_)

	DomTreeUpdater (PostDominatorTree &PDT_, UpdateStrategy Strategy_)

	DomTreeUpdater (PostDominatorTree *PDT_, UpdateStrategy Strategy_)

	DomTreeUpdater (DominatorTree &DT_, PostDominatorTree &PDT_, UpdateStrategy Strategy_)

	DomTreeUpdater (DominatorTree DT_, PostDominatorTree PDT_, UpdateStrategy Strategy_)

	~DomTreeUpdater ()

bool	isLazy () const
	Returns true if the current strategy is Lazy. More...

bool	isEager () const
	Returns true if the current strategy is Eager. More...

bool	hasDomTree () const
	Returns true if it holds a DominatorTree. More...

bool	hasPostDomTree () const
	Returns true if it holds a PostDominatorTree. More...

bool	hasPendingDeletedBB () const
	Returns true if there is BasicBlock awaiting deletion. More...

bool	isBBPendingDeletion (BasicBlock *DelBB) const
	Returns true if DelBB is awaiting deletion. More...

bool	hasPendingUpdates () const
	Returns true if either of DT or PDT is valid and the tree has at least one update pending. More...

bool	hasPendingDomTreeUpdates () const
	Returns true if there are DominatorTree updates queued. More...

bool	hasPendingPostDomTreeUpdates () const
	Returns true if there are PostDominatorTree updates queued. More...

void	applyUpdates (ArrayRef< DominatorTree::UpdateType > Updates, bool ForceRemoveDuplicates=false)
	Apply updates on all available trees. More...

void	insertEdge (BasicBlock From, BasicBlock To)
	Notify all available trees on an edge insertion. More...

void	insertEdgeRelaxed (BasicBlock From, BasicBlock To)
	Notify all available trees on an edge insertion. More...

void	deleteEdge (BasicBlock From, BasicBlock To)
	Notify all available trees on an edge deletion. More...

void	deleteEdgeRelaxed (BasicBlock From, BasicBlock To)
	Notify all available trees on an edge deletion. More...

void	deleteBB (BasicBlock *DelBB)
	Delete DelBB. More...

void	callbackDeleteBB (BasicBlock DelBB, std::function< void(BasicBlock )> Callback)
	Delete DelBB. More...

void	recalculate (Function &F)
	Recalculate all available trees and flush all BasicBlocks awaiting deletion immediately. More...

DominatorTree &	getDomTree ()
	Flush DomTree updates and return DomTree. More...

PostDominatorTree &	getPostDomTree ()
	Flush PostDomTree updates and return PostDomTree. More...

void	flush ()
	Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion. More...

LLVM_DUMP_METHOD void	dump () const
	Debug method to help view the internal state of this class. More...

Detailed Description

Definition at line 27 of file DomTreeUpdater.h.

Member Enumeration Documentation

◆ UpdateStrategy

enum llvm::DomTreeUpdater::UpdateStrategy : unsigned char

strong

Enumerator
Eager
Lazy

Definition at line 29 of file DomTreeUpdater.h.

Constructor & Destructor Documentation

◆ DomTreeUpdater() [1/7]

llvm::DomTreeUpdater::DomTreeUpdater ( UpdateStrategy Strategy_ )

inlineexplicit

Definition at line 31 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [2/7]

llvm::DomTreeUpdater::DomTreeUpdater	(	DominatorTree &	DT_,
		UpdateStrategy	Strategy_
	)

inline

Definition at line 32 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [3/7]

llvm::DomTreeUpdater::DomTreeUpdater	(	DominatorTree *	DT_,
		UpdateStrategy	Strategy_
	)

inline

Definition at line 34 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [4/7]

llvm::DomTreeUpdater::DomTreeUpdater	(	PostDominatorTree &	PDT_,
		UpdateStrategy	Strategy_
	)

inline

Definition at line 36 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [5/7]

llvm::DomTreeUpdater::DomTreeUpdater	(	PostDominatorTree *	PDT_,
		UpdateStrategy	Strategy_
	)

inline

Definition at line 38 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [6/7]

llvm::DomTreeUpdater::DomTreeUpdater	(	DominatorTree &	DT_,
		PostDominatorTree &	PDT_,
		UpdateStrategy	Strategy_
	)

inline

Definition at line 40 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [7/7]

llvm::DomTreeUpdater::DomTreeUpdater	(	DominatorTree *	DT_,
		PostDominatorTree *	PDT_,
		UpdateStrategy	Strategy_
	)

inline

Definition at line 43 of file DomTreeUpdater.h.

◆ ~DomTreeUpdater()

llvm::DomTreeUpdater::~DomTreeUpdater ( )

inline

Definition at line 47 of file DomTreeUpdater.h.

References flush().

Member Function Documentation

◆ applyUpdates()

void llvm::DomTreeUpdater::applyUpdates	(	ArrayRef< DominatorTree::UpdateType >	Updates,
		bool	ForceRemoveDuplicates = `false`
	)

Apply updates on all available trees.

Under Eager UpdateStrategy with ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will discard duplicated updates and self-dominance updates. If both DT and PDT are nullptrs, this function discards all updates. The Eager Strategy applies the updates immediately while the Lazy Strategy queues the updates. It is required for the state of the LLVM IR to be updated before applying the Updates because the internal update routine will analyze the current state of the relationship between a pair of (From, To) BasicBlocks to determine whether a single update needs to be discarded.

Definition at line 265 of file DomTreeUpdater.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), Lazy, llvm::none_of(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by llvm::changeToUnreachable(), llvm::ConstantFoldTerminator(), llvm::DeleteDeadBlocks(), llvm::DuplicateInstructionsInSplitBetween(), hasPendingDeletedBB(), isUnconditionalBranch(), llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), llvm::removeUnreachableBlocks(), and llvm::TryToSimplifyUncondBranchFromEmptyBlock().

◆ callbackDeleteBB()

void llvm::DomTreeUpdater::callbackDeleteBB	(	BasicBlock *	DelBB,
		std::function< void(BasicBlock *)>	Callback
	)

Delete DelBB.

DelBB will be removed from its Parent and erased from available trees if it exists. Then the callback will be called. Finally, DelBB will be deleted. Under Eager UpdateStrategy, DelBB will be processed immediately. Under Lazy UpdateStrategy, DelBB will be queued until a flush event and all available trees are up-to-date. Assert if any instruction of DelBB is modified while awaiting deletion. Multiple callbacks can be queued for one DelBB under Lazy UpdateStrategy.

Definition at line 224 of file DomTreeUpdater.cpp.

References assert(), llvm::BasicBlock::back(), llvm::BasicBlock::empty(), llvm::DominatorTreeBase< NodeT, IsPostDom >::eraseNode(), llvm::UndefValue::get(), llvm::BasicBlock::getContext(), llvm::BasicBlock::getInstList(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Value::getType(), I, Lazy, llvm::iplist_impl< IntrusiveListT, TraitsT >::pop_back(), llvm::pred_empty(), llvm::BasicBlock::removeFromParent(), llvm::Value::replaceAllUsesWith(), and llvm::Value::use_empty().

Referenced by hasPendingDeletedBB().

◆ deleteBB()

void llvm::DomTreeUpdater::deleteBB ( BasicBlock * DelBB )

Delete DelBB.

DelBB will be removed from its Parent and erased from available trees if it exists and finally get deleted. Under Eager UpdateStrategy, DelBB will be processed immediately. Under Lazy UpdateStrategy, DelBB will be queued until a flush event and all available trees are up-to-date. Assert if any instruction of DelBB is modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB will be queued until flush() is called.

Definition at line 212 of file DomTreeUpdater.cpp.

References Lazy, and llvm::BasicBlock::removeFromParent().

Referenced by llvm::DeleteDeadBlocks(), foldReturnAndProcessPred(), hasPendingDeletedBB(), llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), llvm::removeUnreachableBlocks(), llvm::runIPSCCP(), splitCallSite(), and llvm::TryToSimplifyUncondBranchFromEmptyBlock().

◆ deleteEdge()

void llvm::DomTreeUpdater::deleteEdge	(	BasicBlock *	From,
		BasicBlock *	To
	)

Notify all available trees on an edge deletion.

If both DT and PDT are nullptrs, this function discards the update. Under either Strategy, self-dominance update will be removed. The Eager Strategy applies the update immediately while the Lazy Strategy queues the update. It is recommended to only use this method when you have exactly one deletion (and no insertions). It is recommended to use applyUpdates() in all other cases. This function has to be called after making the update on the actual CFG. An internal functions checks if the edge doesn't exist in the CFG in DEBUG mode.

Definition at line 359 of file DomTreeUpdater.cpp.

References assert(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), Eager, and From.

Referenced by llvm::deleteDeadLoop(), llvm::FoldReturnIntoUncondBranch(), getOnlyLiveSuccessor(), hasPendingDeletedBB(), processSwitch(), and splitCallSite().

◆ deleteEdgeRelaxed()

void llvm::DomTreeUpdater::deleteEdgeRelaxed	(	BasicBlock *	From,
		BasicBlock *	To
	)

Notify all available trees on an edge deletion.

Under either Strategy, the following updates will be discard silently

Invalid - Deleting an edge that still exists in the CFG.
Self-dominance update.
Both DT and PDT are nullptrs. The Eager Strategy applies the update immediately while the Lazy Strategy queues the update. It is recommended to only use this method when you have exactly one deletion (and no insertions) and want to discard an invalid update.

Definition at line 384 of file DomTreeUpdater.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), E, Eager, llvm::SmallVectorImpl< T >::erase(), From, and llvm::SmallVectorBase::size().

Referenced by llvm::ConstantFoldTerminator(), hasPendingDeletedBB(), llvm::RemovePredecessorAndSimplify(), and llvm::removeUnwindEdge().

◆ dump()

LLVM_DUMP_METHOD void llvm::DomTreeUpdater::dump ( ) const

Debug method to help view the internal state of this class.

Definition at line 428 of file DomTreeUpdater.cpp.

References assert(), llvm::sys::path::begin(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dbgs(), Eager, llvm::sys::path::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::Value::getName(), llvm::Value::hasName(), I, and llvm::DominatorTreeBase< BasicBlock, false >::Insert.

Referenced by hasPendingDeletedBB().

◆ flush()

void llvm::DomTreeUpdater::flush ( )

Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.

Does nothing under Eager UpdateStrategy.

Definition at line 107 of file DomTreeUpdater.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), E, llvm::SmallVectorTemplateCommon< T, typename >::end(), hasPendingPostDomTreeUpdates(), hasPendingUpdates(), I, Lazy, and llvm::SmallVectorBase::size().

Referenced by hasPendingDeletedBB(), and ~DomTreeUpdater().

◆ getDomTree()

DominatorTree & llvm::DomTreeUpdater::getDomTree ( )

Flush DomTree updates and return DomTree.

It also flush out of date updates applied by all available trees and flush Deleted BBs if both trees are up-to-date. It must only be called when it has a DomTree.

Definition at line 299 of file DomTreeUpdater.cpp.

References assert().

Referenced by hasPendingDeletedBB(), llvm::RewriteStatepointsForGC::runOnFunction(), and shouldSplitOnPredicatedArgument().

◆ getPostDomTree()

PostDominatorTree & llvm::DomTreeUpdater::getPostDomTree ( )

Flush PostDomTree updates and return PostDomTree.

It also flush out of date updates applied by all available trees and flush Deleted BBs if both trees are up-to-date. It must only be called when it has a PostDomTree.

Definition at line 306 of file DomTreeUpdater.cpp.

References assert().

Referenced by hasPendingDeletedBB().

◆ hasDomTree()

bool llvm::DomTreeUpdater::hasDomTree ( ) const

inline

Returns true if it holds a DominatorTree.

Definition at line 56 of file DomTreeUpdater.h.

Referenced by llvm::MergeBasicBlockIntoOnlyPred(), and shouldSplitOnPredicatedArgument().

◆ hasPendingDeletedBB()

bool llvm::DomTreeUpdater::hasPendingDeletedBB ( ) const

inline

Returns true if there is BasicBlock awaiting deletion.

The deletion will only happen until a flush event and all available trees are up-to-date. Returns false under Eager UpdateStrategy.

Definition at line 65 of file DomTreeUpdater.h.

References applyUpdates(), callbackDeleteBB(), deleteBB(), llvm::CallbackVH::deleted(), deleteEdge(), deleteEdgeRelaxed(), dump(), F(), flush(), From, function, getDomTree(), getPostDomTree(), hasPendingDomTreeUpdates(), hasPendingPostDomTreeUpdates(), hasPendingUpdates(), insertEdge(), insertEdgeRelaxed(), isBBPendingDeletion(), Kind, LLVM_DUMP_METHOD, and recalculate().

◆ hasPendingDomTreeUpdates()

bool llvm::DomTreeUpdater::hasPendingDomTreeUpdates ( ) const

Returns true if there are DominatorTree updates queued.

Returns false under Eager UpdateStrategy or DT is nullptr.

Definition at line 189 of file DomTreeUpdater.cpp.

References llvm::SmallVectorBase::size().

Referenced by hasPendingDeletedBB(), and hasPendingUpdates().

◆ hasPendingPostDomTreeUpdates()

bool llvm::DomTreeUpdater::hasPendingPostDomTreeUpdates ( ) const

Returns true if there are PostDominatorTree updates queued.

Returns false under Eager UpdateStrategy or PDT is nullptr.

Definition at line 195 of file DomTreeUpdater.cpp.

References llvm::SmallVectorBase::size().

Referenced by flush(), hasPendingDeletedBB(), and hasPendingUpdates().

◆ hasPendingUpdates()

bool llvm::DomTreeUpdater::hasPendingUpdates ( ) const

Returns true if either of DT or PDT is valid and the tree has at least one update pending.

If DT or PDT is nullptr it is treated as having no pending updates. This function does not check whether there is BasicBlock awaiting deletion. Returns false under Eager UpdateStrategy.

Definition at line 185 of file DomTreeUpdater.cpp.

References hasPendingDomTreeUpdates(), and hasPendingPostDomTreeUpdates().

Referenced by flush(), and hasPendingDeletedBB().

◆ hasPostDomTree()

bool llvm::DomTreeUpdater::hasPostDomTree ( ) const

inline

Returns true if it holds a PostDominatorTree.

Definition at line 59 of file DomTreeUpdater.h.

◆ insertEdge()

void llvm::DomTreeUpdater::insertEdge	(	BasicBlock *	From,
		BasicBlock *	To
	)

Notify all available trees on an edge insertion.

If both DT and PDT are nullptrs, this function discards the update. Under either Strategy, self-dominance update will be removed. The Eager Strategy applies the update immediately while the Lazy Strategy queues the update. It is recommended to only use this method when you have exactly one insertion (and no deletions). It is recommended to use applyUpdates() in all other cases. This function has to be called after making the update on the actual CFG. An internal functions checks if the edge exists in the CFG in DEBUG mode.

Definition at line 313 of file DomTreeUpdater.cpp.

References assert(), Eager, From, llvm::DominatorTreeBase< BasicBlock, false >::Insert, and llvm::DominatorTreeBase< NodeT, IsPostDom >::insertEdge().

Referenced by llvm::deleteDeadLoop(), eliminateRecursiveTailCall(), getOnlyLiveSuccessor(), and hasPendingDeletedBB().

◆ insertEdgeRelaxed()

void llvm::DomTreeUpdater::insertEdgeRelaxed	(	BasicBlock *	From,
		BasicBlock *	To
	)

Notify all available trees on an edge insertion.

Under either Strategy, the following updates will be discard silently

Invalid - Inserting an edge that does not exist in the CFG.
Self-dominance update.
Both DT and PDT are nullptrs. The Eager Strategy applies the update immediately while the Lazy Strategy queues the update. It is recommended to only use this method when you have exactly one insertion (and no deletions) and want to discard an invalid update.

Definition at line 338 of file DomTreeUpdater.cpp.

References Eager, From, llvm::DominatorTreeBase< BasicBlock, false >::Insert, and llvm::DominatorTreeBase< NodeT, IsPostDom >::insertEdge().

Referenced by hasPendingDeletedBB().

◆ isBBPendingDeletion()

bool llvm::DomTreeUpdater::isBBPendingDeletion ( llvm::BasicBlock * DelBB ) const

Returns true if DelBB is awaiting deletion.

Returns false under Eager UpdateStrategy.

Definition at line 201 of file DomTreeUpdater.cpp.

References Eager.

Referenced by hasPendingDeletedBB(), and llvm::removeUnreachableBlocks().

◆ isEager()

bool llvm::DomTreeUpdater::isEager ( ) const

inline

Returns true if the current strategy is Eager.

Definition at line 53 of file DomTreeUpdater.h.

References Eager.

◆ isLazy()

bool llvm::DomTreeUpdater::isLazy ( ) const

inline

Returns true if the current strategy is Lazy.

Definition at line 50 of file DomTreeUpdater.h.

References Lazy.

◆ recalculate()

void llvm::DomTreeUpdater::recalculate ( Function & F )

Recalculate all available trees and flush all BasicBlocks awaiting deletion immediately.

Definition at line 155 of file DomTreeUpdater.cpp.

References Eager, llvm::DominatorTreeBase< NodeT, IsPostDom >::recalculate(), and llvm::SmallVectorBase::size().

Referenced by eliminateRecursiveTailCall(), hasPendingDeletedBB(), and llvm::MergeBasicBlockIntoOnlyPred().

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

include/llvm/IR/DomTreeUpdater.h
lib/IR/DomTreeUpdater.cpp

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ UpdateStrategy

Constructor & Destructor Documentation

◆ DomTreeUpdater() [1/7]

◆ DomTreeUpdater() [2/7]

◆ DomTreeUpdater() [3/7]

◆ DomTreeUpdater() [4/7]

◆ DomTreeUpdater() [5/7]

◆ DomTreeUpdater() [6/7]

◆ DomTreeUpdater() [7/7]

◆ ~DomTreeUpdater()

Member Function Documentation

◆ applyUpdates()

◆ callbackDeleteBB()

◆ deleteBB()

◆ deleteEdge()

◆ deleteEdgeRelaxed()

◆ dump()

◆ flush()

◆ getDomTree()

◆ getPostDomTree()

◆ hasDomTree()

◆ hasPendingDeletedBB()

◆ hasPendingDomTreeUpdates()

◆ hasPendingPostDomTreeUpdates()

◆ hasPendingUpdates()

◆ hasPostDomTree()

◆ insertEdge()

◆ insertEdgeRelaxed()

◆ isBBPendingDeletion()

◆ isEager()

◆ isLazy()

◆ recalculate()