26bool DomTreeUpdater::isUpdateValid(
28 const auto *
From = Update.getFrom();
29 const auto *To = Update.getTo();
30 const auto Kind = Update.getKind();
52bool DomTreeUpdater::isSelfDominance(
55 return Update.getFrom() == Update.getTo();
58void DomTreeUpdater::applyDomTreeUpdates() {
65 const auto I = PendUpdates.
begin() + PendDTUpdateIndex;
66 const auto E = PendUpdates.
end();
67 assert(
I <
E &&
"Iterator range invalid; there should be DomTree updates.");
69 PendDTUpdateIndex = PendUpdates.
size();
74 applyDomTreeUpdates();
75 applyPostDomTreeUpdates();
76 dropOutOfDateUpdates();
79void DomTreeUpdater::applyPostDomTreeUpdates() {
86 const auto I = PendUpdates.
begin() + PendPDTUpdateIndex;
87 const auto E = PendUpdates.
end();
89 "Iterator range invalid; there should be PostDomTree updates.");
91 PendPDTUpdateIndex = PendUpdates.
size();
95void DomTreeUpdater::tryFlushDeletedBB() {
97 forceFlushDeletedBB();
100bool DomTreeUpdater::forceFlushDeletedBB() {
101 if (DeletedBBs.empty())
104 for (
auto *BB : DeletedBBs) {
109 assert(BB->size() == 1 && isa<UnreachableInst>(BB->getTerminator()) &&
110 "DelBB has been modified while awaiting deletion.");
111 BB->removeFromParent();
134 IsRecalculatingDomTree = IsRecalculatingPostDomTree =
true;
138 forceFlushDeletedBB();
145 IsRecalculatingDomTree = IsRecalculatingPostDomTree =
false;
146 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.
size();
147 dropOutOfDateUpdates();
157 return PendUpdates.
size() != PendDTUpdateIndex;
163 return PendUpdates.
size() != PendPDTUpdateIndex;
169 return DeletedBBs.contains(DelBB);
178 validateDeleteBB(DelBB);
180 DeletedBBs.insert(DelBB);
185 eraseDelBBNode(DelBB);
191 validateDeleteBB(DelBB);
193 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
194 DeletedBBs.insert(DelBB);
199 eraseDelBBNode(DelBB);
204void DomTreeUpdater::eraseDelBBNode(
BasicBlock *DelBB) {
205 if (DT && !IsRecalculatingDomTree)
209 if (PDT && !IsRecalculatingPostDomTree)
214void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
215 assert(DelBB &&
"Invalid push_back of nullptr DelBB.");
218 while (!DelBB->empty()) {
219 Instruction &
I = DelBB->back();
223 DelBB->back().eraseFromParent();
227 new UnreachableInst(DelBB->getContext(), DelBB);
236 for (
const auto &U : Updates)
237 if (!isSelfDominance(U))
256 for (
const auto &U : Updates) {
257 auto Edge = std::make_pair(U.getFrom(), U.getTo());
280 if (!isSelfDominance(U) && Seen.
count(Edge) == 0) {
285 if (isUpdateValid(U)) {
304 assert(DT &&
"Invalid acquisition of a null DomTree");
305 applyDomTreeUpdates();
306 dropOutOfDateUpdates();
311 assert(PDT &&
"Invalid acquisition of a null PostDomTree");
312 applyPostDomTreeUpdates();
313 dropOutOfDateUpdates();
317void DomTreeUpdater::dropOutOfDateUpdates() {
325 PendDTUpdateIndex = PendUpdates.
size();
327 PendPDTUpdateIndex = PendUpdates.
size();
329 const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
330 const auto B = PendUpdates.
begin();
331 const auto E = PendUpdates.
begin() + dropIndex;
332 assert(
B <=
E &&
"Iterator out of range.");
335 PendDTUpdateIndex -= dropIndex;
336 PendPDTUpdateIndex -= dropIndex;
339#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
343 OS <<
"Available Trees: ";
348 OS <<
"PostDomTree ";
353 OS <<
"UpdateStrategy: ";
367 for (
auto It = begin, ItEnd = end; It != ItEnd; ++It) {
377 auto S =
From->getName();
378 if (!
From->hasName())
380 OS << S <<
"(" <<
From <<
"), ";
389 OS << S <<
"(" << To <<
")\n";
397 const auto I = PendUpdates.
begin() + PendDTUpdateIndex;
399 "Iterator out of range.");
400 OS <<
"Applied but not cleared DomTreeUpdates:\n";
401 printUpdates(PendUpdates.
begin(),
I);
402 OS <<
"Pending DomTreeUpdates:\n";
403 printUpdates(
I, PendUpdates.
end());
407 const auto I = PendUpdates.
begin() + PendPDTUpdateIndex;
409 "Iterator out of range.");
410 OS <<
"Applied but not cleared PostDomTreeUpdates:\n";
411 printUpdates(PendUpdates.
begin(),
I);
412 OS <<
"Pending PostDomTreeUpdates:\n";
413 printUpdates(
I, PendUpdates.
end());
416 OS <<
"Pending DeletedBBs:\n";
418 for (
const auto *BB : DeletedBBs) {
422 OS << BB->getName() <<
"(";
428 OS <<
"Pending Callbacks:\n";
430 for (
const auto &BB : Callbacks) {
434 OS << BB->getName() <<
"(";
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
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),...
size_t size() const
size - Get the array size.
LLVM Basic Block Representation.
void removeFromParent()
Unlink 'this' from the containing function, but do not delete it.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
bool hasPendingDomTreeUpdates() const
Returns true if there are DominatorTree updates queued.
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
PostDominatorTree & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
bool hasPendingPostDomTreeUpdates() const
Returns true if there are PostDominatorTree updates queued.
bool isLazy() const
Returns true if the current strategy is Lazy.
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending.
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
cfg::Update< NodePtr > UpdateType
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef getName() const
Return a constant reference to the value's name.
This class implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
auto successors(const MachineBasicBlock *BB)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)