Direction of Stack Growth

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

Reply to
John L
Loading thread data ...

In article , snipped-for-privacy@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.

Reply to
Nick Maclaren

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

R's, John

Reply to
John L

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.

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.

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

formatting link
snipped-for-privacy@bytecraft.com

Reply to
Walter Banks

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

Reply to
Ed Prochak

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

Reply to
Louis Krupp

...

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply to
Jerry Avins

In article , Jerry Avins 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.

Reply to
Nick Maclaren

In article , glen herrmannsfeldt writes: |> |> > Witness that System/360 stacks were normally upwards growing in the |> > 1960s and 1970s, and changed as the new generation of people with a |> > DEC background moved in during the 1980s. |> |> The S/360 that I used, running OS/360 and descendants, used |> linked lists for subroutine calling, register saving, and |> argument lists.

Er, no. The system API and initial IBM compilers did. There were a hell of a lot of third-party and customer compilers that did other things. We used about 20, and implemented perhaps 10 of those.

Regards, Nick Maclaren.

Reply to
Nick Maclaren

In article , Walter Banks writes: |> |> 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.

Whether you need a base register is an orthogonal point. Obviously, if you are comparing a downwards stack system that doesn't with an upwards one that does, the former comes out better.

At MOST, the extra cost of an upwards stack system is the use of one extra register during the actual call ONLY, one field in the stack frame, and two instructions per call (one each side of it). That can be significant, but I have never seen any evidence that it can be a major factor - and I have asked people for such evidence dozens of times.

Regards, Nick Maclaren.

Reply to
Nick Maclaren

Paul Keinanen wrote: (snip)

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

Reply to
glen herrmannsfeldt

Nick Maclaren wrote: (snip)

The S/360 that I used, running OS/360 and descendants, used linked lists for subroutine calling, register saving, and argument lists.

I haven't looked at what Linux/390 does, though.

-- glen

Reply to
glen herrmannsfeldt

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.) If you do signed offsets it doesn't seem it would matter much either way. Though local variables are usually accessed more than arguments.

-- glen

Reply to
glen herrmannsfeldt

(snip)

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

Reply to
glen herrmannsfeldt

Jerry Avins wrote: (snip)

Then I didn't explain it right. Consider a system with a program loader, which loads a program into memory and then starts executing that program. It can be loaded near the top of memory, and then started with a branch to its lowest address.

Yes. The disadvantage to what I wrote above is that the starting location is different depending on the installed memory. Many early machines came in only one size, but when more than one size was available the program had to be compiled and/or linked for that size if it was at the top. Starting at the bottom, the starting location would be independent of the memory size. (Once could build smaller systems with all the memory at high addresses, though.)

As I wrote in another post, the IBM 704 Fortran compiler stored arrays in decreasing order in memory. It might also be that programs started from the bottom, and memory for variables (static addressed) from the top. Note also the Fortran requirement that all COMMON blocks except blank COMMON have the same size in all program units. That allows them to be positioned in memory, with the unknown size blank COMMON at the end (one end or the other).

-- glen

Reply to
glen herrmannsfeldt

In article , glen herrmannsfeldt writes: |> |> > 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. |> |> The only time I see a connection between program counter direction |> and stack direction is when one wants to push instructions on |> the stack and execute them. There are programs that do that, |> but it isn't a good practice. Many now specifically don't allow |> execution on the stack.

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.

Regards, Nick Maclaren.

Reply to
Nick Maclaren

Nick Maclaren wrote: (snip regarding stack direction)

The only time I see a connection between program counter direction and stack direction is when one wants to push instructions on the stack and execute them. There are programs that do that, but it isn't a good practice. Many now specifically don't allow execution on the stack.

Loading programs from the bottom or top of memory does not necessarily imply the direction of the program counter. A system could load to the top of memory and start executing at the low address of the program it loaded. (It does help to know the size in advance, though.)

-- glen

Reply to
glen herrmannsfeldt

With the 8080, that was the only way to program output to an I/O address chosen at run time. A computed branch is done by pushing the target address onto the stack and executing RTS.

We know it's all possible. The question that guided development is "What is simplest?"

Jerry

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

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.

Steve

Reply to
Steve Underwood

That's all I was talking about.

Sheesh! The passions expressed in this thread remind me of the "toilet paper orientation" issue (over versus under).

--
%  Randy Yates                  % "She has an IQ of 1001, she has a jumpsuit
%% Fuquay-Varina, NC            %            on, and she's also a telephone."
 Click to see the full signature
Reply to
Randy Yates

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.