Direction of Stack Growth

glen herrmannsfeldt wrote:

> Walter Banks wrote:
> 
>> It doesn't matter much for subroutine return stack.
> 
> 
>> For argument passing a stack that grows downwards may
>> have some advantages. The SP in some cases may be used
>> as a index register for stack access or passed to a index
>> register for stack access and all of these accesses will
>> have a positive offset.
> 
> 
> Many systems now access arguments as positive index off
> the stack pointer, and local variables as negative
> index off the stack pointer.  (or frame pointer.)

sorry, no way with hardware stack pointer. Do not forget that there 
are uncontrollable events like interrupts, so stack should be 
completely "down" all the time - there is no need for negative 
indexes. If you use frame pointer - then yes? but you pay wit extra 
register and "entry" code.

Archi

robertwessel2@yahoo.com wrote:
> On Oct 22, 7:11 pm, Randy Yates <ya...@ieee.org> wrote:
>> Steve Underwood <ste...@dis.org> writes:
>>> There are various machines where there program counter doesn't
>>> actually count at all, but each instruction points to the next. Most
>>> microcoded systems do that, but a few higher level programmable
>>> machines have done so as well.
>> A linked list of instructions?
> 
> 
> The IBM 650, for example, did just that.  Of course instruction words
> were stored on disk.  A key optimization was to arrange them so that
> the next instruction (as defined by the link field) would be in
> position for the head to read it with minimal latency after the
> execution of the prior instruction had finished.
> 
> Another non-traditional program counter design is to use an LFSR
> rather than a counter, so that consecutive instructions are actually
> in a sequence defined by a pseudo-random number generator.  That has
> the disadvantage of making at least one location unreachable (assuming
> a maximum period LFSR), not to mention making a complete hash* of your
> address space, but has the advantage that the LFSR can be
> significantly smaller and faster than an actual adder.  The TMS1000
> microcontrollers did that, for example.
> 
> 
> *pun fully intended
> 
I'd forgotten that one. Some modern mixed signal chips could probably 
benefit from that. Often the biggest part of the digital noise pollution 
in the analogue sections is due to the substantial current flows 
associated with code loop related address line patterns. Long ago I 
scrambled the addresses in circular buffers built from multiple devices, 
to reduce these effects. I tried to do something similar to be 
reasonably tolerant of dead rows or columns in RAMs used for voice 
messages, but it worked out really messy. I ended up using diagonal 
addressing there.

Steve

>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.

For reasons I have never been able to figure out, even though the
arithmetic on the 704 was sign/magnitude, indexing did an unsigned
subtract of the index register from the base address to get the
effective address.  If they didn't store arrays backwards, they'd have
had to negate any computed index values before using them.

The 704 had three index registers numbered 1, 2, and 4.  If you
specified a register number with more than one bit set, it or'ed them
before subtracting.  Cool though this feature was, in later computers
they came to their senses and provided 7 separate registers.

>>> A linked list of instructions? 

>And you optimized your program by placing the instructions at
>the appropriate places on the magnetic drum ...

Drum?  Our Packard Bell 250 (the original PB which later sold its
computer division to Raytheon, not the Korean company that bought the
name out of bankruptcy decades later) used magnetostrictive delay
lines.  By default it executed instructions in sequence but that was
really slow since it meant one instruction per cycle of the delay
line.  There was a bit in each instruction that said to pick up the
next instruction from the location after the operand, which could be a
lot faster.  We tended to write out our programs on big pieces of
paper.

R's,
John

Archi wrote:
(I wrote)

>> Many systems now access arguments as positive index off
>> the stack pointer, and local variables as negative
>> index off the stack pointer.  (or frame pointer.)

> sorry, no way with hardware stack pointer. Do not forget that there are 
> uncontrollable events like interrupts, so stack should be completely 
> "down" all the time - there is no need for negative indexes. If you use 
> frame pointer - then yes? but you pay wit extra register and "entry" code.

Most now have a separate stack for interrupts and other system
functions, pretty much needed for any protected mode system.

I do remember from the 8080 days someone working on the
design of a terminal.  It was found that the fastest way to
clear the screen memory was to point the stack pointer at
one end of the buffer and push blanks.  Mysterious characters
kept appearing on the screen, though, which turned out to be
due to interrupts during the clear loop.

-- glen

On Oct 23, 11:33 am, glen herrmannsfeldt <g...@ugcs.caltech.edu>
wrote:
> Archi wrote:
>
> (I wrote)
>
> >> Many systems now access arguments as positive index off
> >> the stack pointer, and local variables as negative
> >> index off the stack pointer.  (or frame pointer.)
> > sorry, no way with hardware stack pointer. Do not forget that there are
> > uncontrollable events like interrupts, so stack should be completely
> > "down" all the time - there is no need for negative indexes. If you use
> > frame pointer - then yes? but you pay wit extra register and "entry" code.
>
> Most now have a separate stack for interrupts and other system
> functions, pretty much needed for any protected mode system.
>
> I do remember from the 8080 days someone working on the
> design of a terminal.  It was found that the fastest way to
> clear the screen memory was to point the stack pointer at
> one end of the buffer and push blanks.  Mysterious characters
> kept appearing on the screen, though, which turned out to be
> due to interrupts during the clear loop.
>
> -- glen

Check this out.
http://kstruct.com/2007/04/16/interview-questions-stack-direction/

Interesting :)
1) The author claims as below in that link -
 "Wikipedia tells me that most modern OSes grow the stack down which
is odd given the security advantages of doing it up."
Is that true or some kind of wrong information in internet ?

2) But i liked the 'C' program that helps in finding the direction of
stack growth.
3) I also like the shell script mentioned in the link ->
http://www.splode.com/~friedman/software/scripts/src/stack-direction

Thx in advans,
Karthik Balaguru

Nick Maclaren wrote:
> It's the efficient use of a small amount of memory that is the
> issue.  But I agree that it is a pretty marginal point, because
> a decent loader can put the initial stack pointer at the top of
> the code.

I have seen (i.e. written) exactly one program where the direction of 
stack growth made a crucial difference:

On x86 with a very limited register set and downward growing stacks, I 
once needed to process an array of (register-sized) words, but didn't 
have enough registers to hold all the critical variables.

At that point I realized that I could decrement the stack pointer by the 
size of the chunks to be processed, load the array into this area, and 
then use "pop reg" to retrieve each array element in order.

This freed up the crucial extra register, and had the nice side-effect 
of keeping the code size small, since POP is a single-byte opcode. :-)

It does blow away any kind of return stack cache of course, but that 
doesn't matter when I could handle a full L1 cache worth of data in each 
iteration.

Terje
-- 
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

Steve Underwood wrote:
> I've seen that elsewhere, but I've never seen a machine with a 
> decrementing program counter. I bet there must be one somewhere. Every 
> other strange combination has been used.
> 
> There are various machines where there program counter doesn't actually 
> count at all, but each instruction points to the next. Most microcoded 
> systems do that, but a few higher level programmable machines have done 
> so as well.

"The Story of Mel":

<http://catb.org/jargon/html/story-of-mel.html>

Here's a relevant quote:

> The new computer had a one-plus-one
> addressing scheme,
> in which each machine instruction,
> in addition to the operation code
> and the address of the needed operand,
> had a second address that indicated where, on the revolving drum,
> the next instruction was located.

Terje
-- 
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

In article <XvmdnaRhB9sU_oDanZ2dnUVZ_o-mnZ2d@speakeasy.net>,
rpw3@rpw3.org (Rob Warnock) writes:
|> 
|> Don't forget, DEC did it *both* ways! The PDP-10's hardware stack
|> grew "up"; the PDP-11's grew "down". The overlap in the lifecycle
|> of those two product lines was quite considerable. In fact, many
|> later PDP-10s used PDP-11s as front-end processors, so you even had
|> both ways in one system!  ;-}

Oh, indeed.  Now, why the PDP-11 should have disproportionately more
influence on computer scientists (and this is not the only respect),
I leave to the sociologists.


Regards,
Nick Maclaren.

Terje Mathisen wrote:
> Steve Underwood wrote:
>> I've seen that elsewhere, but I've never seen a machine with a 
>> decrementing program counter. I bet there must be one somewhere. Every 
>> other strange combination has been used.
>>
>> There are various machines where there program counter doesn't 
>> actually count at all, but each instruction points to the next. Most 
>> microcoded systems do that, but a few higher level programmable 
>> machines have done so as well.
> 
> "The Story of Mel":
> 
> <http://catb.org/jargon/html/story-of-mel.html>
> 
> Here's a relevant quote:
> 
>> The new computer had a one-plus-one
>> addressing scheme,
>> in which each machine instruction,
>> in addition to the operation code
>> and the address of the needed operand,
>> had a second address that indicated where, on the revolving drum,
>> the next instruction was located.
> 
> Terje

If anecdotes are your only exposure to that kind of programming, you've 
lead a sheltered life. :-) Much is still coded for specialist machines 
where there is no real program counter, and every instruction points to 
the next. It makes patches wonderfully arcane :-)

Back in the good old days, when AMD was the king of the DSP chip makers, 
practically all DSP programming was done that way (and it took a lot of 
AMD chips to make one machine).

Steve