gen.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include "gen.h"
   5 #include "out.h"
   6 #include "tok.h"
   7
   8 /* variable location */
   9 #define LOC_REG         0x01
  10 #define LOC_MEM         0x02
  11 #define LOC_NUM         0x04
  12 #define LOC_SYM         0x08
  13 #define LOC_LOCAL       0x10
  14
  15 #define MIN(a, b)               ((a) < (b) ? (a) : (b))
  16 #define ALIGN(x, a)             (((x) + (a) - 1) & ~((a) - 1))
  17
  18 char cs[SECSIZE];               /* code segment */
  19 int cslen;
  20 static char ds[SECSIZE];        /* data segment */
  21 static int dslen;
  22 static long bsslen;             /* bss segment size */
  23
  24 static long sp;                 /* stack pointer offset from R_RBP */
  25 static long sp_max;             /* maximum stack pointer offset */
  26 static long sp_tmp;             /* sp for the first tmp on the stack */
  27
  28 #define TMP(i)          (((i) < ntmp) ? &tmps[ntmp - 1 - (i)] : NULL)
  29
  30 static struct tmp {
  31         long addr;
  32         char sym[NAMELEN];
  33         long off;       /* offset from a symbol or a local */
  34         unsigned loc;   /* variable location */
  35         unsigned bt;    /* type of address; zero when not a pointer */
  36         int id;         /* local variable id */
  37 } tmps[MAXTMP];
  38 static int ntmp;
  39
  40 static struct tmp *regs[N_REGS];
  41
  42 #define MAXLOCALS       (1 << 10)
  43 static struct local {
  44         int loc;
  45         int sz;
  46         int n_addr;             /* # of address accesses */
  47         int n_access;           /* # of accesses */
  48 } locals[MAXLOCALS];
  49 static int nlocals;
  50
  51 /* function info */
  52 static int func_beg;
  53 static int func_argc;
  54 static int func_varg;
  55
  56 /* function statistics */
  57 int pass1;                      /* collect statistics; 1st pass */
  58 static int stat_calls;          /* # of function calls */
  59 static int stat_tmps;           /* # of stack temporaries  */
  60 static int stat_regs;           /* mask of used registers */
  61
  62 /* optimization info */
  63 static int pass2;               /* use the collected statistics in the 1st pass */
  64 static int tmp_mask;            /* registers that can be used for tmps */
  65 static int opt_sargs;           /* saved args */
  66 static int opt_isreg[MAXLOCALS];/* is a register allocated to a local? */
  67 static int opt_lreg[MAXLOCALS]; /* registers allocated to locals */
  68 static int opt_lregs;           /* mask of registers allocated to locals */
  69
  70 #define TMP_ISLREG(t)   (!(t)->bt && (t)->loc == LOC_LOCAL && opt_isreg[(t)->id])
  71 #define TMP_LREG(t)     (opt_lreg[(t)->id])
  72
  73 /* labels and jmps */
  74 #define MAXJMPS         (1 << 14)
  75
  76 static long labels[MAXJMPS];
  77 static int nlabels;
  78 static long jmp_loc[MAXJMPS];
  79 static int jmp_goal[MAXJMPS];
  80 static int jmp_len[MAXJMPS];
  81 static int njmps;
  82
  83 void o_label(int id)
  84 {
  85         if (id > nlabels)
  86                 nlabels = id + 1;
  87         labels[id] = cslen;
  88 }
  89
  90 /* the number of bytes needed for holding jmp displacement */
  91 static int jmp_sz(int id)
  92 {
  93         long n = jmp_len[id] > 0 ? jmp_len[id] : -jmp_len[id];
  94         if (!pass2)
  95                 return 4;
  96         if (n < 0x70)
  97                 return n == 0 ? 0 : 1;
  98         return n < 0x7000 ? 2 : 4;
  99 }
 100
 101 static void jmp_add(int id, int rn, int z)
 102 {
 103         if (njmps >= MAXJMPS)
 104                 err("nomem: MAXJMPS reached!\n");
 105         i_jmp(rn, z, jmp_sz(njmps));
 106         jmp_loc[njmps] = cslen;
 107         jmp_goal[njmps] = id;
 108         njmps++;
 109 }
 110
 111 static void jmp_fill(void)
 112 {
 113         int i;
 114         for (i = 0; i < njmps; i++)
 115                 jmp_len[i] = i_fill(jmp_loc[i], labels[jmp_goal[i]], jmp_sz(i));
 116 }
 117
 118 /* generating code */
 119
 120 void os(void *s, int n)
 121 {
 122         while (n--)
 123                 cs[cslen++] = *(char *) (s++);
 124 }
 125
 126 void oi(long n, int l)
 127 {
 128         while (l--) {
 129                 cs[cslen++] = n;
 130                 n >>= 8;
 131         }
 132 }
 133
 134 static long sp_push(int sz)
 135 {
 136         sp -= ALIGN(sz, LONGSZ);
 137         if (sp < sp_max)
 138                 sp_max = sp;
 139         return sp;
 140 }
 141
 142 static void tmp_mem(struct tmp *tmp)
 143 {
 144         int src = tmp->addr;
 145         if (tmp->loc != LOC_REG || (1 << src) & opt_lregs)
 146                 return;
 147         if (sp_tmp == -1)
 148                 sp_tmp = sp;
 149         tmp->addr = sp_push(LONGSZ);
 150         i_save(src, REG_FP, tmp->addr, LONGSZ);
 151         stat_tmps++;
 152         regs[src] = NULL;
 153         tmp->loc = LOC_MEM;
 154 }
 155
 156 static void num_cast(struct tmp *t, unsigned bt)
 157 {
 158         if (!(bt & BT_SIGNED) && BT_SZ(bt) != LONGSZ)
 159                 t->addr &= ((1l << (long) (BT_SZ(bt) * 8)) - 1);
 160         if (bt & BT_SIGNED && BT_SZ(bt) != LONGSZ &&
 161                                 t->addr > (1l << (BT_SZ(bt) * 8 - 1)))
 162                 t->addr = -((1l << (BT_SZ(bt) * 8)) - t->addr);
 163 }
 164
 165 static void tmp_reg(struct tmp *tmp, int dst, int deref)
 166 {
 167         int bt = tmp->bt;
 168         if (!tmp->bt)
 169                 deref = 0;
 170         if (deref)
 171                 tmp->bt = 0;
 172         if (tmp->loc == LOC_NUM) {
 173                 i_num(dst, tmp->addr);
 174                 tmp->addr = dst;
 175                 regs[dst] = tmp;
 176                 tmp->loc = LOC_REG;
 177         }
 178         if (tmp->loc == LOC_SYM) {
 179                 i_sym(dst, tmp->sym, tmp->off);
 180                 tmp->addr = dst;
 181                 regs[dst] = tmp;
 182                 tmp->loc = LOC_REG;
 183         }
 184         if (tmp->loc == LOC_REG) {
 185                 if (deref)
 186                         i_load(dst, tmp->addr, 0, bt);
 187                 else if (dst != tmp->addr)
 188                         i_mov(dst, tmp->addr);
 189                 regs[tmp->addr] = NULL;
 190         }
 191         if (tmp->loc == LOC_LOCAL) {
 192                 if (deref)
 193                         locals[tmp->id].n_access++;
 194                 else
 195                         locals[tmp->id].n_addr++;
 196                 if (deref)
 197                         i_load(dst, REG_FP, tmp->addr + tmp->off, bt);
 198                 else
 199                         i_op_imm(O_ADD, dst, REG_FP, tmp->addr + tmp->off);
 200         }
 201         if (tmp->loc == LOC_MEM) {
 202                 i_load(dst, REG_FP, tmp->addr, LONGSZ);
 203                 if (deref)
 204                         i_load(dst, dst, 0, bt);
 205         }
 206         tmp->addr = dst;
 207         stat_regs |= 1 << dst;
 208         regs[dst] = tmp;
 209         tmp->loc = LOC_REG;
 210 }
 211
 212 /* empty the given register, but never touch the registers in rsrvd mask */
 213 static void reg_free(int reg, int rsrvd)
 214 {
 215         int i;
 216         if (!regs[reg])
 217                 return;
 218         rsrvd |= ~tmp_mask;
 219         for (i = 0; i < N_TMPS; i++)
 220                 if (!regs[tmpregs[i]] && ~rsrvd & (1 << tmpregs[i])) {
 221                         tmp_reg(regs[reg], tmpregs[i], 0);
 222                         return;
 223                 }
 224         tmp_mem(regs[reg]);
 225 }
 226
 227 static void reg_for(int reg, struct tmp *t)
 228 {
 229         if (regs[reg] && regs[reg] != t)
 230                 reg_free(reg, 0);
 231 }
 232
 233 static void tmp_mv(struct tmp *t, int reg)
 234 {
 235         reg_for(reg, t);
 236         tmp_reg(t, reg, 0);
 237 }
 238
 239 static void tmp_to(struct tmp *t, int reg)
 240 {
 241         reg_for(reg, t);
 242         if (t->loc == LOC_LOCAL && TMP_ISLREG(t)) {
 243                 t->loc = LOC_REG;
 244                 t->addr = TMP_LREG(t);
 245                 t->bt = 0;
 246         }
 247         tmp_reg(t, reg, 1);
 248 }
 249
 250 static void tmp_drop(int n)
 251 {
 252         int i;
 253         for (i = ntmp - n; i < ntmp; i++)
 254                 if (tmps[i].loc == LOC_REG)
 255                         regs[tmps[i].addr] = NULL;
 256         ntmp -= n;
 257 }
 258
 259 static void tmp_pop(int reg)
 260 {
 261         struct tmp *t = TMP(0);
 262         tmp_to(t, reg);
 263         tmp_drop(1);
 264 }
 265
 266 static struct tmp *tmp_new(void)
 267 {
 268         return &tmps[ntmp++];
 269 }
 270
 271 static void tmp_push(int reg)
 272 {
 273         struct tmp *t = tmp_new();
 274         t->addr = reg;
 275         t->bt = 0;
 276         stat_regs |= 1 << reg;
 277         t->loc = LOC_REG;
 278         regs[reg] = t;
 279 }
 280
 281 void o_local(long addr)
 282 {
 283         struct tmp *t = tmp_new();
 284         t->addr = locals[addr].loc;
 285         t->id = addr;
 286         t->loc = LOC_LOCAL;
 287         t->bt = 0;
 288         t->off = 0;
 289 }
 290
 291 void o_num(long num)
 292 {
 293         struct tmp *t = tmp_new();
 294         t->addr = num;
 295         t->bt = 0;
 296         t->loc = LOC_NUM;
 297 }
 298
 299 void o_sym(char *name)
 300 {
 301         struct tmp *t = tmp_new();
 302         strcpy(t->sym, name);
 303         t->loc = LOC_SYM;
 304         t->bt = 0;
 305         t->off = 0;
 306 }
 307
 308 void o_tmpdrop(int n)
 309 {
 310         if (n == -1 || n > ntmp)
 311                 n = ntmp;
 312         tmp_drop(n);
 313         if (!ntmp) {
 314                 if (sp_tmp != -1)
 315                         sp = sp_tmp;
 316                 sp_tmp = -1;
 317         }
 318 }
 319
 320 /* make sure tmps remain intact after a conditional expression */
 321 void o_fork(void)
 322 {
 323         int i;
 324         for (i = 0; i < ntmp - 1; i++)
 325                 tmp_mem(&tmps[i]);
 326 }
 327
 328 void o_forkpush(void)
 329 {
 330         tmp_pop(REG_FORK);
 331 }
 332
 333 void o_forkjoin(void)
 334 {
 335         tmp_push(REG_FORK);
 336 }
 337
 338 void o_tmpswap(void)
 339 {
 340         struct tmp *t1 = TMP(0);
 341         struct tmp *t2 = TMP(1);
 342         struct tmp t;
 343         memcpy(&t, t1, sizeof(t));
 344         memcpy(t1, t2, sizeof(t));
 345         memcpy(t2, &t, sizeof(t));
 346         if (t1->loc == LOC_REG)
 347                 regs[t1->addr] = t1;
 348         if (t2->loc == LOC_REG)
 349                 regs[t2->addr] = t2;
 350 }
 351
 352 static int reg_get(int mask)
 353 {
 354         int i;
 355         mask &= tmp_mask;
 356         for (i = 0; i < N_TMPS; i++)
 357                 if ((1 << tmpregs[i]) & mask && !regs[tmpregs[i]]) {
 358                         stat_regs |= 1 << tmpregs[i];
 359                         return tmpregs[i];
 360                 }
 361         for (i = 0; i < N_TMPS; i++)
 362                 if ((1 << tmpregs[i]) & mask) {
 363                         reg_free(tmpregs[i], 0);
 364                         stat_regs |= 1 << tmpregs[i];
 365                         return tmpregs[i];
 366                 }
 367         die("reg_get: out of registers!\n");
 368         return 0;
 369 }
 370
 371 static int reg_tmp(struct tmp *t, int mask, int readonly)
 372 {
 373         if (t->loc == LOC_REG && (mask & (1 << t->addr)))
 374                 if (!(opt_lregs & (1 << t->addr)) || (readonly && !t->bt))
 375                         return t->addr;
 376         return reg_get(mask);
 377 }
 378
 379 static int reg_tmpn(struct tmp *t, int notmask, int readonly)
 380 {
 381         if (t->loc == LOC_REG && !(notmask & (1 << t->addr)))
 382                 if (!(opt_lregs & (1 << t->addr)) || (readonly && !t->bt))
 383                         return t->addr;
 384         return reg_get(~notmask);
 385 }
 386
 387 static void tmp_copy(struct tmp *t1)
 388 {
 389         struct tmp *t2 = tmp_new();
 390         memcpy(t2, t1, sizeof(*t1));
 391         if (!(t1->loc & (LOC_REG | LOC_MEM)))
 392                 return;
 393         if (t1->loc == LOC_MEM) {
 394                 tmp_mv(t2, reg_get(R_TMPS));
 395         } else if (t1->loc == LOC_REG) {
 396                 t2->addr = reg_tmpn(t2, 1 << t1->addr, 0);
 397                 i_mov(t2->addr, t1->addr);
 398                 regs[t2->addr] = t2;
 399                 stat_regs |= 1 << t2->addr;
 400         }
 401 }
 402
 403 void o_tmpcopy(void)
 404 {
 405         tmp_copy(TMP(0));
 406 }
 407
 408 void o_deref(unsigned bt)
 409 {
 410         struct tmp *t = TMP(0);
 411         if (TMP_ISLREG(t)) {
 412                 t->loc = LOC_REG;
 413                 t->addr = TMP_LREG(t);
 414         } else {
 415                 if (t->bt)
 416                         tmp_to(t, reg_tmp(t, R_TMPS, 0));
 417                 t->bt = bt;
 418         }
 419 }
 420
 421 void o_load(void)
 422 {
 423         struct tmp *t = TMP(0);
 424         tmp_to(t, reg_tmp(t, R_TMPS, 0));
 425 }
 426
 427 #define TMP_NUM(t)      ((t)->loc == LOC_NUM && !(t)->bt)
 428 #define LOCAL_PTR(t)    ((t)->loc == LOC_LOCAL && !(t)->bt)
 429 #define SYM_PTR(t)      ((t)->loc == LOC_SYM && !(t)->bt)
 430
 431 int o_popnum(long *c)
 432 {
 433         struct tmp *t = TMP(0);
 434         if (!TMP_NUM(t))
 435                 return 1;
 436         *c = t->addr;
 437         tmp_drop(1);
 438         return 0;
 439 }
 440
 441 void o_ret(int rets)
 442 {
 443         if (rets)
 444                 tmp_pop(REG_RET);
 445         else
 446                 i_num(REG_RET, 0);
 447         o_jmp(0);
 448 }
 449
 450 long o_mklocal(int sz)
 451 {
 452         locals[nlocals].loc = sp_push(ALIGN(sz, LONGSZ));
 453         locals[nlocals].sz = sz;
 454         return nlocals++;
 455 }
 456
 457 void o_rmlocal(long addr, int sz)
 458 {
 459 }
 460
 461 long o_arg2loc(int i)
 462 {
 463         return i;
 464 }
 465
 466 #define MOVXX(bt)       ((BT_SZ(bt) == LONGSZ ? O_MOV : ((bt) & BT_SIGNED ? O_SX : O_ZX)))
 467
 468 void o_assign(unsigned bt)
 469 {
 470         struct tmp *t1 = TMP(0);
 471         struct tmp *t2 = TMP(1);
 472         int r1 = reg_tmp(t1, BT_SZ(bt) > 1 ? R_TMPS : R_BYTE, 1);
 473         int r2 = reg_tmpn(t2, 1 << r1, 1);
 474         int off = 0;
 475         tmp_to(t1, r1);
 476         if (TMP_ISLREG(t2)) {
 477                 i_op_imm(MOVXX(bt), TMP_LREG(t2), r1, BT_SZ(bt) * 8);
 478                 goto done;
 479         }
 480         if (t2->bt)
 481                 tmp_to(t2, r2);
 482         if (t2->loc == LOC_LOCAL) {
 483                 r2 = REG_FP;
 484                 off = t2->addr + t2->off;
 485                 locals[t2->id].n_access++;
 486         } else {
 487                 tmp_to(t2, r2);
 488         }
 489         i_save(r1, r2, off, bt);
 490 done:
 491         tmp_drop(2);
 492         tmp_push(r1);
 493 }
 494
 495 static long cu(int op, long i)
 496 {
 497         switch (op & 0xff) {
 498         case O_NEG:
 499                 return -i;
 500         case O_NOT:
 501                 return ~i;
 502         case O_LNOT:
 503                 return !i;
 504         }
 505         return 0;
 506 }
 507
 508 static int c_uop(int op)
 509 {
 510         struct tmp *t1 = TMP(0);
 511         if (!TMP_NUM(t1))
 512                 return 1;
 513         tmp_drop(1);
 514         o_num(cu(op, t1->addr));
 515         return 0;
 516 }
 517
 518 static long cb(int op, long a, long b)
 519 {
 520         switch (op & 0xff) {
 521         case O_ADD:
 522                 return a + b;
 523         case O_SUB:
 524                 return a - b;
 525         case O_AND:
 526                 return a & b;
 527         case O_OR:
 528                 return a | b;
 529         case O_XOR:
 530                 return a ^ b;
 531         case O_MUL:
 532                 return a * b;
 533         case O_DIV:
 534                 return a / b;
 535         case O_MOD:
 536                 return a % b;
 537         case O_SHL:
 538                 return a << b;
 539         case O_SHR:
 540                 if (op & O_SIGNED)
 541                         return a >> b;
 542                 else
 543                         return (unsigned long) a >> b;
 544         case O_LT:
 545                 return a < b;
 546         case O_GT:
 547                 return a > b;
 548         case O_LE:
 549                 return a <= b;
 550         case O_GE:
 551                 return a >= b;
 552         case O_EQ:
 553                 return a == b;
 554         case O_NEQ:
 555                 return a != b;
 556         }
 557         return 0;
 558 }
 559
 560 static int c_bop(int op)
 561 {
 562         struct tmp *t1 = TMP(0);
 563         struct tmp *t2 = TMP(1);
 564         int locs = LOCAL_PTR(t1) + LOCAL_PTR(t2);
 565         int syms = SYM_PTR(t1) + SYM_PTR(t2);
 566         int nums = TMP_NUM(t1) + TMP_NUM(t2);
 567         if (syms + locs == 2 || syms + nums + locs != 2)
 568                 return 1;
 569         if (nums == 1)
 570                 if ((op & 0xff) != O_ADD && ((op & 0xff) != O_SUB || TMP_NUM(t2)))
 571                         return 1;
 572         if (nums == 1) {
 573                 long o1 = TMP_NUM(t1) ? t1->addr : t1->off;
 574                 long o2 = TMP_NUM(t2) ? t2->addr : t2->off;
 575                 long ret = cb(op, o2, o1);
 576                 if (!TMP_NUM(t1))
 577                         o_tmpswap();
 578                 if (t2->loc == LOC_LOCAL)
 579                         locals[t2->id].n_addr++;
 580                 t2->off = ret;
 581                 tmp_drop(1);
 582         } else {
 583                 long ret = cb(op, t2->addr, t1->addr);
 584                 tmp_drop(2);
 585                 o_num(ret);
 586         }
 587         return 0;
 588 }
 589
 590 /* allocate registers for the given binary or unary instruction */
 591 static void regs2(int op, int *rd, int *r1, int *r2)
 592 {
 593         int md, m1, m2, mt;
 594         int all = 0;
 595         int i;
 596         i_reg(op, &md, &m1, &m2, &mt);
 597         if (m2) {
 598                 struct tmp *t2 = TMP(0);
 599                 *r2 = reg_tmp(t2, m2, 1);
 600                 tmp_to(t2, *r2);
 601                 all |= (1 << *r2);
 602         }
 603         if (m1) {
 604                 struct tmp *t1 = TMP(m2 ? 1 : 0);
 605                 *r1 = reg_tmp(t1, m1 & ~all, md ? 1 : 0);
 606                 tmp_to(t1, *r1);
 607                 all |= (1 << *r1);
 608         }
 609         if (md) {
 610                 if (m2 && md & tmp_mask & (1 << *r2))
 611                         *rd = *r2;
 612                 else if (m1 && md & tmp_mask & (1 << *r1))
 613                         *rd = *r1;
 614                 else
 615                         *rd = reg_get(md & ~all);
 616                 all |= (1 << *rd);
 617         } else {
 618                 *rd = *r1;
 619         }
 620         if (mt & ~all) {
 621                 for (i = 0; i < N_TMPS; i++)
 622                         if (mt & ~all & (1 << tmpregs[i]))
 623                                 reg_free(tmpregs[i], all | mt);
 624         }
 625         stat_regs |= mt;
 626         tmp_drop(m2 ? 2 : 1);
 627 }
 628
 629 /* allocate registers for a 3 operand instruction */
 630 static void regs3(int op, int *r0, int *r1, int *r2)
 631 {
 632         int m0, m1, m2, mt;
 633         struct tmp *t0 = TMP(2);
 634         struct tmp *t1 = TMP(1);
 635         struct tmp *t2 = TMP(0);
 636         int all = 0;
 637         int i;
 638         i_reg(op, &m0, &m1, &m2, &mt);
 639         if (m2) {
 640                 *r2 = reg_tmp(t2, m2, 1);
 641                 tmp_to(t2, *r2);
 642                 all |= (1 << *r2);
 643         }
 644         if (m1) {
 645                 *r1 = reg_tmp(t1, m1 & ~(1 << *r2), 1);
 646                 tmp_to(t1, *r1);
 647                 all |= (1 << *r1);
 648         }
 649         if (m0) {
 650                 *r0 = reg_tmp(t0, m0 & ~((1 << *r2) | (1 << *r1)), 1);
 651                 tmp_to(t0, *r0);
 652                 all |= (1 << *r0);
 653         }
 654         if (mt & ~all) {
 655                 for (i = 0; i < N_TMPS; i++)
 656                         if (mt & ~all & (1 << tmpregs[i]))
 657                                 reg_free(tmpregs[i], all | mt);
 658         }
 659         stat_regs |= mt;
 660         tmp_drop(3);
 661 }
 662
 663 static void op_imm(int op, long n)
 664 {
 665         int rd, r1, r2;
 666         regs2(op | O_IMM, &rd, &r1, &r2);
 667         i_op_imm(op | O_IMM, rd, r1, n);
 668         tmp_push(rd);
 669 }
 670
 671 void o_uop(int op)
 672 {
 673         int rd, r1, r2;
 674         if (!c_uop(op))
 675                 return;
 676         regs2(op, &rd, &r1, &r2);
 677         i_op(op, rd, r1, r2);
 678         tmp_push(rd);
 679 }
 680
 681 static int bop_imm(int op, long *n, int swap)
 682 {
 683         struct tmp *t1 = TMP(0);
 684         struct tmp *t2 = TMP(1);
 685         if (!TMP_NUM(t1) && (!swap || !TMP_NUM(t2)))
 686                 return 1;
 687         *n = TMP_NUM(t1) ? t1->addr : t2->addr;
 688         if (!i_imm(op, *n))
 689                 return 1;
 690         if (!TMP_NUM(t1))
 691                 o_tmpswap();
 692         tmp_drop(1);
 693         return 0;
 694 }
 695
 696 static void bin_op(int op, int swap)
 697 {
 698         int rd, r1, r2;
 699         long n;
 700         if (!bop_imm(op, &n, swap)) {
 701                 regs2(op | O_IMM, &rd, &r1, &r2);
 702                 i_op_imm(op, rd, r1, n);
 703         } else {
 704                 regs2(op, &rd, &r1, &r2);
 705                 i_op(op, rd, r1, r2);
 706         }
 707         tmp_push(rd);
 708 }
 709
 710 static int log2a(unsigned long n)
 711 {
 712         int i = 0;
 713         for (i = 0; i < LONGSZ * 8; i++)
 714                 if (n & (1u << i))
 715                         break;
 716         if (i == LONGSZ * 8 || !(n >> (i + 1)))
 717                 return i;
 718         return -1;
 719 }
 720
 721 /* optimized version of mul/div/mod for powers of two */
 722 static int mul_2(int op)
 723 {
 724         struct tmp *t1 = TMP(0);
 725         struct tmp *t2 = TMP(1);
 726         long n;
 727         int p;
 728         if ((op & 0xff) == O_MUL && t2->loc == LOC_NUM && !t2->bt)
 729                 o_tmpswap();
 730         if (t1->loc != LOC_NUM || t1->bt)
 731                 return 1;
 732         n = t1->addr;
 733         p = log2a(n);
 734         if (n && p == -1)
 735                 return 1;
 736         if ((op & 0xff) == O_MUL) {
 737                 tmp_drop(1);
 738                 if (n == 1)
 739                         return 0;
 740                 if (n == 0) {
 741                         tmp_drop(1);
 742                         o_num(0);
 743                         return 0;
 744                 }
 745                 op_imm(O_SHL, p);
 746                 return 0;
 747         }
 748         if (op == O_DIV) {
 749                 tmp_drop(1);
 750                 if (n == 1)
 751                         return 0;
 752                 op_imm((op & O_SIGNED) | O_SHR, p);
 753                 return 0;
 754         }
 755         if (op == O_MOD) {
 756                 tmp_drop(1);
 757                 if (n == 1) {
 758                         tmp_drop(1);
 759                         o_num(0);
 760                         return 0;
 761                 }
 762                 op_imm(O_ZX, p);
 763                 return 0;
 764         }
 765         return 1;
 766 }
 767
 768 void o_bop(int op)
 769 {
 770         if (!c_bop(op))
 771                 return;
 772         if ((op & 0xf0) == 0x00)        /* add */
 773                 bin_op(op, (op & 0xff) != O_SUB);
 774         if ((op & 0xf0) == 0x10)        /* shx */
 775                 bin_op(op, 0);
 776         if ((op & 0xf0) == 0x20) {      /* mul */
 777                 if (!mul_2(op))
 778                         return;
 779                 bin_op(op, (op & 0xff) == O_MUL);
 780         }
 781         if ((op & 0xf0) == 0x30)
 782                 bin_op(op, (op & 0xff) == O_EQ || (op & 0xff) == O_NEQ);
 783 }
 784
 785 void o_memcpy(void)
 786 {
 787         int r0, r1, r2;
 788         regs3(O_MCPY, &r0, &r1, &r2);
 789         i_memcpy(r0, r1, r2);
 790 }
 791
 792 void o_memset(void)
 793 {
 794         int r0, r1, r2;
 795         regs3(O_MSET, &r0, &r1, &r2);
 796         i_memset(r0, r1, r2);
 797 }
 798
 799 void o_cast(unsigned bt)
 800 {
 801         struct tmp *t = TMP(0);
 802         if (!t->bt && t->loc == LOC_NUM) {
 803                 num_cast(t, bt);
 804                 return;
 805         }
 806         if (BT_SZ(bt) != LONGSZ)
 807                 op_imm(MOVXX(bt), BT_SZ(bt) * 8);
 808 }
 809
 810 static void jxz(int id, int z)
 811 {
 812         int r = reg_tmp(TMP(0), R_TMPS, 1);
 813         tmp_pop(r);
 814         jmp_add(id, r, z);
 815 }
 816
 817 void o_jz(int id)
 818 {
 819         jxz(id, 1);
 820 }
 821
 822 void o_jnz(int id)
 823 {
 824         jxz(id, 0);
 825 }
 826
 827 void o_jmp(int id)
 828 {
 829         jmp_add(id, -1, 0);
 830 }
 831
 832 void o_call(int argc, int rets)
 833 {
 834         struct tmp *t;
 835         int i;
 836         int aregs = MIN(N_ARGS, argc);
 837         for (i = 0; i < N_TMPS; i++)
 838                 if (regs[tmpregs[i]] && regs[tmpregs[i]] - tmps < ntmp - argc)
 839                         tmp_mem(regs[tmpregs[i]]);
 840         if (argc > aregs) {
 841                 sp_push(LONGSZ * (argc - aregs));
 842                 for (i = argc - 1; i >= aregs; --i) {
 843                         int reg = reg_tmp(TMP(0), R_TMPS, 1);
 844                         tmp_pop(reg);
 845                         i_save(reg, REG_SP, (i - aregs) * LONGSZ, LONGSZ);
 846                 }
 847         }
 848         for (i = aregs - 1; i >= 0; --i)
 849                 tmp_to(TMP(aregs - i - 1), argregs[i]);
 850         tmp_drop(aregs);
 851         t = TMP(0);
 852         if (t->loc == LOC_SYM && !t->bt) {
 853                 i_call(t->sym, t->off);
 854                 tmp_drop(1);
 855         } else {
 856                 int reg = reg_tmp(t, R_TMPS, 1);
 857                 tmp_pop(reg);
 858                 i_call_reg(reg);
 859         }
 860         if (rets)
 861                 tmp_push(REG_RET);
 862         stat_calls++;
 863 }
 864
 865 void o_mkbss(char *name, int size, int global)
 866 {
 867         if (pass1)
 868                 return;
 869         out_sym(name, OUT_BSS | (global ? OUT_GLOB : 0), bsslen, size);
 870         bsslen += ALIGN(size, OUT_ALIGNMENT);
 871 }
 872
 873 #define MAXDATS         (1 << 10)
 874 static char dat_names[MAXDATS][NAMELEN];
 875 static int dat_offs[MAXDATS];
 876 static int ndats;
 877
 878 void *o_mkdat(char *name, int size, int global)
 879 {
 880         void *addr = ds + dslen;
 881         int idx;
 882         if (pass1)
 883                 return addr;
 884         idx = ndats++;
 885         if (idx >= MAXDATS)
 886                 err("nomem: MAXDATS reached!\n");
 887         strcpy(dat_names[idx], name);
 888         dat_offs[idx] = dslen;
 889         out_sym(name, OUT_DS | (global ? OUT_GLOB : 0), dslen, size);
 890         dslen += ALIGN(size, OUT_ALIGNMENT);
 891         return addr;
 892 }
 893
 894 static int dat_off(char *name)
 895 {
 896         int i;
 897         for (i = 0; i < ndats; i++)
 898                 if (!strcmp(name, dat_names[i]))
 899                         return dat_offs[i];
 900         return 0;
 901 }
 902
 903 void o_datset(char *name, int off, unsigned bt)
 904 {
 905         struct tmp *t = TMP(0);
 906         int sym_off = dat_off(name) + off;
 907         if (pass1) {
 908                 tmp_drop(1);
 909                 return;
 910         }
 911         if (t->loc == LOC_NUM && !t->bt) {
 912                 num_cast(t, bt);
 913                 memcpy(ds + sym_off, &t->addr, BT_SZ(bt));
 914         }
 915         if (t->loc == LOC_SYM && !t->bt) {
 916                 out_rel(t->sym, OUT_DS, sym_off);
 917                 memcpy(ds + sym_off, &t->off, BT_SZ(bt));
 918         }
 919         tmp_drop(1);
 920 }
 921
 922 void o_write(int fd)
 923 {
 924         i_done();
 925         out_write(fd, cs, cslen, ds, dslen);
 926 }
 927
 928 static void opt_reset(void)
 929 {
 930         int i;
 931         memset(opt_isreg, 0, sizeof(opt_isreg));
 932         opt_sargs = func_varg ? R_ARGS : 0;
 933         for (i = MIN(func_argc, N_ARGS) - 1; i >= 0; --i)
 934                 opt_sargs |= 1 << argregs[i];
 935         tmp_mask = N_TMPS > 6 ? R_TMPS & ~R_SAVED : R_TMPS;
 936         opt_lregs = 0;
 937         pass1 = 0;
 938         pass2 = 0;
 939 }
 940
 941 static void func_reset(void)
 942 {
 943         int i;
 944         int argaddr = 0;
 945         memset(regs, 0, sizeof(regs));
 946         memset(locals, 0, sizeof(*locals) * nlocals);
 947         sp = i_sp();
 948         sp_max = sp;
 949         ntmp = 0;
 950         sp_tmp = -1;
 951         nlabels = 0;
 952         njmps = 0;
 953         nlocals = 0;
 954         stat_calls = 0;
 955         stat_tmps = 0;
 956         stat_regs = 1 << REG_RET;
 957         for (i = 0; i < func_argc; i++) {
 958                 locals[nlocals].loc = i_args() + argaddr;
 959                 locals[nlocals].sz = LONGSZ;
 960                 nlocals++;
 961                 if (i >= N_ARGS || opt_sargs & (1 << argregs[i]))
 962                         argaddr += LONGSZ;
 963         }
 964 }
 965
 966 void o_func_beg(char *name, int argc, int global, int varg)
 967 {
 968         func_argc = argc;
 969         func_varg = varg;
 970         func_beg = cslen;
 971         out_sym(name, (global ? OUT_GLOB : 0) | OUT_CS, cslen, 0);
 972         opt_reset();
 973         i_prolog(argc, varg, opt_sargs, tmp_mask & R_SAVED, 1, 1);
 974         func_reset();
 975 }
 976
 977 /* sort locals for register allocation based on the number of accesses */
 978 static int *sortedlocals(void)
 979 {
 980         static int ord[MAXLOCALS];
 981         int i, j;
 982         for (i = 0; i < nlocals; i++) {
 983                 for (j = i - 1; j >= 0; j--) {
 984                         if (locals[i].n_access <= locals[ord[j]].n_access)
 985                                 break;
 986                         ord[j + 1] = ord[j];
 987                 }
 988                 ord[j + 1] = i;
 989         }
 990         return ord;
 991 }
 992
 993 /* assign locals to registers */
 994 static int locals2regs(int leaf)
 995 {
 996         int *ord = sortedlocals();
 997         int nlocregs = 0;
 998         int idx = 0;
 999         int i;
1000         /* letting arguments stay in their registers for leaf functions */
1001         if (!func_varg && leaf) {
1002                 for (i = 0; i < MIN(func_argc, N_ARGS); i++) {
1003                         if (locals[i].sz > LONGSZ || (1 << argregs[i]) & stat_regs)
1004                                 continue;
1005                         if (locals[i].n_access && !locals[i].n_addr) {
1006                                 opt_isreg[i] = 1;
1007                                 opt_lreg[i] = argregs[i];
1008                                 opt_sargs &= ~(1 << argregs[i]);
1009                                 opt_lregs |= (1 << argregs[i]);
1010                                 nlocregs++;
1011                         }
1012                 }
1013         }
1014         /* try finding a register for each local */
1015         for (i = 0; i < nlocals; i++) {
1016                 int l = ord[i];
1017                 int nmask = (leaf ? 0 : ~R_SAVED) | stat_regs | opt_lregs;
1018                 if (opt_isreg[l] || (func_varg && l < func_argc))
1019                         continue;
1020                 /* find a free register */
1021                 while (idx < N_TMPS && ((1 << tmpregs[idx]) & nmask))
1022                         idx++;
1023                 if (idx >= N_TMPS)
1024                         break;
1025                 if (locals[l].sz > LONGSZ || locals[l].n_addr)
1026                         continue;
1027                 if (locals[l].n_access > (leaf ? 0 : 1)) {
1028                         opt_isreg[l] = 1;
1029                         opt_lreg[l] = tmpregs[idx];
1030                         opt_lregs |= 1 << tmpregs[idx];
1031                         if (l < MIN(N_ARGS, func_argc))
1032                                 opt_sargs &= ~(1 << argregs[l]);
1033                         nlocregs++;
1034                         idx++;
1035                 }
1036         }
1037         return nlocregs;
1038 }
1039
1040 void o_pass1(void)
1041 {
1042         pass1 = 1;
1043 }
1044
1045 void o_pass2(void)
1046 {
1047         int locregs, leaf;
1048         int initfp, subsp, sregs;
1049         int i;
1050         o_label(0);
1051         jmp_fill();
1052         leaf = !stat_calls;
1053         cslen = func_beg;
1054         locregs = locals2regs(leaf);
1055         subsp = nlocals > locregs || !leaf;
1056         initfp = subsp || stat_tmps || func_argc > N_ARGS;
1057         sregs = (opt_lregs | stat_regs) & R_SAVED;
1058         tmp_mask = stat_regs;
1059         pass1 = 0;
1060         pass2 = 1;
1061         if (!func_varg)
1062                 for (i = 0; i < func_argc; i++)
1063                         if (i < N_ARGS && (locals[i].n_access + locals[i].n_addr) == 0)
1064                                 opt_sargs &= ~(1 << argregs[i]);
1065         i_prolog(func_argc, func_varg, opt_sargs, sregs, initfp, subsp);
1066         func_reset();
1067         for (i = 0; i < MIN(func_argc, N_ARGS); i++)
1068                 if (opt_isreg[i] && opt_lreg[i] != argregs[i])
1069                         i_mov(opt_lreg[i], argregs[i]);
1070         for (i = N_ARGS; i < func_argc; i++)
1071                 if (opt_isreg[i])
1072                         i_load(opt_lreg[i], REG_FP, locals[i].loc, LONGSZ);
1073 }
1074
1075 void o_func_end(void)
1076 {
1077         o_label(0);
1078         jmp_fill();
1079         i_epilog(sp_max);
1080 }