Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20140601113352

Diff

Diff from 1.237 to:

Annotations

Annotate by Age | Author | Mixed | None
/fisheye/browse/pcc/pcc/mip/regs.c

Annotated File View

ragge
1.237
1 /*      $Id: regs.c,v 1.237 2014/06/01 11:33:52 ragge Exp $     */
ragge
1.1
2 /*
ragge
1.49
3  * Copyright (c) 2005 Anders Magnusson (ragge@ludd.luth.se).
ragge
1.1
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"
ragge
1.146
30 #include <string.h>
gmcgarry
1.171
31 #ifdef HAVE_STRINGS_H
ragge
1.156
32 #include <strings.h>
gmcgarry
1.171
33 #endif
34 #ifdef HAVE_STDINT_H
ragge
1.159
35 #include <stdint.h>
gmcgarry
1.171
36 #endif
ragge
1.62
37 #include <stdlib.h>
ragge
1.1
38
ragge
1.149
39 #define MAXLOOP 20 /* Max number of allocation loops XXX 3 should be enough */
ragge
1.142
40
ragge
1.176
41 #ifndef MAX
ragge
1.74
42 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
ragge
1.176
43 #endif
ragge
1.74
44  
ragge
1.42
45 /*
46  * New-style register allocator using graph coloring.
ragge
1.46
47  * The design is based on the George and Appel paper
48  * "Iterated Register Coalescing", ACM Transactions, No 3, May 1996.
ragge
1.42
49  */
50
ragge
1.59
51 #define BITALLOC(ptr,all,sz) { \
ragge
1.156
52         int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr0sz__s); }
ragge
1.59
53
ragge
1.108
54 #undef COMPERR_PERM_MOVE
ragge
1.209
55 #ifdef PCC_DEBUG
plunky
1.228
56 #define RDEBUG(x)       if (r2debug) printf x
57 #define RRDEBUG(x)      if (r2debug > 1) printf x
58 #define RPRINTIP(x)     if (r2debug) printip(x)
gmcgarry
1.200
59 #define RDEBUGX(x)              x
plunky
1.228
60 #define UDEBUG(x)       if (u2debug) printf x
ragge
1.188
61 #define BDEBUG(x)       if (b2debug) printf x
ragge
1.209
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
ragge
1.82
72
ragge
1.189
73 #define VALIDREG(p)     (p->n_op == REG && TESTBIT(validregs, regno(p)))
74
ragge
1.79
75 /*
ragge
1.133
76  * Data structure overview for this implementation of graph coloring:
ragge
1.79
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  */
104 typedef struct regw3 {
105         struct regw3 *r_next;
106         struct regw *a_temp;
107 ADJL;
108
109 /*
110  * Structure describing a move.
111  */
112 typedef struct regm {
113         DLIST_ENTRY(regmlink;
114         struct regw *src, *dst;
115         int queue;
116 REGM;
117
118 typedef struct movlink {
119         struct movlink *next;
120         REGM *regm;
121 MOVL;
122
123 /*
124  * Structure describing a temporary.
125  */
126 typedef struct regw {
127         DLIST_ENTRY(regwlink;
128         ADJL *r_adjList;        /* linked list of adjacent nodes */
129         int r_class;            /* this nodes class */
ragge
1.85
130         int r_nclass[NUMCLASS+1];       /* count of adjacent classes */
ragge
1.79
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 */
ragge
1.234
135         int nodnum;             /* Human-readable node number */
ragge
1.79
136 REGW;
137
138 /*
139  * Worklists, a node is always on exactly one of these lists.
140  */
141 static REGW precoloredsimplifyWorklistfreezeWorklistspillWorklist,
142         spilledNodescoalescedNodescoloredNodesselectStack;
143 static REGW initial, *nblock;
ragge
1.146
144 static void insnwalk(NODE *p);
ragge
1.84
145 #ifdef PCC_DEBUG
ragge
1.168
146 int use_regw;
ragge
1.234
147 #endif
ragge
1.87
148 int nodnum = 100;
ragge
1.222
149 int ntszstktemp;
ragge
1.84
150 #define SETNUM(x)       (x)->nodnum = nodnum++
151 #define ASGNUM(x)       (x)->nodnum
ragge
1.79
152
ragge
1.191
153 #define ALLNEEDS (NACOUNT|NBCOUNT|NCCOUNT|NDCOUNT|NECOUNT|NFCOUNT|NGCOUNT)
ragge
1.97
154
ragge
1.87
155 /* XXX */
ragge
1.88
156 REGW *ablock;
ragge
1.87
157
ragge
1.99
158 static int tempmintempmaxbasetempxbits;
ragge
1.107
159 /*
ragge
1.108
160  * nsavregs is an array that matches the permregs array.
161  * Each entry in the array may have the values:
162  * 0    : register coalesced, just ignore.
163  * 1    : save register on stack
164  * If the entry is 0 but the resulting color differs from the 
165  * corresponding permregs index, add moves.
166  * XXX - should be a bitfield!
ragge
1.107
167  */
ragge
1.99
168 static int *nsavregs, *ndontregs;
ragge
1.87
169
ragge
1.40
170 /*
ragge
1.89
171  * Return the REGW struct for a temporary.
ragge
1.128
172  * If first time touched, enter into list for existing vars.
173  * Only called from sucomp().
ragge
1.89
174  */
175 static REGW *
ragge
1.120
176 newblock(NODE *p)
ragge
1.89
177 {
ragge
1.209
178         REGW *nb;
179
180 #ifdef PCC_DEBUG
181         if (regno(p) < tempmin || regno(p) >= tempmax)
182                 comperr("temp %p(%d) outside limits (%d-%d)",
183                     pregno(p), tempmintempmax);
184 #endif
185         nb = &nblock[regno(p)];
ragge
1.89
186         if (nb->link.q_forw == 0) {
187                 DLIST_INSERT_AFTER(&initialnblink);
gmcgarry
1.171
188 #ifdef PCC_DEBUG
ragge
1.167
189                 ASGNUM(nb) = regno(p);
ragge
1.106
190                 RDEBUG(("Adding longtime %d for tmp %d\n",
ragge
1.167
191                     nb->nodnumregno(p)));
gmcgarry
1.171
192 #endif
ragge
1.89
193         }
ragge
1.90
194         if (nb->r_class == 0)
ragge
1.94
195                 nb->r_class = gclass(p->n_type);
gmcgarry
1.171
196 #ifdef PCC_DEBUG
ragge
1.129
197         RDEBUG(("newblock: p %p, node %d class %d\n",
198             pnb->nodnumnb->r_class));
gmcgarry
1.171
199 #endif
ragge
1.89
200         return nb;
201 }
202
203 /*
ragge
1.40
204  * Count the number of registers needed to evaluate a tree.
205  * This is only done to find the evaluation order of the tree.
ragge
1.42
206  * While here, assign temp numbers to the registers that will
207  * be needed when the tree is evaluated.
ragge
1.46
208  *
ragge
1.102
209  * While traversing the tree, assign REGW nodes to the registers
ragge
1.46
210  * used by all instructions:
ragge
1.102
211  *      - n_regw[0] is always set to the outgoing node. If the
ragge
1.46
212  *        instruction is 2-op (addl r0,r1) then an implicit move
213  *        is inserted just before the left (clobbered) operand.
ragge
1.102
214  *      - if the instruction has needs then REGW nodes are
215  *        allocated as n_regw[1] etc.
ragge
1.40
216  */
217 int
218 nsucomp(NODE *p)
219 {
ragge
1.63
220         struct optab *q;
ragge
1.40
221         int leftright;
ragge
1.124
222         int nregneedinxrego;
ragge
1.191
223         int naregnbregncregndregneregnfregngreg;
ragge
1.96
224         REGW *w;
ragge
1.40
225
ragge
1.124
226         o = optype(p->n_op);
227
ragge
1.128
228         UDEBUG(("entering nsucomp, node %p\n"p));
229
230         if (TBLIDX(p->n_su) == 0) {
ragge
1.124
231                 int a = 0b;
ragge
1.139
232
233                 p->n_regw = NULL;
ragge
1.127
234                 if (o == LTYPE ) {
ragge
1.129
235                         if (p->n_op == TEMP)
ragge
1.127
236                                 p->n_regw = newblock(p);
ragge
1.161
237                         else if (p->n_op == REG)
ragge
1.167
238                                 p->n_regw = &ablock[regno(p)];
ragge
1.127
239                 } else
ragge
1.124
240                         a = nsucomp(p->n_left);
241                 if (o == BITYPE) {
242                         b = nsucomp(p->n_right);
ragge
1.140
243                         if (b > a)
244                                 p->n_su |= DORIGHT;
ragge
1.124
245                         a = MAX(ab);
246                 }
247                 return a;
248         }
ragge
1.112
249
ragge
1.63
250         q = &table[TBLIDX(p->n_su)];
ragge
1.88
251
ragge
1.222
252 #define NNEEDS(a,b) ((q->needs & a)/b)
ragge
1.191
253         for (i = (q->needs & NACOUNT), nareg = 0ii -= NAREG)
254                 nareg++;
ragge
1.88
255         for (i = (q->needs & NBCOUNT), nbreg = 0ii -= NBREG)
256                 nbreg++;
257         for (i = (q->needs & NCCOUNT), ncreg = 0ii -= NCREG)
258                 ncreg++;
259         for (i = (q->needs & NDCOUNT), ndreg = 0ii -= NDREG)
260                 ndreg++;
ragge
1.191
261         for (i = (q->needs & NECOUNT), nereg = 0ii -= NEREG)
262                 nereg++;
263         for (i = (q->needs & NFCOUNT), nfreg = 0ii -= NFREG)
264                 nfreg++;
265         for (i = (q->needs & NGCOUNT), ngreg = 0ii -= NGREG)
266                 ngreg++;
ragge
1.88
267
ragge
1.222
268         if (ntsz < NNEEDS(NTMASKNTEMP) * szty(p->n_type))
269                 ntsz = NNEEDS(NTMASKNTEMP) * szty(p->n_type);
270
ragge
1.191
271         nxreg = nareg + nbreg + ncreg + ndreg + nereg + nfreg + ngreg;
ragge
1.140
272         nreg = nxreg;
ragge
1.40
273         if (callop(p->n_op))
274                 nreg = MAX(fregsnreg);
275
ragge
1.124
276         if (o == BITYPE) {
277                 right = nsucomp(p->n_right);
278         } else
279                 right = 0;
ragge
1.103
280
ragge
1.124
281         if (o != LTYPE)
282                 left = nsucomp(p->n_left);
283         else
284                 left = 0;
ragge
1.103
285
ragge
1.106
286         UDEBUG(("node %p left %d right %d\n"pleftright));
287
ragge
1.124
288         if (o == BITYPE) {
ragge
1.40
289                 /* Two children */
ragge
1.140
290                 if (right == left) {
ragge
1.40
291                         need = left + MAX(nreg1);
ragge
1.140
292                 } else {
ragge
1.40
293                         need = MAX(rightleft);
ragge
1.140
294                         need = MAX(neednreg);
295                 }
ragge
1.137
296                 if (setorder(p) == 0) {
297                         /* XXX - should take care of overlapping needs */
298                         if (right > left) {
ragge
1.54
299                                 p->n_su |= DORIGHT;
ragge
1.137
300                         } else if (right == left) {
301                                 /* A favor to 2-operand architectures */
302                                 if ((q->rewrite & RRIGHT) == 0)
303                                         p->n_su |= DORIGHT;
304                         }
ragge
1.54
305                 }
ragge
1.124
306         } else if (o != LTYPE) {
ragge
1.40
307                 /* One child */
308                 need = MAX(rightleft) + nreg;
309         } else
310                 need = nreg;
ragge
1.89
311
312         if (p->n_op == TEMP)
ragge
1.120
313                 (void)newblock(p);
ragge
1.84
314
ragge
1.106
315         if (TCLASS(p->n_su) == 0 && nxreg == 0) {
316                 UDEBUG(("node %p no class\n"p));
ragge
1.108
317                 p->n_regw = NULL/* may be set earlier */
ragge
1.106
318                 return need;
319         }
320
gmcgarry
1.171
321 #ifdef PCC_DEBUG
ragge
1.88
322 #define ADCL(n, cl)     \
323         for (i = 0i < ni++, w++) {  w->r_class = cl; \
324                 DLIST_INSERT_BEFORE(&initialwlink);  SETNUM(w); \
ragge
1.106
325                 UDEBUG(("Adding " #n " %d\n"w->nodnum)); \
ragge
1.88
326         }
gmcgarry
1.171
327 #else
328 #define ADCL(n, cl)     \
329         for (i = 0i < ni++, w++) {  w->r_class = cl; \
330                 DLIST_INSERT_BEFORE(&initialwlink);  SETNUM(w); \
331         }
332 #endif
ragge
1.96
333
ragge
1.106
334         UDEBUG(("node %p numregs %d\n"pnxreg+1));
ragge
1.96
335         w = p->n_regw = tmpalloc(sizeof(REGW) * (nxreg+1));
336         memset(w0sizeof(REGW) * (nxreg+1));
ragge
1.108
337
ragge
1.96
338         w->r_class = TCLASS(p->n_su);
339         if (w->r_class == 0)
340                 w->r_class = gclass(p->n_type);
ragge
1.153
341         w->r_nclass[0] = o == LTYPE/* XXX store leaf info here */
ragge
1.96
342         SETNUM(w);
343         if (w->r_class)
344                 DLIST_INSERT_BEFORE(&initialwlink);
gmcgarry
1.171
345 #ifdef PCC_DEBUG
otto
1.158
346         UDEBUG(("Adding short %d class %d\n"w->nodnumw->r_class));
gmcgarry
1.171
347 #endif
ragge
1.96
348         w++;
349         ADCL(naregCLASSA);
350         ADCL(nbregCLASSB);
351         ADCL(ncregCLASSC);
352         ADCL(ndregCLASSD);
ragge
1.191
353         ADCL(neregCLASSE);
354         ADCL(nfregCLASSF);
355         ADCL(ngregCLASSG);
ragge
1.89
356
ragge
1.108
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
ragge
1.106
371         UDEBUG(("node %p return regs %d\n"pneed));
372
373         return need;
ragge
1.40
374 }
375
ragge
1.79
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
ragge
1.46
383
ragge
1.47
384 static bittype *live;
ragge
1.46
385
ragge
1.49
386 #define PUSHWLIST(w, l) DLIST_INSERT_AFTER(&l, w, link); w->r_onlist = &l
ragge
1.48
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);
ragge
1.46
392
ragge
1.82
393 #define trivially_colorable(x) \
394         trivially_colorable_p((x)->r_class, (x)->r_nclass)
ragge
1.76
395 /*
396  * Determine if a node is trivially colorable ("degree < K").
ragge
1.78
397  * This implementation is a dumb one, without considering speed.
ragge
1.76
398  */
399 static int
ragge
1.82
400 trivially_colorable_p(int cint *n)
ragge
1.76
401 {
ragge
1.85
402         int r[NUMCLASS+1];
ragge
1.78
403         int i;
404
ragge
1.85
405         for (i = 1i < NUMCLASS+1i++)
ragge
1.78
406                 r[i] = n[i] < regK[i] ? n[i] : regK[i];
407
ragge
1.87
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 (; exclexcl >>= 1)
413                 if (excl & 1)
414                         r[c]++;
415 #endif
ragge
1.85
416
ragge
1.82
417         i = COLORMAP(cr);
gmcgarry
1.163
418         if (i < 0 || i > 1)
419                 comperr("trivially_colorable_p");
plunky
1.228
420         RRDEBUG(("trivially_colorable_p: n[1] %d n[2] %d n[3] %d n[4] "
421             "%d for class %d, triv %d\n"n[1], n[2], n[3], n[4], ci));
ragge
1.82
422         return i;
ragge
1.76
423 }
424
ragge
1.222
425 int
ragge
1.97
426 ncnt(int needs)
427 {
428         int i = 0;
429
430         while (needs & NACOUNT)
431                 needs -= NAREGi++;
432         while (needs & NBCOUNT)
433                 needs -= NBREGi++;
434         while (needs & NCCOUNT)
435                 needs -= NCREGi++;
436         while (needs & NDCOUNT)
437                 needs -= NDREGi++;
ragge
1.191
438         while (needs & NECOUNT)
439                 needs -= NEREGi++;
440         while (needs & NFCOUNT)
441                 needs -= NFREGi++;
442         while (needs & NGCOUNT)
443                 needs -= NGREGi++;
ragge
1.97
444         return i;
445 }
446
gmcgarry
1.177
447 static REGW *
ragge
1.48
448 popwlist(REGW *l)
449 {
450         REGW *w = DLIST_NEXT(llink);
451
452         DLIST_REMOVE(wlink);
ragge
1.49
453         w->r_onlist = NULL;
ragge
1.48
454         return w;
455 }
ragge
1.46
456
ragge
1.42
457 /*
ragge
1.46
458  * Move lists, a move node is always on only one list.
ragge
1.40
459  */
ragge
1.48
460 static REGM coalescedMovesconstrainedMovesfrozenMoves
461         worklistMovesactiveMoves;
ragge
1.46
462 enum { COALCONSTRFROZENWLISTACTIVE };
463
gmcgarry
1.177
464 static REGM *
ragge
1.48
465 popmlist(REGM *l)
466 {
467         REGM *w = DLIST_NEXT(llink);
468
469         DLIST_REMOVE(wlink);
470         return w;
471 }
472
ragge
1.63
473 /*
474  * About data structures used in liveness analysis:
475  *
476  * The temporaries generated in pass1 are numbered between tempmin and
477  * tempmax.  Temporaries generated in pass2 are numbered above tempmax,
478  * so they are sequentially numbered.
479  *
480  * Bitfields are used for liveness.  Bit arrays are allocated on the
481  * heap for the "live" variable and on the stack for the in, out, gen
gmcgarry
1.177
482  * and killed variables. Therefore, for a temp number, the bit number must
ragge
1.63
483  * be biased with tempmin.
484  *
485  * There may be an idea to use a different data structure to store 
486  * pass2 allocated temporaries, because they are very sparse.
487  */
488
489 #ifdef PCC_DEBUG
490 static void
491 LIVEADD(int x)
492 {
493         RDEBUG(("Liveadd: %d\n"x));
ragge
1.161
494         if (x >= MAXREGS && (x < tempmin || x >= tempmax))
ragge
1.63
495                 comperr("LIVEADD: out of range");
ragge
1.161
496         if (x < MAXREGS) {
497                 BITSET(livex);
498         } else
499                 BITSET(live, (x-tempmin+MAXREGS));
ragge
1.63
500 }
ragge
1.161
501
ragge
1.63
502 static void
503 LIVEDEL(int x)
504 {
505         RDEBUG(("Livedel: %d\n"x));
ragge
1.161
506
507         if (x >= MAXREGS && (x < tempmin || x >= tempmax))
ragge
1.63
508                 comperr("LIVEDEL: out of range");
ragge
1.161
509         if (x < MAXREGS) {
510                 BITCLEAR(livex);
511         } else
512                 BITCLEAR(live, (x-tempmin+MAXREGS));
ragge
1.63
513 }
514 #else
ragge
1.161
515 #define LIVEADD(x) \
516         (x >= MAXREGS ? BITSET(live, (x-tempmin+MAXREGS)) : BITSET(livex))
517 #define LIVEDEL(x) \
518         (x >= MAXREGS ? BITCLEAR(live, (x-tempmin+MAXREGS)) : BITCLEAR(livex))
ragge
1.63
519 #endif
ragge
1.46
520
ragge
1.83
521 static struct lives {
522         DLIST_ENTRY(liveslink;
523         REGW *var;
524 lusedlunused;
525
ragge
1.79
526 static void
527 LIVEADDR(REGW *x)
528 {
ragge
1.83
529         struct lives *l;
530
531 #ifdef PCC_DEBUG
ragge
1.85
532         RDEBUG(("LIVEADDR: %d\n"x->nodnum));
ragge
1.83
533         DLIST_FOREACH(l, &lusedlink)
534                 if (l->var == x)
ragge
1.90
535                         return;
gmcgarry
1.200
536 #if 0
537                         comperr("LIVEADDR: multiple %d"ASGNUM(x));
538 #endif
ragge
1.83
539 #endif
540         if (!DLIST_ISEMPTY(&lunusedlink)) {
541                 l = DLIST_NEXT(&lunusedlink);
542                 DLIST_REMOVE(llink);
543         } else
544                 l = tmpalloc(sizeof(struct lives));
545
546         l->var = x;
547         DLIST_INSERT_AFTER(&lusedllink);
ragge
1.79
548 }
549
550 static void
551 LIVEDELR(REGW *x)
552 {
ragge
1.83
553         struct lives *l;
554
gmcgarry
1.171
555 #ifdef PCC_DEBUG
ragge
1.85
556         RDEBUG(("LIVEDELR: %d\n"x->nodnum));
gmcgarry
1.171
557 #endif
ragge
1.83
558         DLIST_FOREACH(l, &lusedlink) {
559                 if (l->var != x)
560                         continue;
561                 DLIST_REMOVE(llink);
562                 DLIST_INSERT_AFTER(&lunusedllink);
563                 return;
564         }
gmcgarry
1.200
565 #if 0
566         comperr("LIVEDELR: %p not found"x);
567 #endif
ragge
1.79
568 }
569
ragge
1.46
570 #define MOVELISTADD(t, p) movelistadd(t, p)
ragge
1.49
571 #define WORKLISTMOVEADD(s,d) worklistmoveadd(s,d)
ragge
1.46
572
573 static void
ragge
1.79
574 movelistadd(REGW *tREGM *p)
ragge
1.46
575 {
576         MOVL *w = tmpalloc(sizeof(MOVL));
577
578         w->regm = p;
ragge
1.79
579         w->next = t->r_moveList;
580         t->r_moveList = w;
ragge
1.46
581 }
582
583 static REGM *
ragge
1.79
584 worklistmoveadd(REGW *srcREGW *dst)
ragge
1.46
585 {
586         REGM *w = tmpalloc(sizeof(REGM));
587
ragge
1.48
588         DLIST_INSERT_AFTER(&worklistMoveswlink);
ragge
1.49
589         w->src = src;
590         w->dst = dst;
ragge
1.46
591         w->queue = WLIST;
592         return w;
593 }
594
ragge
1.195
595 #define HASHSZ  16384
ragge
1.46
596 struct AdjSet {
597         struct AdjSet *next;
ragge
1.79
598         REGW *u, *v;
ragge
1.195
599 } *edgehash[HASHSZ];
ragge
1.46
600
601 /* Check if a node pair is adjacent */
602 static int
ragge
1.79
603 adjSet(REGW *uREGW *v)
ragge
1.46
604 {
605         struct AdjSet *w;
ragge
1.219
606         REGW *t;
ragge
1.218
607
ragge
1.103
608         if (ONLIST(u) == &precolored) {
609                 ADJL *a = ADJLIST(v);
610                 /*
611                  * Check if any of the registers that have edges against v
612                  * alias to u.
613                  */
614                 for (; aa = a->r_next) {
615                         if (ONLIST(a->a_temp) != &precolored)
616                                 continue;
617                         t = a->a_temp;
618                         if (interferes(t - ablocku - ablock))
619                                 return 1;
620                 }
621         }
ragge
1.218
622
ragge
1.211
623         w = edgehash[(u->nodnum+v->nodnum)& (HASHSZ-1)];
ragge
1.219
624
ragge
1.46
625         for (; ww = w->next) {
ragge
1.211
626                 if ((u == w->u && v == w->v) || (u == w->v && v == w->u))
ragge
1.46
627                         return 1;
628         }
629         return 0;
630 }
631
632 /* Add a pair to adjset.  No check for dups */
ragge
1.219
633 static int
ragge
1.79
634 adjSetadd(REGW *uREGW *v)
ragge
1.46
635 {
636         struct AdjSet *w;
ragge
1.79
637         int x;
ragge
1.46
638
ragge
1.211
639         x = (u->nodnum+v->nodnum)& (HASHSZ-1);
ragge
1.219
640         for (w = edgehash[x]; ww = w->next)
641                 if ((u == w->u && v == w->v) || (u == w->v && v == w->u))
642                         return 1;
643
ragge
1.46
644         w = tmpalloc(sizeof(struct AdjSet));
645         w->u = uw->v = v;
ragge
1.79
646         w->next = edgehash[x];
647         edgehash[x] = w;
ragge
1.219
648         return 0;
ragge
1.46
649 }
650
651 /*
652  * Add an interference edge between two nodes.
653  */
654 static void
ragge
1.79
655 AddEdge(REGW *uREGW *v)
ragge
1.46
656 {
ragge
1.47
657         ADJL *x;
658
gmcgarry
1.171
659 #ifdef PCC_DEBUG
ragge
1.103
660         RRDEBUG(("AddEdge: u %d v %d\n"ASGNUM(u), ASGNUM(v)));
ragge
1.88
661
662 #if 0
ragge
1.85
663         if (ASGNUM(u) == 0)
664                 comperr("AddEdge 0");
ragge
1.88
665 #endif
ragge
1.85
666         if (CLASS(u) == 0 || CLASS(v) == 0)
ragge
1.96
667                 comperr("AddEdge class == 0 (%d=%d, %d=%d)",
668                     CLASS(u), ASGNUM(u), CLASS(v), ASGNUM(v));
ragge
1.79
669 #endif
ragge
1.46
670
671         if (u == v)
672                 return;
ragge
1.219
673         if (adjSetadd(uv))
ragge
1.46
674                 return;
675
ragge
1.87
676 #if 0
677         if (ONLIST(u) == &precolored || ONLIST(v) == &precolored)
ragge
1.78
678                 comperr("precolored node in AddEdge");
679 #endif
ragge
1.79
680
ragge
1.87
681         if (ONLIST(u) != &precolored) {
682                 x = tmpalloc(sizeof(ADJL));
683                 x->a_temp = v;
684                 x->r_next = u->r_adjList;
685                 u->r_adjList = x;
686                 NCLASS(uCLASS(v))++;
687         }
ragge
1.79
688
ragge
1.87
689         if (ONLIST(v) != &precolored) {
690                 x = tmpalloc(sizeof(ADJL));
691                 x->a_temp = u;
692                 x->r_next = v->r_adjList;
693                 v->r_adjList = x;
694                 NCLASS(vCLASS(u))++;
695         }
ragge
1.88
696
ragge
1.110
697 #if 0
ragge
1.73
698         RDEBUG(("AddEdge: u %d(d %d) v %d(d %d)\n"uDEGREE(u), vDEGREE(v)));
ragge
1.76
699 #endif
ragge
1.46
700 }
701
702 static int
ragge
1.79
703 MoveRelated(REGW *n)
ragge
1.46
704 {
705         MOVL *l;
706         REGM *w;
707
ragge
1.49
708         for (l = MOVELIST(n); ll = l->next) {
ragge
1.46
709                 w = l->regm;
710                 if (w->queue == ACTIVE || w->queue == WLIST)
711                         return 1;
712         }
713         return 0;
714 }
715
716 static void
717 MkWorklist(void)
718 {
719         REGW *w;
ragge
1.87
720
gmcgarry
1.200
721         RDEBUGX(int s=0);
722         RDEBUGX(int f=0);
723         RDEBUGX(int d=0);
ragge
1.46
724
ragge
1.48
725         DLIST_INIT(&precoloredlink);
726         DLIST_INIT(&simplifyWorklistlink);
727         DLIST_INIT(&freezeWorklistlink);
728         DLIST_INIT(&spillWorklistlink);
729         DLIST_INIT(&spilledNodeslink);
730         DLIST_INIT(&coalescedNodeslink);
731         DLIST_INIT(&coloredNodeslink);
732         DLIST_INIT(&selectStacklink);
ragge
1.87
733
734         /*
735          * Remove all nodes from the initial list and put them on 
736          * one of the worklists.
737          */
ragge
1.79
738         while (!DLIST_ISEMPTY(&initiallink)) {
739                 w = DLIST_NEXT(&initiallink);
740                 DLIST_REMOVE(wlink);
741                 if (!trivially_colorable(w)) {
ragge
1.46
742                         PUSHWLIST(wspillWorklist);
gmcgarry
1.200
743                         RDEBUGX(s++);
ragge
1.79
744                 } else if (MoveRelated(w)) {
ragge
1.46
745                         PUSHWLIST(wfreezeWorklist);
gmcgarry
1.200
746                         RDEBUGX(f++);
ragge
1.46
747                 } else {
748                         PUSHWLIST(wsimplifyWorklist);
gmcgarry
1.200
749                         RDEBUGX(d++);
ragge
1.46
750                 }
751         }
ragge
1.68
752         RDEBUG(("MkWorklist: spill %d freeze %d simplify %d\n"s,f,d));
ragge
1.46
753 }
754
ragge
1.48
755 static void
ragge
1.79
756 addalledges(REGW *e)
ragge
1.48
757 {
758         int ijk;
ragge
1.83
759         struct lives *l;
ragge
1.48
760
gmcgarry
1.171
761 #ifdef PCC_DEBUG
ragge
1.85
762         RDEBUG(("addalledges for %d\n"e->nodnum));
gmcgarry
1.171
763 #endif
ragge
1.88
764
ragge
1.108
765         if (e->r_class == -1)
766                 return/* unused */
ragge
1.138
767
ragge
1.98
768         if (ONLIST(e) != &precolored) {
ragge
1.99
769                 for (i = 0ndontregs[i] >= 0i++)
770                         AddEdge(e, &ablock[ndontregs[i]]);
ragge
1.98
771         }
ragge
1.88
772
ragge
1.161
773         /* First add to long-lived temps and hard regs */
ragge
1.103
774         RDEBUG(("addalledges longlived "));
ragge
1.161
775         for (i = 0i < xbitsi += NUMBITS) {
ragge
1.203
776                 if ((k = live[i/NUMBITS])) {
777                         while (k) {
778                                 j = ffs(k)-1;
779                                 if (i+j < MAXREGS)
780                                         AddEdge(&ablock[i+j], e);
781                                 else
782                                         AddEdge(&nblock[i+j+tempmin-MAXREGS],e);
783                                 RRDEBUG(("%d "i+j+tempmin));
784                                 k &= ~(1 << j);
785                         }
ragge
1.48
786                 }
ragge
1.202
787 #if NUMBITS > 32 /* XXX hack for LP64 */
788                 k = (live[i/NUMBITS] >> 32);
789                 while (k) {
790                         j = ffs(k)-1;
791                         if (i+j+32 < MAXREGS)
792                                 AddEdge(&ablock[i+j+32], e);
793                         else
794                                 AddEdge(&nblock[i+j+tempmin-MAXREGS+32], e);
795                         RRDEBUG(("%d "i+j+tempmin+32));
796                         k &= ~(1 << j);
797                 }
798 #endif
ragge
1.48
799         }
ragge
1.103
800         RDEBUG(("done\n"));
ragge
1.83
801         /* short-lived temps */
ragge
1.103
802         RDEBUG(("addalledges shortlived "));
803         DLIST_FOREACH(l, &lusedlink) {
gmcgarry
1.171
804 #ifdef PCC_DEBUG
ragge
1.103
805                 RRDEBUG(("%d "ASGNUM(l->var)));
gmcgarry
1.171
806 #endif
ragge
1.103
807                 AddEdge(l->vare);
808         }
809         RDEBUG(("done\n"));
ragge
1.78
810 }
811
ragge
1.128
812 /*
813  * Add a move edge between def and use.
814  */
ragge
1.49
815 static void
ragge
1.79
816 moveadd(REGW *defREGW *use)
ragge
1.49
817 {
818         REGM *r;
ragge
1.208
819         MOVL *w;
ragge
1.49
820
ragge
1.68
821         if (def == use)
822                 return/* no move to itself XXX - ``shouldn't happen'' */
gmcgarry
1.171
823 #ifdef PCC_DEBUG
ragge
1.84
824         RDEBUG(("moveadd: def %d use %d\n"ASGNUM(def), ASGNUM(use)));
gmcgarry
1.171
825 #endif
ragge
1.49
826
ragge
1.208
827         /*
828          * Check if we are already on move list.
829          * XXX How can that happen ???
830          */
831         for (w = MOVELIST(def); ww = w->next) {
832                 if ((w->regm->src == def && w->regm->dst == use) ||
833                     (w->regm->src == use && w->regm->dst == def))
834                         return/* already there XXX reverse? */
835         }
836
ragge
1.49
837         r = WORKLISTMOVEADD(usedef);
838         MOVELISTADD(defr);
839         MOVELISTADD(user);
840 }
841
ragge
1.128
842 /*
843  * Traverse arguments backwards.
844  * XXX - can this be tricked in some other way?
845  */
846 static void
847 argswalk(NODE *p)
848 {
849
850         if (p->n_op == CM) {
851                 argswalk(p->n_left);
852                 insnwalk(p->n_right);
853         } else
854                 insnwalk(p);
855 }
856
ragge
1.129
857 /*
858  * Add to (or remove from) live set variables that must not
859  * be clobbered when traversing down on the other leg for 
860  * a BITYPE node.
861  */
862 static void
863 setlive(NODE *pint setREGW *rv)
864 {
ragge
1.151
865         if (rv != NULL) {
ragge
1.189
866                 if (rv->nodnum < MAXREGS &&
867                     TESTBIT(validregsrv->nodnum) == 0)
868                         return;
ragge
1.151
869                 set ? LIVEADDR(rv) : LIVEDELR(rv);
870                 return;
871         }
ragge
1.129
872
ragge
1.151
873         if (p->n_regw != NULL) {
ragge
1.189
874                 if (p->n_regw->nodnum < MAXREGS &&
875                     TESTBIT(validregsp->n_regw->nodnum) == 0)
876                         return;
ragge
1.151
877                 set ? LIVEADDR(p->n_regw) : LIVEDELR(p->n_regw);
878                 return;
879         }
ragge
1.129
880
881         switch (optype(p->n_op)) {
882         case LTYPE:
ragge
1.189
883                 if (p->n_op == TEMP || VALIDREG(p))
ragge
1.167
884                         set ? LIVEADD(regno(p)) : LIVEDEL(regno(p));
ragge
1.129
885                 break;
886         case BITYPE:
887                 setlive(p->n_rightsetrv);
888                 /* FALLTHROUGH */
889         case UTYPE:
890                 setlive(p->n_leftsetrv);
891                 break;
892         }
893 }
ragge
1.128
894
ragge
1.133
895 /*
ragge
1.134
896  * Add edges for temporary w against all temporaries that may be
897  * used simultaneously (like index registers).
898  */
899 static void
900 addedge_r(NODE *pREGW *w)
901 {
ragge
1.170
902         RRDEBUG(("addedge_r: node %p regw %p\n"pw));
903
ragge
1.151
904         if (p->n_regw != NULL) {
ragge
1.189
905                 if (p->n_regw->nodnum < MAXREGS &&
906                     TESTBIT(validregsp->n_regw->nodnum) == 0)
907                         return;
ragge
1.151
908                 AddEdge(p->n_regww);
909                 return;
910         }
ragge
1.134
911
912         if (optype(p->n_op) == BITYPE)
913                 addedge_r(p->n_rightw);
914         if (optype(p->n_op) != LTYPE)