X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=src%2FSDCClrange.c;h=33dddbad685b58a07415ef32de55c4a457d7ce7a;hb=7b0cd93b7bd04b332f409c2ece675f3943bbd70a;hp=eea9a0751f7958277bc042ed43411a5be17ccc35;hpb=c1f031d23e612a4c2625ba1db2121bca4722a005;p=fw%2Fsdcc diff --git a/src/SDCClrange.c b/src/SDCClrange.c index eea9a075..33dddbad 100644 --- a/src/SDCClrange.c +++ b/src/SDCClrange.c @@ -24,482 +24,705 @@ -------------------------------------------------------------------------*/ #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(); } +