LCOV - code coverage report
Current view: top level - lib/CodeGen/AsmPrinter - DIEHash.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 159 171 93.0 %
Date: 2018-07-13 00:08:38 Functions: 18 18 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13