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)
225 /* for all remaining instructions in current block */
226 for (uic = ic; uic; uic = uic->next)
232 if (uic->op == JUMPTABLE)
234 if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
236 markAlive(ic, uic, sym->key);
244 if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
246 markAlive(ic, uic, sym->key);
252 if (IS_ITEMP (IC_LEFT (uic)))
253 if (IC_LEFT (uic)->key == sym->key)
255 markAlive(ic, uic, sym->key);
259 if (IS_ITEMP (IC_RIGHT (uic)))
260 if (IC_RIGHT (uic)->key == sym->key)
262 markAlive (ic, uic, sym->key);
266 if (IS_ITEMP (IC_RESULT (uic)))
267 if (IC_RESULT (uic)->key == sym->key)
269 if (POINTER_SET (uic))
271 markAlive (ic, uic, sym->key);
280 /* check all successors */
283 succ = setFirstItem (ebp->succList);
284 for (; succ; succ = setNextItem (ebp->succList))
286 retval += findNextUseSym (succ, succ->sch, sym);
291 if (ic) markAlive (ic, ebp->ech, sym->key);
298 /*-----------------------------------------------------------------*/
299 /* findNextUse - finds the next use of the operand and marks it */
300 /* alive in between */
301 /*-----------------------------------------------------------------*/
303 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
306 OP_SYMBOL (op)->isptr = 1;
308 OP_SYMBOL (op)->key = op->key;
310 return findNextUseSym (ebp, ic, OP_SYMBOL(op));
313 /*-----------------------------------------------------------------*/
314 /* unvisitBlocks - clears visited in all blocks */
315 /*-----------------------------------------------------------------*/
316 void unvisitBlocks (eBBlock ** ebbs, int count)
320 for (i = 0; i < count; i++)
321 ebbs[i]->visited = 0;
324 /*-----------------------------------------------------------------*/
325 /* unvisitBlocks - clears visited in all blocks */
326 /*-----------------------------------------------------------------*/
328 incUsed (iCode *ic, operand *op)
331 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
333 OP_SYMBOL (op)->used += 1;
336 /*-----------------------------------------------------------------*/
337 /* rliveClear - clears the rlive bitVectors */
338 /*-----------------------------------------------------------------*/
340 rliveClear (eBBlock ** ebbs, int count)
344 /* for all blocks do */
345 for (i = 0; i < count; i++)
349 /* for all instructions in this block do */
350 for (ic = ebbs[i]->sch; ic; ic = ic->next)
352 freeBitVect (ic->rlive);
358 /*-----------------------------------------------------------------*/
359 /* rlivePoint - for each point compute the ranges that are alive */
360 /*-----------------------------------------------------------------*/
362 rlivePoint (eBBlock ** ebbs, int count)
368 /* for all blocks do */
369 for (i = 0; i < count; i++)
373 /* for all instructions in this block do */
374 for (ic = ebbs[i]->sch; ic; ic = ic->next)
378 ic->rlive = newBitVect (operandKey);
383 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
385 incUsed (ic, IC_JTCOND(ic));
387 if (!IS_ITEMP(IC_JTCOND(ic)))
390 unvisitBlocks(ebbs, count);
391 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
392 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
397 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
399 incUsed (ic, IC_COND(ic));
401 if (!IS_ITEMP(IC_COND(ic)))
404 unvisitBlocks (ebbs, count);
405 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
406 findNextUse (ebbs[i], ic->next, IC_COND(ic));
411 if (IS_SYMOP(IC_LEFT(ic)))
413 incUsed (ic, IC_LEFT(ic));
414 if (IS_ITEMP(IC_LEFT(ic)))
417 unvisitBlocks(ebbs, count);
418 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
419 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
421 /* if this is a send extend the LR to the call */
425 for (lic = ic; lic; lic = lic->next)
427 if (lic->op == CALL || lic->op == PCALL)
429 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
437 if (IS_SYMOP(IC_RIGHT(ic)))
439 incUsed (ic, IC_RIGHT(ic));
440 if (IS_ITEMP(IC_RIGHT(ic)))
442 unvisitBlocks(ebbs, count);
443 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
444 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
448 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
449 incUsed (ic, IC_RESULT(ic));
451 if (IS_ITEMP(IC_RESULT(ic)))
453 unvisitBlocks(ebbs, count);
454 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
455 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
458 if (!POINTER_SET(ic) && IC_RESULT(ic))
459 ic->defKey = IC_RESULT(ic)->key;
463 /* check all symbols that are alive in the last instruction */
464 /* but are not alive in all successors */
466 succ = setFirstItem (ebbs[i]->succList);
470 alive = succ->sch->rlive;
471 while ((succ = setNextItem (ebbs[i]->succList)))
474 alive = bitVectIntersect (alive, succ->sch->rlive);
478 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
480 for (key = 1; key < alive->size; key++)
482 if (!bitVectBitValue (alive, key))
485 unvisitBlocks(ebbs, count);
486 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
492 /*-----------------------------------------------------------------*/
493 /* computeClash - find out which live ranges collide with others */
494 /*-----------------------------------------------------------------*/
496 computeClash (eBBlock ** ebbs, int count)
500 /* for all blocks do */
501 for (i = 0; i < count; i++)
505 /* for every iCode do */
506 for (ic = ebbs[i]->sch; ic; ic = ic->next)
511 /* for all iTemps alive at this iCode */
512 for (key1 = 1; key1 < ic->rlive->size; key1++)
514 if (!bitVectBitValue(ic->rlive, key1))
517 sym1 = hTabItemWithKey(liveRanges, key1);
522 /* for all other iTemps alive at this iCode */
523 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
525 if (!bitVectBitValue(ic->rlive, key2))
528 sym2 = hTabItemWithKey(liveRanges, key2);
533 /* if the result and left or right is an iTemp */
534 /* than possibly the iTemps do not clash */
535 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
536 IS_ITEMP(IC_RESULT(ic)) &&
537 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
539 if (OP_SYMBOL(IC_RESULT(ic))->key == key1
540 && sym1->liveFrom == ic->seq
541 && sym2->liveTo == ic->seq)
543 if (IS_SYMOP(IC_LEFT(ic)))
544 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
546 if (IS_SYMOP(IC_RIGHT(ic)))
547 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
551 if (OP_SYMBOL(IC_RESULT(ic))->key == key2
552 && sym2->liveFrom == ic->seq
553 && sym1->liveTo == ic->seq)
555 if (IS_SYMOP(IC_LEFT(ic)))
556 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
558 if (IS_SYMOP(IC_RIGHT(ic)))
559 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
564 /* the iTemps do clash. set the bits in clashes */
565 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
566 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
568 /* check if they share the same spill location */
569 /* what is this good for? */
570 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
571 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
573 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
574 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
575 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
576 else SYM_SPIL_LOC(sym1)=NULL;
584 /*-----------------------------------------------------------------*/
585 /* allDefsOutOfRange - all definitions are out of a range */
586 /*-----------------------------------------------------------------*/
588 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
595 for (i = 0; i < defs->size; i++)
599 if (bitVectBitValue (defs, i) &&
600 (ic = hTabItemWithKey (iCodehTab, i)) &&
601 (ic->seq >= fseq && ic->seq <= toseq))
610 /*-----------------------------------------------------------------*/
611 /* notUsedInBlock - not used in this block */
612 /*-----------------------------------------------------------------*/
614 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
616 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
617 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
618 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
621 /*-----------------------------------------------------------------*/
622 /* adjustIChain - correct the sch and ech pointers */
623 /*-----------------------------------------------------------------*/
625 adjustIChain (eBBlock ** ebbs, int count)
629 for (i = 0; i < count; i++)
638 /* is there any code for this eBBlock? (e.g. ROM assignment) */
652 /*-----------------------------------------------------------------*/
653 /* computeLiveRanges - computes the live ranges for variables */
654 /*-----------------------------------------------------------------*/
656 computeLiveRanges (eBBlock ** ebbs, int count)
658 /* first look through all blocks and adjust the
659 sch and ech pointers */
660 adjustIChain (ebbs, count);
662 /* sequence the code the live ranges are computed
663 in terms of this sequence additionally the
664 routine will also create a hashtable of instructions */
666 setToNull ((void *) &iCodehTab);
667 iCodehTab = newHashTable (iCodeKey);
668 hashiCodeKeys (ebbs, count);
669 setToNull ((void *) &iCodeSeqhTab);
670 iCodeSeqhTab = newHashTable (iCodeKey);
671 sequenceiCode (ebbs, count);
673 /* mark the ranges live for each point */
674 setToNull ((void *) &liveRanges);
675 rlivePoint (ebbs, count);
677 /* mark the from & to live ranges for variables used */
678 markLiveRanges (ebbs, count);
680 /* compute which overlaps with what */
681 computeClash(ebbs, count);
684 /*-----------------------------------------------------------------*/
685 /* recomputeLiveRanges - recomputes the live ranges for variables */
686 /*-----------------------------------------------------------------*/
688 recomputeLiveRanges (eBBlock ** ebbs, int count)
693 /* clear all rlive bitVectors */
694 rliveClear (ebbs, count);
696 sym = hTabFirstItem (liveRanges, &key);
703 freeBitVect (sym->clashes);
705 } while ( (sym = hTabNextItem (liveRanges, &key)));
708 /* do the LR computation again */
709 computeLiveRanges (ebbs, count);