-------------------------------------------------------------------------*/
#include "common.h"
+#include "limits.h"
-int iCodeSeq = 0 ;
+int iCodeSeq = 0;
hTab *liveRanges = NULL;
hTab *iCodehTab = NULL;
+hTab *iCodeSeqhTab = NULL;
/*-----------------------------------------------------------------*/
/* sequenceiCode - creates a sequence number for the iCode & add */
/*-----------------------------------------------------------------*/
-void sequenceiCode (eBBlock **ebbs, int count)
+void
+sequenceiCode (eBBlock ** ebbs, int count)
{
- int i;
+ 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);
+ 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 */
/*-----------------------------------------------------------------*/
-DEFSETFUNC(markVisited)
+DEFSETFUNC (markVisited)
{
- eBBlock *ebp = item;
-
- if (ebp->visited)
- return 0;
- ebp->visited = 1;
- applyToSet(ebp->succList,markVisited);
+ eBBlock *ebp = item;
+
+ if (ebp->visited)
return 0;
+ ebp->visited = 1;
+ applyToSet (ebp->succList, markVisited);
+ return 0;
}
/*-----------------------------------------------------------------*/
/* isOpAlive - checks to see if the usage in this block is the */
/* uses the same definitions as this one */
/*-----------------------------------------------------------------*/
-DEFSETFUNC(isOpAlive)
+DEFSETFUNC (isOpAlive)
{
- eBBlock *ebp = item;
- V_ARG(operand *,op);
- V_ARG(eBBlock *,orig);
- V_ARG(iCode *,ic);
+ eBBlock *ebp = item;
+ V_ARG (operand *, op);
+ V_ARG (eBBlock *, orig);
+ V_ARG (iCode *, ic);
- if (ebp->visited)
- return 0;
-
- ebp->visited = 1;
-
- /* if we have reached the originating block */
- /* or this block has some definiton for it */
- /* then check if it is used between start & */
- /* this point */
- if ( ebp == orig ||
- bitVectBitsInCommon(OP_DEFS(op),ebp->defSet))
- if (usedBetweenPoints (op,ebp->sch,ic))
- return 1;
- else {
- applyToSet(ebp->succList,markVisited);
- return 0;
- }
- else
- /* choosing this more expensive one since
- killDeadCode will take away some definitions
- but there is not way right now to take away
- the usage information for the corresponding
- usages, this will lead to longer live ranges */
- if (usedInRemaining(op,ebp->sch))
- return 1;
+ if (ebp->visited)
+ return 0;
+ ebp->visited = 1;
- return (applyToSet(ebp->succList,isOpAlive,op,orig,ic));
+ /* if we have reached the originating block */
+ /* or this block has some definiton for it */
+ /* then check if it is used between start & */
+ /* this point */
+ if (ebp == orig ||
+ bitVectBitsInCommon (OP_DEFS (op), ebp->defSet))
+ if (usedBetweenPoints (op, ebp->sch, ic))
+ return 1;
+ else
+ {
+ applyToSet (ebp->succList, markVisited);
+ return 0;
+ }
+ else
+ /* choosing this more expensive one since
+ killDeadCode will take away some definitions
+ but there is not way right now to take away
+ the usage information for the corresponding
+ usages, this will lead to longer live ranges */
+ if (usedInRemaining (op, ebp->sch))
+ return 1;
+
+
+ return (applyToSet (ebp->succList, isOpAlive, op, orig, ic));
}
/*-----------------------------------------------------------------*/
/* isLastUse - return TRUE if no usage of this operand after this */
/*-----------------------------------------------------------------*/
-int isLastUse (operand *op, eBBlock *ebp, iCode *ic,
- eBBlock **ebbs, int count)
+int
+isLastUse (operand * op, eBBlock * ebp, iCode * ic,
+ eBBlock ** ebbs, int count)
{
- int i;
+ 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;
+ /* 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;
+ /* this is the last use */
+ return 1;
}
/*-----------------------------------------------------------------*/
/* unionDefsUsed - unions the defsUsed in a block */
/*-----------------------------------------------------------------*/
-DEFSETFUNC(unionDefsUsed)
+DEFSETFUNC (unionDefsUsed)
{
- eBBlock *ebp = item;
- V_ARG(bitVect **,bvp);
+ eBBlock *ebp = item;
+ V_ARG (bitVect **, bvp);
- if (ebp->visited)
- return 0;
+ if (ebp->visited)
+ return 0;
- ebp->visited = 1;
+ ebp->visited = 1;
- *bvp = bitVectUnion(*bvp, ebp->usesDefs);
- applyToSet(ebp->succList,unionDefsUsed,bvp);
- return 0;
+ *bvp = bitVectUnion (*bvp, ebp->usesDefs);
+ applyToSet (ebp->succList, unionDefsUsed, bvp);
+ return 0;
}
/*-----------------------------------------------------------------*/
/* setFromRange - sets the from range of a given operand */
/*-----------------------------------------------------------------*/
-void setFromRange (operand *op, int from)
+void
+setFromRange (operand * op, int from)
{
- /* only for compiler defined temporaries */
- if (!IS_ITEMP(op))
- return ;
+ /* only for compiler defined temporaries */
+ if (!IS_ITEMP (op))
+ return;
- hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
+ hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
- if (op->isaddr)
- OP_SYMBOL(op)->isptr = 1;
+ if (op->isaddr)
+ OP_SYMBOL (op)->isptr = 1;
- if (!OP_LIVEFROM(op) ||
- OP_LIVEFROM(op) > from)
- OP_LIVEFROM(op) = from;
+ if (!OP_LIVEFROM (op) ||
+ OP_LIVEFROM (op) > from)
+ OP_LIVEFROM (op) = from;
}
/*-----------------------------------------------------------------*/
/* setToRange - set the range to for an operand */
/*-----------------------------------------------------------------*/
-void setToRange (operand *op,int to, bool check)
-{
- /* only for compiler defined temps */
- if (!IS_ITEMP(op))
- return ;
-
- OP_SYMBOL(op)->key = op->key;
- hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
-
- if (op->isaddr)
- OP_SYMBOL(op)->isptr = 1;
-
- if (check)
- if (!OP_LIVETO(op))
- OP_LIVETO(op) = to;
- else ;
- else
- OP_LIVETO(op) = to;
+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;
}
+/*-----------------------------------------------------------------*/
+/* firstDeOf - finds the first definition in seq for op */
+/*-----------------------------------------------------------------*/
+static iCode *
+firstDefOf (operand * op)
+{
+ int i;
+ iCode *ric = NULL, *lic = NULL;
+ int fSeq = INT_MAX;
+
+ if (!OP_DEFS (op))
+ return NULL;
+
+ for (i = 0; i < OP_DEFS (op)->size; i++)
+ {
+ if (bitVectBitValue (OP_DEFS (op), i) &&
+ (lic = hTabItemWithKey (iCodehTab, i)) &&
+ lic->seq < fSeq)
+ {
+ fSeq = lic->seq;
+ ric = lic;
+ }
+ }
+ return ric;
+}
/*-----------------------------------------------------------------*/
-/* operandLUse - check and set the last use for a given operand */
+/* useDefLoopCheck - check for uses before init inside loops */
/*-----------------------------------------------------------------*/
-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);
+static void
+useDefLoopCheck (operand * op, iCode * ic)
+{
+ /* this is for situations like the following
+ int a,b;
+
+ while (...) {
+ a = ... ;
+ ...
+ _some_usage_of_b_;
+ ...
+ b = ... ;
+ }
+ in this case the definition of 'b' will flow to the usages
+ but register allocator cannot handle these situations.so
+ will mark as spilt */
+
+ int i = 0, fdSeq;
+ int er = 0;
+ iCode *tic;
+
+ /* get the first definition */
+ if (!(tic = firstDefOf (op)))
+ return;
+
+ fdSeq = tic->seq;
+ /* now go thru the usages & make sure they follow
+ the first definition */
+ for (i = 0; i <= OP_USES (op)->size; i++)
+ {
+ if (bitVectBitValue (OP_USES (op), i) &&
+ (tic = hTabItemWithKey (iCodehTab, i)) &&
+ tic->seq < fdSeq)
+ {
+ er = 1;
+ break;
}
- op = operandFromOperand(op);
- setToRange(op,torange,FALSE);
- }
- ic->uses = bitVectSetBit(ic->uses,op->key);
-
+ }
+
+ /* found a usage without definition */
+ if (er)
{
- link *type = operandType(op);
- link *etype = getSpec(type);
-
- /* good place to check if unintialised */
- if ((IS_TRUE_SYMOP(op) || OP_SYMBOL(op)->isreqv) &&
- OP_SYMBOL(op)->islocal &&
- !IS_AGGREGATE(type) &&
- !IS_FUNC(type) &&
- ic->op != ADDRESS_OF &&
- !IS_STATIC(etype) ) {
-
- if (bitVectIsZero(op->usesDefs)) {
- OP_SYMBOL(op)->isspilt = 1;
-
- if (OP_SYMBOL(op)->isreqv &&
- !OP_SYMBOL(op)->_isparm && SPIL_LOC(op) ) {
+ if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
+ {
- werror(W_LOCAL_NOINIT,
- SPIL_LOC(op)->name,
- ic->filename,ic->lineno);
- } else {
+ werror (W_LOCAL_NOINIT,
+ SPIL_LOC (op)->name,
+ ic->filename, ic->lineno);
+ }
+ else
+ {
- werror(W_LOCAL_NOINIT,
- OP_SYMBOL(op)->name,
- ic->filename,ic->lineno);
- }
- }
+ werror (W_LOCAL_NOINIT,
+ OP_SYMBOL (op)->name,
+ ic->filename, ic->lineno);
}
+#if 0 // this will create a segfault: bug #498971
+ OP_SYMBOL (op)->isspilt = 1;
+#endif
}
- return op;
}
+
/*-----------------------------------------------------------------*/
-/* compLastUse - computes the last usage with certainty */
+/* operandLUse - check and set the last use for a given operand */
/*-----------------------------------------------------------------*/
-void compLastUse ()
+operand *
+operandLUse (operand * op, eBBlock ** ebbs,
+ int count, iCode * ic, eBBlock * ebp)
{
- 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 );
+ 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 a SEND then the toRange should be extended
+ to the call */
+ if (ic->op == SEND) {
+ iCode *lic ;
+ for (lic = ic->next ; lic ; lic = lic->next) {
+ if (lic->op == CALL || lic->op == PCALL) break;
+ }
+ /* found it : mark */
+ if (lic) torange = lic->prev->seq;
+ }
+ /* if this is the last use then if this block belongs
+ to a loop & some definition comes into the loop
+ then extend the live range to the end of the loop */
+ if (ebp->partOfLoop
+ && hasIncomingDefs (ebp->partOfLoop, op))
+ {
+ torange = findLoopEndSeq (ebp->partOfLoop);
}
+
+ op = operandFromOperand (op);
+ setToRange (op, torange, FALSE);
+ }
+ ic->uses = bitVectSetBit (ic->uses, op->key);
+
+ if (!OP_SYMBOL (op)->udChked)
+ {
+ sym_link *type = operandType (op);
+ sym_link *etype = getSpec (type);
+
+ OP_SYMBOL (op)->udChked = 1;
+ /* good place to check if unintialised */
+ if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
+ OP_SYMBOL (op)->islocal &&
+ !IS_AGGREGATE (type) &&
+ !IS_FUNC (type) &&
+ ic->op != ADDRESS_OF &&
+ !IS_STATIC (etype))
+ {
+
+ if (bitVectIsZero (op->usesDefs) && OP_SYMBOL(op)->ival==NULL)
+ {
+ OP_SYMBOL (op)->isspilt = 1;
+
+ if (OP_SYMBOL (op)->isreqv &&
+ !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
+ {
+
+ werror (W_LOCAL_NOINIT,
+ SPIL_LOC (op)->name,
+ ic->filename, ic->lineno);
+ }
+ else
+ {
- /* got it */
- if (maxKey)
- sym->liveTo = maxKey;
+ werror (W_LOCAL_NOINIT,
+ OP_SYMBOL (op)->name,
+ ic->filename, ic->lineno);
+ }
+ }
+ else
+ {
+ if (ebp->depth && op->usesDefs &&
+ !OP_SYMBOL (op)->_isparm)
+ {
+ /* check non-inits inside loops */
+ useDefLoopCheck (op, ic);
+ }
+ }
+ }
}
+ return op;
}
/*-----------------------------------------------------------------*/
/* killAllAlive - mark all the definitions living with this seq */
/*-----------------------------------------------------------------*/
-void killAllAlive (int seq)
+void
+killAllAlive (int seq)
{
- symbol *sym;
- int k;
+ symbol *sym;
+ int k;
- for (sym = hTabFirstItem(liveRanges,&k); sym;
- sym = hTabNextItem(liveRanges,&k))
- if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
- sym->liveTo = seq;
+ for (sym = hTabFirstItem (liveRanges, &k); sym;
+ sym = hTabNextItem (liveRanges, &k))
+ if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
+ sym->liveTo = seq;
}
/*-----------------------------------------------------------------*/
/* defUsedAfterLoop - all definitions & usages before sequence num */
/*-----------------------------------------------------------------*/
-bool defUsedAfterLoop (operand *op, int seq)
+bool
+defUsedAfterLoop (operand * op, int seq)
{
- int i;
- iCode *ic;
+ 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 ;
+ /* 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;
}
}
- return FALSE;
+ return FALSE;
}
/*-----------------------------------------------------------------*/
/* markLiveRanges - for each operand mark the liveFrom & liveTo */
/*-----------------------------------------------------------------*/
-void markLiveRanges (eBBlock *ebp, eBBlock **ebbs, int count)
+void
+markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
{
- iCode *ic;
- bitVect *defsUsed = NULL;
- bitVect *defsNotUsed = NULL;
- int i;
- /* for all the instructions */
- for (ic = ebp->sch ; ic ; ic = ic->next ) {
-
- if (ic->op == CALL || ic->op == PCALL) {
- setFromRange(IC_RESULT(ic),ic->seq);
- /* if the result has no usage then
- mark this as the end of its life too
- and take it away from the defs for the block*/
- if (bitVectIsZero(OP_SYMBOL(IC_RESULT(ic))->uses)) {
- setToRange(IC_RESULT(ic),ic->seq,FALSE);
- bitVectUnSetBit(ebp->defSet,ic->key);
+ 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);
}
}
- if (SKIP_IC2(ic))
- continue ;
+ if (SKIP_IC2 (ic))
+ continue;
- /* take care of the special icodes first */
- if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic))) {
- operandLUse (IC_JTCOND(ic),ebbs,count,ic,ebp);
- continue;
+ /* take care of the special icodes first */
+ if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
+ {
+ operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
+ continue;
}
-
- 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 ;
+ 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;
}
- /* 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 the definitions in the block */
+ /* compute and set the live from */
+ if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
+ {
+ for (i = 0; i < ebp->ldefs->size; i++)
+ {
+ iCode *dic;
+
+ if (bitVectBitValue (ebp->ldefs, 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);
+ }
+ }
}
- /* 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))) {
+ /* 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))
- continue;
+ /* if this is a register equvalent make sure
+ it is not defined or used anywhere after the loop */
+ if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
+ defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
+ continue;
- setToRange(IC_RESULT(dic),( ebp->lSeq ),FALSE);
+ setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
}
- }
+ }
}
- /* 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);
+ /* 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 we reach a lock with noPath to it then kill all
- the live ranges alive at this point */
+ /* 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);
+ if (ebp->entryLabel == returnLabel)
+ killAllAlive (ebp->fSeq);
}
/*-----------------------------------------------------------------*/
/* rlivePoint - for each point compute the ranges that are alive */
/*-----------------------------------------------------------------*/
-void rlivePoint (eBBlock **ebbs, int count)
+void
+rlivePoint (eBBlock ** ebbs, int count)
{
int i;
-
+
/* for all blocks do */
- for ( i = 0 ; i < count ; i++ ) {
+ for (i = 0; i < count; i++) {
iCode *ic;
-
+
/* for all instruction in the block do */
- for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
+ for (ic = ebbs[i]->sch; ic; ic = ic->next) {
symbol *lrange;
int k;
-
- ic->rlive = newBitVect(operandKey);
+
+ ic->rlive = newBitVect (operandKey);
/* for all symbols in the liverange table */
- for ( lrange = hTabFirstItem(liveRanges,&k); lrange;
- lrange = hTabNextItem(liveRanges,&k)) {
-
+ for (lrange = hTabFirstItem (liveRanges, &k); lrange;
+ lrange = hTabNextItem (liveRanges, &k)) {
+
+ /* if it is live then add the lrange to ic->rlive */
if (lrange->liveFrom <= ic->seq &&
- lrange->liveTo >= ic->seq )
- ic->rlive = bitVectSetBit(ic->rlive,lrange->key);
+ lrange->liveTo >= ic->seq) {
+ lrange->isLiveFcall |= ((lrange->liveFrom < ic->seq) &&
+ (ic->op == CALL || ic->op == PCALL || ic->op == SEND));
+ if (ic->op == CALL && lrange->liveFrom == ic->seq) continue;
+ ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
+ }
+ }
+#if 0
+ /* overlapping live ranges should be eliminated */
+ if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
+ if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic)) && /* left & right share the same spil location */
+ OP_SYMBOL(IC_RESULT(ic))->isreqv && /* left of assign is a register requivalent */
+ !OP_SYMBOL(IC_RIGHT(ic))->isreqv && /* right side is not */
+ OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key && /* right side live beyond this point */
+ bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 ) { /* left has multiple definitions */
+ SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
+ }
}
+#endif
}
- }
+ }
+}
+
+/*-----------------------------------------------------------------*/
+/* computeClash - find out which live ranges collide with others */
+/*-----------------------------------------------------------------*/
+static void computeClash ()
+{
+ hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
+ void *item;
+ symbol *outer, *inner;
+ int key, key1;
+
+ /* have to make a copy of the liveRanges hashTable :: UGHH .*/
+ for (item = hTabFirstItem(liveRanges,&key); item ;
+ item = hTabNextItem(liveRanges,&key)) {
+ hTabAddItem(&lRangeCopy,key,item);
+ }
+
+ /* outerloop : for each liverange do */
+ for (outer = hTabFirstItem(liveRanges,&key); outer ;
+ outer = hTabNextItem(liveRanges,&key)) {
+
+ /* if the liveFrom & To are the same then skip,
+ could happen for unused return values from functions */
+ if (outer->liveFrom == outer->liveTo) continue;
+
+ /* innerloop : for the inner loop we can start from the
+ item after the outer loop */
+ inner = hTabFirstItemWK (lRangeCopy,outer->key);
+ inner = hTabNextItem (lRangeCopy,&key1 );
+ for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
+
+ if (inner->liveFrom == inner->liveTo) continue;
+ if (inner->liveTo < outer->liveFrom) continue;
+ if (inner->liveFrom > outer->liveTo) continue;
+
+ /* if one of them are being defined where the other
+ one end , then no overlap (i.e. they can goto same registers */
+ if (inner->liveFrom == outer->liveTo ||
+ outer->liveFrom == inner->liveTo) continue;
+
+ /* so they overlap : set both their clashes */
+ inner->clashes = bitVectSetBit(inner->clashes,outer->key);
+ outer->clashes = bitVectSetBit(outer->clashes,inner->key);
+
+ /* check if they share the same spillocation */
+ if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
+ SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
+ if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
+ else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
+ else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
+ else SYM_SPIL_LOC(inner)=NULL;
+ }
+
+ }
+ }
+}
+
+/*-----------------------------------------------------------------*/
+/* 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;
+
+ }
+
+ return TRUE;
+}
+
+/*-----------------------------------------------------------------*/
+/* notUsedInBlock - not used in this block */
+/*-----------------------------------------------------------------*/
+int
+notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
+{
+ return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
+ allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
+ allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
}
/*-----------------------------------------------------------------*/
/* computeLiveRanges - computes the live ranges for variables */
/*-----------------------------------------------------------------*/
-void computeLiveRanges (eBBlock **ebbs, int count )
+void
+computeLiveRanges (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);
+ 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);
+ setToNull ((void **) &iCodeSeqhTab);
+ iCodeSeqhTab = 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);
+
+ /* mark the ranges live for each point */
+ rlivePoint (ebbs, count);
+
+ /* compute which overlaps with what */
+ computeClash();
}
+