LCOV - code coverage report
Current view: top level - include/llvm/DebugInfo/CodeView - TypeHashing.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 24 28 85.7 %
Date: 2018-05-20 00:06:23 Functions: 6 8 75.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- TypeHashing.h ---------------------------------------------*- 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             : #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEHASHING_H
      11             : #define LLVM_DEBUGINFO_CODEVIEW_TYPEHASHING_H
      12             : 
      13             : #include "llvm/ADT/DenseMapInfo.h"
      14             : #include "llvm/ADT/Hashing.h"
      15             : 
      16             : #include "llvm/DebugInfo/CodeView/CodeView.h"
      17             : #include "llvm/DebugInfo/CodeView/TypeCollection.h"
      18             : #include "llvm/DebugInfo/CodeView/TypeIndex.h"
      19             : 
      20             : #include "llvm/Support/FormatProviders.h"
      21             : 
      22             : #include <type_traits>
      23             : 
      24             : namespace llvm {
      25             : namespace codeview {
      26             : 
      27             : /// A locally hashed type represents a straightforward hash code of a serialized
      28             : /// record.  The record is simply serialized, and then the bytes are hashed by
      29             : /// a standard algorithm.  This is sufficient for the case of de-duplicating
      30             : /// records within a single sequence of types, because if two records both have
      31             : /// a back-reference to the same type in the same stream, they will both have
      32             : /// the same numeric value for the TypeIndex of the back reference.
      33             : struct LocallyHashedType {
      34             :   hash_code Hash;
      35             :   ArrayRef<uint8_t> RecordData;
      36             : 
      37             :   /// Given a type, compute its local hash.
      38             :   static LocallyHashedType hashType(ArrayRef<uint8_t> RecordData);
      39             : 
      40             :   /// Given a sequence of types, compute all of the local hashes.
      41             :   template <typename Range>
      42             :   static std::vector<LocallyHashedType> hashTypes(Range &&Records) {
      43             :     std::vector<LocallyHashedType> Hashes;
      44             :     Hashes.reserve(std::distance(std::begin(Records), std::end(Records)));
      45             :     for (const auto &R : Records)
      46             :       Hashes.push_back(hashType(R));
      47             : 
      48             :     return Hashes;
      49             :   }
      50             : 
      51             :   static std::vector<LocallyHashedType>
      52             :   hashTypeCollection(TypeCollection &Types) {
      53             :     std::vector<LocallyHashedType> Hashes;
      54          13 :     Types.ForEachRecord([&Hashes](TypeIndex TI, const CVType &Type) {
      55          22 :       Hashes.push_back(hashType(Type.RecordData));
      56          11 :     });
      57             :     return Hashes;
      58             :   }
      59             : };
      60             : 
      61             : enum class GlobalTypeHashAlg : uint16_t {
      62             :   SHA1 = 0, // standard 20-byte SHA1 hash
      63             :   SHA1_8    // last 8-bytes of standard SHA1 hash
      64             : };
      65             : 
      66             : /// A globally hashed type represents a hash value that is sufficient to
      67             : /// uniquely identify a record across multiple type streams or type sequences.
      68             : /// This works by, for any given record A which references B, replacing the
      69             : /// TypeIndex that refers to B with a previously-computed global hash for B.  As
      70             : /// this is a recursive algorithm (e.g. the global hash of B also depends on the
      71             : /// global hashes of the types that B refers to), a global hash can uniquely
      72             : /// identify identify that A occurs in another stream that has a completely
      73             : /// different graph structure.  Although the hash itself is slower to compute,
      74             : /// probing is much faster with a globally hashed type, because the hash itself
      75             : /// is considered "as good as" the original type.  Since type records can be
      76             : /// quite large, this makes the equality comparison of the hash much faster than
      77             : /// equality comparison of a full record.
      78             : struct GloballyHashedType {
      79             :   GloballyHashedType() = default;
      80             :   GloballyHashedType(StringRef H)
      81             :       : GloballyHashedType(ArrayRef<uint8_t>(H.bytes_begin(), H.bytes_end())) {}
      82      198474 :   GloballyHashedType(ArrayRef<uint8_t> H) {
      83             :     assert(H.size() == 8);
      84      199848 :     ::memcpy(Hash.data(), H.data(), 8);
      85             :   }
      86             :   std::array<uint8_t, 8> Hash;
      87             : 
      88             :   /// Given a sequence of bytes representing a record, compute a global hash for
      89             :   /// this record.  Due to the nature of global hashes incorporating the hashes
      90             :   /// of referenced records, this function requires a list of types and ids
      91             :   /// that RecordData might reference, indexable by TypeIndex.
      92             :   static GloballyHashedType hashType(ArrayRef<uint8_t> RecordData,
      93             :                                      ArrayRef<GloballyHashedType> PreviousTypes,
      94             :                                      ArrayRef<GloballyHashedType> PreviousIds);
      95             : 
      96             :   /// Given a sequence of bytes representing a record, compute a global hash for
      97             :   /// this record.  Due to the nature of global hashes incorporating the hashes
      98             :   /// of referenced records, this function requires a list of types and ids
      99             :   /// that RecordData might reference, indexable by TypeIndex.
     100             :   static GloballyHashedType hashType(CVType Type,
     101             :                                      ArrayRef<GloballyHashedType> PreviousTypes,
     102             :                                      ArrayRef<GloballyHashedType> PreviousIds) {
     103          14 :     return hashType(Type.RecordData, PreviousTypes, PreviousIds);
     104             :   }
     105             : 
     106             :   /// Given a sequence of combined type and ID records, compute global hashes
     107             :   /// for each of them, returning the results in a vector of hashed types.
     108             :   template <typename Range>
     109           3 :   static std::vector<GloballyHashedType> hashTypes(Range &&Records) {
     110             :     std::vector<GloballyHashedType> Hashes;
     111          41 :     for (const auto &R : Records)
     112          50 :       Hashes.push_back(hashType(R, Hashes, Hashes));
     113             : 
     114           3 :     return Hashes;
     115             :   }
     116             : 
     117             :   /// Given a sequence of combined type and ID records, compute global hashes
     118             :   /// for each of them, returning the results in a vector of hashed types.
     119             :   template <typename Range>
     120             :   static std::vector<GloballyHashedType>
     121           0 :   hashIds(Range &&Records, ArrayRef<GloballyHashedType> TypeHashes) {
     122             :     std::vector<GloballyHashedType> IdHashes;
     123           0 :     for (const auto &R : Records)
     124           0 :       IdHashes.push_back(hashType(R, TypeHashes, IdHashes));
     125             : 
     126           0 :     return IdHashes;
     127             :   }
     128             : 
     129             :   static std::vector<GloballyHashedType>
     130             :   hashTypeCollection(TypeCollection &Types) {
     131             :     std::vector<GloballyHashedType> Hashes;
     132          13 :     Types.ForEachRecord([&Hashes](TypeIndex TI, const CVType &Type) {
     133          22 :       Hashes.push_back(hashType(Type.RecordData, Hashes, Hashes));
     134          11 :     });
     135             :     return Hashes;
     136             :   }
     137             : };
     138             : #if defined(_MSC_VER)
     139             : // is_trivially_copyable is not available in older versions of libc++, but it is
     140             : // available in all supported versions of MSVC, so at least this gives us some
     141             : // coverage.
     142             : static_assert(std::is_trivially_copyable<GloballyHashedType>::value,
     143             :               "GloballyHashedType must be trivially copyable so that we can "
     144             :               "reinterpret_cast arrays of hash data to arrays of "
     145             :               "GloballyHashedType");
     146             : #endif
     147             : } // namespace codeview
     148             : 
     149             : template <> struct DenseMapInfo<codeview::LocallyHashedType> {
     150             :   static codeview::LocallyHashedType Empty;
     151             :   static codeview::LocallyHashedType Tombstone;
     152             : 
     153        3139 :   static codeview::LocallyHashedType getEmptyKey() { return Empty; }
     154             : 
     155        1960 :   static codeview::LocallyHashedType getTombstoneKey() { return Tombstone; }
     156             : 
     157             :   static unsigned getHashValue(codeview::LocallyHashedType Val) {
     158        1952 :     return Val.Hash;
     159             :   }
     160             : 
     161             :   static bool isEqual(codeview::LocallyHashedType LHS,
     162             :                       codeview::LocallyHashedType RHS) {
     163        8774 :     if (LHS.Hash != RHS.Hash)
     164             :       return false;
     165             :     return LHS.RecordData == RHS.RecordData;
     166             :   }
     167             : };
     168             : 
     169             : template <> struct DenseMapInfo<codeview::GloballyHashedType> {
     170             :   static codeview::GloballyHashedType Empty;
     171             :   static codeview::GloballyHashedType Tombstone;
     172             : 
     173        2683 :   static codeview::GloballyHashedType getEmptyKey() { return Empty; }
     174             : 
     175        1392 :   static codeview::GloballyHashedType getTombstoneKey() { return Tombstone; }
     176             : 
     177             :   static unsigned getHashValue(codeview::GloballyHashedType Val) {
     178             :     return *reinterpret_cast<const unsigned *>(Val.Hash.data());
     179             :   }
     180             : 
     181             :   static bool isEqual(codeview::GloballyHashedType LHS,
     182             :                       codeview::GloballyHashedType RHS) {
     183             :     return LHS.Hash == RHS.Hash;
     184             :   }
     185             : };
     186             : 
     187             : template <> struct format_provider<codeview::LocallyHashedType> {
     188             : public:
     189             :   static void format(const codeview::LocallyHashedType &V,
     190             :                      llvm::raw_ostream &Stream, StringRef Style) {
     191          11 :     write_hex(Stream, V.Hash, HexPrintStyle::Upper, 8);
     192             :   }
     193             : };
     194             : 
     195             : template <> struct format_provider<codeview::GloballyHashedType> {
     196             : public:
     197          27 :   static void format(const codeview::GloballyHashedType &V,
     198             :                      llvm::raw_ostream &Stream, StringRef Style) {
     199         459 :     for (uint8_t B : V.Hash) {
     200         216 :       write_hex(Stream, B, HexPrintStyle::Upper, 2);
     201             :     }
     202          27 :   }
     203             : };
     204             : 
     205             : } // namespace llvm
     206             : 
     207             : #endif

Generated by: LCOV version 1.13