git.gag.com Git - fw/sdcc/blob - src/mcs51/ralloc.c

   1 /*------------------------------------------------------------------------
   2
   3   SDCCralloc.c - source file for register allocation. (8051) specific
   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 "ralloc.h"
  28 #include "gen.h"
  29
  30 /*-----------------------------------------------------------------*/
  31 /* At this point we start getting processor specific although      */
  32 /* some routines are non-processor specific & can be reused when   */
  33 /* targetting other processors. The decision for this will have    */
  34 /* to be made on a routine by routine basis                        */
  35 /* routines used to pack registers are most definitely not reusable*/
  36 /* since the pack the registers depending strictly on the MCU      */
  37 /*-----------------------------------------------------------------*/
  38
  39 extern void gen51Code(iCode *);
  40
  41 /* Global data */
  42 static struct {
  43     bitVect *spiltSet;
  44     set *stackSpil;
  45     bitVect *regAssigned;
  46     short blockSpil;
  47     int slocNum;
  48     bitVect *funcrUsed; /* registers used in a function */
  49     int stackExtend;
  50     int dataExtend;
  51 } _G;
  52
  53 /* Shared with gen.c */
  54 int mcs51_ptrRegReq; /* one byte pointer register required */
  55
  56 /* 8051 registers */
  57 regs regs8051[] =
  58 {
  59
  60     { REG_GPR  ,R2_IDX , REG_GPR , "r2",  "ar2", "0", 2, 1 },
  61     { REG_GPR  ,R3_IDX , REG_GPR , "r3",  "ar3", "0", 3, 1 },
  62     { REG_GPR  ,R4_IDX , REG_GPR , "r4",  "ar4", "0", 4, 1 },
  63     { REG_GPR  ,R5_IDX , REG_GPR , "r5",  "ar5", "0", 5, 1 },
  64     { REG_GPR  ,R6_IDX , REG_GPR , "r6",  "ar6", "0", 6, 1 },
  65     { REG_GPR  ,R7_IDX , REG_GPR , "r7",  "ar7", "0", 7, 1 },
  66     { REG_PTR  ,R0_IDX , REG_PTR , "r0" , "ar0", "0", 0, 1 },
  67     { REG_PTR  ,R1_IDX , REG_PTR , "r1" , "ar1", "0", 1, 1 },
  68     { REG_GPR  ,X8_IDX , REG_GPR , "x8",  "x8" , "xreg", 0, 1 },
  69     { REG_GPR  ,X9_IDX , REG_GPR , "x9",  "x9" , "xreg", 1, 1 },
  70     { REG_GPR  ,X10_IDX,REG_GPR , "x10", "x10",  "xreg", 2, 1 },
  71     { REG_GPR  ,X11_IDX,REG_GPR , "x11", "x11",  "xreg", 3, 1 },
  72     { REG_GPR  ,X12_IDX,REG_GPR , "x12", "x12",  "xreg", 4, 1 },
  73     { REG_CND  ,CND_IDX,REG_CND , "C"  , "C"  ,  "xreg", 0, 1 },
  74 };
  75 int mcs51_nRegs = 13;
  76 static void spillThis (symbol *);
  77
  78 /*-----------------------------------------------------------------*/
  79 /* allocReg - allocates register of given type                     */
  80 /*-----------------------------------------------------------------*/
  81 static regs *allocReg (short type)
  82 {
  83     int i;
  84
  85     for ( i = 0 ; i < mcs51_nRegs ; i++ ) {
  86
  87         /* if type is given as 0 then any
  88            free register will do */
  89         if (!type &&
  90             regs8051[i].isFree ) {
  91             regs8051[i].isFree = 0;
  92             if (currFunc)
  93                 currFunc->regsUsed =
  94                     bitVectSetBit(currFunc->regsUsed,i);
  95             return &regs8051[i];
  96         }
  97         /* other wise look for specific type
  98            of register */
  99         if (regs8051[i].isFree &&
 100             regs8051[i].type == type) {
 101             regs8051[i].isFree = 0;
 102             if (currFunc)
 103                 currFunc->regsUsed =
 104                     bitVectSetBit(currFunc->regsUsed,i);
 105             return &regs8051[i];
 106         }
 107     }
 108     return NULL;
 109 }
 110
 111 /*-----------------------------------------------------------------*/
 112 /* mcs51_regWithIdx - returns pointer to register wit index number       */
 113 /*-----------------------------------------------------------------*/
 114 regs *mcs51_regWithIdx (int idx)
 115 {
 116     int i ;
 117
 118     for (i=0;i < mcs51_nRegs;i++)
 119         if (regs8051[i].rIdx == idx)
 120             return &regs8051[i];
 121
 122     werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
 123            "regWithIdx not found");
 124     exit(1);
 125 }
 126
 127 /*-----------------------------------------------------------------*/
 128 /* freeReg - frees a register                                      */
 129 /*-----------------------------------------------------------------*/
 130 static void freeReg (regs *reg)
 131 {
 132     reg->isFree = 1;
 133 }
 134
 135
 136 /*-----------------------------------------------------------------*/
 137 /* nFreeRegs - returns number of free registers                    */
 138 /*-----------------------------------------------------------------*/
 139 static int nFreeRegs (int type)
 140 {
 141     int i;
 142     int nfr=0;
 143
 144     for (i = 0 ; i < mcs51_nRegs; i++ )
 145         if (regs8051[i].isFree && regs8051[i].type == type)
 146             nfr++;
 147     return nfr;
 148 }
 149
 150 /*-----------------------------------------------------------------*/
 151 /* nfreeRegsType - free registers with type                         */
 152 /*-----------------------------------------------------------------*/
 153 static int nfreeRegsType (int type)
 154 {
 155     int nfr ;
 156     if (type == REG_PTR) {
 157         if ((nfr = nFreeRegs(type)) == 0)
 158             return nFreeRegs(REG_GPR);
 159     }
 160
 161     return nFreeRegs(type);
 162 }
 163
 164
 165 /*-----------------------------------------------------------------*/
 166 /* allDefsOutOfRange - all definitions are out of a range          */
 167 /*-----------------------------------------------------------------*/
 168 static bool allDefsOutOfRange (bitVect *defs,int fseq, int toseq)
 169 {
 170     int i ;
 171
 172     if (!defs)
 173         return TRUE ;
 174
 175     for ( i = 0 ;i < defs->size ; i++ ) {
 176         iCode *ic;
 177
 178         if (bitVectBitValue(defs,i)             &&
 179             (ic = hTabItemWithKey(iCodehTab,i)) &&
 180             ( ic->seq >= fseq  && ic->seq <= toseq))
 181
 182             return FALSE;
 183
 184     }
 185
 186     return TRUE;
 187 }
 188
 189 /*-----------------------------------------------------------------*/
 190 /* computeSpillable - given a point find the spillable live ranges */
 191 /*-----------------------------------------------------------------*/
 192 static bitVect *computeSpillable (iCode *ic)
 193 {
 194     bitVect *spillable ;
 195
 196     /* spillable live ranges are those that are live at this
 197        point . the following categories need to be subtracted
 198        from this set.
 199        a) - those that are already spilt
 200        b) - if being used by this one
 201        c) - defined by this one */
 202
 203     spillable = bitVectCopy(ic->rlive);
 204     spillable =
 205         bitVectCplAnd(spillable,_G.spiltSet); /* those already spilt */
 206     spillable =
 207         bitVectCplAnd(spillable,ic->uses); /* used in this one */
 208     bitVectUnSetBit(spillable,ic->defKey);
 209     spillable = bitVectIntersect(spillable,_G.regAssigned);
 210     return spillable;
 211
 212 }
 213
 214 /*-----------------------------------------------------------------*/
 215 /* noSpilLoc - return true if a variable has no spil location      */
 216 /*-----------------------------------------------------------------*/
 217 static int noSpilLoc (symbol *sym, eBBlock *ebp,iCode *ic)
 218 {
 219     return (sym->usl.spillLoc ? 0 : 1);
 220 }
 221
 222 /*-----------------------------------------------------------------*/
 223 /* hasSpilLoc - will return 1 if the symbol has spil location      */
 224 /*-----------------------------------------------------------------*/
 225 static int hasSpilLoc (symbol *sym, eBBlock *ebp, iCode *ic)
 226 {
 227     return (sym->usl.spillLoc ? 1 : 0);
 228 }
 229
 230 /*-----------------------------------------------------------------*/
 231 /* directSpilLoc - will return 1 if the splilocation is in direct  */
 232 /*-----------------------------------------------------------------*/
 233 static int directSpilLoc (symbol *sym, eBBlock *ebp, iCode *ic)
 234 {
 235     if ( sym->usl.spillLoc &&
 236          (IN_DIRSPACE(SPEC_OCLS(sym->usl.spillLoc->etype))))
 237         return 1;
 238     else
 239         return 0;
 240 }
 241
 242 /*-----------------------------------------------------------------*/
 243 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location*/
 244 /*                    but is not used as a pointer                 */
 245 /*-----------------------------------------------------------------*/
 246 static int hasSpilLocnoUptr (symbol *sym, eBBlock *ebp, iCode *ic)
 247 {
 248     return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
 249 }
 250
 251 /*-----------------------------------------------------------------*/
 252 /* rematable - will return 1 if the remat flag is set              */
 253 /*-----------------------------------------------------------------*/
 254 static int rematable (symbol *sym, eBBlock *ebp, iCode *ic)
 255 {
 256     return sym->remat;
 257 }
 258
 259 /*-----------------------------------------------------------------*/
 260 /* notUsedInBlock - not used in this block                         */
 261 /*-----------------------------------------------------------------*/
 262 static int notUsedInBlock (symbol *sym, eBBlock *ebp, iCode *ic)
 263 {
 264     return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs) &&
 265             allDefsOutOfRange (sym->defs,ebp->fSeq,ebp->lSeq));
 266 /*     return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs)); */
 267 }
 268
 269 /*-----------------------------------------------------------------*/
 270 /* notUsedInRemaining - not used or defined in remain of the block */
 271 /*-----------------------------------------------------------------*/
 272 static int notUsedInRemaining (symbol *sym, eBBlock *ebp, iCode *ic)
 273 {
 274     return ((usedInRemaining (operandFromSymbol(sym),ic) ? 0 : 1) &&
 275             allDefsOutOfRange (sym->defs,ebp->fSeq,ebp->lSeq));
 276 }
 277
 278 /*-----------------------------------------------------------------*/
 279 /* allLRs - return true for all                                    */
 280 /*-----------------------------------------------------------------*/
 281 static int allLRs (symbol *sym, eBBlock *ebp, iCode *ic)
 282 {
 283     return 1;
 284 }
 285
 286 /*-----------------------------------------------------------------*/
 287 /* liveRangesWith - applies function to a given set of live range  */
 288 /*-----------------------------------------------------------------*/
 289 static set *liveRangesWith (bitVect *lrs, int (func)(symbol *,eBBlock *, iCode *),
 290                      eBBlock *ebp, iCode *ic)
 291 {
 292     set *rset = NULL;
 293     int i;
 294
 295     if (!lrs || !lrs->size)
 296         return NULL;
 297
 298     for ( i = 1 ; i < lrs->size ; i++ ) {
 299         symbol *sym;
 300         if (!bitVectBitValue(lrs,i))
 301             continue ;
 302
 303         /* if we don't find it in the live range
 304            hash table we are in serious trouble */
 305         if (!(sym = hTabItemWithKey(liveRanges,i))) {
 306             werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
 307                    "liveRangesWith could not find liveRange");
 308             exit(1);
 309         }
 310
 311         if (func(sym,ebp,ic) && bitVectBitValue(_G.regAssigned,sym->key))
 312             addSetHead(&rset,sym);
 313     }
 314
 315     return rset;
 316 }
 317
 318
 319 /*-----------------------------------------------------------------*/
 320 /* leastUsedLR - given a set determines which is the least used    */
 321 /*-----------------------------------------------------------------*/
 322 static symbol *leastUsedLR (set *sset)
 323 {
 324     symbol *sym = NULL, *lsym = NULL ;
 325
 326     sym = lsym = setFirstItem(sset);
 327
 328     if (!lsym)
 329         return NULL;
 330
 331     for (; lsym; lsym = setNextItem(sset)) {
 332
 333         /* if usage is the same then prefer
 334            the spill the smaller of the two */
 335         if ( lsym->used == sym->used )
 336             if (getSize(lsym->type) < getSize(sym->type))
 337                 sym = lsym;
 338
 339         /* if less usage */
 340         if (lsym->used < sym->used )
 341             sym = lsym;
 342
 343    }
 344
 345     setToNull((void **)&sset);
 346     sym->blockSpil = 0;
 347     return sym;
 348 }
 349
 350 /*-----------------------------------------------------------------*/
 351 /* noOverLap - will iterate through the list looking for over lap  */
 352 /*-----------------------------------------------------------------*/
 353 static int noOverLap (set *itmpStack, symbol *fsym)
 354 {
 355     symbol *sym;
 356
 357
 358     for (sym = setFirstItem(itmpStack); sym;
 359          sym = setNextItem(itmpStack)) {
 360         if (sym->liveTo > fsym->liveFrom )
 361             return 0;
 362
 363     }
 364
 365     return 1;
 366 }
 367
 368 /*-----------------------------------------------------------------*/
 369 /* isFree - will return 1 if the a free spil location is found     */
 370 /*-----------------------------------------------------------------*/
 371 static DEFSETFUNC(isFree)
 372 {
 373     symbol *sym = item;
 374     V_ARG(symbol **,sloc);
 375     V_ARG(symbol *,fsym);
 376
 377     /* if already found */
 378     if (*sloc)
 379         return 0;
 380
 381     /* if it is free && and the itmp assigned to
 382        this does not have any overlapping live ranges
 383        with the one currently being assigned and
 384        the size can be accomodated  */
 385     if (sym->isFree                        &&
 386         noOverLap(sym->usl.itmpStack,fsym) &&
 387         getSize(sym->type) >= getSize(fsym->type)) {
 388         *sloc = sym;
 389         return 1;
 390     }
 391
 392     return 0;
 393 }
 394
 395 /*-----------------------------------------------------------------*/
 396 /* spillLRWithPtrReg :- will spil those live ranges which use PTR  */
 397 /*-----------------------------------------------------------------*/
 398 static void spillLRWithPtrReg (symbol *forSym)
 399 {
 400     symbol *lrsym;
 401     regs *r0,*r1;
 402     int k;
 403
 404     if (!_G.regAssigned ||
 405         bitVectIsZero(_G.regAssigned))
 406         return;
 407
 408     r0 = mcs51_regWithIdx(R0_IDX);
 409     r1 = mcs51_regWithIdx(R1_IDX);
 410
 411     /* for all live ranges */
 412     for (lrsym = hTabFirstItem(liveRanges,&k) ; lrsym ;
 413          lrsym = hTabNextItem(liveRanges,&k) ) {
 414         int j;
 415
 416         /* if no registers assigned to it or
 417            spilt */
 418         /* if it does not overlap with this then
 419            not need to spill it */
 420
 421         if (lrsym->isspilt || !lrsym->nRegs ||
 422             (lrsym->liveTo < forSym->liveFrom))
 423             continue ;
 424
 425         /* go thru the registers : if it is either
 426            r0 or r1 then spil it */
 427         for (j = 0 ; j < lrsym->nRegs ; j++ )
 428             if (lrsym->regs[j] == r0 ||
 429                 lrsym->regs[j] == r1 ) {
 430                 spillThis (lrsym);
 431                 break;
 432             }
 433     }
 434
 435 }
 436
 437 /*-----------------------------------------------------------------*/
 438 /* createStackSpil - create a location on the stack to spil        */
 439 /*-----------------------------------------------------------------*/
 440 static symbol *createStackSpil (symbol *sym)
 441 {
 442     symbol *sloc= NULL;
 443     int useXstack, model, noOverlay;
 444
 445     char slocBuffer[30];
 446
 447     /* first go try and find a free one that is already
 448        existing on the stack */
 449     if (applyToSet(_G.stackSpil,isFree,&sloc, sym)) {
 450         /* found a free one : just update & return */
 451         sym->usl.spillLoc = sloc;
 452         sym->stackSpil= 1;
 453         sloc->isFree = 0;
 454         addSetHead(&sloc->usl.itmpStack,sym);
 455         return sym;
 456     }
 457
 458     /* could not then have to create one , this is the hard part
 459        we need to allocate this on the stack : this is really a
 460        hack!! but cannot think of anything better at this time */
 461
 462     if (sprintf(slocBuffer,"sloc%d",_G.slocNum++) >= sizeof(slocBuffer))
 463     {
 464         fprintf(stderr, "***Internal error: slocBuffer overflowed: %s:%d\n",
 465                 __FILE__, __LINE__);
 466         exit(1);
 467     }
 468
 469     sloc = newiTemp(slocBuffer);
 470
 471     /* set the type to the spilling symbol */
 472     sloc->type = copyLinkChain(sym->type);
 473     sloc->etype = getSpec(sloc->type);
 474     SPEC_SCLS(sloc->etype) = S_DATA ;
 475     SPEC_EXTR(sloc->etype) = 0;
 476
 477     /* we don't allow it to be allocated`
 478        onto the external stack since : so we
 479        temporarily turn it off ; we also
 480        turn off memory model to prevent
 481        the spil from going to the external storage
 482     */
 483
 484     useXstack = options.useXstack;
 485     model = options.model;
 486 /*     noOverlay = options.noOverlay; */
 487 /*     options.noOverlay = 1; */
 488     options.model = options.useXstack = 0;
 489
 490     allocLocal(sloc);
 491
 492     options.useXstack = useXstack;
 493     options.model     = model;
 494 /*     options.noOverlay = noOverlay; */
 495     sloc->isref = 1; /* to prevent compiler warning */
 496
 497     /* if it is on the stack then update the stack */
 498     if (IN_STACK(sloc->etype)) {
 499         currFunc->stack += getSize(sloc->type);
 500         _G.stackExtend += getSize(sloc->type);
 501     } else
 502         _G.dataExtend += getSize(sloc->type);
 503
 504     /* add it to the _G.stackSpil set */
 505     addSetHead(&_G.stackSpil,sloc);
 506     sym->usl.spillLoc = sloc;
 507     sym->stackSpil = 1;
 508
 509     /* add it to the set of itempStack set
 510        of the spill location */
 511     addSetHead(&sloc->usl.itmpStack,sym);
 512     return sym;
 513 }
 514
 515 /*-----------------------------------------------------------------*/
 516 /* isSpiltOnStack - returns true if the spil location is on stack  */
 517 /*-----------------------------------------------------------------*/
 518 static bool isSpiltOnStack (symbol *sym)
 519 {
 520     link *etype;
 521
 522     if (!sym)
 523         return FALSE ;
 524
 525     if (!sym->isspilt)
 526         return FALSE ;
 527
 528 /*     if (sym->_G.stackSpil) */
 529 /*      return TRUE; */
 530
 531     if (!sym->usl.spillLoc)
 532         return FALSE;
 533
 534     etype = getSpec(sym->usl.spillLoc->type);
 535     if (IN_STACK(etype))
 536         return TRUE;
 537
 538     return FALSE ;
 539 }
 540
 541 /*-----------------------------------------------------------------*/
 542 /* spillThis - spils a specific operand                            */
 543 /*-----------------------------------------------------------------*/
 544 static void spillThis (symbol *sym)
 545 {
 546     int i;
 547     /* if this is rematerializable or has a spillLocation
 548        we are okay, else we need to create a spillLocation
 549        for it */
 550     if (!(sym->remat || sym->usl.spillLoc))
 551         createStackSpil (sym);
 552
 553
 554     /* mark it has spilt & put it in the spilt set */
 555     sym->isspilt = 1;
 556     _G.spiltSet = bitVectSetBit(_G.spiltSet,sym->key);
 557
 558     bitVectUnSetBit(_G.regAssigned,sym->key);
 559
 560     for (i = 0 ; i < sym->nRegs ; i++)
 561
 562         if (sym->regs[i]) {
 563             freeReg(sym->regs[i]);
 564             sym->regs[i] = NULL;
 565         }
 566
 567     /* if spilt on stack then free up r0 & r1
 568        if they could have been assigned to some
 569        LIVE ranges */
 570     if (!mcs51_ptrRegReq && isSpiltOnStack(sym)) {
 571         mcs51_ptrRegReq++ ;
 572         spillLRWithPtrReg(sym);
 573     }
 574
 575     if (sym->usl.spillLoc && !sym->remat)
 576         sym->usl.spillLoc->allocreq = 1;
 577     return;
 578 }
 579
 580 /*-----------------------------------------------------------------*/
 581 /* selectSpil - select a iTemp to spil : rather a simple procedure */
 582 /*-----------------------------------------------------------------*/
 583 static symbol *selectSpil (iCode *ic, eBBlock *ebp, symbol *forSym)
 584 {
 585     bitVect *lrcs= NULL ;
 586     set *selectS ;
 587     symbol *sym;
 588
 589     /* get the spillable live ranges */
 590     lrcs = computeSpillable (ic);
 591
 592     /* get all live ranges that are rematerizable */
 593     if ((selectS = liveRangesWith(lrcs,rematable,ebp,ic))) {
 594
 595         /* return the least used of these */
 596         return leastUsedLR(selectS);
 597     }
 598
 599     /* get live ranges with spillLocations in direct space */
 600     if ((selectS = liveRangesWith(lrcs,directSpilLoc,ebp,ic))) {
 601         sym = leastUsedLR(selectS);
 602         strcpy(sym->rname,(sym->usl.spillLoc->rname[0] ?
 603                            sym->usl.spillLoc->rname :
 604                            sym->usl.spillLoc->name));
 605         sym->spildir = 1;
 606         /* mark it as allocation required */
 607         sym->usl.spillLoc->allocreq = 1;
 608         return sym;
 609     }
 610
 611     /* if the symbol is local to the block then */
 612     if (forSym->liveTo < ebp->lSeq) {
 613
 614         /* check if there are any live ranges allocated
 615            to registers that are not used in this block */
 616         if (!_G.blockSpil && (selectS = liveRangesWith(lrcs,notUsedInBlock,ebp,ic))) {
 617             sym = leastUsedLR(selectS);
 618             /* if this is not rematerializable */
 619             if (!sym->remat) {
 620                 _G.blockSpil++;
 621                 sym->blockSpil = 1;
 622             }
 623             return sym;
 624         }
 625
 626         /* check if there are any live ranges that not
 627            used in the remainder of the block */
 628         if (!_G.blockSpil && (selectS = liveRangesWith(lrcs,notUsedInRemaining,ebp,ic))) {
 629             sym = leastUsedLR (selectS);
 630             if (!sym->remat) {
 631                 sym->remainSpil = 1;
 632                 _G.blockSpil++;
 633             }
 634             return sym;
 635         }
 636     }
 637
 638     /* find live ranges with spillocation && not used as pointers */
 639     if ((selectS = liveRangesWith(lrcs,hasSpilLocnoUptr,ebp,ic))) {
 640
 641         sym =  leastUsedLR(selectS);
 642         /* mark this as allocation required */
 643         sym->usl.spillLoc->allocreq = 1;
 644         return sym;
 645     }
 646
 647     /* find live ranges with spillocation */
 648     if ((selectS = liveRangesWith(lrcs,hasSpilLoc,ebp,ic))) {
 649
 650         sym = leastUsedLR(selectS);
 651         sym->usl.spillLoc->allocreq = 1;
 652         return sym;
 653     }
 654
 655     /* couldn't find then we need to create a spil
 656        location on the stack , for which one? the least
 657        used ofcourse */
 658     if ((selectS = liveRangesWith(lrcs,noSpilLoc,ebp,ic))) {
 659
 660         /* return a created spil location */
 661         sym = createStackSpil(leastUsedLR(selectS));
 662         sym->usl.spillLoc->allocreq = 1;
 663         return sym;
 664     }
 665
 666     /* this is an extreme situation we will spill
 667        this one : happens very rarely but it does happen */
 668     spillThis ( forSym );
 669     return forSym ;
 670
 671 }
 672
 673 /*-----------------------------------------------------------------*/
 674 /* spilSomething - spil some variable & mark registers as free     */
 675 /*-----------------------------------------------------------------*/
 676 static bool spilSomething (iCode *ic, eBBlock *ebp, symbol *forSym)
 677 {
 678     symbol *ssym;
 679     int i ;
 680
 681     /* get something we can spil */
 682     ssym = selectSpil(ic,ebp,forSym);
 683
 684     /* mark it as spilt */
 685     ssym->isspilt = 1;
 686     _G.spiltSet = bitVectSetBit(_G.spiltSet,ssym->key);
 687
 688     /* mark it as not register assigned &
 689        take it away from the set */
 690     bitVectUnSetBit(_G.regAssigned,ssym->key);
 691
 692     /* mark the registers as free */
 693     for (i = 0 ; i < ssym->nRegs ;i++ )
 694         if (ssym->regs[i])
 695             freeReg(ssym->regs[i]);
 696
 697     /* if spilt on stack then free up r0 & r1
 698        if they could have been assigned to as gprs */
 699     if (!mcs51_ptrRegReq && isSpiltOnStack(ssym) ) {
 700         mcs51_ptrRegReq++ ;
 701         spillLRWithPtrReg(ssym);
 702     }
 703
 704     /* if this was a block level spil then insert push & pop
 705        at the start & end of block respectively */
 706     if (ssym->blockSpil) {
 707         iCode *nic = newiCode(IPUSH,operandFromSymbol(ssym),NULL);
 708         /* add push to the start of the block */
 709         addiCodeToeBBlock(ebp,nic,( ebp->sch->op == LABEL ?
 710                                     ebp->sch->next : ebp->sch));
 711         nic = newiCode(IPOP,operandFromSymbol(ssym),NULL);
 712         /* add pop to the end of the block */
 713         addiCodeToeBBlock(ebp,nic,NULL);
 714     }
 715
 716     /* if spilt because not used in the remainder of the
 717        block then add a push before this instruction and
 718        a pop at the end of the block */
 719     if (ssym->remainSpil) {
 720
 721         iCode *nic = newiCode(IPUSH,operandFromSymbol(ssym),NULL);
 722         /* add push just before this instruction */
 723         addiCodeToeBBlock(ebp,nic,ic);
 724
 725         nic = newiCode(IPOP,operandFromSymbol(ssym),NULL);
 726         /* add pop to the end of the block */
 727         addiCodeToeBBlock(ebp,nic,NULL);
 728     }
 729
 730     if (ssym == forSym )
 731         return FALSE ;
 732     else
 733         return TRUE ;
 734 }
 735
 736 /*-----------------------------------------------------------------*/
 737 /* getRegPtr - will try for PTR if not a GPR type if not spil      */
 738 /*-----------------------------------------------------------------*/
 739 static regs *getRegPtr (iCode *ic, eBBlock *ebp, symbol *sym)
 740 {
 741     regs *reg;
 742
 743  tryAgain:
 744     /* try for a ptr type */
 745     if ((reg = allocReg(REG_PTR)))
 746         return reg;
 747
 748     /* try for gpr type */
 749     if ((reg = allocReg(REG_GPR)))
 750         return reg;
 751
 752     /* we have to spil */
 753     if (!spilSomething (ic,ebp,sym))
 754         return NULL ;
 755
 756     /* this looks like an infinite loop but
 757        in really selectSpil will abort  */
 758     goto tryAgain ;
 759 }
 760
 761 /*-----------------------------------------------------------------*/
 762 /* getRegGpr - will try for GPR if not spil                        */
 763 /*-----------------------------------------------------------------*/
 764 static regs *getRegGpr (iCode *ic, eBBlock *ebp,symbol *sym)
 765 {
 766     regs *reg;
 767
 768  tryAgain:
 769     /* try for gpr type */
 770     if ((reg = allocReg(REG_GPR)))
 771         return reg;
 772
 773     if (!mcs51_ptrRegReq)
 774         if ((reg = allocReg(REG_PTR)))
 775             return reg ;
 776
 777     /* we have to spil */
 778     if (!spilSomething (ic,ebp,sym))
 779         return NULL ;
 780
 781     /* this looks like an infinite loop but
 782        in really selectSpil will abort  */
 783     goto tryAgain ;
 784 }
 785
 786 /*-----------------------------------------------------------------*/
 787 /* symHasReg - symbol has a given register                         */
 788 /*-----------------------------------------------------------------*/
 789 static bool symHasReg(symbol *sym,regs *reg)
 790 {
 791     int i;
 792
 793     for ( i = 0 ; i < sym->nRegs ; i++)
 794         if (sym->regs[i] == reg)
 795             return TRUE;
 796
 797     return FALSE;
 798 }
 799
 800 /*-----------------------------------------------------------------*/
 801 /* deassignLRs - check the live to and if they have registers & are*/
 802 /*               not spilt then free up the registers              */
 803 /*-----------------------------------------------------------------*/
 804 static void deassignLRs (iCode *ic, eBBlock *ebp)
 805 {
 806     symbol *sym;
 807     int k;
 808     symbol *result;
 809
 810     for (sym = hTabFirstItem(liveRanges,&k); sym;
 811          sym = hTabNextItem(liveRanges,&k)) {
 812
 813         symbol *psym= NULL;
 814         /* if it does not end here */
 815         if (sym->liveTo > ic->seq )
 816             continue ;
 817
 818         /* if it was spilt on stack then we can
 819            mark the stack spil location as free */
 820         if (sym->isspilt ) {
 821             if (sym->stackSpil) {
 822                 sym->usl.spillLoc->isFree = 1;
 823                 sym->stackSpil = 0;
 824             }
 825             continue ;
 826         }
 827
 828         if (!bitVectBitValue(_G.regAssigned,sym->key))
 829             continue;
 830
 831         /* special case check if this is an IFX &
 832            the privious one was a pop and the
 833            previous one was not spilt then keep track
 834            of the symbol */
 835         if (ic->op == IFX && ic->prev &&
 836             ic->prev->op == IPOP &&
 837             !ic->prev->parmPush  &&
 838             !OP_SYMBOL(IC_LEFT(ic->prev))->isspilt)
 839             psym = OP_SYMBOL(IC_LEFT(ic->prev));
 840
 841         if (sym->nRegs) {
 842             int i = 0;
 843
 844             bitVectUnSetBit(_G.regAssigned,sym->key);
 845
 846             /* if the result of this one needs registers
 847                and does not have it then assign it right
 848                away */
 849             if (IC_RESULT(ic) &&
 850                 !  (SKIP_IC2(ic) ||               /* not a special icode */
 851                     ic->op == JUMPTABLE ||
 852                     ic->op == IFX ||
 853                     ic->op == IPUSH ||
 854                     ic->op == IPOP ||
 855                     ic->op == RETURN ||
 856                     POINTER_SET(ic))     &&
 857                 (result = OP_SYMBOL(IC_RESULT(ic))) && /* has a result */
 858                 result->liveTo > ic->seq &&            /* and will live beyond this */
 859                 result->liveTo <= ebp->lSeq &&         /* does not go beyond this block */
 860                 result->regType == sym->regType &&     /* same register types */
 861                 result->nRegs            &&            /* which needs registers */
 862                 ! result->isspilt        &&            /* and does not already have them */
 863                 ! result->remat          &&
 864                 ! bitVectBitValue(_G.regAssigned,result->key) &&
 865                 /* the number of free regs + number of regs in this LR
 866                    can accomodate the what result Needs */
 867                 ((nfreeRegsType(result->regType) +
 868                   sym->nRegs) >= result->nRegs)
 869                 ) {
 870
 871                 for (i = 0 ; i < result->nRegs ; i++)
 872                     if (i < sym->nRegs )
 873                         result->regs[i] = sym->regs[i] ;
 874                     else
 875                         result->regs[i] = getRegGpr (ic,ebp,result);
 876
 877                 _G.regAssigned = bitVectSetBit(_G.regAssigned,result->key);
 878
 879             }
 880
 881             /* free the remaining */
 882             for (; i < sym->nRegs ; i++) {
 883                 if (psym) {
 884                     if (!symHasReg(psym,sym->regs[i]))
 885                         freeReg(sym->regs[i]);
 886                 } else
 887                     freeReg(sym->regs[i]);
 888             }
 889         }
 890     }
 891 }
 892
 893
 894 /*-----------------------------------------------------------------*/
 895 /* reassignLR - reassign this to registers                         */
 896 /*-----------------------------------------------------------------*/
 897 static void reassignLR (operand *op)
 898 {
 899     symbol *sym = OP_SYMBOL(op);
 900     int i;
 901
 902     /* not spilt any more */
 903     sym->isspilt = sym->blockSpil  = sym->remainSpil = 0;
 904     bitVectUnSetBit(_G.spiltSet,sym->key);
 905
 906     _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
 907
 908     _G.blockSpil--;
 909
 910     for (i=0;i<sym->nRegs;i++)
 911         sym->regs[i]->isFree = 0;
 912 }
 913
 914 /*-----------------------------------------------------------------*/
 915 /* willCauseSpill - determines if allocating will cause a spill    */
 916 /*-----------------------------------------------------------------*/
 917 static int willCauseSpill ( int nr, int rt)
 918 {
 919     /* first check if there are any avlb registers
 920        of te type required */
 921     if (rt == REG_PTR) {
 922         /* special case for pointer type
 923            if pointer type not avlb then
 924            check for type gpr */
 925         if (nFreeRegs(rt) >= nr)
 926             return 0;
 927         if (nFreeRegs(REG_GPR) >= nr)
 928             return 0;
 929     } else {
 930         if (mcs51_ptrRegReq) {
 931             if (nFreeRegs(rt) >= nr)
 932                 return 0;
 933         } else {
 934             if (nFreeRegs(REG_PTR) +
 935                 nFreeRegs(REG_GPR) >= nr)
 936                 return 0;
 937         }
 938     }
 939
 940     /* it will cause a spil */
 941     return 1;
 942 }
 943
 944 /*-----------------------------------------------------------------*/
 945 /* positionRegs - the allocator can allocate same registers to res-*/
 946 /* ult and operand, if this happens make sure they are in the same */
 947 /* position as the operand otherwise chaos results                 */
 948 /*-----------------------------------------------------------------*/
 949 static void positionRegs (symbol *result, symbol *opsym, int lineno)
 950 {
 951         int count = min(result->nRegs,opsym->nRegs);
 952         int i , j = 0, shared = 0;
 953
 954         /* if the result has been spilt then cannot share */
 955         if (opsym->isspilt)
 956                 return ;
 957  again:
 958         shared = 0;
 959         /* first make sure that they actually share */
 960         for ( i = 0 ; i < count; i++ ) {
 961                 for (j = 0 ; j < count ; j++ ) {
 962                         if (result->regs[i] == opsym->regs[j] && i !=j) {
 963                                 shared = 1;
 964                                 goto xchgPositions;
 965                         }
 966                 }
 967         }
 968  xchgPositions:
 969         if (shared) {
 970                 regs *tmp = result->regs[i];
 971                 result->regs[i] = result->regs[j];
 972                 result->regs[j] = tmp;
 973                 goto again;
 974         }
 975 }
 976
 977 /*-----------------------------------------------------------------*/
 978 /* serialRegAssign - serially allocate registers to the variables  */
 979 /*-----------------------------------------------------------------*/
 980 static void serialRegAssign (eBBlock **ebbs, int count)
 981 {
 982     int i;
 983
 984     /* for all blocks */
 985     for (i = 0; i < count ; i++ ) {
 986
 987         iCode *ic;
 988
 989         if (ebbs[i]->noPath &&
 990             (ebbs[i]->entryLabel != entryLabel &&
 991              ebbs[i]->entryLabel != returnLabel ))
 992             continue ;
 993
 994         /* of all instructions do */
 995         for (ic = ebbs[i]->sch ; ic ; ic = ic->next) {
 996
 997             /* if this is an ipop that means some live
 998                range will have to be assigned again */
 999             if (ic->op == IPOP)
1000                 reassignLR (IC_LEFT(ic));
1001
1002             /* if result is present && is a true symbol */
1003             if (IC_RESULT(ic) && ic->op != IFX &&
1004                 IS_TRUE_SYMOP(IC_RESULT(ic)))
1005                 OP_SYMBOL(IC_RESULT(ic))->allocreq = 1;
1006
1007             /* take away registers from live
1008                ranges that end at this instruction */
1009             deassignLRs (ic, ebbs[i]) ;
1010
1011             /* some don't need registers */
1012             if (SKIP_IC2(ic) ||
1013                 ic->op == JUMPTABLE ||
1014                 ic->op == IFX ||
1015                 ic->op == IPUSH ||
1016                 ic->op == IPOP ||
1017                 (IC_RESULT(ic) &&POINTER_SET(ic)) )
1018                 continue;
1019
1020             /* now we need to allocate registers
1021                only for the result */
1022             if (IC_RESULT(ic)) {
1023                 symbol *sym = OP_SYMBOL(IC_RESULT(ic));
1024                 bitVect *spillable;
1025                 int willCS ;
1026                 int j;
1027                 int ptrRegSet = 0;
1028
1029                 /* if it does not need or is spilt
1030                    or is already assigned to registers
1031                    or will not live beyond this instructions */
1032                 if (!sym->nRegs      ||
1033                     sym->isspilt     ||
1034                     bitVectBitValue(_G.regAssigned,sym->key) ||
1035                     sym->liveTo <= ic->seq)
1036                     continue ;
1037
1038                 /* if some liverange has been spilt at the block level
1039                    and this one live beyond this block then spil this
1040                    to be safe */
1041                 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq) {
1042                     spillThis (sym);
1043                     continue ;
1044                 }
1045                 /* if trying to allocate this will cause
1046                    a spill and there is nothing to spill
1047                    or this one is rematerializable then
1048                    spill this one */
1049                 willCS = willCauseSpill(sym->nRegs,sym->regType);
1050                 spillable = computeSpillable(ic);
1051                 if ( sym->remat ||
1052                     (willCS  && bitVectIsZero(spillable) ) ) {
1053
1054                     spillThis (sym) ;
1055                     continue ;
1056
1057                 }
1058
1059                 /* if it has a spillocation & is used less than
1060                    all other live ranges then spill this */
1061                 if ( willCS && sym->usl.spillLoc ) {
1062
1063                     symbol *leastUsed =
1064                         leastUsedLR(liveRangesWith (spillable ,
1065                                                     allLRs,
1066                                                     ebbs[i],
1067                                                     ic));
1068                     if (leastUsed &&
1069                         leastUsed->used > sym->used) {
1070                         spillThis (sym);
1071                         continue;
1072                     }
1073                 }
1074
1075                 /* if we need ptr regs for the right side
1076                    then mark it */
1077                 if (POINTER_GET(ic) && getSize(OP_SYMBOL(IC_LEFT(ic))->type)
1078                     <= PTRSIZE)
1079                 {
1080                     mcs51_ptrRegReq++;
1081                     ptrRegSet = 1;
1082                 }
1083                 /* else we assign registers to it */
1084                 _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
1085
1086                 for (j = 0 ; j < sym->nRegs ;j++ ) {
1087                     if (sym->regType == REG_PTR)
1088                         sym->regs[j] = getRegPtr(ic,ebbs[i],sym);
1089                     else
1090                         sym->regs[j] = getRegGpr(ic,ebbs[i],sym);
1091
1092                     /* if the allocation falied which means
1093                        this was spilt then break */
1094                     if (!sym->regs[j])
1095                         break;
1096                 }
1097                 /* if it shares registers with operands make sure
1098                    that they are in the same position */
1099                 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic)) &&
1100                     OP_SYMBOL(IC_LEFT(ic))->nRegs  && ic->op != '=')
1101                         positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1102                                      OP_SYMBOL(IC_LEFT(ic)),ic->lineno);
1103                 /* do the same for the right operand */
1104                 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic)) &&
1105                     OP_SYMBOL(IC_RIGHT(ic))->nRegs)
1106                         positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1107                                      OP_SYMBOL(IC_RIGHT(ic)),ic->lineno);
1108
1109                 if (ptrRegSet) {
1110                     mcs51_ptrRegReq--;
1111                     ptrRegSet = 0;
1112                 }
1113
1114             }
1115         }
1116     }
1117 }
1118
1119 /*-----------------------------------------------------------------*/
1120 /* rUmaskForOp :- returns register mask for an operand             */
1121 /*-----------------------------------------------------------------*/
1122 static bitVect *rUmaskForOp (operand *op)
1123 {
1124     bitVect *rumask;
1125     symbol *sym;
1126     int j;
1127
1128     /* only temporaries are assigned registers */
1129     if (!IS_ITEMP(op))
1130         return NULL;
1131
1132     sym = OP_SYMBOL(op);
1133
1134     /* if spilt or no registers assigned to it
1135        then nothing */
1136     if (sym->isspilt || !sym->nRegs)
1137         return NULL;
1138
1139     rumask = newBitVect(mcs51_nRegs);
1140
1141     for (j = 0; j < sym->nRegs; j++) {
1142         rumask = bitVectSetBit(rumask,
1143                                sym->regs[j]->rIdx);
1144     }
1145
1146     return rumask;
1147 }
1148
1149 /*-----------------------------------------------------------------*/
1150 /* regsUsedIniCode :- returns bit vector of registers used in iCode*/
1151 /*-----------------------------------------------------------------*/
1152 static bitVect *regsUsedIniCode (iCode *ic)
1153 {
1154     bitVect *rmask = newBitVect(mcs51_nRegs);
1155
1156     /* do the special cases first */
1157     if (ic->op == IFX ) {
1158         rmask = bitVectUnion(rmask,
1159                              rUmaskForOp(IC_COND(ic)));
1160         goto ret;
1161     }
1162
1163     /* for the jumptable */
1164     if (ic->op == JUMPTABLE) {
1165         rmask = bitVectUnion(rmask,
1166                              rUmaskForOp(IC_JTCOND(ic)));
1167
1168         goto ret;
1169     }
1170
1171     /* of all other cases */
1172     if (IC_LEFT(ic))
1173         rmask = bitVectUnion(rmask,
1174                              rUmaskForOp(IC_LEFT(ic)));
1175
1176
1177     if (IC_RIGHT(ic))
1178         rmask = bitVectUnion(rmask,
1179                              rUmaskForOp(IC_RIGHT(ic)));
1180
1181     if (IC_RESULT(ic))
1182         rmask = bitVectUnion(rmask,
1183                              rUmaskForOp(IC_RESULT(ic)));
1184
1185  ret:
1186     return rmask;
1187 }
1188
1189 /*-----------------------------------------------------------------*/
1190 /* createRegMask - for each instruction will determine the regsUsed*/
1191 /*-----------------------------------------------------------------*/
1192 static void createRegMask (eBBlock **ebbs, int count)
1193 {
1194     int i;
1195
1196     /* for all blocks */
1197     for (i = 0; i < count ; i++ ) {
1198         iCode *ic ;
1199
1200         if ( ebbs[i]->noPath &&
1201              ( ebbs[i]->entryLabel != entryLabel &&
1202                ebbs[i]->entryLabel != returnLabel ))
1203             continue ;
1204
1205         /* for all instructions */
1206         for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
1207
1208             int j;
1209
1210             if (SKIP_IC2(ic) || !ic->rlive)
1211                 continue ;
1212
1213             /* first mark the registers used in this
1214                instruction */
1215             ic->rUsed = regsUsedIniCode(ic);
1216             _G.funcrUsed = bitVectUnion(_G.funcrUsed,ic->rUsed);
1217
1218             /* now create the register mask for those
1219                registers that are in use : this is a
1220                super set of ic->rUsed */
1221             ic->rMask = newBitVect(mcs51_nRegs+1);
1222
1223             /* for all live Ranges alive at this point */
1224             for (j = 1; j < ic->rlive->size; j++ ) {
1225                 symbol *sym;
1226                 int k;
1227
1228                 /* if not alive then continue */
1229                 if (!bitVectBitValue(ic->rlive,j))
1230                     continue ;
1231
1232                 /* find the live range we are interested in */
1233                 if (!(sym = hTabItemWithKey(liveRanges,j))) {
1234                     werror (E_INTERNAL_ERROR,__FILE__,__LINE__,
1235                             "createRegMask cannot find live range");
1236                     exit(0);
1237                 }
1238
1239                 /* if no register assigned to it */
1240                 if (!sym->nRegs || sym->isspilt)
1241                     continue ;
1242
1243                 /* for all the registers allocated to it */
1244                 for (k = 0 ; k < sym->nRegs ;k++)
1245                     if (sym->regs[k])
1246                         ic->rMask =
1247                             bitVectSetBit(ic->rMask,sym->regs[k]->rIdx);
1248             }
1249         }
1250     }
1251 }
1252
1253 /*-----------------------------------------------------------------*/
1254 /* rematStr - returns the rematerialized string for a remat var    */
1255 /*-----------------------------------------------------------------*/
1256 static char *rematStr (symbol *sym)
1257 {
1258     char *s = buffer;
1259     iCode *ic = sym->rematiCode;
1260
1261     while (1) {
1262
1263         /* if plus or minus print the right hand side */
1264         if (ic->op == '+' || ic->op == '-') {
1265             sprintf(s,"0x%04x %c ",(int) operandLitValue(IC_RIGHT(ic)),
1266                     ic->op );
1267             s += strlen(s);
1268             ic = OP_SYMBOL(IC_LEFT(ic))->rematiCode;
1269             continue ;
1270         }
1271
1272         /* we reached the end */
1273         sprintf(s,"%s",OP_SYMBOL(IC_LEFT(ic))->rname);
1274         break;
1275     }
1276
1277     return buffer ;
1278 }
1279
1280 /*-----------------------------------------------------------------*/
1281 /* regTypeNum - computes the type & number of registers required   */
1282 /*-----------------------------------------------------------------*/
1283 static void regTypeNum ()
1284 {
1285     symbol *sym;
1286     int k;
1287     iCode *ic;
1288
1289     /* for each live range do */
1290     for ( sym = hTabFirstItem(liveRanges,&k); sym ;
1291           sym = hTabNextItem(liveRanges,&k)) {
1292
1293         /* if used zero times then no registers needed */
1294         if ((sym->liveTo - sym->liveFrom) == 0)
1295             continue ;
1296
1297
1298         /* if the live range is a temporary */
1299         if (sym->isitmp) {
1300
1301             /* if the type is marked as a conditional */
1302             if (sym->regType == REG_CND)
1303                 continue ;
1304
1305             /* if used in return only then we don't
1306                need registers */
1307             if (sym->ruonly || sym->accuse) {
1308                 if (IS_AGGREGATE(sym->type) || sym->isptr)
1309                     sym->type = aggrToPtr(sym->type,FALSE);
1310                 continue ;
1311             }
1312
1313             /* if the symbol has only one definition &
1314                that definition is a get_pointer and the
1315                pointer we are getting is rematerializable and
1316                in "data" space */
1317
1318             if (bitVectnBitsOn(sym->defs) == 1 &&
1319                 (ic = hTabItemWithKey(iCodehTab,
1320                                       bitVectFirstBit(sym->defs))) &&
1321                 POINTER_GET(ic) &&
1322                 !IS_BITVAR(sym->etype)) {
1323
1324
1325                 /* if remat in data space */
1326                 if (OP_SYMBOL(IC_LEFT(ic))->remat &&
1327                     DCL_TYPE(aggrToPtr(sym->type,FALSE)) == POINTER) {
1328
1329                     /* create a psuedo symbol & force a spil */
1330                     symbol *psym = newSymbol(rematStr(OP_SYMBOL(IC_LEFT(ic))),1);
1331                     psym->type = sym->type;
1332                     psym->etype = sym->etype;
1333                     strcpy(psym->rname,psym->name);
1334                     sym->isspilt = 1;
1335                     sym->usl.spillLoc = psym;
1336                     continue ;
1337                 }
1338
1339                 /* if in data space or idata space then try to
1340                    allocate pointer register */
1341
1342             }
1343
1344             /* if not then we require registers */
1345             sym->nRegs = ((IS_AGGREGATE(sym->type) || sym->isptr ) ?
1346                           getSize(sym->type = aggrToPtr(sym->type,FALSE)) :
1347                           getSize(sym->type));
1348
1349             if (sym->nRegs > 4) {
1350                 fprintf(stderr,"allocated more than 4 or 0 registers for type ");
1351                 printTypeChain(sym->type,stderr);fprintf(stderr,"\n");
1352             }
1353
1354             /* determine the type of register required */
1355             if (sym->nRegs == 1   &&
1356                 IS_PTR(sym->type) &&
1357                 sym->uptr)
1358                 sym->regType = REG_PTR ;
1359             else
1360                 sym->regType = REG_GPR ;
1361
1362         } else
1363             /* for the first run we don't provide */
1364             /* registers for true symbols we will */
1365             /* see how things go                  */
1366             sym->nRegs = 0 ;
1367     }
1368
1369 }
1370
1371 /*-----------------------------------------------------------------*/
1372 /* freeAllRegs - mark all registers as free                        */
1373 /*-----------------------------------------------------------------*/
1374 static void freeAllRegs()
1375 {
1376     int i;
1377
1378     for (i=0;i< mcs51_nRegs;i++ )
1379         regs8051[i].isFree = 1;
1380 }
1381
1382 /*-----------------------------------------------------------------*/
1383 /* deallocStackSpil - this will set the stack pointer back         */
1384 /*-----------------------------------------------------------------*/
1385 static DEFSETFUNC(deallocStackSpil)
1386 {
1387     symbol *sym = item;
1388
1389     deallocLocal(sym);
1390     return 0;
1391 }
1392
1393 /*-----------------------------------------------------------------*/
1394 /* farSpacePackable - returns the packable icode for far variables */
1395 /*-----------------------------------------------------------------*/
1396 static iCode *farSpacePackable (iCode *ic)
1397 {
1398     iCode *dic ;
1399
1400     /* go thru till we find a definition for the
1401        symbol on the right */
1402     for ( dic = ic->prev ; dic ; dic = dic->prev) {
1403
1404         /* if the definition is a call then no */
1405         if ((dic->op == CALL || dic->op == PCALL) &&
1406             IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1407             return NULL;
1408         }
1409
1410         /* if shift by unknown amount then not */
1411         if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1412             IC_RESULT(dic)->key == IC_RIGHT(ic)->key)
1413             return NULL;
1414
1415         /* if pointer get and size > 1 */
1416         if (POINTER_GET(dic) &&
1417             getSize(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)) > 1)
1418             return NULL ;
1419
1420         if (POINTER_SET(dic) &&
1421             getSize(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)) > 1)
1422             return NULL ;
1423
1424         /* if any three is a true symbol in far space */
1425         if (IC_RESULT(dic) &&
1426             IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1427             isOperandInFarSpace(IC_RESULT(dic)))
1428             return NULL;
1429
1430         if (IC_RIGHT(dic) &&
1431             IS_TRUE_SYMOP(IC_RIGHT(dic)) &&
1432             isOperandInFarSpace(IC_RIGHT(dic)) &&
1433             !isOperandEqual(IC_RIGHT(dic),IC_RESULT(ic)))
1434             return NULL;
1435
1436         if (IC_LEFT(dic) &&
1437             IS_TRUE_SYMOP(IC_LEFT(dic)) &&
1438             isOperandInFarSpace(IC_LEFT(dic)) &&
1439             !isOperandEqual(IC_LEFT(dic),IC_RESULT(ic)))
1440             return NULL;
1441
1442         if (isOperandEqual(IC_RIGHT(ic),IC_RESULT(dic))) {
1443             if ( (dic->op == LEFT_OP  ||
1444                   dic->op == RIGHT_OP ||
1445                   dic->op == '-') &&
1446                  IS_OP_LITERAL(IC_RIGHT(dic)))
1447                 return NULL;
1448             else
1449                 return dic;
1450         }
1451     }
1452
1453     return NULL;
1454 }
1455
1456 /*-----------------------------------------------------------------*/
1457 /* packRegsForAssign - register reduction for assignment           */
1458 /*-----------------------------------------------------------------*/
1459 static int packRegsForAssign (iCode *ic,eBBlock *ebp)
1460 {
1461     iCode *dic, *sic;
1462
1463     if (!IS_ITEMP(IC_RIGHT(ic))       ||
1464         OP_SYMBOL(IC_RIGHT(ic))->isind ||
1465         OP_LIVETO(IC_RIGHT(ic)) > ic->seq) {
1466         return 0;
1467     }
1468
1469     /* if the true symbol is defined in far space or on stack
1470        then we should not since this will increase register pressure */
1471     if (isOperandInFarSpace(IC_RESULT(ic))) {
1472         if ((dic = farSpacePackable(ic)))
1473             goto pack;
1474         else
1475             return 0;
1476
1477     }
1478     /* find the definition of iTempNN scanning backwards if we find a
1479        a use of the true symbol in before we find the definition then
1480        we cannot */
1481     for ( dic = ic->prev ; dic ; dic = dic->prev) {
1482
1483         /* if there is a function call and this is
1484            a parameter & not my parameter then don't pack it */
1485         if ( (dic->op == CALL || dic->op == PCALL) &&
1486              (OP_SYMBOL(IC_RESULT(ic))->_isparm &&
1487               !OP_SYMBOL(IC_RESULT(ic))->ismyparm)) {
1488             dic = NULL;
1489             break;
1490         }
1491
1492         if (SKIP_IC2(dic))
1493             continue;
1494
1495         if (IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1496             IS_OP_VOLATILE(IC_RESULT(dic))) {
1497                 dic = NULL;
1498                 break;
1499         }
1500
1501         if (IS_SYMOP(IC_RESULT(dic)) &&
1502             IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1503             if (POINTER_SET(dic))
1504                 dic = NULL;
1505
1506             break;
1507         }
1508
1509         if (IS_SYMOP(IC_RIGHT(dic)) &&
1510             (IC_RIGHT(dic)->key == IC_RESULT(ic)->key ||
1511              IC_RIGHT(dic)->key == IC_RIGHT(ic)->key)) {
1512             dic = NULL;
1513             break;
1514         }
1515
1516         if (IS_SYMOP(IC_LEFT(dic)) &&
1517             (IC_LEFT(dic)->key == IC_RESULT(ic)->key ||
1518              IC_LEFT(dic)->key == IC_RIGHT(ic)->key)) {
1519             dic = NULL;
1520             break;
1521         }
1522
1523         if (POINTER_SET(dic) &&
1524             IC_RESULT(dic)->key == IC_RESULT(ic)->key ) {
1525             dic = NULL ;
1526             break;
1527         }
1528     }
1529
1530     if (!dic)
1531         return 0 ; /* did not find */
1532
1533     /* if the result is on stack or iaccess then it must be
1534        the same atleast one of the operands */
1535     if (OP_SYMBOL(IC_RESULT(ic))->onStack  ||
1536         OP_SYMBOL(IC_RESULT(ic))->iaccess ) {
1537
1538         /* the operation has only one symbol
1539            operator then we can pack */
1540         if ((IC_LEFT(dic) && !IS_SYMOP(IC_LEFT(dic))) ||
1541             (IC_RIGHT(dic) && !IS_SYMOP(IC_RIGHT(dic))))
1542             goto pack;
1543
1544         if (!((IC_LEFT(dic) &&
1545              IC_RESULT(ic)->key == IC_LEFT(dic)->key) ||
1546               (IC_RIGHT(dic) &&
1547                IC_RESULT(ic)->key == IC_RIGHT(dic)->key)))
1548             return 0;
1549     }
1550 pack:
1551     /* found the definition */
1552     /* replace the result with the result of */
1553     /* this assignment and remove this assignment */
1554     IC_RESULT(dic) = IC_RESULT(ic) ;
1555
1556     if (IS_ITEMP(IC_RESULT(dic)) && OP_SYMBOL(IC_RESULT(dic))->liveFrom > dic->seq) {
1557             OP_SYMBOL(IC_RESULT(dic))->liveFrom = dic->seq;
1558     }
1559     /* delete from liverange table also
1560        delete from all the points inbetween and the new
1561        one */
1562     for ( sic = dic; sic != ic ; sic = sic->next ) {
1563         bitVectUnSetBit(sic->rlive,IC_RESULT(ic)->key);
1564         if (IS_ITEMP(IC_RESULT(dic)))
1565             bitVectSetBit(sic->rlive,IC_RESULT(dic)->key);
1566     }
1567
1568     remiCodeFromeBBlock(ebp,ic);
1569     hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
1570     OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
1571     return 1;
1572
1573 }
1574
1575 /*-----------------------------------------------------------------*/
1576 /* findAssignToSym : scanning backwards looks for first assig found*/
1577 /*-----------------------------------------------------------------*/
1578 static iCode *findAssignToSym (operand *op,iCode *ic)
1579 {
1580     iCode *dic;
1581
1582     for (dic = ic->prev ; dic ; dic = dic->prev) {
1583
1584         /* if definition by assignment */
1585         if (dic->op == '='                 &&
1586             !POINTER_SET(dic)              &&
1587             IC_RESULT(dic)->key == op->key
1588 /*          &&  IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1589             ) {
1590
1591             /* we are interested only if defined in far space */
1592             /* or in stack space in case of + & - */
1593
1594             /* if assigned to a non-symbol then return
1595                true */
1596             if (!IS_SYMOP(IC_RIGHT(dic)))
1597                 break ;
1598
1599             /* if the symbol is in far space then
1600                we should not */
1601             if (isOperandInFarSpace(IC_RIGHT(dic)))
1602                 return NULL ;
1603
1604             /* for + & - operations make sure that
1605                if it is on the stack it is the same
1606                as one of the three operands */
1607             if ((ic->op == '+' || ic->op == '-') &&
1608                 OP_SYMBOL(IC_RIGHT(dic))->onStack) {
1609
1610                 if ( IC_RESULT(ic)->key != IC_RIGHT(dic)->key &&
1611                      IC_LEFT(ic)->key   != IC_RIGHT(dic)->key &&
1612                      IC_RIGHT(ic)->key  != IC_RIGHT(dic)->key)
1613                     return NULL;
1614             }
1615
1616             break ;
1617
1618         }
1619
1620         /* if we find an usage then we cannot delete it */
1621         if (IC_LEFT(dic) && IC_LEFT(dic)->key == op->key)
1622             return NULL;
1623
1624         if (IC_RIGHT(dic) && IC_RIGHT(dic)->key == op->key)
1625             return NULL;
1626
1627         if (POINTER_SET(dic) && IC_RESULT(dic)->key == op->key)
1628             return NULL;
1629     }
1630
1631     /* now make sure that the right side of dic
1632        is not defined between ic & dic */
1633     if (dic) {
1634         iCode *sic = dic->next ;
1635
1636         for (; sic != ic ; sic = sic->next)
1637             if (IC_RESULT(sic) &&
1638                 IC_RESULT(sic)->key == IC_RIGHT(dic)->key)
1639                 return NULL;
1640     }
1641
1642     return dic;
1643
1644
1645 }
1646
1647 /*-----------------------------------------------------------------*/
1648 /* packRegsForSupport :- reduce some registers for support calls   */
1649 /*-----------------------------------------------------------------*/
1650 static int packRegsForSupport (iCode *ic, eBBlock *ebp)
1651 {
1652     int change = 0 ;
1653     /* for the left & right operand :- look to see if the
1654        left was assigned a true symbol in far space in that
1655        case replace them */
1656     if (IS_ITEMP(IC_LEFT(ic)) &&
1657         OP_SYMBOL(IC_LEFT(ic))->liveTo <= ic->seq) {
1658         iCode *dic = findAssignToSym(IC_LEFT(ic),ic);
1659         iCode *sic;
1660
1661         if (!dic)
1662             goto right ;
1663
1664         /* found it we need to remove it from the
1665            block */
1666         for ( sic = dic; sic != ic ; sic = sic->next )
1667             bitVectUnSetBit(sic->rlive,IC_LEFT(ic)->key);
1668
1669         IC_LEFT(ic)->operand.symOperand =
1670             IC_RIGHT(dic)->operand.symOperand;
1671         IC_LEFT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1672         remiCodeFromeBBlock(ebp,dic);
1673         hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1674         change++;
1675     }
1676
1677     /* do the same for the right operand */
1678  right:
1679     if (!change &&
1680         IS_ITEMP(IC_RIGHT(ic)) &&
1681         OP_SYMBOL(IC_RIGHT(ic))->liveTo <= ic->seq) {
1682         iCode *dic = findAssignToSym(IC_RIGHT(ic),ic);
1683         iCode *sic;
1684
1685         if (!dic)
1686             return change ;
1687
1688         /* if this is a subtraction & the result
1689            is a true symbol in far space then don't pack */
1690         if (ic->op == '-' && IS_TRUE_SYMOP(IC_RESULT(dic))) {
1691             link *etype =getSpec(operandType(IC_RESULT(dic)));
1692             if (IN_FARSPACE(SPEC_OCLS(etype)))
1693                 return change ;
1694         }
1695         /* found it we need to remove it from the
1696            block */
1697         for ( sic = dic; sic != ic ; sic = sic->next )
1698             bitVectUnSetBit(sic->rlive,IC_RIGHT(ic)->key);
1699
1700         IC_RIGHT(ic)->operand.symOperand =
1701             IC_RIGHT(dic)->operand.symOperand;
1702         IC_RIGHT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1703
1704         remiCodeFromeBBlock(ebp,dic);
1705         hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1706         change ++;
1707     }
1708
1709     return change ;
1710 }
1711
1712 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1713
1714
1715 /*-----------------------------------------------------------------*/
1716 /* packRegsForOneuse : - will reduce some registers for single Use */
1717 /*-----------------------------------------------------------------*/
1718 static iCode *packRegsForOneuse (iCode *ic, operand *op , eBBlock *ebp)
1719 {
1720     bitVect *uses ;
1721     iCode *dic, *sic;
1722
1723     /* if returning a literal then do nothing */
1724     if (!IS_SYMOP(op))
1725         return NULL;
1726
1727     /* only upto 2 bytes since we cannot predict
1728        the usage of b, & acc */
1729     if (getSize(operandType(op)) >  (fReturnSize - 2) &&
1730         ic->op != RETURN             &&
1731         ic->op != SEND               &&
1732         !POINTER_SET(ic)             &&
1733         !POINTER_GET(ic))
1734         return NULL;
1735
1736     /* this routine will mark the a symbol as used in one
1737        instruction use only && if the defintion is local
1738        (ie. within the basic block) && has only one definition &&
1739        that definiion is either a return value from a
1740        function or does not contain any variables in
1741        far space */
1742     uses = bitVectCopy(OP_USES(op));
1743     bitVectUnSetBit(uses,ic->key); /* take away this iCode */
1744     if (!bitVectIsZero(uses)) /* has other uses */
1745         return NULL ;
1746
1747     /* if it has only one defintion */
1748     if (bitVectnBitsOn(OP_DEFS(op)) > 1)
1749         return NULL ; /* has more than one definition */
1750
1751     /* get the that definition */
1752     if (!(dic =
1753           hTabItemWithKey(iCodehTab,
1754                           bitVectFirstBit(OP_DEFS(op)))))
1755         return NULL ;
1756
1757     /* found the definition now check if it is local */
1758     if (dic->seq < ebp->fSeq ||
1759         dic->seq > ebp->lSeq)
1760         return NULL ; /* non-local */
1761
1762     /* now check if it is the return from
1763        a function call */
1764     if (dic->op == CALL || dic->op == PCALL ) {
1765         if (ic->op != SEND && ic->op != RETURN) {
1766             OP_SYMBOL(op)->ruonly = 1;
1767             return dic;
1768         }
1769         dic = dic->next ;
1770     }
1771
1772
1773     /* otherwise check that the definition does
1774        not contain any symbols in far space */
1775     if (isOperandInFarSpace(IC_LEFT(dic))  ||
1776         isOperandInFarSpace(IC_RIGHT(dic)) ||
1777         IS_OP_RUONLY(IC_LEFT(ic))          ||
1778         IS_OP_RUONLY(IC_RIGHT(ic)) )        {
1779         return NULL;
1780     }
1781
1782     /* if pointer set then make sure the pointer
1783        is one byte */
1784     if (POINTER_SET(dic) &&
1785         !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1786         return NULL ;
1787
1788     if (POINTER_GET(dic) &&
1789         !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1790         return NULL ;
1791
1792     sic = dic;
1793
1794     /* also make sure the intervenening instructions
1795        don't have any thing in far space */
1796     for (dic = dic->next ; dic && dic != ic && sic != ic; dic = dic->next) {
1797
1798         /* if there is an intervening function call then no */
1799         if (dic->op == CALL || dic->op == PCALL)
1800                 return NULL;
1801         /* if pointer set then make sure the pointer
1802            is one byte */
1803         if (POINTER_SET(dic) &&
1804             !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1805             return NULL ;
1806
1807         if (POINTER_GET(dic) &&
1808             !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1809             return NULL ;
1810
1811         /* if address of & the result is remat the okay */
1812         if (dic->op == ADDRESS_OF &&
1813             OP_SYMBOL(IC_RESULT(dic))->remat)
1814             continue ;
1815
1816         /* if operand has size of three or more & this
1817            operation is a '*','/' or '%' then 'b' may
1818            cause a problem */
1819         if (( dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1820             getSize(operandType(op)) >= 3)
1821                 return NULL;
1822
1823         /* if left or right or result is in far space */
1824         if (isOperandInFarSpace(IC_LEFT(dic))   ||
1825             isOperandInFarSpace(IC_RIGHT(dic))  ||
1826             isOperandInFarSpace(IC_RESULT(dic)) ||
1827             IS_OP_RUONLY(IC_LEFT(dic))          ||
1828             IS_OP_RUONLY(IC_RIGHT(dic))         ||
1829             IS_OP_RUONLY(IC_RESULT(dic))            ) {
1830             return NULL;
1831         }
1832     }
1833
1834     OP_SYMBOL(op)->ruonly = 1;
1835     return sic;
1836
1837 }
1838
1839 /*-----------------------------------------------------------------*/
1840 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN          */
1841 /*-----------------------------------------------------------------*/
1842 static bool isBitwiseOptimizable (iCode *ic)
1843 {
1844     link *ltype = getSpec(operandType(IC_LEFT(ic)));
1845     link *rtype = getSpec(operandType(IC_RIGHT(ic)));
1846
1847     /* bitwise operations are considered optimizable
1848        under the following conditions (Jean-Louis VERN)
1849
1850        x & lit
1851        bit & bit
1852        bit & x
1853        bit ^ bit
1854        bit ^ x
1855        x   ^ lit
1856        x   | lit
1857        bit | bit
1858        bit | x
1859     */
1860     if ( IS_LITERAL(rtype) ||
1861          (IS_BITVAR(ltype) && IN_BITSPACE(SPEC_OCLS(ltype))))
1862         return TRUE ;
1863     else
1864         return FALSE ;
1865 }
1866
1867 /*-----------------------------------------------------------------*/
1868 /* packRegsForAccUse - pack registers for acc use                  */
1869 /*-----------------------------------------------------------------*/
1870 static void packRegsForAccUse (iCode *ic)
1871 {
1872     iCode *uic;
1873
1874     /* if + or - then it has to be one byte result */
1875     if ((ic->op == '+' || ic->op == '-')
1876         && getSize(operandType(IC_RESULT(ic))) > 1)
1877         return ;
1878
1879     /* if shift operation make sure right side is not a literal */
1880     if (ic->op == RIGHT_OP  &&
1881         ( isOperandLiteral(IC_RIGHT(ic)) ||
1882           getSize(operandType(IC_RESULT(ic))) > 1))
1883         return ;
1884
1885     if (ic->op == LEFT_OP &&
1886         ( isOperandLiteral(IC_RIGHT(ic)) ||
1887           getSize(operandType(IC_RESULT(ic))) > 1))
1888         return ;
1889
1890     if (IS_BITWISE_OP(ic) &&
1891         getSize(operandType(IC_RESULT(ic))) > 1)
1892         return ;
1893
1894
1895     /* has only one definition */
1896     if (bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1)
1897         return ;
1898
1899     /* has only one use */
1900     if (bitVectnBitsOn(OP_USES(IC_RESULT(ic))) > 1)
1901         return ;
1902
1903     /* and the usage immediately follows this iCode */
1904     if (!(uic = hTabItemWithKey(iCodehTab,
1905                                 bitVectFirstBit(OP_USES(IC_RESULT(ic))))))
1906         return ;
1907
1908     if (ic->next != uic)
1909         return ;
1910
1911     /* if it is a conditional branch then we definitely can */
1912     if (uic->op == IFX  )
1913         goto accuse;
1914
1915     if ( uic->op == JUMPTABLE )
1916         return ;
1917
1918     /* if the usage is not is an assignment
1919        or an arithmetic / bitwise / shift operation then not */
1920     if (POINTER_SET(uic) &&
1921         getSize(aggrToPtr(operandType(IC_RESULT(uic)),FALSE)) > 1)
1922         return;
1923
1924     if (uic->op != '=' &&
1925         !IS_ARITHMETIC_OP(uic) &&
1926         !IS_BITWISE_OP(uic)    &&
1927         uic->op != LEFT_OP &&
1928         uic->op != RIGHT_OP )
1929         return;
1930
1931     /* if used in ^ operation then make sure right is not a
1932        literl */
1933     if (uic->op == '^' && isOperandLiteral(IC_RIGHT(uic)))
1934         return ;
1935
1936     /* if shift operation make sure right side is not a literal */
1937     if (uic->op == RIGHT_OP  &&
1938         ( isOperandLiteral(IC_RIGHT(uic)) ||
1939           getSize(operandType(IC_RESULT(uic))) > 1))
1940         return ;
1941
1942     if (uic->op == LEFT_OP &&
1943         ( isOperandLiteral(IC_RIGHT(uic)) ||
1944           getSize(operandType(IC_RESULT(uic))) > 1))
1945         return ;
1946
1947     /* make sure that the result of this icode is not on the
1948        stack, since acc is used to compute stack offset */
1949     if (IS_TRUE_SYMOP(IC_RESULT(uic)) &&
1950         OP_SYMBOL(IC_RESULT(uic))->onStack)
1951         return ;
1952
1953     /* if either one of them in far space then we cannot */
1954     if ((IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1955          isOperandInFarSpace(IC_LEFT(uic))) ||
1956         (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1957          isOperandInFarSpace(IC_RIGHT(uic))))
1958         return ;
1959
1960     /* if the usage has only one operand then we can */
1961     if (IC_LEFT(uic) == NULL ||
1962         IC_RIGHT(uic) == NULL)
1963         goto accuse;
1964
1965     /* make sure this is on the left side if not
1966        a '+' since '+' is commutative */
1967     if (ic->op != '+' &&
1968         IC_LEFT(uic)->key != IC_RESULT(ic)->key)
1969         return;
1970
1971     /* if one of them is a literal then we can */
1972     if ((IC_LEFT(uic) && IS_OP_LITERAL(IC_LEFT(uic))) ||
1973         (IC_RIGHT(uic) && IS_OP_LITERAL(IC_RIGHT(uic)))) {
1974         OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
1975         return ;
1976     }
1977
1978     /* if the other one is not on stack then we can */
1979     if (IC_LEFT(uic)->key == IC_RESULT(ic)->key &&
1980         (IS_ITEMP(IC_RIGHT(uic)) ||
1981          (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1982           !OP_SYMBOL(IC_RIGHT(uic))->onStack)))
1983         goto accuse;
1984
1985     if (IC_RIGHT(uic)->key == IC_RESULT(ic)->key &&
1986         (IS_ITEMP(IC_LEFT(uic)) ||
1987          (IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1988           !OP_SYMBOL(IC_LEFT(uic))->onStack)))
1989         goto accuse ;
1990
1991     return ;
1992
1993  accuse:
1994     OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
1995
1996
1997 }
1998
1999 /*-----------------------------------------------------------------*/
2000 /* packForPush - hueristics to reduce iCode for pushing            */
2001 /*-----------------------------------------------------------------*/
2002 static void packForPush(iCode *ic, eBBlock *ebp)
2003 {
2004     iCode *dic;
2005
2006     if (ic->op != IPUSH || !IS_ITEMP(IC_LEFT(ic)))
2007         return ;
2008
2009     /* must have only definition & one usage */
2010     if (bitVectnBitsOn(OP_DEFS(IC_LEFT(ic))) != 1 ||
2011         bitVectnBitsOn(OP_USES(IC_LEFT(ic))) != 1 )
2012         return ;
2013
2014     /* find the definition */
2015     if (!(dic = hTabItemWithKey(iCodehTab,
2016                                 bitVectFirstBit(OP_DEFS(IC_LEFT(ic))))))
2017         return ;
2018
2019     if (dic->op != '=' || POINTER_SET(dic))
2020         return;
2021
2022     /* we now we know that it has one & only one def & use
2023        and the that the definition is an assignment */
2024     IC_LEFT(ic) = IC_RIGHT(dic);
2025
2026     remiCodeFromeBBlock(ebp,dic);
2027     hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
2028 }
2029
2030 /*-----------------------------------------------------------------*/
2031 /* packRegisters - does some transformations to reduce register    */
2032 /*                   pressure                                      */
2033 /*-----------------------------------------------------------------*/
2034 static void packRegisters (eBBlock *ebp)
2035 {
2036     iCode *ic ;
2037     int change = 0 ;
2038
2039     while (1) {
2040
2041         change = 0;
2042
2043         /* look for assignments of the form */
2044         /* iTempNN = TRueSym (someoperation) SomeOperand */
2045         /*       ....                       */
2046         /* TrueSym := iTempNN:1             */
2047         for ( ic = ebp->sch ; ic ; ic = ic->next ) {
2048
2049
2050             /* find assignment of the form TrueSym := iTempNN:1 */
2051             if (ic->op == '=' && !POINTER_SET(ic))
2052                 change += packRegsForAssign(ic,ebp);
2053         }
2054
2055         if (!change)
2056             break;
2057     }
2058
2059     for ( ic = ebp->sch ; ic ; ic = ic->next ) {
2060
2061         /* if this is an itemp & result of a address of a true sym
2062            then mark this as rematerialisable   */
2063         if (ic->op == ADDRESS_OF &&
2064             IS_ITEMP(IC_RESULT(ic)) &&
2065             IS_TRUE_SYMOP(IC_LEFT(ic)) &&
2066             bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2067             !OP_SYMBOL(IC_LEFT(ic))->onStack ) {
2068
2069             OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2070             OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2071             OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2072
2073         }
2074
2075         /* if straight assignment then carry remat flag if
2076            this is the only definition */
2077         if (ic->op == '='    &&
2078             !POINTER_SET(ic) &&
2079             IS_SYMOP(IC_RIGHT(ic)) &&
2080             OP_SYMBOL(IC_RIGHT(ic))->remat &&
2081             bitVectnBitsOn(OP_SYMBOL(IC_RESULT(ic))->defs) <= 1) {
2082
2083             OP_SYMBOL(IC_RESULT(ic))->remat =
2084                 OP_SYMBOL(IC_RIGHT(ic))->remat;
2085             OP_SYMBOL(IC_RESULT(ic))->rematiCode =
2086                 OP_SYMBOL(IC_RIGHT(ic))->rematiCode ;
2087         }
2088
2089         /* if this is a +/- operation with a rematerizable
2090            then mark this as rematerializable as well */
2091         if ((ic->op == '+' || ic->op == '-') &&
2092             (IS_SYMOP(IC_LEFT(ic)) &&
2093              IS_ITEMP(IC_RESULT(ic)) &&
2094              OP_SYMBOL(IC_LEFT(ic))->remat &&
2095              bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2096              IS_OP_LITERAL(IC_RIGHT(ic))) ) {
2097
2098             int i = operandLitValue(IC_RIGHT(ic));
2099             OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2100             OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2101             OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2102         }
2103
2104         /* mark the pointer usages */
2105         if (POINTER_SET(ic))
2106             OP_SYMBOL(IC_RESULT(ic))->uptr = 1;
2107
2108         if (POINTER_GET(ic))
2109             OP_SYMBOL(IC_LEFT(ic))->uptr = 1;
2110
2111         if (!SKIP_IC2(ic)) {
2112             /* if we are using a symbol on the stack
2113                then we should say mcs51_ptrRegReq */
2114             if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
2115                 mcs51_ptrRegReq += ((OP_SYMBOL(IC_COND(ic))->onStack ||
2116                                OP_SYMBOL(IC_COND(ic))->iaccess) ? 1 : 0);
2117             else
2118                 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
2119                     mcs51_ptrRegReq += ((OP_SYMBOL(IC_JTCOND(ic))->onStack ||
2120                                    OP_SYMBOL(IC_JTCOND(ic))->iaccess) ? 1 : 0);
2121                 else {
2122                     if (IS_SYMOP(IC_LEFT(ic)))
2123                         mcs51_ptrRegReq += ((OP_SYMBOL(IC_LEFT(ic))->onStack ||
2124                                        OP_SYMBOL(IC_LEFT(ic))->iaccess) ? 1 : 0);
2125                     if (IS_SYMOP(IC_RIGHT(ic)))
2126                         mcs51_ptrRegReq += ((OP_SYMBOL(IC_RIGHT(ic))->onStack ||
2127                                        OP_SYMBOL(IC_RIGHT(ic))->iaccess) ? 1 : 0);
2128                     if (IS_SYMOP(IC_RESULT(ic)))
2129                         mcs51_ptrRegReq += ((OP_SYMBOL(IC_RESULT(ic))->onStack ||
2130                                        OP_SYMBOL(IC_RESULT(ic))->iaccess) ? 1 : 0);
2131                 }
2132         }
2133
2134         /* if the condition of an if instruction
2135            is defined in the previous instruction then
2136            mark the itemp as a conditional */
2137         if ((IS_CONDITIONAL(ic) ||
2138              ( ( ic->op == BITWISEAND      ||
2139                  ic->op == '|'             ||
2140                  ic->op == '^' ) &&
2141                isBitwiseOptimizable(ic))) &&
2142             ic->next && ic->next->op == IFX &&
2143             isOperandEqual(IC_RESULT(ic),IC_COND(ic->next)) &&
2144             OP_SYMBOL(IC_RESULT(ic))->liveTo <= ic->next->seq) {
2145
2146             OP_SYMBOL(IC_RESULT(ic))->regType = REG_CND;
2147             continue ;
2148         }
2149
2150         /* reduce for support function calls */
2151         if (ic->supportRtn || ic->op == '+' || ic->op == '-' )
2152             packRegsForSupport (ic,ebp);
2153
2154         /* some cases the redundant moves can
2155            can be eliminated for return statements */
2156         if ((ic->op == RETURN || ic->op == SEND) &&
2157             !isOperandInFarSpace(IC_LEFT(ic))    &&
2158             options.model == MODEL_SMALL)
2159             packRegsForOneuse (ic,IC_LEFT(ic),ebp);
2160
2161         /* if pointer set & left has a size more than
2162            one and right is not in far space */
2163         if (POINTER_SET(ic)                    &&
2164             !isOperandInFarSpace(IC_RIGHT(ic)) &&
2165             !OP_SYMBOL(IC_RESULT(ic))->remat   &&
2166             !IS_OP_RUONLY(IC_RIGHT(ic))        &&
2167             getSize(aggrToPtr(operandType(IC_RESULT(ic)),FALSE)) > 1 )
2168
2169             packRegsForOneuse (ic,IC_RESULT(ic),ebp);
2170
2171         /* if pointer get */
2172         if (POINTER_GET(ic)                    &&
2173             !isOperandInFarSpace(IC_RESULT(ic))&&
2174             !OP_SYMBOL(IC_LEFT(ic))->remat     &&
2175             !IS_OP_RUONLY(IC_RESULT(ic))         &&
2176             getSize(aggrToPtr(operandType(IC_LEFT(ic)),FALSE)) > 1 )
2177
2178             packRegsForOneuse (ic,IC_LEFT(ic),ebp);
2179
2180
2181         /* if this is cast for intergral promotion then
2182            check if only use of  the definition of the
2183            operand being casted/ if yes then replace
2184            the result of that arithmetic operation with
2185            this result and get rid of the cast */
2186         if (ic->op == CAST) {
2187             link *fromType = operandType(IC_RIGHT(ic));
2188             link *toType = operandType(IC_LEFT(ic));
2189
2190             if (IS_INTEGRAL(fromType) && IS_INTEGRAL(toType) &&
2191                 getSize(fromType) != getSize(toType) ) {
2192
2193                 iCode *dic = packRegsForOneuse(ic,IC_RIGHT(ic),ebp);
2194                 if (dic) {
2195                     if (IS_ARITHMETIC_OP(dic)) {
2196                         IC_RESULT(dic) = IC_RESULT(ic);
2197                         remiCodeFromeBBlock(ebp,ic);
2198                         hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2199                         OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
2200                         ic = ic->prev;
2201                     } else
2202                         OP_SYMBOL(IC_RIGHT(ic))->ruonly =  0;
2203                 }
2204             } else {
2205
2206                 /* if the type from and type to are the same
2207                    then if this is the only use then packit */
2208                 if (checkType(operandType(IC_RIGHT(ic)),
2209                               operandType(IC_LEFT(ic))) == 1) {
2210                     iCode *dic = packRegsForOneuse (ic,IC_RIGHT(ic),ebp);
2211                     if (dic) {
2212                         IC_RESULT(dic) = IC_RESULT(ic);
2213                         remiCodeFromeBBlock(ebp,ic);
2214                         hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2215                         OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
2216                         ic = ic->prev;
2217                     }
2218                 }
2219             }
2220         }
2221
2222         /* pack for PUSH
2223            iTempNN := (some variable in farspace) V1
2224            push iTempNN ;
2225            -------------
2226            push V1
2227         */
2228         if (ic->op == IPUSH ) {
2229             packForPush(ic,ebp);
2230         }
2231
2232
2233         /* pack registers for accumulator use, when the
2234            result of an arithmetic or bit wise operation
2235            has only one use, that use is immediately following
2236            the defintion and the using iCode has only one
2237            operand or has two operands but one is literal &
2238            the result of that operation is not on stack then
2239            we can leave the result of this operation in acc:b
2240            combination */
2241         if ((IS_ARITHMETIC_OP(ic)
2242
2243              || IS_BITWISE_OP(ic)
2244
2245              || ic->op == LEFT_OP || ic->op == RIGHT_OP
2246
2247              ) &&
2248             IS_ITEMP(IC_RESULT(ic)) &&
2249             getSize(operandType(IC_RESULT(ic))) <= 2)
2250
2251             packRegsForAccUse (ic);
2252
2253     }
2254 }
2255
2256 /*-----------------------------------------------------------------*/
2257 /* assignRegisters - assigns registers to each live range as need  */
2258 /*-----------------------------------------------------------------*/
2259 void mcs51_assignRegisters (eBBlock **ebbs, int count)
2260 {
2261     iCode *ic;
2262     int i ;
2263
2264     setToNull((void *)&_G.funcrUsed);
2265     mcs51_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2266     /* if not register extentions then reduce number
2267        of registers */
2268     if (options.regExtend)
2269         mcs51_nRegs = 13;
2270     else
2271         mcs51_nRegs = 8;
2272
2273     /* change assignments this will remove some
2274        live ranges reducing some register pressure */
2275     for (i = 0 ; i < count ;i++ )
2276         packRegisters (ebbs[i]);
2277
2278     if (options.dump_pack)
2279         dumpEbbsToFileExt(".dumppack",ebbs,count);
2280
2281     /* first determine for each live range the number of
2282        registers & the type of registers required for each */
2283     regTypeNum ();
2284
2285     /* and serially allocate registers */
2286     serialRegAssign(ebbs,count);
2287
2288     /* if stack was extended then tell the user */
2289     if (_G.stackExtend) {
2290 /*      werror(W_TOOMANY_SPILS,"stack", */
2291 /*             _G.stackExtend,currFunc->name,""); */
2292         _G.stackExtend = 0 ;
2293     }
2294
2295     if (_G.dataExtend) {
2296 /*      werror(W_TOOMANY_SPILS,"data space", */
2297 /*             _G.dataExtend,currFunc->name,""); */
2298         _G.dataExtend = 0 ;
2299     }
2300
2301     /* after that create the register mask
2302        for each of the instruction */
2303     createRegMask (ebbs,count);
2304
2305     /* redo that offsets for stacked automatic variables */
2306     redoStackOffsets ();
2307
2308     if (options.dump_rassgn) {
2309         dumpEbbsToFileExt(".dumprassgn",ebbs,count);
2310         dumpLiveRanges(".lrange",liveRanges);
2311     }
2312
2313     /* do the overlaysegment stuff SDCCmem.c */
2314     doOverlays(ebbs,count);
2315
2316     /* now get back the chain */
2317     ic = iCodeLabelOptimize(iCodeFromeBBlock (ebbs,count));
2318
2319
2320     gen51Code(ic);
2321
2322     /* free up any _G.stackSpil locations allocated */
2323     applyToSet(_G.stackSpil,deallocStackSpil);
2324     _G.slocNum = 0;
2325     setToNull((void **)&_G.stackSpil);
2326     setToNull((void **)&_G.spiltSet);
2327     /* mark all registers as free */
2328     freeAllRegs();
2329
2330     return ;
2331 }