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

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

/* JUMPOPT.C


   External routines:
      JumpOpt()     Main routine of jump optimization



   BRANCH OPTIMIZATIONS

   The branch optimizer does several separate optimizations.  It
   uses a table of branch labels which contains the label, a
   pointer to the statement node at which it is defined, and the
   number of references to the label.  The table also chains
   together all nodes which reference the label.  Only labels
   with alphabetic first characters are considered; underscore
   and dot are used as first characters for special labels such
   as function names.

   References can occur in the first or second operand of any
   statement node.  A flag in the opcode table indicates which
   statements might have such a reference.  It is assumed that
   references to labels to which branches can occur will never be
   made from a literal or from other than the first two operands
   of a .long, for example.

   ROPT guarantees that there will be no statement node with both
   a label and an 'interesting' instruction.

   The following optimizations are performed:

   o   Delete branches to labels which follow immediately.
   o   Unwind branches around branches.
   o   Remove branches to branches.
       In general all references to a label are replaced by
       references to the target of the second branch.
   o   Remove dead code; that is code which follows unconditional
       branches (except BAL) and which preceeds a label.
   o   With branches being deleted, it is thus possible to delete
       labels to which they referred.  This helps some other
       optimizations work over a larger section of code.
   o   Move "isolated" blocks of code which are branched to from
       one place.  Isolated blocks start with a label and end with
       an unconditional branch.  Their position is thus arbitrary
       and can be moved to the place of an unconditional branch
       to them.

*/

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


JumpOpt()
{
   register int change, ch;

   if(DEBUG1)  ListLabels();

   do {
      change = 0;
      change += ch=brToNext();   if(DEBUG1&&ch)  ListLabels();
      change += ch=brAround();   if(DEBUG1&&ch)  ListLabels();
      change += ch=brToBr();     if(DEBUG1&&ch)  ListLabels();
      change += ch=deadCode();   if(DEBUG1&&ch)  ListLabels();
      change += ch=unwind();     if(DEBUG1&&ch)  ListLabels();
      change += ch=checkUnRef(); if(DEBUG1&&ch)  ListLabels();
      }
        while( change );           /* and repeat all if any worked */
}

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

/* see if there are any unreferenced labels.
  If so, delete the label.
  Only labels which start with alphabetic characters
  are deleted;  all labels which start with a special
  character are things like function names             */
static checkUnRef()
{
   register struct snode *sn;
   register struct label *lab;
   int changes = 0;

   if(DEBUG1)  fprintf(stderr,"Start checkUnRef ----------\n");
   sn = FunctLoc;
   while ( (sn = sn->next) != EFunctLoc)  {
      if( UNIMPORTANT(sn) )  continue;
      if( HASLABEL(sn) )    {
         lab = sn->lablock;
         if(lab != NULL)
            /* labels starting with alpha are local  */
            /* others are things like function names */
            if( isalpha(*(lab->lname)) )
               if( lab->refcount == 0 ) {
                  DeleteLabel(sn);
                  c.unreflab += 1;
                  changes += 1;
                  }
            }
      }
   return changes;
}


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

/* Detect and fix branches to branches.
   For example, the code at (a) is        (a)  be x      (b)  be y
   transformed to the code at (b).             ...            ...
   The branch branched to is NOT            x:             |x:
   deleted (control might drop thru)           b  y           b  y
   but the label ahead of it is deleted
   if possible.
*/
static brToBr()
{
   register struct snode *sn, *ahead, *node, *new, *nextnode;
   int changes = 0;

   if(DEBUG1)  fprintf(stderr,"Start brToBr ----------\n");
   sn = FunctLoc;
   while ( (sn = sn->next) != EFunctLoc)  {

      /* look first for labels;  continue if this isn't one */
      if( UNIMPORTANT(sn) )                         continue;
      if( !HASLABEL(sn) )                           continue;

      /* now look ahead for the next interesting statement */
      ahead = sn->next;
      while( ( HASLABEL(ahead) || UNIMPORTANT(ahead) )
             && ahead!=NULL )
         ahead = ahead->next;
      if( ahead == NULL )                           break;

      /* if it's not a ucbranch, we don't care;  if it is,
         we then care if the branch target matches our
         label  (i.e. branch to here which we leave alone),
         and if it is a possible statement label (alpha) */
      if( !UCBRANCH(ahead) )                        continue;
      if( BAL(ahead) )                              continue;
      if( Labcmp(sn->labels, ahead->op1) )          continue;
      if( !isalpha(*(sn->labels)) )                 continue;
      PrintShortNode(ahead, "brToBr found:");

      /* found label with ucbranch as 'next' thing;
         fixup the 'world' so that no one branches to the label
         but branches to the target of the ucbranch         */
      for( node=sn->lablock->lchain;  node!=NULL;  node=nextnode) {

         /* get pointer to next label in chain before it's gone */
         nextnode = node->labsame;

         /* change label: copy node and mark old one 'deleted' */
         new = CopyNode(node);
         InsertNode(new, node);

         /* change either op1 or op2 as appropriate */
         if( Labcmp(new->op1,  sn->labels) )
            new->op1 = ahead->op1;
         else if( Labcmp(new->op2a, sn->labels) )
            new->op2a = ahead->op1;
         else fprintf(stderr,
                     "In brToBr, label %s not found to replace.\n",
                     sn->labels);

         /* add reference to new label into label table &
            do other housekeeping                         */
         LabNewRef(new);
         MarkChanged(new);
         c.jumptolabels += 1;
         PrintShortNode( node, "brToBr changed:" );
         PrintShortNode( new, "   to:" );
         LabUnRef(node);
         MarkDeleted(node);
         changes += 1;
         }

      /* if our label is now unreferenced (as it should be)
         then 'delete' the label node                       */
      if(sn->lablock->refcount == 0)
         DeleteLabel(sn);
      c.jumptojumps += 1;
      }
   return changes;
}




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

/* Detect and fix branches to the next instruction.
   This optimization will fail to delete a branch *+n
   to the next instruction because it expects the label in op1.
 */

static brToNext()
{
   register struct snode *ahead, *sn;
   int changes = 0;
   if(DEBUG1)  fprintf(stderr,"Start brToNext ----------\n");

   for( sn=FunctLoc;  sn!=EFunctLoc;  sn=sn->next )  {
      if( UNIMPORTANT(sn) )                         continue;
      if( !BRANCH(sn) )                             continue;
      if( BAL(sn) )                                 continue;
      ahead = NextImportant(sn);
      if( ahead == NULL )                           continue;
      if( !HASLABEL(ahead) )                        continue;
      if( !Labcmp(sn->op1, ahead->labels) )         continue;
      PrintShortNode( sn, "brToNext found:" );

      /* found branch to very next important line; delete branch */
      /* (if label becomes unreferenced, it'll be deleted later) */
      LabUnRef(sn);
      MarkDeleted(sn);
      c.jumpdeletes += 1;
      changes += 1;
      }
   return changes;
}


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

/* procedures to detect and fix conditional branches
   around unconditional branches.  Transform (a) to (b)

   (a)     bne  L249             (b)     be   L248
           b    L248
      L249:
*/

static brAround()
{
   register struct snode *ucbr, *ahead, *sn, *new;

   struct opStat *revOpcode();
   register struct opStat *op;
   int changes = 0;

   if(DEBUG1)  fprintf(stderr,"Start brAround ----------\n");
   sn = FunctLoc;
   while ( (sn = sn->next) != EFunctLoc)  {

      /* look for a branch; then scan ahead for the next
         interesting instruction; if not a cbranch, continue */
      if( UNIMPORTANT(sn) )                         continue;
      if( !CBRANCH(sn) )                            continue;
      ahead = sn->next;
      while( UNIMPORTANT(ahead) && ahead!=NULL )
         ahead = ahead->next;
      if( ahead == NULL )                           break;
      if( !UCBRANCH(ahead) )                        continue;
      ucbr = ahead;

      /* now look for a label to which first branch might go */
      ahead = NextImportant(ahead);
      if( ahead == NULL )                           break;
      if( !HASLABEL(ahead) )                        continue;
      if( !Labcmp(sn->op1, ahead->labels) )         continue;
      PrintShortNode(sn, "brAround: ");
      PrintShortNode(ahead, "label is:");

      /* found branch around ucbranch which can be fixed */

      /* Reverse the conditional branch opcode (eg: be->bne) */
      op = revOpcode( sn );
      if( op==NULL )                                continue;

      /* make a new node (will 'delete' old one shortly)  */
      new = CopyNode(sn);

      /* Delete label references; then 'delete' the old stmt */
      LabUnRef(sn);
      MarkDeleted(sn);

      /* insert the new node in the chain and fix it up */
      InsertNode(new, sn->last);
      new->opcode = op;
      new->op1 = ucbr->op1;
      new->rest = NULL;  /* drop comments */
      LabNewRef(new);    /* add operand label to label table */

      /* 'delete' the unconditional br & its label table entry */
      LabUnRef(ucbr);
      MarkDeleted(ucbr);

      /* collect some statistics */
      c.jumpdeletes += 1;
      changes += 1;
      }
   return changes;
}


/* reverse a condition ('e' becomes 'ne', etc)
   (called only by revOpcode below)              */
static char *revCond(cc)
register char *cc;
{
   static char *cclist[] = { "",
       "l",  "nl",
       "m",  "nm",
       "h",  "nh",
       "le", "h",
       "p",  "np",
       "e",  "ne",
       "eq", "ne",
       "z",  "nz",
       "o",  "no",
       "tb", "ntb",
       "c0", "nc0",
        0,    0 };
     register int i;

   for(i=1; cclist[i]!=NULL; i++)
      if(strcmp(cc,cclist[i]) == 0)  {
         if( i&1 )  return(cclist[i+1]);
             else   return(cclist[i-1]);
          }
   return NULL;
}

/* reverse the condition of a conditional branch opcode.
   Returns pointer to opcode table for reversed opcode (or NULL) */
static struct opStat *revOpcode(sn)
register struct snode *sn;
{
   struct opStat *OpcodeEval();
   char temp[10];
   register char *s;

   s = revCond( (sn->opcode->opname)+1 );
   if( s==NULL )  return NULL;
   temp[0] = *(sn->opcode->opname);
   strcpy( &temp[1], s );
   if(DEBUG2) fprintf(stderr,"revOpcode made %s into %s\n",
              sn->opcode->opname, temp);
   return OpcodeEval( temp );  /* find opstat for new opcode */
}


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

/* Detect and fix dead-code of the form:         b   x
                                                  ..dead code..
                                           label:
   Deletes everything from after the
   ucbranch to the label or to _efunct
*/
static deadCode()
{
   register struct snode *ahead, *sn;
   int changes=0, ch;

   if(DEBUG1)  fprintf(stderr,"Start deadCode ----------\n");
   sn = FunctLoc;
   while ( (sn = sn->next) != EFunctLoc)  {

      /* scan until an unconditional branch is found */
      if( UNIMPORTANT(sn) )                         continue;
      if( !UCBRANCH(sn) )                           continue;
      if( BAL(sn) )                                 continue;

      /* delete dead code, remove br targ from label table, ... */
      ch = 0;
      for( ahead = NextImportant(sn);
              ahead!=NULL
              && !HASLABEL(ahead)
              && OPNUMBER(ahead)!=i_efunct;
           ahead = NextImportant(ahead) ) {

         if( !PSEUDO(ahead) ) {
            PrintShortNode(sn, "deadCode: ");
            if( BRANCH(ahead) )
               LabUnRef(ahead);
            MarkDeleted(ahead);
            ch += 1;
            }
         } /*end for */
      if( ch ) {
         changes += 1;
         c.deadblocks += 1;
         c.deadinst += ch;
         }
      }
   return changes;
}

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


/* look for code like (a)     (a) a: b    x      (b) a:
   and transform to code             ...             x: ...
   like at (b).  The part            b    ---           b    abc
   which follows x: is moved      x: ...                ...
   to the branch at a: and           b    abc           b    ---
   the branch thus can be
   deleted.
*/
static unwind()
{
   register struct snode *sn, *ahead, *ahead2;
   struct label *lab;
   int n;
   int changes = 0;

   if(DEBUG1)  fprintf(stderr,"Start unwind ----------\n");
   sn = FunctLoc;
   while ( (sn = sn->next) != EFunctLoc)  {

      /* look first for branches;  continue if this isn't one */
      if( UNIMPORTANT(sn) )                         continue;
      if( !UCBRANCH(sn) )                           continue;
      if( BAL(sn) )                                 continue;
      PrintShortNode(sn, "unwind looking at:");

      /* now look at target of the branch;
         if just one reference we look further */
      lab = sn->lablock;
      if( lab==NULL )                               continue;
      if( lab->refcount != 1 )                      continue;
      if(DEBUG1)  fprintf(stderr, " label found\n");

      /* scan backwards from target for an unconditional branch */
      ahead = lab->ldef;
      if(DEBUG1)  fprintf(stderr,
         " ldef = %04x;  lab = %04x\n", ahead, lab );
      if( ahead==NULL )                             continue;
      ahead = ahead->last;
      while( ahead!=NULL && UNIMPORTANT(ahead) )  {
         PrintShortNode(ahead, "unwind scanning back over:");
         ahead = ahead->last;
         }
      if( ahead == NULL )                           continue;
      if(DEBUG1)
         if( !UCBRANCH(ahead) || BAL(ahead) )
            PrintShortNode(ahead, " not UCBRANCH:" );
      if( !UCBRANCH(ahead) || BAL(ahead) )          continue;
      ahead = lab->ldef;   /* reset to target */
      PrintShortNode(ahead, " it branches to:");

      /* It is an unconditional branch.  We possibly have a
         movable block after it. Scan ahead for ending branch */
      ahead2 = ahead;
      n = 0;
      while( !UNKNOWN(ahead2) && ahead2!=NULL )  {
            if( !BAL(ahead2) )
               if( UCBRANCH(ahead2) )               break;
            if( !UNIMPORTANT(ahead2) )   n++;
            ahead2 = ahead2->next;
            if( OPNUMBER(ahead2) == i_efunct )      break;
            }
      if( ahead2 == NULL )                          continue;
      if( UNKNOWN(ahead2) )                         continue;
      if( OPNUMBER(ahead2) == i_efunct )            continue;
      ahead2 = ahead2->next; /* point AFTER end of block */
      if( ahead2 == NULL )                          continue;
      if( n > UNWINDLIMIT )                         continue;
      PrintShortNode(ahead,  "Unwind block starts at:" );
      PrintShortNode(ahead2, "  and ends before:" );

      /* make sure not about to move something to itself */
      while( ahead!=ahead2 )  {
         ahead = ahead->next;
         if( ahead==sn )                            break;
         }
      if( ahead==sn )                               continue;
      ahead = lab->ldef;   /* reset to target */

      /* found a block to move; (branch will be deleted later) */
      while( ahead!=ahead2 )  {
         ahead = ahead->next;
         MoveAfter( ahead->last, sn );
         sn = sn->next;
         c.jumpmoves += 1;
         }

      c.jumpunwinds += 1;
      changes += 1;
      }
   return changes;
}
