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 /* markVisited - will set the visited flag for the given Block     */
  60 /*-----------------------------------------------------------------*/
  61 DEFSETFUNC (markVisited)
  62 {
  63   eBBlock *ebp = item;
  64
  65   if (ebp->visited)
  66     return 0;
  67   ebp->visited = 1;
  68   applyToSet (ebp->succList, markVisited);
  69   return 0;
  70 }
  71
  72 /*-----------------------------------------------------------------*/
  73 /* isOpAlive - checks to see if the usage in this block is the     */
  74 /*             uses the same definitions as this one               */
  75 /*-----------------------------------------------------------------*/
  76 DEFSETFUNC (isOpAlive)
  77 {
  78   eBBlock *ebp = item;
  79   V_ARG (operand *, op);
  80   V_ARG (eBBlock *, orig);
  81   V_ARG (iCode *, ic);
  82
  83   if (ebp->visited)
  84     return 0;
  85
  86   ebp->visited = 1;
  87
  88   /* if we have reached the originating block */
  89   /* or this block has some definiton for it  */
  90   /* then check if it is used between start & */
  91   /* this point */
  92   if (ebp == orig ||
  93       bitVectBitsInCommon (OP_DEFS (op), ebp->defSet))
  94     if (usedBetweenPoints (op, ebp->sch, ic))
  95       return 1;
  96     else
  97       {
  98         applyToSet (ebp->succList, markVisited);
  99         return 0;
 100       }
 101   else
 102     /* choosing this more expensive one since
 103        killDeadCode will take away some definitions
 104        but there is not way right now to take away
 105        the usage information for the corresponding
 106        usages, this will lead to longer live ranges */
 107   if (usedInRemaining (op, ebp->sch))
 108     return 1;
 109
 110
 111   return (applyToSet (ebp->succList, isOpAlive, op, orig, ic));
 112 }
 113
 114 /*-----------------------------------------------------------------*/
 115 /* isLastUse - return TRUE if no usage of this operand after this  */
 116 /*-----------------------------------------------------------------*/
 117 int
 118 isLastUse (operand * op, eBBlock * ebp, iCode * ic,
 119            eBBlock ** ebbs, int count)
 120 {
 121   int i;
 122
 123   /* if this is used in the remaining */
 124   if (usedInRemaining (op, ic))
 125     return 0;
 126
 127   /* if not then check any of the following blocks use it */
 128   for (i = 0; i < count; i++)
 129     {
 130       if (ebbs[i]->fSeq <= ebp->fSeq)
 131         continue;
 132       if (usedInRemaining (op, ebbs[i]->sch))
 133         return 0;
 134     }
 135
 136   /* this is the last use */
 137   return 1;
 138 }
 139
 140 /*-----------------------------------------------------------------*/
 141 /* unionDefsUsed - unions the defsUsed in a block                  */
 142 /*-----------------------------------------------------------------*/
 143 DEFSETFUNC (unionDefsUsed)
 144 {
 145   eBBlock *ebp = item;
 146   V_ARG (bitVect **, bvp);
 147
 148   if (ebp->visited)
 149     return 0;
 150
 151   ebp->visited = 1;
 152
 153   *bvp = bitVectUnion (*bvp, ebp->usesDefs);
 154   applyToSet (ebp->succList, unionDefsUsed, bvp);
 155   return 0;
 156 }
 157
 158 /*-----------------------------------------------------------------*/
 159 /* setFromRange - sets the from range of a given operand           */
 160 /*-----------------------------------------------------------------*/
 161 void
 162 setFromRange (operand * op, int from)
 163 {
 164   /* only for compiler defined temporaries */
 165   if (!IS_ITEMP (op))
 166     return;
 167
 168   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 169
 170   if (op->isaddr)
 171     OP_SYMBOL (op)->isptr = 1;
 172
 173   if (!OP_LIVEFROM (op) ||
 174       OP_LIVEFROM (op) > from)
 175     OP_LIVEFROM (op) = from;
 176 }
 177
 178 /*-----------------------------------------------------------------*/
 179 /* setToRange - set the range to for an operand                    */
 180 /*-----------------------------------------------------------------*/
 181 void
 182 setToRange (operand * op, int to, bool check)
 183 {
 184   /* only for compiler defined temps */
 185   if (!IS_ITEMP (op))
 186     return;
 187
 188   OP_SYMBOL (op)->key = op->key;
 189   hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
 190
 191   if (op->isaddr)
 192     OP_SYMBOL (op)->isptr = 1;
 193
 194   if (check)
 195     if (!OP_LIVETO (op))
 196       OP_LIVETO (op) = to;
 197     else;
 198   else
 199     OP_LIVETO (op) = to;
 200 }
 201
 202 /*-----------------------------------------------------------------*/
 203 /* firstDeOf - finds the first definition in seq for op            */
 204 /*-----------------------------------------------------------------*/
 205 static iCode *
 206 firstDefOf (operand * op)
 207 {
 208   int i;
 209   iCode *ric = NULL, *lic = NULL;
 210   int fSeq = INT_MAX;
 211
 212   if (!OP_DEFS (op))
 213     return NULL;
 214
 215   for (i = 0; i < OP_DEFS (op)->size; i++)
 216     {
 217       if (bitVectBitValue (OP_DEFS (op), i) &&
 218           (lic = hTabItemWithKey (iCodehTab, i)) &&
 219           lic->seq < fSeq)
 220         {
 221
 222           fSeq = lic->seq;
 223           ric = lic;
 224         }
 225     }
 226   return ric;
 227 }
 228 /*-----------------------------------------------------------------*/
 229 /* useDefLoopCheck - check for uses before init inside loops       */
 230 /*-----------------------------------------------------------------*/
 231 static void
 232 useDefLoopCheck (operand * op, iCode * ic)
 233 {
 234   /* this is for situations like the following
 235      int a,b;
 236
 237      while (...) {
 238      a = ... ;
 239      ...
 240      _some_usage_of_b_;
 241      ...
 242      b = ... ;
 243      }
 244      in this case the definition of 'b' will flow to the usages
 245      but register allocator cannot handle these situations.so
 246      will mark as spilt */
 247
 248   int i = 0, fdSeq;
 249   int er = 0;
 250   iCode *tic;
 251
 252   /* get the first definition */
 253   if (!(tic = firstDefOf (op)))
 254     return;
 255
 256   fdSeq = tic->seq;
 257   /* now go thru the usages & make sure they follow
 258      the first definition */
 259   for (i = 0; i <= OP_USES (op)->size; i++)
 260     {
 261       if (bitVectBitValue (OP_USES (op), i) &&
 262           (tic = hTabItemWithKey (iCodehTab, i)) &&
 263           tic->seq < fdSeq)
 264         {
 265           er = 1;
 266           break;
 267         }
 268     }
 269
 270   /* found a usage without definition */
 271   if (er)
 272     {
 273       if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
 274         {
 275
 276           werror (W_LOCAL_NOINIT,
 277                   SPIL_LOC (op)->name,
 278                   ic->filename, ic->lineno);
 279         }
 280       else
 281         {
 282
 283           werror (W_LOCAL_NOINIT,
 284                   OP_SYMBOL (op)->name,
 285                   ic->filename, ic->lineno);
 286         }
 287 #if 0 // this will create a segfault: bug #498971
 288       OP_SYMBOL (op)->isspilt = 1;
 289 #endif
 290     }
 291 }
 292
 293
 294 /*-----------------------------------------------------------------*/
 295 /* operandLUse - check and set the last use for a given operand    */
 296 /*-----------------------------------------------------------------*/
 297 operand *
 298 operandLUse (operand * op, eBBlock ** ebbs,
 299              int count, iCode * ic, eBBlock * ebp)
 300 {
 301   setFromRange (op, ic->seq);
 302   if (ic->depth)
 303     OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
 304   else
 305     OP_SYMBOL (op)->used += 1;
 306
 307   if (isLastUse (op, ebp, ic->next, ebbs, count) ||
 308       (OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
 309     {
 310       int torange = ic->seq;
 311
 312       /* if this is a SEND then the toRange should be extended
 313          to the call */
 314       if (ic->op == SEND)
 315         {
 316           iCode *lic ;
 317           for (lic = ic->next ; lic ; lic = lic->next)
 318             {
 319               if (lic->op == CALL || lic->op == PCALL)
 320                 break;
 321             }
 322           /* found it : mark */
 323           if (lic)
 324             torange = lic->prev->seq;
 325         }
 326       /* if this is the last use then if this block belongs
 327          to a  loop &  some definition  comes into the loop
 328          then extend the live range to  the end of the loop */
 329       if (ebp->partOfLoop)
 330         {
 331           region *aloop;
 332
 333           aloop = setFirstItem (ebp->partOfLoop);
 334           for (; aloop; aloop = setNextItem (ebp->partOfLoop))
 335             {
 336               if (hasIncomingDefs (aloop, op))
 337                 torange = findLoopEndSeq (aloop);
 338             }
 339         }
 340
 341       op = operandFromOperand (op);
 342       setToRange (op, torange, FALSE);
 343     }
 344   ic->uses = bitVectSetBit (ic->uses, op->key);
 345
 346   if (!OP_SYMBOL (op)->udChked)
 347     {
 348       sym_link *type = operandType (op);
 349       sym_link *etype = getSpec (type);
 350
 351       OP_SYMBOL (op)->udChked = 1;
 352       /* good place to check if unintialised */
 353       if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
 354           OP_SYMBOL (op)->islocal &&
 355           !IS_AGGREGATE (type) &&
 356           !IS_FUNC (type) &&
 357           ic->op != ADDRESS_OF &&
 358           !IS_STATIC (etype))
 359         {
 360
 361           if (bitVectIsZero (op->usesDefs) && OP_SYMBOL(op)->ival==NULL)
 362             {
 363               OP_SYMBOL (op)->isspilt = 1;
 364
 365               if (OP_SYMBOL (op)->isreqv &&
 366                   !OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
 367                 {
 368
 369                   werror (W_LOCAL_NOINIT,
 370                           SPIL_LOC (op)->name,
 371                           ic->filename, ic->lineno);
 372                 }
 373               else
 374                 {
 375
 376                   werror (W_LOCAL_NOINIT,
 377                           OP_SYMBOL (op)->name,
 378                           ic->filename, ic->lineno);
 379                 }
 380             }
 381           else
 382             {
 383               if (ebp->depth && op->usesDefs &&
 384                   !OP_SYMBOL (op)->_isparm)
 385                 {
 386                   /* check non-inits inside loops */
 387                   useDefLoopCheck (op, ic);
 388                 }
 389             }
 390         }
 391     }
 392   return op;
 393 }
 394
 395 /*-----------------------------------------------------------------*/
 396 /* killAllAlive - mark all the definitions living with this seq    */
 397 /*-----------------------------------------------------------------*/
 398 void
 399 killAllAlive (int seq)
 400 {
 401   symbol *sym;
 402   int k;
 403
 404   for (sym = hTabFirstItem (liveRanges, &k); sym;
 405        sym = hTabNextItem (liveRanges, &k))
 406     if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
 407       sym->liveTo = seq;
 408 }
 409 /*-----------------------------------------------------------------*/
 410 /* defUsedAfterLoop - all definitions & usages before sequence num */
 411 /*-----------------------------------------------------------------*/
 412 bool
 413 defUsedAfterLoop (operand * op, int seq)
 414 {
 415   int i;
 416   iCode *ic;
 417
 418   /* check for the usages first */
 419   if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
 420     {
 421       for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
 422         {
 423
 424           if (bitVectBitValue (OP_SYMBOL (op)->uses, i) &&      /* usage found */
 425               (ic = hTabItemWithKey (iCodehTab, i)) &&  /*    ""       */
 426               ic->seq > seq)    /* & is after the seq */
 427             return TRUE;
 428         }
 429     }
 430
 431   return FALSE;
 432 }
 433
 434 /*-----------------------------------------------------------------*/
 435 /* markLiveRanges - for each operand mark the liveFrom & liveTo    */
 436 /*-----------------------------------------------------------------*/
 437 void
 438 markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
 439 {
 440   iCode *ic;
 441   bitVect *defsUsed = NULL;
 442   bitVect *defsNotUsed = NULL;
 443   int i;
 444
 445   /* for all the instructions */
 446   for (ic = ebp->sch; ic; ic = ic->next)
 447     {
 448       if (ic->op == CALL || ic->op == PCALL)
 449         {
 450           setFromRange (IC_RESULT (ic), ic->seq);
 451           /* if the result has no usage then
 452              mark this as the end of its life too
 453              and take it away from the defs for the block */
 454           if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
 455             {
 456               setToRange (IC_RESULT (ic), ic->seq, FALSE);
 457               bitVectUnSetBit (ebp->defSet, ic->key);
 458             }
 459         }
 460
 461       if (SKIP_IC2 (ic))
 462         continue;
 463
 464       /* take care of the special icodes first */
 465       if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
 466         {
 467           operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
 468           continue;
 469         }
 470
 471       if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
 472         {
 473           operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
 474           continue;
 475         }
 476
 477       if (IS_SYMOP (IC_LEFT (ic)))
 478         operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
 479
 480       if (IS_SYMOP (IC_RIGHT (ic)))
 481         operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
 482
 483       if (POINTER_SET (ic))
 484         operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
 485       else if (IC_RESULT (ic))
 486         ic->defKey = IC_RESULT (ic)->key;
 487     }
 488
 489
 490   /* for all the definitions in the block */
 491   /* compute and set the live from        */
 492   if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
 493     {
 494       for (i = 0; i < ebp->ldefs->size; i++)
 495         {
 496           iCode *dic;
 497
 498           if (bitVectBitValue (ebp->ldefs, i) &&
 499               (dic = hTabItemWithKey (iCodehTab, i)))
 500             {
 501
 502               /* if the definition has a from & it is greater */
 503               /* than the defininng iCode->seq then change it */
 504               setFromRange (IC_RESULT (dic), dic->seq);
 505             }
 506         }
 507     }
 508
 509   /* special case for lastBlock in a loop: here we
 510      mark the end of all the induction variables for the
 511      loop */
 512   if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
 513     {
 514       for (i = 0; i <= ebp->linds->size; i++)
 515         {
 516           iCode *dic;
 517
 518           if (bitVectBitValue (ebp->linds, i) &&
 519               (dic = hTabItemWithKey (iCodehTab, i)))
 520             {
 521
 522               /* if this is a register equvalent make sure
 523                  it is not defined or used anywhere after the loop */
 524               if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
 525                   defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
 526                 continue;
 527
 528               setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
 529             }
 530         }
 531     }
 532
 533   /* for defnitions coming into the block if they */
 534   /* not used by itself & any of its successors   */
 535   /* they are dead */
 536   /* first union the definitions used in all successors
 537      and itself */
 538   for (i = 0; i < count; ebbs[i++]->visited = 0);
 539   applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
 540   defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
 541
 542   /* now subract the result of these unions from */
 543   /* the incoming definitions this will give the */
 544   /* definitions that are never used in the future */
 545   defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
 546                                defsUsed);
 547
 548   /* mark the end of the defintions */
 549   if (!bitVectIsZero (defsNotUsed) && ebp->sch)
 550     {
 551       for (i = 0; i < defsNotUsed->size; i++)
 552         {
 553           iCode *dic;
 554
 555           if (bitVectBitValue (defsNotUsed, i) &&
 556               (dic = hTabItemWithKey (iCodehTab, i)))
 557             {
 558               setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
 559             }
 560         }
 561     }
 562
 563
 564   /* if we reach a lock with noPath to it then kill all
 565      the live ranges alive at this point */
 566 /*     if (ebp->noPath || ebp->entryLabel == returnLabel) */
 567   if (ebp->entryLabel == returnLabel)
 568     killAllAlive (ebp->fSeq);
 569 }
 570
 571 /*-----------------------------------------------------------------*/
 572 /* rlivePoint - for each point compute the ranges that are alive   */
 573 /*-----------------------------------------------------------------*/
 574 void
 575 rlivePoint (eBBlock ** ebbs, int count)
 576 {
 577     int i;
 578
 579     /* for all blocks do */
 580     for (i = 0; i < count; i++) {
 581         iCode *ic;
 582
 583         /* for all instruction in the block do */
 584         for (ic = ebbs[i]->sch; ic; ic = ic->next) {
 585             symbol *lrange;
 586             int k;
 587
 588             ic->rlive = newBitVect (operandKey);
 589             /* for all symbols in the liverange table */
 590             for (lrange = hTabFirstItem (liveRanges, &k); lrange;
 591                  lrange = hTabNextItem (liveRanges, &k)) {
 592
 593                 /* if it is live then add the lrange to ic->rlive */
 594                 if (lrange->liveFrom <= ic->seq &&
 595                     lrange->liveTo >= ic->seq) {
 596                     lrange->isLiveFcall |= ((lrange->liveFrom < ic->seq) &&
 597                                             (ic->op == CALL || ic->op == PCALL || ic->op == SEND));
 598                     if (ic->op == CALL && lrange->liveFrom == ic->seq) continue;
 599                     ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
 600                 }
 601             }
 602 #if 0
 603             /* overlapping live ranges should be eliminated */
 604             if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
 605                 if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic))   && /* left & right share the same spil location */
 606                     OP_SYMBOL(IC_RESULT(ic))->isreqv                    && /* left of assign is a register requivalent */
 607                     !OP_SYMBOL(IC_RIGHT(ic))->isreqv                    && /* right side is not */
 608                     OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key           && /* right side live beyond this point */
 609                     bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 )        {  /* left has multiple definitions */
 610                     SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
 611                 }
 612             }
 613 #endif
 614         }
 615     }
 616 }
 617
 618 /*-----------------------------------------------------------------*/
 619 /* computeClash - find out which live ranges collide with others   */
 620 /*-----------------------------------------------------------------*/
 621 static void computeClash ()
 622 {
 623     hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
 624     void *item;
 625     symbol *outer, *inner;
 626     int key, key1;
 627
 628     /* have to make a copy of the liveRanges hashTable :: UGHH .*/
 629     for (item = hTabFirstItem(liveRanges,&key); item ;
 630          item = hTabNextItem(liveRanges,&key)) {
 631         hTabAddItem(&lRangeCopy,key,item);
 632     }
 633
 634     /* outerloop : for each liverange do */
 635     for (outer = hTabFirstItem(liveRanges,&key); outer ;
 636          outer = hTabNextItem(liveRanges,&key)) {
 637
 638         /* if the liveFrom & To are the same then skip,
 639            could happen for unused return values from functions */
 640         if (outer->liveFrom == outer->liveTo) continue;
 641
 642         /* innerloop : for the inner loop we can start from the
 643            item after the outer loop */
 644         inner = hTabFirstItemWK (lRangeCopy,outer->key);
 645         inner = hTabNextItem (lRangeCopy,&key1 );
 646         for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
 647
 648             if (inner->liveFrom == inner->liveTo) continue;
 649             if (inner->liveTo < outer->liveFrom)  continue;
 650             if (inner->liveFrom > outer->liveTo)  continue;
 651
 652             /* if one of them are being defined where the other
 653                one end , then no overlap (i.e. they can goto same registers */
 654             if (inner->liveFrom == outer->liveTo ||
 655                 outer->liveFrom == inner->liveTo) continue;
 656
 657             /* so they overlap : set both their clashes */
 658             inner->clashes = bitVectSetBit(inner->clashes,outer->key);
 659             outer->clashes = bitVectSetBit(outer->clashes,inner->key);
 660
 661             /* check if they share the same spillocation */
 662             if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
 663                 SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
 664                 if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
 665                 else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
 666                 else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
 667                 else SYM_SPIL_LOC(inner)=NULL;
 668             }
 669
 670         }
 671     }
 672 }
 673
 674 /*-----------------------------------------------------------------*/
 675 /* allDefsOutOfRange - all definitions are out of a range          */
 676 /*-----------------------------------------------------------------*/
 677 bool
 678 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
 679 {
 680   int i;
 681
 682   if (!defs)
 683     return TRUE;
 684
 685   for (i = 0; i < defs->size; i++)
 686     {
 687       iCode *ic;
 688
 689       if (bitVectBitValue (defs, i) &&
 690           (ic = hTabItemWithKey (iCodehTab, i)) &&
 691           (ic->seq >= fseq && ic->seq <= toseq))
 692
 693         return FALSE;
 694
 695     }
 696
 697   return TRUE;
 698 }
 699
 700 /*-----------------------------------------------------------------*/
 701 /* notUsedInBlock - not used in this block                         */
 702 /*-----------------------------------------------------------------*/
 703 int
 704 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
 705 {
 706   return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
 707           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
 708           allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
 709 }
 710
 711
 712 /*-----------------------------------------------------------------*/
 713 /* computeLiveRanges - computes the live ranges for variables      */
 714 /*-----------------------------------------------------------------*/
 715 void
 716 computeLiveRanges (eBBlock ** ebbs, int count)
 717 {
 718   int i = 0;
 719   /* sequence the code the live ranges are computed
 720      in terms of this sequence additionally the
 721      routine will also create a hashtable of instructions */
 722   iCodeSeq = 0;
 723   setToNull ((void **) &iCodehTab);
 724   iCodehTab = newHashTable (iCodeKey);
 725   setToNull ((void **) &iCodeSeqhTab);
 726   iCodeSeqhTab = newHashTable (iCodeKey);
 727   sequenceiCode (ebbs, count);
 728
 729   /* add blocks between loop blocks as part of that loop */
 730   addLoopBlocks (ebbs, count);
 731
 732   /* call routine to mark the from & to live ranges for
 733      variables used */
 734   setToNull ((void **) &liveRanges);
 735   for (i = 0; i < count; i++)
 736     markLiveRanges (ebbs[i], ebbs, count);
 737
 738   /* mark the ranges live for each point */
 739   rlivePoint (ebbs, count);
 740
 741   /* compute which overlaps with what */
 742   computeClash();
 743 }
 744