|
|
1.1 root 1: #include "defs.h"
2: #include "optim.h"
3:
4: #define MSKREGTYPES M(TYLOGICAL) | M(TYADDR) | M(TYSHORT) | M(TYLONG)
5: #define ISREGTYPE(x) ONEOF(x, MSKREGTYPES)
6:
7: #define FALSE 0
8: #define TRUE 1
9:
10: LOCAL Bblockp current_BB;
11: LOCAL int cse1count; /* count of number of cse uses eliminated */
12: LOCAL int cse2count; /* count of number of cse def's eliminated */
13:
14:
15:
16:
17: LOCAL dumpstacks()
18: {
19: duplptr dl;
20: valuen p;
21: idlptr idl;
22: idptr idp;
23: nodelptr nl;
24: int i;
25:
26: fprintf(diagfile,"\n *** IDblocks ***\n");
27: for(idp=current_BB->headid;idp;idp=idp->next)
28: {
29: fprintf(diagfile,
30: "idp= %d idaddr= %d initval= %d assgnval= %d \n",
31: idp, idp->idaddr, idp->initval, idp->assgnval);
32: fprintf(diagfile,"nodes: ");
33: i=0;
34: for (nl=idp->headnodelist;nl;nl=nl->next) {
35: if(++i>20){
36: fprintf(diagfile,"\n");
37: i=0;
38: }
39: fprintf(diagfile," %d ",nl->nodep);
40: }
41: fprintf(diagfile,"\n");
42: }
43:
44: fprintf(diagfile,"\n *** VALUE NODES *** \n");
45: for(p=current_BB->headnode;p;p=p->next) {
46: fprintf(diagfile,
47: "\np= %d opp= %d lc= %d rc= %d rs= %d is_dead= %d n_dups %d",
48: p, p->opp,p->lc,p->rc, p->rs, p->is_dead, p->n_dups);
49: if (p->rs){
50: fprintf(diagfile,"tag= %d ",p->opp->tag);
51: if(p->opp->tag==TEXPR)
52: fprintf(diagfile,"opco= %d ",
53: p->opp->exprblock.opcode);
54: }
55: fprintf(diagfile,"\n");
56: fprintf(diagfile,"parent= %d dups: ",p->parent);
57: i=0;
58: for(dl=p->headduplist;dl;dl=dl->next) {
59: if(++i>20){
60: fprintf(diagfile,"\n");
61: i=0;
62: }
63: fprintf(diagfile," %d ",dl->parent);
64: }
65:
66: fprintf(diagfile,"\ndeps IDs");
67: i=0;
68: for(idl=p->headdeplist;idl;idl=idl->next) {
69: if(++i>20){
70: fprintf(diagfile,"\n");
71: i=0;
72: }
73: fprintf(diagfile," %d ",idl->idp);
74: }
75: }
76: }
77:
78:
79:
80: LOCAL idlptr mergedeps(lnode,rnode)
81: valuen lnode,rnode;
82: /* Given two value nodes, merge the lists of identifiers on which they
83: ** depend to produce a new list incorporating both dependencies. Lists
84: ** are assumed to be ordered by increasing idp address. No duplicate identifiers
85: ** are generated in the output list.
86: */
87: {
88: register idlptr lp,lp1,lp2;
89: idlptr head;
90:
91: lp = lp1 = lp2 = head = NULL;
92: if(lnode) lp1 = lnode->headdeplist;
93: if(rnode) lp2 = rnode->headdeplist;
94:
95: while (lp1 || lp2) {
96: if (lp) {
97: lp->next = ALLOC(IDlist);
98: lp = lp->next;
99: }
100: else lp = head = ALLOC(IDlist);
101: lp->next = 0;
102: if (lp1 == 0) {
103: lp->idp = lp2->idp;
104: lp2 = lp2->next;
105: }
106: else if (lp2 == 0) {
107: lp->idp = lp1->idp;
108: lp1 = lp1->next;
109: }
110: else if (lp1->idp < lp2->idp) {
111: lp->idp = lp1->idp;
112: lp1 = lp1->next;
113: }
114: else if (lp1->idp > lp2->idp) {
115: lp->idp = lp2->idp;
116: lp2 = lp2->next;
117: }
118: else {
119: lp->idp = lp1->idp;
120: lp1 = lp1->next;
121: lp2 = lp2->next;
122: }
123: }
124: return(head);
125: }
126:
127:
128:
129: LOCAL removenode(nodep)
130: valuen nodep;
131: /* Removes a value node from every IDblock on the node's list of identifiers.
132: */
133: {
134: register idlptr idl;
135: register nodelptr nl;
136: register nodelptr *addrnl;
137:
138: if(nodep == NULL) return ;
139:
140: /* loop through all identifiers */
141: for(idl=nodep->headdeplist;idl;idl=idl->next)
142: {
143: addrnl = &(idl->idp->headnodelist);
144: /* for each identifier loop through all nodes until match is found */
145: for(nl = *addrnl; nl; nl = *addrnl)
146: {
147: if(nl->nodep == nodep) {
148: *addrnl = nl->next;
149: free ( (charptr) nl );
150: break;
151: }
152: addrnl = &nl->next;
153: }
154: }
155: nodep->is_dead = TRUE;
156: }
157:
158:
159:
160: LOCAL killid(idp)
161: idptr idp;
162: /* Kill all nodes on one identifier's list of dependent nodes, i.e. remove
163: ** all calculations that depend on this identifier from the available
164: ** values stack. Free the list of records pointing at the dependent nodes.
165: */
166: {
167: nodelptr nl1,nl2;
168:
169: for (nl1 = idp->headnodelist; nl1; nl1=nl2)
170: {
171: nl2 = nl1->next;
172: removenode(nl1->nodep);
173: }
174: /* the above call frees the node list record pointed at by nl1 since it frees
175: ** all the node list records that reference the value node being killed
176: */
177: idp->headnodelist = NULL;
178:
179: }
180:
181:
182:
183: LOCAL killdepnodes(idp)
184: idptr idp;
185: /* Kill all value nodes that represent calculations which depend on
186: ** this identifier. If the identifier is in COMMON or EQUIVALENCE storage,
187: ** kill all values that depend on identifiers in COMMON or EQUIVALENCE
188: */
189: {
190: int thismemno;
191:
192: if(idp->idaddr->addrblock.vstg == STGCOMMON)
193: {
194: for(idp=current_BB->headid;idp;idp=idp->next)
195: if(idp->idaddr->addrblock.vstg == STGCOMMON)
196: killid(idp);
197: }
198: else if(idp->idaddr->addrblock.vstg == STGEQUIV)
199: {
200: thismemno=idp->idaddr->addrblock.memno;
201: for(idp=current_BB->headid;idp;idp=idp->next)
202: if(idp->idaddr->addrblock.vstg == STGEQUIV
203: && idp->idaddr->addrblock.memno == thismemno)
204: killid(idp);
205: }
206: else killid(idp);
207:
208: }
209:
210:
211:
212: LOCAL appendnode(nodep)
213: valuen nodep;
214: /* Append a value node to all the IDblocks on that node's list of
215: ** dependent identifiers i.e., since this computation depends on
216: ** all the identifiers on its list then each of those identifiers should
217: ** include this node in their list of dependent nodes.
218: */
219: {
220: register idlptr idl;
221: register nodelptr nl;
222:
223: for(idl=nodep->headdeplist;idl;idl=idl->next)
224: if(idl->idp->idaddr->tag == TADDR ||
225: idl->idp->idaddr->tag == TTEMP)
226: {
227: nl=ALLOC(NODElist);
228: nl->nodep = nodep;
229: nl->next = idl->idp->headnodelist;
230: idl->idp->headnodelist = nl;
231: }
232: }
233:
234:
235:
236: LOCAL idlptr addadep(idp,nodep)
237: idptr idp;
238: valuen nodep;
239: /* Add an identifier to the dependents list of a value node. Dependents
240: ** lists are ordered by increasing idp value
241: */
242: {
243: register idlptr lp1,lp2;
244:
245: lp2 = ALLOC(IDlist);
246: lp2->idp = idp;
247: if(nodep->headdeplist == 0) {
248: lp2->next = 0;
249: nodep->headdeplist = lp2;
250: }
251: else if(idp <= nodep->headdeplist->idp) {
252: lp2->next = nodep->headdeplist;
253: nodep->headdeplist = lp2;
254: }
255: else for(lp1 = nodep->headdeplist; lp1; lp1 = lp1->next)
256: if( (lp1->next == 0) || (idp <= lp1->next->idp) )
257: {
258: lp2->next = lp1->next;
259: lp1->next = lp2;
260: break;
261: }
262: return(lp2);
263: }
264:
265:
266:
267: LOCAL valuen newnode(expr,left,right,rslt)
268: expptr expr;
269: valuen left,right,rslt;
270: /* Build a new value node
271: */
272: {
273: register valuen p;
274:
275: p= ALLOC(VALUEnode);
276: p->opp = expr ;
277: p->parent = NULL ;
278: p->lc = left;
279: p->rc = right;
280: p->rs = rslt;
281: p->n_dups = 0;
282: p->is_dead = FALSE;
283: p->next=NULL;
284: p->headdeplist = mergedeps(left,right);
285: p->headduplist=NULL;
286: if(current_BB->headnode == 0) current_BB->headnode=p;
287: else if(current_BB->tailnode) current_BB->tailnode->next=p;
288: current_BB->tailnode=p;
289:
290: return(p);
291: }
292:
293:
294:
295: LOCAL newid(idaddr,addrof_idptr)
296: expptr idaddr;
297: idptr *addrof_idptr;
298: /* Build a new IDblock and hook it on the current BB's ID list
299: */
300: {
301: register idptr p;
302:
303: p= ALLOC(IDblock);
304:
305: /* build a leaf value node for the identifier and put the ID on the leaf node's
306: ** list of dependent identifiers
307: */
308: p->initval = newnode(idaddr,NULL,NULL,NULL);
309: p->initval->rs = p->initval;
310: addadep(p,p->initval);
311:
312: p->idaddr = idaddr;
313: *addrof_idptr = p;
314: p->headnodelist=NULL;
315: p->next=NULL;
316:
317: }
318:
319:
320:
321: LOCAL addadup(parent,nodep)
322: expptr *parent;
323: valuen nodep;
324:
325: /* A subtree has been found that duplicates the calculation represented
326: ** by the value node referenced by nodep : add the root of the reduntant
327: ** tree to the value node's list of duplicates.
328: */
329:
330: {
331: register duplptr dp;
332: valuen child;
333:
334: dp = ALLOC(DUPlist);
335: dp->parent = parent;
336: dp->next = nodep->headduplist;
337: nodep->headduplist = dp;
338: ++nodep->n_dups;
339:
340: /* Check whether either of nodep's children is also a duplicate calculation
341: ** and if so peel off it's most recent dup record
342: */
343:
344: if ( (child = nodep->lc) && (child->n_dups) )
345: {
346: dp = child->headduplist;
347: child->headduplist = dp->next;
348: free ( (charptr) dp );
349: --child->n_dups;
350: }
351: if ( (child = nodep->rc) && (child->n_dups) )
352: {
353: dp = child->headduplist;
354: child->headduplist = dp->next;
355: free ( (charptr) dp );
356: --child->n_dups;
357: }
358:
359: }
360:
361:
362:
363: LOCAL samebase(ep1,ep2)
364: expptr ep1,ep2;
365: {
366: if ( ep1->tag == ep2->tag )
367: switch (ep2->tag) {
368: case TTEMP :
369: if (ep1->tempblock.memalloc == ep2->tempblock.memalloc)
370: return (TRUE);
371: break;
372: case TADDR :
373: if (ep1->addrblock.vstg == ep2->addrblock.vstg &&
374: ep1->addrblock.memno == ep2->addrblock.memno )
375: return(TRUE);
376: break;
377: case TCONST :
378: if( (ep1->constblock.vtype) ==
379: (ep2->constblock.vtype) )
380: {
381: union Constant *ap,*bp;
382: ap= &ep1->constblock.const;
383: bp= &ep2->constblock.const;
384: switch(ep1->constblock.vtype)
385:
386: {
387: case TYSHORT:
388: case TYLONG:
389: if(ap->ci == bp->ci) return(TRUE);
390: break;
391: case TYREAL:
392: case TYDREAL:
393: if(ap->cd[0] == bp->cd[0]) return(TRUE);
394: break;
395: case TYCOMPLEX:
396: case TYDCOMPLEX:
397: if(ap->cd[0] == bp->cd[0] &&
398: ap->cd[1] == bp->cd[1] )
399: return(TRUE);
400: break;
401: }
402: }
403: break;
404:
405: default :
406: badtag ("samebase",ep2->tag);
407: }
408: return(FALSE);
409: }
410:
411:
412:
413: LOCAL idptr findid(idaddr)
414: expptr idaddr;
415:
416: /* Find an identifier's IDblock given its idaddr. If the identifier has no
417: ** IBblock build one
418: */
419:
420: {
421: register idptr idp;
422: if(current_BB->headid == 0) newid(idaddr,¤t_BB->headid);
423: idp=current_BB->headid;
424:
425: do {
426: if (samebase(idp->idaddr,idaddr) ) break;
427: if (idp->next == 0) {
428: newid(idaddr,&idp->next);
429: idp = idp->next;
430: break;
431: }
432: idp = idp->next;
433: }
434: while(TRUE);
435:
436: return(idp);
437: }
438:
439:
440:
441: LOCAL valuen findnode(ep,leftc,rightc)
442: expptr ep;
443: valuen leftc,rightc;
444: {
445: /* Look for a matching value node in the available computations stack
446: */
447: register valuen p;
448:
449: for ( p=current_BB->headnode; p ; p=p->next) {
450: if( ( ! p->is_dead) &&
451: (p->lc == leftc) &&
452: (p->rc == rightc) &&
453: ( (ep->tag == TEXPR && p->opp->tag == TEXPR
454: && p->opp->exprblock.opcode == ep->exprblock.opcode
455: )
456: || (ep->tag == TADDR) || (ep->tag == TTEMP)
457: )
458: )
459: return(p);
460: }
461: return(NULL);
462: }
463:
464:
465:
466: LOCAL valuen scanchain(listp,p_parent)
467: expptr listp;
468: chainp *p_parent;
469:
470: /* Make value nodes from the chain hanging off a LISTBLOCK
471: */
472:
473: {
474: valuen lnode,rnode,new,scantree();
475: chainp p;
476:
477: p= *p_parent;
478: if (p == NULL) return(NULL);
479: lnode = scantree( &p->datap);
480: rnode = scanchain(listp, &p->nextp);
481: new = newnode(listp,lnode,rnode,0);
482: new->rs = new;
483: return(new->rs);
484: }
485:
486:
487:
488: LOCAL valuen scantree(p_parent)
489: expptr *p_parent;
490:
491: /* build a value node and return its address. p must point to an
492: ** exprblock an addrblock a listblock or a constblock.
493: */
494:
495: {
496: valuen lnode, rnode,rsltnode,new;
497: expptr opp,p;
498: Exprp ep1,ep2;
499: idptr idp;
500:
501: p = *p_parent;
502: if(p == NULL) return(NULL);
503:
504: switch (p->tag) {
505: case TCONST :
506: return( findid(p)->initval );
507:
508: case TTEMP :
509: idp = findid(p);
510: if(idp->assgnval) return(idp->assgnval);
511:
512: lnode = idp->initval;
513: rnode = scantree( &p->tempblock.memalloc);
514:
515: rsltnode = findnode(p,lnode,rnode);
516: if(rsltnode)
517: return(rsltnode);
518: else {
519: new = newnode(p,lnode,rnode,0);
520: new->rs = new;
521: new->parent = p_parent;
522: return(new->rs);
523: }
524:
525: case TADDR :
526: idp = findid(p);
527: if(idp->assgnval) return(idp->assgnval);
528:
529: lnode = idp->initval;
530: rnode = scantree( &p->addrblock.memoffset);
531:
532: rsltnode = findnode(p,lnode,rnode);
533: if(rsltnode) {
534: if(p->addrblock.memoffset &&
535: p->addrblock.memoffset->tag == TEXPR
536: && NULL)
537: addadup(p_parent,rsltnode);
538: return(rsltnode);
539: }
540: else {
541: new = newnode(p,lnode,rnode,0);
542: new->rs = new;
543: new->parent = p_parent;
544: return(new->rs);
545: }
546:
547: case TLIST :
548: return(scanchain(p->listblock.listp,&p->listblock.listp));
549:
550: default :
551: badtag ("scantree",p->tag);
552:
553: case TEXPR :
554: lnode = scantree(&p->exprblock.leftp);
555: rnode = scantree(&p->exprblock.rightp);
556:
557: switch (p->exprblock.opcode) {
558: case OPASSIGN :
559: case OPPLUSEQ :
560: case OPSTAREQ :
561: {
562: Addrp ap;
563:
564: ap = (Addrp) p->exprblock.leftp;
565: idp = findid(ap);
566: killdepnodes(idp);
567: if( ! ap->isarray ) {
568: if(rnode->is_dead)idp->assgnval=idp->initval;
569: else idp->assgnval = rnode;
570: }
571: new = newnode(p,idp->initval,NULL,NULL);
572: appendnode(new);
573: new->rs = new;
574: return(new->rs);
575: }
576:
577: case OPCALL :
578: {
579: chainp cp;
580:
581: if(p->exprblock.rightp)
582:
583: /* pretend that all variables on the arglist have just
584: ** been assigned to i.e. kill of calculations that
585: ** depend on them. Not necessary for CCALL(by value)
586: */
587:
588: for(cp=p->exprblock.rightp->listblock.listp;
589: cp;cp=cp->nextp)
590: if (cp->datap->tag == TADDR ||
591: cp->datap->tag == TTEMP){
592: idp = findid(cp->datap);
593: killdepnodes(idp);
594: idp->assgnval = NULL;
595: }
596:
597: new = newnode(p,lnode,rnode,NULL);
598: new->rs = new;
599: return(new->rs);
600: }
601:
602: case OPCONCAT:
603: case OPADDR:
604: case OPCOLON:
605: case OPINDIRECT:
606: /*
607: * For now, do not optimize LSHIFT until OPINDIRECT
608: * implemented.
609: */
610: case OPLSHIFT:
611: new = newnode(p,lnode,rnode,NULL);
612: new->rs = new;
613: return(new->rs);
614:
615: case OPCOMMA:
616: badop ("scantree",OPCOMMA);
617: break;
618:
619: default :
620: rsltnode = findnode(p,lnode,rnode);
621: if (rsltnode) {
622: addadup(p_parent,rsltnode);
623: return(rsltnode);
624: }
625: else {
626: new = newnode(p,lnode,rnode,NULL);
627: new->rs = new;
628: new->parent = p_parent;
629: appendnode(new);
630: return(new->rs);
631: }
632: }
633: }
634: }
635:
636:
637:
638: LOCAL prunetrees()
639:
640: /* The only optcse.c routine that does any real work: go through the available
641: ** computations stack and eliminate redundant subtrees.
642: */
643:
644: {
645: Addrp tempv;
646: register duplptr dl;
647: register valuen p;
648: expptr t;
649: int is_addrnode;
650: expptr *addr_tree1 = NULL ;
651: expptr tree2 = NULL ;
652:
653: for(p=current_BB->headnode;p;p=p->next)
654: {
655: if(p->rs == NULL) {
656: if( addr_tree1 && tree2 )
657: *addr_tree1 = fixtype(mkexpr(OPCOMMA,tree2,*addr_tree1));
658: addr_tree1 = (expptr*) p->opp;
659: tree2 = NULL;
660: }
661: if (p->n_dups ) {
662:
663: if (p->opp->tag == TTEMP)
664: fprintf(diagfile,"TTEMP in prunetrees - cbb\n");
665: if(p->opp->tag == TADDR) is_addrnode = TRUE;
666: else is_addrnode = FALSE;
667:
668: if (is_addrnode)
669: tempv = mktemp(TYADDR,NULL);
670: else
671: tempv = mktemp(p->opp->exprblock.vtype,
672: p->opp->exprblock.vleng);
673: cse2count++;
674:
675: if(tree2)
676: tree2 = fixtype(mkexpr(OPCOMMA,tree2,
677: fixtype(mkexpr(OPASSIGN,cpexpr(tempv),
678: (is_addrnode ? addrof(p->opp) : p->opp)
679: ))));
680: else
681: tree2 = fixtype(mkexpr(OPASSIGN,cpexpr(tempv),
682: (is_addrnode ? addrof(p->opp) : p->opp)
683: ));
684:
685: if(is_addrnode)
686: *(p->parent) = fixtype(mkexpr(OPINDIRECT,cpexpr(tempv), NULL));
687: else
688: *(p->parent) = (expptr) cpexpr(tempv);
689:
690: /* then replaces all future instances of the calculation by references to
691: the temporary */
692:
693: for(dl=p->headduplist;dl->next;dl=dl->next) {
694: cse1count++;
695: frexpr(*dl->parent);
696: if(is_addrnode)
697: *(dl->parent) = fixtype(
698: mkexpr(OPINDIRECT,cpexpr(tempv), NULL));
699: else
700: *(dl->parent) = (expptr) cpexpr(tempv);
701: }
702:
703: /* the last reference does not use a copy since the temporary can
704: now be freed */
705:
706: cse1count++;
707: frexpr(*dl->parent);
708: if(is_addrnode)
709: *(dl->parent) = fixtype(mkexpr(OPINDIRECT,tempv, NULL));
710: else
711: *(dl->parent) = (expptr) tempv;
712:
713: frtemp (tempv);
714: }
715: }
716: if(addr_tree1 && tree2)
717: *addr_tree1 = fixtype(mkexpr(OPCOMMA,tree2,*addr_tree1));
718: }
719:
720:
721:
722: LOCAL rewritebb (bb)
723: Bblockp bb;
724: {
725: Slotp sp;
726: expptr p;
727:
728: if (bb == NULL)
729: return;
730: else
731: current_BB = bb;
732: sp = current_BB->first;
733:
734: /* loop trough all BB slots and scan candidate expr trees when found */
735:
736: for (sp = current_BB->first; ; sp = sp->next)
737: {
738: switch (sp->type)
739: {
740: case SKEQ :
741: case SKIFN :
742: case SKCMGOTO :
743: case SKCALL :
744: newnode((expptr) &sp->expr,NULL,NULL,NULL);
745: scantree(&sp->expr);
746: break;
747:
748: default :
749: break;
750: }
751: if (sp == current_BB->last) break;
752: }
753:
754: /* use the information built up by scantree to prune reduntant subtrees */
755: prunetrees();
756:
757: current_BB = NULL;
758: }
759:
760:
761:
762: /*
763: * removes all instances of OPCOMMA from the given subexpression of
764: * the given buffer slot
765: */
766:
767: expptr rmcommaop (p,sl)
768: expptr p;
769: Slotp sl;
770:
771: {
772: expptr leftp,rightp;
773: chainp cp;
774:
775: if (!p)
776: return (ENULL);
777: switch (p->tag)
778: {
779: case TEXPR:
780: leftp = p->exprblock.leftp;
781: rightp = p->exprblock.rightp;
782: leftp = rmcommaop (leftp,sl);
783: if (p->exprblock.opcode == OPCOMMA)
784: {
785: optinsert (SKEQ,leftp,0,0,sl);
786: if (p->exprblock.vleng)
787: free ((charptr) p->exprblock.vleng);
788: free ((charptr) p);
789: p = rmcommaop (rightp,sl);
790: return (p);
791: }
792: p->exprblock.leftp = leftp;
793: p->exprblock.rightp = rmcommaop (rightp,sl);
794: return (p);
795:
796: case TLIST:
797: for (cp = p->listblock.listp; cp; cp = cp->nextp)
798: cp->datap = (tagptr) rmcommaop (cp->datap,sl);
799: return (p);
800:
801: default:
802: return (p);
803: }
804: }
805:
806:
807:
808: /*
809: * scans the code buffer, performing common subexpression elimination
810: */
811:
812: optcse ()
813:
814: {
815: Slotp sl;
816: Bblockp bb;
817:
818: if (debugflag[13])
819: return;
820:
821: cse1count = 0;
822: cse2count = 0;
823: for (sl = firstslot; sl; sl = sl->next)
824: sl->expr = rmcommaop (sl->expr,sl);
825: for (bb = firstblock; bb; bb = bb->next)
826: rewritebb (bb);
827:
828: if (debugflag[0])
829: fprintf (diagfile,
830: "%d common subexpression use%s eliminated (%d definition%s)\n",
831: cse1count, (cse1count==1 ? "" : "s"),
832: cse2count, (cse2count==1 ? "" : "s"));
833: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.