X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=src%2FSDCClrange.c;h=c4a5bcc2959a180b2a67d7b7e5499682aa854551;hb=80972b2e54c9b88f11c27b878874fd2a6a681391;hp=b33428c33872323674116277bee3697e6ed326f5;hpb=c110ea5c33885daae1be0519a344473f68b1f6f7;p=fw%2Fsdcc diff --git a/src/SDCClrange.c b/src/SDCClrange.c index b33428c3..c4a5bcc2 100644 --- a/src/SDCClrange.c +++ b/src/SDCClrange.c @@ -8,19 +8,19 @@ under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. - + This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. - + You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - + In other words, you are welcome to use, share and improve this program. You are forbidden to forbid anyone else to use, share and improve - what you give them. Help stamp out software-hoarding! + what you give them. Help stamp out software-hoarding! -------------------------------------------------------------------------*/ #include "common.h" @@ -31,10 +31,15 @@ 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 +void hashiCodeKeys (eBBlock ** ebbs, int count) { int i; @@ -43,14 +48,14 @@ hashiCodeKeys (eBBlock ** ebbs, int count) { iCode *ic; for (ic = ebbs[i]->sch; ic; ic = ic->next) - hTabAddItem (&iCodehTab, ic->key, ic); + hTabAddItem (&iCodehTab, ic->key, ic); } } /*-----------------------------------------------------------------*/ /* sequenceiCode - creates a sequence number for the iCode & add */ /*-----------------------------------------------------------------*/ -void +static void sequenceiCode (eBBlock ** ebbs, int count) { int i; @@ -74,7 +79,8 @@ sequenceiCode (eBBlock ** ebbs, int count) /*-----------------------------------------------------------------*/ /* setFromRange - sets the from range of a given operand */ /*-----------------------------------------------------------------*/ -void +#if 0 +static void setFromRange (operand * op, int from) { /* only for compiler defined temporaries */ @@ -90,11 +96,12 @@ setFromRange (operand * op, int from) OP_LIVEFROM (op) > from) OP_LIVEFROM (op) = from; } +#endif /*-----------------------------------------------------------------*/ /* setToRange - set the range to for an operand */ /*-----------------------------------------------------------------*/ -void +void setToRange (operand * op, int to, bool check) { /* only for compiler defined temps */ @@ -118,7 +125,7 @@ setToRange (operand * op, int to, bool check) /*-----------------------------------------------------------------*/ /* setFromRange - sets the from range of a given operand */ /*-----------------------------------------------------------------*/ -void +static void setLiveFrom (symbol * sym, int from) { if (!sym->liveFrom || sym->liveFrom > from) @@ -128,7 +135,7 @@ setLiveFrom (symbol * sym, int from) /*-----------------------------------------------------------------*/ /* setToRange - set the range to for an operand */ /*-----------------------------------------------------------------*/ -void +static void setLiveTo (symbol * sym, int to) { if (!sym->liveTo || sym->liveTo < to) @@ -138,21 +145,21 @@ setLiveTo (symbol * sym, int to) /*-----------------------------------------------------------------*/ /* markLiveRanges - for each operand mark the liveFrom & liveTo */ /*-----------------------------------------------------------------*/ -void +static void markLiveRanges (eBBlock ** ebbs, int count) { int i, key; symbol *sym; - + for (i = 0; i < count; i++) { iCode *ic; - + for (ic = ebbs[i]->sch; ic; ic = ic->next) { if (ic->op == CALL || ic->op == PCALL) - if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses)) - bitVectUnSetBit (ebbs[i]->defSet, ic->key); + if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses)) + bitVectUnSetBit (ebbs[i]->defSet, ic->key); /* for all iTemps alive at this iCode */ for (key = 1; key < ic->rlive->size; key++) @@ -172,7 +179,7 @@ markLiveRanges (eBBlock ** ebbs, int count) /*-----------------------------------------------------------------*/ /* markAlive - marks the operand as alive between sic and eic */ /*-----------------------------------------------------------------*/ -void +static void markAlive (iCode * sic, iCode * eic, int key) { iCode *dic; @@ -187,7 +194,7 @@ markAlive (iCode * sic, iCode * eic, int key) /* findNextUseSym - finds the next use of the symbol and marks it */ /* alive in between */ /*-----------------------------------------------------------------*/ -int +static int findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym) { int retval = 0; @@ -219,7 +226,8 @@ findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym) if (ebp->visited) return 0; - ebp->visited = 1; + if (ic == ebp->sch) + ebp->visited = 1; /* for all remaining instructions in current block */ for (uic = ic; uic; uic = uic->next) @@ -236,7 +244,7 @@ findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym) return 1; } continue; - } + } if (uic->op == IFX) { @@ -246,7 +254,7 @@ findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym) return 1; } continue; - } + } if (IS_ITEMP (IC_LEFT (uic))) if (IC_LEFT (uic)->key == sym->key) @@ -287,7 +295,7 @@ check_successors: if (retval) { - markAlive (ic, ebp->ech, sym->key); + if (ic) markAlive (ic, ebp->ech, sym->key); return 1; } @@ -298,7 +306,7 @@ check_successors: /* findNextUse - finds the next use of the operand and marks it */ /* alive in between */ /*-----------------------------------------------------------------*/ -int +static int findNextUse (eBBlock *ebp, iCode *ic, operand *op) { if (op->isaddr) @@ -312,7 +320,8 @@ findNextUse (eBBlock *ebp, iCode *ic, operand *op) /*-----------------------------------------------------------------*/ /* unvisitBlocks - clears visited in all blocks */ /*-----------------------------------------------------------------*/ -void unvisitBlocks (eBBlock ** ebbs, int count) +static void +unvisitBlocks (eBBlock ** ebbs, int count) { int i; @@ -320,10 +329,164 @@ void unvisitBlocks (eBBlock ** ebbs, int count) ebbs[i]->visited = 0; } +/*------------------------------------------------------------------*/ +/* markWholeLoop - mark the symbol 'key' alive in all blocks */ +/* included by the outermost loop */ +/*------------------------------------------------------------------*/ +static void +markWholeLoop (eBBlock *ebp, int key) +{ + eBBlock *ebpi; + + /* avoid endless loops */ + ebp->visited = 1; + + /* recurse through all predecessors */ + for (ebpi = setFirstItem (ebp->predList); + ebpi; + ebpi = setNextItem (ebp->predList)) + { + if (ebpi->visited) + continue; + /* is the predecessor still in the loop? */ + if (ebpi->depth == 0) + continue; + markWholeLoop (ebpi, key); + } + + /* recurse through all successors */ + for (ebpi = setFirstItem (ebp->succList); + ebpi; + ebpi = setNextItem (ebp->succList)) + { + if (ebpi->visited) + continue; + if (ebpi->depth == 0) + continue; + markWholeLoop (ebpi, key); + } + + markAlive (ebp->sch, ebp->ech, key); +} + +/*------------------------------------------------------------------*/ +/* findPrevUseSym - search for a previous definition of a symbol in */ +/* - the previous icodes */ +/* - all branches of predecessors */ +/*------------------------------------------------------------------*/ +static bool +findPrevUseSym (eBBlock *ebp, iCode *ic, symbol * sym) +{ + eBBlock * pred; + iCode * uic; + + if (ebp->visited) + { + /* already visited: this branch must have been succesfull, */ + /* because otherwise the search would have been aborted. */ + return TRUE; + } + ebp->visited = 1; + + /* search backward in the current block */ + for (uic = ic; uic; uic = uic->prev) + { + if (!POINTER_SET (uic) && IS_AUTOSYM (IC_RESULT (uic))) + { + if (IC_RESULT (uic)->key == sym->key) + { + /* Ok, found a definition */ + return TRUE; + } + } + /* address taken from symbol? */ + if (uic->op == ADDRESS_OF && IS_AUTOSYM (IC_LEFT (uic))) + { + if (IC_LEFT (uic)->key == sym->key) + { + /* Ok, found a definition */ + return TRUE; + } + } + } + + /* There's no definition in this bblock, */ + /* let's have a look at all predecessors. */ + pred = setFirstItem (ebp->predList); + if (!pred) + { + /* no more predecessors and nothing found yet :-( */ + return FALSE; + } + for (; pred; pred = setNextItem (ebp->predList)) + { + /* recurse into all predecessors */ + if (!findPrevUseSym (pred, pred->ech, sym)) + { + /* found nothing: abort */ + return FALSE; + } + } + + /* Success! Went through all branches with no abort: */ + /* all branches end with a definition */ + return TRUE; +} + +/*------------------------------------------------------------------*/ +/* findPrevUse - search for a previous definition of an operand */ +/* If there's no definition let's: */ +/* - emit a warning */ +/* - fix the life range, if the symbol is used in */ +/* a loop */ +/*------------------------------------------------------------------*/ +static void +findPrevUse (eBBlock *ebp, iCode *ic, operand *op, + eBBlock ** ebbs, int count, + bool emitWarnings) +{ + unvisitBlocks (ebbs, count); + + if (op->isaddr) + OP_SYMBOL (op)->isptr = 1; + OP_SYMBOL (op)->key = op->key; + + /* There must be a definition in each branch of predecessors */ + if (!findPrevUseSym (ebp, ic->prev, OP_SYMBOL(op))) + { + /* computeLiveRanges() is called twice */ + if (emitWarnings) + { + if (IS_ITEMP (op)) + { + if (OP_SYMBOL (op)->prereqv) + { + werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT, + OP_SYMBOL (op)->prereqv->name); + OP_SYMBOL (op)->prereqv->reqv = NULL; + OP_SYMBOL (op)->prereqv->allocreq = 1; + } + } + else + { + werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT, + OP_SYMBOL (op)->name); + } + } + /* is this block part of a loop? */ + if (IS_ITEMP (op) && ebp->depth != 0) + { + /* extend the life range to the outermost loop */ + unvisitBlocks(ebbs, count); + markWholeLoop (ebp, op->key); + } + } +} + /*-----------------------------------------------------------------*/ -/* unvisitBlocks - clears visited in all blocks */ +/* incUsed - increment a symbol's usage count */ /*-----------------------------------------------------------------*/ -void +static void incUsed (iCode *ic, operand *op) { if (ic->depth) @@ -332,11 +495,35 @@ incUsed (iCode *ic, operand *op) OP_SYMBOL (op)->used += 1; } +/*-----------------------------------------------------------------*/ +/* rliveClear - clears the rlive bitVectors */ +/*-----------------------------------------------------------------*/ +static void +rliveClear (eBBlock ** ebbs, int count) +{ + int i; + + /* for all blocks do */ + for (i = 0; i < count; i++) + { + iCode *ic; + + /* for all instructions in this block do */ + for (ic = ebbs[i]->sch; ic; ic = ic->next) + { + freeBitVect (ic->rlive); + ic->rlive = NULL; + } + } +} + /*-----------------------------------------------------------------*/ /* rlivePoint - for each point compute the ranges that are alive */ +/* The live range is only stored for ITEMPs; the same code is used */ +/* to find use of unitialized AUTOSYMs (an ITEMP is an AUTOSYM). */ /*-----------------------------------------------------------------*/ -void -rlivePoint (eBBlock ** ebbs, int count) +static void +rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings) { int i, key; eBBlock *succ; @@ -361,12 +548,16 @@ rlivePoint (eBBlock ** ebbs, int count) { incUsed (ic, IC_JTCOND(ic)); - if (!IS_ITEMP(IC_JTCOND(ic))) + if (!IS_AUTOSYM(IC_JTCOND(ic))) continue; - unvisitBlocks(ebbs, count); - ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key); - findNextUse (ebbs[i], ic->next, IC_JTCOND(ic)); + findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings); + if (IS_ITEMP(IC_JTCOND(ic))) + { + unvisitBlocks(ebbs, count); + ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key); + findNextUse (ebbs[i], ic->next, IC_JTCOND(ic)); + } continue; } @@ -375,12 +566,16 @@ rlivePoint (eBBlock ** ebbs, int count) { incUsed (ic, IC_COND(ic)); - if (!IS_ITEMP(IC_COND(ic))) + if (!IS_AUTOSYM(IC_COND(ic))) continue; - unvisitBlocks (ebbs, count); - ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key); - findNextUse (ebbs[i], ic->next, IC_COND(ic)); + findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings); + if (IS_ITEMP(IC_COND(ic))) + { + unvisitBlocks (ebbs, count); + ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key); + findNextUse (ebbs[i], ic->next, IC_COND(ic)); + } continue; } @@ -388,48 +583,63 @@ rlivePoint (eBBlock ** ebbs, int count) if (IS_SYMOP(IC_LEFT(ic))) { incUsed (ic, IC_LEFT(ic)); - if (IS_ITEMP(IC_LEFT(ic))) + if (IS_AUTOSYM(IC_LEFT(ic)) && + ic->op != ADDRESS_OF) { - - unvisitBlocks(ebbs, count); - ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key); - findNextUse (ebbs[i], ic->next, IC_LEFT(ic)); - - /* if this is a send extend the LR to the call */ - if (ic->op == SEND) - { - iCode *lic; - for (lic = ic; lic; lic = lic->next) - { - if (lic->op == CALL) - { - markAlive (ic, lic->prev, IC_LEFT (ic)->key); - break; - } - } - } + findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings); + if (IS_ITEMP(IC_LEFT(ic))) + { + unvisitBlocks(ebbs, count); + ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key); + findNextUse (ebbs[i], ic->next, IC_LEFT(ic)); + + /* if this is a send extend the LR to the call */ + if (ic->op == SEND) + { + iCode *lic; + for (lic = ic; lic; lic = lic->next) + { + if (lic->op == CALL || lic->op == PCALL) + { + markAlive (ic, lic->prev, IC_LEFT (ic)->key); + break; + } + } + } + } } } if (IS_SYMOP(IC_RIGHT(ic))) { incUsed (ic, IC_RIGHT(ic)); - if (IS_ITEMP(IC_RIGHT(ic))) + if (IS_AUTOSYM(IC_RIGHT(ic))) { - unvisitBlocks(ebbs, count); - ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key); - findNextUse (ebbs[i], ic->next, IC_RIGHT(ic)); + findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings); + if (IS_ITEMP(IC_RIGHT(ic))) + { + unvisitBlocks(ebbs, count); + ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key); + findNextUse (ebbs[i], ic->next, IC_RIGHT(ic)); + } } } if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic))) incUsed (ic, IC_RESULT(ic)); - if (IS_ITEMP(IC_RESULT(ic))) + if (IS_AUTOSYM(IC_RESULT(ic))) { - unvisitBlocks(ebbs, count); - ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key); - findNextUse (ebbs[i], ic->next, IC_RESULT(ic)); + if (POINTER_SET(ic)) + { + findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings); + } + if (IS_ITEMP(IC_RESULT(ic))) + { + unvisitBlocks(ebbs, count); + ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key); + findNextUse (ebbs[i], ic->next, IC_RESULT(ic)); + } } if (!POINTER_SET(ic) && IC_RESULT(ic)) @@ -447,11 +657,15 @@ rlivePoint (eBBlock ** ebbs, int count) alive = succ->sch->rlive; while ((succ = setNextItem (ebbs[i]->succList))) { - alive = bitVectIntersect (alive, succ->sch->rlive); + if (succ->sch) + alive = bitVectIntersect (alive, succ->sch->rlive); } - alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive); + if (ebbs[i]->ech) + alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive); + if(!alive) + continue; for (key = 1; key < alive->size; key++) { if (!bitVectBitValue (alive, key)) @@ -501,7 +715,7 @@ computeClash (eBBlock ** ebbs, int count) continue; sym2 = hTabItemWithKey(liveRanges, key2); - + if (!sym2->isitmp) continue; @@ -511,7 +725,9 @@ computeClash (eBBlock ** ebbs, int count) IS_ITEMP(IC_RESULT(ic)) && (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic)))) { - if (OP_SYMBOL(IC_RESULT(ic))->key == key1) + if (OP_SYMBOL(IC_RESULT(ic))->key == key1 + && sym1->liveFrom == ic->seq + && sym2->liveTo == ic->seq) { if (IS_SYMOP(IC_LEFT(ic))) if (OP_SYMBOL(IC_LEFT(ic))->key == key2) @@ -521,7 +737,9 @@ computeClash (eBBlock ** ebbs, int count) continue; } - if (OP_SYMBOL(IC_RESULT(ic))->key == key2) + if (OP_SYMBOL(IC_RESULT(ic))->key == key2 + && sym2->liveFrom == ic->seq + && sym1->liveTo == ic->seq) { if (IS_SYMOP(IC_LEFT(ic))) if (OP_SYMBOL(IC_LEFT(ic))->key == key1) @@ -570,7 +788,6 @@ allDefsOutOfRange (bitVect * defs, int fseq, int toseq) if (bitVectBitValue (defs, i) && (ic = hTabItemWithKey (iCodehTab, i)) && (ic->seq >= fseq && ic->seq <= toseq)) - return FALSE; } @@ -592,23 +809,27 @@ notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic) /*-----------------------------------------------------------------*/ /* adjustIChain - correct the sch and ech pointers */ /*-----------------------------------------------------------------*/ -void +static void adjustIChain (eBBlock ** ebbs, int count) { int i; - + for (i = 0; i < count; i++) { iCode *ic; - + if (ebbs[i]->noPath) continue; ic = ebbs[i]->sch; + + /* is there any code for this eBBlock? (e.g. ROM assignment) */ + if(!ic)continue; + while (ic->prev) ic = ic->prev; ebbs[i]->sch = ic; - + ic = ebbs[i]->ech; while (ic->next) ic = ic->next; @@ -620,7 +841,7 @@ adjustIChain (eBBlock ** ebbs, int count) /* computeLiveRanges - computes the live ranges for variables */ /*-----------------------------------------------------------------*/ void -computeLiveRanges (eBBlock ** ebbs, int count) +computeLiveRanges (eBBlock ** ebbs, int count, bool emitWarnings) { /* first look through all blocks and adjust the sch and ech pointers */ @@ -639,7 +860,7 @@ computeLiveRanges (eBBlock ** ebbs, int count) /* mark the ranges live for each point */ setToNull ((void *) &liveRanges); - rlivePoint (ebbs, count); + rlivePoint (ebbs, count, emitWarnings); /* mark the from & to live ranges for variables used */ markLiveRanges (ebbs, count); @@ -648,3 +869,68 @@ computeLiveRanges (eBBlock ** ebbs, int count) computeClash(ebbs, count); } +/*-----------------------------------------------------------------*/ +/* recomputeLiveRanges - recomputes the live ranges for variables */ +/*-----------------------------------------------------------------*/ +void +recomputeLiveRanges (eBBlock ** ebbs, int count) +{ + symbol * sym; + int key; + + /* clear all rlive bitVectors */ + rliveClear (ebbs, count); + + sym = hTabFirstItem (liveRanges, &key); + if (sym) + { + do { + sym->used = 0; + sym->liveFrom = 0; + sym->liveTo = 0; + freeBitVect (sym->clashes); + sym->clashes = NULL; + } while ( (sym = hTabNextItem (liveRanges, &key))); + } + + /* do the LR computation again */ + computeLiveRanges (ebbs, count, FALSE); +} + +/*-----------------------------------------------------------------*/ +/* dump icode->rlive in all blocks */ +/*-----------------------------------------------------------------*/ +#if 0 +void +dumpIcRlive (eBBlock ** ebbs, int count) +{ + int i, j; + iCode *ic; + + /* for all blocks do */ + for (i = 0; i < count; i++) + { + printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name); + /* for all instructions in this block do */ + for (ic = ebbs[i]->sch; ic; ic = ic->next) + { + printf ("\tic->key %d\n", ic->key); + + if (!ic->rlive) + continue; + /* for all live Ranges alive at this point */ + for (j = 1; j < ic->rlive->size; j++) + { + symbol *sym; + + if (!bitVectBitValue (ic->rlive, j)) + continue; + + /* find the live range we are interested in */ + if ((sym = hTabItemWithKey (liveRanges, j))) + printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name); + } + } + } +} +#endif