backend

Unnamed repository; edit this file 'description' to name the repository.
git clone https://git.deepztream.com/backend
Log | Files | Refs | Submodules

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(&current_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 };