gen.c

   1 /* neatcc code generation */
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include "ncc.h"
   6
   7 static struct mem ds;           /* data segment */
   8 static struct mem cs;           /* code segment */
   9 static long bsslen;             /* bss segment size */
  10
  11 static long *loc_off;           /* offset of locals on the stack */
  12 static long loc_n, loc_sz;      /* number of locals */
  13 static long loc_pos;            /* current stack position */
  14 static int *loc_mem;            /* local memory was accessed */
  15 static int *loc_ptr;            /* the address of this local is fetched */
  16 static int *loc_dat;            /* the number of data accesses of this local */
  17
  18 static char (*ds_name)[NAMELEN];/* data section symbols */
  19 static long *ds_off;            /* data section offsets */
  20 static long ds_n, ds_sz;        /* number of data section symbols */
  21
  22 static int func_argc;           /* number of arguments */
  23 static int func_varg;           /* varargs */
  24 static int func_regs;           /* used registers */
  25 static int func_maxargs;        /* the maximum number of arguments on the stack */
  26 static int func_leaf;           /* a leaf function */
  27 static long *ic_luse;           /* the last use of values generated by instructions */
  28 static long *ic_bbeg;           /* whether each instruction begins a basic block */
  29
  30 static long ra_vmap[N_REGS];    /* register to intermediate value assignments */
  31 static long ra_lmap[N_REGS];    /* register to local assignments */
  32 static long ra_lmapglob[N_REGS];        /* global register to local assignments */
  33 static long *ra_gmask;          /* the mask of good registers for each value */
  34 static long ra_live[NTMPS];     /* live values */
  35 static int ra_vmax;             /* the number of values stored on the stack */
  36
  37 static long loc_add(long pos)
  38 {
  39         if (loc_n >= loc_sz) {
  40                 loc_sz = MAX(128, loc_sz * 2);
  41                 loc_off = mextend(loc_off, loc_n, loc_sz, sizeof(loc_off[0]));
  42         }
  43         loc_off[loc_n] = pos;
  44         return loc_n++;
  45 }
  46
  47 long o_mklocal(long sz)
  48 {
  49         loc_pos += ALIGN(sz, ULNG);
  50         return loc_add(loc_pos);
  51 }
  52
  53 void o_rmlocal(long addr, long sz)
  54 {
  55 }
  56
  57 long o_arg2loc(int i)
  58 {
  59         return i;
  60 }
  61
  62 void o_bsnew(char *name, long size, int global)
  63 {
  64         out_def(name, OUT_BSS | (global ? OUT_GLOB : 0), bsslen, size);
  65         bsslen += ALIGN(size, OUT_ALIGNMENT);
  66 }
  67
  68 long o_dsnew(char *name, long size, int global)
  69 {
  70         int idx;
  71         if (ds_n >= ds_sz) {
  72                 ds_sz = MAX(128, ds_sz * 2);
  73                 ds_name = mextend(ds_name, ds_n, ds_sz, sizeof(ds_name[0]));
  74                 ds_off = mextend(ds_off, ds_n, ds_sz, sizeof(ds_off[0]));
  75         }
  76         idx = ds_n++;
  77         strcpy(ds_name[idx], name);
  78         ds_off[idx] = mem_len(&ds);
  79         out_def(name, OUT_DS | (global ? OUT_GLOB : 0), mem_len(&ds), size);
  80         mem_putz(&ds, ALIGN(size, OUT_ALIGNMENT));
  81         return ds_off[idx];
  82 }
  83
  84 void o_dscpy(long addr, void *buf, long len)
  85 {
  86         mem_cpy(&ds, addr, buf, len);
  87 }
  88
  89 static int dat_off(char *name)
  90 {
  91         int i;
  92         for (i = 0; i < ds_n; i++)
  93                 if (!strcmp(name, ds_name[i]))
  94                         return ds_off[i];
  95         return 0;
  96 }
  97
  98 void o_dsset(char *name, long off, long bt)
  99 {
 100         long sym_off = dat_off(name) + off;
 101         long num, roff, rsym;
 102         if (!o_popnum(&num)) {
 103                 mem_cpy(&ds, sym_off, &num, T_SZ(bt));
 104                 return;
 105         }
 106         if (!o_popsym(&rsym, &roff)) {
 107                 out_rel(rsym, OUT_DS, sym_off);
 108                 mem_cpy(&ds, sym_off, &roff, T_SZ(bt));
 109         }
 110 }
 111
 112 /* number of register arguments */
 113 static int ic_regcnt(struct ic *ic)
 114 {
 115         long o = ic->op;
 116         if (o & O_BOP)
 117                 return o & (O_NUM | O_SYM | O_LOC) ? 2 : 3;
 118         if (o & O_UOP)
 119                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 120         if (o & O_CALL)
 121                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 122         if (o & O_MOV)
 123                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 124         if (o & O_MEM)
 125                 return 3;
 126         if (o & O_JMP)
 127                 return 0;
 128         if (o & O_JZ)
 129                 return 1;
 130         if (o & O_JCC)
 131                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 132         if (o & O_RET)
 133                 return 1;
 134         if (o & (O_LD | O_ST) && o & (O_SYM | O_LOC))
 135                 return 1;
 136         if (o & (O_LD | O_ST))
 137                 return o & O_NUM ? 2 : 3;
 138         return 0;
 139 }
 140
 141 static int ra_vreg(int val)
 142 {
 143         int i;
 144         for (i = 0; i < LEN(ra_vmap); i++)
 145                 if (ra_vmap[i] == val)
 146                         return i;
 147         return -1;
 148 }
 149
 150 static int ra_lreg(int loc)
 151 {
 152         int i;
 153         for (i = 0; i < LEN(ra_lmap); i++)
 154                 if (ra_lmap[i] == loc)
 155                         return i;
 156         return -1;
 157 }
 158
 159 /* mask of registers assigned to locals */
 160 static long ra_lmask(void)
 161 {
 162         long m = 0;
 163         int i;
 164         for (i = 0; i < LEN(ra_lmap); i++)
 165                 if (ra_lmap[i] >= 0)
 166                         m |= (1 << i);
 167         return m;
 168 }
 169
 170 /* mask of registers assigned to values */
 171 static long ra_vmask(void)
 172 {
 173         long m = 0;
 174         int i;
 175         for (i = 0; i < LEN(ra_vmap); i++)
 176                 if (ra_vmap[i] >= 0)
 177                         m |= (1 << i);
 178         return m;
 179 }
 180
 181 /* find a temporary register specified in the given mask */
 182 static long ra_regscn(long mask)
 183 {
 184         int i;
 185         for (i = 0; i < N_TMPS; i++)
 186                 if ((1 << tmpregs[i]) & mask)
 187                         return tmpregs[i];
 188         return -1;
 189 }
 190
 191 /* find a register, with the given good, acceptable, and bad register masks */
 192 static long ra_regget(long iv, long gmask, long amask, long bmask)
 193 {
 194         long lmask, vmask;
 195         gmask &= ~bmask & amask;
 196         amask &= ~bmask;
 197         if (ra_vreg(iv) >= 0 && (1 << ra_vreg(iv)) & (gmask | amask))
 198                 return ra_vreg(iv);
 199         vmask = ra_vmask();
 200         lmask = ra_lmask();
 201         if (ra_regscn(gmask & ~vmask & ~lmask) >= 0)
 202                 return ra_regscn(gmask & ~vmask & ~lmask);
 203         if (ra_regscn(amask & ~vmask & ~lmask) >= 0)
 204                 return ra_regscn(amask & ~vmask & ~lmask);
 205         if (ra_regscn(gmask) >= 0)
 206                 return ra_regscn(gmask);
 207         if (ra_regscn(amask) >= 0)
 208                 return ra_regscn(amask);
 209         die("neatcc: cannot allocate an acceptable register\n");
 210         return 0;
 211 }
 212
 213 /* find a free and cheap register */
 214 static long ra_regcheap(long mask)
 215 {
 216         return ra_regscn(mask & (func_regs | (R_TMPS & ~R_PERM)) &
 217                         ~ra_lmask() & ~ra_vmask());
 218 }
 219
 220 /* allocate registers for a 3-operand instruction */
 221 static void ra_map(struct ic *ic, int *r0, int *r1, int *r2, long *mt)
 222 {
 223         long m0, m1, m2;
 224         long all = 0;
 225         int n = ic_regcnt(ic);
 226         int oc = O_C(ic->op);
 227         int i;
 228         *r0 = -1;
 229         *r1 = -1;
 230         *r2 = -1;
 231         *mt = 0;
 232         /* optimizing loading locals: point to local's register */
 233         if (oc == (O_LD | O_LOC) && ra_lreg(ic->arg1) >= 0 &&
 234                         ra_vmap[ra_lreg(ic->arg1)] < 0) {
 235                 *r0 = ra_lreg(ic->arg1);
 236                 func_regs |= 1 << *r0;
 237                 return;
 238         }
 239         /* do not use argument registers to hold call destination */
 240         if (oc & O_CALL)
 241                 for (i = 0; i < MIN(ic->arg2, N_ARGS); i++)
 242                         all |= (1 << argregs[i]);
 243         /* instructions on locals can be simplified */
 244         if (oc & O_LOC) {
 245                 if (oc & O_MOV)
 246                         oc = O_ADD | O_NUM;
 247                 if (oc & (O_ST | O_LD))
 248                         oc = (oc & ~O_LOC) & O_NUM;
 249         }
 250         if (i_reg(ic->op, &m0, &m1, &m2, mt))
 251                 die("neatcc: instruction %08lx not supported\n", ic->op);
 252         /*
 253          * the registers used in global register allocation should not
 254          * be used in the last instruction of a basic block.
 255          */
 256         if (ic->op & (O_JZ | O_JCC))
 257                 for (i = 0; i < LEN(ra_lmap); i++)
 258                         if (ra_lmapglob[i] >= 0 && ra_lmap[i] != ra_lmapglob[i])
 259                                 all |= (1 << i);
 260         /* allocating registers for the operands */
 261         if (n >= 3) {
 262                 *r2 = ra_regget(ic->arg2, m2, m2, all);
 263                 all |= (1 << *r2);
 264         }
 265         if (n >= 2) {
 266                 *r1 = ra_regget(ic->arg1, m1, m1, all);
 267                 all |= (1 << *r1);
 268         }
 269         if (n >= 1 && m0) {
 270                 int wop = ic->op & O_OUT;
 271                 if (wop && n >= 3 && m0 & (1 << *r2))
 272                         *r0 = *r2;
 273                 else if (wop && n >= 2 && m0 & (1 << *r1))
 274                         *r0 = *r1;
 275                 else
 276                         *r0 = ra_regget(ic->arg0, ra_gmask[ic->arg0],
 277                                 m0, wop ? 0 : all);
 278         }
 279         if (n >= 1 && !m0)
 280                 *r0 = *r1;
 281         /* if r0 is overwritten and it is a local; use another register */
 282         if (n >= 1 && oc & O_OUT && ra_lmap[*r0] >= 0) {
 283                 long m3 = (m0 ? m0 : m1) & ~(all | (1 << *r0));
 284                 long arg3 = m0 ? ic->arg0 : ic->arg1;
 285                 if (m3 != 0) {
 286                         int r3 = ra_regget(arg3, ra_gmask[ic->arg0], m3, 0);
 287                         if (n >= 2 && *r0 == *r1)
 288                                 *r1 = r3;
 289                         if (n >= 3 && *r0 == *r2)
 290                                 *r2 = r3;
 291                         *r0 = r3;
 292                 }
 293         }
 294         if (n)
 295                 all |= (1 << *r0);
 296         func_regs |= all | *mt;
 297 }
 298
 299 static long iv_rank(long iv)
 300 {
 301         int i;
 302         for (i = 0; i < LEN(ra_live); i++)
 303                 if (ra_live[i] == iv)
 304                         return i;
 305         die("neatcc: the specified value is not live\n");
 306         return 0;
 307 }
 308
 309 static long iv_addr(long rank)
 310 {
 311         return loc_pos + rank * ULNG + ULNG;
 312 }
 313
 314 static void loc_toreg(long loc, long off, int reg, int bt)
 315 {
 316         loc_mem[loc]++;
 317         i_ins(O_MK(O_LD | O_NUM, bt), reg, REG_FP, -loc_off[loc] + off);
 318 }
 319
 320 static void loc_tomem(long loc, long off, int reg, int bt)
 321 {
 322         loc_mem[loc]++;
 323         i_ins(O_MK(O_ST | O_NUM, bt), reg, REG_FP, -loc_off[loc] + off);
 324 }
 325
 326 static void loc_toadd(long loc, long off, int reg)
 327 {
 328         loc_mem[loc]++;
 329         i_ins(O_ADD | O_NUM, reg, REG_FP, -loc_off[loc] + off);
 330 }
 331
 332 static void val_toreg(long val, int reg)
 333 {
 334         i_ins(O_MK(O_LD | O_NUM, ULNG), reg, REG_FP, -iv_addr(iv_rank(val)));
 335 }
 336
 337 static void val_tomem(long val, int reg)
 338 {
 339         long rank = iv_rank(val);
 340         ra_vmax = MAX(ra_vmax, rank + 1);
 341         i_ins(O_MK(O_ST | O_NUM, ULNG), reg, REG_FP, -iv_addr(rank));
 342 }
 343
 344 /* move the value to the stack */
 345 static void ra_spill(int reg)
 346 {
 347         if (ra_vmap[reg] >= 0) {
 348                 val_tomem(ra_vmap[reg], reg);
 349                 ra_vmap[reg] = -1;
 350         }
 351         if (ra_lmap[reg] >= 0) {
 352                 if (ra_lmap[reg] == ra_lmapglob[reg])
 353                         loc_tomem(ra_lmap[reg], 0, reg, ULNG);
 354                 ra_lmap[reg] = -1;
 355         }
 356 }
 357
 358 /* set the value to the given register */
 359 static void ra_vsave(long iv, int reg)
 360 {
 361         int i;
 362         ra_vmap[reg] = iv;
 363         for (i = 0; i < LEN(ra_live); i++)
 364                 if (ra_live[i] < 0)
 365                         break;
 366         if (i == LEN(ra_live))
 367                 die("neatcc: too many live values\n");
 368         ra_live[i] = iv;
 369 }
 370
 371 /* load the value into a register */
 372 static void ra_vload(long iv, int reg)
 373 {
 374         if (ra_vmap[reg] == iv)
 375                 return;
 376         if (ra_vmap[reg] >= 0 || ra_lmap[reg] >= 0)
 377                 ra_spill(reg);
 378         if (ra_vreg(iv) >= 0) {
 379                 i_ins(O_MK(O_MOV, ULNG), reg, ra_vreg(iv), 0);
 380                 ra_vmap[ra_vreg(iv)] = -1;
 381         } else {
 382                 val_toreg(iv, reg);
 383         }
 384         ra_vmap[reg] = iv;
 385 }
 386
 387 /* the value is no longer needed */
 388 static void ra_vdrop(long iv)
 389 {
 390         int i;
 391         for (i = 0; i < LEN(ra_live); i++)
 392                 if (ra_live[i] == iv)
 393                         ra_live[i] = -1;
 394         if (ra_vreg(iv) >= 0)
 395                 ra_vmap[ra_vreg(iv)] = -1;
 396 }
 397
 398 /* move the given value to memory or a free register */
 399 static void ra_vmove(long iv, long mask)
 400 {
 401         int src = ra_vreg(iv);
 402         int dst = ra_regcheap(mask);
 403         if (dst >= 0 && ra_vmap[dst] < 0 && ra_lmap[dst] < 0) {
 404                 i_ins(O_MK(O_MOV, ULNG), dst, src, 0);
 405                 ra_vmap[dst] = iv;
 406         } else {
 407                 val_tomem(iv, src);
 408         }
 409         ra_vmap[src] = -1;
 410 }
 411
 412 /* load the value of local loc into register reg */
 413 static void ra_lload(long loc, long off, int reg, int bt)
 414 {
 415         if (ra_lreg(loc) < 0 && !loc_ptr[loc] && loc_dat[loc] > 2) {
 416                 ra_lmap[reg] = loc;
 417                 loc_toreg(loc, off, reg, bt);
 418         }
 419         if (ra_lreg(loc) >= 0) {
 420                 if (ra_lreg(loc) != reg)
 421                         i_ins(O_MK(O_MOV, bt), reg, ra_lreg(loc), 0);
 422         } else {
 423                 loc_toreg(loc, off, reg, bt);
 424         }
 425 }
 426
 427 /* register reg contains the value of local loc */
 428 static void ra_lsave(long loc, long off, int reg, int bt)
 429 {
 430         int lreg = ra_lreg(loc);
 431         if (lreg >= 0 && ra_lmapglob[lreg] == ra_lmap[lreg]) {
 432                 if (ra_vmap[lreg] >= 0) /* values using the same register */
 433                         ra_vmove(ra_vmap[lreg],
 434                                 ra_gmask[ra_vmap[lreg]] & ~(1 << reg));
 435                 i_ins(O_MK(O_MOV, bt), lreg, reg, 0);
 436         } else {
 437                 if (lreg >= 0)
 438                         ra_lmap[lreg] = -1;
 439                 loc_tomem(loc, off, reg, bt);
 440                 if (!loc_ptr[loc] && loc_dat[loc] > 2 && ra_lmap[reg] < 0)
 441                         ra_lmap[reg] = loc;
 442         }
 443 }
 444
 445 /* end of a basic block */
 446 static void ra_bbend(void)
 447 {
 448         int i;
 449         /* save values to memory */
 450         for (i = 0; i < LEN(ra_vmap); i++)
 451                 if (ra_vmap[i] >= 0)
 452                         ra_spill(i);
 453         /* dropping local caches */
 454         for (i = 0; i < LEN(ra_lmap); i++)
 455                 if (ra_lmap[i] != ra_lmapglob[i] && ra_lmap[i] >= 0)
 456                         ra_spill(i);
 457         /* load global register allocations from memory */
 458         for (i = 0; i < LEN(ra_lmap); i++) {
 459                 if (ra_lmap[i] != ra_lmapglob[i]) {
 460                         ra_lmap[i] = ra_lmapglob[i];
 461                         loc_toreg(ra_lmap[i], 0, i, ULNG);
 462                 }
 463         }
 464 }
 465
 466 /* perform global register allocation */
 467 static void ra_glob(struct ic *ic, int ic_n)
 468 {
 469         int *srt;
 470         long mask;
 471         int nregs;
 472         int i, j;
 473         mask = func_leaf ? R_TMPS : R_PERM;
 474         nregs = MIN(N_TMPS >> 1, 4);
 475         srt = malloc(loc_n * sizeof(srt[0]));
 476         /* sorting locals */
 477         for (i = 0; i < loc_n; i++) {
 478                 for (j = i - 1; j >= 0 && loc_dat[i] > loc_dat[srt[j]]; j--)
 479                         srt[j + 1] = srt[j];
 480                 srt[j + 1] = i;
 481         }
 482         /* allocating registers */
 483         for (i = 0; i < loc_n && nregs > 0; i++) {
 484                 int l = srt[i];
 485                 if (loc_ptr[l])
 486                         continue;
 487                 if (func_leaf && l < N_ARGS && l < func_argc &&
 488                                 ra_lmapglob[argregs[l]] < 0) {
 489                         ra_lmapglob[argregs[l]] = l;
 490                         nregs--;
 491                         continue;
 492                 }
 493                 if (loc_dat[l] < 2)
 494                         continue;
 495                 for (j = func_leaf ? 1 : 3; j < N_TMPS; j++) {
 496                         int r = tmpregs[j];
 497                         if (ra_lmapglob[r] < 0 && (1 << r) & mask) {
 498                                 ra_lmapglob[r] = l;
 499                                 nregs--;
 500                                 break;
 501                         }
 502                 }
 503         }
 504         free(srt);
 505 }
 506
 507 /* return the values written to and read from in the given instruction */
 508 static void ic_info(struct ic *ic, long **w, long **r1, long **r2, long **r3)
 509 {
 510         long n = ic_regcnt(ic);
 511         long o = ic->op & O_OUT;
 512         *r1 = NULL;
 513         *r2 = NULL;
 514         *r3 = NULL;
 515         *w = NULL;
 516         if (o) {
 517                 *w = &ic->arg0;
 518                 *r1 = n >= 2 ? &ic->arg1 : NULL;
 519                 *r2 = n >= 3 ? &ic->arg2 : NULL;
 520         } else {
 521                 *r1 = n >= 1 ? &ic->arg0 : NULL;
 522                 *r2 = n >= 2 ? &ic->arg1 : NULL;
 523                 *r3 = n >= 3 ? &ic->arg2 : NULL;
 524         }
 525 }
 526
 527 static void ra_init(struct ic *ic, int ic_n)
 528 {
 529         long m0, m1, m2, mt;
 530         int *loc_sz;
 531         int i, j;
 532         ic_luse = calloc(ic_n, sizeof(ic_luse[0]));
 533         ic_bbeg = calloc(ic_n, sizeof(ic_bbeg[0]));
 534         ra_gmask = calloc(ic_n, sizeof(ra_gmask[0]));
 535         loc_mem = calloc(loc_n, sizeof(loc_mem[0]));
 536         /* ic_luse */
 537         for (i = ic_n - 1; i >= 0; --i) {
 538                 long *w, *r1, *r2, *r3;
 539                 ic_info(ic + i, &w, &r1, &r2, &r3);
 540                 if (!ic_luse[i])
 541                         if (!w || ic[i].op & O_CALL)
 542                                 ic_luse[i] = -1;
 543                 if (!ic_luse[i])
 544                         continue;
 545                 if (r1 && !ic_luse[*r1])
 546                         ic_luse[*r1] = i;
 547                 if (r2 && !ic_luse[*r2])
 548                         ic_luse[*r2] = i;
 549                 if (r3 && !ic_luse[*r3])
 550                         ic_luse[*r3] = i;
 551                 if (ic[i].op & O_CALL)
 552                         for (j = 0; j < ic[i].arg2; j++)
 553                                 if (!ic_luse[ic[i].args[j]])
 554                                         ic_luse[ic[i].args[j]] = i;
 555         }
 556         /* ic_bbeg */
 557         for (i = 0; i < ic_n; i++) {
 558                 if (!ic_luse[i])
 559                         continue;
 560                 if (i + 1 < ic_n && ic[i].op & (O_JXX | O_RET))
 561                         ic_bbeg[i + 1] = 1;
 562                 if (ic[i].op & O_JXX && ic[i].arg2 < ic_n)
 563                         ic_bbeg[ic[i].arg2] = 1;
 564         }
 565         /* ra_gmask */
 566         for (i = 0; i < ic_n; i++) {
 567                 int n = ic_regcnt(ic + i);
 568                 int op = ic[i].op;
 569                 if (!ic_luse[i])
 570                         continue;
 571                 i_reg(op, &m0, &m1, &m2, &mt);
 572                 if (n >= 1 && !(op & O_OUT))
 573                         ra_gmask[ic[i].arg0] = m0;
 574                 if (n >= 2)
 575                         ra_gmask[ic[i].arg1] = m1;
 576                 if (n >= 3)
 577                         ra_gmask[ic[i].arg2] = m2;
 578                 if (op & O_CALL)
 579                         for (j = 0; j < MIN(N_ARGS, ic[i].arg2); j++)
 580                                 ra_gmask[ic[i].args[j]] = 1 << argregs[j];
 581         }
 582         /* loc_ptr and loc_dat */
 583         loc_ptr = calloc(loc_n, sizeof(loc_ptr[0]));
 584         loc_dat = calloc(loc_n, sizeof(loc_dat[0]));
 585         loc_sz = calloc(loc_n, sizeof(loc_sz[0]));
 586         for (i = 0; i < ic_n; i++) {
 587                 long oc = O_C(ic[i].op);
 588                 if (!ic_luse[i])
 589                         continue;
 590                 if (oc == (O_LD | O_LOC) || oc == (O_ST | O_LOC)) {
 591                         int loc = ic[i].arg1;
 592                         int sz = T_SZ(O_T(ic[i].op));
 593                         if (!loc_sz[loc])
 594                                 loc_sz[loc] = sz;
 595                         if (ic[i].arg2 || sz < 2 || sz != loc_sz[loc])
 596                                 loc_ptr[loc]++;
 597                         else
 598                                 loc_dat[loc]++;
 599                 }
 600                 if (oc == (O_MOV | O_LOC))
 601                         loc_ptr[ic[i].arg1]++;
 602         }
 603         free(loc_sz);
 604         /* func_leaf */
 605         func_leaf = 1;
 606         for (i = 0; i < ic_n; i++)
 607                 if (ic_luse[i] && ic[i].op & O_CALL)
 608                         func_leaf = 0;
 609         /* ra_vmap */
 610         for (i = 0; i < LEN(ra_vmap); i++)
 611                 ra_vmap[i] = -1;
 612         /* ra_lmap */
 613         for (i = 0; i < N_REGS; i++)
 614                 ra_lmapglob[i] = -1;
 615         ra_glob(ic, ic_n);
 616         memcpy(ra_lmap, ra_lmapglob, sizeof(ra_lmap));
 617         for (i = 0; i < LEN(ra_lmapglob); i++)
 618                 if (ra_lmapglob[i] >= 0)
 619                         func_regs |= (1 << i);
 620         /* ra_live */
 621         for (i = 0; i < LEN(ra_live); i++)
 622                 ra_live[i] = -1;
 623         ra_vmax = 0;
 624         func_maxargs = 0;
 625 }
 626
 627 static void ra_done(void)
 628 {
 629         free(ic_luse);
 630         free(ic_bbeg);
 631         free(ra_gmask);
 632         free(loc_mem);
 633         free(loc_ptr);
 634         free(loc_dat);
 635 }
 636
 637 static void ic_gencode(struct ic *ic, int ic_n)
 638 {
 639         int r0, r1, r2;
 640         long mt;
 641         int i, j;
 642         /* loading arguments in their allocated registers */
 643         for (i = 0; i < LEN(ra_lmap); i++) {
 644                 int loc = ra_lmap[i];
 645                 if (loc >= 0 && loc < func_argc)
 646                         if (loc >= N_ARGS || i != argregs[loc])
 647                                 loc_toreg(loc, 0, i, ULNG);
 648         }
 649         /* generating code */
 650         for (i = 0; i < ic_n; i++) {
 651                 long op = ic[i].op;
 652                 long oc = O_C(op);
 653                 int n = ic_regcnt(ic + i);
 654                 i_label(i);
 655                 if (!ic_luse[i])
 656                         continue;
 657                 ra_map(ic + i, &r0, &r1, &r2, &mt);
 658                 if (oc & O_CALL) {
 659                         int argc = ic[i].arg2;
 660                         int aregs = MIN(N_ARGS, argc);
 661                         /* arguments passed via stack */
 662                         for (j = argc - 1; j >= aregs; --j) {
 663                                 int v = ic[i].args[j];
 664                                 int rx = ra_vreg(v) >= 0 ? ra_vreg(v) : r0;
 665                                 ra_vload(v, rx);
 666                                 i_ins(O_MK(O_ST | O_NUM, ULNG), rx, REG_SP,
 667                                         (j - aregs) * ULNG);
 668                                 ra_vdrop(v);
 669                         }
 670                         func_maxargs = MAX(func_maxargs, argc - aregs);
 671                         /* arguments passed via registers */
 672                         for (j = aregs - 1; j >= 0; --j)
 673                                 ra_vload(ic[i].args[j], argregs[j]);
 674                 }
 675                 /* loading the operands */
 676                 if (n >= 1 && !(oc & O_OUT))
 677                         ra_vload(ic[i].arg0, r0);
 678                 if (n >= 2 && !(oc & O_LOC))
 679                         ra_vload(ic[i].arg1, r1);
 680                 if (n >= 3)
 681                         ra_vload(ic[i].arg2, r2);
 682                 /* dropping values that are no longer used */
 683                 for (j = 0; j < LEN(ra_live); j++)
 684                         if (ra_live[j] >= 0 && ic_luse[ra_live[j]] <= i)
 685                                 ra_vdrop(ra_live[j]);
 686                 /* saving values stored in registers that may change */
 687                 for (j = 0; j < N_REGS; j++)
 688                         if (mt & (1 << j))
 689                                 ra_spill(j);
 690                 /* overwriting a value that is needed later (unless loading a local to its register) */
 691                 if (n >= 1 && oc & O_OUT)
 692                         if (oc != (O_LD | O_LOC) || ra_lmap[r0] != ic[i].arg1 ||
 693                                         ra_vmap[r0] >= 0)
 694                                 ra_spill(r0);
 695                 /* before the last instruction of a basic block; for jumps */
 696                 if (i + 1 < ic_n && ic_bbeg[i + 1] && oc & O_JXX)
 697                         ra_bbend();
 698                 /* performing the instruction */
 699                 if (oc & O_BOP)
 700                         i_ins(op, r0, r1, oc & O_NUM ? ic[i].arg2 : r2);
 701                 if (oc & O_UOP)
 702                         i_ins(op, r0, r1, r2);
 703                 if (oc == (O_LD | O_NUM))
 704                         i_ins(op, r0, r1, ic[i].arg2);
 705                 if (oc == (O_LD | O_LOC))
 706                         ra_lload(ic[i].arg1, ic[i].arg2, r0, O_T(op));
 707                 if (oc == (O_ST | O_NUM))
 708                         i_ins(op, r0, r1, ic[i].arg2);
 709                 if (oc == (O_ST | O_LOC))
 710                         ra_lsave(ic[i].arg1, ic[i].arg2, r0, O_T(op));
 711                 if (oc == O_RET)
 712                         i_ins(op, r0, 0, 0);
 713                 if (oc == O_MOV)
 714                         i_ins(op, r0, r0, 0);
 715                 if (oc == (O_MOV | O_NUM))
 716                         i_ins(op, r0, ic[i].arg1, 0);
 717                 if (oc == (O_MOV | O_LOC))
 718                         loc_toadd(ic[i].arg1, ic[i].arg2, r0);
 719                 if (oc == (O_MOV | O_SYM))
 720                         i_ins(op, r0, ic[i].arg1, ic[i].arg2);
 721                 if (oc == O_CALL)
 722                         i_ins(op, r0, r1, 0);
 723                 if (oc == (O_CALL | O_SYM))
 724                         i_ins(op, r0, ic[i].arg1, 0);
 725                 if (oc == O_JMP)
 726                         i_ins(op, 0, 0, ic[i].arg2);
 727                 if (oc & O_JZ)
 728                         i_ins(op, r0, 0, ic[i].arg2);
 729                 if (oc & O_JCC)
 730                         i_ins(op, r0, oc & O_NUM ? ic[i].arg1 : r1, ic[i].arg2);
 731                 if (oc == O_MSET)
 732                         i_ins(op, r0, r1, r2);
 733                 if (oc == O_MCPY)
 734                         i_ins(op, r0, r1, r2);
 735                 /* saving back the output register */
 736                 if (oc & O_OUT)
 737                         ra_vsave(ic[i].arg0, r0);
 738                 /* after the last instruction of a basic block */
 739                 if (i + 1 < ic_n && ic_bbeg[i + 1] && !(oc & O_JXX))
 740                         ra_bbend();
 741         }
 742         i_label(ic_n);
 743 }
 744
 745 static void ic_reset(void)
 746 {
 747         o_tmpdrop(-1);
 748         o_back(0);
 749         free(loc_off);
 750         loc_off = NULL;
 751         loc_n = 0;
 752         loc_sz = 0;
 753         loc_pos = I_LOC0;
 754 }
 755
 756 void o_func_beg(char *name, int argc, int global, int varg)
 757 {
 758         int i;
 759         func_argc = argc;
 760         func_varg = varg;
 761         func_regs = 0;
 762         ic_reset();
 763         for (i = 0; i < argc; i++)
 764                 loc_add(I_ARG0 + -i * ULNG);
 765         out_def(name, (global ? OUT_GLOB : 0) | OUT_CS, mem_len(&cs), 0);
 766 }
 767
 768 void o_code(char *name, char *c, long c_len)
 769 {
 770         out_def(name, OUT_CS, mem_len(&cs), 0);
 771         mem_put(&cs, c, c_len);
 772 }
 773
 774 void o_func_end(void)
 775 {
 776         struct ic *ic;
 777         long ic_n, spsub;
 778         long sargs = 0;
 779         long sargs_last = -1;
 780         long sregs_pos;
 781         char *c;
 782         long c_len, *rsym, *rflg, *roff, rcnt;
 783         int locs = 0;                   /* accessing locals on the stack */
 784         int i;
 785         ic_get(&ic, &ic_n);             /* the intermediate code */
 786         ra_init(ic, ic_n);              /* initialize register allocation */
 787         ic_gencode(ic, ic_n);           /* generating machine code */
 788         /* deciding which arguments to save */
 789         for (i = 0; i < func_argc; i++)
 790                 if (loc_mem[i])
 791                         sargs_last = i + 1;
 792         for (i = 0; i < N_ARGS && (func_varg || i < sargs_last); i++)
 793                 sargs |= 1 << argregs[i];
 794         /* computing the amount of stack subtraction */
 795         for (i = 0; i < loc_n; i++)
 796                 if (loc_mem[i])
 797                         locs = 1;
 798         spsub = (locs || ra_vmax) ? loc_pos + ra_vmax * ULNG : 0;
 799         for (i = 0; i < N_TMPS; i++)
 800                 if (((1 << tmpregs[i]) & func_regs & R_PERM) != 0)
 801                         spsub += ULNG;
 802         sregs_pos = spsub;
 803         spsub += func_maxargs * ULNG;
 804         /* adding function prologue and epilogue */
 805         i_wrap(func_argc, sargs, spsub, spsub || locs || !func_leaf,
 806                 func_regs & R_PERM, -sregs_pos);
 807         ra_done();
 808         i_code(&c, &c_len, &rsym, &rflg, &roff, &rcnt);
 809         for (i = 0; i < rcnt; i++)      /* adding the relocations */
 810                 out_rel(rsym[i], rflg[i], roff[i] + mem_len(&cs));
 811         mem_put(&cs, c, c_len);         /* appending function code */
 812         free(c);
 813         free(rsym);
 814         free(rflg);
 815         free(roff);
 816         for (i = 0; i < ic_n; i++)
 817                 if (ic[i].op & O_CALL)
 818                         free(ic[i].args);
 819         free(ic);
 820         ic_reset();
 821 }
 822
 823 void o_write(int fd)
 824 {
 825         i_done();
 826         out_write(fd, mem_buf(&cs), mem_len(&cs), mem_buf(&ds), mem_len(&ds));
 827         free(loc_off);
 828         free(ds_name);
 829         free(ds_off);
 830         mem_done(&cs);
 831         mem_done(&ds);
 832 }