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 */
445 werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
446 OP_SYMBOL (op)->prereqv);
447 /* is this block part of a loop? */
450 /* extend the life range to the outermost loop */
451 unvisitBlocks(ebbs, count);
452 markWholeLoop (ebp, op->key);
457 /*-----------------------------------------------------------------*/
458 /* incUsed - increment a symbol's usage count */
459 /*-----------------------------------------------------------------*/
461 incUsed (iCode *ic, operand *op)
464 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
466 OP_SYMBOL (op)->used += 1;
469 /*-----------------------------------------------------------------*/
470 /* rliveClear - clears the rlive bitVectors */
471 /*-----------------------------------------------------------------*/
473 rliveClear (eBBlock ** ebbs, int count)
477 /* for all blocks do */
478 for (i = 0; i < count; i++)
482 /* for all instructions in this block do */
483 for (ic = ebbs[i]->sch; ic; ic = ic->next)
485 freeBitVect (ic->rlive);
491 /*-----------------------------------------------------------------*/
492 /* rlivePoint - for each point compute the ranges that are alive */
493 /*-----------------------------------------------------------------*/
495 rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
501 /* for all blocks do */
502 for (i = 0; i < count; i++)
506 /* for all instructions in this block do */
507 for (ic = ebbs[i]->sch; ic; ic = ic->next)
511 ic->rlive = newBitVect (operandKey);
516 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
518 incUsed (ic, IC_JTCOND(ic));
520 if (!IS_ITEMP(IC_JTCOND(ic)))
523 findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings);
524 unvisitBlocks(ebbs, count);
525 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
526 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
531 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
533 incUsed (ic, IC_COND(ic));
535 if (!IS_ITEMP(IC_COND(ic)))
538 findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings);
539 unvisitBlocks (ebbs, count);
540 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
541 findNextUse (ebbs[i], ic->next, IC_COND(ic));
546 if (IS_SYMOP(IC_LEFT(ic)))
548 incUsed (ic, IC_LEFT(ic));
549 if (IS_ITEMP(IC_LEFT(ic)))
551 findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings);
552 unvisitBlocks(ebbs, count);
553 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
554 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
556 /* if this is a send extend the LR to the call */
560 for (lic = ic; lic; lic = lic->next)
562 if (lic->op == CALL || lic->op == PCALL)
564 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
572 if (IS_SYMOP(IC_RIGHT(ic)))
574 incUsed (ic, IC_RIGHT(ic));
575 if (IS_ITEMP(IC_RIGHT(ic)))
577 findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings);
578 unvisitBlocks(ebbs, count);
579 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
580 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
584 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
585 incUsed (ic, IC_RESULT(ic));
587 if (IS_ITEMP(IC_RESULT(ic)))
591 findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings);
593 unvisitBlocks(ebbs, count);
594 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
595 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
598 if (!POINTER_SET(ic) && IC_RESULT(ic))
599 ic->defKey = IC_RESULT(ic)->key;
603 /* check all symbols that are alive in the last instruction */
604 /* but are not alive in all successors */
606 succ = setFirstItem (ebbs[i]->succList);
610 alive = succ->sch->rlive;
611 while ((succ = setNextItem (ebbs[i]->succList)))
614 alive = bitVectIntersect (alive, succ->sch->rlive);
618 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
622 for (key = 1; key < alive->size; key++)
624 if (!bitVectBitValue (alive, key))
627 unvisitBlocks(ebbs, count);
628 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
634 /*-----------------------------------------------------------------*/
635 /* computeClash - find out which live ranges collide with others */
636 /*-----------------------------------------------------------------*/
638 computeClash (eBBlock ** ebbs, int count)
642 /* for all blocks do */
643 for (i = 0; i < count; i++)
647 /* for every iCode do */
648 for (ic = ebbs[i]->sch; ic; ic = ic->next)
653 /* for all iTemps alive at this iCode */
654 for (key1 = 1; key1 < ic->rlive->size; key1++)
656 if (!bitVectBitValue(ic->rlive, key1))
659 sym1 = hTabItemWithKey(liveRanges, key1);
664 /* for all other iTemps alive at this iCode */
665 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
667 if (!bitVectBitValue(ic->rlive, key2))
670 sym2 = hTabItemWithKey(liveRanges, key2);
675 /* if the result and left or right is an iTemp */
676 /* than possibly the iTemps do not clash */
677 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
678 IS_ITEMP(IC_RESULT(ic)) &&
679 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
681 if (OP_SYMBOL(IC_RESULT(ic))->key == key1
682 && sym1->liveFrom == ic->seq
683 && sym2->liveTo == ic->seq)
685 if (IS_SYMOP(IC_LEFT(ic)))
686 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
688 if (IS_SYMOP(IC_RIGHT(ic)))
689 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
693 if (OP_SYMBOL(IC_RESULT(ic))->key == key2
694 && sym2->liveFrom == ic->seq
695 && sym1->liveTo == ic->seq)
697 if (IS_SYMOP(IC_LEFT(ic)))
698 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
700 if (IS_SYMOP(IC_RIGHT(ic)))
701 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
706 /* the iTemps do clash. set the bits in clashes */
707 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
708 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
710 /* check if they share the same spill location */
711 /* what is this good for? */
712 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
713 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
715 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
716 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
717 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
718 else SYM_SPIL_LOC(sym1)=NULL;
726 /*-----------------------------------------------------------------*/
727 /* allDefsOutOfRange - all definitions are out of a range */
728 /*-----------------------------------------------------------------*/
730 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
737 for (i = 0; i < defs->size; i++)
741 if (bitVectBitValue (defs, i) &&
742 (ic = hTabItemWithKey (iCodehTab, i)) &&
743 (ic->seq >= fseq && ic->seq <= toseq))
751 /*-----------------------------------------------------------------*/
752 /* notUsedInBlock - not used in this block */
753 /*-----------------------------------------------------------------*/
755 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
757 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
758 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
759 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
762 /*-----------------------------------------------------------------*/
763 /* adjustIChain - correct the sch and ech pointers */
764 /*-----------------------------------------------------------------*/
766 adjustIChain (eBBlock ** ebbs, int count)
770 for (i = 0; i < count; i++)
779 /* is there any code for this eBBlock? (e.g. ROM assignment) */
793 /*-----------------------------------------------------------------*/
794 /* computeLiveRanges - computes the live ranges for variables */
795 /*-----------------------------------------------------------------*/
797 computeLiveRanges (eBBlock ** ebbs, int count, bool emitWarnings)
799 /* first look through all blocks and adjust the
800 sch and ech pointers */
801 adjustIChain (ebbs, count);
803 /* sequence the code the live ranges are computed
804 in terms of this sequence additionally the
805 routine will also create a hashtable of instructions */
807 setToNull ((void *) &iCodehTab);
808 iCodehTab = newHashTable (iCodeKey);
809 hashiCodeKeys (ebbs, count);
810 setToNull ((void *) &iCodeSeqhTab);
811 iCodeSeqhTab = newHashTable (iCodeKey);
812 sequenceiCode (ebbs, count);
814 /* mark the ranges live for each point */
815 setToNull ((void *) &liveRanges);
816 rlivePoint (ebbs, count, emitWarnings);
818 /* mark the from & to live ranges for variables used */
819 markLiveRanges (ebbs, count);
821 /* compute which overlaps with what */
822 computeClash(ebbs, count);
825 /*-----------------------------------------------------------------*/
826 /* recomputeLiveRanges - recomputes the live ranges for variables */
827 /*-----------------------------------------------------------------*/
829 recomputeLiveRanges (eBBlock ** ebbs, int count)
834 /* clear all rlive bitVectors */
835 rliveClear (ebbs, count);
837 sym = hTabFirstItem (liveRanges, &key);
844 freeBitVect (sym->clashes);
846 } while ( (sym = hTabNextItem (liveRanges, &key)));
849 /* do the LR computation again */
850 computeLiveRanges (ebbs, count, FALSE);
853 /*-----------------------------------------------------------------*/
854 /* dump icode->rlive in all blocks */
855 /*-----------------------------------------------------------------*/
858 dumpIcRlive (eBBlock ** ebbs, int count)
863 /* for all blocks do */
864 for (i = 0; i < count; i++)
866 printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name);
867 /* for all instructions in this block do */
868 for (ic = ebbs[i]->sch; ic; ic = ic->next)
870 printf ("\tic->key %d\n", ic->key);
874 /* for all live Ranges alive at this point */
875 for (j = 1; j < ic->rlive->size; j++)
879 if (!bitVectBitValue (ic->rlive, j))
882 /* find the live range we are interested in */
883 if ((sym = hTabItemWithKey (liveRanges, j)))
884 printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name);