kirchner@informatik.uni-kl.de (Reinhard Kirchner) (12/05/90)
There was a discussion in at.folklore.computers about why stacks are
growing downwards, not up as would seem natural. Since this
is clearly an architectural issue I am posting my experiences about
this to comp.arch as well as alt.folklore.computers.
From the operating system point of view the stack my grow in either
direction, there is no preference ( I think ). Detection of overflow
my be simpler in one direction, but thats all.
Stack and heap should always grow in opposite directions, so you
can allocate one pool of memory for both without any fixed size for one.
Now the architectural ( instruction set / registers ) problems:
I run into them when I designed a virtual machine for pascal with
numeric extensions ( the famous Pascal-SC, now even more extended and
called Pascal-XSC ) about 13 years ago ....
The name of this architecture was ( and is ) KL/P, since we are here
in KaisersLautern, and it was for Pascal, and every real computer has a '/' ...
How are the choices:
a. Stack growing upward
a1 -Stackpointer pointing to the first free byte
a2 -SP pointing to the last byte
a3 -SP pointing to the TOP-object and keeping its length somewhere in
a special register
b. Stack growing downward
b1 -SP pointing to the last byte which is also adress of Top-object
b2 -SP pointing to first free byte
Now we not only have to handle the stack, but also to adress items in it,
like parameters, locals, function results etc. Therefore we need some
base-addresses, one per lexical level, which may reside in baseregisters
or in linked stackframes. Anyway, if this base-point is between params and
locals we need +/- adresses, otherwise only one direction.
If we use baseregisters we need these also for adressing elements of records
( structures ), and since these are referenced by there first byte the
offset in this case must be positive.
Looking at the stack alone gives a clear preference of b1 since top is a
very often needed address. In all other cases we have to compute addresses
to access top.
No using a base address to some point makes it difficult:
When designing KL/P I had to find a compact encoding for small offsets,
so I could not deal with a sign bit. This forced me to positive offsets.
With a b1-stack I had to address over all locals to find parameters and
function results. Now in a numerical environment locals, parameters and
even function-results are often quite large vectors or matrices.
So I decided to use a a1-stack. Our first interpreter was on a Z80, the
handling was tricky anyway and I did not want to use the z80-Stack because
this was needed for the interpretation, and having z80-data and kl/p-data
mixed seemed a reliability issue....
From today and much more experience I must say:
I should have used the z80-stack ( b1 ), and should looked for a solution
to the positive-offset-problem, perhaps by additional address-modes etc.
Using the z80-stack would have given a lot of performance, this would
have outweighted the trouble.
So far the story of my stack
R. Kirchner
Univ. Kaiserslautern Germany
Computer Science
kirchner@uklirb.informatik.uni-kl.de
kinf89@dkluni01.bitnet