LCOV - code coverage report
Current view: top level - lib/CodeGen/AsmPrinter - DIEHash.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 162 176 92.0 %
Date: 2017-09-14 15:23:50 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             : /// \brief Grabs the string in whichever attribute is passed in and returns
      32             : /// a reference to it.
      33         150 : 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         842 :   for (const auto &V : Die.values())
      37         321 :     if (V.getAttribute() == Attr)
      38         200 :       return V.getDIEString().getString();
      39             : 
      40          50 :   return StringRef("");
      41             : }
      42             : 
      43             : /// \brief Adds the string in \p Str to the hash. This also hashes
      44             : /// a trailing NULL with the string.
      45         228 : void DIEHash::addString(StringRef Str) {
      46             :   DEBUG(dbgs() << "Adding string " << Str << " to hash.\n");
      47         228 :   Hash.update(Str);
      48         456 :   Hash.update(makeArrayRef((uint8_t)'\0'));
      49         228 : }
      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        1670 : void DIEHash::addULEB128(uint64_t Value) {
      56             :   DEBUG(dbgs() << "Adding ULEB128 " << Value << " to hash.\n");
      57             :   do {
      58        1670 :     uint8_t Byte = Value & 0x7f;
      59        1670 :     Value >>= 7;
      60        1670 :     if (Value != 0)
      61           0 :       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
      62        3340 :     Hash.update(Byte);
      63        1670 :   } while (Value != 0);
      64        1670 : }
      65             : 
      66          84 : void DIEHash::addSLEB128(int64_t Value) {
      67             :   DEBUG(dbgs() << "Adding ULEB128 " << Value << " to hash.\n");
      68             :   bool More;
      69          84 :   do {
      70          84 :     uint8_t Byte = Value & 0x7f;
      71          84 :     Value >>= 7;
      72          84 :     More = !((((Value == 0) && ((Byte & 0x40) == 0)) ||
      73           1 :               ((Value == -1) && ((Byte & 0x40) != 0))));
      74             :     if (More)
      75           0 :       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
      76         168 :     Hash.update(Byte);
      77             :   } 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             : 
      83             :   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          38 :   SmallVector<const DIE *, 1> Parents;
      88          19 :   const DIE *Cur = &Parent;
      89          27 :   while (Cur->getParent()) {
      90           4 :     Parents.push_back(Cur);
      91           4 :     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          19 :   for (SmallVectorImpl<const DIE *>::reverse_iterator I = Parents.rbegin(),
      99          19 :                                                       E = Parents.rend();
     100          23 :        I != E; ++I) {
     101           4 :     const DIE &Die = **I;
     102             : 
     103             :     // ... Append the letter "C" to the sequence...
     104           4 :     addULEB128('C');
     105             : 
     106             :     // ... Followed by the DWARF tag of the construct...
     107           4 :     addULEB128(Die.getTag());
     108             : 
     109             :     // ... Then the name, taken from the DW_AT_name attribute.
     110           4 :     StringRef Name = getDIEStringAttr(Die, dwarf::DW_AT_name);
     111             :     DEBUG(dbgs() << "... adding context: " << Name << "\n");
     112           4 :     if (!Name.empty())
     113           1 :       addString(Name);
     114             :   }
     115          19 : }
     116             : 
     117             : // Collect all of the attributes for a particular DIE in single structure.
     118         211 : void DIEHash::collectAttributes(const DIE &Die, DIEAttrs &Attrs) {
     119             : 
     120        1814 :   for (const auto &V : Die.values()) {
     121             :     DEBUG(dbgs() << "Attribute: "
     122             :                  << dwarf::AttributeString(V.getAttribute())
     123             :                  << " added.\n");
     124         696 :     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         211 : }
     135             : 
     136          26 : void DIEHash::hashShallowTypeReference(dwarf::Attribute Attribute,
     137             :                                        const DIE &Entry, StringRef Name) {
     138             :   // append the letter 'N'
     139          26 :   addULEB128('N');
     140             : 
     141             :   // the DWARF attribute code (DW_AT_type or DW_AT_friend),
     142          26 :   addULEB128(Attribute);
     143             : 
     144             :   // the context of the tag,
     145          26 :   if (const DIE *Parent = Entry.getParent())
     146          18 :     addParentContext(*Parent);
     147             : 
     148             :   // the letter 'E',
     149          26 :   addULEB128('E');
     150             : 
     151             :   // and the name of the type.
     152          26 :   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          26 : }
     161             : 
     162          25 : 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          25 :   addULEB128('R');
     167             : 
     168          25 :   addULEB128(Attribute);
     169             : 
     170             :   // and use the unsigned LEB128 encoding of [the index of T in the
     171             :   // list] as the attribute value;
     172          25 :   addULEB128(DieNumber);
     173          25 : }
     174             : 
     175         106 : 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         212 :   if ((Tag == dwarf::DW_TAG_pointer_type ||
     183         106 :        Tag == dwarf::DW_TAG_reference_type ||
     184         185 :        Tag == dwarf::DW_TAG_rvalue_reference_type ||
     185          37 :        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          32 :     StringRef Name = getDIEStringAttr(Entry, dwarf::DW_AT_name);
     193          32 :     if (!Name.empty()) {
     194          26 :       hashShallowTypeReference(Attribute, Entry, Name);
     195          26 :       return;
     196             :     }
     197             :   }
     198             : 
     199         160 :   unsigned &DieNumber = Numbering[&Entry];
     200          80 :   if (DieNumber) {
     201          25 :     hashRepeatedTypeReference(Attribute, DieNumber);
     202          25 :     return;
     203             :   }
     204             : 
     205             :   // otherwise, b) use the letter 'T' as the marker, ...
     206          55 :   addULEB128('T');
     207             : 
     208          55 :   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         110 :   DieNumber = Numbering.size();
     213          55 :   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          35 : void DIEHash::hashBlockData(const DIE::const_value_range &Values) {
     219         226 :   for (const auto &V : Values)
     220         312 :     Hash.update((uint64_t)V.getDIEInteger().getValue());
     221          35 : }
     222             : 
     223             : // Hash the contents of a loclistptr class.
     224           1 : void DIEHash::hashLocList(const DIELocList &LocList) {
     225           1 :   HashingByteStreamer Streamer(*this);
     226           1 :   DwarfDebug &DD = *AP->getDwarfDebug();
     227           1 :   const DebugLocStream &Locs = DD.getDebugLocs();
     228           5 :   for (const auto &Entry : Locs.getEntries(Locs.getList(LocList.getValue())))
     229           2 :     DD.emitDebugLocEntry(Streamer, Entry);
     230           1 : }
     231             : 
     232             : // Hash an individual attribute \param Attr based on the type of attribute and
     233             : // the form.
     234         367 : void DIEHash::hashAttribute(const DIEValue &Value, dwarf::Tag Tag) {
     235         367 :   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         367 :   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         106 :   case DIEValue::isEntry:
     252         212 :     hashDIEEntry(Attribute, Tag, Value.getDIEEntry().getEntry());
     253         106 :     break;
     254          97 :   case DIEValue::isInteger: {
     255          97 :     addULEB128('A');
     256          97 :     addULEB128(Attribute);
     257          97 :     switch (Value.getForm()) {
     258          84 :     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          84 :       addULEB128(dwarf::DW_FORM_sdata);
     265         168 :       addSLEB128((int64_t)Value.getDIEInteger().getValue());
     266          84 :       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          13 :     case dwarf::DW_FORM_flag_present:
     270             :     case dwarf::DW_FORM_flag:
     271          13 :       addULEB128(dwarf::DW_FORM_flag);
     272          26 :       addULEB128((int64_t)Value.getDIEInteger().getValue());
     273          13 :       break;
     274           0 :     default:
     275           0 :       llvm_unreachable("Unknown integer form!");
     276             :     }
     277             :     break;
     278             :   }
     279         128 :   case DIEValue::isString:
     280         128 :     addULEB128('A');
     281         128 :     addULEB128(Attribute);
     282         128 :     addULEB128(dwarf::DW_FORM_string);
     283         256 :     addString(Value.getDIEString().getString());
     284         128 :     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          36 :   case DIEValue::isBlock:
     292             :   case DIEValue::isLoc:
     293             :   case DIEValue::isLocList:
     294          36 :     addULEB128('A');
     295          36 :     addULEB128(Attribute);
     296          36 :     addULEB128(dwarf::DW_FORM_block);
     297          36 :     if (Value.getType() == DIEValue::isBlock) {
     298           1 :       addULEB128(Value.getDIEBlock().ComputeSize(AP));
     299           2 :       hashBlockData(Value.getDIEBlock().values());
     300          35 :     } else if (Value.getType() == DIEValue::isLoc) {
     301          34 :       addULEB128(Value.getDIELoc().ComputeSize(AP));
     302          68 :       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           1 :       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         367 : }
     317             : 
     318             : // Go through the attributes from \param Attrs in the order specified in 7.27.4
     319             : // and hash them.
     320         211 : 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         211 : }
     329             : 
     330             : // Add all of the attributes for \param Die to the hash.
     331         211 : void DIEHash::addAttributes(const DIE &Die) {
     332         422 :   DIEAttrs Attrs = {};
     333         211 :   collectAttributes(Die, Attrs);
     334         211 :   hashAttributes(Attrs, Die.getTag());
     335         211 : }
     336             : 
     337          73 : void DIEHash::hashNestedType(const DIE &Die, StringRef Name) {
     338             :   // 7.27 Step 7
     339             :   // ... append the letter 'S',
     340          73 :   addULEB128('S');
     341             : 
     342             :   // the tag of C,
     343          73 :   addULEB128(Die.getTag());
     344             : 
     345             :   // and the name.
     346          73 :   addString(Name);
     347          73 : }
     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         211 : void DIEHash::computeHash(const DIE &Die) {
     353             :   // Append the letter 'D', followed by the DWARF tag of the DIE.
     354         211 :   addULEB128('D');
     355         211 :   addULEB128(Die.getTag());
     356             : 
     357             :   // Add each of the attributes of the DIE.
     358         211 :   addAttributes(Die);
     359             : 
     360             :   // Then hash each of the children of the DIE.
     361         392 :   for (auto &C : Die.children()) {
     362             :     // 7.27 Step 7
     363             :     // If C is a nested type entry or a member function entry, ...
     364         181 :     if (isType(C.getTag()) || C.getTag() == dwarf::DW_TAG_subprogram) {
     365         114 :       StringRef Name = getDIEStringAttr(C, dwarf::DW_AT_name);
     366             :       // ... and has a DW_AT_name attribute
     367         187 :       if (!Name.empty()) {
     368          73 :         hashNestedType(C, Name);
     369          73 :         continue;
     370             :       }
     371             :     }
     372         108 :     computeHash(C);
     373             :   }
     374             : 
     375             :   // Following the last (or if there are no children), append a zero byte.
     376         422 :   Hash.update(makeArrayRef((uint8_t)'\0'));
     377         211 : }
     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          27 : uint64_t DIEHash::computeCUSignature(StringRef DWOName, const DIE &Die) {
     384          27 :   Numbering.clear();
     385          54 :   Numbering[&Die] = 1;
     386             : 
     387          27 :   if (!DWOName.empty())
     388           8 :     Hash.update(DWOName);
     389             :   // Hash the DIE.
     390          27 :   computeHash(Die);
     391             : 
     392             :   // Now return the result.
     393             :   MD5::MD5Result Result;
     394          27 :   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          27 :   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