compiler: optimized tail calls #804

Activity

1. evacchi

   added

   enhancementNew feature or requestNew feature or request

   on Mar 18, 2025
2. evacchi commented on Apr 17, 2025

   

   evacchi

   on Apr 17, 2025

   Last edited by evacchi

   CollaboratorAuthor

   More actions

   given that:

   1. we fully control the ABI for functions
   2. we can mark any function that uses a return_call instruction during (some new?) analysis pass

   we could turn every function that does tail call into a long[] -> long[] (this is already kind of true in a general sense, even though we often optimized and "unbox" the args); the long[] arg is however, built as follows:

   args[0] = function index
   args[1] = CONT, DONE // i.e. 0, 1
   args[2..2+n-1] = reserved for results // generally n=1, so result-index == 2
   args[2+n...] = args
   

   The result array is built exactly in the same way, so that args can be even returned and modified in-place (avoiding further allocations)

   so, for instance factorial(n = 20, acc = 1) would be:

   args = { FACTORIAL_INDEX, CONT, 0, 20, 1 } // 0 is a result placeholder
   

   then each return_call is turned into a plain return args, but the callee must be a special ancillary function that actually does the looping. See below.

   Finally, we could then provide Machine#call wrappers with the usual API/ABI for external calls. (This could even work cross-module, provided that the target function is known to be tailrec. Which we could know by e.g. annotating it in the bytecode)

   here is a full example with FACTORIAL self-recursive and ODD/EVEN mutual-recursive functions:

   class Scratch {
       public static void main(String[] args) {
           // ABI is fIndex, status = [CONT|DONE], result, args...
           long[] result = tailCall(FACTORIAL, CONT, 0, 20, 1);
           System.out.println(result[resultSlot]);
           result = tailCall(ODD, CONT, 0, 1_000_000_000);
           System.out.println(result[resultSlot] != 0); // odd == false
           result = tailCall(EVEN, CONT, 0, 1_000_000_000);
           System.out.println(result[resultSlot] != 0); // even == true
       }
   
       static long DONE = 1, CONT = 0;
       static long FACTORIAL = 0;
       static long EVEN = 1;
       static long ODD = 2;
       static int fSlot = 0;
       static int statusSlot = 1;
       static int resultSlot = 2;
       static int argBegin = 3;
   
       static long[] factorial(long... args) {
           long n = args[argBegin + 0], acc = args[argBegin + 1];
           if (n <= 1) {
               args[statusSlot] = DONE;
               args[resultSlot] = acc;
               return args;
           } else {
               args[statusSlot] = CONT;
               args[argBegin + 0] = n - 1;
               args[argBegin + 1] = n * acc;
               return args;
           }
       }
   
       static long[] even(long... args) {
           long fIndex = EVEN, n = args[argBegin + 0];
           if (n == 0) {
               args[statusSlot] = DONE;
               args[resultSlot] = 1; // TRUE
               return args;
           } else {
               args[fSlot] = ODD;
               args[argBegin+0] = Math.abs(n)-1;
               return args;
           }
       }
   
       static long[] odd(long... args) {
           long n = args[argBegin + 0];
           if (n == 0) {
               args[statusSlot] = DONE;
               args[resultSlot] = 0; // FALSE
               return args;
           } else {
               args[fSlot] = EVEN;
               args[argBegin + 0] = Math.abs(n)-1;
               return args;
           }
       }
   
   
       static long[] tailCall(long... args) {
           var status = CONT;
           do {
               args = dispatchTailCall(args);
               status = args[statusSlot];
           } while (status == CONT);
           return args;
       }
   
       static long[] dispatchTailCall(long... args) {
           if (args[0] == FACTORIAL) {
               return factorial(args);
           }
           if (args[0] == EVEN) {
               return even(args);
           }
           if (args[0] == ODD) {
               return odd(args);
           }
           throw new IllegalArgumentException();
       }
   
   
   }
   
3. andreaTP

   changed the title [-]aot: optimized tail calls[/-] [+]compiler: optimized tail calls[/+] on Jul 24, 2025