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, int fromLevel)
 179 {
 180   /* only for compiler defined temps */
 181   if (!IS_ITEMP (op))
 182     return;
 183
 184   if (fromLevel > OP_SYMBOL(op)->level) {
 185     // this is from an inner block and thus has no authority
 186     return;
 187   }
 188
 189   OP_SYMBOL (op)->key = op->key;
 190   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 191
 192   if (op->isaddr)
 193     OP_SYMBOL (op)->isptr = 1;
 194
 195   if (check)
 196     if (!OP_LIVETO (op))
 197       OP_LIVETO (op) = to;
 198     else;
 199   else
 200     OP_LIVETO (op) = to;
 201 }
 202
 203 /*-----------------------------------------------------------------*/
 204 /* firstDeOf - finds the first definition in seq for op            */
 205 /*-----------------------------------------------------------------*/
 206 static iCode *
 207 firstDefOf (operand * op)
 208 {
 209   int i;
 210   iCode *ric = NULL, *lic = NULL;
 211   int fSeq = INT_MAX;
 212
 213   if (!OP_DEFS (op))
 214     return NULL;
 215
 216   for (i = 0; i < OP_DEFS (op)->size; i++)
 217     {
 218       if (bitVectBitValue (OP_DEFS (op), i) &&
 219           (lic = hTabItemWithKey (iCodehTab, i)) &&
 220           lic->seq < fSeq)
 221         {
 222
 223           fSeq = lic->seq;
 224           ric = lic;
 225         }
 226     }
 227   return ric;
 228 }
 229 /*-----------------------------------------------------------------*/
 230 /* useDefLoopCheck - check for uses before init inside loops       */
 231 /*-----------------------------------------------------------------*/
 232 static void
 233 useDefLoopCheck (operand * op, iCode * ic)
 234 {
 235   /* this is for situations like the following
 236      int a,b;
 237
 238      while (...) {
 239      a = ... ;
 240      ...
 241      _some_usage_of_b_;
 242      ...
 243      b = ... ;
 244      }
 245      in this case the definition of 'b' will flow to the usages
 246      but register allocator cannot handle these situations.so
 247      will mark as spilt */
 248
 249   int i = 0, fdSeq;
 250   int er = 0;
 251   iCode *tic;
 252
 253   /* get the first definition */
 254   if (!(tic = firstDefOf (op)))
 255     return;
 256
 257   fdSeq = tic->seq;
 258   /* now go thru the usages & make sure they follow
 259      the first definition */
 260   for (i = 0; i <= OP_USES (op)->size; i++)
 261     {
 262       if (bitVectBitValue (OP_USES (op), i) &&
 263           (tic = hTabItemWithKey (iCodehTab, i)) &&
 264           tic->seq < fdSeq)
 265         {
 266           er = 1;
 267           break;
 268         }
 269     }
 270
 271   /* found a usage without definition */
 272   if (er)
 273     {
 274       if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
 275         {
 276
 277           werror (W_LOCAL_NOINIT,
 278                   SPIL_LOC (op)->name,
 279                   ic->filename, ic->lineno);
 280         }
 281       else
 282         {
 283
 284           werror (W_LOCAL_NOINIT,
 285                   OP_SYMBOL (op)->name,
 286                   ic->filename, ic->lineno);
 287         }
 288 #if 0 // this will create a segfault: bug #498971
 289       OP_SYMBOL (op)->isspilt = 1;
 290 #endif
 291     }
 292 }
 293
 294
 295 /*-----------------------------------------------------------------*/
 296 /* operandLUse - check and set the last use for a given operand    */
 297 /*-----------------------------------------------------------------*/
 298 operand *
 299 operandLUse (operand * op, eBBlock ** ebbs,
 300              int count, iCode * ic, eBBlock * ebp)
 301 {
 302   setFromRange (op, ic->seq);
 303   if (ic->depth)
 304     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 305   else
 306     OP_SYMBOL (op)->used += 1;
 307
 308   if (isLastUse (op, ebp, ic->next, ebbs, count) ||
 309       (OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
 310     {
 311       int torange = ic->seq;
 312
 313       /* if this is a SEND then the toRange should be extended
 314          to the call */
 315       if (ic->op == SEND) {
 316           iCode *lic ;
 317           for (lic = ic->next ; lic ; lic = lic->next) {
 318               if (lic->op == CALL || lic->op == PCALL) break;
 319           }
 320           /* found it : mark */
 321           if (lic) torange = lic->prev->seq;
 322       }
 323
 324       op = operandFromOperand (op);
 325       setToRange (op, torange, FALSE, ebp->entryLabel->level);
 326     }
 327   ic->uses = bitVectSetBit (ic->uses, op->key);
 328
 329   if (!OP_SYMBOL (op)->udChked)
 330     {
 331       sym_link *type = operandType (op);
 332       sym_link *etype = getSpec (type);
 333
 334       OP_SYMBOL (op)->udChked = 1;
 335       /* good place to check if unintialised */
 336       if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
 337           OP_SYMBOL (op)->islocal &&
 338           !IS_AGGREGATE (type) &&
 339           !IS_FUNC (type) &&
 340           ic->op != ADDRESS_OF &&
 341           !IS_STATIC (etype))
 342         {
 343
 344           if (bitVectIsZero (op->usesDefs) && OP_SYMBOL(op)->ival==NULL)
 345             {
 346               OP_SYMBOL (op)->isspilt = 1;
 347
 348               if (OP_SYMBOL (op)->isreqv &&
 349                   !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
 350                 {
 351
 352                   werror (W_LOCAL_NOINIT,
 353                           SPIL_LOC (op)->name,
 354                           ic->filename, ic->lineno);
 355                 }
 356               else
 357                 {
 358
 359                   werror (W_LOCAL_NOINIT,
 360                           OP_SYMBOL (op)->name,
 361                           ic->filename, ic->lineno);
 362                 }
 363             }
 364           else
 365             {
 366               if (ebp->depth && op->usesDefs &&
 367                   !OP_SYMBOL (op)->_isparm)
 368                 {
 369                   /* check non-inits inside loops */
 370                   useDefLoopCheck (op, ic);
 371                 }
 372             }
 373         }
 374     }
 375   return op;
 376 }
 377
 378 /*-----------------------------------------------------------------*/
 379 /* killAllAlive - mark all the definitions living with this seq    */
 380 /*-----------------------------------------------------------------*/
 381 void
 382 killAllAlive (int seq)
 383 {
 384   symbol *sym;
 385   int k;
 386
 387   for (sym = hTabFirstItem (liveRanges, &k); sym;
 388        sym = hTabNextItem (liveRanges, &k))
 389     if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
 390       sym->liveTo = seq;
 391 }
 392 /*-----------------------------------------------------------------*/
 393 /* defUsedAfterLoop - all definitions & usages before sequence num */
 394 /*-----------------------------------------------------------------*/
 395 bool
 396 defUsedAfterLoop (operand * op, int seq)
 397 {
 398   int i;
 399   iCode *ic;
 400
 401   /* check for the usages first */
 402   if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
 403     {
 404       for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
 405         {
 406
 407           if (bitVectBitValue (OP_SYMBOL (op)->uses, i) &&      /* usage found */
 408               (ic = hTabItemWithKey (iCodehTab, i)) &&  /*    ""       */
 409               ic->seq > seq)    /* & is after the seq */
 410             return TRUE;
 411         }
 412     }
 413
 414   return FALSE;
 415 }
 416
 417 /*-----------------------------------------------------------------*/
 418 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 419 /*-----------------------------------------------------------------*/
 420 void
 421 markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
 422 {
 423   iCode *ic;
 424   bitVect *defsUsed = NULL;
 425   bitVect *defsNotUsed = NULL;
 426   int i;
 427
 428   /* for all the instructions */
 429   for (ic = ebp->sch; ic; ic = ic->next)
 430     {
 431       if (ic->op == CALL || ic->op == PCALL)
 432         {
 433           setFromRange (IC_RESULT (ic), ic->seq);
 434           /* if the result has no usage then
 435              mark this as the end of its life too
 436              and take it away from the defs for the block */
 437           if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
 438             {
 439               setToRange (IC_RESULT (ic), ic->seq, FALSE,
 440                           ebp->entryLabel->level);
 441               bitVectUnSetBit (ebp->defSet, ic->key);
 442             }
 443         }
 444
 445       if (SKIP_IC2 (ic))
 446         continue;
 447
 448       /* take care of the special icodes first */
 449       if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
 450         {
 451           operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
 452           continue;
 453         }
 454
 455       if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
 456         {
 457           operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
 458           continue;
 459         }
 460
 461       if (IS_SYMOP (IC_LEFT (ic)))
 462         operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
 463
 464       if (IS_SYMOP (IC_RIGHT (ic)))
 465         operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
 466
 467       if (POINTER_SET (ic))
 468         operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
 469       else if (IC_RESULT (ic))
 470         ic->defKey = IC_RESULT (ic)->key;
 471     }
 472
 473
 474   /* for all the definitions in the block */
 475   /* compute and set the live from        */
 476   if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
 477     {
 478       for (i = 0; i < ebp->ldefs->size; i++)
 479         {
 480           iCode *dic;
 481
 482           if (bitVectBitValue (ebp->ldefs, i) &&
 483               (dic = hTabItemWithKey (iCodehTab, i)))
 484             {
 485
 486               /* if the definition has a from & it is greater */
 487               /* than the defininng iCode->seq then change it */
 488               setFromRange (IC_RESULT (dic), dic->seq);
 489             }
 490         }
 491     }
 492
 493   /* special case for lastBlock in a loop: here we
 494      mark the end of all the induction variables for the
 495      loop */
 496   if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
 497     {
 498       for (i = 0; i <= ebp->linds->size; i++)
 499         {
 500           iCode *dic;
 501
 502           if (bitVectBitValue (ebp->linds, i) &&
 503               (dic = hTabItemWithKey (iCodehTab, i)))
 504             {
 505
 506               /* if this is a register equvalent make sure
 507                  it is not defined or used anywhere after the loop */
 508               if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
 509                   defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
 510                 continue;
 511
 512               setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE,
 513                           ebp->entryLabel->level);
 514             }
 515         }
 516     }
 517
 518   /* for defnitions coming into the block if they */
 519   /* not used by itself & any of its successors   */
 520   /* they are dead */
 521   /* first union the definitions used in all successors
 522      and itself */
 523   for (i = 0; i < count; ebbs[i++]->visited = 0);
 524   applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
 525   defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
 526
 527   /* now subract the result of these unions from */
 528   /* the incoming definitions this will give the */
 529   /* definitions that are never used in the future */
 530   defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
 531                                defsUsed);
 532
 533   /* mark the end of the defintions */
 534   if (!bitVectIsZero (defsNotUsed) && ebp->sch)
 535     {
 536       for (i = 0; i < defsNotUsed->size; i++)
 537         {
 538           iCode *dic;
 539
 540           if (bitVectBitValue (defsNotUsed, i) &&
 541               (dic = hTabItemWithKey (iCodehTab, i)))
 542             {
 543               setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE,
 544                           ebp->entryLabel->level);
 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