compiler

Unnamed Compiled Systems Language Project
git clone http://frotz.net/git/compiler.git
Log | Files | Refs

codegen-ir.c (25254B)


      1 // Copyright 2021, Brian Swetland <swetland@frotz.net>
      2 // Licensed under the Apache License, Version 2.0.
      3 
      4 #include "ir.h"
      5 
      6 // architecture-specific
      7 
      8 #define REG_PHYS_COUNT 16
      9 
     10 str reg_phys_name[REG_PHYS_COUNT] = {
     11 	"r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7",
     12 	"r8", "r9", "r10", "r11", "fp", "sb", "sp", "lr",
     13 };
     14 
     15 #define REG_R0 (0)
     16 #define REG_FP (12)
     17 #define REG_SB (13)
     18 #define REG_SP (14)
     19 #define REG_LR (15)
     20 
     21 // for errors, etc
     22 #define REG_NONE -1
     23 
     24 #define REG_VIRT_0 -2
     25 
     26 // ------------------------------------------------------------------
     27 
     28 Ast err_last_func = nil;
     29 Ast err_ast = nil;
     30 
     31 void dump_error_ctxt() {
     32 	fprintf(stderr, "\n");
     33 	if (err_last_func) {
     34 		ast_dump(stderr, err_last_func, err_ast);
     35 	}
     36 	fprintf(stderr, "\n");
     37 }
     38 
     39 // global labels start at -1 ...
     40 i32 global_next = 1;
     41 str global_names[1024];
     42 
     43 i32 label_get_global(str name) {
     44 	i32 n = 1;
     45 	while (n < global_next) {
     46 		if (global_names[n] == name) {
     47 			return -n;
     48 		}
     49 		n++;
     50 	}
     51 	global_next = n + 1;
     52 	global_names[n] = name;
     53 	return -n;
     54 }
     55 
     56 // local labels start at 0..
     57 // virtual registers start at 0...
     58 Inst ins_last_placed = nil;
     59 i32 reg_next = REG_VIRT_0;
     60 
     61 i32 reg_get() {
     62 	i32 r = reg_next;
     63 	reg_next = r - 1;
     64 	return r;
     65 }
     66 
     67 // table of labels
     68 i32 label_next = 0;
     69 Inst label_idx[1024];
     70 BBlock bb_idx[1024];
     71 
     72 Inst _inst_make(u32 op, i32 a, i32 b, i32 c) {
     73 	// add opcode-specific property bitflags to allow
     74 	// for quick property testing
     75 	op |= ins_props[op & INS_OP_MASK];
     76 
     77 	Inst ins = malloc(sizeof(InstRec));
     78 	ins->next = nil;
     79 	ins->prev = nil;
     80 	ins->op = op;
     81 	ins->a = a;
     82 	ins->b = b;
     83 	ins->c = c;
     84 	return ins;
     85 }
     86 
     87 // obtain a (detached) label instruction
     88 // branches may target it before it is placed
     89 // with inst_label()
     90 i32 label_get() {
     91 	i32 a = label_next;
     92 	Inst ins = _inst_make(INS_LABEL, a, 0, 0);
     93 	label_idx[a] = ins;
     94 	label_next = a + 1;
     95 	return a;
     96 }
     97 
     98 // allocate an instruction and add it to the graph
     99 i32 inst_make(u32 op, i32 a, i32 b, i32 c) {
    100 	Inst ins = _inst_make(op, a, b, c);
    101 	ins->prev = ins_last_placed;
    102 	ins_last_placed->next = ins;
    103 	ins_last_placed = ins;
    104 	return a;
    105 }
    106 
    107 // place a label obtained with label_get()
    108 i32 inst_label(i32 a) {
    109 	if ((a < 0) || (a >= label_next)) {
    110 		error("invalid label #%d\n", a);
    111 	}
    112 	Inst ins = label_idx[a];
    113 	if (ins->b != 0) {
    114 		error("label #%d placed twice!", a);
    115 	}
    116 	// mark as placed
    117 	ins->b = 1;
    118 	// add to graph
    119 	ins->prev = ins_last_placed;
    120 	ins_last_placed->next = ins;
    121 	ins_last_placed = ins;
    122 	return a;
    123 }
    124 
    125 // branch instructions use this to validate targets
    126 void inst_use_label(i32 a) {
    127 	if ((a < 0) || (a >= label_next)) {
    128 		error("invalid label #%d\n", a);
    129 	}
    130 	// bump edge count
    131 	label_idx[a]->c ++;
    132 }
    133 
    134 i32 inst_label_global(str name) {
    135 	return inst_make(INS_LABEL, label_get_global(name), 1, 0);
    136 }
    137 
    138 i32 inst_alu(u32 op, i32 b, i32 c) {
    139 	if (op > INS_XOR) error("inst_alu invalid alu op");
    140 	return inst_make(op, reg_get(), b, c);
    141 }
    142 i32 inst_alui(u32 op, i32 b, i32 imm) {
    143 	if (op > INS_XOR) error("inst_alui invalid alu op");
    144 	return inst_make(op | INF_C_IMM, reg_get(), b, imm);
    145 }
    146 void inst_aluix(u32 op, i32 a, i32 b, i32 imm) {
    147 	if (op > INS_XOR) error("inst_alui invalid alu op");
    148 	inst_make(op | INF_C_IMM, a, b, imm);
    149 }
    150 i32 inst_phi(i32 b, i32 c) {
    151 	return inst_make(INS_PHI, reg_get(), b, c);
    152 }
    153 i32 inst_movi(i32 imm) {
    154 	return inst_make(INS_MOV | INF_C_IMM, reg_get(), 0, imm);
    155 }
    156 i32 inst_mov(i32 c) {
    157 	return inst_make(INS_MOV, reg_get(), 0, c);
    158 }
    159 i32 inst_movx(i32 a, i32 c) {
    160 	return inst_make(INS_MOV, a, 0, c);
    161 }
    162 i32 inst_ldb(i32 b, i32 c) {
    163 	return inst_make(INS_LD | INF_SZ_U8, reg_get(), b, c);
    164 }
    165 i32 inst_ldw(i32 b, i32 c) {
    166 	return inst_make(INS_LD | INF_SZ_U32, reg_get(), b, c);
    167 }
    168 i32 inst_ldbi(i32 b, i32 imm) {
    169 	return inst_make(INS_LD | INF_SZ_U8 | INF_C_IMM, reg_get(), b, imm);
    170 }
    171 i32 inst_ldwi(i32 b, i32 imm) {
    172 	return inst_make(INS_LD | INF_SZ_U32 | INF_C_IMM, reg_get(), b, imm);
    173 }
    174 void inst_ldwix(i32 a, i32 b, i32 imm) {
    175 	inst_make(INS_LD | INF_SZ_U32 | INF_C_IMM, a, b, imm);
    176 }
    177 void inst_stb(i32 a, i32 b, i32 c) {
    178 	inst_make(INS_ST | INF_SZ_U8, a, b, c);
    179 }
    180 void inst_stw(i32 a, i32 b, i32 c) {
    181 	inst_make(INS_ST | INF_SZ_U32, a, b, c);
    182 }
    183 void inst_stbi(i32 a, i32 b, i32 imm) {
    184 	inst_make(INS_ST | INF_SZ_U8 | INF_C_IMM, a, b, imm);
    185 }
    186 void inst_stwi(i32 a, i32 b, i32 imm) {
    187 	inst_make(INS_ST | INF_SZ_U32 | INF_C_IMM, a, b, imm);
    188 }
    189 i32 inst_br(i32 label) {
    190 	inst_use_label(label);
    191 	return inst_make(INS_B, label, 0, 0);
    192 }
    193 i32 inst_br_cmp(u32 op, i32 label, i32 b, i32 c) {
    194 	inst_use_label(label);
    195 	if ((op < INS_BEQ) || (op > INS_BGE)) {
    196 		error("inst_branch_cond inavlid branch op");
    197 	}
    198 	return inst_make(op, label, b, c);
    199 }
    200 i32 inst_br_cmpi(u32 op, i32 label, i32 b, i32 imm) {
    201 	inst_use_label(label);
    202 	if ((op < INS_BEQ) || (op > INS_BGE)) {
    203 		error("inst_branch_condi inavlid branch op");
    204 	}
    205 	return inst_make(op | INF_C_IMM, label, b, imm);
    206 }
    207 void inst_call(i32 label) {
    208 	if (label >= 0) {
    209 		error("cannot CALL local label #%d\n", label);
    210 	}
    211 	inst_make(INS_CALL, label, 0, 0);
    212 }
    213 void inst_ret(i32 a) {
    214 	inst_make(INS_RET, a, 0, 0);
    215 }
    216 
    217 u32 rel_op_to_ins_tab[6] = { INS_BEQ, INS_BNE, INS_BLT, INS_BLE, INS_BGT, INS_BGE };
    218 u32 rel_op_to_inv_ins_tab[6] = { INS_BNE, INS_BEQ, INS_BGE, INS_BGT, INS_BLE, INS_BLT };
    219 u32 add_op_to_ins_tab[4] = { INS_ADD, INS_SUB, INS_OR, INS_XOR };
    220 u32 mul_op_to_ins_tab[6] = { INS_MUL, INS_SDIV, INS_SREM, INS_AND, INS_LSL, INS_ASR };
    221 
    222 // current loop continue and exit labels
    223 i32 loop_continue = 0;
    224 i32 loop_exit = 0;
    225 // current function exit label
    226 i32 func_exit = 0;
    227 
    228 void gen_block(Ast node);
    229 i32 gen_expr(Ast node);
    230 
    231 void gen_trace(str msg) {
    232 //	fprintf(stderr, "%p %p %s\n", err_last_func, err_ast, msg);
    233 }
    234 
    235 void gen_src_xref(Ast node) {
    236 	ctx.xref[ctx.pc/4] = node->srcloc;
    237 }
    238 
    239 // obtain base register and offset
    240 // for the memory backing a Symbol
    241 void sym_get_loc(Symbol sym, i32* base, i32* offset) {
    242 	if (sym->kind == SYM_LOCAL) {
    243 		*base = REG_FP;
    244 		*offset = -(4 + sym->value);
    245 	} else if (sym->kind == SYM_PARAM) {
    246 		*base = REG_FP;
    247 		*offset = 8 + sym->value;
    248 	} else if (sym->kind == SYM_GLOBAL) {
    249 		*base = REG_SB;
    250 		*offset = sym->value;
    251 	} else {
    252 		error("non-register-relative symbol");
    253 	}
    254 }
    255 
    256 i32 gen_addr_expr(Ast node) {
    257 	if (node->kind == AST_DEREF) {
    258 		return inst_ldwi(gen_addr_expr(node->c0), 0);
    259 	} else if (node->kind == AST_INDEX) {
    260 		i32 esz = node->type->size;
    261 		i32 raddr = gen_addr_expr(node->c0);
    262 		i32 roff = gen_expr(node->c1);
    263 		if (esz > 1) {
    264 			roff = inst_alui(INS_MUL, roff, esz);
    265 		}
    266 		return inst_ldw(raddr, roff);
    267 	} else if (node->kind == AST_FIELD) {
    268 		i32 raddr = gen_addr_expr(node->c0);
    269 		i32 off = node->c1->sym->value;
    270 		// HANDLE non-word-sized
    271 		return inst_alui(INS_ADD, raddr, off);
    272 	} else if (node->kind == AST_SYMBOL) {
    273 		i32 base;
    274 		i32 offset;
    275 		sym_get_loc(node->sym, &base, &offset);
    276 		return inst_alui(INS_ADD, base, offset);
    277 	} else if (node->kind == AST_ADDROF) {
    278 		return gen_addr_expr(node->c0);
    279 	} else {
    280 		err_ast = node;
    281 		error("gen_addr_expr cannot handle %s", ast_kind[node->kind]);
    282 		return -1;
    283 	}
    284 }
    285 
    286 i32 gen_assign(Ast lhs, Ast expr) {
    287 	gen_trace("gen_assign()");
    288 
    289 	i32 base;
    290 	i32 offset;
    291 	if (lhs->kind == AST_SYMBOL) {
    292 		sym_get_loc(lhs->sym, &base, &offset);
    293 	} else {
    294 		base = gen_addr_expr(lhs);
    295 		offset = 0;
    296 	}
    297 	i32 rval = gen_expr(expr);
    298 
    299 	if (lhs->type->size == 4) {
    300 		inst_stwi(rval, base, offset);
    301 		return rval;
    302 	} else if (lhs->type->size == 1) {
    303 		inst_stbi(rval, base, offset);
    304 		return rval;
    305 	} else {
    306 		err_ast = lhs;
    307 		error("unexpected size %u store", lhs->type->size);
    308 		return -1;
    309 	}
    310 }
    311 
    312 i32 gen_call(Ast node) {
    313 	gen_src_xref(node);
    314 	gen_trace("gen_call()");
    315 	Symbol sym = node->c0->sym;
    316 	Ast arg = node->c2;
    317 	Symbol param = sym->first;
    318 
    319 	if (sym->flags & SYM_IS_BUILTIN) {
    320 		// store to special io range
    321 		i32 rval = gen_expr(arg);
    322 		i32 raddr = inst_movi(0xFFFF0000);
    323 		inst_stwi(rval, raddr, 0x100 + sym->value * 4);
    324 	} else {
    325 		u32 sizeargs = 4 * sym->type->len;
    326 		if (sizeargs > 0) {
    327 			inst_aluix(INS_SUB, REG_SP, REG_SP, sizeargs);
    328 			u32 n = 0;
    329 			while (arg != nil) {
    330 				u32 r;
    331 				if (param->type->kind == TYPE_POINTER) {
    332 					// XXX or ptr type?
    333 					r = gen_addr_expr(arg);
    334 				} else {
    335 					r = gen_expr(arg);
    336 				}
    337 				inst_stwi(r, REG_SP, 4 * n);
    338 				arg = arg->c2;
    339 				param = param->next;
    340 				n = n + 1;
    341 			}
    342 			inst_call(label_get_global(sym->name->text));
    343 			inst_aluix(INS_ADD, REG_SP, REG_SP, sizeargs);
    344 		} else {
    345 			inst_call(label_get_global(sym->name->text));
    346 		}
    347 	}
    348 	if (sym->type->base != ctx.type_void) {
    349 		// return is in phys r0
    350 		return inst_mov(REG_R0);
    351 	} else {
    352 		return REG_NONE;
    353 	}
    354 }
    355 
    356 i32 gen_binop(Ast node, u32 op) {
    357 	gen_trace("gen_binop()");
    358 	i32 left = gen_expr(node->c0);
    359 	i32 right = gen_expr(node->c1);
    360 	return inst_alu(op, left, right);
    361 }
    362 
    363 i32 gen_relop(Ast node, u32 op) {
    364 	gen_trace("gen_relop()");
    365 	i32 left = gen_expr(node->c0);
    366 	i32 right = gen_expr(node->c1);
    367 
    368 	i32 label = label_get();
    369 	i32 rtrue = inst_movi(1);
    370 	inst_br_cmp(op, label, left, right);
    371 	i32 rfalse = inst_movi(0);
    372 	inst_label(label);
    373 	return inst_phi(rtrue, rfalse);
    374 }
    375 
    376 i32 gen_branch_if_expr_false(Ast node, i32 label) {
    377 	if (ast_kind_is_relop(node->kind)) {
    378 		u32 op = rel_op_to_inv_ins_tab[node->kind - AST_EQ];
    379 		i32 left = gen_expr(node->c0);
    380 		i32 right = gen_expr(node->c1);
    381 		return inst_br_cmp(op, label, left, right);
    382 	} else {
    383 		i32 r = gen_expr(node);
    384 		return inst_br_cmpi(INS_BEQ, label, r, 0);
    385 	}
    386 }
    387 
    388 
    389 i32 gen_short_circuit_op(Ast node, u32 cc, u32 sc) {
    390 #if 0
    391 	u32 r = gen_expr(node->c0);
    392 	emit_mov(R11, r); // set z flag
    393 	put_reg(r);
    394 	u32 l0_br_sc = ctx.pc;
    395 	emit_bi(cc, 0);
    396 	r = gen_expr(node->c1);
    397 	emit_mov(R11, r); // set z flag
    398 	put_reg(r);
    399 	u32 l1_br_sc = ctx.pc;
    400 	emit_bi(cc, 0);
    401 	r = get_reg_tmp();
    402 	emit_movi(r, !sc);
    403 	u32 l2_br_exit = ctx.pc;
    404 	emit_bi(AL, 0);
    405 	fixup_branch_fwd(l0_br_sc);
    406 	fixup_branch_fwd(l1_br_sc);
    407 	emit_movi(r, sc);
    408 	fixup_branch_fwd(l2_br_exit);
    409 	return r;
    410 #endif
    411 	return -1;
    412 }
    413 
    414 i32 gen_array_read(Ast node) {
    415 	i32 raddr = gen_addr_expr(node->c0);
    416 	i32 roff = gen_expr(node->c1);
    417 
    418 	u32 sz = node->c0->type->base->size;
    419 	if (sz > 1) {
    420 		roff = inst_alui(INS_MUL, roff, sz);
    421 	}
    422 	if (sz == 1) {
    423 		return inst_ldb(raddr, roff);
    424 	} else {
    425 		return inst_ldw(raddr, roff);
    426 	}
    427 }
    428 
    429 i32 gen_struct_read(Ast node) {
    430 	u32 raddr = gen_addr_expr(node->c0);
    431 	u32 off = node->c1->sym->value;
    432 	u32 sz = node->c1->type->size;
    433 	if (sz == 1) {
    434 		return inst_ldbi(raddr, off);
    435 	} else if (sz == 4) {
    436 		return inst_ldwi(raddr, off);
    437 	} else {
    438 		err_ast = node;
    439 		error("unsupported field size");
    440 		return -1;
    441 	}
    442 }
    443 
    444 i32 gen_expr(Ast node) {
    445 	err_ast = node;
    446 	gen_src_xref(node);
    447 	gen_trace("gen_expr()");
    448 	u32 kind = node->kind;
    449 	if (kind == AST_CONST) {
    450 		return inst_movi(node->ival);
    451 	} else if (kind == AST_SYMBOL) {
    452 		// XXX type checking here or before
    453 		if (node->sym->kind == SYM_CONST) {
    454 			return inst_movi(node->sym->value);
    455 		} else {
    456 			i32 base;
    457 			i32 offset;
    458 			//XXX size
    459 			sym_get_loc(node->sym, &base, &offset);
    460 			return inst_ldwi(base, offset);
    461 		}
    462 	} else if (ast_kind_is_relop(kind)) {
    463 		return gen_relop(node, rel_op_to_ins_tab[kind - AST_EQ]);
    464 	} else if (ast_kind_is_addop(kind)) {
    465 		return gen_binop(node, add_op_to_ins_tab[kind - AST_ADD]);
    466 	} else if (ast_kind_is_mulop(kind)) {
    467 		return gen_binop(node, mul_op_to_ins_tab[kind - AST_MUL]);
    468 	} else if (kind == AST_BOOL_OR) {
    469 		return gen_short_circuit_op(node, INS_BNE, 1);
    470 	} else if (kind == AST_BOOL_AND) {
    471 		return gen_short_circuit_op(node, INS_BEQ, 0);
    472 	} else if (kind == AST_ASSIGN) {
    473 		return gen_assign(node->c0, node->c1);
    474 	} else if (kind == AST_NEG) {
    475 		i32 r = gen_expr(node->c0);
    476 		i32 z = inst_movi(0);
    477 		return inst_alu(INS_SUB, z, r);
    478 	} else if (kind == AST_NOT) {
    479 		i32 r = gen_expr(node->c0);
    480 		return inst_alui(INS_XOR, r, 0xffffffff);
    481 	} else if (kind == AST_BOOL_NOT) {
    482 		u32 r = gen_expr(node->c0);
    483 		return inst_alui(INS_XOR, r, r);
    484 	} else if (kind == AST_CALL) {
    485 		return gen_call(node);
    486 	} else if (kind == AST_INDEX) {
    487 		return gen_array_read(node);
    488 	} else if (kind == AST_FIELD) {
    489 		return gen_struct_read(node);
    490 	} else {
    491 		error("gen_expr cannot handle %s\n", ast_kind[node->kind]);
    492 	}
    493 	return 0;
    494 }
    495 
    496 void gen_while(Ast node) {
    497 	gen_trace("gen_while()");
    498 
    499 	// save branch targets
    500 	i32 old_loop_continue = loop_continue;
    501 	i32 old_loop_exit = loop_exit;
    502 
    503 	loop_continue = label_get();
    504 	loop_exit = label_get();
    505 
    506 	inst_label(loop_continue);
    507 
    508 	gen_branch_if_expr_false(node->c0, loop_exit);
    509 
    510 	gen_block(node->c1);
    511 
    512 	inst_br(loop_continue);
    513 
    514 	inst_label(loop_exit);
    515 
    516 	// restore branch targets
    517 	loop_continue = old_loop_continue;
    518 	loop_exit = old_loop_exit;
    519 }
    520 
    521 void gen_if_else(Ast node) {
    522 	// fixups for jumps to the very end
    523 	FixupRec if_exit;
    524 	if_exit.next = nil;
    525 
    526 	gen_trace("gen_if()");
    527 	// IF contains one or more IFELSE nodes
    528 	node = node->c0;
    529 
    530 	// compute if expr
    531 	// branch ahead if false;
    532 	i32 l0_br_false = gen_branch_if_expr_false(node->c0, label_get());
    533 
    534 	i32 l_exit = label_get();
    535 
    536 	// exec then block
    537 	gen_block(node->c1);
    538 
    539 	node = node->c2;
    540 	while (node != nil) {
    541 		// jump from end of 'then' block to end
    542 		inst_br(l_exit);
    543 
    544 		// false jump (over 'then' block) target is here
    545 		inst_label(l0_br_false);
    546 
    547 		if (node->kind == AST_IFELSE) { // ifelse ...
    548 			gen_trace("gen_ifelse()");
    549 			l0_br_false = gen_branch_if_expr_false(node->c0, label_get());
    550 
    551 			gen_block(node->c1);
    552 			node = node->c2;
    553 		} else { // else ...
    554 			gen_trace("gen_else()");
    555 			gen_block(node);
    556 
    557 			// done, place exit label
    558 			inst_label(l_exit);
    559 			return;
    560 		}
    561 	}
    562 
    563 	// place final false label and exit label
    564 	inst_label(l0_br_false);
    565 	inst_label(l_exit);
    566 }
    567 
    568 void gen_block(Ast node);
    569 
    570 void gen_stmt(Ast node) {
    571 	err_ast = node;
    572 	gen_src_xref(node);
    573 	gen_trace("gen_stmt()\n");
    574 	u32 kind = node->kind;
    575 	if (kind == AST_EXPR) {
    576 		gen_expr(node->c0);
    577 	} else if (kind == AST_IF) {
    578 		gen_if_else(node);
    579 	} else if (kind == AST_WHILE) {
    580 		gen_while(node);
    581 	} else if (kind == AST_RETURN) {
    582 		if (node->c0) {
    583 			inst_movx(REG_R0, gen_expr(node->c0));
    584 		}
    585 		inst_br(func_exit);
    586 	} else if (kind == AST_BREAK) {
    587 		inst_br(loop_exit);
    588 	} else if (kind == AST_CONTINUE) {
    589 		inst_br(loop_continue);
    590 	} else if (kind == AST_BLOCK) {
    591 		gen_block(node);
    592 	} else {
    593 		error("gen_stmt cannot handle %s\n", ast_kind[kind]);
    594 	}
    595 }
    596 
    597 void gen_block(Ast node) {
    598 	gen_trace("gen_block()\n");
    599 	gen_src_xref(node);
    600 	node = node->c2;
    601 	while (node != nil) {
    602 		gen_stmt(node);
    603 		node = node->c2;
    604 	}
    605 }
    606 
    607 // before prologue  after prologue
    608 // ---------------  --------------
    609 //       arg2             oldarg2
    610 //       arg1             oldarg1
    611 // FP -> arg0             oldarg0
    612 //       lrsave           oldlr
    613 //       fpsave           oldfp   <-+
    614 //       loc0             oldloc0   |
    615 //       loc1             oldloc1   |
    616 //       ...              ...       |
    617 //       locn             oldlocn   |
    618 //       callarg2         arg2      |
    619 //       callarg1         arg1      |
    620 // SP -> callarg0         arg0      |
    621 //                        lrsave    |
    622 //                  FP -> fpsave ---+
    623 //                        loc0
    624 //                        loc1
    625 //                        ...
    626 //                  SP -> locn
    627 
    628 Inst gen_func(Ast node) {
    629 	err_last_func = node;
    630 	err_ast = node;
    631 
    632 	gen_trace("gen_func()\n");
    633 	gen_src_xref(node);
    634 
    635 	InstRec head;
    636 
    637 	// setup initial state
    638 	ins_last_placed = &head;
    639 	reg_next = REG_VIRT_0;
    640 	label_next = 0;
    641 
    642 	inst_label(label_get());
    643 	Inst first = ins_last_placed;
    644 
    645 	// local space plus saved lr and fp
    646 	u32 x = node->sym->type->size + 8;
    647 
    648 	// generate prologue
    649 #if 0
    650 	node->sym->value = ctx.pc;
    651 	node->sym->flags |= SYM_IS_PLACED;
    652 #endif
    653 	inst_aluix(INS_SUB, REG_SP, REG_SP, x);
    654 	inst_stwi(REG_LR, REG_SP, x - 4);
    655 	inst_stwi(REG_FP, REG_SP, x - 8);
    656 	inst_aluix(INS_ADD, REG_FP, REG_SP, x - 8);
    657 
    658 	// save for use by return, etc
    659 	func_exit = label_get();
    660 
    661 	// generate body
    662 	gen_block(node->c0);
    663 
    664 	// generate epilogue
    665 	inst_label(func_exit);
    666 	inst_ldwix(REG_LR, REG_FP, 4);
    667 	inst_ldwix(REG_FP, REG_FP, 0);
    668 	inst_aluix(INS_ADD, REG_SP, REG_SP, x);
    669 	inst_ret(REG_LR);
    670 
    671 	inst_label(label_get());
    672 
    673 	head.next->prev = nil;
    674 	return head.next;
    675 }
    676 
    677 void inst_disasm(FILE* fp, Inst ins);
    678 
    679 i32 bb_id_counter = 0;
    680 
    681 BBlock make_bblock(i32 pcount) {
    682 	i32 sz = sizeof(BBlockRec) + pcount * 4;
    683 	BBlock bb = malloc(sz);
    684 	memset(bb, 0, sz);
    685 	//bb->pcount = pcount;
    686 	bb->id = bb_id_counter;
    687 	bb_id_counter++;
    688 	return bb;
    689 }
    690 
    691 bool inst_is_label(Inst ins) {
    692 	return ins->op & INF_IS_LABEL;
    693 }
    694 bool inst_is_uncond_branch(Inst ins) {
    695 	return ins->op & INF_IS_B_UC;
    696 }
    697 bool inst_is_cond_branch(Inst ins) {
    698 	return ins->op & INF_IS_B_CC;
    699 }
    700 bool inst_is_branch(Inst ins) {
    701 	return ins->op & INF_IS_B;
    702 }
    703 bool inst_is_return(Inst ins) {
    704 	return ins->op & INF_IS_RET;
    705 }
    706 
    707 // dispose of an instruction
    708 // - removes from graph
    709 // - adjusts refcount for target label if a branch op
    710 // - DOES NO HOUSEKEEPING for labels (remove at your own risk)
    711 Inst opt_inst_destroy(Inst ins) {
    712 	u32 op = ins->op & INS_OP_MASK;
    713 	if (inst_is_branch(ins)) {
    714 		Inst tgt = label_idx[ins->a];
    715 		// decrement inbound count on branch target
    716 		tgt->c --;
    717 	}
    718 	ins->op = INS_DEAD;
    719 
    720 	Inst next = ins->next;
    721 	Inst prev = ins->prev;
    722 
    723 	next->prev = prev;
    724 	prev->next = next;
    725 
    726 	ins->next = nil;
    727 	ins->prev = nil;
    728 
    729 	free(ins);
    730 	return next;
    731 }
    732 
    733 // clean up messes leftover from code generation
    734 // - remove unconditional branches to the next instruction
    735 // - remove labels with no inbounds
    736 // - merge adjacent labels
    737 // - insert labels after flow control departures from straightline
    738 //   if such a label does not already exist
    739 // - remove code between unconditional branches and labels
    740 BBlock opt_func_label_cleanup(Inst first, Inst last) {
    741 	// skip the global label and start with the local label L0
    742 	Inst ins = first->next;
    743 	while (ins != last) {
    744 		if (inst_is_uncond_branch(ins) && !inst_is_label(ins->next)) {
    745 			// any code between an uncond branch and a label is dead
    746 			opt_inst_destroy(ins->next);
    747 			continue;
    748 		}
    749 		if (inst_is_uncond_branch(ins)) {
    750 			// do we target a label between us and the next inst?
    751 			Inst x = ins->next;
    752 			bool remove = false;
    753 			// in case we've replaced its target, obtain the label
    754 			// id of the target via the label index table
    755 			i32 id = label_idx[ins->a]->a;
    756 			while (inst_is_label(x) && (x != last)) {
    757 				if (x->a == id) {
    758 					// we're uncond jumping to an immediately
    759 					// following label.
    760 					remove = true;
    761 					break;
    762 				}
    763 				x = x->next;
    764 			}
    765 			if (remove) {
    766 				ins = opt_inst_destroy(ins);
    767 				continue;
    768 			}
    769 		}
    770 		if (inst_is_label(ins)) {
    771 			if ((ins->c == 0) && !(inst_is_cond_branch(ins->prev))) {
    772 				// nobody jumps here
    773 				// remove label
    774 				label_idx[ins->a] = nil;
    775 				ins = opt_inst_destroy(ins);
    776 				continue;
    777 			}
    778 			if (inst_is_label(ins->prev)) {
    779 				// if prev was also a label, merge with it...
    780 				// 1. acquire its refcount
    781 				ins->prev->c += ins->c;
    782 				// 2. acquire its slot (redirect all inbounds to us)
    783 				label_idx[ins->prev->a] = ins;
    784 				// 3. remove from instruction stream
    785 				ins->op = INS_DEAD;
    786 				ins = opt_inst_destroy(ins);
    787 				continue;
    788 			}
    789 		}
    790 		if (inst_is_cond_branch(ins) && !inst_is_label(ins->next)) {
    791 			// flow control point not followed by a label
    792 			Inst next = ins->next;
    793 			ins_last_placed = ins;
    794 			inst_label(label_get());
    795 			ins_last_placed->next = next;
    796 			next->prev = ins_last_placed;
    797 		}
    798 		if (inst_is_return(ins)) {
    799 			// returns are treated as B Llast
    800 			// from a flow-control standpoint
    801 			last->c++;
    802 		}
    803 		ins = ins->next;
    804 	}
    805 
    806 	// for each non-redirected label, create a basic block
    807 	// sized for the max possible inbound edges of that label
    808 	i32 n = 0;
    809 	BBlock bblast = nil;
    810 	while (n < label_next) {
    811 		if ((label_idx[n] != nil) && (label_idx[n]->a == n)) {
    812 			BBlock bb = make_bblock(label_idx[n]->c + 1);
    813 			bb_idx[n] = bb;
    814 			bb_idx[n]->first = label_idx[n];
    815 			if (bblast != nil) {
    816 				bblast->list = bb;
    817 			}
    818 			bblast = bb;
    819 		} else {
    820 			bb_idx[n] = nil;
    821 		}
    822 		n++;
    823 	}
    824 
    825 	// For each branch instruction, fixup any indirections
    826 	// so they point at their true target label.
    827 	// Hook up prev[] and next[] pointers between bblocks
    828 	ins = first->next;
    829 	BBlock bb = bb_idx[0];
    830 	bb->flags |= BB_FIRST;
    831 	while (ins != nil) {
    832 		if (inst_is_label(ins)) {
    833 			bb->last = ins;
    834 			BBlock nextbb = bb_idx[ins->a];
    835 			// if control flows from previous instruction
    836 			// (last in prev bb) to this one, bidirectionally
    837 			// link us
    838 			if (!inst_is_uncond_branch(ins->prev) &&
    839 			    !inst_is_return(ins->prev)) {
    840 				nextbb->prev[nextbb->pcount] = bb;
    841 				nextbb->pcount++;
    842 				if (bb->next[0] == nil) {
    843 					bb->next[0] = nextbb;
    844 				} else {
    845 					bb->next[1] = nextbb;
    846 				}
    847 			}
    848 			bb = nextbb;
    849 		} else if (inst_is_branch(ins)) {
    850 			Inst target = label_idx[ins->a];
    851 			if (ins->a != target->a) {
    852 				// we've been redirected, let's fix up
    853 				ins->a = target->a;
    854 			}
    855 			BBlock tbb = bb_idx[target->a];
    856 
    857 			// we're branching from bb to tbb
    858 			tbb->prev[tbb->pcount] = bb;
    859 			tbb->pcount++;
    860 			if (bb->next[0] == nil) {
    861 				bb->next[0] = tbb;
    862 			} else {
    863 				bb->next[1] = tbb;
    864 			}
    865 		} else if (inst_is_return(ins)) {
    866 			BBlock tbb = bb_idx[last->a];
    867 
    868 			// return is like a branch to the last label/bb
    869 			tbb->prev[tbb->pcount] = bb;
    870 			tbb->pcount++;
    871 			if (bb->next[0] == nil) {
    872 				bb->next[0] = tbb;
    873 			} else {
    874 				bb->next[1] = tbb;
    875 			}
    876 		}
    877 		ins = ins->next;
    878 	}
    879 
    880 	bb->flags |= BB_LAST;
    881 
    882 	// first bb has pcount 0 but prev[0] points to last for convenience
    883 	bb_idx[0]->prev[0] = bb;
    884 	return bb_idx[0];
    885 }
    886 
    887 BBlock opt_func(Ast node, Inst first, Inst last) {
    888 	BBlock bblist = opt_func_label_cleanup(first, last);
    889 	return bblist;
    890 }
    891 
    892 
    893 void dis_func(FILE* fp, Inst ins, str name) {
    894 	fprintf(fp,"@%s:\n", name);
    895 	while (ins != nil) {
    896 		inst_disasm(fp, ins);
    897 		ins = ins->next;
    898 	}
    899 }
    900 
    901 void graph_func(FILE* fp, str fn, BBlock blocks) {
    902 	fprintf(fp,
    903 		"digraph g {\n"
    904 		"graph [ rankdir=TB; ];\n"
    905 		"node [ shape=plain; ];\n");
    906 	BBlock bb = blocks;
    907 	while (bb != nil) {
    908 		fprintf(fp, "\"%p\" [ label=<<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n", bb);
    909 		Inst ins = bb->first;
    910 		if (bb == blocks) {
    911 			fprintf(fp,"<TR><TD BGCOLOR=\"gray\" ALIGN=\"left\">@%s:</TD></TR>\n", fn);
    912 		}
    913 		while (ins != bb->last) {
    914 			if (inst_is_label(ins)) {
    915 				fprintf(fp,"<TR><TD BGCOLOR=\"gray\" ALIGN=\"left\">");
    916 			} else {
    917 				fprintf(fp,"<TR><TD ALIGN=\"left\">");
    918 			}
    919 			inst_disasm(fp, ins);
    920 			fprintf(fp,"</TD></TR>\n");
    921 			ins = ins->next;
    922 		}
    923 		fprintf(fp, "</TABLE>>; ];\n");
    924 		if (bb->next[0]) {
    925 			fprintf(fp, "\"%p\" -> \"%p\" [ ];\n", bb, bb->next[0]);
    926 		}
    927 		if (bb->next[1]) {
    928 			fprintf(fp, "\"%p\" -> \"%p\" [ ];\n", bb, bb->next[1]);
    929 		}
    930 		bb = bb->list;
    931 	}
    932 	fprintf(fp, "}\n");
    933 }
    934 
    935 void gen_program(Ast node) {
    936 	gen_trace( "gen_risc5_simple()\n");
    937 
    938 	// TODO: program prologue
    939 
    940 	node = node->c2;
    941 	while (node != nil) {
    942 		if (node->kind == AST_FUNC) {
    943 			str fn = node->sym->name->text;
    944 			Inst first = gen_func(node);
    945 			Inst last = ins_last_placed;
    946 			char tmp[256];
    947 			sprintf(tmp, "debug/%s.ast.ir", fn);
    948 			FILE* fp = fopen(tmp, "w");
    949 			if (fp != nil) {
    950 				dis_func(fp, first, fn);
    951 				fclose(fp);
    952 			}
    953 			BBlock bblocks = opt_func(node, first, last);
    954 			sprintf(tmp, "debug/%s.bb.ir", fn);
    955 			fp = fopen(tmp, "w");
    956 			if (fp != nil) {
    957 				dis_func(fp, first, fn);
    958 				fclose(fp);
    959 			}
    960 			sprintf(tmp, "debug/%s.bb.dot", fn);
    961 			fp = fopen(tmp, "w");
    962 			if (fp != nil) {
    963 				graph_func(fp, fn, bblocks);
    964 				fclose(fp);
    965 			}
    966 		}
    967 		node = node->c2;
    968 	}
    969 
    970 	err_last_func = nil;
    971 
    972 	// TODO: program epilogue, globals
    973 }
    974 
    975 void prreg(FILE* fp, i32 n) {
    976 	if ((n >= 0) && (n < REG_PHYS_COUNT)) {
    977 		fprintf(fp, "$%s", reg_phys_name[n]);
    978 	} else if (n < -1) {
    979 		fprintf(fp, "%%%u", (-n) + 1);
    980 	} else {
    981 		fprintf(fp, "<ERROR>");
    982 	}
    983 }
    984 
    985 void prarg(FILE* fp, i32 n, i32 op) {
    986 	if (op & INF_C_IMM) {
    987 		fprintf(fp, "%d", n);
    988 		return;
    989 	} else {
    990 		prreg(fp, n);
    991 	}
    992 }
    993 
    994 void prlabel(FILE* fp, i32 n) {
    995 	if (n >= 0) {
    996 		fprintf(fp, "L%u", label_idx[n]->a);
    997 	} else {
    998 		fprintf(fp, "@%s", global_names[-n]);
    999 	}
   1000 }
   1001 
   1002 void inst_disasm(FILE* fp, Inst ins) {
   1003 	u32 op = ins->op & INS_OP_MASK;
   1004 	//fprintf(fp, "(%08x %08x %08x %08x)\n", ins->op, ins->a, ins->b, ins->c);
   1005 	if (op == INS_LABEL) {
   1006 		prlabel(fp, ins->a);
   1007 		fprintf(fp, ":"); // count=%u", ins->c);
   1008 	} else if (op == INS_MOV) {
   1009 		fprintf(fp, "\tmov ");
   1010 		prreg(fp, ins->a);
   1011 		fprintf(fp, ", ");
   1012 		prarg(fp, ins->c, ins->op);
   1013 	} else if ((op == INS_LD) || (op == INS_ST)) {
   1014 		str sz = isz_name[(ins->op & INF_SZ_MASK) >> INF_SZ_SHIFT];
   1015 		fprintf(fp, "\t%s%s ", ins_name[op], sz);
   1016 		prreg(fp, ins->a);
   1017 		fprintf(fp, ", [");
   1018 		prreg(fp, ins->b);
   1019 		fprintf(fp, ", ");
   1020 		prarg(fp, ins->c, ins->op);
   1021 		fprintf(fp, "]");
   1022 	} else if (op <= INS_PHI) {
   1023 		fprintf(fp, "\t%s ", ins_name[op]);
   1024 		prreg(fp, ins->a);
   1025 		fprintf(fp, ", ");
   1026 		prreg(fp, ins->b);
   1027 		fprintf(fp, ", ");
   1028 		prarg(fp, ins->c, ins->op);
   1029 	} else if (op == INS_B) {
   1030 		fprintf(fp, "\tb ");
   1031 		prlabel(fp, ins->a);
   1032 	} else if ((op >= INS_BEQ) && (op <= INS_BGE)) {
   1033 		fprintf(fp, "\t%s ", ins_name[op]);
   1034 		prlabel(fp, ins->a);
   1035 		fprintf(fp, ", ");
   1036 		prreg(fp, ins->b);
   1037 		fprintf(fp, ", ");
   1038 		prarg(fp, ins->c, ins->op);
   1039 	} else if (op == INS_CALL) {
   1040 		fprintf(fp, "\tcall ");
   1041 		prlabel(fp, ins->a);
   1042 	} else if (op == INS_RET) {
   1043 		fprintf(fp, "\tret ");
   1044 		prreg(fp, ins->a);
   1045 	} else {
   1046 		fprintf(fp, "\tinval 0x%x", ins->op);
   1047 	}
   1048 	fprintf(fp, "\n");
   1049 }
   1050 
   1051 void binary_write(const char* outname) {
   1052 }
   1053 
   1054 void listing_write(const char* listfn, const char* srcfn) {
   1055 }