Grant Edwards wrote:> On 2007-10-22, Jerry Avins <jya@ieee.org> wrote: >> glen herrmannsfeldt wrote: >>> Jerry Avins wrote: >>>> karthikbalaguru wrote: >>>>> Why some processors have stack growing downwards and others have stack >>>>> growing upwards ? >>> (snip) >>> >>>> In the beginning, it was customary to start a peogram at or near the >>>> bottom of memory and start the return stack at or near the top. >>> I thought of that, but I didn't see why programs couldn't >>> load at the top and the stack grow from the bottom. >>> I suppose, though, that it helps not to need to do relocation, >>> if the load point is always the same. >> Programs must start low if the program counter is to count up. > > That's news to all of the processors that start with the PC at > the top of memory. It's trivial to load the program into the > top of memory and put a "jump" instrucation at 0xffff (or > wherever).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. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Direction of Stack Growth
Started by ●October 21, 2007
Reply by ●October 22, 20072007-10-22
Reply by ●October 22, 20072007-10-22
Grant Edwards wrote:> On 2007-10-22, Jerry Avins <jya@ieee.org> wrote: >> Grant Edwards wrote: >>> On 2007-10-21, glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote: >>> >>>>> In the beginning, it was customary to start a peogram at or >>>>> near the bottom of memory and start the return stack at or >>>>> near the top. >>>> I thought of that, but I didn't see why programs couldn't load >>>> at the top and the stack grow from the bottom. >>> That would work equally as well. >> You want the PC to autodecrement with each instruction fetch? > > No. You put a jump instruction at the top of memory that jumps > to the beginning of the program. Quite a few processors work > that way. > >> That might be confusing when debugging. > > I assume you're being sarcastic and don't really think that > loading a program into the top of the address space means that > the PC has to decrement during execution. Of the processors > I've used, more of them started execution at the top of memory > than at the bottom. Even though the program counters on all of > them incremented, they also had a cool new invention call the > "jump instruction".If the PC initializes to FFFF on a processor with 16 address bits, there's no room for a jump instruction. FFF0 is more usual. When as much stack space as possible is wanted and PCs count up, a simple approach is starting application code low and the stack high. If the program is loaded high, different length programs would either need to have different starting locations or waste space. You probably know all this and can certainly figure it out. I guess I'm grumpy this morning. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 22, 20072007-10-22
Elcaro Nosille wrote:> karthikbalaguru schrieb: > > > Hi, > > Why some processors have stack growing downwards > > and others have stack growing upwards? > > With downwards growing stacks you can address the "top" element of > the stack at address sp + 0 and this results often in smaller opodes > of the machine-instructions adressing that elements.This isn't always the case for downward stacks. For example the Freescale 68HC08 and S08 processors the SP points to the next available stack element making the "top" element at SP+1. This is not the only processor that does this. Regards -- Walter Banks Byte Craft Limited Tel. (519) 888-6911 Fax (519) 746 6751 http://www.bytecraft.com walter@bytecraft.com
Reply by ●October 22, 20072007-10-22
In article <471C995F.A7DF8071@bytecraft.com>, Walter Banks <walter@bytecraft.com> writes: |> 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. Sigh. Exactly the same is true for an upwards-growing stack, which is how we did it on the System/370 (with no negative offsets in indexing). The one exception that I know of is for some dialects of K&R C, but it isn't a problem for Algol 60, Algol 68, BCPL, Fortran, Pascal, ISO C/C++, etc. etc. Yes, particular designs may make a downwards-growing stack more natural, but that is a CONSEQUENCE of choosing that approach. Regards, Nick Maclaren.
Reply by ●October 22, 20072007-10-22
Nick Maclaren wrote:> In article <weCdnavEpohCtYHanZ2dnUVZ_oaonZ2d@rcn.net>, > Jerry Avins <jya@ieee.org> writes: > |> > |> I still think that the simple answer is that program counters count up > |> by design. My first useful computer had 1K of RAM, quickly augmented to > |> 4. My first disk-based system had 24K. With such systems, it's > |> convenient to start the stack at the top of memory and let it work down. > > Ah. You mean the model of JUST code and stack? For those, I agree, > but those stopped being important back in the 1950s. The resurgence > in the 1970s and 1980s was short-lived and not very important.They became important again starting with the 4004 and right through the 6809 and friends. Big processors naturally get attention, but I think their numbers pale compared to all the ones in vending machines, cars, scales of many sorts, and cell phones. I don't see that the resurgence was short lived.> I am pretty sure that this is yet another artifact of the way that DEC > was the dominating computer science supplier in the 1970s. Now, why > DEC did things the way they did, I don't know. > > 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.Maybe IBM profited from DEC's example? :-) Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 22, 20072007-10-22
In article <9tKdncEcFeKRNIHanZ2dnUVZ_hisnZ2d@rcn.net>, Jerry Avins <jya@ieee.org> writes: |> |> > Ah. You mean the model of JUST code and stack? For those, I agree, |> > but those stopped being important back in the 1950s. The resurgence |> > in the 1970s and 1980s was short-lived and not very important. |> |> They became important again starting with the 4004 and right through the |> 6809 and friends. Big processors naturally get attention, but I think |> their numbers pale compared to all the ones in vending machines, cars, |> scales of many sorts, and cell phones. I don't see that the resurgence |> was short lived. Yes and no. The implication that all of those use a stack, and none use any dynamically allocated data is false. I agree that it was true for many of those very small embedded systems, but the reason that I said that it wasn't important is the MODEL didn't have much effect on the wider world of IT. |> > I am pretty sure that this is yet another artifact of the way that DEC |> > was the dominating computer science supplier in the 1970s. Now, why |> > DEC did things the way they did, I don't know. |> > |> > 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. |> |> Maybe IBM profited from DEC's example? :-) Nah. It wasn't an IBM change, but was introduced specifically by computer scientists who knew everything. I spoke to some of them; they sounded like many people on this thread. When I suggested that they should actually LOOK at some existing products on the architecture they were designing for, they made it clear that they did not want to pollute their prejudices with facts. Regards, Nick Maclaren.
Reply by ●October 22, 20072007-10-22
nmm1@cus.cam.ac.uk (Nick Maclaren) writes:> Ah. You mean the model of JUST code and stack? For those, I agree, > but those stopped being important back in the 1950s. The resurgence > in the 1970s and 1980s was short-lived and not very important. > > I am pretty sure that this is yet another artifact of the way that DEC > was the dominating computer science supplier in the 1970s. Now, why > DEC did things the way they did, I don't know. > > 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 gov. legal action affected the discount educational institutions could get (between the 60s & 70s) minicomputer prices could fit into individual dept. budgets as opposed to institutional-wide large processor. there was some resurgence with introduction of 43xx (but a lot of those boxes went into commercial accounts ... some number with orders of multiple hundreds at a time) gov. legal action also resulted in the 23jun69 unbundling announcement http://www.garlic.com/~lynn/subtopic.html#unbundle which also marked starting to charge for (application) software.
Reply by ●October 22, 20072007-10-22
Nick Maclaren wrote:> In article <471C995F.A7DF8071@bytecraft.com>, > Walter Banks <walter@bytecraft.com> writes: > |> 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. > > Sigh. Exactly the same is true for an upwards-growing stack, > which is how we did it on the System/370 (with no negative > offsets in indexing).> The one exception that I know of is for some dialects of K&R C, > but it isn't a problem for Algol 60, Algol 68, BCPL, Fortran, > Pascal, ISO C/C++, etc. etc. > > Yes, particular designs may make a downwards-growing stack more > natural, but that is a CONSEQUENCE of choosing that approach.In data stacks the stack frame can be offset from the SP. Some processors allow the SP to used like an index register. 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. We have implemented compilers with both types of stacks. w..
Reply by ●October 22, 20072007-10-22
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. 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. |> We have implemented compilers with both types of stacks. And I have implemented run-time systems with both, primarily on a system with no negative offsets. Including getting quite large applications to run in 44 KB. Oh, and they displayed backtraces if they diagnosed a run-time error, too. The disadvantages of upwards-growing stacks are grossly overstated. Regards, Nick Maclaren.
Reply by ●October 22, 20072007-10-22
>I am pretty sure that this is yet another artifact of the way that >DEC was the dominating computer science supplier in the 1970s. Now, >why DEC did things the way they did, I don't know.It was the same time they gave us little-endian addressing. Perhaps it was just to do everyhing sdrawkcab. Early PDP-11s had a 64KB address space where you typically put the code at the bottom, so the model where the stack grows down toward the heap was reasonable. Later 11's had a larger physical address space but the per process space was still 64K.
