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