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