Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:gmcgarry:20080415095232

Diff

Diff from 1.171 to:

Annotations

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

Annotated File View

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