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