/* $Header:regvar.c 12.0$ */
/* $ACIS:regvar.c 12.0$ */
/* $Source: /ibm/acis/usr/src/lib/c2_ca/RCS/regvar.c,v $ */

#ifndef lint
static char *rcsid = "$Header:regvar.c 12.0$";
#endif

/* REGVAR.C


   External routines:
      RegVar()     Main routine of register variable optimization




   REGISTER VARIABLE OPTIMIZATION

   ReadPgm reads one function into memory at a time; it is thus
   guaranteed that the entire snode chain is one function.
   Root points at or before the _funct and Tail points at or
   before the _efunct.

   The function is scanned for _sym opcodes.  This special opcode
   identifies memory references which are local and not arrays.
   Its form is, for example:

   _sym   4,"L120+68"

   which means that there is a 4 byte item which is referenced at
   "L120+68" off of the frame pointer register (fp).  The items
   with a width of 4 are placed into an operand table.

   The function is them scanned again and each memory reference
   instruction is examined for references.  If found, the
   corresponding table entry is found and the reference (load or
   store) is counted.  If a literal of the form "!long(name)" is
   found, it is entered into the table.  These can occur only on
   'get' instructions.  They usually load address constants.  If
   some instruction references the operand by taking its address,
   the operand is marked so that it never is loaded into a
   register.

   After the information is gathered, it is sorted by 'rank'.
   The rank of an entry is the sum of the number of loads and
   stores; it is the importance of the operand.  Important
   operands will be placed into the unused registers.

   The _efunct also identifies how many free registers there are.
   Those ranked highest the operand table are chosen to be put in
   those registers.

   If the register is to hold a !long literal value, a get
   instruction is generated just behind the _funct to load the
   value.

   The function is again scanned, looking for all references to
   the given operands (which should only be in load or store
   instructions).  The load/store is 'deleted' and a move
   register (mr) instruction is generated to move the value
   to/from its new register.  (Remeber that only full word values
   are supported).  This mr may be deleted later by another
   optimization phase.

   At the end, a statement is output behind the _funct resetting
   the number of register variable registers that should be saved
   and restored.

   A table summarizing operands, load/store counts, and ranking is
   output into the statement node chain in the form of comments.


*/

#include "stdio.h"
#include "opt.h"
#include "instps.h"
#include "inst.h"
#include "error.h"

/* maximum positive int (assumes int is 2 or 4 bytes) */
#define MAXINT  ( (sizeof(int)==2) ? (int)0x7FFF : (int)0x7FFFFFFF )

/* rank of a given number of load and store references */
#define RANK(i) (okToUse[i] && loads[i] ? loads[i]+stores[i] : 0)
#define LOWRANK 1   /* lowwest rank which is ok to use */

/* maximum times to recurse (given a back branch) */
#define MAXRECURSE 3

/*  table of operands and counts for the 'current' function */
#define MAXREC 100
static char *valOpa[MAXREC]; /* ptr into snode holding operand(s)*/
static char *valOpb[MAXREC]; /*  ...  of load or store           */
static long   loads[MAXREC]; /* count of loads for this operand  */
static long  stores[MAXREC]; /* count of stores for this operand */
static long ranking[MAXREC]; /* importance of this operand       */
static int  okToUse[MAXREC]; /* TRUE if no reason not to optimize*/
static int highValue;

static int canUse;    /* TRUE when scanning if stores optimizable*/

int cvt();

struct snode *ScanFor();
struct snode *RestNode();

RegVarOpt()
{
   register struct snode *funct, *efunct;
   register int firstReg, lastReg, nregs;

   funct  = FunctLoc;
   efunct = EFunctLoc;

   if(DEBUG1)  ListLabels();
   gatherInfo(funct, efunct, (long)1);
   if(highValue <= 0)  return;

   rankReferences();      /* calc rank & sort by rank */
   if( DEBUG1 || ShowMods)  printRecord(efunct);
   firstReg = cvt(efunct->op1);
   lastReg  = cvt(efunct->op2a);
   nregs    = howManyRegs(firstReg, lastReg);
   firstReg = lastReg-nregs+1;
   if(DEBUG1)
      fprintf(stderr,"firstReg: %d  lastReg: %d  nregs: %d\n",
                      firstReg, lastReg, nregs);
   if(nregs>0)  {
      highValue = nregs;
      loadRegVars(funct->last, firstReg, nregs);
      setHowMany(efunct,firstReg);
      replaceReferences(funct, efunct, firstReg, nregs);
      }
   clearRecord();
}


                    /* --------------- */

/* scan program segment for loads/stores which can be optimized */
static gatherInfo(from, to, weight)
register struct snode *from, *to;
register long weight;
{
   register struct snode *sn;
   static recurse = 0;

   if( recurse > MAXRECURSE )   return;
   if( from==NULL || to==NULL )
      return;

   if(DEBUG1)  {
      PrintShortNode( from, "gatherInfo from:" );
      PrintShortNode( to,   "             to:" );
      fprintf( stderr,      "         weight: %d\n", weight );
      }

   recurse += 1;
   if( recurse == 1 )
      for( sn=from; sn!=to; sn=sn->next )
         if( OPNUMBER(sn) == i_sym )
            saveSymTab(sn);

   canUse = TRUE;
   for( sn=from; sn!=to; sn=sn->next )  {
      if( UNIMPORTANT(sn) )   continue;
      if( LOAD(sn) ) {
         canUse = FALSE; /* we're past stores of parms */
/*       if( *(sn->op2a) == '!'						tjm */
/*        && *(sn->op2a+1) == 'l' )   /* look for '$.long' */
         if( *(sn->op2a) == '$'
          && *(sn->op2a+1) == '.'     /* look for '$.long' */
          && *(sn->op2a+2) == 'l' )   /* look for '$.long' */
            saveLiteral(sn,weight);  else
         if( *(sn->op2a) == '$'
          && *(sn->op2a+1) == '_' )   /* look for '$_name' */
            saveLiteral(sn,weight);  else
         if( RegNumber(sn->op2b) == FPREG )
            saveLocVar(sn,weight);
         }  else
      if( STORE(sn) )  {
         if( RegNumber(sn->op2b) == FPREG )
            saveLocVar(sn,weight);
         } else
      if( BRANCH(sn) )  {
         if( BrBkwd(sn) )
            if( sn->lablock!=NULL )
               gatherInfo( sn->lablock->ldef, sn->last, weight<<2 );
         }   else
      checkAddrFetch(sn);
      }
   recurse -= 1;    /* if any returns above, we got problems!! */
   if(DEBUG1)  fprintf( stderr, "End gatherInfo()\n\n" );
}

                    /* --------------- */


/* routines to manipulate record of optimizable references */

/* record loads of literal !long's */
static saveLiteral(sn,weight)
register struct snode *sn;
{
   register int i;

   PrintShortNode(sn, "Count:");
   if( (i=lookupValue(sn->op2a, sn->op2b)) == 0 )
      if( (i=enterReference( sn->op2a, sn->op2b)) == 0 )
         return;
   /* value already in table; tweak table */
   loads[i] += weight;
   if(DEBUG1)  showTabEntry(i);
}


/* record loads/stores of local variables
   (i.e. use 'fp' as base) */
static saveLocVar(sn,weight)
register struct snode *sn;
{
   register int i;

   PrintShortNode(sn, "Count:");
   if( (i=lookupValue(sn->op2a, sn->op2b)) == 0 )
      if( (i=enterReference( sn->op2a, sn->op2b)) > 0 )   {
         /* if no _sym & not parm can't optimize */
         okToUse[i] = canUse;
         if(DEBUG1)  showTabEntry(i);
         }
      else  return;
   /* value already in table; tweak table */
   if( !REFFULL(sn) )
      okToUse[i] = FALSE;
   if( LOAD(sn) )
      { if( loads[i]  < MAXINT )  loads[i]  += weight; }
   else
      { if( stores[i] < MAXINT )  stores[i] += weight; }
   if(DEBUG1)  showTabEntry(i);
}


static showTabEntry( n )
int n;
{
   fprintf( stderr, "%s(%s) l:%d s:%d r:%d ok:%d\n",
            valOpa[n], valOpb[n], loads[n], stores[n],
            ranking[n], okToUse[n] );
}


/* record symbols used as local variables from _sym pseudo op
     format:   _sym  len,"reference"
     example:  _sym  4,"L110+64"
               _sym  4,32
               _sym  4,-48
   Makes no assumptions about when a symtab entry appears;
   can be first, last, or mixed in with other junk           */
static saveSymTab(sn)
register struct snode *sn;
{
   register int i;
   register char *s;

   PrintShortNode(sn, "Enter:");
   /* remove quotes from around 2nd operand */
   s = (sn->op2a)+1;
   *(s+strlen(s)-1) = '\0';

   /* see if value in table */
   if( (i=lookupValue(s, "fp")) == 0 )
      if( (i=enterReference( s, "fp")) == 0 )
         return;

   /* value already in table; tweak table */
   if( *(sn->op1) != '4' )   /* limit to full word symbols */
      okToUse[i] = FALSE;
  else
      okToUse[i] = TRUE;
}


/* enter reference into the table */
static int enterReference( op2a, op2b )
register char *op2a, *op2b;
{
   register int i;

   /* see if form is "0-xx"; if so remove zero */
   if( *op2a=='0' && *(op2a+1)=='-' )  op2a++;

   if( (i=1+highValue) >= MAXREC )
      return 0;
   highValue = i;
   valOpa[i] = op2a;
   valOpb[i] = op2b;
   loads[i]  = 0;
   stores[i] = 0;
   okToUse[i] = TRUE;
   return i;
}


/* see if some instruction references a load/store value.
   if so, make sure it will never get deleted.
   Routine never called if instruction is LOAD or STORE */
static checkAddrFetch(sn)
register struct snode *sn;
{
   int i;

   /* look for:    op  Rn,m(fp)
      (used by RUCC to calculate address of local variable) */
   if( RegNumber(sn->op2b) == FPREG )  {
      saveLocVar(sn);
      i=lookupValue(sn->op2a, sn->op2b);
      if(i>0)  okToUse[i] = FALSE;
      }  else

   /* look for:     addi  rn,fp,i
      (used by RUCC to calculate address of local variable)  */
/* if( OPNUMBER(sn) == i_addi )		tjm */
   if( OPNUMBER(sn) == i_ai )
      if( RegNumber(sn->op2a) == FPREG ) {
         i=lookupValue(sn->op3a,sn->op2a);
         if(i>0)  okToUse[i] = FALSE;
         }
}


/* look up a value in the remembered values */
static int lookupValue( sa, sb )
register char *sa, *sb;
{
   register int i;
   if(sa==NULL)    return 0;

   /* see if form is "0-xx"; if so remove zero */
   if( *sa=='0' && *(sa+1)=='-' )  sa++;

   for(i=1; i<=highValue; i++)
      if( strcmp(valOpa[i],sa) == 0 )
         /* (in following, if pointers match
            they are either null or point to same string!) */
         if( sb==valOpb[i] || strcmp(valOpb[i],sb) == 0 )
            return i;
   return 0;
}


                    /* --------------- */

/* evaluate which references are best
   to replace with register variables.
   Then sort references by ranking */
static rankReferences()
{
   register int i, j, jp1, t;
   register char *ct;

   for( i=1; i<=highValue; i++ )
      ranking[i] = RANK(i);

   if(highValue <= 1)  return;

   /* Welk Sort  (bubble!) */
   for( i=1; i<=highValue; i++ )
      for( j=1, jp1=2;  j<=highValue-i;  j=jp1, jp1++ )
         if( ranking[j] < ranking[jp1] )  {
            t=ranking[j]; ranking[j]=ranking[jp1]; ranking[jp1]=t;
            t=loads[j];     loads[j]=loads[jp1];     loads[jp1]=t;
            t=stores[j];   stores[j]=stores[jp1];   stores[jp1]=t;
            ct=valOpa[j];  valOpa[j]=valOpa[jp1];   valOpa[jp1]=ct;
            ct=valOpb[j];  valOpb[j]=valOpb[jp1];   valOpb[jp1]=ct;
            }
}


/* count how many registers are really needed */
static howManyRegs(firstReg, lastReg)
register int firstReg, lastReg;
{
   register int count;

   /* calculate how many registers are available */
   if(firstReg<0 || lastReg<0 || lastReg<firstReg)
      return 0;
   count = lastReg-firstReg+1;

   /* limit to number of allowed references */
   if(count>highValue)
      count=highValue;

   /* limit further to those not below low rank */
   for( ; count>0; count-- )
      if( ranking[count] >= LOWRANK )
         return count;

   return 0;
}


                    /* --------------- */

/* load the registers at the front of the function */
static loadRegVars(where, r, nregs)
register struct snode *where;
register int r;
register int nregs;
{
   register int i;
   char temp[100];
   for( i=1; i<=nregs; i++ )  {
      c.regvars += 1;
      /* dont need to load locals (not stored!) */
      /*if(valOpb[i] != NULL)  {  */
      /*   if( ShowMods )  {  */
      /*      sprintf( temp, "|        r%d contains %s(%s)    \0",  */
      /*               r++, valOpa[i], valOpb[i]);  */
      /*      RestNode(where, temp);  */
      /*      }  */
      /*   }  */
      /*else  */
         GenRS("get", r++, valOpa[i], valOpb[i], where);
      where = where->next;        /* point to new node     */
      }
}


/* output new number of register variables */
static setHowMany(where, reg)
register struct snode *where;
register int reg;
{
   char temp[50];
   char *Myalloc();
   char *tp, *rp;
   struct snode *sp, *new;

/* sprintf(temp, ".LOWREGVAR = %d\0", reg);		tjm */

   sp = where->last;
   if (Debug) PrintNode(sp,"sp before setHowMany");

   new = CopyNode(sp);
   for (tp=temp,rp=sp->rest; *rp!=','; tp++,rp++)
      *tp = *rp;
   sprintf(tp, ",r%d\0", reg);
   new->rest = Myalloc(strlen(temp)+1);
   strcpy(new->rest,temp);
   InsertNode(new,sp);
   MarkDeleted(sp);
   if (Debug) PrintNode(sp,"sp after setHowMany");
   if (Debug) PrintNode(new,"new after setHowMany");

   sp = sp->last;
   if (Debug) PrintNode(sp,"sp1 before setHowMany");
   new = CopyNode(sp);
   for (tp=temp,rp=sp->rest; *rp!=','; tp++,rp++)
      *tp = *rp;
   sprintf(tp, ",%d\0", reg);
   new->rest = Myalloc(strlen(temp)+1);
   strcpy(new->rest,temp);
   InsertNode(new,sp);
   MarkDeleted(sp);
   if (Debug) PrintNode(new,"new1 after setHowMany");
   if (Debug) PrintNode(sp,"sp1 after setHowMany");

   return;
}


                    /* --------------- */

/* replace references to memory with references to registers */
static replaceReferences( from, to, firstReg, nregs )
register struct snode *from, *to;
register int firstReg, nregs;
{
   register struct snode *sn;
   register int tab;

   for( sn=from; sn!=to; sn=sn->next )  {
      if( UNIMPORTANT(sn) )  continue;
      tab=lookupValue(sn->op2a, sn->op2b);
      if(tab==0)  continue;

      if( !LOAD(sn) && !STORE(sn) )  continue;

      /* drop stores if no loads at all
         (on theory that they were spilled to scratch
         and that loadopt killed all reloads)         */
      if( tab>nregs )
         if( loads[tab]==0 && stores[tab]>0 )  {
            MarkDeleted( sn );
            continue;
            }

      if(LOAD(sn))  {
         c.regvarloads  += 1;
/*       GenRR( "mr", RegNumber(sn->op1), firstReg+tab-1, sn ); 	tjm */
         GenRRR( "cas", RegNumber(sn->op1), firstReg+tab-1, 0,  sn );
         }      else
      if(STORE(sn)) {
         c.regvarstores += 1;
/*       GenRR( "mr", firstReg+tab-1, RegNumber(sn->op1), sn );		tjm */
         GenRRR( "cas", firstReg+tab-1, RegNumber(sn->op1), 0, sn );
         }
      c.regvarmr += 1;
      MarkDeleted( sn );
      }
}


                    /* --------------- */


/* clear the remembered values */
static clearRecord()
{
   register int i;
   for(i=0; i<MAXREC; i++)   {
      loads[i]   = 0;
      stores[i]  = 0;
      ranking[i] = 0;
      valOpa[i]  = NULL;
      valOpb[i]  = NULL;
      }
   highValue = 0;
}


/* output the data collected */
static printRecord(sp)
register struct snode *sp;
{
   register int i;
   char temp[200];

   for(i=highValue; i>0; i--)   {
      if(DEBUG1) fprintf(stderr, "%5d %5d %5d %s\n",
                 loads[i], stores[i], ranking[i], valOpa[i] );
      if(valOpb[i]==NULL)
         sprintf( temp, "|  %5d %5d %5d %s",
                  loads[i], stores[i], ranking[i], valOpa[i] );
      else
         sprintf( temp, "|  %5d %5d %5d %s(%s)",
                  loads[i], stores[i], ranking[i],
                  valOpa[i], valOpb[i] );

      RestNode( sp, temp );
      sp->next->mods = 0;      /* unmark as new (for cleaner output) */
      }
}



                    /* --------------- */

static int cvt(s)
register char *s;
{
   if(s==NULL)
      return -1;
   return atoi(s);
}
