838 lines · cpp
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-exception6//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 child17/// 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 parent27/// 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#endif106}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(CU.getDebugInfoEntry(0));114 CUInfo.setPlacement(CompileUnit::PlainDwarf);115 collectRootsToKeep(UnitEntryPairTy{&CU, CU.getDebugInfoEntry(0)},116 std::nullopt, 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(Action, Entry, *ReferencedBy);128 return;129 }130 131 RootEntriesWorkList.emplace_back(Action, 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(Entry.DieEntry);139 CurChild && CurChild->getAbbreviationDeclarationPtr();140 CurChild = Entry.CU->getSiblingEntry(CurChild)) {141 UnitEntryPairTy ChildEntry(Entry.CU, CurChild);142 CompileUnit::DIEInfo &ChildInfo = Entry.CU->getDIEInfo(CurChild);143 144 bool IsLiveChild = false;145 146 switch (CurChild->getTag()) {147 case dwarf::DW_TAG_label: {148 IsLiveChild = isLiveSubprogramEntry(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 LiveRootWorklistActionTy::MarkLiveEntryRec, ChildEntry,155 ReferencedBy);156 }157 } break;158 case dwarf::DW_TAG_subprogram: {159 IsLiveChild = isLiveSubprogramEntry(ChildEntry);160 161 // Keep subprogram referencing live address.162 if (IsLiveChild) {163 // If subprogram is in module scope and this module allows ODR164 // deduplication set "TypeTable" placement, otherwise set "" placement165 LiveRootWorklistActionTy Action =166 (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable())167 ? LiveRootWorklistActionTy::MarkTypeEntryRec168 : LiveRootWorklistActionTy::MarkLiveEntryRec;169 170 addActionToRootEntriesWorkList(Action, ChildEntry, ReferencedBy);171 }172 } break;173 case dwarf::DW_TAG_constant:174 case dwarf::DW_TAG_variable: {175 IsLiveChild = isLiveVariableEntry(ChildEntry, IsLiveParent);176 177 // Keep variable referencing live address.178 if (IsLiveChild) {179 // If variable is in module scope and this module allows ODR180 // deduplication set "TypeTable" placement, otherwise set "" placement181 182 LiveRootWorklistActionTy Action =183 (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable())184 ? LiveRootWorklistActionTy::MarkTypeEntryRec185 : LiveRootWorklistActionTy::MarkLiveEntryRec;186 187 addActionToRootEntriesWorkList(Action, ChildEntry, ReferencedBy);188 }189 } break;190 case dwarf::DW_TAG_base_type: {191 // Always keep base types.192 addActionToRootEntriesWorkList(193 LiveRootWorklistActionTy::MarkSingleLiveEntry, 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 LiveRootWorklistActionTy::MarkSingleLiveEntry, ChildEntry,203 ReferencedBy);204 break;205 }206 207 addActionToRootEntriesWorkList(208 LiveRootWorklistActionTy::MarkSingleTypeEntry, 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(ChildEntry, ReferencedBy, 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(Root.getAction(), Root.getRootEntry(),234 Root.getRootEntry(), InterCUProcessingStarted,235 HasNewInterconnectedCUs)) {236 if (Root.hasReferencedByOtherEntry())237 Dependencies.push_back(Root);238 } else239 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(RootEntry.DieEntry);254 255 UnitEntryPairTy ReferencedByEntry = Root.getReferencedByEntry();256 CompileUnit::DIEInfo &ReferencedByInfo =257 ReferencedByEntry.CU->getDIEInfo(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 for265 // 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.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(Entry.DieEntry);285 CurChild && CurChild->getAbbreviationDeclarationPtr();286 CurChild = Entry.CU->getSiblingEntry(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(Entry.CU->getDIEInfo(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.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(*ParentIdx);346 CompileUnit::DIEInfo &ParentInfo = Entry.CU->getDIEInfo(*ParentIdx);347 348 if (!AreTypeParentsDone && NeedKeepTypeChildren) {349 if (ParentInfo.getKeepTypeChildren())350 AreTypeParentsDone = true;351 else {352 bool AddToWorklist = !isAlreadyMarked(353 ParentInfo, CompileUnit::DieOutputPlacement::TypeTable);354 ParentInfo.setKeepTypeChildren();355 if (AddToWorklist && !isNamespaceLikeEntry(ParentEntry)) {356 addActionToRootEntriesWorkList(357 LiveRootWorklistActionTy::MarkTypeChildrenRec,358 UnitEntryPairTy{Entry.CU, ParentEntry}, std::nullopt);359 }360 }361 }362 363 if (!ArePlainParentsDone && NeedKeepPlainChildren) {364 if (ParentInfo.getKeepPlainChildren())365 ArePlainParentsDone = true;366 else {367 bool AddToWorklist = !isAlreadyMarked(368 ParentInfo, CompileUnit::DieOutputPlacement::PlainDwarf);369 ParentInfo.setKeepPlainChildren();370 if (AddToWorklist && !isNamespaceLikeEntry(ParentEntry)) {371 addActionToRootEntriesWorkList(372 LiveRootWorklistActionTy::MarkLiveChildrenRec,373 UnitEntryPairTy{Entry.CU, ParentEntry}, 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::DieOutputPlacement391getFinalPlacementForEntry(const UnitEntryPairTy &Entry,392 CompileUnit::DieOutputPlacement Placement) {393 assert((Placement != CompileUnit::NotSet) && "Placement is not set");394 CompileUnit::DIEInfo &EntryInfo = Entry.CU->getDIEInfo(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 same401 // 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.DieEntry);436 437 // Calculate final placement placement.438 CompileUnit::DieOutputPlacement Placement = getFinalPlacementForEntry(439 Entry,440 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, 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, 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 DIEs475 // and itself may be subject to move into the artificial type unit.476 // a) Non removable children(like DW_TAG_formal_parameter) should always477 // be cloned. They are placed into the "PlainDwarf" and into the478 // "TypeTable".479 // b) ODR deduplication candidates(type DIEs) children should not be put480 // 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(Entry.DieEntry);485 CurChild && CurChild->getAbbreviationDeclarationPtr();486 CurChild = Entry.CU->getSiblingEntry(CurChild)) {487 CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(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(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, FinalRootEntry, 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(Entry.DieEntry);540 CurChild && CurChild->getAbbreviationDeclarationPtr();541 CurChild = Entry.CU->getSiblingEntry(CurChild)) {542 CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(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, FinalRootEntry, 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(Abbrev->getCode());624 625 // For each DIE attribute...626 for (const auto &AttrSpec : Abbrev->attributes()) {627 DWARFFormValue Val(AttrSpec.Form);628 if (!Val.isFormClass(DWARFFormValue::FC_Reference) ||629 AttrSpec.Attr == dwarf::DW_AT_sibling) {630 DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset,631 Unit.getFormParams());632 continue;633 }634 Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit);635 636 // Resolve reference.637 std::optional<UnitEntryPairTy> RefDie = Entry.CU->resolveDIEReference(638 Val, InterCUProcessingStarted639 ? ResolveInterCUReferencesMode::Resolve640 : ResolveInterCUReferencesMode::AvoidResolving);641 if (!RefDie) {642 Entry.CU->warn("cann't find referenced DIE", 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(RefDie->DieEntry);659 if (!RefInfo.getODRAvailable())660 Action = LiveRootWorklistActionTy::MarkLiveEntryRec;661 else if (RefInfo.getODRAvailable() &&662 llvm::is_contained(getODRAttributes(), AttrSpec.Attr))663 // Note: getODRAttributes does not include DW_AT_containing_type.664 // It should be OK as we do getRootForSpecifiedEntry(). So any containing665 // type would be found as the root for the entry.666 Action = LiveRootWorklistActionTy::MarkTypeEntryRec;667 else if (isLiveAction(Action))668 Action = LiveRootWorklistActionTy::MarkLiveEntryRec;669 else670 Action = LiveRootWorklistActionTy::MarkTypeEntryRec;671 672 if (AttrSpec.Attr == dwarf::DW_AT_import) {673 if (isNamespaceLikeEntry(RefDie->DieEntry)) {674 addActionToRootEntriesWorkList(675 isTypeAction(Action)676 ? LiveRootWorklistActionTy::MarkSingleTypeEntry677 : LiveRootWorklistActionTy::MarkSingleLiveEntry,678 *RefDie, RootEntry);679 continue;680 }681 682 addActionToRootEntriesWorkList(Action, *RefDie, RootEntry);683 continue;684 }685 686 UnitEntryPairTy RootForReferencedDie = getRootForSpecifiedEntry(*RefDie);687 addActionToRootEntriesWorkList(Action, RootForReferencedDie, RootEntry);688 }689 690 return true;691}692 693UnitEntryPairTy694DependencyTracker::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(*ParentIdx);717 if (isNamespaceLikeEntry(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(Entry.DieEntry);728 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(DIE);729 730 if (Info.getTrackLiveness()) {731 const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();732 733 if (!Info.getIsInFunctionScope() &&734 Abbrev->findAttributeIndex(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 this738 // variable's location. The order is important here. We want to always739 // check if the variable has a location expression address. However, we740 // don't want a static variable in a function to force us to keep the741 // enclosing function, unless requested explicitly.742 std::pair<bool, std::optional<int64_t>> LocExprAddrAndRelocAdjustment =743 Entry.CU->getContaingFile().Addresses->getVariableRelocAdjustment(744 DIE, 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(outs(), 8 /* Indent */, DumpOpts);765 }766 767 return true;768}769 770bool DependencyTracker::isLiveSubprogramEntry(const UnitEntryPairTy &Entry) {771 DWARFDie DIE = Entry.CU->getDIE(Entry.DieEntry);772 CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry.DieEntry);773 std::optional<DWARFFormValue> LowPCVal = DIE.find(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(LowPCVal);780 if (!LowPc)781 return false;782 783 Info.setHasAnAddress();784 785 RelocAdjustment =786 Entry.CU->getContaingFile().Addresses->getSubprogramRelocAdjustment(787 DIE, 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);795 if (!HighPc) {796 Entry.CU->warn("function without high_pc. Range will be discarded.",797 &DIE);798 return false;799 }800 801 if (*LowPc > *HighPc) {802 Entry.CU->warn("low_pc greater than high_pc. Range will be discarded.",803 &DIE);804 return false;805 }806 } else if (DIE.getTag() == dwarf::DW_TAG_label) {807 if (Entry.CU->hasLabelAt(*LowPc))808 return false;809 810 // FIXME: dsymutil-classic compat. dsymutil-classic doesn't consider811 // labels that don't fall into the CU's aranges. This is wrong IMO. Debug812 // 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's814 // high_pc.815 if (dwarf::toAddress(Entry.CU->find(Entry.DieEntry, dwarf::DW_AT_high_pc))816 .value_or(UINT64_MAX) <= LowPc)817 return false;818 819 Entry.CU->addLabelLowPc(*LowPc, *RelocAdjustment);820 }821 } else822 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(outs(), 8 /* Indent */, DumpOpts);830 }831 832 if (!Info.getTrackLiveness() || DIE.getTag() == dwarf::DW_TAG_label)833 return true;834 835 Entry.CU->addFunctionRange(*LowPc, *HighPc, *RelocAdjustment);836 return true;837}838