compiler: optimized tail calls
- Dominant language
- Java
- Stars
- 1.1k
- Forks
- 71
- PR merge metrics
- No merged PRs in 30d
Description
#801 introduces tail calls, as a plain desugaring into CALL(_INDIRECT)+RETURN.
This obviously works in a general sense, but it does not implement "real" tail call optimization: some tests in the suite (currently disabled) exercise the stack with deep recursions (e.g. factorial of 1_000_000), and cause an overflow error.
While this is a potential issue, the tail call proposal is currently only required to be present to pass the exception handling suite; however, eventually, we might still want to address it.
There are essentially two scenarios:
- simple tail recursion, where `f` calls itself,
- mutually recursive functions, where `f` calls `g`, `g` calls `f` (more complex scenarios might involve n > 2 functions too).
In the first case the recursion can be (more or less) flattened to a jump to the beginning of the function;
In the second case, multiple solutions could be adopted, such as trampolines, stitching together the bodies of the functions and jump to their logical prologues, or even a task queue.
## Prior art
- https://github.com/Sipkab/jvm-tail-recursion
- https://github.com/wheaties/TwoTails
- https://gist.github.com/eamelink/4466932a11d8d92a6b76e80364062250
Contributor guide
Assessment
This issue has not been assessed yet.