9.3.3 Stack Layout

While not strictly necessary to understand how to work with the VM, it is instructive and sometimes entertaining to consider the structure of the VM stack.

Logically speaking, a VM stack is composed of “frames”. Each frame corresponds to the application of one compiled procedure, and contains storage space for arguments, local variables, intermediate values, and some bookkeeping information (such as what to do after the frame computes its value).

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 section Tail calls.)

Within a frame, you have the data associated with the function application itself, which is of a fixed size, and the stack space for intermediate values. Sometimes only the former is referred to as the “frame”, and the latter is the “stack”, although all pending application frames can have some intermediate computations interleaved on the stack.

The structure of the fixed part of an application frame is as follows:

             Stack
   | ...              |
   | Intermed. val. 0 | <- fp + bp->nargs + bp->nlocs = SCM_FRAME_UPPER_ADDRESS (fp)
   +==================+
   | Local variable 1 |
   | Local variable 0 | <- fp + bp->nargs
   | Argument 1       |
   | Argument 0       | <- fp
   | Program          | <- fp - 1
   +------------------+    
   | Return address   |
   | MV return address|
   | Dynamic link     | <- fp - 4 = SCM_FRAME_DATA_ADDRESS (fp) = SCM_FRAME_LOWER_ADDRESS (fp)
   +==================+
   |                  |

In the above drawing, the stack grows upward. The intermediate values stored in the application of this frame are stored above SCM_FRAME_UPPER_ADDRESS (fp). bp refers to the struct scm_objcode data associated with the program at fp - 1. nargs and nlocs are properties of the compiled procedure, which will be discussed later.

The individual fields of the frame are as follows:

Return address

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.

MV return address

The ip to return to if this application returns multiple values. For continuations that only accept one value, this value will be NULL; for others, it will be an ip that points to a multiple-value return address in the calling code. That code will expect the top value on the stack to be an integer—the number of values being returned—and that below that integer there are the values being returned.

Dynamic link

This is the fp in effect before this program was applied. In effect, this and the return address are the registers that are always “saved”. The dynamic link links the current frame to the previous frame; computing a stack trace involves traversing these frames.

Local variable n

Lambda-local variables that are all allocated as part of the frame. This makes access to variables very cheap.

Argument n

The calling convention of the VM requires arguments of a function application to be pushed on the stack, and here they are. References to arguments dispatch to these locations on the stack.

Program

This is the program being applied. For more information on how programs are implemented, See section Compiled Procedures are VM Programs.

This document was generated on April 20, 2013 using texi2html 5.0.