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 static void io_deadcode(void);
  24
  25 static void iv_put(long n);
  26
  27 static struct ic *ic_put(long op, long arg1, long arg2, long arg3)
  28 {
  29         struct ic *c;
  30         if (ic_n == ic_sz) {
  31                 ic_sz = MAX(128, ic_sz * 2);
  32                 ic = mextend(ic, ic_n, ic_sz, sizeof(*ic));
  33         }
  34         c = &ic[ic_n++];
  35         c->op = op;
  36         c->a1 = arg1;
  37         c->a2 = arg2;
  38         c->a3 = arg3;
  39         if (op & O_OUT)
  40                 iv_put(ic_n - 1);
  41         return c;
  42 }
  43
  44 static void ic_back(long pos)
  45 {
  46         int i;
  47         for (i = pos; i < ic_n; i++)
  48                 if (ic[i].op & O_CALL)
  49                         free(ic[i].args);
  50         ic_n = pos;
  51 }
  52
  53 static long iv_pop(void)
  54 {
  55         return iv[--iv_n];
  56 }
  57
  58 static long iv_get(int n)
  59 {
  60         return iv[iv_n - n - 1];
  61 }
  62
  63 static void iv_put(long n)
  64 {
  65         iv[iv_n++] = n;
  66 }
  67
  68 static void iv_drop(int n)
  69 {
  70         iv_n = MAX(0, iv_n - n);
  71 }
  72
  73 static void iv_swap(int x, int y)
  74 {
  75         long v = iv[iv_n - x - 1];
  76         iv[iv_n - x - 1] = iv[iv_n - y - 1];
  77         iv[iv_n - y - 1] = v;
  78 }
  79
  80 static void iv_dup(void)
  81 {
  82         iv[iv_n] = iv[iv_n - 1];
  83         iv_n++;
  84 }
  85
  86 void o_num(long n)
  87 {
  88         ic_put(O_MOV | O_NUM, n, 0, 0);
  89 }
  90
  91 void o_local(long id)
  92 {
  93         ic_put(O_MOV | O_LOC, id, 0, 0);
  94 }
  95
  96 void o_sym(char *sym)
  97 {
  98         ic_put(O_MOV | O_SYM, out_sym(sym), 0, 0);
  99 }
 100
 101 void o_tmpdrop(int n)
 102 {
 103         iv_drop(n >= 0 ? n : iv_n);
 104 }
 105
 106 void o_tmpswap(void)
 107 {
 108         iv_swap(0, 1);
 109 }
 110
 111 void o_tmpcopy(void)
 112 {
 113         iv_dup();
 114 }
 115
 116 /* return one if the given value is constant */
 117 static int ic_const(long iv)
 118 {
 119         long oc = O_C(ic[iv].op);
 120         return oc & O_MOV && oc & (O_NUM | O_SYM | O_LOC);
 121 }
 122
 123 /* return one if the given value is a simple load */
 124 static int ic_load(long iv)
 125 {
 126         long oc = O_C(ic[iv].op);
 127         int i;
 128         if (oc & O_LD && oc & (O_NUM | O_SYM | O_LOC)) {
 129                 for (i = iv + 1; i < ic_n; i++)
 130                         if (ic[i].op & O_ST)
 131                                 return 0;
 132                 return 1;
 133         }
 134         return 0;
 135 }
 136
 137 void o_bop(long op)
 138 {
 139         int r1 = iv_pop();
 140         int r2 = iv_pop();
 141         /* load constants as late as possible */
 142         if (opt(1) && ic_const(r2) && !ic_const(r1)) {
 143                 ic_put(ic[r2].op, ic[r2].a1, ic[r2].a2, ic[r2].a3);
 144                 r2 = iv_pop();
 145         }
 146         ic_put(op, r2, r1, 0);
 147         if (opt(1)) {
 148                 io_num();
 149                 io_mul2();
 150                 io_addr();
 151                 io_imm();
 152         }
 153 }
 154
 155 void o_uop(long op)
 156 {
 157         int r1 = iv_pop();
 158         ic_put(op, r1, 0, 0);
 159         if (opt(1)) {
 160                 io_num();
 161                 io_cmp();
 162         }
 163 }
 164
 165 void o_assign(long bt)
 166 {
 167         int rv = iv_pop();
 168         int lv = iv_pop();
 169         /* load constants as late as possible */
 170         if (opt(1) && (ic_const(lv) || ic_load(lv))) {
 171                 ic_put(ic[lv].op, ic[lv].a1, ic[lv].a2, ic[lv].a3);
 172                 lv = iv_pop();
 173         }
 174         ic_put(O_MK(O_ST | O_NUM, bt), rv, lv, 0);
 175         iv_put(rv);
 176         if (opt(1))
 177                 io_loc();
 178 }
 179
 180 void o_deref(long bt)
 181 {
 182         int r1 = iv_pop();
 183         ic_put(O_MK(O_LD | O_NUM, bt), r1, 0, 0);
 184         if (opt(1))
 185                 io_loc();
 186 }
 187
 188 void o_cast(long bt)
 189 {
 190         if (T_SZ(bt) != ULNG) {
 191                 int r1 = iv_pop();
 192                 ic_put(O_MK(O_MOV, bt), r1, 0, 0);
 193                 if (opt(1))
 194                         io_num();
 195         }
 196 }
 197
 198 void o_memcpy(void)
 199 {
 200         int r2 = iv_pop();
 201         int r1 = iv_pop();
 202         int r0 = iv_pop();
 203         ic_put(O_MCPY, r0, r1, r2);
 204 }
 205
 206 void o_memset(void)
 207 {
 208         int r2 = iv_pop();
 209         int r1 = iv_pop();
 210         int r0 = iv_pop();
 211         ic_put(O_MSET, r0, r1, r2);
 212 }
 213
 214 void o_call(int argc, int ret)
 215 {
 216         struct ic *c;
 217         long *args = malloc(argc * sizeof(c->args[0]));
 218         int r1, i;
 219         for (i = argc - 1; i >= 0; --i)
 220                 args[i] = iv_pop();
 221         for (i = argc - 1; i >= 0; --i) {
 222                 int iv = args[i];
 223                 /* load constants as late as possible */
 224                 if (opt(1) && (ic_const(iv) || ic_load(iv))) {
 225                         ic_put(ic[iv].op, ic[iv].a1, ic[iv].a2, ic[iv].a3);
 226                         args[i] = iv_pop();
 227                 }
 228         }
 229         r1 = iv_pop();
 230         c = ic_put(O_CALL, r1, 0, argc);
 231         c->args = args;
 232         iv_drop(ret == 0);
 233         if (opt(1))
 234                 io_call();
 235 }
 236
 237 void o_ret(int ret)
 238 {
 239         if (!ret)
 240                 o_num(0);
 241         ic_put(O_RET, iv_pop(), 0, 0);
 242 }
 243
 244 void o_label(long id)
 245 {
 246         while (id >= lab_sz) {
 247                 lab_sz = MAX(128, lab_sz * 2);
 248                 lab_loc = mextend(lab_loc, lab_n, lab_sz, sizeof(*lab_loc));
 249         }
 250         while (lab_n <= id)
 251                 lab_loc[lab_n++] = -1;
 252         lab_loc[id] = ic_n;
 253         lab_last = ic_n;
 254 }
 255
 256 void o_jmp(long id)
 257 {
 258         ic_put(O_JMP, 0, 0, id);
 259 }
 260
 261 void o_jz(long id)
 262 {
 263         ic_put(O_JZ, iv_pop(), 0, id);
 264         if (opt(1))
 265                 io_jmp();
 266 }
 267
 268 int o_popnum(long *n)
 269 {
 270         if (ic_num(ic, iv_get(0), n))
 271                 return 1;
 272         iv_drop(1);
 273         return 0;
 274 }
 275
 276 int o_popsym(long *sym, long *off)
 277 {
 278         if (ic_sym(ic, iv_get(0), sym, off))
 279                 return 1;
 280         iv_drop(1);
 281         return 0;
 282 }
 283
 284 long o_mark(void)
 285 {
 286         return ic_n;
 287 }
 288
 289 void o_back(long mark)
 290 {
 291         ic_back(mark);
 292 }
 293
 294 void ic_get(struct ic **c, long *n)
 295 {
 296         int i;
 297         if (!ic_n || ~ic[ic_n - 1].op & O_RET || lab_last == ic_n)
 298                 o_ret(0);
 299         for (i = 0; i < ic_n; i++)      /* filling branch targets */
 300                 if (ic[i].op & O_JXX)
 301                         ic[i].a3 = lab_loc[ic[i].a3];
 302         io_deadcode();                  /* removing dead code */
 303         *c = ic;
 304         *n = ic_n;
 305         ic = NULL;
 306         ic_n = 0;
 307         ic_sz = 0;
 308         iv_n = 0;
 309         free(lab_loc);
 310         lab_loc = NULL;
 311         lab_n = 0;
 312         lab_sz = 0;
 313         lab_last = 0;
 314 }
 315
 316 void ic_free(struct ic *ic)
 317 {
 318         if (ic->op & O_CALL)
 319                 free(ic->args);
 320 }
 321
 322 /* intermediate code queries */
 323
 324 static long cb(long op, long *r, long a, long b)
 325 {
 326         switch (O_C(op)) {
 327         case O_ADD:
 328                 *r = a + b;
 329                 break;
 330         case O_SUB:
 331                 *r = a - b;
 332                 break;
 333         case O_AND:
 334                 *r = a & b;
 335                 break;
 336         case O_OR:
 337                 *r = a | b;
 338                 break;
 339         case O_XOR:
 340                 *r = a ^ b;
 341                 break;
 342         case O_MUL:
 343                 *r = a * b;
 344                 break;
 345         case O_DIV:
 346                 if (!b)
 347                         return 1;
 348                 *r = a / b;
 349                 break;
 350         case O_MOD:
 351                 if (!b)
 352                         return 1;
 353                 *r = a % b;
 354                 break;
 355         case O_SHL:
 356                 *r = a << b;
 357                 break;
 358         case O_SHR:
 359                 *r = O_T(op) & T_MSIGN ? a >> b : (unsigned long) a >> b;
 360                 break;
 361         case O_LT:
 362                 *r = a < b;
 363                 break;
 364         case O_GT:
 365                 *r = a > b;
 366                 break;
 367         case O_LE:
 368                 *r = a <= b;
 369                 break;
 370         case O_GE:
 371                 *r = a >= b;
 372                 break;
 373         case O_EQ:
 374                 *r = a == b;
 375                 break;
 376         case O_NE:
 377                 *r = a != b;
 378                 break;
 379         }
 380         return 0;
 381 }
 382
 383 static long cu(int op, long i)
 384 {
 385         switch (O_C(op)) {
 386         case O_NEG:
 387                 return -i;
 388         case O_NOT:
 389                 return ~i;
 390         case O_LNOT:
 391                 return !i;
 392         }
 393         return 0;
 394 }
 395
 396 static long c_cast(long n, unsigned bt)
 397 {
 398         if (!(bt & T_MSIGN) && T_SZ(bt) != ULNG)
 399                 n &= ((1l << (long) (T_SZ(bt) * 8)) - 1);
 400         if (bt & T_MSIGN && T_SZ(bt) != ULNG &&
 401                                 n > (1l << (T_SZ(bt) * 8 - 1)))
 402                 n = -((1l << (T_SZ(bt) * 8)) - n);
 403         return n;
 404 }
 405
 406 int ic_num(struct ic *ic, long iv, long *n)
 407 {
 408         long n1, n2;
 409         long oc = O_C(ic[iv].op);
 410         long bt = O_T(ic[iv].op);
 411         if (oc & O_MOV && oc & O_NUM) {
 412                 *n = ic[iv].a1;
 413                 return 0;
 414         }
 415         if (oc & O_BOP) {
 416                 if (ic_num(ic, ic[iv].a1, &n1))
 417                         return 1;
 418                 if (ic_num(ic, ic[iv].a2, &n2))
 419                         return 1;
 420                 return cb(ic[iv].op, n, n1, n2);
 421         }
 422         if (oc & O_UOP) {
 423                 if (ic_num(ic, ic[iv].a1, &n1))
 424                         return 1;
 425                 *n = cu(ic[iv].op, n1);
 426                 return 0;
 427         }
 428         if (oc & O_MOV && !(oc & (O_NUM | O_LOC | O_SYM))) {
 429                 if (ic_num(ic, ic[iv].a1, &n1))
 430                         return 1;
 431                 *n = c_cast(n1, bt);
 432                 return 0;
 433         }
 434         return 1;
 435 }
 436
 437 int ic_sym(struct ic *ic, long iv, long *sym, long *off)
 438 {
 439         long n;
 440         long oc = O_C(ic[iv].op);
 441         if (oc & O_MOV && oc & O_SYM) {
 442                 *sym = ic[iv].a1;
 443                 *off = ic[iv].a2;
 444                 return 0;
 445         }
 446         if (oc == O_ADD) {
 447                 if ((ic_sym(ic, ic[iv].a1, sym, off) ||
 448                                 ic_num(ic, ic[iv].a2, &n)) &&
 449                         (ic_sym(ic, ic[iv].a2, sym, off) ||
 450                                 ic_num(ic, ic[iv].a1, &n)))
 451                         return 1;
 452                 *off += n;
 453                 return 0;
 454         }
 455         if (oc == O_SUB) {
 456                 if (ic_sym(ic, ic[iv].a1, sym, off) ||
 457                                 ic_num(ic, ic[iv].a2, &n))
 458                         return 1;
 459                 *off -= n;
 460                 return 0;
 461         }
 462         return 1;
 463 }
 464
 465 static int ic_off(struct ic *ic, long iv, long *base_iv, long *off)
 466 {
 467         long n;
 468         long oc = O_C(ic[iv].op);
 469         if (oc == (O_ADD | O_NUM)) {
 470                 *base_iv = ic[iv].a1;
 471                 *off = ic[iv].a2;
 472                 return 0;
 473         }
 474         if (oc == (O_SUB | O_NUM)) {
 475                 *base_iv = ic[iv].a1;
 476                 *off = -ic[iv].a2;
 477                 return 0;
 478         }
 479         if (oc == O_ADD) {
 480                 if ((ic_off(ic, ic[iv].a1, base_iv, off) ||
 481                                 ic_num(ic, ic[iv].a2, &n)) &&
 482                         (ic_off(ic, ic[iv].a2, base_iv, off) ||
 483                                 ic_num(ic, ic[iv].a1, &n)))
 484                         return 1;
 485                 *off += n;
 486                 return 0;
 487         }
 488         if (oc == O_SUB) {
 489                 if (ic_off(ic, ic[iv].a1, base_iv, off) ||
 490                                 ic_num(ic, ic[iv].a2, &n))
 491                         return 1;
 492                 *off -= n;
 493                 return 0;
 494         }
 495         *base_iv = iv;
 496         *off = 0;
 497         return 0;
 498 }
 499
 500 /* number of register arguments */
 501 int ic_regcnt(struct ic *ic)
 502 {
 503         long o = ic->op;
 504         if (o & O_BOP)
 505                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 506         if (o & O_UOP)
 507                 return o & (O_NUM | O_SYM | O_LOC) ? 0 : 1;
 508         if (o & O_CALL)
 509                 return o & (O_NUM | O_SYM | O_LOC) ? 0 : 1;
 510         if (o & O_MOV)
 511                 return o & (O_NUM | O_SYM | O_LOC) ? 0 : 1;
 512         if (o & O_MEM)
 513                 return 3;
 514         if (o & O_JMP)
 515                 return 0;
 516         if (o & O_JZ)
 517                 return 1;
 518         if (o & O_JCC)
 519                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 520         if (o & O_RET)
 521                 return 1;
 522         if (o & O_LD)
 523                 return ((o & O_NUM) != 0);
 524         if (o & O_ST)
 525                 return 1 + ((o & O_NUM) != 0);
 526         return 0;
 527 }
 528
 529 /*
 530  * The returned array indicates the last instruction in
 531  * which the value produced by each instruction is used.
 532  */
 533 long *ic_lastuse(struct ic *ic, long ic_n)
 534 {
 535         long *luse = calloc(ic_n, sizeof(luse[0]));
 536         int i, j;
 537         for (i = ic_n - 1; i >= 0; --i) {
 538                 int n = ic_regcnt(ic + i);
 539                 if (!luse[i])
 540                         if (!(ic[i].op & O_OUT) || ic[i].op & O_CALL)
 541                                 luse[i] = -1;
 542                 if (!luse[i])
 543                         continue;
 544                 if (n >= 1 && !luse[ic[i].a1])
 545                         luse[ic[i].a1] = i;
 546                 if (n >= 2 && !luse[ic[i].a2])
 547                         luse[ic[i].a2] = i;
 548                 if (n >= 3 && !luse[ic[i].a3])
 549                         luse[ic[i].a3] = i;
 550                 if (ic[i].op & O_CALL)
 551                         for (j = 0; j < ic[i].a3; j++)
 552                                 if (!luse[ic[i].args[j]])
 553                                         luse[ic[i].args[j]] = i;
 554         }
 555         return luse;
 556 }
 557
 558 /* intermediate code optimisations */
 559
 560 /* constant folding */
 561 static int io_num(void)
 562 {
 563         long n;
 564         if (!ic_num(ic, iv_get(0), &n)) {
 565                 iv_drop(1);
 566                 o_num(n);
 567                 return 0;
 568         }
 569         return 1;
 570 }
 571
 572 static int log2a(unsigned long n)
 573 {
 574         int i = 0;
 575         for (i = 0; i < LONGSZ * 8; i++)
 576                 if (n & (1u << i))
 577                         break;
 578         if (i == LONGSZ * 8 || !(n >> (i + 1)))
 579                 return i;
 580         return -1;
 581 }
 582
 583 static long iv_num(long n)
 584 {
 585         o_num(n);
 586         return iv_pop();
 587 }
 588
 589 /* optimised multiplication operations for powers of two */
 590 static int io_mul2(void)
 591 {
 592         long iv = iv_get(0);
 593         long n, p;
 594         long r1, r2;
 595         long oc = O_C(ic[iv].op);
 596         long bt = O_T(ic[iv].op);
 597         if (!(oc & O_MUL))
 598                 return 1;
 599         if (oc == O_MUL && !ic_num(ic, ic[iv].a1, &n)) {
 600                 long t = ic[iv].a1;
 601                 ic[iv].a1 = ic[iv].a2;
 602                 ic[iv].a2 = t;
 603         }
 604         if (ic_num(ic, ic[iv].a2, &n))
 605                 return 1;
 606         p = log2a(n);
 607         if (n && p < 0)
 608                 return 1;
 609         if (oc == O_MUL) {
 610                 iv_drop(1);
 611                 if (n == 1) {
 612                         iv_put(ic[iv].a1);
 613                         return 0;
 614                 }
 615                 if (n == 0) {
 616                         o_num(0);
 617                         return 0;
 618                 }
 619                 r2 = iv_num(p);
 620                 ic_put(O_MK(O_SHL, ULNG), ic[iv].a1, r2, 0);
 621                 return 0;
 622         }
 623         if (oc == O_DIV && ~bt & T_MSIGN) {
 624                 iv_drop(1);
 625                 if (n == 1) {
 626                         iv_put(ic[iv].a1);
 627                         return 0;
 628                 }
 629                 r2 = iv_num(p);
 630                 ic_put(O_MK(O_SHR, ULNG), ic[iv].a1, r2, 0);
 631                 return 0;
 632         }
 633         if (oc == O_MOD && ~bt & T_MSIGN) {
 634                 iv_drop(1);
 635                 if (n == 1) {
 636                         o_num(0);
 637                         return 0;
 638                 }
 639                 r2 = iv_num(LONGSZ * 8 - p);
 640                 ic_put(O_MK(O_SHL, ULNG), ic[iv].a1, r2, 0);
 641                 r1 = iv_pop();
 642                 r2 = iv_num(LONGSZ * 8 - p);
 643                 ic_put(O_MK(O_SHR, ULNG), r1, r2, 0);
 644                 return 0;
 645         }
 646         return 1;
 647 }
 648
 649 /* optimise comparison */
 650 static int io_cmp(void)
 651 {
 652         long iv = iv_get(0);
 653         long cmp = ic[iv].a1;
 654         if (O_C(ic[iv].op) == O_LNOT && ic[cmp].op & O_CMP) {
 655                 iv_drop(1);
 656                 ic[cmp].op ^= 1;
 657                 iv_put(cmp);
 658                 return 0;
 659         }
 660         return 1;
 661 }
 662
 663 /* optimise branch instructions after comparison */
 664 static int io_jmp(void)
 665 {
 666         struct ic *c = &ic[ic_n - 1];
 667         long oc = O_C(c->op);
 668         if (oc & O_JZ && O_C(ic[c->a1].op) == O_LNOT) {
 669                 c->a1 = ic[c->a1].a1;
 670                 c->op ^= 1;
 671                 return 0;
 672         }
 673         if (oc & O_JZ && O_C(ic[c->a1].op) & O_CMP) {
 674                 long cop = (ic[c->a1].op & ~O_CMP) | O_JCC;
 675                 c->op = O_C(c->op) == O_JZ ? cop ^ 1 : cop;
 676                 c->a2 = ic[c->a1].a2;
 677                 c->a1 = ic[c->a1].a1;
 678                 return 0;
 679         }
 680         return 1;
 681 }
 682
 683 /* optimise accessing locals or symbols with an offset */
 684 static int io_addr(void)
 685 {
 686         long iv, off;
 687         if (ic_off(ic, iv_get(0), &iv, &off) || iv == iv_get(0))
 688                 return 1;
 689         if (ic[iv].op & O_MOV && ic[iv].op & O_LOC) {
 690                 iv_drop(1);
 691                 ic_put(O_MOV | O_LOC, ic[iv].a1, ic[iv].a2 + off, 0);
 692                 return 0;
 693         }
 694         if (ic[iv].op & O_MOV && ic[iv].op & O_SYM) {
 695                 iv_drop(1);
 696                 ic_put(O_MOV | O_SYM, ic[iv].a1, ic[iv].a2 + off, 0);
 697                 return 0;
 698         }
 699         return 1;
 700 }
 701
 702 static int imm_ok(long op, long n, int arg)
 703 {
 704         long m[5];
 705         if (i_reg(op | O_NUM, m + 0, m + 1, m + 2, m + 3, m + 4))
 706                 return 0;
 707         return i_imm(m[arg], n);
 708 }
 709
 710 /* optimise loading and storing locals */
 711 static int io_loc(void)
 712 {
 713         struct ic *c = &ic[ic_n - 1];
 714         long iv, off;
 715         if (c->op & O_LD && c->op & O_NUM) {
 716                 if (ic_off(ic, c->a1, &iv, &off))
 717                         return 1;
 718                 if (ic[iv].op & O_MOV && ic[iv].op & O_LOC) {
 719                         c->op = (c->op & ~O_NUM) | O_LOC;
 720                         c->a1 = ic[iv].a1;
 721                         c->a2 += ic[iv].a2 + off;
 722                         return 0;
 723                 }
 724                 if (imm_ok(c->op, off, 2)) {
 725                         c->a1 = iv;
 726                         c->a2 += off;
 727                 }
 728                 return 0;
 729         }
 730         if (c->op & O_ST && c->op & O_NUM) {
 731                 if (ic_off(ic, c->a2, &iv, &off))
 732                         return 1;
 733                 if (ic[iv].op & O_MOV && ic[iv].op & O_LOC) {
 734                         c->op = (c->op & ~O_NUM) | O_LOC;
 735                         c->a2 = ic[iv].a1;
 736                         c->a3 += ic[iv].a2 + off;
 737                         return 0;
 738                 }
 739                 if (imm_ok(c->op, off, 3)) {
 740                         c->a2 = iv;
 741                         c->a3 += off;
 742                 }
 743                 return 0;
 744         }
 745         return 1;
 746 }
 747
 748 /* reverse the order of comparison operands (e.g., <= to >=) */
 749 static int flip_cond(int op) {
 750         /* lt -> gt, ge -> le, eq -> eq, ne -> ne, le -> ge, gt -> lt */
 751         static int cond[] = {5, 4, 2, 3, 1, 0};
 752         return (op & ~0x0f) | cond[op & 0x0f];
 753 }
 754
 755 /* use instruction immediates */
 756 static int io_imm(void)
 757 {
 758         struct ic *c = &ic[ic_n - 1];
 759         long oc = O_C(c->op);
 760         long n;
 761         if (oc & (O_NUM | O_LOC | O_SYM))
 762                 return 1;
 763         if (oc == O_ADD || oc == O_MUL || oc == O_AND || oc == O_OR ||
 764                         oc == O_XOR || oc == O_EQ || oc == O_NE) {
 765                 if (!ic_num(ic, c->a1, &n)) {
 766                         long t = c->a1;
 767                         c->a1 = c->a2;
 768                         c->a2 = t;
 769                 }
 770         }
 771         if (oc == O_LT || oc == O_GE || oc == O_LE || oc == O_GT) {
 772                 if (!ic_num(ic, c->a1, &n)) {
 773                         int t = c->a1;
 774                         c->a1 = c->a2;
 775                         c->a2 = t;
 776                         c->op = flip_cond(c->op);
 777                 }
 778         }
 779         if (oc & O_JCC && !ic_num(ic, c->a1, &n)) {
 780                 int t = c->a1;
 781                 c->a1 = c->a2;
 782                 c->a2 = t;
 783                 c->op = flip_cond(c->op);
 784         }
 785         if (oc & O_JCC && !ic_num(ic, c->a2, &n) && imm_ok(c->op, n, 2)) {
 786                 c->op |= O_NUM;
 787                 c->a2 = n;
 788                 return 0;
 789         }
 790         if (!(oc & O_BOP) || ic_num(ic, c->a2, &n))
 791                 return 1;
 792         if ((oc == O_ADD || oc == O_SUB || oc & O_SHL) && n == 0) {
 793                 iv_drop(1);
 794                 iv_put(c->a1);
 795                 return 0;
 796         }
 797         if (imm_ok(c->op, n, 2)) {
 798                 c->op |= O_NUM;
 799                 c->a2 = n;
 800                 return 0;
 801         }
 802         return 1;
 803 }
 804
 805 /* calling symbols */
 806 static int io_call(void)
 807 {
 808         struct ic *c = &ic[ic_n - 1];
 809         long sym, off;
 810         if (c->op & O_CALL && !ic_sym(ic, c->a1, &sym, &off) && !off) {
 811                 c->op |= O_SYM;
 812                 c->a1 = sym;
 813                 return 0;
 814         }
 815         return 1;
 816 }
 817
 818 /* remove dead code */
 819 static void io_deadcode(void)
 820 {
 821         char *live;
 822         long *nidx;
 823         long src = 0, dst = 0;
 824         int i, j;
 825         /* liveness analysis */
 826         live = calloc(ic_n, sizeof(live[0]));
 827         for (i = ic_n - 1; i >= 0; i--) {
 828                 int n = ic_regcnt(ic + i);
 829                 if (!(ic[i].op & O_OUT) || ic[i].op & O_CALL)
 830                         live[i] = 1;
 831                 if (!live[i])
 832                         continue;
 833                 if (n >= 1)
 834                         live[ic[i].a1] = 1;
 835                 if (n >= 2)
 836                         live[ic[i].a2] = 1;
 837                 if (n >= 3)
 838                         live[ic[i].a3] = 1;
 839                 if (ic[i].op & O_CALL)
 840                         for (j = 0; j < ic[i].a3; j++)
 841                                 live[ic[i].args[j]] = 1;
 842         }
 843         /* the new indices of intermediate instructions */
 844         nidx = calloc(ic_n, sizeof(nidx[0]));
 845         while (src < ic_n) {
 846                 while (src < ic_n && !live[src]) {
 847                         nidx[src] = dst;
 848                         ic_free(&ic[src++]);
 849                 }
 850                 if (src < ic_n) {
 851                         nidx[src] = dst;
 852                         if (src != dst)
 853                                 memcpy(ic + dst, ic + src, sizeof(ic[src]));
 854                         src++;
 855                         dst++;
 856                 }
 857         }
 858         ic_n = dst;
 859         /* adjusting arguments and branch targets */
 860         for (i = 0; i < ic_n; i++) {
 861                 int n = ic_regcnt(ic + i);
 862                 if (n >= 1)
 863                         ic[i].a1 = nidx[ic[i].a1];
 864                 if (n >= 2)
 865                         ic[i].a2 = nidx[ic[i].a2];
 866                 if (n >= 3)
 867                         ic[i].a3 = nidx[ic[i].a3];
 868                 if (ic[i].op & O_JXX)
 869                         ic[i].a3 = nidx[ic[i].a3];
 870                 if (ic[i].op & O_CALL)
 871                         for (j = 0; j < ic[i].a3; j++)
 872                                 ic[i].args[j] = nidx[ic[i].args[j]];
 873         }
 874         free(live);
 875         free(nidx);
 876 }