#ifndef lint
static char rcsid[] = "$Header:allo.c 12.0$";
#endif
/* $Source: /ibm/acis/usr/src/lib/mip/RCS/allo.c,v $ */
 
static char *sccsid ="%W% (Berkeley) %G%";

#ifdef unix
# include "mfile2.h"
#else
# include "doption h *"  /* circumvention for -D problem with preprocessor */
# include "mfile2 h *"
#endif
 
NODE resc[3];
 
int busy[REGSZ];
 
int maxa, mina, maxb, minb, cura;  /* cura added 4/84 by JEC */

#ifndef FORT
extern int optize;  /* added 7/84 for ibm032 optimizer */
#else
int optize;
#endif 

extern unsigned questmask;  /* added 12/84 for ibm032 optimizer */
 
# ifndef ALLO0
allo0(){ /* free everything */
 
    register i;
 
    maxa = maxb = -1;
    mina = minb = 0;
 
    REGLOOP(i){
        busy[i] = 0;
        if( rstatus[i] & STAREG ){
            if( maxa<0 ) mina = i;
            maxa = i;
            }
        if( rstatus[i] & STBREG ){
            if( maxb<0 ) minb = i;
            maxb = i;
            }
        }
    cura = maxa+1;
    }
# endif
 
# define TBUSY 01000
 
# ifndef ALLO
allo( p, q ) register NODE *p; register struct optab *q; {
 
    register n, i, j;
    register int either;
 
    n = q->needs;
    either = ( EITHER & n );
    i = 0;
#ifndef BUG3
    if( rdebug>1 ) { int index;
        printf("allo: aregs=%d(%s%s), bregs=%d(%s%s), tempstor=%d.\n",
            n&NACOUNT, (n&NASL ? "ShareL" : ""), (n&NASR ? "ShareR" : ""),
            (n&NBCOUNT)>>4, (n&NBSL ? "ShareL" : ""), (n&NBSR ? "ShareR" : ""),
            (n&NTMASK)>>8 );
    }
#endif
/* (ef) 11/14/85 -- grab r2 for function calls */
/* JSW 10/2/86 - also grab r2 for structure assigns, the result of _.blt goes
   here.  Fix for A268 & NCS */
    if ( ( ( p->in.op == STASG ) || callop( p->in.op) ) && ( n&NACOUNT ) ) {
	resc[i].in.op =  REG;
	resc[i].tn.rval= callreg(p);
	resc[i].tn.lval= 0;
	n -= NAREG;
	busy[i] |= TBUSY;
	++i;
    }

    while( n & NACOUNT ){ extern reg_save;
        resc[i].in.op = REG;
        resc[i].tn.rval = freereg( p, n&NAMASK );
        resc[i].tn.lval = 0;
#ifdef FLEXNAMES
        resc[i].in.name = "";
#else
        resc[i].in.name[0] = '\0';
#endif
        n -= NAREG;
	if ((resc[i].tn.rval>MAXARGREG) && (resc[i].tn.rval<reg_save)) 
	   reg_save= resc[i].tn.rval;
        ++i;
        }
 
    if (either) { /* all or nothing at all */
        for( j = 0; j < i; j++ )
            if( resc[j].tn.rval < 0 ) { /* nothing */
                i = 0;
                break;
                }
        if( i != 0 ) goto ok; /* all */
        }
 
    while( n & NBCOUNT ){
        resc[i].in.op = REG;
        resc[i].tn.rval = freereg( p, n&NBMASK );
        resc[i].tn.lval = 0;
#ifdef FLEXNAMES
        resc[i].in.name = "";
#else
        resc[i].in.name[0] = '\0';
#endif
        n -= NBREG;
        ++i;
        }
    if (either) { /* all or nothing at all */
        for( j = 0; j < i; j++ )
            if( resc[j].tn.rval < 0 ) { /* nothing */
                i = 0;
                break;
                }
        if( i != 0 ) goto ok; /* all */
        }
 
    if( n & NTMASK ){
        resc[i].in.op = OREG;
	resc[i].tn.rval = FPREG; /* (ef) 11/30/85 -- using fp again */
        if( p->in.op == STCALL || p->in.op == STARG || p->in.op == UNARY STCALL || p->in.op == STASG ){
            resc[i].tn.lval = freetemp( (SZCHAR*p->stn.stsize + (SZINT-1))/SZINT );
            }
        else {
            resc[i].tn.lval = freetemp( (n&NTMASK)/NTEMP );
            }
 
        resc[i].tn.lval = resc[i].tn.lval / 8;
 
        ++i;
        }
 
    /* turn off "temporarily busy" bit */
 
    ok:
    REGLOOP(j){
        busy[j] &= ~TBUSY;
        }
 
#ifndef BUG3
    if( rdebug>1 ){
        printf("allo:");
        REGLOOP(j){
            if( busy[j] ) printf(" %s=%d", rnames[j], busy[j] );
            }
        }
    for( j=0; j<i; ++j ) if( resc[j].tn.rval < 0 ){
        if( rdebug>1 ) printf(" FAIL\n");
        return(0);
        }
    if( rdebug>1 ) printf(" OK\n");
#else
    for( j=0; j<i; ++j ) if( resc[j].tn.rval < 0 ) return(0);
#endif
    return(1);
 
    }
# endif
 
extern OFFSZ offsz;
freetemp( k ) register k; { /* allocate k integers worth of temp space */
    /* we also make the convention that, if the number of words is more than 1,
    /* it must be aligned for storing doubles... */
 
/* printf( "freetemp( %d ) tmpoff=0x%x, offsz=0x%x, maxoff=0x%x\n",
	    k, tmpoff, offsz, maxoff ); */
 
# ifndef BACKTEMP
    register int t;
 
    if( k>1 ){
        SETOFF( tmpoff, ALDOUBLE );
        }
 
    t = tmpoff;
    tmpoff += k*SZINT;
    if( tmpoff > maxoff ) maxoff = tmpoff;
    if( tmpoff >= offsz )
        cerror( "stack overflow" );
    if( tmpoff-baseoff > maxtemp ) maxtemp = tmpoff-baseoff;
    return(t);
 
# else
    tmpoff += k*SZINT;
    if( k>1 ) {
        SETOFF( tmpoff, ALDOUBLE );
        }
    if( tmpoff > maxoff ) maxoff = tmpoff;
    if( tmpoff >= offsz ){
        printf( "tmpoff=0x%x, offsz=0x%x\n", tmpoff, offsz );
        cerror( "stack overflow" );
        }
    if( tmpoff-baseoff > maxtemp ) maxtemp = tmpoff-baseoff;
    return( -tmpoff );
# endif
    }
 
freereg( p, n ) register NODE *p; register n; {
    /* allocate a register of type n */
    /* p gives the type, if floating */
 
    register j;
    extern int areg_needed;
    extern int taregs[], tbregs[], tregs[];
 
 if (xdebug) fwalk( p, eprint, 0 );
    j = p->in.rall & ~MUSTDO;		/* needed and not allocated */
    if( j!=NOPREF && rstatus[j]&STAREG && usable(p,n,j) ){ 
        return( j );
        }
    if( n&NAMASK ){
/* (ef) 11/17/85 -- give out registers in reverse order so we don't */
/*                  walk on arguments.                              */
/* (ef) 11/17/85 -- first look in non-argument registers            */
/*								    */
/*	for( j=maxa;j>MAXARG; j-- ) if ( rstatus[j]&STAREG ) {	    */
/*	    if( usable(p,n,j) ){				    */
/*                return( cura=j );				    */
/*	    }							    */
/*        }							    */
 
/*        for( j=cura; j>mina; --j ) if ( rstatus[j]&STAREG ) {     */
/*            if( usable(p,n,j) ){				    */
/*                return( cura=j );				    */
/*                }						    */
/*            }							    */
/*        for( j=mina; j<=cura; ++j ) if( rstatus[j]&STAREG ){	    */
/*            if( usable(p,n,j) ){				    */
/*                return( cura=j );				    */
/*                }						    */
/*            }							    */
	  register int *reglist= taregs;

	  while ( (j= *reglist++) >= 0 ) {
if (xdebug) printf("freereg: checking %s\n",rnames[j]);
	      if (rstatus[j]&STAREG) {
		  if (usable(p,n,j)) {
		      return( cura=j );
		  }
		  else if (xdebug) printf("freereg: %s not usable\n",rnames[j]);
	      }
	      else if (xdebug) printf("freereg: %s not a temp reg\n",rnames[j]);
	  }
    }
    else if( n &NBMASK ){
/*        for( j=minb; j<=maxb; ++j ) if( rstatus[j]&STBREG ){*/
/*            if( usable(p,n,j) ){*/
/*                return(j);*/
/*                }*/
/*            }*/
	  register int *reglist= tbregs;

	  while ( (j= *reglist++) >= 0 ) {
if (xdebug) printf("freereg: checking %s\n",rnames[j]);
	      if (rstatus[j]&STBREG) {
		  if (usable(p,n,j)) {
		      return( cura=j );
		  }
		  else if (xdebug) printf("freereg: %s not usable\n",rnames[j]);
	      }
	      else if (xdebug) printf("freereg: %s not a temp reg\n",rnames[j]);
	  }
        }
 
    return( -1 );
    }
 
# ifndef USABLE
usable( p, n, r ) register NODE *p; register n, r; {
    /* decide if register r is usable in tree p to satisfy need n */
 
    /* checks, for the moment */
    if( !istreg(r) ) cerror( "usable asked about nontemp register" ); 
 
    if( busy[r] > 1 ) return(0);
    if( isbreg(r) ){
        if( n&NAMASK ) return(0);
        }
    else {
        if( n & NBMASK ) return(0);
        }

/* (ef) 11/16/85 -- keep your hands off of my argument registers */
/*                 (unless you're an argument)                   */
    if ((p->in.rall&~MUSTDO)==NOPREF) {/* arguments MUSTDO appropriate regs */
	extern int areg_needed,areg_used;

if (xdebug) {
   printf("usable: areg_needed= %d, areg_used= %d, r= %d\n",areg_needed,areg_used,r);
   }
	if (areg_needed&&INARGS(r)&&/*(r<=areg_needed)*/(r<=areg_used)) {
	   return(0);
	}
    }
/* (ef) 11/16/85 -- end of additions */

/*    if( (n&NAMASK) && (szty(p->in.type) == 2) ){ /* only do the pairing for real regs */
/*        if( r&01 ) return(0);*/
/*        if( !istreg(r+1) ) return( 0 );*/
/*        if( busy[r+1] > 1 ) return( 0 );*/
/*       if( busy[r] == 0 && busy[r+1] == 0  ||*/
/*            busy[r+1] == 0 && shareit( p, r, n ) ||*/
/*            busy[r] == 0 && shareit( p, r+1, n ) ){*/
/*            busy[r] |= TBUSY;*/
/*            busy[r+1] |= TBUSY;*/
/*            return(1);*/
/*            }*/
/*        else return(0);*/
/*        }*/

    if( busy[r] == 0 ) {
        busy[r] |= TBUSY;
        return(1);
        }
 
    /* busy[r] is 1: is there chance for sharing */
    return( shareit( p, r, n ) );
 
    }
# endif
 
shareit( p, r, n ) register NODE *p; register r, n; {
    /* can we make register r available by sharing from p
       given that the need is n */
    if( (n&(NASL|NBSL)) && ushare( p, 'L', r ) ) return(1);
    if( (n&(NASR|NBSR)) && ushare( p, 'R', r ) ) return(1);
    return(0);
    }
 
ushare( p, f, r ) register NODE *p; register f,r; {
    /* can we find a register r to share on the left or right
        (as f=='L' or 'R', respectively) of p */
    p = getlr( p, f );
    if( p->in.op == UNARY MUL ) p = p->in.left;
    if( p->in.op == OREG ){
        if( R2TEST(p->tn.rval) ){
            return( r==R2UPK1(p->tn.rval) || r==R2UPK2(p->tn.rval) );
            }
        else return( r == p->tn.rval );
        }
    if( p->in.op == REG ){
        return( r == p->tn.rval || ( szty(p->in.type) == 2 && r==p->tn.rval+1 ) );
        }
    return(0);
    }
 
recl2( p ) register NODE *p; {
    register r = p->tn.rval;
#ifndef OLD
    register int op = p->in.op;
    if (op == REG && r >= REGSZ)
        op = OREG;
    if( op == REG ) rfree( r, p->in.type );
    else if( op == OREG ) {
        if( R2TEST( r ) ) {
            if( R2UPK1( r ) != 100 ) rfree( R2UPK1( r ), PTR+INT );
            rfree( R2UPK2( r ), INT );
            }
        else {
            rfree( r, PTR+INT );
            }
        }
#else
    if( p->in.op == REG ) rfree( r, p->in.type );
    else if( p->in.op == OREG ) {
        if( R2TEST( r ) ) {
            if( R2UPK1( r ) != 100 ) rfree( R2UPK1( r ), PTR+INT );
            rfree( R2UPK2( r ), INT );
            }
        else {
            rfree( r, PTR+INT );
            }
        }
#endif
    }
 
int rdebug = 0;
 
# ifndef RFREE
rfree( r, t ) register r; register TWORD t; {
    /* mark register r free, if it is legal to do so */
    /* t is the type */
 
# ifndef BUG3
    if( rdebug ){
        printf( "rfree( %s ), size %d\n", rnames[r], szty(t) );
        }
# endif
 
    if( istreg(r) ){
        if( --busy[r] < 0 ) cerror( "register overfreed");
        if( szty(t) == 2 ){
            if( (r&01) || (istreg(r)^istreg(r+1)) ) cerror( "illegal free" );
            if( --busy[r+1] < 0 ) cerror( "register overfreed" );
            }
        }
    }
# endif
 
# ifndef RBUSY
rbusy(r,t) register r; register TWORD t; {
    /* mark register r busy */
    /* t is the type */
#ifdef FORT
extern int reg_use;
#endif FORT
 
# ifndef BUG3
    if( rdebug ){
        printf( "rbusy( %s ), size %d\n", rnames[r], szty(t) );
        }
# endif
 
    if( istreg(r) ) ++busy[r];
    if( szty(t) == 2 ){
        if( istreg(r+1) ) ++busy[r+1];
        if( (r&01) || (istreg(r)^istreg(r+1)) ) cerror( "illegal register pair freed" );
        }
#ifdef FORT
    if (r<reg_use) reg_use= r;
#endif FORT
    }
# endif
 
# ifndef BUG3
rwprint( rw ) register rw; { /* print rewriting rule */
    register i, flag;
    static char * rwnames[] = {
 
        "RLEFT",
        "RRIGHT",
        "RESC1",
        "RESC2",
        "RESC3",
        0,
        };
 
    if( rw == RNULL ){
        printf( "RNULL" );
        return;
        }
 
    if( rw == RNOP ){
        printf( "RNOP" );
        return;
        }
 
    flag = 0;
    for( i=0; rwnames[i]; ++i ){
        if( rw & (1<<i) ){
            if( flag ) printf( "|" );
            ++flag;
            printf( rwnames[i] );
            }
        }
    }
# endif
 
reclaim( p, rw, cookie ) register NODE *p; register cookie; {
    register NODE **qq;
    register NODE *q;
    register i;
    NODE *recres[5];
    register struct respref *r;
 
    /* get back stuff */
 
# ifndef BUG3
    if( rdebug ){
        printf( "reclaim( %o, ", p );
        rwprint( rw );
        printf( ", " );
        prcook( cookie );
        printf( " )\n" );
        }
# endif
 
    if( rw == RNOP || ( p->in.op==FREE && rw==RNULL ) )
        goto returntocaller;  /* do nothing */
 
    walkf( p, recl2 );
 
    if( callop(p->in.op) ){
        /* check that all scratch regs are free */
        callchk(p);  /* ordinarily, this is the same as allchk() */
        }
 
    if( rw == RNULL || (cookie&FOREFF) ){ /* totally clobber, leaving nothing */
        tfree(p);
        goto returntocaller;
        }
 
    /* handle condition codes specially */
 
    if( (cookie & FORCC) && (rw&RESCC)) {
        /* result is CC register */
        tfree(p);
        p->in.op = CCODES;
        p->tn.lval = 0;
        p->tn.rval = 0;
        goto returntocaller;
        }
 
    /* locate results */
 
    qq = recres;
 
    if( rw&RLEFT) *qq++ = getlr( p, 'L' );;
    if( rw&RRIGHT ) *qq++ = getlr( p, 'R' );
    if( rw&RESC1 ) *qq++ = &resc[0];
    if( rw&RESC2 ) *qq++ = &resc[1];
    if( rw&RESC3 ) *qq++ = &resc[2];
 
    if( qq == recres ){
        cerror( "illegal reclaim");
        }
 
    *qq = NIL;
 
    /* now, select the best result, based on the cookie */
 
    for( r=respref; r->cform; ++r ){
        if( cookie & r->cform ){
            for( qq=recres; (q= *qq) != NIL; ++qq ){
                if( tshape( q, r->mform ) ) goto gotit;
                }
            }
        }
 
    /* we can't do it; die */
    cerror( "cannot reclaim");
 
    gotit:
 
    if( p->in.op == STARG ) p = p->in.left;  /* STARGs are still STARGS */
                              /* may need to remove the following line JEC */
    q->in.type = p->in.type;  /* to make multi-register allocations work */
        /* maybe there is a better way! */
    q = tcopy(q);
 
    tfree(p);
 
    p->in.op = q->in.op;
    p->tn.lval = q->tn.lval;
    p->tn.rval = q->tn.rval;
#ifdef FLEXNAMES
    p->in.name = q->in.name;
#ifdef ONEPASS
    p->in.stalign = q->in.stalign;
#endif
#else
    for( i=0; i<NCHNAM; ++i )
        p->in.name[i] = q->in.name[i];
#endif
 
    q->in.op = FREE;
 
    /* if the thing is in a register, adjust the type */
 
    switch( p->in.op ){
 
    case REG:
        if( !rtyflg ){
            /* the C language requires intermediate results to change type */
            /* this is inefficient or impossible on some machines */
            /* the "T" command in match supresses this type changing */
            if( p->in.type == CHAR || p->in.type == SHORT ) p->in.type = INT;
            else if( p->in.type == UCHAR || p->in.type == USHORT ) p->in.type = UNSIGNED;
/* 7/84     else if( p->in.type == FLOAT ) p->in.type = DOUBLE;*/
          }

        if( ! (p->in.rall & MUSTDO ) )
            goto returntocaller;  /* unless necessary, ignore it */
        i = p->in.rall & ~MUSTDO;
        if( i & NOPREF ) goto returntocaller;
        if( i != p->tn.rval ){
            if( busy[i] || ( szty(p->in.type)==2 && busy[i+1] ) ){
                cerror( "faulty register move" );
                }
            rbusy( i, p->in.type );
            rfree( p->tn.rval, p->in.type );
            rmove( i, p->tn.rval, p->in.type );
            p->tn.rval = i;
            }
 
    case OREG:
        if( p->in.op == REG || !R2TEST(p->tn.rval) ) {
            if( busy[p->tn.rval]>1 && istreg(p->tn.rval) ) cerror( "potential register overwrite");
            }
        else
            if( (R2UPK1(p->tn.rval) != 100 && busy[R2UPK1(p->tn.rval)]>1 && istreg(R2UPK1(p->tn.rval)) )
                || (busy[R2UPK2(p->tn.rval)]>1 && istreg(R2UPK2(p->tn.rval)) ) )
               cerror( "potential register overwrite");
        }
 
    returntocaller:  /* added 7/84 for ibm032 optimizer */
if(optize>1) printf( "reclaim: questmask = 0x%x\n", questmask );
        if( optize ){
            register i, freemask = 0;
            REGLOOP(i) { extern int areg_used,areg_needed;
                if (( istreg(i) && busy[i]==0 ) &&
		    ( areg_needed && (i<areg_used || i> areg_needed))) {
		    freemask |= 1 << i;
		}
	    }
            printf( "_freg 0x%x\n", freemask & ~questmask );
        }
 
    }
 
ncopy( q, p ) register NODE *p, *q; {
    /* copy the contents of p into q, without any feeling for
       the contents */
    /* this code assume that copying rval and lval does the job;
       in general, it might be necessary to special case the
       operator types */
    register i;
 
    q->in.op = p->in.op;
    q->in.rall = p->in.rall;
    q->in.type = p->in.type;
    q->tn.lval = p->tn.lval;
    q->tn.rval = p->tn.rval;
#ifdef FLEXNAMES
    q->in.name = p->in.name;
#ifdef ONEPASS
    q->in.stalign = p->in.stalign;
#endif
#else
    for( i=0; i<NCHNAM; ++i ) q->in.name[i]  = p->in.name[i];
#endif
 
    }
 
NODE *
tcopy( p ) register NODE *p; {
    /* make a fresh copy of p */
 
    register NODE *q;
    register r;
 
    ncopy( q=talloc(), p );
 
    r = p->tn.rval;
    if( p->in.op == REG ) rbusy( r, p->in.type );
    else if( p->in.op == OREG ) {
        if( R2TEST(r) ){
            if( R2UPK1(r) != 100 ) rbusy( R2UPK1(r), PTR+INT );
            rbusy( R2UPK2(r), INT );
            }
        else {
            rbusy( r, PTR+INT );
            }
        }
 
    switch( optype(q->in.op) ){
 
    case BITYPE:
        q->in.right = tcopy(p->in.right);
    case UTYPE:
        q->in.left = tcopy(p->in.left);
        }
 
    return(q);
    }
 
allchk(){
    /* check to ensure that all register are free */
 
    register i;
 
    REGLOOP(i){
        if( istreg(i) && busy[i] ){
            cerror( "register allocation error");
            }
        }
    }
