Paper Info
Title
An optimization-driven incremental inline substitution algorithm for just-in-time compilers
Abstract
Inlining is one of the most important compiler optimizations. It reduces call overheads and widens the scope of other optimizations. But, inlining is somewhat of a black art of an optimizing compiler, and was characterized as a computationally intractable problem. Intricate heuristics, tuned during countless hours of compiler engineering, are often at the core of an inliner implementation. And despite decades of research, well-established inlining heuristics are still missing. In this paper, we describe a novel inlining algorithm for JIT compilers that incrementally explores a program’s call graph, and alternates between inlining and optimizations. We devise three novel heuristics that guide our inliner: adaptive decision thresholds, callsite clustering, and deep inlining trials. We implement the algorithm inside Graal, a dynamic JIT compiler for the HotSpot JVM. We evaluate our algorithm on a set of industry-standard benchmarks, including Java DaCapo, Scalabench, Spark-Perf, STMBench7 and other benchmarks, and we conclude that it significantly improves performance, surpassing state-of-the-art inlining approaches with speedups ranging from 5% up to 3×.
Year
DOI
Venue
2019
10.1109/CGO.2019.8661171
Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization
Keywords
Field
DocType
cost-benefit analysis, inline expansion, inline subtitution, inlining, just-in-time compilation, optimization-driven inlining, polymorphic dispatch, priority-based inlining
Inline expansion,Computer science,Parallel computing,Algorithm,Compiler,Optimizing compiler,Call graph,Heuristics,Just-in-time compilation,Cluster analysis,Java
Conference
ISSN
ISBN
Citations 
2164-2397
978-1-7281-1436-1
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Aleksandar Prokopec116313.56
Gilles Duboscq221110.10
David Leopoldseder361.83
Thomas Würthinger439625.63