aboutsummaryrefslogtreecommitdiff
path: root/vm/src/vm.c
diff options
context:
space:
mode:
Diffstat (limited to 'vm/src/vm.c')
-rw-r--r--vm/src/vm.c402
1 files changed, 402 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}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-19 21:38:04 +0000