Line data Source code
1 : //===- llvm/CodeGen/DwarfAccelTable.cpp - Dwarf 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 dwarf accelerator tables.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "DwarfAccelTable.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 <cassert>
26 : #include <cstddef>
27 : #include <cstdint>
28 : #include <iterator>
29 : #include <limits>
30 : #include <vector>
31 :
32 : using namespace llvm;
33 :
34 : // The length of the header data is always going to be 4 + 4 + 4*NumAtoms.
35 65896 : DwarfAccelTable::DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom> atomList)
36 65896 : : Header(8 + (atomList.size() * 4)), HeaderData(atomList),
37 593059 : Entries(Allocator) {}
38 :
39 961 : void DwarfAccelTable::AddName(DwarfStringPoolEntryRef Name, const DIE *die,
40 : char Flags) {
41 : assert(Data.empty() && "Already finalized!");
42 : // If the string is in the list already then add this die to the list
43 : // otherwise add a new one.
44 1922 : DataArray &DIEs = Entries[Name.getString()];
45 : assert(!DIEs.Name || DIEs.Name == Name);
46 961 : DIEs.Name = Name;
47 3844 : DIEs.Values.push_back(new (Allocator) HashDataContents(die, Flags));
48 961 : }
49 :
50 800 : void DwarfAccelTable::ComputeBucketCount() {
51 : // First get the number of unique hashes.
52 3200 : std::vector<uint32_t> uniques(Data.size());
53 2506 : for (size_t i = 0, e = Data.size(); i < e; ++i)
54 2718 : uniques[i] = Data[i]->HashValue;
55 2400 : array_pod_sort(uniques.begin(), uniques.end());
56 : std::vector<uint32_t>::iterator p =
57 2400 : std::unique(uniques.begin(), uniques.end());
58 1600 : uint32_t num = std::distance(uniques.begin(), p);
59 :
60 : // Then compute the bucket size, minimum of 1 bucket.
61 800 : if (num > 1024)
62 0 : Header.bucket_count = num / 4;
63 800 : else if (num > 16)
64 1 : Header.bucket_count = num / 2;
65 : else
66 799 : Header.bucket_count = num > 0 ? num : 1;
67 :
68 800 : Header.hashes_count = num;
69 800 : }
70 :
71 : // compareDIEs - comparison predicate that sorts DIEs by their offset.
72 60 : static bool compareDIEs(const DwarfAccelTable::HashDataContents *A,
73 : const DwarfAccelTable::HashDataContents *B) {
74 60 : return A->Die->getOffset() < B->Die->getOffset();
75 : }
76 :
77 800 : void DwarfAccelTable::FinalizeTable(AsmPrinter *Asm, StringRef Prefix) {
78 : // Create the individual hash data outputs.
79 800 : Data.reserve(Entries.size());
80 2400 : for (StringMap<DataArray>::iterator EI = Entries.begin(), EE = Entries.end();
81 1706 : EI != EE; ++EI) {
82 :
83 : // Unique the entries.
84 4530 : std::stable_sort(EI->second.Values.begin(), EI->second.Values.end(), compareDIEs);
85 1812 : EI->second.Values.erase(
86 4530 : std::unique(EI->second.Values.begin(), EI->second.Values.end()),
87 5436 : EI->second.Values.end());
88 :
89 4530 : HashData *Entry = new (Allocator) HashData(EI->getKey(), EI->second);
90 906 : Data.push_back(Entry);
91 : }
92 :
93 : // Figure out how many buckets we need, then compute the bucket
94 : // contents and the final ordering. We'll emit the hashes and offsets
95 : // by doing a walk during the emission phase. We add temporary
96 : // symbols to the data so that we can reference them during the offset
97 : // later, we'll emit them when we emit the data.
98 800 : ComputeBucketCount();
99 :
100 : // Compute bucket contents and final ordering.
101 800 : Buckets.resize(Header.bucket_count);
102 2506 : for (size_t i = 0, e = Data.size(); i < e; ++i) {
103 1812 : uint32_t bucket = Data[i]->HashValue % Header.bucket_count;
104 1812 : Buckets[bucket].push_back(Data[i]);
105 1812 : Data[i]->Sym = Asm->createTempSymbol(Prefix);
106 : }
107 :
108 : // Sort the contents of the buckets by hash value so that hash
109 : // collisions end up together. Stable sort makes testing easier and
110 : // doesn't cost much more.
111 5569 : for (size_t i = 0; i < Buckets.size(); ++i)
112 5292 : std::stable_sort(Buckets[i].begin(), Buckets[i].end(),
113 : [] (HashData *LHS, HashData *RHS) {
114 : return LHS->HashValue < RHS->HashValue;
115 : });
116 800 : }
117 :
118 : // Emits the header for the table via the AsmPrinter.
119 800 : void DwarfAccelTable::EmitHeader(AsmPrinter *Asm) {
120 2400 : Asm->OutStreamer->AddComment("Header Magic");
121 800 : Asm->EmitInt32(Header.magic);
122 2400 : Asm->OutStreamer->AddComment("Header Version");
123 800 : Asm->EmitInt16(Header.version);
124 2400 : Asm->OutStreamer->AddComment("Header Hash Function");
125 800 : Asm->EmitInt16(Header.hash_function);
126 2400 : Asm->OutStreamer->AddComment("Header Bucket Count");
127 800 : Asm->EmitInt32(Header.bucket_count);
128 2400 : Asm->OutStreamer->AddComment("Header Hash Count");
129 800 : Asm->EmitInt32(Header.hashes_count);
130 2400 : Asm->OutStreamer->AddComment("Header Data Length");
131 800 : Asm->EmitInt32(Header.header_data_len);
132 2400 : Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
133 800 : Asm->EmitInt32(HeaderData.die_offset_base);
134 2400 : Asm->OutStreamer->AddComment("HeaderData Atom Count");
135 1600 : Asm->EmitInt32(HeaderData.Atoms.size());
136 2000 : for (size_t i = 0; i < HeaderData.Atoms.size(); i++) {
137 2400 : Atom A = HeaderData.Atoms[i];
138 3600 : Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.type));
139 1200 : Asm->EmitInt16(A.type);
140 3600 : Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.form));
141 1200 : Asm->EmitInt16(A.form);
142 : }
143 800 : }
144 :
145 : // Walk through and emit the buckets for the table. Each index is
146 : // an offset into the list of hashes.
147 800 : void DwarfAccelTable::EmitBuckets(AsmPrinter *Asm) {
148 800 : unsigned index = 0;
149 2923 : for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
150 6615 : Asm->OutStreamer->AddComment("Bucket " + Twine(i));
151 3969 : if (!Buckets[i].empty())
152 663 : Asm->EmitInt32(index);
153 : else
154 660 : Asm->EmitInt32(std::numeric_limits<uint32_t>::max());
155 : // Buckets point in the list of hashes, not to the data. Do not
156 : // increment the index multiple times in case of hash collisions.
157 1323 : uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
158 7521 : for (auto *HD : Buckets[i]) {
159 906 : uint32_t HashValue = HD->HashValue;
160 906 : if (PrevHash != HashValue)
161 900 : ++index;
162 906 : PrevHash = HashValue;
163 : }
164 : }
165 800 : }
166 :
167 : // Walk through the buckets and emit the individual hashes for each
168 : // bucket.
169 800 : void DwarfAccelTable::EmitHashes(AsmPrinter *Asm) {
170 800 : uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
171 2923 : for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
172 5292 : for (HashList::const_iterator HI = Buckets[i].begin(),
173 3969 : HE = Buckets[i].end();
174 2229 : HI != HE; ++HI) {
175 906 : uint32_t HashValue = (*HI)->HashValue;
176 906 : if (PrevHash == HashValue)
177 6 : continue;
178 4500 : Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(i));
179 900 : Asm->EmitInt32(HashValue);
180 900 : PrevHash = HashValue;
181 : }
182 : }
183 800 : }
184 :
185 : // Walk through the buckets and emit the individual offsets for each
186 : // element in each bucket. This is done via a symbol subtraction from the
187 : // beginning of the section. The non-section symbol will be output later
188 : // when we emit the actual data.
189 800 : void DwarfAccelTable::emitOffsets(AsmPrinter *Asm, const MCSymbol *SecBegin) {
190 800 : uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
191 2923 : for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
192 5292 : for (HashList::const_iterator HI = Buckets[i].begin(),
193 3969 : HE = Buckets[i].end();
194 2229 : HI != HE; ++HI) {
195 906 : uint32_t HashValue = (*HI)->HashValue;
196 906 : if (PrevHash == HashValue)
197 6 : continue;
198 900 : PrevHash = HashValue;
199 4500 : Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
200 1800 : MCContext &Context = Asm->OutStreamer->getContext();
201 : const MCExpr *Sub = MCBinaryExpr::createSub(
202 1800 : MCSymbolRefExpr::create((*HI)->Sym, Context),
203 1800 : MCSymbolRefExpr::create(SecBegin, Context), Context);
204 1800 : Asm->OutStreamer->EmitValue(Sub, sizeof(uint32_t));
205 : }
206 : }
207 800 : }
208 :
209 : // Walk through the buckets and emit the full data for each element in
210 : // the bucket. For the string case emit the dies and the various offsets.
211 : // Terminate each HashData bucket with 0.
212 800 : void DwarfAccelTable::EmitData(AsmPrinter *Asm, DwarfDebug *D) {
213 2923 : for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
214 1323 : uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
215 5292 : for (HashList::const_iterator HI = Buckets[i].begin(),
216 3969 : HE = Buckets[i].end();
217 2229 : HI != HE; ++HI) {
218 : // Terminate the previous entry if there is no hash collision
219 : // with the current one.
220 1149 : if (PrevHash != std::numeric_limits<uint64_t>::max() &&
221 243 : PrevHash != (*HI)->HashValue)
222 237 : Asm->EmitInt32(0);
223 : // Remember to emit the label for our offset.
224 1812 : Asm->OutStreamer->EmitLabel((*HI)->Sym);
225 2718 : Asm->OutStreamer->AddComment((*HI)->Str);
226 906 : Asm->emitDwarfStringOffset((*HI)->Data.Name);
227 2718 : Asm->OutStreamer->AddComment("Num DIEs");
228 1812 : Asm->EmitInt32((*HI)->Data.Values.size());
229 4585 : for (HashDataContents *HD : (*HI)->Data.Values) {
230 : // Emit the DIE offset
231 961 : Asm->EmitInt32(HD->Die->getDebugSectionOffset());
232 : // If we have multiple Atoms emit that info too.
233 : // FIXME: A bit of a hack, we either emit only one atom or all info.
234 1922 : if (HeaderData.Atoms.size() > 1) {
235 443 : Asm->EmitInt16(HD->Die->getTag());
236 443 : Asm->EmitInt8(HD->Flags);
237 : }
238 : }
239 906 : PrevHash = (*HI)->HashValue;
240 : }
241 : // Emit the final end marker for the bucket.
242 3969 : if (!Buckets[i].empty())
243 663 : Asm->EmitInt32(0);
244 : }
245 800 : }
246 :
247 : // Emit the entire data structure to the output file.
248 800 : void DwarfAccelTable::emit(AsmPrinter *Asm, const MCSymbol *SecBegin,
249 : DwarfDebug *D) {
250 : // Emit the header.
251 800 : EmitHeader(Asm);
252 :
253 : // Emit the buckets.
254 800 : EmitBuckets(Asm);
255 :
256 : // Emit the hashes.
257 800 : EmitHashes(Asm);
258 :
259 : // Emit the offsets.
260 800 : emitOffsets(Asm, SecBegin);
261 :
262 : // Emit the hash data.
263 800 : EmitData(Asm, D);
264 800 : }
265 :
266 : #ifndef NDEBUG
267 : void DwarfAccelTable::print(raw_ostream &OS) {
268 : Header.print(OS);
269 : HeaderData.print(OS);
270 :
271 : OS << "Entries: \n";
272 : for (StringMap<DataArray>::const_iterator EI = Entries.begin(),
273 : EE = Entries.end();
274 : EI != EE; ++EI) {
275 : OS << "Name: " << EI->getKeyData() << "\n";
276 : for (HashDataContents *HD : EI->second.Values)
277 : HD->print(OS);
278 : }
279 :
280 : OS << "Buckets and Hashes: \n";
281 : for (size_t i = 0, e = Buckets.size(); i < e; ++i)
282 : for (HashList::const_iterator HI = Buckets[i].begin(),
283 : HE = Buckets[i].end();
284 : HI != HE; ++HI)
285 : (*HI)->print(OS);
286 :
287 : OS << "Data: \n";
288 : for (std::vector<HashData *>::const_iterator DI = Data.begin(),
289 : DE = Data.end();
290 : DI != DE; ++DI)
291 : (*DI)->print(OS);
292 : }
293 : #endif
|
