![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to optloop.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Power 6/32 Unix Tahoe 4.2BSD] / cci / usr / src / usr.bin / f77 / f77pass1|
Return to optloop.c CVS log | Up to [Power 6/32 Unix Tahoe 4.2BSD] / cci / usr / src / usr.bin / f77 / 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[] = "@(#)optloop.c 5.1 (Berkeley) 6/7/85";
9: #endif not lint
10:
11: /*
12: * optloop.c
13: *
14: * Loop optimizations, f77 compiler pass 1, 4.2 BSD.
15: *
16: * University of Utah CS Dept. modification history:
17: *
18: * $Log: optloop.c,v $
19: * Revision 1.3 86/02/12 15:28:42 rcs
20: * 4.3 F77. C. Keating.
21: *
22: * Revision 1.4 84/10/25 01:27:29 donn
23: * Fixed a subtle bug in removesafe(). When the moved code is an assignment
24: * into a temporary, we use the lhs to substitute for the expression inside
25: * the loop. Previously the data structure for the temporary was not copied,
26: * so later on when the lhs was freed, the substitute was too, turning it
27: * into garbage.
28: *
29: * Revision 1.3 84/08/05 17:04:03 donn
30: * Changed worthcost() so that it skips variable length strings -- we can't
31: * make temporaries for these...
32: *
33: * Revision 1.2 84/07/19 11:50:39 donn
34: * Installed changes to force non-intrinsic subroutines and functions to define
35: * their arguments (make them ineligible for optimization), function setsuses.
36: * Fix from A.F.
37: *
38: */
39:
40: #include "defs.h"
41: #include "optim.h"
42:
43:
44: #define SCFREE 0
45: #define SCSAFE 1
46:
47:
48:
49: typedef
50: struct varblock
51: {
52: struct varblock *next;
53: field vstg;
54: int memno; /* holds memalloc for TTEMP */
55: short sets;
56: short uses;
57: field setfirst;
58: } VARBLOCK;
59:
60: typedef VARBLOCK *Varp;
61:
62: #define TABLESIZE 59
63:
64: LOCAL Varp table[TABLESIZE];
65:
66:
67:
68: LOCAL Varp mkbucket(vstg,memno)
69: field vstg;
70: int memno;
71:
72: {
73: Varp q;
74:
75: q = ALLOC(varblock);
76: q->vstg = vstg;
77: q->memno = memno;
78: return q;
79: }
80:
81:
82:
83: LOCAL Varp lookup(p)
84: tagptr p;
85:
86: {
87: int vstg, memno;
88: int key;
89: Varp q, r;
90:
91: switch (p->tag)
92: {
93: case TTEMP:
94: vstg = 0;
95: memno = (int) p->tempblock.memalloc;
96: break;
97:
98: case TADDR:
99: vstg = p->addrblock.vstg;
100: memno = p->addrblock.memno;
101: break;
102:
103: default:
104: badtag ("lookup",p->tag);
105: }
106: key = memno % TABLESIZE;
107: q = table[key];
108:
109: if (q)
110: {
111: for (; q; r = q, q = q->next)
112: if ((q->vstg == vstg) && (q->memno == memno))
113: return q;
114: return r->next = mkbucket(vstg,memno);
115: }
116: else
117: return table[key] = mkbucket(vstg,memno);
118: }
119:
120:
121:
122: LOCAL freetable()
123:
124: {
125: int i;
126: Varp p, q;
127:
128: for (i = 0; i < TABLESIZE; i++)
129: if (table[i])
130: {
131: p = table[i];
132: table[i] = NULL;
133:
134: while (p)
135: {
136: q = p->next;
137: free((char *) p);
138: p = q;
139: }
140: }
141: }
142:
143:
144:
145: Slotp newcode;
146: Slotp dohead, doend;
147: LOCAL Slotp first, last;
148: LOCAL commonset;
149: LOCAL int comocount; /* count of number of code motions done */
150:
151:
152: optloops()
153:
154: {
155: int match;
156: Slotp nextslot;
157: Slotp sl1,sl2;
158: Slotp lastlabslot;
159: int lab;
160:
161: if (! optimflag) return;
162: if (debugflag[6]) return;
163:
164: lastlabslot = NULL;
165: comocount = 0;
166: for (sl1 = firstslot; sl1; sl1 = nextslot)
167: {
168: nextslot = sl1->next;
169: switch (sl1->type)
170: {
171: case SKLABEL:
172: lastlabslot = sl1;
173: break;
174:
175: case SKGOTO:
176: if (lastlabslot && sl1->label == lastlabslot->label)
177: {
178: lab = newlabel ();
179: first = optinsert (SKLABEL,0,lab,0,lastlabslot->next);
180: last = sl1;
181: last->label = lab;
182: optloop ();
183: }
184: break;
185:
186: case SKDOHEAD:
187: match = 0;
188: for (sl2 = sl1; sl2; sl2 = sl2->next)
189: {
190: if (sl2->type == SKDOHEAD) match++;
191: else if (sl2->type == SKENDDO) match--;
192: if (match == 0) break;
193: }
194: if (sl2)
195: last = sl2;
196: else
197: fatal ("unmatched do in code buffer");
198: if (sl2->type != SKENDDO)
199: fatal ("internal error in optloops");
200:
201: /* last now points to the SKENDDO slot; the SKNULL slot
202: * is reached through last->nullslot
203: */
204: last = (Slotp) last->nullslot;
205:
206: first = sl1;
207:
208: optloop ();
209: break;
210:
211: default:
212: break;
213: }
214: }
215:
216: if (debugflag[0])
217: fprintf (diagfile,"%d code motion%s performed\n",comocount,
218: (comocount==1 ? "" : "s") );
219: return;
220: }
221:
222:
223:
224: optloop()
225:
226: {
227: newcode = NULL;
228:
229: modify();
230:
231: return;
232: }
233:
234:
235: LOCAL modify()
236:
237: {
238: Slotp sp;
239: int s;
240:
241: scanvars();
242:
243: for (sp = first; sp != last->next; sp = sp->next)
244: switch (sp->type)
245: {
246: case SKEQ:
247: s = anex(sp->expr);
248: if (s == SCSAFE)
249: removesafe (&sp->expr);
250: break;
251:
252: case SKARIF:
253: case SKASGOTO:
254: case SKCALL:
255: case SKCMGOTO:
256: case SKIFN:
257: case SKSTOP:
258: case SKRETURN:
259: case SKPAUSE:
260: case SKIOIFN:
261: s = anex(sp->expr);
262: if (s == SCSAFE)
263: removesafe(&sp->expr);
264: break;
265:
266: default:
267: break;
268: }
269:
270: freetable();
271: return;
272: }
273:
274:
275: LOCAL scanvars()
276:
277: {
278: Slotp sp;
279: Varp varinfo;
280: int i;
281: Varp p;
282:
283: commonset = NO;
284:
285: for (sp = first; sp != last->next; sp = sp->next)
286: {
287: switch (sp->type)
288: {
289: case SKARIF:
290: case SKASGOTO:
291: case SKCALL:
292: case SKCMGOTO:
293: case SKIFN:
294: case SKSTOP:
295: case SKRETURN:
296: case SKPAUSE:
297: case SKIOIFN:
298: case SKEQ:
299: setsuses(sp->expr);
300: break;
301:
302: default:
303: break;
304: }
305: }
306:
307: if (commonset)
308: for (i = 0; i < TABLESIZE; i++)
309: for (p = table[i]; p; p = p->next)
310: if (p->vstg == STGCOMMON)
311: {
312: p->sets++;
313: p->setfirst = NO;
314: }
315: }
316:
317:
318: LOCAL setsuses(p)
319: expptr p;
320:
321: {
322: Addrp lhs;
323: Varp varinfo;
324: chainp args;
325:
326: if (!p) return;
327:
328: switch (p->tag)
329: {
330: case TEXPR:
331: switch (p->exprblock.opcode)
332: {
333: default:
334: setsuses(p->exprblock.leftp);
335: setsuses(p->exprblock.rightp);
336: setsuses(p->exprblock.vleng);
337: break;
338:
339: case OPASSIGN:
340: switch (p->exprblock.leftp->tag)
341: {
342: case TTEMP:
343: lhs = (Addrp) p->exprblock.leftp;
344: goto taddr;
345:
346: case TADDR:
347: lhs = (Addrp) p->exprblock.leftp;
348: setsuses(lhs->memoffset);
349: setsuses(lhs->vleng);
350: taddr:
351: setsuses(p->exprblock.rightp);
352: setsuses(p->exprblock.vleng);
353: varinfo = lookup(lhs);
354: varinfo->sets++;
355: if (varinfo->uses == 0)
356: varinfo->setfirst = YES;
357: break;
358:
359: default:
360: fatal("O6: l-value expected");
361: }
362: break;
363:
364: case OPSTAREQ:
365: case OPPLUSEQ:
366: switch (p->exprblock.leftp->tag)
367: {
368: case TADDR:
369: lhs = (Addrp) p->exprblock.leftp;
370: break;
371: case TTEMP:
372: lhs = (Addrp) p->exprblock.leftp;
373: break;
374: default:
375: fatal("O7: l-value expected");
376: }
377: setsuses(p->exprblock.leftp);
378: setsuses(p->exprblock.rightp);
379: setsuses(p->exprblock.vleng);
380: varinfo = lookup(lhs);
381: varinfo->sets++;
382: break;
383:
384: case OPCALL:
385: if (p->exprblock.leftp->tag != TADDR)
386: fatal("O8: subprogram expected");
387: setsuses(p->exprblock.rightp);
388: setsuses(p->exprblock.vleng);
389: if (p->exprblock.leftp->addrblock.vstg == STGINTR) break;
390: commonset = YES;
391: if (p->exprblock.rightp == NULL) break;
392: args = p->exprblock.rightp->listblock.listp;
393: for (; args; args = args->nextp)
394: if (args->datap->tag == TADDR)
395: {
396: lhs = (Addrp) args->datap;
397: switch (lhs->vstg)
398: {
399: case STGARG:
400: case STGAUTO:
401: case STGBSS:
402: case STGINIT:
403: case STGCOMMON:
404: case STGEQUIV:
405: case STGREG:
406: case STGPREG:
407: varinfo = lookup(lhs);
408: varinfo->sets++;
409: }
410: }
411: else if (args->datap->tag == TTEMP)
412: {
413: lhs = (Addrp) args->datap;
414: varinfo = lookup (lhs);
415: varinfo->sets++;
416: }
417: break;
418: }
419:
420: return;
421:
422: case TTEMP:
423: varinfo = lookup((Addrp) p);
424: varinfo->uses++;
425: return;
426:
427: case TADDR:
428: setsuses(p->addrblock.memoffset);
429: setsuses(p->addrblock.vleng);
430: varinfo = lookup((Addrp) p);
431: varinfo->uses++;
432: return;
433:
434: case TLIST:
435: for (args = p->listblock.listp; args; args = args->nextp)
436: setsuses(args->datap);
437:
438: case TCONST:
439: case TERROR:
440: return;
441:
442: default:
443: fatal("O9: bad tag value");
444: }
445: }
446:
447:
448: LOCAL int anex(p)
449: expptr p;
450:
451: {
452: int s1, s2, s3;
453: expptr q;
454: Varp varinfo;
455: chainp ch;
456: int setfirst;
457: expptr expr;
458:
459:
460: if (p == ENULL)
461: return SCSAFE;
462:
463: switch (p->tag)
464: {
465: case TCONST:
466: return SCSAFE;
467:
468: case TLIST:
469: for (ch = p->listblock.listp; ch; ch = ch->nextp)
470: {
471: s1 = anex (ch->datap);
472: if (s1 == SCSAFE)
473: removesafe (&ch->datap);
474: }
475: return SCFREE;
476:
477: case TEXPR:
478: s1 = anex(p->exprblock.leftp);
479: s2 = anex(p->exprblock.rightp);
480: s3 = anex(p->exprblock.vleng);
481:
482: switch (p->exprblock.opcode)
483: {
484: case OPASSIGN:
485: expr = p->exprblock.leftp;
486: varinfo = lookup(expr);
487: setfirst = varinfo->setfirst && (varinfo->sets == 1);
488: if (expr->tag == TTEMP && setfirst &&
489: s2 == SCSAFE && s3 == SCSAFE)
490: {
491: movefrtemp (expr);
492: return SCSAFE;
493: }
494: else
495: {
496: if (s2 == SCSAFE) removesafe (&p->exprblock.rightp);
497: if (s3 == SCSAFE) removesafe (&p->exprblock.vleng);
498: return SCFREE;
499: }
500:
501: case OPNEG:
502: case OPNOT:
503: case OPABS:
504: case OPADDR:
505: case OPBITNOT:
506: if ((s2 == SCSAFE) && (s3 == SCSAFE))
507: return s1;
508: else
509: return SCFREE;
510:
511: case OPCONV:
512: if ((s2 != SCSAFE) || (s3 != SCSAFE))
513: return SCFREE;
514:
515: if (ISINT(p->exprblock.vtype))
516: return s1;
517: if (ISINT(p->exprblock.leftp->headblock.vtype))
518: return s1;
519:
520: return SCFREE;
521:
522:
523: case OPSTAR:
524: if (ISINT(p->exprblock.vtype))
525: goto safeop;
526:
527: if (safefactor(p->exprblock.leftp) ||
528: safefactor(p->exprblock.rightp))
529: goto safeop;
530:
531: goto floatop;
532:
533:
534: case OPPLUS:
535: case OPMINUS:
536: if (ISINT(p->exprblock.vtype))
537: goto safeop;
538:
539: floatop:
540: if (!(ISREAL(p->exprblock.vtype) || ISCOMPLEX(p->exprblock.vtype)))
541: return SCFREE;
542:
543: switch (s1)
544: {
545: case SCSAFE:
546: removesafe(&p->exprblock.leftp);
547: if (s2 == SCSAFE)
548: removesafe(&p->exprblock.leftp);
549: return SCFREE;
550:
551: case SCFREE:
552: if (s2 == SCSAFE)
553: removesafe(&p->exprblock.rightp);
554: return SCFREE;
555: }
556:
557: case OPOR:
558: case OPAND:
559: case OPEQV:
560: case OPNEQV:
561: case OPLT:
562: case OPEQ:
563: case OPGT:
564: case OPLE:
565: case OPNE:
566: case OPGE:
567: case OPLSHIFT:
568: case OPMIN:
569: case OPMAX:
570: case OPBITOR:
571: case OPBITAND:
572: case OPBITXOR:
573: case OPRSHIFT:
574: safeop:
575: if ((p->exprblock.vleng != ENULL) && ( ! ISCONST(p->exprblock.vleng)))
576: return SCFREE;
577:
578: switch (s1)
579: {
580: case SCSAFE:
581: if (s2 == SCFREE) removesafe (&p->exprblock.leftp);
582: return s2;
583:
584: case SCFREE:
585: if (s2 == SCSAFE) removesafe (&p->exprblock.rightp);
586: return SCFREE;
587: }
588:
589: default:
590: if (s1 == SCSAFE) removesafe(&p->exprblock.leftp);
591: if (s2 == SCSAFE) removesafe(&p->exprblock.rightp);
592: if (s3 == SCSAFE) removesafe(&p->exprblock.vleng);
593: return SCFREE;
594: }
595:
596:
597: case TTEMP:
598: varinfo = lookup(p);
599: if (varinfo->sets == 0)
600: return SCSAFE;
601: else
602: return SCFREE;
603:
604: case TADDR:
605: s1 = anex(p->addrblock.memoffset);
606: s2 = anex(p->addrblock.vleng);
607:
608: varinfo = lookup(p);
609:
610: if (varinfo->sets == 0)
611: switch (s1)
612: {
613: case SCSAFE:
614: if (s2 == SCFREE) removesafe(&p->addrblock.memoffset);
615: return s2;
616:
617: case SCFREE:
618: if (s2 == SCSAFE) removesafe(&p->addrblock.vleng);
619: return SCFREE;
620: }
621:
622: if (s1 == SCSAFE) removesafe(&p->addrblock.memoffset);
623: if (s2 == SCSAFE) removesafe(&p->addrblock.vleng);
624: return SCFREE;
625:
626:
627: default:
628: return SCFREE;
629: }
630: }
631:
632:
633: LOCAL safefactor(p)
634: expptr p;
635:
636: {
637: if ( ! ISCONST(p))
638: return NO;
639:
640: if (ISINT(p->constblock.vtype))
641: if (abs(p->constblock.const.ci) <= 1)
642: return YES;
643:
644: if (ISREAL(p->constblock.vtype))
645: if (abs(p->constblock.const.cd[0]) <= 1.0)
646: return YES;
647:
648: return NO;
649: }
650:
651:
652: LOCAL int worthcost(p)
653: expptr p;
654:
655: {
656: int cost;
657: chainp q;
658: expptr memoffset,vleng;
659:
660: if (p == ENULL)
661: return NO;
662:
663: switch (p->tag)
664: {
665: case TCONST:
666: return NO;
667:
668: case TTEMP:
669: return NO;
670:
671: case TADDR:
672: if ((vleng = p->addrblock.vleng) && ! ISCONST(vleng))
673: return NO; /* Can't make variable length temporaries */
674: if ((memoffset = p->addrblock.memoffset) && ! ISCONST(memoffset))
675: return YES;
676: else
677: return NO;
678:
679: case TEXPR:
680: return YES;
681:
682: case TLIST:
683: cost = 0;
684: for (q = p->listblock.listp; q; q = q->nextp)
685: {
686: if (worthcost ((expptr) q->datap))
687: return YES;
688: cost++;
689: }
690: return (cost>2 ? YES : NO);
691:
692: default:
693: return NO;
694: }
695: }
696:
697:
698: LOCAL removesafe(refexpr)
699: expptr *refexpr;
700:
701: {
702: expptr ep;
703: Tempp ap;
704: Slotp newslot;
705:
706: extern Addrp gettemp();
707:
708: ep = *refexpr;
709: if (! worthcost(ep))
710: return;
711:
712: if (ep->tag == TEXPR && ep->exprblock.opcode == OPASSIGN)
713: {
714: if (ep->exprblock.leftp->tag != TTEMP)
715: fatal ("non-TEMP in assignment to be moved in optloop");
716:
717: newslot = optinsert (SKEQ, ep, 0, 0, first);
718: *refexpr = (expptr) cpexpr (ep->exprblock.leftp);
719: }
720: else
721: {
722: ap = (Tempp) gettemp(ep);
723: newslot = optinsert (SKEQ, mkexpr(OPASSIGN,cpexpr(ap),ep), 0, 0, first);
724: *refexpr = (expptr) ap;
725: optinsert (SKFRTEMP,ap->memalloc,0,0,last->next);
726: }
727:
728: comocount++;
729: if (!newcode)
730: newcode = newslot;
731:
732: return;
733: }
734:
735:
736: LOCAL Addrp gettemp(p)
737: expptr p;
738:
739: {
740: return mktemp(p->headblock.vtype, p->headblock.vleng);
741: }
742:
743:
744:
745: LOCAL movefrtemp (expr)
746: Tempp expr;
747:
748: {
749: Slotp s;
750:
751: if (expr->tag != TTEMP)
752: badtag ("movefrtemp",expr->tag);
753:
754: for (s = first; s; s = s->next)
755: if (s->type == SKFRTEMP && s->expr == (expptr) expr->memalloc)
756: {
757: removeslot (s);
758: insertslot (s,last->next);
759: return;
760: }
761: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.