1 //===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- 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 implements the DomTreeUpdater class, which provides a uniform way
10 // to update dominator tree related data structures.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/DomTreeUpdater.h"
15 #include "llvm/ADT/SmallSet.h"
16 #include "llvm/Analysis/PostDominators.h"
17 #include "llvm/IR/Dominators.h"
18 #include "llvm/Support/GenericDomTree.h"
25 bool DomTreeUpdater::isUpdateValid(
26 const DominatorTree::UpdateType Update) const {
27 const auto *From = Update.getFrom();
28 const auto *To = Update.getTo();
29 const auto Kind = Update.getKind();
31 // Discard updates by inspecting the current state of successors of From.
32 // Since isUpdateValid() must be called *after* the Terminator of From is
33 // altered we can determine if the update is unnecessary for batch updates
34 // or invalid for a single update.
35 const bool HasEdge = llvm::any_of(
36 successors(From), [To](const BasicBlock *B) { return B == To; });
38 // If the IR does not match the update,
39 // 1. In batch updates, this update is unnecessary.
40 // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
41 // Edge does not exist in IR.
42 if (Kind == DominatorTree::Insert && !HasEdge)
46 if (Kind == DominatorTree::Delete && HasEdge)
52 bool DomTreeUpdater::isSelfDominance(
53 const DominatorTree::UpdateType Update) const {
54 // Won't affect DomTree and PostDomTree.
55 return Update.getFrom() == Update.getTo();
58 void DomTreeUpdater::applyDomTreeUpdates() {
59 // No pending DomTreeUpdates.
60 if (Strategy != UpdateStrategy::Lazy || !DT)
63 // Only apply updates not are applied by DomTree.
64 if (hasPendingDomTreeUpdates()) {
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.");
68 DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
69 PendDTUpdateIndex = PendUpdates.size();
73 void DomTreeUpdater::flush() {
74 applyDomTreeUpdates();
75 applyPostDomTreeUpdates();
76 dropOutOfDateUpdates();
79 void DomTreeUpdater::applyPostDomTreeUpdates() {
80 // No pending PostDomTreeUpdates.
81 if (Strategy != UpdateStrategy::Lazy || !PDT)
84 // Only apply updates not are applied by PostDomTree.
85 if (hasPendingPostDomTreeUpdates()) {
86 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
87 const auto E = PendUpdates.end();
89 "Iterator range invalid; there should be PostDomTree updates.");
90 PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
91 PendPDTUpdateIndex = PendUpdates.size();
95 void DomTreeUpdater::tryFlushDeletedBB() {
96 if (!hasPendingUpdates())
97 forceFlushDeletedBB();
100 bool DomTreeUpdater::forceFlushDeletedBB() {
101 if (DeletedBBs.empty())
104 for (auto *BB : DeletedBBs) {
105 // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
106 // validateDeleteBB() removes all instructions of DelBB and adds an
107 // UnreachableInst as its terminator. So we check whether the BasicBlock to
108 // delete only has an UnreachableInst inside.
109 assert(BB->getInstList().size() == 1 &&
110 isa<UnreachableInst>(BB->getTerminator()) &&
111 "DelBB has been modified while awaiting deletion.");
112 BB->removeFromParent();
121 void DomTreeUpdater::recalculate(Function &F) {
123 if (Strategy == UpdateStrategy::Eager) {
131 // There is little performance gain if we pend the recalculation under
132 // Lazy UpdateStrategy so we recalculate available trees immediately.
134 // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
135 IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
137 // Because all trees are going to be up-to-date after recalculation,
138 // flush awaiting deleted BasicBlocks.
139 forceFlushDeletedBB();
145 // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
146 IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
147 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
148 dropOutOfDateUpdates();
151 bool DomTreeUpdater::hasPendingUpdates() const {
152 return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
155 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
158 return PendUpdates.size() != PendDTUpdateIndex;
161 bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
164 return PendUpdates.size() != PendPDTUpdateIndex;
167 bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
168 if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
170 return DeletedBBs.count(DelBB) != 0;
173 // The DT and PDT require the nodes related to updates
174 // are not deleted when update functions are called.
175 // So BasicBlock deletions must be pended when the
176 // UpdateStrategy is Lazy. When the UpdateStrategy is
177 // Eager, the BasicBlock will be deleted immediately.
178 void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
179 validateDeleteBB(DelBB);
180 if (Strategy == UpdateStrategy::Lazy) {
181 DeletedBBs.insert(DelBB);
185 DelBB->removeFromParent();
186 eraseDelBBNode(DelBB);
190 void DomTreeUpdater::callbackDeleteBB(
191 BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
192 validateDeleteBB(DelBB);
193 if (Strategy == UpdateStrategy::Lazy) {
194 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
195 DeletedBBs.insert(DelBB);
199 DelBB->removeFromParent();
200 eraseDelBBNode(DelBB);
205 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
206 if (DT && !IsRecalculatingDomTree)
207 if (DT->getNode(DelBB))
208 DT->eraseNode(DelBB);
210 if (PDT && !IsRecalculatingPostDomTree)
211 if (PDT->getNode(DelBB))
212 PDT->eraseNode(DelBB);
215 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
216 assert(DelBB && "Invalid push_back of nullptr DelBB.");
217 assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
218 // DelBB is unreachable and all its instructions are dead.
219 while (!DelBB->empty()) {
220 Instruction &I = DelBB->back();
221 // Replace used instructions with an arbitrary value (undef).
223 I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
224 DelBB->getInstList().pop_back();
226 // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
227 // Child of Function F it must contain valid IR.
228 new UnreachableInst(DelBB->getContext(), DelBB);
231 void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
235 if (Strategy == UpdateStrategy::Lazy) {
236 for (const auto U : Updates)
237 if (!isSelfDominance(U))
238 PendUpdates.push_back(U);
244 DT->applyUpdates(Updates);
246 PDT->applyUpdates(Updates);
249 void DomTreeUpdater::applyUpdatesPermissive(
250 ArrayRef<DominatorTree::UpdateType> Updates) {
254 SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
255 SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
256 for (const auto U : Updates) {
257 auto Edge = std::make_pair(U.getFrom(), U.getTo());
258 // Because it is illegal to submit updates that have already been applied
259 // and updates to an edge need to be strictly ordered,
260 // it is safe to infer the existence of an edge from the first update
262 // If the first update to an edge is "Delete", it means that the edge
263 // existed before. If the first update to an edge is "Insert", it means
264 // that the edge didn't exist before.
266 // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
268 // 1. it is illegal to submit updates that have already been applied,
269 // i.e., user cannot delete an nonexistent edge,
270 // 2. updates to an edge need to be strictly ordered,
271 // So, initially edge A -> B existed.
272 // We can then safely ignore future updates to this edge and directly
273 // inspect the current CFG:
274 // a. If the edge still exists, because the user cannot insert an existent
275 // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
276 // resulted in a no-op. DTU won't submit any update in this case.
277 // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
278 // actually happened but {Insert, A, B} was an invalid update which never
279 // happened. DTU will submit {Delete, A, B} in this case.
280 if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
282 // If the update doesn't appear in the CFG, it means that
283 // either the change isn't made or relevant operations
284 // result in a no-op.
285 if (isUpdateValid(U)) {
287 PendUpdates.push_back(U);
289 DeduplicatedUpdates.push_back(U);
294 if (Strategy == UpdateStrategy::Lazy)
298 DT->applyUpdates(DeduplicatedUpdates);
300 PDT->applyUpdates(DeduplicatedUpdates);
303 DominatorTree &DomTreeUpdater::getDomTree() {
304 assert(DT && "Invalid acquisition of a null DomTree");
305 applyDomTreeUpdates();
306 dropOutOfDateUpdates();
310 PostDominatorTree &DomTreeUpdater::getPostDomTree() {
311 assert(PDT && "Invalid acquisition of a null PostDomTree");
312 applyPostDomTreeUpdates();
313 dropOutOfDateUpdates();
317 void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
320 assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
321 "Inserted edge does not appear in the CFG");
327 // Won't affect DomTree and PostDomTree; discard update.
331 if (Strategy == UpdateStrategy::Eager) {
333 DT->insertEdge(From, To);
335 PDT->insertEdge(From, To);
339 PendUpdates.push_back({DominatorTree::Insert, From, To});
342 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
349 if (!isUpdateValid({DominatorTree::Insert, From, To}))
352 if (Strategy == UpdateStrategy::Eager) {
354 DT->insertEdge(From, To);
356 PDT->insertEdge(From, To);
360 PendUpdates.push_back({DominatorTree::Insert, From, To});
363 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
366 assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
367 "Deleted edge still exists in the CFG!");
373 // Won't affect DomTree and PostDomTree; discard update.
377 if (Strategy == UpdateStrategy::Eager) {
379 DT->deleteEdge(From, To);
381 PDT->deleteEdge(From, To);
385 PendUpdates.push_back({DominatorTree::Delete, From, To});
388 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
395 if (!isUpdateValid({DominatorTree::Delete, From, To}))
398 if (Strategy == UpdateStrategy::Eager) {
400 DT->deleteEdge(From, To);
402 PDT->deleteEdge(From, To);
406 PendUpdates.push_back({DominatorTree::Delete, From, To});
409 void DomTreeUpdater::dropOutOfDateUpdates() {
410 if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
415 // Drop all updates applied by both trees.
417 PendDTUpdateIndex = PendUpdates.size();
419 PendPDTUpdateIndex = PendUpdates.size();
421 const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
422 const auto B = PendUpdates.begin();
423 const auto E = PendUpdates.begin() + dropIndex;
424 assert(B <= E && "Iterator out of range.");
425 PendUpdates.erase(B, E);
426 // Calculate current index.
427 PendDTUpdateIndex -= dropIndex;
428 PendPDTUpdateIndex -= dropIndex;
431 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
432 LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
433 raw_ostream &OS = llvm::dbgs();
435 OS << "Available Trees: ";
440 OS << "PostDomTree ";
445 OS << "UpdateStrategy: ";
446 if (Strategy == UpdateStrategy::Eager) {
454 [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
455 ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
459 for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
461 OS << " " << Index << " : ";
463 if (U.getKind() == DominatorTree::Insert)
467 BasicBlock *From = U.getFrom();
469 auto S = From->getName();
470 if (!From->hasName())
472 OS << S << "(" << From << "), ";
476 BasicBlock *To = U.getTo();
478 auto S = To->getName();
481 OS << S << "(" << To << ")\n";
489 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
490 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
491 "Iterator out of range.");
492 OS << "Applied but not cleared DomTreeUpdates:\n";
493 printUpdates(PendUpdates.begin(), I);
494 OS << "Pending DomTreeUpdates:\n";
495 printUpdates(I, PendUpdates.end());
499 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
500 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
501 "Iterator out of range.");
502 OS << "Applied but not cleared PostDomTreeUpdates:\n";
503 printUpdates(PendUpdates.begin(), I);
504 OS << "Pending PostDomTreeUpdates:\n";
505 printUpdates(I, PendUpdates.end());
508 OS << "Pending DeletedBBs:\n";
510 for (auto BB : DeletedBBs) {
511 OS << " " << Index << " : ";
514 OS << BB->getName() << "(";
520 OS << "Pending Callbacks:\n";
522 for (auto BB : Callbacks) {
523 OS << " " << Index << " : ";
526 OS << BB->getName() << "(";