LLVM 20.0.0git
DomTreeUpdater.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/SmallSet.h"
18#include "llvm/IR/Constants.h"
21#include <algorithm>
22#include <functional>
23#include <utility>
24
25namespace llvm {
26
27template class GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,
28 PostDominatorTree>;
29
30template void
31GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,
32 PostDominatorTree>::recalculate(Function &F);
33
34bool 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.");
46 BB->eraseFromParent();
47 }
49 Callbacks.clear();
50 return true;
51}
52
53// The DT and PDT require the nodes related to updates
54// are not deleted when update functions are called.
55// So BasicBlock deletions must be pended when the
56// UpdateStrategy is Lazy. When the UpdateStrategy is
57// Eager, the BasicBlock will be deleted immediately.
59 validateDeleteBB(DelBB);
60 if (Strategy == UpdateStrategy::Lazy) {
61 DeletedBBs.insert(DelBB);
62 return;
63 }
64
65 eraseDelBBNode(DelBB);
66 DelBB->eraseFromParent();
67}
68
70 BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
71 validateDeleteBB(DelBB);
72 if (Strategy == UpdateStrategy::Lazy) {
73 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
74 DeletedBBs.insert(DelBB);
75 return;
76 }
77
78 eraseDelBBNode(DelBB);
79 DelBB->removeFromParent();
80 Callback(DelBB);
81 delete DelBB;
82}
83
84void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
85 assert(DelBB && "Invalid push_back of nullptr DelBB.");
86 assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
87 // DelBB is unreachable and all its instructions are dead.
88 while (!DelBB->empty()) {
89 Instruction &I = DelBB->back();
90 // Replace used instructions with an arbitrary value (poison).
91 if (!I.use_empty())
92 I.replaceAllUsesWith(PoisonValue::get(I.getType()));
93 DelBB->back().eraseFromParent();
94 }
95 // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
96 // Child of Function F it must contain valid IR.
97 new UnreachableInst(DelBB->getContext(), DelBB);
98}
99
101void DomTreeUpdater::dump() const {
102 Base::dump();
103#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
104 raw_ostream &OS = dbgs();
105 OS << "Pending Callbacks:\n";
106 int Index = 0;
107 for (const auto &BB : Callbacks) {
108 OS << " " << Index << " : ";
109 ++Index;
110 if (BB->hasName())
111 OS << BB->getName() << "(";
112 else
113 OS << "(no_name)(";
114 OS << BB << ")\n";
115 }
116#endif
117}
118
119} // namespace llvm
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:537
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.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallSet class.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
bool empty() const
Definition: BasicBlock.h:470
void removeFromParent()
Unlink 'this' from the containing function, but do not delete it.
Definition: BasicBlock.cpp:275
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:279
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:168
const Instruction & back() const
Definition: BasicBlock.h:473
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
void eraseDelBBNode(BasicBlockT *DelBB)
Erase Basic Block node before it is unlinked from Function in the DomTree and PostDomTree.
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1852
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:368
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118