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/PointerIntPair.h"
14#include "llvm/ADT/SmallVector.h"
15
16namespace llvm {
17class DWARFDebugInfoEntry;
18class DWARFDie;
19
20namespace dwarf_linker {
21namespace parallel {
22
23/// This class discovers DIEs dependencies: marks "live" DIEs, marks DIE
24/// locations (whether DIE should be cloned as regular DIE or it should be put
25/// into the artificial type unit).
26class DependencyTracker {
27public:
28 DependencyTracker(CompileUnit &CU) : CU(CU) {}
29
30 /// Recursively walk the \p DIE tree and look for DIEs to keep. Store that
31 /// information in \p CU's DIEInfo.
32 ///
33 /// This function is the entry point of the DIE selection algorithm. It is
34 /// expected to walk the DIE tree and(through the mediation of
35 /// Context.File.Addresses) ask for relocation adjustment value on each
36 /// DIE that might be a 'root DIE'(f.e. subprograms, variables).
37 ///
38 /// Returns true if all dependencies are correctly discovered. Inter-CU
39 /// dependencies cannot be discovered if referenced CU is not analyzed yet.
40 /// If that is the case this method returns false.
41 bool resolveDependenciesAndMarkLiveness(
42 bool InterCUProcessingStarted,
43 std::atomic<bool> &HasNewInterconnectedCUs);
44
45 /// Check if dependencies have incompatible placement.
46 /// If that is the case modify placement to be compatible.
47 /// \returns true if any placement was updated, otherwise returns false.
48 /// This method should be called as a followup processing after
49 /// resolveDependenciesAndMarkLiveness().
50 bool updateDependenciesCompleteness();
51
52 /// Recursively walk the \p DIE tree and check "keepness" and "placement"
53 /// information. It is an error if parent node does not have "keep" flag,
54 /// while child has one. It is an error if parent node has "TypeTable"
55 /// placement while child has "PlainDwarf" placement. This function dump error
56 /// at stderr in that case.
57 void verifyKeepChain();
58
59protected:
60 enum class LiveRootWorklistActionTy : uint8_t {
61 /// Mark current item as live entry.
62 MarkSingleLiveEntry = 0,
63
64 /// Mark current item as type entry.
65 MarkSingleTypeEntry,
66
67 /// Mark current item and all its children as live entry.
68 MarkLiveEntryRec,
69
70 /// Mark current item and all its children as type entry.
71 MarkTypeEntryRec,
72
73 /// Mark all children of current item as live entry.
74 MarkLiveChildrenRec,
75
76 /// Mark all children of current item as type entry.
77 MarkTypeChildrenRec,
78 };
79
80 /// \returns true if the specified action is for the "PlainDwarf".
81 bool isLiveAction(LiveRootWorklistActionTy Action) {
82 switch (Action) {
83 default:
84 return false;
85
86 case LiveRootWorklistActionTy::MarkSingleLiveEntry:
87 case LiveRootWorklistActionTy::MarkLiveEntryRec:
88 case LiveRootWorklistActionTy::MarkLiveChildrenRec:
89 return true;
90 }
91 }
92
93 /// \returns true if the specified action is for the "TypeTable".
94 bool isTypeAction(LiveRootWorklistActionTy Action) {
95 switch (Action) {
96 default:
97 return false;
98
99 case LiveRootWorklistActionTy::MarkSingleTypeEntry:
100 case LiveRootWorklistActionTy::MarkTypeEntryRec:
101 case LiveRootWorklistActionTy::MarkTypeChildrenRec:
102 return true;
103 }
104 }
105
106 /// \returns true if the specified action affects only Root entry
107 /// itself and does not affect it`s children.
108 bool isSingleAction(LiveRootWorklistActionTy Action) {
109 switch (Action) {
110 default:
111 return false;
112
113 case LiveRootWorklistActionTy::MarkSingleLiveEntry:
114 case LiveRootWorklistActionTy::MarkSingleTypeEntry:
115 return true;
116 }
117 }
118
119 /// \returns true if the specified action affects only Root entry
120 /// itself and does not affect it`s children.
121 bool isChildrenAction(LiveRootWorklistActionTy Action) {
122 switch (Action) {
123 default:
124 return false;
125
126 case LiveRootWorklistActionTy::MarkLiveChildrenRec:
127 case LiveRootWorklistActionTy::MarkTypeChildrenRec:
128 return true;
129 }
130 }
131
132 /// Class keeping live worklist item data.
133 class LiveRootWorklistItemTy {
134 public:
135 LiveRootWorklistItemTy() = default;
136 LiveRootWorklistItemTy(const LiveRootWorklistItemTy &) = default;
137 LiveRootWorklistItemTy(LiveRootWorklistActionTy Action,
138 UnitEntryPairTy RootEntry) {
139 RootCU.setInt(Action);
140 RootCU.setPointer(RootEntry.CU);
141
142 RootDieEntry = RootEntry.DieEntry;
143 }
144 LiveRootWorklistItemTy(
145 LiveRootWorklistActionTy Action, UnitEntryPairTy RootEntry,
146 UnitEntryPairTy ReferencedBy,
147 const DWARFDebugInfoEntry *ReferencedTypeDieEntry = nullptr) {
148 RootCU.setPointer(RootEntry.CU);
149 RootCU.setInt(Action);
150 RootDieEntry = RootEntry.DieEntry;
151
152 ReferencedByCU = ReferencedBy.CU;
153 ReferencedByDieEntry = ReferencedBy.DieEntry;
154
155 this->ReferencedTypeDieEntry = ReferencedTypeDieEntry;
156 }
157
158 UnitEntryPairTy getRootEntry() const {
159 return UnitEntryPairTy{RootCU.getPointer(), RootDieEntry};
160 }
161
162 CompileUnit::DieOutputPlacement getPlacement() const {
163 return static_cast<CompileUnit::DieOutputPlacement>(RootCU.getInt());
164 }
165
166 bool hasReferencedByOtherEntry() const { return ReferencedByCU != nullptr; }
167
168 UnitEntryPairTy getReferencedByEntry() const {
169 assert(ReferencedByCU);
170 assert(ReferencedByDieEntry);
171 return UnitEntryPairTy{ReferencedByCU, ReferencedByDieEntry};
172 }
173
174 /// \returns the DIE actually referenced by ReferencedByDieEntry, whose
175 /// placement (rather than the enclosing RootDieEntry's) determines whether
176 /// ReferencedByDieEntry may remain in the type table. Null when the
177 /// referenced DIE is RootDieEntry itself, in which case RootDieEntry's
178 /// placement is used instead.
179 const DWARFDebugInfoEntry *getReferencedTypeDieEntry() const {
180 return ReferencedTypeDieEntry;
181 }
182
183 LiveRootWorklistActionTy getAction() const {
184 return static_cast<LiveRootWorklistActionTy>(RootCU.getInt());
185 }
186
187 protected:
188 /// Root entry.
189 /// ASSUMPTION: 3 bits are used to store LiveRootWorklistActionTy value.
190 /// Thus LiveRootWorklistActionTy should have no more eight elements.
191
192 /// Pointer traits for CompileUnit.
193 struct CompileUnitPointerTraits {
194 static inline void *getAsVoidPointer(CompileUnit *P) { return P; }
195 static inline CompileUnit *getFromVoidPointer(void *P) {
196 return (CompileUnit *)P;
197 }
198 static constexpr int NumLowBitsAvailable = 3;
199 static_assert(
200 alignof(CompileUnit) >= (1 << NumLowBitsAvailable),
201 "CompileUnit insufficiently aligned to have enough low bits.");
202 };
203
204 PointerIntPair<CompileUnit *, 3, LiveRootWorklistActionTy,
205 CompileUnitPointerTraits>
206 RootCU;
207 const DWARFDebugInfoEntry *RootDieEntry = nullptr;
208
209 /// Another root entry which references this RootDieEntry.
210 /// ReferencedByDieEntry is kept to update placement.
211 /// if RootDieEntry has placement incompatible with placement
212 /// of ReferencedByDieEntry then it should be updated.
213 CompileUnit *ReferencedByCU = nullptr;
214 const DWARFDebugInfoEntry *ReferencedByDieEntry = nullptr;
215
216 /// The DIE actually referenced by ReferencedByDieEntry. It lives in the
217 /// same CU as RootDieEntry, but its placement can differ: RootDieEntry is
218 /// the enclosing root that is marked as kept, whereas this DIE may be a
219 /// nested type demoted independently. That placement, not RootDieEntry's,
220 /// determines whether ReferencedByDieEntry may remain in the type table.
221 /// Null when RootDieEntry is the referenced DIE itself.
222 const DWARFDebugInfoEntry *ReferencedTypeDieEntry = nullptr;
223 };
224
225 using RootEntriesListTy = SmallVector<LiveRootWorklistItemTy>;
226
227 /// This function navigates DIEs tree starting from specified \p Entry.
228 /// It puts found 'root DIE' into the worklist. The \p CollectLiveEntries
229 /// instructs to collect either live roots(like subprograms having live
230 /// DW_AT_low_pc) or otherwise roots which is not live(they need to be
231 /// collected if they are imported f.e. by DW_TAG_imported_module).
232 void collectRootsToKeep(const UnitEntryPairTy &Entry,
233 std::optional<UnitEntryPairTy> ReferencedBy,
234 bool IsLiveParent);
235
236 /// Returns true if specified variable references live code section.
237 static bool isLiveVariableEntry(const UnitEntryPairTy &Entry,
238 bool IsLiveParent);
239
240 /// Returns true if specified subprogram references live code section.
241 static bool isLiveSubprogramEntry(const UnitEntryPairTy &Entry);
242
243 /// Examine worklist and mark all 'root DIE's as kept and set "Placement"
244 /// property.
245 bool markCollectedLiveRootsAsKept(bool InterCUProcessingStarted,
246 std::atomic<bool> &HasNewInterconnectedCUs);
247
248 /// Mark whole DIE tree as kept recursively. When \p RecordDepsOnly is set the
249 /// tree is not marked. Instead its completeness dependencies are recorded
250 /// (see maybeAddReferencedRoots). This is used to re-walk an already-marked
251 /// subtree so a racing referencing root still contributes its dependencies.
252 bool markDIEEntryAsKeptRec(LiveRootWorklistActionTy Action,
253 const UnitEntryPairTy &RootEntry,
254 const UnitEntryPairTy &Entry,
255 bool InterCUProcessingStarted,
256 std::atomic<bool> &HasNewInterconnectedCUs,
257 bool RecordDepsOnly = false);
258
259 /// Mark parents as keeping children.
260 void markParentsAsKeepingChildren(const UnitEntryPairTy &Entry);
261
262 /// Mark whole DIE tree as placed in "PlainDwarf".
263 void setPlainDwarfPlacementRec(const UnitEntryPairTy &Entry);
264
265 /// Check referenced DIEs and add them into the worklist. When \p
266 /// RecordDepsOnly is set, the referenced roots are not scheduled for marking
267 /// (no new worklist items, hence no reference-following recursion). Instead
268 /// each completeness dependency is appended directly to \c Dependencies. This
269 /// is used when \p Entry was already marked by a racing CU/root: the marking
270 /// and subtree are handled elsewhere, but this referencing root's
271 /// dependencies must still be recorded so the completeness fixpoint sees a
272 /// complete, order-independent dependency set.
273 bool maybeAddReferencedRoots(LiveRootWorklistActionTy Action,
274 const UnitEntryPairTy &RootEntry,
275 const UnitEntryPairTy &Entry,
276 bool InterCUProcessingStarted,
277 std::atomic<bool> &HasNewInterconnectedCUs,
278 bool RecordDepsOnly = false);
279
280 /// \returns true if \p DIEEntry can possibly be put into the artificial type
281 /// unit.
282 bool isTypeTableCandidate(const DWARFDebugInfoEntry *DIEEntry);
283
284 /// \returns root for the specified \p Entry.
285 UnitEntryPairTy getRootForSpecifiedEntry(UnitEntryPairTy Entry);
286
287 /// Add action item to the work list.
288 void addActionToRootEntriesWorkList(
289 LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry,
290 std::optional<UnitEntryPairTy> ReferencedBy,
291 const DWARFDebugInfoEntry *ReferencedTypeDieEntry = nullptr);
292
293 CompileUnit &CU;
294
295 /// List of entries which are 'root DIE's.
296 RootEntriesListTy RootEntriesWorkList;
297
298 /// List of entries dependencies.
299 RootEntriesListTy Dependencies;
300};
301
302} // end of namespace parallel
303} // end of namespace dwarf_linker
304} // end of namespace llvm
305
306#endif // LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H
307