[BOLT] Fix incorrect basic block output addresses (#70000)

Some optimization passes may duplicate basic blocks and assign the same
input offset to a number of different blocks in a function. This i

[BOLT] Fix incorrect basic block output addresses (#70000)

Some optimization passes may duplicate basic blocks and assign the same
input offset to a number of different blocks in a function. This is done
e.g. to correctly map debugging ranges for duplicated code.

However, duplicate input offsets present a problem when we use
AddressMap to generate new addresses for basic blocks. The output
address is calculated based on the input offset and will be the same for
blocks with identical offsets. The result is potentially incorrect debug
info and BAT records.

To address the issue, we have to eliminate the dependency on input
offsets while generating output addresses for a basic block. Each block
has a unique label, hence we extend AddressMap to include address lookup
based on MCSymbol and use the new functionality to update block
addresses.

show more ...

[BOLT] Give precedence to first AddressMap entries

When parsing AddressMap and there is a conflict in keys,
where two entries share the same key, consider the first entry as the
correct one, instead

[BOLT] Give precedence to first AddressMap entries

When parsing AddressMap and there is a conflict in keys,
where two entries share the same key, consider the first entry as the
correct one, instead of the last. This matches previous behavior in
BOLT and covers case such as BOLT creating a new basic block but
sharing the same input offset of the previous (or entry) basic
block. In this case, instead of translating debuginfo to use the newly
created BB, translate using the BB that was originally read from
input. This will increase our chances of getting debuginfo right.

Tested via binary comparison in tests:
X86/dwarf4-df-input-lowpc-ranges.test
X86/dwarf5-df-input-lowpc-ranges.test

Reviewed By: #bolt, maksfb, jobnoorman

Differential Revision: https://reviews.llvm.org/D158686

show more ...

[BOLT] Calculate input to output address map using BOLTLinker

BOLT uses MCAsmLayout to calculate the output values of basic blocks.
This means output values are calculated based on a pre-linking sta

[BOLT] Calculate input to output address map using BOLTLinker

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.

Reviewed By: maksfb

Differential Revision: https://reviews.llvm.org/D155604

show more ...