8

I'm trying to understand how stack frames are constructed and have run into this description on wikipedia:

The locations of all other fields in the frame can be defined relative either to the top of the frame, as negative offsets of the stack pointer, or relative to the top of the frame below, as positive offsets of the frame pointer. The location of the frame pointer itself must inherently be defined as a negative offset of the stack pointer. --- https://en.wikipedia.org/wiki/Call_stack

The description in the quote above implies that the frame pointer's address being an offset from the stack pointer is trivially obvious from their respective definitions.

I'm confused about why the location of the frame pointer must inherently be defined as a function of the stack pointer.

As I understand the situation, the stack pointer is incremented when new memory is allocated to the frame. However the location of the frame pointer is fixed from the point where the procedure's prologue has finished.

Since all memory accesses within the frame must either be addressed as offsets from the frame pointer or as memory offsets from the stack pointer, and one of the frame pointer and stack pointer is a fixed location and the other one is inherently mutable, surely it makes sense to make the mutable pointer an offset from the fixed pointer?

As I understand it, in the above scheme, you'd need to update the frame pointer reference every time you incremented the stack pointer, which seems excessive. What have I misunderstood?

Racheet
  • 447
  • 4
  • 15

1 Answers1

12

Well, you are right, this is all very confusing. First of all, the frame pointer is not even necessary. Everything is addressable using only the stack pointer.

The main reason for the existence of the frame pointer is that the value of the stack pointer may change during the execution of the function, (namely, as you are pushing into the stack parameters of other functions that you are willing to call,) meaning that the offset of each argument and each local will vary. This is not a problem at all to a compiler, which can simply keep track of how the stack pointer varies and use adjusted offsets accordingly, but it can become a nightmare to a human who is trying to write the function or debug it later.

Another reason for the existence of the frame pointer is historical: the Intel x86 architecture used to be somewhat inconvenienced with respect to addressing memory relative to the stack pointer. The only registers that could be used as index registers were BX,BP,SI and DI, note how SP is missing from the list. So, the BP register was used as the frame pointer. However, it is kind of strange that the Wikipedia article should be influenced by the 8086, because it is describing a stack which grows upwards, while on the x86 architecture the stack grows downwards. Go figure.

Note that this has all been fixed in x64. If you look at the System V Application Binary Interface AMD64 Architecture Processor Supplement, on page 16 there is a footnote which says:

The conventional use of %rbp as a frame pointer for the stack frame may be avoided by using %rsp (the stack pointer) to index into the stack frame. This technique saves two instructions in the prologue and epilogue and makes one additional general-purpose register (%rbp) available.

So, in a nutshell, the conventional use of the frame pointer is as follows: upon entry to a function, the frame pointer receives a copy of the value of the stack pointer, and the stack pointer is adjusted to make room for the locals. Then, during the execution of the function, the stack pointer is allowed to vary, but the frame pointer remains constant, so arguments and locals are still addressable at fixed offsets from the frame pointer.

To return in your question, the location of the frame pointer is not exactly defined as a function of the stack pointer, in the sense that the value of the stack pointer is copied into the frame pointer only once, in the beginning of the function. From that point on, the frame pointer stays constant, while the stack pointer varies.

Mike Nakis
  • 32,003
  • 7
  • 76
  • 111
  • 1
    It might be worth to add that, before overwriting the frame pointer, the frame pointer of the previous function should be saved into a "known" location. – Bart van Ingen Schenau Nov 24 '15 at 14:54
  • thanks, that confirms what I thought I understood prior to reading that wikipedia paragraph, which I accidentally read to be implying something radically different. – Racheet Nov 24 '15 at 15:19