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