/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/AsmPrinter/DwarfAccelTable.h
Line | Count | Source |
1 | | //==- llvm/CodeGen/DwarfAccelTable.h - Dwarf Accelerator Tables --*- C++ -*-==// |
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 | | #ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H |
15 | | #define LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H |
16 | | |
17 | | #include "llvm/ADT/ArrayRef.h" |
18 | | #include "llvm/ADT/SmallVector.h" |
19 | | #include "llvm/ADT/StringMap.h" |
20 | | #include "llvm/ADT/StringRef.h" |
21 | | #include "llvm/BinaryFormat/Dwarf.h" |
22 | | #include "llvm/CodeGen/DIE.h" |
23 | | #include "llvm/CodeGen/DwarfStringPoolEntry.h" |
24 | | #include "llvm/MC/MCSymbol.h" |
25 | | #include "llvm/Support/Allocator.h" |
26 | | #include "llvm/Support/Debug.h" |
27 | | #include "llvm/Support/Format.h" |
28 | | #include "llvm/Support/raw_ostream.h" |
29 | | #include <cstddef> |
30 | | #include <cstdint> |
31 | | #include <vector> |
32 | | |
33 | | // The dwarf accelerator tables are an indirect hash table optimized |
34 | | // for null lookup rather than access to known data. They are output into |
35 | | // an on-disk format that looks like this: |
36 | | // |
37 | | // .-------------. |
38 | | // | HEADER | |
39 | | // |-------------| |
40 | | // | BUCKETS | |
41 | | // |-------------| |
42 | | // | HASHES | |
43 | | // |-------------| |
44 | | // | OFFSETS | |
45 | | // |-------------| |
46 | | // | DATA | |
47 | | // `-------------' |
48 | | // |
49 | | // where the header contains a magic number, version, type of hash function, |
50 | | // the number of buckets, total number of hashes, and room for a special |
51 | | // struct of data and the length of that struct. |
52 | | // |
53 | | // The buckets contain an index (e.g. 6) into the hashes array. The hashes |
54 | | // section contains all of the 32-bit hash values in contiguous memory, and |
55 | | // the offsets contain the offset into the data area for the particular |
56 | | // hash. |
57 | | // |
58 | | // For a lookup example, we could hash a function name and take it modulo the |
59 | | // number of buckets giving us our bucket. From there we take the bucket value |
60 | | // as an index into the hashes table and look at each successive hash as long |
61 | | // as the hash value is still the same modulo result (bucket value) as earlier. |
62 | | // If we have a match we look at that same entry in the offsets table and |
63 | | // grab the offset in the data for our final match. |
64 | | |
65 | | namespace llvm { |
66 | | |
67 | | class AsmPrinter; |
68 | | class DwarfDebug; |
69 | | |
70 | | class DwarfAccelTable { |
71 | | // Helper function to compute the number of buckets needed based on |
72 | | // the number of unique hashes. |
73 | | void ComputeBucketCount(); |
74 | | |
75 | | struct TableHeader { |
76 | | uint32_t magic = MagicHash; // 'HASH' magic value to allow endian detection |
77 | | uint16_t version = 1; // Version number. |
78 | | uint16_t hash_function = dwarf::DW_hash_function_djb; |
79 | | // The hash function enumeration that was used. |
80 | | uint32_t bucket_count = 0; // The number of buckets in this hash table. |
81 | | uint32_t hashes_count = 0; // The total number of unique hash values |
82 | | // and hash data offsets in this table. |
83 | | uint32_t header_data_len; // The bytes to skip to get to the hash |
84 | | // indexes (buckets) for correct alignment. |
85 | | // Also written to disk is the implementation specific header data. |
86 | | |
87 | | static const uint32_t MagicHash = 0x48415348; |
88 | | |
89 | 132k | TableHeader(uint32_t data_len) : header_data_len(data_len) {} |
90 | | |
91 | | #ifndef NDEBUG |
92 | | void print(raw_ostream &OS) { |
93 | | OS << "Magic: " << format("0x%x", magic) << "\n" |
94 | | << "Version: " << version << "\n" |
95 | | << "Hash Function: " << hash_function << "\n" |
96 | | << "Bucket Count: " << bucket_count << "\n" |
97 | | << "Header Data Length: " << header_data_len << "\n"; |
98 | | } |
99 | | |
100 | | void dump() { print(dbgs()); } |
101 | | #endif |
102 | | }; |
103 | | |
104 | | public: |
105 | | // The HeaderData describes the form of each set of data. In general this |
106 | | // is as a list of atoms (atom_count) where each atom contains a type |
107 | | // (AtomType type) of data, and an encoding form (form). In the case of |
108 | | // data that is referenced via DW_FORM_ref_* the die_offset_base is |
109 | | // used to describe the offset for all forms in the list of atoms. |
110 | | // This also serves as a public interface of sorts. |
111 | | // When written to disk this will have the form: |
112 | | // |
113 | | // uint32_t die_offset_base |
114 | | // uint32_t atom_count |
115 | | // atom_count Atoms |
116 | | |
117 | | // Make these public so that they can be used as a general interface to |
118 | | // the class. |
119 | | struct Atom { |
120 | | uint16_t type; // enum AtomType |
121 | | uint16_t form; // DWARF DW_FORM_ defines |
122 | | |
123 | 99.1k | constexpr Atom(uint16_t type, uint16_t form) : type(type), form(form) {} |
124 | | |
125 | | #ifndef NDEBUG |
126 | | void print(raw_ostream &OS) { |
127 | | OS << "Type: " << dwarf::AtomTypeString(type) << "\n" |
128 | | << "Form: " << dwarf::FormEncodingString(form) << "\n"; |
129 | | } |
130 | | |
131 | | void dump() { print(dbgs()); } |
132 | | #endif |
133 | | }; |
134 | | |
135 | | private: |
136 | | struct TableHeaderData { |
137 | | uint32_t die_offset_base; |
138 | | SmallVector<Atom, 3> Atoms; |
139 | | |
140 | | TableHeaderData(ArrayRef<Atom> AtomList, uint32_t offset = 0) |
141 | 132k | : die_offset_base(offset), Atoms(AtomList.begin(), AtomList.end()) {} |
142 | | |
143 | | #ifndef NDEBUG |
144 | | void print(raw_ostream &OS) { |
145 | | OS << "die_offset_base: " << die_offset_base << "\n"; |
146 | | for (size_t i = 0; i < Atoms.size(); i++) |
147 | | Atoms[i].print(OS); |
148 | | } |
149 | | |
150 | | void dump() { print(dbgs()); } |
151 | | #endif |
152 | | }; |
153 | | |
154 | | // The data itself consists of a str_offset, a count of the DIEs in the |
155 | | // hash and the offsets to the DIEs themselves. |
156 | | // On disk each data section is ended with a 0 KeyType as the end of the |
157 | | // hash chain. |
158 | | // On output this looks like: |
159 | | // uint32_t str_offset |
160 | | // uint32_t hash_data_count |
161 | | // HashData[hash_data_count] |
162 | | public: |
163 | | struct HashDataContents { |
164 | | const DIE *Die; // Offsets |
165 | | char Flags; // Specific flags to output |
166 | | |
167 | 44.3k | HashDataContents(const DIE *D, char Flags) : Die(D), Flags(Flags) {} |
168 | | |
169 | | #ifndef NDEBUG |
170 | | void print(raw_ostream &OS) const { |
171 | | OS << " Offset: " << Die->getOffset() << "\n" |
172 | | << " Tag: " << dwarf::TagString(Die->getTag()) << "\n" |
173 | | << " Flags: " << Flags << "\n"; |
174 | | } |
175 | | #endif |
176 | | }; |
177 | | |
178 | | private: |
179 | | // String Data |
180 | | struct DataArray { |
181 | | DwarfStringPoolEntryRef Name; |
182 | | std::vector<HashDataContents *> Values; |
183 | | }; |
184 | | |
185 | | friend struct HashData; |
186 | | |
187 | | struct HashData { |
188 | | StringRef Str; |
189 | | uint32_t HashValue; |
190 | | MCSymbol *Sym; |
191 | | DwarfAccelTable::DataArray &Data; // offsets |
192 | | |
193 | | HashData(StringRef S, DwarfAccelTable::DataArray &Data) |
194 | 17.1k | : Str(S), Data(Data) { |
195 | 17.1k | HashValue = dwarf::djbHash(S); |
196 | 17.1k | } |
197 | | |
198 | | #ifndef NDEBUG |
199 | | void print(raw_ostream &OS) { |
200 | | OS << "Name: " << Str << "\n"; |
201 | | OS << " Hash Value: " << format("0x%x", HashValue) << "\n"; |
202 | | OS << " Symbol: "; |
203 | | if (Sym) |
204 | | OS << *Sym; |
205 | | else |
206 | | OS << "<none>"; |
207 | | OS << "\n"; |
208 | | for (HashDataContents *C : Data.Values) { |
209 | | OS << " Offset: " << C->Die->getOffset() << "\n"; |
210 | | OS << " Tag: " << dwarf::TagString(C->Die->getTag()) << "\n"; |
211 | | OS << " Flags: " << C->Flags << "\n"; |
212 | | } |
213 | | } |
214 | | |
215 | | void dump() { print(dbgs()); } |
216 | | #endif |
217 | | }; |
218 | | |
219 | | // Internal Functions |
220 | | void EmitHeader(AsmPrinter *); |
221 | | void EmitBuckets(AsmPrinter *); |
222 | | void EmitHashes(AsmPrinter *); |
223 | | void emitOffsets(AsmPrinter *, const MCSymbol *); |
224 | | void EmitData(AsmPrinter *, DwarfDebug *D); |
225 | | |
226 | | // Allocator for HashData and HashDataContents. |
227 | | BumpPtrAllocator Allocator; |
228 | | |
229 | | // Output Variables |
230 | | TableHeader Header; |
231 | | TableHeaderData HeaderData; |
232 | | std::vector<HashData *> Data; |
233 | | |
234 | | using StringEntries = StringMap<DataArray, BumpPtrAllocator &>; |
235 | | |
236 | | StringEntries Entries; |
237 | | |
238 | | // Buckets/Hashes/Offsets |
239 | | using HashList = std::vector<HashData *>; |
240 | | using BucketList = std::vector<HashList>; |
241 | | BucketList Buckets; |
242 | | HashList Hashes; |
243 | | |
244 | | // Public Implementation |
245 | | public: |
246 | | DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>); |
247 | | DwarfAccelTable(const DwarfAccelTable &) = delete; |
248 | | DwarfAccelTable &operator=(const DwarfAccelTable &) = delete; |
249 | | |
250 | | void AddName(DwarfStringPoolEntryRef Name, const DIE *Die, char Flags = 0); |
251 | | void FinalizeTable(AsmPrinter *, StringRef); |
252 | | void emit(AsmPrinter *, const MCSymbol *, DwarfDebug *); |
253 | | #ifndef NDEBUG |
254 | | void print(raw_ostream &OS); |
255 | | void dump() { print(dbgs()); } |
256 | | #endif |
257 | | }; |
258 | | |
259 | | } // end namespace llvm |
260 | | |
261 | | #endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H |