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 | |
26 | 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(Range: successors(BB: From), Element: 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(Updates: 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(Updates: 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->size() == 1 && isa<UnreachableInst>(BB->getTerminator()) && |
110 | "DelBB has been modified while awaiting deletion." ); |
111 | BB->removeFromParent(); |
112 | eraseDelBBNode(DelBB: 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(Func&: F); |
125 | if (PDT) |
126 | PDT->recalculate(Func&: 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(Func&: F); |
141 | if (PDT) |
142 | PDT->recalculate(Func&: 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(Ptr: 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(Ptr: 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(x: CallBackOnDeletion(DelBB, Callback)); |
194 | DeletedBBs.insert(Ptr: 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(BB: DelBB)) |
207 | DT->eraseNode(BB: DelBB); |
208 | |
209 | if (PDT && !IsRecalculatingPostDomTree) |
210 | if (PDT->getNode(BB: DelBB)) |
211 | PDT->eraseNode(BB: 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 (poison). |
221 | if (!I.use_empty()) |
222 | I.replaceAllUsesWith(V: PoisonValue::get(T: 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 | |
230 | void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) { |
231 | if (!DT && !PDT) |
232 | return; |
233 | |
234 | if (Strategy == UpdateStrategy::Lazy) { |
235 | PendUpdates.reserve(N: PendUpdates.size() + Updates.size()); |
236 | for (const auto &U : Updates) |
237 | if (!isSelfDominance(Update: U)) |
238 | PendUpdates.push_back(Elt: 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(x: U.getFrom(), y: 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(Update: U) && Seen.count(V: Edge) == 0) { |
281 | Seen.insert(V: 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(Update: U)) { |
286 | if (isLazy()) |
287 | PendUpdates.push_back(Elt: U); |
288 | else |
289 | DeduplicatedUpdates.push_back(Elt: U); |
290 | } |
291 | } |
292 | } |
293 | |
294 | if (Strategy == UpdateStrategy::Lazy) |
295 | return; |
296 | |
297 | if (DT) |
298 | DT->applyUpdates(Updates: DeduplicatedUpdates); |
299 | if (PDT) |
300 | PDT->applyUpdates(Updates: 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::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(a: PendDTUpdateIndex, b: 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(CS: B, CE: E); |
334 | // Calculate current index. |
335 | PendDTUpdateIndex -= dropIndex; |
336 | PendPDTUpdateIndex -= dropIndex; |
337 | } |
338 | |
339 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
340 | LLVM_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 | |