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
 431   /* for all the instructions */
 432   for (ic = ebp->sch; ic; ic = ic->next)
 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               setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
 545             }
 546         }
 547     }
 548
 549
 550   /* if we reach a lock with noPath to it then kill all
 551      the live ranges alive at this point */
 552 /*     if (ebp->noPath || ebp->entryLabel == returnLabel) */
 553   if (ebp->entryLabel == returnLabel)
 554     killAllAlive (ebp->fSeq);
 555 }
 556
 557 /*-----------------------------------------------------------------*/
 558 /* rlivePoint - for each point compute the ranges that are alive   */
 559 /*-----------------------------------------------------------------*/
 560 void
 561 rlivePoint (eBBlock ** ebbs, int count)
 562 {
 563     int i;
 564
 565     /* for all blocks do */
 566     for (i = 0; i < count; i++) {
 567         iCode *ic;
 568
 569         /* for all instruction in the block do */
 570         for (ic = ebbs[i]->sch; ic; ic = ic->next) {
 571             symbol *lrange;
 572             int k;
 573
 574             ic->rlive = newBitVect (operandKey);
 575             /* for all symbols in the liverange table */
 576             for (lrange = hTabFirstItem (liveRanges, &k); lrange;
 577                  lrange = hTabNextItem (liveRanges, &k)) {
 578
 579                 /* if it is live then add the lrange to ic->rlive */
 580                 if (lrange->liveFrom <= ic->seq &&
 581                     lrange->liveTo >= ic->seq) {
 582                     lrange->isLiveFcall |= ((lrange->liveFrom < ic->seq) &&
 583                                             (ic->op == CALL || ic->op == PCALL || ic->op == SEND));
 584                     if (ic->op == CALL && lrange->liveFrom == ic->seq) continue;
 585                     ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
 586                 }
 587             }
 588 #if 0
 589             /* overlapping live ranges should be eliminated */
 590             if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
 591                 if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic))   && /* left & right share the same spil location */
 592                     OP_SYMBOL(IC_RESULT(ic))->isreqv                    && /* left of assign is a register requivalent */
 593                     !OP_SYMBOL(IC_RIGHT(ic))->isreqv                    && /* right side is not */
 594                     OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key           && /* right side live beyond this point */
 595                     bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 )        {  /* left has multiple definitions */
 596                     SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
 597                 }
 598             }
 599 #endif
 600         }
 601     }
 602 }
 603
 604 /*-----------------------------------------------------------------*/
 605 /* computeClash - find out which live ranges collide with others   */
 606 /*-----------------------------------------------------------------*/
 607 static void computeClash ()
 608 {
 609     hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
 610     void *item;
 611     symbol *outer, *inner;
 612     int key, key1;
 613
 614     /* have to make a copy of the liveRanges hashTable :: UGHH .*/
 615     for (item = hTabFirstItem(liveRanges,&key); item ;
 616          item = hTabNextItem(liveRanges,&key)) {
 617         hTabAddItem(&lRangeCopy,key,item);
 618     }
 619
 620     /* outerloop : for each liverange do */
 621     for (outer = hTabFirstItem(liveRanges,&key); outer ;
 622          outer = hTabNextItem(liveRanges,&key)) {
 623
 624         /* if the liveFrom & To are the same then skip,
 625            could happen for unused return values from functions */
 626         if (outer->liveFrom == outer->liveTo) continue;
 627
 628         /* innerloop : for the inner loop we can start from the
 629            item after the outer loop */
 630         inner = hTabFirstItemWK (lRangeCopy,outer->key);
 631         inner = hTabNextItem (lRangeCopy,&key1 );
 632         for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
 633
 634             if (inner->liveFrom == inner->liveTo) continue;
 635             if (inner->liveTo < outer->liveFrom)  continue;
 636             if (inner->liveFrom > outer->liveTo)  continue;
 637
 638             /* if one of them are being defined where the other
 639                one end , then no overlap (i.e. they can goto same registers */
 640             if (inner->liveFrom == outer->liveTo ||
 641                 outer->liveFrom == inner->liveTo) continue;
 642
 643             /* so they overlap : set both their clashes */
 644             inner->clashes = bitVectSetBit(inner->clashes,outer->key);
 645             outer->clashes = bitVectSetBit(outer->clashes,inner->key);
 646
 647             /* check if they share the same spillocation */
 648             if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
 649                 SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
 650                 if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
 651                 else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
 652                 else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
 653                 else SYM_SPIL_LOC(inner)=NULL;
 654             }
 655
 656         }
 657     }
 658 }
 659
 660 /*-----------------------------------------------------------------*/
 661 /* allDefsOutOfRange - all definitions are out of a range          */
 662 /*-----------------------------------------------------------------*/
 663 bool
 664 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 665 {
 666   int i;
 667
 668   if (!defs)
 669     return TRUE;
 670
 671   for (i = 0; i < defs->size; i++)
 672     {
 673       iCode *ic;
 674
 675       if (bitVectBitValue (defs, i) &&
 676           (ic = hTabItemWithKey (iCodehTab, i)) &&
 677           (ic->seq >= fseq && ic->seq <= toseq))
 678
 679         return FALSE;
 680
 681     }
 682
 683   return TRUE;
 684 }
 685
 686 /*-----------------------------------------------------------------*/
 687 /* notUsedInBlock - not used in this block                         */
 688 /*-----------------------------------------------------------------*/
 689 int
 690 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 691 {
 692   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 693           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 694           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 695 }
 696
 697
 698 /*-----------------------------------------------------------------*/
 699 /* computeLiveRanges - computes the live ranges for variables      */
 700 /*-----------------------------------------------------------------*/
 701 void
 702 computeLiveRanges (eBBlock ** ebbs, int count)
 703 {
 704   int i = 0;
 705   /* sequence the code the live ranges are computed
 706      in terms of this sequence additionally the
 707      routine will also create a hashtable of instructions */
 708   iCodeSeq = 0;
 709   setToNull ((void **) &iCodehTab);
 710   iCodehTab = newHashTable (iCodeKey);
 711   setToNull ((void **) &iCodeSeqhTab);
 712   iCodeSeqhTab = newHashTable (iCodeKey);
 713   sequenceiCode (ebbs, count);
 714
 715   /* call routine to mark the from & to live ranges for
 716      variables used */
 717   setToNull ((void **) &liveRanges);
 718   for (i = 0; i < count; i++)
 719     markLiveRanges (ebbs[i], ebbs, count);
 720
 721   /* mark the ranges live for each point */
 722   rlivePoint (ebbs, count);
 723
 724   /* compute which overlaps with what */
 725   computeClash();
 726 }
 727