How the stack grows

[deepak]

Hi All,

In C I heard the stack grows from top to bottom and heap from bottom to
top.
Is it compiler depend?

[Chris Dollin]

David T. Ashley wrote:

The direction the stack grows is going to be architecture-dependent. All
machines have a certain direction the stack pointer goes on a subroutine
call and instructions like PUSH, and typically a 'C' compiler will build
stack frames starting with this convention.

Not /all/ machines, the ARM being the obvious example.

(The subroutine call instruction doesn't use any stack at all;
the return address is saved in R14 and restoring that value
to the PC (which happens to be R15) accomplishes a return.
If you want to stack things, the LDR/STR instructions have
enough addressing modes that you can stack either way up; more
crucially, the LDM/STM instructions, which save/restore
multiple registers to sequential locations, have all four of
the increment vs decrement and before vs after variants, so
you can stack either way up with those too. Which ones you
use depend on the environment the code runs in, not some
predetermined hardware choice. As for interrupts, those are
initially handled using shadow registers, not a stack -- so
again, any stack conventions are just that: conventions.

I seem to recall that the C implementation used threaded
stack chunks, not a single contiguous space, so local
variables in different functions [1] could have wildly
different addresses with no necessary consistency in
"grow up" or "grow down", but it's been a long time since
I deserted RISC OS for Linux [2].)

[1] one of which called the other.

[2] I'll just go and have a little cry.

--
Chris "electric hedgehog" Dollin
"No-one here is exactly what he appears." G'kar, /Babylon 5/

[E. Robert Tisdale]

deepak wrote:

In C, I heard that the stack grows from top to bottom
and heap from bottom to top.
Is it compiler depend?

A stack always grows from bottom to top
but neither computers or compilers know up from down.
They don't need to
but programmers sometimes find the distinction convenient.

In the typical implementation,
low memory addresses are associated with the top of memory
and high memory addresses are associated with the bottom of memory.

0000 0000 (top of memory)
0000 0001

[Keith Thompson]

"E. Robert Tisdale" <ed***@netwood. netwrites:

deepak wrote:

In C, I heard that the stack grows from top to bottom
and heap from bottom to top.
Is it compiler depend?

A stack always grows from bottom to top
but neither computers or compilers know up from down.
They don't need to
but programmers sometimes find the distinction convenient.

If you define "top" and "bottom" that way.

In the typical implementation,
low memory addresses are associated with the top of memory
and high memory addresses are associated with the bottom of memory.

[...]

The stack, for systems that have such a thing, can grow in either
direction. For well-written C code, it doesn't matter.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[santosh]

E. Robert Tisdale wrote:

deepak wrote:

In C, I heard that the stack grows from top to bottom
and heap from bottom to top.
Is it compiler depend?

A stack always grows from bottom to top
but neither computers or compilers know up from down.
They don't need to
but programmers sometimes find the distinction convenient.

In the typical implementation,
low memory addresses are associated with the top of memory
and high memory addresses are associated with the bottom of memory.

Haven't you got this backwards from how it's usually considered?

[John Bode]

santosh wrote:

E. Robert Tisdale wrote:

deepak wrote:

In C, I heard that the stack grows from top to bottom
and heap from bottom to top.
Is it compiler depend?

A stack always grows from bottom to top
but neither computers or compilers know up from down.
They don't need to
but programmers sometimes find the distinction convenient.

In the typical implementation,
low memory addresses are associated with the top of memory
and high memory addresses are associated with the bottom of memory.

Haven't you got this backwards from how it's usually considered?

Not necessarily. I've seen a number of implementations that grow from
high to low memory.

If you're implementing a stack as a simple array and updating your
stack pointer via ++ and --, going from high to low is dead easy:

#define N ...
static value_t stack[N];
static size_t sp = 0;

void push(value_t val)
{
if (sp 0)
stack[--sp] = val;
else
// overflow
}

void pop(value_t *val)
{
if (sp < N)
*val = stack[sp++];
else
// underflow
}

Granted, going from low to high isn't that much more complicated, but
it isn't quite this straightforward .

[John Bode]

John Bode wrote:

santosh wrote:

E. Robert Tisdale wrote:

deepak wrote:
>
In C, I heard that the stack grows from top to bottom
and heap from bottom to top.
Is it compiler depend?
>
A stack always grows from bottom to top
but neither computers or compilers know up from down.
They don't need to
but programmers sometimes find the distinction convenient.
>
In the typical implementation,
low memory addresses are associated with the top of memory
and high memory addresses are associated with the bottom of memory.

Haven't you got this backwards from how it's usually considered?

Not necessarily. I've seen a number of implementations that grow from
high to low memory.

If you're implementing a stack as a simple array and updating your
stack pointer via ++ and --, going from high to low is dead easy:

#define N ...
static value_t stack[N];
static size_t sp = 0;

Of course, that line *should* read

static size_t sp = N;

Serves me right for posting before I'm really awake.

[hagman]

deepak schrieb:

Hi All,

In C I heard the stack grows from top to bottom and heap from bottom to
top.
Is it compiler depend?

While the stack growing direction is mostly based on machine dependent
stack treatment (e.g. Intel cpus have PUSH, POP etc. using a cpu
register
as stack pointer that is /decremented/ by a PUSH), heap management
is purely software oriented and thus either OS-dependent or not even
that
(i.e. compiler dependent, where the compiler might base its decision on
OS
and architecture). Heap management methods within your own projects
might even be a configurable option.

[CBFalconer]

santosh wrote:

E. Robert Tisdale wrote:

>deepak wrote:

>>In C, I heard that the stack grows from top to bottom
and heap from bottom to top. Is it compiler depend?

A stack always grows from bottom to top but neither computers or
compilers know up from down. They don't need to but programmers
sometimes find the distinction convenient.

In the typical implementation, low memory addresses are
associated with the top of memory and high memory addresses are
associated with the bottom of memory.

Haven't you got this backwards from how it's usually considered?

Tisdale is normally wrong. Best ignored.

--
Sending unsolicited commercial e-mail to
cbfalconer at maineline dot net
incurs a fee of 500 USD per message, and
acknowledges the legality of this contract.

[Dave Thompson]

On 16 Jan 2007 22:55:33 GMT, ri*****@cogsci. ed.ac.uk (Richard Tobin)
wrote:

In article <5o************ *************** ***@giganews.co m>,
David T. Ashley <dt*@e3ft.comwr ote:

In C I heard the stack grows from top to bottom and heap from bottom to
top.
Is it compiler depend?

In the early days of the PC when 640K was the rule, this may have been the
case. I'm not sure it is the case today.

When talking about C, a more natural computer to consider is the PDP-11.
PCs were latecomers to the C party.

And interestingly, the PDP-11 is an example of a machine where stacks
can be easily used in either direction. Rather than a "push"
instruction, it has auto-increment and auto-decrement modes for
register access.

Stacks in general almost, but the stack used for 'hardware' (ISA)
calls -- and as noted elsethread, in block-frame languages including C
it is usually convenient to put locals and params/args together with
calls -- JSR and RTS use R6=(U?)SP growing downward. It is possible to
cobble together your own calling sequence not using -(R6), but
significantly more tedious for IME&O zero benefit.

And even for other (non-call) stacks, downward push *--r and pop *r++
allow you to peek at the top (single) element more cheaply than the
upward counterparts. FW(L?)IW.

Even on such a machine, there are typically good reasons to use a
particular direction for the call stack. One is compatibility
with other languages on the same system, and another is that the
hardware may assume a particular stack direction when generating
interrupts, though I think it's rare for hardware interrupts to use
the user stack these days.

-11 interrupts/traps and RTI/RTT also use R6=(K?)SP downward, but on
models with memory management it indeed is the K (kernel) one, and at
least the most important -11 OS on which C was implemented (wink,
wink, nudge, nudge <G>) required such models.

I don't recall if there was a C implementation for RT-11 non-XM; there
almost certainly wasn't a conforming one, if in fact there was still
any significant development on or targetting that system by '89.

- David.Thompson1 at worldnet.att.ne t

[Giorgos Keramidas]

On Mon, 29 Jan 2007 00:03:33 GMT,
Dave Thompson <da************ *@worldnet.att. netwrote:

Stacks in general almost, but the stack used for 'hardware'
(ISA) calls -- and as noted elsethread, in block-frame
languages including C it is usually convenient to put locals
and params/args together with calls -- JSR and RTS use
R6=(U?)SP growing downward. It is possible to cobble together
your own calling sequence not using -(R6), but significantly
more tedious for IME&O zero benefit.

And even for other (non-call) stacks, downward push *--r and
pop *r++ allow you to peek at the top (single) element more
cheaply than the upward counterparts. FW(L?)IW.

Hmmm, isn't a downward stack implemented with:

push: *--r = rvalue;
pop: return *r++;

more or less equivalent with an upward growing stack which uses:

push: *++r = rvalue;
pop: return *r--;

or am I missing something fundamental about downward growing stacks?