[lld-macho] Sort data-in-code entries
authorDaniel Bertalan <dani@danielbertalan.dev>
Fri, 9 Sep 2022 15:18:10 +0000 (17:18 +0200)
committerDaniel Bertalan <dani@danielbertalan.dev>
Tue, 13 Sep 2022 17:08:35 +0000 (19:08 +0200)
commit025a5b22c848364be0009a630e7fb53f40515e68
tree3ac65297438ef41b8bf93201b21b73fc0b1c670f
parentd8a57c778875eb0a2d093b6f1991e77ff9885a85
[lld-macho] Sort data-in-code entries

Previously, we would add entries to DataInCodeSection in the order they
appeared in input files. Because of this, entries would not be sorted if
sections were reordered due to e.g. `-order_file` or call graph profile
sorting. ld64 always keeps data-in-code information sorted.

This commit also fixes an incorrect assertion. The original assertion
from D103006 used to check that data-in-code entries are sorted in the
input objects -- likely because we use binary search on that data. In
D115556, the assertion was moved into `collectDataInCodeEntries`, but
the checked variable's name was not changed, so it ended up checking the
final contents of the DataInCodeSection.

We no longer crash when building LLVM with PGO using an asserts build of
LLD as the linker.

Fixes https://bugs.chromium.org/p/chromium/issues/detail?id=1265937

Numbers for linking the Chromium Framework reproducer from #48001, which
has 6829 data-in-code entries:

  x before
  + after
      N           Min           Max        Median           Avg        Stddev
  x  20     2.1076453     2.3059683     2.1132485     2.1350302   0.049905767
  +  20     2.1069031     2.3915262       2.14465     2.1728429   0.084065898
  No difference proven at 95.0% confidence

Differential Revision: https://reviews.llvm.org/D133581
lld/MachO/SyntheticSections.cpp
lld/MachO/SyntheticSections.h
lld/test/MachO/data-in-code-section-ordering.s [new file with mode: 0644]