![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to optim.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / b / bin / c / n2|
Return to optim.c CVS log | Up to [MW Coherent from dump] / coherent / b / bin / c / n2 |
1.1 ! root 1: /* ! 2: * n2/optim.c ! 3: * C compiler. ! 4: * Jump and shape optimization. ! 5: * Jump to jump, etc. ! 6: * Common sequences. ! 7: * Cross jumping. ! 8: */ ! 9: ! 10: #ifdef vax ! 11: #include "INC$LIB:cc2.h" ! 12: #else ! 13: #include "cc2.h" ! 14: #endif ! 15: ! 16: #define NLHASH 64 ! 17: #define LHMASK 077 ! 18: ! 19: static INS *labhash[NLHASH]; ! 20: ! 21: /* ! 22: * Shuffle segments, ! 23: * Move all non 'SHRI' segments to the front, ! 24: * then squash any extra switches out of the stream. ! 25: * This is necessary to make code that is together in ! 26: * memory together in the 'ins' lists. ! 27: */ ! 28: shuffle() ! 29: { ! 30: register INS *fp, *ip; ! 31: register INS *niloc; ! 32: INS *bep, *bfp; ! 33: register int curseg; ! 34: ! 35: niloc = &ins; ! 36: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) { ! 37: if (ip->i_type != ENTER) ! 38: continue; ! 39: bfp = ip; ! 40: do { ! 41: ip = ip->i_fp; ! 42: } while (ip->i_type != ENTER); ! 43: if (bfp != ins.i_fp) { ! 44: bep = ip; ! 45: ip = bfp->i_bp; ! 46: bfp->i_bp->i_fp = bep->i_fp; ! 47: bep->i_fp->i_bp = bfp->i_bp; ! 48: niloc->i_fp->i_bp = bep; ! 49: bfp->i_bp = niloc; ! 50: bep->i_fp = niloc->i_fp; ! 51: niloc->i_fp = bfp; ! 52: niloc = bep; ! 53: } ! 54: } ! 55: curseg = dotseg; ! 56: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) { ! 57: if (ip->i_type != ENTER) ! 58: continue; ! 59: while ((fp=ip->i_fp)!=&ins && fp->i_type==ENTER) ! 60: ip = deleteins(ip, ip->i_fp)->i_fp; ! 61: if (ip->i_seg == curseg) { ! 62: ip = deleteins(ip, ip->i_fp); ! 63: continue; ! 64: } ! 65: curseg = ip->i_seg; ! 66: } ! 67: } ! 68: ! 69: /* ! 70: * Delete node ip. ! 71: * Return a pointer to the previous node. ! 72: * Merge any line number references onto ip1. ! 73: */ ! 74: INS * ! 75: deleteins(ip, ip1) ! 76: register INS *ip; ! 77: INS *ip1; ! 78: { ! 79: register INS *bp, *fp; ! 80: ! 81: mrgdbgt(ip, ip1); ! 82: if ((ip->i_type==JUMP || ip->i_type==LLLINK) && ((fp=ip->i_ip)!=NULL)) ! 83: decrefc(fp); ! 84: bp = ip->i_bp; ! 85: fp = ip->i_fp; ! 86: bp->i_fp = fp; ! 87: fp->i_bp = bp; ! 88: free((char *) ip); ! 89: return bp; ! 90: } ! 91: ! 92: /* ! 93: * Decrement the reference count on a label. ! 94: * Delete it if the label is now unreferenced. ! 95: * It is a fatal error to hand this routine a non label. ! 96: */ ! 97: decrefc(ip) ! 98: register INS *ip; ! 99: { ! 100: if (ip->i_type != LLABEL) ! 101: cbotch("decrefc passed non label"); ! 102: if (--ip->i_refc == 0) ! 103: deleteins(ip, ip->i_fp); ! 104: } ! 105: ! 106: /* ! 107: * Set up label reference counts and delete any unused labels. ! 108: */ ! 109: labels() ! 110: { ! 111: register INS *fp, *ip, *lp; ! 112: INS *findlab(); ! 113: register int curseg, i; ! 114: ! 115: for (i=0; i<NLHASH; ++i) ! 116: labhash[i] = NULL; ! 117: curseg = dotseg; ! 118: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) { ! 119: if (ip->i_type == ENTER) ! 120: curseg = ip->i_seg; ! 121: else if (ip->i_type == LLABEL) { ! 122: ip->i_refc = 0; ! 123: /* ! 124: * Hack the reference count on the ! 125: * label if it is the label on a switch ! 126: * table to prevent it from being deleted ! 127: * by the next bit of code. Kludgy. ! 128: */ ! 129: if (curseg != SCODE) ! 130: ++ip->i_refc; ! 131: else if ((fp=ip->i_fp) != &ins) { ! 132: if (fp->i_type == LLLINK) ! 133: ++ip->i_refc; ! 134: else if (fp->i_type == CODE ! 135: && fp->i_op >= ZBYTE ! 136: && fp->i_op <= ZGPTR) ! 137: ++ip->i_refc; ! 138: } ! 139: labhash[ip->i_labno&LHMASK] = ip; ! 140: } ! 141: } ! 142: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) { ! 143: if (ip->i_type!=JUMP && ip->i_type!=LLLINK) ! 144: continue; ! 145: if ((lp=findlab(ip->i_labno)) != NULL) { ! 146: while ((fp=lp->i_fp)!=&ins && fp->i_type==LLABEL) ! 147: lp = fp; ! 148: ip->i_labno = lp->i_labno; ! 149: ++lp->i_refc; ! 150: } ! 151: ip->i_ip = lp; ! 152: } ! 153: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) { ! 154: if (ip->i_type!=LLABEL || ip->i_refc!=0) ! 155: continue; ! 156: ip = deleteins(ip, ip->i_fp); ! 157: ++nlabdel; ! 158: } ! 159: } ! 160: ! 161: /* ! 162: * Find label. ! 163: * Quick test using hashtable. ! 164: * Long linear search if that fails. ! 165: */ ! 166: INS * ! 167: findlab(n) ! 168: register int n; ! 169: { ! 170: register INS *lp; ! 171: ! 172: if ((lp=labhash[n&LHMASK])!=NULL && lp->i_labno==n) ! 173: return lp; ! 174: for (lp=ins.i_fp; lp!=&ins; lp=lp->i_fp) ! 175: if (lp->i_type==LLABEL && lp->i_labno==n) ! 176: return lp; ! 177: return NULL; ! 178: } ! 179: ! 180: /* ! 181: * Delete dead code. ! 182: * Dead code begins after an unconditional jump and continues ! 183: * until the next label, segment change or the EPILOG. ! 184: */ ! 185: deadcode() ! 186: { ! 187: register INS *fp, *ip; ! 188: register int t; ! 189: ! 190: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) { ! 191: t = ip->i_type; ! 192: if (t == LLLINK) { /* Switch table */ ! 193: while ((fp=ip->i_fp) != &ins && (fp->i_type == LLLINK ! 194: || (fp->i_type == CODE && opinfo[fp->i_op].op_style ! 195: == OF_WORD))) ! 196: ip = fp; ! 197: } else if (t != JUMP || ip->i_rel != UNCON) ! 198: continue; ! 199: fp = ip->i_fp; ! 200: while (fp != &ins) { ! 201: t = fp->i_type; ! 202: if (t==LLABEL || t==EPILOG || t==ENTER) ! 203: break; ! 204: fp = deleteins(fp, fp->i_fp)->i_fp; ! 205: ++ndead; ! 206: ++changes; ! 207: } ! 208: } ! 209: } ! 210: ! 211: /* ! 212: * Fix some of the more common funny things ! 213: * associated with jump instructions and labels. ! 214: * There are more things that could be done. ! 215: * These five things should get most of the common things. ! 216: */ ! 217: fixbr() ! 218: { ! 219: register INS *ip, *ip1, *ip2; ! 220: INS *ip3, *ip4; ! 221: int t; ! 222: ! 223: again: ! 224: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) { ! 225: t = ip->i_type; ! 226: /* Jump to jump. */ ! 227: if ((t==JUMP && ischnrel(ip->i_rel)) || t==LLLINK) { ! 228: ip1 = ip->i_ip; ! 229: if (ip1 != NULL) { ! 230: ip2 = ip1; ! 231: for (;;) { ! 232: while (ip2->i_type == LLABEL) ! 233: ip2 = ip2->i_fp; ! 234: if (ip2->i_type!=JUMP ! 235: || ip2->i_rel!=UNCON) ! 236: break; ! 237: ip3 = ip2->i_ip; ! 238: if (ip3==NULL ! 239: || ip3==ip1 ! 240: || ip3==ip2->i_bp) ! 241: break; ! 242: ip2 = ip3; ! 243: } ! 244: ip2 = ip2->i_bp; ! 245: if (ip1 != ip2) { ! 246: decrefc(ip1); ! 247: increfc(ip2); ! 248: ip->i_labno = ip2->i_labno; ! 249: ip->i_ip = ip2; ! 250: ++nbrbr; ! 251: ++changes; ! 252: } ! 253: } ! 254: } ! 255: /* Reversible jump over unconditional jump. */ ! 256: if (t==JUMP && isrevrel(ip->i_rel)) { ! 257: ip1 = ip->i_fp; ! 258: if (ip1->i_type==JUMP && ip1->i_rel==UNCON) { ! 259: ip2 = ip1->i_fp; ! 260: if (ip2->i_type==LLABEL && ip->i_ip==ip2) { ! 261: ip1->i_rel = revrel(ip->i_rel); ! 262: deleteins(ip, ip1); ! 263: ++ncbrbr; ! 264: ++changes; ! 265: goto again; ! 266: } ! 267: } ! 268: } ! 269: /* Jump to next instruction. */ ! 270: if (t==JUMP && ip->i_ip==ip->i_fp) { ! 271: deleteins(ip, ip->i_fp); ! 272: ++nbrnext; ! 273: ++changes; ! 274: goto again; ! 275: } ! 276: /* Conditional jump followed by unconditional jump to same loc. */ ! 277: if (t==JUMP && ip->i_rel!=UNCON ! 278: && (ip1=ip->i_fp)->i_type==JUMP && ip1->i_rel==UNCON ! 279: && ip->i_ip==ip1->i_ip) { ! 280: deleteins(ip, ip->i_fp); ! 281: ++nexbr; ! 282: ++changes; ! 283: goto again; ! 284: } ! 285: /* ! 286: * The preceding optimizations do not change the code order, ! 287: * so they can be executed even if VNOOPT. ! 288: * The following optimizations do change the code order, ! 289: * so they are suppressed if VNOOPT. ! 290: */ ! 291: if (isvariant(VNOOPT)) ! 292: continue; ! 293: /* ! 294: * [ip]JUMP L1; [ip1]L2:...; [ip2]L1:...; [ip3]JUMP L2; ... ! 295: * becomes [ip2]L1:...; [ip1]L2:...; [ip]JUMP L1; ... ! 296: * Saves a jump in every for loop. ! 297: */ ! 298: if (t==JUMP && ip->i_rel==UNCON) { ! 299: ip1 = ip->i_fp; ! 300: if (ip1!=&ins && ip1->i_type==LLABEL) { ! 301: ip2 = NULL; ! 302: for (ip3=ip1->i_fp; ip3!=&ins; ip3=ip3->i_fp) { ! 303: if (ip3->i_type==LLABEL ! 304: && ip->i_ip==ip3) ! 305: ip2 = ip3; ! 306: else if (ip2!=NULL ! 307: && ip3->i_type==JUMP ! 308: && ip3->i_rel==UNCON ! 309: && ip3->i_ip==ip1) { ! 310: ip4 = ip2->i_bp; ! 311: ip->i_bp->i_fp = ip2; ! 312: ip3->i_bp->i_fp = ip1; ! 313: ip4->i_fp = ip; ! 314: ip->i_fp = ip3; ! 315: ip2->i_bp = ip->i_bp; ! 316: ip1->i_bp = ip3->i_bp; ! 317: ip->i_bp = ip4; ! 318: ip3->i_bp = ip; ! 319: deleteins(ip3, ip1); ! 320: ++nexbr; ! 321: ++changes; ! 322: goto again; ! 323: } ! 324: } ! 325: } ! 326: } ! 327: /* ! 328: * [ip] JUMP L1; <code1>; [ip2] JUMP L2; [ip1] L1: <code2>; [ip3] L2: ! 329: * becomes [ip1] L1: <code2>; [ip] JUMP L2; <code1>; [ip3] L2: ! 330: * Saves a jump in every switch and restores natural code order. ! 331: * <code2> often ends in JUMP or LLLINK, in which case JUMP L2 ! 332: * gets optimized out later. ! 333: */ ! 334: if (t==JUMP && ip->i_rel==UNCON && precedes(ip, ip->i_ip)) { ! 335: ip1 = ip->i_ip; ! 336: ip2 = ip1->i_bp; ! 337: if (ip2->i_type==JUMP && ip2->i_rel==UNCON ! 338: && precedes(ip1, ip2->i_ip)) { ! 339: ip3 = ip2->i_ip; ! 340: /* Rearrange the code. */ ! 341: ip->i_bp->i_fp = ip1; ! 342: ip3->i_bp->i_fp = ip; ! 343: ip2->i_fp = ip3; ! 344: ip1->i_bp = ip->i_bp; ! 345: ip->i_bp = ip3->i_bp; ! 346: ip3->i_bp = ip2; ! 347: /* Change JUMP L1 at ip into JUMP L2. */ ! 348: ip->i_ip = ip3; ! 349: ip->i_labno = ip3->i_labno; ! 350: increfc(ip3); ! 351: decrefc(ip1); ! 352: /* Delete the now extraneous JUMP. */ ! 353: deleteins(ip2, ip3); ! 354: ++nexbr; ! 355: ++changes; ! 356: goto again; ! 357: } ! 358: } ! 359: } ! 360: } ! 361: ! 362: /* ! 363: * Return true iff ip1 precedes ip2 in the INS node chain. ! 364: */ ! 365: static ! 366: precedes(ip1, ip2) ! 367: register INS *ip1, *ip2; ! 368: { ! 369: while ((ip1 = ip1->i_fp) != &ins) ! 370: if (ip1 == ip2) ! 371: return 1; ! 372: return 0; ! 373: } ! 374: ! 375: /* ! 376: * Increment the reference count on a label. ! 377: * It is a fatal error to hand this routine a non label. ! 378: */ ! 379: increfc(ip) ! 380: register INS *ip; ! 381: { ! 382: if (ip->i_type != LLABEL) ! 383: cbotch("increfc passed non label"); ! 384: ++ip->i_refc; ! 385: } ! 386: ! 387: /* ! 388: * Insert a label. ! 389: * It has been 'increfc'ed. ! 390: * Return pointer to the new label. ! 391: */ ! 392: INS * ! 393: inslab(ip) ! 394: register INS *ip; ! 395: { ! 396: register INS *lp, *bp; ! 397: ! 398: if (ip->i_type == LLABEL) { ! 399: increfc(ip); ! 400: return ip; ! 401: } ! 402: lp = (INS *) malloc(sizeof(INS)); ! 403: if (lp != NULL) { ! 404: lp->i_type = LLABEL; ! 405: lp->i_labno = newlab(); ! 406: lp->i_sp = NULL; ! 407: lp->i_refc = 1; ! 408: bp = ip->i_bp; ! 409: bp->i_fp = lp; ! 410: lp->i_fp = ip; ! 411: ip->i_bp = lp; ! 412: lp->i_bp = bp; ! 413: } ! 414: return lp; ! 415: } ! 416: ! 417: /* ! 418: * Cross jumps. ! 419: * If the same code precedes an unconditional jump and ! 420: * the label to which it jumps, replace the former with ! 421: * a jump to a new local label. ! 422: */ ! 423: xjumps() ! 424: { ! 425: register INS *ip, *lp; ! 426: ! 427: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) { ! 428: if (ip->i_type!=JUMP || ip->i_rel!=UNCON ! 429: || (lp = ip->i_ip)==NULL) ! 430: continue; ! 431: if (!docomseq(lp, ip, &nxjump)) ! 432: return; ! 433: } ! 434: } ! 435: ! 436: /* ! 437: * Compare two nodes. ! 438: * True return if the same. ! 439: * Never called on strange stuff ! 440: * or labels. ! 441: */ ! 442: xeq(ip1, ip2) ! 443: register INS *ip1, *ip2; ! 444: { ! 445: register int t; ! 446: ! 447: if ((t=ip1->i_type) != ip2->i_type) ! 448: return 0; ! 449: if (t==JUMP || t==LLLINK) { ! 450: if (ip1->i_labno != ip2->i_labno) ! 451: return 0; ! 452: if (t==JUMP && ip1->i_rel!=ip2->i_rel) ! 453: return 0; ! 454: return 1; ! 455: } ! 456: if (t != CODE) ! 457: cbotch("xeq"); ! 458: if (ip1->i_op != ip2->i_op) ! 459: return 0; ! 460: if (ip1->i_naddr != ip2->i_naddr) ! 461: return 0; ! 462: return cmpfield(ip1, ip2); ! 463: } ! 464: ! 465: /* ! 466: * Detect common sequences before jumps. ! 467: * When found, replace the later with a jump to a new ! 468: * local label preceding the former. ! 469: */ ! 470: comseq() ! 471: { ! 472: register INS *ip, *xp, *yp; ! 473: ! 474: for (xp=ins.i_fp; xp!=&ins; xp=xp->i_fp) { ! 475: if (xp->i_type!=JUMP || xp->i_rel!=UNCON) ! 476: continue; ! 477: ip = xp->i_ip; ! 478: if (ip==NULL || ip->i_type != LLABEL) ! 479: continue; ! 480: for (yp=xp->i_fp; yp!=&ins; yp=yp->i_fp) { ! 481: if (yp->i_type==JUMP && yp->i_rel==UNCON ! 482: && yp->i_ip==ip) { ! 483: if (!docomseq(xp, yp, &ncomseq)) ! 484: return; ! 485: } ! 486: } ! 487: } ! 488: } ! 489: ! 490: ! 491: /* ! 492: * Back up through the code looking for valid cross jumps. ! 493: * When found, insert a new local label before the first ! 494: * and change the second into an unconditional jump to it. ! 495: * Called from xjumps and comseq. ! 496: * Returns 0 if the new node allocation fails. ! 497: */ ! 498: docomseq(xp, yp, countp) ! 499: register INS *xp, *yp; ! 500: int *countp; ! 501: { ! 502: for (;;) { ! 503: xp = xp->i_bp; ! 504: if (xp==&ins || xp->i_type==LLABEL || xp->i_type==LLLINK) ! 505: break; ! 506: yp = yp->i_bp; ! 507: if (yp==&ins || yp->i_type==LLABEL || yp->i_type==LLLINK ! 508: || xeq(xp, yp)==0) ! 509: break; ! 510: xp = inslab(xp); ! 511: if (xp == NULL) ! 512: return 0; ! 513: mrgdbgt(yp, xp->i_fp); ! 514: if ((yp->i_type==JUMP || yp->i_type==LLLINK) && yp->i_ip!=NULL) ! 515: decrefc(yp->i_ip); ! 516: yp->i_type = JUMP; ! 517: yp->i_labno = xp->i_labno; ! 518: yp->i_sp = NULL; ! 519: yp->i_ip = xp; ! 520: yp->i_rel = UNCON; ! 521: yp->i_long = 0; ! 522: ++*countp; ! 523: ++changes; ! 524: } ! 525: return 1; ! 526: } ! 527: ! 528: /* end of n2/optim.c */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.