4.3BSD - /usr/src/lib/mip/allo.c

   1: #ifndef lint
   2: static char *sccsid ="@(#)allo.c	4.8 (Berkeley) 1/8/86";
   3: #endif lint
   4: 
   5: # include "pass2.h"
   6: 
   7: NODE resc[3];
   8: 
   9: int busy[REGSZ];
  10: 
  11: int maxa, mina, maxb, minb;
  12: 
  13: # ifndef ALLO0
  14: allo0(){ /* free everything */
  15: 
  16:     register i;
  17: 
  18:     maxa = maxb = -1;
  19:     mina = minb = 0;
  20: 
  21:     REGLOOP(i){
  22:         busy[i] = 0;
  23:         if( rstatus[i] & STAREG ){
  24:             if( maxa<0 ) mina = i;
  25:             maxa = i;
  26:             }
  27:         if( rstatus[i] & STBREG ){
  28:             if( maxb<0 ) minb = i;
  29:             maxb = i;
  30:             }
  31:         }
  32:     }
  33: # endif
  34: 
  35: # ifndef ALLO
  36: allo( p, q ) NODE *p; struct optab *q; {
  37: 
  38:     register n, i, j;
  39:     int either;
  40: 
  41:     n = q->needs;
  42:     either = ( EITHER & n );
  43:     i = 0;
  44: 
  45:     while( n & NACOUNT ){
  46:         resc[i].in.op = REG;
  47:         resc[i].tn.rval = freereg( p, n&NAMASK );
  48:         resc[i].tn.lval = 0;
  49: #ifdef FLEXNAMES
  50:         resc[i].in.name = "";
  51: #else
  52:         resc[i].in.name[0] = '\0';
  53: #endif
  54:         n -= NAREG;
  55:         ++i;
  56:         }
  57: 
  58:     if (either) { /* all or nothing at all */
  59:         for( j = 0; j < i; j++ )
  60:             if( resc[j].tn.rval < 0 ) { /* nothing */
  61:                 i = 0;
  62:                 break;
  63:                 }
  64:         if( i != 0 ) goto ok; /* all */
  65:         }
  66: 
  67:     while( n & NBCOUNT ){
  68:         resc[i].in.op = REG;
  69:         resc[i].tn.rval = freereg( p, n&NBMASK );
  70:         resc[i].tn.lval = 0;
  71: #ifdef FLEXNAMES
  72:         resc[i].in.name = "";
  73: #else
  74:         resc[i].in.name[0] = '\0';
  75: #endif
  76:         n -= NBREG;
  77:         ++i;
  78:         }
  79:     if (either) { /* all or nothing at all */
  80:         for( j = 0; j < i; j++ )
  81:             if( resc[j].tn.rval < 0 ) { /* nothing */
  82:                 i = 0;
  83:                 break;
  84:                 }
  85:         if( i != 0 ) goto ok; /* all */
  86:         }
  87: 
  88:     if( n & NTMASK ){
  89:         resc[i].in.op = OREG;
  90:         resc[i].tn.rval = TMPREG;
  91:         if( p->in.op == STCALL || p->in.op == STARG || p->in.op == UNARY STCALL || p->in.op == STASG ){
  92:             resc[i].tn.lval = freetemp( (SZCHAR*p->stn.stsize + (SZINT-1))/SZINT );
  93:             }
  94:         else {
  95:             resc[i].tn.lval = freetemp( (n&NTMASK)/NTEMP );
  96:             }
  97: #ifdef FLEXNAMES
  98:         resc[i].in.name = "";
  99: #else
 100:         resc[i].in.name[0] = '\0';
 101: #endif
 102: 
 103:         resc[i].tn.lval = BITOOR(resc[i].tn.lval);
 104:         ++i;
 105:         }
 106: 
 107:     /* turn off "temporarily busy" bit */
 108: 
 109:     ok:
 110:     REGLOOP(j){
 111:         busy[j] &= ~TBUSY;
 112:         }
 113: 
 114:     for( j=0; j<i; ++j ) if( resc[j].tn.rval < 0 ) return(0);
 115:     return(1);
 116: 
 117:     }
 118: # endif
 119: 
 120: extern unsigned int offsz;
 121: freetemp( k ){ /* allocate k integers worth of temp space */
 122:     /* we also make the convention that, if the number of words is more than 1,
 123: 	/* it must be aligned for storing doubles... */
 124: 
 125: # ifndef BACKTEMP
 126:     int t;
 127: 
 128:     if( k>1 ){
 129:         SETOFF( tmpoff, ALDOUBLE );
 130:         }
 131: 
 132:     t = tmpoff;
 133:     tmpoff += k*SZINT;
 134:     if( tmpoff > maxoff ) maxoff = tmpoff;
 135:     if( tmpoff >= offsz )
 136:         cerror( "stack overflow" );
 137:     if( tmpoff-baseoff > maxtemp ) maxtemp = tmpoff-baseoff;
 138:     return(t);
 139: 
 140: # else
 141:     tmpoff += k*SZINT;
 142:     if( k>1 ) {
 143:         SETOFF( tmpoff, ALDOUBLE );
 144:         }
 145:     if( tmpoff > maxoff ) maxoff = tmpoff;
 146:     if( tmpoff >= offsz )
 147:         cerror( "stack overflow" );
 148:     if( tmpoff-baseoff > maxtemp ) maxtemp = tmpoff-baseoff;
 149:     return( -tmpoff );
 150: # endif
 151:     }
 152: 
 153: freereg( p, n ) NODE *p; {
 154:     /* allocate a register of type n */
 155:     /* p gives the type, if floating */
 156: 
 157:     register j;
 158: 
 159:     /* not general; means that only one register (the result) OK for call */
 160:     if( callop(p->in.op) ){
 161:         j = callreg(p);
 162:         if( usable( p, n, j ) ) return( j );
 163:         /* have allocated callreg first */
 164:         }
 165:     j = p->in.rall & ~MUSTDO;
 166:     if( j!=NOPREF && usable(p,n,j) ){ /* needed and not allocated */
 167:         return( j );
 168:         }
 169:     if( n&NAMASK ){
 170:         for( j=mina; j<=maxa; ++j ) if( rstatus[j]&STAREG ){
 171:             if( usable(p,n,j) ){
 172:                 return( j );
 173:                 }
 174:             }
 175:         }
 176:     else if( n &NBMASK ){
 177:         for( j=minb; j<=maxb; ++j ) if( rstatus[j]&STBREG ){
 178:             if( usable(p,n,j) ){
 179:                 return(j);
 180:                 }
 181:             }
 182:         }
 183: 
 184:     return( -1 );
 185:     }
 186: 
 187: # ifndef USABLE
 188: usable( p, n, r ) NODE *p; {
 189:     /* decide if register r is usable in tree p to satisfy need n */
 190: 
 191:     /* checks, for the moment */
 192:     if( !istreg(r) ) cerror( "usable asked about nontemp register" );
 193: 
 194:     if( busy[r] > 1 ) return(0);
 195:     if( isbreg(r) ){
 196:         if( n&NAMASK ) return(0);
 197:         }
 198:     else {
 199:         if( n & NBMASK ) return(0);
 200:         }
 201:     /*
 202: 	 * Some special cases that require register pairs...
 203: 	 * Have to check for ==, <=, etc. because the result is type int
 204: 	 * but need a register pair temp if either side is wide.
 205: 	 * For +=, *= etc. where lhs is narrow and rhs is wide, the temp
 206: 	 * register must be wide.
 207: 	 */
 208:     if( (n&NAMASK) &&
 209:         (szty(p->in.type) == 2 ||
 210:          (logop(p->in.op) && (szty(p->in.left->in.type) == 2 ||
 211:           szty(p->in.right->in.type) == 2)) ||
 212:          (asgop(p->in.op) && szty(p->in.right->in.type) == 2 &&
 213:           szty(p->in.left->in.type) == 1))
 214:     ){
 215: #ifndef NOEVENODD
 216:         if( r&01 ) return(0);
 217: #endif
 218:         if( !istreg(r+1) ) return( 0 );
 219:         if( busy[r+1] > 1 ) return( 0 );
 220:         if( busy[r] == 0 && busy[r+1] == 0  ||
 221:             busy[r+1] == 0 && shareit( p, r, n ) ||
 222:             busy[r] == 0 && shareit( p, r+1, n ) ){
 223:             busy[r] |= TBUSY;
 224:             busy[r+1] |= TBUSY;
 225:             return(1);
 226:             }
 227:         else return(0);
 228:         }
 229:     if( busy[r] == 0 ) {
 230:         busy[r] |= TBUSY;
 231:         return(1);
 232:         }
 233: 
 234:     /* busy[r] is 1: is there chance for sharing */
 235:     return( shareit( p, r, n ) );
 236: 
 237:     }
 238: # endif
 239: 
 240: shareit( p, r, n ) NODE *p; {
 241:     /* can we make register r available by sharing from p
 242: 	   given that the need is n */
 243:     if( (n&(NASL|NBSL)) && ushare( p, 'L', r ) ) return(1);
 244:     if( (n&(NASR|NBSR)) && ushare( p, 'R', r ) ) return(1);
 245:     return(0);
 246:     }
 247: 
 248: ushare( p, f, r ) NODE *p; {
 249:     /* can we find a register r to share on the left or right
 250: 		(as f=='L' or 'R', respectively) of p */
 251:     p = getlr( p, f );
 252:     if( p->in.op == UNARY MUL ) p = p->in.left;
 253:     if( p->in.op == OREG ){
 254:         if( R2TEST(p->tn.rval) ){
 255:             return( r==R2UPK1(p->tn.rval) || r==R2UPK2(p->tn.rval) );
 256:             }
 257:         else return( r == p->tn.rval );
 258:         }
 259:     if( p->in.op == REG ){
 260:         return( r == p->tn.rval || ( szty(p->in.type) == 2 && r==p->tn.rval+1 ) );
 261:         }
 262:     return(0);
 263:     }
 264: 
 265: recl2( p ) register NODE *p; {
 266:     register r = p->tn.rval;
 267: #ifndef OLD
 268:     int op = p->in.op;
 269:     if (op == REG && r >= REGSZ)
 270:         op = OREG;
 271:     if( op == REG ) rfree( r, p->in.type );
 272:     else if( op == OREG ) {
 273:         if( R2TEST( r ) ) {
 274:             if( R2UPK1( r ) != 100 ) rfree( R2UPK1( r ), PTR+INT );
 275:             rfree( R2UPK2( r ), INT );
 276:             }
 277:         else {
 278:             rfree( r, PTR+INT );
 279:             }
 280:         }
 281: #else
 282:     if( p->in.op == REG ) rfree( r, p->in.type );
 283:     else if( p->in.op == OREG ) {
 284:         if( R2TEST( r ) ) {
 285:             if( R2UPK1( r ) != 100 ) rfree( R2UPK1( r ), PTR+INT );
 286:             rfree( R2UPK2( r ), INT );
 287:             }
 288:         else {
 289:             rfree( r, PTR+INT );
 290:             }
 291:         }
 292: #endif
 293:     }
 294: 
 295: int rdebug = 0;
 296: 
 297: # ifndef RFREE
 298: rfree( r, t ) TWORD t; {
 299:     /* mark register r free, if it is legal to do so */
 300:     /* t is the type */
 301: 
 302: # ifndef BUG3
 303:     if( rdebug ){
 304:         printf( "rfree( %s ), size %d\n", rnames[r], szty(t) );
 305:         }
 306: # endif
 307: 
 308:     if( istreg(r) ){
 309:         if( --busy[r] < 0 ) cerror( "register overfreed");
 310:         if( szty(t) == 2 ){
 311: #ifdef NOEVENODD
 312:             if( istreg(r) ^ istreg(r+1) ) cerror( "illegal free" );
 313: #else
 314:             if( (r&01) || (istreg(r)^istreg(r+1)) ) cerror( "illegal free" );
 315: #endif
 316:             if( --busy[r+1] < 0 ) cerror( "register overfreed" );
 317:             }
 318:         }
 319:     }
 320: # endif
 321: 
 322: # ifndef RBUSY
 323: rbusy(r,t) TWORD t; {
 324:     /* mark register r busy */
 325:     /* t is the type */
 326: 
 327: # ifndef BUG3
 328:     if( rdebug ){
 329:         printf( "rbusy( %s ), size %d\n", rnames[r], szty(t) );
 330:         }
 331: # endif
 332: 
 333:     if( istreg(r) ) ++busy[r];
 334:     if( szty(t) == 2 ){
 335:         if( istreg(r+1) ) ++busy[r+1];
 336: #ifdef NOEVENODD
 337:         if( istreg(r) ^ istreg(r+1) ) cerror( "illegal register pair freed" );
 338: #else
 339:         if( (r&01) || (istreg(r)^istreg(r+1)) ) cerror( "illegal register pair freed" );
 340: #endif
 341:         }
 342:     }
 343: # endif
 344: 
 345: # ifndef BUG3
 346: rwprint( rw ){ /* print rewriting rule */
 347:     register i, flag;
 348:     static char * rwnames[] = {
 349: 
 350:         "RLEFT",
 351:         "RRIGHT",
 352:         "RESC1",
 353:         "RESC2",
 354:         "RESC3",
 355:         0,
 356:         };
 357: 
 358:     if( rw == RNULL ){
 359:         printf( "RNULL" );
 360:         return;
 361:         }
 362: 
 363:     if( rw == RNOP ){
 364:         printf( "RNOP" );
 365:         return;
 366:         }
 367: 
 368:     flag = 0;
 369:     for( i=0; rwnames[i]; ++i ){
 370:         if( rw & (1<<i) ){
 371:             if( flag ) printf( "|" );
 372:             ++flag;
 373:             printf( rwnames[i] );
 374:             }
 375:         }
 376:     }
 377: # endif
 378: 
 379: reclaim( p, rw, cookie ) NODE *p; {
 380:     register NODE **qq;
 381:     register NODE *q;
 382:     register i;
 383:     NODE *recres[5];
 384:     struct respref *r;
 385: 
 386:     /* get back stuff */
 387: 
 388: # ifndef BUG3
 389:     if( rdebug ){
 390:         printf( "reclaim( %o, ", p );
 391:         rwprint( rw );
 392:         printf( ", " );
 393:         prcook( cookie );
 394:         printf( " )\n" );
 395:         }
 396: # endif
 397: 
 398:     if( rw == RNOP || ( p->in.op==FREE && rw==RNULL ) ) return;  /* do nothing */
 399: 
 400:     walkf( p, recl2 );
 401: 
 402:     if( callop(p->in.op) ){
 403:         /* check that all scratch regs are free */
 404:         callchk(p);  /* ordinarily, this is the same as allchk() */
 405:         }
 406: 
 407:     if( rw == RNULL || (cookie&FOREFF) ){ /* totally clobber, leaving nothing */
 408:         tfree(p);
 409:         return;
 410:         }
 411: 
 412:     /* handle condition codes specially */
 413: 
 414:     if( (cookie & FORCC) && (rw&RESCC)) {
 415:         /* result is CC register */
 416:         tfree(p);
 417:         p->in.op = CCODES;
 418:         p->tn.lval = 0;
 419:         p->tn.rval = 0;
 420:         return;
 421:         }
 422: 
 423:     /* locate results */
 424: 
 425:     qq = recres;
 426: 
 427:     if( rw&RLEFT) *qq++ = getlr( p, 'L' );;
 428:     if( rw&RRIGHT ) *qq++ = getlr( p, 'R' );
 429:     if( rw&RESC1 ) *qq++ = &resc[0];
 430:     if( rw&RESC2 ) *qq++ = &resc[1];
 431:     if( rw&RESC3 ) *qq++ = &resc[2];
 432: 
 433:     if( qq == recres ){
 434:         cerror( "illegal reclaim");
 435:         }
 436: 
 437:     *qq = NIL;
 438: 
 439:     /* now, select the best result, based on the cookie */
 440: 
 441:     for( r=respref; r->cform; ++r ){
 442:         if( cookie & r->cform ){
 443:             for( qq=recres; (q= *qq) != NIL; ++qq ){
 444:                 if( tshape( q, r->mform ) ) goto gotit;
 445:                 }
 446:             }
 447:         }
 448: 
 449:     /* we can't do it; die */
 450:     cerror( "cannot reclaim");
 451: 
 452:     gotit:
 453: 
 454:     if( p->in.op == STARG ) p = p->in.left;  /* STARGs are still STARGS */
 455: 
 456:     q->in.type = p->in.type;  /* to make multi-register allocations work */
 457:         /* maybe there is a better way! */
 458:     q = tcopy(q);
 459: 
 460:     tfree(p);
 461: 
 462:     p->in.op = q->in.op;
 463:     p->tn.lval = q->tn.lval;
 464:     p->tn.rval = q->tn.rval;
 465: #ifdef FLEXNAMES
 466:     p->in.name = q->in.name;
 467: #ifdef ONEPASS
 468:     p->in.stalign = q->in.stalign;
 469: #endif
 470: #else
 471:     for( i=0; i<NCHNAM; ++i )
 472:         p->in.name[i] = q->in.name[i];
 473: #endif
 474: 
 475:     q->in.op = FREE;
 476: 
 477:     /* if the thing is in a register, adjust the type */
 478: 
 479:     switch( p->in.op ){
 480: 
 481:     case REG:
 482:         if( !rtyflg ){
 483:             /* the C language requires intermediate results to change type */
 484:             /* this is inefficient or impossible on some machines */
 485:             /* the "T" command in match supresses this type changing */
 486:             if( p->in.type == CHAR || p->in.type == SHORT ) p->in.type = INT;
 487:             else if( p->in.type == UCHAR || p->in.type == USHORT ) p->in.type = UNSIGNED;
 488: #if !defined(FORT) && !defined(SPRECC)
 489:             else if( p->in.type == FLOAT ) p->in.type = DOUBLE;
 490: #endif
 491:             }
 492:         if( ! (p->in.rall & MUSTDO ) ) return;  /* unless necessary, ignore it */
 493:         i = p->in.rall & ~MUSTDO;
 494:         if( i & NOPREF ) return;
 495:         if( i != p->tn.rval ){
 496:             if( busy[i] || ( szty(p->in.type)==2 && busy[i+1] ) ){
 497:                 cerror( "faulty register move" );
 498:                 }
 499:             rbusy( i, p->in.type );
 500:             rfree( p->tn.rval, p->in.type );
 501:             rmove( i, p->tn.rval, p->in.type );
 502:             p->tn.rval = i;
 503:             }
 504: 
 505:     case OREG:
 506:         if( p->in.op == REG || !R2TEST(p->tn.rval) ) {
 507:             if( busy[p->tn.rval]>1 && istreg(p->tn.rval) ) cerror( "potential register overwrite");
 508:             }
 509:         else
 510:             if( (R2UPK1(p->tn.rval) != 100 && busy[R2UPK1(p->tn.rval)]>1 && istreg(R2UPK1(p->tn.rval)) )
 511:                 || (busy[R2UPK2(p->tn.rval)]>1 && istreg(R2UPK2(p->tn.rval)) ) )
 512:                cerror( "potential register overwrite");
 513:         }
 514: 
 515:     }
 516: 
 517: #ifndef ncopy
 518: ncopy( q, p ) NODE *p, *q; {
 519:     /* copy the contents of p into q, without any feeling for
 520: 	   the contents */
 521:     /* this code assume that copying rval and lval does the job;
 522: 	   in general, it might be necessary to special case the
 523: 	   operator types */
 524:     register i;
 525: 
 526:     q->in.op = p->in.op;
 527:     q->in.rall = p->in.rall;
 528:     q->in.type = p->in.type;
 529:     q->tn.lval = p->tn.lval;
 530:     q->tn.rval = p->tn.rval;
 531: #ifdef FLEXNAMES
 532:     q->in.name = p->in.name;
 533: #ifdef ONEPASS
 534:     q->in.stalign = p->in.stalign;
 535: #endif
 536: #else
 537:     for( i=0; i<NCHNAM; ++i ) q->in.name[i]  = p->in.name[i];
 538: #endif
 539: 
 540:     }
 541: #endif
 542: 
 543: NODE *
 544: tcopy( p ) register NODE *p; {
 545:     /* make a fresh copy of p */
 546: 
 547:     register NODE *q;
 548:     register r;
 549: 
 550:     ncopy( q=talloc(), p );
 551: 
 552:     r = p->tn.rval;
 553:     if( p->in.op == REG ) rbusy( r, p->in.type );
 554:     else if( p->in.op == OREG ) {
 555:         if( R2TEST(r) ){
 556:             if( R2UPK1(r) != 100 ) rbusy( R2UPK1(r), PTR+INT );
 557:             rbusy( R2UPK2(r), INT );
 558:             }
 559:         else {
 560:             rbusy( r, PTR+INT );
 561:             }
 562:         }
 563: 
 564:     switch( optype(q->in.op) ){
 565: 
 566:     case BITYPE:
 567:         q->in.right = tcopy(p->in.right);
 568:     case UTYPE:
 569:         q->in.left = tcopy(p->in.left);
 570:         }
 571: 
 572:     return(q);
 573:     }
 574: 
 575: allchk(){
 576:     /* check to ensure that all register are free */
 577: 
 578:     register i;
 579: 
 580:     REGLOOP(i){
 581:         if( istreg(i) && busy[i] ){
 582:             cerror( "register allocation error");
 583:             }
 584:         }
 585: 
 586:     }

Defined functions

Defined variables