aboutsummaryrefslogtreecommitdiff
path: root/vm/src
diff options
context:
space:
mode:
author3gg <3gg@shellblade.net>2023-03-02 20:03:52 -0800
committer3gg <3gg@shellblade.net>2023-03-02 20:03:52 -0800
commit664006b1c42aae84a3c749d9b71c1047e0b8ffcf (patch)
treee08f8af944b132742b3bb1d240d8954328e667e5 /vm/src
Initial commit.HEADmain
Diffstat (limited to 'vm/src')
-rw-r--r--vm/src/vm.c402
-rw-r--r--vm/src/vm.h166
2 files changed, 568 insertions, 0 deletions
diff --git a/vm/src/vm.c b/vm/src/vm.c
new file mode 100644
index 0000000..559ad5e
--- /dev/null
+++ b/vm/src/vm.c
@@ -0,0 +1,402 @@
1#include "vm.h"
2
3#include <assert.h>
4#include <stdbool.h>
5#include <stdio.h>
6#include <stdlib.h>
7
8// TODO: Make all these arguments of vm_new().
9
10// Program's main memory stack size.
11#define PROGRAM_STACK_SIZE (64 * 1024)
12
13// Locals stack size.
14#define LOCALS_STACK_SIZE 1024
15
16// Frame stack size.
17#define FRAME_STACK_SIZE (16 * 1024)
18
19// Block stack size.
20#define BLOCK_STACK_SIZE 1024
21
22#define IMPLICIT_LABEL -1
23
24// Locals index.
25typedef size_t Index;
26
27// Bools are internally I32s. 0 = false, non-zero = true.
28static Type Bool = I32;
29typedef int32_t bool_t;
30
31/// Function frame.
32///
33/// Every Frame implicitly starts a Block. The function's locals are inside this
34/// implicit block.
35typedef struct Frame {
36 Label label;
37} Frame;
38
39/// A block of code, used for control flow.
40///
41/// Blocks have a label that the machine can jump to. Jumps are constrained to
42/// the block labels that are in scope.
43///
44/// Block termination automatically frees the block's locals.
45typedef struct Block {
46 Label label;
47 size_t addr; // Address (saved program counter) of the block.
48 size_t locals_start; // Offset into the locals stack.
49 size_t locals_size; // Total size in bytes of local variables.
50} Block;
51
52typedef struct Vm {
53 struct {
54 bool exit : 1;
55 } flags;
56 int32_t exit_code;
57 size_t pc; // Program instruction counter.
58 size_t sp; // Program stack pointer. Points to next available slot.
59 size_t lsp; // Locals stack pointer. Points to next available slot.
60 size_t fsp; // Frame stack pointer.
61 size_t bsp; // Block stack pointer. Points to current Block.
62 uint8_t* stack; // Program stack. Program's main memory.
63 uint8_t* locals; // Locals stack. Stores locals for each Block.
64 Frame* frames; // Frame stack for function calls.
65 Block* blocks; // Block stack for control flow.
66} Vm;
67
68Vm* vm_new() {
69 Vm* vm = calloc(1, sizeof(Vm));
70 if (!vm) {
71 goto cleanup;
72 }
73 if (!(vm->stack = calloc(1, PROGRAM_STACK_SIZE))) {
74 goto cleanup;
75 }
76 if (!(vm->locals = calloc(1, LOCALS_STACK_SIZE))) {
77 goto cleanup;
78 }
79 if (!(vm->frames = calloc(FRAME_STACK_SIZE, sizeof(Frame)))) {
80 goto cleanup;
81 }
82 if (!(vm->blocks = calloc(BLOCK_STACK_SIZE, sizeof(Block)))) {
83 goto cleanup;
84 }
85 return vm;
86
87cleanup:
88 vm_del(&vm);
89 return 0;
90}
91
92void vm_del(Vm** pVm) {
93 if (pVm && *pVm) {
94 Vm* vm = *pVm;
95 if (vm->stack) {
96 free(vm->stack);
97 }
98 if (vm->locals) {
99 free(vm->locals);
100 }
101 if (vm->frames) {
102 free(vm->frames);
103 }
104 if (vm->blocks) {
105 free(vm->blocks);
106 }
107 free(vm);
108 *pVm = 0;
109 }
110}
111
112// static size_t get_size(Type type) {
113// switch (type) {
114// case I32:
115// return sizeof(int32_t);
116// }
117// assert(false);
118// return 0;
119// }
120
121// TODO: Not used?
122#define VM_ASSERT(expr) \
123 {}
124
125#define TOP(vm, type) \
126 (assert(vm->sp >= sizeof(type)), \
127 *((const type*)&vm->stack[vm->sp - sizeof(type)]))
128
129#define PUSH(vm, value, type) \
130 assert(vm->sp + sizeof(type) <= PROGRAM_STACK_SIZE); \
131 *((type*)(&vm->stack[vm->sp])) = value; \
132 vm->sp += sizeof(type);
133
134#define POP(vm, type) \
135 (assert(vm->sp >= sizeof(type)), vm->sp -= sizeof(type), \
136 *((type*)(&vm->stack[vm->sp])))
137
138#define BLOCK_PUSH(vm, block) \
139 assert(vm->bsp < BLOCK_STACK_SIZE); \
140 vm->blocks[++vm->bsp] = block;
141
142#define BLOCK_POP(vm) \
143 assert(vm->bsp > 0); \
144 vm->locals -= vm->blocks[vm->bsp].locals_size; \
145 vm->bsp--;
146
147#define PUSH_LOCAL(vm, type) \
148 assert(vm->lsp + sizeof(type) <= LOCALS_STACK_SIZE); \
149 /* Auto-initialize locals to 0. */ \
150 *((type*)(&vm->locals[vm->lsp])) = 0; \
151 vm->lsp += sizeof(type); \
152 vm->blocks[vm->bsp].locals_size += sizeof(type);
153
154#define POP_LOCAL(vm, type) \
155 (assert(vm->lsp >= sizeof(type)), vm->lsp -= sizeof(type), \
156 vm->blocks[vm->bsp].locals -= sizeof(type), \
157 *((type*)(&vm->locals[vm->lsp])))
158
159// TODO: Should be an offset from the current frame, not block.
160#define GET_LOCAL_PTR(vm, idx, type) \
161 ((const type*)(&vm->locals[vm->blocks[vm->bsp].locals_start + idx]))
162// TODO: Same here.
163#define GET_LOCAL_PTR_MUT(vm, idx, type) \
164 ((type*)(&vm->locals[vm->blocks[vm->bsp].locals_start + idx]))
165
166#define LOCAL_RD(vm, idx, type) (*GET_LOCAL_PTR(vm, idx, type))
167
168#define LOCAL_WR(vm, idx, val, type) (*GET_LOCAL_PTR_MUT(vm, idx, type) = val)
169
170static void push(Vm* vm, Inst inst) {
171 switch (inst.type) {
172 case I32:
173 PUSH(vm, inst.payload.i32, int32_t);
174 break;
175 case F32:
176 PUSH(vm, inst.payload.f32, float);
177 break;
178 }
179}
180
181static Value pop(Vm* vm, Type type) {
182 Value val;
183 switch (type) {
184 case I32:
185 val.i32 = POP(vm, int32_t);
186 break;
187 case F32:
188 val.f32 = POP(vm, float);
189 break;
190 }
191 return val;
192}
193
194static void vm_exit(Vm* vm, Inst inst) {
195 vm->exit_code = vm->sp == 0 ? 0 : POP(vm, int32_t);
196 vm->flags.exit = true;
197}
198
199#define ADD(vm, a, b, field, type) \
200 { \
201 type result = ((a.field) + (b.field)); \
202 PUSH(vm, result, type); \
203 }
204
205static void add(Vm* vm, Type type) {
206 Value opr1 = pop(vm, type);
207 Value opr2 = pop(vm, type);
208 switch (type) {
209 case I32:
210 ADD(vm, opr1, opr2, i32, int32_t);
211 break;
212
213 case F32:
214 ADD(vm, opr1, opr2, f32, float);
215 break;
216 }
217}
218
219static void dec(Vm* vm, Type type) {
220 Value top = pop(vm, type);
221 switch (type) {
222 case I32:
223 PUSH(vm, top.i32 - 1, int32_t);
224 break;
225 case F32:
226 PUSH(vm, top.f32 - 1.0f, float);
227 break;
228 }
229}
230
231static void empty(Vm* vm) { PUSH(vm, vm->sp == 0, bool_t); }
232
233#define CMP(vm, val, type) (POP(vm, type) == val)
234
235static void cmp(Vm* vm, Inst inst) {
236 switch (inst.type) {
237 case I32:
238 PUSH(vm, CMP(vm, inst.payload.i32, int32_t), bool_t);
239 break;
240 case F32:
241 PUSH(vm, CMP(vm, inst.payload.f32, float), bool_t);
242 break;
243 }
244}
245
246static void end(Vm* vm) { BLOCK_POP(vm); }
247
248static void loop(Vm* vm, Inst inst) {
249 const Block block = (Block){.label = inst.payload.i32, .addr = vm->pc};
250 BLOCK_PUSH(vm, block);
251}
252
253static void br(Vm* vm, Inst inst) {
254 const Branch branch = inst.payload.branch;
255 const int32_t label = branch.label;
256 const bool value = branch.expected;
257 const bool is_conditional = branch.conditional;
258 bool should_branch = is_conditional ? POP(vm, bool_t) == value : true;
259 // printf("is conditional: %d\n", is_conditional);
260 // printf("value: %d\n", value);
261 // printf("should branch: %d\n", should_branch);
262 if (should_branch) {
263 while (vm->bsp > 0) {
264 const Block block = vm->blocks[vm->bsp];
265 if (block.label == label) {
266 vm->pc = block.addr;
267 vm->pc--; // Account for increment at every step of the VM loop.
268 return;
269 }
270 vm->bsp--;
271 }
272 // We should be able to find the label in the block stack.
273 assert(false);
274 }
275}
276
277static void vm_break(Vm* vm, Inst inst) {
278 // TODO.
279 // Step over instructions until an End instruction is found.
280}
281
282static void local(Vm* vm, Type type) {
283 switch (type) {
284 case I32:
285 PUSH_LOCAL(vm, int32_t);
286 break;
287 case F32:
288 PUSH_LOCAL(vm, float);
289 break;
290 }
291}
292
293static void local_rd(Vm* vm, Inst inst) {
294 const Index idx = (Index)inst.payload.u64;
295 switch (inst.type) {
296 case I32:
297 PUSH(vm, LOCAL_RD(vm, idx, int32_t), int32_t);
298 break;
299 case F32:
300 PUSH(vm, LOCAL_RD(vm, idx, float), float);
301 break;
302 }
303}
304
305static void local_wr(Vm* vm, Inst inst) {
306 const Index idx = (Index)inst.payload.u64;
307 const Value top = pop(vm, inst.type);
308 switch (inst.type) {
309 case I32:
310 LOCAL_WR(vm, idx, top.i32, int32_t);
311 break;
312 case F32:
313 LOCAL_WR(vm, idx, top.f32, float);
314 break;
315 }
316}
317
318static void exec(Vm* vm, Inst inst) {
319 switch (inst.op) {
320 case Exit:
321 vm_exit(vm, inst);
322 break;
323 case Push:
324 push(vm, inst);
325 break;
326 case Pop:
327 pop(vm, inst.type);
328 break;
329 case Add:
330 add(vm, inst.type);
331 break;
332 case Sub:
333 break;
334 case Mul:
335 break;
336 case Div:
337 break;
338 case Dec:
339 dec(vm, inst.type);
340 break;
341 case Empty:
342 empty(vm);
343 break;
344 case Cmp:
345 cmp(vm, inst);
346 break;
347 case End:
348 end(vm);
349 break;
350 case Break:
351 vm_break(vm, inst);
352 break;
353 case Loop:
354 loop(vm, inst);
355 break;
356 case Br:
357 br(vm, inst);
358 break;
359 case Func: // TODO
360 break;
361 case Arg: // TODO
362 break;
363 case Call: // TODO
364 break;
365 case Local:
366 local(vm, inst.type);
367 break;
368 case LocalRd:
369 local_rd(vm, inst);
370 break;
371 case LocalWr:
372 local_wr(vm, inst);
373 break;
374 }
375}
376
377static void init(Vm* vm) {
378 // Create an implicit frame for the start of the program.
379 vm->frames[0] = (Frame){.label = IMPLICIT_LABEL};
380 vm->blocks[0] = (Block){.label = IMPLICIT_LABEL};
381 // TODO: Reset all Vm state.
382}
383
384int vm_run(Vm* vm, const Inst instructions[], size_t count) {
385 assert(vm);
386 init(vm);
387 for (vm->pc = 0; !vm->flags.exit && vm->pc < count; vm->pc++) {
388 const Inst inst = instructions[vm->pc];
389 exec(vm, inst);
390 }
391 // printf("exit code: %d\n", vm->exit_code);
392 return vm->exit_code;
393}
394
395void vm_print_stack(const Vm* vm) {
396 printf("stack start\n");
397 for (size_t i = 0; i < vm->sp; ++i) {
398 const char sep = (i == vm->sp - 1) ? '\n' : ' ';
399 printf("%x%c", vm->stack[i], sep);
400 }
401 printf("stack end\n");
402}
diff --git a/vm/src/vm.h b/vm/src/vm.h
new file mode 100644
index 0000000..03dfc88
--- /dev/null
+++ b/vm/src/vm.h
@@ -0,0 +1,166 @@
1#pragma once
2
3#include <stdbool.h>
4#include <stddef.h>
5#include <stdint.h>
6
7typedef enum Op {
8 Exit, // Pop value from the stack and return as exit code. Return 0 if the
9 // stack is empty.
10 Push,
11 Pop,
12 Add,
13 Sub,
14 Mul,
15 Div,
16 Dec, // Decrement the top of the stack by 1.
17 Empty, // Check whether the stack is empty. Pushes a bool.
18 Cmp, // Pop the top of the stack and compare it with the payload. Pushes a
19 // bool.
20 /* Blocks */
21 End, // Marks the end of a block.
22 Break, // Exit the current block.
23 Loop, // Push a loop block. Payload (i32): label.
24 /* Branches */
25 Br, // Branch. Payload (i64): [(i32) conditional? | (i32) label].
26 // A condtional branch pops a bool from the stack and branches if true.
27 // The condition can also be negated. See br_if().
28 /* Functions */
29 Func,
30 Arg,
31 Call,
32 /* Locals */
33 Local, // Create a local variable.
34 LocalRd, // Load a local variable into the top of the stack.
35 LocalWr, // Pop the top of the stack and store it in a local variable.
36} Op;
37
38typedef enum Type {
39 I32,
40 F32,
41} Type;
42
43// Label type for blocks and locals.
44typedef uint32_t Label;
45
46typedef struct Branch {
47 Label label;
48 bool conditional : 1; // True for conditional branches.
49 bool expected : 1; // Comparison value for conditional branches.
50} Branch;
51
52typedef struct Function {
53 Label label;
54} Function;
55
56typedef struct Value {
57 union {
58 uint64_t u64;
59 int32_t i32;
60 float f32;
61 Branch branch;
62 Label label;
63 };
64} Value;
65
66typedef struct Inst {
67 Op op : 5;
68 Type type : 2;
69 Value payload;
70} Inst;
71
72typedef struct Vm Vm;
73
74// -----------------------------------------------------------------------------
75// VM API
76
77/// Create a new virtual machine.
78Vm* vm_new();
79
80/// Destroy the virtual machine.
81void vm_del(Vm**);
82
83/// Execute code on the virtual machine.
84///
85/// Returns the program exit code if an exit operation is executed, 0 otherwise.
86int vm_run(Vm*, const Inst[], size_t count);
87
88/// Prints the virtual machine's stack to stdout.
89void vm_print_stack(const Vm*);
90
91// -----------------------------------------------------------------------------
92// Programming API
93
94/// Exit the program.
95static inline Inst vmExit() { return (Inst){.op = Exit}; }
96
97/// Push a value.
98static inline Inst vmPushI32(int32_t value) {
99 return (Inst){.op = Push, .type = I32, .payload = (Value){.i32 = value}};
100}
101
102/// Pop a value.
103static inline Inst vmPop(Type type) { return (Inst){.op = Pop, .type = type}; }
104
105/// Add two values.
106static inline Inst vmAdd(Type type) { return (Inst){.op = Add, .type = type}; }
107
108/// Decrement a value.
109static inline Inst vmDec(Type type) { return (Inst){.op = Dec, .type = type}; }
110
111/// Compare a value.
112static inline Inst vmCmpI32(int32_t value) {
113 return (Inst){.op = Cmp, .type = I32, .payload = (Value){.i32 = value}};
114}
115
116/// End the current block.
117static inline Inst vmEnd() { return (Inst){.op = End}; }
118
119/// Create a loop.
120static inline Inst vmLoop(Label label) {
121 return (Inst){.op = Loop, .payload = (Value){.label = label}};
122}
123
124/// Create the payload of a conditional branch.
125static inline Inst vmBr_if(bool value, Label label) {
126 return (Inst){
127 .op = Br,
128 .payload = (Value){
129 .branch = {
130 .label = label,
131 .conditional = 1,
132 .expected = value,
133 }}};
134}
135
136/// Create a function.
137static inline Inst vmFunc(Label label) {
138 return (Inst){.op = Func, .payload = (Value){.label = label}};
139}
140
141/// Create a function argument.
142static inline Inst vmArg(Type type, Label label) {
143 return (Inst){.op = Arg, .type = type, .payload = (Value){.label = label}};
144}
145
146/// Call a function.
147static inline Inst vmCall(Label label) {
148 return (Inst){.op = Call, .payload = (Value){.label = label}};
149}
150
151/// Create a local variable.
152static inline Inst vmLocal(Type type, Label label) {
153 return (Inst){.op = Local, .type = type, .payload = (Value){.label = label}};
154}
155
156/// Read a local variable.
157static inline Inst vmLocalRd(Type type, Label label) {
158 return (Inst){
159 .op = LocalRd, .type = type, .payload = (Value){.label = label}};
160}
161
162/// Write a local variable.
163static inline Inst vmLocalWr(Type type, Label label) {
164 return (Inst){
165 .op = LocalWr, .type = type, .payload = (Value){.label = label}};
166}