This is an archive of the discontinued LLVM Phabricator instance.

[LLD][ELF] Improve ICF for relocations to ineligible sections via "aliases"
ClosedPublic

Authored by andrewng on Oct 5 2020, 6:10 AM.

Details

Summary

ICF was not able to merge equivalent sections because of relocations to
sections ineligible for ICF that use alternative symbols, e.g. symbol
aliases or section relative relocations.

Merging in this scenario has been enabled by giving the sections that
are ineligigle for ICF a unique ID, i.e. an equivalence class of their
own. This approach also provides another benefit as it improves the
hashing that is used to perform the initial equivalance grouping for
ICF. This is because the ICF ineligible sections can now contribute a
unique value towards the hashes instead of the same value of zero. This
has been seen to reduce link time with ICF by ~68% for objects compiled
with -fprofile-instr-generate.

In order to facilitate this use of a unique ID, the existing
inconsistent approach to the setting of the InputSection eqClass in ICF
has been changed so that there is a clear distinction between the
eqClass values of ICF eligible sections and those of the ineligible
sections that have a unique ID. This inconsistency could have caused
incorrect equivalence class equality in the past, although it appears
that no issues were encountered in actual use.

Diff Detail

Event Timeline

andrewng created this revision.Oct 5 2020, 6:10 AM
andrewng requested review of this revision.Oct 5 2020, 6:10 AM

The description can be shortened a bit. The important part is that variableEq returns false if two relocations reference a pair of aliased symbols in an ineligible section.

lld/ELF/ICF.cpp
227

Here this actually computes non-hash IDs. Clearing the MSB (the original code) is better.

357–358

This comment is stale. This code may be deletable.

476

Same comment: this is unneeded. combineRelocHashes updates eqClass[1]

485

This needs a comment. Ineligible sections are assigned unique IDs so that two sections referencing different ineligible sections can be separated.

MaskRay added inline comments.Oct 5 2020, 6:07 PM
lld/ELF/ICF.cpp
227

hmm. the idea is to make this distinct from a uniqueID.

Let uniqueId start from inputSections.size()?

MaskRay retitled this revision from [LLD][ELF] Improve ICF for relocations to sections via "aliases" to [LLD][ELF] Improve ICF for relocations to ineligible sections via "aliases".Oct 5 2020, 6:08 PM
MaskRay added inline comments.Oct 5 2020, 8:57 PM
lld/test/ELF/icf18.s
1 ↗(On Diff #296166)

The test name can be improved. Consider merging this test with icf-non-mergeable.s

andrewng updated this revision to Diff 296395.Oct 6 2020, 2:53 AM
andrewng marked 5 inline comments as done.

Address review comments.

lld/ELF/ICF.cpp
227

Yes, the intention is to make the equivalence class IDs distinct from the unique IDs, otherwise it might be possible (although very unlikely) for incorrect equality to occur.

I have come up with an alternative solution that uses a base offset derived from uniqueId.

357–358

I have updated the comment, as I believe the code is still applicable.

476

Same reply: combineRelocHashes() only updates the sections that are in the vector sections. The sections that are assigned a unique ID here will not be added to the sections vector, as they are considered ineligible. Therefore, eqClass[1] should also be set to the same unique ID.

lld/test/ELF/icf18.s
1 ↗(On Diff #296166)

Had a look at icf-non-mergeable.s which checks for no merging, so decided just to rename to icf-ineligible.s. Hope that's OK.

The description can be shortened a bit. The important part is that variableEq returns false if two relocations reference a pair of aliased symbols in an ineligible section.

Actually, the key difference in this patch is that variableEq returns true for two relocations to a pair of "aliased" symbols that reference the same section which is ineligible for ICF. This patch actually came about from the investigation into the ICF link performance issue with objects compiled with -fprofile-instr-generate. It was during this investigation that I noticed some of these shortcomings.

MaskRay added inline comments.Oct 7 2020, 2:40 PM
lld/ELF/ICF.cpp
226

How about making uniqueId in the main function start from inputSections.size(). The variable eqClassBase can be avoided.

There is a gap between used values but that is not a problem: [0, sections.size()) ... [inputSections.size(), inputSections.size()+sections.size())

lld/test/ELF/icf-ineligible.s
2

You can delete icf-non-mergeable.s by adding some lines to this file.

andrewng added inline comments.Oct 8 2020, 1:40 AM
lld/ELF/ICF.cpp
226

I did consider this, but I thought it would be better to not have the gap, particularly as eqClass is "only" 32-bit. Also having unqueId start from a higher value, brings it closer to hash collisions given the current code which sets the MSB to avoid such collisions. It's unlikely that this is going to make a practical difference, but it just feels better. What are your thoughts?

Whilst on this topic, do you think we should add some checks for these "range" constraints (in separate patch)?

lld/test/ELF/icf-ineligible.s
2

I actually thought that keeping the tests separate would be better, as in the icf-non-mergable.s test no sections are merged where as this test is expecting all sections to merge. But if you want me to combine the tests, I can do that. If so, which test name would be your preference?

MaskRay accepted this revision.Oct 13 2020, 8:45 AM

One last nit.

lld/ELF/ICF.cpp
227

Inline the variable eqClass

This revision is now accepted and ready to land.Oct 13 2020, 8:45 AM
andrewng added inline comments.Oct 13 2020, 3:26 PM
lld/ELF/ICF.cpp
227

Just to clarify, you want me to replace eqClass with the expression eqClassBase + mid, i.e. bring the addition inside the for loop?

MaskRay added inline comments.Oct 13 2020, 3:49 PM
lld/ELF/ICF.cpp
227

Yes. This is optimizable by the compiler

andrewng added inline comments.Oct 14 2020, 1:56 AM
lld/ELF/ICF.cpp
227

OK, no problem, although I have to admit this goes against my instinctive coding approach. But I guess that might be because most projects with which I've been involved, have put at least some importance towards the run-time performance of unoptimized debug builds. But if this is the "LLVM" way, then so be it.

grimar added inline comments.Oct 15 2020, 12:30 AM
lld/ELF/ICF.cpp
227

OK, no problem, although I have to admit this goes against my instinctive coding approach.

FWIW I agree with it. I also prefer to precalculate values outside of the loop, it looks and reads cleaner usually.

But if this is the "LLVM" way, then so be it.

I don't think it is, I guess the idea was to get rid of a "excessive variable" to make the code a bit shorter.
I have no strong opinion about this particular place, because it is a very short/simple loop, though personally I would not do it too.

Herald added a project: Restricted Project. · View Herald TranscriptOct 15 2020, 4:48 AM