Vicare Scheme: machinery call frames

16.4 Basics of function call frames

We assume the validity of machinery simplifications to focus on some aspect of the runtime behaviour, Simplification assumptions.

Let’s consider the program:

(import (rnrs))
(define (one A)
  (+ A 1))
(one 2)

in which the call to Scheme function generates a stack frame; the form (one 2) is the “call site” and we can think of it as generating Assembly code containing the chunk:

(call address_of_one)
(label return_address)

Let’s start with an empty Scheme stack represented by CPU registers and PCB fields, machinery call frames.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler | <- Frame Pointer Register (FPR)
|----------------------|
            .
            .
            .
|----------------------|
|                      | <- pcb->stack_base
|----------------------|
|                      |
       low memory

Figure 16.4: Empty Scheme stack as represented in the CPU registers and the PCB structure while running Scheme code.

Running the program means executing the following operations:

Prepare to call one: put the single argument on the stack 2 machine words below the underflow handler, machinery call frames.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler | <- FPR
|----------------------|
|                      | <- FPR - 1*wordsize
|----------------------|
|    argument A == 2   | <- FPR - 2*wordsize
|----------------------|
|                      |
       low memory

Figure 16.5: Preparing the function call to one by putting the argument on the stack.

Call one: execute the Assembly instruction call; this puts the return address on the stack and decrements the FPR by a machine word, machinery call frames. Notice that the stack now contains a single stack frame representing the status of the code before the call.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler |
|----------------------|         --
|    return address    | <- FPR  . frame of caller
|----------------------|         --
|    argument A == 2   |
|----------------------|
|                      |
       low memory

Figure 16.6: Stack right after the function call to one.

Prepare to call +: put the two arguments on the stack 2 machine words below the return address, compiler machinery call frames.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler |
|----------------------|         --
|    return address    | <- FPR  . frame of caller
|----------------------|         --
|    argument A == 2   |         .
|----------------------|         . frame of ONE
|                      |         .
|----------------------|         --
|   1st argument == 2  |
|----------------------|
|   2nd argument == 1  |
|----------------------|
|                      |
       low memory

Figure 16.7: Preparing the call to +.

Adjust the FPR to reference the machine word right above the one that will hold the return address, compiler machinery call frames.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler |
|----------------------|         --
|    return address    |         . frame of caller
|----------------------|         --
|    argument A == 2   | <- FPR
|----------------------|
|                      |
|----------------------|
|   1st argument == 2  |
|----------------------|
|   2nd argument == 1  |
|----------------------|
|                      |
       low memory

Figure 16.8: Adjusting the FPR for the call to +.

Call +: execute the Assembly instruction call; this puts the return address on the stack and decrements the FPR by a machine word, machinery call frames. Notice that the stack now contains two stack frames representing the status of the code before the call.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler |
|----------------------|         --
|    return address    |         . frame of caller
|----------------------|         --
|    argument A == 2   |         .
|----------------------|         . frame of ONE
|    return address    | <- FPR  .
|----------------------|         --
|   1st argument == 2  |
|----------------------|
|   2nd argument == 1  |
|----------------------|
|                      |
       low memory

Figure 16.9: Stack right after the call to +.

Let’s skip how + performs the addition and just assume that the result is stored in the AAR register.

Return from +: execute the Assembly instruction ret which: loads the machine word from the stack location referenced by FPR into the CPU’s Instruction Pointer Register, increments the FPR by a machine word, jumps to the code address in the Instruction Pointer Register, machinery call frames.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler |
|----------------------|         --
|    return address    |         . frame of caller
|----------------------|         --
|    argument A == 2   | <- FPR  .
|----------------------|         . frame of ONE
|    return address    |         .
|----------------------|         --
|                      |
       low memory

Figure 16.10: Stack right after the ret instruction that returns from +.

Adjust back the FPR to reference the return address of the caller machinery call frames.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler |
|----------------------|         --
|    return address    | <- FPR  . frame of caller
|----------------------|         --
|    argument A == 2   |
|----------------------|
|                      |
       low memory

Figure 16.11: Adjusting the FPR back after returning from +.

Return from one: execute the Assembly instruction ret which: loads the machine word from the stack location referenced by FPR into the CPU’s Instruction Pointer Register, increments the FPR by a machine word, jumps to the code address in the Instruction Pointer Register, machinery call frames. The return value is still in the AAR register.
```
      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler | <- FPR
|----------------------|
|                      |
       low memory
```
Figure 16.12: Stack right after the ret instruction that returns from one.
The form (one 2) is the only top–level expression in the program, so, after executing it, the execution flow must go back to the C code that started the program; we can imagine the Assembly code:
```
(call address_of_one)
(label return_address)
;; move the return value from AAR to the stack
(movl AAR (disp (- wordsize) FPR))
(ret)
```
where (ret) jumps to the underflow handler.

After the program execution: the stack is left empty as it was at the beginning; this is because no continuation objects have been created.