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 hTab *iCodeSeqhTab = NULL;
  33
  34 /*-----------------------------------------------------------------*/
  35 /* sequenceiCode - creates a sequence number for the iCode & add   */
  36 /*-----------------------------------------------------------------*/
  37 void
  38 sequenceiCode (eBBlock ** ebbs, int count)
  39 {
  40   int i;
  41
  42   for (i = 0; i < count; i++)
  43     {
  44
  45       iCode *ic;
  46       ebbs[i]->fSeq = iCodeSeq + 1;
  47       for (ic = ebbs[i]->sch; ic; ic = ic->next)
  48         {
  49           ic->seq = ++iCodeSeq;
  50           ic->depth = ebbs[i]->depth;
  51           hTabAddItem (&iCodehTab, ic->key, ic);
  52           hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
  53         }
  54       ebbs[i]->lSeq = iCodeSeq;
  55     }
  56 }
  57
  58 /*-----------------------------------------------------------------*/
  59 /* markVisited - will set the visited flag for the given Block     */
  60 /*-----------------------------------------------------------------*/
  61 DEFSETFUNC (markVisited)
  62 {
  63   eBBlock *ebp = item;
  64
  65   if (ebp->visited)
  66     return 0;
  67   ebp->visited = 1;
  68   applyToSet (ebp->succList, markVisited);
  69   return 0;
  70 }
  71
  72 /*-----------------------------------------------------------------*/
  73 /* isOpAlive - checks to see if the usage in this block is the     */
  74 /*             uses the same definitions as this one               */
  75 /*-----------------------------------------------------------------*/
  76 DEFSETFUNC (isOpAlive)
  77 {
  78   eBBlock *ebp = item;
  79   V_ARG (operand *, op);
  80   V_ARG (eBBlock *, orig);
  81   V_ARG (iCode *, ic);
  82
  83   if (ebp->visited)
  84     return 0;
  85
  86   ebp->visited = 1;
  87
  88   /* if we have reached the originating block */
  89   /* or this block has some definiton for it  */
  90   /* then check if it is used between start & */
  91   /* this point */
  92   if (ebp == orig ||
  93       bitVectBitsInCommon (OP_DEFS (op), ebp->defSet))
  94     if (usedBetweenPoints (op, ebp->sch, ic))
  95       return 1;
  96     else
  97       {
  98         applyToSet (ebp->succList, markVisited);
  99         return 0;
 100       }
 101   else
 102     /* choosing this more expensive one since
 103        killDeadCode will take away some definitions
 104        but there is not way right now to take away
 105        the usage information for the corresponding
 106        usages, this will lead to longer live ranges */
 107   if (usedInRemaining (op, ebp->sch))
 108     return 1;
 109
 110
 111   return (applyToSet (ebp->succList, isOpAlive, op, orig, ic));
 112 }
 113
 114 /*-----------------------------------------------------------------*/
 115 /* isLastUse - return TRUE if no usage of this operand after this  */
 116 /*-----------------------------------------------------------------*/
 117 int
 118 isLastUse (operand * op, eBBlock * ebp, iCode * ic,
 119            eBBlock ** ebbs, int count)
 120 {
 121   int i;
 122
 123   /* if this is used in the remaining */
 124   if (usedInRemaining (op, ic))
 125     return 0;
 126
 127   if (getenv ("SDCC_LRKLAUS"))
 128     {
 129       /* if not then check any of the following blocks use it */
 130       for (i = 0; i < count; i++)
 131         {
 132           if (ebbs[i]->fSeq <= ebp->fSeq)
 133             continue;
 134           if (usedInRemaining (op, ebbs[i]->sch))
 135             return 0;
 136         }
 137     }
 138   else
 139     {
 140       /* if not then check any of the successor blocks use it */
 141       for (i = 0; i < count;)
 142         ebbs[i++]->visited = 0;
 143       if (applyToSet (ebp->succList, isOpAlive, op, ebp, ic))
 144         return 0;
 145     }
 146
 147   /* this is the last use */
 148   return 1;
 149 }
 150
 151 /*-----------------------------------------------------------------*/
 152 /* unionDefsUsed - unions the defsUsed in a block                  */
 153 /*-----------------------------------------------------------------*/
 154 DEFSETFUNC (unionDefsUsed)
 155 {
 156   eBBlock *ebp = item;
 157   V_ARG (bitVect **, bvp);
 158
 159   if (ebp->visited)
 160     return 0;
 161
 162   ebp->visited = 1;
 163
 164   *bvp = bitVectUnion (*bvp, ebp->usesDefs);
 165   applyToSet (ebp->succList, unionDefsUsed, bvp);
 166   return 0;
 167 }
 168
 169 /*-----------------------------------------------------------------*/
 170 /* setFromRange - sets the from range of a given operand           */
 171 /*-----------------------------------------------------------------*/
 172 void
 173 setFromRange (operand * op, int from)
 174 {
 175   /* only for compiler defined temporaries */
 176   if (!IS_ITEMP (op))
 177     return;
 178
 179   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 180
 181   if (op->isaddr)
 182     OP_SYMBOL (op)->isptr = 1;
 183
 184   if (!OP_LIVEFROM (op) ||
 185       OP_LIVEFROM (op) > from)
 186     OP_LIVEFROM (op) = from;
 187 }
 188
 189 /*-----------------------------------------------------------------*/
 190 /* setToRange - set the range to for an operand                    */
 191 /*-----------------------------------------------------------------*/
 192 void
 193 setToRange (operand * op, int to, bool check)
 194 {
 195   /* only for compiler defined temps */
 196   if (!IS_ITEMP (op))
 197     return;
 198
 199   OP_SYMBOL (op)->key = op->key;
 200   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 201
 202   if (op->isaddr)
 203     OP_SYMBOL (op)->isptr = 1;
 204
 205   if (check)
 206     if (!OP_LIVETO (op))
 207       OP_LIVETO (op) = to;
 208     else;
 209   else
 210     OP_LIVETO (op) = to;
 211 }
 212
 213 /*-----------------------------------------------------------------*/
 214 /* firstDeOf - finds the first definition in seq for op            */
 215 /*-----------------------------------------------------------------*/
 216 static iCode *
 217 firstDefOf (operand * op)
 218 {
 219   int i;
 220   iCode *ric = NULL, *lic = NULL;
 221   int fSeq = INT_MAX;
 222
 223   if (!OP_DEFS (op))
 224     return NULL;
 225
 226   for (i = 0; i < OP_DEFS (op)->size; i++)
 227     {
 228       if (bitVectBitValue (OP_DEFS (op), i) &&
 229           (lic = hTabItemWithKey (iCodehTab, i)) &&
 230           lic->seq < fSeq)
 231         {
 232
 233           fSeq = lic->seq;
 234           ric = lic;
 235         }
 236     }
 237   return ric;
 238 }
 239 /*-----------------------------------------------------------------*/
 240 /* useDefLoopCheck - check for uses before init inside loops       */
 241 /*-----------------------------------------------------------------*/
 242 static void
 243 useDefLoopCheck (operand * op, iCode * ic)
 244 {
 245   /* this is for situations like the following
 246      int a,b;
 247
 248      while (...) {
 249      a = ... ;
 250      ...
 251      _some_usage_of_b_;
 252      ...
 253      b = ... ;
 254      }
 255      in this case the definition of 'b' will flow to the usages
 256      but register allocator cannot handle these situations.so
 257      will mark as spilt */
 258
 259   int i = 0, fdSeq;
 260   int er = 0;
 261   iCode *tic;
 262
 263   /* get the first definition */
 264   if (!(tic = firstDefOf (op)))
 265     return;
 266
 267   fdSeq = tic->seq;
 268   /* now go thru the usages & make sure they follow
 269      the first definition */
 270   for (i = 0; i <= OP_USES (op)->size; i++)
 271     {
 272       if (bitVectBitValue (OP_USES (op), i) &&
 273           (tic = hTabItemWithKey (iCodehTab, i)) &&
 274           tic->seq < fdSeq)
 275         {
 276           er = 1;
 277           break;
 278         }
 279     }
 280
 281   /* found a usage without definition */
 282   if (er)
 283     {
 284       if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
 285         {
 286
 287           werror (W_LOCAL_NOINIT,
 288                   SPIL_LOC (op)->name,
 289                   ic->filename, ic->lineno);
 290         }
 291       else
 292         {
 293
 294           werror (W_LOCAL_NOINIT,
 295                   OP_SYMBOL (op)->name,
 296                   ic->filename, ic->lineno);
 297         }
 298 #if 0 // this will create a segfault: bug #498971
 299       OP_SYMBOL (op)->isspilt = 1;
 300 #endif
 301     }
 302 }
 303
 304
 305 /*-----------------------------------------------------------------*/
 306 /* operandLUse - check and set the last use for a given operand    */
 307 /*-----------------------------------------------------------------*/
 308 operand *
 309 operandLUse (operand * op, eBBlock ** ebbs,
 310              int count, iCode * ic, eBBlock * ebp)
 311 {
 312   setFromRange (op, ic->seq);
 313   if (ic->depth)
 314     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 315   else
 316     OP_SYMBOL (op)->used += 1;
 317
 318   if (isLastUse (op, ebp, ic->next, ebbs, count) ||
 319       (OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
 320     {
 321       int torange = ic->seq;
 322
 323       /* if this is a SEND then the toRange should be extended
 324          to the call */
 325       if (ic->op == SEND)
 326         {
 327           iCode *lic ;
 328           for (lic = ic->next ; lic ; lic = lic->next)
 329             {
 330               if (lic->op == CALL || lic->op == PCALL)
 331                 break;
 332             }
 333           /* found it : mark */
 334           if (lic)
 335             torange = lic->prev->seq;
 336         }
 337       /* if this is the last use then if this block belongs
 338          to a  loop &  some definition  comes into the loop
 339          then extend the live range to  the end of the loop */
 340       if (getenv ("SDCC_LRKLAUS"))
 341         {
 342           if (ebp->KpartOfLoop)
 343             {
 344               region *aloop;
 345
 346               aloop = setFirstItem (ebp->KpartOfLoop);
 347               for (; aloop; aloop = setNextItem (ebp->KpartOfLoop))
 348                 {
 349                   if (hasIncomingDefs (aloop, op))
 350                     torange = findLoopEndSeq (aloop);
 351                 }
 352             }
 353         }
 354       else
 355         {
 356           if (ebp->partOfLoop
 357               && hasIncomingDefs (ebp->partOfLoop, op))
 358             {
 359               torange = findLoopEndSeq (ebp->partOfLoop);
 360             }
 361         }
 362
 363       op = operandFromOperand (op);
 364       setToRange (op, torange, FALSE);
 365     }
 366   ic->uses = bitVectSetBit (ic->uses, op->key);
 367
 368   if (!OP_SYMBOL (op)->udChked)
 369     {
 370       sym_link *type = operandType (op);
 371       sym_link *etype = getSpec (type);
 372
 373       OP_SYMBOL (op)->udChked = 1;
 374       /* good place to check if unintialised */
 375       if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
 376           OP_SYMBOL (op)->islocal &&
 377           !IS_AGGREGATE (type) &&
 378           !IS_FUNC (type) &&
 379           ic->op != ADDRESS_OF &&
 380           !IS_STATIC (etype))
 381         {
 382
 383           if (bitVectIsZero (op->usesDefs) && OP_SYMBOL(op)->ival==NULL)
 384             {
 385               OP_SYMBOL (op)->isspilt = 1;
 386
 387               if (OP_SYMBOL (op)->isreqv &&
 388                   !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
 389                 {
 390
 391                   werror (W_LOCAL_NOINIT,
 392                           SPIL_LOC (op)->name,
 393                           ic->filename, ic->lineno);
 394                 }
 395               else
 396                 {
 397
 398                   werror (W_LOCAL_NOINIT,
 399                           OP_SYMBOL (op)->name,
 400                           ic->filename, ic->lineno);
 401                 }
 402             }
 403           else
 404             {
 405               if (ebp->depth && op->usesDefs &&
 406                   !OP_SYMBOL (op)->_isparm)
 407                 {
 408                   /* check non-inits inside loops */
 409                   useDefLoopCheck (op, ic);
 410                 }
 411             }
 412         }
 413     }
 414   return op;
 415 }
 416
 417 /*-----------------------------------------------------------------*/
 418 /* killAllAlive - mark all the definitions living with this seq    */
 419 /*-----------------------------------------------------------------*/
 420 void
 421 killAllAlive (int seq)
 422 {
 423   symbol *sym;
 424   int k;
 425
 426   for (sym = hTabFirstItem (liveRanges, &k); sym;
 427        sym = hTabNextItem (liveRanges, &k))
 428     if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
 429       sym->liveTo = seq;
 430 }
 431 /*-----------------------------------------------------------------*/
 432 /* defUsedAfterLoop - all definitions & usages before sequence num */
 433 /*-----------------------------------------------------------------*/
 434 bool
 435 defUsedAfterLoop (operand * op, int seq)
 436 {
 437   int i;
 438   iCode *ic;
 439
 440   /* check for the usages first */
 441   if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
 442     {
 443       for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
 444         {
 445
 446           if (bitVectBitValue (OP_SYMBOL (op)->uses, i) &&      /* usage found */
 447               (ic = hTabItemWithKey (iCodehTab, i)) &&  /*    ""       */
 448               ic->seq > seq)    /* & is after the seq */
 449             return TRUE;
 450         }
 451     }
 452
 453   return FALSE;
 454 }
 455
 456 /*-----------------------------------------------------------------*/
 457 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 458 /*-----------------------------------------------------------------*/
 459 void
 460 markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
 461 {
 462   iCode *ic;
 463   bitVect *defsUsed = NULL;
 464   bitVect *defsNotUsed = NULL;
 465   int i;
 466
 467   /* for all the instructions */
 468   for (ic = ebp->sch; ic; ic = ic->next)
 469     {
 470       if (ic->op == CALL || ic->op == PCALL)
 471         {
 472           setFromRange (IC_RESULT (ic), ic->seq);
 473           /* if the result has no usage then
 474              mark this as the end of its life too
 475              and take it away from the defs for the block */
 476           if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
 477             {
 478               setToRange (IC_RESULT (ic), ic->seq, FALSE);
 479               bitVectUnSetBit (ebp->defSet, ic->key);
 480             }
 481         }
 482
 483       if (SKIP_IC2 (ic))
 484         continue;
 485
 486       /* take care of the special icodes first */
 487       if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
 488         {
 489           operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
 490           continue;
 491         }
 492
 493       if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
 494         {
 495           operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
 496           continue;
 497         }
 498
 499       if (IS_SYMOP (IC_LEFT (ic)))
 500         operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
 501
 502       if (IS_SYMOP (IC_RIGHT (ic)))
 503         operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
 504
 505       if (POINTER_SET (ic))
 506         operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
 507       else if (IC_RESULT (ic))
 508         ic->defKey = IC_RESULT (ic)->key;
 509     }
 510
 511
 512   /* for all the definitions in the block */
 513   /* compute and set the live from        */
 514   if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
 515     {
 516       for (i = 0; i < ebp->ldefs->size; i++)
 517         {
 518           iCode *dic;
 519
 520           if (bitVectBitValue (ebp->ldefs, i) &&
 521               (dic = hTabItemWithKey (iCodehTab, i)))
 522             {
 523
 524               /* if the definition has a from & it is greater */
 525               /* than the defininng iCode->seq then change it */
 526               setFromRange (IC_RESULT (dic), dic->seq);
 527             }
 528         }
 529     }
 530
 531   /* special case for lastBlock in a loop: here we
 532      mark the end of all the induction variables for the
 533      loop */
 534   if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
 535     {
 536       for (i = 0; i <= ebp->linds->size; i++)
 537         {
 538           iCode *dic;
 539
 540           if (bitVectBitValue (ebp->linds, i) &&
 541               (dic = hTabItemWithKey (iCodehTab, i)))
 542             {
 543
 544               /* if this is a register equvalent make sure
 545                  it is not defined or used anywhere after the loop */
 546               if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
 547                   defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
 548                 continue;
 549
 550               setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
 551             }
 552         }
 553     }
 554
 555   /* for defnitions coming into the block if they */
 556   /* not used by itself & any of its successors   */
 557   /* they are dead */
 558   /* first union the definitions used in all successors
 559      and itself */
 560   for (i = 0; i < count; ebbs[i++]->visited = 0);
 561   applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
 562   defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
 563
 564   /* now subract the result of these unions from */
 565   /* the incoming definitions this will give the */
 566   /* definitions that are never used in the future */
 567   defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
 568                                defsUsed);
 569
 570   /* mark the end of the defintions */
 571   if (!bitVectIsZero (defsNotUsed) && ebp->sch)
 572     {
 573       for (i = 0; i < defsNotUsed->size; i++)
 574         {
 575           iCode *dic;
 576
 577           if (bitVectBitValue (defsNotUsed, i) &&
 578               (dic = hTabItemWithKey (iCodehTab, i)))
 579             {
 580               setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
 581             }
 582         }
 583     }
 584
 585
 586   /* if we reach a lock with noPath to it then kill all
 587      the live ranges alive at this point */
 588 /*     if (ebp->noPath || ebp->entryLabel == returnLabel) */
 589   if (ebp->entryLabel == returnLabel)
 590     killAllAlive (ebp->fSeq);
 591 }
 592
 593 /*-----------------------------------------------------------------*/
 594 /* rlivePoint - for each point compute the ranges that are alive   */
 595 /*-----------------------------------------------------------------*/
 596 void
 597 rlivePoint (eBBlock ** ebbs, int count)
 598 {
 599     int i;
 600
 601     /* for all blocks do */
 602     for (i = 0; i < count; i++) {
 603         iCode *ic;
 604
 605         /* for all instruction in the block do */
 606         for (ic = ebbs[i]->sch; ic; ic = ic->next) {
 607             symbol *lrange;
 608             int k;
 609
 610             ic->rlive = newBitVect (operandKey);
 611             /* for all symbols in the liverange table */
 612             for (lrange = hTabFirstItem (liveRanges, &k); lrange;
 613                  lrange = hTabNextItem (liveRanges, &k)) {
 614
 615                 /* if it is live then add the lrange to ic->rlive */
 616                 if (lrange->liveFrom <= ic->seq &&
 617                     lrange->liveTo >= ic->seq) {
 618                     lrange->isLiveFcall |= ((lrange->liveFrom < ic->seq) &&
 619                                             (ic->op == CALL || ic->op == PCALL || ic->op == SEND));
 620                     if (ic->op == CALL && lrange->liveFrom == ic->seq) continue;
 621                     ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
 622                 }
 623             }
 624 #if 0
 625             /* overlapping live ranges should be eliminated */
 626             if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
 627                 if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic))   && /* left & right share the same spil location */
 628                     OP_SYMBOL(IC_RESULT(ic))->isreqv                    && /* left of assign is a register requivalent */
 629                     !OP_SYMBOL(IC_RIGHT(ic))->isreqv                    && /* right side is not */
 630                     OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key           && /* right side live beyond this point */
 631                     bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 )        {  /* left has multiple definitions */
 632                     SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
 633                 }
 634             }
 635 #endif
 636         }
 637     }
 638 }
 639
 640 /*-----------------------------------------------------------------*/
 641 /* computeClash - find out which live ranges collide with others   */
 642 /*-----------------------------------------------------------------*/
 643 static void computeClash ()
 644 {
 645     hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
 646     void *item;
 647     symbol *outer, *inner;
 648     int key, key1;
 649
 650     /* have to make a copy of the liveRanges hashTable :: UGHH .*/
 651     for (item = hTabFirstItem(liveRanges,&key); item ;
 652          item = hTabNextItem(liveRanges,&key)) {
 653         hTabAddItem(&lRangeCopy,key,item);
 654     }
 655
 656     /* outerloop : for each liverange do */
 657     for (outer = hTabFirstItem(liveRanges,&key); outer ;
 658          outer = hTabNextItem(liveRanges,&key)) {
 659
 660         /* if the liveFrom & To are the same then skip,
 661            could happen for unused return values from functions */
 662         if (outer->liveFrom == outer->liveTo) continue;
 663
 664         /* innerloop : for the inner loop we can start from the
 665            item after the outer loop */
 666         inner = hTabFirstItemWK (lRangeCopy,outer->key);
 667         inner = hTabNextItem (lRangeCopy,&key1 );
 668         for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
 669
 670             if (inner->liveFrom == inner->liveTo) continue;
 671             if (inner->liveTo < outer->liveFrom)  continue;
 672             if (inner->liveFrom > outer->liveTo)  continue;
 673
 674             /* if one of them are being defined where the other
 675                one end , then no overlap (i.e. they can goto same registers */
 676             if (inner->liveFrom == outer->liveTo ||
 677                 outer->liveFrom == inner->liveTo) continue;
 678
 679             /* so they overlap : set both their clashes */
 680             inner->clashes = bitVectSetBit(inner->clashes,outer->key);
 681             outer->clashes = bitVectSetBit(outer->clashes,inner->key);
 682
 683             /* check if they share the same spillocation */
 684             if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
 685                 SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
 686                 if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
 687                 else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
 688                 else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
 689                 else SYM_SPIL_LOC(inner)=NULL;
 690             }
 691
 692         }
 693     }
 694 }
 695
 696 /*-----------------------------------------------------------------*/
 697 /* allDefsOutOfRange - all definitions are out of a range          */
 698 /*-----------------------------------------------------------------*/
 699 bool
 700 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 701 {
 702   int i;
 703
 704   if (!defs)
 705     return TRUE;
 706
 707   for (i = 0; i < defs->size; i++)
 708     {
 709       iCode *ic;
 710
 711       if (bitVectBitValue (defs, i) &&
 712           (ic = hTabItemWithKey (iCodehTab, i)) &&
 713           (ic->seq >= fseq && ic->seq <= toseq))
 714
 715         return FALSE;
 716
 717     }
 718
 719   return TRUE;
 720 }
 721
 722 /*-----------------------------------------------------------------*/
 723 /* notUsedInBlock - not used in this block                         */
 724 /*-----------------------------------------------------------------*/
 725 int
 726 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 727 {
 728   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 729           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 730           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 731 }
 732
 733
 734 /*-----------------------------------------------------------------*/
 735 /* computeLiveRanges - computes the live ranges for variables      */
 736 /*-----------------------------------------------------------------*/
 737 void
 738 computeLiveRanges (eBBlock ** ebbs, int count)
 739 {
 740   int i = 0;
 741   /* sequence the code the live ranges are computed
 742      in terms of this sequence additionally the
 743      routine will also create a hashtable of instructions */
 744   iCodeSeq = 0;
 745   setToNull ((void *) &iCodehTab);
 746   iCodehTab = newHashTable (iCodeKey);
 747   setToNull ((void *) &iCodeSeqhTab);
 748   iCodeSeqhTab = newHashTable (iCodeKey);
 749   sequenceiCode (ebbs, count);
 750
 751   if (getenv ("SDCC_LRKLAUS"))
 752     {
 753       /* add blocks between loop blocks as part of that loop */
 754       addLoopBlocks (ebbs, count);
 755     }
 756
 757   /* call routine to mark the from & to live ranges for
 758      variables used */
 759   setToNull ((void *) &liveRanges);
 760   for (i = 0; i < count; i++)
 761     markLiveRanges (ebbs[i], ebbs, count);
 762
 763   /* mark the ranges live for each point */
 764   rlivePoint (ebbs, count);
 765
 766   /* compute which overlaps with what */
 767   computeClash();
 768 }
 769