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 AppleAccelTableHeader::emit(AsmPrinter *Asm) {
33   // Emit Header.
34   Asm->OutStreamer->AddComment("Header Magic");
35   Asm->EmitInt32(Header.Magic);
36   Asm->OutStreamer->AddComment("Header Version");
37   Asm->EmitInt16(Header.Version);
38   Asm->OutStreamer->AddComment("Header Hash Function");
39   Asm->EmitInt16(Header.HashFunction);
40   Asm->OutStreamer->AddComment("Header Bucket Count");
41   Asm->EmitInt32(Header.BucketCount);
42   Asm->OutStreamer->AddComment("Header Hash Count");
43   Asm->EmitInt32(Header.HashCount);
44   Asm->OutStreamer->AddComment("Header Data Length");
45   Asm->EmitInt32(Header.HeaderDataLength);
46 
47   //  Emit Header Data
48   Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
49   Asm->EmitInt32(HeaderData.DieOffsetBase);
50   Asm->OutStreamer->AddComment("HeaderData Atom Count");
51   Asm->EmitInt32(HeaderData.Atoms.size());
52 
53   for (size_t i = 0; i < HeaderData.Atoms.size(); i++) {
54     Atom A = HeaderData.Atoms[i];
55     Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));
56     Asm->EmitInt16(A.Type);
57     Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));
58     Asm->EmitInt16(A.Form);
59   }
60 }
61 
62 void AppleAccelTableHeader::setBucketAndHashCount(uint32_t HashCount) {
63   if (HashCount > 1024)
64     Header.BucketCount = HashCount / 4;
65   else if (HashCount > 16)
66     Header.BucketCount = HashCount / 2;
67   else
68     Header.BucketCount = HashCount > 0 ? HashCount : 1;
69 
70   Header.HashCount = HashCount;
71 }
72 
73 void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); }
74 
75 void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) {
76   unsigned index = 0;
77   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
78     Asm->OutStreamer->AddComment("Bucket " + Twine(i));
79     if (!Buckets[i].empty())
80       Asm->EmitInt32(index);
81     else
82       Asm->EmitInt32(std::numeric_limits<uint32_t>::max());
83     // Buckets point in the list of hashes, not to the data. Do not increment
84     // the index multiple times in case of hash collisions.
85     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
86     for (auto *HD : Buckets[i]) {
87       uint32_t HashValue = HD->HashValue;
88       if (PrevHash != HashValue)
89         ++index;
90       PrevHash = HashValue;
91     }
92   }
93 }
94 
95 void AppleAccelTableBase::emitHashes(AsmPrinter *Asm) {
96   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
97   unsigned BucketIdx = 0;
98   for (auto &Bucket : Buckets) {
99     for (auto &Hash : Bucket) {
100       uint32_t HashValue = Hash->HashValue;
101       if (PrevHash == HashValue)
102         continue;
103       Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
104       Asm->EmitInt32(HashValue);
105       PrevHash = HashValue;
106     }
107     BucketIdx++;
108   }
109 }
110 
111 void AppleAccelTableBase::emitOffsets(AsmPrinter *Asm,
112                                       const MCSymbol *SecBegin) {
113   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
114   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
115     for (auto HI = Buckets[i].begin(), HE = Buckets[i].end(); HI != HE; ++HI) {
116       uint32_t HashValue = (*HI)->HashValue;
117       if (PrevHash == HashValue)
118         continue;
119       PrevHash = HashValue;
120       Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
121       MCContext &Context = Asm->OutStreamer->getContext();
122       const MCExpr *Sub = MCBinaryExpr::createSub(
123           MCSymbolRefExpr::create((*HI)->Sym, Context),
124           MCSymbolRefExpr::create(SecBegin, Context), Context);
125       Asm->OutStreamer->EmitValue(Sub, sizeof(uint32_t));
126     }
127   }
128 }
129 
130 void AppleAccelTableBase::emitData(AsmPrinter *Asm) {
131   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
132     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
133     for (auto &Hash : Buckets[i]) {
134       // Terminate the previous entry if there is no hash collision with the
135       // current one.
136       if (PrevHash != std::numeric_limits<uint64_t>::max() &&
137           PrevHash != Hash->HashValue)
138         Asm->EmitInt32(0);
139       // Remember to emit the label for our offset.
140       Asm->OutStreamer->EmitLabel(Hash->Sym);
141       Asm->OutStreamer->AddComment(Hash->Name.getString());
142       Asm->emitDwarfStringOffset(Hash->Name);
143       Asm->OutStreamer->AddComment("Num DIEs");
144       Asm->EmitInt32(Hash->Values.size());
145       for (const auto *V : Hash->Values) {
146         V->emit(Asm);
147       }
148       PrevHash = Hash->HashValue;
149     }
150     // Emit the final end marker for the bucket.
151     if (!Buckets[i].empty())
152       Asm->EmitInt32(0);
153   }
154 }
155 
156 void AppleAccelTableBase::computeBucketCount() {
157   // First get the number of unique hashes.
158   std::vector<uint32_t> uniques;
159   uniques.reserve(Entries.size());
160   for (const auto &E : Entries)
161     uniques.push_back(E.second.HashValue);
162   array_pod_sort(uniques.begin(), uniques.end());
163   std::vector<uint32_t>::iterator p =
164       std::unique(uniques.begin(), uniques.end());
165 
166   // Compute the hashes count and use it to set that together with the bucket
167   // count in the header.
168   Header.setBucketAndHashCount(std::distance(uniques.begin(), p));
169 }
170 
171 void AppleAccelTableBase::finalizeTable(AsmPrinter *Asm, StringRef Prefix) {
172   // Create the individual hash data outputs.
173   for (auto &E : Entries) {
174     // Unique the entries.
175     std::stable_sort(E.second.Values.begin(), E.second.Values.end(),
176                      [](const AppleAccelTableData *A,
177                         const AppleAccelTableData *B) { return *A < *B; });
178     E.second.Values.erase(
179         std::unique(E.second.Values.begin(), E.second.Values.end()),
180         E.second.Values.end());
181   }
182 
183   // Figure out how many buckets we need, then compute the bucket contents and
184   // the final ordering. We'll emit the hashes and offsets by doing a walk
185   // during the emission phase. We add temporary symbols to the data so that we
186   // can reference them during the offset later, we'll emit them when we emit
187   // the data.
188   computeBucketCount();
189 
190   // Compute bucket contents and final ordering.
191   Buckets.resize(Header.getBucketCount());
192   for (auto &E : Entries) {
193     uint32_t bucket = E.second.HashValue % Header.getBucketCount();
194     Buckets[bucket].push_back(&E.second);
195     E.second.Sym = Asm->createTempSymbol(Prefix);
196   }
197 
198   // Sort the contents of the buckets by hash value so that hash collisions end
199   // up together. Stable sort makes testing easier and doesn't cost much more.
200   for (auto &Bucket : Buckets)
201     std::stable_sort(Bucket.begin(), Bucket.end(),
202                      [](HashData *LHS, HashData *RHS) {
203                        return LHS->HashValue < RHS->HashValue;
204                      });
205 }
206 
207 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
208   Asm->EmitInt32(Die->getDebugSectionOffset());
209 }
210 
211 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
212   Asm->EmitInt32(Die->getDebugSectionOffset());
213   Asm->EmitInt16(Die->getTag());
214   Asm->EmitInt8(0);
215 }
216 
217 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
218   Asm->EmitInt32(Offset);
219 }
220 
221 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
222   Asm->EmitInt32(Offset);
223   Asm->EmitInt16(Tag);
224   Asm->EmitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
225                                           : 0);
226   Asm->EmitInt32(QualifiedNameHash);
227 }
228 
229 #ifndef _MSC_VER
230 // The lines below are rejected by older versions (TBD) of MSVC.
231 constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[];
232 constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[];
233 constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticOffsetData::Atoms[];
234 constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticTypeData::Atoms[];
235 #else
236 // FIXME: Erase this path once the minimum MSCV version has been bumped.
237 const SmallVector<AppleAccelTableHeader::Atom, 4>
238     AppleAccelTableOffsetData::Atoms = {AppleAccelTableHeader::Atom(
239         dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
240 const SmallVector<AppleAccelTableHeader::Atom, 4>
241     AppleAccelTableTypeData::Atoms = {
242         AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
243                                     dwarf::DW_FORM_data4),
244         AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag,
245                                     dwarf::DW_FORM_data2),
246         AppleAccelTableHeader::Atom(dwarf::DW_ATOM_type_flags,
247                                     dwarf::DW_FORM_data1)};
248 const SmallVector<AppleAccelTableHeader::Atom, 4>
249     AppleAccelTableStaticOffsetData::Atoms = {AppleAccelTableHeader::Atom(
250         dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
251 const SmallVector<AppleAccelTableHeader::Atom, 4>
252     AppleAccelTableStaticTypeData::Atoms = {
253         AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
254                                     dwarf::DW_FORM_data4),
255         AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag,
256                                     dwarf::DW_FORM_data2),
257         AppleAccelTableHeader::Atom(5, dwarf::DW_FORM_data1),
258         AppleAccelTableHeader::Atom(6, dwarf::DW_FORM_data4)};
259 #endif
260 
261 #ifndef NDEBUG
262 void AppleAccelTableHeader::Header::print(raw_ostream &OS) const {
263   OS << "Magic: " << format("0x%x", Magic) << "\n"
264      << "Version: " << Version << "\n"
265      << "Hash Function: " << HashFunction << "\n"
266      << "Bucket Count: " << BucketCount << "\n"
267      << "Header Data Length: " << HeaderDataLength << "\n";
268 }
269 
270 void AppleAccelTableHeader::Atom::print(raw_ostream &OS) const {
271   OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
272      << "Form: " << dwarf::FormEncodingString(Form) << "\n";
273 }
274 
275 void AppleAccelTableHeader::HeaderData::print(raw_ostream &OS) const {
276   OS << "DIE Offset Base: " << DieOffsetBase << "\n";
277   for (auto Atom : Atoms)
278     Atom.print(OS);
279 }
280 
281 void AppleAccelTableHeader::print(raw_ostream &OS) const {
282   Header.print(OS);
283   HeaderData.print(OS);
284 }
285 
286 void AppleAccelTableBase::HashData::print(raw_ostream &OS) const {
287   OS << "Name: " << Name.getString() << "\n";
288   OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
289   OS << "  Symbol: ";
290   if (Sym)
291     OS << *Sym;
292   else
293     OS << "<none>";
294   OS << "\n";
295   for (auto *Value : Values)
296     Value->print(OS);
297 }
298 
299 void AppleAccelTableBase::print(raw_ostream &OS) const {
300   // Print Header.
301   Header.print(OS);
302 
303   // Print Content.
304   OS << "Entries: \n";
305   for (const auto &Entry : Entries) {
306     OS << "Name: " << Entry.first() << "\n";
307     for (auto *V : Entry.second.Values)
308       V->print(OS);
309   }
310 
311   OS << "Buckets and Hashes: \n";
312   for (auto &Bucket : Buckets)
313     for (auto &Hash : Bucket)
314       Hash->print(OS);
315 
316   OS << "Data: \n";
317   for (auto &E : Entries)
318     E.second.print(OS);
319 }
320 
321 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
322   OS << "  Offset: " << Die->getOffset() << "\n";
323 }
324 
325 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
326   OS << "  Offset: " << Die->getOffset() << "\n";
327   OS << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
328 }
329 
330 void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {
331   OS << "  Static Offset: " << Offset << "\n";
332 }
333 
334 void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {
335   OS << "  Static Offset: " << Offset << "\n";
336   OS << "  QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
337   OS << "  Tag: " << dwarf::TagString(Tag) << "\n";
338   OS << "  ObjCClassIsImplementation: "
339      << (ObjCClassIsImplementation ? "true" : "false");
340   OS << "\n";
341 }
342 #endif
343