Fusing method handle graphs for efficient dynamic JVM language implementations

A Method Handle (MH) in JSR 292 (Supporting Dynamically Typed Languages on the JVM) is a typed, directly executable reference to an underlying method, constructor, or field, with optional method type transformations. Multiple connected MHs make up a Method Handle Graph (MHG), which transfers an invocation at a dynamic call site to real method implementations at runtime. Despite benefits that MHGs have for dynamic JVM language implementations, MHGs challenge existing JVM optimization because a) larger MHGs at call sites incur higher graph traversal costs at runtime; and b) JIT expenses, including profiling and compilation of individual MHs, increase along with the number of MHs. This paper proposes dynamic graph fusion to compile an MHG into another equivalent but simpler MHG (e.g., fewer MHs and edges), as well as related optimization opportunities (e.g., selection policy and inline caching). Graph fusion dynamically fuses bytecodes of internal MHs on hot paths, and then substitutes these internal MHs with the instance of the newly generated bytecodes at program runtime. The implementation consists of a template system and GraphJIT. The former emits source bytecodes for individual MHs, while the latter is a JIT compiler that fuses source bytecodes from templates on the bytecode level (i.e., both source code and target code are bytecodes). With the JRuby Micro-Indy benchmark from Computer Language Benchmark Game and JavaScript Octane benchmark on Nashorn, our results show that (a) the technique can reduce execution time of Micro-Indy and Octane benchmarks by 6.28% and 7.73% on average; b) it can speed up a typical MHG’s execution by 31.53% using Ahead-Of-Time (AOT) compilation; and (c) the technique reduces the number of MH JIT compilations by 52.1%.