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