1 //===- GenericDomTreeUpdaterImpl.h ------------------------------*- 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 GenericDomTreeUpdater class. This file should only
10 // be included by files that implement a specialization of the relevant
11 // templates. Currently these are:
12 // - llvm/lib/Analysis/DomTreeUpdater.cpp
13 // - llvm/lib/CodeGen/MachineDomTreeUpdater.cpp
14 //
15 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H
17 #define LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H
18
19 #include "llvm/ADT/SmallBitVector.h"
20 #include "llvm/Analysis/GenericDomTreeUpdater.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
23
24 namespace llvm {
25
26 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
27 template <typename FuncT>
recalculate(FuncT & F)28 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::recalculate(
29 FuncT &F) {
30 if (Strategy == UpdateStrategy::Eager) {
31 if (DT)
32 DT->recalculate(F);
33 if (PDT)
34 PDT->recalculate(F);
35 return;
36 }
37
38 // There is little performance gain if we pend the recalculation under
39 // Lazy UpdateStrategy so we recalculate available trees immediately.
40
41 // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
42 IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
43
44 // Because all trees are going to be up-to-date after recalculation,
45 // flush awaiting deleted BasicBlocks.
46 derived().forceFlushDeletedBB();
47 if (DT)
48 DT->recalculate(F);
49 if (PDT)
50 PDT->recalculate(F);
51
52 // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
53 IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
54 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
55 dropOutOfDateUpdates();
56 }
57
58 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
applyUpdates(ArrayRef<UpdateT> Updates)59 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::applyUpdates(
60 ArrayRef<UpdateT> Updates) {
61 if (!DT && !PDT)
62 return;
63
64 if (Strategy == UpdateStrategy::Lazy) {
65 PendUpdates.reserve(PendUpdates.size() + Updates.size());
66 for (const auto &U : Updates)
67 if (!isSelfDominance(U))
68 PendUpdates.push_back(U);
69
70 return;
71 }
72
73 if (DT)
74 DT->applyUpdates(Updates);
75 if (PDT)
76 PDT->applyUpdates(Updates);
77 }
78
79 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
80 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
applyUpdatesPermissive(ArrayRef<UpdateT> Updates)81 applyUpdatesPermissive(ArrayRef<UpdateT> Updates) {
82 if (!DT && !PDT)
83 return;
84
85 SmallSet<std::pair<BasicBlockT *, BasicBlockT *>, 8> Seen;
86 SmallVector<UpdateT, 8> DeduplicatedUpdates;
87 for (const auto &U : Updates) {
88 auto Edge = std::make_pair(U.getFrom(), U.getTo());
89 // Because it is illegal to submit updates that have already been applied
90 // and updates to an edge need to be strictly ordered,
91 // it is safe to infer the existence of an edge from the first update
92 // to this edge.
93 // If the first update to an edge is "Delete", it means that the edge
94 // existed before. If the first update to an edge is "Insert", it means
95 // that the edge didn't exist before.
96 //
97 // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
98 // because
99 // 1. it is illegal to submit updates that have already been applied,
100 // i.e., user cannot delete an nonexistent edge,
101 // 2. updates to an edge need to be strictly ordered,
102 // So, initially edge A -> B existed.
103 // We can then safely ignore future updates to this edge and directly
104 // inspect the current CFG:
105 // a. If the edge still exists, because the user cannot insert an existent
106 // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
107 // resulted in a no-op. DTU won't submit any update in this case.
108 // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
109 // actually happened but {Insert, A, B} was an invalid update which never
110 // happened. DTU will submit {Delete, A, B} in this case.
111 if (!isSelfDominance(U) && Seen.insert(Edge).second) {
112 // If the update doesn't appear in the CFG, it means that
113 // either the change isn't made or relevant operations
114 // result in a no-op.
115 if (isUpdateValid(U)) {
116 if (isLazy())
117 PendUpdates.push_back(U);
118 else
119 DeduplicatedUpdates.push_back(U);
120 }
121 }
122 }
123
124 if (Strategy == UpdateStrategy::Lazy)
125 return;
126
127 if (DT)
128 DT->applyUpdates(DeduplicatedUpdates);
129 if (PDT)
130 PDT->applyUpdates(DeduplicatedUpdates);
131 }
132
133 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
splitCriticalEdge(BasicBlockT * FromBB,BasicBlockT * ToBB,BasicBlockT * NewBB)134 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::splitCriticalEdge(
135 BasicBlockT *FromBB, BasicBlockT *ToBB, BasicBlockT *NewBB) {
136 if (!DT && !PDT)
137 return;
138
139 CriticalEdge E = {FromBB, ToBB, NewBB};
140 if (Strategy == UpdateStrategy::Lazy) {
141 PendUpdates.push_back(E);
142 return;
143 }
144
145 if (DT)
146 splitDTCriticalEdges(E);
147 if (PDT)
148 splitPDTCriticalEdges(E);
149 }
150
151 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
152 DomTreeT &
getDomTree()153 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::getDomTree() {
154 assert(DT && "Invalid acquisition of a null DomTree");
155 applyDomTreeUpdates();
156 dropOutOfDateUpdates();
157 return *DT;
158 }
159
160 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
161 PostDomTreeT &
getPostDomTree()162 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::getPostDomTree() {
163 assert(PDT && "Invalid acquisition of a null PostDomTree");
164 applyPostDomTreeUpdates();
165 dropOutOfDateUpdates();
166 return *PDT;
167 }
168
169 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
170 LLVM_DUMP_METHOD void
dump()171 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::dump() const {
172 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
173 raw_ostream &OS = llvm::dbgs();
174
175 OS << "Available Trees: ";
176 if (DT || PDT) {
177 if (DT)
178 OS << "DomTree ";
179 if (PDT)
180 OS << "PostDomTree ";
181 OS << "\n";
182 } else
183 OS << "None\n";
184
185 OS << "UpdateStrategy: ";
186 if (Strategy == UpdateStrategy::Eager) {
187 OS << "Eager\n";
188 return;
189 } else
190 OS << "Lazy\n";
191 int Index = 0;
192
193 auto printBlockInfo = [&](BasicBlockT *BB, StringRef Ending) {
194 if (BB) {
195 auto S = BB->getName();
196 if (!BB->hasName())
197 S = "(no name)";
198 OS << S << "(" << BB << ")" << Ending;
199 } else {
200 OS << "(badref)" << Ending;
201 }
202 };
203
204 auto printUpdates =
205 [&](typename ArrayRef<DomTreeUpdate>::const_iterator begin,
206 typename ArrayRef<DomTreeUpdate>::const_iterator end) {
207 if (begin == end)
208 OS << " None\n";
209 Index = 0;
210 for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
211 if (!It->IsCriticalEdgeSplit) {
212 auto U = It->Update;
213 OS << " " << Index << " : ";
214 ++Index;
215 if (U.getKind() == DomTreeT::Insert)
216 OS << "Insert, ";
217 else
218 OS << "Delete, ";
219 printBlockInfo(U.getFrom(), ", ");
220 printBlockInfo(U.getTo(), "\n");
221 } else {
222 const auto &Edge = It->EdgeSplit;
223 OS << " " << Index++ << " : Split critical edge, ";
224 printBlockInfo(Edge.FromBB, ", ");
225 printBlockInfo(Edge.ToBB, ", ");
226 printBlockInfo(Edge.NewBB, "\n");
227 }
228 }
229 };
230
231 if (DT) {
232 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
233 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
234 "Iterator out of range.");
235 OS << "Applied but not cleared DomTreeUpdates:\n";
236 printUpdates(PendUpdates.begin(), I);
237 OS << "Pending DomTreeUpdates:\n";
238 printUpdates(I, PendUpdates.end());
239 }
240
241 if (PDT) {
242 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
243 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
244 "Iterator out of range.");
245 OS << "Applied but not cleared PostDomTreeUpdates:\n";
246 printUpdates(PendUpdates.begin(), I);
247 OS << "Pending PostDomTreeUpdates:\n";
248 printUpdates(I, PendUpdates.end());
249 }
250
251 OS << "Pending DeletedBBs:\n";
252 Index = 0;
253 for (const auto *BB : DeletedBBs) {
254 OS << " " << Index << " : ";
255 ++Index;
256 if (BB->hasName())
257 OS << BB->getName() << "(";
258 else
259 OS << "(no name)(";
260 OS << BB << ")\n";
261 }
262 #endif
263 }
264
265 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
266 template <bool IsForward>
267 void GenericDomTreeUpdater<DerivedT, DomTreeT,
applyUpdatesImpl()268 PostDomTreeT>::applyUpdatesImpl() {
269 auto *DomTree = [&]() {
270 if constexpr (IsForward)
271 return DT;
272 else
273 return PDT;
274 }();
275 // No pending DomTreeUpdates.
276 if (Strategy != UpdateStrategy::Lazy || !DomTree)
277 return;
278 size_t &PendUpdateIndex = IsForward ? PendDTUpdateIndex : PendPDTUpdateIndex;
279
280 // Only apply updates not are applied by (Post)DomTree.
281 while (IsForward ? hasPendingDomTreeUpdates()
282 : hasPendingPostDomTreeUpdates()) {
283 auto I = PendUpdates.begin() + PendUpdateIndex;
284 const auto E = PendUpdates.end();
285 assert(I < E && "Iterator range invalid; there should be DomTree updates.");
286 if (!I->IsCriticalEdgeSplit) {
287 SmallVector<UpdateT, 32> NormalUpdates;
288 for (; I != E && !I->IsCriticalEdgeSplit; ++I)
289 NormalUpdates.push_back(I->Update);
290 DomTree->applyUpdates(NormalUpdates);
291 PendUpdateIndex += NormalUpdates.size();
292 } else {
293 SmallVector<CriticalEdge> CriticalEdges;
294 for (; I != E && I->IsCriticalEdgeSplit; ++I)
295 CriticalEdges.push_back(I->EdgeSplit);
296 IsForward ? splitDTCriticalEdges(CriticalEdges)
297 : splitPDTCriticalEdges(CriticalEdges);
298 PendUpdateIndex += CriticalEdges.size();
299 }
300 }
301 }
302
303 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
isUpdateValid(UpdateT Update)304 bool GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::isUpdateValid(
305 UpdateT Update) const {
306 const auto *From = Update.getFrom();
307 const auto *To = Update.getTo();
308 const auto Kind = Update.getKind();
309
310 // Discard updates by inspecting the current state of successors of From.
311 // Since isUpdateValid() must be called *after* the Terminator of From is
312 // altered we can determine if the update is unnecessary for batch updates
313 // or invalid for a single update.
314 const bool HasEdge = llvm::is_contained(successors(From), To);
315
316 // If the IR does not match the update,
317 // 1. In batch updates, this update is unnecessary.
318 // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
319 // Edge does not exist in IR.
320 if (Kind == DomTreeT::Insert && !HasEdge)
321 return false;
322
323 // Edge exists in IR.
324 if (Kind == DomTreeT::Delete && HasEdge)
325 return false;
326
327 return true;
328 }
329
330 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
eraseDelBBNode(BasicBlockT * DelBB)331 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::eraseDelBBNode(
332 BasicBlockT *DelBB) {
333 if (DT && !IsRecalculatingDomTree)
334 if (DT->getNode(DelBB))
335 DT->eraseNode(DelBB);
336
337 if (PDT && !IsRecalculatingPostDomTree)
338 if (PDT->getNode(DelBB))
339 PDT->eraseNode(DelBB);
340 }
341
342 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
343 void GenericDomTreeUpdater<DerivedT, DomTreeT,
tryFlushDeletedBB()344 PostDomTreeT>::tryFlushDeletedBB() {
345 if (!hasPendingUpdates())
346 derived().forceFlushDeletedBB();
347 }
348
349 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
350 void GenericDomTreeUpdater<DerivedT, DomTreeT,
dropOutOfDateUpdates()351 PostDomTreeT>::dropOutOfDateUpdates() {
352 if (Strategy == UpdateStrategy::Eager)
353 return;
354
355 tryFlushDeletedBB();
356
357 // Drop all updates applied by both trees.
358 if (!DT)
359 PendDTUpdateIndex = PendUpdates.size();
360 if (!PDT)
361 PendPDTUpdateIndex = PendUpdates.size();
362
363 const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
364 const auto B = PendUpdates.begin();
365 const auto E = PendUpdates.begin() + dropIndex;
366 assert(B <= E && "Iterator out of range.");
367 PendUpdates.erase(B, E);
368 // Calculate current index.
369 PendDTUpdateIndex -= dropIndex;
370 PendPDTUpdateIndex -= dropIndex;
371 }
372
373 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
374 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
splitDTCriticalEdges(ArrayRef<CriticalEdge> Edges)375 splitDTCriticalEdges(ArrayRef<CriticalEdge> Edges) {
376 // Bail out early if there is nothing to do.
377 if (!DT || Edges.empty())
378 return;
379
380 // Remember all the basic blocks that are inserted during
381 // edge splitting.
382 // Invariant: NewBBs == all the basic blocks contained in the NewBB
383 // field of all the elements of Edges.
384 // I.e., forall elt in Edges, it exists BB in NewBBs
385 // such as BB == elt.NewBB.
386 SmallSet<BasicBlockT *, 32> NewBBs;
387 for (auto &Edge : Edges)
388 NewBBs.insert(Edge.NewBB);
389 // For each element in Edges, remember whether or not element
390 // is the new immediate domminator of its successor. The mapping is done by
391 // index, i.e., the information for the ith element of Edges is
392 // the ith element of IsNewIDom.
393 SmallBitVector IsNewIDom(Edges.size(), true);
394
395 // Collect all the dominance properties info, before invalidating
396 // the underlying DT.
397 for (const auto &[Idx, Edge] : enumerate(Edges)) {
398 // Update dominator information.
399 BasicBlockT *Succ = Edge.ToBB;
400 auto *SuccDTNode = DT->getNode(Succ);
401
402 for (BasicBlockT *PredBB : predecessors(Succ)) {
403 if (PredBB == Edge.NewBB)
404 continue;
405 // If we are in this situation:
406 // FromBB1 FromBB2
407 // + +
408 // + + + +
409 // + + + +
410 // ... Split1 Split2 ...
411 // + +
412 // + +
413 // +
414 // Succ
415 // Instead of checking the domiance property with Split2, we check it
416 // with FromBB2 since Split2 is still unknown of the underlying DT
417 // structure.
418 if (NewBBs.contains(PredBB)) {
419 assert(pred_size(PredBB) == 1 && "A basic block resulting from a "
420 "critical edge split has more "
421 "than one predecessor!");
422 PredBB = *pred_begin(PredBB);
423 }
424 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
425 IsNewIDom[Idx] = false;
426 break;
427 }
428 }
429 }
430
431 // Now, update DT with the collected dominance properties info.
432 for (const auto &[Idx, Edge] : enumerate(Edges)) {
433 // We know FromBB dominates NewBB.
434 auto *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
435
436 // If all the other predecessors of "Succ" are dominated by "Succ" itself
437 // then the new block is the new immediate dominator of "Succ". Otherwise,
438 // the new block doesn't dominate anything.
439 if (IsNewIDom[Idx])
440 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
441 }
442 }
443
444 // Post dominator tree is different, the new basic block in critical edge
445 // may become the new root.
446 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
447 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
splitPDTCriticalEdges(ArrayRef<CriticalEdge> Edges)448 splitPDTCriticalEdges(ArrayRef<CriticalEdge> Edges) {
449 // Bail out early if there is nothing to do.
450 if (!PDT || Edges.empty())
451 return;
452
453 std::vector<UpdateT> Updates;
454 for (const auto &Edge : Edges) {
455 Updates.push_back({PostDomTreeT::Insert, Edge.FromBB, Edge.NewBB});
456 Updates.push_back({PostDomTreeT::Insert, Edge.NewBB, Edge.ToBB});
457 if (!llvm::is_contained(successors(Edge.FromBB), Edge.ToBB))
458 Updates.push_back({PostDomTreeT::Delete, Edge.FromBB, Edge.ToBB});
459 }
460 PDT->applyUpdates(Updates);
461 }
462
463 } // namespace llvm
464
465 #endif // LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H
466