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 static 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 #if 0
  78 static void
  79 setFromRange (operand * op, int from)
  80 {
  81   /* only for compiler defined temporaries */
  82   if (!IS_ITEMP (op))
  83     return;
  84
  85   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
  86
  87   if (op->isaddr)
  88     OP_SYMBOL (op)->isptr = 1;
  89
  90   if (!OP_LIVEFROM (op) ||
  91       OP_LIVEFROM (op) > from)
  92     OP_LIVEFROM (op) = from;
  93 }
  94 #endif
  95
  96 /*-----------------------------------------------------------------*/
  97 /* setToRange - set the range to for an operand                    */
  98 /*-----------------------------------------------------------------*/
  99 void
 100 setToRange (operand * op, int to, bool check)
 101 {
 102   /* only for compiler defined temps */
 103   if (!IS_ITEMP (op))
 104     return;
 105
 106   OP_SYMBOL (op)->key = op->key;
 107   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 108
 109   if (op->isaddr)
 110     OP_SYMBOL (op)->isptr = 1;
 111
 112   if (check)
 113     if (!OP_LIVETO (op))
 114       OP_LIVETO (op) = to;
 115     else;
 116   else
 117     OP_LIVETO (op) = to;
 118 }
 119
 120 /*-----------------------------------------------------------------*/
 121 /* setFromRange - sets the from range of a given operand           */
 122 /*-----------------------------------------------------------------*/
 123 static void
 124 setLiveFrom (symbol * sym, int from)
 125 {
 126   if (!sym->liveFrom || sym->liveFrom > from)
 127     sym->liveFrom = from;
 128 }
 129
 130 /*-----------------------------------------------------------------*/
 131 /* setToRange - set the range to for an operand                    */
 132 /*-----------------------------------------------------------------*/
 133 static void
 134 setLiveTo (symbol * sym, int to)
 135 {
 136   if (!sym->liveTo || sym->liveTo < to)
 137     sym->liveTo = to;
 138 }
 139
 140 /*-----------------------------------------------------------------*/
 141 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 142 /*-----------------------------------------------------------------*/
 143 static void
 144 markLiveRanges (eBBlock ** ebbs, int count)
 145 {
 146   int i, key;
 147   symbol *sym;
 148
 149   for (i = 0; i < count; i++)
 150     {
 151       iCode *ic;
 152
 153       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 154         {
 155           if (ic->op == CALL || ic->op == PCALL)
 156             if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
 157               bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 158
 159           /* for all iTemps alive at this iCode */
 160           for (key = 1; key < ic->rlive->size; key++)
 161             {
 162               if (!bitVectBitValue(ic->rlive, key))
 163                 continue;
 164
 165               sym = hTabItemWithKey(liveRanges, key);
 166               setLiveTo(sym, ic->seq);
 167               setLiveFrom(sym, ic->seq);
 168             }
 169
 170         }
 171     }
 172 }
 173
 174 /*-----------------------------------------------------------------*/
 175 /* markAlive - marks the operand as alive between sic and eic      */
 176 /*-----------------------------------------------------------------*/
 177 static void
 178 markAlive (iCode * sic, iCode * eic, int key)
 179 {
 180   iCode *dic;
 181
 182   for (dic = sic; dic != eic->next; dic = dic->next)
 183     {
 184       dic->rlive = bitVectSetBit (dic->rlive, key);
 185     }
 186 }
 187
 188 /*-----------------------------------------------------------------*/
 189 /* findNextUseSym - finds the next use of the symbol and marks it  */
 190 /*                  alive in between                               */
 191 /*-----------------------------------------------------------------*/
 192 static int
 193 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
 194 {
 195   int retval = 0;
 196   iCode *uic;
 197   eBBlock *succ;
 198
 199   hTabAddItemIfNotP (&liveRanges, sym->key, sym);
 200
 201   if (!ic)
 202     goto check_successors;
 203
 204   /* if we check a complete block and the symbol */
 205   /* is alive at the beginning of the block */
 206   /* and not defined in the first instructions */
 207   /* then a next use exists (return 1) */
 208   if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
 209     {
 210       /* check if the first instruction is a def of this op */
 211       if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
 212         return 1;
 213
 214       if (IS_ITEMP(IC_RESULT(ic)))
 215         if (IC_RESULT(ic)->key == sym->key)
 216           return 0;
 217
 218       return 1;
 219     }
 220
 221   if (ebp->visited)
 222     return 0;
 223
 224   if (ic == ebp->sch)
 225     ebp->visited = 1;
 226
 227   /* for all remaining instructions in current block */
 228   for (uic = ic; uic; uic = uic->next)
 229     {
 230
 231       if (SKIP_IC2(uic))
 232         continue;
 233
 234       if (uic->op == JUMPTABLE)
 235         {
 236           if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
 237             {
 238               markAlive(ic, uic, sym->key);
 239               return 1;
 240             }
 241            continue;
 242         }
 243
 244       if (uic->op == IFX)
 245         {
 246           if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
 247             {
 248               markAlive(ic, uic, sym->key);
 249               return 1;
 250             }
 251            continue;
 252         }
 253
 254       if (IS_ITEMP (IC_LEFT (uic)))
 255         if (IC_LEFT (uic)->key == sym->key)
 256           {
 257             markAlive(ic, uic, sym->key);
 258             return 1;
 259           }
 260
 261       if (IS_ITEMP (IC_RIGHT (uic)))
 262         if (IC_RIGHT (uic)->key == sym->key)
 263           {
 264             markAlive (ic, uic, sym->key);
 265             return 1;
 266           }
 267
 268       if (IS_ITEMP (IC_RESULT (uic)))
 269         if (IC_RESULT (uic)->key == sym->key)
 270           {
 271             if (POINTER_SET (uic))
 272               {
 273                 markAlive (ic, uic, sym->key);
 274                 return 1;
 275               }
 276             else
 277               return 0;
 278           }
 279
 280     }
 281
 282   /* check all successors */
 283 check_successors:
 284
 285   succ = setFirstItem (ebp->succList);
 286   for (; succ; succ = setNextItem (ebp->succList))
 287     {
 288       retval += findNextUseSym (succ, succ->sch, sym);
 289     }
 290
 291   if (retval)
 292     {
 293       if (ic) markAlive (ic, ebp->ech, sym->key);
 294       return 1;
 295     }
 296
 297   return 0;
 298 }
 299
 300 /*-----------------------------------------------------------------*/
 301 /* findNextUse - finds the next use of the operand and marks it    */
 302 /*               alive in between                                  */
 303 /*-----------------------------------------------------------------*/
 304 static int
 305 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
 306 {
 307   if (op->isaddr)
 308     OP_SYMBOL (op)->isptr = 1;
 309
 310   OP_SYMBOL (op)->key = op->key;
 311
 312   return findNextUseSym (ebp, ic, OP_SYMBOL(op));
 313 }
 314
 315 /*-----------------------------------------------------------------*/
 316 /* unvisitBlocks - clears visited in all blocks                    */
 317 /*-----------------------------------------------------------------*/
 318 static void
 319 unvisitBlocks (eBBlock ** ebbs, int count)
 320 {
 321   int i;
 322
 323   for (i = 0; i < count; i++)
 324     ebbs[i]->visited = 0;
 325 }
 326
 327 /*------------------------------------------------------------------*/
 328 /* markWholeLoop - mark the symbol 'key' alive in all blocks        */
 329 /*                 included by the outermost loop                   */
 330 /*------------------------------------------------------------------*/
 331 static void
 332 markWholeLoop (eBBlock *ebp, int key)
 333 {
 334   eBBlock *ebpi;
 335
 336   /* avoid endless loops */
 337   ebp->visited = 1;
 338
 339   /* recurse through all predecessors */
 340   for (ebpi = setFirstItem (ebp->predList);
 341        ebpi;
 342        ebpi = setNextItem (ebp->predList))
 343     {
 344       if (ebpi->visited)
 345         continue;
 346       /* is the predecessor still in the loop? */
 347       if (ebpi->depth == 0)
 348         continue;
 349       markWholeLoop (ebpi, key);
 350     }
 351
 352   /* recurse through all successors */
 353   for (ebpi = setFirstItem (ebp->succList);
 354        ebpi;
 355        ebpi = setNextItem (ebp->succList))
 356     {
 357       if (ebpi->visited)
 358         continue;
 359       if (ebpi->depth == 0)
 360         continue;
 361       markWholeLoop (ebpi, key);
 362     }
 363
 364   markAlive (ebp->sch, ebp->ech, key);
 365 }
 366
 367 /*------------------------------------------------------------------*/
 368 /* findPrevUseSym - search for a previous definition of a symbol in */
 369 /*                  - the previous icodes                           */
 370 /*                  - all branches of predecessors                  */
 371 /*------------------------------------------------------------------*/
 372 static bool
 373 findPrevUseSym  (eBBlock *ebp, iCode *ic, symbol * sym)
 374 {
 375   eBBlock * pred;
 376   iCode * uic;
 377
 378   if (ebp->visited)
 379     {
 380      /* already visited: this branch must have been succesfull, */
 381      /* because otherwise the search would have been aborted. */
 382       return TRUE;
 383     }
 384   ebp->visited = 1;
 385
 386   /* search backward in the current block */
 387   for (uic = ic; uic; uic = uic->prev)
 388     {
 389       if (!POINTER_SET (uic) && IS_ITEMP (IC_RESULT (uic)))
 390         {
 391           if (IC_RESULT (uic)->key == sym->key)
 392             {
 393               /* Ok, found a definition */
 394               return TRUE;
 395             }
 396         }
 397     }
 398
 399   /* There's no definition in this bblock, */
 400   /* let's have a look at all predecessors. */
 401   pred = setFirstItem (ebp->predList);
 402   if (!pred)
 403     {
 404       /* no more predecessors and nothing found yet :-( */
 405       return FALSE;
 406     }
 407   for (; pred; pred = setNextItem (ebp->predList))
 408     {
 409       /* recurse into all predecessors */
 410       if (!findPrevUseSym (pred, pred->ech, sym))
 411         {
 412           /* found nothing: abort */
 413           return FALSE;
 414         }
 415     }
 416
 417   /* Success! Went through all branches with no abort: */
 418   /* all branches end with a definition */
 419   return TRUE;
 420 }
 421
 422 /*------------------------------------------------------------------*/
 423 /* findPrevUse - search for a previous definition of an operand     */
 424 /*                  If there's no definition let's:                 */
 425 /*                  - emit a warning                                */
 426 /*                  - fix the life range, if the symbol is used in  */
 427 /*                    a loop                                        */
 428 /*------------------------------------------------------------------*/
 429 static void
 430 findPrevUse (eBBlock *ebp, iCode *ic, operand *op,
 431              eBBlock ** ebbs, int count,
 432              bool emitWarnings)
 433 {
 434   unvisitBlocks (ebbs, count);
 435
 436   if (op->isaddr)
 437     OP_SYMBOL (op)->isptr = 1;
 438   OP_SYMBOL (op)->key = op->key;
 439
 440   /* There must be a definition in each branch of predecessors */
 441   if (!findPrevUseSym (ebp, ic->prev, OP_SYMBOL(op)))
 442     {
 443       /* computeLiveRanges() is called twice */
 444       if (!emitWarnings)
 445         {
 446           werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
 447                     OP_SYMBOL (op)->prereqv);
 448           OP_SYMBOL (op)->prereqv->reqv = NULL;
 449           OP_SYMBOL (op)->prereqv->allocreq = 1;
 450         }
 451       /* is this block part of a loop? */
 452       if (ebp->depth != 0)
 453         {
 454           /* extend the life range to the outermost loop */
 455           unvisitBlocks(ebbs, count);
 456           markWholeLoop (ebp, op->key);
 457         }
 458     }
 459 }
 460
 461 /*-----------------------------------------------------------------*/
 462 /* incUsed - increment a symbol's usage count                      */
 463 /*-----------------------------------------------------------------*/
 464 static void
 465 incUsed (iCode *ic, operand *op)
 466 {
 467   if (ic->depth)
 468     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 469   else
 470     OP_SYMBOL (op)->used += 1;
 471 }
 472
 473 /*-----------------------------------------------------------------*/
 474 /* rliveClear - clears the rlive bitVectors                        */
 475 /*-----------------------------------------------------------------*/
 476 static void
 477 rliveClear (eBBlock ** ebbs, int count)
 478 {
 479   int i;
 480
 481   /* for all blocks do */
 482   for (i = 0; i < count; i++)
 483     {
 484       iCode *ic;
 485
 486       /* for all instructions in this block do */
 487       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 488         {
 489           freeBitVect (ic->rlive);
 490           ic->rlive = NULL;
 491         }
 492     }
 493 }
 494
 495 /*-----------------------------------------------------------------*/
 496 /* rlivePoint - for each point compute the ranges that are alive   */
 497 /*-----------------------------------------------------------------*/
 498 static void
 499 rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
 500 {
 501   int i, key;
 502   eBBlock *succ;
 503   bitVect *alive;
 504
 505   /* for all blocks do */
 506   for (i = 0; i < count; i++)
 507     {
 508       iCode *ic;
 509
 510       /* for all instructions in this block do */
 511       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 512         {
 513
 514           if (!ic->rlive)
 515             ic->rlive = newBitVect (operandKey);
 516
 517           if (SKIP_IC2(ic))
 518             continue;
 519
 520           if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
 521             {
 522               incUsed (ic, IC_JTCOND(ic));
 523
 524               if (!IS_ITEMP(IC_JTCOND(ic)))
 525                 continue;
 526
 527               findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings);
 528               unvisitBlocks(ebbs, count);
 529               ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
 530               findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
 531
 532               continue;
 533             }
 534
 535           if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
 536             {
 537               incUsed (ic, IC_COND(ic));
 538
 539               if (!IS_ITEMP(IC_COND(ic)))
 540                 continue;
 541
 542               findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings);
 543               unvisitBlocks (ebbs, count);
 544               ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
 545               findNextUse (ebbs[i], ic->next, IC_COND(ic));
 546
 547               continue;
 548             }
 549
 550           if (IS_SYMOP(IC_LEFT(ic)))
 551             {
 552               incUsed (ic, IC_LEFT(ic));
 553               if (IS_ITEMP(IC_LEFT(ic)))
 554                 {
 555                   findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings);
 556                   unvisitBlocks(ebbs, count);
 557                   ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
 558                   findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
 559
 560                   /* if this is a send extend the LR to the call */
 561                   if (ic->op == SEND)
 562                     {
 563                       iCode *lic;
 564                       for (lic = ic; lic; lic = lic->next)
 565                         {
 566                           if (lic->op == CALL || lic->op == PCALL)
 567                             {
 568                               markAlive (ic, lic->prev, IC_LEFT (ic)->key);
 569                               break;
 570                             }
 571                         }
 572                     }
 573                 }
 574             }
 575
 576           if (IS_SYMOP(IC_RIGHT(ic)))
 577             {
 578               incUsed (ic, IC_RIGHT(ic));
 579               if (IS_ITEMP(IC_RIGHT(ic)))
 580                 {
 581                   findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings);
 582                   unvisitBlocks(ebbs, count);
 583                   ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
 584                   findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
 585                 }
 586             }
 587
 588           if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
 589             incUsed (ic, IC_RESULT(ic));
 590
 591           if (IS_ITEMP(IC_RESULT(ic)))
 592             {
 593               if (POINTER_SET(ic))
 594                 {
 595                   findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings);
 596                 }
 597               unvisitBlocks(ebbs, count);
 598               ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
 599               findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
 600             }
 601
 602           if (!POINTER_SET(ic) && IC_RESULT(ic))
 603             ic->defKey = IC_RESULT(ic)->key;
 604
 605         }
 606
 607       /* check all symbols that are alive in the last instruction */
 608       /* but are not alive in all successors */
 609
 610       succ = setFirstItem (ebbs[i]->succList);
 611       if (!succ)
 612         continue;
 613
 614       alive = succ->sch->rlive;
 615       while ((succ = setNextItem (ebbs[i]->succList)))
 616         {
 617           if (succ->sch)
 618             alive = bitVectIntersect (alive, succ->sch->rlive);
 619         }
 620
 621       if (ebbs[i]->ech)
 622         alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 623
 624       if(!alive)
 625         continue;
 626       for (key = 1; key < alive->size; key++)
 627         {
 628           if (!bitVectBitValue (alive, key))
 629             continue;
 630
 631           unvisitBlocks(ebbs, count);
 632           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 633         }
 634
 635     }
 636 }
 637
 638 /*-----------------------------------------------------------------*/
 639 /* computeClash - find out which live ranges collide with others   */
 640 /*-----------------------------------------------------------------*/
 641 static void
 642 computeClash (eBBlock ** ebbs, int count)
 643 {
 644   int i;
 645
 646   /* for all blocks do */
 647   for (i = 0; i < count; i++)
 648     {
 649       iCode *ic;
 650
 651       /* for every iCode do */
 652       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 653         {
 654           symbol *sym1, *sym2;
 655           int key1, key2;
 656
 657           /* for all iTemps alive at this iCode */
 658           for (key1 = 1; key1 < ic->rlive->size; key1++)
 659             {
 660               if (!bitVectBitValue(ic->rlive, key1))
 661                 continue;
 662
 663               sym1 = hTabItemWithKey(liveRanges, key1);
 664
 665               if (!sym1->isitmp)
 666                 continue;
 667
 668               /* for all other iTemps alive at this iCode */
 669               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 670                 {
 671                   if (!bitVectBitValue(ic->rlive, key2))
 672                     continue;
 673
 674                   sym2 = hTabItemWithKey(liveRanges, key2);
 675
 676                   if (!sym2->isitmp)
 677                     continue;
 678
 679                   /* if the result and left or right is an iTemp */
 680                   /* than possibly the iTemps do not clash */
 681                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 682                       IS_ITEMP(IC_RESULT(ic)) &&
 683                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 684                     {
 685                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1
 686                           && sym1->liveFrom == ic->seq
 687                           && sym2->liveTo == ic->seq)
 688                         {
 689                           if (IS_SYMOP(IC_LEFT(ic)))
 690                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 691                               continue;
 692                           if (IS_SYMOP(IC_RIGHT(ic)))
 693                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 694                               continue;
 695                         }
 696
 697                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2
 698                           && sym2->liveFrom == ic->seq
 699                           && sym1->liveTo == ic->seq)
 700                         {
 701                           if (IS_SYMOP(IC_LEFT(ic)))
 702                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 703                               continue;
 704                           if (IS_SYMOP(IC_RIGHT(ic)))
 705                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 706                               continue;
 707                         }
 708                     }
 709
 710                   /* the iTemps do clash. set the bits in clashes */
 711                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 712                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 713
 714                   /* check if they share the same spill location */
 715                   /* what is this good for? */
 716                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 717                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 718                     {
 719                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 720                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 721                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 722                       else SYM_SPIL_LOC(sym1)=NULL;
 723                     }
 724                 }
 725             }
 726         }
 727     }
 728 }
 729
 730 /*-----------------------------------------------------------------*/
 731 /* allDefsOutOfRange - all definitions are out of a range          */
 732 /*-----------------------------------------------------------------*/
 733 bool
 734 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 735 {
 736   int i;
 737
 738   if (!defs)
 739     return TRUE;
 740
 741   for (i = 0; i < defs->size; i++)
 742     {
 743       iCode *ic;
 744
 745       if (bitVectBitValue (defs, i) &&
 746           (ic = hTabItemWithKey (iCodehTab, i)) &&
 747           (ic->seq >= fseq && ic->seq <= toseq))
 748         return FALSE;
 749
 750     }
 751
 752   return TRUE;
 753 }
 754
 755 /*-----------------------------------------------------------------*/
 756 /* notUsedInBlock - not used in this block                         */
 757 /*-----------------------------------------------------------------*/
 758 int
 759 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 760 {
 761   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 762           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 763           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 764 }
 765
 766 /*-----------------------------------------------------------------*/
 767 /* adjustIChain - correct the sch and ech pointers                 */
 768 /*-----------------------------------------------------------------*/
 769 static void
 770 adjustIChain (eBBlock ** ebbs, int count)
 771 {
 772   int i;
 773
 774   for (i = 0; i < count; i++)
 775     {
 776       iCode *ic;
 777
 778       if (ebbs[i]->noPath)
 779         continue;
 780
 781       ic = ebbs[i]->sch;
 782
 783       /* is there any code for this eBBlock? (e.g. ROM assignment) */
 784       if(!ic)continue;
 785
 786       while (ic->prev)
 787         ic = ic->prev;
 788       ebbs[i]->sch = ic;
 789
 790       ic = ebbs[i]->ech;
 791       while (ic->next)
 792         ic = ic->next;
 793       ebbs[i]->ech = ic;
 794     }
 795 }
 796
 797 /*-----------------------------------------------------------------*/
 798 /* computeLiveRanges - computes the live ranges for variables      */
 799 /*-----------------------------------------------------------------*/
 800 void
 801 computeLiveRanges (eBBlock ** ebbs, int count, bool emitWarnings)
 802 {
 803   /* first look through all blocks and adjust the
 804      sch and ech pointers */
 805   adjustIChain (ebbs, count);
 806
 807   /* sequence the code the live ranges are computed
 808      in terms of this sequence additionally the
 809      routine will also create a hashtable of instructions */
 810   iCodeSeq = 0;
 811   setToNull ((void *) &iCodehTab);
 812   iCodehTab = newHashTable (iCodeKey);
 813   hashiCodeKeys (ebbs, count);
 814   setToNull ((void *) &iCodeSeqhTab);
 815   iCodeSeqhTab = newHashTable (iCodeKey);
 816   sequenceiCode (ebbs, count);
 817
 818   /* mark the ranges live for each point */
 819   setToNull ((void *) &liveRanges);
 820   rlivePoint (ebbs, count, emitWarnings);
 821
 822   /* mark the from & to live ranges for variables used */
 823   markLiveRanges (ebbs, count);
 824
 825   /* compute which overlaps with what */
 826   computeClash(ebbs, count);
 827 }
 828
 829 /*-----------------------------------------------------------------*/
 830 /* recomputeLiveRanges - recomputes the live ranges for variables  */
 831 /*-----------------------------------------------------------------*/
 832 void
 833 recomputeLiveRanges (eBBlock ** ebbs, int count)
 834 {
 835   symbol * sym;
 836   int key;
 837
 838   /* clear all rlive bitVectors */
 839   rliveClear (ebbs, count);
 840
 841   sym = hTabFirstItem (liveRanges, &key);
 842   if (sym)
 843     {
 844       do {
 845         sym->used = 0;
 846         sym->liveFrom = 0;
 847         sym->liveTo = 0;
 848         freeBitVect (sym->clashes);
 849         sym->clashes = NULL;
 850       } while ( (sym = hTabNextItem (liveRanges, &key)));
 851     }
 852
 853   /* do the LR computation again */
 854   computeLiveRanges (ebbs, count, FALSE);
 855 }
 856
 857 /*-----------------------------------------------------------------*/
 858 /* dump icode->rlive in all blocks                                 */
 859 /*-----------------------------------------------------------------*/
 860 #if 0
 861 void
 862 dumpIcRlive (eBBlock ** ebbs, int count)
 863 {
 864   int i, j;
 865   iCode *ic;
 866
 867   /* for all blocks do */
 868   for (i = 0; i < count; i++)
 869     {
 870       printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name);
 871       /* for all instructions in this block do */
 872       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 873         {
 874           printf ("\tic->key %d\n", ic->key);
 875
 876           if (!ic->rlive)
 877             continue;
 878           /* for all live Ranges alive at this point */
 879           for (j = 1; j < ic->rlive->size; j++)
 880             {
 881               symbol *sym;
 882
 883               if (!bitVectBitValue (ic->rlive, j))
 884                 continue;
 885
 886               /* find the live range we are interested in */
 887               if ((sym = hTabItemWithKey (liveRanges, j)))
 888                 printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name);
 889             }
 890         }
 891     }
 892 }
 893 #endif