Line data Source code
1 : //===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the DomTreeUpdater class, which provides a uniform way
11 : // to update dominator tree related data structures.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "llvm/IR/DomTreeUpdater.h"
16 : #include "llvm/Analysis/PostDominators.h"
17 : #include "llvm/IR/Dominators.h"
18 : #include "llvm/Support/GenericDomTree.h"
19 : #include <algorithm>
20 : #include <functional>
21 :
22 : namespace llvm {
23 :
24 135291 : bool DomTreeUpdater::isUpdateValid(
25 : const DominatorTree::UpdateType Update) const {
26 135291 : const auto *From = Update.getFrom();
27 : const auto *To = Update.getTo();
28 : const auto Kind = Update.getKind();
29 :
30 : // Discard updates by inspecting the current state of successors of From.
31 : // Since isUpdateValid() must be called *after* the Terminator of From is
32 : // altered we can determine if the update is unnecessary for batch updates
33 : // or invalid for a single update.
34 135291 : const bool HasEdge = llvm::any_of(
35 135291 : successors(From), [To](const BasicBlock *B) { return B == To; });
36 :
37 : // If the IR does not match the update,
38 : // 1. In batch updates, this update is unnecessary.
39 : // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
40 : // Edge does not exist in IR.
41 135291 : if (Kind == DominatorTree::Insert && !HasEdge)
42 : return false;
43 :
44 : // Edge exists in IR.
45 135262 : if (Kind == DominatorTree::Delete && HasEdge)
46 40 : return false;
47 :
48 : return true;
49 : }
50 :
51 132146 : bool DomTreeUpdater::isSelfDominance(
52 : const DominatorTree::UpdateType Update) const {
53 : // Won't affect DomTree and PostDomTree.
54 264292 : return Update.getFrom() == Update.getTo();
55 : }
56 :
57 120944 : bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
58 : BasicBlock *From, BasicBlock *To) {
59 : assert((DT || PDT) &&
60 : "Call applyLazyUpdate() when both DT and PDT are nullptrs.");
61 : assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy &&
62 : "Call applyLazyUpdate() with Eager strategy error");
63 : // Analyze pending updates to determine if the update is unnecessary.
64 : const DominatorTree::UpdateType Update = {Kind, From, To};
65 : const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
66 : ? DominatorTree::Insert
67 : : DominatorTree::Delete,
68 120944 : From, To};
69 : // Only check duplicates in updates that are not applied by both trees.
70 : auto I =
71 120944 : PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
72 : const auto E = PendUpdates.end();
73 :
74 : assert(I <= E && "Iterator out of range.");
75 :
76 5142572 : for (; I != E; ++I) {
77 : if (Update == *I)
78 : return false; // Discard duplicate updates.
79 :
80 : if (Invert == *I) {
81 : // Update and Invert are both valid (equivalent to a no-op). Remove
82 : // Invert from PendUpdates and discard the Update.
83 : PendUpdates.erase(I);
84 17586 : return false;
85 : }
86 : }
87 :
88 103358 : PendUpdates.push_back(Update); // Save the valid update.
89 103358 : return true;
90 : }
91 :
92 357325 : void DomTreeUpdater::applyDomTreeUpdates() {
93 : // No pending DomTreeUpdates.
94 357325 : if (Strategy != UpdateStrategy::Lazy || !DT)
95 : return;
96 :
97 : // Only apply updates not are applied by DomTree.
98 267497 : if (hasPendingDomTreeUpdates()) {
99 6700 : const auto I = PendUpdates.begin() + PendDTUpdateIndex;
100 : const auto E = PendUpdates.end();
101 : assert(I < E && "Iterator range invalid; there should be DomTree updates.");
102 6700 : DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
103 13400 : PendDTUpdateIndex = PendUpdates.size();
104 : }
105 : }
106 :
107 180171 : void DomTreeUpdater::flush() {
108 180171 : applyDomTreeUpdates();
109 180171 : applyPostDomTreeUpdates();
110 180171 : dropOutOfDateUpdates();
111 180171 : }
112 :
113 180216 : void DomTreeUpdater::applyPostDomTreeUpdates() {
114 : // No pending PostDomTreeUpdates.
115 180216 : if (Strategy != UpdateStrategy::Lazy || !PDT)
116 : return;
117 :
118 : // Only apply updates not are applied by PostDomTree.
119 49 : if (hasPendingPostDomTreeUpdates()) {
120 6 : const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
121 : const auto E = PendUpdates.end();
122 : assert(I < E &&
123 : "Iterator range invalid; there should be PostDomTree updates.");
124 6 : PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
125 12 : PendPDTUpdateIndex = PendUpdates.size();
126 : }
127 : }
128 :
129 268483 : void DomTreeUpdater::tryFlushDeletedBB() {
130 268483 : if (!hasPendingUpdates())
131 268479 : forceFlushDeletedBB();
132 268483 : }
133 :
134 269437 : bool DomTreeUpdater::forceFlushDeletedBB() {
135 269437 : if (DeletedBBs.empty())
136 : return false;
137 :
138 36643 : for (auto *BB : DeletedBBs) {
139 : // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
140 : // validateDeleteBB() removes all instructions of DelBB and adds an
141 : // UnreachableInst as its terminator. So we check whether the BasicBlock to
142 : // delete only has an UnreachableInst inside.
143 : assert(BB->getInstList().size() == 1 &&
144 : isa<UnreachableInst>(BB->getTerminator()) &&
145 : "DelBB has been modified while awaiting deletion.");
146 29011 : BB->removeFromParent();
147 29011 : eraseDelBBNode(BB);
148 29011 : delete BB;
149 : }
150 7632 : DeletedBBs.clear();
151 : Callbacks.clear();
152 : return true;
153 : }
154 :
155 989 : void DomTreeUpdater::recalculate(Function &F) {
156 :
157 989 : if (Strategy == UpdateStrategy::Eager) {
158 31 : if (DT)
159 27 : DT->recalculate(F);
160 31 : if (PDT)
161 3 : PDT->recalculate(F);
162 31 : return;
163 : }
164 :
165 : // There is little performance gain if we pend the recalculation under
166 : // Lazy UpdateStrategy so we recalculate available trees immediately.
167 :
168 : // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
169 958 : IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
170 :
171 : // Because all trees are going to be up-to-date after recalculation,
172 : // flush awaiting deleted BasicBlocks.
173 958 : forceFlushDeletedBB();
174 958 : if (DT)
175 957 : DT->recalculate(F);
176 958 : if (PDT)
177 3 : PDT->recalculate(F);
178 :
179 : // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
180 958 : IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
181 958 : PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
182 958 : dropOutOfDateUpdates();
183 : }
184 :
185 268489 : bool DomTreeUpdater::hasPendingUpdates() const {
186 268489 : return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
187 : }
188 :
189 871593 : bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
190 871593 : if (!DT)
191 : return false;
192 1743174 : return PendUpdates.size() != PendDTUpdateIndex;
193 : }
194 :
195 268541 : bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
196 268541 : if (!PDT)
197 : return false;
198 266 : return PendUpdates.size() != PendPDTUpdateIndex;
199 : }
200 :
201 1687124 : bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
202 1687124 : if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
203 : return false;
204 1019632 : return DeletedBBs.count(DelBB) != 0;
205 : }
206 :
207 : // The DT and PDT require the nodes related to updates
208 : // are not deleted when update functions are called.
209 : // So BasicBlock deletions must be pended when the
210 : // UpdateStrategy is Lazy. When the UpdateStrategy is
211 : // Eager, the BasicBlock will be deleted immediately.
212 31995 : void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
213 31995 : validateDeleteBB(DelBB);
214 31995 : if (Strategy == UpdateStrategy::Lazy) {
215 29009 : DeletedBBs.insert(DelBB);
216 29009 : return;
217 : }
218 :
219 2986 : DelBB->removeFromParent();
220 2986 : eraseDelBBNode(DelBB);
221 2986 : delete DelBB;
222 : }
223 :
224 4 : void DomTreeUpdater::callbackDeleteBB(
225 : BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
226 4 : validateDeleteBB(DelBB);
227 4 : if (Strategy == UpdateStrategy::Lazy) {
228 9 : Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
229 3 : DeletedBBs.insert(DelBB);
230 3 : return;
231 : }
232 :
233 1 : DelBB->removeFromParent();
234 1 : eraseDelBBNode(DelBB);
235 1 : Callback(DelBB);
236 1 : delete DelBB;
237 : }
238 :
239 31998 : void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
240 31998 : if (DT && !IsRecalculatingDomTree)
241 2 : if (DT->getNode(DelBB))
242 2 : DT->eraseNode(DelBB);
243 :
244 31998 : if (PDT && !IsRecalculatingPostDomTree)
245 16 : if (PDT->getNode(DelBB))
246 16 : PDT->eraseNode(DelBB);
247 31998 : }
248 :
249 31999 : void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
250 : assert(DelBB && "Invalid push_back of nullptr DelBB.");
251 : assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
252 : // DelBB is unreachable and all its instructions are dead.
253 67090 : while (!DelBB->empty()) {
254 : Instruction &I = DelBB->back();
255 : // Replace used instructions with an arbitrary value (undef).
256 35091 : if (!I.use_empty())
257 0 : I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
258 35091 : DelBB->getInstList().pop_back();
259 : }
260 : // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
261 : // Child of Function F it must contain valid IR.
262 63998 : new UnreachableInst(DelBB->getContext(), DelBB);
263 31999 : }
264 :
265 35879 : void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
266 : bool ForceRemoveDuplicates) {
267 35879 : if (!DT && !PDT)
268 : return;
269 :
270 35879 : if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
271 : SmallVector<DominatorTree::UpdateType, 8> Seen;
272 168693 : for (const auto U : Updates)
273 : // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
274 : // on analysis.
275 132858 : if (llvm::none_of(
276 : Seen,
277 132207 : [U](const DominatorTree::UpdateType S) { return S == U; }) &&
278 265004 : isUpdateValid(U) && !isSelfDominance(U)) {
279 131425 : Seen.push_back(U);
280 131425 : if (Strategy == UpdateStrategy::Lazy)
281 235738 : applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
282 : }
283 35835 : if (Strategy == UpdateStrategy::Lazy)
284 : return;
285 :
286 2992 : if (DT)
287 2990 : DT->applyUpdates(Seen);
288 2992 : if (PDT)
289 18 : PDT->applyUpdates(Seen);
290 2992 : return;
291 : }
292 :
293 44 : if (DT)
294 11 : DT->applyUpdates(Updates);
295 44 : if (PDT)
296 34 : PDT->applyUpdates(Updates);
297 : }
298 :
299 177154 : DominatorTree &DomTreeUpdater::getDomTree() {
300 : assert(DT && "Invalid acquisition of a null DomTree");
301 177154 : applyDomTreeUpdates();
302 177154 : dropOutOfDateUpdates();
303 177154 : return *DT;
304 : }
305 :
306 45 : PostDominatorTree &DomTreeUpdater::getPostDomTree() {
307 : assert(PDT && "Invalid acquisition of a null PostDomTree");
308 45 : applyPostDomTreeUpdates();
309 45 : dropOutOfDateUpdates();
310 45 : return *PDT;
311 : }
312 :
313 277 : void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
314 :
315 : #ifndef NDEBUG
316 : assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
317 : "Inserted edge does not appear in the CFG");
318 : #endif
319 :
320 277 : if (!DT && !PDT)
321 : return;
322 :
323 : // Won't affect DomTree and PostDomTree; discard update.
324 273 : if (From == To)
325 : return;
326 :
327 270 : if (Strategy == UpdateStrategy::Eager) {
328 269 : if (DT)
329 269 : DT->insertEdge(From, To);
330 269 : if (PDT)
331 0 : PDT->insertEdge(From, To);
332 269 : return;
333 : }
334 :
335 1 : applyLazyUpdate(DominatorTree::Insert, From, To);
336 : }
337 :
338 3 : void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
339 3 : if (From == To)
340 : return;
341 :
342 2 : if (!DT && !PDT)
343 : return;
344 :
345 2 : if (!isUpdateValid({DominatorTree::Insert, From, To}))
346 : return;
347 :
348 1 : if (Strategy == UpdateStrategy::Eager) {
349 1 : if (DT)
350 1 : DT->insertEdge(From, To);
351 1 : if (PDT)
352 1 : PDT->insertEdge(From, To);
353 1 : return;
354 : }
355 :
356 0 : applyLazyUpdate(DominatorTree::Insert, From, To);
357 : }
358 :
359 265 : void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
360 :
361 : #ifndef NDEBUG
362 : assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
363 : "Deleted edge still exists in the CFG!");
364 : #endif
365 :
366 265 : if (!DT && !PDT)
367 : return;
368 :
369 : // Won't affect DomTree and PostDomTree; discard update.
370 264 : if (From == To)
371 : return;
372 :
373 262 : if (Strategy == UpdateStrategy::Eager) {
374 259 : if (DT)
375 259 : DT->deleteEdge(From, To);
376 259 : if (PDT)
377 0 : PDT->deleteEdge(From, To);
378 259 : return;
379 : }
380 :
381 3 : applyLazyUpdate(DominatorTree::Delete, From, To);
382 : }
383 :
384 3085 : void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
385 3085 : if (From == To)
386 : return;
387 :
388 3082 : if (!DT && !PDT)
389 : return;
390 :
391 3082 : if (!isUpdateValid({DominatorTree::Delete, From, To}))
392 : return;
393 :
394 3075 : if (Strategy == UpdateStrategy::Eager) {
395 4 : if (DT)
396 4 : DT->deleteEdge(From, To);
397 4 : if (PDT)
398 4 : PDT->deleteEdge(From, To);
399 4 : return;
400 : }
401 :
402 3071 : applyLazyUpdate(DominatorTree::Delete, From, To);
403 : }
404 :
405 358328 : void DomTreeUpdater::dropOutOfDateUpdates() {
406 358328 : if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
407 : return;
408 :
409 268483 : tryFlushDeletedBB();
410 :
411 : // Drop all updates applied by both trees.
412 268483 : if (!DT)
413 12 : PendDTUpdateIndex = PendUpdates.size();
414 268483 : if (!PDT)
415 536816 : PendPDTUpdateIndex = PendUpdates.size();
416 :
417 268486 : const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
418 : const auto B = PendUpdates.begin();
419 268483 : const auto E = PendUpdates.begin() + dropIndex;
420 : assert(B <= E && "Iterator out of range.");
421 : PendUpdates.erase(B, E);
422 : // Calculate current index.
423 268483 : PendDTUpdateIndex -= dropIndex;
424 268483 : PendPDTUpdateIndex -= dropIndex;
425 : }
426 :
427 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
428 : LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
429 : raw_ostream &OS = llvm::dbgs();
430 :
431 : OS << "Available Trees: ";
432 : if (DT || PDT) {
433 : if (DT)
434 : OS << "DomTree ";
435 : if (PDT)
436 : OS << "PostDomTree ";
437 : OS << "\n";
438 : } else
439 : OS << "None\n";
440 :
441 : OS << "UpdateStrategy: ";
442 : if (Strategy == UpdateStrategy::Eager) {
443 : OS << "Eager\n";
444 : return;
445 : } else
446 : OS << "Lazy\n";
447 : int Index = 0;
448 :
449 : auto printUpdates =
450 : [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
451 : ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
452 : if (begin == end)
453 : OS << " None\n";
454 : Index = 0;
455 : for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
456 : auto U = *It;
457 : OS << " " << Index << " : ";
458 : ++Index;
459 : if (U.getKind() == DominatorTree::Insert)
460 : OS << "Insert, ";
461 : else
462 : OS << "Delete, ";
463 : BasicBlock *From = U.getFrom();
464 : if (From) {
465 : auto S = From->getName();
466 : if (!From->hasName())
467 : S = "(no name)";
468 : OS << S << "(" << From << "), ";
469 : } else {
470 : OS << "(badref), ";
471 : }
472 : BasicBlock *To = U.getTo();
473 : if (To) {
474 : auto S = To->getName();
475 : if (!To->hasName())
476 : S = "(no_name)";
477 : OS << S << "(" << To << ")\n";
478 : } else {
479 : OS << "(badref)\n";
480 : }
481 : }
482 : };
483 :
484 : if (DT) {
485 : const auto I = PendUpdates.begin() + PendDTUpdateIndex;
486 : assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
487 : "Iterator out of range.");
488 : OS << "Applied but not cleared DomTreeUpdates:\n";
489 : printUpdates(PendUpdates.begin(), I);
490 : OS << "Pending DomTreeUpdates:\n";
491 : printUpdates(I, PendUpdates.end());
492 : }
493 :
494 : if (PDT) {
495 : const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
496 : assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
497 : "Iterator out of range.");
498 : OS << "Applied but not cleared PostDomTreeUpdates:\n";
499 : printUpdates(PendUpdates.begin(), I);
500 : OS << "Pending PostDomTreeUpdates:\n";
501 : printUpdates(I, PendUpdates.end());
502 : }
503 :
504 : OS << "Pending DeletedBBs:\n";
505 : Index = 0;
506 : for (auto BB : DeletedBBs) {
507 : OS << " " << Index << " : ";
508 : ++Index;
509 : if (BB->hasName())
510 : OS << BB->getName() << "(";
511 : else
512 : OS << "(no_name)(";
513 : OS << BB << ")\n";
514 : }
515 :
516 : OS << "Pending Callbacks:\n";
517 : Index = 0;
518 : for (auto BB : Callbacks) {
519 : OS << " " << Index << " : ";
520 : ++Index;
521 : if (BB->hasName())
522 : OS << BB->getName() << "(";
523 : else
524 : OS << "(no_name)(";
525 : OS << BB << ")\n";
526 : }
527 : }
528 : #endif
529 : } // namespace llvm
|
