[CodeView] Add support for content hashing CodeView type records.

Currently nothing uses this, but this at least gets the core
algorithm in, and adds some test to demonstrate correctness.

Differential Revision: https://reviews.llvm.org/D40736

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@319854 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 83 insertions, 34 deletions

diff --git a/lib/DebugInfo/CodeView/CMakeLists.txt b/lib/DebugInfo/CodeView/CMakeLists.txt
index 7d18c98bdc3..c3d79c0d6e6 100644
--- a/lib/DebugInfo/CodeView/CMakeLists.txt
+++ b/lib/DebugInfo/CodeView/CMakeLists.txt
@@ -32,6 +32,7 @@ add_llvm_library(LLVMDebugInfoCodeView
   TypeDumpVisitor.cpp
   TypeIndex.cpp
   TypeIndexDiscovery.cpp
+  TypeHashing.cpp
   TypeRecordMapping.cpp
   TypeStreamMerger.cpp
   TypeTableCollection.cpp
diff --git a/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp b/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp
index 514d55aed0b..8aee4aa2e2a 100644
--- a/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp
+++ b/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp
@@ -28,27 +28,6 @@
 using namespace llvm;
 using namespace llvm::codeview;
 
-static HashedType Empty{0, {}, TypeIndex::None()};
-static HashedType Tombstone{hash_code(-1), {}, TypeIndex::None()};
-
-namespace llvm {
-
-template <> struct DenseMapInfo<HashedType> {
-  static inline HashedType getEmptyKey() { return Empty; }
-
-  static inline HashedType getTombstoneKey() { return Tombstone; }
-
-  static unsigned getHashValue(HashedType Val) { return Val.Hash; }
-
-  static bool isEqual(HashedType LHS, HashedType RHS) {
-    if (RHS.Hash != LHS.Hash)
-      return false;
-    return RHS.Data == LHS.Data;
-  }
-};
-
-} // end namespace llvm
-
 TypeIndex MergingTypeTableBuilder::nextTypeIndex() const {
   return TypeIndex::fromArrayIndex(SeenRecords.size());
 }
@@ -56,7 +35,6 @@ TypeIndex MergingTypeTableBuilder::nextTypeIndex() const {
 MergingTypeTableBuilder::MergingTypeTableBuilder(BumpPtrAllocator &Storage)
     : RecordStorage(Storage) {
   SeenRecords.reserve(4096);
-  SeenHashes.reserve(4096);
 }
 
 MergingTypeTableBuilder::~MergingTypeTableBuilder() = default;
@@ -102,13 +80,8 @@ ArrayRef<ArrayRef<uint8_t>> MergingTypeTableBuilder::records() const {
   return SeenRecords;
 }
 
-ArrayRef<hash_code> MergingTypeTableBuilder::hashes() const {
-  return SeenHashes;
-}
-
 void MergingTypeTableBuilder::reset() {
   HashedRecords.clear();
-  SeenHashes.clear();
   SeenRecords.clear();
 }
 
@@ -124,18 +97,19 @@ TypeIndex MergingTypeTableBuilder::insertRecordAs(hash_code Hash,
   assert(Record.size() < UINT32_MAX && "Record too big");
   assert(Record.size() % 4 == 0 && "Record is not aligned to 4 bytes!");
 
-  HashedType TempHashedType = {Hash, Record, nextTypeIndex()};
-  auto Result = HashedRecords.insert(TempHashedType);
+  LocallyHashedType WeakHash{Hash, Record};
+  auto Result = HashedRecords.try_emplace(WeakHash, nextTypeIndex());
 
   if (Result.second) {
-    Result.first->Data = stabilize(RecordStorage, Record);
-    SeenRecords.push_back(Result.first->Data);
-    SeenHashes.push_back(Result.first->Hash);
+    ArrayRef<uint8_t> RecordData = stabilize(RecordStorage, Record);
+    Result.first->first.RecordData = RecordData;
+    SeenRecords.push_back(RecordData);
   }
 
   // Update the caller's copy of Record to point a stable copy.
-  Record = Result.first->Data;
-  return Result.first->Index;
+  TypeIndex ActualTI = Result.first->second;
+  Record = SeenRecords[ActualTI.toArrayIndex()];
+  return ActualTI;
 }
 
 TypeIndex
diff --git a/lib/DebugInfo/CodeView/TypeHashing.cpp b/lib/DebugInfo/CodeView/TypeHashing.cpp
new file mode 100644
index 00000000000..f9ab0f3b339
--- /dev/null
+++ b/lib/DebugInfo/CodeView/TypeHashing.cpp
@@ -0,0 +1,74 @@
+//===- TypeHashing.cpp -------------------------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/CodeView/TypeHashing.h"
+
+#include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
+#include "llvm/Support/SHA1.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+LocallyHashedType DenseMapInfo<LocallyHashedType>::Empty{0, {}};
+LocallyHashedType DenseMapInfo<LocallyHashedType>::Tombstone{hash_code(-1), {}};
+
+static std::array<uint8_t, 20> EmptyHash;
+static std::array<uint8_t, 20> TombstoneHash = {
+    0xFF, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
+
+GloballyHashedType DenseMapInfo<GloballyHashedType>::Empty{EmptyHash};
+GloballyHashedType DenseMapInfo<GloballyHashedType>::Tombstone{TombstoneHash};
+
+LocallyHashedType LocallyHashedType::hashType(ArrayRef<uint8_t> RecordData) {
+  return {llvm::hash_value(RecordData), RecordData};
+}
+
+GloballyHashedType
+GloballyHashedType::hashType(ArrayRef<uint8_t> RecordData,
+                             ArrayRef<GloballyHashedType> PreviousTypes,
+                             ArrayRef<GloballyHashedType> PreviousIds) {
+  SmallVector<TiReference, 4> Refs;
+  discoverTypeIndices(RecordData, Refs);
+  SHA1 S;
+  S.init();
+  uint32_t Off = 0;
+  RecordData = RecordData.drop_front(sizeof(RecordPrefix));
+  for (const auto &Ref : Refs) {
+    // Hash any data that comes before this TiRef.
+    uint32_t PreLen = Ref.Offset - Off;
+    ArrayRef<uint8_t> PreData = RecordData.slice(Off, PreLen);
+    S.update(PreData);
+    auto Prev = (Ref.Kind == TiRefKind::IndexRef) ? PreviousIds : PreviousTypes;
+
+    auto RefData = RecordData.slice(Ref.Offset, Ref.Count * sizeof(TypeIndex));
+    // For each type index referenced, add in the previously computed hash
+    // value of that type.
+    ArrayRef<TypeIndex> Indices(
+        reinterpret_cast<const TypeIndex *>(RefData.data()), Ref.Count);
+    for (TypeIndex TI : Indices) {
+      ArrayRef<uint8_t> BytesToHash;
+      if (TI.isSimple() || TI.isNoneType()) {
+        const uint8_t *IndexBytes = reinterpret_cast<const uint8_t *>(&TI);
+        BytesToHash = makeArrayRef(IndexBytes, sizeof(TypeIndex));
+      } else {
+        BytesToHash = Prev[TI.toArrayIndex()].Hash;
+      }
+      S.update(BytesToHash);
+    }
+
+    Off = Ref.Offset + Ref.Count * sizeof(TypeIndex);
+  }
+
+  // Don't forget to add in any trailing bytes.
+  auto TrailingBytes = RecordData.drop_front(Off);
+  S.update(TrailingBytes);
+
+  return {S.final()};
+}