The Virtual Machine¶

This chapter describes the specification of the Decision Virtual Machine. It is defined in the files dvm.c and dvm.h.

Its job is to run the bytecode generated from Code Generation.

The Structure¶

Note

dint == int32_t if the macro DECISION_32 is defined. Otherwise, dint == int64_t.

The Decision VM, DVM, is defined in dvm.h. It has the following properties:

A program counter pc, which is a char*.

Note

The program counter pc increments after every instruction that does not change the value of the program counter, e.g. jumping, returning or calling does not increment the program counter.

A generic stack, which the VM uses to store all of its working values, and is also used as the call stack.
- basePtr stores a pointer to the bottom of the stack.
- stackPtr stores a pointer to the top of the stack.
- framePtr stores a pointer to the start of the stack frame.
2 flags:
- A halted flag, which states if the VM has stopped executing.
- A runtimeError flag, which states if there was an error during execution.

Instruction Format¶

All instructions vary in size. You can find out the size of an instruction by using the function:

unsigned char d_vm_ins_size(DIns opcode)

Given an opcode, get the total size of the instruction involving that opcode in bytes.

Return

The size of the instruction in bytes. 0 if the opcode doesn’t exist.

Parameters

opcode: The opcode to query.

Opcodes¶

Opcodes are stored as a single byte, in the most significant byte of the instruction.

The Stack¶

Unlike how traditional low-level architectures work, where they have several registers and a call stack, this VM does not have any registers. All of the values generated by the program are stored in the VM’s stack. Most instructions will then work with the values poped from the top of the stack, and push back the result.

However, when we say the VM has a stack, it isn’t truly a “stack”, in that you can do more than push and pop from it. It is essentially a dynamically allocated array, in that sense.

Immediates¶

To optimise the number of operations on the stack, there are some instructions that allow you to take shortcuts in the form of immediates. Instead of pushing a constant value onto the stack and then using it to operate on another value in the stack, you can operate on the one stack value in one instruction, with the constant represented as an immediate.

Immediates come in three sizes:

Byte: 1 byte.
Half: Half the word size of the architecture.
Full: The word size of the architecture.

When we say the word size of the architecture, we mean sizeof(dint) in bytes.

Immediates always come after the opcode, and there can be more than one of them.

Note

Floating-point constants cannot be represented as immediates, except for when you are pushing them to the stack, since that’s the only way they can get on the stack.

Diagrams¶

Here are some example diagrams with the instructions represented in big-endian format.

ADD // push(pop() + pop()):

0
+-----+
| 0x2 |
+-----+

SUBHI // push(pop() - I(|M|/2)) in 32-bit:

2      1     0
+------+-----+-----+
| 0x4F | IMMEDIATE |
+------+-----+-----+

CALLRH // pc += I(|M|/2); push(stackFrame w/ I(1) arguments) in 64-bit:

5      4    3    2     1    0
+------+----+----+-----+----+-----------+
| 0x11 |      IMMEDIATE     | IMMEDIATE |
+------+----+----+-----+----+-----------+

JRFI // pc += I(|M|) in 64-bit:

8      7    6    5    4    3    2    1    0
+------+----+----+----+----+----+----+----+----+
| 0x31 |               IMMEDIATE               |
+------+----+----+----+----+----+----+----+----+

Action Syntax¶

Next to each opcode in dvm.h is a description of what the opcode does, and how to write the instruction. The examples above have their descriptions as they appear in the comments. This section describes what the syntax of those descriptions are.

push(item) and pop() are self-explanitory, they push and pop the stack respectively.
pushFloat(float) and popFloat() push and pop in floating-point format to distinguish from integers.
I(n) means an immediate of n bytes.
- |M| means the architecture word size, i.e. sizeof(dint).
pop(stackFrame w/ n return values) means the VM will pop the entire stack frame, but will leave the top n elements alone to act as return values.
push(stackFrame w/ n arguments) means the VM will create a new stack frame, and will leave the top n elements at the top of the stack to act as arguments.
pc means the program counter.
syscall(call, arg0, arg1, arg2) means run a system call call with the 3 given arguments.

Stack Frames¶

The VM has the ability to “call” other sections of bytecode, but we want the calling code to have it’s own frame in the stack, such that the calling code only manipulates the stack within its frame, and once the calling code returns execution, the entire frame disappears from the stack.

Note

The current stack frame is described as the section that is bounded by the frame pointer at the bottom, and the stack pointer at the top.

Calling Procedure¶

Push the arguments to the calling code in order, i.e. push the first argument, then the second, etc.
Either push the pointer to the calling code, or call with the pointer in an immediate, depending on the opcode used.
Set the program counter of the VM to the pointer provided in step 2.
Insert two values before the arguments in the stack: the first being the current difference between the frame pointer and the base of the stack, and the second being the return address.
Set the current frame pointer to point to where the program counter was saved, i.e. the value above the new frame pointer should be the first argument.

Returning Procedure¶

Push the return values in reverse order, i.e. the last return value first, and the first return value last.
If the frame pointer is pointing to an invalid memory location (e.g. the location just before the start of the stack, which is what its starting position is), then halt the VM, as this must be the starting stack frame. Otherwise, move to step 3.
Set the program counter by getting the value pointed at by the current frame pointer.
Set the frame pointer by getting the value below the one pointed at by the current frame pointer, and adding it onto the base of the stack.
Remove all of the values inbetween the saved frame pointer, up to the top of stack, except for the top n values, which will be the return values.

System Calls¶

With the SYSCALL opcode, you can make system calls for extra functionality. All of the types of system calls you can make are defined in an enumerator called DSyscall in dvm.h. Next to each system call in dvm.h is a specification of how the value of each argument register will affect the action.

When generating bytecode, it will always push the arguments before making the system call.

Implementation¶

VM Functions¶

To create a virtual machine, use:

DVM d_vm_create()

Create a Decision VM in its starting state, with malloc’d elements.

Return: A Decision VM in its starting state.

To run code with the VM, use:

bool d_vm_run(DVM *vm, void *start)

Get a virtual machine to start running instructions in a loop, until it is halted.

Return

If it ran without any runtime errors.

Parameters

vm: The VM to run the bytecode in.
start: A pointer to the start of the bytecode to execute.

If you want to dump the state of the VM at any time, including the contents of its stack, use:

void d_vm_dump(DVM *vm)

Dump the contents of a Decision VM to stdout for debugging.

Parameters

vm: The VM to dump the contents of.

If you want to reuse the VM to run some more code, use:

void d_vm_reset(DVM *vm)

Reset a Decision VM to its starting state.

Parameters

vm: A Decision VM to set to its starting state.

If you want to free the VM from memory, run:

void d_vm_free(DVM *vm)

Free the malloc’d elements of a Decision VM. Note that this makes the VM unusable unless you call d_vm_reset on it.

Parameters

vm: The Decision VM to free.

Stack Functions¶

Counting values¶

If you want to get the number of items in the current stack frame, use:

size_t d_vm_frame(DVM *vm)

Get the number of elements in the current stack frame.

Return

The number of elements in the stack frame.

Parameters

vm: The VM whose stack to query.

If you want to get the number of items in the entire stack, use:

size_t d_vm_top(DVM *vm)

Get the number of elements in the stack.

Return

The number of elements in the stack.

Parameters

vm: The VM whose stack to query.

Getting values¶

If you want to retrieve values from the stack without manipulating the stack, use:

dint d_vm_get(DVM *vm, dint index)

Get an integer from a value in the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Return

The integer value of the stack at the given index.

Parameters

vm: The VM whose stack to retrieve from.
index: The index of the stack.

dfloat d_vm_get_float(DVM *vm, dint index)

Get a float from a value in the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Return

The float value of the stack at the given index.

Parameters

vm: The VM whose stack to retrieve from.
index: The index of the stack.

void *d_vm_get_ptr(DVM *vm, dint index)

Get a pointer from a value in the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Return

The pointer value of the stack at the given index.

Parameters

vm: The VM whose stack to retrieve from.
index: The index of the stack.

Inserting values¶

If you want to insert items into the stack at a given index (not nessesarily at the top of the stack), use:

void d_vm_insert(DVM *vm, dint index, dint value)

Insert an integer into the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Parameters

vm: The VM whose stack to insert to.
index: The index of the stack to insert to, i.e. value will be at this location when the function returns.
value: The value to insert into the stack.

void d_vm_insert_float(DVM *vm, dint index, dfloat value)

Insert a float into the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Parameters

vm: The VM whose stack to insert to.
index: The index of the stack to insert to, i.e. value will be at this location when the function returns.
value: The value to insert into the stack.

void d_vm_insert_ptr(DVM *vm, dint index, void *ptr)

Insert a pointer into the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Parameters

vm: The VM whose stack to insert to.
index: The index of the stack to insert to, i.e. ptr will be at this location when the function returns.
ptr: The pointer to insert into the stack.

Poping values¶

If you want to pop values from the top of the stack, use:

dint d_vm_pop(DVM *vm)

Pop an integer from the top of the stack.

Return

The integer at the top of the stack.

Parameters

vm: The VM whose stack to pop from.

dfloat d_vm_pop_float(DVM *vm)

Pop a float from the top of the stack.

Return

The float at the top of the stack.

Parameters

vm: The VM whose stack to pop from.

void *d_vm_pop_ptr(DVM *vm)

Pop a pointer from the top of the stack.

Return

The pointer at the top of the stack.

Parameters

vm: The VM whose stack to pop from.

If you want to pop a variable number of items from the stack without getting their values, use:

void d_vm_popn(DVM *vm, size_t n)

Pop n elements from the stack.

Parameters

vm: The VM whose stack to pop from.
n: The number of elements to pop.

Pushing values¶

If you want to push values to the top of the stack, use:

void d_vm_push(DVM *vm, dint value)

Push an integer value onto the stack.

Parameters

vm: The VM whose stack to push onto.
value: The value to push onto the stack.

void d_vm_push_float(DVM *vm, dfloat value)

Push a float value onto the stack.

Parameters

vm: The VM whose stack to push onto.
value: The value to push onto the stack.

void d_vm_push_ptr(DVM *vm, void *ptr)

Push a pointer onto the stack.

Parameters

vm: The VM whose stack to push onto.
ptr: The pointer to push onto the stack.

If you want to push a variable number of `0`s to the top of the stack, use:

void d_vm_pushn(DVM *vm, size_t n)

Push 0 onto the stack n times.

Parameters

vm: The VM whose stack to push onto.
n: The number of items to push onto the stack.

Removing values¶

If you want to remove a value from the stack (not nessesarily from the top), use:

void d_vm_remove(DVM *vm, dint index)

Remove the value from the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Parameters

vm: The VM whose stack to remove from.
index: The index to remove from the stack.

If you want to remove a subsection of the stack, use:

void d_vm_remove_len(DVM *vm, dint index, size_t len)

Remove a number of values from the stack, starting at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Parameters

vm: The VM whose stack to remove from.
index: The index to start removing from the stack.
len: The number of items to remove from the stack.

Setting values¶

If you want to set a value in the stack (not nessesarily at the top), use:

void d_vm_set(DVM *vm, dint index, dint value)

Set the value of an element in the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Parameters

vm: The VM whose stack to set the element of.
index: The index of the stack.
value: The value to set.

void d_vm_set_float(DVM *vm, dint index, dfloat value)

Set the value of an element in the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Parameters

vm: The VM whose stack to set the element of.
index: The index of the stack.
value: The value to set.

void d_vm_set_ptr(DVM *vm, dint index, void *ptr)

Set the value of an element in the stack at a particular index.

If index is positive, it will index relative to the start of the stack frame.
If index is non-positive, it will index relative to the top of the stack.

Parameters

vm: The VM whose stack to set the element of.
index: The index of the stack.
ptr: The value to set.