Work in progress: "Super Sib Calls"; opinions sought

[Andreas Bauer <baueran at in dot tum dot de>]

Dear gcc hackers,

I'm currently trying to develop and implement a more general tail call
optimisation for gcc 3.2.  My focus is on enhancing the compilation of
functional languages that use GNU C as target platform, such as Haskell
or Mercury.

APPROACH(ES):

I'm planning to go ahead with two separate approaches:  a) implementation
of what I call "super sib calls" and b) implementation of a "fully"
general tail call optimisation that can be applied to all the cases where
(super) sib calls normally fail.

I'm treating super sib calls as an independend call sequence on the RTL
level to not mess with the existing sibling call stuff.  But the
technique I'm applying is very similar to what's already there in gcc.
So, I'm merely removing some of the common constraints, e.g.

 - super sib calls may have a positive stack frame

 - super sib calls must not necessarily match in function signature

 - super sib call arguments are not concerned by overlapping arguments

 - etc.

This is achieved by creating "almost a normal call", but right before the
actual call instruction would be used, I'm copying all the outgoing
arguments back into the incoming argument space and jump to the subroutine
instead.  The result is that I can reuse my incoming argument space and
prevent stack growth for such cases.

Unlike broad and general approaches, this technique is binary compatible
with gcc compiled programs and doesn't require extra precautions.  It
does have some flaws though, but I'm mailing to discuss them with you.

Please, find attached a first patch that implements super sib calls for
gcc 3.2.  I have only tested it on x86, so far with a small sample code
that I have also included with this email (in case you want to try it on
a small demo program).  And no, the current patch does not yet solve all
the restrictions of sibcalls, but in the long run it should also support

 - indirect calls

 - more architectures

 - struct-returns / -args(?).

I'd be very grateful, if you pointed out problems in my code and
implications that I may not be aware of yet.  As I said, it's only a
start and it's work in progress, but an early discussion on the list may
prevent me and others from doing obvious mistakes when messing with call
chains and the like.

EXAMPLE:

The following little program computes the factorial of a number, but if I
use the "ordinary" gcc 3.2 as is, then on my machine I'm not getting
beyond fac(6) without stack overflow.  Using --foptimize-tail-calls and
my patch, you will have stack reusage and therefore no overflow at all.

#include <stdio.h>

int get_num (void);
int factorial (long long);
int fact_help (int, int);

int recursion;

int main ()
{
  int value;
  printf ("Enter 0 to exit.\n");
  value = get_num();
  while (value != 0)
    {
      printf ("Factorial: %d\n", factorial(value));
      printf ("Calls: %d\n", recursion);
      value = get_num();
    }
  return 0;
}

int get_num (void)
{
  int num;
  recursion = 0;
  printf ("Number: ");
  scanf ("%d", &num);
  return num;
}

int factorial (long long x)
{
  if (x != 1)
    {
      recursion++;
      /* This is being optimized as tail call */
      return fact_help (x, x - 1);
    }
  else
    return 1;
}

int fact_help (int total, int x)
{
  int dummy_array[500000];
  
  if (x == 1)
    return total;
  else 
    {
      recursion++;
      /* Another tail call */
      return fact_help (total * x, x - 1);
    }
}

Excuse the length of this mail and the patch, but hopefully it helped
making clear what I am working on and what I am trying to achieve here.
However, I did leave out the discussion of a fully general
implementation, as this is not relevant just yet.  Hope, that's ok.

Thank you in advance.
Cheers,
Andi.

P.S. the patch is from my current local cvs against the original gcc 3.2.

Attachment: super_sib_call_0_1.diff
Description: Text document