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