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