Page MenuHomePhabricator

[lld-macho] Optimize rebase opcode generation
ClosedPublic

Authored by BertalanD on Jul 20 2022, 8:52 AM.

Details

Reviewers
int3
thakis
Group Reviewers
Restricted Project
Commits
rG54e18b23972a: [lld-macho] Optimize rebase opcode generation
Summary

This commit reduces the size of the emitted rebase sections by
generating the REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB and
REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB opcodes.

With this change, chromium_framework's rebase section is a 40% smaller
197 kilobytes, down from the previous 320 KiB. That is 6 KiB smaller
than what ld64 produces for the same input.

Performance figures from my M1 Mac mini:

x before
+ after

    N           Min           Max        Median           Avg        Stddev
x  10     4.2269349     4.3300061     4.2689675     4.2690016   0.031151669
+  10      4.219331     4.2914009     4.2398136     4.2448277   0.023817308
No difference proven at 95.0% confidence

Diff Detail

Event Timeline

BertalanD created this revision.Jul 20 2022, 8:52 AM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptJul 20 2022, 8:52 AM
BertalanD requested review of this revision.Jul 20 2022, 8:52 AM
BertalanD updated this revision to Diff 446170.Jul 20 2022, 8:54 AM
int3 accepted this revision.Jul 20 2022, 11:02 AM

Nice and elegant :)

lld/MachO/SyntheticSections.cpp
173–179

nit 1: "flush" is typically used in conjunction with a buffer. Which RebaseState kind of is, so flushRebase seems reasonable, but flushIncrement isn't really flushing anything. How about emitIncrement?

nit 2: "addend" is already used in the context of relocations. How about calling the parameter incr instead, since we are already using it for the function name?

225

convention is to specify the namespace for these helpers to make it clear that this isn't the std:: version

232

maybe assert that !locations.empty()

This revision is now accepted and ready to land.Jul 20 2022, 11:02 AM

Could we run a benchmark on this just to see if it has any impact on link speed? I remember bind opcodes optimization had a slight link speed regression which was then put behind an -O2 flag since it isn't worth it for debug builds. I'm wondering if we need to do the same for the rebase opcodes.

It doesn't seem to cause a noticeable slowdown. Here are the numbers from my GCE VM:

x before
+ after
+------------------------------------------------------------------------------------------+
|     +  x        +     ++     x                   x                       x        +     x|
||_________________|____M______A___________________A__________|_____________________|      |
+------------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x   5     12.363932     12.531116     12.450043     12.451094   0.067299645
+   5     12.357563     12.519216     12.394229     12.410027   0.062940345
No difference proven at 95.0% confidence

I will add the measurements from my mac when I update the patch.

int3 added a comment.Jul 20 2022, 12:04 PM

Yeah I would expect it to be roughly the same perf given that we're not doing multiple passes. Nice to have those stats though. Could you include them in the commit message?

BertalanD edited the summary of this revision. (Show Details)

Addressed review comments.

Benchmark data from my Mac mini:

x before
+ after

    N           Min           Max        Median           Avg        Stddev
x  10     4.2269349     4.3300061     4.2689675     4.2690016   0.031151669
+  10      4.219331     4.2914009     4.2398136     4.2448277   0.023817308
No difference proven at 95.0% confidence
BertalanD marked 3 inline comments as done.Jul 20 2022, 12:29 PM
thakis accepted this revision.Jul 20 2022, 5:00 PM
thakis added a subscriber: thakis.

Nice!

lld/MachO/SyntheticSections.cpp
208

We're no longer doing this precaution now. Is that intentional?

BertalanD marked an inline comment as done.Jul 20 2022, 10:41 PM
BertalanD added inline comments.
lld/MachO/SyntheticSections.cpp
208

I checked dyld's source code, and I think it handles that case correctly. If rebases start causing issues (which I highly doubt would happen), I'll know where to look first.

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptJul 21 2022, 1:08 AM