This is an archive of the discontinued LLVM Phabricator instance.

[BOLT] Calculate input to output address map using BOLTLinker
ClosedPublic

Authored by jobnoorman on Jul 18 2023, 8:25 AM.

Details

Summary

BOLT uses MCAsmLayout to calculate the output values of basic blocks.
This means output values are calculated based on a pre-linking state and
any changes to symbol values during linking will cause incorrect values
to be used.

This issue was first addressed in D154604 by adding all basic block
symbols to the symbol table for the linker to resolve them. However, the
runtime overhead of handling this huge symbol table turned out to be
prohibitively large.

This patch solves the issue in a different way. First, a temporary
section containing [input address, output symbol] pairs is emitted to the
intermediary object file. The linker will resolve all these references
so we end up with a section of [input address, output address] pairs.
This section is then parsed and used to:

  • Replace BinaryBasicBlock::OffsetTranslationTable
  • Replace BinaryFunction::InputOffsetToAddressMap
  • Update BinaryBasicBlock::OutputAddressRange

Note that the reason this is more performant than the previous attempt
is that these symbol references do not cause entries to be added to the
symbol table. Instead, section-relative references are used for the
relocations.

Diff Detail

Event Timeline

jobnoorman created this revision.Jul 18 2023, 8:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 18 2023, 8:25 AM
jobnoorman requested review of this revision.Jul 18 2023, 8:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 18 2023, 8:25 AM

Apologies for the delay. Thanks for adding the map. I think we can eventually get rid of LocSyms, but we can do it in follow-up diffs.

bolt/include/bolt/Core/AddressMap.h
1

Needs a standard license header.

bolt/include/bolt/Profile/BoltAddressTranslation.h
119

Unneeded. Should be able to get BC via BB->BF->BC.

bolt/include/bolt/Rewrite/RewriteInstance.h
384

Maybe add a flag to BinarySection, instead? WDYT?

bolt/lib/Core/AddressMap.cpp
45

You can also use DataExtractor class for parsing and derive endianness from BC.AsmInfo->isLittleEndian().

bolt/lib/Rewrite/RewriteInstance.cpp
3194

Can we make this call from inside emitBinaryContext()?

4032

Do we need this check and the one below despite calling deregisterSection()?

Address comments from @maksfb. Major changes:

  • Use DataExtractor to parse address map
  • Add IsLinkOnly flag to BinarySection
jobnoorman marked 4 inline comments as done.Jul 27 2023, 2:32 AM
jobnoorman added inline comments.
bolt/lib/Core/AddressMap.cpp
45

TIL about DataExtractor. Thanks!

bolt/lib/Rewrite/RewriteInstance.cpp
3194

Yes, the reason I didn't do this is because it currently doesn't work for Mach-O (because BinaryContext::getDataSection doesn't support it). I moved the call but guarded it by isELF().

4032

We don't :)

jobnoorman marked 3 inline comments as done.Jul 27 2023, 2:35 AM
maksfb accepted this revision.Jul 30 2023, 1:27 PM

LGTM

This revision is now accepted and ready to land.Jul 30 2023, 1:27 PM