Skip to content

Instantly share code, notes, and snippets.

@leddoo
Created December 29, 2022 11:03
Show Gist options
  • Save leddoo/25f307f55bb233fd6f2f900c52fe9367 to your computer and use it in GitHub Desktop.
Save leddoo/25f307f55bb233fd6f2f900c52fe9367 to your computer and use it in GitHub Desktop.
a very simple register vm
// a very minimal instruction set.
// it has just enough operations to implement a recursive
// fibonacci function - what a coincidence :D
// NOTE: in my VM, i don't use an `enum`.
// this is just for simplicity.
#[derive(Clone, Copy, Debug)]
enum Instruction {
LoadInt { dst: u8, value: i16 },
Copy { dst: u8, src: u8 },
Add { dst: u8, src1: u8, src2: u8 },
Sub { dst: u8, src1: u8, src2: u8 },
Call { func: u8, arg: u8, dst: u8 },
Return { src: u8 },
JumpNotLess { target: u8, src1: u8, src2: u8 },
}
struct Function {
code: Vec<Instruction>,
// NOTE: each function must specify how many registers
// it needs ahead of time.
num_registers: usize,
}
struct Vm {
// the vm technically supports multiple functions.
// though this example only uses a single function.
functions: Vec<Function>,
// this is where the "registers" are stored.
// when a function is called,
// - the current top of the stack becomes its "base pointer".
// - `num_registers` many zero values are pushed onto the stack.
// - the argument is copied to register zero.
stack: Vec<i64>,
}
impl Vm {
pub fn new() -> Vm {
Vm {
functions: vec![],
stack: vec![],
}
}
pub fn call(&mut self, func: u8, arg: i64) -> i64 {
let func = func as usize;
// prepare the stack (registers).
let base_pointer = self.stack.len();
{
let function = &self.functions[func];
let stack_top = base_pointer + function.num_registers;
// initialize registers to zero.
self.stack.resize(stack_top, 0);
// write the argument to register `0`.
self.stack[base_pointer] = arg;
}
// NOTE: this function's registers are
// `self.stack[base_pointer..]`
// see the `reg` utility function.
// abbreviation to save typing :)
let bp = base_pointer;
// index of the next instruction to be executed.
let mut program_counter = 0;
loop {
// fetch the next instruction.
let func = &self.functions[func];
let instr = func.code[program_counter];
program_counter += 1;
// uncomment to get spammed.
//println!("executing {:?}", instr);
use Instruction::*;
match instr {
LoadInt { dst, value } => {
*self.reg(bp, dst) = value as i64;
}
Copy { dst, src } => {
*self.reg(bp, dst) = *self.reg(bp, src);
}
Add { dst, src1, src2 } => {
*self.reg(bp, dst) = *self.reg(bp, src1) + *self.reg(bp, src2);
}
Sub { dst, src1, src2 } => {
*self.reg(bp, dst) = *self.reg(bp, src1) - *self.reg(bp, src2);
}
Call { func, arg, dst } => {
// NOTE: in this example, calls are simply implemented
// using recursion.
// real VMs usually implement a "custom call stack".
let arg = *self.reg(bp, arg);
let result = self.call(func, arg);
*self.reg(bp, dst) = result;
}
Return { src } => {
let result = *self.reg(bp, src);
// pop the function's registers from the stack.
self.stack.truncate(base_pointer);
return result;
}
JumpNotLess { target, src1, src2 } => {
let src1 = *self.reg(bp, src1);
let src2 = *self.reg(bp, src2);
if !(src1 < src2) {
program_counter = target as usize;
}
}
}
}
}
// returns a reference to the register `index`,
// in the current function's stack frame.
fn reg(&mut self, base_pointer: usize, index: u8) -> &mut i64 {
&mut self.stack[base_pointer + index as usize]
}
}
fn main() {
let mut vm = Vm::new();
// fib(n) = n if (n < 2) else fib(n-2) + fib(n-1)
let fib = 0; // function index `0`
vm.functions.push(Function {
code: {
// registers:
let n = 0;
let two = 1;
let one = 2;
let temp = 3;
let recursive_1 = 4;
let recursive_2 = 5;
let result = 6;
use Instruction::*;
vec![
// 0
LoadInt { dst: two, value: 2 },
// 1: if !(n < 2) then jump to else
JumpNotLess { target: 3, src1: n, src2: two },
// 2, then:
Return { src: n },
// 3, else:
// recursive_1 = fib(n-2)
Sub { dst: temp, src1: n, src2: two },
Call { func: fib, arg: temp, dst: recursive_1 },
// recursive_2 = fib(n-1)
LoadInt { dst: one, value: 1 },
Sub { dst: temp, src1: n, src2: one },
Call { func: fib, arg: temp, dst: recursive_2 },
// return recursive_1 + recursive_2
Add { dst: result, src1: recursive_1, src2: recursive_2 },
Return { src: result },
]
},
num_registers: 7,
});
for i in 0..10 {
println!("fib({}) = {}", i, vm.call(fib, i));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment