Patch name: tailc.patch

Tail call support in Davinci

Tail call optimization guarantees that a series of tail calls executes in bounded stack space. No StackOverflow exception happens.

After applying the tail call patches Hotspot supports tail call optimization for all method invocations that are marked as tail call. The optimization is performed by the VM if the invocation is marked as a 'tail call' and the necessary conditions for tail calls are met. That is the VM supports hard tail calls. If the VM can not guarantee that the innvocation will be optimized it throws an exception. Note that the VM will not recognize normal calls that could be tail call optimized and perform the optimization on them.

To enable tail call optimization the VM is started with the flag -XX:+TailCalls.

java -XX:+TailCalls TailCallExample

Tail call optimization is implemented by replacing the caller's frame with the callee's frame if the java security mechanism allows it. If removing the caller's frame is not possible, the VM proceeds in two possible ways depending on whether the 'TailCallStackCompressions' flag is set or not.

• TailCallException is thrown. If the VM detects that the security information between caller and tail called callee differs it throws a TailCallException. The security information differs if the class holding the caller method has a different protection domain than the class holding the callee. This behaviour is enabled by default e.g the flag -XX:+TailCallsStackCompression is not set.

• Tail call is defeated. The stack frame of the caller is left on the stack. If the recursion depth is deep enought the stack becomes full. At this point, just before throwing a StackOverflow exception the VM tries to 'compress the stack' by removing superfluous stack frames. To enable this behaviour the flag -XX:+TailCallsStackCompression has to be set.

Marking a call as a 'tail call'

To mark a method call as tail call the invocation bytecode instruction has to be prefixed with a 'wide' (196) bytecode.

public static int tailcaller(int);
  Code:
   0:	iload_0
   1:	ifne	8
   4:	iload_0
   5:	iconst_1
   6:	iadd
   7:	ireturn
   8:	iload_0
   9:	iconst_1
   10:	isub
   11:	wide
   12:	invokestatic	#2; //Method tailcaller:(I)I
   15:	ireturn

}

After applying the langtools-tailcall-goto.patch (to the langtools directory) we can mark calls as tail calls using the 'goto' prefix before a method invocation in java. Above bytecode example is generated by javac from following java code.

public class Simple {
  public static int tailcaller(int x) {
    if (x==0) return x+1;

    return goto tailcaller(x-1);
  }
}

Generating code

There are two bytecode verifiers in the jdk. The old type-inference verifier and the new type-checking verifier. The type-checking verifier is used if the class file format major version is >= 50. To use this verifier, a valid stackmaptable attribute has to be emitted. Tail calls are currently only supported if the new verifier is used. Hence, to use tail calls the generated class file must have a version number >= 50.0 and must contain a valid stackmaptable attribute.

The default behaviour of the jvm is to fall back to the old verifier if the new verifier fails (e.g because the stackmaptable attribute is invalid). The jvm has an option to disable this behaviour.

java -XX:-FailOverToOldVerifier -XX:+TailCalls GeneratedClass

Implementation

e
... more to come.

In the meantime some implementation details can be found in:
http://www.ssw.uni-linz.ac.at/Research/Papers/Schwaighofer09Master/

There currently exist two branches

• tailc-eager.patch: Compiled code (by server, client compiler) moves the callee's arguments to their actual position at the call site as part of the argument lowering.
• tailc-lazy.patch: Compiled code moves the callee's arguments to their actual position at the callee's method entry. Hence arguments are moved twice. First to the outgoing argument of the caller area at the call site. Later the tail call method entry code moves the arguments to the caller's incoming argument area.