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;
33 /*-----------------------------------------------------------------*/
34 /* sequenceiCode - creates a sequence number for the iCode & add */
35 /*-----------------------------------------------------------------*/
37 sequenceiCode (eBBlock ** ebbs, int count)
41 for (i = 0; i < count; i++)
45 ebbs[i]->fSeq = iCodeSeq + 1;
46 for (ic = ebbs[i]->sch; ic; ic = ic->next)
49 ic->depth = ebbs[i]->depth;
50 hTabAddItem (&iCodehTab, ic->key, ic);
52 ebbs[i]->lSeq = iCodeSeq;
56 /*-----------------------------------------------------------------*/
57 /* markVisited - will set the visited flag for the given Block */
58 /*-----------------------------------------------------------------*/
59 DEFSETFUNC (markVisited)
66 applyToSet (ebp->succList, markVisited);
70 /*-----------------------------------------------------------------*/
71 /* isOpAlive - checks to see if the usage in this block is the */
72 /* uses the same definitions as this one */
73 /*-----------------------------------------------------------------*/
74 DEFSETFUNC (isOpAlive)
77 V_ARG (operand *, op);
78 V_ARG (eBBlock *, orig);
86 /* if we have reached the originating block */
87 /* or this block has some definiton for it */
88 /* then check if it is used between start & */
91 bitVectBitsInCommon (OP_DEFS (op), ebp->defSet))
92 if (usedBetweenPoints (op, ebp->sch, ic))
96 applyToSet (ebp->succList, markVisited);
100 /* choosing this more expensive one since
101 killDeadCode will take away some definitions
102 but there is not way right now to take away
103 the usage information for the corresponding
104 usages, this will lead to longer live ranges */
105 if (usedInRemaining (op, ebp->sch))
109 return (applyToSet (ebp->succList, isOpAlive, op, orig, ic));
112 /*-----------------------------------------------------------------*/
113 /* isLastUse - return TRUE if no usage of this operand after this */
114 /*-----------------------------------------------------------------*/
116 isLastUse (operand * op, eBBlock * ebp, iCode * ic,
117 eBBlock ** ebbs, int count)
121 /* if this is used in the remaining */
122 if (usedInRemaining (op, ic))
125 /* if not then check any of the successor blocks use it */
126 for (i = 0; i < count; ebbs[i++]->visited = 0);
127 if (applyToSet (ebp->succList, isOpAlive, op, ebp, ic))
130 /* this is the last use */
134 /*-----------------------------------------------------------------*/
135 /* unionDefsUsed - unions the defsUsed in a block */
136 /*-----------------------------------------------------------------*/
137 DEFSETFUNC (unionDefsUsed)
140 V_ARG (bitVect **, bvp);
147 *bvp = bitVectUnion (*bvp, ebp->usesDefs);
148 applyToSet (ebp->succList, unionDefsUsed, bvp);
152 /*-----------------------------------------------------------------*/
153 /* setFromRange - sets the from range of a given operand */
154 /*-----------------------------------------------------------------*/
156 setFromRange (operand * op, int from)
158 /* only for compiler defined temporaries */
162 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
165 OP_SYMBOL (op)->isptr = 1;
167 if (!OP_LIVEFROM (op) ||
168 OP_LIVEFROM (op) > from)
169 OP_LIVEFROM (op) = from;
172 /*-----------------------------------------------------------------*/
173 /* setToRange - set the range to for an operand */
174 /*-----------------------------------------------------------------*/
176 setToRange (operand * op, int to, bool check)
178 /* only for compiler defined temps */
182 OP_SYMBOL (op)->key = op->key;
183 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
186 OP_SYMBOL (op)->isptr = 1;
196 /*-----------------------------------------------------------------*/
197 /* firstDeOf - finds the first definition in seq for op */
198 /*-----------------------------------------------------------------*/
200 firstDefOf (operand * op)
203 iCode *ric = NULL, *lic = NULL;
209 for (i = 0; i < OP_DEFS (op)->size; i++)
211 if (bitVectBitValue (OP_DEFS (op), i) &&
212 (lic = hTabItemWithKey (iCodehTab, i)) &&
222 /*-----------------------------------------------------------------*/
223 /* useDefLoopCheck - check for uses before init inside loops */
224 /*-----------------------------------------------------------------*/
226 useDefLoopCheck (operand * op, iCode * ic)
228 /* this is for situations like the following
238 in this case the definition of 'b' will flow to the usages
239 but register allocator cannot handle these situations.so
240 will mark as spilt */
246 /* get the first definition */
247 if (!(tic = firstDefOf (op)))
251 /* now go thru the usages & make sure they follow
252 the first definition */
253 for (i = 0; i <= OP_USES (op)->size; i++)
255 if (bitVectBitValue (OP_USES (op), i) &&
256 (tic = hTabItemWithKey (iCodehTab, i)) &&
264 /* found a usage without definition */
267 if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
270 werror (W_LOCAL_NOINIT,
272 ic->filename, ic->lineno);
277 werror (W_LOCAL_NOINIT,
278 OP_SYMBOL (op)->name,
279 ic->filename, ic->lineno);
281 OP_SYMBOL (op)->isspilt = 1;
286 /*-----------------------------------------------------------------*/
287 /* operandLUse - check and set the last use for a given operand */
288 /*-----------------------------------------------------------------*/
290 operandLUse (operand * op, eBBlock ** ebbs,
291 int count, iCode * ic, eBBlock * ebp)
293 setFromRange (op, ic->seq);
295 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
297 OP_SYMBOL (op)->used += 1;
299 if (isLastUse (op, ebp, ic->next, ebbs, count) ||
300 (OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
302 int torange = ic->seq;
303 /* if this is the last use then if this block belongs
304 to a loop & some definition comes into the loop
305 then extend the live range to the end of the loop */
306 if (ebp->partOfLoop &&
307 hasIncomingDefs (ebp->partOfLoop, op))
309 torange = findLoopEndSeq (ebp->partOfLoop);
311 op = operandFromOperand (op);
312 setToRange (op, torange, FALSE);
314 ic->uses = bitVectSetBit (ic->uses, op->key);
316 if (!OP_SYMBOL (op)->udChked)
318 sym_link *type = operandType (op);
319 sym_link *etype = getSpec (type);
321 OP_SYMBOL (op)->udChked = 1;
322 /* good place to check if unintialised */
323 if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
324 OP_SYMBOL (op)->islocal &&
325 !IS_AGGREGATE (type) &&
327 ic->op != ADDRESS_OF &&
331 if (bitVectIsZero (op->usesDefs))
333 OP_SYMBOL (op)->isspilt = 1;
335 if (OP_SYMBOL (op)->isreqv &&
336 !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
339 werror (W_LOCAL_NOINIT,
341 ic->filename, ic->lineno);
346 werror (W_LOCAL_NOINIT,
347 OP_SYMBOL (op)->name,
348 ic->filename, ic->lineno);
353 if (ebp->depth && op->usesDefs &&
354 !OP_SYMBOL (op)->_isparm)
356 /* check non-inits inside loops */
357 useDefLoopCheck (op, ic);
365 /*-----------------------------------------------------------------*/
366 /* killAllAlive - mark all the definitions living with this seq */
367 /*-----------------------------------------------------------------*/
369 killAllAlive (int seq)
374 for (sym = hTabFirstItem (liveRanges, &k); sym;
375 sym = hTabNextItem (liveRanges, &k))
376 if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
379 /*-----------------------------------------------------------------*/
380 /* defUsedAfterLoop - all definitions & usages before sequence num */
381 /*-----------------------------------------------------------------*/
383 defUsedAfterLoop (operand * op, int seq)
388 /* check for the usages first */
389 if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
391 for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
394 if (bitVectBitValue (OP_SYMBOL (op)->uses, i) && /* usage found */
395 (ic = hTabItemWithKey (iCodehTab, i)) && /* "" */
396 ic->seq > seq) /* & is after the seq */
404 /*-----------------------------------------------------------------*/
405 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
406 /*-----------------------------------------------------------------*/
408 markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
411 bitVect *defsUsed = NULL;
412 bitVect *defsNotUsed = NULL;
414 /* for all the instructions */
415 for (ic = ebp->sch; ic; ic = ic->next)
418 if (ic->op == CALL || ic->op == PCALL)
420 setFromRange (IC_RESULT (ic), ic->seq);
421 /* if the result has no usage then
422 mark this as the end of its life too
423 and take it away from the defs for the block */
424 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
426 setToRange (IC_RESULT (ic), ic->seq, FALSE);
427 bitVectUnSetBit (ebp->defSet, ic->key);
434 /* take care of the special icodes first */
435 if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
437 operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
441 if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
443 operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
447 if (IS_SYMOP (IC_LEFT (ic)))
448 operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
450 if (IS_SYMOP (IC_RIGHT (ic)))
451 operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
453 if (POINTER_SET (ic))
454 operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
455 else if (IC_RESULT (ic))
456 ic->defKey = IC_RESULT (ic)->key;
460 /* for all the definitions in the block */
461 /* compute and set the live from */
462 if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
464 for (i = 0; i < ebp->ldefs->size; i++)
468 if (bitVectBitValue (ebp->ldefs, i) &&
469 (dic = hTabItemWithKey (iCodehTab, i)))
472 /* if the definition has a from & it is greater */
473 /* than the defininng iCode->seq then change it */
474 setFromRange (IC_RESULT (dic), dic->seq);
479 /* special case for lastBlock in a loop: here we
480 mark the end of all the induction variables for the
482 if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
484 for (i = 0; i <= ebp->linds->size; i++)
488 if (bitVectBitValue (ebp->linds, i) &&
489 (dic = hTabItemWithKey (iCodehTab, i)))
492 /* if this is a register equvalent make sure
493 it is not defined or used anywhere after the loop */
494 if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
495 defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
498 setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
503 /* for defnitions coming into the block if they */
504 /* not used by itself & any of its successors */
506 /* first union the definitions used in all successors
508 for (i = 0; i < count; ebbs[i++]->visited = 0);
509 applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
510 defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
512 /* now subract the result of these unions from */
513 /* the incoming definitions this will give the */
514 /* definitions that are never used in the future */
515 defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
518 /* mark the end of the defintions */
519 if (!bitVectIsZero (defsNotUsed) && ebp->sch)
521 for (i = 0; i < defsNotUsed->size; i++)
525 if (bitVectBitValue (defsNotUsed, i) &&
526 (dic = hTabItemWithKey (iCodehTab, i)))
529 setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
535 /* if we reach a lock with noPath to it then kill all
536 the live ranges alive at this point */
537 /* if (ebp->noPath || ebp->entryLabel == returnLabel) */
538 if (ebp->entryLabel == returnLabel)
539 killAllAlive (ebp->fSeq);
542 /*-----------------------------------------------------------------*/
543 /* rlivePoint - for each point compute the ranges that are alive */
544 /*-----------------------------------------------------------------*/
546 rlivePoint (eBBlock ** ebbs, int count)
550 /* for all blocks do */
551 for (i = 0; i < count; i++)
555 /* for all instruction in the block do */
556 for (ic = ebbs[i]->sch; ic; ic = ic->next)
561 ic->rlive = newBitVect (operandKey);
562 /* for all symbols in the liverange table */
563 for (lrange = hTabFirstItem (liveRanges, &k); lrange;
564 lrange = hTabNextItem (liveRanges, &k))
567 /* if it is live then add the lrange to ic->rlive */
568 if (lrange->liveFrom <= ic->seq &&
569 lrange->liveTo >= ic->seq)
571 lrange->isLiveFcall |= (ic->op == CALL || ic->op == PCALL || ic->op == SEND);
572 ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
580 /*-----------------------------------------------------------------*/
581 /* computeLiveRanges - computes the live ranges for variables */
582 /*-----------------------------------------------------------------*/
584 computeLiveRanges (eBBlock ** ebbs, int count)
587 /* sequence the code the live ranges are computed
588 in terms of this sequence additionally the
589 routine will also create a hashtable of instructions */
591 setToNull ((void **) &iCodehTab);
592 iCodehTab = newHashTable (iCodeKey);
593 sequenceiCode (ebbs, count);
595 /* call routine to mark the from & to live ranges for
597 setToNull ((void **) &liveRanges);
598 for (i = 0; i < count; i++)
599 markLiveRanges (ebbs[i], ebbs, count);
601 /* mark the ranges live for each point */
602 rlivePoint (ebbs, count);