Quick Search:

Mode

Context

Displaying the whole file. None | Less | More | Full

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.237
 
1.238
 
MAIN:ragge:20140607140204
 
regs.c
_>11 /*      $Id$    */
 22 /*
 33  * Copyright (c) 2005 Anders Magnusson (ragge@ludd.luth.se).
 44  * All rights reserved.
 55  *
 66  * Redistribution and use in source and binary forms, with or without
 77  * modification, are permitted provided that the following conditions
 88  * are met:
 99  * 1. Redistributions of source code must retain the above copyright
 1010  *    notice, this list of conditions and the following disclaimer.
 1111  * 2. Redistributions in binary form must reproduce the above copyright
 1212  *    notice, this list of conditions and the following disclaimer in the
 1313  *    documentation and/or other materials provided with the distribution.
 1414  * 3. The name of the author may not be used to endorse or promote products
 1515  *    derived from this software without specific prior written permission
 1616  *
 1717  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 1818  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 1919  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 2020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 2121  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 2222  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 2323  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 2424  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 2525  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 2626  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 2727  */
 2828 
 2929 #include "pass2.h"
 3030 #include <string.h>
 3131 #ifdef HAVE_STRINGS_H
 3232 #include <strings.h>
 3333 #endif
 3434 #ifdef HAVE_STDINT_H
 3535 #include <stdint.h>
 3636 #endif
 3737 #include <stdlib.h>
 3838 
 3939 #define MAXLOOP 20 /* Max number of allocation loops XXX 3 should be enough */
 4040 
 4141 #ifndef MAX
 4242 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
 4343 #endif
 4444  
 4545 /*
 4646  * New-style register allocator using graph coloring.
 4747  * The design is based on the George and Appel paper
 4848  * "Iterated Register Coalescing", ACM Transactions, No 3, May 1996.
 4949  */
 5050 
 5151 #define BITALLOC(ptr,all,sz) { \
 5252         int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr, 0, sz__s); }
 5353 
 5454 #undef COMPERR_PERM_MOVE
 5555 #ifdef PCC_DEBUG
 5656 #define RDEBUG(x)       if (r2debug) printf x
 5757 #define RRDEBUG(x)      if (r2debug > 1) printf x
 5858 #define RPRINTIP(x)     if (r2debug) printip(x)
 5959 #define RDEBUGX(x)              x
 6060 #define UDEBUG(x)       if (u2debug) printf x
 6161 #define BDEBUG(x)       if (b2debug) printf x
 6262 #define BBDEBUG(x)      if (b2debug > 1) printf x
 6363 #else
 6464 #define RDEBUG(x)
 6565 #define RRDEBUG(x)
 6666 #define RPRINTIP(x)
 6767 #define RDEBUGX(x)
 6868 #define UDEBUG(x)
 6969 #define BDEBUG(x)
 7070 #define BBDEBUG(x)
 7171 #endif
 7272 
 7373 #define VALIDREG(p)     (p->n_op == REG && TESTBIT(validregs, regno(p)))
 7474 
 7575 /*
 7676  * Data structure overview for this implementation of graph coloring:
 7777  *
 7878  * Each temporary (called "node") is described by the type REGW. 
 7979  * Space for all nodes is allocated initially as an array, so
 8080  * the nodes can be can be referenced both by the node number and
 8181  * by pointer.
 8282  *
 8383  * All moves are represented by the type REGM, allocated when needed.
 8484  *
 8585  * The "live" set used during graph building is represented by a bitset.
 8686  *
 8787  * Interference edges are represented by struct AdjSet, hashed and linked
 8888  * from index into the edgehash array.
 8989  *
 9090  * A mapping from each node to the moves it is assiciated with is
 9191  * maintained by an array moveList which for each node number has a linked
 9292  * list of MOVL types, each pointing to a REGM.
 9393  *
 9494  * Adjacency list is maintained by the adjList array, indexed by the
 9595  * node number. Each adjList entry points to an ADJL type, and is a
 9696  * single-linked list for all adjacent nodes.
 9797  *
 9898  * degree, alias and color are integer arrays indexed by node number.
 9999  */
 100100 
 101101 /*
 102102  * linked list of adjacent nodes.
 103103  */
 104104 typedef struct regw3 {
 105105         struct regw3 *r_next;
 106106         struct regw *a_temp;
 107107 } ADJL;
 108108 
 109109 /*
 110110  * Structure describing a move.
 111111  */
 112112 typedef struct regm {
 113113         DLIST_ENTRY(regm) link;
 114114         struct regw *src, *dst;
 115115         int queue;
 116116 } REGM;
 117117 
 118118 typedef struct movlink {
 119119         struct movlink *next;
 120120         REGM *regm;
 121121 } MOVL;
 122122 
 123123 /*
 124124  * Structure describing a temporary.
 125125  */
 126126 typedef struct regw {
 127127         DLIST_ENTRY(regw) link;
 128128         ADJL *r_adjList;        /* linked list of adjacent nodes */
 129129         int r_class;            /* this nodes class */
 130130         int r_nclass[NUMCLASS+1];       /* count of adjacent classes */
 131131         struct regw *r_alias;           /* aliased temporary */
 132132         int r_color;            /* final node color */
 133133         struct regw *r_onlist;  /* which work list this node belongs to */
 134134         MOVL *r_moveList;       /* moves associated with this node */
 135135         int nodnum;             /* Human-readable node number */
 136136 } REGW;
 137137 
 138138 /*
 139139  * Worklists, a node is always on exactly one of these lists.
 140140  */
 141141 static REGW precolored, simplifyWorklist, freezeWorklist, spillWorklist,
 142142         spilledNodes, coalescedNodes, coloredNodes, selectStack;
 143143 static REGW initial, *nblock;
 144144 static void insnwalk(NODE *p);
 145145 #ifdef PCC_DEBUG
 146146 int use_regw;
 147147 #endif
 148148 int nodnum = 100;
 149149 int ntsz, stktemp;
 150150 #define SETNUM(x)       (x)->nodnum = nodnum++
 151151 #define ASGNUM(x)       (x)->nodnum
 152152 
 153153 #define ALLNEEDS (NACOUNT|NBCOUNT|NCCOUNT|NDCOUNT|NECOUNT|NFCOUNT|NGCOUNT)
 154154 
 155155 /* XXX */
 156156 REGW *ablock;
 157157 
 158158 static int tempmin, tempmax, basetemp, xbits;
 159159 /*
 160160  * nsavregs is an array that matches the permregs array.
 161161  * Each entry in the array may have the values:
 162162  * 0    : register coalesced, just ignore.
 163163  * 1    : save register on stack
 164164  * If the entry is 0 but the resulting color differs from the
 165165  * corresponding permregs index, add moves.
 166166  * XXX - should be a bitfield!
 167167  */
 168168 static int *nsavregs, *ndontregs;
 169169 
 170170 /*
 171171  * Return the REGW struct for a temporary.
 172172  * If first time touched, enter into list for existing vars.
 173173  * Only called from sucomp().
 174174  */
 175175 static REGW *
 176176 newblock(NODE *p)
 177177 {
 178178         REGW *nb;
 179179 
 180180 #ifdef PCC_DEBUG
 181181         if (regno(p) < tempmin || regno(p) >= tempmax)
 182182                 comperr("temp %p(%d) outside limits (%d-%d)",
 183183                     p, regno(p), tempmin, tempmax);
 184184 #endif
 185185         nb = &nblock[regno(p)];
 186186         if (nb->link.q_forw == 0) {
 187187                 DLIST_INSERT_AFTER(&initial, nb, link);
 188188 #ifdef PCC_DEBUG
 189189                 ASGNUM(nb) = regno(p);
 190190                 RDEBUG(("Adding longtime %d for tmp %d\n",
 191191                     nb->nodnum, regno(p)));
 192192 #endif
 193193         }
 194194         if (nb->r_class == 0)
 195195                 nb->r_class = gclass(p->n_type);
 196196 #ifdef PCC_DEBUG
 197197         RDEBUG(("newblock: p %p, node %d class %d\n",
 198198             p, nb->nodnum, nb->r_class));
 199199 #endif
 200200         return nb;
 201201 }
 202202 
 203203 /*
 204204  * Count the number of registers needed to evaluate a tree.
 205205  * This is only done to find the evaluation order of the tree.
 206206  * While here, assign temp numbers to the registers that will
 207207  * be needed when the tree is evaluated.
 208208  *
 209209  * While traversing the tree, assign REGW nodes to the registers
 210210  * used by all instructions:
 211211  *      - n_regw[0] is always set to the outgoing node. If the
 212212  *        instruction is 2-op (addl r0,r1) then an implicit move
 213213  *        is inserted just before the left (clobbered) operand.
 214214  *      - if the instruction has needs then REGW nodes are
 215215  *        allocated as n_regw[1] etc.
 216216  */
 217217 int
 218218 nsucomp(NODE *p)
 219219 {
 220220         struct optab *q;
 221221         int left, right;
 222222         int nreg, need, i, nxreg, o;
 223223         int nareg, nbreg, ncreg, ndreg, nereg, nfreg, ngreg;
 224224         REGW *w;
 225225 
 226226         o = optype(p->n_op);
 227227 
 228228         UDEBUG(("entering nsucomp, node %p\n", p));
 229229 
 230230         if (TBLIDX(p->n_su) == 0) {
 231231                 int a = 0, b;
 232232 
 233233                 p->n_regw = NULL;
 234234                 if (o == LTYPE ) {
 235235                         if (p->n_op == TEMP)
 236236                                 p->n_regw = newblock(p);
 237237                         else if (p->n_op == REG)
 238238                                 p->n_regw = &ablock[regno(p)];
 239239                 } else
 240240                         a = nsucomp(p->n_left);
 241241                 if (o == BITYPE) {
 242242                         b = nsucomp(p->n_right);
 243243                         if (b > a)
 244244                                 p->n_su |= DORIGHT;
 245245                         a = MAX(a, b);
 246246                 }
 247247                 return a;
 248248         }
 249249 
 250250         q = &table[TBLIDX(p->n_su)];
 251251 
 252252 #define NNEEDS(a,b) ((q->needs & a)/b)
 253253         for (i = (q->needs & NACOUNT), nareg = 0; i; i -= NAREG)
 254254                 nareg++;
 255255         for (i = (q->needs & NBCOUNT), nbreg = 0; i; i -= NBREG)
 256256                 nbreg++;
 257257         for (i = (q->needs & NCCOUNT), ncreg = 0; i; i -= NCREG)
 258258                 ncreg++;
 259259         for (i = (q->needs & NDCOUNT), ndreg = 0; i; i -= NDREG)
 260260                 ndreg++;
 261261         for (i = (q->needs & NECOUNT), nereg = 0; i; i -= NEREG)
 262262                 nereg++;
 263263         for (i = (q->needs & NFCOUNT), nfreg = 0; i; i -= NFREG)
 264264                 nfreg++;
 265265         for (i = (q->needs & NGCOUNT), ngreg = 0; i; i -= NGREG)
 266266                 ngreg++;
 267267 
 268268         if (ntsz < NNEEDS(NTMASK, NTEMP) * szty(p->n_type))
 269269                 ntsz = NNEEDS(NTMASK, NTEMP) * szty(p->n_type);
 270270 
 271271         nxreg = nareg + nbreg + ncreg + ndreg + nereg + nfreg + ngreg;
 272272         nreg = nxreg;
 273273         if (callop(p->n_op))
 274274                 nreg = MAX(fregs, nreg);
 275275 
 276276         if (o == BITYPE) {
 277277                 right = nsucomp(p->n_right);
 278278         } else
 279279                 right = 0;
 280280 
 281281         if (o != LTYPE)
 282282                 left = nsucomp(p->n_left);
 283283         else
 284284                 left = 0;
 285285 
 286286         UDEBUG(("node %p left %d right %d\n", p, left, right));
 287287 
 288288         if (o == BITYPE) {
 289289                 /* Two children */
 290290                 if (right == left) {
 291291                         need = left + MAX(nreg, 1);
 292292                 } else {
 293293                         need = MAX(right, left);
 294294                         need = MAX(need, nreg);
 295295                 }
 296296                 if (setorder(p) == 0) {
 297297                         /* XXX - should take care of overlapping needs */
 298298                         if (right > left) {
 299299                                 p->n_su |= DORIGHT;
 300300                         } else if (right == left) {
<> 301+#if 0
  302+        /* XXX - need something more clever when large left trees */
301303                                 /* A favor to 2-operand architectures */
 302304                                 if ((q->rewrite & RRIGHT) == 0)
 303305                                         p->n_su |= DORIGHT;
<> 306+#endif
304307                         }
 305308                 }
 306309         } else if (o != LTYPE) {
 307310                 /* One child */
 308311                 need = MAX(right, left) + nreg;
 309312         } else
 310313                 need = nreg;
 311314 
 312315         if (p->n_op == TEMP)
 313316                 (void)newblock(p);
 314317 
 315318         if (TCLASS(p->n_su) == 0 && nxreg == 0) {
 316319                 UDEBUG(("node %p no class\n", p));
 317320                 p->n_regw = NULL; /* may be set earlier */
 318321                 return need;
 319322         }
 320323 
 321324 #ifdef PCC_DEBUG
 322325 #define ADCL(n, cl)     \
 323326         for (i = 0; i < n; i++, w++) {  w->r_class = cl; \
 324327                 DLIST_INSERT_BEFORE(&initial, w, link);  SETNUM(w); \
 325328                 UDEBUG(("Adding " #n " %d\n", w->nodnum)); \
 326329         }
 327330 #else
 328331 #define ADCL(n, cl)     \
 329332         for (i = 0; i < n; i++, w++) {  w->r_class = cl; \
 330333                 DLIST_INSERT_BEFORE(&initial, w, link);  SETNUM(w); \
 331334         }
 332335 #endif
 333336 
 334337         UDEBUG(("node %p numregs %d\n", p, nxreg+1));
 335338         w = p->n_regw = tmpalloc(sizeof(REGW) * (nxreg+1));
 336339         memset(w, 0, sizeof(REGW) * (nxreg+1));
 337340 
 338341         w->r_class = TCLASS(p->n_su);
 339342         if (w->r_class == 0)
 340343                 w->r_class = gclass(p->n_type);
 341344         w->r_nclass[0] = o == LTYPE; /* XXX store leaf info here */
 342345         SETNUM(w);
 343346         if (w->r_class)
 344347                 DLIST_INSERT_BEFORE(&initial, w, link);
 345348 #ifdef PCC_DEBUG
 346349         UDEBUG(("Adding short %d class %d\n", w->nodnum, w->r_class));
 347350 #endif
 348351         w++;
 349352         ADCL(nareg, CLASSA);
 350353         ADCL(nbreg, CLASSB);
 351354         ADCL(ncreg, CLASSC);
 352355         ADCL(ndreg, CLASSD);
 353356         ADCL(nereg, CLASSE);
 354357         ADCL(nfreg, CLASSF);
 355358         ADCL(ngreg, CLASSG);
 356359 
 357360         if (q->rewrite & RESC1) {
 358361                 w = p->n_regw + 1;
 359362                 w->r_class = -1;
 360363                 DLIST_REMOVE(w,link);
 361364         } else if (q->rewrite & RESC2) {
 362365                 w = p->n_regw + 2;
 363366                 w->r_class = -1;
 364367                 DLIST_REMOVE(w,link);
 365368         } else if (q->rewrite & RESC3) {
 366369                 w = p->n_regw + 3;
 367370                 w->r_class = -1;
 368371                 DLIST_REMOVE(w,link);
 369372         }
 370373 
 371374         UDEBUG(("node %p return regs %d\n", p, need));
 372375 
 373376         return need;
 374377 }
 375378 
 376379 #define CLASS(x)        (x)->r_class
 377380 #define NCLASS(x,c)     (x)->r_nclass[c]
 378381 #define ADJLIST(x)      (x)->r_adjList
 379382 #define ALIAS(x)        (x)->r_alias
 380383 #define ONLIST(x)       (x)->r_onlist
 381384 #define MOVELIST(x)     (x)->r_moveList
 382385 #define COLOR(x)        (x)->r_color
 383386 
 384387 static bittype *live;
 385388 
 386389 #define PUSHWLIST(w, l) DLIST_INSERT_AFTER(&l, w, link); w->r_onlist = &l
 387390 #define POPWLIST(l)     popwlist(&l);
 388391 #define DELWLIST(w)     DLIST_REMOVE(w, link)
 389392 #define WLISTEMPTY(h)   DLIST_ISEMPTY(&h,link)
 390393 #define PUSHMLIST(w, l, q)      DLIST_INSERT_AFTER(&l, w, link); w->queue = q
 391394 #define POPMLIST(l)     popmlist(&l);
 392395 
 393396 #define trivially_colorable(x) \
 394397         trivially_colorable_p((x)->r_class, (x)->r_nclass)
 395398 /*
 396399  * Determine if a node is trivially colorable ("degree < K").
 397400  * This implementation is a dumb one, without considering speed.
 398401  */
 399402 static int
 400403 trivially_colorable_p(int c, int *n)
 401404 {
 402405         int r[NUMCLASS+1];
 403406         int i;
 404407 
 405408         for (i = 1; i < NUMCLASS+1; i++)
 406409                 r[i] = n[i] < regK[i] ? n[i] : regK[i];
 407410 
 408411 #if 0
 409412         /* add the exclusion nodes. */
 410413         /* XXX can we do someything smart here? */
 411414         /* worst-case for exclusion nodes are better than the `worst-case' */
 412415         for (; excl; excl >>= 1)
 413416                 if (excl & 1)
 414417                         r[c]++;
 415418 #endif
 416419 
 417420         i = COLORMAP(c, r);
 418421         if (i < 0 || i > 1)
 419422                 comperr("trivially_colorable_p");
 420423         RRDEBUG(("trivially_colorable_p: n[1] %d n[2] %d n[3] %d n[4] "
 421424             "%d for class %d, triv %d\n", n[1], n[2], n[3], n[4], c, i));
 422425         return i;
 423426 }
 424427 
 425428 int
 426429 ncnt(int needs)
 427430 {
 428431         int i = 0;
 429432 
 430433         while (needs & NACOUNT)
 431434                 needs -= NAREG, i++;
 432435         while (needs & NBCOUNT)
 433436                 needs -= NBREG, i++;
 434437         while (needs & NCCOUNT)
 435438                 needs -= NCREG, i++;
 436439         while (needs & NDCOUNT)
 437440                 needs -= NDREG, i++;
 438441         while (needs & NECOUNT)
 439442                 needs -= NEREG, i++;
 440443         while (needs & NFCOUNT)
 441444                 needs -= NFREG, i++;
 442445         while (needs & NGCOUNT)
 443446                 needs -= NGREG, i++;
 444447         return i;
 445448 }
 446449 
 447450 static REGW *
 448451 popwlist(REGW *l)
 449452 {
 450453         REGW *w = DLIST_NEXT(l, link);
 451454 
 452455         DLIST_REMOVE(w, link);
 453456         w->r_onlist = NULL;
 454457         return w;
 455458 }
 456459 
 457460 /*
 458461  * Move lists, a move node is always on only one list.
 459462  */
 460463 static REGM coalescedMoves, constrainedMoves, frozenMoves,
 461464         worklistMoves, activeMoves;
 462465 enum { COAL, CONSTR, FROZEN, WLIST, ACTIVE };
 463466 
 464467 static REGM *
 465468 popmlist(REGM *l)
 466469 {
 467470         REGM *w = DLIST_NEXT(l, link);
 468471 
 469472         DLIST_REMOVE(w, link);
 470473         return w;
 471474 }
 472475 
 473476 /*
 474477  * About data structures used in liveness analysis:
 475478  *
 476479  * The temporaries generated in pass1 are numbered between tempmin and
 477480  * tempmax.  Temporaries generated in pass2 are numbered above tempmax,
 478481  * so they are sequentially numbered.
 479482  *
 480483  * Bitfields are used for liveness.  Bit arrays are allocated on the
 481484  * heap for the "live" variable and on the stack for the in, out, gen
 482485  * and killed variables. Therefore, for a temp number, the bit number must
 483486  * be biased with tempmin.
 484487  *
 485488  * There may be an idea to use a different data structure to store
 486489  * pass2 allocated temporaries, because they are very sparse.
 487490  */
 488491 
 489492 #ifdef PCC_DEBUG
 490493 static void
 491494 LIVEADD(int x)
 492495 {
 493496         RDEBUG(("Liveadd: %d\n", x));
 494497         if (x >= MAXREGS && (x < tempmin || x >= tempmax))
 495498                 comperr("LIVEADD: out of range");
 496499         if (x < MAXREGS) {
 497500                 BITSET(live, x);
 498501         } else
 499502                 BITSET(live, (x-tempmin+MAXREGS));
 500503 }
 501504 
 502505 static void
 503506 LIVEDEL(int x)
 504507 {
 505508         RDEBUG(("Livedel: %d\n", x));
 506509 
 507510         if (x >= MAXREGS && (x < tempmin || x >= tempmax))
 508511                 comperr("LIVEDEL: out of range");
 509512         if (x < MAXREGS) {
 510513                 BITCLEAR(live, x);
 511514         } else
 512515                 BITCLEAR(live, (x-tempmin+MAXREGS));
 513516 }
 514517 #else
 515518 #define LIVEADD(x) \
 516519         (x >= MAXREGS ? BITSET(live, (x-tempmin+MAXREGS)) : BITSET(live, x))
 517520 #define LIVEDEL(x) \
 518521         (x >= MAXREGS ? BITCLEAR(live, (x-tempmin+MAXREGS)) : BITCLEAR(live, x))
 519522 #endif
 520523 
 521524 static struct lives {
 522525         DLIST_ENTRY(lives) link;
 523526         REGW *var;
 524527 } lused, lunused;
 525528 
 526529 static void
 527530 LIVEADDR(REGW *x)
 528531 {
 529532         struct lives *l;
 530533 
 531534 #ifdef PCC_DEBUG
 532535         RDEBUG(("LIVEADDR: %d\n", x->nodnum));
 533536         DLIST_FOREACH(l, &lused, link)
 534537                 if (l->var == x)
 535538                         return;
 536539 #if 0
 537540                         comperr("LIVEADDR: multiple %d", ASGNUM(x));
 538541 #endif
 539542 #endif
 540543         if (!DLIST_ISEMPTY(&lunused, link)) {
 541544                 l = DLIST_NEXT(&lunused, link);
 542545                 DLIST_REMOVE(l, link);
 543546         } else
 544547                 l = tmpalloc(sizeof(struct lives));
 545548 
 546549         l->var = x;
 547550         DLIST_INSERT_AFTER(&lused, l, link);
 548551 }
 549552 
 550553 static void
 551554 LIVEDELR(REGW *x)
 552555 {
 553556         struct lives *l;
 554557 
 555558 #ifdef PCC_DEBUG
 556559         RDEBUG(("LIVEDELR: %d\n", x->nodnum));
 557560 #endif
 558561         DLIST_FOREACH(l, &lused, link) {
 559562                 if (l->var != x)
 560563                         continue;
 561564                 DLIST_REMOVE(l, link);
 562565                 DLIST_INSERT_AFTER(&lunused, l, link);
 563566                 return;
 564567         }
 565568 #if 0
 566569         comperr("LIVEDELR: %p not found", x);
 567570 #endif
 568571 }
 569572 
 570573 #define MOVELISTADD(t, p) movelistadd(t, p)
 571574 #define WORKLISTMOVEADD(s,d) worklistmoveadd(s,d)
 572575 
 573576 static void
 574577 movelistadd(REGW *t, REGM *p)
 575578 {
 576579         MOVL *w = tmpalloc(sizeof(MOVL));
 577580 
 578581         w->regm = p;
 579582         w->next = t->r_moveList;
 580583         t->r_moveList = w;
 581584 }
 582585 
 583586 static REGM *
 584587 worklistmoveadd(REGW *src, REGW *dst)
 585588 {
 586589         REGM *w = tmpalloc(sizeof(REGM));
 587590 
 588591         DLIST_INSERT_AFTER(&worklistMoves, w, link);
 589592         w->src = src;
 590593         w->dst = dst;
 591594         w->queue = WLIST;
 592595         return w;
 593596 }
 594597 
 595598 #define HASHSZ  16384
 596599 struct AdjSet {
 597600         struct AdjSet *next;
 598601         REGW *u, *v;
 599602 } *edgehash[HASHSZ];
 600603 
 601604 /* Check if a node pair is adjacent */
 602605 static int
 603606 adjSet(REGW *u, REGW *v)
 604607 {
 605608         struct AdjSet *w;
 606609         REGW *t;
 607610 
 608611         if (ONLIST(u) == &precolored) {
 609612                 ADJL *a = ADJLIST(v);
 610613                 /*
 611614                  * Check if any of the registers that have edges against v
 612615                  * alias to u.
 613616                  */
 614617                 for (; a; a = a->r_next) {
 615618                         if (ONLIST(a->a_temp) != &precolored)
 616619                                 continue;
 617620                         t = a->a_temp;
 618621                         if (interferes(t - ablock, u - ablock))
 619622                                 return 1;
 620623                 }
 621624         }
 622625 
 623626         w = edgehash[(u->nodnum+v->nodnum)& (HASHSZ-1)];
 624627 
 625628         for (; w; w = w->next) {
 626629                 if ((u == w->u && v == w->v) || (u == w->v && v == w->u))
 627630                         return 1;
 628631         }
 629632         return 0;
 630633 }
 631634 
 632635 /* Add a pair to adjset.  No check for dups */
 633636 static int
 634637 adjSetadd(REGW *u, REGW *v)
 635638 {
 636639         struct AdjSet *w;
 637640         int x;
 638641 
 639642         x = (u->nodnum+v->nodnum)& (HASHSZ-1);
 640643         for (w = edgehash[x]; w; w = w->next)
 641644                 if ((u == w->u && v == w->v) || (u == w->v && v == w->u))
 642645                         return 1;
 643646 
 644647         w = tmpalloc(sizeof(struct AdjSet));
 645648         w->u = u, w->v = v;
 646649         w->next = edgehash[x];
 647650         edgehash[x] = w;
 648651         return 0;
 649652 }
 650653 
 651654 /*
 652655  * Add an interference edge between two nodes.
 653656  */
 654657 static void
 655658 AddEdge(REGW *u, REGW *v)
 656659 {
 657660         ADJL *x;
 658661 
 659662 #ifdef PCC_DEBUG
 660663         RRDEBUG(("AddEdge: u %d v %d\n", ASGNUM(u), ASGNUM(v)));
 661664 
 662665 #if 0
 663666         if (ASGNUM(u) == 0)
 664667                 comperr("AddEdge 0");
 665668 #endif
 666669         if (CLASS(u) == 0 || CLASS(v) == 0)
 667670                 comperr("AddEdge class == 0 (%d=%d, %d=%d)",
 668671                     CLASS(u), ASGNUM(u), CLASS(v), ASGNUM(v));
 669672 #endif
 670673 
 671674         if (u == v)
 672675                 return;
 673676         if (adjSetadd(u, v))
 674677                 return;
 675678 
 676679 #if 0
 677680         if (ONLIST(u) == &precolored || ONLIST(v) == &precolored)
 678681                 comperr("precolored node in AddEdge");
 679682 #endif
 680683 
 681684         if (ONLIST(u) != &precolored) {
 682685                 x = tmpalloc(sizeof(ADJL));
 683686                 x->a_temp = v;
 684687                 x->r_next = u->r_adjList;
 685688                 u->r_adjList = x;
 686689                 NCLASS(u, CLASS(v))++;
 687690         }
 688691 
 689692         if (ONLIST(v) != &precolored) {
 690693                 x = tmpalloc(sizeof(ADJL));
 691694                 x->a_temp = u;
 692695                 x->r_next = v->r_adjList;
 693696                 v->r_adjList = x;
 694697                 NCLASS(v, CLASS(u))++;
 695698         }
 696699 
 697700 #if 0
 698701         RDEBUG(("AddEdge: u %d(d %d) v %d(d %d)\n", u, DEGREE(u), v, DEGREE(v)));
 699702 #endif
 700703 }
 701704 
 702705 static int
 703706 MoveRelated(REGW *n)
 704707 {
 705708         MOVL *l;
 706709         REGM *w;
 707710 
 708711         for (l = MOVELIST(n); l; l = l->next) {
 709712                 w = l->regm;
 710713                 if (w->queue == ACTIVE || w->queue == WLIST)
 711714                         return 1;
 712715         }
 713716         return 0;
 714717 }
 715718 
 716719 static void
 717720 MkWorklist(void)
 718721 {
 719722         REGW *w;
 720723 
 721724         RDEBUGX(int s=0);
 722725         RDEBUGX(int f=0);
 723726         RDEBUGX(int d=0);
 724727 
 725728         DLIST_INIT(&precolored, link);
 726729         DLIST_INIT(&simplifyWorklist, link);
 727730         DLIST_INIT(&freezeWorklist, link);
 728731         DLIST_INIT(&spillWorklist, link);
 729732         DLIST_INIT(&spilledNodes, link);
 730733         DLIST_INIT(&coalescedNodes, link);
 731734         DLIST_INIT(&coloredNodes, link);
 732735         DLIST_INIT(&selectStack, link);
 733736 
 734737         /*
 735738          * Remove all nodes from the initial list and put them on
 736739          * one of the worklists.
 737740          */
 738741         while (!DLIST_ISEMPTY(&initial, link)) {
 739742                 w = DLIST_NEXT(&initial, link);
 740743                 DLIST_REMOVE(w, link);
 741744                 if (!trivially_colorable(w)) {
 742745                         PUSHWLIST(w, spillWorklist);
 743746                         RDEBUGX(s++);
 744747                 } else if (MoveRelated(w)) {
 745748                         PUSHWLIST(w, freezeWorklist);
 746749                         RDEBUGX(f++);
 747750                 } else {
 748751                         PUSHWLIST(w, simplifyWorklist);
 749752                         RDEBUGX(d++);
 750753                 }
 751754         }
 752755         RDEBUG(("MkWorklist: spill %d freeze %d simplify %d\n", s,f,d));
 753756 }
 754757 
 755758 static void
 756759 addalledges(REGW *e)
 757760 {
 758761         int i, j, k;
 759762         struct lives *l;
 760763 
 761764 #ifdef PCC_DEBUG
 762765         RDEBUG(("addalledges for %d\n", e->nodnum));
 763766 #endif
 764767 
 765768         if (e->r_class == -1)
 766769                 return; /* unused */
 767770 
 768771         if (ONLIST(e) != &precolored) {
 769772                 for (i = 0; ndontregs[i] >= 0; i++)
 770773                         AddEdge(e, &ablock[ndontregs[i]]);
 771774         }
 772775 
 773776         /* First add to long-lived temps and hard regs */
 774777         RDEBUG(("addalledges longlived "));
 775778         for (i = 0; i < xbits; i += NUMBITS) {
 776779                 if ((k = live[i/NUMBITS])) {
 777780                         while (k) {
 778781                                 j = ffs(k)-1;
 779782                                 if (i+j < MAXREGS)
 780783                                         AddEdge(&ablock[i+j], e);
 781784                                 else
 782785                                         AddEdge(&nblock[i+j+tempmin-MAXREGS],e);
 783786                                 RRDEBUG(("%d ", i+j+tempmin));
 784787                                 k &= ~(1 << j);
 785788                         }
 786789                 }
 787790 #if NUMBITS > 32 /* XXX hack for LP64 */
 788791                 k = (live[i/NUMBITS] >> 32);
 789792                 while (k) {
 790793                         j = ffs(k)-1;
 791794                         if (i+j+32 < MAXREGS)
 792795                                 AddEdge(&ablock[i+j+32], e);
 793796                         else
 794797                                 AddEdge(&nblock[i+j+tempmin-MAXREGS+32], e);
 795798                         RRDEBUG(("%d ", i+j+tempmin+32));
 796799                         k &= ~(1 << j);
 797800                 }
 798801 #endif
 799802         }
 800803         RDEBUG(("done\n"));
 801804         /* short-lived temps */
 802805         RDEBUG(("addalledges shortlived "));
 803806         DLIST_FOREACH(l, &lused, link) {
 804807 #ifdef PCC_DEBUG
 805808                 RRDEBUG(("%d ", ASGNUM(l->var)));
 806809 #endif
 807810                 AddEdge(l->var, e);
 808811         }
 809812         RDEBUG(("done\n"));
 810813 }
 811814 
 812815 /*
 813816  * Add a move edge between def and use.
 814817  */
 815818 static void
 816819 moveadd(REGW *def, REGW *use)
 817820 {
 818821         REGM *r;
 819822         MOVL *w;
 820823 
 821824         if (def == use)
 822825                 return; /* no move to itself XXX - ``shouldn't happen'' */
 823826 #ifdef PCC_DEBUG
 824827         RDEBUG(("moveadd: def %d use %d\n", ASGNUM(def), ASGNUM(use)));
 825828 #endif
 826829 
 827830         /*
 828831          * Check if we are already on move list.
 829832          * XXX How can that happen ???
 830833          */
 831834         for (w = MOVELIST(def); w; w = w->next) {
 832835                 if ((w->regm->src == def && w->regm->dst == use) ||
 833836                     (w->regm->src == use && w->regm->dst == def))
 834837                         return; /* already there XXX reverse? */
 835838         }
 836839 
 837840         r = WORKLISTMOVEADD(use, def);
 838841         MOVELISTADD(def, r);
 839842         MOVELISTADD(use, r);
 840843 }
 841844 
 842845 /*
 843846  * Traverse arguments backwards.
 844847  * XXX - can this be tricked in some other way?
 845848  */
 846849 static void
 847850 argswalk(NODE *p)
 848851 {
 849852 
 850853         if (p->n_op == CM) {
 851854                 argswalk(p->n_left);
 852855                 insnwalk(p->n_right);
 853856         } else
 854857                 insnwalk(p);
 855858 }
 856859 
 857860 /*
 858861  * Add to (or remove from) live set variables that must not
 859862  * be clobbered when traversing down on the other leg for
 860863  * a BITYPE node.
 861864  */
 862865 static void
 863866 setlive(NODE *p, int set, REGW *rv)
 864867 {
 865868         if (rv != NULL) {
 866869                 if (rv->nodnum < MAXREGS &&
 867870                     TESTBIT(validregs, rv->nodnum) == 0)
 868871                         return;
 869872                 set ? LIVEADDR(rv) : LIVEDELR(rv);
 870873                 return;
 871874         }
 872875 
 873876         if (p->n_regw != NULL) {
 874877                 if (p->n_regw->nodnum < MAXREGS &&
 875878                     TESTBIT(validregs, p->n_regw->nodnum) == 0)
 876879                         return;
 877880                 set ? LIVEADDR(p->n_regw) : LIVEDELR(p->n_regw);
 878881                 return;
 879882         }
 880883 
 881884         switch (optype(p->n_op)) {
 882885         case LTYPE:
 883886                 if (p->n_op == TEMP || VALIDREG(p))
 884887                         set ? LIVEADD(regno(p)) : LIVEDEL(regno(p));
 885888                 break;
 886889         case BITYPE:
 887890                 setlive(p->n_right, set, rv);
 888891                 /* FALLTHROUGH */
 889892         case UTYPE:
 890893                 setlive(p->n_left, set, rv);
 891894                 break;
 892895         }
 893896 }
 894897 
 895898 /*
 896899  * Add edges for temporary w against all temporaries that may be
 897900  * used simultaneously (like index registers).
 898901  */
 899902 static void
 900903 addedge_r(NODE *p, REGW *w)
 901904 {
 902905         RRDEBUG(("addedge_r: node %p regw %p\n", p, w));
 903906 
 904907         if (p->n_regw != NULL) {
 905908                 if (p->n_regw->nodnum < MAXREGS &&
 906909                     TESTBIT(validregs, p->n_regw->nodnum) == 0)
 907910                         return;
 908911                 AddEdge(p->n_regw, w);
 909912                 return;
 910913         }
 911914 
 912915         if (optype(p->n_op) == BITYPE)
 913916                 addedge_r(p->n_right, w);
 914917         if (optype(p->n_op) != LTYPE)
 915918                 addedge_r(p->n_left, w);
 916919 }
 917920 
 918921 /*
 919922  * delete early clobber liveness. Only interesting on regs.
 920923  */
 921924 static void
 922925 delcl(NODE *p)
 923926 {
 924927         int cw;
 925928 
 926929         if (p->n_op == ICON && p->n_type == STRTY)
 927930                 return;
 928931         cw = xasmcode(p->n_name);
 929932         if ((cw & XASMCONSTR) == 0 || !XASMISOUT(cw))
 930933                 return;
 931934         if (XASMVAL(cw) != 'r')
 932935                 return;
 933936         LIVEDEL(regno(p->n_left));
 934937 }
 935938 
 936939 /*
 937940  * add/del parameter from live set.
 938941  */
 939942 static void
 940943 setxarg(NODE *p)
 941944 {
 942945         int i, ut = 0, in = 0;
 943946         REGW *rw;
 944947         int c, cw;
 945948 
 946949         if (p->n_op == ICON && p->n_type == STRTY)
 947950                 return;
 948951 
 949952         RDEBUG(("setxarg %p %s\n", p, p->n_name));
 950953         cw = xasmcode(p->n_name);
 951954         if (XASMISINP(cw))
 952955                 in = 1;
 953956         if (XASMISOUT(cw) && !(cw & XASMCONSTR))
 954957                 ut = 1;
 955958 
 956959         c = XASMVAL(cw);
 957960 
 958961 #ifdef MYSETXARG
 959962         MYSETXARG;
 960963 #endif
 961964 
 962965         switch (c) {
 963966         case 'm':
 964967         case 'g':
 965968                 /* must find all TEMPs/REGs and set them live */
 966969                 if (p->n_left->n_op != REG && p->n_left->n_op != TEMP) {
 967970                         insnwalk(p->n_left);
 968971                         break;
 969972                 }
 970973                 /* FALLTHROUGH */
 971974         case 'r':
 972975                 i = regno(p->n_left);
 973976                 rw = p->n_left->n_op == REG ? ablock : nblock;
 974977                 if (ut) {
 975978                         LIVEDEL(i);
 976979                 }
 977980                 if (in) {
 978981                         LIVEADD(i);
 979982                 }
 980983                 addalledges(&rw[i]);
 981984                 break;
 982985 
 983986         case 'i':
 984987         case 'n':
 985988                 break;
 986989         default:
 987990                 comperr("bad ixarg %s", p->n_name);
 988991         }
 989992 #ifdef MYSETXARG
 990993         MYSETXARG;
 991994 #endif
 992995 }
 993996 
 994997 /*
 995998  * Do the in-tree part of liveness analysis. (the difficult part)
 996999  *
 9971000  * Walk down the tree in reversed-evaluation order (backwards).
 9981001  * The moves and edges inserted and evaluation order for
 9991002  * instructions when code is emitted is described here, hence
 10001003  * this code runs the same but backwards.
 10011004  *
 10021005  * 2-op reclaim LEFT: eval L, move to DEST, eval R.
 10031006  *      moveadd L,DEST; addedge DEST,R
 10041007  * 2-op reclaim LEFT DORIGHT: eval R, eval L, move to DEST.
 10051008  *      moveadd L,DEST; addedge DEST,R; addedge L,R
 10061009  * 2-op reclaim RIGHT; eval L, eval R, move to DEST.
 10071010  *      moveadd R,DEST; addedge DEST,L; addedge L,R
 10081011  * 2-op reclaim RIGHT DORIGHT: eval R, move to DEST, eval L.
 10091012  *      moveadd R,DEST; addedge DEST,L
 10101013  * 3-op: eval L, eval R
 10111014  *      addedge L,R
 10121015  * 3-op DORIGHT: eval R, eval L
 10131016  *      addedge L,R
 10141017  *
 10151018  * Instructions with special needs are handled just like these variants,
 10161019  * with the exception of extra added moves and edges.
 10171020  * Moves to special regs are scheduled after the evaluation of both legs.
 10181021  */
 10191022 
 10201023 static void
 10211024 insnwalk(NODE *p)
 10221025 {
 10231026         int o = p->n_op;
 10241027         struct optab *q = &table[TBLIDX(p->n_su)];
 10251028         REGW *lr, *rr, *rv, *r, *rrv, *lrv;
 10261029         NODE *lp, *rp;
 10271030         int i, n;
 10281031 
 10291032         RDEBUG(("insnwalk %p\n", p));
 10301033 
 10311034         rv = p->n_regw;
 10321035 
 10331036         rrv = lrv = NULL;
 10341037         if (p->n_op == ASSIGN &&
 10351038             (p->n_left->n_op == TEMP || VALIDREG(p->n_left))) {
 10361039                 lr = p->n_left->n_op == TEMP ? nblock : ablock;
 10371040                 i = regno(p->n_left);
 10381041                 LIVEDEL(i);     /* remove assigned temp from live set */
 10391042                 addalledges(&lr[i]);
 10401043         }
 10411044 
 10421045         /* Add edges for the result of this node */
 10431046         if (rv && (q->visit & INREGS || o == TEMP || VALIDREG(p)))      
 10441047                 addalledges(rv);
 10451048 
 10461049         /* special handling of CALL operators */
 10471050         if (callop(o)) {
 10481051                 if (rv)
 10491052                         moveadd(rv, &ablock[RETREG(p->n_type)]);
 10501053                 for (i = 0; tempregs[i] >= 0; i++)
 10511054                         addalledges(&ablock[tempregs[i]]);
 10521055         }
 10531056 
 10541057         /* for special return value registers add moves */
 10551058         if ((q->needs & NSPECIAL) && (n = rspecial(q, NRES)) >= 0) {
 10561059                 rv = &ablock[n];
 10571060                 moveadd(p->n_regw, rv);
 10581061         }
 10591062 
 10601063         /* Check leaves for results in registers */
 10611064         lr = optype(o) != LTYPE ? p->n_left->n_regw : NULL;
 10621065         lp = optype(o) != LTYPE ? p->n_left : NULL;
 10631066         rr = optype(o) == BITYPE ? p->n_right->n_regw : NULL;
 10641067         rp = optype(o) == BITYPE ? p->n_right : NULL;
 10651068 
 10661069         /* simple needs */
 10671070         n = ncnt(q->needs);
 10681071         for (i = 0; i < n; i++) {
 10691072 #if 1
 10701073                 static int ncl[] =
 10711074                     { 0, NASL, NBSL, NCSL, NDSL, NESL, NFSL, NGSL };
 10721075                 static int ncr[] =
 10731076                     { 0, NASR, NBSR, NCSR, NDSR, NESR, NFSR, NGSR };
 10741077                 int j;
 10751078 
 10761079                 /* edges are already added */
 10771080                 if ((r = &p->n_regw[1+i])->r_class == -1) {
 10781081                         r = p->n_regw;
 10791082                 } else {
 10801083                         AddEdge(r, p->n_regw);
 10811084                         addalledges(r);
 10821085                 }
 10831086                 if (optype(o) != LTYPE && (q->needs & ncl[CLASS(r)]) == 0)
 10841087                         addedge_r(p->n_left, r);
 10851088                 if (optype(o) == BITYPE && (q->needs & ncr[CLASS(r)]) == 0)
 10861089                         addedge_r(p->n_right, r);
 10871090                 for (j = i + 1; j < n; j++) {
 10881091                         if (p->n_regw[j+1].r_class == -1)
 10891092                                 continue;
 10901093                         AddEdge(r, &p->n_regw[j+1]);
 10911094                 }
 10921095 #else
 10931096                 if ((r = &p->n_regw[1+i])->r_class == -1)
 10941097                         continue;
 10951098                 addalledges(r);
 10961099                 if (optype(o) != LTYPE && (q->needs & NASL) == 0)
 10971100                         addedge_r(p->n_left, r);
 10981101                 if (optype(o) == BITYPE && (q->needs & NASR) == 0)
 10991102                         addedge_r(p->n_right, r);
 11001103 #endif
 11011104         }
 11021105 
 11031106         /* special needs */
 11041107         if (q->needs & NSPECIAL) {
 11051108                 struct rspecial *rc;
 11061109                 for (rc = nspecial(q); rc->op; rc++) {
 11071110                         switch (rc->op) {
 11081111 #define ONLY(c,s) if (c) s(c, &ablock[rc->num])
 11091112                         case NLEFT:
 11101113                                 addalledges(&ablock[rc->num]);
 11111114                                 ONLY(lr, moveadd);
 11121115                                 if (optype(o) != BITYPE)
 11131116                                         break;
 11141117                                 /* FALLTHROUGH */
 11151118                         case NORIGHT:
 11161119                                 addedge_r(p->n_right, &ablock[rc->num]);
 11171120                                 break;
 11181121                         case NRIGHT:
 11191122                                 addalledges(&ablock[rc->num]);
 11201123                                 ONLY(rr, moveadd);
 11211124                                 /* FALLTHROUGH */
 11221125                         case NOLEFT:
 11231126                                 addedge_r(p->n_left, &ablock[rc->num]);
 11241127                                 break;
 11251128                         case NEVER:
 11261129                                 addalledges(&ablock[rc->num]);
 11271130                                 break;
 11281131 #undef ONLY
 11291132                         }
 11301133                 }
 11311134         }
 11321135 
 11331136         if (o == ASSIGN) {
 11341137                 /* avoid use of unhandled registers */
 11351138                 if (p->n_left->n_op == REG &&
 11361139                     !TESTBIT(validregs, regno(p->n_left)))
 11371140                         lr = NULL;
 11381141                 if (p->n_right->n_op == REG &&
 11391142                     !TESTBIT(validregs, regno(p->n_right)))
 11401143                         rr = NULL;
 11411144                 /* needs special treatment */
 11421145                 if (lr && rr)
 11431146                         moveadd(lr, rr);
 11441147                 if (lr && rv)
 11451148                         moveadd(lr, rv);
 11461149                 if (rr && rv)
 11471150                         moveadd(rr, rv);
 11481151         } else if (callop(o)) {
 11491152                 int *c;
 11501153 
 11511154                 for (c = livecall(p); *c != -1; c++) {
 11521155                         addalledges(ablock + *c);
 11531156                         LIVEADD(*c);
 11541157                 }
 11551158         } else if (q->rewrite & (RESC1|RESC2|RESC3)) {
 11561159                 if (lr && rr)
 11571160                         AddEdge(lr, rr);
 11581161         } else if (q->rewrite & RLEFT) {
 11591162                 if (lr && rv)
 11601163                         moveadd(rv, lr), lrv = rv;
 11611164                 if (rv && rp)
 11621165                         addedge_r(rp, rv);
 11631166         } else if (q->rewrite & RRIGHT) {
 11641167                 if (rr && rv)
 11651168                         moveadd(rv, rr), rrv = rv;
 11661169                 if (rv && lp)
 11671170                         addedge_r(lp, rv);
 11681171         }
 11691172 
 11701173         switch (optype(o)) {
 11711174         case BITYPE:
 11721175                 if (p->n_op == ASSIGN &&
 11731176                     (p->n_left->n_op == TEMP || p->n_left->n_op == REG)) {
 11741177                         /* only go down right node */
 11751178                         insnwalk(p->n_right);
 11761179                 } else if (callop(o)) {
 11771180                         insnwalk(p->n_left);
 11781181                         /* Do liveness analysis on arguments (backwards) */
 11791182                         argswalk(p->n_right);
 11801183                 } else if ((p->n_su & DORIGHT) == 0) {
 11811184                         setlive(p->n_left, 1, lrv);
 11821185                         insnwalk(p->n_right);
 11831186                         setlive(p->n_left, 0, lrv);
 11841187                         insnwalk(p->n_left);
 11851188                 } else {
 11861189                         setlive(p->n_right, 1, rrv);
 11871190                         insnwalk(p->n_left);
 11881191                         setlive(p->n_right, 0, rrv);
 11891192                         insnwalk(p->n_right);
 11901193                 }
 11911194                 break;
 11921195 
 11931196         case UTYPE:
 11941197                 insnwalk(p->n_left);
 11951198                 break;
 11961199 
 11971200         case LTYPE:
 11981201                 switch (o) {
 11991202                 case REG:
 12001203                         if (!TESTBIT(validregs, regno(p)))
 12011204                                 break; /* never add moves */
 12021205                         /* FALLTHROUGH */
 12031206                 case TEMP:
 12041207                         i = regno(p);
 12051208                         rr = (o == TEMP ? &nblock[i] :  &ablock[i]);
 12061209                         if (rv != rr) {
 12071210                                 addalledges(rr);
 12081211                                 moveadd(rv, rr);
 12091212                         }
 12101213                         LIVEADD(i);
 12111214                         break;
 12121215 
 12131216                 case OREG: /* XXX - not yet */
 12141217                         break;
 12151218 
 12161219                 default:
 12171220                         break;
 12181221                 }
 12191222                 break;
 12201223         }
 12211224 }
 12221225 
 12231226 static bittype **gen, **killed, **in, **out;
 12241227 
 12251228 struct notspill {
 12261229         SLIST_ENTRY(notspill) link;
 12271230         int spnum;
 12281231 };
 12291232 SLIST_HEAD(, notspill) nothead;
 12301233 
 12311234 static int
 12321235 innotspill(int n)
 12331236 {
 12341237         struct notspill *nsp;
 12351238 
 12361239         SLIST_FOREACH(nsp, &nothead, link)
 12371240                 if (nsp->spnum == n)
 12381241                         return 1;
 12391242         return 0;
 12401243 }
 12411244 
 12421245 static void
 12431246 addnotspill(int n)
 12441247 {
 12451248         struct notspill *nsp;
 12461249 
 12471250         if (innotspill(n))
 12481251                 return;
 12491252         nsp = tmpalloc(sizeof(struct notspill));
 12501253         nsp->spnum = n;
 12511254         SLIST_INSERT_LAST(&nothead, nsp, link);
 12521255 }
 12531256 
 12541257 /*
 12551258  * Found an extended assembler node, so growel out gen/killed nodes.
 12561259  */
 12571260 static void
 12581261 xasmionize(NODE *p, void *arg)
 12591262 {
 12601263         int bb = *(int *)arg;
 12611264         int cw, b;
 12621265 
 12631266         if (p->n_op == ICON && p->n_type == STRTY)
 12641267                 return; /* dummy end marker */
 12651268 
 12661269         cw = xasmcode(p->n_name);
 12671270         if (XASMVAL(cw) == 'n' /* || XASMVAL(cw) == 'm' */)
 12681271                 return; /* no flow analysis */
 12691272         p = p->n_left;
 12701273 
 12711274         if (XASMVAL(cw) == 'g' && p->n_op != TEMP && p->n_op != REG)
 12721275                 return; /* no flow analysis */
 12731276 
 12741277         b = regno(p);
 12751278         if (XASMVAL(cw) == 'r' && p->n_op == TEMP)
 12761279                 addnotspill(b);
 12771280         if (XASMVAL(cw) == 'm') {
 12781281                 if (p->n_op == UMUL && p->n_left->n_op == TEMP) {
 12791282                         p = p->n_left;
 12801283                         b = regno(p);
 12811284                         addnotspill(b);
 12821285                         cw &= ~(XASMASG|XASMINOUT);
 12831286                 } else
 12841287                         return;
 12851288         }
 12861289 #define MKTOFF(r)       ((r) - tempmin + MAXREGS)
 12871290         if (XASMISOUT(cw)) {
 12881291                 if (p->n_op == TEMP) {
 12891292                         BITCLEAR(gen[bb], MKTOFF(b));
 12901293                         BITSET(killed[bb], MKTOFF(b));
 12911294                 } else if (p->n_op == REG) {
 12921295                         BITCLEAR(gen[bb], b);
 12931296                         BITSET(killed[bb], b);
 12941297                 } else
 12951298                         uerror("bad xasm node type %d", p->n_op);
 12961299         }
 12971300         if (XASMISINP(cw)) {
 12981301                 if (p->n_op == TEMP) {
 12991302                         BITSET(gen[bb], MKTOFF(b));
 13001303                 } else if (p->n_op == REG) {
 13011304                         BITSET(gen[bb], b);
 13021305                 } else if (optype(p->n_op) != LTYPE) {
 13031306                         if (XASMVAL(cw) == 'r')
 13041307                                 uerror("couldn't find available register");
 13051308                         else
 13061309                                 uerror("bad xasm node type2");
 13071310                 }
 13081311         }
 13091312 }
 13101313 
 13111314 #ifndef XASMCONSTREGS
 13121315 #define XASMCONSTREGS(x) (-1)
 13131316 #endif
 13141317 
 13151318 /*
 13161319  * Check that given constraints are valid.
 13171320  */
 13181321 static void
 13191322 xasmconstr(NODE *p, void *arg)
 13201323 {
 13211324         int i;
 13221325 
 13231326         if (p->n_op == ICON && p->n_type == STRTY)
 13241327                 return; /* no constraints */
 13251328 
 13261329         if (strcmp(p->n_name, "cc") == 0 || strcmp(p->n_name, "memory") == 0)
 13271330                 return;
 13281331 
 13291332         for (i = 0; i < MAXREGS; i++)
 13301333                 if (strcmp(rnames[i], p->n_name) == 0) {
 13311334                         addalledges(&ablock[i]);
 13321335                         return;
 13331336                 }
 13341337         if ((i = XASMCONSTREGS(p->n_name)) < 0)
 13351338                 comperr("unsupported xasm constraint %s", p->n_name);
 13361339         addalledges(&ablock[i]);
 13371340 }
 13381341 
 13391342 #define RUP(x) (((x)+NUMBITS-1)/NUMBITS)
 13401343 #define SETCOPY(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] = f[i]
 13411344 #define SETSET(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] |= f[i]
 13421345 #define SETCLEAR(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] &= ~f[i]
 13431346 #define SETCMP(v,t,f,i,n) for (i = 0; i < RUP(n); i++) \
 13441347         if (t[i] != f[i]) v = 1
 13451348 #define SETEMPTY(t,sz)  memset(t, 0, BIT2BYTE(sz))
 13461349 
 13471350 static int
 13481351 deldead(NODE *p, bittype *lvar)
 13491352 {
 13501353         NODE *q;
 13511354         int ty, rv = 0;
 13521355 
 13531356 #define BNO(p) (regno(p) - tempmin+MAXREGS)
 13541357         if (p->n_op == TEMP)
 13551358                 BITSET(lvar, BNO(p));
 13561359         if (asgop(p->n_op) && p->n_left->n_op == TEMP &&
 13571360             TESTBIT(lvar, BNO(p->n_left)) == 0) {
 13581361                 /*
 13591362                  * Not live, must delete the right tree at least
 13601363                  * down to next statement with side effects.
 13611364                  */
 13621365                 BDEBUG(("DCE deleting temp %d\n", regno(p->n_left)));
 13631366                 nfree(p->n_left);
 13641367                 q = p->n_right;
 13651368                 *p = *q;
 13661369                 nfree(q);
 13671370                 rv = 1;
 13681371         }
 13691372         ty = optype(p->n_op);
 13701373         if (ty != LTYPE)
 13711374                 rv |= deldead(p->n_left, lvar);
 13721375         if (ty == BITYPE)
 13731376                 rv |= deldead(p->n_right, lvar);
 13741377         return rv;
 13751378 }
 13761379 
 13771380 /*
 13781381  * Ensure that the su field is empty before generating instructions.
 13791382  */
 13801383 static void
 13811384 clrsu(NODE *p)
 13821385 {
 13831386         int o = optype(p->n_op);
 13841387 
 13851388         p->n_su = 0;
 13861389         if (o != LTYPE)
 13871390                 clrsu(p->n_left);
 13881391         if (o == BITYPE)
 13891392                 clrsu(p->n_right);
 13901393 }
 13911394 
 13921395 /*
 13931396  * Do dead code elimination.
 13941397  */
 13951398 static int
 13961399 dce(struct p2env *p2e)
 13971400 {
 13981401         extern struct interpass prepole;
 13991402         struct basicblock *bb;
 14001403         struct interpass *ip;
 14011404         NODE *p;
 14021405         bittype *lvar;
 14031406         int i, bbnum, fix = 0;
 14041407 
 14051408         BDEBUG(("Entering DCE\n"));
 14061409         /*
 14071410          * Traverse over the basic blocks.
 14081411          * if an assignment is found that writes to a temporary
 14091412          * that is not live out, remove that assignment and its legs.
 14101413          */
 14111414         DLIST_INIT(&prepole, qelem);
 14121415         BITALLOC(lvar, tmpalloc, xbits);
 14131416         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 14141417                 bbnum = bb->bbnum;
 14151418                 BBDEBUG(("DCE bblock %d, start %p last %p\n",
 14161419                     bbnum, bb->first, bb->last));
 14171420                 SETCOPY(lvar, out[bbnum], i, xbits);
 14181421                 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) {
 14191422                         if (ip->type == IP_NODE && deldead(ip->ip_node, lvar)) {
 14201423                                 if ((p = deluseless(ip->ip_node)) == NULL) {
 14211424                                         struct interpass *previp;
 14221425                                         struct basicblock *prevbb;
 14231426 
 14241427                                         if (ip == bb->first && ip == bb->last) {
 14251428                                                 /* Remove basic block */
 14261429                                                 previp = DLIST_PREV(ip, qelem);
 14271430                                                 DLIST_REMOVE(ip, qelem);
 14281431                                                 prevbb = DLIST_PREV(bb, bbelem);
 14291432                                                 DLIST_REMOVE(bb, bbelem);
 14301433                                                 bb = prevbb;
 14311434                                         } else if (ip == bb->first) {
 14321435                                                 bb->first =
 14331436                                                     DLIST_NEXT(ip, qelem);
 14341437                                                 DLIST_REMOVE(ip, qelem);
 14351438                                         } else if (ip == bb->last) {
 14361439                                                 previp = DLIST_PREV(ip, qelem);
 14371440                                                 DLIST_REMOVE(ip, qelem);
 14381441                                                 bb->last = previp;
 14391442                                                 bb = DLIST_PREV(bb, bbelem);
 14401443                                         } else {
 14411444                                                 previp = DLIST_NEXT(ip, qelem);
 14421445                                                 DLIST_REMOVE(ip, qelem);
 14431446                                                 ip = previp;
 14441447                                                 fix++;
 14451448                                                 continue;
 14461449                                         }
 14471450                                         fix++;
 14481451                                         BDEBUG(("bb %d: DCE ip %p deleted\n",
 14491452                                             bbnum, ip));
 14501453                                         break;
 14511454                                 } else while (!DLIST_ISEMPTY(&prepole, qelem)) {
 14521455                                         struct interpass *tipp;
 14531456 
 14541457                                         BDEBUG(("bb %d: DCE doing ip prepend\n", bbnum));
 14551458                                         tipp = DLIST_NEXT(&prepole, qelem);
 14561459                                         DLIST_REMOVE(tipp, qelem);
 14571460                                         DLIST_INSERT_BEFORE(ip, tipp, qelem);
 14581461                                         if (ip == bb->first)
 14591462                                                 bb->first = tipp;
 14601463                                         fix++;
 14611464                                         BDEBUG(("DCE ip prepended\n"));
 14621465                                 }
 14631466                                 if (ip->type == IP_NODE) {
 14641467                                         clrsu(p);
 14651468                                         geninsn(p, FOREFF);
 14661469                                         nsucomp(p);
 14671470                                         ip->ip_node = p;
 14681471                                 }
 14691472                         }
 14701473                         if (ip == bb->first)
 14711474                                 break;
 14721475                 }
 14731476         }
 14741477         BDEBUG(("DCE fix %d\n", fix));
 14751478         return fix;
 14761479 }
 14771480 
 14781481 /*
 14791482  * Set/clear long term liveness for regs and temps.
 14801483  */
 14811484 static void
 14821485 unionize(NODE *p, int bb)
 14831486 {
 14841487         int i, o, ty;
 14851488 
 14861489         if ((o = p->n_op) == TEMP) {
 14871490 #ifdef notyet
 14881491                 for (i = 0; i < szty(p->n_type); i++) {
 14891492                         BITSET(gen[bb], (regno(p) - tempmin+i+MAXREGS));
 14901493                 }
 14911494 #else
 14921495                 i = 0;
 14931496                 BITSET(gen[bb], (regno(p) - tempmin+i+MAXREGS));
 14941497 #endif
 14951498         } else if (VALIDREG(p)) {
 14961499                 BITSET(gen[bb], regno(p));
 14971500         }
 14981501         if (asgop(o)) {
 14991502                 if (p->n_left->n_op == TEMP) {
 15001503                         int b = regno(p->n_left) - tempmin+MAXREGS;
 15011504 #ifdef notyet
 15021505                         for (i = 0; i < szty(p->n_type); i++) {
 15031506                                 BITCLEAR(gen[bb], (b+i));
 15041507                                 BITSET(killed[bb], (b+i));
 15051508                         }
 15061509 #else
 15071510                         i = 0;
 15081511                         BITCLEAR(gen[bb], (b+i));
 15091512                         BITSET(killed[bb], (b+i));
 15101513 #endif
 15111514                         unionize(p->n_right, bb);
 15121515                         return;
 15131516                 } else if (VALIDREG(p->n_left)) {
 15141517                         int b = regno(p->n_left);
 15151518                         BITCLEAR(gen[bb], b);
 15161519                         BITSET(killed[bb], b);
 15171520                         unionize(p->n_right, bb);
 15181521                         return;
 15191522                 }
 15201523         }
 15211524         ty = optype(o);
 15221525         if (ty != LTYPE)
 15231526                 unionize(p->n_left, bb);
 15241527         if (ty == BITYPE)
 15251528                 unionize(p->n_right, bb);
 15261529 }
 15271530 
 15281531 /*
 15291532  * Do variable liveness analysis.  Only analyze the long-lived
 15301533  * variables, and save the live-on-exit temporaries in a bit-field
 15311534  * at the end of each basic block. This bit-field is later used
 15321535  * when doing short-range liveness analysis in Build().
 15331536  */
 15341537 static void
 15351538 LivenessAnalysis(struct p2env *p2e)
 15361539 {
 15371540         struct basicblock *bb;
 15381541         struct interpass *ip;
 15391542         int bbnum;
 15401543 
 15411544         /*
 15421545          * generate the gen-killed sets for all basic blocks.
 15431546          */
 15441547         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 15451548                 bbnum = bb->bbnum;
 15461549                 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) {
 15471550                         /* gen/killed is 'p', this node is 'n' */
 15481551                         if (ip->type == IP_NODE) {
 15491552                                 if (ip->ip_node->n_op == XASM)
 15501553                                         flist(ip->ip_node->n_left,
 15511554                                             xasmionize, &bbnum);
 15521555                                 else
 15531556                                         unionize(ip->ip_node, bbnum);
 15541557                         }
 15551558                         if (ip == bb->first)
 15561559                                 break;
 15571560                 }
 15581561                 memcpy(in[bbnum], gen[bbnum], BIT2BYTE(xbits));
 15591562 #ifdef PCC_DEBUG
 15601563 #define PRTRG(x) printf("%d ", x < MAXREGS ? x : x + tempmin-MAXREGS)
 15611564                 if (r2debug) {
 15621565                         int i;
 15631566 
 15641567                         printf("basic block %d\ngen: ", bbnum);
 15651568                         for (i = 0; i < xbits; i++)
 15661569                                 if (TESTBIT(gen[bbnum], i))
 15671570                                         PRTRG(i);
 15681571                         printf("\nkilled: ");
 15691572                         for (i = 0; i < xbits; i++)
 15701573                                 if (TESTBIT(killed[bbnum], i))
 15711574                                         PRTRG(i);
 15721575                         printf("\n");
 15731576                 }
 15741577 #endif
 15751578         }
 15761579 }
 15771580 
 15781581 
 15791582 /*
 15801583  * Build the set of interference edges and adjacency list.
 15811584  */
 15821585 static void
 15831586 Build(struct p2env *p2e)
 15841587 {
 15851588         struct interpass *ipole = &p2e->ipole;
 15861589         struct basicblock bbfake;
 15871590         struct interpass *ip;
 15881591         struct basicblock *bb;
 15891592         bittype *saved;
 15901593         int i, j, again;
 15911594 
 15921595         if (xtemps == 0) {
 15931596                 /*
 15941597                  * No basic block splitup is done if not optimizing,
 15951598                  * so fake one basic block to keep the liveness analysis
 15961599                  * happy.
 15971600                  */
 15981601                 p2e->nbblocks = 1;
 15991602                 bbfake.bbnum = 0;
 16001603                 bbfake.last = DLIST_PREV(ipole, qelem);
 16011604                 bbfake.first = DLIST_NEXT(ipole, qelem);
 16021605                 DLIST_INIT(&p2e->bblocks, bbelem);
 16031606                 DLIST_INSERT_AFTER(&p2e->bblocks, &bbfake, bbelem);
 16041607                 SLIST_INIT(&bbfake.child);
 16051608         }
 16061609 
 16071610         /* Just fetch space for the temporaries from stack */
 16081611         gen = tmpalloc(p2e->nbblocks*sizeof(bittype*));
 16091612         killed = tmpalloc(p2e->nbblocks*sizeof(bittype*));
 16101613         in = tmpalloc(p2e->nbblocks*sizeof(bittype*));
 16111614         out = tmpalloc(p2e->nbblocks*sizeof(bittype*));
 16121615         for (i = 0; i < p2e->nbblocks; i++) {
 16131616                 BITALLOC(gen[i],tmpalloc,xbits);
 16141617                 BITALLOC(killed[i],tmpalloc,xbits);
 16151618                 BITALLOC(in[i],tmpalloc,xbits);
 16161619                 BITALLOC(out[i],tmpalloc,xbits);
 16171620         }
 16181621         BITALLOC(saved,tmpalloc,xbits);
 16191622 
 16201623         SLIST_INIT(&nothead);
 16211624 livagain:
 16221625         LivenessAnalysis(p2e);
 16231626 
 16241627         /* register variable temporaries are live */
 16251628         for (i = 0; i < NPERMREG-1; i++) {
 16261629                 if (nsavregs[i])
 16271630                         continue;
 16281631                 BITSET(out[p2e->nbblocks-1], (i+MAXREGS));
 16291632                 for (j = i+1; j < NPERMREG-1; j++) {
 16301633                         if (nsavregs[j])
 16311634                                 continue;
 16321635                         AddEdge(&nblock[i+tempmin], &nblock[j+tempmin]);
 16331636                 }
 16341637         }
 16351638 
 16361639         /* do liveness analysis on basic block level */
 16371640         do {
 16381641                 struct cfgnode *cn;
 16391642                 again = 0;
 16401643                 /* XXX - loop should be in reversed execution-order */
 16411644                 DLIST_FOREACH_REVERSE(bb, &p2e->bblocks, bbelem) {
 16421645                         i = bb->bbnum;
 16431646                         SETCOPY(saved, out[i], j, xbits);
 16441647                         SLIST_FOREACH(cn, &bb->child, chld) {
 16451648                                 SETSET(out[i], in[cn->bblock->bbnum], j, xbits);
 16461649                         }
 16471650                         SETCMP(again, saved, out[i], j, xbits);
 16481651                         SETCOPY(saved, in[i], j, xbits);
 16491652                         SETCOPY(in[i], out[i], j, xbits);
 16501653                         SETCLEAR(in[i], killed[i], j, xbits);
 16511654                         SETSET(in[i], gen[i], j, xbits);
 16521655                         SETCMP(again, saved, in[i], j, xbits);
 16531656                 }
 16541657         } while (again);
 16551658 
 16561659 #ifdef PCC_DEBUG
 16571660         if (r2debug) {
 16581661                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 16591662                         printf("basic block %d\nin: ", bb->bbnum);
 16601663                         for (i = 0; i < xbits; i++)
 16611664                                 if (TESTBIT(in[bb->bbnum], i))
 16621665                                         PRTRG(i);
 16631666                         printf("\nout: ");
 16641667                         for (i = 0; i < xbits; i++)
 16651668                                 if (TESTBIT(out[bb->bbnum], i))
 16661669                                         PRTRG(i);
 16671670                         printf("\n");
 16681671                 }
 16691672         }
 16701673 #endif
 16711674         if (xtemps && xdce) {
 16721675                 /*
 16731676                  * Do dead code elimination by using live out.
 16741677                  * Ignores if any variable read from is marked volatile,
 16751678                  * but what it should do is unspecified anyway.
 16761679                  * Liveness Analysis should be done in optim2 instead.
 16771680                  *
 16781681                  * This should recalculate the basic block structure.
 16791682                  */
 16801683                 if (dce(p2e)) {
 16811684                         /* Clear bitfields */
 16821685                         for (i = 0; i < p2e->nbblocks; i++) {
 16831686                                 SETEMPTY(gen[i],xbits);
 16841687                                 SETEMPTY(killed[i],xbits);
 16851688                                 SETEMPTY(in[i],xbits);
 16861689                                 SETEMPTY(out[i],xbits);
 16871690                         }
 16881691                         SETEMPTY(saved,xbits);
 16891692                         goto livagain;
 16901693                 }
 16911694         }
 16921695 
 16931696         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 16941697                 RDEBUG(("liveadd bb %d\n", bb->bbnum));
 16951698                 i = bb->bbnum;
 16961699                 for (j = 0; j < xbits; j += NUMBITS)
 16971700                         live[j/NUMBITS] = 0;
 16981701                 SETCOPY(live, out[i], j, xbits);
 16991702                 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) {
 17001703                         if (ip->type == IP_NODE) {
 17011704                                 if (ip->ip_node->n_op == XASM) {
 17021705                                         flist(ip->ip_node->n_right,
 17031706                                             xasmconstr, 0);
 17041707                                         listf(ip->ip_node->n_left, setxarg);
 17051708                                         listf(ip->ip_node->n_left, delcl);
 17061709                                 } else
 17071710                                         insnwalk(ip->ip_node);
 17081711                         }
 17091712                         if (ip == bb->first)
 17101713                                 break;
 17111714                 }
 17121715         }
 17131716 
 17141717 #ifdef PCC_DEBUG
 17151718         if (r2debug) {
 17161719                 struct AdjSet *w;
 17171720                 ADJL *x;
 17181721                 REGW *y;
 17191722                 MOVL *m;
 17201723 
 17211724                 printf("Interference edges\n");
 17221725                 for (i = 0; i < HASHSZ; i++) {
 17231726                         if ((w = edgehash[i]) == NULL)
 17241727                                 continue;
 17251728                         for (; w; w = w->next)
 17261729                                 printf("%d <-> %d\n", ASGNUM(w->u), ASGNUM(w->v));
 17271730                 }
 17281731                 printf("Degrees\n");
 17291732                 DLIST_FOREACH(y, &initial, link) {
 17301733                         printf("%d (%c): trivial [%d] ", ASGNUM(y),
 17311734                             CLASS(y)+'@', trivially_colorable(y));
 17321735                         i = 0;
 17331736                         for (x = ADJLIST(y); x; x = x->r_next) {
 17341737                                 if (ONLIST(x->a_temp) != &selectStack &&
 17351738                                     ONLIST(x->a_temp) != &coalescedNodes)
 17361739                                         printf("%d ", ASGNUM(x->a_temp));
 17371740                                 else
 17381741                                         printf("(%d) ", ASGNUM(x->a_temp));
 17391742                                 i++;
 17401743                         }
 17411744                         printf(": n=%d\n", i);
 17421745                 }
 17431746                 printf("Move nodes\n");
 17441747                 DLIST_FOREACH(y, &initial, link) {
 17451748                         if (MOVELIST(y) == NULL)
 17461749                                 continue;
 17471750                         printf("%d: ", ASGNUM(y));
 17481751                         for (m = MOVELIST(y); m; m = m->next) {
 17491752                                 REGW *yy = m->regm->src == y ?
 17501753                                     m->regm->dst : m->regm->src;
 17511754                                 printf("%d ", ASGNUM(yy));
 17521755                         }
 17531756                         printf("\n");
 17541757                 }
 17551758         }
 17561759 #endif
 17571760 
 17581761 }
 17591762 
 17601763 static void
 17611764 EnableMoves(REGW *n)
 17621765 {
 17631766         MOVL *l;
 17641767         REGM *m;
 17651768 
 17661769         for (l = MOVELIST(n); l; l = l->next) {
 17671770                 m = l->regm;
 17681771                 if (m->queue != ACTIVE)
 17691772                         continue;
 17701773                 DLIST_REMOVE(m, link);
 17711774                 PUSHMLIST(m, worklistMoves, WLIST);
 17721775         }
 17731776 }
 17741777 
 17751778 static void
 17761779 EnableAdjMoves(REGW *nodes)
 17771780 {
 17781781         ADJL *w;
 17791782         REGW *n;
 17801783 
 17811784         EnableMoves(nodes);
 17821785         for (w = ADJLIST(nodes); w; w = w->r_next) {
 17831786                 n = w->a_temp;
 17841787                 if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes)
 17851788                         continue;
 17861789                 EnableMoves(w->a_temp);
 17871790         }
 17881791 }
 17891792 
 17901793 /*
 17911794  * Decrement the degree of node w for class c.
 17921795  */
 17931796 static void
 17941797 DecrementDegree(REGW *w, int c)
 17951798 {
 17961799         int wast;
 17971800 
 17981801 #ifdef PCC_DEBUG
 17991802         RRDEBUG(("DecrementDegree: w %d, c %d\n", ASGNUM(w), c));
 18001803 #endif
 18011804 
 18021805         wast = trivially_colorable(w);
 18031806         if (NCLASS(w, c) > 0)
 18041807                 NCLASS(w, c)--;
 18051808         if (wast == trivially_colorable(w))
 18061809                 return;
 18071810 
 18081811         EnableAdjMoves(w);
 18091812         DELWLIST(w);
 18101813         ONLIST(w) = 0;
 18111814         if (MoveRelated(w)) {
 18121815                 PUSHWLIST(w, freezeWorklist);
 18131816         } else {
 18141817                 PUSHWLIST(w, simplifyWorklist);
 18151818         }
 18161819 }
 18171820 
 18181821 static void
 18191822 Simplify(void)
 18201823 {
 18211824         REGW *w;
 18221825         ADJL *l;
 18231826 
 18241827         w = POPWLIST(simplifyWorklist);
 18251828         PUSHWLIST(w, selectStack);
 18261829 #ifdef PCC_DEBUG
 18271830         RDEBUG(("Simplify: node %d class %d\n", ASGNUM(w), w->r_class));
 18281831 #endif
 18291832 
 18301833         l = w->r_adjList;
 18311834         for (; l; l = l->r_next) {
 18321835                 if (ONLIST(l->a_temp) == &selectStack ||
 18331836                     ONLIST(l->a_temp) == &coalescedNodes)
 18341837                         continue;
 18351838                 DecrementDegree(l->a_temp, w->r_class);
 18361839         }
 18371840 }
 18381841 
 18391842 static REGW *
 18401843 GetAlias(REGW *n)
 18411844 {
 18421845         if (ONLIST(n) == &coalescedNodes)
 18431846                 return GetAlias(ALIAS(n));
 18441847         return n;
 18451848 }
 18461849 
 18471850 static int
 18481851 OK(REGW *t, REGW *r)
 18491852 {
 18501853 #ifdef PCC_DEBUG
 18511854         RDEBUG(("OK: t %d CLASS(t) %d adjSet(%d,%d)=%d\n",
 18521855             ASGNUM(t), CLASS(t), ASGNUM(t), ASGNUM(r), adjSet(t, r)));
 18531856 
 18541857         if (r2debug > 1) {
 18551858                 ADJL *w;
 18561859                 int ndeg = 0;
 18571860                 printf("OK degree: ");
 18581861                 for (w = ADJLIST(t); w; w = w->r_next) {
 18591862                         if (ONLIST(w->a_temp) != &selectStack &&
 18601863                             ONLIST(w->a_temp) != &coalescedNodes)
 18611864                                 printf("%c%d ", CLASS(w->a_temp)+'@',
 18621865                                     ASGNUM(w->a_temp)), ndeg++;
 18631866                         else
 18641867                                 printf("(%d) ", ASGNUM(w->a_temp));
 18651868                 }
 18661869                 printf("\n");
 18671870 #if 0
 18681871                 if (ndeg != DEGREE(t) && DEGREE(t) >= 0)
 18691872                         printf("!!!ndeg %d != DEGREE(t) %d\n", ndeg, DEGREE(t));
 18701873 #endif
 18711874         }
 18721875 #endif
 18731876 
 18741877         if (trivially_colorable(t) || ONLIST(t) == &precolored ||
 18751878             (adjSet(t, r) || !aliasmap(CLASS(t), COLOR(r))))/* XXX - check aliasmap */
 18761879                 return 1;
 18771880         return 0;
 18781881 }
 18791882 
 18801883 static int
 18811884 adjok(REGW *v, REGW *u)
 18821885 {
 18831886         ADJL *w;
 18841887         REGW *t;
 18851888 
 18861889         RDEBUG(("adjok\n"));
 18871890         for (w = ADJLIST(v); w; w = w->r_next) {
 18881891                 t = w->a_temp;
 18891892                 if (ONLIST(t) == &selectStack || ONLIST(t) == &coalescedNodes)
 18901893                         continue;
 18911894                 if (OK(t, u) == 0)
 18921895                         return 0;
 18931896         }
 18941897         RDEBUG(("adjok returns OK\n"));
 18951898         return 1;
 18961899 }
 18971900 
 18981901 /*
 18991902  * Do a conservative estimation of whether two temporaries can
 19001903  * be coalesced.  This is "Briggs-style" check.
 19011904  * Neither u nor v is precolored when called.
 19021905  */
 19031906 static int
 19041907 Conservative(REGW *u, REGW *v)
 19051908 {
 19061909         ADJL *w, *ww;
 19071910         REGW *n;
 19081911         int xncl[NUMCLASS+1], mcl = 0, j;
 19091912 
 19101913         for (j = 0; j < NUMCLASS+1; j++)
 19111914                 xncl[j] = 0;
 19121915         /*
 19131916          * Increment xncl[class] up to K for each class.
 19141917          * If all classes has reached K then check colorability and return.
 19151918          */
 19161919         for (w = ADJLIST(u); w; w = w->r_next) {
 19171920                 n = w->a_temp;
 19181921                 if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes)
 19191922                         continue;
 19201923                 if (xncl[CLASS(n)] == regK[CLASS(n)])
 19211924                         continue;
 19221925                 if (!trivially_colorable(n) || ONLIST(n) == &precolored)
 19231926                         xncl[CLASS(n)]++;
 19241927                 if (xncl[CLASS(n)] < regK[CLASS(n)])
 19251928                         continue;
 19261929                 if (++mcl == NUMCLASS)
 19271930                         goto out; /* cannot get more out of it */
 19281931         }
 19291932         for (w = ADJLIST(v); w; w = w->r_next) {
 19301933                 n = w->a_temp;
 19311934                 if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes)
 19321935                         continue;
 19331936                 if (xncl[CLASS(n)] == regK[CLASS(n)])
 19341937                         continue;
 19351938                 /* ugly: have we been here already? */
 19361939                 for (ww = ADJLIST(u); ww; ww = ww->r_next)
 19371940                         if (ww->a_temp == n)
 19381941                                 break;
 19391942                 if (ww)
 19401943                         continue;
 19411944                 if (!trivially_colorable(n) || ONLIST(n) == &precolored)
 19421945                         xncl[CLASS(n)]++;
 19431946                 if (xncl[CLASS(n)] < regK[CLASS(n)])
 19441947                         continue;
 19451948                 if (++mcl == NUMCLASS)
 19461949                         break;
 19471950         }
 19481951 out:    j = trivially_colorable_p(CLASS(u), xncl);
 19491952         return j;
 19501953 }
 19511954 
 19521955 static void
 19531956 AddWorkList(REGW *w)
 19541957 {
 19551958 
 19561959         if (ONLIST(w) != &precolored && !MoveRelated(w) &&
 19571960             trivially_colorable(w)) {
 19581961                 DELWLIST(w);
 19591962                 PUSHWLIST(w, simplifyWorklist);
 19601963         }
 19611964 }
 19621965 
 19631966 static void
 19641967 Combine(REGW *u, REGW *v)
 19651968 {
 19661969         MOVL *m;
 19671970         ADJL *l;
 19681971         REGW *t;
 19691972 
 19701973 #ifdef PCC_DEBUG
 19711974         RDEBUG(("Combine (%d,%d)\n", ASGNUM(u), ASGNUM(v)));
 19721975 #endif
 19731976 
 19741977         if (ONLIST(v) == &freezeWorklist) {
 19751978                 DELWLIST(v);
 19761979         } else {
 19771980                 DELWLIST(v);
 19781981         }
 19791982         PUSHWLIST(v, coalescedNodes);
 19801983         ALIAS(v) = u;
 19811984 #ifdef PCC_DEBUG
 19821985         if (r2debug) {
 19831986                 printf("adjlist(%d): ", ASGNUM(v));
 19841987                 for (l = ADJLIST(v); l; l = l->r_next)
 19851988                         printf("%d ", l->a_temp->nodnum);
 19861989                 printf("\n");
 19871990         }
 19881991 #endif
 19891992 #if 1
 19901993 {
 19911994         MOVL *m0 = MOVELIST(v);
 19921995 
 19931996         for (m0 = MOVELIST(v); m0; m0 = m0->next) {
 19941997                 for (m = MOVELIST(u); m; m = m->next)
 19951998                         if (m->regm == m0->regm)
 19961999                                 break; /* Already on list */
 19972000                 if (m)
 19982001                         continue; /* already on list */
 19992002                 MOVELISTADD(u, m0->regm);
 20002003         }
 20012004 }
 20022005 #else
 20032006 
 20042007         if ((m = MOVELIST(u))) {
 20052008                 while (m->next)
 20062009                         m = m->next;
 20072010                 m->next = MOVELIST(v);
 20082011         } else
 20092012                 MOVELIST(u) = MOVELIST(v);
 20102013 #endif
 20112014         EnableMoves(v);
 20122015         for (l = ADJLIST(v); l; l = l->r_next) {
 20132016                 t = l->a_temp;
 20142017                 if (ONLIST(t) == &selectStack || ONLIST(t) == &coalescedNodes)
 20152018                         continue;
 20162019                 /* Do not add edge if u cannot affect the colorability of t */
 20172020                 /* XXX - check aliasmap */
 20182021                 if (ONLIST(u) != &precolored || aliasmap(CLASS(t), COLOR(u)))
 20192022                         AddEdge(t, u);
 20202023                 DecrementDegree(t, CLASS(v));
 20212024         }
 20222025         if (!trivially_colorable(u) && ONLIST(u) == &freezeWorklist) {
 20232026                 DELWLIST(u);
 20242027                 PUSHWLIST(u, spillWorklist);
 20252028         }
 20262029 #ifdef PCC_DEBUG
 20272030         if (r2debug) {
 20282031                 ADJL *w;
 20292032                 printf("Combine %d class (%d): ", ASGNUM(u), CLASS(u));
 20302033                 for (w = ADJLIST(u); w; w = w->r_next) {
 20312034                         if (ONLIST(w->a_temp) != &selectStack &&
 20322035                             ONLIST(w->a_temp) != &coalescedNodes)
 20332036                                 printf("%d ", ASGNUM(w->a_temp));
 20342037                         else
 20352038                                 printf("(%d) ", ASGNUM(w->a_temp));
 20362039                 }
 20372040                 printf("\n");
 20382041         }
 20392042 #endif
 20402043 }
 20412044 
 20422045 static void
 20432046 Coalesce(void)
 20442047 {
 20452048         REGM *m;
 20462049         REGW *x, *y, *u, *v;
 20472050 
 20482051         m = POPMLIST(worklistMoves);
 20492052         x = GetAlias(m->src);
 20502053         y = GetAlias(m->dst);
 20512054 
 20522055         if (ONLIST(y) == &precolored)
 20532056                 u = y, v = x;
 20542057         else
 20552058                 u = x, v = y;
 20562059 
 20572060 #ifdef PCC_DEBUG
 20582061         RDEBUG(("Coalesce: src %d dst %d u %d v %d x %d y %d\n",
 20592062             ASGNUM(m->src), ASGNUM(m->dst), ASGNUM(u), ASGNUM(v),
 20602063             ASGNUM(x), ASGNUM(y)));
 20612064 #endif
 20622065 
 20632066         if (CLASS(m->src) != CLASS(m->dst))
 20642067                 comperr("Coalesce: src class %d, dst class %d",
 20652068                     CLASS(m->src), CLASS(m->dst));
 20662069 
 20672070         if (u == v) {
 20682071                 RDEBUG(("Coalesce: u == v\n"));
 20692072                 PUSHMLIST(m, coalescedMoves, COAL);
 20702073                 AddWorkList(u);
 20712074         } else if (ONLIST(v) == &precolored || adjSet(u, v)) {
 20722075                 RDEBUG(("Coalesce: constrainedMoves\n"));
 20732076                 PUSHMLIST(m, constrainedMoves, CONSTR);
 20742077                 AddWorkList(u);
 20752078                 AddWorkList(v);
 20762079         } else if ((ONLIST(u) == &precolored && adjok(v, u)) ||
 20772080             (ONLIST(u) != &precolored && Conservative(u, v))) {
 20782081                 RDEBUG(("Coalesce: Conservative\n"));
 20792082                 PUSHMLIST(m, coalescedMoves, COAL);
 20802083                 Combine(u, v);
 20812084                 AddWorkList(u);
 20822085         } else {
 20832086                 RDEBUG(("Coalesce: activeMoves\n"));
 20842087                 PUSHMLIST(m, activeMoves, ACTIVE);
 20852088         }
 20862089 }
 20872090 
 20882091 static void
 20892092 coalasg(NODE *p, void *arg)
 20902093 {
 20912094         NODE *l;
 20922095         REGW *u;
 20932096 
 20942097         if (p->n_op != ASSIGN || p->n_regw == NULL)
 20952098                 return;
 20962099         l = p->n_left;
 20972100         if (l->n_op == TEMP)
 20982101                 u = &nblock[regno(l)];
 20992102         else if (l->n_op == REG)
 21002103                 u = &ablock[regno(l)];
 21012104         else
 21022105                 return;
 21032106 
 21042107         Combine(u, p->n_regw);
 21052108         AddWorkList(u);
 21062109 }
 21072110 
 21082111 /*
 21092112  * Coalesce assign to a left reg with the assign temp node itself.
 21102113  * This has to be done before anything else.
 21112114  */
 21122115 static void
 21132116 Coalassign(struct p2env *p2e)
 21142117 {
 21152118         struct interpass *ip;
 21162119 
 21172120         DLIST_FOREACH(ip, &p2env.ipole, qelem) {
 21182121                 if (ip->type == IP_NODE)
 21192122                         walkf(ip->ip_node, coalasg, 0);
 21202123         }
 21212124 }
 21222125 
 21232126 static void
 21242127 FreezeMoves(REGW *u)
 21252128 {
 21262129         MOVL *w, *o;
 21272130         REGM *m;
 21282131         REGW *z;
 21292132         REGW *x, *y, *v;
 21302133 
 21312134         for (w = MOVELIST(u); w; w = w->next) {
 21322135                 m = w->regm;
 21332136                 if (m->queue != WLIST && m->queue != ACTIVE)
 21342137                         continue;
 21352138                 x = m->src;
 21362139                 y = m->dst;
 21372140                 if (GetAlias(y) == GetAlias(u))
 21382141                         v = GetAlias(x);
 21392142                 else
 21402143                         v = GetAlias(y);
 21412144 #ifdef PCC_DEBUG
 21422145                 RDEBUG(("FreezeMoves: u %d (%d,%d) v %d\n",
 21432146                     ASGNUM(u),ASGNUM(x),ASGNUM(y),ASGNUM(v)));
 21442147 #endif
 21452148                 DLIST_REMOVE(m, link);
 21462149                 PUSHMLIST(m, frozenMoves, FROZEN);
 21472150                 if (ONLIST(v) != &freezeWorklist)
 21482151                         continue;
 21492152                 for (o = MOVELIST(v); o; o = o->next)
 21502153                         if (o->regm->queue == WLIST || o->regm->queue == ACTIVE)
 21512154                                 break;
 21522155                 if (o == NULL) {
 21532156                         z = v;
 21542157                         DELWLIST(z);
 21552158                         PUSHWLIST(z, simplifyWorklist);
 21562159                 }
 21572160         }
 21582161 }
 21592162 
 21602163 static void
 21612164 Freeze(void)
 21622165 {
 21632166         REGW *u;
 21642167 
 21652168         /*
 21662169          * To find out:
 21672170          * Check if the moves to freeze have exactly the same
 21682171          * interference edges.  If they do, coalesce them instead, it
 21692172          * may free up other nodes that they interfere with.
 21702173          */
 21712174 
 21722175         /*
 21732176          * Select nodes to freeze first by using following criteria:
 21742177          * - Trivially colorable
 21752178          * - Single or few moves to less trivial nodes.
 21762179          */
 21772180         DLIST_FOREACH(u, &freezeWorklist, link) {
 21782181                 if (u >= &nblock[tempmax] || u < &nblock[tempmin])
 21792182                         continue; /* No short range temps */
 21802183                 if (!trivially_colorable(u))
 21812184                         continue; /* Prefer colorable nodes */
 21822185                 /* Check for at most two move-related nodes */
 21832186                 if (u->r_moveList->next && u->r_moveList->next->next)
 21842187                         continue;
 21852188                 /* Ok, remove node */
 21862189                 DLIST_REMOVE(u, link);
 21872190                 u->r_onlist = 0;
 21882191                 break;
 21892192         }
 21902193         if (u == &freezeWorklist) /* Nothing matched criteria, just take one */
 21912194                 u = POPWLIST(freezeWorklist);
 21922195         PUSHWLIST(u, simplifyWorklist);
 21932196 #ifdef PCC_DEBUG
 21942197         RDEBUG(("Freeze %d\n", ASGNUM(u)));
 21952198 #endif
 21962199         FreezeMoves(u);
 21972200 }
 21982201 
 21992202 static void
 22002203 SelectSpill(void)
 22012204 {
 22022205         REGW *w;
 22032206 
 22042207         RDEBUG(("SelectSpill\n"));
 22052208 #ifdef PCC_DEBUG
 22062209         if (r2debug)
 22072210                 DLIST_FOREACH(w, &spillWorklist, link)
 22082211                         printf("SelectSpill: %d\n", ASGNUM(w));
 22092212 #endif
 22102213 
 22112214         /* First check if we can spill register variables */
 22122215         DLIST_FOREACH(w, &spillWorklist, link) {
 22132216                 if (w >= &nblock[tempmin] && w < &nblock[basetemp])
 22142217                         break;
 22152218         }
 22162219 
 22172220         RRDEBUG(("SelectSpill: trying longrange\n"));
 22182221         if (w == &spillWorklist) {
 22192222                 /* try to find another long-range variable */
 22202223                 DLIST_FOREACH(w, &spillWorklist, link) {
 22212224                         if (innotspill(w - nblock))
 22222225                                 continue;
 22232226                         if (w >= &nblock[tempmin] && w < &nblock[tempmax])
 22242227                                 break;
 22252228                 }
 22262229         }
 22272230 
 22282231         if (w == &spillWorklist) {
 22292232                 RRDEBUG(("SelectSpill: trying not leaf\n"));
 22302233                 /* no heuristics, just fetch first element */
 22312234                 /* but not if leaf */
 22322235                 DLIST_FOREACH(w, &spillWorklist, link) {
 22332236                         if (w->r_nclass[0] == 0)
 22342237                                 break;
 22352238                 }
 22362239         }
 22372240 
 22382241         if (w == &spillWorklist) {
 22392242                 /* Eh, only leaves :-/ Try anyway */
 22402243                 /* May not be useable */
 22412244                 w = DLIST_NEXT(&spillWorklist, link);
 22422245                 RRDEBUG(("SelectSpill: need leaf\n"));
 22432246         }
 22442247  
 22452248         DLIST_REMOVE(w, link);
 22462249 
 22472250         PUSHWLIST(w, simplifyWorklist);
 22482251 #ifdef PCC_DEBUG
 22492252         RDEBUG(("Freezing node %d\n", ASGNUM(w)));
 22502253 #endif
 22512254         FreezeMoves(w);
 22522255 }
 22532256 
 22542257 /*
 22552258  * Set class on long-lived temporaries based on its type.
 22562259  */
 22572260 static void
 22582261 traclass(NODE *p, void *arg)
 22592262 {
 22602263         REGW *nb;
 22612264 
 22622265         if (p->n_op != TEMP)
 22632266                 return;
 22642267 
 22652268         nb = &nblock[regno(p)];
 22662269         if (CLASS(nb) == 0)
 22672270                 CLASS(nb) = gclass(p->n_type);
 22682271 }
 22692272 
 22702273 static void
 22712274 paint(NODE *p, void *arg)
 22722275 {
 22732276         struct optab *q;
 22742277         REGW *w, *ww;
 22752278         int i;
 22762279 
 22772280 #ifdef notyet
 22782281         /* XXX - trashes rewrite of trees (short) */
 22792282         if (!DLIST_ISEMPTY(&spilledNodes, link)) {
 22802283                 p->n_reg = 0;
 22812284                 return;
 22822285         }
 22832286 #endif
 22842287         if (p->n_regw != NULL) {
 22852288                 /* Must color all allocated regs also */
 22862289                 ww = w = p->n_regw;
 22872290                 q = &table[TBLIDX(p->n_su)];
 22882291                 p->n_reg = COLOR(w);
 22892292                 w++;
 22902293                 if (q->needs & ALLNEEDS)
 22912294                         for (i = 0; i < ncnt(q->needs); i++) {
 22922295                                 if (w->r_class == -1)
 22932296                                         p->n_reg |= ENCRA(COLOR(ww), i);
 22942297                                 else
 22952298                                         p->n_reg |= ENCRA(COLOR(w), i);
 22962299                                 w++;
 22972300                         }
 22982301 #ifdef notdef
 22992302                 if (p->n_op == ASSIGN && p->n_left->n_op == REG &&
 23002303                     DECRA(p->n_reg, 0) != regno(p->n_left))
 23012304                         comperr("paint: %p clashing ASSIGN moves; %d != %d", p,
 23022305                             DECRA(p->n_reg, 0), regno(p->n_left));
 23032306 #endif
 23042307         } else
 23052308                 p->n_reg = -1;
 23062309         if (p->n_op == TEMP) {
 23072310                 REGW *nb = &nblock[regno(p)];
 23082311                 regno(p) = COLOR(nb);
 23092312                 if (TCLASS(p->n_su) == 0)
 23102313                         SCLASS(p->n_su, CLASS(nb));
 23112314                 p->n_op = REG;
 23122315                 p->n_lval = 0;
 23132316         }
 23142317 }
 23152318 
 23162319 /*
 23172320  * See if this node have a move that has been removed in Freeze
 23182321  * but as we can make use of anyway.
 23192322  */
 23202323 static int
 23212324 colfind(int okColors, REGW *r)
 23222325 {
 23232326         REGW *w;
 23242327         MOVL *m;
 23252328         int c;
 23262329 
 23272330         for (m = MOVELIST(r); m; m = m->next) {
 23282331                 if ((w = m->regm->src) == r)
 23292332                         w = m->regm->dst;
 23302333                 w = GetAlias(w);
 23312334                 if (ONLIST(w) != &coloredNodes && ONLIST(w) != &precolored)
 23322335                         continue; /* Not yet colored */
 23332336                 if (CLASS(w) != CLASS(r))
 23342337                         comperr("colfind: move between classes");
 23352338 
 23362339                 for (c = 0; c < regK[CLASS(w)]; c++)
 23372340                         if (color2reg(c, CLASS(w)) == COLOR(w))
 23382341                                 break;
 23392342                 if (c == regK[CLASS(w)])
 23402343                         comperr("colfind: out of reg number");
 23412344 
 23422345                 if (((1 << c) & okColors) == 0) {
 23432346                         RDEBUG(("colfind: Failed coloring as %d\n", ASGNUM(w)));
 23442347                         continue;
 23452348                 }
 23462349                 RDEBUG(("colfind: Recommend color from %d\n", ASGNUM(w)));
 23472350                 return COLOR(w);
 23482351         }
 23492352         return color2reg(ffs(okColors)-1, CLASS(r));
 23502353 }
 23512354 
 23522355 static void
 23532356 AssignColors(struct interpass *ip)
 23542357 {
 23552358         struct interpass *ip2;
 23562359         int okColors, c;
 23572360         REGW *o, *w;
 23582361         ADJL *x;
 23592362 
 23602363         RDEBUG(("AssignColors\n"));
 23612364         while (!WLISTEMPTY(selectStack)) {
 23622365                 w = POPWLIST(selectStack);
 23632366                 okColors = classmask(CLASS(w));
 23642367 #ifdef PCC_DEBUG
 23652368                 RDEBUG(("classmask av %d, class %d: %x\n",
 23662369                     w->nodnum, CLASS(w), okColors));
 23672370 #endif
 23682371 
 23692372                 for (x = ADJLIST(w); x; x = x->r_next) {
 23702373                         o = GetAlias(x->a_temp);
 23712374 #ifdef PCC_DEBUG
 23722375                         RRDEBUG(("Adj(%d): %d (%d)\n",
 23732376                             ASGNUM(w), ASGNUM(o), ASGNUM(x->a_temp)));
 23742377 #endif
 23752378 
 23762379                         if (ONLIST(o) == &coloredNodes ||
 23772380                             ONLIST(o) == &precolored) {
 23782381                                 c = aliasmap(CLASS(w), COLOR(o));
 23792382                                 RRDEBUG(("aliasmap in class %d by color %d: "
 23802383                                     "%x, okColors %x\n",
 23812384                                     CLASS(w), COLOR(o), c, okColors));
 23822385 
 23832386                                 okColors &= ~c;
 23842387                         }
 23852388                 }
 23862389                 if (okColors == 0) {
 23872390                         PUSHWLIST(w, spilledNodes);
 23882391 #ifdef PCC_DEBUG
 23892392                         RDEBUG(("Spilling node %d\n", ASGNUM(w)));
 23902393 #endif
 23912394                 } else {
 23922395                         COLOR(w) = colfind(okColors, w);
 23932396                         PUSHWLIST(w, coloredNodes);
 23942397 #ifdef PCC_DEBUG
 23952398                         RDEBUG(("Coloring %d with %s, free %x\n",
 23962399                             ASGNUM(w), rnames[COLOR(w)], okColors));
 23972400 #endif
 23982401                 }
 23992402         }
 24002403         DLIST_FOREACH(w, &coalescedNodes, link) {
 24012404                 REGW *ww = GetAlias(w);
 24022405                 COLOR(w) = COLOR(ww);
 24032406                 if (ONLIST(ww) == &spilledNodes) {
 24042407 #ifdef PCC_DEBUG
 24052408                         RDEBUG(("coalesced node %d spilled\n", w->nodnum));
 24062409 #endif
 24072410                         ww = DLIST_PREV(w, link);
 24082411                         DLIST_REMOVE(w, link);
 24092412                         PUSHWLIST(w, spilledNodes);
 24102413                         w = ww;
 24112414                 } else {
 24122415 #ifdef PCC_DEBUG
 24132416                         RDEBUG(("Giving coalesced node %d color %s\n",
 24142417                             w->nodnum, rnames[COLOR(w)]));
 24152418 #endif
 24162419                 }
 24172420         }
 24182421 
 24192422 #ifdef PCC_DEBUG
 24202423         if (r2debug)
 24212424                 DLIST_FOREACH(w, &coloredNodes, link)
 24222425                         printf("%d: color %s\n", ASGNUM(w), rnames[COLOR(w)]);
 24232426 #endif
 24242427         if (DLIST_ISEMPTY(&spilledNodes, link)) {
 24252428                 DLIST_FOREACH(ip2, ip, qelem)
 24262429                         if (ip2->type == IP_NODE)
 24272430                                 walkf(ip2->ip_node, paint, 0);
 24282431         }
 24292432 }
 24302433 
 24312434 static REGW *spole;
 24322435 /*
 24332436  * Store all spilled nodes in memory by fetching a temporary on the stack.
 24342437  * Will never end up here if not optimizing.
 24352438  */
 24362439 static void
 24372440 longtemp(NODE *p, void *arg)
 24382441 {
 24392442         REGW *w;
 24402443 
 24412444         if (p->n_op != TEMP)
 24422445                 return;
 24432446         /* XXX - should have a bitmask to find temps to convert */
 24442447         DLIST_FOREACH(w, spole, link) {
 24452448                 if (w != &nblock[regno(p)])
 24462449                         continue;
 24472450                 if (w->r_class == 0) {
 24482451                         w->r_color = freetemp(szty(p->n_type));
 24492452                         w->r_class = FPREG; /* just something */
 24502453                 }
 24512454                 storemod(p, w->r_color);
 24522455                 break;
 24532456         }
 24542457 }
 24552458 
<> 2459+/*
  2460+ * Check if this node is just something directly addressable.
  2461+ * XXX - should use target canaddr() when we knows that it is OK
  2462+ * for all targets. Can currently be a little too optimistic.
  2463+ */
  2464+static int
  2465+regcanaddr(NODE *p)
  2466+{
  2467+        int o = p->n_op;
  2468+
  2469+        if (o==NAME || o==ICON || o==OREG )
  2470+                return 1;
  2471+        if (o == UMUL) {
  2472+                if (p->n_left->n_op == REG)
  2473+                        return 1;
  2474+                if ((p->n_left->n_op == PLUS || p->n_left->n_op == MINUS) &&
  2475+                    p->n_left->n_left->n_op == REG &&
  2476+                    p->n_left->n_right->n_op == ICON)
  2477+                        return 1;
  2478+        }
  2479+        return 0;
  2480+}
  2481+
24562482 static struct interpass *cip;
 24572483 /*
 24582484  * Rewrite a tree by storing a variable in memory.
 24592485  * XXX - must check if basic block structure is destroyed!
 24602486  */
 24612487 static void
 24622488 shorttemp(NODE *p, void *arg)
 24632489 {
 24642490         struct interpass *nip;
 24652491         struct optab *q;
 24662492         REGW *w;
 24672493         NODE *l, *r;
 24682494         int off;
 24692495 
 24702496         /* XXX - optimize this somewhat */
 24712497         DLIST_FOREACH(w, spole, link) {
 24722498                 if (w != p->n_regw)
 24732499                         continue;
<>2474 -                /* XXX - use canaddr() */
 2475 -                if (p->n_op == OREG || p->n_op == NAME) {
  2500+                if (regcanaddr(p)) {
24762501                         DLIST_REMOVE(w, link);
 24772502 #ifdef PCC_DEBUG
 24782503                         RDEBUG(("Node %d already in memory\n", ASGNUM(w)));
 24792504 #endif
 24802505                         break;
 24812506                 }
 24822507 #ifdef PCC_DEBUG
 24832508                 RDEBUG(("rewriting node %d\n", ASGNUM(w)));
 24842509 #endif
 24852510 
 24862511                 off = freetemp(szty(p->n_type));
 24872512                 l = storenode(p->n_type, off);
 24882513                 /*
 24892514                  * If this is a binode which reclaim a leg, and it had
 24902515                  * to walk down the other leg first, then it must be
 24912516                  * split below this node instead.
<> 2517+                 * Be careful not to store a node that do not involve
  2518+                 * any evaluation (meaningless).
24922519                  */
 24932520                 q = &table[TBLIDX(p->n_su)];
 24942521                 if (optype(p->n_op) == BITYPE &&
<>2495 -                    (q->rewrite & RLEFT && (p->n_su & DORIGHT) == 0)) {
  2522+                    (q->rewrite & RLEFT && (p->n_su & DORIGHT) == 0) &&
  2523+                    regcanaddr(p->n_left) == 0) {
24962524                         nip = ipnode(mkbinode(ASSIGN, storenode(p->n_type, off),
 24972525                             p->n_left, p->n_type));
 24982526                         p->n_left = l;
 24992527                 } else if (optype(p->n_op) == BITYPE &&
<>2500 -                    (q->rewrite & RRIGHT && (p->n_su & DORIGHT) != 0)) {
  2528+                    (q->rewrite & RRIGHT && (p->n_su & DORIGHT) != 0) &&
  2529+                    regcanaddr(p->n_right) == 0) {
<_25012530                         nip = ipnode(mkbinode(ASSIGN, storenode(p->n_type, off),
 25022531                             p->n_right, p->n_type));
 25032532                         p->n_right = l;
 25042533                 } else {
 25052534                         r = talloc();
 25062535                         *r = *p;
 25072536                         nip = ipnode(mkbinode(ASSIGN, l, r, p->n_type));
 25082537                         storemod(p, off);
 25092538                 }
 25102539                 DLIST_INSERT_BEFORE(cip, nip, qelem);
 25112540                 DLIST_REMOVE(w, link);
 25122541                 break;
 25132542         }
 25142543 }
 25152544 
 25162545 /*
 25172546  * Change the TEMPs in the ipole list to stack variables.
 25182547  */
 25192548 static void
 25202549 treerewrite(struct interpass *ipole, REGW *rpole)
 25212550 {
 25222551         struct interpass *ip;
 25232552 
 25242553         spole = rpole;
 25252554 
 25262555         DLIST_FOREACH(ip, ipole, qelem) {
 25272556                 if (ip->type != IP_NODE)
 25282557                         continue;
 25292558                 cip = ip;
 25302559                 walkf(ip->ip_node, shorttemp, 0); /* convert temps to oregs */
 25312560         }
 25322561         if (!DLIST_ISEMPTY(spole, link))
 25332562                 comperr("treerewrite not empty");
 25342563 }
 25352564 
 25362565 /*
 25372566  * Change the TEMPs in the ipole list to stack variables.
 25382567  */
 25392568 static void
 25402569 leafrewrite(struct interpass *ipole, REGW *rpole)
 25412570 {
 25422571         extern NODE *nodepole;
 25432572         extern int thisline;
 25442573         struct interpass *ip;
 25452574 
 25462575         spole = rpole;
 25472576         DLIST_FOREACH(ip, ipole, qelem) {
 25482577                 if (ip->type != IP_NODE)
 25492578                         continue;
 25502579                 nodepole = ip->ip_node;
 25512580                 thisline = ip->lineno;
 25522581                 walkf(ip->ip_node, longtemp, 0); /* convert temps to oregs */
 25532582         }
 25542583         nodepole = NIL;
 25552584 }
 25562585 
 25572586 /*
 25582587  * Avoid copying spilled argument to new position on stack.
 25592588  */
 25602589 static int
 25612590 temparg(struct interpass *ipole, REGW *w)
 25622591 {
 25632592         struct interpass *ip;
 25642593         NODE *p;
 25652594         int reg;
 25662595 
 25672596         ip = DLIST_NEXT(ipole, qelem); /* PROLOG */
 25682597   &nbs