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   eBBlock * pred;
 371
 372   /* If liveness is already known, then a previous call to findNextUse() */
 373   /* has already taken care of everything. */
 374   if (ic && bitVectBitValue(ic->rlive, op->key))
 375     return;
 376
 377   if (!ic)
 378     {
 379       /* We are at the start of a block. If the operand is alive at the */
 380       /* end of all predecessors, then a previous call to findNextUse() */
 381       /* has already taken care of everything. */
 382
 383       pred = setFirstItem (ebp->predList);
 384       for (; pred; pred = setNextItem (ebp->predList))
 385         if (pred->ech && !bitVectBitValue(pred->ech->rlive, op->key))
 386           break;
 387
 388       if (!pred)
 389         return;
 390     }
 391
 392   if (op->isaddr)
 393     OP_SYMBOL (op)->isptr = 1;
 394
 395   OP_SYMBOL (op)->key = op->key;
 396
 397   /* Otherwise, it appears that this symbol was used prior to definition.     */
 398   /* Just fix the live range; we'll deal with a diagnostic message elsewhere. */
 399   /* If the symbol use was in a loop, we need to extend the live range to the */
 400   /* outermost loop. */
 401   unvisitBlocks (ebbs, count);
 402   succVect = newBitVect (count);
 403   applyToSet (ebp->succList, findRecursiveSucc, succVect);
 404   unvisitBlocks (ebbs, count);
 405   predVect = newBitVect (count);
 406   applyToSet (ebp->predList, findRecursivePred, predVect);
 407
 408   /* Blocks that are both recursively predecessors and successors are in */
 409   /* a loop with the current iCode. Mark the operand as alive in them.   */
 410   for (i = 0; i < count; i++)
 411     {
 412       if (bitVectBitValue(succVect, i) && bitVectBitValue(predVect, i))
 413         markAlive (ebbs[i]->sch, ebbs[i]->ech, op->key);
 414     }
 415
 416   freeBitVect (succVect);
 417   freeBitVect (predVect);
 418 }
 419
 420 /*-----------------------------------------------------------------*/
 421 /* incUsed - increment a symbol's usage count                      */
 422 /*-----------------------------------------------------------------*/
 423 void
 424 incUsed (iCode *ic, operand *op)
 425 {
 426   if (ic->depth)
 427     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 428   else
 429     OP_SYMBOL (op)->used += 1;
 430 }
 431
 432 /*-----------------------------------------------------------------*/
 433 /* rliveClear - clears the rlive bitVectors                        */
 434 /*-----------------------------------------------------------------*/
 435 void
 436 rliveClear (eBBlock ** ebbs, int count)
 437 {
 438   int i;
 439
 440   /* for all blocks do */
 441   for (i = 0; i < count; i++)
 442     {
 443       iCode *ic;
 444
 445       /* for all instructions in this block do */
 446       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 447         {
 448           freeBitVect (ic->rlive);
 449           ic->rlive = NULL;
 450         }
 451     }
 452 }
 453
 454 /*-----------------------------------------------------------------*/
 455 /* rlivePoint - for each point compute the ranges that are alive   */
 456 /*-----------------------------------------------------------------*/
 457 void
 458 rlivePoint (eBBlock ** ebbs, int count)
 459 {
 460   int i, key;
 461   eBBlock *succ;
 462   bitVect *alive;
 463
 464   /* for all blocks do */
 465   for (i = 0; i < count; i++)
 466     {
 467       iCode *ic;
 468
 469       /* for all instructions in this block do */
 470       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 471         {
 472
 473           if (!ic->rlive)
 474             ic->rlive = newBitVect (operandKey);
 475
 476           if (SKIP_IC2(ic))
 477             continue;
 478
 479           if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
 480             {
 481               incUsed (ic, IC_JTCOND(ic));
 482
 483               if (!IS_ITEMP(IC_JTCOND(ic)))
 484                 continue;
 485
 486               findPrevUse (ebbs[i], ic->prev, IC_JTCOND(ic), ebbs, count);
 487               unvisitBlocks(ebbs, count);
 488               ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
 489               findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
 490
 491               continue;
 492             }
 493
 494           if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
 495             {
 496               incUsed (ic, IC_COND(ic));
 497
 498               if (!IS_ITEMP(IC_COND(ic)))
 499                 continue;
 500
 501               findPrevUse (ebbs[i], ic->prev, IC_COND(ic), ebbs, count);
 502               unvisitBlocks (ebbs, count);
 503               ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
 504               findNextUse (ebbs[i], ic->next, IC_COND(ic));
 505
 506               continue;
 507             }
 508
 509           if (IS_SYMOP(IC_LEFT(ic)))
 510             {
 511               incUsed (ic, IC_LEFT(ic));
 512               if (IS_ITEMP(IC_LEFT(ic)))
 513                 {
 514
 515                   findPrevUse (ebbs[i], ic->prev, IC_LEFT(ic), ebbs, count);
 516                   unvisitBlocks(ebbs, count);
 517                   ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
 518                   findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
 519
 520                   /* if this is a send extend the LR to the call */
 521                   if (ic->op == SEND)
 522                     {
 523                       iCode *lic;
 524                       for (lic = ic; lic; lic = lic->next)
 525                         {
 526                           if (lic->op == CALL || lic->op == PCALL)
 527                             {
 528                               markAlive (ic, lic->prev, IC_LEFT (ic)->key);
 529                               break;
 530                             }
 531                         }
 532                     }
 533                 }
 534 //                fprintf(stderr, "%s:%d IS_SYMOP left\t", __FILE__, __LINE__);printOperand(IC_LEFT(ic), stderr);
 535 //                fprintf(stderr, "\n");
 536             }
 537
 538           if (IS_SYMOP(IC_RIGHT(ic)))
 539             {
 540               incUsed (ic, IC_RIGHT(ic));
 541               if (IS_ITEMP(IC_RIGHT(ic)))
 542                 {
 543                   findPrevUse (ebbs[i], ic->prev, IC_RIGHT(ic), ebbs, count);
 544                   unvisitBlocks(ebbs, count);
 545                   ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
 546                   findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
 547                 }
 548 //                fprintf(stderr, "%s:%d IS_SYMOP right\t", __FILE__, __LINE__);printOperand(IC_RIGHT(ic), stderr);
 549 //                fprintf(stderr, "\n");
 550             }
 551
 552           if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
 553             incUsed (ic, IC_RESULT(ic));
 554
 555           if (IS_ITEMP(IC_RESULT(ic)))
 556             {
 557               if (POINTER_SET(ic))
 558                 {
 559                   findPrevUse (ebbs[i], ic->prev, IC_RESULT(ic), ebbs, count);
 560                 }
 561               unvisitBlocks(ebbs, count);
 562               ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
 563               findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
 564             }
 565
 566           if (!POINTER_SET(ic) && IC_RESULT(ic))
 567             ic->defKey = IC_RESULT(ic)->key;
 568
 569         }
 570
 571       /* check all symbols that are alive in the last instruction */
 572       /* but are not alive in all successors */
 573
 574       succ = setFirstItem (ebbs[i]->succList);
 575       if (!succ)
 576         continue;
 577
 578       alive = succ->sch->rlive;
 579       while ((succ = setNextItem (ebbs[i]->succList)))
 580         {
 581           if (succ->sch)
 582             alive = bitVectIntersect (alive, succ->sch->rlive);
 583         }
 584
 585       if (ebbs[i]->ech)
 586         alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 587
 588       if(!alive)
 589         continue;
 590       for (key = 1; key < alive->size; key++)
 591         {
 592           if (!bitVectBitValue (alive, key))
 593             continue;
 594
 595           unvisitBlocks(ebbs, count);
 596           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 597         }
 598
 599     }
 600 }
 601
 602 /*-----------------------------------------------------------------*/
 603 /* computeClash - find out which live ranges collide with others   */
 604 /*-----------------------------------------------------------------*/
 605 static void
 606 computeClash (eBBlock ** ebbs, int count)
 607 {
 608   int i;
 609
 610   /* for all blocks do */
 611   for (i = 0; i < count; i++)
 612     {
 613       iCode *ic;
 614
 615       /* for every iCode do */
 616       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 617         {
 618           symbol *sym1, *sym2;
 619           int key1, key2;
 620
 621           /* for all iTemps alive at this iCode */
 622           for (key1 = 1; key1 < ic->rlive->size; key1++)
 623             {
 624               if (!bitVectBitValue(ic->rlive, key1))
 625                 continue;
 626
 627               sym1 = hTabItemWithKey(liveRanges, key1);
 628
 629               if (!sym1->isitmp)
 630                 continue;
 631
 632               /* for all other iTemps alive at this iCode */
 633               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 634                 {
 635                   if (!bitVectBitValue(ic->rlive, key2))
 636                     continue;
 637
 638                   sym2 = hTabItemWithKey(liveRanges, key2);
 639
 640                   if (!sym2->isitmp)
 641                     continue;
 642
 643                   /* if the result and left or right is an iTemp */
 644                   /* than possibly the iTemps do not clash */
 645                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 646                       IS_ITEMP(IC_RESULT(ic)) &&
 647                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 648                     {
 649                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1
 650                           && sym1->liveFrom == ic->seq
 651                           && sym2->liveTo == ic->seq)
 652                         {
 653                           if (IS_SYMOP(IC_LEFT(ic)))
 654                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 655                               continue;
 656                           if (IS_SYMOP(IC_RIGHT(ic)))
 657                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 658                               continue;
 659                         }
 660
 661                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2
 662                           && sym2->liveFrom == ic->seq
 663                           && sym1->liveTo == ic->seq)
 664                         {
 665                           if (IS_SYMOP(IC_LEFT(ic)))
 666                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 667                               continue;
 668                           if (IS_SYMOP(IC_RIGHT(ic)))
 669                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 670                               continue;
 671                         }
 672                     }
 673
 674                   /* the iTemps do clash. set the bits in clashes */
 675                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 676                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 677
 678                   /* check if they share the same spill location */
 679                   /* what is this good for? */
 680                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 681                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 682                     {
 683                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 684                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 685                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 686                       else SYM_SPIL_LOC(sym1)=NULL;
 687                     }
 688                 }
 689             }
 690         }
 691     }
 692 }
 693
 694 /*-----------------------------------------------------------------*/
 695 /* allDefsOutOfRange - all definitions are out of a range          */
 696 /*-----------------------------------------------------------------*/
 697 bool
 698 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 699 {
 700   int i;
 701
 702   if (!defs)
 703     return TRUE;
 704
 705   for (i = 0; i < defs->size; i++)
 706     {
 707       iCode *ic;
 708
 709       if (bitVectBitValue (defs, i) &&
 710           (ic = hTabItemWithKey (iCodehTab, i)) &&
 711           (ic->seq >= fseq && ic->seq <= toseq))
 712         return FALSE;
 713
 714     }
 715
 716   return TRUE;
 717 }
 718
 719 /*-----------------------------------------------------------------*/
 720 /* notUsedInBlock - not used in this block                         */
 721 /*-----------------------------------------------------------------*/
 722 int
 723 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 724 {
 725   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 726           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 727           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 728 }
 729
 730 /*-----------------------------------------------------------------*/
 731 /* adjustIChain - correct the sch and ech pointers                 */
 732 /*-----------------------------------------------------------------*/
 733 void
 734 adjustIChain (eBBlock ** ebbs, int count)
 735 {
 736   int i;
 737
 738   for (i = 0; i < count; i++)
 739     {
 740       iCode *ic;
 741
 742       if (ebbs[i]->noPath)
 743         continue;
 744
 745       ic = ebbs[i]->sch;
 746
 747       /* is there any code for this eBBlock? (e.g. ROM assignment) */
 748       if(!ic)continue;
 749
 750       while (ic->prev)
 751         ic = ic->prev;
 752       ebbs[i]->sch = ic;
 753
 754       ic = ebbs[i]->ech;
 755       while (ic->next)
 756         ic = ic->next;
 757       ebbs[i]->ech = ic;
 758     }
 759 }
 760
 761 /*-----------------------------------------------------------------*/
 762 /* computeLiveRanges - computes the live ranges for variables      */
 763 /*-----------------------------------------------------------------*/
 764 void
 765 computeLiveRanges (eBBlock ** ebbs, int count)
 766 {
 767   /* first look through all blocks and adjust the
 768      sch and ech pointers */
 769   adjustIChain (ebbs, count);
 770
 771   /* sequence the code the live ranges are computed
 772      in terms of this sequence additionally the
 773      routine will also create a hashtable of instructions */
 774   iCodeSeq = 0;
 775   setToNull ((void *) &iCodehTab);
 776   iCodehTab = newHashTable (iCodeKey);
 777   hashiCodeKeys (ebbs, count);
 778   setToNull ((void *) &iCodeSeqhTab);
 779   iCodeSeqhTab = newHashTable (iCodeKey);
 780   sequenceiCode (ebbs, count);
 781
 782   /* mark the ranges live for each point */
 783   setToNull ((void *) &liveRanges);
 784   rlivePoint (ebbs, count);
 785
 786   /* mark the from & to live ranges for variables used */
 787   markLiveRanges (ebbs, count);
 788
 789   /* compute which overlaps with what */
 790   computeClash(ebbs, count);
 791 }
 792
 793 /*-----------------------------------------------------------------*/
 794 /* recomputeLiveRanges - recomputes the live ranges for variables  */
 795 /*-----------------------------------------------------------------*/
 796 void
 797 recomputeLiveRanges (eBBlock ** ebbs, int count)
 798 {
 799   symbol * sym;
 800   int key;
 801
 802   /* clear all rlive bitVectors */
 803   rliveClear (ebbs, count);
 804
 805   sym = hTabFirstItem (liveRanges, &key);
 806   if (sym)
 807     {
 808       do {
 809         sym->used = 0;
 810         sym->liveFrom = 0;
 811         sym->liveTo = 0;
 812         freeBitVect (sym->clashes);
 813         sym->clashes = NULL;
 814       } while ( (sym = hTabNextItem (liveRanges, &key)));
 815     }
 816
 817   /* do the LR computation again */
 818   computeLiveRanges (ebbs, count);
 819 }
 820