1 /*-------------------------------------------------------------------------
3 SDCClrange.c - source file for live range computations
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
7 This program is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 In other words, you are welcome to use, share and improve this program.
22 You are forbidden to forbid anyone else to use, share and improve
23 what you give them. Help stamp out software-hoarding!
24 -------------------------------------------------------------------------*/
30 hTab *liveRanges = NULL;
31 hTab *iCodehTab = NULL;
32 hTab *iCodeSeqhTab = NULL;
34 /*-----------------------------------------------------------------*/
35 /* hashiCodeKeys - add all iCodes to the hash table */
36 /*-----------------------------------------------------------------*/
38 hashiCodeKeys (eBBlock ** ebbs, int count)
42 for (i = 0; i < count; i++)
45 for (ic = ebbs[i]->sch; ic; ic = ic->next)
46 hTabAddItem (&iCodehTab, ic->key, ic);
50 /*-----------------------------------------------------------------*/
51 /* sequenceiCode - creates a sequence number for the iCode & add */
52 /*-----------------------------------------------------------------*/
54 sequenceiCode (eBBlock ** ebbs, int count)
58 for (i = 0; i < count; i++)
62 ebbs[i]->fSeq = iCodeSeq + 1;
63 for (ic = ebbs[i]->sch; ic; ic = ic->next)
66 ic->depth = ebbs[i]->depth;
67 //hTabAddItem (&iCodehTab, ic->key, ic);
68 hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
70 ebbs[i]->lSeq = iCodeSeq;
74 /*-----------------------------------------------------------------*/
75 /* setFromRange - sets the from range of a given operand */
76 /*-----------------------------------------------------------------*/
78 setFromRange (operand * op, int from)
80 /* only for compiler defined temporaries */
84 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
87 OP_SYMBOL (op)->isptr = 1;
89 if (!OP_LIVEFROM (op) ||
90 OP_LIVEFROM (op) > from)
91 OP_LIVEFROM (op) = from;
94 /*-----------------------------------------------------------------*/
95 /* setToRange - set the range to for an operand */
96 /*-----------------------------------------------------------------*/
98 setToRange (operand * op, int to, bool check)
100 /* only for compiler defined temps */
104 OP_SYMBOL (op)->key = op->key;
105 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
108 OP_SYMBOL (op)->isptr = 1;
118 /*-----------------------------------------------------------------*/
119 /* setFromRange - sets the from range of a given operand */
120 /*-----------------------------------------------------------------*/
122 setLiveFrom (symbol * sym, int from)
124 if (!sym->liveFrom || sym->liveFrom > from)
125 sym->liveFrom = from;
128 /*-----------------------------------------------------------------*/
129 /* setToRange - set the range to for an operand */
130 /*-----------------------------------------------------------------*/
132 setLiveTo (symbol * sym, int to)
134 if (!sym->liveTo || sym->liveTo < to)
138 /*-----------------------------------------------------------------*/
139 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
140 /*-----------------------------------------------------------------*/
142 markLiveRanges (eBBlock ** ebbs, int count)
147 for (i = 0; i < count; i++)
151 for (ic = ebbs[i]->sch; ic; ic = ic->next)
153 if (ic->op == CALL || ic->op == PCALL)
154 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
155 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
157 /* for all iTemps alive at this iCode */
158 for (key = 1; key < ic->rlive->size; key++)
160 if (!bitVectBitValue(ic->rlive, key))
163 sym = hTabItemWithKey(liveRanges, key);
164 setLiveTo(sym, ic->seq);
165 setLiveFrom(sym, ic->seq);
172 /*-----------------------------------------------------------------*/
173 /* markAlive - marks the operand as alive between sic and eic */
174 /*-----------------------------------------------------------------*/
176 markAlive (iCode * sic, iCode * eic, int key)
180 for (dic = sic; dic != eic->next; dic = dic->next)
182 dic->rlive = bitVectSetBit (dic->rlive, key);
186 /*-----------------------------------------------------------------*/
187 /* findNextUseSym - finds the next use of the symbol and marks it */
188 /* alive in between */
189 /*-----------------------------------------------------------------*/
191 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
197 hTabAddItemIfNotP (&liveRanges, sym->key, sym);
200 goto check_successors;
202 /* if we check a complete block and the symbol */
203 /* is alive at the beginning of the block */
204 /* and not defined in the first instructions */
205 /* then a next use exists (return 1) */
206 if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
208 /* check if the first instruction is a def of this op */
209 if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
212 if (IS_ITEMP(IC_RESULT(ic)))
213 if (IC_RESULT(ic)->key == sym->key)
225 /* for all remaining instructions in current block */
226 for (uic = ic; uic; uic = uic->next)
232 if (uic->op == JUMPTABLE)
234 if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
236 markAlive(ic, uic, sym->key);
244 if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
246 markAlive(ic, uic, sym->key);
252 if (IS_ITEMP (IC_LEFT (uic)))
253 if (IC_LEFT (uic)->key == sym->key)
255 markAlive(ic, uic, sym->key);
259 if (IS_ITEMP (IC_RIGHT (uic)))
260 if (IC_RIGHT (uic)->key == sym->key)
262 markAlive (ic, uic, sym->key);
266 if (IS_ITEMP (IC_RESULT (uic)))
267 if (IC_RESULT (uic)->key == sym->key)
269 if (POINTER_SET (uic))
271 markAlive (ic, uic, sym->key);
280 /* check all successors */
283 succ = setFirstItem (ebp->succList);
284 for (; succ; succ = setNextItem (ebp->succList))
286 retval += findNextUseSym (succ, succ->sch, sym);
291 if (ic) markAlive (ic, ebp->ech, sym->key);
298 /*-----------------------------------------------------------------*/
299 /* findNextUse - finds the next use of the operand and marks it */
300 /* alive in between */
301 /*-----------------------------------------------------------------*/
303 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
306 OP_SYMBOL (op)->isptr = 1;
308 OP_SYMBOL (op)->key = op->key;
310 return findNextUseSym (ebp, ic, OP_SYMBOL(op));
313 /*-----------------------------------------------------------------*/
314 /* unvisitBlocks - clears visited in all blocks */
315 /*-----------------------------------------------------------------*/
316 void unvisitBlocks (eBBlock ** ebbs, int count)
320 for (i = 0; i < count; i++)
321 ebbs[i]->visited = 0;
324 /*------------------------------------------------------------------*/
325 /* findRecursiveSucc - build a bit vector of recursive successors */
326 /*------------------------------------------------------------------*/
327 DEFSETFUNC (findRecursiveSucc)
330 V_ARG (bitVect *, succVect);
336 bitVectSetBit (succVect, ebp->bbnum);
337 applyToSet (ebp->succList, findRecursiveSucc, succVect);
342 /*------------------------------------------------------------------*/
343 /* findRecursivePred - build a bit vector of recursive predecessors */
344 /*------------------------------------------------------------------*/
345 DEFSETFUNC (findRecursivePred)
348 V_ARG (bitVect *, predVect);
354 bitVectSetBit (predVect, ebp->bbnum);
355 applyToSet (ebp->predList, findRecursivePred, predVect);
360 /*------------------------------------------------------------------*/
361 /* findPrevUse - handle degenerate case of a symbol used prior to */
362 /* findNextUse() marking any definition. */
363 /*------------------------------------------------------------------*/
365 findPrevUse (eBBlock *ebp, iCode *ic, operand *op, eBBlock **ebbs, int count)
372 /* If liveness is already known, then a previous call to findNextUse() */
373 /* has already taken care of everything. */
374 if (ic && bitVectBitValue(ic->rlive, op->key))
379 /* We are at the start of a block. If the operand is alive at the */
380 /* end of all predecessors, then a previous call to findNextUse() */
381 /* has already taken care of everything. */
383 pred = setFirstItem (ebp->predList);
384 for (; pred; pred = setNextItem (ebp->predList))
385 if (pred->ech && !bitVectBitValue(pred->ech->rlive, op->key))
393 OP_SYMBOL (op)->isptr = 1;
395 OP_SYMBOL (op)->key = op->key;
397 /* Otherwise, it appears that this symbol was used prior to definition. */
398 /* Just fix the live range; we'll deal with a diagnostic message elsewhere. */
399 /* If the symbol use was in a loop, we need to extend the live range to the */
400 /* outermost loop. */
401 unvisitBlocks (ebbs, count);
402 succVect = newBitVect (count);
403 applyToSet (ebp->succList, findRecursiveSucc, succVect);
404 unvisitBlocks (ebbs, count);
405 predVect = newBitVect (count);
406 applyToSet (ebp->predList, findRecursivePred, predVect);
408 /* Blocks that are both recursively predecessors and successors are in */
409 /* a loop with the current iCode. Mark the operand as alive in them. */
410 for (i = 0; i < count; i++)
412 if (bitVectBitValue(succVect, i) && bitVectBitValue(predVect, i))
413 markAlive (ebbs[i]->sch, ebbs[i]->ech, op->key);
416 freeBitVect (succVect);
417 freeBitVect (predVect);
420 /*-----------------------------------------------------------------*/
421 /* incUsed - increment a symbol's usage count */
422 /*-----------------------------------------------------------------*/
424 incUsed (iCode *ic, operand *op)
427 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
429 OP_SYMBOL (op)->used += 1;
432 /*-----------------------------------------------------------------*/
433 /* rliveClear - clears the rlive bitVectors */
434 /*-----------------------------------------------------------------*/
436 rliveClear (eBBlock ** ebbs, int count)
440 /* for all blocks do */
441 for (i = 0; i < count; i++)
445 /* for all instructions in this block do */
446 for (ic = ebbs[i]->sch; ic; ic = ic->next)
448 freeBitVect (ic->rlive);
454 /*-----------------------------------------------------------------*/
455 /* rlivePoint - for each point compute the ranges that are alive */
456 /*-----------------------------------------------------------------*/
458 rlivePoint (eBBlock ** ebbs, int count)
464 /* for all blocks do */
465 for (i = 0; i < count; i++)
469 /* for all instructions in this block do */
470 for (ic = ebbs[i]->sch; ic; ic = ic->next)
474 ic->rlive = newBitVect (operandKey);
479 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
481 incUsed (ic, IC_JTCOND(ic));
483 if (!IS_ITEMP(IC_JTCOND(ic)))
486 findPrevUse (ebbs[i], ic->prev, IC_JTCOND(ic), ebbs, count);
487 unvisitBlocks(ebbs, count);
488 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
489 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
494 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
496 incUsed (ic, IC_COND(ic));
498 if (!IS_ITEMP(IC_COND(ic)))
501 findPrevUse (ebbs[i], ic->prev, IC_COND(ic), ebbs, count);
502 unvisitBlocks (ebbs, count);
503 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
504 findNextUse (ebbs[i], ic->next, IC_COND(ic));
509 if (IS_SYMOP(IC_LEFT(ic)))
511 incUsed (ic, IC_LEFT(ic));
512 if (IS_ITEMP(IC_LEFT(ic)))
515 findPrevUse (ebbs[i], ic->prev, IC_LEFT(ic), ebbs, count);
516 unvisitBlocks(ebbs, count);
517 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
518 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
520 /* if this is a send extend the LR to the call */
524 for (lic = ic; lic; lic = lic->next)
526 if (lic->op == CALL || lic->op == PCALL)
528 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
534 // fprintf(stderr, "%s:%d IS_SYMOP left\t", __FILE__, __LINE__);printOperand(IC_LEFT(ic), stderr);
535 // fprintf(stderr, "\n");
538 if (IS_SYMOP(IC_RIGHT(ic)))
540 incUsed (ic, IC_RIGHT(ic));
541 if (IS_ITEMP(IC_RIGHT(ic)))
543 findPrevUse (ebbs[i], ic->prev, IC_RIGHT(ic), ebbs, count);
544 unvisitBlocks(ebbs, count);
545 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
546 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
548 // fprintf(stderr, "%s:%d IS_SYMOP right\t", __FILE__, __LINE__);printOperand(IC_RIGHT(ic), stderr);
549 // fprintf(stderr, "\n");
552 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
553 incUsed (ic, IC_RESULT(ic));
555 if (IS_ITEMP(IC_RESULT(ic)))
559 findPrevUse (ebbs[i], ic->prev, IC_RESULT(ic), ebbs, count);
561 unvisitBlocks(ebbs, count);
562 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
563 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
566 if (!POINTER_SET(ic) && IC_RESULT(ic))
567 ic->defKey = IC_RESULT(ic)->key;
571 /* check all symbols that are alive in the last instruction */
572 /* but are not alive in all successors */
574 succ = setFirstItem (ebbs[i]->succList);
578 alive = succ->sch->rlive;
579 while ((succ = setNextItem (ebbs[i]->succList)))
582 alive = bitVectIntersect (alive, succ->sch->rlive);
586 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
590 for (key = 1; key < alive->size; key++)
592 if (!bitVectBitValue (alive, key))
595 unvisitBlocks(ebbs, count);
596 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
602 /*-----------------------------------------------------------------*/
603 /* computeClash - find out which live ranges collide with others */
604 /*-----------------------------------------------------------------*/
606 computeClash (eBBlock ** ebbs, int count)
610 /* for all blocks do */
611 for (i = 0; i < count; i++)
615 /* for every iCode do */
616 for (ic = ebbs[i]->sch; ic; ic = ic->next)
621 /* for all iTemps alive at this iCode */
622 for (key1 = 1; key1 < ic->rlive->size; key1++)
624 if (!bitVectBitValue(ic->rlive, key1))
627 sym1 = hTabItemWithKey(liveRanges, key1);
632 /* for all other iTemps alive at this iCode */
633 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
635 if (!bitVectBitValue(ic->rlive, key2))
638 sym2 = hTabItemWithKey(liveRanges, key2);
643 /* if the result and left or right is an iTemp */
644 /* than possibly the iTemps do not clash */
645 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
646 IS_ITEMP(IC_RESULT(ic)) &&
647 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
649 if (OP_SYMBOL(IC_RESULT(ic))->key == key1
650 && sym1->liveFrom == ic->seq
651 && sym2->liveTo == ic->seq)
653 if (IS_SYMOP(IC_LEFT(ic)))
654 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
656 if (IS_SYMOP(IC_RIGHT(ic)))
657 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
661 if (OP_SYMBOL(IC_RESULT(ic))->key == key2
662 && sym2->liveFrom == ic->seq
663 && sym1->liveTo == ic->seq)
665 if (IS_SYMOP(IC_LEFT(ic)))
666 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
668 if (IS_SYMOP(IC_RIGHT(ic)))
669 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
674 /* the iTemps do clash. set the bits in clashes */
675 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
676 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
678 /* check if they share the same spill location */
679 /* what is this good for? */
680 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
681 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
683 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
684 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
685 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
686 else SYM_SPIL_LOC(sym1)=NULL;
694 /*-----------------------------------------------------------------*/
695 /* allDefsOutOfRange - all definitions are out of a range */
696 /*-----------------------------------------------------------------*/
698 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
705 for (i = 0; i < defs->size; i++)
709 if (bitVectBitValue (defs, i) &&
710 (ic = hTabItemWithKey (iCodehTab, i)) &&
711 (ic->seq >= fseq && ic->seq <= toseq))
719 /*-----------------------------------------------------------------*/
720 /* notUsedInBlock - not used in this block */
721 /*-----------------------------------------------------------------*/
723 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
725 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
726 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
727 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
730 /*-----------------------------------------------------------------*/
731 /* adjustIChain - correct the sch and ech pointers */
732 /*-----------------------------------------------------------------*/
734 adjustIChain (eBBlock ** ebbs, int count)
738 for (i = 0; i < count; i++)
747 /* is there any code for this eBBlock? (e.g. ROM assignment) */
761 /*-----------------------------------------------------------------*/
762 /* computeLiveRanges - computes the live ranges for variables */
763 /*-----------------------------------------------------------------*/
765 computeLiveRanges (eBBlock ** ebbs, int count)
767 /* first look through all blocks and adjust the
768 sch and ech pointers */
769 adjustIChain (ebbs, count);
771 /* sequence the code the live ranges are computed
772 in terms of this sequence additionally the
773 routine will also create a hashtable of instructions */
775 setToNull ((void *) &iCodehTab);
776 iCodehTab = newHashTable (iCodeKey);
777 hashiCodeKeys (ebbs, count);
778 setToNull ((void *) &iCodeSeqhTab);
779 iCodeSeqhTab = newHashTable (iCodeKey);
780 sequenceiCode (ebbs, count);
782 /* mark the ranges live for each point */
783 setToNull ((void *) &liveRanges);
784 rlivePoint (ebbs, count);
786 /* mark the from & to live ranges for variables used */
787 markLiveRanges (ebbs, count);
789 /* compute which overlaps with what */
790 computeClash(ebbs, count);
793 /*-----------------------------------------------------------------*/
794 /* recomputeLiveRanges - recomputes the live ranges for variables */
795 /*-----------------------------------------------------------------*/
797 recomputeLiveRanges (eBBlock ** ebbs, int count)
802 /* clear all rlive bitVectors */
803 rliveClear (ebbs, count);
805 sym = hTabFirstItem (liveRanges, &key);
812 freeBitVect (sym->clashes);
814 } while ( (sym = hTabNextItem (liveRanges, &key)));
817 /* do the LR computation again */
818 computeLiveRanges (ebbs, count);