1//===- GenericDomTreeUpdater.h ----------------------------------*- C++ -*-===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// This file defines the GenericDomTreeUpdater class, which provides a uniform 10// way to update dominator tree related data structures. 12//===----------------------------------------------------------------------===// 14#ifndef LLVM_ANALYSIS_GENERICDOMTREEUPDATER_H 15#define LLVM_ANALYSIS_GENERICDOMTREEUPDATER_H 23template <
typename DerivedT,
typename DomTreeT,
typename PostDomTreeT>
25 DerivedT &derived() {
return *
static_cast<DerivedT *
>(
this); }
26const DerivedT &derived()
const{
27return *
static_cast<constDerivedT *
>(
this);
33usingUpdateT =
typename DomTreeT::UpdateType;
53// We cannot call into derived() here as it will already be destroyed. 55"Pending updates were not flushed by derived class.");
58 /// Returns true if the current strategy is Lazy. 61 /// Returns true if the current strategy is Eager. 64 /// Returns true if it holds a DomTreeT. 67 /// Returns true if it holds a PostDomTreeT. 70 /// Returns true if there is BasicBlockT awaiting deletion. 71 /// The deletion will only happen until a flush event and 72 /// all available trees are up-to-date. 73 /// Returns false under Eager UpdateStrategy. 76 /// Returns true if DelBB is awaiting deletion. 77 /// Returns false under Eager UpdateStrategy. 84 /// Returns true if either of DT or PDT is valid and the tree has at 85 /// least one update pending. If DT or PDT is nullptr it is treated 86 /// as having no pending updates. This function does not check 87 /// whether there is MachineBasicBlock awaiting deletion. 88 /// Returns false under Eager UpdateStrategy. 93 /// Returns true if there are DomTreeT updates queued. 94 /// Returns false under Eager UpdateStrategy or DT is nullptr. 101 /// Returns true if there are PostDomTreeT updates queued. 102 /// Returns false under Eager UpdateStrategy or PDT is nullptr. 110 /// \name Mutation APIs 112 /// These methods provide APIs for submitting updates to the DomTreeT and 113 /// the PostDominatorTree. 115 /// Note: There are two strategies to update the DomTreeT and the 116 /// PostDominatorTree: 117 /// 1. Eager UpdateStrategy: Updates are submitted and then flushed 119 /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you 120 /// explicitly call Flush APIs. It is recommended to use this update strategy 121 /// when you submit a bunch of updates multiple times which can then 122 /// add up to a large number of updates between two queries on the 123 /// DomTreeT. The incremental updater can reschedule the updates or 124 /// decide to recalculate the dominator tree in order to speedup the updating 125 /// process depending on the number of updates. 127 /// Although GenericDomTree provides several update primitives, 128 /// it is not encouraged to use these APIs directly. 130 /// Notify DTU that the entry block was replaced. 131 /// Recalculate all available trees and flush all BasicBlocks 132 /// awaiting deletion immediately. 135 /// Submit updates to all available trees. 136 /// The Eager Strategy flushes updates immediately while the Lazy Strategy 137 /// queues the updates. 139 /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is 140 /// in sync with + all updates before that single update. 143 /// 1. It is required for the state of the LLVM IR to be updated 144 /// *before* submitting the updates because the internal update routine will 145 /// analyze the current state of the CFG to determine whether an update 147 /// 2. It is illegal to submit any update that has already been submitted, 148 /// i.e., you are supposed not to insert an existent edge or delete a 149 /// nonexistent edge. 152 /// Apply updates that the critical edge (FromBB, ToBB) has been 153 /// split with NewBB. 157 /// Submit updates to all available trees. It will also 158 /// 1. discard duplicated updates, 159 /// 2. remove invalid updates. (Invalid updates means deletion of an edge that 160 /// still exists or insertion of an edge that does not exist.) 161 /// The Eager Strategy flushes updates immediately while the Lazy Strategy 162 /// queues the updates. 164 /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is 165 /// in sync with + all updates before that single update. 168 /// 1. It is required for the state of the LLVM IR to be updated 169 /// *before* submitting the updates because the internal update routine will 170 /// analyze the current state of the CFG to determine whether an update 172 /// 2. It is illegal to submit any update that has already been submitted, 173 /// i.e., you are supposed not to insert an existent edge or delete a 174 /// nonexistent edge. 175 /// 3. It is only legal to submit updates to an edge in the order CFG changes 176 /// are made. The order you submit updates on different edges is not 185 /// CAUTION! By the moment these flush APIs are called, the current CFG needs 186 /// to be the same as the CFG which DTU is in sync with + all updates 189 /// Flush DomTree updates and return DomTree. 190 /// It flushes Deleted BBs if both trees are up-to-date. 191 /// It must only be called when it has a DomTree. 194 /// Flush PostDomTree updates and return PostDomTree. 195 /// It flushes Deleted BBs if both trees are up-to-date. 196 /// It must only be called when it has a PostDomTree. 199 /// Apply all pending updates to available trees and flush all BasicBlocks 200 /// awaiting deletion. 210 /// Debug method to help view the internal state of this class. 214 /// Helper structure used to hold all the basic blocks 215 /// involved in the split of a critical edge. 235 DomTreeT *
DT =
nullptr;
236 PostDomTreeT *
PDT =
nullptr;
242 /// Returns true if the update is self dominance. 244// Won't affect DomTree and PostDomTree. 245return Update.getFrom() == Update.getTo();
248 /// Helper function to apply all pending DomTree updates. 251 /// Helper function to apply all pending PostDomTree updates. 254 /// Returns true if the update appears in the LLVM IR. 255 /// It is used to check whether an update is valid in 256 /// insertEdge/deleteEdge or is unnecessary in the batch update. 259 /// Erase Basic Block node before it is unlinked from Function 260 /// in the DomTree and PostDomTree. 263 /// Helper function to flush deleted BasicBlocks if all available 264 /// trees are up-to-date. 267 /// Drop all updates applied by all available trees and delete BasicBlocks if 268 /// all available trees are up-to-date. 274template <
bool IsForward>
void applyUpdatesImpl();
279#endif// LLVM_ANALYSIS_GENERICDOMTREEUPDATER_H static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
SmallPtrSet< BasicBlockT *, 8 > DeletedBBs
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
PostDomTreeT & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
bool isEager() const
Returns true if the current strategy is Eager.
void applyPostDomTreeUpdates()
Helper function to apply all pending PostDomTree updates.
void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
GenericDomTreeUpdater(PostDomTreeT &PDT_, UpdateStrategy Strategy_)
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
bool IsRecalculatingPostDomTree
void eraseDelBBNode(BasicBlockT *DelBB)
Erase Basic Block node before it is unlinked from Function in the DomTree and PostDomTree.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks 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 hasDomTree() const
Returns true if it holds a DomTreeT.
bool isSelfDominance(UpdateT Update) const
Returns true if the update is self dominance.
const UpdateStrategy Strategy
typename DomTreeT::UpdateType UpdateT
bool hasPostDomTree() const
Returns true if it holds a PostDomTreeT.
typename DomTreeT::NodeType BasicBlockT
GenericDomTreeUpdater(DomTreeT &DT_, UpdateStrategy Strategy_)
void tryFlushDeletedBB()
Helper function to flush deleted BasicBlocks if all available trees are up-to-date.
bool isBBPendingDeletion(BasicBlockT *DelBB) const
Returns true if DelBB is awaiting deletion.
GenericDomTreeUpdater(DomTreeT *DT_, PostDomTreeT *PDT_, UpdateStrategy Strategy_)
void dropOutOfDateUpdates()
Drop all updates applied by all available trees and delete BasicBlocks if all available trees are up-...
bool IsRecalculatingDomTree
bool hasPendingPostDomTreeUpdates() const
Returns true if there are PostDomTreeT updates queued.
size_t PendPDTUpdateIndex
void recalculate(FuncT &F)
Notify DTU that the entry block was replaced.
void splitCriticalEdge(BasicBlockT *FromBB, BasicBlockT *ToBB, BasicBlockT *NewBB)
Apply updates that the critical edge (FromBB, ToBB) has been split with NewBB.
void applyDomTreeUpdates()
Helper function to apply all pending DomTree updates.
GenericDomTreeUpdater(UpdateStrategy Strategy_)
GenericDomTreeUpdater(DomTreeT &DT_, PostDomTreeT &PDT_, UpdateStrategy Strategy_)
GenericDomTreeUpdater(PostDomTreeT *PDT_, UpdateStrategy Strategy_)
bool isUpdateValid(UpdateT Update) const
Returns true if the update appears in the LLVM IR.
SmallVector< DomTreeUpdate, 16 > PendUpdates
bool hasPendingDeletedBB() const
Returns true if there is BasicBlockT awaiting deletion.
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
bool hasPendingDomTreeUpdates() const
Returns true if there are DomTreeT updates queued.
GenericDomTreeUpdater(DomTreeT *DT_, UpdateStrategy Strategy_)
bool isLazy() const
Returns true if the current strategy is Lazy.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This is an optimization pass for GlobalISel generic memory operations.
Helper structure used to hold all the basic blocks involved in the split of a critical edge.
DomTreeUpdate(CriticalEdge E)
DomTreeUpdate(UpdateT Update)
