![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to func.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / jerq / sgs / optim|
Return to func.c CVS log | Up to [Research Unix] / researchv9 / jerq / sgs / optim |
1.1 root 1: /* @(#) func.c: 1.4 4/28/84 */
2:
3: /* func.c
4: **
5: ** Function improvement routines
6: **
7: **
8: ** This file contains routines that require knowledge of a whole
9: ** function or more to perform their optimizations.
10: */
11:
12: #include "optim.h"
13: #include "optutil.h"
14: #include "storclass.h"
15: #include <string.h>
16: #include "paths.h"
17:
18: /* Macro to add new instruction:
19: ** opn op code number of new instruction
20: ** opst op code string of new instruction
21: ** opn1 operand 1 for new instruction
22: ** opn2 operand 2 for new instruction
23: */
24:
25: #define addi(opn,opst,opn1,opn2) \
26: { \
27: pn = insert( pn ); /* get new node */ \
28: chgop( pn, opn, opst ); /* put in opcode num, str */ \
29: pn->op1 = opn1; /* put in operands */ \
30: pn->op2 = opn2; \
31: }
32: #define opm ops[MAXOPS]
33:
34: #ifdef IMPREGAL
35: /* register allocation optimization
36: **
37: ** F. B. Wolverton 6/16/83
38: **
39: ** This optimization accepts a list of autos and args from the
40: ** compiler and assigns them to registers if there is sufficient estimated
41: ** payoff.
42: **
43: ** Scratch registers are used first, if they are available,
44: ** because they are "free". A variable can be put into a scratch register if
45: ** (a) the register is not used by any instruction in the procedure,
46: ** (b) the variable is dead, i.e., not used before being set,
47: ** following any call in the procedure
48: **
49: ** Register 3 is considered a scratch register, if IMPSCRATCH is defined.
50: **
51: ** Next registers r8 through r4 are assigned (and r3, if it has not been used
52: ** as a scratch register).
53: **
54: ** Register variables assigned by the compiler are assigned first. A variable
55: ** the compiler assigned to a user register may get assigned to a scratch
56: ** register by the optimizer.
57: **
58: ** Variables in the list of autos and args are assigned next.
59: **
60: ** The cumulative cost for puting all variables up to a given variable
61: ** into registers is computed and used to select a cutoff.
62: ** All register variables assigned by the compiler remain in
63: ** registers. Other variables are assigned only if the
64: ** estimated payoff os positive.
65: **
66: ** Instruction operands are modified to reflect the additional assignments.
67: **
68: */
69:
70: #define MAXREGS 10
71: #define MAXVARS 20
72:
73: /* variable storage classes */
74:
75: #define SCLNULL 0
76: #define AUTO 1
77: #define REGISTER 4
78: #define PARAM 9
79:
80: /* register types */
81:
82: #define SCRATCH 0
83: #define USER 1
84:
85: /* register status */
86:
87: #define AVAIL 0
88: #define NOTAVAIL 1
89:
90: /* cycle estimates for BELLMAC-32B instructions */
91:
92: #define CYCSAVE 39 /* SAVE and RESTORE with 0 user registers */
93: #define CYCDELTA 5 /* delta to save and restore an additional register */
94: #define CYCADD 6 /* ADD small literal to stack pointer */
95: #define CYCMOVS 16 /* MOVW from register to register offset and back */
96: #define CYCAWORD 7 /* MOVAW of register offset to frame pointer */
97: #define CYCPUSH 10 /* PUSH a regsiter */
98: #define CYCPOP 10 /* POPW a value into a register */
99:
100: struct hinode { /* ordered table of variables with highest estimators */
101: int hiestim; /* estimator of cycle payoff */
102: int hiscl; /* scl of quant to put in reg */
103: char* hiname; /* name of quantity:
104: * local offset
105: * argument offset*/
106: int hilen; /* length in bytes of quantity */
107: } high[MAXVARS];
108:
109: int vars = 0; /* number of variables stored in 'high' array */
110: int nodblflg = 0; /* flag indicating absence of doubles */
111:
112: struct assign {
113: char *asrname; /* register name */
114: char *asrind; /* indirect reference through register */
115: int asrtype; /* register type */
116: int asrsave; /* number of user registers saved */
117: int asavail; /* availabilty of register */
118: int asestim; /* estimator of cycle payoff of assigned variable */
119: int asvscl; /* storage class of variable assigned */
120: char *asvname; /* variable name */
121: int asvlen; /* variable lenggth in bytes */
122: } asreg[MAXREGS] = {
123: { "%r0", "0(%r0)", SCRATCH, 0 },
124: { "%r1", "0(%r1)", SCRATCH, 0 },
125: { "%r2", "0(%r2)", SCRATCH, 0 },
126: { "%r3", "0(%r3)", SCRATCH, 0 },
127: { "%r8", "0(%r8)", USER, 1 },
128: { "%r7", "0(%r7)", USER, 2 },
129: { "%r6", "0(%r6)", USER, 3 },
130: { "%r5", "0(%r5)", USER, 4 },
131: { "%r4", "0(%r4)", USER, 5 },
132: { "%r3", "0(%r3)", USER, 6 }
133: };
134:
135: /* Note that register 3 appears twice. It is used as a scratch register if
136: ** possible and as a user register otherwise.
137: */
138:
139: char* rnames[] = { "%r8", "%r7", "%r6", "%r5", "%r4", "%r3" };
140:
141:
142: /* routine to read in table of variables stored in high[] */
143:
144: void
145: ratable( p )
146: register char *p;
147:
148: {
149: extern int atoi();
150: register char *q, *r;
151:
152: /* check for table overflow */
153: if( vars >= MAXVARS ) return;
154:
155: /* scan to estimator and read it */
156: while( *p++ != '\t' );
157: high[vars].hiestim = atoi( p );
158:
159: /* scan to storage class and read it */
160: while( *p++ != '\t' );
161: switch (*p) {
162: case 'A': high[vars].hiscl = AUTO; break;
163: case 'P': high[vars].hiscl = PARAM; break;
164: /* set doubles flag */
165: case 'N': nodblflg = 1; return;
166: }
167:
168: /* scan to name and read it */
169: while( *p++ != '\t' );
170: q = p;
171: while( *q++ != '\t' );
172: high[vars].hiname = r = getspace( q - p );
173: while( p < ( q - 1 ) ) *r++ = *p++;
174: *r = '\0';
175:
176: /* read length */
177: high[vars].hilen = atoi(q);
178:
179: /* increment table index */
180: vars++;
181: return;
182: }
183:
184:
185: /* main routine for register allocation optimization */
186:
187: int
188: raoptim( numnreg, numauto )
189: register int numnreg; /* input number of registers saved/restored */
190: register int numauto; /* number of words of automatic variables */
191:
192: {
193: void raavail(), ravassign(), raremove(), raopn(), raparam(), radef();
194: void rainsld(), raremld();
195: int rarassign(), racut();
196: int iascut; /* index for assignment cutoff */
197: int iasrlast; /* index of the last register variable assigned */
198: int newnreg; /* new number of registers to be saved */
199: register int ias;
200:
201: /* check for doubles */
202: if( nodblflg == 0 ) {
203: vars = 0;
204: return( numnreg );
205: }
206:
207: /* initialize assignment table */
208: for( ias = 0; ias < MAXREGS; ias++ ) {
209: asreg[ias].asavail = AVAIL;
210: asreg[ias].asvscl = SCLNULL;
211: asreg[ias].asvlen = 0;
212: }
213:
214: /* determine availability of scratch registers */
215: raavail( numnreg );
216:
217: /* insert branch pointers for live/dead analysis */
218: rainsld();
219:
220: /* assign register variables */
221: iasrlast = rarassign( numnreg );
222:
223: /* assign non-register variables */
224: ravassign();
225:
226: /* remove remove branch pointers from live/dead analysis */
227: raremld();
228:
229: /* compute cutoff from cumulative payoff */
230: iascut = racut( numnreg, numauto, iasrlast );
231: if( iascut < 0 ) { /* if no payoff for this optimization */
232: vars = 0;
233: return( numnreg );
234: }
235: newnreg = asreg[iascut].asrsave;
236:
237: /* modify the instruction operands */
238: raopn( iascut, newnreg );
239:
240: /* insert moves for parameters */
241: raparam( iascut );
242:
243: /* modify def statements */
244: radef( iascut );
245:
246: /* re-initailize for next procedure */
247: vars = 0;
248: return( newnreg );
249: }
250:
251: /* determine availability of scratch registers */
252: void
253: raavail( numnreg )
254: int numnreg; /* input number of registers to be saved/restored */
255: {
256: register NODE *pn;
257: register struct assign *pa;
258: register int iop, i;
259: register char *p;
260: struct assign *map[MAXREGS];
261:
262: /* check availability of scratch %r3 */
263: if( numnreg == 6 ) asreg[3].asavail = NOTAVAIL;
264: else asreg[9].asavail = NOTAVAIL;
265: #ifndef IMPSCRATCH
266: asreg[3].asavail = NOTAVAIL;
267: asreg[9].asavail = AVAIL;
268: #endif /* IMPSCRATCH */
269:
270: /* set up mapping for scratch registers */
271: for( i = 0; i < MAXREGS; i++ ) map[i] = NULL;
272: for( i = 0; i < MAXREGS; i++ ) {
273: pa = &asreg[i];
274: if( pa->asrtype == SCRATCH && pa->asavail == AVAIL )
275: map[*( pa-> asrname + 2 ) - '0'] = pa;
276: }
277:
278: /* scan for uses */
279: for( ALLN( pn ) ) { /* scan nodes */
280: if( pn->op == FILTER ) continue;
281: /* check for use of scratch registers */
282: for( iop = 1; iop < MAXOPS + 1; iop++ ) { /* scan operands */
283: if( ( p = pn->ops[iop] ) == NULL ) continue;
284: while( *p != '\0' ) {
285: if( *p++ != '%' ) continue;
286: if( *p++ != 'r' ) break;
287: pa = map[*p - '0'];
288: if( pa != NULL ) pa->asavail = NOTAVAIL;
289: break;
290: }
291: }
292: }
293: }
294:
295: /* insert pointers for live/dead analysis */
296: void
297: rainsld()
298: {
299: register NODE *pn, *qn;
300: register char *ppn;
301:
302: for( ALLN( pn ) ) {
303: if( isbr( pn ) && !isret( pn ) ) {
304: ppn = getp( pn );
305: /* use wraparound scan when looking for label */
306: for( qn = ( pn->forw != &ntail ) ? pn->forw : n0.forw;
307: qn != pn; qn = ( qn->forw != &ntail ) ?
308: qn->forw : n0.forw ) {
309: if( islabel( qn ) ) {
310: if(*(ppn + 2) != *(qn->ops[0] + 2) &&
311: *(ppn + 1) != '\0' )
312: continue; /* for speed */
313: if( strcmp( ppn, qn->ops[0] ) == 0 ){
314: pn -> opm = (char *) qn;
315: break;
316: }
317: }
318: }
319: }
320: }
321: }
322:
323: /* assign register variables */
324: int
325: rarassign( numnreg )
326: register int numnreg; /* input number of registers to be saved/restored */
327: {
328: register struct assign *pa;
329: register int ias, ireg, ok;
330: int iasrlast;
331:
332: iasrlast = -1;
333:
334: /* assign to first available register, and mark unavailable */
335: for( ireg = 0; ireg < numnreg; ireg++ ) {
336: /* check whether is dead at CALL's etc. */
337: ok = raregok( rnames[ireg], 0 );
338: for( ias = 0; ias < MAXREGS; ias++ ) {
339: pa = &asreg[ias];
340: if( pa->asavail == NOTAVAIL ) continue;
341: if( pa->asrtype == SCRATCH && !ok ) continue;
342:
343: /* assign it */
344: pa->asavail = NOTAVAIL;
345: pa->asestim = 0;
346: pa->asvscl = REGISTER;
347: pa->asvname = rnames[ireg];
348: pa->asvlen = 4;
349: if( iasrlast < ias ) iasrlast = ias;
350: break;
351: }
352: }
353: return( iasrlast );
354: }
355:
356: /* assign non-register variables */
357: void
358: ravassign()
359: {
360: register int ivar, ias, ok;
361: register struct assign *pa;
362: register struct hinode *ph;
363:
364: /* go through variables */
365: for( ivar = 0; ivar < vars; ivar++ ) {
366: ph = &high[ivar];
367: /* check to see if dead at CALL's etc. */
368: ok = raregok(ph->hiname, ph->hilen);
369: /* assign to first register that qualifies */
370: for( ias = 0; ias < MAXREGS; ias++ ) {
371: pa = &asreg[ias];
372: if( pa->asavail == NOTAVAIL ) continue;
373: if( pa->asrtype == SCRATCH && !ok ) continue;
374:
375: /* assign it */
376: pa->asavail = NOTAVAIL;
377: pa->asestim = ph->hiestim;
378: pa->asvscl = ph->hiscl;
379: pa->asvname = ph->hiname;
380: pa->asvlen = ph->hilen;
381: break;
382: }
383: }
384: }
385:
386: /* check if dead at CALL's etc. */
387: int
388: raregok( name, len )
389: register char *name; /* pointer to register or variable name */
390: register int len; /* length of variable (0 for register) */
391: {
392: register NODE *pn;
393: NODE *rald();
394:
395: for( pn = n0.forw; pn != 0; pn = pn->forw ) { /* scan nodes */
396: switch( pn->op ) {
397: default: continue;
398: case CALL:
399: case JSB:
400: case MOVBLB:
401: case MOVBLH:
402: case MOVBLW:
403: /* check if 'name' is live */
404: if( rald( pn->forw, name, len ) != NULL ) return( 0 );
405: }
406: }
407: /* dead */
408: return( 1 );
409: }
410:
411: /* check for register or variable dead in a block */
412: /* Note that this routine may visit a block more than
413: * once, but that it cannot loop because any closed path
414: * in the program contains at least one label, and the
415: * routine will not scan a block beginning with a given
416: * label more than once.
417: */
418: NODE *
419: rald( pn, name, len )
420: register NODE *pn; /* pointer to block to be searched */
421: register char *name; /* pointer to register or variable name */
422: register int len; /* length of variable (0 for register) */
423: {
424: NODE *qn;
425: register int iop;
426: register char *p;
427: int srcsize, dstsize;
428:
429: /* scan block */
430: for( ; pn != 0; pn = pn->forw ) {
431: if( pn->op == FILTER ) continue;
432: /*control recursion */
433: if( islabel( pn ) ) {
434: /* terminate recursion if this block has been visited */
435: if( pn->opm == name ) return( NULL );
436: /* mark block as visited */
437: pn->opm = name;
438: continue;
439: }
440: /* if no references, its dead */
441: if( isret( pn ) ) return( NULL );
442: /* end of block */
443: if( isbr( pn ) ) break;
444: /* check operands of remaining instructions */
445: for( iop = 1; iop < MAXOPS + 1; iop++ ) {
446: p = pn->ops[iop];
447: if( p == NULL ) continue;
448: /* look for register or variable */
449: if( ( *name == '%' && usesreg( p, name ) ) ||
450: rausesoff( p, name, len ) ) {
451: /* see if it's a destination */
452: if( iop==2 && ( length(name) == length(p) )
453: && ismove( pn, &srcsize, &dstsize ))
454: return( NULL );
455: if( iop==3 && ( length(name) == length(p) )) {
456: switch ( pn->op ) {
457: case ANDB3: case ANDH3: case ANDW3:
458: case ORB3: case ORH3: case ORW3:
459: case XORB3: case XORH3: case XORW3:
460: case LLSW3: case LRSW3:
461: case ADDB3: case ADDH3: case ADDW3:
462: case SUBB3: case SUBH3: case SUBW3:
463: case MULW3: case UMULW3:
464: case DIVW3: case UDIVW3:
465: case MODW3: case UMODW3:
466: case ALSW3: case ARSW3:
467: return( NULL );
468: }
469: }
470: /* nope, it's live */
471: return( pn );
472: }
473: }
474: }
475: /* examine next block(s) recursively */
476: if( pn->opm == NULL ) return( pn ); /* dst not a simple label */
477:
478: if( ( qn = rald( (NODE *) pn->opm, name, len ) ) != NULL ) return( qn );
479: if( isuncbr( pn ) ) return( NULL );
480: qn = rald( pn->forw, name, len );
481: return( qn );
482: }
483:
484: /* remove branch information from live/dead analysis */
485: void
486: raremld()
487: {
488: register NODE *pn;
489:
490: for( pn = n0.forw; pn != 0; pn = pn->forw ) {
491: if( isbr( pn ) || islabel( pn ) ) pn->opm = NULL;
492: }
493: }
494:
495: /* compute cutoff from cumulative payoff */
496: int
497: racut( numnreg, numauto, iasrlast )
498: int numnreg; /* input number of registers saved */
499: int numauto; /* number of autos */
500: int iasrlast; /* index of last assigned register variable */
501: {
502: int rsave(), rsaveo();
503: int vcumul; /* cumulative payoff for variables */
504: int rcumul; /* cumulative payoff for reg save/restore */
505: int cumul; /* cumulative total payoff */
506: int paycut; /* payoff for cutoff register */
507: int oldsave; /* cycles to save and restore */
508: int oldsaveo; /* cycles to save and restore with func call opt */
509: int ias, iascut;
510: struct assign *pa;
511:
512: vcumul = 0;
513: iascut = iasrlast;
514: paycut = 0;
515: oldsave = rsave( numnreg, numauto );
516:
517: for( ias = 0; ias < MAXREGS; ias ++ ) {
518:
519: /* skip if no assignment */
520: pa = &asreg[ias];
521: if( pa->asvscl == SCLNULL ) continue;
522:
523: /* compute cumulative variable payoff */
524: vcumul += pa->asestim;
525:
526: /* compute cost/payoff from save and restore */
527: rcumul = oldsave - rsave( pa->asrsave, numauto );
528:
529: /* add cumulative payoffs, find max of last reg and all var */
530: cumul = vcumul + rcumul;
531: if( ias >= iasrlast && cumul >= paycut ) {
532: paycut = cumul;
533: iascut = ias;
534: }
535: /*
536: printf( "#ias=%d %s asestim=%d %s vcumul=%d rcumul=%d cumul=%d iascut=%d\n",
537: ias,pa->asrname,pa->asestim,pa->asvname,vcumul,rcumul,cumul,iascut );
538: */
539: }
540: return( iascut );
541: }
542: /* compute estimated save/restore cycles without func call optimization */
543: int
544: rsave( n, numauto )
545: int n; /* number of registers to save/restore, not including frame pointer */
546: int numauto; /* number of autos */
547:
548: {
549: int e;
550:
551: if( numauto ) e = CYCSAVE + n * CYCDELTA + CYCADD ;
552: else e = CYCSAVE + n * CYCDELTA ;
553: return e;
554: }
555:
556: /* modify the operands */
557: void
558: raopn( iascut, newnreg )
559: int iascut; /* index for assignment cutoff */
560: int newnreg; /* new number of registers to be saved/restored */
561: {
562: register char *p, *q, *q2;
563: NODE *pn;
564: register struct assign *pa, *pacut;
565: struct assign *pamin;
566: int iop;
567: static char* numbers[] = { "&0", "&1", "&2", "&3", "&4", "&5", "&6" };
568: struct assign *map[MAXREGS];
569: int i;
570:
571: /* suppress changes for registers assigned to themselves */
572: pamin = &asreg[0];
573: pacut = &asreg[iascut];
574: for( pa = pamin; pa <= pacut; pa++ ) {
575: if( strcmp( pa->asvname, pa->asrname ) == 0 )
576: pa->asvscl = SCLNULL;
577: }
578:
579: /* set up mapping for registers */
580: for( i = 0; i < MAXREGS; i++ ) map[i] = NULL;
581: for( pa = pamin; pa <= pacut; pa++ )
582: if( pa->asvscl == REGISTER )
583: map[ *( pa->asvname + 2 ) - '0'] = pa;
584:
585: /* make changes on the rest */
586: for( ALLN( pn ) ) {
587: if( pn->op == FILTER ) continue;
588: for( iop = 1; iop <= MAXOPS; iop++ ) { /* scan operands */
589: if( ( q = pn->ops[iop] ) == NULL ) continue;
590: /* check for address arithmetic */
591: if( ( ( pn->op == MOVAW ) || ( pn->op == PUSHAW ) ) &&
592: ( iop == 1 ) ) continue;
593: /* find operands that use registers */
594: for( p = q; *p != '%' && *p != '\0'; p++ );
595: if( *p == '\0' ) continue;
596: p++;
597: switch( *p ) {
598: case 'r': /* %r0 through %r8 */
599: /* change register, if appropriate */
600: if( ( pa = map[*++p - '0'] ) != NULL ) {
601: if( *q == '%' )
602: pn->ops[iop] = pa->asrname;
603: else {
604: for( q2=q; *q2!='\0'; q2++ );
605: q2 = getspace( q2 - q + 1 );
606: pn->ops[iop] = q2;
607: p = q2 + ( p - q );
608: while((*q2++ = *q++) != '\0');
609: *p = *(pa->asrname + 2);
610: }
611: }
612: break;
613: case 'f': /* auto */
614: case 'a': /* parameter */
615: /* convert to register, if apropriate */
616: for( pa = pamin; pa <= pacut; pa++ ) {
617: if( ( *p=='f' && pa->asvscl!=AUTO ) ||
618: (*p=='a'&&pa->asvscl!=PARAM ))
619: continue; /* for speed */
620: if( !rausesoff( q, pa->asvname,
621: pa->asvlen ) ) continue;
622: if( *q == '*' )
623: pn->ops[iop] = pa->asrind;
624: else pn->ops[iop] = pa->asrname;
625: break;
626: }
627: break;
628: }
629: }
630:
631: /* change number of registers saved and restored */
632: if( pn->op==SAVE || pn->op==RET ) pn->op1 = numbers[newnreg];
633: }
634: }
635:
636: /* uses offset addressed variable */
637: int
638: rausesoff( oper, var, len )
639: char* oper; /* pointer to operand */
640: char* var; /* pointer to offset addressed variable */
641: int len; /* length of the variable in bytes */
642: {
643: register int io, iv;
644:
645: if( *oper == '*' ) oper++;
646: io = strtol( oper, &oper, 10 );
647: iv = strtol( var, &var, 10 );
648: if( *oper != '(' || *var != '(' || *(oper + 2) != *(var + 2) )
649: return( 0 );
650: if( io < iv || io > ( iv + len - 1 ) ) return( 0 );
651: return( 1 );
652: }
653:
654: /* insert moves for parameters */
655: void
656: raparam( iascut )
657: register int iascut; /* index for assignment cutoff */
658: {
659: register NODE *pn;
660: register int ias;
661: register struct assign *pa;
662:
663: /* find save instruction */
664: for( pn = n0.forw; pn != 0; pn = pn->forw ) { /* scan nodes */
665: if( pn->op == SAVE ) {
666:
667: /* skip over stack pointer increment for locals */
668: if( *( pn->forw->ops[1] + 2 ) == 'F' ) pn = pn->forw;
669:
670: /* insert move for each parameter assigned to reg */
671: for( ias = 0; ias <= iascut; ias++ ) {
672: pa = &asreg[ias];
673: if( pa->asvscl != PARAM ) continue;
674: switch( atoi( pa->asvname ) % 4 ) {
675: case 0:
676: addi( MOVW, "movw", pa->asvname,
677: pa->asrname );
678: break;
679: case 1:
680: case 3:
681: addi( MOVB, "movb", pa->asvname,
682: pa->asrname );
683: break;
684: case 2:
685: addi( MOVH, "movh", pa->asvname,
686: pa->asrname );
687: break;
688: }
689: }
690: break;
691: }
692: }
693: }
694:
695: /* modify def statements */
696: void
697: radef( iascut )
698: int iascut; /* index for assignment cutoff */
699: {
700: register NODE *pn;
701: int ias;
702: register struct assign *pa;
703: register int scl;
704: int val, vval, dscl;
705: register char *p, *q;
706: char *pv, *ps, *s;
707:
708: for( pn = n0.forw; pn != 0; pn = pn->forw ) { /* scan nodes */
709: if( pn->op != FILTER ) continue;
710: p = pn->opcode;
711: if( ! ( p = strchr( p, '.' ) ) || *++p != 'd' ) continue;
712: if( ! ( p = strchr( p, '.' ) ) || *++p != 'v' ) continue;
713: val = atoi( pv = p += 3 );
714: if( ! ( p = strchr( p, '.' ) ) || *++p != 's' ) continue;
715: scl = atoi( ps = p += 3 );
716: switch( scl ) {
717: case C_AUTO: dscl = AUTO; break;
718: case C_ARG: dscl = PARAM; break;
719: case C_REG:
720: case C_REGPARM: dscl = REGISTER; break;
721: default: continue;
722: }
723: for( ias = 0; ias <= iascut; ias++ ) {
724: pa = &asreg[ias];
725: if( dscl != pa->asvscl ) continue;
726: vval = ( scl == C_AUTO || scl == C_ARG ) ?
727: atoi( pa->asvname ) :
728: *( pa->asvname + 2 ) - '0' ;
729: if( val != vval ) continue;
730: q = s = getspace( length( p = pn->opcode ) + 5 );
731: while( p != pv ) *q++ = *p++; /* thru .val */
732: *q++ = *p++; /* tab */
733: *q++ = *( pa->asrname + 2 ); /* reg no */
734: while( *++p != ';' );
735: while( p != ps ) *q++ = *p++; /* thru .scl */
736: *q++ = *p++; /* tab */
737: q += sprintf( q, "%d", /* scl value */
738: ( scl == C_AUTO || scl == C_REG ) ?
739: C_REG : C_REGPARM );
740: while( *++p != ';' );
741: while( *q++ = *p++ ); /* the rest */
742: pn->opcode = s;
743: }
744: }
745: }
746:
747: /* eliminate auto area if no more autos */
748: int
749: raautos( numauto )
750: int numauto; /* number of bytes of automatic variables */
751: {
752: register NODE *pn, *qn;
753: register int iop;
754: register char *p;
755:
756: for( pn = n0.forw; pn != 0; pn = pn->forw ) { /* scan nodes */
757: if( pn->op == FILTER ) continue;
758: if( pn->op == SAVE ) qn = pn->forw;
759: for( iop = 1; iop < MAXOPS + 1; iop++ ) { /* scan operands */
760: p = pn->ops[iop];
761: if( p == NULL ) continue;
762: /* look for uses of frame pointer */
763: if( usesreg( p, "%fp" ) ) return( numauto );
764: }
765: }
766: /* remove allocation of auto area */
767: if( *( qn->op1 + 2 ) == 'F' ) {
768: DELNODE( qn );
769: numauto = 0;
770: }
771: return( numauto );
772: }
773: #endif /* IMPREGAL */
774:
775:
776: #ifdef IMPIL
777: /* in-line substitution optimization
778: **
779: ** F.B. Wolverton 8/12/83
780: **
781: */
782:
783: #define MAXINSTR 22 /* = 20 * (cost/benefit) + 2 */
784:
785: struct procnode {
786: struct procnode *pnforw; /* forward pointer for list of procs */
787: struct procnode *pnback; /* backward pointer for list of procs */
788: char *pnname; /* procedure name */
789: int pncalls; /* num of times procedure is called */
790: int pnni; /* num of instr in procedure */
791: struct node *pnhead; /* proc head pointer */
792: struct node *pntail; /* proc tail pointer */
793: } prochead, proctail;
794: int proccnt; /* number of procs in table */
795: int totalni = 0; /* total number of instructions in file */
796: #define PNODE struct procnode
797: #define ALLPN( prn ) prn = prochead.pnforw; prn != &proctail; prn=prn->pnforw
798: #define ALLPNB( prn ) prn = proctail.pnback; prn != &prochead; prn=prn->pnback
799: #define PNALLN(prn,pn) pn = prn->pnhead->forw; pn != prn->pntail; pn=pn->forw
800: #define PNALLNB(prn,pn) pn = prn->pntail->back; pn != prn->pnhead; pn=pn->back
801: extern char *mktemp();
802: char itmpname[50]; /* name of file for output before in-line subst */
803: int outfd; /* descriptor for output file after in-line subst */
804: FILE *outfp; /* pointer for output file after in-line subst */
805: void iledit(), ilinsert();
806: struct procnode *ilalloc();
807: #define LINELEN 400
808: char linebuf[LINELEN];
809: int intpc = -3; /* persent limit on in-line expansion */
810: char defltpc[] = MAXPC;
811: char *pcdecode();
812: extern int zflag; /* debug flag for in-line expansion */
813: extern boolean swflag;
814:
815: /* initialization for in-line substitution */
816: void
817: ilinit()
818: {
819: /* initialize procedure list */
820: prochead.pnforw = &proctail;
821: prochead.pnback = NULL;
822: proctail.pnforw = NULL;
823: proctail.pnback = &prochead;
824: proccnt = 0;
825:
826: /* default the in-line expansion limit if not set */
827: if( intpc == -3 && *( pcdecode( defltpc )+1 ) != '\0' ) pcdecode( "" );
828:
829: /* redirect stdout to tempfile to hold output before in-line subst */
830: strcpy( itmpname, TMPDIR );
831: strcat( itmpname, "/ccilXXXXXX" );
832: mktemp( itmpname );
833: if( ( outfd = dup( 1 ) ) == -1 )
834: fatal( "can't get file descriptor\n", 0 );
835: outfp = fdopen( outfd, "w" );
836: if( freopen( itmpname, "w", stdout ) == NULL )
837: fatal( "can't open file %s\n", itmpname );
838: }
839: /* routine to decode the limit on percent in-line expansion */
840: char *
841: pcdecode( flags )
842: char *flags; /* pointer to first character of suboption for 'y' */
843: {
844: char *p;
845: switch( *flags ) {
846: case 'u': intpc = -1; break;
847: case 's': intpc = -2; break;
848: case '\n':
849: case '\0':
850: fprintf( stderr, "Optimizer: in-line option missing, " );
851: fprintf( stderr, "expansion suppressed\n");
852: flags--;
853: intpc = -2;
854: break;
855: default:
856: intpc = ( int ) strtol( p = flags, &flags, 10 );
857: flags--;
858: if( flags >= p ) break; /* break if found an integer */
859: fprintf( stderr, "Optimizer: invalid in-line option " );
860: fprintf( stderr, "starting with '%c', ", *p );
861: fprintf( stderr, "expansion suppressed\n" );
862: intpc = -2;
863: }
864: return( flags ); /* returns pointer to last character of suboption */
865: }
866: /* routine to mark calls with bytes pushed on stack at time of call */
867:
868: /* The purpose of this routine is to permit nested calls to be expanded
869: ** in-line. This routine routine does static analysis of the stack
870: ** size and should, therefore, precede the branch optimization. */
871:
872: void
873: ilmark()
874:
875: {
876: register int npush = 0; /* number of bytes of
877: arguments pushed or moved onto the stack */
878: register NODE *pn; /* pointer to instruction node being
879: processed */
880:
881: /* check whether in-line expansion is being suppressed */
882: if( intpc == -2 ) return;
883:
884: /* mark calls */
885: for( ALLN( pn ) ) {
886: if( pn->op == FILTER ) continue;
887: switch(pn->op) {
888: case PUSHZB:
889: case PUSHZH:
890: case PUSHAW:
891: case PUSHBB:
892: case PUSHBH:
893: case PUSHW:
894: case PUSHD:
895: npush += 4;
896: break;
897: case ADDW2:
898: if( strncmp( pn->op2, "%sp", 3 ) != 0 ) break;
899: if( strncmp( pn->op1, "&.F", 3 ) == 0 ) break;
900: npush += atoi( pn->op1 + 1 );
901: break;
902: case SUBW2:
903: if( strncmp( pn->op2, "%sp", 3 ) != 0 ) break;
904: npush -= atoi( pn->op1 + 1 );
905: break;
906: case CALL:
907: npush -= 4 * atoi( pn->op1 + 1 );
908: pn->opm = (char * ) npush;
909: break;
910: }
911: }
912: }
913:
914: /* gather statistics for in-line substitution */
915: void
916: ilstat( numnreg, numauto )
917: int numnreg; /* number of registers to save and restore */
918: int numauto; /* number of words of autos */
919: {
920: register NODE *pn, *p;
921: PNODE *prn, *pp;
922: int nn, ni, iop, nc, lastop;
923: char *ncp;
924:
925: /* check whether in-line expansion is being suppressed */
926: if( intpc == -2 ) return;
927:
928: /* count CALL's and total number of instructions */
929: lastop = 0;
930: for( ALLN( pn ) ) {
931: if( pn->op == CALL ) {
932: if( ( prn = ilalloc( pn->op2 ) ) == NULL ) return;
933: prn->pncalls++;
934: }
935: if( !islabel( pn ) && pn->op != MISC &&
936: ( pn->op != RET ||
937: ( lastop != RET && lastop != JMP ) ) ) {
938: totalni++;
939: lastop = pn->op;
940: /*
941: printf( "%d %s\n", totalni, pn->ops[0] );
942: */
943: }
944: }
945:
946: /* allocate a node for this proc if one does not exist */
947: for( ALLN( pn ) ) {
948: if( islabel( pn ) ) {
949: if( ( prn = ilalloc( pn->opcode ) ) == NULL ) return;
950: break;
951: }
952: }
953: if( pn == 0 ) return;
954:
955: /* check conditions for being substituted in line */
956: /* check for locals or saved registers */
957: if( numnreg != 0 || numauto != 0 ) return;
958: /* check procedure size and compute total length of strings */
959: nn = ni = nc = lastop = 0;
960: for( ALLN( pn ) ) {
961: register char *cp;
962: nn++;
963: for( iop = 0; iop <= MAXOPS; iop++ ) {
964: if( (cp = pn->ops[iop] ) != NULL ) nc += length( cp );
965: }
966: if( !islabel( pn ) && pn->op != MISC &&
967: ( pn->op != RET ||
968: ( lastop != RET && lastop != JMP ) ) ) {
969: if( ++ni > MAXINSTR ) return;
970: lastop = pn->op;
971: /*
972: printf( "%d %s\n", ni, pn->ops[0] );
973: */
974: }
975: }
976: /* check for label expressions */
977: for( ALLN( pn ) ) {
978: if( !islabel( pn ) ) continue;
979: for( ALLN( p ) ) {
980: register int i;
981: for( i = 0; i <= MAXOPS; i++ ) {
982: register char *cp;
983: cp = p->ops[i];
984: if( cp == NULL ) continue;
985: if( *cp == *( pn->opcode ) &&/*speed*/
986: strcmp(cp, pn->opcode ) == 0) continue;
987: while( *cp != '\0' ) {
988: cp++;
989: if( *cp == *( pn->opcode )&&/* speed */
990: strcmp( cp, pn->opcode ) == 0 )
991: return;
992: }
993: }
994: }
995: }
996:
997: /* check for switch tables */
998: if( swflag ) { swflag = false; return; }
999:
1000: /* save the code */
1001: prn->pnni = ni;
1002: if( ( p = (NODE *)malloc( ( nn + 2 ) * sizeof( NODE ) + nc ) ) == NULL )
1003: return;
1004: ncp = (char *) p + ( nn + 2 ) * sizeof( NODE );
1005: prn->pnhead = p;
1006: p->forw = p + 1;
1007: p->back = NULL;
1008: for( ALLN( pn ) ) {
1009: register int i;
1010: p++;
1011: p->forw = p + 1;
1012: p->back = p - 1;
1013: for( i = 0; i <= MAXOPS; i++ ) {
1014: if( ( p->ops[i] = pn->ops[i] ) == NULL ) continue;
1015: strcpy( ncp, pn->ops[i] );
1016: p->ops[i] = ncp;
1017: ncp += length( ncp );
1018: }
1019: p->op = pn->op;
1020: }
1021: p++;
1022: p->forw = NULL;
1023: p->back = p - 1;
1024: prn->pntail = p;
1025:
1026: /* reposition in list by increasing size */
1027: /* remove from list */
1028: prn->pnforw->pnback = prn->pnback;
1029: prn->pnback->pnforw = prn->pnforw;
1030: /* locate proper position */
1031: for( ALLPNB( pp ) ) {
1032: if( prn->pnni >= pp->pnni ) break;
1033: }
1034: /* reinsert it */
1035: prn->pnforw = pp->pnforw;
1036: prn->pnback = pp;
1037: prn->pnforw->pnback = prn;
1038: prn->pnback->pnforw = prn;
1039: }
1040:
1041: /* perform the in-line substitution for whole file */
1042: void
1043: ilfile()
1044: {
1045: register struct procnode *prn;
1046: int fpc, delta;
1047: register char *linptr;
1048:
1049: /* eliminate nodes for progs not in the file or not called */
1050: for( ALLPN( prn ) ) {
1051: if( prn->pnni == 0 || prn->pncalls ==0 ) {
1052: prn->pnforw->pnback = prn->pnback;
1053: prn->pnback->pnforw = prn->pnforw;
1054: }
1055: }
1056:
1057: /* apply percent limit unless no limit */
1058: if( intpc != -1 ) {
1059: /* apply percent text increase constraint */
1060: fpc = 100 * intpc;
1061: for( ALLPN( prn ) ) {
1062: delta = 100 * ( prn->pnni - 2 ) * 100 / totalni;
1063: fpc -= prn->pncalls * delta;
1064: if( fpc < 0 ) {
1065: while( fpc < 0 && prn->pncalls > 0 ) {
1066: fpc += delta;
1067: prn->pncalls--;
1068: }
1069: break;
1070: }
1071: }
1072: if( prn != &proctail ) {
1073: if( ( prn->pncalls ) == 0 ) prn = prn -> pnback;
1074: prn->pnforw = &proctail;
1075: prn->pnforw->pnback = prn;
1076: }
1077: }
1078:
1079: /* analytic printout */
1080: if( zflag ) {
1081: int size, sumsize;
1082: sumsize = 0;
1083: if( zflag ) fprintf(stderr, "in-line expansion limit = %d\n",
1084: intpc );
1085: for( ALLPN( prn ) ) {
1086: size = prn->pncalls *
1087: ( prn->pnni -2 ) * 100 / totalni;
1088: sumsize += size;
1089: fprintf( stderr,
1090: "%s calls=%d inst=%d sz=%d%% t_sz=%d%% \n",
1091: prn->pnname,prn->pncalls,prn->pnni,size,
1092: sumsize );
1093: }
1094: }
1095:
1096: /* edit routines before inserting */
1097: iledit();
1098:
1099: /* read temp file and write output with inserted procedures */
1100: fclose( stdout );
1101: if( freopen( itmpname, "r", stdin ) == NULL )
1102: fatal( "can't open file %s\n", itmpname );
1103: while( ( linptr = fgets( linebuf, LINELEN, stdin ) ) != NULL ){
1104: register int numauto, nargs;
1105: register char *cp;
1106: char *linp;
1107:
1108: if( *linptr == '!' ) continue;
1109: if( *linptr == '*' ) {
1110: /* insert .il flag to indicate in-line expansion */
1111: if( ( linptr = fgets( linebuf, LINELEN, stdin ) )
1112: == NULL ) break;
1113: for( cp = linebuf; *cp != '\n'; cp++ );
1114: *cp = '\0';
1115: for( ALLPN( prn ) ) {
1116: if( strcmp( linebuf, prn->pnname ) == 0 ) {
1117: linptr = fgets( linebuf, LINELEN,
1118: stdin );
1119: for(cp=linebuf; *cp != '\n'; cp++)
1120: if(*cp == ';') linptr = cp;
1121: *linptr = '\0';
1122: fprintf( outfp, "%s;\t.il;\t.endef\n",
1123: linebuf );
1124: break;
1125: }
1126: }
1127: continue;
1128: }
1129: /* default */
1130: if( *linptr != '@' ) {
1131: fprintf( outfp, "%s", linptr );
1132: continue;
1133: }
1134: /* expand the call */
1135: linp = linptr;
1136: numauto = (int) strtol( ++linp, &linp, 10 );
1137: nargs = (int) strtol( ++linp, &linp, 10 );
1138: linptr = linp;
1139: cp = ++linptr;
1140: while( *cp != '\n' ) cp++;
1141: *cp = '\0';
1142: for( ALLPNB( prn ) ) {
1143: if( strcmp( linptr, prn->pnname ) == 0 ) {
1144: if( prn->pncalls <= 0 ) break;
1145: ilinsert( numauto, nargs, prn );
1146: prn->pncalls--;
1147: fgets( linebuf, LINELEN, stdin );
1148: break;
1149: }
1150: }
1151: }
1152: (void) fclose( stdin );
1153: unlink( itmpname );
1154: }
1155:
1156:
1157: /* edit routines before substitution */
1158: void
1159: iledit()
1160: {
1161: register NODE *pn;
1162: register PNODE *prn;
1163:
1164: for( ALLPN( prn ) ) {
1165: /* replace entry label with new label */
1166: for( PNALLN( prn, pn ) ) {
1167: if( islabel( pn ) ) {
1168: prn->pnhead->forw = pn;
1169: pn->back = prn->pnhead;
1170: pn->opcode = "EL";
1171: break;
1172: }
1173: }
1174: /* replace last return with lab or follow last jump with lab */
1175: for( PNALLNB( prn, pn ) ) {
1176: if( pn->op == RET ) {
1177: pn->op = LABEL;
1178: pn->opcode = "RL";
1179: prn->pntail->back = pn;
1180: pn->forw = prn->pntail;
1181: /* remove duplicate return, if any */
1182: while( islabel( pn ) ) pn = pn ->back;
1183: if( pn->op == RET ) DELNODE( pn );
1184: break;
1185: }
1186: if( pn->op == JMP ) {
1187: addi( LABEL, "RL", 0, 0 );
1188: prn->pntail->back = pn;
1189: pn->forw = prn->pntail;
1190: break;
1191: }
1192: }
1193: /* replace other returns with jump to new label */
1194: for( PNALLN( prn, pn ) ) {
1195: if( pn->op == RET ) {
1196: pn->op = JMP;
1197: pn->opcode = "jmp";
1198: pn->op1 = "RL";
1199: }
1200: }
1201: }
1202: }
1203:
1204:
1205: /* insert a procedure */
1206: void
1207: ilinsert( numauto, nargs, prn )
1208: int numauto; /* numbers of words of autos in calling procedure */
1209: int nargs; /* number of arguments procedure is called with */
1210: PNODE *prn; /* procedure to be inserted */
1211: {
1212: register NODE *pn, *p;
1213: static int ilabel = 0;
1214: register int i;
1215: register char *cp, *cpn;
1216: char *lab;
1217:
1218: /* rewrite labels */
1219: for( PNALLN( prn, pn ) ) {
1220: if( !islabel( pn ) ) continue;
1221: cpn = pn->opcode;
1222: ilabel++;
1223: lab = getspace( 9 );
1224: sprintf( lab, ".I%d\0", ilabel );
1225: for( PNALLN( prn, p ) ) {
1226: for( i = 0; i <= MAXOPS; i++ ) {
1227: cp = p->ops[i];
1228: if( cp == NULL ) continue;
1229: if( *cp == *cpn &&
1230: strcmp( cp, cpn ) == 0 )
1231: p->ops[i] = lab;
1232: }
1233: }
1234: }
1235:
1236: /* write out instructions, rewriting args and omitting save */
1237: for( PNALLN( prn, pn ) ) {
1238: switch( pn->op ) {
1239: case SAVE: continue;
1240: case LABEL:
1241: fprintf( outfp, "%s:\n", pn->opcode );
1242: break;
1243: case HLABEL:
1244: fprintf( outfp, "%s:\n", pn->opcode );
1245: break;
1246: case MISC:
1247: fprintf( outfp, " %s\n", pn->opcode );
1248: break;
1249: case CALL:
1250: pn->opm = NULL;
1251: /* fall through */
1252: default:
1253: fprintf( outfp, " %s ", pn->opcode );
1254: for( i = 1; i < MAXOPS + 1; i++ ) {
1255: if( (cp=pn->ops[i]) == NULL ) continue;
1256: if( i > 1 ) fprintf( outfp, "," );
1257: if( usesreg( cp, "%ap" ) ) {
1258: if( *cp == '*') {
1259: fprintf( outfp, "*" );
1260: cp++;
1261: }
1262: fprintf( outfp, "%d(%%fp)",
1263: atoi( cp ) + numauto );
1264: }
1265: else fprintf( outfp, "%s", cp );
1266: }
1267: fprintf( outfp, "\n" );
1268: break;
1269: }
1270: }
1271:
1272: /* reset stack pointer if necessary */
1273: if( nargs != 0 )
1274: fprintf( outfp, " subw2 &%d,%%sp\n", 4 * nargs );
1275: }
1276:
1277: /* allocate procedure nodes */
1278: struct procnode *
1279: ilalloc( name )
1280: char *name; /* procedure name */
1281: {
1282: register PNODE *prn;
1283:
1284: /* check whether node already exists */
1285: for( ALLPN( prn ) ) {
1286: if( strcmp( name, prn->pnname ) == 0 )
1287: return( prn );
1288: }
1289:
1290: /* allocate node */
1291: if( ( prn = ( PNODE * )
1292: malloc( sizeof( PNODE ) + length( name ) ) ) == NULL )
1293: return( prn );
1294: prn->pnforw = prochead.pnforw;
1295: prn->pnback = &prochead;
1296: prn->pnforw->pnback = prn;
1297: prn->pnback->pnforw = prn;
1298: prn->pnname = (char *) prn + sizeof( PNODE );
1299: strcpy( prn->pnname, name );
1300: prn->pncalls = 0;
1301: prn->pnni = 0;
1302: prn->pnhead = NULL;
1303: return( prn );
1304: }
1305: #endif /* IMPIL */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.