Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050917075840

Diff

Diff from 1.75 to:

Annotations

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

Annotated File View

ragge
1.75
1 /*      $Id: regs.c,v 1.75 2005/09/17 07:58:40 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.37
30 #include <strings.h>
ragge
1.62
31 #include <stdlib.h>
ragge
1.1
32
ragge
1.74
33 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
34  
ragge
1.42
35 /*
36  * New-style register allocator using graph coloring.
ragge
1.46
37  * The design is based on the George and Appel paper
38  * "Iterated Register Coalescing", ACM Transactions, No 3, May 1996.
ragge
1.42
39  */
40
ragge
1.63
41 #define BIT2BYTE(bits) ((((bits)+NUMBITS-1)/NUMBITS)*(NUMBITS/8))
ragge
1.59
42 #define BITALLOC(ptr,all,sz) { \
ragge
1.63
43         int __s = BIT2BYTE(sz); ptr = all(__s); memset(ptr0__s); }
ragge
1.59
44
ragge
1.61
45 int tempmintempfetempmax;
ragge
1.40
46 /*
47  * Count the number of registers needed to evaluate a tree.
48  * This is only done to find the evaluation order of the tree.
ragge
1.42
49  * While here, assign temp numbers to the registers that will
50  * be needed when the tree is evaluated.
ragge
1.46
51  *
52  * While traversing the tree, assign temp numbers to the registers
53  * used by all instructions:
54  *      - n_rall is always set to the outgoing number. If the
55  *        instruction is 2-op (addl r0,r1) then an implicit move
56  *        is inserted just before the left (clobbered) operand.
57  *      - if the instruction has needs then temporaries of size 
58  *        szty() are assumed above the n_rall number.
ragge
1.40
59  */
60 int
61 nsucomp(NODE *p)
62 {
ragge
1.63
63         struct optab *q;
ragge
1.40
64         int leftright;
65         int nregneed;
66
67         if (p->n_su == -1)
68                 return nsucomp(p->n_left);
69    
ragge
1.63
70         q = &table[TBLIDX(p->n_su)];
ragge
1.40
71         nreg = (q->needs & NACOUNT) * szty(p->n_type); /* XXX BREGs */
72         if (callop(p->n_op))
73                 nreg = MAX(fregsnreg);
74
75         switch (p->n_su & RMASK) {
76         case RREG:
ragge
1.63
77                 if (p->n_right->n_op == TEMP && (q->rewrite & RRIGHT) == 0) {
78                         /* only read argument */
79                         p->n_right->n_rall = p->n_right->n_lval;
80                         right = 0;
81                         break;
82                 }
83                 /* FALLTHROUGH */
ragge
1.40
84         case ROREG:
85                 right = nsucomp(p->n_right);
86                 break;
87         case RTEMP
88                 cerror("sucomp RTEMP");
89         default:
90                 right = 0;
91         }
92         switch (p->n_su & LMASK) {
93         case LREG:
ragge
1.63
94                 if (p->n_left->n_op == TEMP && (q->rewrite & RLEFT) == 0) {
95                         /* only read argument */
96                         p->n_left->n_rall = p->n_left->n_lval;
97                         left = 0;
98                         break;
99                 }
100                 /* FALLTHROUGH */
ragge
1.40
101         case LOREG:
102                 left = nsucomp(p->n_left);
103                 break;  
104         case LTEMP:
105                 cerror("sucomp LTEMP");
106         default:
107                 left = 0
108         }
109
110         if ((p->n_su & RMASK) && (p->n_su & LMASK)) {
111                 /* Two children */
112                 if (right == left)
113                         need = left + MAX(nreg1);
114                 else
115                         need = MAX(rightleft);
116                 /* XXX - should take care of overlapping needs */
ragge
1.54
117                 if (right > left) {
ragge
1.40
118                         p->n_su |= DORIGHT;
ragge
1.54
119                 } else if (right == left) {
120                         /* A favor to 2-operand architectures */
ragge
1.57
121                         if ((q->rewrite & RRIGHT) == 0)
ragge
1.54
122                                 p->n_su |= DORIGHT;
123                 }
ragge
1.40
124         } else if ((p->n_su & RMASK) || (p->n_su & LMASK)) {
125                 /* One child */
126                 need = MAX(rightleft) + nreg;
127         } else
128                 need = nreg;
ragge
1.74
129         p->n_rall = tempmax;
130         tempmax += szty(p->n_type);
ragge
1.56
131         if (!callop(p->n_op) && !(q->needs & NSPECIAL))
132                 tempmax += nreg;
ragge
1.40
133         return nreg;
134 }
135
ragge
1.41
136 /*
ragge
1.47
137  * Data structure overview for this implementation:
138  *
139  * Each temporary (called "node") is described by the type REGW.  
140  * Space for all nodes is allocated initially as an array, so 
141  * the nodes can be can be referenced both by the node number and
142  * by pointer.
143  * 
ragge
1.48
144  * All moves are represented by the type REGM, allocated when needed. 
ragge
1.47
145  *
ragge
1.48
146  * The "live" set used during graph building is represented by a bitset.
ragge
1.47
147  *
148  * Interference edges are represented by struct AdjSet, hashed and linked
ragge
1.48
149  * from index into the edgehash array.
ragge
1.47
150  *
151  * A mapping from each node to the moves it is assiciated with is 
152  * maintained by an array moveList which for each node number has a linked
153  * list of MOVL types, each pointing to a REGM.
154  *
155  * Adjacency list is maintained by the adjList array, indexed by the
156  * node number. Each adjList entry points to an ADJL type, and is a
157  * single-linked list for all adjacent nodes.
158  *
159  * degree, alias and color are integer arrays indexed by node number.
ragge
1.42
160  */
ragge
1.46
161
162 /*
ragge
1.49
163  * linked list of adjacent nodes.
ragge
1.46
164  */
ragge
1.47
165 typedef struct regw3 {
166         struct regw3 *r_next;
ragge
1.49
167         int a_temp;
ragge
1.47
168 ADJL;
169
ragge
1.46
170 /*
171  * Structure describing a move.
172  */
173 typedef struct regm {
ragge
1.48
174         DLIST_ENTRY(regmlink;
ragge
1.49
175         int srcdst;
ragge
1.46
176         int queue;
177 REGM;
178
179 typedef struct movlink {
180         struct movlink *next;
181         REGM *regm;
182 MOVL;
183
ragge
1.49
184 /*
185  * Structure describing a temporary.
186  */
187 typedef struct regw {
188         DLIST_ENTRY(regwlink;
189         int r_alias;            /* number of aliased register */
190         ADJL *r_adjList;        /* linked list of adjacent nodes */
191         int r_degree;           /* degree of this node */
192         int r_color;            /* final node color */
193         struct regw *r_onlist;  /* which work list this node belongs to */
194         MOVL *r_moveList;       /* moves associated with this node */
195 REGW;
196
ragge
1.47
197 #define RDEBUG(x)       if (rdebug) printf x
ragge
1.68
198 #define RDX(x)          x
ragge
1.47
199
ragge
1.52
200 static int maxregs;     /* max usable regs for allocator */
201 static int allregs;     /* bitmask of usable regs */
ragge
1.46
202 static REGW *nodeblock;
ragge
1.49
203 #define ALIAS(x)        nodeblock[x].r_alias
204 #define ADJLIST(x)      nodeblock[x].r_adjList
205 #define DEGREE(x)       nodeblock[x].r_degree
206 #define COLOR(x)        nodeblock[x].r_color
207 #define ONLIST(x)       nodeblock[x].r_onlist
208 #define MOVELIST(x)     nodeblock[x].r_moveList
209 #define R_TEMP(w)       (w - nodeblock)
ragge
1.46
210
ragge
1.47
211 static bittype *live;
ragge
1.46
212
ragge
1.49
213 #define PUSHWLIST(w, l) DLIST_INSERT_AFTER(&l, w, link); w->r_onlist = &l
ragge
1.48
214 #define POPWLIST(l)     popwlist(&l);
215 #define DELWLIST(w)     DLIST_REMOVE(w, link)
216 #define WLISTEMPTY(h)   DLIST_ISEMPTY(&h,link)
217 #define PUSHMLIST(w, l, q)      DLIST_INSERT_AFTER(&l, w, link); w->queue = q
218 #define POPMLIST(l)     popmlist(&l);
ragge
1.46
219
220 /*
221  * Worklists, a node is always on exactly one of these lists.
222  */
ragge
1.48
223 static REGW precoloredsimplifyWorklistfreezeWorklistspillWorklist,
224         spilledNodescoalescedNodescoloredNodesselectStack;
225
226 static inline REGW *
227 popwlist(REGW *l)
228 {
229         REGW *w = DLIST_NEXT(llink);
230
231         DLIST_REMOVE(wlink);
ragge
1.49
232         w->r_onlist = NULL;
ragge
1.48
233         return w;
234 }
ragge
1.46
235
ragge
1.42
236 /*
ragge
1.46
237  * Move lists, a move node is always on only one list.
ragge
1.40
238  */
ragge
1.48
239 static REGM coalescedMovesconstrainedMovesfrozenMoves
240         worklistMovesactiveMoves;
ragge
1.46
241 enum { COALCONSTRFROZENWLISTACTIVE };
242
ragge
1.48
243 static inline REGM *
244 popmlist(REGM *l)
245 {
246         REGM *w = DLIST_NEXT(llink);
247
248         DLIST_REMOVE(wlink);
249         return w;
250 }
251
ragge
1.49
252 #define REGUALL(r, n)   r = &nodeblock[n]
ragge
1.74
253 #define GETP(p)         ((p)->n_su == -1 ? getp(p) : p)
254 #define GETRALL(p)      (GETP(p)->n_rall)
ragge
1.46
255
ragge
1.74
256 static NODE *
257 getp(NODE *p)
ragge
1.46
258 {
259         while (p->n_su == -1)
260                 p = p->n_left;
ragge
1.74
261         return p;
ragge
1.46
262 }
263
ragge
1.63
264 /*
265  * About data structures used in liveness analysis:
266  *
267  * The temporaries generated in pass1 are numbered between tempmin and
268  * tempmax.  Temporaries generated in pass2 are numbered above tempmax,
269  * so they are sequentially numbered.
270  *
271  * Bitfields are used for liveness.  Bit arrays are allocated on the
272  * heap for the "live" variable and on the stack for the in, out, gen
273  * and kill variables. Therefore, for a temp number, the bit number must
274  * be biased with tempmin.
275  *
276  * There may be an idea to use a different data structure to store 
277  * pass2 allocated temporaries, because they are very sparse.
278  */
279
280 #ifdef PCC_DEBUG
281 static void
282 LIVEADD(int x)
283 {
284         RDEBUG(("Liveadd: %d\n"x));
285         if (x < tempmin || x >= tempmax)
286                 comperr("LIVEADD: out of range");
287         BITSET(live, (x-tempmin));
288 }
289 static void
290 LIVEDEL(int x)
291 {
292         RDEBUG(("Livedel: %d\n"x));
293         if (x < tempmin || x >= tempmax)
294                 comperr("LIVEDEL: out of range");
295         BITCLEAR(live, (x-tempmin));
296 }
297 #else
ragge
1.64
298 #define LIVEADD(x) BITSET(live, (x-tempmin))
299 #define LIVEDEL(x) BITCLEAR(live, (x-tempmin))
ragge
1.63
300 #endif
ragge
1.46
301
302 #define MOVELISTADD(t, p) movelistadd(t, p)
ragge
1.49
303 #define WORKLISTMOVEADD(s,d) worklistmoveadd(s,d)
ragge
1.46
304
305 static void
306 movelistadd(int tREGM *p)
307 {
308         MOVL *w = tmpalloc(sizeof(MOVL));
309
310         w->regm = p;
ragge
1.49
311         w->next = MOVELIST(t);
312         MOVELIST(t) = w;
ragge
1.46
313 }
314
315 static REGM *
ragge
1.49
316 worklistmoveadd(int srcint dst)
ragge
1.46
317 {
318         REGM *w = tmpalloc(sizeof(REGM));
319
ragge
1.48
320         DLIST_INSERT_AFTER(&worklistMoveswlink);
ragge
1.49
321         w->src = src;
322         w->dst = dst;
ragge
1.46
323         w->queue = WLIST;
324         return w;
325 }
326
327 struct AdjSet {
328         struct AdjSet *next;
329         int uv;
330 } *edgehash[256];
331
332 /* Check if a node pair is adjacent */
333 static int
334 adjSet(int uint v)
335 {
336         struct AdjSet *w;
337         int t;
338
339         if (u > v)
340                 t = vv = uu = t;
341         w = edgehash[(u+v) & 255];
342         for (; ww = w->next) {
343                 if (u == w->u && v == w->v)
344                         return 1;
345         }
346         return 0;
347 }
348
349 /* Add a pair to adjset.  No check for dups */
350 static void
351 adjSetadd(int uint v)
352 {
353         struct AdjSet *w;
354         int t;
355
356         if (u > v)
357                 t = vv = uu = t;
358         t = (u+v) & 255;
359         w = tmpalloc(sizeof(struct AdjSet));
360         w->u = uw->v = v;
361         w->next = edgehash[t];
362         edgehash[t] = w;
363 }
364
365 /*
366  * Add an interference edge between two nodes.
367  */
368 static void
369 AddEdge(int uint v)
370 {
ragge
1.47
371         ADJL *x;
372
373         RDEBUG(("AddEdge: u %d v %d\n"uv));
ragge
1.46
374
375         if (u == v)
376                 return;
377         if (adjSet(uv))
378                 return;
379
380         adjSetadd(uv);
381
ragge
1.48
382         if (u >= tempmin) {
ragge
1.47
383                 x = tmpalloc(sizeof(ADJL));
ragge
1.49
384                 x->a_temp = v;
385                 x->r_next = ADJLIST(u);
386                 ADJLIST(u) = x;
387                 DEGREE(u)++;
ragge
1.46
388         }
ragge
1.49
389         if (v >= tempmin) {
ragge
1.47
390                 x = tmpalloc(sizeof(ADJL));
ragge
1.49
391                 x->a_temp = u;
392                 x->r_next = ADJLIST(v);
393                 ADJLIST(v) = x;
394                 DEGREE(v)++;
ragge
1.46
395         }
ragge
1.73
396         RDEBUG(("AddEdge: u %d(d %d) v %d(d %d)\n"uDEGREE(u), vDEGREE(v)));
ragge
1.46
397 }
398
399 static int
400 MoveRelated(int n)
401 {
402         MOVL *l;
403         REGM *w;
404
ragge
1.49
405         for (l = MOVELIST(n); ll = l->next) {
ragge
1.46
406                 w = l->regm;
407                 if (w->queue == ACTIVE || w->queue == WLIST)
408                         return 1;
409         }
410         return 0;
411 }
412
413 static void
414 MkWorklist(void)
415 {
416         REGW *w;
417         int n;
ragge
1.68
418         RDX(int s=0);
419         RDX(int f=0);
420         RDX(int d=0);
ragge
1.46
421
ragge
1.48
422         DLIST_INIT(&precoloredlink);
423         DLIST_INIT(&simplifyWorklistlink);
424         DLIST_INIT(&freezeWorklistlink);
425         DLIST_INIT(&spillWorklistlink);
426         DLIST_INIT(&spilledNodeslink);
427         DLIST_INIT(&coalescedNodeslink);
428         DLIST_INIT(&coloredNodeslink);
429         DLIST_INIT(&selectStacklink);
ragge
1.46
430         for (n = tempminn < tempmaxn++) {
431                 REGUALL(wn);
ragge
1.52
432                 if (DEGREE(n) >= maxregs) {
ragge
1.46
433                         PUSHWLIST(wspillWorklist);
ragge
1.68
434                         RDX(s++);
ragge
1.46
435                 } else if (MoveRelated(n)) {
436                         PUSHWLIST(wfreezeWorklist);
ragge
1.68
437                         RDX(f++);
ragge
1.46
438                 } else {
439                         PUSHWLIST(wsimplifyWorklist);
ragge
1.68
440                         RDX(d++);
ragge
1.46
441                 }
442         }
ragge
1.68
443         RDEBUG(("MkWorklist: spill %d freeze %d simplify %d\n"s,f,d));
ragge
1.46
444 }
445
ragge
1.48
446 static void
447 addalledges(int e)
448 {
449         int ijk;
ragge
1.64
450         int nbits = tempmax - tempmin;
ragge
1.48
451
ragge
1.64
452         for (i = 0i < nbitsi += NUMBITS) {
ragge
1.48
453                 if ((k = live[i/NUMBITS]) == 0)
454                         continue;
455                 while (k) {
456                         j = ffs(k)-1;
ragge
1.63
457                         AddEdge(i+j+tempmine);
ragge
1.48
458                         k &= ~(1 << j);
459                 }
460         }
461 }
462
ragge
1.49
463 static void
ragge
1.50
464 moveadd(int defint use)
ragge
1.49
465 {
466         REGM *r;
467
ragge
1.68
468         if (def == use)
469                 return/* no move to itself XXX - ``shouldn't happen'' */
ragge
1.50
470         RDEBUG(("moveadd: def %d use %d\n"defuse));
ragge
1.49
471
472         r = WORKLISTMOVEADD(usedef);
473         MOVELISTADD(defr);
474         MOVELISTADD(user);
475         addalledges(def);
476 }
477
ragge
1.50
478 /*
479  * Do the actual liveness analysis inside a tree.
ragge
1.55
480  * The tree is walked in backward-execution order to catch the 
ragge
1.50
481  * long-term temporaries.
482  * Moves to/from precolored registers are implicitly placed
483  * inside the affected nodes (like return value from CALLs).
484  */
ragge
1.49
485 static void
486 insnwalk(NODE *p)
487 {
ragge
1.62
488         struct optab *q;
ragge
1.49
489         int defnreg;
ragge
1.74
490         int ilrftsize;
ragge
1.75
491         int *left, *right, *rmask;
ragge
1.49
492
493         RDEBUG(("insnwalk: %p\n"p));
494
ragge
1.62
495         if (p->n_su == -1)
496                 return insnwalk(p->n_left);
497
498         q = &table[TBLIDX(p->n_su)];
499
ragge
1.74
500         size = szty(p->n_type); /* outgoing count of regs used */
501 #define SZLOOP(i) for (i = 0; i < size; i++)
502 #define SZSLOOP(i,s) for (i = 0; i < szty(s); i++)
ragge
1.63
503         if (p->n_op == ASSIGN) {
504                 if (p->n_left->n_op == TEMP) {
ragge
1.75
505                         /* Remove from live set */
506                         LIVEDEL((int)p->n_left->n_lval);
507                         /* always move via itself */
508                         moveadd((int)p->n_left->n_lvalp->n_rall);
ragge
1.74
509                                 
ragge
1.63
510                 }
511                 if (((l = p->n_left->n_op) == TEMP || l == REG) &&
512                     ((r = p->n_right->n_op) == TEMP || r == REG)) {
513                         f = r == REG ? p->n_right->n_rval : p->n_right->n_lval;
514                         t = l == REG ? p->n_left->n_rval : p->n_left->n_lval;
ragge
1.75
515                         moveadd(tf);
ragge
1.63
516                 }
517         }
ragge
1.49
518         def = p->n_rall;
ragge
1.75
519         addalledges(def);
ragge
1.74
520         nreg = (q->needs & NACOUNT) * size;
521         for (i = 0i < nregi++)
522                 MYADDEDGE(i+defp->n_type); /* register constraints */
ragge
1.56
523
ragge
1.75
524         left = right = 0;
525         rmask = 0;
ragge
1.55
526         if (q->needs & NSPECIAL) {
ragge
1.75
527                 struct rspecial *rs = nspecial(q);
ragge
1.56
528                 /* special instruction requirements */
529
530
ragge
1.55
531                 /* if result ends up in a certain register, add move */
ragge
1.75
532                 if (rs->res)
533                         moveadd(defrs->res[0]);
ragge
1.74
534
ragge
1.75
535                 rmask = rs->rmask;
536                 left = rs->left;
537                 right = rs->right;
ragge
1.56
538                 /* Add edges for used registers */
ragge
1.75
539                 for (i = 0rmask && rmask[i] >= 0i++)
540                         addalledges(rmask[i]);
ragge
1.56
541                 nreg = 0;
ragge
1.55
542         }
ragge
1.56
543
ragge
1.49
544         if (callop(p->n_op)) {
ragge
1.52
545                 /* first add all edges */
546                 for (i = 0i < maxregsi++)
ragge
1.74
547                         if (TAREGS & (1 << i))
548                                 addalledges(i);
ragge
1.49
549                 /* implicit move after call */
ragge
1.75
550                 moveadd(defRETREG);
ragge
1.49
551                 nreg = 0;
552         }
553         /*
554          * rall is the base of need allocation, RESCx tells which
555          * allocated register that should be reclaimed.
556          */
557         for (i = 0i < nregi++) {
558                 LIVEADD(def+i);
ragge
1.63
559                 addalledges(def+i); /* XXX special regs? */
ragge
1.49
560         }
561         /* If leg regs may not be shared, add edges */
ragge
1.74
562         /* XXX - addalledges -> AddEdge */
563         if ((p->n_su & LMASK) == LREG) {
564                 NODE *lp = GETP(p->n_left);
565                 int lr = lp->n_rall;
566
ragge
1.75
567                 if (!(q->needs & NASL))
568                         addalledges(lr);
569
ragge
1.74
570                 /* If a register will be clobbered, and this register */
571                 /* is not the leg register, add edge */
ragge
1.75
572                 for (i = 0rmask && rmask[i] >= 0i++) {
573                         if (left && rmask[i] == left[0])
574                                 continue;
575                         AddEdge(lrrmask[i]);
576                 }
ragge
1.74
577         }
578         if ((p->n_su & RMASK) == RREG) {
579                 NODE *rp = GETP(p->n_right);
580                 int rr = rp->n_rall;
ragge
1.75
581                 if (!(q->needs & NASR))
582                         addalledges(rr);
583
584                 for (i = 0rmask && rmask[i] >= 0i++) {
585                         if (right && rmask[i] == right[0])
586                                 continue;
587                         AddEdge(rrrmask[i]);
ragge
1.74
588                 }
589         }
ragge
1.49
590
591         /* now remove the needs from the live set */
592         for (i = 0i < nregi++)
593                 LIVEDEL(def+i);
594
595         /* walk down the legs and add interference edges */
596         l = r = 0;
597         if ((p->n_su & DORIGHT) && (p->n_su & LMASK)) {
ragge
1.74
598                 NODE *rp = GETP(p->n_right);
599                 r = rp->n_rall;
ragge
1.75
600                 LIVEADD(r);
ragge
1.74
601                 if (q->rewrite & RLEFT) {
602                         l = GETRALL(p->n_left);
ragge
1.75
603                         moveadd(p->n_ralll);
ragge
1.74
604                 }
605                 if (q->needs & NSPECIAL && left) {
606                         NODE *lp = GETP(p->n_left);
ragge
1.75
607                         if (left)
608                                 moveadd(lp->n_rallleft[0]);
ragge
1.74
609                 }
ragge
1.50
610                 insnwalk(p->n_left);
ragge
1.74
611                 if (p->n_right->n_op != TEMP ||
612                     p->n_right->n_rall != p->n_right->n_lval) {
ragge
1.75
613                         LIVEDEL(r);
ragge
1.74
614                 } else
615                         r = 0;
ragge
1.49
616         }
617         if ((p->n_su & RMASK)) {
ragge
1.74
618                 NODE *lp;
ragge
1.50
619                 if (r == 0 && (p->n_su & LMASK)) {
ragge
1.74
620                         lp = GETP(p->n_left);
621                         l = lp->n_rall;
ragge
1.75
622                         LIVEADD(l);
ragge
1.74
623                 }
624                 if (q->rewrite & RRIGHT) {
625                         if (p->n_su & LMASK) {
626                                 t = GETRALL(p->n_left);
ragge
1.75
627                                 moveadd(p->n_rallt);
ragge
1.74
628                         }
ragge
1.75
629                         moveadd(p->n_rallGETRALL(p->n_right));
ragge
1.74
630                 }
631                 if (q->needs & NSPECIAL && right) {
632                         NODE *rp = GETP(p->n_right);
ragge
1.75
633                         if (right)
634                                 moveadd(rp->n_rallright[0]);
ragge
1.49
635                 }
ragge
1.50
636                 insnwalk(p->n_right);
ragge
1.74
637                 if (p->n_su & LMASK) {
638                         if (p->n_left->n_op != TEMP ||
639                             p->n_left->n_rall != p->n_left->n_lval) {
640                                 if (l) {
ragge
1.75
641                                         LIVEDEL(l);
ragge
1.74
642                                 }
643                         } else
644                                 l = 0;
645                 }
ragge
1.49
646         }
647         if (!(p->n_su & DORIGHT) && (p->n_su & LMASK)) {
ragge
1.75
648                 if (q->rewrite & RLEFT)
649                         moveadd(p->n_rallGETRALL(p->n_left));
650
ragge
1.74
651                 if (q->needs & NSPECIAL && left) {
652                         NODE *lp = GETP(p->n_left);
ragge
1.75
653                         if (left)
654                                 moveadd(lp->n_rallleft[0]);
ragge
1.74
655                 }
ragge
1.50
656                 insnwalk(p->n_left);
ragge
1.49
657         }
ragge
1.63
658         if (p->n_op == TEMP) {
ragge
1.75
659                 moveadd(p->n_lvaldef);
660                 LIVEADD((int)p->n_lval);
661         } /* XXX - fix artificial edges */
ragge
1.49
662
663         /* Finished, clean up live set */
ragge
1.74
664         if (r) {
ragge
1.75
665                 LIVEDEL(r);
ragge
1.74
666         }
667         if (l) {
ragge
1.75
668                 LIVEDEL(l);
ragge
1.74
669         }
670 }
671
ragge
1.59
672 static bittype **gen, **kill, **in, **out;
673
674 static void
ragge
1.74
675 unionize(NODE *pint bb)
ragge
1.59
676 {
ragge
1.74
677         int ioty;
ragge
1.59
678
ragge
1.74
679         if ((o = p->n_op) == TEMP) {
680                 for (i = 0i < szty(p->n_type); i++) {
681                         BITSET(gen[bb], ((int)p->n_lval - tempmin+i));
682                 }
683         }
684         if (o == ASSIGN && p->n_left->n_op == TEMP) {
685                 int b = p->n_left->n_lval - tempmin;
686                 for (i = 0i < szty(p->n_type); i++) {
687                         BITCLEAR(gen[bb], (b+i));
688                         BITSET(kill[bb], (b+i));
689                 }
690                 unionize(p->n_rightbb);
ragge
1.59
691                 return;
ragge
1.74
692         }
693         ty = optype(o);
694         if (ty != LTYPE)
695                 unionize(p->n_leftbb);
696         if (ty == BITYPE)
697                 unionize(p->n_rightbb);
ragge
1.59
698 }
699
ragge
1.58
700 /*
701  * Do variable liveness analysis.  Only analyze the long-lived 
702  * variables, and save the live-on-exit temporaries in a bit-field
703  * at the end of each basic block. This bit-field is later used
ragge
1.59
704  * when doing short-range liveness analysis in Build().
ragge
1.58
705  */
ragge
1.46
706 static void
ragge
1.59
707 LivenessAnalysis(void)
ragge
1.46
708 {
ragge
1.59
709         extern struct basicblock bblocks;
710         struct basicblock *bb;
711         struct interpass *ip;
ragge
1.74
712         int ibbnum;
ragge
1.59
713
714         /*
715          * generate the gen-kill sets for all basic blocks.
716          */
717         DLIST_FOREACH(bb, &bblocksbbelem) {
ragge
1.74
718                 bbnum = bb->bbnum;
ragge
1.59
719                 for (ip = bb->last; ; ip = DLIST_PREV(ipqelem)) {
720                         /* gen/kill is 'p', this node is 'n' */
ragge
1.74
721                         if (ip->type == IP_NODE)
722                                 unionize(ip->ip_nodebbnum);
ragge
1.59
723                         if (ip == bb->first)
724                                 break;
725                 }
ragge
1.74
726                 memcpy(in[bbnum], gen[bbnum], BIT2BYTE(tempfe-tempmin));
ragge
1.60
727 #ifdef PCC_DEBUG
ragge
1.59
728                 if (rdebug) {
ragge
1.74
729                         printf("basic block %d\ngen: "bbnum);
ragge
1.61
730                         for (i = 0i < tempfe-tempmini++)
ragge
1.74
731                                 if (TESTBIT(gen[bbnum], i))
ragge
1.61
732                                         printf("%d "i+tempmin);
ragge
1.59
733                         printf("\nkill: ");
ragge
1.61
734                         for (i = 0i < tempfe-tempmini++)
ragge
1.74
735                                 if (TESTBIT(kill[bbnum], i))
ragge
1.61
736                                         printf("%d "i+tempmin);
ragge
1.59
737                         printf("\n");
738                 }
ragge
1.60
739 #endif
ragge
1.59
740         }
ragge
1.46
741 }
742
ragge
1.60
743 #define SETCOPY(t,f,i,n) for (i = 0; i < n; i += NUMBITS) t[i] = f[i]
744 #define SETSET(t,f,i,n) for (i = 0; i < n; i += NUMBITS) t[i] |= f[i]
745 #define SETCLEAR(t,f,i,n) for (i = 0; i < n; i += NUMBITS) t[i] &= ~f[i]
746 #define SETCMP(v,t,f,i,n) for (i = v = 0; i < n; i += NUMBITS) \
747         if (t[i] != f[i]) v = 1
748
ragge
1.67
749 static int savregs;
750
ragge
1.46
751 /*
752  * Build the set of interference edges and adjacency list.
753  */
754 static void
ragge
1.74
755 Build(struct interpass *ipole)
ragge
1.46
756 {
ragge
1.60
757         extern struct basicblock bblocks;
ragge
1.74
758         struct interpass *ip;
ragge
1.60
759         struct basicblock *bb;
760         struct cfgnode *cn;
ragge
1.59
761         extern int nbblocks;
ragge
1.60
762         bittype *saved;
763         int ijagainnbits;
ragge
1.59
764
ragge
1.74
765         if (xtemps) {
ragge
1.59
766                 /* Just fetch space for the temporaries from stack */
ragge
1.60
767
ragge
1.61
768                 nbits = tempfe - tempmin;
ragge
1.59
769                 gen = alloca(nbblocks*sizeof(bittype*));
770                 kill = alloca(nbblocks*sizeof(bittype*));
771                 in = alloca(nbblocks*sizeof(bittype*));
772                 out = alloca(nbblocks*sizeof(bittype*));
773                 for (i = 0i < nbblocksi++) {
774                         BITALLOC(gen[i],alloca,nbits);
775                         BITALLOC(kill[i],alloca,nbits);
776                         BITALLOC(in[i],alloca,nbits);
777                         BITALLOC(out[i],alloca,nbits);
778                 }
ragge
1.60
779                 BITALLOC(saved,alloca,nbits);
ragge
1.59
780                 LivenessAnalysis();
781
ragge
1.65
782                 /* register variable temporaries are live */
783                 for (i = 0i < NREGREGi++) {
ragge
1.67
784                         if ((savregs & (1 << i)) == 0)
785                                 continue/* spilled */
ragge
1.65
786                         BITSET(out[nbblocks-1], i);
787                         moveadd(i+MINRVARi+tempmin);
788                         for (j = ij < NREGREGj++)
789                                 AddEdge(i+tempminj+tempmin);
790                 }
791
ragge
1.60
792                 /* do liveness analysis on basic block level */
793                 do {
794                         again = 0;
795                         /* XXX - loop should be in reversed execution-order */
796                         DLIST_FOREACH_REVERSE(bb, &bblocksbbelem) {
797                                 int i = bb->bbnum;
798                                 SETCOPY(savedout[i], jnbits);
799                                 SLIST_FOREACH(cn, &bb->childrencfgelem) {
800                                         SETSET(out[i], in[cn->bblock->bbnum],
801                                             jnbits);
802                                 }
803                                 SETCMP(againsavedout[i], jnbits);
804                                 SETCOPY(savedin[i], jnbits);
805                                 SETCOPY(in[i], out[i], jnbits);
806                                 SETCLEAR(in[i], kill[i], jnbits);
807                                 SETSET(in[i], gen[i], jnbits);
808                                 SETCMP(againsavedin[i], jnbits);
809                         }
810                 } while (again);
811
ragge
1.61
812 #ifdef PCC_DEBUG
813                 if (rdebug) {
814                         DLIST_FOREACH(bb, &bblocksbbelem) {
815                                 printf("basic block %d\nin: "bb->bbnum);
816                                 for (i = 0i < tempfe-tempmini++)
817                                         if (TESTBIT(in[bb->bbnum], i))
818                                                 printf("%d "i+tempmin);
819                                 printf("\nout: ");
820                                 for (i = 0i < tempfe-tempmini++)
821                                         if (TESTBIT(out[bb->bbnum], i))
822                                                 printf("%d "i+tempmin);
823                                 printf("\n");
824                         }
825                 }
826 #endif
827
ragge
1.59
828                 DLIST_FOREACH(bb, &bblocksbbelem) {
ragge
1.63
829                         RDEBUG(("liveadd bb %d\n"bb->bbnum));
830                         i = bb->bbnum;
831                         for (j = 0j < (tempmax-tempmin); j += NUMBITS)
832                                 live[j] = 0;
ragge
1.60
833                         SETCOPY(liveout[i], jnbits);
834                         for (ip = bb->last; ; ip = DLIST_PREV(ipqelem)) {
835                                 if (ip->type == IP_NODE)
836                                         insnwalk(ip->ip_node);
837                                 if (ip == bb->first)
838                                         break;
839                         }
ragge
1.59
840                 }
ragge
1.74
841         } else {
842                 DLIST_FOREACH_REVERSE(ipipoleqelem) {
843                         if (ip->type != IP_NODE)
844                                 continue;
845                         insnwalk(ip->ip_node);
846                 }
847         }
ragge
1.48
848
ragge
1.74
849 #ifdef PCC_DEBUG
ragge
1.48
850         if (rdebug) {
851                 int i;
852                 struct AdjSet *w;
ragge
1.73
853                 ADJL *x;
ragge
1.48
854
855                 printf("Interference edges\n");
856                 for (i = 0i < 256i++) {
857                         if ((w = edgehash[i]) == NULL)
858                                 continue;
859                         for (; ww = w->next)
860                                 printf("%d <-> %d\n"w->uw->v);
861                 }
ragge
1.73
862                 printf("Degrees\n");
863                 for (i = tempmini < tempmaxi++) {
864                         printf("%d: degree(%d), "iDEGREE(i));
865                         for (x = ADJLIST(i); xx = x->r_next) {
866                                 if (ONLIST(x->a_temp) != &selectStack &&
867                                     ONLIST(x->a_temp) != &coalescedNodes)
868                                         printf("%d "x->a_temp);
869                                 else
870                                         printf("(%d) "x->a_temp);
871                         }
872                         printf("\n");
873                 }
ragge
1.48
874         }
ragge
1.74
875 #endif
ragge
1.48
876
ragge
1.46
877 }
878
879 static void
ragge
1.48
880 EnableMoves(int n)
ragge
1.46
881 {
882         MOVL *l;
ragge
1.48
883         REGM *m;
884
ragge
1.49
885         for (l = MOVELIST(n); ll = l->next) {
ragge
1.48
886                 m = l->regm;
887                 if (m->queue != ACTIVE)
888                         continue;
889                 DLIST_REMOVE(mlink);
890                 PUSHMLIST(mworklistMovesWLIST);
891         }
892 }
893
894 static void
895 EnableAdjMoves(int nodes)
896 {
ragge
1.47
897         ADJL *w;
ragge
1.46
898         int n;
899
ragge
1.48
900         EnableMoves(nodes);
ragge
1.49
901         for (w = ADJLIST(nodes); ww = w->r_next) {
902                 n = w->a_temp;
903                 if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes)
ragge
1.46
904                         continue;
ragge
1.49
905                 EnableMoves(w->a_temp);
ragge
1.46
906         }
907 }
908
909 static void
910 DecrementDegree(int m)
911 {
ragge
1.48
912         REGW *w = &nodeblock[m];
ragge
1.46
913
ragge
1.72
914         RDEBUG(("DecrementDegree: m %d, degree %d\n"mDEGREE(m)));
ragge
1.52
915         if (DEGREE(m)-- != maxregs)
ragge
1.46
916                 return;
917
ragge
1.48
918         EnableAdjMoves(m);
919         DELWLIST(w);
ragge
1.49
920         ONLIST(m) = 0;
ragge
1.46
921         if (MoveRelated(m)) {
922                 PUSHWLIST(wfreezeWorklist);
923         } else {
924                 PUSHWLIST(wsimplifyWorklist);
925         }
926 }
927
928 static void
929 Simplify(void)
930 {
931         REGW *w;
ragge