9.3.3 Stack Layout

The stack of Guile’s virtual machine is composed of frames. Each frame corresponds to the application of one compiled procedure, and contains storage space for arguments, local variables, and some bookkeeping information (such as what to do after the frame is finished).

While the compiler is free to do whatever it wants to, as long as the semantics of a computation are preserved, in practice every time you call a function, a new frame is created. (The notable exception of course is the tail call case, see Tail Calls.)

The structure of the top stack frame is as follows:

   | ...previous frame locals...  |
   +==============================+ <- fp + 3
   | Dynamic link                 |
   +------------------------------+
   | Virtual return address (vRA) |
   +------------------------------+
   | Machine return address (mRA) |
   +==============================+ <- fp
   | Local 0                      |
   +------------------------------+
   | Local 1                      |
   +------------------------------+
   | ...                          |
   +------------------------------+
   | Local N-1                    |
   \------------------------------/ <- sp

In the above drawing, the stack grows downward. At the beginning of a function call, the procedure being applied is in local 0, followed by the arguments from local 1. After the procedure checks that it is being passed a compatible set of arguments, the procedure allocates some additional space in the frame to hold variables local to the function.

Note that once a value in a local variable slot is no longer needed, Guile is free to re-use that slot. This applies to the slots that were initially used for the callee and arguments, too. For this reason, backtraces in Guile aren’t always able to show all of the arguments: it could be that the slot corresponding to that argument was re-used by some other variable.

The virtual return address is the ip that was in effect before this program was applied. When we return from this activation frame, we will jump back to this ip. Likewise, the dynamic link is the offset of the fp that was in effect before this program was applied, relative to the current fp.

There are two return addresses: the virtual return address (vRA), and the machine return address (mRA). The vRA is always present and indicates a bytecode address. The mRA is only present when a call is made from a function with machine code (e.g. a function that has been JIT-compiled).

To prepare for a non-tail application, Guile’s VM will emit code that shuffles the function to apply and its arguments into appropriate stack slots, with three free slots below them. The call then initializes those free slots to hold the machine return address (or NULL), the virtual return address, and the offset to the previous frame pointer (fp). It then gets the ip for the function being called and adjusts fp to point to the new call frame.

In this way, the dynamic link links the current frame to the previous frame. Computing a stack trace involves traversing these frames.

Each stack local in Guile is 64 bits wide, even on 32-bit architectures. This allows Guile to preserve its uniform treatment of stack locals while allowing for unboxed arithmetic on 64-bit integers and floating-point numbers. See Instruction Set, for more on unboxed arithmetic.

As an implementation detail, we actually store the dynamic link as an offset and not an absolute value because the stack can move at runtime as it expands or during partial continuation calls. If it were an absolute value, we would have to walk the frames, relocating frame pointers.