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,ic->seq,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     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         return NULL;
1733
1734     /* this routine will mark the a symbol as used in one
1735        instruction use only && if the defintion is local
1736        (ie. within the basic block) && has only one definition &&
1737        that definiion is either a return value from a
1738        function or does not contain any variables in
1739        far space */
1740     uses = bitVectCopy(OP_USES(op));
1741     bitVectUnSetBit(uses,ic->key); /* take away this iCode */
1742     if (!bitVectIsZero(uses)) /* has other uses */
1743         return NULL ;
1744
1745     /* if it has only one defintion */
1746     if (bitVectnBitsOn(OP_DEFS(op)) > 1)
1747         return NULL ; /* has more than one definition */
1748
1749     /* get the that definition */
1750     if (!(dic =
1751           hTabItemWithKey(iCodehTab,
1752                           bitVectFirstBit(OP_DEFS(op)))))
1753         return NULL ;
1754
1755     /* found the definition now check if it is local */
1756     if (dic->seq < ebp->fSeq ||
1757         dic->seq > ebp->lSeq)
1758         return NULL ; /* non-local */
1759
1760     /* now check if it is the return from
1761        a function call */
1762     if (dic->op == CALL || dic->op == PCALL ) {
1763         if (ic->op != SEND && ic->op != RETURN) {
1764             OP_SYMBOL(op)->ruonly = 1;
1765             return dic;
1766         }
1767         dic = dic->next ;
1768     }
1769
1770
1771     /* otherwise check that the definition does
1772        not contain any symbols in far space */
1773     if (isOperandInFarSpace(IC_LEFT(dic))  ||
1774         isOperandInFarSpace(IC_RIGHT(dic)) ||
1775         IS_OP_RUONLY(IC_LEFT(ic))          ||
1776         IS_OP_RUONLY(IC_RIGHT(ic)) )        {
1777         return NULL;
1778     }
1779
1780     /* if pointer set then make sure the pointer
1781        is one byte */
1782     if (POINTER_SET(dic) &&
1783         !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1784         return NULL ;
1785
1786     if (POINTER_GET(dic) &&
1787         !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1788         return NULL ;
1789
1790     sic = dic;
1791
1792     /* also make sure the intervenening instructions
1793        don't have any thing in far space */
1794     for (dic = dic->next ; dic && dic != ic ; dic = dic->next) {
1795
1796         /* if there is an intervening function call then no */
1797         if (dic->op == CALL || dic->op == PCALL)
1798                 return NULL;
1799         /* if pointer set then make sure the pointer
1800            is one byte */
1801         if (POINTER_SET(dic) &&
1802             !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1803             return NULL ;
1804
1805         if (POINTER_GET(dic) &&
1806             !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1807             return NULL ;
1808
1809         /* if address of & the result is remat the okay */
1810         if (dic->op == ADDRESS_OF &&
1811             OP_SYMBOL(IC_RESULT(dic))->remat)
1812             continue ;
1813
1814         /* if operand has size of three or more & this
1815            operation is a '*','/' or '%' then 'b' may
1816            cause a problem */
1817         if (( dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1818             getSize(operandType(op)) >= 3)
1819                 return NULL;
1820
1821         /* if left or right or result is in far space */
1822         if (isOperandInFarSpace(IC_LEFT(dic))   ||
1823             isOperandInFarSpace(IC_RIGHT(dic))  ||
1824             isOperandInFarSpace(IC_RESULT(dic)) ||
1825             IS_OP_RUONLY(IC_LEFT(dic))          ||
1826             IS_OP_RUONLY(IC_RIGHT(dic))         ||
1827             IS_OP_RUONLY(IC_RESULT(dic))            ) {
1828             return NULL;
1829         }
1830     }
1831
1832     OP_SYMBOL(op)->ruonly = 1;
1833     return sic;
1834
1835 }
1836
1837 /*-----------------------------------------------------------------*/
1838 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN          */
1839 /*-----------------------------------------------------------------*/
1840 static bool isBitwiseOptimizable (iCode *ic)
1841 {
1842     link *ltype = getSpec(operandType(IC_LEFT(ic)));
1843     link *rtype = getSpec(operandType(IC_RIGHT(ic)));
1844
1845     /* bitwise operations are considered optimizable
1846        under the following conditions (Jean-Louis VERN)
1847
1848        x & lit
1849        bit & bit
1850        bit & x
1851        bit ^ bit
1852        bit ^ x
1853        x   ^ lit
1854        x   | lit
1855        bit | bit
1856        bit | x
1857     */
1858     if ( IS_LITERAL(rtype) ||
1859          (IS_BITVAR(ltype) && IN_BITSPACE(SPEC_OCLS(ltype))))
1860         return TRUE ;
1861     else
1862         return FALSE ;
1863 }
1864
1865 /*-----------------------------------------------------------------*/
1866 /* packRegsForAccUse - pack registers for acc use                  */
1867 /*-----------------------------------------------------------------*/
1868 static void packRegsForAccUse (iCode *ic)
1869 {
1870     iCode *uic;
1871
1872     /* if + or - then it has to be one byte result */
1873     if ((ic->op == '+' || ic->op == '-')
1874         && getSize(operandType(IC_RESULT(ic))) > 1)
1875         return ;
1876
1877     /* if shift operation make sure right side is not a literal */
1878     if (ic->op == RIGHT_OP  &&
1879         ( isOperandLiteral(IC_RIGHT(ic)) ||
1880           getSize(operandType(IC_RESULT(ic))) > 1))
1881         return ;
1882
1883     if (ic->op == LEFT_OP &&
1884         ( isOperandLiteral(IC_RIGHT(ic)) ||
1885           getSize(operandType(IC_RESULT(ic))) > 1))
1886         return ;
1887
1888     if (IS_BITWISE_OP(ic) &&
1889         getSize(operandType(IC_RESULT(ic))) > 1)
1890         return ;
1891
1892
1893     /* has only one definition */
1894     if (bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1)
1895         return ;
1896
1897     /* has only one use */
1898     if (bitVectnBitsOn(OP_USES(IC_RESULT(ic))) > 1)
1899         return ;
1900
1901     /* and the usage immediately follows this iCode */
1902     if (!(uic = hTabItemWithKey(iCodehTab,
1903                                 bitVectFirstBit(OP_USES(IC_RESULT(ic))))))
1904         return ;
1905
1906     if (ic->next != uic)
1907         return ;
1908
1909     /* if it is a conditional branch then we definitely can */
1910     if (uic->op == IFX  )
1911         goto accuse;
1912
1913     if ( uic->op == JUMPTABLE )
1914         return ;
1915
1916     /* if the usage is not is an assignment
1917        or an arithmetic / bitwise / shift operation then not */
1918     if (POINTER_SET(uic) &&
1919         getSize(aggrToPtr(operandType(IC_RESULT(uic)),FALSE)) > 1)
1920         return;
1921
1922     if (uic->op != '=' &&
1923         !IS_ARITHMETIC_OP(uic) &&
1924         !IS_BITWISE_OP(uic)    &&
1925         uic->op != LEFT_OP &&
1926         uic->op != RIGHT_OP )
1927         return;
1928
1929     /* if used in ^ operation then make sure right is not a
1930        literl */
1931     if (uic->op == '^' && isOperandLiteral(IC_RIGHT(uic)))
1932         return ;
1933
1934     /* if shift operation make sure right side is not a literal */
1935     if (uic->op == RIGHT_OP  &&
1936         ( isOperandLiteral(IC_RIGHT(uic)) ||
1937           getSize(operandType(IC_RESULT(uic))) > 1))
1938         return ;
1939
1940     if (uic->op == LEFT_OP &&
1941         ( isOperandLiteral(IC_RIGHT(uic)) ||
1942           getSize(operandType(IC_RESULT(uic))) > 1))
1943         return ;
1944
1945     /* make sure that the result of this icode is not on the
1946        stack, since acc is used to compute stack offset */
1947     if (IS_TRUE_SYMOP(IC_RESULT(uic)) &&
1948         OP_SYMBOL(IC_RESULT(uic))->onStack)
1949         return ;
1950
1951     /* if either one of them in far space then we cannot */
1952     if ((IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1953          isOperandInFarSpace(IC_LEFT(uic))) ||
1954         (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1955          isOperandInFarSpace(IC_RIGHT(uic))))
1956         return ;
1957
1958     /* if the usage has only one operand then we can */
1959     if (IC_LEFT(uic) == NULL ||
1960         IC_RIGHT(uic) == NULL)
1961         goto accuse;
1962
1963     /* make sure this is on the left side if not
1964        a '+' since '+' is commutative */
1965     if (ic->op != '+' &&
1966         IC_LEFT(uic)->key != IC_RESULT(ic)->key)
1967         return;
1968
1969     /* if one of them is a literal then we can */
1970     if ((IC_LEFT(uic) && IS_OP_LITERAL(IC_LEFT(uic))) ||
1971         (IC_RIGHT(uic) && IS_OP_LITERAL(IC_RIGHT(uic)))) {
1972         OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
1973         return ;
1974     }
1975
1976     /* if the other one is not on stack then we can */
1977     if (IC_LEFT(uic)->key == IC_RESULT(ic)->key &&
1978         (IS_ITEMP(IC_RIGHT(uic)) ||
1979          (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1980           !OP_SYMBOL(IC_RIGHT(uic))->onStack)))
1981         goto accuse;
1982
1983     if (IC_RIGHT(uic)->key == IC_RESULT(ic)->key &&
1984         (IS_ITEMP(IC_LEFT(uic)) ||
1985          (IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1986           !OP_SYMBOL(IC_LEFT(uic))->onStack)))
1987         goto accuse ;
1988
1989     return ;
1990
1991  accuse:
1992     OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
1993
1994
1995 }
1996
1997 /*-----------------------------------------------------------------*/
1998 /* packForPush - hueristics to reduce iCode for pushing            */
1999 /*-----------------------------------------------------------------*/
2000 static void packForPush(iCode *ic, eBBlock *ebp)
2001 {
2002     iCode *dic;
2003
2004     if (ic->op != IPUSH || !IS_ITEMP(IC_LEFT(ic)))
2005         return ;
2006
2007     /* must have only definition & one usage */
2008     if (bitVectnBitsOn(OP_DEFS(IC_LEFT(ic))) != 1 ||
2009         bitVectnBitsOn(OP_USES(IC_LEFT(ic))) != 1 )
2010         return ;
2011
2012     /* find the definition */
2013     if (!(dic = hTabItemWithKey(iCodehTab,
2014                                 bitVectFirstBit(OP_DEFS(IC_LEFT(ic))))))
2015         return ;
2016
2017     if (dic->op != '=' || POINTER_SET(dic))
2018         return;
2019
2020     /* we now we know that it has one & only one def & use
2021        and the that the definition is an assignment */
2022     IC_LEFT(ic) = IC_RIGHT(dic);
2023
2024     remiCodeFromeBBlock(ebp,dic);
2025     hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
2026 }
2027
2028 /*-----------------------------------------------------------------*/
2029 /* packRegisters - does some transformations to reduce register    */
2030 /*                   pressure                                      */
2031 /*-----------------------------------------------------------------*/
2032 static void packRegisters (eBBlock *ebp)
2033 {
2034     iCode *ic ;
2035     int change = 0 ;
2036
2037     while (1) {
2038
2039         change = 0;
2040
2041         /* look for assignments of the form */
2042         /* iTempNN = TRueSym (someoperation) SomeOperand */
2043         /*       ....                       */
2044         /* TrueSym := iTempNN:1             */
2045         for ( ic = ebp->sch ; ic ; ic = ic->next ) {
2046
2047
2048             /* find assignment of the form TrueSym := iTempNN:1 */
2049             if (ic->op == '=' && !POINTER_SET(ic))
2050                 change += packRegsForAssign(ic,ebp);
2051         }
2052
2053         if (!change)
2054             break;
2055     }
2056
2057     for ( ic = ebp->sch ; ic ; ic = ic->next ) {
2058
2059         /* if this is an itemp & result of a address of a true sym
2060            then mark this as rematerialisable   */
2061         if (ic->op == ADDRESS_OF &&
2062             IS_ITEMP(IC_RESULT(ic)) &&
2063             IS_TRUE_SYMOP(IC_LEFT(ic)) &&
2064             bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2065             !OP_SYMBOL(IC_LEFT(ic))->onStack ) {
2066
2067             OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2068             OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2069             OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2070
2071         }
2072
2073         /* if straight assignment then carry remat flag if
2074            this is the only definition */
2075         if (ic->op == '='    &&
2076             !POINTER_SET(ic) &&
2077             IS_SYMOP(IC_RIGHT(ic)) &&
2078             OP_SYMBOL(IC_RIGHT(ic))->remat &&
2079             bitVectnBitsOn(OP_SYMBOL(IC_RESULT(ic))->defs) <= 1) {
2080
2081             OP_SYMBOL(IC_RESULT(ic))->remat =
2082                 OP_SYMBOL(IC_RIGHT(ic))->remat;
2083             OP_SYMBOL(IC_RESULT(ic))->rematiCode =
2084                 OP_SYMBOL(IC_RIGHT(ic))->rematiCode ;
2085         }
2086
2087         /* if this is a +/- operation with a rematerizable
2088            then mark this as rematerializable as well only
2089            if the literal value is within the range -255 and + 255
2090            the assembler cannot handle it other wise */
2091         if ((ic->op == '+' || ic->op == '-') &&
2092
2093             (IS_SYMOP(IC_LEFT(ic)) &&
2094              IS_ITEMP(IC_RESULT(ic)) &&
2095              OP_SYMBOL(IC_LEFT(ic))->remat &&
2096              bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2097              IS_OP_LITERAL(IC_RIGHT(ic))) ) {
2098
2099             int i = operandLitValue(IC_RIGHT(ic));
2100             if ( i < 255 && i > -255) {
2101                 OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2102                 OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2103                 OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2104             }
2105         }
2106
2107         /* mark the pointer usages */
2108         if (POINTER_SET(ic))
2109             OP_SYMBOL(IC_RESULT(ic))->uptr = 1;
2110
2111         if (POINTER_GET(ic))
2112             OP_SYMBOL(IC_LEFT(ic))->uptr = 1;
2113
2114         if (!SKIP_IC2(ic)) {
2115             /* if we are using a symbol on the stack
2116                then we should say mcs51_ptrRegReq */
2117             if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
2118                 mcs51_ptrRegReq += ((OP_SYMBOL(IC_COND(ic))->onStack ||
2119                                OP_SYMBOL(IC_COND(ic))->iaccess) ? 1 : 0);
2120             else
2121                 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
2122                     mcs51_ptrRegReq += ((OP_SYMBOL(IC_JTCOND(ic))->onStack ||
2123                                    OP_SYMBOL(IC_JTCOND(ic))->iaccess) ? 1 : 0);
2124                 else {
2125                     if (IS_SYMOP(IC_LEFT(ic)))
2126                         mcs51_ptrRegReq += ((OP_SYMBOL(IC_LEFT(ic))->onStack ||
2127                                        OP_SYMBOL(IC_LEFT(ic))->iaccess) ? 1 : 0);
2128                     if (IS_SYMOP(IC_RIGHT(ic)))
2129                         mcs51_ptrRegReq += ((OP_SYMBOL(IC_RIGHT(ic))->onStack ||
2130                                        OP_SYMBOL(IC_RIGHT(ic))->iaccess) ? 1 : 0);
2131                     if (IS_SYMOP(IC_RESULT(ic)))
2132                         mcs51_ptrRegReq += ((OP_SYMBOL(IC_RESULT(ic))->onStack ||
2133                                        OP_SYMBOL(IC_RESULT(ic))->iaccess) ? 1 : 0);
2134                 }
2135         }
2136
2137         /* if the condition of an if instruction
2138            is defined in the previous instruction then
2139            mark the itemp as a conditional */
2140         if ((IS_CONDITIONAL(ic) ||
2141              ( ( ic->op == BITWISEAND      ||
2142                  ic->op == '|'             ||
2143                  ic->op == '^' ) &&
2144                isBitwiseOptimizable(ic))) &&
2145             ic->next && ic->next->op == IFX &&
2146             isOperandEqual(IC_RESULT(ic),IC_COND(ic->next)) &&
2147             OP_SYMBOL(IC_RESULT(ic))->liveTo <= ic->next->seq) {
2148
2149             OP_SYMBOL(IC_RESULT(ic))->regType = REG_CND;
2150             continue ;
2151         }
2152
2153         /* reduce for support function calls */
2154         if (ic->supportRtn || ic->op == '+' || ic->op == '-' )
2155             packRegsForSupport (ic,ebp);
2156
2157         /* some cases the redundant moves can
2158            can be eliminated for return statements */
2159         if ((ic->op == RETURN || ic->op == SEND) &&
2160             !isOperandInFarSpace(IC_LEFT(ic))    &&
2161             !options.model)
2162             packRegsForOneuse (ic,IC_LEFT(ic),ebp);
2163
2164         /* if pointer set & left has a size more than
2165            one and right is not in far space */
2166         if (POINTER_SET(ic)                    &&
2167             !isOperandInFarSpace(IC_RIGHT(ic)) &&
2168             !OP_SYMBOL(IC_RESULT(ic))->remat   &&
2169             !IS_OP_RUONLY(IC_RIGHT(ic))        &&
2170             getSize(aggrToPtr(operandType(IC_RESULT(ic)),FALSE)) > 1 )
2171
2172             packRegsForOneuse (ic,IC_RESULT(ic),ebp);
2173
2174         /* if pointer get */
2175         if (POINTER_GET(ic)                    &&
2176             !isOperandInFarSpace(IC_RESULT(ic))&&
2177             !OP_SYMBOL(IC_LEFT(ic))->remat     &&
2178             !IS_OP_RUONLY(IC_RESULT(ic))         &&
2179             getSize(aggrToPtr(operandType(IC_LEFT(ic)),FALSE)) > 1 )
2180
2181             packRegsForOneuse (ic,IC_LEFT(ic),ebp);
2182
2183
2184         /* if this is cast for intergral promotion then
2185            check if only use of  the definition of the
2186            operand being casted/ if yes then replace
2187            the result of that arithmetic operation with
2188            this result and get rid of the cast */
2189         if (ic->op == CAST) {
2190             link *fromType = operandType(IC_RIGHT(ic));
2191             link *toType = operandType(IC_LEFT(ic));
2192
2193             if (IS_INTEGRAL(fromType) && IS_INTEGRAL(toType) &&
2194                 getSize(fromType) != getSize(toType) ) {
2195
2196                 iCode *dic = packRegsForOneuse(ic,IC_RIGHT(ic),ebp);
2197                 if (dic) {
2198                     if (IS_ARITHMETIC_OP(dic)) {
2199                         IC_RESULT(dic) = IC_RESULT(ic);
2200                         remiCodeFromeBBlock(ebp,ic);
2201                         hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2202                         ic = ic->prev;
2203                     } else
2204                         OP_SYMBOL(IC_RIGHT(ic))->ruonly =  0;
2205                 }
2206             } else {
2207
2208                 /* if the type from and type to are the same
2209                    then if this is the only use then packit */
2210                 if (checkType(operandType(IC_RIGHT(ic)),
2211                               operandType(IC_LEFT(ic))) == 1) {
2212                     iCode *dic = packRegsForOneuse (ic,IC_RIGHT(ic),ebp);
2213                     if (dic) {
2214                         IC_RESULT(dic) = IC_RESULT(ic);
2215                         remiCodeFromeBBlock(ebp,ic);
2216                         hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2217                         ic = ic->prev;
2218                     }
2219                 }
2220             }
2221         }
2222
2223         /* pack for PUSH
2224            iTempNN := (some variable in farspace) V1
2225            push iTempNN ;
2226            -------------
2227            push V1
2228         */
2229         if (ic->op == IPUSH ) {
2230             packForPush(ic,ebp);
2231         }
2232
2233
2234         /* pack registers for accumulator use, when the
2235            result of an arithmetic or bit wise operation
2236            has only one use, that use is immediately following
2237            the defintion and the using iCode has only one
2238            operand or has two operands but one is literal &
2239            the result of that operation is not on stack then
2240            we can leave the result of this operation in acc:b
2241            combination */
2242         if ((IS_ARITHMETIC_OP(ic)
2243
2244              || IS_BITWISE_OP(ic)
2245
2246              || ic->op == LEFT_OP || ic->op == RIGHT_OP
2247
2248              ) &&
2249             IS_ITEMP(IC_RESULT(ic)) &&
2250             getSize(operandType(IC_RESULT(ic))) <= 2)
2251
2252             packRegsForAccUse (ic);
2253
2254     }
2255 }
2256
2257 /*-----------------------------------------------------------------*/
2258 /* assignRegisters - assigns registers to each live range as need  */
2259 /*-----------------------------------------------------------------*/
2260 void mcs51_assignRegisters (eBBlock **ebbs, int count)
2261 {
2262     iCode *ic;
2263     int i ;
2264
2265     setToNull((void *)&_G.funcrUsed);
2266     mcs51_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2267     /* if not register extentions then reduce number
2268        of registers */
2269     if (options.regExtend)
2270         mcs51_nRegs = 13;
2271     else
2272         mcs51_nRegs = 8;
2273
2274     /* change assignments this will remove some
2275        live ranges reducing some register pressure */
2276     for (i = 0 ; i < count ;i++ )
2277         packRegisters (ebbs[i]);
2278
2279     if (options.dump_pack)
2280         dumpEbbsToFileExt(".dumppack",ebbs,count);
2281
2282     /* first determine for each live range the number of
2283        registers & the type of registers required for each */
2284     regTypeNum ();
2285
2286     /* and serially allocate registers */
2287     serialRegAssign(ebbs,count);
2288
2289     /* if stack was extended then tell the user */
2290     if (_G.stackExtend) {
2291 /*      werror(W_TOOMANY_SPILS,"stack", */
2292 /*             _G.stackExtend,currFunc->name,""); */
2293         _G.stackExtend = 0 ;
2294     }
2295
2296     if (_G.dataExtend) {
2297 /*      werror(W_TOOMANY_SPILS,"data space", */
2298 /*             _G.dataExtend,currFunc->name,""); */
2299         _G.dataExtend = 0 ;
2300     }
2301
2302     /* after that create the register mask
2303        for each of the instruction */
2304     createRegMask (ebbs,count);
2305
2306     /* redo that offsets for stacked automatic variables */
2307     redoStackOffsets ();
2308
2309     if (options.dump_rassgn)
2310         dumpEbbsToFileExt(".dumprassgn",ebbs,count);
2311
2312     /* now get back the chain */
2313     ic = iCodeLabelOptimize(iCodeFromeBBlock (ebbs,count));
2314
2315
2316     gen51Code(ic);
2317
2318     /* free up any _G.stackSpil locations allocated */
2319     applyToSet(_G.stackSpil,deallocStackSpil);
2320     _G.slocNum = 0;
2321     setToNull((void **)&_G.stackSpil);
2322     setToNull((void **)&_G.spiltSet);
2323     /* mark all registers as free */
2324     freeAllRegs();
2325
2326     return ;
2327 }