[BOLT] Add function layout class

This patch adds a dedicated class to keep track of each function's
layout. It also lays the groundwork for splitting functions into
multiple fragments (as opposed to

[BOLT] Add function layout class

This patch adds a dedicated class to keep track of each function's
layout. It also lays the groundwork for splitting functions into
multiple fragments (as opposed to a strict hot/cold split).

Reviewed By: maksfb

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

show more ...

[BOLT] Replace uses of layout with basic block list

As we are moving towards support for multiple fragments, loops that
iterate over all basic blocks of a function, but do not depend on the
order of

[BOLT] Replace uses of layout with basic block list

As we are moving towards support for multiple fragments, loops that
iterate over all basic blocks of a function, but do not depend on the
order of basic blocks in the final layout, should iterate over binary
functions directly, rather than the layout.

Eventually, all loops using the layout list should either iterate over
the function, or be aware of multiple layouts. This patch replaces
references to binary function's block layout with the binary function
itself where only little code changes are necessary.

Reviewed By: maksfb

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

show more ...

[BOLT] Support multiple parents for split jump table

There are two assumptions regarding jump table:
(a) It is accessed by only one fragment, say, Parent
(b) All entries target instructions in Paren

[BOLT] Support multiple parents for split jump table

There are two assumptions regarding jump table:
(a) It is accessed by only one fragment, say, Parent
(b) All entries target instructions in Parent

For (a), BOLT stores jump table entries as relative offset to Parent.
For (b), BOLT treats jump table entries target somewhere out of Parent
as INVALID_OFFSET, including fragment of same split function.

In this update, we extend (a) and (b) to include fragment of same split
functinon. For (a), we store jump table entries in absolute offset
instead. In addition, jump table will store all fragments that access
it. A fragment uses this information to only create label for jump table
entries that target to that fragment.

For (b), using absolute offset allows jump table entries to target
fragments of same split function, i.e., extend support for split jump
table. This can be done using relocation (fragment start/size) and
fragment detection heuristics (e.g., using symbol name pattern for
non-stripped binaries).

For jump table targets that can only be reached by one fragment, we
mark them as local label; otherwise, they would be the secondary
function entry to the target fragment.

Test Plan
```
ninja check-bolt
```

Reviewed By: Amir

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

show more ...

[BOLT][AArch64] Handle gold linker veneers

The gold linker veneers are written between functions without symbols,
so we to handle it specially in BOLT.

Vladislav Khmelevsky,
Advanced Software Techn

[BOLT][AArch64] Handle gold linker veneers

The gold linker veneers are written between functions without symbols,
so we to handle it specially in BOLT.

Vladislav Khmelevsky,
Advanced Software Technology Lab, Huawei

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

show more ...

[BOLT] Increase coverage of shrink wrapping [1/5]

Change how function score is calculated and provide more
detailed statistics when reporting back frame optimizer and shrink
wrapping results. In thi

[BOLT] Increase coverage of shrink wrapping [1/5]

Change how function score is calculated and provide more
detailed statistics when reporting back frame optimizer and shrink
wrapping results. In this new statistics, we provide dynamic coverage
numbers. The main metric for shrink wrapping is the number of executed
stores that were saved because of shrink wrapping (push instructions
that were either entirely moved away from the hot block or converted
to a stack adjustment instruction). There is still a number of reduced
load instructions (pop) that we are not counting at the moment. Also
update alloc combiner to report dynamic numbers, as well as frame
optimizer.

For debugging purposes, we also include a list of top 10 functions
optimized by shrink wrapping. These changes are aimed at better
understanding the impact of shrink wrapping in a given binary.

We also remove an assertion in dataflow analysis to do not choke on
empty functions (which makes no sense).

Reviewed By: Amir

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

show more ...

[BOLT] Respect shouldPrint in dump-dot-all

Don't dump dot CFG graph for functions that should not be printed.

Reviewed By: rafauler, maksfb

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

Revert "[BOLT][AArch64] Handle gold linker veneers"

This reverts commit 425dda76e9fac93117289fd68a2abdfb1e4a0ba5.

This commit is currently causing BOLT to crash in one of our
binaries and needs a b

Revert "[BOLT][AArch64] Handle gold linker veneers"

This reverts commit 425dda76e9fac93117289fd68a2abdfb1e4a0ba5.

This commit is currently causing BOLT to crash in one of our
binaries and needs a bit more checking to make sure it is safe
to land.

show more ...

[BOLT][AArch64] Handle gold linker veneers

The gold linker veneers are written between functions without symbols,
so we to handle it specially in BOLT.

Vladislav Khmelevsky,
Advanced Software Techn

[BOLT][AArch64] Handle gold linker veneers

The gold linker veneers are written between functions without symbols,
so we to handle it specially in BOLT.

Vladislav Khmelevsky,
Advanced Software Technology Lab, Huawei

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

show more ...

[BOLT][NFC] Use range-based STL wrappers

Replace `std::` algorithms taking begin/end iterators with `llvm::` counterparts
accepting ranges.

Reviewed By: rafauler

Differential Revision: https://rev

[BOLT][NFC] Use range-based STL wrappers

Replace `std::` algorithms taking begin/end iterators with `llvm::` counterparts
accepting ranges.

Reviewed By: rafauler

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

show more ...

[BOLT] Allow function fragments to point to one jump table

Resolve a crash related to split functions

Due to split function optimization, a function can be divided to two

fragments, and both fragm

[BOLT] Allow function fragments to point to one jump table

Resolve a crash related to split functions

Due to split function optimization, a function can be divided to two

fragments, and both fragments can access same jump table. This
violates 
the assumption that a jump table can only have one parent
function, 
which causes a crash during instrumentation.

We want to support the case: different functions cannot access same
jump tables, but different fragments of same function can!

As all fragments are from same function, we point JT::Parent to one
specific fragment. Right now it is the first disassembled fragment, but
we can point it to the function's main fragment later.

Functions are disassembled sequentially. Previously, at the end of
processing a function, JT::OffsetEntries is cleared, so other fragment
can no longer reuse JT::OffsetEntries. To extend the support for split
function, we only clear JT::OffsetEntries after all functions are
disassembled.

Let say A.hot and A.cold access JT of three targets {X, Y, Z}, where
X and Y are in A.hot, and Z is in A.cold. Suppose that A.hot is
disassembled first, JT::OffsetEntries = {X',Y',INVALID_OFFSET}. When
A.cold is disassembled, it cannot reuse JT::OffsetEntries above due to
different fragment start. A simple solution:
A.hot = {X',Y',INVALID_OFFSET}
A.cold = {INVALID_OFFSET, INVALID_OFFSET, INVALID_OFFSET}

We update the assertion to allow different fragments of same function
to get the same JumpTable object.

Potential improvements:
A.hot = {X',Y',INVALID_OFFSET}
A.cold = {INVALID_OFFSET, INVALID_OFFSET, Z'}
The main issue is A.hot and A.cold have separate CFGs, thus jump table
targets are still constrained within fragment bounds.

Future improvements:
A.hot = {X, Y, Z}
A.cold = {X, Y, Z}

Reviewed By: Amir

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

show more ...

[BOLT][NFCI] Refactor interface for adding basic blocks

Reviewed By: Amir

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

[BOLT][AArch64] Handle data at the beginning of a function when disassembling and building CFG.

This patch adds getFirstInstructionOffset method for BinaryFunction
which is used to properly handle c

[BOLT][AArch64] Handle data at the beginning of a function when disassembling and building CFG.

This patch adds getFirstInstructionOffset method for BinaryFunction
which is used to properly handle cases where data is at zero offset in
a function. The main change is that we add basic block at first
instruction offset when disassembling, which prevents assertion
failures in buildCFG.

Reviewed By: yota9, rafauler

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

show more ...

[bolt] Remove unneeded cl::ZeroOrMore for cl::opt options

[BOLT][NFC] Use colors in CFG dumps

Use color coding to distinguish nodes:
- Entry nodes have bold border
- Scalar (non-loopy) code is milk white
- Outer loops are light yellow
- Innermost loops are

[BOLT][NFC] Use colors in CFG dumps

Use color coding to distinguish nodes:
- Entry nodes have bold border
- Scalar (non-loopy) code is milk white
- Outer loops are light yellow
- Innermost loops are light blue

`-print-loops` needs to be enabled to provide BinaryLoopInfo.
Examples:
{F23170673}
{F23170680}

Reviewed By: rafauler

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

show more ...

[BOLT][NFC] Print block instructions in dumpGraph as part of node label

Reuse the option `-dot-tooltip-code` to put block instructions into the label.
This way, the instructions are displayed by def

[BOLT][NFC] Print block instructions in dumpGraph as part of node label

Reuse the option `-dot-tooltip-code` to put block instructions into the label.
This way, the instructions are displayed by default when used with dot viewer.

When the .dot file is used with dot2html, instructions are hidden by default,
and are shown by clicking on a node.

{F23169510}

Reviewed By: rafauler

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

show more ...

[BOLT][NFC] Remove unused variable

Reviewed By: Amir

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

[BOLT] Add new class for symbolizing X86 instructions

Summary:
While disassembling instructions, we need to replace certain immediate
operands with symbols. This symbolizing process relies on readin

[BOLT] Add new class for symbolizing X86 instructions

Summary:
While disassembling instructions, we need to replace certain immediate
operands with symbols. This symbolizing process relies on reading
relocations against instructions. However, some X86 instructions can
have multiple immediate operands and up to two relocations against
them. Thus, correctly matching a relocation to an operand is not
always possible without knowing the operand offset within the
instruction.

Luckily, LLVM provides an interface for passing the required info from
the disassembler via a virtual MCSymbolizer class. Creating a
target-specific version allows a precise matching of relocations to
operands.

This diff adds X86MCSymbolizer class that performs X86-specific
symbolizing (currently limited to non-branch instructions).

Reviewers: yota9, Amir, ayermolo, rafauler, zr33

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

show more ...

[BOLT] [AArch64] Handle constant islands spanning multiple functions

Fix BOLT's constant island mapping when a constant island marked by $d
spans multiple functions. Currently, because BOLT only mar

[BOLT] [AArch64] Handle constant islands spanning multiple functions

Fix BOLT's constant island mapping when a constant island marked by $d
spans multiple functions. Currently, because BOLT only marks the
constant island in the first function where $d is located, if the next
function contains data at its start, BOLT will miss the data and try
to disassemble it. This patch adds code to explicitly go through all
symbols between $d and $x markers and mark their respective offsets as
data, which stops BOLT from trying to disassemble data. It also adds
MarkerType enum and refactors related functions.

Reviewed By: yota9, rafauler

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

show more ...

[BOLT][NFC] Use ListSeparator in BinaryFunction print methods

Reviewed By: rafauler

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

[BOLT][NFC] Use for_each to simplify printLoopInfo

Reviewed By: rafauler

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

[BOLT][NFC] Move BinaryDominatorTree out of BinaryLoop header

Split up the BinaryLoop header and move BinaryDominatorTree into its own header,
preparing it for a standalone use.

Reviewed By: rafaul

[BOLT][NFC] Move BinaryDominatorTree out of BinaryLoop header

Split up the BinaryLoop header and move BinaryDominatorTree into its own header,
preparing it for a standalone use.

Reviewed By: rafauler

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

show more ...

[BOLT][NFC] Use refs for loop variables to avoid copies

Addresses warnings when built with Apple Clang.

Reviewed By: yota9

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

[BOLT][NFC] Suppress unused variable warnings

Address warnings in Release build without assertions.
Tip @tschuett for reporting the issue #55404.

Reviewed By: rafauler

Differential Revision: https

[BOLT][NFC] Suppress unused variable warnings

Address warnings in Release build without assertions.
Tip @tschuett for reporting the issue #55404.

Reviewed By: rafauler

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

show more ...

[BOLT][NFC] Add MCPlus::primeOperands iterator_range

Reviewed By: yota9

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

[BOLT] Support PC-relative relocations with addends

PC-relative memory operand could reference a different object from
the one located at the target address, e.g. when a negative offset
is used. Che

[BOLT] Support PC-relative relocations with addends

PC-relative memory operand could reference a different object from
the one located at the target address, e.g. when a negative offset
is used. Check relocations for the real referenced object.

Reviewed By: rafauler

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

show more ...