1//=== DependencyTracker.cpp -----------------------------------------------===//
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#include "DependencyTracker.h"
10#include "llvm/Support/FormatVariadic.h"
11
12using namespace llvm;
13using namespace dwarf_linker;
14using namespace dwarf_linker::parallel;
15
16/// A broken link in the keep chain. By recording both the parent and the child
17/// we can show only broken links for DIEs with multiple children.
18struct BrokenLink {
19 BrokenLink(DWARFDie Parent, DWARFDie Child, const char *Message)
20 : Parent(Parent), Child(Child), Message(Message) {}
21 DWARFDie Parent;
22 DWARFDie Child;
23 std::string Message;
24};
25
26/// Verify the keep chain by looking for DIEs that are kept but who's parent
27/// isn't.
28void DependencyTracker::verifyKeepChain() {
29#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
30 SmallVector<DWARFDie> Worklist;
31 Worklist.push_back(CU.getOrigUnit().getUnitDIE());
32
33 // List of broken links.
34 SmallVector<BrokenLink> BrokenLinks;
35
36 while (!Worklist.empty()) {
37 const DWARFDie Current = Worklist.back();
38 Worklist.pop_back();
39
40 if (!Current.isValid())
41 continue;
42
43 CompileUnit::DIEInfo &CurrentInfo =
44 CU.getDIEInfo(Current.getDebugInfoEntry());
45 const bool ParentPlainDieIsKept = CurrentInfo.needToKeepInPlainDwarf();
46 const bool ParentTypeDieIsKept = CurrentInfo.needToPlaceInTypeTable();
47
48 for (DWARFDie Child : reverse(Current.children())) {
49 Worklist.push_back(Child);
50
51 CompileUnit::DIEInfo &ChildInfo =
52 CU.getDIEInfo(Child.getDebugInfoEntry());
53 const bool ChildPlainDieIsKept = ChildInfo.needToKeepInPlainDwarf();
54 const bool ChildTypeDieIsKept = ChildInfo.needToPlaceInTypeTable();
55
56 if (!ParentPlainDieIsKept && ChildPlainDieIsKept)
57 BrokenLinks.emplace_back(Current, Child,
58 "Found invalid link in keep chain");
59
60 if (Child.getTag() == dwarf::DW_TAG_subprogram) {
61 if (!ChildInfo.getKeep() && isLiveSubprogramEntry(UnitEntryPairTy(
62 &CU, Child.getDebugInfoEntry()))) {
63 BrokenLinks.emplace_back(Current, Child,
64 "Live subprogram is not marked as kept");
65 }
66 }
67
68 if (!ChildInfo.getODRAvailable()) {
69 assert(!ChildTypeDieIsKept);
70 continue;
71 }
72
73 if (!ParentTypeDieIsKept && ChildTypeDieIsKept)
74 BrokenLinks.emplace_back(Current, Child,
75 "Found invalid link in keep chain");
76
77 if (CurrentInfo.getIsInAnonNamespaceScope() &&
78 ChildInfo.needToPlaceInTypeTable()) {
79 BrokenLinks.emplace_back(Current, Child,
80 "Found invalid placement marking for member "
81 "of anonymous namespace");
82 }
83 }
84 }
85
86 if (!BrokenLinks.empty()) {
87 for (BrokenLink Link : BrokenLinks) {
88 errs() << "\n=================================\n";
89 WithColor::error() << formatv("{0} between {1:x} and {2:x}", Link.Message,
90 Link.Parent.getOffset(),
91 Link.Child.getOffset());
92
93 errs() << "\nParent:";
94 Link.Parent.dump(errs(), 0, {});
95 errs() << "\n";
96 CU.getDIEInfo(Link.Parent).dump();
97
98 errs() << "\nChild:";
99 Link.Child.dump(errs(), 2, {});
100 errs() << "\n";
101 CU.getDIEInfo(Link.Child).dump();
102 }
103 report_fatal_error("invalid keep chain");
104 }
105#endif
106}
107
108bool DependencyTracker::resolveDependenciesAndMarkLiveness(
109 bool InterCUProcessingStarted, std::atomic<bool> &HasNewInterconnectedCUs) {
110 RootEntriesWorkList.clear();
111
112 // Search for live root DIEs.
113 CompileUnit::DIEInfo &CUInfo = CU.getDIEInfo(Entry: CU.getDebugInfoEntry(Index: 0));
114 CUInfo.setPlacement(CompileUnit::PlainDwarf);
115 collectRootsToKeep(Entry: UnitEntryPairTy{&CU, CU.getDebugInfoEntry(Index: 0)},
116 ReferencedBy: std::nullopt, IsLiveParent: false);
117
118 // Mark live DIEs as kept.
119 return markCollectedLiveRootsAsKept(InterCUProcessingStarted,
120 HasNewInterconnectedCUs);
121}
122
123void DependencyTracker::addActionToRootEntriesWorkList(
124 LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry,
125 std::optional<UnitEntryPairTy> ReferencedBy,
126 const DWARFDebugInfoEntry *ReferencedTypeDieEntry) {
127 if (ReferencedBy) {
128 RootEntriesWorkList.emplace_back(Args&: Action, Args: Entry, Args&: *ReferencedBy,
129 Args&: ReferencedTypeDieEntry);
130 return;
131 }
132
133 RootEntriesWorkList.emplace_back(Args&: Action, Args: Entry);
134}
135
136void DependencyTracker::collectRootsToKeep(
137 const UnitEntryPairTy &Entry, std::optional<UnitEntryPairTy> ReferencedBy,
138 bool IsLiveParent) {
139 for (const DWARFDebugInfoEntry *CurChild =
140 Entry.CU->getFirstChildEntry(Die: Entry.DieEntry);
141 CurChild && CurChild->getAbbreviationDeclarationPtr();
142 CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) {
143 UnitEntryPairTy ChildEntry(Entry.CU, CurChild);
144 CompileUnit::DIEInfo &ChildInfo = Entry.CU->getDIEInfo(Entry: CurChild);
145
146 bool IsLiveChild = false;
147
148 switch (CurChild->getTag()) {
149 case dwarf::DW_TAG_label: {
150 IsLiveChild = isLiveSubprogramEntry(Entry: ChildEntry);
151
152 // Keep label referencing live address.
153 // Keep label which is child of live parent entry.
154 if (IsLiveChild || (IsLiveParent && ChildInfo.getHasAnAddress())) {
155 addActionToRootEntriesWorkList(
156 Action: LiveRootWorklistActionTy::MarkLiveEntryRec, Entry: ChildEntry,
157 ReferencedBy);
158 }
159 } break;
160 case dwarf::DW_TAG_subprogram: {
161 IsLiveChild = isLiveSubprogramEntry(Entry: ChildEntry);
162
163 // Keep subprogram referencing live address.
164 if (IsLiveChild) {
165 // If subprogram is in module scope and this module allows ODR
166 // deduplication set "TypeTable" placement, otherwise set "" placement
167 LiveRootWorklistActionTy Action =
168 (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable())
169 ? LiveRootWorklistActionTy::MarkTypeEntryRec
170 : LiveRootWorklistActionTy::MarkLiveEntryRec;
171
172 addActionToRootEntriesWorkList(Action, Entry: ChildEntry, ReferencedBy);
173 }
174 } break;
175 case dwarf::DW_TAG_constant:
176 case dwarf::DW_TAG_variable: {
177 IsLiveChild = isLiveVariableEntry(Entry: ChildEntry, IsLiveParent);
178
179 // Keep variable referencing live address.
180 if (IsLiveChild) {
181 // If variable is in module scope and this module allows ODR
182 // deduplication set "TypeTable" placement, otherwise set "" placement
183
184 LiveRootWorklistActionTy Action =
185 (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable())
186 ? LiveRootWorklistActionTy::MarkTypeEntryRec
187 : LiveRootWorklistActionTy::MarkLiveEntryRec;
188
189 addActionToRootEntriesWorkList(Action, Entry: ChildEntry, ReferencedBy);
190 }
191 } break;
192 case dwarf::DW_TAG_base_type: {
193 // Always keep base types.
194 addActionToRootEntriesWorkList(
195 Action: LiveRootWorklistActionTy::MarkSingleLiveEntry, Entry: ChildEntry,
196 ReferencedBy);
197 } break;
198 case dwarf::DW_TAG_imported_module:
199 case dwarf::DW_TAG_imported_declaration:
200 case dwarf::DW_TAG_imported_unit: {
201 // Always keep DIEs having DW_AT_import attribute.
202 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_compile_unit) {
203 addActionToRootEntriesWorkList(
204 Action: LiveRootWorklistActionTy::MarkSingleLiveEntry, Entry: ChildEntry,
205 ReferencedBy);
206 break;
207 }
208
209 addActionToRootEntriesWorkList(
210 Action: LiveRootWorklistActionTy::MarkSingleTypeEntry, Entry: ChildEntry,
211 ReferencedBy);
212 } break;
213 case dwarf::DW_TAG_type_unit:
214 case dwarf::DW_TAG_partial_unit:
215 case dwarf::DW_TAG_compile_unit: {
216 llvm_unreachable("Called for incorrect DIE");
217 } break;
218 default:
219 // A forward-declared type nested in a DW_TAG_module is the module's
220 // record that the name exists, even when no full definition has been
221 // emitted. Route it through the type pool: when another CU emits a
222 // real definition for the same synthetic name, the existing
223 // decl-vs-def race resolution in allocateTypeDie + getFinalDie keeps
224 // the definition and drops this declaration at emission time. For
225 // non-ODR languages getFinalPlacementForEntry forces PlainDwarf,
226 // so the forward decl is kept in place under its module.
227 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_module &&
228 dwarf::isType(T: CurChild->getTag()) &&
229 dwarf::toUnsigned(V: Entry.CU->find(Die: CurChild, Attrs: dwarf::DW_AT_declaration),
230 Default: 0)) {
231 addActionToRootEntriesWorkList(
232 Action: LiveRootWorklistActionTy::MarkTypeEntryRec, Entry: ChildEntry,
233 ReferencedBy);
234 }
235 break;
236 }
237
238 collectRootsToKeep(Entry: ChildEntry, ReferencedBy, IsLiveParent: IsLiveChild || IsLiveParent);
239 }
240}
241
242bool DependencyTracker::markCollectedLiveRootsAsKept(
243 bool InterCUProcessingStarted, std::atomic<bool> &HasNewInterconnectedCUs) {
244 bool Res = true;
245
246 // Mark roots as kept.
247 while (!RootEntriesWorkList.empty()) {
248 LiveRootWorklistItemTy Root = RootEntriesWorkList.pop_back_val();
249
250 if (markDIEEntryAsKeptRec(Action: Root.getAction(), RootEntry: Root.getRootEntry(),
251 Entry: Root.getRootEntry(), InterCUProcessingStarted,
252 HasNewInterconnectedCUs)) {
253 if (Root.hasReferencedByOtherEntry())
254 Dependencies.push_back(Elt: Root);
255 } else
256 Res = false;
257 }
258
259 return Res;
260}
261
262bool DependencyTracker::updateDependenciesCompleteness() {
263 bool HasNewDependency = false;
264 for (LiveRootWorklistItemTy &Root : Dependencies) {
265 assert(Root.hasReferencedByOtherEntry() &&
266 "Root entry without dependency inside the dependencies list");
267
268 UnitEntryPairTy RootEntry = Root.getRootEntry();
269
270 // Completeness must be checked against the actual referenced DIE, not its
271 // enclosing root. A nested type can be demoted to plain DWARF while its
272 // root stays in the type table, and a type-table DIE may only reference
273 // DIEs that are themselves in the type table. Checking the root instead
274 // leaves such a DIE in the type table, later tripping the type-unit
275 // reference assertion in DIEAttributeCloner::cloneDieRefAttr.
276 const DWARFDebugInfoEntry *ReferencedDieEntry =
277 Root.getReferencedTypeDieEntry() ? Root.getReferencedTypeDieEntry()
278 : RootEntry.DieEntry;
279 CompileUnit::DIEInfo &RootInfo =
280 RootEntry.CU->getDIEInfo(Entry: ReferencedDieEntry);
281
282 UnitEntryPairTy ReferencedByEntry = Root.getReferencedByEntry();
283 CompileUnit::DIEInfo &ReferencedByInfo =
284 ReferencedByEntry.CU->getDIEInfo(Entry: ReferencedByEntry.DieEntry);
285
286 if (!RootInfo.needToPlaceInTypeTable() &&
287 ReferencedByInfo.needToPlaceInTypeTable()) {
288 HasNewDependency = true;
289 setPlainDwarfPlacementRec(ReferencedByEntry);
290
291 // FIXME: we probably need to update getKeepTypeChildren status for
292 // parents of *Root.ReferencedBy.
293 }
294 }
295
296 return HasNewDependency;
297}
298
299void DependencyTracker::setPlainDwarfPlacementRec(
300 const UnitEntryPairTy &Entry) {
301 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
302 if (Info.getPlacement() == CompileUnit::PlainDwarf &&
303 !Info.getKeepTypeChildren())
304 return;
305
306 Info.setPlacement(CompileUnit::PlainDwarf);
307 Info.unsetKeepTypeChildren();
308 markParentsAsKeepingChildren(Entry);
309
310 for (const DWARFDebugInfoEntry *CurChild =
311 Entry.CU->getFirstChildEntry(Die: Entry.DieEntry);
312 CurChild && CurChild->getAbbreviationDeclarationPtr();
313 CurChild = Entry.CU->getSiblingEntry(Die: CurChild))
314 setPlainDwarfPlacementRec(UnitEntryPairTy{Entry.CU, CurChild});
315}
316
317static bool isNamespaceLikeEntry(const DWARFDebugInfoEntry *Entry) {
318 switch (Entry->getTag()) {
319 case dwarf::DW_TAG_compile_unit:
320 case dwarf::DW_TAG_module:
321 case dwarf::DW_TAG_namespace:
322 return true;
323
324 default:
325 return false;
326 }
327}
328
329bool isAlreadyMarked(const CompileUnit::DIEInfo &Info,
330 CompileUnit::DieOutputPlacement NewPlacement) {
331 if (!Info.getKeep())
332 return false;
333
334 switch (NewPlacement) {
335 case CompileUnit::TypeTable:
336 return Info.needToPlaceInTypeTable();
337
338 case CompileUnit::PlainDwarf:
339 return Info.needToKeepInPlainDwarf();
340
341 case CompileUnit::Both:
342 return Info.needToPlaceInTypeTable() && Info.needToKeepInPlainDwarf();
343
344 case CompileUnit::NotSet:
345 llvm_unreachable("Unset placement type is specified.");
346 };
347
348 llvm_unreachable("Unknown CompileUnit::DieOutputPlacement enum");
349}
350
351bool isAlreadyMarked(const UnitEntryPairTy &Entry,
352 CompileUnit::DieOutputPlacement NewPlacement) {
353 return isAlreadyMarked(Info: Entry.CU->getDIEInfo(Entry: Entry.DieEntry), NewPlacement);
354}
355
356void DependencyTracker::markParentsAsKeepingChildren(
357 const UnitEntryPairTy &Entry) {
358 if (Entry.DieEntry->getAbbreviationDeclarationPtr() == nullptr)
359 return;
360
361 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
362 bool NeedKeepTypeChildren = Info.needToPlaceInTypeTable();
363 bool NeedKeepPlainChildren = Info.needToKeepInPlainDwarf();
364
365 bool AreTypeParentsDone = !NeedKeepTypeChildren;
366 bool ArePlainParentsDone = !NeedKeepPlainChildren;
367
368 // Mark parents as 'Keep*Children'.
369 std::optional<uint32_t> ParentIdx = Entry.DieEntry->getParentIdx();
370 while (ParentIdx) {
371 const DWARFDebugInfoEntry *ParentEntry =
372 Entry.CU->getDebugInfoEntry(Index: *ParentIdx);
373 CompileUnit::DIEInfo &ParentInfo = Entry.CU->getDIEInfo(Idx: *ParentIdx);
374
375 if (!AreTypeParentsDone && NeedKeepTypeChildren) {
376 if (ParentInfo.getKeepTypeChildren())
377 AreTypeParentsDone = true;
378 else {
379 bool AddToWorklist = !isAlreadyMarked(
380 Info: ParentInfo, NewPlacement: CompileUnit::DieOutputPlacement::TypeTable);
381 ParentInfo.setKeepTypeChildren();
382 if (AddToWorklist && !isNamespaceLikeEntry(Entry: ParentEntry)) {
383 addActionToRootEntriesWorkList(
384 Action: LiveRootWorklistActionTy::MarkTypeChildrenRec,
385 Entry: UnitEntryPairTy{Entry.CU, ParentEntry}, ReferencedBy: std::nullopt);
386 }
387 }
388 }
389
390 if (!ArePlainParentsDone && NeedKeepPlainChildren) {
391 if (ParentInfo.getKeepPlainChildren())
392 ArePlainParentsDone = true;
393 else {
394 bool AddToWorklist = !isAlreadyMarked(
395 Info: ParentInfo, NewPlacement: CompileUnit::DieOutputPlacement::PlainDwarf);
396 ParentInfo.setKeepPlainChildren();
397 if (AddToWorklist && !isNamespaceLikeEntry(Entry: ParentEntry)) {
398 addActionToRootEntriesWorkList(
399 Action: LiveRootWorklistActionTy::MarkLiveChildrenRec,
400 Entry: UnitEntryPairTy{Entry.CU, ParentEntry}, ReferencedBy: std::nullopt);
401 }
402 }
403 }
404
405 if (AreTypeParentsDone && ArePlainParentsDone)
406 break;
407
408 ParentIdx = ParentEntry->getParentIdx();
409 }
410}
411
412namespace {
413struct FinalPlacement {
414 CompileUnit::DieOutputPlacement Placement;
415
416 /// How Placement combines with the DIE's current placement when applied.
417 enum ApplyMode {
418 /// Overwrite the current placement. Used for entries whose placement is
419 /// fully determined regardless of how they were reached, so every mark
420 /// agrees on the value (ODR-unavailable entries and static data member
421 /// declarations).
422 Overwrite,
423 /// OR-join into the current placement (the common monotone-lattice case):
424 /// a DIE reached by both a live and a type mark ends up in Both.
425 Join,
426 /// Join for a DW_TAG_variable, which cannot occupy the type table and plain
427 /// DWARF at once: PlainDwarf is absorbing so the variable never lands in
428 /// Both.
429 JoinVariable,
430 } Mode;
431};
432} // namespace
433
434// Computes the placement to apply to \p Entry for a mark requesting \p
435// Placement (PlainDwarf for a live action, TypeTable for a type action), along
436// with how it combines with the DIE's current placement. Most entries join, so
437// a DIE reached by both actions ends up in Both. Entries whose placement is
438// fully determined regardless of how they were reached instead overwrite with
439// an exact placement: ODR-unavailable entries cannot be deduplicated into the
440// type table, and a DW_TAG_variable cannot occupy the type table and plain
441// DWARF at once.
442static FinalPlacement
443getFinalPlacementForEntry(const UnitEntryPairTy &Entry,
444 CompileUnit::DieOutputPlacement Placement) {
445 assert((Placement != CompileUnit::NotSet) && "Placement is not set");
446 CompileUnit::DIEInfo &EntryInfo = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
447
448 if (!EntryInfo.getODRAvailable())
449 return {.Placement: CompileUnit::PlainDwarf, .Mode: FinalPlacement::Overwrite};
450
451 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_variable) {
452 // In-class static member declarations (e.g. "static constexpr int x = 1;")
453 // are DW_TAG_variable children of a DW_TAG_class_type /
454 // DW_TAG_structure_type / DW_TAG_union_type with DW_AT_declaration set.
455 // They are part of the class type and belong in the TypeTable together with
456 // the class. Forcing them into PlainDwarf would also drag the parent class
457 // into PlainDwarf (via markParentsAsKeepingChildren), producing a duplicate
458 // empty class declaration DIE alongside the full class definition emitted
459 // in another CU.
460 bool IsDeclaration = dwarf::toUnsigned(
461 V: Entry.CU->find(Die: Entry.DieEntry, Attrs: dwarf::DW_AT_declaration), Default: 0);
462 bool ParentIsType = false;
463 if (IsDeclaration) {
464 if (std::optional<uint32_t> ParentIdx = Entry.DieEntry->getParentIdx()) {
465 dwarf::Tag ParentTag =
466 Entry.CU->getDebugInfoEntry(Index: *ParentIdx)->getTag();
467 ParentIsType = ParentTag == dwarf::DW_TAG_class_type ||
468 ParentTag == dwarf::DW_TAG_structure_type ||
469 ParentTag == dwarf::DW_TAG_union_type;
470 }
471 }
472 if (IsDeclaration && ParentIsType) {
473 // Pure declarations have no runtime address; they belong with the class
474 // type. Always place in TypeTable regardless of how they were reached.
475 return {.Placement: CompileUnit::TypeTable, .Mode: FinalPlacement::Overwrite};
476 }
477
478 // A live (PlainDwarf) mark pins the variable to plain DWARF.
479 if (Placement == CompileUnit::PlainDwarf || Placement == CompileUnit::Both)
480 return {.Placement: CompileUnit::PlainDwarf, .Mode: FinalPlacement::Overwrite};
481
482 // Only a type-table mark reaches here. The variable join keeps a PlainDwarf
483 // mark racing this one from turning the variable into Both.
484 return {.Placement: Placement, .Mode: FinalPlacement::JoinVariable};
485 }
486
487 return {.Placement: Placement, .Mode: FinalPlacement::Join};
488}
489
490bool DependencyTracker::markDIEEntryAsKeptRec(
491 LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry,
492 const UnitEntryPairTy &Entry, bool InterCUProcessingStarted,
493 std::atomic<bool> &HasNewInterconnectedCUs, bool RecordDepsOnly) {
494 if (Entry.DieEntry->getAbbreviationDeclarationPtr() == nullptr)
495 return true;
496
497 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
498
499 // Calculate final placement.
500 FinalPlacement Final = getFinalPlacementForEntry(
501 Entry,
502 Placement: isLiveAction(Action) ? CompileUnit::PlainDwarf : CompileUnit::TypeTable);
503 CompileUnit::DieOutputPlacement Placement = Final.Placement;
504 assert((Info.getODRAvailable() || isLiveAction(Action) ||
505 Placement == CompileUnit::PlainDwarf) &&
506 "Wrong kind of placement for ODR unavailable entry");
507
508 if (!RecordDepsOnly && !isChildrenAction(Action) &&
509 isAlreadyMarked(Entry, NewPlacement: Placement)) {
510 // Entry (and its subtree) were already marked, possibly by a racing CU or
511 // another referencing root, and which one wins is non-deterministic. Skip
512 // the redundant marking, but re-walk the subtree in record-deps-only mode
513 // so this referencing root still contributes its outgoing completeness
514 // dependencies. Otherwise the recorded dependency set depends on thread
515 // interleaving, the demotion fixpoint misses demotions, and whole type
516 // subtrees are left in the artificial type unit non-deterministically.
517 // Recording extra dependencies is harmless: a dependency only triggers a
518 // demotion when the referenced type is actually placed in plain DWARF.
519 return markDIEEntryAsKeptRec(Action, RootEntry, Entry,
520 InterCUProcessingStarted,
521 HasNewInterconnectedCUs,
522 /*RecordDepsOnly=*/true);
523 }
524
525 if (!RecordDepsOnly) {
526 // Mark current DIE as kept.
527 Info.setKeep();
528 // Marks compose monotonically so no interleaving loses an update: a general
529 // mark only raises the placement in the lattice, and a forced placement is
530 // a value every mark agrees on.
531 switch (Final.Mode) {
532 case FinalPlacement::Overwrite:
533 Info.setPlacement(Placement);
534 break;
535 case FinalPlacement::Join:
536 Info.joinPlacement(Placement);
537 break;
538 case FinalPlacement::JoinVariable:
539 Info.joinVariablePlacement(Placement);
540 break;
541 }
542
543 // Set keep children property for parents.
544 markParentsAsKeepingChildren(Entry);
545 }
546
547 UnitEntryPairTy FinalRootEntry =
548 Entry.DieEntry->getTag() == dwarf::DW_TAG_subprogram ? Entry : RootEntry;
549
550 // Analyse referenced DIEs.
551 bool Res = true;
552 if (!maybeAddReferencedRoots(Action, RootEntry: FinalRootEntry, Entry,
553 InterCUProcessingStarted,
554 HasNewInterconnectedCUs, RecordDepsOnly))
555 Res = false;
556
557 // Return if we do not need to process children.
558 if (isSingleAction(Action))
559 return Res;
560
561 // Process children.
562 // Check for subprograms special case.
563 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_subprogram &&
564 Info.getODRAvailable()) {
565 // Subprograms is a special case. As it can be root for type DIEs
566 // and itself may be subject to move into the artificial type unit.
567 // a) Non removable children(like DW_TAG_formal_parameter) should always
568 // be cloned. They are placed into the "PlainDwarf" and into the
569 // "TypeTable".
570 // b) ODR deduplication candidates(type DIEs) children should not be put
571 // into the "PlainDwarf".
572 // c) Children keeping addresses and locations(like DW_TAG_call_site)
573 // should not be put into the "TypeTable".
574 for (const DWARFDebugInfoEntry *CurChild =
575 Entry.CU->getFirstChildEntry(Die: Entry.DieEntry);
576 CurChild && CurChild->getAbbreviationDeclarationPtr();
577 CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) {
578 CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(Entry: CurChild);
579
580 switch (CurChild->getTag()) {
581 case dwarf::DW_TAG_variable:
582 case dwarf::DW_TAG_constant:
583 case dwarf::DW_TAG_subprogram:
584 case dwarf::DW_TAG_label: {
585 if (ChildInfo.getHasAnAddress())
586 continue;
587 } break;
588
589 // Entries having following tags could not be removed from the subprogram.
590 case dwarf::DW_TAG_lexical_block:
591 case dwarf::DW_TAG_friend:
592 case dwarf::DW_TAG_inheritance:
593 case dwarf::DW_TAG_formal_parameter:
594 case dwarf::DW_TAG_unspecified_parameters:
595 case dwarf::DW_TAG_template_type_parameter:
596 case dwarf::DW_TAG_template_value_parameter:
597 case dwarf::DW_TAG_GNU_template_parameter_pack:
598 case dwarf::DW_TAG_GNU_formal_parameter_pack:
599 case dwarf::DW_TAG_GNU_template_template_param:
600 case dwarf::DW_TAG_thrown_type: {
601 // Go to the default child handling.
602 } break;
603
604 default: {
605 bool ChildIsTypeTableCandidate = isTypeTableCandidate(DIEEntry: CurChild);
606
607 // Skip child marked to be copied into the artificial type unit.
608 if (isLiveAction(Action) && ChildIsTypeTableCandidate)
609 continue;
610
611 // Skip child marked to be copied into the plain unit.
612 if (isTypeAction(Action) && !ChildIsTypeTableCandidate)
613 continue;
614
615 // Go to the default child handling.
616 } break;
617 }
618
619 if (!markDIEEntryAsKeptRec(Action, RootEntry: FinalRootEntry,
620 Entry: UnitEntryPairTy{Entry.CU, CurChild},
621 InterCUProcessingStarted,
622 HasNewInterconnectedCUs, RecordDepsOnly))
623 Res = false;
624 }
625
626 return Res;
627 }
628
629 // Recursively process children.
630 for (const DWARFDebugInfoEntry *CurChild =
631 Entry.CU->getFirstChildEntry(Die: Entry.DieEntry);
632 CurChild && CurChild->getAbbreviationDeclarationPtr();
633 CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) {
634 CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(Entry: CurChild);
635 switch (CurChild->getTag()) {
636 case dwarf::DW_TAG_variable:
637 case dwarf::DW_TAG_constant:
638 case dwarf::DW_TAG_subprogram:
639 case dwarf::DW_TAG_label: {
640 if (ChildInfo.getHasAnAddress())
641 continue;
642 } break;
643 default:
644 break; // Nothing to do.
645 };
646
647 if (!markDIEEntryAsKeptRec(
648 Action, RootEntry: FinalRootEntry, Entry: UnitEntryPairTy{Entry.CU, CurChild},
649 InterCUProcessingStarted, HasNewInterconnectedCUs, RecordDepsOnly))
650 Res = false;
651 }
652
653 return Res;
654}
655
656bool DependencyTracker::isTypeTableCandidate(
657 const DWARFDebugInfoEntry *DIEEntry) {
658 switch (DIEEntry->getTag()) {
659 default:
660 return false;
661
662 case dwarf::DW_TAG_imported_module:
663 case dwarf::DW_TAG_imported_declaration:
664 case dwarf::DW_TAG_imported_unit:
665 case dwarf::DW_TAG_array_type:
666 case dwarf::DW_TAG_class_type:
667 case dwarf::DW_TAG_enumeration_type:
668 case dwarf::DW_TAG_pointer_type:
669 case dwarf::DW_TAG_reference_type:
670 case dwarf::DW_TAG_string_type:
671 case dwarf::DW_TAG_structure_type:
672 case dwarf::DW_TAG_subroutine_type:
673 case dwarf::DW_TAG_typedef:
674 case dwarf::DW_TAG_union_type:
675 case dwarf::DW_TAG_variant:
676 case dwarf::DW_TAG_module:
677 case dwarf::DW_TAG_ptr_to_member_type:
678 case dwarf::DW_TAG_set_type:
679 case dwarf::DW_TAG_subrange_type:
680 case dwarf::DW_TAG_base_type:
681 case dwarf::DW_TAG_const_type:
682 case dwarf::DW_TAG_enumerator:
683 case dwarf::DW_TAG_file_type:
684 case dwarf::DW_TAG_packed_type:
685 case dwarf::DW_TAG_thrown_type:
686 case dwarf::DW_TAG_volatile_type:
687 case dwarf::DW_TAG_dwarf_procedure:
688 case dwarf::DW_TAG_restrict_type:
689 case dwarf::DW_TAG_interface_type:
690 case dwarf::DW_TAG_namespace:
691 case dwarf::DW_TAG_unspecified_type:
692 case dwarf::DW_TAG_shared_type:
693 case dwarf::DW_TAG_rvalue_reference_type:
694 case dwarf::DW_TAG_coarray_type:
695 case dwarf::DW_TAG_dynamic_type:
696 case dwarf::DW_TAG_atomic_type:
697 case dwarf::DW_TAG_immutable_type:
698 case dwarf::DW_TAG_function_template:
699 case dwarf::DW_TAG_class_template:
700 return true;
701 }
702}
703
704bool DependencyTracker::maybeAddReferencedRoots(
705 LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry,
706 const UnitEntryPairTy &Entry, bool InterCUProcessingStarted,
707 std::atomic<bool> &HasNewInterconnectedCUs, bool RecordDepsOnly) {
708 const auto *Abbrev = Entry.DieEntry->getAbbreviationDeclarationPtr();
709 if (Abbrev == nullptr)
710 return true;
711
712 // In record-deps-only mode the referenced root is not scheduled for marking.
713 // The completeness dependency is appended directly so it participates in the
714 // demotion fixpoint without triggering any reference-following recursion.
715 auto AddRoot = [&](LiveRootWorklistActionTy RootAction,
716 const UnitEntryPairTy &Root,
717 const DWARFDebugInfoEntry *ReferencedTypeDieEntry) {
718 if (RecordDepsOnly) {
719 Dependencies.emplace_back(Args&: RootAction, Args: Root, Args: RootEntry,
720 Args&: ReferencedTypeDieEntry);
721 return;
722 }
723 addActionToRootEntriesWorkList(Action: RootAction, Entry: Root, ReferencedBy: RootEntry,
724 ReferencedTypeDieEntry);
725 };
726
727 DWARFUnit &Unit = Entry.CU->getOrigUnit();
728 DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
729 uint64_t Offset =
730 Entry.DieEntry->getOffset() + getULEB128Size(Value: Abbrev->getCode());
731
732 // For each DIE attribute...
733 for (const auto &AttrSpec : Abbrev->attributes()) {
734 DWARFFormValue Val(AttrSpec.Form);
735 if (!Val.isFormClass(FC: DWARFFormValue::FC_Reference) ||
736 AttrSpec.Attr == dwarf::DW_AT_sibling) {
737 DWARFFormValue::skipValue(Form: AttrSpec.Form, DebugInfoData: Data, OffsetPtr: &Offset,
738 FormParams: Unit.getFormParams());
739 continue;
740 }
741 Val.extractValue(Data, OffsetPtr: &Offset, FormParams: Unit.getFormParams(), U: &Unit);
742
743 // Resolve reference.
744 std::optional<UnitEntryPairTy> RefDie = Entry.CU->resolveDIEReference(
745 RefValue: Val, CanResolveInterCUReferences: InterCUProcessingStarted
746 ? ResolveInterCUReferencesMode::Resolve
747 : ResolveInterCUReferencesMode::AvoidResolving);
748 if (!RefDie) {
749 Entry.CU->warn(Warning: "could not find referenced DIE", DieEntry: Entry.DieEntry);
750 continue;
751 }
752
753 if (!RefDie->DieEntry) {
754 // The reference could not be resolved yet. Recording dependencies
755 // happens only after marking has fully resolved interconnections, so skip
756 // it here. The scheduling path below handles the delayed-resolution case.
757 if (RecordDepsOnly)
758 continue;
759
760 // Delay resolving reference.
761 RefDie->CU->setInterconnectedCU();
762 Entry.CU->setInterconnectedCU();
763 HasNewInterconnectedCUs = true;
764 return false;
765 }
766
767 assert((Entry.CU->getUniqueID() == RefDie->CU->getUniqueID() ||
768 InterCUProcessingStarted) &&
769 "Inter-CU reference while inter-CU processing is not started");
770
771 CompileUnit::DIEInfo &RefInfo = RefDie->CU->getDIEInfo(Entry: RefDie->DieEntry);
772 if (!RefInfo.getODRAvailable())
773 Action = LiveRootWorklistActionTy::MarkLiveEntryRec;
774 else if (RefInfo.getODRAvailable() &&
775 llvm::is_contained(Range: getODRAttributes(), Element: AttrSpec.Attr))
776 // Note: getODRAttributes does not include DW_AT_containing_type.
777 // It should be OK as we do getRootForSpecifiedEntry(). So any containing
778 // type would be found as the root for the entry.
779 Action = LiveRootWorklistActionTy::MarkTypeEntryRec;
780 else if (isLiveAction(Action))
781 Action = LiveRootWorklistActionTy::MarkLiveEntryRec;
782 else
783 Action = LiveRootWorklistActionTy::MarkTypeEntryRec;
784
785 if (AttrSpec.Attr == dwarf::DW_AT_import) {
786 if (isNamespaceLikeEntry(Entry: RefDie->DieEntry)) {
787 AddRoot(isTypeAction(Action)
788 ? LiveRootWorklistActionTy::MarkSingleTypeEntry
789 : LiveRootWorklistActionTy::MarkSingleLiveEntry,
790 *RefDie, nullptr);
791 continue;
792 }
793
794 AddRoot(Action, *RefDie, nullptr);
795 continue;
796 }
797
798 // Mark the enclosing root type as kept, but also record the actual
799 // referenced DIE: a nested type can be demoted to plain DWARF independently
800 // of its root, in which case ReferencedBy must be demoted too (see
801 // updateDependenciesCompleteness).
802 UnitEntryPairTy RootForReferencedDie = getRootForSpecifiedEntry(Entry: *RefDie);
803 AddRoot(Action, RootForReferencedDie, RefDie->DieEntry);
804 }
805
806 return true;
807}
808
809UnitEntryPairTy
810DependencyTracker::getRootForSpecifiedEntry(UnitEntryPairTy Entry) {
811 UnitEntryPairTy Result = Entry;
812
813 do {
814 switch (Entry.DieEntry->getTag()) {
815 case dwarf::DW_TAG_subprogram:
816 case dwarf::DW_TAG_label:
817 case dwarf::DW_TAG_variable:
818 case dwarf::DW_TAG_constant: {
819 return Result;
820 } break;
821
822 default: {
823 // Nothing to do.
824 }
825 }
826
827 std::optional<uint32_t> ParentIdx = Result.DieEntry->getParentIdx();
828 if (!ParentIdx)
829 return Result;
830
831 const DWARFDebugInfoEntry *ParentEntry =
832 Result.CU->getDebugInfoEntry(Index: *ParentIdx);
833 if (isNamespaceLikeEntry(Entry: ParentEntry))
834 break;
835 Result.DieEntry = ParentEntry;
836 } while (true);
837
838 return Result;
839}
840
841static void dumpKeptDIE(const DWARFDie &DIE, StringRef Kind, bool Verbose) {
842 if (!Verbose)
843 return;
844 outs() << "Keeping " << Kind << " DIE:";
845 DIDumpOptions DumpOpts;
846 DumpOpts.ChildRecurseDepth = 0;
847 DumpOpts.Verbose = Verbose;
848 DIE.dump(OS&: outs(), /*Indent=*/indent: 8, DumpOpts);
849}
850
851bool DependencyTracker::isLiveVariableEntry(const UnitEntryPairTy &Entry,
852 bool IsLiveParent) {
853 DWARFDie DIE = Entry.CU->getDIE(Die: Entry.DieEntry);
854 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Die: DIE);
855
856 if (Info.getTrackLiveness()) {
857 const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
858
859 if (!Info.getIsInFunctionScope() &&
860 Abbrev->findAttributeIndex(attr: dwarf::DW_AT_const_value)) {
861 // Global variables with constant value can always be kept.
862 } else {
863 // See if there is a relocation to a valid debug map entry inside this
864 // variable's location. The order is important here. We want to always
865 // check if the variable has a location expression address. However, we
866 // don't want a static variable in a function to force us to keep the
867 // enclosing function, unless requested explicitly.
868 std::pair<bool, std::optional<int64_t>> LocExprAddrAndRelocAdjustment =
869 Entry.CU->getContaingFile().Addresses->getVariableRelocAdjustment(
870 DIE, Verbose: Entry.CU->getGlobalData().getOptions().Verbose);
871
872 if (LocExprAddrAndRelocAdjustment.first)
873 Info.setHasAnAddress();
874
875 if (!LocExprAddrAndRelocAdjustment.second)
876 return false;
877
878 if (!IsLiveParent && Info.getIsInFunctionScope() &&
879 !Entry.CU->getGlobalData().getOptions().KeepFunctionForStatic)
880 return false;
881 }
882 }
883 Info.setHasAnAddress();
884
885 dumpKeptDIE(DIE, Kind: "variable", Verbose: Entry.CU->getGlobalData().getOptions().Verbose);
886
887 return true;
888}
889
890bool DependencyTracker::isLiveSubprogramEntry(const UnitEntryPairTy &Entry) {
891 DWARFDie DIE = Entry.CU->getDIE(Die: Entry.DieEntry);
892 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
893 std::optional<DWARFFormValue> LowPCVal = DIE.find(Attr: dwarf::DW_AT_low_pc);
894
895 const bool Verbose = Entry.CU->getGlobalData().getOptions().Verbose;
896 std::optional<uint64_t> LowPc;
897 std::optional<uint64_t> HighPc;
898 std::optional<int64_t> RelocAdjustment;
899 if (Info.getTrackLiveness()) {
900 LowPc = dwarf::toAddress(V: LowPCVal);
901 if (!LowPc)
902 return false;
903
904 Info.setHasAnAddress();
905
906 RelocAdjustment =
907 Entry.CU->getContaingFile().Addresses->getSubprogramRelocAdjustment(
908 DIE, Verbose);
909 if (!RelocAdjustment)
910 return false;
911
912 if (DIE.getTag() == dwarf::DW_TAG_subprogram) {
913 // Validate subprogram address range.
914
915 HighPc = DIE.getHighPC(LowPC: *LowPc);
916 if (!HighPc) {
917 Entry.CU->warn(Warning: "function without high_pc. Range will be discarded.",
918 DIE: &DIE);
919 return false;
920 }
921
922 if (*LowPc > *HighPc) {
923 Entry.CU->warn(Warning: "low_pc greater than high_pc. Range will be discarded.",
924 DIE: &DIE);
925 return false;
926 }
927 } else if (DIE.getTag() == dwarf::DW_TAG_label) {
928 if (Entry.CU->hasLabelAt(Addr: *LowPc))
929 return false;
930
931 // FIXME: dsymutil-classic compat. dsymutil-classic doesn't consider
932 // labels that don't fall into the CU's aranges. This is wrong IMO. Debug
933 // info generation bugs aside, this is really wrong in the case of labels,
934 // where a label marking the end of a function will have a PC == CU's
935 // high_pc.
936 if (dwarf::toAddress(V: Entry.CU->find(Die: Entry.DieEntry, Attrs: dwarf::DW_AT_high_pc))
937 .value_or(UINT64_MAX) <= LowPc)
938 return false;
939
940 // For assembly-language CUs there are typically no DW_TAG_subprogram
941 // DIEs, so labels are the only addresses we see. Fall back to the
942 // assembly-range lookup to recover a function range for the line-table
943 // filter; otherwise the output line table would be empty.
944 uint16_t Language = dwarf::toUnsigned(
945 V: Entry.CU->getOrigUnit().getUnitDIE().find(Attr: dwarf::DW_AT_language), Default: 0);
946 if (Language == dwarf::DW_LANG_Mips_Assembler ||
947 Language == dwarf::DW_LANG_Assembly) {
948 if (auto Range = Entry.CU->getContaingFile()
949 .Addresses->getAssemblyRangeForAddress(Addr: *LowPc))
950 Entry.CU->addFunctionRange(LowPC: Range->LowPC, HighPC: Range->HighPC,
951 PCOffset: *RelocAdjustment);
952 }
953
954 Entry.CU->addLabelLowPc(LabelLowPc: *LowPc, PcOffset: *RelocAdjustment);
955 }
956 } else
957 Info.setHasAnAddress();
958
959 dumpKeptDIE(DIE, Kind: "subprogram", Verbose);
960
961 if (!Info.getTrackLiveness() || DIE.getTag() == dwarf::DW_TAG_label)
962 return true;
963
964 Entry.CU->addFunctionRange(LowPC: *LowPc, HighPC: *HighPc, PCOffset: *RelocAdjustment);
965 return true;
966}
967