1 | //===- bolt/Rewrite/DebugNames.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/DebugNames.h" |
10 | #include "bolt/Core/BinaryContext.h" |
11 | #include "llvm/DebugInfo/DWARF/DWARFExpression.h" |
12 | #include "llvm/DebugInfo/DWARF/DWARFTypeUnit.h" |
13 | #include "llvm/Support/EndianStream.h" |
14 | #include "llvm/Support/LEB128.h" |
15 | #include <cstdint> |
16 | #include <optional> |
17 | |
18 | namespace llvm { |
19 | namespace bolt { |
20 | DWARF5AcceleratorTable::DWARF5AcceleratorTable( |
21 | const bool CreateDebugNames, BinaryContext &BC, |
22 | DebugStrWriter &MainBinaryStrWriter) |
23 | : BC(BC), MainBinaryStrWriter(MainBinaryStrWriter) { |
24 | NeedToCreate = CreateDebugNames || BC.getDebugNamesSection(); |
25 | if (!NeedToCreate) |
26 | return; |
27 | FullTableBuffer = std::make_unique<DebugStrBufferVector>(); |
28 | FullTableStream = std::make_unique<raw_svector_ostream>(args&: *FullTableBuffer); |
29 | StrBuffer = std::make_unique<DebugStrBufferVector>(); |
30 | StrStream = std::make_unique<raw_svector_ostream>(args&: *StrBuffer); |
31 | EntriesBuffer = std::make_unique<DebugStrBufferVector>(); |
32 | Entriestream = std::make_unique<raw_svector_ostream>(args&: *EntriesBuffer); |
33 | AugStringBuffer = std::make_unique<DebugStrBufferVector>(); |
34 | AugStringtream = std::make_unique<raw_svector_ostream>(args&: *AugStringBuffer); |
35 | |
36 | // Binary has split-dwarf CUs. |
37 | // Even thought for non-skeleton-cu all names are in .debug_str.dwo section, |
38 | // for the .debug_names contributions they are in .debug_str section. |
39 | if (BC.getNumDWOCUs()) { |
40 | DataExtractor StrData(BC.DwCtx->getDWARFObj().getStrSection(), |
41 | BC.DwCtx->isLittleEndian(), 0); |
42 | uint64_t Offset = 0; |
43 | uint64_t StrOffset = 0; |
44 | while (StrData.isValidOffset(offset: Offset)) { |
45 | Error Err = Error::success(); |
46 | const char *CStr = StrData.getCStr(OffsetPtr: &Offset, Err: &Err); |
47 | if (Err) { |
48 | NeedToCreate = false; |
49 | BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Could not extract " |
50 | "string from .debug_str section at offset: " |
51 | << Twine::utohexstr(Val: StrOffset) << ".\n"; |
52 | return; |
53 | } |
54 | auto R = StrCacheToOffsetMap.try_emplace( |
55 | Key: llvm::hash_value(S: llvm::StringRef(CStr)), Args&: StrOffset); |
56 | if (!R.second) |
57 | BC.errs() |
58 | << "BOLT-WARNING: [internal-dwarf-error]: collision occured on " |
59 | << CStr << " at offset : 0x"<< Twine::utohexstr(Val: StrOffset) |
60 | << ". Previous string offset is: 0x" |
61 | << Twine::utohexstr(Val: R.first->second) << ".\n"; |
62 | StrOffset = Offset; |
63 | } |
64 | } |
65 | } |
66 | |
67 | void DWARF5AcceleratorTable::setCurrentUnit(DWARFUnit &Unit, |
68 | const uint64_t UnitStartOffset) { |
69 | CurrentUnit = nullptr; |
70 | CurrentUnitOffset = UnitStartOffset; |
71 | std::optional<uint64_t> DWOID = Unit.getDWOId(); |
72 | // We process skeleton CUs after DWO Units for it. |
73 | // Patching offset in CU list to correct one. |
74 | if (!Unit.isDWOUnit() && DWOID) { |
75 | auto Iter = CUOffsetsToPatch.find(Val: *DWOID); |
76 | // Check in case no entries were added from non skeleton DWO section. |
77 | if (Iter != CUOffsetsToPatch.end()) |
78 | CUList[Iter->second] = UnitStartOffset; |
79 | } |
80 | } |
81 | |
82 | void DWARF5AcceleratorTable::addUnit(DWARFUnit &Unit, |
83 | const std::optional<uint64_t> &DWOID) { |
84 | constexpr uint32_t BADCUOFFSET = 0xBADBAD; |
85 | StrSection = Unit.getStringSection(); |
86 | if (Unit.isTypeUnit()) { |
87 | if (DWOID) { |
88 | // We adding an entry for a DWO TU. The DWO CU might not have any entries, |
89 | // so need to add it to the list pre-emptively. |
90 | auto Iter = CUOffsetsToPatch.insert(KV: {*DWOID, CUList.size()}); |
91 | if (Iter.second) |
92 | CUList.push_back(Elt: BADCUOFFSET); |
93 | const uint64_t TUHash = cast<DWARFTypeUnit>(Val: &Unit)->getTypeHash(); |
94 | if (!TUHashToIndexMap.count(Val: TUHash)) { |
95 | TUHashToIndexMap.insert(KV: {TUHash, ForeignTUList.size()}); |
96 | ForeignTUList.push_back(Elt: TUHash); |
97 | } |
98 | } else { |
99 | LocalTUList.push_back(Elt: CurrentUnitOffset); |
100 | } |
101 | } else { |
102 | if (DWOID) { |
103 | // This is a path for split dwarf without type units. |
104 | // We process DWO Units before Skeleton CU. So at this point we don't know |
105 | // the offset of Skeleton CU. Adding CULit index to a map to patch later |
106 | // with the correct offset. |
107 | auto Iter = CUOffsetsToPatch.insert(KV: {*DWOID, CUList.size()}); |
108 | if (Iter.second) |
109 | CUList.push_back(Elt: BADCUOFFSET); |
110 | } else { |
111 | CUList.push_back(Elt: CurrentUnitOffset); |
112 | } |
113 | } |
114 | } |
115 | |
116 | // Returns true if DW_TAG_variable should be included in .debug-names based on |
117 | // section 6.1.1.1 for DWARF5 spec. |
118 | static bool shouldIncludeVariable(const DWARFUnit &Unit, const DIE &Die) { |
119 | const DIEValue LocAttrInfo = |
120 | Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_location); |
121 | if (!LocAttrInfo) |
122 | return false; |
123 | if (!(doesFormBelongToClass(Form: LocAttrInfo.getForm(), FC: DWARFFormValue::FC_Exprloc, |
124 | DwarfVersion: Unit.getVersion()) || |
125 | doesFormBelongToClass(Form: LocAttrInfo.getForm(), FC: DWARFFormValue::FC_Block, |
126 | DwarfVersion: Unit.getVersion()))) |
127 | return false; |
128 | std::vector<uint8_t> Sblock; |
129 | auto constructVect = |
130 | [&](const DIEValueList::const_value_range &Iter) -> void { |
131 | for (const DIEValue &Val : Iter) |
132 | Sblock.push_back(x: Val.getDIEInteger().getValue()); |
133 | }; |
134 | if (doesFormBelongToClass(Form: LocAttrInfo.getForm(), FC: DWARFFormValue::FC_Exprloc, |
135 | DwarfVersion: Unit.getVersion())) |
136 | constructVect(LocAttrInfo.getDIELoc().values()); |
137 | else |
138 | constructVect(LocAttrInfo.getDIEBlock().values()); |
139 | ArrayRef<uint8_t> Expr = ArrayRef<uint8_t>(Sblock); |
140 | DataExtractor Data(StringRef((const char *)Expr.data(), Expr.size()), |
141 | Unit.getContext().isLittleEndian(), 0); |
142 | DWARFExpression LocExpr(Data, Unit.getAddressByteSize(), |
143 | Unit.getFormParams().Format); |
144 | for (const DWARFExpression::Operation &Expr : LocExpr) |
145 | if (Expr.getCode() == dwarf::DW_OP_addrx || |
146 | Expr.getCode() == dwarf::DW_OP_form_tls_address || |
147 | Expr.getCode() == dwarf::DW_OP_GNU_push_tls_address) |
148 | return true; |
149 | return false; |
150 | } |
151 | |
152 | bool static canProcess(const DWARFUnit &Unit, const DIE &Die, |
153 | std::string &NameToUse, const bool TagsOnly) { |
154 | if (Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_declaration)) |
155 | return false; |
156 | switch (Die.getTag()) { |
157 | case dwarf::DW_TAG_base_type: |
158 | case dwarf::DW_TAG_class_type: |
159 | case dwarf::DW_TAG_enumeration_type: |
160 | case dwarf::DW_TAG_imported_declaration: |
161 | case dwarf::DW_TAG_pointer_type: |
162 | case dwarf::DW_TAG_structure_type: |
163 | case dwarf::DW_TAG_typedef: |
164 | case dwarf::DW_TAG_unspecified_type: |
165 | case dwarf::DW_TAG_union_type: |
166 | if (TagsOnly || Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_name)) |
167 | return true; |
168 | return false; |
169 | case dwarf::DW_TAG_namespace: |
170 | // According to DWARF5 spec namespaces without DW_AT_name needs to have |
171 | // "(anonymous namespace)" |
172 | if (!Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_name)) |
173 | NameToUse = "(anonymous namespace)"; |
174 | return true; |
175 | case dwarf::DW_TAG_inlined_subroutine: |
176 | case dwarf::DW_TAG_label: |
177 | case dwarf::DW_TAG_subprogram: |
178 | if (TagsOnly || Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_low_pc) || |
179 | Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_high_pc) || |
180 | Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_ranges) || |
181 | Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_entry_pc)) |
182 | return true; |
183 | return false; |
184 | case dwarf::DW_TAG_variable: |
185 | return TagsOnly || shouldIncludeVariable(Unit, Die); |
186 | default: |
187 | break; |
188 | } |
189 | return false; |
190 | } |
191 | |
192 | bool DWARF5AcceleratorTable::canGenerateEntryWithCrossCUReference( |
193 | const DWARFUnit &Unit, const DIE &Die, |
194 | const DWARFAbbreviationDeclaration::AttributeSpec &AttrSpec) { |
195 | if (!isCreated()) |
196 | return false; |
197 | std::string NameToUse = ""; |
198 | if (!canProcess(Unit, Die, NameToUse, TagsOnly: true)) |
199 | return false; |
200 | return (AttrSpec.Attr == dwarf::Attribute::DW_AT_abstract_origin || |
201 | AttrSpec.Attr == dwarf::Attribute::DW_AT_specification) && |
202 | AttrSpec.Form == dwarf::DW_FORM_ref_addr; |
203 | } |
204 | /// Returns name offset in String Offset section. |
205 | static uint64_t getNameOffset(BinaryContext &BC, DWARFUnit &Unit, |
206 | const uint64_t Index) { |
207 | const DWARFSection &StrOffsetsSection = Unit.getStringOffsetSection(); |
208 | const std::optional<StrOffsetsContributionDescriptor> &Contr = |
209 | Unit.getStringOffsetsTableContribution(); |
210 | if (!Contr) { |
211 | BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not get " |
212 | "StringOffsetsTableContribution for unit at offset: " |
213 | << Twine::utohexstr(Val: Unit.getOffset()) << ".\n"; |
214 | return 0; |
215 | } |
216 | |
217 | const uint8_t DwarfOffsetByteSize = Contr->getDwarfOffsetByteSize(); |
218 | return support::endian::read32le(P: StrOffsetsSection.Data.data() + Contr->Base + |
219 | Index * DwarfOffsetByteSize); |
220 | } |
221 | |
222 | static uint64_t getEntryID(const BOLTDWARF5AccelTableData &Entry) { |
223 | return reinterpret_cast<uint64_t>(&Entry); |
224 | } |
225 | |
226 | uint32_t DWARF5AcceleratorTable::getUnitID(const DWARFUnit &Unit, |
227 | const std::optional<uint64_t> &DWOID, |
228 | bool &IsTU) { |
229 | IsTU = Unit.isTypeUnit(); |
230 | if (IsTU) { |
231 | if (DWOID) { |
232 | const uint64_t TUHash = cast<DWARFTypeUnit>(Val: &Unit)->getTypeHash(); |
233 | auto Iter = TUHashToIndexMap.find(Val: TUHash); |
234 | assert(Iter != TUHashToIndexMap.end() && "Could not find TU hash in map"); |
235 | return Iter->second; |
236 | } |
237 | return LocalTUList.size() - 1; |
238 | } |
239 | return CUList.size() - 1; |
240 | } |
241 | |
242 | std::optional<std::string> DWARF5AcceleratorTable::getName( |
243 | DWARFUnit &Unit, const std::optional<uint64_t> &DWOID, |
244 | const std::string &NameToUse, DIEValue ValName) { |
245 | if ((!ValName || ValName.getForm() == dwarf::DW_FORM_string) && |
246 | NameToUse.empty()) |
247 | return std::nullopt; |
248 | std::string Name = ""; |
249 | uint64_t NameIndexOffset = 0; |
250 | if (NameToUse.empty()) { |
251 | NameIndexOffset = ValName.getDIEInteger().getValue(); |
252 | if (ValName.getForm() != dwarf::DW_FORM_strp) |
253 | NameIndexOffset = getNameOffset(BC, Unit, Index: NameIndexOffset); |
254 | // Counts on strings end with '\0'. |
255 | Name = std::string(&StrSection.data()[NameIndexOffset]); |
256 | } else { |
257 | Name = NameToUse; |
258 | } |
259 | auto &It = Entries[Name]; |
260 | if (It.Values.empty()) { |
261 | if (DWOID && NameToUse.empty()) { |
262 | // For DWO Unit the offset is in the .debug_str.dwo section. |
263 | // Need to find offset for the name in the .debug_str section. |
264 | llvm::hash_code Hash = llvm::hash_value(S: llvm::StringRef(Name)); |
265 | auto ItCache = StrCacheToOffsetMap.find(Val: Hash); |
266 | if (ItCache == StrCacheToOffsetMap.end()) |
267 | NameIndexOffset = MainBinaryStrWriter.addString(Str: Name); |
268 | else |
269 | NameIndexOffset = ItCache->second; |
270 | } |
271 | if (!NameToUse.empty()) |
272 | NameIndexOffset = MainBinaryStrWriter.addString(Str: Name); |
273 | It.StrOffset = NameIndexOffset; |
274 | // This is the same hash function used in DWARF5AccelTableData. |
275 | It.HashValue = caseFoldingDjbHash(Buffer: Name); |
276 | } |
277 | return Name; |
278 | } |
279 | |
280 | std::optional<BOLTDWARF5AccelTableData *> DWARF5AcceleratorTable::addEntry( |
281 | DWARFUnit &DU, const DIE &CurrDie, const std::optional<uint64_t> &DWOID, |
282 | const std::optional<BOLTDWARF5AccelTableData *> &Parent, |
283 | const std::optional<std::string> &Name, |
284 | const uint32_t NumberParentsInChain) { |
285 | if (!Name) |
286 | return std::nullopt; |
287 | |
288 | auto &It = Entries[*Name]; |
289 | bool IsTU = false; |
290 | uint32_t DieTag = CurrDie.getTag(); |
291 | uint32_t UnitID = getUnitID(Unit: DU, DWOID, IsTU); |
292 | std::optional<unsigned> SecondIndex = std::nullopt; |
293 | if (IsTU && DWOID) { |
294 | auto Iter = CUOffsetsToPatch.find(Val: *DWOID); |
295 | if (Iter == CUOffsetsToPatch.end()) |
296 | BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find " |
297 | "DWO ID in CU offsets for second Unit Index " |
298 | << *Name << ". For DIE at offset: " |
299 | << Twine::utohexstr(Val: CurrentUnitOffset + CurrDie.getOffset()) |
300 | << ".\n"; |
301 | SecondIndex = Iter->second; |
302 | } |
303 | std::optional<uint64_t> ParentOffset = |
304 | (Parent ? std::optional<uint64_t>(getEntryID(Entry: **Parent)) : std::nullopt); |
305 | // This will be only populated in writeEntry, in order to keep only the parent |
306 | // entries, and keep the footprint down. |
307 | if (ParentOffset) |
308 | EntryRelativeOffsets.insert(KV: {*ParentOffset, 0}); |
309 | bool IsParentRoot = false; |
310 | // If there is no parent and no valid Entries in parent chain this is a root |
311 | // to be marked with a flag. |
312 | if (!Parent && !NumberParentsInChain) |
313 | IsParentRoot = true; |
314 | It.Values.push_back(x: new (Allocator) BOLTDWARF5AccelTableData( |
315 | CurrDie.getOffset(), ParentOffset, DieTag, UnitID, IsParentRoot, IsTU, |
316 | SecondIndex)); |
317 | return It.Values.back(); |
318 | } |
319 | |
320 | std::optional<BOLTDWARF5AccelTableData *> |
321 | DWARF5AcceleratorTable::processReferencedDie( |
322 | DWARFUnit &Unit, const DIE &Die, const std::optional<uint64_t> &DWOID, |
323 | const std::optional<BOLTDWARF5AccelTableData *> &Parent, |
324 | const std::string &NameToUse, const uint32_t NumberParentsInChain, |
325 | const dwarf::Attribute &Attr) { |
326 | DIEValue Value = Die.findAttribute(Attribute: Attr); |
327 | if (!Value) |
328 | return std::nullopt; |
329 | auto getReferenceDie = [&](const DIEValue &Value, const DIE *RefDieUsed) |
330 | -> std::optional<std::pair<DWARFUnit *, const DIE *>> { |
331 | if (!Value) |
332 | return std::nullopt; |
333 | if (Value.getForm() == dwarf::DW_FORM_ref_addr) { |
334 | auto Iter = CrossCUDies.find(Val: Value.getDIEInteger().getValue()); |
335 | if (Iter == CrossCUDies.end()) { |
336 | BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find " |
337 | "referenced DIE in CrossCUDies for " |
338 | << Twine::utohexstr(Val: Value.getDIEInteger().getValue()) |
339 | << ".\n"; |
340 | return std::nullopt; |
341 | } |
342 | return Iter->second; |
343 | } |
344 | const DIEEntry &DIEENtry = Value.getDIEEntry(); |
345 | return {{&Unit, &DIEENtry.getEntry()}}; |
346 | }; |
347 | |
348 | DIEValue AttrValLinkageName; |
349 | DIEValue AttrValName = Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_name); |
350 | DWARFUnit *RefUnit = &Unit; |
351 | const DIE *RefDieUsed = &Die; |
352 | // It is possible to have DW_TAG_subprogram only with DW_AT_linkage_name that |
353 | // DW_AT_abstract_origin/DW_AT_specification point to. |
354 | while (!AttrValName) { |
355 | std::optional<std::pair<DWARFUnit *, const DIE *>> RefDUDie = |
356 | getReferenceDie(Value, RefDieUsed); |
357 | if (!RefDUDie) |
358 | break; |
359 | RefUnit = RefDUDie->first; |
360 | const DIE &RefDie = *RefDUDie->second; |
361 | RefDieUsed = &RefDie; |
362 | if (!AttrValLinkageName) |
363 | AttrValLinkageName = |
364 | RefDie.findAttribute(Attribute: dwarf::Attribute::DW_AT_linkage_name); |
365 | AttrValName = RefDie.findAttribute(Attribute: dwarf::Attribute::DW_AT_name); |
366 | Value = RefDie.findAttribute(Attribute: dwarf::Attribute::DW_AT_abstract_origin); |
367 | if (!Value) |
368 | Value = RefDie.findAttribute(Attribute: dwarf::Attribute::DW_AT_specification); |
369 | } |
370 | addEntry(DU&: Unit, CurrDie: Die, DWOID, Parent, |
371 | Name: getName(Unit&: *RefUnit, DWOID, NameToUse, ValName: AttrValLinkageName), |
372 | NumberParentsInChain); |
373 | return addEntry(DU&: Unit, CurrDie: Die, DWOID, Parent, |
374 | Name: getName(Unit&: *RefUnit, DWOID, NameToUse, ValName: AttrValName), |
375 | NumberParentsInChain); |
376 | } |
377 | |
378 | std::optional<BOLTDWARF5AccelTableData *> |
379 | DWARF5AcceleratorTable::addAccelTableEntry( |
380 | DWARFUnit &Unit, const DIE &Die, const std::optional<uint64_t> &DWOID, |
381 | const uint32_t NumberParentsInChain, |
382 | std::optional<BOLTDWARF5AccelTableData *> &Parent) { |
383 | if (Unit.getVersion() < 5 || !NeedToCreate) |
384 | return std::nullopt; |
385 | std::string NameToUse = ""; |
386 | |
387 | if (!canProcess(Unit, Die, NameToUse, TagsOnly: false)) |
388 | return std::nullopt; |
389 | |
390 | // Adds a Unit to either CU, LocalTU or ForeignTU list the first time we |
391 | // encounter it. |
392 | // Invoking it here so that we don't add Units that don't have any entries. |
393 | if (&Unit != CurrentUnit) { |
394 | CurrentUnit = &Unit; |
395 | addUnit(Unit, DWOID); |
396 | } |
397 | |
398 | // Minor optimization not to add entry twice for DW_TAG_namespace if it has no |
399 | // DW_AT_name. |
400 | std::optional<BOLTDWARF5AccelTableData *> LinkageEntry = std::nullopt; |
401 | DIEValue NameVal = Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_name); |
402 | DIEValue LinkageNameVal = |
403 | Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_linkage_name); |
404 | if (!(Die.getTag() == dwarf::DW_TAG_namespace && !NameVal)) |
405 | LinkageEntry = addEntry(DU&: Unit, CurrDie: Die, DWOID, Parent, |
406 | Name: getName(Unit, DWOID, NameToUse, ValName: LinkageNameVal), |
407 | NumberParentsInChain); |
408 | |
409 | std::optional<BOLTDWARF5AccelTableData *> NameEntry = |
410 | addEntry(DU&: Unit, CurrDie: Die, DWOID, Parent, |
411 | Name: getName(Unit, DWOID, NameToUse, ValName: NameVal), NumberParentsInChain); |
412 | if (NameEntry) |
413 | return NameEntry; |
414 | |
415 | // The DIE doesn't have DW_AT_name or DW_AT_linkage_name, so we need to see if |
416 | // we can follow other attributes to find them. For the purposes of |
417 | // determining whether a debug information entry has a particular |
418 | // attribute (such as DW_AT_name), if debug information entry A has a |
419 | // DW_AT_specification or DW_AT_abstract_origin attribute pointing to another |
420 | // debug information entry B, any attributes of B are considered to be |
421 | // part of A. |
422 | if (std::optional<BOLTDWARF5AccelTableData *> Entry = processReferencedDie( |
423 | Unit, Die, DWOID, Parent, NameToUse, NumberParentsInChain, |
424 | Attr: dwarf::Attribute::DW_AT_abstract_origin)) |
425 | return *Entry; |
426 | if (std::optional<BOLTDWARF5AccelTableData *> Entry = processReferencedDie( |
427 | Unit, Die, DWOID, Parent, NameToUse, NumberParentsInChain, |
428 | Attr: dwarf::Attribute::DW_AT_specification)) |
429 | return *Entry; |
430 | |
431 | // This point can be hit by DW_TAG_varialbe that has no DW_AT_name. |
432 | return std::nullopt; |
433 | } |
434 | |
435 | /// Algorithm from llvm implementation. |
436 | void DWARF5AcceleratorTable::computeBucketCount() { |
437 | // First get the number of unique hashes. |
438 | std::vector<uint32_t> Uniques; |
439 | Uniques.reserve(n: Entries.size()); |
440 | for (const auto &E : Entries) |
441 | Uniques.push_back(x: E.second.HashValue); |
442 | array_pod_sort(Start: Uniques.begin(), End: Uniques.end()); |
443 | std::vector<uint32_t>::iterator P = llvm::unique(R&: Uniques); |
444 | |
445 | UniqueHashCount = std::distance(first: Uniques.begin(), last: P); |
446 | |
447 | if (UniqueHashCount > 1024) |
448 | BucketCount = UniqueHashCount / 4; |
449 | else if (UniqueHashCount > 16) |
450 | BucketCount = UniqueHashCount / 2; |
451 | else |
452 | BucketCount = std::max<uint32_t>(a: UniqueHashCount, b: 1); |
453 | } |
454 | |
455 | /// Bucket code as in: AccelTableBase::finalize() |
456 | void DWARF5AcceleratorTable::finalize() { |
457 | if (!NeedToCreate) |
458 | return; |
459 | // Figure out how many buckets we need, then compute the bucket contents and |
460 | // the final ordering. The hashes and offsets can be emitted by walking these |
461 | // data structures. |
462 | computeBucketCount(); |
463 | |
464 | // Compute bucket contents and final ordering. |
465 | Buckets.resize(new_size: BucketCount); |
466 | for (auto &E : Entries) { |
467 | uint32_t Bucket = E.second.HashValue % BucketCount; |
468 | Buckets[Bucket].push_back(x: &E.second); |
469 | } |
470 | |
471 | // Sort the contents of the buckets by hash value so that hash collisions end |
472 | // up together. Stable sort makes testing easier and doesn't cost much more. |
473 | for (HashList &Bucket : Buckets) { |
474 | llvm::stable_sort(Range&: Bucket, C: [](const HashData *LHS, const HashData *RHS) { |
475 | return LHS->HashValue < RHS->HashValue; |
476 | }); |
477 | for (HashData *H : Bucket) |
478 | llvm::stable_sort(Range&: H->Values, C: [](const BOLTDWARF5AccelTableData *LHS, |
479 | const BOLTDWARF5AccelTableData *RHS) { |
480 | return LHS->getDieOffset() < RHS->getDieOffset(); |
481 | }); |
482 | } |
483 | |
484 | CUIndexForm = DIEInteger::BestForm(/*IsSigned*/ false, Int: CUList.size() - 1); |
485 | TUIndexForm = DIEInteger::BestForm( |
486 | /*IsSigned*/ false, Int: LocalTUList.size() + ForeignTUList.size() - 1); |
487 | const dwarf::FormParams FormParams{.Version: 5, .AddrSize: 4, .Format: dwarf::DwarfFormat::DWARF32, .DwarfUsesRelocationsAcrossSections: false}; |
488 | CUIndexEncodingSize = *dwarf::getFixedFormByteSize(Form: CUIndexForm, Params: FormParams); |
489 | TUIndexEncodingSize = *dwarf::getFixedFormByteSize(Form: TUIndexForm, Params: FormParams); |
490 | } |
491 | |
492 | std::optional<DWARF5AccelTable::UnitIndexAndEncoding> |
493 | DWARF5AcceleratorTable::getIndexForEntry( |
494 | const BOLTDWARF5AccelTableData &Value) const { |
495 | // The foreign TU list immediately follows the local TU list and they both |
496 | // use the same index, so that if there are N local TU entries, the index for |
497 | // the first foreign TU is N. |
498 | if (Value.isTU()) |
499 | return {{.Index: (Value.getSecondUnitID() ? (unsigned)LocalTUList.size() : 0) + |
500 | Value.getUnitID(), |
501 | .Encoding: {.Index: dwarf::DW_IDX_type_unit, .Form: TUIndexForm}}}; |
502 | if (CUList.size() > 1) |
503 | return {{.Index: Value.getUnitID(), .Encoding: {.Index: dwarf::DW_IDX_compile_unit, .Form: CUIndexForm}}}; |
504 | return std::nullopt; |
505 | } |
506 | |
507 | std::optional<DWARF5AccelTable::UnitIndexAndEncoding> |
508 | DWARF5AcceleratorTable::getSecondIndexForEntry( |
509 | const BOLTDWARF5AccelTableData &Value) const { |
510 | if (Value.isTU() && CUList.size() > 1 && Value.getSecondUnitID()) |
511 | return { |
512 | {.Index: *Value.getSecondUnitID(), .Encoding: {.Index: dwarf::DW_IDX_compile_unit, .Form: CUIndexForm}}}; |
513 | return std::nullopt; |
514 | } |
515 | |
516 | void DWARF5AcceleratorTable::populateAbbrevsMap() { |
517 | for (auto &Bucket : getBuckets()) { |
518 | for (DWARF5AcceleratorTable::HashData *Hash : Bucket) { |
519 | for (BOLTDWARF5AccelTableData *Value : Hash->Values) { |
520 | const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet = |
521 | getIndexForEntry(Value: *Value); |
522 | // For entries that need to refer to the foreign type units and to |
523 | // the CU. |
524 | const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> |
525 | SecondEntryRet = getSecondIndexForEntry(Value: *Value); |
526 | DebugNamesAbbrev Abbrev(Value->getDieTag()); |
527 | if (EntryRet) |
528 | Abbrev.addAttribute(Attr: EntryRet->Encoding); |
529 | if (SecondEntryRet) |
530 | Abbrev.addAttribute(Attr: SecondEntryRet->Encoding); |
531 | Abbrev.addAttribute(Attr: {.Index: dwarf::DW_IDX_die_offset, .Form: dwarf::DW_FORM_ref4}); |
532 | if (std::optional<uint64_t> Offset = Value->getParentDieOffset()) |
533 | Abbrev.addAttribute(Attr: {.Index: dwarf::DW_IDX_parent, .Form: dwarf::DW_FORM_ref4}); |
534 | else if (Value->isParentRoot()) |
535 | Abbrev.addAttribute( |
536 | Attr: {.Index: dwarf::DW_IDX_parent, .Form: dwarf::DW_FORM_flag_present}); |
537 | FoldingSetNodeID ID; |
538 | Abbrev.Profile(ID); |
539 | void *InsertPos; |
540 | if (DebugNamesAbbrev *Existing = |
541 | AbbreviationsSet.FindNodeOrInsertPos(ID, InsertPos)) { |
542 | Value->setAbbrevNumber(Existing->getNumber()); |
543 | continue; |
544 | } |
545 | DebugNamesAbbrev *NewAbbrev = |
546 | new (Alloc) DebugNamesAbbrev(std::move(Abbrev)); |
547 | AbbreviationsVector.push_back(Elt: NewAbbrev); |
548 | NewAbbrev->setNumber(AbbreviationsVector.size()); |
549 | AbbreviationsSet.InsertNode(N: NewAbbrev, InsertPos); |
550 | Value->setAbbrevNumber(NewAbbrev->getNumber()); |
551 | } |
552 | } |
553 | } |
554 | } |
555 | |
556 | void DWARF5AcceleratorTable::writeEntry(BOLTDWARF5AccelTableData &Entry) { |
557 | const uint64_t EntryID = getEntryID(Entry); |
558 | if (EntryRelativeOffsets.find(Val: EntryID) != EntryRelativeOffsets.end()) |
559 | EntryRelativeOffsets[EntryID] = EntriesBuffer->size(); |
560 | |
561 | const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet = |
562 | getIndexForEntry(Value: Entry); |
563 | // For forgeign type (FTU) units that need to refer to the FTU and to the CU. |
564 | const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> SecondEntryRet = |
565 | getSecondIndexForEntry(Value: Entry); |
566 | const unsigned AbbrevIndex = Entry.getAbbrevNumber() - 1; |
567 | assert(AbbrevIndex < AbbreviationsVector.size() && |
568 | "Entry abbrev index is outside of abbreviations vector range."); |
569 | const DebugNamesAbbrev *Abbrev = AbbreviationsVector[AbbrevIndex]; |
570 | encodeULEB128(Value: Entry.getAbbrevNumber(), OS&: *Entriestream); |
571 | auto writeIndex = [&](uint32_t Index, uint32_t IndexSize) -> void { |
572 | switch (IndexSize) { |
573 | default: |
574 | llvm_unreachable("Unsupported Index Size!"); |
575 | break; |
576 | case 1: |
577 | support::endian::write(os&: *Entriestream, value: static_cast<uint8_t>(Index), |
578 | endian: llvm::endianness::little); |
579 | break; |
580 | case 2: |
581 | support::endian::write(os&: *Entriestream, value: static_cast<uint16_t>(Index), |
582 | endian: llvm::endianness::little); |
583 | break; |
584 | case 4: |
585 | support::endian::write(os&: *Entriestream, value: static_cast<uint32_t>(Index), |
586 | endian: llvm::endianness::little); |
587 | break; |
588 | }; |
589 | }; |
590 | |
591 | for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc : |
592 | Abbrev->getAttributes()) { |
593 | switch (AttrEnc.Index) { |
594 | default: { |
595 | llvm_unreachable("Unexpected index attribute!"); |
596 | break; |
597 | } |
598 | case dwarf::DW_IDX_compile_unit: { |
599 | const unsigned CUIndex = |
600 | SecondEntryRet ? SecondEntryRet->Index : EntryRet->Index; |
601 | writeIndex(CUIndex, CUIndexEncodingSize); |
602 | break; |
603 | } |
604 | case dwarf::DW_IDX_type_unit: { |
605 | writeIndex(EntryRet->Index, TUIndexEncodingSize); |
606 | break; |
607 | } |
608 | case dwarf::DW_IDX_die_offset: { |
609 | assert(AttrEnc.Form == dwarf::DW_FORM_ref4); |
610 | support::endian::write(os&: *Entriestream, |
611 | value: static_cast<uint32_t>(Entry.getDieOffset()), |
612 | endian: llvm::endianness::little); |
613 | break; |
614 | } |
615 | case dwarf::DW_IDX_parent: { |
616 | assert( |
617 | (AttrEnc.Form == dwarf::DW_FORM_ref4 && Entry.getParentDieOffset()) || |
618 | AttrEnc.Form == dwarf::DW_FORM_flag_present); |
619 | if (std::optional<uint64_t> ParentOffset = Entry.getParentDieOffset()) { |
620 | Entry.setPatchOffset(EntriesBuffer->size()); |
621 | support::endian::write(os&: *Entriestream, value: static_cast<uint32_t>(UINT32_MAX), |
622 | endian: llvm::endianness::little); |
623 | } |
624 | break; |
625 | } |
626 | } |
627 | } |
628 | } |
629 | |
630 | void DWARF5AcceleratorTable::writeEntries() { |
631 | for (auto &Bucket : getBuckets()) { |
632 | for (DWARF5AcceleratorTable::HashData *Hash : Bucket) { |
633 | Hash->EntryOffset = EntriesBuffer->size(); |
634 | for (BOLTDWARF5AccelTableData *Value : Hash->Values) { |
635 | writeEntry(Entry&: *Value); |
636 | } |
637 | support::endian::write(os&: *Entriestream, value: static_cast<uint8_t>(0), |
638 | endian: llvm::endianness::little); |
639 | } |
640 | } |
641 | // Patching parent offsets. |
642 | for (auto &Bucket : getBuckets()) { |
643 | for (DWARF5AcceleratorTable::HashData *Hash : Bucket) { |
644 | for (BOLTDWARF5AccelTableData *Entry : Hash->Values) { |
645 | std::optional<uint64_t> ParentOffset = Entry->getParentDieOffset(); |
646 | if (!ParentOffset) |
647 | continue; |
648 | if (const auto Iter = EntryRelativeOffsets.find(Val: *ParentOffset); |
649 | Iter != EntryRelativeOffsets.end()) { |
650 | const uint64_t PatchOffset = Entry->getPatchOffset(); |
651 | uint32_t *Ptr = |
652 | reinterpret_cast<uint32_t *>(&EntriesBuffer->data()[PatchOffset]); |
653 | *Ptr = Iter->second; |
654 | } else { |
655 | BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find " |
656 | "entry with offset " |
657 | << *ParentOffset << "\n"; |
658 | } |
659 | } |
660 | } |
661 | } |
662 | } |
663 | |
664 | void DWARF5AcceleratorTable::writeAugmentationString() { |
665 | // String needs to be multiple of 4 bytes. |
666 | *AugStringtream << "BOLT"; |
667 | AugmentationStringSize = AugStringBuffer->size(); |
668 | } |
669 | |
670 | /// Calculates size of .debug_names header without Length field. |
671 | static constexpr uint32_t getDebugNamesHeaderSize() { |
672 | constexpr uint16_t VersionLength = sizeof(uint16_t); |
673 | constexpr uint16_t PaddingLength = sizeof(uint16_t); |
674 | constexpr uint32_t CompUnitCountLength = sizeof(uint32_t); |
675 | constexpr uint32_t LocalTypeUnitCountLength = sizeof(uint32_t); |
676 | constexpr uint32_t ForeignTypeUnitCountLength = sizeof(uint32_t); |
677 | constexpr uint32_t BucketCountLength = sizeof(uint32_t); |
678 | constexpr uint32_t NameCountLength = sizeof(uint32_t); |
679 | constexpr uint32_t AbbrevTableSizeLength = sizeof(uint32_t); |
680 | constexpr uint32_t AugmentationStringSizeLenght = sizeof(uint32_t); |
681 | return VersionLength + PaddingLength + CompUnitCountLength + |
682 | LocalTypeUnitCountLength + ForeignTypeUnitCountLength + |
683 | BucketCountLength + NameCountLength + AbbrevTableSizeLength + |
684 | AugmentationStringSizeLenght; |
685 | } |
686 | |
687 | void DWARF5AcceleratorTable::emitHeader() const { |
688 | constexpr uint32_t HeaderSize = getDebugNamesHeaderSize(); |
689 | // Header Length |
690 | support::endian::write(os&: *FullTableStream, |
691 | value: static_cast<uint32_t>(HeaderSize + StrBuffer->size() + |
692 | AugmentationStringSize), |
693 | endian: llvm::endianness::little); |
694 | // Version |
695 | support::endian::write(os&: *FullTableStream, value: static_cast<uint16_t>(5), |
696 | endian: llvm::endianness::little); |
697 | // Padding |
698 | support::endian::write(os&: *FullTableStream, value: static_cast<uint16_t>(0), |
699 | endian: llvm::endianness::little); |
700 | // Compilation Unit Count |
701 | support::endian::write(os&: *FullTableStream, value: static_cast<uint32_t>(CUList.size()), |
702 | endian: llvm::endianness::little); |
703 | // Local Type Unit Count |
704 | support::endian::write(os&: *FullTableStream, |
705 | value: static_cast<uint32_t>(LocalTUList.size()), |
706 | endian: llvm::endianness::little); |
707 | // Foreign Type Unit Count |
708 | support::endian::write(os&: *FullTableStream, |
709 | value: static_cast<uint32_t>(ForeignTUList.size()), |
710 | endian: llvm::endianness::little); |
711 | // Bucket Count |
712 | support::endian::write(os&: *FullTableStream, value: static_cast<uint32_t>(BucketCount), |
713 | endian: llvm::endianness::little); |
714 | // Name Count |
715 | support::endian::write(os&: *FullTableStream, |
716 | value: static_cast<uint32_t>(Entries.size()), |
717 | endian: llvm::endianness::little); |
718 | // Abbrev Table Size |
719 | support::endian::write(os&: *FullTableStream, |
720 | value: static_cast<uint32_t>(AbbrevTableSize), |
721 | endian: llvm::endianness::little); |
722 | // Augmentation String Size |
723 | support::endian::write(os&: *FullTableStream, |
724 | value: static_cast<uint32_t>(AugmentationStringSize), |
725 | endian: llvm::endianness::little); |
726 | |
727 | emitAugmentationString(); |
728 | FullTableStream->write(Ptr: StrBuffer->data(), Size: StrBuffer->size()); |
729 | } |
730 | |
731 | void DWARF5AcceleratorTable::emitCUList() const { |
732 | for (const uint32_t CUID : CUList) |
733 | support::endian::write(os&: *StrStream, value: CUID, endian: llvm::endianness::little); |
734 | } |
735 | void DWARF5AcceleratorTable::emitTUList() const { |
736 | for (const uint32_t TUID : LocalTUList) |
737 | support::endian::write(os&: *StrStream, value: TUID, endian: llvm::endianness::little); |
738 | |
739 | for (const uint64_t TUID : ForeignTUList) |
740 | support::endian::write(os&: *StrStream, value: TUID, endian: llvm::endianness::little); |
741 | } |
742 | void DWARF5AcceleratorTable::emitBuckets() const { |
743 | uint32_t Index = 1; |
744 | for (const auto &Bucket : enumerate(First: getBuckets())) { |
745 | const uint32_t TempIndex = Bucket.value().empty() ? 0 : Index; |
746 | support::endian::write(os&: *StrStream, value: TempIndex, endian: llvm::endianness::little); |
747 | Index += Bucket.value().size(); |
748 | } |
749 | } |
750 | void DWARF5AcceleratorTable::emitHashes() const { |
751 | for (const auto &Bucket : getBuckets()) { |
752 | for (const DWARF5AcceleratorTable::HashData *Hash : Bucket) |
753 | support::endian::write(os&: *StrStream, value: Hash->HashValue, |
754 | endian: llvm::endianness::little); |
755 | } |
756 | } |
757 | void DWARF5AcceleratorTable::emitStringOffsets() const { |
758 | for (const auto &Bucket : getBuckets()) { |
759 | for (const DWARF5AcceleratorTable::HashData *Hash : Bucket) |
760 | support::endian::write(os&: *StrStream, value: static_cast<uint32_t>(Hash->StrOffset), |
761 | endian: llvm::endianness::little); |
762 | } |
763 | } |
764 | void DWARF5AcceleratorTable::emitOffsets() const { |
765 | for (const auto &Bucket : getBuckets()) { |
766 | for (const DWARF5AcceleratorTable::HashData *Hash : Bucket) |
767 | support::endian::write(os&: *StrStream, |
768 | value: static_cast<uint32_t>(Hash->EntryOffset), |
769 | endian: llvm::endianness::little); |
770 | } |
771 | } |
772 | void DWARF5AcceleratorTable::emitAbbrevs() { |
773 | const uint32_t AbbrevTableStart = StrBuffer->size(); |
774 | for (const auto *Abbrev : AbbreviationsVector) { |
775 | encodeULEB128(Value: Abbrev->getNumber(), OS&: *StrStream); |
776 | encodeULEB128(Value: Abbrev->getDieTag(), OS&: *StrStream); |
777 | for (const auto &AttrEnc : Abbrev->getAttributes()) { |
778 | encodeULEB128(Value: AttrEnc.Index, OS&: *StrStream); |
779 | encodeULEB128(Value: AttrEnc.Form, OS&: *StrStream); |
780 | } |
781 | encodeULEB128(Value: 0, OS&: *StrStream); |
782 | encodeULEB128(Value: 0, OS&: *StrStream); |
783 | } |
784 | encodeULEB128(Value: 0, OS&: *StrStream); |
785 | AbbrevTableSize = StrBuffer->size() - AbbrevTableStart; |
786 | } |
787 | void DWARF5AcceleratorTable::emitData() { |
788 | StrStream->write(Ptr: EntriesBuffer->data(), Size: EntriesBuffer->size()); |
789 | } |
790 | void DWARF5AcceleratorTable::emitAugmentationString() const { |
791 | FullTableStream->write(Ptr: AugStringBuffer->data(), Size: AugStringBuffer->size()); |
792 | } |
793 | void DWARF5AcceleratorTable::emitAccelTable() { |
794 | if (!NeedToCreate) |
795 | return; |
796 | finalize(); |
797 | populateAbbrevsMap(); |
798 | writeEntries(); |
799 | writeAugmentationString(); |
800 | emitCUList(); |
801 | emitTUList(); |
802 | emitBuckets(); |
803 | emitHashes(); |
804 | emitStringOffsets(); |
805 | emitOffsets(); |
806 | emitAbbrevs(); |
807 | emitData(); |
808 | emitHeader(); |
809 | } |
810 | } // namespace bolt |
811 | } // namespace llvm |
812 |
Definitions
- DWARF5AcceleratorTable
- setCurrentUnit
- addUnit
- shouldIncludeVariable
- canProcess
- canGenerateEntryWithCrossCUReference
- getNameOffset
- getEntryID
- getUnitID
- getName
- addEntry
- processReferencedDie
- addAccelTableEntry
- computeBucketCount
- finalize
- getIndexForEntry
- getSecondIndexForEntry
- populateAbbrevsMap
- writeEntry
- writeEntries
- writeAugmentationString
- getDebugNamesHeaderSize
- emitHeader
- emitCUList
- emitTUList
- emitBuckets
- emitHashes
- emitStringOffsets
- emitOffsets
- emitAbbrevs
- emitData
- emitAugmentationString
Learn to use CMake with our Intro Training
Find out more