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->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);
585 /* overlapping live ranges should be eliminated */
586 if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
587 if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic)) && /* left & right share the same spil location */
588 OP_SYMBOL(IC_RESULT(ic))->isreqv && /* left of assign is a register requivalent */
589 !OP_SYMBOL(IC_RIGHT(ic))->isreqv && /* right side is not */
590 OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key && /* right side live beyond this point */
591 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 ) { /* left has multiple definitions */
592 SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
599 /*-----------------------------------------------------------------*/
600 /* computeClash - find out which live ranges collide with others */
601 /*-----------------------------------------------------------------*/
602 static void computeClash ()
604 hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
606 symbol *outer, *inner;
609 /* have to make a copy of the liveRanges hashTable :: UGHH .*/
610 for (item = hTabFirstItem(liveRanges,&key); item ;
611 item = hTabNextItem(liveRanges,&key)) {
612 hTabAddItem(&lRangeCopy,key,item);
615 /* outerloop : for each liverange do */
616 for (outer = hTabFirstItem(liveRanges,&key); outer ;
617 outer = hTabNextItem(liveRanges,&key)) {
619 /* if the liveFrom & To are the same then skip,
620 could happen for unused return values from functions */
621 if (outer->liveFrom == outer->liveTo) continue;
623 /* innerloop : for the inner loop we can start from the
624 item after the outer loop */
625 inner = hTabFirstItemWK (lRangeCopy,outer->key);
626 inner = hTabNextItem (lRangeCopy,&key1 );
627 for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
629 if (inner->liveFrom == inner->liveTo) continue;
630 if (inner->liveTo < outer->liveFrom) continue;
631 if (inner->liveFrom > outer->liveTo) continue;
633 /* if one of them are being defined where the other
634 one end , then no overlap (i.e. they can goto same registers */
635 if (inner->liveFrom == outer->liveTo ||
636 outer->liveFrom == inner->liveTo) continue;
638 /* so they overlap : set both their clashes */
639 inner->clashes = bitVectSetBit(inner->clashes,outer->key);
640 outer->clashes = bitVectSetBit(outer->clashes,inner->key);
642 /* check if they share the same spillocation */
643 if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
644 SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
645 if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
646 else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
647 else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
648 else SYM_SPIL_LOC(inner)=NULL;
655 /*-----------------------------------------------------------------*/
656 /* computeLiveRanges - computes the live ranges for variables */
657 /*-----------------------------------------------------------------*/
659 computeLiveRanges (eBBlock ** ebbs, int 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 setToNull ((void **) &iCodeSeqhTab);
669 iCodeSeqhTab = newHashTable (iCodeKey);
670 sequenceiCode (ebbs, count);
672 /* call routine to mark the from & to live ranges for
674 setToNull ((void **) &liveRanges);
675 for (i = 0; i < count; i++)
676 markLiveRanges (ebbs[i], ebbs, count);
678 /* mark the ranges live for each point */
679 rlivePoint (ebbs, count);
681 /* compute which overlaps with what */