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

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

/* LOADOPT.C
 
   External routines:
     LoadOpt()    Main routine of load optimizer
 
 
 
   LOAD OPTIMIZATIONS
 
   The optimizer recognizes what loads can be deleted by looping
   through all statements.  If a statement:
 
   o   has a label, flush all remembered register contents.
   o   is marked 'dangerous', flush everything;  else
   o   is a LOAD, see if it can be omitted (see below); else
   o   is a move register (mr) then copy register contents; else
   o   is a store, remember register contents; else
   o   is an unconditional branch then flush everything; else
   o   it otherwise changes a register then flush the register.
 
   Register contents are remembered by recording the source
   string which 'names' the place from which loaded or into which
   stored.  A load/store type is placed at the front.
 
   For example, "get r2,abc" is recorded as "f:abc" which means a
   fullword load from 'abc'.  If this is followed by "getc
   r2,0(r2)" then the register contents are remembered as "f:abc
   c:()" which means an indirect character load off of a register
   loaded with a full word from 'abc'.
 
   If an indirect load is encountered and no current value is
   remembered for the base register, as in "get r2,56(fp)" then
   "f:56(r4)" is remembered as the value of r2.
 
   In all cases, if a register is changed, the remembered values
   are scanned for a reference to that register and they are
   invalidated.  For example, after the above value, "f:56(r4)",
   is remembered for r2, any change to r4 causes the value
   remembered for r2 to be flushed.
 
   Loads can be omitted when they would create a string which
   matches one already remembered for a register.  If a load is
   to, say, r5 then r5 is examined first for the value (hoping it
   is already there) and then all registers are searched for the
   value.  If found in some other register, a move register (mr)
   instruction is generated.
 
 
   Indirect load sequences like this:  l   r5,44(fp)
                                       l   r5,0(r5)
 
   are remembered such that the PAIR acts like a unit and another
   pair which loads the same result will be deleted if the result
   is still around.
 
OBSELETE:
/  RUCC processes some post increments (such as i++ or i--) which
/  are not for register variables by incrementing the variable in
/  a register, storing the updated value, and then decrementing
/  the value for further use.  While the code generated is as
/  good as the alternatives, this obscures the value in the
/  register.
/
/  ROPT has a special case in which it looks ahead whenever an
/  ADDI (or SUBI) changes a register to see if it is followed by
/  a store and SUBI (or ADDI) of the same register.  If so, then
/  the three instructions are considered as a unit to have no
/  effect on the register.
 
*/
 
#include "stdio.h"
#include "opt.h"
#include "inst.h"
#include "instps.h"
#include "error.h"
 
/* 'inreg' describes what was loaded from or stored into.
   'whereset' points to oldest snode affecting register */
#define INREGSIZE 100
static char inreg[16][INREGSIZE];
static struct snode *whereset[16];
 
/* String in regvar[] is used as 'value' of a register variable
   register.   This routine doesn't know which are reg vars; it
   allows any to be.   Note that parenthesized register name is
   required so that values are properly flushed if the named
   register is later changed.    */
static char *regvar[16] = {
   "[RegVar(r0)]",   "[RegVar(r1)]",
   "[RegVar(r2)]",   "[RegVar(r3)]",
   "[RegVar(r4)]",   "[RegVar(r5)]",
   "[RegVar(r6)]",   "[RegVar(r7)]",
   "[RegVar(r8)]",   "[RegVar(r9)]",
   "[RegVar(r10)]",  "[RegVar(r11)]",
   "[RegVar(r12)]",  "[RegVar(r13)]",
   "[RegVar(r14)]",  "[RegVar(r15)]" };
 
/* static struct snode *skipPostInc(); */
static flushRegs();
 
/* main loop of load instruction elimination */
LoadOpt()
{
   register struct snode *iload, *nextn;
 
   flushRegs(NULL,0,15);
   iload = Root;
   while ( (iload = iload->next) != NULL)  {
      if( FREGS(iload) ||
          UNIMPORTANT(iload) )     continue;
      PrintShortNode(iload, "See if LOAD: ");
      if ( HASLABEL(iload) )    flushRegs(iload,0,15);
/*    if ( OPNUMBER(iload) == i_addi	 tjm */
/*      || OPNUMBER(iload) == i_shla	 tjm */
/*      || OPNUMBER(iload) == i_subi )	 tjm */

      if ( OPNUMBER(iload) == i_ai
        || OPNUMBER(iload) == i_shla
        || OPNUMBER(iload) == i_si )
         modifyReg( iload );  else
/*       if( (nextn=skipPostInc(iload, i_addi, i_subi)) != NULL ||
/*           (nextn=skipPostInc(iload, i_subi, i_addi)) != NULL ) {
/*            iload = nextn;
/*            continue;  }                                       */
      if ( UNKNOWN(iload) )     flushRegs(iload,0,15);    else
      if ( UCBRANCH(iload))  {
         if ( EXFORM(iload) )   iload = iload->next;
         flushRegs(iload,0,15);  }                        else
      if ( LOAD(iload) )        loadInstruction(iload);   else
/*    if ( OPNUMBER(iload) == i_mr )	tjm */
      if ( MR(iload) )
                                moveReg(iload);           else
      if ( STORE(iload) )       regStored(iload);         else
      if ( SETREG(iload) )      regChanged(iload);
      }
}
 
                    /* --------------- */
 
 
/* Process a Load instruction.  If a load or load sequence cannot
   be omitted, record the result of the load.
*/
static loadInstruction(sp)
register struct snode *sp;
{
   if( tryOmitLoad(sp,sp,"") )
      return;
   regLoaded(sp);
   if(DEBUG1) fprintf(stderr," tryOmitLoad didn't omit a load\n");
}
 
                    /* --------------- */
 
/* look for sequence of loads and indirect loads;
   replace as much as possible.
   Calls itself recursively to look ahead for indirect loads.
   Returns TRUE if load(s) were deleted; FALSE otherwise.
*/
static tryOmitLoad(iload,sp,prevtemp)
register struct snode *iload;
register struct snode *sp;
char *prevtemp;
{
   register struct snode *ahead, *tsp;
   int i, regno;
   char temp[INREGSIZE*2];
 
   /* update load indicator string */
   strcpy(temp,prevtemp);
   if(*temp == 0)
      formRegVal(sp, temp);
   else
      addIndRef(temp, sp->ldstype, sp->op2a);
   if(DEBUG1) fprintf(stderr,"tryOmitLoad looking at: %s\n", temp);
 
   /* get op1 register number */
   regno = RegNumber(sp->op1);
   if (regno < 0)  {Error(E_FORM, sp->op1, sp);
                    flushRegs(iload,0,15); return FALSE; }
 
   /* Look ahead.  If next instr is an indirect load to same register
      as current load, then recurse and try to omit whole sequence.
      If recursion was successful, we exit here                     */
   ahead = NextImportant(sp);
   if( ahead != NULL)  /* if null, doesn't matter */
      if( LOAD(ahead) )
         if( RegNumber(ahead->op1)  == regno
          && RegNumber(ahead->op2b) == regno )
            if(tryOmitLoad(iload,ahead,temp))
               return TRUE;
 
   /* if we get here, the current instruction is the last (or only)
      instruction in a sequence.  If deletable, we can do it here */
 
   /* See if value to be loaded is already loaded.
      If so, delete it and possibly add MR          */
   if( (i=scanRegs(temp,regno,regno)) >= 0  ||
       (i=scanRegs(temp,0,15)) >= 0   ) {
 
      /* delete all loads looked ahead over plus 'original' load */
      for( tsp=iload; tsp->last!=sp; tsp=tsp->next)
          deleteInstr(tsp);
 
      /* invalidate fregs for register holding value */
      InvalidateFregs( whereset[i], sp, i );
 
      /* add MR if needed */
      if(i!=regno)  {
/*       GenRR( "mr", regno, i, sp );	tjm */
         GenRRR( "cas", regno, i, 0, sp );
         c.loadgenmr += 1;
         /* if( invalidated )  GenFREG( sp->next, i ); */
         }
      if(DEBUG1) fprintf(stderr," tryOmitLoad omited a load\n");
 
      return TRUE;  /* tell that we were successful */
      }
 
   /* return with indication that this level didn't do anything */
   return FALSE;
}
 
                    /* --------------- */
 
/* scan registers for a given value */
static int scanRegs(val, lowrange, highrange)
register char *val;     /* string describing register contents */
register int lowrange, highrange;
{
   register int i;
 
   for( i=lowrange; i<=highrange; i++)  {
      if(DEBUG1)  if( *(inreg[i]) )
                    if( !REGVARREG(i) ||
                        (REGVARREG(i) && *(inreg[i])!='[') )
                       fprintf(stderr,"Looking at r%d: %s\n",
                                       i, inreg[i]);
      if(*(inreg[i])) /* i.e. if not empty string */
         if( !strcmp( inreg[i], val ) ) {
            /* value found in a register */
            if(DEBUG1) fprintf(stderr,"Found value in register %d\n", i);
            return(i);
            }
      }
   return(-1);
}
 
                    /* --------------- */
 
/* delete an instruction */
static deleteInstr( sn )
register struct snode *sn;
{
   MarkDeleted( sn );
/* if( OPNUMBER(sn) == i_mr )   c.loadmrchanges += 1; else	tjm */
   if( MR(sn) )                 c.loadmrchanges += 1; else
   if( REFIMMED(sn) )           c.loadideletes += 1;  else
                                c.loadchanges += 1;
}
 
                    /* --------------- */
 
/*  record the change to the register set made by a load
*/
static regLoaded(iload)
register struct snode *iload;
{
   register int regno, regno2;
   char temp[INREGSIZE*2];
 
   PrintShortNode( iload, "regLoaded looking at:");
 
   /* get register numbers */
   regno  = RegNumber(iload->op1);
   if(regno<0)  return;
 
   /* clear other registers which remember values
      based on old value of target register      */
   delRefsTo( iload->op1 );
 
   /* remember what we just loaded into the register */
   formRegVal(iload, temp);
   strcpy(inreg[regno], temp);
 
   /* Set 'whereset' of target to this node.   */
   whereset[regno] = iload;
 
   /* if tracing, output record of register values */
   if(Trace)  traceLoadStatus(iload);
   if(DEBUG1)  fprintf(stderr,"regLoaded into %d: %s\n",
                      regno, inreg[regno]);
}
 
                    /* --------------- */
 
 
/* Some change was made to a register and we don't know
   how to record the effect.
   Flush the register and flush all other references to it.
 */
static regChanged(iload)
 register struct snode *iload;
 {
    register int regno;
    regno = RegNumber(iload->op1);
    flushRegs(iload,regno,regno);
    if(DEBUG1)  fprintf(stderr,"regChanged\n");
    delRefsTo( iload->op1 );
    if(Trace)  traceLoadStatus(iload);
 }
 
                    /* --------------- */
 
/*  Process register contents upon a store.
    Unrecord memories of thing stored to.
*/
static regStored(sp)
register struct snode *sp;
{
   register int regno;
   char temp[INREGSIZE*2];
 
   /* get op1 register number */
   regno = RegNumber(sp->op1);
 
   /* remember register contents */
   formRegVal(sp, temp);
   if( strcmp(temp, inreg[regno]) == 0 )
      c.redunstore += 1;
 
   /* delete references to register used as base for store */
   if( sp->op2b != NULL)
      delRefsTo(sp->op2a, sp->op2b);
 
   /* record remembered register contents.  Note that even reg vars
      are remembered.  When flushed, they regain special values */
   if( *inreg[regno] == '\0' )  {
      strcpy( inreg[regno], temp );
      whereset[regno] = sp;
      }
 
   if(Trace)  traceLoadStatus(sp);
   if(DEBUG1) fprintf(stderr,"regStored from %d: %s\n",regno,inreg[regno]);
}
 
 
 
                    /* --------------- */
 
/* Scan all registers looking for a reference to a given register.
   Flush remembered register contents if register contains
   any reference to the given register.
 
   Input is the register as a string.
   A string is built with the form:    (r)
   and this string is scanned for in all register values.
*/
static delRefsTo(sr)
/*register char *so;    /* offset from some base register (or NULL) */
register char *sr;    /* the register being referenced  */
{
   char temp[20];
   register int i;
   register char *s, *ptemp;
 
   /* build string to scan for */
   i = 0;
   ptemp = temp;
/* if( !REGVARREG( RegNumber(sr) ))                 */
/*    if(so != NULL)                                */
/*       while(*so && (++i<20))  *ptemp++ = *so++;  */
   *ptemp++ = '(';
   while(*sr && (++i<10))  *ptemp++ = *sr++;
   if(i>=10)  { flushRegs(NULL,0,15); return; }
   *ptemp++ = ')';
   *ptemp = '\0';
 
   /* scan register contents for string */
   if(DEBUG1) fprintf(stderr,"delRefsTo: %s\n", temp);
   for( i=0; i<=15; i++ )  {
      ptemp = temp;
      s = inreg[i];
      while (*s)  {
         while(*s && *s!=*ptemp )  /* scan for start of ref */
            s++;
         if(*s)
            if( regMatch(ptemp,s) )  {
               if(DEBUG1)  fprintf(stderr,
                   "Marked reg %d as empty; contained %s\n",
                   i, inreg[i] );
               flushRegs(NULL,i,i);
               break;
               }
            else s++;
         }
      } /*for*/
}
 
/* match two strings of form "(reg)"  or "offset(reg)"
   return TRUE if match up to right parens,
   FALSE otherwise.
   Note:  current callers don't pass an offset.
 */
static regMatch(a,b)
register char *a, *b;
{
   if( a==NULL || b==NULL )  return FALSE;
   while( *a==*b  &&  *a  &&  *a!=')' )   { a++; b++; }
   return *a==')' && *b==')';
}
 
                    /* --------------- */
 
/*  MR instruction; contents of one register moved to another
*/
static moveReg(iload)
register struct snode *iload;
{
   register int regno, regno2;
 
   /* get  register values */
   regno  = RegNumber(iload->op1);
   regno2 = RegNumber(iload->op2a);
   if (regno<0)   {Error(E_FORM,iload->op1,iload);
                   flushRegs(iload,0,15); return;}
   if (regno2<0)  {Error(E_FORM,iload->op2a,iload);
                   flushRegs(iload,0,15); return;}
   if(regno==regno2)  return;
 
   /* target may already have same value;
      if so, delete MR & exit. */
   if( *inreg[regno] )
      if( strcmp(inreg[regno], inreg[regno2]) == 0 )   {
         deleteInstr(iload);
         return;
         }
 
   /* clear other registers which remember values
      based on old value of this register      */
   delRefsTo(iload->op1);
 
   /* if copying from a reg var which is empty,
      copy special value which indicates which reg var.
      Otherwise just copy value to target register   */
   if( REGVARREG(regno2)
    && !REGVARREG(regno)
    && *inreg[regno2] == '\0' ) {
      strcpy( inreg[regno], regvar[regno2] );
      whereset[regno] = iload;
      if(DEBUG1) fprintf(stderr,
         " Reg %d copied from RegVar %d with value %s\n",
         regno, regno2, inreg[regno]);
      }
   else {
      strcpy( inreg[regno], inreg[regno2] );
      whereset[regno] = iload;
      if(DEBUG1) fprintf(stderr,
         " Reg %d copied from reg %d with value %s\n",
         regno, regno2, inreg[regno]);
      }
 
   /* if tracing, record register remembered values in output */
   if(Trace)  traceLoadStatus(iload);
}
 
 
                    /* --------------- */
 
/* process instructions which modify content of a register */
static modifyReg( iload )
register struct snode *iload;
{
   register int regno;
   register char *s = NULL;
 
   regno = RegNumber( iload->op1 );
   if( regno<0 )  return;   /* should not happen */
 
   switch( OPNUMBER(iload) )   {
/*    case i_addi:  s = " addi:";  break;	tjm */
/*    case i_subi:  s = " subi:";  break;	tjm */
      case i_ai:    s = " ai:";    break;
      case i_si:    s = " si:";    break;
      case i_shla:  s = " shla:";  break;
      default:  return;
      }
 
   delRefsTo( iload->op1 );
   strcat( inreg[regno], s );
   strcat( inreg[regno], iload->op2a );
}
 
 
                    /* --------------- */
 
/* See if three instructions are a wash with regard to
   the target register of the first instruction.
   If this is a post inc/dec and if 2nd op is MR,
   flushes its 1st reg.
   Returns NULL if not found  OR
   returns pointer to last instr of sequence.
 
      addi  r5,1                   addi  r5,1
      st    r5,xxx       or        mr    r8,r5
      subi  r5,1                   subi  r5,1
 */
 
/*static struct snode *skipPostInc(sp, i1, i2)
/*register struct snode * sp;
/*register int i1, i2;
/*{
/*   register int r;
/*   register char *n;
/*   register struct snode* mr_sp;
/*
/*   mr_sp = NULL;
/*   if ( OPNUMBER(sp) != i1 )           return NULL;
/*   r = RegNumber(sp->op1);    /* register to inc/dec */
/*   n = sp->op2a;              /* addi/subi amount    */
/*
/*   sp = NextImportant(sp);
/*   if( sp==NULL )                      return NULL;
/*   if ( HASLABEL(sp) )                 return NULL;
/*   if ( OPNUMBER(sp) == i_put )  {
/*      if( r != RegNumber(sp->op1) )    return NULL;
/*      }
/*   else {   /* not a PUT */
/*/*    if( OPNUMBER(sp) != i_mr)        return NULL; 	tjm */
/*      if( MR(sp) )                     return NULL;
/*      if( r == RegNumber(sp->op2a))    return NULL;
/*      if( r != RegNumber(sp->op1) )    return NULL;
/*      mr_sp = sp;
/*      }
/*
/*   sp = NextImportant(sp);
/*   if( sp==NULL )                      return NULL;
/*   if ( HASLABEL(sp) )                 return NULL;
/*   if ( OPNUMBER(sp) != i2 )           return NULL;
/*   if ( r != RegNumber(sp->op1) )      return NULL;
/*   if ( strcmp(n,sp->op2a) != 0 )      return NULL;
/*
/*   c.loadpostskip += 1;
/*   if(DEBUG1)  fprintf(stderr,"Skipping post inc/dec.\n");
/*
/*   /* if skipping MR, flush MR target register */
/*   if( mr_sp != NULL )   {
/*      r = RegNumber(mr_sp->op1);
/*      flushRegs(mr_sp, r, r);
/*      }
/*
/*   return sp;
/*}
--- */
 
                    /* --------------- */
 
/*  clear registers so that range given contains "nothing"
*/
static flushRegs(sp, r1, r2)
register struct snode *sp;
register int r1, r2;
{
   register int i;
   if(DEBUG1)  fprintf(stderr,"flushRegs %d %d\n",r1,r2);
   for( i=r1; i<=r2; i++)  {
      whereset[i] = NULL;
      if( REGVARREG(i) )
         strcpy(inreg[i],regvar[i]);
      else
         *(inreg[i]) = '\0';
      }
 
   if(Trace)
      if(sp)
         traceLoadStatus(sp);
}
 
 
 
                    /* --------------- */
 
 
/* Build string which remembers operands as value of register.*/
static formRegVal(sp, s)
register struct snode *sp;
register char * s;
{
   int regno, regno2;
 
   /* get register values */
   regno = RegNumber(sp->op1);
   if(regno<0) {Error(E_FORM,sp->op1,sp);
                flushRegs(sp,0,15); return;}
   regno2 = RegNumber(sp->op2b);
   *s = '\0';
 
   /* load indirect as in:  l  r4,8(r4)
                       or:  l  r4,0(r6)
      where 'base' register has known content  */
   if( regno2>=0
         && *(inreg[regno2])!= '\0'
      /* && !STORE(sp) */    ) {
      strcpy(s, inreg[regno2]);
      addIndRef( s, sp->ldstype, sp->op2a );
      }
 
   /* references symbol OR load indirect where base is unknown */
   else   {
      *s++ = sp->ldstype;
      *s++ = ':';
      formOp( s, s+INREGSIZE-2, sp->op2a, sp->op2b );
      }
}
 
 
/* forms an operand in 's' from parts in 'opa' and 'opb' */
static formOp( s, lims, opa, opb )
register char *s, *lims, *opa, *opb;
{
   lims -= 2;  /* leave room for sloppy checking! */
   if( opa != NULL)
      while (*opa && s<lims)  *s++ = *opa++;
   if( opb != NULL )   {
      *s++ = '(';
      while (*opb && s<lims)  *s++ = *opb++;
      *s++ = ')';
      }
   *s='\0';
}
 
                    /* --------------- */
 
/* add indirect reference indicator to string */
static addIndRef(s, ltype, offset)
register char *s;
register int ltype;
{
   static char lt[] = " x:";
 
   lt[1] = ltype;
   strcat( s, lt );   /* lt = " x:" where 'x' is ldstype */
   strcat( s, offset );
   strcat( s, "()" );
}
 
                    /* --------------- */
 
#define LTEMP 200
 
/* output to statement nodes, status of register contents */
traceLoadStatus(sp)
register struct snode *sp;
{
   register struct snode *new;
   char temp[LTEMP];
   register char *st;
   register int i;
   int l;
   static int wasempty = TRUE;
 
   /* make string which records remembered register contents */
   st = temp;
   *st = '\0';
   for (i=0; i<=15; i++ )
      if( st < temp+LTEMP-INREGSIZE )
         if(*inreg[i])
            if (strcmp(inreg[i], regvar[i]) != 0)  {
               if(temp[0] == '\0')  {
                  strcpy(temp,"|                   ");
                  st = temp + strlen(temp);
                  }
               l = strlen(inreg[i]) + 12;
               if (st+l >= temp+LTEMP)  break;
               sprintf( st, "  r%d: '%s';\0", i, inreg[i] );
               st = temp + strlen(temp);
               }
 
   /* put out "empty" trace only if just became empty */
   if(temp[0] != '\0')
      wasempty = FALSE;
   else
      if(!wasempty)   {
         strcpy(temp, "|                    r0-r15: (empty)");
         wasempty=TRUE;
         }
      else return;   /* nothing to put out */
 
   /* if possibly too much stuff, indicate
      that there might have been more */
   if(i<15)
      strcat( temp, "  ..." );
 
   /* allocate a new snode */
   new = NewNode();
   new->type = type_unimportant;
   if(new==NULL) return;
 
   /* add register trace to snode */
   new->rest = Myalloc(strlen(temp)+1);
   if(new->rest == NULL)  return;
   strcpy(new->rest, temp);
 
   /* add snode to chain */
   InsertNode(new, sp);
   MarkNew( new );
   PrintShortNode(new, "Added:");
}
