firth@sei.cmu.edu (Robert Firth) (10/05/87)
The discussion on stacks and parameter pushing seems to me
to have confused several issues. This post is intended to
be an attempt to separate them.
One starting point is the familiar parameter-passing sequence,
found for instance on the Vax-11:
p(a1,a2,...an) =>
push an
push an-1
...
push a1
build call frame
invoke p
Within p(f1,f2...fn) we access the formals in order at increasing offsets
from the call frame.
This example shows several things
(a) The direction in which the stack grows is irrelevant. The 'push'
might be an autodecrement or an autoincrement. The key fact is
not the stack direction, but the fact that the call frame is built
AFTER the parameters have been pushed. If the lower-numbered formals
are closer to the call frame, then evidently the parameter list must
be built in reverse order.
(b) Even though the actuals are pushed in reverse order, they can be
evaluated in any order. If the actual is simple (as is usually
the case), this is trivial. If an actual is complex, one has to
evaluate it into a register and subsequently push the register.
(c) Alternatively, one can always move the stack pointer N words and then
evaluate the parameters left-to-right, filling the holes in the stack.
Why would one WANT the parameter list this way round? If the number of
actuals is known at compile time (well, to be picky, if their SIZE is
known) then the order of the list is irrelevant. In the above example,
we address fi at (frame pointer)+(i*4) or whatever; but we could
equally well push the parameters in direct order and address fi at
(frame pointer)+(n-i+1)*4. The underlying reason for having f1 at a
fixed position relative to the call frame, is to permit P to take a
dynamically variable number of actuals.
Even then, there are alternatives. For example, one could always pad the
actual parameter list to some fixed maximum (Ada permits this technique).
Not very efficient, but perhaps reasonable given that variadic procedures
are quite rare.
In addition, there is a different stack building technique. called an "open
stack" that is efficient for variadic procedures and allows the parameter
list to be built left to right. It works like this:
build call frame
load a1
load a2
...
load an
invoke p
In other words, the actuals appear AFTER the call frame. Clearly, this
has f1 at a fixed offset relative to the call frame, and also allows the
caller to pass as many actuals as it wants. Incidentally, it is very
easy to add to this design the optimisation of passing the first few
actuals in registers - the caller leaves a hole in the stack; the called
procedure stores the registers there if necessary (ie if there is an inner
call or if the address of a formal is taken).
Finally, just to remind you that a "stack" is a programming technique
for the allocation of storage with LIFO extent semantics; it is not
necessarily a hardware feature. Even if the engineers gave you an
autodecrement address mode, it still might be expedient to build the
software stack yourself, somewhere else.