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