gen.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "gen.h"
   4 #include "tok.h"
   5
   6 #define TMP_ADDR        0x0001
   7 #define LOC_REG         0x0100
   8 #define LOC_MEM         0x0200
   9 #define LOC_NUM         0x0400
  10 #define LOC_SYM         0x0800
  11 #define LOC_LOCAL       0x1000
  12 #define LOC_MASK        0xff00
  13
  14 #define R_RAX           0x00
  15 #define R_RCX           0x01
  16 #define R_RDX           0x02
  17 #define R_RBX           0x03
  18 #define R_RSP           0x04
  19 #define R_RBP           0x05
  20 #define R_RSI           0x06
  21 #define R_RDI           0x07
  22 #define R_R8            0x08
  23 #define R_R9            0x09
  24 #define R_R10           0x0a
  25 #define R_R11           0x0b
  26 #define R_R12           0x0c
  27 #define R_R13           0x0d
  28 #define R_R14           0x0e
  29 #define R_R15           0x0f
  30 #define NREGS           0x10
  31
  32 #define MOV_M2R         0x8b
  33 #define MOV_R2X         0x89
  34 #define MOV_I2R         0xc7
  35 #define ADD_R2R         0x01
  36 #define SUB_R2R         0x29
  37 #define SHX_REG         0xd3
  38 #define CMP_R2R         0x39
  39 #define LEA_M2R         0x8d
  40
  41 #define TMP_BT(t)               ((t)->flags & TMP_ADDR ? 8 : (t)->bt)
  42
  43 static char buf[SECSIZE];
  44 static char *cur;
  45 static long sp;
  46 static long spsub_addr;
  47 static long maxsp;
  48
  49 static struct tmp {
  50         long addr;
  51         unsigned flags;
  52         unsigned bt;
  53 } tmp[MAXTMP];
  54 static int ntmp;
  55
  56 static char names[MAXTMP][NAMELEN];
  57 static int nnames;
  58 static int tmpsp;
  59
  60 static struct tmp *regs[NREGS];
  61 static int tmpregs[] = {R_RAX, R_RDI, R_RSI, R_RDX, R_RCX, R_R8, R_R9};
  62
  63 static void putint(char *s, long n, int l)
  64 {
  65         while (l--) {
  66                 *s++ = n;
  67                 n >>= 8;
  68         }
  69 }
  70
  71 static void os(char *s, int n)
  72 {
  73         while (n--)
  74                 *cur++ = *s++;
  75 }
  76
  77 static void oi(long n, int l)
  78 {
  79         while (l--) {
  80                 *cur++ = n;
  81                 n >>= 8;
  82         }
  83 }
  84
  85 static long codeaddr(void)
  86 {
  87         return cur - buf;
  88 }
  89
  90 static void o_op(int op, int r1, int r2, unsigned bt)
  91 {
  92         int rex = 0;
  93         if (r1 & 0x8)
  94                 rex |= 4;
  95         if (r2 & 0x8)
  96                 rex |= 1;
  97         if (rex || (bt & BT_SZMASK) == 8)
  98                 oi(0x48 | rex, 1);
  99         if ((bt & BT_SZMASK) == 2)
 100                 oi(0x66, 1);
 101         if ((bt & BT_SZMASK) == 1)
 102                 op &= ~0x1;
 103         oi(op, 1);
 104 }
 105
 106 static void memop(int op, int src, int base, int off, unsigned bt)
 107 {
 108         int dis = off == (char) off ? 1 : 4;
 109         int mod = dis == 4 ? 2 : 1;
 110         o_op(op, src, base, bt);
 111         if (!off)
 112                 mod = 0;
 113         oi((mod << 6) | ((src & 0x07) << 3) | (base & 0x07), 1);
 114         if (off)
 115                 oi(off, dis);
 116 }
 117
 118 static void regop(int op, int src, int dst, unsigned bt)
 119 {
 120         o_op(op, src, dst, bt);
 121         oi((3 << 6) | (src << 3) | (dst & 0x07), 1);
 122 }
 123
 124 static long sp_push(int size)
 125 {
 126         sp += size;
 127         if (sp > maxsp)
 128                 maxsp = sp;
 129         return sp;
 130 }
 131
 132 #define LOC_NEW(f, l)           (((f) & ~LOC_MASK) | (l))
 133
 134 static void tmp_mem(struct tmp *tmp)
 135 {
 136         int src = tmp->addr;
 137         if (!(tmp->flags & LOC_REG))
 138                 return;
 139         if (tmpsp == -1)
 140                 tmpsp = sp;
 141         tmp->addr = sp_push(8);
 142         memop(MOV_R2X, src, R_RBP, -tmp->addr, TMP_BT(tmp));
 143         regs[src] = NULL;
 144         tmp->flags = LOC_NEW(tmp->flags, LOC_MEM);
 145 }
 146
 147 static void tmp_reg(struct tmp *tmp, unsigned dst, int deref)
 148 {
 149         if (!(tmp->flags & TMP_ADDR))
 150                 deref = 0;
 151         if (deref)
 152                 tmp->flags &= ~TMP_ADDR;
 153         if (tmp->flags & LOC_NUM) {
 154                 regop(MOV_I2R, 0, dst, TMP_BT(tmp));
 155                 oi(tmp->addr, BT_SZ(tmp->bt));
 156                 tmp->addr = dst;
 157                 regs[dst] = tmp;
 158                 tmp->flags = LOC_NEW(tmp->flags, LOC_REG);
 159         }
 160         if (tmp->flags & LOC_SYM) {
 161                 regop(MOV_I2R, 0, dst, TMP_BT(tmp));
 162                 out_rela(names[tmp->addr], codeaddr(), 0);
 163                 oi(0, 4);
 164                 tmp->addr = dst;
 165                 regs[dst] = tmp;
 166                 tmp->flags = LOC_NEW(tmp->flags, LOC_REG);
 167         }
 168         if (tmp->flags & LOC_REG) {
 169                 if (deref) {
 170                         memop(MOV_M2R, dst, tmp->addr, 0, tmp->bt);
 171                 } else {
 172                         if (dst == tmp->addr)
 173                                 return;
 174                         regop(MOV_R2X, tmp->addr, dst, TMP_BT(tmp));
 175                 }
 176                 regs[tmp->addr] = NULL;
 177                 tmp->addr = dst;
 178                 regs[dst] = tmp;
 179                 return;
 180         }
 181         if (tmp->flags & LOC_LOCAL) {
 182                 if (deref)
 183                         memop(MOV_M2R, dst, R_RBP, -tmp->addr, TMP_BT(tmp));
 184                 else
 185                         memop(LEA_M2R, dst, R_RBP, -tmp->addr, 8);
 186         }
 187         if (tmp->flags & LOC_MEM) {
 188                 memop(MOV_M2R, dst, R_RBP, -tmp->addr, TMP_BT(tmp));
 189                 if (deref)
 190                         memop(MOV_M2R, dst, dst, 0, TMP_BT(tmp));
 191         }
 192         tmp->addr = dst;
 193         regs[dst] = tmp;
 194         tmp->flags = LOC_NEW(tmp->flags, LOC_REG);
 195 }
 196
 197 static void reg_free(int reg)
 198 {
 199         int i;
 200         if (!regs[reg])
 201                 return;
 202         for (i = 0; i < ARRAY_SIZE(tmpregs); i++)
 203                 if (!regs[tmpregs[i]]) {
 204                         tmp_reg(regs[reg], tmpregs[i], 0);
 205                         return;
 206                 }
 207         tmp_mem(regs[reg]);
 208 }
 209
 210 static void reg_for(int reg, struct tmp *t)
 211 {
 212         if (regs[reg] && regs[reg] != t)
 213                 reg_free(reg);
 214 }
 215
 216 static unsigned tmp_pop(int deref, int reg)
 217 {
 218         struct tmp *t = &tmp[--ntmp];
 219         reg_for(reg, t);
 220         tmp_reg(t, reg, deref);
 221         regs[reg] = NULL;
 222         return t->bt;
 223 }
 224
 225 static void tmp_push_reg(unsigned bt, unsigned reg)
 226 {
 227         struct tmp *t = &tmp[ntmp++];
 228         t->addr = reg;
 229         t->bt = bt;
 230         t->flags = LOC_REG;
 231         regs[reg] = t;
 232 }
 233
 234 void o_local(long addr, unsigned bt)
 235 {
 236         struct tmp *t = &tmp[ntmp++];
 237         t->addr = addr;
 238         t->bt = bt;
 239         t->flags = LOC_LOCAL | TMP_ADDR;
 240 }
 241
 242 void o_num(long num, unsigned bt)
 243 {
 244         struct tmp *t = &tmp[ntmp++];
 245         t->addr = num;
 246         t->bt = bt;
 247         t->flags = LOC_NUM;
 248 }
 249
 250 void o_symaddr(char *name, unsigned bt)
 251 {
 252         int id = nnames++;
 253         struct tmp *t = &tmp[ntmp++];
 254         t->bt = bt;
 255         t->addr = id;
 256         t->flags = LOC_SYM | TMP_ADDR;
 257         strcpy(names[id], name);
 258 }
 259
 260 void o_tmpdrop(int n)
 261 {
 262         int i;
 263         if (n == -1 || n > ntmp)
 264                 n = ntmp;
 265         ntmp -= n;
 266         for (i = ntmp; i < ntmp + n; i++)
 267                 if (tmp[i].flags & LOC_REG)
 268                         regs[tmp[i].addr] = NULL;
 269         if (!ntmp) {
 270                 nnames = 0;
 271                 if (tmpsp != -1)
 272                         sp = tmpsp;
 273                 tmpsp = -1;
 274         }
 275 }
 276
 277 #define FORK_REG                R_RAX
 278
 279 void o_tmpfork(void)
 280 {
 281         struct tmp *t = &tmp[ntmp - 1];
 282         reg_for(FORK_REG, t);
 283         tmp_reg(t, FORK_REG, 0);
 284         o_tmpdrop(1);
 285 }
 286
 287 void o_tmpjoin(void)
 288 {
 289         struct tmp *t = &tmp[ntmp - 1];
 290         reg_for(FORK_REG, t);
 291         tmp_reg(t, FORK_REG, 0);
 292 }
 293
 294 void o_tmpswap(void)
 295 {
 296         struct tmp *t1 = &tmp[ntmp - 1];
 297         struct tmp *t2 = &tmp[ntmp - 2];
 298         struct tmp t;
 299         memcpy(&t, t1, sizeof(t));
 300         memcpy(t1, t2, sizeof(t));
 301         memcpy(t2, &t, sizeof(t));
 302 }
 303
 304 static int reg_other(int not)
 305 {
 306         int i;
 307         for (i = 0; i < ARRAY_SIZE(tmpregs); i++)
 308                 if (tmpregs[i] != not && !regs[tmpregs[i]])
 309                         return tmpregs[i];
 310         for (i = 0; i < ARRAY_SIZE(tmpregs); i++)
 311                 if (tmpregs[i] != not) {
 312                         reg_free(tmpregs[i]);
 313                         return tmpregs[i];
 314                 }
 315         return 0;
 316 }
 317
 318 static int reg_get(void)
 319 {
 320         return reg_other(-1);
 321 }
 322
 323 void o_tmpcopy(void)
 324 {
 325         struct tmp *t1 = &tmp[ntmp - 1];
 326         struct tmp *t2 = &tmp[ntmp++];
 327         if (!(t1->flags & (LOC_REG | LOC_MEM))) {
 328                 memcpy(t2, t1, sizeof(*t2));
 329                 return;
 330         }
 331         memcpy(t2, t1, sizeof(*t1));
 332         if (t1->flags & LOC_MEM)
 333                 tmp_reg(t2, reg_get(), 0);
 334         else if (t1->flags & LOC_REG) {
 335                 t2->addr = reg_get();
 336                 regop(MOV_R2X, t1->addr, t2->addr, TMP_BT(tmp));
 337         }
 338         t2->flags = t1->flags;
 339 }
 340
 341 void o_func_beg(char *name)
 342 {
 343         out_func_beg(name);
 344         cur = buf;
 345         os("\x55", 1);                  /* push %rbp */
 346         os("\x48\x89\xe5", 3);          /* mov %rsp, %rbp */
 347         sp = 0;
 348         maxsp = 0;
 349         ntmp = 0;
 350         nnames = 0;
 351         tmpsp = -1;
 352         memset(regs, 0, sizeof(regs));
 353         os("\x48\x81\xec", 3);          /* sub $xxx, %rsp */
 354         spsub_addr = codeaddr();
 355         oi(0, 4);
 356 }
 357
 358 void o_deref(unsigned bt)
 359 {
 360         struct tmp *t = &tmp[ntmp - 1];
 361         if (t->flags & TMP_ADDR) {
 362                 int reg = t->flags & LOC_REG ? t->addr : reg_get();
 363                 tmp_reg(t, reg, 1);
 364         }
 365         t->flags |= TMP_ADDR;
 366 }
 367
 368 void o_load(void)
 369 {
 370         struct tmp *t = &tmp[ntmp - 1];
 371         int reg = t->flags & LOC_REG ? t->addr : reg_get();
 372         tmp_reg(t, reg, 1);
 373 }
 374
 375 void o_shl(void)
 376 {
 377         struct tmp *t = &tmp[ntmp - 2];
 378         unsigned reg;
 379         unsigned bt;
 380         tmp_pop(1, R_RCX);
 381         reg = (t->flags & LOC_REG) ? t->addr : reg_get();
 382         bt = tmp_pop(1, reg);
 383         regop(SHX_REG, 4, reg, bt);
 384         tmp_push_reg(bt, reg);
 385 }
 386
 387 void o_shr(void)
 388 {
 389         struct tmp *t = &tmp[ntmp - 2];
 390         unsigned reg;
 391         unsigned bt;
 392         tmp_pop(1, R_RCX);
 393         reg = (t->flags & LOC_REG) ? t->addr : reg_get();
 394         bt = tmp_pop(1, reg);
 395         regop(SHX_REG, bt & BT_SIGNED ? 5 : 7, reg, bt);
 396         tmp_push_reg(bt, reg);
 397 }
 398
 399 #define MUL_A2X         0xf7
 400
 401 void o_mul(void)
 402 {
 403         struct tmp *t1 = &tmp[ntmp - 1];
 404         int bt1, bt2;
 405         int reg;
 406         if (t1->flags & LOC_REG && t1->addr != R_RAX)
 407                 reg = t1->addr;
 408         else
 409                 reg = reg_other(R_RAX);
 410         bt1 = tmp_pop(1, reg);
 411         bt2 = tmp_pop(1, R_RAX);
 412         regop(MUL_A2X, bt2 & BT_SIGNED ? 5 : 4, reg, bt2);
 413         tmp_push_reg(bt2, R_RAX);
 414 }
 415
 416 void o_addr(void)
 417 {
 418         tmp[ntmp - 1].flags &= ~TMP_ADDR;
 419         tmp[ntmp - 1].bt = 8;
 420 }
 421
 422 void o_ret(unsigned bt)
 423 {
 424         if (bt)
 425                 tmp_pop(1, R_RAX);
 426         else
 427                 os("\x31\xc0", 2);      /* xor %eax, %eax */
 428         os("\xc9\xc3", 2);              /* leave; ret; */
 429 }
 430
 431 static int binop(int *r1, int *r2)
 432 {
 433         struct tmp *t1 = &tmp[ntmp - 1];
 434         struct tmp *t2 = &tmp[ntmp - 2];
 435         unsigned bt1, bt2;
 436         *r1 = t1->flags & LOC_REG ? t1->addr : reg_get();
 437         *r2 = t2->flags & LOC_REG ? t2->addr : reg_other(*r1);
 438         bt1 = tmp_pop(1, *r1);
 439         bt2 = tmp_pop(1, *r2);
 440         return BT_SZ(bt1) > BT_SZ(bt2) ? bt1 : bt2;
 441 }
 442
 443 void o_add(void)
 444 {
 445         int r1, r2;
 446         int bt = binop(&r1, &r2);
 447         regop(ADD_R2R, r1, r2, bt);
 448         tmp_push_reg(bt, r2);
 449 }
 450
 451 void o_sub(void)
 452 {
 453         int r1, r2;
 454         int bt = binop(&r1, &r2);
 455         regop(SUB_R2R, r1, r2, bt);
 456         tmp_push_reg(bt, r2);
 457 }
 458
 459 static void o_cmp(int uop, int sop)
 460 {
 461         char set[] = "\x0f\x00\xc0";
 462         int r1, r2;
 463         int bt = binop(&r1, &r2);
 464         regop(CMP_R2R, r1, r2, bt);
 465         set[1] = bt & BT_SIGNED ? sop : uop;
 466         reg_free(R_RAX);
 467         os(set, 3);                     /* setl %al */
 468         os("\x0f\xb6\xc0", 3);          /* movzbl %al, %eax */
 469         tmp_push_reg(4 | BT_SIGNED, R_RAX);
 470 }
 471
 472 void o_lt(void)
 473 {
 474         o_cmp(0x92, 0x9c);
 475 }
 476
 477 void o_func_end(void)
 478 {
 479         os("\xc9\xc3", 2);              /* leave; ret; */
 480         putint(buf + spsub_addr, (maxsp + 7) & ~0x07, 4);
 481         out_func_end(buf, cur - buf);
 482 }
 483
 484 long o_mklocal(int size)
 485 {
 486         return sp_push((size + 7) & ~0x07);
 487 }
 488
 489 static int arg_regs[] = {R_RDI, R_RSI, R_RDX, R_RCX, R_R8, R_R9};
 490
 491 long o_arg(int i, unsigned bt)
 492 {
 493         long addr = o_mklocal(BT_SZ(bt));
 494         memop(MOV_R2X, arg_regs[i], R_RBP, -addr, bt);
 495         return addr;
 496 }
 497
 498 void o_assign(unsigned bt)
 499 {
 500         struct tmp *t1 = &tmp[ntmp - 1];
 501         struct tmp *t2 = &tmp[ntmp - 2];
 502         int r1 = t1->flags & LOC_REG ? t1->addr : reg_get();
 503         int reg;
 504         int off;
 505         tmp_pop(1, r1);
 506         if (t2->flags & LOC_LOCAL) {
 507                 reg = R_RBP;
 508                 off = -t2->addr;
 509                 o_tmpdrop(1);
 510         } else {
 511                 reg = t2->flags & LOC_REG ? t2->addr : reg_other(r1);
 512                 off = 0;
 513                 tmp_pop(0, reg);
 514         }
 515         memop(MOV_R2X, r1, reg, off, bt);
 516         tmp_push_reg(bt, r1);
 517 }
 518
 519 long o_mklabel(void)
 520 {
 521         return codeaddr();
 522 }
 523
 524 long o_jz(long addr)
 525 {
 526         tmp_pop(1, R_RAX);
 527         os("\x48\x85\xc0", 3);          /* test %rax, %rax */
 528         os("\x0f\x84", 2);              /* jz $addr */
 529         oi(addr - codeaddr() - 4, 4);
 530         return codeaddr() - 4;
 531 }
 532
 533 long o_jmp(long addr)
 534 {
 535         os("\xe9", 1);                  /* jmp $addr */
 536         oi(addr - codeaddr() - 4, 4);
 537         return codeaddr() - 4;
 538 }
 539
 540 void o_filljmp(long addr)
 541 {
 542         putint(buf + addr, codeaddr() - addr - 4, 4);
 543 }
 544
 545 #define CALL_REG        0xff
 546
 547 void o_call(int argc, unsigned *bt, unsigned ret_bt)
 548 {
 549         int i;
 550         struct tmp *t;
 551         for (i = 0; i < argc; i++)
 552                 tmp_pop(1, arg_regs[i]);
 553         t = &tmp[ntmp - 1];
 554         if (t->flags & LOC_SYM) {
 555                 os("\xe8", 1);          /* call $x */
 556                 out_rela(names[tmp->addr], codeaddr(), 1);
 557                 oi(-4, 4);
 558                 o_tmpdrop(1);
 559         } else {
 560                 tmp_pop(0, R_RAX);
 561                 regop(CALL_REG, 2, R_RAX, 4);
 562         }
 563         for (i = 0; i < ARRAY_SIZE(tmpregs); i++)
 564                 if (regs[i])
 565                         tmp_mem(regs[i]);
 566         if (ret_bt)
 567                 tmp_push_reg(ret_bt, R_RAX);
 568 }