Publication

Improved Basic Block Reordering

IEEE Transactions on Computers


Abstract

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 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.

Related Publications

All Publications

NeurIPS - December 16, 2020

Online Bayesian Persuasion

Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Nicola Gatti

WINE - December 7, 2020

The Ad Types Problem

Riccardo Colini Baldeschi, Julian Mestre, Okke Schrijvers, Christopher A. Wilkens

NBER - September 30, 2020

The Effects of COVID-19 on U.S. Small Businesses: Evidence from Owners, Managers, and Employees

Georgij Alekseev, Safaa Amer, Manasa Gopal, Theresa Kuchler, JW Schneider, Johannes Stroebel, Nils Wernerfelt

The Web Conference - April 30, 2020

Envy, Regret, and Social Welfare Loss

Riccardo Colini Baldeschi, Stefano Leonardi, Okke Schrijvers, Eric Sodomka

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy