LLVM 24.0.0git
DependencyTracker.h
Go to the documentation of this file.
1//===- "DependencyTracker.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#ifndef LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H
10#define LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H
11
13#include "llvm/ADT/DenseMap.h"
16
17namespace llvm {
19class DWARFDie;
20
21namespace dwarf_linker {
22namespace parallel {
23
24/// This class discovers DIEs dependencies: marks "live" DIEs, marks DIE
25/// locations (whether DIE should be cloned as regular DIE or it should be put
26/// into the artificial type unit).
28public:
30
31 /// This function is the entry point of the DIE selection algorithm. It is
32 /// expected to walk the DIE tree and(through the mediation of
33 /// Context.File.Addresses) ask for relocation adjustment value on each
34 /// DIE that might be a 'root DIE'(f.e. subprograms, variables).
35 void collectLiveRoots();
36
37 /// Recursively walk the \p DIE tree and look for DIEs to keep. Store that
38 /// information in \p CU's DIEInfo. This method should be called as a
39 /// followup processing after collectLiveRoots().
40 ///
41 /// Returns true if all dependencies are correctly discovered. Inter-CU
42 /// dependencies cannot be discovered if referenced CU is not analyzed yet.
43 /// If that is the case this method returns false.
45 bool InterCUProcessingStarted,
46 std::atomic<bool> &HasNewInterconnectedCUs);
47
48 /// Check if dependencies have incompatible placement.
49 /// If that is the case modify placement to be compatible.
50 /// \returns true if any placement was updated, otherwise returns false.
51 /// This method should be called as a followup processing after
52 /// resolveDependenciesAndMarkLiveness().
54
55 /// Recursively walk the \p DIE tree and check "keepness" and "placement"
56 /// information. It is an error if parent node does not have "keep" flag,
57 /// while child has one. It is an error if parent node has "TypeTable"
58 /// placement while child has "PlainDwarf" placement. This function dump error
59 /// at stderr in that case.
60 void verifyKeepChain();
61
62protected:
64 /// Mark current item as live entry.
66
67 /// Mark current item as type entry.
69
70 /// Mark current item and all its children as live entry.
72
73 /// Mark current item and all its children as type entry.
75
76 /// Mark all children of current item as live entry.
78
79 /// Mark all children of current item as type entry.
81 };
82
83 /// \returns true if the specified action is for the "PlainDwarf".
85 switch (Action) {
86 default:
87 return false;
88
92 return true;
93 }
94 }
95
96 /// \returns true if the specified action is for the "TypeTable".
98 switch (Action) {
99 default:
100 return false;
101
105 return true;
106 }
107 }
108
109 /// \returns true if the specified action affects only Root entry
110 /// itself and does not affect it`s children.
111 bool isSingleAction(LiveRootWorklistActionTy Action) {
112 switch (Action) {
113 default:
114 return false;
115
118 return true;
119 }
120 }
121
122 /// \returns true if the specified action affects only Root entry
123 /// itself and does not affect it`s children.
125 switch (Action) {
126 default:
127 return false;
128
131 return true;
132 }
133 }
134
135 /// What a tree walk does, and for a walk that only records dependencies,
136 /// which root the dependencies it finds are recorded under. Only a
137 /// DW_TAG_subprogram re-anchors that root, so the distinction cannot be
138 /// recovered by comparing root entries: a walk of a subprogram subtree starts
139 /// out anchored to the subprogram itself.
140 enum class TreeWalkKindTy : uint8_t {
141 /// Mark the tree as kept and schedule the roots it references.
143
144 /// Do not mark. Record the dependencies as belonging to whichever root
145 /// references the walked subtree.
147
148 /// Do not mark. Record the dependencies as belonging to a subprogram inside
149 /// the walked subtree, which makes them the same for every referencing
150 /// root.
152 };
153
154 /// \returns true if the specified walk records dependencies instead of
155 /// marking the tree.
156 static bool recordsDepsOnly(TreeWalkKindTy Kind) {
157 return Kind != TreeWalkKindTy::MarkTree;
158 }
159
160 /// Class keeping live worklist item data.
162 public:
166 UnitEntryPairTy RootEntry) {
167 RootCU.setInt(Action);
168 RootCU.setPointer(RootEntry.CU);
169
170 RootDieEntry = RootEntry.DieEntry;
171 }
174 UnitEntryPairTy ReferencedBy,
176 RootCU.setPointer(RootEntry.CU);
177 RootCU.setInt(Action);
178 RootDieEntry = RootEntry.DieEntry;
179
180 ReferencedByCU = ReferencedBy.CU;
181 ReferencedByDieEntry = ReferencedBy.DieEntry;
182
184 }
185
187 return UnitEntryPairTy{RootCU.getPointer(), RootDieEntry};
188 }
189
191 return static_cast<CompileUnit::DieOutputPlacement>(RootCU.getInt());
192 }
193
194 bool hasReferencedByOtherEntry() const { return ReferencedByCU != nullptr; }
195
201
202 /// \returns the DIE actually referenced by ReferencedByDieEntry, whose
203 /// placement (rather than the enclosing RootDieEntry's) determines whether
204 /// ReferencedByDieEntry may remain in the type table. Null when the
205 /// referenced DIE is RootDieEntry itself, in which case RootDieEntry's
206 /// placement is used instead.
210
212 return static_cast<LiveRootWorklistActionTy>(RootCU.getInt());
213 }
214
215 protected:
216 /// Root entry.
217 /// ASSUMPTION: 3 bits are used to store LiveRootWorklistActionTy value.
218 /// Thus LiveRootWorklistActionTy should have no more eight elements.
219
220 /// Pointer traits for CompileUnit.
222 static inline void *getAsVoidPointer(CompileUnit *P) { return P; }
223 static inline CompileUnit *getFromVoidPointer(void *P) {
224 return (CompileUnit *)P;
225 }
226 static constexpr int NumLowBitsAvailable = 3;
227 static_assert(
228 alignof(CompileUnit) >= (1 << NumLowBitsAvailable),
229 "CompileUnit insufficiently aligned to have enough low bits.");
230 };
231
236
237 /// Another root entry which references this RootDieEntry.
238 /// ReferencedByDieEntry is kept to update placement.
239 /// if RootDieEntry has placement incompatible with placement
240 /// of ReferencedByDieEntry then it should be updated.
243
244 /// The DIE actually referenced by ReferencedByDieEntry. It lives in the
245 /// same CU as RootDieEntry, but its placement can differ: RootDieEntry is
246 /// the enclosing root that is marked as kept, whereas this DIE may be a
247 /// nested type demoted independently. That placement, not RootDieEntry's,
248 /// determines whether ReferencedByDieEntry may remain in the type table.
249 /// Null when RootDieEntry is the referenced DIE itself.
251 };
252
254
255 /// A completeness dependency of a subtree that belongs to whichever root
256 /// references the subtree, which is not known while the subtree is walked.
262
264
265 /// A subtree paired with the action it is walked with, which selects both the
266 /// visited children and the action recorded for a reference.
268 std::tuple<CompileUnit *, const DWARFDebugInfoEntry *,
270
271 /// A root referencing an already-marked subtree, standing in for all of that
272 /// subtree's dependencies. The subtree is walked when completeness is
273 /// checked, once per subtree rather than once per referencing root, which is
274 /// what keeps recording linear in the number of shared subtrees.
275 ///
276 /// Deferring the walk out of marking also keeps it off the state marking is
277 /// still mutating. A walk that only records dependencies reads a DIE's ODR
278 /// availability and whether it has an address, both settled before marking
279 /// begins, and never the keep and placement bits that sibling units raise as
280 /// they mark. Walking during marking would consult those bits through
281 /// isAlreadyMarked and yield a result that depends on how the units
282 /// interleave.
288
289 /// This function navigates DIEs tree starting from specified \p Entry.
290 /// It puts found 'root DIE' into the worklist. The \p CollectLiveEntries
291 /// instructs to collect either live roots(like subprograms having live
292 /// DW_AT_low_pc) or otherwise roots which is not live(they need to be
293 /// collected if they are imported f.e. by DW_TAG_imported_module).
294 void collectRootsToKeep(const UnitEntryPairTy &Entry,
295 std::optional<UnitEntryPairTy> ReferencedBy,
296 bool IsLiveParent);
297
298 /// Returns true if specified variable references live code section.
299 static bool isLiveVariableEntry(const UnitEntryPairTy &Entry,
300 bool IsLiveParent);
301
302 /// Returns true if specified subprogram references live code section.
303 static bool isLiveSubprogramEntry(const UnitEntryPairTy &Entry);
304
305 /// Examine worklist and mark all 'root DIE's as kept and set "Placement"
306 /// property.
307 bool markCollectedLiveRootsAsKept(bool InterCUProcessingStarted,
308 std::atomic<bool> &HasNewInterconnectedCUs);
309
310 /// Mark whole DIE tree as kept recursively. A walk that only records
311 /// dependencies (see \p Kind) does not mark the tree. Instead its
312 /// completeness dependencies are collected (see maybeAddReferencedRoots) so
313 /// they can be applied to every root referencing the tree.
314 /// \see materializeSubtreeSummaries.
316 const UnitEntryPairTy &RootEntry,
317 const UnitEntryPairTy &Entry,
318 bool InterCUProcessingStarted,
319 std::atomic<bool> &HasNewInterconnectedCUs,
321
322 /// Record that \p RootEntry references the already-marked subtree \p Entry,
323 /// and therefore carries the completeness dependencies of that subtree. The
324 /// subtree itself is walked later, by materializeSubtreeSummaries().
326 const UnitEntryPairTy &RootEntry,
327 const UnitEntryPairTy &Entry);
328
329 /// Walk every subtree that a recorded reference stands for, once per subtree
330 /// and action, and summarize the dependencies it contributes. Called when
331 /// completeness is checked, so that liveness marking and inter-unit reference
332 /// resolution have settled and the summary no longer depends on the order the
333 /// units were processed in.
335
336 /// Apply each summarized subtree's dependencies to every root recorded as
337 /// referencing it.
338 /// \returns true if any placement was updated.
340
341 /// Demote \p ReferencedBy to plain DWARF if it may not stay in the type table
342 /// while the DIE it references through \p Root is not placed there.
343 /// \returns true if the placement was updated.
344 bool demoteIfIncomplete(const UnitEntryPairTy &Root,
345 const DWARFDebugInfoEntry *ReferencedTypeDieEntry,
346 const UnitEntryPairTy &ReferencedBy);
347
348 /// Mark parents as keeping children.
350
351 /// Keep \p Child if it is a variable that is kept with its parent, which the
352 /// walk in progress keeps for \p RootEntry.
353 void keepWithParent(const UnitEntryPairTy &RootEntry,
354 const UnitEntryPairTy &Child, TreeWalkKindTy Kind);
355
356 /// Mark whole DIE tree as placed in "PlainDwarf".
358
359 /// Check referenced DIEs and add them into the worklist. A walk that only
360 /// records dependencies (see \p Kind) schedules nothing, so it triggers no
361 /// reference-following recursion. Each dependency it finds is instead
362 /// collected for the root that carries it, which is either whichever root
363 /// references the walked subtree or a subprogram nested inside it. This is
364 /// used when \p Entry was already marked by a racing CU/root: the marking and
365 /// subtree are handled elsewhere, but the referencing root's dependencies
366 /// must still be recorded so the completeness fixpoint sees a complete,
367 /// order-independent dependency set.
369 const UnitEntryPairTy &RootEntry,
370 const UnitEntryPairTy &Entry,
371 bool InterCUProcessingStarted,
372 std::atomic<bool> &HasNewInterconnectedCUs,
374
375 /// \returns true if \p DIEEntry can possibly be put into the artificial type
376 /// unit.
378
379 /// \returns root for the specified \p Entry.
381
382 /// Add action item to the work list.
384 LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry,
385 std::optional<UnitEntryPairTy> ReferencedBy,
386 const DWARFDebugInfoEntry *ReferencedTypeDieEntry = nullptr);
387
389
390 /// List of entries which are 'root DIE's.
392
393 /// List of entries dependencies.
395
396 /// Dependency summaries of already-marked subtrees, keyed by subtree and
397 /// action. Filled once, when completeness is first checked.
399
400 /// Roots referencing an already-marked subtree.
402
403 /// Number of leading SubtreeDependencyRefs whose subtree is summarized.
405
406 /// Where the walk in progress collects the dependencies that belong to the
407 /// root referencing the walked subtree, or null when no such walk is in
408 /// progress. Scoped by materializeSubtreeSummaries().
410
411 /// Whether inter-unit references could be resolved during marking. Reused
412 /// when the recorded subtrees are walked, which happens outside of marking.
414};
415
416} // end of namespace parallel
417} // end of namespace dwarf_linker
418} // end of namespace llvm
419
420#endif // LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the DenseMap class.
#define P(N)
This file defines the PointerIntPair class.
This file defines the SmallVector class.
A pointer to another debug information entry.
Definition DIE.h:318
DWARFDebugInfoEntry - A DIE with only the minimum required data.
Utility class that carries the DWARF compile/type unit and the debug info entry in an object.
Definition DWARFDie.h:43
PointerIntPair - This class implements a pair of a pointer and small integer.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Stores all information related to a compile unit, be it in its original instance of the object file o...
DieOutputPlacement
Kinds of placement for the output die.
LiveRootWorklistItemTy(LiveRootWorklistActionTy Action, UnitEntryPairTy RootEntry, UnitEntryPairTy ReferencedBy, const DWARFDebugInfoEntry *ReferencedTypeDieEntry=nullptr)
LiveRootWorklistItemTy(LiveRootWorklistActionTy Action, UnitEntryPairTy RootEntry)
PointerIntPair< CompileUnit *, 3, LiveRootWorklistActionTy, CompileUnitPointerTraits > RootCU
const DWARFDebugInfoEntry * ReferencedTypeDieEntry
The DIE actually referenced by ReferencedByDieEntry.
CompileUnit * ReferencedByCU
Another root entry which references this RootDieEntry.
bool markDIEEntryAsKeptRec(LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry, bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs, TreeWalkKindTy Kind=TreeWalkKindTy::MarkTree)
Mark whole DIE tree as kept recursively.
void verifyKeepChain()
Recursively walk the DIE tree and check "keepness" and "placement" information.
RootEntriesListTy Dependencies
List of entries dependencies.
void markParentsAsKeepingChildren(const UnitEntryPairTy &Entry)
Mark parents as keeping children.
UnitEntryPairTy getRootForSpecifiedEntry(UnitEntryPairTy Entry)
static bool recordsDepsOnly(TreeWalkKindTy Kind)
bool demoteIfIncomplete(const UnitEntryPairTy &Root, const DWARFDebugInfoEntry *ReferencedTypeDieEntry, const UnitEntryPairTy &ReferencedBy)
Demote ReferencedBy to plain DWARF if it may not stay in the type table while the DIE it references t...
bool markCollectedLiveRootsAsKept(bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
Examine worklist and mark all 'root DIE's as kept and set "Placement" property.
bool InterCUProcessingWasStarted
Whether inter-unit references could be resolved during marking.
bool applySubtreeSummaries()
Apply each summarized subtree's dependencies to every root recorded as referencing it.
bool isLiveAction(LiveRootWorklistActionTy Action)
bool isChildrenAction(LiveRootWorklistActionTy Action)
void keepWithParent(const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Child, TreeWalkKindTy Kind)
Keep Child if it is a variable that is kept with its parent, which the walk in progress keeps for Roo...
TreeWalkKindTy
What a tree walk does, and for a walk that only records dependencies, which root the dependencies it ...
@ MarkTree
Mark the tree as kept and schedule the roots it references.
bool isTypeAction(LiveRootWorklistActionTy Action)
void addActionToRootEntriesWorkList(LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry, std::optional< UnitEntryPairTy > ReferencedBy, const DWARFDebugInfoEntry *ReferencedTypeDieEntry=nullptr)
Add action item to the work list.
DenseMap< SubtreeDependenciesKeyTy, SubtreeDependenciesTy > SubtreeSummaries
Dependency summaries of already-marked subtrees, keyed by subtree and action.
SubtreeDependenciesTy * CollectedSubtreeDeps
Where the walk in progress collects the dependencies that belong to the root referencing the walked s...
bool isTypeTableCandidate(const DWARFDebugInfoEntry *DIEEntry)
size_t MaterializedRefs
Number of leading SubtreeDependencyRefs whose subtree is summarized.
SmallVector< LiveRootWorklistItemTy > RootEntriesListTy
void setPlainDwarfPlacementRec(const UnitEntryPairTy &Entry)
Mark whole DIE tree as placed in "PlainDwarf".
RootEntriesListTy RootEntriesWorkList
List of entries which are 'root DIE's.
SmallVector< SubtreeDependencyTy > SubtreeDependenciesTy
static bool isLiveSubprogramEntry(const UnitEntryPairTy &Entry)
Returns true if specified subprogram references live code section.
std::tuple< CompileUnit *, const DWARFDebugInfoEntry *, LiveRootWorklistActionTy > SubtreeDependenciesKeyTy
A subtree paired with the action it is walked with, which selects both the visited children and the a...
void recordSubtreeDependencies(LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry)
Record that RootEntry references the already-marked subtree Entry, and therefore carries the complete...
bool resolveDependenciesAndMarkLiveness(bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
Recursively walk the DIE tree and look for DIEs to keep.
static bool isLiveVariableEntry(const UnitEntryPairTy &Entry, bool IsLiveParent)
Returns true if specified variable references live code section.
@ MarkTypeEntryRec
Mark current item and all its children as type entry.
@ MarkLiveChildrenRec
Mark all children of current item as live entry.
@ MarkLiveEntryRec
Mark current item and all its children as live entry.
@ MarkTypeChildrenRec
Mark all children of current item as type entry.
SmallVector< SubtreeDependencyRefTy > SubtreeDependencyRefs
Roots referencing an already-marked subtree.
void collectLiveRoots()
This function is the entry point of the DIE selection algorithm.
void collectRootsToKeep(const UnitEntryPairTy &Entry, std::optional< UnitEntryPairTy > ReferencedBy, bool IsLiveParent)
This function navigates DIEs tree starting from specified Entry.
bool maybeAddReferencedRoots(LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry, bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs, TreeWalkKindTy Kind=TreeWalkKindTy::MarkTree)
Check referenced DIEs and add them into the worklist.
bool updateDependenciesCompleteness()
Check if dependencies have incompatible placement.
void materializeSubtreeSummaries()
Walk every subtree that a recorded reference stands for, once per subtree and action,...
This is an optimization pass for GlobalISel generic memory operations.
A root referencing an already-marked subtree, standing in for all of that subtree's dependencies.
A completeness dependency of a subtree that belongs to whichever root references the subtree,...
This is a helper structure which keeps a debug info entry with it's containing compilation unit.