[ELF] Handle bitcode comdat groups separately to deduplicate thinlto comdat sections

[christylee]

Summary

This change allows lld to deduplicate bitcode file comdat groups, which will allow it to deduplicate .debug_types sections in thinlto.

For more context, see https://reviews.llvm.org/D62884

[dblaikie]

(I'm probably not the right person to do detailed/semantic review of this, but here's some basic things I spotted)

lld/ELF/InputFiles.cpp

609–617

typo? ("proceed" was intended to be "processed", perhaps?)

1568–1571

Unrelated change in this patch - probably best to remove it or commit it separately?

[christylee]

Fixed typo and removed unrelated change.

[sbc100]

Would you mind making the equivalent changes to lld/wasm?

And a test?

lld/ELF/InputFiles.cpp

393

Perhaps this would better be names something like isLTOOutput? Otherwise it sounds like it might a bitcode object which is a different class here.

[christylee]

This comment was removed by christylee.

[christylee]

@sbc100 What would be a good way to go about writing a test for this? The reason why I noticed this bug was because .debug_types are not deduplicated in thinlto, but writing a lld test case using debug metadata seems clunky.

I've also tried something like this but it doesn't repro:

; REQUIRES: x86
; RUN: llvm-as %s -o %t.o
; RUN: llc %t.o -o %t2.o -filetype=obj
; RUN: ld.lld %t.o %t2.o %t.o %t2.o -o %t3.o --shared
; RUN: llvm-readobj --symbols %t3.o | FileCheck %s

; CHECK:      Name: foo
; CHECK-NEXT: Value:
; CHECK-NEXT: Size: 1
; CHECK-NEXT: Binding: Global
; CHECK-NEXT: Type: Function
; CHECK-NEXT: Other: 0
; CHECK-NEXT: Section: .text

target triple = "x86_64-unknown-linux-gnu"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"

$foo = comdat any
define void @foo() comdat {
  ret void
}

[sbc100]

In D80765#2063931, @christylee wrote:

@sbc100 What would be a good way to go about writing a test for this? The reason why I noticed this bug was because .debug_types are not deduplicated in thinlto, but writing a lld test case using debug metadata seems clunky.

I've also tried something like this but it doesn't repro:

; REQUIRES: x86
; RUN: llvm-as %s -o %t.o
; RUN: llc %t.o -o %t2.o -filetype=obj
; RUN: ld.lld %t.o %t2.o %t.o %t2.o -o %t3.o --shared
; RUN: llvm-readobj --symbols %t3.o | FileCheck %s

; CHECK:      Name: foo
; CHECK-NEXT: Value:
; CHECK-NEXT: Size: 1
; CHECK-NEXT: Binding: Global
; CHECK-NEXT: Type: Function
; CHECK-NEXT: Other: 0
; CHECK-NEXT: Section: .text

target triple = "x86_64-unknown-linux-gnu"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"

$foo = comdat any
define void @foo() comdat {
  ret void
}

I'm sorry I've not looked into this in much detail but shouldn't this same bug reproduce with all comdats? Maybe there is something different about debug metatdata? BTW, the test above doesn't use lto or thinglto does it?

[christylee]

Addressed comments:

1). Changed isBitcodeFile to isLTOOutput.
2). Added test. Before this patch, lld does not deduplicate comdat sections generated by the backend. .debug_types is an example.

Change for COFF to follow.

[christylee]

Changed variable name bitcodeComdatGroup to ltoOutputComdatGroup for consistency.

[christylee]

Fixed a comment.

[christylee]

We don't need to make the same change to COFF. COFF does not ignore comdats, it attempts to add a comdat symbol as long as the symbol is external. It also tracks whether a symbol is from a regular object file or bitcode file so it won't have duplicates.

[grimar]

lld/ELF/SymbolTable.h

66

Double space before "Define".

67

fromt -> from

68

Could you expand the comment to mention why it is important to distinct them?

[christylee]

Fixed comment.

[grimar]

The LLD change looks fine to me. But I am not well familiar with LTO stuff and hence do not feel myself is a right person to approve it.

[christylee]

@grimar Do you know who might be a good reviewer?

[MaskRay]

In D80765#2090905, @christylee wrote:

@grimar Do you know who might be a good reviewer?

@tejohnson is a good one.

I'll also get to this patch soon. I tried an earlier version of this patch and noticed issues testing internally. I'll retest since the patch has changed a lot.

[tejohnson]

In D80765#2090939, @MaskRay wrote:

In D80765#2090905, @christylee wrote:

@grimar Do you know who might be a good reviewer?

@tejohnson is a good one.

Since this is very specific to lld, and not in the LLVM LTO handling, I'm not sure I'm the best person to review. I looked at the change but don't have enough understanding of how lld is otherwise handling comdat groups to do a really informed review.

I'll also get to this patch soon. I tried an earlier version of this patch and noticed issues testing internally. I'll retest since the patch has changed a lot.

Sounds good.

lld/test/ELF/lto/debug-types-deduplication.ll

4

IMO it is better to test ThinLTO by using "opt -module-summary" to create the bitcode object, and not have the serialized summary. It makes it clearer that it is a ThinLTO test.

[MaskRay]

Apologies for my slowness getting to this patch.

symtab->ltoOutputComdatGroups does work:

% readelf -g a3.o.lto.o a3.o1.lto.o 

File: a3.o.lto.o

COMDAT group section [    4] `.group' [4068369915778327548] contains 2 sections:
   [Index]    Name
   [    5]   .debug_types
   [    6]   .rela.debug_types

File: a3.o1.lto.o

COMDAT group section [    4] `.group' [4068369915778327548] contains 2 sections:
   [Index]    Name
   [    5]   .debug_types
   [    6]   .rela.debug_types

The .debug_types from a3.o1.lto.o can be discarded by the new COMDAT logic. However, I am concerned that making it general as this patch does can miss some codegen bugs. See @pcc's argument in
in https://reviews.llvm.org/D56015#1339411 . Since .debug_types (notably, a non-SHF_ALLOC section) is the only COMDAT rule this patch will discard, how about special casing .debug_types (i.e. if isLTOOutput && the group is related to .debug_types)?

[MaskRay]

lld/test/ELF/lto/debug-types-deduplication.ll

37

Can you drop some unneeded metadata nodes here?

[hoyFB]

In D80765#2099946, @MaskRay wrote:

Apologies for my slowness getting to this patch.

symtab->ltoOutputComdatGroups does work:

% readelf -g a3.o.lto.o a3.o1.lto.o 

File: a3.o.lto.o

COMDAT group section [    4] `.group' [4068369915778327548] contains 2 sections:
   [Index]    Name
   [    5]   .debug_types
   [    6]   .rela.debug_types

File: a3.o1.lto.o

COMDAT group section [    4] `.group' [4068369915778327548] contains 2 sections:
   [Index]    Name
   [    5]   .debug_types
   [    6]   .rela.debug_types

The .debug_types from a3.o1.lto.o can be discarded by the new COMDAT logic. However, I am concerned that making it general as this patch does can miss some codegen bugs. See @pcc's argument in
in https://reviews.llvm.org/D56015#1339411 . Since .debug_types (notably, a non-SHF_ALLOC section) is the only COMDAT rule this patch will discard, how about special casing .debug_types (i.e. if isLTOOutput && the group is related to .debug_types)?

Thanks for taking time reviewing this change. It is an interesting argument whether LTO should introduce new COMDAT symbols. Do we have a conclusion on this? So far the .debug_types are the only COMDAT we've seen introduced by LTO, but in theory any LTO-exclusive pass may introduce a new COMDAT symbol and it's up to the pass how to set the symbol's linkage type.

[christylee]

lld/ELF/InputFiles.cpp

611

@MaskRay

Since .debug_types (notably, a non-SHF_ALLOC section) is the only COMDAT rule this patch will discard, how about special casing .debug_types (i.e. if isLTOOutput && the group is related to .debug_types)?

At the time we run this check, not all InputSections have been initialized, so a the group might be related to an uninitialized section. Since it might be uninitialized, what's the best way to check if that section is non-SHF_ALLOC?

[MaskRay]

lld/ELF/InputFiles.cpp

611

This is difficult. An alternative is to use ltoOutputComdatGroups but assert that no collision happens

if (isLTOOutput) {
  CachedHashStringRef ref(signature);
  isNew = symtab->ltoOutputComdatGroups.try_emplace(ref, this).second);
  if (symtab->comdatGroups.coumt(ref))
    errorOrWarn(toString(this) + ": LTO output should not emit a section group whose signature collides with a non-LTO group signature");
}

[christylee]

lld/ELF/InputFiles.cpp

611

When we link something with thinlto, we first process the comdat groups when they are in bitcode form. We add that to symtab->comdatGroups since we want symtab->comdatGroups to contain all possible comdatGroups. After compiling the bitcode to object files, we process comdat groups again. At this point, if they are lto output, then we need to check whether we've seen it from other lto outputs. In other words, if something is in symtab->ltoOutputComdatGroups, then it must also be in symtab->comdatGroups, but we need the two distinct maps to ensure there are no duplicate symbols.

[christylee]

lld/ELF/InputFiles.cpp

611

@MaskRay , can we ship this as is?

lld/test/ELF/lto/debug-types-deduplication.ll

37

I've tried dropping the metadata but this is as small as I can get it.

[christylee]

In case we are concerned about correctness, we've been using this patch internally for a couple of months with no problems.

[MaskRay]

@MaskRay , can we ship this as is?

This still looks like a workaround done at an inappropriate layer to me. The .debug_types code generator should probably know that some .debug_types sections should not be emitted.
BTW, do you have statistics about the effectiveness for this change?

[christylee]

BTW, do you have statistics about the effectiveness for this change?

@MaskRay , one of our thinlto binaries went from a 6.9 GiB .debug_types section to 420 MiB, while another went from 7.8 GiB to 370 MiB.

[dblaikie]

Yeah - one alternative here would be for ThinLTO To "home" debug type information, the same way I believe it "homes" inline functions. (original/incoming IR to the thinlink may have multiple definitions of inline functions - one in every module that has a call to the inline function - but something in the think link summary basically says "drop this definition" in all but one of those modules and in that one blessed module it says "always produce a weak definition of this function, even if you don't need it" - something like that should be done with type information, which would remove the redundancy in the object files)

In the case of a full executable link (with the homing above implemented), I'd then suggest not enabling type units, since they just add overhead and wouldn't reduce any duplication - in the case of a static library built with ThinLTO (if that's even a thing), then you'd still potentially want to use type units so they could be deduplicated against other libraries.

[hoyFB]

In D80765#2170820, @dblaikie wrote:

Yeah - one alternative here would be for ThinLTO To "home" debug type information, the same way I believe it "homes" inline functions. (original/incoming IR to the thinlink may have multiple definitions of inline functions - one in every module that has a call to the inline function - but something in the think link summary basically says "drop this definition" in all but one of those modules and in that one blessed module it says "always produce a weak definition of this function, even if you don't need it" - something like that should be done with type information, which would remove the redundancy in the object files)

In the case of a full executable link (with the homing above implemented), I'd then suggest not enabling type units, since they just add overhead and wouldn't reduce any duplication - in the case of a static library built with ThinLTO (if that's even a thing), then you'd still potentially want to use type units so they could be deduplicated against other libraries.

Enabling compile-time type deduplication is indeed an ideal solution, as you pointed out finding a prevailing symbol definition and dropping others for duplicate functions from different modules. This would require quite some work in parsing type metadata on the IR and might slow down thinLink. Also this may not completely address deduplication of new data introduced during LTO postLink code generation time. The type unit level deduplication could be the last resort to handle the duplicates, like what is done in non-LTO build.

[dblaikie]

In D80765#2174141, @hoyFB wrote:

In D80765#2170820, @dblaikie wrote:

Yeah - one alternative here would be for ThinLTO To "home" debug type information, the same way I believe it "homes" inline functions. (original/incoming IR to the thinlink may have multiple definitions of inline functions - one in every module that has a call to the inline function - but something in the think link summary basically says "drop this definition" in all but one of those modules and in that one blessed module it says "always produce a weak definition of this function, even if you don't need it" - something like that should be done with type information, which would remove the redundancy in the object files)

In the case of a full executable link (with the homing above implemented), I'd then suggest not enabling type units, since they just add overhead and wouldn't reduce any duplication - in the case of a static library built with ThinLTO (if that's even a thing), then you'd still potentially want to use type units so they could be deduplicated against other libraries.

Enabling compile-time type deduplication is indeed an ideal solution, as you pointed out finding a prevailing symbol definition and dropping others for duplicate functions from different modules. This would require quite some work in parsing type metadata on the IR and might slow down thinLink.

Fair point - though presumably the first stage compile would do the metadata walk through the IR, provide a list of types in the thin summary file and the thin link would then communicate to the backend compiles specifying which types each backend compile should emit into its respective object file.

Also this may not completely address deduplication of new data introduced during LTO postLink code generation time. The type unit level deduplication could be the last resort to handle the duplicates, like what is done in non-LTO build.

Not sure I follow - what duplication would remain if the thin link homed type descriptions? When linking to non-LTO (normal machine code/object files) libraries? Yeah, fair point (tangential warning: LLVM's type unit hashes are non-DWARF-conforming and not compatible with GCC's type unit hashes... :/)

It /sounds/ like, maybe the original fix in D62884 maybe was going in the wrong direction, and instead ThinLTO should be removing the comdat group from "homed" inline functions? Then there wouldn't be a need for a special case in how comdats are handled.

[MaskRay]

In D80765#2174250, @dblaikie wrote:

In D80765#2174141, @hoyFB wrote:

In D80765#2170820, @dblaikie wrote:

Yeah - one alternative here would be for ThinLTO To "home" debug type information, the same way I believe it "homes" inline functions. (original/incoming IR to the thinlink may have multiple definitions of inline functions - one in every module that has a call to the inline function - but something in the think link summary basically says "drop this definition" in all but one of those modules and in that one blessed module it says "always produce a weak definition of this function, even if you don't need it" - something like that should be done with type information, which would remove the redundancy in the object files)

In the case of a full executable link (with the homing above implemented), I'd then suggest not enabling type units, since they just add overhead and wouldn't reduce any duplication - in the case of a static library built with ThinLTO (if that's even a thing), then you'd still potentially want to use type units so they could be deduplicated against other libraries.

Enabling compile-time type deduplication is indeed an ideal solution, as you pointed out finding a prevailing symbol definition and dropping others for duplicate functions from different modules. This would require quite some work in parsing type metadata on the IR and might slow down thinLink.

Fair point - though presumably the first stage compile would do the metadata walk through the IR, provide a list of types in the thin summary file and the thin link would then communicate to the backend compiles specifying which types each backend compile should emit into its respective object file.

Also this may not completely address deduplication of new data introduced during LTO postLink code generation time. The type unit level deduplication could be the last resort to handle the duplicates, like what is done in non-LTO build.

Not sure I follow - what duplication would remain if the thin link homed type descriptions? When linking to non-LTO (normal machine code/object files) libraries? Yeah, fair point (tangential warning: LLVM's type unit hashes are non-DWARF-conforming and not compatible with GCC's type unit hashes... :/)

It /sounds/ like, maybe the original fix in D62884 maybe was going in the wrong direction, and instead ThinLTO should be removing the comdat group from "homed" inline functions? Then there wouldn't be a need for a special case in how comdats are handled.

I am with @dblaikie here. A bit of archaeology finds that rG4de44b7ef87bcef83798eee69fdcbfab9866d52e was probably going in the wrong direction but it was indeed the simplest/least intrusive approach.
D62884 just made some refactorings. Just a thought: for ThinLTO backend, dropping comdat in processGlobalsForThinLTO may achieve some results. However, one issue is that on the MC layer the section group signature is part of ELFSectionKey.

.section foo,"aG",@progbits,aaa,comdat
.section foo,"aG",@progbits,bbb,comdat

are two sections. Dropping the comdat key will make them one combined section. Unique linkage may work around it but there may be a fair amount of complexity in TargetLoweringObjectFileImpl/MC.
I agree with pcc that LTO should not generate additional arbitrary comdat objects.

[dblaikie]

In D80765#2174269, @MaskRay wrote:

In D80765#2174250, @dblaikie wrote:

In D80765#2174141, @hoyFB wrote:

In D80765#2170820, @dblaikie wrote:

Yeah - one alternative here would be for ThinLTO To "home" debug type information, the same way I believe it "homes" inline functions. (original/incoming IR to the thinlink may have multiple definitions of inline functions - one in every module that has a call to the inline function - but something in the think link summary basically says "drop this definition" in all but one of those modules and in that one blessed module it says "always produce a weak definition of this function, even if you don't need it" - something like that should be done with type information, which would remove the redundancy in the object files)

In the case of a full executable link (with the homing above implemented), I'd then suggest not enabling type units, since they just add overhead and wouldn't reduce any duplication - in the case of a static library built with ThinLTO (if that's even a thing), then you'd still potentially want to use type units so they could be deduplicated against other libraries.

Enabling compile-time type deduplication is indeed an ideal solution, as you pointed out finding a prevailing symbol definition and dropping others for duplicate functions from different modules. This would require quite some work in parsing type metadata on the IR and might slow down thinLink.

Fair point - though presumably the first stage compile would do the metadata walk through the IR, provide a list of types in the thin summary file and the thin link would then communicate to the backend compiles specifying which types each backend compile should emit into its respective object file.

Also this may not completely address deduplication of new data introduced during LTO postLink code generation time. The type unit level deduplication could be the last resort to handle the duplicates, like what is done in non-LTO build.

Not sure I follow - what duplication would remain if the thin link homed type descriptions? When linking to non-LTO (normal machine code/object files) libraries? Yeah, fair point (tangential warning: LLVM's type unit hashes are non-DWARF-conforming and not compatible with GCC's type unit hashes... :/)

It /sounds/ like, maybe the original fix in D62884 maybe was going in the wrong direction, and instead ThinLTO should be removing the comdat group from "homed" inline functions? Then there wouldn't be a need for a special case in how comdats are handled.

I am with @dblaikie here. A bit of archaeology finds that rG4de44b7ef87bcef83798eee69fdcbfab9866d52e was probably going in the wrong direction but it was indeed the simplest/least intrusive approach.
D62884 just made some refactorings. Just a thought: for ThinLTO backend, dropping comdat in processGlobalsForThinLTO may achieve some results.

Yeah, maybe something near/similar to https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Utils/FunctionImportUtils.cpp#L275 - where the comdat is imported as available externally, and its comdat group is stripped. Theory is, maybe we should be stripping the comdat on the other side too.

Hmm, maybe not, though? What about non-whole-program-ThinLTO? There could be a comdat copy of this function in a static library that it should be deduplicated against?

I take it the underlying assumption lld is making is that a comdat group is only kept alive by references from within the object file that defines it? Is that formally specified/required? If not, then maybe we could/should remoev that assumption, so that ThinLTO can work naturally with non-(Thin)LTO archives and still do the suitable comdat deduplication or dropping?

However, one issue is that on the MC layer the section group signature is part of ELFSectionKey.

.section foo,"aG",@progbits,aaa,comdat
.section foo,"aG",@progbits,bbb,comdat

are two sections. Dropping the comdat key will make them one combined section.

Is that a problem? When linked they end up in the same section, right?

Unique linkage may work around it but there may be a fair amount of complexity in TargetLoweringObjectFileImpl/MC.
I agree with pcc that LTO should not generate additional arbitrary comdat objects.

What additional arbitrary comdat objects are being generated or proposed to be generated?

[hoyFB]

In D80765#2177014, @dblaikie wrote:

In D80765#2174269, @MaskRay wrote:

In D80765#2174250, @dblaikie wrote:

In D80765#2174141, @hoyFB wrote:

In D80765#2170820, @dblaikie wrote:

Yeah - one alternative here would be for ThinLTO To "home" debug type information, the same way I believe it "homes" inline functions. (original/incoming IR to the thinlink may have multiple definitions of inline functions - one in every module that has a call to the inline function - but something in the think link summary basically says "drop this definition" in all but one of those modules and in that one blessed module it says "always produce a weak definition of this function, even if you don't need it" - something like that should be done with type information, which would remove the redundancy in the object files)

In the case of a full executable link (with the homing above implemented), I'd then suggest not enabling type units, since they just add overhead and wouldn't reduce any duplication - in the case of a static library built with ThinLTO (if that's even a thing), then you'd still potentially want to use type units so they could be deduplicated against other libraries.

Enabling compile-time type deduplication is indeed an ideal solution, as you pointed out finding a prevailing symbol definition and dropping others for duplicate functions from different modules. This would require quite some work in parsing type metadata on the IR and might slow down thinLink.

Fair point - though presumably the first stage compile would do the metadata walk through the IR, provide a list of types in the thin summary file and the thin link would then communicate to the backend compiles specifying which types each backend compile should emit into its respective object file.

Also this may not completely address deduplication of new data introduced during LTO postLink code generation time. The type unit level deduplication could be the last resort to handle the duplicates, like what is done in non-LTO build.

Not sure I follow - what duplication would remain if the thin link homed type descriptions? When linking to non-LTO (normal machine code/object files) libraries? Yeah, fair point (tangential warning: LLVM's type unit hashes are non-DWARF-conforming and not compatible with GCC's type unit hashes... :/)

It /sounds/ like, maybe the original fix in D62884 maybe was going in the wrong direction, and instead ThinLTO should be removing the comdat group from "homed" inline functions? Then there wouldn't be a need for a special case in how comdats are handled.

I am with @dblaikie here. A bit of archaeology finds that rG4de44b7ef87bcef83798eee69fdcbfab9866d52e was probably going in the wrong direction but it was indeed the simplest/least intrusive approach.
D62884 just made some refactorings. Just a thought: for ThinLTO backend, dropping comdat in processGlobalsForThinLTO may achieve some results.

Yeah, maybe something near/similar to https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Utils/FunctionImportUtils.cpp#L275 - where the comdat is imported as available externally, and its comdat group is stripped. Theory is, maybe we should be stripping the comdat on the other side too.

Hmm, maybe not, though? What about non-whole-program-ThinLTO? There could be a comdat copy of this function in a static library that it should be deduplicated against?

This is probably fine if the static library is a native input to lld , since lld itself can deduplicate comdat groups of its native input.

I take it the underlying assumption lld is making is that a comdat group is only kept alive by references from within the object file that defines it? Is that formally specified/required? If not, then maybe we could/should remoev that assumption, so that ThinLTO can work naturally with non-(Thin)LTO archives and still do the suitable comdat deduplication or dropping?

However, one issue is that on the MC layer the section group signature is part of ELFSectionKey.

.section foo,"aG",@progbits,aaa,comdat
.section foo,"aG",@progbits,bbb,comdat

are two sections. Dropping the comdat key will make them one combined section.

Is that a problem? When linked they end up in the same section, right?

Unique linkage may work around it but there may be a fair amount of complexity in TargetLoweringObjectFileImpl/MC.
I agree with pcc that LTO should not generate additional arbitrary comdat objects.

What additional arbitrary comdat objects are being generated or proposed to be generated?

So far the Dwarf types are the only new artifacts generated by the LTO backend. What I was wondering was new LTO-exclusive codegen passes that may introduce new comdat groups, but sound like it is a design principle that new symbols/data should be only generated in preLink LTO phase.

[dblaikie]

In D80765#2177208, @hoyFB wrote:

In D80765#2177014, @dblaikie wrote:

In D80765#2174269, @MaskRay wrote:

In D80765#2174250, @dblaikie wrote:

In D80765#2174141, @hoyFB wrote:

In D80765#2170820, @dblaikie wrote:

Yeah - one alternative here would be for ThinLTO To "home" debug type information, the same way I believe it "homes" inline functions. (original/incoming IR to the thinlink may have multiple definitions of inline functions - one in every module that has a call to the inline function - but something in the think link summary basically says "drop this definition" in all but one of those modules and in that one blessed module it says "always produce a weak definition of this function, even if you don't need it" - something like that should be done with type information, which would remove the redundancy in the object files)

In the case of a full executable link (with the homing above implemented), I'd then suggest not enabling type units, since they just add overhead and wouldn't reduce any duplication - in the case of a static library built with ThinLTO (if that's even a thing), then you'd still potentially want to use type units so they could be deduplicated against other libraries.

Enabling compile-time type deduplication is indeed an ideal solution, as you pointed out finding a prevailing symbol definition and dropping others for duplicate functions from different modules. This would require quite some work in parsing type metadata on the IR and might slow down thinLink.

Fair point - though presumably the first stage compile would do the metadata walk through the IR, provide a list of types in the thin summary file and the thin link would then communicate to the backend compiles specifying which types each backend compile should emit into its respective object file.

Also this may not completely address deduplication of new data introduced during LTO postLink code generation time. The type unit level deduplication could be the last resort to handle the duplicates, like what is done in non-LTO build.

Not sure I follow - what duplication would remain if the thin link homed type descriptions? When linking to non-LTO (normal machine code/object files) libraries? Yeah, fair point (tangential warning: LLVM's type unit hashes are non-DWARF-conforming and not compatible with GCC's type unit hashes... :/)

It /sounds/ like, maybe the original fix in D62884 maybe was going in the wrong direction, and instead ThinLTO should be removing the comdat group from "homed" inline functions? Then there wouldn't be a need for a special case in how comdats are handled.

I am with @dblaikie here. A bit of archaeology finds that rG4de44b7ef87bcef83798eee69fdcbfab9866d52e was probably going in the wrong direction but it was indeed the simplest/least intrusive approach.
D62884 just made some refactorings. Just a thought: for ThinLTO backend, dropping comdat in processGlobalsForThinLTO may achieve some results.

Yeah, maybe something near/similar to https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Utils/FunctionImportUtils.cpp#L275 - where the comdat is imported as available externally, and its comdat group is stripped. Theory is, maybe we should be stripping the comdat on the other side too.

Hmm, maybe not, though? What about non-whole-program-ThinLTO? There could be a comdat copy of this function in a static library that it should be deduplicated against?

This is probably fine if the static library is a native input to lld , since lld itself can deduplicate comdat groups of its native input.

Oh, yeah, fair point.

I take it the underlying assumption lld is making is that a comdat group is only kept alive by references from within the object file that defines it? Is that formally specified/required? If not, then maybe we could/should remoev that assumption, so that ThinLTO can work naturally with non-(Thin)LTO archives and still do the suitable comdat deduplication or dropping?

However, one issue is that on the MC layer the section group signature is part of ELFSectionKey.

.section foo,"aG",@progbits,aaa,comdat
.section foo,"aG",@progbits,bbb,comdat

are two sections. Dropping the comdat key will make them one combined section.

Is that a problem? When linked they end up in the same section, right?

Unique linkage may work around it but there may be a fair amount of complexity in TargetLoweringObjectFileImpl/MC.
I agree with pcc that LTO should not generate additional arbitrary comdat objects.

What additional arbitrary comdat objects are being generated or proposed to be generated?

So far the Dwarf types are the only new artifacts generated by the LTO backend.

Ah, OK, "new" in the sense that they weren't present as comdat groups in the ThinLTO input IR.

What do we gain by having this restriction? I guess it removes a certain amount of work the linker would otherwise do when performing the final link step in ThinLTO?

Anyone have a sense of the significance of that restriction compared to linking "as normal"?

lld/ELF/Driver.cpp

template <class ELFT> void LinkerDriver::compileBitcodeFiles() {
   llvm::TimeTraceScope timeScope("LTO");
   // Compile bitcode files and replace bitcode symbols.
   lto.reset(new BitcodeCompiler);
   for (BitcodeFile *file : bitcodeFiles)
     lto->add(*file);
 
   for (InputFile *file : lto->compile()) {
     auto *obj = cast<ObjFile<ELFT>>(file);
-    obj->parse(/*ignoreComdats=*/true);
+    obj->parse(/*isLTOOutput=*/true);
     for (Symbol *sym : obj->getGlobalSymbols())
       sym->parseSymbolVersion();
     objectFiles.push_back(file);
   }
 }
 
 // The --wrap option is a feature to rename symbols so that you can write
 // wrappers for existing functions. If you pass `-wrap=foo`, all

lld/ELF/InputFiles.h

public:
 
   ArrayRef<Symbol *> getLocalSymbols();
   ArrayRef<Symbol *> getGlobalSymbols();
 
   ObjFile(MemoryBufferRef m, StringRef archiveName) : ELFFileBase(ObjKind, m) {
     this->archiveName = std::string(archiveName);
   }
 
-  void parse(bool ignoreComdats = false);
+  void parse(bool isLTOOutput = false);
 
   StringRef getShtGroupSignature(ArrayRef<Elf_Shdr> sections,
                                  const Elf_Shdr &sec);
 
   Symbol &getSymbol(uint32_t symbolIndex) const {
     if (symbolIndex >= this->symbols.size())
       fatal(toString(this) + ": invalid symbol index");
     return *this->symbols[symbolIndex];
public:
 
   // SHT_LLVM_CALL_GRAPH_PROFILE table
   ArrayRef<Elf_CGProfile> cgProfile;
 
   // Get cached DWARF information.
   DWARFCache *getDwarf();
 
 private:
-  void initializeSections(bool ignoreComdats);
+  void initializeSections(bool isLTOOutput);
   void initializeSymbols();
   void initializeJustSymbols();
 
   InputSectionBase *getRelocTarget(const Elf_Shdr &sec);
   InputSectionBase *createInputSection(const Elf_Shdr &sec);
   StringRef getSectionName(const Elf_Shdr &sec);
 
   bool shouldMerge(const Elf_Shdr &sec, StringRef name);

lld/ELF/InputFiles.cpp

if (this->symbols.empty())
     return {};
   return makeArrayRef(this->symbols).slice(1, this->firstGlobal - 1);
 }
 
 template <class ELFT> ArrayRef<Symbol *> ObjFile<ELFT>::getGlobalSymbols() {
   return makeArrayRef(this->symbols).slice(this->firstGlobal);
 }
 
-template <class ELFT> void ObjFile<ELFT>::parse(bool ignoreComdats) {
+template <class ELFT> void ObjFile<ELFT>::parse(bool isLTOOutput) {
   // Read a section table. justSymbols is usually false.
   if (this->justSymbols)
     initializeJustSymbols();
   else
-    initializeSections(ignoreComdats);
+    initializeSections(isLTOOutput);
 
   // Read a symbol table.
   initializeSymbols();
 }
 
 // Sections with SHT_GROUP and comdat bits define comdat section groups.
 // They are identified and deduplicated by group name. This function
 // returns a group name.
for (uint32_t index : entries.slice(1)) {
     else
       head = s;
     prev = s;
   }
   if (prev)
     prev->nextInSectionGroup = head;
 }
 
-template <class ELFT>
-void ObjFile<ELFT>::initializeSections(bool ignoreComdats) {
+template <class ELFT> void ObjFile<ELFT>::initializeSections(bool isLTOOutput) {
   const ELFFile<ELFT> &obj = this->getObj();
 
   ArrayRef<Elf_Shdr> objSections = CHECK(obj.sections(), this);
   uint64_t size = objSections.size();
   this->sections.resize(size);
   this->sectionStringTable =
       CHECK(obj.getSectionStringTable(objSections), this);
 
case SHT_GROUP: {
       // An group with the empty flag doesn't define anything; such sections
       // are just skipped.
       if (entries[0] == 0)
         continue;
 
       if (entries[0] != GRP_COMDAT)
         fatal(toString(this) + ": unsupported SHT_GROUP format");
 
-      bool isNew =
-          ignoreComdats ||
-          symtab->comdatGroups.try_emplace(CachedHashStringRef(signature), this)
+      // If this is an lto output file, ignore already processed comdat groups.
+      // Else, check all comdat groups.
+      bool isNew = isLTOOutput
+                       ? symtab->ltoOutputComdatGroups
+                             .try_emplace(CachedHashStringRef(signature), this)
+                             .second
+                       : symtab->comdatGroups
+                             .try_emplace(CachedHashStringRef(signature), this)
                              .second;
       if (isNew) {
         if (config->relocatable)
           this->sections[i] = createInputSection(sec);
         selectedGroups.push_back(entries);
         continue;
       }
 
       // Otherwise, discard group members.
static Symbol *createBitcodeSymbol(const std::vector<bool> &keptComdats,
   Defined newSym(&f, name, binding, visibility, type, 0, 0, nullptr);
   if (canOmitFromDynSym)
     newSym.exportDynamic = false;
   return symtab->addSymbol(newSym);
 }
 
 template <class ELFT> void BitcodeFile::parse() {
   std::vector<bool> keptComdats;
   for (StringRef s : obj->getComdatTable())
     keptComdats.push_back(
         symtab->comdatGroups.try_emplace(CachedHashStringRef(s), this).second);
 
   for (const lto::InputFile::Symbol &objSym : obj->symbols())
     symbols.push_back(createBitcodeSymbol<ELFT>(keptComdats, objSym, *this));
 
   for (auto l : obj->getDependentLibraries())
     addDependentLibrary(l, this);
 }
 
 void BinaryFile::parse() {

lld/ELF/Relocations.cpp

static std::string maybeReportDiscarded(Undefined &sym) {
   msg += "\n>>> defined in " + toString(file);
 
   Elf_Shdr_Impl<ELFT> elfSec = objSections[sym.discardedSecIdx - 1];
   if (elfSec.sh_type != SHT_GROUP)
     return msg;
 
   // If the discarded section is a COMDAT.
   StringRef signature = file->getShtGroupSignature(objSections, elfSec);
-  if (const InputFile *prevailing =
-          symtab->comdatGroups.lookup(CachedHashStringRef(signature)))
+  const InputFile *prevailing =
+      symtab->comdatGroups.lookup(CachedHashStringRef(signature));
+  if (!prevailing)
+    prevailing =
+        symtab->ltoOutputComdatGroups.lookup(CachedHashStringRef(signature));
+  if (prevailing)
     msg += "\n>>> section group signature: " + signature.str() +
            "\n>>> prevailing definition is in " + toString(prevailing);
   return msg;
 }
 
 // Undefined diagnostics are collected in a vector and emitted once all of
 // them are known, so that some postprocessing on the list of undefined symbols
 // can happen before lld emits diagnostics.

lld/ELF/SymbolTable.h

public:
   // Set of .so files to not link the same shared object file more than once.
   llvm::DenseMap<StringRef, SharedFile *> soNames;
 
   // Comdat groups define "link once" sections. If two comdat groups have the
   // same name, only one of them is linked, and the other is ignored. This map
   // is used to uniquify them.
   llvm::DenseMap<llvm::CachedHashStringRef, const InputFile *> comdatGroups;
 
+  // We link twice in thinlto. A comdat group might be processed while it was
+  // in bitcode file where symbols are added but not defined, so when it is
+  // processed again as object file the symbol will be skipped and we end up
+  // with undefined symbols. Define a separate map of comdat groups for
+  // bitcode files to make sure the symbols are distinct from the ones found
+  // in object files
+  llvm::DenseMap<llvm::CachedHashStringRef, const InputFile *>
+      ltoOutputComdatGroups;
+
 private:
   std::vector<Symbol *> findByVersion(SymbolVersion ver);
   std::vector<Symbol *> findAllByVersion(SymbolVersion ver);
 
   llvm::StringMap<std::vector<Symbol *>> &getDemangledSyms();
   void assignExactVersion(SymbolVersion ver, uint16_t versionId,
                           StringRef versionName);
   void assignWildcardVersion(SymbolVersion ver, uint16_t versionId);

lld/test/ELF/lto/Inputs/debug-types-deduplication.ll

+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.foo = type { i32 }
+
+define dso_local i32 @_Z3bar3foo(i32 %0) noinline optnone !dbg !4 {
+  %2 = alloca %struct.foo, align 4
+  call void @llvm.dbg.declare(metadata %struct.foo* %2, metadata !10, metadata !DIExpression()), !dbg !11
+  ret i32 0, !dbg !12
+}
+
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, emissionKind: FullDebug)
+!1 = !DIFile(filename: "foo.cc", directory: "")
+!2 = !{i32 7, !"Dwarf Version", i32 4}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = distinct !DISubprogram(name: "bar", linkageName: "_Z3bar3foo", type: !5, unit: !0)
+!5 = !DISubroutineType(types: !{!6, !7})
+!6 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!7 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "foo", file: !8, line: 4, size: 32, flags: DIFlagTypePassByValue, elements: !{!9}, identifier: "_ZTS3foo")
+!8 = !DIFile(filename: "./foo.h", directory: "")
+!9 = !DIDerivedType(tag: DW_TAG_member, name: "f", scope: !7, file: !8, line: 4, baseType: !6, size: 32)
+!10 = !DILocalVariable(name: "f1", arg: 1, scope: !4, file: !1, line: 3, type: !7)
+!11 = !DILocation(line: 1, column: 1, scope: !4)
+!12 = !DILocation(line: 2, column: 1, scope: !4)
+
+^0 = module: (path: "foo.o", hash: (505897185, 3065645384, 2109903963, 2773340897, 2672438121))
+^1 = gv: (name: "_Z3bar3foo", summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 1, canAutoHide: 0), insts: 6, funcFlags: (readNone: 0, readOnly: 0, noRecurse: 0, returnDoesNotAlias: 0, noInline: 1, alwaysInline: 0)))) ; guid = 11911810691311191905

lld/test/ELF/lto/debug-types-deduplication.ll

+; REQUIRES: x86
+; RUN: llvm-as %s -o %t.o
+; RUN: llvm-as %p/Inputs/debug-types-deduplication.ll -o %t2.o
+; RUN: ld.lld %t.o %t2.o -mllvm --generate-type-units --entry=main -o %t3.o
+; RUN: llvm-dwarfdump --debug-types %t3.o | FileCheck %s
+
+; CHECK-COUNT-1: Type Unit:
+; CHECK-NOT: Type Unit:
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.foo = type { i32 }
+
+define dso_local i32 @main() noinline optnone !dbg !4 {
+  %1 = alloca %struct.foo, align 4
+  call void @llvm.dbg.declare(metadata %struct.foo* %1, metadata !7, metadata !DIExpression()), !dbg !11
+  ret i32 0, !dbg !12
+}
+
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+
+declare dso_local i32 @_Z3bar3foo(i32)
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i64, i1 immarg)
+
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, emissionKind: FullDebug)
+!1 = !DIFile(filename: "hello.cc", directory: "")
+!2 = !{i32 7, !"Dwarf Version", i32 4}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = distinct !DISubprogram(name: "main", type: !5, unit: !0)
+!5 = !DISubroutineType(types: !{!6})
+!6 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!7 = !DILocalVariable(name: "f1", scope: !4, file: !1,type: !8)
+!8 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "foo", file: !9, line: 4, size: 32, flags: DIFlagTypePassByValue, elements: !{!10}, identifier: "_ZTS3foo")
+!9 = !DIFile(filename: "./foo.h", directory: "")
+!10 = !DIDerivedType(tag: DW_TAG_member, name: "f", scope: !8, file: !9, line: 4, baseType: !6, size: 32)
+!11 = !DILocation(line: 1, column: 1, scope: !4)
+!12 = !DILocation(line: 2, column: 2, scope: !4)
+
+^0 = module: (path: "hello.o", hash: (339834615, 71091658, 394989773, 1362321694, 1785275294))