This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: proper tail recursion for gcc
On Thu, Jul 20, 2000 at 11:41:18AM +0200, Jakub Jelinek wrote:
> On Wed, Jul 19, 2000 at 11:33:08PM -0700, Zack Weinberg wrote:
> > On Wed, Jul 19, 2000 at 11:06:08PM -0700, Geoff Keating wrote:
> > >
> > > Mark Probst <schani@mips.complang.tuwien.ac.at> writes:
> > >
> > > > i want to implement proper tail recursion for a much broader set of
> > > > cases than is currently implemented.
> > > ...
> > >
> > > I think you'll find this has already been done in the development gcc.
> > > It's the 'sibling call' optimisation.
> >
> > It's not as complete as a Scheme compiler is required to implement.
> > The Scheme standard requires sibcall optimization for *every* function
> > call followed immediately by a return from the current function. We
>
> There must be exceptions, like if you take an address of some local
> variable and pass it to some other functions...
Scheme is a LISP dialect. It doesn't have any constructs that would
interfere with this optimization.
...
> > We don't sibcall optimize this, but we could and probably should.
> > [Perhaps this is the sort of thing that would be handled by the
> > "better tree-based sibcall optimizer" coming RSN?]
>
> I believe the problem here is not if we use tree-based or
> expand_call/rtl-based sibcall optimizer, the issues are backend
> related. Basically, if the incoming arguments stack area of the
> tail function is larger than of tail callee, then you have to
> allocate some area immediately below virtual-incoming-args-rtx to
> compensate it and in a machine specific way copy machine dependent
> stuff down (or up, depending on stack growth), e.g. on Intel the
> return address stored on the stack.
I do understand this.
In the specific example I gave, it would be possible to implement it
without machine-specific stack diddling, if we had a concept of
alternate entry points. In pseudo assembler:
foo:
move a(%sp), %r1 ; r1, r2 call-saved
move b(%sp), %r2
push %r2
push %r1
call calculate_bar ; result in %r0
add 8, %sp
jmp foo_tail
foo_with_bar:
move a(%sp), %r1
move b(%sp), %r2
move c(%sp), %r0
foo_tail:
...
But that would take serious interprocedural analysis, which we aren't
going to have anytime soon.
> It is IMHO worth implementing, but under a separate -f switch not
> enabled by default from -O options, because I don't think it will be
> a win for random C code.
This comes back to Mark's original idea, to have an annotation on
specific function calls indicating that they should be sibcall
optimized. I'd rather have that than another -f switch.
zw