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 /* hashiCodeKeys - add all iCodes to the hash table                */
  36 /*-----------------------------------------------------------------*/
  37 void
  38 hashiCodeKeys (eBBlock ** ebbs, int count)
  39 {
  40   int i;
  41
  42   for (i = 0; i < count; i++)
  43     {
  44       iCode *ic;
  45       for (ic = ebbs[i]->sch; ic; ic = ic->next)
  46         hTabAddItem (&iCodehTab, ic->key, ic);
  47     }
  48 }
  49
  50 /*-----------------------------------------------------------------*/
  51 /* sequenceiCode - creates a sequence number for the iCode & add   */
  52 /*-----------------------------------------------------------------*/
  53 void
  54 sequenceiCode (eBBlock ** ebbs, int count)
  55 {
  56   int i;
  57
  58   for (i = 0; i < count; i++)
  59     {
  60
  61       iCode *ic;
  62       ebbs[i]->fSeq = iCodeSeq + 1;
  63       for (ic = ebbs[i]->sch; ic; ic = ic->next)
  64         {
  65           ic->seq = ++iCodeSeq;
  66           ic->depth = ebbs[i]->depth;
  67           //hTabAddItem (&iCodehTab, ic->key, ic);
  68           hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
  69         }
  70       ebbs[i]->lSeq = iCodeSeq;
  71     }
  72 }
  73
  74 /*-----------------------------------------------------------------*/
  75 /* setFromRange - sets the from range of a given operand           */
  76 /*-----------------------------------------------------------------*/
  77 void
  78 setFromRange (operand * op, int from)
  79 {
  80   /* only for compiler defined temporaries */
  81   if (!IS_ITEMP (op))
  82     return;
  83
  84   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
  85
  86   if (op->isaddr)
  87     OP_SYMBOL (op)->isptr = 1;
  88
  89   if (!OP_LIVEFROM (op) ||
  90       OP_LIVEFROM (op) > from)
  91     OP_LIVEFROM (op) = from;
  92 }
  93
  94 /*-----------------------------------------------------------------*/
  95 /* setToRange - set the range to for an operand                    */
  96 /*-----------------------------------------------------------------*/
  97 void
  98 setToRange (operand * op, int to, bool check)
  99 {
 100   /* only for compiler defined temps */
 101   if (!IS_ITEMP (op))
 102     return;
 103
 104   OP_SYMBOL (op)->key = op->key;
 105   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 106
 107   if (op->isaddr)
 108     OP_SYMBOL (op)->isptr = 1;
 109
 110   if (check)
 111     if (!OP_LIVETO (op))
 112       OP_LIVETO (op) = to;
 113     else;
 114   else
 115     OP_LIVETO (op) = to;
 116 }
 117
 118 /*-----------------------------------------------------------------*/
 119 /* setFromRange - sets the from range of a given operand           */
 120 /*-----------------------------------------------------------------*/
 121 void
 122 setLiveFrom (symbol * sym, int from)
 123 {
 124   if (!sym->liveFrom || sym->liveFrom > from)
 125     sym->liveFrom = from;
 126 }
 127
 128 /*-----------------------------------------------------------------*/
 129 /* setToRange - set the range to for an operand                    */
 130 /*-----------------------------------------------------------------*/
 131 void
 132 setLiveTo (symbol * sym, int to)
 133 {
 134   if (!sym->liveTo || sym->liveTo < to)
 135     sym->liveTo = to;
 136 }
 137
 138 /*-----------------------------------------------------------------*/
 139 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 140 /*-----------------------------------------------------------------*/
 141 void
 142 markLiveRanges (eBBlock ** ebbs, int count)
 143 {
 144   int i, key;
 145   symbol *sym;
 146
 147   for (i = 0; i < count; i++)
 148     {
 149       iCode *ic;
 150
 151       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 152         {
 153           if (ic->op == CALL || ic->op == PCALL)
 154             if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
 155               bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 156
 157           /* for all iTemps alive at this iCode */
 158           for (key = 1; key < ic->rlive->size; key++)
 159             {
 160               if (!bitVectBitValue(ic->rlive, key))
 161                 continue;
 162
 163               sym = hTabItemWithKey(liveRanges, key);
 164               setLiveTo(sym, ic->seq);
 165               setLiveFrom(sym, ic->seq);
 166             }
 167
 168         }
 169     }
 170 }
 171
 172 /*-----------------------------------------------------------------*/
 173 /* markAlive - marks the operand as alive between sic and eic      */
 174 /*-----------------------------------------------------------------*/
 175 void
 176 markAlive (iCode * sic, iCode * eic, int key)
 177 {
 178   iCode *dic;
 179
 180   for (dic = sic; dic != eic->next; dic = dic->next)
 181     {
 182       dic->rlive = bitVectSetBit (dic->rlive, key);
 183     }
 184 }
 185
 186 /*-----------------------------------------------------------------*/
 187 /* findNextUseSym - finds the next use of the symbol and marks it  */
 188 /*                  alive in between                               */
 189 /*-----------------------------------------------------------------*/
 190 int
 191 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
 192 {
 193   int retval = 0;
 194   iCode *uic;
 195   eBBlock *succ;
 196
 197   hTabAddItemIfNotP (&liveRanges, sym->key, sym);
 198
 199   if (!ic)
 200     goto check_successors;
 201
 202   /* if we check a complete block and the symbol */
 203   /* is alive at the beginning of the block */
 204   /* and not defined in the first instructions */
 205   /* then a next use exists (return 1) */
 206   if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
 207     {
 208       /* check if the first instruction is a def of this op */
 209       if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
 210         return 1;
 211
 212       if (IS_ITEMP(IC_RESULT(ic)))
 213         if (IC_RESULT(ic)->key == sym->key)
 214           return 0;
 215
 216       return 1;
 217     }
 218
 219   if (ebp->visited)
 220     return 0;
 221
 222   if (ic == ebp->sch)
 223     ebp->visited = 1;
 224
 225   /* for all remaining instructions in current block */
 226   for (uic = ic; uic; uic = uic->next)
 227     {
 228
 229       if (SKIP_IC2(uic))
 230         continue;
 231
 232       if (uic->op == JUMPTABLE)
 233         {
 234           if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
 235             {
 236               markAlive(ic, uic, sym->key);
 237               return 1;
 238             }
 239            continue;
 240         }
 241
 242       if (uic->op == IFX)
 243         {
 244           if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
 245             {
 246               markAlive(ic, uic, sym->key);
 247               return 1;
 248             }
 249            continue;
 250         }
 251
 252       if (IS_ITEMP (IC_LEFT (uic)))
 253         if (IC_LEFT (uic)->key == sym->key)
 254           {
 255             markAlive(ic, uic, sym->key);
 256             return 1;
 257           }
 258
 259       if (IS_ITEMP (IC_RIGHT (uic)))
 260         if (IC_RIGHT (uic)->key == sym->key)
 261           {
 262             markAlive (ic, uic, sym->key);
 263             return 1;
 264           }
 265
 266       if (IS_ITEMP (IC_RESULT (uic)))
 267         if (IC_RESULT (uic)->key == sym->key)
 268           {
 269             if (POINTER_SET (uic))
 270               {
 271                 markAlive (ic, uic, sym->key);
 272                 return 1;
 273               }
 274             else
 275               return 0;
 276           }
 277
 278     }
 279
 280   /* check all successors */
 281 check_successors:
 282
 283   succ = setFirstItem (ebp->succList);
 284   for (; succ; succ = setNextItem (ebp->succList))
 285     {
 286       retval += findNextUseSym (succ, succ->sch, sym);
 287     }
 288
 289   if (retval)
 290     {
 291       if (ic) markAlive (ic, ebp->ech, sym->key);
 292       return 1;
 293     }
 294
 295   return 0;
 296 }
 297
 298 /*-----------------------------------------------------------------*/
 299 /* findNextUse - finds the next use of the operand and marks it    */
 300 /*               alive in between                                  */
 301 /*-----------------------------------------------------------------*/
 302 int
 303 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
 304 {
 305   if (op->isaddr)
 306     OP_SYMBOL (op)->isptr = 1;
 307
 308   OP_SYMBOL (op)->key = op->key;
 309
 310   return findNextUseSym (ebp, ic, OP_SYMBOL(op));
 311 }
 312
 313 /*-----------------------------------------------------------------*/
 314 /* unvisitBlocks - clears visited in all blocks                    */
 315 /*-----------------------------------------------------------------*/
 316 void unvisitBlocks (eBBlock ** ebbs, int count)
 317 {
 318   int i;
 319
 320   for (i = 0; i < count; i++)
 321     ebbs[i]->visited = 0;
 322 }
 323
 324 /*------------------------------------------------------------------*/
 325 /* findRecursiveSucc - build a bit vector of recursive successors   */
 326 /*------------------------------------------------------------------*/
 327 DEFSETFUNC (findRecursiveSucc)
 328 {
 329   eBBlock *ebp = item;
 330   V_ARG (bitVect *, succVect);
 331
 332   if (ebp->visited)
 333     return 0;
 334
 335   ebp->visited = 1;
 336   bitVectSetBit (succVect, ebp->bbnum);
 337   applyToSet (ebp->succList, findRecursiveSucc, succVect);
 338   return 0;
 339 }
 340
 341
 342 /*------------------------------------------------------------------*/
 343 /* findRecursivePred - build a bit vector of recursive predecessors */
 344 /*------------------------------------------------------------------*/
 345 DEFSETFUNC (findRecursivePred)
 346 {
 347   eBBlock *ebp = item;
 348   V_ARG (bitVect *, predVect);
 349
 350   if (ebp->visited)
 351     return 0;
 352
 353   ebp->visited = 1;
 354   bitVectSetBit (predVect, ebp->bbnum);
 355   applyToSet (ebp->predList, findRecursivePred, predVect);
 356   return 0;
 357 }
 358
 359
 360 /*------------------------------------------------------------------*/
 361 /* findPrevUse - handle degenerate case of a symbol used prior to   */
 362 /*               findNextUse() marking any definition.              */
 363 /*------------------------------------------------------------------*/
 364 void
 365 findPrevUse (eBBlock *ebp, iCode *ic, operand *op, eBBlock **ebbs, int count)
 366 {
 367   int i;
 368   bitVect * succVect;
 369   bitVect * predVect;
 370
 371   /* If liveness is already known, then a previous call to findNextUse() */
 372   /* has already taken care of everything. */
 373   if (ic && bitVectBitValue(ic->rlive, op->key))
 374     return;
 375
 376   if (op->isaddr)
 377     OP_SYMBOL (op)->isptr = 1;
 378
 379   OP_SYMBOL (op)->key = op->key;
 380
 381   /* Otherwise, it appears that this symbol was used prior to definition.     */
 382   /* Just fix the live range; we'll deal with a diagnostic message elsewhere. */
 383   /* If the symbol use was in a loop, we need to extend the live range to the */
 384   /* outermost loop. */
 385   unvisitBlocks (ebbs, count);
 386   succVect = newBitVect (count);
 387   applyToSet (ebp->succList, findRecursiveSucc, succVect);
 388   unvisitBlocks (ebbs, count);
 389   predVect = newBitVect (count);
 390   applyToSet (ebp->predList, findRecursivePred, predVect);
 391
 392   /* Blocks that are both recursively predecessors and successors are in */
 393   /* a loop with the current iCode. Mark the operand as alive in them.   */
 394   for (i = 0; i < count; i++)
 395     {
 396       if (bitVectBitValue(succVect, i) && bitVectBitValue(predVect, i))
 397         markAlive (ebbs[i]->sch, ebbs[i]->ech, op->key);
 398     }
 399
 400   freeBitVect (succVect);
 401   freeBitVect (predVect);
 402 }
 403
 404 /*-----------------------------------------------------------------*/
 405 /* incUsed - increment a symbol's usage count                      */
 406 /*-----------------------------------------------------------------*/
 407 void
 408 incUsed (iCode *ic, operand *op)
 409 {
 410   if (ic->depth)
 411     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 412   else
 413     OP_SYMBOL (op)->used += 1;
 414 }
 415
 416 /*-----------------------------------------------------------------*/
 417 /* rliveClear - clears the rlive bitVectors                        */
 418 /*-----------------------------------------------------------------*/
 419 void
 420 rliveClear (eBBlock ** ebbs, int count)
 421 {
 422   int i;
 423
 424   /* for all blocks do */
 425   for (i = 0; i < count; i++)
 426     {
 427       iCode *ic;
 428
 429       /* for all instructions in this block do */
 430       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 431         {
 432           freeBitVect (ic->rlive);
 433           ic->rlive = NULL;
 434         }
 435     }
 436 }
 437
 438 /*-----------------------------------------------------------------*/
 439 /* rlivePoint - for each point compute the ranges that are alive   */
 440 /*-----------------------------------------------------------------*/
 441 void
 442 rlivePoint (eBBlock ** ebbs, int count)
 443 {
 444   int i, key;
 445   eBBlock *succ;
 446   bitVect *alive;
 447
 448   /* for all blocks do */
 449   for (i = 0; i < count; i++)
 450     {
 451       iCode *ic;
 452
 453       /* for all instructions in this block do */
 454       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 455         {
 456
 457           if (!ic->rlive)
 458             ic->rlive = newBitVect (operandKey);
 459
 460           if (SKIP_IC2(ic))
 461             continue;
 462
 463           if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
 464             {
 465               incUsed (ic, IC_JTCOND(ic));
 466
 467               if (!IS_ITEMP(IC_JTCOND(ic)))
 468                 continue;
 469
 470               findPrevUse (ebbs[i], ic->prev, IC_JTCOND(ic), ebbs, count);
 471               unvisitBlocks(ebbs, count);
 472               ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
 473               findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
 474
 475               continue;
 476             }
 477
 478           if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
 479             {
 480               incUsed (ic, IC_COND(ic));
 481
 482               if (!IS_ITEMP(IC_COND(ic)))
 483                 continue;
 484
 485               findPrevUse (ebbs[i], ic->prev, IC_COND(ic), ebbs, count);
 486               unvisitBlocks (ebbs, count);
 487               ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
 488               findNextUse (ebbs[i], ic->next, IC_COND(ic));
 489
 490               continue;
 491             }
 492
 493           if (IS_SYMOP(IC_LEFT(ic)))
 494             {
 495               incUsed (ic, IC_LEFT(ic));
 496               if (IS_ITEMP(IC_LEFT(ic)))
 497                 {
 498
 499                   findPrevUse (ebbs[i], ic->prev, IC_LEFT(ic), ebbs, count);
 500                   unvisitBlocks(ebbs, count);
 501                   ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
 502                   findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
 503
 504                   /* if this is a send extend the LR to the call */
 505                   if (ic->op == SEND)
 506                     {
 507                       iCode *lic;
 508                       for (lic = ic; lic; lic = lic->next)
 509                         {
 510                           if (lic->op == CALL || lic->op == PCALL)
 511                             {
 512                               markAlive (ic, lic->prev, IC_LEFT (ic)->key);
 513                               break;
 514                             }
 515                         }
 516                     }
 517                 }
 518             }
 519
 520           if (IS_SYMOP(IC_RIGHT(ic)))
 521             {
 522               incUsed (ic, IC_RIGHT(ic));
 523               if (IS_ITEMP(IC_RIGHT(ic)))
 524                 {
 525                   findPrevUse (ebbs[i], ic->prev, IC_RIGHT(ic), ebbs, count);
 526                   unvisitBlocks(ebbs, count);
 527                   ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
 528                   findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
 529                 }
 530             }
 531
 532           if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
 533             incUsed (ic, IC_RESULT(ic));
 534
 535           if (IS_ITEMP(IC_RESULT(ic)))
 536             {
 537               if (POINTER_SET(ic))
 538                 {
 539                   findPrevUse (ebbs[i], ic->prev, IC_RESULT(ic), ebbs, count);
 540                 }
 541               unvisitBlocks(ebbs, count);
 542               ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
 543               findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
 544             }
 545
 546           if (!POINTER_SET(ic) && IC_RESULT(ic))
 547             ic->defKey = IC_RESULT(ic)->key;
 548
 549         }
 550
 551       /* check all symbols that are alive in the last instruction */
 552       /* but are not alive in all successors */
 553
 554       succ = setFirstItem (ebbs[i]->succList);
 555       if (!succ)
 556         continue;
 557
 558       alive = succ->sch->rlive;
 559       while ((succ = setNextItem (ebbs[i]->succList)))
 560         {
 561           if (succ->sch)
 562             alive = bitVectIntersect (alive, succ->sch->rlive);
 563         }
 564
 565       if (ebbs[i]->ech)
 566         alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 567
 568       if(!alive)
 569         continue;
 570       for (key = 1; key < alive->size; key++)
 571         {
 572           if (!bitVectBitValue (alive, key))
 573             continue;
 574
 575           unvisitBlocks(ebbs, count);
 576           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 577         }
 578
 579     }
 580 }
 581
 582 /*-----------------------------------------------------------------*/
 583 /* computeClash - find out which live ranges collide with others   */
 584 /*-----------------------------------------------------------------*/
 585 static void
 586 computeClash (eBBlock ** ebbs, int count)
 587 {
 588   int i;
 589
 590   /* for all blocks do */
 591   for (i = 0; i < count; i++)
 592     {
 593       iCode *ic;
 594
 595       /* for every iCode do */
 596       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 597         {
 598           symbol *sym1, *sym2;
 599           int key1, key2;
 600
 601           /* for all iTemps alive at this iCode */
 602           for (key1 = 1; key1 < ic->rlive->size; key1++)
 603             {
 604               if (!bitVectBitValue(ic->rlive, key1))
 605                 continue;
 606
 607               sym1 = hTabItemWithKey(liveRanges, key1);
 608
 609               if (!sym1->isitmp)
 610                 continue;
 611
 612               /* for all other iTemps alive at this iCode */
 613               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 614                 {
 615                   if (!bitVectBitValue(ic->rlive, key2))
 616                     continue;
 617
 618                   sym2 = hTabItemWithKey(liveRanges, key2);
 619
 620                   if (!sym2->isitmp)
 621                     continue;
 622
 623                   /* if the result and left or right is an iTemp */
 624                   /* than possibly the iTemps do not clash */
 625                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 626                       IS_ITEMP(IC_RESULT(ic)) &&
 627                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 628                     {
 629                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1
 630                           && sym1->liveFrom == ic->seq
 631                           && sym2->liveTo == ic->seq)
 632                         {
 633                           if (IS_SYMOP(IC_LEFT(ic)))
 634                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 635                               continue;
 636                           if (IS_SYMOP(IC_RIGHT(ic)))
 637                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 638                               continue;
 639                         }
 640
 641                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2
 642                           && sym2->liveFrom == ic->seq
 643                           && sym1->liveTo == ic->seq)
 644                         {
 645                           if (IS_SYMOP(IC_LEFT(ic)))
 646                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 647                               continue;
 648                           if (IS_SYMOP(IC_RIGHT(ic)))
 649                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 650                               continue;
 651                         }
 652                     }
 653
 654                   /* the iTemps do clash. set the bits in clashes */
 655                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 656                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 657
 658                   /* check if they share the same spill location */
 659                   /* what is this good for? */
 660                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 661                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 662                     {
 663                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 664                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 665                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 666                       else SYM_SPIL_LOC(sym1)=NULL;
 667                     }
 668                 }
 669             }
 670         }
 671     }
 672 }
 673
 674 /*-----------------------------------------------------------------*/
 675 /* allDefsOutOfRange - all definitions are out of a range          */
 676 /*-----------------------------------------------------------------*/
 677 bool
 678 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 679 {
 680   int i;
 681
 682   if (!defs)
 683     return TRUE;
 684
 685   for (i = 0; i < defs->size; i++)
 686     {
 687       iCode *ic;
 688
 689       if (bitVectBitValue (defs, i) &&
 690           (ic = hTabItemWithKey (iCodehTab, i)) &&
 691           (ic->seq >= fseq && ic->seq <= toseq))
 692         return FALSE;
 693
 694     }
 695
 696   return TRUE;
 697 }
 698
 699 /*-----------------------------------------------------------------*/
 700 /* notUsedInBlock - not used in this block                         */
 701 /*-----------------------------------------------------------------*/
 702 int
 703 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 704 {
 705   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 706           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 707           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 708 }
 709
 710 /*-----------------------------------------------------------------*/
 711 /* adjustIChain - correct the sch and ech pointers                 */
 712 /*-----------------------------------------------------------------*/
 713 void
 714 adjustIChain (eBBlock ** ebbs, int count)
 715 {
 716   int i;
 717
 718   for (i = 0; i < count; i++)
 719     {
 720       iCode *ic;
 721
 722       if (ebbs[i]->noPath)
 723         continue;
 724
 725       ic = ebbs[i]->sch;
 726
 727       /* is there any code for this eBBlock? (e.g. ROM assignment) */
 728       if(!ic)continue;
 729
 730       while (ic->prev)
 731         ic = ic->prev;
 732       ebbs[i]->sch = ic;
 733
 734       ic = ebbs[i]->ech;
 735       while (ic->next)
 736         ic = ic->next;
 737       ebbs[i]->ech = ic;
 738     }
 739 }
 740
 741 /*-----------------------------------------------------------------*/
 742 /* computeLiveRanges - computes the live ranges for variables      */
 743 /*-----------------------------------------------------------------*/
 744 void
 745 computeLiveRanges (eBBlock ** ebbs, int count)
 746 {
 747   /* first look through all blocks and adjust the
 748      sch and ech pointers */
 749   adjustIChain (ebbs, count);
 750
 751   /* sequence the code the live ranges are computed
 752      in terms of this sequence additionally the
 753      routine will also create a hashtable of instructions */
 754   iCodeSeq = 0;
 755   setToNull ((void *) &iCodehTab);
 756   iCodehTab = newHashTable (iCodeKey);
 757   hashiCodeKeys (ebbs, count);
 758   setToNull ((void *) &iCodeSeqhTab);
 759   iCodeSeqhTab = newHashTable (iCodeKey);
 760   sequenceiCode (ebbs, count);
 761
 762   /* mark the ranges live for each point */
 763   setToNull ((void *) &liveRanges);
 764   rlivePoint (ebbs, count);
 765
 766   /* mark the from & to live ranges for variables used */
 767   markLiveRanges (ebbs, count);
 768
 769   /* compute which overlaps with what */
 770   computeClash(ebbs, count);
 771 }
 772
 773 /*-----------------------------------------------------------------*/
 774 /* recomputeLiveRanges - recomputes the live ranges for variables  */
 775 /*-----------------------------------------------------------------*/
 776 void
 777 recomputeLiveRanges (eBBlock ** ebbs, int count)
 778 {
 779   symbol * sym;
 780   int key;
 781
 782   /* clear all rlive bitVectors */
 783   rliveClear (ebbs, count);
 784
 785   sym = hTabFirstItem (liveRanges, &key);
 786   if (sym)
 787     {
 788       do {
 789         sym->used = 0;
 790         sym->liveFrom = 0;
 791         sym->liveTo = 0;
 792         freeBitVect (sym->clashes);
 793         sym->clashes = NULL;
 794       } while ( (sym = hTabNextItem (liveRanges, &key)));
 795     }
 796
 797   /* do the LR computation again */
 798   computeLiveRanges (ebbs, count);
 799 }
 800