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

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