LLVM: llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT (original) (raw)

#include "[llvm/Analysis/GenericDomTreeUpdater.h](GenericDomTreeUpdater%5F8h%5Fsource.html)"

Public Types
enum class	UpdateStrategy : unsigned char { Eager = 0 , Lazy = 1 }
using	BasicBlockT = typename DomTreeT::NodeType
using	UpdateT = typename DomTreeT::UpdateType

Public Member Functions
	GenericDomTreeUpdater (UpdateStrategy Strategy_)
	GenericDomTreeUpdater (DomTreeT &DT_, UpdateStrategy Strategy_)
	GenericDomTreeUpdater (DomTreeT *DT_, UpdateStrategy Strategy_)
	GenericDomTreeUpdater (PostDomTreeT &PDT_, UpdateStrategy Strategy_)
	GenericDomTreeUpdater (PostDomTreeT *PDT_, UpdateStrategy Strategy_)
	GenericDomTreeUpdater (DomTreeT &DT_, PostDomTreeT &PDT_, UpdateStrategy Strategy_)
	GenericDomTreeUpdater (DomTreeT DT_, PostDomTreeT PDT_, UpdateStrategy Strategy_)
	~GenericDomTreeUpdater ()
bool	isLazy () const
	Returns true if the current strategy is Lazy.
bool	isEager () const
	Returns true if the current strategy is Eager.
bool	hasDomTree () const
	Returns true if it holds a DomTreeT.
bool	hasPostDomTree () const
	Returns true if it holds a PostDomTreeT.
bool	hasPendingDeletedBB () const
	Returns true if there is BasicBlockT awaiting deletion.
bool	isBBPendingDeletion (BasicBlockT *DelBB) const
	Returns true if DelBB is awaiting deletion.
bool	hasPendingUpdates () const
	Returns true if either of DT or PDT is valid and the tree has at least one update pending.
bool	hasPendingDomTreeUpdates () const
	Returns true if there are DomTreeT updates queued.
bool	hasPendingPostDomTreeUpdates () const
	Returns true if there are PostDomTreeT updates queued.
LLVM_DUMP_METHOD void	dump () const
	Debug method to help view the internal state of this class.
Mutation APIs
These methods provide APIs for submitting updates to the DomTreeT and the PostDominatorTree. Note: There are two strategies to update the DomTreeT and the PostDominatorTree: Eager UpdateStrategy: Updates are submitted and then flushed immediately. Lazy UpdateStrategy: Updates are submitted but only flushed when you explicitly call Flush APIs. It is recommended to use this update strategy when you submit a bunch of updates multiple times which can then add up to a large number of updates between two queries on the DomTreeT. The incremental updater can reschedule the updates or decide to recalculate the dominator tree in order to speedup the updating process depending on the number of updates. Although GenericDomTree provides several update primitives, it is not encouraged to use these APIs directly.
template
void	recalculate (FuncT &F)
	Notify DTU that the entry block was replaced.
void	applyUpdates (ArrayRef< UpdateT > Updates)
	Submit updates to all available trees.
void	splitCriticalEdge (BasicBlockT FromBB, BasicBlockT ToBB, BasicBlockT *NewBB)
	Apply updates that the critical edge (FromBB, ToBB) has been split with NewBB.
void	applyUpdatesPermissive (ArrayRef< UpdateT > Updates)
	Submit updates to all available trees.
Flush APIs
CAUTION! By the moment these flush APIs are called, the current CFG needs to be the same as the CFG which DTU is in sync with + all updates submitted.
DomTreeT &	getDomTree ()
	Flush DomTree updates and return DomTree.
PostDomTreeT &	getPostDomTree ()
	Flush PostDomTree updates and return PostDomTree.
void	flush ()
	Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.

Protected Member Functions
bool	isSelfDominance (UpdateT Update) const
	Returns true if the update is self dominance.
void	applyDomTreeUpdates ()
	Helper function to apply all pending DomTree updates.
void	applyPostDomTreeUpdates ()
	Helper function to apply all pending PostDomTree updates.
bool	isUpdateValid (UpdateT Update) const
	Returns true if the update appears in the LLVM IR.
void	eraseDelBBNode (BasicBlockT *DelBB)
	Erase Basic Block node before it is unlinked from Function in the DomTree and PostDomTree.
void	tryFlushDeletedBB ()
	Helper function to flush deleted BasicBlocks if all available trees are up-to-date.
void	dropOutOfDateUpdates ()
	Drop all updates applied by all available trees and delete BasicBlocks if all available trees are up-to-date.

Protected Attributes
SmallVector< DomTreeUpdate, 16 >	PendUpdates
size_t	PendDTUpdateIndex = 0
size_t	PendPDTUpdateIndex = 0
DomTreeT *	DT = nullptr
PostDomTreeT *	PDT = nullptr
const UpdateStrategy	Strategy
SmallPtrSet< BasicBlockT *, 8 >	DeletedBBs
bool	IsRecalculatingDomTree = false
bool	IsRecalculatingPostDomTree = false

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>
class llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >

Definition at line 24 of file GenericDomTreeUpdater.h.

◆ BasicBlockT

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ UpdateT

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ UpdateStrategy

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ GenericDomTreeUpdater() [2/7]

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ GenericDomTreeUpdater() [3/7]

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ GenericDomTreeUpdater() [4/7]

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ GenericDomTreeUpdater() [5/7]

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ GenericDomTreeUpdater() [6/7]

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::GenericDomTreeUpdater ( DomTreeT & DT_, PostDomTreeT & PDT_, UpdateStrategy Strategy_ )	inline

◆ GenericDomTreeUpdater() [7/7]

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::GenericDomTreeUpdater ( DomTreeT * DT_, PostDomTreeT * PDT_, UpdateStrategy Strategy_ )	inline

◆ ~GenericDomTreeUpdater()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ applyDomTreeUpdates()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ applyPostDomTreeUpdates()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ applyUpdates()

Submit updates to all available trees.

The Eager Strategy flushes updates immediately while the Lazy Strategy queues the updates.

Note: The "existence" of an edge in a CFG refers to the CFG which DTU is in sync with + all updates before that single update.

CAUTION!

It is required for the state of the LLVM IR to be updated before submitting the updates because the internal update routine will analyze the current state of the CFG to determine whether an update is valid.
It is illegal to submit any update that has already been submitted, i.e., you are supposed not to insert an existent edge or delete a nonexistent edge.

Definition at line 59 of file GenericDomTreeUpdaterImpl.h.

References DT, isSelfDominance(), Lazy, PDT, PendUpdates, llvm::ArrayRef< T >::size(), and Strategy.

Referenced by llvm::breakLoopBackedge(), llvm::changeToCall(), llvm::changeToInvokeAndSplitBasicBlock(), llvm::changeToUnreachable(), connectEpilogueVectorLoop(), llvm::ConstantFoldTerminator(), createUnreachableSwitchDefault(), llvm::DeleteDeadBlocks(), llvm::deleteDeadLoop(), llvm::DuplicateInstructionsInSplitBetween(), llvm::ehAwareSplitEdge(), eliminateDeadSwitchCases(), expandToSwitch(), llvm::ControlFlowHub::finalize(), foldCondBranchOnValueKnownInPredecessorImpl(), foldMemChr(), llvm::FoldReturnIntoUncondBranch(), foldTwoEntryPHINode(), llvm::MergeBlockIntoPredecessor(), mergeComparisons(), mergeCompatibleInvokesImpl(), mergeNestedCondBranch(), performBranchToCommonDestFolding(), processSwitch(), removeEmptyCleanup(), removeSwitchAfterSelectFold(), removeUndefIntroducingPredecessor(), llvm::removeUnwindEdge(), replaceConditionalBranchesOnConstant(), runImpl(), SimplifyCondBranchToCondBranch(), simplifySwitchLookup(), simplifySwitchOfCmpIntrinsic(), simplifySwitchOfPowersOfTwo(), simplifySwitchWhenUMin(), llvm::SplitBlockAndInsertIfThenElse(), llvm::splitBlockBefore(), SplitBlockImpl(), llvm::SplitCallBrEdge(), tailMergeBlocksWithSimilarFunctionTerminators(), tryToMergeLandingPad(), llvm::TryToSimplifyUncondBranchFromEmptyBlock(), tryWidenCondBranchToCondBranch(), llvm::UnrollLoop(), and UpdateAnalysisInformation().

◆ applyUpdatesPermissive()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

void llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::applyUpdatesPermissive	(	ArrayRef< UpdateT >	Updates	)

Submit updates to all available trees.

It will also

discard duplicated updates,
remove invalid updates. (Invalid updates means deletion of an edge that still exists or insertion of an edge that does not exist.) The Eager Strategy flushes updates immediately while the Lazy Strategy queues the updates.

Note: The "existence" of an edge in a CFG refers to the CFG which DTU is in sync with + all updates before that single update.

CAUTION!

It is required for the state of the LLVM IR to be updated before submitting the updates because the internal update routine will analyze the current state of the CFG to determine whether an update is valid.
It is illegal to submit any update that has already been submitted, i.e., you are supposed not to insert an existent edge or delete a nonexistent edge.
It is only legal to submit updates to an edge in the order CFG changes are made. The order you submit updates on different edges is not restricted.

Definition at line 80 of file GenericDomTreeUpdaterImpl.h.

References DT, llvm::SmallSet< T, N, C >::insert(), isLazy(), isSelfDominance(), isUpdateValid(), Lazy, PDT, PendUpdates, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and Strategy.

Referenced by llvm::MergeBasicBlockIntoOnlyPred(), processSwitch(), llvm::SCCPSolver::removeNonFeasibleEdges(), splitCallSite(), and llvm::UnrollAndJamLoop().

◆ dropOutOfDateUpdates()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

Drop all updates applied by all available trees and delete BasicBlocks if all available trees are up-to-date.

Definition at line 351 of file GenericDomTreeUpdaterImpl.h.

References assert(), B(), dropOutOfDateUpdates(), DT, E(), Eager, PDT, PendDTUpdateIndex, PendPDTUpdateIndex, PendUpdates, Strategy, and tryFlushDeletedBB().

Referenced by dropOutOfDateUpdates(), llvm::GenericDomTreeUpdater< DomTreeUpdater, DominatorTree, PostDominatorTree >::flush(), getDomTree(), getPostDomTree(), and recalculate().

◆ dump()

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

Definition at line 171 of file GenericDomTreeUpdaterImpl.h.

References assert(), llvm::dbgs(), DeletedBBs, DT, Eager, I, PDT, PendDTUpdateIndex, PendPDTUpdateIndex, PendUpdates, and Strategy.

◆ eraseDelBBNode()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ flush()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ getDomTree()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

DomTreeT & llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::getDomTree	(	)

Flush DomTree updates and return DomTree.

It flushes Deleted BBs if both trees are up-to-date. It must only be called when it has a DomTree.

Definition at line 153 of file GenericDomTreeUpdaterImpl.h.

References applyDomTreeUpdates(), assert(), dropOutOfDateUpdates(), and DT.

Referenced by runImpl(), llvm::RewriteStatepointsForGC::runOnFunction(), shouldSplitOnPredicatedArgument(), llvm::splitBlockBefore(), llvm::SplitCallBrEdge(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), and UpdateAnalysisInformation().

◆ getPostDomTree()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

PostDomTreeT & llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::getPostDomTree	(	)

◆ hasDomTree()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ hasPendingDeletedBB()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

Returns true if there is BasicBlockT 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 74 of file GenericDomTreeUpdater.h.

◆ hasPendingDomTreeUpdates()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ hasPendingPostDomTreeUpdates()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ hasPendingUpdates()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ hasPostDomTree()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ isBBPendingDeletion()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ isEager()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ isLazy()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ isSelfDominance()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ isUpdateValid()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ recalculate()

Notify DTU that the entry block was replaced.

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

Definition at line 28 of file GenericDomTreeUpdaterImpl.h.

References dropOutOfDateUpdates(), DT, Eager, F, IsRecalculatingDomTree, IsRecalculatingPostDomTree, PDT, PendDTUpdateIndex, PendPDTUpdateIndex, PendUpdates, and Strategy.

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

◆ splitCriticalEdge()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

void llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::splitCriticalEdge	(	BasicBlockT *	FromBB,
BasicBlockT *	ToBB,
BasicBlockT *	NewBB )

◆ tryFlushDeletedBB()

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ DeletedBBs

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ DT

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ IsRecalculatingDomTree

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ IsRecalculatingPostDomTree

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ PDT

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ PendDTUpdateIndex

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ PendPDTUpdateIndex

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ PendUpdates

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

◆ Strategy

template<typename DerivedT, typename DomTreeT, typename PostDomTreeT>

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

include/llvm/Analysis/GenericDomTreeUpdater.h
include/llvm/Analysis/DomTreeUpdater.h
include/llvm/Analysis/GenericDomTreeUpdaterImpl.h
include/llvm/CodeGen/MachineDomTreeUpdater.h
lib/Analysis/DomTreeUpdater.cpp
lib/CodeGen/MachineDomTreeUpdater.cpp