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