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
  15 static char (*ds_name)[NAMELEN];/* data section symbols */
  16 static long *ds_off;            /* data section offsets */
  17 static long ds_n, ds_sz;        /* number of data section symbols */
  18
  19 static int func_argc;           /* number of arguments */
  20 static int func_varg;           /* varargs */
  21 static int func_regs;           /* used registers */
  22
  23 static long loc_add(long pos)
  24 {
  25         if (loc_n >= loc_sz) {
  26                 loc_sz = MAX(128, loc_sz * 2);
  27                 loc_off = mextend(loc_off, loc_n, loc_sz, sizeof(loc_off[0]));
  28         }
  29         loc_off[loc_n] = pos;
  30         return loc_n++;
  31 }
  32
  33 long o_mklocal(long sz)
  34 {
  35         loc_pos += ALIGN(sz, ULNG);
  36         return loc_add(loc_pos);
  37 }
  38
  39 void o_rmlocal(long addr, long sz)
  40 {
  41 }
  42
  43 long o_arg2loc(int i)
  44 {
  45         return i;
  46 }
  47
  48 void o_bsnew(char *name, long size, int global)
  49 {
  50         out_def(name, OUT_BSS | (global ? OUT_GLOB : 0), bsslen, size);
  51         bsslen += ALIGN(size, OUT_ALIGNMENT);
  52 }
  53
  54 long o_dsnew(char *name, long size, int global)
  55 {
  56         int idx;
  57         if (ds_n >= ds_sz) {
  58                 ds_sz = MAX(128, ds_sz * 2);
  59                 ds_name = mextend(ds_name, ds_n, ds_sz, sizeof(ds_name[0]));
  60                 ds_off = mextend(ds_off, ds_n, ds_sz, sizeof(ds_off[0]));
  61         }
  62         idx = ds_n++;
  63         strcpy(ds_name[idx], name);
  64         ds_off[idx] = mem_len(&ds);
  65         out_def(name, OUT_DS | (global ? OUT_GLOB : 0), mem_len(&ds), size);
  66         mem_putz(&ds, ALIGN(size, OUT_ALIGNMENT));
  67         return ds_off[idx];
  68 }
  69
  70 void o_dscpy(long addr, void *buf, long len)
  71 {
  72         mem_cpy(&ds, addr, buf, len);
  73 }
  74
  75 static int dat_off(char *name)
  76 {
  77         int i;
  78         for (i = 0; i < ds_n; i++)
  79                 if (!strcmp(name, ds_name[i]))
  80                         return ds_off[i];
  81         return 0;
  82 }
  83
  84 void o_dsset(char *name, long off, long bt)
  85 {
  86         long sym_off = dat_off(name) + off;
  87         long num, roff, rsym;
  88         if (!o_popnum(&num)) {
  89                 mem_cpy(&ds, sym_off, &num, T_SZ(bt));
  90                 return;
  91         }
  92         if (!o_popsym(&rsym, &roff)) {
  93                 out_rel(rsym, OUT_DS, sym_off);
  94                 mem_cpy(&ds, sym_off, &roff, T_SZ(bt));
  95         }
  96 }
  97
  98 /* number of register arguments */
  99 static int ic_regcnt(struct ic *ic)
 100 {
 101         long o = ic->op;
 102         if (o & O_BOP)
 103                 return o & (O_NUM | O_SYM | O_LOC) ? 2 : 3;
 104         if (o & O_UOP)
 105                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 106         if (o & O_CALL)
 107                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 108         if (o & O_MOV)
 109                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 110         if (o & O_MEM)
 111                 return 3;
 112         if (o & O_JMP)
 113                 return 0;
 114         if (o & O_JZ)
 115                 return 1;
 116         if (o & O_JCC)
 117                 return o & (O_NUM | O_SYM | O_LOC) ? 1 : 2;
 118         if (o & O_RET)
 119                 return 1;
 120         if (o & (O_LD | O_ST) && o & (O_SYM | O_LOC))
 121                 return 1;
 122         if (o & (O_LD | O_ST))
 123                 return o & O_NUM ? 2 : 3;
 124         return 0;
 125 }
 126
 127 static long *iv_use;            /* the last time each value is used */
 128 static long *iv_gmask;          /* the mask of good registers for each value */
 129 static long *iv_bbeg;           /* whether each instruction begins a basic block */
 130 static long *iv_pos;            /* the current position of each value */
 131 static long iv_regmap[N_REGS];  /* the value stored in each register */
 132 static long iv_live[NTMPS];     /* live values */
 133 static int iv_maxlive;          /* the number of values stored on the stack */
 134 static int iv_maxargs;          /* the maximum number of arguments on the stack */
 135
 136 /* find a register, with the given good, acceptable, and bad registers */
 137 static long iv_map(long iv, long gmask, long amask, long bmask)
 138 {
 139         int i;
 140         gmask &= ~bmask & amask;
 141         amask &= ~bmask;
 142         if (iv_pos[iv] >= 0 && (1 << iv_pos[iv]) & (gmask | amask))
 143                 return iv_pos[iv];
 144         for (i = 0; i < N_TMPS; i++)
 145                 if ((1 << tmpregs[i]) & gmask && iv_regmap[tmpregs[i]] < 0)
 146                         return tmpregs[i];
 147         for (i = 0; i < N_TMPS; i++)
 148                 if ((1 << tmpregs[i]) & amask && iv_regmap[tmpregs[i]] < 0)
 149                         return tmpregs[i];
 150         for (i = 0; i < N_TMPS; i++)
 151                 if ((1 << tmpregs[i]) & gmask)
 152                         return tmpregs[i];
 153         for (i = 0; i < N_TMPS; i++)
 154                 if ((1 << tmpregs[i]) & amask)
 155                         return tmpregs[i];
 156         die("neatcc: cannot allocate an acceptable register\n");
 157         return 0;
 158 }
 159
 160 /* allocate registers for a 3 operand instruction */
 161 static void ic_map(struct ic *ic, int *r0, int *r1, int *r2, long *mt)
 162 {
 163         long m0, m1, m2;
 164         long all = 0;
 165         int n = ic_regcnt(ic);
 166         int oc = O_C(ic->op);
 167         int i;
 168         *r0 = 0;
 169         *r1 = 0;
 170         *r2 = 0;
 171         *mt = 0;
 172         if (oc & O_CALL)
 173                 for (i = 0; i < MIN(ic->arg2, N_ARGS); i++)
 174                         all |= (1 << argregs[i]);
 175         if (oc & O_LOC) {
 176                 if (oc & O_MOV)
 177                         oc = O_ADD | O_NUM;
 178                 if (oc & (O_ST | O_LD))
 179                         oc = (oc & ~O_LOC) & O_NUM;
 180         }
 181         if (i_reg(ic->op, &m0, &m1, &m2, mt))
 182                 die("neatcc: instruction %08lx not supported\n", ic->op);
 183         if (n >= 3) {
 184                 *r2 = iv_map(ic->arg2, m2, m2, all);
 185                 all |= (1 << *r2);
 186         }
 187         if (n >= 2) {
 188                 *r1 = iv_map(ic->arg1, m1, m1, all);
 189                 all |= (1 << *r1);
 190         }
 191         if (n >= 1 && m0) {
 192                 int wop = ic->op & O_OUT;
 193                 if (wop && n >= 3 && m0 & (1 << *r2))
 194                         *r0 = *r2;
 195                 else if (wop && n >= 2 && m0 & (1 << *r1))
 196                         *r0 = *r1;
 197                 else
 198                         *r0 = iv_map(ic->arg0, iv_gmask[ic->arg0],
 199                                 m0, wop ? 0 : all);
 200         }
 201         if (n >= 1 && !m0)
 202                 *r0 = *r1;
 203         if (n)
 204                 all |= *r0;
 205         func_regs |= all | *mt;
 206 }
 207
 208 static long iv_rank(long iv)
 209 {
 210         int i;
 211         for (i = 0; i < LEN(iv_live); i++)
 212                 if (iv_live[i] == iv)
 213                         return i;
 214         die("neatcc: the specified value is not live\n");
 215         return 0;
 216 }
 217
 218 static long iv_addr(long rank)
 219 {
 220         return loc_pos + rank * ULNG + ULNG;
 221 }
 222
 223 /* move the value to the stack */
 224 static void iv_spill(long iv)
 225 {
 226         if (iv_pos[iv] >= 0) {
 227                 long rank = iv_rank(iv);
 228                 iv_maxlive = MAX(iv_maxlive, rank + 1);
 229                 i_ins(O_MK(O_ST | O_NUM, ULNG), iv_pos[iv], REG_FP, -iv_addr(rank));
 230                 iv_regmap[iv_pos[iv]] = -1;
 231                 iv_pos[iv] = -1;
 232         }
 233 }
 234
 235 /* set the value to the given register */
 236 static void iv_save(long iv, int reg)
 237 {
 238         int i;
 239         iv_regmap[reg] = iv;
 240         iv_pos[iv] = reg;
 241         for (i = 0; i < LEN(iv_live); i++)
 242                 if (iv_live[i] < 0)
 243                         break;
 244         if (i == LEN(iv_live))
 245                 die("neatcc: too many live values\n");
 246         iv_live[i] = iv;
 247 }
 248
 249 /* load the value into a register */
 250 static void iv_load(long iv, int reg)
 251 {
 252         if (iv_regmap[reg] == iv)
 253                 return;
 254         if (iv_regmap[reg] >= 0)
 255                 iv_spill(iv_regmap[reg]);
 256         if (iv_pos[iv] >= 0) {
 257                 iv_regmap[iv_pos[iv]] = -1;
 258                 i_ins(O_MK(O_MOV, ULNG), reg, iv_pos[iv], 0);
 259         } else {
 260                 i_ins(O_MK(O_LD | O_NUM, ULNG), reg, REG_FP, -iv_addr(iv_rank(iv)));
 261         }
 262         iv_regmap[reg] = iv;
 263         iv_pos[iv] = reg;
 264 }
 265
 266 /* the value is no longer needed */
 267 static void iv_drop(long iv)
 268 {
 269         int i;
 270         for (i = 0; i < LEN(iv_live); i++)
 271                 if (iv_live[i] == iv)
 272                         iv_live[i] = -1;
 273         if (iv_pos[iv] >= 0) {
 274                 iv_regmap[iv_pos[iv]] = -1;
 275                 iv_pos[iv] = -1;
 276         }
 277 }
 278
 279 /* return the values written to and read from in the given instruction */
 280 static void ic_info(struct ic *ic, long **w, long **r1, long **r2, long **r3)
 281 {
 282         long n = ic_regcnt(ic);
 283         long o = ic->op & O_OUT;
 284         *r1 = NULL;
 285         *r2 = NULL;
 286         *r3 = NULL;
 287         *w = NULL;
 288         if (o) {
 289                 *w = &ic->arg0;
 290                 *r1 = n >= 2 ? &ic->arg1 : NULL;
 291                 *r2 = n >= 3 ? &ic->arg2 : NULL;
 292         } else {
 293                 *r1 = n >= 1 ? &ic->arg0 : NULL;
 294                 *r2 = n >= 2 ? &ic->arg1 : NULL;
 295                 *r3 = n >= 3 ? &ic->arg2 : NULL;
 296         }
 297 }
 298
 299 static void iv_init(struct ic *ic, int ic_n)
 300 {
 301         long m0, m1, m2, mt;
 302         int i, j;
 303         iv_use = calloc(ic_n, sizeof(iv_use[0]));
 304         iv_gmask = calloc(ic_n, sizeof(iv_gmask[0]));
 305         iv_bbeg = calloc(ic_n, sizeof(iv_bbeg[0]));
 306         iv_pos = malloc(ic_n * sizeof(iv_pos[0]));
 307         /* iv_use */
 308         for (i = ic_n - 1; i >= 0; --i) {
 309                 long *w, *r1, *r2, *r3;
 310                 ic_info(ic + i, &w, &r1, &r2, &r3);
 311                 if (!iv_use[i])
 312                         if (!w || ic[i].op & O_CALL)
 313                                 iv_use[i] = i;
 314                 if (!iv_use[i])
 315                         continue;
 316                 if (r1 && !iv_use[*r1])
 317                         iv_use[*r1] = i;
 318                 if (r2 && !iv_use[*r2])
 319                         iv_use[*r2] = i;
 320                 if (r3 && !iv_use[*r3])
 321                         iv_use[*r3] = i;
 322                 if (ic[i].op & O_CALL)
 323                         for (j = 0; j < ic[i].arg2; j++)
 324                                 if (!iv_use[ic[i].args[j]])
 325                                         iv_use[ic[i].args[j]] = i;
 326         }
 327         /* iv_gmask */
 328         for (i = 0; i < ic_n; i++) {
 329                 int n = ic_regcnt(ic + i);
 330                 int op = ic[i].op;
 331                 if (!iv_use[i])
 332                         continue;
 333                 i_reg(op, &m0, &m1, &m2, &mt);
 334                 if (n >= 1 && !(op & O_OUT))
 335                         iv_gmask[ic[i].arg0] = m0;
 336                 if (n >= 2)
 337                         iv_gmask[ic[i].arg1] = m1;
 338                 if (n >= 3)
 339                         iv_gmask[ic[i].arg2] = m2;
 340                 if (op & O_CALL)
 341                         for (j = 0; j < MIN(N_ARGS, ic[i].arg2); j++)
 342                                 iv_gmask[ic[i].args[j]] = 1 << argregs[j];
 343         }
 344         /* iv_bbeg */
 345         for (i = 0; i < ic_n; i++) {
 346                 if (!iv_use[i])
 347                         continue;
 348                 if (i + 1 < ic_n && ic[i].op & (O_JXX | O_CALL | O_RET))
 349                         iv_bbeg[i + 1] = 1;
 350                 if (ic[i].op & O_JXX && ic[i].arg2 < ic_n)
 351                         iv_bbeg[ic[i].arg2] = 1;
 352         }
 353         /* iv_pos */
 354         for (i = 0; i < ic_n; i++)
 355                 iv_pos[i] = -1;
 356         /* iv_regmap */
 357         for (i = 0; i < LEN(iv_regmap); i++)
 358                 iv_regmap[i] = -1;
 359         /* iv_live */
 360         for (i = 0; i < LEN(iv_live); i++)
 361                 iv_live[i] = -1;
 362         iv_maxlive = 0;
 363         iv_maxargs = 0;
 364 }
 365
 366 static void iv_done(void)
 367 {
 368         free(iv_use);
 369         free(iv_gmask);
 370         free(iv_bbeg);
 371         free(iv_pos);
 372 }
 373
 374 static void ic_gencode(struct ic *ic, int ic_n)
 375 {
 376         int r0, r1, r2;
 377         long mt;
 378         int i, j;
 379         iv_init(ic, ic_n);
 380         for (i = 0; i < ic_n; i++) {
 381                 long op = ic[i].op;
 382                 long oc = O_C(op);
 383                 int n = ic_regcnt(ic + i);
 384                 i_label(i);
 385                 if (!iv_use[i])
 386                         continue;
 387                 ic_map(ic + i, &r0, &r1, &r2, &mt);
 388                 if (oc & O_CALL) {
 389                         int argc = ic[i].arg2;
 390                         int aregs = MIN(N_ARGS, argc);
 391                         /* arguments passed via stack */
 392                         for (j = argc - 1; j >= aregs; --j) {
 393                                 int v = ic[i].args[j];
 394                                 int rx = iv_pos[v] >= 0 ? iv_pos[v] : r0;
 395                                 iv_load(v, rx);
 396                                 i_ins(O_MK(O_ST | O_NUM, ULNG), rx, REG_SP,
 397                                         (j - aregs) * ULNG);
 398                                 iv_drop(v);
 399                         }
 400                         iv_maxargs = MAX(iv_maxargs, argc - aregs);
 401                         /* arguments passed via registers */
 402                         for (j = aregs - 1; j >= 0; --j)
 403                                 iv_load(ic[i].args[j], argregs[j]);
 404                 }
 405                 /* loading the arguments */
 406                 if (n >= 1 && !(oc & O_OUT))
 407                         iv_load(ic[i].arg0, r0);
 408                 if (n >= 2 && !(oc & O_LOC))
 409                         iv_load(ic[i].arg1, r1);
 410                 if (n >= 3)
 411                         iv_load(ic[i].arg2, r2);
 412                 /* saving values stored in registers that may change */
 413                 for (j = 0; j < N_REGS; j++)
 414                         if (iv_regmap[j] >= 0 && mt & (1 << j))
 415                                 iv_spill(iv_regmap[j]);
 416                 /* overwriting a value that is needed later */
 417                 if (n >= 1 && oc & O_OUT && iv_regmap[r0] >= 0)
 418                         if (iv_use[iv_regmap[r0]] > i)
 419                                 iv_spill(iv_regmap[r0]);
 420                 /* dropping values that are no longer used */
 421                 for (j = 0; j < LEN(iv_live); j++)
 422                         if (iv_live[j] >= 0 && iv_use[iv_live[j]] <= i)
 423                                 iv_drop(iv_live[j]);
 424                 /* the last instruction of a basic block */
 425                 if (i + 1 < ic_n && iv_bbeg[i + 1])
 426                         for (j = 0; j < LEN(iv_live); j++)
 427                                 if (iv_live[j] >= 0)
 428                                         iv_spill(iv_live[j]);
 429                 /* performing the instruction */
 430                 if (oc & O_BOP)
 431                         i_ins(op, r0, r1, oc & O_NUM ? ic[i].arg2 : r2);
 432                 if (oc & O_UOP)
 433                         i_ins(op, r0, r1, r2);
 434                 if (oc == (O_LD | O_NUM))
 435                         i_ins(op, r0, r1, ic[i].arg2);
 436                 if (oc == (O_LD | O_LOC))
 437                         i_ins((op & ~O_LOC) | O_NUM, r0, REG_FP,
 438                                 -loc_off[ic[i].arg1] + ic[i].arg2);
 439                 if (oc == (O_ST | O_NUM))
 440                         i_ins(op, r0, r1, ic[i].arg2);
 441                 if (oc == (O_ST | O_LOC))
 442                         i_ins((op & ~O_LOC) | O_NUM , r0, REG_FP,
 443                                 -loc_off[ic[i].arg1] + ic[i].arg2);
 444                 if (oc == O_RET)
 445                         i_ins(op, r0, 0, 0);
 446                 if (oc == O_MOV)
 447                         i_ins(op, r0, r0, 0);
 448                 if (oc == (O_MOV | O_NUM))
 449                         i_ins(op, r0, ic[i].arg1, 0);
 450                 if (oc == (O_MOV | O_LOC))
 451                         i_ins(O_ADD | O_NUM, r0, REG_FP,
 452                                 -loc_off[ic[i].arg1] + ic[i].arg2);
 453                 if (oc == (O_MOV | O_SYM))
 454                         i_ins(op, r0, ic[i].arg1, ic[i].arg2);
 455                 if (oc == O_CALL)
 456                         i_ins(op, r0, r1, 0);
 457                 if (oc == (O_CALL | O_SYM))
 458                         i_ins(op, r0, ic[i].arg1, 0);
 459                 if (oc == O_JMP)
 460                         i_ins(op, 0, 0, ic[i].arg2);
 461                 if (oc & O_JZ)
 462                         i_ins(op, r0, 0, ic[i].arg2);
 463                 if (oc & O_JCC)
 464                         i_ins(op, r0, oc & O_NUM ? ic[i].arg1 : r1, ic[i].arg2);
 465                 if (oc == O_MSET)
 466                         i_ins(op, r0, r1, r2);
 467                 if (oc == O_MCPY)
 468                         i_ins(op, r0, r1, r2);
 469                 /* saving back the output register */
 470                 if (oc & O_OUT)
 471                         iv_save(ic[i].arg0, r0);
 472         }
 473         i_label(ic_n);
 474         iv_done();
 475 }
 476
 477 static void ic_reset(void)
 478 {
 479         o_tmpdrop(-1);
 480         o_back(0);
 481         free(loc_off);
 482         loc_off = NULL;
 483         loc_n = 0;
 484         loc_sz = 0;
 485         loc_pos = I_LOC0;
 486 }
 487
 488 void o_func_beg(char *name, int argc, int global, int varg)
 489 {
 490         int i;
 491         func_argc = argc;
 492         func_varg = varg;
 493         func_regs = 0;
 494         ic_reset();
 495         for (i = 0; i < argc; i++)
 496                 loc_add(I_ARG0 + -i * ULNG);
 497         out_def(name, (global ? OUT_GLOB : 0) | OUT_CS, mem_len(&cs), 0);
 498 }
 499
 500 void o_code(char *name, char *c, long c_len)
 501 {
 502         out_def(name, OUT_CS, mem_len(&cs), 0);
 503         mem_put(&cs, c, c_len);
 504 }
 505
 506 void o_func_end(void)
 507 {
 508         struct ic *ic;
 509         long ic_n, spsub;
 510         long sargs = 0;
 511         long sregs_pos;
 512         char *c;
 513         long c_len, *rsym, *rflg, *roff, rcnt;
 514         int i;
 515         ic_get(&ic, &ic_n);             /* the intermediate code */
 516         ic_gencode(ic, ic_n);           /* generating machine code */
 517         /* adding function prologue and epilogue */
 518         for (i = 0; i < N_ARGS && (func_varg || i < func_argc); i++)
 519                 sargs |= 1 << argregs[i];
 520         spsub = loc_pos + iv_maxlive * ULNG;
 521         for (i = 0; i < N_TMPS; i++)
 522                 if ((func_regs & R_PERM) != 0)
 523                         spsub += ULNG;
 524         sregs_pos = spsub;
 525         spsub += iv_maxargs * ULNG;
 526         i_wrap(func_argc, sargs, spsub, spsub || func_argc,
 527                 R_PERM & func_regs, -sregs_pos);
 528         i_code(&c, &c_len, &rsym, &rflg, &roff, &rcnt);
 529         for (i = 0; i < rcnt; i++)      /* adding the relocations */
 530                 out_rel(rsym[i], rflg[i], roff[i] + mem_len(&cs));
 531         mem_put(&cs, c, c_len);         /* appending function code */
 532         free(c);
 533         free(rsym);
 534         free(rflg);
 535         free(roff);
 536         for (i = 0; i < ic_n; i++)
 537                 if (ic[i].op & O_CALL)
 538                         free(ic[i].args);
 539         free(ic);
 540         ic_reset();
 541 }
 542
 543 void o_write(int fd)
 544 {
 545         i_done();
 546         out_write(fd, mem_buf(&cs), mem_len(&cs), mem_buf(&ds), mem_len(&ds));
 547         free(loc_off);
 548         free(ds_name);
 549         free(ds_off);
 550         mem_done(&cs);
 551         mem_done(&ds);
 552 }