int.c

   1 /* neatcc intermediate code generation */
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include "ncc.h"
   6
   7 static struct ic *ic;           /* intermediate code */
   8 static long ic_n, ic_sz;        /* number of instructions in ic[] */
   9 static long iv[NTMPS];          /* operand stack */
  10 static long iv_n;               /* number of values in iv[] */
  11 static long *lab_loc;           /* label locations */
  12 static long lab_n, lab_sz;      /* number of labels in lab_loc[] */
  13 static long lab_last;           /* the last label target */
  14
  15 static int io_num(void);
  16 static int io_mul2(void);
  17 static int io_cmp(void);
  18 static int io_jmp(void);
  19 static int io_addr(void);
  20 static int io_loc(void);
  21 static int io_imm(void);
  22 static int io_call(void);
  23
  24 static struct ic *ic_new(void)
  25 {
  26         if (ic_n == ic_sz) {
  27                 ic_sz = MAX(128, ic_sz * 2);
  28                 ic = mextend(ic, ic_n, ic_sz, sizeof(*ic));
  29         }
  30         return &ic[ic_n++];
  31 }
  32
  33 static struct ic *ic_put(long op, long arg0, long arg1, long arg2)
  34 {
  35         struct ic *c = ic_new();
  36         c->op = op;
  37         c->arg0 = arg0;
  38         c->arg1 = arg1;
  39         c->arg2 = arg2;
  40         return c;
  41 }
  42
  43 static void ic_back(long pos)
  44 {
  45         int i;
  46         for (i = pos; i < ic_n; i++)
  47                 if (ic[i].op & O_CALL)
  48                         free(ic[i].args);
  49         ic_n = pos;
  50 }
  51
  52 static long iv_pop(void)
  53 {
  54         return iv[--iv_n];
  55 }
  56
  57 static long iv_get(int n)
  58 {
  59         return iv[iv_n - n - 1];
  60 }
  61
  62 static long iv_new(void)
  63 {
  64         iv[iv_n] = ic_n;
  65         return iv[iv_n++];
  66 }
  67
  68 static void iv_put(long n)
  69 {
  70         iv[iv_n++] = n;
  71 }
  72
  73 static void iv_drop(int n)
  74 {
  75         iv_n = MAX(0, iv_n - n);
  76 }
  77
  78 static void iv_swap(int x, int y)
  79 {
  80         long v = iv[iv_n - x - 1];
  81         iv[iv_n - x - 1] = iv[iv_n - y - 1];
  82         iv[iv_n - y - 1] = v;
  83 }
  84
  85 static void iv_dup(void)
  86 {
  87         iv[iv_n] = iv[iv_n - 1];
  88         iv_n++;
  89 }
  90
  91 void o_num(long n)
  92 {
  93         ic_put(O_MOV | O_NUM, iv_new(), n, 0);
  94 }
  95
  96 void o_local(long id)
  97 {
  98         ic_put(O_MOV | O_LOC, iv_new(), id, 0);
  99 }
 100
 101 void o_sym(char *sym)
 102 {
 103         ic_put(O_MOV | O_SYM, iv_new(), out_sym(sym), 0);
 104 }
 105
 106 void o_tmpdrop(int n)
 107 {
 108         iv_drop(n >= 0 ? n : iv_n);
 109 }
 110
 111 void o_tmpswap(void)
 112 {
 113         iv_swap(0, 1);
 114 }
 115
 116 void o_tmpcopy(void)
 117 {
 118         iv_dup();
 119 }
 120
 121 void o_bop(long op)
 122 {
 123         int r1 = iv_pop();
 124         int r2 = iv_pop();
 125         ic_put(op, iv_new(), r2, r1);
 126         io_num() && io_mul2() && io_imm() && io_addr();
 127 }
 128
 129 void o_uop(long op)
 130 {
 131         int r1 = iv_pop();
 132         ic_put(op, iv_new(), r1, 0);
 133         if (io_num())
 134                 io_cmp();
 135 }
 136
 137 void o_assign(long bt)
 138 {
 139         ic_put(O_MK(O_ST | O_NUM, bt), iv_get(0), iv_get(1), 0);
 140         iv_swap(0, 1);
 141         iv_pop();
 142         io_loc();
 143 }
 144
 145 void o_deref(long bt)
 146 {
 147         int r1 = iv_pop();
 148         ic_put(O_MK(O_LD | O_NUM, bt), iv_new(), r1, 0);
 149         io_loc();
 150 }
 151
 152 void o_cast(long bt)
 153 {
 154         if (T_SZ(bt) != ULNG) {
 155                 int r1 = iv_pop();
 156                 ic_put(O_MK(O_MOV, bt), iv_new(), r1, 0);
 157                 io_num();
 158         }
 159 }
 160
 161 void o_memcpy(void)
 162 {
 163         int r2 = iv_pop();
 164         int r1 = iv_pop();
 165         int r0 = iv_pop();
 166         ic_put(O_MCPY, r0, r1, r2);
 167 }
 168
 169 void o_memset(void)
 170 {
 171         int r2 = iv_pop();
 172         int r1 = iv_pop();
 173         int r0 = iv_pop();
 174         ic_put(O_MSET, r0, r1, r2);
 175 }
 176
 177 void o_call(int argc, int ret)
 178 {
 179         struct ic *c;
 180         long *args = malloc(argc * sizeof(c->args[0]));
 181         int r1, i;
 182         for (i = argc - 1; i >= 0; --i)
 183                 args[i] = iv_pop();
 184         r1 = iv_pop();
 185         c = ic_put(O_CALL, iv_new(), r1, argc);
 186         c->args = args;
 187         iv_drop(ret == 0);
 188         io_call();
 189 }
 190
 191 void o_ret(int ret)
 192 {
 193         if (!ret)
 194                 o_num(0);
 195         ic_put(O_RET, iv_pop(), 0, 0);
 196 }
 197
 198 void o_label(long id)
 199 {
 200         while (id >= lab_sz) {
 201                 lab_sz = MAX(128, lab_sz * 2);
 202                 lab_loc = mextend(lab_loc, lab_n, lab_sz, sizeof(*lab_loc));
 203         }
 204         while (lab_n <= id)
 205                 lab_loc[lab_n++] = -1;
 206         lab_loc[id] = ic_n;
 207         lab_last = ic_n;
 208 }
 209
 210 void o_jmp(long id)
 211 {
 212         ic_put(O_JMP, 0, 0, id);
 213 }
 214
 215 void o_jz(long id)
 216 {
 217         ic_put(O_JZ, iv_pop(), 0, id);
 218         io_jmp();
 219 }
 220
 221 int o_popnum(long *n)
 222 {
 223         if (ic_num(ic, iv_get(0), n))
 224                 return 1;
 225         iv_drop(1);
 226         return 0;
 227 }
 228
 229 int o_popsym(long *sym, long *off)
 230 {
 231         if (ic_sym(ic, iv_get(0), sym, off))
 232                 return 1;
 233         iv_drop(1);
 234         return 0;
 235 }
 236
 237 long o_mark(void)
 238 {
 239         return ic_n;
 240 }
 241
 242 void o_back(long mark)
 243 {
 244         ic_back(mark);
 245 }
 246
 247 void ic_get(struct ic **c, long *n)
 248 {
 249         int i;
 250         if (!ic_n || ~ic[ic_n - 1].op & O_RET || lab_last == ic_n)
 251                 o_ret(0);
 252         /* filling jump destinations */
 253         for (i = 0; i < ic_n; i++)
 254                 if (ic[i].op & O_JXX)
 255                         ic[i].arg2 = lab_loc[ic[i].arg2];
 256         *c = ic;
 257         *n = ic_n;
 258         ic = NULL;
 259         ic_n = 0;
 260         ic_sz = 0;
 261         iv_n = 0;
 262         free(lab_loc);
 263         lab_loc = NULL;
 264         lab_n = 0;
 265         lab_sz = 0;
 266         lab_last = 0;
 267 }
 268
 269 /* intermediate code queries */
 270
 271 static long cb(long op, long a, long b)
 272 {
 273         switch (O_C(op)) {
 274         case O_ADD:
 275                 return a + b;
 276         case O_SUB:
 277                 return a - b;
 278         case O_AND:
 279                 return a & b;
 280         case O_OR:
 281                 return a | b;
 282         case O_XOR:
 283                 return a ^ b;
 284         case O_MUL:
 285                 return a * b;
 286         case O_DIV:
 287                 return a / b;
 288         case O_MOD:
 289                 return a % b;
 290         case O_SHL:
 291                 return a << b;
 292         case O_SHR:
 293                 return O_T(op) & T_MSIGN ? a >> b : (unsigned long) a >> b;
 294         case O_LT:
 295                 return a < b;
 296         case O_GT:
 297                 return a > b;
 298         case O_LE:
 299                 return a <= b;
 300         case O_GE:
 301                 return a >= b;
 302         case O_EQ:
 303                 return a == b;
 304         case O_NE:
 305                 return a != b;
 306         }
 307         return 0;
 308 }
 309
 310 static long cu(int op, long i)
 311 {
 312         switch (O_C(op)) {
 313         case O_NEG:
 314                 return -i;
 315         case O_NOT:
 316                 return ~i;
 317         case O_LNOT:
 318                 return !i;
 319         }
 320         return 0;
 321 }
 322
 323 static long c_cast(long n, unsigned bt)
 324 {
 325         if (!(bt & T_MSIGN) && T_SZ(bt) != ULNG)
 326                 n &= ((1l << (long) (T_SZ(bt) * 8)) - 1);
 327         if (bt & T_MSIGN && T_SZ(bt) != ULNG &&
 328                                 n > (1l << (T_SZ(bt) * 8 - 1)))
 329                 n = -((1l << (T_SZ(bt) * 8)) - n);
 330         return n;
 331 }
 332
 333 int ic_num(struct ic *ic, long iv, long *n)
 334 {
 335         long n1, n2;
 336         long oc = O_C(ic[iv].op);
 337         long bt = O_T(ic[iv].op);
 338         if (oc & O_MOV && oc & O_NUM) {
 339                 *n = ic[iv].arg1;
 340                 return 0;
 341         }
 342         if (oc & O_BOP) {
 343                 if (ic_num(ic, ic[iv].arg1, &n1))
 344                         return 1;
 345                 if (ic_num(ic, ic[iv].arg2, &n2))
 346                         return 1;
 347                 *n = cb(ic[iv].op, n1, n2);
 348                 return 0;
 349         }
 350         if (oc & O_UOP) {
 351                 if (ic_num(ic, ic[iv].arg1, &n1))
 352                         return 1;
 353                 *n = cu(ic[iv].op, n1);
 354                 return 0;
 355         }
 356         if (oc & O_MOV && !(oc & (O_NUM | O_LOC | O_SYM))) {
 357                 if (ic_num(ic, ic[iv].arg1, &n1))
 358                         return 1;
 359                 *n = c_cast(n1, bt);
 360                 return 0;
 361         }
 362         return 1;
 363 }
 364
 365 int ic_sym(struct ic *ic, long iv, long *sym, long *off)
 366 {
 367         long n;
 368         long oc = O_C(ic[iv].op);
 369         if (oc & O_MOV && oc & O_SYM) {
 370                 *sym = ic[iv].arg1;
 371                 *off = ic[iv].arg2;
 372                 return 0;
 373         }
 374         if (oc == O_ADD) {
 375                 if ((ic_sym(ic, ic[iv].arg1, sym, off) ||
 376                                 ic_num(ic, ic[iv].arg2, &n)) &&
 377                         (ic_sym(ic, ic[iv].arg2, sym, off) ||
 378                                 ic_num(ic, ic[iv].arg1, &n)))
 379                         return 1;
 380                 *off += n;
 381                 return 0;
 382         }
 383         if (oc == O_SUB) {
 384                 if (ic_sym(ic, ic[iv].arg1, sym, off) ||
 385                                 ic_num(ic, ic[iv].arg2, &n))
 386                         return 1;
 387                 *off -= n;
 388                 return 0;
 389         }
 390         return 1;
 391 }
 392
 393 static int ic_off(struct ic *ic, long iv, long *base_iv, long *off)
 394 {
 395         long n;
 396         long oc = O_C(ic[iv].op);
 397         if (oc != O_ADD && oc != O_SUB) {
 398                 *base_iv = iv;
 399                 *off = 0;
 400                 return 0;
 401         }
 402         if (oc == O_ADD) {
 403                 if ((ic_off(ic, ic[iv].arg1, base_iv, off) ||
 404                                 ic_num(ic, ic[iv].arg2, &n)) &&
 405                         (ic_off(ic, ic[iv].arg2, base_iv, off) ||
 406                                 ic_num(ic, ic[iv].arg1, &n)))
 407                         return 1;
 408                 *off += n;
 409                 return 0;
 410         }
 411         if (oc == O_SUB) {
 412                 if (ic_off(ic, ic[iv].arg1, base_iv, off) ||
 413                                 ic_num(ic, ic[iv].arg2, &n))
 414                         return 1;
 415                 *off -= n;
 416                 return 0;
 417         }
 418         return 1;
 419 }
 420
 421 /* intermediate code optimisations */
 422
 423 /* constant folding */
 424 static int io_num(void)
 425 {
 426         long n;
 427         if (!ic_num(ic, iv_get(0), &n)) {
 428                 iv_drop(1);
 429                 o_num(n);
 430                 return 0;
 431         }
 432         return 1;
 433 }
 434
 435 static int log2a(unsigned long n)
 436 {
 437         int i = 0;
 438         for (i = 0; i < LONGSZ * 8; i++)
 439                 if (n & (1u << i))
 440                         break;
 441         if (i == LONGSZ * 8 || !(n >> (i + 1)))
 442                 return i;
 443         return -1;
 444 }
 445
 446 static long iv_num(long n)
 447 {
 448         o_num(n);
 449         return iv_pop();
 450 }
 451
 452 /* optimised multiplication operations for powers of two */
 453 static int io_mul2(void)
 454 {
 455         long iv = iv_get(0);
 456         long n, p;
 457         long r1, r2;
 458         long oc = O_C(ic[iv].op);
 459         long bt = O_T(ic[iv].op);
 460         if (!(oc & O_MUL))
 461                 return 1;
 462         if (oc == O_MUL && !ic_num(ic, ic[iv].arg1, &n)) {
 463                 long t = ic[iv].arg1;
 464                 ic[iv].arg1 = ic[iv].arg2;
 465                 ic[iv].arg2 = t;
 466         }
 467         if (ic_num(ic, ic[iv].arg2, &n))
 468                 return 1;
 469         p = log2a(n);
 470         if (n && p < 0)
 471                 return 1;
 472         if (oc == O_MUL) {
 473                 iv_drop(1);
 474                 if (n == 1) {
 475                         iv_put(ic[iv].arg1);
 476                         return 0;
 477                 }
 478                 if (n == 0) {
 479                         o_num(0);
 480                         return 0;
 481                 }
 482                 r2 = iv_num(p);
 483                 ic_put(O_MK(O_SHL, ULNG), iv_new(), ic[iv].arg1, r2);
 484                 return 0;
 485         }
 486         if (oc == O_DIV && ~bt & T_MSIGN) {
 487                 iv_drop(1);
 488                 if (n == 1) {
 489                         iv_put(ic[iv].arg1);
 490                         return 0;
 491                 }
 492                 r2 = iv_num(p);
 493                 ic_put(O_MK(O_SHR, ULNG), iv_new(), ic[iv].arg1, r2);
 494                 return 0;
 495         }
 496         if (oc == O_MOD && ~bt & T_MSIGN) {
 497                 iv_drop(1);
 498                 if (n == 1) {
 499                         o_num(0);
 500                         return 0;
 501                 }
 502                 r2 = iv_num(LONGSZ * 8 - p);
 503                 ic_put(O_MK(O_SHL, ULNG), iv_new(), ic[iv].arg1, r2);
 504                 r1 = iv_pop();
 505                 r2 = iv_num(LONGSZ * 8 - p);
 506                 ic_put(O_MK(O_SHR, ULNG), iv_new(), r1, r2);
 507                 return 0;
 508         }
 509         return 1;
 510 }
 511
 512 /* optimise comparison */
 513 static int io_cmp(void)
 514 {
 515         long iv = iv_get(0);
 516         long cmp = ic[iv].arg1;
 517         if (O_C(ic[iv].op) == O_LNOT && ic[cmp].op & O_CMP) {
 518                 iv_drop(1);
 519                 ic[cmp].op ^= 1;
 520                 iv_put(ic[cmp].arg0);
 521                 return 0;
 522         }
 523         return 1;
 524 }
 525
 526 /* optimise branch instructions after comparison */
 527 static int io_jmp(void)
 528 {
 529         struct ic *c = &ic[ic_n - 1];
 530         long oc = O_C(c->op);
 531         if (oc & O_JZ && O_C(ic[c->arg0].op) == O_LNOT) {
 532                 c->arg0 = ic[c->arg0].arg1;
 533                 c->op ^= 1;
 534                 return 0;
 535         }
 536         if (oc & O_JZ && O_C(ic[c->arg0].op) & O_CMP) {
 537                 long cop = (ic[c->arg0].op & ~O_CMP) | O_JCC;
 538                 c->op = O_C(c->op) == O_JZ ? cop ^ 1 : cop;
 539                 c->arg1 = ic[c->arg0].arg2;
 540                 c->arg0 = ic[c->arg0].arg1;
 541                 return 0;
 542         }
 543         return 1;
 544 }
 545
 546 /* optimise accessing locals or symbols with an offset */
 547 static int io_addr(void)
 548 {
 549         long iv, off;
 550         if (ic_off(ic, ic_n - 1, &iv, &off) || iv != ic_n - 1)
 551                 return 1;
 552         if (ic[iv].op & O_MOV && ic[iv].op & O_LOC) {
 553                 iv_drop(1);
 554                 ic_put(O_MOV | O_LOC, iv_new(), ic[iv].arg1, ic[iv].arg2 + off);
 555                 return 0;
 556         }
 557         if (ic[iv].op & O_MOV && ic[iv].op & O_SYM) {
 558                 iv_drop(1);
 559                 ic_put(O_MOV | O_SYM, iv_new(), ic[iv].arg1, ic[iv].arg2 + off);
 560                 return 0;
 561         }
 562         return 1;
 563 }
 564
 565 /* optimise loading and storing locals */
 566 static int io_loc(void)
 567 {
 568         struct ic *c = &ic[ic_n - 1];
 569         long iv, off;
 570         if (!(c->op & (O_LD | O_ST)) || !(c->op & O_NUM))
 571                 return 1;
 572         if (ic_off(ic, c->arg1, &iv, &off))
 573                 return 1;
 574         if (ic[iv].op & O_MOV && ic[iv].op & O_LOC) {
 575                 c->op = (c->op & ~O_NUM) | O_LOC;
 576                 c->arg1 = ic[iv].arg1;
 577                 c->arg2 += ic[iv].arg2 + off;
 578                 return 0;
 579         }
 580         c->arg1 = iv;
 581         c->arg2 += off;
 582         return 0;
 583 }
 584
 585 static int imm_ok(long op, long n, int arg)
 586 {
 587         long m0, m1, m2, mt;
 588         if (i_reg(op | O_NUM, &m0, &m1, &m2, &mt))
 589                 return 0;
 590         return i_imm(arg == 2 ? m2 : m1, n);
 591 }
 592
 593 /* use instruction immediates */
 594 static int io_imm(void)
 595 {
 596         struct ic *c = &ic[ic_n - 1];
 597         long oc = O_C(c->op);
 598         long n;
 599         if (oc & (O_NUM | O_LOC | O_SYM))
 600                 return 1;
 601         if (oc == O_ADD || oc == O_MUL || oc == O_AND || oc == O_OR ||
 602                         oc == O_XOR || oc == O_EQ || oc == O_NE) {
 603                 if (!ic_num(ic, c->arg1, &n)) {
 604                         long t = c->arg1;
 605                         c->arg1 = c->arg2;
 606                         c->arg2 = t;
 607                 }
 608         }
 609         if (oc == O_LT || oc == O_GE || oc == O_LE || oc == O_GT) {
 610                 if (!ic_num(ic, c->arg1, &n)) {
 611                         int t = c->arg1;
 612                         c->arg1 = c->arg2;
 613                         c->arg2 = t;
 614                         c->op ^= 1;
 615                 }
 616         }
 617         if (oc & O_JCC && !ic_num(ic, c->arg0, &n)) {
 618                 int t = c->arg0;
 619                 c->arg0 = c->arg1;
 620                 c->arg1 = t;
 621                 c->op ^= 1;
 622         }
 623         if (oc & O_JCC && !ic_num(ic, c->arg1, &n) && imm_ok(c->op, n, 1)) {
 624                 c->op |= O_NUM;
 625                 c->arg1 = n;
 626                 return 0;
 627         }
 628         if (!(oc & O_BOP) || ic_num(ic, c->arg2, &n))
 629                 return 1;
 630         if ((oc == O_ADD || oc == O_SUB || oc & O_SHL) && n == 0) {
 631                 iv_drop(1);
 632                 iv_put(c->arg1);
 633                 return 0;
 634         }
 635         if (imm_ok(c->op, n, 2)) {
 636                 c->op |= O_NUM;
 637                 c->arg2 = n;
 638                 return 0;
 639         }
 640         return 1;
 641 }
 642
 643 /* calling symbols */
 644 static int io_call(void)
 645 {
 646         int iv = iv_get(0);
 647         struct ic *c = &ic[iv];
 648         long sym, off;
 649         if (c->op & O_CALL && !ic_sym(ic, c->arg1, &sym, &off) && !off) {
 650                 c->op |= O_SYM;
 651                 c->arg1 = sym;
 652                 return 0;
 653         }
 654         return 1;
 655 }