path: root/src/SDCClabel.c

/*-----------------------------------------------------------------
    SDCClabel.c - label optimizations on iCode (intermediate code)

    Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)

    This program is free software; you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by the
    Free Software Foundation; either version 2, or (at your option) any
    later version.
    
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
    
    In other words, you are welcome to use, share and improve this program.
    You are forbidden to forbid anyone else to use, share and improve
    what you give them.   Help stamp out software-hoarding!  
-------------------------------------------------------------------------*/

#include "common.h"

hTab *labelRef = NULL;
hTab *labelDef = NULL;

/*-----------------------------------------------------------------*/
/* buildLabelRefTable - creates an hashTable of label references   */
/*-----------------------------------------------------------------*/
void 
buildLabelRefTable (iCode * ic)
{
  iCode *lic;

  setToNull ((void *) &labelRef);
  setToNull ((void *) &labelDef);
  labelRef = newHashTable (labelKey + 1);
  labelDef = newHashTable (labelKey + 1);

  for (lic = ic; lic; lic = lic->next)
    {
      if (lic->op == GOTO)
        hTabAddItem (&labelRef, (IC_LABEL (lic))->key, lic);

      if (lic->op == JUMPTABLE)
        {
          symbol *lbl;
          for (lbl = setFirstItem (IC_JTLABELS (lic)); lbl;
               lbl = setNextItem (IC_JTLABELS (lic)))
            {
              hTabAddItem (&labelRef, lbl->key, lic);
            }
        }

      if (lic->op == IFX)
        {
          if (IC_TRUE (lic))
            hTabAddItem (&labelRef, (IC_TRUE (lic))->key, lic);
          else
            hTabAddItem (&labelRef, (IC_FALSE (lic))->key, lic);
        }
      if (lic->op == LABEL)
        hTabAddItem (&labelDef, (IC_LABEL (lic))->key, lic);

    }
}

/*-----------------------------------------------------------------*/
/* labelGotoNext - kills gotos to next statement                   */
/*-----------------------------------------------------------------*/
int 
labelGotoNext (iCode * ic)
{
  iCode *loop;
  int change = 0;

  for (loop = ic; loop; loop = loop->next)
    {

      if (loop->op == GOTO &&   /* if this is a goto */
          loop->next &&         /* and we have a next one */
          loop->next->op == LABEL &&    /* next one is a label */
          loop->next->label->key == loop->label->key)   /* same label */
        {
          loop->prev->next = loop->next;        /* get this out of the chain */
          loop->next->prev = loop->prev;
          hTabDeleteItem (&labelRef, (IC_LABEL (loop))->key, loop, DELETE_ITEM, NULL);
          change++;
        }
    }

  return change;
}

/*-------------------------------------------------------------------*/
/* deleteIfx - delete an IFX iCode or convert to DUMMY_READ_VOLATILE */
/*-------------------------------------------------------------------*/
static void
deleteIfx (iCode * loop, int key)
{
  werrorfl (loop->filename, loop->lineno, W_CONTROL_FLOW);
  hTabDeleteItem (&labelRef, key, loop, DELETE_ITEM, NULL);

  /* If the condition was volatile, convert IFX to */
  /* DUMMY_READ_VOLATILE. Otherwise just delete the */
  /* IFX iCode */
  if (IS_OP_VOLATILE (IC_COND (loop)))
    {
      IC_RIGHT (loop) = IC_COND (loop);
      IC_LEFT (loop) = NULL;
      IC_RESULT (loop) = NULL;
      loop->op = DUMMY_READ_VOLATILE;
    }
  else
    {
      loop->prev->next = loop->next;
      loop->next->prev = loop->prev;
    }
}


/*-----------------------------------------------------------------*/
/* labelIfx - special case Ifx elimination                         */
/*-----------------------------------------------------------------*/
int 
labelIfx (iCode * ic)
{
  iCode *loop;
  iCode *stat;
  int change = 0;

  for (loop = ic; loop; loop = loop->next)
    {
      /*   if  condition  goto label */
      /*   goto label                */
      /* i.e. the flow is going to the same location 
         regardless of the condition in this case the 
         condition can be eliminated with a WARNING ofcource */
      if (loop->op == IFX &&
            loop->next &&
        loop->next->op == GOTO)
        {
          if (IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key)
            {
              deleteIfx (loop, IC_TRUE (loop)->key);
              change++;
              continue;
            }
          else
            {
              if (IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)
                {
                  deleteIfx (loop, IC_FALSE (loop)->key);
                  change++;
                  continue;
                }
            }
        }
      /* same as above but with a twist */
      /* if condition goto label */
      /* label:                  */
      if (loop->op == IFX &&
          loop->next &&
          loop->next->op == LABEL &&
          ((IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key) ||
           (IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)))
        {
          deleteIfx (loop, IC_LABEL (loop->next)->key);
          change++;
          continue;
        }

      /* we will eliminate certain special case situations */
      /* of the conditional statement :-                  */
      /*       if cond != 0 goto _trueLabel               */
      /*       goto _falseLabel                           */
      /* _trueLabel :                                     */
      /*       ...                                        */
      /* in these cases we can change it to :-            */
      /*       if cond == 0 goto _falseLabel              */
      /* _trueLabel :                                     */
      /*       ...                                        */
      /* similarly if we have a situation like :-         */
      /*       if cond == 0 goto _falseLabel              */
      /*       goto _someLabel                            */
      /* _falseLabel :                                    */
      /* we can change this to                            */
      /*       if cond != 0 goto _someLabel               */
      /* _falseLabel :                                    */
      /*       ...                                        */
      if (loop->op == IFX && loop->next && loop->next->op == GOTO &&
            loop->next->next && loop->next->next->op == LABEL)
        {
          if (IC_TRUE (loop) && (IC_TRUE (loop))->key != (IC_LABEL (loop->next->next))->key ||
            (IC_FALSE (loop) && (IC_FALSE (loop))->key != (IC_LABEL (loop->next->next))->key))
            continue;

          /* now make sure that this is the only */
          /* referenece to the _trueLabel        */
          if (IC_TRUE (loop) && hTabItemWithKey (labelRef, (IC_TRUE (loop))->key))
            {
              /* we just change the falseLabel */
              /* to the next goto statement    */
              /* unreferenced label will take  */
              /* care of removing the label    */
              /* delete reference to the true label */

              hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
              IC_TRUE (loop) = NULL;
              IC_FALSE (loop) = IC_LABEL (loop->next);
              /* add reference to the LABEL */
              hTabAddItem (&labelRef, (IC_FALSE (loop))->key, loop);
              /* next remove the goto */
              hTabDeleteItem (&labelRef,
               (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
              loop->next = loop->next->next;
              loop->next->prev = loop;
              change++;
              continue;
            }

          /* now do the same with the false labels */
          if (IC_FALSE (loop) && hTabItemWithKey (labelRef, (IC_FALSE (loop))->key))
            {
              hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
              IC_FALSE (loop) = NULL;
              IC_TRUE (loop) = IC_LABEL (loop->next);
              hTabAddItem (&labelRef, (IC_TRUE (loop))->key, loop);
              hTabDeleteItem (&labelRef, (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
              loop->next = loop->next->next;
              loop->next->prev = loop;
              change++;
              continue;
            }
        }

      /* Optimize hidden jump-to-jump:
         Simplify
           v = 1;              stat->prev
           goto l1;            stat
         l0:
           v = 0;              loop->prev
         l1:                   loop
           if (v) goto l3;     loop->next
         Into
           v = 1;
           goto l3;
         l0:
           v = 0;
         l1: */
      if (loop->op == LABEL &&
          loop->next && loop->next->op == IFX &&
          (stat = hTabFirstItemWK (labelRef, (IC_LABEL (loop))->key)) &&
          !hTabNextItemWK (labelRef) &&
          stat && stat->op == GOTO &&
          stat->prev && stat->prev->op == '=' && IS_OP_LITERAL (IC_RIGHT (stat->prev)) &&
          loop->prev && loop->prev->op == '=' && IS_OP_LITERAL (IC_RIGHT (loop->prev)) &&
          IC_RESULT (stat->prev)->key == IC_COND (loop->next)->key &&
          IC_RESULT (loop->prev)->key == IC_COND (loop->next)->key &&
          !IS_OP_VOLATILE (IC_COND (loop->next)) &&
          (!operandLitValue (IC_RIGHT (stat->prev)) ^ !operandLitValue (IC_RIGHT (loop->prev))))
        {
          if (IC_FALSE (loop->next) && !operandLitValue (IC_RIGHT (loop->prev)) ||
              IC_TRUE (loop->next)  && operandLitValue (IC_RIGHT (loop->prev)))
            /* Complicated case: Insert goto, remove conditional jump. */
            {
              /* Change IFX to GOTO. */
              stat = loop->next;
              IC_LABEL (stat) = IC_TRUE (stat) ? IC_TRUE (stat) : IC_FALSE (stat);
              stat->op = GOTO;

             /* Move to desired location. */
              if (loop->next->next)
                loop->next->next->prev = loop;
              loop->next = loop->next->next;
              stat->prev = loop->prev;
              stat->prev->next = stat;
              stat->next = loop;
              loop->prev = stat;
              change++;
              continue;
            }
          else /* Simple case: Redirect goto, remove conditional jump. */
            {
              hTabDeleteItem (&labelRef, (IC_LABEL (stat))->key, stat, DELETE_ITEM, NULL);
              IC_LABEL (stat) = IC_TRUE (loop->next) ? IC_TRUE (loop->next) : IC_FALSE (loop->next);
              hTabAddItem (&labelRef, (IC_LABEL (stat))->key, stat);
              hTabDeleteItem (&labelRef, IC_LABEL (stat)->key, loop->next, DELETE_ITEM, NULL);
              if (loop->next->next)
                loop->next->next->prev = loop;
              loop->next = loop->next->next;
              change++;
              continue;
            }
        }
    }

  return change;
}

/*-----------------------------------------------------------------*/
/* replaceGotoGoto - find new target for jump                      */
/* if we have a target statement then check if the next            */
/* one is a goto: this means target of goto is a goto              */
/*-----------------------------------------------------------------*/
static symbol *
replaceGotoGoto (const iCode *ic, const symbol *sLabel, const iCode *target)
{
  if (!target || !target->next)
    return 0;

  if (target->next->op != GOTO && target->next->op != LABEL || target->next == ic)
    return 0;

  symbol *repLabel = target->next->label;

  if (repLabel == sLabel)
    return 0;

  return repLabel;
}


/*-----------------------------------------------------------------*/
/* labelGotoGoto - target of a goto is a goto                      */
/*-----------------------------------------------------------------*/
int 
labelGotoGoto (iCode *ic)
{
  iCode *loop;
  int change = 0;

  for (loop = ic; loop; loop = loop->next)
    {
      iCode *stat;
      symbol *sLabel = NULL;
      symbol *repLabel;
      stat = NULL;
      switch (loop->op)
        {
        case GOTO:              /* for a goto statement */

          stat = hTabItemWithKey (labelDef, (sLabel = IC_LABEL (loop))->key);

          if (repLabel = replaceGotoGoto (loop, sLabel, stat))
            {
              hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
              loop->label = repLabel;
              hTabAddItem (&labelRef, repLabel->key, loop);
              change++;
            }
          break;

        case IFX:               /* for a conditional jump */

          if (IC_TRUE (loop))
            stat = hTabItemWithKey (labelDef, (sLabel = IC_TRUE (loop))->key);
          else
            stat = hTabItemWithKey (labelDef, (sLabel = IC_FALSE (loop))->key);

          if (repLabel = replaceGotoGoto (loop, sLabel, stat))
            {
              if (IC_TRUE (loop))
                {
                  hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
                  IC_TRUE (loop) = repLabel;
                }
              else
                {
                  hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
                  IC_FALSE (loop) = repLabel;
                }
              hTabAddItem (&labelRef, repLabel->key, loop);
              change++;
            }
          break;
        case JUMPTABLE:

          for (sLabel = setFirstItem (IC_JTLABELS (loop)); sLabel; sLabel = setNextItem (IC_JTLABELS (loop)))
            if (repLabel = replaceGotoGoto (loop, sLabel, hTabItemWithKey (labelDef, sLabel->key)))
              {
                hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
                replaceSetItem (IC_JTLABELS (loop), sLabel, repLabel);
                hTabAddItem (&labelRef, repLabel->key, loop);
                change++;
              }
        }
    }

  return change;
}

/*-----------------------------------------------------------------*/
/* labelUnrefLabel - remove unreferenced labels                    */
/*-----------------------------------------------------------------*/
int 
labelUnrefLabel (iCode * ic)
{
  iCode *loop;
  int change = 0;

  for (loop = ic; loop; loop = loop->next)
    {

      /* if this is a label */
      if (loop->op == LABEL)
        {
          if (((IC_LABEL (loop))->key == returnLabel->key) ||
              ((IC_LABEL (loop))->key == entryLabel->key))
            continue;

          if (hTabItemWithKey (labelRef, (IC_LABEL (loop))->key))
            continue;

          /* else eliminitate this one */
          loop->prev->next = loop->next;        /* get this out of the chain */
          loop->next->prev = loop->prev;
          change++;
        }
    }

  return change;
}

/*-----------------------------------------------------------------*/
/* labelUnreach - remove unreachable code                          */
/*-----------------------------------------------------------------*/
int 
labelUnreach (iCode * ic)
{
  iCode *loop;
  iCode *tic;
  int change = 0;

  /* if we hit a return statement or a goto statement */
  /* remove all statements till we hit the next label */
  for (loop = ic; loop; loop = loop->next)
    {
      iCode *loop2;

      /* found a goto || return && the next */
      /* statement is not a label           */
      if (loop->op == GOTO || loop->op == RETURN ||
        loop->op == CALL && IFFUNC_ISNORETURN (operandType (IC_LEFT (loop))))
        {
          if (loop->next &&
              (loop->next->op == LABEL || loop->next->op == ENDFUNCTION))
            continue;

          /* loop till we find a label */
          loop2 = loop->next;
          while (loop2 && loop2->op != LABEL)
            loop2 = loop2->next;

          /* throw away those in between */
          for (tic = loop->next; tic && tic != loop2; tic = tic->next)
            {
              /* remove label references if any */
              switch (tic->op)
                {
                case GOTO:
                  hTabDeleteItem (&labelRef, IC_LABEL (tic)->key, tic, DELETE_ITEM, NULL);
                  break;
                case IFX:
                  werrorfl (tic->filename, tic->lineno, W_CODE_UNREACH);
                  if (IC_TRUE (tic))
                    hTabDeleteItem (&labelRef, IC_TRUE (tic)->key, tic, DELETE_ITEM, NULL);
                  else
                    hTabDeleteItem (&labelRef, IC_FALSE (tic)->key, tic, DELETE_ITEM, NULL);
                  break;
                default:
                  werrorfl (tic->filename, tic->lineno, W_CODE_UNREACH);
                }
            }

          /* now set up the pointers */
          loop->next = loop2;
          if (loop2)
            loop2->prev = loop;
          change++;
        }
    }
  return change;
}

/*-----------------------------------------------------------------*/
/* iCodeLabelOptimize - some obvious & general optimizations       */
/*-----------------------------------------------------------------*/
iCode *
iCodeLabelOptimize (iCode * ic)
{
  if (!optimize.label1 &&
      !optimize.label2 &&
      !optimize.label3 &&
      !optimize.label4)
    return ic;

  /* build labelreferences */
  buildLabelRefTable (ic);

  /* the following transformations need to ne done */
  /* repeatedly till a fixed point is reached      */
  while (1)
    {
      int change;
      change = 0;

      /* first eliminate any goto statement */
      /* that goes to the next statement    */
      if (optimize.label1)
        change += labelGotoNext (ic);

      if (optimize.label2)
        change += labelIfx (ic);

      /* target of a goto is a goto then rename this goto */
      if (optimize.label3)
        change += labelGotoGoto (ic);

      /* remove unreference labels */
      if (optimize.label4)
        change += labelUnrefLabel (ic);

      /* remove unreachable code */
      change += labelUnreach (ic);

      if (!change)              /* fixed point reached */
        break;
    }

  return ic;
}