Update svn merge history.

[sdcc.git] / sdcc / src / SDCCloop.c

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

  SDCCloop.c - source file for loop detection & optimizations

             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"
#include "newalloc.h"

DEFSETFUNC (isDefAlive);

STACK_DCL (regionStack, eBBlock *, MAX_NEST_LEVEL * 10)

/*-----------------------------------------------------------------*/
/* newInduction - creates a new induction variable                 */
/*-----------------------------------------------------------------*/
static induction *
newInduction (operand * sym, unsigned int op, long constVal, iCode * ic, operand * asym)
{
  induction *ip;

  ip = Safe_alloc (sizeof (induction));

  ip->sym = sym;
  ip->asym = asym;
  ip->op = op;
  ip->cval = constVal;
  ip->ic = ic;
//updateSpillLocation(ic,1);
  return ip;
}

/*-----------------------------------------------------------------*/
/* newRegion - allocate & returns a loop structure                 */
/*-----------------------------------------------------------------*/
static region *
newRegion ()
{
  region *lp;

  lp = Safe_alloc (sizeof (region));

  return lp;
}


#if 0
/*-----------------------------------------------------------------*/
/* pinduction - prints induction                                   */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (pinduction)
{
  induction *ip = item;
  iCodeTable *icTab;

  fprintf (stdout, "\t");
  printOperand (ip->sym, stdout);
  icTab = getTableEntry (ip->ic->op);
  icTab->iCodePrint (stdout, ip->ic, icTab->printName);
  fprintf (stdout, " %04d\n", (int) ip->cval);
  return 0;
}

/*-----------------------------------------------------------------*/
/* pregion - prints loop information                                */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (pregion)
{
  region *lp = item;

  printf ("================\n");
  printf (" loop with entry -- > ");
  printEntryLabel (lp->entry, ap);
  printf ("\n");
  printf (" loop body --> ");
  applyToSet (lp->regBlocks, printEntryLabel);
  printf ("\n");
  printf (" loop exits --> ");
  applyToSet (lp->exits, printEntryLabel);
  printf ("\n");
  return 0;
}
#endif

/*-----------------------------------------------------------------*/
/* backEdges - returns a list of back edges                        */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (backEdges)
{
  edge *ep = item;
  V_ARG (set **, bEdges);

  /* if this is a back edge ; to determine this we check */
  /* to see if the 'to' is in the dominator list of the  */
  /* 'from' if yes then this is a back edge              */
  if (bitVectBitValue (ep->from->domVect, ep->to->bbnum))
    {
      addSetHead (bEdges, ep);
      return 1;
    }

  return 0;
}

/*-----------------------------------------------------------------*/
/* intersectLoopSucc - returns intersection of loop Successors     */
/*-----------------------------------------------------------------*/
static bitVect *
intersectLoopSucc (set * lexits, eBBlock ** ebbs)
{
  bitVect *succVect = NULL;
  eBBlock *exit = setFirstItem (lexits);

  if (!exit)
    return NULL;

  succVect = bitVectCopy (exit->succVect);

  for (exit = setNextItem (lexits); exit; exit = setNextItem (lexits))
    {
      succVect = bitVectIntersect (succVect, exit->succVect);
    }

  return succVect;
}

/*-----------------------------------------------------------------*/
/* loopInsert will insert a block into the loop set                */
/*-----------------------------------------------------------------*/
static void
loopInsert (set ** regionSet, eBBlock * block)
{
  if (!isinSet (*regionSet, block))
    {
      addSetHead (regionSet, block);
      STACK_PUSH (regionStack, block);
    }
}

/*-----------------------------------------------------------------*/
/* insertIntoLoop - insert item into loop                          */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (insertIntoLoop)
{
  eBBlock *ebp = item;
  V_ARG (set **, regionSet);

  loopInsert (regionSet, ebp);
  return 0;
}

/*-----------------------------------------------------------------*/
/* isNotInBlocks - will return 1 if not is blocks                  */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (isNotInBlocks)
{
  eBBlock *ebp = item;
  V_ARG (set *, blocks);

  if (!isinSet (blocks, ebp))
    return 1;

  return 0;
}

#if 0
/*-----------------------------------------------------------------*/
/* hasIncomingDefs - has definitions coming into the loop. i.e.    */
/* check to see if the preheaders outDefs has any definitions      */
/*-----------------------------------------------------------------*/
static int
hasIncomingDefs (region * lreg, operand * op)
{
  eBBlock *preHdr = lreg->entry->preHeader;

  if (preHdr && bitVectBitsInCommon (preHdr->outDefs, OP_DEFS (op)))
    return 1;
  return 0;
}

/*-----------------------------------------------------------------*/
/* findLoopEndSeq - will return the sequence number of the last    */
/* iCode with the maximum dfNumber in the region                   */
/*-----------------------------------------------------------------*/
static int
findLoopEndSeq (region * lreg)
{
  eBBlock *block;
  eBBlock *lblock;

  for (block = lblock = setFirstItem (lreg->regBlocks); block; block = setNextItem (lreg->regBlocks))
    {
      if (block != lblock && block->lSeq > lblock->lSeq)
        lblock = block;
    }

  return lblock->lSeq;
}
#endif

/*-----------------------------------------------------------------*/
/* addToExitsMarkDepth - will add the the exitSet all blocks that  */
/* have exits, will also update the depth field in the blocks      */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (addToExitsMarkDepth)
{
  eBBlock *ebp = item;
  V_ARG (set *, loopBlocks);
  V_ARG (set **, exits);
  V_ARG (int, depth);
  V_ARG (region *, lr);

  /* mark the loop depth of this block */
  //if (!ebp->depth)
  if (ebp->depth < depth)
    ebp->depth = depth;

  /* NOTE: here we will update only the inner most loop
     that it is a part of */
  if (!ebp->partOfLoop)
    ebp->partOfLoop = lr;

  /* if any of the successors go out of the loop then */
  /* we add this one to the exits */
  if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
    {
      addSetHead (exits, ebp);
      return 1;
    }

  return 0;
}

/*-----------------------------------------------------------------*/
/* createLoop - will create a set of region                        */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (createLoop)
{
  edge *ep = item;
  V_ARG (set **, allRegion);
  region *aloop = newRegion ();
  eBBlock *block;

  /* make sure regionStack is empty */
  while (!STACK_EMPTY (regionStack))
    STACK_POP (regionStack);

  /* add the entryBlock */
  addSet (&aloop->regBlocks, ep->to);
  loopInsert (&aloop->regBlocks, ep->from);

  while (!STACK_EMPTY (regionStack))
    {
      block = STACK_POP (regionStack);
      /* if block != entry */
      if (block != ep->to)
        applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
    }

  aloop->entry = ep->to;

  /* now add it to the set */
  addSetHead (allRegion, aloop);
  return 0;
}

/*-----------------------------------------------------------------*/
/* dominatedBy - will return 1 if item is dominated by block       */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (dominatedBy)
{
  eBBlock *ebp = item;
  V_ARG (eBBlock *, block);

  return bitVectBitValue (ebp->domVect, block->bbnum);
}

/*-----------------------------------------------------------------*/
/* addDefInExprs - adds an expression into the inexpressions       */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (addDefInExprs)
{
  eBBlock *ebp = item;
  V_ARG (cseDef *, cdp);
  V_ARG (ebbIndex *, ebbi);

  addSetHead (&ebp->inExprs, cdp);
  cseBBlock (ebp, optimize.global_cse, ebbi);
  return 0;
}

/*-----------------------------------------------------------------*/
/* assignmentsToSym - for a set of blocks determine # time assigned */
/*-----------------------------------------------------------------*/
static int
assignmentsToSym (set * sset, operand * sym)
{
  eBBlock *ebp;
  int assigns = 0;
  set *blocks = setFromSet (sset);

  for (ebp = setFirstItem (blocks); ebp; ebp = setNextItem (blocks))
    {
      /* get all the definitions for this symbol
         in this block */
      bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
      assigns += bitVectnBitsOn (defs);
      setToNull ((void *) &defs);
    }

  return assigns;
}


/*-----------------------------------------------------------------*/
/* isOperandInvariant - determines if an operand is an invariant   */
/*-----------------------------------------------------------------*/
static int
isOperandInvariant (operand * op, region * theLoop, set * lInvars)
{
  int opin = 0;
  /* operand is an invariant if it is a                */
  /*       a. constants .                              */
  /*       b. that have definitions reaching loop entry */
  /*       c. that are already defined as invariant    */
  /*       d. has no assignments in the loop           */
  if (op)
    {
      if (IS_OP_LITERAL (op))
        opin = 1;
      else if (IS_SYMOP (op) && OP_SYMBOL (op)->addrtaken)
        opin = 0;
      else if (ifDefSymIs (theLoop->entry->inExprs, op))
        opin = 1;
      else if (ifDefSymIs (lInvars, op))
        opin = 1;
      else if (IS_SYMOP (op) && !IS_OP_GLOBAL (op) && !IS_OP_VOLATILE (op) && assignmentsToSym (theLoop->regBlocks, op) == 0)
        opin = 1;
    }
  else
    opin++;

  return opin;
}

/*-----------------------------------------------------------------*/
/* pointerAssigned - will return 1 if pointer set found            */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (pointerAssigned)
{
  eBBlock *ebp = item;
  V_ARG (operand *, op);

  if (ebp->hasFcall)
    return 1;

  if (bitVectBitValue (ebp->ptrsSet, op->key))
    return 1;

  /* Unfortunately, one of the other pointer set operations  */
  /* may be using an alias of this operand, and the above    */
  /* test would miss it. To be thorough, some aliasing       */
  /* analysis should be done here. In the meantime, be       */
  /* conservative and assume any other pointer set operation */
  /* is dangerous                                            */
  if (!bitVectIsZero (ebp->ptrsSet))
    return 1;

  return 0;
}

/*-----------------------------------------------------------------*/
/* hasNonPtrUse - returns true if operand has non pointer usage    */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (hasNonPtrUse)
{
  eBBlock *ebp = item;
  V_ARG (operand *, op);
  iCode *ic = usedInRemaining (op, ebp->sch);

  if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
    return 1;

  return 0;

}

/*-----------------------------------------------------------------*/
/* loopInvariants - takes loop invariants out of region            */
/*-----------------------------------------------------------------*/
static int
loopInvariants (region *theLoop, ebbIndex *ebbi)
{
  eBBlock **ebbs = ebbi->dfOrder;
  int count = ebbi->count;
  set *lInvars = NULL;

  int change = 0;
  int fCallsInBlock;

  /* if the preHeader does not exist then do nothing */
  /* or no exits then do nothing ( have to think about this situation */
  if (theLoop->entry->preHeader == NULL || theLoop->exits == NULL)
    return 0;

  /* we will do the elimination for those blocks       */
  /* in the loop that dominate all exits from the loop */
  for (eBBlock *lBlock = setFirstItem (theLoop->regBlocks); lBlock; lBlock = setNextItem (theLoop->regBlocks))
    {
      iCode *ic;
      int domsAllExits;

      /* mark the dominates all exits flag */
      domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) == elementsInSet (theLoop->exits));

      /* find out if we have a function call in this block */
      for (ic = lBlock->sch, fCallsInBlock = 0; ic; ic = ic->next)
        {
          if (SKIP_IC (ic))
            {
              fCallsInBlock++;
            }
        }

      /* now we go thru the instructions of this block and */
      /* collect those instructions with invariant operands */
      for (ic = lBlock->sch; ic; ic = ic->next)
        {
          int lin, rin;
          cseDef *ivar;

          /* TODO this is only needed if the call is between
             here and the definition, but I am too lazy to do that now */

          /* if there are function calls in this block */
          if (fCallsInBlock)
            {
              /* if this is a pointer get */
              if (POINTER_GET (ic))
                {
                  continue;
                }

              /* if this is an assignment from a global */
              if (ic->op == '=' && isOperandGlobal (IC_RIGHT (ic)))
                {
                  continue;
                }

              /* Bug 1717943,
               * if this is an assignment to a global */
              if (ic->op == '=' && isOperandGlobal (IC_RESULT (ic)))
                {
                  continue;
                }
            }

          if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
            continue;

          /* iTemp assignment from a literal may be invariant, but it
             will needlessly increase register pressure if the
             iCode(s) that use this iTemp are not also invariant */
          if (ic->op == '=' && IS_ITEMP (IC_RESULT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic)))
            continue;

          /* if result is volatile then skip */
          if (IC_RESULT (ic) && (isOperandVolatile (IC_RESULT (ic), TRUE) || IS_OP_PARM (IC_RESULT (ic))))
            continue;

          /* if result depends on a volatile then skip */
          if ((IC_LEFT (ic) && isOperandVolatile (IC_LEFT (ic), TRUE)) ||
              (IC_RIGHT (ic) && isOperandVolatile (IC_RIGHT (ic), TRUE)))
            continue;

          if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
            continue;

          lin = rin = 0;

          /* special case */
          /* if address of then it is an invariant */
          if (ic->op == ADDRESS_OF && IS_SYMOP (IC_LEFT (ic)) && IS_AGGREGATE (operandType (IC_LEFT (ic))))
            {
              lin++;
            }
          else
            {
              /* check if left operand is an invariant */
              if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)) &&
                  /* if this is a pointer get then make sure
                     that the pointer set does not exist in
                     any of the blocks */
                  POINTER_GET (ic) && applyToSet (theLoop->regBlocks, pointerAssigned, IC_LEFT (ic)))
                {
                  lin = 0;
                }
            }

          /* do the same for right */
          rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);

          /* if this is a POINTER_GET then special case, make sure all
             usages within the loop are POINTER_GET any other usage
             would mean that this is not an invariant , since the pointer
             could then be passed as a parameter */
          if (POINTER_GET (ic) && applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
            continue;


          /* if both the left & right are invariants : then check that */
          /* this definition exists in the out definition of all the   */
          /* blocks, this will ensure that this is not assigned any    */
          /* other value in the loop, and not used in this block       */
          /* prior to this definition which means only this definition */
          /* is used in this loop                                      */
          if (lin && rin && IC_RESULT (ic))
            {
              eBBlock *sBlock;
              set *lSet = setFromSet (theLoop->regBlocks);

              /* if this block does not dominate all exits */
              /* make sure this definition is not used anywhere else */
              if (!domsAllExits)
                {
                  if (isOperandGlobal (IC_RESULT (ic)))
                    continue;
                  /* for successors for all exits */
                  for (sBlock = setFirstItem (theLoop->exits); sBlock; sBlock = setNextItem (theLoop->exits))
                    {
                      for (int i = 0; i < count; ebbs[i++]->visited = 0);
                      lBlock->visited = 1;
                      if (applyToSet (sBlock->succList, isDefAlive, ic))
                        break;
                    }

                  /* we have found usage */
                  if (sBlock)
                    continue;
                }

              /* now make sure this is the only definition */
              for (sBlock = setFirstItem (lSet); sBlock; sBlock = setNextItem (lSet))
                {
                  iCode *ic2;
                  int used;
                  int defDominates;

                  /* if this is the block make sure the definition */
                  /* reaches the end of the block */
                  if (sBlock == lBlock)
                    {
                      if (!ifDiCodeIs (sBlock->outExprs, ic))
                        break;
                    }
                  else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
                    break;

                  /* Check that this definition is not assigned */
                  /* any other value in this block. Also check */
                  /* that any usage in the block is dominated by */
                  /* by this definition. */
                  defDominates = bitVectBitValue (sBlock->domVect, lBlock->bbnum);
                  used = 0;
                  for (ic2 = sBlock->sch; ic2; ic2 = ic2->next)
                    {
                      if (ic2->op == IFX)
                        {
                          if (isOperandEqual (IC_RESULT (ic), IC_COND (ic2)))
                            used = 1;
                        }
                      else if (ic2->op == JUMPTABLE)
                        {
                          if (isOperandEqual (IC_RESULT (ic), IC_JTCOND (ic2)))
                            used = 1;
                        }
                      else
                        {
                          if (IC_LEFT (ic2) && isOperandEqual (IC_RESULT (ic), IC_LEFT (ic2)))
                            used = 1;
                          if (IC_RIGHT (ic2) && isOperandEqual (IC_RESULT (ic), IC_RIGHT (ic2)))
                            used = 1;
                          if ((ic != ic2) && (isOperandEqual (IC_RESULT (ic), IC_RESULT (ic2))))
                            break;
                          /* If used before this definition, might not be invariant */
                          if ((ic == ic2) && used)
                            break;
                        }
                      if (used && !defDominates)
                        break;
                    }
                  if (ic2)      /* found another definition or a usage before the definition */
                    break;
                }

              if (sBlock)
                continue;       /* another definition present in the block */

              // Avoid bug #3560 - the address might have been passed elsewehere, so functions called in the loop could change the value (and rely on the changed value).
              if (OP_SYMBOL (IC_RESULT (ic))->addrtaken && fCallsInBlock)
                continue;

              /* now check if it exists in the in of this block */
              /* if not then it was killed before this instruction */
              if (!bitVectBitValue (lBlock->inDefs, ic->key))
                continue;

              /* now we know it is a true invariant */
              /* remove it from the insts chain & put */
              /* in the invariant set                */

              OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
              SPIL_LOC (IC_RESULT (ic)) = NULL;
              remiCodeFromeBBlock (lBlock, ic);

              /* maintain the data flow */
              /* this means removing from definition from the */
              /* defset of this block and adding it to the    */
              /* inexpressions of all blocks within the loop  */
              bitVectUnSetBit (lBlock->defSet, ic->key);
              bitVectUnSetBit (lBlock->ldefs, ic->key);
              ivar = newCseDef (IC_RESULT (ic), ic);
              applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbi);
              addSet (&lInvars, ivar);
            }
        }
    }                           /* for all loop blocks */

  /* if we have some invariants then */
  if (lInvars)
    {
      eBBlock *preHdr = theLoop->entry->preHeader;
      iCode *icFirst = NULL, *icLast = NULL;

      /* create an iCode chain from it */
      for (cseDef *cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
        {
          /* maintain data flow .. add it to the */
          /* ldefs defSet & outExprs of the preheader  */
          preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
          preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
          cdp->diCode->filename = preHdr->ech->filename;
          cdp->diCode->lineno = preHdr->ech->lineno;
          addSetHead (&preHdr->outExprs, cdp);

          if (!icFirst)
            icFirst = cdp->diCode;
          if (icLast)
            {
              icLast->next = cdp->diCode;
              cdp->diCode->prev = icLast;
              icLast = cdp->diCode;
            }
          else
            icLast = cdp->diCode;
          change++;
        }

      /* add the instruction chain to the end of the
         preheader for this loop, preheaders will always
         have atleast a label */
      preHdr->ech->next = icFirst;
      icFirst->prev = preHdr->ech;
      preHdr->ech = icLast;
      icLast->next = NULL;
    }
  return change;
}

/*-----------------------------------------------------------------*/
/* addressTaken - returns true if the symbol is found in the addrof */
/*-----------------------------------------------------------------*/
static int
addressTaken (set * sset, operand * sym)
{
  set *loop;
  eBBlock *ebp;
  set *loop2;

  for (loop = sset; loop; loop = loop->next)
    {
      ebp = loop->item;
      loop2 = ebp->addrOf;
      while (loop2)
        {
          if (isOperandEqual ((operand *) loop2->item, sym))
            return 1;
          loop2 = loop2->next;
        }
    }

  return 0;
}


/*-----------------------------------------------------------------*/
/* findInduction :- returns 1 & the item if the induction is found */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (findInduction)
{
  induction *ip = item;
  V_ARG (operand *, sym);
  V_ARG (induction **, ipp);

  if (isOperandEqual (ip->sym, sym))
    {
      *ipp = ip;
      return 1;
    }

  return 0;
}

/*-----------------------------------------------------------------*/
/* findDefInRegion - finds the definition within the region        */
/*-----------------------------------------------------------------*/
static iCode *
findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
{
  eBBlock *lBlock;

  /* for all blocks in the region */
  for (lBlock = setFirstItem (regBlocks); lBlock; lBlock = setNextItem (regBlocks))
    {

      /* if a definition for this exists */
      if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
        {
          iCode *ic;

          /* go thru the instruction chain to find it */
          for (ic = lBlock->sch; ic; ic = ic->next)
            if (bitVectBitValue (OP_DEFS (defOp), ic->key))
              {
                if (owner)
                  *owner = lBlock;
                return ic;
              }
        }
    }

  return NULL;
}

/*-----------------------------------------------------------------*/
/* addPostLoopBlock - add a ebblock before the successors of the   */
/*                    loop exits                                   */
/*-----------------------------------------------------------------*/
static void
addPostLoopBlock (region * loopReg, ebbIndex * ebbi, iCode * ic)
{
  bitVect *loopSuccs;
  int i;

  /* if the number of exits is greater than one then
     we use another trick: we will create an intersection
     of successors of the exits, then take those that are not
     part of the loop and have dfNumber greater loop entry (eblock),
     insert a new predecessor postLoopBlk before them and add
     a copy of ic in the new block. The postLoopBlk in between
     is necessary, because the old successors of the loop exits can
     be successors of other blocks too: see bug-136564. */

  /* loopSuccs now contains intersection
     of all the loops successors */
  loopSuccs = intersectLoopSucc (loopReg->exits, ebbi->dfOrder);
  if (!loopSuccs)
    return;

  for (i = 0; i < loopSuccs->size; i++)
    {
      eBBlock *eblock = NULL;
      eBBlock *postLoopBlk;
      iCode *newic;
      int j;

      if (!bitVectBitValue (loopSuccs, i))
        continue;

      /* Need to search for bbnum == i since ebbi->dfOrder is
         sorted by dfnum; a direct index won't do.  */
      for (j = 0; j < ebbi->count; j++)
        if (ebbi->dfOrder[j]->bbnum == i)
          {
            eblock = ebbi->dfOrder[j];
            break;
          }
      assert (eblock);

      /* if the successor does not belong to the loop
         and will be executed after the loop : then
         add a definition to the block */
      if (isinSet (loopReg->regBlocks, eblock))
        continue;
      if (eblock->dfnum <= loopReg->entry->dfnum)
        continue;

      /* look for an existing loopExitBlock */
      if (strncmp (LOOPEXITLBL, eblock->entryLabel->name, sizeof (LOOPEXITLBL) - 1) == 0)
        {
          /* reuse the existing one */
          postLoopBlk = eblock;
        }
      else
        {
          /* create and insert a new eBBlock.
             Damn, that's messy ... */
          int i;
          set *oldPredList;
          eBBlock *ebpi;

          postLoopBlk = neweBBlock ();

          /* create a loopExit-label */
          postLoopBlk->entryLabel = newiTempLoopHeaderLabel (0);

          /* increase bbnum for all blocks after
             (and including) eblock */
          for (i = 0; i < ebbi->count; i++)
            {
              if (ebbi->bbOrder[i]->bbnum >= eblock->bbnum)
                ++ebbi->bbOrder[i]->bbnum;
            }
          /* insert postLoopBlk before bbnum */
          postLoopBlk->bbnum = eblock->bbnum - 1;

          ++ebbi->count;

          /* these arrays need one more block, which ... */
          ebbi->bbOrder = Safe_realloc (ebbi->bbOrder, (ebbi->count + 1) * sizeof (eBBlock *));
          /* ... must be initialized with 0 */
          ebbi->bbOrder[ebbi->count] = NULL;
          /* move the blocks up ... */
          memmove (&ebbi->bbOrder[postLoopBlk->bbnum + 1],
                   &ebbi->bbOrder[postLoopBlk->bbnum], (ebbi->count - postLoopBlk->bbnum - 1) * sizeof (eBBlock *));
          /* ... and insert postLoopBlk */
          ebbi->bbOrder[postLoopBlk->bbnum] = postLoopBlk;

          /* just add postLoopBlk at the end of dfOrder,
             computeControlFlow() will compute the new dfnum */
          ebbi->dfOrder = Safe_realloc (ebbi->dfOrder, (ebbi->count + 1) * sizeof (eBBlock *));
          ebbi->dfOrder[ebbi->count] = NULL;
          ebbi->dfOrder[ebbi->count - 1] = postLoopBlk;

          /* copy loop information from eblock to postLoopBlk */
          if (eblock->partOfLoop)
            {
              postLoopBlk->partOfLoop = eblock->partOfLoop;
              /* add postLoopBlk to loop region */
              addSetHead (&postLoopBlk->partOfLoop->regBlocks, postLoopBlk);
            }

          /* go through loop exits and replace the old exit block eblock
             with the new postLoopBlk */
          for (ebpi = setFirstItem (loopReg->exits); ebpi; ebpi = setNextItem (loopReg->exits))
            {
              /* replace old label with new label */
              replaceLabel (ebpi, eblock->entryLabel, postLoopBlk->entryLabel);
            }

          /* now eblock is replaced by postLoopBlk.
             It's possible, that eblock has an immediate predecessor
             (with ebpi->bbnum + 1 == eblock->bbnum), which isn't part of the
             loop. This predecessor must stay predecessor of eblock, not of
             postLoopBlk. But now postLoopBlk is in between, therefore a GOTO
             from this predecessor to eblock must be appended.
             Example: bug-136564.c */

          /* take all predecessors and subtract the loop exits */
          oldPredList = subtractFromSet (eblock->predList, loopReg->exits, THROW_NONE);
          for (ebpi = setFirstItem (oldPredList); ebpi; ebpi = setNextItem (oldPredList))
            {
              /* Is it an immediate predecessor (without GOTO)?
                 All other predecessors end with a
                 GOTO, IF, IFX or JUMPTABLE: nothing to to do */
              if (ebpi->bbnum + 1 == postLoopBlk->bbnum)
                {
                  /* insert goto to old predecessor of eblock */
                  newic = newiCodeLabelGoto (GOTO, eblock->entryLabel);
                  addiCodeToeBBlock (ebpi, newic, NULL);
                  /* Make sure the GOTO has a target */
                  if (eblock->sch->op != LABEL)
                    {
                      newic = newiCodeLabelGoto (LABEL, eblock->entryLabel);
                      addiCodeToeBBlock (eblock, newic, eblock->sch);
                    }
                  break;        /* got it, only one is possible */
                }
            }

          /* set the label */
          postLoopBlk->sch = postLoopBlk->ech = newiCodeLabelGoto (LABEL, postLoopBlk->entryLabel);
        }

      /* create the definition in postLoopBlk */
      newic = newiCode ('=', NULL, operandFromOperand (IC_RIGHT (ic)));
      IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
      /* maintain data flow */
      OP_DEFS (IC_RESULT (newic)) = bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
      OP_USES (IC_RIGHT (newic)) = bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);

      /* and add it */
      addiCodeToeBBlock (postLoopBlk, newic, NULL);
      postLoopBlk->sch->filename = postLoopBlk->ech->filename = eblock->sch->filename;
      postLoopBlk->sch->lineno = postLoopBlk->ech->lineno = eblock->sch->lineno;

      /* outDefs is needed by computeControlFlow(), anything
         else will be set up by computeControlFlow() */
      postLoopBlk->outDefs = bitVectSetBit (postLoopBlk->outDefs, newic->key);
    }                           /* for (i = 0; i < loopSuccs->size; i++) */

  /* the postLoopBlk and the induction significantly
     changed the control flow, recompute it */
  computeControlFlow (ebbi);
}

/*-----------------------------------------------------------------*/
/* basicInduction - finds the basic induction variables in a loop  */
/*-----------------------------------------------------------------*/
static set *
basicInduction (region * loopReg, ebbIndex * ebbi)
{
  eBBlock *lBlock;
  set *indVars = NULL;

  /* i.e. all assignments of the form a := a +/- const */
  /* for all blocks within the loop do */
  for (lBlock = setFirstItem (loopReg->regBlocks); lBlock; lBlock = setNextItem (loopReg->regBlocks))
    {

      iCode *ic, *dic;

      /* for all instructions in the blocks do */
      for (ic = lBlock->sch; ic; ic = ic->next)
        {
          operand *aSym;
          long litValue;
          induction *ip;
          iCode *indIc;
          eBBlock *owner = NULL;
          int nexits;
          sym_link *optype;

          /* To find an induction variable, we need to */
          /* find within the loop three iCodes in this */
          /* general form:                             */
          /*                                           */
          /* ddic: iTempB    := symbolVar              */
          /* dic:  iTempA    := iTempB + lit           */
          /*    or iTempA    := iTempB - lit           */
          /*    or iTempA    := lit + iTempB           */
          /* ic:   symbolVar := iTempA                 */
          /*                                           */
          /* (symbolVar may also be an iTemp if it is  */
          /*  register equivalent)                     */

          /* look for assignments of the form */
          /*   symbolVar := iTempNN */
          if (ic->op != '=')
            continue;

          if (!IS_SYMOP (IC_RESULT (ic)))
            continue;

          if (!IS_TRUE_SYMOP (IC_RESULT (ic)) && !OP_SYMBOL (IC_RESULT (ic))->isreqv)
            continue;

          if (isOperandGlobal (IC_RESULT (ic)))
            continue;

          if (!IS_ITEMP (IC_RIGHT (ic)))
            continue;

          /* if it has multiple assignments within the loop then skip */
          if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
            continue;

          /* if the address of this was taken inside the loop then continue */
          if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
            continue;

          /* Only consider variables with integral type. */
          /* (2004/12/06 - EEP - ds390 fails regression tests unless */
          /* pointers are also considered for induction (due to some */
          /* register allocation bugs). Remove !IS_PTR clause when */
          /* that gets fixed) */
          optype = operandType (IC_RIGHT (ic));
          if (!IS_INTEGRAL (optype) && !IS_PTR (optype))
            continue;

          /* find the definition for the result in the block */
          if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks), IC_RIGHT (ic), &owner)))
            continue;

          /* if not +/- continue */
          if (dic->op != '+' && dic->op != '-')
            continue;

          /* make sure definition is of the form  a +/- c */
          if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
            continue;

          /* make sure the definition found is the only one */
          if (assignmentsToSym (loopReg->regBlocks, IC_RIGHT (ic)) > 1)
            continue;

          if (IS_OP_LITERAL (IC_RIGHT (dic)))
            {
              aSym = IC_LEFT (dic);
              litValue = (long) operandLitValue (IC_RIGHT (dic));
            }
          else
            {
              /* For minus, the literal must not be on the left side. */
              /* (Actually, this case could be handled, but it's probably */
              /* not worth the extra code) */
              if (dic->op == '-')
                continue;
              aSym = IC_RIGHT (dic);
              litValue = (long) operandLitValue (IC_LEFT (dic));
            }

          if (!isOperandEqual (IC_RESULT (ic), aSym) && !isOperandEqual (IC_RIGHT (ic), aSym))
            {
              iCode *ddic;
              /* find the definition for this and check */
              if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner)))
                continue;

              if (ddic->op != '=')
                continue;

              if (!isOperandEqual (IC_RESULT (ddic), aSym) || !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
                continue;
            }

          /* if the right hand side has more than one usage then
             don't make it an induction (will have to think some more) */
          if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
            continue;

          /* if the definition is volatile then it cannot be
             an induction object */
          if (isOperandVolatile (IC_RIGHT (ic), FALSE) || isOperandVolatile (IC_RESULT (ic), FALSE))
            continue;

          /* whew !! that was a lot of work to find the definition */
          /* create an induction object */
          indIc = newiCode ('=', NULL, IC_RESULT (ic));
          indIc->filename = ic->filename;
          indIc->lineno = ic->lineno;
          IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
          IC_RESULT (indIc)->isaddr = 0;
          OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
          ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);

          /* replace the inducted variable by the iTemp */
          replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
          /* ic should now be moved to the exit block(s) */

          nexits = elementsInSet (loopReg->exits);
          if (nexits == 0)
            {
              /* this is a endless loop without exits: there's
                 no need to restore the inducted variable */
              iCode *saveic = ic->prev;

              /* ic will be removed by killDeadCode() too,
                 but it's a nice to see a clean dumploop now. */
              unsetDefsAndUses (ic);
              remiCodeFromeBBlock (lBlock, ic);
              /* clear the definition */
              bitVectUnSetBit (lBlock->defSet, ic->key);
              ic = saveic;
            }
          else
            addPostLoopBlock (loopReg, ebbi, ic);
          addSet (&indVars, ip);
        }                       /* for ic */
    }                           /* end of all blocks for basic induction variables */

  return indVars;
}

/*-----------------------------------------------------------------*/
/* loopInduction - remove induction variables from a loop          */
/*-----------------------------------------------------------------*/
static int
loopInduction (region * loopReg, ebbIndex * ebbi)
{
  int change = 0;
  eBBlock *lBlock, *owner, *lastBlock = NULL;
  set *indVars = NULL;
  set *basicInd = NULL;

  if (loopReg->entry->preHeader == NULL)
    return 0;

  /* we first determine the basic Induction variables */
  basicInd = setFromSet (indVars = basicInduction (loopReg, ebbi));

  /* find other induction variables : by other we mean definitions of */
  /* the form x := y (* | / ) <constant> .. we will move this one to  */
  /* beginning of the loop and reduce strength i.e. replace with +/-  */
  /* these expensive expressions: OH! and y must be induction too     */
  for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
       lBlock && indVars; lBlock = setNextItem (loopReg->regBlocks))
    {
      iCode *ic, *indIc, *dic;
      induction *ip;

      /* last block is the one with the highest block
         number */
      if (lastBlock->bbnum < lBlock->bbnum)
        lastBlock = lBlock;

      for (ic = lBlock->sch; ic; ic = ic->next)
        {
          operand *aSym;
          operand *litSym;
          long litVal;

          /* consider only * & / */
          if (ic->op != '*' && ic->op != '/')
            continue;

          /* only consider variables with integral type */
          if (!IS_INTEGRAL (operandType (IC_RESULT (ic))))
            continue;

          /* if the result has more definitions then */
          if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
            continue;

          /* check if the operands are what we want */
          /* i.e. one of them an symbol the other a literal */
          if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
                (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
            continue;

          if (IS_SYMOP (IC_LEFT (ic)))
            {
              aSym = IC_LEFT (ic);
              litSym = IC_RIGHT (ic);
            }
          else
            {
              /* For division, the literal must not be on the left side */
              if (ic->op == '/')
                continue;
              aSym = IC_RIGHT (ic);
              litSym = IC_LEFT (ic);
            }
          litVal = (long) operandLitValue (litSym);

          ip = NULL;
          /* check if this is an induction variable */
          if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
            continue;

          /* ask port for size not worth if native instruction
             exist for multiply & divide */
          if (port->hasNativeMulFor (ic, operandType (IC_LEFT (ic)), operandType (IC_RIGHT (ic))))
            continue;

          /* if this is a division then the remainder should be zero
             for it to be inducted */
          if (ic->op == '/' && (ip->cval % litVal))
            continue;

          /* create the iCode to be placed in the loop header */
          /* and create the induction object */

          /* create an instruction */
          /* this will be put on the loop header */
          indIc = newiCode (ic->op, operandFromOperand (aSym), operandFromOperand (litSym));
          indIc->filename = ic->filename;
          indIc->lineno = ic->lineno;
          IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
          OP_SYMBOL (IC_RESULT (indIc))->isind = 1;

          /* keep track of the inductions */
          litVal = (ic->op == '*' ? (litVal * ip->cval) : (ip->cval / litVal));

          addSet (&indVars, newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));

          /* Replace mul/div with assignment to self; killDeadCode() will */
          /* clean this up since we can't use remiCodeFromeBBlock() here. */
          ic->op = '=';
          IC_LEFT (ic) = NULL;
          IC_RIGHT (ic) = IC_RESULT (ic);
          bitVectUnSetBit (OP_USES (aSym), ic->key);

          /* Insert an update of the induction variable just before */
          /* the update of the basic induction variable. */
          indIc = newiCode (ip->op, operandFromOperand (IC_RESULT (ic)), operandFromLit (litVal));
          IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
          owner = NULL;
          dic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner);
          assert (dic);
          addiCodeToeBBlock (owner, indIc, dic);
        }
    }

  /* if we have some induction variables then */
  if (indVars)
    {
      eBBlock *preHdr = loopReg->entry->preHeader;
      iCode *icFirst = NULL, *icLast = NULL;
      induction *ip;
      bitVect *indVect = NULL;

      /* create an iCode chain from it */
      for (ip = setFirstItem (indVars); ip; ip = setNextItem (indVars))
        {
          indVect = bitVectSetBit (indVect, ip->ic->key);
          ip->ic->filename = preHdr->ech->filename;
          ip->ic->lineno = preHdr->ech->lineno;
          if (!icFirst)
            icFirst = ip->ic;
          if (icLast)
            {
              icLast->next = ip->ic;
              ip->ic->prev = icLast;
              icLast = ip->ic;
            }
          else
            icLast = ip->ic;
          change++;
        }

      /* add the instruction chain to the end of the */
      /* preheader for this loop                     */
      preHdr->ech->next = icFirst;
      icFirst->prev = preHdr->ech;
      preHdr->ech = icLast;
      icLast->next = NULL;

      /* add the induction variable vector to the last
         block in the loop */
      lastBlock->isLastInLoop = 1;
      lastBlock->linds = bitVectUnion (lastBlock->linds, indVect);
    }

  setToNull ((void *) &indVars);
  return change;
}

/*-----------------------------------------------------------------*/
/* mergeRegions - will merge region with same entry point           */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (mergeRegions)
{
  region *theLoop = item;
  V_ARG (set *, allRegion);
  region *lp;

  /* if this has already been merged then do nothing */
  if (theLoop->merged)
    return 0;

  /* go thru all the region and check if any of them have the */
  /* entryPoint as the Loop                                  */
  for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
    {

      if (lp == theLoop)
        continue;

      if (lp->entry == theLoop->entry)
        {
          theLoop->regBlocks = unionSets (theLoop->regBlocks, lp->regBlocks, THROW_DEST);
          lp->merged = 1;
        }
    }

  return 1;
}

/*-----------------------------------------------------------------*/
/* ifMerged - return 1 if the merge flag is 1                      */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (ifMerged)
{
  region *lp = item;

  return lp->merged;
}

/*-----------------------------------------------------------------*/
/* mergeInnerLoops - will merge into body when entry is present    */
/*-----------------------------------------------------------------*/
static
DEFSETFUNC (mergeInnerLoops)
{
  region *theLoop = item;
  V_ARG (set *, allRegion);
  V_ARG (int *, maxDepth);
  region *lp;

  /* check if the entry point is present in the body of any */
  /* loop then put the body of this loop into the outer loop */
  for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
    {

      if (lp == theLoop)
        continue;

      if (isinSet (lp->regBlocks, theLoop->entry))
        {
          lp->containsLoops += theLoop->containsLoops + 1;
          if (lp->containsLoops > (*maxDepth))
            *maxDepth = lp->containsLoops;

          lp->regBlocks = unionSets (lp->regBlocks, theLoop->regBlocks, THROW_DEST);
        }
    }

  return 1;
}


/*-----------------------------------------------------------------*/
/* createLoopRegions - will detect and create a set of natural loops */
/*-----------------------------------------------------------------*/
hTab *
createLoopRegions (ebbIndex * ebbi)
{
  set *allRegion = NULL;        /* set of all loops */
  hTab *orderedLoops = NULL;
  set *bEdges = NULL;
  int maxDepth = 0;
  region *lp;

  /* get all the back edges in the graph */
  if (!applyToSet (graphEdges, backEdges, &bEdges))
    return 0;                   /* found no loops */

  /* for each of these back edges get the blocks that */
  /* constitute the loops                             */
  applyToSet (bEdges, createLoop, &allRegion);

  /* now we will create regions from these loops               */
  /* loops with the same entry points are considered to be the */
  /* same loop & they are merged. If the entry point of a loop */
  /* is found in the body of another loop then , all the blocks */
  /* in that loop are added to the loops containing the header */
  applyToSet (allRegion, mergeRegions, allRegion);

  /* delete those already merged */
  deleteItemIf (&allRegion, ifMerged);

  applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
  maxDepth++;

  /* now create all the exits .. also */
  /* create an ordered set of loops   */
  /* i.e. we process loops in the inner to outer order */
  for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
    {
      applyToSet (lp->regBlocks, addToExitsMarkDepth, lp->regBlocks, &lp->exits, (maxDepth - lp->containsLoops), lp);

      hTabAddItem (&orderedLoops, lp->containsLoops, lp);

    }
  return orderedLoops;
}

/*-----------------------------------------------------------------*/
/* loopOptimizations - identify region & remove invariants & ind   */
/*-----------------------------------------------------------------*/
int
loopOptimizations (hTab * orderedLoops, ebbIndex * ebbi)
{
  region *lp;
  int change = 0;
  int k;

  /* if no loop optimizations requested */
  if (!optimize.loopInvariant && !optimize.loopInduction)
    return 0;

  /* now we process the loops inner to outer order */
  /* this is essential to maintain data flow information */
  /* the other choice is an ugly iteration for the depth */
  /* of the loops would hate that */
  for (lp = hTabFirstItem (orderedLoops, &k); lp; lp = hTabNextItem (orderedLoops, &k))
    {

      if (optimize.loopInvariant)
        change += loopInvariants (lp, ebbi);

      if (optimize.loopInduction)
        change += loopInduction (lp, ebbi);
    }

  return change;
}