projects / fw / sdcc / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Large cummulative patch for pic16 port.
[fw/sdcc] / src / SDCClrange.c
diff --git a/src/SDCClrange.c b/src/SDCClrange.c
index eea9a0751f7958277bc042ed43411a5be17ccc35..d99df74ce0928b5c5f04ff77715a61b1342e1290 100644 (file)
--- a/src/SDCClrange.c
+++ b/src/SDCClrange.c
@@ -8,498 +8,809 @@
    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"
+#include "limits.h"
 
 
-int iCodeSeq = 0 ;
+int iCodeSeq = 0;
 hTab *liveRanges = NULL;
 hTab *iCodehTab = NULL;
 hTab *liveRanges = NULL;
 hTab *iCodehTab = NULL;
+hTab *iCodeSeqhTab = NULL;
 
 /*-----------------------------------------------------------------*/
 
 /*-----------------------------------------------------------------*/
-/* sequenceiCode - creates a sequence number for the iCode & add   */
+/* hashiCodeKeys - add all iCodes to the hash table                */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void sequenceiCode (eBBlock **ebbs, int count)
+void
+hashiCodeKeys (eBBlock ** ebbs, int count)
 {
 {
-    int i;
-
-    for (i = 0 ; i < count ; i++ ) {
-       
-       iCode *ic;
-       ebbs[i]->fSeq = iCodeSeq + 1;
-       for ( ic = ebbs[i]->sch ; ic ; ic= ic->next) {
-           ic->seq = ++iCodeSeq;
-           ic->depth = ebbs[i]->depth;
-           hTabAddItem(&iCodehTab,ic->key,ic);
-       }
-       ebbs[i]->lSeq = iCodeSeq ;
+  int i;
+
+  for (i = 0; i < count; i++)
+    {
+      iCode *ic;
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+        hTabAddItem (&iCodehTab, ic->key, ic);
     }
 }
 
 /*-----------------------------------------------------------------*/
     }
 }
 
 /*-----------------------------------------------------------------*/
-/* markVisited - will set the visited flag for the given Block     */
+/* sequenceiCode - creates a sequence number for the iCode & add   */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-DEFSETFUNC(markVisited)
+void
+sequenceiCode (eBBlock ** ebbs, int count)
 {
 {
-    eBBlock *ebp = item;
-    
-    if (ebp->visited)
-       return 0;
-    ebp->visited = 1;
-    applyToSet(ebp->succList,markVisited);
-    return 0;
+  int i;
+
+  for (i = 0; i < count; i++)
+    {
+
+      iCode *ic;
+      ebbs[i]->fSeq = iCodeSeq + 1;
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+       {
+         ic->seq = ++iCodeSeq;
+         ic->depth = ebbs[i]->depth;
+         //hTabAddItem (&iCodehTab, ic->key, ic);
+         hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
+       }
+      ebbs[i]->lSeq = iCodeSeq;
+    }
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* isOpAlive - checks to see if the usage in this block is the     */
-/*             uses the same definitions as this one               */
+/* setFromRange - sets the from range of a given operand           */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-DEFSETFUNC(isOpAlive)
+void
+setFromRange (operand * op, int from)
 {
 {
-    eBBlock *ebp = item;
-    V_ARG(operand *,op);
-    V_ARG(eBBlock *,orig);
-    V_ARG(iCode *,ic);   
+  /* only for compiler defined temporaries */
+  if (!IS_ITEMP (op))
+    return;
 
 
-    if (ebp->visited)
-       return 0;
+  hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 
 
-    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;
+  if (op->isaddr)
+    OP_SYMBOL (op)->isptr = 1;
 
 
+  if (!OP_LIVEFROM (op) ||
+      OP_LIVEFROM (op) > from)
+    OP_LIVEFROM (op) = from;
+}
 
 
-    return (applyToSet(ebp->succList,isOpAlive,op,orig,ic));
+/*-----------------------------------------------------------------*/
+/* setToRange - set the range to for an operand                    */
+/*-----------------------------------------------------------------*/
+void
+setToRange (operand * op, int to, bool check)
+{
+  /* only for compiler defined temps */
+  if (!IS_ITEMP (op))
+    return;
+
+  OP_SYMBOL (op)->key = op->key;
+  hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
+
+  if (op->isaddr)
+    OP_SYMBOL (op)->isptr = 1;
+
+  if (check)
+    if (!OP_LIVETO (op))
+      OP_LIVETO (op) = to;
+    else;
+  else
+    OP_LIVETO (op) = to;
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* isLastUse - return TRUE if no usage of this operand after this  */
+/* setFromRange - sets the from range of a given operand           */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-int isLastUse (operand *op, eBBlock *ebp, iCode *ic, 
-                    eBBlock **ebbs, int count)
+void
+setLiveFrom (symbol * sym, int from)
 {
 {
-    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;   
+  if (!sym->liveFrom || sym->liveFrom > from)
+    sym->liveFrom = from;
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* unionDefsUsed - unions the defsUsed in a block                  */
+/* setToRange - set the range to for an operand                    */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-DEFSETFUNC(unionDefsUsed)
+void
+setLiveTo (symbol * sym, int to)
 {
 {
-    eBBlock *ebp = item;
-    V_ARG(bitVect **,bvp);   
+  if (!sym->liveTo || sym->liveTo < to)
+    sym->liveTo = to;
+}
 
 
-    if (ebp->visited)
-       return 0;
+/*-----------------------------------------------------------------*/
+/* markLiveRanges - for each operand mark the liveFrom & liveTo    */
+/*-----------------------------------------------------------------*/
+void
+markLiveRanges (eBBlock ** ebbs, int count)
+{
+  int i, key;
+  symbol *sym;
 
 
-    ebp->visited = 1;
+  for (i = 0; i < count; i++)
+    {
+      iCode *ic;
+
+      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);
+
+         /* 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);
+           }
 
 
-    *bvp = bitVectUnion(*bvp, ebp->usesDefs);
-    applyToSet(ebp->succList,unionDefsUsed,bvp);
-    return 0;
+       }
+    }
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* setFromRange - sets the from range of a given operand           */
+/* markAlive - marks the operand as alive between sic and eic      */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void setFromRange (operand *op, int from)
+void
+markAlive (iCode * sic, iCode * eic, int key)
 {
 {
-    /* only for compiler defined temporaries */
-    if (!IS_ITEMP(op))
-       return ;
-
-    hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
-
-    if (op->isaddr)
-       OP_SYMBOL(op)->isptr = 1;
+  iCode *dic;
 
 
-    if (!OP_LIVEFROM(op) || 
-       OP_LIVEFROM(op) > from) 
-       OP_LIVEFROM(op) = from;
+  for (dic = sic; dic != eic->next; dic = dic->next)
+    {
+      dic->rlive = bitVectSetBit (dic->rlive, key);
+    }
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* setToRange - set the range to for an operand                    */
+/* findNextUseSym - finds the next use of the symbol and marks it  */
+/*                  alive in between                               */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void setToRange (operand *op,int to, bool check)
-{    
-    /* only for compiler defined temps */
-    if (!IS_ITEMP(op))
-       return ;
-        
-    OP_SYMBOL(op)->key = op->key;
-    hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
-
-    if (op->isaddr)
-       OP_SYMBOL(op)->isptr = 1;
-
-    if (check)
-       if (!OP_LIVETO(op))
-           OP_LIVETO(op) = to;
-       else ;
-    else
-       OP_LIVETO(op) = to;
-}
+int
+findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
+{
+  int retval = 0;
+  iCode *uic;
+  eBBlock *succ;
 
 
+  hTabAddItemIfNotP (&liveRanges, sym->key, sym);
 
 
-/*-----------------------------------------------------------------*/
-/* operandLUse - check and set the last use for a given operand    */
-/*-----------------------------------------------------------------*/
-operand *operandLUse (operand *op, eBBlock **ebbs, 
-                     int count, iCode *ic, eBBlock *ebp)
-{        
-    setFromRange(op,ic->seq);
-    if (ic->depth)
-       OP_SYMBOL(op)->used += (((unsigned int)1 << ic->depth) + 1);
-    else
-       OP_SYMBOL(op)->used += 1;
-    
-    if (isLastUse(op,ebp,ic->next,ebbs,count) ||
-       (OP_LIVETO(op) && OP_LIVETO(op) < ic->seq)) {
-       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);
-    }  
-    ic->uses = bitVectSetBit(ic->uses,op->key);
-    
+  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))
     {
     {
-       link *type = operandType(op);
-       link *etype = getSpec(type);
-
-       /* 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)         ) {
-           
-           if (bitVectIsZero(op->usesDefs)) {          
-               OP_SYMBOL(op)->isspilt = 1;
-               
-               if (OP_SYMBOL(op)->isreqv && 
-                   !OP_SYMBOL(op)->_isparm && SPIL_LOC(op) ) {
-
-                   werror(W_LOCAL_NOINIT,                          
-                          SPIL_LOC(op)->name,                     
-                          ic->filename,ic->lineno);
-               } else {
-
-                   werror(W_LOCAL_NOINIT,                         
-                          OP_SYMBOL(op)->name,                   
-                          ic->filename,ic->lineno); 
-               }
-           } 
+      /* check if the first instruction is a def of this op */
+      if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
+        return 1;
+
+      if (IS_ITEMP(IC_RESULT(ic)))
+        if (IC_RESULT(ic)->key == sym->key)
+         return 0;
+
+      return 1;
+    }
+
+  if (ebp->visited)
+    return 0;
+
+  if (ic == ebp->sch)
+    ebp->visited = 1;
+
+  /* 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;
+           }
+          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);
     }
     }
-    return op;
+
+  if (retval)
+    {
+      if (ic) markAlive (ic, ebp->ech, sym->key);
+      return 1;
+    }
+
+  return 0;
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* compLastUse - computes the last usage with certainty            */
+/* findNextUse - finds the next use of the operand and marks it    */
+/*               alive in between                                  */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void compLastUse ()
+int
+findNextUse (eBBlock *ebp, iCode *ic, operand *op)
 {
 {
-    symbol *sym;
-    int key;
-    /* the strategy here is to look for live ranges that are not
-       induction variables, and find out the usage icode with the
-       highest sequence number then set the to range to that icode
-       sequence */
-    /* once fully tested we can use only this routine to mark the
-       to range that will reduce a lot of computations in the 
-       markLiveRanges routine */
-    for (sym = hTabFirstItem(liveRanges,&key) ; sym;
-        sym = hTabNextItem(liveRanges,&key)) {
-
-       int i ;
-       int maxKey = 0 ;
-
-       if (sym->isind)
-           continue ;
-
-       if (!sym->uses)
-           continue ;
-
-       /* go thru all the usages of this live range and find out
-          the maximum sequence number of the icode that used it */
-       for (i = 0 ; i < sym->uses->size ; i++ ) {
-           iCode *uic ;
-
-           if (!bitVectBitValue(sym->uses,i))
-               continue ;
-           
-           if ((uic = hTabItemWithKey(iCodehTab,i)))
-               maxKey = ( uic->seq > maxKey ? uic->seq : maxKey );         
-       }
+  if (op->isaddr)
+    OP_SYMBOL (op)->isptr = 1;
 
 
-       /* got it */
-       if (maxKey)
-           sym->liveTo = maxKey;
-    }
+  OP_SYMBOL (op)->key = op->key;
+
+  return findNextUseSym (ebp, ic, OP_SYMBOL(op));
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* killAllAlive - mark all the definitions living with this seq    */
+/* unvisitBlocks - clears visited in all blocks                    */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void killAllAlive (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)
 {
 {
-    symbol *sym;
-    int k;
+  int i;
+  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;
+
+  if (!ic)
+    {
+      /* 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;
+    }
 
 
-    for (sym = hTabFirstItem(liveRanges,&k); sym;
-        sym = hTabNextItem(liveRanges,&k))
-       if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
-           sym->liveTo = seq;
+  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);
+    }
+
+  freeBitVect (succVect);
+  freeBitVect (predVect);
 }
 }
+
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-/* defUsedAfterLoop - all definitions & usages before sequence num */
+/* incUsed - increment a symbol's usage count                      */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-bool defUsedAfterLoop (operand *op, int seq)
+void
+incUsed (iCode *ic, operand *op)
 {
 {
-    int i;
-    iCode *ic;
-
-    /* check for the usages first */
-    if (OP_SYMBOL(op)->uses && !bitVectIsZero(OP_SYMBOL(op)->uses)) {
-       for (i = 0 ; i < OP_SYMBOL(op)->uses->size ; i++ ) {
-           
-           if (bitVectBitValue( OP_SYMBOL(op)->uses,i) && /* usage found */
-               (ic = hTabItemWithKey(iCodehTab,i))     && /*    ""       */
-               ic->seq > seq )                            /* & is after the seq */
-               return TRUE ;
+  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
+rliveClear (eBBlock ** ebbs, int count)
+{
+  int i;
+
+  /* for all blocks do */
+  for (i = 0; i < count; i++)
+    {
+      iCode *ic;
+
+      /* for all instructions in this block do */
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+        {
+         freeBitVect (ic->rlive);
+         ic->rlive = NULL;
        }
     }
        }
     }
-
-    return FALSE;
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* markLiveRanges - for each operand mark the liveFrom & liveTo    */
+/* rlivePoint - for each point compute the ranges that are alive   */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void markLiveRanges (eBBlock *ebp, eBBlock **ebbs, int count)
+void
+rlivePoint (eBBlock ** ebbs, int count)
 {
 {
-    iCode *ic;
-    bitVect *defsUsed = NULL;
-    bitVect *defsNotUsed = NULL;
-    int i;
-    /* for all the instructions */
-    for (ic = ebp->sch ; ic ; ic = ic->next ) {
-
-       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);
+  int i, key;
+  eBBlock *succ;
+  bitVect *alive;
+
+  /* for all blocks do */
+  for (i = 0; i < count; i++)
+    {
+      iCode *ic;
+
+      /* for all instructions in this block do */
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+        {
+
+         if (!ic->rlive)
+           ic->rlive = newBitVect (operandKey);
+
+         if (SKIP_IC2(ic))
+           continue;
+
+         if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
+           {
+             incUsed (ic, IC_JTCOND(ic));
+
+             if (!IS_ITEMP(IC_JTCOND(ic)))
+               continue;
+
+             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 (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
+           {
+             incUsed (ic, IC_COND(ic));
+
+             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;
+           }
+
+         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;
+                           }
+                       }
+                   }
+               }
+           }
+
+         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));
+               }
+           }
+
+         if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
+           incUsed (ic, IC_RESULT(ic));
+
+         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;
+
+       }
+
+      /* check all symbols that are alive in the last instruction */
+      /* but are not alive in all successors */
+
+      succ = setFirstItem (ebbs[i]->succList);
+      if (!succ)
+        continue;
+
+      alive = succ->sch->rlive;
+      while ((succ = setNextItem (ebbs[i]->succList)))
+        {
+         if (succ->sch)
+            alive = bitVectIntersect (alive, succ->sch->rlive);
        }
 
        }
 
-       if (SKIP_IC2(ic))
-           continue ;
+      if (ebbs[i]->ech)
+        alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), 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);
+      if(!alive)
+        continue;
+      for (key = 1; key < alive->size; key++)
+        {
+         if (!bitVectBitValue (alive, key))
            continue;
            continue;
+
+         unvisitBlocks(ebbs, count);
+         findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
        }
        }
-       
-       if (ic->op == IFX && IS_SYMOP(IC_COND(ic))) {
-           operandLUse (IC_COND(ic),ebbs,count,ic,ebp);
-           continue ;
-       } 
-       
-       if (IS_SYMOP(IC_LEFT(ic))) 
-           operandLUse (IC_LEFT(ic),ebbs,count,ic,ebp);                
-
-       if (IS_SYMOP(IC_RIGHT(ic))) 
-           operandLUse (IC_RIGHT(ic),ebbs,count,ic,ebp);                       
-       
-       if (POINTER_SET(ic)) 
-           operandLUse(IC_RESULT(ic),ebbs,count,ic,ebp);
-       else
-           if (IC_RESULT(ic))
-               ic->defKey = IC_RESULT(ic)->key ;
+
     }
     }
+}
 
 
+/*-----------------------------------------------------------------*/
+/* computeClash - find out which live ranges collide with others   */
+/*-----------------------------------------------------------------*/
+static void
+computeClash (eBBlock ** ebbs, int count)
+{
+  int i;
 
 
-    /* for all the definitions in the block */
-    /* compute and set the live from        */
-    if ( ebp->defSet && ! bitVectIsZero(ebp->defSet)) {
-       for ( i = 0 ; i < ebp->defSet->size ; i++ ) {
-           iCode *dic;     
-           
-           if (bitVectBitValue(ebp->defSet,i) &&          
-               (dic = hTabItemWithKey(iCodehTab,i))) {
-               
-               /* if the definition has a from & it is greater */
-               /* than the defininng iCode->seq then change it */
-               setFromRange(IC_RESULT(dic),dic->seq);
-           }       
-       }    
-    }
+  /* 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);
 
 
-    /* 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 (bitVectBitValue(ebp->linds,i) &&
-               (dic = hTabItemWithKey(iCodehTab,i))) {
-
-               /* 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))
+             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;
 
                    continue;
 
-               setToRange(IC_RESULT(dic),( ebp->lSeq ),FALSE);
-           }
-       }       
-    }
+                 sym2 = hTabItemWithKey(liveRanges, key2);
 
 
-    /* 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;
-           
-           if (bitVectBitValue(defsNotUsed,i) &&
-               (dic = hTabItemWithKey(iCodehTab,i))) {
-               
-               setToRange(IC_RESULT(dic),( ebp->fSeq - 1),TRUE);
+                 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;
+                   }
+               }
            }
        }
     }
            }
        }
     }
+}
+
+/*-----------------------------------------------------------------*/
+/* allDefsOutOfRange - all definitions are out of a range          */
+/*-----------------------------------------------------------------*/
+bool
+allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
+{
+  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;
+
+    }
 
 
-    /* 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);
+  return TRUE;
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* rlivePoint - for each point compute the ranges that are alive   */
+/* notUsedInBlock - not used in this block                         */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void rlivePoint (eBBlock **ebbs, int count)
+int
+notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 {
 {
-    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 (lrange->liveFrom <= ic->seq &&
-                   lrange->liveTo   >= ic->seq )
-                   ic->rlive = bitVectSetBit(ic->rlive,lrange->key);
-           }
-       }
-    }  
+  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 computeLiveRanges (eBBlock **ebbs, int count )
+void
+computeLiveRanges (eBBlock ** ebbs, int count)
+{
+  /* 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;
+  setToNull ((void *) &iCodehTab);
+  iCodehTab = newHashTable (iCodeKey);
+  hashiCodeKeys (ebbs, count);
+  setToNull ((void *) &iCodeSeqhTab);
+  iCodeSeqhTab = newHashTable (iCodeKey);
+  sequenceiCode (ebbs, count);
+
+  /* mark the ranges live for each point */
+  setToNull ((void *) &liveRanges);
+  rlivePoint (ebbs, count);
+
+  /* mark the from & to live ranges for variables used */
+  markLiveRanges (ebbs, count);
+
+  /* compute which overlaps with what */
+  computeClash(ebbs, count);
+}
+
+/*-----------------------------------------------------------------*/
+/* recomputeLiveRanges - recomputes the live ranges for variables  */
+/*-----------------------------------------------------------------*/
+void
+recomputeLiveRanges (eBBlock ** ebbs, int count)
 {
 {
-    int i = 0 ;
-    /* 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 ;
-    setToNull((void **)&iCodehTab);
-    iCodehTab = newHashTable (iCodeKey);
-    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);
-    
-/*     compLastUse(); */
-    /* mark the ranges live for each point */
-    rlivePoint (ebbs,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);
 }
 }
+
SDCC with magic sdcdb for TeleMetrum