[InstrProf] Use BalancedPartitioning to order temporal profiling trace data
authorEllis Hoag <ellis.sparky.hoag@gmail.com>
Tue, 6 Jun 2023 18:43:36 +0000 (11:43 -0700)
committerEllis Hoag <ellis.sparky.hoag@gmail.com>
Tue, 6 Jun 2023 18:59:57 +0000 (11:59 -0700)
commit1117b9a284aa6e4b1f3cbde31825605bd07a2384
treedf4b13b865ddc7e781f5c02d8bd0e02cde3e8e0a
parent58b2d652af49ee9d9ff2af6edd7f67f23b26bfee
[InstrProf] Use BalancedPartitioning to order temporal profiling trace data

In [0] we described an algorithm called //BalancedPartitioning// (bp) to consume function traces [1] and compute a function order that reduces the number of page faults during startup.

This patch adds the `order` command to the `llvm-profdata` tool which uses bp to output a function order that can be passed to the linker via `--symbol-ordering-file=`.

Special thanks to Sergey Pupyrev and Julian Mestre for designing this balanced partitioning algorithm.

[0] https://discourse.llvm.org/t/rfc-temporal-profiling-extension-for-irpgo/68068
[1] https://reviews.llvm.org/D147287

Reviewed By: spupyrev

Differential Revision: https://reviews.llvm.org/D147812
llvm/docs/CommandGuide/llvm-profdata.rst
llvm/include/llvm/ProfileData/InstrProf.h
llvm/include/llvm/Support/BalancedPartitioning.h [new file with mode: 0644]
llvm/lib/ProfileData/InstrProf.cpp
llvm/lib/Support/BalancedPartitioning.cpp [new file with mode: 0644]
llvm/lib/Support/CMakeLists.txt
llvm/test/tools/llvm-profdata/show-order.proftext [new file with mode: 0644]
llvm/tools/llvm-profdata/llvm-profdata.cpp
llvm/unittests/Support/BalancedPartitioningTest.cpp [new file with mode: 0644]
llvm/unittests/Support/CMakeLists.txt