| 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 | #include "llvm/Support/SaveAndRestore.h" |
| 12 | |
| 13 | using namespace llvm; |
| 14 | using namespace dwarf_linker; |
| 15 | using 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. |
| 19 | struct BrokenLink { |
| 20 | BrokenLink(DWARFDie Parent, DWARFDie Child, const char *Message) |
| 21 | : Parent(Parent), Child(Child), Message(Message) {} |
| 22 | DWARFDie Parent; |
| 23 | DWARFDie Child; |
| 24 | std::string Message; |
| 25 | }; |
| 26 | |
| 27 | /// Verify the keep chain by looking for DIEs that are kept but who's parent |
| 28 | /// isn't. |
| 29 | void DependencyTracker::verifyKeepChain() { |
| 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 | |
| 109 | static 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 | |
| 121 | void DependencyTracker::collectLiveRoots() { |
| 122 | RootEntriesWorkList.clear(); |
| 123 | |
| 124 | // Search for live root DIEs. |
| 125 | CompileUnit::DIEInfo &CUInfo = CU.getDIEInfo(Entry: CU.getDebugInfoEntry(Index: 0)); |
| 126 | CUInfo.setPlacement(CompileUnit::PlainDwarf); |
| 127 | collectRootsToKeep(Entry: UnitEntryPairTy{&CU, CU.getDebugInfoEntry(Index: 0)}, |
| 128 | ReferencedBy: std::nullopt, IsLiveParent: false); |
| 129 | } |
| 130 | |
| 131 | bool DependencyTracker::resolveDependenciesAndMarkLiveness( |
| 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 | |
| 147 | void DependencyTracker::addActionToRootEntriesWorkList( |
| 148 | LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry, |
| 149 | std::optional<UnitEntryPairTy> ReferencedBy, |
| 150 | const DWARFDebugInfoEntry *ReferencedTypeDieEntry) { |
| 151 | if (ReferencedBy) { |
| 152 | RootEntriesWorkList.emplace_back(Args&: Action, Args: Entry, Args&: *ReferencedBy, |
| 153 | Args&: ReferencedTypeDieEntry); |
| 154 | return; |
| 155 | } |
| 156 | |
| 157 | RootEntriesWorkList.emplace_back(Args&: Action, Args: Entry); |
| 158 | } |
| 159 | |
| 160 | void DependencyTracker::collectRootsToKeep( |
| 161 | const UnitEntryPairTy &Entry, std::optional<UnitEntryPairTy> ReferencedBy, |
| 162 | bool IsLiveParent) { |
| 163 | for (const DWARFDebugInfoEntry *CurChild = |
| 164 | Entry.CU->getFirstChildEntry(Die: Entry.DieEntry); |
| 165 | CurChild && CurChild->getAbbreviationDeclarationPtr(); |
| 166 | CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) { |
| 167 | UnitEntryPairTy ChildEntry(Entry.CU, CurChild); |
| 168 | CompileUnit::DIEInfo &ChildInfo = Entry.CU->getDIEInfo(Entry: CurChild); |
| 169 | |
| 170 | bool IsLiveChild = false; |
| 171 | |
| 172 | switch (CurChild->getTag()) { |
| 173 | case dwarf::DW_TAG_label: { |
| 174 | IsLiveChild = isLiveSubprogramEntry(Entry: ChildEntry); |
| 175 | |
| 176 | // Keep label referencing live address. |
| 177 | // Keep label which is child of live parent entry. |
| 178 | if (IsLiveChild || (IsLiveParent && ChildInfo.getHasAnAddress())) { |
| 179 | addActionToRootEntriesWorkList( |
| 180 | Action: LiveRootWorklistActionTy::MarkLiveEntryRec, Entry: ChildEntry, |
| 181 | ReferencedBy); |
| 182 | } |
| 183 | } break; |
| 184 | case dwarf::DW_TAG_subprogram: { |
| 185 | IsLiveChild = isLiveSubprogramEntry(Entry: 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 |
| 191 | LiveRootWorklistActionTy Action = |
| 192 | (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable()) |
| 193 | ? LiveRootWorklistActionTy::MarkTypeEntryRec |
| 194 | : LiveRootWorklistActionTy::MarkLiveEntryRec; |
| 195 | |
| 196 | addActionToRootEntriesWorkList(Action, Entry: ChildEntry, ReferencedBy); |
| 197 | } |
| 198 | } break; |
| 199 | case dwarf::DW_TAG_constant: |
| 200 | case dwarf::DW_TAG_variable: { |
| 201 | IsLiveChild = isLiveVariableEntry(Entry: 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 | |
| 208 | LiveRootWorklistActionTy Action = |
| 209 | (ChildInfo.getIsInMouduleScope() && ChildInfo.getODRAvailable()) |
| 210 | ? LiveRootWorklistActionTy::MarkTypeEntryRec |
| 211 | : LiveRootWorklistActionTy::MarkLiveEntryRec; |
| 212 | |
| 213 | addActionToRootEntriesWorkList(Action, Entry: ChildEntry, ReferencedBy); |
| 214 | } |
| 215 | } break; |
| 216 | case dwarf::DW_TAG_base_type: { |
| 217 | // Always keep base types. |
| 218 | addActionToRootEntriesWorkList( |
| 219 | Action: LiveRootWorklistActionTy::MarkSingleLiveEntry, Entry: ChildEntry, |
| 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) { |
| 227 | addActionToRootEntriesWorkList( |
| 228 | Action: LiveRootWorklistActionTy::MarkSingleLiveEntry, Entry: ChildEntry, |
| 229 | ReferencedBy); |
| 230 | break; |
| 231 | } |
| 232 | |
| 233 | addActionToRootEntriesWorkList( |
| 234 | Action: LiveRootWorklistActionTy::MarkSingleTypeEntry, Entry: ChildEntry, |
| 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: Entry.DieEntry) && |
| 247 | dwarf::isType(T: CurChild->getTag())) { |
| 248 | addActionToRootEntriesWorkList( |
| 249 | Action: LiveRootWorklistActionTy::MarkTypeEntryRec, Entry: ChildEntry, |
| 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(T: CurChild->getTag()) && |
| 266 | dwarf::toUnsigned(V: Entry.CU->find(Die: CurChild, Attrs: dwarf::DW_AT_declaration), |
| 267 | Default: 0)) { |
| 268 | addActionToRootEntriesWorkList( |
| 269 | Action: LiveRootWorklistActionTy::MarkTypeEntryRec, Entry: ChildEntry, |
| 270 | ReferencedBy); |
| 271 | } |
| 272 | break; |
| 273 | } |
| 274 | |
| 275 | collectRootsToKeep(Entry: ChildEntry, ReferencedBy, IsLiveParent: IsLiveChild || IsLiveParent); |
| 276 | } |
| 277 | } |
| 278 | |
| 279 | bool DependencyTracker::markCollectedLiveRootsAsKept( |
| 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 | |
| 287 | if (markDIEEntryAsKeptRec(Action: Root.getAction(), RootEntry: Root.getRootEntry(), |
| 288 | Entry: Root.getRootEntry(), InterCUProcessingStarted, |
| 289 | HasNewInterconnectedCUs)) { |
| 290 | if (Root.hasReferencedByOtherEntry()) |
| 291 | Dependencies.push_back(Elt: Root); |
| 292 | } else |
| 293 | Res = false; |
| 294 | } |
| 295 | |
| 296 | return Res; |
| 297 | } |
| 298 | |
| 299 | void DependencyTracker::recordSubtreeDependencies( |
| 300 | LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, |
| 301 | const UnitEntryPairTy &Entry) { |
| 302 | SubtreeDependencyRefs.push_back(Elt: {.Subtree: Entry, .Action: Action, .ReferencedBy: RootEntry}); |
| 303 | } |
| 304 | |
| 305 | void DependencyTracker::materializeSubtreeSummaries() { |
| 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. |
| 313 | const SubtreeDependencyRefTy Ref = SubtreeDependencyRefs[Idx]; |
| 314 | SubtreeDependenciesKeyTy Key{Ref.Subtree.CU, Ref.Subtree.DieEntry, |
| 315 | Ref.Action}; |
| 316 | if (SubtreeSummaries.contains(Val: Key)) |
| 317 | continue; |
| 318 | |
| 319 | // Collected separately so that growing the map cannot invalidate the sink. |
| 320 | SubtreeDependenciesTy SubtreeDeps; |
| 321 | { |
| 322 | SaveAndRestore<SubtreeDependenciesTy *> CollectInto(CollectedSubtreeDeps, |
| 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 | Action: Ref.Action, RootEntry: Ref.ReferencedBy, Entry: Ref.Subtree, |
| 331 | InterCUProcessingStarted: InterCUProcessingWasStarted, HasNewInterconnectedCUs, |
| 332 | Kind: TreeWalkKindTy::RecordSubtreeDeps); |
| 333 | assert(Res && !HasNewInterconnectedCUs && "record-deps-only walk failed" ); |
| 334 | } |
| 335 | |
| 336 | SubtreeSummaries[Key] = std::move(SubtreeDeps); |
| 337 | } |
| 338 | |
| 339 | MaterializedRefs = SubtreeDependencyRefs.size(); |
| 340 | } |
| 341 | |
| 342 | bool DependencyTracker::demoteIfIncomplete( |
| 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(Entry: ReferencedDieEntry); |
| 355 | CompileUnit::DIEInfo &ReferencedByInfo = |
| 356 | ReferencedBy.CU->getDIEInfo(Entry: 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 | |
| 369 | bool DependencyTracker::applySubtreeSummaries() { |
| 370 | bool HasNewDependency = false; |
| 371 | for (const SubtreeDependencyRefTy &Ref : SubtreeDependencyRefs) { |
| 372 | CompileUnit::DIEInfo &ReferencedByInfo = |
| 373 | Ref.ReferencedBy.CU->getDIEInfo(Entry: 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(Val: 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) { |
| 385 | if (demoteIfIncomplete(Root: Dep.Root, ReferencedTypeDieEntry: Dep.ReferencedTypeDieEntry, |
| 386 | ReferencedBy: Ref.ReferencedBy)) { |
| 387 | HasNewDependency = true; |
| 388 | break; |
| 389 | } |
| 390 | } |
| 391 | } |
| 392 | |
| 393 | return HasNewDependency; |
| 394 | } |
| 395 | |
| 396 | bool DependencyTracker::updateDependenciesCompleteness() { |
| 397 | materializeSubtreeSummaries(); |
| 398 | |
| 399 | bool HasNewDependency = false; |
| 400 | for (LiveRootWorklistItemTy &Root : Dependencies) { |
| 401 | assert(Root.hasReferencedByOtherEntry() && |
| 402 | "Root entry without dependency inside the dependencies list" ); |
| 403 | |
| 404 | if (demoteIfIncomplete(Root: Root.getRootEntry(), |
| 405 | ReferencedTypeDieEntry: Root.getReferencedTypeDieEntry(), |
| 406 | ReferencedBy: Root.getReferencedByEntry())) |
| 407 | HasNewDependency = true; |
| 408 | } |
| 409 | |
| 410 | if (applySubtreeSummaries()) |
| 411 | HasNewDependency = true; |
| 412 | |
| 413 | return HasNewDependency; |
| 414 | } |
| 415 | |
| 416 | void DependencyTracker::setPlainDwarfPlacementRec( |
| 417 | const UnitEntryPairTy &Entry) { |
| 418 | CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry); |
| 419 | if (Info.getPlacement() == CompileUnit::PlainDwarf && |
| 420 | !Info.getKeepTypeChildren()) |
| 421 | return; |
| 422 | |
| 423 | Info.setPlacement(CompileUnit::PlainDwarf); |
| 424 | Info.unsetKeepTypeChildren(); |
| 425 | markParentsAsKeepingChildren(Entry); |
| 426 | |
| 427 | for (const DWARFDebugInfoEntry *CurChild = |
| 428 | Entry.CU->getFirstChildEntry(Die: Entry.DieEntry); |
| 429 | CurChild && CurChild->getAbbreviationDeclarationPtr(); |
| 430 | CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) |
| 431 | setPlainDwarfPlacementRec(UnitEntryPairTy{Entry.CU, CurChild}); |
| 432 | } |
| 433 | |
| 434 | bool isAlreadyMarked(const CompileUnit::DIEInfo &Info, |
| 435 | CompileUnit::DieOutputPlacement NewPlacement) { |
| 436 | if (!Info.getKeep()) |
| 437 | return false; |
| 438 | |
| 439 | switch (NewPlacement) { |
| 440 | case CompileUnit::TypeTable: |
| 441 | return Info.needToPlaceInTypeTable(); |
| 442 | |
| 443 | case CompileUnit::PlainDwarf: |
| 444 | return Info.needToKeepInPlainDwarf(); |
| 445 | |
| 446 | case CompileUnit::Both: |
| 447 | return Info.needToPlaceInTypeTable() && Info.needToKeepInPlainDwarf(); |
| 448 | |
| 449 | case CompileUnit::NotSet: |
| 450 | llvm_unreachable("Unset placement type is specified." ); |
| 451 | }; |
| 452 | |
| 453 | llvm_unreachable("Unknown CompileUnit::DieOutputPlacement enum" ); |
| 454 | } |
| 455 | |
| 456 | bool isAlreadyMarked(const UnitEntryPairTy &Entry, |
| 457 | CompileUnit::DieOutputPlacement NewPlacement) { |
| 458 | return isAlreadyMarked(Info: Entry.CU->getDIEInfo(Entry: Entry.DieEntry), NewPlacement); |
| 459 | } |
| 460 | |
| 461 | void DependencyTracker::keepWithParent(const UnitEntryPairTy &RootEntry, |
| 462 | const UnitEntryPairTy &Child, |
| 463 | TreeWalkKindTy Kind) { |
| 464 | if (recordsDepsOnly(Kind) || |
| 465 | !Child.CU->getDIEInfo(Entry: 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. |
| 471 | addActionToRootEntriesWorkList(Action: LiveRootWorklistActionTy::MarkLiveEntryRec, |
| 472 | Entry: Child, ReferencedBy: RootEntry); |
| 473 | } |
| 474 | |
| 475 | void DependencyTracker::markParentsAsKeepingChildren( |
| 476 | const UnitEntryPairTy &Entry) { |
| 477 | if (Entry.DieEntry->getAbbreviationDeclarationPtr() == nullptr) |
| 478 | return; |
| 479 | |
| 480 | CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: 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(Index: *ParentIdx); |
| 492 | CompileUnit::DIEInfo &ParentInfo = Entry.CU->getDIEInfo(Idx: *ParentIdx); |
| 493 | |
| 494 | if (!AreTypeParentsDone && NeedKeepTypeChildren) { |
| 495 | if (ParentInfo.getKeepTypeChildren()) |
| 496 | AreTypeParentsDone = true; |
| 497 | else { |
| 498 | bool AddToWorklist = !isAlreadyMarked( |
| 499 | Info: ParentInfo, NewPlacement: CompileUnit::DieOutputPlacement::TypeTable); |
| 500 | ParentInfo.setKeepTypeChildren(); |
| 501 | if (AddToWorklist && !isNamespaceLikeEntry(Entry: ParentEntry)) { |
| 502 | addActionToRootEntriesWorkList( |
| 503 | Action: LiveRootWorklistActionTy::MarkTypeChildrenRec, |
| 504 | Entry: UnitEntryPairTy{Entry.CU, ParentEntry}, ReferencedBy: std::nullopt); |
| 505 | } |
| 506 | } |
| 507 | } |
| 508 | |
| 509 | if (!ArePlainParentsDone && NeedKeepPlainChildren) { |
| 510 | if (ParentInfo.getKeepPlainChildren()) |
| 511 | ArePlainParentsDone = true; |
| 512 | else { |
| 513 | bool AddToWorklist = !isAlreadyMarked( |
| 514 | Info: ParentInfo, NewPlacement: CompileUnit::DieOutputPlacement::PlainDwarf); |
| 515 | ParentInfo.setKeepPlainChildren(); |
| 516 | if (AddToWorklist && !isNamespaceLikeEntry(Entry: ParentEntry)) { |
| 517 | addActionToRootEntriesWorkList( |
| 518 | Action: LiveRootWorklistActionTy::MarkLiveChildrenRec, |
| 519 | Entry: UnitEntryPairTy{Entry.CU, ParentEntry}, ReferencedBy: std::nullopt); |
| 520 | } |
| 521 | } |
| 522 | } |
| 523 | |
| 524 | if (AreTypeParentsDone && ArePlainParentsDone) |
| 525 | break; |
| 526 | |
| 527 | ParentIdx = ParentEntry->getParentIdx(); |
| 528 | } |
| 529 | } |
| 530 | |
| 531 | namespace { |
| 532 | struct FinalPlacement { |
| 533 | CompileUnit::DieOutputPlacement Placement; |
| 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. |
| 561 | static FinalPlacement |
| 562 | getFinalPlacementForEntry(const UnitEntryPairTy &Entry, |
| 563 | CompileUnit::DieOutputPlacement Placement) { |
| 564 | assert((Placement != CompileUnit::NotSet) && "Placement is not set" ); |
| 565 | CompileUnit::DIEInfo &EntryInfo = Entry.CU->getDIEInfo(Entry: Entry.DieEntry); |
| 566 | |
| 567 | if (!EntryInfo.getODRAvailable()) |
| 568 | return {.Placement: CompileUnit::PlainDwarf, .Mode: 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 | V: Entry.CU->find(Die: Entry.DieEntry, Attrs: dwarf::DW_AT_declaration), Default: 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(Index: *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 {.Placement: CompileUnit::TypeTable, .Mode: FinalPlacement::Overwrite}; |
| 595 | } |
| 596 | |
| 597 | // A live (PlainDwarf) mark pins the variable to plain DWARF. |
| 598 | if (Placement == CompileUnit::PlainDwarf || Placement == CompileUnit::Both) |
| 599 | return {.Placement: CompileUnit::PlainDwarf, .Mode: 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: Placement, .Mode: FinalPlacement::JoinVariable}; |
| 604 | } |
| 605 | |
| 606 | return {.Placement: Placement, .Mode: FinalPlacement::Join}; |
| 607 | } |
| 608 | |
| 609 | bool DependencyTracker::markDIEEntryAsKeptRec( |
| 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: Entry.DieEntry); |
| 617 | |
| 618 | // Calculate final placement. |
| 619 | FinalPlacement Final = getFinalPlacementForEntry( |
| 620 | Entry, |
| 621 | Placement: isLiveAction(Action) ? CompileUnit::PlainDwarf : CompileUnit::TypeTable); |
| 622 | CompileUnit::DieOutputPlacement Placement = Final.Placement; |
| 623 | assert((Info.getODRAvailable() || isLiveAction(Action) || |
| 624 | Placement == CompileUnit::PlainDwarf) && |
| 625 | "Wrong kind of placement for ODR unavailable entry" ); |
| 626 | |
| 627 | if (!recordsDepsOnly(Kind) && !isChildrenAction(Action) && |
| 628 | isAlreadyMarked(Entry, NewPlacement: 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. |
| 659 | markParentsAsKeepingChildren(Entry); |
| 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 |
| 670 | ? TreeWalkKindTy::RecordNestedSubprogramDeps |
| 671 | : Kind; |
| 672 | |
| 673 | // Analyse referenced DIEs. |
| 674 | bool Res = true; |
| 675 | if (!maybeAddReferencedRoots(Action, RootEntry: FinalRootEntry, Entry, |
| 676 | InterCUProcessingStarted, |
| 677 | HasNewInterconnectedCUs, Kind: 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(Die: Entry.DieEntry); |
| 699 | CurChild && CurChild->getAbbreviationDeclarationPtr(); |
| 700 | CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) { |
| 701 | CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(Entry: 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(RootEntry: FinalRootEntry, Child: 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(DIEEntry: 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 | |
| 745 | if (!markDIEEntryAsKeptRec( |
| 746 | Action, RootEntry: FinalRootEntry, Entry: UnitEntryPairTy{Entry.CU, CurChild}, |
| 747 | InterCUProcessingStarted, HasNewInterconnectedCUs, Kind: FinalKind)) |
| 748 | Res = false; |
| 749 | } |
| 750 | |
| 751 | return Res; |
| 752 | } |
| 753 | |
| 754 | // Recursively process children. |
| 755 | for (const DWARFDebugInfoEntry *CurChild = |
| 756 | Entry.CU->getFirstChildEntry(Die: Entry.DieEntry); |
| 757 | CurChild && CurChild->getAbbreviationDeclarationPtr(); |
| 758 | CurChild = Entry.CU->getSiblingEntry(Die: CurChild)) { |
| 759 | CompileUnit::DIEInfo ChildInfo = Entry.CU->getDIEInfo(Entry: 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(RootEntry: FinalRootEntry, Child: UnitEntryPairTy{Entry.CU, CurChild}, |
| 767 | Kind); |
| 768 | continue; |
| 769 | } |
| 770 | } break; |
| 771 | default: |
| 772 | break; // Nothing to do. |
| 773 | }; |
| 774 | |
| 775 | if (!markDIEEntryAsKeptRec( |
| 776 | Action, RootEntry: FinalRootEntry, Entry: UnitEntryPairTy{Entry.CU, CurChild}, |
| 777 | InterCUProcessingStarted, HasNewInterconnectedCUs, Kind: FinalKind)) |
| 778 | Res = false; |
| 779 | } |
| 780 | |
| 781 | return Res; |
| 782 | } |
| 783 | |
| 784 | bool DependencyTracker::isTypeTableCandidate( |
| 785 | const DWARFDebugInfoEntry *DIEEntry) { |
| 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 | |
| 832 | bool DependencyTracker::maybeAddReferencedRoots( |
| 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) { |
| 848 | case TreeWalkKindTy::MarkTree: |
| 849 | addActionToRootEntriesWorkList(Action: RootAction, Entry: Root, ReferencedBy: RootEntry, |
| 850 | ReferencedTypeDieEntry); |
| 851 | return; |
| 852 | |
| 853 | case TreeWalkKindTy::RecordSubtreeDeps: |
| 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 | Elt: {.Action: RootAction, .Root: Root, .ReferencedTypeDieEntry: ReferencedTypeDieEntry}); |
| 859 | return; |
| 860 | |
| 861 | case TreeWalkKindTy::RecordNestedSubprogramDeps: |
| 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(Args&: RootAction, Args: Root, Args: RootEntry, |
| 865 | Args&: 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(Value: Abbrev->getCode()); |
| 875 | |
| 876 | // For each DIE attribute... |
| 877 | for (const auto &AttrSpec : Abbrev->attributes()) { |
| 878 | DWARFFormValue Val(AttrSpec.Form); |
| 879 | if (!Val.isFormClass(FC: DWARFFormValue::FC_Reference) || |
| 880 | AttrSpec.Attr == dwarf::DW_AT_sibling) { |
| 881 | DWARFFormValue::skipValue(Form: AttrSpec.Form, DebugInfoData: Data, OffsetPtr: &Offset, |
| 882 | FormParams: Unit.getFormParams()); |
| 883 | continue; |
| 884 | } |
| 885 | Val.extractValue(Data, OffsetPtr: &Offset, FormParams: Unit.getFormParams(), U: &Unit); |
| 886 | |
| 887 | // Resolve reference. |
| 888 | std::optional<UnitEntryPairTy> RefDie = Entry.CU->resolveDIEReference( |
| 889 | RefValue: Val, CanResolveInterCUReferences: InterCUProcessingStarted |
| 890 | ? ResolveInterCUReferencesMode::Resolve |
| 891 | : ResolveInterCUReferencesMode::AvoidResolving); |
| 892 | if (!RefDie) { |
| 893 | Entry.CU->warn(Warning: "could not find referenced DIE" , DieEntry: 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(Entry: RefDie->DieEntry); |
| 918 | if (!RefInfo.getODRAvailable()) |
| 919 | Action = LiveRootWorklistActionTy::MarkLiveEntryRec; |
| 920 | else if (RefInfo.getODRAvailable() && |
| 921 | llvm::is_contained(Range: getODRAttributes(), Element: 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. |
| 925 | Action = LiveRootWorklistActionTy::MarkTypeEntryRec; |
| 926 | else if (isLiveAction(Action)) |
| 927 | Action = LiveRootWorklistActionTy::MarkLiveEntryRec; |
| 928 | else |
| 929 | Action = LiveRootWorklistActionTy::MarkTypeEntryRec; |
| 930 | |
| 931 | if (AttrSpec.Attr == dwarf::DW_AT_import) { |
| 932 | if (isNamespaceLikeEntry(Entry: RefDie->DieEntry)) { |
| 933 | AddRoot(isTypeAction(Action) |
| 934 | ? LiveRootWorklistActionTy::MarkSingleTypeEntry |
| 935 | : LiveRootWorklistActionTy::MarkSingleLiveEntry, |
| 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(Entry: *RefDie); |
| 949 | AddRoot(Action, RootForReferencedDie, RefDie->DieEntry); |
| 950 | } |
| 951 | |
| 952 | return true; |
| 953 | } |
| 954 | |
| 955 | UnitEntryPairTy |
| 956 | DependencyTracker::getRootForSpecifiedEntry(UnitEntryPairTy Entry) { |
| 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(Index: *ParentIdx); |
| 979 | if (isNamespaceLikeEntry(Entry: ParentEntry)) |
| 980 | break; |
| 981 | Result.DieEntry = ParentEntry; |
| 982 | } while (true); |
| 983 | |
| 984 | return Result; |
| 985 | } |
| 986 | |
| 987 | static 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(OS&: outs(), /*Indent=*/indent: 8, DumpOpts); |
| 995 | } |
| 996 | |
| 997 | bool DependencyTracker::isLiveVariableEntry(const UnitEntryPairTy &Entry, |
| 998 | bool IsLiveParent) { |
| 999 | DWARFDie DIE = Entry.CU->getDIE(Die: Entry.DieEntry); |
| 1000 | CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Die: DIE); |
| 1001 | |
| 1002 | if (Info.getTrackLiveness()) { |
| 1003 | const auto *Abbrev = DIE.getAbbreviationDeclarationPtr(); |
| 1004 | |
| 1005 | if (!Info.getIsInFunctionScope() && |
| 1006 | Abbrev->findAttributeIndex(attr: 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, Verbose: 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, Kind: "variable" , Verbose: Entry.CU->getGlobalData().getOptions().Verbose); |
| 1034 | |
| 1035 | return true; |
| 1036 | } |
| 1037 | |
| 1038 | bool DependencyTracker::isLiveSubprogramEntry(const UnitEntryPairTy &Entry) { |
| 1039 | DWARFDie DIE = Entry.CU->getDIE(Die: Entry.DieEntry); |
| 1040 | CompileUnit::DIEInfo &Info = Entry.CU->getDIEInfo(Entry: Entry.DieEntry); |
| 1041 | std::optional<DWARFFormValue> LowPCVal = DIE.find(Attr: 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(V: 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: *LowPc); |
| 1064 | if (!HighPc) { |
| 1065 | Entry.CU->warn(Warning: "function without high_pc. Range will be discarded." , |
| 1066 | DIE: &DIE); |
| 1067 | return false; |
| 1068 | } |
| 1069 | |
| 1070 | if (*LowPc > *HighPc) { |
| 1071 | Entry.CU->warn(Warning: "low_pc greater than high_pc. Range will be discarded." , |
| 1072 | DIE: &DIE); |
| 1073 | return false; |
| 1074 | } |
| 1075 | } else if (DIE.getTag() == dwarf::DW_TAG_label) { |
| 1076 | if (Entry.CU->hasLabelAt(Addr: *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(V: Entry.CU->find(Die: Entry.DieEntry, Attrs: 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 | V: Entry.CU->getOrigUnit().getUnitDIE().find(Attr: dwarf::DW_AT_language), Default: 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(Addr: *LowPc)) |
| 1098 | Entry.CU->addFunctionRange(LowPC: Range->LowPC, HighPC: Range->HighPC, |
| 1099 | PCOffset: *RelocAdjustment); |
| 1100 | } |
| 1101 | |
| 1102 | Entry.CU->addLabelLowPc(LabelLowPc: *LowPc, PcOffset: *RelocAdjustment); |
| 1103 | } |
| 1104 | } else |
| 1105 | Info.setHasAnAddress(); |
| 1106 | |
| 1107 | dumpKeptDIE(DIE, Kind: "subprogram" , Verbose); |
| 1108 | |
| 1109 | if (!Info.getTrackLiveness() || DIE.getTag() == dwarf::DW_TAG_label) |
| 1110 | return true; |
| 1111 | |
| 1112 | Entry.CU->addFunctionRange( |
| 1113 | LowPC: *LowPc, |
| 1114 | HighPC: Entry.CU->getContainingFile().Addresses->constrainCodeRangeHighPC( |
| 1115 | LowPC: *LowPc, HighPC: *HighPc, Adjustment: *RelocAdjustment), |
| 1116 | PCOffset: *RelocAdjustment); |
| 1117 | return true; |
| 1118 | } |
| 1119 | |