![[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.