under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version.
-
+
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
-
+
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-
+
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
- what you give them. Help stamp out software-hoarding!
+ what you give them. Help stamp out software-hoarding!
-------------------------------------------------------------------------*/
#include "common.h"
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
+void
hashiCodeKeys (eBBlock ** ebbs, int count)
{
int i;
{
iCode *ic;
for (ic = ebbs[i]->sch; ic; ic = ic->next)
- hTabAddItem (&iCodehTab, ic->key, ic);
+ hTabAddItem (&iCodehTab, ic->key, ic);
}
}
/*-----------------------------------------------------------------*/
/* sequenceiCode - creates a sequence number for the iCode & add */
/*-----------------------------------------------------------------*/
-void
+static void
sequenceiCode (eBBlock ** ebbs, int count)
{
int i;
/*-----------------------------------------------------------------*/
/* setFromRange - sets the from range of a given operand */
/*-----------------------------------------------------------------*/
-void
+#if 0
+static void
setFromRange (operand * op, int from)
{
/* only for compiler defined temporaries */
OP_LIVEFROM (op) > from)
OP_LIVEFROM (op) = from;
}
+#endif
/*-----------------------------------------------------------------*/
/* setToRange - set the range to for an operand */
/*-----------------------------------------------------------------*/
-void
+void
setToRange (operand * op, int to, bool check)
{
/* only for compiler defined temps */
/*-----------------------------------------------------------------*/
/* setFromRange - sets the from range of a given operand */
/*-----------------------------------------------------------------*/
-void
+static void
setLiveFrom (symbol * sym, int from)
{
if (!sym->liveFrom || sym->liveFrom > from)
/*-----------------------------------------------------------------*/
/* setToRange - set the range to for an operand */
/*-----------------------------------------------------------------*/
-void
+static void
setLiveTo (symbol * sym, int to)
{
if (!sym->liveTo || sym->liveTo < to)
/*-----------------------------------------------------------------*/
/* markLiveRanges - for each operand mark the liveFrom & liveTo */
/*-----------------------------------------------------------------*/
-void
+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);
+ 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++)
/*-----------------------------------------------------------------*/
/* markAlive - marks the operand as alive between sic and eic */
/*-----------------------------------------------------------------*/
-void
+static void
markAlive (iCode * sic, iCode * eic, int key)
{
iCode *dic;
/* findNextUseSym - finds the next use of the symbol and marks it */
/* alive in between */
/*-----------------------------------------------------------------*/
-int
+static int
findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
{
int retval = 0;
if (ebp->visited)
return 0;
- ebp->visited = 1;
+ if (ic == ebp->sch)
+ ebp->visited = 1;
/* for all remaining instructions in current block */
for (uic = ic; uic; uic = uic->next)
return 1;
}
continue;
- }
+ }
if (uic->op == IFX)
{
return 1;
}
continue;
- }
+ }
if (IS_ITEMP (IC_LEFT (uic)))
if (IC_LEFT (uic)->key == sym->key)
if (retval)
{
- markAlive (ic, ebp->ech, sym->key);
+ if (ic) markAlive (ic, ebp->ech, sym->key);
return 1;
}
/* findNextUse - finds the next use of the operand and marks it */
/* alive in between */
/*-----------------------------------------------------------------*/
-int
+static int
findNextUse (eBBlock *ebp, iCode *ic, operand *op)
{
if (op->isaddr)
/*-----------------------------------------------------------------*/
/* unvisitBlocks - clears visited in all blocks */
/*-----------------------------------------------------------------*/
-void unvisitBlocks (eBBlock ** ebbs, int count)
+static void
+unvisitBlocks (eBBlock ** ebbs, int count)
{
int 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;
+
+ /* avoid endless loops */
+ ebp->visited = 1;
+
+ /* recurse through all predecessors */
+ for (ebpi = setFirstItem (ebp->predList);
+ ebpi;
+ ebpi = setNextItem (ebp->predList))
+ {
+ if (ebpi->visited)
+ continue;
+ /* is the predecessor still in the loop? */
+ if (ebpi->depth == 0)
+ continue;
+ markWholeLoop (ebpi, key);
+ }
+
+ /* 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);
+}
+
+/*------------------------------------------------------------------*/
+/* 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)
+{
+ 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;
+ }
+ }
+ }
+
+ /* 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);
+ }
+ }
+}
+
/*-----------------------------------------------------------------*/
-/* unvisitBlocks - clears visited in all blocks */
+/* incUsed - increment a symbol's usage count */
/*-----------------------------------------------------------------*/
-void
+static void
incUsed (iCode *ic, operand *op)
{
if (ic->depth)
OP_SYMBOL (op)->used += 1;
}
+/*-----------------------------------------------------------------*/
+/* rliveClear - clears the rlive bitVectors */
+/*-----------------------------------------------------------------*/
+static 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;
+ }
+ }
+}
+
/*-----------------------------------------------------------------*/
/* 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
-rlivePoint (eBBlock ** ebbs, int count)
+static void
+rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
{
int i, key;
eBBlock *succ;
{
incUsed (ic, IC_JTCOND(ic));
- if (!IS_ITEMP(IC_JTCOND(ic)))
+ if (!IS_AUTOSYM(IC_JTCOND(ic)))
continue;
- unvisitBlocks(ebbs, count);
- ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
- findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
+ 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;
}
{
incUsed (ic, IC_COND(ic));
- if (!IS_ITEMP(IC_COND(ic)))
+ if (!IS_AUTOSYM(IC_COND(ic)))
continue;
- unvisitBlocks (ebbs, count);
- ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
- findNextUse (ebbs[i], ic->next, IC_COND(ic));
+ 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_ITEMP(IC_LEFT(ic)))
+ if (IS_AUTOSYM(IC_LEFT(ic)) &&
+ ic->op != ADDRESS_OF)
{
-
- 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)
- {
- markAlive (ic, lic->prev, IC_LEFT (ic)->key);
- break;
- }
- }
- }
+ 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_ITEMP(IC_RIGHT(ic)))
+ if (IS_AUTOSYM(IC_RIGHT(ic)))
{
- unvisitBlocks(ebbs, count);
- ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
- findNextUse (ebbs[i], ic->next, 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_ITEMP(IC_RESULT(ic)))
+ if (IS_AUTOSYM(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))
+ {
+ 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))
alive = succ->sch->rlive;
while ((succ = setNextItem (ebbs[i]->succList)))
{
- alive = bitVectIntersect (alive, succ->sch->rlive);
+ if (succ->sch)
+ alive = bitVectIntersect (alive, succ->sch->rlive);
}
- alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
+ 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;
sym2 = hTabItemWithKey(liveRanges, key2);
-
+
if (!sym2->isitmp)
continue;
IS_ITEMP(IC_RESULT(ic)) &&
(IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
{
- if (OP_SYMBOL(IC_RESULT(ic))->key == key1)
+ 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 (OP_SYMBOL(IC_RESULT(ic))->key == key2)
+ 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)
if (bitVectBitValue (defs, i) &&
(ic = hTabItemWithKey (iCodehTab, i)) &&
(ic->seq >= fseq && ic->seq <= toseq))
-
return FALSE;
}
/*-----------------------------------------------------------------*/
/* adjustIChain - correct the sch and ech pointers */
/*-----------------------------------------------------------------*/
-void
+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;
/* computeLiveRanges - computes the live ranges for variables */
/*-----------------------------------------------------------------*/
void
-computeLiveRanges (eBBlock ** ebbs, int count)
+computeLiveRanges (eBBlock ** ebbs, int count, bool emitWarnings)
{
/* first look through all blocks and adjust the
sch and ech pointers */
/* mark the ranges live for each point */
setToNull ((void *) &liveRanges);
- rlivePoint (ebbs, count);
+ rlivePoint (ebbs, count, emitWarnings);
/* mark the from & to live ranges for variables used */
markLiveRanges (ebbs, count);
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, 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
projects / fw / sdcc / blobdiff