LLVM 24.0.0git
DependencyTracker.cpp
Go to the documentation of this file.
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"
12
13using namespace llvm;
14using namespace dwarf_linker;
15using namespace dwarf_linker::parallel;
16
17/// A broken link in the keep chain. By recording both the parent and the child
18/// we can show only broken links for DIEs with multiple children.
26
27/// Verify the keep chain by looking for DIEs that are kept but who's parent
28/// isn't.
30#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
31 SmallVector<DWARFDie> Worklist;
32 Worklist.push_back(CU.getOrigUnit().getUnitDIE());
33
34 // List of broken links.
35 SmallVector<BrokenLink> BrokenLinks;
36
37 while (!Worklist.empty()) {
38 const DWARFDie Current = Worklist.back();
39 Worklist.pop_back();
40
41 if (!Current.isValid())
42 continue;
43
44 CompileUnit::DIEInfo &CurrentInfo =
45 CU.getDIEInfo(Current.getDebugInfoEntry());
46 const bool ParentPlainDieIsKept = CurrentInfo.needToKeepInPlainDwarf();
47 const bool ParentTypeDieIsKept = CurrentInfo.needToPlaceInTypeTable();
48
49 for (DWARFDie Child : reverse(Current.children())) {
50 Worklist.push_back(Child);
51
52 CompileUnit::DIEInfo &ChildInfo =
53 CU.getDIEInfo(Child.getDebugInfoEntry());
54 const bool ChildPlainDieIsKept = ChildInfo.needToKeepInPlainDwarf();
55 const bool ChildTypeDieIsKept = ChildInfo.needToPlaceInTypeTable();
56
57 if (!ParentPlainDieIsKept && ChildPlainDieIsKept)
58 BrokenLinks.emplace_back(Current, Child,
59 "Found invalid link in keep chain");
60
61 if (Child.getTag() == dwarf::DW_TAG_subprogram) {
62 if (!ChildInfo.getKeep() && isLiveSubprogramEntry(UnitEntryPairTy(
63 &CU, Child.getDebugInfoEntry()))) {
64 BrokenLinks.emplace_back(Current, Child,
65 "Live subprogram is not marked as kept");
66 }
67 }
68
69 if (!ChildInfo.getODRAvailable()) {
70 assert(!ChildTypeDieIsKept);
71 continue;
72 }
73
74 if (!ParentTypeDieIsKept && ChildTypeDieIsKept)
75 BrokenLinks.emplace_back(Current, Child,
76 "Found invalid link in keep chain");
77
78 if (CurrentInfo.getIsInAnonNamespaceScope() &&
79 ChildInfo.needToPlaceInTypeTable()) {
80 BrokenLinks.emplace_back(Current, Child,
81 "Found invalid placement marking for member "
82 "of anonymous namespace");
83 }
84 }
85 }
86
87 if (!BrokenLinks.empty()) {
88 for (BrokenLink Link : BrokenLinks) {
89 errs() << "\n=================================\n";
90 WithColor::error() << formatv("{0} between {1:x} and {2:x}", Link.Message,
91 Link.Parent.getOffset(),
92 Link.Child.getOffset());
93
94 errs() << "\nParent:";
95 Link.Parent.dump(errs(), 0, {});
96 errs() << "\n";
97 CU.getDIEInfo(Link.Parent).dump();
98
99 errs() << "\nChild:";
100 Link.Child.dump(errs(), 2, {});
101 errs() << "\n";
102 CU.getDIEInfo(Link.Child).dump();
103 }
104 report_fatal_error("invalid keep chain");
105 }
106#endif
107}
108
109static bool isNamespaceLikeEntry(const DWARFDebugInfoEntry *Entry) {
110 switch (Entry->getTag()) {
111 case dwarf::DW_TAG_compile_unit:
112 case dwarf::DW_TAG_module:
113 case dwarf::DW_TAG_namespace:
114 return true;
115
116 default:
117 return false;
118 }
119}
120
122 RootEntriesWorkList.clear();
123
124 // Search for live root DIEs.
125 CompileUnit::DIEInfo &CUInfo = CU.getDIEInfo(CU.getDebugInfoEntry(0));
127 collectRootsToKeep(UnitEntryPairTy{&CU, CU.getDebugInfoEntry(0)},
128 std::nullopt, false);
129}
130
132 bool InterCUProcessingStarted, std::atomic<bool> &HasNewInterconnectedCUs) {
133 // The recorded subtrees are walked after marking, and need to resolve
134 // references the same way marking did. A unit whose references could not all
135 // be resolved is reset to its loaded stage and marked again from scratch, so
136 // no reference recorded under one resolution mode survives into another.
137 assert((SubtreeDependencyRefs.empty() ||
138 InterCUProcessingWasStarted == InterCUProcessingStarted) &&
139 "recorded subtrees would be walked in a different resolution mode");
140 InterCUProcessingWasStarted = InterCUProcessingStarted;
141
142 // Mark live DIEs as kept.
143 return markCollectedLiveRootsAsKept(InterCUProcessingStarted,
144 HasNewInterconnectedCUs);
145}
146
148 LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry,
149 std::optional<UnitEntryPairTy> ReferencedBy,
150 const DWARFDebugInfoEntry *ReferencedTypeDieEntry) {
151 if (ReferencedBy) {
152 RootEntriesWorkList.emplace_back(Action, Entry, *ReferencedBy,
153 ReferencedTypeDieEntry);
154 return;
155 }
156
157 RootEntriesWorkList.emplace_back(Action, Entry);
158}
159
161 const UnitEntryPairTy &Entry, std::optional<UnitEntryPairTy> ReferencedBy,
162 bool IsLiveParent) {
163 for (const DWARFDebugInfoEntry *CurChild =
164 Entry.CU->getFirstChildEntry(Entry.DieEntry);
165 CurChild && CurChild->getAbbreviationDeclarationPtr();
166 CurChild = Entry.CU->getSiblingEntry(CurChild)) {
167 UnitEntryPairTy ChildEntry(Entry.CU, CurChild);
168 CompileUnit::DIEInfo &ChildInfo = Entry.CU->getDIEInfo(CurChild);
169
170 bool IsLiveChild = false;
171
172 switch (CurChild->getTag()) {
173 case dwarf::DW_TAG_label: {
174 IsLiveChild = isLiveSubprogramEntry(ChildEntry);
175
176 // Keep label referencing live address.
177 // Keep label which is child of live parent entry.
178 if (IsLiveChild || (IsLiveParent && ChildInfo.getHasAnAddress())) {
181 ReferencedBy);
182 }
183 } break;
184 case dwarf::DW_TAG_subprogram: {
185 IsLiveChild = isLiveSubprogramEntry(ChildEntry);
186
187 // Keep subprogram referencing live address.
188 if (IsLiveChild) {
189 // If subprogram is in module scope and this module allows ODR
190 // deduplication set "TypeTable" placement, otherwise set "" placement
192 (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable())
195
196 addActionToRootEntriesWorkList(Action, ChildEntry, ReferencedBy);
197 }
198 } break;
199 case dwarf::DW_TAG_constant:
200 case dwarf::DW_TAG_variable: {
201 IsLiveChild = isLiveVariableEntry(ChildEntry, IsLiveParent);
202
203 // Keep variable referencing live address.
204 if (IsLiveChild) {
205 // If variable is in module scope and this module allows ODR
206 // deduplication set "TypeTable" placement, otherwise set "" placement
207
209 (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable())
212
213 addActionToRootEntriesWorkList(Action, ChildEntry, ReferencedBy);
214 }
215 } break;
216 case dwarf::DW_TAG_base_type: {
217 // Always keep base types.
220 ReferencedBy);
221 } break;
222 case dwarf::DW_TAG_imported_module:
223 case dwarf::DW_TAG_imported_declaration:
224 case dwarf::DW_TAG_imported_unit: {
225 // Always keep DIEs having DW_AT_import attribute.
226 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_compile_unit) {
229 ReferencedBy);
230 break;
231 }
232
235 ReferencedBy);
236 } break;
237 case dwarf::DW_TAG_type_unit:
238 case dwarf::DW_TAG_partial_unit:
239 case dwarf::DW_TAG_compile_unit: {
240 llvm_unreachable("Called for incorrect DIE");
241 } break;
242 default:
243 // A module compile unit has no relocations, so liveness analysis never
244 // reaches a type definition that nothing else in the unit references. The
245 // module owns the only copy of those definitions, so keep them.
246 if (Entry.CU->isClangModule() && isNamespaceLikeEntry(Entry.DieEntry) &&
247 dwarf::isType(CurChild->getTag())) {
250 ReferencedBy);
251 break;
252 }
253
254 // An importing unit emits a skeleton of the module it imports, so a
255 // forward-declared type nested in a DW_TAG_module there is the module's
256 // record that the name exists, even when no full definition has been
257 // emitted. Route it through the type pool: when another CU emits a
258 // real definition for the same synthetic name, the existing
259 // decl-vs-def race resolution in allocateTypeDie + getFinalDie keeps
260 // the definition and drops this declaration at emission time. For
261 // non-ODR languages getFinalPlacementForEntry forces PlainDwarf,
262 // so the forward decl is kept in place under its module.
263 if (!Entry.CU->isClangModule() &&
264 Entry.DieEntry->getTag() == dwarf::DW_TAG_module &&
265 dwarf::isType(CurChild->getTag()) &&
266 dwarf::toUnsigned(Entry.CU->find(CurChild, dwarf::DW_AT_declaration),
267 0)) {
270 ReferencedBy);
271 }
272 break;
273 }
274
275 collectRootsToKeep(ChildEntry, ReferencedBy, IsLiveChild || IsLiveParent);
276 }
277}
278
280 bool InterCUProcessingStarted, std::atomic<bool> &HasNewInterconnectedCUs) {
281 bool Res = true;
282
283 // Mark roots as kept.
284 while (!RootEntriesWorkList.empty()) {
285 LiveRootWorklistItemTy Root = RootEntriesWorkList.pop_back_val();
286
288 Root.getRootEntry(), InterCUProcessingStarted,
289 HasNewInterconnectedCUs)) {
290 if (Root.hasReferencedByOtherEntry())
291 Dependencies.push_back(Root);
292 } else
293 Res = false;
294 }
295
296 return Res;
297}
298
300 LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry,
301 const UnitEntryPairTy &Entry) {
302 SubtreeDependencyRefs.push_back({Entry, Action, RootEntry});
303}
304
306 // Walking a subtree appends the dependencies that belong to a subprogram
307 // nested inside it, so all walking has to finish before the dependency list
308 // is traversed.
309 for (size_t Idx = MaterializedRefs; Idx != SubtreeDependencyRefs.size();
310 ++Idx) {
311 // Copied rather than referenced so that the loop does not depend on the
312 // walk below leaving the vector alone.
314 SubtreeDependenciesKeyTy Key{Ref.Subtree.CU, Ref.Subtree.DieEntry,
315 Ref.Action};
316 if (SubtreeSummaries.contains(Key))
317 continue;
318
319 // Collected separately so that growing the map cannot invalidate the sink.
320 SubtreeDependenciesTy SubtreeDeps;
321 {
323 &SubtreeDeps);
324
325 // A walk that only records dependencies neither marks nor follows
326 // references, so it cannot discover a new interconnection and cannot
327 // fail.
328 std::atomic<bool> HasNewInterconnectedCUs = false;
329 [[maybe_unused]] bool Res = markDIEEntryAsKeptRec(
330 Ref.Action, Ref.ReferencedBy, Ref.Subtree,
331 InterCUProcessingWasStarted, HasNewInterconnectedCUs,
333 assert(Res && !HasNewInterconnectedCUs && "record-deps-only walk failed");
334 }
335
336 SubtreeSummaries[Key] = std::move(SubtreeDeps);
337 }
338
340}
341
343 const UnitEntryPairTy &Root,
344 const DWARFDebugInfoEntry *ReferencedTypeDieEntry,
345 const UnitEntryPairTy &ReferencedBy) {
346 // Completeness must be checked against the actual referenced DIE, not its
347 // enclosing root. A nested type can be demoted to plain DWARF while its
348 // root stays in the type table, and a type-table DIE may only reference
349 // DIEs that are themselves in the type table. Checking the root instead
350 // leaves such a DIE in the type table, later tripping the type-unit
351 // reference assertion in DIEAttributeCloner::cloneDieRefAttr.
352 const DWARFDebugInfoEntry *ReferencedDieEntry =
353 ReferencedTypeDieEntry ? ReferencedTypeDieEntry : Root.DieEntry;
354 CompileUnit::DIEInfo &RootInfo = Root.CU->getDIEInfo(ReferencedDieEntry);
355 CompileUnit::DIEInfo &ReferencedByInfo =
356 ReferencedBy.CU->getDIEInfo(ReferencedBy.DieEntry);
357
358 if (RootInfo.needToPlaceInTypeTable() ||
359 !ReferencedByInfo.needToPlaceInTypeTable())
360 return false;
361
362 setPlainDwarfPlacementRec(ReferencedBy);
363
364 // FIXME: we probably need to update getKeepTypeChildren status for
365 // parents of ReferencedBy.
366 return true;
367}
368
370 bool HasNewDependency = false;
372 CompileUnit::DIEInfo &ReferencedByInfo =
373 Ref.ReferencedBy.CU->getDIEInfo(Ref.ReferencedBy.DieEntry);
374 if (!ReferencedByInfo.needToPlaceInTypeTable())
375 continue;
376
377 SubtreeDependenciesKeyTy Key{Ref.Subtree.CU, Ref.Subtree.DieEntry,
378 Ref.Action};
379 auto Summary = SubtreeSummaries.find(Key);
380 assert(Summary != SubtreeSummaries.end() && "subtree was not summarized");
381
382 // Demotion takes the root out of the type table, so no further dependency
383 // of the same subtree can demote it again.
384 for (const SubtreeDependencyTy &Dep : Summary->second) {
386 Ref.ReferencedBy)) {
387 HasNewDependency = true;
388 break;
389 }
390 }
391 }
392
393 return HasNewDependency;
394}
395
398
399 bool HasNewDependency = false;
401 assert(Root.hasReferencedByOtherEntry() &&
402 "Root entry without dependency inside the dependencies list");
403
404 if (demoteIfIncomplete(Root.getRootEntry(),
405 Root.getReferencedTypeDieEntry(),
406 Root.getReferencedByEntry()))
407 HasNewDependency = true;
408 }
409
411 HasNewDependency = true;
412
413 return HasNewDependency;
414}
415
417 const UnitEntryPairTy &Entry) {
418 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry.DieEntry);
419 if (Info.getPlacement() == CompileUnit::PlainDwarf &&
420 !Info.getKeepTypeChildren())
421 return;
422
424 Info.unsetKeepTypeChildren();
426
427 for (const DWARFDebugInfoEntry *CurChild =
428 Entry.CU->getFirstChildEntry(Entry.DieEntry);
429 CurChild && CurChild->getAbbreviationDeclarationPtr();
430 CurChild = Entry.CU->getSiblingEntry(CurChild))
431 setPlainDwarfPlacementRec(UnitEntryPairTy{Entry.CU, CurChild});
432}
433
435 CompileUnit::DieOutputPlacement NewPlacement) {
436 if (!Info.getKeep())
437 return false;
438
439 switch (NewPlacement) {
441 return Info.needToPlaceInTypeTable();
442
444 return Info.needToKeepInPlainDwarf();
445
447 return Info.needToPlaceInTypeTable() && Info.needToKeepInPlainDwarf();
448
450 llvm_unreachable("Unset placement type is specified.");
451 };
452
453 llvm_unreachable("Unknown CompileUnit::DieOutputPlacement enum");
454}
455
457 CompileUnit::DieOutputPlacement NewPlacement) {
458 return isAlreadyMarked(Entry.CU->getDIEInfo(Entry.DieEntry), NewPlacement);
459}
460
462 const UnitEntryPairTy &Child,
463 TreeWalkKindTy Kind) {
464 if (recordsDepsOnly(Kind) ||
465 !Child.CU->getDIEInfo(Child.DieEntry).getKeepWithParent())
466 return;
467
468 // The variable cannot go to the type table. As a root that the walked root
469 // depends on, it takes that root out of the type table too, which leaves it
470 // under the DIE the instances of its function refer to.
472 Child, RootEntry);
473}
474
476 const UnitEntryPairTy &Entry) {
477 if (Entry.DieEntry->getAbbreviationDeclarationPtr() == nullptr)
478 return;
479
480 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry.DieEntry);
481 bool NeedKeepTypeChildren = Info.needToPlaceInTypeTable();
482 bool NeedKeepPlainChildren = Info.needToKeepInPlainDwarf();
483
484 bool AreTypeParentsDone = !NeedKeepTypeChildren;
485 bool ArePlainParentsDone = !NeedKeepPlainChildren;
486
487 // Mark parents as 'Keep*Children'.
488 std::optional<uint32_t> ParentIdx = Entry.DieEntry->getParentIdx();
489 while (ParentIdx) {
490 const DWARFDebugInfoEntry *ParentEntry =
491 Entry.CU->getDebugInfoEntry(*ParentIdx);
492 CompileUnit::DIEInfo &ParentInfo = Entry.CU->getDIEInfo(*ParentIdx);
493
494 if (!AreTypeParentsDone && NeedKeepTypeChildren) {
495 if (ParentInfo.getKeepTypeChildren())
496 AreTypeParentsDone = true;
497 else {
498 bool AddToWorklist = !isAlreadyMarked(
500 ParentInfo.setKeepTypeChildren();
501 if (AddToWorklist && !isNamespaceLikeEntry(ParentEntry)) {
504 UnitEntryPairTy{Entry.CU, ParentEntry}, std::nullopt);
505 }
506 }
507 }
508
509 if (!ArePlainParentsDone && NeedKeepPlainChildren) {
510 if (ParentInfo.getKeepPlainChildren())
511 ArePlainParentsDone = true;
512 else {
513 bool AddToWorklist = !isAlreadyMarked(
515 ParentInfo.setKeepPlainChildren();
516 if (AddToWorklist && !isNamespaceLikeEntry(ParentEntry)) {
519 UnitEntryPairTy{Entry.CU, ParentEntry}, std::nullopt);
520 }
521 }
522 }
523
524 if (AreTypeParentsDone && ArePlainParentsDone)
525 break;
526
527 ParentIdx = ParentEntry->getParentIdx();
528 }
529}
530
531namespace {
532struct FinalPlacement {
534
535 /// How Placement combines with the DIE's current placement when applied.
536 enum ApplyMode {
537 /// Overwrite the current placement. Used for entries whose placement is
538 /// fully determined regardless of how they were reached, so every mark
539 /// agrees on the value (ODR-unavailable entries and static data member
540 /// declarations).
541 Overwrite,
542 /// OR-join into the current placement (the common monotone-lattice case):
543 /// a DIE reached by both a live and a type mark ends up in Both.
544 Join,
545 /// Join for a DW_TAG_variable, which cannot occupy the type table and plain
546 /// DWARF at once: PlainDwarf is absorbing so the variable never lands in
547 /// Both.
548 JoinVariable,
549 } Mode;
550};
551} // namespace
552
553// Computes the placement to apply to \p Entry for a mark requesting \p
554// Placement (PlainDwarf for a live action, TypeTable for a type action), along
555// with how it combines with the DIE's current placement. Most entries join, so
556// a DIE reached by both actions ends up in Both. Entries whose placement is
557// fully determined regardless of how they were reached instead overwrite with
558// an exact placement: ODR-unavailable entries cannot be deduplicated into the
559// type table, and a DW_TAG_variable cannot occupy the type table and plain
560// DWARF at once.
561static FinalPlacement
564 assert((Placement != CompileUnit::NotSet) && "Placement is not set");
565 CompileUnit::DIEInfo &EntryInfo = Entry.CU->getDIEInfo(Entry.DieEntry);
566
567 if (!EntryInfo.getODRAvailable())
568 return {CompileUnit::PlainDwarf, FinalPlacement::Overwrite};
569
570 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_variable) {
571 // In-class static member declarations (e.g. "static constexpr int x = 1;")
572 // are DW_TAG_variable children of a DW_TAG_class_type /
573 // DW_TAG_structure_type / DW_TAG_union_type with DW_AT_declaration set.
574 // They are part of the class type and belong in the TypeTable together with
575 // the class. Forcing them into PlainDwarf would also drag the parent class
576 // into PlainDwarf (via markParentsAsKeepingChildren), producing a duplicate
577 // empty class declaration DIE alongside the full class definition emitted
578 // in another CU.
579 bool IsDeclaration = dwarf::toUnsigned(
580 Entry.CU->find(Entry.DieEntry, dwarf::DW_AT_declaration), 0);
581 bool ParentIsType = false;
582 if (IsDeclaration) {
583 if (std::optional<uint32_t> ParentIdx = Entry.DieEntry->getParentIdx()) {
584 dwarf::Tag ParentTag =
585 Entry.CU->getDebugInfoEntry(*ParentIdx)->getTag();
586 ParentIsType = ParentTag == dwarf::DW_TAG_class_type ||
587 ParentTag == dwarf::DW_TAG_structure_type ||
588 ParentTag == dwarf::DW_TAG_union_type;
589 }
590 }
591 if (IsDeclaration && ParentIsType) {
592 // Pure declarations have no runtime address; they belong with the class
593 // type. Always place in TypeTable regardless of how they were reached.
594 return {CompileUnit::TypeTable, FinalPlacement::Overwrite};
595 }
596
597 // A live (PlainDwarf) mark pins the variable to plain DWARF.
599 return {CompileUnit::PlainDwarf, FinalPlacement::Overwrite};
600
601 // Only a type-table mark reaches here. The variable join keeps a PlainDwarf
602 // mark racing this one from turning the variable into Both.
603 return {Placement, FinalPlacement::JoinVariable};
604 }
605
606 return {Placement, FinalPlacement::Join};
607}
608
610 LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry,
611 const UnitEntryPairTy &Entry, bool InterCUProcessingStarted,
612 std::atomic<bool> &HasNewInterconnectedCUs, TreeWalkKindTy Kind) {
613 if (Entry.DieEntry->getAbbreviationDeclarationPtr() == nullptr)
614 return true;
615
616 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry.DieEntry);
617
618 // Calculate final placement.
619 FinalPlacement Final = getFinalPlacementForEntry(
620 Entry,
623 assert((Info.getODRAvailable() || isLiveAction(Action) ||
625 "Wrong kind of placement for ODR unavailable entry");
626
627 if (!recordsDepsOnly(Kind) && !isChildrenAction(Action) &&
628 isAlreadyMarked(Entry, Placement)) {
629 // Entry (and its subtree) were already marked, possibly by a racing CU or
630 // another referencing root, and which one wins is non-deterministic. Skip
631 // the redundant marking, but still record that this root carries the
632 // dependencies the subtree contributes. Otherwise the recorded dependency
633 // set depends on thread interleaving, the demotion fixpoint misses
634 // demotions, and whole type subtrees are left in the artificial type unit
635 // non-deterministically.
636 recordSubtreeDependencies(Action, RootEntry, Entry);
637 return true;
638 }
639
640 if (!recordsDepsOnly(Kind)) {
641 // Mark current DIE as kept.
642 Info.setKeep();
643 // Marks compose monotonically so no interleaving loses an update: a general
644 // mark only raises the placement in the lattice, and a forced placement is
645 // a value every mark agrees on.
646 switch (Final.Mode) {
647 case FinalPlacement::Overwrite:
648 Info.setPlacement(Placement);
649 break;
650 case FinalPlacement::Join:
651 Info.joinPlacement(Placement);
652 break;
653 case FinalPlacement::JoinVariable:
654 Info.joinVariablePlacement(Placement);
655 break;
656 }
657
658 // Set keep children property for parents.
660 }
661
662 bool IsSubprogram = Entry.DieEntry->getTag() == dwarf::DW_TAG_subprogram;
663 UnitEntryPairTy FinalRootEntry = IsSubprogram ? Entry : RootEntry;
664
665 // A subprogram becomes the root of everything found below it, so from here on
666 // the dependencies name the subprogram instead of the root referencing the
667 // walked subtree, and are the same for every such root.
668 TreeWalkKindTy FinalKind =
669 IsSubprogram && Kind == TreeWalkKindTy::RecordSubtreeDeps
671 : Kind;
672
673 // Analyse referenced DIEs.
674 bool Res = true;
675 if (!maybeAddReferencedRoots(Action, FinalRootEntry, Entry,
676 InterCUProcessingStarted,
677 HasNewInterconnectedCUs, FinalKind))
678 Res = false;
679
680 // Return if we do not need to process children.
681 if (isSingleAction(Action))
682 return Res;
683
684 // Process children.
685 // Check for subprograms special case.
686 if (Entry.DieEntry->getTag() == dwarf::DW_TAG_subprogram &&
687 Info.getODRAvailable()) {
688 // Subprograms is a special case. As it can be root for type DIEs
689 // and itself may be subject to move into the artificial type unit.
690 // a) Non removable children(like DW_TAG_formal_parameter) should always
691 // be cloned. They are placed into the "PlainDwarf" and into the
692 // "TypeTable".
693 // b) ODR deduplication candidates(type DIEs) children should not be put
694 // into the "PlainDwarf".
695 // c) Children keeping addresses and locations(like DW_TAG_call_site)
696 // should not be put into the "TypeTable".
697 for (const DWARFDebugInfoEntry *CurChild =
698 Entry.CU->getFirstChildEntry(Entry.DieEntry);
699 CurChild && CurChild->getAbbreviationDeclarationPtr();
700 CurChild = Entry.CU->getSiblingEntry(CurChild)) {
701 CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(CurChild);
702
703 switch (CurChild->getTag()) {
704 case dwarf::DW_TAG_variable:
705 case dwarf::DW_TAG_constant:
706 case dwarf::DW_TAG_subprogram:
707 case dwarf::DW_TAG_label: {
708 if (ChildInfo.getHasAnAddress()) {
709 keepWithParent(FinalRootEntry, UnitEntryPairTy{Entry.CU, CurChild},
710 Kind);
711 continue;
712 }
713 } break;
714
715 // Entries having following tags could not be removed from the subprogram.
716 case dwarf::DW_TAG_lexical_block:
717 case dwarf::DW_TAG_friend:
718 case dwarf::DW_TAG_inheritance:
719 case dwarf::DW_TAG_formal_parameter:
720 case dwarf::DW_TAG_unspecified_parameters:
721 case dwarf::DW_TAG_template_type_parameter:
722 case dwarf::DW_TAG_template_value_parameter:
723 case dwarf::DW_TAG_GNU_template_parameter_pack:
724 case dwarf::DW_TAG_GNU_formal_parameter_pack:
725 case dwarf::DW_TAG_GNU_template_template_param:
726 case dwarf::DW_TAG_thrown_type: {
727 // Go to the default child handling.
728 } break;
729
730 default: {
731 bool ChildIsTypeTableCandidate = isTypeTableCandidate(CurChild);
732
733 // Skip child marked to be copied into the artificial type unit.
734 if (isLiveAction(Action) && ChildIsTypeTableCandidate)
735 continue;
736
737 // Skip child marked to be copied into the plain unit.
738 if (isTypeAction(Action) && !ChildIsTypeTableCandidate)
739 continue;
740
741 // Go to the default child handling.
742 } break;
743 }
744
746 Action, FinalRootEntry, UnitEntryPairTy{Entry.CU, CurChild},
747 InterCUProcessingStarted, HasNewInterconnectedCUs, FinalKind))
748 Res = false;
749 }
750
751 return Res;
752 }
753
754 // Recursively process children.
755 for (const DWARFDebugInfoEntry *CurChild =
756 Entry.CU->getFirstChildEntry(Entry.DieEntry);
757 CurChild && CurChild->getAbbreviationDeclarationPtr();
758 CurChild = Entry.CU->getSiblingEntry(CurChild)) {
759 CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(CurChild);
760 switch (CurChild->getTag()) {
761 case dwarf::DW_TAG_variable:
762 case dwarf::DW_TAG_constant:
763 case dwarf::DW_TAG_subprogram:
764 case dwarf::DW_TAG_label: {
765 if (ChildInfo.getHasAnAddress()) {
766 keepWithParent(FinalRootEntry, UnitEntryPairTy{Entry.CU, CurChild},
767 Kind);
768 continue;
769 }
770 } break;
771 default:
772 break; // Nothing to do.
773 };
774
776 Action, FinalRootEntry, UnitEntryPairTy{Entry.CU, CurChild},
777 InterCUProcessingStarted, HasNewInterconnectedCUs, FinalKind))
778 Res = false;
779 }
780
781 return Res;
782}
783
786 switch (DIEEntry->getTag()) {
787 default:
788 return false;
789
790 case dwarf::DW_TAG_imported_module:
791 case dwarf::DW_TAG_imported_declaration:
792 case dwarf::DW_TAG_imported_unit:
793 case dwarf::DW_TAG_array_type:
794 case dwarf::DW_TAG_class_type:
795 case dwarf::DW_TAG_enumeration_type:
796 case dwarf::DW_TAG_pointer_type:
797 case dwarf::DW_TAG_reference_type:
798 case dwarf::DW_TAG_string_type:
799 case dwarf::DW_TAG_structure_type:
800 case dwarf::DW_TAG_subroutine_type:
801 case dwarf::DW_TAG_typedef:
802 case dwarf::DW_TAG_union_type:
803 case dwarf::DW_TAG_variant:
804 case dwarf::DW_TAG_module:
805 case dwarf::DW_TAG_ptr_to_member_type:
806 case dwarf::DW_TAG_set_type:
807 case dwarf::DW_TAG_subrange_type:
808 case dwarf::DW_TAG_base_type:
809 case dwarf::DW_TAG_const_type:
810 case dwarf::DW_TAG_enumerator:
811 case dwarf::DW_TAG_file_type:
812 case dwarf::DW_TAG_packed_type:
813 case dwarf::DW_TAG_thrown_type:
814 case dwarf::DW_TAG_volatile_type:
815 case dwarf::DW_TAG_dwarf_procedure:
816 case dwarf::DW_TAG_restrict_type:
817 case dwarf::DW_TAG_interface_type:
818 case dwarf::DW_TAG_namespace:
819 case dwarf::DW_TAG_unspecified_type:
820 case dwarf::DW_TAG_shared_type:
821 case dwarf::DW_TAG_rvalue_reference_type:
822 case dwarf::DW_TAG_coarray_type:
823 case dwarf::DW_TAG_dynamic_type:
824 case dwarf::DW_TAG_atomic_type:
825 case dwarf::DW_TAG_immutable_type:
826 case dwarf::DW_TAG_function_template:
827 case dwarf::DW_TAG_class_template:
828 return true;
829 }
830}
831
833 LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry,
834 const UnitEntryPairTy &Entry, bool InterCUProcessingStarted,
835 std::atomic<bool> &HasNewInterconnectedCUs, TreeWalkKindTy Kind) {
836 const auto *Abbrev = Entry.DieEntry->getAbbreviationDeclarationPtr();
837 if (Abbrev == nullptr)
838 return true;
839
840 // A walk that only records dependencies does not schedule the referenced root
841 // for marking. The completeness dependency is collected instead, so it
842 // participates in the demotion fixpoint without triggering any
843 // reference-following recursion.
844 auto AddRoot = [&](LiveRootWorklistActionTy RootAction,
845 const UnitEntryPairTy &Root,
846 const DWARFDebugInfoEntry *ReferencedTypeDieEntry) {
847 switch (Kind) {
849 addActionToRootEntriesWorkList(RootAction, Root, RootEntry,
850 ReferencedTypeDieEntry);
851 return;
852
854 // The dependency belongs to whichever root references this subtree, so it
855 // is summarized and applied to each of them in turn.
856 assert(CollectedSubtreeDeps && "record-deps-only walk without a sink");
857 CollectedSubtreeDeps->push_back(
858 {RootAction, Root, ReferencedTypeDieEntry});
859 return;
860
862 // The dependency belongs to a subprogram nested inside the subtree, so it
863 // is the same for every referencing root and recording it once is enough.
864 Dependencies.emplace_back(RootAction, Root, RootEntry,
865 ReferencedTypeDieEntry);
866 return;
867 }
868 llvm_unreachable("Unknown TreeWalkKindTy enum");
869 };
870
871 DWARFUnit &Unit = Entry.CU->getOrigUnit();
872 DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
873 uint64_t Offset =
874 Entry.DieEntry->getOffset() + getULEB128Size(Abbrev->getCode());
875
876 // For each DIE attribute...
877 for (const auto &AttrSpec : Abbrev->attributes()) {
878 DWARFFormValue Val(AttrSpec.Form);
880 AttrSpec.Attr == dwarf::DW_AT_sibling) {
881 DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset,
882 Unit.getFormParams());
883 continue;
884 }
885 Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit);
886
887 // Resolve reference.
888 std::optional<UnitEntryPairTy> RefDie = Entry.CU->resolveDIEReference(
889 Val, InterCUProcessingStarted
892 if (!RefDie) {
893 Entry.CU->warn("could not find referenced DIE", Entry.DieEntry);
894 continue;
895 }
896
897 if (!RefDie->DieEntry) {
898 // The reference could not be resolved yet. Recording dependencies
899 // happens only after marking has fully resolved interconnections, so skip
900 // it here. The scheduling path below handles the delayed-resolution case.
901 if (recordsDepsOnly(Kind))
902 continue;
903
904 // Delay resolving reference.
905 RefDie->CU->setInterconnectedCU();
906 Entry.CU->setInterconnectedCU();
907 HasNewInterconnectedCUs = true;
908 return false;
909 }
910
911 assert((Entry.CU->getUniqueID() == RefDie->CU->getUniqueID() ||
912 InterCUProcessingStarted) &&
913 "Inter-CU reference while inter-CU processing is not started");
914 assert(RefDie->CU->getStage() >= CompileUnit::Stage::LiveRootsCollected &&
915 "Referenced unit has not found its live roots");
916
917 CompileUnit::DIEInfo &RefInfo = RefDie->CU->getDIEInfo(RefDie->DieEntry);
918 if (!RefInfo.getODRAvailable())
920 else if (RefInfo.getODRAvailable() &&
921 llvm::is_contained(getODRAttributes(), AttrSpec.Attr))
922 // Note: getODRAttributes does not include DW_AT_containing_type.
923 // It should be OK as we do getRootForSpecifiedEntry(). So any containing
924 // type would be found as the root for the entry.
926 else if (isLiveAction(Action))
928 else
930
931 if (AttrSpec.Attr == dwarf::DW_AT_import) {
932 if (isNamespaceLikeEntry(RefDie->DieEntry)) {
933 AddRoot(isTypeAction(Action)
936 *RefDie, nullptr);
937 continue;
938 }
939
940 AddRoot(Action, *RefDie, nullptr);
941 continue;
942 }
943
944 // Mark the enclosing root type as kept, but also record the actual
945 // referenced DIE: a nested type can be demoted to plain DWARF independently
946 // of its root, in which case ReferencedBy must be demoted too (see
947 // updateDependenciesCompleteness).
948 UnitEntryPairTy RootForReferencedDie = getRootForSpecifiedEntry(*RefDie);
949 AddRoot(Action, RootForReferencedDie, RefDie->DieEntry);
950 }
951
952 return true;
953}
954
957 UnitEntryPairTy Result = Entry;
958
959 do {
960 switch (Entry.DieEntry->getTag()) {
961 case dwarf::DW_TAG_subprogram:
962 case dwarf::DW_TAG_label:
963 case dwarf::DW_TAG_variable:
964 case dwarf::DW_TAG_constant: {
965 return Result;
966 } break;
967
968 default: {
969 // Nothing to do.
970 }
971 }
972
973 std::optional<uint32_t> ParentIdx = Result.DieEntry->getParentIdx();
974 if (!ParentIdx)
975 return Result;
976
977 const DWARFDebugInfoEntry *ParentEntry =
978 Result.CU->getDebugInfoEntry(*ParentIdx);
979 if (isNamespaceLikeEntry(ParentEntry))
980 break;
981 Result.DieEntry = ParentEntry;
982 } while (true);
983
984 return Result;
985}
986
987static void dumpKeptDIE(const DWARFDie &DIE, StringRef Kind, bool Verbose) {
988 if (!Verbose)
989 return;
990 outs() << "Keeping " << Kind << " DIE:";
991 DIDumpOptions DumpOpts;
992 DumpOpts.ChildRecurseDepth = 0;
993 DumpOpts.Verbose = Verbose;
994 DIE.dump(outs(), /*Indent=*/8, DumpOpts);
995}
996
998 bool IsLiveParent) {
999 DWARFDie DIE = Entry.CU->getDIE(Entry.DieEntry);
1000 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(DIE);
1001
1002 if (Info.getTrackLiveness()) {
1003 const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
1004
1005 if (!Info.getIsInFunctionScope() &&
1006 Abbrev->findAttributeIndex(dwarf::DW_AT_const_value)) {
1007 // Global variables with constant value can always be kept.
1008 } else {
1009 // See if there is a relocation to a valid debug map entry inside this
1010 // variable's location. The order is important here. We want to always
1011 // check if the variable has a location expression address. However, we
1012 // don't want a static variable in a function to force us to keep the
1013 // enclosing function, unless requested explicitly.
1014 std::pair<bool, std::optional<int64_t>> LocExprAddrAndRelocAdjustment =
1015 Entry.CU->getContainingFile().Addresses->getVariableRelocAdjustment(
1016 DIE, Entry.CU->getGlobalData().getOptions().Verbose);
1017
1018 if (LocExprAddrAndRelocAdjustment.first)
1019 Info.setHasAnAddress();
1020
1021 if (!LocExprAddrAndRelocAdjustment.second)
1022 return false;
1023
1024 if (!IsLiveParent && Info.getIsInFunctionScope() &&
1025 !Entry.CU->getGlobalData().getOptions().KeepFunctionForStatic) {
1026 Info.setKeepWithParent();
1027 return false;
1028 }
1029 }
1030 }
1031 Info.setHasAnAddress();
1032
1033 dumpKeptDIE(DIE, "variable", Entry.CU->getGlobalData().getOptions().Verbose);
1034
1035 return true;
1036}
1037
1039 DWARFDie DIE = Entry.CU->getDIE(Entry.DieEntry);
1040 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry.DieEntry);
1041 std::optional<DWARFFormValue> LowPCVal = DIE.find(dwarf::DW_AT_low_pc);
1042
1043 const bool Verbose = Entry.CU->getGlobalData().getOptions().Verbose;
1044 std::optional<uint64_t> LowPc;
1045 std::optional<uint64_t> HighPc;
1046 std::optional<int64_t> RelocAdjustment;
1047 if (Info.getTrackLiveness()) {
1048 LowPc = dwarf::toAddress(LowPCVal);
1049 if (!LowPc)
1050 return false;
1051
1052 Info.setHasAnAddress();
1053
1054 RelocAdjustment =
1055 Entry.CU->getContainingFile().Addresses->getSubprogramRelocAdjustment(
1056 DIE, Verbose);
1057 if (!RelocAdjustment)
1058 return false;
1059
1060 if (DIE.getTag() == dwarf::DW_TAG_subprogram) {
1061 // Validate subprogram address range.
1062
1063 HighPc = DIE.getHighPC(*LowPc);
1064 if (!HighPc) {
1065 Entry.CU->warn("function without high_pc. Range will be discarded.",
1066 &DIE);
1067 return false;
1068 }
1069
1070 if (*LowPc > *HighPc) {
1071 Entry.CU->warn("low_pc greater than high_pc. Range will be discarded.",
1072 &DIE);
1073 return false;
1074 }
1075 } else if (DIE.getTag() == dwarf::DW_TAG_label) {
1076 if (Entry.CU->hasLabelAt(*LowPc))
1077 return false;
1078
1079 // FIXME: dsymutil-classic compat. dsymutil-classic doesn't consider
1080 // labels that don't fall into the CU's aranges. This is wrong IMO. Debug
1081 // info generation bugs aside, this is really wrong in the case of labels,
1082 // where a label marking the end of a function will have a PC == CU's
1083 // high_pc.
1084 if (dwarf::toAddress(Entry.CU->find(Entry.DieEntry, dwarf::DW_AT_high_pc))
1085 .value_or(UINT64_MAX) <= LowPc)
1086 return false;
1087
1088 // For assembly-language CUs there are typically no DW_TAG_subprogram
1089 // DIEs, so labels are the only addresses we see. Fall back to the
1090 // symbol-range lookup to recover a function range for the line-table
1091 // filter; otherwise the output line table would be empty.
1092 uint16_t Language = dwarf::toUnsigned(
1093 Entry.CU->getOrigUnit().getUnitDIE().find(dwarf::DW_AT_language), 0);
1094 if (Language == dwarf::DW_LANG_Mips_Assembler ||
1095 Language == dwarf::DW_LANG_Assembly) {
1096 if (auto Range = Entry.CU->getContainingFile()
1097 .Addresses->getSymbolRangeForAddress(*LowPc))
1098 Entry.CU->addFunctionRange(Range->LowPC, Range->HighPC,
1099 *RelocAdjustment);
1100 }
1101
1102 Entry.CU->addLabelLowPc(*LowPc, *RelocAdjustment);
1103 }
1104 } else
1105 Info.setHasAnAddress();
1106
1107 dumpKeptDIE(DIE, "subprogram", Verbose);
1108
1109 if (!Info.getTrackLiveness() || DIE.getTag() == dwarf::DW_TAG_label)
1110 return true;
1111
1112 Entry.CU->addFunctionRange(
1113 *LowPc,
1114 Entry.CU->getContainingFile().Addresses->constrainCodeRangeHighPC(
1115 *LowPc, *HighPc, *RelocAdjustment),
1116 *RelocAdjustment);
1117 return true;
1118}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
bool isAlreadyMarked(const CompileUnit::DIEInfo &Info, CompileUnit::DieOutputPlacement NewPlacement)
static void dumpKeptDIE(const DWARFDie &DIE, StringRef Kind, bool Verbose)
static FinalPlacement getFinalPlacementForEntry(const UnitEntryPairTy &Entry, CompileUnit::DieOutputPlacement Placement)
static bool isNamespaceLikeEntry(const DWARFDebugInfoEntry *Entry)
Branch Probability Basic Block Placement
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
This file provides utility classes that use RAII to save and restore values.
A pointer to another debug information entry.
Definition DIE.h:318
A structured debug information entry.
Definition DIE.h:835
dwarf::Tag getTag() const
Definition DIE.h:880
LLVM_ABI void dump() const
Definition DIE.cpp:286
A DWARFDataExtractor (typically for an in-memory copy of an object-file section) plus a relocation ma...
DWARFDebugInfoEntry - A DIE with only the minimum required data.
std::optional< uint32_t > getParentIdx() const
Returns index of the parent die.
const DWARFAbbreviationDeclaration * getAbbreviationDeclarationPtr() const
Utility class that carries the DWARF compile/type unit and the debug info entry in an object.
Definition DWARFDie.h:43
iterator_range< iterator > children() const
Definition DWARFDie.h:407
const DWARFDebugInfoEntry * getDebugInfoEntry() const
Definition DWARFDie.h:54
bool isValid() const
Definition DWARFDie.h:52
LLVM_ABI bool isFormClass(FormClass FC) const
LLVM_ABI bool extractValue(const DWARFDataExtractor &Data, uint64_t *OffsetPtr, dwarf::FormParams FormParams, const DWARFContext *Context=nullptr, const DWARFUnit *Unit=nullptr)
Extracts a value in Data at offset *OffsetPtr.
bool skipValue(DataExtractor DebugInfoData, uint64_t *OffsetPtr, const dwarf::FormParams Params) const
Skip a form's value in DebugInfoData at the offset specified by OffsetPtr.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
static LLVM_ABI raw_ostream & error()
Convenience method for printing "error: " to stderr.
Definition WithColor.cpp:84
DieOutputPlacement
Kinds of placement for the output die.
@ Both
Corresponding DIE goes to type table and to plain dwarf.
@ TypeTable
Corresponding DIE goes to the type table only.
@ PlainDwarf
Corresponding DIE goes to the plain dwarf only.
@ LiveRootsCollected
DIEs with a live address are found.
bool markDIEEntryAsKeptRec(LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry, bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs, TreeWalkKindTy Kind=TreeWalkKindTy::MarkTree)
Mark whole DIE tree as kept recursively.
void verifyKeepChain()
Recursively walk the DIE tree and check "keepness" and "placement" information.
RootEntriesListTy Dependencies
List of entries dependencies.
void markParentsAsKeepingChildren(const UnitEntryPairTy &Entry)
Mark parents as keeping children.
UnitEntryPairTy getRootForSpecifiedEntry(UnitEntryPairTy Entry)
static bool recordsDepsOnly(TreeWalkKindTy Kind)
bool demoteIfIncomplete(const UnitEntryPairTy &Root, const DWARFDebugInfoEntry *ReferencedTypeDieEntry, const UnitEntryPairTy &ReferencedBy)
Demote ReferencedBy to plain DWARF if it may not stay in the type table while the DIE it references t...
bool markCollectedLiveRootsAsKept(bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
Examine worklist and mark all 'root DIE's as kept and set "Placement" property.
bool InterCUProcessingWasStarted
Whether inter-unit references could be resolved during marking.
bool applySubtreeSummaries()
Apply each summarized subtree's dependencies to every root recorded as referencing it.
bool isLiveAction(LiveRootWorklistActionTy Action)
bool isChildrenAction(LiveRootWorklistActionTy Action)
void keepWithParent(const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Child, TreeWalkKindTy Kind)
Keep Child if it is a variable that is kept with its parent, which the walk in progress keeps for Roo...
TreeWalkKindTy
What a tree walk does, and for a walk that only records dependencies, which root the dependencies it ...
@ MarkTree
Mark the tree as kept and schedule the roots it references.
bool isTypeAction(LiveRootWorklistActionTy Action)
void addActionToRootEntriesWorkList(LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry, std::optional< UnitEntryPairTy > ReferencedBy, const DWARFDebugInfoEntry *ReferencedTypeDieEntry=nullptr)
Add action item to the work list.
DenseMap< SubtreeDependenciesKeyTy, SubtreeDependenciesTy > SubtreeSummaries
Dependency summaries of already-marked subtrees, keyed by subtree and action.
SubtreeDependenciesTy * CollectedSubtreeDeps
Where the walk in progress collects the dependencies that belong to the root referencing the walked s...
bool isTypeTableCandidate(const DWARFDebugInfoEntry *DIEEntry)
size_t MaterializedRefs
Number of leading SubtreeDependencyRefs whose subtree is summarized.
void setPlainDwarfPlacementRec(const UnitEntryPairTy &Entry)
Mark whole DIE tree as placed in "PlainDwarf".
RootEntriesListTy RootEntriesWorkList
List of entries which are 'root DIE's.
SmallVector< SubtreeDependencyTy > SubtreeDependenciesTy
static bool isLiveSubprogramEntry(const UnitEntryPairTy &Entry)
Returns true if specified subprogram references live code section.
std::tuple< CompileUnit *, const DWARFDebugInfoEntry *, LiveRootWorklistActionTy > SubtreeDependenciesKeyTy
A subtree paired with the action it is walked with, which selects both the visited children and the a...
void recordSubtreeDependencies(LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry)
Record that RootEntry references the already-marked subtree Entry, and therefore carries the complete...
bool resolveDependenciesAndMarkLiveness(bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
Recursively walk the DIE tree and look for DIEs to keep.
static bool isLiveVariableEntry(const UnitEntryPairTy &Entry, bool IsLiveParent)
Returns true if specified variable references live code section.
@ MarkTypeEntryRec
Mark current item and all its children as type entry.
@ MarkLiveChildrenRec
Mark all children of current item as live entry.
@ MarkLiveEntryRec
Mark current item and all its children as live entry.
@ MarkTypeChildrenRec
Mark all children of current item as type entry.
SmallVector< SubtreeDependencyRefTy > SubtreeDependencyRefs
Roots referencing an already-marked subtree.
void collectLiveRoots()
This function is the entry point of the DIE selection algorithm.
void collectRootsToKeep(const UnitEntryPairTy &Entry, std::optional< UnitEntryPairTy > ReferencedBy, bool IsLiveParent)
This function navigates DIEs tree starting from specified Entry.
bool maybeAddReferencedRoots(LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry, bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs, TreeWalkKindTy Kind=TreeWalkKindTy::MarkTree)
Check referenced DIEs and add them into the worklist.
bool updateDependenciesCompleteness()
Check if dependencies have incompatible placement.
void materializeSubtreeSummaries()
Walk every subtree that a recorded reference stands for, once per subtree and action,...
DIEInfo & getDIEInfo(unsigned Idx)
Idx index of the DIE.
#define UINT64_MAX
Definition DataTypes.h:77
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ArrayRef< dwarf::Attribute > getODRAttributes()
std::optional< uint64_t > toAddress(const std::optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract an address.
bool isType(Tag T)
Definition Dwarf.h:113
std::optional< uint64_t > toUnsigned(const std::optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract an unsigned constant.
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:577
LLVM_ABI raw_fd_ostream & outs()
This returns a reference to a raw_fd_ostream for standard output.
auto formatv(bool Validate, const char *Fmt, Ts &&...Vals)
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
Definition Error.cpp:163
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ Ref
The access may reference the value stored in memory.
Definition ModRef.h:32
LLVM_ABI unsigned getULEB128Size(uint64_t Value)
Utility function to get the size of the ULEB128-encoded value.
Definition LEB128.cpp:19
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1963
Container for dump options that control which debug information will be dumped.
Definition DIContext.h:197
unsigned ChildRecurseDepth
Definition DIContext.h:199
A utility class that uses RAII to save and restore the value of a variable.
Information gathered about a DIE in the object file.
void setPlacement(DieOutputPlacement Placement)
Sets Placement kind for the corresponding die.
A root referencing an already-marked subtree, standing in for all of that subtree's dependencies.
A completeness dependency of a subtree that belongs to whichever root references the subtree,...
This is a helper structure which keeps a debug info entry with it's containing compilation unit.