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.constant.ci == 433 ep2->addrblock.memoffset->constblock.constant.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.constant; 451 bp= &ep2->constblock.constant; 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 } 926