Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20140607140204

Diff

Diff from 1.238 to:

Annotations

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

Annotated File View

ragge
1.238
1 /*      $Id: regs.c,v 1.238 2014/06/07 14:02:04 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) {
ragge
1.238
301 #if 0
302         /* XXX - need something more clever when large left trees */
ragge
1.137
303                                 /* A favor to 2-operand architectures */
304                                 if ((q->rewrite & RRIGHT) == 0)
305                                         p->n_su |= DORIGHT;
ragge
1.238
306 #endif
ragge
1.137
307                         }
ragge
1.54
308                 }
ragge
1.124
309         } else if (o != LTYPE) {
ragge
1.40
310                 /* One child */
311                 need = MAX(rightleft) + nreg;
312         } else
313                 need = nreg;
ragge
1.89
314
315         if (p->n_op == TEMP)
ragge
1.120
316                 (void)newblock(p);
ragge
1.84
317
ragge
1.106
318         if (TCLASS(p->n_su) == 0 && nxreg == 0) {
319                 UDEBUG(("node %p no class\n"p));
ragge
1.108
320                 p->n_regw = NULL/* may be set earlier */
ragge
1.106
321                 return need;
322         }
323
gmcgarry
1.171
324 #ifdef PCC_DEBUG
ragge
1.88
325 #define ADCL(n, cl)     \
326         for (i = 0i < ni++, w++) {  w->r_class = cl; \
327                 DLIST_INSERT_BEFORE(&initialwlink);  SETNUM(w); \
ragge
1.106
328                 UDEBUG(("Adding " #n " %d\n"w->nodnum)); \
ragge
1.88
329         }
gmcgarry
1.171
330 #else
331 #define ADCL(n, cl)     \
332         for (i = 0i < ni++, w++) {  w->r_class = cl; \
333                 DLIST_INSERT_BEFORE(&initialwlink);  SETNUM(w); \
334         }
335 #endif
ragge
1.96
336
ragge
1.106
337         UDEBUG(("node %p numregs %d\n"pnxreg+1));
ragge
1.96
338         w = p->n_regw = tmpalloc(sizeof(REGW) * (nxreg+1));
339         memset(w0sizeof(REGW) * (nxreg+1));
ragge
1.108
340
ragge
1.96
341         w->r_class = TCLASS(p->n_su);
342         if (w->r_class == 0)
343                 w->r_class = gclass(p->n_type);
ragge
1.153
344         w->r_nclass[0] = o == LTYPE/* XXX store leaf info here */
ragge
1.96
345         SETNUM(w);
346         if (w->r_class)
347                 DLIST_INSERT_BEFORE(&initialwlink);
gmcgarry
1.171
348 #ifdef PCC_DEBUG
otto
1.158
349         UDEBUG(("Adding short %d class %d\n"w->nodnumw->r_class));
gmcgarry
1.171
350 #endif
ragge
1.96
351         w++;
352         ADCL(naregCLASSA);
353         ADCL(nbregCLASSB);
354         ADCL(ncregCLASSC);
355         ADCL(ndregCLASSD);
ragge
1.191
356         ADCL(neregCLASSE);
357         ADCL(nfregCLASSF);
358         ADCL(ngregCLASSG);
ragge
1.89
359
ragge
1.108
360         if (q->rewrite & RESC1) {
361                 w = p->n_regw + 1;
362                 w->r_class = -1;
363                 DLIST_REMOVE(w,link);
364         } else if (q->rewrite & RESC2) {
365                 w = p->n_regw + 2;
366                 w->r_class = -1;
367                 DLIST_REMOVE(w,link);
368         } else if (q->rewrite & RESC3) {
369                 w = p->n_regw + 3;
370                 w->r_class = -1;
371                 DLIST_REMOVE(w,link);
372         }
373
ragge
1.106
374         UDEBUG(("node %p return regs %d\n"pneed));
375
376         return need;
ragge
1.40
377 }
378
ragge
1.79
379 #define CLASS(x)        (x)->r_class
380 #define NCLASS(x,c)     (x)->r_nclass[c]
381 #define ADJLIST(x)      (x)->r_adjList
382 #define ALIAS(x)        (x)->r_alias
383 #define ONLIST(x)       (x)->r_onlist
384 #define MOVELIST(x)     (x)->r_moveList
385 #define COLOR(x)        (x)->r_color
ragge
1.46
386
ragge
1.47
387 static bittype *live;
ragge
1.46
388
ragge
1.49
389 #define PUSHWLIST(w, l) DLIST_INSERT_AFTER(&l, w, link); w->r_onlist = &l
ragge
1.48
390 #define POPWLIST(l)     popwlist(&l);
391 #define DELWLIST(w)     DLIST_REMOVE(w, link)
392 #define WLISTEMPTY(h)   DLIST_ISEMPTY(&h,link)
393 #define PUSHMLIST(w, l, q)      DLIST_INSERT_AFTER(&l, w, link); w->queue = q
394 #define POPMLIST(l)     popmlist(&l);
ragge
1.46
395
ragge
1.82
396 #define trivially_colorable(x) \
397         trivially_colorable_p((x)->r_class, (x)->r_nclass)
ragge
1.76
398 /*
399  * Determine if a node is trivially colorable ("degree < K").
ragge
1.78
400  * This implementation is a dumb one, without considering speed.
ragge
1.76
401  */
402 static int
ragge
1.82
403 trivially_colorable_p(int cint *n)
ragge
1.76
404 {
ragge
1.85
405         int r[NUMCLASS+1];
ragge
1.78
406         int i;
407
ragge
1.85
408         for (i = 1i < NUMCLASS+1i++)
ragge
1.78
409                 r[i] = n[i] < regK[i] ? n[i] : regK[i];
410
ragge
1.87
411 #if 0
412         /* add the exclusion nodes. */
413         /* XXX can we do someything smart here? */
414         /* worst-case for exclusion nodes are better than the `worst-case' */
415         for (; exclexcl >>= 1)
416                 if (excl & 1)
417                         r[c]++;
418 #endif
ragge
1.85
419
ragge
1.82
420         i = COLORMAP(cr);
gmcgarry
1.163
421         if (i < 0 || i > 1)
422                 comperr("trivially_colorable_p");
plunky
1.228
423         RRDEBUG(("trivially_colorable_p: n[1] %d n[2] %d n[3] %d n[4] "
424             "%d for class %d, triv %d\n"n[1], n[2], n[3], n[4], ci));
ragge
1.82
425         return i;
ragge
1.76
426 }
427
ragge
1.222
428 int
ragge
1.97
429 ncnt(int needs)
430 {
431         int i = 0;
432
433         while (needs & NACOUNT)
434                 needs -= NAREGi++;
435         while (needs & NBCOUNT)
436                 needs -= NBREGi++;
437         while (needs & NCCOUNT)
438                 needs -= NCREGi++;
439         while (needs & NDCOUNT)
440                 needs -= NDREGi++;
ragge
1.191
441         while (needs & NECOUNT)
442                 needs -= NEREGi++;
443         while (needs & NFCOUNT)
444                 needs -= NFREGi++;
445         while (needs & NGCOUNT)
446                 needs -= NGREGi++;
ragge
1.97
447         return i;
448 }
449
gmcgarry
1.177
450 static REGW *
ragge
1.48
451 popwlist(REGW *l)
452 {
453         REGW *w = DLIST_NEXT(llink);
454
455         DLIST_REMOVE(wlink);
ragge
1.49
456         w->r_onlist = NULL;
ragge
1.48
457         return w;
458 }
ragge
1.46
459
ragge
1.42
460 /*
ragge
1.46
461  * Move lists, a move node is always on only one list.
ragge
1.40
462  */
ragge
1.48
463 static REGM coalescedMovesconstrainedMovesfrozenMoves
464         worklistMovesactiveMoves;
ragge
1.46
465 enum { COALCONSTRFROZENWLISTACTIVE };
466
gmcgarry
1.177
467 static REGM *
ragge
1.48
468 popmlist(REGM *l)
469 {
470         REGM *w = DLIST_NEXT(llink);
471
472         DLIST_REMOVE(wlink);
473         return w;
474 }
475
ragge
1.63
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
gmcgarry
1.177
485  * and killed variables. Therefore, for a temp number, the bit number must
ragge
1.63
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
493 static void
494 LIVEADD(int x)
495 {
496         RDEBUG(("Liveadd: %d\n"x));
ragge
1.161
497         if (x >= MAXREGS && (x < tempmin || x >= tempmax))
ragge
1.63
498                 comperr("LIVEADD: out of range");
ragge
1.161
499         if (x < MAXREGS) {
500                 BITSET(livex);
501         } else
502                 BITSET(live, (x-tempmin+MAXREGS));
ragge
1.63
503 }
ragge
1.161
504
ragge
1.63
505 static void
506 LIVEDEL(int x)
507 {
508         RDEBUG(("Livedel: %d\n"x));
ragge
1.161
509
510         if (x >= MAXREGS && (x < tempmin || x >= tempmax))
ragge
1.63
511                 comperr("LIVEDEL: out of range");
ragge
1.161
512         if (x < MAXREGS) {
513                 BITCLEAR(livex);
514         } else
515                 BITCLEAR(live, (x-tempmin+MAXREGS));
ragge
1.63
516 }
517 #else
ragge
1.161
518 #define LIVEADD(x) \
519         (x >= MAXREGS ? BITSET(live, (x-tempmin+MAXREGS)) : BITSET(livex))
520 #define LIVEDEL(x) \
521         (x >= MAXREGS ? BITCLEAR(live, (x-tempmin+MAXREGS)) : BITCLEAR(livex))
ragge
1.63
522 #endif
ragge
1.46
523
ragge
1.83
524 static struct lives {
525         DLIST_ENTRY(liveslink;
526         REGW *var;
527 lusedlunused;
528
ragge
1.79
529 static void
530 LIVEADDR(REGW *x)
531 {
ragge
1.83
532         struct lives *l;
533
534 #ifdef PCC_DEBUG
ragge
1.85
535         RDEBUG(("LIVEADDR: %d\n"x->nodnum));
ragge
1.83
536         DLIST_FOREACH(l, &lusedlink)
537                 if (l->var == x)
ragge
1.90
538                         return;
gmcgarry
1.200
539 #if 0
540                         comperr("LIVEADDR: multiple %d"ASGNUM(x));
541 #endif
ragge
1.83
542 #endif
543         if (!DLIST_ISEMPTY(&lunusedlink)) {
544                 l = DLIST_NEXT(&lunusedlink);
545                 DLIST_REMOVE(llink);
546         } else
547                 l = tmpalloc(sizeof(struct lives));
548
549         l->var = x;
550         DLIST_INSERT_AFTER(&lusedllink);
ragge
1.79
551 }
552
553 static void
554 LIVEDELR(REGW *x)
555 {
ragge
1.83
556         struct lives *l;
557
gmcgarry
1.171
558 #ifdef PCC_DEBUG
ragge
1.85
559         RDEBUG(("LIVEDELR: %d\n"x->nodnum));
gmcgarry
1.171
560 #endif
ragge
1.83
561         DLIST_FOREACH(l, &lusedlink) {
562                 if (l->var != x)
563                         continue;
564                 DLIST_REMOVE(llink);
565                 DLIST_INSERT_AFTER(&lunusedllink);
566                 return;
567         }
gmcgarry
1.200
568 #if 0
569         comperr("LIVEDELR: %p not found"x);
570 #endif
ragge
1.79
571 }
572
ragge
1.46
573 #define MOVELISTADD(t, p) movelistadd(t, p)
ragge
1.49
574 #define WORKLISTMOVEADD(s,d) worklistmoveadd(s,d)
ragge
1.46
575
576 static void
ragge
1.79
577 movelistadd(REGW *tREGM *p)
ragge
1.46
578 {
579         MOVL *w = tmpalloc(sizeof(MOVL));
580
581         w->regm = p;
ragge
1.79
582         w->next = t->r_moveList;
583         t->r_moveList = w;
ragge
1.46
584 }
585
586 static REGM *
ragge
1.79
587 worklistmoveadd(REGW *srcREGW *dst)
ragge
1.46
588 {
589         REGM *w = tmpalloc(sizeof(REGM));
590
ragge
1.48
591         DLIST_INSERT_AFTER(&worklistMoveswlink);
ragge
1.49
592         w->src = src;
593         w->dst = dst;
ragge
1.46
594         w->queue = WLIST;
595         return w;
596 }
597
ragge
1.195
598 #define HASHSZ  16384
ragge
1.46
599 struct AdjSet {
600         struct AdjSet *next;
ragge
1.79
601         REGW *u, *v;
ragge
1.195
602 } *edgehash[HASHSZ];
ragge
1.46
603
604 /* Check if a node pair is adjacent */
605 static int
ragge
1.79
606 adjSet(REGW *uREGW *v)
ragge
1.46
607 {
608         struct AdjSet *w;
ragge
1.219
609         REGW *t;
ragge
1.218
610
ragge
1.103
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 (; aa = a->r_next) {
618                         if (ONLIST(a->a_temp) != &precolored)
619                                 continue;
620                         t = a->a_temp;
621                         if (interferes(t - ablocku - ablock))
622                                 return 1;
623                 }
624         }
ragge
1.218
625
ragge
1.211
626         w = edgehash[(u->nodnum+v->nodnum)& (HASHSZ-1)];
ragge
1.219
627
ragge
1.46
628         for (; ww = w->next) {
ragge
1.211
629                 if ((u == w->u && v == w->v) || (u == w->v && v == w->u))
ragge
1.46
630                         return 1;
631         }
632         return 0;
633 }
634
635 /* Add a pair to adjset.  No check for dups */
ragge
1.219
636 static int
ragge
1.79
637 adjSetadd(REGW *uREGW *v)
ragge
1.46
638 {
639         struct AdjSet *w;
ragge
1.79
640         int x;
ragge
1.46
641
ragge
1.211
642         x = (u->nodnum+v->nodnum)& (HASHSZ-1);
ragge
1.219
643         for (w = edgehash[x]; ww = w->next)
644                 if ((u == w->u && v == w->v) || (u == w->v && v == w->u))
645                         return 1;
646
ragge
1.46
647         w = tmpalloc(sizeof(struct AdjSet));
648         w->u = uw->v = v;
ragge
1.79
649         w->next = edgehash[x];
650         edgehash[x] = w;
ragge
1.219
651         return 0;
ragge
1.46
652 }
653
654 /*
655  * Add an interference edge between two nodes.
656  */
657 static void
ragge
1.79
658 AddEdge(REGW *uREGW *v)
ragge
1.46
659 {
ragge
1.47
660         ADJL *x;
661
gmcgarry
1.171
662 #ifdef PCC_DEBUG
ragge
1.103
663         RRDEBUG(("AddEdge: u %d v %d\n"ASGNUM(u), ASGNUM(v)));
ragge
1.88
664
665 #if 0
ragge
1.85
666         if (ASGNUM(u) == 0)
667                 comperr("AddEdge 0");
ragge
1.88
668 #endif
ragge
1.85
669         if (CLASS(u) == 0 || CLASS(v) == 0)
ragge
1.96
670                 comperr("AddEdge class == 0 (%d=%d, %d=%d)",
671                     CLASS(u), ASGNUM(u), CLASS(v), ASGNUM(v));
ragge
1.79
672 #endif
ragge
1.46
673
674         if (u == v)
675                 return;
ragge
1.219
676         if (adjSetadd(uv))
ragge
1.46
677                 return;
678
ragge
1.87
679 #if 0
680         if (ONLIST(u) == &precolored || ONLIST(v) == &precolored)
ragge
1.78
681                 comperr("precolored node in AddEdge");
682 #endif
ragge
1.79
683
ragge
1.87
684         if (ONLIST(u) != &precolored) {
685                 x = tmpalloc(sizeof(ADJL));
686                 x->a_temp = v;
687                 x->r_next = u->r_adjList;
688                 u->r_adjList = x;
689                 NCLASS(uCLASS(v))++;
690         }
ragge
1.79
691
ragge
1.87
692         if (ONLIST(v) != &precolored) {
693                 x = tmpalloc(sizeof(ADJL));
694                 x->a_temp = u;
695                 x->r_next = v->r_adjList;
696                 v->r_adjList = x;
697                 NCLASS(vCLASS(u))++;
698         }
ragge
1.88
699
ragge
1.110
700 #if 0
ragge
1.73
701         RDEBUG(("AddEdge: u %d(d %d) v %d(d %d)\n"uDEGREE(u), vDEGREE(v)));
ragge
1.76
702 #endif
ragge
1.46
703 }
704
705 static int
ragge
1.79
706 MoveRelated(REGW *n)
ragge
1.46
707 {
708         MOVL *l;
709         REGM *w;
710
ragge
1.49
711         for (l = MOVELIST(n); ll = l->next) {
ragge
1.46
712                 w = l->regm;
713                 if (w->queue == ACTIVE || w->queue == WLIST)
714                         return 1;
715         }
716         return 0;
717 }
718
719 static void
720 MkWorklist(void)
721 {
722         REGW *w;
ragge
1.87
723
gmcgarry
1.200
724         RDEBUGX(int s=0);
725         RDEBUGX(int f=0);
726         RDEBUGX(int d=0);
ragge
1.46
727
ragge
1.48
728         DLIST_INIT(&precoloredlink);
729         DLIST_INIT(&simplifyWorklistlink);
730         DLIST_INIT(&freezeWorklistlink);
731         DLIST_INIT(&spillWorklistlink);
732         DLIST_INIT(&spilledNodeslink);
733         DLIST_INIT(&coalescedNodeslink);
734         DLIST_INIT(&coloredNodeslink);
735         DLIST_INIT(&selectStacklink);
ragge
1.87
736
737         /*
738          * Remove all nodes from the initial list and put them on 
739          * one of the worklists.
740          */
ragge
1.79
741         while (!DLIST_ISEMPTY(&initiallink)) {
742                 w = DLIST_NEXT(&initiallink);
743                 DLIST_REMOVE(wlink);
744                 if (!trivially_colorable(w)) {
ragge
1.46
745                         PUSHWLIST(wspillWorklist);
gmcgarry
1.200
746                         RDEBUGX(s++);
ragge
1.79
747                 } else if (MoveRelated(w)) {
ragge
1.46
748                         PUSHWLIST(wfreezeWorklist);
gmcgarry
1.200
749                         RDEBUGX(f++);
ragge
1.46
750                 } else {
751                         PUSHWLIST(wsimplifyWorklist);
gmcgarry
1.200
752                         RDEBUGX(d++);
ragge
1.46
753                 }
754         }
ragge
1.68
755         RDEBUG(("MkWorklist: spill %d freeze %d simplify %d\n"s,f,d));
ragge
1.46
756 }
757
ragge
1.48
758 static void
ragge
1.79
759 addalledges(REGW *e)
ragge
1.48
760 {
761         int ijk;
ragge
1.83
762         struct lives *l;
ragge
1.48
763
gmcgarry
1.171
764 #ifdef PCC_DEBUG
ragge
1.85
765         RDEBUG(("addalledges for %d\n"e->nodnum));
gmcgarry
1.171
766 #endif
ragge
1.88
767
ragge
1.108
768         if (e->r_class == -1)
769                 return/* unused */
ragge
1.138
770
ragge
1.98
771         if (ONLIST(e) != &precolored) {
ragge
1.99
772                 for (i = 0ndontregs[i] >= 0i++)
773                         AddEdge(e, &ablock[ndontregs[i]]);
ragge
1.98
774         }
ragge
1.88
775
ragge
1.161
776         /* First add to long-lived temps and hard regs */
ragge
1.103
777         RDEBUG(("addalledges longlived "));
ragge
1.161
778         for (i = 0i < xbitsi += NUMBITS) {
ragge
1.203
779                 if ((k = live[i/NUMBITS])) {
780                         while (k) {
781                                 j = ffs(k)-1;
782                                 if (i+j < MAXREGS)
783                                         AddEdge(&ablock[i+j], e);
784                                 else
785                                         AddEdge(&nblock[i+j+tempmin-MAXREGS],e);
786                                 RRDEBUG(("%d "i+j+tempmin));
787                                 k &= ~(1 << j);
788                         }
ragge
1.48
789                 }
ragge
1.202
790 #if NUMBITS > 32 /* XXX hack for LP64 */
791                 k = (live[i/NUMBITS] >> 32);
792                 while (k) {
793                         j = ffs(k)-1;
794                         if (i+j+32 < MAXREGS)
795                                 AddEdge(&ablock[i+j+32], e);
796                         else
797                                 AddEdge(&nblock[i+j+tempmin-MAXREGS+32], e);
798                         RRDEBUG(("%d "i+j+tempmin+32));
799                         k &= ~(1 << j);
800                 }
801 #endif
ragge
1.48
802         }
ragge
1.103
803         RDEBUG(("done\n"));
ragge
1.83
804         /* short-lived temps */
ragge
1.103
805         RDEBUG(("addalledges shortlived "));
806         DLIST_FOREACH(l, &lusedlink) {
gmcgarry
1.171
807 #ifdef PCC_DEBUG
ragge
1.103
808                 RRDEBUG(("%d "ASGNUM(l->var)));
gmcgarry
1.171
809 #endif
ragge
1.103
810                 AddEdge(l->vare);
811         }
812         RDEBUG(("done\n"));
ragge
1.78
813 }
814
ragge
1.128
815 /*
816  * Add a move edge between def and use.
817  */
ragge
1.49
818 static void
ragge
1.79
819 moveadd(REGW *defREGW *use)
ragge
1.49
820 {
821         REGM *r;
ragge
1.208
822         MOVL *w;
ragge
1.49
823
ragge
1.68
824         if (def == use)
825                 return/* no move to itself XXX - ``shouldn't happen'' */
gmcgarry
1.171
826 #ifdef PCC_DEBUG
ragge
1.84
827         RDEBUG(("moveadd: def %d use %d\n"ASGNUM(def), ASGNUM(use)));
gmcgarry
1.171
828 #endif
ragge
1.49
829
ragge
1.208
830         /*
831          * Check if we are already on move list.
832          * XXX How can that happen ???
833          */
834         for (w = MOVELIST(def); ww = w->next) {
835                 if ((w->regm->src == def && w->regm->dst == use) ||
836                     (w->regm->src == use && w->regm->dst == def))
837                         return/* already there XXX reverse? */
838         }
839
ragge
1.49
840         r = WORKLISTMOVEADD(usedef);
841         MOVELISTADD(defr);
842         MOVELISTADD(user);
843 }
844
ragge
1.128
845 /*
846  * Traverse arguments backwards.
847  * XXX - can this be tricked in some other way?
848  */
849 static void
850 argswalk(NODE *p)
851 {
852
853         if (p->n_op == CM) {
854                 argswalk(p->n_left);
855                 insnwalk(p->n_right);
856         } else
857                 insnwalk(p);
858 }
859
ragge
1.129
860 /*
861  * Add to (or remove from) live set variables that must not
862  * be clobbered when traversing down on the other leg for 
863  * a BITYPE node.
864  */
865 static void
866 setlive(NODE *pint setREGW *rv)
867 {
ragge
1.151
868         if (rv != NULL) {
ragge
1.189
869                 if (rv->nodnum < MAXREGS &&
870                     TESTBIT(validregsrv->nodnum) == 0)
871                         return;
ragge
1.151
872                 set ? LIVEADDR(rv) : LIVEDELR(rv);
873                 return;
874         }
ragge
1.129
875
ragge
1.151
876         if (p->n_regw != NULL) {
ragge
1.189
877                 if (p->n_regw->nodnum < MAXREGS &&
878                     TESTBIT(validregsp->n_regw->nodnum) == 0)
879                         return;
ragge
1.151
880                 set ? LIVEADDR(p->n_regw) : LIVEDELR(p->n_regw);
881                 return;
882         }
ragge
1.129
883
884         switch (optype(p->n_op)) {
885         case LTYPE:
ragge
1.189
886                 if (p->n_op == TEMP || VALIDREG(p))
ragge
1.167
887                         set ? LIVEADD(regno(p)) : LIVEDEL(regno(p));
ragge
1.129
888                 break;
889         case BITYPE:
890                 setlive(p->n_rightsetrv);
891                 /* FALLTHROUGH */
892         case UTYPE:
893                 setlive(p->n_leftsetrv);
894                 break;
895         }
896 }
ragge
1.128
897
ragge
1.133
898 /*
ragge
1.134
899  * Add edges for temporary w against all temporaries that may be
900  * used simultaneously (like index registers).
901  */
902 static void
903 addedge_r(NODE *pREGW *w)
904 {
ragge
1.170
905         RRDEBUG(("addedge_r: node %p regw %p\n"pw));
906
ragge
1.151
907         if (p->n_regw != NULL) {
ragge
1.189
908                 if (p->n_regw->nodnum < MAXREGS &&
909                     TESTBIT(validregsp->n_regw->nodnum) == 0)
910                         return;
ragge
1.151
911                 AddEdge(p->n_regww);