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 /* all symbols, for which the previous definition is searched
35 and warning is emitted if there's none. */
36 #define IS_AUTOSYM(op) (IS_ITEMP(op) || \
37 (IS_SYMOP(op) && IS_AUTO(op->operand.symOperand) && !IS_PARM(op)))
39 /*-----------------------------------------------------------------*/
40 /* hashiCodeKeys - add all iCodes to the hash table */
41 /*-----------------------------------------------------------------*/
43 hashiCodeKeys (eBBlock ** ebbs, int count)
47 for (i = 0; i < count; i++)
50 for (ic = ebbs[i]->sch; ic; ic = ic->next)
51 hTabAddItem (&iCodehTab, ic->key, ic);
55 /*-----------------------------------------------------------------*/
56 /* sequenceiCode - creates a sequence number for the iCode & add */
57 /*-----------------------------------------------------------------*/
59 sequenceiCode (eBBlock ** ebbs, int count)
63 for (i = 0; i < count; i++)
67 ebbs[i]->fSeq = iCodeSeq + 1;
68 for (ic = ebbs[i]->sch; ic; ic = ic->next)
71 ic->depth = ebbs[i]->depth;
72 //hTabAddItem (&iCodehTab, ic->key, ic);
73 hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
75 ebbs[i]->lSeq = iCodeSeq;
79 /*-----------------------------------------------------------------*/
80 /* setFromRange - sets the from range of a given operand */
81 /*-----------------------------------------------------------------*/
84 setFromRange (operand * op, int from)
86 /* only for compiler defined temporaries */
90 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
93 OP_SYMBOL (op)->isptr = 1;
95 if (!OP_LIVEFROM (op) ||
96 OP_LIVEFROM (op) > from)
97 OP_LIVEFROM (op) = from;
101 /*-----------------------------------------------------------------*/
102 /* setToRange - set the range to for an operand */
103 /*-----------------------------------------------------------------*/
105 setToRange (operand * op, int to, bool check)
107 /* only for compiler defined temps */
111 OP_SYMBOL (op)->key = op->key;
112 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
115 OP_SYMBOL (op)->isptr = 1;
125 /*-----------------------------------------------------------------*/
126 /* setFromRange - sets the from range of a given operand */
127 /*-----------------------------------------------------------------*/
129 setLiveFrom (symbol * sym, int from)
131 if (!sym->liveFrom || sym->liveFrom > from)
132 sym->liveFrom = from;
135 /*-----------------------------------------------------------------*/
136 /* setToRange - set the range to for an operand */
137 /*-----------------------------------------------------------------*/
139 setLiveTo (symbol * sym, int to)
141 if (!sym->liveTo || sym->liveTo < to)
145 /*-----------------------------------------------------------------*/
146 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
147 /*-----------------------------------------------------------------*/
149 markLiveRanges (eBBlock ** ebbs, int count)
154 for (i = 0; i < count; i++)
158 for (ic = ebbs[i]->sch; ic; ic = ic->next)
160 if (ic->op == CALL || ic->op == PCALL)
161 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
162 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
164 /* for all iTemps alive at this iCode */
165 for (key = 1; key < ic->rlive->size; key++)
167 if (!bitVectBitValue(ic->rlive, key))
170 sym = hTabItemWithKey(liveRanges, key);
171 setLiveTo(sym, ic->seq);
172 setLiveFrom(sym, ic->seq);
179 /*-----------------------------------------------------------------*/
180 /* markAlive - marks the operand as alive between sic and eic */
181 /*-----------------------------------------------------------------*/
183 markAlive (iCode * sic, iCode * eic, int key)
187 for (dic = sic; dic != eic->next; dic = dic->next)
189 dic->rlive = bitVectSetBit (dic->rlive, key);
193 /*-----------------------------------------------------------------*/
194 /* findNextUseSym - finds the next use of the symbol and marks it */
195 /* alive in between */
196 /*-----------------------------------------------------------------*/
198 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
204 hTabAddItemIfNotP (&liveRanges, sym->key, sym);
207 goto check_successors;
209 /* if we check a complete block and the symbol */
210 /* is alive at the beginning of the block */
211 /* and not defined in the first instructions */
212 /* then a next use exists (return 1) */
213 if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
215 /* check if the first instruction is a def of this op */
216 if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
219 if (IS_ITEMP(IC_RESULT(ic)))
220 if (IC_RESULT(ic)->key == sym->key)
232 /* for all remaining instructions in current block */
233 for (uic = ic; uic; uic = uic->next)
239 if (uic->op == JUMPTABLE)
241 if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
243 markAlive(ic, uic, sym->key);
251 if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
253 markAlive(ic, uic, sym->key);
259 if (IS_ITEMP (IC_LEFT (uic)))
260 if (IC_LEFT (uic)->key == sym->key)
262 markAlive(ic, uic, sym->key);
266 if (IS_ITEMP (IC_RIGHT (uic)))
267 if (IC_RIGHT (uic)->key == sym->key)
269 markAlive (ic, uic, sym->key);
273 if (IS_ITEMP (IC_RESULT (uic)))
274 if (IC_RESULT (uic)->key == sym->key)
276 if (POINTER_SET (uic))
278 markAlive (ic, uic, sym->key);
287 /* check all successors */
290 succ = setFirstItem (ebp->succList);
291 for (; succ; succ = setNextItem (ebp->succList))
293 retval += findNextUseSym (succ, succ->sch, sym);
298 if (ic) markAlive (ic, ebp->ech, sym->key);
305 /*-----------------------------------------------------------------*/
306 /* findNextUse - finds the next use of the operand and marks it */
307 /* alive in between */
308 /*-----------------------------------------------------------------*/
310 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
313 OP_SYMBOL (op)->isptr = 1;
315 OP_SYMBOL (op)->key = op->key;
317 return findNextUseSym (ebp, ic, OP_SYMBOL(op));
320 /*-----------------------------------------------------------------*/
321 /* unvisitBlocks - clears visited in all blocks */
322 /*-----------------------------------------------------------------*/
324 unvisitBlocks (eBBlock ** ebbs, int count)
328 for (i = 0; i < count; i++)
329 ebbs[i]->visited = 0;
332 /*------------------------------------------------------------------*/
333 /* markWholeLoop - mark the symbol 'key' alive in all blocks */
334 /* included by the outermost loop */
335 /*------------------------------------------------------------------*/
337 markWholeLoop (eBBlock *ebp, int key)
341 /* avoid endless loops */
344 /* recurse through all predecessors */
345 for (ebpi = setFirstItem (ebp->predList);
347 ebpi = setNextItem (ebp->predList))
351 /* is the predecessor still in the loop? */
352 if (ebpi->depth == 0)
354 markWholeLoop (ebpi, key);
357 /* recurse through all successors */
358 for (ebpi = setFirstItem (ebp->succList);
360 ebpi = setNextItem (ebp->succList))
364 if (ebpi->depth == 0)
366 markWholeLoop (ebpi, key);
369 markAlive (ebp->sch, ebp->ech, key);
372 /*------------------------------------------------------------------*/
373 /* findPrevUseSym - search for a previous definition of a symbol in */
374 /* - the previous icodes */
375 /* - all branches of predecessors */
376 /*------------------------------------------------------------------*/
378 findPrevUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
385 /* already visited: this branch must have been succesfull, */
386 /* because otherwise the search would have been aborted. */
391 /* search backward in the current block */
392 for (uic = ic; uic; uic = uic->prev)
394 if (!POINTER_SET (uic) && IS_AUTOSYM (IC_RESULT (uic)))
396 if (IC_RESULT (uic)->key == sym->key)
398 /* Ok, found a definition */
402 /* address taken from symbol? */
403 if (uic->op == ADDRESS_OF && IS_AUTOSYM (IC_LEFT (uic)))
405 if (IC_LEFT (uic)->key == sym->key)
407 /* Ok, found a definition */
413 /* There's no definition in this bblock, */
414 /* let's have a look at all predecessors. */
415 pred = setFirstItem (ebp->predList);
418 /* no more predecessors and nothing found yet :-( */
421 for (; pred; pred = setNextItem (ebp->predList))
423 /* recurse into all predecessors */
424 if (!findPrevUseSym (pred, pred->ech, sym))
426 /* found nothing: abort */
431 /* Success! Went through all branches with no abort: */
432 /* all branches end with a definition */
436 /*------------------------------------------------------------------*/
437 /* findPrevUse - search for a previous definition of an operand */
438 /* If there's no definition let's: */
439 /* - emit a warning */
440 /* - fix the life range, if the symbol is used in */
442 /*------------------------------------------------------------------*/
444 findPrevUse (eBBlock *ebp, iCode *ic, operand *op,
445 eBBlock ** ebbs, int count,
448 unvisitBlocks (ebbs, count);
451 OP_SYMBOL (op)->isptr = 1;
452 OP_SYMBOL (op)->key = op->key;
454 /* There must be a definition in each branch of predecessors */
455 if (!findPrevUseSym (ebp, ic->prev, OP_SYMBOL(op)))
457 /* computeLiveRanges() is called twice */
460 werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
461 IS_ITEMP (op) ? OP_SYMBOL (op)->prereqv->name :
462 OP_SYMBOL (op)->name);
465 OP_SYMBOL (op)->prereqv->reqv = NULL;
466 OP_SYMBOL (op)->prereqv->allocreq = 1;
469 /* is this block part of a loop? */
473 /* extend the life range to the outermost loop */
474 unvisitBlocks(ebbs, count);
475 markWholeLoop (ebp, op->key);
480 /*-----------------------------------------------------------------*/
481 /* incUsed - increment a symbol's usage count */
482 /*-----------------------------------------------------------------*/
484 incUsed (iCode *ic, operand *op)
487 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
489 OP_SYMBOL (op)->used += 1;
492 /*-----------------------------------------------------------------*/
493 /* rliveClear - clears the rlive bitVectors */
494 /*-----------------------------------------------------------------*/
496 rliveClear (eBBlock ** ebbs, int count)
500 /* for all blocks do */
501 for (i = 0; i < count; i++)
505 /* for all instructions in this block do */
506 for (ic = ebbs[i]->sch; ic; ic = ic->next)
508 freeBitVect (ic->rlive);
514 /*-----------------------------------------------------------------*/
515 /* rlivePoint - for each point compute the ranges that are alive */
516 /* The live range is only stored for ITEMPs; the same code is used */
517 /* to find use of unitialized AUTOSYMs (an ITEMP is an AUTOSYM). */
518 /*-----------------------------------------------------------------*/
520 rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
526 /* for all blocks do */
527 for (i = 0; i < count; i++)
531 /* for all instructions in this block do */
532 for (ic = ebbs[i]->sch; ic; ic = ic->next)
536 ic->rlive = newBitVect (operandKey);
541 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
543 incUsed (ic, IC_JTCOND(ic));
545 if (!IS_AUTOSYM(IC_JTCOND(ic)))
548 findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings);
549 if (IS_ITEMP(IC_JTCOND(ic)))
551 unvisitBlocks(ebbs, count);
552 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
553 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
559 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
561 incUsed (ic, IC_COND(ic));
563 if (!IS_AUTOSYM(IC_COND(ic)))
566 findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings);
567 if (IS_ITEMP(IC_COND(ic)))
569 unvisitBlocks (ebbs, count);
570 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
571 findNextUse (ebbs[i], ic->next, IC_COND(ic));
577 if (IS_SYMOP(IC_LEFT(ic)))
579 incUsed (ic, IC_LEFT(ic));
580 if (IS_AUTOSYM(IC_LEFT(ic)) &&
581 ic->op != ADDRESS_OF)
583 findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings);
584 if (IS_ITEMP(IC_LEFT(ic)))
586 unvisitBlocks(ebbs, count);
587 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
588 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
590 /* if this is a send extend the LR to the call */
594 for (lic = ic; lic; lic = lic->next)
596 if (lic->op == CALL || lic->op == PCALL)
598 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
607 if (IS_SYMOP(IC_RIGHT(ic)))
609 incUsed (ic, IC_RIGHT(ic));
610 if (IS_AUTOSYM(IC_RIGHT(ic)))
612 findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings);
613 if (IS_ITEMP(IC_RIGHT(ic)))
615 unvisitBlocks(ebbs, count);
616 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
617 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
622 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
623 incUsed (ic, IC_RESULT(ic));
625 if (IS_AUTOSYM(IC_RESULT(ic)))
629 findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings);
631 if (IS_ITEMP(IC_RESULT(ic)))
633 unvisitBlocks(ebbs, count);
634 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
635 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
639 if (!POINTER_SET(ic) && IC_RESULT(ic))
640 ic->defKey = IC_RESULT(ic)->key;
644 /* check all symbols that are alive in the last instruction */
645 /* but are not alive in all successors */
647 succ = setFirstItem (ebbs[i]->succList);
651 alive = succ->sch->rlive;
652 while ((succ = setNextItem (ebbs[i]->succList)))
655 alive = bitVectIntersect (alive, succ->sch->rlive);
659 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
663 for (key = 1; key < alive->size; key++)
665 if (!bitVectBitValue (alive, key))
668 unvisitBlocks(ebbs, count);
669 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
675 /*-----------------------------------------------------------------*/
676 /* computeClash - find out which live ranges collide with others */
677 /*-----------------------------------------------------------------*/
679 computeClash (eBBlock ** ebbs, int count)
683 /* for all blocks do */
684 for (i = 0; i < count; i++)
688 /* for every iCode do */
689 for (ic = ebbs[i]->sch; ic; ic = ic->next)
694 /* for all iTemps alive at this iCode */
695 for (key1 = 1; key1 < ic->rlive->size; key1++)
697 if (!bitVectBitValue(ic->rlive, key1))
700 sym1 = hTabItemWithKey(liveRanges, key1);
705 /* for all other iTemps alive at this iCode */
706 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
708 if (!bitVectBitValue(ic->rlive, key2))
711 sym2 = hTabItemWithKey(liveRanges, key2);
716 /* if the result and left or right is an iTemp */
717 /* than possibly the iTemps do not clash */
718 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
719 IS_ITEMP(IC_RESULT(ic)) &&
720 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
722 if (OP_SYMBOL(IC_RESULT(ic))->key == key1
723 && sym1->liveFrom == ic->seq
724 && sym2->liveTo == ic->seq)
726 if (IS_SYMOP(IC_LEFT(ic)))
727 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
729 if (IS_SYMOP(IC_RIGHT(ic)))
730 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
734 if (OP_SYMBOL(IC_RESULT(ic))->key == key2
735 && sym2->liveFrom == ic->seq
736 && sym1->liveTo == ic->seq)
738 if (IS_SYMOP(IC_LEFT(ic)))
739 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
741 if (IS_SYMOP(IC_RIGHT(ic)))
742 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
747 /* the iTemps do clash. set the bits in clashes */
748 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
749 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
751 /* check if they share the same spill location */
752 /* what is this good for? */
753 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
754 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
756 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
757 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
758 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
759 else SYM_SPIL_LOC(sym1)=NULL;
767 /*-----------------------------------------------------------------*/
768 /* allDefsOutOfRange - all definitions are out of a range */
769 /*-----------------------------------------------------------------*/
771 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
778 for (i = 0; i < defs->size; i++)
782 if (bitVectBitValue (defs, i) &&
783 (ic = hTabItemWithKey (iCodehTab, i)) &&
784 (ic->seq >= fseq && ic->seq <= toseq))
792 /*-----------------------------------------------------------------*/
793 /* notUsedInBlock - not used in this block */
794 /*-----------------------------------------------------------------*/
796 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
798 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
799 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
800 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
803 /*-----------------------------------------------------------------*/
804 /* adjustIChain - correct the sch and ech pointers */
805 /*-----------------------------------------------------------------*/
807 adjustIChain (eBBlock ** ebbs, int count)
811 for (i = 0; i < count; i++)
820 /* is there any code for this eBBlock? (e.g. ROM assignment) */
834 /*-----------------------------------------------------------------*/
835 /* computeLiveRanges - computes the live ranges for variables */
836 /*-----------------------------------------------------------------*/
838 computeLiveRanges (eBBlock ** ebbs, int count, bool emitWarnings)
840 /* first look through all blocks and adjust the
841 sch and ech pointers */
842 adjustIChain (ebbs, count);
844 /* sequence the code the live ranges are computed
845 in terms of this sequence additionally the
846 routine will also create a hashtable of instructions */
848 setToNull ((void *) &iCodehTab);
849 iCodehTab = newHashTable (iCodeKey);
850 hashiCodeKeys (ebbs, count);
851 setToNull ((void *) &iCodeSeqhTab);
852 iCodeSeqhTab = newHashTable (iCodeKey);
853 sequenceiCode (ebbs, count);
855 /* mark the ranges live for each point */
856 setToNull ((void *) &liveRanges);
857 rlivePoint (ebbs, count, emitWarnings);
859 /* mark the from & to live ranges for variables used */
860 markLiveRanges (ebbs, count);
862 /* compute which overlaps with what */
863 computeClash(ebbs, count);
866 /*-----------------------------------------------------------------*/
867 /* recomputeLiveRanges - recomputes the live ranges for variables */
868 /*-----------------------------------------------------------------*/
870 recomputeLiveRanges (eBBlock ** ebbs, int count)
875 /* clear all rlive bitVectors */
876 rliveClear (ebbs, count);
878 sym = hTabFirstItem (liveRanges, &key);
885 freeBitVect (sym->clashes);
887 } while ( (sym = hTabNextItem (liveRanges, &key)));
890 /* do the LR computation again */
891 computeLiveRanges (ebbs, count, FALSE);
894 /*-----------------------------------------------------------------*/
895 /* dump icode->rlive in all blocks */
896 /*-----------------------------------------------------------------*/
899 dumpIcRlive (eBBlock ** ebbs, int count)
904 /* for all blocks do */
905 for (i = 0; i < count; i++)
907 printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name);
908 /* for all instructions in this block do */
909 for (ic = ebbs[i]->sch; ic; ic = ic->next)
911 printf ("\tic->key %d\n", ic->key);
915 /* for all live Ranges alive at this point */
916 for (j = 1; j < ic->rlive->size; j++)
920 if (!bitVectBitValue (ic->rlive, j))
923 /* find the live range we are interested in */
924 if ((sym = hTabItemWithKey (liveRanges, j)))
925 printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name);