🚀 go-pugleaf

Stan Ryckman writes:
|> Konrad Schwarz (KS) wrote:
	[alloca ...]
KS: As far as I know, implementing alloca via the stack is trivial on
KS: any general-purpose CPU, but I am interested in hearing of counter examples.
 
J Kanze: So what do you do on machines that don't have a stack?

KS: General-purpose CPU's have stacks, at least in my book.  How do you
KS: implement C on machines that don't have a stack?

|> How about calling malloc() at function entry, and free() at function
|> exit?  That should work.  (I mean that the generated code does
|> this, not that the programmer does this; it's invisible to him/her.)
|> setjmp/longjmp becomes tricky to implement to avoid memory leaks, but
|> is possible.

Someone else mailed me the suggestion ``use activation records,''
and I guess that is what your proposal amounts to.  In this case,
alloca degenerates into a simple malloc; alloca's speed is still of the
same order as procedure invocation.  Of course, the implementation must now
garbage-collect alloca'd memory at procedure exit, which is simple
to do, since the blocks can be linked together in a list.

I am pretty sure that most any scheme used to implement C is trivially
extended to handle alloca.

|> There are several problems with alloca().  I couldn't think of
|> any when I previously wrote.  Here are three:
|> 	1.  Think of how it would be implemented such that it would
|> 	    work correctly when assigned to a function pointer.  For
|> 	    example, call some other function with malloc sometimes
|> 	    and alloca sometimes as an argument.

The ANSI function (or macro?) setjmp is not allowed to
be called in all contexts; I'm sure a similar restriction can be
imposed on alloca.

|> 	2.  Try this:
|> 	        char *base, *interesting_stuff;
|> 	        int f1(), f2();
|> 	        interesting_stuff = f1() + (base=alloca(SIZE)) + f2();
|> 	    How would you implement alloca() to handle this?

I'm afraid I don't see the problem here.  Let's say f1, f2, and
alloca can be called in any order (they have to be, since there
is no sequence point in the assignment).  f1() returns an integer,
f2() returns an integer, their sum is added to base, so you get a pointer
offset f1() + f2() from base.  If alloca is called first, the
(in this case non-existant) arguments of f1 and f2 get pushed after
the allocated block; if it gets called last, f1 and f2 have removed their
procedure frames; if it gets called in between the two, the first function
removes its stack frame, then alloca reserves space on the stack, after
which f2 puts its stuff on the stack.

Are you worried where the partial
results (e.g., f1 () + (base = alloca(SIZE))) will be kept?  Well, to
a first approximation in registers.  If there aren't enough registers,
the compiler will know this, and (I'd hope) be able to reserve an
unnamed variable here.  C++ allows variables to be defined at any point,
so its definitely possible;
I don't think they've added an extra pass just for this.

The difficulty I am aware of is using alloca in an expression that
is an actual argument to a function; but see the comment above.

|> 	3. Since the standard chose (probably for good reasons :)
|> 	    to omit alloca, porting code that uses it can be a real
|> 	    b**ch.  I once had to deal with some code that had called
|> 	    alloca() IN A LOOP (otherwise, I could have just replaced:
|> 	        alloca         with    malloc, saving ptr
|> 	        return         with    goto EXIT
|> 	    and added:
|> 	        EXIT: free(ptr); return;
|> 	    which is easy (in the absence of setjmp/longjmp, anyway).)

I still don't really see those good reasons.
I often call alloca in a loop; this is one of the reasons
why alloca is so useful.

Your porting experience does not indicate a deficiency of alloca
(other than it not being standard), but a weakness of ANSI C,
since the code is so much easier using alloca.

Konrad Schwarz