![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to regalloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin / f77 / f77.tahoe / f77pass1|
Return to regalloc.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin / f77 / f77.tahoe / f77pass1 |
1.1 root 1: /*
2: * Copyright (c) 1980 Regents of the University of California.
3: * All rights reserved. The Berkeley software License Agreement
4: * specifies the terms and conditions for redistribution.
5: */
6:
7: #ifndef lint
8: static char sccsid[] = "@(#)regalloc.c 5.1 (Berkeley) 6/7/85";
9: #endif not lint
10:
11: /*
12: * regalloc.c
13: *
14: * Register optimization routines for f77 compiler, pass 1
15: *
16: * University of Utah CS Dept modification history:
17: *
18: * $History$
19: * $Log: regalloc.c,v $
20: * Revision 1.4 86/02/12 15:29:16 rcs
21: * 4.3 F77. C. Keating.
22: *
23: * Revision 2.9 85/03/18 21:35:05 donn
24: * Bob Corbett's hack to prevent conflicts between subroutine side effects
25: * and register assignment. Makes the code a lot worse...
26: *
27: * Revision 2.8 85/02/22 02:14:08 donn
28: * In code like 'x = foo(x)', alreg() would copy the memory version of the
29: * variable 'x' into the register version after the assignment, clobbering
30: * the result. A small change to regwrite() seems to prevent this.
31: *
32: * Revision 2.7 85/02/16 03:32:45 donn
33: * Fixed a bug where the loop test and increment were having register
34: * substitution performed twice, once in the environment of the current
35: * loop and once in the environment of the containing loop. If the
36: * containing loop puts (say) the inner loop's index variable in register
37: * but the inner loop does not, havoc results.
38: *
39: * Revision 2.6 85/02/14 23:21:45 donn
40: * Don't permit variable references of the form 'a(i)' to be put in register
41: * if array 'a' is in common. This is because there is no good way to
42: * identify instances of this sort without getting confused with other
43: * variables in the same common block which are in register. Sigh.
44: *
45: * Revision 2.5 85/01/11 21:08:00 donn
46: * Made changes so that we pay attention to SAVE statements. Added a new
47: * gensetreturn() function to implement this.
48: *
49: * Revision 2.4 84/09/03 22:37:28 donn
50: * Changed the treatment of SKRETURN in alreg() so that all variables in
51: * register, not just COMMON variables, get written out to memory before a
52: * RETURN. This was causing the return value of a function to get lost when
53: * a RETURN was done from inside a loop (among other problems).
54: *
55: * Revision 2.3 84/08/04 20:52:42 donn
56: * Added fixes for EXTERNAL parameters from Jerry Berkman.
57: *
58: * Revision 2.2 84/08/04 20:34:29 donn
59: * Fixed a stupidity pointed out by Jerry Berkman -- the 'floats in register'
60: * stuff applies if the TARGET is a VAX, not if the local machine is a VAX.
61: *
62: * Revision 2.1 84/07/19 12:04:47 donn
63: * Changed comment headers for UofU.
64: *
65: * Revision 1.5 83/11/27 19:25:41 donn
66: * Added REAL to the list of types which may appear in registers (VAXen only).
67: *
68: * Revision 1.4 83/11/13 02:38:39 donn
69: * Bug fixed in alreg()'s handling of computed goto's. A '<=' in place of a
70: * '<' led to core dumps when we walked off the end of the list of labels...
71: *
72: * Revision 1.3 83/11/12 01:25:57 donn
73: * Bug in redundant register assignment code, mistakenly carried over some old
74: * code that sometimes rewound a slot pointer even when a redundant slot wasn't
75: * deleted; this caused an infinite loop... Seems to work now.
76: *
77: * Revision 1.2 83/11/09 14:58:12 donn
78: * Took out broken code dealing with redundant register initializations.
79: * Couldn't see what to do about redundantly initializing a DO variable but
80: * I did fix things so that an assignment from a register into the same
81: * register is always deleted.
82: *
83: */
84:
85: #include "defs.h"
86: #include "optim.h"
87:
88: #define LABTABSIZE 101
89: #define VARTABSIZE 1009
90: #define TABLELIMIT 12
91:
92: #if TARGET==VAX || TARGET==TAHOE
93: #define MSKREGTYPES M(TYLOGICAL) | M(TYADDR) | M(TYSHORT) | M(TYLONG) | M(TYREAL)
94: #if TARGET==TAHOE
95: #define BUMPREALS /* put floats last */
96: #endif
97: #else
98: #define MSKREGTYPES M(TYLOGICAL) | M(TYADDR) | M(TYSHORT) | M(TYLONG)
99: #endif
100:
101:
102: #define ISREGTYPE(x) ONEOF(x, MSKREGTYPES)
103:
104: #define MSKVARS M(STGAUTO) | M(STGBSS) | M(STGINIT) | M(STGCONST) |\
105: M(STGEQUIV) | M(STGARG) | M(STGCOMMON)
106:
107: #define ISVAR(x) ((((expptr) x)->headblock.vclass == CLVAR || \
108: ((expptr) x)->headblock.vclass == CLUNKNOWN) \
109: && ONEOF(((expptr) x)->headblock.vstg, MSKVARS))
110:
111:
112: typedef
113: struct regdata
114: {
115: field vstg;
116: field vtype;
117: int memno;
118: int memoffset;
119: int refs;
120: Addrp stgp;
121: unsigned isarrayarg : 1;
122: unsigned istemp : 1;
123: unsigned isset : 1;
124: unsigned setfirst : 1;
125: } REGDATA;
126:
127:
128: typedef
129: struct labelnode
130: {
131: struct labelnode *link;
132: int labelno;
133: } LABELNODE;
134:
135:
136:
137: typedef
138: struct varnode
139: {
140: struct varnode *link;
141: int memoffset;
142: unsigned isset : 1;
143: unsigned isused : 1;
144: unsigned setfirst : 1;
145: unsigned unusable : 1;
146: int refs;
147: Addrp stgp;
148: } VARNODE;
149:
150:
151: typedef
152: struct addrnode
153: {
154: struct addrnode *link;
155: field vtype;
156: field vstg;
157: int memno;
158: unsigned istemp : 1;
159: unsigned isset : 1;
160: unsigned loopset :1;
161: unsigned freeuse : 1;
162: unsigned mixedtype : 1;
163: unsigned fixed : 1;
164: int refs;
165: struct addrnode *commonlink;
166: VARNODE *varlist;
167: } ADDRNODE;
168:
169:
170: typedef
171: struct setnode
172: {
173: struct setnode *link;
174: field vstg;
175: int memno;
176: int memoffset;
177: } SETNODE;
178:
179:
180: typedef
181: struct doqueue
182: {
183: struct doqueue *up, *down;
184: Slotp dohead, doend;
185: int nregvars;
186: REGNODE *reg[MAXREGVAR];
187: } DOQUEUE;
188:
189: LOCAL DOQUEUE *dqptr, *dqtop, *dqbottom;
190:
191:
192: LOCAL Slotp dohead;
193: LOCAL Slotp doend;
194: LOCAL Slotp newcode;
195:
196:
197:
198: LOCAL LABELNODE *labeltable[LABTABSIZE];
199: LOCAL ADDRNODE *vartable[VARTABSIZE];
200: LOCAL ADDRNODE *commonvars;
201: LOCAL SETNODE *setlist;
202: LOCAL int topregvar;
203: LOCAL int toplcv;
204: LOCAL int allset;
205: LOCAL ADDRNODE *currentaddr;
206: LOCAL int loopcost;
207: LOCAL REGDATA *regtab[MAXREGVAR];
208: LOCAL REGDATA *rt[TABLELIMIT];
209: LOCAL int tabletop;
210: LOCAL int linearcode;
211: LOCAL int docount;
212: LOCAL int globalbranch;
213: LOCAL int commonunusable;
214: LOCAL int regdefined[MAXREGVAR];
215: LOCAL int memdefined[MAXREGVAR];
216: LOCAL int regaltered[MAXREGVAR];
217:
218:
219:
220: LOCAL insertlabel(l)
221: int l;
222:
223: {
224: int key;
225: LABELNODE *p;
226:
227: key = l % LABTABSIZE;
228: for (p = labeltable[key]; p; p = p->link)
229: if (p->labelno == l) return;
230: p = labeltable[key];
231: labeltable[key] = ALLOC(labelnode);
232: labeltable[key]->link = p;
233: labeltable[key]->labelno = l;
234: return;
235: }
236:
237:
238:
239: LOCAL int locallabel(l)
240: int l;
241:
242: {
243: int key;
244: LABELNODE *p;
245:
246: key = l % LABTABSIZE;
247: for (p = labeltable[key]; p; p = p->link)
248: if (p->labelno == l) return YES;
249:
250: return NO;
251: }
252:
253:
254:
255: LOCAL freelabtab()
256:
257: {
258: int i;
259: LABELNODE *p, *q;
260:
261: for (i = 0; i < LABTABSIZE; i++)
262: if (labeltable[i])
263: {
264: p = labeltable[i];
265: labeltable[i] = NULL;
266: while (p)
267: {
268: q = p->link;
269: free(p);
270: p = q;
271: }
272: }
273: return;
274: }
275:
276:
277:
278: LOCAL ADDRNODE *getaddr(ap)
279: Addrp ap;
280:
281: {
282: int key;
283: field vstg;
284: int memno;
285: register ADDRNODE *q;
286: ADDRNODE *q1;
287:
288: if (!ISVAR(ap))
289: fatal("regalloc: bad data sent to getaddr");
290: vstg = ap->vstg;
291: memno = ap->memno;
292: key = (256*vstg + memno) % VARTABSIZE;
293:
294: for (q = vartable[key]; q; q = q->link)
295: if ((q->vstg == vstg) && (q->memno == memno))
296: {
297: if (ap->istemp) q->istemp = YES;
298: if (ap->vtype != q->vtype)
299: q->mixedtype = YES;
300: if (!fixedaddress(ap))
301: q->fixed = NO;
302: return q;
303: }
304:
305: q1 = vartable[key];
306: vartable[key] = q = ALLOC(addrnode);
307: q->link = q1;
308: q->vstg = vstg;
309: q->memno = memno;
310: if (ap->istemp) q->istemp = YES;
311: if (fixedaddress(ap)) q->fixed = YES;
312: q->vtype = ap->vtype;
313: q->varlist = NULL;
314: if (vstg == STGCOMMON)
315: {
316: q->commonlink = commonvars;
317: commonvars = q;
318: }
319: return q;
320: }
321:
322:
323:
324: LOCAL VARNODE *getvar(ainfo, ap)
325: ADDRNODE *ainfo;
326: Addrp ap;
327:
328: {
329: register VARNODE *q;
330: register VARNODE *q1;
331:
332: int memoffset;
333:
334: if (!ISVAR(ap))
335: fatal("regalloc: bad data sent to getvar");
336:
337: memoffset = ap->memoffset->constblock.const.ci;
338:
339: for (q = ainfo->varlist; q; q = q->link)
340: if (q->memoffset == memoffset)
341: return q;
342:
343: q1 = ainfo->varlist;
344: ainfo->varlist = q = ALLOC(varnode);
345: q->link = q1;
346: q->memoffset = memoffset;
347: q->stgp = (Addrp) cpexpr(ap);
348: return q;
349: }
350:
351:
352: LOCAL ADDRNODE *lookupaddr(vstg, memno)
353: field vstg;
354: int memno;
355:
356: {
357: int key;
358: register ADDRNODE *q;
359:
360: key = (256*vstg + memno) % VARTABSIZE;
361:
362: for (q = vartable[key]; q; q = q->link)
363: if ((q->vstg == vstg) && (q->memno == memno))
364: return q;
365:
366: fatal("regalloc: lookupaddr");
367: }
368:
369:
370: LOCAL VARNODE *lookupvar(ainfo, memoffset)
371: ADDRNODE *ainfo;
372: int memoffset;
373:
374: {
375: register VARNODE *q;
376:
377: for (q = ainfo->varlist; q; q = q->link)
378: if (q->memoffset == memoffset)
379: return q;
380:
381: fatal("regalloc: lookupvar");
382: }
383:
384:
385:
386: LOCAL int invartable(p)
387: REGNODE *p;
388:
389: {
390: field vstg;
391: int memno;
392: int key;
393: register ADDRNODE *q;
394:
395: vstg = p->vstg;
396: memno = p->memno;
397: key = (256*vstg + memno) % VARTABSIZE;
398:
399: for (q = vartable[key]; q; q = q->link)
400: if ((q->vstg == vstg) && (q->memno == memno))
401: return YES;
402:
403: return NO;
404: }
405:
406:
407:
408: LOCAL freevartab()
409:
410: {
411: register ADDRNODE *p;
412: ADDRNODE *p1;
413: register VARNODE *q;
414: VARNODE *q1;
415: register int i;
416:
417: for (i = 0; i < VARTABSIZE; i++)
418: if (vartable[i])
419: {
420: p = vartable[i];
421: vartable[i] = NULL;
422:
423: while (p)
424: {
425: for (q = p->varlist; q; q = q1)
426: {
427: q1 = q->link;
428: frexpr(q->stgp);
429: free ((char *) q);
430: }
431: p1 = p->link;
432: free((char *) p);
433: p = p1;
434: }
435: }
436: }
437:
438:
439:
440: LOCAL insertset(vstg, memno, memoffset)
441: field vstg;
442: int memno;
443: int memoffset;
444:
445: {
446: register SETNODE *p;
447: SETNODE *q;
448:
449: if (allset) return;
450: for (p = setlist; p; p = p->link)
451: if((p->vstg == vstg) && (p->memno == memno) && (p->memoffset == memoffset))
452: return;
453:
454: q = p;
455: setlist = p = ALLOC(setnode);
456: p->link = q;
457: p->vstg = vstg;
458: p->memno = memno;
459: p->memoffset = memoffset;
460: return;
461: }
462:
463:
464:
465: LOCAL int insetlist(vstg, memno, memoffset)
466: field vstg;
467: int memno;
468: int memoffset;
469:
470: {
471: register SETNODE *p;
472:
473: if (allset) return YES;
474: for (p = setlist; p; p = p->link)
475: if((p->vstg == vstg) && (p->memno == memno) && (p->memoffset == memoffset))
476: return YES;
477:
478: return NO;
479: }
480:
481:
482:
483: LOCAL clearsets()
484:
485: {
486: register SETNODE *p, *q;
487:
488: allset = NO;
489:
490: p = setlist;
491: while (p)
492: {
493: q = p->link;
494: free ((char *) p);
495: p = q;
496: }
497: setlist = NULL;
498: return;
499: }
500:
501:
502:
503: LOCAL alreg()
504:
505: {
506: register Slotp sp;
507: register int i;
508: register ADDRNODE *p;
509: register VARNODE *q;
510: Slotp sp1, sp2;
511: ADDRNODE *addrinfo;
512: VARNODE *varinfo;
513: struct Labelblock **lp;
514: int toptrack;
515: int track[MAXREGVAR];
516: Addrp ap, ap1;
517: DOQUEUE *dqp;
518: REGDATA *rp;
519: REGNODE *regp;
520:
521: if (nregvar >= maxregvar) return;
522:
523: commonvars = NULL;
524: docount = 0;
525:
526: for (sp = dohead; sp != doend->next; sp = sp->next)
527: switch (sp->type)
528: {
529: case SKLABEL:
530: insertlabel(sp->label);
531: break;
532:
533: case SKARIF:
534: case SKASGOTO:
535: case SKCALL:
536: case SKCMGOTO:
537: case SKEQ:
538: case SKIFN:
539: case SKIOIFN:
540: case SKSTOP:
541: case SKPAUSE:
542: case SKRETURN:
543: scanvars(sp->expr);
544: break;
545:
546: case SKDOHEAD:
547: ++docount;
548: break;
549:
550: case SKENDDO:
551: --docount;
552: break;
553:
554: case SKNULL:
555: case SKGOTO:
556: case SKASSIGN:
557: break;
558:
559: default:
560: badthing ("SKtype", "alreg-1", sp->type);
561: }
562:
563: loopcost = 0;
564: docount = 1;
565: commonunusable = NO;
566: if (! dohead->nullslot) fatal ("missing dohead->nullslot -cbb");
567: for (sp = dohead->next, globalbranch = NO;
568: docount;
569: sp = sp->next, clearsets(), globalbranch = NO)
570: if (docount > 1)
571: switch (sp->type)
572: {
573: case SKDOHEAD:
574: docount++;
575: break;
576:
577: case SKENDDO:
578: docount--;
579:
580: default:
581: break;
582: }
583: else
584: switch (sp->type)
585: {
586: case SKARIF:
587: #define LM ((struct Labelblock * *)sp->ctlinfo)[0]->labelno
588: #define LZ ((struct Labelblock * *)sp->ctlinfo)[1]->labelno
589: #define LP ((struct Labelblock * *)sp->ctlinfo)[2]->labelno
590:
591: if (!locallabel(LM) || !locallabel(LZ) || !locallabel(LP))
592: {
593: setall();
594: globalbranch = YES;
595: }
596: countrefs(sp->expr);
597: break;
598:
599: case SKASGOTO:
600: setall();
601: globalbranch = YES;
602: countrefs(sp->expr);
603: break;
604:
605: case SKCMGOTO:
606: lp = (struct Labelblock **) sp->ctlinfo;
607: for (i = 0; i < sp->label; i++, lp++)
608: if (!locallabel((*lp)->labelno))
609: {
610: setall();
611: globalbranch = YES;
612: break;
613: }
614: countrefs(sp->expr);
615: break;
616:
617: case SKDOHEAD:
618: globalbranch = YES;
619: loopcost = 2;
620: docount++;
621: break;
622:
623: case SKENDDO:
624: docount = 0;
625: break;
626:
627: case SKGOTO:
628: if (!locallabel(sp->label))
629: {
630: setall();
631: globalbranch = YES;
632: }
633: break;
634:
635: case SKIFN:
636: case SKIOIFN:
637: if (!locallabel(sp->label))
638: {
639: setall();
640: globalbranch = YES;
641: }
642: countrefs(sp->expr);
643: break;
644:
645: case SKEQ:
646: case SKCALL:
647: case SKSTOP:
648: case SKPAUSE:
649: linearcode = YES;
650: countrefs(sp->expr);
651: linearcode = NO;
652: break;
653: }
654:
655: topregvar = toplcv = nregvar - 1;
656:
657: for (i = 0; i < nregvar; i++)
658: {
659: ap = memversion(regnamep[i]);
660: regtab[i] = rp = ALLOC(regdata);
661: rp->vstg = ap->vstg;
662: rp->vtype = ap->vtype;
663: rp->memno = ap->memno;
664: rp->memoffset = ap->memoffset->constblock.const.ci;
665: rp->isarrayarg = NO;
666: rp->stgp = ap;
667: }
668:
669: for (i = 0; i < MAXREGVAR; i++)
670: track[i] = YES;
671:
672: for (dqp = dqptr->down; dqp; dqp = dqp->down)
673: {
674: if (dqp->nregvars - 1 > topregvar)
675: topregvar = dqp->nregvars -1;
676: for (i = toplcv + 1; i < dqp->nregvars; i++)
677: if (track[i])
678: if (regp = dqp->reg[i])
679: if (rp = regtab[i])
680: {
681: if (!samevar(rp, regp))
682: track[i] = NO;
683: }
684: else if (invartable(regp))
685: {
686: regtab[i] = rp = ALLOC(regdata);
687: rp->vstg = regp->vstg;
688: rp->vtype = regp->vtype;
689: rp->memno = regp->memno;
690: rp->memoffset = regp->memoffset;
691: addrinfo = lookupaddr(rp->vstg, rp->memno);
692: if (regp->isarrayarg)
693: {
694: rp->isarrayarg = YES;
695: rp->refs = addrinfo->refs;
696: }
697: else
698: {
699: varinfo = lookupvar(addrinfo, regp->memoffset);
700: rp->refs = varinfo->refs;
701: rp->stgp = (Addrp) cpexpr(varinfo->stgp);
702: rp->istemp = addrinfo->istemp;
703: rp->isset = varinfo->isset;
704: rp->setfirst = varinfo->setfirst;
705: }
706: }
707: else
708: track[i] = NO;
709: else
710: track[i] = NO;
711: }
712:
713: toptrack = topregvar;
714:
715: for (i = toplcv + 1; i <= topregvar; i++)
716: if (regtab[i])
717: if ((track[i] == NO) || (regtab[i]->refs <= 0))
718: {
719: free((char *) regtab[i]);
720: regtab[i] = NULL;
721: }
722:
723: tabletop = -1;
724: if (topregvar < maxregvar - 1)
725: for (i = 0; i < VARTABSIZE; i++)
726: for (p = vartable[i]; p; p = p->link)
727: {
728: entableaddr(p);
729: if ((!p->loopset) &&
730: (!p->mixedtype) &&
731: (p->vstg != STGARG) &&
732: !((p->vstg == STGCOMMON) && ((!p->fixed) || commonunusable)))
733: for (q = p->varlist; q; q = q->link)
734: entablevar(q);
735: }
736:
737: for (i = 0; (i <= tabletop) && (topregvar + 1 < maxregvar); i++)
738: {
739: if (inregtab(rt[i]) || (loopcost && rt[i]->isset))
740: continue;
741: topregvar++;
742: regtab[topregvar] = rp = ALLOC(regdata);
743: rp->vstg = rt[i]->vstg;
744: rp->vtype = rt[i]->vtype;
745: rp->memno = rt[i]->memno;
746: rp->memoffset = rt[i]->memoffset;
747: rp->refs = rt[i]->refs;
748: rp->stgp = (Addrp) cpexpr(rt[i]->stgp);
749: rp->isarrayarg = rt[i]->isarrayarg;
750: rp->istemp = rt[i]->istemp;
751: rp->isset = rt[i]->isset;
752: rp->setfirst = rt[i]->setfirst;
753: }
754:
755: for (i = toplcv + 1; i <= topregvar; i++)
756: {
757: if (rp = regtab[i])
758: if (rp->isarrayarg)
759: {
760: ap = ALLOC(Addrblock);
761: ap->tag = TADDR;
762: ap->vstg = STGREG;
763: ap->vtype = TYADDR;
764: ap->vclass = CLVAR;
765: ap->memno = regnum[i];
766: ap->memoffset = ICON(0);
767:
768: ap1 = ALLOC(Addrblock);
769: ap1->tag = TADDR;
770: ap1->vstg = rp->vstg;
771: ap1->vtype = rp->vtype;
772: ap1->vclass = CLVAR;
773: ap1->memno = rp->memno;
774: ap1->memoffset = ICON(0);
775:
776: insertassign(dohead, ap, addrof(ap1));
777: }
778: else if (!(rp->setfirst && rp->istemp))
779: {
780: if (rp->istemp)
781: for (sp = newcode; sp && sp != dohead; sp = sp->next)
782: if (sp->type == SKEQ)
783: {
784: ap = (Addrp) sp->expr->exprblock.leftp;
785: if ((ap->vstg == rp->vstg) && (ap->memno == rp->memno) &&
786: fixedaddress(ap) &&
787: (ap->memoffset->constblock.const.ci == rp->memoffset))
788: {
789: changetoreg(ap, i);
790: goto L1;
791: }
792: }
793: ap = (Addrp) cpexpr(rp->stgp);
794: changetoreg(ap, i);
795: insertassign(dohead, ap, cpexpr(rp->stgp));
796: }
797: L1:;
798: }
799:
800: for (i = toplcv + 1; i <= topregvar; i++)
801: if (rp = regtab[i])
802: if (rp->isset && !(rp->istemp || rp->isarrayarg))
803: {
804: ap = (Addrp) cpexpr(rp->stgp);
805: changetoreg(ap, i);
806: appendassign(doend, cpexpr(rp->stgp), ap);
807: }
808:
809: docount = 1;
810: clearmems();
811: setregs();
812: sp = dohead->next;
813: if (loopcost)
814: for (i = toptrack + 1; i <= topregvar; i++)
815: if ((rp = regtab[i]) && !rp->isarrayarg)
816: {
817: ap = (Addrp) cpexpr(rp->stgp);
818: changetoreg(ap, i);
819: insertassign(sp, cpexpr(rp->stgp), ap);
820: }
821:
822: for ( sp = dohead->next;
823: docount || sp->type != SKNULL;
824: sp = sp->next)
825: if (docount > 1)
826: switch (sp->type)
827: {
828: case SKDOHEAD:
829: docount++;
830: break;
831:
832: case SKENDDO:
833: if (--docount == 1)
834: {
835: /*
836: * Remove redundant stores to memory.
837: */
838: sp1 = sp->nullslot->next;
839: while (sp1)
840: {
841: if (regtomem(sp1))
842: {
843: ap = (Addrp) sp1->expr->exprblock.rightp;
844: sp2 = sp1->next;
845: for (i = toplcv + 2; i <= toptrack; i++)
846: if (regtab[i] && (regnum[i] == ap->memno))
847: {
848: deleteslot(sp1);
849: break;
850: }
851: sp1 = sp2;
852: }
853: else
854: sp1 = NULL;
855: }
856:
857: /*
858: * Restore register variables (complement to DOHEAD code).
859: */
860: sp1 = sp->nullslot->next;
861: for (i = toplcv + 1; i <= topregvar; i++)
862: if (rp = regtab[i])
863: if (!regdefined[i])
864: if (i >= dqp->nregvars || !samevar(rp, dqp->reg[i]))
865: {
866: ap = (Addrp) cpexpr(rp->stgp);
867: changetoreg(ap, i);
868: insertassign(sp1, ap, cpexpr(rp->stgp));
869: regdefined[i] = YES;
870: }
871:
872: clearmems();
873: if (toplcv + 1 < maxregvar)
874: memdefined[toplcv + 1] = YES;
875: sp = sp1->prev;
876: }
877: break;
878: }
879: else
880: {
881: setregs();
882: for (i = 0; i <= MAXREGVAR; i++)
883: regaltered[i] = NO;
884: globalbranch = NO;
885:
886: switch (sp->type)
887: {
888: case SKLABEL:
889: clearmems();
890: break;
891:
892: case SKGOTO:
893: if (!locallabel(sp->label))
894: gensetall(sp);
895: break;
896:
897: case SKENDDO:
898: docount = 0;
899: break;
900:
901: case SKRETURN:
902: gensetreturn(sp);
903: linearcode = YES;
904: regwrite(sp, sp->expr);
905: linearcode = NO;
906: break;
907:
908: case SKDOHEAD:
909: /*
910: * If one of the current loop's register variables is not in
911: * register in an inner loop, we must save it. It's a pity
912: * we don't save enough info to optimize this properly...
913: */
914: for (dqp = dqptr->down; dqp; dqp = dqp->down)
915: if (dqp->dohead == sp)
916: break;
917: if (dqp == NULL)
918: fatal("confused in alreg loop analysis");
919: for (i = toplcv + 1; i <= topregvar; i++)
920: if (rp = regtab[i])
921: if (!memdefined[i])
922: if (i >= dqp->nregvars || !samevar(rp, dqp->reg[i]))
923: {
924: ap = (Addrp) cpexpr(rp->stgp);
925: changetoreg(ap, i);
926: insertassign(sp, cpexpr(rp->stgp), ap);
927: memdefined[i] = YES;
928: regdefined[i] = NO;
929: }
930:
931: docount++;
932: globalbranch = YES;
933: break;
934:
935: case SKEQ:
936: case SKCALL:
937: case SKSTOP:
938: case SKPAUSE:
939: linearcode = YES;
940: regwrite(sp, sp->expr);
941: for (i = toplcv + 1; i <= topregvar; i++)
942: if (!regdefined[i] && ((rp = regtab[i]) && rp->isset))
943: {
944: ap = (Addrp) cpexpr(rp->stgp);
945: changetoreg(ap, i);
946: appendassign(sp, ap, cpexpr(rp->stgp));
947: sp = sp->next;
948: regdefined[i] = YES;
949: }
950: linearcode = NO;
951:
952: /*
953: * Eliminate redundant register moves.
954: */
955: if (regtoreg(sp))
956: {
957: ap = (Addrp) sp->expr->exprblock.leftp;
958: sp1 = sp->prev;
959: for (i = toplcv + 1; i <= toptrack; i++)
960: if (regtab[i] && (regnum[i] == ap->memno))
961: {
962: deleteslot(sp);
963: sp = sp1;
964: break;
965: }
966: }
967: break;
968:
969: case SKARIF:
970: if (!locallabel(LM) || !locallabel(LZ) || !locallabel(LP))
971: {
972: gensetall(sp);
973: globalbranch = YES;
974: }
975: regwrite(sp, sp->expr);
976: break;
977:
978: case SKASGOTO:
979: gensetall(sp);
980: globalbranch = YES;
981: regwrite(sp, sp->expr);
982: break;
983:
984: case SKCMGOTO:
985: lp = (struct Labelblock **) sp->ctlinfo;
986: for (i = 0; i < sp->label; i++, lp++)
987: if (!locallabel((*lp)->labelno))
988: {
989: gensetall(sp);
990: globalbranch = YES;
991: break;
992: }
993: regwrite(sp, sp->expr);
994: break;
995:
996: case SKIFN:
997: case SKIOIFN:
998: if (!locallabel(sp->label))
999: {
1000: gensetall(sp);
1001: globalbranch = YES;
1002: }
1003: regwrite(sp, sp->expr);
1004: break;
1005:
1006: case SKNULL:
1007: case SKASSIGN:
1008: break;
1009:
1010: default:
1011: badthing ("SKtype","alreg-3",sp->type);
1012: }
1013:
1014: for (i = toplcv + 1; i <= topregvar; i++)
1015: if (regaltered[i])
1016: memdefined[i] = NO;
1017: }
1018:
1019: if (topregvar + 1 > highregvar)
1020: highregvar = topregvar + 1;
1021: dqptr->nregvars = topregvar + 1;
1022: for (i = 0; i <= topregvar; i++)
1023: if (rp = regtab[i])
1024: {
1025: dqptr->reg[i] = regp = ALLOC(regnode);
1026: regp->vstg = rp->vstg;
1027: regp->vtype = rp->vtype;
1028: regp->memno = rp->memno;
1029: regp->memoffset = rp->memoffset;
1030: regp->isarrayarg = rp->isarrayarg;
1031: frexpr(rp->stgp);
1032: free((char *) rp);
1033: regtab[i] = NULL;
1034: }
1035:
1036: while (tabletop >= 0)
1037: free((char *) rt[tabletop--]);
1038: freelabtab();
1039: freevartab();
1040: return;
1041: }
1042:
1043:
1044:
1045: LOCAL scanvars(p)
1046: expptr p;
1047:
1048: {
1049: Addrp ap;
1050: ADDRNODE *addrinfo;
1051: VARNODE *varinfo;
1052: chainp args;
1053: VARNODE *q;
1054:
1055: if (p == NULL) return;
1056:
1057: switch (p->tag)
1058: {
1059: case TCONST:
1060: return;
1061:
1062: case TEXPR:
1063: switch (p->exprblock.opcode)
1064: {
1065: case OPASSIGN:
1066: scanassign(p);
1067: return;
1068:
1069: case OPPLUSEQ:
1070: case OPSTAREQ:
1071: scanopeq(p);
1072: return;
1073:
1074: case OPCALL:
1075: scancall(p);
1076: return;
1077:
1078: default:
1079: scanvars(p->exprblock.vleng);
1080: scanvars(p->exprblock.leftp);
1081: scanvars(p->exprblock.rightp);
1082: return;
1083: }
1084:
1085: case TADDR:
1086: ap = (Addrp) p;
1087: scanvars(ap->vleng);
1088: scanvars(ap->memoffset);
1089: if (!ISVAR(ap)) return;
1090:
1091: addrinfo = getaddr(ap);
1092: if (fixedaddress(ap))
1093: {
1094: if (ISREGTYPE(ap->vtype))
1095: {
1096: varinfo = getvar(addrinfo, ap);
1097: varinfo->isused = YES;
1098: }
1099: }
1100: else
1101: {
1102: addrinfo->freeuse = YES;
1103: for (q = addrinfo->varlist; q; q = q->link)
1104: q->isused = YES;
1105: }
1106: return;
1107:
1108: case TLIST:
1109: for (args = p->listblock.listp; args; args = args->nextp)
1110: scanvars(args->datap);
1111: return;
1112:
1113: default:
1114: badtag ("regalloc:scanvars", p->tag);
1115: }
1116: }
1117:
1118:
1119:
1120: LOCAL scanassign(ep)
1121: Exprp ep;
1122:
1123: {
1124: Addrp lhs;
1125: VARNODE *varinfo;
1126: ADDRNODE *addrinfo;
1127:
1128: scanvars(ep->rightp);
1129: if (ep->leftp->tag == TADDR)
1130: {
1131: lhs = (Addrp) ep->leftp;
1132: scanvars(lhs->vleng);
1133: scanvars(lhs->memoffset);
1134: if ((lhs->vstg == STGREG) || (lhs->vstg == STGPREG))
1135: return;
1136: if (ISVAR(lhs))
1137: {
1138: addrinfo = getaddr(lhs);
1139: addrinfo->isset = YES;
1140: if (docount > 1)
1141: addrinfo->loopset = YES;
1142: if (fixedaddress(lhs) && ISREGTYPE(lhs->vtype))
1143: {
1144: varinfo = getvar(addrinfo, lhs);
1145: if (addrinfo->freeuse) varinfo->isused = YES;
1146: varinfo->isset = YES;
1147: if (!addrinfo->freeuse && !varinfo->isused)
1148: varinfo->setfirst = YES;
1149: }
1150: }
1151: }
1152: else
1153: badtag ("regalloc:scanassign", ep->leftp->tag);
1154: }
1155:
1156:
1157:
1158: LOCAL scanopeq(ep)
1159: Exprp ep;
1160:
1161: {
1162: Addrp lhs;
1163: ADDRNODE *addrinfo;
1164: VARNODE *varinfo;
1165:
1166: scanvars(ep->rightp);
1167: if (ep->leftp->tag == TADDR)
1168: {
1169: lhs = (Addrp) ep->leftp;
1170: scanvars(lhs->vleng);
1171: scanvars(lhs->memoffset);
1172: if ((lhs->vstg == STGREG) || (lhs->vstg == STGPREG))
1173: return;
1174: if (ISVAR(lhs))
1175: {
1176: addrinfo = getaddr(lhs);
1177: addrinfo->isset = YES;
1178: if (docount > 1)
1179: addrinfo->loopset = YES;
1180: if (fixedaddress(lhs))
1181: {
1182: if (ISREGTYPE(lhs->vtype))
1183: {
1184: varinfo = getvar(addrinfo, lhs);
1185: varinfo->isused = YES;
1186: varinfo->isset = YES;
1187: }
1188: }
1189: }
1190: else
1191: addrinfo->freeuse = YES;
1192: }
1193: else
1194: badtag ("regalloc:scanopeq", ep->leftp->tag);
1195: }
1196:
1197:
1198:
1199: LOCAL scancall(ep)
1200: Exprp ep;
1201:
1202: {
1203: Addrp lhs;
1204: chainp args;
1205: Addrp ap;
1206: VARNODE *varinfo;
1207: ADDRNODE *addrinfo;
1208:
1209: lhs = (Addrp) ep->leftp;
1210: scanvars(lhs->vleng);
1211: scanvars(lhs->memoffset);
1212:
1213: if (ep->rightp == NULL) return;
1214:
1215: if (lhs->vstg != STGINTR)
1216: {
1217: args = ep->rightp->listblock.listp;
1218: for (; args; args = args->nextp)
1219: {
1220: if (args->datap->tag == TADDR)
1221: {
1222: ap = (Addrp) args->datap;
1223: scanvars(ap->vleng);
1224: scanvars(ap->memoffset);
1225: if (!ISVAR(ap)) continue;
1226:
1227: addrinfo = getaddr(ap);
1228: addrinfo->isset = YES;
1229: if (docount > 1)
1230: addrinfo->loopset = YES;
1231: if (fixedaddress(ap))
1232: {
1233: varinfo = getvar(addrinfo, ap);
1234: if (ap->vstg != STGCONST)
1235: varinfo->isset = YES;
1236: varinfo->isused = YES;
1237: }
1238: else
1239: addrinfo->freeuse = YES;
1240: }
1241: else
1242: scanvars(args->datap);
1243: }
1244: }
1245: else
1246: scanvars(ep->rightp);
1247:
1248: return;
1249: }
1250:
1251:
1252:
1253: LOCAL int fixedaddress(ap)
1254: Addrp ap;
1255:
1256: {
1257: if (!ap->memoffset)
1258: return NO;
1259: return (ISCONST(ap->memoffset) && ISINT(ap->memoffset->headblock.vtype));
1260: }
1261:
1262:
1263:
1264: LOCAL countrefs(p)
1265: expptr p;
1266:
1267: {
1268: Addrp ap;
1269: ADDRNODE *addrinfo;
1270: VARNODE *varinfo;
1271: VARNODE *vp;
1272: chainp args;
1273:
1274: if (p == NULL) return;
1275:
1276: switch (p->tag)
1277: {
1278: case TCONST:
1279: return;
1280:
1281: case TEXPR:
1282: switch (p->exprblock.opcode)
1283: {
1284: case OPCALL:
1285: if (p->exprblock.leftp->tag != TADDR)
1286: badtag ("regalloc:countrefs", p->exprblock.leftp->tag);
1287: countrefs(p->exprblock.leftp->addrblock.vleng);
1288: countrefs(p->exprblock.leftp->addrblock.memoffset);
1289:
1290: if (p->exprblock.leftp->addrblock.vstg != STGINTR)
1291: {
1292: if (!commonunusable)
1293: if (linearcode)
1294: setcommon();
1295: else
1296: commonunusable = YES;
1297: if (p->exprblock.rightp == NULL) return;
1298: args = p->exprblock.rightp->listblock.listp;
1299: for (; args; args = args->nextp)
1300: if (args->datap->tag == TADDR)
1301: {
1302: ap = (Addrp) args->datap;
1303: countrefs(ap->vleng);
1304: countrefs(ap->memoffset);
1305: if (!ISVAR(ap) || ap->vstg == STGCONST) continue;
1306: addrinfo = lookupaddr(ap->vstg, ap->memno);
1307: if (ap->vstg == STGARG)
1308: addrinfo->refs++;
1309: for (vp = addrinfo->varlist; vp; vp = vp->link)
1310: if (linearcode)
1311: if (!insetlist(ap->vstg, ap->memno, vp->memoffset))
1312: if (addrinfo->istemp)
1313: vp->refs--;
1314: else
1315: {
1316: vp->refs -= 2;
1317: insertset(ap->vstg, ap->memno, vp->memoffset);
1318: }
1319: else
1320: vp->refs--;
1321: else
1322: {
1323: if (!addrinfo->istemp)
1324: vp->unusable = YES;
1325: }
1326: }
1327: else
1328: countrefs(args->datap);
1329: }
1330: else
1331: {
1332: if (p->exprblock.rightp == NULL) return;
1333: args = p->exprblock.rightp->listblock.listp;
1334: for (; args; args = args->nextp)
1335: if (args->datap->tag == TADDR)
1336: {
1337: ap = (Addrp) args->datap;
1338: countrefs(ap->vleng);
1339: countrefs(ap->memoffset);
1340: if (!ISVAR(ap) || ap->vstg == STGCONST) continue;
1341: addrinfo = lookupaddr(ap->vstg, ap->memno);
1342: addrinfo->refs++;
1343: for (vp = addrinfo->varlist; vp; vp = vp->link)
1344: if (!insetlist(ap->vstg, ap->memno, vp->memoffset))
1345: {
1346: vp->refs--;
1347: insertset(ap->vstg, ap->memno, vp->memoffset);
1348: }
1349: }
1350: else
1351: countrefs(args->datap);
1352: }
1353: return;
1354:
1355: case OPASSIGN:
1356: case OPPLUSEQ:
1357: case OPSTAREQ:
1358: countrefs(p->exprblock.vleng);
1359: countrefs(p->exprblock.rightp);
1360: ap = (Addrp) p->exprblock.leftp;
1361: if (fixedaddress(ap))
1362: if (globalbranch)
1363: {
1364: countrefs(ap->vleng);
1365: countrefs(ap->memoffset);
1366: }
1367: else
1368: countrefs(ap);
1369: else if (linearcode)
1370: {
1371: countrefs(ap);
1372: for (vp = lookupaddr(ap->vstg, ap->memno)->varlist;
1373: vp;
1374: vp = vp->link)
1375: vp->refs--;
1376: }
1377: else
1378: {
1379: countrefs(ap);
1380: for (vp = lookupaddr(ap->vstg, ap->memno)->varlist;
1381: vp;
1382: vp = vp->link)
1383: vp->unusable = YES;
1384: }
1385: return;
1386:
1387: default:
1388: countrefs(p->exprblock.vleng);
1389: countrefs(p->exprblock.leftp);
1390: countrefs(p->exprblock.rightp);
1391: return;
1392: }
1393:
1394: case TADDR:
1395: ap = (Addrp) p;
1396: countrefs(ap->vleng);
1397: countrefs(ap->memoffset);
1398: if (!ISVAR(ap)) return;
1399:
1400: addrinfo = lookupaddr(ap->vstg, ap->memno);
1401: if (ap->vstg == STGARG)
1402: addrinfo->refs++;
1403:
1404: if (fixedaddress(ap))
1405: {
1406: if (ISREGTYPE(ap->vtype))
1407: {
1408: varinfo = lookupvar(addrinfo, ap->memoffset->constblock.const.ci);
1409: varinfo->refs++;
1410: }
1411: }
1412: else
1413: for (vp = addrinfo->varlist; vp; vp = vp->link)
1414: if (!insetlist(ap->vstg, ap->memno, vp->memoffset))
1415: {
1416: vp->refs--;
1417: insertset(ap->vstg, ap->memno, vp->memoffset);
1418: }
1419: return;
1420:
1421: case TLIST:
1422: args = p->listblock.listp;
1423: for (; args; args = args->nextp)
1424: countrefs(args->datap);
1425: return;
1426:
1427: default:
1428: badtag ("regalloc:countrefs", p->tag);
1429: }
1430: }
1431:
1432:
1433:
1434: LOCAL regwrite(sp, p)
1435: Slotp sp;
1436: expptr p;
1437:
1438: {
1439: register int i;
1440: REGDATA *rp;
1441: chainp args;
1442: Addrp ap, ap1;
1443: int memoffset;
1444:
1445: if (p == NULL) return;
1446:
1447: switch (p->tag)
1448: {
1449: case TCONST:
1450: return;
1451:
1452: case TEXPR:
1453: switch (p->exprblock.opcode)
1454: {
1455: case OPCALL:
1456: ap = (Addrp) p->exprblock.leftp;
1457: regwrite(sp, ap->vleng);
1458: regwrite(sp, ap->memoffset);
1459: if (ap->vstg != STGINTR)
1460: {
1461: if (linearcode)
1462: {
1463: gensetcommon(sp);
1464: for (i = toplcv + 1; i <= topregvar; i++)
1465: if ((rp = regtab[i]) && (rp->vstg == STGCOMMON))
1466: regdefined[i] = NO;
1467: }
1468: if (p->exprblock.rightp == NULL) return;
1469: args = p->exprblock.rightp->listblock.listp;
1470: for (; args; args = args->nextp)
1471: if (args->datap->tag == TADDR)
1472: {
1473: ap = (Addrp) args->datap;
1474: regwrite(sp, ap->vleng);
1475: regwrite(sp, ap->memoffset);
1476: for (i = toplcv + 1; i <= topregvar; i++)
1477: if ((rp = regtab[i]) &&
1478: !rp->isarrayarg &&
1479: !rp->istemp &&
1480: (rp->vstg == ap->vstg) &&
1481: (rp->memno == ap->memno))
1482: {
1483: regdefined[i] = NO;
1484: if (!memdefined[i])
1485: {
1486: ap1 = (Addrp) cpexpr(rp->stgp);
1487: changetoreg(ap1, i);
1488: insertassign(sp, cpexpr(rp->stgp), ap1);
1489: memdefined[i] = YES;
1490: }
1491: }
1492: else if (rp->isarrayarg &&
1493: (ap->vstg == STGARG) &&
1494: (ap->memno == rp->memno))
1495: {
1496: ap->vstg = STGPREG;
1497: ap->memno = regnum[i];
1498: }
1499: }
1500: else
1501: regwrite(sp, args->datap);
1502: }
1503: else
1504: {
1505: if (p->exprblock.rightp == NULL) return;
1506: args = p->exprblock.rightp->listblock.listp;
1507: for (; args; args = args->nextp)
1508: if (args->datap->tag == TADDR)
1509: {
1510: ap = (Addrp) args->datap;
1511: regwrite(sp, ap->vleng);
1512: regwrite(sp, ap->memoffset);
1513: for (i = toplcv + 1; i <= topregvar; i++)
1514: if ((rp = regtab[i]) &&
1515: !rp->isarrayarg &&
1516: !rp->istemp &&
1517: (rp->vstg == ap->vstg) &&
1518: (rp->memno == ap->memno) &&
1519: !memdefined[i])
1520: {
1521: ap1 = (Addrp) cpexpr(rp->stgp);
1522: changetoreg(ap1, i);
1523: insertassign(sp, cpexpr(rp->stgp), ap1);
1524: memdefined[i] = YES;
1525: }
1526: else if (rp->isarrayarg &&
1527: (ap->vstg == STGARG) &&
1528: (rp->memno == ap->memno))
1529: {
1530: ap->vstg = STGPREG;
1531: ap->memno = regnum[i];
1532: }
1533: }
1534: else
1535: {
1536: regwrite(sp, args->datap);
1537: }
1538: }
1539: return;
1540:
1541: case OPASSIGN:
1542: case OPPLUSEQ:
1543: case OPSTAREQ:
1544: regwrite(sp, p->exprblock.vleng);
1545: regwrite(sp, p->exprblock.rightp);
1546: ap = (Addrp) p->exprblock.leftp;
1547: regwrite(sp, ap->vleng);
1548: regwrite(sp, ap->memoffset);
1549:
1550: if (ap->vstg == STGARG)
1551: for (i = toplcv + 1; i<=topregvar; i++)
1552: if ((rp = regtab[i]) &&
1553: rp->isarrayarg &&
1554: (rp->memno == ap->memno))
1555: {
1556: ap->vstg = STGPREG;
1557: ap->memno = regnum[i];
1558: return;
1559: }
1560:
1561: if (fixedaddress(ap))
1562: {
1563: memoffset = ap->memoffset->constblock.const.ci;
1564: for (i = toplcv + 1; i <= topregvar; i++)
1565: if ((rp = regtab[i]) &&
1566: !rp->isarrayarg &&
1567: (rp->vstg == ap->vstg) &&
1568: (rp->memno == ap->memno) &&
1569: (rp->memoffset == memoffset))
1570: {
1571: changetoreg(ap, i);
1572: if (globalbranch)
1573: {
1574: p->exprblock.rightp = (expptr) cpexpr(p);
1575: p->exprblock.leftp = (expptr) cpexpr(rp->stgp);
1576: p->exprblock.opcode = OPASSIGN;
1577: memdefined[i] = YES;
1578: }
1579: else
1580: {
1581: regaltered[i] = YES;
1582: regdefined[i] = YES;
1583: }
1584: }
1585: return;
1586: }
1587:
1588: if (linearcode)
1589: for (i = toplcv + 1; i <= topregvar; i++)
1590: if ((rp = regtab[i]) &&
1591: !rp->isarrayarg &&
1592: (rp->vstg == ap->vstg) &&
1593: (rp->memno == ap->memno))
1594: regdefined[i] = NO;
1595: return;
1596:
1597: default:
1598: regwrite(sp, p->exprblock.vleng);
1599: regwrite(sp, p->exprblock.leftp);
1600: regwrite(sp, p->exprblock.rightp);
1601: return;
1602: }
1603:
1604: case TADDR:
1605: ap = (Addrp) p;
1606: regwrite(sp, ap->vleng);
1607: regwrite(sp, ap->memoffset);
1608:
1609: if (ap->vstg == STGARG)
1610: for (i = toplcv + 1; i <= topregvar; i++)
1611: if ((rp = regtab[i]) &&
1612: rp->isarrayarg &&
1613: (rp->memno == ap->memno))
1614: {
1615: ap->vstg = STGPREG;
1616: ap->memno = regnum[i];
1617: return;
1618: }
1619:
1620: if (fixedaddress(ap))
1621: {
1622: memoffset = ap->memoffset->constblock.const.ci;
1623: for (i = toplcv + 1; i <= topregvar; i++)
1624: if ((rp = regtab[i]) &&
1625: !rp->isarrayarg &&
1626: (rp->vstg == ap->vstg) &&
1627: (rp->memno == ap->memno) &&
1628: (rp->memoffset == memoffset))
1629: {
1630: changetoreg(ap, i);
1631: return;
1632: }
1633: }
1634: else
1635: {
1636: for (i = toplcv + 1; i <= topregvar; i++)
1637: if ((rp = regtab[i]) &&
1638: !rp->isarrayarg &&
1639: (rp->vstg == ap->vstg) &&
1640: (rp->memno == ap->memno) &&
1641: !memdefined[i])
1642: {
1643: ap1 = (Addrp) cpexpr(rp->stgp);
1644: changetoreg(ap1, i);
1645: insertassign(sp, cpexpr(rp->stgp), ap1);
1646: memdefined[i] = YES;
1647: }
1648: }
1649: return;
1650:
1651: case TLIST:
1652: for (args = p->listblock.listp; args; args = args->nextp)
1653: regwrite(sp, args->datap);
1654: return;
1655:
1656: default:
1657: badtag ("regalloc:regwrite", p->tag);
1658: }
1659: }
1660:
1661:
1662:
1663: LOCAL setcommon()
1664:
1665: {
1666: ADDRNODE *ap;
1667: VARNODE *vp;
1668:
1669: for (ap = commonvars; ap; ap = ap->commonlink)
1670: for (vp = ap->varlist; vp; vp = vp->link)
1671: if (!insetlist(ap->vstg, ap->memno, vp->memoffset))
1672: {
1673: vp->refs -= 2;
1674: insertset(ap->vstg, ap->memno, vp->memoffset);
1675: }
1676: else
1677: vp->refs--;
1678:
1679: return;
1680: }
1681:
1682:
1683:
1684: LOCAL setall()
1685:
1686: {
1687: register int i;
1688: register ADDRNODE *p;
1689: register VARNODE *q;
1690:
1691: for (i = 0; i < VARTABSIZE; i++)
1692: for (p = vartable[i]; p; p = p->link)
1693: if (p->istemp || !p->isset)
1694: break;
1695: else
1696: for (q = p->varlist; q; q = q->link)
1697: if (q->isset && !insetlist(p->vstg, p->memno, q->memoffset))
1698: q->refs--;
1699:
1700: allset = YES;
1701: return;
1702: }
1703:
1704:
1705:
1706: LOCAL int samevar(r1, r2)
1707: register REGDATA *r1;
1708: register REGNODE *r2;
1709:
1710: {
1711: if ((r1->vstg != r2->vstg) ||
1712: (r1->memno != r2->memno) ||
1713: (r1->isarrayarg != r2->isarrayarg))
1714: return NO;
1715: if (r1->isarrayarg)
1716: return YES;
1717: return (r1->memoffset == r2->memoffset);
1718: }
1719:
1720:
1721:
1722: LOCAL entableaddr(p)
1723: ADDRNODE *p;
1724:
1725: {
1726: int refs;
1727: Addrp ap;
1728: register int i;
1729:
1730: if (p->vstg != STGARG)
1731: {
1732: currentaddr = p;
1733: return;
1734: }
1735:
1736: refs = p->refs;
1737: if (refs <= 0) return;
1738:
1739: if (tabletop < 0)
1740: tabletop = i = 0;
1741: else if (refs > rt[tabletop]->refs)
1742: {
1743: if (tabletop + 1 < TABLELIMIT)
1744: tabletop++;
1745: else
1746: {
1747: frexpr(rt[tabletop]->stgp);
1748: free((char *) rt[tabletop]);
1749: }
1750:
1751: for (i = tabletop; i > 0; i--)
1752: if (refs > rt[i - 1]->refs)
1753: rt[i] = rt[i - 1];
1754: else
1755: break;
1756: }
1757: else if (tabletop + 1 < TABLELIMIT)
1758: i = ++tabletop;
1759: else
1760: return;
1761:
1762: rt[i] = ALLOC(regdata);
1763: rt[i]->vstg = p->vstg;
1764: rt[i]->vtype = p->vtype;
1765: rt[i]->memno = p->memno;
1766: rt[i]->refs = refs;
1767: rt[i]->isarrayarg = YES;
1768:
1769: return;
1770: }
1771:
1772:
1773:
1774:
1775: LOCAL entablevar(p)
1776: VARNODE *p;
1777:
1778: {
1779: int refs;
1780: register int i;
1781:
1782: if (p->unusable) return;
1783: refs = p->refs - loopcost;
1784: if (refs <= 0) return;
1785:
1786: if (tabletop < 0)
1787: tabletop = i = 0;
1788: else if (refs > rt[tabletop]->refs
1789: #ifdef BUMPREALS /* put floats last */
1790: || currentaddr->vtype!=TYREAL && rt[tabletop]->vtype==TYREAL && !rt[tabletop]->isarrayarg
1791: #endif
1792: ){
1793: if (tabletop + 1 < TABLELIMIT)
1794: tabletop++;
1795: else
1796: {
1797: frexpr(rt[tabletop]->stgp);
1798: free((char *) rt[tabletop]);
1799: }
1800:
1801: for (i = tabletop; i > 0; i--)
1802: if (refs > rt[i - 1]->refs
1803: #ifdef BUMPREALS /* put floats last */
1804: || currentaddr->vtype!=TYREAL && rt[i-1]->vtype==TYREAL && !rt[i-1]->isarrayarg
1805: #endif
1806: )
1807: rt[i] = rt[i - 1];
1808: else
1809: break;
1810: }
1811: else if (tabletop + 1 < TABLELIMIT)
1812: i = ++tabletop;
1813: else
1814: return;
1815:
1816: rt[i] = ALLOC(regdata);
1817: rt[i]->vstg = currentaddr->vstg;
1818: rt[i]->vtype = currentaddr->vtype;
1819: rt[i]->memno = currentaddr->memno;
1820: rt[i]->memoffset = p->memoffset;
1821: rt[i]->refs = refs;
1822: rt[i]->stgp = (Addrp) cpexpr(p->stgp);
1823: rt[i]->isarrayarg = NO;
1824: rt[i]->istemp = currentaddr->istemp;
1825: rt[i]->isset = p->isset;
1826: rt[i]->setfirst = p->setfirst;
1827:
1828: return;
1829: }
1830:
1831:
1832:
1833: LOCAL int inregtab(p)
1834: register REGDATA *p;
1835:
1836: {
1837: register REGDATA *rp;
1838: register int i;
1839:
1840: for (i = 0; i <= topregvar; i++)
1841: if (rp = regtab[i])
1842: if ((rp->vstg == p->vstg) &&
1843: (rp->memno == p->memno) &&
1844: (rp->isarrayarg == p->isarrayarg))
1845: if (rp->isarrayarg)
1846: return YES;
1847: else if (rp->memoffset == p->memoffset)
1848: return YES;
1849:
1850: return NO;
1851: }
1852:
1853:
1854:
1855: LOCAL changetoreg(ap, i)
1856: register Addrp ap;
1857: int i;
1858:
1859: {
1860: ap->vstg = STGREG;
1861: ap->memno = regnum[i];
1862: frexpr(ap->memoffset);
1863: ap->memoffset = ICON(0);
1864: ap->istemp = NO;
1865: return;
1866: }
1867:
1868:
1869:
1870: LOCAL insertassign(sp, dest, src)
1871: Slotp sp;
1872: Addrp dest;
1873: expptr src;
1874:
1875: {
1876: Slotp newslot;
1877: expptr p;
1878:
1879: p = mkexpr(OPASSIGN, dest, src);
1880: newslot = optinsert (SKEQ,p,0,0,sp);
1881:
1882: if (sp == dohead)
1883: if (!newcode)
1884: newcode = newslot;
1885:
1886: return;
1887: }
1888:
1889:
1890: LOCAL appendassign(sp, dest, src)
1891: Slotp sp;
1892: Addrp dest;
1893: expptr src;
1894:
1895: {
1896: Slotp newslot;
1897: expptr p;
1898:
1899: if (!sp)
1900: fatal ("regalloc:appendassign");
1901:
1902: p = mkexpr(OPASSIGN, dest, src);
1903: newslot = optinsert (SKEQ,p,0,0,sp->next);
1904:
1905: return;
1906: }
1907:
1908:
1909:
1910: LOCAL int regtomem(sp)
1911: Slotp sp;
1912:
1913: {
1914: expptr p, l, r;
1915: int i;
1916:
1917: if (sp->type != SKEQ) return NO;
1918:
1919: p = sp->expr;
1920: if ((p->tag != TEXPR) || (p->exprblock.opcode != OPASSIGN))
1921: return NO;
1922:
1923: r = p->exprblock.rightp;
1924: if ((r->tag != TADDR) || (r->addrblock.vstg != STGREG))
1925: return NO;
1926:
1927: l = p->exprblock.leftp;
1928: if (l->tag != TADDR)
1929: return NO;
1930: i = r->addrblock.memno;
1931: if (regtab[i] &&
1932: (l->addrblock.vstg == regtab[i]->vstg) &&
1933: (l->addrblock.memno == regtab[i]->memno) &&
1934: fixedaddress(l) &&
1935: (l->addrblock.memoffset->constblock.const.ci == regtab[i]->memoffset))
1936: return YES;
1937:
1938: return NO;
1939: }
1940:
1941:
1942:
1943: LOCAL int regtoreg(sp)
1944: Slotp sp;
1945:
1946: {
1947: expptr p, l, r;
1948:
1949: if (sp->type != SKEQ) return NO;
1950:
1951: p = sp->expr;
1952: if ((p->tag != TEXPR) || (p->exprblock.opcode != OPASSIGN))
1953: return NO;
1954:
1955: l = p->exprblock.leftp;
1956: if ((l->tag != TADDR) || (l->addrblock.vstg != STGREG))
1957: return NO;
1958:
1959: r = p->exprblock.rightp;
1960: if ((r->tag == TADDR) &&
1961: (r->addrblock.vstg == STGREG) &&
1962: (r->addrblock.memno == l->addrblock.memno))
1963: return YES;
1964:
1965: if ((r->tag == TEXPR) &&
1966: (r->exprblock.opcode == OPADDR) &&
1967: (r->exprblock.leftp->tag == TADDR) &&
1968: (r->exprblock.leftp->addrblock.vstg == STGPREG) &&
1969: (r->exprblock.leftp->addrblock.memno == l->addrblock.memno))
1970: return YES;
1971:
1972: return NO;
1973: }
1974:
1975:
1976:
1977: LOCAL deleteslot(sp)
1978: Slotp sp;
1979:
1980: {
1981: if (newcode == sp)
1982: {
1983: newcode = sp->next;
1984: if (newcode == dohead)
1985: newcode = NULL;
1986: }
1987:
1988: delslot (sp);
1989: return;
1990: }
1991:
1992:
1993:
1994: LOCAL gensetall(sp)
1995: Slotp sp;
1996:
1997: {
1998: register int i;
1999: register REGDATA *rp;
2000: register Addrp ap;
2001:
2002: for (i = toplcv + 1; i <= topregvar; i++)
2003: if (rp = regtab[i])
2004: if (rp->isset && !(rp->istemp || rp->isarrayarg))
2005: if (!memdefined[i])
2006: {
2007: ap = (Addrp) cpexpr(rp->stgp);
2008: changetoreg(ap, i);
2009: insertassign(sp, cpexpr(rp->stgp), ap);
2010: memdefined[i] = YES;
2011: }
2012:
2013: return;
2014: }
2015:
2016:
2017: LOCAL gensetcommon(sp)
2018: Slotp sp;
2019:
2020: {
2021: register int i;
2022: register REGDATA *rp;
2023: register Addrp ap;
2024:
2025: for (i = toplcv + 1; i <= topregvar; i++)
2026: if (rp = regtab[i])
2027: if ((rp->vstg == STGCOMMON) && !rp->isarrayarg)
2028: if (!memdefined[i])
2029: {
2030: ap = (Addrp) cpexpr(rp->stgp);
2031: changetoreg(ap, i);
2032: insertassign(sp, cpexpr(rp->stgp), ap);
2033: memdefined[i] = YES;
2034: }
2035:
2036: return;
2037: }
2038:
2039:
2040: LOCAL gensetreturn(sp)
2041: Slotp sp;
2042:
2043: {
2044: register int i;
2045: register REGDATA *rp;
2046: register Addrp ap;
2047:
2048: for (i = toplcv + 1; i <= topregvar; i++)
2049: if (rp = regtab[i])
2050: if (((rp->vstg == STGCOMMON) && !rp->isarrayarg)
2051: || (rp->isset && (saveall || rp->stgp->issaved) && !(rp->istemp || rp->isarrayarg)))
2052: if (!memdefined[i])
2053: {
2054: ap = (Addrp) cpexpr(rp->stgp);
2055: changetoreg(ap, i);
2056: insertassign(sp, cpexpr(rp->stgp), ap);
2057: memdefined[i] = YES;
2058: }
2059:
2060: return;
2061: }
2062:
2063:
2064:
2065: LOCAL clearmems()
2066:
2067: {
2068: REGDATA *rp;
2069: register int i;
2070:
2071: for (i = 0; i <= toplcv; i++)
2072: memdefined[i] = YES;
2073: for (; i <= topregvar; i++)
2074: if ((rp = regtab[i]) && rp->isset)
2075: memdefined[i] = NO;
2076: else
2077: memdefined[i] = YES;
2078: return;
2079: }
2080:
2081:
2082: LOCAL setregs()
2083:
2084: {
2085: register int i;
2086:
2087: for (i = 0; i <= topregvar; i++)
2088: regdefined[i] = YES;
2089: return;
2090: }
2091:
2092:
2093:
2094: regalloc()
2095:
2096: {
2097: int match;
2098: Slotp nextslot;
2099: Slotp sl1,sl2;
2100: Slotp lastlabslot;
2101:
2102: if (! optimflag) return;
2103:
2104: docount = 0;
2105: lastlabslot = NULL;
2106: for (sl1 = firstslot; sl1; sl1 = nextslot)
2107: {
2108: nextslot = sl1->next;
2109: switch (sl1->type)
2110: {
2111:
2112: /* temporarily commented out -----
2113: case SKLABEL:
2114: lastlabslot = sl1;
2115: break;
2116:
2117: case SKGOTO:
2118: if (lastlabslot && sl1->label == lastlabslot->label)
2119: {
2120: dohead = lastlabslot;
2121: doend = sl1;
2122: alreg ();
2123: }
2124: break;
2125: ----- */
2126:
2127: case SKDOHEAD:
2128: ++docount;
2129: pushq (sl1);
2130: break;
2131:
2132: case SKENDDO:
2133: --docount;
2134: match = 0;
2135: for (sl2 = sl1; sl2; sl2 = sl2->prev)
2136: {
2137: if (sl2->type == SKDOHEAD) match++;
2138: else if (sl2->type == SKENDDO) match--;
2139: if (match == 0) break;
2140: }
2141: if (sl2)
2142: dohead = sl2;
2143: else
2144: fatal ("unmatched enddo in code buffer");
2145: if (sl2->type != SKDOHEAD)
2146: fatal ("internal error in regalloc");
2147:
2148: for (dqptr = dqbottom; dqptr; dqptr = dqptr->up)
2149: {
2150: if (dqptr->dohead == dohead)
2151: break;
2152: }
2153:
2154: if (!dqptr)
2155: fatal ("garbled doqueue in regalloc");
2156:
2157: /* sl1 now points to the SKENDDO slot; the SKNULL slot
2158: * is reached through sl1->nullslot
2159: */
2160: dqptr->doend = (Slotp) sl1->nullslot;
2161: if (docount == 0)
2162: {
2163: for (dqptr = dqbottom; dqptr; dqptr = dqptr->up)
2164: {
2165: dohead = dqptr->dohead;
2166: doend = dqptr->doend;
2167: alreg();
2168: }
2169: while (dqtop)
2170: popq(dqtop->dohead);
2171: docount = 0;
2172: }
2173: break;
2174:
2175: default:
2176: break;
2177: }
2178: }
2179:
2180: return;
2181: }
2182:
2183:
2184:
2185: LOCAL pushq(sp)
2186: Slotp sp;
2187:
2188: {
2189: DOQUEUE *t;
2190:
2191: if (sp->type != SKDOHEAD)
2192: fatal("regalloc:pushq: DO statement expected");
2193:
2194: if (dqbottom)
2195: {
2196: t = ALLOC(doqueue);
2197: t->up = dqbottom;
2198: dqbottom->down = t;
2199: dqbottom = t;
2200: }
2201: else
2202: dqtop = dqbottom = ALLOC(doqueue);
2203:
2204: dqbottom->dohead = sp;
2205: }
2206:
2207:
2208: LOCAL popq(sp)
2209: Slotp sp;
2210:
2211: {
2212: DOQUEUE *t;
2213: register int i;
2214:
2215: if (!dqtop)
2216: fatal("regalloc:popq: empty DO queue");
2217: if (dqtop->dohead != sp)
2218: fatal("regalloc:popq: garbled DO queue");
2219:
2220: t = dqtop;
2221:
2222: dqtop = t->down;
2223: if (dqtop)
2224: dqtop->up = NULL;
2225: else
2226: dqbottom = NULL;
2227: for (i = 0; i < MAXREGVAR; i++)
2228: if (t->reg[i])
2229: free((char *) t->reg[i]);
2230: free(t);
2231: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.