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

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

/* MROPT.C  -- Eliminate MR instructions and related junk

   External routines:
      MrOpt()    Main MR phase routine

*/


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

static struct snode * canDropMr();

/* main loop of MR instruction elimination */
MrOpt()
{
   while( oneMrOptPass() );
}


/* do one MrOpt pass */
static oneMrOptPass()
{
   register struct snode *sp;
   register int opnum, changed;

   if(DEBUG1)  fprintf(stderr,"\nStart MrOpt ---\n");
   sp = Root;
   changed = FALSE;
   while ( (sp = sp->next) != NULL)  {
      if ( UNIMPORTANT(sp))   continue;
      if ( EXFORM(sp) )
         {  sp = sp->next;  continue; }
      opnum = OPNUMBER(sp);
/*    if ( opnum == i_mr )  { 	tjm */
      if ( MR(sp) )  {
         PrintShortNode(sp, "MR found: ");
         changed |= dropMR(sp);
/*       }  else
/*    if ( opnum==i_subi || opnum==i_addi )   {		tjm */
/*       changed |= dropChange(sp);
/*       if( sp->op3a == NULL )  /* i.e. 2 operands */
/*          if( !UNIMPORTANT(sp) )  /* i.e. not deleted above */
/*             changed |= tryMergeWithGet( sp, opnum );
/*       }
*/
      }
   }
   return changed;
}

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

static dropMR(sp)
register struct snode *sp;
{
   register int regno, regno2;
   register struct snode *ahead;
   register int changed = FALSE;

   regno  = RegNumber(sp->op1);
   regno2 = RegNumber(sp->op2a);
   if( regno<0 || regno2<0 )   return FALSE;
   if( regno==0 && regno2==0 ) return FALSE; /* no-op (mr r0,r0) */

   /* if move FROM r0 don't optimize (else might use r0 as base!) */
   if( regno2==0 )             return FALSE;

   /* if move TO regvar from scratch follows GET into scratch,
      try to transform MR */
   if( REGVARREG(regno) && SCRATCHREG(regno2) )
      changed |= tformGet(sp, regno2);

   /* if not loading into a scratch reg, can't do anything */
   if( !SCRATCHREG(regno) )  return changed;

   /* if move to scratch simply to modify then move back, fix it */
   if( tformRegVarMod(sp) )        return TRUE;

   /* if move of regvar to scratch followed by inc/dec of scratch,
      move inc/dec as far forward as possible                    */
   if( REGVARREG(regno2) )
      changed |= tformMod( sp, regno );

   /* we have a scratch register; see if we can eliminate MR */
   ahead = canDropMr(sp, regno, regno2);
   if(ahead==NULL)  return changed;

   /* Success!  We can now drop MR & change registers */
   deleteMR( sp );
   if(sp != ahead)  {
      replaceMR( sp, ahead );
      InvalidateFregs( sp, ahead, regno2 );
      }
   return TRUE;
}

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


/* try to drop a change (addi/subi) to a register */
static dropChange(sp)
register struct snode *sp;
{
   register int regno;

   regno  = RegNumber(sp->op1);
   if(regno<0)                       return 0;

   /* if not changing a scratch reg, can't do anything */
   if( !SCRATCHREG(regno) )          return 0;
   if( !SETREG(sp) )                 return 0;
   PrintShortNode( sp, "dropChange looking at:" );

   /* See if can drop instr & change registers */
   if( regValueUsed(sp->next, regno) )     return 0;
   deleteMR( sp );
   return 1;
}


/* see if moving into a register var reg;      (a)  get  r5,0(r4)
   if not, look backwards for a load        sp==>   mr   r9,r5
   which loads the scratch reg we are
   moving from.  Transform (a) to (b)          (b)  get  r9,0(r4)
   which we know how to fix.                sp==>   mr   r5,r9
   ('sp' points to mr NOT to get;
   passed reg is mr's 2nd reg)
*/
static tformGet( sp, regno2 )
register struct snode *sp;   /* points to MR instruction */
register int regno2;         /* 2nd reg of MR */
{
   register struct snode *back;

   back = sp;
   while( UNIMPORTANT(back = back->last) );
   if( !LOAD(back) )                     return FALSE;
   if( RegNumber(back->op1) != regno2 )  return FALSE;

   back->op1 = sp->op1;
   MarkChanged( back );

   sp->op1   = sp->op2a;
   sp->op2a  = back->op1;
   MarkChanged( sp );
   PrintShortNode( sp, "tformGet: " );

   return TRUE;
}


/* If sequence has form of    (a)  mr     r4,r11
   incr of reg var using           addi   r4,1    (some mod to r4)
   scratch reg as in (a),          mr     r11,r4
   modify to (b).             (b)  addi   r11,1
                                   mr     r4,r11
*/
static int tformRegVarMod(sp)
register struct snode * sp;
{
   register int r, r2;
   register struct snode *first, *middle;

/* if ( OPNUMBER(sp) != i_mr )         return FALSE; 	tjm */
   if ( !MR(sp) )                      return FALSE;
   r  = RegNumber(sp->op1);    /* register being changed */
   r2 = RegNumber(sp->op2a);
   if( r<0 || r2<0 )                   return FALSE;
   if ( !SCRATCHREG(r) )               return FALSE;
   if ( !REGVARREG(r2) )               return FALSE;
   first = sp;

   sp = NextImportant( sp );
   if ( sp == NULL )                   return FALSE;
   if ( HASLABEL(sp) )                 return FALSE;
   if ( UNKNOWN(sp) )                  return FALSE;
   if ( RegNumber(sp->op1) != r )      return FALSE;
   if ( !SETREG(sp) )                  return FALSE;
   middle = sp;

   sp = NextImportant( sp );
   if ( sp == NULL )                   return FALSE;
   if ( HASLABEL(sp) )                 return FALSE;
/* if ( OPNUMBER(sp) != i_mr )         return FALSE;	tjm */
   if ( !MR(sp) )                      return FALSE;
   if ( r  != RegNumber(sp->op2a) )    return FALSE;
   if ( r2 != RegNumber(sp->op1) )     return FALSE;

   /* found a move--mod--move sequence that we can fix */
   deleteMR( first );
   middle->op1   =  sp->op1;
   MarkChanged( middle );
   sp->op1   =  first->op1;
   sp->op2a  =  first->op2a;
   MarkChanged( sp );
   PrintShortNode( sp, "tformRegVarMod: " );
   return TRUE;
}


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

/* We are moving a value from
   a reg var to a scratch reg            mr   r3,r10
   and then changing scratch;            addi r3,1
   move change as far
   forward as possible.
*/
static tformMod( sp, regno )
register struct snode *sp;   /* points to MR instruction */
register int regno;          /* first reg of MR */
{
   register struct snode *ahead, *old, *new;
   register int n;

   old = ahead = NextImportant( sp );
   if( ahead==NULL )                     return FALSE;
/* if( OPNUMBER(ahead) != i_addi &&
/*     OPNUMBER(ahead) != i_subi )       return FALSE;		tjm */
   if( OPNUMBER(ahead) != i_ai &&
       OPNUMBER(ahead) != i_si )         return FALSE;
   if( RegNumber(ahead->op1) != regno )  return FALSE;

   /* search ahead to see how far instr can move */
   n = 0;
   for( ahead=sp->next;  ahead!=NULL;  ahead=ahead->next ) {
      if( UNIMPORTANT(ahead) )       continue;
      if( BRANCH(ahead) )            break;
      if( HASLABEL(ahead) )          break;
      if( refsReg(ahead,regno) )     break;
      n += 1;
      }
   if( ahead==NULL )                     return FALSE;
   if( n == 0 )                          return FALSE;

   new = CopyNode( old );
   InsertNode( new, ahead->last );
   MarkDeleted( old );
   PrintShortNode( new, "tformMod moved: " );

   return TRUE;
}

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


/* Look for SUBI/ADDI followed by GETx/PUTx    (a)  addi  r4,1
   as in (a).  If found, and if addi/subi           get   r2,0(r4)
   target is not used beyond the GETx/PUTx,
   delete the SUBI/ADDI and fold operation
   into the offset of the GETx/PUTx (b).       (b)  get   r2,1(r4)
   Return TRUE if a change made.
*/
tryMergeWithGet(sp, opnum)
register struct snode *sp;
int opnum;
{
   register int regno;
   register struct snode *ahead;
   struct snode *new;
   char temp[100];
   char *s;
   static char fmtplus[]  = "%s+%s";
   static char fmtminus[] = "%s-%s";
   static char fmtaiminus[] = "%s%s";

   /* if addi/subi is to a register variable, cannot delete it */
   regno = RegNumber(sp->op1);
   if( !SCRATCHREG(regno) )               return FALSE;

   /* find the next interesting instruction */
   ahead = NextImportant( sp );
   if( ahead==NULL )                      return FALSE;
   PrintShortNode( ahead, "tryMergeWithGet looking ahead at:" );

   /* see if next instruction is a load or store */
   if( REFTYPE(ahead) )
      if( REFIMMED(ahead) )               return FALSE;

   /* see if it loads based on our register; if not, exit */
   if( RegNumber(ahead->op2b) != regno )  return FALSE;

   /* if register value is used beyond GETx/PUTx, cannot merge.
      (if load itself replaces the register, don't look ahead) */
   if( RegNumber(ahead->op1) != regno )
      if( regValueUsed(ahead->next, regno) )
                                          return FALSE;

   /* delete the addi/subi */
   deleteMR( sp );

   /* merge subi/addi operand into load/store */
/* sprintf( temp, (opnum==i_addi) ? fmtplus : fmtminus,
/*          ahead->op2a, sp->op2a );			tjm */
   if (opnum == i_ai) {
      if (atoi(sp->op3a) < 0 )
       sprintf( temp, fmtaiminus, ahead->op2a, sp->op3a);
      else
       sprintf( temp, fmtminus, ahead->op2a, sp->op3a);
   }
   else
       sprintf( temp, fmtminus, ahead->op2a, sp->op3a);

   s = Myalloc( strlen(temp) );
   if( s==NULL )  {
      Error( E_STORAGE, "in TryMergeWithGet()", sp );
      exit();
      }
   new = CopyNode( ahead );
   InsertNode( new, ahead );
   deleteMR( ahead );
   new->op2a = s;
   strcpy( s, temp );
   return TRUE;
}


/* Look ahead to see if the value of a register is further used.
   Return TRUE is used or we cannot tell,
   return FALSE if not further referenced.
*/
static regValueUsed(sp, regno)
struct snode *sp;
int regno;
{
   register struct snode *ahead;
   int n;

   if(sp==NULL)  return TRUE;
   for( ahead=sp;  ahead!=NULL;  ahead=ahead->next )  {
      PrintShortNode( ahead, "regValueUsed looking at:" );

      /* if a _freg, and if register is free, we know not used */
      if( FREGS(ahead) )
         if( REGFREE(ahead,regno) )           return FALSE;

      /* check for junk (must follow FREG test above)  */
      if( UNIMPORTANT(ahead) )                continue;

      /* look for baddies */
/*    if( HASLABEL(ahead) )                   return TRUE;  */
      if( UNKNOWN(ahead) )                    return TRUE;

      /* if we have a balr which reloads our register
         we know register is not further used.   */
      if( BAL(ahead) )
         if( regno==RegNumber(ahead->op1) )   return FALSE;
         else                                 return TRUE;

      /* if a branch, return FALSE always */
      if( BRANCH(ahead) )                     return FALSE;

      /* see if this instruction references our register.
         If so, if register is REPLACED then search is successful.
         If changed, then search known to have failed  */
      if( (n=refsReg(ahead,regno)) > 0 )  {
         if( n==1 && LOAD(ahead) )
            if( regno!=RegNumber(ahead->op2b) )  return FALSE;
/*       if( n==1 && OPNUMBER(ahead)==i_mr ) 	tjm */
         if( n==1 && MR(ahead) )
            if( regno!=RegNumber(ahead->op2a) )  return FALSE;
         return TRUE;
         }
      }
   return TRUE;
}



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

/* Look ahead for things which prevent elimination of MR.
   If found, return NULL.
   Else we know scope of use of target and source registers
   are such that the MR can be eliminated.  We thus
   return the snode which is at or beyond the last reference
   to the source or target of the subject MR.
*/
static struct snode *canDropMr(sp, regno, regno2)
struct snode *sp;
int regno, regno2;
{
   register struct snode *ahead;
   struct snode *ret;
   register int r, r2;

   if(sp==NULL)  return NULL;

   for( ahead=sp->next;  ahead!=NULL;  ahead=ahead->next )  {

      /* if a _freg, and if register is free,
         we know scope and are successful */
      if( FREGS(ahead) )
         if( REGFREE(ahead,regno) )           return ahead;

      /* check for junk (must follow FREG test above)  */
      if( UNIMPORTANT(ahead) )                continue;
      PrintShortNode( ahead, "Looking ahead at:" );

      /* look for baddies */
      if( HASLABEL(ahead) )                   return NULL;
      if( UNKNOWN(ahead) )                    return NULL;

      /* if we have a balr which branches to a target given by
         first operand of MR, assume register not further used. */
      if( OPNUMBER(ahead)==i_balr ||
          OPNUMBER(ahead)==i_balrx)
         if( regno==RegNumber(ahead->op2a) )  return ahead;
         else                                 return NULL;

      /* if any branch always return NULL */
      if( BRANCH(ahead) )                     return NULL;

      /* if SOURCE register is changed, we can't remove the mr          */
      /*   (unless TARGET is not used afterwards)                       */
      r  = RegNumber(ahead->op1);
      if( r==regno2 && SETREG(ahead) )  {
         if( regValueUsed(ahead, regno) )     return NULL;
         else                                 return ahead;
         }

      /* Now check if the source of the mr is r0, and ahead
         uses the target of the mr as a base register (op2a) or
         as op3 (in cas).  If so, we can not drop this mr.  */
      r2 = RegNumber(ahead->op2b);
      if (regno2 == 0) {
         if (regno == r2 ||
             regno == RegNumber(ahead->op3a))  return NULL;
         }

      /* see if this instruction references mr TARGET register.
         If so, if register is REPLACED then search is successful.
         If changed, then search known to have failed  */
      if( r==regno )  {
         /* if( LOAD(ahead) && (r==r2) )      return ahead; */
         if( repReg(ahead)  )                 return ahead;
         if( SETREG(ahead) )                  return NULL;
         }
      }
   return NULL;
}

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

/* Determine if an instruction references a given register.
   If so, return indicator of which operand first references it.
   Else return a zero
*/
static int refsReg(sp, n)
register struct snode *sp;
register int n;
{
   register int rc = 0;
   if( sp==NULL || sp->op1==NULL ) rc = 0;  else
   if( OPTPSEUDO(sp) )             rc = 0;  else
   if( RegNumber(sp->op1)  == n )  rc = 1;  else
   if( sp->op2b == NULL &&
       RegNumber(sp->op2a) == n )  rc = 2;  else
   if( RegNumber(sp->op2b) == n )  rc = 3;  else
   if( sp->op3b == NULL &&
       RegNumber(sp->op3a) == n )  rc = 4;  else
   if( RegNumber(sp->op3b) == n )  rc = 5;
   if(DEBUG1)  fprintf(stderr,"Reg %d is operand %d\n", n, rc);
   return rc;
}
                    /* --------------- */

/* tests for replacement of target register versus
   simply modifying target.
   Returns TRUE if target is replaced.
   This is considered a replacement:    get  r2,4(r2)
   Returns FALSE if is or might be modified
*/
static int repReg(sp)
register struct snode *sp;
{
   if( ! SETREG(sp) )              return FALSE;
   if( LOAD(sp) )                  return TRUE;
   if( OPNUMBER(sp) == i_balr)     return TRUE;
   if( OPNUMBER(sp) == i_balrx)    return TRUE;
/* if( OPNUMBER(sp) == i_mr )      return TRUE; 	tjm */
   if( MR(sp) )                    return TRUE;
   return FALSE;

   /* instruction specific tests can make this
      more accurate.  For example:   CAL  r2,r3,r4,4
      should return TRUE since R2 is replaced, not changed
   */
}

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

/* loop through a range of instruction nodes and replace all
   references to the target register of the MR instruction at 'sp'
   with references to its source register
*/
static replaceMR(old, ahead)
register struct snode *old;
struct snode *ahead;
{
   register struct snode *sp, *new;
   register int regno, n;
   int stop = FALSE;

   /* get MR instruction target register number */
   regno = RegNumber(old->op1);

   /*  loop through the range  */
   for( sp=old->next;  stop==FALSE;  sp=sp->next )  {

      /* see if this is our last node;  must check now since
         we might add another node and move on to it       */
      stop = sp==ahead;
      if( sp == NULL )         return;

      /* skip junk and 'deleted' nodes */
      if( UNIMPORTANT(sp) )    continue;

      /* loop while the instruction refers to the Mr target;
         change the reference to be the MR source register  */
      while ( (n=refsReg(sp,regno)) != 0 )  {

         /* first some special cases: indirect loads, balrs & others
            may reference the register in several operands.  We must
            not change the first.   This code forces it to happen.
            (These cases happen on last changeable instruction)   */
         if( n==1 ) {
            if( LOAD(sp) )
               if( RegNumber(sp->op1) == RegNumber(sp->op2b) )
                  /* indirect load; change only op2 */
                  n = 3;
               else break;  /* already got it */
            if( OPNUMBER(sp) == i_balr ||
                OPNUMBER(sp) == i_balrx )
               if( RegNumber(sp->op2a) == regno )
                  n = 2;
               else break;   /* already got it */
            /* may have MR or CAL or ?? which changes target;
               it may also reference register. change reference only */
            if( SETREG(sp) )  {
               if( RegNumber(sp->op2a)==regno )  n = 2; else
               if( RegNumber(sp->op2b)==regno )  n = 3; else
               if( RegNumber(sp->op3a)==regno )  n = 4; else
               if( RegNumber(sp->op3b)==regno )  n = 5; else
                  break;      /* already got it */
                  }
            }
         PrintShortNode(sp, "About to replace:" );

         /* change the node by making a copy and marking the old
            one as deleted;  then fixup the new one            */
         new = CopyNode(sp);
         InsertNode(new, sp);
         MarkDeleted( sp );
         sp = new;
         switch (n)  {
            case 1:   sp->op1  = old->op2a;   break;
            case 2:   sp->op2a = old->op2a;   break;
            case 3:   sp->op2b = old->op2a;   break;
            case 4:   sp->op3a = old->op2a;   break;
            case 5:   sp->op3b = old->op2a;   break;
            }
         PrintShortNode(sp, "Just modified:  " );
         }
      }
}

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

/* delete an instruction */
static deleteMR(sp)
register struct snode *sp;
{
   MarkDeleted( sp );
   c.mrdeletes += 1;
}
