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       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           alive = bitVectIntersect (alive, succ->sch->rlive);
 473         }
 474
 475       alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 476
 477       for (key = 1; key < alive->size; key++)
 478         {
 479           if (!bitVectBitValue (alive, key))
 480             continue;
 481
 482           unvisitBlocks(ebbs, count);
 483           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 484         }
 485
 486     }
 487 }
 488
 489 /*-----------------------------------------------------------------*/
 490 /* computeClash - find out which live ranges collide with others   */
 491 /*-----------------------------------------------------------------*/
 492 static void
 493 computeClash (eBBlock ** ebbs, int count)
 494 {
 495   int i;
 496
 497   /* for all blocks do */
 498   for (i = 0; i < count; i++)
 499     {
 500       iCode *ic;
 501
 502       /* for every iCode do */
 503       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 504         {
 505           symbol *sym1, *sym2;
 506           int key1, key2;
 507
 508           /* for all iTemps alive at this iCode */
 509           for (key1 = 1; key1 < ic->rlive->size; key1++)
 510             {
 511               if (!bitVectBitValue(ic->rlive, key1))
 512                 continue;
 513
 514               sym1 = hTabItemWithKey(liveRanges, key1);
 515
 516               if (!sym1->isitmp)
 517                 continue;
 518
 519               /* for all other iTemps alive at this iCode */
 520               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 521                 {
 522                   if (!bitVectBitValue(ic->rlive, key2))
 523                     continue;
 524
 525                   sym2 = hTabItemWithKey(liveRanges, key2);
 526
 527                   if (!sym2->isitmp)
 528                     continue;
 529
 530                   /* if the result and left or right is an iTemp */
 531                   /* than possibly the iTemps do not clash */
 532                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 533                       IS_ITEMP(IC_RESULT(ic)) &&
 534                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 535                     {
 536                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1)
 537                         {
 538                           if (IS_SYMOP(IC_LEFT(ic)))
 539                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 540                               continue;
 541                           if (IS_SYMOP(IC_RIGHT(ic)))
 542                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 543                               continue;
 544                         }
 545
 546                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2)
 547                         {
 548                           if (IS_SYMOP(IC_LEFT(ic)))
 549                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 550                               continue;
 551                           if (IS_SYMOP(IC_RIGHT(ic)))
 552                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 553                               continue;
 554                         }
 555                     }
 556
 557                   /* the iTemps do clash. set the bits in clashes */
 558                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 559                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 560
 561                   /* check if they share the same spill location */
 562                   /* what is this good for? */
 563                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 564                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 565                     {
 566                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 567                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 568                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 569                       else SYM_SPIL_LOC(sym1)=NULL;
 570                     }
 571                 }
 572             }
 573         }
 574     }
 575 }
 576
 577 /*-----------------------------------------------------------------*/
 578 /* allDefsOutOfRange - all definitions are out of a range          */
 579 /*-----------------------------------------------------------------*/
 580 bool
 581 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 582 {
 583   int i;
 584
 585   if (!defs)
 586     return TRUE;
 587
 588   for (i = 0; i < defs->size; i++)
 589     {
 590       iCode *ic;
 591
 592       if (bitVectBitValue (defs, i) &&
 593           (ic = hTabItemWithKey (iCodehTab, i)) &&
 594           (ic->seq >= fseq && ic->seq <= toseq))
 595
 596         return FALSE;
 597
 598     }
 599
 600   return TRUE;
 601 }
 602
 603 /*-----------------------------------------------------------------*/
 604 /* notUsedInBlock - not used in this block                         */
 605 /*-----------------------------------------------------------------*/
 606 int
 607 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 608 {
 609   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 610           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 611           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 612 }
 613
 614 /*-----------------------------------------------------------------*/
 615 /* adjustIChain - correct the sch and ech pointers                 */
 616 /*-----------------------------------------------------------------*/
 617 void
 618 adjustIChain (eBBlock ** ebbs, int count)
 619 {
 620   int i;
 621
 622   for (i = 0; i < count; i++)
 623     {
 624       iCode *ic;
 625
 626       if (ebbs[i]->noPath)
 627         continue;
 628
 629       ic = ebbs[i]->sch;
 630       while (ic->prev)
 631         ic = ic->prev;
 632       ebbs[i]->sch = ic;
 633
 634       ic = ebbs[i]->ech;
 635       while (ic->next)
 636         ic = ic->next;
 637       ebbs[i]->ech = ic;
 638     }
 639 }
 640
 641 /*-----------------------------------------------------------------*/
 642 /* computeLiveRanges - computes the live ranges for variables      */
 643 /*-----------------------------------------------------------------*/
 644 void
 645 computeLiveRanges (eBBlock ** ebbs, int count)
 646 {
 647   /* first look through all blocks and adjust the
 648      sch and ech pointers */
 649   adjustIChain (ebbs, count);
 650
 651   /* sequence the code the live ranges are computed
 652      in terms of this sequence additionally the
 653      routine will also create a hashtable of instructions */
 654   iCodeSeq = 0;
 655   setToNull ((void *) &iCodehTab);
 656   iCodehTab = newHashTable (iCodeKey);
 657   hashiCodeKeys (ebbs, count);
 658   setToNull ((void *) &iCodeSeqhTab);
 659   iCodeSeqhTab = newHashTable (iCodeKey);
 660   sequenceiCode (ebbs, count);
 661
 662   /* mark the ranges live for each point */
 663   setToNull ((void *) &liveRanges);
 664   rlivePoint (ebbs, count);
 665
 666   /* mark the from & to live ranges for variables used */
 667   markLiveRanges (ebbs, count);
 668
 669   /* compute which overlaps with what */
 670   computeClash(ebbs, count);
 671 }
 672
 673 /*-----------------------------------------------------------------*/
 674 /* recomputeLiveRanges - recomputes the live ranges for variables  */
 675 /*-----------------------------------------------------------------*/
 676 void
 677 recomputeLiveRanges (eBBlock ** ebbs, int count)
 678 {
 679   symbol * sym;
 680   int key;
 681
 682   /* clear all rlive bitVectors */
 683   rliveClear (ebbs, count);
 684
 685   sym = hTabFirstItem (liveRanges, &key);
 686   if (sym)
 687     {
 688       do {
 689         sym->used = 0;
 690         sym->liveFrom = 0;
 691         sym->liveTo = 0;
 692         freeBitVect (sym->clashes);
 693         sym->clashes = NULL;
 694       } while ( (sym = hTabNextItem (liveRanges, &key)));
 695     }
 696
 697   /* do the LR computation again */
 698   computeLiveRanges (ebbs, count);
 699 }
 700