Implement the worlds worst register machine

2 files changed, 109 insertions, 32 deletions

diff --git a/src/badlib.h b/src/badlib.h
index 25bb92b..522e4bb 100644
--- a/src/badlib.h
+++ b/src/badlib.h
@@ -920,9 +920,12 @@ typedef struct ArrayHeader {
 #define array_cap(ARR) ((ARR) ? array_head(ARR)->cap : 0)
 
 // Initialize a dynamic array ARR with N elements. The initialization doesn't
-// zero out the data, so thread carefully..
+// zero out the data, so thread carefully. Use array_zero instead if that's what
+// you need.
 #define array_init(ARR, N, ARENA) \
     ((ARR) = _array_reserve(N, sizeof(*(ARR)), (ARENA)))
+#define array_zero(ARR, N, ARENA) \
+    ((ARR) = _array_reserve_zero(N, sizeof(*(ARR)), (ARENA)))
 
 // Push a given element T to the dynamic array ARR.
 #define array_push(ARR, T, ARENA)                          \
@@ -953,6 +956,15 @@ _array_reserve(sz num_elem, sz type_size, Arena *a) {
 }
 
 static inline void *
+_array_reserve_zero(sz num_elem, sz type_size, Arena *a) {
+    u8 *p = arena_calloc(num_elem * type_size + sizeof(ArrayHeader), a);
+    p += sizeof(ArrayHeader);
+    array_head(p)->size = 0;
+    array_head(p)->cap = num_elem;
+    return p;
+}
+
+static inline void *
 _array_maybe_grow(void *arr, sz type_size, Arena *a) {
     if (!arr) {
         arr = _array_reserve(0, 0, a);
diff --git a/src/main.c b/src/main.c
index a6e1cf6..2c24eaf 100644
--- a/src/main.c
+++ b/src/main.c
@@ -22,9 +22,9 @@ init(void) {
 }
 
 typedef struct Instruction {
+    u8 dst;
     u8 a;
     u8 b;
-    u8 c;
     u8 op;
 } Instruction;
 
@@ -44,20 +44,29 @@ typedef struct Chunk {
 
 typedef enum OpCode {
     OP_HALT,
-    OP_ADD_INT,
+    OP_INT_ADD,
+    OP_INT_SUB,
+    OP_INT_MUL,
+    OP_INT_DIV,
+    OP_INT_MOD,
 } OpCode;
 
 Str op_str[] = {
-    [OP_HALT]    = cstr("HALT   "),
-    [OP_ADD_INT] = cstr("ADD    "),
+    [OP_HALT] = cstr("HALT   "),    [OP_INT_ADD] = cstr("ADD    "),
+    [OP_INT_SUB] = cstr("SUB    "), [OP_INT_MUL] = cstr("MUL    "),
+    [OP_INT_DIV] = cstr("DIV    "), [OP_INT_MOD] = cstr("MOD    "),
 };
 
 void
 disassemble_instruction(Instruction instruction) {
     switch (instruction.op) {
-        case OP_ADD_INT:
-            println("%s %d %d %d", op_str[instruction.op], instruction.a,
-                    instruction.b, instruction.c);
+        case OP_INT_SUB:
+        case OP_INT_MUL:
+        case OP_INT_DIV:
+        case OP_INT_MOD:
+        case OP_INT_ADD:
+            println("%s %d %d %d", op_str[instruction.op], instruction.dst,
+                    instruction.a, instruction.b);
             break;
         case OP_HALT: println("%s", op_str[instruction.op]); break;
         default: println("Unknown opcode %d", instruction.op); break;
@@ -79,9 +88,10 @@ disassemble_chunk(Chunk chunk) {
     }
 }
 
+#define N_CONST 256
 typedef struct VM {
     Chunk *chunk;
-    Constant regs[256];
+    Constant regs[N_CONST];
     Instruction *ip;
 } VM;
 
@@ -89,8 +99,9 @@ void
 vm_init(VM *vm, Chunk *chunk) {
     assert(vm);
     assert(chunk);
+    assert(chunk->code);
     vm->chunk = chunk;
-    for (sz i = 0; i < array_size(chunk->constants); i++) {
+    for (sz i = 0; i < N_CONST; i++) {
         vm->regs[i] = chunk->constants[i];
     }
     vm->ip = vm->chunk->code;
@@ -98,6 +109,9 @@ vm_init(VM *vm, Chunk *chunk) {
 
 void
 vm_run(VM *vm) {
+    assert(vm);
+    assert(vm->chunk);
+    assert(vm->ip);
     println("VM running...");
     while (true) {
         Instruction instruction = *vm->ip++;
@@ -106,19 +120,79 @@ vm_run(VM *vm) {
         disassemble_instruction(instruction);
 #endif
         switch (instruction.op) {
-            case OP_ADD_INT: {
-                u8 dst = instruction.a;
-                u8 src_a = instruction.b;
-                u8 src_b = instruction.c;
-                vm->regs[dst].u = vm->regs[src_a].u + vm->regs[src_b].u;
+            // TODO: Other numeric types
+            case OP_INT_ADD: {
+                u8 dst = instruction.dst;
+                u8 src_a = instruction.a;
+                u8 src_b = instruction.b;
+                vm->regs[dst].i = vm->regs[src_a].i + vm->regs[src_b].i;
+            } break;
+            case OP_INT_SUB: {
+                u8 dst = instruction.dst;
+                u8 src_a = instruction.a;
+                u8 src_b = instruction.b;
+                vm->regs[dst].i = vm->regs[src_a].i - vm->regs[src_b].i;
+            } break;
+            case OP_INT_MUL: {
+                u8 dst = instruction.dst;
+                u8 src_a = instruction.a;
+                u8 src_b = instruction.b;
+                vm->regs[dst].i = vm->regs[src_a].i * vm->regs[src_b].i;
+            } break;
+            case OP_INT_DIV: {
+                u8 dst = instruction.dst;
+                u8 src_a = instruction.a;
+                u8 src_b = instruction.b;
+                vm->regs[dst].i = vm->regs[src_a].i / vm->regs[src_b].i;
+            } break;
+            case OP_INT_MOD: {
+                u8 dst = instruction.dst;
+                u8 src_a = instruction.a;
+                u8 src_b = instruction.b;
+                vm->regs[dst].i = vm->regs[src_a].i % vm->regs[src_b].i;
             } break;
             case OP_HALT: {
                 return;
             }
+            default: {
+                eprintln("unimplemented OP code: %d", instruction.op);
+                return;
+            }
         }
     }
 }
 
+sz reg_idx = 0;
+sz compile_expr(Chunk *chunk, Node *node, Arena *a);
+
+sz
+compile_binary(OpCode op, Chunk *chunk, Node *node, Arena *a) {
+    sz reg_a = compile_expr(chunk, node->left, a);
+    sz reg_b = compile_expr(chunk, node->right, a);
+    sz reg_dst = reg_idx++;
+    Instruction inst =
+        (Instruction){.op = op, .dst = reg_dst, .a = reg_a, .b = reg_b};
+    array_push(chunk->code, inst, a);
+    return reg_dst;
+}
+
+sz
+compile_expr(Chunk *chunk, Node *node, Arena *a) {
+    switch (node->kind) {
+        case NODE_ADD: return compile_binary(OP_INT_ADD, chunk, node, a); break;
+        case NODE_SUB: return compile_binary(OP_INT_SUB, chunk, node, a); break;
+        case NODE_MUL: return compile_binary(OP_INT_MUL, chunk, node, a); break;
+        case NODE_DIV: return compile_binary(OP_INT_DIV, chunk, node, a); break;
+        case NODE_MOD: return compile_binary(OP_INT_MOD, chunk, node, a); break;
+        case NODE_NUM_INT: {
+            chunk->constants[reg_idx] = (Constant){.i = node->value.i};
+            return reg_idx++;
+        } break;
+        default: break;
+    }
+    return -1;
+}
+
 void
 process_file(Str path) {
     Arena lexer_arena = arena_create(LEXER_MEM, os_allocator);
@@ -181,30 +255,21 @@ process_file(Str path) {
     }
     // TODO: Semantic analysis.
     // TODO: Type checking.
-    // TODO: Compile roots.
+
+    // Compile roots.
+    Arena bytecode_arena = arena_create(LEXER_MEM, os_allocator);
+    Chunk chunk = {.file_name = path};
+    array_zero(chunk.constants, 256, &bytecode_arena);
+    array_zero(chunk.code, 0xffff, &bytecode_arena);
     sz n_roots = array_size(parser.nodes);
     for (sz i = 0; i < n_roots; i++) {
         // The parser stores the root nodes as a stack.
         Node *root = parser.nodes[i];
-        // compile_expr(Node *root)
-        (void)root;
+        compile_expr(&chunk, root, &bytecode_arena);
     }
-
-    // Run bytecode on VM.
-    Arena bytecode_arena = arena_create(LEXER_MEM, os_allocator);
-    Chunk chunk = {.file_name = path};
-    array_init(chunk.constants, 256, &bytecode_arena);
-    array_init(chunk.code, 0xffff, &bytecode_arena);
-
-    // FIXME: Some debugging instructions for now.
-    array_push(chunk.constants, (Constant){.u = 1}, &bytecode_arena);
-    array_push(chunk.constants, (Constant){.u = 2}, &bytecode_arena);
-    Instruction add = (Instruction){.op = OP_ADD_INT, .a = 2, .b = 0, .c = 1};
-    array_push(chunk.code, add, &bytecode_arena);
     array_push(chunk.code, (Instruction){.op = OP_HALT}, &bytecode_arena);
-    disassemble_chunk(chunk);
 
-    // Testing VM execution here.
+    // Run bytecode on VM.
     VM vm = {0};
     vm_init(&vm, &chunk);
     println("VM REGISTERS BEFORE:\n%{Mem}",