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(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.
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->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
120void DomTreeUpdater::recalculate(Function &F) {
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
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(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(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(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
230void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
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
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::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(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)
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