Virtual Machine

To ease ourselves from the complexity of a real computer, I decided we will run our program on a virtual machine. A simple virtual machine is really easy to build.

Architecture

The virtual machine we will build has two memory units. A memory unit will store the instructions. Each instruction will have its own address. Another memory unit will store our stack, the stack has 10,000 cells and each cell can store a single integer/code address.

The machine has two special purpose registers, ip is used to point to the next instruction to be executed, sp is used to point to the top of the stack. It has four general purpose register R1 to R4.

Application Binary Interface

An application binary interface is an interface a system (i.e. machine and operating system) requires application to follows. This typically include register usage, function calling convention and stack usage, etc.

Our rules are simple:

• Any function can use any registers,
• None of the general purpose registers are preserved across function call (i.e. they are volatile/caller save),
• R1 is used to pass the first and only argument,
• R2 is used to pass the first and only return,
• The first instruction must be used to reserve stack space, no other instruction (except the final return) should ever change the stack pointer value.

These rules are modeled after the Windows x64 ABI, with a lot of simplification, but the essence is similar.

Instruction set

Here is a listing of the instructions:

load destination_register, address
load_immediate destination_register, value
compare destination_register, operand_register_1, operand_register_2
store source_register, address
branch_on_zero operand_register, address
branch address
plus destination_register, operand_register_1, operand_register_2
minus destination_register, operand_register_1, operand_register_2
call address
return
push stack_space_to_reserve
pop stack_space_to_reserve
print
break

Interface

class virtual_machine
{
public:
    virtual_machine();
    void run(instruction_sequence instructions, int entry_point);
entry_point);
};

Interface explained

The virtual machine take the instruction sequence, the entry point, and then it will run to completion.

Implementation

It is a lot of code to write the virtual machine to process all these instructions, but they are all trivial code to write. In my implementation, I emulated a call from -1 to the entry point, and therefore we know exactly when does the program completes. Be prepare to debug your code generator - it is quite likely that you have not generated good code!

Practical notes

This is a typical interpreter implementation, nothing special, except this is so inefficient that most people do not write code like this. Most practical virtual machine would try to optimize the code, make less function calls by bundling them into a single big switch statements, hijacking return address to run the next instruction directly, and even JIT compile the instructions. Here we simply make a simplest possible virtual machine. This is to make the latter debugging work easy.

Moving forward

With the completion of the virtual machine, we can now conclude part I. In the next part, we will get into our main topic, debugging.