Tailcall anyone ?

Last June, Arnold Schwaighofer push a patch to mlvm repository that allow to transform tail call invocation of a method to a jump.
Even if this transformation is classical in language like Lisp, Scheme or Caml, the JVM was not offering any help to optimize this kind of call until this patch.
Recently, Tom Davies has refreshed the patch in order to be used with a more recent jdk7 beta VM.
Really cool, indeed.

The patch requires the compiler to emit a special bytecode instruction for a tail call by prepreding the bytecode wide before one of the opcodes that invoke a method (invokestatic, invokevirtual, etc) at call site. So I've tweaked my favorite compiler, the one that compiles a language named Pseudo, to detect tail calls and emit a call with the bytecode wide.

Here is an example in Pseudo of a linked list and a function get that retrieve the element at an index given as argument. This function is recursive and ends with a tail call.

record Link {
  any element
  Link next

  init(e, Link n) {
    element = e
    next = n
  }
}

def cons(element, Link next):Link {
  return new Link(element, next)
}

def get(Link l, int index) {
  if (index == 0) {
    return l.element
  }
  return get(l.next, index - 1)   // tail call
}

{
  Link l = null
  for(int i = 0; i < 1000000; i = i + 1) {
    l = cons(i, l)
  }

  print get(l, 1000000 - 1)
}

The compiler detects a tail call and generates a wide in front of an invokestatic.

  public static java.lang.Object get(tailcall$Link, int) throws java.lang.Throwable;
    Code:
       0: iload_1       
       1: ifne          9
       4: aload_0       
       5: getfield      #4                  // Field tailcall$Link.element:Ljava/lang/Object;
       8: areturn       
       9: aload_0       
      10: getfield      #5                  // Field tailcall$Link.next:Ltailcall$Link;
      13: iload_1       
      14: iconst_1      
      15: isub          
      16: wide
      17: invokestatic  #6                  // Method get:(Ltailcall$Link;I)Ljava/lang/Object;
      20: areturn     

To execute the code, you need a patched VM, you can build it from the source (don't forget to replace the tailcall patches by the ones provided by Tom) or if you use a 32 bits linux, you can use this precompiled VM (client VM) and put it in directory /jre/lib/i386 of the lastest JDK7 binaries.
To enable tail calls, you need to add -XX:+TailCalls otherwise the verifier will be grumpy :)

/usr/jdk/jdk1.7.0/bin/java -tailc -XX:+TailCalls -XX:+UnlockExperimentalVMOptions -XX:+EnableInvokeDynamic -cp .:../runtime/lib/pseudo-runtime.jar tailcall

And the result is: 0.
Note that if you run this code without tailcall, it will blow out the stack.

What's next ?
Hum, perhaps a post on Pseudo.

Cheers,
Rémi