1 /*- 2 * Copyright (c) 1980 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.proprietary.c% 6 */ 7 8 #ifndef lint 9 static char sccsid[] = "@(#)bb.c 5.3 (Berkeley) 04/12/91"; 10 #endif /* not lint */ 11 12 /* 13 * bb.c 14 * 15 * Basic block optimizations. 16 * 17 * University of Utah CS Dept modification history: 18 * 19 * Revision 2.1 84/07/19 12:01:20 donn 20 * Changed comment headers for UofU. 21 * 22 * Revision 1.2 84/04/02 14:22:49 donn 23 * Bug in copy propagation missed places where temporaries are assigned to 24 * by OPSTAREQ or OPPLUSEQ, e.g. exponentiation with an integer constant 25 * power, expanded inline. 26 * 27 */ 28 29 #include "defs.h" 30 #include "optim.h" 31 32 /* 33 * This file contains code for determination of basic blocks, 34 * as well as some other optimization supporting routines 35 * [including the main routine 'optimize()']. 36 * 37 * The compiler's general debugging flag ['debugflag'] has been 38 * extended to provide the capability of having multiple flags 39 * which are contained in an array. If the option -d is used, 40 * then the flag debugflag[0] is set. If a sequence of one or more 41 * numbers are given (e.g, -d3,7,12), then the flags debugflag[3], 42 * debugflag[7], and debugflag[12] are set. The maximum number of 43 * flags available is specified in the defines.h file. 44 */ 45 46 47 Bblockp firstblock = NULL; /* first block in buffer */ 48 Bblockp lastblock = NULL; /* last block in buffer */ 49 50 expptr tempalloc(); 51 52 53 optimize () 54 55 { 56 Bblockp bb; 57 Slotp sl,nextsl; 58 59 if (debugflag[2]) showbuffer (); 60 61 optloops (); 62 63 if (debugflag[3]) showbuffer (); 64 65 formbblock (); 66 optcse (); 67 68 if (debugflag[4]) showbuffer (); 69 70 if (! debugflag[7]) 71 copyprop (); 72 73 if (debugflag[9]) showbuffer (); 74 75 for (sl = firstslot; sl; sl = nextsl) 76 { 77 nextsl = sl->next; 78 if (sl->type == SKFRTEMP) 79 { 80 templist = mkchain (sl->expr,templist); 81 sl->expr = NULL; 82 delslot (sl); 83 } 84 else 85 sl->expr = tempalloc (sl->expr); 86 } 87 88 if (! debugflag[10]) 89 regalloc (); 90 91 flushopt (); 92 } 93 94 95 96 /* 97 * creates a new basic block record 98 */ 99 100 LOCAL Bblockp newblock (sl) 101 Slotp sl; 102 103 { 104 register Bblockp bb; 105 106 bb = ALLOC( bblock ); 107 bb->next = NULL ; 108 if (lastblock) 109 { 110 bb->prev = lastblock; 111 lastblock->next = bb; 112 lastblock = bb; 113 } 114 else 115 { 116 firstblock = lastblock = bb; 117 bb->prev = NULL; 118 } 119 120 bb->first = sl; 121 return (bb); 122 } 123 124 125 126 /* 127 * scans slot buffer, creating basic block records 128 */ 129 130 formbblock () 131 132 { 133 Slotp sl; 134 field type; 135 Bblockp newbb; 136 137 newbb = NULL; 138 for (sl = firstslot; sl; sl = sl->next) 139 { 140 type = sl->type; 141 switch (type) 142 { 143 case SKEQ: 144 if (!newbb) 145 newbb = newblock(sl); 146 if (containscall(sl->expr)) 147 { 148 newbb->last = sl; 149 newbb = NULL; 150 } 151 break; 152 case SKNULL: 153 case SKASSIGN: 154 case SKFRTEMP: 155 if (!newbb) 156 newbb = newblock(sl); 157 break; 158 case SKPAUSE: 159 case SKSTOP: 160 case SKIFN: 161 case SKGOTO: 162 case SKCMGOTO: 163 case SKARIF: 164 case SKASGOTO: 165 case SKIOIFN: 166 case SKCALL: 167 case SKRETURN: 168 if (!newbb) 169 newbb = newblock(sl); 170 newbb->last = sl; 171 newbb = NULL; 172 break; 173 case SKLABEL: 174 if (newbb) 175 newbb->last = sl->prev; 176 newbb = newblock(sl); 177 break; 178 case SKDOHEAD: 179 case SKENDDO: 180 if (!newbb) 181 newbb = newblock(sl); 182 break; 183 default: 184 badthing("SKtype", "formbblock", type); 185 break; 186 } 187 } 188 if (newbb) 189 newbb->last = lastslot; 190 } 191 192 193 194 /* 195 * frees all basic block records 196 * as well as the id and value node chains hanging off the bb and their 197 * respective cross link chains (IDlist, DUPlist and NODElist structs) 198 */ 199 200 clearbb () 201 { 202 Bblockp bb,next; 203 204 for (bb = firstblock; bb; bb = next) 205 { 206 next = bb->next; 207 { 208 idptr idp,next; 209 for(idp = bb->headid; idp; idp = next) 210 { 211 next = idp->next; 212 { 213 nodelptr nodelp, next; 214 for(nodelp = idp->headnodelist; nodelp; nodelp = next) 215 { 216 next = nodelp->next; 217 free( (charptr) nodelp); 218 } 219 } 220 free( (charptr) idp); 221 } 222 } 223 { 224 valuen vp,next; 225 for(vp = bb->headnode; vp; vp = next) 226 { 227 next = vp->next; 228 { 229 idlptr idlp, next; 230 for(idlp = vp->headdeplist; idlp; idlp = next) 231 { 232 next = idlp->next; 233 free( (charptr) idlp); 234 } 235 } 236 { 237 duplptr duplp, next; 238 for(duplp = vp->headduplist; duplp; duplp = next) 239 { 240 next = duplp->next; 241 free( (charptr) duplp); 242 } 243 } 244 free( (charptr) vp); 245 } 246 } 247 free ( (charptr) bb); 248 } 249 firstblock = lastblock = NULL; 250 } 251 252 253 /* structure for maintaining records on copy statements */ 254 255 typedef struct Subrec { 256 Addrp lmem; 257 Addrp rmem; 258 int sets; 259 } *Subrecp; 260 261 262 LOCAL chainp sublist; /* list of copy statements */ 263 LOCAL int prop1count; /* count of number of temporaries eliminated */ 264 LOCAL int prop2count; /* count of number of uses of temporaries replaced */ 265 266 expptr rmcommaop(); 267 Addrp subfor(); 268 269 270 271 /* 272 * eliminates copy statements of the form T1 = T2 from the intermediate 273 * code, where T1 and T2 are temporary variables which are each 274 * set only once; eliminates the copy statement and replaces each 275 * use of T1 by T2 (T1 is therefore totally eliminated). 276 */ 277 278 LOCAL copyprop () 279 280 { 281 Slotp sl,nextsl; 282 expptr expr; 283 Tempp lp,rp; 284 285 for (sl = firstslot; sl; sl = sl->next) 286 sl->expr = rmcommaop (sl->expr,sl); 287 288 prop1count = prop2count = 0; 289 findcopies (); 290 291 for (sl = firstslot; sl; sl = nextsl) 292 { 293 nextsl = sl->next; 294 expr = sl->expr; 295 296 if ((sl->type == SKFRTEMP) && subfor (expr)) 297 { 298 delslot (sl); 299 expr = ENULL; 300 } 301 else if (expr && expr->tag == TEXPR && 302 expr->exprblock.opcode == OPASSIGN) 303 { 304 lp = (Tempp) expr->exprblock.leftp; 305 rp = (Tempp) expr->exprblock.rightp; 306 if (lp->tag == TTEMP && rp->tag == TTEMP) 307 if (subfor(lp->memalloc) == rp->memalloc 308 && !subfor (rp->memalloc)) 309 { 310 frexpr (expr); 311 expr = sl->expr = ENULL; 312 prop1count++; 313 } 314 } 315 316 propagate (expr); 317 } 318 319 if (debugflag[0]) 320 fprintf (diagfile, 321 "%d temporarie%s replaced by copy propagation (%d use%s)\n", 322 prop1count,(prop1count==1 ? "" : "s"), 323 prop2count,(prop2count==1 ? "" : "s") ); 324 } 325 326 327 328 /* 329 * finds copy statements and enters information in table 330 */ 331 332 LOCAL findcopies () 333 334 { 335 Slotp sl; 336 expptr expr; 337 chainp cp; 338 339 for (sl = firstslot; sl; sl = sl->next) 340 { 341 expr = sl->expr; 342 if (expr) switch (expr->tag) 343 { 344 case TEXPR: 345 ckexpr (expr); 346 break; 347 348 case TLIST: 349 for (cp = expr->listblock.listp; cp; cp = cp->nextp) 350 { 351 expr = (expptr) cp->datap; 352 ckexpr (expr); 353 } 354 break; 355 356 default: 357 break; 358 } 359 } 360 } 361 362 363 364 /* 365 * checks an individual expression 366 */ 367 368 ckexpr (expr) 369 expptr expr; 370 371 { 372 Tempp lp,rp; 373 int oc = expr->exprblock.opcode; 374 375 if (oc == OPASSIGN || oc == OPPLUSEQ || oc == OPSTAREQ) 376 { 377 lp = (Tempp) expr->exprblock.leftp; 378 rp = (Tempp) expr->exprblock.rightp; 379 if (lp->tag == TTEMP) 380 if (rp->tag == TTEMP && oc == OPASSIGN) 381 enter (lp->memalloc, rp->memalloc); 382 else 383 enter (lp->memalloc, ENULL); 384 } 385 } 386 387 388 389 /* 390 * Enters the given memalloc values in the table (or update if they 391 * are already there), for the assignment statement m1 = m2. 392 * If m2 is NULL, this indicates that the assignment is not a copy 393 * statement. 394 */ 395 396 LOCAL enter (m1,m2) 397 Addrp m1,m2; 398 399 { 400 chainp cp; 401 Subrecp old,new; 402 403 for (cp = sublist; cp; cp = cp->nextp) 404 { 405 old = (Subrecp) cp->datap; 406 if (old->lmem == m1) 407 { 408 old->sets++; 409 return; 410 } 411 } 412 413 new = ALLOC (Subrec); 414 new->lmem = m1; 415 new->rmem = m2; 416 new->sets = 1; 417 sublist = mkchain (new, sublist); 418 } 419 420 421 422 /* 423 * looks for record for the given memalloc value 424 */ 425 426 LOCAL Subrecp lookup (mem) 427 Addrp mem; 428 429 { 430 chainp cp; 431 Subrecp rec; 432 433 for (cp = sublist; cp; cp = cp->nextp) 434 { 435 rec = (Subrecp) cp->datap; 436 if (rec->lmem == mem) 437 return rec; 438 } 439 440 return NULL; 441 } 442 443 444 445 /* 446 * checks to see if there is a substitute for given memalloc value 447 */ 448 449 LOCAL Addrp subfor (mem) 450 Addrp mem; 451 452 { 453 Subrecp rec,rec2; 454 Addrp sub; 455 456 rec = lookup (mem); 457 if (rec && rec->sets == 1) 458 { 459 sub = rec->rmem; 460 rec2 = lookup(sub); 461 if (rec2 && rec2->sets == 1) 462 return sub; 463 } 464 465 return NULL; 466 } 467 468 469 470 /* 471 * actually propagates the information 472 */ 473 474 LOCAL propagate (expr) 475 expptr expr; 476 477 { 478 chainp t; 479 Addrp new; 480 481 if (! expr) return; 482 483 switch (expr->tag) 484 { 485 case TEXPR: 486 propagate (expr->exprblock.leftp); 487 propagate (expr->exprblock.rightp); 488 break; 489 490 case TADDR: 491 propagate (expr->addrblock.vleng); 492 propagate (expr->addrblock.memoffset); 493 break; 494 495 case TLIST: 496 for (t = expr->listblock.listp; t; t = t->nextp) 497 propagate (t->datap); 498 break; 499 500 case TTEMP: 501 new = subfor (expr->tempblock.memalloc); 502 if (new) 503 { 504 expr->tempblock.memalloc = new; 505 prop2count++; 506 } 507 break; 508 509 default: 510 break; 511 } 512 } 513 514 515 516 /* 517 * allocates ADDR blocks for each TEMP in the expression 518 */ 519 520 LOCAL expptr tempalloc (expr) 521 expptr expr; 522 523 { 524 chainp t; 525 526 if (! expr) 527 return NULL; 528 529 switch (expr->tag) 530 { 531 case TEXPR: 532 expr->exprblock.leftp = tempalloc (expr->exprblock.leftp); 533 expr->exprblock.rightp = tempalloc (expr->exprblock.rightp); 534 break; 535 536 case TADDR: 537 expr->addrblock.vleng = tempalloc (expr->addrblock.vleng); 538 expr->addrblock.memoffset = tempalloc (expr->addrblock.memoffset); 539 break; 540 541 case TLIST: 542 for (t = expr->listblock.listp; t; t = t->nextp) 543 t->datap = (tagptr) tempalloc (t->datap); 544 break; 545 546 case TTEMP: 547 return (expptr) cpexpr (altmpn (expr)); 548 break; 549 550 default: 551 break; 552 } 553 return expr; 554 } 555 556 557 /********************* debugging routines *********************/ 558 559 560 561 Announce (s,q) 562 char *s; 563 expptr q; 564 565 { 566 fprintf (diagfile,"\nAn expression [%s]----->\n",s); 567 showexpr(q,0); 568 fprintf (diagfile,"\n-------------end of expr--------------\n"); 569 } 570 571 572 573 /* 574 * dump the basic block buffer, including expressions, mnemonically 575 */ 576 577 showbuffer () 578 579 { 580 Slotp sl; 581 Bblockp bb; 582 int i; 583 584 fprintf (diagfile,"Basic blocks with first and last slots ----------\n"); 585 for (i=1, bb = firstblock; bb; i++, bb = bb->next) 586 fprintf (diagfile,"%2d. %d %d\n",i,bb->first,bb->last); 587 fprintf (diagfile,"\n"); 588 589 fprintf (diagfile,"Slots and expressions ----------\n"); 590 591 fprintf (diagfile,"tag pointer vtype vclass vstg vleng\n"); 592 fprintf (diagfile," ADDR memno memoffset istemp ntempelt varleng\n"); 593 fprintf (diagfile," TEMP memalloc istemp ntempelt varleng\n"); 594 fprintf (diagfile," EXPR opcode leftp rightp\n"); 595 fprintf (diagfile," LIST type listp\n"); 596 fprintf (diagfile,"\n"); 597 598 for (i=1, sl = firstslot; sl; i++, sl = sl->next) 599 { 600 fprintf (diagfile,"%2d. ",i); 601 showslt (sl); 602 } 603 fprintf (diagfile,"---------- End of showbuffer ----------\n"); 604 } 605 606 607 608 /* 609 * dumps a single slot in the code buffer 610 */ 611 612 LOCAL charptr Zslot[] = {"NULL", 613 "IFN","GOTO","LABEL","EQ","CALL","CMGOTO","STOP","DOHEAD", 614 "ENDDO","ARIF","RETURN","ASGOTO","PAUSE","ASSIGN","IOIFN","FRTEMP"}; 615 616 617 618 showslt (sl) 619 Slotp sl; 620 621 { 622 fprintf (diagfile,"(%2d) %d %s %d\n", 623 sl->lineno,sl,Zslot[sl->type],sl->label); 624 showexpr (sl->expr,0); 625 fprintf (diagfile,"\n"); 626 } 627 628 629 630 showslottype (type) 631 int type; 632 633 { 634 fprintf (diagfile,"%s\n",Zslot[type]); 635 } 636 637 638 639 /* 640 * displays the given expression at the given indentation, showing 641 * its subexpressions at further indentations 642 */ 643 644 LOCAL charptr Ztag[] = {"----", 645 "NAME","CONST","EXPR","ADDR","TEMP","PRIM","LIST","IMPLDO","ERROR"}; 646 LOCAL charptr Zstg[] = {"unk", 647 "ARG","AUTO","BSS","INIT","CONST","EXT","INTR","STFUNCT", 648 "COMMON","EQUIV","REG","LENG","NULL","PREG"}; 649 LOCAL charptr Zclass[] = {"unk", 650 "PARAM","VAR","ENTRY","MAIN","BLOCK","PROC","NAMELIST"}; 651 LOCAL charptr Zop[] = {"----", 652 "PLUS","MINUS","STAR","SLASH","POWER","NEG","OR","AND","EQV", 653 "NEQV","NOT","CONCAT","LT","EQ","GT","LE","NE","GE","CALL", 654 "CCALL","ASSIGN","PLUSEQ","STAREQ","CONV","LSHIFT","MOD", 655 "COMMA","QUEST","COLON","ABS","MIN","MAX","ADDR","INDIRECT", 656 "BITOR","BITAND","BITXOR","BITNOT","RSHIFT","PAREN"}; 657 LOCAL charptr Ztype[] = {"unk", 658 "ADDR","SHORT","LONG","REAL","DREAL","COMPLEX","DCOMPLEX", 659 "LOGICAL","CHAR","SUBR","ERROR"}; 660 661 662 showexpr(p,indent) 663 tagptr p; 664 int indent; 665 666 { 667 int i; 668 int type; 669 chainp q; 670 671 #define PRHEAD(q) fprintf(diagfile,"%s %d %s %s %s %d", \ 672 Ztag[q->tag], q, Ztype[q->headblock.vtype], \ 673 Zclass[q->headblock.vclass], Zstg[q->headblock.vstg], \ 674 q->headblock.vleng); 675 #define SHOWEXPR(p) showexpr(p,indent+2) 676 677 678 679 if(p == NULL) 680 return; 681 682 for (i=0; i<indent; i++) 683 putc(' ',diagfile); 684 685 switch(p->tag) 686 { 687 case TCONST: 688 PRHEAD(p); 689 690 type=p->constblock.vtype; 691 if (ISCHAR(p)) 692 { 693 fprintf(diagfile," ISCHAR ccp= %d\n", 694 p->constblock.constant.ccp); 695 SHOWEXPR(p->constblock.vleng); 696 } 697 else if( ISINT(type) ) 698 fprintf(diagfile," ci= %d\n",p->constblock.constant.ci); 699 else if( ISREAL(type) ) 700 fprintf(diagfile, 701 " cd[0]= %e\n",p->constblock.constant.cd[0]); 702 else fprintf(diagfile," cd[0]= %e cd[1]= %e\n", 703 p->constblock.constant.cd[0], 704 p->constblock.constant.cd[1] ); 705 break; 706 707 case TADDR: 708 PRHEAD(p); 709 fprintf(diagfile, 710 " memno= %d %d %d %d %d\n", 711 p->addrblock.memno,p->addrblock.memoffset,p->addrblock.istemp, 712 p->addrblock.ntempelt,p->addrblock.varleng); 713 SHOWEXPR(p->addrblock.vleng); 714 SHOWEXPR(p->addrblock.memoffset); 715 break; 716 717 case TTEMP: 718 fprintf(diagfile,"%s %d %s %s %d", 719 Ztag[p->tag], p, Ztype[p->headblock.vtype], 720 Zclass[p->headblock.vclass], 721 p->headblock.vleng); 722 fprintf(diagfile, 723 " memalloc= %d %d %d %d\n", 724 p->tempblock.memalloc,p->tempblock.istemp, 725 p->tempblock.ntempelt,p->tempblock.varleng); 726 SHOWEXPR(p->tempblock.vleng); 727 SHOWEXPR(p->tempblock.memalloc); 728 break; 729 730 case TERROR: 731 fprintf(diagfile,"ERROR %d\n",p); 732 break; 733 734 case TNAME: 735 fprintf(diagfile,"NAME %d\n",p); 736 return; 737 738 case TPRIM: 739 fprintf(diagfile,"PRIM %d --- not implemented\n",p); 740 break; 741 742 case TEXPR: 743 PRHEAD(p); 744 fprintf(diagfile," opcode= %s %d %d\n", 745 Zop[p->exprblock.opcode],p->exprblock.leftp, 746 p->exprblock.rightp); 747 SHOWEXPR(p->exprblock.leftp); 748 if(p->exprblock.rightp) 749 SHOWEXPR(p->exprblock.rightp); 750 break; 751 752 case TLIST: 753 fprintf(diagfile,"LIST %d %s %d\n",p, 754 Ztype[p->listblock.vtype],p->listblock.listp); 755 for(q= p->listblock.listp ; q ; q = q->nextp) 756 SHOWEXPR(q->datap); 757 for (i=0; i<indent; i++) 758 putc (' ',diagfile); 759 fprintf(diagfile,"END LIST %d\n",p); 760 break; 761 762 default: 763 fprintf(diagfile,"showexpr BAD TAG= %d at %d \n",p->tag,p); 764 } 765 } 766 767 768 769 selective()/************************************/ 770 { 771 int i; 772 Slotp sl; 773 774 i=0; 775 fprintf (stderr,"SELECTIVE OUTPUT\n"); 776 for (sl=firstslot;sl;sl=sl->next) 777 { 778 i++; 779 /* 780 if (i>=176 && i<184) 781 */ 782 { 783 fprintf (stderr,"%d. ",i); 784 showslt(sl); 785 } 786 } 787 } 788 789 790 791 792 LOCAL containscall(p) 793 expptr p; 794 { 795 chainp cp; 796 797 if (p == NULL) 798 return NO; 799 800 switch (p->tag) 801 { 802 case TADDR: 803 if (containscall(p->addrblock.vleng) 804 || containscall(p->addrblock.memoffset)) 805 return YES; 806 else 807 return NO; 808 809 case TCONST: 810 return NO; 811 812 case TERROR: 813 return NO; 814 815 case TEXPR: 816 if (p->exprblock.opcode == OPCALL || 817 p->exprblock.opcode == OPCCALL) 818 return YES; 819 if (containscall(p->exprblock.vleng) || 820 containscall(p->exprblock.leftp) || 821 containscall(p->exprblock.rightp)) 822 return YES; 823 else 824 return NO; 825 826 case TLIST: 827 cp = p->listblock.listp; 828 while (cp) 829 { 830 if (containscall(cp->datap)) 831 return YES; 832 cp = cp->nextp; 833 } 834 return NO; 835 836 default: 837 return YES; 838 } 839 } 840