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 #include "limits.h"
  28
  29 int iCodeSeq = 0 ;
  30 hTab *liveRanges = NULL;
  31 hTab *iCodehTab = NULL;
  32
  33 /*-----------------------------------------------------------------*/
  34 /* sequenceiCode - creates a sequence number for the iCode & add   */
  35 /*-----------------------------------------------------------------*/
  36 void sequenceiCode (eBBlock **ebbs, int count)
  37 {
  38     int i;
  39
  40     for (i = 0 ; i < count ; i++ ) {
  41
  42         iCode *ic;
  43         ebbs[i]->fSeq = iCodeSeq + 1;
  44         for ( ic = ebbs[i]->sch ; ic ; ic= ic->next) {
  45             ic->seq = ++iCodeSeq;
  46             ic->depth = ebbs[i]->depth;
  47             hTabAddItem(&iCodehTab,ic->key,ic);
  48         }
  49         ebbs[i]->lSeq = iCodeSeq ;
  50     }
  51 }
  52
  53 /*-----------------------------------------------------------------*/
  54 /* markVisited - will set the visited flag for the given Block     */
  55 /*-----------------------------------------------------------------*/
  56 DEFSETFUNC(markVisited)
  57 {
  58     eBBlock *ebp = item;
  59
  60     if (ebp->visited)
  61         return 0;
  62     ebp->visited = 1;
  63     applyToSet(ebp->succList,markVisited);
  64     return 0;
  65 }
  66
  67 /*-----------------------------------------------------------------*/
  68 /* isOpAlive - checks to see if the usage in this block is the     */
  69 /*             uses the same definitions as this one               */
  70 /*-----------------------------------------------------------------*/
  71 DEFSETFUNC(isOpAlive)
  72 {
  73     eBBlock *ebp = item;
  74     V_ARG(operand *,op);
  75     V_ARG(eBBlock *,orig);
  76     V_ARG(iCode *,ic);
  77
  78     if (ebp->visited)
  79         return 0;
  80
  81     ebp->visited = 1;
  82
  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 & */
  86     /* this point */
  87     if ( ebp == orig ||
  88          bitVectBitsInCommon(OP_DEFS(op),ebp->defSet))
  89         if (usedBetweenPoints (op,ebp->sch,ic))
  90             return 1;
  91         else {
  92             applyToSet(ebp->succList,markVisited);
  93             return 0;
  94         }
  95     else
  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))
 102             return 1;
 103
 104
 105     return (applyToSet(ebp->succList,isOpAlive,op,orig,ic));
 106 }
 107
 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)
 113 {
 114     int i;
 115
 116     /* if this is used in the remaining */
 117     if (usedInRemaining(op,ic))
 118         return 0;
 119
 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))
 123         return 0;
 124
 125     /* this is the last use */
 126     return 1;
 127 }
 128
 129 /*-----------------------------------------------------------------*/
 130 /* unionDefsUsed - unions the defsUsed in a block                  */
 131 /*-----------------------------------------------------------------*/
 132 DEFSETFUNC(unionDefsUsed)
 133 {
 134     eBBlock *ebp = item;
 135     V_ARG(bitVect **,bvp);
 136
 137     if (ebp->visited)
 138         return 0;
 139
 140     ebp->visited = 1;
 141
 142     *bvp = bitVectUnion(*bvp, ebp->usesDefs);
 143     applyToSet(ebp->succList,unionDefsUsed,bvp);
 144     return 0;
 145 }
 146
 147 /*-----------------------------------------------------------------*/
 148 /* setFromRange - sets the from range of a given operand           */
 149 /*-----------------------------------------------------------------*/
 150 void setFromRange (operand *op, int from)
 151 {
 152     /* only for compiler defined temporaries */
 153     if (!IS_ITEMP(op))
 154         return ;
 155
 156     hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
 157
 158     if (op->isaddr)
 159         OP_SYMBOL(op)->isptr = 1;
 160
 161     if (!OP_LIVEFROM(op) ||
 162         OP_LIVEFROM(op) > from)
 163         OP_LIVEFROM(op) = from;
 164 }
 165
 166 /*-----------------------------------------------------------------*/
 167 /* setToRange - set the range to for an operand                    */
 168 /*-----------------------------------------------------------------*/
 169 void setToRange (operand *op,int to, bool check)
 170 {
 171     /* only for compiler defined temps */
 172     if (!IS_ITEMP(op))
 173         return ;
 174
 175     OP_SYMBOL(op)->key = op->key;
 176     hTabAddItemIfNotP (&liveRanges,op->key,OP_SYMBOL(op));
 177
 178     if (op->isaddr)
 179         OP_SYMBOL(op)->isptr = 1;
 180
 181     if (check)
 182         if (!OP_LIVETO(op))
 183             OP_LIVETO(op) = to;
 184         else ;
 185     else
 186         OP_LIVETO(op) = to;
 187 }
 188
 189 /*-----------------------------------------------------------------*/
 190 /* firstDeOf - finds the first definition in seq for op            */
 191 /*-----------------------------------------------------------------*/
 192 static iCode *firstDefOf (operand *op)
 193 {
 194     int i;
 195     iCode *ric=NULL,*lic=NULL;
 196     int fSeq = INT_MAX;
 197
 198     if (!OP_DEFS(op))
 199         return NULL;
 200
 201     for (i=0; i < OP_DEFS(op)->size ;i++) {
 202         if (bitVectBitValue(OP_DEFS(op),i) &&
 203             (lic = hTabItemWithKey(iCodehTab,i)) &&
 204             lic->seq < fSeq) {
 205
 206             fSeq = lic->seq ;
 207             ric = lic;
 208         }
 209     }
 210     return ric;
 211 }
 212 /*-----------------------------------------------------------------*/
 213 /* useDefLoopCheck - check for uses before init inside loops       */
 214 /*-----------------------------------------------------------------*/
 215 static void useDefLoopCheck(operand *op,iCode *ic)
 216 {
 217     /* this is for situations like the following
 218        int a,b;
 219
 220        while (...) {
 221             a = ... ;
 222             ...
 223             _some_usage_of_b_;
 224             ...
 225             b = ... ;
 226             }
 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 */
 230
 231     int i =0, fdSeq ;
 232     int er=0;
 233     iCode *tic ;
 234
 235     /* get the first definition */
 236     if (!(tic = firstDefOf(op)))
 237         return ;
 238
 239     fdSeq = tic->seq;
 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)) &&
 245             tic->seq < fdSeq){
 246             er = 1;
 247             break;
 248         }
 249     }
 250
 251     /* found a usage without definition */
 252     if (er) {
 253         if (OP_SYMBOL(op)->isreqv && SPIL_LOC(op) ) {
 254
 255             werror(W_LOCAL_NOINIT,
 256                    SPIL_LOC(op)->name,
 257                    ic->filename,ic->lineno);
 258         } else {
 259
 260             werror(W_LOCAL_NOINIT,
 261                    OP_SYMBOL(op)->name,
 262                    ic->filename,ic->lineno);
 263         }
 264         OP_SYMBOL(op)->isspilt = 1;
 265     }
 266 }
 267
 268
 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)
 274 {
 275     setFromRange(op,ic->seq);
 276     if (ic->depth)
 277         OP_SYMBOL(op)->used += (((unsigned int)1 << ic->depth) + 1);
 278     else
 279         OP_SYMBOL(op)->used += 1;
 280
 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);
 290         }
 291         op = operandFromOperand(op);
 292         setToRange(op,torange,FALSE);
 293     }
 294     ic->uses = bitVectSetBit(ic->uses,op->key);
 295
 296     if (!OP_SYMBOL(op)->udChked)
 297     {
 298         link *type = operandType(op);
 299         link *etype = getSpec(type);
 300
 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)       &&
 306             !IS_FUNC(type)            &&
 307             ic->op != ADDRESS_OF      &&
 308             !IS_STATIC(etype)         ) {
 309
 310             if (bitVectIsZero(op->usesDefs)) {
 311                 OP_SYMBOL(op)->isspilt = 1;
 312
 313                 if (OP_SYMBOL(op)->isreqv &&
 314                     !OP_SYMBOL(op)->_isparm && SPIL_LOC(op) ) {
 315
 316                     werror(W_LOCAL_NOINIT,
 317                            SPIL_LOC(op)->name,
 318                            ic->filename,ic->lineno);
 319                 } else {
 320
 321                     werror(W_LOCAL_NOINIT,
 322                            OP_SYMBOL(op)->name,
 323                            ic->filename,ic->lineno);
 324                 }
 325             } else {
 326                 if (ebp->depth && op->usesDefs &&
 327                     !OP_SYMBOL(op)->_isparm) {
 328                     /* check non-inits inside loops */
 329                     useDefLoopCheck(op,ic);
 330                 }
 331             }
 332         }
 333     }
 334     return op;
 335 }
 336
 337 /*-----------------------------------------------------------------*/
 338 /* killAllAlive - mark all the definitions living with this seq    */
 339 /*-----------------------------------------------------------------*/
 340 void killAllAlive (int seq)
 341 {
 342     symbol *sym;
 343     int k;
 344
 345     for (sym = hTabFirstItem(liveRanges,&k); sym;
 346          sym = hTabNextItem(liveRanges,&k))
 347         if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
 348             sym->liveTo = seq;
 349 }
 350 /*-----------------------------------------------------------------*/
 351 /* defUsedAfterLoop - all definitions & usages before sequence num */
 352 /*-----------------------------------------------------------------*/
 353 bool defUsedAfterLoop (operand *op, int seq)
 354 {
 355     int i;
 356     iCode *ic;
 357
 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++ ) {
 361
 362             if (bitVectBitValue( OP_SYMBOL(op)->uses,i) && /* usage found */
 363                 (ic = hTabItemWithKey(iCodehTab,i))     && /*    ""       */
 364                 ic->seq > seq )                            /* & is after the seq */
 365                 return TRUE ;
 366         }
 367     }
 368
 369     return FALSE;
 370 }
 371
 372 /*-----------------------------------------------------------------*/
 373 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 374 /*-----------------------------------------------------------------*/
 375 void markLiveRanges (eBBlock *ebp, eBBlock **ebbs, int count)
 376 {
 377     iCode *ic;
 378     bitVect *defsUsed = NULL;
 379     bitVect *defsNotUsed = NULL;
 380     int i;
 381     /* for all the instructions */
 382     for (ic = ebp->sch ; ic ; ic = ic->next ) {
 383
 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);
 392             }
 393         }
 394
 395         if (SKIP_IC2(ic))
 396             continue ;
 397
 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);
 401             continue;
 402         }
 403
 404         if (ic->op == IFX && IS_SYMOP(IC_COND(ic))) {
 405             operandLUse (IC_COND(ic),ebbs,count,ic,ebp);
 406             continue ;
 407         }
 408
 409         if (IS_SYMOP(IC_LEFT(ic)))
 410             operandLUse (IC_LEFT(ic),ebbs,count,ic,ebp);
 411
 412         if (IS_SYMOP(IC_RIGHT(ic)))
 413             operandLUse (IC_RIGHT(ic),ebbs,count,ic,ebp);
 414
 415         if (POINTER_SET(ic))
 416             operandLUse(IC_RESULT(ic),ebbs,count,ic,ebp);
 417         else
 418             if (IC_RESULT(ic))
 419                 ic->defKey = IC_RESULT(ic)->key ;
 420     }
 421
 422
 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++ ) {
 427             iCode *dic;
 428
 429             if (bitVectBitValue(ebp->ldefs,i) &&
 430                 (dic = hTabItemWithKey(iCodehTab,i))) {
 431
 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);
 435             }
 436         }
 437     }
 438
 439     /* special case for lastBlock in a loop: here we
 440        mark the end of all the induction variables for the
 441        loop */
 442     if (ebp->isLastInLoop && !bitVectIsZero(ebp->linds)) {
 443         for ( i = 0 ; i <= ebp->linds->size ; i++ ) {
 444             iCode *dic;
 445
 446             if (bitVectBitValue(ebp->linds,i) &&
 447                 (dic = hTabItemWithKey(iCodehTab,i))) {
 448
 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))
 453                     continue;
 454
 455                 setToRange(IC_RESULT(dic),( ebp->lSeq ),FALSE);
 456             }
 457         }
 458     }
 459
 460     /* for defnitions coming into the block if they */
 461     /* not used by itself & any of its successors   */
 462     /* they are dead */
 463     /* first union the definitions used in all successors
 464        and itself */
 465     for (i = 0; i < count ; ebbs[i++]->visited = 0);
 466     applyToSet(ebp->succList,unionDefsUsed,&defsUsed);
 467     defsUsed = bitVectUnion(defsUsed,ebp->usesDefs);
 468
 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),
 473                                 defsUsed);
 474
 475     /* mark the end of the defintions */
 476     if ( !bitVectIsZero(defsNotUsed) && ebp->sch ) {
 477         for ( i = 0 ; i < defsNotUsed->size; i++ ) {
 478             iCode *dic;
 479
 480             if (bitVectBitValue(defsNotUsed,i) &&
 481                 (dic = hTabItemWithKey(iCodehTab,i))) {
 482
 483                 setToRange(IC_RESULT(dic),( ebp->fSeq - 1),TRUE);
 484             }
 485         }
 486     }
 487
 488
 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);
 494 }
 495
 496 /*-----------------------------------------------------------------*/
 497 /* rlivePoint - for each point compute the ranges that are alive   */
 498 /*-----------------------------------------------------------------*/
 499 void rlivePoint (eBBlock **ebbs, int count)
 500 {
 501     int i;
 502
 503     /* for all blocks do */
 504     for ( i = 0 ; i < count ; i++ ) {
 505         iCode *ic;
 506
 507         /* for all instruction in the block do */
 508         for ( ic = ebbs[i]->sch ;  ic ; ic = ic->next ) {
 509             symbol *lrange;
 510             int k;
 511
 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)) {
 516
 517                     /* if it is live then add the lrange to ic->rlive */
 518                 if (lrange->liveFrom <= ic->seq &&
 519                     lrange->liveTo   >= ic->seq ) {
 520                         lrange->isLiveFcall = (ic->op == CALL || ic->op == PCALL);
 521                         ic->rlive = bitVectSetBit(ic->rlive,lrange->key);
 522                 }
 523             }
 524         }
 525     }
 526 }
 527
 528
 529 /*-----------------------------------------------------------------*/
 530 /* computeLiveRanges - computes the live ranges for variables      */
 531 /*-----------------------------------------------------------------*/
 532 void computeLiveRanges (eBBlock **ebbs, int count )
 533 {
 534     int i = 0 ;
 535     /* sequence the code the live ranges are computed
 536        in terms of this sequence additionally the
 537        routine will also create a hashtable of instructions */
 538     iCodeSeq = 0 ;
 539     setToNull((void **)&iCodehTab);
 540     iCodehTab = newHashTable (iCodeKey);
 541     sequenceiCode(ebbs,count);
 542
 543     /* call routine to mark the from & to live ranges for
 544        variables used */
 545     setToNull((void **)&liveRanges);
 546     for ( i = 0 ; i < count; i++ )
 547         markLiveRanges (ebbs[i],ebbs,count);
 548
 549     /* mark the ranges live for each point */
 550     rlivePoint (ebbs,count);
 551 }