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 /* sequenceiCode - creates a sequence number for the iCode & add   */
  36 /*-----------------------------------------------------------------*/
  37 void
  38 sequenceiCode (eBBlock ** ebbs, int count)
  39 {
  40   int i;
  41
  42   for (i = 0; i < count; i++)
  43     {
  44
  45       iCode *ic;
  46       ebbs[i]->fSeq = iCodeSeq + 1;
  47       for (ic = ebbs[i]->sch; ic; ic = ic->next)
  48         {
  49           ic->seq = ++iCodeSeq;
  50           ic->depth = ebbs[i]->depth;
  51           hTabAddItem (&iCodehTab, ic->key, ic);
  52           hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
  53         }
  54       ebbs[i]->lSeq = iCodeSeq;
  55     }
  56 }
  57
  58 /*-----------------------------------------------------------------*/
  59 /* setFromRange - sets the from range of a given operand           */
  60 /*-----------------------------------------------------------------*/
  61 void
  62 setFromRange (operand * op, int from)
  63 {
  64   /* only for compiler defined temporaries */
  65   if (!IS_ITEMP (op))
  66     return;
  67
  68   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
  69
  70   if (op->isaddr)
  71     OP_SYMBOL (op)->isptr = 1;
  72
  73   if (!OP_LIVEFROM (op) ||
  74       OP_LIVEFROM (op) > from)
  75     OP_LIVEFROM (op) = from;
  76 }
  77
  78 /*-----------------------------------------------------------------*/
  79 /* setToRange - set the range to for an operand                    */
  80 /*-----------------------------------------------------------------*/
  81 void
  82 setToRange (operand * op, int to, bool check)
  83 {
  84   /* only for compiler defined temps */
  85   if (!IS_ITEMP (op))
  86     return;
  87
  88   OP_SYMBOL (op)->key = op->key;
  89   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
  90
  91   if (op->isaddr)
  92     OP_SYMBOL (op)->isptr = 1;
  93
  94   if (check)
  95     if (!OP_LIVETO (op))
  96       OP_LIVETO (op) = to;
  97     else;
  98   else
  99     OP_LIVETO (op) = to;
 100 }
 101
 102 /*-----------------------------------------------------------------*/
 103 /* setFromRange - sets the from range of a given operand           */
 104 /*-----------------------------------------------------------------*/
 105 void
 106 setLiveFrom (symbol * sym, int from)
 107 {
 108   if (!sym->liveFrom || sym->liveFrom > from)
 109     sym->liveFrom = from;
 110 }
 111
 112 /*-----------------------------------------------------------------*/
 113 /* setToRange - set the range to for an operand                    */
 114 /*-----------------------------------------------------------------*/
 115 void
 116 setLiveTo (symbol * sym, int to)
 117 {
 118   if (!sym->liveTo || sym->liveTo < to)
 119     sym->liveTo = to;
 120 }
 121
 122 /*-----------------------------------------------------------------*/
 123 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 124 /*-----------------------------------------------------------------*/
 125 void
 126 markLiveRanges (eBBlock ** ebbs, int count)
 127 {
 128   int i, key;
 129   symbol *sym;
 130
 131   for (i = 0; i < count; i++)
 132     {
 133       iCode *ic;
 134
 135       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 136         {
 137           if (ic->op == CALL || ic->op == PCALL)
 138               if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
 139                 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 140
 141           /* for all iTemps alive at this iCode */
 142           for (key = 1; key < ic->rlive->size; key++)
 143             {
 144               if (!bitVectBitValue(ic->rlive, key))
 145                 continue;
 146
 147               sym = hTabItemWithKey(liveRanges, key);
 148               setLiveTo(sym, ic->seq);
 149               setLiveFrom(sym, ic->seq);
 150             }
 151
 152         }
 153     }
 154 }
 155
 156 /*-----------------------------------------------------------------*/
 157 /* markAlive - marks the operand as alive between sic and eic      */
 158 /*-----------------------------------------------------------------*/
 159 void
 160 markAlive (iCode * sic, iCode * eic, int key)
 161 {
 162   iCode *dic;
 163
 164   for (dic = sic; dic != eic->next; dic = dic->next)
 165     {
 166       dic->rlive = bitVectSetBit (dic->rlive, key);
 167     }
 168 }
 169
 170 /*-----------------------------------------------------------------*/
 171 /* findNextUseSym - finds the next use of the symbol and marks it  */
 172 /*                  alive in between                               */
 173 /*-----------------------------------------------------------------*/
 174 int
 175 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
 176 {
 177   int retval = 0;
 178   iCode *uic;
 179   eBBlock *succ;
 180
 181   hTabAddItemIfNotP (&liveRanges, sym->key, sym);
 182
 183   if (!ic)
 184     goto check_successors;
 185
 186   /* if we check a complete block and the symbol */
 187   /* is alive at the beginning of the block */
 188   /* and not defined in the first instructions */
 189   /* then a next use exists (return 1) */
 190   if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
 191     {
 192       /* check if the first instruction is a def of this op */
 193       if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
 194         return 1;
 195
 196       if (IS_ITEMP(IC_RESULT(ic)))
 197         if (IC_RESULT(ic)->key == sym->key)
 198           return 0;
 199
 200       return 1;
 201     }
 202
 203   if (ebp->visited)
 204     return 0;
 205
 206   ebp->visited = 1;
 207
 208   /* for all remaining instructions in current block */
 209   for (uic = ic; uic; uic = uic->next)
 210     {
 211
 212       if (SKIP_IC2(uic))
 213         continue;
 214
 215       if (uic->op == JUMPTABLE)
 216         {
 217           if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
 218             {
 219               markAlive(ic, uic, sym->key);
 220               return 1;
 221             }
 222            continue;
 223          }
 224
 225       if (uic->op == IFX)
 226         {
 227           if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
 228             {
 229               markAlive(ic, uic, sym->key);
 230               return 1;
 231             }
 232            continue;
 233          }
 234
 235       if (IS_ITEMP (IC_LEFT (uic)))
 236         if (IC_LEFT (uic)->key == sym->key)
 237           {
 238             markAlive(ic, uic, sym->key);
 239             return 1;
 240           }
 241
 242       if (IS_ITEMP (IC_RIGHT (uic)))
 243         if (IC_RIGHT (uic)->key == sym->key)
 244           {
 245             markAlive (ic, uic, sym->key);
 246             return 1;
 247           }
 248
 249       if (IS_ITEMP (IC_RESULT (uic)))
 250         if (IC_RESULT (uic)->key == sym->key)
 251           {
 252             if (POINTER_SET (uic))
 253               {
 254                 markAlive (ic, uic, sym->key);
 255                 return 1;
 256               }
 257             else
 258               return 0;
 259           }
 260
 261     }
 262
 263   /* check all successors */
 264 check_successors:
 265
 266   succ = setFirstItem (ebp->succList);
 267   for (; succ; succ = setNextItem (ebp->succList))
 268     {
 269       retval += findNextUseSym (succ, succ->sch, sym);
 270     }
 271
 272   if (retval)
 273     {
 274       markAlive (ic, ebp->ech, sym->key);
 275       return 1;
 276     }
 277
 278   return 0;
 279 }
 280
 281 /*-----------------------------------------------------------------*/
 282 /* findNextUse - finds the next use of the operand and marks it    */
 283 /*               alive in between                                  */
 284 /*-----------------------------------------------------------------*/
 285 int
 286 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
 287 {
 288   if (op->isaddr)
 289     OP_SYMBOL (op)->isptr = 1;
 290
 291   OP_SYMBOL (op)->key = op->key;
 292
 293   return findNextUseSym (ebp, ic, OP_SYMBOL(op));
 294 }
 295
 296 /*-----------------------------------------------------------------*/
 297 /* unvisitBlocks - clears visited in all blocks                    */
 298 /*-----------------------------------------------------------------*/
 299 void unvisitBlocks (eBBlock ** ebbs, int count)
 300 {
 301   int i;
 302
 303   for (i = 0; i < count; i++)
 304     ebbs[i]->visited = 0;
 305 }
 306
 307 /*-----------------------------------------------------------------*/
 308 /* unvisitBlocks - clears visited in all blocks                    */
 309 /*-----------------------------------------------------------------*/
 310 void
 311 incUsed (iCode *ic, operand *op)
 312 {
 313   if (ic->depth)
 314     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 315   else
 316     OP_SYMBOL (op)->used += 1;
 317 }
 318
 319 /*-----------------------------------------------------------------*/
 320 /* rlivePoint - for each point compute the ranges that are alive   */
 321 /*-----------------------------------------------------------------*/
 322 void
 323 rlivePoint (eBBlock ** ebbs, int count)
 324 {
 325   int i, key;
 326   eBBlock *succ;
 327   bitVect *alive;
 328
 329   /* for all blocks do */
 330   for (i = 0; i < count; i++)
 331     {
 332       iCode *ic;
 333
 334       /* for all instructions in this block do */
 335       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 336         {
 337
 338           if (!ic->rlive)
 339             ic->rlive = newBitVect (operandKey);
 340
 341           if (SKIP_IC2(ic))
 342             continue;
 343
 344           if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
 345             {
 346               incUsed (ic, IC_JTCOND(ic));
 347
 348               if (!IS_ITEMP(IC_JTCOND(ic)))
 349                 continue;
 350
 351               unvisitBlocks(ebbs, count);
 352               ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
 353               findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
 354
 355               continue;
 356             }
 357
 358           if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
 359             {
 360               incUsed (ic, IC_COND(ic));
 361
 362               if (!IS_ITEMP(IC_COND(ic)))
 363                 continue;
 364
 365               unvisitBlocks (ebbs, count);
 366               ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
 367               findNextUse (ebbs[i], ic->next, IC_COND(ic));
 368
 369               continue;
 370             }
 371
 372           if (IS_SYMOP(IC_LEFT(ic)))
 373             {
 374               incUsed (ic, IC_LEFT(ic));
 375               if (IS_ITEMP(IC_LEFT(ic)))
 376                 {
 377
 378                   unvisitBlocks(ebbs, count);
 379                   ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
 380                   findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
 381
 382                   /* if this is a send extend the LR to the call */
 383                   if (ic->op == SEND)
 384                     {
 385                       iCode *lic;
 386                       for (lic = ic; lic; lic = lic->next)
 387                         {
 388                           if (lic->op == CALL)
 389                             {
 390                               markAlive (ic, lic->prev, IC_LEFT (ic)->key);
 391                               break;
 392                             }
 393                         }
 394                     }
 395                 }
 396             }
 397
 398           if (IS_SYMOP(IC_RIGHT(ic)))
 399             {
 400               incUsed (ic, IC_RIGHT(ic));
 401               if (IS_ITEMP(IC_RIGHT(ic)))
 402                 {
 403                   unvisitBlocks(ebbs, count);
 404                   ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
 405                   findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
 406                 }
 407             }
 408
 409           if (IS_ITEMP(IC_RESULT(ic)))
 410             {
 411               unvisitBlocks(ebbs, count);
 412               ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
 413               findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
 414             }
 415
 416           if (!POINTER_SET(ic) && IC_RESULT(ic))
 417             ic->defKey = IC_RESULT(ic)->key;
 418
 419         }
 420
 421       /* check all symbols that are alive in the last instruction */
 422       /* but are not alive in all successors */
 423
 424       succ = setFirstItem (ebbs[i]->succList);
 425       if (!succ)
 426         continue;
 427
 428       alive = succ->sch->rlive;
 429       while ((succ = setNextItem (ebbs[i]->succList)))
 430         {
 431           alive = bitVectIntersect (alive, succ->sch->rlive);
 432         }
 433
 434       alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
 435
 436       for (key = 1; key < alive->size; key++)
 437         {
 438           if (!bitVectBitValue (alive, key))
 439             continue;
 440
 441           unvisitBlocks(ebbs, count);
 442           findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
 443         }
 444
 445     }
 446 }
 447
 448 /*-----------------------------------------------------------------*/
 449 /* computeClash - find out which live ranges collide with others   */
 450 /*-----------------------------------------------------------------*/
 451 static void
 452 computeClash (eBBlock ** ebbs, int count)
 453 {
 454   int i;
 455
 456   /* for all blocks do */
 457   for (i = 0; i < count; i++)
 458     {
 459       iCode *ic;
 460
 461       /* for every iCode do */
 462       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 463         {
 464           symbol *sym1, *sym2;
 465           int key1, key2;
 466
 467           /* for all iTemps alive at this iCode */
 468           for (key1 = 1; key1 < ic->rlive->size; key1++)
 469             {
 470               if (!bitVectBitValue(ic->rlive, key1))
 471                 continue;
 472
 473               sym1 = hTabItemWithKey(liveRanges, key1);
 474
 475               if (!sym1->isitmp)
 476                 continue;
 477
 478               /* for all other iTemps alive at this iCode */
 479               for (key2 = key1+1; key2 < ic->rlive->size; key2++)
 480                 {
 481                   if (!bitVectBitValue(ic->rlive, key2))
 482                     continue;
 483
 484                   sym2 = hTabItemWithKey(liveRanges, key2);
 485
 486                   if (!sym2->isitmp)
 487                     continue;
 488
 489                   /* if the result and left or right is an iTemp */
 490                   /* than possibly the iTemps do not clash */
 491                   if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
 492                       IS_ITEMP(IC_RESULT(ic)) &&
 493                       (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
 494                     {
 495                       if (OP_SYMBOL(IC_RESULT(ic))->key == key1)
 496                         {
 497                           if (IS_SYMOP(IC_LEFT(ic)))
 498                             if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
 499                               continue;
 500                           if (IS_SYMOP(IC_RIGHT(ic)))
 501                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
 502                               continue;
 503                         }
 504
 505                       if (OP_SYMBOL(IC_RESULT(ic))->key == key2)
 506                         {
 507                           if (IS_SYMOP(IC_LEFT(ic)))
 508                             if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
 509                               continue;
 510                           if (IS_SYMOP(IC_RIGHT(ic)))
 511                             if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
 512                               continue;
 513                         }
 514                     }
 515
 516                   /* the iTemps do clash. set the bits in clashes */
 517                   sym1->clashes = bitVectSetBit (sym1->clashes, key2);
 518                   sym2->clashes = bitVectSetBit (sym2->clashes, key1);
 519
 520                   /* check if they share the same spill location */
 521                   /* what is this good for? */
 522                   if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
 523                       SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
 524                     {
 525                       if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
 526                       else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
 527                       else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
 528                       else SYM_SPIL_LOC(sym1)=NULL;
 529                     }
 530                 }
 531             }
 532         }
 533     }
 534 }
 535
 536 /*-----------------------------------------------------------------*/
 537 /* allDefsOutOfRange - all definitions are out of a range          */
 538 /*-----------------------------------------------------------------*/
 539 bool
 540 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 541 {
 542   int i;
 543
 544   if (!defs)
 545     return TRUE;
 546
 547   for (i = 0; i < defs->size; i++)
 548     {
 549       iCode *ic;
 550
 551       if (bitVectBitValue (defs, i) &&
 552           (ic = hTabItemWithKey (iCodehTab, i)) &&
 553           (ic->seq >= fseq && ic->seq <= toseq))
 554
 555         return FALSE;
 556
 557     }
 558
 559   return TRUE;
 560 }
 561
 562 /*-----------------------------------------------------------------*/
 563 /* notUsedInBlock - not used in this block                         */
 564 /*-----------------------------------------------------------------*/
 565 int
 566 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 567 {
 568   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 569           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 570           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 571 }
 572
 573 /*-----------------------------------------------------------------*/
 574 /* adjustIChain - correct the sch and ech pointers                 */
 575 /*-----------------------------------------------------------------*/
 576 void
 577 adjustIChain (eBBlock ** ebbs, int count)
 578 {
 579   int i;
 580
 581   for (i = 0; i < count; i++)
 582     {
 583       iCode *ic;
 584
 585       if (ebbs[i]->noPath)
 586         continue;
 587
 588       ic = ebbs[i]->sch;
 589       while (ic->prev)
 590         ic = ic->prev;
 591       ebbs[i]->sch = ic;
 592
 593       ic = ebbs[i]->ech;
 594       while (ic->next)
 595         ic = ic->next;
 596       ebbs[i]->ech = ic;
 597     }
 598 }
 599
 600 /*-----------------------------------------------------------------*/
 601 /* computeLiveRanges - computes the live ranges for variables      */
 602 /*-----------------------------------------------------------------*/
 603 void
 604 computeLiveRanges (eBBlock ** ebbs, int count)
 605 {
 606   /* first look through all blocks and adjust the
 607      sch and ech pointers */
 608   adjustIChain (ebbs, count);
 609
 610   /* sequence the code the live ranges are computed
 611      in terms of this sequence additionally the
 612      routine will also create a hashtable of instructions */
 613   iCodeSeq = 0;
 614   setToNull ((void *) &iCodehTab);
 615   iCodehTab = newHashTable (iCodeKey);
 616   setToNull ((void *) &iCodeSeqhTab);
 617   iCodeSeqhTab = newHashTable (iCodeKey);
 618   sequenceiCode (ebbs, count);
 619
 620   /* mark the ranges live for each point */
 621   setToNull ((void *) &liveRanges);
 622   rlivePoint (ebbs, count);
 623
 624   /* mark the from & to live ranges for variables used */
 625   markLiveRanges (ebbs, count);
 626
 627   /* compute which overlaps with what */
 628   computeClash(ebbs, count);
 629 }
 630