Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:plunky:20121020185913

Diff

Diff from 1.233 to:

Annotations

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

Annotated File View

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