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         werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
 446                   OP_SYMBOL (op)->prereqv);
 447       /* is this block part of a loop? */
 448       if (ebp->depth != 0)
 449         {
 450           /* extend the life range to the outermost loop */
 451           unvisitBlocks(ebbs, count);
 452           markWholeLoop (ebp, op->key);
 453         }
 454     }
 455 }
 456
 457 /*-----------------------------------------------------------------*/
 458 /* incUsed - increment a symbol's usage count                      */
 459 /*-----------------------------------------------------------------*/
 460 static void
 461 incUsed (iCode *ic, operand *op)
 462 {
 463   if (ic->depth)
 464     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 465   else
 466     OP_SYMBOL (op)->used += 1;
 467 }
 468
 469 /*-----------------------------------------------------------------*/
 470 /* rliveClear - clears the rlive bitVectors                        */
 471 /*-----------------------------------------------------------------*/
 472 static void
 473 rliveClear (eBBlock ** ebbs, int count)
 474 {
 475   int i;
 476
 477   /* for all blocks do */
 478   for (i = 0; i < count; i++)
 479     {
 480       iCode *ic;
 481
 482       /* for all instructions in this block do */
 483       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 484         {
 485           freeBitVect (ic->rlive);
 486           ic->rlive = NULL;
 487         }
 488     }
 489 }
 490
 491 /*-----------------------------------------------------------------*/
 492 /* rlivePoint - for each point compute the ranges that are alive   */
 493 /*-----------------------------------------------------------------*/
 494 static void
 495 rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
 496 {
 497   int i, key;
 498   eBBlock *succ;
 499   bitVect *alive;
 500
 501   /* for all blocks do */
 502   for (i = 0; i < count; i++)
 503     {
 504       iCode *ic;
 505
 506       /* for all instructions in this block do */
 507       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 508         {
 509
 510           if (!ic->rlive)
 511             ic->rlive = newBitVect (operandKey);
 512
 513           if (SKIP_IC2(ic))
 514             continue;
 515
 516           if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
 517             {
 518               incUsed (ic, IC_JTCOND(ic));
 519
 520               if (!IS_ITEMP(IC_JTCOND(ic)))
 521                 continue;
 522
 523               findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings);
 524               unvisitBlocks(ebbs, count);
 525               ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
 526               findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
 527
 528               continue;
 529             }
 530
 531           if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
 532             {
 533               incUsed (ic, IC_COND(ic));
 534
 535               if (!IS_ITEMP(IC_COND(ic)))
 536                 continue;
 537
 538               findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings);
 539               unvisitBlocks (ebbs, count);
 540               ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
 541               findNextUse (ebbs[i], ic->next, IC_COND(ic));
 542
 543               continue;
 544             }
 545
 546           if (IS_SYMOP(IC_LEFT(ic)))
 547             {
 548               incUsed (ic, IC_LEFT(ic));
 549               if (IS_ITEMP(IC_LEFT(ic)))
 550                 {
 551                   findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings);
 552                   unvisitBlocks(ebbs, count);
 553                   ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
 554                   findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
 555
 556                   /* if this is a send extend the LR to the call */
 557                   if (ic->op == SEND)
 558                     {
 559                       iCode *lic;
 560                       for (lic = ic; lic; lic = lic->next)
 561                         {
 562                           if (lic->op == CALL || lic->op == PCALL)
 563                             {
 564                               markAlive (ic, lic->prev, IC_LEFT (ic)->key);
 565                               break;
 566                             }
 567                         }
 568                     }
 569                 }
 570             }
 571
 572           if (IS_SYMOP(IC_RIGHT(ic)))
 573             {
 574               incUsed (ic, IC_RIGHT(ic));
 575               if (IS_ITEMP(IC_RIGHT(ic)))
 576                 {
 577                   findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings);
 578                   unvisitBlocks(ebbs, count);
 579                   ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
 580                   findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
 581                 }
 582             }
 583
 584           if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
 585             incUsed (ic, IC_RESULT(ic));
 586
 587           if (IS_ITEMP(IC_RESULT(ic)))
 588             {
 589               if (POINTER_SET(ic))
 590                 {
 591                   findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings);
 592                 }
 593               unvisitBlocks(ebbs, count);
 594               ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
 595               findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
 596             }
 597
 598           if (!POINTER_SET(ic) && IC_RESULT(ic))
 599             ic->defKey = IC_RESULT(ic)->key;
 600
 601         }
 602
 603       /* check all symbols that are alive in the last instruction */
 604       /* but are not alive in all successors */
 605
 606       succ = setFirstItem (ebbs[i]->succList);
 607       if (!succ)
 608         continue;
 609
 610       alive = succ->sch->rlive;
 611       while ((succ = setNextItem (ebbs[i]->succList)))
 612         {
 613           if (succ->sch)
 614             alive = bitVectIntersect (alive, succ->sch->rlive);
 615         }
 616
 617       if (ebbs[i]->ech)
 618         alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 619
 620       if(!alive)
 621         continue;
 622       for (key = 1; key < alive->size; key++)
 623         {
 624           if (!bitVectBitValue (alive, key))
 625             continue;
 626
 627           unvisitBlocks(ebbs, count);
 628           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 629         }
 630
 631     }
 632 }
 633
 634 /*-----------------------------------------------------------------*/
 635 /* computeClash - find out which live ranges collide with others   */
 636 /*-----------------------------------------------------------------*/
 637 static void
 638 computeClash (eBBlock ** ebbs, int count)
 639 {
 640   int i;
 641
 642   /* for all blocks do */
 643   for (i = 0; i < count; i++)
 644     {
 645       iCode *ic;
 646
 647       /* for every iCode do */
 648       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 649         {
 650           symbol *sym1, *sym2;
 651           int key1, key2;
 652
 653           /* for all iTemps alive at this iCode */
 654           for (key1 = 1; key1 < ic->rlive->size; key1++)
 655             {
 656               if (!bitVectBitValue(ic->rlive, key1))
 657                 continue;
 658
 659               sym1 = hTabItemWithKey(liveRanges, key1);
 660
 661               if (!sym1->isitmp)
 662                 continue;
 663
 664               /* for all other iTemps alive at this iCode */
 665               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 666                 {
 667                   if (!bitVectBitValue(ic->rlive, key2))
 668                     continue;
 669
 670                   sym2 = hTabItemWithKey(liveRanges, key2);
 671
 672                   if (!sym2->isitmp)
 673                     continue;
 674
 675                   /* if the result and left or right is an iTemp */
 676                   /* than possibly the iTemps do not clash */
 677                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 678                       IS_ITEMP(IC_RESULT(ic)) &&
 679                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 680                     {
 681                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1
 682                           && sym1->liveFrom == ic->seq
 683                           && sym2->liveTo == ic->seq)
 684                         {
 685                           if (IS_SYMOP(IC_LEFT(ic)))
 686                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 687                               continue;
 688                           if (IS_SYMOP(IC_RIGHT(ic)))
 689                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 690                               continue;
 691                         }
 692
 693                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2
 694                           && sym2->liveFrom == ic->seq
 695                           && sym1->liveTo == ic->seq)
 696                         {
 697                           if (IS_SYMOP(IC_LEFT(ic)))
 698                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 699                               continue;
 700                           if (IS_SYMOP(IC_RIGHT(ic)))
 701                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 702                               continue;
 703                         }
 704                     }
 705
 706                   /* the iTemps do clash. set the bits in clashes */
 707                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 708                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 709
 710                   /* check if they share the same spill location */
 711                   /* what is this good for? */
 712                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 713                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 714                     {
 715                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 716                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 717                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 718                       else SYM_SPIL_LOC(sym1)=NULL;
 719                     }
 720                 }
 721             }
 722         }
 723     }
 724 }
 725
 726 /*-----------------------------------------------------------------*/
 727 /* allDefsOutOfRange - all definitions are out of a range          */
 728 /*-----------------------------------------------------------------*/
 729 bool
 730 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 731 {
 732   int i;
 733
 734   if (!defs)
 735     return TRUE;
 736
 737   for (i = 0; i < defs->size; i++)
 738     {
 739       iCode *ic;
 740
 741       if (bitVectBitValue (defs, i) &&
 742           (ic = hTabItemWithKey (iCodehTab, i)) &&
 743           (ic->seq >= fseq && ic->seq <= toseq))
 744         return FALSE;
 745
 746     }
 747
 748   return TRUE;
 749 }
 750
 751 /*-----------------------------------------------------------------*/
 752 /* notUsedInBlock - not used in this block                         */
 753 /*-----------------------------------------------------------------*/
 754 int
 755 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 756 {
 757   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 758           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 759           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 760 }
 761
 762 /*-----------------------------------------------------------------*/
 763 /* adjustIChain - correct the sch and ech pointers                 */
 764 /*-----------------------------------------------------------------*/
 765 static void
 766 adjustIChain (eBBlock ** ebbs, int count)
 767 {
 768   int i;
 769
 770   for (i = 0; i < count; i++)
 771     {
 772       iCode *ic;
 773
 774       if (ebbs[i]->noPath)
 775         continue;
 776
 777       ic = ebbs[i]->sch;
 778
 779       /* is there any code for this eBBlock? (e.g. ROM assignment) */
 780       if(!ic)continue;
 781
 782       while (ic->prev)
 783         ic = ic->prev;
 784       ebbs[i]->sch = ic;
 785
 786       ic = ebbs[i]->ech;
 787       while (ic->next)
 788         ic = ic->next;
 789       ebbs[i]->ech = ic;
 790     }
 791 }
 792
 793 /*-----------------------------------------------------------------*/
 794 /* computeLiveRanges - computes the live ranges for variables      */
 795 /*-----------------------------------------------------------------*/
 796 void
 797 computeLiveRanges (eBBlock ** ebbs, int count, bool emitWarnings)
 798 {
 799   /* first look through all blocks and adjust the
 800      sch and ech pointers */
 801   adjustIChain (ebbs, count);
 802
 803   /* sequence the code the live ranges are computed
 804      in terms of this sequence additionally the
 805      routine will also create a hashtable of instructions */
 806   iCodeSeq = 0;
 807   setToNull ((void *) &iCodehTab);
 808   iCodehTab = newHashTable (iCodeKey);
 809   hashiCodeKeys (ebbs, count);
 810   setToNull ((void *) &iCodeSeqhTab);
 811   iCodeSeqhTab = newHashTable (iCodeKey);
 812   sequenceiCode (ebbs, count);
 813
 814   /* mark the ranges live for each point */
 815   setToNull ((void *) &liveRanges);
 816   rlivePoint (ebbs, count, emitWarnings);
 817
 818   /* mark the from & to live ranges for variables used */
 819   markLiveRanges (ebbs, count);
 820
 821   /* compute which overlaps with what */
 822   computeClash(ebbs, count);
 823 }
 824
 825 /*-----------------------------------------------------------------*/
 826 /* recomputeLiveRanges - recomputes the live ranges for variables  */
 827 /*-----------------------------------------------------------------*/
 828 void
 829 recomputeLiveRanges (eBBlock ** ebbs, int count)
 830 {
 831   symbol * sym;
 832   int key;
 833
 834   /* clear all rlive bitVectors */
 835   rliveClear (ebbs, count);
 836
 837   sym = hTabFirstItem (liveRanges, &key);
 838   if (sym)
 839     {
 840       do {
 841         sym->used = 0;
 842         sym->liveFrom = 0;
 843         sym->liveTo = 0;
 844         freeBitVect (sym->clashes);
 845         sym->clashes = NULL;
 846       } while ( (sym = hTabNextItem (liveRanges, &key)));
 847     }
 848
 849   /* do the LR computation again */
 850   computeLiveRanges (ebbs, count, FALSE);
 851 }
 852
 853 /*-----------------------------------------------------------------*/
 854 /* dump icode->rlive in all blocks                                 */
 855 /*-----------------------------------------------------------------*/
 856 #if 0
 857 void
 858 dumpIcRlive (eBBlock ** ebbs, int count)
 859 {
 860   int i, j;
 861   iCode *ic;
 862
 863   /* for all blocks do */
 864   for (i = 0; i < count; i++)
 865     {
 866       printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name);
 867       /* for all instructions in this block do */
 868       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 869         {
 870           printf ("\tic->key %d\n", ic->key);
 871
 872           if (!ic->rlive)
 873             continue;
 874           /* for all live Ranges alive at this point */
 875           for (j = 1; j < ic->rlive->size; j++)
 876             {
 877               symbol *sym;
 878
 879               if (!bitVectBitValue (ic->rlive, j))
 880                 continue;
 881
 882               /* find the live range we are interested in */
 883               if ((sym = hTabItemWithKey (liveRanges, j)))
 884                 printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name);
 885             }
 886         }
 887     }
 888 }
 889 #endif