Two (minor) improvements for stale matching:
- always match entry blocks to each other, even if there is a hash mismatch;
- ignore nops in (loose) hash computation.
I record a small improvement in inference quality on my benchmarks. Tests are not affected
Reviewed By: Amir
Differential Revision: https://reviews.llvm.org/D159488
Fine-tuning hash computation for stale matching:
- introducing a new "loose" basic block hash that allows to match many more blocks than before;
- tweaking params of the inference algorithm that find (slightly) better solutions;
- added more meaningful tests for stale matching.
Tested the changes on several open-source benchmarks (clang, rocksdb, chrome)
and one prod workload using different compiler modes (LTO/PGO etc). There is
always an improvement in the quality of inferred profiles.
(The current implementation is still not optimal but the diff is a step forward;
I am open to further suggestions)
Reviewed By: Amir
Differential Revision: https://reviews.llvm.org/D156278
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
Use short loop instead of duplicating the code for setHasProfileAvailable.
Reviewed By: #bolt, maksfb
Differential Revision: https://reviews.llvm.org/D154749
Work around the issue of multiple profiles per function.
Can happen with a stale profile which has separate profiles
that in a new binary got merged and became aliases.
Reviewed By: #bolt, maksfb
Differential Revision: https://reviews.llvm.org/D156644
1. Using ADT/Bitfields.h for hash computation; this is equivalent but shorter than the existing implementation
2. Getting rid of Layout indices for stale matching; using BB->getIndex for indexing
Reviewed By: Amir
Differential Revision: https://reviews.llvm.org/D155748
Adding some logs related to stale profile matching. The new data can be helpful
to understand how "stale" the input profile is and how well the inference is
able to utilize the stale data.
Example of outputs on clang-10 built with LTO (profile collected on a year-old release):
```
BOLT-INFO: inferred profile for 2101 (18.52% of profiled, 100.00% of stale) functions responsible for 30.95% samples (14754697 out of 47670654)
BOLT-INFO: stale inference matched 89.42% of basic blocks (79052 out of 88402 stale) responsible for 76.99% samples (645737 out of 838719 stale)
```
LTO+AutoFDO:
```
BOLT-INFO: inferred profile for 6146 (57.57% of profiled, 100.00% of stale) functions responsible for 90.34% samples (50891403 out of 56330313)
BOLT-INFO: stale inference matched 74.55% of basic blocks (191295 out of 256589 stale) responsible for 57.30% samples (1288632 out of 2248799 stale)
```
Reviewed By: Amir, maksfb
Differential Revision: https://reviews.llvm.org/D154737
Specify blocks order used in YAML profile. Needed to ensure profile backwards
compatibility with pre-D155514 DFS order by default.
Reviewed By: #bolt, maksfb
Differential Revision: https://reviews.llvm.org/D156176
Use layout order in YAML profile reading/writing. Preserve old behavior (DFS order)
under `-profile-use-dfs` option.
Reviewed By: spupyrev
Differential Revision: https://reviews.llvm.org/D155514
Align YAML and fdata profiles by sorting CallSiteInfo targets by symbol name,
aligning it to fdata. By default, YAML CallSiteInfo is sorted by function id,
which is the order of function in the binary.
Follow-up to D152731, aligning yaml vs fdata, and in turn all three between to
each other.
Reviewed By: #bolt, rafauler
Differential Revision: https://reviews.llvm.org/D152733
Align perf reader to fdata behavior by sorting BranchData after reading samples,
in the same way as DataReader:
20c66a0c66/bolt/lib/Profile/DataReader.cpp (L1239)
Namely, that order affects CallSiteInfo annotations which determine the
construction order of CallGraph, which in turn affects function reordering.
Reviewed By: #bolt, rafauler
Differential Revision: https://reviews.llvm.org/D152731
This is a first "serious" version of stale profile matching in BOLT. This diff
extends the hash computation for basic blocks so that we can apply a fuzzy
hash-based matching. The idea is to compute several "versions" of a hash value
for a basic block. A loose version of a hash (computed by ignoring instruction
operands) allows to match blocks in functions whose content has been changed,
while stricter hash values (considering instruction opcodes with operands and
even based on hashes of block's successors/predecessors) allow to resolve
collisions. In order to save space and build time, individual hash components
are blended into a single uint64_t.
There are likely numerous ways of improving hash computation but already this
simple variant provides significant perf benefits.
**Perf testing** on the clang binary: collecting data on clang-10 and using it
to optimize clang-11 (with ~1 year of commits in between). Next, we compare
- //stale_clang// (clang-11 optimized with profile collected on clang-10 with **infer-stale-profile=0**)
- //opt_clang// (clang-11 optimized with profile collected on clang-11)
- //infer_clang// (clang-11 optimized with profile collected on clang-10 with **infer-stale-profile=1**)
`LTO-only` mode:
//stale_clang// vs //opt_clang//: task-clock [delta(%): 9.4252 ± 1.6582, p-value: 0.000002]
(That is, there is a ~9.5% perf regression)
//infer_clang// vs //opt_clang//: task-clock [delta(%): 2.1834 ± 1.8158, p-value: 0.040702]
(That is, the regression is reduced to ~2%)
Related BOLT logs:
```
BOLT-INFO: identified 2114 (18.61%) stale functions responsible for 30.96% samples
BOLT-INFO: inferred profile for 2101 (18.52% of all profiled) functions responsible for 30.95% samples
```
`LTO+AutoFDO` mode:
//stale_clang// vs //opt_clang//: task-clock [delta(%): 19.1293 ± 1.4131, p-value: 0.000002]
//infer_clang// vs //opt_clang//: task-clock [delta(%): 7.4364 ± 1.3343, p-value: 0.000002]
Related BOLT logs:
```
BOLT-INFO: identified 5452 (50.27%) stale functions responsible for 85.34% samples
BOLT-INFO: inferred profile for 5442 (50.23% of all profiled) functions responsible for 85.33% samples
```
Reviewed By: Amir
Differential Revision: https://reviews.llvm.org/D146661
Align yaml and fdata profiles by applying the same treatment to recursive
calls (direct, indirect, tail). fdata profile increments entry count when
handling recursive calls. Make perf/pre-aggregated perf reader (DataAggregator)
do the same.
Test Plan:
In pre-aggregated-perf.test, add a dummy pre-aggregated branch entry between
an indirect call in `frame_dummy` function and its entry point.
Check that YAML profile gets incremented entry count for this function.
End-to-end test: https://github.com/rafaelauler/bolt-tests/pull/24
Reviewed By: #bolt, maksfb
Differential Revision: https://reviews.llvm.org/D152338
Fix debug printing, making it easier to compare two debug logs side by side:
- `BinaryFunction::addRelocation`: print function name instead of `this` ptr,
- `DataAggregator::doTrace`: remove duplicated function name.
Reviewed By: #bolt, maksfb
Differential Revision: https://reviews.llvm.org/D152314
BOLT often has to deal with profiles collected on binaries built from several
revisions behind release. As a result, a certain percentage of functions is
considered stale and not optimized. This diff adds an ability to match profile
to functions that are not 100% binary identical, which increases the
optimization coverage and boosts the performance of applications.
The algorithm consists of two phases: matching and inference:
- At the matching phase, we try to "guess" as many block and jump counts from
the stale profile as possible. To this end, the content of each basic block
is hashed and stored in the (yaml) profile. When BOLT optimizes a binary,
it computes block hashes and identifies the corresponding entries in the
stale profile. It yields a partial profile for every CFG in the binary.
- At the inference phase, we employ a network flow-based algorithm (profi) to
reconstruct "realistic" block and jump counts from the partial profile
generated at the first stage. In practice, we don't always produce proper
profile data but the majority (e.g., >90%) of CFGs get the correct counts.
This is a first part of the change; the next stacked diff extends the block hashing
and provides perf evaluation numbers.
Reviewed By: maksfb
Differential Revision: https://reviews.llvm.org/D144500
`DataAggregator::recordTrace` serves two purposes:
- Attaching LBR fallthrough ("trace") information to CFG (`getBranchInfo`),
which eventually gets emitted as YAML profile.
- Populating vector of offsets that gets added to `FuncBranchData`, which
eventually gets emitted as fdata profile.
`recordTrace` is invoked from `getFallthroughsInTrace` which checks its return
status and passes on the collected vector of offsets to `doTrace`.
However, if a malformed trace is passed to `recordTrace` it might partially
attach the profile to CFG and exit with false, not propagating the vector of
offsets to `doTrace`. This leads to a difference between fdata and yaml profile
collected from the same binary and the same perf file.
(Skylake LBR errata might produce such malformed traces where the last entry
is duplicated, resulting in invalid fallthrough path between the last two
entries).
There are two ways to handle this mismatch: conservative (aligned with fdata),
or aggressive (aligned with yaml). Conservative approach would discard the
trace entirely, buffering the CFG updates until all fallthroughs are confirmed.
Aggressive approach would apply CFG updates and return the matching
fallthroughs in the vector even if the trace is invalid (doesn't correspond to
a valid fallthrough path). I chose to go with the former (conservative/fdata)
approach which produces more accurate profile.
We can't rely on pre-filtering such traces early (in LBR sample processing) as
DataAggregator is used for both perf samples and pre-aggregated perf information
which loses branch stack information.
Test Plan: https://github.com/rafaelauler/bolt-tests/pull/22
Reviewed By: #bolt, rafauler
Differential Revision: https://reviews.llvm.org/D151614
Extending yaml profile format with block hashes, which are used for stale
profile matching. To avoid duplication of the code, created a new class with a
collection of utilities for computing hashes.
Reviewed By: Amir
Differential Revision: https://reviews.llvm.org/D144306
`Function.RawBranchCount` is initialized for fdata profile but not for yaml one.
The diff adds the computation of the field for yaml profiles
Reviewed By: Amir
Differential Revision: https://reviews.llvm.org/D144211
Move out prepareToParse lambda, generalize it to handle mem events perf process.
Reviewed By: #bolt, rafauler
Differential Revision: https://reviews.llvm.org/D146002
Remove the usage of StringMap in places where the iteration order
affects the output since the iteration over StringMap is
non-deterministic.
Reviewed By: Amir
Differential Revision: https://reviews.llvm.org/D145194
Reuse getLTOCommonName in components other than Profile (to be used in Core)
Reviewed By: #bolt, maksfb
Differential Revision: https://reviews.llvm.org/D142259
In profile matching, if `.__uniq` suffix added for internal linkage
symbols with `-funique-internal-linkage-names` prevents BOLT from
matching to a binary function, try to strip the suffix and perform
fuzzy name matching.
Follow-up to D124117.
Reviewed By: #bolt, maksfb
Differential Revision: https://reviews.llvm.org/D142073
Similar to how `makeArrayRef` is deprecated in favor of deduction guides, do the
same for `makeMutableArrayRef`.
Once all of the places in-tree are using the deduction guides for
`MutableArrayRef`, we can mark `makeMutableArrayRef` as deprecated.
Differential Revision: https://reviews.llvm.org/D141814
Use llvm::reverse instead of `for (auto I = rbegin(), E = rend(); I != E; ++I)`
Reviewed By: #bolt, rafauler
Differential Revision: https://reviews.llvm.org/D140516
No-LBR mode wasn't tested and slipped when mayHaveProfileData was added for
Lite mode. This enables processing of profiles collected without LBR and
converted with `perf2bolt -nl` option.
Test Plan:
bin/llvm-lit -a tools/bolt/test/X86/nolbr.s
https://github.com/rafaelauler/bolt-tests/pull/20
Reviewed By: #bolt, rafauler
Differential Revision: https://reviews.llvm.org/D140256
When the user does not have permissions to access the profile, consume
the error contained in Expected<> to avoid dumping stack to the user.
Differential Revision: https://reviews.llvm.org/D139480
This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.
This is part of an effort to migrate from llvm::Optional to
std::optional:
https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
This patch fixes:
bolt/lib/Profile/DataAggregator.cpp:264:66: error: no viable
conversion from 'Optional<llvm::StringRef>[3]' to
'ArrayRef<std::optional<StringRef>>'
This patch replaces those occurrences of NoneType that would trigger
an error if the definition of NoneType were missing in None.h.
To keep this patch focused, I am deliberately not replacing None with
std::nullopt in this patch or updating comments. They will be
addressed in subsequent patches.
This is part of an effort to migrate from llvm::Optional to
std::optional:
https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
Differential Revision: https://reviews.llvm.org/D138539
This patch replaces NoneType() and NoneType::None with None in
preparation for migration from llvm::Optional to std::optional.
In the std::optional world, we are not guranteed to be able to
default-construct std::nullopt_t or peek what's inside it, so neither
NoneType() nor NoneType::None has a corresponding expression in the
std::optional world.
Once we consistently use None, we should even be able to replace the
contents of llvm/include/llvm/ADT/None.h with something like:
using NoneType = std::nullopt_t;
inline constexpr std::nullopt_t None = std::nullopt;
to ease the migration from llvm::Optional to std::optional.
Differential Revision: https://reviews.llvm.org/D138376
In weird entries we were issueing a parse error. For example, in line 5 here:
6862acc063b0aa86595f52ff81628577df4296ff a.so
6862acc063b0aa86595f52ff81628577df4296ff a.so
6862acc063b0aa86595f52ff81628577df4296ff a.so
db758cb3c970044e78d5a4c99b011708a9995636 bin1
60326683eab31acfd03435d9ed4ff9a8 bin2
7d448e51851b4bdb33eac84f90e74628a14a5f00 b.so
742aa26e0211794356cc25f415c25230a26aa045 c.so
Error reading BOLT data input file: line 89, column 33: malformed field
Fix that.
Reviewed By: #bolt, Amir
Differential Revision: https://reviews.llvm.org/D134822
This does *not* link with libLLVM, but with static archives instead. Not
super-great, but at least the build works, which is probably better than
failing.
Related to #57551
Differential Revision: https://reviews.llvm.org/D134434
In perf2bolt and `-aggregate-only` BOLT mode, the output profile file is written
in fdata format by default. Provide a knob `-profile-format=[fdata,yaml]` to
control the format.
Note that `-w` option still dumps in YAML format.
Reviewed By: #bolt, maksfb
Differential Revision: https://reviews.llvm.org/D133995
