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