LLVM: include/llvm/Analysis/GenericDomTreeUpdaterImpl.h Source File

LLVM 22.0.0git
GenericDomTreeUpdaterImpl.h
Go to the documentation of this file.
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
24namespace llvm {
25
26template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
27template <typename FuncT>
29 FuncT &F) {
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.
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.
56}
57
58template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
60 ArrayRef<UpdateT> Updates) {
61 if (!DT && !PDT)
62 return;
63
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
79template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
82 if (!DT && !PDT)
83 return;
84
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
125 return;
126
127 if (DT)
128 DT->applyUpdates(DeduplicatedUpdates);
129 if (PDT)
130 PDT->applyUpdates(DeduplicatedUpdates);
131}
132
133template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
135 BasicBlockT *FromBB, BasicBlockT *ToBB, BasicBlockT *NewBB) {
136 if (!DT && !PDT)
137 return;
138
139 CriticalEdge E = {FromBB, ToBB, NewBB};
141 PendUpdates.push_back(E);
142 return;
143 }
144
145 if (DT)
146 splitDTCriticalEdges(E);
147 if (PDT)
148 splitPDTCriticalEdges(E);
149}
150
151template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
152DomTreeT &
154 assert(DT && "Invalid acquisition of a null DomTree");
157 return *DT;
158}
159
160template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
161PostDomTreeT &
163 assert(PDT && "Invalid acquisition of a null PostDomTree");
166 return *PDT;
167}
168
169template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
170LLVM_DUMP_METHOD void
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: ";
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 =
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
265template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
266template <bool IsForward>
267void GenericDomTreeUpdater<DerivedT, DomTreeT,
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
303template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
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
330template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
332 BasicBlockT *DelBB) {
334 if (DT->getNode(DelBB))
335 DT->eraseNode(DelBB);
336
338 if (PDT->getNode(DelBB))
339 PDT->eraseNode(DelBB);
340}
341
342template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
343void GenericDomTreeUpdater<DerivedT, DomTreeT,
344 PostDomTreeT>::tryFlushDeletedBB() {
345 if (!hasPendingUpdates())
346 derived().forceFlushDeletedBB();
347}
348
349template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
350void GenericDomTreeUpdater<DerivedT, DomTreeT,
351 PostDomTreeT>::dropOutOfDateUpdates() {
353 return;
354
356
357 // Drop all updates applied by both trees.
358 if (!DT)
360 if (!PDT)
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
373template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
374void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
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 SmallPtrSet<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.
446template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
447void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
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
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:638
F
#define F(x, y, z)
Definition MD5.cpp:55
I
#define I(x, y, z)
Definition MD5.cpp:58
std::pair< BasicBlock *, BasicBlock * > Edge
This file implements the SmallBitVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:41
const_pointer const_iterator
Definition ArrayRef.h:49
size_t size() const
size - Get the array size.
Definition ArrayRef.h:143
bool empty() const
empty - Check if the array is empty.
Definition ArrayRef.h:138
SmallPtrSet< BasicBlockT *, 8 > DeletedBBs
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
PostDomTreeT & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
void applyPostDomTreeUpdates()
Helper function to apply all pending PostDomTree updates.
void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
void eraseDelBBNode(BasicBlockT *DelBB)
Erase Basic Block node before it is unlinked from Function in the DomTree and PostDomTree.
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending.
bool isSelfDominance(UpdateT Update) const
Returns true if the update is self dominance.
typename DomTreeT::UpdateType UpdateT
typename DomTreeT::NodeType BasicBlockT
void recalculate(FuncT &F)
Notify DTU that the entry block was replaced.
void tryFlushDeletedBB()
Helper function to flush deleted BasicBlocks if all available trees are up-to-date.
void dropOutOfDateUpdates()
Drop all updates applied by all available trees and delete BasicBlocks if all available trees are up-...
void splitCriticalEdge(BasicBlockT *FromBB, BasicBlockT *ToBB, BasicBlockT *NewBB)
Apply updates that the critical edge (FromBB, ToBB) has been split with NewBB.
void applyDomTreeUpdates()
Helper function to apply all pending DomTree updates.
bool isUpdateValid(UpdateT Update) const
Returns true if the update appears in the LLVM IR.
SmallVector< DomTreeUpdate, 16 > PendUpdates
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
bool isLazy() const
Returns true if the current strategy is Lazy.
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition SmallPtrSet.h:389
bool contains(ConstPtrType Ptr) const
Definition SmallPtrSet.h:461
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition SmallPtrSet.h:527
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition SmallSet.h:133
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition SmallSet.h:183
void push_back(const T &Elt)
Definition SmallVector.h:417
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition SmallVector.h:1203
StringRef - Represent a constant reference to a string, i.e.
Definition StringRef.h:55
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
This is an optimization pass for GlobalISel generic memory operations.
Definition AddressRanges.h:18
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition STLExtras.h:2472
auto successors(const MachineBasicBlock *BB)
auto pred_size(const MachineBasicBlock *BB)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
Definition SmallVector.h:1129
auto pred_begin(const MachineBasicBlock *BB)
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1897
Helper structure used to hold all the basic blocks involved in the split of a critical edge.
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /