x86.c

   1 /* architecture-dependent code generation for x86 */
   2 #include <stdlib.h>
   3 #include "ncc.h"
   4
   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
  14
  15 #define REG_RET         R_RAX
  16 #define R_BYTE          0x0007
  17
  18 /* x86 opcodes */
  19 #define I_MOV           0x89
  20 #define I_MOVI          0xc7
  21 #define I_MOVIR         0xb8
  22 #define I_MOVR          0x8b
  23 #define I_MOVSXD        0x63
  24 #define I_SHX           0xd3
  25 #define I_CMP           0x3b
  26 #define I_TST           0x85
  27 #define I_LEA           0x8d
  28 #define I_NOT           0xf7
  29 #define I_CALL          0xff
  30 #define I_MUL           0xf7
  31 #define I_XOR           0x33
  32 #define I_CQO           0x99
  33 #define I_PUSH          0x50
  34 #define I_POP           0x58
  35
  36 #define MIN(a, b)               ((a) < (b) ? (a) : (b))
  37 #define ALIGN(x, a)             (((x) + (a) - 1) & ~((a) - 1))
  38
  39 int tmpregs[] = {0, 1, 2, 6, 7, 3};
  40 int argregs[] = {0};
  41
  42 #define OP2(o2, o1)             (0x010000 | ((o2) << 8) | (o1))
  43 #define O2(op)                  (((op) >> 8) & 0xff)
  44 #define O1(op)                  ((op) & 0xff)
  45 #define MODRM(m, r1, r2)        ((m) << 6 | (r1) << 3 | (r2))
  46
  47 static struct mem cs;           /* generated code */
  48
  49 /* code generation functions */
  50 static void os(void *s, int n)
  51 {
  52         mem_put(&cs, s, n);
  53 }
  54
  55 static char *ointbuf(long n, int l)
  56 {
  57         static char buf[16];
  58         int i;
  59         for (i = 0; i < l; i++) {
  60                 buf[i] = n & 0xff;
  61                 n >>= 8;
  62         }
  63         return buf;
  64 }
  65
  66 static void oi(long n, int l)
  67 {
  68         mem_put(&cs, ointbuf(n, l), l);
  69 }
  70
  71 static void oi_at(long pos, long n, int l)
  72 {
  73         mem_cpy(&cs, pos, ointbuf(n, l), l);
  74 }
  75
  76 static long opos(void)
  77 {
  78         return mem_len(&cs);
  79 }
  80
  81 static void op_x(int op, int r1, int r2, int bt)
  82 {
  83         int sz = T_SZ(bt);
  84         if (sz == 2)
  85                 oi(0x66, 1);
  86         if (op & 0x10000)
  87                 oi(O2(op), 1);
  88         oi(sz == 1 ? O1(op) & ~0x1 : O1(op), 1);
  89 }
  90
  91 #define op_mr           op_rm
  92
  93 /* op_*(): r=reg, m=mem, i=imm, s=sym */
  94 static void op_rm(int op, int src, int base, int off, int bt)
  95 {
  96         int dis = off == (char) off ? 1 : 4;
  97         int mod = dis == 4 ? 2 : 1;
  98         if (!off && (base & 7) != R_RBP)
  99                 mod = 0;
 100         op_x(op, src, base, bt);
 101         oi(MODRM(mod, src & 0x07, base & 0x07), 1);
 102         if ((base & 7) == R_RSP)
 103                 oi(0x24, 1);
 104         if (mod)
 105                 oi(off, dis);
 106 }
 107
 108 static void op_rr(int op, int src, int dst, int bt)
 109 {
 110         op_x(op, src, dst, bt);
 111         oi(MODRM(3, src & 0x07, dst & 0x07), 1);
 112 }
 113
 114 #define movrx_bt(bt)            (LONGSZ)
 115
 116 static int movrx_op(int bt, int mov)
 117 {
 118         int sz = T_SZ(bt);
 119         if (sz == 2)
 120                 return OP2(0x0f, bt & T_MSIGN ? 0xbf : 0xb7);
 121         if (sz == 1)
 122                 return OP2(0x0f, bt & T_MSIGN ? 0xbe : 0xb6);
 123         return mov;
 124 }
 125
 126 static void mov_r2r(int rd, int r1, unsigned bt)
 127 {
 128         if (rd != r1 || T_SZ(bt) != LONGSZ)
 129                 op_rr(movrx_op(bt, I_MOVR), rd, r1, movrx_bt(bt));
 130 }
 131
 132 static void i_push(int reg)
 133 {
 134         op_x(I_PUSH | (reg & 0x7), 0, reg, LONGSZ);
 135 }
 136
 137 static void i_pop(int reg)
 138 {
 139         op_x(I_POP | (reg & 0x7), 0, reg, LONGSZ);
 140 }
 141
 142 void i_mov(int rd, int rn)
 143 {
 144         op_rr(movrx_op(LONGSZ, I_MOVR), rd, rn, movrx_bt(LONGSZ));
 145 }
 146
 147 static void i_add(int op, int rd, int r1, int r2)
 148 {
 149         /* opcode for O_ADD, O_SUB, O_AND, O_OR, O_XOR */
 150         static int rx[] = {0003, 0053, 0043, 0013, 0063};
 151         op_rr(rx[op & 0x0f], rd, r2, LONGSZ);
 152 }
 153
 154 static void i_add_imm(int op, int rd, int rn, long n)
 155 {
 156         /* opcode for O_ADD, O_SUB, O_AND, O_OR, O_XOR */
 157         static int rx[] = {0xc0, 0xe8, 0xe0, 0xc8, 0xf0};
 158         unsigned char s[4] = {0x83, rx[op & 0x0f] | rd, n & 0xff};
 159         os((void *) s, 3);
 160 }
 161
 162 static void i_num(int rd, long n)
 163 {
 164         if (!n) {
 165                 op_rr(I_XOR, rd, rd, 4);
 166                 return;
 167         } else {
 168                 op_x(I_MOVIR + (rd & 7), 0, rd, LONGSZ);
 169                 oi(n, LONGSZ);
 170         }
 171 }
 172
 173 static void i_mul(int rd, int r1, int r2)
 174 {
 175         if (r2 != R_RDX)
 176                 i_num(R_RDX, 0);
 177         op_rr(I_MUL, 4, r2, LONGSZ);
 178 }
 179
 180 static void i_div(int op, int rd, int r1, int r2)
 181 {
 182         long bt = O_T(op);
 183         if (r2 != R_RDX) {
 184                 if (bt & T_MSIGN)
 185                         op_x(I_CQO, R_RAX, R_RDX, LONGSZ);
 186                 else
 187                         i_num(R_RDX, 0);
 188         }
 189         op_rr(I_MUL, bt & T_MSIGN ? 7 : 6, r2, LONGSZ);
 190 }
 191
 192 static void i_tst(int rn, int rm)
 193 {
 194         op_rr(I_TST, rn, rm, LONGSZ);
 195 }
 196
 197 static void i_cmp(int rn, int rm)
 198 {
 199         op_rr(I_CMP, rn, rm, LONGSZ);
 200 }
 201
 202 static void i_cmp_imm(int rn, long n)
 203 {
 204         unsigned char s[4] = {0x83, 0xf8 | rn, n & 0xff};
 205         os(s, 3);
 206 }
 207
 208 static void i_shl(int op, int rd, int r1, int rs)
 209 {
 210         long bt = O_T(op);
 211         int sm = 4;
 212         if ((op & 0x0f) == 1)
 213                 sm = bt & T_MSIGN ? 7 : 5;
 214         op_rr(I_SHX, sm, rd, LONGSZ);
 215 }
 216
 217 static void i_shl_imm(int op, int rd, int rn, long n)
 218 {
 219         long bt = O_T(op);
 220         int sm = (op & 0x1) ? (bt & T_MSIGN ? 0xf8 : 0xe8) : 0xe0;
 221         char s[4] = {0xc1, sm | rn, n & 0xff};
 222         os(s, 3);
 223 }
 224
 225 static void i_neg(int rd)
 226 {
 227         op_rr(I_NOT, 3, rd, LONGSZ);
 228 }
 229
 230 static void i_not(int rd)
 231 {
 232         op_rr(I_NOT, 2, rd, LONGSZ);
 233 }
 234
 235 static int i_cond(long op)
 236 {
 237         /* lt, ge, eq, ne, le, gt */
 238         static int ucond[] = {0x92, 0x93, 0x94, 0x95, 0x96, 0x97};
 239         static int scond[] = {0x9c, 0x9d, 0x94, 0x95, 0x9e, 0x9f};
 240         long bt = O_T(op);
 241         return bt & T_MSIGN ? scond[op & 0x0f] : ucond[op & 0x0f];
 242 }
 243
 244 static void i_set(long op, int rd)
 245 {
 246         char set[] = "\x0f\x00\xc0";
 247         set[1] = i_cond(op);
 248         os(set, 3);                     /* setl al */
 249         os("\x0f\xb6\xc0", 3);          /* movzx rax, al */
 250 }
 251
 252 static void i_lnot(int rd)
 253 {
 254         char cmp[] = "\x83\xf8\x00";
 255         cmp[1] |= rd;
 256         os(cmp, 3);             /* cmp rax, 0 */
 257         i_set(O_EQ, rd);
 258 }
 259
 260 static void jx(int x, int nbytes)
 261 {
 262         char op[2] = {0x0f};
 263         if (nbytes == 1) {
 264                 oi(0x70 | (x & 0x0f), 1);       /* jx $addr */
 265         } else {
 266                 op[1] = x;
 267                 os(op, 2);                      /* jx $addr */
 268         }
 269 }
 270
 271 static long i_jmp(long op, long rn, long rm, int nbytes)
 272 {
 273         long ret;
 274         if (nbytes > 1)
 275                 nbytes = 4;
 276         if (op & (O_JZ | O_JCC)) {
 277                 if (op & O_JZ) {
 278                         i_tst(rn, rn);
 279                         jx(O_C(op) == O_JZ ? 0x84 : 0x85, nbytes);
 280                 } else {
 281                         if (op & O_NUM)
 282                                 i_cmp_imm(rn, rm);
 283                         else
 284                                 i_cmp(rn, rm);
 285                         jx(i_cond(op) & ~0x10, nbytes);
 286                 }
 287         } else {
 288                 os(nbytes == 1 ? "\xeb" : "\xe9", 1);   /* jmp $addr */
 289         }
 290         ret = opos();
 291         oi(0, nbytes);
 292         return ret;
 293 }
 294
 295 static void i_zx(int rd, int r1, int bits)
 296 {
 297         if (bits & 0x07) {
 298                 i_shl_imm(O_SHL, rd, rd, LONGSZ * 8 - bits);
 299                 i_shl_imm(O_SHR, rd, rd, LONGSZ * 8 - bits);
 300         } else {
 301                 mov_r2r(rd, r1, bits >> 3);
 302         }
 303 }
 304
 305 static void i_sx(int rd, int r1, int bits)
 306 {
 307         mov_r2r(rd, r1, T_MSIGN | (bits >> 3));
 308 }
 309
 310 static void i_cast(int rd, int rn, int bt)
 311 {
 312         if (T_SZ(bt) == 8) {
 313                 if (rd != rn)
 314                         i_mov(rd, rn);
 315         } else {
 316                 if (bt & T_MSIGN)
 317                         i_sx(rd, rn, T_SZ(bt) * 8);
 318                 else
 319                         i_zx(rd, rn, T_SZ(bt) * 8);
 320         }
 321 }
 322
 323 static void i_add_anyimm(int rd, int rn, long n)
 324 {
 325         op_rm(I_LEA, rd, rn, n, LONGSZ);
 326 }
 327
 328 static long *rel_sym;           /* relocation symbols */
 329 static long *rel_flg;           /* relocation flags */
 330 static long *rel_off;           /* relocation offsets */
 331 static long rel_n, rel_sz;      /* relocation count */
 332
 333 static long lab_sz;             /* label count */
 334 static long *lab_loc;           /* label offsets in cs */
 335 static long jmp_n, jmp_sz;      /* jump count */
 336 static long *jmp_off;           /* jump offsets */
 337 static long *jmp_dst;           /* jump destinations */
 338 static long jmp_ret;            /* the position of the last return jmp */
 339
 340 static void lab_add(long id)
 341 {
 342         while (id >= lab_sz) {
 343                 int lab_n = lab_sz;
 344                 lab_sz = MAX(128, lab_sz * 2);
 345                 lab_loc = mextend(lab_loc, lab_n, lab_sz, sizeof(*lab_loc));
 346         }
 347         lab_loc[id] = opos();
 348 }
 349
 350 static void jmp_add(long off, long dst)
 351 {
 352         if (jmp_n == jmp_sz) {
 353                 jmp_sz = MAX(128, jmp_sz * 2);
 354                 jmp_off = mextend(jmp_off, jmp_n, jmp_sz, sizeof(*jmp_off));
 355                 jmp_dst = mextend(jmp_dst, jmp_n, jmp_sz, sizeof(*jmp_dst));
 356         }
 357         jmp_off[jmp_n] = off;
 358         jmp_dst[jmp_n] = dst;
 359         jmp_n++;
 360 }
 361
 362 void i_label(long id)
 363 {
 364         lab_add(id + 1);
 365 }
 366
 367 static void i_rel(long sym, long flg, long off)
 368 {
 369         if (rel_n == rel_sz) {
 370                 rel_sz = MAX(128, rel_sz * 2);
 371                 rel_sym = mextend(rel_sym, rel_n, rel_sz, sizeof(*rel_sym));
 372                 rel_flg = mextend(rel_flg, rel_n, rel_sz, sizeof(*rel_flg));
 373                 rel_off = mextend(rel_off, rel_n, rel_sz, sizeof(*rel_off));
 374         }
 375         rel_sym[rel_n] = sym;
 376         rel_flg[rel_n] = flg;
 377         rel_off[rel_n] = off;
 378         rel_n++;
 379 }
 380
 381 static void i_sym(int rd, int sym, int off)
 382 {
 383         op_x(I_MOVIR + (rd & 7), 0, rd, LONGSZ);
 384         i_rel(sym, OUT_CS, opos());
 385         oi(off, LONGSZ);
 386 }
 387
 388 static void i_saveregs(long sregs, long sregs_pos, int st)
 389 {
 390         int nsregs = 0;
 391         int i;
 392         for (i = 0; i < N_TMPS; i++)
 393                 if ((1 << tmpregs[i]) & sregs)
 394                         op_rm(st ? I_MOV : I_MOVR, tmpregs[i], REG_FP,
 395                                 sregs_pos + nsregs++ * ULNG, ULNG);
 396 }
 397
 398 void i_wrap(int argc, long sargs, long spsub, int initfp, long sregs, long sregs_pos)
 399 {
 400         long body_n;
 401         void *body;
 402         long diff;              /* prologue length */
 403         int i;
 404         /* removing the last jmp to the epilogue */
 405         if (jmp_ret + 5 == opos()) {
 406                 mem_cut(&cs, jmp_ret);
 407                 jmp_n--;
 408         }
 409         lab_add(0);                             /* the return label */
 410         body_n = mem_len(&cs);
 411         body = mem_get(&cs);
 412         /* generating function prologue */
 413         if (initfp) {
 414                 os("\x55", 1);                  /* push rbp */
 415                 os("\x89\xe5", 2);              /* mov rbp, rsp */
 416         }
 417         if (spsub) {
 418                 os("\x81\xec", 2);
 419                 spsub = ALIGN(spsub, 8);
 420                 oi(spsub, 4);
 421         }
 422         i_saveregs(sregs, sregs_pos, 1);        /* saving registers */
 423         diff = mem_len(&cs);
 424         mem_put(&cs, body, body_n);
 425         free(body);
 426         /* generating function epilogue */
 427         i_saveregs(sregs, sregs_pos, 0);        /* restoring saved registers */
 428         if (initfp)
 429                 os("\xc9", 1);                  /* leave */
 430         os("\xc3", 1);                          /* ret */
 431         /* adjusting code offsets */
 432         for (i = 0; i < rel_n; i++)
 433                 rel_off[i] += diff;
 434         for (i = 0; i < jmp_n; i++)
 435                 jmp_off[i] += diff;
 436         for (i = 0; i < lab_sz; i++)
 437                 lab_loc[i] += diff;
 438 }
 439
 440 void i_code(char **c, long *c_len, long **rsym, long **rflg, long **roff, long *rcnt)
 441 {
 442         int i;
 443         for (i = 0; i < jmp_n; i++)     /* filling jmp destinations */
 444                 oi_at(jmp_off[i], lab_loc[jmp_dst[i]] - jmp_off[i] - 4, 4);
 445         *c_len = mem_len(&cs);
 446         *c = mem_get(&cs);
 447         *rsym = rel_sym;
 448         *rflg = rel_flg;
 449         *roff = rel_off;
 450         *rcnt = rel_n;
 451         rel_sym = NULL;
 452         rel_flg = NULL;
 453         rel_off = NULL;
 454         rel_n = 0;
 455         rel_sz = 0;
 456         jmp_n = 0;
 457 }
 458
 459 void i_done(void)
 460 {
 461         free(jmp_off);
 462         free(jmp_dst);
 463         free(lab_loc);
 464 }
 465
 466 long i_reg(long op, long *rd, long *r1, long *r2, long *tmp)
 467 {
 468         long oc = O_C(op);
 469         long bt = O_T(op);
 470         *rd = 0;
 471         *r1 = 0;
 472         *r2 = 0;
 473         *tmp = 0;
 474         if (oc & O_MOV) {
 475                 *rd = R_TMPS;
 476                 if (oc & (O_NUM | O_SYM))
 477                         *r1 = oc & (O_NUM | O_SYM) ? LONGSZ * 8 : R_TMPS;
 478                 else
 479                         *r1 = T_SZ(bt) == 1 ? R_BYTE : R_TMPS;
 480                 return 0;
 481         }
 482         if (oc & O_ADD) {
 483                 *r1 = R_TMPS;
 484                 *r2 = oc & O_NUM ? (oc == O_ADD ? 32 : 8) : R_TMPS;
 485                 return 0;
 486         }
 487         if (oc & O_SHL) {
 488                 if (oc & O_NUM) {
 489                         *r1 = R_TMPS;
 490                         *r2 = 8;
 491                 } else {
 492                         *r2 = 1 << R_RCX;
 493                         *r1 = R_TMPS & ~*r2;
 494                 }
 495                 return 0;
 496         }
 497         if (oc & O_MUL) {
 498                 if (oc & O_NUM)
 499                         return 1;
 500                 *rd = oc == O_MOD ? (1 << R_RDX) : (1 << R_RAX);
 501                 *r1 = (1 << R_RAX);
 502                 *r2 = R_TMPS & ~*rd & ~*r1;
 503                 if (oc == O_DIV)
 504                         *r2 &= ~(1 << R_RDX);
 505                 *tmp = (1 << R_RDX) | (1 << R_RAX);
 506                 return 0;
 507         }
 508         if (oc & O_CMP) {
 509                 *rd = 1 << R_RAX;
 510                 *r1 = R_TMPS;
 511                 *r2 = oc & O_NUM ? 8 : R_TMPS;
 512                 return 0;
 513         }
 514         if (oc & O_UOP) {
 515                 *rd = R_TMPS;
 516                 if (oc == O_LNOT)
 517                         *r1 = 1 << R_RAX;
 518                 else
 519                         *r1 = R_TMPS;
 520                 return 0;
 521         }
 522         if (oc == O_MSET) {
 523                 *rd = 1 << R_RDI;
 524                 *r1 = 1 << R_RAX;
 525                 *r2 = 1 << R_RCX;
 526                 return 0;
 527         }
 528         if (oc == O_MCPY) {
 529                 *rd = 1 << R_RDI;
 530                 *r1 = 1 << R_RSI;
 531                 *r2 = 1 << R_RCX;
 532                 return 0;
 533         }
 534         if (oc == O_RET) {
 535                 *rd = (1 << REG_RET);
 536                 return 0;
 537         }
 538         if (oc & O_CALL) {
 539                 *rd = (1 << REG_RET);
 540                 *r1 = oc & O_SYM ? 0 : R_TMPS;
 541                 return 0;
 542         }
 543         if (oc & (O_LD | O_ST)) {
 544                 *rd = R_TMPS;
 545                 *r1 = R_TMPS;
 546                 *r2 = oc & O_NUM ? 0 : R_TMPS;
 547                 return 0;
 548         }
 549         if (oc & O_JZ) {
 550                 *rd = R_TMPS;
 551                 return 0;
 552         }
 553         if (oc & O_JCC) {
 554                 *rd = R_TMPS;
 555                 *r1 = oc & O_NUM ? 8 : R_TMPS;
 556                 return 0;
 557         }
 558         if (oc == O_JMP)
 559                 return 0;
 560         return 1;
 561 }
 562
 563 int i_imm(long lim, long n)
 564 {
 565         long max = (1 << (lim - 1)) - 1;
 566         return n <= max && n + 1 >= -max;
 567 }
 568
 569 long i_ins(long op, long r0, long r1, long r2)
 570 {
 571         long oc = O_C(op);
 572         long bt = O_T(op);
 573         if (oc & O_ADD) {
 574                 if (oc & O_NUM) {
 575                         if (r0 == r1 && r2 <= 127 && r2 >= -128)
 576                                 i_add_imm(op, r1, r1, r2);
 577                         else
 578                                 i_add_anyimm(r0, r1, r2);
 579                 } else {
 580                         i_add(op, r1, r1, r2);
 581                 }
 582         }
 583         if (oc & O_SHL) {
 584                 if (oc & O_NUM)
 585                         i_shl_imm(op, r1, r1, r2);
 586                 else
 587                         i_shl(op, r1, r1, r2);
 588         }
 589         if (oc & O_MUL) {
 590                 if (oc == O_MUL)
 591                         i_mul(R_RAX, r1, r2);
 592                 if (oc == O_DIV)
 593                         i_div(op, R_RAX, r1, r2);
 594                 if (oc == O_MOD)
 595                         i_div(op, R_RDX, r1, r2);
 596                 return 0;
 597         }
 598         if (oc & O_CMP) {
 599                 if (oc & O_NUM)
 600                         i_cmp_imm(r1, r2);
 601                 else
 602                         i_cmp(r1, r2);
 603                 i_set(op, r0);
 604                 return 0;
 605         }
 606         if (oc & O_UOP) {       /* uop */
 607                 if (oc == O_NEG)
 608                         i_neg(r1);
 609                 if (oc == O_NOT)
 610                         i_not(r1);
 611                 if (oc == O_LNOT)
 612                         i_lnot(r1);
 613                 return 0;
 614         }
 615         if (oc == O_CALL) {
 616                 op_rr(I_CALL, 2, r1, LONGSZ);
 617                 return 0;
 618         }
 619         if (oc == (O_CALL | O_SYM)) {
 620                 os("\xe8", 1);          /* call $x */
 621                 i_rel(r1, OUT_CS | OUT_RLREL, opos());
 622                 oi(-4, 4);
 623                 return 0;
 624         }
 625         if (oc == (O_MOV | O_SYM)) {
 626                 i_sym(r0, r1, r2);
 627                 return 0;
 628         }
 629         if (oc == (O_MOV | O_NUM)) {
 630                 i_num(r0, r1);
 631                 return 0;
 632         }
 633         if (oc == O_MSET) {
 634                 os("\xfc\xf3\xaa", 3);          /* cld; rep stosb */
 635                 return 0;
 636         }
 637         if (oc == O_MCPY) {
 638                 os("\xfc\xf3\xa4", 3);          /* cld; rep movs */
 639                 return 0;
 640         }
 641         if (oc == O_RET) {
 642                 jmp_ret = opos();
 643                 jmp_add(i_jmp(O_JMP, 0, 0, 4), 0);
 644                 return 0;
 645         }
 646         if (oc == (O_LD | O_NUM)) {
 647                 op_rm(movrx_op(bt, I_MOVR), r0, r1, r2, movrx_bt(bt));
 648                 return 0;
 649         }
 650         if (oc == (O_ST | O_NUM)) {
 651                 op_rm(I_MOV, r0, r1, r2, bt);
 652                 return 0;
 653         }
 654         if (oc == O_MOV) {
 655                 i_cast(r0, r1, bt);
 656                 return 0;
 657         }
 658         if (oc & O_JXX) {
 659                 jmp_add(i_jmp(op, r0, r1, 4), r2 + 1);
 660                 return 0;
 661         }
 662         return 1;
 663 }