tail calls in the VM
By john.rose on Jul 12, 2007
Tail-calling is an old idea; see the MIT “Lambda the Ultimate” papers. It is usually treated as an optimization. If A calls B calls C, and the last action of B is to call C, then the machine resources (such as stack) are adjusted so that it is as if A had directly called C. In effect, B pops its stack frame back to A, pushes arguments to C, and jumps to C, so that when C pops its arguments and returns, it branches directly back to A.
This optimization can save instructions, stack space, and instruction cache activity, so it is often found in compilers. But as long as it’s only an elective optimization of what’s really just a recursive call, it matters only as a performance hack. Call this hack “soft tail call”.
On the other hand, a “hard tail call” is a guaranteed tail call, one not only allows the compiler to improve the call site (from B to C then back to A), but requires the improvement. Some languages, notably Scheme, Haskell, and Fortress, feature hard tail calls, and use them to form iterative constructs, threaded interpreters, and other forms of control flow delegation.
JVM Support for Hard Tail CallsWe propose a new bytecode prefix called
tailcall, which may precede any
invokeinstruction. This prefix has no other action than to require that the following instruction constitute a tail call, and be implemented as a hard tail call.
The byte code for
tailcall is numerically the same as the
The verifier statically checks the following properties:
- The callee method’s return signature is identical with the caller method’s return signature.
- The invoke instruction is immediately followed by a return instruction.
- No exception handlers apply to the invoke instruction.
- The caller method is not synchronized.
- The caller method is holding no object locks. (It has executed sufficient
monitorexitinstructions to undo the effect of any
- The callee method is accessible and linkable from the caller method.
The JVM executes the
invoke instruction as if the
tailcall prefix were not present, except that the JVM discards the stack frame for the caller before executing the callee. The following return instruction is never directly executed; it is present only to simplify code analysis.
The effects of removing the caller’s stack frame are visible to some APIs, notably access control checks and stack tracing. It is as if the caller’s caller had directly called the callee. Any privileges possessed by the caller are discarded after control is transferred to the callee. However, the linkage and accessibility of the callee method are computed before the transfer of control, and take into account the tail-calling caller.
Removing the caller’s stack prevents
StackOverflowError conditions which would otherwise be eventually caused by iteratively tail-calling one or more methods but never returning.
Because of the difficulty of ensuring correct caller access, the following methods may not be the subject of a hard tail call. In particular,
Method.invoke simulates access checks which properly occur when the caller links to the callee, and therefore requires the caller to be visible on the stack.
- (what else?)