DIEHash.cpp revision dd0cd3c4f468b55651bf33240667881bbed8d04c
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#define DEBUG_TYPE "dwarfdebug" 15 16#include "DIE.h" 17#include "DIEHash.h" 18#include "DwarfCompileUnit.h" 19#include "llvm/ADT/ArrayRef.h" 20#include "llvm/ADT/StringRef.h" 21#include "llvm/Support/Debug.h" 22#include "llvm/Support/Dwarf.h" 23#include "llvm/Support/Endian.h" 24#include "llvm/Support/MD5.h" 25#include "llvm/Support/raw_ostream.h" 26 27using namespace llvm; 28 29/// \brief Grabs the string in whichever attribute is passed in and returns 30/// a reference to it. 31static StringRef getDIEStringAttr(DIE *Die, uint16_t Attr) { 32 const SmallVectorImpl<DIEValue *> &Values = Die->getValues(); 33 const DIEAbbrev &Abbrevs = Die->getAbbrev(); 34 35 // Iterate through all the attributes until we find the one we're 36 // looking for, if we can't find it return an empty string. 37 for (size_t i = 0; i < Values.size(); ++i) { 38 if (Abbrevs.getData()[i].getAttribute() == Attr) { 39 DIEValue *V = Values[i]; 40 assert(isa<DIEString>(V) && "String requested. Not a string."); 41 DIEString *S = cast<DIEString>(V); 42 return S->getString(); 43 } 44 } 45 return StringRef(""); 46} 47 48/// \brief Adds the string in \p Str to the hash. This also hashes 49/// a trailing NULL with the string. 50void DIEHash::addString(StringRef Str) { 51 DEBUG(dbgs() << "Adding string " << Str << " to hash.\n"); 52 Hash.update(Str); 53 Hash.update(makeArrayRef((uint8_t)'\0')); 54} 55 56// FIXME: The LEB128 routines are copied and only slightly modified out of 57// LEB128.h. 58 59/// \brief Adds the unsigned in \p Value to the hash encoded as a ULEB128. 60void DIEHash::addULEB128(uint64_t Value) { 61 DEBUG(dbgs() << "Adding ULEB128 " << Value << " to hash.\n"); 62 do { 63 uint8_t Byte = Value & 0x7f; 64 Value >>= 7; 65 if (Value != 0) 66 Byte |= 0x80; // Mark this byte to show that more bytes will follow. 67 Hash.update(Byte); 68 } while (Value != 0); 69} 70 71/// \brief Including \p Parent adds the context of Parent to the hash.. 72void DIEHash::addParentContext(DIE *Parent) { 73 74 DEBUG(dbgs() << "Adding parent context to hash...\n"); 75 76 // [7.27.2] For each surrounding type or namespace beginning with the 77 // outermost such construct... 78 SmallVector<DIE *, 1> Parents; 79 while (Parent->getTag() != dwarf::DW_TAG_compile_unit) { 80 Parents.push_back(Parent); 81 Parent = Parent->getParent(); 82 } 83 84 // Reverse iterate over our list to go from the outermost construct to the 85 // innermost. 86 for (SmallVectorImpl<DIE *>::reverse_iterator I = Parents.rbegin(), 87 E = Parents.rend(); 88 I != E; ++I) { 89 DIE *Die = *I; 90 91 // ... Append the letter "C" to the sequence... 92 addULEB128('C'); 93 94 // ... Followed by the DWARF tag of the construct... 95 addULEB128(Die->getTag()); 96 97 // ... Then the name, taken from the DW_AT_name attribute. 98 StringRef Name = getDIEStringAttr(Die, dwarf::DW_AT_name); 99 DEBUG(dbgs() << "... adding context: " << Name << "\n"); 100 if (!Name.empty()) 101 addString(Name); 102 } 103} 104 105/// This is based on the type signature computation given in section 7.27 of the 106/// DWARF4 standard. It is the md5 hash of a flattened description of the DIE 107/// with the exception that we are hashing only the context and the name of the 108/// type. 109uint64_t DIEHash::computeDIEODRSignature(DIE *Die) { 110 111 // Add the contexts to the hash. We won't be computing the ODR hash for 112 // function local types so it's safe to use the generic context hashing 113 // algorithm here. 114 // FIXME: If we figure out how to account for linkage in some way we could 115 // actually do this with a slight modification to the parent hash algorithm. 116 DIE *Parent = Die->getParent(); 117 if (Parent) 118 addParentContext(Parent); 119 120 // Add the current DIE information. 121 122 // Add the DWARF tag of the DIE. 123 addULEB128(Die->getTag()); 124 125 // Add the name of the type to the hash. 126 addString(getDIEStringAttr(Die, dwarf::DW_AT_name)); 127 128 // Now get the result. 129 MD5::MD5Result Result; 130 Hash.final(Result); 131 132 // ... take the least significant 8 bytes and return those. Our MD5 133 // implementation always returns its results in little endian, swap bytes 134 // appropriately. 135 return *reinterpret_cast<support::ulittle64_t *>(Result + 8); 136} 137