llvm dev - May 2018 - Proposal for address-significance tables for --icf=safe

On Wed, May 23, 2018 at 3:25 AM, Peter Smith <peter.smith at linaro.org>
wrote:
> Hello,
>
> I think that the approach of using a section to record address
> significance is a good one. I'm guessing it will have its own section
> type and format? If it does would it make sense to try and submit this
> to the GABI https://groups.google.com/forum/#!forum/generic-abi as it
> could be potentially useful for other linkers, for example gold?
>
Yes, there is a new section type (SHT_LLVM_ADDRSIG) and format (a sequence
of ULEB128-encoded symbol table indexes that are address-significant).

I think it makes sense for this to eventually be part of the generic ABI,
and I will send a proposal to generic-abi. As I mentioned in my reply to
James Knight, I don't think we should block on getting a section number
assignment, but we can at least incorporate any design feedback from that
proposal.

Peter


> Happy to help out with reviews.
>
> Peter
>
>
> On 22 May 2018 at 23:06, Peter Collingbourne via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > Hi all,
> >
> > Context: ld.gold has an --icf=safe flag which is intended to apply ICF
> only
> > to sections which can be safely merged according to the guarantees
> provided
> > by the language. It works using a set of heuristics (symbol name
matching
> > and relocation scanning). That's not only imprecise but it only
works
> with
> > certain languages and is slow due to the need to demangle symbols and
> scan
> > relocations. It's also redundant with the (local_)unnamed_addr
analysis
> > already performed by LLVM.
> >
> > I implemented an alternative to this approach in clang and lld. It
works
> by
> > adding a section to each object file containing the indexes of the
> symbols
> > which are address-significant (i.e. not (local_)unnamed_addr in IR).
> >
> > I used this implementation to link clang with release+asserts with
each
> of
> > --icf={none,safe,all}. The binary sizes were:
> >
> > none: 109407184
> > safe: 108534736 (-0.8%)
> > all: 107281360 (-2%)
> >
> > I measured the object file overhead of these sections in my clang
build
> at
> > 0.08%. That's almost nothing, and I think it's small enough
that we can
> turn
> > it on by default.
> >
> > I've uploaded a patch series for this feature here:
> > https://github.com/pcc/llvm-project/tree/llvm-addrsig
> > I intend to start sending it for review soon.
> >
> > Thanks,
> > --
> > --
> > Peter
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
>


-- 
-- 
Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180523/a7a7420a/attachment.html>

On Wed, May 23, 2018 at 12:16 PM, Peter Collingbourne <peter at pcc.me.uk>
wrote:
> On Wed, May 23, 2018 at 3:25 AM, Peter Smith <peter.smith at
linaro.org>
> wrote:
>
>> Hello,
>>
>> I think that the approach of using a section to record address
>> significance is a good one. I'm guessing it will have its own
section
>> type and format? If it does would it make sense to try and submit this
>> to the GABI https://groups.google.com/forum/#!forum/generic-abi as it
>> could be potentially useful for other linkers, for example gold?
>>
>
> Yes, there is a new section type (SHT_LLVM_ADDRSIG) and format (a sequence
> of ULEB128-encoded symbol table indexes that are address-significant).
>
> I think it makes sense for this to eventually be part of the generic ABI,
> and I will send a proposal to generic-abi. As I mentioned in my reply to
> James Knight, I don't think we should block on getting a section number
> assignment, but we can at least incorporate any design feedback from that
> proposal.
>
I've sent the proposal:
https://groups.google.com/forum/#!topic/generic-abi/MPr8TVtnVn4

Peter
>
> Peter
>
>
>
>> Happy to help out with reviews.
>>
>> Peter
>>
>>
>> On 22 May 2018 at 23:06, Peter Collingbourne via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>> > Hi all,
>> >
>> > Context: ld.gold has an --icf=safe flag which is intended to apply
ICF
>> only
>> > to sections which can be safely merged according to the guarantees
>> provided
>> > by the language. It works using a set of heuristics (symbol name
>> matching
>> > and relocation scanning). That's not only imprecise but it
only works
>> with
>> > certain languages and is slow due to the need to demangle symbols
and
>> scan
>> > relocations. It's also redundant with the (local_)unnamed_addr
analysis
>> > already performed by LLVM.
>> >
>> > I implemented an alternative to this approach in clang and lld. It
>> works by
>> > adding a section to each object file containing the indexes of the
>> symbols
>> > which are address-significant (i.e. not (local_)unnamed_addr in
IR).
>> >
>> > I used this implementation to link clang with release+asserts with
each
>> of
>> > --icf={none,safe,all}. The binary sizes were:
>> >
>> > none: 109407184
>> > safe: 108534736 (-0.8%)
>> > all: 107281360 (-2%)
>> >
>> > I measured the object file overhead of these sections in my clang
build
>> at
>> > 0.08%. That's almost nothing, and I think it's small
enough that we can
>> turn
>> > it on by default.
>> >
>> > I've uploaded a patch series for this feature here:
>> > https://github.com/pcc/llvm-project/tree/llvm-addrsig
>> > I intend to start sending it for review soon.
>> >
>> > Thanks,
>> > --
>> > --
>> > Peter
>> >
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > llvm-dev at lists.llvm.org
>> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> >
>>
>
>
>
> --
> --
> Peter
>


-- 
-- 
Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180523/c2168edd/attachment.html>

On 23 May 2018 at 23:07, Peter Collingbourne <peter at pcc.me.uk>
wrote:
>
>
> On Wed, May 23, 2018 at 12:16 PM, Peter Collingbourne <peter at
pcc.me.uk>
> wrote:
>>
>> On Wed, May 23, 2018 at 3:25 AM, Peter Smith <peter.smith at
linaro.org>
>> wrote:
>>>
>>> Hello,
>>>
>>> I think that the approach of using a section to record address
>>> significance is a good one. I'm guessing it will have its own
section
>>> type and format? If it does would it make sense to try and submit
this
>>> to the GABI https://groups.google.com/forum/#!forum/generic-abi as
it
>>> could be potentially useful for other linkers, for example gold?
>>
>>
>> Yes, there is a new section type (SHT_LLVM_ADDRSIG) and format (a
sequence
>> of ULEB128-encoded symbol table indexes that are address-significant).
>>
>> I think it makes sense for this to eventually be part of the generic
ABI,
>> and I will send a proposal to generic-abi. As I mentioned in my reply
to
>> James Knight, I don't think we should block on getting a section
number
>> assignment, but we can at least incorporate any design feedback from
that
>> proposal.
>
>
> I've sent the proposal:
> https://groups.google.com/forum/#!topic/generic-abi/MPr8TVtnVn4
>
> Peter
Thanks. I agree we shouldn't require it to be in the GABI before
proceeding. I think making the proposal more visible to the wider
community will already have been worthwhile.

In the absence of a GABI defined way to tell if an ELF processing tool
may have broken the symbol table order, one possible option might be
to reserve the first entry as some hash of the symbol names that would
be different if the indexes into the symbol table were changed. This
does make it more complicated for an object processing tool to handle
the section though.

Peter

Hi Peter,

Thanks for doing this!

On Wed, May 23, 2018 at 3:07 PM Peter Collingbourne via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
>
> On Wed, May 23, 2018 at 12:16 PM, Peter Collingbourne <peter at
pcc.me.uk>
> wrote:
>
>> On Wed, May 23, 2018 at 3:25 AM, Peter Smith <peter.smith at
linaro.org>
>> wrote:
>>
>>> Hello,
>>>
>>> I think that the approach of using a section to record address
>>> significance is a good one. I'm guessing it will have its own
section
>>> type and format? If it does would it make sense to try and submit
this
>>> to the GABI https://groups.google.com/forum/#!forum/generic-abi as
it
>>> could be potentially useful for other linkers, for example gold?
>>>
>>
>> Yes, there is a new section type (SHT_LLVM_ADDRSIG) and format (a
>> sequence of ULEB128-encoded symbol table indexes that are
>> address-significant).
>>
>> I think it makes sense for this to eventually be part of the generic
ABI,
>> and I will send a proposal to generic-abi. As I mentioned in my reply
to
>> James Knight, I don't think we should block on getting a section
number
>> assignment, but we can at least incorporate any design feedback from
that
>> proposal.
>>
>
> I've sent the proposal:
> https://groups.google.com/forum/#!topic/generic-abi/MPr8TVtnVn4
>
>
The proposal looks decent. I'll probably comment more once I (like the
others) get a chance to read more deeply. I've also taken a look at the
basic patches - one request is that since this is newly standardizing bits
that you make sure to comment or even put a detailed standards-esque
description of the tables into the code?

-eric



> Peter
>
>>
>> Peter
>>
>>
>>
>>> Happy to help out with reviews.
>>>
>>> Peter
>>>
>>>
>>> On 22 May 2018 at 23:06, Peter Collingbourne via llvm-dev
>>> <llvm-dev at lists.llvm.org> wrote:
>>> > Hi all,
>>> >
>>> > Context: ld.gold has an --icf=safe flag which is intended to
apply ICF
>>> only
>>> > to sections which can be safely merged according to the
guarantees
>>> provided
>>> > by the language. It works using a set of heuristics (symbol
name
>>> matching
>>> > and relocation scanning). That's not only imprecise but it
only works
>>> with
>>> > certain languages and is slow due to the need to demangle
symbols and
>>> scan
>>> > relocations. It's also redundant with the
(local_)unnamed_addr analysis
>>> > already performed by LLVM.
>>> >
>>> > I implemented an alternative to this approach in clang and
lld. It
>>> works by
>>> > adding a section to each object file containing the indexes of
the
>>> symbols
>>> > which are address-significant (i.e. not (local_)unnamed_addr
in IR).
>>> >
>>> > I used this implementation to link clang with release+asserts
with
>>> each of
>>> > --icf={none,safe,all}. The binary sizes were:
>>> >
>>> > none: 109407184
>>> > safe: 108534736 (-0.8%)
>>> > all: 107281360 (-2%)
>>> >
>>> > I measured the object file overhead of these sections in my
clang
>>> build at
>>> > 0.08%. That's almost nothing, and I think it's small
enough that we
>>> can turn
>>> > it on by default.
>>> >
>>> > I've uploaded a patch series for this feature here:
>>> > https://github.com/pcc/llvm-project/tree/llvm-addrsig
>>> > I intend to start sending it for review soon.
>>> >
>>> > Thanks,
>>> > --
>>> > --
>>> > Peter
>>> >
>>> > _______________________________________________
>>> > LLVM Developers mailing list
>>> > llvm-dev at lists.llvm.org
>>> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>> >
>>>
>>
>>
>>
>> --
>> --
>> Peter
>>
>
>
>
> --
> --
> Peter
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180524/e0cc9884/attachment.html>

On Wed, May 23, 2018 at 3:07 PM, Peter Collingbourne <peter at pcc.me.uk>
wrote:
>
>
> On Wed, May 23, 2018 at 12:16 PM, Peter Collingbourne <peter at
pcc.me.uk>
> wrote:
>
>> On Wed, May 23, 2018 at 3:25 AM, Peter Smith <peter.smith at
linaro.org>
>> wrote:
>>
>>> Hello,
>>>
>>> I think that the approach of using a section to record address
>>> significance is a good one. I'm guessing it will have its own
section
>>> type and format? If it does would it make sense to try and submit
this
>>> to the GABI https://groups.google.com/forum/#!forum/generic-abi as
it
>>> could be potentially useful for other linkers, for example gold?
>>>
>>
>> Yes, there is a new section type (SHT_LLVM_ADDRSIG) and format (a
>> sequence of ULEB128-encoded symbol table indexes that are
>> address-significant).
>>
>> I think it makes sense for this to eventually be part of the generic
ABI,
>> and I will send a proposal to generic-abi. As I mentioned in my reply
to
>> James Knight, I don't think we should block on getting a section
number
>> assignment, but we can at least incorporate any design feedback from
that
>> proposal.
>>
>
> I've sent the proposal: https://groups.google.com/foru
> m/#!topic/generic-abi/MPr8TVtnVn4
>
Based on feedback from the generic-abi thread I looked at the object file
size and link time impact of a few other representations for the
address-significance table. My results are here: https://groups.google.
com/d/msg/generic-abi/MPr8TVtnVn4/30Z0_KHMAQAJ

One of the proposals (a compressed array of symbol attributes) is slightly
more expensive than what I originally proposed (+0.03% object file size,
+1% link time) but it would allow for future expansion and therefore seems
more appropriate for the gABI. That's not really a concern for us though
since the initial implementation will use a platform-specific section
number, and we can always switch to the gABI representation at the same
time as we adopt the gABI section numbers. There's also the possibility
that we will end up doing something completely different in the gABI.

Does anyone have a strong opinion that we should do something more aligned
with the gABI? If not, I'll start upstreaming my original proposal.

Peter
>
> Peter
>
>>
>> Peter
>>
>>
>>
>>> Happy to help out with reviews.
>>>
>>> Peter
>>>
>>>
>>> On 22 May 2018 at 23:06, Peter Collingbourne via llvm-dev
>>> <llvm-dev at lists.llvm.org> wrote:
>>> > Hi all,
>>> >
>>> > Context: ld.gold has an --icf=safe flag which is intended to
apply ICF
>>> only
>>> > to sections which can be safely merged according to the
guarantees
>>> provided
>>> > by the language. It works using a set of heuristics (symbol
name
>>> matching
>>> > and relocation scanning). That's not only imprecise but it
only works
>>> with
>>> > certain languages and is slow due to the need to demangle
symbols and
>>> scan
>>> > relocations. It's also redundant with the
(local_)unnamed_addr analysis
>>> > already performed by LLVM.
>>> >
>>> > I implemented an alternative to this approach in clang and
lld. It
>>> works by
>>> > adding a section to each object file containing the indexes of
the
>>> symbols
>>> > which are address-significant (i.e. not (local_)unnamed_addr
in IR).
>>> >
>>> > I used this implementation to link clang with release+asserts
with
>>> each of
>>> > --icf={none,safe,all}. The binary sizes were:
>>> >
>>> > none: 109407184
>>> > safe: 108534736 (-0.8%)
>>> > all: 107281360 (-2%)
>>> >
>>> > I measured the object file overhead of these sections in my
clang
>>> build at
>>> > 0.08%. That's almost nothing, and I think it's small
enough that we
>>> can turn
>>> > it on by default.
>>> >
>>> > I've uploaded a patch series for this feature here:
>>> > https://github.com/pcc/llvm-project/tree/llvm-addrsig
>>> > I intend to start sending it for review soon.
>>> >
>>> > Thanks,
>>> > --
>>> > --
>>> > Peter
>>> >
>>> > _______________________________________________
>>> > LLVM Developers mailing list
>>> > llvm-dev at lists.llvm.org
>>> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>> >
>>>
>>
>>
>>
>> --
>> --
>> Peter
>>
>
>
>
> --
> --
> Peter
>


-- 
-- 
Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180531/35c5ba60/attachment.html>