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 */
462 if (OP_SYMBOL (op)->prereqv)
464 werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
465 OP_SYMBOL (op)->prereqv->name);
466 OP_SYMBOL (op)->prereqv->reqv = NULL;
467 OP_SYMBOL (op)->prereqv->allocreq = 1;
472 werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
473 OP_SYMBOL (op)->name);
476 /* is this block part of a loop? */
477 if (IS_ITEMP (op) && ebp->depth != 0)
479 /* extend the life range to the outermost loop */
480 unvisitBlocks(ebbs, count);
481 markWholeLoop (ebp, op->key);
486 /*-----------------------------------------------------------------*/
487 /* incUsed - increment a symbol's usage count */
488 /*-----------------------------------------------------------------*/
490 incUsed (iCode *ic, operand *op)
493 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
495 OP_SYMBOL (op)->used += 1;
498 /*-----------------------------------------------------------------*/
499 /* rliveClear - clears the rlive bitVectors */
500 /*-----------------------------------------------------------------*/
502 rliveClear (eBBlock ** ebbs, int count)
506 /* for all blocks do */
507 for (i = 0; i < count; i++)
511 /* for all instructions in this block do */
512 for (ic = ebbs[i]->sch; ic; ic = ic->next)
514 freeBitVect (ic->rlive);
520 /*-----------------------------------------------------------------*/
521 /* rlivePoint - for each point compute the ranges that are alive */
522 /* The live range is only stored for ITEMPs; the same code is used */
523 /* to find use of unitialized AUTOSYMs (an ITEMP is an AUTOSYM). */
524 /*-----------------------------------------------------------------*/
526 rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
532 /* for all blocks do */
533 for (i = 0; i < count; i++)
537 /* for all instructions in this block do */
538 for (ic = ebbs[i]->sch; ic; ic = ic->next)
542 ic->rlive = newBitVect (operandKey);
547 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
549 incUsed (ic, IC_JTCOND(ic));
551 if (!IS_AUTOSYM(IC_JTCOND(ic)))
554 findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings);
555 if (IS_ITEMP(IC_JTCOND(ic)))
557 unvisitBlocks(ebbs, count);
558 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
559 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
565 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
567 incUsed (ic, IC_COND(ic));
569 if (!IS_AUTOSYM(IC_COND(ic)))
572 findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings);
573 if (IS_ITEMP(IC_COND(ic)))
575 unvisitBlocks (ebbs, count);
576 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
577 findNextUse (ebbs[i], ic->next, IC_COND(ic));
583 if (IS_SYMOP(IC_LEFT(ic)))
585 incUsed (ic, IC_LEFT(ic));
586 if (IS_AUTOSYM(IC_LEFT(ic)) &&
587 ic->op != ADDRESS_OF)
589 findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings);
590 if (IS_ITEMP(IC_LEFT(ic)))
592 unvisitBlocks(ebbs, count);
593 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
594 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
596 /* if this is a send extend the LR to the call */
600 for (lic = ic; lic; lic = lic->next)
602 if (lic->op == CALL || lic->op == PCALL)
604 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
613 if (IS_SYMOP(IC_RIGHT(ic)))
615 incUsed (ic, IC_RIGHT(ic));
616 if (IS_AUTOSYM(IC_RIGHT(ic)))
618 findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings);
619 if (IS_ITEMP(IC_RIGHT(ic)))
621 unvisitBlocks(ebbs, count);
622 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
623 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
628 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
629 incUsed (ic, IC_RESULT(ic));
631 if (IS_AUTOSYM(IC_RESULT(ic)))
635 findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings);
637 if (IS_ITEMP(IC_RESULT(ic)))
639 unvisitBlocks(ebbs, count);
640 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
641 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
645 if (!POINTER_SET(ic) && IC_RESULT(ic))
646 ic->defKey = IC_RESULT(ic)->key;
650 /* check all symbols that are alive in the last instruction */
651 /* but are not alive in all successors */
653 succ = setFirstItem (ebbs[i]->succList);
657 alive = succ->sch->rlive;
658 while ((succ = setNextItem (ebbs[i]->succList)))
661 alive = bitVectIntersect (alive, succ->sch->rlive);
665 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
669 for (key = 1; key < alive->size; key++)
671 if (!bitVectBitValue (alive, key))
674 unvisitBlocks(ebbs, count);
675 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
681 /*-----------------------------------------------------------------*/
682 /* computeClash - find out which live ranges collide with others */
683 /*-----------------------------------------------------------------*/
685 computeClash (eBBlock ** ebbs, int count)
689 /* for all blocks do */
690 for (i = 0; i < count; i++)
694 /* for every iCode do */
695 for (ic = ebbs[i]->sch; ic; ic = ic->next)
700 /* for all iTemps alive at this iCode */
701 for (key1 = 1; key1 < ic->rlive->size; key1++)
703 if (!bitVectBitValue(ic->rlive, key1))
706 sym1 = hTabItemWithKey(liveRanges, key1);
711 /* for all other iTemps alive at this iCode */
712 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
714 if (!bitVectBitValue(ic->rlive, key2))
717 sym2 = hTabItemWithKey(liveRanges, key2);
722 /* if the result and left or right is an iTemp */
723 /* than possibly the iTemps do not clash */
724 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
725 IS_ITEMP(IC_RESULT(ic)) &&
726 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
728 if (OP_SYMBOL(IC_RESULT(ic))->key == key1
729 && sym1->liveFrom == ic->seq
730 && sym2->liveTo == ic->seq)
732 if (IS_SYMOP(IC_LEFT(ic)))
733 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
735 if (IS_SYMOP(IC_RIGHT(ic)))
736 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
740 if (OP_SYMBOL(IC_RESULT(ic))->key == key2
741 && sym2->liveFrom == ic->seq
742 && sym1->liveTo == ic->seq)
744 if (IS_SYMOP(IC_LEFT(ic)))
745 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
747 if (IS_SYMOP(IC_RIGHT(ic)))
748 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
753 /* the iTemps do clash. set the bits in clashes */
754 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
755 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
757 /* check if they share the same spill location */
758 /* what is this good for? */
759 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
760 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
762 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
763 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
764 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
765 else SYM_SPIL_LOC(sym1)=NULL;
773 /*-----------------------------------------------------------------*/
774 /* allDefsOutOfRange - all definitions are out of a range */
775 /*-----------------------------------------------------------------*/
777 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
784 for (i = 0; i < defs->size; i++)
788 if (bitVectBitValue (defs, i) &&
789 (ic = hTabItemWithKey (iCodehTab, i)) &&
790 (ic->seq >= fseq && ic->seq <= toseq))
798 /*-----------------------------------------------------------------*/
799 /* notUsedInBlock - not used in this block */
800 /*-----------------------------------------------------------------*/
802 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
804 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
805 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
806 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
809 /*-----------------------------------------------------------------*/
810 /* adjustIChain - correct the sch and ech pointers */
811 /*-----------------------------------------------------------------*/
813 adjustIChain (eBBlock ** ebbs, int count)
817 for (i = 0; i < count; i++)
826 /* is there any code for this eBBlock? (e.g. ROM assignment) */
840 /*-----------------------------------------------------------------*/
841 /* computeLiveRanges - computes the live ranges for variables */
842 /*-----------------------------------------------------------------*/
844 computeLiveRanges (eBBlock ** ebbs, int count, bool emitWarnings)
846 /* first look through all blocks and adjust the
847 sch and ech pointers */
848 adjustIChain (ebbs, count);
850 /* sequence the code the live ranges are computed
851 in terms of this sequence additionally the
852 routine will also create a hashtable of instructions */
854 setToNull ((void *) &iCodehTab);
855 iCodehTab = newHashTable (iCodeKey);
856 hashiCodeKeys (ebbs, count);
857 setToNull ((void *) &iCodeSeqhTab);
858 iCodeSeqhTab = newHashTable (iCodeKey);
859 sequenceiCode (ebbs, count);
861 /* mark the ranges live for each point */
862 setToNull ((void *) &liveRanges);
863 rlivePoint (ebbs, count, emitWarnings);
865 /* mark the from & to live ranges for variables used */
866 markLiveRanges (ebbs, count);
868 /* compute which overlaps with what */
869 computeClash(ebbs, count);
872 /*-----------------------------------------------------------------*/
873 /* recomputeLiveRanges - recomputes the live ranges for variables */
874 /*-----------------------------------------------------------------*/
876 recomputeLiveRanges (eBBlock ** ebbs, int count)
881 /* clear all rlive bitVectors */
882 rliveClear (ebbs, count);
884 sym = hTabFirstItem (liveRanges, &key);
891 freeBitVect (sym->clashes);
893 } while ( (sym = hTabNextItem (liveRanges, &key)));
896 /* do the LR computation again */
897 computeLiveRanges (ebbs, count, FALSE);
900 /*-----------------------------------------------------------------*/
901 /* dump icode->rlive in all blocks */
902 /*-----------------------------------------------------------------*/
905 dumpIcRlive (eBBlock ** ebbs, int count)
910 /* for all blocks do */
911 for (i = 0; i < count; i++)
913 printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name);
914 /* for all instructions in this block do */
915 for (ic = ebbs[i]->sch; ic; ic = ic->next)
917 printf ("\tic->key %d\n", ic->key);
921 /* for all live Ranges alive at this point */
922 for (j = 1; j < ic->rlive->size; j++)
926 if (!bitVectBitValue (ic->rlive, j))
929 /* find the live range we are interested in */
930 if ((sym = hTabItemWithKey (liveRanges, j)))
931 printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name);