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