Re: proper tail recursion for gcc

[Mikael Djurfeldt]

Richard Stallman <address@hidden> writes:

> The obvious way to handle multiple values is to pass a structure
> pointer argument to the function and have it store values into the
> structure.  But if multiple values are common, it is worth doing
> something to make them faster.  On machines that pass arguments in
> registers, the first several values could be returned in the same
> registers.
> 
> But on most machines, where args are passed on the stack, it is
> probably only possible to return one or two args in registers anyway.
> The rest would have to be handled in memory, which probably means
> there is no way to do much better than the straightforward method.

The Dybvig paper explains their solution, where the first few results
are stored in registers, while the rest is stored on the stack, in the
same space where the arguments of the function were stored.

In fact, in Scheme, a continuation receiving multiple values is always
set up by the procedure `call-with-values', or by some syntactic
abstraction reducible to it.  Dybvig shows how the compiler easily can
reduce all uses of multiple values either into binding forms or into
multiple value calls of the form

  (mv-call (producer a1 ...) consumer-expr)

where consumer-expr evaluates to a procedure.

In their solution, storing the results from the producer in registers
and on the stack is, in most cases, the same thing as preparing the
arguments for the call to the consumer.  This means that a particular
value is usually not stored to memory at all.  In the case of many
values returned, the last values are stored once to the stack and read
from there once.  (The exception is when mv-call expression itself is
in a tail position, in which case the values on the stack need to be
shifted.)

> The most important platform, the x86, has 3 registers which could
> perhaps be used for return values.  Is it worth implementing the code
> to optimize them, if it will only optimize the first 3 values for most
> users?

It is certainly worth it.  The most commonly form of usage apart from
single return value is two returned values.  For example, in Olin
Shivers' implementation of SRFI-1 (the Scheme list library), there are
97 procedures with single return value, 13 procedures with 2 return
values, 1 with 3, 1 with 4 and 1 with 5.

The reason for this is that one or two conceptually distinct return
values is easy and natural to think about.  If you have further
conceptually distinct values, the issue becomes complex, and it is
likely that the problem can be abstracted in a more natural way.  In
fact, if you want to return more than three values, it is likely that
these are not conceptually distinct and may be better treated as a set
or a list returned as a single value.

Alos, we should not be discouraged by the low ratio of multiple value
return values compared to single return (16/97).  While it is more
common with single return values, there are certain situations where
an operation is naturally abstracted by a procedure returning multiple
values.  An example is `partition' which takes a predicate and a list
and returns two lists.

> Maybe it would be better to get the compiler working first, and then
> optimize multiple values if that is worth while.

Yeah, I just wanted to bring it into the picture so that we have it in
the back of our heads.

Actually, maybe it would be better to start with the design of the
compiler before implementing tail-call support for GCC.  Then it would
be clearer what kind of support we really need.