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             }
 535
 536           if (IS_SYMOP(IC_RIGHT(ic)))
 537             {
 538               incUsed (ic, IC_RIGHT(ic));
 539               if (IS_ITEMP(IC_RIGHT(ic)))
 540                 {
 541                   findPrevUse (ebbs[i], ic->prev, IC_RIGHT(ic), ebbs, count);
 542                   unvisitBlocks(ebbs, count);
 543                   ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
 544                   findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
 545                 }
 546             }
 547
 548           if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
 549             incUsed (ic, IC_RESULT(ic));
 550
 551           if (IS_ITEMP(IC_RESULT(ic)))
 552             {
 553               if (POINTER_SET(ic))
 554                 {
 555                   findPrevUse (ebbs[i], ic->prev, IC_RESULT(ic), ebbs, count);
 556                 }
 557               unvisitBlocks(ebbs, count);
 558               ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
 559               findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
 560             }
 561
 562           if (!POINTER_SET(ic) && IC_RESULT(ic))
 563             ic->defKey = IC_RESULT(ic)->key;
 564
 565         }
 566
 567       /* check all symbols that are alive in the last instruction */
 568       /* but are not alive in all successors */
 569
 570       succ = setFirstItem (ebbs[i]->succList);
 571       if (!succ)
 572         continue;
 573
 574       alive = succ->sch->rlive;
 575       while ((succ = setNextItem (ebbs[i]->succList)))
 576         {
 577           if (succ->sch)
 578             alive = bitVectIntersect (alive, succ->sch->rlive);
 579         }
 580
 581       if (ebbs[i]->ech)
 582         alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 583
 584       if(!alive)
 585         continue;
 586       for (key = 1; key < alive->size; key++)
 587         {
 588           if (!bitVectBitValue (alive, key))
 589             continue;
 590
 591           unvisitBlocks(ebbs, count);
 592           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 593         }
 594
 595     }
 596 }
 597
 598 /*-----------------------------------------------------------------*/
 599 /* computeClash - find out which live ranges collide with others   */
 600 /*-----------------------------------------------------------------*/
 601 static void
 602 computeClash (eBBlock ** ebbs, int count)
 603 {
 604   int i;
 605
 606   /* for all blocks do */
 607   for (i = 0; i < count; i++)
 608     {
 609       iCode *ic;
 610
 611       /* for every iCode do */
 612       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 613         {
 614           symbol *sym1, *sym2;
 615           int key1, key2;
 616
 617           /* for all iTemps alive at this iCode */
 618           for (key1 = 1; key1 < ic->rlive->size; key1++)
 619             {
 620               if (!bitVectBitValue(ic->rlive, key1))
 621                 continue;
 622
 623               sym1 = hTabItemWithKey(liveRanges, key1);
 624
 625               if (!sym1->isitmp)
 626                 continue;
 627
 628               /* for all other iTemps alive at this iCode */
 629               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 630                 {
 631                   if (!bitVectBitValue(ic->rlive, key2))
 632                     continue;
 633
 634                   sym2 = hTabItemWithKey(liveRanges, key2);
 635
 636                   if (!sym2->isitmp)
 637                     continue;
 638
 639                   /* if the result and left or right is an iTemp */
 640                   /* than possibly the iTemps do not clash */
 641                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 642                       IS_ITEMP(IC_RESULT(ic)) &&
 643                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 644                     {
 645                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1
 646                           && sym1->liveFrom == ic->seq
 647                           && sym2->liveTo == ic->seq)
 648                         {
 649                           if (IS_SYMOP(IC_LEFT(ic)))
 650                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 651                               continue;
 652                           if (IS_SYMOP(IC_RIGHT(ic)))
 653                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 654                               continue;
 655                         }
 656
 657                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2
 658                           && sym2->liveFrom == ic->seq
 659                           && sym1->liveTo == ic->seq)
 660                         {
 661                           if (IS_SYMOP(IC_LEFT(ic)))
 662                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 663                               continue;
 664                           if (IS_SYMOP(IC_RIGHT(ic)))
 665                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 666                               continue;
 667                         }
 668                     }
 669
 670                   /* the iTemps do clash. set the bits in clashes */
 671                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 672                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 673
 674                   /* check if they share the same spill location */
 675                   /* what is this good for? */
 676                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 677                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 678                     {
 679                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 680                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 681                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 682                       else SYM_SPIL_LOC(sym1)=NULL;
 683                     }
 684                 }
 685             }
 686         }
 687     }
 688 }
 689
 690 /*-----------------------------------------------------------------*/
 691 /* allDefsOutOfRange - all definitions are out of a range          */
 692 /*-----------------------------------------------------------------*/
 693 bool
 694 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 695 {
 696   int i;
 697
 698   if (!defs)
 699     return TRUE;
 700
 701   for (i = 0; i < defs->size; i++)
 702     {
 703       iCode *ic;
 704
 705       if (bitVectBitValue (defs, i) &&
 706           (ic = hTabItemWithKey (iCodehTab, i)) &&
 707           (ic->seq >= fseq && ic->seq <= toseq))
 708         return FALSE;
 709
 710     }
 711
 712   return TRUE;
 713 }
 714
 715 /*-----------------------------------------------------------------*/
 716 /* notUsedInBlock - not used in this block                         */
 717 /*-----------------------------------------------------------------*/
 718 int
 719 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 720 {
 721   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 722           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 723           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 724 }
 725
 726 /*-----------------------------------------------------------------*/
 727 /* adjustIChain - correct the sch and ech pointers                 */
 728 /*-----------------------------------------------------------------*/
 729 void
 730 adjustIChain (eBBlock ** ebbs, int count)
 731 {
 732   int i;
 733
 734   for (i = 0; i < count; i++)
 735     {
 736       iCode *ic;
 737
 738       if (ebbs[i]->noPath)
 739         continue;
 740
 741       ic = ebbs[i]->sch;
 742
 743       /* is there any code for this eBBlock? (e.g. ROM assignment) */
 744       if(!ic)continue;
 745
 746       while (ic->prev)
 747         ic = ic->prev;
 748       ebbs[i]->sch = ic;
 749
 750       ic = ebbs[i]->ech;
 751       while (ic->next)
 752         ic = ic->next;
 753       ebbs[i]->ech = ic;
 754     }
 755 }
 756
 757 /*-----------------------------------------------------------------*/
 758 /* computeLiveRanges - computes the live ranges for variables      */
 759 /*-----------------------------------------------------------------*/
 760 void
 761 computeLiveRanges (eBBlock ** ebbs, int count)
 762 {
 763   /* first look through all blocks and adjust the
 764      sch and ech pointers */
 765   adjustIChain (ebbs, count);
 766
 767   /* sequence the code the live ranges are computed
 768      in terms of this sequence additionally the
 769      routine will also create a hashtable of instructions */
 770   iCodeSeq = 0;
 771   setToNull ((void *) &iCodehTab);
 772   iCodehTab = newHashTable (iCodeKey);
 773   hashiCodeKeys (ebbs, count);
 774   setToNull ((void *) &iCodeSeqhTab);
 775   iCodeSeqhTab = newHashTable (iCodeKey);
 776   sequenceiCode (ebbs, count);
 777
 778   /* mark the ranges live for each point */
 779   setToNull ((void *) &liveRanges);
 780   rlivePoint (ebbs, count);
 781
 782   /* mark the from & to live ranges for variables used */
 783   markLiveRanges (ebbs, count);
 784
 785   /* compute which overlaps with what */
 786   computeClash(ebbs, count);
 787 }
 788
 789 /*-----------------------------------------------------------------*/
 790 /* recomputeLiveRanges - recomputes the live ranges for variables  */
 791 /*-----------------------------------------------------------------*/
 792 void
 793 recomputeLiveRanges (eBBlock ** ebbs, int count)
 794 {
 795   symbol * sym;
 796   int key;
 797
 798   /* clear all rlive bitVectors */
 799   rliveClear (ebbs, count);
 800
 801   sym = hTabFirstItem (liveRanges, &key);
 802   if (sym)
 803     {
 804       do {
 805         sym->used = 0;
 806         sym->liveFrom = 0;
 807         sym->liveTo = 0;
 808         freeBitVect (sym->clashes);
 809         sym->clashes = NULL;
 810       } while ( (sym = hTabNextItem (liveRanges, &key)));
 811     }
 812
 813   /* do the LR computation again */
 814   computeLiveRanges (ebbs, count);
 815 }
 816