Re: [Tinycc-devel] Proposal for handling alloca(). Anyone see a problem with it?

[David A. Wheeler]

Wheeler mentioned this as a problem:
> >   a( b(4+c()), alloca(x*g()), h()+n());
> > In this example, a naive alloca implementation would be in the middle of 
> > computing this expression, with some intermediate values on the stack, and 
> > the alloca() call would then screw up the stack DURING the expression 
> > calculation... causing the whole expression to miscalculate.

Daniel Glöckner <address@hidden>
> Are you shure this can happen with tinycc?
> AFAIR all parameters are evaluated before gfunc_call is called to put
> them on the stack.

I believe that's only true for each function call taken individually.  But when 
calls are nested, you can't make an (outer) call unless you've computed all its 
(inner) parameters, and if a call to alloca() is in the parameters, it'll 
usually subvert the evaluation process.

Here's my understanding of what would happen in the example above (corrections 
welcome!):
* The code calculates b(4+c()), and places that result on the stack.
* It then computes x*g(), and places that result on the stack.
* It then calls alloca(), which consumes its (one) parameter, and that's when 
the magic happens: alloca would MOVE the stack pointer some distance computed 
at run time.  It'd then return the alloca result... but store it at a radically 
different stack position, one whose distance from the frame pointer is NOT 
necessarily known at compile time.  Even if it's not "called" in the 
traditional sense, the basic idea would be that the stack pointer would get 
moved.
* It then computes h()+n(), and places that result on the stack.

Now tinycc needs to generate the code that calls a().  But wait!  The 
parameters of a() are no longer adjacent on the stack, as they would be under 
"normal" circumstances! Instead, we probably have the first parameter, a big 
area allocated by alloca() whose size is NOT necessarily known at compile time, 
followed by second parameter (the pointer returned by alloca()), and the third 
parameter (h()+n()'s result).  The function parameters are NO LONGER ADJACENT, 
because the area created by alloca() is "in between".  That'll screw up any 
callee, who will try to access parameter 1 and get some allocated memory 
instead.

It could copy the "parameters already computed" up after the alloca(), but 
that's really messy. And it leaves other problems unsolved; if more variables 
get allocated later (e.g., { int i; ...}), they're no longer a known constant 
distance from the frame pointer, which screws up everything.

Another solution would be to allocate the alloca() area AFTER the current stack 
pointer (say, decrement at least 4096 bytes, and use THAT as your location for 
allocated memory).  But that means that if you later on declare long automatic 
variables, or simply stack several signal callers, you're in trouble. Handling 
calling functions in the expression is really nasty; it'll be easy for silent 
failures to happen.

Some problems go away if you say "you can't use alloca() unless nothing is 
stacked", e.g.:
 a = alloca(q);
But of course, that means that many programs will go haywire. And that still 
leaves the problem of later declarations unsolved.  Declarations like { int i; 
....} after the alloca() will still mean that there isn't a constant distance 
between the frame pointer and the location of i.

This isn't a big deal with a multi-pass compiler, because a multi-pass compiler 
can break down the steps and reorder them in a "nice" way.  But adding another 
complicated pass just to support alloca() is silly; let's do something simpler.

--- David A. Wheeler