This is an archive of the discontinued LLVM Phabricator instance.

[lld-macho][nfc] Sort OutputSections based on explicit order of command-line inputs
ClosedPublic

Authored by int3 on May 22 2021, 5:52 PM.

Details

Summary

This diff paves the way for D102964: [lld-macho] Implement cstring deduplication which adds a new kind of
InputSection.

We previously maintained section ordering implicitly: we created
InputSections as we parsed each file in command-line order, and passed
on this ordering when we created OutputSections and OutputSegments by
iterating over these InputSections. The implicitness of the ordering
made it difficult to refactor the code to e.g. handle a new type of
InputSection. As such, I've codified the ordering explicitly via
inputOrder fields. This also allows us to use sort instead of
stable_sort.

Benchmarking chromium_framework on my 3.2 GHz 16-Core Intel Xeon W:

    N           Min           Max        Median           Avg        Stddev
x  20          4.23          4.35          4.27         4.274   0.030157481
+  20          4.24          4.38          4.27        4.2815   0.033759989
No difference proven at 95.0% confidence

Diff Detail

Event Timeline

int3 created this revision.May 22 2021, 5:52 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a subscriber: mgrang. · View Herald Transcript
int3 requested review of this revision.May 22 2021, 5:52 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 22 2021, 5:52 PM
alexander-shaposhnikov added inline comments.
lld/MachO/OutputSegment.h
56

this looks a bit strange that inputOrder is size_t but the function below (sectionOrder) returns int

int3 marked an inline comment as done.May 22 2021, 6:31 PM
int3 added inline comments.
lld/MachO/OutputSegment.h
56

well the values here are generated from an index into a vector, but I see your point

int3 updated this revision to Diff 347222.May 22 2021, 6:32 PM
int3 marked an inline comment as done.

use int

lld/MachO/OutputSegment.h
47

the presence of comparator and inputOrder, perhaps, deserves some comments
(e.g. are there any places where sections are sorted using different comparators ?)
otherwise this probably can be simplified a bit.

int3 added inline comments.May 22 2021, 8:06 PM
lld/MachO/OutputSegment.h
47

There's only one comparator... I think this only exists so that all the segment+section sorting code could live together in Writer.cpp. But yeah we can simplify it by moving all the sorting code into OutputSegment.cpp instead. Out of scope for this diff though

int3 marked an inline comment as done.May 22 2021, 8:09 PM
int3 added inline comments.
This revision is now accepted and ready to land.May 24 2021, 6:40 PM
thakis added a subscriber: thakis.Jun 19 2021, 7:33 AM
thakis added inline comments.
lld/MachO/OutputSection.h
64

This is a dangerous default that is almost always wrong in practice since it makes every section compete with BSS sections (which _must_ be last). See https://bugs.llvm.org/show_bug.cgi?id=50769#c5