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