In article <ffgae6$1npr$1@gal.iecc.com>, johnl@iecc.com (John L) writes: |> |> The other is the influence of the IBM S/360. Its desigers didn't put |> in explicit stack hardware because they knew it was easy to do a stack |> in software if you have base and index registers. But its addressing |> modes have a 12 bit unsigned offset that is added to the base |> register. If a stack grows upward, a program either needs a frame |> register separate from the base register to address local variables, |> or else use extra instructions to simulate negative offsets. If the |> stack grows down, locals are at positive offsets from the stack |> pointer. Most (all?) modern computers have signed offsets so it'd |> work either way, but once you're used to a programming style, why |> mess with it? 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. Regards, Nick Maclaren.
Direction of Stack Growth
Started by ●October 21, 2007
Reply by ●October 21, 20072007-10-21
Reply by ●October 21, 20072007-10-21
On 2007-10-21, John L <johnl@iecc.com> wrote:> I see two motivations for the switch in modern computers to stacks > that grow downward. One was the use of programming techniques that > used heap storage in a fixed address space, which made it attractive > to have the heap and stack grow toward each other.I don't see how that results in a preference for a downward growing stack. It just means that the heap and stack need to grow in opposite directions -- it doesn't matter which grows up and which grows down. -- Grant Edwards grante Yow! Please come home with at me ... I have Tylenol!! visi.com
Reply by ●October 21, 20072007-10-21
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. -- Grant Edwards grante Yow! Are we THERE yet? at My MIND is a SUBMARINE!! visi.com
Reply by ●October 21, 20072007-10-21
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.
Reply by ●October 21, 20072007-10-21
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. > 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.I agree with others that the direction does not matter. You can prove this if you take your preferred scheme (up or down) and invert the address bits. An 'up' scheme becomes a 'down' scheme and vice versa, but nothing else changes. It still works as well. Regards, John
Reply by ●October 21, 20072007-10-21
Elcaro Nosille wrote:> 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.Wouldn't it be just as easy to have SP point at the current "top", using pre-increment and post-decrement addressing? -- glen
Reply by ●October 21, 20072007-10-21
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.If you don't do relocation, and machines come with different amounts of memory all starting at zero, then it is convenient to load programs near the bottom of memory. Note, though, that the 8080 starts with the PC at 0, while the 8086 (and other x86 machines) start near the top. The interrupt vectors for real mode x86 start at 0, though. For an 8080 system with ROM at high addresses and RAM at low addresses, starting with the PC at zero was not convenient. The solution was special logic to map ROM at 0 for the first few clock cycles, long enough to jump to a higher address. With x86 and segment registers, there isn't such a big advantage to starting at low memory, but x86 was designed to maintain 8080 source compatibility. (You could reassemble 8080 assembly code to run on an 8086.) It might be that the 8080 got its decrementing stack from the PDP-11, and later microprocessors from the 8080. -- glen
Reply by ●October 22, 20072007-10-22
John L 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. > > Beginning of what? The earliest computer I used that had hardware > stack support was the PDP-6, designed circa 1963, and its stacks grew > upwards. The B5000 which was designed around the same time or > slightly earlier also had upward growing stacks. > > I see two motivations for the switch in modern computers to stacks > that grow downward. One was the use of programming techniques that > used heap storage in a fixed address space, which made it attractive > to have the heap and stack grow toward each other. (Back in the 60s > memory was so valuable that you laid it all out when you wrote your > program, and the stack was just one of the areas you laid out.) > > The other is the influence of the IBM S/360. Its desigers didn't put > in explicit stack hardware because they knew it was easy to do a stack > in software if you have base and index registers. But its addressing > modes have a 12 bit unsigned offset that is added to the base > register. If a stack grows upward, a program either needs a frame > register separate from the base register to address local variables, > or else use extra instructions to simulate negative offsets. If the > stack grows down, locals are at positive offsets from the stack > pointer. Most (all?) modern computers have signed offsets so it'd > work either way, but once you're used to a programming style, why > mess with it?How about some attribution? I see posts in date order -- my thread mechanism is temporarily kaput -- and If I hadn't recognized my deathless prose, I would have been boorishly unresponsive. In the beginning of the microprocessor revolution, when the more prescient among us recognized that front-panel switches on computers would not be around for long, and that the PC would have to preload at powerup. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 22, 20072007-10-22
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.> This is all without virtual storage (dynamic address translation), > and a single task (no need to leave memory for anyone else).Yes. Computers were like that once. ... Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 22, 20072007-10-22
Nick Maclaren wrote:> In article <ffgae6$1npr$1@gal.iecc.com>, johnl@iecc.com (John L) writes: > |> > |> The other is the influence of the IBM S/360. Its desigers didn't put > |> in explicit stack hardware because they knew it was easy to do a stack > |> in software if you have base and index registers. But its addressing > |> modes have a 12 bit unsigned offset that is added to the base > |> register. If a stack grows upward, a program either needs a frame > |> register separate from the base register to address local variables, > |> or else use extra instructions to simulate negative offsets. If the > |> stack grows down, locals are at positive offsets from the stack > |> pointer. Most (all?) modern computers have signed offsets so it'd > |> work either way, but once you're used to a programming style, why > |> mess with it? > > 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.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. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
