Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20081116133016

Diff

Diff from 1.193 to:

Annotations

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

Annotated File View

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