LLVM 19.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"
17#include "llvm/IR/Constants.h"
20#include <algorithm>
21#include <functional>
22#include <utility>
23
24namespace llvm {
25
26bool DomTreeUpdater::isUpdateValid(
27 const DominatorTree::UpdateType Update) const {
28 const auto *From = Update.getFrom();
29 const auto *To = Update.getTo();
30 const auto Kind = Update.getKind();
31
32 // Discard updates by inspecting the current state of successors of From.
33 // Since isUpdateValid() must be called *after* the Terminator of From is
34 // altered we can determine if the update is unnecessary for batch updates
35 // or invalid for a single update.
36 const bool HasEdge = llvm::is_contained(successors(From), To);
37
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)
43 return false;
44
45 // Edge exists in IR.
46 if (Kind == DominatorTree::Delete && HasEdge)
47 return false;
48
49 return true;
50}
51
52bool DomTreeUpdater::isSelfDominance(
53 const DominatorTree::UpdateType Update) const {
54 // Won't affect DomTree and PostDomTree.
55 return Update.getFrom() == Update.getTo();
56}
57
58void DomTreeUpdater::applyDomTreeUpdates() {
59 // No pending DomTreeUpdates.
60 if (Strategy != UpdateStrategy::Lazy || !DT)
61 return;
62
63 // Only apply updates not are applied by DomTree.
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();
70 }
71}
72
74 applyDomTreeUpdates();
75 applyPostDomTreeUpdates();
76 dropOutOfDateUpdates();
77}
78
79void DomTreeUpdater::applyPostDomTreeUpdates() {
80 // No pending PostDomTreeUpdates.
81 if (Strategy != UpdateStrategy::Lazy || !PDT)
82 return;
83
84 // Only apply updates not are applied by PostDomTree.
86 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
87 const auto E = PendUpdates.end();
88 assert(I < E &&
89 "Iterator range invalid; there should be PostDomTree updates.");
91 PendPDTUpdateIndex = PendUpdates.size();
92 }
93}
94
95void DomTreeUpdater::tryFlushDeletedBB() {
96 if (!hasPendingUpdates())
97 forceFlushDeletedBB();
98}
99
100bool DomTreeUpdater::forceFlushDeletedBB() {
101 if (DeletedBBs.empty())
102 return false;
103
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->size() == 1 && isa<UnreachableInst>(BB->getTerminator()) &&
110 "DelBB has been modified while awaiting deletion.");
111 BB->removeFromParent();
112 eraseDelBBNode(BB);
113 delete BB;
114 }
115 DeletedBBs.clear();
116 Callbacks.clear();
117 return true;
118}
119
121
122 if (Strategy == UpdateStrategy::Eager) {
123 if (DT)
124 DT->recalculate(F);
125 if (PDT)
126 PDT->recalculate(F);
127 return;
128 }
129
130 // There is little performance gain if we pend the recalculation under
131 // Lazy UpdateStrategy so we recalculate available trees immediately.
132
133 // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
134 IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
135
136 // Because all trees are going to be up-to-date after recalculation,
137 // flush awaiting deleted BasicBlocks.
138 forceFlushDeletedBB();
139 if (DT)
140 DT->recalculate(F);
141 if (PDT)
142 PDT->recalculate(F);
143
144 // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
145 IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
146 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
147 dropOutOfDateUpdates();
148}
149
152}
153
155 if (!DT)
156 return false;
157 return PendUpdates.size() != PendDTUpdateIndex;
158}
159
161 if (!PDT)
162 return false;
163 return PendUpdates.size() != PendPDTUpdateIndex;
164}
165
167 if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
168 return false;
169 return DeletedBBs.contains(DelBB);
170}
171
172// The DT and PDT require the nodes related to updates
173// are not deleted when update functions are called.
174// So BasicBlock deletions must be pended when the
175// UpdateStrategy is Lazy. When the UpdateStrategy is
176// Eager, the BasicBlock will be deleted immediately.
178 validateDeleteBB(DelBB);
179 if (Strategy == UpdateStrategy::Lazy) {
180 DeletedBBs.insert(DelBB);
181 return;
182 }
183
184 DelBB->removeFromParent();
185 eraseDelBBNode(DelBB);
186 delete DelBB;
187}
188
190 BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
191 validateDeleteBB(DelBB);
192 if (Strategy == UpdateStrategy::Lazy) {
193 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
194 DeletedBBs.insert(DelBB);
195 return;
196 }
197
198 DelBB->removeFromParent();
199 eraseDelBBNode(DelBB);
200 Callback(DelBB);
201 delete DelBB;
202}
203
204void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
205 if (DT && !IsRecalculatingDomTree)
206 if (DT->getNode(DelBB))
207 DT->eraseNode(DelBB);
208
209 if (PDT && !IsRecalculatingPostDomTree)
210 if (PDT->getNode(DelBB))
211 PDT->eraseNode(DelBB);
212}
213
214void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
215 assert(DelBB && "Invalid push_back of nullptr DelBB.");
216 assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
217 // DelBB is unreachable and all its instructions are dead.
218 while (!DelBB->empty()) {
219 Instruction &I = DelBB->back();
220 // Replace used instructions with an arbitrary value (poison).
221 if (!I.use_empty())
222 I.replaceAllUsesWith(PoisonValue::get(I.getType()));
223 DelBB->back().eraseFromParent();
224 }
225 // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
226 // Child of Function F it must contain valid IR.
227 new UnreachableInst(DelBB->getContext(), DelBB);
228}
229
231 if (!DT && !PDT)
232 return;
233
234 if (Strategy == UpdateStrategy::Lazy) {
235 PendUpdates.reserve(PendUpdates.size() + Updates.size());
236 for (const auto &U : Updates)
237 if (!isSelfDominance(U))
238 PendUpdates.push_back(U);
239
240 return;
241 }
242
243 if (DT)
244 DT->applyUpdates(Updates);
245 if (PDT)
246 PDT->applyUpdates(Updates);
247}
248
251 if (!DT && !PDT)
252 return;
253
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
261 // to this edge.
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.
265 //
266 // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
267 // because
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) {
281 Seen.insert(Edge);
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)) {
286 if (isLazy())
287 PendUpdates.push_back(U);
288 else
289 DeduplicatedUpdates.push_back(U);
290 }
291 }
292 }
293
294 if (Strategy == UpdateStrategy::Lazy)
295 return;
296
297 if (DT)
298 DT->applyUpdates(DeduplicatedUpdates);
299 if (PDT)
300 PDT->applyUpdates(DeduplicatedUpdates);
301}
302
304 assert(DT && "Invalid acquisition of a null DomTree");
305 applyDomTreeUpdates();
306 dropOutOfDateUpdates();
307 return *DT;
308}
309
311 assert(PDT && "Invalid acquisition of a null PostDomTree");
312 applyPostDomTreeUpdates();
313 dropOutOfDateUpdates();
314 return *PDT;
315}
316
317void DomTreeUpdater::dropOutOfDateUpdates() {
319 return;
320
321 tryFlushDeletedBB();
322
323 // Drop all updates applied by both trees.
324 if (!DT)
325 PendDTUpdateIndex = PendUpdates.size();
326 if (!PDT)
327 PendPDTUpdateIndex = PendUpdates.size();
328
329 const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
330 const auto B = PendUpdates.begin();
331 const auto E = PendUpdates.begin() + dropIndex;
332 assert(B <= E && "Iterator out of range.");
333 PendUpdates.erase(B, E);
334 // Calculate current index.
335 PendDTUpdateIndex -= dropIndex;
336 PendPDTUpdateIndex -= dropIndex;
337}
338
339#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
342
343 OS << "Available Trees: ";
344 if (DT || PDT) {
345 if (DT)
346 OS << "DomTree ";
347 if (PDT)
348 OS << "PostDomTree ";
349 OS << "\n";
350 } else
351 OS << "None\n";
352
353 OS << "UpdateStrategy: ";
354 if (Strategy == UpdateStrategy::Eager) {
355 OS << "Eager\n";
356 return;
357 } else
358 OS << "Lazy\n";
359 int Index = 0;
360
361 auto printUpdates =
364 if (begin == end)
365 OS << " None\n";
366 Index = 0;
367 for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
368 auto U = *It;
369 OS << " " << Index << " : ";
370 ++Index;
371 if (U.getKind() == DominatorTree::Insert)
372 OS << "Insert, ";
373 else
374 OS << "Delete, ";
375 BasicBlock *From = U.getFrom();
376 if (From) {
377 auto S = From->getName();
378 if (!From->hasName())
379 S = "(no name)";
380 OS << S << "(" << From << "), ";
381 } else {
382 OS << "(badref), ";
383 }
384 BasicBlock *To = U.getTo();
385 if (To) {
386 auto S = To->getName();
387 if (!To->hasName())
388 S = "(no_name)";
389 OS << S << "(" << To << ")\n";
390 } else {
391 OS << "(badref)\n";
392 }
393 }
394 };
395
396 if (DT) {
397 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
398 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
399 "Iterator out of range.");
400 OS << "Applied but not cleared DomTreeUpdates:\n";
401 printUpdates(PendUpdates.begin(), I);
402 OS << "Pending DomTreeUpdates:\n";
403 printUpdates(I, PendUpdates.end());
404 }
405
406 if (PDT) {
407 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
408 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
409 "Iterator out of range.");
410 OS << "Applied but not cleared PostDomTreeUpdates:\n";
411 printUpdates(PendUpdates.begin(), I);
412 OS << "Pending PostDomTreeUpdates:\n";
413 printUpdates(I, PendUpdates.end());
414 }
415
416 OS << "Pending DeletedBBs:\n";
417 Index = 0;
418 for (const auto *BB : DeletedBBs) {
419 OS << " " << Index << " : ";
420 ++Index;
421 if (BB->hasName())
422 OS << BB->getName() << "(";
423 else
424 OS << "(no_name)(";
425 OS << BB << ")\n";
426 }
427
428 OS << "Pending Callbacks:\n";
429 Index = 0;
430 for (const auto &BB : Callbacks) {
431 OS << " " << Index << " : ";
432 ++Index;
433 if (BB->hasName())
434 OS << BB->getName() << "(";
435 else
436 OS << "(no_name)(";
437 OS << BB << ")\n";
438 }
439}
440#endif
441} // namespace llvm
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
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.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
void removeFromParent()
Unlink 'this' from the containing function, but do not delete it.
Definition: BasicBlock.cpp:319
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
bool hasPendingDomTreeUpdates() const
Returns true if there are DominatorTree updates queued.
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
PostDominatorTree & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
bool hasPendingPostDomTreeUpdates() const
Returns true if there are PostDominatorTree updates queued.
bool isLazy() const
Returns true if the current strategy is Lazy.
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending.
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1827
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:676
iterator erase(const_iterator CI)
Definition: SmallVector.h:750
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
bool hasName() const
Definition: Value.h:261
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118