ncc: new intermediate code
[neatcc.git] / x64.c
blob9c30050f1e1ca1415684421a58cc0140ef7cb789
1 /* architecture-dependent code generation for x86_64 */
2 #include <stdlib.h>
3 #include "ncc.h"
5 /* x86-64 registers, without r8-r15 */
6 #define R_RAX 0x00
7 #define R_RCX 0x01
8 #define R_RDX 0x02
9 #define R_RBX 0x03
10 #define R_RSP 0x04
11 #define R_RBP 0x05
12 #define R_RSI 0x06
13 #define R_RDI 0x07
15 #define REG_RET R_RAX
17 /* x86 opcodes */
18 #define I_MOV 0x89
19 #define I_MOVI 0xc7
20 #define I_MOVIR 0xb8
21 #define I_MOVR 0x8b
22 #define I_MOVSXD 0x63
23 #define I_SHX 0xd3
24 #define I_CMP 0x3b
25 #define I_TST 0x85
26 #define I_LEA 0x8d
27 #define I_NOT 0xf7
28 #define I_CALL 0xff
29 #define I_MUL 0xf7
30 #define I_XOR 0x33
31 #define I_CQO 0x99
32 #define I_PUSH 0x50
33 #define I_POP 0x58
35 #define MIN(a, b) ((a) < (b) ? (a) : (b))
36 #define ALIGN(x, a) (((x) + (a) - 1) & ~((a) - 1))
38 int tmpregs[] = {0, 7, 6, 2, 1, 8, 9, 10, 11, 3, 12, 13, 14, 15};
39 int argregs[] = {7, 6, 2, 1, 8, 9};
41 #define OP2(o2, o1) (0x010000 | ((o2) << 8) | (o1))
42 #define O2(op) (((op) >> 8) & 0xff)
43 #define O1(op) ((op) & 0xff)
44 #define MODRM(m, r1, r2) ((m) << 6 | (r1) << 3 | (r2))
45 #define REX(r1, r2) (0x48 | (((r1) & 8) >> 1) | (((r2) & 8) >> 3))
47 static struct mem cs; /* generated code */
49 /* code generation functions */
50 void os(void *s, int n)
52 mem_put(&cs, s, n);
55 static char *ointbuf(long n, int l)
57 static char buf[16];
58 int i;
59 for (i = 0; i < l; i++) {
60 buf[i] = n & 0xff;
61 n >>= 8;
63 return buf;
66 void oi(long n, int l)
68 mem_put(&cs, ointbuf(n, l), l);
71 void oi_at(long pos, long n, int l)
73 mem_cpy(&cs, pos, ointbuf(n, l), l);
76 long opos(void)
78 return mem_len(&cs);
81 static void op_x(int op, int r1, int r2, int bt)
83 int sz = T_SZ(bt);
84 int rex = 0;
85 if (sz == 8)
86 rex |= 8;
87 if (sz == 1)
88 rex |= 0x40;
89 if (r1 & 0x8)
90 rex |= 4;
91 if (r2 & 0x8)
92 rex |= 1;
93 if (sz == 2)
94 oi(0x66, 1);
95 if (rex)
96 oi(rex | 0x40, 1);
97 if (op & 0x10000)
98 oi(O2(op), 1);
99 oi(sz == 1 ? O1(op) & ~0x1 : O1(op), 1);
102 #define op_mr op_rm
104 /* op_*(): r=reg, m=mem, i=imm, s=sym */
105 static void op_rm(int op, int src, int base, int off, int bt)
107 int dis = off == (char) off ? 1 : 4;
108 int mod = dis == 4 ? 2 : 1;
109 if (!off && (base & 7) != R_RBP)
110 mod = 0;
111 op_x(op, src, base, bt);
112 oi(MODRM(mod, src & 0x07, base & 0x07), 1);
113 if ((base & 7) == R_RSP)
114 oi(0x24, 1);
115 if (mod)
116 oi(off, dis);
119 static void op_rr(int op, int src, int dst, int bt)
121 op_x(op, src, dst, bt);
122 oi(MODRM(3, src & 0x07, dst & 0x07), 1);
125 #define movrx_bt(bt) (((bt) == 4) ? 4 : LONGSZ)
127 static int movrx_op(int bt, int mov)
129 int sz = T_SZ(bt);
130 if (sz == 4)
131 return bt & T_MSIGN ? I_MOVSXD : mov;
132 if (sz == 2)
133 return OP2(0x0f, bt & T_MSIGN ? 0xbf : 0xb7);
134 if (sz == 1)
135 return OP2(0x0f, bt & T_MSIGN ? 0xbe : 0xb6);
136 return mov;
139 static void mov_r2r(int rd, int r1, unsigned bt)
141 if (rd != r1 || T_SZ(bt) != LONGSZ)
142 op_rr(movrx_op(bt, I_MOVR), rd, r1, movrx_bt(bt));
145 static void i_push(int reg)
147 op_x(I_PUSH | (reg & 0x7), 0, reg, LONGSZ);
150 void i_mov(int rd, int rn)
152 op_rr(movrx_op(LONGSZ, I_MOVR), rd, rn, movrx_bt(LONGSZ));
155 static void i_add(int op, int rd, int r1, int r2)
157 /* opcode for O_ADD, O_SUB, O_AND, O_OR, O_XOR */
158 static int rx[] = {0003, 0053, 0043, 0013, 0063};
159 op_rr(rx[op & 0x0f], rd, r2, LONGSZ);
162 static void i_add_imm(int op, int rd, int rn, long n)
164 /* opcode for O_ADD, O_SUB, O_AND, O_OR, O_XOR */
165 static int rx[] = {0xc0, 0xe8, 0xe0, 0xc8, 0xf0};
166 unsigned char s[4] = {REX(0, rd), 0x83, rx[op & 0x0f] | (rd & 7), n & 0xff};
167 os((void *) s, 4);
170 static void i_num(int rd, long n)
172 if (!n) {
173 op_rr(I_XOR, rd, rd, 4);
174 return;
176 if (n < 0 && -n <= 0xffffffff) {
177 op_rr(I_MOVI, 0, rd, LONGSZ);
178 oi(n, 4);
179 } else {
180 int len = 8;
181 if (n > 0 && n <= 0xffffffff)
182 len = 4;
183 op_x(I_MOVIR + (rd & 7), 0, rd, len);
184 oi(n, len);
188 static void i_mul(int rd, int r1, int r2)
190 if (r2 != R_RDX)
191 i_num(R_RDX, 0);
192 op_rr(I_MUL, 4, r2, LONGSZ);
195 static void i_div(int op, int rd, int r1, int r2)
197 long bt = O_T(op);
198 if (r2 != R_RDX) {
199 if (bt & T_MSIGN)
200 op_x(I_CQO, R_RAX, R_RDX, LONGSZ);
201 else
202 i_num(R_RDX, 0);
204 op_rr(I_MUL, bt & T_MSIGN ? 7 : 6, r2, LONGSZ);
207 static void i_tst(int rn, int rm)
209 op_rr(I_TST, rn, rm, LONGSZ);
212 static void i_cmp(int rn, int rm)
214 op_rr(I_CMP, rn, rm, LONGSZ);
217 static void i_cmp_imm(int rn, long n)
219 unsigned char s[4] = {REX(0, rn), 0x83, 0xf8 | rn, n & 0xff};
220 os(s, 4);
223 static void i_shl(int op, int rd, int r1, int rs)
225 long bt = O_T(op);
226 int sm = 4;
227 if ((op & 0x0f) == 1)
228 sm = bt & T_MSIGN ? 7 : 5;
229 op_rr(I_SHX, sm, rd, LONGSZ);
232 static void i_shl_imm(int op, int rd, int rn, long n)
234 long bt = O_T(op);
235 int sm = (op & 0x1) ? (bt & T_MSIGN ? 0xf8 : 0xe8) : 0xe0;
236 char s[4] = {REX(0, rn), 0xc1, sm | (rn & 7), n & 0xff};
237 os(s, 4);
240 static void i_neg(int rd)
242 op_rr(I_NOT, 3, rd, LONGSZ);
245 static void i_not(int rd)
247 op_rr(I_NOT, 2, rd, LONGSZ);
250 static int i_cond(long op)
252 /* lt, ge, eq, ne, le, gt */
253 static int ucond[] = {0x92, 0x93, 0x94, 0x95, 0x96, 0x97};
254 static int scond[] = {0x9c, 0x9d, 0x94, 0x95, 0x9e, 0x9f};
255 long bt = O_T(op);
256 return bt & T_MSIGN ? scond[op & 0x0f] : ucond[op & 0x0f];
259 static void i_set(long op, int rd)
261 char set[] = "\x0f\x00\xc0";
262 set[1] = i_cond(op);
263 os(set, 3); /* setl al */
264 os("\x48\x0f\xb6\xc0", 4); /* movzx rax, al */
267 static void i_lnot(int rd)
269 char cmp[] = "\x00\x83\xf8\x00";
270 cmp[0] = REX(0, rd);
271 cmp[2] |= rd & 7;
272 os(cmp, 4); /* cmp rax, 0 */
273 i_set(O_EQ, rd);
276 static void jx(int x, int nbytes)
278 char op[2] = {0x0f};
279 if (nbytes == 1) {
280 op[0] = 0x70 | (x & 0x0f);
281 os(op, 1); /* jx $addr */
282 } else {
283 op[1] = x;
284 os(op, 2); /* jx $addr */
288 static long i_jmp(long op, long rn, long rm, int nbytes)
290 long ret;
291 if (nbytes > 1)
292 nbytes = 4;
293 if (op & (O_JZ | O_JCC)) {
294 if (op & O_JZ) {
295 i_tst(rn, rn);
296 jx(O_C(op) == O_JZ ? 0x84 : 0x85, nbytes);
297 } else {
298 if (op & O_NUM)
299 i_cmp_imm(rn, rm);
300 else
301 i_cmp(rn, rm);
302 jx(i_cond(op) & ~0x10, nbytes);
304 } else {
305 os(nbytes == 1 ? "\xeb" : "\xe9", 1); /* jmp $addr */
307 ret = opos();
308 oi(0, nbytes);
309 return ret;
312 void i_fill(long src, long dst, long nbytes)
314 if (nbytes > 1)
315 nbytes = 4;
316 oi_at(src, dst - src - nbytes, nbytes);
319 static void i_zx(int rd, int r1, int bits)
321 if (bits & 0x07) {
322 i_shl_imm(O_SHL, rd, rd, LONGSZ * 8 - bits);
323 i_shl_imm(O_SHR, rd, rd, LONGSZ * 8 - bits);
324 } else {
325 mov_r2r(rd, r1, bits >> 3);
329 static void i_sx(int rd, int r1, int bits)
331 mov_r2r(rd, r1, T_MSIGN | (bits >> 3));
334 static void i_cast(int rd, int rn, int bt)
336 if (T_SZ(bt) == 8) {
337 if (rd != rn)
338 i_mov(rd, rn);
339 } else {
340 if (bt & T_MSIGN)
341 i_sx(rd, rn, T_SZ(bt) * 8);
342 else
343 i_zx(rd, rn, T_SZ(bt) * 8);
347 static void i_add_anyimm(int rd, int rn, long n)
349 op_rm(I_LEA, rd, rn, n, LONGSZ);
352 static long *rel_sym; /* relocation symbols */
353 static long *rel_flg; /* relocation flags */
354 static long *rel_off; /* relocation offsets */
355 static long rel_n, rel_sz; /* relocation count */
357 static long lab_sz; /* label count */
358 static long *lab_loc; /* label offsets in cs */
359 static long jmp_n, jmp_sz; /* jump count */
360 static long *jmp_off; /* jump offsets */
361 static long *jmp_dst; /* jump destinations */
362 static long jmp_ret; /* the position of the last return jmp */
364 static void lab_add(long id)
366 while (id >= lab_sz) {
367 int lab_n = lab_sz;
368 lab_sz = MAX(128, lab_sz * 2);
369 lab_loc = mextend(lab_loc, lab_n, lab_sz, sizeof(*lab_loc));
371 lab_loc[id] = opos();
374 static void jmp_add(long off, long dst)
376 if (jmp_n == jmp_sz) {
377 jmp_sz = MAX(128, jmp_sz * 2);
378 jmp_off = mextend(jmp_off, jmp_n, jmp_sz, sizeof(*jmp_off));
379 jmp_dst = mextend(jmp_dst, jmp_n, jmp_sz, sizeof(*jmp_dst));
381 jmp_off[jmp_n] = off;
382 jmp_dst[jmp_n] = dst;
383 jmp_n++;
386 void i_label(long id)
388 lab_add(id + 1);
391 static void i_rel(long sym, long flg, long off)
393 if (rel_n == rel_sz) {
394 rel_sz = MAX(128, rel_sz * 2);
395 rel_sym = mextend(rel_sym, rel_n, rel_sz, sizeof(*rel_sym));
396 rel_flg = mextend(rel_flg, rel_n, rel_sz, sizeof(*rel_flg));
397 rel_off = mextend(rel_off, rel_n, rel_sz, sizeof(*rel_off));
399 rel_sym[rel_n] = sym;
400 rel_flg[rel_n] = flg;
401 rel_off[rel_n] = off;
402 rel_n++;
405 static void i_sym(int rd, int sym, int off)
407 int sz = X64_ABS_RL & OUT_RL32 ? 4 : LONGSZ;
408 if (X64_ABS_RL & OUT_RLSX)
409 op_rr(I_MOVI, 0, rd, sz);
410 else
411 op_x(I_MOVIR + (rd & 7), 0, rd, sz);
412 i_rel(sym, OUT_CS | X64_ABS_RL, opos());
413 oi(off, sz);
416 static void i_saveargs(long sargs)
418 int i;
419 os("\x58", 1); /* pop rax */
420 for (i = N_ARGS - 1; i >= 0; i--)
421 if ((1 << argregs[i]) & sargs)
422 i_push(argregs[i]);
423 os("\x50", 1); /* push rax */
426 static void i_saveregs(long sregs, long sregs_pos, int st)
428 int nsregs = 0;
429 int i;
430 for (i = 0; i < N_TMPS; i++)
431 if ((1 << tmpregs[i]) & sregs)
432 op_rm(st ? I_MOV : I_MOVR, tmpregs[i], REG_FP,
433 sregs_pos + nsregs++ * ULNG, ULNG);
436 void i_wrap(int argc, long sargs, long spsub, int initfp, long sregs, long sregs_pos)
438 long body_n;
439 void *body;
440 long diff; /* prologue length */
441 int nsargs = 0; /* number of saved arguments */
442 int mod16; /* 16-byte alignment */
443 int i;
444 /* removing the last jmp to the epilogue */
445 if (jmp_ret + 5 == opos()) {
446 mem_cut(&cs, jmp_ret);
447 jmp_n--;
449 lab_add(0); /* the return label */
450 body_n = mem_len(&cs);
451 body = mem_get(&cs);
452 /* generating function prologue */
453 if (sargs)
454 i_saveargs(sargs);
455 if (initfp) {
456 os("\x55", 1); /* push rbp */
457 os("\x48\x89\xe5", 3); /* mov rbp, rsp */
459 for (i = 0; i < N_ARGS; i++)
460 if ((1 << argregs[i]) & sargs)
461 nsargs++;
462 mod16 = (spsub + nsargs * LONGSZ) % 16; /* forcing 16-byte alignment */
463 if (spsub) {
464 os("\x48\x81\xec", 3);
465 spsub = spsub + (16 - mod16);
466 oi(spsub, 4);
468 i_saveregs(sregs, sregs_pos, 1); /* saving registers */
469 diff = mem_len(&cs);
470 mem_put(&cs, body, body_n);
471 free(body);
472 /* generating function epilogue */
473 i_saveregs(sregs, sregs_pos, 0); /* restoring saved registers */
474 if (initfp)
475 os("\xc9", 1); /* leave */
476 if (sargs) {
477 os("\xc2", 1); /* ret n */
478 oi(nsargs * LONGSZ, 2);
479 } else {
480 os("\xc3", 1); /* ret */
482 /* adjusting code offsets */
483 for (i = 0; i < rel_n; i++)
484 rel_off[i] += diff;
485 for (i = 0; i < jmp_n; i++)
486 jmp_off[i] += diff;
487 for (i = 0; i < lab_sz; i++)
488 lab_loc[i] += diff;
491 void i_code(char **c, long *c_len, long **rsym, long **rflg, long **roff, long *rcnt)
493 int i;
494 for (i = 0; i < jmp_n; i++) /* filling jmp destinations */
495 oi_at(jmp_off[i], lab_loc[jmp_dst[i]] - jmp_off[i] - 4, 4);
496 *c_len = mem_len(&cs);
497 *c = mem_get(&cs);
498 *rsym = rel_sym;
499 *rflg = rel_flg;
500 *roff = rel_off;
501 *rcnt = rel_n;
502 rel_sym = NULL;
503 rel_flg = NULL;
504 rel_off = NULL;
505 rel_n = 0;
506 rel_sz = 0;
507 jmp_n = 0;
510 void i_done(void)
512 free(jmp_off);
513 free(jmp_dst);
514 free(lab_loc);
517 long i_reg(long op, long *rd, long *r1, long *r2, long *tmp)
519 int oc = O_C(op);
520 *rd = 0;
521 *r1 = 0;
522 *r2 = 0;
523 *tmp = 0;
524 if (oc & O_MOV) {
525 *rd = R_TMPS;
526 *r1 = oc & (O_NUM | O_SYM) ? 0 : R_TMPS;
527 return 0;
529 if (oc & O_ADD) {
530 *r1 = R_TMPS;
531 *r2 = oc & O_NUM ? (oc == O_ADD ? 32 : 8) : R_TMPS;
532 return 0;
534 if (oc & O_SHL) {
535 if (oc & O_NUM) {
536 *r1 = R_TMPS;
537 *r2 = 8;
538 } else {
539 *r2 = 1 << R_RCX;
540 *r1 = R_TMPS & ~*r2;
542 return 0;
544 if (oc & O_MUL) {
545 if (oc & O_NUM)
546 return 1;
547 *rd = oc == O_MOD ? (1 << R_RDX) : (1 << R_RAX);
548 *r1 = (1 << R_RAX);
549 *r2 = R_TMPS & ~*rd & ~*r1;
550 if (oc == O_DIV)
551 *r2 &= ~(1 << R_RDX);
552 *tmp = (1 << R_RDX) | (1 << R_RAX);
553 return 0;
555 if (oc & O_CMP) {
556 *rd = 1 << R_RAX;
557 *r1 = R_TMPS;
558 *r2 = oc & O_NUM ? 8 : R_TMPS;
559 return 0;
561 if (oc & O_UOP) {
562 *rd = R_TMPS;
563 if (oc == O_LNOT)
564 *r1 = 1 << R_RAX;
565 else
566 *r1 = R_TMPS;
567 return 0;
569 if (oc == O_MSET) {
570 *rd = 1 << R_RDI;
571 *r1 = 1 << R_RAX;
572 *r2 = 1 << R_RCX;
573 return 0;
575 if (oc == O_MCPY) {
576 *rd = 1 << R_RDI;
577 *r1 = 1 << R_RSI;
578 *r2 = 1 << R_RCX;
579 return 0;
581 if (oc == O_RET) {
582 *rd = (1 << REG_RET);
583 return 0;
585 if (oc & O_CALL) {
586 *rd = (1 << REG_RET);
587 *r1 = oc & O_SYM ? 0 : R_TMPS;
588 return 0;
590 if (oc & (O_LD | O_ST)) {
591 *rd = R_TMPS;
592 *r1 = R_TMPS;
593 *r2 = oc & O_NUM ? 0 : R_TMPS;
594 return 0;
596 if (oc & O_JZ) {
597 *rd = R_TMPS;
598 return 0;
600 if (oc & O_JCC) {
601 *rd = R_TMPS;
602 *r1 = oc & O_NUM ? 8 : R_TMPS;
603 return 0;
605 if (oc == O_JMP)
606 return 0;
607 return 1;
610 int i_imm(long lim, long n)
612 long max = (1 << (lim - 1)) - 1;
613 return n <= max && n + 1 >= -max;
616 long i_ins(long op, long r0, long r1, long r2)
618 long oc = O_C(op);
619 long bt = O_T(op);
620 if (oc & O_ADD) {
621 if (oc & O_NUM) {
622 if (r0 == r1 && r2 <= 127 && r2 >= -128)
623 i_add_imm(op, r1, r1, r2);
624 else
625 i_add_anyimm(r0, r1, r2);
626 } else {
627 i_add(op, r1, r1, r2);
630 if (oc & O_SHL) {
631 if (oc & O_NUM)
632 i_shl_imm(op, r1, r1, r2);
633 else
634 i_shl(op, r1, r1, r2);
636 if (oc & O_MUL) {
637 if (oc == O_MUL)
638 i_mul(R_RAX, r1, r2);
639 if (oc == O_DIV)
640 i_div(op, R_RAX, r1, r2);
641 if (oc == O_MOD)
642 i_div(op, R_RDX, r1, r2);
643 return 0;
645 if (oc & O_CMP) {
646 if (oc & O_NUM)
647 i_cmp_imm(r1, r2);
648 else
649 i_cmp(r1, r2);
650 i_set(op, r0);
651 return 0;
653 if (oc & O_UOP) { /* uop */
654 if (oc == O_NEG)
655 i_neg(r1);
656 if (oc == O_NOT)
657 i_not(r1);
658 if (oc == O_LNOT)
659 i_lnot(r1);
660 return 0;
662 if (oc == O_CALL) {
663 op_rr(I_CALL, 2, r1, LONGSZ);
664 return 0;
666 if (oc == (O_CALL | O_SYM)) {
667 os("\xe8", 1); /* call $x */
668 i_rel(r1, OUT_CS | OUT_RLREL, opos());
669 oi(-4 + r2, 4);
670 return 0;
672 if (oc == (O_MOV | O_SYM)) {
673 i_sym(r0, r1, r2);
674 return 0;
676 if (oc == (O_MOV | O_NUM)) {
677 i_num(r0, r1);
678 return 0;
680 if (oc == O_MSET) {
681 os("\xfc\xf3\xaa", 3); /* cld; rep stosb */
682 return 0;
684 if (oc == O_MCPY) {
685 os("\xfc\xf3\xa4", 3); /* cld; rep movs */
686 return 0;
688 if (oc == O_RET) {
689 jmp_ret = opos();
690 jmp_add(i_jmp(O_JMP, 0, 0, 4), 0);
691 return 0;
693 if (oc == (O_LD | O_NUM)) {
694 op_rm(movrx_op(bt, I_MOVR), r0, r1, r2, movrx_bt(bt));
695 return 0;
697 if (oc == (O_ST | O_NUM)) {
698 op_rm(I_MOV, r0, r1, r2, bt);
699 return 0;
701 if (oc == O_MOV) {
702 i_cast(r0, r1, bt);
703 return 0;
705 if (oc & O_JXX) {
706 jmp_add(i_jmp(op, r0, r1, 4), r2 + 1);
707 return 0;
709 return 1;