x86_64-codegen.c (78185B)
1 #define SIZE_T_INVALID 0xfffffffffffffffful 2 3 typedef enum { 4 x86_64_NOP, 5 x86_64_MOV, 6 x86_64_XCHG, 7 x86_64_PUSH, 8 x86_64_JMP, 9 x86_64_JZ, 10 x86_64_JNZ, 11 x86_64_TEST, 12 x86_64_CMP, 13 x86_64_SETL, 14 x86_64_INC, 15 x86_64_ADD, 16 x86_64_XOR, 17 x86_64_RET, 18 x86_64_CALL, 19 x86_64_SYSCALL, 20 21 x86_64_PSEUDO_RET, 22 x86_64_PSEUDO_CALL, 23 x86_64_PSEUDO_SYSCALL, 24 x86_64_PSEUDO_PHI, 25 } x86_64_Opcode; 26 27 typedef enum { 28 x86_64_NO_OPERAND, 29 x86_64_I, 30 x86_64_R, 31 x86_64_M, 32 x86_64_RI, 33 x86_64_RR, 34 x86_64_RM, 35 x86_64_MR, 36 x86_64_MI, 37 x86_64_RMI, 38 } x86_64_Operand_encoding; 39 40 typedef enum { 41 x86_64_RAND_NONE, 42 x86_64_RAND_REGISTER, 43 x86_64_RAND_MEMORY, 44 x86_64_RAND_IMMEDIATE, 45 x86_64_RAND_SYMBOL, 46 } x86_64_Operand_kind; 47 48 typedef struct { 49 int8_t physical; 50 size_t temp_id; 51 } x86_64_Register; 52 53 typedef enum { 54 x86_64_IMM_LITERAL, 55 x86_64_IMM_CODE_LABEL, 56 x86_64_IMM_DATA_LABEL, 57 x86_64_IMM_NAMED_DATA, 58 } x86_64_Immediate_kind; 59 60 typedef struct { 61 x86_64_Immediate_kind kind; 62 union { 63 long int i64; 64 size_t label_id; 65 Sv name; 66 }; 67 } x86_64_Immediate; 68 69 typedef enum { 70 x86_64_MEM_D, 71 x86_64_MEM_B, 72 x86_64_MEM_BS, 73 x86_64_MEM_BD, 74 x86_64_MEM_SD, 75 x86_64_MEM_BSD, 76 } x86_64_Memory_encoding; 77 78 typedef struct { 79 x86_64_Memory_encoding encoding; 80 char reg2_scale; 81 char offset_bit_width; 82 x86_64_Immediate offset; 83 x86_64_Register base, index; 84 } x86_64_Memory; 85 86 char * 87 x86_64_immediate_to_cstr(x86_64_Immediate imm) 88 { 89 char *leak_buf = malloc(32); 90 if (imm.kind == x86_64_IMM_CODE_LABEL) { 91 snprintf(leak_buf, 32, ".%zu", imm.label_id); 92 } else if (imm.kind == x86_64_IMM_DATA_LABEL) { 93 snprintf(leak_buf, 32, "@%zu", imm.label_id); 94 } else if (imm.kind == x86_64_IMM_LITERAL) { 95 snprintf(leak_buf, 32, "%li", imm.i64); 96 } else { 97 unreachable("immediate kind"); 98 } 99 return leak_buf; 100 } 101 102 typedef struct { 103 char bit_width; 104 x86_64_Operand_kind kind; 105 union { 106 x86_64_Register reg; 107 x86_64_Memory mem; 108 x86_64_Immediate imm; 109 Sv symbol; 110 }; 111 } x86_64_Operand; 112 113 typedef struct { 114 x86_64_Operand *items; 115 size_t count; 116 size_t capacity; 117 } x86_64_Operand_list; 118 119 typedef struct { 120 struct { 121 size_t temp_id; 122 size_t label_id; 123 } *items; 124 size_t count; 125 size_t capacity; 126 } x86_64_Phi_list; 127 128 const char *x86_64_registers_8[16] = { 129 "al", "cl", "dl", "bl", "spl", "bpl", "sil", "dil", 130 "r8b", "r9b", "r10b", "r11b", "r12b", "r13b", "r14b", "r15b", 131 }; 132 133 const char *x86_64_registers_16[16] = { 134 "ax", "cx", "dx", "bx", "sp", "bp", "si", "di", 135 "r8w", "r9w", "r10w", "r11w", "r12w", "r13w", "r14w", "r15w", 136 }; 137 138 const char *x86_64_registers_32[16] = { 139 "eax", "ecx", "edx", "ebx", "esp", "ebp", "esi", "edi", 140 "r8d", "r9d", "r10d", "r11d", "r12d", "r13d", "r14d", "r15d", 141 }; 142 143 const char *x86_64_registers_64[16] = { 144 "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi", 145 "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", 146 }; 147 148 const char *x86_64_registers_err[16] = { 149 "err_ax", "err_cx", "err_dx", "err_bx", "err_sp", "err_bp", "err_si", "err_di", 150 "err_8", "err_9", "err_10", "err_11", "err_12", "err_13", "err_14", "err_15", 151 }; 152 153 #define x86_64_REGISTERS_COUNT (sizeof(x86_64_registers_64) / sizeof(*x86_64_registers_64)) 154 155 int8_t x86_64_registers_ccall[6] = { 156 7, 6, 2, 1, 8, 9, 157 }; 158 159 int8_t x86_64_registers_syscall[6] = { 160 7, 6, 2, 10, 8, 9, 161 }; 162 163 bool x86_64_registers_caller_save[16] = { 164 true, true, true, false, false, false, true, true, 165 true, true, true, true, false, false, false, false 166 }; 167 168 int 169 x86_64_bit_width_of_type(Ir_type type) 170 { 171 switch (type) { 172 case TYPE_I8: 173 return 8; 174 case TYPE_I16: 175 return 16; 176 case TYPE_I32: 177 return 32; 178 case TYPE_PTR: 179 case TYPE_I64: 180 return 64; 181 case TYPE_F32: 182 case TYPE_F64: 183 todo("float"); 184 case TYPE_VOID: 185 unreachable("type void width"); 186 case TYPE_UNKNOWN: 187 return 0; 188 unreachable("type unknown width"); 189 default: 190 unreachable("type"); 191 } 192 } 193 194 const char * 195 x86_64_operand_to_cstr(x86_64_Operand rand) 196 { 197 int len; 198 char *leak_buf = malloc(32); 199 const char **reg_names; 200 if (rand.bit_width == 8) { 201 reg_names = x86_64_registers_8; 202 } else if (rand.bit_width == 16) { 203 reg_names = x86_64_registers_16; 204 } else if (rand.bit_width == 32) { 205 reg_names = x86_64_registers_32; 206 } else if (rand.bit_width == 64) { 207 reg_names = x86_64_registers_64; 208 } else { 209 reg_names = x86_64_registers_err; 210 } 211 switch(rand.kind) { 212 case x86_64_RAND_NONE: 213 free(leak_buf); 214 return "(none)"; 215 case x86_64_RAND_REGISTER: 216 if (rand.reg.physical == -1) { 217 snprintf(leak_buf, 32, "r_%zu", rand.reg.temp_id); 218 } else { 219 free(leak_buf); 220 return reg_names[rand.reg.physical]; 221 } 222 break; 223 case x86_64_RAND_MEMORY: 224 switch (rand.mem.encoding) { 225 case x86_64_MEM_D: 226 assert(rand.mem.offset.kind == x86_64_IMM_NAMED_DATA); 227 free(leak_buf); 228 len = rand.mem.offset.name.count + 5; 229 leak_buf = malloc(len); 230 len = snprintf(leak_buf, len, "[%.*s]", (int) rand.mem.offset.name.count, rand.mem.offset.name.items); 231 break; 232 case x86_64_MEM_B: 233 todo_p("MEM_B"); 234 case x86_64_MEM_BS: 235 todo_p("MEM_BS"); 236 case x86_64_MEM_BD: 237 assert(rand.mem.base.physical != -1); 238 assert(rand.mem.offset.kind == x86_64_IMM_LITERAL); 239 if (rand.mem.offset.i64 >= 0) { 240 len = snprintf(leak_buf, 32, "[%s+%li]", x86_64_registers_64[rand.mem.base.physical], rand.mem.offset.i64); 241 } else { 242 len = snprintf(leak_buf, 32, "[%s-%li]", x86_64_registers_64[rand.mem.base.physical], -rand.mem.offset.i64); 243 } 244 assert(len < 32); 245 break; 246 case x86_64_MEM_SD: 247 todo_p("MEM_SD"); 248 case x86_64_MEM_BSD: 249 todo_p("MEM_BSD"); 250 default: 251 unreachable("memory encoding"); 252 } 253 break; 254 case x86_64_RAND_IMMEDIATE: 255 free(leak_buf); 256 return x86_64_immediate_to_cstr(rand.imm); 257 case x86_64_RAND_SYMBOL: 258 free(leak_buf); 259 return sv_to_cstr(rand.symbol); 260 default: 261 unreachable("operand kind"); 262 } 263 return leak_buf; 264 } 265 266 typedef struct { 267 x86_64_Opcode opcode; 268 x86_64_Operand_encoding encoding; 269 x86_64_Operand rand1; 270 union { 271 struct { 272 x86_64_Operand rand2; 273 x86_64_Operand rand3; 274 }; 275 struct { 276 x86_64_Operand ret; 277 x86_64_Operand_list call_args; 278 }; 279 x86_64_Phi_list phi_list; 280 }; 281 } x86_64_Instruction; 282 283 typedef struct { 284 x86_64_Instruction *items; 285 size_t count; 286 size_t capacity; 287 } x86_64_Instruction_list; 288 289 typedef enum { 290 x86_64_LIVE_NOT_STARTED = 0, 291 x86_64_LIVE_STARTED, 292 x86_64_LIVE_COMPLETED, 293 } x86_64_Liveness_status; 294 295 typedef struct { 296 int start; 297 int end; 298 size_t temp_id; 299 /* size_t physical; */ 300 /* size_t spill_offset; */ 301 } x86_64_Liveness_entry; 302 303 typedef struct { 304 x86_64_Liveness_entry *items; 305 size_t count; 306 size_t capacity; 307 } x86_64_Liveness_list; 308 309 size_t 310 x86_64_get_liveness_entry(x86_64_Liveness_list *list, size_t temp_id) 311 { 312 for (size_t i = 0; i < list->count; i++) { 313 if (list->items[i].temp_id == temp_id) { 314 return i; 315 } 316 } 317 return SIZE_T_INVALID; 318 } 319 320 typedef struct { 321 x86_64_Instruction_list instructions; 322 x86_64_Liveness_list live; 323 x86_64_Liveness_status live_status; 324 struct { 325 size_t *items; 326 size_t count; 327 size_t capacity; 328 } parents; 329 struct { 330 size_t *items; 331 size_t count; 332 size_t capacity; 333 } children; 334 } x86_64_Basic_block; 335 336 typedef struct { 337 x86_64_Basic_block *items; 338 size_t count; 339 size_t capacity; 340 } x86_64_Basic_block_list; 341 342 typedef struct { 343 Sv name; 344 size_t temporary_count; 345 int *mappings; 346 x86_64_Basic_block_list blocks; 347 } x86_64_Function; 348 349 typedef struct { 350 x86_64_Function *items; 351 size_t count; 352 size_t capacity; 353 } x86_64_Function_list; 354 355 typedef struct { 356 bool null_terminate; 357 bool read_only; 358 void *ptr; 359 size_t length; 360 size_t alignment; 361 Sv name; 362 } x86_64_Data; 363 364 typedef struct { 365 x86_64_Data *items; 366 size_t count; 367 size_t capacity; 368 } x86_64_Data_list; 369 370 size_t 371 x86_64_add_cstr_from_sv(x86_64_Data_list *data_list, Sv sv) 372 { 373 Sb sb = {0}; 374 sb_append_and_unescape_sv(&sb, sv); 375 da_append(&sb, '\0'); 376 da_append(data_list, ((x86_64_Data) { 377 .read_only = true, 378 .ptr = (void *) sb.data, 379 .alignment = 1, 380 .length = sb.count, 381 })); 382 return data_list->count - 1; 383 } 384 385 bool 386 x86_64_add_static_data(x86_64_Data_list *data_list, Ir_static_data data, bool read_only) 387 { 388 assert(data.default_value.kind == ARG_INT_LITERAL); 389 size_t i; 390 void *ptr = malloc(8); 391 x86_64_Data x86_64_data = { .name = { .data = data.name.data + 1, .count = data.name.count - 1 }, .ptr = ptr, .read_only = read_only }; 392 for (i = 0; i < data_list->count; i++) { 393 if (sv_equal(x86_64_data.name, data_list->items[i].name)) { 394 fprintf(stderr, "Error: symbol `%.*s` already defined\n", (int) x86_64_data.name.count, x86_64_data.name.items); 395 return false; 396 } 397 } 398 switch (data.type) { 399 case TYPE_I8: 400 x86_64_data.alignment = 1; 401 x86_64_data.length = 1; 402 *(int8_t *) ptr = data.default_value.i64; 403 break; 404 case TYPE_I16: 405 x86_64_data.alignment = 2; 406 x86_64_data.length = 2; 407 *(int16_t *) ptr = data.default_value.i64; 408 break; 409 case TYPE_I32: 410 x86_64_data.alignment = 4; 411 x86_64_data.length = 4; 412 *(int32_t *) ptr = data.default_value.i64; 413 break; 414 case TYPE_PTR: 415 case TYPE_I64: 416 x86_64_data.alignment = 8; 417 x86_64_data.length = 8; 418 *(int64_t *) ptr = data.default_value.i64; 419 break; 420 case TYPE_F32: 421 todo("f32"); 422 case TYPE_F64: 423 todo("f64"); 424 case TYPE_VOID: 425 fprintf(stderr, "Error: void type not allowed for static data\n"); 426 return false; 427 case TYPE_UNKNOWN: 428 unreachable("unknown data type"); 429 default: 430 unreachable("data type"); 431 } 432 if (!read_only && !data.default_value.i64) { 433 free(ptr); 434 x86_64_data.ptr = NULL; 435 } 436 da_append(data_list, x86_64_data); 437 return true; 438 } 439 440 typedef struct { 441 x86_64_Function_list functions; 442 x86_64_Data_list static_data; 443 Ir_extern_list externs; 444 } x86_64_Program; 445 446 void 447 x86_64_emit_program_header(x86_64_Program prog, Sb *sb) 448 { 449 (void) prog; 450 sb_printf(sb, "BITS 64\n"); 451 sb_printf(sb, "DEFAULT REL\n"); 452 sb_printf(sb, "SECTION .text\n"); 453 } 454 455 void 456 x86_64_emit_program_footer(x86_64_Program prog, Sb *sb) 457 { 458 (void) prog; 459 (void) sb; 460 } 461 462 void 463 x86_64_emit_data_header(x86_64_Program prog, Sb *sb) 464 { 465 (void) prog; 466 sb_printf(sb, "\n; Static data storage ;\n"); 467 } 468 469 void 470 x86_64_emit_data_footer(x86_64_Program prog, Sb *sb) 471 { 472 (void) prog; 473 (void) sb; 474 } 475 476 bool 477 x86_64_emit_instruction(x86_64_Instruction ins, Sb *sb) 478 { 479 size_t i; 480 switch (ins.opcode) { 481 case x86_64_NOP: 482 break; 483 case x86_64_MOV: 484 switch (ins.encoding) { 485 case x86_64_RI: 486 case x86_64_RR: 487 case x86_64_RM: 488 case x86_64_MR: 489 case x86_64_MI: 490 sb_printf(sb, " mov %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); 491 break; 492 493 case x86_64_NO_OPERAND: 494 case x86_64_R: 495 case x86_64_M: 496 case x86_64_I: 497 case x86_64_RMI: 498 unreachable("invalid encoding"); 499 default: 500 unreachable("encoding"); 501 } 502 break; 503 case x86_64_XCHG: 504 switch (ins.encoding) { 505 case x86_64_RR: 506 case x86_64_RM: 507 case x86_64_MR: 508 sb_printf(sb, " xchg %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); 509 break; 510 511 case x86_64_MI: 512 case x86_64_RI: 513 case x86_64_NO_OPERAND: 514 case x86_64_R: 515 case x86_64_M: 516 case x86_64_I: 517 case x86_64_RMI: 518 unreachable("invalid encoding"); 519 default: 520 unreachable("encoding"); 521 } 522 break; 523 case x86_64_PUSH: 524 todo("push"); 525 case x86_64_JMP: 526 switch (ins.encoding) { 527 case x86_64_I: 528 sb_printf(sb, " jmp %s\n", x86_64_operand_to_cstr(ins.rand1)); 529 break; 530 case x86_64_NO_OPERAND: 531 case x86_64_RI: 532 case x86_64_RR: 533 case x86_64_RM: 534 case x86_64_MR: 535 case x86_64_MI: 536 case x86_64_R: 537 case x86_64_M: 538 case x86_64_RMI: 539 unreachable("invalid encoding"); 540 default: 541 unreachable("encoding"); 542 } 543 break; 544 case x86_64_JZ: 545 sb_printf(sb, " jz %s\n", x86_64_operand_to_cstr(ins.rand1)); 546 break; 547 case x86_64_JNZ: 548 sb_printf(sb, " jnz %s\n", x86_64_operand_to_cstr(ins.rand1)); 549 break; 550 case x86_64_TEST: 551 sb_printf(sb, " test %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); 552 break; 553 case x86_64_CMP: 554 sb_printf(sb, " cmp %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); 555 break; 556 case x86_64_SETL: 557 sb_printf(sb, " setl %s\n", x86_64_operand_to_cstr(ins.rand1)); 558 break; 559 case x86_64_INC: 560 sb_printf(sb, " inc %s\n", x86_64_operand_to_cstr(ins.rand1)); 561 break; 562 case x86_64_ADD: 563 sb_printf(sb, " add %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); 564 break; 565 case x86_64_XOR: 566 sb_printf(sb, " xor %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); 567 break; 568 case x86_64_RET: 569 sb_printf(sb, " jmp .ret\n"); 570 break; 571 case x86_64_CALL: 572 sb_printf(sb, " call %.*s\n", (int) ins.rand1.symbol.count, ins.rand1.symbol.data); 573 break; 574 case x86_64_SYSCALL: 575 sb_printf(sb, " syscall\n"); 576 break; 577 case x86_64_PSEUDO_RET: 578 sb_printf(sb, " ret %s\n", x86_64_operand_to_cstr(ins.ret)); 579 break; 580 case x86_64_PSEUDO_CALL: 581 assert(ins.rand1.kind == x86_64_RAND_SYMBOL); 582 sb_printf(sb, " call %.*s (", (int) ins.rand1.symbol.count, ins.rand1.symbol.data); 583 for (i = 0; i < ins.call_args.count; i++) { 584 if (i) { 585 sb_printf(sb, ", "); 586 } 587 sb_printf(sb, "%s", x86_64_operand_to_cstr(ins.call_args.items[i])); 588 } 589 sb_printf(sb, ") -> %s\n", x86_64_operand_to_cstr(ins.ret)); 590 break; 591 case x86_64_PSEUDO_SYSCALL: 592 assert(ins.rand1.kind == x86_64_RAND_IMMEDIATE || ins.rand1.kind == x86_64_RAND_REGISTER); 593 sb_printf(sb, " syscall %s (", x86_64_operand_to_cstr(ins.rand1)); 594 for (i = 0; i < ins.call_args.count; i++) { 595 if (i) { 596 sb_printf(sb, ", "); 597 } 598 sb_printf(sb, "%s", x86_64_operand_to_cstr(ins.call_args.items[i])); 599 } 600 sb_printf(sb, ") -> %s\n", x86_64_operand_to_cstr(ins.ret)); 601 break; 602 603 case x86_64_PSEUDO_PHI: 604 todo("emit phi"); 605 default: 606 unreachable("x86_64_opcode"); 607 } 608 return true; 609 } 610 bool 611 x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_list *data_list) 612 { 613 switch (ir.kind) { 614 case IR_LOAD: 615 switch (ir.load.loc.kind) { 616 case ARG_INT_LITERAL: 617 todo("load-int"); 618 case ARG_TEMP_STORAGE: 619 todo("load-temp"); 620 case ARG_ADDRESS: 621 todo("load-address"); 622 case ARG_STATIC_VARIABLE: 623 da_append(list, ((x86_64_Instruction) { 624 .opcode = x86_64_MOV, 625 .encoding = x86_64_RM, 626 .rand1 = { 627 .bit_width = 32, 628 .kind = x86_64_RAND_REGISTER, 629 .reg = { 630 .physical = -1, 631 .temp_id = ir.result.temp_id, 632 }, 633 }, 634 .rand2 = { 635 .bit_width = 32, 636 .kind = x86_64_RAND_MEMORY, 637 .mem = { 638 .encoding = x86_64_MEM_D, 639 .offset = { 640 .kind = x86_64_IMM_NAMED_DATA, 641 .name = ir.load.loc.name, 642 }, 643 }, 644 }, 645 })); 646 break; 647 case ARG_CSTRING_LITERAL: 648 unreachable("load-cstring"); 649 case ARG_NONE: 650 unreachable("load-none"); 651 case ARG_REGISTER: 652 unreachable("assign-register"); 653 default: 654 unreachable("assign"); 655 } 656 break; 657 case IR_STORE: 658 todo("store"); 659 break; 660 case IR_ASSIGN: 661 switch (ir.assign.kind) { 662 case ARG_NONE: 663 unreachable("assign-none"); 664 case ARG_INT_LITERAL: 665 /* sb_printf(sb, " mov tmp_%zu, %li\n", ir.assign.i64); */ 666 da_append(list, ((x86_64_Instruction) { 667 .opcode = x86_64_MOV, 668 .encoding = x86_64_RI, 669 .rand1 = { 670 .bit_width = 32, 671 .kind = x86_64_RAND_REGISTER, 672 .reg = { 673 .physical = -1, 674 .temp_id = ir.result.temp_id, 675 }, 676 }, 677 .rand2 = { 678 .bit_width = 32, 679 .kind = x86_64_RAND_IMMEDIATE, 680 .imm = { 681 .kind = x86_64_IMM_LITERAL, 682 .i64 = (unsigned int) ir.assign.i64, 683 }, 684 }, 685 })); 686 break; 687 case ARG_CSTRING_LITERAL: 688 da_append(list, ((x86_64_Instruction) { 689 .opcode = x86_64_MOV, 690 .encoding = x86_64_RI, 691 .rand1 = { 692 .bit_width = 64, 693 .kind = x86_64_RAND_REGISTER, 694 .reg = { 695 .physical = -1, 696 .temp_id = ir.result.temp_id, 697 }, 698 }, 699 .rand2 = { 700 .bit_width = 64, 701 .kind = x86_64_RAND_IMMEDIATE, 702 .imm = { 703 .kind = x86_64_IMM_DATA_LABEL, 704 .label_id = x86_64_add_cstr_from_sv(data_list, ir.assign.sv), 705 }, 706 }, 707 })); 708 break; 709 case ARG_TEMP_STORAGE: 710 da_append(list, ((x86_64_Instruction) { 711 .opcode = x86_64_MOV, 712 .encoding = x86_64_RR, 713 .rand1 = { 714 .bit_width = 32, 715 .kind = x86_64_RAND_REGISTER, 716 .reg = { 717 .physical = -1, 718 .temp_id = ir.result.temp_id, 719 }, 720 }, 721 .rand2 = { 722 .bit_width = 32, 723 .kind = x86_64_RAND_REGISTER, 724 .reg = { 725 .physical = -1, 726 .temp_id = ir.assign.temp_id, 727 }, 728 }, 729 })); 730 break; 731 case ARG_ADDRESS: 732 todo("assign-address"); 733 case ARG_STATIC_VARIABLE: 734 todo("assign-static-variable"); 735 case ARG_REGISTER: 736 unreachable("assign-register"); 737 default: 738 unreachable("assign"); 739 } 740 /* return false; */ 741 break; 742 case IR_BINOP: 743 switch (ir.binop.op) { 744 case OP_ADD: 745 /* if (ir.binop.left.kind == ARG_TEMP_STORAGE && ir.binop.right.kind == ARG_INT_LITERAL) { */ 746 if (ir.binop.op_type != TYPE_I32) { 747 todo("add types"); 748 } 749 /* sb_printf(sb, " cmp tmp_%zu, %li\n", ir.binop.left.temp_id, ir.binop.right.i64); */ 750 if (ir.binop.left.kind == ARG_TEMP_STORAGE) { 751 da_append(list, ((x86_64_Instruction) { 752 .opcode = x86_64_MOV, 753 .encoding = x86_64_RR, 754 .rand1 = { 755 .bit_width = 32, 756 .kind = x86_64_RAND_REGISTER, 757 .reg = { 758 .physical = -1, 759 .temp_id = ir.result.temp_id, 760 }, 761 }, 762 .rand2 = { 763 .bit_width = 32, 764 .kind = x86_64_RAND_REGISTER, 765 .reg = { 766 .physical = -1, 767 .temp_id = ir.binop.left.temp_id, 768 }, 769 }, 770 })); 771 } else { 772 todo("+ left"); 773 } 774 if (ir.binop.right.kind == ARG_TEMP_STORAGE) { 775 da_append(list, ((x86_64_Instruction) { 776 .opcode = x86_64_ADD, 777 .encoding = x86_64_RR, 778 .rand1 = { 779 .bit_width = 32, 780 .kind = x86_64_RAND_REGISTER, 781 .reg = { 782 .physical = -1, 783 .temp_id = ir.result.temp_id, 784 }, 785 }, 786 .rand2 = { 787 .bit_width = 32, 788 .kind = x86_64_RAND_REGISTER, 789 .reg = { 790 .physical = -1, 791 .temp_id = ir.binop.right.temp_id, 792 }, 793 }, 794 })); 795 } else if (ir.binop.right.kind == ARG_INT_LITERAL) { 796 da_append(list, ((x86_64_Instruction) { 797 .opcode = x86_64_ADD, 798 .encoding = x86_64_RI, 799 .rand1 = { 800 .bit_width = 32, 801 .kind = x86_64_RAND_REGISTER, 802 .reg = { 803 .physical = -1, 804 .temp_id = ir.result.temp_id, 805 }, 806 }, 807 .rand2 = { 808 .bit_width = 32, 809 .kind = x86_64_RAND_IMMEDIATE, 810 .imm = { 811 .kind = x86_64_IMM_LITERAL, 812 .i64 = ir.binop.right.i64, 813 }, 814 }, 815 })); 816 } else { 817 todo("binop +"); 818 } 819 break; 820 case OP_SUB: 821 todo("binop -"); 822 case OP_MUL: 823 todo("binop *"); 824 case OP_DIV: 825 todo("binop /"); 826 case OP_LT: 827 if (ir.binop.left.kind == ARG_TEMP_STORAGE && ir.binop.right.kind == ARG_INT_LITERAL) { 828 if (ir.binop.op_type != TYPE_I32) { 829 todo("lt types"); 830 } 831 /* sb_printf(sb, " cmp tmp_%zu, %li\n", ir.binop.left.temp_id, ir.binop.right.i64); */ 832 da_append(list, ((x86_64_Instruction) { 833 .opcode = x86_64_CMP, 834 .encoding = x86_64_RI, 835 .rand1 = { 836 .bit_width = 32, 837 .kind = x86_64_RAND_REGISTER, 838 .reg = { 839 .physical = -1, 840 .temp_id = ir.binop.left.temp_id, 841 }, 842 }, 843 .rand2 = { 844 .bit_width = 32, 845 .kind = x86_64_RAND_IMMEDIATE, 846 .imm = { 847 .kind = x86_64_IMM_LITERAL, 848 .i64 = ir.binop.right.i64, 849 }, 850 }, 851 })); 852 } else { 853 todo("binop <"); 854 } 855 /* sb_printf(sb, " setl tmp_%zu\n", ir.result.temp_id); */ 856 da_append(list, ((x86_64_Instruction) { 857 .opcode = x86_64_SETL, 858 .encoding = x86_64_R, 859 .rand1 = { 860 .bit_width = 8, 861 .kind = x86_64_RAND_REGISTER, 862 .reg = { 863 .physical = -1, 864 .temp_id = ir.result.temp_id, 865 }, 866 }, 867 })); 868 break; 869 case OP_GT: 870 todo("binop >"); 871 case OP_EQ: 872 todo("binop =="); 873 case OP_LEQ: 874 todo("binop <="); 875 case OP_GEQ: 876 todo("binop >="); 877 default: 878 unreachable("binop"); 879 } 880 break; 881 case IR_CALL: 882 if (ir.call.args.count > 6) { 883 todo("call > 6 args"); 884 } 885 da_append(list, ((x86_64_Instruction) { 886 .opcode = x86_64_PSEUDO_CALL, 887 .encoding = x86_64_I, 888 .rand1 = { 889 .kind = x86_64_RAND_SYMBOL, 890 .symbol = ir.call.name, 891 }, 892 .ret = { 893 .kind = x86_64_RAND_REGISTER, 894 .bit_width = 32, 895 .reg = { 896 .physical = -1, 897 .temp_id = ir.result.temp_id, 898 }, 899 }, 900 })); 901 for (size_t i = 0; i < ir.call.args.count; i++) { 902 x86_64_Operand arg = {0}; 903 switch (ir.call.args.items[i].kind) { 904 case ARG_INT_LITERAL: 905 arg.kind = x86_64_RAND_IMMEDIATE; 906 arg.imm = (x86_64_Immediate) { 907 .kind = x86_64_IMM_LITERAL, 908 .i64 = ir.call.args.items[i].i64, 909 }; 910 break; 911 case ARG_CSTRING_LITERAL: 912 arg.kind = x86_64_RAND_IMMEDIATE; 913 arg.bit_width = x86_64_bit_width_of_type(ir.call.args.items[i].type); 914 arg.imm = (x86_64_Immediate) { 915 .kind = x86_64_IMM_DATA_LABEL, 916 .label_id = x86_64_add_cstr_from_sv(data_list, ir.call.args.items[i].sv), 917 }; 918 break; 919 case ARG_TEMP_STORAGE: 920 arg.kind = x86_64_RAND_REGISTER; 921 arg.bit_width = x86_64_bit_width_of_type(ir.call.args.items[i].type); 922 arg.reg = (x86_64_Register) { 923 .physical = -1, 924 .temp_id = ir.call.args.items[i].temp_id, 925 }; 926 break; 927 case ARG_STATIC_VARIABLE: 928 todo("static-variable operand"); 929 case ARG_ADDRESS: 930 case ARG_REGISTER: 931 case ARG_NONE: 932 default: 933 unreachable("args operand"); 934 } 935 da_append(&list->items[list->count - 1].call_args, arg); 936 } 937 break; 938 case IR_SYSCALL: 939 if (ir.syscall.args.count > 6) { 940 todo("syscall > 6 args"); 941 } 942 x86_64_Operand_encoding syscall_encoding; 943 x86_64_Operand syscall_rand; 944 switch (ir.syscall.syscall.kind) { 945 case ARG_INT_LITERAL: 946 syscall_encoding = x86_64_I; 947 syscall_rand = (x86_64_Operand) { 948 .kind = x86_64_RAND_IMMEDIATE, 949 .imm = { 950 .kind = x86_64_IMM_LITERAL, 951 .i64 = ir.syscall.syscall.i64, 952 }, 953 }; 954 break; 955 case ARG_TEMP_STORAGE: 956 syscall_encoding = x86_64_R; 957 syscall_rand = (x86_64_Operand) { 958 .kind = x86_64_RAND_REGISTER, 959 .bit_width = 64, 960 .reg = { 961 .physical = -1, 962 .temp_id = ir.syscall.syscall.temp_id, 963 }, 964 }; 965 break; 966 case ARG_STATIC_VARIABLE: 967 todo("syscall->static-variable"); 968 case ARG_CSTRING_LITERAL: 969 unreachable("syscall->cstring"); 970 case ARG_ADDRESS: 971 unreachable("syscall->address"); 972 case ARG_REGISTER: 973 unreachable("syscall->register"); 974 case ARG_NONE: 975 unreachable("syscall->none"); 976 default: 977 unreachable("syscall operand kind"); 978 } 979 da_append(list, ((x86_64_Instruction) { 980 .opcode = x86_64_PSEUDO_SYSCALL, 981 .encoding = syscall_encoding, 982 .rand1 = syscall_rand, 983 .ret = { 984 .kind = x86_64_RAND_REGISTER, 985 .bit_width = 64, 986 .reg = { 987 .physical = -1, 988 .temp_id = ir.result.temp_id, 989 }, 990 }, 991 })); 992 for (size_t i = 0; i < ir.syscall.args.count; i++) { 993 x86_64_Operand arg = {0}; 994 switch (ir.syscall.args.items[i].kind) { 995 case ARG_INT_LITERAL: 996 arg.kind = x86_64_RAND_IMMEDIATE; 997 arg.imm = (x86_64_Immediate) { 998 .kind = x86_64_IMM_LITERAL, 999 .i64 = ir.syscall.args.items[i].i64, 1000 }; 1001 break; 1002 case ARG_CSTRING_LITERAL: 1003 arg.kind = x86_64_RAND_IMMEDIATE; 1004 arg.bit_width = x86_64_bit_width_of_type(ir.syscall.args.items[i].type); 1005 arg.imm = (x86_64_Immediate) { 1006 .kind = x86_64_IMM_DATA_LABEL, 1007 .label_id = x86_64_add_cstr_from_sv(data_list, ir.syscall.args.items[i].sv), 1008 }; 1009 break; 1010 case ARG_TEMP_STORAGE: 1011 arg.kind = x86_64_RAND_REGISTER; 1012 arg.bit_width = x86_64_bit_width_of_type(ir.syscall.args.items[i].type); 1013 arg.reg = (x86_64_Register) { 1014 .physical = -1, 1015 .temp_id = ir.syscall.args.items[i].temp_id, 1016 }; 1017 break; 1018 case ARG_STATIC_VARIABLE: 1019 todo("static-variable operand"); 1020 case ARG_ADDRESS: 1021 case ARG_REGISTER: 1022 case ARG_NONE: 1023 default: 1024 unreachable("args operand"); 1025 } 1026 da_append(&list->items[list->count - 1].call_args, arg); 1027 } 1028 break; 1029 case IR_RETURN: 1030 if (ir.ret.kind == ARG_TEMP_STORAGE) { 1031 /* 1032 da_append(list, ((x86_64_Instruction) { 1033 .opcode = x86_64_MOV, 1034 .encoding = x86_64_RR, 1035 .rand1 = { 1036 .bit_width = 32, 1037 .kind = x86_64_RAND_REGISTER, 1038 .reg = { 1039 .physical = 0, 1040 .temp_id = SIZE_T_INVALID, 1041 }, 1042 }, 1043 .rand2 = { 1044 .bit_width = 32, 1045 .kind = x86_64_RAND_REGISTER, 1046 .reg = { 1047 .physical = -1, 1048 .temp_id = ir.ret.temp_id, 1049 }, 1050 }, 1051 })); 1052 */ 1053 da_append(list, ((x86_64_Instruction) { 1054 .opcode = x86_64_PSEUDO_RET, 1055 .encoding = x86_64_R, 1056 .rand1 = { 1057 .bit_width = 32, 1058 .kind = x86_64_RAND_REGISTER, 1059 .reg = { 1060 .physical = -1, 1061 .temp_id = ir.ret.temp_id, 1062 }, 1063 }, 1064 })); 1065 } else { 1066 todo("return"); 1067 } 1068 break; 1069 /* case IR_LABEL: */ 1070 case IR_JUMP: 1071 assert(ir.jump.label.resolved); 1072 da_append(list, ((x86_64_Instruction) { 1073 .opcode = x86_64_JMP, 1074 .encoding = x86_64_I, 1075 .rand1 = { 1076 .bit_width = 64, 1077 .kind = x86_64_RAND_IMMEDIATE, 1078 .imm = { 1079 .kind = x86_64_IMM_CODE_LABEL, 1080 .label_id = ir.jump.label.id, 1081 }, 1082 }, 1083 })); 1084 break; 1085 case IR_BRANCH: 1086 assert(ir.branch.true_label.resolved); 1087 assert(ir.branch.false_label.resolved); 1088 if (ir.branch.cond.kind == ARG_TEMP_STORAGE) { 1089 da_append(list, ((x86_64_Instruction) { 1090 .opcode = x86_64_TEST, 1091 .encoding = x86_64_RR, 1092 .rand1 = { 1093 .bit_width = 8, 1094 .kind = x86_64_RAND_REGISTER, 1095 .reg = { 1096 .physical = -1, 1097 .temp_id = ir.branch.cond.temp_id, 1098 }, 1099 }, 1100 .rand2 = { 1101 .bit_width = 8, 1102 .kind = x86_64_RAND_REGISTER, 1103 .reg = { 1104 .physical = -1, 1105 .temp_id = ir.branch.cond.temp_id, 1106 }, 1107 }, 1108 })); 1109 da_append(list, ((x86_64_Instruction) { 1110 .opcode = x86_64_JZ, 1111 .encoding = x86_64_I, 1112 .rand1 = { 1113 .bit_width = 64, 1114 .kind = x86_64_RAND_IMMEDIATE, 1115 .imm = { 1116 .kind = x86_64_IMM_CODE_LABEL, 1117 .label_id = ir.branch.false_label.id, 1118 }, 1119 }, 1120 })); 1121 da_append(list, ((x86_64_Instruction) { 1122 .opcode = x86_64_JMP, 1123 .encoding = x86_64_I, 1124 .rand1 = { 1125 .bit_width = 64, 1126 .kind = x86_64_RAND_IMMEDIATE, 1127 .imm = { 1128 .kind = x86_64_IMM_CODE_LABEL, 1129 .label_id = ir.branch.true_label.id, 1130 }, 1131 }, 1132 })); 1133 /* sb_printf(sb, " mov rax, tmp_%zu\n", ir.branch.cond.temp_id); */ 1134 /* sb_printf(sb, " test rax, rax\n"); */ 1135 /* sb_printf(sb, " jz .%zu\n", ir.branch.true_label_id); */ 1136 /* sb_printf(sb, " jmp .%zu\n", ir.branch.false_label_id); */ 1137 } else { 1138 todo("branch"); 1139 } 1140 break; 1141 case IR_PHI: 1142 unreachable("phi nodes should've been purged"); 1143 default: 1144 unreachable("ir_kind"); 1145 } 1146 return true; 1147 } 1148 1149 bool 1150 x86_64_compile_basic_block(Ir_block block, x86_64_Basic_block *out_block, x86_64_Data_list *data_list) 1151 { 1152 bool success = true; 1153 size_t i; 1154 for (i = 0; i < block.count; i++) { 1155 if (!x86_64_compile_instruction(block.items[i], &out_block->instructions, data_list)) { 1156 success = false; 1157 break; 1158 } 1159 } 1160 return success; 1161 } 1162 1163 bool 1164 x86_64_emit_basic_block(x86_64_Basic_block block, Sb *sb) 1165 { 1166 bool success = true; 1167 size_t i; 1168 for (i = 0; i < block.instructions.count; i++) { 1169 if (!x86_64_emit_instruction(block.instructions.items[i], sb)) { 1170 success = false; 1171 break; 1172 } 1173 } 1174 return success; 1175 } 1176 1177 bool 1178 x86_64_compile_function(Ir_function func, x86_64_Function *out_func, x86_64_Data_list *data_list) 1179 { 1180 bool success = true; 1181 size_t i; 1182 int bit_width; 1183 x86_64_Basic_block block = {0}; 1184 for (i = 0; i < func.argument_types.count; i++) { 1185 bit_width = x86_64_bit_width_of_type(func.argument_types.items[i]); 1186 da_append(&block.instructions, ((x86_64_Instruction) { 1187 .opcode = x86_64_MOV, 1188 .encoding = x86_64_RR, 1189 .rand1 = { 1190 .kind = x86_64_RAND_REGISTER, 1191 .bit_width = bit_width, 1192 .reg = { 1193 .physical = -1, 1194 .temp_id = i, 1195 }, 1196 }, 1197 .rand2 = { 1198 .kind = x86_64_RAND_REGISTER, 1199 .bit_width = bit_width, 1200 .reg = { 1201 .physical = x86_64_registers_ccall[i], 1202 .temp_id = SIZE_T_INVALID, 1203 }, 1204 }, 1205 })); 1206 } 1207 for (i = 0; i < func.body.count; i++) { 1208 if (!x86_64_compile_basic_block(func.body.items[i], &block, data_list)) { 1209 da_append(&out_func->blocks, block); 1210 success = false; 1211 break; 1212 } 1213 da_append(&out_func->blocks, block); 1214 block = (x86_64_Basic_block) {0}; 1215 } 1216 return success; 1217 } 1218 1219 bool 1220 x86_64_emit_function(x86_64_Function fn, Sb *sb) 1221 { 1222 bool success = true; 1223 size_t i, j; 1224 struct { 1225 int *items; 1226 size_t count; 1227 size_t capacity; 1228 } saved = {0}; 1229 sb_printf(sb, "\nGLOBAL %.*s\n", (int) fn.name.count, fn.name.items); 1230 sb_printf(sb, "%.*s:\n", (int) fn.name.count, fn.name.items); 1231 sb_printf(sb, " push rbp\n"); 1232 for (i = 0; i < 16; i++) { 1233 if (x86_64_registers_caller_save[i]) { 1234 continue; 1235 } 1236 for (j = 0; j < fn.temporary_count; j++) { 1237 if (fn.mappings[j] == (int) i) { 1238 sb_printf(sb, " push %s\n", x86_64_registers_64[i]); 1239 da_append(&saved, i); 1240 break; 1241 } 1242 } 1243 } 1244 sb_printf(sb, " mov rbp, rsp\n"); 1245 sb_printf(sb, " sub rsp, %zu\n", ((fn.temporary_count * 8) + 0xF) & ~0xF); 1246 1247 Sb body = {0}; 1248 for (i = 0; i < fn.blocks.count; i++) { 1249 sb_printf(&body, " .%zu:\n", i); 1250 if (!x86_64_emit_basic_block(fn.blocks.items[i], &body)) { 1251 success = false; 1252 break; 1253 } 1254 } 1255 sb_append_sv(sb, sv_from_sb(body)); 1256 sb_printf(sb, " .ret:\n"); 1257 sb_printf(sb, " mov rsp, rbp\n"); 1258 for (i = saved.count; i; i--) { 1259 sb_printf(sb, " pop %s\n", x86_64_registers_64[saved.items[i - 1]]); 1260 } 1261 sb_printf(sb, " pop rbp\n"); 1262 sb_printf(sb, " ret\n"); 1263 1264 free(body.items); 1265 if (saved.capacity) { 1266 free(saved.items); 1267 } 1268 1269 return success; 1270 } 1271 1272 bool 1273 x86_64_emit_data(x86_64_Data data, Sb *sb, size_t label_id) 1274 { 1275 size_t i; 1276 int prefix_len; 1277 if (data.alignment > 1) { 1278 sb_printf(sb, "ALIGN %zu\n", data.alignment); 1279 } 1280 if (data.ptr) { 1281 if (data.read_only) { 1282 sb_printf(sb, "SECTION .rodata\n"); 1283 } else { 1284 sb_printf(sb, "SECTION .data\n"); 1285 } 1286 if (data.name.count) { 1287 prefix_len = sb_printf(sb, "%.*s: db ", (int) data.name.count, data.name.items); 1288 } else { 1289 prefix_len = sb_printf(sb, "@%zu: db ", label_id); 1290 } 1291 for (i = 0; i < data.length; i++) { 1292 if (i) { 1293 da_append(sb, ','); 1294 if (!(i & 0x0f)) { 1295 sb_printf(sb, "\n%*s", prefix_len, ""); 1296 } 1297 } 1298 sb_printf(sb, "0x%02x", ((char *) data.ptr)[i]); 1299 } 1300 if (data.null_terminate) { 1301 sb_printf(sb, ",0x00"); 1302 } 1303 da_append(sb, '\n'); 1304 } else { 1305 sb_printf(sb, "SECTION .bss\n"); 1306 if (data.name.count) { 1307 sb_printf(sb, "%.*s: resb %zu\n", (int) data.name.count, data.name.items, data.length); 1308 } else { 1309 sb_printf(sb, "@%zu: resb %zu\n", label_id, data.length); 1310 } 1311 } 1312 return true; 1313 } 1314 1315 bool 1316 x86_64_emit_extern(Ir_extern ext, Sb *sb) 1317 { 1318 sb_printf(sb, "EXTERN %.*s\n", (int) ext.symbol.count, ext.symbol.data); 1319 return true; 1320 } 1321 1322 bool 1323 x86_64_emit_program(x86_64_Program prog, Sb *sb) 1324 { 1325 bool success = true; 1326 size_t i; 1327 x86_64_emit_program_header(prog, sb); 1328 for (i = 0; i < prog.externs.count; i++) { 1329 if (!x86_64_emit_extern(prog.externs.items[i], sb)) { 1330 success = false; 1331 break; 1332 } 1333 } 1334 for (i = 0; i < prog.functions.count; i++) { 1335 if (!x86_64_emit_function(prog.functions.items[i], sb)) { 1336 success = false; 1337 break; 1338 } 1339 } 1340 x86_64_emit_program_footer(prog, sb); 1341 x86_64_emit_data_header(prog, sb); 1342 for (i = 0; i < prog.static_data.count; i++) { 1343 if (!x86_64_emit_data(prog.static_data.items[i], sb, i)) { 1344 success = false; 1345 break; 1346 } 1347 } 1348 x86_64_emit_data_footer(prog, sb); 1349 return success; 1350 } 1351 1352 bool 1353 x86_64_calculate_internal_liveness(x86_64_Basic_block *block) 1354 { 1355 size_t i, j, entry_index; 1356 x86_64_Instruction ins; 1357 x86_64_Liveness_entry *entry; 1358 1359 size_t block_icount = block->instructions.count; 1360 for (i = block_icount - 1; i != SIZE_T_INVALID; i--) { 1361 ins = block->instructions.items[i]; 1362 switch (ins.opcode) { 1363 case x86_64_NOP: 1364 continue; 1365 case x86_64_CALL: 1366 unreachable("live call"); 1367 case x86_64_SYSCALL: 1368 unreachable("live syscall"); 1369 case x86_64_PSEUDO_PHI: 1370 todo("live phi"); 1371 case x86_64_MOV: 1372 case x86_64_XCHG: 1373 case x86_64_SETL: 1374 switch (ins.encoding) { 1375 case x86_64_R: 1376 case x86_64_RI: 1377 if (ins.rand1.reg.physical != -1) { 1378 /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ 1379 } else { 1380 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { 1381 da_append(&block->live, ((x86_64_Liveness_entry) { 1382 .start = i, 1383 .end = i, 1384 .temp_id = ins.rand1.reg.temp_id, 1385 })); 1386 } else { 1387 assert(block->live.items[entry_index].start == -1); 1388 block->live.items[entry_index].start = i; 1389 } 1390 } 1391 break; 1392 case x86_64_M: 1393 todo("modifying M"); 1394 1395 case x86_64_RR: 1396 if (ins.rand1.reg.physical != -1) { 1397 /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ 1398 } else { 1399 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { 1400 da_append(&block->live, ((x86_64_Liveness_entry) { 1401 .start = i, 1402 .end = i, 1403 .temp_id = ins.rand1.reg.temp_id, 1404 })); 1405 } else { 1406 assert(block->live.items[entry_index].start == -1); 1407 block->live.items[entry_index].start = i; 1408 } 1409 } 1410 if (ins.rand2.reg.physical != -1) { 1411 /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ 1412 } else { 1413 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand2.reg.temp_id)) == SIZE_T_INVALID) { 1414 da_append(&block->live, ((x86_64_Liveness_entry) { 1415 .start = -1, 1416 .end = i, 1417 .temp_id = ins.rand2.reg.temp_id, 1418 })); 1419 } else { 1420 entry = &block->live.items[entry_index]; 1421 if (entry->start == entry->end) { 1422 entry->end = i; 1423 } 1424 if (entry->start >= 0) { 1425 entry->start = -(entry->start + 2); 1426 } 1427 /* DO NOTHING? */ 1428 /* fprintf(stderr, "%%%zu already defined as (%i -> %i)\n", ins.rand2.reg.temp_id, block->live.items[entry_index].start, block->live.items[entry_index].end); */ 1429 } 1430 } 1431 break; 1432 case x86_64_RM: 1433 if (ins.rand1.reg.physical != -1) { 1434 /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ 1435 } else { 1436 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { 1437 da_append(&block->live, ((x86_64_Liveness_entry) { 1438 .start = i, 1439 .end = i, 1440 .temp_id = ins.rand1.reg.temp_id, 1441 })); 1442 } else { 1443 assert(block->live.items[entry_index].start == -1); 1444 block->live.items[entry_index].start = i; 1445 } 1446 } 1447 switch (ins.rand2.mem.encoding) { 1448 case x86_64_MEM_D: 1449 break; 1450 /* 1451 switch (ins.rand2.mem.offset.kind) { 1452 case x86_64_IMM_CODE_LABEL: 1453 case x86_64_IMM_LITERAL: 1454 case x86_64_IMM_DATA_LABEL: 1455 case x86_64_IMM_NAMED_DATA: 1456 default: 1457 unreachabel("mem->imm kind"); 1458 } 1459 break; 1460 */ 1461 case x86_64_MEM_B: 1462 todo("mem B"); 1463 case x86_64_MEM_BD: 1464 todo("mem BD"); 1465 case x86_64_MEM_BS: 1466 todo("mem BS"); 1467 case x86_64_MEM_SD: 1468 todo("mem SD"); 1469 case x86_64_MEM_BSD: 1470 todo("mem BSD"); 1471 default: 1472 unreachable("mem encoding"); 1473 } 1474 break; 1475 todo("modifying RM"); 1476 case x86_64_MR: 1477 todo("modifying MR"); 1478 case x86_64_MI: 1479 todo("modifying RMI"); 1480 case x86_64_RMI: 1481 todo("modifying RMI"); 1482 1483 case x86_64_I: 1484 break; 1485 case x86_64_NO_OPERAND: 1486 default: 1487 unreachable("encoding"); 1488 } 1489 break; 1490 1491 /* Modifies their first operand, but not a valid start, since it also reads from it. Must be preceeded by mov or similar */ 1492 case x86_64_INC: 1493 case x86_64_ADD: 1494 case x86_64_XOR: 1495 /* Doesn't modify their operands */ 1496 case x86_64_PUSH: 1497 case x86_64_TEST: 1498 case x86_64_CMP: 1499 case x86_64_PSEUDO_RET: 1500 switch (ins.encoding) { 1501 case x86_64_RI: 1502 case x86_64_R: 1503 if (ins.rand1.reg.physical != -1) { 1504 /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ 1505 break; 1506 } 1507 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { 1508 da_append(&block->live, ((x86_64_Liveness_entry) { 1509 .start = -1, 1510 .end = i, 1511 .temp_id = ins.rand1.reg.temp_id, 1512 })); 1513 } else { 1514 /* DO NOTHING? */ 1515 } 1516 break; 1517 case x86_64_M: 1518 todo("non-modifying M"); 1519 case x86_64_RR: 1520 if (ins.rand1.reg.physical != -1) { 1521 /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ 1522 } else { 1523 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { 1524 da_append(&block->live, ((x86_64_Liveness_entry) { 1525 .start = -1, 1526 .end = i, 1527 .temp_id = ins.rand1.reg.temp_id, 1528 })); 1529 } else { 1530 /* DO NOTHING? */ 1531 } 1532 } 1533 if (ins.rand2.reg.physical != -1) { 1534 /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ 1535 } else { 1536 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand2.reg.temp_id)) == SIZE_T_INVALID) { 1537 da_append(&block->live, ((x86_64_Liveness_entry) { 1538 .start = -1, 1539 .end = i, 1540 .temp_id = ins.rand2.reg.temp_id, 1541 })); 1542 } else { 1543 /* DO NOTHING? */ 1544 } 1545 } 1546 break; 1547 case x86_64_RM: 1548 todo("non-modifying RM"); 1549 case x86_64_MR: 1550 todo("non-modifying MR"); 1551 case x86_64_MI: 1552 todo("non-modifying MI"); 1553 case x86_64_RMI: 1554 todo("non-modifying RMM"); 1555 1556 case x86_64_I: 1557 break; 1558 case x86_64_NO_OPERAND: 1559 default: 1560 unreachable("encoding"); 1561 } 1562 break; 1563 1564 case x86_64_PSEUDO_CALL: 1565 if (ins.encoding == x86_64_R) { 1566 todo("indirect call"); 1567 } 1568 if (ins.ret.kind == x86_64_RAND_REGISTER) { 1569 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.ret.reg.temp_id)) == SIZE_T_INVALID) { 1570 da_append(&block->live, ((x86_64_Liveness_entry) { 1571 .start = i, 1572 .end = i, 1573 .temp_id = ins.ret.reg.temp_id, 1574 })); 1575 } else { 1576 assert(block->live.items[entry_index].start == -1); 1577 block->live.items[entry_index].start = i; 1578 } 1579 } 1580 if (ins.call_args.count) { 1581 for (j = 0; j < ins.call_args.count; j++) { 1582 x86_64_Operand arg = ins.call_args.items[j]; 1583 if (arg.kind != x86_64_RAND_REGISTER) { 1584 continue; 1585 } 1586 if (arg.reg.physical != -1) { 1587 /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ 1588 break; 1589 } 1590 if ((entry_index = x86_64_get_liveness_entry(&block->live, arg.reg.temp_id)) == SIZE_T_INVALID) { 1591 da_append(&block->live, ((x86_64_Liveness_entry) { 1592 .start = -1, 1593 .end = i, 1594 .temp_id = arg.reg.temp_id, 1595 })); 1596 } else { 1597 /* DO NOTHING? */ 1598 } 1599 } 1600 } 1601 break; 1602 case x86_64_PSEUDO_SYSCALL: 1603 if (ins.encoding == x86_64_R && ins.rand1.reg.physical == -1) { 1604 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { 1605 da_append(&block->live, ((x86_64_Liveness_entry) { 1606 .start = -1, 1607 .end = i, 1608 .temp_id = ins.rand1.reg.temp_id, 1609 })); 1610 } else { 1611 /* DO NOTHING? */ 1612 } 1613 } 1614 if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.ret.reg.temp_id)) == SIZE_T_INVALID) { 1615 da_append(&block->live, ((x86_64_Liveness_entry) { 1616 .start = i, 1617 .end = i, 1618 .temp_id = ins.ret.reg.temp_id, 1619 })); 1620 } else { 1621 assert(block->live.items[entry_index].start == -1); 1622 block->live.items[entry_index].start = i; 1623 } 1624 if (ins.call_args.count) { 1625 for (j = 0; j < ins.call_args.count; j++) { 1626 x86_64_Operand arg = ins.call_args.items[j]; 1627 if (arg.kind != x86_64_RAND_REGISTER) { 1628 continue; 1629 } 1630 if (arg.reg.physical != -1) { 1631 break; 1632 } 1633 if ((entry_index = x86_64_get_liveness_entry(&block->live, arg.reg.temp_id)) == SIZE_T_INVALID) { 1634 da_append(&block->live, ((x86_64_Liveness_entry) { 1635 .start = -1, 1636 .end = i, 1637 .temp_id = arg.reg.temp_id, 1638 })); 1639 } else { 1640 /* DO NOTHING? */ 1641 } 1642 } 1643 } 1644 break; 1645 1646 /* Can only use static labels */ 1647 case x86_64_JZ: 1648 case x86_64_JNZ: 1649 case x86_64_JMP: 1650 assert(ins.encoding == x86_64_I); 1651 break; 1652 1653 /* No operands */ 1654 case x86_64_RET: 1655 assert(ins.encoding == x86_64_NO_OPERAND); 1656 break; 1657 default: 1658 unreachable("instruction"); 1659 } 1660 } 1661 return true; 1662 } 1663 1664 bool 1665 x86_64_calculate_external_liveness(x86_64_Basic_block *block, x86_64_Basic_block_list *block_list) 1666 { 1667 if (block->live_status == x86_64_LIVE_COMPLETED) { 1668 return true; 1669 } 1670 block->live_status = x86_64_LIVE_STARTED; 1671 size_t i, j, entry_index; 1672 x86_64_Basic_block *child_block; 1673 x86_64_Liveness_entry *entry, *child_entry; 1674 for (i = 0; i < block->children.count; i++) { 1675 if (block->children.items[i] == block_list->count) { 1676 continue; 1677 } 1678 child_block = &block_list->items[block->children.items[i]]; 1679 if (child_block->live_status == x86_64_LIVE_NOT_STARTED) { 1680 if (!x86_64_calculate_external_liveness(child_block, block_list)) { 1681 return false; 1682 } 1683 } 1684 for (j = 0; j < child_block->live.count; j++) { 1685 child_entry = &child_block->live.items[j]; 1686 if (child_entry->start >= 0) { 1687 continue; 1688 } 1689 if ((entry_index = x86_64_get_liveness_entry(&block->live, child_entry->temp_id)) == SIZE_T_INVALID) { 1690 da_append(&block->live, ((x86_64_Liveness_entry) { 1691 .start = -1, 1692 .end = -1, 1693 .temp_id = child_entry->temp_id, 1694 })); 1695 } else { 1696 entry = &block->live.items[entry_index]; 1697 if (entry->end >= 0) { 1698 entry->end = -(entry->end + 2); 1699 } 1700 } 1701 } 1702 } 1703 return true; 1704 } 1705 1706 bool 1707 x86_64_calculate_liveness(x86_64_Function *fn) 1708 { 1709 size_t i, j, max_temp = SIZE_T_INVALID; 1710 x86_64_Basic_block *block; 1711 /* fprintf(stderr, "--- Internal Lifetimes ---\n"); */ 1712 for (i = 0; i < fn->blocks.count; i++) { 1713 block = &fn->blocks.items[i]; 1714 if (!x86_64_calculate_internal_liveness(block)) { 1715 return false; 1716 } 1717 /* fprintf(stderr, ".%zu {\n", i); */ 1718 for (j = 0; j < block->live.count; j++) { 1719 /* fprintf(stderr, " %%%zu: %i -> %i\n", block->live.items[j].temp_id, block->live.items[j].start, block->live.items[j].end); */ 1720 if (max_temp < block->live.items[j].temp_id || max_temp == SIZE_T_INVALID) { 1721 max_temp = block->live.items[j].temp_id; 1722 } 1723 } 1724 /* fprintf(stderr, "}\n"); */ 1725 } 1726 assert(max_temp != SIZE_T_INVALID); 1727 fn->temporary_count = max_temp + 1; 1728 1729 fprintf(stderr, "\n--- Total Lifetimes ---\n"); 1730 for (i = 0; i < fn->blocks.count; i++) { 1731 block = &fn->blocks.items[i]; 1732 if (!x86_64_calculate_external_liveness(block, &fn->blocks)) { 1733 return false; 1734 } 1735 block->live_status = x86_64_LIVE_COMPLETED; 1736 1737 fprintf(stderr, ".%zu {\n", i); 1738 for (j = 0; j < block->live.count; j++) { 1739 fprintf(stderr, " %%%zu: %i -> %i\n", block->live.items[j].temp_id, block->live.items[j].start, block->live.items[j].end); 1740 } 1741 fprintf(stderr, "}\n"); 1742 } 1743 return true; 1744 } 1745 1746 bool 1747 x86_64_calculate_call_graph(x86_64_Function *fn) 1748 { 1749 size_t i, j, k, child; 1750 x86_64_Basic_block *block; 1751 x86_64_Instruction *ins; 1752 for (i = 0; i < fn->blocks.count; i++) { 1753 block = &fn->blocks.items[i]; 1754 for (j = 0; j < block->instructions.count; j++) { 1755 ins = &block->instructions.items[j]; 1756 if (ins->opcode == x86_64_RET || ins->opcode == x86_64_PSEUDO_RET) { 1757 da_append(&block->children, fn->blocks.count); 1758 } else if (ins->opcode == x86_64_JMP || 1759 ins->opcode == x86_64_JZ || 1760 ins->opcode == x86_64_JNZ) { 1761 assert(ins->encoding == x86_64_I); 1762 assert(ins->rand1.imm.kind == x86_64_IMM_CODE_LABEL); 1763 child = ins->rand1.imm.label_id; 1764 for (k = 0; k < block->children.count; k++) { 1765 if (block->children.items[k] == child) { 1766 break; 1767 } 1768 } 1769 if (k == block->children.count) { 1770 da_append(&block->children, child); 1771 da_append(&fn->blocks.items[child].parents, i); 1772 } 1773 } 1774 } 1775 } 1776 return true; 1777 } 1778 1779 void 1780 x86_64_emit_call_graph_dotfmt(x86_64_Function fn) 1781 { 1782 size_t i, j; 1783 FILE *f = fopen("build/callgraph.gv", "w"); 1784 if (!f) { 1785 perror("x86_64_emit_call_graph_dotfmt"); 1786 return; 1787 } 1788 fprintf(f, "digraph {\n"); 1789 fprintf(f, " .%zu [name=ret]\n", fn.blocks.count); 1790 for (i = 0; i < fn.blocks.count; i++) { 1791 for (j = 0; j < fn.blocks.items[i].children.count; j++) { 1792 fprintf(f, " .%zu -> .%zu\n", i, fn.blocks.items[i].children.items[j]); 1793 } 1794 } 1795 fprintf(f, "}\n"); 1796 } 1797 1798 bool 1799 x86_64_is_pseudo_opcode(x86_64_Opcode opcode) { 1800 switch (opcode) { 1801 case x86_64_NOP: 1802 case x86_64_MOV: 1803 case x86_64_XCHG: 1804 case x86_64_PUSH: 1805 case x86_64_JMP: 1806 case x86_64_JZ: 1807 case x86_64_JNZ: 1808 case x86_64_TEST: 1809 case x86_64_CMP: 1810 case x86_64_SETL: 1811 case x86_64_INC: 1812 case x86_64_ADD: 1813 case x86_64_XOR: 1814 case x86_64_RET: 1815 case x86_64_CALL: 1816 case x86_64_SYSCALL: 1817 return false; 1818 1819 case x86_64_PSEUDO_RET: 1820 case x86_64_PSEUDO_CALL: 1821 case x86_64_PSEUDO_SYSCALL: 1822 case x86_64_PSEUDO_PHI: 1823 return true; 1824 default: 1825 unreachable("opcode"); 1826 } 1827 } 1828 1829 bool 1830 x86_64_expand_pseudo_instructions(x86_64_Function *fn) 1831 { 1832 size_t i, j, k, l; 1833 x86_64_Basic_block *block; 1834 x86_64_Instruction_list new_instruction_list = {0}; 1835 x86_64_Instruction *ins; 1836 x86_64_Operand *arg; 1837 x86_64_Operand_list saved = {0}; 1838 for (i = 0; i < fn->blocks.count; i++) { 1839 block = &fn->blocks.items[i]; 1840 for (j = 0; j< block->instructions.count; j++) { 1841 ins = &block->instructions.items[j]; 1842 /* if (ins->opcode != x86_64_PSEUDO_CALL) { */ 1843 if (!x86_64_is_pseudo_opcode(ins->opcode)) { 1844 da_append(&new_instruction_list, *ins); 1845 continue; 1846 } 1847 if (ins->opcode == x86_64_PSEUDO_PHI) { 1848 todo("expand pseudo-phi"); 1849 } 1850 if (ins->opcode == x86_64_PSEUDO_RET) { 1851 x86_64_Operand_encoding ret_encoding; 1852 switch (ins->encoding) { 1853 case x86_64_R: 1854 ret_encoding = x86_64_RR; 1855 break; 1856 case x86_64_I: 1857 todo("ret I"); 1858 case x86_64_M: 1859 todo("ret m"); 1860 case x86_64_NO_OPERAND: 1861 case x86_64_RI: 1862 case x86_64_RR: 1863 case x86_64_RM: 1864 case x86_64_MR: 1865 case x86_64_MI: 1866 case x86_64_RMI: 1867 default: 1868 unreachable("ret encoding"); 1869 } 1870 da_append(&new_instruction_list, ((x86_64_Instruction) { 1871 .opcode = x86_64_MOV, 1872 .encoding = ret_encoding, 1873 .rand1 = { 1874 .kind = x86_64_RAND_REGISTER, 1875 .bit_width = ins->rand1.bit_width, 1876 .reg = { 1877 .physical = 0, 1878 .temp_id = SIZE_T_INVALID, 1879 }, 1880 }, 1881 .rand2 = ins->rand1, 1882 })); 1883 da_append(&new_instruction_list, ((x86_64_Instruction) { 1884 .opcode = x86_64_RET, 1885 .encoding = x86_64_NO_OPERAND, 1886 })); 1887 continue; 1888 } 1889 saved.count = 0; 1890 for (k = 0; k < block->live.count; k++) { 1891 x86_64_Liveness_entry *live = &block->live.items[k]; 1892 if (live->start >= (long) j || (live->end >= 0 && live->end <= (long) j)) { 1893 continue; 1894 } 1895 if (!x86_64_registers_caller_save[fn->mappings[live->temp_id]]) { 1896 continue; 1897 } 1898 x86_64_Operand arg = { 1899 .kind = x86_64_RAND_REGISTER, 1900 .bit_width = 64, 1901 .reg = { 1902 .physical = fn->mappings[live->temp_id], 1903 .temp_id = live->temp_id, 1904 }, 1905 }; 1906 da_append(&saved, arg); 1907 da_append(&new_instruction_list, ((x86_64_Instruction) { 1908 .opcode = x86_64_MOV, 1909 .encoding = x86_64_MR, 1910 .rand1 = { 1911 .kind = x86_64_RAND_MEMORY, 1912 .mem = { 1913 .encoding = x86_64_MEM_BD, 1914 .base = { 1915 .physical = 5, 1916 .temp_id = SIZE_T_INVALID, 1917 }, 1918 .offset_bit_width = 8, 1919 .offset = { 1920 .kind = x86_64_IMM_LITERAL, 1921 .i64 = -(saved.count << 3), 1922 }, 1923 }, 1924 }, 1925 .rand2 = arg, 1926 })); 1927 } 1928 struct { 1929 int8_t *items; 1930 size_t count; 1931 size_t capacity; 1932 } current_reg = {0}; 1933 da_expand(¤t_reg, ins->call_args.count); 1934 for (k = 0; k < ins->call_args.count; k++) { 1935 if (ins->call_args.items[k].kind == x86_64_RAND_REGISTER) { 1936 current_reg.items[k] = ins->call_args.items[k].reg.physical; 1937 } else { 1938 current_reg.items[k] = -1; 1939 } 1940 } 1941 int8_t *reg_array; 1942 if (ins->opcode == x86_64_PSEUDO_CALL) { 1943 reg_array = x86_64_registers_ccall; 1944 } else if (ins->opcode == x86_64_PSEUDO_SYSCALL) { 1945 reg_array = x86_64_registers_syscall; 1946 } else { 1947 unreachable("opcode"); 1948 } 1949 for (k = 0; k < ins->call_args.count; k++) { 1950 int8_t swap = -1; 1951 arg = &ins->call_args.items[k]; 1952 for (l = k + 1; l < ins->call_args.count; l++) { 1953 if (reg_array[k] == current_reg.items[l]) { 1954 fprintf(stderr, "Error: Overwriting later operand %s\n", x86_64_registers_64[reg_array[k]]); 1955 if (current_reg.items[k] != -1) { 1956 swap = current_reg.items[k]; 1957 /* current_reg.items[k] = current_reg.items[l]; */ 1958 current_reg.items[l] = swap; 1959 } else { 1960 todo("handle non-register cases"); 1961 } 1962 } 1963 } 1964 if (swap == -1) { 1965 switch (arg->kind) { 1966 case x86_64_RAND_NONE: 1967 break; 1968 case x86_64_RAND_REGISTER: 1969 assert(arg->reg.physical != -1); 1970 da_append(&new_instruction_list, ((x86_64_Instruction) { 1971 .opcode = x86_64_MOV, 1972 .encoding = x86_64_RR, 1973 .rand1 = { 1974 .kind = x86_64_RAND_REGISTER, 1975 .bit_width = arg->bit_width, 1976 .reg = { 1977 .physical = reg_array[k], 1978 .temp_id = SIZE_T_INVALID, 1979 }, 1980 }, 1981 .rand2 = { 1982 .kind = x86_64_RAND_REGISTER, 1983 .bit_width = arg->bit_width, 1984 .reg = { 1985 .physical = current_reg.items[k], 1986 .temp_id = arg->reg.temp_id, 1987 }, 1988 }, 1989 })); 1990 break; 1991 case x86_64_RAND_MEMORY: 1992 todo("memory"); 1993 case x86_64_RAND_IMMEDIATE: 1994 da_append(&new_instruction_list, ((x86_64_Instruction) { 1995 .opcode = x86_64_MOV, 1996 .encoding = x86_64_RI, 1997 .rand1 = { 1998 .kind = x86_64_RAND_REGISTER, 1999 .bit_width = arg->bit_width, 2000 .reg = { 2001 .physical = reg_array[k], 2002 .temp_id = SIZE_T_INVALID, 2003 }, 2004 }, 2005 .rand2 = *arg, 2006 })); 2007 break; 2008 case x86_64_RAND_SYMBOL: 2009 todo("symbol"); 2010 default: 2011 unreachable("operand kind"); 2012 } 2013 } else { 2014 switch (arg->kind) { 2015 case x86_64_RAND_NONE: 2016 break; 2017 case x86_64_RAND_REGISTER: 2018 assert(arg->reg.physical != -1); 2019 break; 2020 case x86_64_RAND_MEMORY: 2021 todo("memory"); 2022 case x86_64_RAND_IMMEDIATE: 2023 da_append(&new_instruction_list, ((x86_64_Instruction) { 2024 .opcode = x86_64_MOV, 2025 .encoding = x86_64_RI, 2026 .rand1 = { 2027 .kind = x86_64_RAND_REGISTER, 2028 .bit_width = arg->bit_width, 2029 .reg = { 2030 .physical = swap, 2031 .temp_id = SIZE_T_INVALID, 2032 }, 2033 }, 2034 .rand2 = *arg, 2035 })); 2036 break; 2037 case x86_64_RAND_SYMBOL: 2038 todo("symbol"); 2039 default: 2040 unreachable("operand kind"); 2041 } 2042 2043 da_append(&new_instruction_list, ((x86_64_Instruction) { 2044 .opcode = x86_64_XCHG, 2045 .encoding = x86_64_RR, 2046 .rand1 = { 2047 .kind = x86_64_RAND_REGISTER, 2048 .bit_width = 64, 2049 .reg = { 2050 .physical = reg_array[k], 2051 .temp_id = SIZE_T_INVALID, 2052 }, 2053 }, 2054 .rand2 = { 2055 .kind = x86_64_RAND_REGISTER, 2056 .bit_width = 64, 2057 .reg = { 2058 .physical = swap, 2059 .temp_id = SIZE_T_INVALID, 2060 }, 2061 }, 2062 })); 2063 } 2064 } 2065 if (ins->opcode == x86_64_PSEUDO_CALL) { 2066 da_append(&new_instruction_list, ((x86_64_Instruction) { 2067 .opcode = x86_64_MOV, 2068 .encoding = x86_64_RI, 2069 .rand1 = { 2070 .kind = x86_64_RAND_REGISTER, 2071 .bit_width = 64, 2072 .reg = { 2073 .physical = 0, 2074 .temp_id = SIZE_T_INVALID, 2075 }, 2076 }, 2077 .rand2 = { 2078 .kind = x86_64_RAND_IMMEDIATE, 2079 .imm = { 2080 .kind = x86_64_IMM_LITERAL, 2081 .i64 = 0, 2082 }, 2083 }, 2084 })); 2085 da_append(&new_instruction_list, ((x86_64_Instruction) { 2086 .opcode = x86_64_CALL, 2087 .encoding = x86_64_I, 2088 .rand1 = ins->rand1, 2089 })); 2090 } else if (ins->opcode == x86_64_PSEUDO_SYSCALL) { 2091 if (ins->encoding == x86_64_R) { 2092 da_append(&new_instruction_list, ((x86_64_Instruction) { 2093 .opcode = x86_64_MOV, 2094 .encoding = x86_64_RR, 2095 .rand1 = { 2096 .kind = x86_64_RAND_REGISTER, 2097 .bit_width = ins->rand1.bit_width, 2098 .reg = { 2099 .physical = 0, 2100 .temp_id = SIZE_T_INVALID, 2101 }, 2102 }, 2103 .rand2 = ins->rand1, 2104 })); 2105 } 2106 da_append(&new_instruction_list, ((x86_64_Instruction) { 2107 .opcode = x86_64_SYSCALL, 2108 .encoding = x86_64_NO_OPERAND, 2109 })); 2110 } else { 2111 unreachable("opcode"); 2112 } 2113 if (ins->ret.kind == x86_64_RAND_REGISTER) { 2114 da_append(&new_instruction_list, ((x86_64_Instruction) { 2115 .opcode = x86_64_MOV, 2116 .encoding = x86_64_RR, 2117 .rand1 = ins->ret, 2118 .rand2 = { 2119 .kind = x86_64_RAND_REGISTER, 2120 .bit_width = ins->ret.bit_width, 2121 .reg = { 2122 .physical = 0, 2123 .temp_id = SIZE_T_INVALID, 2124 }, 2125 }, 2126 })); 2127 } else if (ins->ret.kind == x86_64_RAND_NONE) { 2128 /* DO NOTHING */ 2129 } else { 2130 unreachable("return value operand"); 2131 } 2132 while (saved.count) { 2133 saved.count--; 2134 da_append(&new_instruction_list, ((x86_64_Instruction) { 2135 .opcode = x86_64_MOV, 2136 .encoding = x86_64_RM, 2137 .rand1 = saved.items[saved.count], 2138 .rand2 = { 2139 .kind = x86_64_RAND_MEMORY, 2140 .mem = { 2141 .encoding = x86_64_MEM_BD, 2142 .base = { 2143 .physical = 5, 2144 .temp_id = SIZE_T_INVALID, 2145 }, 2146 .offset_bit_width = 8, 2147 .offset = { 2148 .kind = x86_64_IMM_LITERAL, 2149 .i64 = -((saved.count+1) << 3), 2150 }, 2151 }, 2152 }, 2153 })); 2154 } 2155 } 2156 free(block->instructions.items); 2157 block->instructions = new_instruction_list; 2158 memset(&new_instruction_list, 0, sizeof(new_instruction_list)); 2159 } 2160 free(saved.items); 2161 return true; 2162 } 2163 2164 typedef struct { 2165 size_t *items; 2166 size_t count; 2167 size_t capacity; 2168 } x86_64_Interference_list; 2169 2170 void 2171 x86_64_emit_temp_interference_graph_dotfmt(x86_64_Interference_list *graph, size_t entries) 2172 { 2173 size_t i, j; 2174 FILE *f = fopen("build/interferencegraph.gv", "w"); 2175 if (!f) { 2176 perror("x86_64_emit_temp_interference_graph_dotfmt"); 2177 return; 2178 } 2179 fprintf(f, "digraph {\n"); 2180 for (i = 0; i < entries; i++) { 2181 for (j = 0; j < graph[i].count; j++) { 2182 fprintf(f, " r_%zu -> r_%zu\n", i, graph[i].items[j]); 2183 } 2184 } 2185 fprintf(f, "}\n"); 2186 } 2187 2188 /* 2189 "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi", 2190 "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", 2191 */ 2192 2193 int x86_64_registers_usable[] = { 2194 0, 1, 2, 6, 7, 8, 9, 3, 10, 11, 12, 13, 14, 15, 2195 }; 2196 2197 int x86_64_registers_usable_rgb[] = { 2198 0xff0000, 0xffff00, 0xff00ff, 0x00ffff, 0x336600, 0x993300, 0xcccc99, 2199 0x66cc00, 0x669999, 0x33cc99, 0x0066cc, 0x9966cc, 0x330066, 0x990066, 2200 }; 2201 2202 size_t x86_64_registers_usable_count = sizeof(x86_64_registers_usable) / sizeof(*x86_64_registers_usable); 2203 2204 void 2205 x86_64_emit_temp_colored_graph_dotfmt(x86_64_Interference_list *graph, int *colors, size_t entries) 2206 { 2207 size_t i, j; 2208 FILE *f = fopen("build/colorgraph.gv", "w"); 2209 if (!f) { 2210 perror("x86_64_emit_temp_colored_graph_dotfmt"); 2211 return; 2212 } 2213 fprintf(f, "graph {\n"); 2214 for (i = 0; i < entries; i++) { 2215 fprintf(f, " r_%zu [fillcolor=\"#%06x\", style=filled];\n", i, x86_64_registers_usable_rgb[colors[i]]); 2216 for (j = 0; j < graph[i].count; j++) { 2217 if (i < graph[i].items[j]) { 2218 fprintf(f, " r_%zu -- r_%zu;\n", i, graph[i].items[j]); 2219 } 2220 } 2221 } 2222 fprintf(f, "}\n"); 2223 } 2224 2225 int 2226 x86_64_neighbours_count_compare(const void *a, const void *b, void *graph) 2227 { 2228 size_t ia = *(size_t *) a; 2229 size_t ib = *(size_t *) b; 2230 x86_64_Interference_list *ga = &((x86_64_Interference_list *) graph)[ia]; 2231 x86_64_Interference_list *gb = &((x86_64_Interference_list *) graph)[ib]; 2232 return gb->count - ga->count; 2233 } 2234 2235 bool 2236 x86_64_assign_registers(x86_64_Function *fn) 2237 { 2238 size_t i, j, k, l; 2239 int s1, s2, e1, e2; 2240 x86_64_Basic_block *block; 2241 x86_64_Liveness_entry *live, *live_cmp; 2242 size_t temp_count = fn->temporary_count; 2243 x86_64_Interference_list *graph = calloc(temp_count, sizeof(*graph)); 2244 int *mappings = malloc(sizeof(*mappings) * temp_count); 2245 for (i = 0; i < temp_count; i++) { 2246 mappings[i] = -1; 2247 } 2248 for (i = 0; i < fn->blocks.count; i++) { 2249 block = &fn->blocks.items[i]; 2250 for (j = 0; j < block->live.count; j++) { 2251 live = &block->live.items[j]; 2252 s1 = live->start; 2253 e1 = live->end; 2254 for (k = 0; k < block->live.count; k++) { 2255 if (j == k) { 2256 continue; 2257 } 2258 live_cmp = &block->live.items[k]; 2259 s2 = live_cmp->start; 2260 e2 = live_cmp->end; 2261 if ( 2262 (s2 < 0 && e2 < 0) || 2263 (s1 < 0 && e1 < 0) || 2264 (s1 < 0 && s2 < 0) || 2265 (e1 < 0 && e2 < 0) || 2266 (s1 >= 0 && s2 >= 0 && e1 >= 0 && e1 > s2 && s1 < s2) || 2267 (s1 >= 0 && s2 >= 0 && e2 >= 0 && e2 > s1 && s2 < s1) || 2268 (s1 >= 0 && e1 >= 0 && e2 >= 0 && e1 > s2 && s1 < e2) 2269 ) { 2270 for (l = 0; l < graph[live->temp_id].count; l++) { 2271 if (graph[live->temp_id].items[l] == live_cmp->temp_id) { 2272 break; 2273 } 2274 } 2275 if (l == graph[live->temp_id].count) { 2276 /* fprintf(stderr, "Overlap in this basic block: {%i, %i} {%i, %i}\n", s1, e1, s2, e2); */ 2277 da_append(&graph[live->temp_id], live_cmp->temp_id); 2278 } 2279 } else { 2280 /* fprintf(stderr, "No overlap in this basic block: {%i, %i} {%i, %i}\n", s1, e1, s2, e2); */ 2281 } 2282 } 2283 } 2284 } 2285 size_t *color_order = calloc(temp_count, sizeof(*color_order)); 2286 for (i = 0; i < temp_count; i++) { 2287 color_order[i] = i; 2288 } 2289 qsort_r(color_order, temp_count, sizeof(*color_order), x86_64_neighbours_count_compare, (void *)graph); 2290 2291 bool possible[x86_64_REGISTERS_COUNT] = {0}; 2292 for (i = 0; i < temp_count; i++) { 2293 k = color_order[i]; 2294 for (j = 0; j < x86_64_registers_usable_count; j++) { 2295 possible[x86_64_registers_usable[j]] = true; 2296 } 2297 for (j = 0; j < graph[k].count; j++) { 2298 if (mappings[graph[k].items[j]] != -1) { 2299 possible[mappings[graph[k].items[j]]] = false; 2300 } 2301 } 2302 for (j = 0; j < x86_64_registers_usable_count; j++) { 2303 if (possible[x86_64_registers_usable[j]]) { 2304 mappings[k] = x86_64_registers_usable[j]; 2305 break; 2306 } 2307 } 2308 if (j == x86_64_registers_usable_count) { 2309 todo("spill"); 2310 } 2311 } 2312 2313 for (i = 0; i < fn->blocks.count; i++) { 2314 block = &fn->blocks.items[i]; 2315 for (j = 0; j < block->instructions.count; j++) { 2316 x86_64_Instruction *ins = &block->instructions.items[j]; 2317 if (ins->opcode == x86_64_PSEUDO_CALL) { 2318 assert(ins->ret.reg.physical == -1); 2319 ins->ret.reg.physical = mappings[ins->ret.reg.temp_id]; 2320 if (ins->rand1.kind == x86_64_RAND_REGISTER) { 2321 assert(ins->rand1.reg.physical == -1); 2322 ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; 2323 } 2324 for (k = 0; k < ins->call_args.count; k++) { 2325 if (ins->call_args.items[k].kind == x86_64_RAND_REGISTER) { 2326 assert(ins->call_args.items[k].reg.physical == -1); 2327 ins->call_args.items[k].reg.physical = mappings[ins->call_args.items[k].reg.temp_id]; 2328 } 2329 } 2330 continue; 2331 } 2332 if (ins->opcode == x86_64_PSEUDO_SYSCALL) { 2333 assert(ins->ret.reg.physical == -1); 2334 ins->ret.reg.physical = mappings[ins->ret.reg.temp_id]; 2335 if (ins->rand1.kind == x86_64_RAND_REGISTER) { 2336 assert(ins->rand1.reg.physical == -1); 2337 ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; 2338 } 2339 for (k = 0; k < ins->call_args.count; k++) { 2340 if (ins->call_args.items[k].kind == x86_64_RAND_REGISTER) { 2341 assert(ins->call_args.items[k].reg.physical == -1); 2342 ins->call_args.items[k].reg.physical = mappings[ins->call_args.items[k].reg.temp_id]; 2343 } 2344 } 2345 continue; 2346 } 2347 if (ins->opcode == x86_64_PSEUDO_PHI) { 2348 todo("reg phi"); 2349 continue; 2350 } 2351 switch (ins->encoding) { 2352 case x86_64_NO_OPERAND: 2353 case x86_64_I: 2354 break; 2355 2356 case x86_64_R: 2357 case x86_64_RI: 2358 assert(ins->rand1.reg.physical == -1); 2359 ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; 2360 break; 2361 2362 case x86_64_RR: 2363 if (ins->rand1.reg.physical != -1) { 2364 Sb sb = {0}; 2365 x86_64_emit_instruction(*ins, &sb); 2366 sb_write(1, sb); 2367 exit(1); 2368 } 2369 ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; 2370 2371 if (ins->rand2.reg.physical == -1) { 2372 ins->rand2.reg.physical = mappings[ins->rand2.reg.temp_id]; 2373 } 2374 break; 2375 2376 case x86_64_M: 2377 todo("assign M"); 2378 case x86_64_RM: 2379 switch (ins->rand2.mem.encoding) { 2380 case x86_64_MEM_D: 2381 break; 2382 case x86_64_MEM_BS: 2383 todo("MEM_BS"); 2384 case x86_64_MEM_B: 2385 case x86_64_MEM_BD: 2386 assert(ins->rand2.mem.base.physical == -1); 2387 ins->rand2.mem.base.physical = mappings[ins->rand2.mem.base.temp_id]; 2388 break; 2389 case x86_64_MEM_SD: 2390 todo("MEM_SD"); 2391 case x86_64_MEM_BSD: 2392 todo("MEM_BSD"); 2393 default: 2394 unreachable("memory encoding"); 2395 } 2396 assert(ins->rand1.reg.physical == -1); 2397 ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; 2398 break; 2399 case x86_64_MR: 2400 switch (ins->rand1.mem.encoding) { 2401 case x86_64_MEM_D: 2402 break; 2403 case x86_64_MEM_BS: 2404 todo("MEM_BS"); 2405 case x86_64_MEM_B: 2406 case x86_64_MEM_BD: 2407 assert(ins->rand1.mem.base.physical == -1); 2408 ins->rand1.mem.base.physical = mappings[ins->rand1.mem.base.temp_id]; 2409 break; 2410 case x86_64_MEM_SD: 2411 todo("MEM_SD"); 2412 case x86_64_MEM_BSD: 2413 todo("MEM_BSD"); 2414 default: 2415 unreachable("memory encoding"); 2416 } 2417 assert(ins->rand2.reg.physical == -1); 2418 ins->rand2.reg.physical = mappings[ins->rand2.reg.temp_id]; 2419 break; 2420 case x86_64_MI: 2421 todo("assign MI"); 2422 case x86_64_RMI: 2423 todo("assign RMI"); 2424 default: 2425 unreachable("ins->encoding"); 2426 } 2427 } 2428 } 2429 x86_64_emit_temp_interference_graph_dotfmt(graph, temp_count); 2430 x86_64_emit_temp_colored_graph_dotfmt(graph, mappings, temp_count); 2431 free(graph); 2432 /* free(mappings); */ 2433 fn->mappings = mappings; 2434 return true; 2435 } 2436 2437 bool 2438 x86_64_simplify_constant_operations(x86_64_Function *fn) 2439 { 2440 size_t i, j; 2441 x86_64_Basic_block *block; 2442 x86_64_Instruction *ins; 2443 for (i = 0; i < fn->blocks.count; i++) { 2444 block = &fn->blocks.items[i]; 2445 for (j = 0; j < block->instructions.count; j++) { 2446 ins = &block->instructions.items[j]; 2447 2448 if (ins->opcode == x86_64_MOV) { 2449 if (ins->encoding == x86_64_RI && ins->rand2.imm.kind == x86_64_IMM_LITERAL) { 2450 if (ins->rand2.imm.i64 == 0) { 2451 ins->opcode = x86_64_XOR; 2452 ins->encoding = x86_64_RR; 2453 ins->rand1.bit_width = 32; 2454 ins->rand2 = ins->rand1; 2455 } else if (ins->rand2.imm.i64 > 0 && ins->rand2.imm.i64 <= UINT32_MAX && ins->rand1.bit_width == 64) { 2456 ins->rand1.bit_width = 32; 2457 } 2458 } 2459 } else if (ins->opcode == x86_64_ADD) { 2460 if (ins->encoding == x86_64_RI && ins->rand2.imm.kind == x86_64_IMM_LITERAL) { 2461 if (ins->rand2.imm.i64 == 1) { 2462 ins->opcode = x86_64_INC; 2463 ins->encoding = x86_64_R; 2464 if (ins->rand1.bit_width != 64) { 2465 ins->rand1.bit_width = 32; 2466 } 2467 } else if (ins->rand2.imm.i64 > 0 && ins->rand2.imm.i64 <= UINT32_MAX && ins->rand1.bit_width == 64) { 2468 ins->rand1.bit_width = 32; 2469 } 2470 } 2471 } 2472 } 2473 } 2474 return true; 2475 } 2476 2477 bool 2478 x86_64_delete_unused_temporaries(x86_64_Function *fn) 2479 { 2480 size_t i, j; 2481 x86_64_Basic_block *block; 2482 x86_64_Instruction *ins; 2483 bool found_unused; 2484 for (;;) { 2485 found_unused = false; 2486 for (i = 0; i < fn->blocks.count; i++) { 2487 block = &fn->blocks.items[i]; 2488 for (j = 0; j < block->live.count; j++) { 2489 /* fprintf(stderr, " %%%zu: %i -> %i\n", block->live.items[j].temp_id, block->live.items[j].start, block->live.items[j].end); */ 2490 if (block->live.items[j].start == block->live.items[j].end && block->live.items[j].start >= 0) { 2491 ins = &block->instructions.items[block->live.items[j].start]; 2492 if (ins->opcode == x86_64_MOV) { 2493 ins->opcode = x86_64_NOP; 2494 found_unused = true; 2495 } else if (ins->opcode == x86_64_PSEUDO_CALL) { 2496 ins->ret.kind = x86_64_RAND_NONE; 2497 } else if (ins->opcode == x86_64_PSEUDO_SYSCALL) { 2498 ins->ret.kind = x86_64_RAND_NONE; 2499 } 2500 } 2501 } 2502 } 2503 if (!found_unused) { 2504 break; 2505 } 2506 for (i = 0; i < fn->blocks.count; i++) { 2507 block = &fn->blocks.items[i]; 2508 block->live_status = x86_64_LIVE_NOT_STARTED; 2509 block->live.count = 0; 2510 } 2511 if (!x86_64_calculate_liveness(fn)) { 2512 return false; 2513 } 2514 } 2515 return true; 2516 } 2517 2518 bool 2519 x86_64_delete_nop(x86_64_Function *fn) 2520 { 2521 bool is_nop; 2522 size_t i, j; 2523 x86_64_Basic_block *block; 2524 x86_64_Instruction *ins; 2525 for (i = 0; i < fn->blocks.count; i++) { 2526 block = &fn->blocks.items[i]; 2527 for (j = 0; j < block->instructions.count; j++) { 2528 is_nop = false; 2529 ins = &block->instructions.items[j]; 2530 2531 if (ins->opcode == x86_64_MOV && ins->encoding == x86_64_RR) { 2532 if (ins->rand1.reg.physical == ins->rand2.reg.physical) { 2533 is_nop = true; 2534 } 2535 } else if (ins->opcode == x86_64_XCHG && ins->encoding == x86_64_RR) { 2536 if (ins->rand1.reg.physical == ins->rand2.reg.physical) { 2537 is_nop = true; 2538 } 2539 } else if(ins->opcode == x86_64_JMP && ins->rand1.imm.label_id == i + 1) { 2540 assert(j == block->instructions.count - 1); 2541 is_nop = true; 2542 } else if(ins->opcode == x86_64_RET && i == fn->blocks.count - 1) { 2543 assert(j == block->instructions.count - 1); 2544 is_nop = true; 2545 } 2546 2547 if (is_nop) { 2548 da_delete_ordered(&block->instructions, j); 2549 j--; 2550 } 2551 } 2552 } 2553 return true; 2554 } 2555 2556 bool 2557 x86_64_compile_program(Ir_program prog, x86_64_Program *out_prog) 2558 { 2559 bool success = true; 2560 size_t i; 2561 x86_64_Function func = {0}; 2562 for (i = 0; i < prog.const_data.count; i++) { 2563 if (!x86_64_add_static_data(&out_prog->static_data, prog.const_data.items[i], true)) { 2564 success = false; 2565 } 2566 } 2567 for (i = 0; i < prog.variable_data.count; i++) { 2568 if (!x86_64_add_static_data(&out_prog->static_data, prog.variable_data.items[i], false)) { 2569 success = false; 2570 } 2571 } 2572 for (i = 0; i < prog.functions.count; i++) { 2573 func = (x86_64_Function) { .name = prog.functions.items[i].name }; 2574 if (!x86_64_compile_function(prog.functions.items[i], &func, &out_prog->static_data)) { 2575 da_append(&out_prog->functions, func); 2576 success = false; 2577 break; 2578 } 2579 if (!x86_64_calculate_call_graph(&func)) { 2580 da_append(&out_prog->functions, func); 2581 success = false; 2582 break; 2583 } 2584 2585 x86_64_emit_call_graph_dotfmt(func); 2586 2587 if (!x86_64_calculate_liveness(&func)) { 2588 da_append(&out_prog->functions, func); 2589 success = false; 2590 break; 2591 } 2592 2593 if (!x86_64_delete_unused_temporaries(&func)) { 2594 da_append(&out_prog->functions, func); 2595 success = false; 2596 break; 2597 } 2598 2599 if (!x86_64_assign_registers(&func)) { 2600 da_append(&out_prog->functions, func); 2601 success = false; 2602 break; 2603 } 2604 2605 if (!x86_64_expand_pseudo_instructions(&func)) { 2606 da_append(&out_prog->functions, func); 2607 success = false; 2608 break; 2609 } 2610 2611 if (!x86_64_simplify_constant_operations(&func)) { 2612 da_append(&out_prog->functions, func); 2613 success = false; 2614 break; 2615 } 2616 2617 if (!x86_64_delete_nop(&func)) { 2618 da_append(&out_prog->functions, func); 2619 success = false; 2620 break; 2621 } 2622 2623 da_append(&out_prog->functions, func); 2624 } 2625 return success; 2626 } 2627 2628 bool 2629 x86_64_compile_and_emit(Ir_program prog, Sb *sb) 2630 { 2631 x86_64_Program x86_64_prog = {0}; 2632 x86_64_prog.externs = prog.externs; 2633 if (!x86_64_compile_program(prog, &x86_64_prog)) { 2634 x86_64_emit_program(x86_64_prog, sb); 2635 return false; 2636 } 2637 return x86_64_emit_program(x86_64_prog, sb); 2638 } 2639 2640 Backend x86_64_backend = { 2641 "x86_64 assembly", 2642 x86_64_compile_and_emit, 2643 };