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