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