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? That might be confusing when debugging. 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
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). -- Grant Edwards grante Yow! Is it FUN to be at a MIDGET? visi.com
Reply by ●October 22, 20072007-10-22
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". -- Grant Edwards grante Yow! I've got a COUSIN at who works in the GARMENT visi.com DISTRICT...
Reply by ●October 22, 20072007-10-22
On 21 Oct 2007 21:25:48 GMT, nmm1@cus.cam.ac.uk (Nick Maclaren) wrote:>Actually, handling upwards-growing stacks on the System/360 was as >easy as downwards-growing ones, and you DON'T need a separate frame >pointer for most languages - but that doesn't deny your point. > >I lost track of the number of people I tried to explain the major >methods of doing it to, generally unsuccessfully. There was >definitely a belief (i.e. myth) that upwards-growing ones were >inefficient or even impossible and, as always, pointing out counter- >examples and explaining the techniques didn't kill the myth.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. On PDP-11 a sequence with downwards growing software stack would be MOV VAR1, -(R5) ; Push Var1 to top of stack (TOS) COM (R5) ; Do some operations on the value on the TOS ADD #5,(R5) ; Some more operations on TOS MOV (R5)+,VAR2 ; Pop value from stack With a stack growing upwards MOV VAR1, (R5)+ ; Push Var1 to top of stack ; R5 now points above the value pushed COM -2(R5) ; Do some operations on the value on the TOS ADD #5,-2(R5) ; Some more operations on TOS MOV -(R5),VAR2 ; Pop value from stack This is 2 words (4 bytes) longer than the previous example. When other locations are accessed, the offset penalty applies to both methods, but with processors with several offset sizes, the offset may be shorter, if the (short) offset is handled as an unsigned value. In processors with pre-increment and post-decrement addressing modes, it would be natural to let the stack grow upwards. Paul
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. > With upwards growing stacks you either would have to know the size > of the top element when pushing another element to the stack or you > would have to address the top element at sp - N, you you couldn't > address it with an offset-less instruction.Sure you could! You just need a pre-increment stack pointer.> So it's best to grow stack downwards: you can address the "top" > element without an offset and you don't have to know its size to > push another element on the stack.Nope, see above. Terje -- - <Terje.Mathisen@hda.hydro.com> "almost all programming can be viewed as an exercise in caching"
Reply by ●October 22, 20072007-10-22
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. 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. Regards, Nick Maclaren.
Reply by ●October 22, 20072007-10-22
Terje Mathisen schrieb:>> 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. >> With upwards growing stacks you either would have to know the size >> of the top element when pushing another element to the stack or you >> would have to address the top element at sp - N, you you couldn't >> address it with an offset-less instruction.> Sure you could! > You just need a pre-increment stack pointer.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.
Reply by ●October 22, 20072007-10-22
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.
Reply by ●October 22, 20072007-10-22
On Oct 22, 4:49 am, Elcaro Nosille <Elcaro.Nosi...@mailinator.com> 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. > With upwards growing stacks you either would have to know the size > of the top element when pushing another element to the stack or you > would have to address the top element at sp - N, you you couldn't > address it with an offset-less instruction. > So it's best to grow stack downwards: you can address the "top" > element without an offset and you don't have to know its size to > push another element on the stack.Interesting :):) So, downward stack growth is used because it involves less complexities during implementation w.r.t knowing the size and having a check on it everytime. But, upward stack growth involves those complexities while implementation. Thx, Karthik Balaguru
Reply by ●October 22, 20072007-10-22
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. Related to stack access assuming a downwards stack is the question of should the SP be decremented and used as an index or used as an idex then decremented when data is put on it. When the SP is decremented and then used as a index the SP is pointing directly at the last item on the stack an advantage on some processors. I know of several processors that the endian of the subroutine stack is reversed from the natural endian of the processors. This requires separate math implementation for modifications to subroutine stack contents in high level language tools. Regards -- Walter Banks Byte Craft Limited Tel. (519) 888-6911 Fax (519) 746 6751 http://www.bytecraft.com walter@bytecraft.com karthikbalaguru wrote:> Hi, > > Why some processors have stack growing downwards and others have stack > growing upwards ? > Any advantages/disadvantages w.r.t both these designs. > Which is the best model ? > > I serached the internet, but i did not find a good link that explains > these stuffs in detail. > > Thx in advans, > Karthik Balaguru