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 <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 *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 */
/*-----------------------------------------------------------------*/
-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;
+
+ 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;
+
+ 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;
- 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 */
/*-----------------------------------------------------------------*/
-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
projects / fw / sdcc / blobdiff