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 /*-----------------------------------------------------------------*/
36 void sequenceiCode (eBBlock **ebbs, int count)
40 for (i = 0 ; i < count ; i++ ) {
43 ebbs[i]->fSeq = iCodeSeq + 1;
44 for ( ic = ebbs[i]->sch ; ic ; ic= ic->next) {
46 ic->depth = ebbs[i]->depth;
47 hTabAddItem(&iCodehTab,ic->key,ic);
49 ebbs[i]->lSeq = iCodeSeq ;
53 /*-----------------------------------------------------------------*/
54 /* markVisited - will set the visited flag for the given Block */
55 /*-----------------------------------------------------------------*/
56 DEFSETFUNC(markVisited)
63 applyToSet(ebp->succList,markVisited);
67 /*-----------------------------------------------------------------*/
68 /* isOpAlive - checks to see if the usage in this block is the */
69 /* uses the same definitions as this one */
70 /*-----------------------------------------------------------------*/
75 V_ARG(eBBlock *,orig);
83 /* if we have reached the originating block */
84 /* or this block has some definiton for it */
85 /* then check if it is used between start & */
88 bitVectBitsInCommon(OP_DEFS(op),ebp->defSet))
89 if (usedBetweenPoints (op,ebp->sch,ic))
92 applyToSet(ebp->succList,markVisited);
96 /* choosing this more expensive one since
97 killDeadCode will take away some definitions
98 but there is not way right now to take away
99 the usage information for the corresponding
100 usages, this will lead to longer live ranges */
101 if (usedInRemaining(op,ebp->sch))
105 return (applyToSet(ebp->succList,isOpAlive,op,orig,ic));
108 /*-----------------------------------------------------------------*/
109 /* isLastUse - return TRUE if no usage of this operand after this */
110 /*-----------------------------------------------------------------*/
111 int isLastUse (operand *op, eBBlock *ebp, iCode *ic,
112 eBBlock **ebbs, int count)
116 /* if this is used in the remaining */
117 if (usedInRemaining(op,ic))
120 /* if not then check any of the successor blocks use it */
121 for (i = 0 ; i < count ; ebbs[i++]->visited = 0);
122 if (applyToSet(ebp->succList,isOpAlive,op,ebp,ic))
125 /* this is the last use */
129 /*-----------------------------------------------------------------*/
130 /* unionDefsUsed - unions the defsUsed in a block */
131 /*-----------------------------------------------------------------*/
132 DEFSETFUNC(unionDefsUsed)
135 V_ARG(bitVect **,bvp);
142 *bvp = bitVectUnion(*bvp, ebp->usesDefs);
143 applyToSet(ebp->succList,unionDefsUsed,bvp);
147 /*-----------------------------------------------------------------*/
148 /* setFromRange - sets the from range of a given operand */
149 /*-----------------------------------------------------------------*/
150 void setFromRange (operand *op, int from)
152 /* only for compiler defined temporaries */
156 hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
159 OP_SYMBOL(op)->isptr = 1;
161 if (!OP_LIVEFROM(op) ||
162 OP_LIVEFROM(op) > from)
163 OP_LIVEFROM(op) = from;
166 /*-----------------------------------------------------------------*/
167 /* setToRange - set the range to for an operand */
168 /*-----------------------------------------------------------------*/
169 void setToRange (operand *op,int to, bool check)
171 /* only for compiler defined temps */
175 OP_SYMBOL(op)->key = op->key;
176 hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
179 OP_SYMBOL(op)->isptr = 1;
189 /*-----------------------------------------------------------------*/
190 /* firstDeOf - finds the first definition in seq for op */
191 /*-----------------------------------------------------------------*/
192 static iCode *firstDefOf (operand *op)
195 iCode *ric=NULL,*lic=NULL;
201 for (i=0; i < OP_DEFS(op)->size ;i++) {
202 if (bitVectBitValue(OP_DEFS(op),i) &&
203 (lic = hTabItemWithKey(iCodehTab,i)) &&
212 /*-----------------------------------------------------------------*/
213 /* useDefLoopCheck - check for uses before init inside loops */
214 /*-----------------------------------------------------------------*/
215 static void useDefLoopCheck(operand *op,iCode *ic)
217 /* this is for situations like the following
227 in this case the definition of 'b' will flow to the usages
228 but register allocator cannot handle these situations.so
229 will mark as spilt */
235 /* get the first definition */
236 if (!(tic = firstDefOf(op)))
240 /* now go thru the usages & make sure they follow
241 the first definition */
242 for (i=0; i <= OP_USES(op)->size;i++ ) {
243 if (bitVectBitValue(OP_USES(op),i) &&
244 (tic = hTabItemWithKey(iCodehTab,i)) &&
251 /* found a usage without definition */
253 if (OP_SYMBOL(op)->isreqv && SPIL_LOC(op) ) {
255 werror(W_LOCAL_NOINIT,
257 ic->filename,ic->lineno);
260 werror(W_LOCAL_NOINIT,
262 ic->filename,ic->lineno);
264 OP_SYMBOL(op)->isspilt = 1;
269 /*-----------------------------------------------------------------*/
270 /* operandLUse - check and set the last use for a given operand */
271 /*-----------------------------------------------------------------*/
272 operand *operandLUse (operand *op, eBBlock **ebbs,
273 int count, iCode *ic, eBBlock *ebp)
275 setFromRange(op,ic->seq);
277 OP_SYMBOL(op)->used += (((unsigned int)1 << ic->depth) + 1);
279 OP_SYMBOL(op)->used += 1;
281 if (isLastUse(op,ebp,ic->next,ebbs,count) ||
282 (OP_LIVETO(op) && OP_LIVETO(op) < ic->seq)) {
283 int torange = ic->seq;
284 /* if this is the last use then if this block belongs
285 to a loop & some definition comes into the loop
286 then extend the live range to the end of the loop */
287 if (ebp->partOfLoop &&
288 hasIncomingDefs(ebp->partOfLoop,op)) {
289 torange = findLoopEndSeq(ebp->partOfLoop);
291 op = operandFromOperand(op);
292 setToRange(op,torange,FALSE);
294 ic->uses = bitVectSetBit(ic->uses,op->key);
296 if (!OP_SYMBOL(op)->udChked)
298 link *type = operandType(op);
299 link *etype = getSpec(type);
301 OP_SYMBOL(op)->udChked = 1;
302 /* good place to check if unintialised */
303 if ((IS_TRUE_SYMOP(op) || OP_SYMBOL(op)->isreqv) &&
304 OP_SYMBOL(op)->islocal &&
305 !IS_AGGREGATE(type) &&
307 ic->op != ADDRESS_OF &&
308 !IS_STATIC(etype) ) {
310 if (bitVectIsZero(op->usesDefs)) {
311 OP_SYMBOL(op)->isspilt = 1;
313 if (OP_SYMBOL(op)->isreqv &&
314 !OP_SYMBOL(op)->_isparm && SPIL_LOC(op) ) {
316 werror(W_LOCAL_NOINIT,
318 ic->filename,ic->lineno);
321 werror(W_LOCAL_NOINIT,
323 ic->filename,ic->lineno);
326 if (ebp->depth && op->usesDefs &&
327 !OP_SYMBOL(op)->_isparm) {
328 /* check non-inits inside loops */
329 useDefLoopCheck(op,ic);
337 /*-----------------------------------------------------------------*/
338 /* killAllAlive - mark all the definitions living with this seq */
339 /*-----------------------------------------------------------------*/
340 void killAllAlive (int seq)
345 for (sym = hTabFirstItem(liveRanges,&k); sym;
346 sym = hTabNextItem(liveRanges,&k))
347 if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
350 /*-----------------------------------------------------------------*/
351 /* defUsedAfterLoop - all definitions & usages before sequence num */
352 /*-----------------------------------------------------------------*/
353 bool defUsedAfterLoop (operand *op, int seq)
358 /* check for the usages first */
359 if (OP_SYMBOL(op)->uses && !bitVectIsZero(OP_SYMBOL(op)->uses)) {
360 for (i = 0 ; i < OP_SYMBOL(op)->uses->size ; i++ ) {
362 if (bitVectBitValue( OP_SYMBOL(op)->uses,i) && /* usage found */
363 (ic = hTabItemWithKey(iCodehTab,i)) && /* "" */
364 ic->seq > seq ) /* & is after the seq */
372 /*-----------------------------------------------------------------*/
373 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
374 /*-----------------------------------------------------------------*/
375 void markLiveRanges (eBBlock *ebp, eBBlock **ebbs, int count)
378 bitVect *defsUsed = NULL;
379 bitVect *defsNotUsed = NULL;
381 /* for all the instructions */
382 for (ic = ebp->sch ; ic ; ic = ic->next ) {
384 if (ic->op == CALL || ic->op == PCALL) {
385 setFromRange(IC_RESULT(ic),ic->seq);
386 /* if the result has no usage then
387 mark this as the end of its life too
388 and take it away from the defs for the block*/
389 if (bitVectIsZero(OP_SYMBOL(IC_RESULT(ic))->uses)) {
390 setToRange(IC_RESULT(ic),ic->seq,FALSE);
391 bitVectUnSetBit(ebp->defSet,ic->key);
398 /* take care of the special icodes first */
399 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic))) {
400 operandLUse (IC_JTCOND(ic),ebbs,count,ic,ebp);
404 if (ic->op == IFX && IS_SYMOP(IC_COND(ic))) {
405 operandLUse (IC_COND(ic),ebbs,count,ic,ebp);
409 if (IS_SYMOP(IC_LEFT(ic)))
410 operandLUse (IC_LEFT(ic),ebbs,count,ic,ebp);
412 if (IS_SYMOP(IC_RIGHT(ic)))
413 operandLUse (IC_RIGHT(ic),ebbs,count,ic,ebp);
416 operandLUse(IC_RESULT(ic),ebbs,count,ic,ebp);
419 ic->defKey = IC_RESULT(ic)->key ;
423 /* for all the definitions in the block */
424 /* compute and set the live from */
425 if ( ebp->ldefs && ! bitVectIsZero(ebp->ldefs)) {
426 for ( i = 0 ; i < ebp->ldefs->size ; i++ ) {
429 if (bitVectBitValue(ebp->ldefs,i) &&
430 (dic = hTabItemWithKey(iCodehTab,i))) {
432 /* if the definition has a from & it is greater */
433 /* than the defininng iCode->seq then change it */
434 setFromRange(IC_RESULT(dic),dic->seq);
439 /* special case for lastBlock in a loop: here we
440 mark the end of all the induction variables for the
442 if (ebp->isLastInLoop && !bitVectIsZero(ebp->linds)) {
443 for ( i = 0 ; i <= ebp->linds->size ; i++ ) {
446 if (bitVectBitValue(ebp->linds,i) &&
447 (dic = hTabItemWithKey(iCodehTab,i))) {
449 /* if this is a register equvalent make sure
450 it is not defined or used anywhere after the loop */
451 if (OP_SYMBOL(IC_RESULT(dic))->isreqv &&
452 defUsedAfterLoop(IC_RESULT(dic), ebp->lSeq))
455 setToRange(IC_RESULT(dic),( ebp->lSeq ),FALSE);
460 /* for defnitions coming into the block if they */
461 /* not used by itself & any of its successors */
463 /* first union the definitions used in all successors
465 for (i = 0; i < count ; ebbs[i++]->visited = 0);
466 applyToSet(ebp->succList,unionDefsUsed,&defsUsed);
467 defsUsed = bitVectUnion(defsUsed,ebp->usesDefs);
469 /* now subract the result of these unions from */
470 /* the incoming definitions this will give the */
471 /* definitions that are never used in the future */
472 defsNotUsed = bitVectCplAnd(bitVectCopy(ebp->inDefs),
475 /* mark the end of the defintions */
476 if ( !bitVectIsZero(defsNotUsed) && ebp->sch ) {
477 for ( i = 0 ; i < defsNotUsed->size; i++ ) {
480 if (bitVectBitValue(defsNotUsed,i) &&
481 (dic = hTabItemWithKey(iCodehTab,i))) {
483 setToRange(IC_RESULT(dic),( ebp->fSeq - 1),TRUE);
489 /* if we reach a lock with noPath to it then kill all
490 the live ranges alive at this point */
491 /* if (ebp->noPath || ebp->entryLabel == returnLabel) */
492 if (ebp->entryLabel == returnLabel)
493 killAllAlive(ebp->fSeq);
496 /*-----------------------------------------------------------------*/
497 /* rlivePoint - for each point compute the ranges that are alive */
498 /*-----------------------------------------------------------------*/
499 void rlivePoint (eBBlock **ebbs, int count)
503 /* for all blocks do */
504 for ( i = 0 ; i < count ; i++ ) {
507 /* for all instruction in the block do */
508 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
512 ic->rlive = newBitVect(operandKey);
513 /* for all symbols in the liverange table */
514 for ( lrange = hTabFirstItem(liveRanges,&k); lrange;
515 lrange = hTabNextItem(liveRanges,&k)) {
517 if (lrange->liveFrom <= ic->seq &&
518 lrange->liveTo >= ic->seq )
519 ic->rlive = bitVectSetBit(ic->rlive,lrange->key);
526 /*-----------------------------------------------------------------*/
527 /* computeLiveRanges - computes the live ranges for variables */
528 /*-----------------------------------------------------------------*/
529 void computeLiveRanges (eBBlock **ebbs, int count )
532 /* sequence the code the live ranges are computed
533 in terms of this sequence additionally the
534 routine will also create a hashtable of instructions */
536 setToNull((void **)&iCodehTab);
537 iCodehTab = newHashTable (iCodeKey);
538 sequenceiCode(ebbs,count);
540 /* call routine to mark the from & to live ranges for
542 setToNull((void **)&liveRanges);
543 for ( i = 0 ; i < count; i++ )
544 markLiveRanges (ebbs[i],ebbs,count);
546 /* mark the ranges live for each point */
547 rlivePoint (ebbs,count);