Skip to content

Extend loopification to mutual recursion and let-bound join points #234

Description

@Unisay

Problem

Loopify.hs (#181) turns a self-recursive tail call into a while true loop with simultaneous reassignment of the parameters, but only self-recursion. Two shapes are left as calls:

  • Mutual recursion: a group of functions that tail-call each other (even/odd, hand-written state machines) keeps paying a call per transition.
  • Join points: a let-bound helper only ever tail-called from the body is a loop in disguise, but compiles as a function.

Both fall to one backend-agnostic analysis: precise tail-position tracking (a call argument is never a tail position), a uniform-tail-call test (loopifiable iff called at one arity with all uses in tail position), a mutual group lowered to one dispatcher over a branch index, and a join point rewritten to a continue-style jump.

Approach

Implement that analysis: tail-position tracking, the uniform-tail-call test, mutual-group detection, join-point detection. Emission is Lua-specific and in places simpler than on a JS target:

  • a mutual group → one while true dispatcher over a branch-selector local plus shared argument slots, where each tail call sets the selector and the slots and loops;
  • a join point → reassign its parameters and loop, no call.

Lua's simultaneous assignment (a, b = e1, e2) removes the temporaries a JS emission needs for the slot update.

Prerequisites / Relations

Builds on the loopification landed in #181. Relates to #204 (the LuaJIT closure-allocation regression on loopified bodies). Same emission area, but that issue is about per-iteration closures, not recursion topology. Independent of the inlining issues.

Verification / Measurement

A mutually tail-recursive pair compiles to a single while true dispatcher with no inter-function calls in golden.lua, and its eval golden proves identical output and termination. A let-bound tail-only helper loses its function and becomes a loop. A benchmark mirroring #181's curried_step but over a mutual pair, through the #172 harness.

Metadata

Metadata

Assignees

No one assigned

    Labels

    OptimisationA Compiler Optimisationarea: codegenLua code generation / printingenhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions