/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/AsmPrinter/DIEHash.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- llvm/CodeGen/DIEHash.cpp - Dwarf Hashing Framework ----------------===// |
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 DWARF4 hashing of DIEs. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "DIEHash.h" |
15 | | #include "ByteStreamer.h" |
16 | | #include "DwarfDebug.h" |
17 | | #include "llvm/ADT/ArrayRef.h" |
18 | | #include "llvm/ADT/StringRef.h" |
19 | | #include "llvm/BinaryFormat/Dwarf.h" |
20 | | #include "llvm/CodeGen/AsmPrinter.h" |
21 | | #include "llvm/CodeGen/DIE.h" |
22 | | #include "llvm/Support/Debug.h" |
23 | | #include "llvm/Support/Endian.h" |
24 | | #include "llvm/Support/MD5.h" |
25 | | #include "llvm/Support/raw_ostream.h" |
26 | | |
27 | | using namespace llvm; |
28 | | |
29 | | #define DEBUG_TYPE "dwarfdebug" |
30 | | |
31 | | /// \brief Grabs the string in whichever attribute is passed in and returns |
32 | | /// a reference to it. |
33 | 169 | static StringRef getDIEStringAttr(const DIE &Die, uint16_t Attr) { |
34 | 169 | // Iterate through all the attributes until we find the one we're |
35 | 169 | // looking for, if we can't find it return an empty string. |
36 | 169 | for (const auto &V : Die.values()) |
37 | 362 | if (362 V.getAttribute() == Attr362 ) |
38 | 105 | return V.getDIEString().getString(); |
39 | 64 | |
40 | 64 | return StringRef(""); |
41 | 64 | } |
42 | | |
43 | | /// \brief Adds the string in \p Str to the hash. This also hashes |
44 | | /// a trailing NULL with the string. |
45 | 236 | void DIEHash::addString(StringRef Str) { |
46 | 236 | DEBUG(dbgs() << "Adding string " << Str << " to hash.\n"); |
47 | 236 | Hash.update(Str); |
48 | 236 | Hash.update(makeArrayRef((uint8_t)'\0')); |
49 | 236 | } |
50 | | |
51 | | // FIXME: The LEB128 routines are copied and only slightly modified out of |
52 | | // LEB128.h. |
53 | | |
54 | | /// \brief Adds the unsigned in \p Value to the hash encoded as a ULEB128. |
55 | 1.75k | void DIEHash::addULEB128(uint64_t Value) { |
56 | 1.75k | DEBUG(dbgs() << "Adding ULEB128 " << Value << " to hash.\n"); |
57 | 1.75k | do { |
58 | 1.75k | uint8_t Byte = Value & 0x7f; |
59 | 1.75k | Value >>= 7; |
60 | 1.75k | if (Value != 0) |
61 | 0 | Byte |= 0x80; // Mark this byte to show that more bytes will follow. |
62 | 1.75k | Hash.update(Byte); |
63 | 1.75k | } while (Value != 0); |
64 | 1.75k | } |
65 | | |
66 | 84 | void DIEHash::addSLEB128(int64_t Value) { |
67 | 84 | DEBUG(dbgs() << "Adding ULEB128 " << Value << " to hash.\n"); |
68 | 84 | bool More; |
69 | 84 | do { |
70 | 84 | uint8_t Byte = Value & 0x7f; |
71 | 84 | Value >>= 7; |
72 | 83 | More = !((((Value == 0) && ((Byte & 0x40) == 0)) || |
73 | 1 | ((Value == -1) && 1 ((Byte & 0x40) != 0)1 ))); |
74 | 84 | if (More) |
75 | 0 | Byte |= 0x80; // Mark this byte to show that more bytes will follow. |
76 | 84 | Hash.update(Byte); |
77 | 84 | } while (More); |
78 | 84 | } |
79 | | |
80 | | /// \brief Including \p Parent adds the context of Parent to the hash.. |
81 | 19 | void DIEHash::addParentContext(const DIE &Parent) { |
82 | 19 | |
83 | 19 | DEBUG(dbgs() << "Adding parent context to hash...\n"); |
84 | 19 | |
85 | 19 | // [7.27.2] For each surrounding type or namespace beginning with the |
86 | 19 | // outermost such construct... |
87 | 19 | SmallVector<const DIE *, 1> Parents; |
88 | 19 | const DIE *Cur = &Parent; |
89 | 23 | while (Cur->getParent()23 ) { |
90 | 4 | Parents.push_back(Cur); |
91 | 4 | Cur = Cur->getParent(); |
92 | 4 | } |
93 | 19 | assert(Cur->getTag() == dwarf::DW_TAG_compile_unit || |
94 | 19 | Cur->getTag() == dwarf::DW_TAG_type_unit); |
95 | 19 | |
96 | 19 | // Reverse iterate over our list to go from the outermost construct to the |
97 | 19 | // innermost. |
98 | 19 | for (SmallVectorImpl<const DIE *>::reverse_iterator I = Parents.rbegin(), |
99 | 19 | E = Parents.rend(); |
100 | 23 | I != E23 ; ++I4 ) { |
101 | 4 | const DIE &Die = **I; |
102 | 4 | |
103 | 4 | // ... Append the letter "C" to the sequence... |
104 | 4 | addULEB128('C'); |
105 | 4 | |
106 | 4 | // ... Followed by the DWARF tag of the construct... |
107 | 4 | addULEB128(Die.getTag()); |
108 | 4 | |
109 | 4 | // ... Then the name, taken from the DW_AT_name attribute. |
110 | 4 | StringRef Name = getDIEStringAttr(Die, dwarf::DW_AT_name); |
111 | 4 | DEBUG(dbgs() << "... adding context: " << Name << "\n"); |
112 | 4 | if (!Name.empty()) |
113 | 1 | addString(Name); |
114 | 4 | } |
115 | 19 | } |
116 | | |
117 | | // Collect all of the attributes for a particular DIE in single structure. |
118 | 226 | void DIEHash::collectAttributes(const DIE &Die, DIEAttrs &Attrs) { |
119 | 226 | |
120 | 734 | for (const auto &V : Die.values()) { |
121 | 734 | DEBUG(dbgs() << "Attribute: " |
122 | 734 | << dwarf::AttributeString(V.getAttribute()) |
123 | 734 | << " added.\n"); |
124 | 734 | switch (V.getAttribute()) { |
125 | 734 | #define HANDLE_DIE_HASH_ATTR(NAME) \ |
126 | 382 | case dwarf::NAME: \ |
127 | 382 | Attrs.NAME = V; \ |
128 | 382 | break; |
129 | 734 | #include "DIEHashAttributes.def"734 |
130 | 352 | default: |
131 | 352 | break; |
132 | 226 | } |
133 | 226 | } |
134 | 226 | } |
135 | | |
136 | | void DIEHash::hashShallowTypeReference(dwarf::Attribute Attribute, |
137 | 26 | const DIE &Entry, StringRef Name) { |
138 | 26 | // append the letter 'N' |
139 | 26 | addULEB128('N'); |
140 | 26 | |
141 | 26 | // the DWARF attribute code (DW_AT_type or DW_AT_friend), |
142 | 26 | addULEB128(Attribute); |
143 | 26 | |
144 | 26 | // the context of the tag, |
145 | 26 | if (const DIE *Parent = Entry.getParent()) |
146 | 18 | addParentContext(*Parent); |
147 | 26 | |
148 | 26 | // the letter 'E', |
149 | 26 | addULEB128('E'); |
150 | 26 | |
151 | 26 | // and the name of the type. |
152 | 26 | addString(Name); |
153 | 26 | |
154 | 26 | // Currently DW_TAG_friends are not used by Clang, but if they do become so, |
155 | 26 | // here's the relevant spec text to implement: |
156 | 26 | // |
157 | 26 | // For DW_TAG_friend, if the referenced entry is the DW_TAG_subprogram, |
158 | 26 | // the context is omitted and the name to be used is the ABI-specific name |
159 | 26 | // of the subprogram (e.g., the mangled linker name). |
160 | 26 | } |
161 | | |
162 | | void DIEHash::hashRepeatedTypeReference(dwarf::Attribute Attribute, |
163 | 29 | unsigned DieNumber) { |
164 | 29 | // a) If T is in the list of [previously hashed types], use the letter |
165 | 29 | // 'R' as the marker |
166 | 29 | addULEB128('R'); |
167 | 29 | |
168 | 29 | addULEB128(Attribute); |
169 | 29 | |
170 | 29 | // and use the unsigned LEB128 encoding of [the index of T in the |
171 | 29 | // list] as the attribute value; |
172 | 29 | addULEB128(DieNumber); |
173 | 29 | } |
174 | | |
175 | | void DIEHash::hashDIEEntry(dwarf::Attribute Attribute, dwarf::Tag Tag, |
176 | 114 | const DIE &Entry) { |
177 | 114 | assert(Tag != dwarf::DW_TAG_friend && "No current LLVM clients emit friend " |
178 | 114 | "tags. Add support here when there's " |
179 | 114 | "a use case"); |
180 | 114 | // Step 5 |
181 | 114 | // If the tag in Step 3 is one of [the below tags] |
182 | 114 | if ((Tag == dwarf::DW_TAG_pointer_type || |
183 | 85 | Tag == dwarf::DW_TAG_reference_type || |
184 | 82 | Tag == dwarf::DW_TAG_rvalue_reference_type || |
185 | 81 | Tag == dwarf::DW_TAG_ptr_to_member_type) && |
186 | 114 | // and the referenced type (via the [below attributes]) |
187 | 114 | // FIXME: This seems overly restrictive, and causes hash mismatches |
188 | 114 | // there's a decl/def difference in the containing type of a |
189 | 114 | // ptr_to_member_type, but it's what DWARF says, for some reason. |
190 | 114 | Attribute == dwarf::DW_AT_type43 ) { |
191 | 38 | // ... has a DW_AT_name attribute, |
192 | 38 | StringRef Name = getDIEStringAttr(Entry, dwarf::DW_AT_name); |
193 | 38 | if (!Name.empty()38 ) { |
194 | 26 | hashShallowTypeReference(Attribute, Entry, Name); |
195 | 26 | return; |
196 | 26 | } |
197 | 88 | } |
198 | 88 | |
199 | 88 | unsigned &DieNumber = Numbering[&Entry]; |
200 | 88 | if (DieNumber88 ) { |
201 | 29 | hashRepeatedTypeReference(Attribute, DieNumber); |
202 | 29 | return; |
203 | 29 | } |
204 | 59 | |
205 | 59 | // otherwise, b) use the letter 'T' as the marker, ... |
206 | 59 | addULEB128('T'); |
207 | 59 | |
208 | 59 | addULEB128(Attribute); |
209 | 59 | |
210 | 59 | // ... process the type T recursively by performing Steps 2 through 7, and |
211 | 59 | // use the result as the attribute value. |
212 | 59 | DieNumber = Numbering.size(); |
213 | 59 | computeHash(Entry); |
214 | 59 | } |
215 | | |
216 | | // Hash all of the values in a block like set of values. This assumes that |
217 | | // all of the data is going to be added as integers. |
218 | 35 | void DIEHash::hashBlockData(const DIE::const_value_range &Values) { |
219 | 35 | for (const auto &V : Values) |
220 | 78 | Hash.update((uint64_t)V.getDIEInteger().getValue()); |
221 | 35 | } |
222 | | |
223 | | // Hash the contents of a loclistptr class. |
224 | 3 | void DIEHash::hashLocList(const DIELocList &LocList) { |
225 | 3 | HashingByteStreamer Streamer(*this); |
226 | 3 | DwarfDebug &DD = *AP->getDwarfDebug(); |
227 | 3 | const DebugLocStream &Locs = DD.getDebugLocs(); |
228 | 3 | for (const auto &Entry : Locs.getEntries(Locs.getList(LocList.getValue()))) |
229 | 4 | DD.emitDebugLocEntry(Streamer, Entry); |
230 | 3 | } |
231 | | |
232 | | // Hash an individual attribute \param Attr based on the type of attribute and |
233 | | // the form. |
234 | 382 | void DIEHash::hashAttribute(const DIEValue &Value, dwarf::Tag Tag) { |
235 | 382 | dwarf::Attribute Attribute = Value.getAttribute(); |
236 | 382 | |
237 | 382 | // Other attribute values use the letter 'A' as the marker, and the value |
238 | 382 | // consists of the form code (encoded as an unsigned LEB128 value) followed by |
239 | 382 | // the encoding of the value according to the form code. To ensure |
240 | 382 | // reproducibility of the signature, the set of forms used in the signature |
241 | 382 | // computation is limited to the following: DW_FORM_sdata, DW_FORM_flag, |
242 | 382 | // DW_FORM_string, and DW_FORM_block. |
243 | 382 | |
244 | 382 | switch (Value.getType()) { |
245 | 0 | case DIEValue::isNone: |
246 | 0 | llvm_unreachable("Expected valid DIEValue"); |
247 | 382 | |
248 | 382 | // 7.27 Step 3 |
249 | 382 | // ... An attribute that refers to another type entry T is processed as |
250 | 382 | // follows: |
251 | 114 | case DIEValue::isEntry: |
252 | 114 | hashDIEEntry(Attribute, Tag, Value.getDIEEntry().getEntry()); |
253 | 114 | break; |
254 | 99 | case DIEValue::isInteger: { |
255 | 99 | addULEB128('A'); |
256 | 99 | addULEB128(Attribute); |
257 | 99 | switch (Value.getForm()) { |
258 | 84 | case dwarf::DW_FORM_data1: |
259 | 84 | case dwarf::DW_FORM_data2: |
260 | 84 | case dwarf::DW_FORM_data4: |
261 | 84 | case dwarf::DW_FORM_data8: |
262 | 84 | case dwarf::DW_FORM_udata: |
263 | 84 | case dwarf::DW_FORM_sdata: |
264 | 84 | addULEB128(dwarf::DW_FORM_sdata); |
265 | 84 | addSLEB128((int64_t)Value.getDIEInteger().getValue()); |
266 | 84 | break; |
267 | 84 | // DW_FORM_flag_present is just flag with a value of one. We still give it a |
268 | 84 | // value so just use the value. |
269 | 15 | case dwarf::DW_FORM_flag_present: |
270 | 15 | case dwarf::DW_FORM_flag: |
271 | 15 | addULEB128(dwarf::DW_FORM_flag); |
272 | 15 | addULEB128((int64_t)Value.getDIEInteger().getValue()); |
273 | 15 | break; |
274 | 0 | default: |
275 | 0 | llvm_unreachable("Unknown integer form!"); |
276 | 99 | } |
277 | 99 | break; |
278 | 99 | } |
279 | 131 | case DIEValue::isString: |
280 | 131 | addULEB128('A'); |
281 | 131 | addULEB128(Attribute); |
282 | 131 | addULEB128(dwarf::DW_FORM_string); |
283 | 131 | addString(Value.getDIEString().getString()); |
284 | 131 | break; |
285 | 0 | case DIEValue::isInlineString: |
286 | 0 | addULEB128('A'); |
287 | 0 | addULEB128(Attribute); |
288 | 0 | addULEB128(dwarf::DW_FORM_string); |
289 | 0 | addString(Value.getDIEInlineString().getString()); |
290 | 0 | break; |
291 | 38 | case DIEValue::isBlock: |
292 | 38 | case DIEValue::isLoc: |
293 | 38 | case DIEValue::isLocList: |
294 | 38 | addULEB128('A'); |
295 | 38 | addULEB128(Attribute); |
296 | 38 | addULEB128(dwarf::DW_FORM_block); |
297 | 38 | if (Value.getType() == DIEValue::isBlock38 ) { |
298 | 1 | addULEB128(Value.getDIEBlock().ComputeSize(AP)); |
299 | 1 | hashBlockData(Value.getDIEBlock().values()); |
300 | 38 | } else if (37 Value.getType() == DIEValue::isLoc37 ) { |
301 | 34 | addULEB128(Value.getDIELoc().ComputeSize(AP)); |
302 | 34 | hashBlockData(Value.getDIELoc().values()); |
303 | 37 | } else { |
304 | 3 | // We could add the block length, but that would take |
305 | 3 | // a bit of work and not add a lot of uniqueness |
306 | 3 | // to the hash in some way we could test. |
307 | 3 | hashLocList(Value.getDIELocList()); |
308 | 3 | } |
309 | 38 | break; |
310 | 38 | // FIXME: It's uncertain whether or not we should handle this at the moment. |
311 | 0 | case DIEValue::isExpr: |
312 | 0 | case DIEValue::isLabel: |
313 | 0 | case DIEValue::isDelta: |
314 | 0 | llvm_unreachable("Add support for additional value types."); |
315 | 382 | } |
316 | 382 | } |
317 | | |
318 | | // Go through the attributes from \param Attrs in the order specified in 7.27.4 |
319 | | // and hash them. |
320 | 226 | void DIEHash::hashAttributes(const DIEAttrs &Attrs, dwarf::Tag Tag) { |
321 | 226 | #define HANDLE_DIE_HASH_ATTR(NAME) \ |
322 | 11.0k | { \ |
323 | 11.0k | if (Attrs.NAME) \ |
324 | 382 | hashAttribute(Attrs.NAME, Tag); \ |
325 | 11.0k | } |
326 | 226 | #include "DIEHashAttributes.def" |
327 | 226 | // FIXME: Add the extended attributes. |
328 | 226 | } |
329 | | |
330 | | // Add all of the attributes for \param Die to the hash. |
331 | 226 | void DIEHash::addAttributes(const DIE &Die) { |
332 | 226 | DIEAttrs Attrs = {}; |
333 | 226 | collectAttributes(Die, Attrs); |
334 | 226 | hashAttributes(Attrs, Die.getTag()); |
335 | 226 | } |
336 | | |
337 | 78 | void DIEHash::hashNestedType(const DIE &Die, StringRef Name) { |
338 | 78 | // 7.27 Step 7 |
339 | 78 | // ... append the letter 'S', |
340 | 78 | addULEB128('S'); |
341 | 78 | |
342 | 78 | // the tag of C, |
343 | 78 | addULEB128(Die.getTag()); |
344 | 78 | |
345 | 78 | // and the name. |
346 | 78 | addString(Name); |
347 | 78 | } |
348 | | |
349 | | // Compute the hash of a DIE. This is based on the type signature computation |
350 | | // given in section 7.27 of the DWARF4 standard. It is the md5 hash of a |
351 | | // flattened description of the DIE. |
352 | 226 | void DIEHash::computeHash(const DIE &Die) { |
353 | 226 | // Append the letter 'D', followed by the DWARF tag of the DIE. |
354 | 226 | addULEB128('D'); |
355 | 226 | addULEB128(Die.getTag()); |
356 | 226 | |
357 | 226 | // Add each of the attributes of the DIE. |
358 | 226 | addAttributes(Die); |
359 | 226 | |
360 | 226 | // Then hash each of the children of the DIE. |
361 | 196 | for (auto &C : Die.children()) { |
362 | 196 | // 7.27 Step 7 |
363 | 196 | // If C is a nested type entry or a member function entry, ... |
364 | 196 | if (isType(C.getTag()) || 196 C.getTag() == dwarf::DW_TAG_subprogram125 ) { |
365 | 127 | StringRef Name = getDIEStringAttr(C, dwarf::DW_AT_name); |
366 | 127 | // ... and has a DW_AT_name attribute |
367 | 127 | if (!Name.empty()127 ) { |
368 | 78 | hashNestedType(C, Name); |
369 | 78 | continue; |
370 | 78 | } |
371 | 118 | } |
372 | 118 | computeHash(C); |
373 | 118 | } |
374 | 226 | |
375 | 226 | // Following the last (or if there are no children), append a zero byte. |
376 | 226 | Hash.update(makeArrayRef((uint8_t)'\0')); |
377 | 226 | } |
378 | | |
379 | | /// This is based on the type signature computation given in section 7.27 of the |
380 | | /// DWARF4 standard. It is an md5 hash of the flattened description of the DIE |
381 | | /// with the inclusion of the full CU and all top level CU entities. |
382 | | // TODO: Initialize the type chain at 0 instead of 1 for CU signatures. |
383 | 28 | uint64_t DIEHash::computeCUSignature(StringRef DWOName, const DIE &Die) { |
384 | 28 | Numbering.clear(); |
385 | 28 | Numbering[&Die] = 1; |
386 | 28 | |
387 | 28 | if (!DWOName.empty()) |
388 | 8 | Hash.update(DWOName); |
389 | 28 | // Hash the DIE. |
390 | 28 | computeHash(Die); |
391 | 28 | |
392 | 28 | // Now return the result. |
393 | 28 | MD5::MD5Result Result; |
394 | 28 | Hash.final(Result); |
395 | 28 | |
396 | 28 | // ... take the least significant 8 bytes and return those. Our MD5 |
397 | 28 | // implementation always returns its results in little endian, so we actually |
398 | 28 | // need the "high" word. |
399 | 28 | return Result.high(); |
400 | 28 | } |
401 | | |
402 | | /// This is based on the type signature computation given in section 7.27 of the |
403 | | /// DWARF4 standard. It is an md5 hash of the flattened description of the DIE |
404 | | /// with the inclusion of additional forms not specifically called out in the |
405 | | /// standard. |
406 | 21 | uint64_t DIEHash::computeTypeSignature(const DIE &Die) { |
407 | 21 | Numbering.clear(); |
408 | 21 | Numbering[&Die] = 1; |
409 | 21 | |
410 | 21 | if (const DIE *Parent = Die.getParent()) |
411 | 1 | addParentContext(*Parent); |
412 | 21 | |
413 | 21 | // Hash the DIE. |
414 | 21 | computeHash(Die); |
415 | 21 | |
416 | 21 | // Now return the result. |
417 | 21 | MD5::MD5Result Result; |
418 | 21 | Hash.final(Result); |
419 | 21 | |
420 | 21 | // ... take the least significant 8 bytes and return those. Our MD5 |
421 | 21 | // implementation always returns its results in little endian, so we actually |
422 | 21 | // need the "high" word. |
423 | 21 | return Result.high(); |
424 | 21 | } |