[PDB] Emit S_UDT records in LLD

[zturner]

Summary

This patch emits S_UDT records from LLD. These represent typedefs. The compiler emits these into the .debug$S section, and the linker must split these up between the PDB globals stream and PDB module stream, depending on whether it is a global typedef or a function local typedef.

Note there is a problem here, which is that we emit local typedefs using their fully qualified name, so we append the function name to the beginning. This is obviously wrong, and it is a simple fix, however it's orthogonal to this change so I'll submit that patch to the compiler in a followup.

[zturner]

Cleanup the test a little bit. Also added a CHECK-NOT: S_END line to make sure that the typedef we emit actually is inside the proper scope.

[zturner]

Update the diff for real.

[rnk]

lld/test/COFF/s_udt.test

2

Any particular reason for this to be an IR test that uses llc? LTO isn't involved, so you could either do a yaml input or an assembly file input. Which ever is more readable.

If you do want an IR test, can we name it .ll? We should be able to add .ll to the list of test case suffixes if it's not in there already.

llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp

52–59

I don't think we should assume xxHash64 doesn't have collisions. The space of 64-bit hashes is big, but it's not a content hash like SHA1, so it should be possible to construct some collisions. Someone has code to do it here: https://github.com/Cyan4973/xxHash/issues/54

If you don't want to add the collision resolution code because it's slow, at least try linking browser_tests with extra instrumentation code to detect collisions. If you find a collision, then we should keep the resolution code and add that as a test case. If you don't find a collision, then at least put a large comment here documenting our decision to sometimes drop typedefs with matching xxHash64 values.

Also, you might want to structure this code in such a way that it can be extended for S_CONSTANT, which also needs deduplication: https://bugs.llvm.org/show_bug.cgi?id=37933

[zturner]

llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp

52–59

The thing about collisions is that the consequences of a collision are that we end up with a few extra bytes in the PDB. So it seems unimportant to worry about a collision, even in the case that we do have collisions.

[aganea]

lld/test/COFF/s_udt.test

35

Could you possibly add here the source code that generated this test?

llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp

48

Could someone insert twice the same S_UDT record by calling GSIStreamBuilder::addGlobalSymbol(const UDTSym &Sym)? Replace Records.push_back by a call to addSymbol in that case.

[aganea]

llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp

52–59

Unless I'm missing something, @rnk is right: the PDB will not receive a colliding record. If you're inserting a S_UDT 'typedef char B' with hash 0x2, and a previous 'typedef int A' with same hash 0x2 was already there in UdtHashes, the new record 'B' will not make it to Records.push_back().

[zturner]

Yea he's right, I was just having a brain fail when I wrote that. I'm updating the code to correctly handle collisions. I don't think we need to do anything special for S_CONSTANT though, because the DenseSet<> is just holding hash values of generic CVSymbol records, which could be any kind of symbol, including S_CONSTANT. With a record-kind-agnostic hash set and the ability to handle collisions, we just need to change the if statement to a switch statement and we can handle all the types we want.

[zturner]

Changed the test to an llvm assembly test, and properly handle collisions. I actually added some instrumentation to detect if any collisions were actually occurring, and I did not find any with a PDB containing 450,000 S_UDT records. On the other hand, I did not measure a performance impact from adding this, so I'm adding it anyway. We can revisit later if it shows up on a profile.

Note that the test changed a little bit. For some reason, when I use an IR test and llc it generates different assembly than if I use an assembly test with llvm-mc. I don't know if this is normal, but throwing it out there just in case.

[aganea]

lld/test/COFF/s_udt.s

20 ↗

(On Diff #176680)

Just to be sure, 0x1003 is here because of the yet unlanded D55236? It should read 0x1006 once it lands? You would need to re-generate this test at that point?

llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp

46

Since you removed GSIStreamBuilder::addGlobalSymbol below, do we still need this function?

[zturner]

lld/test/COFF/s_udt.s

20 ↗

(On Diff #176680)

Yes, whoever lands second would need to update their patch.

llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp

46

I only removed the overload that takes a UDTSym (it was never called), but there are still other overloads. Once we extend the hash lookup to include types other than S_UDT, we can evaluate the other methods. I could also probably just change the push_back to an addSymbol since there's no reason not to. I'll do that offline before I submit.

[aganea]

Thank you!

lld/COFF/PDB.cpp

static void scopeStackClose(SmallVectorImpl<SymbolScope> &Stack,
   if (Stack.empty()) {
     warn("symbol scopes are not balanced in " + File->getName());
     return;
   }
   SymbolScope S = Stack.pop_back_val();
   S.OpeningRecord->PtrEnd = CurOffset;
 }
 
-static bool symbolGoesInModuleStream(const CVSymbol &Sym) {
+static bool symbolGoesInModuleStream(const CVSymbol &Sym, bool IsGlobalScope) {
   switch (Sym.kind()) {
   case SymbolKind::S_GDATA32:
   case SymbolKind::S_CONSTANT:
-  case SymbolKind::S_UDT:
   // We really should not be seeing S_PROCREF and S_LPROCREF in the first place
   // since they are synthesized by the linker in response to S_GPROC32 and
   // S_LPROC32, but if we do see them, don't put them in the module stream I
   // guess.
   case SymbolKind::S_PROCREF:
   case SymbolKind::S_LPROCREF:
     return false;
+  // S_UDT records go in the module stream if it is not a global S_UDT.
+  case SymbolKind::S_UDT:
+    return !IsGlobalScope;
   // S_GDATA32 does not go in the module stream, but S_LDATA32 does.
   case SymbolKind::S_LDATA32:
   default:
     return true;
   }
 }
 
-static bool symbolGoesInGlobalsStream(const CVSymbol &Sym) {
+static bool symbolGoesInGlobalsStream(const CVSymbol &Sym, bool IsGlobalScope) {
   switch (Sym.kind()) {
   case SymbolKind::S_CONSTANT:
   case SymbolKind::S_GDATA32:
   // S_LDATA32 goes in both the module stream and the globals stream.
   case SymbolKind::S_LDATA32:
   case SymbolKind::S_GPROC32:
   case SymbolKind::S_LPROC32:
   // We really should not be seeing S_PROCREF and S_LPROCREF in the first place
   // since they are synthesized by the linker in response to S_GPROC32 and
   // S_LPROC32, but if we do see them, copy them straight through.
   case SymbolKind::S_PROCREF:
   case SymbolKind::S_LPROCREF:
     return true;
-  // FIXME: For now, we drop all S_UDT symbols (i.e. they don't go in the
-  // globals stream or the modules stream).  These have special handling which
-  // needs more investigation before we can get right, but by putting them all
-  // into the globals stream WinDbg fails to display local variables of class
-  // types saying that it cannot find the type Foo *.  So as a stopgap just to
-  // keep things working, we drop them.
+  // S_UDT records go in the globals stream if it is a global S_UDT.
   case SymbolKind::S_UDT:
+    return IsGlobalScope;
   default:
     return false;
   }
 }
 
 static void addGlobalSymbol(pdb::GSIStreamBuilder &Builder, uint16_t ModIndex,
                             unsigned SymOffset, const CVSymbol &Sym) {
   switch (Sym.kind()) {
cantFail(forEachCodeViewRecord<CVSymbol>(
           scopeStackOpen(Scopes, CurSymOffset, Sym);
         else if (symbolEndsScope(Sym.kind()))
           scopeStackClose(Scopes, CurSymOffset, File);
 
         // Add the symbol to the globals stream if necessary.  Do this before
         // adding the symbol to the module since we may need to get the next
         // symbol offset, and writing to the module's symbol stream will update
         // that offset.
-        if (symbolGoesInGlobalsStream(Sym))
+        if (symbolGoesInGlobalsStream(Sym, Scopes.empty()))
           addGlobalSymbol(Builder.getGsiBuilder(),
                           File->ModuleDBI->getModuleIndex(), CurSymOffset, Sym);
 
-        if (symbolGoesInModuleStream(Sym)) {
+        if (symbolGoesInModuleStream(Sym, Scopes.empty())) {
           // Add symbols to the module in bulk. If this symbol is contiguous
           // with the previous run of symbols to add, combine the ranges. If
           // not, close the previous range of symbols and start a new one.
           if (Sym.data().data() == BulkSymbols.end()) {
             BulkSymbols = makeArrayRef(BulkSymbols.data(),
                                        BulkSymbols.size() + Sym.length());
           } else {
             File->ModuleDBI->addSymbolsInBulk(BulkSymbols);

lld/test/COFF/s_udt.test

+; RUN: llc -filetype=obj < %s > %t.obj
+; RUN: lld-link /DEBUG:FULL /nodefaultlib /entry:main %t.obj /PDB:%t.pdb /OUT:%t.exe
+; RUN: llvm-pdbutil dump -types -globals -symbols -modi=0 %t.pdb | FileCheck %s
+
+; CHECK:                               Types (TPI Stream)
+; CHECK-NEXT: ============================================================
+; CHECK:      0x1003 | LF_STRUCTURE [size = 44] `Struct`
+; CHECK-NEXT:          unique name: `.?AUStruct@@`
+; CHECK-NEXT:          vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK-NEXT:          options: forward ref (-> 0x1006) | has unique name, sizeof 0
+; CHECK-NEXT: 0x1004 | LF_POINTER [size = 12]
+; CHECK-NEXT:          referent = 0x1003, mode = pointer, opts = None, kind = ptr64
+; CHECK:      0x1006 | LF_STRUCTURE [size = 44] `Struct`
+; CHECK-NEXT:          unique name: `.?AUStruct@@`
+; CHECK-NEXT:          vtable: <no type>, base list: <no type>, field list: 0x1005
+; CHECK-NEXT:          options: has unique name, sizeof 4
+; CHECK:                               Global Symbols
+; CHECK-NEXT: ============================================================
+; CHECK:      {{.*}} | S_UDT [size = 24] `StructTypedef`
+; CHECK:               original type = 0x1003
+; CHECK:      {{.*}} | S_UDT [size = 16] `Struct`
+; CHECK:               original type = 0x1006
+; CHECK:      {{.*}} | S_UDT [size = 20] `IntTypedef`
+; CHECK:               original type = 0x0074 (int)
+; CHECK:                               Symbols
+; CHECK-NEXT: ============================================================
+; CHECK:      {{.*}} | S_GPROC32 [size = 44] `main`
+; CHECK-NEXT:          parent = 0, end = 252, addr = 0001:0000, code size = 50
+; CHECK-NEXT:          type = `0x1002 (int (int, char**))`, debug start = 0, debug end = 0, flags = none
+; CHECK-NOT:  {{.*}} | S_END
+; CHECK:      {{.*}} | S_UDT [size = 28] `main::LocalTypedef`
+; CHECK-NEXT:          original type = 0x1004
+; CHECK:      {{.*}} | S_END [size = 4]
+
+; ModuleID = 'foo.cpp'
+source_filename = "foo.cpp"
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc19.16.27024"
+
+%struct.Struct = type { i32 }
+
+@"?S@@3UStruct@@A" = dso_local global %struct.Struct zeroinitializer, align 4, !dbg !0
+@"?SS@@3UStruct@@A" = dso_local global %struct.Struct zeroinitializer, align 4, !dbg !6
+@"?I@@3HA" = dso_local global i32 0, align 4, !dbg !13
+
+; Function Attrs: noinline norecurse nounwind optnone uwtable
+define dso_local i32 @main(i32 %argc, i8** %argv) #0 !dbg !23 {
+entry:
+  %retval = alloca i32, align 4
+  %argv.addr = alloca i8**, align 8
+  %argc.addr = alloca i32, align 4
+  %SPtr = alloca %struct.Struct*, align 8
+  store i32 0, i32* %retval, align 4
+  store i8** %argv, i8*** %argv.addr, align 8
+  call void @llvm.dbg.declare(metadata i8*** %argv.addr, metadata !29, metadata !DIExpression()), !dbg !30
+  store i32 %argc, i32* %argc.addr, align 4
+  call void @llvm.dbg.declare(metadata i32* %argc.addr, metadata !31, metadata !DIExpression()), !dbg !30
+  call void @llvm.dbg.declare(metadata %struct.Struct** %SPtr, metadata !32, metadata !DIExpression()), !dbg !35
+  %0 = load i32, i32* @"?I@@3HA", align 4, !dbg !36
+  %1 = load i32, i32* getelementptr inbounds (%struct.Struct, %struct.Struct* @"?S@@3UStruct@@A", i32 0, i32 0), align 4, !dbg !36
+  %add = add nsw i32 %0, %1, !dbg !36
+  %2 = load i32, i32* getelementptr inbounds (%struct.Struct, %struct.Struct* @"?SS@@3UStruct@@A", i32 0, i32 0), align 4, !dbg !36
+  %add1 = add nsw i32 %add, %2, !dbg !36
+  %3 = load %struct.Struct*, %struct.Struct** %SPtr, align 8, !dbg !36
+  %x = getelementptr inbounds %struct.Struct, %struct.Struct* %3, i32 0, i32 0, !dbg !36
+  %4 = load i32, i32* %x, align 4, !dbg !36
+  %add2 = add nsw i32 %add1, %4, !dbg !36
+  ret i32 %add2, !dbg !36
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+attributes #0 = { noinline norecurse nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!2}
+!llvm.linker.options = !{!16, !17}
+!llvm.module.flags = !{!18, !19, !20, !21}
+!llvm.ident = !{!22}
+
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "S", linkageName: "?S@@3UStruct@@A", scope: !2, file: !3, line: 8, type: !9, isLocal: false, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !3, producer: "clang version 8.0.0 ", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5, nameTableKind: None)
+!3 = !DIFile(filename: "foo.cpp", directory: "D:\5C\5Csrc\5C\5Cllvmbuild\5C\5Ccl\5C\5CDebug\5C\5Cx64", checksumkind: CSK_MD5, checksum: "2b62298ee3eef94e1d81fdfe18bd46a6")
+!4 = !{}
+!5 = !{!0, !6, !13}
+!6 = !DIGlobalVariableExpression(var: !7, expr: !DIExpression())
+!7 = distinct !DIGlobalVariable(name: "SS", linkageName: "?SS@@3UStruct@@A", scope: !2, file: !3, line: 9, type: !8, isLocal: false, isDefinition: true)
+!8 = !DIDerivedType(tag: DW_TAG_typedef, name: "StructTypedef", file: !3, line: 7, baseType: !9)
+!9 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "Struct", file: !3, line: 1, size: 32, flags: DIFlagTypePassByValue | DIFlagTrivial, elements: !10, identifier: ".?AUStruct@@")
+!10 = !{!11}
+!11 = !DIDerivedType(tag: DW_TAG_member, name: "x", scope: !9, file: !3, line: 2, baseType: !12, size: 32)
+!12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!13 = !DIGlobalVariableExpression(var: !14, expr: !DIExpression())
+!14 = distinct !DIGlobalVariable(name: "I", linkageName: "?I@@3HA", scope: !2, file: !3, line: 10, type: !15, isLocal: false, isDefinition: true)
+!15 = !DIDerivedType(tag: DW_TAG_typedef, name: "IntTypedef", file: !3, line: 6, baseType: !12)
+!16 = !{!"/DEFAULTLIB:libcmt.lib"}
+!17 = !{!"/DEFAULTLIB:oldnames.lib"}
+!18 = !{i32 2, !"CodeView", i32 1}
+!19 = !{i32 2, !"Debug Info Version", i32 3}
+!20 = !{i32 1, !"wchar_size", i32 2}
+!21 = !{i32 7, !"PIC Level", i32 2}
+!22 = !{!"clang version 8.0.0 "}
+!23 = distinct !DISubprogram(name: "main", scope: !3, file: !3, line: 12, type: !24, scopeLine: 12, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !2, retainedNodes: !4)
+!24 = !DISubroutineType(types: !25)
+!25 = !{!12, !12, !26}
+!26 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !27, size: 64)
+!27 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !28, size: 64)
+!28 = !DIBasicType(name: "char", size: 8, encoding: DW_ATE_signed_char)
+!29 = !DILocalVariable(name: "argv", arg: 2, scope: !23, file: !3, line: 12, type: !26)
+!30 = !DILocation(line: 12, scope: !23)
+!31 = !DILocalVariable(name: "argc", arg: 1, scope: !23, file: !3, line: 12, type: !12)
+!32 = !DILocalVariable(name: "SPtr", scope: !23, file: !3, line: 14, type: !33)
+!33 = !DIDerivedType(tag: DW_TAG_typedef, name: "LocalTypedef", scope: !23, file: !3, line: 13, baseType: !34)
+!34 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !9, size: 64)
+!35 = !DILocation(line: 14, scope: !23)
+!36 = !DILocation(line: 15, scope: !23)

llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp

 //===- DbiStreamBuilder.cpp - PDB Dbi Stream Creation -----------*- 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/PDB/Native/GSIStreamBuilder.h"
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/DebugInfo/CodeView/RecordName.h"
 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"
 #include "llvm/DebugInfo/CodeView/SymbolRecord.h"
 #include "llvm/DebugInfo/CodeView/SymbolSerializer.h"
 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFCommon.h"
 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
 #include "llvm/DebugInfo/PDB/Native/Hash.h"
 #include "llvm/Support/BinaryItemStream.h"
 #include "llvm/Support/BinaryStreamWriter.h"
+#include "llvm/Support/xxhash.h"
 #include <algorithm>
 #include <vector>
 
 using namespace llvm;
 using namespace llvm::msf;
 using namespace llvm::pdb;
 using namespace llvm::codeview;
 
 struct llvm::pdb::GSIHashStreamBuilder {
   std::vector<CVSymbol> Records;
   uint32_t StreamIndex;
+  llvm::DenseSet<uint64_t> UdtHashes;
   std::vector<PSHashRecord> HashRecords;
   std::array<support::ulittle32_t, (IPHR_HASH + 32) / 32> HashBitmap;
   std::vector<support::ulittle32_t> HashBuckets;
 
   uint32_t calculateSerializedLength() const;
   uint32_t calculateRecordByteSize() const;
   Error commit(BinaryStreamWriter &Writer);
   void finalizeBuckets(uint32_t RecordZeroOffset);
 
   template <typename T> void addSymbol(const T &Symbol, MSFBuilder &Msf) {
     T Copy(Symbol);
     Records.push_back(SymbolSerializer::writeOneSymbol(Copy, Msf.getAllocator(),
                                                        CodeViewContainer::Pdb));
   }
-  void addSymbol(const CVSymbol &Symbol) { Records.push_back(Symbol); }
+  void addSymbol(const CVSymbol &Symbol) {
+    if (Symbol.kind() == S_UDT) {
+      uint64_t Hash = xxHash64(Symbol.RecordData);
+      auto Iter = UdtHashes.insert(Hash);
+      if (!Iter.second)
+        return;
+    }
+
+    Records.push_back(Symbol);
+  }
 };
 
 uint32_t GSIHashStreamBuilder::calculateSerializedLength() const {
   uint32_t Size = sizeof(GSIHashHeader);
   Size += HashRecords.size() * sizeof(PSHashRecord);
   Size += HashBitmap.size() * sizeof(uint32_t);
   Size += HashBuckets.size() * sizeof(uint32_t);
   return Size;