xref: /llvm-project/llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp (revision ba8daf0964c74ec394e905cc07ca3042360b51bf) 
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 constexpr const AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[];
74 constexpr const AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[];
75 constexpr const AppleAccelTableHeader::Atom AppleAccelTableStaticOffsetData::Atoms[];
76 constexpr const AppleAccelTableHeader::Atom AppleAccelTableStaticTypeData::Atoms[];
77 
78 void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); }
79 
80 void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) {
81   unsigned index = 0;
82   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
83     Asm->OutStreamer->AddComment("Bucket " + Twine(i));
84     if (!Buckets[i].empty())
85       Asm->EmitInt32(index);
86     else
87       Asm->EmitInt32(std::numeric_limits<uint32_t>::max());
88     // Buckets point in the list of hashes, not to the data. Do not increment
89     // the index multiple times in case of hash collisions.
90     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
91     for (auto *HD : Buckets[i]) {
92       uint32_t HashValue = HD->HashValue;
93       if (PrevHash != HashValue)
94         ++index;
95       PrevHash = HashValue;
96     }
97   }
98 }
99 
100 void AppleAccelTableBase::emitHashes(AsmPrinter *Asm) {
101   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
102   unsigned BucketIdx = 0;
103   for (auto &Bucket : Buckets) {
104     for (auto &Hash : Bucket) {
105       uint32_t HashValue = Hash->HashValue;
106       if (PrevHash == HashValue)
107         continue;
108       Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
109       Asm->EmitInt32(HashValue);
110       PrevHash = HashValue;
111     }
112     BucketIdx++;
113   }
114 }
115 
116 void AppleAccelTableBase::emitOffsets(AsmPrinter *Asm,
117                                       const MCSymbol *SecBegin) {
118   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
119   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
120     for (auto HI = Buckets[i].begin(), HE = Buckets[i].end(); HI != HE; ++HI) {
121       uint32_t HashValue = (*HI)->HashValue;
122       if (PrevHash == HashValue)
123         continue;
124       PrevHash = HashValue;
125       Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
126       MCContext &Context = Asm->OutStreamer->getContext();
127       const MCExpr *Sub = MCBinaryExpr::createSub(
128           MCSymbolRefExpr::create((*HI)->Sym, Context),
129           MCSymbolRefExpr::create(SecBegin, Context), Context);
130       Asm->OutStreamer->EmitValue(Sub, sizeof(uint32_t));
131     }
132   }
133 }
134 
135 void AppleAccelTableBase::emitData(AsmPrinter *Asm) {
136   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
137     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
138     for (auto &Hash : Buckets[i]) {
139       // Terminate the previous entry if there is no hash collision with the
140       // current one.
141       if (PrevHash != std::numeric_limits<uint64_t>::max() &&
142           PrevHash != Hash->HashValue)
143         Asm->EmitInt32(0);
144       // Remember to emit the label for our offset.
145       Asm->OutStreamer->EmitLabel(Hash->Sym);
146       Asm->OutStreamer->AddComment(Hash->Str);
147       Asm->emitDwarfStringOffset(Hash->Data.Name);
148       Asm->OutStreamer->AddComment("Num DIEs");
149       Asm->EmitInt32(Hash->Data.Values.size());
150       for (const auto *V : Hash->Data.Values) {
151         V->emit(Asm);
152       }
153       PrevHash = Hash->HashValue;
154     }
155     // Emit the final end marker for the bucket.
156     if (!Buckets[i].empty())
157       Asm->EmitInt32(0);
158   }
159 }
160 
161 void AppleAccelTableBase::computeBucketCount() {
162   // First get the number of unique hashes.
163   std::vector<uint32_t> uniques(Data.size());
164   for (size_t i = 0, e = Data.size(); i < e; ++i)
165     uniques[i] = Data[i]->HashValue;
166   array_pod_sort(uniques.begin(), uniques.end());
167   std::vector<uint32_t>::iterator p =
168       std::unique(uniques.begin(), uniques.end());
169 
170   // Compute the hashes count and use it to set that together with the bucket
171   // count in the header.
172   Header.setBucketAndHashCount(std::distance(uniques.begin(), p));
173 }
174 
175 void AppleAccelTableBase::finalizeTable(AsmPrinter *Asm, StringRef Prefix) {
176   // Create the individual hash data outputs.
177   Data.reserve(Entries.size());
178   for (auto &E : Entries) {
179     // Unique the entries.
180     std::stable_sort(E.second.Values.begin(), E.second.Values.end(),
181                      [](const AppleAccelTableData *A,
182                         const AppleAccelTableData *B) { return *A < *B; });
183     E.second.Values.erase(
184         std::unique(E.second.Values.begin(), E.second.Values.end()),
185         E.second.Values.end());
186 
187     HashData *Entry = new (Allocator) HashData(E.first(), E.second);
188     Data.push_back(Entry);
189   }
190 
191   // Figure out how many buckets we need, then compute the bucket contents and
192   // the final ordering. We'll emit the hashes and offsets by doing a walk
193   // during the emission phase. We add temporary symbols to the data so that we
194   // can reference them during the offset later, we'll emit them when we emit
195   // the data.
196   computeBucketCount();
197 
198   // Compute bucket contents and final ordering.
199   Buckets.resize(Header.getBucketCount());
200   for (auto &D : Data) {
201     uint32_t bucket = D->HashValue % Header.getBucketCount();
202     Buckets[bucket].push_back(D);
203     D->Sym = Asm->createTempSymbol(Prefix);
204   }
205 
206   // Sort the contents of the buckets by hash value so that hash collisions end
207   // up together. Stable sort makes testing easier and doesn't cost much more.
208   for (auto &Bucket : Buckets)
209     std::stable_sort(Bucket.begin(), Bucket.end(),
210                      [](HashData *LHS, HashData *RHS) {
211                        return LHS->HashValue < RHS->HashValue;
212                      });
213 }
214 
215 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
216   Asm->EmitInt32(Die->getDebugSectionOffset());
217 }
218 
219 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
220   Asm->EmitInt32(Die->getDebugSectionOffset());
221   Asm->EmitInt16(Die->getTag());
222   Asm->EmitInt8(0);
223 }
224 
225 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
226   Asm->EmitInt32(Offset);
227 }
228 
229 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
230   Asm->EmitInt32(Offset);
231   Asm->EmitInt16(Tag);
232   Asm->EmitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
233                                           : 0);
234   Asm->EmitInt32(QualifiedNameHash);
235 }
236