Re: Direction of Stack Growth - Embedded

This is a discussion on Re: Direction of Stack Growth - Embedded ; On Oct 22, 11:32 am, Paul Keinanen wrote: > On 21 Oct 2007 21:25:48 GMT, n...@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 ...

+ Reply to Thread
Page 1 of 2 1 2 LastLast
Results 1 to 20 of 38

Thread: Re: Direction of Stack Growth

  1. Re: Direction of Stack Growth

    On Oct 22, 11:32 am, Paul Keinanen wrote:
    > On 21 Oct 2007 21:25:48 GMT, n...@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.
    >


    Reading through this and thinking about heap mechanism. I got some
    query.
    Why do we need the stack as the heap appears flexible ?

    Thx in advans,
    Karthik Balaguru


  2. Re: Direction of Stack Growth

    karthikbalaguru wrote:

    ...

    > Reading through this and thinking about heap mechanism. I got some
    > query.
    > Why do we need the stack as the heap appears flexible ?


    Manipulating a heap requires software. Some stacks are implemented
    entirely in hardware (PUSH, POP; CALL, RETURN). It would be very hard to
    create or maintain a heap on a machine with no stack.

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

  3. Re: Direction of Stack Growth


    glen herrmannsfeldt writes:
    > IBM S/360 and S/370 don't have a stack. CALL and RETURN are done
    > through a linked list that also includes space to save the registers.
    > Called routines are expected to save and restore most of the general
    > registers. The calling convention used by OS/360 and many of the
    > supported high-level languages has the calling routine supply a 72
    > byte save area addressed in R13. R14 is the return address, and R15
    > is the address of the routine being called. The called routine then
    > saves registers 14 through 12 in the save area addressed by R13,
    > arranges its own save area as the next element in a linked list.
    > Traditionally many assembly and Fortran programs used a static save
    > area (no recursion). Languages that allow recursion dynamically
    > allocate a save area along with space for local variables.


    q&d conversion of old greencard ios3270 to html
    http://www.garlic.com/~lynn/gcard.html

    call/save/return conventions
    http://www.garlic.com/~lynn/gcard.html#50

  4. Re: Direction of Stack Growth

    Jerry Avins wrote:

    > karthikbalaguru wrote:


    >> Reading through this and thinking about heap mechanism. I got some
    >> query. Why do we need the stack as the heap appears flexible ?


    > Manipulating a heap requires software. Some stacks are implemented
    > entirely in hardware (PUSH, POP; CALL, RETURN). It would be very hard to
    > create or maintain a heap on a machine with no stack.


    IBM S/360 and S/370 don't have a stack. CALL and RETURN are done
    through a linked list that also includes space to save the registers.
    Called routines are expected to save and restore most of the
    general registers. The calling convention used by OS/360 and
    many of the supported high-level languages has the calling routine
    supply a 72 byte save area addressed in R13. R14 is the return
    address, and R15 is the address of the routine being called.
    The called routine then saves registers 14 through 12 in the save
    area addressed by R13, arranges its own save area as the next
    element in a linked list. Traditionally many assembly and Fortran
    programs used a static save area (no recursion). Languages that
    allow recursion dynamically allocate a save area along with space
    for local variables.

    One inconvenience of a stack is that someone has to create the
    stack, and so that routine has to be different. For OS/360,
    the calling convention described is similar to that used
    by the OS to call your program. It is then more convenient
    than other systems to load a program into memory and call it
    without a question of who owns the stack.

    For small allocations, though, the stack likely has less overhead.

    -- glen


  5. Re: Direction of Stack Growth


    In article ,
    glen herrmannsfeldt writes:
    |> Jerry Avins wrote:
    |> > karthikbalaguru wrote:
    |>
    |> >> Reading through this and thinking about heap mechanism. I got some
    |> >> query. Why do we need the stack as the heap appears flexible ?
    |>
    |> > Manipulating a heap requires software. Some stacks are implemented
    |> > entirely in hardware (PUSH, POP; CALL, RETURN). It would be very hard to
    |> > create or maintain a heap on a machine with no stack.
    |>
    |> IBM S/360 and S/370 don't have a stack. CALL and RETURN are done
    |> through a linked list that also includes space to save the registers.

    Specifically, several compilers generated code that used 'GETMAIN R'
    to allocate the stack frame one procedure entry. Those compilers
    used an underlying 'heap' mechanism for the call stack.

    Been there - done that :-)


    Regards,
    Nick Maclaren.

  6. Re: Direction of Stack Growth

    >Specifically, several compilers generated code that used 'GETMAIN R'
    >to allocate the stack frame one procedure entry. Those compilers
    >used an underlying 'heap' mechanism for the call stack.
    >
    >Been there - done that :-)


    Wow, was that slow. I know that Algol F did that, at least until you
    installed the patches from (as I recall) Princeton that suballocated
    bigger GETMAIN areas. What else did?


  7. Re: Direction of Stack Growth

    Nick Maclaren wrote:

    > In article ,
    > glen herrmannsfeldt writes:


    (snip)

    > |> IBM S/360 and S/370 don't have a stack. CALL and RETURN are done
    > |> through a linked list that also includes space to save the registers.


    > Specifically, several compilers generated code that used 'GETMAIN R'
    > to allocate the stack frame one procedure entry. Those compilers
    > used an underlying 'heap' mechanism for the call stack.


    It is supposed to be best to have one routine do larger GETMAIN
    calls and parcel them out. Otherwise, direct calls to GETMAIN
    should work just fine.

    Most of my early assembly was Fortran callable so I didn't have
    to worry about such things. (Static save areas!)

    > Been there - done that :-)


    -- glen


  8. Re: Direction of Stack Growth


    glen herrmannsfeldt writes:
    > IBM S/360 and S/370 don't have a stack. CALL and RETURN are done
    > through a linked list that also includes space to save the registers.
    > Called routines are expected to save and restore most of the
    > general registers. The calling convention used by OS/360 and
    > many of the supported high-level languages has the calling routine
    > supply a 72 byte save area addressed in R13. R14 is the return
    > address, and R15 is the address of the routine being called.
    > The called routine then saves registers 14 through 12 in the save
    > area addressed by R13, arranges its own save area as the next
    > element in a linked list. Traditionally many assembly and Fortran
    > programs used a static save area (no recursion). Languages that
    > allow recursion dynamically allocate a save area along with space
    > for local variables.


    re:
    http://www.garlic.com/~lynn/2007q.html#65 Direction of Stack Growth

    in the os/360 convention called routine only needs its own savearea if
    it is planning on calling other routine(s). a routine that doesn't make
    any calls ... won't need its own savearea. a routine is only
    allocating/chaining savearea (on entry), when it is calling other
    routine(s) (for their use).

    original/early cp67 kernel allocated 100 (contiguous) "saveareas" at
    boot initialized/managed as push/pop list. all internal kernel
    call/returns were done via svc (supervisor call) interrupt which would
    allocate/deallocate a savearea (from push/pop list). the called routine
    was still responsible for "saving" registers in the (recently) allocated
    savearea. when the 100 "savearea" were exhausted ... system failed. on
    entry, the pointer to the "active" savearea was in register 13 ... as
    per os/360 convention.

    early on (as undergraduate) in the 60s, i made a number of cp67 kernel
    modifications:

    several "called" kernel routines were "closed" ... i.e. they didn't
    call to any other routines. for these i changed the calling sequence
    from a supervisor call interrupt to (more familiar) BALR ... and these
    called routines, saved (calling routines) registers (on entry) in a
    single, kernel-wide savearea (actually in "page zero" ... so it
    was a per processor, kernel-wide savearea ... one for every processor
    in a multiprocessor configuration).

    if the initial 100 saveareas were exhausted (actually any time available
    saveareas were exhausted) ... it would savange some storage and
    replenish the list with another block of saveareas.

    .....

    the change to dynamicly extend kernel saveareas then complicated
    standard cp67 kernel failure analysis ... since it had been possible to
    examine all extent active and pending process indications by examining
    the fixed (location) preallocated, contiguous 100 saveareas.

    these eventually shipped in standard cp67 product.

    also as undergraduate i did an enhancement that moved some number of
    kernel routines out of fixed kernel storage and made them pageable. this
    required a little slight of hand ... while cp67 supported virtual memory
    and ran all of its virtual machines in virtual address spaces ... the
    cp67 kernel ran in "real addressing" (non virtual addressing
    mode). while the "pageable" kernel routines were fetched into memory and
    removed from memory via standard paging facilities ... the routines ran
    in "real addressing" mode w/o address translation turned on and couldn't
    depend on virtual address translation and/or hardware page faults. this
    didn't ship in standard cp67 product ... but was incorporated into the
    product as part of the morph from cp67 to vm370.

    for a little topic drift ... some recent posts about the "new", 40+ yr
    old virtual machine technology
    http://www.garlic.com/~lynn/2007b.html#23 How many 36-bit Unix ports in the old days?
    http://www.garlic.com/~lynn/2007b.html#26 How many 36-bit Unix ports in the old days?
    http://www.garlic.com/~lynn/2007l.html#23 John W. Backus, 82, Fortran developer, dies
    http://www.garlic.com/~lynn/2007p.html#7 what does xp do when system is copying
    http://www.garlic.com/~lynn/2007q.html#3 Virtualization: Don't Ask, Don't Tell
    http://www.garlic.com/~lynn/2007q.html#22 Enterprise: Accelerating the Progress of Linux
    http://www.garlic.com/~lynn/2007q.html#25 VMware: New King Of The Data Center?
    http://www.garlic.com/~lynn/2007q.html#49 Slimmed Down Windows Offers Glimpse Into Microsoft's Virtualization Ambitions
    http://www.garlic.com/~lynn/2007q.html#59 Virtualization: Everybody's Doing It, but Few Know How
    http://www.garlic.com/~lynn/2007q.html#64 Virtual Browsers: Disposable Security

  9. Re: Direction of Stack Growth

    Anne & Lynn Wheeler wrote:

    (snip)

    > http://www.garlic.com/~lynn/2007q.html#65 Direction of Stack Growth


    > in the os/360 convention called routine only needs its own savearea if
    > it is planning on calling other routine(s). a routine that doesn't make
    > any calls ... won't need its own savearea. a routine is only
    > allocating/chaining savearea (on entry), when it is calling other
    > routine(s) (for their use).


    That is true, but if you don't chain the save area you
    don't get an entry in the traceback for systems that do
    generate one.

    -- glen


  10. Re: Direction of Stack Growth


    In article , johnl@iecc.com (John L) writes:
    |>
    |> >Specifically, several compilers generated code that used 'GETMAIN R'
    |> >to allocate the stack frame one procedure entry. Those compilers
    |> >used an underlying 'heap' mechanism for the call stack.
    |> >
    |> >Been there - done that :-)
    |>
    |> Wow, was that slow. I know that Algol F did that, at least until you
    |> installed the patches from (as I recall) Princeton that suballocated
    |> bigger GETMAIN areas. What else did?

    Indeed! One of the PL/I options did, if I recall, and at least one
    of the other specialist languages I worked with. I now forget which,
    but they weren't mainstream, or any of IBM's, and they may have been
    only for the bootstrapping stage.

    It was certainly a recommended way of writing reentrant code but, as
    you point out, everyone then found that it ran like a drain. The
    amount of extra run-time system code to do it sanely was tiny.


    Regards,
    Nick Maclaren.

  11. Re: Direction of Stack Growth

    On Tue, 23 Oct 2007 17:21:21 -0400, Jerry Avins wrote:

    >karthikbalaguru wrote:
    >
    > ...
    >
    >> Reading through this and thinking about heap mechanism. I got some
    >> query.
    >> Why do we need the stack as the heap appears flexible ?

    >
    >Manipulating a heap requires software. Some stacks are implemented
    >entirely in hardware (PUSH, POP; CALL, RETURN). It would be very hard to
    >create or maintain a heap on a machine with no stack.


    The stack simplifies many things, such as re-entrancy. There have been
    architectures without an ordinary stack mechanism as the IBM S/360
    mentioned in other posts. The TI TMS9900 had all the general purpose
    registers in the RAM and starting a subroutine could use a new
    register set, which included a link to the previous register set so
    you knew how to return.

    In the 1960's for instance the DDP516 (later Honeywell) stored the
    return address at the first word of the subroutine and the actual
    subroutine code started at the next word. To return from the
    subroutine, an indirect jump was performed through the first word of
    the routine (which now contained the return address). This required
    that the code space was writable and the routine was not re-entrant,
    so recursion had to implemented in different way 8if ever used those
    days).

    Paul


  12. Re: Direction of Stack Growth

    > Why do we need the stack as the heap appears flexible ?
    >

    A heap needs addresses, Variables om a stack is can be addressed
    automatically (e.g. with 1 byte commands on an x86).

    -Michael

  13. Re: Direction of Stack Growth


    In article ,
    Paul Keinanen writes:
    |> On Tue, 23 Oct 2007 17:21:21 -0400, Jerry Avins wrote:
    |> >karthikbalaguru wrote:
    |> >
    |> >> Reading through this and thinking about heap mechanism. I got some
    |> >> query.
    |> >> Why do we need the stack as the heap appears flexible ?
    |> >
    |> >Manipulating a heap requires software. Some stacks are implemented
    |> >entirely in hardware (PUSH, POP; CALL, RETURN). It would be very hard to
    |> >create or maintain a heap on a machine with no stack.
    |>
    |> The stack simplifies many things, such as re-entrancy. There have been
    |> architectures without an ordinary stack mechanism as the IBM S/360
    |> mentioned in other posts. ...

    Not just that. During my spells at IBM, I tried very hard to persuade
    the Fortran people that using a stack would IMPROVE performance, based
    on my experiences on the System/370 with many languages.

    They were wedded to static allocation, because it enabled many of the
    address constants to be calculated by the compiler, which also eased
    pressure on the registers. This was Fortran 77, of course, and didn't
    support reentrancy. That argument is a good one, but I was arguing
    that the better locality properties of a stack gave MORE of a gain.

    As some people know, I have been banging on about double stacks for
    years. I first encountered them in Algol 68, was suspicious, but
    discovered that they need negligible extra code, stack space and
    register use, and vastly improve locality. Now, in these days of
    90% of performance being due to cachability, why does nobody pick
    them up again?

    It's insane.


    Regards,
    Nick Maclaren.

  14. Re: Direction of Stack Growth

    Nick Maclaren wrote:

    > As some people know, I have been banging on about double stacks for
    > years. I first encountered them in Algol 68, was suspicious, but
    > discovered that they need negligible extra code, stack space and
    > register use, and vastly improve locality. Now, in these days of
    > 90% of performance being due to cachability, why does nobody pick
    > them up again?


    If I've understood the "double stack" method correctly, it is like
    the "secondary stack" method that is used in some current Ada
    compilers, including the GNU Ada compiler GNAT, to manage
    dynamically sized stack-allocated objects.

    --
    Niklas Holsti
    Tidorum Ltd
    niklas holsti tidorum fi
    . @ .

  15. Re: Direction of Stack Growth


    In article <471f03bc$0$3501$39db0f71@news.song.fi>,
    Niklas Holsti writes:
    |>
    |> > As some people know, I have been banging on about double stacks for
    |> > years. I first encountered them in Algol 68, was suspicious, but
    |> > discovered that they need negligible extra code, stack space and
    |> > register use, and vastly improve locality. Now, in these days of
    |> > 90% of performance being due to cachability, why does nobody pick
    |> > them up again?
    |>
    |> If I've understood the "double stack" method correctly, it is like
    |> the "secondary stack" method that is used in some current Ada
    |> compilers, including the GNU Ada compiler GNAT, to manage
    |> dynamically sized stack-allocated objects.

    Yes, it is. I had forgotten about those. Thanks for the correction.
    The "nobody" should be "nobody except the Ada community"!


    Regards,
    Nick Maclaren.

  16. Re: Direction of Stack Growth

    Nick Maclaren wrote:

    ...

    > As some people know, I have been banging on about double stacks for
    > years. I first encountered them in Algol 68, was suspicious, but
    > discovered that they need negligible extra code, stack space and
    > register use, and vastly improve locality. Now, in these days of
    > 90% of performance being due to cachability, why does nobody pick
    > them up again?
    >
    > It's insane.


    Ayup! The Forths I use have three stacks.

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

  17. Re: Direction of Stack Growth


    In article <_uGdnTqXWaEPHYLanZ2dnUVZ_hWdnZ2d@rcn.net>,
    Jerry Avins writes:
    |>
    |> > As some people know, I have been banging on about double stacks for
    |> > years. I first encountered them in Algol 68, was suspicious, but
    |> > discovered that they need negligible extra code, stack space and
    |> > register use, and vastly improve locality. Now, in these days of
    |> > 90% of performance being due to cachability, why does nobody pick
    |> > them up again?
    |> >
    |> > It's insane.
    |>
    |> Ayup! The Forths I use have three stacks.

    Up, down and sideways? I always knew that Forth was a bizarre
    language :-)


    Regards,
    Nick Maclaren.

  18. Re: Direction of Stack Growth

    nmm1@cus.cam.ac.uk (Nick Maclaren) writes:
    > Niklas Holsti writes:
    > |>
    > |> > As some people know, I have been banging on about double stacks for
    > |> > years. I first encountered them in Algol 68, was suspicious, but
    > |> > discovered that they need negligible extra code, stack space and
    > |> > register use, and vastly improve locality. Now, in these days of
    > |> > 90% of performance being due to cachability, why does nobody pick
    > |> > them up again?
    > |>
    > |> If I've understood the "double stack" method correctly, it is like
    > |> the "secondary stack" method that is used in some current Ada
    > |> compilers, including the GNU Ada compiler GNAT, to manage
    > |> dynamically sized stack-allocated objects.
    >
    > Yes, it is. I had forgotten about those. Thanks for the correction.
    > The "nobody" should be "nobody except the Ada community"!


    If you're talking about separate stacks for return addresses and data,
    there are C compilers extant using that method under the hood.

    While on the subject of return addresses, isn't the ARM a throwback
    to the old BALR days? It's granted that you can save a push operation
    for leaf functions, but otherwise you spend the same or more operations
    saving the return address than just having the hardware do it
    automagically.

  19. Re: Direction of Stack Growth

    Niklas Holsti wrote:
    > Nick Maclaren wrote:
    >
    >> As some people know, I have been banging on about double stacks for
    >> years. I first encountered them in Algol 68, was suspicious, but
    >> discovered that they need negligible extra code, stack space and
    >> register use, and vastly improve locality. Now, in these days of
    >> 90% of performance being due to cachability, why does nobody pick
    >> them up again?

    >
    > If I've understood the "double stack" method correctly, it is like the
    > "secondary stack" method that is used in some current Ada compilers,
    > including the GNU Ada compiler GNAT, to manage dynamically sized
    > stack-allocated objects.
    >

    The Infineon TriCore (TC1796) has what amounts to dual stacks, in
    hardware. When you make a function call, a conventional stack pointer is
    moved (downwards, per GCC, but that's not mandatory), to obtain a new
    automatic-data space. Subroutine linkage & default register save is done
    separately, using a linked list of available "contexts". They use a
    linked list, rather than a second stack, as the pool of contexts can
    then be shared by all threads running.

  20. Re: Direction of Stack Growth


    In article <20071024.7937158.8D09@mojaveg.lsan.mdsg-pacwest.com>,
    mojaveg@mojaveg.lsan.mdsg-pacwest.com (Everett M. Greene) writes:
    |> nmm1@cus.cam.ac.uk (Nick Maclaren) writes:
    |> > Niklas Holsti writes:
    |> > |>
    |> > |> > As some people know, I have been banging on about double stacks for
    |> > |> > years. I first encountered them in Algol 68, was suspicious, but
    |> > |> > discovered that they need negligible extra code, stack space and
    |> > |> > register use, and vastly improve locality. Now, in these days of
    |> > |> > 90% of performance being due to cachability, why does nobody pick
    |> > |> > them up again?
    |> > |>
    |> > |> If I've understood the "double stack" method correctly, it is like
    |> > |> the "secondary stack" method that is used in some current Ada
    |> > |> compilers, including the GNU Ada compiler GNAT, to manage
    |> > |> dynamically sized stack-allocated objects.
    |> >
    |> > Yes, it is. I had forgotten about those. Thanks for the correction.
    |> > The "nobody" should be "nobody except the Ada community"!
    |>
    |> If you're talking about separate stacks for return addresses and data,
    |> there are C compilers extant using that method under the hood.

    No, we aren't. The method isn't much use for C89 or C++, but is
    for C99.


    Regards,
    Nick Maclaren.

+ Reply to Thread
Page 1 of 2 1 2 LastLast