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 -------------------------------------------------------------------------*/
29 hTab *liveRanges = NULL;
30 hTab *iCodehTab = NULL;
32 /*-----------------------------------------------------------------*/
33 /* sequenceiCode - creates a sequence number for the iCode & add */
34 /*-----------------------------------------------------------------*/
35 void sequenceiCode (eBBlock **ebbs, int count)
39 for (i = 0 ; i < count ; i++ ) {
42 ebbs[i]->fSeq = iCodeSeq + 1;
43 for ( ic = ebbs[i]->sch ; ic ; ic= ic->next) {
45 ic->depth = ebbs[i]->depth;
46 hTabAddItem(&iCodehTab,ic->key,ic);
48 ebbs[i]->lSeq = iCodeSeq ;
52 /*-----------------------------------------------------------------*/
53 /* markVisited - will set the visited flag for the given Block */
54 /*-----------------------------------------------------------------*/
55 DEFSETFUNC(markVisited)
62 applyToSet(ebp->succList,markVisited);
66 /*-----------------------------------------------------------------*/
67 /* isOpAlive - checks to see if the usage in this block is the */
68 /* uses the same definitions as this one */
69 /*-----------------------------------------------------------------*/
74 V_ARG(eBBlock *,orig);
82 /* if we have reached the originating block */
83 /* or this block has some definiton for it */
84 /* then check if it is used between start & */
87 bitVectBitsInCommon(OP_DEFS(op),ebp->defSet))
88 if (usedBetweenPoints (op,ebp->sch,ic))
91 applyToSet(ebp->succList,markVisited);
95 /* choosing this more expensive one since
96 killDeadCode will take away some definitions
97 but there is not way right now to take away
98 the usage information for the corresponding
99 usages, this will lead to longer live ranges */
100 if (usedInRemaining(op,ebp->sch))
104 return (applyToSet(ebp->succList,isOpAlive,op,orig,ic));
107 /*-----------------------------------------------------------------*/
108 /* isLastUse - return TRUE if no usage of this operand after this */
109 /*-----------------------------------------------------------------*/
110 int isLastUse (operand *op, eBBlock *ebp, iCode *ic,
111 eBBlock **ebbs, int count)
115 /* if this is used in the remaining */
116 if (usedInRemaining(op,ic))
119 /* if not then check any of the successor blocks use it */
120 for (i = 0 ; i < count ; ebbs[i++]->visited = 0);
121 if (applyToSet(ebp->succList,isOpAlive,op,ebp,ic))
124 /* this is the last use */
128 /*-----------------------------------------------------------------*/
129 /* unionDefsUsed - unions the defsUsed in a block */
130 /*-----------------------------------------------------------------*/
131 DEFSETFUNC(unionDefsUsed)
134 V_ARG(bitVect **,bvp);
141 *bvp = bitVectUnion(*bvp, ebp->usesDefs);
142 applyToSet(ebp->succList,unionDefsUsed,bvp);
146 /*-----------------------------------------------------------------*/
147 /* setFromRange - sets the from range of a given operand */
148 /*-----------------------------------------------------------------*/
149 void setFromRange (operand *op, int from)
151 /* only for compiler defined temporaries */
155 hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
158 OP_SYMBOL(op)->isptr = 1;
160 if (!OP_LIVEFROM(op) ||
161 OP_LIVEFROM(op) > from)
162 OP_LIVEFROM(op) = from;
165 /*-----------------------------------------------------------------*/
166 /* setToRange - set the range to for an operand */
167 /*-----------------------------------------------------------------*/
168 void setToRange (operand *op,int to, bool check)
170 /* only for compiler defined temps */
174 OP_SYMBOL(op)->key = op->key;
175 hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
178 OP_SYMBOL(op)->isptr = 1;
189 /*-----------------------------------------------------------------*/
190 /* operandLUse - check and set the last use for a given operand */
191 /*-----------------------------------------------------------------*/
192 operand *operandLUse (operand *op, eBBlock **ebbs,
193 int count, iCode *ic, eBBlock *ebp)
195 setFromRange(op,ic->seq);
197 OP_SYMBOL(op)->used += (((unsigned int)1 << ic->depth) + 1);
199 OP_SYMBOL(op)->used += 1;
201 if (isLastUse(op,ebp,ic->next,ebbs,count) ||
202 (OP_LIVETO(op) && OP_LIVETO(op) < ic->seq)) {
203 int torange = ic->seq;
204 /* if this is the last use then if this block belongs
205 to a loop & some definition comes into the loop
206 then extend the live range to the end of the loop */
207 if (ebp->partOfLoop &&
208 hasIncomingDefs(ebp->partOfLoop,op)) {
209 torange = findLoopEndSeq(ebp->partOfLoop);
211 op = operandFromOperand(op);
212 setToRange(op,torange,FALSE);
214 ic->uses = bitVectSetBit(ic->uses,op->key);
217 link *type = operandType(op);
218 link *etype = getSpec(type);
220 /* good place to check if unintialised */
221 if ((IS_TRUE_SYMOP(op) || OP_SYMBOL(op)->isreqv) &&
222 OP_SYMBOL(op)->islocal &&
223 !IS_AGGREGATE(type) &&
225 ic->op != ADDRESS_OF &&
226 !IS_STATIC(etype) ) {
228 if (bitVectIsZero(op->usesDefs)) {
229 OP_SYMBOL(op)->isspilt = 1;
231 if (OP_SYMBOL(op)->isreqv &&
232 !OP_SYMBOL(op)->_isparm && SPIL_LOC(op) ) {
234 werror(W_LOCAL_NOINIT,
236 ic->filename,ic->lineno);
239 werror(W_LOCAL_NOINIT,
241 ic->filename,ic->lineno);
249 /*-----------------------------------------------------------------*/
250 /* compLastUse - computes the last usage with certainty */
251 /*-----------------------------------------------------------------*/
256 /* the strategy here is to look for live ranges that are not
257 induction variables, and find out the usage icode with the
258 highest sequence number then set the to range to that icode
260 /* once fully tested we can use only this routine to mark the
261 to range that will reduce a lot of computations in the
262 markLiveRanges routine */
263 for (sym = hTabFirstItem(liveRanges,&key) ; sym;
264 sym = hTabNextItem(liveRanges,&key)) {
275 /* go thru all the usages of this live range and find out
276 the maximum sequence number of the icode that used it */
277 for (i = 0 ; i < sym->uses->size ; i++ ) {
280 if (!bitVectBitValue(sym->uses,i))
283 if ((uic = hTabItemWithKey(iCodehTab,i)))
284 maxKey = ( uic->seq > maxKey ? uic->seq : maxKey );
289 sym->liveTo = maxKey;
293 /*-----------------------------------------------------------------*/
294 /* killAllAlive - mark all the definitions living with this seq */
295 /*-----------------------------------------------------------------*/
296 void killAllAlive (int seq)
301 for (sym = hTabFirstItem(liveRanges,&k); sym;
302 sym = hTabNextItem(liveRanges,&k))
303 if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
306 /*-----------------------------------------------------------------*/
307 /* defUsedAfterLoop - all definitions & usages before sequence num */
308 /*-----------------------------------------------------------------*/
309 bool defUsedAfterLoop (operand *op, int seq)
314 /* check for the usages first */
315 if (OP_SYMBOL(op)->uses && !bitVectIsZero(OP_SYMBOL(op)->uses)) {
316 for (i = 0 ; i < OP_SYMBOL(op)->uses->size ; i++ ) {
318 if (bitVectBitValue( OP_SYMBOL(op)->uses,i) && /* usage found */
319 (ic = hTabItemWithKey(iCodehTab,i)) && /* "" */
320 ic->seq > seq ) /* & is after the seq */
328 /*-----------------------------------------------------------------*/
329 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
330 /*-----------------------------------------------------------------*/
331 void markLiveRanges (eBBlock *ebp, eBBlock **ebbs, int count)
334 bitVect *defsUsed = NULL;
335 bitVect *defsNotUsed = NULL;
337 /* for all the instructions */
338 for (ic = ebp->sch ; ic ; ic = ic->next ) {
340 if (ic->op == CALL || ic->op == PCALL) {
341 setFromRange(IC_RESULT(ic),ic->seq);
342 /* if the result has no usage then
343 mark this as the end of its life too
344 and take it away from the defs for the block*/
345 if (bitVectIsZero(OP_SYMBOL(IC_RESULT(ic))->uses)) {
346 setToRange(IC_RESULT(ic),ic->seq,FALSE);
347 bitVectUnSetBit(ebp->defSet,ic->key);
354 /* take care of the special icodes first */
355 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic))) {
356 operandLUse (IC_JTCOND(ic),ebbs,count,ic,ebp);
360 if (ic->op == IFX && IS_SYMOP(IC_COND(ic))) {
361 operandLUse (IC_COND(ic),ebbs,count,ic,ebp);
365 if (IS_SYMOP(IC_LEFT(ic)))
366 operandLUse (IC_LEFT(ic),ebbs,count,ic,ebp);
368 if (IS_SYMOP(IC_RIGHT(ic)))
369 operandLUse (IC_RIGHT(ic),ebbs,count,ic,ebp);
372 operandLUse(IC_RESULT(ic),ebbs,count,ic,ebp);
375 ic->defKey = IC_RESULT(ic)->key ;
379 /* for all the definitions in the block */
380 /* compute and set the live from */
381 if ( ebp->defSet && ! bitVectIsZero(ebp->defSet)) {
382 for ( i = 0 ; i < ebp->defSet->size ; i++ ) {
385 if (bitVectBitValue(ebp->defSet,i) &&
386 (dic = hTabItemWithKey(iCodehTab,i))) {
388 /* if the definition has a from & it is greater */
389 /* than the defininng iCode->seq then change it */
390 setFromRange(IC_RESULT(dic),dic->seq);
395 /* special case for lastBlock in a loop: here we
396 mark the end of all the induction variables for the
398 if (ebp->isLastInLoop && !bitVectIsZero(ebp->linds)) {
399 for ( i = 0 ; i <= ebp->linds->size ; i++ ) {
402 if (bitVectBitValue(ebp->linds,i) &&
403 (dic = hTabItemWithKey(iCodehTab,i))) {
405 /* if this is a register equvalent make sure
406 it is not defined or used anywhere after the loop */
407 if (OP_SYMBOL(IC_RESULT(dic))->isreqv &&
408 defUsedAfterLoop(IC_RESULT(dic), ebp->lSeq))
411 setToRange(IC_RESULT(dic),( ebp->lSeq ),FALSE);
416 /* for defnitions coming into the block if they */
417 /* not used by itself & any of its successors */
419 /* first union the definitions used in all successors
421 for (i = 0; i < count ; ebbs[i++]->visited = 0);
422 applyToSet(ebp->succList,unionDefsUsed,&defsUsed);
423 defsUsed = bitVectUnion(defsUsed,ebp->usesDefs);
425 /* now subract the result of these unions from */
426 /* the incoming definitions this will give the */
427 /* definitions that are never used in the future */
428 defsNotUsed = bitVectCplAnd(bitVectCopy(ebp->inDefs),
431 /* mark the end of the defintions */
432 if ( !bitVectIsZero(defsNotUsed) && ebp->sch ) {
433 for ( i = 0 ; i < defsNotUsed->size; i++ ) {
436 if (bitVectBitValue(defsNotUsed,i) &&
437 (dic = hTabItemWithKey(iCodehTab,i))) {
439 setToRange(IC_RESULT(dic),( ebp->fSeq - 1),TRUE);
445 /* if we reach a lock with noPath to it then kill all
446 the live ranges alive at this point */
447 /* if (ebp->noPath || ebp->entryLabel == returnLabel) */
448 if (ebp->entryLabel == returnLabel)
449 killAllAlive(ebp->fSeq);
452 /*-----------------------------------------------------------------*/
453 /* rlivePoint - for each point compute the ranges that are alive */
454 /*-----------------------------------------------------------------*/
455 void rlivePoint (eBBlock **ebbs, int count)
459 /* for all blocks do */
460 for ( i = 0 ; i < count ; i++ ) {
463 /* for all instruction in the block do */
464 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
468 ic->rlive = newBitVect(operandKey);
469 /* for all symbols in the liverange table */
470 for ( lrange = hTabFirstItem(liveRanges,&k); lrange;
471 lrange = hTabNextItem(liveRanges,&k)) {
473 if (lrange->liveFrom <= ic->seq &&
474 lrange->liveTo >= ic->seq )
475 ic->rlive = bitVectSetBit(ic->rlive,lrange->key);
482 /*-----------------------------------------------------------------*/
483 /* computeLiveRanges - computes the live ranges for variables */
484 /*-----------------------------------------------------------------*/
485 void computeLiveRanges (eBBlock **ebbs, int count )
488 /* sequence the code the live ranges are computed
489 in terms of this sequence additionally the
490 routine will also create a hashtable of instructions */
492 setToNull((void **)&iCodehTab);
493 iCodehTab = newHashTable (iCodeKey);
494 sequenceiCode(ebbs,count);
496 /* call routine to mark the from & to live ranges for
498 setToNull((void **)&liveRanges);
499 for ( i = 0 ; i < count; i++ )
500 markLiveRanges (ebbs[i],ebbs,count);
503 /* mark the ranges live for each point */
504 rlivePoint (ebbs,count);