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 /*-----------------------------------------------------------------*/
79 setFromRange (operand * op, int from)
81 /* only for compiler defined temporaries */
85 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
88 OP_SYMBOL (op)->isptr = 1;
90 if (!OP_LIVEFROM (op) ||
91 OP_LIVEFROM (op) > from)
92 OP_LIVEFROM (op) = from;
96 /*-----------------------------------------------------------------*/
97 /* setToRange - set the range to for an operand */
98 /*-----------------------------------------------------------------*/
100 setToRange (operand * op, int to, bool check)
102 /* only for compiler defined temps */
106 OP_SYMBOL (op)->key = op->key;
107 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
110 OP_SYMBOL (op)->isptr = 1;
120 /*-----------------------------------------------------------------*/
121 /* setFromRange - sets the from range of a given operand */
122 /*-----------------------------------------------------------------*/
124 setLiveFrom (symbol * sym, int from)
126 if (!sym->liveFrom || sym->liveFrom > from)
127 sym->liveFrom = from;
130 /*-----------------------------------------------------------------*/
131 /* setToRange - set the range to for an operand */
132 /*-----------------------------------------------------------------*/
134 setLiveTo (symbol * sym, int to)
136 if (!sym->liveTo || sym->liveTo < to)
140 /*-----------------------------------------------------------------*/
141 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
142 /*-----------------------------------------------------------------*/
144 markLiveRanges (eBBlock ** ebbs, int count)
149 for (i = 0; i < count; i++)
153 for (ic = ebbs[i]->sch; ic; ic = ic->next)
155 if (ic->op == CALL || ic->op == PCALL)
156 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
157 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
159 /* for all iTemps alive at this iCode */
160 for (key = 1; key < ic->rlive->size; key++)
162 if (!bitVectBitValue(ic->rlive, key))
165 sym = hTabItemWithKey(liveRanges, key);
166 setLiveTo(sym, ic->seq);
167 setLiveFrom(sym, ic->seq);
174 /*-----------------------------------------------------------------*/
175 /* markAlive - marks the operand as alive between sic and eic */
176 /*-----------------------------------------------------------------*/
178 markAlive (iCode * sic, iCode * eic, int key)
182 for (dic = sic; dic != eic->next; dic = dic->next)
184 dic->rlive = bitVectSetBit (dic->rlive, key);
188 /*-----------------------------------------------------------------*/
189 /* findNextUseSym - finds the next use of the symbol and marks it */
190 /* alive in between */
191 /*-----------------------------------------------------------------*/
193 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
199 hTabAddItemIfNotP (&liveRanges, sym->key, sym);
202 goto check_successors;
204 /* if we check a complete block and the symbol */
205 /* is alive at the beginning of the block */
206 /* and not defined in the first instructions */
207 /* then a next use exists (return 1) */
208 if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
210 /* check if the first instruction is a def of this op */
211 if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
214 if (IS_ITEMP(IC_RESULT(ic)))
215 if (IC_RESULT(ic)->key == sym->key)
227 /* for all remaining instructions in current block */
228 for (uic = ic; uic; uic = uic->next)
234 if (uic->op == JUMPTABLE)
236 if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
238 markAlive(ic, uic, sym->key);
246 if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
248 markAlive(ic, uic, sym->key);
254 if (IS_ITEMP (IC_LEFT (uic)))
255 if (IC_LEFT (uic)->key == sym->key)
257 markAlive(ic, uic, sym->key);
261 if (IS_ITEMP (IC_RIGHT (uic)))
262 if (IC_RIGHT (uic)->key == sym->key)
264 markAlive (ic, uic, sym->key);
268 if (IS_ITEMP (IC_RESULT (uic)))
269 if (IC_RESULT (uic)->key == sym->key)
271 if (POINTER_SET (uic))
273 markAlive (ic, uic, sym->key);
282 /* check all successors */
285 succ = setFirstItem (ebp->succList);
286 for (; succ; succ = setNextItem (ebp->succList))
288 retval += findNextUseSym (succ, succ->sch, sym);
293 if (ic) markAlive (ic, ebp->ech, sym->key);
300 /*-----------------------------------------------------------------*/
301 /* findNextUse - finds the next use of the operand and marks it */
302 /* alive in between */
303 /*-----------------------------------------------------------------*/
305 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
308 OP_SYMBOL (op)->isptr = 1;
310 OP_SYMBOL (op)->key = op->key;
312 return findNextUseSym (ebp, ic, OP_SYMBOL(op));
315 /*-----------------------------------------------------------------*/
316 /* unvisitBlocks - clears visited in all blocks */
317 /*-----------------------------------------------------------------*/
319 unvisitBlocks (eBBlock ** ebbs, int count)
323 for (i = 0; i < count; i++)
324 ebbs[i]->visited = 0;
327 /*------------------------------------------------------------------*/
328 /* markWholeLoop - mark the symbol 'key' alive in all blocks */
329 /* included by the outermost loop */
330 /*------------------------------------------------------------------*/
332 markWholeLoop (eBBlock *ebp, int key)
336 /* avoid endless loops */
339 /* recurse through all predecessors */
340 for (ebpi = setFirstItem (ebp->predList);
342 ebpi = setNextItem (ebp->predList))
346 /* is the predecessor still in the loop? */
347 if (ebpi->depth == 0)
349 markWholeLoop (ebpi, key);
352 /* recurse through all successors */
353 for (ebpi = setFirstItem (ebp->succList);
355 ebpi = setNextItem (ebp->succList))
359 if (ebpi->depth == 0)
361 markWholeLoop (ebpi, key);
364 markAlive (ebp->sch, ebp->ech, key);
367 /*------------------------------------------------------------------*/
368 /* findPrevUseSym - search for a previous definition of a symbol in */
369 /* - the previous icodes */
370 /* - all branches of predecessors */
371 /*------------------------------------------------------------------*/
373 findPrevUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
380 /* already visited: this branch must have been succesfull, */
381 /* because otherwise the search would have been aborted. */
386 /* search backward in the current block */
387 for (uic = ic; uic; uic = uic->prev)
389 if (!POINTER_SET (uic) && IS_ITEMP (IC_RESULT (uic)))
391 if (IC_RESULT (uic)->key == sym->key)
393 /* Ok, found a definition */
399 /* There's no definition in this bblock, */
400 /* let's have a look at all predecessors. */
401 pred = setFirstItem (ebp->predList);
404 /* no more predecessors and nothing found yet :-( */
407 for (; pred; pred = setNextItem (ebp->predList))
409 /* recurse into all predecessors */
410 if (!findPrevUseSym (pred, pred->ech, sym))
412 /* found nothing: abort */
417 /* Success! Went through all branches with no abort: */
418 /* all branches end with a definition */
422 /*------------------------------------------------------------------*/
423 /* findPrevUse - search for a previous definition of an operand */
424 /* If there's no definition let's: */
425 /* - emit a warning */
426 /* - fix the life range, if the symbol is used in */
428 /*------------------------------------------------------------------*/
430 findPrevUse (eBBlock *ebp, iCode *ic, operand *op,
431 eBBlock ** ebbs, int count,
434 unvisitBlocks (ebbs, count);
437 OP_SYMBOL (op)->isptr = 1;
438 OP_SYMBOL (op)->key = op->key;
440 /* There must be a definition in each branch of predecessors */
441 if (!findPrevUseSym (ebp, ic->prev, OP_SYMBOL(op)))
443 /* computeLiveRanges() is called twice */
446 werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
447 OP_SYMBOL (op)->prereqv);
448 OP_SYMBOL (op)->prereqv->reqv = NULL;
449 OP_SYMBOL (op)->prereqv->allocreq = 1;
451 /* is this block part of a loop? */
454 /* extend the life range to the outermost loop */
455 unvisitBlocks(ebbs, count);
456 markWholeLoop (ebp, op->key);
461 /*-----------------------------------------------------------------*/
462 /* incUsed - increment a symbol's usage count */
463 /*-----------------------------------------------------------------*/
465 incUsed (iCode *ic, operand *op)
468 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
470 OP_SYMBOL (op)->used += 1;
473 /*-----------------------------------------------------------------*/
474 /* rliveClear - clears the rlive bitVectors */
475 /*-----------------------------------------------------------------*/
477 rliveClear (eBBlock ** ebbs, int count)
481 /* for all blocks do */
482 for (i = 0; i < count; i++)
486 /* for all instructions in this block do */
487 for (ic = ebbs[i]->sch; ic; ic = ic->next)
489 freeBitVect (ic->rlive);
495 /*-----------------------------------------------------------------*/
496 /* rlivePoint - for each point compute the ranges that are alive */
497 /*-----------------------------------------------------------------*/
499 rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
505 /* for all blocks do */
506 for (i = 0; i < count; i++)
510 /* for all instructions in this block do */
511 for (ic = ebbs[i]->sch; ic; ic = ic->next)
515 ic->rlive = newBitVect (operandKey);
520 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
522 incUsed (ic, IC_JTCOND(ic));
524 if (!IS_ITEMP(IC_JTCOND(ic)))
527 findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings);
528 unvisitBlocks(ebbs, count);
529 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
530 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
535 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
537 incUsed (ic, IC_COND(ic));
539 if (!IS_ITEMP(IC_COND(ic)))
542 findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings);
543 unvisitBlocks (ebbs, count);
544 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
545 findNextUse (ebbs[i], ic->next, IC_COND(ic));
550 if (IS_SYMOP(IC_LEFT(ic)))
552 incUsed (ic, IC_LEFT(ic));
553 if (IS_ITEMP(IC_LEFT(ic)))
555 findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings);
556 unvisitBlocks(ebbs, count);
557 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
558 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
560 /* if this is a send extend the LR to the call */
564 for (lic = ic; lic; lic = lic->next)
566 if (lic->op == CALL || lic->op == PCALL)
568 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
576 if (IS_SYMOP(IC_RIGHT(ic)))
578 incUsed (ic, IC_RIGHT(ic));
579 if (IS_ITEMP(IC_RIGHT(ic)))
581 findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings);
582 unvisitBlocks(ebbs, count);
583 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
584 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
588 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
589 incUsed (ic, IC_RESULT(ic));
591 if (IS_ITEMP(IC_RESULT(ic)))
595 findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings);
597 unvisitBlocks(ebbs, count);
598 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
599 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
602 if (!POINTER_SET(ic) && IC_RESULT(ic))
603 ic->defKey = IC_RESULT(ic)->key;
607 /* check all symbols that are alive in the last instruction */
608 /* but are not alive in all successors */
610 succ = setFirstItem (ebbs[i]->succList);
614 alive = succ->sch->rlive;
615 while ((succ = setNextItem (ebbs[i]->succList)))
618 alive = bitVectIntersect (alive, succ->sch->rlive);
622 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
626 for (key = 1; key < alive->size; key++)
628 if (!bitVectBitValue (alive, key))
631 unvisitBlocks(ebbs, count);
632 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
638 /*-----------------------------------------------------------------*/
639 /* computeClash - find out which live ranges collide with others */
640 /*-----------------------------------------------------------------*/
642 computeClash (eBBlock ** ebbs, int count)
646 /* for all blocks do */
647 for (i = 0; i < count; i++)
651 /* for every iCode do */
652 for (ic = ebbs[i]->sch; ic; ic = ic->next)
657 /* for all iTemps alive at this iCode */
658 for (key1 = 1; key1 < ic->rlive->size; key1++)
660 if (!bitVectBitValue(ic->rlive, key1))
663 sym1 = hTabItemWithKey(liveRanges, key1);
668 /* for all other iTemps alive at this iCode */
669 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
671 if (!bitVectBitValue(ic->rlive, key2))
674 sym2 = hTabItemWithKey(liveRanges, key2);
679 /* if the result and left or right is an iTemp */
680 /* than possibly the iTemps do not clash */
681 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
682 IS_ITEMP(IC_RESULT(ic)) &&
683 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
685 if (OP_SYMBOL(IC_RESULT(ic))->key == key1
686 && sym1->liveFrom == ic->seq
687 && sym2->liveTo == ic->seq)
689 if (IS_SYMOP(IC_LEFT(ic)))
690 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
692 if (IS_SYMOP(IC_RIGHT(ic)))
693 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
697 if (OP_SYMBOL(IC_RESULT(ic))->key == key2
698 && sym2->liveFrom == ic->seq
699 && sym1->liveTo == ic->seq)
701 if (IS_SYMOP(IC_LEFT(ic)))
702 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
704 if (IS_SYMOP(IC_RIGHT(ic)))
705 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
710 /* the iTemps do clash. set the bits in clashes */
711 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
712 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
714 /* check if they share the same spill location */
715 /* what is this good for? */
716 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
717 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
719 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
720 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
721 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
722 else SYM_SPIL_LOC(sym1)=NULL;
730 /*-----------------------------------------------------------------*/
731 /* allDefsOutOfRange - all definitions are out of a range */
732 /*-----------------------------------------------------------------*/
734 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
741 for (i = 0; i < defs->size; i++)
745 if (bitVectBitValue (defs, i) &&
746 (ic = hTabItemWithKey (iCodehTab, i)) &&
747 (ic->seq >= fseq && ic->seq <= toseq))
755 /*-----------------------------------------------------------------*/
756 /* notUsedInBlock - not used in this block */
757 /*-----------------------------------------------------------------*/
759 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
761 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
762 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
763 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
766 /*-----------------------------------------------------------------*/
767 /* adjustIChain - correct the sch and ech pointers */
768 /*-----------------------------------------------------------------*/
770 adjustIChain (eBBlock ** ebbs, int count)
774 for (i = 0; i < count; i++)
783 /* is there any code for this eBBlock? (e.g. ROM assignment) */
797 /*-----------------------------------------------------------------*/
798 /* computeLiveRanges - computes the live ranges for variables */
799 /*-----------------------------------------------------------------*/
801 computeLiveRanges (eBBlock ** ebbs, int count, bool emitWarnings)
803 /* first look through all blocks and adjust the
804 sch and ech pointers */
805 adjustIChain (ebbs, count);
807 /* sequence the code the live ranges are computed
808 in terms of this sequence additionally the
809 routine will also create a hashtable of instructions */
811 setToNull ((void *) &iCodehTab);
812 iCodehTab = newHashTable (iCodeKey);
813 hashiCodeKeys (ebbs, count);
814 setToNull ((void *) &iCodeSeqhTab);
815 iCodeSeqhTab = newHashTable (iCodeKey);
816 sequenceiCode (ebbs, count);
818 /* mark the ranges live for each point */
819 setToNull ((void *) &liveRanges);
820 rlivePoint (ebbs, count, emitWarnings);
822 /* mark the from & to live ranges for variables used */
823 markLiveRanges (ebbs, count);
825 /* compute which overlaps with what */
826 computeClash(ebbs, count);
829 /*-----------------------------------------------------------------*/
830 /* recomputeLiveRanges - recomputes the live ranges for variables */
831 /*-----------------------------------------------------------------*/
833 recomputeLiveRanges (eBBlock ** ebbs, int count)
838 /* clear all rlive bitVectors */
839 rliveClear (ebbs, count);
841 sym = hTabFirstItem (liveRanges, &key);
848 freeBitVect (sym->clashes);
850 } while ( (sym = hTabNextItem (liveRanges, &key)));
853 /* do the LR computation again */
854 computeLiveRanges (ebbs, count, FALSE);
857 /*-----------------------------------------------------------------*/
858 /* dump icode->rlive in all blocks */
859 /*-----------------------------------------------------------------*/
862 dumpIcRlive (eBBlock ** ebbs, int count)
867 /* for all blocks do */
868 for (i = 0; i < count; i++)
870 printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name);
871 /* for all instructions in this block do */
872 for (ic = ebbs[i]->sch; ic; ic = ic->next)
874 printf ("\tic->key %d\n", ic->key);
878 /* for all live Ranges alive at this point */
879 for (j = 1; j < ic->rlive->size; j++)
883 if (!bitVectBitValue (ic->rlive, j))
886 /* find the live range we are interested in */
887 if ((sym = hTabItemWithKey (liveRanges, j)))
888 printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name);