«

Recently K. Thompson asked me to specify what did I understand
with "stack frame". I think that it is important for people using the
language, that this important concept is clear, so I have produced
this post.

Obviously, there are some people here that live in some
special world where all those things do not exist. They should stay
there and ignore this thread. The same goes for all people that
program in coffee machines and other primitive processors that
do not have a stack pointer or enough registers to use a stack
efficiently.

----------------------
What is a stack frame?
---------------------

Within a stack, each procedure builds a "stack frame", i.e. a fixed
point within the stack, where storage for local variables is reserved.

The stack frames are a linked list of this storage areas. This builds
the conceptual stack that the language needs. Each stack frame is
linked to the previous one. A new stack frame is built when a
procedure is entered, and it is popped from the stack of stack frames
at the procedure exit.

The "main" function has the first (visible) frame, and each stack
frame built in one of the functions called after "main" started is
linked to that stack frame. This makes it possible for debuggers
and other tools to "walk the stack" of called procedures.

We can (conceptually) describe the stack frame as follows

struct tagStackFrame {
void *Previous;
void *ThisFrame;
char LocalStorage[];
};

The "Next" member is a pointer to the previous function's stack frame,
the "ThisFrame" pointer points to the current stack frame, and the
Local storage is made out of different variables that a function
declares. We can imagine that the local storage of deeper nested
blocks is added to the function's local storage, even if it is not
visible (i.e. can't be accessed) after its scope disappears.

Building the stack frame (Prologue)
------------------------

The first thing to do to build a stack frame is then, to save in the
"Previous" slot, the value of the current stack frame pointer.
Normally, this is a dedicated register. For instance, the power PC
version of lcc-win uses register 31. This register is normally
defined by the operating system ABI (Application Binary Interface)
since ALL programs running in the same operating system MUST agree
as to what the frame pointer register is, if not CHAOS is surely the
consequence.

After saving the current FP (or Frame Pointer) we copy the current
value of the stack pointer into the frame pointer, to establish a new
stack frame from this stack position on. We fill then, the "ThisFrame"
slot of our structure, and lastly, we subtract from the frame pointer
the amount of space needed by the function's local variables, our
"Local storage" member.

There exist MANY variation of this scheme. Some optimizing compilers
save themselves the trouble of having a different register than the
stack pointer to build a stack frame, and just use the stack pointer to
address local variables. Conceptually however, nothing changes.

Popping the stack frame (Epilogue)
-----------------------

A function must restore the previous stack frame before leaving the
scene. This is done in the reverse order of the previous actions. The
space allocated for local variables is released by adjusting the stack
pointer, the previous value of the stack frame is popped from the stack,
and the function can now return.

Other stuff
-----------

A function uses registers to do its calculations. Those register can be
scratch registers, i.e. registers that can be used without having to
save them, or they can be registers that need save before use, to
preserve their value across function calls. The saved registers are part
of the stack frame, even if I did not mention that above to keep things
simple. They are restored before the current function exits.

Another thing to be known is "alloca". This function allocates storage
from the stack by decreasing the stack pointer. A function that calls
alloca must do the popping of the current stack frame in a different
manner since the current stack frame is "deformed" by alloca.

And yet another thing: in standard C, we can have objects whose size
is allocated in local storage but whose exact size is unknown until
run time. This is similar to alloca, and produces the same consequences.




--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

jacob navia said:

> Recently K. Thompson asked me to specify what did I understand
> with "stack frame". I think that it is important for people using the
> language, that this important concept is clear, so I have produced
> this post.

Have you considered posting this in a newsgroup where it's relevant, such
as, perhaps, comp.arch?

> Obviously, there are some people here that live in some
> special world where all those things do not exist.

Well, there are many such worlds, of which comp.lang.c is one, yes. Others
include rec.scuba, alt.folklore.urban, and sci.med.dentistry. I note that
you did not post this article to those groups. Why post it to comp.lang.c?

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

"jacob navia" <> wrote in message
news:fqgksq$eja$...

> The first thing to do to build a stack frame is then, to save in the
> "Previous" slot, the value of the current stack frame pointer.
> Normally, this is a dedicated register. For instance, the power PC
> version of lcc-win uses register 31. This register is normally
> defined by the operating system ABI (Application Binary Interface)

I think it is specified by the architecture where there is special support
for a frame pointer. But even then implementations can make whatever
arrangements they like.

> since ALL programs running in the same operating system MUST agree
> as to what the frame pointer register is, if not CHAOS is surely the
> consequence.

That sounds unlikely.

> Some optimizing compilers
> save themselves the trouble of having a different register than the
> stack pointer to build a stack frame, and just use the stack pointer to
> address local variables.

And clearly 'chaos' does not result.

The point is all this stuff depends on the implementation of the language
and varies from system to system. Probably most implementations will have
some sort of stack and maybe some will use some concept of a frame pointer,
and sometimes it might be helpful to bear all this in mind. But your details
are far too specific.

--
Bart

Bartc wrote:
> "jacob navia" <> wrote in message
> news:fqgksq$eja$...
>
>> The first thing to do to build a stack frame is then, to save in the
>> "Previous" slot, the value of the current stack frame pointer.
>> Normally, this is a dedicated register. For instance, the power PC
>> version of lcc-win uses register 31. This register is normally
>> defined by the operating system ABI (Application Binary Interface)
>
> I think it is specified by the architecture where there is special support
> for a frame pointer. But even then implementations can make whatever
> arrangements they like.

Arrangements that MUST be compatible with the ABI. Here we have the
"as if rule": an implementation could use other registers for the
frame pointer as long as it does NOT trash the value in the official
frame pointer.
>
>> since ALL programs running in the same operating system MUST agree
>> as to what the frame pointer register is, if not CHAOS is surely the
>> consequence.
>
> That sounds unlikely.
>

Try trashing the frame pointer then, and see what happens.

>> Some optimizing compilers
>> save themselves the trouble of having a different register than the
>> stack pointer to build a stack frame, and just use the stack pointer to
>> address local variables.
>
> And clearly 'chaos' does not result.
>

Because they preserve the frame pointer register.

> The point is all this stuff depends on the implementation of the language
> and varies from system to system.

The general setup I described does NOT.


> Probably most implementations will have
> some sort of stack and maybe some will use some concept of a frame pointer,
> and sometimes it might be helpful to bear all this in mind. But your details
> are far too specific.
>

No, they are general enough to cover most implementations.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

Richard Heathfield wrote:

> jacob navia said:
>
>> Recently K. Thompson asked me to specify what did I understand
>> with "stack frame". I think that it is important for people using the
>> language, that this important concept is clear, so I have produced
>> this post.
>
> Have you considered posting this in a newsgroup where it's relevant,
> such as, perhaps, comp.arch?
>
>> Obviously, there are some people here that live in some
>> special world where all those things do not exist.
>
> Well, there are many such worlds, of which comp.lang.c is one, yes.
> Others include rec.scuba, alt.folklore.urban, and sci.med.dentistry. I
> note that you did not post this article to those groups. Why post it
> to comp.lang.c?

IMO, it would be most appropriate in comp.compilers as the stack frame
is more a compiler artifact than anything else.

In article <fqgqq3$21f$>, jacob navia <> wrote:

>>> since ALL programs running in the same operating system MUST agree
>>> as to what the frame pointer register is, if not CHAOS is surely the
>>> consequence.

>> That sounds unlikely.

>Try trashing the frame pointer then, and see what happens.

I can't be bothered to find out how to do that. Why not just tell us?

I wouldn't have expected the frame pointer to have any significance
outside the current process (except to a debugger), so I don't know
why "all programs running in the same operating system must agree".

-- Richard

--
:wq

Richard Tobin wrote:
> In article <fqgqq3$21f$>, jacob navia <> wrote:
>
>>>> since ALL programs running in the same operating system MUST agree
>>>> as to what the frame pointer register is, if not CHAOS is surely the
>>>> consequence.
>
>>> That sounds unlikely.
>
>> Try trashing the frame pointer then, and see what happens.
>
> I can't be bothered to find out how to do that. Why not just tell us?
>
> I wouldn't have expected the frame pointer to have any significance
> outside the current process (except to a debugger), so I don't know
> why "all programs running in the same operating system must agree".
>
> -- Richard
>

Obvious, because all libraries in the OS must be called with specific
calling conventions and register usage agreements. All programs must
call the OS to do I/O. They must respect the OS ABI to call those basic
OS routines.

The OS libraries are used by ALL code that runs in that system
eventually, no matter what language the end user is using.


--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

santosh wrote:
>
> IMO, it would be most appropriate in comp.compilers as the stack frame
> is more a compiler artifact than anything else.
>

Yes, compilers are an "artifact" of compiled languages. Obviously
you think that C is not one of them.

or what ???

Basic knowledge about compiler code generation is needed if you want
to be able to understand what is going on within your program.

Obviously it is not required, as you can drive a car for miles without
needing to know that it needs gas to run.

"According to my car user's manual, if I press this pedal the car
should move. It doesn't say ANYWHERE that gas is needed".

You have the same attitude here, like your big friend.

Why santosh?

You seem reasonable at times.




--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

jacob navia <> wrote:

> santosh wrote:
> >
> > IMO, it would be most appropriate in comp.compilers as the stack frame
> > is more a compiler artifact than anything else.
>
> Yes, compilers are an "artifact" of compiled languages. Obviously
> you think that C is not one of them.
>
> or what ???

You've never seen a C interpreter?

> Basic knowledge about compiler code generation is needed if you want
> to be able to understand what is going on within your program.

*******s. Knowledge of the _language_ is needed if you want to know what
your program does. If you want to know _how_ it does that, merely basic
knowledge about merely code generation is not nearly sufficient.

Richard

In article <fqgrl4$44a$>, jacob navia <> wrote:

>> I wouldn't have expected the frame pointer to have any significance
>> outside the current process (except to a debugger), so I don't know
>> why "all programs running in the same operating system must agree".

>All programs must call the OS to do I/O. They must respect the OS ABI
>to call those basic OS routines.

Do any OS ABIs require the caller to take any care of the frame
pointer?

I just looked up the x86 call conventions. As far as I can see, the
calle saves and restores the frame pointer and does not use its old
value. So on these systems you do can use it for anyh purpose you
like.

[If you are called back by these libraries you will presumably have to
preserve the frame pointer, but that just restricts the functions
that you can pass in to it.]

>The OS libraries are used by ALL code that runs in that system
>eventually

No, this is certainly not true. I have used several languages that
just did system call instructions directly. The normal procedure
calling convention was irrelevant.

-- Richard
--
:wq