Direction of Stack Growth

>Yes, but then a push onto the stack would have to know the size of
>the element pushed before; i.e. there would be two operands of this
>push-operation - that's bulky and unnecessary.

Back in the 60s you always knew the size of the elements you pushed.
It was one word.

In article <ffii6t$1ij9$2@gal.iecc.com>, johnl@iecc.com (John L) writes:
|> 
|> >Yes, but then a push onto the stack would have to know the size of
|> >the element pushed before; i.e. there would be two operands of this
|> >push-operation - that's bulky and unnecessary.
|> 
|> Back in the 60s you always knew the size of the elements you pushed.
|> It was one word.

Yes.  Well, it might be several words, but it was always a fixed
number, known at compile-time.

Despite the fact that it is possible to implement, it is a damn-fool
idea to have a stack that is not unwindable fairly easily, because
the number of other problems it causes is legion.  And having stack
frames with a size that varies at run-time that cannot be found out
almost trivially are not easily unwindable.


Regards,
Nick Maclaren.

>The disadvantages of upwards-growing stacks are grossly overstated.

Agreed.  If you have variable size stack frames so you need separate
frame and base pointers anyway, they're nonexistent.

R's,
John

Nick Maclaren wrote:

> In article <471CC11C.604EBBDB@bytecraft.com>,
> Walter Banks <walter@bytecraft.com> writes:
> |>
> |> In  upward stacks SP at the start of a stack is used as a base address
> |> for local variables and is copied to RAM or an index register at run
> |> time. In RAM poor embedded systems this impacts RAM or index
> |> register usage. Except for this impact (which can be quite large in
> |> some cases) stack references are quite similar. A downwards-growing
> |> stack doesn't need the base saved and all of the offsets are SP
> |> related computed at compile time.
>
> Eh?  The former is true, with reservations (e.g. it is not true for
> any language that allows dynamically sized stack variables), but the
> latter is as true for upwards-growing stacks.  And the expense of
> one extra field in the stack frame is NOT 'quite large' except in
> dubiously structured codes - e.g. ones that use recursion to emulate
> iteration.

I stay with my comment , the impact can be quite large. Most of the
embedded systems I work are RAM poor with a limited register sets
making spilling off an index register (often the only one) for stack
variable access expensive. In an industry where 0.5% is a big number
Base pointers at any point in time represent an impact of several percent
of processor resources.

Dynamic variables in either implementation need run time information
on size available in the addition to base or SP. Base information alone
in the upward stack is not enough.


> Also note that, without such a chain, it becomes damn-near impossible
> to print backtraces without invoking a heavyweight, separate debugging
> mechanism.  Some of us regard diagnostic tools as things that should
> be provided in all environments.

Diagnostic tools are very important but it is also important for the
diagnostic tool to be separated from the application to eliminate
tool induced heisenbugs. This same separation makes it possible
to reliability ship (often millions) of copies of the application without
carrying the debug support with the code. The resulting application
will have improved battery life and lower EMI. Part of the price is
the need to use a heavyweight separate debugging system that
typically involves processor emulators and simulation. Many
times these run in parallel to provide detailed information on
application execution.

> The disadvantages of upwards-growing stacks are grossly overstated.
>

I would agree. Most processors that have upward stacks
do so with the instructions to support them.

Regards

--
Walter Banks
Byte Craft Limited
Tel. (519) 888-6911
Fax (519) 746 6751
http://www.bytecraft.com
walter@bytecraft.com

On Oct 22, 5:39 am, Elcaro Nosille <Elcaro.Nosi...@mailinator.com>
wrote:
> glen herrmannsfeldt schrieb:
>
> > Wouldn't it be just as easy to have SP point at the current
> > "top", using pre-increment and post-decrement addressing?
>
> Yes, but then push and pop would have to know the size of
> the element under the top, i.e. these operations would have
> two operands.

only if you were allowing different sizes. most of the time you push
and pop machine words. (IOW, on a 16bit machine you push/pop 2bytes,
on a 32bit machince it's 4bytes) actually the size can be implied in
the opcode

POPB/PUSHB  pop/push byte
POPW/PUSHW  pop/push word
POPD/PUSHD  pop/push double

So I do not agree it requires the size. I think you are talking about
the stack frame. The compiler that built the frame at the start of the
call, also tears it down at the end of the call. It knows how big it
is.

  Ed

Ed Prochak wrote:
> On Oct 22, 5:39 am, Elcaro Nosille <Elcaro.Nosi...@mailinator.com>
> wrote:
>> glen herrmannsfeldt schrieb:
>>
>>> Wouldn't it be just as easy to have SP point at the current
>>> "top", using pre-increment and post-decrement addressing?
>> Yes, but then push and pop would have to know the size of
>> the element under the top, i.e. these operations would have
>> two operands.
> 
> only if you were allowing different sizes. most of the time you push
> and pop machine words. (IOW, on a 16bit machine you push/pop 2bytes,
> on a 32bit machince it's 4bytes) actually the size can be implied in
> the opcode
> 
> POPB/PUSHB  pop/push byte
> POPW/PUSHW  pop/push word
> POPD/PUSHD  pop/push double
> 
> So I do not agree it requires the size. I think you are talking about
> the stack frame. The compiler that built the frame at the start of the
> call, also tears it down at the end of the call. It knows how big it
> is.

I don't think Glen was talking about stack frames.  I believe he was 
talking about pushing and popping elements that *could* be of different 
sizes.

How often this actually happens is a different question.

Louis

Nick Maclaren wrote:

   ...

> The disadvantages of upwards-growing stacks are grossly overstated.

Amen to that. Overstatement notwithstanding, the answer to the OP's 
question is slightly more than "That's the way it happened to evolve." 
Given an upwardly marching program counter and our natural propensity to 
avoid analyzing more than we need to, a downward marching stack pointer 
has a slight but ultimately controlling edge. The effect of Earth's 
gravity on Venus is also small, but Venus's diurnal period is locked to 
Earth. It doesn't take much influence to have a large effect.

Example: because most people are right handed, many implements are 
intended for right-handed use. Right-handed people become more right 
handed, while lefties often become more ambidextrous. Maybe that's 
related to why lefties seem to be smarter on average. (The number of 
left-handed Nobel Prize winners is disproportionately high.)

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

In article <F72dnQOzPdLonIDanZ2dnUVZ_v6rnZ2d@rcn.net>,
Jerry Avins <jya@ieee.org> writes:
|> 
|> > The disadvantages of upwards-growing stacks are grossly overstated.
|> 
|> Amen to that. Overstatement notwithstanding, the answer to the OP's 
|> question is slightly more than "That's the way it happened to evolve." 
|> Given an upwardly marching program counter and our natural propensity to 
|> avoid analyzing more than we need to, a downward marching stack pointer 
|> has a slight but ultimately controlling edge. ...

You also need to take the code+stack (i.e. no heap) model as given.
It was more that I was questioning.

But I agree that, given an upwardly marching program counter and the
simple code+stack model, a downward marching stack pointer has an
edge.


Regards,
Nick Maclaren.

Jerry Avins wrote:

(snip)

> If they really started at the top of memory, each chip would have to be 
> designed for a particular amount of RAM, or at least address a ROM 
> there. Hardware tricks -- at least incompletely decoded addressing for 
> high bits -- are in fact used. Even so, those processors start *near* 
> the virtual top and the program counters count up from there. That way 
> you get a few instructions to jump to the real start. Application code 
> starts at 0x200 in CP/M, even on processors that start high.

Intel x86 still starts at what is the top of memory in real mode.

Some models start with CS at X'F000' and PC at X'FFF0',
others with CS at X'FFFF' and PC '0000', either way the physical
address is X'FFFF0'.  An inconvenient hole in the address space
on machines starting with the 80286.

Otherwise, if you start with an address such as X'FFFFFFF0'
it will be near the end of addressable memory on all systems that
decode a subset of address bits.

-- glen

-- glen

Paul Keinanen wrote:
(snip)

> It depends how the stack pointer (or other general register) is
> updated. With register pre-decrement and post-increment access, it is
> natural to let the stack grow downwards, since the register will point
> to the newly pushed value. If the stack grows upwards, the stack would
> point to a useless (free) location of the stack and to access the last
> value, you would have to use an offset.

But a machine with a stack that grows upwards, and with register
post-decrement and pre-increment  would work just as well.
If it has index registers, you would want to be able to index down.

Note that the IBM 704, the first machine with Fortran, stored
arrays in memory in decreasing address order.  It seems that
was more convenient with the index registers and addressing
modes available.

-- glen