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