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