.. Decision Copyright (C) 2019-2020 Benjamin Beddows This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . .. _the-virtual-machine: ******************* 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 :ref:`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: .. doxygenfunction:: d_vm_ins_size :no-link: 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 ================= 1. Push the arguments to the calling code in order, i.e. push the first argument, then the second, etc. 2. Either push the pointer to the calling code, or call with the pointer in an immediate, depending on the opcode used. 3. Set the program counter of the VM to the pointer provided in step 2. 4. 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. 5. 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 =================== 1. Push the return values in reverse order, i.e. the last return value first, and the first return value last. 2. 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. 3. Set the program counter by getting the value pointed at by the current frame pointer. 4. 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. 5. 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: .. doxygenfunction:: d_vm_create :no-link: To run code with the VM, use: .. doxygenfunction:: d_vm_run :no-link: If you want to dump the state of the VM at any time, including the contents of its stack, use: .. doxygenfunction:: d_vm_dump :no-link: If you want to reuse the VM to run some more code, use: .. doxygenfunction:: d_vm_reset :no-link: If you want to free the VM from memory, run: .. doxygenfunction:: d_vm_free :no-link: Stack Functions =============== Counting values --------------- If you want to get the number of items in the current stack frame, use: .. doxygenfunction:: d_vm_frame :no-link: If you want to get the number of items in the entire stack, use: .. doxygenfunction:: d_vm_top :no-link: Getting values -------------- If you want to retrieve values from the stack without manipulating the stack, use: .. doxygenfunction:: d_vm_get :no-link: .. doxygenfunction:: d_vm_get_float :no-link: .. doxygenfunction:: d_vm_get_ptr :no-link: Inserting values ---------------- If you want to insert items into the stack at a given index (not nessesarily at the top of the stack), use: .. doxygenfunction:: d_vm_insert :no-link: .. doxygenfunction:: d_vm_insert_float :no-link: .. doxygenfunction:: d_vm_insert_ptr :no-link: Poping values ------------- If you want to pop values from the top of the stack, use: .. doxygenfunction:: d_vm_pop :no-link: .. doxygenfunction:: d_vm_pop_float :no-link: .. doxygenfunction:: d_vm_pop_ptr :no-link: If you want to pop a variable number of items from the stack without getting their values, use: .. doxygenfunction:: d_vm_popn :no-link: Pushing values -------------- If you want to push values to the top of the stack, use: .. doxygenfunction:: d_vm_push :no-link: .. doxygenfunction:: d_vm_push_float :no-link: .. doxygenfunction:: d_vm_push_ptr :no-link: If you want to push a variable number of `0`s to the top of the stack, use: .. doxygenfunction:: d_vm_pushn :no-link: Removing values --------------- If you want to remove a value from the stack (not nessesarily from the top), use: .. doxygenfunction:: d_vm_remove :no-link: If you want to remove a subsection of the stack, use: .. doxygenfunction:: d_vm_remove_len :no-link: Setting values -------------- If you want to set a value in the stack (not nessesarily at the top), use: .. doxygenfunction:: d_vm_set :no-link: .. doxygenfunction:: d_vm_set_float :no-link: .. doxygenfunction:: d_vm_set_ptr :no-link: