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

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

/* EXFORM.C
 
   External routines:
       BalrOpt()     Main BALR->BALRX optimizer
 
 
 
   BALR TO BALRX OPTIMIZATION
 
   The optimizer moves instructions behind BALRs and changes them
   to BALRX.  Here is an outline of how it decides what to move.
 
   o   The main loop scans through the program looking for BALRs.
       When it finds one it then starts scanning backwards as long
       as:
 
       -   it cannot move the instruction.
       -   it CAN continue scanning
 
   o   If an instruction is found that can be moved, it is moved
       (copied actually) and flags set so that the output program
       shows enough to tell what happened later.
 
   o   An instruction cannot be moved when:
 
       -   It's type or effects are unknown
       -   It is flagged as 'unimportant' (i.e.  many pseudo ops)
       -   It has a label.
       -   It does NOT use registers.
       -   It sets the condition code.
       -   It is not a 4 byte a two byte instruction.
           Two byte instructions are moved and padded with a MR
           R0,R0.  As a special case, the GET instruction is moved
           but changed to a L instruction.
       -   Any operand of the instruction matches ANY operand of
           any instruction forward to (and including) the BALR.
       -   The instruction is itself behind a B--X instruction.
 
   o   Scanning can continue except when:
 
       -   The  instruction type  is  dangerous; this  includes
           some pseudo operations like .using.
       -   The instruction sets the condition code.
       -   The instruction is a branch (any kind including BALR).
       -   The instruction has a label.
*/
 
#include "stdio.h"
#include "opt.h"
#include "inst.h"
 
#define FAST_OK  TRUE
#define SHORT_OK TRUE
 
 
/* Change BALR to BALX */
 
BalrOpt()
{
   register struct snode *ibalr, *prev, *new, *hold;
   struct opStat *opStatLoad, *opStatBalrx, *OpcodeEval(), *opStatStore;
   struct snode *scanBack();
 
   opStatBalrx = OpcodeEval("balrx");  /* find opstat for BALRX */
   opStatLoad  = OpcodeEval("l"    );  /* find opstat for L     */
   opStatStore = OpcodeEval("st"   );  /* find opstat for ST    */
 
   ibalr = Root;
   while ( (ibalr = ibalr->next) != NULL)  {
 
      if (UNIMPORTANT(ibalr) )                  continue;
      if (ibalr->opcode->opnumber != i_balr)    continue;
      if(DEBUG1)  PrintShortNode( ibalr, "Found BALR:");
 
      /* scan backwards looking for something to move;
         will take fast or slow,   long or short  */
      prev = scanBack(ibalr->last, ibalr, FAST_OK, SHORT_OK);
      if (!prev)  continue;
 
      /* may have found fast instruction;
         if so, try for slow one */
      if( FASTINSTR(prev) )   {
         hold = scanBack(prev->last, ibalr, !FAST_OK, SHORT_OK );
         if(hold)  prev = hold;
         }
 
      /* may have found short/slow instruction;
         if so, try for long/slow one */
      if( SHORTINSTR(prev) )   {
         hold = scanBack(prev->last, ibalr, !FAST_OK, !SHORT_OK );
         if(hold)  prev = hold;
         }
 
      /* Success!  Now, move the instruction (by creating a new
         node and marking the old node as deleted).  Pad with
         a no-op if the moved instruction is short.  Change the
         opcode of the BALR to BALRX  */
      new = CopyNode(prev);
      InsertNode(new, ibalr);
      ibalr->opcode = opStatBalrx;
      MarkChanged( ibalr );
      ibalr->type  = opStatBalrx->optype;
      ibalr->ldstype = opStatBalrx->opldstype;
      MarkMoved( prev );
      c.balrmoves += 1;
/*    if( OPNUMBER(new) == i_get )				tjm */
/*       new->opcode = opStatLoad;  /* Change GET to L */
/*    if( OPNUMBER(new) == i_put )
/*       new->opcode = opStatStore;  /* Change PUT to ST */
      if (SHORTINSTR(prev)) {
/*       GenRR( "mr", 0, 0, new ); 	tjm */
         GenRRR( "cas", 0, 0, 0, new );
         new->next->modby |= who_balr;
         c.balrmrgen += 1;
         }
      if(DEBUG1)  PrintShortNode(new, "Added node:");
      }
}
 
/* Scan backwards looking for an instruction that can be moved.
   If a node cannot be moved, continue to loop if it's ok to do so
*/
static struct snode *scanBack(sp, ibalr, fastOK, shortOK )
register struct snode *sp, *ibalr;
register int fastOK, shortOK;
{
   register int i;
   while( sp!=NULL &&
          !(i=canMove(sp, ibalr, fastOK, shortOK )) &&
          okToContinue(sp) )
      sp = sp->last;
   return i ? sp : NULL;
}
 
 
/* see if the instruction at 'sp' can be moved behind
   the BALR at 'where'.  (See prolog for details).
*/
static canMove(sp, where, fastOK, shortOK )
register struct snode *sp;    /* an instruction ahead of 'where' */
register struct snode *where; /* a balr which might become a balx*/
register int fastOK, shortOK;
{
   register struct snode  *ip;
   register int i;
 
   if(DEBUG1)  PrintShortNode( sp, "See if canMove:");
   /* check for known show stoppers */
   if ( UNKNOWN(sp) )         return FALSE;
   if(DEBUG2)  fprintf(stderr,"unk ");
   if ( UNIMPORTANT(sp) )     return FALSE;
   if(DEBUG2)  fprintf(stderr,"unimp ");
   if ( HASLABEL(sp) )        return FALSE;
   if(DEBUG2)  fprintf(stderr,"laslab ");
/* if ( !USEREG(sp) )         return FALSE; */
/* if(DEBUG2)  fprintf(stderr,"usereg ");    */
   if ( SETCC(sp) )           return FALSE;
   if(DEBUG2)  fprintf(stderr,"setcc ");
   if ( BRANCH(sp) )          return FALSE;
   if(DEBUG2)  fprintf(stderr,"br ");
   if ( OPNUMBER(sp) != i_get && OPNUMBER(sp) != i_put )  {
      if( !LONGINSTR(sp) &&
          !SHORTINSTR(sp) )
         return FALSE;
      if( (FASTINSTR(sp)  && !fastOK)  ||
          (SHORTINSTR(sp) && !shortOK)     )
         return FALSE;
      }
   if(DEBUG2)  fprintf(stderr," long|short|getput\n");
 
   /* loop through range 'sp' to 'where' looking for a match of
      any operand of any instruction in the range with 'sp'.
      Any match and we cannot move 'sp'                         */
   for (ip=sp->next;  (!(i=compOp(sp,ip)))
                      && (ip!=where);     ip=ip->next)
      ;
   if(!i)  if(DEBUG2)  fprintf(stderr,"   no operands match\n");
 
   /* found one; but, it might be behind a BALRX or BrrX */
   if( sp->last!=NULL )  {
      if( EXFORM(sp->last) )   return FALSE;
      }
   if(!i)  if(DEBUG1)  fprintf(stderr," CAN MOVE!!");
 
   return( !i );
}
 
 
 
/* Compare operands of an instruction
   with those of another instruction.
   Return TRUE if any match
*/
 
#define COMPS(a,b)   ((b)!=NULL) ? strcmp(a,(b))==0 : FALSE
 
static compOp(p1, p2)
register struct snode *p1;   /* an instruction */
register struct snode *p2;   /* some other instruction   */
{
   if( UNIMPORTANT(p2) )  return FALSE;
 
   /* (not 'looped' or 'procedured' for speed) */
   if( p1->op1 != NULL ) {
      if( COMPS(p1->op1,  p2->op1 ) )   goto rtrue;
      if( COMPS(p1->op1,  p2->op2a) )   goto rtrue;
      if( COMPS(p1->op1,  p2->op2b) )   goto rtrue;
      if( COMPS(p1->op1,  p2->op3a) )   goto rtrue;
      if( COMPS(p1->op1,  p2->op3b) )   goto rtrue;
      }
 
   if( p1->op2a != NULL ) {
      if( COMPS(p1->op2a, p2->op1 ) )   goto rtrue;
      if( COMPS(p1->op2a, p2->op2a) )   goto rtrue;
      if( COMPS(p1->op2a, p2->op2b) )   goto rtrue;
      if( COMPS(p1->op2a, p2->op3a) )   goto rtrue;
      if( COMPS(p1->op2a, p2->op3b) )   goto rtrue;
      }
 
   if( p1->op2b != NULL ) {
      if( COMPS(p1->op2b, p2->op1 ) )   goto rtrue;
      if( COMPS(p1->op2b, p2->op2a) )   goto rtrue;
      if( COMPS(p1->op2b, p2->op2b) )   goto rtrue;
      if( COMPS(p1->op2b, p2->op3a) )   goto rtrue;
      if( COMPS(p1->op2b, p2->op3b) )   goto rtrue;
      }
 
   if( p1->op3a != NULL ) {
      if( COMPS(p1->op3a, p2->op1 ) )   goto rtrue;
      if( COMPS(p1->op3a, p2->op2a) )   goto rtrue;
      if( COMPS(p1->op3a, p2->op2b) )   goto rtrue;
      if( COMPS(p1->op3a, p2->op3a) )   goto rtrue;
      if( COMPS(p1->op3a, p2->op3b) )   goto rtrue;
      }
 
   if( p1->op3b != NULL ) {
      if( COMPS(p1->op3b, p2->op1 ) )   goto rtrue;
      if( COMPS(p1->op3b, p2->op2a) )   goto rtrue;
      if( COMPS(p1->op3b, p2->op2b) )   goto rtrue;
      if( COMPS(p1->op3b, p2->op3a) )   goto rtrue;
      if( COMPS(p1->op3b, p2->op3b) )   goto rtrue;
      }
 
   return FALSE;
 rtrue:
   return TRUE;
}
 
 
/* while scanning back thru instruction stream,
   make sure it is o.k. to continue scanning
*/
static okToContinue(sp)
register struct snode *sp;
{
   if (!UNIMPORTANT(sp)) {
      if (UNKNOWN(sp))      return FALSE;
      if (SETCC(sp))        return FALSE;
      if (BRANCH(sp))       return FALSE;
      if (HASLABEL(sp))     return FALSE;
      }
   if(DEBUG1) fprintf(stderr,"is okToContinue\n");
   return TRUE;
}
