alloca

[Robert Firth]

In article <19895 at cornell.UUCP> aitken at svax.cs.cornell.edu (William Aitken) writes:
>Could someone give a concrete example of an architecture on which alloca is
>difficult to implement, and explain what it is that makes automatic
>arrays possible, but alloca difficult?   If C were to provide a means 
>to declare an automatic array with size that depended on an integer valued
>argument, many of the uses of alloca would disappear;  would this be any
>easier to implement than alloca?  Why?

First, recall that "alloca" claims a chunk of local stack space, of size
unknown at compile time.  It is therefore almost the same as being able
to declare a local array

	int myarray[expression()]

whose size is likewise dynamic.  The implementation difficulty is almost
the same.  C local arrays, by contrast, have a size known at compile time,
and so are a lot easier to deal with.

There are two problems.  Neither is really major, but they're there.
First, what happens if you have an inner declaration after the allocation:

	int myarray[...];	/* array of dynamic size */
	...
	{
	  int i,j;
	}

If you observe strict stack allocation (LIFO) semantics, then I and J are
at an offset from the start of the stack frame that you can't compute.  So
you have to "float" inner declarations above the dynamic declaration, which
makes life tough for one-pass guys.  (If you declare an inner variable
after calling alloca you'll probably discover another reason why it's a
bad idea to use alloca!)

The second problem is that, if the size of a local stack frame is dynamic,
you cannot get away with having just a frame pointer; you MUST have a stack
front pointer.  That can add substantially to the cost of a procedure call;
moreover, it probably adds to the cost of ALL procedure calls.  That means
you probably can't have the caller adjust the stack, which blows away the
optimisation of eliding stack adjustments between successive calls, and
so compounds the inefficiency.

On the majority of machines I've written codegenerators for, there is a
cost in going from a stack regime where all sizes are known at compile
time, to one where they aren't.  It seems to me pretty silly to force
every C user to pay that price for the sake of the few who regard writing
portable code as beneath their dignity.

So, do I have an alternative?  The only serious reason for allocating
dynamic objects on the local stack is to ensure their automatic deallocation
on scope exit; most C dynamic storage libraries are pretty efficient. This
seems to me largely a matter of programmer convenience, which could
perhaps be served almost as well by an auxiliary stack managed explicitly.

We initialize this by something like

	createaux(size)

which does a malloc() to get the stack and sets up a stack pointer.
We claim by allocaux(size), which grabs a chunk.  We manage scopes
explicitly by 

    {
	m = markaux(); /* grab current aux stack pointer */

	... /* code that does a lot of allocaux() calls */

	resetaux(m);   /* reset aux stack pointer */
    }

So the programmer has to remember to set a Mark at the beginning of the
scope and to do a Reset at the end of the scope.  And, of course, not to
jump out of the scope!

Finally, there is an ALMOST safe way to do without the Mark/Reset
discipline.  Give each allocated chunk a header and store in it the
value of the caller's stack pointer.  On an allocate, first deallocate
all chunks whose stored stack pointer is "below" the stack pointer of
the current caller - those chunks must have passed out of scope.

(I used this technique to implement Algol-60 local arrays; this was
 completely safe rather than "almost" safe, since the compiler could pass
 down to the allocator enough contextual information)

Finally, the old BCPL library had a strange function that was a lot
easier than alloca and allowed you to claim one (or at most a very
few) chunks of stack space.  It is called aptovec, and is rather like
this:

	int aptovec( f, s )
	/* whatever says f takes (*int,int) and returns int */
	int s;
	{
	  int myarray[s];
	  return f(&a[0],s);
	}

The body is a hairy piece of machine code that achieves the above effect,
including allocation and deallocation of the dynamic array.

Hope this helps.