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