cbza.org Casa Budista Zapatista-Anarquista

Stack Allocation for StreetLISP

Explaining the changes needed in the vm and compiler in order to do stack allocation.

Background: Current Stack Frame Layout

The current layout of a stack frame in StreetLISP is:

Certain values of the vm are set to locations in the stack: obp, ipd, and sl.curr_frame. The value ipd is used to save the current instruction pointer in order to continue execution after returning from function calls. sl.curr_frame is used to return to the previous frame; it is the reference point to get the saved ip and previous curr_frame for example. The value obp is used as the base pointer from which to retrieve values placed on the stack: the arguments to the function and local variables. This is used in the OP_LOADA instruction.

Changes to the Stack Frame

The proposed change is to add a static value to each stack frame to track the amount of stack allocation and to add a section of dynamically allocated stack:

The values stka_size and stka_idx will both be 4 bytes to fit in a single sl_v location on the stack. The value stka_size will represent the maximum amount pre-reserved on the stack for stack allocated values. Local variables will begin to be stored at sl.curr_frame + stka_size. The value stka_idx will represent an index to the current unallocated value on the stack. This will be incremented when stack allocation occurs, through, for example, a call to stkcons.

Changes to Functions

A function must store its stka_size as a new value in the function data structure. This value will be computed at compile-time.

Changes to VM Instructions

There will be a new instruction LOADL (load local) which will use as base pointer offset sl.curr_frame + stka_size instead of obp. This is because stack allocation may be dynamic in the case of tail calls. This requires a slight change to the compiler which will be explained below.

There will be a new instruction OP_STKCONS which will copy the arguments to OP_STKCONS to the current stk_idx value and increment stk_idx, and then push a pointer to those values onto the stack of locals, i.e., a normal PUSH call for this pointer value. Other stack allocations will be implemented in the future, for example for vectors or a call to list, but we'll start with this one.

A call to a function will push the stka_size saved in the function data structure to the stack frame and will set the stka_idx to zero.

A tail call to a function will increment the stka_size value of the current frame by the function's computed stka_size value and not change (i.e. reset) the stka_idx.

Changes to the Compiler

The vinfo data structure will have an extra field to mark whether the variable is an argument or a local. The compile-let function will mark the variables compiled in vars-to-env as being local. Accessing such local variables will cause the compiler to emit a LOADL instruction instead of LOADA.

The compiler currently increments the stack pointer for variables by 4 to account for the extra values pushed on the stack after arguments but before locals, i.e., the env_ptr, the saved sl.curr_frame from the previous frame, nargs and the location to save the ip.

This is done with the following code in the compiler:

;; set initial stack pointer
(bcode:stack g (+ (length vars) 4))

Instead of incrementing the compile-time stack pointer for locals, the LOADL instruction will ensure that locals are accessed at the correct offset, after the stack allocated values. So the compile-time stack pointer instead will get set to 0 instead.