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/PostDominators.h"
17#include "llvm/IR/Constants.h"
18#include "llvm/IR/Instructions.h"
19#include "llvm/Support/GenericDomTree.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(Range: successors(BB: From), Element: 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.
64 if (hasPendingDomTreeUpdates()) {
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(Updates: ArrayRef<DominatorTree::UpdateType>(I, E));
69 PendDTUpdateIndex = PendUpdates.size();
70 }
71}
72
73void DomTreeUpdater::flush() {
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.
85 if (hasPendingPostDomTreeUpdates()) {
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.");
90 PDT->applyUpdates(Updates: ArrayRef<DominatorTree::UpdateType>(I, E));
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(DelBB: BB);
113 delete BB;
114 }
115 DeletedBBs.clear();
116 Callbacks.clear();
117 return true;
118}
119
120void DomTreeUpdater::recalculate(Function &F) {
121
122 if (Strategy == UpdateStrategy::Eager) {
123 if (DT)
124 DT->recalculate(Func&: F);
125 if (PDT)
126 PDT->recalculate(Func&: 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(Func&: F);
141 if (PDT)
142 PDT->recalculate(Func&: F);
143
144 // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
145 IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
146 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
147 dropOutOfDateUpdates();
148}
149
150bool DomTreeUpdater::hasPendingUpdates() const {
151 return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
152}
153
154bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
155 if (!DT)
156 return false;
157 return PendUpdates.size() != PendDTUpdateIndex;
158}
159
160bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
161 if (!PDT)
162 return false;
163 return PendUpdates.size() != PendPDTUpdateIndex;
164}
165
166bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
167 if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
168 return false;
169 return DeletedBBs.contains(Ptr: 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.
177void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
178 validateDeleteBB(DelBB);
179 if (Strategy == UpdateStrategy::Lazy) {
180 DeletedBBs.insert(Ptr: DelBB);
181 return;
182 }
183
184 DelBB->removeFromParent();
185 eraseDelBBNode(DelBB);
186 delete DelBB;
187}
188
189void DomTreeUpdater::callbackDeleteBB(
190 BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
191 validateDeleteBB(DelBB);
192 if (Strategy == UpdateStrategy::Lazy) {
193 Callbacks.push_back(x: CallBackOnDeletion(DelBB, Callback));
194 DeletedBBs.insert(Ptr: 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(BB: DelBB))
207 DT->eraseNode(BB: DelBB);
208
209 if (PDT && !IsRecalculatingPostDomTree)
210 if (PDT->getNode(BB: DelBB))
211 PDT->eraseNode(BB: 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(V: PoisonValue::get(T: 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
230void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
231 if (!DT && !PDT)
232 return;
233
234 if (Strategy == UpdateStrategy::Lazy) {
235 PendUpdates.reserve(N: PendUpdates.size() + Updates.size());
236 for (const auto &U : Updates)
237 if (!isSelfDominance(Update: U))
238 PendUpdates.push_back(Elt: U);
239
240 return;
241 }
242
243 if (DT)
244 DT->applyUpdates(Updates);
245 if (PDT)
246 PDT->applyUpdates(Updates);
247}
248
249void DomTreeUpdater::applyUpdatesPermissive(
250 ArrayRef<DominatorTree::UpdateType> Updates) {
251 if (!DT && !PDT)
252 return;
253
254 SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
255 SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
256 for (const auto &U : Updates) {
257 auto Edge = std::make_pair(x: U.getFrom(), y: 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(Update: U) && Seen.count(V: Edge) == 0) {
281 Seen.insert(V: 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(Update: U)) {
286 if (isLazy())
287 PendUpdates.push_back(Elt: U);
288 else
289 DeduplicatedUpdates.push_back(Elt: U);
290 }
291 }
292 }
293
294 if (Strategy == UpdateStrategy::Lazy)
295 return;
296
297 if (DT)
298 DT->applyUpdates(Updates: DeduplicatedUpdates);
299 if (PDT)
300 PDT->applyUpdates(Updates: DeduplicatedUpdates);
301}
302
303DominatorTree &DomTreeUpdater::getDomTree() {
304 assert(DT && "Invalid acquisition of a null DomTree");
305 applyDomTreeUpdates();
306 dropOutOfDateUpdates();
307 return *DT;
308}
309
310PostDominatorTree &DomTreeUpdater::getPostDomTree() {
311 assert(PDT && "Invalid acquisition of a null PostDomTree");
312 applyPostDomTreeUpdates();
313 dropOutOfDateUpdates();
314 return *PDT;
315}
316
317void DomTreeUpdater::dropOutOfDateUpdates() {
318 if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
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(a: PendDTUpdateIndex, b: 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(CS: B, CE: E);
334 // Calculate current index.
335 PendDTUpdateIndex -= dropIndex;
336 PendPDTUpdateIndex -= dropIndex;
337}
338
339#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
340LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
341 raw_ostream &OS = llvm::dbgs();
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 =
362 [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
363 ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
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
442

source code of llvm/lib/Analysis/DomTreeUpdater.cpp