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 
24 namespace llvm {
25 
isUpdateValid(const DominatorTree::UpdateType Update) const26 bool 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 
isSelfDominance(const DominatorTree::UpdateType Update) const52 bool DomTreeUpdater::isSelfDominance(
53     const DominatorTree::UpdateType Update) const {
54   // Won't affect DomTree and PostDomTree.
55   return Update.getFrom() == Update.getTo();
56 }
57 
applyDomTreeUpdates()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 
flush()73 void DomTreeUpdater::flush() {
74   applyDomTreeUpdates();
75   applyPostDomTreeUpdates();
76   dropOutOfDateUpdates();
77 }
78 
applyPostDomTreeUpdates()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 
tryFlushDeletedBB()95 void DomTreeUpdater::tryFlushDeletedBB() {
96   if (!hasPendingUpdates())
97     forceFlushDeletedBB();
98 }
99 
forceFlushDeletedBB()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 
recalculate(Function & F)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 
hasPendingUpdates() const151 bool DomTreeUpdater::hasPendingUpdates() const {
152   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
153 }
154 
hasPendingDomTreeUpdates() const155 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
156   if (!DT)
157     return false;
158   return PendUpdates.size() != PendDTUpdateIndex;
159 }
160 
hasPendingPostDomTreeUpdates() const161 bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
162   if (!PDT)
163     return false;
164   return PendUpdates.size() != PendPDTUpdateIndex;
165 }
166 
isBBPendingDeletion(llvm::BasicBlock * DelBB) const167 bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
168   if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
169     return false;
170   return DeletedBBs.contains(DelBB);
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.
deleteBB(BasicBlock * DelBB)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 
callbackDeleteBB(BasicBlock * DelBB,std::function<void (BasicBlock *)> Callback)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 
eraseDelBBNode(BasicBlock * DelBB)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 
validateDeleteBB(BasicBlock * DelBB)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 
applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates)231 void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
232   if (!DT && !PDT)
233     return;
234 
235   if (Strategy == UpdateStrategy::Lazy) {
236     PendUpdates.reserve(PendUpdates.size() + Updates.size());
237     for (const auto &U : Updates)
238       if (!isSelfDominance(U))
239         PendUpdates.push_back(U);
240 
241     return;
242   }
243 
244   if (DT)
245     DT->applyUpdates(Updates);
246   if (PDT)
247     PDT->applyUpdates(Updates);
248 }
249 
applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates)250 void DomTreeUpdater::applyUpdatesPermissive(
251     ArrayRef<DominatorTree::UpdateType> Updates) {
252   if (!DT && !PDT)
253     return;
254 
255   SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
256   SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
257   for (const auto &U : Updates) {
258     auto Edge = std::make_pair(U.getFrom(), U.getTo());
259     // Because it is illegal to submit updates that have already been applied
260     // and updates to an edge need to be strictly ordered,
261     // it is safe to infer the existence of an edge from the first update
262     // to this edge.
263     // If the first update to an edge is "Delete", it means that the edge
264     // existed before. If the first update to an edge is "Insert", it means
265     // that the edge didn't exist before.
266     //
267     // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
268     // because
269     // 1. it is illegal to submit updates that have already been applied,
270     // i.e., user cannot delete an nonexistent edge,
271     // 2. updates to an edge need to be strictly ordered,
272     // So, initially edge A -> B existed.
273     // We can then safely ignore future updates to this edge and directly
274     // inspect the current CFG:
275     // a. If the edge still exists, because the user cannot insert an existent
276     // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
277     // resulted in a no-op. DTU won't submit any update in this case.
278     // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
279     // actually happened but {Insert, A, B} was an invalid update which never
280     // happened. DTU will submit {Delete, A, B} in this case.
281     if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
282       Seen.insert(Edge);
283       // If the update doesn't appear in the CFG, it means that
284       // either the change isn't made or relevant operations
285       // result in a no-op.
286       if (isUpdateValid(U)) {
287         if (isLazy())
288           PendUpdates.push_back(U);
289         else
290           DeduplicatedUpdates.push_back(U);
291       }
292     }
293   }
294 
295   if (Strategy == UpdateStrategy::Lazy)
296     return;
297 
298   if (DT)
299     DT->applyUpdates(DeduplicatedUpdates);
300   if (PDT)
301     PDT->applyUpdates(DeduplicatedUpdates);
302 }
303 
getDomTree()304 DominatorTree &DomTreeUpdater::getDomTree() {
305   assert(DT && "Invalid acquisition of a null DomTree");
306   applyDomTreeUpdates();
307   dropOutOfDateUpdates();
308   return *DT;
309 }
310 
getPostDomTree()311 PostDominatorTree &DomTreeUpdater::getPostDomTree() {
312   assert(PDT && "Invalid acquisition of a null PostDomTree");
313   applyPostDomTreeUpdates();
314   dropOutOfDateUpdates();
315   return *PDT;
316 }
317 
dropOutOfDateUpdates()318 void DomTreeUpdater::dropOutOfDateUpdates() {
319   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
320     return;
321 
322   tryFlushDeletedBB();
323 
324   // Drop all updates applied by both trees.
325   if (!DT)
326     PendDTUpdateIndex = PendUpdates.size();
327   if (!PDT)
328     PendPDTUpdateIndex = PendUpdates.size();
329 
330   const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
331   const auto B = PendUpdates.begin();
332   const auto E = PendUpdates.begin() + dropIndex;
333   assert(B <= E && "Iterator out of range.");
334   PendUpdates.erase(B, E);
335   // Calculate current index.
336   PendDTUpdateIndex -= dropIndex;
337   PendPDTUpdateIndex -= dropIndex;
338 }
339 
340 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const341 LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
342   raw_ostream &OS = llvm::dbgs();
343 
344   OS << "Available Trees: ";
345   if (DT || PDT) {
346     if (DT)
347       OS << "DomTree ";
348     if (PDT)
349       OS << "PostDomTree ";
350     OS << "\n";
351   } else
352     OS << "None\n";
353 
354   OS << "UpdateStrategy: ";
355   if (Strategy == UpdateStrategy::Eager) {
356     OS << "Eager\n";
357     return;
358   } else
359     OS << "Lazy\n";
360   int Index = 0;
361 
362   auto printUpdates =
363       [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
364           ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
365         if (begin == end)
366           OS << "  None\n";
367         Index = 0;
368         for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
369           auto U = *It;
370           OS << "  " << Index << " : ";
371           ++Index;
372           if (U.getKind() == DominatorTree::Insert)
373             OS << "Insert, ";
374           else
375             OS << "Delete, ";
376           BasicBlock *From = U.getFrom();
377           if (From) {
378             auto S = From->getName();
379             if (!From->hasName())
380               S = "(no name)";
381             OS << S << "(" << From << "), ";
382           } else {
383             OS << "(badref), ";
384           }
385           BasicBlock *To = U.getTo();
386           if (To) {
387             auto S = To->getName();
388             if (!To->hasName())
389               S = "(no_name)";
390             OS << S << "(" << To << ")\n";
391           } else {
392             OS << "(badref)\n";
393           }
394         }
395       };
396 
397   if (DT) {
398     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
399     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
400            "Iterator out of range.");
401     OS << "Applied but not cleared DomTreeUpdates:\n";
402     printUpdates(PendUpdates.begin(), I);
403     OS << "Pending DomTreeUpdates:\n";
404     printUpdates(I, PendUpdates.end());
405   }
406 
407   if (PDT) {
408     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
409     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
410            "Iterator out of range.");
411     OS << "Applied but not cleared PostDomTreeUpdates:\n";
412     printUpdates(PendUpdates.begin(), I);
413     OS << "Pending PostDomTreeUpdates:\n";
414     printUpdates(I, PendUpdates.end());
415   }
416 
417   OS << "Pending DeletedBBs:\n";
418   Index = 0;
419   for (const auto *BB : DeletedBBs) {
420     OS << "  " << Index << " : ";
421     ++Index;
422     if (BB->hasName())
423       OS << BB->getName() << "(";
424     else
425       OS << "(no_name)(";
426     OS << BB << ")\n";
427   }
428 
429   OS << "Pending Callbacks:\n";
430   Index = 0;
431   for (const auto &BB : Callbacks) {
432     OS << "  " << Index << " : ";
433     ++Index;
434     if (BB->hasName())
435       OS << BB->getName() << "(";
436     else
437       OS << "(no_name)(";
438     OS << BB << ")\n";
439   }
440 }
441 #endif
442 } // namespace llvm
443