llvm/lib/DWARFLinkerParallel/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 namespace llvm {
  13 namespace dwarflinker_parallel {
  14
  15 #ifndef NDEBUG
  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) : Parent(Parent), Child(Child) {}
  20   DWARFDie Parent;
  21   DWARFDie Child;
  22 };
  23
  24 /// Verify the keep chain by looking for DIEs that are kept but who's parent
  25 /// isn't.
  26 void DependencyTracker::verifyKeepChain(CompileUnit &CU) {
  27   SmallVector<DWARFDie> Worklist;
  28   Worklist.push_back(CU.getOrigUnit().getUnitDIE());
  29
  30   // List of broken links.
  31   SmallVector<BrokenLink> BrokenLinks;
  32
  33   while (!Worklist.empty()) {
  34     const DWARFDie Current = Worklist.back();
  35     Worklist.pop_back();
  36
  37     if (!Current.isValid())
  38       continue;
  39
  40     const bool CurrentDieIsKept = CU.getDIEInfo(Current).getKeep() ||
  41                                   CU.getDIEInfo(Current).getKeepChildren();
  42
  43     for (DWARFDie Child : reverse(Current.children())) {
  44       Worklist.push_back(Child);
  45
  46       const bool ChildDieIsKept = CU.getDIEInfo(Child).getKeep() ||
  47                                   CU.getDIEInfo(Child).getKeepChildren();
  48       if (!CurrentDieIsKept && ChildDieIsKept)
  49         BrokenLinks.emplace_back(Current, Child);
  50     }
  51   }
  52
  53   if (!BrokenLinks.empty()) {
  54     for (BrokenLink Link : BrokenLinks) {
  55       WithColor::error() << formatv(
  56           "Found invalid link in keep chain between {0:x} and {1:x}\n",
  57           Link.Parent.getOffset(), Link.Child.getOffset());
  58
  59       errs() << "Parent:";
  60       Link.Parent.dump(errs(), 0, {});
  61       CU.getDIEInfo(Link.Parent).dump();
  62
  63       errs() << "Child:";
  64       Link.Child.dump(errs(), 2, {});
  65       CU.getDIEInfo(Link.Child).dump();
  66     }
  67     report_fatal_error("invalid keep chain");
  68   }
  69 }
  70 #endif
  71
  72 bool DependencyTracker::resolveDependenciesAndMarkLiveness(CompileUnit &CU) {
  73   // We do not track liveness inside Clang modules. We also do not track
  74   // liveness if UpdateIndexTablesOnly is requested.
  75   TrackLiveness = !(CU.isClangModule() ||
  76                     CU.getGlobalData().getOptions().UpdateIndexTablesOnly);
  77   RootEntriesWorkList.clear();
  78
  79   // Search for live root DIEs.
  80   collectRootsToKeep(CU, CU.getDebugInfoEntry(0));
  81
  82   // Mark live DIEs as kept.
  83   return markLiveRootsAsKept();
  84 }
  85
  86 void DependencyTracker::collectRootsToKeep(CompileUnit &CU,
  87                                            const DWARFDebugInfoEntry *Entry) {
  88   if (!TrackLiveness) {
  89     addItemToWorklist(CU, Entry);
  90     return;
  91   }
  92
  93   switch (Entry->getTag()) {
  94   case dwarf::DW_TAG_subprogram:
  95   case dwarf::DW_TAG_label:
  96     if (isLiveSubprogramEntry(CU, Entry)) {
  97       addItemToWorklist(CU, Entry);
  98       break;
  99     }
 100     [[fallthrough]];
 101   case dwarf::DW_TAG_compile_unit:
 102   case dwarf::DW_TAG_namespace:
 103   case dwarf::DW_TAG_module:
 104   case dwarf::DW_TAG_lexical_block: {
 105     for (const DWARFDebugInfoEntry *CurChild = CU.getFirstChildEntry(Entry);
 106          CurChild && CurChild->getAbbreviationDeclarationPtr();
 107          CurChild = CU.getSiblingEntry(CurChild))
 108       collectRootsToKeep(CU, CurChild);
 109   } break;
 110   case dwarf::DW_TAG_constant:
 111   case dwarf::DW_TAG_variable: {
 112     if (isLiveVariableEntry(CU, Entry))
 113       addItemToWorklist(CU, Entry);
 114   } break;
 115   case dwarf::DW_TAG_base_type: {
 116     addItemToWorklist(CU, Entry);
 117   } break;
 118   case dwarf::DW_TAG_imported_module:
 119   case dwarf::DW_TAG_imported_declaration:
 120   case dwarf::DW_TAG_imported_unit: {
 121     addItemToWorklist(CU, Entry);
 122   } break;
 123   default:
 124     // Nothing to do.
 125     break;
 126   }
 127 }
 128
 129 bool DependencyTracker::markLiveRootsAsKept() {
 130   bool Res = true;
 131
 132   while (!RootEntriesWorkList.empty()) {
 133     RootEntryTy CurrentItem = RootEntriesWorkList.pop_back_val();
 134
 135     if (!markDIEEntryAsKeptRec(CurrentItem, CurrentItem.CU,
 136                                CurrentItem.RootEntry))
 137       Res = false;
 138   }
 139
 140   return Res;
 141 }
 142
 143 bool DependencyTracker::markDIEEntryAsKeptRec(
 144     const RootEntryTy &RootItem, CompileUnit &CU,
 145     const DWARFDebugInfoEntry *Entry) {
 146   if (Entry->getAbbreviationDeclarationPtr() == nullptr)
 147     return true;
 148
 149   CompileUnit::DIEInfo &Info = CU.getDIEInfo(Entry);
 150
 151   if (Info.getKeep())
 152     return true;
 153
 154   // Mark parents as 'KeepChildren'.
 155   std::optional<uint32_t> ParentIdx = Entry->getParentIdx();
 156   while (ParentIdx) {
 157     const DWARFDebugInfoEntry *ParentEntry = CU.getDebugInfoEntry(*ParentIdx);
 158     CompileUnit::DIEInfo &ParentInfo = CU.getDIEInfo(*ParentIdx);
 159     if (ParentInfo.getKeepChildren())
 160       break;
 161     ParentInfo.setKeepChildren();
 162     ParentIdx = ParentEntry->getParentIdx();
 163   }
 164
 165   // Mark current DIE as kept.
 166   Info.setKeep();
 167   setDIEPlacementAndTypename(Info);
 168
 169   // Set liveness information.
 170   switch (Entry->getTag()) {
 171   case dwarf::DW_TAG_constant:
 172   case dwarf::DW_TAG_variable: {
 173     isLiveVariableEntry(CU, Entry);
 174   } break;
 175   case dwarf::DW_TAG_subprogram:
 176   case dwarf::DW_TAG_label: {
 177     isLiveSubprogramEntry(CU, Entry);
 178   } break;
 179   default:
 180     // Nothing to do.
 181     break;
 182   }
 183
 184   // Analyse referenced DIEs.
 185   bool Res = true;
 186   if (!maybeAddReferencedRoots(RootItem, CU, Entry))
 187     Res = false;
 188
 189   // Navigate children.
 190   for (const DWARFDebugInfoEntry *CurChild = CU.getFirstChildEntry(Entry);
 191        CurChild && CurChild->getAbbreviationDeclarationPtr();
 192        CurChild = CU.getSiblingEntry(CurChild)) {
 193     if (!markDIEEntryAsKeptRec(RootItem, CU, CurChild))
 194       Res = false;
 195   }
 196
 197   return Res;
 198 }
 199
 200 bool DependencyTracker::maybeAddReferencedRoots(
 201     const RootEntryTy &RootItem, CompileUnit &CU,
 202     const DWARFDebugInfoEntry *Entry) {
 203   const auto *Abbrev = Entry->getAbbreviationDeclarationPtr();
 204   if (Abbrev == nullptr)
 205     return true;
 206
 207   DWARFUnit &Unit = CU.getOrigUnit();
 208   DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
 209   uint64_t Offset = Entry->getOffset() + getULEB128Size(Abbrev->getCode());
 210
 211   // For each DIE attribute...
 212   for (const auto &AttrSpec : Abbrev->attributes()) {
 213     DWARFFormValue Val(AttrSpec.Form);
 214     if (!Val.isFormClass(DWARFFormValue::FC_Reference) ||
 215         AttrSpec.Attr == dwarf::DW_AT_sibling) {
 216       DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset,
 217                                 Unit.getFormParams());
 218       continue;
 219     }
 220     Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit);
 221
 222     // Resolve reference.
 223     std::optional<std::pair<CompileUnit *, uint32_t>> RefDie =
 224         CU.resolveDIEReference(
 225             Val, Context.InterCUProcessingStarted
 226                      ? ResolveInterCUReferencesMode::Resolve
 227                      : ResolveInterCUReferencesMode::AvoidResolving);
 228     if (!RefDie) {
 229       CU.warn("cann't find referenced DIE", Entry);
 230       continue;
 231     }
 232
 233     if (RefDie->second == 0) {
 234       // Delay resolving reference.
 235       RefDie->first->setInterconnectedCU();
 236       CU.setInterconnectedCU();
 237       Context.HasNewInterconnectedCUs = true;
 238       return false;
 239     }
 240
 241     assert(CU.getUniqueID() == RefDie->first->getUniqueID() ||
 242            Context.InterCUProcessingStarted);
 243
 244     addItemToWorklist(*RefDie->first,
 245                       RefDie->first->getDebugInfoEntry(RefDie->second));
 246   }
 247
 248   return true;
 249 }
 250
 251 // Returns true if the specified DIE type allows removing children.
 252 static bool childrenCanBeRemoved(uint32_t Tag) {
 253   switch (Tag) {
 254   default:
 255     return true;
 256   case dwarf::DW_TAG_class_type:
 257   case dwarf::DW_TAG_common_block:
 258   case dwarf::DW_TAG_lexical_block:
 259   case dwarf::DW_TAG_structure_type:
 260   case dwarf::DW_TAG_subprogram:
 261   case dwarf::DW_TAG_subroutine_type:
 262   case dwarf::DW_TAG_union_type:
 263   case dwarf::DW_TAG_array_type:
 264     return false;
 265   }
 266   llvm_unreachable("Invalid Tag");
 267 }
 268
 269 void DependencyTracker::addItemToWorklist(CompileUnit &CU,
 270                                           const DWARFDebugInfoEntry *Entry) {
 271   if (Entry->getAbbreviationDeclarationPtr() == nullptr)
 272     return;
 273
 274   const DWARFDebugInfoEntry *EntryToAdd = Entry;
 275
 276   // If parent does not allow children removing then use that parent as a root
 277   // DIE.
 278   std::optional<uint32_t> ParentIdx = Entry->getParentIdx();
 279   while (ParentIdx) {
 280     const DWARFDebugInfoEntry *ParentEntry = CU.getDebugInfoEntry(*ParentIdx);
 281     if (childrenCanBeRemoved(ParentEntry->getTag()))
 282       break;
 283     EntryToAdd = ParentEntry;
 284     ParentIdx = ParentEntry->getParentIdx();
 285   }
 286
 287   // Check if the DIE entry is already kept.
 288   if (CU.getDIEInfo(EntryToAdd).getKeep())
 289     return;
 290
 291   RootEntriesWorkList.emplace_back(CU, EntryToAdd);
 292 }
 293
 294 bool DependencyTracker::isLiveVariableEntry(CompileUnit &CU,
 295                                             const DWARFDebugInfoEntry *Entry) {
 296   DWARFDie DIE = CU.getDIE(Entry);
 297   CompileUnit::DIEInfo &Info = CU.getDIEInfo(DIE);
 298
 299   if (TrackLiveness) {
 300     const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
 301
 302     // Global variables with constant value can always be kept.
 303     if (!Info.getIsInFunctionScope() &&
 304         Abbrev->findAttributeIndex(dwarf::DW_AT_const_value))
 305       return true;
 306
 307     // See if there is a relocation to a valid debug map entry inside this
 308     // variable's location. The order is important here. We want to always check
 309     // if the variable has a location expression address.
 310     // However, we don't want a static variable in a function to force us to
 311     // keep the enclosing function, unless requested explicitly.
 312     std::pair<bool, std::optional<int64_t>> LocExprAddrAndRelocAdjustment =
 313         CU.getContaingFile().Addresses->getVariableRelocAdjustment(DIE);
 314
 315     if (!LocExprAddrAndRelocAdjustment.second)
 316       return false;
 317
 318     if ((Info.getIsInFunctionScope()) &&
 319         !LLVM_UNLIKELY(CU.getGlobalData().getOptions().KeepFunctionForStatic))
 320       return false;
 321   }
 322
 323   if (CU.getGlobalData().getOptions().Verbose) {
 324     outs() << "Keeping variable DIE:";
 325     DIDumpOptions DumpOpts;
 326     DumpOpts.ChildRecurseDepth = 0;
 327     DumpOpts.Verbose = CU.getGlobalData().getOptions().Verbose;
 328     DIE.dump(outs(), 8 /* Indent */, DumpOpts);
 329   }
 330
 331   return true;
 332 }
 333
 334 bool DependencyTracker::isLiveSubprogramEntry(
 335     CompileUnit &CU, const DWARFDebugInfoEntry *Entry) {
 336   DWARFDie DIE = CU.getDIE(Entry);
 337
 338   std::optional<uint64_t> LowPc;
 339   std::optional<uint64_t> HighPc;
 340   std::optional<int64_t> RelocAdjustment;
 341
 342   if (TrackLiveness) {
 343     LowPc = dwarf::toAddress(DIE.find(dwarf::DW_AT_low_pc));
 344     if (!LowPc)
 345       return false;
 346
 347     RelocAdjustment =
 348         CU.getContaingFile().Addresses->getSubprogramRelocAdjustment(DIE);
 349     if (!RelocAdjustment)
 350       return false;
 351
 352     if (DIE.getTag() == dwarf::DW_TAG_subprogram) {
 353       // Validate subprogram address range.
 354
 355       HighPc = DIE.getHighPC(*LowPc);
 356       if (!HighPc) {
 357         CU.warn("function without high_pc. Range will be discarded.", &DIE);
 358         return false;
 359       }
 360
 361       if (*LowPc > *HighPc) {
 362         CU.warn("low_pc greater than high_pc. Range will be discarded.", &DIE);
 363         return false;
 364       }
 365     } else if (DIE.getTag() == dwarf::DW_TAG_variable) {
 366       if (CU.hasLabelAt(*LowPc))
 367         return false;
 368
 369       // FIXME: dsymutil-classic compat. dsymutil-classic doesn't consider
 370       // labels that don't fall into the CU's aranges. This is wrong IMO. Debug
 371       // info generation bugs aside, this is really wrong in the case of labels,
 372       // where a label marking the end of a function will have a PC == CU's
 373       // high_pc.
 374       if (dwarf::toAddress(
 375               CU.getOrigUnit().getUnitDIE().find(dwarf::DW_AT_high_pc))
 376               .value_or(UINT64_MAX) <= LowPc)
 377         return false;
 378
 379       CU.addLabelLowPc(*LowPc, *RelocAdjustment);
 380     }
 381   }
 382
 383   if (CU.getGlobalData().getOptions().Verbose) {
 384     outs() << "Keeping subprogram DIE:";
 385     DIDumpOptions DumpOpts;
 386     DumpOpts.ChildRecurseDepth = 0;
 387     DumpOpts.Verbose = CU.getGlobalData().getOptions().Verbose;
 388     DIE.dump(outs(), 8 /* Indent */, DumpOpts);
 389   }
 390
 391   if (!TrackLiveness || DIE.getTag() == dwarf::DW_TAG_label)
 392     return true;
 393
 394   CU.addFunctionRange(*LowPc, *HighPc, *RelocAdjustment);
 395   return true;
 396 }
 397
 398 void DependencyTracker::setDIEPlacementAndTypename(CompileUnit::DIEInfo &Info) {
 399   Info.setPlacement(CompileUnit::PlainDwarf);
 400 }
 401
 402 } // end of namespace dwarflinker_parallel
 403 } // namespace llvm