diff options
author | Bad Diode <bd@badd10de.dev> | 2022-04-25 11:21:28 -0300 |
---|---|---|
committer | Bad Diode <bd@badd10de.dev> | 2022-04-25 11:21:28 -0300 |
commit | 38fd557a61e7366140b6fbdacfebc3ad28f55369 (patch) | |
tree | 7d5ebf147ca546859f2f43df1c62696e72e2003b | |
parent | cc8600eaff00904650c21052d3e2be2508410876 (diff) | |
download | bdl-38fd557a61e7366140b6fbdacfebc3ad28f55369.tar.gz bdl-38fd557a61e7366140b6fbdacfebc3ad28f55369.zip |
Remove and update old code in ir.h
-rw-r--r-- | src/ir.c | 115 | ||||
-rw-r--r-- | src/ir.h | 642 |
2 files changed, 99 insertions, 658 deletions
@@ -1,121 +1,8 @@ | |||
1 | typedef enum Operator { | 1 | #include "ir.h" |
2 | // Arithmetic ops. | ||
3 | OP_ADD, | ||
4 | OP_SUB, | ||
5 | OP_MUL, | ||
6 | OP_DIV, | ||
7 | OP_MOD, | ||
8 | |||
9 | // Load/store/copy operations. | ||
10 | OP_LD8, | ||
11 | OP_LD16, | ||
12 | OP_LD32, | ||
13 | OP_LD64, | ||
14 | OP_ST8, | ||
15 | OP_ST16, | ||
16 | OP_ST32, | ||
17 | OP_ST64, | ||
18 | OP_CP8, | ||
19 | OP_CP16, | ||
20 | OP_CP32, | ||
21 | OP_CP64, | ||
22 | |||
23 | // Bit fiddling operations. | ||
24 | OP_NOT, | ||
25 | OP_AND, | ||
26 | OP_OR, | ||
27 | OP_XOR, | ||
28 | OP_LSHIFT, | ||
29 | OP_RSHIFT, | ||
30 | OP_LROT, | ||
31 | OP_RROT, | ||
32 | |||
33 | // (Un)conditional jump operations. | ||
34 | OP_LABEL, | ||
35 | OP_JMP, | ||
36 | OP_JMP_EQ, | ||
37 | OP_JMP_NEQ, | ||
38 | OP_JMP_GT, | ||
39 | OP_JMP_LT, | ||
40 | OP_JMP_GE, | ||
41 | OP_JMP_LE, | ||
42 | } Operator; | ||
43 | |||
44 | typedef enum OperandType { | ||
45 | OP_TYPE_REG, | ||
46 | OP_TYPE_CONST, | ||
47 | OP_TYPE_LABEL, | ||
48 | } OperandType; | ||
49 | 2 | ||
50 | static size_t reg_gen_id = 0; | 3 | static size_t reg_gen_id = 0; |
51 | static size_t lab_gen_id = 0; | 4 | static size_t lab_gen_id = 0; |
52 | 5 | ||
53 | #define NEW_REG() (Operand){ .type = OP_TYPE_REG, .id = reg_gen_id++ } | ||
54 | #define NEW_LAB() (Operand){ .type = OP_TYPE_LABEL, .id = lab_gen_id++ } | ||
55 | #define NEW_S64(C) (Operand){ .type = OP_TYPE_CONST, .constant.sval = (C) } | ||
56 | #define EMIT_0(PROGRAM, LINE, OP, DST) do { \ | ||
57 | Instruction inst = (Instruction){ \ | ||
58 | .op = (OP), \ | ||
59 | .dst = (DST), \ | ||
60 | }; \ | ||
61 | array_push((PROGRAM)->inst, inst); \ | ||
62 | array_push((PROGRAM)->lines, (LINE)); \ | ||
63 | } while(false); | ||
64 | #define EMIT_1(PROGRAM, LINE, OP, DST, A) do { \ | ||
65 | Instruction inst = (Instruction){ \ | ||
66 | .op = (OP), \ | ||
67 | .dst = (DST), \ | ||
68 | .src_a = (A), \ | ||
69 | }; \ | ||
70 | array_push((PROGRAM)->inst, inst); \ | ||
71 | array_push((PROGRAM)->lines, (LINE)); \ | ||
72 | } while(false); | ||
73 | #define EMIT_2(PROGRAM, LINE, OP, DST, A, B) do { \ | ||
74 | Instruction inst = (Instruction){ \ | ||
75 | .op = (OP), \ | ||
76 | .dst = (DST), \ | ||
77 | .src_a = (A), \ | ||
78 | .src_b = (B), \ | ||
79 | }; \ | ||
80 | array_push((PROGRAM)->inst, inst); \ | ||
81 | array_push((PROGRAM)->lines, (LINE)); \ | ||
82 | } while(false); | ||
83 | |||
84 | typedef struct Operand { | ||
85 | OperandType type; | ||
86 | union { | ||
87 | // REG/LABEL | ||
88 | size_t id; | ||
89 | |||
90 | // s64 constant; | ||
91 | struct { | ||
92 | union { | ||
93 | u64 uval; | ||
94 | s64 sval; | ||
95 | }; | ||
96 | } constant; | ||
97 | }; | ||
98 | } Operand; | ||
99 | |||
100 | typedef struct Instruction { | ||
101 | Operator op; | ||
102 | Operand dst; | ||
103 | Operand src_a; | ||
104 | Operand src_b; | ||
105 | } Instruction; | ||
106 | |||
107 | typedef struct LineInfo { | ||
108 | size_t line; | ||
109 | size_t col; | ||
110 | } LineInfo; | ||
111 | |||
112 | typedef struct ProgramBASM { | ||
113 | Instruction *inst; | ||
114 | LineInfo *lines; | ||
115 | } ProgramBASM; | ||
116 | |||
117 | Operand emit_basm(ProgramBASM *program, Node *node); | ||
118 | |||
119 | Operand | 6 | Operand |
120 | emit_arith(ProgramBASM *program, Node *node, Operator op) { | 7 | emit_arith(ProgramBASM *program, Node *node, Operator op) { |
121 | LineInfo line = (LineInfo){ | 8 | LineInfo line = (LineInfo){ |
@@ -1,565 +1,119 @@ | |||
1 | #ifndef BDL_IR_H | 1 | #ifndef BDL_IR_H |
2 | #define BDL_IR_H | 2 | #define BDL_IR_H |
3 | 3 | ||
4 | typedef struct LineInfo { | 4 | typedef enum Operator { |
5 | size_t line; | ||
6 | size_t col; | ||
7 | } LineInfo; | ||
8 | |||
9 | typedef enum Op { | ||
10 | // Arithmetic ops. | 5 | // Arithmetic ops. |
11 | // - Binary operations. | ||
12 | // - Arguments are passed via the stack. | ||
13 | // - Consume two items in the stack. | ||
14 | OP_ADD, | 6 | OP_ADD, |
15 | OP_SUB, | 7 | OP_SUB, |
16 | OP_MUL, | 8 | OP_MUL, |
17 | OP_DIV, | 9 | OP_DIV, |
18 | OP_MOD, | 10 | OP_MOD, |
19 | // Logic ops. | 11 | |
12 | // Load/store/copy operations. | ||
13 | OP_LD8, | ||
14 | OP_LD16, | ||
15 | OP_LD32, | ||
16 | OP_LD64, | ||
17 | OP_ST8, | ||
18 | OP_ST16, | ||
19 | OP_ST32, | ||
20 | OP_ST64, | ||
21 | OP_CP8, | ||
22 | OP_CP16, | ||
23 | OP_CP32, | ||
24 | OP_CP64, | ||
25 | |||
26 | // Bit fiddling operations. | ||
20 | OP_NOT, | 27 | OP_NOT, |
21 | // Stack ops. | 28 | OP_AND, |
22 | // - Requires a constant Object to push into the stack. | 29 | OP_OR, |
23 | OP_PUSH, | 30 | OP_XOR, |
24 | // - Discards the last value in the stack. | 31 | OP_LSHIFT, |
25 | OP_DROP, | 32 | OP_RSHIFT, |
26 | // - Duplicates the last value in the stack. | 33 | OP_LROT, |
27 | OP_DUP, | 34 | OP_RROT, |
28 | // - Rotates the last three elements in the stack. | 35 | |
29 | // - Right: [ a b c -> c a b ] | 36 | // (Un)conditional jump operations. |
30 | // - Left: [ a b c -> b c a] | ||
31 | OP_ROT_RIGHT, | ||
32 | OP_ROT_LEFT, | ||
33 | // A label for memory access. | ||
34 | // - The argument should be a unique value. | ||
35 | OP_LABEL, | 37 | OP_LABEL, |
36 | // Jump/conditional ops. | 38 | OP_JMP, |
37 | // - Take a label as argument. | 39 | OP_JMP_EQ, |
38 | OP_JUMP, | 40 | OP_JMP_NEQ, |
39 | // - Consume one value in the stack. | 41 | OP_JMP_GT, |
40 | // - All objects except `false` are considered `true`. | 42 | OP_JMP_LT, |
41 | OP_JUMP_IF_TRUE, | 43 | OP_JMP_GE, |
42 | OP_JUMP_IF_FALSE, | 44 | OP_JMP_LE, |
43 | // - These require numerical objects on the stack. | 45 | } Operator; |
44 | // - Consume two items in the stack. | 46 | |
45 | // - Jumps to the given label as argument when appropriate. | 47 | typedef enum OperandType { |
46 | OP_JUMP_IF_EQ, | 48 | OP_TYPE_REG, |
47 | OP_JUMP_IF_NEQ, | 49 | OP_TYPE_CONST, |
48 | OP_JUMP_IF_GT, | 50 | OP_TYPE_LABEL, |
49 | OP_JUMP_IF_LT, | 51 | } OperandType; |
50 | OP_JUMP_IF_GE, | 52 | |
51 | OP_JUMP_IF_LE, | 53 | #define NEW_REG() (Operand){ .type = OP_TYPE_REG, .id = reg_gen_id++ } |
52 | // Variable access. | 54 | #define NEW_LAB() (Operand){ .type = OP_TYPE_LABEL, .id = lab_gen_id++ } |
53 | // - Require an index corresponding to the variable to store. | 55 | #define NEW_S64(C) (Operand){ .type = OP_TYPE_CONST, .constant.sval = (C) } |
54 | // - Consume the last item in the stack. | 56 | #define EMIT_0(PROGRAM, LINE, OP, DST) do { \ |
55 | OP_STORE_LOCAL, | 57 | Instruction inst = (Instruction){ \ |
56 | OP_STORE_CAPTURED, | 58 | .op = (OP), \ |
57 | OP_STORE_PARAM, | 59 | .dst = (DST), \ |
58 | // - Require an index corresponding to the variable to load. | 60 | }; \ |
59 | // - The loaded value is pushed into the stack. | 61 | array_push((PROGRAM)->inst, inst); \ |
60 | OP_LOAD_LOCAL, | 62 | array_push((PROGRAM)->lines, (LINE)); \ |
61 | OP_LOAD_CAPTURED, | ||
62 | OP_LOAD_PARAM, | ||
63 | // Primitive complex commands. | ||
64 | // - Prints the last object in the stack. | ||
65 | OP_PRINT, | ||
66 | // Procedures. | ||
67 | // - Consumes the last value in the stack, which must be a lambda. | ||
68 | OP_CALL, | ||
69 | // - Return position is on a know location of the stack based on the offset | ||
70 | // of locals, parameters, etc. | ||
71 | OP_RETURN, | ||
72 | // TODO: add remaining ops. | ||
73 | } Op; | ||
74 | |||
75 | static const char* ops_str[] = { | ||
76 | [OP_ADD] = "OP_ADD", | ||
77 | [OP_SUB] = "OP_SUB", | ||
78 | [OP_MUL] = "OP_MUL", | ||
79 | [OP_DIV] = "OP_DIV", | ||
80 | [OP_MOD] = "OP_MOD", | ||
81 | [OP_NOT] = "OP_NOT", | ||
82 | [OP_PUSH] = "OP_PUSH", | ||
83 | [OP_DROP] = "OP_DROP", | ||
84 | [OP_DUP] = "OP_DUP", | ||
85 | [OP_ROT_RIGHT] = "OP_ROT_RIGHT", | ||
86 | [OP_ROT_LEFT] = "OP_ROT_LEFT", | ||
87 | [OP_LABEL] = "OP_LABEL", | ||
88 | [OP_JUMP] = "OP_JUMP", | ||
89 | [OP_JUMP_IF_TRUE] = "OP_JUMP_IF_TRUE", | ||
90 | [OP_JUMP_IF_FALSE] = "OP_JUMP_IF_FALSE", | ||
91 | [OP_JUMP_IF_EQ] = "OP_JUMP_IF_EQ", | ||
92 | [OP_JUMP_IF_NEQ] = "OP_JUMP_IF_NEQ", | ||
93 | [OP_JUMP_IF_GT] = "OP_JUMP_IF_GT", | ||
94 | [OP_JUMP_IF_LT] = "OP_JUMP_IF_LT", | ||
95 | [OP_JUMP_IF_GE] = "OP_JUMP_IF_GE", | ||
96 | [OP_JUMP_IF_LE] = "OP_JUMP_IF_LE", | ||
97 | [OP_STORE_LOCAL] = "OP_STORE_LOCAL", | ||
98 | [OP_STORE_CAPTURED] = "OP_STORE_CAPTURED", | ||
99 | [OP_STORE_PARAM] = "OP_STORE_PARAM", | ||
100 | [OP_LOAD_LOCAL] = "OP_LOAD_LOCAL", | ||
101 | [OP_LOAD_CAPTURED] = "OP_LOAD_CAPTURED", | ||
102 | [OP_LOAD_PARAM] = "OP_LOAD_PARAM", | ||
103 | [OP_PRINT] = "OP_PRINT", | ||
104 | [OP_CALL] = "OP_CALL", | ||
105 | [OP_RETURN] = "OP_RETURN", | ||
106 | }; | ||
107 | |||
108 | typedef struct Instruction { | ||
109 | Op op; | ||
110 | |||
111 | // Op arguments. | ||
112 | union { | ||
113 | // OP_PUSH | ||
114 | Object *argument; | ||
115 | |||
116 | // OP_LABEL | ||
117 | // OP_JUMP | ||
118 | // OP_JUMP_IF_xxx | ||
119 | size_t label_id; | ||
120 | |||
121 | // OP_STORE_LOCAL | ||
122 | // OP_LOAD_LOCAL | ||
123 | size_t index; | ||
124 | }; | ||
125 | |||
126 | // Original line/column for debugging purposes. | ||
127 | size_t line; | ||
128 | size_t col; | ||
129 | } Instruction; | ||
130 | |||
131 | typedef struct Procedure { | ||
132 | // Procedure name. | ||
133 | char *name; | ||
134 | |||
135 | struct Procedure *parent; | ||
136 | |||
137 | // Program code. | ||
138 | Instruction *instructions; | ||
139 | |||
140 | // Variables. | ||
141 | Object **locals; | ||
142 | Object **captured; | ||
143 | Object **params; | ||
144 | } Procedure; | ||
145 | |||
146 | typedef struct ProgramIr { | ||
147 | Procedure **procedures; | ||
148 | Object **lambdas; | ||
149 | size_t labels; | ||
150 | } ProgramIr; | ||
151 | |||
152 | #define INST_SIMPLE(PROC, OP, LINE, COL) \ | ||
153 | do { \ | ||
154 | Instruction inst = (Instruction){(OP), NULL, (LINE), (COL)}; \ | ||
155 | array_push((PROC)->instructions, inst); \ | ||
156 | } while(false); | ||
157 | |||
158 | #define INST_ARG(PROC, OP, ARG, LINE, COL) \ | ||
159 | do { \ | ||
160 | Instruction inst = (Instruction){(OP), .argument = (ARG), (LINE), (COL)}; \ | ||
161 | array_push((PROC)->instructions, inst); \ | ||
162 | } while(false); | 63 | } while(false); |
163 | 64 | #define EMIT_1(PROGRAM, LINE, OP, DST, A) do { \ | |
164 | #define INST_LABEL(PROC, OP, ARG, LINE, COL) \ | 65 | Instruction inst = (Instruction){ \ |
165 | do { \ | 66 | .op = (OP), \ |
166 | Instruction inst = (Instruction){(OP), .label_id = (ARG), (LINE), (COL)}; \ | 67 | .dst = (DST), \ |
167 | array_push((PROC)->instructions, inst); \ | 68 | .src_a = (A), \ |
69 | }; \ | ||
70 | array_push((PROGRAM)->inst, inst); \ | ||
71 | array_push((PROGRAM)->lines, (LINE)); \ | ||
168 | } while(false); | 72 | } while(false); |
169 | 73 | #define EMIT_2(PROGRAM, LINE, OP, DST, A, B) do { \ | |
170 | #define INST_VAR(PROC, OP, ARG, LINE, COL) \ | 74 | Instruction inst = (Instruction){ \ |
171 | do { \ | 75 | .op = (OP), \ |
172 | Instruction inst = (Instruction){(OP), .index = (ARG), (LINE), (COL)}; \ | 76 | .dst = (DST), \ |
173 | array_push((PROC)->instructions, inst); \ | 77 | .src_a = (A), \ |
78 | .src_b = (B), \ | ||
79 | }; \ | ||
80 | array_push((PROGRAM)->inst, inst); \ | ||
81 | array_push((PROGRAM)->lines, (LINE)); \ | ||
174 | } while(false); | 82 | } while(false); |
175 | 83 | ||
176 | void | 84 | typedef struct Operand { |
177 | print_instruction(Instruction *instruction) { | 85 | OperandType type; |
178 | printf("%4ld:%-4ld ", instruction->line, instruction->col); | 86 | union { |
179 | Op op = instruction->op; | 87 | // REG/LABEL |
180 | switch (op) { | 88 | size_t id; |
181 | case OP_PUSH: { | 89 | |
182 | printf("%-16s -> ", ops_str[op]); | 90 | // s64 constant; |
183 | OBJ_PRINT(instruction->argument); | 91 | struct { |
184 | } break; | 92 | union { |
185 | case OP_JUMP: | 93 | u64 uval; |
186 | case OP_JUMP_IF_TRUE: | 94 | s64 sval; |
187 | case OP_JUMP_IF_FALSE: | 95 | }; |
188 | case OP_JUMP_IF_EQ: | 96 | } constant; |
189 | case OP_JUMP_IF_NEQ: | 97 | }; |
190 | case OP_JUMP_IF_GT: | 98 | } Operand; |
191 | case OP_JUMP_IF_LT: | ||
192 | case OP_JUMP_IF_GE: | ||
193 | case OP_JUMP_IF_LE: | ||
194 | case OP_LABEL: { | ||
195 | printf("%-16s -> %zu\n", ops_str[op], instruction->label_id); | ||
196 | } break; | ||
197 | case OP_STORE_LOCAL: | ||
198 | case OP_STORE_CAPTURED: | ||
199 | case OP_STORE_PARAM: | ||
200 | case OP_LOAD_LOCAL: | ||
201 | case OP_LOAD_CAPTURED: | ||
202 | case OP_LOAD_PARAM: { | ||
203 | printf("%-16s -> %zu\n", ops_str[op], instruction->index); | ||
204 | } break; | ||
205 | default: { | ||
206 | printf("%s\n", ops_str[op]); | ||
207 | } break; | ||
208 | } | ||
209 | } | ||
210 | |||
211 | void | ||
212 | print_procedure(Procedure *proc) { | ||
213 | printf("===== %.*s =====\n", (int)array_size(proc->name), proc->name); | ||
214 | printf("code:\n"); | ||
215 | for (size_t i = 0; i < array_size(proc->instructions); ++i) { | ||
216 | print_instruction(&proc->instructions[i]); | ||
217 | } | ||
218 | } | ||
219 | |||
220 | Procedure * | ||
221 | proc_alloc(ProgramIr *program, StringView name, Procedure *parent) { | ||
222 | Procedure *proc = calloc(1, sizeof(Procedure)); | ||
223 | array_init(proc->name, name.n); | ||
224 | array_insert(proc->name, name.start, name.n); | ||
225 | array_init(proc->instructions, 0); | ||
226 | array_init(proc->locals, 0); | ||
227 | array_init(proc->captured, 0); | ||
228 | array_init(proc->params, 0); | ||
229 | proc->parent = parent; | ||
230 | array_push(program->procedures, proc); | ||
231 | return proc; | ||
232 | } | ||
233 | |||
234 | void compile_object(ProgramIr *program, Procedure *proc, Object *obj); | ||
235 | |||
236 | void | ||
237 | compile_arithmetic(ProgramIr *program, Procedure *proc, Op op, | ||
238 | size_t line, size_t col, Object *args) { | ||
239 | compile_object(program, proc, args->head); | ||
240 | args = args->tail; | ||
241 | while (args != NULL) { | ||
242 | compile_object(program, proc, args->head); | ||
243 | args = args->tail; | ||
244 | INST_SIMPLE(proc, op, line, col); | ||
245 | } | ||
246 | } | ||
247 | |||
248 | void | ||
249 | compile_numeric_cmp(ProgramIr *program, Procedure *proc, Op op, | ||
250 | size_t line, size_t col, Object *args) { | ||
251 | size_t label_false = program->labels++; | ||
252 | size_t label_exit = program->labels++; | ||
253 | compile_object(program, proc, args->head); | ||
254 | args = args->tail; | ||
255 | while (args != NULL) { | ||
256 | compile_object(program, proc, args->head); | ||
257 | args = args->tail; | ||
258 | INST_SIMPLE(proc, OP_DUP, line, col); | ||
259 | INST_SIMPLE(proc, OP_ROT_RIGHT, line, col); | ||
260 | INST_LABEL(proc, op, label_false, line, col); | ||
261 | } | ||
262 | INST_SIMPLE(proc, OP_DROP, line, col); | ||
263 | INST_ARG(proc, OP_PUSH, &obj_true, line, col); | ||
264 | INST_LABEL(proc, OP_JUMP, label_exit, line, col); | ||
265 | INST_LABEL(proc, OP_LABEL, label_false, line, col); | ||
266 | INST_SIMPLE(proc, OP_DROP, line, col); | ||
267 | INST_ARG(proc, OP_PUSH, &obj_false, line, col); | ||
268 | INST_LABEL(proc, OP_LABEL, label_exit, line, col); | ||
269 | } | ||
270 | |||
271 | void | ||
272 | compile_print(ProgramIr *program, Procedure *proc, | ||
273 | size_t line, size_t col, Object *args) { | ||
274 | while (args != NULL) { | ||
275 | compile_object(program, proc, args->head); | ||
276 | args = args->tail; | ||
277 | INST_SIMPLE(proc, OP_PRINT, line, col); | ||
278 | } | ||
279 | } | ||
280 | |||
281 | void | ||
282 | compile_not(ProgramIr *program, Procedure *proc, | ||
283 | size_t line, size_t col, Object *args) { | ||
284 | compile_object(program, proc, args->head); | ||
285 | INST_SIMPLE(proc, OP_NOT, line, col); | ||
286 | } | ||
287 | |||
288 | void | ||
289 | compile_and(ProgramIr *program, Procedure *proc, | ||
290 | size_t line, size_t col, Object *args) { | ||
291 | size_t label_false = program->labels++; | ||
292 | size_t label_exit = program->labels++; | ||
293 | while (args != NULL) { | ||
294 | compile_object(program, proc, args->head); | ||
295 | args = args->tail; | ||
296 | INST_LABEL(proc, OP_JUMP_IF_FALSE, label_false, line, col); | ||
297 | } | ||
298 | INST_ARG(proc, OP_PUSH, &obj_true, line, col); | ||
299 | INST_LABEL(proc, OP_JUMP, label_exit, line, col); | ||
300 | INST_LABEL(proc, OP_LABEL, label_false, line, col); | ||
301 | INST_ARG(proc, OP_PUSH, &obj_false, line, col); | ||
302 | INST_LABEL(proc, OP_LABEL, label_exit, line, col); | ||
303 | } | ||
304 | |||
305 | void | ||
306 | compile_or(ProgramIr *program, Procedure *proc, | ||
307 | size_t line, size_t col, Object *args) { | ||
308 | size_t label_true = program->labels++; | ||
309 | size_t label_exit = program->labels++; | ||
310 | while (args != NULL) { | ||
311 | compile_object(program, proc, args->head); | ||
312 | args = args->tail; | ||
313 | INST_LABEL(proc, OP_JUMP_IF_TRUE, label_true, line, col); | ||
314 | } | ||
315 | INST_ARG(proc, OP_PUSH, &obj_false, line, col); | ||
316 | INST_LABEL(proc, OP_JUMP, label_exit, line, col); | ||
317 | INST_LABEL(proc, OP_LABEL, label_true, line, col); | ||
318 | INST_ARG(proc, OP_PUSH, &obj_true, line, col); | ||
319 | INST_LABEL(proc, OP_LABEL, label_exit, line, col); | ||
320 | } | ||
321 | |||
322 | void | ||
323 | compile_builtin(ProgramIr *program, Procedure *proc, Object *obj) { | ||
324 | size_t line = obj->line; | ||
325 | size_t col = obj->col; | ||
326 | switch (obj->head->builtin) { | ||
327 | case BUILTIN_ADD: { | ||
328 | compile_arithmetic(program, proc, OP_ADD, line, col, obj->tail); | ||
329 | } break; | ||
330 | case BUILTIN_SUB: { | ||
331 | compile_arithmetic(program, proc, OP_SUB, line, col, obj->tail); | ||
332 | } break; | ||
333 | case BUILTIN_MUL: { | ||
334 | compile_arithmetic(program, proc, OP_MUL, line, col, obj->tail); | ||
335 | } break; | ||
336 | case BUILTIN_DIV: { | ||
337 | compile_arithmetic(program, proc, OP_DIV, line, col, obj->tail); | ||
338 | } break; | ||
339 | case BUILTIN_MOD: { | ||
340 | compile_arithmetic(program, proc, OP_MOD, line, col, obj->tail); | ||
341 | } break; | ||
342 | case BUILTIN_PRINT: { | ||
343 | compile_print(program, proc, line, col, obj->tail); | ||
344 | } break; | ||
345 | case BUILTIN_NOT: { | ||
346 | compile_not(program, proc, line, col, obj->tail); | ||
347 | } break; | ||
348 | case BUILTIN_AND: { | ||
349 | compile_and(program, proc, line, col, obj->tail); | ||
350 | } break; | ||
351 | case BUILTIN_OR: { | ||
352 | compile_or(program, proc, line, col, obj->tail); | ||
353 | } break; | ||
354 | case BUILTIN_EQ: { | ||
355 | compile_numeric_cmp(program, proc, OP_JUMP_IF_NEQ, line, col, obj->tail); | ||
356 | } break; | ||
357 | case BUILTIN_GT: { | ||
358 | compile_numeric_cmp(program, proc, OP_JUMP_IF_LE, line, col, obj->tail); | ||
359 | } break; | ||
360 | case BUILTIN_LT: { | ||
361 | compile_numeric_cmp(program, proc, OP_JUMP_IF_GE, line, col, obj->tail); | ||
362 | } break; | ||
363 | case BUILTIN_GE: { | ||
364 | compile_numeric_cmp(program, proc, OP_JUMP_IF_LT, line, col, obj->tail); | ||
365 | } break; | ||
366 | case BUILTIN_LE: { | ||
367 | compile_numeric_cmp(program, proc, OP_JUMP_IF_GT, line, col, obj->tail); | ||
368 | } break; | ||
369 | // TODO: cons, car, cdr, type checks (nil? zero? fixnum? bool? ...) | ||
370 | default: { | ||
371 | assert(false && "builtin not implemented"); | ||
372 | } break; | ||
373 | } | ||
374 | } | ||
375 | |||
376 | void | ||
377 | compile_proc_call(ProgramIr *program, Procedure *proc, Object *obj) { | ||
378 | if (IS_BUILTIN(obj->head)) { | ||
379 | compile_builtin(program, proc, obj); | ||
380 | } else { | ||
381 | Object *tail = obj->tail; | ||
382 | while (tail != NULL) { | ||
383 | compile_object(program, proc, tail->head); | ||
384 | tail = tail->tail; | ||
385 | } | ||
386 | compile_object(program, proc, obj->head); | ||
387 | INST_SIMPLE(proc, OP_CALL, obj->line, obj->col); | ||
388 | } | ||
389 | } | ||
390 | |||
391 | void | ||
392 | compile_if(ProgramIr *program, Procedure *proc, Object *obj) { | ||
393 | size_t label_false = program->labels++; | ||
394 | compile_object(program, proc, obj->condition); | ||
395 | INST_LABEL(proc, OP_JUMP_IF_FALSE, label_false, obj->line, obj->col); | ||
396 | compile_object(program, proc, obj->expr_true); | ||
397 | if (obj->expr_false != NULL) { | ||
398 | size_t label_exit = program->labels++; | ||
399 | INST_LABEL(proc, OP_JUMP, label_exit, obj->line, obj->col); | ||
400 | INST_LABEL(proc, OP_LABEL, label_false, obj->line, obj->col); | ||
401 | compile_object(program, proc, obj->expr_false); | ||
402 | INST_LABEL(proc, OP_LABEL, label_exit, obj->line, obj->col); | ||
403 | } else { | ||
404 | INST_LABEL(proc, OP_LABEL, label_false, obj->line, obj->col); | ||
405 | } | ||
406 | } | ||
407 | |||
408 | void | ||
409 | compile_def(ProgramIr *program, Procedure *proc, Object *obj) { | ||
410 | ssize_t idx = find_var_index(proc->locals, obj->var_name); | ||
411 | if (idx == -1) { | ||
412 | array_push(proc->locals, obj->var_name); | ||
413 | idx = array_size(proc->locals) - 1; | ||
414 | } | ||
415 | compile_object(program, proc, obj->var_expr); | ||
416 | INST_VAR(proc, OP_STORE_LOCAL, idx, obj->line, obj->col); | ||
417 | } | ||
418 | |||
419 | void | ||
420 | compile_lambda(ProgramIr *program, Procedure *proc, Object *obj) { | ||
421 | // NOTE: As an optimization, instead of storing and comparing lambdas, we | ||
422 | // could calculate a checksum and only check equality in full if they | ||
423 | // differ. We can also calculate the equality of Procedure instead of | ||
424 | // lambdas. | ||
425 | for (size_t i = 0; i < array_size(program->lambdas); ++i) { | ||
426 | if (object_equal(program->lambdas[i], obj)) { | ||
427 | INST_ARG(proc, OP_PUSH, obj, obj->line, obj->col); | ||
428 | return; | ||
429 | } | ||
430 | } | ||
431 | array_push(program->lambdas, obj); | ||
432 | Procedure *lambda = proc_alloc(program, STRING("lambda"), proc); | ||
433 | |||
434 | // Parameters. | ||
435 | for (size_t i = 0; i < array_size(obj->params); ++i) { | ||
436 | array_push(lambda->params, obj->params[i]); | ||
437 | } | ||
438 | |||
439 | // Body. | ||
440 | for (size_t i = 0; i < array_size(obj->body) - 1; i++) { | ||
441 | compile_object(program, lambda, obj->body[i]); | ||
442 | } | ||
443 | Object *last_expr = obj->body[array_size(obj->body) - 1]; | ||
444 | |||
445 | // Tail Call Optimization. | ||
446 | // TODO: also for if statements | ||
447 | if (IS_PAIR(last_expr)) { | ||
448 | if (IS_BUILTIN(last_expr->head)) { | ||
449 | compile_builtin(program, lambda, last_expr); | ||
450 | } else { | ||
451 | // TODO: Discard the previous stack frame. | ||
452 | // context_printf(" mov rsp, rbp\n"); | ||
453 | // TODO: Replace stack frame instead of compiling a new one. | ||
454 | compile_proc_call(program, lambda, last_expr); | ||
455 | |||
456 | // size_t old_offset = n_locals + n_captured + n_params; | ||
457 | // size_t new_offset = compile_call_body(last_expr); | ||
458 | // context_printf(" mov rdi, [rbp - 8]\n"); | ||
459 | // for (size_t i = 0; i < new_offset + 1; i++) { | ||
460 | // context_printf(" mov rax, [rbp - 8 * %zu]\n", i + 1); | ||
461 | // context_printf(" mov [rbp + 8 * %zu], rax\n", old_offset - i); | ||
462 | // } | ||
463 | |||
464 | // // Set the stack pointer at the end of given parameters. | ||
465 | // context_printf(" mov rsp, rbp\n"); | ||
466 | // ssize_t offset_diff = old_offset - new_offset; | ||
467 | // if (offset_diff > 0) { | ||
468 | // context_printf(" add rsp, 8 * %zu\n", offset_diff); | ||
469 | // } else { | ||
470 | // context_printf(" sub rsp, 8 * %zu\n", offset_diff); | ||
471 | // } | ||
472 | |||
473 | // context_printf(" jmp rdi\n"); | ||
474 | } | ||
475 | } else { | ||
476 | // compile_nil(); | ||
477 | compile_object(program, lambda, last_expr); | ||
478 | |||
479 | // // Return is stored in the `rax`. | ||
480 | // context_printf(" pop rax\n"); | ||
481 | |||
482 | // // Restore the previous call frame. | ||
483 | // size_t rp_offset = (n_locals + n_params + n_captured + 1); | ||
484 | // context_printf(" mov rdi, [rbp + %zu]\n", 8 * rp_offset); | ||
485 | // context_printf(" mov rsp, rbp\n"); | ||
486 | // context_printf(" add rsp, %zu\n", 8 * n_locals); | ||
487 | // context_printf(" jmp rdi\n"); | ||
488 | } | ||
489 | INST_SIMPLE(lambda, OP_RETURN, obj->line, obj->col); | ||
490 | |||
491 | INST_ARG(proc, OP_PUSH, obj, obj->line, obj->col); | ||
492 | } | ||
493 | |||
494 | void | ||
495 | compile_symbol(Procedure *proc, Object *obj) { | ||
496 | ssize_t idx = -1; | ||
497 | |||
498 | // Is a local variable? | ||
499 | idx = find_var_index(proc->locals, obj); | ||
500 | if (idx != -1) { | ||
501 | INST_VAR(proc, OP_LOAD_LOCAL, idx, obj->line, obj->col); | ||
502 | return; | ||
503 | } | ||
504 | |||
505 | // Is a captured variable? | ||
506 | idx = find_var_index(proc->captured, obj); | ||
507 | if (idx != -1) { | ||
508 | INST_VAR(proc, OP_LOAD_CAPTURED, idx, obj->line, obj->col); | ||
509 | return; | ||
510 | } | ||
511 | |||
512 | // Is a function parameter? | ||
513 | idx = find_var_index(proc->params, obj); | ||
514 | if (idx != -1) { | ||
515 | INST_VAR(proc, OP_LOAD_PARAM, idx, obj->line, obj->col); | ||
516 | return; | ||
517 | } | ||
518 | |||
519 | // Not in this scope, if is in another scope, it must be captured. Since we | ||
520 | // perform semantic analysis before this should always be true in this | ||
521 | // phase. | ||
522 | array_push(proc->captured, obj); | ||
523 | INST_VAR(proc, OP_LOAD_CAPTURED, array_size(proc->captured) - 1, obj->line, obj->col); | ||
524 | } | ||
525 | |||
526 | void | ||
527 | compile_object(ProgramIr *program, Procedure *proc, Object *obj) { | ||
528 | switch (obj->type) { | ||
529 | case OBJ_TYPE_NIL: | ||
530 | case OBJ_TYPE_TRUE: | ||
531 | case OBJ_TYPE_FALSE: | ||
532 | case OBJ_TYPE_STRING: | ||
533 | case OBJ_TYPE_FIXNUM: { INST_ARG(proc, OP_PUSH, obj, obj->line, obj->col); } break; | ||
534 | case OBJ_TYPE_PAIR: { compile_proc_call(program, proc, obj); } break; | ||
535 | case OBJ_TYPE_IF: { compile_if(program, proc, obj); } break; | ||
536 | case OBJ_TYPE_LAMBDA: { compile_lambda(program, proc, obj); } break; | ||
537 | case OBJ_TYPE_DEF: { compile_def(program, proc, obj); } break; | ||
538 | case OBJ_TYPE_SYMBOL: { compile_symbol(proc, obj); } break; | ||
539 | default: { | ||
540 | assert(false && "compile_object not implemented"); | ||
541 | } break; | ||
542 | } | ||
543 | } | ||
544 | 99 | ||
545 | ProgramIr | 100 | typedef struct Instruction { |
546 | compile(Program program) { | 101 | Operator op; |
547 | ProgramIr program_ir = {0}; | 102 | Operand dst; |
548 | array_init(program_ir.procedures, 0); | 103 | Operand src_a; |
549 | array_init(program_ir.lambdas, 0); | 104 | Operand src_b; |
550 | Procedure *main = proc_alloc(&program_ir, STRING("main"), NULL); | 105 | } Instruction; |
551 | 106 | ||
552 | for (size_t i = 0; i < array_size(program.roots); i++) { | 107 | typedef struct LineInfo { |
553 | Object *root = program.roots[i]; | 108 | size_t line; |
554 | compile_object(&program_ir, main, root); | 109 | size_t col; |
555 | } | 110 | } LineInfo; |
556 | 111 | ||
557 | // DEBUG:... | 112 | typedef struct ProgramBASM { |
558 | for (size_t i = 0; i < array_size(program_ir.procedures); ++i) { | 113 | Instruction *inst; |
559 | print_procedure(program_ir.procedures[i]); | 114 | LineInfo *lines; |
560 | } | 115 | } ProgramBASM; |
561 | 116 | ||
562 | return program_ir; | 117 | Operand emit_basm(ProgramBASM *program, Node *node); |
563 | } | ||
564 | 118 | ||
565 | #endif // BDL_IR_H | 119 | #endif // BDL_IR_H |