1 //===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the DomTreeUpdater class, which provides a uniform way
10 // to update dominator tree related data structures.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Analysis/DomTreeUpdater.h"
15 #include "llvm/ADT/SmallSet.h"
16 #include "llvm/Analysis/GenericDomTreeUpdaterImpl.h"
17 #include "llvm/Analysis/PostDominators.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/Support/GenericDomTree.h"
21 #include <algorithm>
22 #include <functional>
23 #include <utility>
24
25 namespace llvm {
26
27 template class GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,
28 PostDominatorTree>;
29
30 template void
31 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,
32 PostDominatorTree>::recalculate(Function &F);
33
forceFlushDeletedBB()34 bool DomTreeUpdater::forceFlushDeletedBB() {
35 if (DeletedBBs.empty())
36 return false;
37
38 for (auto *BB : DeletedBBs) {
39 // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
40 // validateDeleteBB() removes all instructions of DelBB and adds an
41 // UnreachableInst as its terminator. So we check whether the BasicBlock to
42 // delete only has an UnreachableInst inside.
43 assert(BB->size() == 1 && isa<UnreachableInst>(BB->getTerminator()) &&
44 "DelBB has been modified while awaiting deletion.");
45 BB->removeFromParent();
46 eraseDelBBNode(BB);
47 delete BB;
48 }
49 DeletedBBs.clear();
50 Callbacks.clear();
51 return true;
52 }
53
54 // The DT and PDT require the nodes related to updates
55 // are not deleted when update functions are called.
56 // So BasicBlock deletions must be pended when the
57 // UpdateStrategy is Lazy. When the UpdateStrategy is
58 // Eager, the BasicBlock will be deleted immediately.
deleteBB(BasicBlock * DelBB)59 void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
60 validateDeleteBB(DelBB);
61 if (Strategy == UpdateStrategy::Lazy) {
62 DeletedBBs.insert(DelBB);
63 return;
64 }
65
66 DelBB->removeFromParent();
67 eraseDelBBNode(DelBB);
68 delete DelBB;
69 }
70
callbackDeleteBB(BasicBlock * DelBB,std::function<void (BasicBlock *)> Callback)71 void DomTreeUpdater::callbackDeleteBB(
72 BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
73 validateDeleteBB(DelBB);
74 if (Strategy == UpdateStrategy::Lazy) {
75 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
76 DeletedBBs.insert(DelBB);
77 return;
78 }
79
80 DelBB->removeFromParent();
81 eraseDelBBNode(DelBB);
82 Callback(DelBB);
83 delete DelBB;
84 }
85
validateDeleteBB(BasicBlock * DelBB)86 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
87 assert(DelBB && "Invalid push_back of nullptr DelBB.");
88 assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
89 // DelBB is unreachable and all its instructions are dead.
90 while (!DelBB->empty()) {
91 Instruction &I = DelBB->back();
92 // Replace used instructions with an arbitrary value (poison).
93 if (!I.use_empty())
94 I.replaceAllUsesWith(PoisonValue::get(I.getType()));
95 DelBB->back().eraseFromParent();
96 }
97 // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
98 // Child of Function F it must contain valid IR.
99 new UnreachableInst(DelBB->getContext(), DelBB);
100 }
101
102 LLVM_DUMP_METHOD
dump() const103 void DomTreeUpdater::dump() const {
104 Base::dump();
105 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
106 raw_ostream &OS = dbgs();
107 OS << "Pending Callbacks:\n";
108 int Index = 0;
109 for (const auto &BB : Callbacks) {
110 OS << " " << Index << " : ";
111 ++Index;
112 if (BB->hasName())
113 OS << BB->getName() << "(";
114 else
115 OS << "(no_name)(";
116 OS << BB << ")\n";
117 }
118 #endif
119 }
120
121 } // namespace llvm
122