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