dylibso / dylibso/chicory

compiler: optimized tail calls

Open
#804 1 comment 0 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.