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