projects / fw / sdcc / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
* fixed GCC 4.4.0 mingw compilation:
[fw/sdcc] / src / SDCClrange.c
diff --git a/src/SDCClrange.c b/src/SDCClrange.c
index 5dd9335667e699c361a5f23387cf6c7a866c7032..c4a5bcc2959a180b2a67d7b7e5499682aa854551 100644 (file)
--- a/src/SDCClrange.c
+++ b/src/SDCClrange.c
@@ -8,516 +8,929 @@
    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 <stdio.h>
-#include <stdlib.h>
-#include "SDCCglobl.h"
-#include "SDCCast.h"
-#include "SDCCmem.h"
-#include "SDCCy.h"
-#include "SDCChasht.h"
-#include "SDCCbitv.h"
-#include "SDCCset.h"
-#include "SDCCicode.h"
-#include "SDCClabel.h"
-#include "SDCCBBlock.h"
-#include "SDCCloop.h"
-#include "SDCCcse.h"
-#include "SDCCcflow.h"
-#include "SDCCdflow.h"
-#include "SDCClrange.h"
-
-int iCodeSeq = 0 ;
+#include "common.h"
+#include "limits.h"
+
+int iCodeSeq = 0;
 hTab *liveRanges = NULL;
 hTab *iCodehTab = NULL;
 hTab *liveRanges = NULL;
 hTab *iCodehTab = NULL;
+hTab *iCodeSeqhTab = NULL;
+
+/* all symbols, for which the previous definition is searched
+   and warning is emitted if there's none. */
+#define IS_AUTOSYM(op) (IS_ITEMP(op) || \
+                        (IS_SYMOP(op) && IS_AUTO(op->operand.symOperand) && !IS_PARM(op)))
+
+/*-----------------------------------------------------------------*/
+/* 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 sequenceiCode (eBBlock **ebbs, int count)
+static void
+sequenceiCode (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);
+  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 ;
+      ebbs[i]->lSeq = iCodeSeq;
     }
 }
 
 /*-----------------------------------------------------------------*/
     }
 }
 
 /*-----------------------------------------------------------------*/
-/* markVisited - will set the visited flag for the given Block     */
+/* setFromRange - sets the from range of a given operand           */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-DEFSETFUNC(markVisited)
+#if 0
+static void
+setFromRange (operand * op, int from)
 {
 {
-    eBBlock *ebp = item;
-    
-    if (ebp->visited)
-       return 0;
-    ebp->visited = 1;
-    applyToSet(ebp->succList,markVisited);
-    return 0;
+  /* 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;
+
+  if (!OP_LIVEFROM (op) ||
+      OP_LIVEFROM (op) > from)
+    OP_LIVEFROM (op) = from;
 }
 }
+#endif
 
 /*-----------------------------------------------------------------*/
 
 /*-----------------------------------------------------------------*/
-/* isOpAlive - checks to see if the usage in this block is the     */
-/*             uses the same definitions as this one               */
+/* setToRange - set the range to for an operand                    */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-DEFSETFUNC(isOpAlive)
+void
+setToRange (operand * op, int to, bool check)
 {
 {
-    eBBlock *ebp = item;
-    V_ARG(operand *,op);
-    V_ARG(eBBlock *,orig);
-    V_ARG(iCode *,ic);   
+  /* 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;
+}
 
 
-    if (ebp->visited)
-       return 0;
+/*-----------------------------------------------------------------*/
+/* setFromRange - sets the from range of a given operand           */
+/*-----------------------------------------------------------------*/
+static void
+setLiveFrom (symbol * sym, int from)
+{
+  if (!sym->liveFrom || sym->liveFrom > from)
+    sym->liveFrom = from;
+}
 
 
-    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;
+/*-----------------------------------------------------------------*/
+/* setToRange - set the range to for an operand                    */
+/*-----------------------------------------------------------------*/
+static void
+setLiveTo (symbol * sym, int to)
+{
+  if (!sym->liveTo || sym->liveTo < to)
+    sym->liveTo = to;
+}
+
+/*-----------------------------------------------------------------*/
+/* markLiveRanges - for each operand mark the liveFrom & liveTo    */
+/*-----------------------------------------------------------------*/
+static void
+markLiveRanges (eBBlock ** ebbs, int count)
+{
+  int i, key;
+  symbol *sym;
 
 
+  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);
+           }
 
 
-    return (applyToSet(ebp->succList,isOpAlive,op,orig,ic));
+       }
+    }
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* isLastUse - return TRUE if no usage of this operand after this  */
+/* markAlive - marks the operand as alive between sic and eic      */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-int isLastUse (operand *op, eBBlock *ebp, iCode *ic, 
-                    eBBlock **ebbs, int count)
+static void
+markAlive (iCode * sic, iCode * eic, int key)
 {
 {
-    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;   
+  iCode *dic;
+
+  for (dic = sic; dic != eic->next; dic = dic->next)
+    {
+      dic->rlive = bitVectSetBit (dic->rlive, key);
+    }
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* unionDefsUsed - unions the defsUsed in a block                  */
+/* findNextUseSym - finds the next use of the symbol and marks it  */
+/*                  alive in between                               */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-DEFSETFUNC(unionDefsUsed)
+static int
+findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
 {
 {
-    eBBlock *ebp = item;
-    V_ARG(bitVect **,bvp);   
+  int retval = 0;
+  iCode *uic;
+  eBBlock *succ;
 
 
-    if (ebp->visited)
-       return 0;
+  hTabAddItemIfNotP (&liveRanges, sym->key, sym);
 
 
-    ebp->visited = 1;
+  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))
+    {
+      /* check if the first instruction is a def of this op */
+      if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
+        return 1;
 
 
-    *bvp = bitVectUnion(*bvp, ebp->usesDefs);
-    applyToSet(ebp->succList,unionDefsUsed,bvp);
+      if (IS_ITEMP(IC_RESULT(ic)))
+        if (IC_RESULT(ic)->key == sym->key)
+         return 0;
+
+      return 1;
+    }
+
+  if (ebp->visited)
     return 0;
     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);
+    }
+
+  if (retval)
+    {
+      if (ic) markAlive (ic, ebp->ech, sym->key);
+      return 1;
+    }
+
+  return 0;
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* setFromRange - sets the from range of a given operand           */
+/* findNextUse - finds the next use of the operand and marks it    */
+/*               alive in between                                  */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void setFromRange (operand *op, int from)
+static int
+findNextUse (eBBlock *ebp, iCode *ic, operand *op)
 {
 {
-    /* 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;
 
 
-    if (op->isaddr)
-       OP_SYMBOL(op)->isptr = 1;
+  OP_SYMBOL (op)->key = op->key;
 
 
-    if (!OP_LIVEFROM(op) || 
-       OP_LIVEFROM(op) > from) 
-       OP_LIVEFROM(op) = from;
+  return findNextUseSym (ebp, ic, OP_SYMBOL(op));
 }
 
 /*-----------------------------------------------------------------*/
 }
 
 /*-----------------------------------------------------------------*/
-/* setToRange - set the range to for an operand                    */
+/* unvisitBlocks - clears visited in all blocks                    */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-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;
+static void
+unvisitBlocks (eBBlock ** ebbs, int count)
+{
+  int i;
+
+  for (i = 0; i < count; i++)
+    ebbs[i]->visited = 0;
 }
 
 }
 
+/*------------------------------------------------------------------*/
+/* markWholeLoop - mark the symbol 'key' alive in all blocks        */
+/*                 included by the outermost loop                   */
+/*------------------------------------------------------------------*/
+static void
+markWholeLoop (eBBlock *ebp, int key)
+{
+  eBBlock *ebpi;
 
 
-/*-----------------------------------------------------------------*/
-/* 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);
-    
+  /* avoid endless loops */
+  ebp->visited = 1;
+
+  /* recurse through all predecessors */
+  for (ebpi = setFirstItem (ebp->predList);
+       ebpi;
+       ebpi = setNextItem (ebp->predList))
     {
     {
-       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 (OP_SYMBOL(op)->isreqv && !OP_SYMBOL(op)->_isparm){ */
-               
-/*             if (SPIL_LOC(op) &&  */
-/*                 bitVectIsZero(SPIL_LOC(op)->defs)) { */
-/*                 OP_SYMBOL(op)->isspilt = 1; */
-/*                 werror(W_LOCAL_NOINIT,                          */
-/*                        SPIL_LOC(op)->name,                     */
-/*                        ic->filename,ic->lineno);  */
-/*             } */
-/*         } else { */
-               
-           if (bitVectIsZero(op->usesDefs)) {
-               OP_SYMBOL(op)->isspilt = 1;
-               werror(W_LOCAL_NOINIT,                     
-                      OP_SYMBOL(op)->name,                       
-                      ic->filename,ic->lineno); 
-           }
-/*         } */
-       }
+      if (ebpi->visited)
+        continue;
+      /* is the predecessor still in the loop? */
+      if (ebpi->depth == 0)
+        continue;
+      markWholeLoop (ebpi, key);
     }
     }
-    return op;
+
+  /* recurse through all successors */
+  for (ebpi = setFirstItem (ebp->succList);
+       ebpi;
+       ebpi = setNextItem (ebp->succList))
+    {
+      if (ebpi->visited)
+        continue;
+      if (ebpi->depth == 0)
+        continue;
+      markWholeLoop (ebpi, key);
+    }
+
+  markAlive (ebp->sch, ebp->ech, key);
 }
 
 }
 
-/*-----------------------------------------------------------------*/
-/* compLastUse - computes the last usage with certainty            */
-/*-----------------------------------------------------------------*/
-void compLastUse ()
+/*------------------------------------------------------------------*/
+/* findPrevUseSym - search for a previous definition of a symbol in */
+/*                  - the previous icodes                           */
+/*                  - all branches of predecessors                  */
+/*------------------------------------------------------------------*/
+static bool
+findPrevUseSym  (eBBlock *ebp, iCode *ic, symbol * sym)
 {
 {
-    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 );         
-       }
+  eBBlock * pred;
+  iCode * uic;
+
+  if (ebp->visited)
+    {
+     /* already visited: this branch must have been succesfull, */
+     /* because otherwise the search would have been aborted. */
+      return TRUE;
+    }
+  ebp->visited = 1;
+
+  /* search backward in the current block */
+  for (uic = ic; uic; uic = uic->prev)
+    {
+      if (!POINTER_SET (uic) && IS_AUTOSYM (IC_RESULT (uic)))
+        {
+          if (IC_RESULT (uic)->key == sym->key)
+            {
+              /* Ok, found a definition */
+              return TRUE;
+            }
+        }
+      /* address taken from symbol? */
+      if (uic->op == ADDRESS_OF && IS_AUTOSYM (IC_LEFT (uic)))
+        {
+          if (IC_LEFT (uic)->key == sym->key)
+            {
+              /* Ok, found a definition */
+              return TRUE;
+            }
+        }
+    }
 
 
-       /* got it */
-       if (maxKey)
-           sym->liveTo = maxKey;
+  /* There's no definition in this bblock, */
+  /* let's have a look at all predecessors. */
+  pred = setFirstItem (ebp->predList);
+  if (!pred)
+    {
+      /* no more predecessors and nothing found yet :-( */
+      return FALSE;
+    }
+  for (; pred; pred = setNextItem (ebp->predList))
+    {
+      /* recurse into all predecessors */
+      if (!findPrevUseSym (pred, pred->ech, sym))
+        {
+          /* found nothing: abort */
+          return FALSE;
+        }
+    }
+
+  /* Success! Went through all branches with no abort: */
+  /* all branches end with a definition */
+  return TRUE;
+}
+
+/*------------------------------------------------------------------*/
+/* findPrevUse - search for a previous definition of an operand     */
+/*                  If there's no definition let's:                 */
+/*                  - emit a warning                                */
+/*                  - fix the life range, if the symbol is used in  */
+/*                    a loop                                        */
+/*------------------------------------------------------------------*/
+static void
+findPrevUse (eBBlock *ebp, iCode *ic, operand *op,
+             eBBlock ** ebbs, int count,
+             bool emitWarnings)
+{
+  unvisitBlocks (ebbs, count);
+
+  if (op->isaddr)
+    OP_SYMBOL (op)->isptr = 1;
+  OP_SYMBOL (op)->key = op->key;
+
+  /* There must be a definition in each branch of predecessors */
+  if (!findPrevUseSym (ebp, ic->prev, OP_SYMBOL(op)))
+    {
+      /* computeLiveRanges() is called twice */
+      if (emitWarnings)
+        {
+          if (IS_ITEMP (op))
+            {
+              if (OP_SYMBOL (op)->prereqv)
+                {
+                  werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
+                            OP_SYMBOL (op)->prereqv->name);
+                  OP_SYMBOL (op)->prereqv->reqv = NULL;
+                  OP_SYMBOL (op)->prereqv->allocreq = 1;
+                }
+            }
+          else
+            {
+              werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
+                        OP_SYMBOL (op)->name);
+            }
+        }
+      /* is this block part of a loop? */
+      if (IS_ITEMP (op) && ebp->depth != 0)
+        {
+          /* extend the life range to the outermost loop */
+          unvisitBlocks(ebbs, count);
+          markWholeLoop (ebp, op->key);
+        }
     }
 }
 
 /*-----------------------------------------------------------------*/
     }
 }
 
 /*-----------------------------------------------------------------*/
-/* killAllAlive - mark all the definitions living with this seq    */
+/* incUsed - increment a symbol's usage count                      */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void killAllAlive (int seq)
+static void
+incUsed (iCode *ic, operand *op)
 {
 {
-    symbol *sym;
-    int k;
-
-    for (sym = hTabFirstItem(liveRanges,&k); sym;
-        sym = hTabNextItem(liveRanges,&k))
-       if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
-           sym->liveTo = seq;
+  if (ic->depth)
+    OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
+  else
+    OP_SYMBOL (op)->used += 1;
 }
 }
+
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-/* defUsedAfterLoop - all definitions & usages before sequence num */
+/* rliveClear - clears the rlive bitVectors                        */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-bool defUsedAfterLoop (operand *op, int seq)
+static void
+rliveClear (eBBlock ** ebbs, int count)
 {
 {
-    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 ;
+  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   */
+/* The live range is only stored for ITEMPs; the same code is used */
+/* to find use of unitialized AUTOSYMs (an ITEMP is an AUTOSYM).   */
 /*-----------------------------------------------------------------*/
 /*-----------------------------------------------------------------*/
-void markLiveRanges (eBBlock *ebp, eBBlock **ebbs, int count)
+static void
+rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
 {
 {
-    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_AUTOSYM(IC_JTCOND(ic)))
+               continue;
+
+             findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings);
+              if (IS_ITEMP(IC_JTCOND(ic)))
+                {
+                  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_AUTOSYM(IC_COND(ic)))
+               continue;
+
+             findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings);
+              if (IS_ITEMP(IC_COND(ic)))
+                {
+                  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_AUTOSYM(IC_LEFT(ic)) &&
+                 ic->op != ADDRESS_OF)
+               {
+                 findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings);
+                  if (IS_ITEMP(IC_LEFT(ic)))
+                    {
+                      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_AUTOSYM(IC_RIGHT(ic)))
+               {
+                 findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings);
+                  if (IS_ITEMP(IC_RIGHT(ic)))
+                    {
+                      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_AUTOSYM(IC_RESULT(ic)))
+           {
+             if (POINTER_SET(ic))
+               {
+                 findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings);
+               }
+              if (IS_ITEMP(IC_RESULT(ic)))
+                {
+                  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;
+
        }
 
        }
 
-       if (SKIP_IC2(ic))
-           continue ;
+      /* check all symbols that are alive in the last instruction */
+      /* but are not alive in all successors */
 
 
-       /* take care of the special icodes first */
-       if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic))) {
-           operandLUse (IC_JTCOND(ic),ebbs,count,ic,ebp);
+      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 (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;
            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                 */
+/*-----------------------------------------------------------------*/
+static 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, bool emitWarnings)
+{
+  /* 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, emitWarnings);
+
+  /* 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, FALSE);
+}
+
+/*-----------------------------------------------------------------*/
+/* dump icode->rlive in all blocks                                 */
+/*-----------------------------------------------------------------*/
+#if 0
+void
+dumpIcRlive (eBBlock ** ebbs, int count)
+{
+  int i, j;
+  iCode *ic;
+
+  /* for all blocks do */
+  for (i = 0; i < count; i++)
+    {
+      printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name);
+      /* for all instructions in this block do */
+      for (ic = ebbs[i]->sch; ic; ic = ic->next)
+        {
+          printf ("\tic->key %d\n", ic->key);
+
+          if (!ic->rlive)
+            continue;
+          /* for all live Ranges alive at this point */
+          for (j = 1; j < ic->rlive->size; j++)
+            {
+              symbol *sym;
+
+              if (!bitVectBitValue (ic->rlive, j))
+                continue;
+
+              /* find the live range we are interested in */
+              if ((sym = hTabItemWithKey (liveRanges, j)))
+                printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name);
+            }
+        }
+    }
 }
 }
+#endif
SDCC with magic sdcdb for TeleMetrum