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

   1 /*------------------------------------------------------------------------
   2
   3   SDCCralloc.c - source file for register allocation. (8051) 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 gen51Code (iCode *);
  40 #define D(x)
  41
  42 /* Global data */
  43 static struct
  44   {
  45     bitVect *spiltSet;
  46     set *stackSpil;
  47     bitVect *regAssigned;
  48     bitVect *totRegAssigned;    /* final set of LRs that got into registers */
  49     short blockSpil;
  50     int slocNum;
  51     bitVect *funcrUsed;         /* registers used in a function */
  52     int stackExtend;
  53     int dataExtend;
  54   }
  55 _G;
  56
  57 /* Shared with gen.c */
  58 int mcs51_ptrRegReq;            /* one byte pointer register required */
  59
  60 /* 8051 registers */
  61 regs regs8051[] =
  62 {
  63
  64   {REG_GPR, R2_IDX, REG_GPR, "r2", "ar2", "0", 2, 1},
  65   {REG_GPR, R3_IDX, REG_GPR, "r3", "ar3", "0", 3, 1},
  66   {REG_GPR, R4_IDX, REG_GPR, "r4", "ar4", "0", 4, 1},
  67   {REG_GPR, R5_IDX, REG_GPR, "r5", "ar5", "0", 5, 1},
  68   {REG_GPR, R6_IDX, REG_GPR, "r6", "ar6", "0", 6, 1},
  69   {REG_GPR, R7_IDX, REG_GPR, "r7", "ar7", "0", 7, 1},
  70   {REG_PTR, R0_IDX, REG_PTR, "r0", "ar0", "0", 0, 1},
  71   {REG_PTR, R1_IDX, REG_PTR, "r1", "ar1", "0", 1, 1},
  72   {REG_GPR, X8_IDX, REG_GPR, "x8", "x8", "xreg", 0, 1},
  73   {REG_GPR, X9_IDX, REG_GPR, "x9", "x9", "xreg", 1, 1},
  74   {REG_GPR, X10_IDX, REG_GPR, "x10", "x10", "xreg", 2, 1},
  75   {REG_GPR, X11_IDX, REG_GPR, "x11", "x11", "xreg", 3, 1},
  76   {REG_GPR, X12_IDX, REG_GPR, "x12", "x12", "xreg", 4, 1},
  77   {REG_CND, CND_IDX, REG_CND, "C", "psw", "0xd0", 0, 1},
  78   {0, DPL_IDX, 0, "dpl", "dpl", "0x82", 0, 0},
  79   {0, DPH_IDX, 0, "dph", "dph", "0x83", 0, 0},
  80   {0, B_IDX, 0, "b", "b", "0xf0", 0, 0},
  81   {0, A_IDX, 0, "a", "acc", "0xe0", 0, 0},
  82 };
  83 int mcs51_nRegs = 17;
  84 static void spillThis (symbol *);
  85 static void freeAllRegs ();
  86
  87 /*-----------------------------------------------------------------*/
  88 /* allocReg - allocates register of given type                     */
  89 /*-----------------------------------------------------------------*/
  90 static regs *
  91 allocReg (short type)
  92 {
  93   int i;
  94
  95   for (i = 0; i < mcs51_nRegs; i++)
  96     {
  97
  98       /* if type is given as 0 then any
  99          free register will do */
 100       if (!type &&
 101           regs8051[i].isFree)
 102         {
 103           regs8051[i].isFree = 0;
 104           if (currFunc)
 105             currFunc->regsUsed =
 106               bitVectSetBit (currFunc->regsUsed, i);
 107           return &regs8051[i];
 108         }
 109       /* other wise look for specific type
 110          of register */
 111       if (regs8051[i].isFree &&
 112           regs8051[i].type == type)
 113         {
 114           regs8051[i].isFree = 0;
 115           if (currFunc)
 116             currFunc->regsUsed =
 117               bitVectSetBit (currFunc->regsUsed, i);
 118           return &regs8051[i];
 119         }
 120     }
 121   return NULL;
 122 }
 123
 124 /*-----------------------------------------------------------------*/
 125 /* allocThisReg - allocates a particular register (if free)        */
 126 /*-----------------------------------------------------------------*/
 127 static regs *
 128 allocThisReg (regs * reg)
 129 {
 130   if (!reg->isFree)
 131     return NULL;
 132
 133   reg->isFree = 0;
 134   if (currFunc)
 135     currFunc->regsUsed = bitVectSetBit (currFunc->regsUsed, reg->rIdx);
 136
 137   return reg;
 138 }
 139
 140
 141 /*-----------------------------------------------------------------*/
 142 /* mcs51_regWithIdx - returns pointer to register with index number*/
 143 /*-----------------------------------------------------------------*/
 144 regs *
 145 mcs51_regWithIdx (int idx)
 146 {
 147   int i;
 148
 149   for (i = 0; i < sizeof(regs8051)/sizeof(regs); i++)
 150     if (regs8051[i].rIdx == idx)
 151       return &regs8051[i];
 152
 153   werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
 154           "regWithIdx not found");
 155   exit (1);
 156 }
 157
 158 /*-----------------------------------------------------------------*/
 159 /* freeReg - frees a register                                      */
 160 /*-----------------------------------------------------------------*/
 161 static void
 162 freeReg (regs * reg)
 163 {
 164   if (!reg)
 165     {
 166       werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
 167               "freeReg - Freeing NULL register");
 168       exit (1);
 169     }
 170
 171   reg->isFree = 1;
 172 }
 173
 174
 175 /*-----------------------------------------------------------------*/
 176 /* nFreeRegs - returns number of free registers                    */
 177 /*-----------------------------------------------------------------*/
 178 static int
 179 nFreeRegs (int type)
 180 {
 181   int i;
 182   int nfr = 0;
 183
 184   for (i = 0; i < mcs51_nRegs; i++)
 185     if (regs8051[i].isFree && regs8051[i].type == type)
 186       nfr++;
 187   return nfr;
 188 }
 189
 190 /*-----------------------------------------------------------------*/
 191 /* nfreeRegsType - free registers with type                         */
 192 /*-----------------------------------------------------------------*/
 193 static int
 194 nfreeRegsType (int type)
 195 {
 196   int nfr;
 197   if (type == REG_PTR)
 198     {
 199       if ((nfr = nFreeRegs (type)) == 0)
 200         return nFreeRegs (REG_GPR);
 201     }
 202
 203   return nFreeRegs (type);
 204 }
 205
 206 /*-----------------------------------------------------------------*/
 207 /* useReg - marks a register  as used                              */
 208 /*-----------------------------------------------------------------*/
 209 static void
 210 useReg (regs * reg)
 211 {
 212   reg->isFree = 0;
 213 }
 214
 215 /*-----------------------------------------------------------------*/
 216 /* computeSpillable - given a point find the spillable live ranges */
 217 /*-----------------------------------------------------------------*/
 218 static bitVect *
 219 computeSpillable (iCode * ic)
 220 {
 221   bitVect *spillable;
 222
 223   /* spillable live ranges are those that are live at this
 224      point . the following categories need to be subtracted
 225      from this set.
 226      a) - those that are already spilt
 227      b) - if being used by this one
 228      c) - defined by this one */
 229
 230   spillable = bitVectCopy (ic->rlive);
 231   spillable =
 232     bitVectCplAnd (spillable, _G.spiltSet);     /* those already spilt */
 233   spillable =
 234     bitVectCplAnd (spillable, ic->uses);        /* used in this one */
 235   bitVectUnSetBit (spillable, ic->defKey);
 236   spillable = bitVectIntersect (spillable, _G.regAssigned);
 237   return spillable;
 238
 239 }
 240
 241 /*-----------------------------------------------------------------*/
 242 /* noSpilLoc - return true if a variable has no spil location      */
 243 /*-----------------------------------------------------------------*/
 244 static int
 245 noSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
 246 {
 247   return (sym->usl.spillLoc ? 0 : 1);
 248 }
 249
 250 /*-----------------------------------------------------------------*/
 251 /* hasSpilLoc - will return 1 if the symbol has spil location      */
 252 /*-----------------------------------------------------------------*/
 253 static int
 254 hasSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
 255 {
 256   return (sym->usl.spillLoc ? 1 : 0);
 257 }
 258
 259 /*-----------------------------------------------------------------*/
 260 /* directSpilLoc - will return 1 if the splilocation is in direct  */
 261 /*-----------------------------------------------------------------*/
 262 static int
 263 directSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
 264 {
 265   if (sym->usl.spillLoc &&
 266       (IN_DIRSPACE (SPEC_OCLS (sym->usl.spillLoc->etype))))
 267     return 1;
 268   else
 269     return 0;
 270 }
 271
 272 /*-----------------------------------------------------------------*/
 273 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location */
 274 /*                    but is not used as a pointer                 */
 275 /*-----------------------------------------------------------------*/
 276 static int
 277 hasSpilLocnoUptr (symbol * sym, eBBlock * ebp, iCode * ic)
 278 {
 279   return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
 280 }
 281
 282 /*-----------------------------------------------------------------*/
 283 /* rematable - will return 1 if the remat flag is set              */
 284 /*-----------------------------------------------------------------*/
 285 static int
 286 rematable (symbol * sym, eBBlock * ebp, iCode * ic)
 287 {
 288   return sym->remat;
 289 }
 290
 291 /*-----------------------------------------------------------------*/
 292 /* notUsedInRemaining - not used or defined in remain of the block */
 293 /*-----------------------------------------------------------------*/
 294 static int
 295 notUsedInRemaining (symbol * sym, eBBlock * ebp, iCode * ic)
 296 {
 297   return ((usedInRemaining (operandFromSymbol (sym), ic) ? 0 : 1) &&
 298           allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq));
 299 }
 300
 301 /*-----------------------------------------------------------------*/
 302 /* allLRs - return true for all                                    */
 303 /*-----------------------------------------------------------------*/
 304 static int
 305 allLRs (symbol * sym, eBBlock * ebp, iCode * ic)
 306 {
 307   return 1;
 308 }
 309
 310 /*-----------------------------------------------------------------*/
 311 /* liveRangesWith - applies function to a given set of live range  */
 312 /*-----------------------------------------------------------------*/
 313 static set *
 314 liveRangesWith (bitVect * lrs, int (func) (symbol *, eBBlock *, iCode *),
 315                 eBBlock * ebp, iCode * ic)
 316 {
 317   set *rset = NULL;
 318   int i;
 319
 320   if (!lrs || !lrs->size)
 321     return NULL;
 322
 323   for (i = 1; i < lrs->size; i++)
 324     {
 325       symbol *sym;
 326       if (!bitVectBitValue (lrs, i))
 327         continue;
 328
 329       /* if we don't find it in the live range
 330          hash table we are in serious trouble */
 331       if (!(sym = hTabItemWithKey (liveRanges, i)))
 332         {
 333           werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
 334                   "liveRangesWith could not find liveRange");
 335           exit (1);
 336         }
 337
 338       if (func (sym, ebp, ic) && bitVectBitValue (_G.regAssigned, sym->key))
 339         addSetHead (&rset, sym);
 340     }
 341
 342   return rset;
 343 }
 344
 345
 346 /*-----------------------------------------------------------------*/
 347 /* leastUsedLR - given a set determines which is the least used    */
 348 /*-----------------------------------------------------------------*/
 349 static symbol *
 350 leastUsedLR (set * sset)
 351 {
 352   symbol *sym = NULL, *lsym = NULL;
 353
 354   sym = lsym = setFirstItem (sset);
 355
 356   if (!lsym)
 357     return NULL;
 358
 359   for (; lsym; lsym = setNextItem (sset))
 360     {
 361
 362       /* if usage is the same then prefer
 363          the spill the smaller of the two */
 364       if (lsym->used == sym->used)
 365         if (getSize (lsym->type) < getSize (sym->type))
 366           sym = lsym;
 367
 368       /* if less usage */
 369       if (lsym->used < sym->used)
 370         sym = lsym;
 371
 372     }
 373
 374   setToNull ((void *) &sset);
 375   sym->blockSpil = 0;
 376   return sym;
 377 }
 378
 379 /*-----------------------------------------------------------------*/
 380 /* noOverLap - will iterate through the list looking for over lap  */
 381 /*-----------------------------------------------------------------*/
 382 static int
 383 noOverLap (set * itmpStack, symbol * fsym)
 384 {
 385   symbol *sym;
 386
 387   for (sym = setFirstItem (itmpStack); sym;
 388        sym = setNextItem (itmpStack))
 389     {
 390         if (bitVectBitValue(sym->clashes,fsym->key)) return 0;
 391     }
 392   return 1;
 393 }
 394
 395 /*-----------------------------------------------------------------*/
 396 /* isFree - will return 1 if the a free spil location is found     */
 397 /*-----------------------------------------------------------------*/
 398 static
 399 DEFSETFUNC (isFree)
 400 {
 401   symbol *sym = item;
 402   V_ARG (symbol **, sloc);
 403   V_ARG (symbol *, fsym);
 404
 405   /* if already found */
 406   if (*sloc)
 407     return 0;
 408
 409   /* if it is free && and the itmp assigned to
 410      this does not have any overlapping live ranges
 411      with the one currently being assigned and
 412      the size can be accomodated  */
 413   if (sym->isFree &&
 414       noOverLap (sym->usl.itmpStack, fsym) &&
 415       getSize (sym->type) >= getSize (fsym->type))
 416     {
 417       *sloc = sym;
 418       return 1;
 419     }
 420
 421   return 0;
 422 }
 423
 424 /*-----------------------------------------------------------------*/
 425 /* spillLRWithPtrReg :- will spil those live ranges which use PTR  */
 426 /*-----------------------------------------------------------------*/
 427 static void
 428 spillLRWithPtrReg (symbol * forSym)
 429 {
 430   symbol *lrsym;
 431   regs *r0, *r1;
 432   int k;
 433
 434   if (!_G.regAssigned ||
 435       bitVectIsZero (_G.regAssigned))
 436     return;
 437
 438   r0 = mcs51_regWithIdx (R0_IDX);
 439   r1 = mcs51_regWithIdx (R1_IDX);
 440
 441   /* for all live ranges */
 442   for (lrsym = hTabFirstItem (liveRanges, &k); lrsym;
 443        lrsym = hTabNextItem (liveRanges, &k))
 444     {
 445       int j;
 446
 447       /* if no registers assigned to it or spilt */
 448       /* if it does not overlap this then
 449          no need to spill it */
 450
 451       if (lrsym->isspilt || !lrsym->nRegs ||
 452           (lrsym->liveTo < forSym->liveFrom))
 453         continue;
 454
 455       /* go thru the registers : if it is either
 456          r0 or r1 then spill it */
 457       for (j = 0; j < lrsym->nRegs; j++)
 458         if (lrsym->regs[j] == r0 ||
 459             lrsym->regs[j] == r1)
 460           {
 461             spillThis (lrsym);
 462             break;
 463           }
 464     }
 465
 466 }
 467
 468 /*-----------------------------------------------------------------*/
 469 /* createStackSpil - create a location on the stack to spil        */
 470 /*-----------------------------------------------------------------*/
 471 static symbol *
 472 createStackSpil (symbol * sym)
 473 {
 474   symbol *sloc = NULL;
 475   int useXstack, model;
 476
 477   char slocBuffer[30];
 478
 479   /* first go try and find a free one that is already
 480      existing on the stack */
 481   if (applyToSet (_G.stackSpil, isFree, &sloc, sym))
 482     {
 483       /* found a free one : just update & return */
 484       sym->usl.spillLoc = sloc;
 485       sym->stackSpil = 1;
 486       sloc->isFree = 0;
 487       addSetHead (&sloc->usl.itmpStack, sym);
 488       return sym;
 489     }
 490
 491   /* could not then have to create one , this is the hard part
 492      we need to allocate this on the stack : this is really a
 493      hack!! but cannot think of anything better at this time */
 494
 495   if (SNPRINTF (slocBuffer, sizeof(slocBuffer),
 496                 "sloc%d", _G.slocNum++) >= sizeof (slocBuffer))
 497     {
 498       fprintf (stderr, "***Internal error: slocBuffer overflowed: %s:%d\n",
 499                __FILE__, __LINE__);
 500       exit (1);
 501     }
 502
 503   sloc = newiTemp (slocBuffer);
 504
 505   /* set the type to the spilling symbol */
 506   sloc->type = copyLinkChain (sym->type);
 507   sloc->etype = getSpec (sloc->type);
 508   SPEC_SCLS (sloc->etype) = S_DATA;
 509   SPEC_EXTR (sloc->etype) = 0;
 510   SPEC_STAT (sloc->etype) = 0;
 511   SPEC_VOLATILE(sloc->etype) = 0;
 512   SPEC_ABSA(sloc->etype) = 0;
 513
 514   /* we don't allow it to be allocated`
 515      onto the external stack since : so we
 516      temporarily turn it off ; we also
 517      turn off memory model to prevent
 518      the spil from going to the external storage
 519    */
 520
 521   useXstack = options.useXstack;
 522   model = options.model;
 523 /*     noOverlay = options.noOverlay; */
 524 /*     options.noOverlay = 1; */
 525   options.model = options.useXstack = 0;
 526
 527   allocLocal (sloc);
 528
 529   options.useXstack = useXstack;
 530   options.model = model;
 531 /*     options.noOverlay = noOverlay; */
 532   sloc->isref = 1;              /* to prevent compiler warning */
 533
 534   /* if it is on the stack then update the stack */
 535   if (IN_STACK (sloc->etype))
 536     {
 537       currFunc->stack += getSize (sloc->type);
 538       _G.stackExtend += getSize (sloc->type);
 539     }
 540   else
 541     _G.dataExtend += getSize (sloc->type);
 542
 543   /* add it to the _G.stackSpil set */
 544   addSetHead (&_G.stackSpil, sloc);
 545   sym->usl.spillLoc = sloc;
 546   sym->stackSpil = 1;
 547
 548   /* add it to the set of itempStack set
 549      of the spill location */
 550   addSetHead (&sloc->usl.itmpStack, sym);
 551   return sym;
 552 }
 553
 554 /*-----------------------------------------------------------------*/
 555 /* isSpiltOnStack - returns true if the spil location is on stack  */
 556 /*-----------------------------------------------------------------*/
 557 static bool
 558 isSpiltOnStack (symbol * sym)
 559 {
 560   sym_link *etype;
 561
 562   if (!sym)
 563     return FALSE;
 564
 565   if (!sym->isspilt)
 566     return FALSE;
 567
 568 /*     if (sym->_G.stackSpil) */
 569 /*      return TRUE; */
 570
 571   if (!sym->usl.spillLoc)
 572     return FALSE;
 573
 574   etype = getSpec (sym->usl.spillLoc->type);
 575   if (IN_STACK (etype))
 576     return TRUE;
 577
 578   return FALSE;
 579 }
 580
 581 /*-----------------------------------------------------------------*/
 582 /* spillThis - spils a specific operand                            */
 583 /*-----------------------------------------------------------------*/
 584 static void
 585 spillThis (symbol * sym)
 586 {
 587   int i;
 588   /* if this is rematerializable or has a spillLocation
 589      we are okay, else we need to create a spillLocation
 590      for it */
 591   if (!(sym->remat || sym->usl.spillLoc))
 592     createStackSpil (sym);
 593
 594   /* mark it has spilt & put it in the spilt set */
 595   sym->isspilt = sym->spillA = 1;
 596   _G.spiltSet = bitVectSetBit (_G.spiltSet, sym->key);
 597
 598   bitVectUnSetBit (_G.regAssigned, sym->key);
 599   bitVectUnSetBit (_G.totRegAssigned, sym->key);
 600
 601   for (i = 0; i < sym->nRegs; i++)
 602
 603     if (sym->regs[i])
 604       {
 605         freeReg (sym->regs[i]);
 606         sym->regs[i] = NULL;
 607       }
 608
 609   /* if spilt on stack then free up r0 & r1
 610      if they could have been assigned to some
 611      LIVE ranges */
 612   if (!mcs51_ptrRegReq && isSpiltOnStack (sym))
 613     {
 614       mcs51_ptrRegReq++;
 615       spillLRWithPtrReg (sym);
 616     }
 617
 618   if (sym->usl.spillLoc && !sym->remat)
 619     sym->usl.spillLoc->allocreq++;
 620   return;
 621 }
 622
 623 /*-----------------------------------------------------------------*/
 624 /* selectSpil - select a iTemp to spil : rather a simple procedure */
 625 /*-----------------------------------------------------------------*/
 626 static symbol *
 627 selectSpil (iCode * ic, eBBlock * ebp, symbol * forSym)
 628 {
 629   bitVect *lrcs = NULL;
 630   set *selectS;
 631   symbol *sym;
 632
 633   /* get the spillable live ranges */
 634   lrcs = computeSpillable (ic);
 635
 636   /* get all live ranges that are rematerizable */
 637   if ((selectS = liveRangesWith (lrcs, rematable, ebp, ic)))
 638     {
 639
 640       /* return the least used of these */
 641       return leastUsedLR (selectS);
 642     }
 643
 644   /* get live ranges with spillLocations in direct space */
 645   if ((selectS = liveRangesWith (lrcs, directSpilLoc, ebp, ic)))
 646     {
 647       sym = leastUsedLR (selectS);
 648       strncpyz (sym->rname,
 649                 sym->usl.spillLoc->rname[0] ?
 650                    sym->usl.spillLoc->rname : sym->usl.spillLoc->name,
 651                 sizeof(sym->rname));
 652       sym->spildir = 1;
 653       /* mark it as allocation required */
 654       sym->usl.spillLoc->allocreq++;
 655       return sym;
 656     }
 657
 658   /* if the symbol is local to the block then */
 659   if (forSym->liveTo < ebp->lSeq)
 660     {
 661
 662       /* check if there are any live ranges allocated
 663          to registers that are not used in this block */
 664       if (!_G.blockSpil && (selectS = liveRangesWith (lrcs, notUsedInBlock, ebp, ic)))
 665         {
 666           sym = leastUsedLR (selectS);
 667           /* if this is not rematerializable */
 668           if (!sym->remat)
 669             {
 670               _G.blockSpil++;
 671               sym->blockSpil = 1;
 672             }
 673           return sym;
 674         }
 675
 676       /* check if there are any live ranges that not
 677          used in the remainder of the block */
 678       if (!_G.blockSpil &&
 679           !isiCodeInFunctionCall (ic) &&
 680           (selectS = liveRangesWith (lrcs, notUsedInRemaining, ebp, ic)))
 681         {
 682           sym = leastUsedLR (selectS);
 683           if (sym != forSym)
 684             {
 685               if (!sym->remat)
 686                 {
 687                   sym->remainSpil = 1;
 688                   _G.blockSpil++;
 689                 }
 690               return sym;
 691             }
 692         }
 693     }
 694
 695   /* find live ranges with spillocation && not used as pointers */
 696   if ((selectS = liveRangesWith (lrcs, hasSpilLocnoUptr, ebp, ic)))
 697     {
 698
 699       sym = leastUsedLR (selectS);
 700       /* mark this as allocation required */
 701       sym->usl.spillLoc->allocreq++;
 702       return sym;
 703     }
 704
 705   /* find live ranges with spillocation */
 706   if ((selectS = liveRangesWith (lrcs, hasSpilLoc, ebp, ic)))
 707     {
 708
 709       sym = leastUsedLR (selectS);
 710       sym->usl.spillLoc->allocreq++;
 711       return sym;
 712     }
 713
 714   /* couldn't find then we need to create a spil
 715      location on the stack , for which one? the least
 716      used ofcourse */
 717   if ((selectS = liveRangesWith (lrcs, noSpilLoc, ebp, ic)))
 718     {
 719
 720       /* return a created spil location */
 721       sym = createStackSpil (leastUsedLR (selectS));
 722       sym->usl.spillLoc->allocreq++;
 723       return sym;
 724     }
 725
 726   /* this is an extreme situation we will spill
 727      this one : happens very rarely but it does happen */
 728   spillThis (forSym);
 729   return forSym;
 730
 731 }
 732
 733 /*-----------------------------------------------------------------*/
 734 /* spilSomething - spil some variable & mark registers as free     */
 735 /*-----------------------------------------------------------------*/
 736 static bool
 737 spilSomething (iCode * ic, eBBlock * ebp, symbol * forSym)
 738 {
 739   symbol *ssym;
 740   int i;
 741
 742   /* get something we can spil */
 743   ssym = selectSpil (ic, ebp, forSym);
 744
 745   /* mark it as spilt */
 746   ssym->isspilt = ssym->spillA = 1;
 747   _G.spiltSet = bitVectSetBit (_G.spiltSet, ssym->key);
 748
 749   /* mark it as not register assigned &
 750      take it away from the set */
 751   bitVectUnSetBit (_G.regAssigned, ssym->key);
 752   bitVectUnSetBit (_G.totRegAssigned, ssym->key);
 753
 754   /* mark the registers as free */
 755   for (i = 0; i < ssym->nRegs; i++)
 756     if (ssym->regs[i])
 757       freeReg (ssym->regs[i]);
 758
 759   /* if spilt on stack then free up r0 & r1
 760      if they could have been assigned to as gprs */
 761   if (!mcs51_ptrRegReq && isSpiltOnStack (ssym))
 762     {
 763       mcs51_ptrRegReq++;
 764       spillLRWithPtrReg (ssym);
 765     }
 766
 767   /* if this was a block level spil then insert push & pop
 768      at the start & end of block respectively */
 769   if (ssym->blockSpil)
 770     {
 771       iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
 772       /* add push to the start of the block */
 773       addiCodeToeBBlock (ebp, nic, (ebp->sch->op == LABEL ?
 774                                     ebp->sch->next : ebp->sch));
 775       nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
 776       /* add pop to the end of the block */
 777       addiCodeToeBBlock (ebp, nic, NULL);
 778     }
 779
 780   /* if spilt because not used in the remainder of the
 781      block then add a push before this instruction and
 782      a pop at the end of the block */
 783   if (ssym->remainSpil)
 784     {
 785
 786       iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
 787       /* add push just before this instruction */
 788       addiCodeToeBBlock (ebp, nic, ic);
 789
 790       nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
 791       /* add pop to the end of the block */
 792       addiCodeToeBBlock (ebp, nic, NULL);
 793     }
 794
 795   if (ssym == forSym)
 796     return FALSE;
 797   else
 798     return TRUE;
 799 }
 800
 801 /*-----------------------------------------------------------------*/
 802 /* getRegPtr - will try for PTR if not a GPR type if not spil      */
 803 /*-----------------------------------------------------------------*/
 804 static regs *
 805 getRegPtr (iCode * ic, eBBlock * ebp, symbol * sym)
 806 {
 807   regs *reg;
 808   int j;
 809
 810 tryAgain:
 811   /* try for a ptr type */
 812   if ((reg = allocReg (REG_PTR)))
 813     return reg;
 814
 815   /* try for gpr type */
 816   if ((reg = allocReg (REG_GPR)))
 817     return reg;
 818
 819   /* we have to spil */
 820   if (!spilSomething (ic, ebp, sym))
 821     return NULL;
 822
 823   /* make sure partially assigned registers aren't reused */
 824   for (j=0; j<=sym->nRegs; j++)
 825     if (sym->regs[j])
 826       sym->regs[j]->isFree = 0;
 827
 828   /* this looks like an infinite loop but
 829      in really selectSpil will abort  */
 830   goto tryAgain;
 831 }
 832
 833 /*-----------------------------------------------------------------*/
 834 /* getRegGpr - will try for GPR if not spil                        */
 835 /*-----------------------------------------------------------------*/
 836 static regs *
 837 getRegGpr (iCode * ic, eBBlock * ebp, symbol * sym)
 838 {
 839   regs *reg;
 840   int j;
 841
 842 tryAgain:
 843   /* try for gpr type */
 844   if ((reg = allocReg (REG_GPR)))
 845     return reg;
 846
 847   if (!mcs51_ptrRegReq)
 848     if ((reg = allocReg (REG_PTR)))
 849       return reg;
 850
 851   /* we have to spil */
 852   if (!spilSomething (ic, ebp, sym))
 853     return NULL;
 854
 855   /* make sure partially assigned registers aren't reused */
 856   for (j=0; j<=sym->nRegs; j++)
 857     if (sym->regs[j])
 858       sym->regs[j]->isFree = 0;
 859
 860   /* this looks like an infinite loop but
 861      in really selectSpil will abort  */
 862   goto tryAgain;
 863 }
 864
 865 /*-----------------------------------------------------------------*/
 866 /* getRegPtrNoSpil - get it cannot split                           */
 867 /*-----------------------------------------------------------------*/
 868 static regs *getRegPtrNoSpil()
 869 {
 870   regs *reg;
 871
 872   /* try for a ptr type */
 873   if ((reg = allocReg (REG_PTR)))
 874     return reg;
 875
 876   /* try for gpr type */
 877   if ((reg = allocReg (REG_GPR)))
 878     return reg;
 879
 880   assert(0);
 881
 882   /* just to make the compiler happy */
 883   return 0;
 884 }
 885
 886 /*-----------------------------------------------------------------*/
 887 /* getRegGprNoSpil - get it cannot split                           */
 888 /*-----------------------------------------------------------------*/
 889 static regs *getRegGprNoSpil()
 890 {
 891
 892   regs *reg;
 893   if ((reg = allocReg (REG_GPR)))
 894     return reg;
 895
 896   if (!mcs51_ptrRegReq)
 897     if ((reg = allocReg (REG_PTR)))
 898       return reg;
 899
 900   assert(0);
 901
 902   /* just to make the compiler happy */
 903   return 0;
 904 }
 905
 906 /*-----------------------------------------------------------------*/
 907 /* symHasReg - symbol has a given register                         */
 908 /*-----------------------------------------------------------------*/
 909 static bool
 910 symHasReg (symbol * sym, regs * reg)
 911 {
 912   int i;
 913
 914   for (i = 0; i < sym->nRegs; i++)
 915     if (sym->regs[i] == reg)
 916       return TRUE;
 917
 918   return FALSE;
 919 }
 920
 921 /*-----------------------------------------------------------------*/
 922 /* deassignLRs - check the live to and if they have registers & are */
 923 /*               not spilt then free up the registers              */
 924 /*-----------------------------------------------------------------*/
 925 static void
 926 deassignLRs (iCode * ic, eBBlock * ebp)
 927 {
 928   symbol *sym;
 929   int k;
 930   symbol *result;
 931
 932   for (sym = hTabFirstItem (liveRanges, &k); sym;
 933        sym = hTabNextItem (liveRanges, &k))
 934     {
 935
 936       symbol *psym = NULL;
 937       /* if it does not end here */
 938       if (sym->liveTo > ic->seq)
 939         continue;
 940
 941       /* if it was spilt on stack then we can
 942          mark the stack spil location as free */
 943       if (sym->isspilt)
 944         {
 945           if (sym->stackSpil)
 946             {
 947               sym->usl.spillLoc->isFree = 1;
 948               sym->stackSpil = 0;
 949             }
 950           continue;
 951         }
 952
 953       if (!bitVectBitValue (_G.regAssigned, sym->key))
 954         continue;
 955
 956       /* special case check if this is an IFX &
 957          the privious one was a pop and the
 958          previous one was not spilt then keep track
 959          of the symbol */
 960       if (ic->op == IFX && ic->prev &&
 961           ic->prev->op == IPOP &&
 962           !ic->prev->parmPush &&
 963           !OP_SYMBOL (IC_LEFT (ic->prev))->isspilt)
 964         psym = OP_SYMBOL (IC_LEFT (ic->prev));
 965
 966       if (sym->nRegs)
 967         {
 968           int i = 0;
 969
 970           bitVectUnSetBit (_G.regAssigned, sym->key);
 971
 972           /* if the result of this one needs registers
 973              and does not have it then assign it right
 974              away */
 975           if (IC_RESULT (ic) &&
 976               !(SKIP_IC2 (ic) ||        /* not a special icode */
 977                 ic->op == JUMPTABLE ||
 978                 ic->op == IFX ||
 979                 ic->op == IPUSH ||
 980                 ic->op == IPOP ||
 981                 ic->op == RETURN ||
 982                 POINTER_SET (ic)) &&
 983               (result = OP_SYMBOL (IC_RESULT (ic))) &&  /* has a result */
 984               result->liveTo > ic->seq &&       /* and will live beyond this */
 985               result->liveTo <= ebp->lSeq &&    /* does not go beyond this block */
 986               result->liveFrom == ic->seq &&    /* does not start before here */
 987               result->regType == sym->regType &&        /* same register types */
 988               result->nRegs &&  /* which needs registers */
 989               !result->isspilt &&       /* and does not already have them */
 990               !result->remat &&
 991               !bitVectBitValue (_G.regAssigned, result->key) &&
 992           /* the number of free regs + number of regs in this LR
 993              can accomodate the what result Needs */
 994               ((nfreeRegsType (result->regType) +
 995                 sym->nRegs) >= result->nRegs)
 996             )
 997             {
 998
 999               for (i = 0; i < result->nRegs; i++)
1000                 if (i < sym->nRegs)
1001                   result->regs[i] = sym->regs[i];
1002                 else
1003                   result->regs[i] = getRegGpr (ic, ebp, result);
1004
1005               _G.regAssigned = bitVectSetBit (_G.regAssigned, result->key);
1006               _G.totRegAssigned = bitVectSetBit (_G.totRegAssigned, result->key);
1007
1008             }
1009
1010           /* free the remaining */
1011           for (; i < sym->nRegs; i++)
1012             {
1013               if (psym)
1014                 {
1015                   if (!symHasReg (psym, sym->regs[i]))
1016                     freeReg (sym->regs[i]);
1017                 }
1018               else
1019                 freeReg (sym->regs[i]);
1020             }
1021         }
1022     }
1023 }
1024
1025
1026 /*-----------------------------------------------------------------*/
1027 /* reassignLR - reassign this to registers                         */
1028 /*-----------------------------------------------------------------*/
1029 static void
1030 reassignLR (operand * op)
1031 {
1032   symbol *sym = OP_SYMBOL (op);
1033   int i;
1034
1035   /* not spilt any more */
1036   sym->isspilt = sym->spillA = sym->blockSpil = sym->remainSpil = 0;
1037   bitVectUnSetBit (_G.spiltSet, sym->key);
1038
1039   _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1040   _G.totRegAssigned = bitVectSetBit (_G.totRegAssigned, sym->key);
1041
1042   _G.blockSpil--;
1043
1044   for (i = 0; i < sym->nRegs; i++)
1045     sym->regs[i]->isFree = 0;
1046 }
1047
1048 /*-----------------------------------------------------------------*/
1049 /* willCauseSpill - determines if allocating will cause a spill    */
1050 /*-----------------------------------------------------------------*/
1051 static int
1052 willCauseSpill (int nr, int rt)
1053 {
1054   /* first check if there are any avlb registers
1055      of te type required */
1056   if (rt == REG_PTR)
1057     {
1058       /* special case for pointer type
1059          if pointer type not avlb then
1060          check for type gpr */
1061       if (nFreeRegs (rt) >= nr)
1062         return 0;
1063       if (nFreeRegs (REG_GPR) >= nr)
1064         return 0;
1065     }
1066   else
1067     {
1068       if (mcs51_ptrRegReq)
1069         {
1070           if (nFreeRegs (rt) >= nr)
1071             return 0;
1072         }
1073       else
1074         {
1075           if (nFreeRegs (REG_PTR) +
1076               nFreeRegs (REG_GPR) >= nr)
1077             return 0;
1078         }
1079     }
1080
1081   /* it will cause a spil */
1082   return 1;
1083 }
1084
1085 /*-----------------------------------------------------------------*/
1086 /* positionRegs - the allocator can allocate same registers to res- */
1087 /* ult and operand, if this happens make sure they are in the same */
1088 /* position as the operand otherwise chaos results                 */
1089 /*-----------------------------------------------------------------*/
1090 static int
1091 positionRegs (symbol * result, symbol * opsym)
1092 {
1093   int count = min (result->nRegs, opsym->nRegs);
1094   int i, j = 0, shared = 0;
1095   int change = 0;
1096
1097   /* if the result has been spilt then cannot share */
1098   if (opsym->isspilt)
1099     return 0;
1100 again:
1101   shared = 0;
1102   /* first make sure that they actually share */
1103   for (i = 0; i < count; i++)
1104     {
1105       for (j = 0; j < count; j++)
1106         {
1107           if (result->regs[i] == opsym->regs[j] && i != j)
1108             {
1109               shared = 1;
1110               goto xchgPositions;
1111             }
1112         }
1113     }
1114 xchgPositions:
1115   if (shared)
1116     {
1117       regs *tmp = result->regs[i];
1118       result->regs[i] = result->regs[j];
1119       result->regs[j] = tmp;
1120       change ++;
1121       goto again;
1122     }
1123   return change;
1124 }
1125
1126 /*------------------------------------------------------------------*/
1127 /* verifyRegsAssigned - make sure an iTemp is properly initialized; */
1128 /* it should either have registers or have beed spilled. Otherwise, */
1129 /* there was an uninitialized variable, so just spill this to get   */
1130 /* the operand in a valid state.                                    */
1131 /*------------------------------------------------------------------*/
1132 static void
1133 verifyRegsAssigned (operand *op, iCode * ic)
1134 {
1135   symbol * sym;
1136
1137   if (!op) return;
1138   if (!IS_ITEMP (op)) return;
1139
1140   sym = OP_SYMBOL (op);
1141   if (sym->isspilt) return;
1142   if (!sym->nRegs) return;
1143   if (sym->regs[0]) return;
1144
1145   werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
1146             sym->prereqv ? sym->prereqv->name : sym->name);
1147   spillThis (sym);
1148 }
1149
1150
1151 /*-----------------------------------------------------------------*/
1152 /* serialRegAssign - serially allocate registers to the variables  */
1153 /*-----------------------------------------------------------------*/
1154 static void
1155 serialRegAssign (eBBlock ** ebbs, int count)
1156 {
1157   int i;
1158
1159   /* for all blocks */
1160   for (i = 0; i < count; i++)
1161     {
1162
1163       iCode *ic;
1164
1165       if (ebbs[i]->noPath &&
1166           (ebbs[i]->entryLabel != entryLabel &&
1167            ebbs[i]->entryLabel != returnLabel))
1168         continue;
1169
1170       /* of all instructions do */
1171       for (ic = ebbs[i]->sch; ic; ic = ic->next)
1172         {
1173 #if 1
1174             int reg;
1175
1176             // update the registers in use at the start of this icode
1177             for (reg=0; reg<mcs51_nRegs; reg++) {
1178               if (regs8051[reg].isFree) {
1179                 ic->riu &= ~(1<<regs8051[reg].offset);
1180               } else {
1181                 ic->riu |= (1<<regs8051[reg].offset);
1182               }
1183             }
1184 #endif
1185             /* if this is an ipop that means some live
1186                range will have to be assigned again */
1187             if (ic->op == IPOP)
1188                 reassignLR (IC_LEFT (ic));
1189
1190             /* if result is present && is a true symbol */
1191             if (IC_RESULT (ic) && ic->op != IFX &&
1192                 IS_TRUE_SYMOP (IC_RESULT (ic)))
1193                 OP_SYMBOL (IC_RESULT (ic))->allocreq++;
1194
1195             /* take away registers from live
1196                ranges that end at this instruction */
1197             deassignLRs (ic, ebbs[i]);
1198
1199             /* some don't need registers */
1200             if (SKIP_IC2 (ic) ||
1201                 ic->op == JUMPTABLE ||
1202                 ic->op == IFX ||
1203                 ic->op == IPUSH ||
1204                 ic->op == IPOP ||
1205                 (IC_RESULT (ic) && POINTER_SET (ic)))
1206                 continue;
1207
1208             /* now we need to allocate registers
1209                only for the result */
1210             if (IC_RESULT (ic)) {
1211                 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1212                 bitVect *spillable;
1213                 int willCS;
1214                 int j;
1215                 int ptrRegSet = 0;
1216
1217                 /* if it does not need or is spilt
1218                    or is already assigned to registers
1219                    or will not live beyond this instructions */
1220                 if (!sym->nRegs ||
1221                     sym->isspilt ||
1222                     bitVectBitValue (_G.regAssigned, sym->key) ||
1223                     sym->liveTo <= ic->seq)
1224                     continue;
1225
1226                 /* if some liverange has been spilt at the block level
1227                    and this one live beyond this block then spil this
1228                    to be safe */
1229                 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq) {
1230                     spillThis (sym);
1231                     continue;
1232                 }
1233                 /* if trying to allocate this will cause
1234                    a spill and there is nothing to spill
1235                    or this one is rematerializable then
1236                    spill this one */
1237                 willCS = willCauseSpill (sym->nRegs, sym->regType);
1238                 spillable = computeSpillable (ic);
1239                 if (sym->remat || (willCS && bitVectIsZero (spillable))) {
1240                     spillThis (sym);
1241                     continue;
1242                 }
1243
1244                 /* If the live range preceeds the point of definition
1245                    then ideally we must take into account registers that
1246                    have been allocated after sym->liveFrom but freed
1247                    before ic->seq. This is complicated, so spill this
1248                    symbol instead and let fillGaps handle the allocation. */
1249                 if (sym->liveFrom < ic->seq) {
1250                     spillThis (sym);
1251                     continue;
1252                 }
1253
1254                 /* if it has a spillocation & is used less than
1255                    all other live ranges then spill this */
1256                 if (willCS) {
1257                     if (sym->usl.spillLoc) {
1258                         symbol *leastUsed = leastUsedLR (liveRangesWith (spillable,
1259                                                                          allLRs, ebbs[i], ic));
1260                         if (leastUsed && leastUsed->used > sym->used) {
1261                             spillThis (sym);
1262                             continue;
1263                         }
1264                     } else {
1265                         /* if none of the liveRanges have a spillLocation then better
1266                            to spill this one than anything else already assigned to registers */
1267                         if (liveRangesWith(spillable,noSpilLoc,ebbs[i],ic)) {
1268                             /* if this is local to this block then we might find a block spil */
1269                             if (!(sym->liveFrom >= ebbs[i]->fSeq && sym->liveTo <= ebbs[i]->lSeq)) {
1270                                 spillThis (sym);
1271                                 continue;
1272                             }
1273                         }
1274                     }
1275                 }
1276                 /* if we need ptr regs for the right side
1277                    then mark it */
1278                 if (POINTER_GET (ic) && IS_SYMOP (IC_LEFT (ic))
1279                     && getSize (OP_SYMBOL (IC_LEFT (ic))->type) <= (unsigned int) PTRSIZE) {
1280                     mcs51_ptrRegReq++;
1281                     ptrRegSet = 1;
1282                 }
1283                 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic))
1284                     && SPEC_OCLS(OP_SYMBOL (IC_LEFT (ic))->etype) == idata) {
1285                     mcs51_ptrRegReq++;
1286                     ptrRegSet = 1;
1287                 }
1288                 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))
1289                     && SPEC_OCLS(OP_SYMBOL (IC_RIGHT (ic))->etype) == idata) {
1290                     mcs51_ptrRegReq++;
1291                     ptrRegSet = 1;
1292                 }
1293
1294                 /* else we assign registers to it */
1295                 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1296                 _G.totRegAssigned = bitVectSetBit (_G.totRegAssigned, sym->key);
1297
1298                 for (j = 0; j < sym->nRegs; j++) {
1299                     sym->regs[j] = NULL;
1300                     if (sym->regType == REG_PTR)
1301                         sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1302                     else
1303                       {
1304                         if (ic->op == CAST && IS_SYMOP (IC_RIGHT (ic)))
1305                           {
1306                             symbol * right = OP_SYMBOL (IC_RIGHT (ic));
1307
1308                             if (right->regs[j])
1309                               sym->regs[j] = allocThisReg (right->regs[j]);
1310                           }
1311                         if (!sym->regs[j])
1312                           sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1313                       }
1314
1315                     /* if the allocation failed which means
1316                        this was spilt then break */
1317                     if (!sym->regs[j])
1318                       {
1319                         for (i=0; i < sym->nRegs ; i++ )
1320                           sym->regs[i] = NULL;
1321                         break;
1322                       }
1323                 }
1324
1325                 if (!POINTER_SET(ic) && !POINTER_GET(ic)) {
1326                     /* if it shares registers with operands make sure
1327                        that they are in the same position */
1328                     if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1329                         OP_SYMBOL (IC_LEFT (ic))->nRegs) {
1330                         positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1331                                       OP_SYMBOL (IC_LEFT (ic)));
1332                     }
1333                     /* do the same for the right operand */
1334                     if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)) &&
1335                         OP_SYMBOL (IC_RIGHT (ic))->nRegs) {
1336                         positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1337                                       OP_SYMBOL (IC_RIGHT (ic)));
1338                     }
1339                 }
1340
1341                 if (ptrRegSet) {
1342                     mcs51_ptrRegReq--;
1343                     ptrRegSet = 0;
1344                 }
1345
1346             }
1347         }
1348     }
1349
1350     /* Check for and fix any problems with uninitialized operands */
1351     for (i = 0; i < count; i++)
1352       {
1353         iCode *ic;
1354
1355         if (ebbs[i]->noPath &&
1356             (ebbs[i]->entryLabel != entryLabel &&
1357              ebbs[i]->entryLabel != returnLabel))
1358             continue;
1359
1360         for (ic = ebbs[i]->sch; ic; ic = ic->next)
1361           {
1362             if (SKIP_IC2 (ic))
1363               continue;
1364
1365             if (ic->op == IFX)
1366               {
1367                 verifyRegsAssigned (IC_COND (ic), ic);
1368                 continue;
1369               }
1370
1371             if (ic->op == JUMPTABLE)
1372               {
1373                 verifyRegsAssigned (IC_JTCOND (ic), ic);
1374                 continue;
1375               }
1376
1377             verifyRegsAssigned (IC_RESULT (ic), ic);
1378             verifyRegsAssigned (IC_LEFT (ic), ic);
1379             verifyRegsAssigned (IC_RIGHT (ic), ic);
1380           }
1381       }
1382 }
1383
1384 /*-----------------------------------------------------------------*/
1385 /* fillGaps - Try to fill in the Gaps left by Pass1                */
1386 /*-----------------------------------------------------------------*/
1387 static void fillGaps()
1388 {
1389     symbol *sym =NULL;
1390     int key =0;
1391     int pass;
1392     iCode *ic = NULL;
1393
1394     if (getenv("DISABLE_FILL_GAPS")) return;
1395
1396     /* look for liveranges that were spilt by the allocator */
1397     for (sym = hTabFirstItem(liveRanges,&key) ; sym ;
1398          sym = hTabNextItem(liveRanges,&key)) {
1399
1400         int i;
1401         int pdone = 0;
1402
1403         if (!sym->spillA || !sym->clashes || sym->remat) continue ;
1404
1405         /* find the liveRanges this one clashes with, that are
1406            still assigned to registers & mark the registers as used*/
1407         for ( i = 0 ; i < sym->clashes->size ; i ++) {
1408             int k;
1409             symbol *clr;
1410
1411             if (bitVectBitValue(sym->clashes,i) == 0 ||    /* those that clash with this */
1412                 bitVectBitValue(_G.totRegAssigned,i) == 0) /* and are still assigned to registers */
1413                 continue ;
1414
1415             clr = hTabItemWithKey(liveRanges,i);
1416             assert(clr);
1417
1418             /* mark these registers as used */
1419             for (k = 0 ; k < clr->nRegs ; k++ )
1420                 useReg(clr->regs[k]);
1421         }
1422
1423         if (willCauseSpill(sym->nRegs,sym->regType)) {
1424             /* NOPE :( clear all registers & and continue */
1425             freeAllRegs();
1426             continue ;
1427         }
1428
1429         ic = NULL;
1430         for (i = 0 ; i < sym->defs->size ; i++ )
1431           {
1432             if (bitVectBitValue(sym->defs,i))
1433               {
1434                 if (!(ic = hTabItemWithKey(iCodehTab,i)))
1435                   continue;
1436                 if (ic->op == CAST)
1437                   break;
1438               }
1439           }
1440
1441         D(printf("Atemping fillGaps on %s: [",sym->name));
1442         /* THERE IS HOPE !!!! */
1443         for (i=0; i < sym->nRegs ; i++ ) {
1444             if (sym->regType == REG_PTR)
1445                 sym->regs[i] = getRegPtrNoSpil ();
1446             else
1447               {
1448                 sym->regs[i] = NULL;
1449                 if (ic && ic->op == CAST && IS_SYMOP (IC_RIGHT (ic)))
1450                   {
1451                     symbol * right = OP_SYMBOL (IC_RIGHT (ic));
1452
1453                     if (right->regs[i])
1454                       sym->regs[i] = allocThisReg (right->regs[i]);
1455                   }
1456                 if (!sym->regs[i])
1457                   sym->regs[i] = getRegGprNoSpil ();
1458               }
1459             D(printf("%s ", sym->regs[i]->name));
1460         }
1461         D(printf("]\n"));
1462
1463         /* For all its definitions check if the registers
1464            allocated needs positioning NOTE: we can position
1465            only ONCE if more than One positioning required
1466            then give up.
1467            We may need to perform the checks twice; once to
1468            position the registers as needed, the second to
1469            verify any register repositioning is still
1470            compatible.
1471           */
1472         sym->isspilt = 0;
1473         for (pass=0; pass<2; pass++) {
1474             D(printf(" checking definitions\n"));
1475             for (i = 0 ; i < sym->defs->size ; i++ ) {
1476                 if (bitVectBitValue(sym->defs,i)) {
1477                     if (!(ic = hTabItemWithKey(iCodehTab,i))) continue ;
1478                     D(printf("  ic->seq = %d\n", ic->seq));
1479                     if (SKIP_IC(ic)) continue;
1480                     assert(isSymbolEqual(sym,OP_SYMBOL(IC_RESULT(ic)))); /* just making sure */
1481                     /* if left is assigned to registers */
1482                     if (IS_SYMOP(IC_LEFT(ic)))
1483                       {
1484                         D(printf("   left = "));
1485                         D(printOperand(IC_LEFT(ic),NULL));
1486                       }
1487                     if (IS_SYMOP(IC_LEFT(ic)) &&
1488                       bitVectBitValue(_G.totRegAssigned,OP_SYMBOL(IC_LEFT(ic))->key)) {
1489                         pdone += (positionRegs(sym,OP_SYMBOL(IC_LEFT(ic)))>0);
1490                     }
1491                     if (IS_SYMOP(IC_RIGHT(ic)))
1492                       {
1493                         D(printf("   right = "));
1494                         D(printOperand(IC_RIGHT(ic),NULL));
1495                       }
1496                     if (IS_SYMOP(IC_RIGHT(ic)) &&
1497                       bitVectBitValue(_G.totRegAssigned,OP_SYMBOL(IC_RIGHT(ic))->key)) {
1498                         pdone += (positionRegs(sym,OP_SYMBOL(IC_RIGHT(ic)))>0);
1499                     }
1500                     D(printf("   pdone = %d\n", pdone));
1501                     if (pdone > 1) break;
1502                 }
1503             }
1504             D(printf(" checking uses\n"));
1505             for (i = 0 ; i < sym->uses->size ; i++ ) {
1506                 if (bitVectBitValue(sym->uses,i)) {
1507                     iCode *ic;
1508                     if (!(ic = hTabItemWithKey(iCodehTab,i))) continue ;
1509                     D(printf("  ic->seq = %d\n", ic->seq));
1510                     if (SKIP_IC(ic)) continue;
1511                     if (POINTER_SET(ic) || POINTER_GET(ic)) continue ;
1512
1513                     /* if result is assigned to registers */
1514                     if (IS_SYMOP(IC_RESULT(ic)))
1515                       {
1516                         D(printf("   result = "));
1517                         D(printOperand(IC_RESULT(ic),NULL));
1518                       }
1519                     if (IS_SYMOP(IC_RESULT(ic)) &&
1520                         bitVectBitValue(_G.totRegAssigned,OP_SYMBOL(IC_RESULT(ic))->key)) {
1521                         pdone += (positionRegs(sym,OP_SYMBOL(IC_RESULT(ic)))>0);
1522                     }
1523                     D(printf("   pdone = %d\n", pdone));
1524                     if (pdone > 1) break;
1525                 }
1526             }
1527             if (pdone == 0) break; /* second pass only if regs repositioned */
1528             if (pdone > 1) break;
1529         }
1530         D(printf(" sym->regs = ["));
1531         for (i=0; i < sym->nRegs ; i++ )
1532           D(printf("%s ", sym->regs[i]->name));
1533         D(printf("]\n"));
1534         /* had to position more than once GIVE UP */
1535         if (pdone > 1) {
1536             /* UNDO all the changes we made to try this */
1537             sym->isspilt = 1;
1538             for (i=0; i < sym->nRegs ; i++ ) {
1539                     sym->regs[i] = NULL;
1540             }
1541             freeAllRegs();
1542             D(printf ("Fill Gap gave up due to positioning for %s in function %s\n",sym->name, currFunc ? currFunc->name : "UNKNOWN"));
1543             continue ;
1544         }
1545         D(printf ("FILLED GAP for %s in function %s\n",sym->name, currFunc ? currFunc->name : "UNKNOWN"));
1546
1547         _G.totRegAssigned = bitVectSetBit(_G.totRegAssigned,sym->key);
1548         sym->isspilt = sym->spillA = 0 ;
1549         sym->usl.spillLoc->allocreq--;
1550         freeAllRegs();
1551     }
1552 }
1553
1554 /*-----------------------------------------------------------------*/
1555 /* rUmaskForOp :- returns register mask for an operand             */
1556 /*-----------------------------------------------------------------*/
1557 bitVect *
1558 mcs51_rUmaskForOp (operand * op)
1559 {
1560   bitVect *rumask;
1561   symbol *sym;
1562   int j;
1563
1564   /* only temporaries are assigned registers */
1565   if (!IS_ITEMP (op))
1566     return NULL;
1567
1568   sym = OP_SYMBOL (op);
1569
1570   /* if spilt or no registers assigned to it
1571      then nothing */
1572   if (sym->isspilt || !sym->nRegs)
1573     return NULL;
1574
1575   rumask = newBitVect (mcs51_nRegs);
1576
1577   for (j = 0; j < sym->nRegs; j++)
1578     {
1579       if (sym->regs[j]) /* EEP - debug */
1580       rumask = bitVectSetBit (rumask,
1581                               sym->regs[j]->rIdx);
1582     }
1583
1584   return rumask;
1585 }
1586
1587 /*-----------------------------------------------------------------*/
1588 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1589 /*-----------------------------------------------------------------*/
1590 static bitVect *
1591 regsUsedIniCode (iCode * ic)
1592 {
1593   bitVect *rmask = newBitVect (mcs51_nRegs);
1594
1595   /* do the special cases first */
1596   if (ic->op == IFX)
1597     {
1598       rmask = bitVectUnion (rmask,
1599                             mcs51_rUmaskForOp (IC_COND (ic)));
1600       goto ret;
1601     }
1602
1603   /* for the jumptable */
1604   if (ic->op == JUMPTABLE)
1605     {
1606       rmask = bitVectUnion (rmask,
1607                             mcs51_rUmaskForOp (IC_JTCOND (ic)));
1608
1609       goto ret;
1610     }
1611
1612   /* of all other cases */
1613   if (IC_LEFT (ic))
1614     rmask = bitVectUnion (rmask,
1615                           mcs51_rUmaskForOp (IC_LEFT (ic)));
1616
1617
1618   if (IC_RIGHT (ic))
1619     rmask = bitVectUnion (rmask,
1620                           mcs51_rUmaskForOp (IC_RIGHT (ic)));
1621
1622   if (IC_RESULT (ic))
1623     rmask = bitVectUnion (rmask,
1624                           mcs51_rUmaskForOp (IC_RESULT (ic)));
1625
1626 ret:
1627   return rmask;
1628 }
1629
1630 /*-----------------------------------------------------------------*/
1631 /* createRegMask - for each instruction will determine the regsUsed */
1632 /*-----------------------------------------------------------------*/
1633 static void
1634 createRegMask (eBBlock ** ebbs, int count)
1635 {
1636   int i;
1637
1638   /* for all blocks */
1639   for (i = 0; i < count; i++)
1640     {
1641       iCode *ic;
1642
1643       if (ebbs[i]->noPath &&
1644           (ebbs[i]->entryLabel != entryLabel &&
1645            ebbs[i]->entryLabel != returnLabel))
1646         continue;
1647
1648       /* for all instructions */
1649       for (ic = ebbs[i]->sch; ic; ic = ic->next)
1650         {
1651
1652           int j;
1653
1654           if (SKIP_IC2 (ic) || !ic->rlive)
1655             continue;
1656
1657           /* first mark the registers used in this
1658              instruction */
1659           ic->rUsed = regsUsedIniCode (ic);
1660           _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1661
1662           /* now create the register mask for those
1663              registers that are in use : this is a
1664              super set of ic->rUsed */
1665           ic->rMask = newBitVect (mcs51_nRegs + 1);
1666
1667           /* for all live Ranges alive at this point */
1668           for (j = 1; j < ic->rlive->size; j++)
1669             {
1670               symbol *sym;
1671               int k;
1672
1673               /* if not alive then continue */
1674               if (!bitVectBitValue (ic->rlive, j))
1675                 continue;
1676
1677               /* find the live range we are interested in */
1678               if (!(sym = hTabItemWithKey (liveRanges, j)))
1679                 {
1680                   werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
1681                           "createRegMask cannot find live range");
1682                   fprintf(stderr, "\tmissing live range: key=%d\n", j);
1683                   exit (0);
1684                 }
1685
1686               /* if no register assigned to it */
1687               if (!sym->nRegs || sym->isspilt)
1688                 continue;
1689
1690               /* for all the registers allocated to it */
1691               for (k = 0; k < sym->nRegs; k++)
1692                 if (sym->regs[k])
1693                   ic->rMask =
1694                     bitVectSetBit (ic->rMask, sym->regs[k]->rIdx);
1695             }
1696         }
1697     }
1698 }
1699
1700 /*-----------------------------------------------------------------*/
1701 /* rematStr - returns the rematerialized string for a remat var    */
1702 /*-----------------------------------------------------------------*/
1703 static char *
1704 rematStr (symbol * sym)
1705 {
1706   char *s = buffer;
1707   iCode *ic = sym->rematiCode;
1708
1709   *s = 0;
1710
1711   while (1)
1712     {
1713
1714       /* if plus or minus print the right hand side */
1715       if (ic->op == '+' || ic->op == '-')
1716         {
1717           SNPRINTF (s, sizeof(buffer) - strlen(buffer),
1718                     "0x%04x %c ", (int) operandLitValue (IC_RIGHT (ic)),
1719                     ic->op);
1720           s += strlen (s);
1721           ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1722           continue;
1723         }
1724
1725       /* cast then continue */
1726       if (IS_CAST_ICODE(ic)) {
1727           ic = OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
1728           continue;
1729       }
1730       /* we reached the end */
1731       SNPRINTF (s, sizeof(buffer) - strlen(buffer),
1732                 "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1733       break;
1734     }
1735
1736   return buffer;
1737 }
1738
1739 /*-----------------------------------------------------------------*/
1740 /* regTypeNum - computes the type & number of registers required   */
1741 /*-----------------------------------------------------------------*/
1742 static void
1743 regTypeNum (eBBlock *ebbs)
1744 {
1745   symbol *sym;
1746   int k;
1747   iCode *ic;
1748
1749   /* for each live range do */
1750   for (sym = hTabFirstItem (liveRanges, &k); sym;
1751        sym = hTabNextItem (liveRanges, &k))
1752     {
1753
1754       /* if used zero times then no registers needed */
1755       if ((sym->liveTo - sym->liveFrom) == 0)
1756         continue;
1757
1758
1759       /* if the live range is a temporary */
1760       if (sym->isitmp)
1761         {
1762
1763           /* if the type is marked as a conditional */
1764           if (sym->regType == REG_CND)
1765             continue;
1766
1767           /* if used in return only then we don't
1768              need registers */
1769           if (sym->ruonly || sym->accuse)
1770             {
1771               if (IS_AGGREGATE (sym->type) || sym->isptr)
1772                 sym->type = aggrToPtr (sym->type, FALSE);
1773               continue;
1774             }
1775
1776           /* if the symbol has only one definition &
1777              that definition is a get_pointer */
1778           if (bitVectnBitsOn (sym->defs) == 1 &&
1779               (ic = hTabItemWithKey (iCodehTab,
1780                                      bitVectFirstBit (sym->defs))) &&
1781               POINTER_GET (ic) &&
1782               !IS_BITVAR (sym->etype) &&
1783               (aggrToPtrDclType (operandType (IC_LEFT (ic)), FALSE) == POINTER))
1784             {
1785
1786               if (ptrPseudoSymSafe (sym, ic))
1787                 {
1788                   ptrPseudoSymConvert (sym, ic, rematStr (OP_SYMBOL (IC_LEFT (ic))));
1789                   continue;
1790                 }
1791
1792               /* if in data space or idata space then try to
1793                  allocate pointer register */
1794
1795             }
1796
1797           /* if not then we require registers */
1798           sym->nRegs = ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1799                         getSize (sym->type = aggrToPtr (sym->type, FALSE)) :
1800                         getSize (sym->type));
1801
1802           if (sym->nRegs > 4)
1803             {
1804               fprintf (stderr, "allocated more than 4 or 0 registers for type ");
1805               printTypeChain (sym->type, stderr);
1806               fprintf (stderr, "\n");
1807             }
1808
1809           /* determine the type of register required */
1810           if (sym->nRegs == 1 &&
1811               IS_PTR (sym->type) &&
1812               sym->uptr)
1813             sym->regType = REG_PTR;
1814           else
1815             sym->regType = REG_GPR;
1816
1817         }
1818       else
1819         /* for the first run we don't provide */
1820         /* registers for true symbols we will */
1821         /* see how things go                  */
1822         sym->nRegs = 0;
1823     }
1824
1825 }
1826
1827 /*-----------------------------------------------------------------*/
1828 /* freeAllRegs - mark all registers as free                        */
1829 /*-----------------------------------------------------------------*/
1830 static void
1831 freeAllRegs ()
1832 {
1833   int i;
1834
1835   for (i = 0; i < mcs51_nRegs; i++)
1836     regs8051[i].isFree = 1;
1837 }
1838
1839 /*-----------------------------------------------------------------*/
1840 /* deallocStackSpil - this will set the stack pointer back         */
1841 /*-----------------------------------------------------------------*/
1842 static
1843 DEFSETFUNC (deallocStackSpil)
1844 {
1845   symbol *sym = item;
1846
1847   deallocLocal (sym);
1848   return 0;
1849 }
1850
1851 /*-----------------------------------------------------------------*/
1852 /* farSpacePackable - returns the packable icode for far variables */
1853 /*-----------------------------------------------------------------*/
1854 static iCode *
1855 farSpacePackable (iCode * ic)
1856 {
1857   iCode *dic;
1858
1859   /* go thru till we find a definition for the
1860      symbol on the right */
1861   for (dic = ic->prev; dic; dic = dic->prev)
1862     {
1863       /* if the definition is a call then no */
1864       if ((dic->op == CALL || dic->op == PCALL) &&
1865           IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1866         {
1867           return NULL;
1868         }
1869
1870       /* if shift by unknown amount then not */
1871       if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1872           IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1873         return NULL;
1874
1875       /* if pointer get and size > 1 */
1876       if (POINTER_GET (dic) &&
1877           getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) > 1)
1878         return NULL;
1879
1880       if (POINTER_SET (dic) &&
1881           getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)) > 1)
1882         return NULL;
1883
1884       if (dic->op == IFX)
1885         {
1886           if (IC_COND (dic) &&
1887               IS_TRUE_SYMOP (IC_COND (dic)) &&
1888               isOperandInFarSpace (IC_COND (dic)))
1889             return NULL;
1890         }
1891       else if (dic->op == JUMPTABLE)
1892         {
1893           if (IC_JTCOND (dic) &&
1894               IS_TRUE_SYMOP (IC_JTCOND (dic)) &&
1895               isOperandInFarSpace (IC_JTCOND (dic)))
1896             return NULL;
1897         }
1898       else
1899         {
1900           /* if any tree is a true symbol in far space */
1901           if (IC_RESULT (dic) &&
1902               IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1903               isOperandInFarSpace (IC_RESULT (dic)))
1904             return NULL;
1905
1906           if (IC_RIGHT (dic) &&
1907               IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
1908               isOperandInFarSpace (IC_RIGHT (dic)) &&
1909               !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
1910             return NULL;
1911
1912           if (IC_LEFT (dic) &&
1913               IS_TRUE_SYMOP (IC_LEFT (dic)) &&
1914               isOperandInFarSpace (IC_LEFT (dic)) &&
1915               !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
1916             return NULL;
1917         }
1918
1919       if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic)))
1920         {
1921           if ((dic->op == LEFT_OP ||
1922                dic->op == RIGHT_OP ||
1923                dic->op == '-') &&
1924               IS_OP_LITERAL (IC_RIGHT (dic)))
1925             return NULL;
1926           else
1927             return dic;
1928         }
1929     }
1930
1931   return NULL;
1932 }
1933
1934 /*-----------------------------------------------------------------*/
1935 /* packRegsForAssign - register reduction for assignment           */
1936 /*-----------------------------------------------------------------*/
1937 static int
1938 packRegsForAssign (iCode * ic, eBBlock * ebp)
1939 {
1940   iCode *dic, *sic;
1941
1942   if (!IS_ITEMP (IC_RIGHT (ic)) ||
1943       OP_SYMBOL (IC_RIGHT (ic))->isind ||
1944       OP_LIVETO (IC_RIGHT (ic)) > ic->seq)
1945     {
1946       return 0;
1947     }
1948
1949   /* if the true symbol is defined in far space or on stack
1950      then we should not since this will increase register pressure */
1951   if (isOperandInFarSpace(IC_RESULT(ic)) && !farSpacePackable(ic)) {
1952     return 0;
1953   }
1954
1955   /* find the definition of iTempNN scanning backwards if we find a
1956      a use of the true symbol in before we find the definition then
1957      we cannot */
1958   for (dic = ic->prev; dic; dic = dic->prev)
1959     {
1960       int crossedCall = 0;
1961
1962       /* We can pack across a function call only if it's a local */
1963       /* variable or our parameter. Never pack global variables */
1964       /* or parameters to a function we call. */
1965       if ((dic->op == CALL || dic->op == PCALL))
1966         {
1967           if (!OP_SYMBOL (IC_RESULT (ic))->ismyparm
1968               && !OP_SYMBOL (IC_RESULT (ic))->islocal)
1969             {
1970               crossedCall = 1;
1971             }
1972         }
1973
1974       if (SKIP_IC2 (dic))
1975         continue;
1976
1977       if (dic->op == IFX)
1978         {
1979           if (IS_SYMOP (IC_COND (dic)) &&
1980               (IC_COND (dic)->key == IC_RESULT (ic)->key ||
1981                IC_COND (dic)->key == IC_RIGHT (ic)->key))
1982             {
1983               dic = NULL;
1984               break;
1985             }
1986         }
1987       else
1988         {
1989           if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1990               IS_OP_VOLATILE (IC_RESULT (dic)))
1991             {
1992               dic = NULL;
1993               break;
1994             }
1995
1996           if (IS_SYMOP (IC_RESULT (dic)) &&
1997               IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1998             {
1999               if (POINTER_SET (dic))
2000                 dic = NULL;
2001
2002               break;
2003             }
2004
2005           if (IS_SYMOP (IC_RIGHT (dic)) &&
2006               (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
2007                IC_RIGHT (dic)->key == IC_RIGHT (ic)->key))
2008             {
2009               dic = NULL;
2010               break;
2011             }
2012
2013           if (IS_SYMOP (IC_LEFT (dic)) &&
2014               (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
2015                IC_LEFT (dic)->key == IC_RIGHT (ic)->key))
2016             {
2017               dic = NULL;
2018               break;
2019             }
2020
2021           if (IS_SYMOP (IC_RESULT (dic)) &&
2022               IC_RESULT (dic)->key == IC_RESULT (ic)->key)
2023             {
2024               dic = NULL;
2025               break;
2026             }
2027
2028           if (crossedCall)
2029             {
2030               dic = NULL;
2031               break;
2032             }
2033
2034         }
2035     }
2036
2037   if (!dic)
2038     return 0;                   /* did not find */
2039
2040   /* if assignment then check that right is not a bit */
2041   if (ASSIGNMENT (ic) && !POINTER_SET (ic))
2042     {
2043       sym_link *etype = operandType (IC_RESULT (dic));
2044       if (IS_BITFIELD (etype))
2045         {
2046           /* if result is a bit too then it's ok */
2047           etype = operandType (IC_RESULT (ic));
2048           if (!IS_BITFIELD (etype))
2049             {
2050               return 0;
2051             }
2052        }
2053     }
2054 #if 0
2055   /* if assignment then check that right is not a bit */
2056   if (ASSIGNMENT (dic) && !POINTER_SET (dic))
2057     {
2058       sym_link *etype = operandType (IC_RIGHT (dic));
2059       if (IS_BITFIELD (etype))
2060         {
2061           /* if result is a bit too then it's ok */
2062           etype = operandType (IC_RESULT (dic));
2063           if (!IS_BITFIELD (etype))
2064             return 0;
2065         }
2066     }
2067 #endif
2068   /* if the result is on stack or iaccess then it must be
2069      the same atleast one of the operands */
2070   if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
2071       OP_SYMBOL (IC_RESULT (ic))->iaccess)
2072     {
2073
2074       /* the operation has only one symbol
2075          operator then we can pack */
2076       if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
2077           (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
2078         goto pack;
2079
2080       if (!((IC_LEFT (dic) &&
2081              IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
2082             (IC_RIGHT (dic) &&
2083              IC_RESULT (ic)->key == IC_RIGHT (dic)->key)))
2084         return 0;
2085     }
2086 pack:
2087   /* found the definition */
2088   /* replace the result with the result of */
2089   /* this assignment and remove this assignment */
2090   bitVectUnSetBit(OP_SYMBOL(IC_RESULT(dic))->defs,dic->key);
2091   ReplaceOpWithCheaperOp(&IC_RESULT (dic), IC_RESULT (ic));
2092
2093   if (IS_ITEMP (IC_RESULT (dic)) && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq)
2094     {
2095       OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
2096     }
2097   // TODO: and the otherway around?
2098
2099   /* delete from liverange table also
2100      delete from all the points inbetween and the new
2101      one */
2102   for (sic = dic; sic != ic; sic = sic->next)
2103     {
2104       bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
2105       if (IS_ITEMP (IC_RESULT (dic)))
2106         bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
2107     }
2108
2109   remiCodeFromeBBlock (ebp, ic);
2110   bitVectUnSetBit(OP_SYMBOL(IC_RESULT(ic))->defs,ic->key);
2111   hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2112   OP_DEFS(IC_RESULT (dic))=bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2113   return 1;
2114 }
2115
2116 /*------------------------------------------------------------------*/
2117 /* findAssignToSym : scanning backwards looks for first assig found */
2118 /*------------------------------------------------------------------*/
2119 static iCode *
2120 findAssignToSym (operand * op, iCode * ic)
2121 {
2122   iCode *dic;
2123
2124   /* This routine is used to find sequences like
2125      iTempAA = FOO;
2126      ...;  (intervening ops don't use iTempAA or modify FOO)
2127      blah = blah + iTempAA;
2128
2129      and eliminate the use of iTempAA, freeing up its register for
2130      other uses.
2131   */
2132
2133   for (dic = ic->prev; dic; dic = dic->prev)
2134     {
2135
2136       /* if definition by assignment */
2137       if (dic->op == '=' &&
2138           !POINTER_SET (dic) &&
2139           IC_RESULT (dic)->key == op->key
2140 /*          &&  IS_TRUE_SYMOP(IC_RIGHT(dic)) */
2141         )
2142         break;  /* found where this temp was defined */
2143
2144       /* if we find an usage then we cannot delete it */
2145
2146       if (dic->op == IFX)
2147         {
2148           if (IC_COND (dic) && IC_COND (dic)->key == op->key)
2149             return NULL;
2150         }
2151       else if (dic->op == JUMPTABLE)
2152         {
2153           if (IC_JTCOND (dic) && IC_JTCOND (dic)->key == op->key)
2154             return NULL;
2155         }
2156       else
2157         {
2158           if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
2159             return NULL;
2160
2161           if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
2162             return NULL;
2163
2164           if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
2165             return NULL;
2166         }
2167     }
2168
2169   if (!dic)
2170     return NULL;   /* didn't find any assignment to op */
2171
2172   /* we are interested only if defined in far space */
2173   /* or in stack space in case of + & - */
2174
2175   /* if assigned to a non-symbol then don't repack regs */
2176   if (!IS_SYMOP (IC_RIGHT (dic)))
2177     return NULL;
2178
2179   /* if the symbol is volatile then we should not */
2180   if (isOperandVolatile (IC_RIGHT (dic), TRUE))
2181     return NULL;
2182   /* XXX TODO --- should we be passing FALSE to isOperandVolatile()?
2183      What does it mean for an iTemp to be volatile, anyway? Passing
2184      TRUE is more cautious but may prevent possible optimizations */
2185
2186   /* if the symbol is in far space then we should not */
2187   if (isOperandInFarSpace (IC_RIGHT (dic)))
2188     return NULL;
2189
2190   /* for + & - operations make sure that
2191      if it is on the stack it is the same
2192      as one of the three operands */
2193   if ((ic->op == '+' || ic->op == '-') &&
2194       OP_SYMBOL (IC_RIGHT (dic))->onStack)
2195     {
2196
2197       if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key &&
2198           IC_LEFT (ic)->key != IC_RIGHT (dic)->key &&
2199           IC_RIGHT (ic)->key != IC_RIGHT (dic)->key)
2200         return NULL;
2201     }
2202
2203   /* now make sure that the right side of dic
2204      is not defined between ic & dic */
2205   if (dic)
2206     {
2207       iCode *sic = dic->next;
2208
2209       for (; sic != ic; sic = sic->next)
2210         if (IC_RESULT (sic) &&
2211             IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
2212           return NULL;
2213     }
2214
2215   return dic;
2216 }
2217
2218 /*-----------------------------------------------------------------*/
2219 /* reassignAliasedSym - used by packRegsForSupport to replace      */
2220 /*                      redundant iTemp with equivalent symbol     */
2221 /*-----------------------------------------------------------------*/
2222 static void
2223 reassignAliasedSym (eBBlock *ebp, iCode *assignment, iCode *use, operand *op)
2224 {
2225   iCode *ic;
2226   unsigned oldSymKey, newSymKey;
2227
2228   oldSymKey = op->key;
2229   newSymKey = IC_RIGHT(assignment)->key;
2230
2231   /* only track live ranges of compiler-generated temporaries */
2232   if (!IS_ITEMP(IC_RIGHT(assignment)))
2233     newSymKey = 0;
2234
2235   /* update the live-value bitmaps */
2236   for (ic = assignment; ic != use; ic = ic->next) {
2237     bitVectUnSetBit (ic->rlive, oldSymKey);
2238     if (newSymKey != 0)
2239       ic->rlive = bitVectSetBit (ic->rlive, newSymKey);
2240   }
2241
2242   /* update the sym of the used operand */
2243   OP_SYMBOL(op) = OP_SYMBOL(IC_RIGHT(assignment));
2244   op->key = OP_SYMBOL(op)->key;
2245   OP_SYMBOL(op)->accuse = 0;
2246
2247   /* update the sym's liverange */
2248   if ( OP_LIVETO(op) < ic->seq )
2249     setToRange(op, ic->seq, FALSE);
2250
2251   /* remove the assignment iCode now that its result is unused */
2252   remiCodeFromeBBlock (ebp, assignment);
2253   bitVectUnSetBit(OP_SYMBOL(IC_RESULT(assignment))->defs, assignment->key);
2254   hTabDeleteItem (&iCodehTab, assignment->key, assignment, DELETE_ITEM, NULL);
2255 }
2256
2257
2258 /*-----------------------------------------------------------------*/
2259 /* packRegsForSupport :- reduce some registers for support calls   */
2260 /*-----------------------------------------------------------------*/
2261 static int
2262 packRegsForSupport (iCode * ic, eBBlock * ebp)
2263 {
2264   iCode *dic;
2265
2266   /* for the left & right operand :- look to see if the
2267      left was assigned a true symbol in far space in that
2268      case replace them */
2269
2270   if (IS_ITEMP (IC_LEFT (ic)) &&
2271       OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq)
2272     {
2273       dic = findAssignToSym (IC_LEFT (ic), ic);
2274
2275       if (dic)
2276         {
2277           /* found it we need to remove it from the block */
2278           reassignAliasedSym (ebp, dic, ic, IC_LEFT(ic));
2279           return 1;
2280         }
2281     }
2282
2283   /* do the same for the right operand */
2284   if (IS_ITEMP (IC_RIGHT (ic)) &&
2285       OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq)
2286     {
2287       iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
2288
2289       if (dic)
2290         {
2291           /* if this is a subtraction & the result
2292              is a true symbol in far space then don't pack */
2293           if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic)))
2294             {
2295               sym_link *etype = getSpec (operandType (IC_RESULT (dic)));
2296               if (IN_FARSPACE (SPEC_OCLS (etype)))
2297                 return 0;
2298             }
2299           /* found it we need to remove it from the
2300              block */
2301           reassignAliasedSym (ebp, dic, ic, IC_RIGHT(ic));
2302
2303           return 1;
2304         }
2305     }
2306
2307   return 0;
2308 }
2309
2310 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
2311
2312
2313 /*-----------------------------------------------------------------*/
2314 /* packRegsForOneuse : - will reduce some registers for single Use */
2315 /*-----------------------------------------------------------------*/
2316 static iCode *
2317 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
2318 {
2319   iCode *dic, *sic;
2320
2321   /* if returning a literal then do nothing */
2322   if (!IS_ITEMP (op))
2323     return NULL;
2324
2325   /* if rematerializable or already return use then do nothing */
2326   if (OP_SYMBOL(op)->remat || OP_SYMBOL(op)->ruonly)
2327     return NULL;
2328
2329   /* only upto 2 bytes since we cannot predict
2330      the usage of b, & acc */
2331   if (getSize (operandType (op)) > (fReturnSizeMCS51 - 2))
2332     return NULL;
2333
2334   if (ic->op != RETURN &&
2335       ic->op != SEND &&
2336       !POINTER_SET (ic) &&
2337       !POINTER_GET (ic))
2338     return NULL;
2339
2340   if (ic->op == SEND && ic->argreg != 1) return NULL;
2341
2342   /* this routine will mark the a symbol as used in one
2343      instruction use only && if the defintion is local
2344      (ie. within the basic block) && has only one definition &&
2345      that definiion is either a return value from a
2346      function or does not contain any variables in
2347      far space */
2348   if (bitVectnBitsOn (OP_USES (op)) > 1)
2349     return NULL;
2350
2351   /* if it has only one defintion */
2352   if (bitVectnBitsOn (OP_DEFS (op)) > 1)
2353     return NULL;                /* has more than one definition */
2354
2355   /* get that definition */
2356   if (!(dic =
2357         hTabItemWithKey (iCodehTab,
2358                          bitVectFirstBit (OP_DEFS (op)))))
2359     return NULL;
2360
2361   /* if that only usage is a cast */
2362   if (dic->op == CAST) {
2363     /* to a bigger type */
2364     if (getSize(OP_SYM_TYPE(IC_RESULT(dic))) >
2365         getSize(OP_SYM_TYPE(IC_RIGHT(dic)))) {
2366       /* than we can not, since we cannot predict the usage of b & acc */
2367       return NULL;
2368     }
2369   }
2370
2371   /* found the definition now check if it is local */
2372   if (dic->seq < ebp->fSeq ||
2373       dic->seq > ebp->lSeq)
2374     return NULL;                /* non-local */
2375
2376   /* now check if it is the return from
2377      a function call */
2378   if (dic->op == CALL || dic->op == PCALL)
2379     {
2380       if (ic->op != SEND && ic->op != RETURN &&
2381           !POINTER_SET(ic) && !POINTER_GET(ic))
2382         {
2383           OP_SYMBOL (op)->ruonly = 1;
2384           return dic;
2385         }
2386     }
2387   else
2388     {
2389   /* otherwise check that the definition does
2390      not contain any symbols in far space */
2391   if (isOperandInFarSpace (IC_LEFT (dic)) ||
2392       isOperandInFarSpace (IC_RIGHT (dic)) ||
2393       IS_OP_RUONLY (IC_LEFT (ic)) ||
2394       IS_OP_RUONLY (IC_RIGHT (ic)))
2395     {
2396       return NULL;
2397     }
2398
2399   /* if pointer set then make sure the pointer
2400      is one byte */
2401   if (POINTER_SET (dic) &&
2402       !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
2403     return NULL;
2404
2405   if (POINTER_GET (dic) &&
2406       !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
2407     return NULL;
2408     }
2409
2410   /* Make sure no overlapping liverange is already assigned to DPTR */
2411   if (OP_SYMBOL(op)->clashes)
2412     {
2413       symbol *sym;
2414       int i;
2415
2416       for (i = 0 ; i < OP_SYMBOL(op)->clashes->size ; i++ )
2417         {
2418           if (bitVectBitValue(OP_SYMBOL(op)->clashes,i))
2419             {
2420               sym = hTabItemWithKey(liveRanges,i);
2421               if (sym->ruonly)
2422                 return NULL ;
2423             }
2424         }
2425     }
2426
2427   sic = dic;
2428
2429   /* also make sure the intervenening instructions
2430      don't have any thing in far space */
2431   for (dic = dic->next; dic && dic != ic && sic != ic; dic = dic->next)
2432     {
2433
2434       /* if there is an intervening function call then no */
2435       if (dic->op == CALL || dic->op == PCALL)
2436         return NULL;
2437       /* if pointer set then make sure the pointer
2438          is one byte */
2439       if (POINTER_SET (dic) &&
2440           !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
2441         return NULL;
2442
2443       if (POINTER_GET (dic) &&
2444           !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
2445         return NULL;
2446
2447       /* if address of & the result is remat the okay */
2448       if (dic->op == ADDRESS_OF &&
2449           OP_SYMBOL (IC_RESULT (dic))->remat)
2450         continue;
2451
2452       /* if operand has size of three or more & this
2453          operation is a '*','/' or '%' then 'b' may
2454          cause a problem */
2455       if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
2456           getSize (operandType (op)) >= 3)
2457         return NULL;
2458
2459       /* if left or right or result is in far space */
2460       if (isOperandInFarSpace (IC_LEFT (dic)) ||
2461           isOperandInFarSpace (IC_RIGHT (dic)) ||
2462           isOperandInFarSpace (IC_RESULT (dic)) ||
2463           IS_OP_RUONLY (IC_LEFT (dic)) ||
2464           IS_OP_RUONLY (IC_RIGHT (dic)) ||
2465           IS_OP_RUONLY (IC_RESULT (dic)))
2466         {
2467           return NULL;
2468         }
2469       /* if left or right or result is on stack */
2470       if (isOperandOnStack(IC_LEFT(dic)) ||
2471           isOperandOnStack(IC_RIGHT(dic)) ||
2472           isOperandOnStack(IC_RESULT(dic))) {
2473         return NULL;
2474       }
2475     }
2476
2477   OP_SYMBOL (op)->ruonly = 1;
2478   return sic;
2479 }
2480
2481 /*-----------------------------------------------------------------*/
2482 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN          */
2483 /*-----------------------------------------------------------------*/
2484 static bool
2485 isBitwiseOptimizable (iCode * ic)
2486 {
2487   sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
2488   sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
2489
2490   /* bitwise operations are considered optimizable
2491      under the following conditions (Jean-Louis VERN)
2492
2493      x & lit
2494      bit & bit
2495      bit & x
2496      bit ^ bit
2497      bit ^ x
2498      x   ^ lit
2499      x   | lit
2500      bit | bit
2501      bit | x
2502   */
2503   if (IS_LITERAL(rtype) ||
2504       (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
2505     return TRUE;
2506   else
2507     return FALSE;
2508 }
2509
2510 /*-----------------------------------------------------------------*/
2511 /* isCommutativeOp - tests whether this op cares what order its    */
2512 /*                   operands are in                               */
2513 /*-----------------------------------------------------------------*/
2514 bool isCommutativeOp(unsigned int op)
2515 {
2516   if (op == '+' || op == '*' || op == EQ_OP ||
2517       op == '^' || op == '|' || op == BITWISEAND)
2518     return TRUE;
2519   else
2520     return FALSE;
2521 }
2522
2523 /*-----------------------------------------------------------------*/
2524 /* operandUsesAcc - determines whether the code generated for this */
2525 /*                  operand will have to use the accumulator       */
2526 /*-----------------------------------------------------------------*/
2527 bool operandUsesAcc(operand *op)
2528 {
2529   if (!op)
2530     return FALSE;
2531
2532   if (IS_SYMOP(op)) {
2533     symbol *sym = OP_SYMBOL(op);
2534     memmap *symspace;
2535
2536     if (sym->accuse)
2537       return TRUE;  /* duh! */
2538
2539     if (IN_STACK(sym->etype) || sym->onStack ||
2540         (SPIL_LOC(op) && SPIL_LOC(op)->onStack))
2541       return TRUE;  /* acc is used to calc stack offset */
2542
2543     if (IS_ITEMP(op))
2544       {
2545         if (SPIL_LOC(op)) {
2546           sym = SPIL_LOC(op);  /* if spilled, look at spill location */
2547         } else {
2548           return FALSE;  /* more checks? */
2549         }
2550       }
2551
2552     symspace = SPEC_OCLS(sym->etype);
2553
2554     if (sym->iaccess && symspace->paged)
2555       return TRUE;  /* must fetch paged indirect sym via accumulator */
2556
2557     if (IN_BITSPACE(symspace))
2558       return TRUE;  /* fetching bit vars uses the accumulator */
2559
2560     if (IN_FARSPACE(symspace) || IN_CODESPACE(symspace))
2561       return TRUE;  /* fetched via accumulator and dptr */
2562   }
2563
2564   return FALSE;
2565 }
2566
2567 /*-----------------------------------------------------------------*/
2568 /* packRegsForAccUse - pack registers for acc use                  */
2569 /*-----------------------------------------------------------------*/
2570 static void
2571 packRegsForAccUse (iCode * ic)
2572 {
2573   iCode *uic;
2574
2575   /* if this is an aggregate, e.g. a one byte char array */
2576   if (IS_AGGREGATE(operandType(IC_RESULT(ic)))) {
2577     return;
2578   }
2579
2580   /* if we are calling a reentrant function that has stack parameters */
2581   if (ic->op == CALL &&
2582        IFFUNC_ISREENT(operandType(IC_LEFT(ic))) &&
2583        FUNC_HASSTACKPARM(operandType(IC_LEFT(ic))))
2584       return;
2585
2586   if (ic->op == PCALL &&
2587        IFFUNC_ISREENT(operandType(IC_LEFT(ic))->next) &&
2588        FUNC_HASSTACKPARM(operandType(IC_LEFT(ic))->next))
2589       return;
2590
2591   /* if + or - then it has to be one byte result */
2592   if ((ic->op == '+' || ic->op == '-')
2593       && getSize (operandType (IC_RESULT (ic))) > 1)
2594     return;
2595
2596   /* if shift operation make sure right side is not a literal */
2597   if (ic->op == RIGHT_OP &&
2598       (isOperandLiteral (IC_RIGHT (ic)) ||
2599        getSize (operandType (IC_RESULT (ic))) > 1))
2600     return;
2601
2602   if (ic->op == LEFT_OP &&
2603       (isOperandLiteral (IC_RIGHT (ic)) ||
2604        getSize (operandType (IC_RESULT (ic))) > 1))
2605     return;
2606
2607   if (IS_BITWISE_OP (ic) &&
2608       getSize (operandType (IC_RESULT (ic))) > 1)
2609     return;
2610
2611
2612   /* has only one definition */
2613   if (bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) > 1)
2614     return;
2615
2616   /* has only one use */
2617   if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) > 1)
2618     return;
2619
2620   /* and the usage immediately follows this iCode */
2621   if (!(uic = hTabItemWithKey (iCodehTab,
2622                                bitVectFirstBit (OP_USES (IC_RESULT (ic))))))
2623     return;
2624
2625   if (ic->next != uic)
2626     return;
2627
2628   /* if it is a conditional branch then we definitely can */
2629   if (uic->op == IFX)
2630     goto accuse;
2631
2632   if (uic->op == JUMPTABLE)
2633     return;
2634
2635   if (POINTER_SET (uic) &&
2636       getSize (aggrToPtr (operandType (IC_RESULT (uic)), FALSE)) > 1)
2637     return;
2638
2639   /* if the usage is not is an assignment
2640      or an arithmetic / bitwise / shift operation then not */
2641   if (uic->op != '=' &&
2642       !IS_ARITHMETIC_OP (uic) &&
2643       !IS_BITWISE_OP (uic) &&
2644       uic->op != LEFT_OP &&
2645       uic->op != RIGHT_OP)
2646     return;
2647
2648   /* if used in ^ operation then make sure right is not a
2649      literal (WIML: Why is this?) */
2650   if (uic->op == '^' && isOperandLiteral (IC_RIGHT (uic)))
2651     return;
2652
2653   /* if shift operation make sure right side is not a literal */
2654   /* WIML: Why is this? */
2655   if (uic->op == RIGHT_OP &&
2656       (isOperandLiteral (IC_RIGHT (uic)) ||
2657        getSize (operandType (IC_RESULT (uic))) > 1))
2658     return;
2659   if (uic->op == LEFT_OP &&
2660       (isOperandLiteral (IC_RIGHT (uic)) ||
2661        getSize (operandType (IC_RESULT (uic))) > 1))
2662     return;
2663
2664   /* make sure that the result of this icode is not on the
2665      stack, since acc is used to compute stack offset */
2666 #if 0
2667   if (IS_TRUE_SYMOP (IC_RESULT (uic)) &&
2668       OP_SYMBOL (IC_RESULT (uic))->onStack)
2669     return;
2670 #else
2671   if (isOperandOnStack(IC_RESULT(uic)))
2672     return;
2673 #endif
2674
2675   /* if the usage has only one operand then we can */
2676   if (IC_LEFT (uic) == NULL ||
2677       IC_RIGHT (uic) == NULL)
2678     goto accuse;
2679
2680   /* if the other operand uses the accumulator then we cannot */
2681   if ( (IC_LEFT(uic)->key == IC_RESULT(ic)->key &&
2682         operandUsesAcc(IC_RIGHT(uic))) ||
2683        (IC_RIGHT(uic)->key == IC_RESULT(ic)->key &&
2684         operandUsesAcc(IC_LEFT(uic))) )
2685     return;
2686
2687   /* make sure this is on the left side if not commutative */
2688   /* except for '-', which has been written to be able to
2689      handle reversed operands */
2690   if (!(isCommutativeOp(ic->op) || ic->op == '-') &&
2691        IC_LEFT (uic)->key != IC_RESULT (ic)->key)
2692     return;
2693
2694 #if 0
2695   // this is too dangerous and need further restrictions
2696   // see bug #447547
2697
2698   /* if one of them is a literal then we can */
2699   if ((IC_LEFT (uic) && IS_OP_LITERAL (IC_LEFT (uic))) ||
2700       (IC_RIGHT (uic) && IS_OP_LITERAL (IC_RIGHT (uic))))
2701     {
2702       OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2703       return;
2704     }
2705 #endif
2706
2707 accuse:
2708   OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2709
2710 }
2711
2712 /*-----------------------------------------------------------------*/
2713 /* packForPush - hueristics to reduce iCode for pushing            */
2714 /*-----------------------------------------------------------------*/
2715 static void
2716 packForPush (iCode * ic, eBBlock ** ebpp, int blockno)
2717 {
2718   iCode *dic, *lic;
2719   bitVect *dbv;
2720   struct eBBlock * ebp=ebpp[blockno];
2721
2722   if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
2723     return;
2724
2725   /* must have only definition & one usage */
2726   if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
2727       bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
2728     return;
2729
2730   /* find the definition */
2731   if (!(dic = hTabItemWithKey (iCodehTab,
2732                                bitVectFirstBit (OP_DEFS (IC_LEFT (ic))))))
2733     return;
2734
2735   if (dic->op != '=' || POINTER_SET (dic))
2736     return;
2737
2738   if (dic->seq < ebp->fSeq) { // Evelyn did this
2739     int i;
2740     for (i=0; i<blockno; i++) {
2741       if (dic->seq >= ebpp[i]->fSeq && dic->seq <= ebpp[i]->lSeq) {
2742         ebp=ebpp[i];
2743         break;
2744       }
2745     }
2746     wassert (i!=blockno); // no way to recover from here
2747   }
2748
2749   if (IS_SYMOP(IC_RIGHT(dic))) {
2750     /* make sure the right side does not have any definitions
2751        inbetween */
2752     dbv = OP_DEFS(IC_RIGHT(dic));
2753     for (lic = ic; lic && lic != dic ; lic = lic->prev) {
2754       if (bitVectBitValue(dbv,lic->key))
2755         return ;
2756     }
2757     /* make sure they have the same type */
2758     if (IS_SPEC(operandType(IC_LEFT(ic))))
2759     {
2760       sym_link *itype=operandType(IC_LEFT(ic));
2761       sym_link *ditype=operandType(IC_RIGHT(dic));
2762
2763       if (SPEC_USIGN(itype)!=SPEC_USIGN(ditype) ||
2764           SPEC_LONG(itype)!=SPEC_LONG(ditype))
2765         return;
2766     }
2767     /* extend the live range of replaced operand if needed */
2768     if (OP_SYMBOL(IC_RIGHT(dic))->liveTo < ic->seq) {
2769       OP_SYMBOL(IC_RIGHT(dic))->liveTo = ic->seq;
2770     }
2771     bitVectUnSetBit(OP_SYMBOL(IC_RESULT(dic))->defs,dic->key);
2772   }
2773
2774   /* we now we know that it has one & only one def & use
2775      and the that the definition is an assignment */
2776   ReplaceOpWithCheaperOp(&IC_LEFT (ic), IC_RIGHT (dic));
2777   remiCodeFromeBBlock (ebp, dic);
2778   hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
2779 }
2780
2781 /*-----------------------------------------------------------------*/
2782 /* packRegisters - does some transformations to reduce register    */
2783 /*                   pressure                                      */
2784 /*-----------------------------------------------------------------*/
2785 static void
2786 packRegisters (eBBlock ** ebpp, int blockno)
2787 {
2788   iCode *ic;
2789   int change = 0;
2790   eBBlock *ebp=ebpp[blockno];
2791
2792   while (1)
2793     {
2794       change = 0;
2795
2796       /* look for assignments of the form */
2797       /* iTempNN = TRueSym (someoperation) SomeOperand */
2798       /*       ....                       */
2799       /* TrueSym := iTempNN:1             */
2800       for (ic = ebp->sch; ic; ic = ic->next)
2801         {
2802           /* find assignment of the form TrueSym := iTempNN:1 */
2803           if (ic->op == '=' && !POINTER_SET (ic))
2804             change += packRegsForAssign (ic, ebp);
2805         }
2806
2807       if (!change)
2808         break;
2809     }
2810
2811   for (ic = ebp->sch; ic; ic = ic->next)
2812     {
2813       /* Fix for bug #979599:   */
2814       /* P0 &= ~1;              */
2815
2816       /* Look for two subsequent iCodes with */
2817       /*   iTemp := _c;         */
2818       /*   _c = iTemp & op;     */
2819       /* and replace them by    */
2820       /*   iTemp := _c;         */
2821       /*   _c = _c & op;        */
2822       if ((ic->op == BITWISEAND || ic->op == '|' || ic->op == '^') &&
2823           ic->prev &&
2824           ic->prev->op == '=' &&
2825           IS_ITEMP (IC_LEFT (ic)) &&
2826           IC_LEFT (ic) == IC_RESULT (ic->prev) &&
2827           isOperandEqual (IC_RESULT(ic), IC_RIGHT(ic->prev)))
2828         {
2829           iCode* ic_prev = ic->prev;
2830           symbol* prev_result_sym = OP_SYMBOL (IC_RESULT (ic_prev));
2831
2832           ReplaceOpWithCheaperOp (&IC_LEFT (ic), IC_RESULT (ic));
2833           if (IC_RESULT (ic_prev) != IC_RIGHT (ic))
2834             {
2835               bitVectUnSetBit (OP_USES (IC_RESULT (ic_prev)), ic->key);
2836               if (/*IS_ITEMP (IC_RESULT (ic_prev)) && */
2837                   prev_result_sym->liveTo == ic->seq)
2838                 {
2839                   prev_result_sym->liveTo = ic_prev->seq;
2840                 }
2841             }
2842           bitVectSetBit (OP_USES (IC_RESULT (ic)), ic->key);
2843
2844           bitVectSetBit (ic->rlive, IC_RESULT (ic)->key);
2845
2846           if (bitVectIsZero (OP_USES (IC_RESULT (ic_prev))))
2847             {
2848               bitVectUnSetBit (ic->rlive, IC_RESULT (ic)->key);
2849               bitVectUnSetBit (OP_DEFS (IC_RESULT (ic_prev)), ic_prev->key);
2850               remiCodeFromeBBlock (ebp, ic_prev);
2851               hTabDeleteItem (&iCodehTab, ic_prev->key, ic_prev, DELETE_ITEM, NULL);
2852             }
2853         }
2854
2855       /* if this is an itemp & result of an address of a true sym
2856          then mark this as rematerialisable   */
2857       if (ic->op == ADDRESS_OF &&
2858           IS_ITEMP (IC_RESULT (ic)) &&
2859           IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2860           bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2861           !OP_SYMBOL (IC_LEFT (ic))->onStack)
2862         {
2863           OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2864           OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2865           OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2866         }
2867
2868       /* if straight assignment then carry remat flag if
2869          this is the only definition */
2870       if (ic->op == '=' &&
2871           !POINTER_SET (ic) &&
2872           IS_SYMOP (IC_RIGHT (ic)) &&
2873           OP_SYMBOL (IC_RIGHT (ic))->remat &&
2874           !IS_CAST_ICODE(OP_SYMBOL (IC_RIGHT (ic))->rematiCode) &&
2875           bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1)
2876         {
2877           OP_SYMBOL (IC_RESULT (ic))->remat =
2878             OP_SYMBOL (IC_RIGHT (ic))->remat;
2879           OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2880             OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2881         }
2882
2883       /* if cast to a generic pointer & the pointer being
2884          cast is remat, then we can remat this cast as well */
2885       if (ic->op == CAST &&
2886           IS_SYMOP(IC_RIGHT(ic)) &&
2887           OP_SYMBOL(IC_RIGHT(ic))->remat &&
2888           bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1)
2889         {
2890           sym_link *to_type = operandType(IC_LEFT(ic));
2891           sym_link *from_type = operandType(IC_RIGHT(ic));
2892           if (IS_GENPTR(to_type) && IS_PTR(from_type))
2893             {
2894               OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2895               OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2896               OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2897             }
2898         }
2899
2900       /* if this is a +/- operation with a rematerizable
2901          then mark this as rematerializable as well */
2902       if ((ic->op == '+' || ic->op == '-') &&
2903           (IS_SYMOP (IC_LEFT (ic)) &&
2904            IS_ITEMP (IC_RESULT (ic)) &&
2905            IS_OP_LITERAL (IC_RIGHT (ic))) &&
2906            OP_SYMBOL (IC_LEFT (ic))->remat &&
2907           (!IS_SYMOP (IC_RIGHT (ic)) || !IS_CAST_ICODE(OP_SYMBOL (IC_RIGHT (ic))->rematiCode)) &&
2908            bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1)
2909         {
2910           OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2911           OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2912           OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2913         }
2914
2915       /* mark the pointer usages */
2916       if (POINTER_SET (ic))
2917         OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2918
2919       if (POINTER_GET (ic) &&
2920           IS_SYMOP(IC_LEFT (ic)))
2921         OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2922
2923       if (!SKIP_IC2 (ic))
2924         {
2925           /* if we are using a symbol on the stack
2926              then we should say mcs51_ptrRegReq */
2927           if (options.useXstack && ic->parmPush
2928               && (ic->op == IPUSH || ic->op == IPOP))
2929             mcs51_ptrRegReq++;
2930           if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
2931             mcs51_ptrRegReq += ((OP_SYMBOL (IC_COND (ic))->onStack ||
2932                                  OP_SYMBOL (IC_COND (ic))->iaccess ||
2933                                  SPEC_OCLS(OP_SYMBOL (IC_COND (ic))->etype) == idata) ? 1 : 0);
2934           else if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
2935             mcs51_ptrRegReq += ((OP_SYMBOL (IC_JTCOND (ic))->onStack ||
2936                               OP_SYMBOL (IC_JTCOND (ic))->iaccess ||
2937                               SPEC_OCLS(OP_SYMBOL (IC_JTCOND (ic))->etype) == idata) ? 1 : 0);
2938           else
2939             {
2940               if (IS_SYMOP (IC_LEFT (ic)))
2941                 mcs51_ptrRegReq += ((OP_SYMBOL (IC_LEFT (ic))->onStack ||
2942                                 OP_SYMBOL (IC_LEFT (ic))->iaccess ||
2943                                 SPEC_OCLS(OP_SYMBOL (IC_LEFT (ic))->etype) == idata) ? 1 : 0);
2944               if (IS_SYMOP (IC_RIGHT (ic)))
2945                 mcs51_ptrRegReq += ((OP_SYMBOL (IC_RIGHT (ic))->onStack ||
2946                                OP_SYMBOL (IC_RIGHT (ic))->iaccess ||
2947                                SPEC_OCLS(OP_SYMBOL (IC_RIGHT (ic))->etype) == idata) ? 1 : 0);
2948               if (IS_SYMOP (IC_RESULT (ic)))
2949                 mcs51_ptrRegReq += ((OP_SYMBOL (IC_RESULT (ic))->onStack ||
2950                               OP_SYMBOL (IC_RESULT (ic))->iaccess ||
2951                               SPEC_OCLS(OP_SYMBOL (IC_RESULT (ic))->etype) == idata) ? 1 : 0);
2952               if (POINTER_GET (ic) && IS_SYMOP (IC_LEFT (ic))
2953                   && getSize (OP_SYMBOL (IC_LEFT (ic))->type) <= (unsigned int) PTRSIZE)
2954                 mcs51_ptrRegReq ++;
2955               if (POINTER_SET (ic) && IS_SYMOP (IC_RESULT (ic))
2956                   && getSize (OP_SYMBOL (IC_RESULT (ic))->type) <= (unsigned int) PTRSIZE)
2957                 mcs51_ptrRegReq ++;
2958             }
2959         }
2960
2961       /* if the condition of an if instruction
2962          is defined in the previous instruction and
2963          this is the only usage then
2964          mark the itemp as a conditional */
2965       if ((IS_CONDITIONAL (ic) ||
2966            (IS_BITWISE_OP(ic) && isBitwiseOptimizable (ic)) ||
2967            (POINTER_GET (ic) && getSize (operandType (IC_RESULT (ic))) <=1)) &&
2968           ic->next && ic->next->op == IFX &&
2969           bitVectnBitsOn (OP_USES(IC_RESULT(ic)))==1 &&
2970           isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2971           OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq)
2972         {
2973           OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2974           continue;
2975         }
2976
2977       /* if the condition of an if instruction
2978          is defined in the previous GET_POINTER instruction and
2979          this is the only usage then
2980          mark the itemp as accumulator use */
2981       if ((POINTER_GET (ic) && getSize (operandType (IC_RESULT (ic))) <=1) &&
2982           ic->next && ic->next->op == IFX &&
2983           bitVectnBitsOn (OP_USES(IC_RESULT(ic)))==1 &&
2984           isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2985           OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq)
2986         {
2987           OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2988           continue;
2989         }
2990
2991       /* reduce for support function calls */
2992       if (ic->supportRtn || ic->op == '+' || ic->op == '-')
2993         packRegsForSupport (ic, ebp);
2994
2995       /* some cases the redundant moves can
2996          can be eliminated for return statements */
2997       if ((ic->op == RETURN || (ic->op == SEND && ic->argreg == 1)) &&
2998           !isOperandInFarSpace (IC_LEFT (ic)) &&
2999           options.model == MODEL_SMALL) {
3000         packRegsForOneuse (ic, IC_LEFT (ic), ebp);
3001       }
3002
3003       /* if pointer set & left has a size more than
3004          one and right is not in far space */
3005       if (POINTER_SET (ic) &&
3006           !isOperandInFarSpace (IC_RIGHT (ic)) &&
3007           !OP_SYMBOL (IC_RESULT (ic))->remat &&
3008           !IS_OP_RUONLY (IC_RIGHT (ic)) &&
3009           getSize (aggrToPtr (operandType (IC_RESULT (ic)), FALSE)) > 1)
3010         packRegsForOneuse (ic, IC_RESULT (ic), ebp);
3011
3012       /* if pointer get */
3013       if (POINTER_GET (ic) &&
3014           IS_SYMOP (IC_LEFT (ic)) &&
3015           !isOperandInFarSpace (IC_RESULT (ic)) &&
3016           !OP_SYMBOL (IC_LEFT (ic))->remat &&
3017           !IS_OP_RUONLY (IC_RESULT (ic)) &&
3018           getSize (aggrToPtr (operandType (IC_LEFT (ic)), FALSE)) > 1)
3019         packRegsForOneuse (ic, IC_LEFT (ic), ebp);
3020
3021
3022       /* if this is a cast for intergral promotion then
3023          check if it's the only use of the definition of the
3024          operand being casted/ if yes then replace
3025          the result of that arithmetic operation with
3026          this result and get rid of the cast */
3027       if (ic->op == CAST)
3028         {
3029           sym_link *fromType = operandType (IC_RIGHT (ic));
3030           sym_link *toType = operandType (IC_LEFT (ic));
3031
3032           if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
3033               getSize (fromType) != getSize (toType) &&
3034               SPEC_USIGN (fromType) == SPEC_USIGN (toType))
3035             {
3036
3037               iCode *dic = packRegsForOneuse (ic, IC_RIGHT (ic), ebp);
3038               if (dic)
3039                 {
3040                   if (IS_ARITHMETIC_OP (dic))
3041                     {
3042                       bitVectUnSetBit(OP_SYMBOL(IC_RESULT(dic))->defs,dic->key);
3043                       ReplaceOpWithCheaperOp(&IC_RESULT (dic), IC_RESULT (ic));
3044                       remiCodeFromeBBlock (ebp, ic);
3045                       bitVectUnSetBit(OP_SYMBOL(IC_RESULT(ic))->defs,ic->key);
3046                       hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
3047                       OP_DEFS(IC_RESULT (dic))=bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
3048                       ic = ic->prev;
3049                     }
3050                   else
3051                     OP_SYMBOL (IC_RIGHT (ic))->ruonly = 0;
3052                 }
3053             }
3054           else
3055             {
3056
3057               /* if the type from and type to are the same
3058                  then if this is the only use then packit */
3059               if (compareType (operandType (IC_RIGHT (ic)),
3060                              operandType (IC_LEFT (ic))) == 1)
3061                 {
3062                   iCode *dic = packRegsForOneuse (ic, IC_RIGHT (ic), ebp);
3063                   if (dic)
3064                     {
3065                       bitVectUnSetBit(OP_SYMBOL(IC_RESULT(dic))->defs,dic->key);
3066                       ReplaceOpWithCheaperOp(&IC_RESULT (dic), IC_RESULT (ic));
3067                       remiCodeFromeBBlock (ebp, ic);
3068                       bitVectUnSetBit(OP_SYMBOL(IC_RESULT(ic))->defs,ic->key);
3069                       hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
3070                       OP_DEFS(IC_RESULT (dic))=bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
3071                       ic = ic->prev;
3072                     }
3073                 }
3074             }
3075         }
3076
3077       /* pack for PUSH
3078          iTempNN := (some variable in farspace) V1
3079          push iTempNN ;
3080          -------------
3081          push V1
3082        */
3083       if (ic->op == IPUSH)
3084         {
3085           packForPush (ic, ebpp, blockno);
3086         }
3087
3088
3089       /* pack registers for accumulator use, when the
3090          result of an arithmetic or bit wise operation
3091          has only one use, that use is immediately following
3092          the defintion and the using iCode has only one
3093          operand or has two operands but one is literal &
3094          the result of that operation is not on stack then
3095          we can leave the result of this operation in acc:b
3096          combination */
3097       if ((IS_ARITHMETIC_OP (ic)
3098            || IS_CONDITIONAL(ic)
3099            || IS_BITWISE_OP (ic)
3100            || ic->op == LEFT_OP || ic->op == RIGHT_OP || ic->op == CALL
3101            || (ic->op == ADDRESS_OF && isOperandOnStack (IC_LEFT (ic)))
3102           ) &&
3103           IS_ITEMP (IC_RESULT (ic)) &&
3104           getSize (operandType (IC_RESULT (ic))) <= 2)
3105
3106         packRegsForAccUse (ic);
3107     }
3108 }
3109
3110 /*-----------------------------------------------------------------*/
3111 /* assignRegisters - assigns registers to each live range as need  */
3112 /*-----------------------------------------------------------------*/
3113 void
3114 mcs51_assignRegisters (eBBlock ** ebbs, int count)
3115 {
3116   iCode *ic;
3117   int i;
3118
3119   setToNull ((void *) &_G.funcrUsed);
3120   setToNull ((void *) &_G.regAssigned);
3121   setToNull ((void *) &_G.totRegAssigned);
3122   mcs51_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
3123   mcs51_nRegs = 8;
3124
3125   /* change assignments this will remove some
3126      live ranges reducing some register pressure */
3127
3128   for (i = 0; i < count; i++)
3129     packRegisters (ebbs, i);
3130
3131   /* liveranges probably changed by register packing
3132      so we compute them again */
3133   recomputeLiveRanges (ebbs, count);
3134
3135   if (options.dump_pack)
3136     dumpEbbsToFileExt (DUMP_PACK, ebbs, count);
3137
3138   /* first determine for each live range the number of
3139      registers & the type of registers required for each */
3140   regTypeNum (*ebbs);
3141
3142   /* and serially allocate registers */
3143   serialRegAssign (ebbs, count);
3144
3145   freeAllRegs ();
3146   //setToNull ((void *) &_G.regAssigned);
3147   //setToNull ((void *) &_G.totRegAssigned);
3148   fillGaps();
3149
3150   /* if stack was extended then tell the user */
3151   if (_G.stackExtend)
3152     {
3153 /*      werror(W_TOOMANY_SPILS,"stack", */
3154 /*             _G.stackExtend,currFunc->name,""); */
3155       _G.stackExtend = 0;
3156     }
3157
3158   if (_G.dataExtend)
3159     {
3160 /*      werror(W_TOOMANY_SPILS,"data space", */
3161 /*             _G.dataExtend,currFunc->name,""); */
3162       _G.dataExtend = 0;
3163     }
3164
3165   /* after that create the register mask
3166      for each of the instruction */
3167   createRegMask (ebbs, count);
3168
3169   /* redo that offsets for stacked automatic variables */
3170   if (currFunc) {
3171     redoStackOffsets ();
3172   }
3173
3174   /* make sure r0 & r1 are flagged as used if they might be used */
3175   /* as pointers */
3176   if (currFunc && mcs51_ptrRegReq)
3177     {
3178       currFunc->regsUsed = bitVectSetBit (currFunc->regsUsed, R0_IDX);
3179       currFunc->regsUsed = bitVectSetBit (currFunc->regsUsed, R1_IDX);
3180     }
3181
3182   if (options.dump_rassgn)
3183     {
3184       dumpEbbsToFileExt (DUMP_RASSGN, ebbs, count);
3185       dumpLiveRanges (DUMP_LRANGE, liveRanges);
3186     }
3187
3188   /* do the overlaysegment stuff SDCCmem.c */
3189   doOverlays (ebbs, count);
3190
3191   /* now get back the chain */
3192   ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
3193
3194   gen51Code (ic);
3195
3196   /* free up any _G.stackSpil locations allocated */
3197   applyToSet (_G.stackSpil, deallocStackSpil);
3198   _G.slocNum = 0;
3199   setToNull ((void *) &_G.stackSpil);
3200   setToNull ((void *) &_G.spiltSet);
3201   /* mark all registers as free */
3202   freeAllRegs ();
3203
3204   return;
3205 }