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