1/* Id: regs.c,v 1.247 2015/11/17 19:19:40 ragge Exp */ 2/* $NetBSD: regs.c,v 1.1.1.7 2016/02/09 20:29:19 plunky Exp $ */ 3/* 4 * Copyright (c) 2005 Anders Magnusson (ragge@ludd.luth.se). 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. The name of the author may not be used to endorse or promote products 16 * derived from this software without specific prior written permission 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30#include "pass2.h" 31#include <string.h> 32#ifdef HAVE_STRINGS_H 33#include <strings.h> 34#endif 35#ifdef HAVE_STDINT_H 36#include <stdint.h> 37#endif 38#include <stdlib.h> 39 40#define MAXLOOP 20 /* Max number of allocation loops XXX 3 should be enough */ 41 42#ifndef MAX 43#define MAX(a,b) (((a) > (b)) ? (a) : (b)) 44#endif 45 46/* 47 * New-style register allocator using graph coloring. 48 * The design is based on the George and Appel paper 49 * "Iterated Register Coalescing", ACM Transactions, No 3, May 1996. 50 */ 51 52#define BITALLOC(ptr,all,sz) { \ 53 int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr, 0, sz__s); } 54 55#undef COMPERR_PERM_MOVE 56#ifdef PCC_DEBUG 57#define RDEBUG(x) if (r2debug) printf x 58#define RRDEBUG(x) if (r2debug > 1) printf x 59#define RPRINTIP(x) if (r2debug) printip(x) 60#define RDEBUGX(x) x 61#define UDEBUG(x) if (u2debug) printf x 62#define BDEBUG(x) if (b2debug) printf x 63#define BBDEBUG(x) if (b2debug > 1) printf x 64#else 65#define RDEBUG(x) 66#define RRDEBUG(x) 67#define RPRINTIP(x) 68#define RDEBUGX(x) 69#define UDEBUG(x) 70#define BDEBUG(x) 71#define BBDEBUG(x) 72#endif 73 74#define VALIDREG(p) (p->n_op == REG && TESTBIT(validregs, regno(p))) 75 76/* 77 * Data structure overview for this implementation of graph coloring: 78 * 79 * Each temporary (called "node") is described by the type REGW. 80 * Space for all nodes is allocated initially as an array, so 81 * the nodes can be can be referenced both by the node number and 82 * by pointer. 83 * 84 * All moves are represented by the type REGM, allocated when needed. 85 * 86 * The "live" set used during graph building is represented by a bitset. 87 * 88 * Interference edges are represented by struct AdjSet, hashed and linked 89 * from index into the edgehash array. 90 * 91 * A mapping from each node to the moves it is assiciated with is 92 * maintained by an array moveList which for each node number has a linked 93 * list of MOVL types, each pointing to a REGM. 94 * 95 * Adjacency list is maintained by the adjList array, indexed by the 96 * node number. Each adjList entry points to an ADJL type, and is a 97 * single-linked list for all adjacent nodes. 98 * 99 * degree, alias and color are integer arrays indexed by node number. 100 */ 101 102/* 103 * linked list of adjacent nodes. 104 */ 105typedef struct regw3 { 106 struct regw3 *r_next; 107 struct regw *a_temp; 108} ADJL; 109 110/* 111 * Structure describing a move. 112 */ 113typedef struct regm { 114 DLIST_ENTRY(regm) link; 115 struct regw *src, *dst; 116 int queue; 117} REGM; 118 119typedef struct movlink { 120 struct movlink *next; 121 REGM *regm; 122} MOVL; 123 124/* 125 * Structure describing a temporary. 126 */ 127typedef struct regw { 128 DLIST_ENTRY(regw) link; 129 ADJL *r_adjList; /* linked list of adjacent nodes */ 130 int r_class; /* this nodes class */ 131 int r_nclass[NUMCLASS+1]; /* count of adjacent classes */ 132 struct regw *r_alias; /* aliased temporary */ 133 int r_color; /* final node color */ 134 struct regw *r_onlist; /* which work list this node belongs to */ 135 MOVL *r_moveList; /* moves associated with this node */ 136 int nodnum; /* Human-readable node number */ 137} REGW; 138 139/* 140 * Worklists, a node is always on exactly one of these lists. 141 */ 142static REGW precolored, simplifyWorklist, freezeWorklist, spillWorklist, 143 spilledNodes, coalescedNodes, coloredNodes, selectStack; 144static REGW initial, *nblock; 145static void insnwalk(NODE *p); 146#ifdef PCC_DEBUG 147int use_regw; 148#endif 149int nodnum = 100; 150int ntsz, stktemp; 151#define SETNUM(x) (x)->nodnum = nodnum++ 152#define ASGNUM(x) (x)->nodnum 153 154#define ALLNEEDS (NACOUNT|NBCOUNT|NCCOUNT|NDCOUNT|NECOUNT|NFCOUNT|NGCOUNT) 155 156/* XXX */ 157REGW *ablock; 158 159static int tempmin, tempmax, basetemp, xbits; 160/* 161 * nsavregs is an array that matches the permregs array. 162 * Each entry in the array may have the values: 163 * 0 : register coalesced, just ignore. 164 * 1 : save register on stack 165 * If the entry is 0 but the resulting color differs from the 166 * corresponding permregs index, add moves. 167 * XXX - should be a bitfield! 168 */ 169static int *nsavregs, *ndontregs; 170 171/* 172 * Return the REGW struct for a temporary. 173 * If first time touched, enter into list for existing vars. 174 * Only called from sucomp(). 175 */ 176static REGW * 177newblock(NODE *p) 178{ 179 REGW *nb; 180 181#ifdef PCC_DEBUG 182 if (regno(p) < tempmin || regno(p) >= tempmax) 183 comperr("temp %p(%d) outside limits (%d-%d)", 184 p, regno(p), tempmin, tempmax); 185#endif 186 nb = &nblock[regno(p)]; 187 if (nb->link.q_forw == 0) { 188 DLIST_INSERT_AFTER(&initial, nb, link); 189#ifdef PCC_DEBUG 190 ASGNUM(nb) = regno(p); 191 RDEBUG(("Adding longtime %d for tmp %d\n", 192 nb->nodnum, regno(p))); 193#endif 194 } 195 if (nb->r_class == 0) 196 nb->r_class = gclass(p->n_type); 197#ifdef PCC_DEBUG 198 RDEBUG(("newblock: p %p, node %d class %d\n", 199 p, nb->nodnum, nb->r_class)); 200#endif 201 return nb; 202} 203 204/* 205 * Count the number of registers needed to evaluate a tree. 206 * This is only done to find the evaluation order of the tree. 207 * While here, assign temp numbers to the registers that will 208 * be needed when the tree is evaluated. 209 * 210 * While traversing the tree, assign REGW nodes to the registers 211 * used by all instructions: 212 * - n_regw[0] is always set to the outgoing node. If the 213 * instruction is 2-op (addl r0,r1) then an implicit move 214 * is inserted just before the left (clobbered) operand. 215 * - if the instruction has needs then REGW nodes are 216 * allocated as n_regw[1] etc. 217 */ 218int 219nsucomp(NODE *p) 220{ 221 struct optab *q; 222 int left, right; 223 int nreg, need, i, nxreg, o; 224 int nareg, nbreg, ncreg, ndreg, nereg, nfreg, ngreg; 225 REGW *w; 226 227 o = optype(p->n_op); 228 229 UDEBUG(("entering nsucomp, node %p\n", p)); 230 231 if (TBLIDX(p->n_su) == 0) { 232 int a = 0, b; 233 234 p->n_regw = NULL; 235 if (o == LTYPE ) { 236 if (p->n_op == TEMP) { 237 p->n_regw = newblock(p); 238 a = 1; 239 } else if (p->n_op == REG) 240 p->n_regw = &ablock[regno(p)]; 241 } else 242 a = nsucomp(p->n_left); 243 if (o == BITYPE) { 244 b = nsucomp(p->n_right); 245 if (b > a) 246 p->n_su |= DORIGHT; 247 a = MAX(a, b); 248 } 249 return a; 250 } 251 252 q = &table[TBLIDX(p->n_su)]; 253 254#define NNEEDS(a,b) ((q->needs & a)/b) 255 for (i = (q->needs & NACOUNT), nareg = 0; i; i -= NAREG) 256 nareg++; 257 for (i = (q->needs & NBCOUNT), nbreg = 0; i; i -= NBREG) 258 nbreg++; 259 for (i = (q->needs & NCCOUNT), ncreg = 0; i; i -= NCREG) 260 ncreg++; 261 for (i = (q->needs & NDCOUNT), ndreg = 0; i; i -= NDREG) 262 ndreg++; 263 for (i = (q->needs & NECOUNT), nereg = 0; i; i -= NEREG) 264 nereg++; 265 for (i = (q->needs & NFCOUNT), nfreg = 0; i; i -= NFREG) 266 nfreg++; 267 for (i = (q->needs & NGCOUNT), ngreg = 0; i; i -= NGREG) 268 ngreg++; 269 270 if (ntsz < NNEEDS(NTMASK, NTEMP) * szty(p->n_type)) 271 ntsz = NNEEDS(NTMASK, NTEMP) * szty(p->n_type); 272 273 nxreg = nareg + nbreg + ncreg + ndreg + nereg + nfreg + ngreg; 274 nreg = nxreg; 275 if (callop(p->n_op)) 276 nreg = MAX(fregs, nreg); 277 278 if (o == BITYPE) { 279 right = nsucomp(p->n_right); 280 } else 281 right = 0; 282 283 if (o != LTYPE) 284 left = nsucomp(p->n_left); 285 else 286 left = 0; 287 288 UDEBUG(("node %p left %d right %d\n", p, left, right)); 289 290 if (o == BITYPE) { 291 /* Two children */ 292 if (right == left) { 293 need = left + MAX(nreg, 1); 294 } else { 295 need = MAX(right, left); 296 need = MAX(need, nreg); 297 } 298 if (setorder(p) == 0) { 299 /* XXX - should take care of overlapping needs */ 300 if (right > left) { 301 p->n_su |= DORIGHT; 302 } else if (right == left) { 303#if 0 304 /* XXX - need something more clever when large left trees */ 305 /* A favor to 2-operand architectures */ 306 if ((q->rewrite & RRIGHT) == 0) 307 p->n_su |= DORIGHT; 308#endif 309 } 310 } 311 } else if (o != LTYPE) { 312 /* One child */ 313 need = MAX(right, left) + nreg; 314 } else 315 need = nreg; 316 317 if (p->n_op == TEMP) 318 (void)newblock(p); 319 320 if (TCLASS(p->n_su) == 0 && nxreg == 0) { 321 UDEBUG(("node %p no class\n", p)); 322 p->n_regw = NULL; /* may be set earlier */ 323 return need; 324 } 325 326#ifdef PCC_DEBUG 327#define ADCL(n, cl) \ 328 for (i = 0; i < n; i++, w++) { w->r_class = cl; \ 329 DLIST_INSERT_BEFORE(&initial, w, link); SETNUM(w); \ 330 UDEBUG(("Adding " #n " %d\n", w->nodnum)); \ 331 } 332#else 333#define ADCL(n, cl) \ 334 for (i = 0; i < n; i++, w++) { w->r_class = cl; \ 335 DLIST_INSERT_BEFORE(&initial, w, link); SETNUM(w); \ 336 } 337#endif 338 339 UDEBUG(("node %p numregs %d\n", p, nxreg+1)); 340 w = p->n_regw = tmpalloc(sizeof(REGW) * (nxreg+1)); 341 memset(w, 0, sizeof(REGW) * (nxreg+1)); 342 343 w->r_class = TCLASS(p->n_su); 344 if (w->r_class == 0) 345 w->r_class = gclass(p->n_type); 346 w->r_nclass[0] = o == LTYPE; /* XXX store leaf info here */ 347 SETNUM(w); 348 if (w->r_class) 349 DLIST_INSERT_BEFORE(&initial, w, link); 350#ifdef PCC_DEBUG 351 UDEBUG(("Adding short %d class %d\n", w->nodnum, w->r_class)); 352#endif 353 w++; 354 ADCL(nareg, CLASSA); 355 ADCL(nbreg, CLASSB); 356 ADCL(ncreg, CLASSC); 357 ADCL(ndreg, CLASSD); 358 ADCL(nereg, CLASSE); 359 ADCL(nfreg, CLASSF); 360 ADCL(ngreg, CLASSG); 361 362 if (q->rewrite & RESC1) { 363 w = p->n_regw + 1; 364 w->r_class = -1; 365 DLIST_REMOVE(w,link); 366 } else if (q->rewrite & RESC2) { 367 w = p->n_regw + 2; 368 w->r_class = -1; 369 DLIST_REMOVE(w,link); 370 } else if (q->rewrite & RESC3) { 371 w = p->n_regw + 3; 372 w->r_class = -1; 373 DLIST_REMOVE(w,link); 374 } 375 376 UDEBUG(("node %p return regs %d\n", p, need)); 377 378 return need; 379} 380 381#define CLASS(x) (x)->r_class 382#define NCLASS(x,c) (x)->r_nclass[c] 383#define ADJLIST(x) (x)->r_adjList 384#define ALIAS(x) (x)->r_alias 385#define ONLIST(x) (x)->r_onlist 386#define MOVELIST(x) (x)->r_moveList 387#define COLOR(x) (x)->r_color 388 389static bittype *live; 390 391#define PUSHWLIST(w, l) DLIST_INSERT_AFTER(&l, w, link); w->r_onlist = &l 392#define POPWLIST(l) popwlist(&l); 393#define DELWLIST(w) DLIST_REMOVE(w, link) 394#define WLISTEMPTY(h) DLIST_ISEMPTY(&h,link) 395#define PUSHMLIST(w, l, q) DLIST_INSERT_AFTER(&l, w, link); w->queue = q 396#define POPMLIST(l) popmlist(&l); 397 398#define trivially_colorable(x) \ 399 trivially_colorable_p((x)->r_class, (x)->r_nclass) 400/* 401 * Determine if a node is trivially colorable ("degree < K"). 402 * This implementation is a dumb one, without considering speed. 403 */ 404static int 405trivially_colorable_p(int c, int *n) 406{ 407 int r[NUMCLASS+1]; 408 int i; 409 410 for (i = 1; i < NUMCLASS+1; i++) 411 r[i] = n[i] < regK[i] ? n[i] : regK[i]; 412 413#if 0 414 /* add the exclusion nodes. */ 415 /* XXX can we do someything smart here? */ 416 /* worst-case for exclusion nodes are better than the `worst-case' */ 417 for (; excl; excl >>= 1) 418 if (excl & 1) 419 r[c]++; 420#endif 421 422 i = COLORMAP(c, r); 423 if (i < 0 || i > 1) 424 comperr("trivially_colorable_p"); 425 RRDEBUG(("trivially_colorable_p: n[1] %d n[2] %d n[3] %d n[4] " 426 "%d for class %d, triv %d\n", n[1], n[2], n[3], n[4], c, i)); 427 return i; 428} 429 430int 431ncnt(int needs) 432{ 433 int i = 0; 434 435 while (needs & NACOUNT) 436 needs -= NAREG, i++; 437 while (needs & NBCOUNT) 438 needs -= NBREG, i++; 439 while (needs & NCCOUNT) 440 needs -= NCREG, i++; 441 while (needs & NDCOUNT) 442 needs -= NDREG, i++; 443 while (needs & NECOUNT) 444 needs -= NEREG, i++; 445 while (needs & NFCOUNT) 446 needs -= NFREG, i++; 447 while (needs & NGCOUNT) 448 needs -= NGREG, i++; 449 return i; 450} 451 452static REGW * 453popwlist(REGW *l) 454{ 455 REGW *w = DLIST_NEXT(l, link); 456 457 DLIST_REMOVE(w, link); 458 w->r_onlist = NULL; 459 return w; 460} 461 462/* 463 * Move lists, a move node is always on only one list. 464 */ 465static REGM coalescedMoves, constrainedMoves, frozenMoves, 466 worklistMoves, activeMoves; 467enum { COAL, CONSTR, FROZEN, WLIST, ACTIVE }; 468 469static REGM * 470popmlist(REGM *l) 471{ 472 REGM *w = DLIST_NEXT(l, link); 473 474 DLIST_REMOVE(w, link); 475 return w; 476} 477 478/* 479 * About data structures used in liveness analysis: 480 * 481 * The temporaries generated in pass1 are numbered between tempmin and 482 * tempmax. Temporaries generated in pass2 are numbered above tempmax, 483 * so they are sequentially numbered. 484 * 485 * Bitfields are used for liveness. Bit arrays are allocated on the 486 * heap for the "live" variable and on the stack for the in, out, gen 487 * and killed variables. Therefore, for a temp number, the bit number must 488 * be biased with tempmin. 489 * 490 * There may be an idea to use a different data structure to store 491 * pass2 allocated temporaries, because they are very sparse. 492 */ 493 494#ifdef PCC_DEBUG 495static void 496LIVEADD(int x) 497{ 498 RDEBUG(("Liveadd: %d\n", x)); 499 if (x >= MAXREGS && (x < tempmin || x >= tempmax)) 500 comperr("LIVEADD: out of range"); 501 if (x < MAXREGS) { 502 BITSET(live, x); 503 } else 504 BITSET(live, (x-tempmin+MAXREGS)); 505} 506 507static void 508LIVEDEL(int x) 509{ 510 RDEBUG(("Livedel: %d\n", x)); 511 512 if (x >= MAXREGS && (x < tempmin || x >= tempmax)) 513 comperr("LIVEDEL: out of range"); 514 if (x < MAXREGS) { 515 BITCLEAR(live, x); 516 } else 517 BITCLEAR(live, (x-tempmin+MAXREGS)); 518} 519#else 520#define LIVEADD(x) \ 521 (x >= MAXREGS ? BITSET(live, (x-tempmin+MAXREGS)) : BITSET(live, x)) 522#define LIVEDEL(x) \ 523 (x >= MAXREGS ? BITCLEAR(live, (x-tempmin+MAXREGS)) : BITCLEAR(live, x)) 524#endif 525 526static struct lives { 527 DLIST_ENTRY(lives) link; 528 REGW *var; 529} lused, lunused; 530 531static void 532LIVEADDR(REGW *x) 533{ 534 struct lives *l; 535 536#ifdef PCC_DEBUG 537 RDEBUG(("LIVEADDR: %d\n", x->nodnum)); 538 DLIST_FOREACH(l, &lused, link) 539 if (l->var == x) 540 return; 541#if 0 542 comperr("LIVEADDR: multiple %d", ASGNUM(x)); 543#endif 544#endif 545 if (!DLIST_ISEMPTY(&lunused, link)) { 546 l = DLIST_NEXT(&lunused, link); 547 DLIST_REMOVE(l, link); 548 } else 549 l = tmpalloc(sizeof(struct lives)); 550 551 l->var = x; 552 DLIST_INSERT_AFTER(&lused, l, link); 553} 554 555static void 556LIVEDELR(REGW *x) 557{ 558 struct lives *l; 559 560#ifdef PCC_DEBUG 561 RDEBUG(("LIVEDELR: %d\n", x->nodnum)); 562#endif 563 DLIST_FOREACH(l, &lused, link) { 564 if (l->var != x) 565 continue; 566 DLIST_REMOVE(l, link); 567 DLIST_INSERT_AFTER(&lunused, l, link); 568 return; 569 } 570#if 0 571 comperr("LIVEDELR: %p not found", x); 572#endif 573} 574 575#define MOVELISTADD(t, p) movelistadd(t, p) 576#define WORKLISTMOVEADD(s,d) worklistmoveadd(s,d) 577 578static void 579movelistadd(REGW *t, REGM *p) 580{ 581 MOVL *w = tmpalloc(sizeof(MOVL)); 582 583 w->regm = p; 584 w->next = t->r_moveList; 585 t->r_moveList = w; 586} 587 588static REGM * 589worklistmoveadd(REGW *src, REGW *dst) 590{ 591 REGM *w = tmpalloc(sizeof(REGM)); 592 593 DLIST_INSERT_AFTER(&worklistMoves, w, link); 594 w->src = src; 595 w->dst = dst; 596 w->queue = WLIST; 597 return w; 598} 599 600#define HASHSZ 16384 601struct AdjSet { 602 struct AdjSet *next; 603 REGW *u, *v; 604} *edgehash[HASHSZ]; 605 606/* Check if a node pair is adjacent */ 607static int 608adjSet(REGW *u, REGW *v) 609{ 610 struct AdjSet *w; 611 REGW *t; 612 613 if (ONLIST(u) == &precolored) { 614 ADJL *a = ADJLIST(v); 615 /* 616 * Check if any of the registers that have edges against v 617 * alias to u. 618 */ 619 for (; a; a = a->r_next) { 620 if (ONLIST(a->a_temp) != &precolored) 621 continue; 622 t = a->a_temp; 623 if (interferes(t - ablock, u - ablock)) 624 return 1; 625 } 626 } 627 628 w = edgehash[(u->nodnum+v->nodnum)& (HASHSZ-1)]; 629 630 for (; w; w = w->next) { 631 if ((u == w->u && v == w->v) || (u == w->v && v == w->u)) 632 return 1; 633 } 634 return 0; 635} 636 637/* Add a pair to adjset. No check for dups */ 638static int 639adjSetadd(REGW *u, REGW *v) 640{ 641 struct AdjSet *w; 642 int x; 643 644 x = (u->nodnum+v->nodnum)& (HASHSZ-1); 645 for (w = edgehash[x]; w; w = w->next) 646 if ((u == w->u && v == w->v) || (u == w->v && v == w->u)) 647 return 1; 648 649 w = tmpalloc(sizeof(struct AdjSet)); 650 w->u = u, w->v = v; 651 w->next = edgehash[x]; 652 edgehash[x] = w; 653 return 0; 654} 655 656/* 657 * Add an interference edge between two nodes. 658 */ 659static void 660AddEdge(REGW *u, REGW *v) 661{ 662 ADJL *x; 663 664#ifdef PCC_DEBUG 665 RRDEBUG(("AddEdge: u %d v %d\n", ASGNUM(u), ASGNUM(v))); 666 667#if 0 668 if (ASGNUM(u) == 0) 669 comperr("AddEdge 0"); 670#endif 671 if (CLASS(u) == 0 || CLASS(v) == 0) 672 comperr("AddEdge class == 0 (%d=%d, %d=%d)", 673 CLASS(u), ASGNUM(u), CLASS(v), ASGNUM(v)); 674#endif 675 676 if (u == v) 677 return; 678 if (adjSetadd(u, v)) 679 return; 680 681#if 0 682 if (ONLIST(u) == &precolored || ONLIST(v) == &precolored) 683 comperr("precolored node in AddEdge"); 684#endif 685 686 if (ONLIST(u) != &precolored) { 687 x = tmpalloc(sizeof(ADJL)); 688 x->a_temp = v; 689 x->r_next = u->r_adjList; 690 u->r_adjList = x; 691 NCLASS(u, CLASS(v))++; 692 } 693 694 if (ONLIST(v) != &precolored) { 695 x = tmpalloc(sizeof(ADJL)); 696 x->a_temp = u; 697 x->r_next = v->r_adjList; 698 v->r_adjList = x; 699 NCLASS(v, CLASS(u))++; 700 } 701 702#if 0 703 RDEBUG(("AddEdge: u %d(d %d) v %d(d %d)\n", u, DEGREE(u), v, DEGREE(v))); 704#endif 705} 706 707static int 708MoveRelated(REGW *n) 709{ 710 MOVL *l; 711 REGM *w; 712 713 for (l = MOVELIST(n); l; l = l->next) { 714 w = l->regm; 715 if (w->queue == ACTIVE || w->queue == WLIST) 716 return 1; 717 } 718 return 0; 719} 720 721static void 722MkWorklist(void) 723{ 724 REGW *w; 725 726 RDEBUGX(int s=0); 727 RDEBUGX(int f=0); 728 RDEBUGX(int d=0); 729 730 DLIST_INIT(&precolored, link); 731 DLIST_INIT(&simplifyWorklist, link); 732 DLIST_INIT(&freezeWorklist, link); 733 DLIST_INIT(&spillWorklist, link); 734 DLIST_INIT(&spilledNodes, link); 735 DLIST_INIT(&coalescedNodes, link); 736 DLIST_INIT(&coloredNodes, link); 737 DLIST_INIT(&selectStack, link); 738 739 /* 740 * Remove all nodes from the initial list and put them on 741 * one of the worklists. 742 */ 743 while (!DLIST_ISEMPTY(&initial, link)) { 744 w = DLIST_NEXT(&initial, link); 745 DLIST_REMOVE(w, link); 746 if (!trivially_colorable(w)) { 747 PUSHWLIST(w, spillWorklist); 748 RDEBUGX(s++); 749 } else if (MoveRelated(w)) { 750 PUSHWLIST(w, freezeWorklist); 751 RDEBUGX(f++); 752 } else { 753 PUSHWLIST(w, simplifyWorklist); 754 RDEBUGX(d++); 755 } 756 } 757 RDEBUG(("MkWorklist: spill %d freeze %d simplify %d\n", s,f,d)); 758} 759 760static void 761addalledges(REGW *e) 762{ 763 int i, j, k; 764 struct lives *l; 765 766#ifdef PCC_DEBUG 767 RDEBUG(("addalledges for %d\n", e->nodnum)); 768#endif 769 770 if (e->r_class == -1) 771 return; /* unused */ 772 773 if (ONLIST(e) != &precolored) { 774 for (i = 0; ndontregs[i] >= 0; i++) 775 AddEdge(e, &ablock[ndontregs[i]]); 776 } 777 778 /* First add to long-lived temps and hard regs */ 779 RDEBUG(("addalledges longlived ")); 780 for (i = 0; i < xbits; i += NUMBITS) { 781 if ((k = live[i/NUMBITS])) { 782 while (k) { 783 j = ffs(k)-1; 784 if (i+j < MAXREGS) 785 AddEdge(&ablock[i+j], e); 786 else 787 AddEdge(&nblock[i+j+tempmin-MAXREGS],e); 788 RRDEBUG(("%d ", i+j+tempmin)); 789 k &= ~(1 << j); 790 } 791 } 792#if NUMBITS > 32 /* XXX hack for LP64 */ 793 k = (live[i/NUMBITS] >> 32); 794 while (k) { 795 j = ffs(k)-1; 796 if (i+j+32 < MAXREGS) 797 AddEdge(&ablock[i+j+32], e); 798 else 799 AddEdge(&nblock[i+j+tempmin-MAXREGS+32], e); 800 RRDEBUG(("%d ", i+j+tempmin+32)); 801 k &= ~(1 << j); 802 } 803#endif 804 } 805 RDEBUG(("done\n")); 806 /* short-lived temps */ 807 RDEBUG(("addalledges shortlived ")); 808 DLIST_FOREACH(l, &lused, link) { 809#ifdef PCC_DEBUG 810 RRDEBUG(("%d ", ASGNUM(l->var))); 811#endif 812 AddEdge(l->var, e); 813 } 814 RDEBUG(("done\n")); 815} 816 817/* 818 * Add a move edge between def and use. 819 */ 820static void 821moveadd(REGW *def, REGW *use) 822{ 823 REGM *r; 824 MOVL *w; 825 826 if (def == use) 827 return; /* no move to itself XXX - ``shouldn't happen'' */ 828#ifdef PCC_DEBUG 829 RDEBUG(("moveadd: def %d use %d\n", ASGNUM(def), ASGNUM(use))); 830#endif 831 832 /* 833 * Check if we are already on move list. 834 * XXX How can that happen ??? 835 */ 836 for (w = MOVELIST(def); w; w = w->next) { 837 if ((w->regm->src == def && w->regm->dst == use) || 838 (w->regm->src == use && w->regm->dst == def)) 839 return; /* already there XXX reverse? */ 840 } 841 842 r = WORKLISTMOVEADD(use, def); 843 MOVELISTADD(def, r); 844 MOVELISTADD(use, r); 845} 846 847/* 848 * Traverse arguments backwards. 849 * XXX - can this be tricked in some other way? 850 */ 851static void 852argswalk(NODE *p) 853{ 854 855 if (p->n_op == CM) { 856 argswalk(p->n_left); 857 insnwalk(p->n_right); 858 } else 859 insnwalk(p); 860} 861 862/* 863 * Add to (or remove from) live set variables that must not 864 * be clobbered when traversing down on the other leg for 865 * a BITYPE node. 866 */ 867static void 868setlive(NODE *p, int set, REGW *rv) 869{ 870 if (rv != NULL) { 871 if (rv->nodnum < MAXREGS && 872 TESTBIT(validregs, rv->nodnum) == 0) 873 return; 874 set ? LIVEADDR(rv) : LIVEDELR(rv); 875 return; 876 } 877 878 if (p->n_regw != NULL) { 879 if (p->n_regw->nodnum < MAXREGS && 880 TESTBIT(validregs, p->n_regw->nodnum) == 0) 881 return; 882 set ? LIVEADDR(p->n_regw) : LIVEDELR(p->n_regw); 883 return; 884 } 885 886 switch (optype(p->n_op)) { 887 case LTYPE: 888 if (p->n_op == TEMP || VALIDREG(p)) 889 set ? LIVEADD(regno(p)) : LIVEDEL(regno(p)); 890 break; 891 case BITYPE: 892 setlive(p->n_right, set, rv); 893 /* FALLTHROUGH */ 894 case UTYPE: 895 setlive(p->n_left, set, rv); 896 break; 897 } 898} 899 900/* 901 * Add edges for temporary w against all temporaries that may be 902 * used simultaneously (like index registers). 903 */ 904static void 905addedge_r(NODE *p, REGW *w) 906{ 907 RRDEBUG(("addedge_r: node %p regw %p\n", p, w)); 908 909 if (p->n_regw != NULL) { 910 if (p->n_regw->nodnum < MAXREGS && 911 TESTBIT(validregs, p->n_regw->nodnum) == 0) 912 return; 913 AddEdge(p->n_regw, w); 914 return; 915 } 916 917 if (optype(p->n_op) == BITYPE) 918 addedge_r(p->n_right, w); 919 if (optype(p->n_op) != LTYPE) 920 addedge_r(p->n_left, w); 921} 922 923/* 924 * delete early clobber liveness. Only interesting on regs. 925 */ 926static void 927delcl(NODE *p) 928{ 929 int cw; 930 931 if (p->n_op == ICON && p->n_type == STRTY) 932 return; 933 cw = xasmcode(p->n_name); 934 if ((cw & XASMCONSTR) == 0 || !XASMISOUT(cw)) 935 return; 936 if (XASMVAL(cw) != 'r') 937 return; 938 LIVEDEL(regno(p->n_left)); 939} 940 941/* 942 * add/del parameter from live set. 943 */ 944static void 945setxarg(NODE *p) 946{ 947 int i, ut = 0, in = 0; 948 REGW *rw; 949 int c, cw; 950 951 if (p->n_op == ICON && p->n_type == STRTY) 952 return; 953 954 RDEBUG(("setxarg %p %s\n", p, p->n_name)); 955 cw = xasmcode(p->n_name); 956 if (XASMISINP(cw)) 957 in = 1; 958 if (XASMISOUT(cw) && !(cw & XASMCONSTR)) 959 ut = 1; 960 961 c = XASMVAL(cw); 962 963#ifdef MYSETXARG 964 MYSETXARG; 965#endif 966 967 switch (c) { 968 case 'm': 969 case 'g': 970 /* must find all TEMPs/REGs and set them live */ 971 if (p->n_left->n_op != REG && p->n_left->n_op != TEMP) { 972 insnwalk(p->n_left); 973 break; 974 } 975 /* FALLTHROUGH */ 976 case 'r': 977 i = regno(p->n_left); 978 rw = p->n_left->n_op == REG ? ablock : nblock; 979 if (ut) { 980 LIVEDEL(i); 981 } 982 if (in) { 983 LIVEADD(i); 984 } 985 addalledges(&rw[i]); 986 break; 987 988 case 'i': 989 case 'n': 990 break; 991 default: 992 comperr("bad ixarg %s", p->n_name); 993 } 994#ifdef MYSETXARG 995 MYSETXARG; 996#endif 997} 998 999/* 1000 * Do the in-tree part of liveness analysis. (the difficult part) 1001 * 1002 * Walk down the tree in reversed-evaluation order (backwards). 1003 * The moves and edges inserted and evaluation order for 1004 * instructions when code is emitted is described here, hence 1005 * this code runs the same but backwards. 1006 * 1007 * 2-op reclaim LEFT: eval L, move to DEST, eval R. 1008 * moveadd L,DEST; addedge DEST,R 1009 * 2-op reclaim LEFT DORIGHT: eval R, eval L, move to DEST. 1010 * moveadd L,DEST; addedge DEST,R; addedge L,R 1011 * 2-op reclaim RIGHT; eval L, eval R, move to DEST. 1012 * moveadd R,DEST; addedge DEST,L; addedge L,R 1013 * 2-op reclaim RIGHT DORIGHT: eval R, move to DEST, eval L. 1014 * moveadd R,DEST; addedge DEST,L 1015 * 3-op: eval L, eval R 1016 * addedge L,R 1017 * 3-op DORIGHT: eval R, eval L 1018 * addedge L,R 1019 * 1020 * Instructions with special needs are handled just like these variants, 1021 * with the exception of extra added moves and edges. 1022 * Moves to special regs are scheduled after the evaluation of both legs. 1023 */ 1024 1025static void 1026insnwalk(NODE *p) 1027{ 1028 int o = p->n_op; 1029 struct optab *q = &table[TBLIDX(p->n_su)]; 1030 REGW *lr, *rr, *rv, *r, *rrv, *lrv; 1031 NODE *lp, *rp; 1032 int i, n; 1033 1034 RDEBUG(("insnwalk %p\n", p)); 1035 1036 rv = p->n_regw; 1037 1038 rrv = lrv = NULL; 1039 if (p->n_op == ASSIGN && 1040 (p->n_left->n_op == TEMP || VALIDREG(p->n_left))) { 1041 lr = p->n_left->n_op == TEMP ? nblock : ablock; 1042 i = regno(p->n_left); 1043 LIVEDEL(i); /* remove assigned temp from live set */ 1044 addalledges(&lr[i]); 1045 } 1046 1047 /* Add edges for the result of this node */ 1048 if (rv && (q->visit & INREGS || o == TEMP || VALIDREG(p))) 1049 addalledges(rv); 1050 1051 /* special handling of CALL operators */ 1052 if (callop(o)) { 1053 if (rv) 1054 moveadd(rv, &ablock[RETREG(p->n_type)]); 1055 for (i = 0; tempregs[i] >= 0; i++) 1056 addalledges(&ablock[tempregs[i]]); 1057 } 1058 1059 /* for special return value registers add moves */ 1060 if ((q->needs & NSPECIAL) && (n = rspecial(q, NRES)) >= 0 && 1061 p->n_regw != NULL) { 1062 rv = &ablock[n]; 1063 moveadd(p->n_regw, rv); 1064 } 1065 1066 /* Check leaves for results in registers */ 1067 lr = optype(o) != LTYPE ? p->n_left->n_regw : NULL; 1068 lp = optype(o) != LTYPE ? p->n_left : NULL; 1069 rr = optype(o) == BITYPE ? p->n_right->n_regw : NULL; 1070 rp = optype(o) == BITYPE ? p->n_right : NULL; 1071 1072 /* simple needs */ 1073 n = ncnt(q->needs); 1074 for (i = 0; i < n; i++) { 1075#if 1 1076 static int ncl[] = 1077 { 0, NASL, NBSL, NCSL, NDSL, NESL, NFSL, NGSL }; 1078 static int ncr[] = 1079 { 0, NASR, NBSR, NCSR, NDSR, NESR, NFSR, NGSR }; 1080 int j; 1081 1082 /* edges are already added */ 1083 if ((r = &p->n_regw[1+i])->r_class == -1) { 1084 r = p->n_regw; 1085 } else { 1086 AddEdge(r, p->n_regw); 1087 addalledges(r); 1088 if (q->needs & NSPECIAL) { 1089 struct rspecial *rc; 1090 for (rc = nspecial(q); rc->op; rc++) { 1091 if (rc->op != NEVER) 1092 continue; 1093 AddEdge(r, &ablock[rc->num]); 1094 } 1095 } 1096 } 1097 if (optype(o) != LTYPE && (q->needs & ncl[CLASS(r)]) == 0) 1098 addedge_r(p->n_left, r); 1099 if (optype(o) == BITYPE && (q->needs & ncr[CLASS(r)]) == 0) 1100 addedge_r(p->n_right, r); 1101 for (j = i + 1; j < n; j++) { 1102 if (p->n_regw[j+1].r_class == -1) 1103 continue; 1104 AddEdge(r, &p->n_regw[j+1]); 1105 } 1106#else 1107 if ((r = &p->n_regw[1+i])->r_class == -1) 1108 continue; 1109 addalledges(r); 1110 if (optype(o) != LTYPE && (q->needs & NASL) == 0) 1111 addedge_r(p->n_left, r); 1112 if (optype(o) == BITYPE && (q->needs & NASR) == 0) 1113 addedge_r(p->n_right, r); 1114#endif 1115 } 1116 1117 /* special needs */ 1118 if (q->needs & NSPECIAL) { 1119 struct rspecial *rc; 1120 for (rc = nspecial(q); rc->op; rc++) { 1121 switch (rc->op) { 1122#define ONLY(c,s) if (c) s(c, &ablock[rc->num]) 1123 case NLEFT: 1124 addalledges(&ablock[rc->num]); 1125 ONLY(lr, moveadd); 1126 if (optype(o) != BITYPE) 1127 break; 1128 /* FALLTHROUGH */ 1129 case NORIGHT: 1130 addedge_r(p->n_right, &ablock[rc->num]); 1131 break; 1132 case NRIGHT: 1133 addalledges(&ablock[rc->num]); 1134 ONLY(rr, moveadd); 1135 /* FALLTHROUGH */ 1136 case NOLEFT: 1137 addedge_r(p->n_left, &ablock[rc->num]); 1138 break; 1139 case NEVER: 1140 addalledges(&ablock[rc->num]); 1141 break; 1142#undef ONLY 1143 } 1144 } 1145 } 1146 1147 if (o == ASSIGN) { 1148 /* avoid use of unhandled registers */ 1149 if (p->n_left->n_op == REG && 1150 !TESTBIT(validregs, regno(p->n_left))) 1151 lr = NULL; 1152 if (p->n_right->n_op == REG && 1153 !TESTBIT(validregs, regno(p->n_right))) 1154 rr = NULL; 1155 /* needs special treatment */ 1156 if (lr && rr) 1157 moveadd(lr, rr); 1158 if (lr && rv) 1159 moveadd(lr, rv); 1160 if (rr && rv) 1161 moveadd(rr, rv); 1162 } else if (callop(o)) { 1163 int *c; 1164 1165 for (c = livecall(p); *c != -1; c++) { 1166 addalledges(ablock + *c); 1167 LIVEADD(*c); 1168 } 1169 } else if (q->rewrite & (RESC1|RESC2|RESC3)) { 1170 if (lr && rr) 1171 AddEdge(lr, rr); 1172 } else if (q->rewrite & RLEFT) { 1173 if (lr && rv) 1174 moveadd(rv, lr), lrv = rv; 1175 if (rv && rp) 1176 addedge_r(rp, rv); 1177 } else if (q->rewrite & RRIGHT) { 1178 if (rr && rv) 1179 moveadd(rv, rr), rrv = rv; 1180 if (rv && lp) 1181 addedge_r(lp, rv); 1182 } 1183 1184 switch (optype(o)) { 1185 case BITYPE: 1186 if (p->n_op == ASSIGN && 1187 (p->n_left->n_op == TEMP || p->n_left->n_op == REG)) { 1188 /* only go down right node */ 1189 insnwalk(p->n_right); 1190 } else if (callop(o)) { 1191 insnwalk(p->n_left); 1192 /* Do liveness analysis on arguments (backwards) */ 1193 argswalk(p->n_right); 1194 } else if ((p->n_su & DORIGHT) == 0) { 1195 setlive(p->n_left, 1, lrv); 1196 insnwalk(p->n_right); 1197 setlive(p->n_left, 0, lrv); 1198 insnwalk(p->n_left); 1199 } else { 1200 setlive(p->n_right, 1, rrv); 1201 insnwalk(p->n_left); 1202 setlive(p->n_right, 0, rrv); 1203 insnwalk(p->n_right); 1204 } 1205 break; 1206 1207 case UTYPE: 1208 insnwalk(p->n_left); 1209 break; 1210 1211 case LTYPE: 1212 switch (o) { 1213 case REG: 1214 if (!TESTBIT(validregs, regno(p))) 1215 break; /* never add moves */ 1216 /* FALLTHROUGH */ 1217 case TEMP: 1218 i = regno(p); 1219 rr = (o == TEMP ? &nblock[i] : &ablock[i]); 1220 if (rv != rr) { 1221 addalledges(rr); 1222 moveadd(rv, rr); 1223 } 1224 LIVEADD(i); 1225 break; 1226 1227 case OREG: /* XXX - not yet */ 1228 break; 1229 1230 default: 1231 break; 1232 } 1233 break; 1234 } 1235} 1236 1237static bittype **gen, **killed, **in, **out; 1238 1239struct notspill { 1240 SLIST_ENTRY(notspill) link; 1241 int spnum; 1242}; 1243SLIST_HEAD(, notspill) nothead; 1244 1245static int 1246innotspill(int n) 1247{ 1248 struct notspill *nsp; 1249 1250 SLIST_FOREACH(nsp, ¬head, link) 1251 if (nsp->spnum == n) 1252 return 1; 1253 return 0; 1254} 1255 1256static void 1257addnotspill(int n) 1258{ 1259 struct notspill *nsp; 1260 1261 if (innotspill(n)) 1262 return; 1263 nsp = tmpalloc(sizeof(struct notspill)); 1264 nsp->spnum = n; 1265 SLIST_INSERT_LAST(¬head, nsp, link); 1266} 1267 1268/* 1269 * Found an extended assembler node, so growel out gen/killed nodes. 1270 */ 1271static void 1272xasmionize(NODE *p, void *arg) 1273{ 1274 int bb = *(int *)arg; 1275 int cw, b; 1276 1277 if (p->n_op == ICON && p->n_type == STRTY) 1278 return; /* dummy end marker */ 1279 1280 cw = xasmcode(p->n_name); 1281 if (XASMVAL(cw) == 'n' /* || XASMVAL(cw) == 'm' */) 1282 return; /* no flow analysis */ 1283 p = p->n_left; 1284 1285 if (XASMVAL(cw) == 'g' && p->n_op != TEMP && p->n_op != REG) 1286 return; /* no flow analysis */ 1287 1288 b = regno(p); 1289 if (XASMVAL(cw) == 'r' && p->n_op == TEMP) 1290 addnotspill(b); 1291 if (XASMVAL(cw) == 'm') { 1292 if (p->n_op == UMUL && p->n_left->n_op == TEMP) { 1293 p = p->n_left; 1294 b = regno(p); 1295 addnotspill(b); 1296 cw &= ~(XASMASG|XASMINOUT); 1297 } else 1298 return; 1299 } 1300#define MKTOFF(r) ((r) - tempmin + MAXREGS) 1301 if (XASMISOUT(cw)) { 1302 if (p->n_op == TEMP) { 1303 BITCLEAR(gen[bb], MKTOFF(b)); 1304 BITSET(killed[bb], MKTOFF(b)); 1305 } else if (p->n_op == REG) { 1306 BITCLEAR(gen[bb], b); 1307 BITSET(killed[bb], b); 1308 } else 1309 uerror("bad xasm node type %d", p->n_op); 1310 } 1311 if (XASMISINP(cw)) { 1312 if (p->n_op == TEMP) { 1313 BITSET(gen[bb], MKTOFF(b)); 1314 } else if (p->n_op == REG) { 1315 BITSET(gen[bb], b); 1316 } else if (optype(p->n_op) != LTYPE) { 1317 if (XASMVAL(cw) == 'r') 1318 uerror("couldn't find available register"); 1319 else 1320 uerror("bad xasm node type2"); 1321 } 1322 } 1323} 1324 1325#ifndef XASMCONSTREGS 1326#define XASMCONSTREGS(x) (-1) 1327#endif 1328 1329/* 1330 * Check that given constraints are valid. 1331 */ 1332static void 1333xasmconstr(NODE *p, void *arg) 1334{ 1335 int i; 1336 1337 if (p->n_op == ICON && p->n_type == STRTY) 1338 return; /* no constraints */ 1339 1340 if (strcmp(p->n_name, "cc") == 0 || strcmp(p->n_name, "memory") == 0) 1341 return; 1342 1343 for (i = 0; i < MAXREGS; i++) 1344 if (strcmp(rnames[i], p->n_name) == 0) { 1345 addalledges(&ablock[i]); 1346 return; 1347 } 1348 if ((i = XASMCONSTREGS(p->n_name)) < 0) 1349 comperr("unsupported xasm constraint %s", p->n_name); 1350 addalledges(&ablock[i]); 1351} 1352 1353#define RUP(x) (((x)+NUMBITS-1)/NUMBITS) 1354#define SETCOPY(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] = f[i] 1355#define SETSET(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] |= f[i] 1356#define SETCLEAR(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] &= ~f[i] 1357#define SETCMP(v,t,f,i,n) for (i = 0; i < RUP(n); i++) \ 1358 if (t[i] != f[i]) v = 1 1359#define SETEMPTY(t,sz) memset(t, 0, BIT2BYTE(sz)) 1360 1361static int 1362deldead(NODE *p, bittype *lvar) 1363{ 1364 NODE *q; 1365 int ty, rv = 0; 1366 1367#define BNO(p) (regno(p) - tempmin+MAXREGS) 1368 if (p->n_op == TEMP) 1369 BITSET(lvar, BNO(p)); 1370 if (asgop(p->n_op) && p->n_left->n_op == TEMP && 1371 TESTBIT(lvar, BNO(p->n_left)) == 0) { 1372 /* 1373 * Not live, must delete the right tree at least 1374 * down to next statement with side effects. 1375 */ 1376 BDEBUG(("DCE deleting temp %d\n", regno(p->n_left))); 1377 nfree(p->n_left); 1378 q = p->n_right; 1379 *p = *q; 1380 nfree(q); 1381 rv = 1; 1382 } 1383 ty = optype(p->n_op); 1384 if (ty != LTYPE) 1385 rv |= deldead(p->n_left, lvar); 1386 if (ty == BITYPE) 1387 rv |= deldead(p->n_right, lvar); 1388 return rv; 1389} 1390 1391/* 1392 * Ensure that the su field is empty before generating instructions. 1393 */ 1394static void 1395clrsu(NODE *p) 1396{ 1397 int o = optype(p->n_op); 1398 1399 p->n_su = 0; 1400 if (o != LTYPE) 1401 clrsu(p->n_left); 1402 if (o == BITYPE) 1403 clrsu(p->n_right); 1404} 1405 1406/* 1407 * Do dead code elimination. 1408 */ 1409static int 1410dce(struct p2env *p2e) 1411{ 1412 extern struct interpass prepole; 1413 struct basicblock *bb; 1414 struct interpass *ip; 1415 NODE *p; 1416 bittype *lvar; 1417 int i, bbnum, fix = 0; 1418 1419#ifdef mach_vax 1420 return 0; /* XXX may need to recalc tree structure */ 1421 /* eliminating assignments may create more OREGs */ 1422 /* Fix by or/either break out ASSIGN or do this earlier */ 1423#endif 1424 1425 BDEBUG(("Entering DCE\n")); 1426 /* 1427 * Traverse over the basic blocks. 1428 * if an assignment is found that writes to a temporary 1429 * that is not live out, remove that assignment and its legs. 1430 */ 1431 DLIST_INIT(&prepole, qelem); 1432 BITALLOC(lvar, tmpalloc, xbits); 1433 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1434 bbnum = bb->bbnum; 1435 BBDEBUG(("DCE bblock %d, start %p last %p\n", 1436 bbnum, bb->first, bb->last)); 1437 SETCOPY(lvar, out[bbnum], i, xbits); 1438 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) { 1439 if (ip->type == IP_NODE && deldead(ip->ip_node, lvar)) { 1440 if ((p = deluseless(ip->ip_node)) == NULL) { 1441 struct interpass *previp; 1442 struct basicblock *prevbb; 1443 1444 if (ip == bb->first && ip == bb->last) { 1445 /* Remove basic block */ 1446 previp = DLIST_PREV(ip, qelem); 1447 DLIST_REMOVE(ip, qelem); 1448 prevbb = DLIST_PREV(bb, bbelem); 1449 DLIST_REMOVE(bb, bbelem); 1450 bb = prevbb; 1451 } else if (ip == bb->first) { 1452 bb->first = 1453 DLIST_NEXT(ip, qelem); 1454 DLIST_REMOVE(ip, qelem); 1455 } else if (ip == bb->last) { 1456 previp = DLIST_PREV(ip, qelem); 1457 DLIST_REMOVE(ip, qelem); 1458 bb->last = previp; 1459 bb = DLIST_PREV(bb, bbelem); 1460 } else { 1461 previp = DLIST_NEXT(ip, qelem); 1462 DLIST_REMOVE(ip, qelem); 1463 ip = previp; 1464 fix++; 1465 continue; 1466 } 1467 fix++; 1468 BDEBUG(("bb %d: DCE ip %p deleted\n", 1469 bbnum, ip)); 1470 break; 1471 } else while (!DLIST_ISEMPTY(&prepole, qelem)) { 1472 struct interpass *tipp; 1473 1474 BDEBUG(("bb %d: DCE doing ip prepend\n", bbnum)); 1475 tipp = DLIST_NEXT(&prepole, qelem); 1476 DLIST_REMOVE(tipp, qelem); 1477 DLIST_INSERT_BEFORE(ip, tipp, qelem); 1478 if (ip == bb->first) 1479 bb->first = tipp; 1480 fix++; 1481 BDEBUG(("DCE ip prepended\n")); 1482 } 1483 if (ip->type == IP_NODE) { 1484 clrsu(p); 1485 geninsn(p, FOREFF); 1486 nsucomp(p); 1487 ip->ip_node = p; 1488 } 1489 } 1490 if (ip == bb->first) 1491 break; 1492 } 1493 } 1494 BDEBUG(("DCE fix %d\n", fix)); 1495 return fix; 1496} 1497 1498/* 1499 * Set/clear long term liveness for regs and temps. 1500 */ 1501static void 1502unionize(NODE *p, int bb) 1503{ 1504 int i, o, ty; 1505 1506 if ((o = p->n_op) == TEMP) { 1507#ifdef notyet 1508 for (i = 0; i < szty(p->n_type); i++) { 1509 BITSET(gen[bb], (regno(p) - tempmin+i+MAXREGS)); 1510 } 1511#else 1512 i = 0; 1513 BITSET(gen[bb], (regno(p) - tempmin+i+MAXREGS)); 1514#endif 1515 } else if (VALIDREG(p)) { 1516 BITSET(gen[bb], regno(p)); 1517 } 1518 if (asgop(o)) { 1519 if (p->n_left->n_op == TEMP) { 1520 int b = regno(p->n_left) - tempmin+MAXREGS; 1521#ifdef notyet 1522 for (i = 0; i < szty(p->n_type); i++) { 1523 BITCLEAR(gen[bb], (b+i)); 1524 BITSET(killed[bb], (b+i)); 1525 } 1526#else 1527 i = 0; 1528 BITCLEAR(gen[bb], (b+i)); 1529 BITSET(killed[bb], (b+i)); 1530#endif 1531 unionize(p->n_right, bb); 1532 return; 1533 } else if (VALIDREG(p->n_left)) { 1534 int b = regno(p->n_left); 1535 BITCLEAR(gen[bb], b); 1536 BITSET(killed[bb], b); 1537 unionize(p->n_right, bb); 1538 return; 1539 } 1540 } 1541 ty = optype(o); 1542 if (ty != LTYPE) 1543 unionize(p->n_left, bb); 1544 if (ty == BITYPE) 1545 unionize(p->n_right, bb); 1546} 1547 1548/* 1549 * Do variable liveness analysis. Only analyze the long-lived 1550 * variables, and save the live-on-exit temporaries in a bit-field 1551 * at the end of each basic block. This bit-field is later used 1552 * when doing short-range liveness analysis in Build(). 1553 */ 1554static void 1555LivenessAnalysis(struct p2env *p2e) 1556{ 1557 struct basicblock *bb; 1558 struct interpass *ip; 1559 int bbnum; 1560 1561 /* 1562 * generate the gen-killed sets for all basic blocks. 1563 */ 1564 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1565 bbnum = bb->bbnum; 1566 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) { 1567 /* gen/killed is 'p', this node is 'n' */ 1568 if (ip->type == IP_NODE) { 1569 if (ip->ip_node->n_op == XASM) 1570 flist(ip->ip_node->n_left, 1571 xasmionize, &bbnum); 1572 else 1573 unionize(ip->ip_node, bbnum); 1574 } 1575 if (ip == bb->first) 1576 break; 1577 } 1578 memcpy(in[bbnum], gen[bbnum], BIT2BYTE(xbits)); 1579#ifdef PCC_DEBUG 1580#define PRTRG(x) printf("%d ", x < MAXREGS ? x : x + tempmin-MAXREGS) 1581 if (r2debug) { 1582 int i; 1583 1584 printf("basic block %d\ngen: ", bbnum); 1585 for (i = 0; i < xbits; i++) 1586 if (TESTBIT(gen[bbnum], i)) 1587 PRTRG(i); 1588 printf("\nkilled: "); 1589 for (i = 0; i < xbits; i++) 1590 if (TESTBIT(killed[bbnum], i)) 1591 PRTRG(i); 1592 printf("\n"); 1593 } 1594#endif 1595 } 1596} 1597 1598 1599/* 1600 * Build the set of interference edges and adjacency list. 1601 */ 1602static void 1603Build(struct p2env *p2e) 1604{ 1605 struct interpass *ipole = &p2e->ipole; 1606 struct basicblock bbfake; 1607 struct interpass *ip; 1608 struct basicblock *bb; 1609 bittype *saved; 1610 int i, j, again; 1611 1612 if (xtemps == 0) { 1613 /* 1614 * No basic block splitup is done if not optimizing, 1615 * so fake one basic block to keep the liveness analysis 1616 * happy. 1617 */ 1618 p2e->nbblocks = 1; 1619 bbfake.bbnum = 0; 1620 bbfake.last = DLIST_PREV(ipole, qelem); 1621 bbfake.first = DLIST_NEXT(ipole, qelem); 1622 DLIST_INIT(&p2e->bblocks, bbelem); 1623 DLIST_INSERT_AFTER(&p2e->bblocks, &bbfake, bbelem); 1624 SLIST_INIT(&bbfake.child); 1625 } 1626 1627 /* Just fetch space for the temporaries from stack */ 1628 gen = tmpalloc(p2e->nbblocks*sizeof(bittype*)); 1629 killed = tmpalloc(p2e->nbblocks*sizeof(bittype*)); 1630 in = tmpalloc(p2e->nbblocks*sizeof(bittype*)); 1631 out = tmpalloc(p2e->nbblocks*sizeof(bittype*)); 1632 for (i = 0; i < p2e->nbblocks; i++) { 1633 BITALLOC(gen[i],tmpalloc,xbits); 1634 BITALLOC(killed[i],tmpalloc,xbits); 1635 BITALLOC(in[i],tmpalloc,xbits); 1636 BITALLOC(out[i],tmpalloc,xbits); 1637 } 1638 BITALLOC(saved,tmpalloc,xbits); 1639 1640 SLIST_INIT(¬head); 1641livagain: 1642 LivenessAnalysis(p2e); 1643 1644 /* register variable temporaries are live */ 1645 for (i = 0; i < NPERMREG-1; i++) { 1646 if (nsavregs[i]) 1647 continue; 1648 BITSET(out[p2e->nbblocks-1], (i+MAXREGS)); 1649 for (j = i+1; j < NPERMREG-1; j++) { 1650 if (nsavregs[j]) 1651 continue; 1652 AddEdge(&nblock[i+tempmin], &nblock[j+tempmin]); 1653 } 1654 } 1655 1656 /* do liveness analysis on basic block level */ 1657 do { 1658 struct cfgnode *cn; 1659 again = 0; 1660 /* XXX - loop should be in reversed execution-order */ 1661 DLIST_FOREACH_REVERSE(bb, &p2e->bblocks, bbelem) { 1662 i = bb->bbnum; 1663 SETCOPY(saved, out[i], j, xbits); 1664 SLIST_FOREACH(cn, &bb->child, chld) { 1665 SETSET(out[i], in[cn->bblock->bbnum], j, xbits); 1666 } 1667 SETCMP(again, saved, out[i], j, xbits); 1668 SETCOPY(saved, in[i], j, xbits); 1669 SETCOPY(in[i], out[i], j, xbits); 1670 SETCLEAR(in[i], killed[i], j, xbits); 1671 SETSET(in[i], gen[i], j, xbits); 1672 SETCMP(again, saved, in[i], j, xbits); 1673 } 1674 } while (again); 1675 1676#ifdef PCC_DEBUG 1677 if (r2debug) { 1678 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1679 printf("basic block %d\nin: ", bb->bbnum); 1680 for (i = 0; i < xbits; i++) 1681 if (TESTBIT(in[bb->bbnum], i)) 1682 PRTRG(i); 1683 printf("\nout: "); 1684 for (i = 0; i < xbits; i++) 1685 if (TESTBIT(out[bb->bbnum], i)) 1686 PRTRG(i); 1687 printf("\n"); 1688 } 1689 } 1690#endif 1691 if (xtemps && xdce) { 1692 /* 1693 * Do dead code elimination by using live out. 1694 * Ignores if any variable read from is marked volatile, 1695 * but what it should do is unspecified anyway. 1696 * Liveness Analysis should be done in optim2 instead. 1697 * 1698 * This should recalculate the basic block structure. 1699 */ 1700 if (dce(p2e)) { 1701 /* Clear bitfields */ 1702 for (i = 0; i < p2e->nbblocks; i++) { 1703 SETEMPTY(gen[i],xbits); 1704 SETEMPTY(killed[i],xbits); 1705 SETEMPTY(in[i],xbits); 1706 SETEMPTY(out[i],xbits); 1707 } 1708 SETEMPTY(saved,xbits); 1709 goto livagain; 1710 } 1711 } 1712 1713 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1714 RDEBUG(("liveadd bb %d\n", bb->bbnum)); 1715 i = bb->bbnum; 1716 for (j = 0; j < xbits; j += NUMBITS) 1717 live[j/NUMBITS] = 0; 1718 SETCOPY(live, out[i], j, xbits); 1719 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) { 1720 if (ip->type == IP_NODE) { 1721 if (ip->ip_node->n_op == XASM) { 1722 flist(ip->ip_node->n_right, 1723 xasmconstr, 0); 1724 listf(ip->ip_node->n_left, setxarg); 1725 listf(ip->ip_node->n_left, delcl); 1726 } else 1727 insnwalk(ip->ip_node); 1728 } 1729 if (ip == bb->first) 1730 break; 1731 } 1732 } 1733 1734#ifdef PCC_DEBUG 1735 if (r2debug) { 1736 struct AdjSet *w; 1737 ADJL *x; 1738 REGW *y; 1739 MOVL *m; 1740 1741 printf("Interference edges\n"); 1742 for (i = 0; i < HASHSZ; i++) { 1743 if ((w = edgehash[i]) == NULL) 1744 continue; 1745 for (; w; w = w->next) 1746 printf("%d <-> %d\n", ASGNUM(w->u), ASGNUM(w->v)); 1747 } 1748 printf("Degrees\n"); 1749 DLIST_FOREACH(y, &initial, link) { 1750 printf("%d (%c): trivial [%d] ", ASGNUM(y), 1751 CLASS(y)+'@', trivially_colorable(y)); 1752 i = 0; 1753 for (x = ADJLIST(y); x; x = x->r_next) { 1754 if (ONLIST(x->a_temp) != &selectStack && 1755 ONLIST(x->a_temp) != &coalescedNodes) 1756 printf("%d ", ASGNUM(x->a_temp)); 1757 else 1758 printf("(%d) ", ASGNUM(x->a_temp)); 1759 i++; 1760 } 1761 printf(": n=%d\n", i); 1762 } 1763 printf("Move nodes\n"); 1764 DLIST_FOREACH(y, &initial, link) { 1765 if (MOVELIST(y) == NULL) 1766 continue; 1767 printf("%d: ", ASGNUM(y)); 1768 for (m = MOVELIST(y); m; m = m->next) { 1769 REGW *yy = m->regm->src == y ? 1770 m->regm->dst : m->regm->src; 1771 printf("%d ", ASGNUM(yy)); 1772 } 1773 printf("\n"); 1774 } 1775 } 1776#endif 1777 1778} 1779 1780static void 1781EnableMoves(REGW *n) 1782{ 1783 MOVL *l; 1784 REGM *m; 1785 1786 for (l = MOVELIST(n); l; l = l->next) { 1787 m = l->regm; 1788 if (m->queue != ACTIVE) 1789 continue; 1790 DLIST_REMOVE(m, link); 1791 PUSHMLIST(m, worklistMoves, WLIST); 1792 } 1793} 1794 1795static void 1796EnableAdjMoves(REGW *nodes) 1797{ 1798 ADJL *w; 1799 REGW *n; 1800 1801 EnableMoves(nodes); 1802 for (w = ADJLIST(nodes); w; w = w->r_next) { 1803 n = w->a_temp; 1804 if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes) 1805 continue; 1806 EnableMoves(w->a_temp); 1807 } 1808} 1809 1810/* 1811 * Decrement the degree of node w for class c. 1812 */ 1813static void 1814DecrementDegree(REGW *w, int c) 1815{ 1816 int wast; 1817 1818#ifdef PCC_DEBUG 1819 RRDEBUG(("DecrementDegree: w %d, c %d\n", ASGNUM(w), c)); 1820#endif 1821 1822 wast = trivially_colorable(w); 1823 if (NCLASS(w, c) > 0) 1824 NCLASS(w, c)--; 1825 if (wast == trivially_colorable(w)) 1826 return; 1827 1828 EnableAdjMoves(w); 1829 DELWLIST(w); 1830 ONLIST(w) = 0; 1831 if (MoveRelated(w)) { 1832 PUSHWLIST(w, freezeWorklist); 1833 } else { 1834 PUSHWLIST(w, simplifyWorklist); 1835 } 1836} 1837 1838static void 1839Simplify(void) 1840{ 1841 REGW *w; 1842 ADJL *l; 1843 1844 w = POPWLIST(simplifyWorklist); 1845 PUSHWLIST(w, selectStack); 1846#ifdef PCC_DEBUG 1847 RDEBUG(("Simplify: node %d class %d\n", ASGNUM(w), w->r_class)); 1848#endif 1849 1850 l = w->r_adjList; 1851 for (; l; l = l->r_next) { 1852 if (ONLIST(l->a_temp) == &selectStack || 1853 ONLIST(l->a_temp) == &coalescedNodes) 1854 continue; 1855 DecrementDegree(l->a_temp, w->r_class); 1856 } 1857} 1858 1859static REGW * 1860GetAlias(REGW *n) 1861{ 1862 if (ONLIST(n) == &coalescedNodes) 1863 return GetAlias(ALIAS(n)); 1864 return n; 1865} 1866 1867static int 1868OK(REGW *t, REGW *r) 1869{ 1870#ifdef PCC_DEBUG 1871 RDEBUG(("OK: t %d CLASS(t) %d adjSet(%d,%d)=%d\n", 1872 ASGNUM(t), CLASS(t), ASGNUM(t), ASGNUM(r), adjSet(t, r))); 1873 1874 if (r2debug > 1) { 1875 ADJL *w; 1876 int ndeg = 0; 1877 printf("OK degree: "); 1878 for (w = ADJLIST(t); w; w = w->r_next) { 1879 if (ONLIST(w->a_temp) != &selectStack && 1880 ONLIST(w->a_temp) != &coalescedNodes) 1881 printf("%c%d ", CLASS(w->a_temp)+'@', 1882 ASGNUM(w->a_temp)), ndeg++; 1883 else 1884 printf("(%d) ", ASGNUM(w->a_temp)); 1885 } 1886 printf("\n"); 1887#if 0 1888 if (ndeg != DEGREE(t) && DEGREE(t) >= 0) 1889 printf("!!!ndeg %d != DEGREE(t) %d\n", ndeg, DEGREE(t)); 1890#endif 1891 } 1892#endif 1893 1894 if (trivially_colorable(t) || ONLIST(t) == &precolored || 1895 (adjSet(t, r) || !aliasmap(CLASS(t), COLOR(r))))/* XXX - check aliasmap */ 1896 return 1; 1897 return 0; 1898} 1899 1900static int 1901adjok(REGW *v, REGW *u) 1902{ 1903 ADJL *w; 1904 REGW *t; 1905 1906 RDEBUG(("adjok\n")); 1907 for (w = ADJLIST(v); w; w = w->r_next) { 1908 t = w->a_temp; 1909 if (ONLIST(t) == &selectStack || ONLIST(t) == &coalescedNodes) 1910 continue; 1911 if (OK(t, u) == 0) 1912 return 0; 1913 } 1914 RDEBUG(("adjok returns OK\n")); 1915 return 1; 1916} 1917 1918/* 1919 * Do a conservative estimation of whether two temporaries can 1920 * be coalesced. This is "Briggs-style" check. 1921 * Neither u nor v is precolored when called. 1922 */ 1923static int 1924Conservative(REGW *u, REGW *v) 1925{ 1926 ADJL *w, *ww; 1927 REGW *n; 1928 int xncl[NUMCLASS+1], mcl = 0, j; 1929 1930 for (j = 0; j < NUMCLASS+1; j++) 1931 xncl[j] = 0; 1932 /* 1933 * Increment xncl[class] up to K for each class. 1934 * If all classes has reached K then check colorability and return. 1935 */ 1936 for (w = ADJLIST(u); w; w = w->r_next) { 1937 n = w->a_temp; 1938 if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes) 1939 continue; 1940 if (xncl[CLASS(n)] == regK[CLASS(n)]) 1941 continue; 1942 if (!trivially_colorable(n) || ONLIST(n) == &precolored) 1943 xncl[CLASS(n)]++; 1944 if (xncl[CLASS(n)] < regK[CLASS(n)]) 1945 continue; 1946 if (++mcl == NUMCLASS) 1947 goto out; /* cannot get more out of it */ 1948 } 1949 for (w = ADJLIST(v); w; w = w->r_next) { 1950 n = w->a_temp; 1951 if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes) 1952 continue; 1953 if (xncl[CLASS(n)] == regK[CLASS(n)]) 1954 continue; 1955 /* ugly: have we been here already? */ 1956 for (ww = ADJLIST(u); ww; ww = ww->r_next) 1957 if (ww->a_temp == n) 1958 break; 1959 if (ww) 1960 continue; 1961 if (!trivially_colorable(n) || ONLIST(n) == &precolored) 1962 xncl[CLASS(n)]++; 1963 if (xncl[CLASS(n)] < regK[CLASS(n)]) 1964 continue; 1965 if (++mcl == NUMCLASS) 1966 break; 1967 } 1968out: j = trivially_colorable_p(CLASS(u), xncl); 1969 return j; 1970} 1971 1972static void 1973AddWorkList(REGW *w) 1974{ 1975 1976 if (ONLIST(w) != &precolored && !MoveRelated(w) && 1977 trivially_colorable(w)) { 1978 DELWLIST(w); 1979 PUSHWLIST(w, simplifyWorklist); 1980 } 1981} 1982 1983static void 1984Combine(REGW *u, REGW *v) 1985{ 1986 MOVL *m; 1987 ADJL *l; 1988 REGW *t; 1989 1990#ifdef PCC_DEBUG 1991 RDEBUG(("Combine (%d,%d)\n", ASGNUM(u), ASGNUM(v))); 1992#endif 1993 1994 if (ONLIST(v) == &freezeWorklist) { 1995 DELWLIST(v); 1996 } else { 1997 DELWLIST(v); 1998 } 1999 PUSHWLIST(v, coalescedNodes); 2000 ALIAS(v) = u; 2001#ifdef PCC_DEBUG 2002 if (r2debug) { 2003 printf("adjlist(%d): ", ASGNUM(v)); 2004 for (l = ADJLIST(v); l; l = l->r_next) 2005 printf("%d ", l->a_temp->nodnum); 2006 printf("\n"); 2007 } 2008#endif 2009#if 1 2010{ 2011 MOVL *m0 = MOVELIST(v); 2012 2013 for (m0 = MOVELIST(v); m0; m0 = m0->next) { 2014 for (m = MOVELIST(u); m; m = m->next) 2015 if (m->regm == m0->regm) 2016 break; /* Already on list */ 2017 if (m) 2018 continue; /* already on list */ 2019 MOVELISTADD(u, m0->regm); 2020 } 2021} 2022#else 2023 2024 if ((m = MOVELIST(u))) { 2025 while (m->next) 2026 m = m->next; 2027 m->next = MOVELIST(v); 2028 } else 2029 MOVELIST(u) = MOVELIST(v); 2030#endif 2031 EnableMoves(v); 2032 for (l = ADJLIST(v); l; l = l->r_next) { 2033 t = l->a_temp; 2034 if (ONLIST(t) == &selectStack || ONLIST(t) == &coalescedNodes) 2035 continue; 2036 /* Do not add edge if u cannot affect the colorability of t */ 2037 /* XXX - check aliasmap */ 2038 if (ONLIST(u) != &precolored || aliasmap(CLASS(t), COLOR(u))) 2039 AddEdge(t, u); 2040 DecrementDegree(t, CLASS(v)); 2041 } 2042 if (!trivially_colorable(u) && ONLIST(u) == &freezeWorklist) { 2043 DELWLIST(u); 2044 PUSHWLIST(u, spillWorklist); 2045 } 2046#ifdef PCC_DEBUG 2047 if (r2debug) { 2048 ADJL *w; 2049 printf("Combine %d class (%d): ", ASGNUM(u), CLASS(u)); 2050 for (w = ADJLIST(u); w; w = w->r_next) { 2051 if (ONLIST(w->a_temp) != &selectStack && 2052 ONLIST(w->a_temp) != &coalescedNodes) 2053 printf("%d ", ASGNUM(w->a_temp)); 2054 else 2055 printf("(%d) ", ASGNUM(w->a_temp)); 2056 } 2057 printf("\n"); 2058 } 2059#endif 2060} 2061 2062static void 2063Coalesce(void) 2064{ 2065 REGM *m; 2066 REGW *x, *y, *u, *v; 2067 2068 m = POPMLIST(worklistMoves); 2069 x = GetAlias(m->src); 2070 y = GetAlias(m->dst); 2071 2072 if (ONLIST(y) == &precolored) 2073 u = y, v = x; 2074 else 2075 u = x, v = y; 2076 2077#ifdef PCC_DEBUG 2078 RDEBUG(("Coalesce: src %d dst %d u %d v %d x %d y %d\n", 2079 ASGNUM(m->src), ASGNUM(m->dst), ASGNUM(u), ASGNUM(v), 2080 ASGNUM(x), ASGNUM(y))); 2081#endif 2082 2083 if (CLASS(m->src) != CLASS(m->dst)) 2084 comperr("Coalesce: src class %d, dst class %d", 2085 CLASS(m->src), CLASS(m->dst)); 2086 2087 if (u == v) { 2088 RDEBUG(("Coalesce: u == v\n")); 2089 PUSHMLIST(m, coalescedMoves, COAL); 2090 AddWorkList(u); 2091 } else if (ONLIST(v) == &precolored || adjSet(u, v)) { 2092 RDEBUG(("Coalesce: constrainedMoves\n")); 2093 PUSHMLIST(m, constrainedMoves, CONSTR); 2094 AddWorkList(u); 2095 AddWorkList(v); 2096 } else if ((ONLIST(u) == &precolored && adjok(v, u)) || 2097 (ONLIST(u) != &precolored && Conservative(u, v))) { 2098 RDEBUG(("Coalesce: Conservative\n")); 2099 PUSHMLIST(m, coalescedMoves, COAL); 2100 Combine(u, v); 2101 AddWorkList(u); 2102 } else { 2103 RDEBUG(("Coalesce: activeMoves\n")); 2104 PUSHMLIST(m, activeMoves, ACTIVE); 2105 } 2106} 2107 2108static void 2109coalasg(NODE *p, void *arg) 2110{ 2111 NODE *l; 2112 REGW *u; 2113 2114 if (p->n_op != ASSIGN || p->n_regw == NULL) 2115 return; 2116 l = p->n_left; 2117 if (l->n_op == TEMP) 2118 u = &nblock[regno(l)]; 2119 else if (l->n_op == REG) 2120 u = &ablock[regno(l)]; 2121 else 2122 return; 2123 2124 Combine(u, p->n_regw); 2125 AddWorkList(u); 2126} 2127 2128/* 2129 * Coalesce assign to a left reg with the assign temp node itself. 2130 * This has to be done before anything else. 2131 */ 2132static void 2133Coalassign(struct p2env *p2e) 2134{ 2135 struct interpass *ip; 2136 2137 DLIST_FOREACH(ip, &p2env.ipole, qelem) { 2138 if (ip->type == IP_NODE) 2139 walkf(ip->ip_node, coalasg, 0); 2140 } 2141} 2142 2143static void 2144FreezeMoves(REGW *u) 2145{ 2146 MOVL *w, *o; 2147 REGM *m; 2148 REGW *z; 2149 REGW *x, *y, *v; 2150 2151 for (w = MOVELIST(u); w; w = w->next) { 2152 m = w->regm; 2153 if (m->queue != WLIST && m->queue != ACTIVE) 2154 continue; 2155 x = m->src; 2156 y = m->dst; 2157 if (GetAlias(y) == GetAlias(u)) 2158 v = GetAlias(x); 2159 else 2160 v = GetAlias(y); 2161#ifdef PCC_DEBUG 2162 RDEBUG(("FreezeMoves: u %d (%d,%d) v %d\n", 2163 ASGNUM(u),ASGNUM(x),ASGNUM(y),ASGNUM(v))); 2164#endif 2165 DLIST_REMOVE(m, link); 2166 PUSHMLIST(m, frozenMoves, FROZEN); 2167 if (ONLIST(v) != &freezeWorklist) 2168 continue; 2169 for (o = MOVELIST(v); o; o = o->next) 2170 if (o->regm->queue == WLIST || o->regm->queue == ACTIVE) 2171 break; 2172 if (o == NULL) { 2173 z = v; 2174 DELWLIST(z); 2175 PUSHWLIST(z, simplifyWorklist); 2176 } 2177 } 2178} 2179 2180static void 2181Freeze(void) 2182{ 2183 REGW *u; 2184 2185 /* 2186 * To find out: 2187 * Check if the moves to freeze have exactly the same 2188 * interference edges. If they do, coalesce them instead, it 2189 * may free up other nodes that they interfere with. 2190 */ 2191 2192 /* 2193 * Select nodes to freeze first by using following criteria: 2194 * - Trivially colorable 2195 * - Single or few moves to less trivial nodes. 2196 */ 2197 DLIST_FOREACH(u, &freezeWorklist, link) { 2198 if (u >= &nblock[tempmax] || u < &nblock[tempmin]) 2199 continue; /* No short range temps */ 2200 if (!trivially_colorable(u)) 2201 continue; /* Prefer colorable nodes */ 2202 /* Check for at most two move-related nodes */ 2203 if (u->r_moveList->next && u->r_moveList->next->next) 2204 continue; 2205 /* Ok, remove node */ 2206 DLIST_REMOVE(u, link); 2207 u->r_onlist = 0; 2208 break; 2209 } 2210 if (u == &freezeWorklist) /* Nothing matched criteria, just take one */ 2211 u = POPWLIST(freezeWorklist); 2212 PUSHWLIST(u, simplifyWorklist); 2213#ifdef PCC_DEBUG 2214 RDEBUG(("Freeze %d\n", ASGNUM(u))); 2215#endif 2216 FreezeMoves(u); 2217} 2218 2219static void 2220SelectSpill(void) 2221{ 2222 REGW *w; 2223 2224 RDEBUG(("SelectSpill\n")); 2225#ifdef PCC_DEBUG 2226 if (r2debug) 2227 DLIST_FOREACH(w, &spillWorklist, link) 2228 printf("SelectSpill: %d\n", ASGNUM(w)); 2229#endif 2230 2231 /* First check if we can spill register variables */ 2232 DLIST_FOREACH(w, &spillWorklist, link) { 2233 if (w >= &nblock[tempmin] && w < &nblock[basetemp]) 2234 break; 2235 } 2236 2237 RRDEBUG(("SelectSpill: trying longrange\n")); 2238 if (w == &spillWorklist) { 2239 /* try to find another long-range variable */ 2240 DLIST_FOREACH(w, &spillWorklist, link) { 2241 if (innotspill(w - nblock)) 2242 continue; 2243 if (w >= &nblock[tempmin] && w < &nblock[tempmax]) 2244 break; 2245 } 2246 } 2247 2248 if (w == &spillWorklist) { 2249 RRDEBUG(("SelectSpill: trying not leaf\n")); 2250 /* no heuristics, just fetch first element */ 2251 /* but not if leaf */ 2252 DLIST_FOREACH(w, &spillWorklist, link) { 2253 if (w->r_nclass[0] == 0) 2254 break; 2255 } 2256 } 2257 2258 if (w == &spillWorklist) { 2259 /* Eh, only leaves :-/ Try anyway */ 2260 /* May not be useable */ 2261 w = DLIST_NEXT(&spillWorklist, link); 2262 RRDEBUG(("SelectSpill: need leaf\n")); 2263 } 2264 2265 DLIST_REMOVE(w, link); 2266 2267 PUSHWLIST(w, simplifyWorklist); 2268#ifdef PCC_DEBUG 2269 RDEBUG(("Freezing node %d\n", ASGNUM(w))); 2270#endif 2271 FreezeMoves(w); 2272} 2273 2274/* 2275 * Set class on long-lived temporaries based on its type. 2276 */ 2277static void 2278traclass(NODE *p, void *arg) 2279{ 2280 REGW *nb; 2281 2282 if (p->n_op != TEMP) 2283 return; 2284 2285 nb = &nblock[regno(p)]; 2286 if (CLASS(nb) == 0) 2287 CLASS(nb) = gclass(p->n_type); 2288} 2289 2290static void 2291paint(NODE *p, void *arg) 2292{ 2293 struct optab *q; 2294 REGW *w, *ww; 2295 int i; 2296 2297#ifdef notyet 2298 /* XXX - trashes rewrite of trees (short) */ 2299 if (!DLIST_ISEMPTY(&spilledNodes, link)) { 2300 p->n_reg = 0; 2301 return; 2302 } 2303#endif 2304 if (p->n_regw != NULL) { 2305 /* Must color all allocated regs also */ 2306 ww = w = p->n_regw; 2307 q = &table[TBLIDX(p->n_su)]; 2308 p->n_reg = COLOR(w); 2309 w++; 2310 if (q->needs & ALLNEEDS) 2311 for (i = 0; i < ncnt(q->needs); i++) { 2312 if (w->r_class == -1) 2313 p->n_reg |= ENCRA(COLOR(ww), i); 2314 else 2315 p->n_reg |= ENCRA(COLOR(w), i); 2316 w++; 2317 } 2318#ifdef notdef 2319 if (p->n_op == ASSIGN && p->n_left->n_op == REG && 2320 DECRA(p->n_reg, 0) != regno(p->n_left)) 2321 comperr("paint: %p clashing ASSIGN moves; %d != %d", p, 2322 DECRA(p->n_reg, 0), regno(p->n_left)); 2323#endif 2324 } else 2325 p->n_reg = -1; 2326 if (p->n_op == TEMP) { 2327 REGW *nb = &nblock[regno(p)]; 2328 regno(p) = COLOR(nb); 2329 if (TCLASS(p->n_su) == 0) 2330 SCLASS(p->n_su, CLASS(nb)); 2331 p->n_op = REG; 2332 setlval(p, 0); 2333 } 2334} 2335 2336/* 2337 * See if this node have a move that has been removed in Freeze 2338 * but as we can make use of anyway. 2339 */ 2340static int 2341colfind(int okColors, REGW *r) 2342{ 2343 REGW *w; 2344 MOVL *m; 2345 int c; 2346 2347 for (m = MOVELIST(r); m; m = m->next) { 2348 if ((w = m->regm->src) == r) 2349 w = m->regm->dst; 2350 w = GetAlias(w); 2351 if (ONLIST(w) != &coloredNodes && ONLIST(w) != &precolored) 2352 continue; /* Not yet colored */ 2353 if (CLASS(w) != CLASS(r)) 2354 comperr("colfind: move between classes"); 2355 2356 for (c = 0; c < regK[CLASS(w)]; c++) 2357 if (color2reg(c, CLASS(w)) == COLOR(w)) 2358 break; 2359 if (c == regK[CLASS(w)]) 2360 comperr("colfind: out of reg number"); 2361 2362 if (((1 << c) & okColors) == 0) { 2363 RDEBUG(("colfind: Failed coloring as %d\n", ASGNUM(w))); 2364 continue; 2365 } 2366 RDEBUG(("colfind: Recommend color from %d\n", ASGNUM(w))); 2367 return COLOR(w); 2368 } 2369 return color2reg(ffs(okColors)-1, CLASS(r)); 2370} 2371 2372static void 2373AssignColors(struct interpass *ip) 2374{ 2375 struct interpass *ip2; 2376 int okColors, c; 2377 REGW *o, *w; 2378 ADJL *x; 2379 2380 RDEBUG(("AssignColors\n")); 2381 while (!WLISTEMPTY(selectStack)) { 2382 w = POPWLIST(selectStack); 2383 okColors = classmask(CLASS(w)); 2384#ifdef PCC_DEBUG 2385 RDEBUG(("classmask av %d, class %d: %x\n", 2386 w->nodnum, CLASS(w), okColors)); 2387#endif 2388 2389 for (x = ADJLIST(w); x; x = x->r_next) { 2390 o = GetAlias(x->a_temp); 2391#ifdef PCC_DEBUG 2392 RRDEBUG(("Adj(%d): %d (%d)\n", 2393 ASGNUM(w), ASGNUM(o), ASGNUM(x->a_temp))); 2394#endif 2395 2396 if (ONLIST(o) == &coloredNodes || 2397 ONLIST(o) == &precolored) { 2398 c = aliasmap(CLASS(w), COLOR(o)); 2399 RRDEBUG(("aliasmap in class %d by color %d: " 2400 "%x, okColors %x\n", 2401 CLASS(w), COLOR(o), c, okColors)); 2402 2403 okColors &= ~c; 2404 } 2405 } 2406 if (okColors == 0) { 2407 PUSHWLIST(w, spilledNodes); 2408#ifdef PCC_DEBUG 2409 RDEBUG(("Spilling node %d\n", ASGNUM(w))); 2410#endif 2411 } else { 2412 COLOR(w) = colfind(okColors, w); 2413 PUSHWLIST(w, coloredNodes); 2414#ifdef PCC_DEBUG 2415 RDEBUG(("Coloring %d with %s, free %x\n", 2416 ASGNUM(w), rnames[COLOR(w)], okColors)); 2417#endif 2418 } 2419 } 2420 DLIST_FOREACH(w, &coalescedNodes, link) { 2421 REGW *ww = GetAlias(w); 2422 COLOR(w) = COLOR(ww); 2423 if (ONLIST(ww) == &spilledNodes) { 2424#ifdef PCC_DEBUG 2425 RDEBUG(("coalesced node %d spilled\n", w->nodnum)); 2426#endif 2427 ww = DLIST_PREV(w, link); 2428 DLIST_REMOVE(w, link); 2429 PUSHWLIST(w, spilledNodes); 2430 w = ww; 2431 } else { 2432#ifdef PCC_DEBUG 2433 RDEBUG(("Giving coalesced node %d color %s\n", 2434 w->nodnum, rnames[COLOR(w)])); 2435#endif 2436 } 2437 } 2438 2439#ifdef PCC_DEBUG 2440 if (r2debug) 2441 DLIST_FOREACH(w, &coloredNodes, link) 2442 printf("%d: color %s\n", ASGNUM(w), rnames[COLOR(w)]); 2443#endif 2444 if (DLIST_ISEMPTY(&spilledNodes, link)) { 2445 DLIST_FOREACH(ip2, ip, qelem) 2446 if (ip2->type == IP_NODE) 2447 walkf(ip2->ip_node, paint, 0); 2448 } 2449} 2450 2451static REGW *spole, *longsp; 2452/* 2453 * Store all spilled nodes in memory by fetching a temporary on the stack. 2454 * Will never end up here if not optimizing. 2455 */ 2456static void 2457longtemp(NODE *p, void *arg) 2458{ 2459 REGW *w; 2460 2461 if (p->n_op != TEMP) 2462 return; 2463 /* XXX - should have a bitmask to find temps to convert */ 2464 DLIST_FOREACH(w, spole, link) { 2465 if (w != &nblock[regno(p)]) 2466 continue; 2467#ifdef MYLONGTEMP 2468 MYLONGTEMP(p, w); 2469#endif 2470 if (w->r_class == 0) { 2471 w->r_color = freetemp(szty(p->n_type)); 2472 w->r_class = FPREG; /* XXX - assumption? */ 2473 } 2474 storemod(p, w->r_color, w->r_class); 2475 break; 2476 } 2477} 2478 2479/* 2480 * Check if this node is just something directly addressable. 2481 * XXX - should use target canaddr() when we knows that it is OK 2482 * for all targets. Can currently be a little too optimistic. 2483 */ 2484static int 2485regcanaddr(NODE *p) 2486{ 2487 int o = p->n_op; 2488 2489 if (o==NAME || o==ICON || o==OREG ) 2490 return 1; 2491 if (o == UMUL) { 2492 if (p->n_left->n_op == REG || p->n_left->n_op == TEMP) 2493 return 1; 2494 if ((p->n_left->n_op == PLUS || p->n_left->n_op == MINUS) && 2495 (p->n_left->n_left->n_op == REG || 2496 p->n_left->n_left->n_op == TEMP) && 2497 p->n_left->n_right->n_op == ICON) 2498 return 1; 2499 } 2500 return 0; 2501} 2502 2503static struct interpass *cip; 2504 2505static NODE * 2506shstore(NODE *p, struct interpass *ipp, REGW *w) 2507{ 2508 struct interpass *ip; 2509 int off; 2510 NODE *l; 2511 2512 off = freetemp(szty(p->n_type)); 2513 l = storenode(p->n_type, off); 2514 2515 ip = ipnode(mkbinode(ASSIGN, storenode(p->n_type, off), p, p->n_type)); 2516 DLIST_INSERT_BEFORE(ipp, ip, qelem); 2517 DLIST_REMOVE(w, link); 2518 return l; 2519} 2520 2521/* 2522 * Rewrite a tree by storing a variable in memory. 2523 * This code would work better if the SU computations were smarter. 2524 * XXX - must check if basic block structure is destroyed! 2525 * 2526 * 1) Ensure that both left & right are directly addressable. 2527 * 2) Save interfering long-term temporaries. 2528 * 3) If node itself not addressable, store the node itself. 2529 * 4) Store the parent. 2530 * 5) ...HELP!!??!! 2531 * 2532 * It might be a better idea to start with 3) or 4) first, but that will 2533 * make the code more complicated and I'm not sure it's worth it. 2534 */ 2535static int 2536shorttemp(NODE *p, NODE *parent, REGW *w) 2537{ 2538 struct interpass *nip; 2539 ADJL *ll; 2540 NODE *l, *r; 2541 int off, i, nc; 2542 2543 if (p->n_regw == NULL) 2544 goto down; 2545 2546 /* Check if this the correct node. */ 2547 nc = p->n_su == -1 ? 0 : ncnt(table[TBLIDX(p->n_su)].needs); 2548 for (i = 0; i < nc + 1; i++) 2549 if ((p->n_regw + i) == w) 2550 break; 2551 2552 if (i == nc + 1) { 2553down: switch (optype(p->n_op)) { 2554 case BITYPE: 2555 if (shorttemp(p->n_left, p, w) == 0) 2556 return shorttemp(p->n_right, p, w); 2557 return 1; 2558 case UTYPE: 2559 return shorttemp(p->n_left, p, w); 2560 case LTYPE: 2561 return 0; 2562 } 2563 } 2564 2565 RDEBUG(("Node %d (%p) to store\n", ASGNUM(w), p)); 2566 /* ensure that both left and right are addressable */ 2567 if (!regcanaddr(p) && !callop(p->n_op)) { 2568 /* this is neither leaf nor addressable */ 2569 if (p->n_op != ASSIGN && !regcanaddr(p->n_left)) { 2570 /* store left */ 2571 p->n_left = shstore(p->n_left, cip, w); 2572 RDEBUG(("Node %d stored left\n", ASGNUM(w))); 2573 return 1; 2574 } else if (optype(p->n_op) == BITYPE && 2575 !regcanaddr(p->n_right)) { 2576 /* store right */ 2577 p->n_right = shstore(p->n_right, cip, w); 2578 RDEBUG(("Node %d stored right\n", ASGNUM(w))); 2579 return 1; 2580 } 2581 } 2582 /* Store long-term temps that interferes */ 2583 ll = w->r_adjList; 2584 for (; ll; ll = ll->r_next) { 2585 if (ll->a_temp < &nblock[tempmax] && 2586 ll->a_temp >= &nblock[tempmin]) { 2587 longsp = ll->a_temp; 2588 RDEBUG(("Stored long %d\n", ASGNUM(longsp))); 2589 return 1; /* try again */ 2590 } 2591 } 2592 2593 if (regcanaddr(p)) { 2594 /* The node to spill is addressable, spill parent */ 2595 if (parent == NULL) 2596 comperr("cannot spill TOP node!"); 2597 p = parent; 2598 } 2599 off = freetemp(szty(p->n_type)); 2600 l = storenode(p->n_type, off); 2601 r = talloc(); 2602 *r = *p; 2603 nip = ipnode(mkbinode(ASSIGN, l, r, p->n_type)); 2604 storemod(p, off, FPREG); /* XXX */ 2605 DLIST_INSERT_BEFORE(cip, nip, qelem); 2606 DLIST_REMOVE(w, link); 2607 RDEBUG(("Stored parent node %d (%p)\n", ASGNUM(w), p)); 2608 return 1; 2609} 2610 2611static void 2612dlr(REGW *w) 2613{ 2614 if (w == 0) 2615 return; 2616 DLIST_REMOVE(w, link); 2617 RDEBUG(("Removing %d\n", ASGNUM(w))); 2618} 2619 2620/* 2621 * Return the number of the topmost temporary that should be spilled. 2622 * If temps below found, remove them from the spill list. 2623 * If two temps at the same level are found, remove one. 2624 * If both left & right have temps, store right and leave left. 2625 */ 2626static REGW * 2627toptemp(NODE *p, REGW *rw) 2628{ 2629 REGW *r, *l, *rv, *w; 2630 int nc, i; 2631 2632 l = r = rv = NULL; 2633 if (optype(p->n_op) != LTYPE) 2634 l = toptemp(p->n_left, rw); 2635 if (optype(p->n_op) == BITYPE) 2636 r = toptemp(p->n_right, rw); 2637 DLIST_FOREACH(w, rw, link) { 2638 nc = p->n_su == -1 ? 0 : ncnt(table[TBLIDX(p->n_su)].needs); 2639 for (i = 0; i < nc + 1; i++) { 2640 if ((p->n_regw + i) != w) 2641 continue; 2642 RDEBUG(("Found %d \n", ASGNUM(w))); 2643 dlr(rv); 2644 rv = w; 2645 } 2646 } 2647 if (rv != NULL) { 2648 dlr(l); 2649 dlr(r); 2650 } else if (r != NULL) { 2651 /* pick right, not left */ 2652 rv = r; 2653 dlr(l); 2654 } else { 2655 rv = l; 2656 } 2657 return rv; 2658} 2659 2660static void leafrewrite(struct interpass *ipole, REGW *rpole); 2661/* 2662 * Change the TEMPs in the ipole list to stack variables. 2663 */ 2664static void 2665treerewrite(struct interpass *ipole, REGW *rpole) 2666{ 2667 struct interpass *ip; 2668 REGW *w, longregs; 2669 2670 spole = rpole; 2671 2672 DLIST_FOREACH(ip, ipole, qelem) { 2673 if (ip->type != IP_NODE) 2674 continue; 2675 if ((w = toptemp(ip->ip_node, rpole)) == 0) 2676 continue; 2677 cip = ip; 2678 shorttemp(ip->ip_node, NULL, w); /* convert temps to oregs */ 2679 } 2680 if (longsp) { 2681#ifdef PCC_DEBUG 2682 RDEBUG(("Storing node %d to save short\n", ASGNUM(longsp))); 2683#endif 2684 if (longsp >= &nblock[tempmin] && longsp < &nblock[basetemp]) { 2685 int num = longsp - nblock - tempmin; 2686 nsavregs[num] = 1; 2687 } else { 2688 DLIST_INIT(&longregs, link); 2689 DLIST_INSERT_AFTER(&longregs, longsp, link); 2690 leafrewrite(ipole, &longregs); 2691 } 2692 } else if (!DLIST_ISEMPTY(spole, link)) 2693 comperr("treerewrite not empty"); 2694} 2695 2696/* 2697 * Change the TEMPs in the ipole list to stack variables. 2698 */ 2699static void 2700leafrewrite(struct interpass *ipole, REGW *rpole) 2701{ 2702 extern NODE *nodepole; 2703 extern int thisline; 2704 struct interpass *ip; 2705 2706 spole = rpole; 2707 DLIST_FOREACH(ip, ipole, qelem) { 2708 if (ip->type != IP_NODE) 2709 continue; 2710 nodepole = ip->ip_node; 2711 thisline = ip->lineno; 2712 walkf(ip->ip_node, longtemp, 0); /* convert temps to oregs */ 2713 } 2714 nodepole = NIL; 2715} 2716 2717/* 2718 * Avoid copying spilled argument to new position on stack. 2719 */ 2720static int 2721temparg(struct interpass *ipole, REGW *w) 2722{ 2723 struct interpass *ip; 2724 NODE *p; 2725 int reg; 2726 2727 ip = DLIST_NEXT(ipole, qelem); /* PROLOG */ 2728 while (ip->type != IP_DEFLAB) 2729 ip = DLIST_NEXT(ip, qelem); 2730 ip = DLIST_NEXT(ip, qelem); /* first NODE */ 2731 for (; ip->type != IP_DEFLAB; ip = DLIST_NEXT(ip, qelem)) { 2732 if (ip->type == IP_ASM) 2733 continue; 2734 p = ip->ip_node; 2735#ifdef notdef 2736 /* register args may already have been put on stack */ 2737 if (p->n_op != ASSIGN || p->n_left->n_op != TEMP) 2738 comperr("temparg"); 2739#endif 2740 if (p->n_op != ASSIGN || p->n_left->n_op != TEMP) 2741 continue; /* unknown tree */ 2742 2743 if (p->n_right->n_op != OREG) 2744 continue; /* arg in register */ 2745 if (w != &nblock[regno(p->n_left)]) 2746 continue; 2747 w->r_color = (int)getlval(p->n_right); 2748 reg = regno(p->n_right); 2749 tfree(p); 2750 /* Cannot DLIST_REMOVE here, would break basic blocks */ 2751 /* Make it a nothing instead */ 2752 ip->type = IP_ASM; 2753 ip->ip_asm = ""; 2754 return reg; 2755 } 2756 return 0; 2757} 2758 2759#define ONLYPERM 1 2760#define LEAVES 2 2761#define SMALL 3 2762 2763/* 2764 * Scan the whole function and search for temporaries to be stored 2765 * on-stack. 2766 * 2767 * Be careful to not destroy the basic block structure in the first scan. 2768 */ 2769static int 2770RewriteProgram(struct interpass *ip) 2771{ 2772 REGW shortregs, longregs, saveregs, *q; 2773 REGW *w; 2774 int rwtyp; 2775 2776 RDEBUG(("RewriteProgram\n")); 2777 DLIST_INIT(&shortregs, link); 2778 DLIST_INIT(&longregs, link); 2779 DLIST_INIT(&saveregs, link); 2780 2781 /* sort the temporaries in three queues, short, long and perm */ 2782 while (!DLIST_ISEMPTY(&spilledNodes, link)) { 2783 w = DLIST_NEXT(&spilledNodes, link); 2784 DLIST_REMOVE(w, link); 2785 2786 if (w >= &nblock[tempmin] && w < &nblock[basetemp]) { 2787 q = &saveregs; 2788 } else if (w >= &nblock[basetemp] && w < &nblock[tempmax]) { 2789 q = &longregs; 2790 } else 2791 q = &shortregs; 2792 DLIST_INSERT_AFTER(q, w, link); 2793 } 2794#ifdef PCC_DEBUG 2795 if (r2debug) { 2796 printf("permanent: "); 2797 DLIST_FOREACH(w, &saveregs, link) 2798 printf("%d ", ASGNUM(w)); 2799 printf("\nlong-lived: "); 2800 DLIST_FOREACH(w, &longregs, link) 2801 printf("%d ", ASGNUM(w)); 2802 printf("\nshort-lived: "); 2803 DLIST_FOREACH(w, &shortregs, link) 2804 printf("%d ", ASGNUM(w)); 2805 printf("\n"); 2806 } 2807#endif 2808 rwtyp = 0; 2809 2810 if (!DLIST_ISEMPTY(&saveregs, link)) { 2811 rwtyp = ONLYPERM; 2812 DLIST_FOREACH(w, &saveregs, link) { 2813 int num = w - nblock - tempmin; 2814 nsavregs[num] = 1; 2815 } 2816 } 2817 if (!DLIST_ISEMPTY(&longregs, link)) { 2818 rwtyp = LEAVES; 2819 DLIST_FOREACH(w, &longregs, link) { 2820 w->r_class = xtemps ? temparg(ip, w) : 0; 2821 } 2822 } 2823 2824 if (rwtyp == LEAVES) { 2825 leafrewrite(ip, &longregs); 2826 rwtyp = ONLYPERM; 2827 } 2828 2829 if (rwtyp == 0 && !DLIST_ISEMPTY(&shortregs, link)) { 2830 /* Must rewrite the trees */ 2831 treerewrite(ip, &shortregs); 2832#if 0 2833 if (xtemps) 2834 comperr("treerewrite"); 2835#endif 2836 rwtyp = SMALL; 2837 } 2838 2839 RDEBUG(("savregs %x rwtyp %d\n", 0, rwtyp)); 2840 2841 return rwtyp; 2842} 2843 2844#ifdef PCC_DEBUG 2845/* 2846 * Print TEMP/REG contents in a node. 2847 */ 2848void 2849prtreg(NODE *p) 2850{ 2851 int i, n = p->n_su == -1 ? 0 : ncnt(table[TBLIDX(p->n_su)].needs); 2852if (p->n_reg == -1) goto foo; 2853 if (use_regw || p->n_reg > 0x40000000 || p->n_reg < 0) { 2854 printf("TEMP "); 2855 if (p->n_regw != NULL) { 2856 for (i = 0; i < n+1; i++) 2857 printf("%d ", p->n_regw[i].nodnum); 2858 } else 2859 printf("<undef>"); 2860 } else { 2861foo: printf("REG "); 2862 if (p->n_reg != -1) { 2863 for (i = 0; i < n+1; i++) { 2864 int r = DECRA(p->n_reg, i); 2865 if (r >= MAXREGS) 2866 printf("<badreg> "); 2867 else 2868 printf("%s ", rnames[r]); 2869 } 2870 } else 2871 printf("<undef>"); 2872 } 2873} 2874#endif 2875 2876#ifdef notyet 2877/* 2878 * Assign instructions, calculate evaluation order and 2879 * set temporary register numbers. 2880 */ 2881static void 2882insgen() 2883{ 2884 clrsu(p); 2885 geninsn(); /* instruction assignment */ 2886 sucomp(); /* set evaluation order */ 2887 slong(); /* set long temp types */ 2888 sshort(); /* set short temp numbers */ 2889} 2890#endif 2891 2892/* 2893 * Do register allocation for trees by graph-coloring. 2894 */ 2895void 2896ngenregs(struct p2env *p2e) 2897{ 2898 struct interpass *ipole = &p2e->ipole; 2899 extern NODE *nodepole; 2900 struct interpass *ip; 2901 int i, j, tbits; 2902 int uu[NPERMREG] = { -1 }; 2903 int xnsavregs[NPERMREG]; 2904 int beenhere = 0; 2905 TWORD type; 2906 2907 DLIST_INIT(&lunused, link); 2908 DLIST_INIT(&lused, link); 2909 2910 /* 2911 * Do some setup before doing the real thing. 2912 */ 2913 tempmin = p2e->ipp->ip_tmpnum; 2914 2915 /* 2916 * Allocate space for the permanent registers in the 2917 * same block as the long-lived temporaries. 2918 * These temporaries will be handled the same way as 2919 * all other variables. 2920 */ 2921 basetemp = tempmin; 2922 nsavregs = xnsavregs; 2923 for (i = 0; i < NPERMREG; i++) 2924 xnsavregs[i] = 0; 2925 ndontregs = uu; /* currently never avoid any regs */ 2926 2927 tempmin -= (NPERMREG-1); 2928#ifdef notyet 2929 if (xavoidfp) 2930 dontregs |= REGBIT(FPREG); 2931#endif 2932 2933 /* Block for precolored nodes */ 2934 ablock = tmpalloc(sizeof(REGW)*MAXREGS); 2935 memset(ablock, 0, sizeof(REGW)*MAXREGS); 2936 for (i = 0; i < MAXREGS; i++) { 2937 ablock[i].r_onlist = &precolored; 2938 ablock[i].r_class = GCLASS(i); /* XXX */ 2939 ablock[i].r_color = i; 2940#ifdef PCC_DEBUG 2941 ablock[i].nodnum = i; 2942#endif 2943 } 2944 2945ssagain: 2946 tempmax = p2e->epp->ip_tmpnum; 2947#ifdef PCC_DEBUG 2948 nodnum = tempmax; 2949#endif 2950 tbits = tempmax - tempmin; /* # of temporaries */ 2951 xbits = tbits + MAXREGS; /* total size of live array */ 2952 if (tbits) { 2953 nblock = tmpalloc(tbits * sizeof(REGW)); 2954 2955 nblock -= tempmin; 2956#ifdef HAVE_C99_FORMAT 2957 RDEBUG(("nblock %p num %d size %zu\n", 2958 nblock, tbits, (size_t)(tbits * sizeof(REGW)))); 2959#endif 2960 } 2961 live = tmpalloc(BIT2BYTE(xbits)); 2962 2963#ifdef notyet 2964 TMPMARK(); 2965#endif 2966 2967 2968recalc: 2969onlyperm: /* XXX - should not have to redo all */ 2970 memset(edgehash, 0, sizeof(edgehash)); 2971 2972 /* clear adjacent node list */ 2973 for (i = 0; i < MAXREGS; i++) 2974 for (j = 0; j < NUMCLASS+1; j++) 2975 NCLASS(&ablock[i], j) = 0; 2976 2977 if (tbits) { 2978 memset(nblock+tempmin, 0, tbits * sizeof(REGW)); 2979#ifdef PCC_DEBUG 2980 for (i = tempmin; i < tempmax; i++) 2981 nblock[i].nodnum = i; 2982#endif 2983 } 2984 memset(live, 0, BIT2BYTE(xbits)); 2985 RPRINTIP(ipole); 2986 DLIST_INIT(&initial, link); 2987 ntsz = 0; 2988 DLIST_FOREACH(ip, ipole, qelem) { 2989 extern int thisline; 2990 if (ip->type != IP_NODE) 2991 continue; 2992 nodepole = ip->ip_node; 2993 thisline = ip->lineno; 2994 if (ip->ip_node->n_op != XASM) { 2995 clrsu(ip->ip_node); 2996 geninsn(ip->ip_node, FOREFF); 2997 } 2998 nsucomp(ip->ip_node); 2999 walkf(ip->ip_node, traclass, 0); 3000 } 3001 nodepole = NIL; 3002 RDEBUG(("nsucomp allocated %d temps (%d,%d)\n", 3003 tempmax-tempmin, tempmin, tempmax)); 3004 3005#ifdef PCC_DEBUG 3006 use_regw = 1; 3007 RPRINTIP(ipole); 3008 use_regw = 0; 3009#endif 3010 RDEBUG(("ngenregs: numtemps %d (%d, %d)\n", tempmax-tempmin, 3011 tempmin, tempmax)); 3012 3013 DLIST_INIT(&coalescedMoves, link); 3014 DLIST_INIT(&constrainedMoves, link); 3015 DLIST_INIT(&frozenMoves, link); 3016 DLIST_INIT(&worklistMoves, link); 3017 DLIST_INIT(&activeMoves, link); 3018 3019 /* Set class and move-related for perm regs */ 3020 for (i = 0; i < (NPERMREG-1); i++) { 3021 if (nsavregs[i]) 3022 continue; 3023 nblock[i+tempmin].r_class = GCLASS(permregs[i]); 3024 DLIST_INSERT_AFTER(&initial, &nblock[i+tempmin], link); 3025 moveadd(&nblock[i+tempmin], &ablock[permregs[i]]); 3026 addalledges(&nblock[i+tempmin]); 3027 } 3028 3029 Build(p2e); 3030 RDEBUG(("Build done\n")); 3031 MkWorklist(); 3032 RDEBUG(("MkWorklist done\n")); 3033 Coalassign(p2e); 3034 do { 3035 if (!WLISTEMPTY(simplifyWorklist)) 3036 Simplify(); 3037 else if (!WLISTEMPTY(worklistMoves)) 3038 Coalesce(); 3039 else if (!WLISTEMPTY(freezeWorklist)) 3040 Freeze(); 3041 else if (!WLISTEMPTY(spillWorklist)) 3042 SelectSpill(); 3043 } while (!WLISTEMPTY(simplifyWorklist) || !WLISTEMPTY(worklistMoves) || 3044 !WLISTEMPTY(freezeWorklist) || !WLISTEMPTY(spillWorklist)); 3045 AssignColors(ipole); 3046 3047 RDEBUG(("After AssignColors\n")); 3048 RPRINTIP(ipole); 3049 3050 if (!WLISTEMPTY(spilledNodes)) { 3051 switch (RewriteProgram(ipole)) { 3052 case ONLYPERM: 3053 goto onlyperm; 3054 case SMALL: 3055 optimize(p2e); 3056 if (beenhere++ == MAXLOOP) 3057 comperr("cannot color graph - COLORMAP() bug?"); 3058 if (xssa) 3059 goto ssagain; 3060 goto recalc; 3061 } 3062 } 3063 3064 /* fill in regs to save */ 3065 memset(p2e->ipp->ipp_regs, 0, sizeof(p2e->ipp->ipp_regs)); 3066 for (i = 0; i < NPERMREG-1; i++) { 3067 NODE *p; 3068 3069 if (nsavregs[i]) { 3070 BITSET(p2e->ipp->ipp_regs, permregs[i]); 3071 continue; /* Spilled */ 3072 } 3073 if (nblock[i+tempmin].r_color == permregs[i]) 3074 continue; /* Coalesced */ 3075 /* 3076 * If the original color of this permreg is used for 3077 * coloring another register, swap them to avoid 3078 * unnecessary moves. 3079 */ 3080 for (j = i+1; j < NPERMREG-1; j++) { 3081 if (nblock[j+tempmin].r_color != permregs[i]) 3082 continue; 3083 nblock[j+tempmin].r_color = nblock[i+tempmin].r_color; 3084 break; 3085 } 3086 if (j != NPERMREG-1) 3087 continue; 3088 3089 /* Generate reg-reg move nodes for save */ 3090 type = PERMTYPE(permregs[i]); 3091#ifdef PCC_DEBUG 3092 if (PERMTYPE(nblock[i+tempmin].r_color) != type) 3093 comperr("permreg botch"); 3094#endif 3095 p = mkbinode(ASSIGN, 3096 mklnode(REG, 0, nblock[i+tempmin].r_color, type), 3097 mklnode(REG, 0, permregs[i], type), type); 3098 p->n_reg = p->n_left->n_reg = p->n_right->n_reg = -1; 3099 clrsu(p); 3100 geninsn(p, FOREFF); 3101 ip = ipnode(p); 3102 DLIST_INSERT_AFTER(ipole->qelem.q_forw, ip, qelem); 3103 p = mkbinode(ASSIGN, mklnode(REG, 0, permregs[i], type), 3104 mklnode(REG, 0, nblock[i+tempmin].r_color, type), type); 3105 p->n_reg = p->n_left->n_reg = p->n_right->n_reg = -1; 3106 clrsu(p); 3107 geninsn(p, FOREFF); 3108 ip = ipnode(p); 3109 DLIST_INSERT_BEFORE(ipole->qelem.q_back, ip, qelem); 3110 } 3111 stktemp = freetemp(ntsz); 3112 memcpy(p2e->epp->ipp_regs, p2e->ipp->ipp_regs, sizeof(p2e->epp->ipp_regs)); 3113 /* Done! */ 3114} 3115