Fabonicseries Program required

[Chris Uppal]

I'm interested in whether the Hotspot JIT compiler ever actually does
[tail recursion elimination]

As far as I can tell from limited research, it does not.

First off, I can't find any mention of the term "tail recursion" in the
platform source (1.5 through 1.7). And "tail call" only seems to occur in
irrelevant contexts. I didn't check all variations of that phrase, though.

Secondly, even with as trivial a case as I can concoct without letting the
optimiser remove the method altogether, it is possible blow the stack at
runtime. I'll attach my test code. Presumably the JVM doesn't consider itself
under a responsibility to simulate the effects of running out of stack space,
so I assume that it didn't actually remove the tail-call.

Lastly, I had a play with the JVMTI stuff to monitor the generated IA32 code.
I'll attatch the result of disassembling that too in case anyone fancies trying
to make sense of it. My assembler skills are weak, but as far as I can tell
from some rather stange code, the JIT has inlined one layer of recusive calls,
but done no other recursion elmination. There are no backward jumps, so no
looping has been introduced. I'm guessing that the call to
_resolve_static_call_Java is checking code initially, and that it and the
preceeding no-ops will be overwritten with a direct recursive call to recurse()
after the checks have passed (but that is /only/ a guess !)

-- chris

===============================
public class Test
{
private static class BoolHolder { boolean value; }

public static void
main(String[] args)
{
BoolHolder bottom;

System.out.println("warming JIT...");
bottom = new BoolHolder();
for (int i = 0; i < 10000; i++)
recurse(1000, bottom);

System.out.println("running...");
bottom = new BoolHolder();
recurse(1000 * 1000 * 1000, bottom);
System.out.println(bottom.value);
}

private static void
recurse(int n, BoolHolder bottom)
{
if (n <= 0)
{
bottom.value = true;
return;
}
recurse(n-1, bottom);
}
}
===========================================
Disassembled IA32 code for recurse()

0xB05FE0 mov [dword esp+0xFFFFD000],eax
0xB05FE7 sub esp,0xC
0xB05FED test ecx,ecx
0xB05FEF jle short 0xB0601A ; recurse+0x3A
0xB05FF1 mov eax,ecx
0xB05FF3 dec eax
0xB05FF4 test eax,eax
0xB05FF6 jle short 0xB06014 ; recurse+0x34
0xB05FF8 mov ebx,ecx
0xB05FFA add ebx,0xFFFFFFFE
0xB05FFD test ebx,ebx
0xB05FFF jle short 0xB0600E ; recurse+0x2E
0xB06001 add ecx,0xFFFFFFFD
0xB06004 nop
0xB06005 nop
0xB06006 nop
0xB06007 call _resolve_static_call_Java
0xB0600C jmp short 0xB0601E ; recurse+0x3E
0xB0600E mov [byte edx+0x8],0x1
0xB06012 jmp short 0xB0601E ; recurse+0x3E
0xB06014 mov [byte edx+0x8],0x1
0xB06018 jmp short 0xB0601E ; recurse+0x3E
0xB0601A mov [byte edx+0x8],0x1
0xB0601E add esp,0xC
0xB06021 test [dword 0x390000],eax
0xB06027 retn

 

[Chris Smith]

Lastly, I had a play with the JVMTI stuff to monitor the generated IA32 code.
I'll attatch the result of disassembling that too in case anyone fancies trying
to make sense of it. My assembler skills are weak, but as far as I can tell
from some rather stange code, the JIT has inlined one layer of recusive calls,
but done no other recursion elmination. There are no backward jumps, so no
looping has been introduced. I'm guessing that the call to
_resolve_static_call_Java is checking code initially, and that it and the
preceeding no-ops will be overwritten with a direct recursive call to recurse()
after the checks have passed (but that is /only/ a guess !)

Yes, very nice. Looks like you are right about everything.
_resolve_static_call_Java makes perfect sense for handling static
initialization requirements without a long-term performance penalty.
(In this case, though, one could imagine the compiler being smart enough
to recognize that static initialization can never be triggered by a
static method calling itself; or indeed anything in the same class.)
Definitely no tail call elimination. Plenty of other places, as well,
where optimizations are obvious.

Is this code before your warm-up loop, or after? I'm assuming before,
since the static call would be resolved by then if it were after. It
would be interesting to see what else happens; maybe I'll poke around.

 

[Chris Uppal]

(In this case, though, one could imagine the compiler being smart enough
to recognize that static initialization can never be triggered by a
static method calling itself; or indeed anything in the same class.)

Probably just not worth the effort. It won't make any real difference unless
the method is executed a lot, but if it's executed a lot then it won't make any
real difference ;-)

Is this code before your warm-up loop, or after? I'm assuming before,
since the static call would be resolved by then if it were after. It
would be interesting to see what else happens; maybe I'll poke around.

JVMTI seems to be telling me about this code sometime around first call to
recurse() (I say "sometime" because I don't know how often it has been executed
in the interpreter before that). I'm assuming that JVMTI only tells me about
whole-method generation, not about "simple" runtime patching. In this case it
doesn't tell me about any subsequent patches to recurse(). I /have/ seen it
generate several different versions of a method during a run, but not in this
case.

-- chris