source: mainline/uspace/app/pcc/mip/regs.c@ a7de7182

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since a7de7182 was a7de7182, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 14 years ago

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