... Patch name: tailc.patch
{warning:title=Prototype} Work in progress.
{warning}
h1. 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.
h2. 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.
{code}
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
}
{code}
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.
{code}
public class Simple {
public static int tailcaller(int x) {
if (x==0) return x+1;
return goto tailcaller(x-1);
}
}
{code}
h2. 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.
{code}
java -XX:-FailOverToOldVerifier -XX:+TailCalls GeneratedClass
{code}
h2. 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/]
|