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