Re: Recursion Optimization

[Zack Weinberg <zack@bitmover.com>]

Andreas Schwab wrote:
> Kevin Atkinson <kevinatk@home.com> writes:
> 
> |> Gcc can handel nested functions, so with a smart enough optimization
> |> technoligy it out to be able to rewrite it as
> |> 
> |> int sum (int i, int stop) {
> |>   int sumh(int i) {
> |>     if (i == stop) return i;
> |>     else return sum(i+1, stop) + i;
> |>   }
> |>   return sumh(i);
> |> }
> 
> In which way is this different from the previous version?  You still have
> the same call to sum which requires a contiguous argument list on the stack.

He meant to write this:

int sum(int i, int stop)
{
    int sumh(int i)
    {
	if(i == stop) return i;
	else return sumh(i+1) + i;
    }
    return sumh(i);
}

'stop' will be accessed via the static chain register, eliminating the
need to push it on the stack.  Unfortunately, you now have to push the
static chain register, so you don't gain anything.

What he actually wants gcc to do is something like:

int sum(int i, int stop)
{
  x:
    if(i == stop) goto y;
    else
    {
	push(i);
	i += 1;
	goto x;
    }
  y:
    if(stack_empty()) return i;
    i += pop();
    goto y;
}

where push, pop, and stack_empty are operations on some generic stack.
By doing this, you avoid having to push "stop", the return address,
the frame pointer, any call-saved registers, and so on.  It can be a
*huge* win in terms of stack usage.  You can use the function-call
stack as long as you have a frame pointer to work with - this
optimization would be rather difficult on AIX/PPC where there isn't
one, for example.

This can also enable further optimizations.  A moderately intelligent
compiler would recognize that the above code corresponds to

int sum(int i, int stop)
{
   for(; i < stop; i++) push(i);
   while(!stack_empty()) i += pop();
   return i;
}

and loop-optimize it to death.  A genius compiler would recognize that
the values pushed on the stack are predictable, and generate

int sum(int i, int stop)
{
    int tmp = 0;
    while(i <= stop) tmp += i++;
    return tmp;
}


... To answer the original question: No, GCC is not capable of any of these
optimizations.  I'm sure we would be delighted to accept contributions
that gave it the ability to do them.  Even adding support for general
tail recursion optimization a la Scheme would be a great step
forward.

There is existing support for tail recursion optimization in very
limited cases.  I have never got it to do anything useful for non-toy
functions.

zw