Patch name: tailc.patch

*Note: Work in progress.*

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 'TailCallStackCompression' 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:+TailCallStackCompression 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:+TailCallStackCompression 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.

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 we can mark calls as tail calls using the 'goto' prefix before a method invocation. 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);
  }
}