2016/11/06 by Rudy Bunel, Alban Desmaison, Bunel, Rudy +8 · 1 voice · 17 citations
Computer Science · #Artificial intelligence #Code (set theory) #Compiler #Computer science #Correctness #Leverage (statistics) #Machine learning #Paraphrase #Program optimization #Programming language #Semantics (computer science) #Set (abstract data type) #Software Engineering Research #Software Reliability and Analysis Research #Software Testing and Debugging Techniques #Source code #Syntax #Theoretical computer science #Utterance #cs.LG
paper · pdf · doi:10.48550/arxiv.1611.01787
published in arXiv (Cornell University) (Cornell University) · Accepted to ICLR 2017
openalex publication_date 2016/11/06 · arxiv created 2017/06/28 · arxiv updated 2017/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Code super-optimization is the task of transforming any given program to a more efficient version while preserving its input-output behaviour. In some sense, it is similar to the paraphrase problem from natural language processing where the intention is to change the syntax of an utterance without changing its semantics. Code-optimization has been the subject of years of research that has resulted in the development of rule-based transformation strategies that are used by compilers. More recently, however, a class of stochastic search based methods have been shown to outperform these strategies. This approach involves repeated sampling of modifications to the program from a proposal distribution, which are accepted or rejected based on whether they preserve correctness, and the improvement they achieve. These methods, however, neither learn from past behaviour nor do they try to leverage the semantics of the program under consideration. Motivated by this observation, we present a novel learning based approach for code super-optimization. Intuitively, our method works by learning the proposal distribution using unbiased estimators of the gradient of the expected improvement. Experiments on benchmarks comprising of automatically generated as well as existing ("Hacker's Delight") programs show that the proposed method is able to significantly outperform state of the art approaches for code super-optimization.