class DomTreeUpdater

Declaration

class DomTreeUpdater { /* full declaration omitted */ };

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:28

Member Variables

private SmallVector<DominatorTree::UpdateType, 16> PendUpdates
private size_t PendDTUpdateIndex = 0
private size_t PendPDTUpdateIndex = 0
private llvm::DominatorTree* DT = nullptr
private llvm::PostDominatorTree* PDT = nullptr
private const llvm::DomTreeUpdater::UpdateStrategy Strategy
private SmallPtrSet<llvm::BasicBlock*, 8> DeletedBBs
private std::vector<CallBackOnDeletion> Callbacks
private bool IsRecalculatingDomTree = false
private bool IsRecalculatingPostDomTree = false

Method Overview

Methods

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:33

Parameters

llvm::DominatorTree& DT_
llvm::DomTreeUpdater::UpdateStrategy Strategy_

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:35

Parameters

llvm::DominatorTree* DT_
llvm::DomTreeUpdater::UpdateStrategy Strategy_

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:37

Parameters

llvm::PostDominatorTree& PDT_
llvm::DomTreeUpdater::UpdateStrategy Strategy_

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:39

Parameters

llvm::PostDominatorTree* PDT_
llvm::DomTreeUpdater::UpdateStrategy Strategy_

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:41

Parameters

llvm::DominatorTree& DT_
llvm::PostDominatorTree& PDT_
llvm::DomTreeUpdater::UpdateStrategy Strategy_

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:44

Parameters

llvm::DominatorTree* DT_
llvm::PostDominatorTree* PDT_
llvm::DomTreeUpdater::UpdateStrategy Strategy_

DomTreeUpdater(
    llvm::DomTreeUpdater::UpdateStrategy
        Strategy_)

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:32

Parameters

llvm::DomTreeUpdater::UpdateStrategy Strategy_

void applyDomTreeUpdates()

Description

Helper function to apply all pending DomTree updates.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:241

void applyPostDomTreeUpdates()

Description

Helper function to apply all pending PostDomTree updates.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:244

void applyUpdates(
    ArrayRef<DominatorTree::UpdateType> Updates)

Description

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.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:123

Parameters

ArrayRef<DominatorTree::UpdateType> Updates

void applyUpdatesPermissive(
    ArrayRef<DominatorTree::UpdateType> Updates)

Description

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.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:146

Parameters

ArrayRef<DominatorTree::UpdateType> Updates

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

Description

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.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:170

Parameters

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

void deleteBB(llvm::BasicBlock* DelBB)

Description

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.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:160

Parameters

llvm::BasicBlock* DelBB

void dropOutOfDateUpdates()

Description

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:252

void dump() const

Description

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:200

void eraseDelBBNode(llvm::BasicBlock* DelBB)

Description

Erase Basic Block node that has been unlinked from Function in the DomTree and PostDomTree.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:256

Parameters

llvm::BasicBlock* DelBB

void flush()

Description

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

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:195

bool forceFlushDeletedBB()

Description

Returns true if at least one BasicBlock is deleted.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:238

llvm::DominatorTree& getDomTree()

Description

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.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:185

llvm::PostDominatorTree& getPostDomTree()

Description

Flush PostDomTree updates and return PostDomTree. It flushes Deleted BBs if both trees are up-to-date. It must only be called when it has a PostDomTree.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:190

bool hasDomTree() const

Description

Returns true if it holds a DominatorTree.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:57

bool hasPendingDeletedBB() const

Description

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.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:66

bool hasPendingDomTreeUpdates() const

Description

Returns true if there are DominatorTree updates queued. Returns false under Eager UpdateStrategy or DT is nullptr.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:81

bool hasPendingPostDomTreeUpdates() const

Description

Returns true if there are PostDominatorTree updates queued. Returns false under Eager UpdateStrategy or PDT is nullptr.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:85

bool hasPendingUpdates() const

Description

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.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:77

bool hasPostDomTree() const

Description

Returns true if it holds a PostDominatorTree.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:60

bool isBBPendingDeletion(
    llvm::BasicBlock* DelBB) const

Description

Returns true if DelBB is awaiting deletion. Returns false under Eager UpdateStrategy.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:70

Parameters

llvm::BasicBlock* DelBB

bool isEager() const

Description

Returns true if the current strategy is Eager.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:54

bool isLazy() const

Description

Returns true if the current strategy is Lazy.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:51

bool isSelfDominance(
    DominatorTree::UpdateType Update) const

Description

Returns true if the update is self dominance.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:264

Parameters

DominatorTree::UpdateType Update

bool isUpdateValid(
    DominatorTree::UpdateType Update) const

Description

Returns true if the update appears in the LLVM IR. It is used to check whether an update is valid in insertEdge/deleteEdge or is unnecessary in the batch update.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:261

Parameters

DominatorTree::UpdateType Update

void recalculate(llvm::Function& F)

Description

Notify DTU that the entry block was replaced. Recalculate all available trees and flush all BasicBlocks awaiting deletion immediately.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:151

Parameters

llvm::Function& F

void tryFlushDeletedBB()

Description

Helper function to flush deleted BasicBlocks if all available trees are up-to-date.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:248

void validateDeleteBB(llvm::BasicBlock* DelBB)

Description

First remove all the instructions of DelBB and then make sure DelBB has a valid terminator instruction which is necessary to have when DelBB still has to be inside of its parent Function while awaiting deletion under Lazy UpdateStrategy to prevent other routines from asserting the state of the IR is inconsistent. Assert if DelBB is nullptr or has predecessors.

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:235

Parameters

llvm::BasicBlock* DelBB

~DomTreeUpdater()

Declared at: llvm/include/llvm/Analysis/DomTreeUpdater.h:48