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