Improved Basic Block Reordering
share
Basic block reordering is an important step for profile-guided binary optimization. The state-of-the-art 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 compiler Clang, and SPEC CPU 2006 benchmarks, indicate that the new method outperforms existing block reordering techniques, improving the resulting performance of large-scale data-center applications. We have open sourced the code of the new algorithm as a part of a post-link binary optimization tool, BOLT.
READ FULL TEXT