Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20140817154134

Diff

Diff from 1.244 to:

Annotations

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

Annotated File View

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