[BOLT] stale profile matching [part 1 out of 2]
authorspupyrev <spupyrev@fb.com>
Thu, 16 Feb 2023 18:52:04 +0000 (10:52 -0800)
committerspupyrev <spupyrev@fb.com>
Tue, 6 Jun 2023 19:13:52 +0000 (12:13 -0700)
commit44268271f61e46636619623d52013c3be3e272c0
tree55f1c7b56c3a2eb973cfe443d950320ccd738842
parent3cb6ead77c6668fcd1362763b2603752c6c595fa
[BOLT] stale profile matching [part 1 out of 2]

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
bolt/include/bolt/Core/BinaryFunction.h
bolt/include/bolt/Profile/YAMLProfileReader.h
bolt/lib/Passes/BinaryPasses.cpp
bolt/lib/Profile/CMakeLists.txt
bolt/lib/Profile/StaleProfileMatching.cpp [new file with mode: 0644]
bolt/lib/Profile/YAMLProfileReader.cpp
bolt/test/X86/Inputs/blarge_profile_stale.yaml [new file with mode: 0644]
bolt/test/X86/reader-stale-yaml.test [new file with mode: 0644]