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