  Basic block reordering is an important step for profile-guided binary
optimization. The state-of-the-art goal for basic block reordering is to
maximize the number of fall-through branches. However, we demonstrate that such
orderings may impose suboptimal performance on instruction and I-TLB caches. We
propose a new algorithm that relies on a model combining the effects of
fall-through and caching behavior. As details of modern processor caching is
quite complex and often unknown, we show how to use machine learning in
selecting parameters that best trade off different caching effects to maximize
binary performance.
  An extensive evaluation on a variety of applications, including Facebook
production workloads, the open-source compilers Clang and GCC, and SPEC CPU
benchmarks, indicate that the new method outperforms existing block reordering
techniques, improving the resulting performance of applications with large code
size. We have open sourced the code of the new algorithm as a part of a
post-link binary optimization tool, BOLT.
