2019 · 22 citations · 48 references
ComputingComputer EngineeringComputer ScienceAlgorithmsCompilersComputer ArchitectureAbstract Syntax TreesCompiler ConstructionControl-flow AnalysisData-flow AnalysisJust-in-time CompilationAdaptive ThresholdsCall Graph ConstructionCompiler DesignDecision ThresholdsHeuristicsInliningOptimization HeuristicsReference Benchmarks
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×.
48
Stephen M. Blackburn, Robin Garner, Chris Hoffmann et al. · 2006 · 1.6K citations · Full text
Statistically rigorous java performance evaluation
Andy Georges, Dries Buytaert, Lieven Eeckhout · 2007 · 525 citations · Full text
Applicative programming with effects
Conor McBride, Ross Paterson · Journal of Functional Programming · 2007 · 402 citations · Full text