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/Analysis/GenericDomTreeUpdater.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
22
23 namespace llvm {
24
25 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
26 template <typename FuncT>
recalculate(FuncT & F)27 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::recalculate(
28 FuncT &F) {
29 if (Strategy == UpdateStrategy::Eager) {
30 if (DT)
31 DT->recalculate(F);
32 if (PDT)
33 PDT->recalculate(F);
34 return;
35 }
36
37 // There is little performance gain if we pend the recalculation under
38 // Lazy UpdateStrategy so we recalculate available trees immediately.
39
40 // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
41 IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
42
43 // Because all trees are going to be up-to-date after recalculation,
44 // flush awaiting deleted BasicBlocks.
45 derived().forceFlushDeletedBB();
46 if (DT)
47 DT->recalculate(F);
48 if (PDT)
49 PDT->recalculate(F);
50
51 // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
52 IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
53 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
54 dropOutOfDateUpdates();
55 }
56
57 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
applyUpdates(ArrayRef<typename DomTreeT::UpdateType> Updates)58 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::applyUpdates(
59 ArrayRef<typename DomTreeT::UpdateType> Updates) {
60 if (!DT && !PDT)
61 return;
62
63 if (Strategy == UpdateStrategy::Lazy) {
64 PendUpdates.reserve(PendUpdates.size() + Updates.size());
65 for (const auto &U : Updates)
66 if (!isSelfDominance(U))
67 PendUpdates.push_back(U);
68
69 return;
70 }
71
72 if (DT)
73 DT->applyUpdates(Updates);
74 if (PDT)
75 PDT->applyUpdates(Updates);
76 }
77
78 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
79 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
applyUpdatesPermissive(ArrayRef<typename DomTreeT::UpdateType> Updates)80 applyUpdatesPermissive(ArrayRef<typename DomTreeT::UpdateType> Updates) {
81 if (!DT && !PDT)
82 return;
83
84 SmallSet<std::pair<BasicBlockT *, BasicBlockT *>, 8> Seen;
85 SmallVector<typename DomTreeT::UpdateType, 8> DeduplicatedUpdates;
86 for (const auto &U : Updates) {
87 auto Edge = std::make_pair(U.getFrom(), U.getTo());
88 // Because it is illegal to submit updates that have already been applied
89 // and updates to an edge need to be strictly ordered,
90 // it is safe to infer the existence of an edge from the first update
91 // to this edge.
92 // If the first update to an edge is "Delete", it means that the edge
93 // existed before. If the first update to an edge is "Insert", it means
94 // that the edge didn't exist before.
95 //
96 // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
97 // because
98 // 1. it is illegal to submit updates that have already been applied,
99 // i.e., user cannot delete an nonexistent edge,
100 // 2. updates to an edge need to be strictly ordered,
101 // So, initially edge A -> B existed.
102 // We can then safely ignore future updates to this edge and directly
103 // inspect the current CFG:
104 // a. If the edge still exists, because the user cannot insert an existent
105 // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
106 // resulted in a no-op. DTU won't submit any update in this case.
107 // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
108 // actually happened but {Insert, A, B} was an invalid update which never
109 // happened. DTU will submit {Delete, A, B} in this case.
110 if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
111 Seen.insert(Edge);
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>
134 DomTreeT &
getDomTree()135 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::getDomTree() {
136 assert(DT && "Invalid acquisition of a null DomTree");
137 applyDomTreeUpdates();
138 dropOutOfDateUpdates();
139 return *DT;
140 }
141
142 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
143 PostDomTreeT &
getPostDomTree()144 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::getPostDomTree() {
145 assert(PDT && "Invalid acquisition of a null PostDomTree");
146 applyPostDomTreeUpdates();
147 dropOutOfDateUpdates();
148 return *PDT;
149 }
150
151 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
152 LLVM_DUMP_METHOD void
dump()153 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::dump() const {
154 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
155 raw_ostream &OS = llvm::dbgs();
156
157 OS << "Available Trees: ";
158 if (DT || PDT) {
159 if (DT)
160 OS << "DomTree ";
161 if (PDT)
162 OS << "PostDomTree ";
163 OS << "\n";
164 } else
165 OS << "None\n";
166
167 OS << "UpdateStrategy: ";
168 if (Strategy == UpdateStrategy::Eager) {
169 OS << "Eager\n";
170 return;
171 } else
172 OS << "Lazy\n";
173 int Index = 0;
174
175 auto printUpdates =
176 [&](typename ArrayRef<typename DomTreeT::UpdateType>::const_iterator
177 begin,
178 typename ArrayRef<typename DomTreeT::UpdateType>::const_iterator
179 end) {
180 if (begin == end)
181 OS << " None\n";
182 Index = 0;
183 for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
184 auto U = *It;
185 OS << " " << Index << " : ";
186 ++Index;
187 if (U.getKind() == DomTreeT::Insert)
188 OS << "Insert, ";
189 else
190 OS << "Delete, ";
191 BasicBlockT *From = U.getFrom();
192 if (From) {
193 auto S = From->getName();
194 if (!From->hasName())
195 S = "(no name)";
196 OS << S << "(" << From << "), ";
197 } else {
198 OS << "(badref), ";
199 }
200 BasicBlockT *To = U.getTo();
201 if (To) {
202 auto S = To->getName();
203 if (!To->hasName())
204 S = "(no_name)";
205 OS << S << "(" << To << ")\n";
206 } else {
207 OS << "(badref)\n";
208 }
209 }
210 };
211
212 if (DT) {
213 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
214 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
215 "Iterator out of range.");
216 OS << "Applied but not cleared DomTreeUpdates:\n";
217 printUpdates(PendUpdates.begin(), I);
218 OS << "Pending DomTreeUpdates:\n";
219 printUpdates(I, PendUpdates.end());
220 }
221
222 if (PDT) {
223 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
224 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
225 "Iterator out of range.");
226 OS << "Applied but not cleared PostDomTreeUpdates:\n";
227 printUpdates(PendUpdates.begin(), I);
228 OS << "Pending PostDomTreeUpdates:\n";
229 printUpdates(I, PendUpdates.end());
230 }
231
232 OS << "Pending DeletedBBs:\n";
233 Index = 0;
234 for (const auto *BB : DeletedBBs) {
235 OS << " " << Index << " : ";
236 ++Index;
237 if (BB->hasName())
238 OS << BB->getName() << "(";
239 else
240 OS << "(no_name)(";
241 OS << BB << ")\n";
242 }
243 #endif
244 }
245
246 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
247 void GenericDomTreeUpdater<DerivedT, DomTreeT,
applyDomTreeUpdates()248 PostDomTreeT>::applyDomTreeUpdates() {
249 // No pending DomTreeUpdates.
250 if (Strategy != UpdateStrategy::Lazy || !DT)
251 return;
252
253 // Only apply updates not are applied by DomTree.
254 if (hasPendingDomTreeUpdates()) {
255 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
256 const auto E = PendUpdates.end();
257 assert(I < E && "Iterator range invalid; there should be DomTree updates.");
258 DT->applyUpdates(ArrayRef<typename DomTreeT::UpdateType>(I, E));
259 PendDTUpdateIndex = PendUpdates.size();
260 }
261 }
262
263 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
264 void GenericDomTreeUpdater<DerivedT, DomTreeT,
applyPostDomTreeUpdates()265 PostDomTreeT>::applyPostDomTreeUpdates() {
266 // No pending PostDomTreeUpdates.
267 if (Strategy != UpdateStrategy::Lazy || !PDT)
268 return;
269
270 // Only apply updates not are applied by PostDomTree.
271 if (hasPendingPostDomTreeUpdates()) {
272 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
273 const auto E = PendUpdates.end();
274 assert(I < E &&
275 "Iterator range invalid; there should be PostDomTree updates.");
276 PDT->applyUpdates(ArrayRef<typename DomTreeT::UpdateType>(I, E));
277 PendPDTUpdateIndex = PendUpdates.size();
278 }
279 }
280
281 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
isUpdateValid(typename DomTreeT::UpdateType Update)282 bool GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::isUpdateValid(
283 typename DomTreeT::UpdateType Update) const {
284 const auto *From = Update.getFrom();
285 const auto *To = Update.getTo();
286 const auto Kind = Update.getKind();
287
288 // Discard updates by inspecting the current state of successors of From.
289 // Since isUpdateValid() must be called *after* the Terminator of From is
290 // altered we can determine if the update is unnecessary for batch updates
291 // or invalid for a single update.
292 const bool HasEdge = llvm::is_contained(successors(From), To);
293
294 // If the IR does not match the update,
295 // 1. In batch updates, this update is unnecessary.
296 // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
297 // Edge does not exist in IR.
298 if (Kind == DomTreeT::Insert && !HasEdge)
299 return false;
300
301 // Edge exists in IR.
302 if (Kind == DomTreeT::Delete && HasEdge)
303 return false;
304
305 return true;
306 }
307
308 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
eraseDelBBNode(BasicBlockT * DelBB)309 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::eraseDelBBNode(
310 BasicBlockT *DelBB) {
311 if (DT && !IsRecalculatingDomTree)
312 if (DT->getNode(DelBB))
313 DT->eraseNode(DelBB);
314
315 if (PDT && !IsRecalculatingPostDomTree)
316 if (PDT->getNode(DelBB))
317 PDT->eraseNode(DelBB);
318 }
319
320 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
321 void GenericDomTreeUpdater<DerivedT, DomTreeT,
tryFlushDeletedBB()322 PostDomTreeT>::tryFlushDeletedBB() {
323 if (!hasPendingUpdates())
324 derived().forceFlushDeletedBB();
325 }
326
327 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
328 void GenericDomTreeUpdater<DerivedT, DomTreeT,
dropOutOfDateUpdates()329 PostDomTreeT>::dropOutOfDateUpdates() {
330 if (Strategy == UpdateStrategy::Eager)
331 return;
332
333 tryFlushDeletedBB();
334
335 // Drop all updates applied by both trees.
336 if (!DT)
337 PendDTUpdateIndex = PendUpdates.size();
338 if (!PDT)
339 PendPDTUpdateIndex = PendUpdates.size();
340
341 const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
342 const auto B = PendUpdates.begin();
343 const auto E = PendUpdates.begin() + dropIndex;
344 assert(B <= E && "Iterator out of range.");
345 PendUpdates.erase(B, E);
346 // Calculate current index.
347 PendDTUpdateIndex -= dropIndex;
348 PendPDTUpdateIndex -= dropIndex;
349 }
350
351 } // namespace llvm
352
353 #endif // LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H
354