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