xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/DomTreeUpdater.cpp (revision b13788e396c2b24f88697e7d4a74bab429ef4d0c)
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/Dominators.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::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 
52 bool DomTreeUpdater::isSelfDominance(
53     const DominatorTree::UpdateType Update) const {
54   // Won't affect DomTree and PostDomTree.
55   return Update.getFrom() == Update.getTo();
56 }
57 
58 void 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 
73 void DomTreeUpdater::flush() {
74   applyDomTreeUpdates();
75   applyPostDomTreeUpdates();
76   dropOutOfDateUpdates();
77 }
78 
79 void 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 
95 void DomTreeUpdater::tryFlushDeletedBB() {
96   if (!hasPendingUpdates())
97     forceFlushDeletedBB();
98 }
99 
100 bool 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 
121 void 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 
151 bool DomTreeUpdater::hasPendingUpdates() const {
152   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
153 }
154 
155 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
156   if (!DT)
157     return false;
158   return PendUpdates.size() != PendDTUpdateIndex;
159 }
160 
161 bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
162   if (!PDT)
163     return false;
164   return PendUpdates.size() != PendPDTUpdateIndex;
165 }
166 
167 bool 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.
178 void 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 
190 void 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 
205 void 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 
215 void 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 
231 void 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 
249 void 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 
303 DominatorTree &DomTreeUpdater::getDomTree() {
304   assert(DT && "Invalid acquisition of a null DomTree");
305   applyDomTreeUpdates();
306   dropOutOfDateUpdates();
307   return *DT;
308 }
309 
310 PostDominatorTree &DomTreeUpdater::getPostDomTree() {
311   assert(PDT && "Invalid acquisition of a null PostDomTree");
312   applyPostDomTreeUpdates();
313   dropOutOfDateUpdates();
314   return *PDT;
315 }
316 
317 void 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 
342 void 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 
363 void 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 
388 void 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 
409 void 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)
432 LLVM_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 (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 (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