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

Journal of Big Data - July 19, 2021

Cumulative deviation of a subpopulation from the full population

Mark Tygert

Management Science (journal) - September 30, 2021

Pacing Equilibrium in First Price Auction Markets

Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E. Stier-Moses, Eric Sodomka, Christopher A. Wilkens

ArXiv/SSRN - July 1, 2021

Social Connectedness in Urban Areas

Michael Bailey, Patrick Farrell, Theresa Kuchler, Johannes Stroebel

ArXiv/SSRN - December 28, 2020

Social Distancing During a Pandemic: The Role of Friends

Michael Bailey, Drew Johnston, Martin Koenen, Theresa Kuchler, Dominic Russel, Johannes Stroebel

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