1 //===- DWARFLinkerTypeUnit.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 "DWARFLinkerTypeUnit.h"
10 #include "DIEGenerator.h"
11 #include "DWARFEmitterImpl.h"
12 #include "llvm/Support/LEB128.h"
13 
14 using namespace llvm;
15 using namespace dwarf_linker;
16 using namespace dwarf_linker::parallel;
17 
18 TypeUnit::TypeUnit(LinkingGlobalData &GlobalData, unsigned ID,
19                    std::optional<uint16_t> Language, dwarf::FormParams Format,
20                    endianness Endianess)
21     : DwarfUnit(GlobalData, ID, ""), Language(Language),
22       AcceleratorRecords(&GlobalData.getAllocator()) {
23 
24   UnitName = "__artificial_type_unit";
25 
26   setOutputFormat(Format, Endianess);
27 
28   // Create line table prologue.
29   LineTable.Prologue.FormParams = getFormParams();
30   LineTable.Prologue.MinInstLength = 1;
31   LineTable.Prologue.MaxOpsPerInst = 1;
32   LineTable.Prologue.DefaultIsStmt = 1;
33   LineTable.Prologue.LineBase = -5;
34   LineTable.Prologue.LineRange = 14;
35   LineTable.Prologue.OpcodeBase = 13;
36   LineTable.Prologue.StandardOpcodeLengths = {0, 1, 1, 1, 1, 0,
37                                               0, 0, 1, 0, 0, 1};
38 
39   getOrCreateSectionDescriptor(DebugSectionKind::DebugInfo);
40 }
41 
42 void TypeUnit::createDIETree(BumpPtrAllocator &Allocator) {
43   prepareDataForTreeCreation();
44 
45   // TaskGroup is created here as internal code has calls to
46   // PerThreadBumpPtrAllocator which should be called from the task group task.
47   llvm::parallel::TaskGroup TG;
48   TG.spawn([&]() {
49     SectionDescriptor &DebugInfoSection =
50         getOrCreateSectionDescriptor(DebugSectionKind::DebugInfo);
51     SectionDescriptor &DebugLineSection =
52         getOrCreateSectionDescriptor(DebugSectionKind::DebugLine);
53 
54     DIEGenerator DIETreeGenerator(Allocator, *this);
55     OffsetsPtrVector PatchesOffsets;
56 
57     // Create a Die for artificial compilation unit for types.
58     DIE *UnitDIE = DIETreeGenerator.createDIE(dwarf::DW_TAG_compile_unit, 0);
59     uint64_t OutOffset = getDebugInfoHeaderSize();
60     UnitDIE->setOffset(OutOffset);
61 
62     SmallString<200> ProducerString;
63     ProducerString += "llvm DWARFLinkerParallel library version ";
64     DebugInfoSection.notePatchWithOffsetUpdate(
65         DebugStrPatch{
66             {OutOffset},
67             GlobalData.getStringPool().insert(ProducerString.str()).first},
68         PatchesOffsets);
69     OutOffset += DIETreeGenerator
70                      .addStringPlaceholderAttribute(dwarf::DW_AT_producer,
71                                                     dwarf::DW_FORM_strp)
72                      .second;
73 
74     if (Language) {
75       OutOffset += DIETreeGenerator
76                        .addScalarAttribute(dwarf::DW_AT_language,
77                                            dwarf::DW_FORM_data2, *Language)
78                        .second;
79     }
80 
81     DebugInfoSection.notePatchWithOffsetUpdate(
82         DebugStrPatch{{OutOffset},
83                       GlobalData.getStringPool().insert(getUnitName()).first},
84         PatchesOffsets);
85     OutOffset += DIETreeGenerator
86                      .addStringPlaceholderAttribute(dwarf::DW_AT_name,
87                                                     dwarf::DW_FORM_strp)
88                      .second;
89 
90     if (!LineTable.Prologue.FileNames.empty()) {
91       DebugInfoSection.notePatchWithOffsetUpdate(
92           DebugOffsetPatch{OutOffset, &DebugLineSection}, PatchesOffsets);
93 
94       OutOffset += DIETreeGenerator
95                        .addScalarAttribute(dwarf::DW_AT_stmt_list,
96                                            dwarf::DW_FORM_sec_offset, 0xbaddef)
97                        .second;
98     }
99 
100     DebugInfoSection.notePatchWithOffsetUpdate(
101         DebugStrPatch{{OutOffset}, GlobalData.getStringPool().insert("").first},
102         PatchesOffsets);
103     OutOffset += DIETreeGenerator
104                      .addStringPlaceholderAttribute(dwarf::DW_AT_comp_dir,
105                                                     dwarf::DW_FORM_strp)
106                      .second;
107 
108     if (!DebugStringIndexMap.empty()) {
109       // Type unit is assumed to be emitted first. Thus we can use direct value
110       // for DW_AT_str_offsets_base attribute(No need to fix it up with unit
111       // offset value).
112       OutOffset += DIETreeGenerator
113                        .addScalarAttribute(dwarf::DW_AT_str_offsets_base,
114                                            dwarf::DW_FORM_sec_offset,
115                                            getDebugStrOffsetsHeaderSize())
116                        .second;
117     }
118 
119     UnitDIE->setSize(OutOffset - UnitDIE->getOffset() + 1);
120     OutOffset =
121         finalizeTypeEntryRec(UnitDIE->getOffset(), UnitDIE, Types.getRoot());
122 
123     // Update patch offsets.
124     for (uint64_t *OffsetPtr : PatchesOffsets)
125       *OffsetPtr += getULEB128Size(UnitDIE->getAbbrevNumber());
126 
127     setOutUnitDIE(UnitDIE);
128   });
129 }
130 
131 void TypeUnit::prepareDataForTreeCreation() {
132   SectionDescriptor &DebugInfoSection =
133       getOrCreateSectionDescriptor(DebugSectionKind::DebugInfo);
134 
135   // Type unit data created parallelly. So the order of data is not
136   // deterministic. Order data here if we need deterministic output.
137 
138   llvm::parallel::TaskGroup TG;
139 
140   if (!GlobalData.getOptions().AllowNonDeterministicOutput) {
141     TG.spawn([&]() {
142       // Sort types to have a deterministic output.
143       Types.sortTypes();
144     });
145   }
146 
147   TG.spawn([&]() {
148     if (!GlobalData.getOptions().AllowNonDeterministicOutput) {
149       // Sort decl type patches to have a deterministic output.
150       std::function<bool(const DebugTypeDeclFilePatch &LHS,
151                          const DebugTypeDeclFilePatch &RHS)>
152           PatchesComparator = [&](const DebugTypeDeclFilePatch &LHS,
153                                   const DebugTypeDeclFilePatch &RHS) {
154             return LHS.Directory->first() < RHS.Directory->first() ||
155                    (!(RHS.Directory->first() < LHS.Directory->first()) &&
156                     LHS.FilePath->first() < RHS.FilePath->first());
157           };
158       // Sort patches to have a deterministic output.
159       DebugInfoSection.ListDebugTypeDeclFilePatch.sort(PatchesComparator);
160     }
161 
162     // Update DW_AT_decl_file attribute
163     dwarf::Form DeclFileForm =
164         getScalarFormForValue(
165             DebugInfoSection.ListDebugTypeDeclFilePatch.size())
166             .first;
167 
168     DebugInfoSection.ListDebugTypeDeclFilePatch.forEach(
169         [&](DebugTypeDeclFilePatch &Patch) {
170           TypeEntryBody *TypeEntry = Patch.TypeName->getValue().load();
171           assert(TypeEntry &&
172                  formatv("No data for type {0}", Patch.TypeName->getKey())
173                      .str()
174                      .c_str());
175           if (&TypeEntry->getFinalDie() != Patch.Die)
176             return;
177 
178           uint32_t FileIdx =
179               addFileNameIntoLinetable(Patch.Directory, Patch.FilePath);
180 
181           unsigned DIESize = Patch.Die->getSize();
182           DIEGenerator DIEGen(Patch.Die, Types.getThreadLocalAllocator(),
183                               *this);
184 
185           DIESize += DIEGen
186                          .addScalarAttribute(dwarf::DW_AT_decl_file,
187                                              DeclFileForm, FileIdx)
188                          .second;
189           Patch.Die->setSize(DIESize);
190         });
191   });
192 
193   if (!GlobalData.getOptions().AllowNonDeterministicOutput) {
194     // Sort patches to have a deterministic output.
195     TG.spawn([&]() {
196       forEach([&](SectionDescriptor &OutSection) {
197         std::function<bool(const DebugStrPatch &LHS, const DebugStrPatch &RHS)>
198             StrPatchesComparator =
199                 [&](const DebugStrPatch &LHS, const DebugStrPatch &RHS) {
200                   return LHS.String->getKey() < RHS.String->getKey();
201                 };
202         OutSection.ListDebugStrPatch.sort(StrPatchesComparator);
203 
204         std::function<bool(const DebugTypeStrPatch &LHS,
205                            const DebugTypeStrPatch &RHS)>
206             TypeStrPatchesComparator = [&](const DebugTypeStrPatch &LHS,
207                                            const DebugTypeStrPatch &RHS) {
208               return LHS.String->getKey() < RHS.String->getKey();
209             };
210         OutSection.ListDebugTypeStrPatch.sort(TypeStrPatchesComparator);
211       });
212     });
213   }
214 
215   if (!GlobalData.getOptions().AllowNonDeterministicOutput) {
216     // Sort patches to have a deterministic output.
217     TG.spawn([&]() {
218       forEach([&](SectionDescriptor &OutSection) {
219         std::function<bool(const DebugLineStrPatch &LHS,
220                            const DebugLineStrPatch &RHS)>
221             LineStrPatchesComparator = [&](const DebugLineStrPatch &LHS,
222                                            const DebugLineStrPatch &RHS) {
223               return LHS.String->getKey() < RHS.String->getKey();
224             };
225         OutSection.ListDebugLineStrPatch.sort(LineStrPatchesComparator);
226 
227         std::function<bool(const DebugTypeLineStrPatch &LHS,
228                            const DebugTypeLineStrPatch &RHS)>
229             TypeLineStrPatchesComparator =
230                 [&](const DebugTypeLineStrPatch &LHS,
231                     const DebugTypeLineStrPatch &RHS) {
232                   return LHS.String->getKey() < RHS.String->getKey();
233                 };
234         OutSection.ListDebugTypeLineStrPatch.sort(TypeLineStrPatchesComparator);
235       });
236     });
237   }
238 }
239 
240 uint64_t TypeUnit::finalizeTypeEntryRec(uint64_t OutOffset, DIE *OutDIE,
241                                         TypeEntry *Entry) {
242   bool HasChildren = !Entry->getValue().load()->Children.empty();
243   DIEGenerator DIEGen(OutDIE, Types.getThreadLocalAllocator(), *this);
244   OutOffset += DIEGen.finalizeAbbreviations(HasChildren, nullptr);
245   OutOffset += OutDIE->getSize() - 1;
246 
247   if (HasChildren) {
248     Entry->getValue().load()->Children.forEach([&](TypeEntry *ChildEntry) {
249       DIE *ChildDIE = &ChildEntry->getValue().load()->getFinalDie();
250       DIEGen.addChild(ChildDIE);
251 
252       ChildDIE->setOffset(OutOffset);
253 
254       OutOffset = finalizeTypeEntryRec(OutOffset, ChildDIE, ChildEntry);
255     });
256 
257     // End of children marker.
258     OutOffset += sizeof(int8_t);
259   }
260 
261   OutDIE->setSize(OutOffset - OutDIE->getOffset());
262   return OutOffset;
263 }
264 
265 uint32_t TypeUnit::addFileNameIntoLinetable(StringEntry *Dir,
266                                             StringEntry *FileName) {
267   uint32_t DirIdx = 0;
268 
269   if (Dir->first() == "") {
270     DirIdx = 0;
271   } else {
272     DirectoriesMapTy::iterator DirEntry = DirectoriesMap.find(Dir);
273     if (DirEntry == DirectoriesMap.end()) {
274       // We currently do not support more than UINT32_MAX directories.
275       assert(LineTable.Prologue.IncludeDirectories.size() < UINT32_MAX);
276       DirIdx = LineTable.Prologue.IncludeDirectories.size();
277       DirectoriesMap.insert({Dir, DirIdx});
278       LineTable.Prologue.IncludeDirectories.push_back(
279           DWARFFormValue::createFromPValue(dwarf::DW_FORM_string,
280                                            Dir->getKeyData()));
281     } else {
282       DirIdx = DirEntry->second;
283     }
284 
285     if (getVersion() < 5)
286       DirIdx++;
287   }
288 
289   uint32_t FileIdx = 0;
290   FilenamesMapTy::iterator FileEntry = FileNamesMap.find({FileName, DirIdx});
291   if (FileEntry == FileNamesMap.end()) {
292     // We currently do not support more than UINT32_MAX files.
293     assert(LineTable.Prologue.FileNames.size() < UINT32_MAX);
294     FileIdx = LineTable.Prologue.FileNames.size();
295     FileNamesMap.insert({{FileName, DirIdx}, FileIdx});
296     LineTable.Prologue.FileNames.push_back(DWARFDebugLine::FileNameEntry());
297     LineTable.Prologue.FileNames.back().Name = DWARFFormValue::createFromPValue(
298         dwarf::DW_FORM_string, FileName->getKeyData());
299     LineTable.Prologue.FileNames.back().DirIdx = DirIdx;
300   } else {
301     FileIdx = FileEntry->second;
302   }
303 
304   return getVersion() < 5 ? FileIdx + 1 : FileIdx;
305 }
306 
307 std::pair<dwarf::Form, uint8_t>
308 TypeUnit::getScalarFormForValue(uint64_t Value) const {
309   if (Value > 0xFFFFFFFF)
310     return std::make_pair(dwarf::DW_FORM_data8, 8);
311 
312   if (Value > 0xFFFF)
313     return std::make_pair(dwarf::DW_FORM_data4, 4);
314 
315   if (Value > 0xFF)
316     return std::make_pair(dwarf::DW_FORM_data2, 2);
317 
318   return std::make_pair(dwarf::DW_FORM_data1, 1);
319 }
320 
321 uint8_t TypeUnit::getSizeByAttrForm(dwarf::Form Form) const {
322   if (Form == dwarf::DW_FORM_data1)
323     return 1;
324 
325   if (Form == dwarf::DW_FORM_data2)
326     return 2;
327 
328   if (Form == dwarf::DW_FORM_data4)
329     return 4;
330 
331   if (Form == dwarf::DW_FORM_data8)
332     return 8;
333 
334   if (Form == dwarf::DW_FORM_data16)
335     return 16;
336 
337   llvm_unreachable("Unsupported Attr Form");
338 }
339 
340 Error TypeUnit::finishCloningAndEmit(const Triple &TargetTriple) {
341   BumpPtrAllocator Allocator;
342   createDIETree(Allocator);
343 
344   if (getOutUnitDIE() == nullptr)
345     return Error::success();
346 
347   // Create sections ahead so that they should not be created asynchronously
348   // later.
349   getOrCreateSectionDescriptor(DebugSectionKind::DebugInfo);
350   getOrCreateSectionDescriptor(DebugSectionKind::DebugLine);
351   getOrCreateSectionDescriptor(DebugSectionKind::DebugStrOffsets);
352   getOrCreateSectionDescriptor(DebugSectionKind::DebugAbbrev);
353   if (llvm::is_contained(GlobalData.getOptions().AccelTables,
354                          DWARFLinker::AccelTableKind::Pub)) {
355     getOrCreateSectionDescriptor(DebugSectionKind::DebugPubNames);
356     getOrCreateSectionDescriptor(DebugSectionKind::DebugPubTypes);
357   }
358 
359   SmallVector<std::function<Error(void)>> Tasks;
360 
361   // Add task for emitting .debug_line section.
362   if (!LineTable.Prologue.FileNames.empty()) {
363     Tasks.push_back(
364         [&]() -> Error { return emitDebugLine(TargetTriple, LineTable); });
365   }
366 
367   // Add task for emitting .debug_info section.
368   Tasks.push_back([&]() -> Error { return emitDebugInfo(TargetTriple); });
369 
370   // Add task for emitting Pub accelerator sections.
371   if (llvm::is_contained(GlobalData.getOptions().AccelTables,
372                          DWARFLinker::AccelTableKind::Pub)) {
373     Tasks.push_back([&]() -> Error {
374       emitPubAccelerators();
375       return Error::success();
376     });
377   }
378 
379   // Add task for emitting .debug_str_offsets section.
380   Tasks.push_back([&]() -> Error { return emitDebugStringOffsetSection(); });
381 
382   // Add task for emitting .debug_abbr section.
383   Tasks.push_back([&]() -> Error { return emitAbbreviations(); });
384 
385   if (auto Err = parallelForEachError(
386           Tasks, [&](std::function<Error(void)> F) { return F(); }))
387     return Err;
388 
389   return Error::success();
390 }
391