1//===- bolt/Core/DIEBuilder.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 "bolt/Core/DIEBuilder.h"
10#include "bolt/Core/BinaryContext.h"
11#include "bolt/Core/ParallelUtilities.h"
12#include "llvm/ADT/StringRef.h"
13#include "llvm/BinaryFormat/Dwarf.h"
14#include "llvm/CodeGen/DIE.h"
15#include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
16#include "llvm/DebugInfo/DWARF/DWARFDie.h"
17#include "llvm/DebugInfo/DWARF/DWARFExpression.h"
18#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
19#include "llvm/DebugInfo/DWARF/DWARFTypeUnit.h"
20#include "llvm/DebugInfo/DWARF/DWARFUnit.h"
21#include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
22#include "llvm/Support/Casting.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/ErrorHandling.h"
25#include "llvm/Support/LEB128.h"
26
27#include <algorithm>
28#include <cstdint>
29#include <memory>
30#include <mutex>
31#include <optional>
32#include <unordered_map>
33#include <utility>
34#include <vector>
35
36#undef DEBUG_TYPE
37#define DEBUG_TYPE "bolt"
38namespace opts {
39extern cl::opt<unsigned> Verbosity;
40}
41namespace llvm {
42namespace bolt {
43
44void DIEBuilder::updateReferences() {
45 for (auto &[SrcDIEInfo, ReferenceInfo] : getState().AddrReferences) {
46 DIEInfo *DstDIEInfo = ReferenceInfo.Dst;
47 DWARFUnitInfo &DstUnitInfo = getUnitInfo(UnitId: DstDIEInfo->UnitId);
48 dwarf::Attribute Attr = ReferenceInfo.AttrSpec.Attr;
49 dwarf::Form Form = ReferenceInfo.AttrSpec.Form;
50
51 const uint64_t NewAddr =
52 DstDIEInfo->Die->getOffset() + DstUnitInfo.UnitOffset;
53 SrcDIEInfo->Die->replaceValue(Alloc&: getState().DIEAlloc, Attribute: Attr, Form,
54 NewValue: DIEInteger(NewAddr));
55 }
56
57 // Handling referenes in location expressions.
58 for (LocWithReference &LocExpr : getState().LocWithReferencesToProcess) {
59 SmallVector<uint8_t, 32> Buffer;
60 DataExtractor Data(StringRef((const char *)LocExpr.BlockData.data(),
61 LocExpr.BlockData.size()),
62 LocExpr.U.isLittleEndian(),
63 LocExpr.U.getAddressByteSize());
64 DWARFExpression Expr(Data, LocExpr.U.getAddressByteSize(),
65 LocExpr.U.getFormParams().Format);
66 cloneExpression(Data, Expression: Expr, U&: LocExpr.U, OutputBuffer&: Buffer, Stage: CloneExpressionStage::PATCH);
67
68 DIEValueList *AttrVal;
69 if (LocExpr.Form == dwarf::DW_FORM_exprloc) {
70 DIELoc *DL = new (getState().DIEAlloc) DIELoc;
71 DL->setSize(Buffer.size());
72 AttrVal = static_cast<DIEValueList *>(DL);
73 } else {
74 DIEBlock *DBL = new (getState().DIEAlloc) DIEBlock;
75 DBL->setSize(Buffer.size());
76 AttrVal = static_cast<DIEValueList *>(DBL);
77 }
78 for (auto Byte : Buffer)
79 AttrVal->addValue(Alloc&: getState().DIEAlloc, Attribute: static_cast<dwarf::Attribute>(0),
80 Form: dwarf::DW_FORM_data1, Value: DIEInteger(Byte));
81
82 DIEValue Value;
83 if (LocExpr.Form == dwarf::DW_FORM_exprloc)
84 Value =
85 DIEValue(dwarf::Attribute(LocExpr.Attr), dwarf::Form(LocExpr.Form),
86 static_cast<DIELoc *>(AttrVal));
87 else
88 Value =
89 DIEValue(dwarf::Attribute(LocExpr.Attr), dwarf::Form(LocExpr.Form),
90 static_cast<DIEBlock *>(AttrVal));
91
92 LocExpr.Die.replaceValue(Alloc&: getState().DIEAlloc, Attribute: LocExpr.Attr, Form: LocExpr.Form,
93 NewValue&: Value);
94 }
95
96 return;
97}
98
99uint32_t DIEBuilder::allocDIE(const DWARFUnit &DU, const DWARFDie &DDie,
100 BumpPtrAllocator &Alloc, const uint32_t UId) {
101 DWARFUnitInfo &DWARFUnitInfo = getUnitInfo(UnitId: UId);
102 const uint64_t DDieOffset = DDie.getOffset();
103 if (DWARFUnitInfo.DIEIDMap.count(x: DDieOffset))
104 return DWARFUnitInfo.DIEIDMap[DDieOffset];
105
106 DIE *Die = DIE::get(Alloc, Tag: dwarf::Tag(DDie.getTag()));
107 // This handles the case where there is a DIE ref which points to
108 // invalid DIE. This prevents assert when IR is written out.
109 // Also it makes debugging easier.
110 // DIE dump is not very useful.
111 // It's nice to know original offset from which this DIE was constructed.
112 Die->setOffset(DDie.getOffset());
113 if (opts::Verbosity >= 1)
114 getState().DWARFDieAddressesParsed.insert(x: DDie.getOffset());
115 const uint32_t DId = DWARFUnitInfo.DieInfoVector.size();
116 DWARFUnitInfo.DIEIDMap[DDieOffset] = DId;
117 DWARFUnitInfo.DieInfoVector.emplace_back(
118 args: std::make_unique<DIEInfo>(args: DIEInfo{.Die: Die, .DieId: DId, .UnitId: UId}));
119 return DId;
120}
121
122void DIEBuilder::constructFromUnit(DWARFUnit &DU) {
123 std::optional<uint32_t> UnitId = getUnitId(DU);
124 if (!UnitId) {
125 BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: "
126 << "Skip Unit at " << Twine::utohexstr(Val: DU.getOffset()) << "\n";
127 return;
128 }
129
130 const uint32_t UnitHeaderSize = DU.getHeaderSize();
131 uint64_t DIEOffset = DU.getOffset() + UnitHeaderSize;
132 uint64_t NextCUOffset = DU.getNextUnitOffset();
133 DWARFDataExtractor DebugInfoData = DU.getDebugInfoExtractor();
134 DWARFDebugInfoEntry DIEEntry;
135 std::vector<DIE *> CurParentDIEStack;
136 std::vector<uint32_t> Parents;
137 uint32_t TUTypeOffset = 0;
138
139 if (DWARFTypeUnit *TU = dyn_cast_or_null<DWARFTypeUnit>(Val: &DU))
140 TUTypeOffset = TU->getTypeOffset();
141
142 assert(DebugInfoData.isValidOffset(NextCUOffset - 1));
143 Parents.push_back(UINT32_MAX);
144 do {
145 const bool IsTypeDIE = (TUTypeOffset == DIEOffset - DU.getOffset());
146 if (!DIEEntry.extractFast(U: DU, OffsetPtr: &DIEOffset, DebugInfoData, UEndOffset: NextCUOffset,
147 ParentIdx: Parents.back()))
148 break;
149
150 if (const DWARFAbbreviationDeclaration *AbbrDecl =
151 DIEEntry.getAbbreviationDeclarationPtr()) {
152 DWARFDie DDie(&DU, &DIEEntry);
153
154 DIE *CurDIE = constructDIEFast(DDie, U&: DU, UnitId: *UnitId);
155 DWARFUnitInfo &UI = getUnitInfo(UnitId: *UnitId);
156 // Can't rely on first element in DieVector due to cross CU forward
157 // references.
158 if (!UI.UnitDie)
159 UI.UnitDie = CurDIE;
160 if (IsTypeDIE)
161 getState().TypeDIEMap[&DU] = CurDIE;
162
163 if (!CurParentDIEStack.empty())
164 CurParentDIEStack.back()->addChild(Child: CurDIE);
165
166 if (AbbrDecl->hasChildren())
167 CurParentDIEStack.push_back(x: CurDIE);
168 } else {
169 // NULL DIE: finishes current children scope.
170 CurParentDIEStack.pop_back();
171 }
172 } while (CurParentDIEStack.size() > 0);
173
174 getState().CloneUnitCtxMap[*UnitId].IsConstructed = true;
175}
176
177DIEBuilder::DIEBuilder(BinaryContext &BC, DWARFContext *DwarfContext,
178 DWARF5AcceleratorTable &DebugNamesTable,
179 DWARFUnit *SkeletonCU)
180 : BC(BC), DwarfContext(DwarfContext), SkeletonCU(SkeletonCU),
181 DebugNamesTable(DebugNamesTable) {}
182
183static unsigned int getCUNum(DWARFContext *DwarfContext, bool IsDWO) {
184 unsigned int CUNum = IsDWO ? DwarfContext->getNumDWOCompileUnits()
185 : DwarfContext->getNumCompileUnits();
186 CUNum += IsDWO ? DwarfContext->getNumDWOTypeUnits()
187 : DwarfContext->getNumTypeUnits();
188 return CUNum;
189}
190
191void DIEBuilder::buildTypeUnits(DebugStrOffsetsWriter *StrOffsetWriter,
192 const bool Init) {
193 if (Init)
194 BuilderState.reset(p: new State());
195
196 const DWARFUnitIndex &TUIndex = DwarfContext->getTUIndex();
197 if (!TUIndex.getRows().empty()) {
198 for (auto &Row : TUIndex.getRows()) {
199 uint64_t Signature = Row.getSignature();
200 // manually populate TypeUnit to UnitVector
201 DwarfContext->getTypeUnitForHash(Version: DwarfContext->getMaxVersion(), Hash: Signature,
202 IsDWO: true);
203 }
204 }
205 const unsigned int CUNum = getCUNum(DwarfContext, IsDWO: isDWO());
206 getState().CloneUnitCtxMap.resize(new_size: CUNum);
207 DWARFContext::unit_iterator_range CU4TURanges =
208 isDWO() ? DwarfContext->dwo_types_section_units()
209 : DwarfContext->types_section_units();
210
211 getState().Type = ProcessingType::DWARF4TUs;
212 for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges)
213 registerUnit(DU&: *DU.get(), NeedSort: false);
214
215 for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges)
216 constructFromUnit(DU&: *DU.get());
217
218 DWARFContext::unit_iterator_range CURanges =
219 isDWO() ? DwarfContext->dwo_info_section_units()
220 : DwarfContext->info_section_units();
221
222 // This handles DWARF4 CUs and DWARF5 CU/TUs.
223 // Creating a vector so that for reference handling only DWARF5 CU/TUs are
224 // used, and not DWARF4 TUs.
225 getState().Type = ProcessingType::DWARF5TUs;
226 for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
227 if (!DU->isTypeUnit())
228 continue;
229 registerUnit(DU&: *DU.get(), NeedSort: false);
230 }
231
232 for (DWARFUnit *DU : getState().DWARF5TUVector) {
233 constructFromUnit(DU&: *DU);
234 if (StrOffsetWriter)
235 StrOffsetWriter->finalizeSection(Unit&: *DU, DIEBldr&: *this);
236 }
237}
238
239void DIEBuilder::buildCompileUnits(const bool Init) {
240 if (Init)
241 BuilderState.reset(p: new State());
242
243 unsigned int CUNum = getCUNum(DwarfContext, IsDWO: isDWO());
244 getState().CloneUnitCtxMap.resize(new_size: CUNum);
245 DWARFContext::unit_iterator_range CURanges =
246 isDWO() ? DwarfContext->dwo_info_section_units()
247 : DwarfContext->info_section_units();
248
249 // This handles DWARF4 CUs and DWARF5 CU/TUs.
250 // Creating a vector so that for reference handling only DWARF5 CU/TUs are
251 // used, and not DWARF4 TUs.getState().DUList
252 getState().Type = ProcessingType::CUs;
253 for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
254 if (DU->isTypeUnit())
255 continue;
256 registerUnit(DU&: *DU.get(), NeedSort: false);
257 }
258
259 // Using DULIst since it can be modified by cross CU refrence resolution.
260 for (DWARFUnit *DU : getState().DUList) {
261 if (DU->isTypeUnit())
262 continue;
263 constructFromUnit(DU&: *DU);
264 }
265}
266void DIEBuilder::buildCompileUnits(const std::vector<DWARFUnit *> &CUs) {
267 BuilderState.reset(p: new State());
268 // Allocating enough for current batch being processed.
269 // In real use cases we either processing a batch of CUs with no cross
270 // references, or if they do have them it is due to LTO. With clang they will
271 // share the same abbrev table. In either case this vector will not grow.
272 getState().CloneUnitCtxMap.resize(new_size: CUs.size());
273 getState().Type = ProcessingType::CUs;
274 for (DWARFUnit *CU : CUs)
275 registerUnit(DU&: *CU, NeedSort: false);
276
277 for (DWARFUnit *DU : getState().DUList)
278 constructFromUnit(DU&: *DU);
279}
280
281void DIEBuilder::buildDWOUnit(DWARFUnit &U) {
282 BuilderState.release();
283 BuilderState = std::make_unique<State>();
284 buildTypeUnits(StrOffsetWriter: nullptr, Init: false);
285 getState().Type = ProcessingType::CUs;
286 registerUnit(DU&: U, NeedSort: false);
287 constructFromUnit(DU&: U);
288}
289
290DIE *DIEBuilder::constructDIEFast(DWARFDie &DDie, DWARFUnit &U,
291 uint32_t UnitId) {
292
293 std::optional<uint32_t> Idx = getAllocDIEId(DU: U, DDie);
294 if (Idx) {
295 DWARFUnitInfo &DWARFUnitInfo = getUnitInfo(UnitId);
296 DIEInfo &DieInfo = getDIEInfo(UnitId, DIEId: *Idx);
297 if (DWARFUnitInfo.IsConstructed && DieInfo.Die)
298 return DieInfo.Die;
299 } else {
300 Idx = allocDIE(DU: U, DDie, Alloc&: getState().DIEAlloc, UId: UnitId);
301 }
302
303 DIEInfo &DieInfo = getDIEInfo(UnitId, DIEId: *Idx);
304
305 uint64_t Offset = DDie.getOffset();
306 uint64_t NextOffset = Offset;
307 DWARFDataExtractor Data = U.getDebugInfoExtractor();
308 DWARFDebugInfoEntry DDIEntry;
309
310 if (DDIEntry.extractFast(U, OffsetPtr: &NextOffset, DebugInfoData: Data, UEndOffset: U.getNextUnitOffset(), ParentIdx: 0))
311 assert(NextOffset - U.getOffset() <= Data.getData().size() &&
312 "NextOffset OOB");
313
314 SmallString<40> DIECopy(Data.getData().substr(Start: Offset, N: NextOffset - Offset));
315 Data =
316 DWARFDataExtractor(DIECopy, Data.isLittleEndian(), Data.getAddressSize());
317
318 const DWARFAbbreviationDeclaration *Abbrev =
319 DDie.getAbbreviationDeclarationPtr();
320 uint64_t AttrOffset = getULEB128Size(Value: Abbrev->getCode());
321
322 using AttrSpec = DWARFAbbreviationDeclaration::AttributeSpec;
323 for (const AttrSpec &AttrSpec : Abbrev->attributes()) {
324 DWARFFormValue Val(AttrSpec.Form);
325 Val.extractValue(Data, OffsetPtr: &AttrOffset, FormParams: U.getFormParams(), U: &U);
326 cloneAttribute(Die&: *DieInfo.Die, InputDIE: DDie, U, Val, AttrSpec);
327 }
328 return DieInfo.Die;
329}
330
331static DWARFUnit *
332getUnitForOffset(DIEBuilder &Builder, DWARFContext &DWCtx,
333 const uint64_t Offset,
334 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
335 auto findUnit = [&](std::vector<DWARFUnit *> &Units) -> DWARFUnit * {
336 auto CUIter = llvm::upper_bound(Range&: Units, Value: Offset,
337 C: [](uint64_t LHS, const DWARFUnit *RHS) {
338 return LHS < RHS->getNextUnitOffset();
339 });
340 static std::vector<DWARFUnit *> CUOffsets;
341 static std::once_flag InitVectorFlag;
342 auto initCUVector = [&]() {
343 CUOffsets.reserve(n: DWCtx.getNumCompileUnits());
344 for (const std::unique_ptr<DWARFUnit> &CU : DWCtx.compile_units())
345 CUOffsets.emplace_back(args: CU.get());
346 };
347 DWARFUnit *CU = CUIter != Units.end() ? *CUIter : nullptr;
348 // Above algorithm breaks when there is only one CU, and reference is
349 // outside of it. Fall through slower path, that searches all the CUs.
350 // For example when src and destination of cross CU references have
351 // different abbrev section.
352 if (!CU ||
353 (CU && AttrSpec.Form == dwarf::DW_FORM_ref_addr &&
354 !(CU->getOffset() < Offset && CU->getNextUnitOffset() > Offset))) {
355 // This is a work around for XCode clang. There is a build error when we
356 // pass DWCtx.compile_units() to llvm::upper_bound
357 std::call_once(once&: InitVectorFlag, f&: initCUVector);
358 auto CUIter = std::upper_bound(first: CUOffsets.begin(), last: CUOffsets.end(), val: Offset,
359 comp: [](uint64_t LHS, const DWARFUnit *RHS) {
360 return LHS < RHS->getNextUnitOffset();
361 });
362 CU = CUIter != CUOffsets.end() ? (*CUIter) : nullptr;
363 }
364 return CU;
365 };
366
367 switch (Builder.getCurrentProcessingState()) {
368 case DIEBuilder::ProcessingType::DWARF4TUs:
369 return findUnit(Builder.getDWARF4TUVector());
370 case DIEBuilder::ProcessingType::DWARF5TUs:
371 return findUnit(Builder.getDWARF5TUVector());
372 case DIEBuilder::ProcessingType::CUs:
373 return findUnit(Builder.getDWARFCUVector());
374 };
375
376 return nullptr;
377}
378
379uint32_t DIEBuilder::finalizeDIEs(
380 DWARFUnit &CU, DIE &Die,
381 std::vector<std::optional<BOLTDWARF5AccelTableData *>> &Parents,
382 uint32_t &CurOffset) {
383 getState().DWARFDieAddressesParsed.erase(x: Die.getOffset());
384 uint32_t CurSize = 0;
385 Die.setOffset(CurOffset);
386 std::optional<BOLTDWARF5AccelTableData *> NameEntry =
387 DebugNamesTable.addAccelTableEntry(
388 Unit&: CU, Die, DWOID: SkeletonCU ? SkeletonCU->getDWOId() : std::nullopt,
389 Parent&: Parents.back());
390 // It is possible that an indexed debugging information entry has a parent
391 // that is not indexed (for example, if its parent does not have a name
392 // attribute). In such a case, a parent attribute may point to a nameless
393 // index entry (that is, one that cannot be reached from any entry in the name
394 // table), or it may point to the nearest ancestor that does have an index
395 // entry.
396 if (NameEntry)
397 Parents.push_back(x: std::move(NameEntry));
398 for (DIEValue &Val : Die.values())
399 CurSize += Val.sizeOf(FormParams: CU.getFormParams());
400 CurSize += getULEB128Size(Value: Die.getAbbrevNumber());
401 CurOffset += CurSize;
402
403 for (DIE &Child : Die.children()) {
404 uint32_t ChildSize = finalizeDIEs(CU, Die&: Child, Parents, CurOffset);
405 CurSize += ChildSize;
406 }
407 // for children end mark.
408 if (Die.hasChildren()) {
409 CurSize += sizeof(uint8_t);
410 CurOffset += sizeof(uint8_t);
411 }
412
413 Die.setSize(CurSize);
414 if (NameEntry)
415 Parents.pop_back();
416
417 return CurSize;
418}
419
420void DIEBuilder::finish() {
421 auto finalizeCU = [&](DWARFUnit &CU, uint64_t &UnitStartOffset) -> void {
422 DIE *UnitDIE = getUnitDIEbyUnit(DU: CU);
423 uint32_t HeaderSize = CU.getHeaderSize();
424 uint32_t CurOffset = HeaderSize;
425 DebugNamesTable.setCurrentUnit(Unit&: CU, UnitStartOffset);
426 std::vector<std::optional<BOLTDWARF5AccelTableData *>> Parents;
427 Parents.push_back(x: std::nullopt);
428 finalizeDIEs(CU, Die&: *UnitDIE, Parents, CurOffset);
429
430 DWARFUnitInfo &CurUnitInfo = getUnitInfoByDwarfUnit(DwarfUnit: CU);
431 CurUnitInfo.UnitOffset = UnitStartOffset;
432 CurUnitInfo.UnitLength = HeaderSize + UnitDIE->getSize();
433 UnitStartOffset += CurUnitInfo.UnitLength;
434 };
435 // Computing offsets for .debug_types section.
436 // It's processed first when CU is registered so will be at the begginnig of
437 // the vector.
438 uint64_t TypeUnitStartOffset = 0;
439 for (DWARFUnit *CU : getState().DUList) {
440 // We process DWARF$ types first.
441 if (!(CU->getVersion() < 5 && CU->isTypeUnit()))
442 break;
443 finalizeCU(*CU, TypeUnitStartOffset);
444 }
445
446 for (DWARFUnit *CU : getState().DUList) {
447 // Skipping DWARF4 types.
448 if (CU->getVersion() < 5 && CU->isTypeUnit())
449 continue;
450 finalizeCU(*CU, UnitSize);
451 }
452 if (opts::Verbosity >= 1) {
453 if (!getState().DWARFDieAddressesParsed.empty())
454 dbgs() << "Referenced DIE offsets not in .debug_info\n";
455 for (const uint64_t Address : getState().DWARFDieAddressesParsed) {
456 dbgs() << Twine::utohexstr(Val: Address) << "\n";
457 }
458 }
459 updateReferences();
460}
461
462DWARFDie DIEBuilder::resolveDIEReference(
463 const DWARFFormValue &RefValue,
464 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
465 DWARFUnit *&RefCU, DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
466 assert(RefValue.isFormClass(DWARFFormValue::FC_Reference));
467 uint64_t RefOffset = *RefValue.getAsReference();
468 return resolveDIEReference(AttrSpec, ReffOffset: RefOffset, RefCU, DwarfDebugInfoEntry);
469}
470
471DWARFDie DIEBuilder::resolveDIEReference(
472 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
473 const uint64_t RefOffset, DWARFUnit *&RefCU,
474 DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
475 uint64_t TmpRefOffset = RefOffset;
476 if ((RefCU =
477 getUnitForOffset(Builder&: *this, DWCtx&: *DwarfContext, Offset: TmpRefOffset, AttrSpec))) {
478 /// Trying to add to current working set in case it's cross CU reference.
479 registerUnit(DU&: *RefCU, NeedSort: true);
480 DWARFDataExtractor DebugInfoData = RefCU->getDebugInfoExtractor();
481 if (DwarfDebugInfoEntry.extractFast(U: *RefCU, OffsetPtr: &TmpRefOffset, DebugInfoData,
482 UEndOffset: RefCU->getNextUnitOffset(), ParentIdx: 0)) {
483 // In a file with broken references, an attribute might point to a NULL
484 // DIE.
485 DWARFDie RefDie = DWARFDie(RefCU, &DwarfDebugInfoEntry);
486 if (!RefDie.isNULL()) {
487 std::optional<uint32_t> UnitId = getUnitId(DU: *RefCU);
488
489 // forward reference
490 if (UnitId && !getState().CloneUnitCtxMap[*UnitId].IsConstructed &&
491 !getAllocDIEId(DU: *RefCU, DDie: RefDie))
492 allocDIE(DU: *RefCU, DDie: RefDie, Alloc&: getState().DIEAlloc, UId: *UnitId);
493 return RefDie;
494 }
495 BC.errs()
496 << "BOLT-WARNING: [internal-dwarf-error]: invalid referenced DIE "
497 "at offset: "
498 << Twine::utohexstr(Val: RefOffset) << ".\n";
499
500 } else {
501 BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: could not parse "
502 "referenced DIE at offset: "
503 << Twine::utohexstr(Val: RefOffset) << ".\n";
504 }
505 } else {
506 BC.errs()
507 << "BOLT-WARNING: [internal-dwarf-error]: could not find referenced "
508 "CU. Referenced DIE offset: "
509 << Twine::utohexstr(Val: RefOffset) << ".\n";
510 }
511 return DWARFDie();
512}
513
514void DIEBuilder::cloneDieReferenceAttribute(
515 DIE &Die, const DWARFUnit &U, const DWARFDie &InputDIE,
516 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
517 const DWARFFormValue &Val) {
518 const uint64_t Ref = *Val.getAsReference();
519
520 DIE *NewRefDie = nullptr;
521 DWARFUnit *RefUnit = nullptr;
522
523 DWARFDebugInfoEntry DDIEntry;
524 const DWARFDie RefDie = resolveDIEReference(RefValue: Val, AttrSpec, RefCU&: RefUnit, DwarfDebugInfoEntry&: DDIEntry);
525
526 if (!RefDie)
527 return;
528
529 const std::optional<uint32_t> UnitId = getUnitId(DU: *RefUnit);
530 const std::optional<uint32_t> IsAllocId = getAllocDIEId(DU: *RefUnit, DDie: RefDie);
531 assert(IsAllocId.has_value() && "Encountered unexpected unallocated DIE.");
532 const uint32_t DIEId = *IsAllocId;
533 DIEInfo &DieInfo = getDIEInfo(UnitId: *UnitId, DIEId);
534
535 if (!DieInfo.Die) {
536 assert(Ref > InputDIE.getOffset());
537 (void)Ref;
538 BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: encounter unexpected "
539 "unallocated DIE. Should be alloc!\n";
540 // We haven't cloned this DIE yet. Just create an empty one and
541 // store it. It'll get really cloned when we process it.
542 DieInfo.Die = DIE::get(Alloc&: getState().DIEAlloc, Tag: dwarf::Tag(RefDie.getTag()));
543 }
544 NewRefDie = DieInfo.Die;
545
546 if (AttrSpec.Form == dwarf::DW_FORM_ref_addr) {
547 // Adding referenced DIE to DebugNames to be used when entries are created
548 // that contain cross cu references.
549 if (DebugNamesTable.canGenerateEntryWithCrossCUReference(Unit: U, Die, AttrSpec))
550 DebugNamesTable.addCrossCUDie(Die: DieInfo.Die);
551 // no matter forward reference or backward reference, we are supposed
552 // to calculate them in `finish` due to the possible modification of
553 // the DIE.
554 DWARFDie CurDie = const_cast<DWARFDie &>(InputDIE);
555 DIEInfo *CurDieInfo = &getDIEInfoByDwarfDie(DwarfDie&: CurDie);
556 getState().AddrReferences.push_back(
557 x: std::make_pair(x&: CurDieInfo, y: AddrReferenceInfo(&DieInfo, AttrSpec)));
558
559 Die.addValue(Alloc&: getState().DIEAlloc, Attribute: AttrSpec.Attr, Form: dwarf::DW_FORM_ref_addr,
560 Value: DIEInteger(DieInfo.Die->getOffset()));
561 return;
562 }
563
564 Die.addValue(Alloc&: getState().DIEAlloc, Attribute: AttrSpec.Attr, Form: AttrSpec.Form,
565 Value: DIEEntry(*NewRefDie));
566}
567
568void DIEBuilder::cloneStringAttribute(
569 DIE &Die, const DWARFUnit &U,
570 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
571 const DWARFFormValue &Val) {
572 if (AttrSpec.Form == dwarf::DW_FORM_string) {
573 Expected<const char *> StrAddr = Val.getAsCString();
574 if (!StrAddr) {
575 consumeError(Err: StrAddr.takeError());
576 return;
577 }
578 Die.addValue(Alloc&: getState().DIEAlloc, Attribute: AttrSpec.Attr, Form: dwarf::DW_FORM_string,
579 Value: new (getState().DIEAlloc)
580 DIEInlineString(StrAddr.get(), getState().DIEAlloc));
581 } else {
582 std::optional<uint64_t> OffsetIndex = Val.getRawUValue();
583 Die.addValue(Alloc&: getState().DIEAlloc, Attribute: AttrSpec.Attr, Form: AttrSpec.Form,
584 Value: DIEInteger(*OffsetIndex));
585 }
586}
587
588bool DIEBuilder::cloneExpression(const DataExtractor &Data,
589 const DWARFExpression &Expression,
590 DWARFUnit &U,
591 SmallVectorImpl<uint8_t> &OutputBuffer,
592 const CloneExpressionStage &Stage) {
593 using Encoding = DWARFExpression::Operation::Encoding;
594 using Descr = DWARFExpression::Operation::Description;
595 uint64_t OpOffset = 0;
596 bool DoesContainReference = false;
597 for (const DWARFExpression::Operation &Op : Expression) {
598 const Descr &Description = Op.getDescription();
599 // DW_OP_const_type is variable-length and has 3
600 // operands. Thus far we only support 2.
601 if ((Description.Op.size() == 2 &&
602 Description.Op[0] == Encoding::BaseTypeRef) ||
603 (Description.Op.size() == 2 &&
604 Description.Op[1] == Encoding::BaseTypeRef &&
605 Description.Op[0] != Encoding::Size1))
606 BC.outs() << "BOLT-WARNING: [internal-dwarf-error]: unsupported DW_OP "
607 "encoding.\n";
608
609 if ((Description.Op.size() == 1 &&
610 Description.Op[0] == Encoding::BaseTypeRef) ||
611 (Description.Op.size() == 2 &&
612 Description.Op[1] == Encoding::BaseTypeRef &&
613 Description.Op[0] == Encoding::Size1)) {
614 // This code assumes that the other non-typeref operand fits into 1
615 // byte.
616 assert(OpOffset < Op.getEndOffset());
617 const uint32_t ULEBsize = Op.getEndOffset() - OpOffset - 1;
618 (void)ULEBsize;
619 assert(ULEBsize <= 16);
620
621 // Copy over the operation.
622 OutputBuffer.push_back(Elt: Op.getCode());
623 uint64_t RefOffset;
624 if (Description.Op.size() == 1) {
625 RefOffset = Op.getRawOperand(Idx: 0);
626 } else {
627 OutputBuffer.push_back(Elt: Op.getRawOperand(Idx: 0));
628 RefOffset = Op.getRawOperand(Idx: 1);
629 }
630 uint32_t Offset = 0;
631 if (RefOffset > 0 || Op.getCode() != dwarf::DW_OP_convert) {
632 DoesContainReference = true;
633 std::optional<uint32_t> RefDieID =
634 getAllocDIEId(DU: U, Offset: U.getOffset() + RefOffset);
635 std::optional<uint32_t> RefUnitID = getUnitId(DU: U);
636 if (RefDieID.has_value() && RefUnitID.has_value()) {
637 DIEInfo &RefDieInfo = getDIEInfo(UnitId: *RefUnitID, DIEId: *RefDieID);
638 if (DIE *Clone = RefDieInfo.Die)
639 Offset = Stage == CloneExpressionStage::INIT ? RefOffset
640 : Clone->getOffset();
641 else
642 BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: base type ref "
643 "doesn't point to "
644 "DW_TAG_base_type.\n";
645 }
646 }
647 uint8_t ULEB[16];
648 // Hard coding to max size so size doesn't change when we update the
649 // offset.
650 encodeULEB128(Value: Offset, p: ULEB, PadTo: 4);
651 ArrayRef<uint8_t> ULEBbytes(ULEB, 4);
652 OutputBuffer.append(in_start: ULEBbytes.begin(), in_end: ULEBbytes.end());
653 } else {
654 // Copy over everything else unmodified.
655 const StringRef Bytes = Data.getData().slice(Start: OpOffset, End: Op.getEndOffset());
656 OutputBuffer.append(in_start: Bytes.begin(), in_end: Bytes.end());
657 }
658 OpOffset = Op.getEndOffset();
659 }
660 return DoesContainReference;
661}
662
663void DIEBuilder::cloneBlockAttribute(
664 DIE &Die, DWARFUnit &U,
665 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
666 const DWARFFormValue &Val) {
667 DIEValueList *Attr;
668 DIEValue Value;
669 DIELoc *Loc = nullptr;
670 DIEBlock *Block = nullptr;
671
672 if (AttrSpec.Form == dwarf::DW_FORM_exprloc) {
673 Loc = new (getState().DIEAlloc) DIELoc;
674 } else if (doesFormBelongToClass(Form: AttrSpec.Form, FC: DWARFFormValue::FC_Block,
675 DwarfVersion: U.getVersion())) {
676 Block = new (getState().DIEAlloc) DIEBlock;
677 } else {
678 BC.errs()
679 << "BOLT-WARNING: [internal-dwarf-error]: Unexpected Form value in "
680 "cloneBlockAttribute\n";
681 return;
682 }
683 Attr = Loc ? static_cast<DIEValueList *>(Loc)
684 : static_cast<DIEValueList *>(Block);
685
686 SmallVector<uint8_t, 32> Buffer;
687 ArrayRef<uint8_t> Bytes = *Val.getAsBlock();
688 if (DWARFAttribute::mayHaveLocationExpr(Attr: AttrSpec.Attr) &&
689 (Val.isFormClass(FC: DWARFFormValue::FC_Block) ||
690 Val.isFormClass(FC: DWARFFormValue::FC_Exprloc))) {
691 DataExtractor Data(StringRef((const char *)Bytes.data(), Bytes.size()),
692 U.isLittleEndian(), U.getAddressByteSize());
693 DWARFExpression Expr(Data, U.getAddressByteSize(),
694 U.getFormParams().Format);
695 if (cloneExpression(Data, Expression: Expr, U, OutputBuffer&: Buffer, Stage: CloneExpressionStage::INIT))
696 getState().LocWithReferencesToProcess.emplace_back(
697 args: Bytes.vec(), args&: U, args&: Die, args: AttrSpec.Form, args: AttrSpec.Attr);
698 Bytes = Buffer;
699 }
700 for (auto Byte : Bytes)
701 Attr->addValue(Alloc&: getState().DIEAlloc, Attribute: static_cast<dwarf::Attribute>(0),
702 Form: dwarf::DW_FORM_data1, Value: DIEInteger(Byte));
703
704 if (Loc)
705 Loc->setSize(Bytes.size());
706 else
707 Block->setSize(Bytes.size());
708
709 if (Loc)
710 Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
711 dwarf::Form(AttrSpec.Form), Loc);
712 else
713 Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
714 dwarf::Form(AttrSpec.Form), Block);
715 Die.addValue(Alloc&: getState().DIEAlloc, V: Value);
716}
717
718void DIEBuilder::cloneAddressAttribute(
719 DIE &Die, const DWARFUnit &U,
720 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
721 const DWARFFormValue &Val) {
722 Die.addValue(Alloc&: getState().DIEAlloc, Attribute: AttrSpec.Attr, Form: AttrSpec.Form,
723 Value: DIEInteger(Val.getRawUValue()));
724}
725
726void DIEBuilder::cloneRefsigAttribute(
727 DIE &Die, DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
728 const DWARFFormValue &Val) {
729 const std::optional<uint64_t> SigVal = Val.getRawUValue();
730 Die.addValue(Alloc&: getState().DIEAlloc, Attribute: AttrSpec.Attr, Form: dwarf::DW_FORM_ref_sig8,
731 Value: DIEInteger(*SigVal));
732}
733
734void DIEBuilder::cloneScalarAttribute(
735 DIE &Die, const DWARFDie &InputDIE,
736 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
737 const DWARFFormValue &Val) {
738 uint64_t Value;
739
740 if (auto OptionalValue = Val.getAsUnsignedConstant())
741 Value = *OptionalValue;
742 else if (auto OptionalValue = Val.getAsSignedConstant())
743 Value = *OptionalValue;
744 else if (auto OptionalValue = Val.getAsSectionOffset())
745 Value = *OptionalValue;
746 else {
747 BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
748 "attribute form. Dropping "
749 "attribute.\n";
750 return;
751 }
752
753 Die.addValue(Alloc&: getState().DIEAlloc, Attribute: AttrSpec.Attr, Form: AttrSpec.Form,
754 Value: DIEInteger(Value));
755}
756
757void DIEBuilder::cloneLoclistAttrubute(
758 DIE &Die, const DWARFDie &InputDIE,
759 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
760 const DWARFFormValue &Val) {
761 std::optional<uint64_t> Value = std::nullopt;
762
763 if (auto OptionalValue = Val.getAsUnsignedConstant())
764 Value = OptionalValue;
765 else if (auto OptionalValue = Val.getAsSignedConstant())
766 Value = OptionalValue;
767 else if (auto OptionalValue = Val.getAsSectionOffset())
768 Value = OptionalValue;
769 else
770 BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
771 "attribute form. Dropping "
772 "attribute.\n";
773
774 if (!Value.has_value())
775 return;
776
777 Die.addValue(Alloc&: getState().DIEAlloc, Attribute: AttrSpec.Attr, Form: AttrSpec.Form,
778 Value: DIELocList(*Value));
779}
780
781void DIEBuilder::cloneAttribute(
782 DIE &Die, const DWARFDie &InputDIE, DWARFUnit &U, const DWARFFormValue &Val,
783 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
784 switch (AttrSpec.Form) {
785 case dwarf::DW_FORM_strp:
786 case dwarf::DW_FORM_string:
787 case dwarf::DW_FORM_strx:
788 case dwarf::DW_FORM_strx1:
789 case dwarf::DW_FORM_strx2:
790 case dwarf::DW_FORM_strx3:
791 case dwarf::DW_FORM_strx4:
792 case dwarf::DW_FORM_GNU_str_index:
793 case dwarf::DW_FORM_line_strp:
794 cloneStringAttribute(Die, U, AttrSpec, Val);
795 break;
796 case dwarf::DW_FORM_ref_addr:
797 case dwarf::DW_FORM_ref1:
798 case dwarf::DW_FORM_ref2:
799 case dwarf::DW_FORM_ref4:
800 case dwarf::DW_FORM_ref8:
801 cloneDieReferenceAttribute(Die, U, InputDIE, AttrSpec, Val);
802 break;
803 case dwarf::DW_FORM_block:
804 case dwarf::DW_FORM_block1:
805 case dwarf::DW_FORM_block2:
806 case dwarf::DW_FORM_block4:
807 case dwarf::DW_FORM_exprloc:
808 cloneBlockAttribute(Die, U, AttrSpec, Val);
809 break;
810 case dwarf::DW_FORM_addr:
811 case dwarf::DW_FORM_addrx:
812 case dwarf::DW_FORM_GNU_addr_index:
813 cloneAddressAttribute(Die, U, AttrSpec, Val);
814 break;
815 case dwarf::DW_FORM_data1:
816 case dwarf::DW_FORM_data2:
817 case dwarf::DW_FORM_data4:
818 case dwarf::DW_FORM_data8:
819 case dwarf::DW_FORM_udata:
820 case dwarf::DW_FORM_sdata:
821 case dwarf::DW_FORM_sec_offset:
822 case dwarf::DW_FORM_rnglistx:
823 case dwarf::DW_FORM_flag:
824 case dwarf::DW_FORM_flag_present:
825 case dwarf::DW_FORM_implicit_const:
826 cloneScalarAttribute(Die, InputDIE, AttrSpec, Val);
827 break;
828 case dwarf::DW_FORM_loclistx:
829 cloneLoclistAttrubute(Die, InputDIE, AttrSpec, Val);
830 break;
831 case dwarf::DW_FORM_ref_sig8:
832 cloneRefsigAttribute(Die, AttrSpec, Val);
833 break;
834 default:
835 BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported attribute "
836 "form " +
837 dwarf::FormEncodingString(Encoding: AttrSpec.Form).str() +
838 " in cloneAttribute. Dropping.";
839 }
840}
841void DIEBuilder::assignAbbrev(DIEAbbrev &Abbrev) {
842 // Check the set for priors.
843 FoldingSetNodeID ID;
844 Abbrev.Profile(ID);
845 void *InsertToken;
846 DIEAbbrev *InSet = AbbreviationsSet.FindNodeOrInsertPos(ID, InsertPos&: InsertToken);
847
848 // If it's newly added.
849 if (InSet) {
850 // Assign existing abbreviation number.
851 Abbrev.setNumber(InSet->getNumber());
852 } else {
853 // Add to abbreviation list.
854 Abbreviations.push_back(
855 x: std::make_unique<DIEAbbrev>(args: Abbrev.getTag(), args: Abbrev.hasChildren()));
856 for (const auto &Attr : Abbrev.getData())
857 Abbreviations.back()->AddAttribute(Attribute: Attr.getAttribute(), Form: Attr.getForm());
858 AbbreviationsSet.InsertNode(N: Abbreviations.back().get(), InsertPos: InsertToken);
859 // Assign the unique abbreviation number.
860 Abbrev.setNumber(Abbreviations.size());
861 Abbreviations.back()->setNumber(Abbreviations.size());
862 }
863}
864
865void DIEBuilder::generateAbbrevs() {
866 if (isEmpty())
867 return;
868
869 for (DWARFUnit *DU : getState().DUList) {
870 DIE *UnitDIE = getUnitDIEbyUnit(DU: *DU);
871 generateUnitAbbrevs(Die: UnitDIE);
872 }
873}
874
875void DIEBuilder::generateUnitAbbrevs(DIE *Die) {
876 DIEAbbrev NewAbbrev = Die->generateAbbrev();
877
878 if (Die->hasChildren())
879 NewAbbrev.setChildrenFlag(dwarf::DW_CHILDREN_yes);
880 assignAbbrev(Abbrev&: NewAbbrev);
881 Die->setAbbrevNumber(NewAbbrev.getNumber());
882
883 for (auto &Child : Die->children()) {
884 generateUnitAbbrevs(Die: &Child);
885 }
886}
887
888static uint64_t getHash(const DWARFUnit &DU) {
889 // Before DWARF5 TU units are in their own section, so at least one offset,
890 // first one, will be the same as CUs in .debug_info.dwo section
891 if (DU.getVersion() < 5 && DU.isTypeUnit()) {
892 const uint64_t TypeUnitHash =
893 cast_or_null<DWARFTypeUnit>(Val: &DU)->getTypeHash();
894 const uint64_t Offset = DU.getOffset();
895 return llvm::hash_combine(args: llvm::hash_value(value: TypeUnitHash),
896 args: llvm::hash_value(value: Offset));
897 }
898 return DU.getOffset();
899}
900
901void DIEBuilder::registerUnit(DWARFUnit &DU, bool NeedSort) {
902 auto IterGlobal = AllProcessed.insert(V: getHash(DU));
903 // If DU is already in a current working set or was already processed we can
904 // skip it.
905 if (!IterGlobal.second)
906 return;
907 if (getState().Type == ProcessingType::DWARF4TUs) {
908 getState().DWARF4TUVector.push_back(x: &DU);
909 } else if (getState().Type == ProcessingType::DWARF5TUs) {
910 getState().DWARF5TUVector.push_back(x: &DU);
911 } else {
912 getState().DWARFCUVector.push_back(x: &DU);
913 /// Sorting for cross CU reference resolution.
914 if (NeedSort)
915 std::sort(first: getState().DWARFCUVector.begin(),
916 last: getState().DWARFCUVector.end(),
917 comp: [](const DWARFUnit *A, const DWARFUnit *B) {
918 return A->getOffset() < B->getOffset();
919 });
920 }
921 getState().UnitIDMap[getHash(DU)] = getState().DUList.size();
922 // This handles the case where we do have cross cu references, but CUs do not
923 // share the same abbrev table.
924 if (getState().DUList.size() == getState().CloneUnitCtxMap.size())
925 getState().CloneUnitCtxMap.emplace_back();
926 getState().DUList.push_back(x: &DU);
927}
928
929std::optional<uint32_t> DIEBuilder::getUnitId(const DWARFUnit &DU) {
930 auto Iter = getState().UnitIDMap.find(x: getHash(DU));
931 if (Iter != getState().UnitIDMap.end())
932 return Iter->second;
933 return std::nullopt;
934}
935
936} // namespace bolt
937} // namespace llvm
938

source code of bolt/lib/Core/DIEBuilder.cpp