Tail self-call optimization in generated C code?

[PR]

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;
 }
}


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.
>
>