Finding missed optimizations through the lens of dead code elimination
Open Access
- 22 February 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 697-709
Abstract
Compilers are foundational software development tools and incorporate increasingly sophisticated optimizations. Due to their complexity, it is difficult to systematically identify opportunities for improving them. Indeed, the automatic discovery of missed optimizations has been an important and significant challenge. The few existing approaches either cannot accurately pinpoint missed optimizations or target only specific analyses. This paper tackles this challenge by introducing a novel, effective approach that --- in a simple and general manner --- automatically identifies a wide range of missed optimizations. Our core insight is to leverage dead code elimination (DCE) to both analyze how well compilers optimize code and identify missed optimizations: (1) insert "optimization markers" in the basic blocks of a given program, (2) compute the program's live/dead basic blocks using the "optimization markers", and (3) identify missed optimizations from how well compilers eliminate dead blocks. We essentially exploit that, since DCE heavily depends on the rest of the optimization pipeline, through the lens of DCE, one can systematically quantify how well compilers optimize code. We conduct an extensive analysis of GCC and LLVM using our approach, which (1) provides quantitative and qualitative insights regarding their optimization capabilities, and (2) uncovers a diverse set of missed optimizations. Our results also lead to 84 bug reports for GCC and LLVM, of which 62 have already been confirmed or fixed, demonstrating our work's strong practical utility. We expect that the simplicity and generality of our approach will make it widely applicable for understanding compiler performance and finding missed optimizations. This work opens and initiates this promising direction.Keywords
This publication has 32 references indexed in Scilit:
- Detecting Arithmetic Optimization Opportunities for C Compilers by Randomly Generated Equivalent ProgramsIPSJ Transactions on System and LSI Design Methodology, 2016
- Finding deep compiler bugs via guided stochastic program mutation2015
- Throttling Automatic Vectorization: When Less is More2015
- Compiler validation via equivalence modulo inputs2014
- Undefined behavior2012
- Understanding and detecting real-world performance bugs2012
- On the decidability of phase ordering problem in optimizing compilation2006
- Isolating cause-effect chains from computer programs2002
- Compiler transformations for high-performance computingACM Computing Surveys, 1994
- The program summary graph and flow-sensitive interprocedual data flow analysis1988