In this post, we continue the task of implementing a VM (“AstridVM”) by doing the hardest tasks first. In part I, we implemented the simplest possible VM we could with only three operations: PUSH, POP, and HALT. However, we did so with a more robust register type than we necessarily needed at the time. But because it was instructive for how real registers work, and we because we won’t have to retrofit our VM later when we need those fancy general purpose registers later, we went a little over the top.
We will continue to eschew simpler operations like math (we still don’t have ADD, SUB, or MUL ops; but you can probably implement them trivially using stack operations we’ve already defined) in favor of something I have yet to see other example and toy VM’s do: procedure calls. By introducing procedure calls, we make AstridVM very close to being actually useful. By the end of the post, you’ll see why it will become necessary for Part III to cover the construction of an assembler attendant to AstridVM.
How Procedures Work
To implement procedure calls in AstridVM, we have to examine how they work on a “real” computer. A procedure call hands control of execution to a subroutine, with the expectation that we will gain control back. On PC, this means that before we hand over control, we save several important details, such as “where are we now?” and “what part of the stack were we looking at?” This means saving the stack pointer, instruction pointer, and frame pointer on what’s called the call stack. On a PC, this is also called the program stack or machine stack, and it’s the stack, meaning it’s also where local variables are kept. We save IP, SP, and FP when we call the procedure. When we return, we pop these values off the stack and back into their respective registers, thus restoring the exact state we had before we made the procedure call.
Top of the Stack
SP -> ----------------
Local Variables
FP -> ----------------
Saved Registers
----------------
Procedure Params
----------------
Figure 1: Anatomy of a traditional stack frame
But we already have a stack we intend to use for local variables, so what gives? We have options. We could use our stack as the call stack, but because we are in the context of a VM that is not necessarily tied to hardware implementation, we aren’t shackled to how the PC architecture does it. For AstridVM, I’ll make a separate, discrete call stack. This means that I don’t need to iteratively unwind stack items to get to the last procedure call; I just need to pop the last item off the call stack.
Introducing the Frame Pointer
Notice above, the frame pointer points at the area just before the procedure’s local variables. This means that FP defines our local scope. You’ll see that all our local scope stack references (read: local variables) are based off of FP. To effect this, when we make our procedure call (after saving control registers to the call stack), we update FP to point to the top of the stack before pushing our local variables (we’ll cover these in a subsequent post).
Our New Opcodes
We add to our opcodes three new instructions that are hopefully explained well enough by their comments:
CALL = 0x0004, // Call the address specified by the operand. RETN = 0x0005, // Return from the current procedure. RETV = 0x0006, // Same as RETN, but we take the value at the // address specified by the operand and push it // to the stack after returning.
Implementing the Call Stack
#define CALLSTACK_SIZE 256
typedef struct callstack_record
{
OFFSET_TYPE _sp;
OFFSET_TYPE _ip;
OFFSET_TYPE _fp;
} callstack_record;
extern callstack_record callstack[];
Figure 3: globals.h
The names of the struct members may seem odd, but they are necessary. The underscore prevents the name from clashing with the preprocessor macros named for their respective registers.
We also need to add another register; one that is not a part of standard PC architecture. Because we have a separate call stack, we need a pointer to its top:
typedef enum
{
IP, SP, FP,
CSP,
NUM_REGS
} registers_names;
#define csp (registers[CSP].r16)
Figure 4: registers.h
Now that we are dealing with addresses, we need to define some helper methods for grabbing them off the instruction list and pushing them onto the stack:
OFFSET_TYPE fetch_offset()
{
ip += OFFSET_SIZE;
return *(OFFSET_TYPE*)(instructions + ip - OFFSET_SIZE);
}
void push_offset(OFFSET_TYPE val)
{
*(OFFSET_TYPE*)(stack + sp) = val;
sp += OFFSET_SIZE;
}
Figure 5: astridvm.c
And don’t forget to instantiate the call stack:
callstack_record callstack[CALLSTACK_SIZE];
Figure 6: astridvm.c
Instruction Implementation
In eval(), we need to add our new opcodes. First, we implement CALL:
case CALL:
callstack[csp]._ip = ip;
callstack[csp]._sp = sp;
callstack[csp]._fp = fp;
csp++;
ip = fetch_offset();
fp = sp;
#ifdef DEBUG
printf("CALL %d\n", ip);
#endif
break;
Figure 7: astridvm.c
First, we save the registers to the current call stack entry, then advance the call stack pointer. Then we fetch the address we are branching execution to, and overwriting the instruction pointer with it (this is how we effect the branch). We set the frame pointer to the current stack pointer, so that we can use relative offsets to refer to local variables.
Next we implement RETN, a straight return with no return value:
case RETN:
csp--;
ip = callstack[csp]._ip;
sp = callstack[csp]._sp;
fp = callstack[csp]._fp;
#ifdef DEBUG
printf("RETN\n");
#endif
break;
Figure 8: astridvm.c
This simple and easy. We restore the control registers from the top of the call stack, which places us back where we came from. We now resume execution from the point of branching.
Finally we have RETV, or return-with-value, which takes an operand that references a local stack value (relative to the frame pointer):
case RETV:
csp--;
sp = callstack[csp]._sp;
push_offset(*(OFFSET_TYPE*)(stack + fp + fetch_offset()));
ip = callstack[csp]._ip;
fp = callstack[csp]._fp;
#ifdef DEBUG
printf("RETV %d\n", *(OFFSET_TYPE*)(stack+sp));
#endif
break;
Figure 9: astridvm.c
First we restore the stack pointer, but leave in place the frame pointer. This is because we need the push an item (the return value) on the stack, but using an offset of the frame pointer. After that item has been pushed, we can safely replace the frame pointer with its former value (from before the procedure call). Now we have returned to the branch point, with a new return value sitting on top of the stack.
In main(), we need to add CSP to our register initialization:
sp = 0; ip = 0; fp = 0; csp = 0;
Figure 10: astridvm.c
Finally, let’s write a program that demonstrates all the new functionality we have added:
uint16_t program[] = {
PUSH, 1,
POP,
PUSH, 5,
CALL, 24,
POP, // Pop what was on the stack before we called Func 1 (5)
CALL, 36,
POP, // Pop the return value of Func 2 (75)
HALT,
PUSH, 55, // Func 1
PUSH, 65,
POP,
RETN,
PUSH, 75, // Func 2
PUSH, 0, // Setting up locals
PUSH, 0,
RETV, 0, // Use the first local variable as the return value.
};
$ ./astridvm PUSH[sp=2] 1 POP[sp=0] 1 PUSH[sp=2] 5 CALL 24 PUSH[sp=4] 55 PUSH[sp=6] 65 POP[sp=4] 65 RETN POP[sp=0] 5 CALL 36 PUSH[sp=2] 75 PUSH[sp=4] 0 PUSH[sp=6] 0 RETV 0 POP[sp=0] 75 HALT
Figure 12: output
Everything looks to be in proper working order. We now have functioning procedure calls and a call stack, which puts us ahead of most demonstrative toy VM’s. A little more work, and AstridVM won’t be a toy anymore.
Next Steps
Notice how in our sample program, we used numbers to define our CALL targets. These numbers were determined by manually counting the bytes up to the procedure implementations. This is both laborious and fragile; adding or removing any instruction, anywhere, would require us to recount all of our procedure addresses.
Simply put, we have exhausted the capabilities of program[] as a suitable test-bed for AstridVM. It’s now time to write a proper assembler that will compute these addresses for us: AstridASM, which will be what Part 3 of this series will be devoted to.