llvm/lib/DWARFLinker/Parallel/DependencyTracker.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "DependencyTracker.h"
  10 #include "llvm/Support/FormatVariadic.h"
  11
  12 using namespace llvm;
  13 using namespace dwarf_linker;
  14 using 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.
  18 struct 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.
  28 void 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
 108 bool 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
 123 void 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
 134 void 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 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, 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 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, 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
 225 bool 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     } else
 239       Res = false;
 240   }
 241
 242   return Res;
 243 }
 244
 245 bool 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 for
 265       // parents of *Root.ReferencedBy.
 266     }
 267   }
 268
 269   return HasNewDependency;
 270 }
 271
 272 void 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
 290 static 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
 302 bool 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
 324 bool isAlreadyMarked(const UnitEntryPairTy &Entry,
 325                      CompileUnit::DieOutputPlacement NewPlacement) {
 326   return isAlreadyMarked(Entry.CU->getDIEInfo(Entry.DieEntry), NewPlacement);
 327 }
 328
 329 void 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.
 390 static CompileUnit::DieOutputPlacement
 391 getFinalPlacementForEntry(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 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
 428 bool 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 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(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
 564 bool 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
 612 bool 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, InterCUProcessingStarted
 639                  ? ResolveInterCUReferencesMode::Resolve
 640                  : 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 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(RefDie->DieEntry)) {
 674         addActionToRootEntriesWorkList(
 675             isTypeAction(Action)
 676                 ? LiveRootWorklistActionTy::MarkSingleTypeEntry
 677                 : 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
 693 UnitEntryPairTy
 694 DependencyTracker::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
 725 bool 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 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, 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
 770 bool 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 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(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   } 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(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 }