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

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