|
|
1.1 ! root 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[] = "@(#)optloop.c 5.1 (Berkeley) 6/7/85"; ! 9: #endif not lint ! 10: ! 11: /* ! 12: * optloop.c ! 13: * ! 14: * Loop optimizations, f77 compiler pass 1, 4.2 BSD. ! 15: * ! 16: * University of Utah CS Dept. modification history: ! 17: * ! 18: * $Log: optloop.c,v $ ! 19: * Revision 1.3 86/02/12 15:28:42 rcs ! 20: * 4.3 F77. C. Keating. ! 21: * ! 22: * Revision 1.4 84/10/25 01:27:29 donn ! 23: * Fixed a subtle bug in removesafe(). When the moved code is an assignment ! 24: * into a temporary, we use the lhs to substitute for the expression inside ! 25: * the loop. Previously the data structure for the temporary was not copied, ! 26: * so later on when the lhs was freed, the substitute was too, turning it ! 27: * into garbage. ! 28: * ! 29: * Revision 1.3 84/08/05 17:04:03 donn ! 30: * Changed worthcost() so that it skips variable length strings -- we can't ! 31: * make temporaries for these... ! 32: * ! 33: * Revision 1.2 84/07/19 11:50:39 donn ! 34: * Installed changes to force non-intrinsic subroutines and functions to define ! 35: * their arguments (make them ineligible for optimization), function setsuses. ! 36: * Fix from A.F. ! 37: * ! 38: */ ! 39: ! 40: #include "defs.h" ! 41: #include "optim.h" ! 42: ! 43: ! 44: #define SCFREE 0 ! 45: #define SCSAFE 1 ! 46: ! 47: ! 48: ! 49: typedef ! 50: struct varblock ! 51: { ! 52: struct varblock *next; ! 53: field vstg; ! 54: int memno; /* holds memalloc for TTEMP */ ! 55: short sets; ! 56: short uses; ! 57: field setfirst; ! 58: } VARBLOCK; ! 59: ! 60: typedef VARBLOCK *Varp; ! 61: ! 62: #define TABLESIZE 59 ! 63: ! 64: LOCAL Varp table[TABLESIZE]; ! 65: ! 66: ! 67: ! 68: LOCAL Varp mkbucket(vstg,memno) ! 69: field vstg; ! 70: int memno; ! 71: ! 72: { ! 73: Varp q; ! 74: ! 75: q = ALLOC(varblock); ! 76: q->vstg = vstg; ! 77: q->memno = memno; ! 78: return q; ! 79: } ! 80: ! 81: ! 82: ! 83: LOCAL Varp lookup(p) ! 84: tagptr p; ! 85: ! 86: { ! 87: int vstg, memno; ! 88: int key; ! 89: Varp q, r; ! 90: ! 91: switch (p->tag) ! 92: { ! 93: case TTEMP: ! 94: vstg = 0; ! 95: memno = (int) p->tempblock.memalloc; ! 96: break; ! 97: ! 98: case TADDR: ! 99: vstg = p->addrblock.vstg; ! 100: memno = p->addrblock.memno; ! 101: break; ! 102: ! 103: default: ! 104: badtag ("lookup",p->tag); ! 105: } ! 106: key = memno % TABLESIZE; ! 107: q = table[key]; ! 108: ! 109: if (q) ! 110: { ! 111: for (; q; r = q, q = q->next) ! 112: if ((q->vstg == vstg) && (q->memno == memno)) ! 113: return q; ! 114: return r->next = mkbucket(vstg,memno); ! 115: } ! 116: else ! 117: return table[key] = mkbucket(vstg,memno); ! 118: } ! 119: ! 120: ! 121: ! 122: LOCAL freetable() ! 123: ! 124: { ! 125: int i; ! 126: Varp p, q; ! 127: ! 128: for (i = 0; i < TABLESIZE; i++) ! 129: if (table[i]) ! 130: { ! 131: p = table[i]; ! 132: table[i] = NULL; ! 133: ! 134: while (p) ! 135: { ! 136: q = p->next; ! 137: free((char *) p); ! 138: p = q; ! 139: } ! 140: } ! 141: } ! 142: ! 143: ! 144: ! 145: Slotp newcode; ! 146: Slotp dohead, doend; ! 147: LOCAL Slotp first, last; ! 148: LOCAL commonset; ! 149: LOCAL int comocount; /* count of number of code motions done */ ! 150: ! 151: ! 152: optloops() ! 153: ! 154: { ! 155: int match; ! 156: Slotp nextslot; ! 157: Slotp sl1,sl2; ! 158: Slotp lastlabslot; ! 159: int lab; ! 160: ! 161: if (! optimflag) return; ! 162: if (debugflag[6]) return; ! 163: ! 164: lastlabslot = NULL; ! 165: comocount = 0; ! 166: for (sl1 = firstslot; sl1; sl1 = nextslot) ! 167: { ! 168: nextslot = sl1->next; ! 169: switch (sl1->type) ! 170: { ! 171: case SKLABEL: ! 172: lastlabslot = sl1; ! 173: break; ! 174: ! 175: case SKGOTO: ! 176: if (lastlabslot && sl1->label == lastlabslot->label) ! 177: { ! 178: lab = newlabel (); ! 179: first = optinsert (SKLABEL,0,lab,0,lastlabslot->next); ! 180: last = sl1; ! 181: last->label = lab; ! 182: optloop (); ! 183: } ! 184: break; ! 185: ! 186: case SKDOHEAD: ! 187: match = 0; ! 188: for (sl2 = sl1; sl2; sl2 = sl2->next) ! 189: { ! 190: if (sl2->type == SKDOHEAD) match++; ! 191: else if (sl2->type == SKENDDO) match--; ! 192: if (match == 0) break; ! 193: } ! 194: if (sl2) ! 195: last = sl2; ! 196: else ! 197: fatal ("unmatched do in code buffer"); ! 198: if (sl2->type != SKENDDO) ! 199: fatal ("internal error in optloops"); ! 200: ! 201: /* last now points to the SKENDDO slot; the SKNULL slot ! 202: * is reached through last->nullslot ! 203: */ ! 204: last = (Slotp) last->nullslot; ! 205: ! 206: first = sl1; ! 207: ! 208: optloop (); ! 209: break; ! 210: ! 211: default: ! 212: break; ! 213: } ! 214: } ! 215: ! 216: if (debugflag[0]) ! 217: fprintf (diagfile,"%d code motion%s performed\n",comocount, ! 218: (comocount==1 ? "" : "s") ); ! 219: return; ! 220: } ! 221: ! 222: ! 223: ! 224: optloop() ! 225: ! 226: { ! 227: newcode = NULL; ! 228: ! 229: modify(); ! 230: ! 231: return; ! 232: } ! 233: ! 234: ! 235: LOCAL modify() ! 236: ! 237: { ! 238: Slotp sp; ! 239: int s; ! 240: ! 241: scanvars(); ! 242: ! 243: for (sp = first; sp != last->next; sp = sp->next) ! 244: switch (sp->type) ! 245: { ! 246: case SKEQ: ! 247: s = anex(sp->expr); ! 248: if (s == SCSAFE) ! 249: removesafe (&sp->expr); ! 250: break; ! 251: ! 252: case SKARIF: ! 253: case SKASGOTO: ! 254: case SKCALL: ! 255: case SKCMGOTO: ! 256: case SKIFN: ! 257: case SKSTOP: ! 258: case SKRETURN: ! 259: case SKPAUSE: ! 260: case SKIOIFN: ! 261: s = anex(sp->expr); ! 262: if (s == SCSAFE) ! 263: removesafe(&sp->expr); ! 264: break; ! 265: ! 266: default: ! 267: break; ! 268: } ! 269: ! 270: freetable(); ! 271: return; ! 272: } ! 273: ! 274: ! 275: LOCAL scanvars() ! 276: ! 277: { ! 278: Slotp sp; ! 279: Varp varinfo; ! 280: int i; ! 281: Varp p; ! 282: ! 283: commonset = NO; ! 284: ! 285: for (sp = first; sp != last->next; sp = sp->next) ! 286: { ! 287: switch (sp->type) ! 288: { ! 289: case SKARIF: ! 290: case SKASGOTO: ! 291: case SKCALL: ! 292: case SKCMGOTO: ! 293: case SKIFN: ! 294: case SKSTOP: ! 295: case SKRETURN: ! 296: case SKPAUSE: ! 297: case SKIOIFN: ! 298: case SKEQ: ! 299: setsuses(sp->expr); ! 300: break; ! 301: ! 302: default: ! 303: break; ! 304: } ! 305: } ! 306: ! 307: if (commonset) ! 308: for (i = 0; i < TABLESIZE; i++) ! 309: for (p = table[i]; p; p = p->next) ! 310: if (p->vstg == STGCOMMON) ! 311: { ! 312: p->sets++; ! 313: p->setfirst = NO; ! 314: } ! 315: } ! 316: ! 317: ! 318: LOCAL setsuses(p) ! 319: expptr p; ! 320: ! 321: { ! 322: Addrp lhs; ! 323: Varp varinfo; ! 324: chainp args; ! 325: ! 326: if (!p) return; ! 327: ! 328: switch (p->tag) ! 329: { ! 330: case TEXPR: ! 331: switch (p->exprblock.opcode) ! 332: { ! 333: default: ! 334: setsuses(p->exprblock.leftp); ! 335: setsuses(p->exprblock.rightp); ! 336: setsuses(p->exprblock.vleng); ! 337: break; ! 338: ! 339: case OPASSIGN: ! 340: switch (p->exprblock.leftp->tag) ! 341: { ! 342: case TTEMP: ! 343: lhs = (Addrp) p->exprblock.leftp; ! 344: goto taddr; ! 345: ! 346: case TADDR: ! 347: lhs = (Addrp) p->exprblock.leftp; ! 348: setsuses(lhs->memoffset); ! 349: setsuses(lhs->vleng); ! 350: taddr: ! 351: setsuses(p->exprblock.rightp); ! 352: setsuses(p->exprblock.vleng); ! 353: varinfo = lookup(lhs); ! 354: varinfo->sets++; ! 355: if (varinfo->uses == 0) ! 356: varinfo->setfirst = YES; ! 357: break; ! 358: ! 359: default: ! 360: fatal("O6: l-value expected"); ! 361: } ! 362: break; ! 363: ! 364: case OPSTAREQ: ! 365: case OPPLUSEQ: ! 366: switch (p->exprblock.leftp->tag) ! 367: { ! 368: case TADDR: ! 369: lhs = (Addrp) p->exprblock.leftp; ! 370: break; ! 371: case TTEMP: ! 372: lhs = (Addrp) p->exprblock.leftp; ! 373: break; ! 374: default: ! 375: fatal("O7: l-value expected"); ! 376: } ! 377: setsuses(p->exprblock.leftp); ! 378: setsuses(p->exprblock.rightp); ! 379: setsuses(p->exprblock.vleng); ! 380: varinfo = lookup(lhs); ! 381: varinfo->sets++; ! 382: break; ! 383: ! 384: case OPCALL: ! 385: if (p->exprblock.leftp->tag != TADDR) ! 386: fatal("O8: subprogram expected"); ! 387: setsuses(p->exprblock.rightp); ! 388: setsuses(p->exprblock.vleng); ! 389: if (p->exprblock.leftp->addrblock.vstg == STGINTR) break; ! 390: commonset = YES; ! 391: if (p->exprblock.rightp == NULL) break; ! 392: args = p->exprblock.rightp->listblock.listp; ! 393: for (; args; args = args->nextp) ! 394: if (args->datap->tag == TADDR) ! 395: { ! 396: lhs = (Addrp) args->datap; ! 397: switch (lhs->vstg) ! 398: { ! 399: case STGARG: ! 400: case STGAUTO: ! 401: case STGBSS: ! 402: case STGINIT: ! 403: case STGCOMMON: ! 404: case STGEQUIV: ! 405: case STGREG: ! 406: case STGPREG: ! 407: varinfo = lookup(lhs); ! 408: varinfo->sets++; ! 409: } ! 410: } ! 411: else if (args->datap->tag == TTEMP) ! 412: { ! 413: lhs = (Addrp) args->datap; ! 414: varinfo = lookup (lhs); ! 415: varinfo->sets++; ! 416: } ! 417: break; ! 418: } ! 419: ! 420: return; ! 421: ! 422: case TTEMP: ! 423: varinfo = lookup((Addrp) p); ! 424: varinfo->uses++; ! 425: return; ! 426: ! 427: case TADDR: ! 428: setsuses(p->addrblock.memoffset); ! 429: setsuses(p->addrblock.vleng); ! 430: varinfo = lookup((Addrp) p); ! 431: varinfo->uses++; ! 432: return; ! 433: ! 434: case TLIST: ! 435: for (args = p->listblock.listp; args; args = args->nextp) ! 436: setsuses(args->datap); ! 437: ! 438: case TCONST: ! 439: case TERROR: ! 440: return; ! 441: ! 442: default: ! 443: fatal("O9: bad tag value"); ! 444: } ! 445: } ! 446: ! 447: ! 448: LOCAL int anex(p) ! 449: expptr p; ! 450: ! 451: { ! 452: int s1, s2, s3; ! 453: expptr q; ! 454: Varp varinfo; ! 455: chainp ch; ! 456: int setfirst; ! 457: expptr expr; ! 458: ! 459: ! 460: if (p == ENULL) ! 461: return SCSAFE; ! 462: ! 463: switch (p->tag) ! 464: { ! 465: case TCONST: ! 466: return SCSAFE; ! 467: ! 468: case TLIST: ! 469: for (ch = p->listblock.listp; ch; ch = ch->nextp) ! 470: { ! 471: s1 = anex (ch->datap); ! 472: if (s1 == SCSAFE) ! 473: removesafe (&ch->datap); ! 474: } ! 475: return SCFREE; ! 476: ! 477: case TEXPR: ! 478: s1 = anex(p->exprblock.leftp); ! 479: s2 = anex(p->exprblock.rightp); ! 480: s3 = anex(p->exprblock.vleng); ! 481: ! 482: switch (p->exprblock.opcode) ! 483: { ! 484: case OPASSIGN: ! 485: expr = p->exprblock.leftp; ! 486: varinfo = lookup(expr); ! 487: setfirst = varinfo->setfirst && (varinfo->sets == 1); ! 488: if (expr->tag == TTEMP && setfirst && ! 489: s2 == SCSAFE && s3 == SCSAFE) ! 490: { ! 491: movefrtemp (expr); ! 492: return SCSAFE; ! 493: } ! 494: else ! 495: { ! 496: if (s2 == SCSAFE) removesafe (&p->exprblock.rightp); ! 497: if (s3 == SCSAFE) removesafe (&p->exprblock.vleng); ! 498: return SCFREE; ! 499: } ! 500: ! 501: case OPNEG: ! 502: case OPNOT: ! 503: case OPABS: ! 504: case OPADDR: ! 505: case OPBITNOT: ! 506: if ((s2 == SCSAFE) && (s3 == SCSAFE)) ! 507: return s1; ! 508: else ! 509: return SCFREE; ! 510: ! 511: case OPCONV: ! 512: if ((s2 != SCSAFE) || (s3 != SCSAFE)) ! 513: return SCFREE; ! 514: ! 515: if (ISINT(p->exprblock.vtype)) ! 516: return s1; ! 517: if (ISINT(p->exprblock.leftp->headblock.vtype)) ! 518: return s1; ! 519: ! 520: return SCFREE; ! 521: ! 522: ! 523: case OPSTAR: ! 524: if (ISINT(p->exprblock.vtype)) ! 525: goto safeop; ! 526: ! 527: if (safefactor(p->exprblock.leftp) || ! 528: safefactor(p->exprblock.rightp)) ! 529: goto safeop; ! 530: ! 531: goto floatop; ! 532: ! 533: ! 534: case OPPLUS: ! 535: case OPMINUS: ! 536: if (ISINT(p->exprblock.vtype)) ! 537: goto safeop; ! 538: ! 539: floatop: ! 540: if (!(ISREAL(p->exprblock.vtype) || ISCOMPLEX(p->exprblock.vtype))) ! 541: return SCFREE; ! 542: ! 543: switch (s1) ! 544: { ! 545: case SCSAFE: ! 546: removesafe(&p->exprblock.leftp); ! 547: if (s2 == SCSAFE) ! 548: removesafe(&p->exprblock.leftp); ! 549: return SCFREE; ! 550: ! 551: case SCFREE: ! 552: if (s2 == SCSAFE) ! 553: removesafe(&p->exprblock.rightp); ! 554: return SCFREE; ! 555: } ! 556: ! 557: case OPOR: ! 558: case OPAND: ! 559: case OPEQV: ! 560: case OPNEQV: ! 561: case OPLT: ! 562: case OPEQ: ! 563: case OPGT: ! 564: case OPLE: ! 565: case OPNE: ! 566: case OPGE: ! 567: case OPLSHIFT: ! 568: case OPMIN: ! 569: case OPMAX: ! 570: case OPBITOR: ! 571: case OPBITAND: ! 572: case OPBITXOR: ! 573: case OPRSHIFT: ! 574: safeop: ! 575: if ((p->exprblock.vleng != ENULL) && ( ! ISCONST(p->exprblock.vleng))) ! 576: return SCFREE; ! 577: ! 578: switch (s1) ! 579: { ! 580: case SCSAFE: ! 581: if (s2 == SCFREE) removesafe (&p->exprblock.leftp); ! 582: return s2; ! 583: ! 584: case SCFREE: ! 585: if (s2 == SCSAFE) removesafe (&p->exprblock.rightp); ! 586: return SCFREE; ! 587: } ! 588: ! 589: default: ! 590: if (s1 == SCSAFE) removesafe(&p->exprblock.leftp); ! 591: if (s2 == SCSAFE) removesafe(&p->exprblock.rightp); ! 592: if (s3 == SCSAFE) removesafe(&p->exprblock.vleng); ! 593: return SCFREE; ! 594: } ! 595: ! 596: ! 597: case TTEMP: ! 598: varinfo = lookup(p); ! 599: if (varinfo->sets == 0) ! 600: return SCSAFE; ! 601: else ! 602: return SCFREE; ! 603: ! 604: case TADDR: ! 605: s1 = anex(p->addrblock.memoffset); ! 606: s2 = anex(p->addrblock.vleng); ! 607: ! 608: varinfo = lookup(p); ! 609: ! 610: if (varinfo->sets == 0) ! 611: switch (s1) ! 612: { ! 613: case SCSAFE: ! 614: if (s2 == SCFREE) removesafe(&p->addrblock.memoffset); ! 615: return s2; ! 616: ! 617: case SCFREE: ! 618: if (s2 == SCSAFE) removesafe(&p->addrblock.vleng); ! 619: return SCFREE; ! 620: } ! 621: ! 622: if (s1 == SCSAFE) removesafe(&p->addrblock.memoffset); ! 623: if (s2 == SCSAFE) removesafe(&p->addrblock.vleng); ! 624: return SCFREE; ! 625: ! 626: ! 627: default: ! 628: return SCFREE; ! 629: } ! 630: } ! 631: ! 632: ! 633: LOCAL safefactor(p) ! 634: expptr p; ! 635: ! 636: { ! 637: if ( ! ISCONST(p)) ! 638: return NO; ! 639: ! 640: if (ISINT(p->constblock.vtype)) ! 641: if (abs(p->constblock.const.ci) <= 1) ! 642: return YES; ! 643: ! 644: if (ISREAL(p->constblock.vtype)) ! 645: if (abs(p->constblock.const.cd[0]) <= 1.0) ! 646: return YES; ! 647: ! 648: return NO; ! 649: } ! 650: ! 651: ! 652: LOCAL int worthcost(p) ! 653: expptr p; ! 654: ! 655: { ! 656: int cost; ! 657: chainp q; ! 658: expptr memoffset,vleng; ! 659: ! 660: if (p == ENULL) ! 661: return NO; ! 662: ! 663: switch (p->tag) ! 664: { ! 665: case TCONST: ! 666: return NO; ! 667: ! 668: case TTEMP: ! 669: return NO; ! 670: ! 671: case TADDR: ! 672: if ((vleng = p->addrblock.vleng) && ! ISCONST(vleng)) ! 673: return NO; /* Can't make variable length temporaries */ ! 674: if ((memoffset = p->addrblock.memoffset) && ! ISCONST(memoffset)) ! 675: return YES; ! 676: else ! 677: return NO; ! 678: ! 679: case TEXPR: ! 680: return YES; ! 681: ! 682: case TLIST: ! 683: cost = 0; ! 684: for (q = p->listblock.listp; q; q = q->nextp) ! 685: { ! 686: if (worthcost ((expptr) q->datap)) ! 687: return YES; ! 688: cost++; ! 689: } ! 690: return (cost>2 ? YES : NO); ! 691: ! 692: default: ! 693: return NO; ! 694: } ! 695: } ! 696: ! 697: ! 698: LOCAL removesafe(refexpr) ! 699: expptr *refexpr; ! 700: ! 701: { ! 702: expptr ep; ! 703: Tempp ap; ! 704: Slotp newslot; ! 705: ! 706: extern Addrp gettemp(); ! 707: ! 708: ep = *refexpr; ! 709: if (! worthcost(ep)) ! 710: return; ! 711: ! 712: if (ep->tag == TEXPR && ep->exprblock.opcode == OPASSIGN) ! 713: { ! 714: if (ep->exprblock.leftp->tag != TTEMP) ! 715: fatal ("non-TEMP in assignment to be moved in optloop"); ! 716: ! 717: newslot = optinsert (SKEQ, ep, 0, 0, first); ! 718: *refexpr = (expptr) cpexpr (ep->exprblock.leftp); ! 719: } ! 720: else ! 721: { ! 722: ap = (Tempp) gettemp(ep); ! 723: newslot = optinsert (SKEQ, mkexpr(OPASSIGN,cpexpr(ap),ep), 0, 0, first); ! 724: *refexpr = (expptr) ap; ! 725: optinsert (SKFRTEMP,ap->memalloc,0,0,last->next); ! 726: } ! 727: ! 728: comocount++; ! 729: if (!newcode) ! 730: newcode = newslot; ! 731: ! 732: return; ! 733: } ! 734: ! 735: ! 736: LOCAL Addrp gettemp(p) ! 737: expptr p; ! 738: ! 739: { ! 740: return mktemp(p->headblock.vtype, p->headblock.vleng); ! 741: } ! 742: ! 743: ! 744: ! 745: LOCAL movefrtemp (expr) ! 746: Tempp expr; ! 747: ! 748: { ! 749: Slotp s; ! 750: ! 751: if (expr->tag != TTEMP) ! 752: badtag ("movefrtemp",expr->tag); ! 753: ! 754: for (s = first; s; s = s->next) ! 755: if (s->type == SKFRTEMP && s->expr == (expptr) expr->memalloc) ! 756: { ! 757: removeslot (s); ! 758: insertslot (s,last->next); ! 759: return; ! 760: } ! 761: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.