xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/DomTreeUpdater.cpp (revision 19261079b74319502c6ffa1249920079f0f69a72)
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 
23 namespace llvm {
24 
25 bool 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::is_contained(successors(From), 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   if (Kind == DominatorTree::Insert && !HasEdge)
42     return false;
43 
44   // Edge exists in IR.
45   if (Kind == DominatorTree::Delete && HasEdge)
46     return false;
47 
48   return true;
49 }
50 
51 bool DomTreeUpdater::isSelfDominance(
52     const DominatorTree::UpdateType Update) const {
53   // Won't affect DomTree and PostDomTree.
54   return Update.getFrom() == Update.getTo();
55 }
56 
57 void DomTreeUpdater::applyDomTreeUpdates() {
58   // No pending DomTreeUpdates.
59   if (Strategy != UpdateStrategy::Lazy || !DT)
60     return;
61 
62   // Only apply updates not are applied by DomTree.
63   if (hasPendingDomTreeUpdates()) {
64     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
65     const auto E = PendUpdates.end();
66     assert(I < E && "Iterator range invalid; there should be DomTree updates.");
67     DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
68     PendDTUpdateIndex = PendUpdates.size();
69   }
70 }
71 
72 void DomTreeUpdater::flush() {
73   applyDomTreeUpdates();
74   applyPostDomTreeUpdates();
75   dropOutOfDateUpdates();
76 }
77 
78 void DomTreeUpdater::applyPostDomTreeUpdates() {
79   // No pending PostDomTreeUpdates.
80   if (Strategy != UpdateStrategy::Lazy || !PDT)
81     return;
82 
83   // Only apply updates not are applied by PostDomTree.
84   if (hasPendingPostDomTreeUpdates()) {
85     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
86     const auto E = PendUpdates.end();
87     assert(I < E &&
88            "Iterator range invalid; there should be PostDomTree updates.");
89     PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
90     PendPDTUpdateIndex = PendUpdates.size();
91   }
92 }
93 
94 void DomTreeUpdater::tryFlushDeletedBB() {
95   if (!hasPendingUpdates())
96     forceFlushDeletedBB();
97 }
98 
99 bool DomTreeUpdater::forceFlushDeletedBB() {
100   if (DeletedBBs.empty())
101     return false;
102 
103   for (auto *BB : DeletedBBs) {
104     // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
105     // validateDeleteBB() removes all instructions of DelBB and adds an
106     // UnreachableInst as its terminator. So we check whether the BasicBlock to
107     // delete only has an UnreachableInst inside.
108     assert(BB->getInstList().size() == 1 &&
109            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 
120 void 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 
150 bool DomTreeUpdater::hasPendingUpdates() const {
151   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
152 }
153 
154 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
155   if (!DT)
156     return false;
157   return PendUpdates.size() != PendDTUpdateIndex;
158 }
159 
160 bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
161   if (!PDT)
162     return false;
163   return PendUpdates.size() != PendPDTUpdateIndex;
164 }
165 
166 bool 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.
177 void 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 
189 void 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 
204 void 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 
214 void 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 (undef).
221     if (!I.use_empty())
222       I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
223     DelBB->getInstList().pop_back();
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 
230 void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
231   if (!DT && !PDT)
232     return;
233 
234   if (Strategy == UpdateStrategy::Lazy) {
235     for (const auto &U : Updates)
236       if (!isSelfDominance(U))
237         PendUpdates.push_back(U);
238 
239     return;
240   }
241 
242   if (DT)
243     DT->applyUpdates(Updates);
244   if (PDT)
245     PDT->applyUpdates(Updates);
246 }
247 
248 void DomTreeUpdater::applyUpdatesPermissive(
249     ArrayRef<DominatorTree::UpdateType> Updates) {
250   if (!DT && !PDT)
251     return;
252 
253   SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
254   SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
255   for (const auto &U : Updates) {
256     auto Edge = std::make_pair(U.getFrom(), U.getTo());
257     // Because it is illegal to submit updates that have already been applied
258     // and updates to an edge need to be strictly ordered,
259     // it is safe to infer the existence of an edge from the first update
260     // to this edge.
261     // If the first update to an edge is "Delete", it means that the edge
262     // existed before. If the first update to an edge is "Insert", it means
263     // that the edge didn't exist before.
264     //
265     // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
266     // because
267     // 1. it is illegal to submit updates that have already been applied,
268     // i.e., user cannot delete an nonexistent edge,
269     // 2. updates to an edge need to be strictly ordered,
270     // So, initially edge A -> B existed.
271     // We can then safely ignore future updates to this edge and directly
272     // inspect the current CFG:
273     // a. If the edge still exists, because the user cannot insert an existent
274     // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
275     // resulted in a no-op. DTU won't submit any update in this case.
276     // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
277     // actually happened but {Insert, A, B} was an invalid update which never
278     // happened. DTU will submit {Delete, A, B} in this case.
279     if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
280       Seen.insert(Edge);
281       // If the update doesn't appear in the CFG, it means that
282       // either the change isn't made or relevant operations
283       // result in a no-op.
284       if (isUpdateValid(U)) {
285         if (isLazy())
286           PendUpdates.push_back(U);
287         else
288           DeduplicatedUpdates.push_back(U);
289       }
290     }
291   }
292 
293   if (Strategy == UpdateStrategy::Lazy)
294     return;
295 
296   if (DT)
297     DT->applyUpdates(DeduplicatedUpdates);
298   if (PDT)
299     PDT->applyUpdates(DeduplicatedUpdates);
300 }
301 
302 DominatorTree &DomTreeUpdater::getDomTree() {
303   assert(DT && "Invalid acquisition of a null DomTree");
304   applyDomTreeUpdates();
305   dropOutOfDateUpdates();
306   return *DT;
307 }
308 
309 PostDominatorTree &DomTreeUpdater::getPostDomTree() {
310   assert(PDT && "Invalid acquisition of a null PostDomTree");
311   applyPostDomTreeUpdates();
312   dropOutOfDateUpdates();
313   return *PDT;
314 }
315 
316 void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
317 
318 #ifndef NDEBUG
319   assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
320          "Inserted edge does not appear in the CFG");
321 #endif
322 
323   if (!DT && !PDT)
324     return;
325 
326   // Won't affect DomTree and PostDomTree; discard update.
327   if (From == To)
328     return;
329 
330   if (Strategy == UpdateStrategy::Eager) {
331     if (DT)
332       DT->insertEdge(From, To);
333     if (PDT)
334       PDT->insertEdge(From, To);
335     return;
336   }
337 
338   PendUpdates.push_back({DominatorTree::Insert, From, To});
339 }
340 
341 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
342   if (From == To)
343     return;
344 
345   if (!DT && !PDT)
346     return;
347 
348   if (!isUpdateValid({DominatorTree::Insert, From, To}))
349     return;
350 
351   if (Strategy == UpdateStrategy::Eager) {
352     if (DT)
353       DT->insertEdge(From, To);
354     if (PDT)
355       PDT->insertEdge(From, To);
356     return;
357   }
358 
359   PendUpdates.push_back({DominatorTree::Insert, From, To});
360 }
361 
362 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
363 
364 #ifndef NDEBUG
365   assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
366          "Deleted edge still exists in the CFG!");
367 #endif
368 
369   if (!DT && !PDT)
370     return;
371 
372   // Won't affect DomTree and PostDomTree; discard update.
373   if (From == To)
374     return;
375 
376   if (Strategy == UpdateStrategy::Eager) {
377     if (DT)
378       DT->deleteEdge(From, To);
379     if (PDT)
380       PDT->deleteEdge(From, To);
381     return;
382   }
383 
384   PendUpdates.push_back({DominatorTree::Delete, From, To});
385 }
386 
387 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
388   if (From == To)
389     return;
390 
391   if (!DT && !PDT)
392     return;
393 
394   if (!isUpdateValid({DominatorTree::Delete, From, To}))
395     return;
396 
397   if (Strategy == UpdateStrategy::Eager) {
398     if (DT)
399       DT->deleteEdge(From, To);
400     if (PDT)
401       PDT->deleteEdge(From, To);
402     return;
403   }
404 
405   PendUpdates.push_back({DominatorTree::Delete, From, To});
406 }
407 
408 void DomTreeUpdater::dropOutOfDateUpdates() {
409   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
410     return;
411 
412   tryFlushDeletedBB();
413 
414   // Drop all updates applied by both trees.
415   if (!DT)
416     PendDTUpdateIndex = PendUpdates.size();
417   if (!PDT)
418     PendPDTUpdateIndex = PendUpdates.size();
419 
420   const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
421   const auto B = PendUpdates.begin();
422   const auto E = PendUpdates.begin() + dropIndex;
423   assert(B <= E && "Iterator out of range.");
424   PendUpdates.erase(B, E);
425   // Calculate current index.
426   PendDTUpdateIndex -= dropIndex;
427   PendPDTUpdateIndex -= dropIndex;
428 }
429 
430 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
431 LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
432   raw_ostream &OS = llvm::dbgs();
433 
434   OS << "Available Trees: ";
435   if (DT || PDT) {
436     if (DT)
437       OS << "DomTree ";
438     if (PDT)
439       OS << "PostDomTree ";
440     OS << "\n";
441   } else
442     OS << "None\n";
443 
444   OS << "UpdateStrategy: ";
445   if (Strategy == UpdateStrategy::Eager) {
446     OS << "Eager\n";
447     return;
448   } else
449     OS << "Lazy\n";
450   int Index = 0;
451 
452   auto printUpdates =
453       [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
454           ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
455         if (begin == end)
456           OS << "  None\n";
457         Index = 0;
458         for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
459           auto U = *It;
460           OS << "  " << Index << " : ";
461           ++Index;
462           if (U.getKind() == DominatorTree::Insert)
463             OS << "Insert, ";
464           else
465             OS << "Delete, ";
466           BasicBlock *From = U.getFrom();
467           if (From) {
468             auto S = From->getName();
469             if (!From->hasName())
470               S = "(no name)";
471             OS << S << "(" << From << "), ";
472           } else {
473             OS << "(badref), ";
474           }
475           BasicBlock *To = U.getTo();
476           if (To) {
477             auto S = To->getName();
478             if (!To->hasName())
479               S = "(no_name)";
480             OS << S << "(" << To << ")\n";
481           } else {
482             OS << "(badref)\n";
483           }
484         }
485       };
486 
487   if (DT) {
488     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
489     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
490            "Iterator out of range.");
491     OS << "Applied but not cleared DomTreeUpdates:\n";
492     printUpdates(PendUpdates.begin(), I);
493     OS << "Pending DomTreeUpdates:\n";
494     printUpdates(I, PendUpdates.end());
495   }
496 
497   if (PDT) {
498     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
499     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
500            "Iterator out of range.");
501     OS << "Applied but not cleared PostDomTreeUpdates:\n";
502     printUpdates(PendUpdates.begin(), I);
503     OS << "Pending PostDomTreeUpdates:\n";
504     printUpdates(I, PendUpdates.end());
505   }
506 
507   OS << "Pending DeletedBBs:\n";
508   Index = 0;
509   for (const auto *BB : DeletedBBs) {
510     OS << "  " << Index << " : ";
511     ++Index;
512     if (BB->hasName())
513       OS << BB->getName() << "(";
514     else
515       OS << "(no_name)(";
516     OS << BB << ")\n";
517   }
518 
519   OS << "Pending Callbacks:\n";
520   Index = 0;
521   for (const auto &BB : Callbacks) {
522     OS << "  " << Index << " : ";
523     ++Index;
524     if (BB->hasName())
525       OS << BB->getName() << "(";
526     else
527       OS << "(no_name)(";
528     OS << BB << ")\n";
529   }
530 }
531 #endif
532 } // namespace llvm
533