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
12#include "DWARFLinkerCompileUnit.h"
13#include "llvm/ADT/DenseMap.h"
14#include "llvm/ADT/PointerIntPair.h"
15#include "llvm/ADT/SmallVector.h"
16
17namespace llvm {
18class DWARFDebugInfoEntry;
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).
27class DependencyTracker {
28public:
29 DependencyTracker(CompileUnit &CU) : CU(CU) {}
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.
44 bool resolveDependenciesAndMarkLiveness(
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().
53 bool updateDependenciesCompleteness();
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:
63 enum class LiveRootWorklistActionTy : uint8_t {
64 /// Mark current item as live entry.
65 MarkSingleLiveEntry = 0,
66
67 /// Mark current item as type entry.
68 MarkSingleTypeEntry,
69
70 /// Mark current item and all its children as live entry.
71 MarkLiveEntryRec,
72
73 /// Mark current item and all its children as type entry.
74 MarkTypeEntryRec,
75
76 /// Mark all children of current item as live entry.
77 MarkLiveChildrenRec,
78
79 /// Mark all children of current item as type entry.
80 MarkTypeChildrenRec,
81 };
82
83 /// \returns true if the specified action is for the "PlainDwarf".
84 bool isLiveAction(LiveRootWorklistActionTy Action) {
85 switch (Action) {
86 default:
87 return false;
88
89 case LiveRootWorklistActionTy::MarkSingleLiveEntry:
90 case LiveRootWorklistActionTy::MarkLiveEntryRec:
91 case LiveRootWorklistActionTy::MarkLiveChildrenRec:
92 return true;
93 }
94 }
95
96 /// \returns true if the specified action is for the "TypeTable".
97 bool isTypeAction(LiveRootWorklistActionTy Action) {
98 switch (Action) {
99 default:
100 return false;
101
102 case LiveRootWorklistActionTy::MarkSingleTypeEntry:
103 case LiveRootWorklistActionTy::MarkTypeEntryRec:
104 case LiveRootWorklistActionTy::MarkTypeChildrenRec:
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
116 case LiveRootWorklistActionTy::MarkSingleLiveEntry:
117 case LiveRootWorklistActionTy::MarkSingleTypeEntry:
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.
124 bool isChildrenAction(LiveRootWorklistActionTy Action) {
125 switch (Action) {
126 default:
127 return false;
128
129 case LiveRootWorklistActionTy::MarkLiveChildrenRec:
130 case LiveRootWorklistActionTy::MarkTypeChildrenRec:
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.
142 MarkTree,
143
144 /// Do not mark. Record the dependencies as belonging to whichever root
145 /// references the walked subtree.
146 RecordSubtreeDeps,
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.
151 RecordNestedSubprogramDeps,
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.
161 class LiveRootWorklistItemTy {
162 public:
163 LiveRootWorklistItemTy() = default;
164 LiveRootWorklistItemTy(const LiveRootWorklistItemTy &) = default;
165 LiveRootWorklistItemTy(LiveRootWorklistActionTy Action,
166 UnitEntryPairTy RootEntry) {
167 RootCU.setInt(Action);
168 RootCU.setPointer(RootEntry.CU);
169
170 RootDieEntry = RootEntry.DieEntry;
171 }
172 LiveRootWorklistItemTy(
173 LiveRootWorklistActionTy Action, UnitEntryPairTy RootEntry,
174 UnitEntryPairTy ReferencedBy,
175 const DWARFDebugInfoEntry *ReferencedTypeDieEntry = nullptr) {
176 RootCU.setPointer(RootEntry.CU);
177 RootCU.setInt(Action);
178 RootDieEntry = RootEntry.DieEntry;
179
180 ReferencedByCU = ReferencedBy.CU;
181 ReferencedByDieEntry = ReferencedBy.DieEntry;
182
183 this->ReferencedTypeDieEntry = ReferencedTypeDieEntry;
184 }
185
186 UnitEntryPairTy getRootEntry() const {
187 return UnitEntryPairTy{RootCU.getPointer(), RootDieEntry};
188 }
189
190 CompileUnit::DieOutputPlacement getPlacement() const {
191 return static_cast<CompileUnit::DieOutputPlacement>(RootCU.getInt());
192 }
193
194 bool hasReferencedByOtherEntry() const { return ReferencedByCU != nullptr; }
195
196 UnitEntryPairTy getReferencedByEntry() const {
197 assert(ReferencedByCU);
198 assert(ReferencedByDieEntry);
199 return UnitEntryPairTy{ReferencedByCU, ReferencedByDieEntry};
200 }
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.
207 const DWARFDebugInfoEntry *getReferencedTypeDieEntry() const {
208 return ReferencedTypeDieEntry;
209 }
210
211 LiveRootWorklistActionTy getAction() const {
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.
221 struct CompileUnitPointerTraits {
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
232 PointerIntPair<CompileUnit *, 3, LiveRootWorklistActionTy,
233 CompileUnitPointerTraits>
234 RootCU;
235 const DWARFDebugInfoEntry *RootDieEntry = nullptr;
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.
241 CompileUnit *ReferencedByCU = nullptr;
242 const DWARFDebugInfoEntry *ReferencedByDieEntry = nullptr;
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.
250 const DWARFDebugInfoEntry *ReferencedTypeDieEntry = nullptr;
251 };
252
253 using RootEntriesListTy = SmallVector<LiveRootWorklistItemTy>;
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.
257 struct SubtreeDependencyTy {
258 LiveRootWorklistActionTy Action;
259 UnitEntryPairTy Root;
260 const DWARFDebugInfoEntry *ReferencedTypeDieEntry;
261 };
262
263 using SubtreeDependenciesTy = SmallVector<SubtreeDependencyTy>;
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.
267 using SubtreeDependenciesKeyTy =
268 std::tuple<CompileUnit *, const DWARFDebugInfoEntry *,
269 LiveRootWorklistActionTy>;
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.
283 struct SubtreeDependencyRefTy {
284 UnitEntryPairTy Subtree;
285 LiveRootWorklistActionTy Action;
286 UnitEntryPairTy ReferencedBy;
287 };
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.
315 bool markDIEEntryAsKeptRec(LiveRootWorklistActionTy Action,
316 const UnitEntryPairTy &RootEntry,
317 const UnitEntryPairTy &Entry,
318 bool InterCUProcessingStarted,
319 std::atomic<bool> &HasNewInterconnectedCUs,
320 TreeWalkKindTy Kind = TreeWalkKindTy::MarkTree);
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().
325 void recordSubtreeDependencies(LiveRootWorklistActionTy Action,
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.
334 void materializeSubtreeSummaries();
335
336 /// Apply each summarized subtree's dependencies to every root recorded as
337 /// referencing it.
338 /// \returns true if any placement was updated.
339 bool applySubtreeSummaries();
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.
349 void markParentsAsKeepingChildren(const UnitEntryPairTy &Entry);
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".
357 void setPlainDwarfPlacementRec(const UnitEntryPairTy &Entry);
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.
368 bool maybeAddReferencedRoots(LiveRootWorklistActionTy Action,
369 const UnitEntryPairTy &RootEntry,
370 const UnitEntryPairTy &Entry,
371 bool InterCUProcessingStarted,
372 std::atomic<bool> &HasNewInterconnectedCUs,
373 TreeWalkKindTy Kind = TreeWalkKindTy::MarkTree);
374
375 /// \returns true if \p DIEEntry can possibly be put into the artificial type
376 /// unit.
377 bool isTypeTableCandidate(const DWARFDebugInfoEntry *DIEEntry);
378
379 /// \returns root for the specified \p Entry.
380 UnitEntryPairTy getRootForSpecifiedEntry(UnitEntryPairTy Entry);
381
382 /// Add action item to the work list.
383 void addActionToRootEntriesWorkList(
384 LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry,
385 std::optional<UnitEntryPairTy> ReferencedBy,
386 const DWARFDebugInfoEntry *ReferencedTypeDieEntry = nullptr);
387
388 CompileUnit &CU;
389
390 /// List of entries which are 'root DIE's.
391 RootEntriesListTy RootEntriesWorkList;
392
393 /// List of entries dependencies.
394 RootEntriesListTy Dependencies;
395
396 /// Dependency summaries of already-marked subtrees, keyed by subtree and
397 /// action. Filled once, when completeness is first checked.
398 DenseMap<SubtreeDependenciesKeyTy, SubtreeDependenciesTy> SubtreeSummaries;
399
400 /// Roots referencing an already-marked subtree.
401 SmallVector<SubtreeDependencyRefTy> SubtreeDependencyRefs;
402
403 /// Number of leading SubtreeDependencyRefs whose subtree is summarized.
404 size_t MaterializedRefs = 0;
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().
409 SubtreeDependenciesTy *CollectedSubtreeDeps = nullptr;
410
411 /// Whether inter-unit references could be resolved during marking. Reused
412 /// when the recorded subtrees are walked, which happens outside of marking.
413 bool InterCUProcessingWasStarted = false;
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
421