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