1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
|
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "compiler.h"
#include "symtab.h"
static void write_func_params(struct pair_tn *params, struct node *list) {
if (list->type == N_LIST_END) return;
assert(list->child1->type == N_VAR_DECL);
params[0].type = list->child1->rtype;
params[0].name = strdup(list->child1->name);
write_func_params(params + 1, list->child2);
}
static bool oper_is_basic_arith(enum operator oper) {
return oper == OP_ADD || oper == OP_SUB || oper == OP_MUL || oper == OP_DIV || oper == OP_MOD;
}
static bool oper_is_comparison(enum operator oper) {
return oper == OP_EQ || oper == OP_NEQ ||
oper == OP_LT || oper == OP_GT ||
oper == OP_LEQ || oper == OP_GEQ;
}
static struct ref compile_expr(struct ir *ir, struct symtab *symtab, struct node *node);
static void compile_boolexpr(
struct ir *ir, struct symtab *symtab, struct node *node, char *truedest, char *falsedest) {
if (node->type == N_BINOP && oper_is_comparison(node->oper)) {
struct ref r1 = compile_expr(ir, symtab, node->child1);
struct ref r2 = compile_expr(ir, symtab, node->child2);
ir_append(ir, irins_make_12(INS_CMP, r1, r2));
enum condcode condcode;
switch (node->oper) {
case OP_EQ: condcode = CCNZ; break;
case OP_NEQ: condcode = CCZ; break;
case OP_LT: condcode = CCGE; break;
case OP_GT: condcode = CCLE; break;
case OP_LEQ: condcode = CCG; break;
case OP_GEQ: condcode = CCL; break;
default: assert(false);
}
ir_append(ir, irins_make_jcc(falsedest, condcode));
ir_append(ir, irins_make_name(INS_JMP, truedest));
} else if (node->type == N_BINOP && node->oper == OP_AND) {
char *try2lbl = gen_label_name();
compile_boolexpr(ir, symtab, node->child1, try2lbl, falsedest);
ir_append(ir, irins_make_name(INS_LBL, try2lbl));
compile_boolexpr(ir, symtab, node->child2, truedest, falsedest);
} else if (node->type == N_BINOP && node->oper == OP_OR) {
char *try2lbl = gen_label_name();
compile_boolexpr(ir, symtab, node->child1, truedest, try2lbl);
ir_append(ir, irins_make_name(INS_LBL, try2lbl));
compile_boolexpr(ir, symtab, node->child2, truedest, falsedest);
} else if (node->type == N_UNOP && node->oper == OP_NOT) {
compile_boolexpr(ir, symtab, node->child1, falsedest, truedest);
} else {
struct ref ref = compile_expr(ir, symtab, node);
ir_append(ir, irins_make_12(INS_TEST, ref, ref));
ir_append(ir, irins_make_jcc(falsedest, CCZ));
ir_append(ir, irins_make_name(INS_JMP, truedest));
}
}
static struct ref compile_expr(struct ir *ir, struct symtab *symtab, struct node *node) {
switch (node->type) {
case N_NUM: {
struct ref ref = ref_next_register();
ir_append(ir, irins_make_01(INS_MOV, ref, ref_imm(node->value)));
return ref;
}
case N_VAR: {
struct symbol *sym = symtab_find(symtab, node->name);
if (!sym) {
fprintf(stderr, "Use of undeclared variable '%s'\n", node->name);
exit(1);
}
return sym->ref;
}
case N_BINOP: {
if (oper_is_basic_arith(node->oper)) {
struct ref r0 = ref_next_register();
struct ref r1 = compile_expr(ir, symtab, node->child1);
struct ref r2 = compile_expr(ir, symtab, node->child2);
enum instype instype;
switch (node->oper) {
case OP_ADD: instype = INS_ADD; break;
case OP_SUB: instype = INS_SUB; break;
case OP_MUL: instype = INS_MUL; break;
case OP_DIV: instype = INS_DIV; break;
case OP_MOD: instype = INS_MOD; break;
default: assert(false);
}
ir_append(ir, irins_make_012(instype, r0, r1, r2));
return r0;
} else if (oper_is_comparison(node->oper) || node->oper == OP_AND || node->oper == OP_OR) {
char *truelbl = gen_label_name();
char *falselbl = gen_label_name();
char *afterlbl = gen_label_name();
compile_boolexpr(ir, symtab, node, truelbl, falselbl);
struct ref cval = ref_next_register();
ir_append(ir, irins_make_name(INS_LBL, truelbl));
ir_append(ir, irins_make_01(INS_MOV, cval, ref_imm(1)));
ir_append(ir, irins_make_name(INS_JMP, afterlbl));
ir_append(ir, irins_make_name(INS_LBL, falselbl));
ir_append(ir, irins_make_01(INS_MOV, cval, ref_imm(0)));
ir_append(ir, irins_make_name(INS_LBL, afterlbl));
return cval;
} else if (node->oper == OP_ASSIGN) {
if (node->child1->type == N_VAR ||
(node->child1->type == N_UNOP && node->child1->oper == OP_DEREF)) {
struct ref r0 = compile_expr(ir, symtab, node->child1);
struct ref r1 = compile_expr(ir, symtab, node->child2);
ir_append(ir, irins_make_01(INS_MOV, r0, r1));
return r0;
} else {
fprintf(stderr, "Invalid left-hand side in assignment.\n");
exit(1);
}
} else {
assert(false);
}
}
case N_UNOP: {
switch (node->oper) {
case OP_NEG: {
struct ref r0 = ref_next_register();
struct ref r1 = compile_expr(ir, symtab, node->child1);
ir_append(ir, irins_make_01(INS_NEG, r0, r1));
return r0;
}
case OP_NOT: {
struct ref r0 = ref_next_register();
struct ref r1 = compile_expr(ir, symtab, node->child1);
ir_append(ir, irins_make_01(INS_NOT, r0, r1));
return r0;
}
case OP_DEREF: {
struct ref addr = compile_expr(ir, symtab, node->child1);
struct ref r1;
switch (addr.type) {
case REF_REG: r1 = ref_mem(addr.reg, 0, false); break;
case REF_IMM: r1 = ref_mem(-1, addr.imm, false); break;
case REF_MEM: {
r1 = ref_next_register();
ir_append(ir, irins_make_01(INS_MOV, r1, addr));
r1 = ref_mem(r1.reg, 0, false); break;
break;
}
}
struct ref r0 = ref_next_register();
ir_append(ir, irins_make_01(INS_MOV, r0, r1));
return r0;
}
case OP_ADDROF:
fprintf(stderr, "OP_ADDROF not implemented\n");
exit(1);
default:
assert(false);
}
}
case N_CALL: {
fprintf(stderr, "function calls not implemented\n");
exit(1);
/*struct symbol *sym = symtab_find(symtab, node->name);
if (!sym) {
fprintf(stderr, "Call of undeclared function '%s'\n", node->name);
exit(1);
}
;*/
}
default:
fprintf(stderr, "Invalid node type %d in expression\n", node->type);
exit(1);
}
}
static void compile_node(struct ir *ir, struct symtab *symtab, struct node *node) {
switch (node->type) {
case N_LIST:
compile_node(ir, symtab, node->child1);
compile_node(ir, symtab, node->child2);
break;
case N_LIST_END:
break;
case N_BLOCK: {
symtab = symtab_sub(symtab);
compile_node(ir, symtab, node->child1);
symtab = symtab_delete_get_parent(symtab);
break;
}
case N_VAR_DECL_INIT:
case N_VAR_DECL: {
if (symtab_find_local(symtab, node->name)) {
fprintf(stderr, "Redeclaration of variable '%s'\n", node->name);
exit(1);
}
struct symbol *sym = symbol_make_var(node->name, node->rtype);
sym->ref = ref_next_register();
symtab_insert(symtab, sym);
ir_append(ir, irins_make_01(INS_MOV, sym->ref, ref_imm(node->value)));
break;
}
case N_FUNC_DECL: {
if (symtab_find(symtab, node->name)) {
fprintf(stderr, "Redeclaration of function '%s'\n", node->name);
exit(1);
}
int numparams = node_list_length(node->child1);
struct symbol *sym = symbol_make_func(node->name, node->rtype, numparams);
write_func_params(sym->params, node->child1);
symtab_insert(symtab_root(symtab), sym);
ir_append(ir, irins_make_name(INS_LBL, strdup(node->name)));
symtab = symtab_sub(symtab);
compile_node(ir, symtab, node->child2);
symtab = symtab_delete_get_parent(symtab);
break;
}
case N_IF: {
char *elselbl = gen_label_name();
char *afterlbl = gen_label_name();
struct ref condref = compile_expr(ir, symtab, node->child1);
ir_append(ir, irins_make_12(INS_TEST, condref, condref));
ir_append(ir, irins_make_jcc(elselbl, CCZ));
compile_node(ir, symtab, node->child2);
ir_append(ir, irins_make_name(INS_JMP, afterlbl));
ir_append(ir, irins_make_name(INS_LBL, elselbl));
compile_node(ir, symtab, node->child3);
ir_append(ir, irins_make_name(INS_LBL, afterlbl));
break;
}
case N_WHILE: {
char *startlbl = gen_label_name();
char *afterlbl = gen_label_name();
ir_append(ir, irins_make_name(INS_LBL, startlbl));
struct ref condref = compile_expr(ir, symtab, node->child1);
ir_append(ir, irins_make_12(INS_TEST, condref, condref));
ir_append(ir, irins_make_jcc(afterlbl, CCZ));
compile_node(ir, symtab, node->child2);
ir_append(ir, irins_make_name(INS_JMP, startlbl));
ir_append(ir, irins_make_name(INS_LBL, afterlbl));
break;
}
case N_RETURN: {
struct ref ref = compile_expr(ir, symtab, node->child1);
ir_append(ir, irins_make_1(INS_RETV, ref));
break;
}
default: // hmm, maybe it's an expression statement?
compile_expr(ir, symtab, node);
break;
}
}
struct ir* compile(struct node *node) {
struct ir *ir = ir_make();
struct symtab *symtab = symtab_make();
compile_node(ir, symtab, node);
return ir;
}
|
