[m-dev.] [m-users.] Tail recursion optimisation

[Zoltan Somogyi]

On Mon, 18 May 2026 16:41:12 +1000, Julien Fischer <jfischer at opturion.com> wrote:

> On Mon, 18 May 2026 at 16:35, Zoltan Somogyi <zoltan.somogyi at runbox.com> wrote:
> >
> > On Mon, 18 May 2026 16:33:32 +1000, Julien Fischer <jfischer at opturion.com> wrote:
> > > It is. Those pragmas are currently undocumented however (at least
> > > their documentation
> > > is currently commented out.)
> >
> > I have already started enabling that documentation, after fixing it up.
> 
> IIRC, the reason it wasn't enabled is that you can specify that lack
> of tail recursion
> should cause a compilation error.  That fine in production grades,
> like asm_fast.gc
> or hlc.gc, but it also affects grades that do not support tail
> recursion, like the deep
> profiling grades (i.e. it needs to be possible to compile programs for
> profiling without
> having to manually edit all the require_tail_recursion pragmas.)

I am in the process of fixing that, by adding a new dimension to the pragma.
The two values of this dimension I am proposing to be named "in_all_grades"
and "in_tailrec_grades_only", which the first calling for violations of the required
kind of tail recursion to be reported in all grades, with the second calling for the same
only in grades that support tail recursion in general (mostly asm_fast and hlc).

> (Another issue may have been that at the time those pragmas were added, there
> was more disparity between the backend over code could be compiled to be
> tail recursive.)

Yes, there was, with the main limitation being that MLDS grades supported only self
recursion. I added support for mutual recursion to MLDS grades several years ago.
If I remember correctly, the only difference now between LLDS and MLDS grades
in this respect is that in mutual recursion between predicates and/or functions
in different modules can be tail recursive in LLDS grades, but not in MLDS grades.
However, the code in mark_tail_calls.m that checks whether mutual recursive calls
are tail recursive does not consider cross-module calls to be calls that it should check,
since the callee may not (and in most cases, will not) call the caller back. In the absence
of compiler-visible mutual recursion, the pragma is not applicable.

The only issue here is when the cross-module call is to an opt-imported procedure.
These are included in the SCCs we use test for mutual recursion, but whether such
a callee is in opt_imported or just plain imported obviously depends on the values
of the intermodule optimization options. We could handle this with a third value
on the new dimension, e.g. by splitting "in_tailrec_grades_only" into two, for which
the descriptive but too-long named could be "in_tailrec_grades_only_with_intermod"
and "in_tailrec_grades_only_all_in_one_module". The first would not warn about
mutual tailrec between modules, the second would. Better and/or shorter names
welcome.

Zoltan.