gen.c (21406B)
1 #include "c.h" 2 3 4 #define readsreg(p) \ 5 (generic((p)->op)==INDIR && (p)->kids[0]->op==VREG+P) 6 #define setsrc(d) ((d) && (d)->x.regnode && \ 7 (d)->x.regnode->set == src->x.regnode->set && \ 8 (d)->x.regnode->mask&src->x.regnode->mask) 9 10 #define relink(a, b) ((b)->x.prev = (a), (a)->x.next = (b)) 11 12 static Symbol askfixedreg(Symbol); 13 static Symbol askreg(Symbol, unsigned*); 14 static void blkunroll(int, int, int, int, int, int, int[]); 15 static void docall(Node); 16 static void dumpcover(Node, int, int); 17 static void dumpregs(char *, char *, char *); 18 static void dumprule(int); 19 static void dumptree(Node); 20 static unsigned emitasm(Node, int); 21 static void genreload(Node, Symbol, int); 22 static void genspill(Symbol, Node, Symbol); 23 static Symbol getreg(Symbol, unsigned*, Node); 24 static int getrule(Node, int); 25 static void linearize(Node, Node); 26 static int moveself(Node); 27 static void prelabel(Node); 28 static Node* prune(Node, Node*); 29 static void putreg(Symbol); 30 static void ralloc(Node); 31 static void reduce(Node, int); 32 static int reprune(Node*, int, int, Node); 33 static int requate(Node); 34 static Node reuse(Node, int); 35 static void rewrite(Node); 36 static Symbol spillee(Symbol, unsigned mask[], Node); 37 static void spillr(Symbol, Node); 38 static int uses(Node, Regnode); 39 40 int offset; 41 42 int maxoffset; 43 44 int framesize; 45 int argoffset; 46 47 int maxargoffset; 48 49 int dalign, salign; 50 int bflag = 0; /* omit */ 51 int dflag = 0; 52 53 int swap; 54 55 unsigned (*emitter)(Node, int) = emitasm; 56 static char NeedsReg[] = { 57 0, /* unused */ 58 1, /* CNST */ 59 0, 0, /* ARG ASGN */ 60 1, /* INDIR */ 61 0, 0, 1, 1, /* - - CVF CVI */ 62 1, 0, 1, 1, /* CVP - CVU NEG */ 63 1, /* CALL */ 64 1, /* LOAD */ 65 0, /* RET */ 66 1, 1, 1, /* ADDRG ADDRF ADDRL */ 67 1, 1, 1, 1, 1, /* ADD SUB LSH MOD RSH */ 68 1, 1, 1, 1, /* BAND BCOM BOR BXOR */ 69 1, 1, /* DIV MUL */ 70 0, 0, 0, 0, 0, 0, /* EQ GE GT LE LT NE */ 71 0, 0 /* JUMP LABEL */ 72 }; 73 Node head; 74 75 unsigned freemask[2]; 76 unsigned usedmask[2]; 77 unsigned tmask[2]; 78 unsigned vmask[2]; 79 Symbol mkreg(char *fmt, int n, int mask, int set) { 80 Symbol p; 81 82 NEW0(p, PERM); 83 p->name = p->x.name = stringf(fmt, n); 84 NEW0(p->x.regnode, PERM); 85 p->x.regnode->number = n; 86 p->x.regnode->mask = mask<<n; 87 p->x.regnode->set = set; 88 return p; 89 } 90 Symbol mkwildcard(Symbol *syms) { 91 Symbol p; 92 93 NEW0(p, PERM); 94 p->name = p->x.name = "wildcard"; 95 p->x.wildcard = syms; 96 return p; 97 } 98 void mkauto(Symbol p) { 99 assert(p->sclass == AUTO); 100 offset = roundup(offset + p->type->size, p->type->align); 101 p->x.offset = -offset; 102 p->x.name = stringd(-offset); 103 } 104 void blockbeg(Env *e) { 105 e->offset = offset; 106 e->freemask[IREG] = freemask[IREG]; 107 e->freemask[FREG] = freemask[FREG]; 108 } 109 void blockend(Env *e) { 110 if (offset > maxoffset) 111 maxoffset = offset; 112 offset = e->offset; 113 freemask[IREG] = e->freemask[IREG]; 114 freemask[FREG] = e->freemask[FREG]; 115 } 116 int mkactual(int align, int size) { 117 int n = roundup(argoffset, align); 118 119 argoffset = n + size; 120 return n; 121 } 122 static void docall(Node p) { 123 p->syms[1] = p->syms[0]; 124 p->syms[0] = intconst(argoffset); 125 if (argoffset > maxargoffset) 126 maxargoffset = argoffset; 127 argoffset = 0; 128 } 129 void blkcopy(int dreg, int doff, int sreg, int soff, int size, int tmp[]) { 130 assert(size >= 0); 131 if (size == 0) 132 return; 133 else if (size <= 2) 134 blkunroll(size, dreg, doff, sreg, soff, size, tmp); 135 else if (size == 3) { 136 blkunroll(2, dreg, doff, sreg, soff, 2, tmp); 137 blkunroll(1, dreg, doff+2, sreg, soff+2, 1, tmp); 138 } 139 else if (size <= 16) { 140 blkunroll(4, dreg, doff, sreg, soff, size&~3, tmp); 141 blkcopy(dreg, doff+(size&~3), 142 sreg, soff+(size&~3), size&3, tmp); 143 } 144 else 145 (*IR->x.blkloop)(dreg, doff, sreg, soff, size, tmp); 146 } 147 static void blkunroll(int k, int dreg, int doff, int sreg, int soff, int size, int tmp[]) { 148 int i; 149 150 assert(IR->x.max_unaligned_load); 151 if (k > IR->x.max_unaligned_load 152 && (k > salign || k > dalign)) 153 k = IR->x.max_unaligned_load; 154 for (i = 0; i+k < size; i += 2*k) { 155 (*IR->x.blkfetch)(k, soff+i, sreg, tmp[0]); 156 (*IR->x.blkfetch)(k, soff+i+k, sreg, tmp[1]); 157 (*IR->x.blkstore)(k, doff+i, dreg, tmp[0]); 158 (*IR->x.blkstore)(k, doff+i+k, dreg, tmp[1]); 159 } 160 if (i < size) { 161 (*IR->x.blkfetch)(k, i+soff, sreg, tmp[0]); 162 (*IR->x.blkstore)(k, i+doff, dreg, tmp[0]); 163 } 164 } 165 void parseflags(int argc, char *argv[]) { 166 int i; 167 168 for (i = 0; i < argc; i++) 169 if (strcmp(argv[i], "-d") == 0) 170 dflag = 1; 171 else if (strcmp(argv[i], "-b") == 0) /* omit */ 172 bflag = 1; /* omit */ 173 } 174 static int getrule(Node p, int nt) { 175 int rulenum; 176 177 assert(p); 178 rulenum = (*IR->x._rule)(p->x.state, nt); 179 if (!rulenum) { 180 fprint(stderr, "(%x->op=%s at %w is corrupt.)\n", p, opname(p->op), &src); 181 assert(0); 182 } 183 return rulenum; 184 } 185 static void reduce(Node p, int nt) { 186 int rulenum, i; 187 short *nts; 188 Node kids[10]; 189 190 p = reuse(p, nt); 191 rulenum = getrule(p, nt); 192 nts = IR->x._nts[rulenum]; 193 (*IR->x._kids)(p, rulenum, kids); 194 for (i = 0; nts[i]; i++) 195 reduce(kids[i], nts[i]); 196 if (IR->x._isinstruction[rulenum]) { 197 assert(p->x.inst == 0 || p->x.inst == nt); 198 p->x.inst = nt; 199 if (p->syms[RX] && p->syms[RX]->temporary) { 200 debug(fprint(stderr, "(using %s)\n", p->syms[RX]->name)); 201 p->syms[RX]->x.usecount++; 202 } 203 } 204 } 205 static Node reuse(Node p, int nt) { 206 struct _state { 207 short cost[1]; 208 }; 209 Symbol r = p->syms[RX]; 210 211 if (generic(p->op) == INDIR && p->kids[0]->op == VREG+P 212 && r->u.t.cse && p->x.mayrecalc 213 && ((struct _state*)r->u.t.cse->x.state)->cost[nt] == 0) 214 return r->u.t.cse; 215 else 216 return p; 217 } 218 219 int mayrecalc(Node p) { 220 int op; 221 222 assert(p && p->syms[RX]); 223 if (p->syms[RX]->u.t.cse == NULL) 224 return 0; 225 op = generic(p->syms[RX]->u.t.cse->op); 226 if (op == CNST || op == ADDRF || op == ADDRG || op == ADDRL) { 227 p->x.mayrecalc = 1; 228 return 1; 229 } else 230 return 0; 231 } 232 static Node *prune(Node p, Node pp[]) { 233 if (p == NULL) 234 return pp; 235 p->x.kids[0] = p->x.kids[1] = p->x.kids[2] = NULL; 236 if (p->x.inst == 0) 237 return prune(p->kids[1], prune(p->kids[0], pp)); 238 else if (p->syms[RX] && p->syms[RX]->temporary 239 && p->syms[RX]->x.usecount < 2) { 240 p->x.inst = 0; 241 debug(fprint(stderr, "(clobbering %s)\n", p->syms[RX]->name)); 242 return prune(p->kids[1], prune(p->kids[0], pp)); 243 } 244 else { 245 prune(p->kids[1], prune(p->kids[0], &p->x.kids[0])); 246 *pp = p; 247 return pp + 1; 248 } 249 } 250 251 #define ck(i) return (i) ? 0 : LBURG_MAX 252 253 int range(Node p, int lo, int hi) { 254 Symbol s = p->syms[0]; 255 256 switch (specific(p->op)) { 257 case ADDRF+P: 258 case ADDRL+P: ck(s->x.offset >= lo && s->x.offset <= hi); 259 case CNST+I: ck(s->u.c.v.i >= lo && s->u.c.v.i <= hi); 260 case CNST+U: ck(s->u.c.v.u >= lo && s->u.c.v.u <= hi); 261 case CNST+P: ck(s->u.c.v.p == 0 && lo <= 0 && hi >= 0); 262 } 263 return LBURG_MAX; 264 } 265 static void dumptree(Node p) { 266 if (p->op == VREG+P && p->syms[0]) { 267 fprint(stderr, "VREGP(%s)", p->syms[0]->name); 268 return; 269 } else if (generic(p->op) == LOAD) { 270 fprint(stderr, "LOAD("); 271 dumptree(p->kids[0]); 272 fprint(stderr, ")"); 273 return; 274 } 275 fprint(stderr, "%s(", opname(p->op)); 276 switch (generic(p->op)) { 277 case CNST: case LABEL: 278 case ADDRG: case ADDRF: case ADDRL: 279 if (p->syms[0]) 280 fprint(stderr, "%s", p->syms[0]->name); 281 break; 282 case RET: 283 if (p->kids[0]) 284 dumptree(p->kids[0]); 285 break; 286 case CVF: case CVI: case CVP: case CVU: case JUMP: 287 case ARG: case BCOM: case NEG: case INDIR: 288 dumptree(p->kids[0]); 289 break; 290 case CALL: 291 if (optype(p->op) != B) { 292 dumptree(p->kids[0]); 293 break; 294 } 295 /* else fall thru */ 296 case EQ: case NE: case GT: case GE: case LE: case LT: 297 case ASGN: case BOR: case BAND: case BXOR: case RSH: case LSH: 298 case ADD: case SUB: case DIV: case MUL: case MOD: 299 dumptree(p->kids[0]); 300 fprint(stderr, ", "); 301 dumptree(p->kids[1]); 302 break; 303 default: assert(0); 304 } 305 fprint(stderr, ")"); 306 } 307 static void dumpcover(Node p, int nt, int in) { 308 int rulenum, i; 309 short *nts; 310 Node kids[10]; 311 312 p = reuse(p, nt); 313 rulenum = getrule(p, nt); 314 nts = IR->x._nts[rulenum]; 315 fprint(stderr, "dumpcover(%x) = ", p); 316 for (i = 0; i < in; i++) 317 fprint(stderr, " "); 318 dumprule(rulenum); 319 (*IR->x._kids)(p, rulenum, kids); 320 for (i = 0; nts[i]; i++) 321 dumpcover(kids[i], nts[i], in+1); 322 } 323 324 static void dumprule(int rulenum) { 325 assert(rulenum); 326 fprint(stderr, "%s / %s", IR->x._string[rulenum], 327 IR->x._templates[rulenum]); 328 if (!IR->x._isinstruction[rulenum]) 329 fprint(stderr, "\n"); 330 } 331 static unsigned emitasm(Node p, int nt) { 332 int rulenum; 333 short *nts; 334 char *fmt; 335 Node kids[10]; 336 337 p = reuse(p, nt); 338 rulenum = getrule(p, nt); 339 nts = IR->x._nts[rulenum]; 340 fmt = IR->x._templates[rulenum]; 341 assert(fmt); 342 if (IR->x._isinstruction[rulenum] && p->x.emitted) 343 print("%s", p->syms[RX]->x.name); 344 else if (*fmt == '#') 345 (*IR->x.emit2)(p); 346 else { 347 if (*fmt == '?') { 348 fmt++; 349 assert(p->kids[0]); 350 if (p->syms[RX] == p->x.kids[0]->syms[RX]) 351 while (*fmt++ != '\n') 352 ; 353 } 354 for ((*IR->x._kids)(p, rulenum, kids); *fmt; fmt++) 355 if (*fmt != '%') 356 (void)putchar(*fmt); 357 else if (*++fmt == 'F') 358 print("%d", framesize); 359 else if (*fmt >= '0' && *fmt <= '9') 360 emitasm(kids[*fmt - '0'], nts[*fmt - '0']); 361 else if (*fmt >= 'a' && *fmt < 'a' + NELEMS(p->syms)) 362 fputs(p->syms[*fmt - 'a']->x.name, stdout); 363 else 364 (void)putchar(*fmt); 365 } 366 return 0; 367 } 368 void emit(Node p) { 369 for (; p; p = p->x.next) { 370 assert(p->x.registered); 371 if (p->x.equatable && requate(p) || moveself(p)) 372 ; 373 else 374 (*emitter)(p, p->x.inst); 375 p->x.emitted = 1; 376 } 377 } 378 static int moveself(Node p) { 379 return p->x.copy 380 && p->syms[RX]->x.name == p->x.kids[0]->syms[RX]->x.name; 381 } 382 int move(Node p) { 383 p->x.copy = 1; 384 return 1; 385 } 386 static int requate(Node q) { 387 Symbol src = q->x.kids[0]->syms[RX]; 388 Symbol tmp = q->syms[RX]; 389 Node p; 390 int n = 0; 391 392 debug(fprint(stderr, "(requate(%x): tmp=%s src=%s)\n", q, tmp->x.name, src->x.name)); 393 for (p = q->x.next; p; p = p->x.next) 394 if (p->x.copy && p->syms[RX] == src 395 && p->x.kids[0]->syms[RX] == tmp) 396 debug(fprint(stderr, "(requate arm 0 at %x)\n", p)), 397 p->syms[RX] = tmp; 398 else if (setsrc(p->syms[RX]) && !moveself(p) && !readsreg(p)) 399 return 0; 400 else if (p->x.spills) 401 return 0; 402 else if (generic(p->op) == CALL && p->x.next) 403 return 0; 404 else if (p->op == LABEL+V && p->x.next) 405 return 0; 406 else if (p->syms[RX] == tmp && readsreg(p)) 407 debug(fprint(stderr, "(requate arm 5 at %x)\n", p)), 408 n++; 409 else if (p->syms[RX] == tmp) 410 break; 411 debug(fprint(stderr, "(requate arm 7 at %x)\n", p)); 412 assert(n > 0); 413 for (p = q->x.next; p; p = p->x.next) 414 if (p->syms[RX] == tmp && readsreg(p)) { 415 p->syms[RX] = src; 416 if (--n <= 0) 417 break; 418 } 419 return 1; 420 } 421 static void prelabel(Node p) { 422 if (p == NULL) 423 return; 424 prelabel(p->kids[0]); 425 prelabel(p->kids[1]); 426 if (NeedsReg[opindex(p->op)]) 427 setreg(p, (*IR->x.rmap)(opkind(p->op))); 428 switch (generic(p->op)) { 429 case ADDRF: case ADDRL: 430 if (p->syms[0]->sclass == REGISTER) 431 p->op = VREG+P; 432 break; 433 case INDIR: 434 if (p->kids[0]->op == VREG+P) 435 setreg(p, p->kids[0]->syms[0]); 436 break; 437 case ASGN: 438 if (p->kids[0]->op == VREG+P) 439 rtarget(p, 1, p->kids[0]->syms[0]); 440 break; 441 case CVI: case CVU: case CVP: 442 if (optype(p->op) != F 443 && opsize(p->op) <= p->syms[0]->u.c.v.i) 444 p->op = LOAD + opkind(p->op); 445 break; 446 } 447 (IR->x.target)(p); 448 } 449 void setreg(Node p, Symbol r) { 450 p->syms[RX] = r; 451 } 452 void rtarget(Node p, int n, Symbol r) { 453 Node q = p->kids[n]; 454 455 assert(q); 456 assert(r); 457 assert(r->sclass == REGISTER || !r->x.wildcard); 458 assert(q->syms[RX]); 459 if (r != q->syms[RX] && !q->syms[RX]->x.wildcard) { 460 q = newnode(LOAD + opkind(q->op), 461 q, NULL, q->syms[0]); 462 if (r->u.t.cse == p->kids[n]) 463 r->u.t.cse = q; 464 p->kids[n] = p->x.kids[n] = q; 465 q->x.kids[0] = q->kids[0]; 466 } 467 setreg(q, r); 468 debug(fprint(stderr, "(targeting %x->x.kids[%d]=%x to %s)\n", p, n, p->kids[n], r->x.name)); 469 } 470 static void rewrite(Node p) { 471 assert(p->x.inst == 0); 472 prelabel(p); 473 debug(dumptree(p)); 474 debug(fprint(stderr, "\n")); 475 (*IR->x._label)(p); 476 debug(dumpcover(p, 1, 0)); 477 reduce(p, 1); 478 } 479 Node gen(Node forest) { 480 int i; 481 struct node sentinel; 482 Node dummy, p; 483 484 head = forest; 485 for (p = forest; p; p = p->link) { 486 assert(p->count == 0); 487 if (generic(p->op) == CALL) 488 docall(p); 489 else if ( generic(p->op) == ASGN 490 && generic(p->kids[1]->op) == CALL) 491 docall(p->kids[1]); 492 else if (generic(p->op) == ARG) 493 (*IR->x.doarg)(p); 494 rewrite(p); 495 p->x.listed = 1; 496 } 497 for (p = forest; p; p = p->link) 498 prune(p, &dummy); 499 relink(&sentinel, &sentinel); 500 for (p = forest; p; p = p->link) 501 linearize(p, &sentinel); 502 forest = sentinel.x.next; 503 assert(forest); 504 sentinel.x.next->x.prev = NULL; 505 sentinel.x.prev->x.next = NULL; 506 for (p = forest; p; p = p->x.next) 507 for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) { 508 assert(p->x.kids[i]->syms[RX]); 509 if (p->x.kids[i]->syms[RX]->temporary) { 510 p->x.kids[i]->x.prevuse = 511 p->x.kids[i]->syms[RX]->x.lastuse; 512 p->x.kids[i]->syms[RX]->x.lastuse = p->x.kids[i]; 513 } 514 } 515 for (p = forest; p; p = p->x.next) { 516 ralloc(p); 517 if (p->x.listed && NeedsReg[opindex(p->op)] 518 && (*IR->x.rmap)(opkind(p->op))) { 519 assert(generic(p->op) == CALL || generic(p->op) == LOAD); 520 putreg(p->syms[RX]); 521 } 522 } 523 return forest; 524 } 525 int notarget(Node p) { 526 return p->syms[RX]->x.wildcard ? 0 : LBURG_MAX; 527 } 528 static void putreg(Symbol r) { 529 assert(r && r->x.regnode); 530 freemask[r->x.regnode->set] |= r->x.regnode->mask; 531 debug(dumpregs("(freeing %s)\n", r->x.name, NULL)); 532 } 533 static Symbol askfixedreg(Symbol s) { 534 Regnode r = s->x.regnode; 535 int n = r->set; 536 537 if (r->mask&~freemask[n]) 538 return NULL; 539 else { 540 freemask[n] &= ~r->mask; 541 usedmask[n] |= r->mask; 542 return s; 543 } 544 } 545 static Symbol askreg(Symbol rs, unsigned rmask[]) { 546 int i; 547 548 if (rs->x.wildcard == NULL) 549 return askfixedreg(rs); 550 for (i = 31; i >= 0; i--) { 551 Symbol r = rs->x.wildcard[i]; 552 if (r != NULL 553 && !(r->x.regnode->mask&~rmask[r->x.regnode->set]) 554 && askfixedreg(r)) 555 return r; 556 } 557 return NULL; 558 } 559 560 static Symbol getreg(Symbol s, unsigned mask[], Node p) { 561 Symbol r = askreg(s, mask); 562 if (r == NULL) { 563 r = spillee(s, mask, p); 564 assert(r && r->x.regnode); 565 spill(r->x.regnode->mask, r->x.regnode->set, p); 566 r = askreg(s, mask); 567 } 568 assert(r && r->x.regnode); 569 r->x.regnode->vbl = NULL; 570 return r; 571 } 572 int askregvar(Symbol p, Symbol regs) { 573 Symbol r; 574 575 assert(p); 576 if (p->sclass != REGISTER) 577 return 0; 578 else if (!isscalar(p->type)) { 579 p->sclass = AUTO; 580 return 0; 581 } 582 else if (p->temporary) { 583 p->x.name = "?"; 584 return 1; 585 } 586 else if ((r = askreg(regs, vmask)) != NULL) { 587 p->x.regnode = r->x.regnode; 588 p->x.regnode->vbl = p; 589 p->x.name = r->x.name; 590 debug(dumpregs("(allocating %s to symbol %s)\n", p->x.name, p->name)); 591 return 1; 592 } 593 else { 594 p->sclass = AUTO; 595 return 0; 596 } 597 } 598 static void linearize(Node p, Node next) { 599 int i; 600 601 for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) 602 linearize(p->x.kids[i], next); 603 relink(next->x.prev, p); 604 relink(p, next); 605 debug(fprint(stderr, "(listing %x)\n", p)); 606 } 607 static void ralloc(Node p) { 608 int i; 609 unsigned mask[2]; 610 611 mask[0] = tmask[0]; 612 mask[1] = tmask[1]; 613 assert(p); 614 debug(fprint(stderr, "(rallocing %x)\n", p)); 615 for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) { 616 Node kid = p->x.kids[i]; 617 Symbol r = kid->syms[RX]; 618 assert(r && kid->x.registered); 619 if (r->sclass != REGISTER && r->x.lastuse == kid) 620 putreg(r); 621 } 622 if (!p->x.registered && NeedsReg[opindex(p->op)] 623 && (*IR->x.rmap)(opkind(p->op))) { 624 Symbol sym = p->syms[RX], set = sym; 625 assert(sym); 626 if (sym->temporary) 627 set = (*IR->x.rmap)(opkind(p->op)); 628 assert(set); 629 if (set->sclass != REGISTER) { 630 Symbol r; 631 if (*IR->x._templates[getrule(p, p->x.inst)] == '?') 632 for (i = 1; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) { 633 Symbol r = p->x.kids[i]->syms[RX]; 634 assert(p->x.kids[i]->x.registered); 635 assert(r && r->x.regnode); 636 assert(sym->x.wildcard || sym != r); 637 mask[r->x.regnode->set] &= ~r->x.regnode->mask; 638 } 639 r = getreg(set, mask, p); 640 if (sym->temporary) { 641 Node q; 642 r->x.lastuse = sym->x.lastuse; 643 for (q = sym->x.lastuse; q; q = q->x.prevuse) { 644 q->syms[RX] = r; 645 q->x.registered = 1; 646 if (sym->u.t.cse && q->x.copy) 647 q->x.equatable = 1; 648 } 649 } else { 650 p->syms[RX] = r; 651 r->x.lastuse = p; 652 } 653 debug(dumpregs("(allocating %s to node %x)\n", r->x.name, (char *) p)); 654 } 655 } 656 p->x.registered = 1; 657 (*IR->x.clobber)(p); 658 } 659 static Symbol spillee(Symbol set, unsigned mask[], Node here) { 660 Symbol bestreg = NULL; 661 int bestdist = -1, i; 662 663 assert(set); 664 if (!set->x.wildcard) 665 bestreg = set; 666 else { 667 for (i = 31; i >= 0; i--) { 668 Symbol ri = set->x.wildcard[i]; 669 if ( 670 ri != NULL && 671 ri->x.lastuse && 672 (ri->x.regnode->mask&tmask[ri->x.regnode->set]&mask[ri->x.regnode->set]) 673 ) { 674 Regnode rn = ri->x.regnode; 675 Node q = here; 676 int dist = 0; 677 for (; q && !uses(q, rn); q = q->x.next) 678 dist++; 679 if (q && dist > bestdist) { 680 bestdist = dist; 681 bestreg = ri; 682 } 683 } 684 } 685 } 686 assert(bestreg); /* Must be able to spill something. Reconfigure the register allocator 687 to ensure that we can allocate a register for all nodes without spilling 688 the node's necessary input regs. */ 689 assert(bestreg->x.regnode->vbl == NULL); /* Can't spill register variables because 690 the reload site might be in other blocks. Reconfigure the register allocator 691 to ensure that this register is never allocated to a variable. */ 692 return bestreg; 693 } 694 static int uses(Node p, Regnode rn) { 695 int i; 696 697 for (i = 0; i < NELEMS(p->x.kids); i++) 698 if ( 699 p->x.kids[i] && 700 p->x.kids[i]->x.registered && 701 rn->set == p->x.kids[i]->syms[RX]->x.regnode->set && 702 (rn->mask&p->x.kids[i]->syms[RX]->x.regnode->mask) 703 ) 704 return 1; 705 return 0; 706 } 707 static void spillr(Symbol r, Node here) { 708 int i; 709 Symbol tmp; 710 Node p = r->x.lastuse; 711 assert(p); 712 while (p->x.prevuse) 713 assert(r == p->syms[RX]), 714 p = p->x.prevuse; 715 assert(p->x.registered && !readsreg(p)); 716 tmp = newtemp(AUTO, optype(p->op), opsize(p->op)); 717 genspill(r, p, tmp); 718 for (p = here->x.next; p; p = p->x.next) 719 for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) { 720 Node k = p->x.kids[i]; 721 if (k->x.registered && k->syms[RX] == r) 722 genreload(p, tmp, i); 723 } 724 putreg(r); 725 } 726 static void genspill(Symbol r, Node last, Symbol tmp) { 727 Node p, q; 728 Symbol s; 729 unsigned ty; 730 731 debug(fprint(stderr, "(spilling %s to local %s)\n", r->x.name, tmp->x.name)); 732 debug(fprint(stderr, "(genspill: ")); 733 debug(dumptree(last)); 734 debug(fprint(stderr, ")\n")); 735 ty = opkind(last->op); 736 NEW0(s, FUNC); 737 s->sclass = REGISTER; 738 s->name = s->x.name = r->x.name; 739 s->x.regnode = r->x.regnode; 740 q = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, s); 741 q = newnode(INDIR + ty, q, NULL, NULL); 742 p = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, tmp); 743 p = newnode(ASGN + ty, p, q, NULL); 744 p->x.spills = 1; 745 rewrite(p); 746 prune(p, &q); 747 q = last->x.next; 748 linearize(p, q); 749 for (p = last->x.next; p != q; p = p->x.next) { 750 ralloc(p); 751 assert(!p->x.listed || !NeedsReg[opindex(p->op)] || !(*IR->x.rmap)(opkind(p->op))); 752 } 753 } 754 755 static void genreload(Node p, Symbol tmp, int i) { 756 Node q; 757 int ty; 758 759 debug(fprint(stderr, "(replacing %x with a reload from %s)\n", p->x.kids[i], tmp->x.name)); 760 debug(fprint(stderr, "(genreload: ")); 761 debug(dumptree(p->x.kids[i])); 762 debug(fprint(stderr, ")\n")); 763 ty = opkind(p->x.kids[i]->op); 764 q = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, tmp); 765 p->x.kids[i] = newnode(INDIR + ty, q, NULL, NULL); 766 rewrite(p->x.kids[i]); 767 prune(p->x.kids[i], &q); 768 reprune(&p->kids[1], reprune(&p->kids[0], 0, i, p), i, p); 769 prune(p, &q); 770 linearize(p->x.kids[i], p); 771 } 772 static int reprune(Node *pp, int k, int n, Node p) { 773 struct node x, *q = *pp; 774 775 if (q == NULL || k > n) 776 return k; 777 else if (q->x.inst == 0) 778 return reprune(&q->kids[1], 779 reprune(&q->kids[0], k, n, p), n, p); 780 if (k == n) { 781 debug(fprint(stderr, "(reprune changes %x from %x to %x)\n", pp, *pp, p->x.kids[n])); 782 *pp = p->x.kids[n]; 783 x = *p; 784 (IR->x.target)(&x); 785 } 786 return k + 1; 787 } 788 void spill(unsigned mask, int n, Node here) { 789 int i; 790 Node p; 791 792 here->x.spills = 1; 793 usedmask[n] |= mask; 794 if (mask&~freemask[n]) { 795 796 assert( /* It makes no sense for a node to clobber() its target. */ 797 here->x.registered == 0 || /* call isn't coming through clobber() */ 798 here->syms[RX] == NULL || 799 here->syms[RX]->x.regnode == NULL || 800 here->syms[RX]->x.regnode->set != n || 801 (here->syms[RX]->x.regnode->mask&mask) == 0 802 ); 803 804 for (p = here; p; p = p->x.next) 805 for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) { 806 Symbol r = p->x.kids[i]->syms[RX]; 807 assert(r); 808 if (p->x.kids[i]->x.registered && r->x.regnode->set == n 809 && r->x.regnode->mask&mask) 810 spillr(r, here); 811 } 812 } 813 } 814 static void dumpregs(char *msg, char *a, char *b) { 815 fprint(stderr, msg, a, b); 816 fprint(stderr, "(free[0]=%x)\n", freemask[0]); 817 fprint(stderr, "(free[1]=%x)\n", freemask[1]); 818 } 819 820 int getregnum(Node p) { 821 assert(p && p->syms[RX] && p->syms[RX]->x.regnode); 822 return p->syms[RX]->x.regnode->number; 823 } 824 825 826 unsigned regloc(Symbol p) { 827 assert(p && p->sclass == REGISTER && p->sclass == REGISTER && p->x.regnode); 828 return p->x.regnode->set<<8 | p->x.regnode->number; 829 } 830