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 <b>get(</b>l.next, index - 1<b>)</b>   // 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: <b>wide</b>
      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