Tail Call Optimization in the Java HotSpot(TM) VM

Arnold Schwaighofer
arnold.schwaighofer@gmail.com

Abstract

Many programming language implementations compile to Java bytecode, which is executed by a virtual machine (e.g the Java HotSpot(TM) VM). Among these languages are functional languages, which require an optimization that guarantees that certain kinds of method calls do not cause the execution stack to grow unlimitedly. This optimization is called tail call optimization and is currently not supported by the HotSpot(TM) VM. Implementations of functional languages have to resort to alternative techniques to guarantee that the stack space does not increase unboundedly. These techniques complicate the implementation and also incur a performance penalty.

This thesis presents techniques for supporting tail call optimization in the Java HotSpot(TM) Virtual Machine. Our optimization is implemented in the interpreter, the client compiler and the server compiler. Tail call optimization normally removes stack frames to guarantee that the stack space stays bounded. However, some stack frames are required for the Java access security mechanism to work and hence cannot be removed. The virtual machine features a mechanism called deoptimization that allows one to rewrite stack frames. We describe an approach that uses the deoptimization infrastructure to compress stack frames when tail call optimization was disabled because of the security mechanism. This approach allows a series of tail calls to execute in bounded stack space in the presence of a stack-based security mechanism.

Download as PDF