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