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 /* markVisited - will set the visited flag for the given Block */
60 /*-----------------------------------------------------------------*/
61 DEFSETFUNC (markVisited)
68 applyToSet (ebp->succList, markVisited);
72 /*-----------------------------------------------------------------*/
73 /* isOpAlive - checks to see if the usage in this block is the */
74 /* uses the same definitions as this one */
75 /*-----------------------------------------------------------------*/
76 DEFSETFUNC (isOpAlive)
79 V_ARG (operand *, op);
80 V_ARG (eBBlock *, orig);
88 /* if we have reached the originating block */
89 /* or this block has some definiton for it */
90 /* then check if it is used between start & */
93 bitVectBitsInCommon (OP_DEFS (op), ebp->defSet))
94 if (usedBetweenPoints (op, ebp->sch, ic))
98 applyToSet (ebp->succList, markVisited);
102 /* choosing this more expensive one since
103 killDeadCode will take away some definitions
104 but there is not way right now to take away
105 the usage information for the corresponding
106 usages, this will lead to longer live ranges */
107 if (usedInRemaining (op, ebp->sch))
111 return (applyToSet (ebp->succList, isOpAlive, op, orig, ic));
114 /*-----------------------------------------------------------------*/
115 /* isLastUse - return TRUE if no usage of this operand after this */
116 /*-----------------------------------------------------------------*/
118 isLastUse (operand * op, eBBlock * ebp, iCode * ic,
119 eBBlock ** ebbs, int count)
123 /* if this is used in the remaining */
124 if (usedInRemaining (op, ic))
127 if (getenv ("SDCC_LRKLAUS"))
129 /* if not then check any of the following blocks use it */
130 for (i = 0; i < count; i++)
132 if (ebbs[i]->fSeq <= ebp->fSeq)
134 if (usedInRemaining (op, ebbs[i]->sch))
140 /* if not then check any of the successor blocks use it */
141 for (i = 0; i < count;)
142 ebbs[i++]->visited = 0;
143 if (applyToSet (ebp->succList, isOpAlive, op, ebp, ic))
147 /* this is the last use */
151 /*-----------------------------------------------------------------*/
152 /* unionDefsUsed - unions the defsUsed in a block */
153 /*-----------------------------------------------------------------*/
154 DEFSETFUNC (unionDefsUsed)
157 V_ARG (bitVect **, bvp);
164 *bvp = bitVectUnion (*bvp, ebp->usesDefs);
165 applyToSet (ebp->succList, unionDefsUsed, bvp);
169 /*-----------------------------------------------------------------*/
170 /* setFromRange - sets the from range of a given operand */
171 /*-----------------------------------------------------------------*/
173 setFromRange (operand * op, int from)
175 /* only for compiler defined temporaries */
179 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
182 OP_SYMBOL (op)->isptr = 1;
184 if (!OP_LIVEFROM (op) ||
185 OP_LIVEFROM (op) > from)
186 OP_LIVEFROM (op) = from;
189 /*-----------------------------------------------------------------*/
190 /* setToRange - set the range to for an operand */
191 /*-----------------------------------------------------------------*/
193 setToRange (operand * op, int to, bool check)
195 /* only for compiler defined temps */
199 OP_SYMBOL (op)->key = op->key;
200 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
203 OP_SYMBOL (op)->isptr = 1;
213 /*-----------------------------------------------------------------*/
214 /* firstDeOf - finds the first definition in seq for op */
215 /*-----------------------------------------------------------------*/
217 firstDefOf (operand * op)
220 iCode *ric = NULL, *lic = NULL;
226 for (i = 0; i < OP_DEFS (op)->size; i++)
228 if (bitVectBitValue (OP_DEFS (op), i) &&
229 (lic = hTabItemWithKey (iCodehTab, i)) &&
239 /*-----------------------------------------------------------------*/
240 /* useDefLoopCheck - check for uses before init inside loops */
241 /*-----------------------------------------------------------------*/
243 useDefLoopCheck (operand * op, iCode * ic)
245 /* this is for situations like the following
255 in this case the definition of 'b' will flow to the usages
256 but register allocator cannot handle these situations.so
257 will mark as spilt */
263 /* get the first definition */
264 if (!(tic = firstDefOf (op)))
268 /* now go thru the usages & make sure they follow
269 the first definition */
270 for (i = 0; i <= OP_USES (op)->size; i++)
272 if (bitVectBitValue (OP_USES (op), i) &&
273 (tic = hTabItemWithKey (iCodehTab, i)) &&
281 /* found a usage without definition */
284 if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
287 werror (W_LOCAL_NOINIT,
289 ic->filename, ic->lineno);
294 werror (W_LOCAL_NOINIT,
295 OP_SYMBOL (op)->name,
296 ic->filename, ic->lineno);
298 #if 0 // this will create a segfault: bug #498971
299 OP_SYMBOL (op)->isspilt = 1;
305 /*-----------------------------------------------------------------*/
306 /* operandLUse - check and set the last use for a given operand */
307 /*-----------------------------------------------------------------*/
309 operandLUse (operand * op, eBBlock ** ebbs,
310 int count, iCode * ic, eBBlock * ebp)
312 setFromRange (op, ic->seq);
314 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
316 OP_SYMBOL (op)->used += 1;
318 if (isLastUse (op, ebp, ic->next, ebbs, count) ||
319 (OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
321 int torange = ic->seq;
323 /* if this is a SEND then the toRange should be extended
328 for (lic = ic->next ; lic ; lic = lic->next)
330 if (lic->op == CALL || lic->op == PCALL)
333 /* found it : mark */
335 torange = lic->prev->seq;
337 /* if this is the last use then if this block belongs
338 to a loop & some definition comes into the loop
339 then extend the live range to the end of the loop */
340 if (getenv ("SDCC_LRKLAUS"))
342 if (ebp->KpartOfLoop)
346 aloop = setFirstItem (ebp->KpartOfLoop);
347 for (; aloop; aloop = setNextItem (ebp->KpartOfLoop))
349 if (hasIncomingDefs (aloop, op))
350 torange = findLoopEndSeq (aloop);
357 && hasIncomingDefs (ebp->partOfLoop, op))
359 torange = findLoopEndSeq (ebp->partOfLoop);
363 op = operandFromOperand (op);
364 setToRange (op, torange, FALSE);
366 ic->uses = bitVectSetBit (ic->uses, op->key);
368 if (!OP_SYMBOL (op)->udChked)
370 sym_link *type = operandType (op);
371 sym_link *etype = getSpec (type);
373 OP_SYMBOL (op)->udChked = 1;
374 /* good place to check if unintialised */
375 if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
376 OP_SYMBOL (op)->islocal &&
377 !IS_AGGREGATE (type) &&
379 ic->op != ADDRESS_OF &&
383 if (bitVectIsZero (op->usesDefs) && OP_SYMBOL(op)->ival==NULL)
385 OP_SYMBOL (op)->isspilt = 1;
387 if (OP_SYMBOL (op)->isreqv &&
388 !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
391 werror (W_LOCAL_NOINIT,
393 ic->filename, ic->lineno);
398 werror (W_LOCAL_NOINIT,
399 OP_SYMBOL (op)->name,
400 ic->filename, ic->lineno);
405 if (ebp->depth && op->usesDefs &&
406 !OP_SYMBOL (op)->_isparm)
408 /* check non-inits inside loops */
409 useDefLoopCheck (op, ic);
417 /*-----------------------------------------------------------------*/
418 /* killAllAlive - mark all the definitions living with this seq */
419 /*-----------------------------------------------------------------*/
421 killAllAlive (int seq)
426 for (sym = hTabFirstItem (liveRanges, &k); sym;
427 sym = hTabNextItem (liveRanges, &k))
428 if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
431 /*-----------------------------------------------------------------*/
432 /* defUsedAfterLoop - all definitions & usages before sequence num */
433 /*-----------------------------------------------------------------*/
435 defUsedAfterLoop (operand * op, int seq)
440 /* check for the usages first */
441 if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
443 for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
446 if (bitVectBitValue (OP_SYMBOL (op)->uses, i) && /* usage found */
447 (ic = hTabItemWithKey (iCodehTab, i)) && /* "" */
448 ic->seq > seq) /* & is after the seq */
456 /*-----------------------------------------------------------------*/
457 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
458 /*-----------------------------------------------------------------*/
460 markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
463 bitVect *defsUsed = NULL;
464 bitVect *defsNotUsed = NULL;
467 /* for all the instructions */
468 for (ic = ebp->sch; ic; ic = ic->next)
470 if (ic->op == CALL || ic->op == PCALL)
472 setFromRange (IC_RESULT (ic), ic->seq);
473 /* if the result has no usage then
474 mark this as the end of its life too
475 and take it away from the defs for the block */
476 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
478 setToRange (IC_RESULT (ic), ic->seq, FALSE);
479 bitVectUnSetBit (ebp->defSet, ic->key);
486 /* take care of the special icodes first */
487 if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
489 operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
493 if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
495 operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
499 if (IS_SYMOP (IC_LEFT (ic)))
500 operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
502 if (IS_SYMOP (IC_RIGHT (ic)))
503 operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
505 if (POINTER_SET (ic))
506 operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
507 else if (IC_RESULT (ic))
508 ic->defKey = IC_RESULT (ic)->key;
512 /* for all the definitions in the block */
513 /* compute and set the live from */
514 if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
516 for (i = 0; i < ebp->ldefs->size; i++)
520 if (bitVectBitValue (ebp->ldefs, i) &&
521 (dic = hTabItemWithKey (iCodehTab, i)))
524 /* if the definition has a from & it is greater */
525 /* than the defininng iCode->seq then change it */
526 setFromRange (IC_RESULT (dic), dic->seq);
531 /* special case for lastBlock in a loop: here we
532 mark the end of all the induction variables for the
534 if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
536 for (i = 0; i <= ebp->linds->size; i++)
540 if (bitVectBitValue (ebp->linds, i) &&
541 (dic = hTabItemWithKey (iCodehTab, i)))
544 /* if this is a register equvalent make sure
545 it is not defined or used anywhere after the loop */
546 if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
547 defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
550 setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
555 /* for defnitions coming into the block if they */
556 /* not used by itself & any of its successors */
558 /* first union the definitions used in all successors
560 for (i = 0; i < count; ebbs[i++]->visited = 0);
561 applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
562 defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
564 /* now subract the result of these unions from */
565 /* the incoming definitions this will give the */
566 /* definitions that are never used in the future */
567 defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
570 /* mark the end of the defintions */
571 if (!bitVectIsZero (defsNotUsed) && ebp->sch)
573 for (i = 0; i < defsNotUsed->size; i++)
577 if (bitVectBitValue (defsNotUsed, i) &&
578 (dic = hTabItemWithKey (iCodehTab, i)))
580 setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
586 /* if we reach a lock with noPath to it then kill all
587 the live ranges alive at this point */
588 /* if (ebp->noPath || ebp->entryLabel == returnLabel) */
589 if (ebp->entryLabel == returnLabel)
590 killAllAlive (ebp->fSeq);
593 /*-----------------------------------------------------------------*/
594 /* rlivePoint - for each point compute the ranges that are alive */
595 /*-----------------------------------------------------------------*/
597 rlivePoint (eBBlock ** ebbs, int count)
601 /* for all blocks do */
602 for (i = 0; i < count; i++) {
605 /* for all instruction in the block do */
606 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
610 ic->rlive = newBitVect (operandKey);
611 /* for all symbols in the liverange table */
612 for (lrange = hTabFirstItem (liveRanges, &k); lrange;
613 lrange = hTabNextItem (liveRanges, &k)) {
615 /* if it is live then add the lrange to ic->rlive */
616 if (lrange->liveFrom <= ic->seq &&
617 lrange->liveTo >= ic->seq) {
618 lrange->isLiveFcall |= ((lrange->liveFrom < ic->seq) &&
619 (ic->op == CALL || ic->op == PCALL || ic->op == SEND));
620 if (ic->op == CALL && lrange->liveFrom == ic->seq) continue;
621 ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
625 /* overlapping live ranges should be eliminated */
626 if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
627 if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic)) && /* left & right share the same spil location */
628 OP_SYMBOL(IC_RESULT(ic))->isreqv && /* left of assign is a register requivalent */
629 !OP_SYMBOL(IC_RIGHT(ic))->isreqv && /* right side is not */
630 OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key && /* right side live beyond this point */
631 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 ) { /* left has multiple definitions */
632 SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
640 /*-----------------------------------------------------------------*/
641 /* computeClash - find out which live ranges collide with others */
642 /*-----------------------------------------------------------------*/
643 static void computeClash ()
645 hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
647 symbol *outer, *inner;
650 /* have to make a copy of the liveRanges hashTable :: UGHH .*/
651 for (item = hTabFirstItem(liveRanges,&key); item ;
652 item = hTabNextItem(liveRanges,&key)) {
653 hTabAddItem(&lRangeCopy,key,item);
656 /* outerloop : for each liverange do */
657 for (outer = hTabFirstItem(liveRanges,&key); outer ;
658 outer = hTabNextItem(liveRanges,&key)) {
660 /* if the liveFrom & To are the same then skip,
661 could happen for unused return values from functions */
662 if (outer->liveFrom == outer->liveTo) continue;
664 /* innerloop : for the inner loop we can start from the
665 item after the outer loop */
666 inner = hTabFirstItemWK (lRangeCopy,outer->key);
667 inner = hTabNextItem (lRangeCopy,&key1 );
668 for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
670 if (inner->liveFrom == inner->liveTo) continue;
671 if (inner->liveTo < outer->liveFrom) continue;
672 if (inner->liveFrom > outer->liveTo) continue;
674 /* if one of them are being defined where the other
675 one end , then no overlap (i.e. they can goto same registers */
676 if (inner->liveFrom == outer->liveTo ||
677 outer->liveFrom == inner->liveTo) continue;
679 /* so they overlap : set both their clashes */
680 inner->clashes = bitVectSetBit(inner->clashes,outer->key);
681 outer->clashes = bitVectSetBit(outer->clashes,inner->key);
683 /* check if they share the same spillocation */
684 if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
685 SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
686 if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
687 else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
688 else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
689 else SYM_SPIL_LOC(inner)=NULL;
696 /*-----------------------------------------------------------------*/
697 /* allDefsOutOfRange - all definitions are out of a range */
698 /*-----------------------------------------------------------------*/
700 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
707 for (i = 0; i < defs->size; i++)
711 if (bitVectBitValue (defs, i) &&
712 (ic = hTabItemWithKey (iCodehTab, i)) &&
713 (ic->seq >= fseq && ic->seq <= toseq))
722 /*-----------------------------------------------------------------*/
723 /* notUsedInBlock - not used in this block */
724 /*-----------------------------------------------------------------*/
726 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
728 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
729 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
730 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
734 /*-----------------------------------------------------------------*/
735 /* computeLiveRanges - computes the live ranges for variables */
736 /*-----------------------------------------------------------------*/
738 computeLiveRanges (eBBlock ** ebbs, int count)
741 /* sequence the code the live ranges are computed
742 in terms of this sequence additionally the
743 routine will also create a hashtable of instructions */
745 setToNull ((void *) &iCodehTab);
746 iCodehTab = newHashTable (iCodeKey);
747 setToNull ((void *) &iCodeSeqhTab);
748 iCodeSeqhTab = newHashTable (iCodeKey);
749 sequenceiCode (ebbs, count);
751 if (getenv ("SDCC_LRKLAUS"))
753 /* add blocks between loop blocks as part of that loop */
754 addLoopBlocks (ebbs, count);
757 /* call routine to mark the from & to live ranges for
759 setToNull ((void *) &liveRanges);
760 for (i = 0; i < count; i++)
761 markLiveRanges (ebbs[i], ebbs, count);
763 /* mark the ranges live for each point */
764 rlivePoint (ebbs, count);
766 /* compute which overlaps with what */