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