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