[CodeView] Add support for type record content hashing

[zturner]

Summary

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

[zturner]

Added some doxygen comments explaining what this is for.

[zturner]

Added a minor sanity check to the unit test to make sure that different records in the same stream return different hashes.

[zturner]

Renames WeaklyHashedType to LocallyHashedType and ContentHashedType to GloballyHashedType to better express where the strength and weakness lies in the hash.

[zturner]

Updated the interface to allow you to specify previous types and previous ids separately. This isn't used yet, but should be supported since it's possible to want to compute global hashes for streams where types and ids are already split.

Also, +ruiu since rnk is OOO.

[ruiu]

llvm/include/llvm/DebugInfo/CodeView/TypeHashing.h

30

Is this used when an object file doesn't have type record hash values?

If you use 64-bit values as unique keys and want to maintain a probability of collision lower than 10^-9, for example, the maximum number of type records you can have is 190,000, according to [1]. Is this enough?

https://en.wikipedia.org/wiki/Birthday_problem#Probability_table

42

identify

[ruiu]

LGTM

Let's land this so that we can experiment. I still doubt if a noncryptographic tree hash is faster than SHA1, but that can be experimented once this patch is in.

[zturner]

In D40736#945605, @ruiu wrote:

LGTM

Let's land this so that we can experiment. I still doubt if a noncryptographic tree hash is faster than SHA1, but that can be experimented once this patch is in.

We can't compare tree vs non-tree. Only tree vs tree and non-tree vs non-tree. In those scenarios, noncryptographic hash function is always faster than SHA1.

Current algorithm uses non-cryptographic non-tree hash function. The new code will use cryptographic tree hash function. So hash computation gets slower (tree is slower than non-tree, cryptographic is slower than non-cryptographic), but the magic is that the work can be off-loaded to the compiler. The other thing that's easy to lose sight of is that it's not just the speed of computing the hash. It's also the cost of probing. Since our hashes are bucketed only on the lower 4 bytes, there's always going to be probes no matter what the hash function is. But with the tree hash, a probe gets much cheaper, because an equality comparison is just a 20-byte tree hash comparison, and not a massive full record comparison. On a large application, that could be several terabytes of memcmps which we can now eliminate.

Anyway, like you said we'll see after some more experimentation :) Thanks!

llvm/include/llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h

 #define LLVM_DEBUGINFO_CODEVIEW_MERGINGTYPETABLEBUILDER_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/DebugInfo/CodeView/CodeView.h"
 #include "llvm/DebugInfo/CodeView/SimpleTypeSerializer.h"
 #include "llvm/DebugInfo/CodeView/TypeCollection.h"
+#include "llvm/DebugInfo/CodeView/TypeHashing.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/Support/Allocator.h"
 #include <cassert>
 #include <cstdint>
 #include <memory>
 #include <vector>
 
 namespace llvm {
 namespace codeview {
 
 class ContinuationRecordBuilder;
-class TypeHasher;
-
-struct HashedType {
-  hash_code Hash;
-  ArrayRef<uint8_t> Data;
-  TypeIndex Index;
-};
 
 class MergingTypeTableBuilder : public TypeCollection {
   /// Storage for records.  These need to outlive the TypeTableBuilder.
   BumpPtrAllocator &RecordStorage;
 
   /// A serializer that can write non-continuation leaf types.  Only used as
   /// a convenience function so that we can provide an interface method to
   /// write an unserialized record.
   SimpleTypeSerializer SimpleSerializer;
 
   /// Hash table.
-  DenseSet<HashedType> HashedRecords;
+  DenseSet<WeaklyHashedType> HashedRecords;
 
   /// Contains a list of all records indexed by TypeIndex.toArrayIndex().
   SmallVector<ArrayRef<uint8_t>, 2> SeenRecords;
 
-  /// Contains a list of all hash codes index by TypeIndex.toArrayIndex().
-  SmallVector<hash_code, 2> SeenHashes;
-
 public:
   explicit MergingTypeTableBuilder(BumpPtrAllocator &Storage);
   ~MergingTypeTableBuilder();
 
   // TypeTableCollection overrides
   Optional<TypeIndex> getFirst() override;
   Optional<TypeIndex> getNext(TypeIndex Prev) override;
   CVType getType(TypeIndex Index) override;
   StringRef getTypeName(TypeIndex Index) override;
   bool contains(TypeIndex Index) override;
   uint32_t size() override;
   uint32_t capacity() override;
 
   // public interface
   void reset();
   TypeIndex nextTypeIndex() const;
 
   BumpPtrAllocator &getAllocator() { return RecordStorage; }
 
   ArrayRef<ArrayRef<uint8_t>> records() const;
-  ArrayRef<hash_code> hashes() const;
 
   TypeIndex insertRecordAs(hash_code Hash, ArrayRef<uint8_t> &Record);
   TypeIndex insertRecordBytes(ArrayRef<uint8_t> &Record);
   TypeIndex insertRecord(ContinuationRecordBuilder &Builder);
 
   template <typename T> TypeIndex writeLeafType(T &Record) {
     ArrayRef<uint8_t> Data = SimpleSerializer.serialize(Record);
     return insertRecordBytes(Data);
   }
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_MERGINGTYPETABLEBUILDER_H

llvm/include/llvm/DebugInfo/CodeView/TypeHashing.h

+//===- TypeHashing.h ---------------------------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEHASHING_H
+#define LLVM_DEBUGINFO_CODEVIEW_TYPEHASHING_H
+
+#include "llvm/DebugInfo/CodeView/CodeView.h"
+#include "llvm/DebugInfo/CodeView/TypeIndex.h"
+
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/Hashing.h"
+
+namespace llvm {
+namespace codeview {
+struct WeaklyHashedType {
+  hash_code Hash;
+  ArrayRef<uint8_t> RecordData;
+  TypeIndex Index;
+
+  static WeaklyHashedType hashType(TypeIndex Index,
+                                   ArrayRef<uint8_t> RecordData,
+                                   ArrayRef<WeaklyHashedType> PreviousTypes);
+};
+
+struct ContentHashedType {
+  ContentHashedType() = default;
+  ContentHashedType(StringRef H, TypeIndex TI)
+      : ContentHashedType(ArrayRef<uint8_t>(H.bytes_begin(), H.bytes_end()),
+                          TI) {}
+  ContentHashedType(ArrayRef<uint8_t> H, TypeIndex TI) : Index(TI) {
+    assert(H.size() == 20);
+    ::memcpy(Hash.data(), H.data(), 20);
+  }
+  std::array<uint8_t, 20> Hash;
+  TypeIndex Index;
+
+  static ContentHashedType hashType(TypeIndex Index,
+                                    ArrayRef<uint8_t> RecordData,
+                                    ArrayRef<ContentHashedType> PreviousTypes);
+
+  template <typename Range>
+  static std::vector<ContentHashedType> hashTypes(Range &&Records) {
+    std::vector<ContentHashedType> Hashes;
+    Hashes.reserve(std::distance(std::begin(Records), std::end(Records)));
+    TypeIndex TI(TypeIndex::FirstNonSimpleIndex);
+    for (const auto &R : Records)
+      Hashes.push_back(hashType(TI, R, Hashes));
+
+    return Hashes;
+  }
+};
+} // namespace codeview
+
+template <> struct DenseMapInfo<codeview::WeaklyHashedType> {
+  static codeview::WeaklyHashedType Empty;
+  static codeview::WeaklyHashedType Tombstone;
+
+  static codeview::WeaklyHashedType getEmptyKey() { return Empty; }
+
+  static codeview::WeaklyHashedType getTombstoneKey() { return Tombstone; }
+
+  static unsigned getHashValue(codeview::WeaklyHashedType Val) {
+    return Val.Hash;
+  }
+
+  static bool isEqual(codeview::WeaklyHashedType LHS,
+                      codeview::WeaklyHashedType RHS) {
+    if (LHS.Hash != RHS.Hash)
+      return false;
+    return LHS.RecordData == RHS.RecordData;
+  }
+};
+
+template <> struct DenseMapInfo<codeview::ContentHashedType> {
+  static codeview::ContentHashedType Empty;
+  static codeview::ContentHashedType Tombstone;
+
+  static codeview::ContentHashedType getEmptyKey() { return Empty; }
+
+  static codeview::ContentHashedType getTombstoneKey() { return Tombstone; }
+
+  static unsigned getHashValue(codeview::ContentHashedType Val) {
+    return *reinterpret_cast<const unsigned *>(Val.Hash.data());
+  }
+
+  static bool isEqual(codeview::WeaklyHashedType LHS,
+                      codeview::WeaklyHashedType RHS) {
+    return LHS.Hash == RHS.Hash;
+  }
+};
+
+} // namespace llvm
+
+#endif

llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h

public:
   bool isUnaligned() const {
     return !!(Attrs & uint32_t(PointerOptions::Unaligned));
   }
 
   TypeIndex ReferentType;
   uint32_t Attrs;
   Optional<MemberPointerInfo> MemberInfo;
 
+  void setAttrs(PointerKind PK, PointerMode PM, PointerOptions PO,
+                uint8_t Size) {
+    Attrs = calcAttrs(PK, PM, PO, Size);
+  }
+
 private:
   static uint32_t calcAttrs(PointerKind PK, PointerMode PM, PointerOptions PO,
                             uint8_t Size) {
     uint32_t A = 0;
     A |= static_cast<uint32_t>(PK);
     A |= static_cast<uint32_t>(PO);
     A |= (static_cast<uint32_t>(PM) << PointerModeShift);
     A |= (static_cast<uint32_t>(Size) << PointerSizeShift);

llvm/lib/DebugInfo/CodeView/CMakeLists.txt

add_llvm_library(LLVMDebugInfoCodeView
   SimpleTypeSerializer.cpp
   StringsAndChecksums.cpp
   SymbolRecordMapping.cpp
   SymbolDumper.cpp
   SymbolSerializer.cpp
   TypeDumpVisitor.cpp
   TypeIndex.cpp
   TypeIndexDiscovery.cpp
+  TypeHashing.cpp
   TypeRecordMapping.cpp
   TypeStreamMerger.cpp
   TypeTableCollection.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/CodeView
   )

llvm/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp

 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <cstring>
 
 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());
 }
 
 MergingTypeTableBuilder::MergingTypeTableBuilder(BumpPtrAllocator &Storage)
     : RecordStorage(Storage) {
   SeenRecords.reserve(4096);
-  SeenHashes.reserve(4096);
 }
 
 MergingTypeTableBuilder::~MergingTypeTableBuilder() = default;
 
 Optional<TypeIndex> MergingTypeTableBuilder::getFirst() {
   if (empty())
     return None;
 

 uint32_t MergingTypeTableBuilder::size() { return SeenRecords.size(); }
 
 uint32_t MergingTypeTableBuilder::capacity() { return SeenRecords.size(); }
 
 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();
 }
 
 static inline ArrayRef<uint8_t> stabilize(BumpPtrAllocator &Alloc,
                                           ArrayRef<uint8_t> Data) {
   uint8_t *Stable = Alloc.Allocate<uint8_t>(Data.size());
   memcpy(Stable, Data.data(), Data.size());
   return makeArrayRef(Stable, Data.size());
 }
 
 TypeIndex MergingTypeTableBuilder::insertRecordAs(hash_code Hash,
                                                   ArrayRef<uint8_t> &Record) {
   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()};
+  WeaklyHashedType TempHashedType = {Hash, Record, nextTypeIndex()};
   auto Result = HashedRecords.insert(TempHashedType);
 
   if (Result.second) {
-    Result.first->Data = stabilize(RecordStorage, Record);
-    SeenRecords.push_back(Result.first->Data);
-    SeenHashes.push_back(Result.first->Hash);
+    Result.first->RecordData = stabilize(RecordStorage, Record);
+    SeenRecords.push_back(Result.first->RecordData);
   }
 
   // Update the caller's copy of Record to point a stable copy.
-  Record = Result.first->Data;
+  Record = Result.first->RecordData;
   return Result.first->Index;
 }
 
 TypeIndex
 MergingTypeTableBuilder::insertRecordBytes(ArrayRef<uint8_t> &Record) {
   return insertRecordAs(hash_value(Record), Record);
 }
 

llvm/lib/DebugInfo/CodeView/TypeHashing.cpp

+//===- 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;
+
+WeaklyHashedType DenseMapInfo<WeaklyHashedType>::Empty{
+    0, {}, TypeIndex::None()};
+WeaklyHashedType DenseMapInfo<WeaklyHashedType>::Tombstone{
+    hash_code(-1), {}, TypeIndex::None()};
+
+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};
+
+ContentHashedType DenseMapInfo<ContentHashedType>::Empty{EmptyHash,
+                                                         TypeIndex::None()};
+ContentHashedType DenseMapInfo<ContentHashedType>::Tombstone{TombstoneHash,
+                                                             TypeIndex::None()};
+
+WeaklyHashedType
+WeaklyHashedType::hashType(TypeIndex Index, ArrayRef<uint8_t> RecordData,
+                           ArrayRef<WeaklyHashedType> PreviousTypes) {
+  return {llvm::hash_value(RecordData), RecordData, Index};
+}
+
+ContentHashedType
+ContentHashedType::hashType(TypeIndex Index, ArrayRef<uint8_t> RecordData,
+                            ArrayRef<ContentHashedType> PreviousTypes) {
+  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 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 = PreviousTypes[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(), Index};
+}

llvm/unittests/DebugInfo/CodeView/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   DebugInfoCodeView
   )
 
 set(DebugInfoCodeViewSources
   RandomAccessVisitorTest.cpp
+  TypeHashingTest.cpp
   TypeIndexDiscoveryTest.cpp
   )
 
 add_llvm_unittest(DebugInfoCodeViewTests
   ${DebugInfoCodeViewSources}
   )
 
 target_link_libraries(DebugInfoCodeViewTests LLVMTestingSupport)
 No newline at end of file

llvm/unittests/DebugInfo/CodeView/TypeHashingTest.cpp

+//===- llvm/unittest/DebugInfo/CodeView/TypeHashingTest.cpp ---------------===//
+//
+//                     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/AppendingTypeTableBuilder.h"
+
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+static TypeIndex createPointerRecord(AppendingTypeTableBuilder &Builder,
+                                     TypeIndex TI) {
+  PointerRecord PR(TypeRecordKind::Pointer);
+  PR.setAttrs(PointerKind::Near32, PointerMode::Pointer, PointerOptions::None,
+              4);
+  PR.ReferentType = TI;
+  return Builder.writeLeafType(PR);
+}
+
+static TypeIndex createArgListRecord(AppendingTypeTableBuilder &Builder,
+                                     TypeIndex Q, TypeIndex R) {
+  ArgListRecord AR(TypeRecordKind::ArgList);
+  AR.ArgIndices.push_back(Q);
+  AR.ArgIndices.push_back(R);
+  return Builder.writeLeafType(AR);
+}
+
+static TypeIndex createProcedureRecord(AppendingTypeTableBuilder &Builder,
+                                       uint32_t ParamCount, TypeIndex Return,
+                                       TypeIndex ArgList) {
+  ProcedureRecord PR(TypeRecordKind::Procedure);
+  PR.ArgumentList = ArgList;
+  PR.CallConv = CallingConvention::NearC;
+  PR.Options = FunctionOptions::None;
+  PR.ParameterCount = ParamCount;
+  PR.ReturnType = Return;
+  return Builder.writeLeafType(PR);
+}
+
+static ArrayRef<uint8_t> hash_of(ArrayRef<ContentHashedType> Hashes,
+                                 TypeIndex TI) {
+  return Hashes[TI.toArrayIndex()].Hash;
+}
+
+TEST(TypeHashingTest, ContentHash) {
+  SimpleTypeSerializer Serializer;
+
+  TypeIndex CharStar(SimpleTypeKind::SignedCharacter,
+                     SimpleTypeMode::NearPointer32);
+
+  BumpPtrAllocator Alloc;
+  AppendingTypeTableBuilder Ordering1(Alloc);
+  AppendingTypeTableBuilder Ordering2(Alloc);
+
+  TypeIndex CharP(SimpleTypeKind::SignedCharacter, SimpleTypeMode::NearPointer);
+  TypeIndex IntP(SimpleTypeKind::Int32, SimpleTypeMode::NearPointer);
+  TypeIndex DoubleP(SimpleTypeKind::Float64, SimpleTypeMode::NearPointer);
+
+  // We're going to the same type sequence with two different orderings, and
+  // then confirm all records are hashed the same.
+
+  TypeIndex CharPP[2];
+  TypeIndex IntPP[2];
+  TypeIndex IntPPP[2];
+  TypeIndex DoublePP[2];
+  TypeIndex Args[2];
+  TypeIndex Proc[2];
+
+  // Ordering 1
+  // ----------------------------------------
+  // LF_POINTER             0x1000   {char**}
+  //   Referent = char*
+  // LF_POINTER             0x1001   {int**}
+  //   Referent = int*
+  // LF_POINTER             0x1002   {int***}
+  //   Referent = 0x1001
+  // LF_ARGLIST             0x1003   {(char**, int***)}
+  //   Arg[0] = 0x1000
+  //   Arg[1] = 0x1002
+  // LF_PROCEDURE           0x1004   {int** func(char**, int***)}
+  //   ArgList = 0x1003
+  //   ReturnType = 0x1001
+  std::vector<ContentHashedType> Ordering1Hashes;
+  CharPP[0] = createPointerRecord(Ordering1, CharP);
+  IntPP[0] = createPointerRecord(Ordering1, IntP);
+  IntPPP[0] = createPointerRecord(Ordering1, IntPP[0]);
+  Args[0] = createArgListRecord(Ordering1, CharPP[0], IntPPP[0]);
+  Proc[0] = createProcedureRecord(Ordering1, 2, IntPP[0], Args[0]);
+
+  ASSERT_EQ(0x1000U, CharPP[0].getIndex());
+  ASSERT_EQ(0x1001U, IntPP[0].getIndex());
+  ASSERT_EQ(0x1002U, IntPPP[0].getIndex());
+  ASSERT_EQ(0x1003U, Args[0].getIndex());
+  ASSERT_EQ(0x1004U, Proc[0].getIndex());
+
+  auto Hashes1 = ContentHashedType::hashTypes(Ordering1.records());
+
+  // Ordering 2
+  // ----------------------------------------
+  // LF_POINTER             0x1000   {int**}
+  //   Referent = int*
+  // LF_POINTER             0x1001   {int***}
+  //   Referent = 0x1000
+  // LF_POINTER             0x1002   {char**}
+  //   Referent = char*
+  // LF_POINTER             0x1003   {double**}
+  //   Referent = double*
+  // LF_ARGLIST             0x1004   {(char**, int***)}
+  //   Arg[0] = 0x1002
+  //   Arg[1] = 0x1001
+  // LF_PROCEDURE           0x1005   {int** func(char**, int***)}
+  //   ArgList = 0x1004
+  //   ReturnType = 0x1000
+  IntPP[1] = createPointerRecord(Ordering2, IntP);
+  IntPPP[1] = createPointerRecord(Ordering2, IntPP[1]);
+  CharPP[1] = createPointerRecord(Ordering2, CharP);
+  DoublePP[1] = createPointerRecord(Ordering2, DoubleP);
+  Args[1] = createArgListRecord(Ordering2, CharPP[1], IntPPP[1]);
+  Proc[1] = createProcedureRecord(Ordering2, 2, IntPP[1], Args[1]);
+  auto Hashes2 = ContentHashedType::hashTypes(Ordering2.records());
+
+  ASSERT_EQ(0x1000U, IntPP[1].getIndex());
+  ASSERT_EQ(0x1001U, IntPPP[1].getIndex());
+  ASSERT_EQ(0x1002U, CharPP[1].getIndex());
+  ASSERT_EQ(0x1003U, DoublePP[1].getIndex());
+  ASSERT_EQ(0x1004U, Args[1].getIndex());
+  ASSERT_EQ(0x1005U, Proc[1].getIndex());
+
+  EXPECT_EQ(hash_of(Hashes1, IntPP[0]), hash_of(Hashes2, IntPP[1]));
+  EXPECT_EQ(hash_of(Hashes1, IntPPP[0]), hash_of(Hashes2, IntPPP[1]));
+  EXPECT_EQ(hash_of(Hashes1, CharPP[0]), hash_of(Hashes2, CharPP[1]));
+  EXPECT_EQ(hash_of(Hashes1, Args[0]), hash_of(Hashes2, Args[1]));
+  EXPECT_EQ(hash_of(Hashes1, Proc[0]), hash_of(Hashes2, Proc[1]));
+}