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

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