more about genUnpackBits

[fw/sdcc] / src / SDCClrange.c

diff --git a/src/SDCClrange.c b/src/SDCClrange.c
index 9207338affba3d2cc6a3a54d087461471bf41472..194d37a22bdad0b642bb2adfc8aec7306e9fb9f9 100644 (file)
--- a/src/SDCClrange.c
+++ b/src/SDCClrange.c
@@ -8,19 +8,19 @@
    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.
    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.
    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.
    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
    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!  
+   what you give them.   Help stamp out software-hoarding!

 -------------------------------------------------------------------------*/
 
 #include "common.h"
 -------------------------------------------------------------------------*/
 
 #include "common.h"


@@ -29,11 +29,28 @@
 int iCodeSeq = 0;
 hTab *liveRanges = NULL;
 hTab *iCodehTab = NULL;
 int iCodeSeq = 0;
 hTab *liveRanges = NULL;
 hTab *iCodehTab = NULL;

+hTab *iCodeSeqhTab = NULL;
+
+/*-----------------------------------------------------------------*/
+/* hashiCodeKeys - add all iCodes to the hash table                */
+/*-----------------------------------------------------------------*/
+void
+hashiCodeKeys (eBBlock ** ebbs, int count)
+{
+  int i;
+
+  for (i = 0; i < count; i++)
+    {
+      iCode *ic;
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+        hTabAddItem (&iCodehTab, ic->key, ic);
+    }
+}

 
 /*-----------------------------------------------------------------*/
 /* sequenceiCode - creates a sequence number for the iCode & add   */
 /*-----------------------------------------------------------------*/
 
 /*-----------------------------------------------------------------*/
 /* sequenceiCode - creates a sequence number for the iCode & add   */
 /*-----------------------------------------------------------------*/

-void 
+void

 sequenceiCode (eBBlock ** ebbs, int count)
 {
   int i;
 sequenceiCode (eBBlock ** ebbs, int count)
 {
   int i;


@@ -47,112 +64,17 @@ sequenceiCode (eBBlock ** ebbs, int count)
        {
          ic->seq = ++iCodeSeq;
          ic->depth = ebbs[i]->depth;
        {
          ic->seq = ++iCodeSeq;
          ic->depth = ebbs[i]->depth;

-         hTabAddItem (&iCodehTab, ic->key, ic);
+         //hTabAddItem (&iCodehTab, ic->key, ic);
+         hTabAddItem (&iCodeSeqhTab, ic->seq, ic);

        }
       ebbs[i]->lSeq = iCodeSeq;
     }
 }
 
        }
       ebbs[i]->lSeq = iCodeSeq;
     }
 }
 

-/*-----------------------------------------------------------------*/
-/* markVisited - will set the visited flag for the given Block     */
-/*-----------------------------------------------------------------*/
-DEFSETFUNC (markVisited)
-{
-  eBBlock *ebp = item;
-
-  if (ebp->visited)
-    return 0;
-  ebp->visited = 1;
-  applyToSet (ebp->succList, markVisited);
-  return 0;
-}
-
-/*-----------------------------------------------------------------*/
-/* isOpAlive - checks to see if the usage in this block is the     */
-/*             uses the same definitions as this one               */
-/*-----------------------------------------------------------------*/
-DEFSETFUNC (isOpAlive)
-{
-  eBBlock *ebp = item;
-  V_ARG (operand *, op);
-  V_ARG (eBBlock *, orig);
-  V_ARG (iCode *, ic);
-
-  if (ebp->visited)
-    return 0;
-
-  ebp->visited = 1;
-
-  /* if we have reached the originating block */
-  /* or this block has some definiton for it  */
-  /* then check if it is used between start & */
-  /* this point */
-  if (ebp == orig ||
-      bitVectBitsInCommon (OP_DEFS (op), ebp->defSet))
-    if (usedBetweenPoints (op, ebp->sch, ic))
-      return 1;
-    else
-      {
-       applyToSet (ebp->succList, markVisited);
-       return 0;
-      }
-  else
-    /* choosing this more expensive one since 
-       killDeadCode will take away some definitions
-       but there is not way right now to take away
-       the usage information for the corresponding
-       usages, this will lead to longer live ranges */
-  if (usedInRemaining (op, ebp->sch))
-    return 1;
-
-
-  return (applyToSet (ebp->succList, isOpAlive, op, orig, ic));
-}
-
-/*-----------------------------------------------------------------*/
-/* isLastUse - return TRUE if no usage of this operand after this  */
-/*-----------------------------------------------------------------*/
-int 
-isLastUse (operand * op, eBBlock * ebp, iCode * ic,
-          eBBlock ** ebbs, int count)
-{
-  int i;
-
-  /* if this is used in the remaining */
-  if (usedInRemaining (op, ic))
-    return 0;
-
-  /* if not then check any of the successor blocks use it */
-  for (i = 0; i < count; ebbs[i++]->visited = 0);
-  if (applyToSet (ebp->succList, isOpAlive, op, ebp, ic))
-    return 0;
-
-  /* this is the last use */
-  return 1;
-}
-
-/*-----------------------------------------------------------------*/
-/* unionDefsUsed - unions the defsUsed in a block                  */
-/*-----------------------------------------------------------------*/
-DEFSETFUNC (unionDefsUsed)
-{
-  eBBlock *ebp = item;
-  V_ARG (bitVect **, bvp);
-
-  if (ebp->visited)
-    return 0;
-
-  ebp->visited = 1;
-
-  *bvp = bitVectUnion (*bvp, ebp->usesDefs);
-  applyToSet (ebp->succList, unionDefsUsed, bvp);
-  return 0;
-}
-

 /*-----------------------------------------------------------------*/
 /* setFromRange - sets the from range of a given operand           */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
 /* setFromRange - sets the from range of a given operand           */
 /*-----------------------------------------------------------------*/

-void 
+void

 setFromRange (operand * op, int from)
 {
   /* only for compiler defined temporaries */
 setFromRange (operand * op, int from)
 {
   /* only for compiler defined temporaries */


@@ -172,7 +94,7 @@ setFromRange (operand * op, int from)
 /*-----------------------------------------------------------------*/
 /* setToRange - set the range to for an operand                    */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
 /* setToRange - set the range to for an operand                    */
 /*-----------------------------------------------------------------*/

-void 
+void

 setToRange (operand * op, int to, bool check)
 {
   /* only for compiler defined temps */
 setToRange (operand * op, int to, bool check)
 {
   /* only for compiler defined temps */


@@ -194,378 +116,575 @@ setToRange (operand * op, int to, bool check)
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/

-/* firstDeOf - finds the first definition in seq for op            */
+/* setFromRange - sets the from range of a given operand           */

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

-static iCode *
-firstDefOf (operand * op)
+void
+setLiveFrom (symbol * sym, int from)

 {
 {

-  int i;
-  iCode *ric = NULL, *lic = NULL;
-  int fSeq = INT_MAX;
-
-  if (!OP_DEFS (op))
-    return NULL;
-
-  for (i = 0; i < OP_DEFS (op)->size; i++)
-    {
-      if (bitVectBitValue (OP_DEFS (op), i) &&
-         (lic = hTabItemWithKey (iCodehTab, i)) &&
-         lic->seq < fSeq)
-       {
+  if (!sym->liveFrom || sym->liveFrom > from)
+    sym->liveFrom = from;
+}

 
 

-         fSeq = lic->seq;
-         ric = lic;
-       }
-    }
-  return ric;
+/*-----------------------------------------------------------------*/
+/* setToRange - set the range to for an operand                    */
+/*-----------------------------------------------------------------*/
+void
+setLiveTo (symbol * sym, int to)
+{
+  if (!sym->liveTo || sym->liveTo < to)
+    sym->liveTo = to;

 }
 }

+

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

-/* useDefLoopCheck - check for uses before init inside loops       */
+/* markLiveRanges - for each operand mark the liveFrom & liveTo    */

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

-static void 
-useDefLoopCheck (operand * op, iCode * ic)
+void
+markLiveRanges (eBBlock ** ebbs, int count)

 {
 {

-  /* this is for situations like the following
-     int a,b;
-
-     while (...) {
-     a = ... ;
-     ...
-     _some_usage_of_b_;
-     ...
-     b = ... ;
-     } 
-     in this case the definition of 'b' will flow to the usages
-     but register allocator cannot handle these situations.so
-     will mark as spilt */
-
-  int i = 0, fdSeq;
-  int er = 0;
-  iCode *tic;
-
-  /* get the first definition */
-  if (!(tic = firstDefOf (op)))
-    return;
+  int i, key;
+  symbol *sym;

 
 

-  fdSeq = tic->seq;
-  /* now go thru the usages & make sure they follow
-     the first definition */
-  for (i = 0; i <= OP_USES (op)->size; i++)
+  for (i = 0; i < count; i++)

     {
     {

-      if (bitVectBitValue (OP_USES (op), i) &&
-         (tic = hTabItemWithKey (iCodehTab, i)) &&
-         tic->seq < fdSeq)
-       {
-         er = 1;
-         break;
-       }
-    }
+      iCode *ic;

 
 

-  /* found a usage without definition */
-  if (er)
-    {
-      if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
-       {
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+        {
+         if (ic->op == CALL || ic->op == PCALL)
+           if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
+              bitVectUnSetBit (ebbs[i]->defSet, ic->key);

 
 

-         werror (W_LOCAL_NOINIT,
-                 SPIL_LOC (op)->name,
-                 ic->filename, ic->lineno);
-       }
-      else
-       {
+         /* for all iTemps alive at this iCode */
+         for (key = 1; key < ic->rlive->size; key++)
+           {
+             if (!bitVectBitValue(ic->rlive, key))
+               continue;
+
+             sym = hTabItemWithKey(liveRanges, key);
+             setLiveTo(sym, ic->seq);
+             setLiveFrom(sym, ic->seq);
+           }

 
 

-         werror (W_LOCAL_NOINIT,
-                 OP_SYMBOL (op)->name,
-                 ic->filename, ic->lineno);

        }
        }

-      OP_SYMBOL (op)->isspilt = 1;

     }
 }
 
     }
 }
 

-

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

-/* operandLUse - check and set the last use for a given operand    */
+/* markAlive - marks the operand as alive between sic and eic      */

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

-operand *
-operandLUse (operand * op, eBBlock ** ebbs,
-            int count, iCode * ic, eBBlock * ebp)
+void
+markAlive (iCode * sic, iCode * eic, int key)

 {
 {

-  setFromRange (op, ic->seq);
-  if (ic->depth)
-    OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
-  else
-    OP_SYMBOL (op)->used += 1;
+  iCode *dic;

 
 

-  if (isLastUse (op, ebp, ic->next, ebbs, count) ||
-      (OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
+  for (dic = sic; dic != eic->next; dic = dic->next)

     {
     {

-      int torange = ic->seq;
-      /* if this is the last use then if this block belongs 
-         to a  loop &  some definition  comes into the loop 
-         then extend the live range to  the end of the loop */
-      if (ebp->partOfLoop 
-         && hasIncomingDefs (ebp->partOfLoop, op))
-       {
-         torange = findLoopEndSeq (ebp->partOfLoop);
-       }
-      op = operandFromOperand (op);
-      setToRange (op, torange, FALSE);
+      dic->rlive = bitVectSetBit (dic->rlive, key);

     }
     }

-  ic->uses = bitVectSetBit (ic->uses, op->key);
+}

 
 

-  if (!OP_SYMBOL (op)->udChked)
+/*-----------------------------------------------------------------*/
+/* findNextUseSym - finds the next use of the symbol and marks it  */
+/*                  alive in between                               */
+/*-----------------------------------------------------------------*/
+int
+findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
+{
+  int retval = 0;
+  iCode *uic;
+  eBBlock *succ;
+
+  hTabAddItemIfNotP (&liveRanges, sym->key, sym);
+
+  if (!ic)
+    goto check_successors;
+
+  /* if we check a complete block and the symbol */
+  /* is alive at the beginning of the block */
+  /* and not defined in the first instructions */
+  /* then a next use exists (return 1) */
+  if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))

     {
     {

-      sym_link *type = operandType (op);
-      sym_link *etype = getSpec (type);
-
-      OP_SYMBOL (op)->udChked = 1;
-      /* good place to check if unintialised */
-      if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
-         OP_SYMBOL (op)->islocal &&
-         !IS_AGGREGATE (type) &&
-         !IS_FUNC (type) &&
-         ic->op != ADDRESS_OF &&
-         !IS_STATIC (etype))
-       {
+      /* check if the first instruction is a def of this op */
+      if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
+        return 1;

 
 

-         if (bitVectIsZero (op->usesDefs))
-           {
-             OP_SYMBOL (op)->isspilt = 1;
+      if (IS_ITEMP(IC_RESULT(ic)))
+        if (IC_RESULT(ic)->key == sym->key)
+         return 0;
+
+      return 1;
+    }

 
 

-             if (OP_SYMBOL (op)->isreqv &&
-                 !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
-               {
+  if (ebp->visited)
+    return 0;

 
 

-                 werror (W_LOCAL_NOINIT,
-                         SPIL_LOC (op)->name,
-                         ic->filename, ic->lineno);
-               }
-             else
-               {
+  if (ic == ebp->sch)
+    ebp->visited = 1;

 
 

-                 werror (W_LOCAL_NOINIT,
-                         OP_SYMBOL (op)->name,
-                         ic->filename, ic->lineno);
-               }
+  /* for all remaining instructions in current block */
+  for (uic = ic; uic; uic = uic->next)
+    {
+
+      if (SKIP_IC2(uic))
+        continue;
+
+      if (uic->op == JUMPTABLE)
+        {
+          if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
+            {
+             markAlive(ic, uic, sym->key);
+             return 1;

            }
            }

-         else
-           {
-             if (ebp->depth && op->usesDefs &&
-                 !OP_SYMBOL (op)->_isparm)
-               {
-                 /* check non-inits inside loops */
-                 useDefLoopCheck (op, ic);
-               }
+          continue;
+       }
+
+      if (uic->op == IFX)
+        {
+          if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
+            {
+             markAlive(ic, uic, sym->key);
+             return 1;

            }
            }

+          continue;

        }
        }

+
+      if (IS_ITEMP (IC_LEFT (uic)))
+        if (IC_LEFT (uic)->key == sym->key)
+          {
+           markAlive(ic, uic, sym->key);
+           return 1;
+         }
+
+      if (IS_ITEMP (IC_RIGHT (uic)))
+        if (IC_RIGHT (uic)->key == sym->key)
+         {
+           markAlive (ic, uic, sym->key);
+           return 1;
+         }
+
+      if (IS_ITEMP (IC_RESULT (uic)))
+        if (IC_RESULT (uic)->key == sym->key)
+         {
+           if (POINTER_SET (uic))
+             {
+               markAlive (ic, uic, sym->key);
+                return 1;
+             }
+           else
+             return 0;
+         }
+
+    }
+
+  /* check all successors */
+check_successors:
+
+  succ = setFirstItem (ebp->succList);
+  for (; succ; succ = setNextItem (ebp->succList))
+    {
+      retval += findNextUseSym (succ, succ->sch, sym);
+    }
+
+  if (retval)
+    {
+      if (ic) markAlive (ic, ebp->ech, sym->key);
+      return 1;

     }
     }

-  return op;
+
+  return 0;

 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/

-/* killAllAlive - mark all the definitions living with this seq    */
+/* findNextUse - finds the next use of the operand and marks it    */
+/*               alive in between                                  */

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

-void 
-killAllAlive (int seq)
+int
+findNextUse (eBBlock *ebp, iCode *ic, operand *op)

 {
 {

-  symbol *sym;
-  int k;
+  if (op->isaddr)
+    OP_SYMBOL (op)->isptr = 1;
+
+  OP_SYMBOL (op)->key = op->key;

 
 

-  for (sym = hTabFirstItem (liveRanges, &k); sym;
-       sym = hTabNextItem (liveRanges, &k))
-    if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
-      sym->liveTo = seq;
+  return findNextUseSym (ebp, ic, OP_SYMBOL(op));

 }
 }

+

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

-/* defUsedAfterLoop - all definitions & usages before sequence num */
+/* unvisitBlocks - clears visited in all blocks                    */

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

-bool 
-defUsedAfterLoop (operand * op, int seq)
+void unvisitBlocks (eBBlock ** ebbs, int count)
+{
+  int i;
+
+  for (i = 0; i < count; i++)
+    ebbs[i]->visited = 0;
+}
+
+/*------------------------------------------------------------------*/
+/* findRecursiveSucc - build a bit vector of recursive successors   */
+/*------------------------------------------------------------------*/
+DEFSETFUNC (findRecursiveSucc)
+{
+  eBBlock *ebp = item;
+  V_ARG (bitVect *, succVect);
+  
+  if (ebp->visited)
+    return 0;
+  
+  ebp->visited = 1;
+  bitVectSetBit (succVect, ebp->bbnum);
+  applyToSet (ebp->succList, findRecursiveSucc, succVect);
+  return 0;
+}
+
+
+/*------------------------------------------------------------------*/
+/* findRecursivePred - build a bit vector of recursive predecessors */
+/*------------------------------------------------------------------*/
+DEFSETFUNC (findRecursivePred)
+{
+  eBBlock *ebp = item;
+  V_ARG (bitVect *, predVect);
+  
+  if (ebp->visited)
+    return 0;
+  
+  ebp->visited = 1;
+  bitVectSetBit (predVect, ebp->bbnum);
+  applyToSet (ebp->predList, findRecursivePred, predVect);
+  return 0;
+}
+
+
+/*------------------------------------------------------------------*/
+/* findPrevUse - handle degenerate case of a symbol used prior to   */
+/*               findNextUse() marking any definition.              */
+/*------------------------------------------------------------------*/
+void
+findPrevUse (eBBlock *ebp, iCode *ic, operand *op, eBBlock **ebbs, int count)

 {
   int i;
 {
   int i;

-  iCode *ic;
+  bitVect * succVect;
+  bitVect * predVect;
+  eBBlock * pred;
+
+  /* If liveness is already known, then a previous call to findNextUse() */
+  /* has already taken care of everything. */
+  if (ic && bitVectBitValue(ic->rlive, op->key))
+    return;

 
 

-  /* check for the usages first */
-  if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
+  if (!ic)

     {
     {

-      for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
-       {
+      /* We are at the start of a block. If the operand is alive at the */
+      /* end of all predecessors, then a previous call to findNextUse() */
+      /* has already taken care of everything. */
+      
+      pred = setFirstItem (ebp->predList);
+      for (; pred; pred = setNextItem (ebp->predList))
+        if (pred->ech && !bitVectBitValue(pred->ech->rlive, op->key))
+          break;
+      
+      if (!pred)
+        return;
+    }

 
 

-         if (bitVectBitValue (OP_SYMBOL (op)->uses, i) &&      /* usage found */
-             (ic = hTabItemWithKey (iCodehTab, i)) &&  /*    ""       */
-             ic->seq > seq)    /* & is after the seq */
-           return TRUE;
-       }
+  if (op->isaddr)
+    OP_SYMBOL (op)->isptr = 1;
+
+  OP_SYMBOL (op)->key = op->key;
+
+  /* Otherwise, it appears that this symbol was used prior to definition.     */
+  /* Just fix the live range; we'll deal with a diagnostic message elsewhere. */
+  /* If the symbol use was in a loop, we need to extend the live range to the */
+  /* outermost loop. */
+  unvisitBlocks (ebbs, count);
+  succVect = newBitVect (count);
+  applyToSet (ebp->succList, findRecursiveSucc, succVect);
+  unvisitBlocks (ebbs, count);
+  predVect = newBitVect (count);
+  applyToSet (ebp->predList, findRecursivePred, predVect);
+
+  /* Blocks that are both recursively predecessors and successors are in */
+  /* a loop with the current iCode. Mark the operand as alive in them.   */
+  for (i = 0; i < count; i++)
+    {
+      if (bitVectBitValue(succVect, i) && bitVectBitValue(predVect, i))
+        markAlive (ebbs[i]->sch, ebbs[i]->ech, op->key);

     }
 
     }
 

-  return FALSE;
+  freeBitVect (succVect);
+  freeBitVect (predVect);

 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/

-/* markLiveRanges - for each operand mark the liveFrom & liveTo    */
+/* incUsed - increment a symbol's usage count                      */
+/*-----------------------------------------------------------------*/
+void
+incUsed (iCode *ic, operand *op)
+{
+  if (ic->depth)
+    OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
+  else
+    OP_SYMBOL (op)->used += 1;
+}
+
+/*-----------------------------------------------------------------*/
+/* rliveClear - clears the rlive bitVectors                        */

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

-void 
-markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
+void
+rliveClear (eBBlock ** ebbs, int count)

 {
 {

-  iCode *ic;
-  bitVect *defsUsed = NULL;
-  bitVect *defsNotUsed = NULL;

   int i;
   int i;

-  /* for all the instructions */
-  for (ic = ebp->sch; ic; ic = ic->next)
+
+  /* for all blocks do */
+  for (i = 0; i < count; i++)

     {
     {

+      iCode *ic;

 
 

-      if (ic->op == CALL || ic->op == PCALL)
-       {
-         setFromRange (IC_RESULT (ic), ic->seq);
-         /* if the result has no usage then 
-            mark this as the end of its life too 
-            and take it away from the defs for the block */
-         if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
-           {
-             setToRange (IC_RESULT (ic), ic->seq, FALSE);
-             bitVectUnSetBit (ebp->defSet, ic->key);
-           }
+      /* for all instructions in this block do */
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+        {
+         freeBitVect (ic->rlive);
+         ic->rlive = NULL;

        }
        }

+    }
+}

 
 

-      if (SKIP_IC2 (ic))
-       continue;
+/*-----------------------------------------------------------------*/
+/* rlivePoint - for each point compute the ranges that are alive   */
+/*-----------------------------------------------------------------*/
+void
+rlivePoint (eBBlock ** ebbs, int count)
+{
+  int i, key;
+  eBBlock *succ;
+  bitVect *alive;

 
 

-      /* take care of the special icodes first */
-      if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
-       {
-         operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
-         continue;
-       }
+  /* for all blocks do */
+  for (i = 0; i < count; i++)
+    {
+      iCode *ic;

 
 

-      if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
-       {
-         operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
-         continue;
-       }
+      /* for all instructions in this block do */
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+        {

 
 

-      if (IS_SYMOP (IC_LEFT (ic)))
-       operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
+         if (!ic->rlive)
+           ic->rlive = newBitVect (operandKey);

 
 

-      if (IS_SYMOP (IC_RIGHT (ic)))
-       operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
+         if (SKIP_IC2(ic))
+           continue;

 
 

-      if (POINTER_SET (ic))
-       operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
-      else if (IC_RESULT (ic))
-       ic->defKey = IC_RESULT (ic)->key;
-    }
+         if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
+           {
+             incUsed (ic, IC_JTCOND(ic));

 
 

+             if (!IS_ITEMP(IC_JTCOND(ic)))
+               continue;

 
 

-  /* for all the definitions in the block */
-  /* compute and set the live from        */
-  if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
-    {
-      for (i = 0; i < ebp->ldefs->size; i++)
-       {
-         iCode *dic;
+             findPrevUse (ebbs[i], ic->prev, IC_JTCOND(ic), ebbs, count);
+             unvisitBlocks(ebbs, count);
+             ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
+             findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
+
+             continue;
+           }

 
 

-         if (bitVectBitValue (ebp->ldefs, i) &&
-             (dic = hTabItemWithKey (iCodehTab, i)))
+         if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))

            {
            {

+             incUsed (ic, IC_COND(ic));

 
 

-             /* if the definition has a from & it is greater */
-             /* than the defininng iCode->seq then change it */
-             setFromRange (IC_RESULT (dic), dic->seq);
+             if (!IS_ITEMP(IC_COND(ic)))
+               continue;
+
+             findPrevUse (ebbs[i], ic->prev, IC_COND(ic), ebbs, count);
+             unvisitBlocks (ebbs, count);
+             ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
+             findNextUse (ebbs[i], ic->next, IC_COND(ic));
+
+             continue;

            }
            }

-       }
-    }

 
 

-  /* special case for lastBlock in a loop: here we
-     mark the end of all the induction variables for the
-     loop */
-  if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
-    {
-      for (i = 0; i <= ebp->linds->size; i++)
-       {
-         iCode *dic;
+         if (IS_SYMOP(IC_LEFT(ic)))
+           {
+             incUsed (ic, IC_LEFT(ic));
+             if (IS_ITEMP(IC_LEFT(ic)))
+               {
+
+                 findPrevUse (ebbs[i], ic->prev, IC_LEFT(ic), ebbs, count);
+                 unvisitBlocks(ebbs, count);
+                 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
+                 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
+
+                 /* if this is a send extend the LR to the call */
+                 if (ic->op == SEND)
+                   {
+                     iCode *lic;
+                     for (lic = ic; lic; lic = lic->next)
+                       {
+                         if (lic->op == CALL || lic->op == PCALL)
+                           {
+                             markAlive (ic, lic->prev, IC_LEFT (ic)->key);
+                             break;
+                           }
+                       }
+                   }
+               }
+//                fprintf(stderr, "%s:%d IS_SYMOP left\t", __FILE__, __LINE__);printOperand(IC_LEFT(ic), stderr);
+//                fprintf(stderr, "\n");
+           }

 
 

-         if (bitVectBitValue (ebp->linds, i) &&
-             (dic = hTabItemWithKey (iCodehTab, i)))
+         if (IS_SYMOP(IC_RIGHT(ic)))

            {
            {

+             incUsed (ic, IC_RIGHT(ic));
+             if (IS_ITEMP(IC_RIGHT(ic)))
+               {
+                 findPrevUse (ebbs[i], ic->prev, IC_RIGHT(ic), ebbs, count);
+                 unvisitBlocks(ebbs, count);
+                 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
+                 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
+               }
+//                fprintf(stderr, "%s:%d IS_SYMOP right\t", __FILE__, __LINE__);printOperand(IC_RIGHT(ic), stderr);
+//                fprintf(stderr, "\n");
+           }

 
 

-             /* if this is a register equvalent make sure
-                it is not defined or used anywhere after the loop */
-             if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
-                 defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
-               continue;
+         if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
+           incUsed (ic, IC_RESULT(ic));

 
 

-             setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
+         if (IS_ITEMP(IC_RESULT(ic)))
+           {
+             if (POINTER_SET(ic))
+               {
+                 findPrevUse (ebbs[i], ic->prev, IC_RESULT(ic), ebbs, count);
+               }
+             unvisitBlocks(ebbs, count);
+             ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
+             findNextUse (ebbs[i], ic->next, IC_RESULT(ic));

            }
            }

+
+         if (!POINTER_SET(ic) && IC_RESULT(ic))
+           ic->defKey = IC_RESULT(ic)->key;
+

        }
        }

-    }

 
 

-  /* for defnitions coming into the block if they */
-  /* not used by itself & any of its successors   */
-  /* they are dead */
-  /* first union the definitions used in all successors
-     and itself */
-  for (i = 0; i < count; ebbs[i++]->visited = 0);
-  applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
-  defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
-
-  /* now subract the result of these unions from */
-  /* the incoming definitions this will give the */
-  /* definitions that are never used in the future */
-  defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
-                              defsUsed);
-
-  /* mark the end of the defintions */
-  if (!bitVectIsZero (defsNotUsed) && ebp->sch)
-    {
-      for (i = 0; i < defsNotUsed->size; i++)
-       {
-         iCode *dic;
+      /* check all symbols that are alive in the last instruction */
+      /* but are not alive in all successors */

 
 

-         if (bitVectBitValue (defsNotUsed, i) &&
-             (dic = hTabItemWithKey (iCodehTab, i)))
-           {
+      succ = setFirstItem (ebbs[i]->succList);
+      if (!succ)
+        continue;

 
 

-             setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
-           }
+      alive = succ->sch->rlive;
+      while ((succ = setNextItem (ebbs[i]->succList)))
+        {
+         if (succ->sch)
+            alive = bitVectIntersect (alive, succ->sch->rlive);

        }
        }

-    }

 
 

+      if (ebbs[i]->ech)
+        alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
+
+      if(!alive)
+        continue;
+      for (key = 1; key < alive->size; key++)
+        {
+         if (!bitVectBitValue (alive, key))
+           continue;
+
+         unvisitBlocks(ebbs, count);
+         findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
+       }

 
 

-  /* if we reach a lock with noPath to it then kill all
-     the live ranges alive at this point */
-/*     if (ebp->noPath || ebp->entryLabel == returnLabel) */
-  if (ebp->entryLabel == returnLabel)
-    killAllAlive (ebp->fSeq);
+    }

 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/

-/* rlivePoint - for each point compute the ranges that are alive   */
+/* computeClash - find out which live ranges collide with others   */

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

-void 
-rlivePoint (eBBlock ** ebbs, int count)
+static void
+computeClash (eBBlock ** ebbs, int count)

 {
 {

-    int i;
-    
-    /* for all blocks do */
-    for (i = 0; i < count; i++) {
-       iCode *ic;
-       
-       /* for all instruction in the block do */
-       for (ic = ebbs[i]->sch; ic; ic = ic->next) {
-           symbol *lrange;
-           int k;
-           
-           ic->rlive = newBitVect (operandKey);
-           /* for all symbols in the liverange table */
-           for (lrange = hTabFirstItem (liveRanges, &k); lrange;
-                lrange = hTabNextItem (liveRanges, &k)) {
-               
-               /* if it is live then add the lrange to ic->rlive */
-               if (lrange->liveFrom <= ic->seq &&
-                   lrange->liveTo >= ic->seq) {
-                   lrange->isLiveFcall |= (ic->op == CALL || ic->op == PCALL || ic->op == SEND);
-                   ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
+  int i;
+
+  /* for all blocks do */
+  for (i = 0; i < count; i++)
+    {
+      iCode *ic;
+
+      /* for every iCode do */
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+       {
+         symbol *sym1, *sym2;
+         int key1, key2;
+
+         /* for all iTemps alive at this iCode */
+         for (key1 = 1; key1 < ic->rlive->size; key1++)
+           {
+             if (!bitVectBitValue(ic->rlive, key1))
+               continue;
+
+             sym1 = hTabItemWithKey(liveRanges, key1);
+
+             if (!sym1->isitmp)
+               continue;
+
+             /* for all other iTemps alive at this iCode */
+             for (key2 = key1+1; key2 < ic->rlive->size; key2++)
+               {
+                 if (!bitVectBitValue(ic->rlive, key2))
+                   continue;
+
+                 sym2 = hTabItemWithKey(liveRanges, key2);
+
+                 if (!sym2->isitmp)
+                   continue;
+
+                 /* if the result and left or right is an iTemp */
+                 /* than possibly the iTemps do not clash */
+                 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
+                     IS_ITEMP(IC_RESULT(ic)) &&
+                     (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
+                   {
+                     if (OP_SYMBOL(IC_RESULT(ic))->key == key1
+                         && sym1->liveFrom == ic->seq
+                         && sym2->liveTo == ic->seq)
+                       {
+                         if (IS_SYMOP(IC_LEFT(ic)))
+                           if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
+                             continue;
+                         if (IS_SYMOP(IC_RIGHT(ic)))
+                           if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
+                             continue;
+                       }
+
+                     if (OP_SYMBOL(IC_RESULT(ic))->key == key2
+                         && sym2->liveFrom == ic->seq
+                         && sym1->liveTo == ic->seq)
+                       {
+                         if (IS_SYMOP(IC_LEFT(ic)))
+                           if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
+                             continue;
+                         if (IS_SYMOP(IC_RIGHT(ic)))
+                           if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
+                             continue;
+                       }
+                   }
+
+                 /* the iTemps do clash. set the bits in clashes */
+                 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
+                 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
+
+                 /* check if they share the same spill location */
+                 /* what is this good for? */
+                 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
+                     SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
+                   {
+                     if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
+                     else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
+                     else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
+                     else SYM_SPIL_LOC(sym1)=NULL;
+                   }

                }
            }
        }
                }
            }
        }


@@ -573,83 +692,129 @@ rlivePoint (eBBlock ** ebbs, int count)
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/

-/* computeClash - find out which live ranges collide with others   */
+/* allDefsOutOfRange - all definitions are out of a range          */

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

-static void computeClash ()
+bool
+allDefsOutOfRange (bitVect * defs, int fseq, int toseq)

 {
 {

-    hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
-    void *item;
-    symbol *outer, *inner;
-    int key, key1;
-
-    /* have to make a copy of the liveRanges hashTable :: UGHH .*/
-    for (item = hTabFirstItem(liveRanges,&key); item ; 
-        item = hTabNextItem(liveRanges,&key)) {
-       hTabAddItem(&lRangeCopy,key,item);
+  int i;
+
+  if (!defs)
+    return TRUE;
+
+  for (i = 0; i < defs->size; i++)
+    {
+      iCode *ic;
+
+      if (bitVectBitValue (defs, i) &&
+         (ic = hTabItemWithKey (iCodehTab, i)) &&
+         (ic->seq >= fseq && ic->seq <= toseq))
+       return FALSE;
+

     }
     }

-   
-    /* outerloop : for each liverange do */
-    for (outer = hTabFirstItem(liveRanges,&key); outer ; 
-        outer = hTabNextItem(liveRanges,&key)) {
-
-       /* if the liveFrom & To are the same then skip, 
-          could happen for unused return values from functions */
-       if (outer->liveFrom == outer->liveTo) continue;
-
-       /* innerloop : for the inner loop we can start from the
-          item after the outer loop */
-       inner = hTabFirstItemWK (lRangeCopy,outer->key);
-       inner = hTabNextItem (lRangeCopy,&key1 );
-       for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
-
-           if (inner->liveFrom == inner->liveTo) continue;
-           if (inner->liveTo < outer->liveFrom)  continue;
-           if (inner->liveFrom > outer->liveTo)  continue;
-           
-           /* if one of them are being defined where the other
-              one end , then no overlap (i.e. they can goto same registers */
-           if (inner->liveFrom == outer->liveTo ||
-               outer->liveFrom == inner->liveTo) continue;
-
-           /* so they overlap : set both their clashes */
-           inner->clashes = bitVectSetBit(inner->clashes,outer->key);
-           outer->clashes = bitVectSetBit(outer->clashes,inner->key);
-           
-           /* check if they share the same spillocation */
-           if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer)) {
-               if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
-               else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
-               else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
-               else SYM_SPIL_LOC(inner)=NULL;
-           }
-       }
+
+  return TRUE;
+}
+
+/*-----------------------------------------------------------------*/
+/* notUsedInBlock - not used in this block                         */
+/*-----------------------------------------------------------------*/
+int
+notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
+{
+  return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
+         allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
+         allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
+}
+
+/*-----------------------------------------------------------------*/
+/* adjustIChain - correct the sch and ech pointers                 */
+/*-----------------------------------------------------------------*/
+void
+adjustIChain (eBBlock ** ebbs, int count)
+{
+  int i;
+
+  for (i = 0; i < count; i++)
+    {
+      iCode *ic;
+
+      if (ebbs[i]->noPath)
+        continue;
+
+      ic = ebbs[i]->sch;
+
+      /* is there any code for this eBBlock? (e.g. ROM assignment) */
+      if(!ic)continue;
+
+      while (ic->prev)
+        ic = ic->prev;
+      ebbs[i]->sch = ic;
+
+      ic = ebbs[i]->ech;
+      while (ic->next)
+        ic = ic->next;
+      ebbs[i]->ech = ic;

     }
 }
 
 /*-----------------------------------------------------------------*/
 /* computeLiveRanges - computes the live ranges for variables      */
 /*-----------------------------------------------------------------*/
     }
 }
 
 /*-----------------------------------------------------------------*/
 /* computeLiveRanges - computes the live ranges for variables      */
 /*-----------------------------------------------------------------*/

-void 
+void

 computeLiveRanges (eBBlock ** ebbs, int count)
 {
 computeLiveRanges (eBBlock ** ebbs, int count)
 {

-  int i = 0;
-  /* sequence the code the live ranges are computed 
-     in terms of this sequence additionally the   
+  /* first look through all blocks and adjust the
+     sch and ech pointers */
+  adjustIChain (ebbs, count);
+
+  /* sequence the code the live ranges are computed
+     in terms of this sequence additionally the

      routine will also create a hashtable of instructions */
   iCodeSeq = 0;
      routine will also create a hashtable of instructions */
   iCodeSeq = 0;

-  setToNull ((void **) &iCodehTab);
+  setToNull ((void *) &iCodehTab);

   iCodehTab = newHashTable (iCodeKey);
   iCodehTab = newHashTable (iCodeKey);

+  hashiCodeKeys (ebbs, count);
+  setToNull ((void *) &iCodeSeqhTab);
+  iCodeSeqhTab = newHashTable (iCodeKey);

   sequenceiCode (ebbs, count);
 
   sequenceiCode (ebbs, count);
 

-  /* call routine to mark the from & to live ranges for
-     variables used */
-  setToNull ((void **) &liveRanges);
-  for (i = 0; i < count; i++)
-    markLiveRanges (ebbs[i], ebbs, count);
-

   /* mark the ranges live for each point */
   /* mark the ranges live for each point */

+  setToNull ((void *) &liveRanges);

   rlivePoint (ebbs, count);
 
   rlivePoint (ebbs, count);
 

+  /* mark the from & to live ranges for variables used */
+  markLiveRanges (ebbs, count);
+

   /* compute which overlaps with what */
   /* compute which overlaps with what */

-  computeClash();
+  computeClash(ebbs, count);

 }
 }

+
+/*-----------------------------------------------------------------*/
+/* recomputeLiveRanges - recomputes the live ranges for variables  */
+/*-----------------------------------------------------------------*/
+void
+recomputeLiveRanges (eBBlock ** ebbs, int count)
+{
+  symbol * sym;
+  int key;
+
+  /* clear all rlive bitVectors */
+  rliveClear (ebbs, count);
+
+  sym = hTabFirstItem (liveRanges, &key);
+  if (sym)
+    {
+      do {
+        sym->used = 0;
+        sym->liveFrom = 0;
+        sym->liveTo = 0;
+        freeBitVect (sym->clashes);
+        sym->clashes = NULL;
+      } while ( (sym = hTabNextItem (liveRanges, &key)));
+    }
+
+  /* do the LR computation again */
+  computeLiveRanges (ebbs, count);
+}
+