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