257128 - Interpreter and tail call elimination

Status: RESOLVED FIXED

(Rhino Graveyard :: Core, enhancement)

Description

[Igor Bukanov]

Given that interpreter do not use Java stack frames for JS (see bug 256339) it
is only natural to support at least minimal form of tail call elimination so
tail call recursion in JS would require only constant amount of memory.

Comment 1

[Igor Bukanov]

Attachment: Implementation

The code generation of the patch is straightforward. It adds context flags to
visitExpression which defaults to 0 indicating generic context if node does not
know what to do about it. Then during generation of Token.RETURN the patch
calls visitExpression with ECF_TAIL flag to indicate the context. Then
Token.COMMA, Token.HOOK, Token.AND and Token.OR preserve the flag for tail call
operands and when Token.CALL gets the flag it uses Icode_TAIL_CALL instead of
Token.CALL to indicate tail call.

The runtime part was more tricky since initially I tries to implement state and
its stack arrays reuse. But this is too complex due to possible exceptions
during state reinitialization (see comments in the patch) )so at the end the
difference between tail and ordinary call in the patch is that the tail call
release its parent and would transfer control on return to its grandparent
instead.

Comment 2

[Igor Bukanov]

Attachment: JS test cae

Without tail call recursion eleimination the test case would create 20_000_000
JS stack frames and even stackless interpreter would give up with OutOfMemory.

With the patch applied the test case finishes after about 45s on my Athlon
1.2MHz Fedora box.

Comment 3

[Igor Bukanov]

Attachment: Implementation2

The previous patch contains a bug: Interpreter.interpret would use initial
state to extract interpretation result but after tail call that state was never
updated with the result. The solution is to return the final state for the
result extraction.

Comment 4

[Igor Bukanov]

I committed the patch