1 //===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the DomTreeUpdater class, which provides a uniform way
11 // to update dominator tree related data structures.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/IR/DomTreeUpdater.h"
16 #include "llvm/Analysis/PostDominators.h"
17 #include "llvm/IR/Dominators.h"
18 #include "llvm/Support/GenericDomTree.h"
24 bool DomTreeUpdater::isUpdateValid(
25 const DominatorTree::UpdateType Update) const {
26 const auto *From = Update.getFrom();
27 const auto *To = Update.getTo();
28 const auto Kind = Update.getKind();
30 // Discard updates by inspecting the current state of successors of From.
31 // Since isUpdateValid() must be called *after* the Terminator of From is
32 // altered we can determine if the update is unnecessary for batch updates
33 // or invalid for a single update.
34 const bool HasEdge = llvm::any_of(
35 successors(From), [To](const BasicBlock *B) { return B == To; });
37 // If the IR does not match the update,
38 // 1. In batch updates, this update is unnecessary.
39 // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
40 // Edge does not exist in IR.
41 if (Kind == DominatorTree::Insert && !HasEdge)
45 if (Kind == DominatorTree::Delete && HasEdge)
51 bool DomTreeUpdater::isSelfDominance(
52 const DominatorTree::UpdateType Update) const {
53 // Won't affect DomTree and PostDomTree.
54 return Update.getFrom() == Update.getTo();
57 bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
58 BasicBlock *From, BasicBlock *To) {
60 "Call applyLazyUpdate() when both DT and PDT are nullptrs.");
61 assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy &&
62 "Call applyLazyUpdate() with Eager strategy error");
63 // Analyze pending updates to determine if the update is unnecessary.
64 const DominatorTree::UpdateType Update = {Kind, From, To};
65 const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
66 ? DominatorTree::Insert
67 : DominatorTree::Delete,
69 // Only check duplicates in updates that are not applied by both trees.
71 PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
72 const auto E = PendUpdates.end();
74 assert(I <= E && "Iterator out of range.");
78 return false; // Discard duplicate updates.
81 // Update and Invert are both valid (equivalent to a no-op). Remove
82 // Invert from PendUpdates and discard the Update.
88 PendUpdates.push_back(Update); // Save the valid update.
92 void DomTreeUpdater::applyDomTreeUpdates() {
93 // No pending DomTreeUpdates.
94 if (Strategy != UpdateStrategy::Lazy || !DT)
97 // Only apply updates not are applied by DomTree.
98 if (hasPendingDomTreeUpdates()) {
99 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
100 const auto E = PendUpdates.end();
101 assert(I < E && "Iterator range invalid; there should be DomTree updates.");
102 DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
103 PendDTUpdateIndex = PendUpdates.size();
107 void DomTreeUpdater::flush() {
108 applyDomTreeUpdates();
109 applyPostDomTreeUpdates();
110 dropOutOfDateUpdates();
113 void DomTreeUpdater::applyPostDomTreeUpdates() {
114 // No pending PostDomTreeUpdates.
115 if (Strategy != UpdateStrategy::Lazy || !PDT)
118 // Only apply updates not are applied by PostDomTree.
119 if (hasPendingPostDomTreeUpdates()) {
120 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
121 const auto E = PendUpdates.end();
123 "Iterator range invalid; there should be PostDomTree updates.");
124 PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
125 PendPDTUpdateIndex = PendUpdates.size();
129 void DomTreeUpdater::tryFlushDeletedBB() {
130 if (!hasPendingUpdates())
131 forceFlushDeletedBB();
134 bool DomTreeUpdater::forceFlushDeletedBB() {
135 if (DeletedBBs.empty())
138 for (auto *BB : DeletedBBs) {
139 // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
140 // validateDeleteBB() removes all instructions of DelBB and adds an
141 // UnreachableInst as its terminator. So we check whether the BasicBlock to
142 // delete only has an UnreachableInst inside.
143 assert(BB->getInstList().size() == 1 &&
144 isa<UnreachableInst>(BB->getTerminator()) &&
145 "DelBB has been modified while awaiting deletion.");
146 BB->removeFromParent();
155 void DomTreeUpdater::recalculate(Function &F) {
157 if (Strategy == UpdateStrategy::Eager) {
165 // There is little performance gain if we pend the recalculation under
166 // Lazy UpdateStrategy so we recalculate available trees immediately.
168 // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
169 IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
171 // Because all trees are going to be up-to-date after recalculation,
172 // flush awaiting deleted BasicBlocks.
173 forceFlushDeletedBB();
179 // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
180 IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
181 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
182 dropOutOfDateUpdates();
185 bool DomTreeUpdater::hasPendingUpdates() const {
186 return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
189 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
192 return PendUpdates.size() != PendDTUpdateIndex;
195 bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
198 return PendUpdates.size() != PendPDTUpdateIndex;
201 bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
202 if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
204 return DeletedBBs.count(DelBB) != 0;
207 // The DT and PDT require the nodes related to updates
208 // are not deleted when update functions are called.
209 // So BasicBlock deletions must be pended when the
210 // UpdateStrategy is Lazy. When the UpdateStrategy is
211 // Eager, the BasicBlock will be deleted immediately.
212 void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
213 validateDeleteBB(DelBB);
214 if (Strategy == UpdateStrategy::Lazy) {
215 DeletedBBs.insert(DelBB);
219 DelBB->removeFromParent();
220 eraseDelBBNode(DelBB);
224 void DomTreeUpdater::callbackDeleteBB(
225 BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
226 validateDeleteBB(DelBB);
227 if (Strategy == UpdateStrategy::Lazy) {
228 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
229 DeletedBBs.insert(DelBB);
233 DelBB->removeFromParent();
234 eraseDelBBNode(DelBB);
239 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
240 if (DT && !IsRecalculatingDomTree)
241 if (DT->getNode(DelBB))
242 DT->eraseNode(DelBB);
244 if (PDT && !IsRecalculatingPostDomTree)
245 if (PDT->getNode(DelBB))
246 PDT->eraseNode(DelBB);
249 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
250 assert(DelBB && "Invalid push_back of nullptr DelBB.");
251 assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
252 // DelBB is unreachable and all its instructions are dead.
253 while (!DelBB->empty()) {
254 Instruction &I = DelBB->back();
255 // Replace used instructions with an arbitrary value (undef).
257 I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
258 DelBB->getInstList().pop_back();
260 // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
261 // Child of Function F it must contain valid IR.
262 new UnreachableInst(DelBB->getContext(), DelBB);
265 void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
266 bool ForceRemoveDuplicates) {
270 if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
271 SmallVector<DominatorTree::UpdateType, 8> Seen;
272 for (const auto U : Updates)
273 // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
277 [U](const DominatorTree::UpdateType S) { return S == U; }) &&
278 isUpdateValid(U) && !isSelfDominance(U)) {
280 if (Strategy == UpdateStrategy::Lazy)
281 applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
283 if (Strategy == UpdateStrategy::Lazy)
287 DT->applyUpdates(Seen);
289 PDT->applyUpdates(Seen);
294 DT->applyUpdates(Updates);
296 PDT->applyUpdates(Updates);
299 DominatorTree &DomTreeUpdater::getDomTree() {
300 assert(DT && "Invalid acquisition of a null DomTree");
301 applyDomTreeUpdates();
302 dropOutOfDateUpdates();
306 PostDominatorTree &DomTreeUpdater::getPostDomTree() {
307 assert(PDT && "Invalid acquisition of a null PostDomTree");
308 applyPostDomTreeUpdates();
309 dropOutOfDateUpdates();
313 void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
316 assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
317 "Inserted edge does not appear in the CFG");
323 // Won't affect DomTree and PostDomTree; discard update.
327 if (Strategy == UpdateStrategy::Eager) {
329 DT->insertEdge(From, To);
331 PDT->insertEdge(From, To);
335 applyLazyUpdate(DominatorTree::Insert, From, To);
338 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
345 if (!isUpdateValid({DominatorTree::Insert, From, To}))
348 if (Strategy == UpdateStrategy::Eager) {
350 DT->insertEdge(From, To);
352 PDT->insertEdge(From, To);
356 applyLazyUpdate(DominatorTree::Insert, From, To);
359 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
362 assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
363 "Deleted edge still exists in the CFG!");
369 // Won't affect DomTree and PostDomTree; discard update.
373 if (Strategy == UpdateStrategy::Eager) {
375 DT->deleteEdge(From, To);
377 PDT->deleteEdge(From, To);
381 applyLazyUpdate(DominatorTree::Delete, From, To);
384 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
391 if (!isUpdateValid({DominatorTree::Delete, From, To}))
394 if (Strategy == UpdateStrategy::Eager) {
396 DT->deleteEdge(From, To);
398 PDT->deleteEdge(From, To);
402 applyLazyUpdate(DominatorTree::Delete, From, To);
405 void DomTreeUpdater::dropOutOfDateUpdates() {
406 if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
411 // Drop all updates applied by both trees.
413 PendDTUpdateIndex = PendUpdates.size();
415 PendPDTUpdateIndex = PendUpdates.size();
417 const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
418 const auto B = PendUpdates.begin();
419 const auto E = PendUpdates.begin() + dropIndex;
420 assert(B <= E && "Iterator out of range.");
421 PendUpdates.erase(B, E);
422 // Calculate current index.
423 PendDTUpdateIndex -= dropIndex;
424 PendPDTUpdateIndex -= dropIndex;
427 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
428 LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
429 raw_ostream &OS = llvm::dbgs();
431 OS << "Available Trees: ";
436 OS << "PostDomTree ";
441 OS << "UpdateStrategy: ";
442 if (Strategy == UpdateStrategy::Eager) {
450 [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
451 ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
455 for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
457 OS << " " << Index << " : ";
459 if (U.getKind() == DominatorTree::Insert)
463 BasicBlock *From = U.getFrom();
465 auto S = From->getName();
466 if (!From->hasName())
468 OS << S << "(" << From << "), ";
472 BasicBlock *To = U.getTo();
474 auto S = To->getName();
477 OS << S << "(" << To << ")\n";
485 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
486 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
487 "Iterator out of range.");
488 OS << "Applied but not cleared DomTreeUpdates:\n";
489 printUpdates(PendUpdates.begin(), I);
490 OS << "Pending DomTreeUpdates:\n";
491 printUpdates(I, PendUpdates.end());
495 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
496 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
497 "Iterator out of range.");
498 OS << "Applied but not cleared PostDomTreeUpdates:\n";
499 printUpdates(PendUpdates.begin(), I);
500 OS << "Pending PostDomTreeUpdates:\n";
501 printUpdates(I, PendUpdates.end());
504 OS << "Pending DeletedBBs:\n";
506 for (auto BB : DeletedBBs) {
507 OS << " " << Index << " : ";
510 OS << BB->getName() << "(";
516 OS << "Pending Callbacks:\n";
518 for (auto BB : Callbacks) {
519 OS << " " << Index << " : ";
522 OS << BB->getName() << "(";