[ThinLTO] Only emit referenced type id records in index files

[tejohnson]

Summary

Currently all type ids are emitted into the index file when it is
written. For distributed ThinLTO, that meant that all type ids were
being duplicated into every single distributed index file, regardless of
whether they were referenced, leading to huge amounts of unnecessary
duplication and size bloat.

Keep track of the type id GUIDs actually referenced by the GV summary
records being emitted, and only emit those type IDs.

Add a new test, and fix test/Assembler/thinlto-summary.ll so that all
type ids are referenced to prevent deletion in that test.

[pcc]

LGTM

test/ThinLTO/X86/cfi-distributed.ll

19

You mean @test2?

25

Ditto

[tejohnson]

test/ThinLTO/X86/cfi-distributed.ll

19

Yep, fixed here and below.

[tejohnson]

Fix test comments

lib/Bitcode/Writer/BitcodeWriter.cpp

forEachModule(
 
         Vals.clear();
       });
   Stream.ExitBlock();
 }
 
 /// Write the function type metadata related records that need to appear before
 /// a function summary entry (whether per-module or combined).
-static void writeFunctionTypeMetadataRecords(BitstreamWriter &Stream,
-                                             FunctionSummary *FS) {
-  if (!FS->type_tests().empty())
+static void writeFunctionTypeMetadataRecords(
+    BitstreamWriter &Stream, FunctionSummary *FS,
+    std::set<GlobalValue::GUID> &ReferencedTypeIds) {
+  if (!FS->type_tests().empty()) {
     Stream.EmitRecord(bitc::FS_TYPE_TESTS, FS->type_tests());
+    for (auto &TT : FS->type_tests())
+      ReferencedTypeIds.insert(TT);
+  }
 
   SmallVector<uint64_t, 64> Record;
 
   auto WriteVFuncIdVec = [&](uint64_t Ty,
                              ArrayRef<FunctionSummary::VFuncId> VFs) {
     if (VFs.empty())
       return;
     Record.clear();
     for (auto &VF : VFs) {
       Record.push_back(VF.GUID);
       Record.push_back(VF.Offset);
+      ReferencedTypeIds.insert(VF.GUID);
     }
     Stream.EmitRecord(Ty, Record);
   };
 
   WriteVFuncIdVec(bitc::FS_TYPE_TEST_ASSUME_VCALLS,
                   FS->type_test_assume_vcalls());
   WriteVFuncIdVec(bitc::FS_TYPE_CHECKED_LOAD_VCALLS,
                   FS->type_checked_load_vcalls());
 
   auto WriteConstVCallVec = [&](uint64_t Ty,
                                 ArrayRef<FunctionSummary::ConstVCall> VCs) {
     for (auto &VC : VCs) {
       Record.clear();
       Record.push_back(VC.VFunc.GUID);
+      ReferencedTypeIds.insert(VC.VFunc.GUID);
       Record.push_back(VC.VFunc.Offset);
       Record.insert(Record.end(), VC.Args.begin(), VC.Args.end());
       Stream.EmitRecord(Ty, Record);
     }
   };
 
   WriteConstVCallVec(bitc::FS_TYPE_TEST_ASSUME_CONST_VCALL,
                      FS->type_test_assume_const_vcalls());

 // Helper to emit a single function summary record.
 void ModuleBitcodeWriterBase::writePerModuleFunctionSummaryRecord(
     SmallVector<uint64_t, 64> &NameVals, GlobalValueSummary *Summary,
     unsigned ValueID, unsigned FSCallsAbbrev, unsigned FSCallsProfileAbbrev,
     const Function &F) {
   NameVals.push_back(ValueID);
 
   FunctionSummary *FS = cast<FunctionSummary>(Summary);
-  writeFunctionTypeMetadataRecords(Stream, FS);
+  std::set<GlobalValue::GUID> ReferencedTypeIds;
+  writeFunctionTypeMetadataRecords(Stream, FS, ReferencedTypeIds);
 
   NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
   NameVals.push_back(FS->instCount());
   NameVals.push_back(getEncodedFFlags(FS->fflags()));
   NameVals.push_back(FS->refs().size());
 
   for (auto &RI : FS->refs())
     NameVals.push_back(VE.getValueID(RI.getValue()));
void IndexBitcodeWriter::writeCombinedGlobalValueSummary() {
   // id of the aliasee. Save them in a vector for post-processing.
   SmallVector<AliasSummary *, 64> Aliases;
 
   // Save the value id for each summary for alias emission.
   DenseMap<const GlobalValueSummary *, unsigned> SummaryToValueIdMap;
 
   SmallVector<uint64_t, 64> NameVals;
 
+  // Set that will be populated during call to writeFunctionTypeMetadataRecords
+  // with the type ids referenced by this index file.
+  std::set<GlobalValue::GUID> ReferencedTypeIds;
+
   // For local linkage, we also emit the original name separately
   // immediately after the record.
   auto MaybeEmitOriginalName = [&](GlobalValueSummary &S) {
     if (!GlobalValue::isLocalLinkage(S.linkage()))
       return;
     NameVals.push_back(S.getOriginalName());
     Stream.EmitRecord(bitc::FS_COMBINED_ORIGINAL_NAME, NameVals);
     NameVals.clear();
if (auto *VS = dyn_cast<GlobalVarSummary>(S)) {
       Stream.EmitRecord(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS, NameVals,
                         FSModRefsAbbrev);
       NameVals.clear();
       MaybeEmitOriginalName(*S);
       return;
     }
 
     auto *FS = cast<FunctionSummary>(S);
-    writeFunctionTypeMetadataRecords(Stream, FS);
+    writeFunctionTypeMetadataRecords(Stream, FS, ReferencedTypeIds);
 
     NameVals.push_back(*ValueId);
     NameVals.push_back(Index.getModuleId(FS->modulePath()));
     NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
     NameVals.push_back(FS->instCount());
     NameVals.push_back(getEncodedFFlags(FS->fflags()));
     // Fill in below
     NameVals.push_back(0);
for (auto &S : Index.cfiFunctionDecls()) {
       NameVals.push_back(S.size());
     }
     Stream.EmitRecord(bitc::FS_CFI_FUNCTION_DECLS, NameVals);
     NameVals.clear();
   }
 
   if (!Index.typeIds().empty()) {
     for (auto &S : Index.typeIds()) {
+      // Skip if not referenced in any GV summary within this index file.
+      if (!ReferencedTypeIds.count(GlobalValue::getGUID(S.first)))
+        continue;
       writeTypeIdSummaryRecord(NameVals, StrtabBuilder, S.first, S.second);
       Stream.EmitRecord(bitc::FS_TYPE_ID, NameVals);
       NameVals.clear();
     }
   }
 
   Stream.ExitBlock();
 }

test/Assembler/thinlto-summary.ll

 ; Alias summary with backwards reference to aliasee.
 ^18 = gv: (guid: 17, summaries: (alias: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 1), aliasee: ^14)))
 
 ; Test all types of TypeIdInfo on function summaries.
 ^19 = gv: (guid: 18, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 4, typeIdInfo: (typeTests: (^24, ^26)))))
 ^20 = gv: (guid: 19, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 8, typeIdInfo: (typeTestAssumeVCalls: (vFuncId: (^27, offset: 16))))))
 ^21 = gv: (guid: 20, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadVCalls: (vFuncId: (^25, offset: 16))))))
 ^22 = gv: (guid: 21, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 15, typeIdInfo: (typeTestAssumeConstVCalls: (vFuncId: (^27, offset: 16), args: (42), vFuncId: (^27, offset: 24), args: (43))))))
-^23 = gv: (guid: 22, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadConstVCalls: (vFuncId: (^27, offset: 16), args: (42))))))
+^23 = gv: (guid: 22, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadConstVCalls: (vFuncId: (^28, offset: 16), args: (42))))))
 
 ; Test TypeId summaries:
 
 ; Test the AllOnes resolution, and all kinds of WholeProgramDevirtResolution
 ; types, including all optional resolution by argument kinds.
 ^24 = typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: allOnes, sizeM1BitWidth: 7), wpdResolutions: ((offset: 0, wpdRes: (kind: branchFunnel)), (offset: 8, wpdRes: (kind: singleImpl, singleImplName: "_ZN1A1nEi")), (offset: 16, wpdRes: (kind: indir, resByArg: (args: (1, 2), byArg: (kind: indir, byte: 2, bit: 3), args: (3), byArg: (kind: uniformRetVal, info: 1), args: (4), byArg: (kind: uniqueRetVal, info: 1), args: (5), byArg: (kind: virtualConstProp)))))))
 ; Test TypeId with other optional fields (alignLog2/sizeM1/bitMask/inlineBits)
 ^25 = typeid: (name: "_ZTS1B", summary: (typeTestRes: (kind: inline, sizeM1BitWidth: 0, alignLog2: 1, sizeM1: 2, bitMask: 3, inlineBits: 4)))

 ; CHECK: ^15 = gv: (guid: 14, summaries: (function: (module: ^1, flags: (linkage: external, notEligibleToImport: 1, live: 1, dsoLocal: 0), insts: 1)))
 ; CHECK: ^16 = gv: (guid: 15, summaries: (function: (module: ^1, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 1, funcFlags: (readNone: 1, readOnly: 0, noRecurse: 1, returnDoesNotAlias: 0))))
 ; CHECK: ^17 = gv: (guid: 16, summaries: (function: (module: ^1, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 1, funcFlags: (readNone: 0, readOnly: 1, noRecurse: 0, returnDoesNotAlias: 1), calls: ((callee: ^15)))))
 ; CHECK: ^18 = gv: (guid: 17, summaries: (alias: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 1), aliasee: ^14)))
 ; CHECK: ^19 = gv: (guid: 18, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 4, typeIdInfo: (typeTests: (^24, ^26)))))
 ; CHECK: ^20 = gv: (guid: 19, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 8, typeIdInfo: (typeTestAssumeVCalls: (vFuncId: (^27, offset: 16))))))
 ; CHECK: ^21 = gv: (guid: 20, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadVCalls: (vFuncId: (^25, offset: 16))))))
 ; CHECK: ^22 = gv: (guid: 21, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 15, typeIdInfo: (typeTestAssumeConstVCalls: (vFuncId: (^27, offset: 16), args: (42), vFuncId: (^27, offset: 24), args: (43))))))
-; CHECK: ^23 = gv: (guid: 22, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadConstVCalls: (vFuncId: (^27, offset: 16), args: (42))))))
+; CHECK: ^23 = gv: (guid: 22, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadConstVCalls: (vFuncId: (^28, offset: 16), args: (42))))))
 ; CHECK: ^24 = typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: allOnes, sizeM1BitWidth: 7), wpdResolutions: ((offset: 0, wpdRes: (kind: branchFunnel)), (offset: 8, wpdRes: (kind: singleImpl, singleImplName: "_ZN1A1nEi")), (offset: 16, wpdRes: (kind: indir, resByArg: (args: (1, 2), byArg: (kind: indir, byte: 2, bit: 3), args: (3), byArg: (kind: uniformRetVal, info: 1), args: (4), byArg: (kind: uniqueRetVal, info: 1), args: (5), byArg: (kind: virtualConstProp))))))) ; guid = 7004155349499253778
 ; CHECK: ^25 = typeid: (name: "_ZTS1B", summary: (typeTestRes: (kind: inline, sizeM1BitWidth: 0, alignLog2: 1, sizeM1: 2, bitMask: 3, inlineBits: 4))) ; guid = 6203814149063363976
 ; CHECK: ^26 = typeid: (name: "_ZTS1C", summary: (typeTestRes: (kind: single, sizeM1BitWidth: 0))) ; guid = 1884921850105019584
 ; CHECK: ^27 = typeid: (name: "_ZTS1D", summary: (typeTestRes: (kind: byteArray, sizeM1BitWidth: 0))) ; guid = 9614786172484273522
 ; CHECK: ^28 = typeid: (name: "_ZTS1E", summary: (typeTestRes: (kind: unsat, sizeM1BitWidth: 0))) ; guid = 17437243864166745132

test/ThinLTO/X86/Inputs/cfi-distributed.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.B2 = type { %struct.A2 }
+%struct.A2 = type { i32 (...)** }
+
+@_ZTV1B2 = constant { [3 x i8*] } { [3 x i8*] [i8* undef, i8* undef, i8* undef] }, !type !0
+
+define void @test2(i8* %b) {
+entry:
+  %0 = bitcast i8* %b to i8**
+  %vtable2 = load i8*, i8** %0
+  %1 = tail call i1 @llvm.type.test(i8* %vtable2, metadata !"_ZTS1A2")
+  br i1 %1, label %cont, label %trap
+
+trap:
+  tail call void @llvm.trap()
+  unreachable
+
+cont:
+  ret void
+}
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.trap()
+
+!0 = !{i64 16, !"_ZTS1A2"}
+!1 = !{i64 16, !"_ZTS1B2"}

test/ThinLTO/X86/cfi-distributed.ll

+; REQUIRES: x86-registered-target
+
+; Test to ensure that only referenced type ID records are emitted into
+; each distributed index file.
+
+; RUN: opt -thinlto-bc -o %t1.o %s
+; RUN: opt -thinlto-bc -o %t2.o %p/Inputs/cfi-distributed.ll
+
+; RUN: llvm-lto2 run -thinlto-distributed-indexes %t1.o %t2.o \
+; RUN:   -o %t3 \
+; RUN:   -r=%t1.o,test,px \
+; RUN:   -r=%t1.o,_ZTV1B, \
+; RUN:   -r=%t1.o,_ZTV1B,px \
+; RUN:   -r=%t1.o,test2, \
+; RUN:   -r=%t2.o,test2,px \
+; RUN:   -r=%t2.o,_ZTV1B2, \
+; RUN:   -r=%t2.o,_ZTV1B2,px
+
+; Since @test calls @test1, the latter should be imported here and the
+; first index file should reference both type ids.
+; RUN: llvm-dis %t1.o.thinlto.bc -o - | FileCheck %s --check-prefix=INDEX1
+; INDEX1: typeid: (name: "_ZTS1A"
+; INDEX1: typeid: (name: "_ZTS1A2"
+
+; The second index file, corresponding to @test1, should only contain the
+; typeid for _ZTS1A.
+; RUN: llvm-dis %t2.o.thinlto.bc -o - | FileCheck %s --check-prefix=INDEX2
+; INDEX2-NOT: typeid: (name: "_ZTS1A"
+; INDEX2: typeid: (name: "_ZTS1A2"
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.B = type { %struct.A }
+%struct.A = type { i32 (...)** }
+
+@_ZTV1B = constant { [3 x i8*] } { [3 x i8*] [i8* undef, i8* undef, i8* undef] }, !type !0
+
+define void @test(i8* %b) {
+entry:
+  tail call void @test2(i8* %b)
+  %0 = bitcast i8* %b to i8**
+  %vtable2 = load i8*, i8** %0
+  %1 = tail call i1 @llvm.type.test(i8* %vtable2, metadata !"_ZTS1A")
+  br i1 %1, label %cont, label %trap
+
+trap:
+  tail call void @llvm.trap()
+  unreachable
+
+cont:
+  ret void
+}
+
+declare void @test2(i8*)
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.trap()
+
+!0 = !{i64 16, !"_ZTS1A"}
+!1 = !{i64 16, !"_ZTS1B"}