happy new year!

[Arnold Schwaighofer]

Hi John,

that's great news. I am still finishing my written thesis work. I was
delayed because performance evaluation showed that the current
implementation of tail calls in the compiler is slower than a
trampolined version because the current implementation moves arguments
twice. At the call site the arguments are moved to the normal outgoing
argument area of the current caller. Execution resumes at a tail call
method entry. This entry moves the arguments onto the caller's caller
and pops the frame.

tailcaller()
   move args onto outgoing arg area
   call tailcallee.tc_method_entry

tailcallee.tc_method_entry:
   move args onto caller's caller outgoing area
   pop frame

So i implemented a second prototype that moves the arguments onto the
caller's caller at the call site. The runtime (e.g
SharedRuntime::find_callee_arguments) had to be modified to look at
the correct place for parameters when the last java call on the stack
is a tail call.

tailcaller()
   move args onto incomming arg area
   call tailcallee.tc_method_entry

tailcallee.tc_method_entry:
   pop frame

This prototype currently does not support stack compression i.e if a
protection domain mismatch is detected an exception is thrown. But can
be made to by adding additional entry points to every method (and to
the c2i adapters) that move the arguments back to the caller's
outgoing area if the tail call is defeated

tailcaller()
  move args onto incoming arg area
  if (pd_mismatch)
    call tailcallee.tc_mismatch_entry
  else
    call tailcallee.tc_method_entry

tailcallee.tc_mismatch_entry:
  move args from caller's incomming area to caller's outgoing area
  jump tailcallee.vep

Anyway this change delayed me in finishing the thesis. So i still have
to write the evaluation part. I hope to be finished by the end of this
month although i am becomming more and more reluctant to give any
dates ;).

At this point i will publish a polished set of patches. The design
notes date from the very beginning of the implementation. I should
probably have deleted them. When my thesis is finished we can put the
parts (an abbreviated version) that describe the implementation on the
wiki.

regards
arnold
On Wed, Feb 11, 2009 at 12:13 AM, John Rose <John.Rose at sun.com> wrote:
> Hey, Arnold, I just reintegrated the latest patch I had from you and posted
> it to the mlvm repo.
>
> I also stuck your design notes (from your patch) on the wiki, FWIW:
>  http://wikis.sun.com/display/mlvm/TailCalls
>
> I'd be happy to take the next layer when you have a good moment to shoot it
> my way.
>
> At some point, we need to figure out the right kind of test harness to put
> on the repo (or wherever it belongs).  We'll probably want to hack some sort
> of tunnel through javac so we don't have to play with jasm to make use
> cases, and so we can begin to get the feel of using it as a first-class
> feature of the JVM stack.
>
> Thanks for all your work so far. It's pretty amazing stuff!
>
> We really want tail calls in order to build good method handle combinators
> (hence flexible invokedynamic runtimes) that don't blow the stack and
> introduce extraneous transition frames.
>
> Best,
> -- John
>
> On Jan 21, 2009, at 3:46 AM, Arnold Schwaighofer wrote:
>
>> A prototype was implemented on x86-32 and will hopefully be soon
>> availabe on the mlvm site.
>> The modified hotspot supports tail calls in the interpreter, client
>> and server compiler.
>> To mark a call as tail call the programmer emits a 'wide' byte code
>> before the various invoke... instructions.
>> The verifier checks that the call really is a tail call (i.e the last
>> thing the method does before it returns etc.).
>> Hotspot guarantees that a series of such tail calls execute in bounded
>> stack space. That is no stackoverflow exception happens.
>
>