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

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