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