4.3BSD - /usr/src/usr.bin/f77/src/f77pass1/optcse.c

   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,&current_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: }

Defined functions

Defined variables

Defined macros