[InstrProf] Add support for dead_strip+live_support functionality

[vsk]

Summary

On Darwin, marking a section as "regular,live_support" means that a
symbol in the section should only be kept live if it has a reference to
something that is live. Otherwise, the linker is free to dead-strip it.

Turn this functionality on for the __llvm_prf_data section.

This means that counters, names, and data associated with dead functions
will be removed from dead-stripped binaries. This will result in smaller
profiles and binaries, and should speed up profile collection.

Tested with check-profile, llvm-lit test/tools/llvm-{cov,profdata}, and
check-llvm.

[mehdi_amini]

LGTM.

Are these symbols already in the "llvm.compiler_used" list?

[davidxl]

include/llvm/ProfileData/InstrProf.h

58 ↗

(On Diff #74191)

What is the exact meaning of this attribute? Does it mark the section 'not' the root of the reference graph (which allows symbols just referenced from this section to be GCed)?

Garbage collection for dead function (with profile instrumentation) is currently also broken on Linux because -fdata-sections is not honored by for prof data symbols.

[mehdi_amini]

include/llvm/ProfileData/InstrProf.h

58 ↗

(On Diff #74191)

I see this section as "reversing" the edges in the dead-strip algorithm: if a symbol foo is in the live_support section, the linker will keep it alive if the symbols *referenced by* foo are live.
(Nothing is expected to reference foo).

[vsk]

In D25456#566944, @mehdi_amini wrote:

Are these symbols already in the "llvm.compiler_used" list?

No, contents of __llvm_prf_data are in llvm.used, which is a bit stricter. Actually, this is very unexpected.. is dead-stripping of live_support sections supposed to kick in for symbols in the llvm.used list? I only expect this to happen for the llvm.compiler_used list.

include/llvm/ProfileData/InstrProf.h

58 ↗

(On Diff #74191)

This is better than my explanation, thanks Mehdi :).

It's true that symbols referenced by data in a "live_support" section may be GC'd, but it's only interesting the other way: if we could GC a symbol by not treating "live_support" uses as "critical", then we GC the symbol and its uses.

[mehdi_amini]

In D25456#566952, @vsk wrote:

In D25456#566944, @mehdi_amini wrote:

Are these symbols already in the "llvm.compiler_used" list?

No, contents of __llvm_prf_data are in llvm.used, which is a bit stricter. Actually, this is very unexpected.. is dead-stripping of live_support sections supposed to kick in for symbols in the llvm.used list? I only expect this to happen for the llvm.compiler_used list.

Well, in theory we should use llvm.compiler_used, but by "chance" ld64 ignore the "no dead strip" attribute (that results from llvm.used) when doing the special processing for "live_support"

[davidxl]

include/llvm/ProfileData/InstrProf.h

58 ↗

(On Diff #74191)

The reversing edge is a good way to explain it -- which has two effects:

1. the references from the section is ignored
2. if the section ends up referencing non or only dead symbols, it is dead too.

Note that all per-function prof data are put in the same section -- so the second effect won't kick in unless fdata-sections is effective too.

[mehdi_amini]

include/llvm/ProfileData/InstrProf.h

58 ↗

(On Diff #74191)

On MachO, -fdata-sections -ffunction-sections can't be turned off (AFAIK) :)
Every symbol is an "atom", i.e. a node in the graph formed by all the symbols (nodes) in the program and their references (edges).

[davidxl]

include/llvm/ProfileData/InstrProf.h

58 ↗

(On Diff #74191)

That is a nice feature.

[davidxl]

lgtm

[MaskRay]

I've made ELF GC work in https://reviews.llvm.org/D97585 and am trying D103372 which will make (to a large extent) Windows GC work.

My question is whether S_ATTR_LIVE_SUPPORT suppresses N_NO_DEAD_STRIP on Darwin.

% cat a.ll
@bar = external global void ()*, align 8

define void @foo() {
entry:
  %tmp = load void ()*, void ()** @bar, align 8
  call void %tmp()
  ret void
}
% opt -mtriple=x86_64-apple-darwin -passes=pgo-instr-gen,instrprof -S < a.ll | llc -mtriple=x86_64-apple-darwin -filetype=obj -function-sections -o a.o

l___profd_foo has N_NO_DEAD_STRIP (due to llvm.used) while its section has S_ATTR_LIVE_SUPPORT. Is N_NO_DEAD_STRIP ignored in this case?
If not the GC doesn't kick in.
@thakis may be interested in this for the ld64.lld -dead_strip implementation (D103324).

[thakis]

In D25456#2788418, @MaskRay wrote:

I've made ELF GC work in https://reviews.llvm.org/D97585 and am trying D103372 which will make (to a large extent) Windows GC work.

My question is whether S_ATTR_LIVE_SUPPORT suppresses N_NO_DEAD_STRIP on Darwin.

I thought I read somewhere that ld64 happens to ignore it…oh it was right here on this review: https://reviews.llvm.org/D25456#566954

lld doesn't ignore it in my implementation as that seems more semantically correct: Mach-O has a hierarchy of segment->section->"subsection" where the latter is associated with a symbol. N_NO_DEAD_STRIP is set on a symbol, so it feels like it's a more local concept that should win over the more global S_ATTR_LIVE_SUPPORT.

l___profd_foo has N_NO_DEAD_STRIP (due to llvm.used) while its section has S_ATTR_LIVE_SUPPORT. Is N_NO_DEAD_STRIP ignored in this case?
If not the GC doesn't kick in.

If we want l___profd_foo to be stripped, maybe we shouldn't mark it N_NO_DEAD_STRIP then?

@thakis may be interested in this for the ld64.lld -dead_strip implementation (D103324).

[vsk]

If llvm stopped appending __profd_foo to llvm.compiler.used, there might not be anything left to prevent the optimizer from discarding it. The current scheme of having the linker ignore N_NO_DEAD_STRIP if S_ATTR_LIVE_SUPPORT is in effect seems like a neat way to solve the issue. Is there a tidy alternative?

[MaskRay]

In D25456#2794689, @vsk wrote:

If llvm stopped appending __profd_foo to llvm.compiler.used, there might not be anything left to prevent the optimizer from discarding it. The current scheme of having the linker ignore N_NO_DEAD_STRIP if S_ATTR_LIVE_SUPPORT is in effect seems like a neat way to solve the issue. Is there a tidy alternative?

Currently __profd_foo is in llvm.used instead of llvm.compiler.used on Mach-O.

D103372 My thought (but I don't have a device to test) is that Mach-O can use appendToCompilerUsed(*M, CompilerUsedVars); as well.

[vsk]

In D25456#2796732, @MaskRay wrote:

In D25456#2794689, @vsk wrote:

If llvm stopped appending __profd_foo to llvm.compiler.used, there might not be anything left to prevent the optimizer from discarding it. The current scheme of having the linker ignore N_NO_DEAD_STRIP if S_ATTR_LIVE_SUPPORT is in effect seems like a neat way to solve the issue. Is there a tidy alternative?

Currently __profd_foo is in llvm.used instead of llvm.compiler.used on Mach-O.

D103372 My thought (but I don't have a device to test) is that Mach-O can use appendToCompilerUsed(*M, CompilerUsedVars); as well.

That's a good point: adding __profd_X to llvm.compiler.used should prevent llvm's optimizer from deleting it. But is it sufficient to guarantee that linker (ld64/lld.macho) optimizations will not delete it?

llvm/trunk/include/llvm/ProfileData/InstrProf.h

inline StringRef getInstrProfNameSectionName(bool AddSegment) {
   return AddSegment ? "__DATA," INSTR_PROF_NAME_SECT_NAME_STR
                     : INSTR_PROF_NAME_SECT_NAME_STR;
 }
 
 /// Return the name of the data section containing per-function control
 /// data.
 inline StringRef getInstrProfDataSectionName(bool AddSegment) {
   return AddSegment ? "__DATA," INSTR_PROF_DATA_SECT_NAME_STR
+                      ",regular,live_support"
                     : INSTR_PROF_DATA_SECT_NAME_STR;
 }
 
 /// Return the name of data section containing pointers to value profile
 /// counters/nodes.
 inline StringRef getInstrProfValuesSectionName(bool AddSegment) {
   return AddSegment ? "__DATA," INSTR_PROF_VALS_SECT_NAME_STR
                     : INSTR_PROF_VALS_SECT_NAME_STR;

llvm/trunk/test/Instrumentation/InstrProfiling/PR23499.ll

 ; RUN: opt < %s -mtriple=x86_64-pc-win32-coff -passes=instrprof -S | FileCheck %s --check-prefix=COFF
 
 $_Z3barIvEvv = comdat any
 
 @__profn__Z3barIvEvv = linkonce_odr hidden constant [11 x i8] c"_Z3barIvEvv", align 1
 
 ; CHECK: @__profn__Z3barIvEvv = private constant [11 x i8] c"_Z3barIvEvv", align 1
 ; CHECK: @__profc__Z3barIvEvv = linkonce_odr hidden global [1 x i64] zeroinitializer, section "{{.*}}__llvm_prf_cnts", comdat($__profv__Z3barIvEvv), align 8
-; CHECK: @__profd__Z3barIvEvv = linkonce_odr hidden global { i64, i64, i64*, i8*, i8*, i32, [1 x i16] } { i64 4947693190065689389, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__Z3barIvEvv, i32 0, i32 0), i8*{{.*}}, i8* null, i32 1, [1 x i16] zeroinitializer }, section "{{.*}}__llvm_prf_data", comdat($__profv__Z3barIvEvv), align 8
+; CHECK: @__profd__Z3barIvEvv = linkonce_odr hidden global { i64, i64, i64*, i8*, i8*, i32, [1 x i16] } { i64 4947693190065689389, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__Z3barIvEvv, i32 0, i32 0), i8*{{.*}}, i8* null, i32 1, [1 x i16] zeroinitializer }, section "{{.*}}__llvm_prf_data{{.*}}", comdat($__profv__Z3barIvEvv), align 8
 ; CHECK: @__llvm_prf_nm = private constant [{{.*}} x i8] c"{{.*}}", section "{{.*}}__llvm_prf_names"
 
 
 ; COFF: @__profn__Z3barIvEvv = private constant [11 x i8] c"_Z3barIvEvv", align 1
 ; COFF: @__profc__Z3barIvEvv = linkonce_odr hidden global [1 x i64] zeroinitializer, section "{{.*}}__llvm_prf_cnts", comdat, align 8
-; COFF: @__profd__Z3barIvEvv = linkonce_odr hidden global { i64, i64, i64*, i8*, i8*, i32, [1 x i16] } { i64 4947693190065689389, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__Z3barIvEvv, i32 0, i32 0), i8*{{.*}}, i8* null, i32 1, [1 x i16] zeroinitializer }, section "{{.*}}__llvm_prf_data", comdat($__profc__Z3barIvEvv), align 8
+; COFF: @__profd__Z3barIvEvv = linkonce_odr hidden global { i64, i64, i64*, i8*, i8*, i32, [1 x i16] } { i64 4947693190065689389, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__Z3barIvEvv, i32 0, i32 0), i8*{{.*}}, i8* null, i32 1, [1 x i16] zeroinitializer }, section "{{.*}}__llvm_prf_data{{.*}}", comdat($__profc__Z3barIvEvv), align 8
 
 
 declare void @llvm.instrprof.increment(i8*, i64, i32, i32) #1
 
 define linkonce_odr void @_Z3barIvEvv() comdat {
 entry:
   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @__profn__Z3barIvEvv, i32 0, i32 0), i64 0, i32 1, i32 0)
   ret void
 }

llvm/trunk/test/Instrumentation/InstrProfiling/platform.ll

 
 @__profn_foo = hidden constant [3 x i8] c"foo"
 ; MACHO: @__profn_foo = private constant [3 x i8] c"foo"
 ; ELF: @__profn_foo = private constant [3 x i8] c"foo"
 
 ; MACHO: @__profc_foo = hidden global [1 x i64] zeroinitializer, section "__DATA,__llvm_prf_cnts", align 8
 ; ELF: @__profc_foo = hidden global [1 x i64] zeroinitializer, section "__llvm_prf_cnts", align 8
 
-; MACHO: @__profd_foo = hidden {{.*}}, section "__DATA,__llvm_prf_data", align 8
+; MACHO: @__profd_foo = hidden {{.*}}, section "__DATA,__llvm_prf_data,regular,live_support", align 8
 ; LINUX: @__profd_foo = hidden {{.*}}, section "__llvm_prf_data", align 8
 ; FREEBSD: @__profd_foo = hidden {{.*}}, section "__llvm_prf_data", align 8
 ; PS4: @__profd_foo = hidden {{.*}}, section "__llvm_prf_data", align 8
 ; SOLARIS: @__profd_foo = hidden {{.*}}, section "__llvm_prf_data", align 8
 
 ; ELF: @__llvm_prf_nm = private constant [{{.*}} x i8] c"{{.*}}", section "{{.*}}__llvm_prf_names"
 
 define void @foo() {

llvm/trunk/test/Instrumentation/InstrProfiling/profiling.ll

 ; RUN: opt < %s -instrprof -S | FileCheck %s
 ; RUN: opt < %s -passes=instrprof -S | FileCheck %s
 
 target triple = "x86_64-apple-macosx10.10.0"
 
 @__profn_foo = hidden constant [3 x i8] c"foo"
 ; CHECK: @__profn_foo = private constant [3 x i8] c"foo"
 @__profn_bar = hidden constant [4 x i8] c"bar\00"
 ; CHECK: @__profn_bar = private constant [4 x i8] c"bar\00"
 @__profn_baz = hidden constant [3 x i8] c"baz"
 ; CHECK: @__profn_baz = private constant [3 x i8] c"baz"
 
 ; CHECK: @__profc_foo = hidden global [1 x i64] zeroinitializer, section "__DATA,__llvm_prf_cnts", align 8
-; CHECK: @__profd_foo = hidden {{.*}}, section "__DATA,__llvm_prf_data", align 8
+; CHECK: @__profd_foo = hidden {{.*}}, section "__DATA,__llvm_prf_data,regular,live_support", align 8
 define void @foo() {
   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_foo, i32 0, i32 0), i64 0, i32 1, i32 0)
   ret void
 }
 
 ; CHECK: @__profc_bar = hidden global [1 x i64] zeroinitializer, section "__DATA,__llvm_prf_cnts", align 8
-; CHECK: @__profd_bar = hidden {{.*}}, section "__DATA,__llvm_prf_data", align 8
+; CHECK: @__profd_bar = hidden {{.*}}, section "__DATA,__llvm_prf_data,regular,live_support", align 8
 define void @bar() {
   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @__profn_bar, i32 0, i32 0), i64 0, i32 1, i32 0)
   ret void
 }
 
 ; CHECK: @__profc_baz = hidden global [3 x i64] zeroinitializer, section "__DATA,__llvm_prf_cnts", align 8
-; CHECK: @__profd_baz = hidden {{.*}}, section "__DATA,__llvm_prf_data", align 8
+; CHECK: @__profd_baz = hidden {{.*}}, section "__DATA,__llvm_prf_data,regular,live_support", align 8
 define void @baz() {
   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_baz, i32 0, i32 0), i64 0, i32 3, i32 0)
   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_baz, i32 0, i32 0), i64 0, i32 3, i32 1)
   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_baz, i32 0, i32 0), i64 0, i32 3, i32 2)
   ret void
 }
 
 declare void @llvm.instrprof.increment(i8*, i64, i32, i32)
 
 ; CHECK: @__llvm_profile_runtime = external global i32
 ; CHECK: @llvm.used = appending global {{.*}} @__profd_foo {{.*}} @__profd_bar {{.*}} @__profd_baz {{.*}} section "llvm.metadata"