git.gag.com Git - fw/sdcc/blob - src/SDCClrange.c

   1 /*-------------------------------------------------------------------------
   2
   3   SDCClrange.c - source file for live range computations
   4
   5              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
   6
   7    This program is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 2, or (at your option) any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20
  21    In other words, you are welcome to use, share and improve this program.
  22    You are forbidden to forbid anyone else to use, share and improve
  23    what you give them.   Help stamp out software-hoarding!
  24 -------------------------------------------------------------------------*/
  25
  26 #include "common.h"
  27 #include "limits.h"
  28
  29 int iCodeSeq = 0;
  30 hTab *liveRanges = NULL;
  31 hTab *iCodehTab = NULL;
  32 hTab *iCodeSeqhTab = NULL;
  33
  34 /*-----------------------------------------------------------------*/
  35 /* hashiCodeKeys - add all iCodes to the hash table                */
  36 /*-----------------------------------------------------------------*/
  37 void
  38 hashiCodeKeys (eBBlock ** ebbs, int count)
  39 {
  40   int i;
  41
  42   for (i = 0; i < count; i++)
  43     {
  44       iCode *ic;
  45       for (ic = ebbs[i]->sch; ic; ic = ic->next)
  46         hTabAddItem (&iCodehTab, ic->key, ic);
  47     }
  48 }
  49
  50 /*-----------------------------------------------------------------*/
  51 /* sequenceiCode - creates a sequence number for the iCode & add   */
  52 /*-----------------------------------------------------------------*/
  53 void
  54 sequenceiCode (eBBlock ** ebbs, int count)
  55 {
  56   int i;
  57
  58   for (i = 0; i < count; i++)
  59     {
  60
  61       iCode *ic;
  62       ebbs[i]->fSeq = iCodeSeq + 1;
  63       for (ic = ebbs[i]->sch; ic; ic = ic->next)
  64         {
  65           ic->seq = ++iCodeSeq;
  66           ic->depth = ebbs[i]->depth;
  67           //hTabAddItem (&iCodehTab, ic->key, ic);
  68           hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
  69         }
  70       ebbs[i]->lSeq = iCodeSeq;
  71     }
  72 }
  73
  74 /*-----------------------------------------------------------------*/
  75 /* setFromRange - sets the from range of a given operand           */
  76 /*-----------------------------------------------------------------*/
  77 void
  78 setFromRange (operand * op, int from)
  79 {
  80   /* only for compiler defined temporaries */
  81   if (!IS_ITEMP (op))
  82     return;
  83
  84   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
  85
  86   if (op->isaddr)
  87     OP_SYMBOL (op)->isptr = 1;
  88
  89   if (!OP_LIVEFROM (op) ||
  90       OP_LIVEFROM (op) > from)
  91     OP_LIVEFROM (op) = from;
  92 }
  93
  94 /*-----------------------------------------------------------------*/
  95 /* setToRange - set the range to for an operand                    */
  96 /*-----------------------------------------------------------------*/
  97 void
  98 setToRange (operand * op, int to, bool check)
  99 {
 100   /* only for compiler defined temps */
 101   if (!IS_ITEMP (op))
 102     return;
 103
 104   OP_SYMBOL (op)->key = op->key;
 105   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 106
 107   if (op->isaddr)
 108     OP_SYMBOL (op)->isptr = 1;
 109
 110   if (check)
 111     if (!OP_LIVETO (op))
 112       OP_LIVETO (op) = to;
 113     else;
 114   else
 115     OP_LIVETO (op) = to;
 116 }
 117
 118 /*-----------------------------------------------------------------*/
 119 /* setFromRange - sets the from range of a given operand           */
 120 /*-----------------------------------------------------------------*/
 121 void
 122 setLiveFrom (symbol * sym, int from)
 123 {
 124   if (!sym->liveFrom || sym->liveFrom > from)
 125     sym->liveFrom = from;
 126 }
 127
 128 /*-----------------------------------------------------------------*/
 129 /* setToRange - set the range to for an operand                    */
 130 /*-----------------------------------------------------------------*/
 131 void
 132 setLiveTo (symbol * sym, int to)
 133 {
 134   if (!sym->liveTo || sym->liveTo < to)
 135     sym->liveTo = to;
 136 }
 137
 138 /*-----------------------------------------------------------------*/
 139 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 140 /*-----------------------------------------------------------------*/
 141 void
 142 markLiveRanges (eBBlock ** ebbs, int count)
 143 {
 144   int i, key;
 145   symbol *sym;
 146
 147   for (i = 0; i < count; i++)
 148     {
 149       iCode *ic;
 150
 151       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 152         {
 153           if (ic->op == CALL || ic->op == PCALL)
 154               if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
 155                 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 156
 157           /* for all iTemps alive at this iCode */
 158           for (key = 1; key < ic->rlive->size; key++)
 159             {
 160               if (!bitVectBitValue(ic->rlive, key))
 161                 continue;
 162
 163               sym = hTabItemWithKey(liveRanges, key);
 164               setLiveTo(sym, ic->seq);
 165               setLiveFrom(sym, ic->seq);
 166             }
 167
 168         }
 169     }
 170 }
 171
 172 /*-----------------------------------------------------------------*/
 173 /* markAlive - marks the operand as alive between sic and eic      */
 174 /*-----------------------------------------------------------------*/
 175 void
 176 markAlive (iCode * sic, iCode * eic, int key)
 177 {
 178   iCode *dic;
 179
 180   for (dic = sic; dic != eic->next; dic = dic->next)
 181     {
 182       dic->rlive = bitVectSetBit (dic->rlive, key);
 183     }
 184 }
 185
 186 /*-----------------------------------------------------------------*/
 187 /* findNextUseSym - finds the next use of the symbol and marks it  */
 188 /*                  alive in between                               */
 189 /*-----------------------------------------------------------------*/
 190 int
 191 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
 192 {
 193   int retval = 0;
 194   iCode *uic;
 195   eBBlock *succ;
 196
 197   hTabAddItemIfNotP (&liveRanges, sym->key, sym);
 198
 199   if (!ic)
 200     goto check_successors;
 201
 202   /* if we check a complete block and the symbol */
 203   /* is alive at the beginning of the block */
 204   /* and not defined in the first instructions */
 205   /* then a next use exists (return 1) */
 206   if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
 207     {
 208       /* check if the first instruction is a def of this op */
 209       if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
 210         return 1;
 211
 212       if (IS_ITEMP(IC_RESULT(ic)))
 213         if (IC_RESULT(ic)->key == sym->key)
 214           return 0;
 215
 216       return 1;
 217     }
 218
 219   if (ebp->visited)
 220     return 0;
 221
 222   ebp->visited = 1;
 223
 224   /* for all remaining instructions in current block */
 225   for (uic = ic; uic; uic = uic->next)
 226     {
 227
 228       if (SKIP_IC2(uic))
 229         continue;
 230
 231       if (uic->op == JUMPTABLE)
 232         {
 233           if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
 234             {
 235               markAlive(ic, uic, sym->key);
 236               return 1;
 237             }
 238            continue;
 239          }
 240
 241       if (uic->op == IFX)
 242         {
 243           if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
 244             {
 245               markAlive(ic, uic, sym->key);
 246               return 1;
 247             }
 248            continue;
 249          }
 250
 251       if (IS_ITEMP (IC_LEFT (uic)))
 252         if (IC_LEFT (uic)->key == sym->key)
 253           {
 254             markAlive(ic, uic, sym->key);
 255             return 1;
 256           }
 257
 258       if (IS_ITEMP (IC_RIGHT (uic)))
 259         if (IC_RIGHT (uic)->key == sym->key)
 260           {
 261             markAlive (ic, uic, sym->key);
 262             return 1;
 263           }
 264
 265       if (IS_ITEMP (IC_RESULT (uic)))
 266         if (IC_RESULT (uic)->key == sym->key)
 267           {
 268             if (POINTER_SET (uic))
 269               {
 270                 markAlive (ic, uic, sym->key);
 271                 return 1;
 272               }
 273             else
 274               return 0;
 275           }
 276
 277     }
 278
 279   /* check all successors */
 280 check_successors:
 281
 282   succ = setFirstItem (ebp->succList);
 283   for (; succ; succ = setNextItem (ebp->succList))
 284     {
 285       retval += findNextUseSym (succ, succ->sch, sym);
 286     }
 287
 288   if (retval)
 289     {
 290       if (ic) markAlive (ic, ebp->ech, sym->key);
 291       return 1;
 292     }
 293
 294   return 0;
 295 }
 296
 297 /*-----------------------------------------------------------------*/
 298 /* findNextUse - finds the next use of the operand and marks it    */
 299 /*               alive in between                                  */
 300 /*-----------------------------------------------------------------*/
 301 int
 302 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
 303 {
 304   if (op->isaddr)
 305     OP_SYMBOL (op)->isptr = 1;
 306
 307   OP_SYMBOL (op)->key = op->key;
 308
 309   return findNextUseSym (ebp, ic, OP_SYMBOL(op));
 310 }
 311
 312 /*-----------------------------------------------------------------*/
 313 /* unvisitBlocks - clears visited in all blocks                    */
 314 /*-----------------------------------------------------------------*/
 315 void unvisitBlocks (eBBlock ** ebbs, int count)
 316 {
 317   int i;
 318
 319   for (i = 0; i < count; i++)
 320     ebbs[i]->visited = 0;
 321 }
 322
 323 /*-----------------------------------------------------------------*/
 324 /* unvisitBlocks - clears visited in all blocks                    */
 325 /*-----------------------------------------------------------------*/
 326 void
 327 incUsed (iCode *ic, operand *op)
 328 {
 329   if (ic->depth)
 330     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 331   else
 332     OP_SYMBOL (op)->used += 1;
 333 }
 334
 335 /*-----------------------------------------------------------------*/
 336 /* rliveClear - clears the rlive bitVectors                        */
 337 /*-----------------------------------------------------------------*/
 338 void
 339 rliveClear (eBBlock ** ebbs, int count)
 340 {
 341   int i;
 342
 343   /* for all blocks do */
 344   for (i = 0; i < count; i++)
 345     {
 346       iCode *ic;
 347
 348       /* for all instructions in this block do */
 349       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 350         {
 351           freeBitVect (ic->rlive);
 352           ic->rlive = NULL;
 353         }
 354     }
 355 }
 356
 357 /*-----------------------------------------------------------------*/
 358 /* rlivePoint - for each point compute the ranges that are alive   */
 359 /*-----------------------------------------------------------------*/
 360 void
 361 rlivePoint (eBBlock ** ebbs, int count)
 362 {
 363   int i, key;
 364   eBBlock *succ;
 365   bitVect *alive;
 366
 367   /* for all blocks do */
 368   for (i = 0; i < count; i++)
 369     {
 370       iCode *ic;
 371
 372       /* for all instructions in this block do */
 373       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 374         {
 375
 376           if (!ic->rlive)
 377             ic->rlive = newBitVect (operandKey);
 378
 379           if (SKIP_IC2(ic))
 380             continue;
 381
 382           if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
 383             {
 384               incUsed (ic, IC_JTCOND(ic));
 385
 386               if (!IS_ITEMP(IC_JTCOND(ic)))
 387                 continue;
 388
 389               unvisitBlocks(ebbs, count);
 390               ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
 391               findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
 392
 393               continue;
 394             }
 395
 396           if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
 397             {
 398               incUsed (ic, IC_COND(ic));
 399
 400               if (!IS_ITEMP(IC_COND(ic)))
 401                 continue;
 402
 403               unvisitBlocks (ebbs, count);
 404               ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
 405               findNextUse (ebbs[i], ic->next, IC_COND(ic));
 406
 407               continue;
 408             }
 409
 410           if (IS_SYMOP(IC_LEFT(ic)))
 411             {
 412               incUsed (ic, IC_LEFT(ic));
 413               if (IS_ITEMP(IC_LEFT(ic)))
 414                 {
 415
 416                   unvisitBlocks(ebbs, count);
 417                   ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
 418                   findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
 419
 420                   /* if this is a send extend the LR to the call */
 421                   if (ic->op == SEND)
 422                     {
 423                       iCode *lic;
 424                       for (lic = ic; lic; lic = lic->next)
 425                         {
 426                           if (lic->op == CALL)
 427                             {
 428                               markAlive (ic, lic->prev, IC_LEFT (ic)->key);
 429                               break;
 430                             }
 431                         }
 432                     }
 433                 }
 434             }
 435
 436           if (IS_SYMOP(IC_RIGHT(ic)))
 437             {
 438               incUsed (ic, IC_RIGHT(ic));
 439               if (IS_ITEMP(IC_RIGHT(ic)))
 440                 {
 441                   unvisitBlocks(ebbs, count);
 442                   ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
 443                   findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
 444                 }
 445             }
 446
 447           if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
 448             incUsed (ic, IC_RESULT(ic));
 449
 450           if (IS_ITEMP(IC_RESULT(ic)))
 451             {
 452               unvisitBlocks(ebbs, count);
 453               ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
 454               findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
 455             }
 456
 457           if (!POINTER_SET(ic) && IC_RESULT(ic))
 458             ic->defKey = IC_RESULT(ic)->key;
 459
 460         }
 461
 462       /* check all symbols that are alive in the last instruction */
 463       /* but are not alive in all successors */
 464
 465       succ = setFirstItem (ebbs[i]->succList);
 466       if (!succ)
 467         continue;
 468
 469       alive = succ->sch->rlive;
 470       while ((succ = setNextItem (ebbs[i]->succList)))
 471         {
 472           if (succ->sch)
 473             alive = bitVectIntersect (alive, succ->sch->rlive);
 474         }
 475
 476       if (ebbs[i]->ech)
 477         alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 478
 479       for (key = 1; key < alive->size; key++)
 480         {
 481           if (!bitVectBitValue (alive, key))
 482             continue;
 483
 484           unvisitBlocks(ebbs, count);
 485           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 486         }
 487
 488     }
 489 }
 490
 491 /*-----------------------------------------------------------------*/
 492 /* computeClash - find out which live ranges collide with others   */
 493 /*-----------------------------------------------------------------*/
 494 static void
 495 computeClash (eBBlock ** ebbs, int count)
 496 {
 497   int i;
 498
 499   /* for all blocks do */
 500   for (i = 0; i < count; i++)
 501     {
 502       iCode *ic;
 503
 504       /* for every iCode do */
 505       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 506         {
 507           symbol *sym1, *sym2;
 508           int key1, key2;
 509
 510           /* for all iTemps alive at this iCode */
 511           for (key1 = 1; key1 < ic->rlive->size; key1++)
 512             {
 513               if (!bitVectBitValue(ic->rlive, key1))
 514                 continue;
 515
 516               sym1 = hTabItemWithKey(liveRanges, key1);
 517
 518               if (!sym1->isitmp)
 519                 continue;
 520
 521               /* for all other iTemps alive at this iCode */
 522               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 523                 {
 524                   if (!bitVectBitValue(ic->rlive, key2))
 525                     continue;
 526
 527                   sym2 = hTabItemWithKey(liveRanges, key2);
 528
 529                   if (!sym2->isitmp)
 530                     continue;
 531
 532                   /* if the result and left or right is an iTemp */
 533                   /* than possibly the iTemps do not clash */
 534                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 535                       IS_ITEMP(IC_RESULT(ic)) &&
 536                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 537                     {
 538                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1)
 539                         {
 540                           if (IS_SYMOP(IC_LEFT(ic)))
 541                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 542                               continue;
 543                           if (IS_SYMOP(IC_RIGHT(ic)))
 544                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 545                               continue;
 546                         }
 547
 548                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2)
 549                         {
 550                           if (IS_SYMOP(IC_LEFT(ic)))
 551                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 552                               continue;
 553                           if (IS_SYMOP(IC_RIGHT(ic)))
 554                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 555                               continue;
 556                         }
 557                     }
 558
 559                   /* the iTemps do clash. set the bits in clashes */
 560                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 561                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 562
 563                   /* check if they share the same spill location */
 564                   /* what is this good for? */
 565                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 566                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 567                     {
 568                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 569                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 570                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 571                       else SYM_SPIL_LOC(sym1)=NULL;
 572                     }
 573                 }
 574             }
 575         }
 576     }
 577 }
 578
 579 /*-----------------------------------------------------------------*/
 580 /* allDefsOutOfRange - all definitions are out of a range          */
 581 /*-----------------------------------------------------------------*/
 582 bool
 583 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 584 {
 585   int i;
 586
 587   if (!defs)
 588     return TRUE;
 589
 590   for (i = 0; i < defs->size; i++)
 591     {
 592       iCode *ic;
 593
 594       if (bitVectBitValue (defs, i) &&
 595           (ic = hTabItemWithKey (iCodehTab, i)) &&
 596           (ic->seq >= fseq && ic->seq <= toseq))
 597
 598         return FALSE;
 599
 600     }
 601
 602   return TRUE;
 603 }
 604
 605 /*-----------------------------------------------------------------*/
 606 /* notUsedInBlock - not used in this block                         */
 607 /*-----------------------------------------------------------------*/
 608 int
 609 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 610 {
 611   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 612           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 613           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 614 }
 615
 616 /*-----------------------------------------------------------------*/
 617 /* adjustIChain - correct the sch and ech pointers                 */
 618 /*-----------------------------------------------------------------*/
 619 void
 620 adjustIChain (eBBlock ** ebbs, int count)
 621 {
 622   int i;
 623
 624   for (i = 0; i < count; i++)
 625     {
 626       iCode *ic;
 627
 628       if (ebbs[i]->noPath)
 629         continue;
 630
 631       ic = ebbs[i]->sch;
 632       while (ic->prev)
 633         ic = ic->prev;
 634       ebbs[i]->sch = ic;
 635
 636       ic = ebbs[i]->ech;
 637       while (ic->next)
 638         ic = ic->next;
 639       ebbs[i]->ech = ic;
 640     }
 641 }
 642
 643 /*-----------------------------------------------------------------*/
 644 /* computeLiveRanges - computes the live ranges for variables      */
 645 /*-----------------------------------------------------------------*/
 646 void
 647 computeLiveRanges (eBBlock ** ebbs, int count)
 648 {
 649   /* first look through all blocks and adjust the
 650      sch and ech pointers */
 651   adjustIChain (ebbs, count);
 652
 653   /* sequence the code the live ranges are computed
 654      in terms of this sequence additionally the
 655      routine will also create a hashtable of instructions */
 656   iCodeSeq = 0;
 657   setToNull ((void *) &iCodehTab);
 658   iCodehTab = newHashTable (iCodeKey);
 659   hashiCodeKeys (ebbs, count);
 660   setToNull ((void *) &iCodeSeqhTab);
 661   iCodeSeqhTab = newHashTable (iCodeKey);
 662   sequenceiCode (ebbs, count);
 663
 664   /* mark the ranges live for each point */
 665   setToNull ((void *) &liveRanges);
 666   rlivePoint (ebbs, count);
 667
 668   /* mark the from & to live ranges for variables used */
 669   markLiveRanges (ebbs, count);
 670
 671   /* compute which overlaps with what */
 672   computeClash(ebbs, count);
 673 }
 674
 675 /*-----------------------------------------------------------------*/
 676 /* recomputeLiveRanges - recomputes the live ranges for variables  */
 677 /*-----------------------------------------------------------------*/
 678 void
 679 recomputeLiveRanges (eBBlock ** ebbs, int count)
 680 {
 681   symbol * sym;
 682   int key;
 683
 684   /* clear all rlive bitVectors */
 685   rliveClear (ebbs, count);
 686
 687   sym = hTabFirstItem (liveRanges, &key);
 688   if (sym)
 689     {
 690       do {
 691         sym->used = 0;
 692         sym->liveFrom = 0;
 693         sym->liveTo = 0;
 694         freeBitVect (sym->clashes);
 695         sym->clashes = NULL;
 696       } while ( (sym = hTabNextItem (liveRanges, &key)));
 697     }
 698
 699   /* do the LR computation again */
 700   computeLiveRanges (ebbs, count);
 701 }
 702