git.gag.com Git - fw/sdcc/blob - src/SDCClrange.c

   1 /*-------------------------------------------------------------------------
   2
   3   SDCClrange.c - source file for live range computations
   4
   5              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
   6
   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
  10    later version.
  11
  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.
  16
  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.
  20
  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 -------------------------------------------------------------------------*/
  25
  26 #include "common.h"
  27
  28 int iCodeSeq = 0 ;
  29 hTab *liveRanges = NULL;
  30 hTab *iCodehTab = NULL;
  31
  32 /*-----------------------------------------------------------------*/
  33 /* sequenceiCode - creates a sequence number for the iCode & add   */
  34 /*-----------------------------------------------------------------*/
  35 void sequenceiCode (eBBlock **ebbs, int count)
  36 {
  37     int i;
  38
  39     for (i = 0 ; i < count ; i++ ) {
  40
  41         iCode *ic;
  42         ebbs[i]->fSeq = iCodeSeq + 1;
  43         for ( ic = ebbs[i]->sch ; ic ; ic= ic->next) {
  44             ic->seq = ++iCodeSeq;
  45             ic->depth = ebbs[i]->depth;
  46             hTabAddItem(&iCodehTab,ic->key,ic);
  47         }
  48         ebbs[i]->lSeq = iCodeSeq ;
  49     }
  50 }
  51
  52 /*-----------------------------------------------------------------*/
  53 /* markVisited - will set the visited flag for the given Block     */
  54 /*-----------------------------------------------------------------*/
  55 DEFSETFUNC(markVisited)
  56 {
  57     eBBlock *ebp = item;
  58
  59     if (ebp->visited)
  60         return 0;
  61     ebp->visited = 1;
  62     applyToSet(ebp->succList,markVisited);
  63     return 0;
  64 }
  65
  66 /*-----------------------------------------------------------------*/
  67 /* isOpAlive - checks to see if the usage in this block is the     */
  68 /*             uses the same definitions as this one               */
  69 /*-----------------------------------------------------------------*/
  70 DEFSETFUNC(isOpAlive)
  71 {
  72     eBBlock *ebp = item;
  73     V_ARG(operand *,op);
  74     V_ARG(eBBlock *,orig);
  75     V_ARG(iCode *,ic);
  76
  77     if (ebp->visited)
  78         return 0;
  79
  80     ebp->visited = 1;
  81
  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 & */
  85     /* this point */
  86     if ( ebp == orig ||
  87          bitVectBitsInCommon(OP_DEFS(op),ebp->defSet))
  88         if (usedBetweenPoints (op,ebp->sch,ic))
  89             return 1;
  90         else {
  91             applyToSet(ebp->succList,markVisited);
  92             return 0;
  93         }
  94     else
  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))
 101             return 1;
 102
 103
 104     return (applyToSet(ebp->succList,isOpAlive,op,orig,ic));
 105 }
 106
 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)
 112 {
 113     int i;
 114
 115     /* if this is used in the remaining */
 116     if (usedInRemaining(op,ic))
 117         return 0;
 118
 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))
 122         return 0;
 123
 124     /* this is the last use */
 125     return 1;
 126 }
 127
 128 /*-----------------------------------------------------------------*/
 129 /* unionDefsUsed - unions the defsUsed in a block                  */
 130 /*-----------------------------------------------------------------*/
 131 DEFSETFUNC(unionDefsUsed)
 132 {
 133     eBBlock *ebp = item;
 134     V_ARG(bitVect **,bvp);
 135
 136     if (ebp->visited)
 137         return 0;
 138
 139     ebp->visited = 1;
 140
 141     *bvp = bitVectUnion(*bvp, ebp->usesDefs);
 142     applyToSet(ebp->succList,unionDefsUsed,bvp);
 143     return 0;
 144 }
 145
 146 /*-----------------------------------------------------------------*/
 147 /* setFromRange - sets the from range of a given operand           */
 148 /*-----------------------------------------------------------------*/
 149 void setFromRange (operand *op, int from)
 150 {
 151     /* only for compiler defined temporaries */
 152     if (!IS_ITEMP(op))
 153         return ;
 154
 155     hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
 156
 157     if (op->isaddr)
 158         OP_SYMBOL(op)->isptr = 1;
 159
 160     if (!OP_LIVEFROM(op) ||
 161         OP_LIVEFROM(op) > from)
 162         OP_LIVEFROM(op) = from;
 163 }
 164
 165 /*-----------------------------------------------------------------*/
 166 /* setToRange - set the range to for an operand                    */
 167 /*-----------------------------------------------------------------*/
 168 void setToRange (operand *op,int to, bool check)
 169 {
 170     /* only for compiler defined temps */
 171     if (!IS_ITEMP(op))
 172         return ;
 173
 174     OP_SYMBOL(op)->key = op->key;
 175     hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
 176
 177     if (op->isaddr)
 178         OP_SYMBOL(op)->isptr = 1;
 179
 180     if (check)
 181         if (!OP_LIVETO(op))
 182             OP_LIVETO(op) = to;
 183         else ;
 184     else
 185         OP_LIVETO(op) = to;
 186 }
 187
 188
 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)
 194 {
 195     setFromRange(op,ic->seq);
 196     if (ic->depth)
 197         OP_SYMBOL(op)->used += (((unsigned int)1 << ic->depth) + 1);
 198     else
 199         OP_SYMBOL(op)->used += 1;
 200
 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);
 210         }
 211         op = operandFromOperand(op);
 212         setToRange(op,torange,FALSE);
 213     }
 214     ic->uses = bitVectSetBit(ic->uses,op->key);
 215
 216     {
 217         link *type = operandType(op);
 218         link *etype = getSpec(type);
 219
 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)       &&
 224             !IS_FUNC(type)            &&
 225             ic->op != ADDRESS_OF      &&
 226             !IS_STATIC(etype)         ) {
 227
 228             if (bitVectIsZero(op->usesDefs)) {
 229                 OP_SYMBOL(op)->isspilt = 1;
 230
 231                 if (OP_SYMBOL(op)->isreqv &&
 232                     !OP_SYMBOL(op)->_isparm && SPIL_LOC(op) ) {
 233
 234                     werror(W_LOCAL_NOINIT,
 235                            SPIL_LOC(op)->name,
 236                            ic->filename,ic->lineno);
 237                 } else {
 238
 239                     werror(W_LOCAL_NOINIT,
 240                            OP_SYMBOL(op)->name,
 241                            ic->filename,ic->lineno);
 242                 }
 243             }
 244         }
 245     }
 246     return op;
 247 }
 248
 249 /*-----------------------------------------------------------------*/
 250 /* compLastUse - computes the last usage with certainty            */
 251 /*-----------------------------------------------------------------*/
 252 void compLastUse ()
 253 {
 254     symbol *sym;
 255     int key;
 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
 259        sequence */
 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)) {
 265
 266         int i ;
 267         int maxKey = 0 ;
 268
 269         if (sym->isind)
 270             continue ;
 271
 272         if (!sym->uses)
 273             continue ;
 274
 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++ ) {
 278             iCode *uic ;
 279
 280             if (!bitVectBitValue(sym->uses,i))
 281                 continue ;
 282
 283             if ((uic = hTabItemWithKey(iCodehTab,i)))
 284                 maxKey = ( uic->seq > maxKey ? uic->seq : maxKey );
 285         }
 286
 287         /* got it */
 288         if (maxKey)
 289             sym->liveTo = maxKey;
 290     }
 291 }
 292
 293 /*-----------------------------------------------------------------*/
 294 /* killAllAlive - mark all the definitions living with this seq    */
 295 /*-----------------------------------------------------------------*/
 296 void killAllAlive (int seq)
 297 {
 298     symbol *sym;
 299     int k;
 300
 301     for (sym = hTabFirstItem(liveRanges,&k); sym;
 302          sym = hTabNextItem(liveRanges,&k))
 303         if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
 304             sym->liveTo = seq;
 305 }
 306 /*-----------------------------------------------------------------*/
 307 /* defUsedAfterLoop - all definitions & usages before sequence num */
 308 /*-----------------------------------------------------------------*/
 309 bool defUsedAfterLoop (operand *op, int seq)
 310 {
 311     int i;
 312     iCode *ic;
 313
 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++ ) {
 317
 318             if (bitVectBitValue( OP_SYMBOL(op)->uses,i) && /* usage found */
 319                 (ic = hTabItemWithKey(iCodehTab,i))     && /*    ""       */
 320                 ic->seq > seq )                            /* & is after the seq */
 321                 return TRUE ;
 322         }
 323     }
 324
 325     return FALSE;
 326 }
 327
 328 /*-----------------------------------------------------------------*/
 329 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 330 /*-----------------------------------------------------------------*/
 331 void markLiveRanges (eBBlock *ebp, eBBlock **ebbs, int count)
 332 {
 333     iCode *ic;
 334     bitVect *defsUsed = NULL;
 335     bitVect *defsNotUsed = NULL;
 336     int i;
 337     /* for all the instructions */
 338     for (ic = ebp->sch ; ic ; ic = ic->next ) {
 339
 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);
 348             }
 349         }
 350
 351         if (SKIP_IC2(ic))
 352             continue ;
 353
 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);
 357             continue;
 358         }
 359
 360         if (ic->op == IFX && IS_SYMOP(IC_COND(ic))) {
 361             operandLUse (IC_COND(ic),ebbs,count,ic,ebp);
 362             continue ;
 363         }
 364
 365         if (IS_SYMOP(IC_LEFT(ic)))
 366             operandLUse (IC_LEFT(ic),ebbs,count,ic,ebp);
 367
 368         if (IS_SYMOP(IC_RIGHT(ic)))
 369             operandLUse (IC_RIGHT(ic),ebbs,count,ic,ebp);
 370
 371         if (POINTER_SET(ic))
 372             operandLUse(IC_RESULT(ic),ebbs,count,ic,ebp);
 373         else
 374             if (IC_RESULT(ic))
 375                 ic->defKey = IC_RESULT(ic)->key ;
 376     }
 377
 378
 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++ ) {
 383             iCode *dic;
 384
 385             if (bitVectBitValue(ebp->defSet,i) &&
 386                 (dic = hTabItemWithKey(iCodehTab,i))) {
 387
 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);
 391             }
 392         }
 393     }
 394
 395     /* special case for lastBlock in a loop: here we
 396        mark the end of all the induction variables for the
 397        loop */
 398     if (ebp->isLastInLoop && !bitVectIsZero(ebp->linds)) {
 399         for ( i = 0 ; i <= ebp->linds->size ; i++ ) {
 400             iCode *dic;
 401
 402             if (bitVectBitValue(ebp->linds,i) &&
 403                 (dic = hTabItemWithKey(iCodehTab,i))) {
 404
 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))
 409                     continue;
 410
 411                 setToRange(IC_RESULT(dic),( ebp->lSeq ),FALSE);
 412             }
 413         }
 414     }
 415
 416     /* for defnitions coming into the block if they */
 417     /* not used by itself & any of its successors   */
 418     /* they are dead */
 419     /* first union the definitions used in all successors
 420        and itself */
 421     for (i = 0; i < count ; ebbs[i++]->visited = 0);
 422     applyToSet(ebp->succList,unionDefsUsed,&defsUsed);
 423     defsUsed = bitVectUnion(defsUsed,ebp->usesDefs);
 424
 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),
 429                                 defsUsed);
 430
 431     /* mark the end of the defintions */
 432     if ( !bitVectIsZero(defsNotUsed) && ebp->sch ) {
 433         for ( i = 0 ; i < defsNotUsed->size; i++ ) {
 434             iCode *dic;
 435
 436             if (bitVectBitValue(defsNotUsed,i) &&
 437                 (dic = hTabItemWithKey(iCodehTab,i))) {
 438
 439                 setToRange(IC_RESULT(dic),( ebp->fSeq - 1),TRUE);
 440             }
 441         }
 442     }
 443
 444
 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);
 450 }
 451
 452 /*-----------------------------------------------------------------*/
 453 /* rlivePoint - for each point compute the ranges that are alive   */
 454 /*-----------------------------------------------------------------*/
 455 void rlivePoint (eBBlock **ebbs, int count)
 456 {
 457     int i;
 458
 459     /* for all blocks do */
 460     for ( i = 0 ; i < count ; i++ ) {
 461         iCode *ic;
 462
 463         /* for all instruction in the block do */
 464         for ( ic = ebbs[i]->sch ;  ic ; ic = ic->next ) {
 465             symbol *lrange;
 466             int k;
 467
 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)) {
 472
 473                 if (lrange->liveFrom <= ic->seq &&
 474                     lrange->liveTo   >= ic->seq )
 475                     ic->rlive = bitVectSetBit(ic->rlive,lrange->key);
 476             }
 477         }
 478     }
 479 }
 480
 481
 482 /*-----------------------------------------------------------------*/
 483 /* computeLiveRanges - computes the live ranges for variables      */
 484 /*-----------------------------------------------------------------*/
 485 void computeLiveRanges (eBBlock **ebbs, int count )
 486 {
 487     int i = 0 ;
 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 */
 491     iCodeSeq = 0 ;
 492     setToNull((void **)&iCodehTab);
 493     iCodehTab = newHashTable (iCodeKey);
 494     sequenceiCode(ebbs,count);
 495
 496     /* call routine to mark the from & to live ranges for
 497        variables used */
 498     setToNull((void **)&liveRanges);
 499     for ( i = 0 ; i < count; i++ )
 500         markLiveRanges (ebbs[i],ebbs,count);
 501
 502 /*     compLastUse(); */
 503     /* mark the ranges live for each point */
 504     rlivePoint (ebbs,count);
 505 }