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 if  (result->regType == REG_SCR)
 885                             result->regs[i] = getRegScr(ic,ebp,result);
 886                     else
 887                             result->regs[i] = getRegGpr (ic,ebp,result);
 888
 889                 _G.regAssigned = bitVectSetBit(_G.regAssigned,result->key);
 890
 891             }
 892
 893             /* free the remaining */
 894             for (; i < sym->nRegs ; i++) {
 895                 if (psym) {
 896                     if (!symHasReg(psym,sym->regs[i]))
 897                         freeReg(sym->regs[i]);
 898                 } else
 899                     freeReg(sym->regs[i]);
 900             }
 901         }
 902     }
 903 }
 904
 905
 906 /*-----------------------------------------------------------------*/
 907 /* reassignLR - reassign this to registers                         */
 908 /*-----------------------------------------------------------------*/
 909 static void reassignLR (operand *op)
 910 {
 911     symbol *sym = OP_SYMBOL(op);
 912     int i;
 913
 914     /* not spilt any more */
 915     sym->isspilt = sym->blockSpil  = sym->remainSpil = 0;
 916     bitVectUnSetBit(_G.spiltSet,sym->key);
 917
 918     _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
 919
 920     _G.blockSpil--;
 921
 922     for (i=0;i<sym->nRegs;i++)
 923         sym->regs[i]->isFree = 0;
 924 }
 925
 926 /*-----------------------------------------------------------------*/
 927 /* willCauseSpill - determines if allocating will cause a spill    */
 928 /*-----------------------------------------------------------------*/
 929 static int willCauseSpill ( int nr, int rt)
 930 {
 931     /* first check if there are any avlb registers
 932        of te type required */
 933     if (rt == REG_PTR) {
 934         /* special case for pointer type
 935            if pointer type not avlb then
 936            check for type gpr */
 937         if (nFreeRegs(rt) >= nr)
 938             return 0;
 939         if (nFreeRegs(REG_GPR) >= nr)
 940             return 0;
 941     } else {
 942         if (avr_ptrRegReq) {
 943             if (nFreeRegs(rt) >= nr)
 944                 return 0;
 945         } else {
 946             if (nFreeRegs(REG_PTR) +
 947                 nFreeRegs(REG_GPR) >= nr)
 948                 return 0;
 949         }
 950     }
 951
 952     /* it will cause a spil */
 953     return 1;
 954 }
 955
 956 /*-----------------------------------------------------------------*/
 957 /* positionRegs - the allocator can allocate same registers to res-*/
 958 /* ult and operand, if this happens make sure they are in the same */
 959 /* position as the operand otherwise chaos results                 */
 960 /*-----------------------------------------------------------------*/
 961 static void positionRegs (symbol *result, symbol *opsym, int lineno)
 962 {
 963     int count = min(result->nRegs,opsym->nRegs);
 964     int i , j = 0, shared = 0;
 965
 966     /* if the result has been spilt then cannot share */
 967     if (opsym->isspilt)
 968         return ;
 969  again:
 970     shared = 0;
 971     /* first make sure that they actually share */
 972     for ( i = 0 ; i < count; i++ ) {
 973         for (j = 0 ; j < count ; j++ ) {
 974             if (result->regs[i] == opsym->regs[j] && i !=j) {
 975                 shared = 1;
 976                 goto xchgPositions;
 977             }
 978         }
 979     }
 980  xchgPositions:
 981     if (shared) {
 982         regs *tmp = result->regs[i];
 983         result->regs[i] = result->regs[j];
 984         result->regs[j] = tmp;
 985         goto again;
 986     }
 987 }
 988
 989 /*-----------------------------------------------------------------*/
 990 /* serialRegAssign - serially allocate registers to the variables  */
 991 /*-----------------------------------------------------------------*/
 992 static void serialRegAssign (eBBlock **ebbs, int count)
 993 {
 994     int i;
 995
 996     /* for all blocks */
 997     for (i = 0; i < count ; i++ ) {
 998
 999         iCode *ic;
1000
1001         if (ebbs[i]->noPath &&
1002             (ebbs[i]->entryLabel != entryLabel &&
1003              ebbs[i]->entryLabel != returnLabel ))
1004             continue ;
1005
1006         /* of all instructions do */
1007         for (ic = ebbs[i]->sch ; ic ; ic = ic->next) {
1008
1009             /* if this is an ipop that means some live
1010                range will have to be assigned again */
1011             if (ic->op == IPOP)
1012                 reassignLR (IC_LEFT(ic));
1013
1014             /* if result is present && is a true symbol */
1015             if (IC_RESULT(ic) && ic->op != IFX &&
1016                 IS_TRUE_SYMOP(IC_RESULT(ic)))
1017                 OP_SYMBOL(IC_RESULT(ic))->allocreq = 1;
1018
1019             /* take away registers from live
1020                ranges that end at this instruction */
1021             deassignLRs (ic, ebbs[i]) ;
1022
1023             /* some don't need registers */
1024             if (SKIP_IC2(ic) ||
1025                 ic->op == JUMPTABLE ||
1026                 ic->op == IFX ||
1027                 ic->op == IPUSH ||
1028                 ic->op == IPOP ||
1029                 (IC_RESULT(ic) &&POINTER_SET(ic)) )
1030                 continue;
1031
1032             /* now we need to allocate registers
1033                only for the result */
1034             if (IC_RESULT(ic)) {
1035                 symbol *sym = OP_SYMBOL(IC_RESULT(ic));
1036                 bitVect *spillable;
1037                 int willCS ;
1038                 int j;
1039
1040                 /* if it does not need or is spilt
1041                    or is already assigned to registers
1042                    or will not live beyond this instructions */
1043                 if (!sym->nRegs      ||
1044                     sym->isspilt     ||
1045                     bitVectBitValue(_G.regAssigned,sym->key) ||
1046                     sym->liveTo <= ic->seq)
1047                     continue ;
1048
1049                 /* if some liverange has been spilt at the block level
1050                    and this one live beyond this block then spil this
1051                    to be safe */
1052                 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq) {
1053                     spillThis (sym);
1054                     continue ;
1055                 }
1056                 /* if trying to allocate this will cause
1057                    a spill and there is nothing to spill
1058                    or this one is rematerializable then
1059                    spill this one */
1060                 willCS = willCauseSpill(sym->nRegs,sym->regType);
1061                 spillable = computeSpillable(ic);
1062                 if ( sym->remat ||
1063                     (willCS  && bitVectIsZero(spillable) ) ) {
1064
1065                     spillThis (sym) ;
1066                     continue ;
1067
1068                 }
1069
1070                 /* if it has a spillocation & is used less than
1071                    all other live ranges then spill this */
1072                 if ( willCS && sym->usl.spillLoc ) {
1073
1074                     symbol *leastUsed =
1075                         leastUsedLR(liveRangesWith (spillable ,
1076                                                     allLRs,
1077                                                     ebbs[i],
1078                                                     ic));
1079                     if (leastUsed &&
1080                         leastUsed->used > sym->used) {
1081                         spillThis (sym);
1082                         continue;
1083                     }
1084                 }
1085
1086                 /* we assign registers to it */
1087                 _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
1088
1089                 for (j = 0 ; j < sym->nRegs ;j++ ) {
1090                     if (sym->regType == REG_PTR)
1091                         sym->regs[j] = getRegPtr(ic,ebbs[i],sym);
1092                     else if (sym->regType == REG_SCR)
1093                         sym->regs[j] = getRegScr(ic,ebbs[i],sym);
1094                     else
1095                         sym->regs[j] = getRegGpr(ic,ebbs[i],sym);
1096
1097                     /* if the allocation falied which means
1098                        this was spilt then break */
1099                     if (!sym->regs[j])
1100                         break;
1101                 }
1102                 /* if it shares registers with operands make sure
1103                    that they are in the same position */
1104                 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic)) &&
1105                     OP_SYMBOL(IC_LEFT(ic))->nRegs  && ic->op != '=')
1106                         positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1107                                      OP_SYMBOL(IC_LEFT(ic)),ic->lineno);
1108                 /* do the same for the right operand */
1109                 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic)) &&
1110                     OP_SYMBOL(IC_RIGHT(ic))->nRegs )
1111                         positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1112                                      OP_SYMBOL(IC_RIGHT(ic)),ic->lineno);
1113
1114             }
1115         }
1116     }
1117 }
1118
1119 /*-----------------------------------------------------------------*/
1120 /* rUmaskForOp :- returns register mask for an operand             */
1121 /*-----------------------------------------------------------------*/
1122 static bitVect *rUmaskForOp (operand *op)
1123 {
1124     bitVect *rumask;
1125     symbol *sym;
1126     int j;
1127
1128     /* only temporaries are assigned registers */
1129     if (!IS_ITEMP(op))
1130         return NULL;
1131
1132     sym = OP_SYMBOL(op);
1133
1134     /* if spilt or no registers assigned to it
1135        then nothing */
1136     if (sym->isspilt || !sym->nRegs)
1137         return NULL;
1138
1139     rumask = newBitVect(avr_nRegs);
1140
1141     for (j = 0; j < sym->nRegs; j++) {
1142         rumask = bitVectSetBit(rumask,
1143                                sym->regs[j]->rIdx);
1144     }
1145
1146     return rumask;
1147 }
1148
1149 /*-----------------------------------------------------------------*/
1150 /* regsUsedIniCode :- returns bit vector of registers used in iCode*/
1151 /*-----------------------------------------------------------------*/
1152 static bitVect *regsUsedIniCode (iCode *ic)
1153 {
1154     bitVect *rmask = newBitVect(avr_nRegs);
1155
1156     /* do the special cases first */
1157     if (ic->op == IFX ) {
1158         rmask = bitVectUnion(rmask,
1159                              rUmaskForOp(IC_COND(ic)));
1160         goto ret;
1161     }
1162
1163     /* for the jumptable */
1164     if (ic->op == JUMPTABLE) {
1165         rmask = bitVectUnion(rmask,
1166                              rUmaskForOp(IC_JTCOND(ic)));
1167
1168         goto ret;
1169     }
1170
1171     /* of all other cases */
1172     if (IC_LEFT(ic))
1173         rmask = bitVectUnion(rmask,
1174                              rUmaskForOp(IC_LEFT(ic)));
1175
1176
1177     if (IC_RIGHT(ic))
1178         rmask = bitVectUnion(rmask,
1179                              rUmaskForOp(IC_RIGHT(ic)));
1180
1181     if (IC_RESULT(ic))
1182         rmask = bitVectUnion(rmask,
1183                              rUmaskForOp(IC_RESULT(ic)));
1184
1185  ret:
1186     return rmask;
1187 }
1188
1189 /*-----------------------------------------------------------------*/
1190 /* createRegMask - for each instruction will determine the regsUsed*/
1191 /*-----------------------------------------------------------------*/
1192 static void createRegMask (eBBlock **ebbs, int count)
1193 {
1194     int i;
1195
1196     /* for all blocks */
1197     for (i = 0; i < count ; i++ ) {
1198         iCode *ic ;
1199
1200         if ( ebbs[i]->noPath &&
1201              ( ebbs[i]->entryLabel != entryLabel &&
1202                ebbs[i]->entryLabel != returnLabel ))
1203             continue ;
1204
1205         /* for all instructions */
1206         for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
1207
1208             int j;
1209
1210             if (SKIP_IC2(ic) || !ic->rlive)
1211                 continue ;
1212
1213             /* first mark the registers used in this
1214                instruction */
1215             ic->rUsed = regsUsedIniCode(ic);
1216             _G.funcrUsed = bitVectUnion(_G.funcrUsed,ic->rUsed);
1217
1218             /* now create the register mask for those
1219                registers that are in use : this is a
1220                super set of ic->rUsed */
1221             ic->rMask = newBitVect(avr_nRegs+1);
1222
1223             /* for all live Ranges alive at this point */
1224             for (j = 1; j < ic->rlive->size; j++ ) {
1225                 symbol *sym;
1226                 int k;
1227
1228                 /* if not alive then continue */
1229                 if (!bitVectBitValue(ic->rlive,j))
1230                     continue ;
1231
1232                 /* find the live range we are interested in */
1233                 if (!(sym = hTabItemWithKey(liveRanges,j))) {
1234                     werror (E_INTERNAL_ERROR,__FILE__,__LINE__,
1235                             "createRegMask cannot find live range");
1236                     exit(0);
1237                 }
1238
1239                 /* if no register assigned to it */
1240                 if (!sym->nRegs || sym->isspilt)
1241                     continue ;
1242
1243                 /* for all the registers allocated to it */
1244                 for (k = 0 ; k < sym->nRegs ;k++) {
1245                     if (sym->regs[k]) {
1246                         ic->rMask =
1247                             bitVectSetBit(ic->rMask,sym->regs[k]->rIdx);
1248                         /* special case for X & Z registers */
1249                         if (k == R26_IDX || k == R27_IDX)
1250                             ic->rMask = bitVectSetBit(ic->rMask,X_IDX);
1251                         if (k == R30_IDX || k == R31_IDX)
1252                             ic->rMask = bitVectSetBit(ic->rMask,Z_IDX);
1253                     }
1254                 }
1255             }
1256         }
1257     }
1258 }
1259
1260 /*-----------------------------------------------------------------*/
1261 /* rematStr - returns the rematerialized string for a remat var    */
1262 /*-----------------------------------------------------------------*/
1263 static char *rematStr (symbol *sym)
1264 {
1265     char *s = buffer;
1266     iCode *ic = sym->rematiCode;
1267
1268     while (1) {
1269
1270         /* if plus or minus print the right hand side */
1271         if (ic->op == '+' || ic->op == '-') {
1272             sprintf(s,"0x%04x %c ",(int) operandLitValue(IC_RIGHT(ic)),
1273                     ic->op );
1274             s += strlen(s);
1275             ic = OP_SYMBOL(IC_LEFT(ic))->rematiCode;
1276             continue ;
1277         }
1278
1279         /* we reached the end */
1280         sprintf(s,"%s",OP_SYMBOL(IC_LEFT(ic))->rname);
1281         break;
1282     }
1283
1284     return buffer ;
1285 }
1286
1287 /*-----------------------------------------------------------------*/
1288 /* regTypeNum - computes the type & number of registers required   */
1289 /*-----------------------------------------------------------------*/
1290 static void regTypeNum ()
1291 {
1292     symbol *sym;
1293     int k;
1294     iCode *ic;
1295
1296     /* for each live range do */
1297     for ( sym = hTabFirstItem(liveRanges,&k); sym ;
1298           sym = hTabNextItem(liveRanges,&k)) {
1299
1300         /* if used zero times then no registers needed */
1301         if ((sym->liveTo - sym->liveFrom) == 0)
1302             continue ;
1303
1304
1305         /* if the live range is a temporary */
1306         if (sym->isitmp) {
1307
1308             /* if the type is marked as a conditional */
1309             if (sym->regType == REG_CND)
1310                 continue ;
1311
1312             /* if used in return only then we don't
1313                need registers */
1314             if (sym->ruonly || sym->accuse) {
1315                 if (IS_AGGREGATE(sym->type) || sym->isptr)
1316                     sym->type = aggrToPtr(sym->type,FALSE);
1317                 continue ;
1318             }
1319
1320             /* if the symbol has only one definition &
1321                that definition is a get_pointer and the
1322                pointer we are getting is rematerializable and
1323                in "data" space */
1324
1325             if (bitVectnBitsOn(sym->defs) == 1 &&
1326                 (ic = hTabItemWithKey(iCodehTab,
1327                                       bitVectFirstBit(sym->defs))) &&
1328                 POINTER_GET(ic) &&
1329                 !IS_BITVAR(sym->etype)) {
1330
1331                 /* if in data space or idata space then try to
1332                    allocate pointer register */
1333
1334             }
1335
1336             /* if not then we require registers */
1337             sym->nRegs = ((IS_AGGREGATE(sym->type) || sym->isptr ) ?
1338                           getSize(sym->type = aggrToPtr(sym->type,FALSE)) :
1339                           getSize(sym->type));
1340
1341             if (sym->nRegs > 4) {
1342                 fprintf(stderr,"allocated more than 4 or 0 registers for type ");
1343                 printTypeChain(sym->type,stderr);fprintf(stderr,"\n");
1344             }
1345
1346             /* determine the type of register required */
1347             if (sym->nRegs == 2   && /* size is two */
1348                 IS_PTR(sym->type) && /* is a pointer */
1349                 sym->uptr)   {        /* has pointer usage i.e. get/set pointer */
1350                 sym->regType = REG_PTR ;
1351                 avr_ptrRegReq++;
1352             }
1353             else {
1354                 /* live accross a function call then gpr else scratch */
1355                 if (sym->isLiveFcall)
1356                     sym->regType = REG_GPR ;
1357                 else
1358                     sym->regType = REG_SCR ;
1359             }
1360         } else
1361             /* for the first run we don't provide */
1362             /* registers for true symbols we will */
1363             /* see how things go                  */
1364             sym->nRegs = 0 ;
1365     }
1366
1367 }
1368
1369 /*-----------------------------------------------------------------*/
1370 /* deallocStackSpil - this will set the stack pointer back         */
1371 /*-----------------------------------------------------------------*/
1372 static DEFSETFUNC(deallocStackSpil)
1373 {
1374     symbol *sym = item;
1375
1376     deallocLocal(sym);
1377     return 0;
1378 }
1379
1380 /*-----------------------------------------------------------------*/
1381 /* farSpacePackable - returns the packable icode for far variables */
1382 /*-----------------------------------------------------------------*/
1383 static iCode *farSpacePackable (iCode *ic)
1384 {
1385     iCode *dic ;
1386
1387     /* go thru till we find a definition for the
1388        symbol on the right */
1389     for ( dic = ic->prev ; dic ; dic = dic->prev) {
1390
1391         /* if the definition is a call then no */
1392         if ((dic->op == CALL || dic->op == PCALL) &&
1393             IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1394             return NULL;
1395         }
1396
1397         /* if shift by unknown amount then not */
1398         if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1399             IC_RESULT(dic)->key == IC_RIGHT(ic)->key)
1400             return NULL;
1401
1402         /* if pointer get and size > 1 */
1403         if (POINTER_GET(dic) &&
1404             getSize(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)) > 1)
1405             return NULL ;
1406
1407         if (POINTER_SET(dic) &&
1408             getSize(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)) > 1)
1409             return NULL ;
1410
1411         /* if any three is a true symbol in far space */
1412         if (IC_RESULT(dic) &&
1413             IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1414             isOperandInFarSpace(IC_RESULT(dic)))
1415             return NULL;
1416
1417         if (IC_RIGHT(dic) &&
1418             IS_TRUE_SYMOP(IC_RIGHT(dic)) &&
1419             isOperandInFarSpace(IC_RIGHT(dic)) &&
1420             !isOperandEqual(IC_RIGHT(dic),IC_RESULT(ic)))
1421             return NULL;
1422
1423         if (IC_LEFT(dic) &&
1424             IS_TRUE_SYMOP(IC_LEFT(dic)) &&
1425             isOperandInFarSpace(IC_LEFT(dic)) &&
1426             !isOperandEqual(IC_LEFT(dic),IC_RESULT(ic)))
1427             return NULL;
1428
1429         if (isOperandEqual(IC_RIGHT(ic),IC_RESULT(dic))) {
1430             if ( (dic->op == LEFT_OP  ||
1431                   dic->op == RIGHT_OP ||
1432                   dic->op == '-') &&
1433                  IS_OP_LITERAL(IC_RIGHT(dic)))
1434                 return NULL;
1435             else
1436                 return dic;
1437         }
1438     }
1439
1440     return NULL;
1441 }
1442
1443 /*-----------------------------------------------------------------*/
1444 /* packRegsForAssign - register reduction for assignment           */
1445 /*-----------------------------------------------------------------*/
1446 static int packRegsForAssign (iCode *ic,eBBlock *ebp)
1447 {
1448     iCode *dic, *sic;
1449
1450     if (!IS_ITEMP(IC_RIGHT(ic))       ||
1451         OP_SYMBOL(IC_RIGHT(ic))->isind ||
1452         OP_LIVETO(IC_RIGHT(ic)) > ic->seq) {
1453         return 0;
1454     }
1455
1456     /* find the definition of iTempNN scanning backwards if we find a
1457        a use of the true symbol in before we find the definition then
1458        we cannot */
1459     for ( dic = ic->prev ; dic ; dic = dic->prev) {
1460
1461         /* if there is a function call and this is
1462            a parameter & not my parameter then don't pack it */
1463         if ( (dic->op == CALL || dic->op == PCALL) &&
1464              (OP_SYMBOL(IC_RESULT(ic))->_isparm &&
1465               !OP_SYMBOL(IC_RESULT(ic))->ismyparm)) {
1466             dic = NULL;
1467             break;
1468         }
1469
1470         if (SKIP_IC2(dic))
1471             continue;
1472
1473         if (IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1474             IS_OP_VOLATILE(IC_RESULT(dic))) {
1475                 dic = NULL;
1476                 break;
1477         }
1478
1479         if (IS_SYMOP(IC_RESULT(dic)) &&
1480             IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1481             if (POINTER_SET(dic))
1482                 dic = NULL;
1483
1484             break;
1485         }
1486
1487         if (IS_SYMOP(IC_RIGHT(dic)) &&
1488             (IC_RIGHT(dic)->key == IC_RESULT(ic)->key ||
1489              IC_RIGHT(dic)->key == IC_RIGHT(ic)->key)) {
1490             dic = NULL;
1491             break;
1492         }
1493
1494         if (IS_SYMOP(IC_LEFT(dic)) &&
1495             (IC_LEFT(dic)->key == IC_RESULT(ic)->key ||
1496              IC_LEFT(dic)->key == IC_RIGHT(ic)->key)) {
1497             dic = NULL;
1498             break;
1499         }
1500
1501         if (POINTER_SET(dic) &&
1502             IC_RESULT(dic)->key == IC_RESULT(ic)->key ) {
1503             dic = NULL ;
1504             break;
1505         }
1506     }
1507
1508     if (!dic)
1509         return 0 ; /* did not find */
1510
1511     /* if the result is on stack or iaccess then it must be
1512        the same atleast one of the operands */
1513     if (OP_SYMBOL(IC_RESULT(ic))->onStack  ||
1514         OP_SYMBOL(IC_RESULT(ic))->iaccess ) {
1515
1516         /* the operation has only one symbol
1517            operator then we can pack */
1518         if ((IC_LEFT(dic) && !IS_SYMOP(IC_LEFT(dic))) ||
1519             (IC_RIGHT(dic) && !IS_SYMOP(IC_RIGHT(dic))))
1520             goto pack;
1521
1522         if (!((IC_LEFT(dic) &&
1523              IC_RESULT(ic)->key == IC_LEFT(dic)->key) ||
1524               (IC_RIGHT(dic) &&
1525                IC_RESULT(ic)->key == IC_RIGHT(dic)->key)))
1526             return 0;
1527     }
1528 pack:
1529     /* if in far space & tru symbol then don't */
1530     if ((IS_TRUE_SYMOP(IC_RESULT(ic))) && isOperandInFarSpace(IC_RESULT(ic)))
1531         return 0;
1532     /* found the definition */
1533     /* replace the result with the result of */
1534     /* this assignment and remove this assignment */
1535     IC_RESULT(dic) = IC_RESULT(ic) ;
1536
1537     if (IS_ITEMP(IC_RESULT(dic)) && OP_SYMBOL(IC_RESULT(dic))->liveFrom > dic->seq) {
1538             OP_SYMBOL(IC_RESULT(dic))->liveFrom = dic->seq;
1539     }
1540     /* delete from liverange table also
1541        delete from all the points inbetween and the new
1542        one */
1543     for ( sic = dic; sic != ic ; sic = sic->next ) {
1544         bitVectUnSetBit(sic->rlive,IC_RESULT(ic)->key);
1545         if (IS_ITEMP(IC_RESULT(dic)))
1546             bitVectSetBit(sic->rlive,IC_RESULT(dic)->key);
1547     }
1548
1549     remiCodeFromeBBlock(ebp,ic);
1550     hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
1551     return 1;
1552
1553 }
1554
1555 /*-----------------------------------------------------------------*/
1556 /* findAssignToSym : scanning backwards looks for first assig found*/
1557 /*-----------------------------------------------------------------*/
1558 static iCode *findAssignToSym (operand *op,iCode *ic)
1559 {
1560     iCode *dic;
1561
1562     for (dic = ic->prev ; dic ; dic = dic->prev) {
1563
1564         /* if definition by assignment */
1565         if (dic->op == '='                 &&
1566             !POINTER_SET(dic)              &&
1567             IC_RESULT(dic)->key == op->key
1568 /*          &&  IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1569             ) {
1570
1571             /* we are interested only if defined in far space */
1572             /* or in stack space in case of + & - */
1573
1574             /* if assigned to a non-symbol then return
1575                true */
1576             if (!IS_SYMOP(IC_RIGHT(dic)))
1577                 break ;
1578
1579             /* if the symbol is in far space then
1580                we should not */
1581             if (isOperandInFarSpace(IC_RIGHT(dic)))
1582                 return NULL ;
1583
1584             /* for + & - operations make sure that
1585                if it is on the stack it is the same
1586                as one of the three operands */
1587             if ((ic->op == '+' || ic->op == '-') &&
1588                 OP_SYMBOL(IC_RIGHT(dic))->onStack) {
1589
1590                 if ( IC_RESULT(ic)->key != IC_RIGHT(dic)->key &&
1591                      IC_LEFT(ic)->key   != IC_RIGHT(dic)->key &&
1592                      IC_RIGHT(ic)->key  != IC_RIGHT(dic)->key)
1593                     return NULL;
1594             }
1595
1596             break ;
1597
1598         }
1599
1600         /* if we find an usage then we cannot delete it */
1601         if (IC_LEFT(dic) && IC_LEFT(dic)->key == op->key)
1602             return NULL;
1603
1604         if (IC_RIGHT(dic) && IC_RIGHT(dic)->key == op->key)
1605             return NULL;
1606
1607         if (POINTER_SET(dic) && IC_RESULT(dic)->key == op->key)
1608             return NULL;
1609     }
1610
1611     /* now make sure that the right side of dic
1612        is not defined between ic & dic */
1613     if (dic) {
1614         iCode *sic = dic->next ;
1615
1616         for (; sic != ic ; sic = sic->next)
1617             if (IC_RESULT(sic) &&
1618                 IC_RESULT(sic)->key == IC_RIGHT(dic)->key)
1619                 return NULL;
1620     }
1621
1622     return dic;
1623
1624
1625 }
1626
1627 /*-----------------------------------------------------------------*/
1628 /* packRegsForSupport :- reduce some registers for support calls   */
1629 /*-----------------------------------------------------------------*/
1630 static int packRegsForSupport (iCode *ic, eBBlock *ebp)
1631 {
1632     int change = 0 ;
1633     /* for the left & right operand :- look to see if the
1634        left was assigned a true symbol in far space in that
1635        case replace them */
1636     if (IS_ITEMP(IC_LEFT(ic)) &&
1637         OP_SYMBOL(IC_LEFT(ic))->liveTo <= ic->seq) {
1638         iCode *dic = findAssignToSym(IC_LEFT(ic),ic);
1639         iCode *sic;
1640
1641         if (!dic)
1642             goto right ;
1643
1644         /* found it we need to remove it from the
1645            block */
1646         for ( sic = dic; sic != ic ; sic = sic->next )
1647             bitVectUnSetBit(sic->rlive,IC_LEFT(ic)->key);
1648
1649         IC_LEFT(ic)->operand.symOperand =
1650             IC_RIGHT(dic)->operand.symOperand;
1651         IC_LEFT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1652         remiCodeFromeBBlock(ebp,dic);
1653         hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1654         change++;
1655     }
1656
1657     /* do the same for the right operand */
1658  right:
1659     if (!change &&
1660         IS_ITEMP(IC_RIGHT(ic)) &&
1661         OP_SYMBOL(IC_RIGHT(ic))->liveTo <= ic->seq) {
1662         iCode *dic = findAssignToSym(IC_RIGHT(ic),ic);
1663         iCode *sic;
1664
1665         if (!dic)
1666             return change ;
1667
1668         /* if this is a subtraction & the result
1669            is a true symbol in far space then don't pack */
1670         if (ic->op == '-' && IS_TRUE_SYMOP(IC_RESULT(dic))) {
1671             link *etype =getSpec(operandType(IC_RESULT(dic)));
1672             if (IN_FARSPACE(SPEC_OCLS(etype)))
1673                 return change ;
1674         }
1675         /* found it we need to remove it from the
1676            block */
1677         for ( sic = dic; sic != ic ; sic = sic->next )
1678             bitVectUnSetBit(sic->rlive,IC_RIGHT(ic)->key);
1679
1680         IC_RIGHT(ic)->operand.symOperand =
1681             IC_RIGHT(dic)->operand.symOperand;
1682         IC_RIGHT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1683
1684         remiCodeFromeBBlock(ebp,dic);
1685         hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1686         change ++;
1687     }
1688
1689     return change ;
1690 }
1691
1692 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1693
1694
1695 /*-----------------------------------------------------------------*/
1696 /* packRegsForOneuse : - will reduce some registers for single Use */
1697 /*-----------------------------------------------------------------*/
1698 static iCode *packRegsForOneuse (iCode *ic, operand *op , eBBlock *ebp)
1699 {
1700     bitVect *uses ;
1701     iCode *dic, *sic;
1702
1703     /* if returning a literal then do nothing */
1704     if (!IS_SYMOP(op))
1705         return NULL;
1706
1707     /* only upto 2 bytes since we cannot predict
1708        the usage of b, & acc */
1709     if (getSize(operandType(op)) > fAVRReturnSize  &&
1710         ic->op != RETURN             &&
1711         ic->op != SEND)
1712         return NULL;
1713
1714     /* this routine will mark the a symbol as used in one
1715        instruction use only && if the defintion is local
1716        (ie. within the basic block) && has only one definition &&
1717        that definiion is either a return value from a
1718        function or does not contain any variables in
1719        far space */
1720     uses = bitVectCopy(OP_USES(op));
1721     bitVectUnSetBit(uses,ic->key); /* take away this iCode */
1722     if (!bitVectIsZero(uses)) /* has other uses */
1723         return NULL ;
1724
1725     /* if it has only one defintion */
1726     if (bitVectnBitsOn(OP_DEFS(op)) > 1)
1727         return NULL ; /* has more than one definition */
1728
1729     /* get the that definition */
1730     if (!(dic =
1731           hTabItemWithKey(iCodehTab,
1732                           bitVectFirstBit(OP_DEFS(op)))))
1733         return NULL ;
1734
1735     /* found the definition now check if it is local */
1736     if (dic->seq < ebp->fSeq ||
1737         dic->seq > ebp->lSeq)
1738         return NULL ; /* non-local */
1739
1740     /* now check if it is the return from
1741        a function call */
1742     if (dic->op == CALL || dic->op == PCALL ) {
1743         if (ic->op != SEND && ic->op != RETURN) {
1744             OP_SYMBOL(op)->ruonly = 1;
1745             return dic;
1746         }
1747         dic = dic->next ;
1748     }
1749
1750
1751     /* otherwise check that the definition does
1752        not contain any symbols in far space */
1753     if (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                 SPEC_USIGN(fromType) == SPEC_USIGN(toType)) {
2146
2147                 iCode *dic = packRegsForOneuse(ic,IC_RIGHT(ic),ebp);
2148                 if (dic) {
2149                     if (IS_ARITHMETIC_OP(dic)) {
2150                         IC_RESULT(dic) = IC_RESULT(ic);
2151                         remiCodeFromeBBlock(ebp,ic);
2152                         hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2153                         ic = ic->prev;
2154                     } else
2155                         OP_SYMBOL(IC_RIGHT(ic))->ruonly =  0;
2156                 }
2157             } else {
2158
2159                 /* if the type from and type to are the same
2160                    then if this is the only use then packit */
2161                 if (checkType(operandType(IC_RIGHT(ic)),
2162                               operandType(IC_LEFT(ic))) == 1) {
2163                     iCode *dic = packRegsForOneuse (ic,IC_RIGHT(ic),ebp);
2164                     if (dic) {
2165                         IC_RESULT(dic) = IC_RESULT(ic);
2166                         remiCodeFromeBBlock(ebp,ic);
2167                         hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2168                         ic = ic->prev;
2169                     }
2170                 }
2171             }
2172         }
2173
2174         /* pack for PUSH
2175            iTempNN := (some variable in farspace) V1
2176            push iTempNN ;
2177            -------------
2178            push V1
2179         */
2180 /*      if (ic->op == IPUSH ) { */
2181 /*          packForPush(ic,ebp); */
2182 /*      } */
2183
2184
2185         /* pack registers for accumulator use, when the
2186            result of an arithmetic or bit wise operation
2187            has only one use, that use is immediately following
2188            the defintion and the using iCode has only one
2189            operand or has two operands but one is literal &
2190            the result of that operation is not on stack then
2191            we can leave the result of this operation in acc:b
2192            combination */
2193 /*      if ((IS_ARITHMETIC_OP(ic)  */
2194
2195 /*           || IS_BITWISE_OP(ic)  */
2196
2197 /*           || ic->op == LEFT_OP || ic->op == RIGHT_OP */
2198
2199 /*           ) && */
2200 /*          IS_ITEMP(IC_RESULT(ic)) && */
2201 /*          getSize(operandType(IC_RESULT(ic))) <= 2) */
2202
2203 /*          packRegsForAccUse (ic); */
2204
2205     }
2206 }
2207
2208 /*-----------------------------------------------------------------*/
2209 /* preAssignParms - we have a leaf function preassign registers    */
2210 /*-----------------------------------------------------------------*/
2211 static void preAssignParms (iCode *ic)
2212 {
2213     int i = R16_IDX;
2214     /* look for receives and assign registers
2215        to the result of the receives */
2216     while (ic) {
2217         /* if it is a receive */
2218         if (ic->op == RECEIVE) {
2219             symbol *r = OP_SYMBOL(IC_RESULT(ic));
2220             int size = getSize(r->type);
2221             if (r->regType == REG_GPR || r->regType == REG_SCR) {
2222                 int j = 0;
2223                 while (size--) {
2224                     r->regs[j++] = &regsAVR[i++];
2225                     regsAVR[i-1].isFree = 0;
2226                 }
2227                 /* put in the regassigned vector */
2228                 _G.regAssigned = bitVectSetBit(_G.regAssigned,r->key);
2229             } else {
2230                 /* not a GPR then we should mark as free */
2231                 while (size--) {
2232                     regsAVR[i++].isFree =1;
2233                 }
2234             }
2235         }
2236         ic = ic->next;
2237     }
2238     /* mark anything remaining as free */
2239     while (i <= R23_IDX)
2240         regsAVR[i++].isFree =1;
2241 }
2242
2243 /*-----------------------------------------------------------------*/
2244 /* setdefaultRegs - do setup stuff for register allocation         */
2245 /*-----------------------------------------------------------------*/
2246 static void setDefaultRegs(eBBlock **ebbs,int count)
2247 {
2248     int i ;
2249
2250     /* if no pointer registers required in this function
2251        then mark r26-27 & r30-r31 as GPR & free */
2252     regsAVR[R26_IDX].isFree =
2253         regsAVR[R27_IDX].isFree =
2254         regsAVR[R30_IDX].isFree =
2255         regsAVR[R31_IDX].isFree = 1;
2256
2257     if (!avr_ptrRegReq) {
2258         regsAVR[R26_IDX].type =
2259             regsAVR[R27_IDX].type =
2260             regsAVR[R30_IDX].type =
2261             regsAVR[R31_IDX].type = REG_GPR ;
2262     } else {
2263         regsAVR[R26_IDX].type =
2264             regsAVR[R27_IDX].type =
2265             regsAVR[R30_IDX].type =
2266             regsAVR[R31_IDX].type = REG_PTR ;
2267     }
2268
2269     /* registers 0-1 / 24-25 used as scratch */
2270     regsAVR[R0_IDX].isFree =
2271         regsAVR[R1_IDX].isFree =
2272         regsAVR[R24_IDX].isFree =
2273         regsAVR[R25_IDX].isFree = 0;
2274
2275     /* if this has no function calls then we need
2276        to do something special
2277        a) pre-assign registers to parameters RECEIVE
2278        b) mark the remaining parameter regs as free */
2279     if (!currFunc->hasFcall) {
2280         /* mark the parameter regs as GPR */
2281         for (i= R16_IDX ; i <= R23_IDX ;i++) {
2282             regsAVR[i].type = REG_SCR;
2283             regsAVR[i].isFree = 1;
2284         }
2285         preAssignParms(ebbs[0]->sch);
2286     } else {
2287
2288         /* otherwise mark them as free scratch */
2289         for (i= R16_IDX ; i <= R23_IDX ;i++) {
2290             regsAVR[i].type = REG_SCR;
2291             regsAVR[i].isFree = 1;
2292         }
2293     }
2294
2295     /* Y - is not allocated (it is the stack frame) */
2296     regsAVR[R28_IDX].isFree =
2297         regsAVR[R28_IDX].isFree =0;
2298 }
2299
2300 /*-----------------------------------------------------------------*/
2301 /* assignRegisters - assigns registers to each live range as need  */
2302 /*-----------------------------------------------------------------*/
2303 void avr_assignRegisters (eBBlock **ebbs, int count)
2304 {
2305     iCode *ic;
2306     int i ;
2307
2308     setToNull((void *)&_G.funcrUsed);
2309     avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2310
2311     /* change assignments this will remove some
2312        live ranges reducing some register pressure */
2313     for (i = 0 ; i < count ;i++ )
2314         packRegisters (ebbs[i]);
2315
2316     if (options.dump_pack)
2317         dumpEbbsToFileExt(".dumppack",ebbs,count);
2318
2319     /* first determine for each live range the number of
2320        registers & the type of registers required for each */
2321     regTypeNum ();
2322
2323     /* setup the default registers */
2324     setDefaultRegs(ebbs,count);
2325
2326     /* and serially allocate registers */
2327     serialRegAssign(ebbs,count);
2328
2329     /* if stack was extended then tell the user */
2330     if (_G.stackExtend) {
2331 /*      werror(W_TOOMANY_SPILS,"stack", */
2332 /*             _G.stackExtend,currFunc->name,""); */
2333         _G.stackExtend = 0 ;
2334     }
2335
2336     if (_G.dataExtend) {
2337 /*      werror(W_TOOMANY_SPILS,"data space", */
2338 /*             _G.dataExtend,currFunc->name,""); */
2339         _G.dataExtend = 0 ;
2340     }
2341
2342     /* after that create the register mask
2343        for each of the instruction */
2344     createRegMask (ebbs,count);
2345
2346     /* redo that offsets for stacked automatic variables */
2347     redoStackOffsets ();
2348
2349     if (options.dump_rassgn)
2350         dumpEbbsToFileExt(".dumprassgn",ebbs,count);
2351
2352     /* now get back the chain */
2353     ic = iCodeLabelOptimize(iCodeFromeBBlock (ebbs,count));
2354
2355
2356     genAVRCode(ic);
2357 /*     for (; ic ; ic = ic->next) */
2358 /*          piCode(ic,stdout); */
2359     /* free up any _G.stackSpil locations allocated */
2360     applyToSet(_G.stackSpil,deallocStackSpil);
2361     _G.slocNum = 0;
2362     setToNull((void **)&_G.stackSpil);
2363     setToNull((void **)&_G.spiltSet);
2364     /* mark all registers as free */
2365
2366     return ;
2367 }