Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20080622152459

Diff

Diff from 1.178 to:

Annotations

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

Annotated File View

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