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 #define LOC_REG         0x01
   9 #define LOC_MEM         0x02
  10 #define LOC_NUM         0x04
  11 #define LOC_SYM         0x08
  12 #define LOC_LOCAL       0x10
  13
  14 #define NREGS           16
  15
  16 #define REG_PC          15      /* program counter */
  17 #define REG_LR          14      /* link register */
  18 #define REG_SP          13      /* stack pointer */
  19 #define REG_TMP         12      /* temporary register */
  20 #define REG_FP          11      /* frame pointer register */
  21 #define REG_DP          10      /* data pointer register */
  22 #define REG_RET         0       /* returned value register */
  23
  24 #define MIN(a, b)               ((a) < (b) ? (a) : (b))
  25 #define ALIGN(x, a)             (((x) + (a) - 1) & ~((a) - 1))
  26
  27 #define TMP_REG(t)              ((t)->loc == LOC_REG ? (t)->addr : reg_get(~0))
  28 #define TMP_REG2(t, r)          ((t)->loc == LOC_REG && (t)->addr != (r) ? \
  29                                         (t)->addr : reg_get(~(1 << (r))))
  30 #define TMP_REG3(t, r1, r2)     ((t)->loc == LOC_REG && (t)->addr != (r1) && (t)->addr != (r2) ? \
  31                                         (t)->addr : reg_get(~((1 << (r1)) | (1 << (r2)))))
  32
  33 static char cs[SECSIZE];        /* code segment */
  34 static int cslen;
  35 static char ds[SECSIZE];        /* data segment */
  36 static int dslen;
  37 static long bsslen;             /* bss segment size */
  38
  39 static int nogen;               /* don't generate code */
  40 static long sp;
  41 static long func_beg;
  42 static long maxsp;
  43
  44 #define TMP(i)          (((i) < ntmp) ? &tmps[ntmp - 1 - (i)] : NULL)
  45
  46 static struct tmp {
  47         long addr;
  48         char sym[NAMELEN];
  49         long off;       /* offset from a symbol or a local */
  50         unsigned loc;   /* variable location */
  51         unsigned bt;    /* type of address; zero when not a pointer */
  52 } tmps[MAXTMP];
  53 static int ntmp;
  54
  55 static int tmpsp;
  56
  57 static struct tmp *regs[NREGS];
  58 static int tmpregs[] = {4, 5, 6, 7, 8, 9, 0, 1, 2, 3};
  59 static int argregs[] = {0, 1, 2, 3};
  60
  61 #define I_AND           0x00
  62 #define I_EOR           0x01
  63 #define I_SUB           0x02
  64 #define I_RSB           0x03
  65 #define I_ADD           0x04
  66 #define I_TST           0x08
  67 #define I_CMP           0x0a
  68 #define I_ORR           0x0c
  69 #define I_MOV           0x0d
  70 #define I_MVN           0x0f
  71
  72 #define MAXRET                  (1 << 8)
  73
  74 static long ret[MAXRET];
  75 static int nret;
  76
  77 /* output div/mod functions */
  78 static int putdiv = 0;
  79
  80 /* for optimizing cmp + bcc */
  81 static long last_cmp = -1;
  82 static long last_set = -1;
  83 static long last_cond;
  84
  85 static void os(void *s, int n)
  86 {
  87         memcpy(cs + cslen, s, n);
  88         cslen += n;
  89 }
  90
  91 static void oi(long n)
  92 {
  93         if (nogen)
  94                 return;
  95         *(int *) (cs + cslen) = n;
  96         cslen += 4;
  97 }
  98
  99 #define MAXNUMS         1024
 100
 101 /* data pool */
 102 static long num_offs[MAXNUMS];                  /* data immediate value */
 103 static char num_names[MAXNUMS][NAMELEN];        /* relocation data symbol name */
 104 static int nums;
 105
 106 static int pool_find(char *name, int off)
 107 {
 108         int i;
 109         for (i = 0; i < nums; i++)
 110                 if (!strcmp(name, num_names[i]) && off == num_offs[i])
 111                         return i;
 112         return -1;
 113 }
 114
 115 static int pool_num(long num)
 116 {
 117         int idx = pool_find("", num);
 118         if (idx < 0) {
 119                 idx = nums++;
 120                 num_offs[idx] = num;
 121                 num_names[idx][0] = '\0';
 122         }
 123         return idx << 2;
 124 }
 125
 126 static int pool_reloc(char *name, long off)
 127 {
 128         int idx = pool_find(name, off);
 129         if (idx < 0) {
 130                 idx = nums++;
 131                 num_offs[idx] = off;
 132                 strcpy(num_names[idx], name);
 133         }
 134         return idx << 2;
 135 }
 136
 137 static void pool_write(void)
 138 {
 139         int i;
 140         for (i = 0; i < nums; i++) {
 141                 if (num_names[i])
 142                         out_rel(num_names[i], OUT_CS, cslen);
 143                 oi(num_offs[i]);
 144         }
 145 }
 146
 147 /*
 148  * data processing:
 149  * +---------------------------------------+
 150  * |COND|00|I| op |S| Rn | Rd |  operand2  |
 151  * +---------------------------------------+
 152  *
 153  * S: set condition code
 154  * Rn: first operand
 155  * Rd: destination operand
 156  *
 157  * I=0 operand2=| shift  | Rm |
 158  * I=1 operand2=|rota|  imm   |
 159  */
 160 #define ADD(op, rd, rn, s, i, cond)     \
 161         (((cond) << 28) | ((i) << 25) | ((s) << 20) | \
 162                 ((op) << 21) | ((rn) << 16) | ((rd) << 12))
 163
 164 static void i_add(int op, int rd, int rn, int rm)
 165 {
 166         oi(ADD(op, rd, rn, 0, 0, 14) | rm);
 167 }
 168
 169 static int add_encimm(unsigned n)
 170 {
 171         int i = 0;
 172         while (i < 12 && (n >> ((4 + i) << 1)))
 173                 i++;
 174         return (n >> (i << 1)) | (((16 - i) & 0x0f) << 8);
 175 }
 176
 177 static int add_decimm(unsigned n)
 178 {
 179         int rot = (16 - ((n >> 8) & 0x0f)) & 0x0f;
 180         return (n & 0xff) << (rot << 1);
 181 }
 182
 183 static int add_rndimm(unsigned n)
 184 {
 185         int rot = (n >> 8) & 0x0f;
 186         int num = n & 0xff;
 187         if (rot == 0)
 188                 return n;
 189         if (num == 0xff) {
 190                 num = 0;
 191                 rot = (rot + 12) & 0x0f;
 192         }
 193         return ((num + 1) & 0xff) | (rot << 8);
 194 }
 195
 196 static void i_ldr(int l, int rd, int rn, int off, int bt);
 197
 198 static void i_num(int rd, long n)
 199 {
 200         int neg = n < 0;
 201         int p = neg ? -n - 1 : n;
 202         int enc = add_encimm(p);
 203         if (p == add_decimm(enc)) {
 204                 oi(ADD(neg ? I_MVN : I_MOV, rd, 0, 0, 1, 14) | enc);
 205         } else {
 206                 if (!nogen) {
 207                         int off = pool_num(n);
 208                         i_ldr(1, rd, REG_DP, off, LONGSZ);
 209                 }
 210         }
 211 }
 212
 213 static void i_add_imm(int op, int rd, int rn, int n)
 214 {
 215         int neg = n < 0;
 216         int imm = add_encimm(neg ? -n : n);
 217         if (imm == add_decimm(neg ? -n : n)) {
 218                 oi(ADD(neg ? I_SUB : I_ADD, rd, rn, 0, 1, 14) | imm);
 219         } else {
 220                 i_num(rd, n);
 221                 i_add(I_ADD, rd, rd, rn);
 222         }
 223 }
 224
 225 /*
 226  * multiply
 227  * +----------------------------------------+
 228  * |COND|000000|A|S| Rd | Rn | Rs |1001| Rm |
 229  * +----------------------------------------+
 230  *
 231  * Rd: destination
 232  * A: accumulate
 233  * C: set condition codes
 234  *
 235  * I=0 operand2=| shift  | Rm |
 236  * I=1 operand2=|rota|  imm   |
 237  */
 238 #define MUL(rd, rn, rs)         \
 239         ((14 << 28) | ((rd) << 16) | ((0) << 12) | ((rn) << 8) | ((9) << 4) | (rm))
 240
 241 static void i_mul(int rd, int rn, int rm)
 242 {
 243         oi(MUL(rd, rn, rm));
 244 }
 245
 246 static void i_cmp(int op, int rn, int rm)
 247 {
 248         oi(ADD(op, 0, rn, 1, 0, 14) | rm);
 249         last_cmp = cslen;
 250 }
 251
 252 static void i_set(int cond, int rd)
 253 {
 254         last_set = cslen;
 255         last_cond = cond;
 256         oi(ADD(I_MOV, rd, 0, 0, 1, 14));
 257         oi(ADD(I_MOV, rd, 0, 0, 1, cond) | 1);
 258 }
 259
 260 #define SM_LSL          0
 261 #define SM_LSR          1
 262 #define SM_ASR          2
 263
 264 static void i_shl(int sm, int rd, int rm, int rs)
 265 {
 266         oi(ADD(I_MOV, rd, 0, 0, 0, 14) | (rs << 8) | (sm << 5) | (1 << 4) | rm);
 267 }
 268
 269 static void i_shl_imm(int sm, int rd, int n)
 270 {
 271         oi(ADD(I_MOV, rd, 0, 0, 0, 14) | (n << 7) | (sm << 5) | rd);
 272 }
 273
 274 static void i_mov(int op, int rd, int rn)
 275 {
 276         oi(ADD(op, rd, 0, 0, 0, 14) | rn);
 277 }
 278
 279 /*
 280  * single data transfer:
 281  * +------------------------------------------+
 282  * |COND|01|I|P|U|B|W|L| Rn | Rd |   offset   |
 283  * +------------------------------------------+
 284  *
 285  * I: immediate/offset
 286  * P: post/pre indexing
 287  * U: down/up
 288  * B: byte/word
 289  * W: writeback
 290  * L: store/load
 291  * Rn: base register
 292  * Rd: source/destination register
 293  *
 294  * I=0 offset=| immediate |
 295  * I=1 offset=| shift  | Rm |
 296  *
 297  * halfword and signed data transfer
 298  * +----------------------------------------------+
 299  * |COND|000|P|U|0|W|L| Rn | Rd |0000|1|S|H|1| Rm |
 300  * +----------------------------------------------+
 301  *
 302  * +----------------------------------------------+
 303  * |COND|000|P|U|1|W|L| Rn | Rd |off1|1|S|H|1|off2|
 304  * +----------------------------------------------+
 305  *
 306  * S: singed
 307  * H: halfword
 308  */
 309 #define LDR(l, rd, rn, b, u, p, w)              \
 310         ((14 << 28) | (1 << 26) | ((p) << 24) | ((b) << 22) | ((u) << 23) | \
 311         ((w) << 21) | ((l) << 20) | ((rn) << 16) | ((rd) << 12))
 312 #define LDRH(l, rd, rn, s, h, u, i)     \
 313         ((14 << 28) | (1 << 24) | ((u) << 23) | ((i) << 22) | ((l) << 20) | \
 314         ((rn) << 16) | ((rd) << 12) | ((s) << 6) | ((h) << 5) | (9 << 4))
 315
 316 static void i_ldr(int l, int rd, int rn, int off, int bt)
 317 {
 318         int b = BT_SZ(bt) == 1;
 319         int h = BT_SZ(bt) == 2;
 320         int s = l && (bt & BT_SIGNED);
 321         int half = h || (b && s);
 322         int maximm = half ? 0x100 : 0x1000;
 323         int neg = off < 0;
 324         if (neg)
 325                 off = -off;
 326         while (off >= maximm) {
 327                 int imm = add_encimm(off);
 328                 oi(ADD(neg ? I_SUB : I_ADD, rd, rn, 0, 1, 14) | imm);
 329                 rn = rd;
 330                 off -= add_decimm(imm);
 331         }
 332         if (!half)
 333                 oi(LDR(l, rd, rn, b, !neg, 1, 0) | off);
 334         else
 335                 oi(LDRH(l, rd, rn, s, h, !neg, 1) |
 336                         ((off & 0xf0) << 4) | (off & 0x0f));
 337 }
 338
 339 static void i_sym(int rd, char *sym, int off)
 340 {
 341         if (!nogen) {
 342                 int doff = pool_reloc(sym, off);
 343                 i_ldr(1, rd, REG_DP, doff, LONGSZ);
 344         }
 345 }
 346
 347 static void i_neg(int rd)
 348 {
 349         oi(ADD(I_RSB, rd, rd, 0, 1, 14));
 350 }
 351
 352 static void i_not(int rd)
 353 {
 354         oi(ADD(I_MVN, rd, 0, rd, 1, 14));
 355 }
 356
 357 static void i_lnot(int rd)
 358 {
 359         i_cmp(I_TST, rd, rd);
 360         oi(ADD(I_MOV, rd, 0, 0, 1, 14));
 361         oi(ADD(I_MOV, rd, 0, 0, 1, 0) | 1);
 362 }
 363
 364 /* rd = rd & ((1 << bits) - 1) */
 365 static void i_zx(int rd, int bits)
 366 {
 367         if (bits <= 8) {
 368                 oi(ADD(I_AND, rd, rd, 0, 1, 14) | add_encimm((1 << bits) - 1));
 369         } else {
 370                 i_shl_imm(SM_LSL, rd, 32 - bits);
 371                 i_shl_imm(SM_LSR, rd, 32 - bits);
 372         }
 373 }
 374
 375 static void i_sx(int rd, int bits)
 376 {
 377         i_shl_imm(SM_LSL, rd, 32 - bits);
 378         i_shl_imm(SM_ASR, rd, 32 - bits);
 379 }
 380
 381 /*
 382  * branch:
 383  * +-----------------------------------+
 384  * |COND|101|L|         offset         |
 385  * +-----------------------------------+
 386  *
 387  * L: link
 388  */
 389 #define BL(cond, l, o)  (((cond) << 28) | (5 << 25) | ((l) << 24) | \
 390                                 ((((o) - 8) >> 2) & 0x00ffffff))
 391
 392 static void i_b(long addr)
 393 {
 394         oi(BL(14, 0, addr - cslen));
 395 }
 396
 397 static void i_b_if(long addr, int rn, int z)
 398 {
 399         static int nots[] = {1, 0, 3, 2, -1, -1, -1, -1, 9, 8, 11, 10, 13, 12, -1};
 400         if (last_cmp + 8 != cslen || last_set != last_cmp) {
 401                 i_cmp(I_TST, rn, rn);
 402                 oi(BL(z ? 0 : 1, 0, addr - cslen));
 403                 return;
 404         }
 405         cslen = last_cmp;
 406         oi(BL(z ? nots[last_cond] : last_cond, 0, addr - cslen));
 407 }
 408
 409 static void i_b_fill(long *dst, int diff)
 410 {
 411         *dst = (*dst & 0xff000000) | (((diff - 8) >> 2) & 0x00ffffff);
 412 }
 413
 414 static void i_memcpy(int rd, int rs, int rn)
 415 {
 416         oi(ADD(I_SUB, rn, rn, 1, 1, 14) | 1);
 417         oi(BL(4, 0, 16));
 418         oi(LDR(1, REG_TMP, rs, 1, 1, 0, 0) | 1);
 419         oi(LDR(0, REG_TMP, rd, 1, 1, 0, 0) | 1);
 420         oi(BL(14, 0, -16));
 421 }
 422
 423 static void i_memset(int rd, int rs, int rn)
 424 {
 425         oi(ADD(I_SUB, rn, rn, 1, 1, 14) | 1);
 426         oi(BL(4, 0, 12));
 427         oi(LDR(0, rs, rd, 1, 1, 0, 0) | 1);
 428         oi(BL(14, 0, -12));
 429 }
 430
 431 static void i_call_reg(int rd)
 432 {
 433         i_mov(I_MOV, REG_LR, REG_PC);
 434         i_mov(I_MOV, REG_PC, rd);
 435 }
 436
 437 static void i_call(char *sym)
 438 {
 439         if (!nogen)
 440                 out_rel(sym, OUT_CS | OUT_REL24, cslen);
 441         oi(BL(14, 1, 0));
 442 }
 443
 444 static void i_prolog(void)
 445 {
 446         func_beg = cslen;
 447         nums = 0;
 448         oi(0xe1a0c00d);         /* mov   r12, sp */
 449         oi(0xe92d000f);         /* stmfd sp!, {r0-r3} */
 450         oi(0xe92d5ff0);         /* stmfd sp!, {r0-r11, r12, lr} */
 451         oi(0xe1a0b00d);         /* mov   fp, sp */
 452         oi(0xe24dd000);         /* sub   sp, sp, xx */
 453         oi(0xe28fa000);         /* add   dp, pc, xx */
 454 }
 455
 456 static void i_epilog(void)
 457 {
 458         int dpoff;
 459         oi(0xe89baff0);         /* ldmfd fp, {r4-r11, sp, pc} */
 460         dpoff = add_decimm(add_rndimm(add_encimm(cslen - func_beg - 28)));
 461         cslen = func_beg + dpoff + 28;
 462         maxsp = ALIGN(maxsp, 8);
 463         maxsp = add_decimm(add_rndimm(add_encimm(maxsp)));
 464         /* fill stack sub: sp = sp - xx */
 465         *(long *) (cs + func_beg + 16) |= add_encimm(maxsp);
 466         /* fill data ptr addition: dp = pc + xx */
 467         *(long *) (cs + func_beg + 20) |= add_encimm(dpoff);
 468         pool_write();
 469 }
 470
 471 static long sp_push(int size)
 472 {
 473         sp += size;
 474         if (sp > maxsp)
 475                 maxsp = sp;
 476         return sp;
 477 }
 478
 479 static void tmp_mem(struct tmp *tmp)
 480 {
 481         int src = tmp->addr;
 482         if (!(tmp->loc == LOC_REG))
 483                 return;
 484         if (tmpsp == -1)
 485                 tmpsp = sp;
 486         tmp->addr = -sp_push(LONGSZ);
 487         i_ldr(0, src, REG_FP, tmp->addr, LONGSZ);
 488         regs[src] = NULL;
 489         tmp->loc = LOC_MEM;
 490 }
 491
 492 static void num_cast(struct tmp *t, unsigned bt)
 493 {
 494         if (!(bt & BT_SIGNED) && BT_SZ(bt) != LONGSZ)
 495                 t->addr &= ((1l << (long) (BT_SZ(bt) * 8)) - 1);
 496         if (bt & BT_SIGNED && BT_SZ(bt) != LONGSZ &&
 497                                 t->addr > (1l << (BT_SZ(bt) * 8 - 1)))
 498                 t->addr = -((1l << (BT_SZ(bt) * 8)) - t->addr);
 499 }
 500
 501 static void tmp_reg(struct tmp *tmp, int dst, int deref)
 502 {
 503         int bt = tmp->bt;
 504         if (!tmp->bt)
 505                 deref = 0;
 506         if (deref)
 507                 tmp->bt = 0;
 508         if (tmp->loc == LOC_NUM) {
 509                 i_num(dst, tmp->addr);
 510                 tmp->addr = dst;
 511                 regs[dst] = tmp;
 512                 tmp->loc = LOC_REG;
 513         }
 514         if (tmp->loc == LOC_SYM) {
 515                 i_sym(dst, tmp->sym, tmp->off);
 516                 tmp->addr = dst;
 517                 regs[dst] = tmp;
 518                 tmp->loc = LOC_REG;
 519         }
 520         if (tmp->loc == LOC_REG) {
 521                 if (deref)
 522                         i_ldr(1, dst, tmp->addr, 0, bt);
 523                 else if (dst != tmp->addr)
 524                         i_mov(I_MOV, dst, tmp->addr);
 525                 regs[tmp->addr] = NULL;
 526         }
 527         if (tmp->loc == LOC_LOCAL) {
 528                 if (deref)
 529                         i_ldr(1, dst, REG_FP, tmp->addr + tmp->off, bt);
 530                 else
 531                         i_add_imm(I_ADD, dst, REG_FP, tmp->addr + tmp->off);
 532         }
 533         if (tmp->loc == LOC_MEM) {
 534                 i_ldr(1, dst, REG_FP, tmp->addr, LONGSZ);
 535                 if (deref)
 536                         i_ldr(1, dst, dst, 0, bt);
 537         }
 538         tmp->addr = dst;
 539         regs[dst] = tmp;
 540         tmp->loc = LOC_REG;
 541 }
 542
 543 static void reg_free(int reg)
 544 {
 545         int i;
 546         if (!regs[reg])
 547                 return;
 548         for (i = 0; i < ARRAY_SIZE(tmpregs); i++)
 549                 if (!regs[tmpregs[i]]) {
 550                         tmp_reg(regs[reg], tmpregs[i], 0);
 551                         return;
 552                 }
 553         tmp_mem(regs[reg]);
 554 }
 555
 556 static void reg_for(int reg, struct tmp *t)
 557 {
 558         if (regs[reg] && regs[reg] != t)
 559                 reg_free(reg);
 560 }
 561
 562 static void tmp_mv(struct tmp *t, int reg)
 563 {
 564         reg_for(reg, t);
 565         tmp_reg(t, reg, 0);
 566 }
 567
 568 static void tmp_to(struct tmp *t, int reg)
 569 {
 570         reg_for(reg, t);
 571         tmp_reg(t, reg, 1);
 572 }
 573
 574 static void tmp_drop(int n)
 575 {
 576         int i;
 577         for (i = ntmp - n; i < ntmp; i++)
 578                 if (tmps[i].loc == LOC_REG)
 579                         regs[tmps[i].addr] = NULL;
 580         ntmp -= n;
 581 }
 582
 583 static void tmp_pop(int reg)
 584 {
 585         struct tmp *t = TMP(0);
 586         tmp_to(t, reg);
 587         tmp_drop(1);
 588 }
 589
 590 static struct tmp *tmp_new(void)
 591 {
 592         return &tmps[ntmp++];
 593 }
 594
 595 static void tmp_push(int reg)
 596 {
 597         struct tmp *t = tmp_new();
 598         t->addr = reg;
 599         t->bt = 0;
 600         t->loc = LOC_REG;
 601         regs[reg] = t;
 602 }
 603
 604 void o_local(long addr)
 605 {
 606         struct tmp *t = tmp_new();
 607         t->addr = -addr;
 608         t->loc = LOC_LOCAL;
 609         t->bt = 0;
 610         t->off = 0;
 611 }
 612
 613 void o_num(long num)
 614 {
 615         struct tmp *t = tmp_new();
 616         t->addr = num;
 617         t->bt = 0;
 618         t->loc = LOC_NUM;
 619 }
 620
 621 void o_sym(char *name)
 622 {
 623         struct tmp *t = tmp_new();
 624         strcpy(t->sym, name);
 625         t->loc = LOC_SYM;
 626         t->bt = 0;
 627         t->off = 0;
 628 }
 629
 630 void o_tmpdrop(int n)
 631 {
 632         if (n == -1 || n > ntmp)
 633                 n = ntmp;
 634         tmp_drop(n);
 635         if (!ntmp) {
 636                 if (tmpsp != -1)
 637                         sp = tmpsp;
 638                 tmpsp = -1;
 639         }
 640 }
 641
 642 #define FORK_REG                0x00
 643
 644 /* make sure tmps remain intact after a conditional expression */
 645 void o_fork(void)
 646 {
 647         int i;
 648         for (i = 0; i < ntmp - 1; i++)
 649                 tmp_mem(&tmps[i]);
 650 }
 651
 652 void o_forkpush(void)
 653 {
 654         tmp_pop(FORK_REG);
 655 }
 656
 657 void o_forkjoin(void)
 658 {
 659         tmp_push(FORK_REG);
 660 }
 661
 662 void o_tmpswap(void)
 663 {
 664         struct tmp *t1 = TMP(0);
 665         struct tmp *t2 = TMP(1);
 666         struct tmp t;
 667         memcpy(&t, t1, sizeof(t));
 668         memcpy(t1, t2, sizeof(t));
 669         memcpy(t2, &t, sizeof(t));
 670         if (t1->loc == LOC_REG)
 671                 regs[t1->addr] = t1;
 672         if (t2->loc == LOC_REG)
 673                 regs[t2->addr] = t2;
 674 }
 675
 676 static int reg_get(int mask)
 677 {
 678         int i;
 679         for (i = 0; i < ARRAY_SIZE(tmpregs); i++)
 680                 if ((1 << tmpregs[i]) & mask && !regs[tmpregs[i]])
 681                         return tmpregs[i];
 682         for (i = 0; i < ARRAY_SIZE(tmpregs); i++)
 683                 if ((1 << tmpregs[i]) & mask) {
 684                         reg_free(tmpregs[i]);
 685                         return tmpregs[i];
 686                 }
 687         return 0;
 688 }
 689
 690 static void tmp_copy(struct tmp *t1)
 691 {
 692         struct tmp *t2 = tmp_new();
 693         memcpy(t2, t1, sizeof(*t1));
 694         if (!(t1->loc & (LOC_REG | LOC_MEM)))
 695                 return;
 696         if (t1->loc == LOC_MEM) {
 697                 tmp_mv(t2, reg_get(~0));
 698         } else if (t1->loc == LOC_REG) {
 699                 t2->addr = TMP_REG2(t2, t1->addr);
 700                 i_mov(I_MOV, t2->addr, t1->addr);
 701                 regs[t2->addr] = t2;
 702         }
 703 }
 704
 705 void o_tmpcopy(void)
 706 {
 707         tmp_copy(TMP(0));
 708 }
 709
 710 void o_cast(unsigned bt)
 711 {
 712         struct tmp *t = TMP(0);
 713         if (t->bt) {
 714                 t->bt = bt;
 715                 return;
 716         }
 717         if (t->loc == LOC_NUM) {
 718                 num_cast(t, bt);
 719                 return;
 720         }
 721         if (BT_SZ(bt) != LONGSZ) {
 722                 int reg = TMP_REG(t);
 723                 tmp_to(t, reg);
 724                 if (bt & BT_SIGNED)
 725                         i_sx(reg, BT_SZ(bt) * 8);
 726                 else
 727                         i_zx(reg, BT_SZ(bt) * 8);
 728         }
 729 }
 730
 731 void o_func_beg(char *name, int global)
 732 {
 733         out_sym(name, (global ? OUT_GLOB : 0) | OUT_CS, cslen, 0);
 734         i_prolog();
 735         sp = 0;
 736         maxsp = sp;
 737         ntmp = 0;
 738         tmpsp = -1;
 739         nret = 0;
 740         memset(regs, 0, sizeof(regs));
 741 }
 742
 743 void o_deref(unsigned bt)
 744 {
 745         struct tmp *t = TMP(0);
 746         if (t->bt)
 747                 tmp_to(t, TMP_REG(t));
 748         t->bt = bt;
 749 }
 750
 751 void o_load(void)
 752 {
 753         struct tmp *t = TMP(0);
 754         tmp_to(t, TMP_REG(t));
 755 }
 756
 757 #define TMP_NUM(t)      ((t)->loc == LOC_NUM && !(t)->bt)
 758 #define LOCAL_PTR(t)    ((t)->loc == LOC_LOCAL && !(t)->bt)
 759 #define SYM_PTR(t)      ((t)->loc == LOC_SYM && !(t)->bt)
 760
 761 int o_popnum(long *c)
 762 {
 763         struct tmp *t = TMP(0);
 764         if (!TMP_NUM(t))
 765                 return 1;
 766         *c = t->addr;
 767         tmp_drop(1);
 768         return 0;
 769 }
 770
 771 void o_ret(int rets)
 772 {
 773         if (rets)
 774                 tmp_pop(REG_RET);
 775         else
 776                 i_num(REG_RET, 0);
 777         ret[nret++] = o_jmp(0);
 778 }
 779
 780 void o_func_end(void)
 781 {
 782         int i;
 783         if (nret && ret[nret - 1] == cslen - 4) {
 784                 cslen -= 4;
 785                 nret--;
 786         }
 787         for (i = 0; i < nret; i++)
 788                 o_filljmp(ret[i]);
 789         i_epilog();
 790 }
 791
 792 long o_mklocal(int size)
 793 {
 794         return sp_push(ALIGN(size, LONGSZ));
 795 }
 796
 797 void o_rmlocal(long addr, int sz)
 798 {
 799         sp = addr - sz;
 800 }
 801
 802 long o_arg(int i)
 803 {
 804         return -(10 + i) << 2;
 805 }
 806
 807 void o_assign(unsigned bt)
 808 {
 809         struct tmp *t1 = TMP(0);
 810         struct tmp *t2 = TMP(1);
 811         int r1 = TMP_REG(t1);
 812         int r2 = TMP_REG2(t2, r1);
 813         int off = 0;
 814         tmp_to(t1, r1);
 815         if (t2->bt)
 816                 tmp_to(t2, r2);
 817         if (t2->loc == LOC_LOCAL) {
 818                 r2 = REG_FP;
 819                 off = t2->addr + t2->off;
 820         } else {
 821                 tmp_to(t2, r2);
 822         }
 823         tmp_drop(2);
 824         i_ldr(0, r1, r2, off, bt);
 825         tmp_push(r1);
 826 }
 827
 828 static long cu(int op, long i)
 829 {
 830         switch (op & 0xff) {
 831         case O_NEG:
 832                 return -i;
 833         case O_NOT:
 834                 return ~i;
 835         case O_LNOT:
 836                 return !i;
 837         }
 838         return 0;
 839 }
 840
 841 static int c_uop(int op)
 842 {
 843         struct tmp *t1 = TMP(0);
 844         if (!TMP_NUM(t1))
 845                 return 1;
 846         tmp_drop(1);
 847         o_num(cu(op, t1->addr));
 848         return 0;
 849 }
 850
 851 static long cb(int op, long a, long b)
 852 {
 853         switch (op & 0xff) {
 854         case O_ADD:
 855                 return a + b;
 856         case O_SUB:
 857                 return a - b;
 858         case O_AND:
 859                 return a & b;
 860         case O_OR:
 861                 return a | b;
 862         case O_XOR:
 863                 return a ^ b;
 864         case O_MUL:
 865                 return a * b;
 866         case O_DIV:
 867                 return a / b;
 868         case O_MOD:
 869                 return a % b;
 870         case O_SHL:
 871                 return a << b;
 872         case O_SHR:
 873                 if (op & O_SIGNED)
 874                         return a >> b;
 875                 else
 876                         return (unsigned long) a >> b;
 877         case O_LT:
 878                 return a < b;
 879         case O_GT:
 880                 return a > b;
 881         case O_LE:
 882                 return a <= b;
 883         case O_GE:
 884                 return a >= b;
 885         case O_EQ:
 886                 return a == b;
 887         case O_NEQ:
 888                 return a != b;
 889         }
 890         return 0;
 891 }
 892
 893 static int c_bop(int op)
 894 {
 895         struct tmp *t1 = TMP(0);
 896         struct tmp *t2 = TMP(1);
 897         int locals = LOCAL_PTR(t1) + LOCAL_PTR(t2);
 898         int syms = SYM_PTR(t1) + SYM_PTR(t2);
 899         int nums = TMP_NUM(t1) + TMP_NUM(t2);
 900         if (syms + locals == 2 || syms + nums + locals != 2)
 901                 return 1;
 902         if (nums == 1)
 903                 if ((op & 0xff) != O_ADD && ((op & 0xff) != O_SUB || TMP_NUM(t2)))
 904                         return 1;
 905         if (nums == 1) {
 906                 long o1 = TMP_NUM(t1) ? t1->addr : t1->off;
 907                 long o2 = TMP_NUM(t2) ? t2->addr : t2->off;
 908                 long ret = cb(op, o2, o1);
 909                 if (!TMP_NUM(t1))
 910                         o_tmpswap();
 911                 t2->off = ret;
 912                 tmp_drop(1);
 913         } else {
 914                 long ret = cb(op, t2->addr, t1->addr);
 915                 tmp_drop(2);
 916                 o_num(ret);
 917         }
 918         return 0;
 919 }
 920
 921 void o_uop(int op)
 922 {
 923         int r1 = TMP_REG(TMP(0));
 924         if (!c_uop(op))
 925                 return;
 926         tmp_to(TMP(0), r1);
 927         switch (op & 0xff) {
 928         case O_NEG:
 929                 i_neg(r1);
 930                 break;
 931         case O_NOT:
 932                 i_not(r1);
 933                 break;
 934         case O_LNOT:
 935                 i_lnot(r1);
 936                 break;
 937         }
 938 }
 939
 940 static void bin_regs(int *r1, int *r2)
 941 {
 942         struct tmp *t2 = TMP(0);
 943         struct tmp *t1 = TMP(1);
 944         *r2 = TMP_REG(t2);
 945         tmp_to(t2, *r2);
 946         *r1 = TMP_REG2(t1, *r2);
 947         tmp_pop(*r2);
 948         tmp_pop(*r1);
 949 }
 950
 951 static void bin_add(int op)
 952 {
 953         /* opcode for O_ADD, O_SUB, O_AND, O_OR, O_XOR */
 954         static int rx[] = {I_ADD, I_SUB, I_AND, I_ORR, I_EOR};
 955         int r1, r2;
 956         bin_regs(&r1, &r2);
 957         i_add(rx[op & 0x0f], r1, r1, r2);
 958         tmp_push(r1);
 959 }
 960
 961 static void bin_shx(int op)
 962 {
 963         int sm = SM_LSL;
 964         int r1, r2;
 965         bin_regs(&r1, &r2);
 966         if ((op & 0x0f) == 1)
 967                 sm = op & O_SIGNED ? SM_ASR : SM_LSR;
 968         i_shl(sm, r1, r1, r2);
 969         tmp_push(r1);
 970 }
 971
 972 static int log2a(unsigned long n)
 973 {
 974         int i = 0;
 975         for (i = 0; i < LONGSZ * 8; i++)
 976                 if (n & (1u << i))
 977                         break;
 978         if (i == LONGSZ * 8 || !(n >> (i + 1)))
 979                 return i;
 980         return -1;
 981 }
 982
 983 /* optimized version of mul/div/mod for powers of two */
 984 static int mul_2(int op)
 985 {
 986         struct tmp *t1 = TMP(0);
 987         struct tmp *t2 = TMP(1);
 988         long n;
 989         int r2;
 990         int p;
 991         if ((op & 0xff) == O_MUL && t2->loc == LOC_NUM && !t2->bt)
 992                 o_tmpswap();
 993         if (t1->loc != LOC_NUM || t1->bt)
 994                 return 1;
 995         n = t1->addr;
 996         p = log2a(n);
 997         if (n && p == -1)
 998                 return 1;
 999         if ((op & 0xff) == O_MUL) {
1000                 tmp_drop(1);
1001                 if (n == 1)
1002                         return 0;
1003                 if (n == 0) {
1004                         tmp_drop(1);
1005                         o_num(0);
1006                         return 0;
1007                 }
1008                 r2 = TMP_REG(t2);
1009                 tmp_to(t2, r2);
1010                 i_shl_imm(SM_LSL, r2, p);
1011                 return 0;
1012         }
1013         if (op == O_DIV) {
1014                 tmp_drop(1);
1015                 if (n == 1)
1016                         return 0;
1017                 r2 = TMP_REG(t2);
1018                 tmp_to(t2, r2);
1019                 i_shl_imm(op & O_SIGNED ? SM_ASR : SM_LSR, r2, p);
1020                 return 0;
1021         }
1022         if (op == O_MOD) {
1023                 tmp_drop(1);
1024                 if (n == 1) {
1025                         tmp_drop(1);
1026                         o_num(0);
1027                         return 0;
1028                 }
1029                 r2 = TMP_REG(t2);
1030                 tmp_to(t2, r2);
1031                 i_zx(r2, p);
1032                 return 0;
1033         }
1034         return 1;
1035 }
1036
1037 static void bin_div(int op)
1038 {
1039         struct tmp *t2 = TMP(0);
1040         struct tmp *t1 = TMP(1);
1041         char *func;
1042         int i;
1043         putdiv = 1;
1044         if ((op & 0xff) == O_DIV)
1045                 func = op & O_SIGNED ? "__divdi3" : "__udivdi3";
1046         else
1047                 func = op & O_SIGNED ? "__moddi3" : "__umoddi3";
1048         for (i = 0; i < ARRAY_SIZE(argregs); i++)
1049                 if (regs[argregs[i]] && regs[argregs[i]] - tmps < ntmp - 2)
1050                         tmp_mem(regs[argregs[i]]);
1051         tmp_to(t1, argregs[0]);
1052         tmp_to(t2, argregs[1]);
1053         tmp_drop(2);
1054         i_call(func);
1055         tmp_push(REG_RET);
1056 }
1057
1058 static void bin_mul(int op)
1059 {
1060         int r1, r2;
1061         if (!mul_2(op))
1062                 return;
1063         if ((op & 0xff) == O_DIV || (op & 0xff) == O_MOD) {
1064                 bin_div(op);
1065         } else {
1066                 bin_regs(&r1, &r2);
1067                 i_mul(r1, r1, r2);
1068                 tmp_push(r1);
1069         }
1070 }
1071
1072 static void bin_cmp(int op)
1073 {
1074         /* lt, gt, le, ge, eq, neq */
1075         static int ucond[] = {3, 8, 9, 2, 0, 1};
1076         static int scond[] = {11, 12, 13, 10, 0, 1};
1077         int r1, r2;
1078         bin_regs(&r1, &r2);
1079         i_cmp(I_CMP, r1, r2);
1080         i_set(op & O_SIGNED ? scond[op & 0x0f] : ucond[op & 0x0f], r1);
1081         tmp_push(r1);
1082 }
1083
1084 void o_bop(int op)
1085 {
1086         if (!c_bop(op))
1087                 return;
1088         if ((op & 0xf0) == 0x00)
1089                 bin_add(op);
1090         if ((op & 0xf0) == 0x10)
1091                 bin_shx(op);
1092         if ((op & 0xf0) == 0x20)
1093                 bin_mul(op);
1094         if ((op & 0xf0) == 0x30)
1095                 bin_cmp(op);
1096 }
1097
1098 static void load_regs2(int *r0, int *r1, int *r2)
1099 {
1100         struct tmp *t0 = TMP(0);
1101         struct tmp *t1 = TMP(1);
1102         struct tmp *t2 = TMP(2);
1103         *r0 = TMP_REG(t0);
1104         *r1 = TMP_REG2(t1, *r0);
1105         *r2 = TMP_REG3(t2, *r0, *r1);
1106         tmp_to(t0, *r0);
1107         tmp_to(t1, *r1);
1108         tmp_to(t2, *r2);
1109 }
1110
1111 void o_memcpy(void)
1112 {
1113         int rd, rs, rn;
1114         load_regs2(&rn, &rs, &rd);
1115         i_memcpy(rd, rs, rn);
1116         tmp_drop(2);
1117 }
1118
1119 void o_memset(void)
1120 {
1121         int rd, rs, rn;
1122         load_regs2(&rn, &rs, &rd);
1123         i_memset(rd, rs, rn);
1124         tmp_drop(2);
1125 }
1126
1127 long o_mklabel(void)
1128 {
1129         return cslen;
1130 }
1131
1132 static long jxz(long addr, int z)
1133 {
1134         int r = TMP_REG(TMP(0));
1135         tmp_pop(r);
1136         i_b_if(addr, r, z);
1137         return cslen - 4;
1138 }
1139
1140 long o_jz(long addr)
1141 {
1142         return jxz(addr, 1);
1143 }
1144
1145 long o_jnz(long addr)
1146 {
1147         return jxz(addr, 0);
1148 }
1149
1150 long o_jmp(long addr)
1151 {
1152         i_b(addr);
1153         return cslen - 4;
1154 }
1155
1156 void o_filljmp2(long addr, long jmpdst)
1157 {
1158         i_b_fill((void *) cs + addr, jmpdst - addr);
1159 }
1160
1161 void o_filljmp(long addr)
1162 {
1163         o_filljmp2(addr, cslen);
1164 }
1165
1166 void o_call(int argc, int rets)
1167 {
1168         struct tmp *t;
1169         int i;
1170         int aregs = MIN(ARRAY_SIZE(argregs), argc);
1171         for (i = 0; i < ARRAY_SIZE(argregs); i++)
1172                 if (regs[argregs[i]] && regs[argregs[i]] - tmps < ntmp - argc)
1173                         tmp_mem(regs[argregs[i]]);
1174         if (argc > aregs) {
1175                 sp_push(LONGSZ * (argc - aregs));
1176                 for (i = argc - 1; i >= aregs; --i) {
1177                         int reg = TMP_REG(TMP(0));
1178                         tmp_pop(reg);
1179                         i_ldr(0, reg, REG_SP, (i - aregs) * LONGSZ, LONGSZ);
1180                 }
1181         }
1182         for (i = aregs - 1; i >= 0; --i)
1183                 tmp_to(TMP(aregs - i - 1), argregs[i]);
1184         tmp_drop(aregs);
1185         t = TMP(0);
1186         if (t->loc == LOC_SYM && !t->bt) {
1187                 i_call(t->sym);
1188                 tmp_drop(1);
1189         } else {
1190                 int reg = t->loc == LOC_REG ? t->addr : REG_TMP;
1191                 tmp_pop(reg);
1192                 i_call_reg(reg);
1193         }
1194         if (rets)
1195                 tmp_push(REG_RET);
1196 }
1197
1198 void o_nogen(void)
1199 {
1200         nogen++;
1201 }
1202
1203 void o_dogen(void)
1204 {
1205         nogen--;
1206 }
1207
1208 void dat_bss(char *name, int size, int global)
1209 {
1210         out_sym(name, OUT_BSS | (global ? OUT_GLOB : 0), bsslen, size);
1211         bsslen += ALIGN(size, LONGSZ);
1212 }
1213
1214 #define MAXDATS         (1 << 10)
1215 static char dat_names[MAXDATS][NAMELEN];
1216 static int dat_offs[MAXDATS];
1217 static int ndats;
1218
1219 void err(char *msg);
1220 void *dat_dat(char *name, int size, int global)
1221 {
1222         void *addr = ds + dslen;
1223         int idx = ndats++;
1224         if (idx >= MAXDATS)
1225                 err("nomem: MAXDATS reached!\n");
1226         strcpy(dat_names[idx], name);
1227         dat_offs[idx] = dslen;
1228         out_sym(name, OUT_DS | (global ? OUT_GLOB : 0), dslen, size);
1229         dslen += ALIGN(size, LONGSZ);
1230         return addr;
1231 }
1232
1233 static int dat_off(char *name)
1234 {
1235         int i;
1236         for (i = 0; i < ndats; i++)
1237                 if (!strcmp(name, dat_names[i]))
1238                         return dat_offs[i];
1239         return 0;
1240 }
1241
1242 void o_datset(char *name, int off, unsigned bt)
1243 {
1244         struct tmp *t = TMP(0);
1245         int sym_off = dat_off(name) + off;
1246         if (t->loc == LOC_NUM && !t->bt) {
1247                 num_cast(t, bt);
1248                 memcpy(ds + sym_off, &t->addr, BT_SZ(bt));
1249         }
1250         if (t->loc == LOC_SYM && !t->bt) {
1251                 out_rel(t->sym, OUT_DS, sym_off);
1252                 memcpy(ds + sym_off, &t->off, BT_SZ(bt));
1253         }
1254         tmp_drop(1);
1255 }
1256
1257 /* compiled division functions; div.s contains the source */
1258 static int udivdi3[] = {
1259         0xe3a02000, 0xe3a03000, 0xe1110001, 0x0a00000a,
1260         0xe1b0c211, 0xe2822001, 0x5afffffc, 0xe3a0c001,
1261         0xe2522001, 0x4a000004, 0xe1500211, 0x3afffffb,
1262         0xe0400211, 0xe083321c, 0xeafffff8, 0xe1a01000,
1263         0xe1a00003, 0xe1a0f00e,
1264 };
1265 static int umoddi3[] = {
1266         0xe92d4000, 0xebffffeb, 0xe1a00001, 0xe8bd8000,
1267 };
1268 static int divdi3[] = {
1269         0xe92d4030, 0xe1a04000, 0xe1a05001, 0xe1100000,
1270         0x42600000, 0xe1110001, 0x42611000, 0xebffffe1,
1271         0xe1340005, 0x42600000, 0xe1140004, 0x42611000,
1272         0xe8bd8030,
1273 };
1274 static int moddi3[] = {
1275         0xe92d4000, 0xebfffff0, 0xe1a00001, 0xe8bd8000,
1276 };
1277
1278 void o_write(int fd)
1279 {
1280         if (putdiv) {
1281                 out_sym("__udivdi3", OUT_CS, cslen, 0);
1282                 os(udivdi3, sizeof(udivdi3));
1283                 out_sym("__umoddi3", OUT_CS, cslen, 0);
1284                 os(umoddi3, sizeof(umoddi3));
1285                 out_sym("__divdi3", OUT_CS, cslen, 0);
1286                 os(divdi3, sizeof(divdi3));
1287                 out_sym("__moddi3", OUT_CS, cslen, 0);
1288                 os(moddi3, sizeof(moddi3));
1289         }
1290         out_write(fd, cs, cslen, ds, dslen);
1291 }