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
9#include "llvm/DWARFLinker/Classic/DWARFLinker.h"
10#include "llvm/ADT/ArrayRef.h"
11#include "llvm/ADT/BitVector.h"
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/StringExtras.h"
14#include "llvm/CodeGen/NonRelocatableStringpool.h"
15#include "llvm/DWARFLinker/Classic/DWARFLinkerDeclContext.h"
16#include "llvm/DWARFLinker/Classic/DWARFStreamer.h"
17#include "llvm/DWARFLinker/Utils.h"
18#include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
19#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
20#include "llvm/DebugInfo/DWARF/DWARFContext.h"
21#include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
22#include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
23#include "llvm/DebugInfo/DWARF/DWARFDebugMacro.h"
24#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
25#include "llvm/DebugInfo/DWARF/DWARFDie.h"
26#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
27#include "llvm/DebugInfo/DWARF/DWARFSection.h"
28#include "llvm/DebugInfo/DWARF/DWARFUnit.h"
29#include "llvm/DebugInfo/DWARF/LowLevel/DWARFExpression.h"
30#include "llvm/MC/MCDwarf.h"
31#include "llvm/Support/DataExtractor.h"
32#include "llvm/Support/Error.h"
33#include "llvm/Support/ErrorHandling.h"
34#include "llvm/Support/ErrorOr.h"
35#include "llvm/Support/FormatVariadic.h"
36#include "llvm/Support/LEB128.h"
37#include "llvm/Support/Path.h"
38#include "llvm/Support/ThreadPool.h"
39#include <vector>
40
41namespace llvm {
42
43using namespace dwarf_linker;
44using namespace dwarf_linker::classic;
45
46/// Hold the input and output of the debug info size in bytes.
47struct DebugInfoSize {
48 uint64_t Input;
49 uint64_t Output;
50};
51
52/// Compute the total size of the debug info.
53static uint64_t getDebugInfoSize(DWARFContext &Dwarf) {
54 uint64_t Size = 0;
55 for (auto &Unit : Dwarf.compile_units()) {
56 Size += Unit->getLength();
57 }
58 return Size;
59}
60
61/// Similar to DWARFUnitSection::getUnitForOffset(), but returning our
62/// CompileUnit object instead.
63static CompileUnit *getUnitForOffset(const UnitListTy &Units, uint64_t Offset) {
64 auto CU = llvm::upper_bound(
65 Range: Units, Value&: Offset, C: [](uint64_t LHS, const std::unique_ptr<CompileUnit> &RHS) {
66 return LHS < RHS->getOrigUnit().getNextUnitOffset();
67 });
68 return CU != Units.end() ? CU->get() : nullptr;
69}
70
71/// Resolve the DIE attribute reference that has been extracted in \p RefValue.
72/// The resulting DIE might be in another CompileUnit which is stored into \p
73/// ReferencedCU. \returns null if resolving fails for any reason.
74DWARFDie DWARFLinker::resolveDIEReference(const DWARFFile &File,
75 const UnitListTy &Units,
76 const DWARFFormValue &RefValue,
77 const DWARFDie &DIE,
78 CompileUnit *&RefCU) {
79 assert(RefValue.isFormClass(DWARFFormValue::FC_Reference));
80 uint64_t RefOffset;
81 if (std::optional<uint64_t> Off = RefValue.getAsRelativeReference()) {
82 RefOffset = RefValue.getUnit()->getOffset() + *Off;
83 } else if (Off = RefValue.getAsDebugInfoReference(); Off) {
84 RefOffset = *Off;
85 } else {
86 reportWarning(Warning: "Unsupported reference type", File, DIE: &DIE);
87 return DWARFDie();
88 }
89 if ((RefCU = getUnitForOffset(Units, Offset: RefOffset)))
90 if (const auto RefDie = RefCU->getOrigUnit().getDIEForOffset(Offset: RefOffset)) {
91 // In a file with broken references, an attribute might point to a NULL
92 // DIE.
93 if (!RefDie.isNULL())
94 return RefDie;
95 }
96
97 reportWarning(Warning: "could not find referenced DIE", File, DIE: &DIE);
98 return DWARFDie();
99}
100
101/// \returns whether the passed \a Attr type might contain a DIE reference
102/// suitable for ODR uniquing.
103static bool isODRAttribute(uint16_t Attr) {
104 switch (Attr) {
105 default:
106 return false;
107 case dwarf::DW_AT_type:
108 case dwarf::DW_AT_containing_type:
109 case dwarf::DW_AT_specification:
110 case dwarf::DW_AT_abstract_origin:
111 case dwarf::DW_AT_import:
112 case dwarf::DW_AT_LLVM_alloc_type:
113 return true;
114 }
115 llvm_unreachable("Improper attribute.");
116}
117
118static bool isTypeTag(uint16_t Tag) {
119 switch (Tag) {
120 case dwarf::DW_TAG_array_type:
121 case dwarf::DW_TAG_class_type:
122 case dwarf::DW_TAG_enumeration_type:
123 case dwarf::DW_TAG_pointer_type:
124 case dwarf::DW_TAG_reference_type:
125 case dwarf::DW_TAG_string_type:
126 case dwarf::DW_TAG_structure_type:
127 case dwarf::DW_TAG_subroutine_type:
128 case dwarf::DW_TAG_template_alias:
129 case dwarf::DW_TAG_typedef:
130 case dwarf::DW_TAG_union_type:
131 case dwarf::DW_TAG_ptr_to_member_type:
132 case dwarf::DW_TAG_set_type:
133 case dwarf::DW_TAG_subrange_type:
134 case dwarf::DW_TAG_base_type:
135 case dwarf::DW_TAG_const_type:
136 case dwarf::DW_TAG_constant:
137 case dwarf::DW_TAG_file_type:
138 case dwarf::DW_TAG_namelist:
139 case dwarf::DW_TAG_packed_type:
140 case dwarf::DW_TAG_volatile_type:
141 case dwarf::DW_TAG_restrict_type:
142 case dwarf::DW_TAG_atomic_type:
143 case dwarf::DW_TAG_interface_type:
144 case dwarf::DW_TAG_unspecified_type:
145 case dwarf::DW_TAG_shared_type:
146 case dwarf::DW_TAG_immutable_type:
147 return true;
148 default:
149 break;
150 }
151 return false;
152}
153
154/// Recurse through the input DIE's canonical references until we find a
155/// DW_AT_name.
156llvm::StringRef
157DWARFLinker::DIECloner::getCanonicalDIEName(DWARFDie Die, const DWARFFile &File,
158 CompileUnit *Unit) {
159 if (!Die)
160 return {};
161
162 std::optional<DWARFFormValue> Ref;
163
164 auto GetDieName = [](const DWARFDie &D) -> llvm::StringRef {
165 auto NameForm = D.find(Attr: llvm::dwarf::DW_AT_name);
166 if (!NameForm)
167 return {};
168
169 auto NameOrErr = NameForm->getAsCString();
170 if (!NameOrErr) {
171 llvm::consumeError(Err: NameOrErr.takeError());
172 return {};
173 }
174
175 return *NameOrErr;
176 };
177
178 llvm::StringRef Name = GetDieName(Die);
179 if (!Name.empty())
180 return Name;
181
182 while (true) {
183 if (!(Ref = Die.find(Attr: llvm::dwarf::DW_AT_specification)) &&
184 !(Ref = Die.find(Attr: llvm::dwarf::DW_AT_abstract_origin)))
185 break;
186
187 Die = Linker.resolveDIEReference(File, Units: CompileUnits, RefValue: *Ref, DIE: Die, RefCU&: Unit);
188 if (!Die)
189 break;
190
191 assert(Unit);
192
193 unsigned SpecIdx = Unit->getOrigUnit().getDIEIndex(D: Die);
194 CompileUnit::DIEInfo &SpecInfo = Unit->getInfo(Idx: SpecIdx);
195 if (SpecInfo.Ctxt && SpecInfo.Ctxt->hasCanonicalDIE()) {
196 if (!SpecInfo.Ctxt->getCanonicalName().empty()) {
197 Name = SpecInfo.Ctxt->getCanonicalName();
198 break;
199 }
200 }
201
202 Name = GetDieName(Die);
203 if (!Name.empty())
204 break;
205 }
206
207 return Name;
208}
209
210bool DWARFLinker::DIECloner::getDIENames(
211 const DWARFDie &Die, AttributesInfo &Info, OffsetsStringPool &StringPool,
212 const DWARFFile &File, CompileUnit &Unit, bool StripTemplate) {
213 // This function will be called on DIEs having low_pcs and
214 // ranges. As getting the name might be more expansive, filter out
215 // blocks directly.
216 if (Die.getTag() == dwarf::DW_TAG_lexical_block)
217 return false;
218
219 // The mangled name of an specification DIE will by virtue of the
220 // uniquing algorithm be the same as the one it got uniqued into.
221 // So just use the input DIE's linkage name.
222 if (!Info.MangledName)
223 if (const char *MangledName = Die.getLinkageName())
224 Info.MangledName = StringPool.getEntry(S: MangledName);
225
226 // For subprograms with linkage names, we unique on the linkage name,
227 // so DW_AT_name's may differ between the input and canonical DIEs.
228 // Use the name of the canonical DIE.
229 if (!Info.Name)
230 if (llvm::StringRef Name = getCanonicalDIEName(Die, File, Unit: &Unit);
231 !Name.empty())
232 Info.Name = StringPool.getEntry(S: Name);
233
234 if (!Info.MangledName)
235 Info.MangledName = Info.Name;
236
237 if (StripTemplate && Info.Name && Info.MangledName != Info.Name) {
238 StringRef Name = Info.Name.getString();
239 if (std::optional<StringRef> StrippedName = StripTemplateParameters(Name))
240 Info.NameWithoutTemplate = StringPool.getEntry(S: *StrippedName);
241 }
242
243 return Info.Name || Info.MangledName;
244}
245
246/// Resolve the relative path to a build artifact referenced by DWARF by
247/// applying DW_AT_comp_dir.
248static void resolveRelativeObjectPath(SmallVectorImpl<char> &Buf, DWARFDie CU) {
249 sys::path::append(path&: Buf, a: dwarf::toString(V: CU.find(Attr: dwarf::DW_AT_comp_dir), Default: ""));
250}
251
252/// Collect references to parseable Swift interfaces in imported
253/// DW_TAG_module blocks.
254static void analyzeImportedModule(
255 const DWARFDie &DIE, CompileUnit &CU,
256 DWARFLinkerBase::SwiftInterfacesMapTy *ParseableSwiftInterfaces,
257 std::function<void(const Twine &, const DWARFDie &)> ReportWarning) {
258 if (CU.getLanguage() != dwarf::DW_LANG_Swift)
259 return;
260
261 if (!ParseableSwiftInterfaces)
262 return;
263
264 StringRef Path = dwarf::toStringRef(V: DIE.find(Attr: dwarf::DW_AT_LLVM_include_path));
265 if (!Path.ends_with(Suffix: ".swiftinterface"))
266 return;
267 // Don't track interfaces that are part of the SDK.
268 StringRef SysRoot = dwarf::toStringRef(V: DIE.find(Attr: dwarf::DW_AT_LLVM_sysroot));
269 if (SysRoot.empty())
270 SysRoot = CU.getSysRoot();
271 if (!SysRoot.empty() && Path.starts_with(Prefix: SysRoot))
272 return;
273 // Don't track interfaces that are part of the toolchain.
274 // For example: Swift, _Concurrency, ...
275 StringRef DeveloperDir = guessDeveloperDir(SysRoot);
276 if (!DeveloperDir.empty() && Path.starts_with(Prefix: DeveloperDir))
277 return;
278 if (isInToolchainDir(Path))
279 return;
280 std::optional<const char *> Name =
281 dwarf::toString(V: DIE.find(Attr: dwarf::DW_AT_name));
282 if (!Name)
283 return;
284 auto &Entry = (*ParseableSwiftInterfaces)[*Name];
285 // The prepend path is applied later when copying.
286 DWARFDie CUDie = CU.getOrigUnit().getUnitDIE();
287 SmallString<128> ResolvedPath;
288 if (sys::path::is_relative(path: Path))
289 resolveRelativeObjectPath(Buf&: ResolvedPath, CU: CUDie);
290 sys::path::append(path&: ResolvedPath, a: Path);
291 if (!Entry.empty() && Entry != ResolvedPath)
292 ReportWarning(Twine("Conflicting parseable interfaces for Swift Module ") +
293 *Name + ": " + Entry + " and " + Path,
294 DIE);
295 Entry = std::string(ResolvedPath);
296}
297
298/// The distinct types of work performed by the work loop in
299/// analyzeContextInfo.
300enum class ContextWorklistItemType : uint8_t {
301 AnalyzeContextInfo,
302 UpdateChildPruning,
303 UpdatePruning,
304};
305
306/// This class represents an item in the work list. The type defines what kind
307/// of work needs to be performed when processing the current item. Everything
308/// but the Type and Die fields are optional based on the type.
309struct ContextWorklistItem {
310 DWARFDie Die;
311 unsigned ParentIdx;
312 union {
313 CompileUnit::DIEInfo *OtherInfo;
314 DeclContext *Context;
315 };
316 ContextWorklistItemType Type;
317 bool InImportedModule;
318
319 ContextWorklistItem(DWARFDie Die, ContextWorklistItemType T,
320 CompileUnit::DIEInfo *OtherInfo = nullptr)
321 : Die(Die), ParentIdx(0), OtherInfo(OtherInfo), Type(T),
322 InImportedModule(false) {}
323
324 ContextWorklistItem(DWARFDie Die, DeclContext *Context, unsigned ParentIdx,
325 bool InImportedModule)
326 : Die(Die), ParentIdx(ParentIdx), Context(Context),
327 Type(ContextWorklistItemType::AnalyzeContextInfo),
328 InImportedModule(InImportedModule) {}
329};
330
331static bool updatePruning(const DWARFDie &Die, CompileUnit &CU,
332 uint64_t ModulesEndOffset) {
333 CompileUnit::DIEInfo &Info = CU.getInfo(Die);
334
335 // Prune this DIE if it is either a forward declaration inside a
336 // DW_TAG_module or a DW_TAG_module that contains nothing but
337 // forward declarations.
338 Info.Prune &= (Die.getTag() == dwarf::DW_TAG_module) ||
339 (isTypeTag(Tag: Die.getTag()) &&
340 dwarf::toUnsigned(V: Die.find(Attr: dwarf::DW_AT_declaration), Default: 0));
341
342 // Only prune forward declarations inside a DW_TAG_module for which a
343 // definition exists elsewhere.
344 if (ModulesEndOffset == 0)
345 Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset();
346 else
347 Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() > 0 &&
348 Info.Ctxt->getCanonicalDIEOffset() <= ModulesEndOffset;
349
350 return Info.Prune;
351}
352
353static void updateChildPruning(const DWARFDie &Die, CompileUnit &CU,
354 CompileUnit::DIEInfo &ChildInfo) {
355 CompileUnit::DIEInfo &Info = CU.getInfo(Die);
356 Info.Prune &= ChildInfo.Prune;
357}
358
359/// Recursive helper to build the global DeclContext information and
360/// gather the child->parent relationships in the original compile unit.
361///
362/// This function uses the same work list approach as lookForDIEsToKeep.
363///
364/// \return true when this DIE and all of its children are only
365/// forward declarations to types defined in external clang modules
366/// (i.e., forward declarations that are children of a DW_TAG_module).
367static void analyzeContextInfo(
368 const DWARFDie &DIE, unsigned ParentIdx, CompileUnit &CU,
369 DeclContext *CurrentDeclContext, DeclContextTree &Contexts,
370 uint64_t ModulesEndOffset,
371 DWARFLinkerBase::SwiftInterfacesMapTy *ParseableSwiftInterfaces,
372 std::function<void(const Twine &, const DWARFDie &)> ReportWarning) {
373 // LIFO work list.
374 std::vector<ContextWorklistItem> Worklist;
375 Worklist.emplace_back(args: DIE, args&: CurrentDeclContext, args&: ParentIdx, args: false);
376
377 while (!Worklist.empty()) {
378 ContextWorklistItem Current = Worklist.back();
379 Worklist.pop_back();
380
381 switch (Current.Type) {
382 case ContextWorklistItemType::UpdatePruning:
383 updatePruning(Die: Current.Die, CU, ModulesEndOffset);
384 continue;
385 case ContextWorklistItemType::UpdateChildPruning:
386 updateChildPruning(Die: Current.Die, CU, ChildInfo&: *Current.OtherInfo);
387 continue;
388 case ContextWorklistItemType::AnalyzeContextInfo:
389 break;
390 }
391
392 unsigned Idx = CU.getOrigUnit().getDIEIndex(D: Current.Die);
393 CompileUnit::DIEInfo &Info = CU.getInfo(Idx);
394
395 // Clang imposes an ODR on modules(!) regardless of the language:
396 // "The module-id should consist of only a single identifier,
397 // which provides the name of the module being defined. Each
398 // module shall have a single definition."
399 //
400 // This does not extend to the types inside the modules:
401 // "[I]n C, this implies that if two structs are defined in
402 // different submodules with the same name, those two types are
403 // distinct types (but may be compatible types if their
404 // definitions match)."
405 //
406 // We treat non-C++ modules like namespaces for this reason.
407 if (Current.Die.getTag() == dwarf::DW_TAG_module &&
408 Current.ParentIdx == 0 &&
409 dwarf::toString(V: Current.Die.find(Attr: dwarf::DW_AT_name), Default: "") !=
410 CU.getClangModuleName()) {
411 Current.InImportedModule = true;
412 analyzeImportedModule(DIE: Current.Die, CU, ParseableSwiftInterfaces,
413 ReportWarning);
414 }
415
416 Info.ParentIdx = Current.ParentIdx;
417 Info.InModuleScope = CU.isClangModule() || Current.InImportedModule;
418 if (CU.hasODR() || Info.InModuleScope) {
419 if (Current.Context) {
420 auto PtrInvalidPair = Contexts.getChildDeclContext(
421 Context&: *Current.Context, DIE: Current.Die, Unit&: CU, InClangModule: Info.InModuleScope);
422 Current.Context = PtrInvalidPair.getPointer();
423 Info.Ctxt =
424 PtrInvalidPair.getInt() ? nullptr : PtrInvalidPair.getPointer();
425 if (Info.Ctxt)
426 Info.Ctxt->setDefinedInClangModule(Info.InModuleScope);
427 } else
428 Info.Ctxt = Current.Context = nullptr;
429 }
430
431 Info.Prune = Current.InImportedModule;
432 // Add children in reverse order to the worklist to effectively process
433 // them in order.
434 Worklist.emplace_back(args&: Current.Die, args: ContextWorklistItemType::UpdatePruning);
435 for (auto Child : reverse(C: Current.Die.children())) {
436 CompileUnit::DIEInfo &ChildInfo = CU.getInfo(Die: Child);
437 Worklist.emplace_back(
438 args&: Current.Die, args: ContextWorklistItemType::UpdateChildPruning, args: &ChildInfo);
439 Worklist.emplace_back(args&: Child, args&: Current.Context, args&: Idx,
440 args&: Current.InImportedModule);
441 }
442 }
443}
444
445static bool dieNeedsChildrenToBeMeaningful(uint32_t Tag) {
446 switch (Tag) {
447 default:
448 return false;
449 case dwarf::DW_TAG_class_type:
450 case dwarf::DW_TAG_common_block:
451 case dwarf::DW_TAG_lexical_block:
452 case dwarf::DW_TAG_structure_type:
453 case dwarf::DW_TAG_subprogram:
454 case dwarf::DW_TAG_subroutine_type:
455 case dwarf::DW_TAG_union_type:
456 return true;
457 }
458 llvm_unreachable("Invalid Tag");
459}
460
461void DWARFLinker::cleanupAuxiliarryData(LinkContext &Context) {
462 Context.clear();
463
464 for (DIEBlock *I : DIEBlocks)
465 I->~DIEBlock();
466 for (DIELoc *I : DIELocs)
467 I->~DIELoc();
468
469 DIEBlocks.clear();
470 DIELocs.clear();
471 DIEAlloc.Reset();
472}
473
474static bool isTlsAddressCode(uint8_t DW_OP_Code) {
475 return DW_OP_Code == dwarf::DW_OP_form_tls_address ||
476 DW_OP_Code == dwarf::DW_OP_GNU_push_tls_address;
477}
478
479static void constructSeqOffsettoOrigRowMapping(
480 CompileUnit &Unit, const DWARFDebugLine::LineTable &LT,
481 DenseMap<uint64_t, unsigned> &SeqOffToOrigRow) {
482
483 // Use std::map for ordered iteration.
484 std::map<uint64_t, unsigned> LineTableMapping;
485
486 // First, trust the sequences that the DWARF parser did identify.
487 for (const DWARFDebugLine::Sequence &Seq : LT.Sequences)
488 LineTableMapping[Seq.StmtSeqOffset] = Seq.FirstRowIndex;
489
490 // Second, manually find sequence boundaries and match them to the
491 // sorted attributes to handle sequences the parser might have missed.
492 auto StmtAttrs = Unit.getStmtSeqListAttributes();
493 llvm::sort(C&: StmtAttrs, Comp: [](const PatchLocation &A, const PatchLocation &B) {
494 return A.get() < B.get();
495 });
496
497 std::vector<unsigned> SeqStartRows;
498 SeqStartRows.push_back(x: 0);
499 for (auto [I, Row] : llvm::enumerate(First: ArrayRef(LT.Rows).drop_back()))
500 if (Row.EndSequence)
501 SeqStartRows.push_back(x: I + 1);
502
503 // While SeqOffToOrigRow parsed from CU could be the ground truth,
504 // e.g.
505 //
506 // SeqOff Row
507 // 0x08 9
508 // 0x14 15
509 //
510 // The StmtAttrs and SeqStartRows may not match perfectly, e.g.
511 //
512 // StmtAttrs SeqStartRows
513 // 0x04 3
514 // 0x08 5
515 // 0x10 9
516 // 0x12 11
517 // 0x14 15
518 //
519 // In this case, we don't want to assign 5 to 0x08, since we know 0x08
520 // maps to 9. If we do a dummy 1:1 mapping 0x10 will be mapped to 9
521 // which is incorrect. The expected behavior is ignore 5, realign the
522 // table based on the result from the line table:
523 //
524 // StmtAttrs SeqStartRows
525 // 0x04 3
526 // -- 5
527 // 0x08 9 <- LineTableMapping ground truth
528 // 0x10 11
529 // 0x12 --
530 // 0x14 15 <- LineTableMapping ground truth
531
532 ArrayRef StmtAttrsRef(StmtAttrs);
533 ArrayRef SeqStartRowsRef(SeqStartRows);
534
535 // Dummy last element to make sure StmtAttrsRef and SeqStartRowsRef always
536 // run out first.
537 constexpr uint64_t DummyKey = UINT64_MAX;
538 constexpr unsigned DummyVal = UINT32_MAX;
539 LineTableMapping[DummyKey] = DummyVal;
540
541 for (auto [NextSeqOff, NextRow] : LineTableMapping) {
542 // Explict capture to avoid capturing structured bindings and make C++17
543 // happy.
544 auto StmtAttrSmallerThanNext = [N = NextSeqOff](const PatchLocation &SA) {
545 return SA.get() < N;
546 };
547 auto SeqStartSmallerThanNext = [N = NextRow](const unsigned &Row) {
548 return Row < N;
549 };
550 // If both StmtAttrs and SeqStartRows points to value not in
551 // the LineTableMapping yet, we do a dummy one to one mapping and
552 // move the pointer.
553 while (!StmtAttrsRef.empty() && !SeqStartRowsRef.empty() &&
554 StmtAttrSmallerThanNext(StmtAttrsRef.front()) &&
555 SeqStartSmallerThanNext(SeqStartRowsRef.front())) {
556 SeqOffToOrigRow[StmtAttrsRef.consume_front().get()] =
557 SeqStartRowsRef.consume_front();
558 }
559 // One of the pointer points to the value at or past Next in the
560 // LineTableMapping, We move the pointer to re-align with the
561 // LineTableMapping
562 StmtAttrsRef = StmtAttrsRef.drop_while(Pred: StmtAttrSmallerThanNext);
563 SeqStartRowsRef = SeqStartRowsRef.drop_while(Pred: SeqStartSmallerThanNext);
564 // Use the LineTableMapping's result as the ground truth and move
565 // on.
566 if (NextSeqOff != DummyKey) {
567 SeqOffToOrigRow[NextSeqOff] = NextRow;
568 }
569 // Move the pointers if they are pointed at Next.
570 // It is possible that they point to later entries in LineTableMapping.
571 // Therefore we only increment the pointers after we validate they are
572 // pointing to the `Next` entry. e.g.
573 //
574 // LineTableMapping
575 // SeqOff Row
576 // 0x08 9 <- NextSeqOff/NextRow
577 // 0x14 15
578 //
579 // StmtAttrs SeqStartRows
580 // 0x14 13 <- StmtAttrsRef.front() / SeqStartRowsRef.front()
581 // 0x16 15
582 // -- 17
583 if (!StmtAttrsRef.empty() && StmtAttrsRef.front().get() == NextSeqOff)
584 StmtAttrsRef.consume_front();
585 if (!SeqStartRowsRef.empty() && SeqStartRowsRef.front() == NextRow)
586 SeqStartRowsRef.consume_front();
587 }
588}
589
590std::pair<bool, std::optional<int64_t>>
591DWARFLinker::getVariableRelocAdjustment(AddressesMap &RelocMgr,
592 const DWARFDie &DIE) {
593 assert((DIE.getTag() == dwarf::DW_TAG_variable ||
594 DIE.getTag() == dwarf::DW_TAG_constant) &&
595 "Wrong type of input die");
596
597 const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
598
599 // Check if DIE has DW_AT_location attribute.
600 DWARFUnit *U = DIE.getDwarfUnit();
601 std::optional<uint32_t> LocationIdx =
602 Abbrev->findAttributeIndex(attr: dwarf::DW_AT_location);
603 if (!LocationIdx)
604 return std::make_pair(x: false, y: std::nullopt);
605
606 // Get offset to the DW_AT_location attribute.
607 uint64_t AttrOffset =
608 Abbrev->getAttributeOffsetFromIndex(AttrIndex: *LocationIdx, DIEOffset: DIE.getOffset(), U: *U);
609
610 // Get value of the DW_AT_location attribute.
611 std::optional<DWARFFormValue> LocationValue =
612 Abbrev->getAttributeValueFromOffset(AttrIndex: *LocationIdx, Offset: AttrOffset, U: *U);
613 if (!LocationValue)
614 return std::make_pair(x: false, y: std::nullopt);
615
616 // Check that DW_AT_location attribute is of 'exprloc' class.
617 // Handling value of location expressions for attributes of 'loclist'
618 // class is not implemented yet.
619 std::optional<ArrayRef<uint8_t>> Expr = LocationValue->getAsBlock();
620 if (!Expr)
621 return std::make_pair(x: false, y: std::nullopt);
622
623 // Parse 'exprloc' expression.
624 DataExtractor Data(toStringRef(Input: *Expr), U->getContext().isLittleEndian(),
625 U->getAddressByteSize());
626 DWARFExpression Expression(Data, U->getAddressByteSize(),
627 U->getFormParams().Format);
628
629 bool HasLocationAddress = false;
630 uint64_t CurExprOffset = 0;
631 for (DWARFExpression::iterator It = Expression.begin();
632 It != Expression.end(); ++It) {
633 DWARFExpression::iterator NextIt = It;
634 ++NextIt;
635
636 const DWARFExpression::Operation &Op = *It;
637 switch (Op.getCode()) {
638 case dwarf::DW_OP_const2u:
639 case dwarf::DW_OP_const4u:
640 case dwarf::DW_OP_const8u:
641 case dwarf::DW_OP_const2s:
642 case dwarf::DW_OP_const4s:
643 case dwarf::DW_OP_const8s:
644 if (NextIt == Expression.end() || !isTlsAddressCode(DW_OP_Code: NextIt->getCode()))
645 break;
646 [[fallthrough]];
647 case dwarf::DW_OP_addr: {
648 HasLocationAddress = true;
649 // Check relocation for the address.
650 if (std::optional<int64_t> RelocAdjustment =
651 RelocMgr.getExprOpAddressRelocAdjustment(
652 U&: *U, Op, StartOffset: AttrOffset + CurExprOffset,
653 EndOffset: AttrOffset + Op.getEndOffset(), Verbose: Options.Verbose))
654 return std::make_pair(x&: HasLocationAddress, y&: *RelocAdjustment);
655 } break;
656 case dwarf::DW_OP_constx:
657 case dwarf::DW_OP_addrx: {
658 HasLocationAddress = true;
659 if (std::optional<uint64_t> AddressOffset =
660 DIE.getDwarfUnit()->getIndexedAddressOffset(
661 Index: Op.getRawOperand(Idx: 0))) {
662 // Check relocation for the address.
663 if (std::optional<int64_t> RelocAdjustment =
664 RelocMgr.getExprOpAddressRelocAdjustment(
665 U&: *U, Op, StartOffset: *AddressOffset,
666 EndOffset: *AddressOffset + DIE.getDwarfUnit()->getAddressByteSize(),
667 Verbose: Options.Verbose))
668 return std::make_pair(x&: HasLocationAddress, y&: *RelocAdjustment);
669 }
670 } break;
671 default: {
672 // Nothing to do.
673 } break;
674 }
675 CurExprOffset = Op.getEndOffset();
676 }
677
678 return std::make_pair(x&: HasLocationAddress, y: std::nullopt);
679}
680
681/// Check if a variable describing DIE should be kept.
682/// \returns updated TraversalFlags.
683unsigned DWARFLinker::shouldKeepVariableDIE(AddressesMap &RelocMgr,
684 const DWARFDie &DIE,
685 CompileUnit::DIEInfo &MyInfo,
686 unsigned Flags) {
687 const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
688
689 // Global variables with constant value can always be kept.
690 if (!(Flags & TF_InFunctionScope) &&
691 Abbrev->findAttributeIndex(attr: dwarf::DW_AT_const_value)) {
692 MyInfo.InDebugMap = true;
693 return Flags | TF_Keep;
694 }
695
696 // See if there is a relocation to a valid debug map entry inside this
697 // variable's location. The order is important here. We want to always check
698 // if the variable has a valid relocation, so that the DIEInfo is filled.
699 // However, we don't want a static variable in a function to force us to keep
700 // the enclosing function, unless requested explicitly.
701 std::pair<bool, std::optional<int64_t>> LocExprAddrAndRelocAdjustment =
702 getVariableRelocAdjustment(RelocMgr, DIE);
703
704 if (LocExprAddrAndRelocAdjustment.first)
705 MyInfo.HasLocationExpressionAddr = true;
706
707 if (!LocExprAddrAndRelocAdjustment.second)
708 return Flags;
709
710 MyInfo.AddrAdjust = *LocExprAddrAndRelocAdjustment.second;
711 MyInfo.InDebugMap = true;
712
713 if (((Flags & TF_InFunctionScope) &&
714 !LLVM_UNLIKELY(Options.KeepFunctionForStatic)))
715 return Flags;
716
717 if (Options.Verbose) {
718 outs() << "Keeping variable DIE:";
719 DIDumpOptions DumpOpts;
720 DumpOpts.ChildRecurseDepth = 0;
721 DumpOpts.Verbose = Options.Verbose;
722 DIE.dump(OS&: outs(), indent: 8 /* Indent */, DumpOpts);
723 }
724
725 return Flags | TF_Keep;
726}
727
728/// Check if a function describing DIE should be kept.
729/// \returns updated TraversalFlags.
730unsigned DWARFLinker::shouldKeepSubprogramDIE(
731 AddressesMap &RelocMgr, const DWARFDie &DIE, const DWARFFile &File,
732 CompileUnit &Unit, CompileUnit::DIEInfo &MyInfo, unsigned Flags) {
733 Flags |= TF_InFunctionScope;
734
735 auto LowPc = dwarf::toAddress(V: DIE.find(Attr: dwarf::DW_AT_low_pc));
736 if (!LowPc)
737 return Flags;
738
739 assert(LowPc && "low_pc attribute is not an address.");
740 std::optional<int64_t> RelocAdjustment =
741 RelocMgr.getSubprogramRelocAdjustment(DIE, Verbose: Options.Verbose);
742 if (!RelocAdjustment)
743 return Flags;
744
745 MyInfo.AddrAdjust = *RelocAdjustment;
746 MyInfo.InDebugMap = true;
747
748 if (Options.Verbose) {
749 outs() << "Keeping subprogram DIE:";
750 DIDumpOptions DumpOpts;
751 DumpOpts.ChildRecurseDepth = 0;
752 DumpOpts.Verbose = Options.Verbose;
753 DIE.dump(OS&: outs(), indent: 8 /* Indent */, DumpOpts);
754 }
755
756 if (DIE.getTag() == dwarf::DW_TAG_label) {
757 if (Unit.hasLabelAt(Addr: *LowPc))
758 return Flags;
759
760 DWARFUnit &OrigUnit = Unit.getOrigUnit();
761 // FIXME: dsymutil-classic compat. dsymutil-classic doesn't consider labels
762 // that don't fall into the CU's aranges. This is wrong IMO. Debug info
763 // generation bugs aside, this is really wrong in the case of labels, where
764 // a label marking the end of a function will have a PC == CU's high_pc.
765 if (dwarf::toAddress(V: OrigUnit.getUnitDIE().find(Attr: dwarf::DW_AT_high_pc))
766 .value_or(UINT64_MAX) <= LowPc)
767 return Flags;
768 Unit.addLabelLowPc(LabelLowPc: *LowPc, PcOffset: MyInfo.AddrAdjust);
769 return Flags | TF_Keep;
770 }
771
772 Flags |= TF_Keep;
773
774 std::optional<uint64_t> HighPc = DIE.getHighPC(LowPC: *LowPc);
775 if (!HighPc) {
776 reportWarning(Warning: "Function without high_pc. Range will be discarded.\n", File,
777 DIE: &DIE);
778 return Flags;
779 }
780 if (*LowPc > *HighPc) {
781 reportWarning(Warning: "low_pc greater than high_pc. Range will be discarded.\n",
782 File, DIE: &DIE);
783 return Flags;
784 }
785
786 // Replace the debug map range with a more accurate one.
787 Unit.addFunctionRange(LowPC: *LowPc, HighPC: *HighPc, PCOffset: MyInfo.AddrAdjust);
788 return Flags;
789}
790
791/// Check if a DIE should be kept.
792/// \returns updated TraversalFlags.
793unsigned DWARFLinker::shouldKeepDIE(AddressesMap &RelocMgr, const DWARFDie &DIE,
794 const DWARFFile &File, CompileUnit &Unit,
795 CompileUnit::DIEInfo &MyInfo,
796 unsigned Flags) {
797 switch (DIE.getTag()) {
798 case dwarf::DW_TAG_constant:
799 case dwarf::DW_TAG_variable:
800 return shouldKeepVariableDIE(RelocMgr, DIE, MyInfo, Flags);
801 case dwarf::DW_TAG_subprogram:
802 case dwarf::DW_TAG_label:
803 return shouldKeepSubprogramDIE(RelocMgr, DIE, File, Unit, MyInfo, Flags);
804 case dwarf::DW_TAG_base_type:
805 // DWARF Expressions may reference basic types, but scanning them
806 // is expensive. Basic types are tiny, so just keep all of them.
807 case dwarf::DW_TAG_imported_module:
808 case dwarf::DW_TAG_imported_declaration:
809 case dwarf::DW_TAG_imported_unit:
810 // We always want to keep these.
811 return Flags | TF_Keep;
812 default:
813 break;
814 }
815
816 return Flags;
817}
818
819/// Helper that updates the completeness of the current DIE based on the
820/// completeness of one of its children. It depends on the incompleteness of
821/// the children already being computed.
822static void updateChildIncompleteness(const DWARFDie &Die, CompileUnit &CU,
823 CompileUnit::DIEInfo &ChildInfo) {
824 switch (Die.getTag()) {
825 case dwarf::DW_TAG_structure_type:
826 case dwarf::DW_TAG_class_type:
827 case dwarf::DW_TAG_union_type:
828 break;
829 default:
830 return;
831 }
832
833 CompileUnit::DIEInfo &MyInfo = CU.getInfo(Die);
834
835 if (ChildInfo.Incomplete || ChildInfo.Prune)
836 MyInfo.Incomplete = true;
837}
838
839/// Helper that updates the completeness of the current DIE based on the
840/// completeness of the DIEs it references. It depends on the incompleteness of
841/// the referenced DIE already being computed.
842static void updateRefIncompleteness(const DWARFDie &Die, CompileUnit &CU,
843 CompileUnit::DIEInfo &RefInfo) {
844 switch (Die.getTag()) {
845 case dwarf::DW_TAG_typedef:
846 case dwarf::DW_TAG_member:
847 case dwarf::DW_TAG_reference_type:
848 case dwarf::DW_TAG_ptr_to_member_type:
849 case dwarf::DW_TAG_pointer_type:
850 break;
851 default:
852 return;
853 }
854
855 CompileUnit::DIEInfo &MyInfo = CU.getInfo(Die);
856
857 if (MyInfo.Incomplete)
858 return;
859
860 if (RefInfo.Incomplete)
861 MyInfo.Incomplete = true;
862}
863
864/// Look at the children of the given DIE and decide whether they should be
865/// kept.
866void DWARFLinker::lookForChildDIEsToKeep(
867 const DWARFDie &Die, CompileUnit &CU, unsigned Flags,
868 SmallVectorImpl<WorklistItem> &Worklist) {
869 // The TF_ParentWalk flag tells us that we are currently walking up the
870 // parent chain of a required DIE, and we don't want to mark all the children
871 // of the parents as kept (consider for example a DW_TAG_namespace node in
872 // the parent chain). There are however a set of DIE types for which we want
873 // to ignore that directive and still walk their children.
874 if (dieNeedsChildrenToBeMeaningful(Tag: Die.getTag()))
875 Flags &= ~DWARFLinker::TF_ParentWalk;
876
877 // We're finished if this DIE has no children or we're walking the parent
878 // chain.
879 if (!Die.hasChildren() || (Flags & DWARFLinker::TF_ParentWalk))
880 return;
881
882 // Add children in reverse order to the worklist to effectively process them
883 // in order.
884 for (auto Child : reverse(C: Die.children())) {
885 // Add a worklist item before every child to calculate incompleteness right
886 // after the current child is processed.
887 CompileUnit::DIEInfo &ChildInfo = CU.getInfo(Die: Child);
888 Worklist.emplace_back(Args: Die, Args&: CU, Args: WorklistItemType::UpdateChildIncompleteness,
889 Args: &ChildInfo);
890 Worklist.emplace_back(Args&: Child, Args&: CU, Args&: Flags);
891 }
892}
893
894static bool isODRCanonicalCandidate(const DWARFDie &Die, CompileUnit &CU) {
895 CompileUnit::DIEInfo &Info = CU.getInfo(Die);
896
897 if (!Info.Ctxt || (Die.getTag() == dwarf::DW_TAG_namespace))
898 return false;
899
900 if (!CU.hasODR() && !Info.InModuleScope)
901 return false;
902
903 return !Info.Incomplete && Info.Ctxt != CU.getInfo(Idx: Info.ParentIdx).Ctxt;
904}
905
906void DWARFLinker::markODRCanonicalDie(const DWARFDie &Die, CompileUnit &CU) {
907 CompileUnit::DIEInfo &Info = CU.getInfo(Die);
908
909 Info.ODRMarkingDone = true;
910 if (Info.Keep && isODRCanonicalCandidate(Die, CU) &&
911 !Info.Ctxt->hasCanonicalDIE())
912 Info.Ctxt->setHasCanonicalDIE();
913}
914
915/// Look at DIEs referenced by the given DIE and decide whether they should be
916/// kept. All DIEs referenced though attributes should be kept.
917void DWARFLinker::lookForRefDIEsToKeep(
918 const DWARFDie &Die, CompileUnit &CU, unsigned Flags,
919 const UnitListTy &Units, const DWARFFile &File,
920 SmallVectorImpl<WorklistItem> &Worklist) {
921 bool UseOdr = (Flags & DWARFLinker::TF_DependencyWalk)
922 ? (Flags & DWARFLinker::TF_ODR)
923 : CU.hasODR();
924 DWARFUnit &Unit = CU.getOrigUnit();
925 DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
926 const auto *Abbrev = Die.getAbbreviationDeclarationPtr();
927 uint64_t Offset = Die.getOffset() + getULEB128Size(Value: Abbrev->getCode());
928
929 SmallVector<std::pair<DWARFDie, CompileUnit &>, 4> ReferencedDIEs;
930 for (const auto &AttrSpec : Abbrev->attributes()) {
931 DWARFFormValue Val(AttrSpec.Form);
932 if (!Val.isFormClass(FC: DWARFFormValue::FC_Reference) ||
933 AttrSpec.Attr == dwarf::DW_AT_sibling) {
934 DWARFFormValue::skipValue(Form: AttrSpec.Form, DebugInfoData: Data, OffsetPtr: &Offset,
935 FormParams: Unit.getFormParams());
936 continue;
937 }
938
939 Val.extractValue(Data, OffsetPtr: &Offset, FormParams: Unit.getFormParams(), U: &Unit);
940 CompileUnit *ReferencedCU;
941 if (auto RefDie =
942 resolveDIEReference(File, Units, RefValue: Val, DIE: Die, RefCU&: ReferencedCU)) {
943 CompileUnit::DIEInfo &Info = ReferencedCU->getInfo(Die: RefDie);
944 // If the referenced DIE has a DeclContext that has already been
945 // emitted, then do not keep the one in this CU. We'll link to
946 // the canonical DIE in cloneDieReferenceAttribute.
947 //
948 // FIXME: compatibility with dsymutil-classic. UseODR shouldn't
949 // be necessary and could be advantageously replaced by
950 // ReferencedCU->hasODR() && CU.hasODR().
951 //
952 // FIXME: compatibility with dsymutil-classic. There is no
953 // reason not to unique ref_addr references.
954 if (AttrSpec.Form != dwarf::DW_FORM_ref_addr &&
955 isODRAttribute(Attr: AttrSpec.Attr) && Info.Ctxt &&
956 Info.Ctxt->hasCanonicalDIE())
957 continue;
958
959 // Keep a module forward declaration if there is no definition.
960 if (!(isODRAttribute(Attr: AttrSpec.Attr) && Info.Ctxt &&
961 Info.Ctxt->hasCanonicalDIE()))
962 Info.Prune = false;
963 ReferencedDIEs.emplace_back(Args&: RefDie, Args&: *ReferencedCU);
964 }
965 }
966
967 unsigned ODRFlag = UseOdr ? DWARFLinker::TF_ODR : 0;
968
969 // Add referenced DIEs in reverse order to the worklist to effectively
970 // process them in order.
971 for (auto &P : reverse(C&: ReferencedDIEs)) {
972 // Add a worklist item before every child to calculate incompleteness right
973 // after the current child is processed.
974 CompileUnit::DIEInfo &Info = P.second.getInfo(Die: P.first);
975 Worklist.emplace_back(Args: Die, Args&: CU, Args: WorklistItemType::UpdateRefIncompleteness,
976 Args: &Info);
977 Worklist.emplace_back(Args&: P.first, Args&: P.second,
978 Args: DWARFLinker::TF_Keep |
979 DWARFLinker::TF_DependencyWalk | ODRFlag);
980 }
981}
982
983/// Look at the parent of the given DIE and decide whether they should be kept.
984void DWARFLinker::lookForParentDIEsToKeep(
985 unsigned AncestorIdx, CompileUnit &CU, unsigned Flags,
986 SmallVectorImpl<WorklistItem> &Worklist) {
987 // Stop if we encounter an ancestor that's already marked as kept.
988 if (CU.getInfo(Idx: AncestorIdx).Keep)
989 return;
990
991 DWARFUnit &Unit = CU.getOrigUnit();
992 DWARFDie ParentDIE = Unit.getDIEAtIndex(Index: AncestorIdx);
993 Worklist.emplace_back(Args&: CU.getInfo(Idx: AncestorIdx).ParentIdx, Args&: CU, Args&: Flags);
994 Worklist.emplace_back(Args&: ParentDIE, Args&: CU, Args&: Flags);
995}
996
997/// Recursively walk the \p DIE tree and look for DIEs to keep. Store that
998/// information in \p CU's DIEInfo.
999///
1000/// This function is the entry point of the DIE selection algorithm. It is
1001/// expected to walk the DIE tree in file order and (though the mediation of
1002/// its helper) call hasValidRelocation() on each DIE that might be a 'root
1003/// DIE' (See DwarfLinker class comment).
1004///
1005/// While walking the dependencies of root DIEs, this function is also called,
1006/// but during these dependency walks the file order is not respected. The
1007/// TF_DependencyWalk flag tells us which kind of traversal we are currently
1008/// doing.
1009///
1010/// The recursive algorithm is implemented iteratively as a work list because
1011/// very deep recursion could exhaust the stack for large projects. The work
1012/// list acts as a scheduler for different types of work that need to be
1013/// performed.
1014///
1015/// The recursive nature of the algorithm is simulated by running the "main"
1016/// algorithm (LookForDIEsToKeep) followed by either looking at more DIEs
1017/// (LookForChildDIEsToKeep, LookForRefDIEsToKeep, LookForParentDIEsToKeep) or
1018/// fixing up a computed property (UpdateChildIncompleteness,
1019/// UpdateRefIncompleteness).
1020///
1021/// The return value indicates whether the DIE is incomplete.
1022void DWARFLinker::lookForDIEsToKeep(AddressesMap &AddressesMap,
1023 const UnitListTy &Units,
1024 const DWARFDie &Die, const DWARFFile &File,
1025 CompileUnit &Cu, unsigned Flags) {
1026 // LIFO work list.
1027 SmallVector<WorklistItem, 4> Worklist;
1028 Worklist.emplace_back(Args: Die, Args&: Cu, Args&: Flags);
1029
1030 while (!Worklist.empty()) {
1031 WorklistItem Current = Worklist.pop_back_val();
1032
1033 // Look at the worklist type to decide what kind of work to perform.
1034 switch (Current.Type) {
1035 case WorklistItemType::UpdateChildIncompleteness:
1036 updateChildIncompleteness(Die: Current.Die, CU&: Current.CU, ChildInfo&: *Current.OtherInfo);
1037 continue;
1038 case WorklistItemType::UpdateRefIncompleteness:
1039 updateRefIncompleteness(Die: Current.Die, CU&: Current.CU, RefInfo&: *Current.OtherInfo);
1040 continue;
1041 case WorklistItemType::LookForChildDIEsToKeep:
1042 lookForChildDIEsToKeep(Die: Current.Die, CU&: Current.CU, Flags: Current.Flags, Worklist);
1043 continue;
1044 case WorklistItemType::LookForRefDIEsToKeep:
1045 lookForRefDIEsToKeep(Die: Current.Die, CU&: Current.CU, Flags: Current.Flags, Units, File,
1046 Worklist);
1047 continue;
1048 case WorklistItemType::LookForParentDIEsToKeep:
1049 lookForParentDIEsToKeep(AncestorIdx: Current.AncestorIdx, CU&: Current.CU, Flags: Current.Flags,
1050 Worklist);
1051 continue;
1052 case WorklistItemType::MarkODRCanonicalDie:
1053 markODRCanonicalDie(Die: Current.Die, CU&: Current.CU);
1054 continue;
1055 case WorklistItemType::LookForDIEsToKeep:
1056 break;
1057 }
1058
1059 unsigned Idx = Current.CU.getOrigUnit().getDIEIndex(D: Current.Die);
1060 CompileUnit::DIEInfo &MyInfo = Current.CU.getInfo(Idx);
1061
1062 if (MyInfo.Prune) {
1063 // We're walking the dependencies of a module forward declaration that was
1064 // kept because there is no definition.
1065 if (Current.Flags & TF_DependencyWalk)
1066 MyInfo.Prune = false;
1067 else
1068 continue;
1069 }
1070
1071 // If the Keep flag is set, we are marking a required DIE's dependencies.
1072 // If our target is already marked as kept, we're all set.
1073 bool AlreadyKept = MyInfo.Keep;
1074 if ((Current.Flags & TF_DependencyWalk) && AlreadyKept)
1075 continue;
1076
1077 if (!(Current.Flags & TF_DependencyWalk))
1078 Current.Flags = shouldKeepDIE(RelocMgr&: AddressesMap, DIE: Current.Die, File, Unit&: Current.CU,
1079 MyInfo, Flags: Current.Flags);
1080
1081 // We need to mark context for the canonical die in the end of normal
1082 // traversing(not TF_DependencyWalk) or after normal traversing if die
1083 // was not marked as kept.
1084 if (!(Current.Flags & TF_DependencyWalk) ||
1085 (MyInfo.ODRMarkingDone && !MyInfo.Keep)) {
1086 if (Current.CU.hasODR() || MyInfo.InModuleScope)
1087 Worklist.emplace_back(Args&: Current.Die, Args&: Current.CU,
1088 Args: WorklistItemType::MarkODRCanonicalDie);
1089 }
1090
1091 // Finish by looking for child DIEs. Because of the LIFO worklist we need
1092 // to schedule that work before any subsequent items are added to the
1093 // worklist.
1094 Worklist.emplace_back(Args&: Current.Die, Args&: Current.CU, Args&: Current.Flags,
1095 Args: WorklistItemType::LookForChildDIEsToKeep);
1096
1097 if (AlreadyKept || !(Current.Flags & TF_Keep))
1098 continue;
1099
1100 // If it is a newly kept DIE mark it as well as all its dependencies as
1101 // kept.
1102 MyInfo.Keep = true;
1103
1104 // We're looking for incomplete types.
1105 MyInfo.Incomplete =
1106 Current.Die.getTag() != dwarf::DW_TAG_subprogram &&
1107 Current.Die.getTag() != dwarf::DW_TAG_member &&
1108 dwarf::toUnsigned(V: Current.Die.find(Attr: dwarf::DW_AT_declaration), Default: 0);
1109
1110 // After looking at the parent chain, look for referenced DIEs. Because of
1111 // the LIFO worklist we need to schedule that work before any subsequent
1112 // items are added to the worklist.
1113 Worklist.emplace_back(Args&: Current.Die, Args&: Current.CU, Args&: Current.Flags,
1114 Args: WorklistItemType::LookForRefDIEsToKeep);
1115
1116 bool UseOdr = (Current.Flags & TF_DependencyWalk) ? (Current.Flags & TF_ODR)
1117 : Current.CU.hasODR();
1118 unsigned ODRFlag = UseOdr ? TF_ODR : 0;
1119 unsigned ParFlags = TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag;
1120
1121 // Now schedule the parent walk.
1122 Worklist.emplace_back(Args&: MyInfo.ParentIdx, Args&: Current.CU, Args&: ParFlags);
1123 }
1124}
1125
1126#ifndef NDEBUG
1127/// A broken link in the keep chain. By recording both the parent and the child
1128/// we can show only broken links for DIEs with multiple children.
1129struct BrokenLink {
1130 BrokenLink(DWARFDie Parent, DWARFDie Child) : Parent(Parent), Child(Child) {}
1131 DWARFDie Parent;
1132 DWARFDie Child;
1133};
1134
1135/// Verify the keep chain by looking for DIEs that are kept but who's parent
1136/// isn't.
1137static void verifyKeepChain(CompileUnit &CU) {
1138 std::vector<DWARFDie> Worklist;
1139 Worklist.push_back(CU.getOrigUnit().getUnitDIE());
1140
1141 // List of broken links.
1142 std::vector<BrokenLink> BrokenLinks;
1143
1144 while (!Worklist.empty()) {
1145 const DWARFDie Current = Worklist.back();
1146 Worklist.pop_back();
1147
1148 const bool CurrentDieIsKept = CU.getInfo(Current).Keep;
1149
1150 for (DWARFDie Child : reverse(Current.children())) {
1151 Worklist.push_back(Child);
1152
1153 const bool ChildDieIsKept = CU.getInfo(Child).Keep;
1154 if (!CurrentDieIsKept && ChildDieIsKept)
1155 BrokenLinks.emplace_back(Current, Child);
1156 }
1157 }
1158
1159 if (!BrokenLinks.empty()) {
1160 for (BrokenLink Link : BrokenLinks) {
1161 WithColor::error() << formatv(
1162 "Found invalid link in keep chain between {0:x} and {1:x}\n",
1163 Link.Parent.getOffset(), Link.Child.getOffset());
1164
1165 errs() << "Parent:";
1166 Link.Parent.dump(errs(), 0, {});
1167 CU.getInfo(Link.Parent).dump();
1168
1169 errs() << "Child:";
1170 Link.Child.dump(errs(), 2, {});
1171 CU.getInfo(Link.Child).dump();
1172 }
1173 report_fatal_error("invalid keep chain");
1174 }
1175}
1176#endif
1177
1178/// Assign an abbreviation number to \p Abbrev.
1179///
1180/// Our DIEs get freed after every DebugMapObject has been processed,
1181/// thus the FoldingSet we use to unique DIEAbbrevs cannot refer to
1182/// the instances hold by the DIEs. When we encounter an abbreviation
1183/// that we don't know, we create a permanent copy of it.
1184void DWARFLinker::assignAbbrev(DIEAbbrev &Abbrev) {
1185 // Check the set for priors.
1186 FoldingSetNodeID ID;
1187 Abbrev.Profile(ID);
1188 void *InsertToken;
1189 DIEAbbrev *InSet = AbbreviationsSet.FindNodeOrInsertPos(ID, InsertPos&: InsertToken);
1190
1191 // If it's newly added.
1192 if (InSet) {
1193 // Assign existing abbreviation number.
1194 Abbrev.setNumber(InSet->getNumber());
1195 } else {
1196 // Add to abbreviation list.
1197 Abbreviations.push_back(
1198 x: std::make_unique<DIEAbbrev>(args: Abbrev.getTag(), args: Abbrev.hasChildren()));
1199 for (const auto &Attr : Abbrev.getData())
1200 Abbreviations.back()->AddAttribute(AbbrevData: Attr);
1201 AbbreviationsSet.InsertNode(N: Abbreviations.back().get(), InsertPos: InsertToken);
1202 // Assign the unique abbreviation number.
1203 Abbrev.setNumber(Abbreviations.size());
1204 Abbreviations.back()->setNumber(Abbreviations.size());
1205 }
1206}
1207
1208unsigned DWARFLinker::DIECloner::cloneStringAttribute(DIE &Die,
1209 AttributeSpec AttrSpec,
1210 const DWARFFormValue &Val,
1211 const DWARFUnit &U,
1212 AttributesInfo &Info) {
1213 std::optional<const char *> String = dwarf::toString(V: Val);
1214 if (!String)
1215 return 0;
1216 DwarfStringPoolEntryRef StringEntry;
1217 if (AttrSpec.Form == dwarf::DW_FORM_line_strp) {
1218 StringEntry = DebugLineStrPool.getEntry(S: *String);
1219 } else {
1220 StringEntry = DebugStrPool.getEntry(S: *String);
1221
1222 if (AttrSpec.Attr == dwarf::DW_AT_APPLE_origin) {
1223 Info.HasAppleOrigin = true;
1224 if (std::optional<StringRef> FileName =
1225 ObjFile.Addresses->getLibraryInstallName()) {
1226 StringEntry = DebugStrPool.getEntry(S: *FileName);
1227 }
1228 }
1229
1230 // Update attributes info.
1231 if (AttrSpec.Attr == dwarf::DW_AT_name)
1232 Info.Name = StringEntry;
1233 else if (AttrSpec.Attr == dwarf::DW_AT_MIPS_linkage_name ||
1234 AttrSpec.Attr == dwarf::DW_AT_linkage_name)
1235 Info.MangledName = StringEntry;
1236 if (U.getVersion() >= 5) {
1237 // Switch everything to DW_FORM_strx strings.
1238 auto StringOffsetIndex =
1239 StringOffsetPool.getValueIndex(Value: StringEntry.getOffset());
1240 return Die
1241 .addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1242 Form: dwarf::DW_FORM_strx, Value: DIEInteger(StringOffsetIndex))
1243 ->sizeOf(FormParams: U.getFormParams());
1244 }
1245 // Switch everything to out of line strings.
1246 AttrSpec.Form = dwarf::DW_FORM_strp;
1247 }
1248 Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr), Form: AttrSpec.Form,
1249 Value: DIEInteger(StringEntry.getOffset()));
1250 return 4;
1251}
1252
1253unsigned DWARFLinker::DIECloner::cloneDieReferenceAttribute(
1254 DIE &Die, const DWARFDie &InputDIE, AttributeSpec AttrSpec,
1255 unsigned AttrSize, const DWARFFormValue &Val, const DWARFFile &File,
1256 CompileUnit &Unit) {
1257 const DWARFUnit &U = Unit.getOrigUnit();
1258 uint64_t Ref;
1259 if (std::optional<uint64_t> Off = Val.getAsRelativeReference())
1260 Ref = Val.getUnit()->getOffset() + *Off;
1261 else if (Off = Val.getAsDebugInfoReference(); Off)
1262 Ref = *Off;
1263 else
1264 return 0;
1265
1266 DIE *NewRefDie = nullptr;
1267 CompileUnit *RefUnit = nullptr;
1268
1269 DWARFDie RefDie =
1270 Linker.resolveDIEReference(File, Units: CompileUnits, RefValue: Val, DIE: InputDIE, RefCU&: RefUnit);
1271
1272 // If the referenced DIE is not found, drop the attribute.
1273 if (!RefDie || AttrSpec.Attr == dwarf::DW_AT_sibling)
1274 return 0;
1275
1276 CompileUnit::DIEInfo &RefInfo = RefUnit->getInfo(Die: RefDie);
1277
1278 // If we already have emitted an equivalent DeclContext, just point
1279 // at it.
1280 if (isODRAttribute(Attr: AttrSpec.Attr) && RefInfo.Ctxt &&
1281 RefInfo.Ctxt->getCanonicalDIEOffset()) {
1282 assert(RefInfo.Ctxt->hasCanonicalDIE() &&
1283 "Offset to canonical die is set, but context is not marked");
1284 DIEInteger Attr(RefInfo.Ctxt->getCanonicalDIEOffset());
1285 Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1286 Form: dwarf::DW_FORM_ref_addr, Value&: Attr);
1287 return U.getRefAddrByteSize();
1288 }
1289
1290 if (!RefInfo.Clone) {
1291 // We haven't cloned this DIE yet. Just create an empty one and
1292 // store it. It'll get really cloned when we process it.
1293 RefInfo.UnclonedReference = true;
1294 RefInfo.Clone = DIE::get(Alloc&: DIEAlloc, Tag: dwarf::Tag(RefDie.getTag()));
1295 }
1296 NewRefDie = RefInfo.Clone;
1297
1298 if (AttrSpec.Form == dwarf::DW_FORM_ref_addr ||
1299 (Unit.hasODR() && isODRAttribute(Attr: AttrSpec.Attr))) {
1300 // We cannot currently rely on a DIEEntry to emit ref_addr
1301 // references, because the implementation calls back to DwarfDebug
1302 // to find the unit offset. (We don't have a DwarfDebug)
1303 // FIXME: we should be able to design DIEEntry reliance on
1304 // DwarfDebug away.
1305 uint64_t Attr;
1306 if (Ref < InputDIE.getOffset() && !RefInfo.UnclonedReference) {
1307 // We have already cloned that DIE.
1308 uint32_t NewRefOffset =
1309 RefUnit->getStartOffset() + NewRefDie->getOffset();
1310 Attr = NewRefOffset;
1311 Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1312 Form: dwarf::DW_FORM_ref_addr, Value: DIEInteger(Attr));
1313 } else {
1314 // A forward reference. Note and fixup later.
1315 Attr = 0xBADDEF;
1316 Unit.noteForwardReference(
1317 Die: NewRefDie, RefUnit, Ctxt: RefInfo.Ctxt,
1318 Attr: Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1319 Form: dwarf::DW_FORM_ref_addr, Value: DIEInteger(Attr)));
1320 }
1321 return U.getRefAddrByteSize();
1322 }
1323
1324 Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1325 Form: dwarf::Form(AttrSpec.Form), Value: DIEEntry(*NewRefDie));
1326
1327 return AttrSize;
1328}
1329
1330void DWARFLinker::DIECloner::cloneExpression(
1331 DataExtractor &Data, DWARFExpression Expression, const DWARFFile &File,
1332 CompileUnit &Unit, SmallVectorImpl<uint8_t> &OutputBuffer,
1333 int64_t AddrRelocAdjustment, bool IsLittleEndian) {
1334 using Encoding = DWARFExpression::Operation::Encoding;
1335
1336 uint8_t OrigAddressByteSize = Unit.getOrigUnit().getAddressByteSize();
1337
1338 uint64_t OpOffset = 0;
1339 for (auto &Op : Expression) {
1340 auto Desc = Op.getDescription();
1341 // DW_OP_const_type is variable-length and has 3
1342 // operands. Thus far we only support 2.
1343 if ((Desc.Op.size() == 2 && Desc.Op[0] == Encoding::BaseTypeRef) ||
1344 (Desc.Op.size() == 2 && Desc.Op[1] == Encoding::BaseTypeRef &&
1345 Desc.Op[0] != Encoding::Size1))
1346 Linker.reportWarning(Warning: "Unsupported DW_OP encoding.", File);
1347
1348 if ((Desc.Op.size() == 1 && Desc.Op[0] == Encoding::BaseTypeRef) ||
1349 (Desc.Op.size() == 2 && Desc.Op[1] == Encoding::BaseTypeRef &&
1350 Desc.Op[0] == Encoding::Size1)) {
1351 // This code assumes that the other non-typeref operand fits into 1 byte.
1352 assert(OpOffset < Op.getEndOffset());
1353 uint32_t ULEBsize = Op.getEndOffset() - OpOffset - 1;
1354 assert(ULEBsize <= 16);
1355
1356 // Copy over the operation.
1357 assert(!Op.getSubCode() && "SubOps not yet supported");
1358 OutputBuffer.push_back(Elt: Op.getCode());
1359 uint64_t RefOffset;
1360 if (Desc.Op.size() == 1) {
1361 RefOffset = Op.getRawOperand(Idx: 0);
1362 } else {
1363 OutputBuffer.push_back(Elt: Op.getRawOperand(Idx: 0));
1364 RefOffset = Op.getRawOperand(Idx: 1);
1365 }
1366 uint32_t Offset = 0;
1367 // Look up the base type. For DW_OP_convert, the operand may be 0 to
1368 // instead indicate the generic type. The same holds for
1369 // DW_OP_reinterpret, which is currently not supported.
1370 if (RefOffset > 0 || Op.getCode() != dwarf::DW_OP_convert) {
1371 RefOffset += Unit.getOrigUnit().getOffset();
1372 auto RefDie = Unit.getOrigUnit().getDIEForOffset(Offset: RefOffset);
1373 CompileUnit::DIEInfo &Info = Unit.getInfo(Die: RefDie);
1374 if (DIE *Clone = Info.Clone)
1375 Offset = Clone->getOffset();
1376 else
1377 Linker.reportWarning(
1378 Warning: "base type ref doesn't point to DW_TAG_base_type.", File);
1379 }
1380 uint8_t ULEB[16];
1381 unsigned RealSize = encodeULEB128(Value: Offset, p: ULEB, PadTo: ULEBsize);
1382 if (RealSize > ULEBsize) {
1383 // Emit the generic type as a fallback.
1384 RealSize = encodeULEB128(Value: 0, p: ULEB, PadTo: ULEBsize);
1385 Linker.reportWarning(Warning: "base type ref doesn't fit.", File);
1386 }
1387 assert(RealSize == ULEBsize && "padding failed");
1388 ArrayRef<uint8_t> ULEBbytes(ULEB, ULEBsize);
1389 OutputBuffer.append(in_start: ULEBbytes.begin(), in_end: ULEBbytes.end());
1390 } else if (!Linker.Options.Update && Op.getCode() == dwarf::DW_OP_addrx) {
1391 if (std::optional<object::SectionedAddress> SA =
1392 Unit.getOrigUnit().getAddrOffsetSectionItem(
1393 Index: Op.getRawOperand(Idx: 0))) {
1394 // DWARFLinker does not use addrx forms since it generates relocated
1395 // addresses. Replace DW_OP_addrx with DW_OP_addr here.
1396 // Argument of DW_OP_addrx should be relocated here as it is not
1397 // processed by applyValidRelocs.
1398 OutputBuffer.push_back(Elt: dwarf::DW_OP_addr);
1399 uint64_t LinkedAddress = SA->Address + AddrRelocAdjustment;
1400 if (IsLittleEndian != sys::IsLittleEndianHost)
1401 sys::swapByteOrder(Value&: LinkedAddress);
1402 ArrayRef<uint8_t> AddressBytes(
1403 reinterpret_cast<const uint8_t *>(&LinkedAddress),
1404 OrigAddressByteSize);
1405 OutputBuffer.append(in_start: AddressBytes.begin(), in_end: AddressBytes.end());
1406 } else
1407 Linker.reportWarning(Warning: "cannot read DW_OP_addrx operand.", File);
1408 } else if (!Linker.Options.Update && Op.getCode() == dwarf::DW_OP_constx) {
1409 if (std::optional<object::SectionedAddress> SA =
1410 Unit.getOrigUnit().getAddrOffsetSectionItem(
1411 Index: Op.getRawOperand(Idx: 0))) {
1412 // DWARFLinker does not use constx forms since it generates relocated
1413 // addresses. Replace DW_OP_constx with DW_OP_const[*]u here.
1414 // Argument of DW_OP_constx should be relocated here as it is not
1415 // processed by applyValidRelocs.
1416 std::optional<uint8_t> OutOperandKind;
1417 switch (OrigAddressByteSize) {
1418 case 4:
1419 OutOperandKind = dwarf::DW_OP_const4u;
1420 break;
1421 case 8:
1422 OutOperandKind = dwarf::DW_OP_const8u;
1423 break;
1424 default:
1425 Linker.reportWarning(
1426 Warning: formatv(Fmt: ("unsupported address size: {0}."), Vals&: OrigAddressByteSize),
1427 File);
1428 break;
1429 }
1430
1431 if (OutOperandKind) {
1432 OutputBuffer.push_back(Elt: *OutOperandKind);
1433 uint64_t LinkedAddress = SA->Address + AddrRelocAdjustment;
1434 if (IsLittleEndian != sys::IsLittleEndianHost)
1435 sys::swapByteOrder(Value&: LinkedAddress);
1436 ArrayRef<uint8_t> AddressBytes(
1437 reinterpret_cast<const uint8_t *>(&LinkedAddress),
1438 OrigAddressByteSize);
1439 OutputBuffer.append(in_start: AddressBytes.begin(), in_end: AddressBytes.end());
1440 }
1441 } else
1442 Linker.reportWarning(Warning: "cannot read DW_OP_constx operand.", File);
1443 } else {
1444 // Copy over everything else unmodified.
1445 StringRef Bytes = Data.getData().slice(Start: OpOffset, End: Op.getEndOffset());
1446 OutputBuffer.append(in_start: Bytes.begin(), in_end: Bytes.end());
1447 }
1448 OpOffset = Op.getEndOffset();
1449 }
1450}
1451
1452unsigned DWARFLinker::DIECloner::cloneBlockAttribute(
1453 DIE &Die, const DWARFDie &InputDIE, const DWARFFile &File,
1454 CompileUnit &Unit, AttributeSpec AttrSpec, const DWARFFormValue &Val,
1455 bool IsLittleEndian) {
1456 DIEValueList *Attr;
1457 DIEValue Value;
1458 DIELoc *Loc = nullptr;
1459 DIEBlock *Block = nullptr;
1460 if (AttrSpec.Form == dwarf::DW_FORM_exprloc) {
1461 Loc = new (DIEAlloc) DIELoc;
1462 Linker.DIELocs.push_back(x: Loc);
1463 } else {
1464 Block = new (DIEAlloc) DIEBlock;
1465 Linker.DIEBlocks.push_back(x: Block);
1466 }
1467 Attr = Loc ? static_cast<DIEValueList *>(Loc)
1468 : static_cast<DIEValueList *>(Block);
1469
1470 DWARFUnit &OrigUnit = Unit.getOrigUnit();
1471 // If the block is a DWARF Expression, clone it into the temporary
1472 // buffer using cloneExpression(), otherwise copy the data directly.
1473 SmallVector<uint8_t, 32> Buffer;
1474 ArrayRef<uint8_t> Bytes = *Val.getAsBlock();
1475 if (DWARFAttribute::mayHaveLocationExpr(Attr: AttrSpec.Attr) &&
1476 (Val.isFormClass(FC: DWARFFormValue::FC_Block) ||
1477 Val.isFormClass(FC: DWARFFormValue::FC_Exprloc))) {
1478 DataExtractor Data(StringRef((const char *)Bytes.data(), Bytes.size()),
1479 IsLittleEndian, OrigUnit.getAddressByteSize());
1480 DWARFExpression Expr(Data, OrigUnit.getAddressByteSize(),
1481 OrigUnit.getFormParams().Format);
1482 cloneExpression(Data, Expression: Expr, File, Unit, OutputBuffer&: Buffer,
1483 AddrRelocAdjustment: Unit.getInfo(Die: InputDIE).AddrAdjust, IsLittleEndian);
1484 Bytes = Buffer;
1485 }
1486 for (auto Byte : Bytes)
1487 Attr->addValue(Alloc&: DIEAlloc, Attribute: static_cast<dwarf::Attribute>(0),
1488 Form: dwarf::DW_FORM_data1, Value: DIEInteger(Byte));
1489
1490 // FIXME: If DIEBlock and DIELoc just reuses the Size field of
1491 // the DIE class, this "if" could be replaced by
1492 // Attr->setSize(Bytes.size()).
1493 if (Loc)
1494 Loc->setSize(Bytes.size());
1495 else
1496 Block->setSize(Bytes.size());
1497
1498 if (Loc)
1499 Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
1500 dwarf::Form(AttrSpec.Form), Loc);
1501 else {
1502 // The expression location data might be updated and exceed the original
1503 // size. Check whether the new data fits into the original form.
1504 if ((AttrSpec.Form == dwarf::DW_FORM_block1 &&
1505 (Bytes.size() > UINT8_MAX)) ||
1506 (AttrSpec.Form == dwarf::DW_FORM_block2 &&
1507 (Bytes.size() > UINT16_MAX)) ||
1508 (AttrSpec.Form == dwarf::DW_FORM_block4 && (Bytes.size() > UINT32_MAX)))
1509 AttrSpec.Form = dwarf::DW_FORM_block;
1510
1511 Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
1512 dwarf::Form(AttrSpec.Form), Block);
1513 }
1514
1515 return Die.addValue(Alloc&: DIEAlloc, V: Value)->sizeOf(FormParams: OrigUnit.getFormParams());
1516}
1517
1518unsigned DWARFLinker::DIECloner::cloneAddressAttribute(
1519 DIE &Die, const DWARFDie &InputDIE, AttributeSpec AttrSpec,
1520 unsigned AttrSize, const DWARFFormValue &Val, const CompileUnit &Unit,
1521 AttributesInfo &Info) {
1522 if (AttrSpec.Attr == dwarf::DW_AT_low_pc)
1523 Info.HasLowPc = true;
1524
1525 if (LLVM_UNLIKELY(Linker.Options.Update)) {
1526 Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1527 Form: dwarf::Form(AttrSpec.Form), Value: DIEInteger(Val.getRawUValue()));
1528 return AttrSize;
1529 }
1530
1531 // Cloned Die may have address attributes relocated to a
1532 // totally unrelated value. This can happen:
1533 // - If high_pc is an address (Dwarf version == 2), then it might have been
1534 // relocated to a totally unrelated value (because the end address in the
1535 // object file might be start address of another function which got moved
1536 // independently by the linker).
1537 // - If address relocated in an inline_subprogram that happens at the
1538 // beginning of its inlining function.
1539 // To avoid above cases and to not apply relocation twice (in
1540 // applyValidRelocs and here), read address attribute from InputDIE and apply
1541 // Info.PCOffset here.
1542
1543 std::optional<DWARFFormValue> AddrAttribute = InputDIE.find(Attr: AttrSpec.Attr);
1544 if (!AddrAttribute)
1545 llvm_unreachable("Cann't find attribute.");
1546
1547 std::optional<uint64_t> Addr = AddrAttribute->getAsAddress();
1548 if (!Addr) {
1549 Linker.reportWarning(Warning: "Cann't read address attribute value.", File: ObjFile);
1550 return 0;
1551 }
1552
1553 if (InputDIE.getTag() == dwarf::DW_TAG_compile_unit &&
1554 AttrSpec.Attr == dwarf::DW_AT_low_pc) {
1555 if (std::optional<uint64_t> LowPC = Unit.getLowPc())
1556 Addr = *LowPC;
1557 else
1558 return 0;
1559 } else if (InputDIE.getTag() == dwarf::DW_TAG_compile_unit &&
1560 AttrSpec.Attr == dwarf::DW_AT_high_pc) {
1561 if (uint64_t HighPc = Unit.getHighPc())
1562 Addr = HighPc;
1563 else
1564 return 0;
1565 } else {
1566 *Addr += Info.PCOffset;
1567 }
1568
1569 if (AttrSpec.Form == dwarf::DW_FORM_addr) {
1570 Die.addValue(Alloc&: DIEAlloc, Attribute: static_cast<dwarf::Attribute>(AttrSpec.Attr),
1571 Form: AttrSpec.Form, Value: DIEInteger(*Addr));
1572 return Unit.getOrigUnit().getAddressByteSize();
1573 }
1574
1575 auto AddrIndex = AddrPool.getValueIndex(Value: *Addr);
1576
1577 return Die
1578 .addValue(Alloc&: DIEAlloc, Attribute: static_cast<dwarf::Attribute>(AttrSpec.Attr),
1579 Form: dwarf::Form::DW_FORM_addrx, Value: DIEInteger(AddrIndex))
1580 ->sizeOf(FormParams: Unit.getOrigUnit().getFormParams());
1581}
1582
1583unsigned DWARFLinker::DIECloner::cloneScalarAttribute(
1584 DIE &Die, const DWARFDie &InputDIE, const DWARFFile &File,
1585 CompileUnit &Unit, AttributeSpec AttrSpec, const DWARFFormValue &Val,
1586 unsigned AttrSize, AttributesInfo &Info) {
1587 uint64_t Value;
1588
1589 // We don't emit any skeleton CUs with dsymutil. So avoid emitting
1590 // a redundant DW_AT_GNU_dwo_id on the non-skeleton CU.
1591 if (AttrSpec.Attr == dwarf::DW_AT_GNU_dwo_id ||
1592 AttrSpec.Attr == dwarf::DW_AT_dwo_id)
1593 return 0;
1594
1595 // Check for the offset to the macro table. If offset is incorrect then we
1596 // need to remove the attribute.
1597 if (AttrSpec.Attr == dwarf::DW_AT_macro_info) {
1598 if (std::optional<uint64_t> Offset = Val.getAsSectionOffset()) {
1599 const llvm::DWARFDebugMacro *Macro = File.Dwarf->getDebugMacinfo();
1600 if (Macro == nullptr || !Macro->hasEntryForOffset(Offset: *Offset))
1601 return 0;
1602 }
1603 }
1604
1605 if (AttrSpec.Attr == dwarf::DW_AT_macros) {
1606 if (std::optional<uint64_t> Offset = Val.getAsSectionOffset()) {
1607 const llvm::DWARFDebugMacro *Macro = File.Dwarf->getDebugMacro();
1608 if (Macro == nullptr || !Macro->hasEntryForOffset(Offset: *Offset))
1609 return 0;
1610 }
1611 }
1612
1613 if (AttrSpec.Attr == dwarf::DW_AT_str_offsets_base) {
1614 // DWARFLinker generates common .debug_str_offsets table used for all
1615 // compile units. The offset to the common .debug_str_offsets table is 8 on
1616 // DWARF32.
1617 Info.AttrStrOffsetBaseSeen = true;
1618 return Die
1619 .addValue(Alloc&: DIEAlloc, Attribute: dwarf::DW_AT_str_offsets_base,
1620 Form: dwarf::DW_FORM_sec_offset, Value: DIEInteger(8))
1621 ->sizeOf(FormParams: Unit.getOrigUnit().getFormParams());
1622 }
1623
1624 if (AttrSpec.Attr == dwarf::DW_AT_LLVM_stmt_sequence) {
1625 // If needed, we'll patch this sec_offset later with the correct offset.
1626 auto Patch = Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1627 Form: dwarf::DW_FORM_sec_offset,
1628 Value: DIEInteger(*Val.getAsSectionOffset()));
1629
1630 // Record this patch location so that it can be fixed up later.
1631 Unit.noteStmtSeqListAttribute(Attr: Patch);
1632
1633 return Unit.getOrigUnit().getFormParams().getDwarfOffsetByteSize();
1634 }
1635
1636 if (LLVM_UNLIKELY(Linker.Options.Update)) {
1637 if (auto OptionalValue = Val.getAsUnsignedConstant())
1638 Value = *OptionalValue;
1639 else if (auto OptionalValue = Val.getAsSignedConstant())
1640 Value = *OptionalValue;
1641 else if (auto OptionalValue = Val.getAsSectionOffset())
1642 Value = *OptionalValue;
1643 else {
1644 Linker.reportWarning(
1645 Warning: "Unsupported scalar attribute form. Dropping attribute.", File,
1646 DIE: &InputDIE);
1647 return 0;
1648 }
1649 if (AttrSpec.Attr == dwarf::DW_AT_declaration && Value)
1650 Info.IsDeclaration = true;
1651
1652 if (AttrSpec.Form == dwarf::DW_FORM_loclistx)
1653 Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1654 Form: dwarf::Form(AttrSpec.Form), Value: DIELocList(Value));
1655 else
1656 Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1657 Form: dwarf::Form(AttrSpec.Form), Value: DIEInteger(Value));
1658 return AttrSize;
1659 }
1660
1661 [[maybe_unused]] dwarf::Form OriginalForm = AttrSpec.Form;
1662 if (AttrSpec.Form == dwarf::DW_FORM_rnglistx) {
1663 // DWARFLinker does not generate .debug_addr table. Thus we need to change
1664 // all "addrx" related forms to "addr" version. Change DW_FORM_rnglistx
1665 // to DW_FORM_sec_offset here.
1666 std::optional<uint64_t> Index = Val.getAsSectionOffset();
1667 if (!Index) {
1668 Linker.reportWarning(Warning: "Cannot read the attribute. Dropping.", File,
1669 DIE: &InputDIE);
1670 return 0;
1671 }
1672 std::optional<uint64_t> Offset =
1673 Unit.getOrigUnit().getRnglistOffset(Index: *Index);
1674 if (!Offset) {
1675 Linker.reportWarning(Warning: "Cannot read the attribute. Dropping.", File,
1676 DIE: &InputDIE);
1677 return 0;
1678 }
1679
1680 Value = *Offset;
1681 AttrSpec.Form = dwarf::DW_FORM_sec_offset;
1682 AttrSize = Unit.getOrigUnit().getFormParams().getDwarfOffsetByteSize();
1683 } else if (AttrSpec.Form == dwarf::DW_FORM_loclistx) {
1684 // DWARFLinker does not generate .debug_addr table. Thus we need to change
1685 // all "addrx" related forms to "addr" version. Change DW_FORM_loclistx
1686 // to DW_FORM_sec_offset here.
1687 std::optional<uint64_t> Index = Val.getAsSectionOffset();
1688 if (!Index) {
1689 Linker.reportWarning(Warning: "Cannot read the attribute. Dropping.", File,
1690 DIE: &InputDIE);
1691 return 0;
1692 }
1693 std::optional<uint64_t> Offset =
1694 Unit.getOrigUnit().getLoclistOffset(Index: *Index);
1695 if (!Offset) {
1696 Linker.reportWarning(Warning: "Cannot read the attribute. Dropping.", File,
1697 DIE: &InputDIE);
1698 return 0;
1699 }
1700
1701 Value = *Offset;
1702 AttrSpec.Form = dwarf::DW_FORM_sec_offset;
1703 AttrSize = Unit.getOrigUnit().getFormParams().getDwarfOffsetByteSize();
1704 } else if (AttrSpec.Attr == dwarf::DW_AT_high_pc &&
1705 Die.getTag() == dwarf::DW_TAG_compile_unit) {
1706 std::optional<uint64_t> LowPC = Unit.getLowPc();
1707 if (!LowPC)
1708 return 0;
1709 // Dwarf >= 4 high_pc is an size, not an address.
1710 Value = Unit.getHighPc() - *LowPC;
1711 } else if (AttrSpec.Form == dwarf::DW_FORM_sec_offset)
1712 Value = *Val.getAsSectionOffset();
1713 else if (AttrSpec.Form == dwarf::DW_FORM_sdata)
1714 Value = *Val.getAsSignedConstant();
1715 else if (auto OptionalValue = Val.getAsUnsignedConstant())
1716 Value = *OptionalValue;
1717 else {
1718 Linker.reportWarning(
1719 Warning: "Unsupported scalar attribute form. Dropping attribute.", File,
1720 DIE: &InputDIE);
1721 return 0;
1722 }
1723
1724 DIE::value_iterator Patch =
1725 Die.addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(AttrSpec.Attr),
1726 Form: dwarf::Form(AttrSpec.Form), Value: DIEInteger(Value));
1727 if (AttrSpec.Attr == dwarf::DW_AT_ranges ||
1728 AttrSpec.Attr == dwarf::DW_AT_start_scope) {
1729 Unit.noteRangeAttribute(Die, Attr: Patch);
1730 Info.HasRanges = true;
1731 } else if (DWARFAttribute::mayHaveLocationList(Attr: AttrSpec.Attr) &&
1732 dwarf::doesFormBelongToClass(Form: AttrSpec.Form,
1733 FC: DWARFFormValue::FC_SectionOffset,
1734 DwarfVersion: Unit.getOrigUnit().getVersion())) {
1735
1736 CompileUnit::DIEInfo &LocationDieInfo = Unit.getInfo(Die: InputDIE);
1737 Unit.noteLocationAttribute(Attr: {Patch, LocationDieInfo.InDebugMap
1738 ? LocationDieInfo.AddrAdjust
1739 : Info.PCOffset});
1740 } else if (AttrSpec.Attr == dwarf::DW_AT_declaration && Value)
1741 Info.IsDeclaration = true;
1742
1743 // check that all dwarf::DW_FORM_rnglistx are handled previously.
1744 assert((Info.HasRanges || (OriginalForm != dwarf::DW_FORM_rnglistx)) &&
1745 "Unhandled DW_FORM_rnglistx attribute");
1746
1747 return AttrSize;
1748}
1749
1750/// Clone \p InputDIE's attribute described by \p AttrSpec with
1751/// value \p Val, and add it to \p Die.
1752/// \returns the size of the cloned attribute.
1753unsigned DWARFLinker::DIECloner::cloneAttribute(
1754 DIE &Die, const DWARFDie &InputDIE, const DWARFFile &File,
1755 CompileUnit &Unit, const DWARFFormValue &Val, const AttributeSpec AttrSpec,
1756 unsigned AttrSize, AttributesInfo &Info, bool IsLittleEndian) {
1757 const DWARFUnit &U = Unit.getOrigUnit();
1758
1759 switch (AttrSpec.Form) {
1760 case dwarf::DW_FORM_strp:
1761 case dwarf::DW_FORM_line_strp:
1762 case dwarf::DW_FORM_string:
1763 case dwarf::DW_FORM_strx:
1764 case dwarf::DW_FORM_strx1:
1765 case dwarf::DW_FORM_strx2:
1766 case dwarf::DW_FORM_strx3:
1767 case dwarf::DW_FORM_strx4:
1768 return cloneStringAttribute(Die, AttrSpec, Val, U, Info);
1769 case dwarf::DW_FORM_ref_addr:
1770 case dwarf::DW_FORM_ref1:
1771 case dwarf::DW_FORM_ref2:
1772 case dwarf::DW_FORM_ref4:
1773 case dwarf::DW_FORM_ref8:
1774 return cloneDieReferenceAttribute(Die, InputDIE, AttrSpec, AttrSize, Val,
1775 File, Unit);
1776 case dwarf::DW_FORM_block:
1777 case dwarf::DW_FORM_block1:
1778 case dwarf::DW_FORM_block2:
1779 case dwarf::DW_FORM_block4:
1780 case dwarf::DW_FORM_exprloc:
1781 return cloneBlockAttribute(Die, InputDIE, File, Unit, AttrSpec, Val,
1782 IsLittleEndian);
1783 case dwarf::DW_FORM_addr:
1784 case dwarf::DW_FORM_addrx:
1785 case dwarf::DW_FORM_addrx1:
1786 case dwarf::DW_FORM_addrx2:
1787 case dwarf::DW_FORM_addrx3:
1788 case dwarf::DW_FORM_addrx4:
1789 return cloneAddressAttribute(Die, InputDIE, AttrSpec, AttrSize, Val, Unit,
1790 Info);
1791 case dwarf::DW_FORM_data1:
1792 case dwarf::DW_FORM_data2:
1793 case dwarf::DW_FORM_data4:
1794 case dwarf::DW_FORM_data8:
1795 case dwarf::DW_FORM_udata:
1796 case dwarf::DW_FORM_sdata:
1797 case dwarf::DW_FORM_sec_offset:
1798 case dwarf::DW_FORM_flag:
1799 case dwarf::DW_FORM_flag_present:
1800 case dwarf::DW_FORM_rnglistx:
1801 case dwarf::DW_FORM_loclistx:
1802 case dwarf::DW_FORM_implicit_const:
1803 return cloneScalarAttribute(Die, InputDIE, File, Unit, AttrSpec, Val,
1804 AttrSize, Info);
1805 default:
1806 Linker.reportWarning(Warning: "Unsupported attribute form " +
1807 dwarf::FormEncodingString(Encoding: AttrSpec.Form) +
1808 " in cloneAttribute. Dropping.",
1809 File, DIE: &InputDIE);
1810 }
1811
1812 return 0;
1813}
1814
1815void DWARFLinker::DIECloner::addObjCAccelerator(CompileUnit &Unit,
1816 const DIE *Die,
1817 DwarfStringPoolEntryRef Name,
1818 OffsetsStringPool &StringPool,
1819 bool SkipPubSection) {
1820 std::optional<ObjCSelectorNames> Names =
1821 getObjCNamesIfSelector(Name: Name.getString());
1822 if (!Names)
1823 return;
1824 Unit.addNameAccelerator(Die, Name: StringPool.getEntry(S: Names->Selector),
1825 SkipPubnamesSection: SkipPubSection);
1826 Unit.addObjCAccelerator(Die, Name: StringPool.getEntry(S: Names->ClassName),
1827 SkipPubnamesSection: SkipPubSection);
1828 if (Names->ClassNameNoCategory)
1829 Unit.addObjCAccelerator(
1830 Die, Name: StringPool.getEntry(S: *Names->ClassNameNoCategory), SkipPubnamesSection: SkipPubSection);
1831 if (Names->MethodNameNoCategory)
1832 Unit.addNameAccelerator(
1833 Die, Name: StringPool.getEntry(S: *Names->MethodNameNoCategory), SkipPubnamesSection: SkipPubSection);
1834}
1835
1836static bool
1837shouldSkipAttribute(bool Update,
1838 DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
1839 bool SkipPC) {
1840 switch (AttrSpec.Attr) {
1841 default:
1842 return false;
1843 case dwarf::DW_AT_low_pc:
1844 case dwarf::DW_AT_high_pc:
1845 case dwarf::DW_AT_ranges:
1846 return !Update && SkipPC;
1847 case dwarf::DW_AT_rnglists_base:
1848 // In case !Update the .debug_addr table is not generated/preserved.
1849 // Thus instead of DW_FORM_rnglistx the DW_FORM_sec_offset is used.
1850 // Since DW_AT_rnglists_base is used for only DW_FORM_rnglistx the
1851 // DW_AT_rnglists_base is removed.
1852 return !Update;
1853 case dwarf::DW_AT_loclists_base:
1854 // In case !Update the .debug_addr table is not generated/preserved.
1855 // Thus instead of DW_FORM_loclistx the DW_FORM_sec_offset is used.
1856 // Since DW_AT_loclists_base is used for only DW_FORM_loclistx the
1857 // DW_AT_loclists_base is removed.
1858 return !Update;
1859 case dwarf::DW_AT_location:
1860 case dwarf::DW_AT_frame_base:
1861 return !Update && SkipPC;
1862 }
1863}
1864
1865struct AttributeLinkedOffsetFixup {
1866 int64_t LinkedOffsetFixupVal;
1867 uint64_t InputAttrStartOffset;
1868 uint64_t InputAttrEndOffset;
1869};
1870
1871DIE *DWARFLinker::DIECloner::cloneDIE(const DWARFDie &InputDIE,
1872 const DWARFFile &File, CompileUnit &Unit,
1873 int64_t PCOffset, uint32_t OutOffset,
1874 unsigned Flags, bool IsLittleEndian,
1875 DIE *Die) {
1876 DWARFUnit &U = Unit.getOrigUnit();
1877 unsigned Idx = U.getDIEIndex(D: InputDIE);
1878 CompileUnit::DIEInfo &Info = Unit.getInfo(Idx);
1879
1880 // Should the DIE appear in the output?
1881 if (!Unit.getInfo(Idx).Keep)
1882 return nullptr;
1883
1884 uint64_t Offset = InputDIE.getOffset();
1885 assert(!(Die && Info.Clone) && "Can't supply a DIE and a cloned DIE");
1886 if (!Die) {
1887 // The DIE might have been already created by a forward reference
1888 // (see cloneDieReferenceAttribute()).
1889 if (!Info.Clone)
1890 Info.Clone = DIE::get(Alloc&: DIEAlloc, Tag: dwarf::Tag(InputDIE.getTag()));
1891 Die = Info.Clone;
1892 }
1893
1894 assert(Die->getTag() == InputDIE.getTag());
1895 Die->setOffset(OutOffset);
1896 if (isODRCanonicalCandidate(Die: InputDIE, CU&: Unit) && Info.Ctxt &&
1897 (Info.Ctxt->getCanonicalDIEOffset() == 0)) {
1898 if (!Info.Ctxt->hasCanonicalDIE())
1899 Info.Ctxt->setHasCanonicalDIE();
1900 // We are about to emit a DIE that is the root of its own valid
1901 // DeclContext tree. Make the current offset the canonical offset
1902 // for this context.
1903 Info.Ctxt->setCanonicalDIEOffset(OutOffset + Unit.getStartOffset());
1904 }
1905
1906 // Extract and clone every attribute.
1907 DWARFDataExtractor Data = U.getDebugInfoExtractor();
1908 // Point to the next DIE (generally there is always at least a NULL
1909 // entry after the current one). If this is a lone
1910 // DW_TAG_compile_unit without any children, point to the next unit.
1911 uint64_t NextOffset = (Idx + 1 < U.getNumDIEs())
1912 ? U.getDIEAtIndex(Index: Idx + 1).getOffset()
1913 : U.getNextUnitOffset();
1914 AttributesInfo AttrInfo;
1915
1916 // We could copy the data only if we need to apply a relocation to it. After
1917 // testing, it seems there is no performance downside to doing the copy
1918 // unconditionally, and it makes the code simpler.
1919 SmallString<40> DIECopy(Data.getData().substr(Start: Offset, N: NextOffset - Offset));
1920 Data =
1921 DWARFDataExtractor(DIECopy, Data.isLittleEndian(), Data.getAddressSize());
1922
1923 // Modify the copy with relocated addresses.
1924 ObjFile.Addresses->applyValidRelocs(Data: DIECopy, BaseOffset: Offset, IsLittleEndian: Data.isLittleEndian());
1925
1926 // Reset the Offset to 0 as we will be working on the local copy of
1927 // the data.
1928 Offset = 0;
1929
1930 const auto *Abbrev = InputDIE.getAbbreviationDeclarationPtr();
1931 Offset += getULEB128Size(Value: Abbrev->getCode());
1932
1933 // We are entering a subprogram. Get and propagate the PCOffset.
1934 if (Die->getTag() == dwarf::DW_TAG_subprogram)
1935 PCOffset = Info.AddrAdjust;
1936 AttrInfo.PCOffset = PCOffset;
1937
1938 if (Abbrev->getTag() == dwarf::DW_TAG_subprogram) {
1939 Flags |= TF_InFunctionScope;
1940 if (!Info.InDebugMap && LLVM_LIKELY(!Update))
1941 Flags |= TF_SkipPC;
1942 } else if (Abbrev->getTag() == dwarf::DW_TAG_variable) {
1943 // Function-local globals could be in the debug map even when the function
1944 // is not, e.g., inlined functions.
1945 if ((Flags & TF_InFunctionScope) && Info.InDebugMap)
1946 Flags &= ~TF_SkipPC;
1947 // Location expressions referencing an address which is not in debug map
1948 // should be deleted.
1949 else if (!Info.InDebugMap && Info.HasLocationExpressionAddr &&
1950 LLVM_LIKELY(!Update))
1951 Flags |= TF_SkipPC;
1952 }
1953
1954 std::optional<StringRef> LibraryInstallName =
1955 ObjFile.Addresses->getLibraryInstallName();
1956 SmallVector<AttributeLinkedOffsetFixup> AttributesFixups;
1957 for (const auto &AttrSpec : Abbrev->attributes()) {
1958 if (shouldSkipAttribute(Update, AttrSpec, SkipPC: Flags & TF_SkipPC)) {
1959 DWARFFormValue::skipValue(Form: AttrSpec.Form, DebugInfoData: Data, OffsetPtr: &Offset,
1960 FormParams: U.getFormParams());
1961 continue;
1962 }
1963
1964 AttributeLinkedOffsetFixup CurAttrFixup;
1965 CurAttrFixup.InputAttrStartOffset = InputDIE.getOffset() + Offset;
1966 CurAttrFixup.LinkedOffsetFixupVal =
1967 Unit.getStartOffset() + OutOffset - CurAttrFixup.InputAttrStartOffset;
1968
1969 DWARFFormValue Val = AttrSpec.getFormValue();
1970 uint64_t AttrSize = Offset;
1971 Val.extractValue(Data, OffsetPtr: &Offset, FormParams: U.getFormParams(), U: &U);
1972 CurAttrFixup.InputAttrEndOffset = InputDIE.getOffset() + Offset;
1973 AttrSize = Offset - AttrSize;
1974
1975 uint64_t FinalAttrSize =
1976 cloneAttribute(Die&: *Die, InputDIE, File, Unit, Val, AttrSpec, AttrSize,
1977 Info&: AttrInfo, IsLittleEndian);
1978 if (FinalAttrSize != 0 && ObjFile.Addresses->needToSaveValidRelocs())
1979 AttributesFixups.push_back(Elt: CurAttrFixup);
1980
1981 OutOffset += FinalAttrSize;
1982 }
1983
1984 uint16_t Tag = InputDIE.getTag();
1985 // Add the DW_AT_APPLE_origin attribute to Compile Unit die if we have
1986 // an install name and the DWARF doesn't have the attribute yet.
1987 const bool NeedsAppleOrigin = (Tag == dwarf::DW_TAG_compile_unit) &&
1988 LibraryInstallName.has_value() &&
1989 !AttrInfo.HasAppleOrigin;
1990 if (NeedsAppleOrigin) {
1991 auto StringEntry = DebugStrPool.getEntry(S: LibraryInstallName.value());
1992 Die->addValue(Alloc&: DIEAlloc, Attribute: dwarf::Attribute(dwarf::DW_AT_APPLE_origin),
1993 Form: dwarf::DW_FORM_strp, Value: DIEInteger(StringEntry.getOffset()));
1994 AttrInfo.Name = StringEntry;
1995 OutOffset += 4;
1996 }
1997
1998 // Look for accelerator entries.
1999 // FIXME: This is slightly wrong. An inline_subroutine without a
2000 // low_pc, but with AT_ranges might be interesting to get into the
2001 // accelerator tables too. For now stick with dsymutil's behavior.
2002 if ((Info.InDebugMap || AttrInfo.HasLowPc || AttrInfo.HasRanges) &&
2003 Tag != dwarf::DW_TAG_compile_unit &&
2004 getDIENames(Die: InputDIE, Info&: AttrInfo, StringPool&: DebugStrPool, File, Unit,
2005 StripTemplate: Tag != dwarf::DW_TAG_inlined_subroutine)) {
2006 if (AttrInfo.MangledName && AttrInfo.MangledName != AttrInfo.Name)
2007 Unit.addNameAccelerator(Die, Name: AttrInfo.MangledName,
2008 SkipPubnamesSection: Tag == dwarf::DW_TAG_inlined_subroutine);
2009 if (AttrInfo.Name) {
2010 if (AttrInfo.NameWithoutTemplate)
2011 Unit.addNameAccelerator(Die, Name: AttrInfo.NameWithoutTemplate,
2012 /* SkipPubSection */ SkipPubnamesSection: true);
2013 Unit.addNameAccelerator(Die, Name: AttrInfo.Name,
2014 SkipPubnamesSection: Tag == dwarf::DW_TAG_inlined_subroutine);
2015 }
2016 if (AttrInfo.Name)
2017 addObjCAccelerator(Unit, Die, Name: AttrInfo.Name, StringPool&: DebugStrPool,
2018 /* SkipPubSection =*/true);
2019
2020 } else if (Tag == dwarf::DW_TAG_namespace) {
2021 if (!AttrInfo.Name)
2022 AttrInfo.Name = DebugStrPool.getEntry(S: "(anonymous namespace)");
2023 Unit.addNamespaceAccelerator(Die, Name: AttrInfo.Name);
2024 } else if (Tag == dwarf::DW_TAG_imported_declaration && AttrInfo.Name) {
2025 Unit.addNamespaceAccelerator(Die, Name: AttrInfo.Name);
2026 } else if (isTypeTag(Tag) && !AttrInfo.IsDeclaration) {
2027 bool Success = getDIENames(Die: InputDIE, Info&: AttrInfo, StringPool&: DebugStrPool, File, Unit);
2028 uint64_t RuntimeLang =
2029 dwarf::toUnsigned(V: InputDIE.find(Attr: dwarf::DW_AT_APPLE_runtime_class))
2030 .value_or(u: 0);
2031 bool ObjCClassIsImplementation =
2032 (RuntimeLang == dwarf::DW_LANG_ObjC ||
2033 RuntimeLang == dwarf::DW_LANG_ObjC_plus_plus) &&
2034 dwarf::toUnsigned(V: InputDIE.find(Attr: dwarf::DW_AT_APPLE_objc_complete_type))
2035 .value_or(u: 0);
2036 if (Success && AttrInfo.Name && !AttrInfo.Name.getString().empty()) {
2037 uint32_t Hash = hashFullyQualifiedName(DIE: InputDIE, U&: Unit, File);
2038 Unit.addTypeAccelerator(Die, Name: AttrInfo.Name, ObjcClassImplementation: ObjCClassIsImplementation,
2039 QualifiedNameHash: Hash);
2040 }
2041
2042 // For Swift, mangled names are put into DW_AT_linkage_name.
2043 if (Success && AttrInfo.MangledName &&
2044 RuntimeLang == dwarf::DW_LANG_Swift &&
2045 !AttrInfo.MangledName.getString().empty() &&
2046 AttrInfo.MangledName != AttrInfo.Name) {
2047 auto Hash = djbHash(Buffer: AttrInfo.MangledName.getString().data());
2048 Unit.addTypeAccelerator(Die, Name: AttrInfo.MangledName,
2049 ObjcClassImplementation: ObjCClassIsImplementation, QualifiedNameHash: Hash);
2050 }
2051 }
2052
2053 // Determine whether there are any children that we want to keep.
2054 bool HasChildren = false;
2055 for (auto Child : InputDIE.children()) {
2056 unsigned Idx = U.getDIEIndex(D: Child);
2057 if (Unit.getInfo(Idx).Keep) {
2058 HasChildren = true;
2059 break;
2060 }
2061 }
2062
2063 if (Unit.getOrigUnit().getVersion() >= 5 && !AttrInfo.AttrStrOffsetBaseSeen &&
2064 Die->getTag() == dwarf::DW_TAG_compile_unit) {
2065 // No DW_AT_str_offsets_base seen, add it to the DIE.
2066 Die->addValue(Alloc&: DIEAlloc, Attribute: dwarf::DW_AT_str_offsets_base,
2067 Form: dwarf::DW_FORM_sec_offset, Value: DIEInteger(8));
2068 OutOffset += 4;
2069 }
2070
2071 DIEAbbrev NewAbbrev = Die->generateAbbrev();
2072 if (HasChildren)
2073 NewAbbrev.setChildrenFlag(dwarf::DW_CHILDREN_yes);
2074 // Assign a permanent abbrev number
2075 Linker.assignAbbrev(Abbrev&: NewAbbrev);
2076 Die->setAbbrevNumber(NewAbbrev.getNumber());
2077
2078 uint64_t AbbrevNumberSize = getULEB128Size(Value: Die->getAbbrevNumber());
2079
2080 // Add the size of the abbreviation number to the output offset.
2081 OutOffset += AbbrevNumberSize;
2082
2083 // Update fixups with the size of the abbreviation number
2084 for (AttributeLinkedOffsetFixup &F : AttributesFixups)
2085 F.LinkedOffsetFixupVal += AbbrevNumberSize;
2086
2087 for (AttributeLinkedOffsetFixup &F : AttributesFixups)
2088 ObjFile.Addresses->updateAndSaveValidRelocs(
2089 IsDWARF5: Unit.getOrigUnit().getVersion() >= 5, OriginalUnitOffset: Unit.getOrigUnit().getOffset(),
2090 LinkedOffset: F.LinkedOffsetFixupVal, StartOffset: F.InputAttrStartOffset, EndOffset: F.InputAttrEndOffset);
2091
2092 if (!HasChildren) {
2093 // Update our size.
2094 Die->setSize(OutOffset - Die->getOffset());
2095 return Die;
2096 }
2097
2098 // Recursively clone children.
2099 for (auto Child : InputDIE.children()) {
2100 if (DIE *Clone = cloneDIE(InputDIE: Child, File, Unit, PCOffset, OutOffset, Flags,
2101 IsLittleEndian)) {
2102 Die->addChild(Child: Clone);
2103 OutOffset = Clone->getOffset() + Clone->getSize();
2104 }
2105 }
2106
2107 // Account for the end of children marker.
2108 OutOffset += sizeof(int8_t);
2109 // Update our size.
2110 Die->setSize(OutOffset - Die->getOffset());
2111 return Die;
2112}
2113
2114/// Patch the input object file relevant debug_ranges or debug_rnglists
2115/// entries and emit them in the output file. Update the relevant attributes
2116/// to point at the new entries.
2117void DWARFLinker::generateUnitRanges(CompileUnit &Unit, const DWARFFile &File,
2118 DebugDieValuePool &AddrPool) const {
2119 if (LLVM_UNLIKELY(Options.Update))
2120 return;
2121
2122 const auto &FunctionRanges = Unit.getFunctionRanges();
2123
2124 // Build set of linked address ranges for unit function ranges.
2125 AddressRanges LinkedFunctionRanges;
2126 for (const AddressRangeValuePair &Range : FunctionRanges)
2127 LinkedFunctionRanges.insert(
2128 Range: {Range.Range.start() + Range.Value, Range.Range.end() + Range.Value});
2129
2130 // Emit LinkedFunctionRanges into .debug_aranges
2131 if (!LinkedFunctionRanges.empty())
2132 TheDwarfEmitter->emitDwarfDebugArangesTable(Unit, LinkedRanges: LinkedFunctionRanges);
2133
2134 RngListAttributesTy AllRngListAttributes = Unit.getRangesAttributes();
2135 std::optional<PatchLocation> UnitRngListAttribute =
2136 Unit.getUnitRangesAttribute();
2137
2138 if (!AllRngListAttributes.empty() || UnitRngListAttribute) {
2139 std::optional<AddressRangeValuePair> CachedRange;
2140 MCSymbol *EndLabel = TheDwarfEmitter->emitDwarfDebugRangeListHeader(Unit);
2141
2142 // Read original address ranges, apply relocation value, emit linked address
2143 // ranges.
2144 for (PatchLocation &AttributePatch : AllRngListAttributes) {
2145 // Get ranges from the source DWARF corresponding to the current
2146 // attribute.
2147 AddressRanges LinkedRanges;
2148 if (Expected<DWARFAddressRangesVector> OriginalRanges =
2149 Unit.getOrigUnit().findRnglistFromOffset(Offset: AttributePatch.get())) {
2150 // Apply relocation adjustment.
2151 for (const auto &Range : *OriginalRanges) {
2152 if (!CachedRange || !CachedRange->Range.contains(Addr: Range.LowPC))
2153 CachedRange = FunctionRanges.getRangeThatContains(Addr: Range.LowPC);
2154
2155 // All range entries should lie in the function range.
2156 if (!CachedRange) {
2157 reportWarning(Warning: "inconsistent range data.", File);
2158 continue;
2159 }
2160
2161 // Store range for emiting.
2162 LinkedRanges.insert(Range: {Range.LowPC + CachedRange->Value,
2163 Range.HighPC + CachedRange->Value});
2164 }
2165 } else {
2166 llvm::consumeError(Err: OriginalRanges.takeError());
2167 reportWarning(Warning: "invalid range list ignored.", File);
2168 }
2169
2170 // Emit linked ranges.
2171 TheDwarfEmitter->emitDwarfDebugRangeListFragment(
2172 Unit, LinkedRanges, Patch: AttributePatch, AddrPool);
2173 }
2174
2175 // Emit ranges for Unit AT_ranges attribute.
2176 if (UnitRngListAttribute.has_value())
2177 TheDwarfEmitter->emitDwarfDebugRangeListFragment(
2178 Unit, LinkedRanges: LinkedFunctionRanges, Patch: *UnitRngListAttribute, AddrPool);
2179
2180 // Emit ranges footer.
2181 TheDwarfEmitter->emitDwarfDebugRangeListFooter(Unit, EndLabel);
2182 }
2183}
2184
2185void DWARFLinker::DIECloner::generateUnitLocations(
2186 CompileUnit &Unit, const DWARFFile &File,
2187 ExpressionHandlerRef ExprHandler) {
2188 if (LLVM_UNLIKELY(Linker.Options.Update))
2189 return;
2190
2191 const LocListAttributesTy &AllLocListAttributes =
2192 Unit.getLocationAttributes();
2193
2194 if (AllLocListAttributes.empty())
2195 return;
2196
2197 // Emit locations list table header.
2198 MCSymbol *EndLabel = Emitter->emitDwarfDebugLocListHeader(Unit);
2199
2200 for (auto &CurLocAttr : AllLocListAttributes) {
2201 // Get location expressions vector corresponding to the current attribute
2202 // from the source DWARF.
2203 Expected<DWARFLocationExpressionsVector> OriginalLocations =
2204 Unit.getOrigUnit().findLoclistFromOffset(Offset: CurLocAttr.get());
2205
2206 if (!OriginalLocations) {
2207 llvm::consumeError(Err: OriginalLocations.takeError());
2208 Linker.reportWarning(Warning: "Invalid location attribute ignored.", File);
2209 continue;
2210 }
2211
2212 DWARFLocationExpressionsVector LinkedLocationExpressions;
2213 for (DWARFLocationExpression &CurExpression : *OriginalLocations) {
2214 DWARFLocationExpression LinkedExpression;
2215
2216 if (CurExpression.Range) {
2217 // Relocate address range.
2218 LinkedExpression.Range = {
2219 CurExpression.Range->LowPC + CurLocAttr.RelocAdjustment,
2220 CurExpression.Range->HighPC + CurLocAttr.RelocAdjustment};
2221 }
2222
2223 // Clone expression.
2224 LinkedExpression.Expr.reserve(N: CurExpression.Expr.size());
2225 ExprHandler(CurExpression.Expr, LinkedExpression.Expr,
2226 CurLocAttr.RelocAdjustment);
2227
2228 LinkedLocationExpressions.push_back(x: LinkedExpression);
2229 }
2230
2231 // Emit locations list table fragment corresponding to the CurLocAttr.
2232 Emitter->emitDwarfDebugLocListFragment(Unit, LinkedLocationExpression: LinkedLocationExpressions,
2233 Patch: CurLocAttr, AddrPool);
2234 }
2235
2236 // Emit locations list table footer.
2237 Emitter->emitDwarfDebugLocListFooter(Unit, EndLabel);
2238}
2239
2240static void patchAddrBase(DIE &Die, DIEInteger Offset) {
2241 for (auto &V : Die.values())
2242 if (V.getAttribute() == dwarf::DW_AT_addr_base) {
2243 V = DIEValue(V.getAttribute(), V.getForm(), Offset);
2244 return;
2245 }
2246
2247 llvm_unreachable("Didn't find a DW_AT_addr_base in cloned DIE!");
2248}
2249
2250void DWARFLinker::DIECloner::emitDebugAddrSection(
2251 CompileUnit &Unit, const uint16_t DwarfVersion) const {
2252
2253 if (LLVM_UNLIKELY(Linker.Options.Update))
2254 return;
2255
2256 if (DwarfVersion < 5)
2257 return;
2258
2259 if (AddrPool.getValues().empty())
2260 return;
2261
2262 MCSymbol *EndLabel = Emitter->emitDwarfDebugAddrsHeader(Unit);
2263 patchAddrBase(Die&: *Unit.getOutputUnitDIE(),
2264 Offset: DIEInteger(Emitter->getDebugAddrSectionSize()));
2265 Emitter->emitDwarfDebugAddrs(Addrs: AddrPool.getValues(),
2266 AddrSize: Unit.getOrigUnit().getAddressByteSize());
2267 Emitter->emitDwarfDebugAddrsFooter(Unit, EndLabel);
2268}
2269
2270/// A helper struct to help keep track of the association between the input and
2271/// output rows during line table rewriting. This is used to patch
2272/// DW_AT_LLVM_stmt_sequence attributes, which reference a particular line table
2273/// row.
2274struct TrackedRow {
2275 DWARFDebugLine::Row Row;
2276 size_t OriginalRowIndex;
2277 bool isStartSeqInOutput;
2278};
2279
2280/// Insert the new line info sequence \p Seq into the current
2281/// set of already linked line info \p Rows.
2282static void insertLineSequence(std::vector<TrackedRow> &Seq,
2283 std::vector<TrackedRow> &Rows) {
2284 if (Seq.empty())
2285 return;
2286
2287 // Mark the first row in Seq to indicate it is the start of a sequence
2288 // in the output line table.
2289 Seq.front().isStartSeqInOutput = true;
2290
2291 if (!Rows.empty() && Rows.back().Row.Address < Seq.front().Row.Address) {
2292 llvm::append_range(C&: Rows, R&: Seq);
2293 Seq.clear();
2294 return;
2295 }
2296
2297 object::SectionedAddress Front = Seq.front().Row.Address;
2298 auto InsertPoint = partition_point(
2299 Range&: Rows, P: [=](const TrackedRow &O) { return O.Row.Address < Front; });
2300
2301 // FIXME: this only removes the unneeded end_sequence if the
2302 // sequences have been inserted in order. Using a global sort like
2303 // described in generateLineTableForUnit() and delaying the end_sequence
2304 // elimination to emitLineTableForUnit() we can get rid of all of them.
2305 if (InsertPoint != Rows.end() && InsertPoint->Row.Address == Front &&
2306 InsertPoint->Row.EndSequence) {
2307 *InsertPoint = Seq.front();
2308 Rows.insert(position: InsertPoint + 1, first: Seq.begin() + 1, last: Seq.end());
2309 } else {
2310 Rows.insert(position: InsertPoint, first: Seq.begin(), last: Seq.end());
2311 }
2312
2313 Seq.clear();
2314}
2315
2316static void patchStmtList(DIE &Die, DIEInteger Offset) {
2317 for (auto &V : Die.values())
2318 if (V.getAttribute() == dwarf::DW_AT_stmt_list) {
2319 V = DIEValue(V.getAttribute(), V.getForm(), Offset);
2320 return;
2321 }
2322
2323 llvm_unreachable("Didn't find DW_AT_stmt_list in cloned DIE!");
2324}
2325
2326void DWARFLinker::DIECloner::rememberUnitForMacroOffset(CompileUnit &Unit) {
2327 DWARFUnit &OrigUnit = Unit.getOrigUnit();
2328 DWARFDie OrigUnitDie = OrigUnit.getUnitDIE();
2329
2330 if (std::optional<uint64_t> MacroAttr =
2331 dwarf::toSectionOffset(V: OrigUnitDie.find(Attr: dwarf::DW_AT_macros))) {
2332 UnitMacroMap.insert(KV: std::make_pair(x&: *MacroAttr, y: &Unit));
2333 return;
2334 }
2335
2336 if (std::optional<uint64_t> MacroAttr =
2337 dwarf::toSectionOffset(V: OrigUnitDie.find(Attr: dwarf::DW_AT_macro_info))) {
2338 UnitMacroMap.insert(KV: std::make_pair(x&: *MacroAttr, y: &Unit));
2339 return;
2340 }
2341}
2342
2343void DWARFLinker::DIECloner::generateLineTableForUnit(CompileUnit &Unit) {
2344 if (LLVM_UNLIKELY(Emitter == nullptr))
2345 return;
2346
2347 // Check whether DW_AT_stmt_list attribute is presented.
2348 DWARFDie CUDie = Unit.getOrigUnit().getUnitDIE();
2349 auto StmtList = dwarf::toSectionOffset(V: CUDie.find(Attr: dwarf::DW_AT_stmt_list));
2350 if (!StmtList)
2351 return;
2352
2353 // Update the cloned DW_AT_stmt_list with the correct debug_line offset.
2354 if (auto *OutputDIE = Unit.getOutputUnitDIE())
2355 patchStmtList(Die&: *OutputDIE, Offset: DIEInteger(Emitter->getLineSectionSize()));
2356
2357 if (const DWARFDebugLine::LineTable *LT =
2358 ObjFile.Dwarf->getLineTableForUnit(U: &Unit.getOrigUnit())) {
2359
2360 DWARFDebugLine::LineTable LineTable;
2361
2362 // Set Line Table header.
2363 LineTable.Prologue = LT->Prologue;
2364
2365 // Set Line Table Rows.
2366 if (Linker.Options.Update) {
2367 LineTable.Rows = LT->Rows;
2368 // If all the line table contains is a DW_LNE_end_sequence, clear the line
2369 // table rows, it will be inserted again in the DWARFStreamer.
2370 if (LineTable.Rows.size() == 1 && LineTable.Rows[0].EndSequence)
2371 LineTable.Rows.clear();
2372
2373 LineTable.Sequences = LT->Sequences;
2374
2375 Emitter->emitLineTableForUnit(LineTable, Unit, DebugStrPool,
2376 DebugLineStrPool);
2377 } else {
2378 // Create TrackedRow objects for all input rows.
2379 std::vector<TrackedRow> InputRows;
2380 InputRows.reserve(n: LT->Rows.size());
2381 for (size_t i = 0; i < LT->Rows.size(); i++)
2382 InputRows.emplace_back(args: TrackedRow{.Row: LT->Rows[i], .OriginalRowIndex: i, .isStartSeqInOutput: false});
2383
2384 // This vector is the output line table (still in TrackedRow form).
2385 std::vector<TrackedRow> OutputRows;
2386 OutputRows.reserve(n: InputRows.size());
2387
2388 // Current sequence of rows being extracted, before being inserted
2389 // in OutputRows.
2390 std::vector<TrackedRow> Seq;
2391 Seq.reserve(n: InputRows.size());
2392
2393 const auto &FunctionRanges = Unit.getFunctionRanges();
2394 std::optional<AddressRangeValuePair> CurrRange;
2395
2396 // FIXME: This logic is meant to generate exactly the same output as
2397 // Darwin's classic dsymutil. There is a nicer way to implement this
2398 // by simply putting all the relocated line info in OutputRows and simply
2399 // sorting OutputRows before passing it to emitLineTableForUnit. This
2400 // should be correct as sequences for a function should stay
2401 // together in the sorted output. There are a few corner cases that
2402 // look suspicious though, and that required to implement the logic
2403 // this way. Revisit that once initial validation is finished.
2404
2405 // Iterate over the object file line info and extract the sequences
2406 // that correspond to linked functions.
2407 for (size_t i = 0; i < InputRows.size(); i++) {
2408 TrackedRow TR = InputRows[i];
2409
2410 // Check whether we stepped out of the range. The range is
2411 // half-open, but consider accepting the end address of the range if
2412 // it is marked as end_sequence in the input (because in that
2413 // case, the relocation offset is accurate and that entry won't
2414 // serve as the start of another function).
2415 if (!CurrRange || !CurrRange->Range.contains(Addr: TR.Row.Address.Address)) {
2416 // We just stepped out of a known range. Insert an end_sequence
2417 // corresponding to the end of the range.
2418 uint64_t StopAddress =
2419 CurrRange ? CurrRange->Range.end() + CurrRange->Value : -1ULL;
2420 CurrRange =
2421 FunctionRanges.getRangeThatContains(Addr: TR.Row.Address.Address);
2422 if (StopAddress != -1ULL && !Seq.empty()) {
2423 // Insert end sequence row with the computed end address, but
2424 // the same line as the previous one.
2425 auto NextLine = Seq.back();
2426 NextLine.Row.Address.Address = StopAddress;
2427 NextLine.Row.EndSequence = 1;
2428 NextLine.Row.PrologueEnd = 0;
2429 NextLine.Row.BasicBlock = 0;
2430 NextLine.Row.EpilogueBegin = 0;
2431 Seq.push_back(x: NextLine);
2432 insertLineSequence(Seq, Rows&: OutputRows);
2433 }
2434
2435 if (!CurrRange)
2436 continue;
2437 }
2438
2439 // Ignore empty sequences.
2440 if (TR.Row.EndSequence && Seq.empty())
2441 continue;
2442
2443 // Relocate row address and add it to the current sequence.
2444 TR.Row.Address.Address += CurrRange->Value;
2445 Seq.push_back(x: TR);
2446
2447 if (TR.Row.EndSequence)
2448 insertLineSequence(Seq, Rows&: OutputRows);
2449 }
2450
2451 // Materialize the tracked rows into final DWARFDebugLine::Row objects.
2452 LineTable.Rows.clear();
2453 LineTable.Rows.reserve(n: OutputRows.size());
2454 for (auto &TR : OutputRows)
2455 LineTable.Rows.push_back(x: TR.Row);
2456
2457 // Use OutputRowOffsets to store the offsets of each line table row in the
2458 // output .debug_line section.
2459 std::vector<uint64_t> OutputRowOffsets;
2460
2461 // The unit might not have any DW_AT_LLVM_stmt_sequence attributes, so use
2462 // hasStmtSeq to skip the patching logic.
2463 bool hasStmtSeq = Unit.getStmtSeqListAttributes().size() > 0;
2464 Emitter->emitLineTableForUnit(LineTable, Unit, DebugStrPool,
2465 DebugLineStrPool,
2466 RowOffsets: hasStmtSeq ? &OutputRowOffsets : nullptr);
2467
2468 if (hasStmtSeq) {
2469 assert(OutputRowOffsets.size() == OutputRows.size() &&
2470 "must have an offset for each row");
2471
2472 // Create a map of stmt sequence offsets to original row indices.
2473 DenseMap<uint64_t, unsigned> SeqOffToOrigRow;
2474 // The DWARF parser's discovery of sequences can be incomplete. To
2475 // ensure all DW_AT_LLVM_stmt_sequence attributes can be patched, we
2476 // build a map from both the parser's results and a manual
2477 // reconstruction.
2478 if (!LT->Rows.empty())
2479 constructSeqOffsettoOrigRowMapping(Unit, LT: *LT, SeqOffToOrigRow);
2480
2481 // Create a map of original row indices to new row indices.
2482 DenseMap<size_t, size_t> OrigRowToNewRow;
2483 for (size_t i = 0; i < OutputRows.size(); ++i)
2484 OrigRowToNewRow[OutputRows[i].OriginalRowIndex] = i;
2485
2486 // Patch DW_AT_LLVM_stmt_sequence attributes in the compile unit DIE
2487 // with the correct offset into the .debug_line section.
2488 for (const auto &StmtSeq : Unit.getStmtSeqListAttributes()) {
2489 uint64_t OrigStmtSeq = StmtSeq.get();
2490 // 1. Get the original row index from the stmt list offset.
2491 auto OrigRowIter = SeqOffToOrigRow.find(Val: OrigStmtSeq);
2492 const uint64_t InvalidOffset =
2493 Unit.getOrigUnit().getFormParams().getDwarfMaxOffset();
2494 // Check whether we have an output sequence for the StmtSeq offset.
2495 // Some sequences are discarded by the DWARFLinker if they are invalid
2496 // (empty).
2497 if (OrigRowIter == SeqOffToOrigRow.end()) {
2498 StmtSeq.set(InvalidOffset);
2499 continue;
2500 }
2501 size_t OrigRowIndex = OrigRowIter->second;
2502
2503 // 2. Get the new row index from the original row index.
2504 auto NewRowIter = OrigRowToNewRow.find(Val: OrigRowIndex);
2505 if (NewRowIter == OrigRowToNewRow.end()) {
2506 // If the original row index is not found in the map, update the
2507 // stmt_sequence attribute to the 'invalid offset' magic value.
2508 StmtSeq.set(InvalidOffset);
2509 continue;
2510 }
2511
2512 // 3. Get the offset of the new row in the output .debug_line section.
2513 assert(NewRowIter->second < OutputRowOffsets.size() &&
2514 "New row index out of bounds");
2515 uint64_t NewStmtSeqOffset = OutputRowOffsets[NewRowIter->second];
2516
2517 // 4. Patch the stmt_list attribute with the new offset.
2518 StmtSeq.set(NewStmtSeqOffset);
2519 }
2520 }
2521 }
2522
2523 } else
2524 Linker.reportWarning(Warning: "Cann't load line table.", File: ObjFile);
2525}
2526
2527void DWARFLinker::emitAcceleratorEntriesForUnit(CompileUnit &Unit) {
2528 for (AccelTableKind AccelTableKind : Options.AccelTables) {
2529 switch (AccelTableKind) {
2530 case AccelTableKind::Apple: {
2531 // Add namespaces.
2532 for (const auto &Namespace : Unit.getNamespaces())
2533 AppleNamespaces.addName(Name: Namespace.Name, Args: Namespace.Die->getOffset() +
2534 Unit.getStartOffset());
2535 // Add names.
2536 for (const auto &Pubname : Unit.getPubnames())
2537 AppleNames.addName(Name: Pubname.Name,
2538 Args: Pubname.Die->getOffset() + Unit.getStartOffset());
2539 // Add types.
2540 for (const auto &Pubtype : Unit.getPubtypes())
2541 AppleTypes.addName(
2542 Name: Pubtype.Name, Args: Pubtype.Die->getOffset() + Unit.getStartOffset(),
2543 Args: Pubtype.Die->getTag(),
2544 Args: Pubtype.ObjcClassImplementation ? dwarf::DW_FLAG_type_implementation
2545 : 0,
2546 Args: Pubtype.QualifiedNameHash);
2547 // Add ObjC names.
2548 for (const auto &ObjC : Unit.getObjC())
2549 AppleObjc.addName(Name: ObjC.Name,
2550 Args: ObjC.Die->getOffset() + Unit.getStartOffset());
2551 } break;
2552 case AccelTableKind::Pub: {
2553 TheDwarfEmitter->emitPubNamesForUnit(Unit);
2554 TheDwarfEmitter->emitPubTypesForUnit(Unit);
2555 } break;
2556 case AccelTableKind::DebugNames: {
2557 for (const auto &Namespace : Unit.getNamespaces())
2558 DebugNames.addName(
2559 Name: Namespace.Name, Args: Namespace.Die->getOffset(),
2560 Args: DWARF5AccelTableData::getDefiningParentDieOffset(Die: *Namespace.Die),
2561 Args: Namespace.Die->getTag(), Args: Unit.getUniqueID(),
2562 Args: Unit.getTag() == dwarf::DW_TAG_type_unit);
2563 for (const auto &Pubname : Unit.getPubnames())
2564 DebugNames.addName(
2565 Name: Pubname.Name, Args: Pubname.Die->getOffset(),
2566 Args: DWARF5AccelTableData::getDefiningParentDieOffset(Die: *Pubname.Die),
2567 Args: Pubname.Die->getTag(), Args: Unit.getUniqueID(),
2568 Args: Unit.getTag() == dwarf::DW_TAG_type_unit);
2569 for (const auto &Pubtype : Unit.getPubtypes())
2570 DebugNames.addName(
2571 Name: Pubtype.Name, Args: Pubtype.Die->getOffset(),
2572 Args: DWARF5AccelTableData::getDefiningParentDieOffset(Die: *Pubtype.Die),
2573 Args: Pubtype.Die->getTag(), Args: Unit.getUniqueID(),
2574 Args: Unit.getTag() == dwarf::DW_TAG_type_unit);
2575 } break;
2576 }
2577 }
2578}
2579
2580/// Read the frame info stored in the object, and emit the
2581/// patched frame descriptions for the resulting file.
2582///
2583/// This is actually pretty easy as the data of the CIEs and FDEs can
2584/// be considered as black boxes and moved as is. The only thing to do
2585/// is to patch the addresses in the headers.
2586void DWARFLinker::patchFrameInfoForObject(LinkContext &Context) {
2587 DWARFContext &OrigDwarf = *Context.File.Dwarf;
2588 unsigned SrcAddrSize = OrigDwarf.getDWARFObj().getAddressSize();
2589
2590 StringRef FrameData = OrigDwarf.getDWARFObj().getFrameSection().Data;
2591 if (FrameData.empty())
2592 return;
2593
2594 RangesTy AllUnitsRanges;
2595 for (std::unique_ptr<CompileUnit> &Unit : Context.CompileUnits) {
2596 for (auto CurRange : Unit->getFunctionRanges())
2597 AllUnitsRanges.insert(Range: CurRange.Range, Value: CurRange.Value);
2598 }
2599
2600 DataExtractor Data(FrameData, OrigDwarf.isLittleEndian(), 0);
2601 uint64_t InputOffset = 0;
2602
2603 // Store the data of the CIEs defined in this object, keyed by their
2604 // offsets.
2605 DenseMap<uint64_t, StringRef> LocalCIES;
2606
2607 while (Data.isValidOffset(offset: InputOffset)) {
2608 uint64_t EntryOffset = InputOffset;
2609 uint32_t InitialLength = Data.getU32(offset_ptr: &InputOffset);
2610 if (InitialLength == 0xFFFFFFFF)
2611 return reportWarning(Warning: "Dwarf64 bits no supported", File: Context.File);
2612
2613 uint32_t CIEId = Data.getU32(offset_ptr: &InputOffset);
2614 if (CIEId == 0xFFFFFFFF) {
2615 // This is a CIE, store it.
2616 StringRef CIEData = FrameData.substr(Start: EntryOffset, N: InitialLength + 4);
2617 LocalCIES[EntryOffset] = CIEData;
2618 // The -4 is to account for the CIEId we just read.
2619 InputOffset += InitialLength - 4;
2620 continue;
2621 }
2622
2623 uint64_t Loc = Data.getUnsigned(offset_ptr: &InputOffset, byte_size: SrcAddrSize);
2624
2625 // Some compilers seem to emit frame info that doesn't start at
2626 // the function entry point, thus we can't just lookup the address
2627 // in the debug map. Use the AddressInfo's range map to see if the FDE
2628 // describes something that we can relocate.
2629 std::optional<AddressRangeValuePair> Range =
2630 AllUnitsRanges.getRangeThatContains(Addr: Loc);
2631 if (!Range) {
2632 // The +4 is to account for the size of the InitialLength field itself.
2633 InputOffset = EntryOffset + InitialLength + 4;
2634 continue;
2635 }
2636
2637 // This is an FDE, and we have a mapping.
2638 // Have we already emitted a corresponding CIE?
2639 StringRef CIEData = LocalCIES[CIEId];
2640 if (CIEData.empty())
2641 return reportWarning(Warning: "Inconsistent debug_frame content. Dropping.",
2642 File: Context.File);
2643
2644 // Look if we already emitted a CIE that corresponds to the
2645 // referenced one (the CIE data is the key of that lookup).
2646 auto IteratorInserted = EmittedCIEs.insert(
2647 KV: std::make_pair(x&: CIEData, y: TheDwarfEmitter->getFrameSectionSize()));
2648 // If there is no CIE yet for this ID, emit it.
2649 if (IteratorInserted.second) {
2650 LastCIEOffset = TheDwarfEmitter->getFrameSectionSize();
2651 IteratorInserted.first->getValue() = LastCIEOffset;
2652 TheDwarfEmitter->emitCIE(CIEBytes: CIEData);
2653 }
2654
2655 // Emit the FDE with updated address and CIE pointer.
2656 // (4 + AddrSize) is the size of the CIEId + initial_location
2657 // fields that will get reconstructed by emitFDE().
2658 unsigned FDERemainingBytes = InitialLength - (4 + SrcAddrSize);
2659 TheDwarfEmitter->emitFDE(CIEOffset: IteratorInserted.first->getValue(), AddreSize: SrcAddrSize,
2660 Address: Loc + Range->Value,
2661 Bytes: FrameData.substr(Start: InputOffset, N: FDERemainingBytes));
2662 InputOffset += FDERemainingBytes;
2663 }
2664}
2665
2666uint32_t DWARFLinker::DIECloner::hashFullyQualifiedName(DWARFDie DIE,
2667 CompileUnit &U,
2668 const DWARFFile &File,
2669 int ChildRecurseDepth) {
2670 const char *Name = nullptr;
2671 DWARFUnit *OrigUnit = &U.getOrigUnit();
2672 CompileUnit *CU = &U;
2673 std::optional<DWARFFormValue> Ref;
2674
2675 while (true) {
2676 if (const char *CurrentName = DIE.getName(Kind: DINameKind::ShortName))
2677 Name = CurrentName;
2678
2679 if (!(Ref = DIE.find(Attr: dwarf::DW_AT_specification)) &&
2680 !(Ref = DIE.find(Attr: dwarf::DW_AT_abstract_origin)))
2681 break;
2682
2683 if (!Ref->isFormClass(FC: DWARFFormValue::FC_Reference))
2684 break;
2685
2686 CompileUnit *RefCU;
2687 if (auto RefDIE =
2688 Linker.resolveDIEReference(File, Units: CompileUnits, RefValue: *Ref, DIE, RefCU)) {
2689 CU = RefCU;
2690 OrigUnit = &RefCU->getOrigUnit();
2691 DIE = RefDIE;
2692 }
2693 }
2694
2695 unsigned Idx = OrigUnit->getDIEIndex(D: DIE);
2696 if (!Name && DIE.getTag() == dwarf::DW_TAG_namespace)
2697 Name = "(anonymous namespace)";
2698
2699 if (CU->getInfo(Idx).ParentIdx == 0 ||
2700 // FIXME: dsymutil-classic compatibility. Ignore modules.
2701 CU->getOrigUnit().getDIEAtIndex(Index: CU->getInfo(Idx).ParentIdx).getTag() ==
2702 dwarf::DW_TAG_module)
2703 return djbHash(Buffer: Name ? Name : "", H: djbHash(Buffer: ChildRecurseDepth ? "" : "::"));
2704
2705 DWARFDie Die = OrigUnit->getDIEAtIndex(Index: CU->getInfo(Idx).ParentIdx);
2706 return djbHash(
2707 Buffer: (Name ? Name : ""),
2708 H: djbHash(Buffer: (Name ? "::" : ""),
2709 H: hashFullyQualifiedName(DIE: Die, U&: *CU, File, ChildRecurseDepth: ++ChildRecurseDepth)));
2710}
2711
2712static uint64_t getDwoId(const DWARFDie &CUDie) {
2713 auto DwoId = dwarf::toUnsigned(
2714 V: CUDie.find(Attrs: {dwarf::DW_AT_dwo_id, dwarf::DW_AT_GNU_dwo_id}));
2715 if (DwoId)
2716 return *DwoId;
2717 return 0;
2718}
2719
2720static std::string
2721remapPath(StringRef Path,
2722 const DWARFLinkerBase::ObjectPrefixMapTy &ObjectPrefixMap) {
2723 if (ObjectPrefixMap.empty())
2724 return Path.str();
2725
2726 SmallString<256> p = Path;
2727 for (const auto &Entry : ObjectPrefixMap)
2728 if (llvm::sys::path::replace_path_prefix(Path&: p, OldPrefix: Entry.first, NewPrefix: Entry.second))
2729 break;
2730 return p.str().str();
2731}
2732
2733static std::string
2734getPCMFile(const DWARFDie &CUDie,
2735 const DWARFLinkerBase::ObjectPrefixMapTy *ObjectPrefixMap) {
2736 std::string PCMFile = dwarf::toString(
2737 V: CUDie.find(Attrs: {dwarf::DW_AT_dwo_name, dwarf::DW_AT_GNU_dwo_name}), Default: "");
2738
2739 if (PCMFile.empty())
2740 return PCMFile;
2741
2742 if (ObjectPrefixMap)
2743 PCMFile = remapPath(Path: PCMFile, ObjectPrefixMap: *ObjectPrefixMap);
2744
2745 return PCMFile;
2746}
2747
2748std::pair<bool, bool> DWARFLinker::isClangModuleRef(const DWARFDie &CUDie,
2749 std::string &PCMFile,
2750 LinkContext &Context,
2751 unsigned Indent,
2752 bool Quiet) {
2753 if (PCMFile.empty())
2754 return std::make_pair(x: false, y: false);
2755
2756 // Clang module DWARF skeleton CUs abuse this for the path to the module.
2757 uint64_t DwoId = getDwoId(CUDie);
2758
2759 std::string Name = dwarf::toString(V: CUDie.find(Attr: dwarf::DW_AT_name), Default: "");
2760 if (Name.empty()) {
2761 if (!Quiet)
2762 reportWarning(Warning: "Anonymous module skeleton CU for " + PCMFile,
2763 File: Context.File);
2764 return std::make_pair(x: true, y: true);
2765 }
2766
2767 if (!Quiet && Options.Verbose) {
2768 outs().indent(NumSpaces: Indent);
2769 outs() << "Found clang module reference " << PCMFile;
2770 }
2771
2772 auto Cached = ClangModules.find(Key: PCMFile);
2773 if (Cached != ClangModules.end()) {
2774 // FIXME: Until PR27449 (https://llvm.org/bugs/show_bug.cgi?id=27449) is
2775 // fixed in clang, only warn about DWO_id mismatches in verbose mode.
2776 // ASTFileSignatures will change randomly when a module is rebuilt.
2777 if (!Quiet && Options.Verbose && (Cached->second != DwoId))
2778 reportWarning(Warning: Twine("hash mismatch: this object file was built against a "
2779 "different version of the module ") +
2780 PCMFile,
2781 File: Context.File);
2782 if (!Quiet && Options.Verbose)
2783 outs() << " [cached].\n";
2784 return std::make_pair(x: true, y: true);
2785 }
2786
2787 return std::make_pair(x: true, y: false);
2788}
2789
2790bool DWARFLinker::registerModuleReference(const DWARFDie &CUDie,
2791 LinkContext &Context,
2792 ObjFileLoaderTy Loader,
2793 CompileUnitHandlerTy OnCUDieLoaded,
2794 unsigned Indent) {
2795 std::string PCMFile = getPCMFile(CUDie, ObjectPrefixMap: Options.ObjectPrefixMap);
2796 std::pair<bool, bool> IsClangModuleRef =
2797 isClangModuleRef(CUDie, PCMFile, Context, Indent, Quiet: false);
2798
2799 if (!IsClangModuleRef.first)
2800 return false;
2801
2802 if (IsClangModuleRef.second)
2803 return true;
2804
2805 if (Options.Verbose)
2806 outs() << " ...\n";
2807
2808 // Cyclic dependencies are disallowed by Clang, but we still
2809 // shouldn't run into an infinite loop, so mark it as processed now.
2810 ClangModules.insert(KV: {PCMFile, getDwoId(CUDie)});
2811
2812 if (Error E = loadClangModule(Loader, CUDie, PCMFile, Context, OnCUDieLoaded,
2813 Indent: Indent + 2)) {
2814 consumeError(Err: std::move(E));
2815 return false;
2816 }
2817 return true;
2818}
2819
2820Error DWARFLinker::loadClangModule(
2821 ObjFileLoaderTy Loader, const DWARFDie &CUDie, const std::string &PCMFile,
2822 LinkContext &Context, CompileUnitHandlerTy OnCUDieLoaded, unsigned Indent) {
2823
2824 uint64_t DwoId = getDwoId(CUDie);
2825 std::string ModuleName = dwarf::toString(V: CUDie.find(Attr: dwarf::DW_AT_name), Default: "");
2826
2827 /// Using a SmallString<0> because loadClangModule() is recursive.
2828 SmallString<0> Path(Options.PrependPath);
2829 if (sys::path::is_relative(path: PCMFile))
2830 resolveRelativeObjectPath(Buf&: Path, CU: CUDie);
2831 sys::path::append(path&: Path, a: PCMFile);
2832 // Don't use the cached binary holder because we have no thread-safety
2833 // guarantee and the lifetime is limited.
2834
2835 if (Loader == nullptr) {
2836 reportError(Warning: "Could not load clang module: loader is not specified.\n",
2837 File: Context.File);
2838 return Error::success();
2839 }
2840
2841 auto ErrOrObj = Loader(Context.File.FileName, Path);
2842 if (!ErrOrObj)
2843 return Error::success();
2844
2845 std::unique_ptr<CompileUnit> Unit;
2846 for (const auto &CU : ErrOrObj->Dwarf->compile_units()) {
2847 OnCUDieLoaded(*CU);
2848 // Recursively get all modules imported by this one.
2849 auto ChildCUDie = CU->getUnitDIE();
2850 if (!ChildCUDie)
2851 continue;
2852 if (!registerModuleReference(CUDie: ChildCUDie, Context, Loader, OnCUDieLoaded,
2853 Indent)) {
2854 if (Unit) {
2855 std::string Err =
2856 (PCMFile +
2857 ": Clang modules are expected to have exactly 1 compile unit.\n");
2858 reportError(Warning: Err, File: Context.File);
2859 return make_error<StringError>(Args&: Err, Args: inconvertibleErrorCode());
2860 }
2861 // FIXME: Until PR27449 (https://llvm.org/bugs/show_bug.cgi?id=27449) is
2862 // fixed in clang, only warn about DWO_id mismatches in verbose mode.
2863 // ASTFileSignatures will change randomly when a module is rebuilt.
2864 uint64_t PCMDwoId = getDwoId(CUDie: ChildCUDie);
2865 if (PCMDwoId != DwoId) {
2866 if (Options.Verbose)
2867 reportWarning(
2868 Warning: Twine("hash mismatch: this object file was built against a "
2869 "different version of the module ") +
2870 PCMFile,
2871 File: Context.File);
2872 // Update the cache entry with the DwoId of the module loaded from disk.
2873 ClangModules[PCMFile] = PCMDwoId;
2874 }
2875
2876 // Add this module.
2877 Unit = std::make_unique<CompileUnit>(args&: *CU, args: UniqueUnitID++, args: !Options.NoODR,
2878 args&: ModuleName);
2879 }
2880 }
2881
2882 if (Unit)
2883 Context.ModuleUnits.emplace_back(args: RefModuleUnit{*ErrOrObj, std::move(Unit)});
2884
2885 return Error::success();
2886}
2887
2888uint64_t DWARFLinker::DIECloner::cloneAllCompileUnits(
2889 DWARFContext &DwarfContext, const DWARFFile &File, bool IsLittleEndian) {
2890 uint64_t OutputDebugInfoSize =
2891 (Emitter == nullptr) ? 0 : Emitter->getDebugInfoSectionSize();
2892 const uint64_t StartOutputDebugInfoSize = OutputDebugInfoSize;
2893
2894 for (auto &CurrentUnit : CompileUnits) {
2895 const uint16_t DwarfVersion = CurrentUnit->getOrigUnit().getVersion();
2896 const uint32_t UnitHeaderSize = DwarfVersion >= 5 ? 12 : 11;
2897 auto InputDIE = CurrentUnit->getOrigUnit().getUnitDIE();
2898 CurrentUnit->setStartOffset(OutputDebugInfoSize);
2899 if (!InputDIE) {
2900 OutputDebugInfoSize = CurrentUnit->computeNextUnitOffset(DwarfVersion);
2901 continue;
2902 }
2903 if (CurrentUnit->getInfo(Idx: 0).Keep) {
2904 // Clone the InputDIE into your Unit DIE in our compile unit since it
2905 // already has a DIE inside of it.
2906 CurrentUnit->createOutputDIE();
2907 rememberUnitForMacroOffset(Unit&: *CurrentUnit);
2908 cloneDIE(InputDIE, File, Unit&: *CurrentUnit, PCOffset: 0 /* PC offset */, OutOffset: UnitHeaderSize,
2909 Flags: 0, IsLittleEndian, Die: CurrentUnit->getOutputUnitDIE());
2910 }
2911
2912 OutputDebugInfoSize = CurrentUnit->computeNextUnitOffset(DwarfVersion);
2913
2914 if (Emitter != nullptr) {
2915
2916 generateLineTableForUnit(Unit&: *CurrentUnit);
2917
2918 Linker.emitAcceleratorEntriesForUnit(Unit&: *CurrentUnit);
2919
2920 if (LLVM_UNLIKELY(Linker.Options.Update))
2921 continue;
2922
2923 Linker.generateUnitRanges(Unit&: *CurrentUnit, File, AddrPool);
2924
2925 auto ProcessExpr = [&](SmallVectorImpl<uint8_t> &SrcBytes,
2926 SmallVectorImpl<uint8_t> &OutBytes,
2927 int64_t RelocAdjustment) {
2928 DWARFUnit &OrigUnit = CurrentUnit->getOrigUnit();
2929 DataExtractor Data(SrcBytes, IsLittleEndian,
2930 OrigUnit.getAddressByteSize());
2931 cloneExpression(Data,
2932 Expression: DWARFExpression(Data, OrigUnit.getAddressByteSize(),
2933 OrigUnit.getFormParams().Format),
2934 File, Unit&: *CurrentUnit, OutputBuffer&: OutBytes, AddrRelocAdjustment: RelocAdjustment,
2935 IsLittleEndian);
2936 };
2937 generateUnitLocations(Unit&: *CurrentUnit, File, ExprHandler: ProcessExpr);
2938 emitDebugAddrSection(Unit&: *CurrentUnit, DwarfVersion);
2939 }
2940 AddrPool.clear();
2941 }
2942
2943 if (Emitter != nullptr) {
2944 assert(Emitter);
2945 // Emit macro tables.
2946 Emitter->emitMacroTables(Context: File.Dwarf.get(), UnitMacroMap, StringPool&: DebugStrPool);
2947
2948 // Emit all the compile unit's debug information.
2949 for (auto &CurrentUnit : CompileUnits) {
2950 CurrentUnit->fixupForwardReferences();
2951
2952 if (!CurrentUnit->getOutputUnitDIE())
2953 continue;
2954
2955 unsigned DwarfVersion = CurrentUnit->getOrigUnit().getVersion();
2956
2957 assert(Emitter->getDebugInfoSectionSize() ==
2958 CurrentUnit->getStartOffset());
2959 Emitter->emitCompileUnitHeader(Unit&: *CurrentUnit, DwarfVersion);
2960 Emitter->emitDIE(Die&: *CurrentUnit->getOutputUnitDIE());
2961 assert(Emitter->getDebugInfoSectionSize() ==
2962 CurrentUnit->computeNextUnitOffset(DwarfVersion));
2963 }
2964 }
2965
2966 return OutputDebugInfoSize - StartOutputDebugInfoSize;
2967}
2968
2969void DWARFLinker::copyInvariantDebugSection(DWARFContext &Dwarf) {
2970 TheDwarfEmitter->emitSectionContents(SecData: Dwarf.getDWARFObj().getLocSection().Data,
2971 SecKind: DebugSectionKind::DebugLoc);
2972 TheDwarfEmitter->emitSectionContents(
2973 SecData: Dwarf.getDWARFObj().getRangesSection().Data,
2974 SecKind: DebugSectionKind::DebugRange);
2975 TheDwarfEmitter->emitSectionContents(
2976 SecData: Dwarf.getDWARFObj().getFrameSection().Data, SecKind: DebugSectionKind::DebugFrame);
2977 TheDwarfEmitter->emitSectionContents(SecData: Dwarf.getDWARFObj().getArangesSection(),
2978 SecKind: DebugSectionKind::DebugARanges);
2979 TheDwarfEmitter->emitSectionContents(
2980 SecData: Dwarf.getDWARFObj().getAddrSection().Data, SecKind: DebugSectionKind::DebugAddr);
2981 TheDwarfEmitter->emitSectionContents(
2982 SecData: Dwarf.getDWARFObj().getRnglistsSection().Data,
2983 SecKind: DebugSectionKind::DebugRngLists);
2984 TheDwarfEmitter->emitSectionContents(
2985 SecData: Dwarf.getDWARFObj().getLoclistsSection().Data,
2986 SecKind: DebugSectionKind::DebugLocLists);
2987}
2988
2989void DWARFLinker::addObjectFile(DWARFFile &File, ObjFileLoaderTy Loader,
2990 CompileUnitHandlerTy OnCUDieLoaded) {
2991 ObjectContexts.emplace_back(args: LinkContext(File));
2992
2993 if (ObjectContexts.back().File.Dwarf) {
2994 for (const std::unique_ptr<DWARFUnit> &CU :
2995 ObjectContexts.back().File.Dwarf->compile_units()) {
2996 DWARFDie CUDie = CU->getUnitDIE();
2997
2998 if (!CUDie)
2999 continue;
3000
3001 OnCUDieLoaded(*CU);
3002
3003 if (!LLVM_UNLIKELY(Options.Update))
3004 registerModuleReference(CUDie, Context&: ObjectContexts.back(), Loader,
3005 OnCUDieLoaded);
3006 }
3007 }
3008}
3009
3010Error DWARFLinker::link() {
3011 assert((Options.TargetDWARFVersion != 0) &&
3012 "TargetDWARFVersion should be set");
3013
3014 // First populate the data structure we need for each iteration of the
3015 // parallel loop.
3016 unsigned NumObjects = ObjectContexts.size();
3017
3018 // This Dwarf string pool which is used for emission. It must be used
3019 // serially as the order of calling getStringOffset matters for
3020 // reproducibility.
3021 OffsetsStringPool DebugStrPool(true);
3022 OffsetsStringPool DebugLineStrPool(false);
3023 DebugDieValuePool StringOffsetPool;
3024
3025 // ODR Contexts for the optimize.
3026 DeclContextTree ODRContexts;
3027
3028 for (LinkContext &OptContext : ObjectContexts) {
3029 if (Options.Verbose)
3030 outs() << "DEBUG MAP OBJECT: " << OptContext.File.FileName << "\n";
3031
3032 if (!OptContext.File.Dwarf)
3033 continue;
3034
3035 if (Options.VerifyInputDWARF)
3036 verifyInput(File: OptContext.File);
3037
3038 // Look for relocations that correspond to address map entries.
3039
3040 // there was findvalidrelocations previously ... probably we need to gather
3041 // info here
3042 if (LLVM_LIKELY(!Options.Update) &&
3043 !OptContext.File.Addresses->hasValidRelocs()) {
3044 if (Options.Verbose)
3045 outs() << "No valid relocations found. Skipping.\n";
3046
3047 // Set "Skip" flag as a signal to other loops that we should not
3048 // process this iteration.
3049 OptContext.Skip = true;
3050 continue;
3051 }
3052
3053 // Setup access to the debug info.
3054 if (!OptContext.File.Dwarf)
3055 continue;
3056
3057 // Check whether type units are presented.
3058 if (!OptContext.File.Dwarf->types_section_units().empty()) {
3059 reportWarning(Warning: "type units are not currently supported: file will "
3060 "be skipped",
3061 File: OptContext.File);
3062 OptContext.Skip = true;
3063 continue;
3064 }
3065
3066 // Clone all the clang modules with requires extracting the DIE units. We
3067 // don't need the full debug info until the Analyze phase.
3068 OptContext.CompileUnits.reserve(
3069 n: OptContext.File.Dwarf->getNumCompileUnits());
3070 for (const auto &CU : OptContext.File.Dwarf->compile_units()) {
3071 auto CUDie = CU->getUnitDIE(/*ExtractUnitDIEOnly=*/true);
3072 if (Options.Verbose) {
3073 outs() << "Input compilation unit:";
3074 DIDumpOptions DumpOpts;
3075 DumpOpts.ChildRecurseDepth = 0;
3076 DumpOpts.Verbose = Options.Verbose;
3077 CUDie.dump(OS&: outs(), indent: 0, DumpOpts);
3078 }
3079 }
3080
3081 for (auto &CU : OptContext.ModuleUnits) {
3082 if (Error Err = cloneModuleUnit(Context&: OptContext, Unit&: CU, ODRContexts, DebugStrPool,
3083 DebugLineStrPool, StringOffsetPool))
3084 reportWarning(Warning: toString(E: std::move(Err)), File: CU.File);
3085 }
3086 }
3087
3088 // At this point we know how much data we have emitted. We use this value to
3089 // compare canonical DIE offsets in analyzeContextInfo to see if a definition
3090 // is already emitted, without being affected by canonical die offsets set
3091 // later. This prevents undeterminism when analyze and clone execute
3092 // concurrently, as clone set the canonical DIE offset and analyze reads it.
3093 const uint64_t ModulesEndOffset =
3094 (TheDwarfEmitter == nullptr) ? 0
3095 : TheDwarfEmitter->getDebugInfoSectionSize();
3096
3097 // These variables manage the list of processed object files.
3098 // The mutex and condition variable are to ensure that this is thread safe.
3099 std::mutex ProcessedFilesMutex;
3100 std::condition_variable ProcessedFilesConditionVariable;
3101 BitVector ProcessedFiles(NumObjects, false);
3102
3103 // Analyzing the context info is particularly expensive so it is executed in
3104 // parallel with emitting the previous compile unit.
3105 auto AnalyzeLambda = [&](size_t I) {
3106 auto &Context = ObjectContexts[I];
3107
3108 if (Context.Skip || !Context.File.Dwarf)
3109 return;
3110
3111 for (const auto &CU : Context.File.Dwarf->compile_units()) {
3112 // Previously we only extracted the unit DIEs. We need the full debug info
3113 // now.
3114 auto CUDie = CU->getUnitDIE(/*ExtractUnitDIEOnly=*/false);
3115 std::string PCMFile = getPCMFile(CUDie, ObjectPrefixMap: Options.ObjectPrefixMap);
3116
3117 if (!CUDie || LLVM_UNLIKELY(Options.Update) ||
3118 !isClangModuleRef(CUDie, PCMFile, Context, Indent: 0, Quiet: true).first) {
3119 Context.CompileUnits.push_back(x: std::make_unique<CompileUnit>(
3120 args&: *CU, args: UniqueUnitID++, args: !Options.NoODR && !Options.Update, args: ""));
3121 }
3122 }
3123
3124 // Now build the DIE parent links that we will use during the next phase.
3125 for (auto &CurrentUnit : Context.CompileUnits) {
3126 auto CUDie = CurrentUnit->getOrigUnit().getUnitDIE();
3127 if (!CUDie)
3128 continue;
3129 analyzeContextInfo(DIE: CurrentUnit->getOrigUnit().getUnitDIE(), ParentIdx: 0,
3130 CU&: *CurrentUnit, CurrentDeclContext: &ODRContexts.getRoot(), Contexts&: ODRContexts,
3131 ModulesEndOffset, ParseableSwiftInterfaces: Options.ParseableSwiftInterfaces,
3132 ReportWarning: [&](const Twine &Warning, const DWARFDie &DIE) {
3133 reportWarning(Warning, File: Context.File, DIE: &DIE);
3134 });
3135 }
3136 };
3137
3138 // For each object file map how many bytes were emitted.
3139 StringMap<DebugInfoSize> SizeByObject;
3140
3141 // And then the remaining work in serial again.
3142 // Note, although this loop runs in serial, it can run in parallel with
3143 // the analyzeContextInfo loop so long as we process files with indices >=
3144 // than those processed by analyzeContextInfo.
3145 auto CloneLambda = [&](size_t I) {
3146 auto &OptContext = ObjectContexts[I];
3147 if (OptContext.Skip || !OptContext.File.Dwarf)
3148 return;
3149
3150 // Then mark all the DIEs that need to be present in the generated output
3151 // and collect some information about them.
3152 // Note that this loop can not be merged with the previous one because
3153 // cross-cu references require the ParentIdx to be setup for every CU in
3154 // the object file before calling this.
3155 if (LLVM_UNLIKELY(Options.Update)) {
3156 for (auto &CurrentUnit : OptContext.CompileUnits)
3157 CurrentUnit->markEverythingAsKept();
3158 copyInvariantDebugSection(Dwarf&: *OptContext.File.Dwarf);
3159 } else {
3160 for (auto &CurrentUnit : OptContext.CompileUnits) {
3161 lookForDIEsToKeep(AddressesMap&: *OptContext.File.Addresses, Units: OptContext.CompileUnits,
3162 Die: CurrentUnit->getOrigUnit().getUnitDIE(),
3163 File: OptContext.File, Cu&: *CurrentUnit, Flags: 0);
3164#ifndef NDEBUG
3165 verifyKeepChain(*CurrentUnit);
3166#endif
3167 }
3168 }
3169
3170 // The calls to applyValidRelocs inside cloneDIE will walk the reloc
3171 // array again (in the same way findValidRelocsInDebugInfo() did). We
3172 // need to reset the NextValidReloc index to the beginning.
3173 if (OptContext.File.Addresses->hasValidRelocs() ||
3174 LLVM_UNLIKELY(Options.Update)) {
3175 SizeByObject[OptContext.File.FileName].Input =
3176 getDebugInfoSize(Dwarf&: *OptContext.File.Dwarf);
3177 SizeByObject[OptContext.File.FileName].Output =
3178 DIECloner(*this, TheDwarfEmitter, OptContext.File, DIEAlloc,
3179 OptContext.CompileUnits, Options.Update, DebugStrPool,
3180 DebugLineStrPool, StringOffsetPool)
3181 .cloneAllCompileUnits(DwarfContext&: *OptContext.File.Dwarf, File: OptContext.File,
3182 IsLittleEndian: OptContext.File.Dwarf->isLittleEndian());
3183 }
3184 if ((TheDwarfEmitter != nullptr) && !OptContext.CompileUnits.empty() &&
3185 LLVM_LIKELY(!Options.Update))
3186 patchFrameInfoForObject(Context&: OptContext);
3187
3188 // Clean-up before starting working on the next object.
3189 cleanupAuxiliarryData(Context&: OptContext);
3190 };
3191
3192 auto EmitLambda = [&]() {
3193 // Emit everything that's global.
3194 if (TheDwarfEmitter != nullptr) {
3195 TheDwarfEmitter->emitAbbrevs(Abbrevs: Abbreviations, DwarfVersion: Options.TargetDWARFVersion);
3196 TheDwarfEmitter->emitStrings(Pool: DebugStrPool);
3197 TheDwarfEmitter->emitStringOffsets(StringOffsets: StringOffsetPool.getValues(),
3198 TargetDWARFVersion: Options.TargetDWARFVersion);
3199 TheDwarfEmitter->emitLineStrings(Pool: DebugLineStrPool);
3200 for (AccelTableKind TableKind : Options.AccelTables) {
3201 switch (TableKind) {
3202 case AccelTableKind::Apple:
3203 TheDwarfEmitter->emitAppleNamespaces(Table&: AppleNamespaces);
3204 TheDwarfEmitter->emitAppleNames(Table&: AppleNames);
3205 TheDwarfEmitter->emitAppleTypes(Table&: AppleTypes);
3206 TheDwarfEmitter->emitAppleObjc(Table&: AppleObjc);
3207 break;
3208 case AccelTableKind::Pub:
3209 // Already emitted by emitAcceleratorEntriesForUnit.
3210 // Already emitted by emitAcceleratorEntriesForUnit.
3211 break;
3212 case AccelTableKind::DebugNames:
3213 TheDwarfEmitter->emitDebugNames(Table&: DebugNames);
3214 break;
3215 }
3216 }
3217 }
3218 };
3219
3220 auto AnalyzeAll = [&]() {
3221 for (unsigned I = 0, E = NumObjects; I != E; ++I) {
3222 AnalyzeLambda(I);
3223
3224 std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
3225 ProcessedFiles.set(I);
3226 ProcessedFilesConditionVariable.notify_one();
3227 }
3228 };
3229
3230 auto CloneAll = [&]() {
3231 for (unsigned I = 0, E = NumObjects; I != E; ++I) {
3232 {
3233 std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
3234 if (!ProcessedFiles[I]) {
3235 ProcessedFilesConditionVariable.wait(
3236 lock&: LockGuard, p: [&]() { return ProcessedFiles[I]; });
3237 }
3238 }
3239
3240 CloneLambda(I);
3241 }
3242 EmitLambda();
3243 };
3244
3245 // To limit memory usage in the single threaded case, analyze and clone are
3246 // run sequentially so the OptContext is freed after processing each object
3247 // in endDebugObject.
3248 if (Options.Threads == 1) {
3249 for (unsigned I = 0, E = NumObjects; I != E; ++I) {
3250 AnalyzeLambda(I);
3251 CloneLambda(I);
3252 }
3253 EmitLambda();
3254 } else {
3255 DefaultThreadPool Pool(hardware_concurrency(ThreadCount: 2));
3256 Pool.async(F&: AnalyzeAll);
3257 Pool.async(F&: CloneAll);
3258 Pool.wait();
3259 }
3260
3261 if (Options.Statistics) {
3262 // Create a vector sorted in descending order by output size.
3263 std::vector<std::pair<StringRef, DebugInfoSize>> Sorted;
3264 for (auto &E : SizeByObject)
3265 Sorted.emplace_back(args: E.first(), args&: E.second);
3266 llvm::sort(C&: Sorted, Comp: [](auto &LHS, auto &RHS) {
3267 return LHS.second.Output > RHS.second.Output;
3268 });
3269
3270 auto ComputePercentange = [](int64_t Input, int64_t Output) -> float {
3271 const float Difference = Output - Input;
3272 const float Sum = Input + Output;
3273 if (Sum == 0)
3274 return 0;
3275 return (Difference / (Sum / 2));
3276 };
3277
3278 int64_t InputTotal = 0;
3279 int64_t OutputTotal = 0;
3280 const char *FormatStr = "{0,-45} {1,10}b {2,10}b {3,8:P}\n";
3281
3282 // Print header.
3283 outs() << ".debug_info section size (in bytes)\n";
3284 outs() << "----------------------------------------------------------------"
3285 "---------------\n";
3286 outs() << "Filename Object "
3287 " dSYM Change\n";
3288 outs() << "----------------------------------------------------------------"
3289 "---------------\n";
3290
3291 // Print body.
3292 for (auto &E : Sorted) {
3293 InputTotal += E.second.Input;
3294 OutputTotal += E.second.Output;
3295 llvm::outs() << formatv(
3296 Fmt: FormatStr, Vals: sys::path::filename(path: E.first).take_back(N: 45), Vals&: E.second.Input,
3297 Vals&: E.second.Output, Vals: ComputePercentange(E.second.Input, E.second.Output));
3298 }
3299 // Print total and footer.
3300 outs() << "----------------------------------------------------------------"
3301 "---------------\n";
3302 llvm::outs() << formatv(Fmt: FormatStr, Vals: "Total", Vals&: InputTotal, Vals&: OutputTotal,
3303 Vals: ComputePercentange(InputTotal, OutputTotal));
3304 outs() << "----------------------------------------------------------------"
3305 "---------------\n\n";
3306 }
3307
3308 return Error::success();
3309}
3310
3311Error DWARFLinker::cloneModuleUnit(LinkContext &Context, RefModuleUnit &Unit,
3312 DeclContextTree &ODRContexts,
3313 OffsetsStringPool &DebugStrPool,
3314 OffsetsStringPool &DebugLineStrPool,
3315 DebugDieValuePool &StringOffsetPool,
3316 unsigned Indent) {
3317 assert(Unit.Unit.get() != nullptr);
3318
3319 if (!Unit.Unit->getOrigUnit().getUnitDIE().hasChildren())
3320 return Error::success();
3321
3322 if (Options.Verbose) {
3323 outs().indent(NumSpaces: Indent);
3324 outs() << "cloning .debug_info from " << Unit.File.FileName << "\n";
3325 }
3326
3327 // Analyze context for the module.
3328 analyzeContextInfo(DIE: Unit.Unit->getOrigUnit().getUnitDIE(), ParentIdx: 0, CU&: *(Unit.Unit),
3329 CurrentDeclContext: &ODRContexts.getRoot(), Contexts&: ODRContexts, ModulesEndOffset: 0,
3330 ParseableSwiftInterfaces: Options.ParseableSwiftInterfaces,
3331 ReportWarning: [&](const Twine &Warning, const DWARFDie &DIE) {
3332 reportWarning(Warning, File: Context.File, DIE: &DIE);
3333 });
3334 // Keep everything.
3335 Unit.Unit->markEverythingAsKept();
3336
3337 // Clone unit.
3338 UnitListTy CompileUnits;
3339 CompileUnits.emplace_back(args: std::move(Unit.Unit));
3340 assert(TheDwarfEmitter);
3341 DIECloner(*this, TheDwarfEmitter, Unit.File, DIEAlloc, CompileUnits,
3342 Options.Update, DebugStrPool, DebugLineStrPool, StringOffsetPool)
3343 .cloneAllCompileUnits(DwarfContext&: *Unit.File.Dwarf, File: Unit.File,
3344 IsLittleEndian: Unit.File.Dwarf->isLittleEndian());
3345 return Error::success();
3346}
3347
3348void DWARFLinker::verifyInput(const DWARFFile &File) {
3349 assert(File.Dwarf);
3350
3351 std::string Buffer;
3352 raw_string_ostream OS(Buffer);
3353 DIDumpOptions DumpOpts;
3354 if (!File.Dwarf->verify(OS, DumpOpts: DumpOpts.noImplicitRecursion())) {
3355 if (Options.InputVerificationHandler)
3356 Options.InputVerificationHandler(File, OS.str());
3357 }
3358}
3359
3360} // namespace llvm
3361