![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to cost.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / jerq / sgs / comp|
Return to cost.c CVS log | Up to [Research Unix] / researchv9 / jerq / sgs / comp |
1.1 ! root 1: /* @(#) cost.c: 1.5 3/9/84 */ ! 2: ! 3: # include "mfile2.h" ! 4: ! 5: # ifndef CSTORE ! 6: # define CSTORE(q) 2 ! 7: # endif ! 8: # ifndef CLOAD ! 9: # define CLOAD(q) 2 ! 10: # endif ! 11: # ifndef CCTEST ! 12: # define CCTEST(q) 1 ! 13: # endif ! 14: # ifndef DFLT_STRATEGY ! 15: # define DFLT_STRATEGY LTOR|RTOL ! 16: # endif ! 17: ! 18: /* enough regs so there is always a free pair */ ! 19: # define HREG ((1+NRGS)/2+1) ! 20: ! 21: #define LSAVED 30 ! 22: /* stores costs of leaves costed so far */ ! 23: static struct leaf { ! 24: int op; ! 25: int type; ! 26: int cst[NCOSTS]; ! 27: } leafcosts[LSAVED], *leaf_ptr=leafcosts, *recost_leaf=0; ! 28: /* used to identify subtrees */ ! 29: # define NSUBTREES 10 ! 30: int nsubtree; ! 31: NODE *subtree[NSUBTREES]; ! 32: int subgoal[NSUBTREES]; ! 33: ! 34: int strbc[NCOSTS]; /* the strategy done by bcost */ ! 35: SHAPE * lshbc[NCOSTS]; /* left-hand shape */ ! 36: SHAPE * rshbc[NCOSTS]; /* right-hand shape */ ! 37: ! 38: commute( p ) NODE *p; { ! 39: /* commute p in place */ ! 40: register NODE *q; ! 41: #ifndef NODBG ! 42: if(odebug) printf("commute: .=%u l=%u r=%u\n",p,p->in.left,p->in.right); ! 43: #endif ! 44: q = p->in.left; ! 45: p->in.left = p->in.right; ! 46: p->in.right = q; ! 47: } ! 48: ! 49: # ifndef NODBG ! 50: # define GETS(x,y) if( e2debug>1) printf( " x gets %d\n", y ); ! 51: # define GETSN(x,y) if( e2debug>1) printf( " cst[%d] gets %d\n", x, y ); ! 52: # else ! 53: # define GETS(x,y) ! 54: # define GETSN(x,y) ! 55: # endif ! 56: ! 57: bcost( p, q ) ! 58: register NODE *p; ! 59: register OPTAB *q; ! 60: { ! 61: /* return the basic costs of matching q against tree p */ ! 62: /* sha is set previously by match with a list of legal left ! 63: /* and right shapes */ ! 64: /* bcost updates strbc, lshbc, and rshbc to reflect the ! 65: /* strategy, left shape, and right shape, that minimizes the cost ! 66: /* for q on p */ ! 67: ! 68: /* j has its address taken, so it can't be in a reg */ ! 69: int j; ! 70: int o, cc, c, s, tc, ttc, n, nn, lnn, lregs, rregs, cs, res; ! 71: int il, ir; /* index into left and right address shapes */ ! 72: int lsubtree; ! 73: NODE *l, *r; ! 74: register NODE *pp; ! 75: register ix; ! 76: SHAPE *sl, *sr; ! 77: ! 78: o = p->tn.op; ! 79: ! 80: /* look for the simple cases with register counts */ ! 81: n = (q->needs&NCOUNT); ! 82: if( (q->needs&NPAIR) && n<HREG ) n = HREG; ! 83: ! 84: /* set up the left and right descendents */ ! 85: l = getlo( p, o ); ! 86: r = getro( p, o ); ! 87: /* ! 88: * If the operator table entry does not have a left shape, ! 89: * but it does have a right shape, then this ! 90: * table entry is for leaves ONLY, referenced to p, not to r ! 91: */ ! 92: if( q->rshape && !q->lshape) ! 93: r = p; ! 94: ! 95: res = q->rewrite; ! 96: ! 97: /* determine the code generation strategy */ ! 98: ! 99: if( o == COMOP ) cerror( "COMOP in bcost" ); ! 100: ! 101: s = LTOR; /* default strategy */ ! 102: ! 103: if( optype(o) == BITYPE ) { ! 104: ! 105: switch( o ) { ! 106: ! 107: case CALL: ! 108: case STCALL: ! 109: case FORTCALL: ! 110: # ifndef LTORARGS ! 111: case CM: /* function arguments */ ! 112: # endif ! 113: s = RTOL; ! 114: break; ! 115: ! 116: default: ! 117: # ifdef STACK ! 118: if( asgop(o) ) s = RTOL; ! 119: else s = LTOR; ! 120: # else ! 121: s = DFLT_STRATEGY; ! 122: # endif ! 123: break; ! 124: } ! 125: } ! 126: ! 127: # ifndef NODBG ! 128: if(e2debug) { ! 129: printf("bcost(%d(%s),%d(%s),%x), s = ", ! 130: p-node, opst[o], q->stinline, opst[q->op], sha[0] ); ! 131: pstrat(s); ! 132: printf( "\n" ); ! 133: printf( "\tneeds=%d%s%s\n", n, ! 134: (q->needs&LSHARE)?", LSHARE":"", ! 135: (q->needs&RSHARE)?", RSHARE":"" ); ! 136: printf( "\tshape table: (%d %d %d ... )(%d %d %d ... )\n", ! 137: sha[0][0]-shapes, sha[0][1]-shapes, sha[0][2]-shapes, ! 138: sha[1][0]-shapes, sha[1][1]-shapes, sha[1][2]-shapes ! 139: ); ! 140: } ! 141: # endif ! 142: ! 143: /* triple loop: ! 144: /* double loop over the left and right sides */ ! 145: /* single loop over the number of regs available */ ! 146: ! 147: for( il=0; (sl = sha[0][il]) || il==0; ++il ) { ! 148: lregs = lsubtree = nsubtree = 0; ! 149: c = q->cost; ! 150: lnn = n; ! 151: if( sl ) { ! 152: /* list the left subtrees */ ! 153: findsub( l, sl ); ! 154: if( l->tn.op==REG && sl->op==REG && asgop(q->op) ! 155: && !asgop(o) ) { ! 156: ! 157: /* in an expression such as a+b, where a is */ ! 158: /* a register var, copy a to a scratch reg */ ! 159: /* before using += to do the add */ ! 160: /* this test causes that copy, by suggesting */ ! 161: /* that the lhs is a subtree, even though it ! 162: /* matches the template exactly */ ! 163: ! 164: subtree[nsubtree] = l; ! 165: subgoal[nsubtree] = NRGS; ! 166: ++nsubtree; ! 167: } ! 168: lsubtree = nsubtree; ! 169: ! 170: /* account for the cost of the shape */ ! 171: c += q->lcount * sl->sc; ! 172: ! 173: /* count lhs register usage */ ! 174: for( lregs=ix=0; ix<lsubtree; ++ix ) { ! 175: if( subgoal[ix] == NRGS ) { ! 176: lregs += szty(subtree[ix]->tn.type); ! 177: } ! 178: } ! 179: if( !(q->needs&LSHARE) ) lnn += lregs; ! 180: } ! 181: ! 182: # ifndef NODBG ! 183: if( e2debug ) { ! 184: printf( "\tbcost left shape: sl=%d(%s), cost=%d\n", ! 185: sl-shapes, sl?opst[sl->op]:"?", c ); ! 186: printf( "\t%d left subtrees\n", nsubtree ); ! 187: for( j=0; j<nsubtree; ++j ) { ! 188: printf( "\t\tsubtree %d, goal %d\n", ! 189: subtree[j]-node, subgoal[j] ); ! 190: } ! 191: } ! 192: # endif ! 193: ! 194: for( ir=0; (sr = sha[1][ir]) || ir==0; ++ir ) { ! 195: ttc = c; ! 196: nsubtree = lsubtree; ! 197: if( sr ) { ! 198: ttc += q->rcount * sr->sc; ! 199: findsub( r, sr ); ! 200: } ! 201: # ifndef NODBG ! 202: if( e2debug ) { ! 203: printf( "\tbcost rt. shp: sr=%d(%s), cost=%d\n", ! 204: sr-shapes, sr?opst[sr->op]:"?", ttc ); ! 205: printf( "\t%d right subtrees\n", ! 206: nsubtree-lsubtree ); ! 207: for( j=lsubtree; j<nsubtree; ++j ) { ! 208: printf( "\t\tsubtree %d, goal %d\n", ! 209: subtree[j]-node, subgoal[j] ); ! 210: } ! 211: } ! 212: # endif ! 213: ! 214: /* figure out the minimum number of regs. possible */ ! 215: for( rregs=0,ix=lsubtree; ix<nsubtree; ++ix ) { ! 216: if( subgoal[ix] == NRGS ) { ! 217: rregs += szty(subtree[ix]->tn.type); ! 218: } ! 219: } ! 220: ! 221: nn = lnn; ! 222: if( q->needs & RSHARE ) nn -= rregs; ! 223: if( nn < lregs ) nn = lregs; ! 224: nn += rregs; ! 225: ! 226: # ifndef NODBG ! 227: if( e2debug ) { ! 228: printf( "%d left, %d right regs, need >= %d\n", ! 229: lregs, rregs, nn ); ! 230: } ! 231: # endif ! 232: ! 233: for( j=NRGS; j>=nn; --j ) { ! 234: # ifndef NODBG ! 235: if( e2debug ) { ! 236: printf( "\t*** j = %d ***\n", j ); ! 237: } ! 238: # endif ! 239: /* exact match: don't fool around */ ! 240: if( nsubtree==0 ) { ! 241: cc = ttc; ! 242: cs = LTOR; ! 243: goto distribute; ! 244: } ! 245: /* general case: grub around */ ! 246: /* LTOR means ascending, RTOL means descending*/ ! 247: ! 248: cc = INFINITY; ! 249: if( s<OR ){ /* do it left to right */ ! 250: int j1 = j; ! 251: tc = ttc; ! 252: for( ix=0; ix<nsubtree; ++ix ) { ! 253: pp = subtree[ix]; ! 254: if( subgoal[ix] == NRGS ){ ! 255: /* shouldn't happen */ ! 256: if( j1<0 ) tc=INFINITY; ! 257: else tc+=pp->tn.cst[j1]; ! 258: j1 -= szty(pp->tn.type); ! 259: } ! 260: else tc += ! 261: pp->tn.cst[subgoal[ix]]; ! 262: } ! 263: cc = tc; ! 264: cs = LTOR; ! 265: } ! 266: if( s&RTOL ){ /* do it right to left */ ! 267: int j1 = j; ! 268: tc = ttc; ! 269: for( ix=nsubtree-1; ix>=0; --ix ) { ! 270: pp = subtree[ix]; ! 271: if( subgoal[ix] == NRGS ){ ! 272: /* shouldn't happen */ ! 273: if( j1<0 ) tc=INFINITY; ! 274: else tc+=pp->tn.cst[j1]; ! 275: j1 -= szty(pp->tn.type); ! 276: } ! 277: else tc += ! 278: pp->tn.cst[subgoal[ix]]; ! 279: } ! 280: if( tc < cc ){ ! 281: cc = tc; ! 282: cs = RTOL; ! 283: } ! 284: } ! 285: if( cc >= INFINITY ) break; /* done */ ! 286: ! 287: /* now, cc is the minmal cost with j regs */ ! 288: /* update the various cost measures */ ! 289: /* everything affects CEFF */ ! 290: distribute: ! 291: # ifndef NODBG ! 292: if( e2debug ) { ! 293: printf( "\tdistribute %d\n", cc ); ! 294: } ! 295: # endif ! 296: if( cc < p->tn.cst[CEFF] ) { ! 297: GETS(EFF,cc); ! 298: p->tn.cst[CEFF] = cc; ! 299: strbc[CEFF] = cs; ! 300: lshbc[CEFF] = sl; ! 301: rshbc[CEFF] = sr; ! 302: } ! 303: /* for EFF, only do with NRGS */ ! 304: if( p->tn.goal == CEFF ) break; ! 305: if( res == RNULL || res == RNOP ){ ! 306: /* affects only CEFF */ ! 307: cerror( "RNULL/RNOP error" ); ! 308: } ! 309: ! 310: if( (p->tn.goal==CCC) && (res&RESCC) ) { ! 311: /* CC's set */ ! 312: if( cc < p->tn.cst[CCC] ) { ! 313: GETS(CC,cc); ! 314: p->tn.cst[CCC] = cc; ! 315: strbc[CCC] = cs; ! 316: lshbc[CCC] = sl; ! 317: rshbc[CCC] = sr; ! 318: } ! 319: } ! 320: ! 321: ! 322: /* now, the register cost */ ! 323: tc = cc; ! 324: if( (res&RLEFT) && sl->op != REG ){ ! 325: cc += CLOAD(q); ! 326: } ! 327: else if( (res&RRIGHT) && sr->op != REG ){ ! 328: cc += CLOAD(q); ! 329: } ! 330: if( cc < p->tn.cst[j] ) { ! 331: GETSN(j,cc); ! 332: p->tn.cst[j] = cc; ! 333: strbc[j] = cs; ! 334: lshbc[j] = sl; ! 335: rshbc[j] = sr; ! 336: } ! 337: ! 338: /* for CC's, only do w. NRGS */ ! 339: if( p->tn.goal == CCC ) break; ! 340: ! 341: if( j != NRGS ) continue; ! 342: ! 343: /* record if lhs is actually a temp */ ! 344: /* need only do for NRGS */ ! 345: ! 346: if( tempok(p) && tc < p->tn.cst[CTEMP] ) { ! 347: GETS(TEMP,tc); ! 348: p->tn.cst[CTEMP] = tc; ! 349: strbc[CTEMP] = cs; ! 350: lshbc[CTEMP] = sl; ! 351: rshbc[CTEMP] = sr; ! 352: } ! 353: } ! 354: } ! 355: } ! 356: ! 357: /* now, some global cleanup */ ! 358: /* some things are worth updating only once per template */ ! 359: ! 360: if( p->tn.goal == CEFF ) return; /* done */ ! 361: ! 362: /* set Condition Codes by testing a register */ ! 363: if( p->tn.goal == CCC ) { ! 364: tc = p->tn.cst[NRGS]+CCTEST(q); ! 365: if( tc < p->tn.cst[CCC] ) { ! 366: GETS(CC,tc); ! 367: p->tn.cst[CCC] = tc; ! 368: strbc[CCC] = strbc[NRGS]; ! 369: lshbc[CCC] = lshbc[NRGS]; ! 370: rshbc[CCC] = rshbc[NRGS]; ! 371: } ! 372: return; ! 373: } ! 374: ! 375: /* put into TEMP by putting into REG, then storing */ ! 376: /* if the lhs type is OK and we have an assignment op, don't ! 377: /* need to store: just use the result from EFF */ ! 378: ! 379: if( asgop(o) && o!=INCR && o!= DECR && lhsok( l ) && ! 380: p->tn.type == l->tn.type ) { ! 381: cc = p->tn.cst[CEFF]; ! 382: if( cc < p->tn.cst[CTEMP] ) { ! 383: GETS(CTEMP,cc); ! 384: p->tn.cst[CTEMP] = cc; ! 385: strbc[CTEMP] = strbc[CEFF]; ! 386: lshbc[CTEMP] = lshbc[CEFF]; ! 387: rshbc[CTEMP] = rshbc[CEFF]; ! 388: } ! 389: } ! 390: tc = p->tn.cst[NRGS] + CSTORE(q); ! 391: ! 392: if( tc < p->tn.cst[CTEMP] ) { ! 393: GETS(TEMP,tc); ! 394: p->tn.cst[CTEMP] = tc; ! 395: strbc[CTEMP] = strbc[NRGS]; ! 396: lshbc[CTEMP] = lshbc[NRGS]; ! 397: rshbc[CTEMP] = rshbc[NRGS]; ! 398: } ! 399: ! 400: /* compute with few regs by storing, then loading */ ! 401: ! 402: tc = p->tn.cst[CTEMP] + CLOAD(q); ! 403: ! 404: for( j=1; j<NRGS; ++j ) { ! 405: if( tc < p->tn.cst[j] ) { ! 406: p->tn.cst[j] = tc; ! 407: GETSN(j,tc); ! 408: strbc[j] = strbc[CTEMP] | STORE; ! 409: lshbc[j] = lshbc[CTEMP]; ! 410: rshbc[j] = rshbc[CTEMP]; ! 411: } ! 412: } ! 413: } ! 414: ! 415: lhsok( p ) ! 416: NODE *p; ! 417: { ! 418: /* p appears on the lhs of an assignment op */ ! 419: /* is it an OK substitute for a TEMP? */ ! 420: ! 421: switch( p->tn.op ) { ! 422: ! 423: case NAME: ! 424: case VAUTO: ! 425: case VPARAM: ! 426: case TEMP: ! 427: case REG: ! 428: return( 1 ); ! 429: ! 430: } ! 431: return( 0 ); ! 432: } ! 433: ! 434: shpr(sp) register SHAPE *sp; { ! 435: if (!sp) return; ! 436: if( sp->op < 0 || sp->op > DSIZE ) cerror( "shape op %d\n", sp->op ); ! 437: printf(" %s", opst[sp->op]); ! 438: shpr(sp->sl); ! 439: shpr(sp->sr); ! 440: } ! 441: ! 442: pstrat( s ) { ! 443: /* print a nice version of the strategy s */ ! 444: register i, flag; ! 445: static char *stratnames[] = { ! 446: "STORE", ! 447: "LTOR", ! 448: "RTOL", ! 449: 0 }; ! 450: flag = 0; ! 451: for( i=0; stratnames[i]; ++i ){ ! 452: if( s & (1<<i) ) { ! 453: if( flag ) putchar( '|' ); ! 454: printf( "%s", stratnames[i] ); ! 455: flag = 1; ! 456: } ! 457: } ! 458: if( !flag ) printf( "0" ); ! 459: } ! 460: ! 461: insout( p, i ) ! 462: NODE *p; ! 463: { ! 464: OPTAB *q; ! 465: int c, o, j; ! 466: ! 467: /* generate the actual instructions */ ! 468: /* if the cost is infinite, try rewriting */ ! 469: ! 470: c = p->in.cst[i]; ! 471: o = p->tn.op; ! 472: ! 473: #ifndef NODBG ! 474: if( odebug>1 ) printf( "insout(%d,%d), cost %d\n", p-node,i,c ); ! 475: #endif ! 476: if( c >= INFINITY ){ ! 477: cerror( "missing table entry, op %s", opst[p->tn.op] ); ! 478: } ! 479: ! 480: /* handle COMOP specially */ ! 481: if( o == COMOP ) { ! 482: q = match( p, (OPTAB *)0 ); /* had better match */ ! 483: if( !q ) cerror( "COMOP match fails" ); ! 484: bprt( p, q, i ); ! 485: return; ! 486: } ! 487: ! 488: /* want to force bcost to do some work */ ! 489: /* this is because the strbc, etc., arrays, set by bcost, are used ! 490: /* by bprt */ ! 491: ! 492: for( j=0; j<NCOSTS; ++j ) ++p->in.cst[j]; ! 493: for( q=0; q = match( p, q ); ){ ! 494: if( i != CEFF ) { ! 495: if( q->rewrite & RLEFT ) restrip( sha[0] ); ! 496: if( q->rewrite & RRIGHT ) restrip( sha[1] ); ! 497: } ! 498: bcost( p, q ); ! 499: if( p->tn.cst[i] == c ) { /* we have found it */ ! 500: if( strbc[i]&STORE ) bprt( p, q, CTEMP ); ! 501: else bprt( p, q, i ); ! 502: return; ! 503: } ! 504: } ! 505: ! 506: /* commuting must be in order here */ ! 507: /* if fast flag is on, we can only fail, but it's ok to try */ ! 508: ! 509: if( o != PLUS && o != MUL && o != AND && o != OR && o != ER ) { ! 510: e2print( p ); ! 511: cerror( "commute??, op[%d] == %s", o, opst[o] ); ! 512: } ! 513: commute( p ); /* this is the payoff; don't need to commute back */ ! 514: for( q=0; q = match( p, q ); ){ ! 515: if( i != CEFF ) { ! 516: if( q->rewrite & RLEFT ) restrip( sha[0] ); ! 517: if( q->rewrite & RRIGHT ) restrip( sha[1] ); ! 518: } ! 519: bcost( p, q ); ! 520: if( p->tn.cst[i] == c ) { /* we found it */ ! 521: bprt( p, q, i ); ! 522: return; ! 523: } ! 524: } ! 525: ! 526: cerror( "insout returns without a match" ); ! 527: /* NOTREACHED */ ! 528: ! 529: } ! 530: ! 531: bprt( p, q, i ) ! 532: NODE *p; ! 533: OPTAB *q; ! 534: { ! 535: /* this routine is called to print out the actual instructions */ ! 536: /* it is called with a tree node p, a template q, and a goal i */ ! 537: /* bprt calls bcost, and then captures the left and right shapes */ ! 538: /* it then uses findsub to determine the preconditions and goals */ ! 539: /* a local copy of this information must be made, since bprt can be ! 540: /* called recursively */ ! 541: /* then, bprt calls insout to output the instructions that establish ! 542: /* the preconditions. Finally, it can output its own instruction */ ! 543: ! 544: int j, j1, s, o, k; ! 545: NODE *l, *r; ! 546: SHAPE *ls, *rs; ! 547: int nn; ! 548: int mygoal[NSUBTREES]; ! 549: NODE *mysubs[NSUBTREES]; ! 550: ! 551: /* sets j as well */ ! 552: if( i < NRGS ) j = i; ! 553: else j = NRGS; ! 554: l = getl( p ); ! 555: r = getr( p ); ! 556: if (q->rshape && !q->lshape) ! 557: r = p; ! 558: s = strbc[i]; ! 559: ls = lshbc[i]; ! 560: rs = rshbc[i]; ! 561: o = p->tn.op; ! 562: # ifndef NODBG ! 563: if( odebug>1 ) { ! 564: printf( " matches %d, ls = %d(%s), rs = %d(%s), s= ", ! 565: q->stinline, ls-shapes, ls?opst[ls->op]:"SHNL", ! 566: rs-shapes, rs?opst[rs->op]:"SHNL" ); ! 567: pstrat( s ); ! 568: printf( "\n" ); ! 569: } ! 570: # endif ! 571: ! 572: /* handle COMOP differently; this has more to do with the register ! 573: /* allocation than the ordering */ ! 574: ! 575: if( o == COMOP ) { ! 576: insout( l, CEFF ); ! 577: insout( r, i ); ! 578: goto generate; ! 579: } ! 580: ! 581: nsubtree = 0; ! 582: if(rs && (s&RTOL) ) findsub( r, rs ); ! 583: if( ls ) { ! 584: findsub( l, ls ); ! 585: if( l->tn.op==REG && ls->op==REG && asgop(q->op) && ! 586: !asgop(o) ) { ! 587: /* we must arrange to copy a reg variable on the lhs ! 588: /* of a binary op, in some cases (cf. bcost) */ ! 589: subtree[nsubtree] = l; ! 590: subgoal[nsubtree] = NRGS; ! 591: ++nsubtree; ! 592: } ! 593: } ! 594: if(rs && (s<OR) ) findsub( r, rs ); ! 595: nn = nsubtree; ! 596: ! 597: /* make a local copy */ ! 598: for( k=0; k<nn; ++k ) { ! 599: mygoal[k] = subgoal[k]; ! 600: mysubs[k] = subtree[k]; ! 601: } ! 602: ! 603: # ifndef NODBG ! 604: if( odebug>1 ) { /* subtree matches are: */ ! 605: printf( "\t\t%d matches\n", nn ); ! 606: for( k=0; k<nn; ++k ) { ! 607: printf( "\t\tnode %d, goal %d\n",mysubs[k]-node, ! 608: mygoal[k] ); ! 609: } ! 610: } ! 611: # endif ! 612: ! 613: /* do the subtrees */ ! 614: /* someday, rewrite the temps right here and now */ ! 615: ! 616: j1 = j; ! 617: for( k=0; k<nn; ++k ) { ! 618: # ifndef NODBG ! 619: if( odebug>2 ) ! 620: printf( "\t\tcalling insout(%d,%d)\n", mysubs[k]-node, ! 621: j1 ); ! 622: # endif ! 623: if( mygoal[k] == NRGS ) { ! 624: insout( mysubs[k], j1 ); ! 625: j1 -= szty( mysubs[k]->tn.type ); ! 626: } ! 627: else { ! 628: insout( mysubs[k], mygoal[k] ); ! 629: } ! 630: } ! 631: /* put onto the instruction string the info about the instruction */ ! 632: generate: ! 633: if( nins >= NINS ) cerror( "too many instructions generated" ); ! 634: inst[nins].p = p; ! 635: inst[nins].q = q; ! 636: inst[nins].goal = i; ! 637: /* a special case: REG op= xxx, should be done as early as possible */ ! 638: if( asgop(o) && p->in.left->tn.op == REG && o != INCR && o != DECR ! 639: && i!=CEFF && i!=CCC && !istreg(p->in.left->tn.rval)){ ! 640: /* "istreg" guards against rewriting returns, switches, etc. */ ! 641: inst[nins].goal = CTEMP; ! 642: } ! 643: ++nins; ! 644: } ! 645: ! 646: findsub( p, s ) ! 647: NODE *p; ! 648: SHAPE *s; ! 649: { ! 650: /* account for the costs of matching the shape s with the tree j */ ! 651: ! 652: if( !s ) ! 653: return; ! 654: ! 655: # ifndef NODBG ! 656: if( e2debug>1 ) { ! 657: printf( "\t\tfindsub( %d, %d )\n", p-node, s-shapes ); ! 658: } ! 659: # endif ! 660: ! 661: switch( s->op ) { ! 662: ! 663: case TEMP: ! 664: /* leave j unchanged */ ! 665: if( p->tn.op == TEMP ) return; ! 666: subtree[nsubtree] = p; ! 667: subgoal[nsubtree] = CTEMP; ! 668: ++nsubtree; ! 669: return; ! 670: ! 671: case FREE: ! 672: subtree[nsubtree] = p; ! 673: subgoal[nsubtree] = CEFF; ! 674: ++nsubtree; ! 675: return; ! 676: ! 677: case CCODES: ! 678: subtree[nsubtree] = p; ! 679: subgoal[nsubtree] = CCC; ! 680: ++nsubtree; ! 681: return; ! 682: ! 683: case REG: ! 684: if( p->tn.op == REG ) return; /* exact match */ ! 685: ! 686: /* in general, look beneath */ ! 687: /* also, look here if a REG and rcst is 1 */ ! 688: ! 689: subtree[nsubtree] = p; ! 690: subgoal[nsubtree] = NRGS; ! 691: ++nsubtree; ! 692: return; ! 693: } ! 694: ! 695: if( s->op == p->tn.op ) { ! 696: ! 697: /* look at subtrees */ ! 698: if( s->sl ) findsub( getl(p), s->sl ); ! 699: if( s->sr ) findsub( getr(p), s->sr ); ! 700: return; ! 701: } ! 702: } ! 703: ! 704: costs( p ) register NODE *p; { ! 705: register OPTAB *q; ! 706: int i, o, ty; ! 707: register *pc; ! 708: ! 709: /* compute the costs for p */ ! 710: /* the goal is either NRGS (into a reg. or temp), CCC, or CEFF */ ! 711: ! 712: /* in a stack machine, this will probably look very different. ! 713: /* it is possible that seting szty() to be 0 will deal with the ! 714: /* stack machine problems; if not, we will need to put some special ! 715: /* code in here under control of ifdef STACK ! 716: /* the stack machine issue is that the "register" use on the left does ! 717: /* not limit the computations on the right, and conversely */ ! 718: again: ! 719: ty = optype( o = p->tn.op ); ! 720: if (ty == LTYPE && get_leaf(p) ) return(0); ! 721: pc = p->in.cst; ! 722: for( i=0; i<NCOSTS; ++i ) { ! 723: pc[i] = INFINITY; ! 724: strbc[i] = 0; ! 725: lshbc[i] = rshbc[i] = (SHAPE *)0; ! 726: } ! 727: ! 728: # ifndef NODBG ! 729: if( udebug ) { ! 730: printf( "costs( %d, %d ), op = %s\n", p-node, ! 731: p->tn.goal, opst[o] ); ! 732: } ! 733: # endif ! 734: ! 735: if( ty != LTYPE ) if( costs( p->in.left ) ) return(1); ! 736: if( ty == BITYPE ) if( costs( p->in.right ) ) return(1); ! 737: ! 738: pc = p->in.cst; ! 739: ! 740: /* now, compute the costs based on matches */ ! 741: /* handle COMOP specially */ ! 742: if( o == COMOP ) { ! 743: int cc = p->in.left->in.cst[CEFF]; ! 744: for( i=NRGS; i<NCOSTS; ++i ) { ! 745: pc[i] = cc + p->in.right->in.cst[i]; ! 746: if( pc[i] > INFINITY ) pc[i] = INFINITY; ! 747: } ! 748: return(0); ! 749: } ! 750: ! 751: for( q=0; q = match(p,q); ){ ! 752: if( p->tn.goal != CEFF ) { ! 753: if( q->rewrite & RLEFT ) restrip( sha[0] ); ! 754: if( q->rewrite & RRIGHT ) restrip( sha[1] ); ! 755: } ! 756: bcost( p, q ); ! 757: # ifndef NODBG ! 758: if( udebug ) { ! 759: printf( "bcost( %d, %d )\n", p-node, q->stinline); ! 760: e222print( 1, p, "T" ); ! 761: } ! 762: # endif ! 763: } ! 764: ! 765: #ifndef NOCOMMUTE ! 766: /* don't commute if we are trying to be fast */ ! 767: if( !fast && (o==PLUS||o==MUL||o==AND||o==OR||o==ER) ){ ! 768: # ifndef NODBG ! 769: if( udebug ) { ! 770: printf( "COMMUTE %d *******\n", p-node ); ! 771: } ! 772: # endif ! 773: commute( p ); ! 774: for( q=0; q = match(p,q); ){ ! 775: if( p->tn.goal != CEFF ) { ! 776: if( q->rewrite & RLEFT ) restrip( sha[0] ); ! 777: if( q->rewrite & RRIGHT ) restrip( sha[1] ); ! 778: } ! 779: bcost( p, q ); ! 780: # ifndef NODBG ! 781: if( udebug ) { ! 782: printf( "bcost( %d, %d )\n", p-node, q->stinline); ! 783: e222print( 1, p, "T" ); ! 784: } ! 785: # endif ! 786: } ! 787: commute( p ); ! 788: # ifndef NODBG ! 789: if( udebug ) { ! 790: printf( "END OF COMMUTE %d *******\n", p-node ); ! 791: } ! 792: # endif ! 793: } ! 794: ! 795: /* END OF COMMUTE CODE ***** */ ! 796: # endif ! 797: ! 798: /* here is a big worry; when do we do this rewriting? ! 799: /* if we do it too early, we may miss some neat possibilities */ ! 800: /* if we do it too late, we may have miscomputed some earlier things */ ! 801: ! 802: if( pc[p->tn.goal]>=INFINITY ){ ! 803: if( p->fn.type == TSTRUCT ) return(0); ! 804: if( optype( o ) == LTYPE ) return( 0 ); ! 805: if( rewass( p ) ) return( 1 ); /* major rewrite */ ! 806: goto again; /* minor rewrite: restart here */ ! 807: } ! 808: if (ty == LTYPE) ! 809: save_leaf(p); ! 810: return( 0 ); ! 811: } ! 812: static get_leaf(p) ! 813: register NODE *p; ! 814: { ! 815: register struct leaf *lf; ! 816: /*see if this leaf/type pair is in the tables*/ ! 817: /* multiple flavored ICON's don't save properly */ ! 818: if ( p->tn.op == ICON ) return(0); ! 819: recost_leaf=0; ! 820: for (lf=leafcosts;lf < leaf_ptr; lf++){ ! 821: if (lf->op == p->tn.op && lf->type == p->tn.type) ! 822: { ! 823: /*if the saved cost was infinite, we will have ! 824: to recost the leaf anyway*/ ! 825: if (lf->cst[p->tn.goal] >= INFINITY) ! 826: { ! 827: recost_leaf = lf; ! 828: return(0); ! 829: } ! 830: /*else, load the costs and leave*/ ! 831: memcpy(p->tn.cst,lf->cst,sizeof(int)*NCOSTS); ! 832: return(1); ! 833: } ! 834: } /*end for*/ ! 835: return(0); ! 836: } /*end get_leaf*/ ! 837: ! 838: static save_leaf(p) ! 839: register NODE *p; ! 840: { ! 841: /*save the costs of this leaf for future reference. ! 842: if recost_leaf is non-zero, it is already in the ! 843: table*/ ! 844: register struct leaf *lf; ! 845: if ( p->tn.op == ICON ) ! 846: { ! 847: /* ICONs have too many flavors to save by op */ ! 848: recost_leaf=0; ! 849: return; ! 850: } ! 851: if ( !recost_leaf && (leaf_ptr >= leafcosts + LSAVED) ) return; ! 852: lf = recost_leaf ? recost_leaf : leaf_ptr++; ! 853: lf->op = p->tn.op; ! 854: lf->type = p->tn.type; ! 855: memcpy(lf->cst,p->tn.cst,sizeof(int)*NCOSTS); ! 856: recost_leaf=0; ! 857: } ! 858:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.