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 /* sequenceiCode - creates a sequence number for the iCode & add */
36 /*-----------------------------------------------------------------*/
38 sequenceiCode (eBBlock ** ebbs, int count)
42 for (i = 0; i < count; i++)
46 ebbs[i]->fSeq = iCodeSeq + 1;
47 for (ic = ebbs[i]->sch; ic; ic = ic->next)
50 ic->depth = ebbs[i]->depth;
51 hTabAddItem (&iCodehTab, ic->key, ic);
52 hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
54 ebbs[i]->lSeq = iCodeSeq;
58 /*-----------------------------------------------------------------*/
59 /* setFromRange - sets the from range of a given operand */
60 /*-----------------------------------------------------------------*/
62 setFromRange (operand * op, int from)
64 /* only for compiler defined temporaries */
68 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
71 OP_SYMBOL (op)->isptr = 1;
73 if (!OP_LIVEFROM (op) ||
74 OP_LIVEFROM (op) > from)
75 OP_LIVEFROM (op) = from;
78 /*-----------------------------------------------------------------*/
79 /* setToRange - set the range to for an operand */
80 /*-----------------------------------------------------------------*/
82 setToRange (operand * op, int to, bool check)
84 /* only for compiler defined temps */
88 OP_SYMBOL (op)->key = op->key;
89 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
92 OP_SYMBOL (op)->isptr = 1;
102 /*-----------------------------------------------------------------*/
103 /* setFromRange - sets the from range of a given operand */
104 /*-----------------------------------------------------------------*/
106 setLiveFrom (symbol * sym, int from)
108 if (!sym->liveFrom || sym->liveFrom > from)
109 sym->liveFrom = from;
112 /*-----------------------------------------------------------------*/
113 /* setToRange - set the range to for an operand */
114 /*-----------------------------------------------------------------*/
116 setLiveTo (symbol * sym, int to)
118 if (!sym->liveTo || sym->liveTo < to)
122 /*-----------------------------------------------------------------*/
123 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
124 /*-----------------------------------------------------------------*/
126 markLiveRanges (eBBlock ** ebbs, int count)
131 for (i = 0; i < count; i++)
135 for (ic = ebbs[i]->sch; ic; ic = ic->next)
137 if (ic->op == CALL || ic->op == PCALL)
138 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
139 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
141 /* for all iTemps alive at this iCode */
142 for (key = 1; key < ic->rlive->size; key++)
144 if (!bitVectBitValue(ic->rlive, key))
147 sym = hTabItemWithKey(liveRanges, key);
148 setLiveTo(sym, ic->seq);
149 setLiveFrom(sym, ic->seq);
156 /*-----------------------------------------------------------------*/
157 /* markAlive - marks the operand as alive between sic and eic */
158 /*-----------------------------------------------------------------*/
160 markAlive (iCode * sic, iCode * eic, int key)
164 for (dic = sic; dic != eic->next; dic = dic->next)
166 dic->rlive = bitVectSetBit (dic->rlive, key);
170 /*-----------------------------------------------------------------*/
171 /* findNextUseSym - finds the next use of the symbol and marks it */
172 /* alive in between */
173 /*-----------------------------------------------------------------*/
175 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
181 hTabAddItemIfNotP (&liveRanges, sym->key, sym);
184 goto check_successors;
186 /* if we check a complete block and the symbol */
187 /* is alive at the beginning of the block */
188 /* and not defined in the first instructions */
189 /* then a next use exists (return 1) */
190 if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
192 /* check if the first instruction is a def of this op */
193 if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
196 if (IS_ITEMP(IC_RESULT(ic)))
197 if (IC_RESULT(ic)->key == sym->key)
208 /* for all remaining instructions in current block */
209 for (uic = ic; uic; uic = uic->next)
215 if (uic->op == JUMPTABLE)
217 if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
219 markAlive(ic, uic, sym->key);
227 if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
229 markAlive(ic, uic, sym->key);
235 if (IS_ITEMP (IC_LEFT (uic)))
236 if (IC_LEFT (uic)->key == sym->key)
238 markAlive(ic, uic, sym->key);
242 if (IS_ITEMP (IC_RIGHT (uic)))
243 if (IC_RIGHT (uic)->key == sym->key)
245 markAlive (ic, uic, sym->key);
249 if (IS_ITEMP (IC_RESULT (uic)))
250 if (IC_RESULT (uic)->key == sym->key)
252 if (POINTER_SET (uic))
254 markAlive (ic, uic, sym->key);
263 /* check all successors */
266 succ = setFirstItem (ebp->succList);
267 for (; succ; succ = setNextItem (ebp->succList))
269 retval += findNextUseSym (succ, succ->sch, sym);
274 markAlive (ic, ebp->ech, sym->key);
281 /*-----------------------------------------------------------------*/
282 /* findNextUse - finds the next use of the operand and marks it */
283 /* alive in between */
284 /*-----------------------------------------------------------------*/
286 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
289 OP_SYMBOL (op)->isptr = 1;
291 OP_SYMBOL (op)->key = op->key;
293 return findNextUseSym (ebp, ic, OP_SYMBOL(op));
296 /*-----------------------------------------------------------------*/
297 /* unvisitBlocks - clears visited in all blocks */
298 /*-----------------------------------------------------------------*/
299 void unvisitBlocks (eBBlock ** ebbs, int count)
303 for (i = 0; i < count; i++)
304 ebbs[i]->visited = 0;
307 /*-----------------------------------------------------------------*/
308 /* unvisitBlocks - clears visited in all blocks */
309 /*-----------------------------------------------------------------*/
311 incUsed (iCode *ic, operand *op)
314 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
316 OP_SYMBOL (op)->used += 1;
319 /*-----------------------------------------------------------------*/
320 /* rlivePoint - for each point compute the ranges that are alive */
321 /*-----------------------------------------------------------------*/
323 rlivePoint (eBBlock ** ebbs, int count)
329 /* for all blocks do */
330 for (i = 0; i < count; i++)
334 /* for all instructions in this block do */
335 for (ic = ebbs[i]->sch; ic; ic = ic->next)
339 ic->rlive = newBitVect (operandKey);
344 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
346 incUsed (ic, IC_JTCOND(ic));
348 if (!IS_ITEMP(IC_JTCOND(ic)))
351 unvisitBlocks(ebbs, count);
352 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
353 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
358 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
360 incUsed (ic, IC_COND(ic));
362 if (!IS_ITEMP(IC_COND(ic)))
365 unvisitBlocks (ebbs, count);
366 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
367 findNextUse (ebbs[i], ic->next, IC_COND(ic));
372 if (IS_SYMOP(IC_LEFT(ic)))
374 incUsed (ic, IC_LEFT(ic));
375 if (IS_ITEMP(IC_LEFT(ic)))
378 unvisitBlocks(ebbs, count);
379 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
380 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
382 /* if this is a send extend the LR to the call */
386 for (lic = ic; lic; lic = lic->next)
390 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
398 if (IS_SYMOP(IC_RIGHT(ic)))
400 incUsed (ic, IC_RIGHT(ic));
401 if (IS_ITEMP(IC_RIGHT(ic)))
403 unvisitBlocks(ebbs, count);
404 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
405 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
409 if (IS_ITEMP(IC_RESULT(ic)))
411 unvisitBlocks(ebbs, count);
412 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
413 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
416 if (!POINTER_SET(ic) && IC_RESULT(ic))
417 ic->defKey = IC_RESULT(ic)->key;
421 /* check all symbols that are alive in the last instruction */
422 /* but are not alive in all successors */
424 succ = setFirstItem (ebbs[i]->succList);
428 alive = succ->sch->rlive;
429 while ((succ = setNextItem (ebbs[i]->succList)))
431 alive = bitVectIntersect (alive, succ->sch->rlive);
434 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
436 for (key = 1; key < alive->size; key++)
438 if (!bitVectBitValue (alive, key))
441 unvisitBlocks(ebbs, count);
442 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
448 /*-----------------------------------------------------------------*/
449 /* computeClash - find out which live ranges collide with others */
450 /*-----------------------------------------------------------------*/
452 computeClash (eBBlock ** ebbs, int count)
456 /* for all blocks do */
457 for (i = 0; i < count; i++)
461 /* for every iCode do */
462 for (ic = ebbs[i]->sch; ic; ic = ic->next)
467 /* for all iTemps alive at this iCode */
468 for (key1 = 1; key1 < ic->rlive->size; key1++)
470 if (!bitVectBitValue(ic->rlive, key1))
473 sym1 = hTabItemWithKey(liveRanges, key1);
478 /* for all other iTemps alive at this iCode */
479 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
481 if (!bitVectBitValue(ic->rlive, key2))
484 sym2 = hTabItemWithKey(liveRanges, key2);
489 /* if the result and left or right is an iTemp */
490 /* than possibly the iTemps do not clash */
491 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
492 IS_ITEMP(IC_RESULT(ic)) &&
493 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
495 if (OP_SYMBOL(IC_RESULT(ic))->key == key1)
497 if (IS_SYMOP(IC_LEFT(ic)))
498 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
500 if (IS_SYMOP(IC_RIGHT(ic)))
501 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
505 if (OP_SYMBOL(IC_RESULT(ic))->key == key2)
507 if (IS_SYMOP(IC_LEFT(ic)))
508 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
510 if (IS_SYMOP(IC_RIGHT(ic)))
511 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
516 /* the iTemps do clash. set the bits in clashes */
517 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
518 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
520 /* check if they share the same spill location */
521 /* what is this good for? */
522 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
523 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
525 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
526 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
527 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
528 else SYM_SPIL_LOC(sym1)=NULL;
536 /*-----------------------------------------------------------------*/
537 /* allDefsOutOfRange - all definitions are out of a range */
538 /*-----------------------------------------------------------------*/
540 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
547 for (i = 0; i < defs->size; i++)
551 if (bitVectBitValue (defs, i) &&
552 (ic = hTabItemWithKey (iCodehTab, i)) &&
553 (ic->seq >= fseq && ic->seq <= toseq))
562 /*-----------------------------------------------------------------*/
563 /* notUsedInBlock - not used in this block */
564 /*-----------------------------------------------------------------*/
566 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
568 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
569 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
570 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
573 /*-----------------------------------------------------------------*/
574 /* adjustIChain - correct the sch and ech pointers */
575 /*-----------------------------------------------------------------*/
577 adjustIChain (eBBlock ** ebbs, int count)
581 for (i = 0; i < count; i++)
600 /*-----------------------------------------------------------------*/
601 /* computeLiveRanges - computes the live ranges for variables */
602 /*-----------------------------------------------------------------*/
604 computeLiveRanges (eBBlock ** ebbs, int count)
606 /* first look through all blocks and adjust the
607 sch and ech pointers */
608 adjustIChain (ebbs, count);
610 /* sequence the code the live ranges are computed
611 in terms of this sequence additionally the
612 routine will also create a hashtable of instructions */
614 setToNull ((void *) &iCodehTab);
615 iCodehTab = newHashTable (iCodeKey);
616 setToNull ((void *) &iCodeSeqhTab);
617 iCodeSeqhTab = newHashTable (iCodeKey);
618 sequenceiCode (ebbs, count);
620 /* mark the ranges live for each point */
621 setToNull ((void *) &liveRanges);
622 rlivePoint (ebbs, count);
624 /* mark the from & to live ranges for variables used */
625 markLiveRanges (ebbs, count);
627 /* compute which overlaps with what */
628 computeClash(ebbs, count);