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 /* rlivePoint - for each point compute the ranges that are alive   */
 337 /*-----------------------------------------------------------------*/
 338 void
 339 rlivePoint (eBBlock ** ebbs, int count)
 340 {
 341   int i, key;
 342   eBBlock *succ;
 343   bitVect *alive;
 344
 345   /* for all blocks do */
 346   for (i = 0; i < count; i++)
 347     {
 348       iCode *ic;
 349
 350       /* for all instructions in this block do */
 351       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 352         {
 353
 354           if (!ic->rlive)
 355             ic->rlive = newBitVect (operandKey);
 356
 357           if (SKIP_IC2(ic))
 358             continue;
 359
 360           if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
 361             {
 362               incUsed (ic, IC_JTCOND(ic));
 363
 364               if (!IS_ITEMP(IC_JTCOND(ic)))
 365                 continue;
 366
 367               unvisitBlocks(ebbs, count);
 368               ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
 369               findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
 370
 371               continue;
 372             }
 373
 374           if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
 375             {
 376               incUsed (ic, IC_COND(ic));
 377
 378               if (!IS_ITEMP(IC_COND(ic)))
 379                 continue;
 380
 381               unvisitBlocks (ebbs, count);
 382               ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
 383               findNextUse (ebbs[i], ic->next, IC_COND(ic));
 384
 385               continue;
 386             }
 387
 388           if (IS_SYMOP(IC_LEFT(ic)))
 389             {
 390               incUsed (ic, IC_LEFT(ic));
 391               if (IS_ITEMP(IC_LEFT(ic)))
 392                 {
 393
 394                   unvisitBlocks(ebbs, count);
 395                   ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
 396                   findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
 397
 398                   /* if this is a send extend the LR to the call */
 399                   if (ic->op == SEND)
 400                     {
 401                       iCode *lic;
 402                       for (lic = ic; lic; lic = lic->next)
 403                         {
 404                           if (lic->op == CALL)
 405                             {
 406                               markAlive (ic, lic->prev, IC_LEFT (ic)->key);
 407                               break;
 408                             }
 409                         }
 410                     }
 411                 }
 412             }
 413
 414           if (IS_SYMOP(IC_RIGHT(ic)))
 415             {
 416               incUsed (ic, IC_RIGHT(ic));
 417               if (IS_ITEMP(IC_RIGHT(ic)))
 418                 {
 419                   unvisitBlocks(ebbs, count);
 420                   ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
 421                   findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
 422                 }
 423             }
 424
 425           if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
 426             incUsed (ic, IC_RESULT(ic));
 427
 428           if (IS_ITEMP(IC_RESULT(ic)))
 429             {
 430               unvisitBlocks(ebbs, count);
 431               ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
 432               findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
 433             }
 434
 435           if (!POINTER_SET(ic) && IC_RESULT(ic))
 436             ic->defKey = IC_RESULT(ic)->key;
 437
 438         }
 439
 440       /* check all symbols that are alive in the last instruction */
 441       /* but are not alive in all successors */
 442
 443       succ = setFirstItem (ebbs[i]->succList);
 444       if (!succ)
 445         continue;
 446
 447       alive = succ->sch->rlive;
 448       while ((succ = setNextItem (ebbs[i]->succList)))
 449         {
 450           alive = bitVectIntersect (alive, succ->sch->rlive);
 451         }
 452
 453       alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 454
 455       for (key = 1; key < alive->size; key++)
 456         {
 457           if (!bitVectBitValue (alive, key))
 458             continue;
 459
 460           unvisitBlocks(ebbs, count);
 461           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 462         }
 463
 464     }
 465 }
 466
 467 /*-----------------------------------------------------------------*/
 468 /* computeClash - find out which live ranges collide with others   */
 469 /*-----------------------------------------------------------------*/
 470 static void
 471 computeClash (eBBlock ** ebbs, int count)
 472 {
 473   int i;
 474
 475   /* for all blocks do */
 476   for (i = 0; i < count; i++)
 477     {
 478       iCode *ic;
 479
 480       /* for every iCode do */
 481       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 482         {
 483           symbol *sym1, *sym2;
 484           int key1, key2;
 485
 486           /* for all iTemps alive at this iCode */
 487           for (key1 = 1; key1 < ic->rlive->size; key1++)
 488             {
 489               if (!bitVectBitValue(ic->rlive, key1))
 490                 continue;
 491
 492               sym1 = hTabItemWithKey(liveRanges, key1);
 493
 494               if (!sym1->isitmp)
 495                 continue;
 496
 497               /* for all other iTemps alive at this iCode */
 498               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 499                 {
 500                   if (!bitVectBitValue(ic->rlive, key2))
 501                     continue;
 502
 503                   sym2 = hTabItemWithKey(liveRanges, key2);
 504
 505                   if (!sym2->isitmp)
 506                     continue;
 507
 508                   /* if the result and left or right is an iTemp */
 509                   /* than possibly the iTemps do not clash */
 510                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 511                       IS_ITEMP(IC_RESULT(ic)) &&
 512                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 513                     {
 514                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1)
 515                         {
 516                           if (IS_SYMOP(IC_LEFT(ic)))
 517                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 518                               continue;
 519                           if (IS_SYMOP(IC_RIGHT(ic)))
 520                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 521                               continue;
 522                         }
 523
 524                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2)
 525                         {
 526                           if (IS_SYMOP(IC_LEFT(ic)))
 527                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 528                               continue;
 529                           if (IS_SYMOP(IC_RIGHT(ic)))
 530                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 531                               continue;
 532                         }
 533                     }
 534
 535                   /* the iTemps do clash. set the bits in clashes */
 536                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 537                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 538
 539                   /* check if they share the same spill location */
 540                   /* what is this good for? */
 541                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 542                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 543                     {
 544                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 545                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 546                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 547                       else SYM_SPIL_LOC(sym1)=NULL;
 548                     }
 549                 }
 550             }
 551         }
 552     }
 553 }
 554
 555 /*-----------------------------------------------------------------*/
 556 /* allDefsOutOfRange - all definitions are out of a range          */
 557 /*-----------------------------------------------------------------*/
 558 bool
 559 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 560 {
 561   int i;
 562
 563   if (!defs)
 564     return TRUE;
 565
 566   for (i = 0; i < defs->size; i++)
 567     {
 568       iCode *ic;
 569
 570       if (bitVectBitValue (defs, i) &&
 571           (ic = hTabItemWithKey (iCodehTab, i)) &&
 572           (ic->seq >= fseq && ic->seq <= toseq))
 573
 574         return FALSE;
 575
 576     }
 577
 578   return TRUE;
 579 }
 580
 581 /*-----------------------------------------------------------------*/
 582 /* notUsedInBlock - not used in this block                         */
 583 /*-----------------------------------------------------------------*/
 584 int
 585 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 586 {
 587   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 588           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 589           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 590 }
 591
 592 /*-----------------------------------------------------------------*/
 593 /* adjustIChain - correct the sch and ech pointers                 */
 594 /*-----------------------------------------------------------------*/
 595 void
 596 adjustIChain (eBBlock ** ebbs, int count)
 597 {
 598   int i;
 599
 600   for (i = 0; i < count; i++)
 601     {
 602       iCode *ic;
 603
 604       if (ebbs[i]->noPath)
 605         continue;
 606
 607       ic = ebbs[i]->sch;
 608       while (ic->prev)
 609         ic = ic->prev;
 610       ebbs[i]->sch = ic;
 611
 612       ic = ebbs[i]->ech;
 613       while (ic->next)
 614         ic = ic->next;
 615       ebbs[i]->ech = ic;
 616     }
 617 }
 618
 619 /*-----------------------------------------------------------------*/
 620 /* computeLiveRanges - computes the live ranges for variables      */
 621 /*-----------------------------------------------------------------*/
 622 void
 623 computeLiveRanges (eBBlock ** ebbs, int count)
 624 {
 625   /* first look through all blocks and adjust the
 626      sch and ech pointers */
 627   adjustIChain (ebbs, count);
 628
 629   /* sequence the code the live ranges are computed
 630      in terms of this sequence additionally the
 631      routine will also create a hashtable of instructions */
 632   iCodeSeq = 0;
 633   setToNull ((void *) &iCodehTab);
 634   iCodehTab = newHashTable (iCodeKey);
 635   hashiCodeKeys (ebbs, count);
 636   setToNull ((void *) &iCodeSeqhTab);
 637   iCodeSeqhTab = newHashTable (iCodeKey);
 638   sequenceiCode (ebbs, count);
 639
 640   /* mark the ranges live for each point */
 641   setToNull ((void *) &liveRanges);
 642   rlivePoint (ebbs, count);
 643
 644   /* mark the from & to live ranges for variables used */
 645   markLiveRanges (ebbs, count);
 646
 647   /* compute which overlaps with what */
 648   computeClash(ebbs, count);
 649 }
 650