LLVM  12.0.0git
DWARFLinker.cpp
Go to the documentation of this file.
1 //=== DWARFLinker.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 
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/ADT/BitVector.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/Triple.h"
26 #include "llvm/Support/Error.h"
28 #include "llvm/Support/ErrorOr.h"
30 #include "llvm/Support/LEB128.h"
31 #include "llvm/Support/Path.h"
33 #include <vector>
34 
35 namespace llvm {
36 
37 /// Hold the input and output of the debug info size in bytes.
38 struct DebugInfoSize {
39  uint64_t Input;
40  uint64_t Output;
41 };
42 
43 /// Compute the total size of the debug info.
44 static uint64_t getDebugInfoSize(DWARFContext &Dwarf) {
45  uint64_t Size = 0;
46  for (auto &Unit : Dwarf.compile_units()) {
47  Size += Unit->getLength();
48  }
49  return Size;
50 }
51 
52 /// Similar to DWARFUnitSection::getUnitForOffset(), but returning our
53 /// CompileUnit object instead.
54 static CompileUnit *getUnitForOffset(const UnitListTy &Units, uint64_t Offset) {
55  auto CU = std::upper_bound(
56  Units.begin(), Units.end(), Offset,
57  [](uint64_t LHS, const std::unique_ptr<CompileUnit> &RHS) {
58  return LHS < RHS->getOrigUnit().getNextUnitOffset();
59  });
60  return CU != Units.end() ? CU->get() : nullptr;
61 }
62 
63 /// Resolve the DIE attribute reference that has been extracted in \p RefValue.
64 /// The resulting DIE might be in another CompileUnit which is stored into \p
65 /// ReferencedCU. \returns null if resolving fails for any reason.
66 DWARFDie DWARFLinker::resolveDIEReference(const DwarfFile &File,
67  const UnitListTy &Units,
68  const DWARFFormValue &RefValue,
69  const DWARFDie &DIE,
70  CompileUnit *&RefCU) {
72  uint64_t RefOffset = *RefValue.getAsReference();
73  if ((RefCU = getUnitForOffset(Units, RefOffset)))
74  if (const auto RefDie = RefCU->getOrigUnit().getDIEForOffset(RefOffset)) {
75  // In a file with broken references, an attribute might point to a NULL
76  // DIE.
77  if (!RefDie.isNULL())
78  return RefDie;
79  }
80 
81  reportWarning("could not find referenced DIE", File, &DIE);
82  return DWARFDie();
83 }
84 
85 /// \returns whether the passed \a Attr type might contain a DIE reference
86 /// suitable for ODR uniquing.
87 static bool isODRAttribute(uint16_t Attr) {
88  switch (Attr) {
89  default:
90  return false;
91  case dwarf::DW_AT_type:
92  case dwarf::DW_AT_containing_type:
93  case dwarf::DW_AT_specification:
94  case dwarf::DW_AT_abstract_origin:
95  case dwarf::DW_AT_import:
96  return true;
97  }
98  llvm_unreachable("Improper attribute.");
99 }
100 
101 static bool isTypeTag(uint16_t Tag) {
102  switch (Tag) {
103  case dwarf::DW_TAG_array_type:
104  case dwarf::DW_TAG_class_type:
105  case dwarf::DW_TAG_enumeration_type:
106  case dwarf::DW_TAG_pointer_type:
107  case dwarf::DW_TAG_reference_type:
108  case dwarf::DW_TAG_string_type:
109  case dwarf::DW_TAG_structure_type:
110  case dwarf::DW_TAG_subroutine_type:
111  case dwarf::DW_TAG_typedef:
112  case dwarf::DW_TAG_union_type:
113  case dwarf::DW_TAG_ptr_to_member_type:
114  case dwarf::DW_TAG_set_type:
115  case dwarf::DW_TAG_subrange_type:
116  case dwarf::DW_TAG_base_type:
117  case dwarf::DW_TAG_const_type:
118  case dwarf::DW_TAG_constant:
119  case dwarf::DW_TAG_file_type:
120  case dwarf::DW_TAG_namelist:
121  case dwarf::DW_TAG_packed_type:
122  case dwarf::DW_TAG_volatile_type:
123  case dwarf::DW_TAG_restrict_type:
124  case dwarf::DW_TAG_atomic_type:
125  case dwarf::DW_TAG_interface_type:
126  case dwarf::DW_TAG_unspecified_type:
127  case dwarf::DW_TAG_shared_type:
128  return true;
129  default:
130  break;
131  }
132  return false;
133 }
134 
136 
138 
140  // We are looking for template parameters to strip from Name. e.g.
141  //
142  // operator<<B>
143  //
144  // We look for > at the end but if it does not contain any < then we
145  // have something like operator>>. We check for the operator<=> case.
146  if (!Name.endswith(">") || Name.count("<") == 0 || Name.endswith("<=>"))
147  return {};
148 
149  // How many < until we have the start of the template parameters.
150  size_t NumLeftAnglesToSkip = 1;
151 
152  // If we have operator<=> then we need to skip its < as well.
153  NumLeftAnglesToSkip += Name.count("<=>");
154 
155  size_t RightAngleCount = Name.count('>');
156  size_t LeftAngleCount = Name.count('<');
157 
158  // If we have more < than > we have operator< or operator<<
159  // we to account for their < as well.
160  if (LeftAngleCount > RightAngleCount)
161  NumLeftAnglesToSkip += LeftAngleCount - RightAngleCount;
162 
163  size_t StartOfTemplate = 0;
164  while (NumLeftAnglesToSkip--)
165  StartOfTemplate = Name.find('<', StartOfTemplate) + 1;
166 
167  return Name.substr(0, StartOfTemplate - 1);
168 }
169 
170 bool DWARFLinker::DIECloner::getDIENames(const DWARFDie &Die,
171  AttributesInfo &Info,
172  OffsetsStringPool &StringPool,
173  bool StripTemplate) {
174  // This function will be called on DIEs having low_pcs and
175  // ranges. As getting the name might be more expansive, filter out
176  // blocks directly.
177  if (Die.getTag() == dwarf::DW_TAG_lexical_block)
178  return false;
179 
180  if (!Info.MangledName)
181  if (const char *MangledName = Die.getLinkageName())
182  Info.MangledName = StringPool.getEntry(MangledName);
183 
184  if (!Info.Name)
185  if (const char *Name = Die.getShortName())
186  Info.Name = StringPool.getEntry(Name);
187 
188  if (!Info.MangledName)
189  Info.MangledName = Info.Name;
190 
191  if (StripTemplate && Info.Name && Info.MangledName != Info.Name) {
192  StringRef Name = Info.Name.getString();
193  if (Optional<StringRef> StrippedName = StripTemplateParameters(Name))
194  Info.NameWithoutTemplate = StringPool.getEntry(*StrippedName);
195  }
196 
197  return Info.Name || Info.MangledName;
198 }
199 
200 /// Resolve the relative path to a build artifact referenced by DWARF by
201 /// applying DW_AT_comp_dir.
203  sys::path::append(Buf, dwarf::toString(CU.find(dwarf::DW_AT_comp_dir), ""));
204 }
205 
206 /// Collect references to parseable Swift interfaces in imported
207 /// DW_TAG_module blocks.
209  const DWARFDie &DIE, CompileUnit &CU,
210  swiftInterfacesMap *ParseableSwiftInterfaces,
211  std::function<void(const Twine &, const DWARFDie &)> ReportWarning) {
212  if (CU.getLanguage() != dwarf::DW_LANG_Swift)
213  return;
214 
215  if (!ParseableSwiftInterfaces)
216  return;
217 
218  StringRef Path = dwarf::toStringRef(DIE.find(dwarf::DW_AT_LLVM_include_path));
219  if (!Path.endswith(".swiftinterface"))
220  return;
221  // Don't track interfaces that are part of the SDK.
222  StringRef SysRoot = dwarf::toStringRef(DIE.find(dwarf::DW_AT_LLVM_sysroot));
223  if (SysRoot.empty())
224  SysRoot = CU.getSysRoot();
225  if (!SysRoot.empty() && Path.startswith(SysRoot))
226  return;
227  if (Optional<DWARFFormValue> Val = DIE.find(dwarf::DW_AT_name))
228  if (Optional<const char *> Name = Val->getAsCString()) {
229  auto &Entry = (*ParseableSwiftInterfaces)[*Name];
230  // The prepend path is applied later when copying.
231  DWARFDie CUDie = CU.getOrigUnit().getUnitDIE();
232  SmallString<128> ResolvedPath;
233  if (sys::path::is_relative(Path))
234  resolveRelativeObjectPath(ResolvedPath, CUDie);
235  sys::path::append(ResolvedPath, Path);
236  if (!Entry.empty() && Entry != ResolvedPath)
237  ReportWarning(
238  Twine("Conflicting parseable interfaces for Swift Module ") +
239  *Name + ": " + Entry + " and " + Path,
240  DIE);
241  Entry = std::string(ResolvedPath.str());
242  }
243 }
244 
245 /// Recursive helper to build the global DeclContext information and
246 /// gather the child->parent relationships in the original compile unit.
247 ///
248 /// \return true when this DIE and all of its children are only
249 /// forward declarations to types defined in external clang modules
250 /// (i.e., forward declarations that are children of a DW_TAG_module).
251 static bool analyzeContextInfo(
252  const DWARFDie &DIE, unsigned ParentIdx, CompileUnit &CU,
253  DeclContext *CurrentDeclContext, UniquingStringPool &StringPool,
254  DeclContextTree &Contexts, uint64_t ModulesEndOffset,
255  swiftInterfacesMap *ParseableSwiftInterfaces,
256  std::function<void(const Twine &, const DWARFDie &)> ReportWarning,
257  bool InImportedModule = false) {
258  unsigned MyIdx = CU.getOrigUnit().getDIEIndex(DIE);
259  CompileUnit::DIEInfo &Info = CU.getInfo(MyIdx);
260 
261  // Clang imposes an ODR on modules(!) regardless of the language:
262  // "The module-id should consist of only a single identifier,
263  // which provides the name of the module being defined. Each
264  // module shall have a single definition."
265  //
266  // This does not extend to the types inside the modules:
267  // "[I]n C, this implies that if two structs are defined in
268  // different submodules with the same name, those two types are
269  // distinct types (but may be compatible types if their
270  // definitions match)."
271  //
272  // We treat non-C++ modules like namespaces for this reason.
273  if (DIE.getTag() == dwarf::DW_TAG_module && ParentIdx == 0 &&
274  dwarf::toString(DIE.find(dwarf::DW_AT_name), "") !=
275  CU.getClangModuleName()) {
276  InImportedModule = true;
277  analyzeImportedModule(DIE, CU, ParseableSwiftInterfaces, ReportWarning);
278  }
279 
280  Info.ParentIdx = ParentIdx;
281  bool InClangModule = CU.isClangModule() || InImportedModule;
282  if (CU.hasODR() || InClangModule) {
283  if (CurrentDeclContext) {
284  auto PtrInvalidPair = Contexts.getChildDeclContext(
285  *CurrentDeclContext, DIE, CU, StringPool, InClangModule);
286  CurrentDeclContext = PtrInvalidPair.getPointer();
287  Info.Ctxt =
288  PtrInvalidPair.getInt() ? nullptr : PtrInvalidPair.getPointer();
289  if (Info.Ctxt)
290  Info.Ctxt->setDefinedInClangModule(InClangModule);
291  } else
292  Info.Ctxt = CurrentDeclContext = nullptr;
293  }
294 
295  Info.Prune = InImportedModule;
296  if (DIE.hasChildren())
297  for (auto Child : DIE.children())
298  Info.Prune &= analyzeContextInfo(Child, MyIdx, CU, CurrentDeclContext,
299  StringPool, Contexts, ModulesEndOffset,
300  ParseableSwiftInterfaces, ReportWarning,
301  InImportedModule);
302 
303  // Prune this DIE if it is either a forward declaration inside a
304  // DW_TAG_module or a DW_TAG_module that contains nothing but
305  // forward declarations.
306  Info.Prune &= (DIE.getTag() == dwarf::DW_TAG_module) ||
307  (isTypeTag(DIE.getTag()) &&
308  dwarf::toUnsigned(DIE.find(dwarf::DW_AT_declaration), 0));
309 
310  // Only prune forward declarations inside a DW_TAG_module for which a
311  // definition exists elsewhere.
312  if (ModulesEndOffset == 0)
313  Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset();
314  else
315  Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() > 0 &&
316  Info.Ctxt->getCanonicalDIEOffset() <= ModulesEndOffset;
317 
318  return Info.Prune;
319 }
320 
322  switch (Tag) {
323  default:
324  return false;
325  case dwarf::DW_TAG_class_type:
326  case dwarf::DW_TAG_common_block:
327  case dwarf::DW_TAG_lexical_block:
328  case dwarf::DW_TAG_structure_type:
329  case dwarf::DW_TAG_subprogram:
330  case dwarf::DW_TAG_subroutine_type:
331  case dwarf::DW_TAG_union_type:
332  return true;
333  }
334  llvm_unreachable("Invalid Tag");
335 }
336 
337 void DWARFLinker::cleanupAuxiliarryData(LinkContext &Context) {
338  Context.clear();
339 
340  for (auto I = DIEBlocks.begin(), E = DIEBlocks.end(); I != E; ++I)
341  (*I)->~DIEBlock();
342  for (auto I = DIELocs.begin(), E = DIELocs.end(); I != E; ++I)
343  (*I)->~DIELoc();
344 
345  DIEBlocks.clear();
346  DIELocs.clear();
347  DIEAlloc.Reset();
348 }
349 
350 /// Get the starting and ending (exclusive) offset for the
351 /// attribute with index \p Idx descibed by \p Abbrev. \p Offset is
352 /// supposed to point to the position of the first attribute described
353 /// by \p Abbrev.
354 /// \return [StartOffset, EndOffset) as a pair.
355 static std::pair<uint64_t, uint64_t>
357  uint64_t Offset, const DWARFUnit &Unit) {
359 
360  for (unsigned I = 0; I < Idx; ++I)
362  Unit.getFormParams());
363 
364  uint64_t End = Offset;
365  DWARFFormValue::skipValue(Abbrev->getFormByIndex(Idx), Data, &End,
366  Unit.getFormParams());
367 
368  return std::make_pair(Offset, End);
369 }
370 
371 /// Check if a variable describing DIE should be kept.
372 /// \returns updated TraversalFlags.
373 unsigned DWARFLinker::shouldKeepVariableDIE(AddressesMap &RelocMgr,
374  const DWARFDie &DIE,
375  CompileUnit &Unit,
376  CompileUnit::DIEInfo &MyInfo,
377  unsigned Flags) {
378  const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
379 
380  // Global variables with constant value can always be kept.
381  if (!(Flags & TF_InFunctionScope) &&
382  Abbrev->findAttributeIndex(dwarf::DW_AT_const_value)) {
383  MyInfo.InDebugMap = true;
384  return Flags | TF_Keep;
385  }
386 
387  Optional<uint32_t> LocationIdx =
388  Abbrev->findAttributeIndex(dwarf::DW_AT_location);
389  if (!LocationIdx)
390  return Flags;
391 
392  uint64_t Offset = DIE.getOffset() + getULEB128Size(Abbrev->getCode());
393  const DWARFUnit &OrigUnit = Unit.getOrigUnit();
394  uint64_t LocationOffset, LocationEndOffset;
395  std::tie(LocationOffset, LocationEndOffset) =
396  getAttributeOffsets(Abbrev, *LocationIdx, Offset, OrigUnit);
397 
398  // See if there is a relocation to a valid debug map entry inside
399  // this variable's location. The order is important here. We want to
400  // always check if the variable has a valid relocation, so that the
401  // DIEInfo is filled. However, we don't want a static variable in a
402  // function to force us to keep the enclosing function.
403  if (!RelocMgr.hasValidRelocationAt(LocationOffset, LocationEndOffset,
404  MyInfo) ||
405  (Flags & TF_InFunctionScope))
406  return Flags;
407 
408  if (Options.Verbose) {
409  outs() << "Keeping variable DIE:";
410  DIDumpOptions DumpOpts;
411  DumpOpts.ChildRecurseDepth = 0;
412  DumpOpts.Verbose = Options.Verbose;
413  DIE.dump(outs(), 8 /* Indent */, DumpOpts);
414  }
415 
416  return Flags | TF_Keep;
417 }
418 
419 /// Check if a function describing DIE should be kept.
420 /// \returns updated TraversalFlags.
421 unsigned DWARFLinker::shouldKeepSubprogramDIE(
422  AddressesMap &RelocMgr, RangesTy &Ranges, const DWARFDie &DIE,
423  const DwarfFile &File, CompileUnit &Unit, CompileUnit::DIEInfo &MyInfo,
424  unsigned Flags) {
425  const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
426 
427  Flags |= TF_InFunctionScope;
428 
429  Optional<uint32_t> LowPcIdx = Abbrev->findAttributeIndex(dwarf::DW_AT_low_pc);
430  if (!LowPcIdx)
431  return Flags;
432 
433  uint64_t Offset = DIE.getOffset() + getULEB128Size(Abbrev->getCode());
434  DWARFUnit &OrigUnit = Unit.getOrigUnit();
435  uint64_t LowPcOffset, LowPcEndOffset;
436  std::tie(LowPcOffset, LowPcEndOffset) =
437  getAttributeOffsets(Abbrev, *LowPcIdx, Offset, OrigUnit);
438 
439  auto LowPc = dwarf::toAddress(DIE.find(dwarf::DW_AT_low_pc));
440  assert(LowPc.hasValue() && "low_pc attribute is not an address.");
441  if (!LowPc ||
442  !RelocMgr.hasValidRelocationAt(LowPcOffset, LowPcEndOffset, MyInfo))
443  return Flags;
444 
445  if (Options.Verbose) {
446  outs() << "Keeping subprogram DIE:";
447  DIDumpOptions DumpOpts;
448  DumpOpts.ChildRecurseDepth = 0;
449  DumpOpts.Verbose = Options.Verbose;
450  DIE.dump(outs(), 8 /* Indent */, DumpOpts);
451  }
452 
453  if (DIE.getTag() == dwarf::DW_TAG_label) {
454  if (Unit.hasLabelAt(*LowPc))
455  return Flags;
456  // FIXME: dsymutil-classic compat. dsymutil-classic doesn't consider labels
457  // that don't fall into the CU's aranges. This is wrong IMO. Debug info
458  // generation bugs aside, this is really wrong in the case of labels, where
459  // a label marking the end of a function will have a PC == CU's high_pc.
460  if (dwarf::toAddress(OrigUnit.getUnitDIE().find(dwarf::DW_AT_high_pc))
461  .getValueOr(UINT64_MAX) <= LowPc)
462  return Flags;
463  Unit.addLabelLowPc(*LowPc, MyInfo.AddrAdjust);
464  return Flags | TF_Keep;
465  }
466 
467  Flags |= TF_Keep;
468 
469  Optional<uint64_t> HighPc = DIE.getHighPC(*LowPc);
470  if (!HighPc) {
471  reportWarning("Function without high_pc. Range will be discarded.\n", File,
472  &DIE);
473  return Flags;
474  }
475 
476  // Replace the debug map range with a more accurate one.
477  Ranges[*LowPc] = ObjFileAddressRange(*HighPc, MyInfo.AddrAdjust);
478  Unit.addFunctionRange(*LowPc, *HighPc, MyInfo.AddrAdjust);
479  return Flags;
480 }
481 
482 /// Check if a DIE should be kept.
483 /// \returns updated TraversalFlags.
484 unsigned DWARFLinker::shouldKeepDIE(AddressesMap &RelocMgr, RangesTy &Ranges,
485  const DWARFDie &DIE, const DwarfFile &File,
486  CompileUnit &Unit,
487  CompileUnit::DIEInfo &MyInfo,
488  unsigned Flags) {
489  switch (DIE.getTag()) {
490  case dwarf::DW_TAG_constant:
491  case dwarf::DW_TAG_variable:
492  return shouldKeepVariableDIE(RelocMgr, DIE, Unit, MyInfo, Flags);
493  case dwarf::DW_TAG_subprogram:
494  case dwarf::DW_TAG_label:
495  return shouldKeepSubprogramDIE(RelocMgr, Ranges, DIE, File, Unit, MyInfo,
496  Flags);
497  case dwarf::DW_TAG_base_type:
498  // DWARF Expressions may reference basic types, but scanning them
499  // is expensive. Basic types are tiny, so just keep all of them.
500  case dwarf::DW_TAG_imported_module:
501  case dwarf::DW_TAG_imported_declaration:
502  case dwarf::DW_TAG_imported_unit:
503  // We always want to keep these.
504  return Flags | TF_Keep;
505  default:
506  break;
507  }
508 
509  return Flags;
510 }
511 
512 /// Helper that updates the completeness of the current DIE based on the
513 /// completeness of one of its children. It depends on the incompleteness of
514 /// the children already being computed.
515 static void updateChildIncompleteness(const DWARFDie &Die, CompileUnit &CU,
516  CompileUnit::DIEInfo &ChildInfo) {
517  switch (Die.getTag()) {
518  case dwarf::DW_TAG_structure_type:
519  case dwarf::DW_TAG_class_type:
520  break;
521  default:
522  return;
523  }
524 
525  unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
526  CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
527 
528  if (ChildInfo.Incomplete || ChildInfo.Prune)
529  MyInfo.Incomplete = true;
530 }
531 
532 /// Helper that updates the completeness of the current DIE based on the
533 /// completeness of the DIEs it references. It depends on the incompleteness of
534 /// the referenced DIE already being computed.
535 static void updateRefIncompleteness(const DWARFDie &Die, CompileUnit &CU,
536  CompileUnit::DIEInfo &RefInfo) {
537  switch (Die.getTag()) {
538  case dwarf::DW_TAG_typedef:
539  case dwarf::DW_TAG_member:
540  case dwarf::DW_TAG_reference_type:
541  case dwarf::DW_TAG_ptr_to_member_type:
542  case dwarf::DW_TAG_pointer_type:
543  break;
544  default:
545  return;
546  }
547 
548  unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
549  CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
550 
551  if (MyInfo.Incomplete)
552  return;
553 
554  if (RefInfo.Incomplete)
555  MyInfo.Incomplete = true;
556 }
557 
558 /// Look at the children of the given DIE and decide whether they should be
559 /// kept.
560 void DWARFLinker::lookForChildDIEsToKeep(
561  const DWARFDie &Die, CompileUnit &CU, unsigned Flags,
562  SmallVectorImpl<WorklistItem> &Worklist) {
563  // The TF_ParentWalk flag tells us that we are currently walking up the
564  // parent chain of a required DIE, and we don't want to mark all the children
565  // of the parents as kept (consider for example a DW_TAG_namespace node in
566  // the parent chain). There are however a set of DIE types for which we want
567  // to ignore that directive and still walk their children.
569  Flags &= ~DWARFLinker::TF_ParentWalk;
570 
571  // We're finished if this DIE has no children or we're walking the parent
572  // chain.
573  if (!Die.hasChildren() || (Flags & DWARFLinker::TF_ParentWalk))
574  return;
575 
576  // Add children in reverse order to the worklist to effectively process them
577  // in order.
578  for (auto Child : reverse(Die.children())) {
579  // Add a worklist item before every child to calculate incompleteness right
580  // after the current child is processed.
581  unsigned Idx = CU.getOrigUnit().getDIEIndex(Child);
582  CompileUnit::DIEInfo &ChildInfo = CU.getInfo(Idx);
583  Worklist.emplace_back(Die, CU, WorklistItemType::UpdateChildIncompleteness,
584  &ChildInfo);
585  Worklist.emplace_back(Child, CU, Flags);
586  }
587 }
588 
589 /// Look at DIEs referenced by the given DIE and decide whether they should be
590 /// kept. All DIEs referenced though attributes should be kept.
591 void DWARFLinker::lookForRefDIEsToKeep(
592  const DWARFDie &Die, CompileUnit &CU, unsigned Flags,
593  const UnitListTy &Units, const DwarfFile &File,
594  SmallVectorImpl<WorklistItem> &Worklist) {
595  bool UseOdr = (Flags & DWARFLinker::TF_DependencyWalk)
596  ? (Flags & DWARFLinker::TF_ODR)
597  : CU.hasODR();
598  DWARFUnit &Unit = CU.getOrigUnit();
600  const auto *Abbrev = Die.getAbbreviationDeclarationPtr();
601  uint64_t Offset = Die.getOffset() + getULEB128Size(Abbrev->getCode());
602 
604  for (const auto &AttrSpec : Abbrev->attributes()) {
605  DWARFFormValue Val(AttrSpec.Form);
607  AttrSpec.Attr == dwarf::DW_AT_sibling) {
608  DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset,
609  Unit.getFormParams());
610  continue;
611  }
612 
613  Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit);
614  CompileUnit *ReferencedCU;
615  if (auto RefDie =
616  resolveDIEReference(File, Units, Val, Die, ReferencedCU)) {
617  uint32_t RefIdx = ReferencedCU->getOrigUnit().getDIEIndex(RefDie);
618  CompileUnit::DIEInfo &Info = ReferencedCU->getInfo(RefIdx);
619  bool IsModuleRef = Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() &&
621  // If the referenced DIE has a DeclContext that has already been
622  // emitted, then do not keep the one in this CU. We'll link to
623  // the canonical DIE in cloneDieReferenceAttribute.
624  //
625  // FIXME: compatibility with dsymutil-classic. UseODR shouldn't
626  // be necessary and could be advantageously replaced by
627  // ReferencedCU->hasODR() && CU.hasODR().
628  //
629  // FIXME: compatibility with dsymutil-classic. There is no
630  // reason not to unique ref_addr references.
631  if (AttrSpec.Form != dwarf::DW_FORM_ref_addr && (UseOdr || IsModuleRef) &&
632  Info.Ctxt &&
633  Info.Ctxt != ReferencedCU->getInfo(Info.ParentIdx).Ctxt &&
634  Info.Ctxt->getCanonicalDIEOffset() && isODRAttribute(AttrSpec.Attr))
635  continue;
636 
637  // Keep a module forward declaration if there is no definition.
638  if (!(isODRAttribute(AttrSpec.Attr) && Info.Ctxt &&
639  Info.Ctxt->getCanonicalDIEOffset()))
640  Info.Prune = false;
641  ReferencedDIEs.emplace_back(RefDie, *ReferencedCU);
642  }
643  }
644 
645  unsigned ODRFlag = UseOdr ? DWARFLinker::TF_ODR : 0;
646 
647  // Add referenced DIEs in reverse order to the worklist to effectively
648  // process them in order.
649  for (auto &P : reverse(ReferencedDIEs)) {
650  // Add a worklist item before every child to calculate incompleteness right
651  // after the current child is processed.
652  uint32_t RefIdx = P.second.getOrigUnit().getDIEIndex(P.first);
653  CompileUnit::DIEInfo &Info = P.second.getInfo(RefIdx);
654  Worklist.emplace_back(Die, CU, WorklistItemType::UpdateRefIncompleteness,
655  &Info);
656  Worklist.emplace_back(P.first, P.second,
657  DWARFLinker::TF_Keep |
658  DWARFLinker::TF_DependencyWalk | ODRFlag);
659  }
660 }
661 
662 /// Look at the parent of the given DIE and decide whether they should be kept.
663 void DWARFLinker::lookForParentDIEsToKeep(
664  unsigned AncestorIdx, CompileUnit &CU, unsigned Flags,
665  SmallVectorImpl<WorklistItem> &Worklist) {
666  // Stop if we encounter an ancestor that's already marked as kept.
667  if (CU.getInfo(AncestorIdx).Keep)
668  return;
669 
670  DWARFUnit &Unit = CU.getOrigUnit();
671  DWARFDie ParentDIE = Unit.getDIEAtIndex(AncestorIdx);
672  Worklist.emplace_back(CU.getInfo(AncestorIdx).ParentIdx, CU, Flags);
673  Worklist.emplace_back(ParentDIE, CU, Flags);
674 }
675 
676 /// Recursively walk the \p DIE tree and look for DIEs to keep. Store that
677 /// information in \p CU's DIEInfo.
678 ///
679 /// This function is the entry point of the DIE selection algorithm. It is
680 /// expected to walk the DIE tree in file order and (though the mediation of
681 /// its helper) call hasValidRelocation() on each DIE that might be a 'root
682 /// DIE' (See DwarfLinker class comment).
683 ///
684 /// While walking the dependencies of root DIEs, this function is also called,
685 /// but during these dependency walks the file order is not respected. The
686 /// TF_DependencyWalk flag tells us which kind of traversal we are currently
687 /// doing.
688 ///
689 /// The recursive algorithm is implemented iteratively as a work list because
690 /// very deep recursion could exhaust the stack for large projects. The work
691 /// list acts as a scheduler for different types of work that need to be
692 /// performed.
693 ///
694 /// The recursive nature of the algorithm is simulated by running the "main"
695 /// algorithm (LookForDIEsToKeep) followed by either looking at more DIEs
696 /// (LookForChildDIEsToKeep, LookForRefDIEsToKeep, LookForParentDIEsToKeep) or
697 /// fixing up a computed property (UpdateChildIncompleteness,
698 /// UpdateRefIncompleteness).
699 ///
700 /// The return value indicates whether the DIE is incomplete.
701 void DWARFLinker::lookForDIEsToKeep(AddressesMap &AddressesMap,
702  RangesTy &Ranges, const UnitListTy &Units,
703  const DWARFDie &Die, const DwarfFile &File,
704  CompileUnit &Cu, unsigned Flags) {
705  // LIFO work list.
707  Worklist.emplace_back(Die, Cu, Flags);
708 
709  while (!Worklist.empty()) {
710  WorklistItem Current = Worklist.back();
711  Worklist.pop_back();
712 
713  // Look at the worklist type to decide what kind of work to perform.
714  switch (Current.Type) {
715  case WorklistItemType::UpdateChildIncompleteness:
716  updateChildIncompleteness(Current.Die, Current.CU, *Current.OtherInfo);
717  continue;
718  case WorklistItemType::UpdateRefIncompleteness:
719  updateRefIncompleteness(Current.Die, Current.CU, *Current.OtherInfo);
720  continue;
721  case WorklistItemType::LookForChildDIEsToKeep:
722  lookForChildDIEsToKeep(Current.Die, Current.CU, Current.Flags, Worklist);
723  continue;
724  case WorklistItemType::LookForRefDIEsToKeep:
725  lookForRefDIEsToKeep(Current.Die, Current.CU, Current.Flags, Units, File,
726  Worklist);
727  continue;
728  case WorklistItemType::LookForParentDIEsToKeep:
729  lookForParentDIEsToKeep(Current.AncestorIdx, Current.CU, Current.Flags,
730  Worklist);
731  continue;
732  case WorklistItemType::LookForDIEsToKeep:
733  break;
734  }
735 
736  unsigned Idx = Current.CU.getOrigUnit().getDIEIndex(Current.Die);
737  CompileUnit::DIEInfo &MyInfo = Current.CU.getInfo(Idx);
738 
739  if (MyInfo.Prune)
740  continue;
741 
742  // If the Keep flag is set, we are marking a required DIE's dependencies.
743  // If our target is already marked as kept, we're all set.
744  bool AlreadyKept = MyInfo.Keep;
745  if ((Current.Flags & TF_DependencyWalk) && AlreadyKept)
746  continue;
747 
748  // We must not call shouldKeepDIE while called from keepDIEAndDependencies,
749  // because it would screw up the relocation finding logic.
750  if (!(Current.Flags & TF_DependencyWalk))
751  Current.Flags = shouldKeepDIE(AddressesMap, Ranges, Current.Die, File,
752  Current.CU, MyInfo, Current.Flags);
753 
754  // Finish by looking for child DIEs. Because of the LIFO worklist we need
755  // to schedule that work before any subsequent items are added to the
756  // worklist.
757  Worklist.emplace_back(Current.Die, Current.CU, Current.Flags,
758  WorklistItemType::LookForChildDIEsToKeep);
759 
760  if (AlreadyKept || !(Current.Flags & TF_Keep))
761  continue;
762 
763  // If it is a newly kept DIE mark it as well as all its dependencies as
764  // kept.
765  MyInfo.Keep = true;
766 
767  // We're looking for incomplete types.
768  MyInfo.Incomplete =
769  Current.Die.getTag() != dwarf::DW_TAG_subprogram &&
770  Current.Die.getTag() != dwarf::DW_TAG_member &&
771  dwarf::toUnsigned(Current.Die.find(dwarf::DW_AT_declaration), 0);
772 
773  // After looking at the parent chain, look for referenced DIEs. Because of
774  // the LIFO worklist we need to schedule that work before any subsequent
775  // items are added to the worklist.
776  Worklist.emplace_back(Current.Die, Current.CU, Current.Flags,
777  WorklistItemType::LookForRefDIEsToKeep);
778 
779  bool UseOdr = (Current.Flags & TF_DependencyWalk) ? (Current.Flags & TF_ODR)
780  : Current.CU.hasODR();
781  unsigned ODRFlag = UseOdr ? TF_ODR : 0;
782  unsigned ParFlags = TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag;
783 
784  // Now schedule the parent walk.
785  Worklist.emplace_back(MyInfo.ParentIdx, Current.CU, ParFlags);
786  }
787 }
788 
789 /// Assign an abbreviation number to \p Abbrev.
790 ///
791 /// Our DIEs get freed after every DebugMapObject has been processed,
792 /// thus the FoldingSet we use to unique DIEAbbrevs cannot refer to
793 /// the instances hold by the DIEs. When we encounter an abbreviation
794 /// that we don't know, we create a permanent copy of it.
795 void DWARFLinker::assignAbbrev(DIEAbbrev &Abbrev) {
796  // Check the set for priors.
798  Abbrev.Profile(ID);
799  void *InsertToken;
800  DIEAbbrev *InSet = AbbreviationsSet.FindNodeOrInsertPos(ID, InsertToken);
801 
802  // If it's newly added.
803  if (InSet) {
804  // Assign existing abbreviation number.
805  Abbrev.setNumber(InSet->getNumber());
806  } else {
807  // Add to abbreviation list.
808  Abbreviations.push_back(
809  std::make_unique<DIEAbbrev>(Abbrev.getTag(), Abbrev.hasChildren()));
810  for (const auto &Attr : Abbrev.getData())
811  Abbreviations.back()->AddAttribute(Attr.getAttribute(), Attr.getForm());
812  AbbreviationsSet.InsertNode(Abbreviations.back().get(), InsertToken);
813  // Assign the unique abbreviation number.
814  Abbrev.setNumber(Abbreviations.size());
815  Abbreviations.back()->setNumber(Abbreviations.size());
816  }
817 }
818 
819 unsigned DWARFLinker::DIECloner::cloneStringAttribute(
820  DIE &Die, AttributeSpec AttrSpec, const DWARFFormValue &Val,
821  const DWARFUnit &U, OffsetsStringPool &StringPool, AttributesInfo &Info) {
822  // Switch everything to out of line strings.
823  const char *String = *Val.getAsCString();
824  auto StringEntry = StringPool.getEntry(String);
825 
826  // Update attributes info.
827  if (AttrSpec.Attr == dwarf::DW_AT_name)
828  Info.Name = StringEntry;
829  else if (AttrSpec.Attr == dwarf::DW_AT_MIPS_linkage_name ||
830  AttrSpec.Attr == dwarf::DW_AT_linkage_name)
831  Info.MangledName = StringEntry;
832 
833  Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr), dwarf::DW_FORM_strp,
834  DIEInteger(StringEntry.getOffset()));
835 
836  return 4;
837 }
838 
839 unsigned DWARFLinker::DIECloner::cloneDieReferenceAttribute(
840  DIE &Die, const DWARFDie &InputDIE, AttributeSpec AttrSpec,
841  unsigned AttrSize, const DWARFFormValue &Val, const DwarfFile &File,
842  CompileUnit &Unit) {
843  const DWARFUnit &U = Unit.getOrigUnit();
844  uint64_t Ref = *Val.getAsReference();
845 
846  DIE *NewRefDie = nullptr;
847  CompileUnit *RefUnit = nullptr;
848  DeclContext *Ctxt = nullptr;
849 
850  DWARFDie RefDie =
851  Linker.resolveDIEReference(File, CompileUnits, Val, InputDIE, RefUnit);
852 
853  // If the referenced DIE is not found, drop the attribute.
854  if (!RefDie || AttrSpec.Attr == dwarf::DW_AT_sibling)
855  return 0;
856 
857  unsigned Idx = RefUnit->getOrigUnit().getDIEIndex(RefDie);
858  CompileUnit::DIEInfo &RefInfo = RefUnit->getInfo(Idx);
859 
860  // If we already have emitted an equivalent DeclContext, just point
861  // at it.
862  if (isODRAttribute(AttrSpec.Attr)) {
863  Ctxt = RefInfo.Ctxt;
864  if (Ctxt && Ctxt->getCanonicalDIEOffset()) {
865  DIEInteger Attr(Ctxt->getCanonicalDIEOffset());
866  Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
867  dwarf::DW_FORM_ref_addr, Attr);
868  return U.getRefAddrByteSize();
869  }
870  }
871 
872  if (!RefInfo.Clone) {
873  assert(Ref > InputDIE.getOffset());
874  // We haven't cloned this DIE yet. Just create an empty one and
875  // store it. It'll get really cloned when we process it.
876  RefInfo.Clone = DIE::get(DIEAlloc, dwarf::Tag(RefDie.getTag()));
877  }
878  NewRefDie = RefInfo.Clone;
879 
880  if (AttrSpec.Form == dwarf::DW_FORM_ref_addr ||
881  (Unit.hasODR() && isODRAttribute(AttrSpec.Attr))) {
882  // We cannot currently rely on a DIEEntry to emit ref_addr
883  // references, because the implementation calls back to DwarfDebug
884  // to find the unit offset. (We don't have a DwarfDebug)
885  // FIXME: we should be able to design DIEEntry reliance on
886  // DwarfDebug away.
887  uint64_t Attr;
888  if (Ref < InputDIE.getOffset()) {
889  // We must have already cloned that DIE.
890  uint32_t NewRefOffset =
891  RefUnit->getStartOffset() + NewRefDie->getOffset();
892  Attr = NewRefOffset;
893  Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
894  dwarf::DW_FORM_ref_addr, DIEInteger(Attr));
895  } else {
896  // A forward reference. Note and fixup later.
897  Attr = 0xBADDEF;
899  NewRefDie, RefUnit, Ctxt,
900  Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
901  dwarf::DW_FORM_ref_addr, DIEInteger(Attr)));
902  }
903  return U.getRefAddrByteSize();
904  }
905 
906  Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
907  dwarf::Form(AttrSpec.Form), DIEEntry(*NewRefDie));
908 
909  return AttrSize;
910 }
911 
912 void DWARFLinker::DIECloner::cloneExpression(
914  CompileUnit &Unit, SmallVectorImpl<uint8_t> &OutputBuffer) {
915  using Encoding = DWARFExpression::Operation::Encoding;
916 
917  uint64_t OpOffset = 0;
918  for (auto &Op : Expression) {
919  auto Description = Op.getDescription();
920  // DW_OP_const_type is variable-length and has 3
921  // operands. DWARFExpression thus far only supports 2.
922  auto Op0 = Description.Op[0];
923  auto Op1 = Description.Op[1];
924  if ((Op0 == Encoding::BaseTypeRef && Op1 != Encoding::SizeNA) ||
925  (Op1 == Encoding::BaseTypeRef && Op0 != Encoding::Size1))
926  Linker.reportWarning("Unsupported DW_OP encoding.", File);
927 
928  if ((Op0 == Encoding::BaseTypeRef && Op1 == Encoding::SizeNA) ||
929  (Op1 == Encoding::BaseTypeRef && Op0 == Encoding::Size1)) {
930  // This code assumes that the other non-typeref operand fits into 1 byte.
931  assert(OpOffset < Op.getEndOffset());
932  uint32_t ULEBsize = Op.getEndOffset() - OpOffset - 1;
933  assert(ULEBsize <= 16);
934 
935  // Copy over the operation.
936  OutputBuffer.push_back(Op.getCode());
937  uint64_t RefOffset;
938  if (Op1 == Encoding::SizeNA) {
939  RefOffset = Op.getRawOperand(0);
940  } else {
941  OutputBuffer.push_back(Op.getRawOperand(0));
942  RefOffset = Op.getRawOperand(1);
943  }
944  uint32_t Offset = 0;
945  // Look up the base type. For DW_OP_convert, the operand may be 0 to
946  // instead indicate the generic type. The same holds for
947  // DW_OP_reinterpret, which is currently not supported.
948  if (RefOffset > 0 || Op.getCode() != dwarf::DW_OP_convert) {
949  auto RefDie = Unit.getOrigUnit().getDIEForOffset(RefOffset);
950  uint32_t RefIdx = Unit.getOrigUnit().getDIEIndex(RefDie);
951  CompileUnit::DIEInfo &Info = Unit.getInfo(RefIdx);
952  if (DIE *Clone = Info.Clone)
953  Offset = Clone->getOffset();
954  else
955  Linker.reportWarning(
956  "base type ref doesn't point to DW_TAG_base_type.", File);
957  }
958  uint8_t ULEB[16];
959  unsigned RealSize = encodeULEB128(Offset, ULEB, ULEBsize);
960  if (RealSize > ULEBsize) {
961  // Emit the generic type as a fallback.
962  RealSize = encodeULEB128(0, ULEB, ULEBsize);
963  Linker.reportWarning("base type ref doesn't fit.", File);
964  }
965  assert(RealSize == ULEBsize && "padding failed");
966  ArrayRef<uint8_t> ULEBbytes(ULEB, ULEBsize);
967  OutputBuffer.append(ULEBbytes.begin(), ULEBbytes.end());
968  } else {
969  // Copy over everything else unmodified.
970  StringRef Bytes = Data.getData().slice(OpOffset, Op.getEndOffset());
971  OutputBuffer.append(Bytes.begin(), Bytes.end());
972  }
973  OpOffset = Op.getEndOffset();
974  }
975 }
976 
977 unsigned DWARFLinker::DIECloner::cloneBlockAttribute(
978  DIE &Die, const DwarfFile &File, CompileUnit &Unit, AttributeSpec AttrSpec,
979  const DWARFFormValue &Val, unsigned AttrSize, bool IsLittleEndian) {
980  DIEValueList *Attr;
981  DIEValue Value;
982  DIELoc *Loc = nullptr;
983  DIEBlock *Block = nullptr;
984  if (AttrSpec.Form == dwarf::DW_FORM_exprloc) {
985  Loc = new (DIEAlloc) DIELoc;
986  Linker.DIELocs.push_back(Loc);
987  } else {
988  Block = new (DIEAlloc) DIEBlock;
989  Linker.DIEBlocks.push_back(Block);
990  }
991  Attr = Loc ? static_cast<DIEValueList *>(Loc)
992  : static_cast<DIEValueList *>(Block);
993 
994  if (Loc)
995  Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
996  dwarf::Form(AttrSpec.Form), Loc);
997  else
998  Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
999  dwarf::Form(AttrSpec.Form), Block);
1000 
1001  // If the block is a DWARF Expression, clone it into the temporary
1002  // buffer using cloneExpression(), otherwise copy the data directly.
1003  SmallVector<uint8_t, 32> Buffer;
1004  ArrayRef<uint8_t> Bytes = *Val.getAsBlock();
1005  if (DWARFAttribute::mayHaveLocationDescription(AttrSpec.Attr) &&
1008  DWARFUnit &OrigUnit = Unit.getOrigUnit();
1009  DataExtractor Data(StringRef((const char *)Bytes.data(), Bytes.size()),
1010  IsLittleEndian, OrigUnit.getAddressByteSize());
1011  DWARFExpression Expr(Data, OrigUnit.getAddressByteSize(),
1012  OrigUnit.getFormParams().Format);
1013  cloneExpression(Data, Expr, File, Unit, Buffer);
1014  Bytes = Buffer;
1015  }
1016  for (auto Byte : Bytes)
1017  Attr->addValue(DIEAlloc, static_cast<dwarf::Attribute>(0),
1018  dwarf::DW_FORM_data1, DIEInteger(Byte));
1019 
1020  // FIXME: If DIEBlock and DIELoc just reuses the Size field of
1021  // the DIE class, this "if" could be replaced by
1022  // Attr->setSize(Bytes.size()).
1023  if (Loc)
1024  Loc->setSize(Bytes.size());
1025  else
1026  Block->setSize(Bytes.size());
1027 
1028  Die.addValue(DIEAlloc, Value);
1029  return AttrSize;
1030 }
1031 
1032 unsigned DWARFLinker::DIECloner::cloneAddressAttribute(
1033  DIE &Die, AttributeSpec AttrSpec, const DWARFFormValue &Val,
1034  const CompileUnit &Unit, AttributesInfo &Info) {
1035  uint64_t Addr = *Val.getAsAddress();
1036 
1037  if (LLVM_UNLIKELY(Linker.Options.Update)) {
1038  if (AttrSpec.Attr == dwarf::DW_AT_low_pc)
1039  Info.HasLowPc = true;
1040  Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
1041  dwarf::Form(AttrSpec.Form), DIEInteger(Addr));
1042  return Unit.getOrigUnit().getAddressByteSize();
1043  }
1044 
1045  if (AttrSpec.Attr == dwarf::DW_AT_low_pc) {
1046  if (Die.getTag() == dwarf::DW_TAG_inlined_subroutine ||
1047  Die.getTag() == dwarf::DW_TAG_lexical_block)
1048  // The low_pc of a block or inline subroutine might get
1049  // relocated because it happens to match the low_pc of the
1050  // enclosing subprogram. To prevent issues with that, always use
1051  // the low_pc from the input DIE if relocations have been applied.
1052  Addr = (Info.OrigLowPc != std::numeric_limits<uint64_t>::max()
1053  ? Info.OrigLowPc
1054  : Addr) +
1055  Info.PCOffset;
1056  else if (Die.getTag() == dwarf::DW_TAG_compile_unit) {
1057  Addr = Unit.getLowPc();
1058  if (Addr == std::numeric_limits<uint64_t>::max())
1059  return 0;
1060  }
1061  Info.HasLowPc = true;
1062  } else if (AttrSpec.Attr == dwarf::DW_AT_high_pc) {
1063  if (Die.getTag() == dwarf::DW_TAG_compile_unit) {
1064  if (uint64_t HighPc = Unit.getHighPc())
1065  Addr = HighPc;
1066  else
1067  return 0;
1068  } else
1069  // If we have a high_pc recorded for the input DIE, use
1070  // it. Otherwise (when no relocations where applied) just use the
1071  // one we just decoded.
1072  Addr = (Info.OrigHighPc ? Info.OrigHighPc : Addr) + Info.PCOffset;
1073  } else if (AttrSpec.Attr == dwarf::DW_AT_call_return_pc) {
1074  // Relocate a return PC address within a call site entry.
1075  if (Die.getTag() == dwarf::DW_TAG_call_site)
1076  Addr = (Info.OrigCallReturnPc ? Info.OrigCallReturnPc : Addr) +
1077  Info.PCOffset;
1078  } else if (AttrSpec.Attr == dwarf::DW_AT_call_pc) {
1079  // Relocate the address of a branch instruction within a call site entry.
1080  if (Die.getTag() == dwarf::DW_TAG_call_site)
1081  Addr = (Info.OrigCallPc ? Info.OrigCallPc : Addr) + Info.PCOffset;
1082  }
1083 
1084  Die.addValue(DIEAlloc, static_cast<dwarf::Attribute>(AttrSpec.Attr),
1085  static_cast<dwarf::Form>(AttrSpec.Form), DIEInteger(Addr));
1086  return Unit.getOrigUnit().getAddressByteSize();
1087 }
1088 
1089 unsigned DWARFLinker::DIECloner::cloneScalarAttribute(
1090  DIE &Die, const DWARFDie &InputDIE, const DwarfFile &File,
1091  CompileUnit &Unit, AttributeSpec AttrSpec, const DWARFFormValue &Val,
1092  unsigned AttrSize, AttributesInfo &Info) {
1093  uint64_t Value;
1094 
1095  if (LLVM_UNLIKELY(Linker.Options.Update)) {
1096  if (auto OptionalValue = Val.getAsUnsignedConstant())
1097  Value = *OptionalValue;
1098  else if (auto OptionalValue = Val.getAsSignedConstant())
1099  Value = *OptionalValue;
1100  else if (auto OptionalValue = Val.getAsSectionOffset())
1101  Value = *OptionalValue;
1102  else {
1103  Linker.reportWarning(
1104  "Unsupported scalar attribute form. Dropping attribute.", File,
1105  &InputDIE);
1106  return 0;
1107  }
1108  if (AttrSpec.Attr == dwarf::DW_AT_declaration && Value)
1109  Info.IsDeclaration = true;
1110  Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
1111  dwarf::Form(AttrSpec.Form), DIEInteger(Value));
1112  return AttrSize;
1113  }
1114 
1115  if (AttrSpec.Attr == dwarf::DW_AT_high_pc &&
1116  Die.getTag() == dwarf::DW_TAG_compile_unit) {
1117  if (Unit.getLowPc() == -1ULL)
1118  return 0;
1119  // Dwarf >= 4 high_pc is an size, not an address.
1120  Value = Unit.getHighPc() - Unit.getLowPc();
1121  } else if (AttrSpec.Form == dwarf::DW_FORM_sec_offset)
1122  Value = *Val.getAsSectionOffset();
1123  else if (AttrSpec.Form == dwarf::DW_FORM_sdata)
1124  Value = *Val.getAsSignedConstant();
1125  else if (auto OptionalValue = Val.getAsUnsignedConstant())
1126  Value = *OptionalValue;
1127  else {
1128  Linker.reportWarning(
1129  "Unsupported scalar attribute form. Dropping attribute.", File,
1130  &InputDIE);
1131  return 0;
1132  }
1133  PatchLocation Patch =
1134  Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
1135  dwarf::Form(AttrSpec.Form), DIEInteger(Value));
1136  if (AttrSpec.Attr == dwarf::DW_AT_ranges) {
1137  Unit.noteRangeAttribute(Die, Patch);
1138  Info.HasRanges = true;
1139  }
1140 
1141  // A more generic way to check for location attributes would be
1142  // nice, but it's very unlikely that any other attribute needs a
1143  // location list.
1144  // FIXME: use DWARFAttribute::mayHaveLocationDescription().
1145  else if (AttrSpec.Attr == dwarf::DW_AT_location ||
1146  AttrSpec.Attr == dwarf::DW_AT_frame_base) {
1147  Unit.noteLocationAttribute(Patch, Info.PCOffset);
1148  } else if (AttrSpec.Attr == dwarf::DW_AT_declaration && Value)
1149  Info.IsDeclaration = true;
1150 
1151  return AttrSize;
1152 }
1153 
1154 /// Clone \p InputDIE's attribute described by \p AttrSpec with
1155 /// value \p Val, and add it to \p Die.
1156 /// \returns the size of the cloned attribute.
1157 unsigned DWARFLinker::DIECloner::cloneAttribute(
1158  DIE &Die, const DWARFDie &InputDIE, const DwarfFile &File,
1159  CompileUnit &Unit, OffsetsStringPool &StringPool, const DWARFFormValue &Val,
1160  const AttributeSpec AttrSpec, unsigned AttrSize, AttributesInfo &Info,
1161  bool IsLittleEndian) {
1162  const DWARFUnit &U = Unit.getOrigUnit();
1163 
1164  switch (AttrSpec.Form) {
1165  case dwarf::DW_FORM_strp:
1166  case dwarf::DW_FORM_string:
1167  return cloneStringAttribute(Die, AttrSpec, Val, U, StringPool, Info);
1168  case dwarf::DW_FORM_ref_addr:
1169  case dwarf::DW_FORM_ref1:
1170  case dwarf::DW_FORM_ref2:
1171  case dwarf::DW_FORM_ref4:
1172  case dwarf::DW_FORM_ref8:
1173  return cloneDieReferenceAttribute(Die, InputDIE, AttrSpec, AttrSize, Val,
1174  File, Unit);
1175  case dwarf::DW_FORM_block:
1176  case dwarf::DW_FORM_block1:
1177  case dwarf::DW_FORM_block2:
1178  case dwarf::DW_FORM_block4:
1179  case dwarf::DW_FORM_exprloc:
1180  return cloneBlockAttribute(Die, File, Unit, AttrSpec, Val, AttrSize,
1181  IsLittleEndian);
1182  case dwarf::DW_FORM_addr:
1183  return cloneAddressAttribute(Die, AttrSpec, Val, Unit, Info);
1184  case dwarf::DW_FORM_data1:
1185  case dwarf::DW_FORM_data2:
1186  case dwarf::DW_FORM_data4:
1187  case dwarf::DW_FORM_data8:
1188  case dwarf::DW_FORM_udata:
1189  case dwarf::DW_FORM_sdata:
1190  case dwarf::DW_FORM_sec_offset:
1191  case dwarf::DW_FORM_flag:
1192  case dwarf::DW_FORM_flag_present:
1193  return cloneScalarAttribute(Die, InputDIE, File, Unit, AttrSpec, Val,
1194  AttrSize, Info);
1195  default:
1196  Linker.reportWarning(
1197  "Unsupported attribute form in cloneAttribute. Dropping.", File,
1198  &InputDIE);
1199  }
1200 
1201  return 0;
1202 }
1203 
1205  return Name.size() > 2 && (Name[0] == '-' || Name[0] == '+') &&
1206  (Name[1] == '[');
1207 }
1208 
1209 void DWARFLinker::DIECloner::addObjCAccelerator(CompileUnit &Unit,
1210  const DIE *Die,
1212  OffsetsStringPool &StringPool,
1213  bool SkipPubSection) {
1214  assert(isObjCSelector(Name.getString()) && "not an objc selector");
1215  // Objective C method or class function.
1216  // "- [Class(Category) selector :withArg ...]"
1217  StringRef ClassNameStart(Name.getString().drop_front(2));
1218  size_t FirstSpace = ClassNameStart.find(' ');
1219  if (FirstSpace == StringRef::npos)
1220  return;
1221 
1222  StringRef SelectorStart(ClassNameStart.data() + FirstSpace + 1);
1223  if (!SelectorStart.size())
1224  return;
1225 
1226  StringRef Selector(SelectorStart.data(), SelectorStart.size() - 1);
1227  Unit.addNameAccelerator(Die, StringPool.getEntry(Selector), SkipPubSection);
1228 
1229  // Add an entry for the class name that points to this
1230  // method/class function.
1231  StringRef ClassName(ClassNameStart.data(), FirstSpace);
1232  Unit.addObjCAccelerator(Die, StringPool.getEntry(ClassName), SkipPubSection);
1233 
1234  if (ClassName[ClassName.size() - 1] == ')') {
1235  size_t OpenParens = ClassName.find('(');
1236  if (OpenParens != StringRef::npos) {
1237  StringRef ClassNameNoCategory(ClassName.data(), OpenParens);
1238  Unit.addObjCAccelerator(Die, StringPool.getEntry(ClassNameNoCategory),
1239  SkipPubSection);
1240 
1241  std::string MethodNameNoCategory(Name.getString().data(), OpenParens + 2);
1242  // FIXME: The missing space here may be a bug, but
1243  // dsymutil-classic also does it this way.
1244  MethodNameNoCategory.append(std::string(SelectorStart));
1245  Unit.addNameAccelerator(Die, StringPool.getEntry(MethodNameNoCategory),
1246  SkipPubSection);
1247  }
1248  }
1249 }
1250 
1251 static bool
1253  uint16_t Tag, bool InDebugMap, bool SkipPC,
1254  bool InFunctionScope) {
1255  switch (AttrSpec.Attr) {
1256  default:
1257  return false;
1258  case dwarf::DW_AT_low_pc:
1259  case dwarf::DW_AT_high_pc:
1260  case dwarf::DW_AT_ranges:
1261  return SkipPC;
1262  case dwarf::DW_AT_location:
1263  case dwarf::DW_AT_frame_base:
1264  // FIXME: for some reason dsymutil-classic keeps the location attributes
1265  // when they are of block type (i.e. not location lists). This is totally
1266  // wrong for globals where we will keep a wrong address. It is mostly
1267  // harmless for locals, but there is no point in keeping these anyway when
1268  // the function wasn't linked.
1269  return (SkipPC || (!InFunctionScope && Tag == dwarf::DW_TAG_variable &&
1270  !InDebugMap)) &&
1272  }
1273 }
1274 
1275 DIE *DWARFLinker::DIECloner::cloneDIE(const DWARFDie &InputDIE,
1276  const DwarfFile &File, CompileUnit &Unit,
1277  OffsetsStringPool &StringPool,
1278  int64_t PCOffset, uint32_t OutOffset,
1279  unsigned Flags, bool IsLittleEndian,
1280  DIE *Die) {
1281  DWARFUnit &U = Unit.getOrigUnit();
1282  unsigned Idx = U.getDIEIndex(InputDIE);
1283  CompileUnit::DIEInfo &Info = Unit.getInfo(Idx);
1284 
1285  // Should the DIE appear in the output?
1286  if (!Unit.getInfo(Idx).Keep)
1287  return nullptr;
1288 
1289  uint64_t Offset = InputDIE.getOffset();
1290  assert(!(Die && Info.Clone) && "Can't supply a DIE and a cloned DIE");
1291  if (!Die) {
1292  // The DIE might have been already created by a forward reference
1293  // (see cloneDieReferenceAttribute()).
1294  if (!Info.Clone)
1295  Info.Clone = DIE::get(DIEAlloc, dwarf::Tag(InputDIE.getTag()));
1296  Die = Info.Clone;
1297  }
1298 
1299  assert(Die->getTag() == InputDIE.getTag());
1300  Die->setOffset(OutOffset);
1301  if ((Unit.hasODR() || Unit.isClangModule()) && !Info.Incomplete &&
1302  Die->getTag() != dwarf::DW_TAG_namespace && Info.Ctxt &&
1303  Info.Ctxt != Unit.getInfo(Info.ParentIdx).Ctxt &&
1304  !Info.Ctxt->getCanonicalDIEOffset()) {
1305  // We are about to emit a DIE that is the root of its own valid
1306  // DeclContext tree. Make the current offset the canonical offset
1307  // for this context.
1308  Info.Ctxt->setCanonicalDIEOffset(OutOffset + Unit.getStartOffset());
1309  }
1310 
1311  // Extract and clone every attribute.
1313  // Point to the next DIE (generally there is always at least a NULL
1314  // entry after the current one). If this is a lone
1315  // DW_TAG_compile_unit without any children, point to the next unit.
1316  uint64_t NextOffset = (Idx + 1 < U.getNumDIEs())
1317  ? U.getDIEAtIndex(Idx + 1).getOffset()
1318  : U.getNextUnitOffset();
1319  AttributesInfo AttrInfo;
1320 
1321  // We could copy the data only if we need to apply a relocation to it. After
1322  // testing, it seems there is no performance downside to doing the copy
1323  // unconditionally, and it makes the code simpler.
1324  SmallString<40> DIECopy(Data.getData().substr(Offset, NextOffset - Offset));
1325  Data =
1326  DWARFDataExtractor(DIECopy, Data.isLittleEndian(), Data.getAddressSize());
1327 
1328  // Modify the copy with relocated addresses.
1329  if (ObjFile.Addresses->areRelocationsResolved() &&
1330  ObjFile.Addresses->applyValidRelocs(DIECopy, Offset,
1331  Data.isLittleEndian())) {
1332  // If we applied relocations, we store the value of high_pc that was
1333  // potentially stored in the input DIE. If high_pc is an address
1334  // (Dwarf version == 2), then it might have been relocated to a
1335  // totally unrelated value (because the end address in the object
1336  // file might be start address of another function which got moved
1337  // independently by the linker). The computation of the actual
1338  // high_pc value is done in cloneAddressAttribute().
1339  AttrInfo.OrigHighPc =
1340  dwarf::toAddress(InputDIE.find(dwarf::DW_AT_high_pc), 0);
1341  // Also store the low_pc. It might get relocated in an
1342  // inline_subprogram that happens at the beginning of its
1343  // inlining function.
1344  AttrInfo.OrigLowPc = dwarf::toAddress(InputDIE.find(dwarf::DW_AT_low_pc),
1346  AttrInfo.OrigCallReturnPc =
1347  dwarf::toAddress(InputDIE.find(dwarf::DW_AT_call_return_pc), 0);
1348  AttrInfo.OrigCallPc =
1349  dwarf::toAddress(InputDIE.find(dwarf::DW_AT_call_pc), 0);
1350  }
1351 
1352  // Reset the Offset to 0 as we will be working on the local copy of
1353  // the data.
1354  Offset = 0;
1355 
1356  const auto *Abbrev = InputDIE.getAbbreviationDeclarationPtr();
1357  Offset += getULEB128Size(Abbrev->getCode());
1358 
1359  // We are entering a subprogram. Get and propagate the PCOffset.
1360  if (Die->getTag() == dwarf::DW_TAG_subprogram)
1361  PCOffset = Info.AddrAdjust;
1362  AttrInfo.PCOffset = PCOffset;
1363 
1364  if (Abbrev->getTag() == dwarf::DW_TAG_subprogram) {
1365  Flags |= TF_InFunctionScope;
1366  if (!Info.InDebugMap && LLVM_LIKELY(!Update))
1367  Flags |= TF_SkipPC;
1368  }
1369 
1370  bool Copied = false;
1371  for (const auto &AttrSpec : Abbrev->attributes()) {
1372  if (LLVM_LIKELY(!Update) &&
1373  shouldSkipAttribute(AttrSpec, Die->getTag(), Info.InDebugMap,
1374  Flags & TF_SkipPC, Flags & TF_InFunctionScope)) {
1375  DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset,
1376  U.getFormParams());
1377  // FIXME: dsymutil-classic keeps the old abbreviation around
1378  // even if it's not used. We can remove this (and the copyAbbrev
1379  // helper) as soon as bit-for-bit compatibility is not a goal anymore.
1380  if (!Copied) {
1381  copyAbbrev(*InputDIE.getAbbreviationDeclarationPtr(), Unit.hasODR());
1382  Copied = true;
1383  }
1384  continue;
1385  }
1386 
1387  DWARFFormValue Val(AttrSpec.Form);
1388  uint64_t AttrSize = Offset;
1389  Val.extractValue(Data, &Offset, U.getFormParams(), &U);
1390  AttrSize = Offset - AttrSize;
1391 
1392  OutOffset += cloneAttribute(*Die, InputDIE, File, Unit, StringPool, Val,
1393  AttrSpec, AttrSize, AttrInfo, IsLittleEndian);
1394  }
1395 
1396  // Look for accelerator entries.
1397  uint16_t Tag = InputDIE.getTag();
1398  // FIXME: This is slightly wrong. An inline_subroutine without a
1399  // low_pc, but with AT_ranges might be interesting to get into the
1400  // accelerator tables too. For now stick with dsymutil's behavior.
1401  if ((Info.InDebugMap || AttrInfo.HasLowPc || AttrInfo.HasRanges) &&
1402  Tag != dwarf::DW_TAG_compile_unit &&
1403  getDIENames(InputDIE, AttrInfo, StringPool,
1404  Tag != dwarf::DW_TAG_inlined_subroutine)) {
1405  if (AttrInfo.MangledName && AttrInfo.MangledName != AttrInfo.Name)
1406  Unit.addNameAccelerator(Die, AttrInfo.MangledName,
1407  Tag == dwarf::DW_TAG_inlined_subroutine);
1408  if (AttrInfo.Name) {
1409  if (AttrInfo.NameWithoutTemplate)
1410  Unit.addNameAccelerator(Die, AttrInfo.NameWithoutTemplate,
1411  /* SkipPubSection */ true);
1412  Unit.addNameAccelerator(Die, AttrInfo.Name,
1413  Tag == dwarf::DW_TAG_inlined_subroutine);
1414  }
1415  if (AttrInfo.Name && isObjCSelector(AttrInfo.Name.getString()))
1416  addObjCAccelerator(Unit, Die, AttrInfo.Name, StringPool,
1417  /* SkipPubSection =*/true);
1418 
1419  } else if (Tag == dwarf::DW_TAG_namespace) {
1420  if (!AttrInfo.Name)
1421  AttrInfo.Name = StringPool.getEntry("(anonymous namespace)");
1422  Unit.addNamespaceAccelerator(Die, AttrInfo.Name);
1423  } else if (isTypeTag(Tag) && !AttrInfo.IsDeclaration &&
1424  getDIENames(InputDIE, AttrInfo, StringPool) && AttrInfo.Name &&
1425  AttrInfo.Name.getString()[0]) {
1426  uint32_t Hash = hashFullyQualifiedName(InputDIE, Unit, File);
1427  uint64_t RuntimeLang =
1428  dwarf::toUnsigned(InputDIE.find(dwarf::DW_AT_APPLE_runtime_class))
1429  .getValueOr(0);
1430  bool ObjCClassIsImplementation =
1431  (RuntimeLang == dwarf::DW_LANG_ObjC ||
1432  RuntimeLang == dwarf::DW_LANG_ObjC_plus_plus) &&
1433  dwarf::toUnsigned(InputDIE.find(dwarf::DW_AT_APPLE_objc_complete_type))
1434  .getValueOr(0);
1435  Unit.addTypeAccelerator(Die, AttrInfo.Name, ObjCClassIsImplementation,
1436  Hash);
1437  }
1438 
1439  // Determine whether there are any children that we want to keep.
1440  bool HasChildren = false;
1441  for (auto Child : InputDIE.children()) {
1442  unsigned Idx = U.getDIEIndex(Child);
1443  if (Unit.getInfo(Idx).Keep) {
1444  HasChildren = true;
1445  break;
1446  }
1447  }
1448 
1449  DIEAbbrev NewAbbrev = Die->generateAbbrev();
1450  if (HasChildren)
1452  // Assign a permanent abbrev number
1453  Linker.assignAbbrev(NewAbbrev);
1454  Die->setAbbrevNumber(NewAbbrev.getNumber());
1455 
1456  // Add the size of the abbreviation number to the output offset.
1457  OutOffset += getULEB128Size(Die->getAbbrevNumber());
1458 
1459  if (!HasChildren) {
1460  // Update our size.
1461  Die->setSize(OutOffset - Die->getOffset());
1462  return Die;
1463  }
1464 
1465  // Recursively clone children.
1466  for (auto Child : InputDIE.children()) {
1467  if (DIE *Clone = cloneDIE(Child, File, Unit, StringPool, PCOffset,
1468  OutOffset, Flags, IsLittleEndian)) {
1469  Die->addChild(Clone);
1470  OutOffset = Clone->getOffset() + Clone->getSize();
1471  }
1472  }
1473 
1474  // Account for the end of children marker.
1475  OutOffset += sizeof(int8_t);
1476  // Update our size.
1477  Die->setSize(OutOffset - Die->getOffset());
1478  return Die;
1479 }
1480 
1481 /// Patch the input object file relevant debug_ranges entries
1482 /// and emit them in the output file. Update the relevant attributes
1483 /// to point at the new entries.
1484 void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
1485  DWARFContext &OrigDwarf,
1486  const DwarfFile &File) const {
1487  DWARFDebugRangeList RangeList;
1488  const auto &FunctionRanges = Unit.getFunctionRanges();
1489  unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
1490  DWARFDataExtractor RangeExtractor(OrigDwarf.getDWARFObj(),
1491  OrigDwarf.getDWARFObj().getRangesSection(),
1492  OrigDwarf.isLittleEndian(), AddressSize);
1493  auto InvalidRange = FunctionRanges.end(), CurrRange = InvalidRange;
1494  DWARFUnit &OrigUnit = Unit.getOrigUnit();
1495  auto OrigUnitDie = OrigUnit.getUnitDIE(false);
1496  uint64_t OrigLowPc =
1497  dwarf::toAddress(OrigUnitDie.find(dwarf::DW_AT_low_pc), -1ULL);
1498  // Ranges addresses are based on the unit's low_pc. Compute the
1499  // offset we need to apply to adapt to the new unit's low_pc.
1500  int64_t UnitPcOffset = 0;
1501  if (OrigLowPc != -1ULL)
1502  UnitPcOffset = int64_t(OrigLowPc) - Unit.getLowPc();
1503 
1504  for (const auto &RangeAttribute : Unit.getRangesAttributes()) {
1505  uint64_t Offset = RangeAttribute.get();
1506  RangeAttribute.set(TheDwarfEmitter->getRangesSectionSize());
1507  if (Error E = RangeList.extract(RangeExtractor, &Offset)) {
1508  llvm::consumeError(std::move(E));
1509  reportWarning("invalid range list ignored.", File);
1510  RangeList.clear();
1511  }
1512  const auto &Entries = RangeList.getEntries();
1513  if (!Entries.empty()) {
1514  const DWARFDebugRangeList::RangeListEntry &First = Entries.front();
1515 
1516  if (CurrRange == InvalidRange ||
1517  First.StartAddress + OrigLowPc < CurrRange.start() ||
1518  First.StartAddress + OrigLowPc >= CurrRange.stop()) {
1519  CurrRange = FunctionRanges.find(First.StartAddress + OrigLowPc);
1520  if (CurrRange == InvalidRange ||
1521  CurrRange.start() > First.StartAddress + OrigLowPc) {
1522  reportWarning("no mapping for range.", File);
1523  continue;
1524  }
1525  }
1526  }
1527 
1528  TheDwarfEmitter->emitRangesEntries(UnitPcOffset, OrigLowPc, CurrRange,
1529  Entries, AddressSize);
1530  }
1531 }
1532 
1533 /// Generate the debug_aranges entries for \p Unit and if the
1534 /// unit has a DW_AT_ranges attribute, also emit the debug_ranges
1535 /// contribution for this attribute.
1536 /// FIXME: this could actually be done right in patchRangesForUnit,
1537 /// but for the sake of initial bit-for-bit compatibility with legacy
1538 /// dsymutil, we have to do it in a delayed pass.
1539 void DWARFLinker::generateUnitRanges(CompileUnit &Unit) const {
1540  auto Attr = Unit.getUnitRangesAttribute();
1541  if (Attr)
1542  Attr->set(TheDwarfEmitter->getRangesSectionSize());
1543  TheDwarfEmitter->emitUnitRangesEntries(Unit, static_cast<bool>(Attr));
1544 }
1545 
1546 /// Insert the new line info sequence \p Seq into the current
1547 /// set of already linked line info \p Rows.
1548 static void insertLineSequence(std::vector<DWARFDebugLine::Row> &Seq,
1549  std::vector<DWARFDebugLine::Row> &Rows) {
1550  if (Seq.empty())
1551  return;
1552 
1553  if (!Rows.empty() && Rows.back().Address < Seq.front().Address) {
1554  Rows.insert(Rows.end(), Seq.begin(), Seq.end());
1555  Seq.clear();
1556  return;
1557  }
1558 
1559  object::SectionedAddress Front = Seq.front().Address;
1560  auto InsertPoint = partition_point(
1561  Rows, [=](const DWARFDebugLine::Row &O) { return O.Address < Front; });
1562 
1563  // FIXME: this only removes the unneeded end_sequence if the
1564  // sequences have been inserted in order. Using a global sort like
1565  // described in patchLineTableForUnit() and delaying the end_sequene
1566  // elimination to emitLineTableForUnit() we can get rid of all of them.
1567  if (InsertPoint != Rows.end() && InsertPoint->Address == Front &&
1568  InsertPoint->EndSequence) {
1569  *InsertPoint = Seq.front();
1570  Rows.insert(InsertPoint + 1, Seq.begin() + 1, Seq.end());
1571  } else {
1572  Rows.insert(InsertPoint, Seq.begin(), Seq.end());
1573  }
1574 
1575  Seq.clear();
1576 }
1577 
1578 static void patchStmtList(DIE &Die, DIEInteger Offset) {
1579  for (auto &V : Die.values())
1580  if (V.getAttribute() == dwarf::DW_AT_stmt_list) {
1581  V = DIEValue(V.getAttribute(), V.getForm(), Offset);
1582  return;
1583  }
1584 
1585  llvm_unreachable("Didn't find DW_AT_stmt_list in cloned DIE!");
1586 }
1587 
1588 /// Extract the line table for \p Unit from \p OrigDwarf, and
1589 /// recreate a relocated version of these for the address ranges that
1590 /// are present in the binary.
1591 void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
1592  DWARFContext &OrigDwarf,
1593  const DwarfFile &File) {
1594  DWARFDie CUDie = Unit.getOrigUnit().getUnitDIE();
1595  auto StmtList = dwarf::toSectionOffset(CUDie.find(dwarf::DW_AT_stmt_list));
1596  if (!StmtList)
1597  return;
1598 
1599  // Update the cloned DW_AT_stmt_list with the correct debug_line offset.
1600  if (auto *OutputDIE = Unit.getOutputUnitDIE())
1601  patchStmtList(*OutputDIE,
1602  DIEInteger(TheDwarfEmitter->getLineSectionSize()));
1603 
1604  RangesTy &Ranges = File.Addresses->getValidAddressRanges();
1605 
1606  // Parse the original line info for the unit.
1607  DWARFDebugLine::LineTable LineTable;
1608  uint64_t StmtOffset = *StmtList;
1609  DWARFDataExtractor LineExtractor(
1610  OrigDwarf.getDWARFObj(), OrigDwarf.getDWARFObj().getLineSection(),
1611  OrigDwarf.isLittleEndian(), Unit.getOrigUnit().getAddressByteSize());
1612  if (needToTranslateStrings())
1613  return TheDwarfEmitter->translateLineTable(LineExtractor, StmtOffset);
1614 
1615  if (Error Err =
1616  LineTable.parse(LineExtractor, &StmtOffset, OrigDwarf,
1617  &Unit.getOrigUnit(), OrigDwarf.getWarningHandler()))
1618  OrigDwarf.getWarningHandler()(std::move(Err));
1619 
1620  // This vector is the output line table.
1621  std::vector<DWARFDebugLine::Row> NewRows;
1622  NewRows.reserve(LineTable.Rows.size());
1623 
1624  // Current sequence of rows being extracted, before being inserted
1625  // in NewRows.
1626  std::vector<DWARFDebugLine::Row> Seq;
1627  const auto &FunctionRanges = Unit.getFunctionRanges();
1628  auto InvalidRange = FunctionRanges.end(), CurrRange = InvalidRange;
1629 
1630  // FIXME: This logic is meant to generate exactly the same output as
1631  // Darwin's classic dsymutil. There is a nicer way to implement this
1632  // by simply putting all the relocated line info in NewRows and simply
1633  // sorting NewRows before passing it to emitLineTableForUnit. This
1634  // should be correct as sequences for a function should stay
1635  // together in the sorted output. There are a few corner cases that
1636  // look suspicious though, and that required to implement the logic
1637  // this way. Revisit that once initial validation is finished.
1638 
1639  // Iterate over the object file line info and extract the sequences
1640  // that correspond to linked functions.
1641  for (auto &Row : LineTable.Rows) {
1642  // Check whether we stepped out of the range. The range is
1643  // half-open, but consider accept the end address of the range if
1644  // it is marked as end_sequence in the input (because in that
1645  // case, the relocation offset is accurate and that entry won't
1646  // serve as the start of another function).
1647  if (CurrRange == InvalidRange || Row.Address.Address < CurrRange.start() ||
1648  Row.Address.Address > CurrRange.stop() ||
1649  (Row.Address.Address == CurrRange.stop() && !Row.EndSequence)) {
1650  // We just stepped out of a known range. Insert a end_sequence
1651  // corresponding to the end of the range.
1652  uint64_t StopAddress = CurrRange != InvalidRange
1653  ? CurrRange.stop() + CurrRange.value()
1654  : -1ULL;
1655  CurrRange = FunctionRanges.find(Row.Address.Address);
1656  bool CurrRangeValid =
1657  CurrRange != InvalidRange && CurrRange.start() <= Row.Address.Address;
1658  if (!CurrRangeValid) {
1659  CurrRange = InvalidRange;
1660  if (StopAddress != -1ULL) {
1661  // Try harder by looking in the Address ranges map.
1662  // There are corner cases where this finds a
1663  // valid entry. It's unclear if this is right or wrong, but
1664  // for now do as dsymutil.
1665  // FIXME: Understand exactly what cases this addresses and
1666  // potentially remove it along with the Ranges map.
1667  auto Range = Ranges.lower_bound(Row.Address.Address);
1668  if (Range != Ranges.begin() && Range != Ranges.end())
1669  --Range;
1670 
1671  if (Range != Ranges.end() && Range->first <= Row.Address.Address &&
1672  Range->second.HighPC >= Row.Address.Address) {
1673  StopAddress = Row.Address.Address + Range->second.Offset;
1674  }
1675  }
1676  }
1677  if (StopAddress != -1ULL && !Seq.empty()) {
1678  // Insert end sequence row with the computed end address, but
1679  // the same line as the previous one.
1680  auto NextLine = Seq.back();
1681  NextLine.Address.Address = StopAddress;
1682  NextLine.EndSequence = 1;
1683  NextLine.PrologueEnd = 0;
1684  NextLine.BasicBlock = 0;
1685  NextLine.EpilogueBegin = 0;
1686  Seq.push_back(NextLine);
1687  insertLineSequence(Seq, NewRows);
1688  }
1689 
1690  if (!CurrRangeValid)
1691  continue;
1692  }
1693 
1694  // Ignore empty sequences.
1695  if (Row.EndSequence && Seq.empty())
1696  continue;
1697 
1698  // Relocate row address and add it to the current sequence.
1699  Row.Address.Address += CurrRange.value();
1700  Seq.emplace_back(Row);
1701 
1702  if (Row.EndSequence)
1703  insertLineSequence(Seq, NewRows);
1704  }
1705 
1706  // Finished extracting, now emit the line tables.
1707  // FIXME: LLVM hard-codes its prologue values. We just copy the
1708  // prologue over and that works because we act as both producer and
1709  // consumer. It would be nicer to have a real configurable line
1710  // table emitter.
1711  if (LineTable.Prologue.getVersion() < 2 ||
1712  LineTable.Prologue.getVersion() > 5 ||
1714  LineTable.Prologue.OpcodeBase > 13)
1715  reportWarning("line table parameters mismatch. Cannot emit.", File);
1716  else {
1717  uint32_t PrologueEnd = *StmtList + 10 + LineTable.Prologue.PrologueLength;
1718  // DWARF v5 has an extra 2 bytes of information before the header_length
1719  // field.
1720  if (LineTable.Prologue.getVersion() == 5)
1721  PrologueEnd += 2;
1722  StringRef LineData = OrigDwarf.getDWARFObj().getLineSection().Data;
1723  MCDwarfLineTableParams Params;
1724  Params.DWARF2LineOpcodeBase = LineTable.Prologue.OpcodeBase;
1725  Params.DWARF2LineBase = LineTable.Prologue.LineBase;
1726  Params.DWARF2LineRange = LineTable.Prologue.LineRange;
1727  TheDwarfEmitter->emitLineTableForUnit(
1728  Params, LineData.slice(*StmtList + 4, PrologueEnd),
1729  LineTable.Prologue.MinInstLength, NewRows,
1730  Unit.getOrigUnit().getAddressByteSize());
1731  }
1732 }
1733 
1734 void DWARFLinker::emitAcceleratorEntriesForUnit(CompileUnit &Unit) {
1735  switch (Options.TheAccelTableKind) {
1736  case AccelTableKind::Apple:
1737  emitAppleAcceleratorEntriesForUnit(Unit);
1738  break;
1739  case AccelTableKind::Dwarf:
1740  emitDwarfAcceleratorEntriesForUnit(Unit);
1741  break;
1743  llvm_unreachable("The default must be updated to a concrete value.");
1744  break;
1745  }
1746 }
1747 
1748 void DWARFLinker::emitAppleAcceleratorEntriesForUnit(CompileUnit &Unit) {
1749  // Add namespaces.
1750  for (const auto &Namespace : Unit.getNamespaces())
1751  AppleNamespaces.addName(Namespace.Name,
1752  Namespace.Die->getOffset() + Unit.getStartOffset());
1753 
1754  /// Add names.
1755  TheDwarfEmitter->emitPubNamesForUnit(Unit);
1756  for (const auto &Pubname : Unit.getPubnames())
1757  AppleNames.addName(Pubname.Name,
1758  Pubname.Die->getOffset() + Unit.getStartOffset());
1759 
1760  /// Add types.
1761  TheDwarfEmitter->emitPubTypesForUnit(Unit);
1762  for (const auto &Pubtype : Unit.getPubtypes())
1763  AppleTypes.addName(
1764  Pubtype.Name, Pubtype.Die->getOffset() + Unit.getStartOffset(),
1765  Pubtype.Die->getTag(),
1766  Pubtype.ObjcClassImplementation ? dwarf::DW_FLAG_type_implementation
1767  : 0,
1768  Pubtype.QualifiedNameHash);
1769 
1770  /// Add ObjC names.
1771  for (const auto &ObjC : Unit.getObjC())
1772  AppleObjc.addName(ObjC.Name, ObjC.Die->getOffset() + Unit.getStartOffset());
1773 }
1774 
1775 void DWARFLinker::emitDwarfAcceleratorEntriesForUnit(CompileUnit &Unit) {
1776  for (const auto &Namespace : Unit.getNamespaces())
1777  DebugNames.addName(Namespace.Name, Namespace.Die->getOffset(),
1778  Namespace.Die->getTag(), Unit.getUniqueID());
1779  for (const auto &Pubname : Unit.getPubnames())
1780  DebugNames.addName(Pubname.Name, Pubname.Die->getOffset(),
1781  Pubname.Die->getTag(), Unit.getUniqueID());
1782  for (const auto &Pubtype : Unit.getPubtypes())
1783  DebugNames.addName(Pubtype.Name, Pubtype.Die->getOffset(),
1784  Pubtype.Die->getTag(), Unit.getUniqueID());
1785 }
1786 
1787 /// Read the frame info stored in the object, and emit the
1788 /// patched frame descriptions for the resulting file.
1789 ///
1790 /// This is actually pretty easy as the data of the CIEs and FDEs can
1791 /// be considered as black boxes and moved as is. The only thing to do
1792 /// is to patch the addresses in the headers.
1793 void DWARFLinker::patchFrameInfoForObject(const DwarfFile &File,
1794  RangesTy &Ranges,
1795  DWARFContext &OrigDwarf,
1796  unsigned AddrSize) {
1797  StringRef FrameData = OrigDwarf.getDWARFObj().getFrameSection().Data;
1798  if (FrameData.empty())
1799  return;
1800 
1801  DataExtractor Data(FrameData, OrigDwarf.isLittleEndian(), 0);
1802  uint64_t InputOffset = 0;
1803 
1804  // Store the data of the CIEs defined in this object, keyed by their
1805  // offsets.
1807 
1808  while (Data.isValidOffset(InputOffset)) {
1809  uint64_t EntryOffset = InputOffset;
1810  uint32_t InitialLength = Data.getU32(&InputOffset);
1811  if (InitialLength == 0xFFFFFFFF)
1812  return reportWarning("Dwarf64 bits no supported", File);
1813 
1814  uint32_t CIEId = Data.getU32(&InputOffset);
1815  if (CIEId == 0xFFFFFFFF) {
1816  // This is a CIE, store it.
1817  StringRef CIEData = FrameData.substr(EntryOffset, InitialLength + 4);
1818  LocalCIES[EntryOffset] = CIEData;
1819  // The -4 is to account for the CIEId we just read.
1820  InputOffset += InitialLength - 4;
1821  continue;
1822  }
1823 
1824  uint32_t Loc = Data.getUnsigned(&InputOffset, AddrSize);
1825 
1826  // Some compilers seem to emit frame info that doesn't start at
1827  // the function entry point, thus we can't just lookup the address
1828  // in the debug map. Use the AddressInfo's range map to see if the FDE
1829  // describes something that we can relocate.
1830  auto Range = Ranges.upper_bound(Loc);
1831  if (Range != Ranges.begin())
1832  --Range;
1833  if (Range == Ranges.end() || Range->first > Loc ||
1834  Range->second.HighPC <= Loc) {
1835  // The +4 is to account for the size of the InitialLength field itself.
1836  InputOffset = EntryOffset + InitialLength + 4;
1837  continue;
1838  }
1839 
1840  // This is an FDE, and we have a mapping.
1841  // Have we already emitted a corresponding CIE?
1842  StringRef CIEData = LocalCIES[CIEId];
1843  if (CIEData.empty())
1844  return reportWarning("Inconsistent debug_frame content. Dropping.", File);
1845 
1846  // Look if we already emitted a CIE that corresponds to the
1847  // referenced one (the CIE data is the key of that lookup).
1848  auto IteratorInserted = EmittedCIEs.insert(
1849  std::make_pair(CIEData, TheDwarfEmitter->getFrameSectionSize()));
1850  // If there is no CIE yet for this ID, emit it.
1851  if (IteratorInserted.second ||
1852  // FIXME: dsymutil-classic only caches the last used CIE for
1853  // reuse. Mimic that behavior for now. Just removing that
1854  // second half of the condition and the LastCIEOffset variable
1855  // makes the code DTRT.
1856  LastCIEOffset != IteratorInserted.first->getValue()) {
1857  LastCIEOffset = TheDwarfEmitter->getFrameSectionSize();
1858  IteratorInserted.first->getValue() = LastCIEOffset;
1859  TheDwarfEmitter->emitCIE(CIEData);
1860  }
1861 
1862  // Emit the FDE with updated address and CIE pointer.
1863  // (4 + AddrSize) is the size of the CIEId + initial_location
1864  // fields that will get reconstructed by emitFDE().
1865  unsigned FDERemainingBytes = InitialLength - (4 + AddrSize);
1866  TheDwarfEmitter->emitFDE(IteratorInserted.first->getValue(), AddrSize,
1867  Loc + Range->second.Offset,
1868  FrameData.substr(InputOffset, FDERemainingBytes));
1869  InputOffset += FDERemainingBytes;
1870  }
1871 }
1872 
1873 void DWARFLinker::DIECloner::copyAbbrev(
1874  const DWARFAbbreviationDeclaration &Abbrev, bool HasODR) {
1875  DIEAbbrev Copy(dwarf::Tag(Abbrev.getTag()),
1876  dwarf::Form(Abbrev.hasChildren()));
1877 
1878  for (const auto &Attr : Abbrev.attributes()) {
1879  uint16_t Form = Attr.Form;
1880  if (HasODR && isODRAttribute(Attr.Attr))
1881  Form = dwarf::DW_FORM_ref_addr;
1882  Copy.AddAttribute(dwarf::Attribute(Attr.Attr), dwarf::Form(Form));
1883  }
1884 
1885  Linker.assignAbbrev(Copy);
1886 }
1887 
1888 uint32_t DWARFLinker::DIECloner::hashFullyQualifiedName(DWARFDie DIE,
1889  CompileUnit &U,
1890  const DwarfFile &File,
1891  int ChildRecurseDepth) {
1892  const char *Name = nullptr;
1893  DWARFUnit *OrigUnit = &U.getOrigUnit();
1894  CompileUnit *CU = &U;
1896 
1897  while (1) {
1898  if (const char *CurrentName = DIE.getName(DINameKind::ShortName))
1899  Name = CurrentName;
1900 
1901  if (!(Ref = DIE.find(dwarf::DW_AT_specification)) &&
1902  !(Ref = DIE.find(dwarf::DW_AT_abstract_origin)))
1903  break;
1904 
1905  if (!Ref->isFormClass(DWARFFormValue::FC_Reference))
1906  break;
1907 
1908  CompileUnit *RefCU;
1909  if (auto RefDIE =
1910  Linker.resolveDIEReference(File, CompileUnits, *Ref, DIE, RefCU)) {
1911  CU = RefCU;
1912  OrigUnit = &RefCU->getOrigUnit();
1913  DIE = RefDIE;
1914  }
1915  }
1916 
1917  unsigned Idx = OrigUnit->getDIEIndex(DIE);
1918  if (!Name && DIE.getTag() == dwarf::DW_TAG_namespace)
1919  Name = "(anonymous namespace)";
1920 
1921  if (CU->getInfo(Idx).ParentIdx == 0 ||
1922  // FIXME: dsymutil-classic compatibility. Ignore modules.
1923  CU->getOrigUnit().getDIEAtIndex(CU->getInfo(Idx).ParentIdx).getTag() ==
1924  dwarf::DW_TAG_module)
1925  return djbHash(Name ? Name : "", djbHash(ChildRecurseDepth ? "" : "::"));
1926 
1927  DWARFDie Die = OrigUnit->getDIEAtIndex(CU->getInfo(Idx).ParentIdx);
1928  return djbHash(
1929  (Name ? Name : ""),
1930  djbHash((Name ? "::" : ""),
1931  hashFullyQualifiedName(Die, *CU, File, ++ChildRecurseDepth)));
1932 }
1933 
1934 static uint64_t getDwoId(const DWARFDie &CUDie, const DWARFUnit &Unit) {
1935  auto DwoId = dwarf::toUnsigned(
1936  CUDie.find({dwarf::DW_AT_dwo_id, dwarf::DW_AT_GNU_dwo_id}));
1937  if (DwoId)
1938  return *DwoId;
1939  return 0;
1940 }
1941 
1942 static std::string remapPath(StringRef Path,
1943  const objectPrefixMap &ObjectPrefixMap) {
1944  if (ObjectPrefixMap.empty())
1945  return Path.str();
1946 
1947  SmallString<256> p = Path;
1948  for (const auto &Entry : ObjectPrefixMap)
1949  if (llvm::sys::path::replace_path_prefix(p, Entry.first, Entry.second))
1950  break;
1951  return p.str().str();
1952 }
1953 
1954 bool DWARFLinker::registerModuleReference(
1955  DWARFDie CUDie, const DWARFUnit &Unit, const DwarfFile &File,
1957  DeclContextTree &ODRContexts, uint64_t ModulesEndOffset, unsigned &UnitID,
1958  bool IsLittleEndian, unsigned Indent, bool Quiet) {
1959  std::string PCMfile = dwarf::toString(
1960  CUDie.find({dwarf::DW_AT_dwo_name, dwarf::DW_AT_GNU_dwo_name}), "");
1961  if (PCMfile.empty())
1962  return false;
1963  if (Options.ObjectPrefixMap)
1964  PCMfile = remapPath(PCMfile, *Options.ObjectPrefixMap);
1965 
1966  // Clang module DWARF skeleton CUs abuse this for the path to the module.
1967  uint64_t DwoId = getDwoId(CUDie, Unit);
1968 
1969  std::string Name = dwarf::toString(CUDie.find(dwarf::DW_AT_name), "");
1970  if (Name.empty()) {
1971  if (!Quiet)
1972  reportWarning("Anonymous module skeleton CU for " + PCMfile, File);
1973  return true;
1974  }
1975 
1976  if (!Quiet && Options.Verbose) {
1977  outs().indent(Indent);
1978  outs() << "Found clang module reference " << PCMfile;
1979  }
1980 
1981  auto Cached = ClangModules.find(PCMfile);
1982  if (Cached != ClangModules.end()) {
1983  // FIXME: Until PR27449 (https://llvm.org/bugs/show_bug.cgi?id=27449) is
1984  // fixed in clang, only warn about DWO_id mismatches in verbose mode.
1985  // ASTFileSignatures will change randomly when a module is rebuilt.
1986  if (!Quiet && Options.Verbose && (Cached->second != DwoId))
1987  reportWarning(Twine("hash mismatch: this object file was built against a "
1988  "different version of the module ") +
1989  PCMfile,
1990  File);
1991  if (!Quiet && Options.Verbose)
1992  outs() << " [cached].\n";
1993  return true;
1994  }
1995  if (!Quiet && Options.Verbose)
1996  outs() << " ...\n";
1997 
1998  // Cyclic dependencies are disallowed by Clang, but we still
1999  // shouldn't run into an infinite loop, so mark it as processed now.
2000  ClangModules.insert({PCMfile, DwoId});
2001 
2002  if (Error E =
2003  loadClangModule(CUDie, PCMfile, Name, DwoId, File, StringPool,
2004  UniquingStringPool, ODRContexts, ModulesEndOffset,
2005  UnitID, IsLittleEndian, Indent + 2, Quiet)) {
2006  consumeError(std::move(E));
2007  return false;
2008  }
2009  return true;
2010 }
2011 
2012 Error DWARFLinker::loadClangModule(
2013  DWARFDie CUDie, StringRef Filename, StringRef ModuleName, uint64_t DwoId,
2014  const DwarfFile &File, OffsetsStringPool &StringPool,
2015  UniquingStringPool &UniquingStringPool, DeclContextTree &ODRContexts,
2016  uint64_t ModulesEndOffset, unsigned &UnitID, bool IsLittleEndian,
2017  unsigned Indent, bool Quiet) {
2018  /// Using a SmallString<0> because loadClangModule() is recursive.
2019  SmallString<0> Path(Options.PrependPath);
2020  if (sys::path::is_relative(Filename))
2021  resolveRelativeObjectPath(Path, CUDie);
2022  sys::path::append(Path, Filename);
2023  // Don't use the cached binary holder because we have no thread-safety
2024  // guarantee and the lifetime is limited.
2025 
2026  if (Options.ObjFileLoader == nullptr)
2027  return Error::success();
2028 
2029  auto ErrOrObj = Options.ObjFileLoader(File.FileName, Path);
2030  if (!ErrOrObj)
2031  return Error::success();
2032 
2033  std::unique_ptr<CompileUnit> Unit;
2034 
2035  for (const auto &CU : ErrOrObj->Dwarf->compile_units()) {
2036  updateDwarfVersion(CU->getVersion());
2037  // Recursively get all modules imported by this one.
2038  auto CUDie = CU->getUnitDIE(false);
2039  if (!CUDie)
2040  continue;
2041  if (!registerModuleReference(
2042  CUDie, *CU, File, StringPool, UniquingStringPool, ODRContexts,
2043  ModulesEndOffset, UnitID, IsLittleEndian, Indent, Quiet)) {
2044  if (Unit) {
2045  std::string Err =
2046  (Filename +
2047  ": Clang modules are expected to have exactly 1 compile unit.\n")
2048  .str();
2049  reportError(Err, File);
2050  return make_error<StringError>(Err, inconvertibleErrorCode());
2051  }
2052  // FIXME: Until PR27449 (https://llvm.org/bugs/show_bug.cgi?id=27449) is
2053  // fixed in clang, only warn about DWO_id mismatches in verbose mode.
2054  // ASTFileSignatures will change randomly when a module is rebuilt.
2055  uint64_t PCMDwoId = getDwoId(CUDie, *CU);
2056  if (PCMDwoId != DwoId) {
2057  if (!Quiet && Options.Verbose)
2058  reportWarning(
2059  Twine("hash mismatch: this object file was built against a "
2060  "different version of the module ") +
2061  Filename,
2062  File);
2063  // Update the cache entry with the DwoId of the module loaded from disk.
2064  ClangModules[Filename] = PCMDwoId;
2065  }
2066 
2067  // Add this module.
2068  Unit = std::make_unique<CompileUnit>(*CU, UnitID++, !Options.NoODR,
2069  ModuleName);
2070  Unit->setHasInterestingContent();
2071  analyzeContextInfo(CUDie, 0, *Unit, &ODRContexts.getRoot(),
2072  UniquingStringPool, ODRContexts, ModulesEndOffset,
2073  Options.ParseableSwiftInterfaces,
2074  [&](const Twine &Warning, const DWARFDie &DIE) {
2075  reportWarning(Warning, File, &DIE);
2076  });
2077  // Keep everything.
2078  Unit->markEverythingAsKept();
2079  }
2080  }
2081  if (!Unit->getOrigUnit().getUnitDIE().hasChildren())
2082  return Error::success();
2083  if (!Quiet && Options.Verbose) {
2084  outs().indent(Indent);
2085  outs() << "cloning .debug_info from " << Filename << "\n";
2086  }
2087 
2088  UnitListTy CompileUnits;
2089  CompileUnits.push_back(std::move(Unit));
2090  assert(TheDwarfEmitter);
2091  DIECloner(*this, TheDwarfEmitter, *ErrOrObj, DIEAlloc, CompileUnits,
2092  Options.Update)
2093  .cloneAllCompileUnits(*(ErrOrObj->Dwarf), File, StringPool,
2094  IsLittleEndian);
2095  return Error::success();
2096 }
2097 
2098 uint64_t DWARFLinker::DIECloner::cloneAllCompileUnits(
2099  DWARFContext &DwarfContext, const DwarfFile &File,
2100  OffsetsStringPool &StringPool, bool IsLittleEndian) {
2101  uint64_t OutputDebugInfoSize =
2102  Linker.Options.NoOutput ? 0 : Emitter->getDebugInfoSectionSize();
2103  const uint64_t StartOutputDebugInfoSize = OutputDebugInfoSize;
2104 
2105  for (auto &CurrentUnit : CompileUnits) {
2106  auto InputDIE = CurrentUnit->getOrigUnit().getUnitDIE();
2107  CurrentUnit->setStartOffset(OutputDebugInfoSize);
2108  if (!InputDIE) {
2109  OutputDebugInfoSize = CurrentUnit->computeNextUnitOffset();
2110  continue;
2111  }
2112  if (CurrentUnit->getInfo(0).Keep) {
2113  // Clone the InputDIE into your Unit DIE in our compile unit since it
2114  // already has a DIE inside of it.
2115  CurrentUnit->createOutputDIE();
2116  cloneDIE(InputDIE, File, *CurrentUnit, StringPool, 0 /* PC offset */,
2117  11 /* Unit Header size */, 0, IsLittleEndian,
2118  CurrentUnit->getOutputUnitDIE());
2119  }
2120 
2121  OutputDebugInfoSize = CurrentUnit->computeNextUnitOffset();
2122 
2123  if (!Linker.Options.NoOutput) {
2124  assert(Emitter);
2125 
2126  if (LLVM_LIKELY(!Linker.Options.Update) ||
2127  Linker.needToTranslateStrings())
2128  Linker.patchLineTableForUnit(*CurrentUnit, DwarfContext, File);
2129 
2130  Linker.emitAcceleratorEntriesForUnit(*CurrentUnit);
2131 
2132  if (LLVM_UNLIKELY(Linker.Options.Update))
2133  continue;
2134 
2135  Linker.patchRangesForUnit(*CurrentUnit, DwarfContext, File);
2136  auto ProcessExpr = [&](StringRef Bytes,
2137  SmallVectorImpl<uint8_t> &Buffer) {
2138  DWARFUnit &OrigUnit = CurrentUnit->getOrigUnit();
2139  DataExtractor Data(Bytes, IsLittleEndian,
2140  OrigUnit.getAddressByteSize());
2141  cloneExpression(Data,
2142  DWARFExpression(Data, OrigUnit.getAddressByteSize(),
2143  OrigUnit.getFormParams().Format),
2144  File, *CurrentUnit, Buffer);
2145  };
2146  Emitter->emitLocationsForUnit(*CurrentUnit, DwarfContext, ProcessExpr);
2147  }
2148  }
2149 
2150  if (!Linker.Options.NoOutput) {
2151  assert(Emitter);
2152  // Emit all the compile unit's debug information.
2153  for (auto &CurrentUnit : CompileUnits) {
2154  if (LLVM_LIKELY(!Linker.Options.Update))
2155  Linker.generateUnitRanges(*CurrentUnit);
2156 
2157  CurrentUnit->fixupForwardReferences();
2158 
2159  if (!CurrentUnit->getOutputUnitDIE())
2160  continue;
2161 
2162  assert(Emitter->getDebugInfoSectionSize() ==
2163  CurrentUnit->getStartOffset());
2164  Emitter->emitCompileUnitHeader(*CurrentUnit);
2165  Emitter->emitDIE(*CurrentUnit->getOutputUnitDIE());
2166  assert(Emitter->getDebugInfoSectionSize() ==
2167  CurrentUnit->computeNextUnitOffset());
2168  }
2169  }
2170 
2171  return OutputDebugInfoSize - StartOutputDebugInfoSize;
2172 }
2173 
2174 void DWARFLinker::updateAccelKind(DWARFContext &Dwarf) {
2175  if (Options.TheAccelTableKind != AccelTableKind::Default)
2176  return;
2177 
2178  auto &DwarfObj = Dwarf.getDWARFObj();
2179 
2180  if (!AtLeastOneDwarfAccelTable &&
2181  (!DwarfObj.getAppleNamesSection().Data.empty() ||
2182  !DwarfObj.getAppleTypesSection().Data.empty() ||
2183  !DwarfObj.getAppleNamespacesSection().Data.empty() ||
2184  !DwarfObj.getAppleObjCSection().Data.empty())) {
2185  AtLeastOneAppleAccelTable = true;
2186  }
2187 
2188  if (!AtLeastOneDwarfAccelTable && !DwarfObj.getNamesSection().Data.empty()) {
2189  AtLeastOneDwarfAccelTable = true;
2190  }
2191 }
2192 
2193 bool DWARFLinker::emitPaperTrailWarnings(const DwarfFile &File,
2194  OffsetsStringPool &StringPool) {
2195 
2196  if (File.Warnings.empty())
2197  return false;
2198 
2199  DIE *CUDie = DIE::get(DIEAlloc, dwarf::DW_TAG_compile_unit);
2200  CUDie->setOffset(11);
2201  StringRef Producer;
2202  StringRef WarningHeader;
2203 
2204  switch (DwarfLinkerClientID) {
2206  Producer = StringPool.internString("dsymutil");
2207  WarningHeader = "dsymutil_warning";
2208  break;
2209 
2210  default:
2211  Producer = StringPool.internString("dwarfopt");
2212  WarningHeader = "dwarfopt_warning";
2213  break;
2214  }
2215 
2216  StringRef FileName = StringPool.internString(File.FileName);
2217  CUDie->addValue(DIEAlloc, dwarf::DW_AT_producer, dwarf::DW_FORM_strp,
2218  DIEInteger(StringPool.getStringOffset(Producer)));
2219  DIEBlock *String = new (DIEAlloc) DIEBlock();
2220  DIEBlocks.push_back(String);
2221  for (auto &C : FileName)
2222  String->addValue(DIEAlloc, dwarf::Attribute(0), dwarf::DW_FORM_data1,
2223  DIEInteger(C));
2224  String->addValue(DIEAlloc, dwarf::Attribute(0), dwarf::DW_FORM_data1,
2225  DIEInteger(0));
2226 
2227  CUDie->addValue(DIEAlloc, dwarf::DW_AT_name, dwarf::DW_FORM_string, String);
2228  for (const auto &Warning : File.Warnings) {
2229  DIE &ConstDie = CUDie->addChild(DIE::get(DIEAlloc, dwarf::DW_TAG_constant));
2230  ConstDie.addValue(DIEAlloc, dwarf::DW_AT_name, dwarf::DW_FORM_strp,
2231  DIEInteger(StringPool.getStringOffset(WarningHeader)));
2232  ConstDie.addValue(DIEAlloc, dwarf::DW_AT_artificial, dwarf::DW_FORM_flag,
2233  DIEInteger(1));
2234  ConstDie.addValue(DIEAlloc, dwarf::DW_AT_const_value, dwarf::DW_FORM_strp,
2235  DIEInteger(StringPool.getStringOffset(Warning)));
2236  }
2237  unsigned Size = 4 /* FORM_strp */ + FileName.size() + 1 +
2238  File.Warnings.size() * (4 + 1 + 4) + 1 /* End of children */;
2239  DIEAbbrev Abbrev = CUDie->generateAbbrev();
2240  assignAbbrev(Abbrev);
2241  CUDie->setAbbrevNumber(Abbrev.getNumber());
2242  Size += getULEB128Size(Abbrev.getNumber());
2243  // Abbreviation ordering needed for classic compatibility.
2244  for (auto &Child : CUDie->children()) {
2245  Abbrev = Child.generateAbbrev();
2246  assignAbbrev(Abbrev);
2247  Child.setAbbrevNumber(Abbrev.getNumber());
2248  Size += getULEB128Size(Abbrev.getNumber());
2249  }
2250  CUDie->setSize(Size);
2251  TheDwarfEmitter->emitPaperTrailWarningsDie(*CUDie);
2252 
2253  return true;
2254 }
2255 
2256 void DWARFLinker::copyInvariantDebugSection(DWARFContext &Dwarf) {
2257  if (!needToTranslateStrings())
2258  TheDwarfEmitter->emitSectionContents(
2259  Dwarf.getDWARFObj().getLineSection().Data, "debug_line");
2260  TheDwarfEmitter->emitSectionContents(Dwarf.getDWARFObj().getLocSection().Data,
2261  "debug_loc");
2262  TheDwarfEmitter->emitSectionContents(
2263  Dwarf.getDWARFObj().getRangesSection().Data, "debug_ranges");
2264  TheDwarfEmitter->emitSectionContents(
2265  Dwarf.getDWARFObj().getFrameSection().Data, "debug_frame");
2266  TheDwarfEmitter->emitSectionContents(Dwarf.getDWARFObj().getArangesSection(),
2267  "debug_aranges");
2268 }
2269 
2271  ObjectContexts.emplace_back(LinkContext(File));
2272 
2273  if (ObjectContexts.back().File.Dwarf)
2274  updateAccelKind(*ObjectContexts.back().File.Dwarf);
2275 }
2276 
2278  assert(Options.NoOutput || TheDwarfEmitter);
2279 
2280  // A unique ID that identifies each compile unit.
2281  unsigned UnitID = 0;
2282 
2283  // First populate the data structure we need for each iteration of the
2284  // parallel loop.
2285  unsigned NumObjects = ObjectContexts.size();
2286 
2287  // This Dwarf string pool which is only used for uniquing. This one should
2288  // never be used for offsets as its not thread-safe or predictable.
2289  UniquingStringPool UniquingStringPool(nullptr, true);
2290 
2291  // This Dwarf string pool which is used for emission. It must be used
2292  // serially as the order of calling getStringOffset matters for
2293  // reproducibility.
2294  OffsetsStringPool OffsetsStringPool(StringsTranslator, true);
2295 
2296  // ODR Contexts for the optimize.
2297  DeclContextTree ODRContexts;
2298 
2299  // If we haven't decided on an accelerator table kind yet, we base ourselves
2300  // on the DWARF we have seen so far. At this point we haven't pulled in debug
2301  // information from modules yet, so it is technically possible that they
2302  // would affect the decision. However, as they're built with the same
2303  // compiler and flags, it is safe to assume that they will follow the
2304  // decision made here.
2305  if (Options.TheAccelTableKind == AccelTableKind::Default) {
2306  if (AtLeastOneDwarfAccelTable && !AtLeastOneAppleAccelTable)
2307  Options.TheAccelTableKind = AccelTableKind::Dwarf;
2308  else
2309  Options.TheAccelTableKind = AccelTableKind::Apple;
2310  }
2311 
2312  for (LinkContext &OptContext : ObjectContexts) {
2313  if (Options.Verbose) {
2314  if (DwarfLinkerClientID == DwarfLinkerClient::Dsymutil)
2315  outs() << "DEBUG MAP OBJECT: " << OptContext.File.FileName << "\n";
2316  else
2317  outs() << "OBJECT FILE: " << OptContext.File.FileName << "\n";
2318  }
2319 
2320  if (emitPaperTrailWarnings(OptContext.File, OffsetsStringPool))
2321  continue;
2322 
2323  if (!OptContext.File.Dwarf)
2324  continue;
2325  // Look for relocations that correspond to address map entries.
2326 
2327  // there was findvalidrelocations previously ... probably we need to gather
2328  // info here
2329  if (LLVM_LIKELY(!Options.Update) &&
2330  !OptContext.File.Addresses->hasValidRelocs()) {
2331  if (Options.Verbose)
2332  outs() << "No valid relocations found. Skipping.\n";
2333 
2334  // Set "Skip" flag as a signal to other loops that we should not
2335  // process this iteration.
2336  OptContext.Skip = true;
2337  continue;
2338  }
2339 
2340  // Setup access to the debug info.
2341  if (!OptContext.File.Dwarf)
2342  continue;
2343 
2344  // In a first phase, just read in the debug info and load all clang modules.
2345  OptContext.CompileUnits.reserve(
2346  OptContext.File.Dwarf->getNumCompileUnits());
2347 
2348  for (const auto &CU : OptContext.File.Dwarf->compile_units()) {
2349  updateDwarfVersion(CU->getVersion());
2350  auto CUDie = CU->getUnitDIE(false);
2351  if (Options.Verbose) {
2352  outs() << "Input compilation unit:";
2353  DIDumpOptions DumpOpts;
2354  DumpOpts.ChildRecurseDepth = 0;
2355  DumpOpts.Verbose = Options.Verbose;
2356  CUDie.dump(outs(), 0, DumpOpts);
2357  }
2358  if (CUDie && !LLVM_UNLIKELY(Options.Update))
2359  registerModuleReference(CUDie, *CU, OptContext.File, OffsetsStringPool,
2360  UniquingStringPool, ODRContexts, 0, UnitID,
2361  OptContext.File.Dwarf->isLittleEndian());
2362  }
2363  }
2364 
2365  // If we haven't seen any CUs, pick an arbitrary valid Dwarf version anyway.
2366  if (MaxDwarfVersion == 0)
2367  MaxDwarfVersion = 3;
2368 
2369  // At this point we know how much data we have emitted. We use this value to
2370  // compare canonical DIE offsets in analyzeContextInfo to see if a definition
2371  // is already emitted, without being affected by canonical die offsets set
2372  // later. This prevents undeterminism when analyze and clone execute
2373  // concurrently, as clone set the canonical DIE offset and analyze reads it.
2374  const uint64_t ModulesEndOffset =
2375  Options.NoOutput ? 0 : TheDwarfEmitter->getDebugInfoSectionSize();
2376 
2377  // These variables manage the list of processed object files.
2378  // The mutex and condition variable are to ensure that this is thread safe.
2379  std::mutex ProcessedFilesMutex;
2380  std::condition_variable ProcessedFilesConditionVariable;
2381  BitVector ProcessedFiles(NumObjects, false);
2382 
2383  // Analyzing the context info is particularly expensive so it is executed in
2384  // parallel with emitting the previous compile unit.
2385  auto AnalyzeLambda = [&](size_t I) {
2386  auto &Context = ObjectContexts[I];
2387 
2388  if (Context.Skip || !Context.File.Dwarf)
2389  return;
2390 
2391  for (const auto &CU : Context.File.Dwarf->compile_units()) {
2392  updateDwarfVersion(CU->getVersion());
2393  // The !registerModuleReference() condition effectively skips
2394  // over fully resolved skeleton units. This second pass of
2395  // registerModuleReferences doesn't do any new work, but it
2396  // will collect top-level errors, which are suppressed. Module
2397  // warnings were already displayed in the first iteration.
2398  bool Quiet = true;
2399  auto CUDie = CU->getUnitDIE(false);
2400  if (!CUDie || LLVM_UNLIKELY(Options.Update) ||
2401  !registerModuleReference(CUDie, *CU, Context.File, OffsetsStringPool,
2402  UniquingStringPool, ODRContexts,
2403  ModulesEndOffset, UnitID, Quiet)) {
2404  Context.CompileUnits.push_back(std::make_unique<CompileUnit>(
2405  *CU, UnitID++, !Options.NoODR && !Options.Update, ""));
2406  }
2407  }
2408 
2409  // Now build the DIE parent links that we will use during the next phase.
2410  for (auto &CurrentUnit : Context.CompileUnits) {
2411  auto CUDie = CurrentUnit->getOrigUnit().getUnitDIE();
2412  if (!CUDie)
2413  continue;
2414  analyzeContextInfo(CurrentUnit->getOrigUnit().getUnitDIE(), 0,
2415  *CurrentUnit, &ODRContexts.getRoot(),
2416  UniquingStringPool, ODRContexts, ModulesEndOffset,
2417  Options.ParseableSwiftInterfaces,
2418  [&](const Twine &Warning, const DWARFDie &DIE) {
2419  reportWarning(Warning, Context.File, &DIE);
2420  });
2421  }
2422  };
2423 
2424  // For each object file map how many bytes were emitted.
2425  StringMap<DebugInfoSize> SizeByObject;
2426 
2427  // And then the remaining work in serial again.
2428  // Note, although this loop runs in serial, it can run in parallel with
2429  // the analyzeContextInfo loop so long as we process files with indices >=
2430  // than those processed by analyzeContextInfo.
2431  auto CloneLambda = [&](size_t I) {
2432  auto &OptContext = ObjectContexts[I];
2433  if (OptContext.Skip || !OptContext.File.Dwarf)
2434  return;
2435 
2436  // Then mark all the DIEs that need to be present in the generated output
2437  // and collect some information about them.
2438  // Note that this loop can not be merged with the previous one because
2439  // cross-cu references require the ParentIdx to be setup for every CU in
2440  // the object file before calling this.
2441  if (LLVM_UNLIKELY(Options.Update)) {
2442  for (auto &CurrentUnit : OptContext.CompileUnits)
2443  CurrentUnit->markEverythingAsKept();
2444  copyInvariantDebugSection(*OptContext.File.Dwarf);
2445  } else {
2446  for (auto &CurrentUnit : OptContext.CompileUnits)
2447  lookForDIEsToKeep(*OptContext.File.Addresses,
2448  OptContext.File.Addresses->getValidAddressRanges(),
2449  OptContext.CompileUnits,
2450  CurrentUnit->getOrigUnit().getUnitDIE(),
2451  OptContext.File, *CurrentUnit, 0);
2452  }
2453 
2454  // The calls to applyValidRelocs inside cloneDIE will walk the reloc
2455  // array again (in the same way findValidRelocsInDebugInfo() did). We
2456  // need to reset the NextValidReloc index to the beginning.
2457  if (OptContext.File.Addresses->hasValidRelocs() ||
2458  LLVM_UNLIKELY(Options.Update)) {
2459  SizeByObject[OptContext.File.FileName].Input =
2460  getDebugInfoSize(*OptContext.File.Dwarf);
2461  SizeByObject[OptContext.File.FileName].Output =
2462  DIECloner(*this, TheDwarfEmitter, OptContext.File, DIEAlloc,
2463  OptContext.CompileUnits, Options.Update)
2464  .cloneAllCompileUnits(*OptContext.File.Dwarf, OptContext.File,
2465  OffsetsStringPool,
2466  OptContext.File.Dwarf->isLittleEndian());
2467  }
2468  if (!Options.NoOutput && !OptContext.CompileUnits.empty() &&
2469  LLVM_LIKELY(!Options.Update))
2470  patchFrameInfoForObject(
2471  OptContext.File, OptContext.File.Addresses->getValidAddressRanges(),
2472  *OptContext.File.Dwarf,
2473  OptContext.CompileUnits[0]->getOrigUnit().getAddressByteSize());
2474 
2475  // Clean-up before starting working on the next object.
2476  cleanupAuxiliarryData(OptContext);
2477  };
2478 
2479  auto EmitLambda = [&]() {
2480  // Emit everything that's global.
2481  if (!Options.NoOutput) {
2482  TheDwarfEmitter->emitAbbrevs(Abbreviations, MaxDwarfVersion);
2483  TheDwarfEmitter->emitStrings(OffsetsStringPool);
2484  switch (Options.TheAccelTableKind) {
2485  case AccelTableKind::Apple:
2486  TheDwarfEmitter->emitAppleNames(AppleNames);
2487  TheDwarfEmitter->emitAppleNamespaces(AppleNamespaces);
2488  TheDwarfEmitter->emitAppleTypes(AppleTypes);
2489  TheDwarfEmitter->emitAppleObjc(AppleObjc);
2490  break;
2491  case AccelTableKind::Dwarf:
2492  TheDwarfEmitter->emitDebugNames(DebugNames);
2493  break;
2495  llvm_unreachable("Default should have already been resolved.");
2496  break;
2497  }
2498  }
2499  };
2500 
2501  auto AnalyzeAll = [&]() {
2502  for (unsigned I = 0, E = NumObjects; I != E; ++I) {
2503  AnalyzeLambda(I);
2504 
2505  std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
2506  ProcessedFiles.set(I);
2507  ProcessedFilesConditionVariable.notify_one();
2508  }
2509  };
2510 
2511  auto CloneAll = [&]() {
2512  for (unsigned I = 0, E = NumObjects; I != E; ++I) {
2513  {
2514  std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
2515  if (!ProcessedFiles[I]) {
2516  ProcessedFilesConditionVariable.wait(
2517  LockGuard, [&]() { return ProcessedFiles[I]; });
2518  }
2519  }
2520 
2521  CloneLambda(I);
2522  }
2523  EmitLambda();
2524  };
2525 
2526  // To limit memory usage in the single threaded case, analyze and clone are
2527  // run sequentially so the OptContext is freed after processing each object
2528  // in endDebugObject.
2529  if (Options.Threads == 1) {
2530  for (unsigned I = 0, E = NumObjects; I != E; ++I) {
2531  AnalyzeLambda(I);
2532  CloneLambda(I);
2533  }
2534  EmitLambda();
2535  } else {
2537  Pool.async(AnalyzeAll);
2538  Pool.async(CloneAll);
2539  Pool.wait();
2540  }
2541 
2542  if (Options.Statistics) {
2543  // Create a vector sorted in descending order by output size.
2544  std::vector<std::pair<StringRef, DebugInfoSize>> Sorted;
2545  for (auto &E : SizeByObject)
2546  Sorted.emplace_back(E.first(), E.second);
2547  llvm::sort(Sorted.begin(), Sorted.end(), [](auto &LHS, auto &RHS) {
2548  return LHS.second.Output > RHS.second.Output;
2549  });
2550 
2551  auto ComputePercentange = [](int64_t Input, int64_t Output) -> float {
2552  const float Difference = Output - Input;
2553  const float Sum = Input + Output;
2554  if (Sum == 0)
2555  return 0;
2556  return (Difference / (Sum / 2));
2557  };
2558 
2559  int64_t InputTotal = 0;
2560  int64_t OutputTotal = 0;
2561  const char *FormatStr = "{0,-45} {1,10}b {2,10}b {3,8:P}\n";
2562 
2563  // Print header.
2564  outs() << ".debug_info section size (in bytes)\n";
2565  outs() << "----------------------------------------------------------------"
2566  "---------------\n";
2567  outs() << "Filename Object "
2568  " dSYM Change\n";
2569  outs() << "----------------------------------------------------------------"
2570  "---------------\n";
2571 
2572  // Print body.
2573  for (auto &E : Sorted) {
2574  InputTotal += E.second.Input;
2575  OutputTotal += E.second.Output;
2576  llvm::outs() << formatv(
2577  FormatStr, sys::path::filename(E.first).take_back(45), E.second.Input,
2578  E.second.Output, ComputePercentange(E.second.Input, E.second.Output));
2579  }
2580  // Print total and footer.
2581  outs() << "----------------------------------------------------------------"
2582  "---------------\n";
2583  llvm::outs() << formatv(FormatStr, "Total", InputTotal, OutputTotal,
2584  ComputePercentange(InputTotal, OutputTotal));
2585  outs() << "----------------------------------------------------------------"
2586  "---------------\n\n";
2587  }
2588 
2589  return true;
2590 }
2591 
2592 } // namespace llvm
A DeclContext is a named program scope that is used for ODR uniquing of types.
uint64_t CallInst * C
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:687
uint64_t getNextUnitOffset() const
Definition: DWARFUnit.h:297
BitVector & set()
Definition: BitVector.h:398
static void patchStmtList(DIE &Die, DIEInteger Offset)
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:248
LLVMContext & Context
static bool dieNeedsChildrenToBeMeaningful(uint32_t Tag)
void setSize(unsigned S)
Definition: DIE.h:827
LLVM_NODISCARD bool endswith(StringRef Suffix) const
Check if this string ends with the given Suffix.
Definition: StringRef.h:300
DIELoc - Represents an expression location.
Definition: DIE.h:914
void setDefinedInClangModule(bool Val)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
uint32_t getCanonicalDIEOffset() const
uint64_t getLowPc() const
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:219
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:218
iterator begin() const
Definition: ArrayRef.h:144
virtual bool hasValidRelocationAt(uint64_t StartOffset, uint64_t EndOffset, CompileUnit::DIEInfo &Info)=0
Checks that there is a relocation against .debug_info table between StartOffset and NextOffset...
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
bool hasLabelAt(uint64_t Addr) const
Stores all information relating to a compile unit, be it in its original instance in the object file ...
DWARF v5 .debug_names.
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:289
Attribute
Attributes.
Definition: Dwarf.h:103
bool link()
Link debug info for added objFiles.
void addNamespaceAccelerator(const DIE *Die, DwarfStringPoolEntryRef Name)
Add a name accelerator entry for Die with Name.
child_range children()
Definition: DIE.h:771
static bool isTypeTag(uint16_t Tag)
const DWARFAbbreviationDeclaration * getAbbreviationDeclarationPtr() const
Get the abbreviation declaration for this DIE.
Definition: DWARFDie.h:59
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
uint8_t MinInstLength
The size in bytes of the smallest target machine instruction.
virtual const DWARFSection & getLocSection() const
Definition: DWARFObject.h:40
uint32_t getU32(uint64_t *offset_ptr, Error *Err=nullptr) const
Extract a uint32_t value from *offset_ptr.
std::vector< std::unique_ptr< CompileUnit > > UnitListTy
Definition: DWARFLinker.h:201
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
uint8_t getRefAddrByteSize() const
Definition: DWARFUnit.h:289
StringRef getData() const
Get the data pointed to by this extractor.
Definition: DataExtractor.h:92
StrongType< NonRelocatableStringpool, UniqueTag > UniquingStringPool
bool extractValue(const DWARFDataExtractor &Data, uint64_t *OffsetPtr, dwarf::FormParams FormParams, const DWARFContext *Context=nullptr, const DWARFUnit *Unit=nullptr)
Extracts a value in Data at offset *OffsetPtr.
void AddAttribute(dwarf::Attribute Attribute, dwarf::Form Form)
Adds another set of attribute information to the abbreviation.
Definition: DIE.h:109
bool isFormClass(FormClass FC) const
void dump(raw_ostream &OS, unsigned indent=0, DIDumpOptions DumpOpts=DIDumpOptions()) const
Dump the DIE and all of its attributes to the supplied stream.
Definition: DWARFDie.cpp:582
std::shared_future< void > async(Function &&F, Args &&... ArgList)
Asynchronous submission of a task to the pool.
Definition: ThreadPool.h:54
The core of the Dwarf linking logic.
Definition: DWARFLinker.h:245
Optional< uint64_t > toAddress(const Optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract an address.
bool InDebugMap
Was this DIE&#39;s entity found in the map?
virtual const DWARFSection & getFrameSection() const
Definition: DWARFObject.h:43
const dwarf::FormParams & getFormParams() const
Definition: DWARFUnit.h:284
AddressesMap represents information about valid addresses used by debug information.
Definition: DWARFLinker.h:54
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
object::SectionedAddress Address
The program-counter value corresponding to a machine instruction generated by the compiler and sectio...
void setSize(unsigned size)
Definition: DIE.h:925
Optional< uint64_t > getAsReference() const
getAsFoo functions below return the extracted value as Foo if only DWARFFormValue has form class is s...
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:455
const char * getShortName() const
Return the DIE short name resolving DW_AT_specification or DW_AT_abstract_origin references if necess...
Definition: DWARFDie.cpp:541
virtual StringRef getArangesSection() const
Definition: DWARFObject.h:42
int64_t AddrAdjust
Address offset to apply to the described entity.
virtual const DWARFSection & getRangesSection() const
Definition: DWARFObject.h:48
iterator_range< iterator > children() const
Definition: DWARFDie.h:399
void Profile(FoldingSetNodeID &ID) const
Used to gather unique data for the abbreviation folding set.
Definition: DIE.cpp:57
static Optional< StringRef > StripTemplateParameters(StringRef Name)
static std::string remapPath(StringRef Path, const objectPrefixMap &ObjectPrefixMap)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
const std::vector< PatchLocation > & getRangesAttributes() const
const std::vector< RangeListEntry > & getEntries()
Optional< ArrayRef< uint8_t > > getAsBlock() const
LLVM_NODISCARD StringRef drop_front(size_t N=1) const
Return a StringRef equal to &#39;this&#39; but with the first N elements dropped.
Definition: StringRef.h:654
LLVM_NODISCARD size_t count(char C) const
Return the number of occurrences of C in the string.
Definition: StringRef.h:490
unit_iterator_range compile_units()
Get compile units in this context.
Definition: DWARFContext.h:166
uint32_t ParentIdx
The index of this DIE&#39;s parent.
LLVM_NODISCARD StringRef take_back(size_t N=1) const
Return a StringRef equal to &#39;this&#39; but with only the last N elements remaining.
Definition: StringRef.h:631
The access may reference the value stored in memory.
uint8_t DWARF2LineRange
Range of line offsets in a special line info. opcode.
Definition: MCDwarf.h:215
LLVM_NODISCARD StringRef slice(size_t Start, size_t End) const
Return a reference to the substring from [Start, End).
Definition: StringRef.h:713
LLVM_NODISCARD StringRef substr(size_t Start, size_t N=npos) const
Return a reference to the substring from [Start, Start + N).
Definition: StringRef.h:612
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:156
uint8_t LineRange
This parameter affects the meaning of the special opcodes. See below.
Hold the input and output of the debug info size in bytes.
Definition: DWARFLinker.cpp:38
uint8_t getAddressByteSize() const
Definition: DWARFUnit.h:288
static constexpr size_t npos
Definition: StringRef.h:59
void noteRangeAttribute(const DIE &Die, PatchLocation Attr)
Keep track of a DW_AT_range attribute that we will need to patch up later.
DIEAbbrev generateAbbrev() const
Generate the abbreviation for this DIE.
Definition: DIE.cpp:186
unsigned getNumDIEs()
Returns the number of DIEs in the unit.
Definition: DWARFUnit.h:450
This class gives a tree-like API to the DenseMap that stores the DeclContext objects.
StringRef str() const
Explicit conversion to StringRef.
Definition: SmallString.h:266
void addObjCAccelerator(const DIE *Die, DwarfStringPoolEntryRef Name, bool SkipPubnamesSection=false)
Add various accelerator entries for Die with Name which is stored in the string table at Offset...
StringRef toStringRef(const Optional< DWARFFormValue > &V, StringRef Default={})
Take an optional DWARFFormValue and try to extract a string value from it.
void addNameAccelerator(const DIE *Die, DwarfStringPoolEntryRef Name, bool SkipPubnamesSection=false)
Add a name accelerator entry for Die with Name.
uint8_t OpcodeBase
The number assigned to the first special opcode.
#define UINT64_MAX
Definition: DataTypes.h:77
Helper for making strong types.
bool hasChildren() const
Definition: DWARFDie.h:79
dwarf::Form getFormByIndex(uint32_t idx) const
void setNumber(unsigned N)
Definition: DIE.h:105
void setSize(unsigned size)
Definition: DIE.h:962
A list of DIE values.
Definition: DIE.h:646
This class provides the core functionality of linking in LLVM.
Definition: Linker.h:24
LLVM_NODISCARD size_t size() const
size - Get the string size.
Definition: StringRef.h:160
.apple_names, .apple_namespaces, .apple_types, .apple_objc.
bool isDefinedInClangModule() const
A ThreadPool for asynchronous parallel execution on a defined number of threads.
Definition: ThreadPool.h:37
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1607
static bool shouldSkipAttribute(DWARFAbbreviationDeclaration::AttributeSpec AttrSpec, uint16_t Tag, bool InDebugMap, bool SkipPC, bool InFunctionScope)
DIE & addChild(DIE *Child)
Add a child to the DIE.
Definition: DIE.h:830
static void insertLineSequence(std::vector< DWARFDebugLine::Row > &Seq, std::vector< DWARFDebugLine::Row > &Rows)
Insert the new line info sequence Seq into the current set of already linked line info Rows...
virtual ~DwarfEmitter()
Analysis containing CSE Info
Definition: CSEInfo.cpp:25
StringRef getSysRoot()
Return the DW_AT_LLVM_sysroot of the compile unit or an empty StringRef.
static void updateChildIncompleteness(const DWARFDie &Die, CompileUnit &CU, CompileUnit::DIEInfo &ChildInfo)
Helper that updates the completeness of the current DIE based on the completeness of one of its child...
Container for dump options that control which debug information will be dumped.
Definition: DIContext.h:181
std::map< std::string, std::string > objectPrefixMap
Definition: DWARFLinker.h:229
static DIE * get(BumpPtrAllocator &Alloc, dwarf::Tag Tag)
Definition: DIE.h:753
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:313
Optional< uint64_t > toSectionOffset(const Optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract an section offset.
A pointer to another debug information entry.
Definition: DIE.h:313
#define P(N)
Utility class that carries the DWARF compile/type unit and the debug info entry in an object...
Definition: DWARFDie.h:43
unsigned getUniqueID() const
uint8_t DWARF2LineOpcodeBase
First special line opcode - leave room for the standard opcodes.
Definition: MCDwarf.h:210
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
uint64_t getUnsigned(uint64_t *offset_ptr, uint32_t byte_size, Error *Err=nullptr) const
Extract an unsigned integer of size byte_size from *offset_ptr.
void addTypeAccelerator(const DIE *Die, DwarfStringPoolEntryRef Name, bool ObjcClassImplementation, uint32_t QualifiedNameHash)
Add a type accelerator entry for Die with Name which is stored in the string table at Offset...
virtual ~AddressesMap()
Instrumentation for Order File
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:156
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
value_range values()
Definition: DIE.h:711
bool hasChildren() const
Definition: DIE.h:102
uint64_t PrologueLength
The number of bytes following the prologue_length field to the beginning of the first byte of the sta...
const_iterator end() const
Definition: IntervalMap.h:1111
static bool analyzeContextInfo(const DWARFDie &DIE, unsigned ParentIdx, CompileUnit &CU, DeclContext *CurrentDeclContext, UniquingStringPool &StringPool, DeclContextTree &Contexts, uint64_t ModulesEndOffset, swiftInterfacesMap *ParseableSwiftInterfaces, std::function< void(const Twine &, const DWARFDie &)> ReportWarning, bool InImportedModule=false)
Recursive helper to build the global DeclContext information and gather the child->parent relationshi...
A structured debug information entry.
Definition: DIE.h:723
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:1632
bool Keep
Is the DIE part of the linked output?
LLVM_NODISCARD size_t find(char C, size_t From=0) const
Search for the first character C in the string.
Definition: StringRef.h:318
DIE * Clone
Cloned version of that DIE.
uint64_t getStartOffset() const
Optional< uint64_t > getAsAddress() const
Encoding
Size and signedness of expression operations&#39; operands.
Optional< uint64_t > getAsUnsignedConstant() const
bool Prune
Is this a pure forward declaration we can strip?
Error extract(const DWARFDataExtractor &data, uint64_t *offset_ptr)
static uint64_t getDebugInfoSize(DWARFContext &Dwarf)
Compute the total size of the debug info.
Definition: DWARFLinker.cpp:44
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1433
Optional< PatchLocation > getUnitRangesAttribute() const
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:1006
int8_t DWARF2LineBase
Minimum line offset in a special line info.
Definition: MCDwarf.h:213
uint32_t djbHash(StringRef Buffer, uint32_t H=5381)
The Bernstein hash function used by the DWARF accelerator tables.
Definition: DJB.h:21
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
function_ref< void(Error)> getWarningHandler()
Definition: DWARFContext.h:377
const T * data() const
Definition: ArrayRef.h:153
unsigned getULEB128Size(uint64_t Value)
Utility function to get the size of the ULEB128-encoded value.
Definition: LEB128.cpp:19
Standard .debug_line state machine structure.
std::map< std::string, std::string > swiftInterfacesMap
Definition: DWARFLinker.h:228
A DataExtractor (typically for an in-memory copy of an object-file section) plus a relocation map for...
DeclContext * Ctxt
ODR Declaration context.
DWARFDie getUnitDIE(bool ExtractUnitDIEOnly=true)
Definition: DWARFUnit.h:381
static ErrorSuccess success()
Create a success value.
Definition: Error.h:332
void noteLocationAttribute(PatchLocation Attr, int64_t PcOffset)
Keep track of a location attribute pointing to a location list in the debug_loc section.
dwarf::Tag getTag() const
Accessors.
Definition: DIE.h:100
const char * getName(DINameKind Kind) const
Return the DIE name resolving DW_AT_specification or DW_AT_abstract_origin references if necessary...
Definition: DWARFDie.cpp:530
DIE * getOutputUnitDIE() const
DIEInfo & getInfo(unsigned Idx)
static Error reportError(StringRef Message)
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
const std::string & getClangModuleName() const
const std::vector< AccelInfo > & getPubnames() const
unsigned encodeULEB128(uint64_t Value, raw_ostream &OS, unsigned PadTo=0)
Utility function to encode a ULEB128 value to an output stream.
Definition: LEB128.h:80
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
void addLabelLowPc(uint64_t LabelLowPc, int64_t PcOffset)
Add the low_pc of a label that is relocated by applying offset PCOffset.
iterator end() const
Definition: ArrayRef.h:145
static std::pair< uint64_t, uint64_t > getAttributeOffsets(const DWARFAbbreviationDeclaration *Abbrev, unsigned Idx, uint64_t Offset, const DWARFUnit &Unit)
Get the starting and ending (exclusive) offset for the attribute with index Idx descibed by Abbrev...
DWARFContext This data structure is the top level entity that deals with dwarf debug information pars...
Definition: DWARFContext.h:53
AddressesMap * Addresses
helpful address information(list of valid address ranges, relocations).
Definition: DWARFLinker.h:217
DWARFDie getDIEForOffset(uint64_t Offset)
Return the DIE object for a given offset inside the unit&#39;s DIE vector.
Definition: DWARFUnit.h:481
Partial address range.
Definition: DWARFLinker.h:34
static Optional< unsigned > getTag(const TargetRegisterInfo *TRI, const MachineInstr &MI, const LoadInfo &LI)
Optional< const char * > toString(const Optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract a string value from it.
bool isValidOffset(uint64_t offset) const
Test the validity of offset.
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:106
void noteForwardReference(DIE *Die, const CompileUnit *RefUnit, DeclContext *Ctxt, PatchLocation Attr)
Keep track of a forward reference to DIE Die in RefUnit by Attr.
PointerIntPair< DeclContext *, 1 > getChildDeclContext(DeclContext &Context, const DWARFDie &DIE, CompileUnit &Unit, UniquingStringPool &StringPool, bool InClangModule)
Get the child of Context described by DIE in Unit.
const std::vector< AccelInfo > & getNamespaces() const
iterator begin() const
Definition: StringRef.h:131
#define DWARF2_LINE_DEFAULT_IS_STMT
Definition: MCDwarf.h:85
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:433
const std::vector< AccelInfo > & getObjC() const
raw_fd_ostream & outs()
This returns a reference to a raw_fd_ostream for standard output.
dwarf::Tag getTag() const
Definition: DIE.h:759
String pool entry reference.
DWARFDataExtractor getDebugInfoExtractor() const
Definition: DWARFUnit.cpp:213
const KeyT & stop() const
stop - Return the end of the current interval.
Definition: IntervalMap.h:1367
static uint64_t getDwoId(const DWARFDie &CUDie, const DWARFUnit &Unit)
void addObjectFile(DwarfFile &File)
Add object file to be linked.
Dwarf for DWARF5 or later, Apple otherwise.
An integer value DIE.
Definition: DIE.h:163
virtual const DWARFSection & getLineSection() const
Definition: DWARFObject.h:45
Dwarf abbreviation, describes the organization of a debug information object.
Definition: DIE.h:79
DWARFDie getDIEAtIndex(unsigned Index)
Return the DIE object at the given index.
Definition: DWARFUnit.h:466
static bool isODRAttribute(uint16_t Attr)
Definition: DWARFLinker.cpp:87
StringRef filename(StringRef path, Style style=Style::native)
Get filename.
Definition: Path.cpp:577
dwarf::Tag getTag() const
Definition: DWARFDie.h:72
ThreadPoolStrategy hardware_concurrency(unsigned ThreadCount=0)
Returns a default thread strategy where all available hardware ressources are to be used...
Definition: Threading.h:217
const std::vector< AccelInfo > & getPubtypes() const
void setOffset(unsigned O)
Definition: DIE.h:826
#define I(x, y, z)
Definition: MD5.cpp:59
Optional< const char * > getAsCString() const
bool is_relative(const Twine &path, Style style=Style::native)
Is path relative?
Definition: Path.cpp:686
Error parse(DWARFDataExtractor &DebugLineData, uint64_t *OffsetPtr, const DWARFContext &Ctx, const DWARFUnit *U, function_ref< void(Error)> RecoverableErrorHandler, raw_ostream *OS=nullptr, bool Verbose=false)
Parse prologue and all rows.
static bool mayHaveLocationDescription(dwarf::Attribute Attr)
Identifies DWARF attributes that may contain a reference to a DWARF expression.
Definition: DWARFDie.cpp:722
virtual RangesTy & getValidAddressRanges()=0
Returns all valid functions address ranges(i.e., those ranges which points to sections with code)...
uint32_t Size
Definition: Profile.cpp:46
Optional< int64_t > getAsSignedConstant() const
void setChildrenFlag(bool hasChild)
Definition: DIE.h:104
unsigned ChildRecurseDepth
Definition: DIContext.h:183
bool isLittleEndian() const
Definition: DWARFContext.h:360
const DWARFObject & getDWARFObj() const
Definition: DWARFContext.h:130
const FunctionIntervals & getFunctionRanges() const
Optional< uint64_t > getHighPC(uint64_t LowPC) const
Get the DW_AT_high_pc attribute value as an address.
Definition: DWARFDie.cpp:418
void setCanonicalDIEOffset(uint32_t Offset)
uint8_t DefaultIsStmt
The initial value of theis_stmtregister.
Provides ErrorOr<T> smart pointer.
unsigned getAbbrevNumber() const
Definition: DIE.h:758
LLVM_NODISCARD const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:152
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
DwarfFormat Format
Definition: Dwarf.h:557
static void updateRefIncompleteness(const DWARFDie &Die, CompileUnit &CU, CompileUnit::DIEInfo &RefInfo)
Helper that updates the completeness of the current DIE based on the completeness of the DIEs it refe...
static bool isObjCSelector(StringRef Name)
std::map< uint64_t, ObjFileAddressRange > RangesTy
Map LowPC to ObjFileAddressRange.
Definition: DWARFLinker.h:48
Optional< DWARFFormValue > find(dwarf::Attribute Attr) const
Extract the specified attribute from this DIE.
Definition: DWARFDie.cpp:335
static CompileUnit * getUnitForOffset(const UnitListTy &Units, uint64_t Offset)
Similar to DWARFUnitSection::getUnitForOffset(), but returning our CompileUnit object instead...
Definition: DWARFLinker.cpp:54
int8_t LineBase
This parameter affects the meaning of the special opcodes. See below.
const SmallVectorImpl< DIEAbbrevData > & getData() const
Definition: DIE.h:103
unsigned getNumber() const
Definition: DIE.h:101
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
uint64_t getOffset() const
Get the absolute offset into the debug info or types section.
Definition: DWARFDie.h:67
StrongType< NonRelocatableStringpool, OffsetsTag > OffsetsStringPool
bool Incomplete
Does DIE transitively refer an incomplete decl?
void setAbbrevNumber(unsigned I)
Set the abbreviation number for this DIE.
Definition: DIE.h:787
uint64_t getHighPc() const
unsigned getOffset() const
Get the compile/type unit relative offset of this DIE.
Definition: DIE.h:761
bool replace_path_prefix(SmallVectorImpl< char > &Path, StringRef OldPrefix, StringRef NewPrefix, Style style=Style::native)
Replace matching path prefix with another path.
Definition: Path.cpp:518
print Print MemDeps of function
static void analyzeImportedModule(const DWARFDie &DIE, CompileUnit &CU, swiftInterfacesMap *ParseableSwiftInterfaces, std::function< void(const Twine &, const DWARFDie &)> ReportWarning)
Collect references to parseable Swift interfaces in imported DW_TAG_module blocks.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
bool skipValue(DataExtractor DebugInfoData, uint64_t *OffsetPtr, const dwarf::FormParams Params) const
Skip a form&#39;s value in DebugInfoData at the offset specified by OffsetPtr.
Class representing an expression and its matching format.
DIEBlock - Represents a block of values.
Definition: DIE.h:951
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:341
this class represents DWARF information for source file and it`s address map.
Definition: DWARFLinker.h:205
Information gathered about a DIE in the object file.
iterator end() const
Definition: StringRef.h:133
Optional< uint64_t > getAsSectionOffset() const
const char * getLinkageName() const
Return the DIE linkage name resolving DW_AT_specification or DW_AT_abstract_origin references if nece...
Definition: DWARFDie.cpp:548
void wait()
Blocking wait for all the threads to complete and the queue to be empty.
Definition: ThreadPool.cpp:69
uint64_t StartAddress
A beginning address offset.
static void resolveRelativeObjectPath(SmallVectorImpl< char > &Buf, DWARFDie CU)
Resolve the relative path to a build artifact referenced by DWARF by applying DW_AT_comp_dir.
const std::vector< std::string > & Warnings
warnings for object file.
Definition: DWARFLinker.h:219
value_iterator addValue(BumpPtrAllocator &Alloc, const DIEValue &V)
Definition: DIE.h:697
StringRef FileName
object file name.
Definition: DWARFLinker.h:213
Optional< uint64_t > toUnsigned(const Optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract an unsigned constant.
void addFunctionRange(uint64_t LowPC, uint64_t HighPC, int64_t PCOffset)
Add a function range [LowPC, HighPC) that is relocated by applying offset PCOffset.
std::error_code inconvertibleErrorCode()
The value returned by this function can be returned from convertToErrorCode for Error values where no...
Definition: Error.cpp:77
DWARFUnit & getOrigUnit() const