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);
536 if (IS_SYMOP(IC_RIGHT(ic)))
538 incUsed (ic, IC_RIGHT(ic));
539 if (IS_ITEMP(IC_RIGHT(ic)))
541 findPrevUse (ebbs[i], ic->prev, IC_RIGHT(ic), ebbs, count);
542 unvisitBlocks(ebbs, count);
543 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
544 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
548 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
549 incUsed (ic, IC_RESULT(ic));
551 if (IS_ITEMP(IC_RESULT(ic)))
555 findPrevUse (ebbs[i], ic->prev, IC_RESULT(ic), ebbs, count);
557 unvisitBlocks(ebbs, count);
558 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
559 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
562 if (!POINTER_SET(ic) && IC_RESULT(ic))
563 ic->defKey = IC_RESULT(ic)->key;
567 /* check all symbols that are alive in the last instruction */
568 /* but are not alive in all successors */
570 succ = setFirstItem (ebbs[i]->succList);
574 alive = succ->sch->rlive;
575 while ((succ = setNextItem (ebbs[i]->succList)))
578 alive = bitVectIntersect (alive, succ->sch->rlive);
582 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
586 for (key = 1; key < alive->size; key++)
588 if (!bitVectBitValue (alive, key))
591 unvisitBlocks(ebbs, count);
592 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
598 /*-----------------------------------------------------------------*/
599 /* computeClash - find out which live ranges collide with others */
600 /*-----------------------------------------------------------------*/
602 computeClash (eBBlock ** ebbs, int count)
606 /* for all blocks do */
607 for (i = 0; i < count; i++)
611 /* for every iCode do */
612 for (ic = ebbs[i]->sch; ic; ic = ic->next)
617 /* for all iTemps alive at this iCode */
618 for (key1 = 1; key1 < ic->rlive->size; key1++)
620 if (!bitVectBitValue(ic->rlive, key1))
623 sym1 = hTabItemWithKey(liveRanges, key1);
628 /* for all other iTemps alive at this iCode */
629 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
631 if (!bitVectBitValue(ic->rlive, key2))
634 sym2 = hTabItemWithKey(liveRanges, key2);
639 /* if the result and left or right is an iTemp */
640 /* than possibly the iTemps do not clash */
641 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
642 IS_ITEMP(IC_RESULT(ic)) &&
643 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
645 if (OP_SYMBOL(IC_RESULT(ic))->key == key1
646 && sym1->liveFrom == ic->seq
647 && sym2->liveTo == ic->seq)
649 if (IS_SYMOP(IC_LEFT(ic)))
650 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
652 if (IS_SYMOP(IC_RIGHT(ic)))
653 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
657 if (OP_SYMBOL(IC_RESULT(ic))->key == key2
658 && sym2->liveFrom == ic->seq
659 && sym1->liveTo == ic->seq)
661 if (IS_SYMOP(IC_LEFT(ic)))
662 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
664 if (IS_SYMOP(IC_RIGHT(ic)))
665 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
670 /* the iTemps do clash. set the bits in clashes */
671 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
672 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
674 /* check if they share the same spill location */
675 /* what is this good for? */
676 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
677 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
679 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
680 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
681 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
682 else SYM_SPIL_LOC(sym1)=NULL;
690 /*-----------------------------------------------------------------*/
691 /* allDefsOutOfRange - all definitions are out of a range */
692 /*-----------------------------------------------------------------*/
694 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
701 for (i = 0; i < defs->size; i++)
705 if (bitVectBitValue (defs, i) &&
706 (ic = hTabItemWithKey (iCodehTab, i)) &&
707 (ic->seq >= fseq && ic->seq <= toseq))
715 /*-----------------------------------------------------------------*/
716 /* notUsedInBlock - not used in this block */
717 /*-----------------------------------------------------------------*/
719 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
721 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
722 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
723 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
726 /*-----------------------------------------------------------------*/
727 /* adjustIChain - correct the sch and ech pointers */
728 /*-----------------------------------------------------------------*/
730 adjustIChain (eBBlock ** ebbs, int count)
734 for (i = 0; i < count; i++)
743 /* is there any code for this eBBlock? (e.g. ROM assignment) */
757 /*-----------------------------------------------------------------*/
758 /* computeLiveRanges - computes the live ranges for variables */
759 /*-----------------------------------------------------------------*/
761 computeLiveRanges (eBBlock ** ebbs, int count)
763 /* first look through all blocks and adjust the
764 sch and ech pointers */
765 adjustIChain (ebbs, count);
767 /* sequence the code the live ranges are computed
768 in terms of this sequence additionally the
769 routine will also create a hashtable of instructions */
771 setToNull ((void *) &iCodehTab);
772 iCodehTab = newHashTable (iCodeKey);
773 hashiCodeKeys (ebbs, count);
774 setToNull ((void *) &iCodeSeqhTab);
775 iCodeSeqhTab = newHashTable (iCodeKey);
776 sequenceiCode (ebbs, count);
778 /* mark the ranges live for each point */
779 setToNull ((void *) &liveRanges);
780 rlivePoint (ebbs, count);
782 /* mark the from & to live ranges for variables used */
783 markLiveRanges (ebbs, count);
785 /* compute which overlaps with what */
786 computeClash(ebbs, count);
789 /*-----------------------------------------------------------------*/
790 /* recomputeLiveRanges - recomputes the live ranges for variables */
791 /*-----------------------------------------------------------------*/
793 recomputeLiveRanges (eBBlock ** ebbs, int count)
798 /* clear all rlive bitVectors */
799 rliveClear (ebbs, count);
801 sym = hTabFirstItem (liveRanges, &key);
808 freeBitVect (sym->clashes);
810 } while ( (sym = hTabNextItem (liveRanges, &key)));
813 /* do the LR computation again */
814 computeLiveRanges (ebbs, count);