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 }