Re: Calling conventions (particularly 32-bit ARM)

Thomas Koenig <tkoenig@netcologne.de> writes:

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>

That would mean that you find it ok that existing programs that use
vararg functions like printf but do not declare them before use don't
work on your newfangled architecture.

>
Interestingly, tail call optimization (which I believe you like)
can cause bugs with mismatched arguments when different functions
disagree abuout the stack size.

I have a use case for tail-call optimization.  When I first looked
into that around 1994, I found that gcc does not perform tail-call
optimization, and I was surprised, because it had been written by a
Lisp programmer.

When I looked into the reasons, I found that in C calling conventions
typically the caller is responsible for alloating stack space for
arguments and for deallocating that stack space.  The reason for that
is varargs and the fact that in old C there was no requirement to
define a prototype of a function (including vararg functions).  If in
case of a call just before a return the function needs to put
deallocating code between the call and return, the call is not a
tail-call and therefore cannot be tail-call optimized.

So I thought that with C calling conventions (necessitated by the
properties of the C language), tail-call optimization is not possible,
but Mark Probst, a student in our group, actually managed to deal with
the tail-recursion case
<https://www.complang.tuwien.ac.at/schani/diplarb.ps>.

A few years later sibling call optimization (more restrictive than
general tail-call optimization, but less restrictive than
tail-recursion elimination) appeared in gcc.  The gcc manual
apparently does not say what a sibling call is, but
<https://stackoverflow.com/questions/22037261/what-does-sibling-calls-mean>
says "where caller function and callee function do not need to be
same, but they have compatible stack footprint.".  Given the bug you
point out, that's obviously not restrictive enough to be correct in
all cases.

Concerning my use case, for me it's good enough if tail-calls are
optimized when the caller and the callee have the same argument types
and return type, and the arguments fit in registers.  So if in your
buggy case gcc decided not to optimize the call as sibling call, my
use case would not be affected.

Moreover, I need a guarantee that a call is actually
tail-call-optimized (and if not, compilation should ideally error out,
saving me the need to validate that property afterwards), and I would
be willing to put some text in the source code that indicates that
intent.  E.g., something along the lines of

void add(VMinst *ip, long *sp, long sp_top)
{
  /* payload start */
  sp_top += *sp++;
  /* payload end */
  /* invoke the next VM instruction */
  (*ip)(ip+1,sp,sp_top) __attribute__("tail-call optimized");
}

Existing code would be unaffected by such an approach to tail-call
optimization.

Beyond my use case: tail-call optimization has to be applied like
every other optimization: It preserve the behaviour of existing,
working programs, i.e., the result must be equivalent.  In the bug you
mention, this obviously was not the case, and one way out would be not
to apply tail-call optimization in this case and similar cases (maybe
in all cases where arguments are in memory).  That looks like a simple
way to fix the bug.  Maybe there's a less restrictive one.

Sure one can wish that C was different (e.g., like the fantasy that
all C programs are strictly conforming to some particular C standard
that turns some desired transformation into a correct optimization),
but existing, working programs are far more relevant than the wishes
for some transformation IMO; there are a lot of people who see this
differently, but it seems to me that these people not only wish that
the old C programs vanish, but they don't care much about new C
programs (apart from a few benchmarks), either.  After all, they don't
program in C, but in C++, Fortran, Rust, or something else.

Actually, concerning the fantasy mentioned above, gcc already offers
options such as -std=c23 and -pedantic which would allow the user to
tell gcc that the compiled program actually lives in this fantasy
world, but if the user did not ask for pain, a compiler should not
provide it.

So, if you want to allow mismatched declarations, better
disable tail calls, to be on the safe side.

That would be a way of dealing with the problem.  It matches the
general pattern of people defending transformations that do not
preserve program equivalence (i.e., are buggy when intended as
optimizations) by putting up a straw man that disables correct
otimizations in addition to transformations that do not preserve
program equivalence.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
  Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>