Re: GNAT & Unconstrained Arrays

Re: GNAT & Unconstrained Arrays

[Richard Kenner]

In article <CE1vHy.4C4@inmet.camb.inmet.com> stt@spock.camb.inmet.com (Tucker T
aft) writes:
>The Intermetrics Ada compilers generally use a "secondary stack" for
>objects whose size is not known at compile-time, as well as for
>returning from functions with unconstrained result subtypes.
>It has the advantage over "alloca"-based approaches (where the primary
>stack is used) by being more portable, by allowing the primary stack frame
>to be fixed size (thereby allowing the stack and frame pointers to be
>the same register on some targets), and by allowing secondary stack release 
>to be postponed on function return

We discussed the secondary stack approach and concluded it didn't buy
us much, but perhaps we should revisit it.  We don't see any
significant advantage of using it for variable-sized objects in our
environment.  The main advantage you cite is portability over alloca,
but, in fact, the GCC backend supports alloca for all targets, so it's
as portable as we need it to be.  Your point that using alloca
requires a separate frame and stack pointer is valid, but as you say,
some targets require this anyway for debugging (and hence exceptions).
My feeling is that functions that have varible-sized objects are
likely to be complex enough that the slight efficiency loss in the
extra register isn't enough to compensate for the fact that allocating
and releasing primary stack is just a few instructions vs. probably
calls for a secondary stack (certainly you'd have to get its address
from the per-task data).

Also, if the GNAT front end does nothing special, GCC will use alloca
for variable-sized objects (recall that this is an extension the FSF
made to the C language in GNU C), while using a secondary stack would
mean we'd have to do the allocation ourselves.

However, using the secondary stack for unconstrained return values is
certainly a possibility.  What we don't see is how it solves the
trickiest problem: when to release the memory.  We certainly can defer
it until the calling function exits, but it might not ever exit.  It
might well call a function returning an unconstrained array inside a
loop.  Besides, as I say, we need to be able to support finalizations
which are required to be done at the right time (i.e., right after the
statement), so that forms a natural place to free primary stack memory
just as easily as the secondary stack memory.  Since we think most
unconstrained values are small, we expect to be able to avoid heap
allocation by passing a 4K block from caller to callee.

Are there any advantages to a secondary stack in our environment that
we missed?

Re: GNAT & Unconstrained Arrays

[Robert Firth]

In article <CE1vHy.4C4@inmet.camb.inmet.com> stt@spock.camb.inmet.com (Tucker T
aft) writes:

>The Intermetrics Ada compilers generally use a "secondary stack" for
>objects whose size is not known at compile-time, as well as for
>returning from functions with unconstrained result subtypes.
>A secondary stack is simply a per-task mark/release heap.

I have used exactly this system in two language implementations, and
strongly recommend it.

Some advantages, briefly:

(a) the primary stack size is known at the function level at compile
    time.  This not only saves a register, it simplifies both variable
    addressing and variable allocation.  For example, you don;t have
    to float simple variables out of inner blocks.

(b) the register you save can be the secondary stack pointer, and the
    mark/allocate/release then becomes simple open code

(c) the secondary stack is per task.  You don't have to worry about
    interrupts and task context switches during variable allocations -
    NEW must still implement mutual exclusion (or hairy tricks), but
    nothing else has to

(d) within a task, you have substantial gains in data locality

(e) you have much more freedom when and how to implement the release,
    since you know that the allocation is (almost) strictly LIFO and
    contiguous.  For example, you can release all the dynamic memory
    on function exit with one instruction, since you know there has
    been no task interleaving fragmenting a global heap.

In my humble opinion, putting local objects onto a global heap almost
always causes more trouble than it's worth, and leads to a series of
ever hairier, more dubious, and less maintainable hacks.

Robert Firth