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

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

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

  1. Invalid - Deleting an edge that still exists in the CFG.
  2. Self-dominance update.
  3. 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

◆ 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

  1. Invalid - Inserting an edge that does not exist in the CFG.
  2. Self-dominance update.
  3. 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: