xref: /llvm-project/llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp (revision 55fcd07d25123f52f6f0b220c99a3f8216dc8652)
1 //===- llvm/CodeGen/AsmPrinter/AccelTable.cpp - Accelerator Tables --------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains support for writing accelerator tables.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/CodeGen/AccelTable.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/StringMap.h"
17 #include "llvm/ADT/Twine.h"
18 #include "llvm/BinaryFormat/Dwarf.h"
19 #include "llvm/CodeGen/AsmPrinter.h"
20 #include "llvm/CodeGen/DIE.h"
21 #include "llvm/MC/MCExpr.h"
22 #include "llvm/MC/MCStreamer.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <algorithm>
25 #include <cstddef>
26 #include <cstdint>
27 #include <limits>
28 #include <vector>
29 
30 using namespace llvm;
31 
32 void AccelTableBase::computeBucketCount() {
33   // First get the number of unique hashes.
34   std::vector<uint32_t> Uniques;
35   Uniques.reserve(Entries.size());
36   for (const auto &E : Entries)
37     Uniques.push_back(E.second.HashValue);
38   array_pod_sort(Uniques.begin(), Uniques.end());
39   std::vector<uint32_t>::iterator P =
40       std::unique(Uniques.begin(), Uniques.end());
41 
42   UniqueHashCount = std::distance(Uniques.begin(), P);
43 
44   if (UniqueHashCount > 1024)
45     BucketCount = UniqueHashCount / 4;
46   else if (UniqueHashCount > 16)
47     BucketCount = UniqueHashCount / 2;
48   else
49     BucketCount = std::max<uint32_t>(UniqueHashCount, 1);
50 }
51 
52 void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) {
53   // Create the individual hash data outputs.
54   for (auto &E : Entries) {
55     // Unique the entries.
56     std::stable_sort(E.second.Values.begin(), E.second.Values.end(),
57                      [](const AccelTableData *A, const AccelTableData *B) {
58                        return *A < *B;
59                      });
60     E.second.Values.erase(
61         std::unique(E.second.Values.begin(), E.second.Values.end()),
62         E.second.Values.end());
63   }
64 
65   // Figure out how many buckets we need, then compute the bucket contents and
66   // the final ordering. The hashes and offsets can be emitted by walking these
67   // data structures. We add temporary symbols to the data so they can be
68   // referenced when emitting the offsets.
69   computeBucketCount();
70 
71   // Compute bucket contents and final ordering.
72   Buckets.resize(BucketCount);
73   for (auto &E : Entries) {
74     uint32_t Bucket = E.second.HashValue % BucketCount;
75     Buckets[Bucket].push_back(&E.second);
76     E.second.Sym = Asm->createTempSymbol(Prefix);
77   }
78 
79   // Sort the contents of the buckets by hash value so that hash collisions end
80   // up together. Stable sort makes testing easier and doesn't cost much more.
81   for (auto &Bucket : Buckets)
82     std::stable_sort(Bucket.begin(), Bucket.end(),
83                      [](HashData *LHS, HashData *RHS) {
84                        return LHS->HashValue < RHS->HashValue;
85                      });
86 }
87 
88 namespace {
89 class AccelTableEmitter {
90 protected:
91   AsmPrinter *const Asm;          ///< Destination.
92   const AccelTableBase &Contents; ///< Data to emit.
93 
94   /// Controls whether to emit duplicate hash and offset table entries for names
95   /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5
96   /// tables do.
97   const bool SkipIdenticalHashes;
98 
99   void emitHashes() const;
100 
101   /// Emit offsets to lists of entries with identical names. The offsets are
102   /// relative to the Base argument.
103   void emitOffsets(const MCSymbol *Base) const;
104 
105 public:
106   AccelTableEmitter(AsmPrinter *Asm, const AccelTableBase &Contents,
107                     bool SkipIdenticalHashes)
108       : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {
109   }
110 };
111 
112 class AppleAccelTableEmitter : public AccelTableEmitter {
113   using Atom = AppleAccelTableData::Atom;
114 
115   /// The fixed header of an Apple Accelerator Table.
116   struct Header {
117     uint32_t Magic = MagicHash;
118     uint16_t Version = 1;
119     uint16_t HashFunction = dwarf::DW_hash_function_djb;
120     uint32_t BucketCount;
121     uint32_t HashCount;
122     uint32_t HeaderDataLength;
123 
124     /// 'HASH' magic value to detect endianness.
125     static const uint32_t MagicHash = 0x48415348;
126 
127     Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)
128         : BucketCount(BucketCount), HashCount(UniqueHashCount),
129           HeaderDataLength(DataLength) {}
130 
131     void emit(AsmPrinter *Asm) const;
132 #ifndef NDEBUG
133     void print(raw_ostream &OS) const;
134     void dump() const { print(dbgs()); }
135 #endif
136   };
137 
138   /// The HeaderData describes the structure of an Apple accelerator table
139   /// through a list of Atoms.
140   struct HeaderData {
141     /// In the case of data that is referenced via DW_FORM_ref_* the offset
142     /// base is used to describe the offset for all forms in the list of atoms.
143     uint32_t DieOffsetBase;
144 
145     const SmallVector<Atom, 4> Atoms;
146 
147     HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
148         : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
149 
150     void emit(AsmPrinter *Asm) const;
151 #ifndef NDEBUG
152     void print(raw_ostream &OS) const;
153     void dump() const { print(dbgs()); }
154 #endif
155   };
156 
157   Header Header;
158   HeaderData HeaderData;
159   const MCSymbol *SecBegin;
160 
161   void emitBuckets() const;
162   void emitData() const;
163 
164 public:
165   AppleAccelTableEmitter(AsmPrinter *Asm, const AccelTableBase &Contents,
166                          ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)
167       : AccelTableEmitter(Asm, Contents, true),
168         Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),
169                8 + (Atoms.size() * 4)),
170         HeaderData(Atoms), SecBegin(SecBegin) {}
171 
172   void emit() const;
173 
174 #ifndef NDEBUG
175   void print(raw_ostream &OS) const;
176   void dump() const { print(dbgs()); }
177 #endif
178 };
179 } // namespace
180 
181 void AccelTableEmitter::emitHashes() const {
182   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
183   unsigned BucketIdx = 0;
184   for (auto &Bucket : Contents.getBuckets()) {
185     for (auto &Hash : Bucket) {
186       uint32_t HashValue = Hash->HashValue;
187       if (SkipIdenticalHashes && PrevHash == HashValue)
188         continue;
189       Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
190       Asm->emitInt32(HashValue);
191       PrevHash = HashValue;
192     }
193     BucketIdx++;
194   }
195 }
196 
197 void AccelTableEmitter::emitOffsets(const MCSymbol *Base) const {
198   const auto &Buckets = Contents.getBuckets();
199   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
200   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
201     for (auto *Hash : Buckets[i]) {
202       uint32_t HashValue = Hash->HashValue;
203       if (SkipIdenticalHashes && PrevHash == HashValue)
204         continue;
205       PrevHash = HashValue;
206       Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
207       Asm->EmitLabelDifference(Hash->Sym, Base, sizeof(uint32_t));
208     }
209   }
210 }
211 
212 void AppleAccelTableEmitter::Header::emit(AsmPrinter *Asm) const {
213   Asm->OutStreamer->AddComment("Header Magic");
214   Asm->emitInt32(Magic);
215   Asm->OutStreamer->AddComment("Header Version");
216   Asm->emitInt16(Version);
217   Asm->OutStreamer->AddComment("Header Hash Function");
218   Asm->emitInt16(HashFunction);
219   Asm->OutStreamer->AddComment("Header Bucket Count");
220   Asm->emitInt32(BucketCount);
221   Asm->OutStreamer->AddComment("Header Hash Count");
222   Asm->emitInt32(HashCount);
223   Asm->OutStreamer->AddComment("Header Data Length");
224   Asm->emitInt32(HeaderDataLength);
225 }
226 
227 void AppleAccelTableEmitter::HeaderData::emit(AsmPrinter *Asm) const {
228   Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
229   Asm->emitInt32(DieOffsetBase);
230   Asm->OutStreamer->AddComment("HeaderData Atom Count");
231   Asm->emitInt32(Atoms.size());
232 
233   for (const Atom &A : Atoms) {
234     Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));
235     Asm->emitInt16(A.Type);
236     Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));
237     Asm->emitInt16(A.Form);
238   }
239 }
240 
241 void AppleAccelTableEmitter::emitBuckets() const {
242   const auto &Buckets = Contents.getBuckets();
243   unsigned index = 0;
244   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
245     Asm->OutStreamer->AddComment("Bucket " + Twine(i));
246     if (!Buckets[i].empty())
247       Asm->emitInt32(index);
248     else
249       Asm->emitInt32(std::numeric_limits<uint32_t>::max());
250     // Buckets point in the list of hashes, not to the data. Do not increment
251     // the index multiple times in case of hash collisions.
252     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
253     for (auto *HD : Buckets[i]) {
254       uint32_t HashValue = HD->HashValue;
255       if (PrevHash != HashValue)
256         ++index;
257       PrevHash = HashValue;
258     }
259   }
260 }
261 
262 void AppleAccelTableEmitter::emitData() const {
263   const auto &Buckets = Contents.getBuckets();
264   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
265     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
266     for (auto &Hash : Buckets[i]) {
267       // Terminate the previous entry if there is no hash collision with the
268       // current one.
269       if (PrevHash != std::numeric_limits<uint64_t>::max() &&
270           PrevHash != Hash->HashValue)
271         Asm->emitInt32(0);
272       // Remember to emit the label for our offset.
273       Asm->OutStreamer->EmitLabel(Hash->Sym);
274       Asm->OutStreamer->AddComment(Hash->Name.getString());
275       Asm->emitDwarfStringOffset(Hash->Name);
276       Asm->OutStreamer->AddComment("Num DIEs");
277       Asm->emitInt32(Hash->Values.size());
278       for (const auto *V : Hash->Values)
279         static_cast<const AppleAccelTableData *>(V)->emit(Asm);
280       PrevHash = Hash->HashValue;
281     }
282     // Emit the final end marker for the bucket.
283     if (!Buckets[i].empty())
284       Asm->emitInt32(0);
285   }
286 }
287 
288 void AppleAccelTableEmitter::emit() const {
289   Header.emit(Asm);
290   HeaderData.emit(Asm);
291   emitBuckets();
292   emitHashes();
293   emitOffsets(SecBegin);
294   emitData();
295 }
296 
297 void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
298                                    StringRef Prefix, const MCSymbol *SecBegin,
299                                    ArrayRef<AppleAccelTableData::Atom> Atoms) {
300   Contents.finalize(Asm, Prefix);
301   AppleAccelTableEmitter(Asm, Contents, Atoms, SecBegin).emit();
302 }
303 
304 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
305   Asm->emitInt32(Die->getDebugSectionOffset());
306 }
307 
308 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
309   Asm->emitInt32(Die->getDebugSectionOffset());
310   Asm->emitInt16(Die->getTag());
311   Asm->emitInt8(0);
312 }
313 
314 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
315   Asm->emitInt32(Offset);
316 }
317 
318 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
319   Asm->emitInt32(Offset);
320   Asm->emitInt16(Tag);
321   Asm->emitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
322                                           : 0);
323   Asm->emitInt32(QualifiedNameHash);
324 }
325 
326 #ifndef _MSC_VER
327 // The lines below are rejected by older versions (TBD) of MSVC.
328 constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[];
329 constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[];
330 constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[];
331 constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[];
332 #else
333 // FIXME: Erase this path once the minimum MSCV version has been bumped.
334 const SmallVector<AppleAccelTableData::Atom, 4>
335     AppleAccelTableOffsetData::Atoms = {
336         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
337 const SmallVector<AppleAccelTableData::Atom, 4> AppleAccelTableTypeData::Atoms =
338     {Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
339      Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
340      Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
341 const SmallVector<AppleAccelTableData::Atom, 4>
342     AppleAccelTableStaticOffsetData::Atoms = {
343         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
344 const SmallVector<AppleAccelTableData::Atom, 4>
345     AppleAccelTableStaticTypeData::Atoms = {
346         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
347         Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
348         Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
349 #endif
350 
351 #ifndef NDEBUG
352 void AppleAccelTableEmitter::Header::print(raw_ostream &OS) const {
353   OS << "Magic: " << format("0x%x", Magic) << "\n"
354      << "Version: " << Version << "\n"
355      << "Hash Function: " << HashFunction << "\n"
356      << "Bucket Count: " << BucketCount << "\n"
357      << "Header Data Length: " << HeaderDataLength << "\n";
358 }
359 
360 void AppleAccelTableData::Atom::print(raw_ostream &OS) const {
361   OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
362      << "Form: " << dwarf::FormEncodingString(Form) << "\n";
363 }
364 
365 void AppleAccelTableEmitter::HeaderData::print(raw_ostream &OS) const {
366   OS << "DIE Offset Base: " << DieOffsetBase << "\n";
367   for (auto Atom : Atoms)
368     Atom.print(OS);
369 }
370 
371 void AppleAccelTableEmitter::print(raw_ostream &OS) const {
372   Header.print(OS);
373   HeaderData.print(OS);
374   Contents.print(OS);
375   SecBegin->print(OS, nullptr);
376 }
377 
378 void AccelTableBase::HashData::print(raw_ostream &OS) const {
379   OS << "Name: " << Name.getString() << "\n";
380   OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
381   OS << "  Symbol: ";
382   if (Sym)
383     OS << *Sym;
384   else
385     OS << "<none>";
386   OS << "\n";
387   for (auto *Value : Values)
388     Value->print(OS);
389 }
390 
391 void AccelTableBase::print(raw_ostream &OS) const {
392   // Print Content.
393   OS << "Entries: \n";
394   for (const auto &Entry : Entries) {
395     OS << "Name: " << Entry.first() << "\n";
396     for (auto *V : Entry.second.Values)
397       V->print(OS);
398   }
399 
400   OS << "Buckets and Hashes: \n";
401   for (auto &Bucket : Buckets)
402     for (auto &Hash : Bucket)
403       Hash->print(OS);
404 
405   OS << "Data: \n";
406   for (auto &E : Entries)
407     E.second.print(OS);
408 }
409 
410 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
411   OS << "  Offset: " << Die->getOffset() << "\n";
412 }
413 
414 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
415   OS << "  Offset: " << Die->getOffset() << "\n";
416   OS << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
417 }
418 
419 void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {
420   OS << "  Static Offset: " << Offset << "\n";
421 }
422 
423 void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {
424   OS << "  Static Offset: " << Offset << "\n";
425   OS << "  QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
426   OS << "  Tag: " << dwarf::TagString(Tag) << "\n";
427   OS << "  ObjCClassIsImplementation: "
428      << (ObjCClassIsImplementation ? "true" : "false");
429   OS << "\n";
430 }
431 #endif
432