LLD Support for Basic Block Sections
authorSriraman Tallam <tmsriram@google.com>
Tue, 7 Apr 2020 13:48:18 +0000 (06:48 -0700)
committerSriraman Tallam <tmsriram@google.com>
Tue, 7 Apr 2020 13:55:57 +0000 (06:55 -0700)
commit94317878d8267de23a1a23dfa3d92f9143c433ca
treed7d2e656bf65f31262446b8917785857783819b5
parentc97be2c377852fad7eb38409aae5692fa417e49b
LLD Support for Basic Block Sections

This is part of the Propeller framework to do post link code layout
optimizations. Please see the RFC here:
https://groups.google.com/forum/#!msg/llvm-dev/ef3mKzAdJ7U/1shV64BYBAAJ and the
detailed RFC doc here:
https://github.com/google/llvm-propeller/blob/plo-dev/Propeller_RFC.pdf

This patch adds lld support for basic block sections and performs relaxations
after the basic blocks have been reordered.

After the linker has reordered the basic block sections according to the
desired sequence, it runs a relaxation pass to optimize jump instructions.
Currently, the compiler emits the long form of all jump instructions. AMD64 ISA
supports variants of jump instructions with one byte offset or a four byte
offset. The compiler generates jump instructions with R_X86_64 32-bit PC
relative relocations. We would like to use a new relocation type for these jump
instructions as it makes it easy and accurate while relaxing these instructions.

The relaxation pass does two things:

First, it deletes all explicit fall-through direct jump instructions between
adjacent basic blocks. This is done by discarding the tail of the basic block
section.

Second, If there are consecutive jump instructions, it checks if the first
conditional jump can be inverted to convert the second into a fall through and
delete the second.

The jump instructions are relaxed by using jump instruction mods, something
like relocations. These are used to modify the opcode of the jump instruction.
Jump instruction mods contain three values, instruction offset, jump type and
size. While writing this jump instruction out to the final binary, the linker
uses the jump instruction mod to determine the opcode and the size of the
modified jump instruction. These mods are required because the input object
files are memory-mapped without write permissions and directly modifying the
object files requires copying these sections. Copying a large number of basic
block sections significantly bloats memory.

Differential Revision: https://reviews.llvm.org/D68065
14 files changed:
lld/ELF/Arch/X86_64.cpp
lld/ELF/Config.h
lld/ELF/Driver.cpp
lld/ELF/InputSection.cpp
lld/ELF/InputSection.h
lld/ELF/LTO.cpp
lld/ELF/Options.td
lld/ELF/OutputSections.cpp
lld/ELF/Relocations.h
lld/ELF/Target.h
lld/ELF/Writer.cpp
lld/test/ELF/bb-sections-and-icf.s [new file with mode: 0644]
lld/test/ELF/bb-sections-delete-fallthru.s [new file with mode: 0644]
lld/test/ELF/bb-sections-pc32reloc.s [new file with mode: 0644]