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/Instructions.h"
18#include "llvm/Support/GenericDomTree.h"
19#include <algorithm>
20#include <functional>
21#include <utility>
22
23namespace llvm {
24
25bool DomTreeUpdater::isUpdateValid(
26    const DominatorTree::UpdateType Update) const {
27  const auto *From = Update.getFrom();
28  const auto *To = Update.getTo();
29  const auto Kind = Update.getKind();
30
31  // Discard updates by inspecting the current state of successors of From.
32  // Since isUpdateValid() must be called *after* the Terminator of From is
33  // altered we can determine if the update is unnecessary for batch updates
34  // or invalid for a single update.
35  const bool HasEdge = llvm::any_of(
36      successors(From), [To](const BasicBlock *B) { return B == 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(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(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->getInstList().size() == 1 &&
110           isa<UnreachableInst>(BB->getTerminator()) &&
111           "DelBB has been modified while awaiting deletion.");
112    BB->removeFromParent();
113    eraseDelBBNode(BB);
114    delete BB;
115  }
116  DeletedBBs.clear();
117  Callbacks.clear();
118  return true;
119}
120
121void DomTreeUpdater::recalculate(Function &F) {
122
123  if (Strategy == UpdateStrategy::Eager) {
124    if (DT)
125      DT->recalculate(F);
126    if (PDT)
127      PDT->recalculate(F);
128    return;
129  }
130
131  // There is little performance gain if we pend the recalculation under
132  // Lazy UpdateStrategy so we recalculate available trees immediately.
133
134  // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
135  IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
136
137  // Because all trees are going to be up-to-date after recalculation,
138  // flush awaiting deleted BasicBlocks.
139  forceFlushDeletedBB();
140  if (DT)
141    DT->recalculate(F);
142  if (PDT)
143    PDT->recalculate(F);
144
145  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
146  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
147  PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
148  dropOutOfDateUpdates();
149}
150
151bool DomTreeUpdater::hasPendingUpdates() const {
152  return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
153}
154
155bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
156  if (!DT)
157    return false;
158  return PendUpdates.size() != PendDTUpdateIndex;
159}
160
161bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
162  if (!PDT)
163    return false;
164  return PendUpdates.size() != PendPDTUpdateIndex;
165}
166
167bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
168  if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
169    return false;
170  return DeletedBBs.count(DelBB) != 0;
171}
172
173// The DT and PDT require the nodes related to updates
174// are not deleted when update functions are called.
175// So BasicBlock deletions must be pended when the
176// UpdateStrategy is Lazy. When the UpdateStrategy is
177// Eager, the BasicBlock will be deleted immediately.
178void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
179  validateDeleteBB(DelBB);
180  if (Strategy == UpdateStrategy::Lazy) {
181    DeletedBBs.insert(DelBB);
182    return;
183  }
184
185  DelBB->removeFromParent();
186  eraseDelBBNode(DelBB);
187  delete DelBB;
188}
189
190void DomTreeUpdater::callbackDeleteBB(
191    BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
192  validateDeleteBB(DelBB);
193  if (Strategy == UpdateStrategy::Lazy) {
194    Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
195    DeletedBBs.insert(DelBB);
196    return;
197  }
198
199  DelBB->removeFromParent();
200  eraseDelBBNode(DelBB);
201  Callback(DelBB);
202  delete DelBB;
203}
204
205void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
206  if (DT && !IsRecalculatingDomTree)
207    if (DT->getNode(DelBB))
208      DT->eraseNode(DelBB);
209
210  if (PDT && !IsRecalculatingPostDomTree)
211    if (PDT->getNode(DelBB))
212      PDT->eraseNode(DelBB);
213}
214
215void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
216  assert(DelBB && "Invalid push_back of nullptr DelBB.");
217  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
218  // DelBB is unreachable and all its instructions are dead.
219  while (!DelBB->empty()) {
220    Instruction &I = DelBB->back();
221    // Replace used instructions with an arbitrary value (undef).
222    if (!I.use_empty())
223      I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
224    DelBB->getInstList().pop_back();
225  }
226  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
227  // Child of Function F it must contain valid IR.
228  new UnreachableInst(DelBB->getContext(), DelBB);
229}
230
231void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
232  if (!DT && !PDT)
233    return;
234
235  if (Strategy == UpdateStrategy::Lazy) {
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
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(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
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::insertEdge(BasicBlock *From, BasicBlock *To) {
318
319#ifndef NDEBUG
320  assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
321         "Inserted edge does not appear in the CFG");
322#endif
323
324  if (!DT && !PDT)
325    return;
326
327  // Won't affect DomTree and PostDomTree; discard update.
328  if (From == To)
329    return;
330
331  if (Strategy == UpdateStrategy::Eager) {
332    if (DT)
333      DT->insertEdge(From, To);
334    if (PDT)
335      PDT->insertEdge(From, To);
336    return;
337  }
338
339  PendUpdates.push_back({DominatorTree::Insert, From, To});
340}
341
342void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
343  if (From == To)
344    return;
345
346  if (!DT && !PDT)
347    return;
348
349  if (!isUpdateValid({DominatorTree::Insert, From, To}))
350    return;
351
352  if (Strategy == UpdateStrategy::Eager) {
353    if (DT)
354      DT->insertEdge(From, To);
355    if (PDT)
356      PDT->insertEdge(From, To);
357    return;
358  }
359
360  PendUpdates.push_back({DominatorTree::Insert, From, To});
361}
362
363void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
364
365#ifndef NDEBUG
366  assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
367         "Deleted edge still exists in the CFG!");
368#endif
369
370  if (!DT && !PDT)
371    return;
372
373  // Won't affect DomTree and PostDomTree; discard update.
374  if (From == To)
375    return;
376
377  if (Strategy == UpdateStrategy::Eager) {
378    if (DT)
379      DT->deleteEdge(From, To);
380    if (PDT)
381      PDT->deleteEdge(From, To);
382    return;
383  }
384
385  PendUpdates.push_back({DominatorTree::Delete, From, To});
386}
387
388void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
389  if (From == To)
390    return;
391
392  if (!DT && !PDT)
393    return;
394
395  if (!isUpdateValid({DominatorTree::Delete, From, To}))
396    return;
397
398  if (Strategy == UpdateStrategy::Eager) {
399    if (DT)
400      DT->deleteEdge(From, To);
401    if (PDT)
402      PDT->deleteEdge(From, To);
403    return;
404  }
405
406  PendUpdates.push_back({DominatorTree::Delete, From, To});
407}
408
409void DomTreeUpdater::dropOutOfDateUpdates() {
410  if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
411    return;
412
413  tryFlushDeletedBB();
414
415  // Drop all updates applied by both trees.
416  if (!DT)
417    PendDTUpdateIndex = PendUpdates.size();
418  if (!PDT)
419    PendPDTUpdateIndex = PendUpdates.size();
420
421  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
422  const auto B = PendUpdates.begin();
423  const auto E = PendUpdates.begin() + dropIndex;
424  assert(B <= E && "Iterator out of range.");
425  PendUpdates.erase(B, E);
426  // Calculate current index.
427  PendDTUpdateIndex -= dropIndex;
428  PendPDTUpdateIndex -= dropIndex;
429}
430
431#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
432LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
433  raw_ostream &OS = llvm::dbgs();
434
435  OS << "Available Trees: ";
436  if (DT || PDT) {
437    if (DT)
438      OS << "DomTree ";
439    if (PDT)
440      OS << "PostDomTree ";
441    OS << "\n";
442  } else
443    OS << "None\n";
444
445  OS << "UpdateStrategy: ";
446  if (Strategy == UpdateStrategy::Eager) {
447    OS << "Eager\n";
448    return;
449  } else
450    OS << "Lazy\n";
451  int Index = 0;
452
453  auto printUpdates =
454      [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
455          ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
456        if (begin == end)
457          OS << "  None\n";
458        Index = 0;
459        for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
460          auto U = *It;
461          OS << "  " << Index << " : ";
462          ++Index;
463          if (U.getKind() == DominatorTree::Insert)
464            OS << "Insert, ";
465          else
466            OS << "Delete, ";
467          BasicBlock *From = U.getFrom();
468          if (From) {
469            auto S = From->getName();
470            if (!From->hasName())
471              S = "(no name)";
472            OS << S << "(" << From << "), ";
473          } else {
474            OS << "(badref), ";
475          }
476          BasicBlock *To = U.getTo();
477          if (To) {
478            auto S = To->getName();
479            if (!To->hasName())
480              S = "(no_name)";
481            OS << S << "(" << To << ")\n";
482          } else {
483            OS << "(badref)\n";
484          }
485        }
486      };
487
488  if (DT) {
489    const auto I = PendUpdates.begin() + PendDTUpdateIndex;
490    assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
491           "Iterator out of range.");
492    OS << "Applied but not cleared DomTreeUpdates:\n";
493    printUpdates(PendUpdates.begin(), I);
494    OS << "Pending DomTreeUpdates:\n";
495    printUpdates(I, PendUpdates.end());
496  }
497
498  if (PDT) {
499    const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
500    assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
501           "Iterator out of range.");
502    OS << "Applied but not cleared PostDomTreeUpdates:\n";
503    printUpdates(PendUpdates.begin(), I);
504    OS << "Pending PostDomTreeUpdates:\n";
505    printUpdates(I, PendUpdates.end());
506  }
507
508  OS << "Pending DeletedBBs:\n";
509  Index = 0;
510  for (const auto *BB : DeletedBBs) {
511    OS << "  " << Index << " : ";
512    ++Index;
513    if (BB->hasName())
514      OS << BB->getName() << "(";
515    else
516      OS << "(no_name)(";
517    OS << BB << ")\n";
518  }
519
520  OS << "Pending Callbacks:\n";
521  Index = 0;
522  for (const auto &BB : Callbacks) {
523    OS << "  " << Index << " : ";
524    ++Index;
525    if (BB->hasName())
526      OS << BB->getName() << "(";
527    else
528      OS << "(no_name)(";
529    OS << BB << ")\n";
530  }
531}
532#endif
533} // namespace llvm
534