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)
224 /* for all remaining instructions in current block */
225 for (uic = ic; uic; uic = uic->next)
231 if (uic->op == JUMPTABLE)
233 if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
235 markAlive(ic, uic, sym->key);
243 if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
245 markAlive(ic, uic, sym->key);
251 if (IS_ITEMP (IC_LEFT (uic)))
252 if (IC_LEFT (uic)->key == sym->key)
254 markAlive(ic, uic, sym->key);
258 if (IS_ITEMP (IC_RIGHT (uic)))
259 if (IC_RIGHT (uic)->key == sym->key)
261 markAlive (ic, uic, sym->key);
265 if (IS_ITEMP (IC_RESULT (uic)))
266 if (IC_RESULT (uic)->key == sym->key)
268 if (POINTER_SET (uic))
270 markAlive (ic, uic, sym->key);
279 /* check all successors */
282 succ = setFirstItem (ebp->succList);
283 for (; succ; succ = setNextItem (ebp->succList))
285 retval += findNextUseSym (succ, succ->sch, sym);
290 if (ic) markAlive (ic, ebp->ech, sym->key);
297 /*-----------------------------------------------------------------*/
298 /* findNextUse - finds the next use of the operand and marks it */
299 /* alive in between */
300 /*-----------------------------------------------------------------*/
302 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
305 OP_SYMBOL (op)->isptr = 1;
307 OP_SYMBOL (op)->key = op->key;
309 return findNextUseSym (ebp, ic, OP_SYMBOL(op));
312 /*-----------------------------------------------------------------*/
313 /* unvisitBlocks - clears visited in all blocks */
314 /*-----------------------------------------------------------------*/
315 void unvisitBlocks (eBBlock ** ebbs, int count)
319 for (i = 0; i < count; i++)
320 ebbs[i]->visited = 0;
323 /*-----------------------------------------------------------------*/
324 /* unvisitBlocks - clears visited in all blocks */
325 /*-----------------------------------------------------------------*/
327 incUsed (iCode *ic, operand *op)
330 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
332 OP_SYMBOL (op)->used += 1;
335 /*-----------------------------------------------------------------*/
336 /* rliveClear - clears the rlive bitVectors */
337 /*-----------------------------------------------------------------*/
339 rliveClear (eBBlock ** ebbs, int count)
343 /* for all blocks do */
344 for (i = 0; i < count; i++)
348 /* for all instructions in this block do */
349 for (ic = ebbs[i]->sch; ic; ic = ic->next)
351 freeBitVect (ic->rlive);
357 /*-----------------------------------------------------------------*/
358 /* rlivePoint - for each point compute the ranges that are alive */
359 /*-----------------------------------------------------------------*/
361 rlivePoint (eBBlock ** ebbs, int count)
367 /* for all blocks do */
368 for (i = 0; i < count; i++)
372 /* for all instructions in this block do */
373 for (ic = ebbs[i]->sch; ic; ic = ic->next)
377 ic->rlive = newBitVect (operandKey);
382 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
384 incUsed (ic, IC_JTCOND(ic));
386 if (!IS_ITEMP(IC_JTCOND(ic)))
389 unvisitBlocks(ebbs, count);
390 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
391 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
396 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
398 incUsed (ic, IC_COND(ic));
400 if (!IS_ITEMP(IC_COND(ic)))
403 unvisitBlocks (ebbs, count);
404 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
405 findNextUse (ebbs[i], ic->next, IC_COND(ic));
410 if (IS_SYMOP(IC_LEFT(ic)))
412 incUsed (ic, IC_LEFT(ic));
413 if (IS_ITEMP(IC_LEFT(ic)))
416 unvisitBlocks(ebbs, count);
417 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
418 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
420 /* if this is a send extend the LR to the call */
424 for (lic = ic; lic; lic = lic->next)
426 if (lic->op == CALL || lic->op == PCALL)
428 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
436 if (IS_SYMOP(IC_RIGHT(ic)))
438 incUsed (ic, IC_RIGHT(ic));
439 if (IS_ITEMP(IC_RIGHT(ic)))
441 unvisitBlocks(ebbs, count);
442 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
443 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
447 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
448 incUsed (ic, IC_RESULT(ic));
450 if (IS_ITEMP(IC_RESULT(ic)))
452 unvisitBlocks(ebbs, count);
453 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
454 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
457 if (!POINTER_SET(ic) && IC_RESULT(ic))
458 ic->defKey = IC_RESULT(ic)->key;
462 /* check all symbols that are alive in the last instruction */
463 /* but are not alive in all successors */
465 succ = setFirstItem (ebbs[i]->succList);
469 alive = succ->sch->rlive;
470 while ((succ = setNextItem (ebbs[i]->succList)))
473 alive = bitVectIntersect (alive, succ->sch->rlive);
477 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
479 for (key = 1; key < alive->size; key++)
481 if (!bitVectBitValue (alive, key))
484 unvisitBlocks(ebbs, count);
485 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
491 /*-----------------------------------------------------------------*/
492 /* computeClash - find out which live ranges collide with others */
493 /*-----------------------------------------------------------------*/
495 computeClash (eBBlock ** ebbs, int count)
499 /* for all blocks do */
500 for (i = 0; i < count; i++)
504 /* for every iCode do */
505 for (ic = ebbs[i]->sch; ic; ic = ic->next)
510 /* for all iTemps alive at this iCode */
511 for (key1 = 1; key1 < ic->rlive->size; key1++)
513 if (!bitVectBitValue(ic->rlive, key1))
516 sym1 = hTabItemWithKey(liveRanges, key1);
521 /* for all other iTemps alive at this iCode */
522 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
524 if (!bitVectBitValue(ic->rlive, key2))
527 sym2 = hTabItemWithKey(liveRanges, key2);
532 /* if the result and left or right is an iTemp */
533 /* than possibly the iTemps do not clash */
534 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
535 IS_ITEMP(IC_RESULT(ic)) &&
536 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
538 if (OP_SYMBOL(IC_RESULT(ic))->key == key1)
540 if (IS_SYMOP(IC_LEFT(ic)))
541 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
543 if (IS_SYMOP(IC_RIGHT(ic)))
544 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
548 if (OP_SYMBOL(IC_RESULT(ic))->key == key2)
550 if (IS_SYMOP(IC_LEFT(ic)))
551 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
553 if (IS_SYMOP(IC_RIGHT(ic)))
554 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
559 /* the iTemps do clash. set the bits in clashes */
560 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
561 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
563 /* check if they share the same spill location */
564 /* what is this good for? */
565 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
566 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
568 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
569 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
570 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
571 else SYM_SPIL_LOC(sym1)=NULL;
579 /*-----------------------------------------------------------------*/
580 /* allDefsOutOfRange - all definitions are out of a range */
581 /*-----------------------------------------------------------------*/
583 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
590 for (i = 0; i < defs->size; i++)
594 if (bitVectBitValue (defs, i) &&
595 (ic = hTabItemWithKey (iCodehTab, i)) &&
596 (ic->seq >= fseq && ic->seq <= toseq))
605 /*-----------------------------------------------------------------*/
606 /* notUsedInBlock - not used in this block */
607 /*-----------------------------------------------------------------*/
609 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
611 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
612 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
613 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
616 /*-----------------------------------------------------------------*/
617 /* adjustIChain - correct the sch and ech pointers */
618 /*-----------------------------------------------------------------*/
620 adjustIChain (eBBlock ** ebbs, int count)
624 for (i = 0; i < count; i++)
633 /* is there any code for this eBBlock? (e.g. ROM assignment) */
647 /*-----------------------------------------------------------------*/
648 /* computeLiveRanges - computes the live ranges for variables */
649 /*-----------------------------------------------------------------*/
651 computeLiveRanges (eBBlock ** ebbs, int count)
653 /* first look through all blocks and adjust the
654 sch and ech pointers */
655 adjustIChain (ebbs, count);
657 /* sequence the code the live ranges are computed
658 in terms of this sequence additionally the
659 routine will also create a hashtable of instructions */
661 setToNull ((void *) &iCodehTab);
662 iCodehTab = newHashTable (iCodeKey);
663 hashiCodeKeys (ebbs, count);
664 setToNull ((void *) &iCodeSeqhTab);
665 iCodeSeqhTab = newHashTable (iCodeKey);
666 sequenceiCode (ebbs, count);
668 /* mark the ranges live for each point */
669 setToNull ((void *) &liveRanges);
670 rlivePoint (ebbs, count);
672 /* mark the from & to live ranges for variables used */
673 markLiveRanges (ebbs, count);
675 /* compute which overlaps with what */
676 computeClash(ebbs, count);
679 /*-----------------------------------------------------------------*/
680 /* recomputeLiveRanges - recomputes the live ranges for variables */
681 /*-----------------------------------------------------------------*/
683 recomputeLiveRanges (eBBlock ** ebbs, int count)
688 /* clear all rlive bitVectors */
689 rliveClear (ebbs, count);
691 sym = hTabFirstItem (liveRanges, &key);
698 freeBitVect (sym->clashes);
700 } while ( (sym = hTabNextItem (liveRanges, &key)));
703 /* do the LR computation again */
704 computeLiveRanges (ebbs, count);