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