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 not then check any of the successor blocks use it */
128 for (i = 0; i < count; ebbs[i++]->visited = 0);
129 if (applyToSet (ebp->succList, isOpAlive, op, ebp, ic))
132 /* this is the last use */
136 /*-----------------------------------------------------------------*/
137 /* unionDefsUsed - unions the defsUsed in a block */
138 /*-----------------------------------------------------------------*/
139 DEFSETFUNC (unionDefsUsed)
142 V_ARG (bitVect **, bvp);
149 *bvp = bitVectUnion (*bvp, ebp->usesDefs);
150 applyToSet (ebp->succList, unionDefsUsed, bvp);
154 /*-----------------------------------------------------------------*/
155 /* setFromRange - sets the from range of a given operand */
156 /*-----------------------------------------------------------------*/
158 setFromRange (operand * op, int from)
160 /* only for compiler defined temporaries */
164 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
167 OP_SYMBOL (op)->isptr = 1;
169 if (!OP_LIVEFROM (op) ||
170 OP_LIVEFROM (op) > from)
171 OP_LIVEFROM (op) = from;
174 /*-----------------------------------------------------------------*/
175 /* setToRange - set the range to for an operand */
176 /*-----------------------------------------------------------------*/
178 setToRange (operand * op, int to, bool check)
180 /* only for compiler defined temps */
184 OP_SYMBOL (op)->key = op->key;
185 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
188 OP_SYMBOL (op)->isptr = 1;
198 /*-----------------------------------------------------------------*/
199 /* firstDeOf - finds the first definition in seq for op */
200 /*-----------------------------------------------------------------*/
202 firstDefOf (operand * op)
205 iCode *ric = NULL, *lic = NULL;
211 for (i = 0; i < OP_DEFS (op)->size; i++)
213 if (bitVectBitValue (OP_DEFS (op), i) &&
214 (lic = hTabItemWithKey (iCodehTab, i)) &&
224 /*-----------------------------------------------------------------*/
225 /* useDefLoopCheck - check for uses before init inside loops */
226 /*-----------------------------------------------------------------*/
228 useDefLoopCheck (operand * op, iCode * ic)
230 /* this is for situations like the following
240 in this case the definition of 'b' will flow to the usages
241 but register allocator cannot handle these situations.so
242 will mark as spilt */
248 /* get the first definition */
249 if (!(tic = firstDefOf (op)))
253 /* now go thru the usages & make sure they follow
254 the first definition */
255 for (i = 0; i <= OP_USES (op)->size; i++)
257 if (bitVectBitValue (OP_USES (op), i) &&
258 (tic = hTabItemWithKey (iCodehTab, i)) &&
266 /* found a usage without definition */
269 if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
272 werror (W_LOCAL_NOINIT,
274 ic->filename, ic->lineno);
279 werror (W_LOCAL_NOINIT,
280 OP_SYMBOL (op)->name,
281 ic->filename, ic->lineno);
283 #if 0 // this will create a segfault: bug #498971
284 OP_SYMBOL (op)->isspilt = 1;
290 /*-----------------------------------------------------------------*/
291 /* operandLUse - check and set the last use for a given operand */
292 /*-----------------------------------------------------------------*/
294 operandLUse (operand * op, eBBlock ** ebbs,
295 int count, iCode * ic, eBBlock * ebp)
297 setFromRange (op, ic->seq);
299 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
301 OP_SYMBOL (op)->used += 1;
303 if (isLastUse (op, ebp, ic->next, ebbs, count) ||
304 (OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
306 int torange = ic->seq;
308 /* if this is a SEND then the toRange should be extended
310 if (ic->op == SEND) {
312 for (lic = ic->next ; lic ; lic = lic->next) {
313 if (lic->op == CALL || lic->op == PCALL) break;
315 /* found it : mark */
316 if (lic) torange = lic->prev->seq;
318 /* if this is the last use then if this block belongs
319 to a loop & some definition comes into the loop
320 then extend the live range to the end of the loop */
322 && hasIncomingDefs (ebp->partOfLoop, op))
324 torange = findLoopEndSeq (ebp->partOfLoop);
327 op = operandFromOperand (op);
328 setToRange (op, torange, FALSE);
330 ic->uses = bitVectSetBit (ic->uses, op->key);
332 if (!OP_SYMBOL (op)->udChked)
334 sym_link *type = operandType (op);
335 sym_link *etype = getSpec (type);
337 OP_SYMBOL (op)->udChked = 1;
338 /* good place to check if unintialised */
339 if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
340 OP_SYMBOL (op)->islocal &&
341 !IS_AGGREGATE (type) &&
343 ic->op != ADDRESS_OF &&
347 if (bitVectIsZero (op->usesDefs) && OP_SYMBOL(op)->ival==NULL)
349 OP_SYMBOL (op)->isspilt = 1;
351 if (OP_SYMBOL (op)->isreqv &&
352 !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
355 werror (W_LOCAL_NOINIT,
357 ic->filename, ic->lineno);
362 werror (W_LOCAL_NOINIT,
363 OP_SYMBOL (op)->name,
364 ic->filename, ic->lineno);
369 if (ebp->depth && op->usesDefs &&
370 !OP_SYMBOL (op)->_isparm)
372 /* check non-inits inside loops */
373 useDefLoopCheck (op, ic);
381 /*-----------------------------------------------------------------*/
382 /* killAllAlive - mark all the definitions living with this seq */
383 /*-----------------------------------------------------------------*/
385 killAllAlive (int seq)
390 for (sym = hTabFirstItem (liveRanges, &k); sym;
391 sym = hTabNextItem (liveRanges, &k))
392 if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
395 /*-----------------------------------------------------------------*/
396 /* defUsedAfterLoop - all definitions & usages before sequence num */
397 /*-----------------------------------------------------------------*/
399 defUsedAfterLoop (operand * op, int seq)
404 /* check for the usages first */
405 if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
407 for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
410 if (bitVectBitValue (OP_SYMBOL (op)->uses, i) && /* usage found */
411 (ic = hTabItemWithKey (iCodehTab, i)) && /* "" */
412 ic->seq > seq) /* & is after the seq */
420 /*-----------------------------------------------------------------*/
421 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
422 /*-----------------------------------------------------------------*/
424 markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
427 bitVect *defsUsed = NULL;
428 bitVect *defsNotUsed = NULL;
430 /* for all the instructions */
431 for (ic = ebp->sch; ic; ic = ic->next)
434 if (ic->op == CALL || ic->op == PCALL)
436 setFromRange (IC_RESULT (ic), ic->seq);
437 /* if the result has no usage then
438 mark this as the end of its life too
439 and take it away from the defs for the block */
440 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
442 setToRange (IC_RESULT (ic), ic->seq, FALSE);
443 bitVectUnSetBit (ebp->defSet, ic->key);
450 /* take care of the special icodes first */
451 if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
453 operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
457 if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
459 operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
463 if (IS_SYMOP (IC_LEFT (ic)))
464 operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
466 if (IS_SYMOP (IC_RIGHT (ic)))
467 operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
469 if (POINTER_SET (ic))
470 operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
471 else if (IC_RESULT (ic))
472 ic->defKey = IC_RESULT (ic)->key;
476 /* for all the definitions in the block */
477 /* compute and set the live from */
478 if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
480 for (i = 0; i < ebp->ldefs->size; i++)
484 if (bitVectBitValue (ebp->ldefs, i) &&
485 (dic = hTabItemWithKey (iCodehTab, i)))
488 /* if the definition has a from & it is greater */
489 /* than the defininng iCode->seq then change it */
490 setFromRange (IC_RESULT (dic), dic->seq);
495 /* special case for lastBlock in a loop: here we
496 mark the end of all the induction variables for the
498 if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
500 for (i = 0; i <= ebp->linds->size; i++)
504 if (bitVectBitValue (ebp->linds, i) &&
505 (dic = hTabItemWithKey (iCodehTab, i)))
508 /* if this is a register equvalent make sure
509 it is not defined or used anywhere after the loop */
510 if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
511 defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
514 setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
519 /* for defnitions coming into the block if they */
520 /* not used by itself & any of its successors */
522 /* first union the definitions used in all successors
524 for (i = 0; i < count; ebbs[i++]->visited = 0);
525 applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
526 defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
528 /* now subract the result of these unions from */
529 /* the incoming definitions this will give the */
530 /* definitions that are never used in the future */
531 defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
534 /* mark the end of the defintions */
535 if (!bitVectIsZero (defsNotUsed) && ebp->sch)
537 for (i = 0; i < defsNotUsed->size; i++)
541 if (bitVectBitValue (defsNotUsed, i) &&
542 (dic = hTabItemWithKey (iCodehTab, i)))
545 setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
551 /* if we reach a lock with noPath to it then kill all
552 the live ranges alive at this point */
553 /* if (ebp->noPath || ebp->entryLabel == returnLabel) */
554 if (ebp->entryLabel == returnLabel)
555 killAllAlive (ebp->fSeq);
558 /*-----------------------------------------------------------------*/
559 /* rlivePoint - for each point compute the ranges that are alive */
560 /*-----------------------------------------------------------------*/
562 rlivePoint (eBBlock ** ebbs, int count)
566 /* for all blocks do */
567 for (i = 0; i < count; i++) {
570 /* for all instruction in the block do */
571 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
575 ic->rlive = newBitVect (operandKey);
576 /* for all symbols in the liverange table */
577 for (lrange = hTabFirstItem (liveRanges, &k); lrange;
578 lrange = hTabNextItem (liveRanges, &k)) {
580 /* if it is live then add the lrange to ic->rlive */
581 if (lrange->liveFrom <= ic->seq &&
582 lrange->liveTo >= ic->seq) {
583 lrange->isLiveFcall |= ((lrange->liveFrom < ic->seq) &&
584 (ic->op == CALL || ic->op == PCALL || ic->op == SEND));
585 if (ic->op == CALL && lrange->liveFrom == ic->seq) continue;
586 ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
590 /* overlapping live ranges should be eliminated */
591 if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
592 if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic)) && /* left & right share the same spil location */
593 OP_SYMBOL(IC_RESULT(ic))->isreqv && /* left of assign is a register requivalent */
594 !OP_SYMBOL(IC_RIGHT(ic))->isreqv && /* right side is not */
595 OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key && /* right side live beyond this point */
596 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 ) { /* left has multiple definitions */
597 SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
605 /*-----------------------------------------------------------------*/
606 /* computeClash - find out which live ranges collide with others */
607 /*-----------------------------------------------------------------*/
608 static void computeClash ()
610 hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
612 symbol *outer, *inner;
615 /* have to make a copy of the liveRanges hashTable :: UGHH .*/
616 for (item = hTabFirstItem(liveRanges,&key); item ;
617 item = hTabNextItem(liveRanges,&key)) {
618 hTabAddItem(&lRangeCopy,key,item);
621 /* outerloop : for each liverange do */
622 for (outer = hTabFirstItem(liveRanges,&key); outer ;
623 outer = hTabNextItem(liveRanges,&key)) {
625 /* if the liveFrom & To are the same then skip,
626 could happen for unused return values from functions */
627 if (outer->liveFrom == outer->liveTo) continue;
629 /* innerloop : for the inner loop we can start from the
630 item after the outer loop */
631 inner = hTabFirstItemWK (lRangeCopy,outer->key);
632 inner = hTabNextItem (lRangeCopy,&key1 );
633 for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
635 if (inner->liveFrom == inner->liveTo) continue;
636 if (inner->liveTo < outer->liveFrom) continue;
637 if (inner->liveFrom > outer->liveTo) continue;
639 /* if one of them are being defined where the other
640 one end , then no overlap (i.e. they can goto same registers */
641 if (inner->liveFrom == outer->liveTo ||
642 outer->liveFrom == inner->liveTo) continue;
644 /* so they overlap : set both their clashes */
645 inner->clashes = bitVectSetBit(inner->clashes,outer->key);
646 outer->clashes = bitVectSetBit(outer->clashes,inner->key);
648 /* check if they share the same spillocation */
649 if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
650 SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
651 if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
652 else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
653 else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
654 else SYM_SPIL_LOC(inner)=NULL;
661 /*-----------------------------------------------------------------*/
662 /* allDefsOutOfRange - all definitions are out of a range */
663 /*-----------------------------------------------------------------*/
665 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
672 for (i = 0; i < defs->size; i++)
676 if (bitVectBitValue (defs, i) &&
677 (ic = hTabItemWithKey (iCodehTab, i)) &&
678 (ic->seq >= fseq && ic->seq <= toseq))
687 /*-----------------------------------------------------------------*/
688 /* notUsedInBlock - not used in this block */
689 /*-----------------------------------------------------------------*/
691 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
693 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
694 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
695 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
699 /*-----------------------------------------------------------------*/
700 /* computeLiveRanges - computes the live ranges for variables */
701 /*-----------------------------------------------------------------*/
703 computeLiveRanges (eBBlock ** ebbs, int count)
706 /* sequence the code the live ranges are computed
707 in terms of this sequence additionally the
708 routine will also create a hashtable of instructions */
710 setToNull ((void **) &iCodehTab);
711 iCodehTab = newHashTable (iCodeKey);
712 setToNull ((void **) &iCodeSeqhTab);
713 iCodeSeqhTab = newHashTable (iCodeKey);
714 sequenceiCode (ebbs, count);
716 /* call routine to mark the from & to live ranges for
718 setToNull ((void **) &liveRanges);
719 for (i = 0; i < count; i++)
720 markLiveRanges (ebbs[i], ebbs, count);
722 /* mark the ranges live for each point */
723 rlivePoint (ebbs, count);
725 /* compute which overlaps with what */