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 OP_SYMBOL (op)->isspilt = 1;
288 /*-----------------------------------------------------------------*/
289 /* operandLUse - check and set the last use for a given operand */
290 /*-----------------------------------------------------------------*/
292 operandLUse (operand * op, eBBlock ** ebbs,
293 int count, iCode * ic, eBBlock * ebp)
295 setFromRange (op, ic->seq);
297 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
299 OP_SYMBOL (op)->used += 1;
301 if (isLastUse (op, ebp, ic->next, ebbs, count) ||
302 (OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
304 int torange = ic->seq;
306 /* if this is a SEND then the toRange should be extended
308 if (ic->op == SEND) {
310 for (lic = ic->next ; lic ; lic = lic->next) {
311 if (lic->op == CALL || lic->op == PCALL) break;
313 /* found it : mark */
314 if (lic) torange = lic->prev->seq;
316 /* if this is the last use then if this block belongs
317 to a loop & some definition comes into the loop
318 then extend the live range to the end of the loop */
320 && hasIncomingDefs (ebp->partOfLoop, op))
322 torange = findLoopEndSeq (ebp->partOfLoop);
325 op = operandFromOperand (op);
326 setToRange (op, torange, FALSE);
328 ic->uses = bitVectSetBit (ic->uses, op->key);
330 if (!OP_SYMBOL (op)->udChked)
332 sym_link *type = operandType (op);
333 sym_link *etype = getSpec (type);
335 OP_SYMBOL (op)->udChked = 1;
336 /* good place to check if unintialised */
337 if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
338 OP_SYMBOL (op)->islocal &&
339 !IS_AGGREGATE (type) &&
341 ic->op != ADDRESS_OF &&
345 if (bitVectIsZero (op->usesDefs))
347 OP_SYMBOL (op)->isspilt = 1;
349 if (OP_SYMBOL (op)->isreqv &&
350 !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
353 werror (W_LOCAL_NOINIT,
355 ic->filename, ic->lineno);
360 werror (W_LOCAL_NOINIT,
361 OP_SYMBOL (op)->name,
362 ic->filename, ic->lineno);
367 if (ebp->depth && op->usesDefs &&
368 !OP_SYMBOL (op)->_isparm)
370 /* check non-inits inside loops */
371 useDefLoopCheck (op, ic);
379 /*-----------------------------------------------------------------*/
380 /* killAllAlive - mark all the definitions living with this seq */
381 /*-----------------------------------------------------------------*/
383 killAllAlive (int seq)
388 for (sym = hTabFirstItem (liveRanges, &k); sym;
389 sym = hTabNextItem (liveRanges, &k))
390 if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
393 /*-----------------------------------------------------------------*/
394 /* defUsedAfterLoop - all definitions & usages before sequence num */
395 /*-----------------------------------------------------------------*/
397 defUsedAfterLoop (operand * op, int seq)
402 /* check for the usages first */
403 if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
405 for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
408 if (bitVectBitValue (OP_SYMBOL (op)->uses, i) && /* usage found */
409 (ic = hTabItemWithKey (iCodehTab, i)) && /* "" */
410 ic->seq > seq) /* & is after the seq */
418 /*-----------------------------------------------------------------*/
419 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
420 /*-----------------------------------------------------------------*/
422 markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
425 bitVect *defsUsed = NULL;
426 bitVect *defsNotUsed = NULL;
428 /* for all the instructions */
429 for (ic = ebp->sch; ic; ic = ic->next)
432 if (ic->op == CALL || ic->op == PCALL)
434 setFromRange (IC_RESULT (ic), ic->seq);
435 /* if the result has no usage then
436 mark this as the end of its life too
437 and take it away from the defs for the block */
438 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
440 setToRange (IC_RESULT (ic), ic->seq, FALSE);
441 bitVectUnSetBit (ebp->defSet, ic->key);
448 /* take care of the special icodes first */
449 if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
451 operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
455 if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
457 operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
461 if (IS_SYMOP (IC_LEFT (ic)))
462 operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
464 if (IS_SYMOP (IC_RIGHT (ic)))
465 operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
467 if (POINTER_SET (ic))
468 operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
469 else if (IC_RESULT (ic))
470 ic->defKey = IC_RESULT (ic)->key;
474 /* for all the definitions in the block */
475 /* compute and set the live from */
476 if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
478 for (i = 0; i < ebp->ldefs->size; i++)
482 if (bitVectBitValue (ebp->ldefs, i) &&
483 (dic = hTabItemWithKey (iCodehTab, i)))
486 /* if the definition has a from & it is greater */
487 /* than the defininng iCode->seq then change it */
488 setFromRange (IC_RESULT (dic), dic->seq);
493 /* special case for lastBlock in a loop: here we
494 mark the end of all the induction variables for the
496 if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
498 for (i = 0; i <= ebp->linds->size; i++)
502 if (bitVectBitValue (ebp->linds, i) &&
503 (dic = hTabItemWithKey (iCodehTab, i)))
506 /* if this is a register equvalent make sure
507 it is not defined or used anywhere after the loop */
508 if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
509 defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
512 setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
517 /* for defnitions coming into the block if they */
518 /* not used by itself & any of its successors */
520 /* first union the definitions used in all successors
522 for (i = 0; i < count; ebbs[i++]->visited = 0);
523 applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
524 defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
526 /* now subract the result of these unions from */
527 /* the incoming definitions this will give the */
528 /* definitions that are never used in the future */
529 defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
532 /* mark the end of the defintions */
533 if (!bitVectIsZero (defsNotUsed) && ebp->sch)
535 for (i = 0; i < defsNotUsed->size; i++)
539 if (bitVectBitValue (defsNotUsed, i) &&
540 (dic = hTabItemWithKey (iCodehTab, i)))
543 setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
549 /* if we reach a lock with noPath to it then kill all
550 the live ranges alive at this point */
551 /* if (ebp->noPath || ebp->entryLabel == returnLabel) */
552 if (ebp->entryLabel == returnLabel)
553 killAllAlive (ebp->fSeq);
556 /*-----------------------------------------------------------------*/
557 /* rlivePoint - for each point compute the ranges that are alive */
558 /*-----------------------------------------------------------------*/
560 rlivePoint (eBBlock ** ebbs, int count)
564 /* for all blocks do */
565 for (i = 0; i < count; i++) {
568 /* for all instruction in the block do */
569 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
573 ic->rlive = newBitVect (operandKey);
574 /* for all symbols in the liverange table */
575 for (lrange = hTabFirstItem (liveRanges, &k); lrange;
576 lrange = hTabNextItem (liveRanges, &k)) {
578 /* if it is live then add the lrange to ic->rlive */
579 if (lrange->liveFrom <= ic->seq &&
580 lrange->liveTo >= ic->seq) {
581 lrange->isLiveFcall |= (ic->op == CALL || ic->op == PCALL || ic->op == SEND);
582 ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
586 /* overlapping live ranges should be eliminated */
587 if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
588 if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic)) && /* left & right share the same spil location */
589 OP_SYMBOL(IC_RESULT(ic))->isreqv && /* left of assign is a register requivalent */
590 !OP_SYMBOL(IC_RIGHT(ic))->isreqv && /* right side is not */
591 OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key && /* right side live beyond this point */
592 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 ) { /* left has multiple definitions */
593 SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
601 /*-----------------------------------------------------------------*/
602 /* computeClash - find out which live ranges collide with others */
603 /*-----------------------------------------------------------------*/
604 static void computeClash ()
606 hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
608 symbol *outer, *inner;
611 /* have to make a copy of the liveRanges hashTable :: UGHH .*/
612 for (item = hTabFirstItem(liveRanges,&key); item ;
613 item = hTabNextItem(liveRanges,&key)) {
614 hTabAddItem(&lRangeCopy,key,item);
617 /* outerloop : for each liverange do */
618 for (outer = hTabFirstItem(liveRanges,&key); outer ;
619 outer = hTabNextItem(liveRanges,&key)) {
621 /* if the liveFrom & To are the same then skip,
622 could happen for unused return values from functions */
623 if (outer->liveFrom == outer->liveTo) continue;
625 /* innerloop : for the inner loop we can start from the
626 item after the outer loop */
627 inner = hTabFirstItemWK (lRangeCopy,outer->key);
628 inner = hTabNextItem (lRangeCopy,&key1 );
629 for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
631 if (inner->liveFrom == inner->liveTo) continue;
632 if (inner->liveTo < outer->liveFrom) continue;
633 if (inner->liveFrom > outer->liveTo) continue;
635 /* if one of them are being defined where the other
636 one end , then no overlap (i.e. they can goto same registers */
637 if (inner->liveFrom == outer->liveTo ||
638 outer->liveFrom == inner->liveTo) continue;
640 /* so they overlap : set both their clashes */
641 inner->clashes = bitVectSetBit(inner->clashes,outer->key);
642 outer->clashes = bitVectSetBit(outer->clashes,inner->key);
644 /* check if they share the same spillocation */
645 if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
646 SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
647 if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
648 else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
649 else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
650 else SYM_SPIL_LOC(inner)=NULL;
657 /*-----------------------------------------------------------------*/
658 /* computeLiveRanges - computes the live ranges for variables */
659 /*-----------------------------------------------------------------*/
661 computeLiveRanges (eBBlock ** ebbs, int count)
664 /* sequence the code the live ranges are computed
665 in terms of this sequence additionally the
666 routine will also create a hashtable of instructions */
668 setToNull ((void **) &iCodehTab);
669 iCodehTab = newHashTable (iCodeKey);
670 setToNull ((void **) &iCodeSeqhTab);
671 iCodeSeqhTab = newHashTable (iCodeKey);
672 sequenceiCode (ebbs, count);
674 /* call routine to mark the from & to live ranges for
676 setToNull ((void **) &liveRanges);
677 for (i = 0; i < count; i++)
678 markLiveRanges (ebbs[i], ebbs, count);
680 /* mark the ranges live for each point */
681 rlivePoint (ebbs, count);
683 /* compute which overlaps with what */