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