LLVM  9.0.0svn
Classes | Public Types | Public Member Functions | List of all members
llvm::DomTreeUpdater Class Reference

#include "llvm/Analysis/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...
 
LLVM_DUMP_METHOD void dump () const
 Debug method to help view the internal state of this class. More...
 
Mutation APIs

These methods provide APIs for submitting updates to the DominatorTree and the PostDominatorTree.

Note: There are two strategies to update the DominatorTree and the PostDominatorTree:

  1. Eager UpdateStrategy: Updates are submitted and then flushed immediately.
  2. 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 DominatorTree. 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.

void applyUpdates (ArrayRef< DominatorTree::UpdateType > Updates)
 Submit updates to all available trees. More...
 
void applyUpdatesPermissive (ArrayRef< DominatorTree::UpdateType > Updates)
 Submit updates to all available trees. More...
 
void recalculate (Function &F)
 Notify DTU that the entry block was replaced. More...
 
 LLVM_ATTRIBUTE_DEPRECATED (void insertEdge(BasicBlock *From, BasicBlock *To), "Use applyUpdates() instead.")
 
 LLVM_ATTRIBUTE_DEPRECATED (void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To), "Use applyUpdatesPermissive() instead.")
 
 LLVM_ATTRIBUTE_DEPRECATED (void deleteEdge(BasicBlock *From, BasicBlock *To), "Use applyUpdates() instead.")
 
 LLVM_ATTRIBUTE_DEPRECATED (void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To), "Use applyUpdatesPermissive() instead.")
 
void deleteBB (BasicBlock *DelBB)
 Delete DelBB. More...
 
void callbackDeleteBB (BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
 Delete DelBB. More...
 
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.

DominatorTreegetDomTree ()
 Flush DomTree updates and return DomTree. More...
 
PostDominatorTreegetPostDomTree ()
 Flush PostDomTree updates and return PostDomTree. More...
 
void flush ()
 Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion. More...
 

Detailed Description

Definition at line 26 of file DomTreeUpdater.h.

Member Enumeration Documentation

◆ UpdateStrategy

Enumerator
Eager 
Lazy 

Definition at line 28 of file DomTreeUpdater.h.

Constructor & Destructor Documentation

◆ DomTreeUpdater() [1/7]

llvm::DomTreeUpdater::DomTreeUpdater ( UpdateStrategy  Strategy_)
inlineexplicit

Definition at line 30 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [2/7]

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

Definition at line 31 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [3/7]

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

Definition at line 33 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [4/7]

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

Definition at line 35 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [5/7]

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

Definition at line 37 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [6/7]

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

Definition at line 39 of file DomTreeUpdater.h.

◆ DomTreeUpdater() [7/7]

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

Definition at line 42 of file DomTreeUpdater.h.

◆ ~DomTreeUpdater()

llvm::DomTreeUpdater::~DomTreeUpdater ( )
inline

Definition at line 46 of file DomTreeUpdater.h.

References flush().

Member Function Documentation

◆ applyUpdates()

void llvm::DomTreeUpdater::applyUpdates ( ArrayRef< DominatorTree::UpdateType Updates)

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!

  1. 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.
  2. 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 231 of file DomTreeUpdater.cpp.

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

Referenced by llvm::deleteDeadLoop(), llvm::DuplicateInstructionsInSplitBetween(), eliminateRecursiveTailCall(), llvm::FoldReturnIntoUncondBranch(), LoopFuser::fuseLoops(), getInnermostLoopFor(), hasPendingDeletedBB(), and isUnconditionalBranch().

◆ applyUpdatesPermissive()

void llvm::DomTreeUpdater::applyUpdatesPermissive ( ArrayRef< DominatorTree::UpdateType Updates)

Submit updates to all available trees.

It will also

  1. discard duplicated updates,
  2. 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!

  1. 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.
  2. 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.
  3. 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 249 of file DomTreeUpdater.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), llvm::SmallSet< T, N, C >::count(), llvm::SmallSet< T, N, C >::insert(), isLazy(), Lazy, llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::changeToUnreachable(), llvm::DeleteDeadBlocks(), hasPendingDeletedBB(), llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), llvm::RemovePredecessorAndSimplify(), llvm::removeUnreachableBlocks(), llvm::removeUnwindEdge(), splitCallSite(), 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 190 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 178 of file DomTreeUpdater.cpp.

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

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

◆ dump()

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

◆ flush()

void llvm::DomTreeUpdater::flush ( )

◆ getDomTree()

DominatorTree & llvm::DomTreeUpdater::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 303 of file DomTreeUpdater.cpp.

References assert().

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

◆ getPostDomTree()

PostDominatorTree & llvm::DomTreeUpdater::getPostDomTree ( )

◆ hasDomTree()

bool llvm::DomTreeUpdater::hasDomTree ( ) const
inline

Returns true if it holds a DominatorTree.

Definition at line 55 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 64 of file DomTreeUpdater.h.

References applyUpdates(), applyUpdatesPermissive(), callbackDeleteBB(), deleteBB(), llvm::CallbackVH::deleted(), dump(), F(), flush(), From, function, getDomTree(), getPostDomTree(), hasPendingDomTreeUpdates(), hasPendingPostDomTreeUpdates(), hasPendingUpdates(), isBBPendingDeletion(), LLVM_ATTRIBUTE_DEPRECATED(), 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 155 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 161 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 151 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 58 of file DomTreeUpdater.h.

◆ isBBPendingDeletion()

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

Returns true if DelBB is awaiting deletion.

Returns false under Eager UpdateStrategy.

Definition at line 167 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 52 of file DomTreeUpdater.h.

References Eager.

◆ isLazy()

bool llvm::DomTreeUpdater::isLazy ( ) const
inline

Returns true if the current strategy is Lazy.

Definition at line 49 of file DomTreeUpdater.h.

References Lazy.

Referenced by applyUpdatesPermissive().

◆ LLVM_ATTRIBUTE_DEPRECATED() [1/4]

llvm::DomTreeUpdater::LLVM_ATTRIBUTE_DEPRECATED ( void   insertEdgeBasicBlock *From, BasicBlock *To,
"Use applyUpdates() instead."   
)
Deprecated:
{ Submit an edge insertion to all available trees.

The Eager Strategy flushes this update immediately while the Lazy Strategy queues the update. An internal function checks if the edge exists in the CFG in DEBUG mode. CAUTION! This function has to be called after making the update on the actual CFG. It is illegal to submit any update that has already been applied. }

Referenced by hasPendingDeletedBB().

◆ LLVM_ATTRIBUTE_DEPRECATED() [2/4]

llvm::DomTreeUpdater::LLVM_ATTRIBUTE_DEPRECATED ( void   insertEdgeRelaxedBasicBlock *From, BasicBlock *To,
"Use applyUpdatesPermissive() instead."   
)
Deprecated:
{Submit an edge insertion to all available trees.

Under either Strategy, an invalid update will be discard silently. Invalid update means inserting an edge that does not exist in the CFG. The Eager Strategy flushes this update immediately while the Lazy Strategy queues the update. It is only recommended to use this method when you want to discard an invalid update. CAUTION! It is illegal to submit any update that has already been submitted. }

◆ LLVM_ATTRIBUTE_DEPRECATED() [3/4]

llvm::DomTreeUpdater::LLVM_ATTRIBUTE_DEPRECATED ( void   deleteEdgeBasicBlock *From, BasicBlock *To,
"Use applyUpdates() instead."   
)
Deprecated:
{ Submit an edge deletion to all available trees.

The Eager Strategy flushes this update immediately while the Lazy Strategy queues the update. An internal function checks if the edge doesn't exist in the CFG in DEBUG mode. CAUTION! This function has to be called after making the update on the actual CFG. It is illegal to submit any update that has already been submitted. }

◆ LLVM_ATTRIBUTE_DEPRECATED() [4/4]

llvm::DomTreeUpdater::LLVM_ATTRIBUTE_DEPRECATED ( void   deleteEdgeRelaxedBasicBlock *From, BasicBlock *To,
"Use applyUpdatesPermissive() instead."   
)
Deprecated:
{ Submit an edge deletion to all available trees.

Under either Strategy, an invalid update will be discard silently. Invalid update means deleting an edge that exists in the CFG. The Eager Strategy flushes this update immediately while the Lazy Strategy queues the update. It is only recommended to use this method when you want to discard an invalid update. CAUTION! It is illegal to submit any update that has already been submitted. }

◆ recalculate()

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

Notify DTU that the entry block was replaced.

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

Definition at line 121 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: