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 if (ReferencedBy) {
127 RootEntriesWorkList.emplace_back(Args&: Action, Args: Entry, Args&: *ReferencedBy);
128 return;
129 }
130
131 RootEntriesWorkList.emplace_back(Args&: Action, Args: Entry);
132}
133
134void DependencyTracker::collectRootsToKeep(
135 const UnitEntryPairTy &Entry, std::optional<UnitEntryPairTy> ReferencedBy,
136 bool IsLiveParent) {
137 for (const DWARFDebugInfoEntry *CurChild =
138 Entry.CU->getFirstChildEntry(Die: Entry.DieEntry);
139 CurChild && CurChild->getAbbreviationDeclarationPtr();
140 CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) {
141 UnitEntryPairTy ChildEntry(Entry.CU, CurChild);
142 CompileUnit::DIEInfo &ChildInfo = Entry.CU->getDIEInfo(Entry: CurChild);
143
144 bool IsLiveChild = false;
145
146 switch (CurChild->getTag()) {
147 case dwarf::DW_TAG_label: {
148 IsLiveChild = isLiveSubprogramEntry(Entry: ChildEntry);
149
150 // Keep label referencing live address.
151 // Keep label which is child of live parent entry.
152 if (IsLiveChild || (IsLiveParent && ChildInfo.getHasAnAddress())) {
153 addActionToRootEntriesWorkList(
154 Action: LiveRootWorklistActionTy::MarkLiveEntryRec, Entry: ChildEntry,
155 ReferencedBy);
156 }
157 } break;
158 case dwarf::DW_TAG_subprogram: {
159 IsLiveChild = isLiveSubprogramEntry(Entry: ChildEntry);
160
161 // Keep subprogram referencing live address.
162 if (IsLiveChild) {
163 // If subprogram is in module scope and this module allows ODR
164 // deduplication set "TypeTable" placement, otherwise set "" placement
165 LiveRootWorklistActionTy Action =
166 (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable())
167 ? LiveRootWorklistActionTy::MarkTypeEntryRec
168 : LiveRootWorklistActionTy::MarkLiveEntryRec;
169
170 addActionToRootEntriesWorkList(Action, Entry: ChildEntry, ReferencedBy);
171 }
172 } break;
173 case dwarf::DW_TAG_constant:
174 case dwarf::DW_TAG_variable: {
175 IsLiveChild = isLiveVariableEntry(Entry: ChildEntry, IsLiveParent);
176
177 // Keep variable referencing live address.
178 if (IsLiveChild) {
179 // If variable is in module scope and this module allows ODR
180 // deduplication set "TypeTable" placement, otherwise set "" placement
181
182 LiveRootWorklistActionTy Action =
183 (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable())
184 ? LiveRootWorklistActionTy::MarkTypeEntryRec
185 : LiveRootWorklistActionTy::MarkLiveEntryRec;
186
187 addActionToRootEntriesWorkList(Action, Entry: ChildEntry, ReferencedBy);
188 }
189 } break;
190 case dwarf::DW_TAG_base_type: {
191 // Always keep base types.
192 addActionToRootEntriesWorkList(
193 Action: LiveRootWorklistActionTy::MarkSingleLiveEntry, Entry: ChildEntry,
194 ReferencedBy);
195 } break;
196 case dwarf::DW_TAG_imported_module:
197 case dwarf::DW_TAG_imported_declaration:
198 case dwarf::DW_TAG_imported_unit: {
199 // Always keep DIEs having DW_AT_import attribute.
200 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_compile_unit) {
201 addActionToRootEntriesWorkList(
202 Action: LiveRootWorklistActionTy::MarkSingleLiveEntry, Entry: ChildEntry,
203 ReferencedBy);
204 break;
205 }
206
207 addActionToRootEntriesWorkList(
208 Action: LiveRootWorklistActionTy::MarkSingleTypeEntry, Entry: ChildEntry,
209 ReferencedBy);
210 } break;
211 case dwarf::DW_TAG_type_unit:
212 case dwarf::DW_TAG_partial_unit:
213 case dwarf::DW_TAG_compile_unit: {
214 llvm_unreachable("Called for incorrect DIE");
215 } break;
216 default:
217 // A forward-declared type nested in a DW_TAG_module is the module's
218 // record that the name exists, even when no full definition has been
219 // emitted. Route it through the type pool: when another CU emits a
220 // real definition for the same synthetic name, the existing
221 // decl-vs-def race resolution in allocateTypeDie + getFinalDie keeps
222 // the definition and drops this declaration at emission time. For
223 // non-ODR languages getFinalPlacementForEntry forces PlainDwarf,
224 // so the forward decl is kept in place under its module.
225 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_module &&
226 dwarf::isType(T: CurChild->getTag()) &&
227 dwarf::toUnsigned(V: Entry.CU->find(Die: CurChild, Attrs: dwarf::DW_AT_declaration),
228 Default: 0)) {
229 addActionToRootEntriesWorkList(
230 Action: LiveRootWorklistActionTy::MarkTypeEntryRec, Entry: ChildEntry,
231 ReferencedBy);
232 }
233 break;
234 }
235
236 collectRootsToKeep(Entry: ChildEntry, ReferencedBy, IsLiveParent: IsLiveChild || IsLiveParent);
237 }
238}
239
240bool DependencyTracker::markCollectedLiveRootsAsKept(
241 bool InterCUProcessingStarted, std::atomic<bool> &HasNewInterconnectedCUs) {
242 bool Res = true;
243
244 // Mark roots as kept.
245 while (!RootEntriesWorkList.empty()) {
246 LiveRootWorklistItemTy Root = RootEntriesWorkList.pop_back_val();
247
248 if (markDIEEntryAsKeptRec(Action: Root.getAction(), RootEntry: Root.getRootEntry(),
249 Entry: Root.getRootEntry(), InterCUProcessingStarted,
250 HasNewInterconnectedCUs)) {
251 if (Root.hasReferencedByOtherEntry())
252 Dependencies.push_back(Elt: Root);
253 } else
254 Res = false;
255 }
256
257 return Res;
258}
259
260bool DependencyTracker::updateDependenciesCompleteness() {
261 bool HasNewDependency = false;
262 for (LiveRootWorklistItemTy &Root : Dependencies) {
263 assert(Root.hasReferencedByOtherEntry() &&
264 "Root entry without dependency inside the dependencies list");
265
266 UnitEntryPairTy RootEntry = Root.getRootEntry();
267 CompileUnit::DIEInfo &RootInfo =
268 RootEntry.CU->getDIEInfo(Entry: RootEntry.DieEntry);
269
270 UnitEntryPairTy ReferencedByEntry = Root.getReferencedByEntry();
271 CompileUnit::DIEInfo &ReferencedByInfo =
272 ReferencedByEntry.CU->getDIEInfo(Entry: ReferencedByEntry.DieEntry);
273
274 if (!RootInfo.needToPlaceInTypeTable() &&
275 ReferencedByInfo.needToPlaceInTypeTable()) {
276 HasNewDependency = true;
277 setPlainDwarfPlacementRec(ReferencedByEntry);
278
279 // FIXME: we probably need to update getKeepTypeChildren status for
280 // parents of *Root.ReferencedBy.
281 }
282 }
283
284 return HasNewDependency;
285}
286
287void DependencyTracker::setPlainDwarfPlacementRec(
288 const UnitEntryPairTy &Entry) {
289 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
290 if (Info.getPlacement() == CompileUnit::PlainDwarf &&
291 !Info.getKeepTypeChildren())
292 return;
293
294 Info.setPlacement(CompileUnit::PlainDwarf);
295 Info.unsetKeepTypeChildren();
296 markParentsAsKeepingChildren(Entry);
297
298 for (const DWARFDebugInfoEntry *CurChild =
299 Entry.CU->getFirstChildEntry(Die: Entry.DieEntry);
300 CurChild && CurChild->getAbbreviationDeclarationPtr();
301 CurChild = Entry.CU->getSiblingEntry(Die: CurChild))
302 setPlainDwarfPlacementRec(UnitEntryPairTy{Entry.CU, CurChild});
303}
304
305static bool isNamespaceLikeEntry(const DWARFDebugInfoEntry *Entry) {
306 switch (Entry->getTag()) {
307 case dwarf::DW_TAG_compile_unit:
308 case dwarf::DW_TAG_module:
309 case dwarf::DW_TAG_namespace:
310 return true;
311
312 default:
313 return false;
314 }
315}
316
317bool isAlreadyMarked(const CompileUnit::DIEInfo &Info,
318 CompileUnit::DieOutputPlacement NewPlacement) {
319 if (!Info.getKeep())
320 return false;
321
322 switch (NewPlacement) {
323 case CompileUnit::TypeTable:
324 return Info.needToPlaceInTypeTable();
325
326 case CompileUnit::PlainDwarf:
327 return Info.needToKeepInPlainDwarf();
328
329 case CompileUnit::Both:
330 return Info.needToPlaceInTypeTable() && Info.needToKeepInPlainDwarf();
331
332 case CompileUnit::NotSet:
333 llvm_unreachable("Unset placement type is specified.");
334 };
335
336 llvm_unreachable("Unknown CompileUnit::DieOutputPlacement enum");
337}
338
339bool isAlreadyMarked(const UnitEntryPairTy &Entry,
340 CompileUnit::DieOutputPlacement NewPlacement) {
341 return isAlreadyMarked(Info: Entry.CU->getDIEInfo(Entry: Entry.DieEntry), NewPlacement);
342}
343
344void DependencyTracker::markParentsAsKeepingChildren(
345 const UnitEntryPairTy &Entry) {
346 if (Entry.DieEntry->getAbbreviationDeclarationPtr() == nullptr)
347 return;
348
349 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
350 bool NeedKeepTypeChildren = Info.needToPlaceInTypeTable();
351 bool NeedKeepPlainChildren = Info.needToKeepInPlainDwarf();
352
353 bool AreTypeParentsDone = !NeedKeepTypeChildren;
354 bool ArePlainParentsDone = !NeedKeepPlainChildren;
355
356 // Mark parents as 'Keep*Children'.
357 std::optional<uint32_t> ParentIdx = Entry.DieEntry->getParentIdx();
358 while (ParentIdx) {
359 const DWARFDebugInfoEntry *ParentEntry =
360 Entry.CU->getDebugInfoEntry(Index: *ParentIdx);
361 CompileUnit::DIEInfo &ParentInfo = Entry.CU->getDIEInfo(Idx: *ParentIdx);
362
363 if (!AreTypeParentsDone && NeedKeepTypeChildren) {
364 if (ParentInfo.getKeepTypeChildren())
365 AreTypeParentsDone = true;
366 else {
367 bool AddToWorklist = !isAlreadyMarked(
368 Info: ParentInfo, NewPlacement: CompileUnit::DieOutputPlacement::TypeTable);
369 ParentInfo.setKeepTypeChildren();
370 if (AddToWorklist && !isNamespaceLikeEntry(Entry: ParentEntry)) {
371 addActionToRootEntriesWorkList(
372 Action: LiveRootWorklistActionTy::MarkTypeChildrenRec,
373 Entry: UnitEntryPairTy{Entry.CU, ParentEntry}, ReferencedBy: std::nullopt);
374 }
375 }
376 }
377
378 if (!ArePlainParentsDone && NeedKeepPlainChildren) {
379 if (ParentInfo.getKeepPlainChildren())
380 ArePlainParentsDone = true;
381 else {
382 bool AddToWorklist = !isAlreadyMarked(
383 Info: ParentInfo, NewPlacement: CompileUnit::DieOutputPlacement::PlainDwarf);
384 ParentInfo.setKeepPlainChildren();
385 if (AddToWorklist && !isNamespaceLikeEntry(Entry: ParentEntry)) {
386 addActionToRootEntriesWorkList(
387 Action: LiveRootWorklistActionTy::MarkLiveChildrenRec,
388 Entry: UnitEntryPairTy{Entry.CU, ParentEntry}, ReferencedBy: std::nullopt);
389 }
390 }
391 }
392
393 if (AreTypeParentsDone && ArePlainParentsDone)
394 break;
395
396 ParentIdx = ParentEntry->getParentIdx();
397 }
398}
399
400// This function tries to set specified \p Placement for the \p Entry.
401// Depending on the concrete entry, the placement could be:
402// a) changed to another.
403// b) joined with current entry placement.
404// c) set as requested.
405static CompileUnit::DieOutputPlacement
406getFinalPlacementForEntry(const UnitEntryPairTy &Entry,
407 CompileUnit::DieOutputPlacement Placement) {
408 assert((Placement != CompileUnit::NotSet) && "Placement is not set");
409 CompileUnit::DIEInfo &EntryInfo = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
410
411 if (!EntryInfo.getODRAvailable())
412 return CompileUnit::PlainDwarf;
413
414 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_variable) {
415 // In-class static member declarations (e.g. "static constexpr int x = 1;")
416 // are DW_TAG_variable children of a DW_TAG_class_type /
417 // DW_TAG_structure_type / DW_TAG_union_type with DW_AT_declaration set.
418 // They are part of the class type and belong in the TypeTable together with
419 // the class. Forcing them into PlainDwarf would also drag the parent class
420 // into PlainDwarf (via markParentsAsKeepingChildren), producing a duplicate
421 // empty class declaration DIE alongside the full class definition emitted
422 // in another CU.
423 bool IsDeclaration = dwarf::toUnsigned(
424 V: Entry.CU->find(Die: Entry.DieEntry, Attrs: dwarf::DW_AT_declaration), Default: 0);
425 bool ParentIsType = false;
426 if (IsDeclaration) {
427 if (std::optional<uint32_t> ParentIdx = Entry.DieEntry->getParentIdx()) {
428 dwarf::Tag ParentTag =
429 Entry.CU->getDebugInfoEntry(Index: *ParentIdx)->getTag();
430 ParentIsType = ParentTag == dwarf::DW_TAG_class_type ||
431 ParentTag == dwarf::DW_TAG_structure_type ||
432 ParentTag == dwarf::DW_TAG_union_type;
433 }
434 }
435 if (IsDeclaration && ParentIsType) {
436 // Pure declarations have no runtime address; they belong with the class
437 // type. Always place in TypeTable regardless of how they were reached.
438 return CompileUnit::TypeTable;
439 }
440
441 // Do not put variable into the "TypeTable" and "PlainDwarf" at the same
442 // time.
443 if (EntryInfo.getPlacement() == CompileUnit::PlainDwarf ||
444 EntryInfo.getPlacement() == CompileUnit::Both)
445 return CompileUnit::PlainDwarf;
446
447 if (Placement == CompileUnit::PlainDwarf || Placement == CompileUnit::Both)
448 return CompileUnit::PlainDwarf;
449 }
450
451 switch (EntryInfo.getPlacement()) {
452 case CompileUnit::NotSet:
453 return Placement;
454
455 case CompileUnit::TypeTable:
456 return Placement == CompileUnit::PlainDwarf ? CompileUnit::Both : Placement;
457
458 case CompileUnit::PlainDwarf:
459 return Placement == CompileUnit::TypeTable ? CompileUnit::Both : Placement;
460
461 case CompileUnit::Both:
462 return CompileUnit::Both;
463 };
464
465 llvm_unreachable("Unknown placement type.");
466 return Placement;
467}
468
469bool DependencyTracker::markDIEEntryAsKeptRec(
470 LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry,
471 const UnitEntryPairTy &Entry, bool InterCUProcessingStarted,
472 std::atomic<bool> &HasNewInterconnectedCUs) {
473 if (Entry.DieEntry->getAbbreviationDeclarationPtr() == nullptr)
474 return true;
475
476 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
477
478 // Calculate final placement placement.
479 CompileUnit::DieOutputPlacement Placement = getFinalPlacementForEntry(
480 Entry,
481 Placement: isLiveAction(Action) ? CompileUnit::PlainDwarf : CompileUnit::TypeTable);
482 assert((Info.getODRAvailable() || isLiveAction(Action) ||
483 Placement == CompileUnit::PlainDwarf) &&
484 "Wrong kind of placement for ODR unavailable entry");
485
486 if (!isChildrenAction(Action))
487 if (isAlreadyMarked(Entry, NewPlacement: Placement))
488 return true;
489
490 // Mark current DIE as kept.
491 Info.setKeep();
492 Info.setPlacement(Placement);
493
494 // Set keep children property for parents.
495 markParentsAsKeepingChildren(Entry);
496
497 UnitEntryPairTy FinalRootEntry =
498 Entry.DieEntry->getTag() == dwarf::DW_TAG_subprogram ? Entry : RootEntry;
499
500 // Analyse referenced DIEs.
501 bool Res = true;
502 if (!maybeAddReferencedRoots(Action, RootEntry: FinalRootEntry, Entry,
503 InterCUProcessingStarted,
504 HasNewInterconnectedCUs))
505 Res = false;
506
507 // Return if we do not need to process children.
508 if (isSingleAction(Action))
509 return Res;
510
511 // Process children.
512 // Check for subprograms special case.
513 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_subprogram &&
514 Info.getODRAvailable()) {
515 // Subprograms is a special case. As it can be root for type DIEs
516 // and itself may be subject to move into the artificial type unit.
517 // a) Non removable children(like DW_TAG_formal_parameter) should always
518 // be cloned. They are placed into the "PlainDwarf" and into the
519 // "TypeTable".
520 // b) ODR deduplication candidates(type DIEs) children should not be put
521 // into the "PlainDwarf".
522 // c) Children keeping addresses and locations(like DW_TAG_call_site)
523 // should not be put into the "TypeTable".
524 for (const DWARFDebugInfoEntry *CurChild =
525 Entry.CU->getFirstChildEntry(Die: Entry.DieEntry);
526 CurChild && CurChild->getAbbreviationDeclarationPtr();
527 CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) {
528 CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(Entry: CurChild);
529
530 switch (CurChild->getTag()) {
531 case dwarf::DW_TAG_variable:
532 case dwarf::DW_TAG_constant:
533 case dwarf::DW_TAG_subprogram:
534 case dwarf::DW_TAG_label: {
535 if (ChildInfo.getHasAnAddress())
536 continue;
537 } break;
538
539 // Entries having following tags could not be removed from the subprogram.
540 case dwarf::DW_TAG_lexical_block:
541 case dwarf::DW_TAG_friend:
542 case dwarf::DW_TAG_inheritance:
543 case dwarf::DW_TAG_formal_parameter:
544 case dwarf::DW_TAG_unspecified_parameters:
545 case dwarf::DW_TAG_template_type_parameter:
546 case dwarf::DW_TAG_template_value_parameter:
547 case dwarf::DW_TAG_GNU_template_parameter_pack:
548 case dwarf::DW_TAG_GNU_formal_parameter_pack:
549 case dwarf::DW_TAG_GNU_template_template_param:
550 case dwarf::DW_TAG_thrown_type: {
551 // Go to the default child handling.
552 } break;
553
554 default: {
555 bool ChildIsTypeTableCandidate = isTypeTableCandidate(DIEEntry: CurChild);
556
557 // Skip child marked to be copied into the artificial type unit.
558 if (isLiveAction(Action) && ChildIsTypeTableCandidate)
559 continue;
560
561 // Skip child marked to be copied into the plain unit.
562 if (isTypeAction(Action) && !ChildIsTypeTableCandidate)
563 continue;
564
565 // Go to the default child handling.
566 } break;
567 }
568
569 if (!markDIEEntryAsKeptRec(
570 Action, RootEntry: FinalRootEntry, Entry: UnitEntryPairTy{Entry.CU, CurChild},
571 InterCUProcessingStarted, HasNewInterconnectedCUs))
572 Res = false;
573 }
574
575 return Res;
576 }
577
578 // Recursively process children.
579 for (const DWARFDebugInfoEntry *CurChild =
580 Entry.CU->getFirstChildEntry(Die: Entry.DieEntry);
581 CurChild && CurChild->getAbbreviationDeclarationPtr();
582 CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) {
583 CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(Entry: CurChild);
584 switch (CurChild->getTag()) {
585 case dwarf::DW_TAG_variable:
586 case dwarf::DW_TAG_constant:
587 case dwarf::DW_TAG_subprogram:
588 case dwarf::DW_TAG_label: {
589 if (ChildInfo.getHasAnAddress())
590 continue;
591 } break;
592 default:
593 break; // Nothing to do.
594 };
595
596 if (!markDIEEntryAsKeptRec(
597 Action, RootEntry: FinalRootEntry, Entry: UnitEntryPairTy{Entry.CU, CurChild},
598 InterCUProcessingStarted, HasNewInterconnectedCUs))
599 Res = false;
600 }
601
602 return Res;
603}
604
605bool DependencyTracker::isTypeTableCandidate(
606 const DWARFDebugInfoEntry *DIEEntry) {
607 switch (DIEEntry->getTag()) {
608 default:
609 return false;
610
611 case dwarf::DW_TAG_imported_module:
612 case dwarf::DW_TAG_imported_declaration:
613 case dwarf::DW_TAG_imported_unit:
614 case dwarf::DW_TAG_array_type:
615 case dwarf::DW_TAG_class_type:
616 case dwarf::DW_TAG_enumeration_type:
617 case dwarf::DW_TAG_pointer_type:
618 case dwarf::DW_TAG_reference_type:
619 case dwarf::DW_TAG_string_type:
620 case dwarf::DW_TAG_structure_type:
621 case dwarf::DW_TAG_subroutine_type:
622 case dwarf::DW_TAG_typedef:
623 case dwarf::DW_TAG_union_type:
624 case dwarf::DW_TAG_variant:
625 case dwarf::DW_TAG_module:
626 case dwarf::DW_TAG_ptr_to_member_type:
627 case dwarf::DW_TAG_set_type:
628 case dwarf::DW_TAG_subrange_type:
629 case dwarf::DW_TAG_base_type:
630 case dwarf::DW_TAG_const_type:
631 case dwarf::DW_TAG_enumerator:
632 case dwarf::DW_TAG_file_type:
633 case dwarf::DW_TAG_packed_type:
634 case dwarf::DW_TAG_thrown_type:
635 case dwarf::DW_TAG_volatile_type:
636 case dwarf::DW_TAG_dwarf_procedure:
637 case dwarf::DW_TAG_restrict_type:
638 case dwarf::DW_TAG_interface_type:
639 case dwarf::DW_TAG_namespace:
640 case dwarf::DW_TAG_unspecified_type:
641 case dwarf::DW_TAG_shared_type:
642 case dwarf::DW_TAG_rvalue_reference_type:
643 case dwarf::DW_TAG_coarray_type:
644 case dwarf::DW_TAG_dynamic_type:
645 case dwarf::DW_TAG_atomic_type:
646 case dwarf::DW_TAG_immutable_type:
647 case dwarf::DW_TAG_function_template:
648 case dwarf::DW_TAG_class_template:
649 return true;
650 }
651}
652
653bool DependencyTracker::maybeAddReferencedRoots(
654 LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry,
655 const UnitEntryPairTy &Entry, bool InterCUProcessingStarted,
656 std::atomic<bool> &HasNewInterconnectedCUs) {
657 const auto *Abbrev = Entry.DieEntry->getAbbreviationDeclarationPtr();
658 if (Abbrev == nullptr)
659 return true;
660
661 DWARFUnit &Unit = Entry.CU->getOrigUnit();
662 DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
663 uint64_t Offset =
664 Entry.DieEntry->getOffset() + getULEB128Size(Value: Abbrev->getCode());
665
666 // For each DIE attribute...
667 for (const auto &AttrSpec : Abbrev->attributes()) {
668 DWARFFormValue Val(AttrSpec.Form);
669 if (!Val.isFormClass(FC: DWARFFormValue::FC_Reference) ||
670 AttrSpec.Attr == dwarf::DW_AT_sibling) {
671 DWARFFormValue::skipValue(Form: AttrSpec.Form, DebugInfoData: Data, OffsetPtr: &Offset,
672 FormParams: Unit.getFormParams());
673 continue;
674 }
675 Val.extractValue(Data, OffsetPtr: &Offset, FormParams: Unit.getFormParams(), U: &Unit);
676
677 // Resolve reference.
678 std::optional<UnitEntryPairTy> RefDie = Entry.CU->resolveDIEReference(
679 RefValue: Val, CanResolveInterCUReferences: InterCUProcessingStarted
680 ? ResolveInterCUReferencesMode::Resolve
681 : ResolveInterCUReferencesMode::AvoidResolving);
682 if (!RefDie) {
683 Entry.CU->warn(Warning: "could not find referenced DIE", DieEntry: Entry.DieEntry);
684 continue;
685 }
686
687 if (!RefDie->DieEntry) {
688 // Delay resolving reference.
689 RefDie->CU->setInterconnectedCU();
690 Entry.CU->setInterconnectedCU();
691 HasNewInterconnectedCUs = true;
692 return false;
693 }
694
695 assert((Entry.CU->getUniqueID() == RefDie->CU->getUniqueID() ||
696 InterCUProcessingStarted) &&
697 "Inter-CU reference while inter-CU processing is not started");
698
699 CompileUnit::DIEInfo &RefInfo = RefDie->CU->getDIEInfo(Entry: RefDie->DieEntry);
700 if (!RefInfo.getODRAvailable())
701 Action = LiveRootWorklistActionTy::MarkLiveEntryRec;
702 else if (RefInfo.getODRAvailable() &&
703 llvm::is_contained(Range: getODRAttributes(), Element: AttrSpec.Attr))
704 // Note: getODRAttributes does not include DW_AT_containing_type.
705 // It should be OK as we do getRootForSpecifiedEntry(). So any containing
706 // type would be found as the root for the entry.
707 Action = LiveRootWorklistActionTy::MarkTypeEntryRec;
708 else if (isLiveAction(Action))
709 Action = LiveRootWorklistActionTy::MarkLiveEntryRec;
710 else
711 Action = LiveRootWorklistActionTy::MarkTypeEntryRec;
712
713 if (AttrSpec.Attr == dwarf::DW_AT_import) {
714 if (isNamespaceLikeEntry(Entry: RefDie->DieEntry)) {
715 addActionToRootEntriesWorkList(
716 Action: isTypeAction(Action)
717 ? LiveRootWorklistActionTy::MarkSingleTypeEntry
718 : LiveRootWorklistActionTy::MarkSingleLiveEntry,
719 Entry: *RefDie, ReferencedBy: RootEntry);
720 continue;
721 }
722
723 addActionToRootEntriesWorkList(Action, Entry: *RefDie, ReferencedBy: RootEntry);
724 continue;
725 }
726
727 UnitEntryPairTy RootForReferencedDie = getRootForSpecifiedEntry(Entry: *RefDie);
728 addActionToRootEntriesWorkList(Action, Entry: RootForReferencedDie, ReferencedBy: RootEntry);
729 }
730
731 return true;
732}
733
734UnitEntryPairTy
735DependencyTracker::getRootForSpecifiedEntry(UnitEntryPairTy Entry) {
736 UnitEntryPairTy Result = Entry;
737
738 do {
739 switch (Entry.DieEntry->getTag()) {
740 case dwarf::DW_TAG_subprogram:
741 case dwarf::DW_TAG_label:
742 case dwarf::DW_TAG_variable:
743 case dwarf::DW_TAG_constant: {
744 return Result;
745 } break;
746
747 default: {
748 // Nothing to do.
749 }
750 }
751
752 std::optional<uint32_t> ParentIdx = Result.DieEntry->getParentIdx();
753 if (!ParentIdx)
754 return Result;
755
756 const DWARFDebugInfoEntry *ParentEntry =
757 Result.CU->getDebugInfoEntry(Index: *ParentIdx);
758 if (isNamespaceLikeEntry(Entry: ParentEntry))
759 break;
760 Result.DieEntry = ParentEntry;
761 } while (true);
762
763 return Result;
764}
765
766static void dumpKeptDIE(const DWARFDie &DIE, StringRef Kind, bool Verbose) {
767 if (!Verbose)
768 return;
769 outs() << "Keeping " << Kind << " DIE:";
770 DIDumpOptions DumpOpts;
771 DumpOpts.ChildRecurseDepth = 0;
772 DumpOpts.Verbose = Verbose;
773 DIE.dump(OS&: outs(), /*Indent=*/indent: 8, DumpOpts);
774}
775
776bool DependencyTracker::isLiveVariableEntry(const UnitEntryPairTy &Entry,
777 bool IsLiveParent) {
778 DWARFDie DIE = Entry.CU->getDIE(Die: Entry.DieEntry);
779 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Die: DIE);
780
781 if (Info.getTrackLiveness()) {
782 const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
783
784 if (!Info.getIsInFunctionScope() &&
785 Abbrev->findAttributeIndex(attr: dwarf::DW_AT_const_value)) {
786 // Global variables with constant value can always be kept.
787 } else {
788 // See if there is a relocation to a valid debug map entry inside this
789 // variable's location. The order is important here. We want to always
790 // check if the variable has a location expression address. However, we
791 // don't want a static variable in a function to force us to keep the
792 // enclosing function, unless requested explicitly.
793 std::pair<bool, std::optional<int64_t>> LocExprAddrAndRelocAdjustment =
794 Entry.CU->getContaingFile().Addresses->getVariableRelocAdjustment(
795 DIE, Verbose: Entry.CU->getGlobalData().getOptions().Verbose);
796
797 if (LocExprAddrAndRelocAdjustment.first)
798 Info.setHasAnAddress();
799
800 if (!LocExprAddrAndRelocAdjustment.second)
801 return false;
802
803 if (!IsLiveParent && Info.getIsInFunctionScope() &&
804 !Entry.CU->getGlobalData().getOptions().KeepFunctionForStatic)
805 return false;
806 }
807 }
808 Info.setHasAnAddress();
809
810 dumpKeptDIE(DIE, Kind: "variable", Verbose: Entry.CU->getGlobalData().getOptions().Verbose);
811
812 return true;
813}
814
815bool DependencyTracker::isLiveSubprogramEntry(const UnitEntryPairTy &Entry) {
816 DWARFDie DIE = Entry.CU->getDIE(Die: Entry.DieEntry);
817 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry);
818 std::optional<DWARFFormValue> LowPCVal = DIE.find(Attr: dwarf::DW_AT_low_pc);
819
820 const bool Verbose = Entry.CU->getGlobalData().getOptions().Verbose;
821 std::optional<uint64_t> LowPc;
822 std::optional<uint64_t> HighPc;
823 std::optional<int64_t> RelocAdjustment;
824 if (Info.getTrackLiveness()) {
825 LowPc = dwarf::toAddress(V: LowPCVal);
826 if (!LowPc)
827 return false;
828
829 Info.setHasAnAddress();
830
831 RelocAdjustment =
832 Entry.CU->getContaingFile().Addresses->getSubprogramRelocAdjustment(
833 DIE, Verbose);
834 if (!RelocAdjustment)
835 return false;
836
837 if (DIE.getTag() == dwarf::DW_TAG_subprogram) {
838 // Validate subprogram address range.
839
840 HighPc = DIE.getHighPC(LowPC: *LowPc);
841 if (!HighPc) {
842 Entry.CU->warn(Warning: "function without high_pc. Range will be discarded.",
843 DIE: &DIE);
844 return false;
845 }
846
847 if (*LowPc > *HighPc) {
848 Entry.CU->warn(Warning: "low_pc greater than high_pc. Range will be discarded.",
849 DIE: &DIE);
850 return false;
851 }
852 } else if (DIE.getTag() == dwarf::DW_TAG_label) {
853 if (Entry.CU->hasLabelAt(Addr: *LowPc))
854 return false;
855
856 // FIXME: dsymutil-classic compat. dsymutil-classic doesn't consider
857 // labels that don't fall into the CU's aranges. This is wrong IMO. Debug
858 // info generation bugs aside, this is really wrong in the case of labels,
859 // where a label marking the end of a function will have a PC == CU's
860 // high_pc.
861 if (dwarf::toAddress(V: Entry.CU->find(Die: Entry.DieEntry, Attrs: dwarf::DW_AT_high_pc))
862 .value_or(UINT64_MAX) <= LowPc)
863 return false;
864
865 // For assembly-language CUs there are typically no DW_TAG_subprogram
866 // DIEs, so labels are the only addresses we see. Fall back to the
867 // assembly-range lookup to recover a function range for the line-table
868 // filter; otherwise the output line table would be empty.
869 uint16_t Language = dwarf::toUnsigned(
870 V: Entry.CU->getOrigUnit().getUnitDIE().find(Attr: dwarf::DW_AT_language), Default: 0);
871 if (Language == dwarf::DW_LANG_Mips_Assembler ||
872 Language == dwarf::DW_LANG_Assembly) {
873 if (auto Range = Entry.CU->getContaingFile()
874 .Addresses->getAssemblyRangeForAddress(Addr: *LowPc))
875 Entry.CU->addFunctionRange(LowPC: Range->LowPC, HighPC: Range->HighPC,
876 PCOffset: *RelocAdjustment);
877 }
878
879 Entry.CU->addLabelLowPc(LabelLowPc: *LowPc, PcOffset: *RelocAdjustment);
880 }
881 } else
882 Info.setHasAnAddress();
883
884 dumpKeptDIE(DIE, Kind: "subprogram", Verbose);
885
886 if (!Info.getTrackLiveness() || DIE.getTag() == dwarf::DW_TAG_label)
887 return true;
888
889 Entry.CU->addFunctionRange(LowPC: *LowPc, HighPC: *HighPc, PCOffset: *RelocAdjustment);
890 return true;
891}
892