Tail self-call optimization in generated C code?

[Eric Brunel]

Le 2017-08-21 14:55, PR a écrit :
> 2017-08-21 14:11 GMT+02:00, Eric Brunel <eric.brunel at pragmadev.com>:
>> Hello all,
>> 
>> I'm trying to get ECL to optimize tail self-calls in the C code
>> generated from the Lisp files and it looks like I'm missing something,
>> because I can't find a way to do that.
> 
> Here is an example that works (not written by me, it's from cliki.net):
> 
> (defun fib (n)
>   "Tail-recursive computation of the nth element."
>   (check-type n (integer 0 *))
>   (labels ((fib-aux (n f1 f2)
>              (if (zerop n)
>                  f1
>                  (fib-aux (1- n) f2 (+ f1 f2)))))
>     (fib-aux n 0 1)))
> 
> The generated C code uses goto, as you can see:
> 
> static cl_object LC1fib_aux(cl_object v1n, cl_object v2f1, cl_object 
> v3f2)
> {
>  cl_object env0;
>  const cl_env_ptr cl_env_copy = ecl_process_env();
>  cl_object value0;
>  ecl_cs_check(cl_env_copy,value0);
>  {
> TTL:
>   if (!(ecl_zerop(v1n))) { goto L1; }
>   value0 = v2f1;
>   cl_env_copy->nvalues = 1;
>   return value0;
> L1:;
>   v1n = ecl_one_minus(v1n);
>   {
>    cl_object v4;
>    v4 = v3f2;
>    v3f2 = ecl_plus(v2f1,v3f2);
>    v2f1 = v4;
>   }
>   goto TTL;
>  }
> }
> 

It does indeed, and I think I got it: the optional parameters to my 
function seem to prevent the optimization from happening. If I rewrite 
my function as:

(defun enumerate-aux (l index result)
   (cond
     ((null l) (reverse result))
     (t (enumerate-aux (cdr l) (+ index 1) (cons (list index (car l)) 
result)))
   )
)
(defun enumerate (l) (enumerate-aux l 0 nil))

the generated code for the enumerate-aux function is as expected:

static cl_object L1enumerate_aux(cl_object v1l, cl_object v2index, 
cl_object v3result)
{
  cl_object T0, T1;
  cl_object env0;
  const cl_env_ptr cl_env_copy = ecl_process_env();
  cl_object value0;
  ecl_cs_check(cl_env_copy,value0);
  {
TTL:
   if (!(v1l==ECL_NIL)) { goto L1; }
   value0 = cl_reverse(v3result);
   return value0;
L1:;
   {
    cl_object v4;
    v4 = ecl_cdr(v1l);
    {
     cl_object v5;
     v5 = ecl_plus(v2index,ecl_make_fixnum(1));
     T0 = ecl_car(v1l);
     T1 = cl_list(2, v2index, T0);
     v3result = CONS(T1,v3result);
     v2index = v5;
     v1l = v4;
    }
   }
   goto TTL;
  }
}

Not sure I understand why, but I have a solution.

Thank you very much!
  - Eric -


> 
> Paul
> 
> 
>> 
>> Here is the behavior I'm getting for this simple Lisp function:
>> 
>> (defun enumerate (l &optional (index 0) (result nil))
>>    (cond
>>      ((null l) (reverse result))
>>      (t (enumerate (cdr l) (+ index 1) (cons (list index (car l))
>> result)))
>>    )
>> )
>> 
>> As far as I can see, this function is properly tail-recursive, so I
>> expected the generated C code to take the into account and generate a
>> goto instead of a recursive call. But what I'm getting is this:
>> 
>> static cl_object L1enumerate(cl_narg narg, cl_object v1l, ...)
>> {
>>   cl_object T0, T1, T2, T3, T4;
>>   cl_object env0;
>>   const cl_env_ptr cl_env_copy = ecl_process_env();
>>   cl_object value0;
>>   ecl_cs_check(cl_env_copy,value0);
>>   if (ecl_unlikely(narg<1)) FEwrong_num_arguments_anonym();
>>   if (ecl_unlikely(narg>3)) FEwrong_num_arguments_anonym();
>>   {
>>    cl_object v2index;
>>    cl_object v3result;
>>    va_list args; va_start(args,v1l);
>>    {
>>     int i = 1;
>>     if (i >= narg) {
>>      v2index = ecl_make_fixnum(0);
>>     } else {
>>      i++;
>>      v2index = va_arg(args,cl_object);
>>     }
>>     if (i >= narg) {
>>      v3result = ECL_NIL;
>>     } else {
>>      i++;
>>      v3result = va_arg(args,cl_object);
>>     }
>>    }
>>    va_end(args);
>>    if (!(v1l==ECL_NIL)) { goto L3; }
>>    value0 = cl_reverse(v3result);
>>    return value0;
>> L3:;
>>    T0 = ecl_cdr(v1l);
>>    T1 = ecl_plus(v2index,ecl_make_fixnum(1));
>>    T2 = ecl_car(v1l);
>>    T3 = cl_list(2, v2index, T2);
>>    T4 = CONS(T3,v3result);
>>    value0 = L1enumerate(3, T0, T1, T4);
>>    return value0;
>>   }
>> }
>> 
>> The recursive call is generated as a recursive call in C too...
>> 
>> I'm almost sure I've seen C code generated from ECL that generated 
>> self
>> tail calls as goto's, and I know it works when using the bytecode, 
>> where
>> you just have to compile the function. But my search for a way to
>> trigger this behavior for the generated C code has been unsuccessful 
>> so
>> far.
>> 
>> I'm using ECL 16.1.3. I used "ecl -c ... --compile ..." to get the C
>> code, but my main build uses asdf:make-build with an ASD file.
>> 
>>