1 /*------------------------------------------------------------------------
3 SDCCralloc.c - source file for register allocation. (8051) specific
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
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
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.
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.
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 -------------------------------------------------------------------------*/
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 /*-----------------------------------------------------------------*/
39 extern void gen51Code (iCode *);
49 bitVect *funcrUsed; /* registers used in a function */
55 /* Shared with gen.c */
56 int mcs51_ptrRegReq; /* one byte pointer register required */
62 {REG_GPR, R2_IDX, REG_GPR, "r2", "ar2", "0", 2, 1},
63 {REG_GPR, R3_IDX, REG_GPR, "r3", "ar3", "0", 3, 1},
64 {REG_GPR, R4_IDX, REG_GPR, "r4", "ar4", "0", 4, 1},
65 {REG_GPR, R5_IDX, REG_GPR, "r5", "ar5", "0", 5, 1},
66 {REG_GPR, R6_IDX, REG_GPR, "r6", "ar6", "0", 6, 1},
67 {REG_GPR, R7_IDX, REG_GPR, "r7", "ar7", "0", 7, 1},
68 {REG_PTR, R0_IDX, REG_PTR, "r0", "ar0", "0", 0, 1},
69 {REG_PTR, R1_IDX, REG_PTR, "r1", "ar1", "0", 1, 1},
70 {REG_GPR, X8_IDX, REG_GPR, "x8", "x8", "xreg", 0, 1},
71 {REG_GPR, X9_IDX, REG_GPR, "x9", "x9", "xreg", 1, 1},
72 {REG_GPR, X10_IDX, REG_GPR, "x10", "x10", "xreg", 2, 1},
73 {REG_GPR, X11_IDX, REG_GPR, "x11", "x11", "xreg", 3, 1},
74 {REG_GPR, X12_IDX, REG_GPR, "x12", "x12", "xreg", 4, 1},
75 {REG_CND, CND_IDX, REG_CND, "C", "C", "xreg", 0, 1},
78 static void spillThis (symbol *);
80 /*-----------------------------------------------------------------*/
81 /* allocReg - allocates register of given type */
82 /*-----------------------------------------------------------------*/
88 for (i = 0; i < mcs51_nRegs; i++)
91 /* if type is given as 0 then any
92 free register will do */
96 regs8051[i].isFree = 0;
99 bitVectSetBit (currFunc->regsUsed, i);
102 /* other wise look for specific type
104 if (regs8051[i].isFree &&
105 regs8051[i].type == type)
107 regs8051[i].isFree = 0;
110 bitVectSetBit (currFunc->regsUsed, i);
117 /*-----------------------------------------------------------------*/
118 /* mcs51_regWithIdx - returns pointer to register wit index number */
119 /*-----------------------------------------------------------------*/
121 mcs51_regWithIdx (int idx)
125 for (i = 0; i < mcs51_nRegs; i++)
126 if (regs8051[i].rIdx == idx)
129 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
130 "regWithIdx not found");
134 /*-----------------------------------------------------------------*/
135 /* freeReg - frees a register */
136 /*-----------------------------------------------------------------*/
142 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
143 "freeReg - Freeing NULL register");
151 /*-----------------------------------------------------------------*/
152 /* nFreeRegs - returns number of free registers */
153 /*-----------------------------------------------------------------*/
160 for (i = 0; i < mcs51_nRegs; i++)
161 if (regs8051[i].isFree && regs8051[i].type == type)
166 /*-----------------------------------------------------------------*/
167 /* nfreeRegsType - free registers with type */
168 /*-----------------------------------------------------------------*/
170 nfreeRegsType (int type)
175 if ((nfr = nFreeRegs (type)) == 0)
176 return nFreeRegs (REG_GPR);
179 return nFreeRegs (type);
183 /*-----------------------------------------------------------------*/
184 /* allDefsOutOfRange - all definitions are out of a range */
185 /*-----------------------------------------------------------------*/
187 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
194 for (i = 0; i < defs->size; i++)
198 if (bitVectBitValue (defs, i) &&
199 (ic = hTabItemWithKey (iCodehTab, i)) &&
200 (ic->seq >= fseq && ic->seq <= toseq))
209 /*-----------------------------------------------------------------*/
210 /* computeSpillable - given a point find the spillable live ranges */
211 /*-----------------------------------------------------------------*/
213 computeSpillable (iCode * ic)
217 /* spillable live ranges are those that are live at this
218 point . the following categories need to be subtracted
220 a) - those that are already spilt
221 b) - if being used by this one
222 c) - defined by this one */
224 spillable = bitVectCopy (ic->rlive);
226 bitVectCplAnd (spillable, _G.spiltSet); /* those already spilt */
228 bitVectCplAnd (spillable, ic->uses); /* used in this one */
229 bitVectUnSetBit (spillable, ic->defKey);
230 spillable = bitVectIntersect (spillable, _G.regAssigned);
235 /*-----------------------------------------------------------------*/
236 /* noSpilLoc - return true if a variable has no spil location */
237 /*-----------------------------------------------------------------*/
239 noSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
241 return (sym->usl.spillLoc ? 0 : 1);
244 /*-----------------------------------------------------------------*/
245 /* hasSpilLoc - will return 1 if the symbol has spil location */
246 /*-----------------------------------------------------------------*/
248 hasSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
250 return (sym->usl.spillLoc ? 1 : 0);
253 /*-----------------------------------------------------------------*/
254 /* directSpilLoc - will return 1 if the splilocation is in direct */
255 /*-----------------------------------------------------------------*/
257 directSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
259 if (sym->usl.spillLoc &&
260 (IN_DIRSPACE (SPEC_OCLS (sym->usl.spillLoc->etype))))
266 /*-----------------------------------------------------------------*/
267 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location */
268 /* but is not used as a pointer */
269 /*-----------------------------------------------------------------*/
271 hasSpilLocnoUptr (symbol * sym, eBBlock * ebp, iCode * ic)
273 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
276 /*-----------------------------------------------------------------*/
277 /* rematable - will return 1 if the remat flag is set */
278 /*-----------------------------------------------------------------*/
280 rematable (symbol * sym, eBBlock * ebp, iCode * ic)
285 /*-----------------------------------------------------------------*/
286 /* notUsedInBlock - not used in this block */
287 /*-----------------------------------------------------------------*/
289 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode * ic)
291 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
292 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq));
293 /* return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs)); */
296 /*-----------------------------------------------------------------*/
297 /* notUsedInRemaining - not used or defined in remain of the block */
298 /*-----------------------------------------------------------------*/
300 notUsedInRemaining (symbol * sym, eBBlock * ebp, iCode * ic)
302 return ((usedInRemaining (operandFromSymbol (sym), ic) ? 0 : 1) &&
303 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq));
306 /*-----------------------------------------------------------------*/
307 /* allLRs - return true for all */
308 /*-----------------------------------------------------------------*/
310 allLRs (symbol * sym, eBBlock * ebp, iCode * ic)
315 /*-----------------------------------------------------------------*/
316 /* liveRangesWith - applies function to a given set of live range */
317 /*-----------------------------------------------------------------*/
319 liveRangesWith (bitVect * lrs, int (func) (symbol *, eBBlock *, iCode *),
320 eBBlock * ebp, iCode * ic)
325 if (!lrs || !lrs->size)
328 for (i = 1; i < lrs->size; i++)
331 if (!bitVectBitValue (lrs, i))
334 /* if we don't find it in the live range
335 hash table we are in serious trouble */
336 if (!(sym = hTabItemWithKey (liveRanges, i)))
338 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
339 "liveRangesWith could not find liveRange");
343 if (func (sym, ebp, ic) && bitVectBitValue (_G.regAssigned, sym->key))
344 addSetHead (&rset, sym);
351 /*-----------------------------------------------------------------*/
352 /* leastUsedLR - given a set determines which is the least used */
353 /*-----------------------------------------------------------------*/
355 leastUsedLR (set * sset)
357 symbol *sym = NULL, *lsym = NULL;
359 sym = lsym = setFirstItem (sset);
364 for (; lsym; lsym = setNextItem (sset))
367 /* if usage is the same then prefer
368 the spill the smaller of the two */
369 if (lsym->used == sym->used)
370 if (getSize (lsym->type) < getSize (sym->type))
374 if (lsym->used < sym->used)
379 setToNull ((void **) &sset);
384 /*-----------------------------------------------------------------*/
385 /* noOverLap - will iterate through the list looking for over lap */
386 /*-----------------------------------------------------------------*/
388 noOverLap (set * itmpStack, symbol * fsym)
393 for (sym = setFirstItem (itmpStack); sym;
394 sym = setNextItem (itmpStack))
396 if (bitVectBitValue(sym->clashes,fsym->key)) return 0;
402 /*-----------------------------------------------------------------*/
403 /* isFree - will return 1 if the a free spil location is found */
404 /*-----------------------------------------------------------------*/
409 V_ARG (symbol **, sloc);
410 V_ARG (symbol *, fsym);
412 /* if already found */
416 /* if it is free && and the itmp assigned to
417 this does not have any overlapping live ranges
418 with the one currently being assigned and
419 the size can be accomodated */
421 noOverLap (sym->usl.itmpStack, fsym) &&
422 getSize (sym->type) >= getSize (fsym->type))
431 /*-----------------------------------------------------------------*/
432 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
433 /*-----------------------------------------------------------------*/
435 spillLRWithPtrReg (symbol * forSym)
441 if (!_G.regAssigned ||
442 bitVectIsZero (_G.regAssigned))
445 r0 = mcs51_regWithIdx (R0_IDX);
446 r1 = mcs51_regWithIdx (R1_IDX);
448 /* for all live ranges */
449 for (lrsym = hTabFirstItem (liveRanges, &k); lrsym;
450 lrsym = hTabNextItem (liveRanges, &k))
454 /* if no registers assigned to it or spilt */
455 /* if it does not overlap with this then
456 not need to spill it */
458 if (lrsym->isspilt || !lrsym->nRegs ||
459 (lrsym->liveTo < forSym->liveFrom))
462 /* go thru the registers : if it is either
463 r0 or r1 then spil it */
464 for (j = 0; j < lrsym->nRegs; j++)
465 if (lrsym->regs[j] == r0 ||
466 lrsym->regs[j] == r1)
475 /*-----------------------------------------------------------------*/
476 /* createStackSpil - create a location on the stack to spil */
477 /*-----------------------------------------------------------------*/
479 createStackSpil (symbol * sym)
482 int useXstack, model;
486 /* first go try and find a free one that is already
487 existing on the stack */
488 if (applyToSet (_G.stackSpil, isFree, &sloc, sym))
490 /* found a free one : just update & return */
491 sym->usl.spillLoc = sloc;
494 addSetHead (&sloc->usl.itmpStack, sym);
498 /* could not then have to create one , this is the hard part
499 we need to allocate this on the stack : this is really a
500 hack!! but cannot think of anything better at this time */
502 if (sprintf (slocBuffer, "sloc%d", _G.slocNum++) >= sizeof (slocBuffer))
504 fprintf (stderr, "***Internal error: slocBuffer overflowed: %s:%d\n",
509 sloc = newiTemp (slocBuffer);
511 /* set the type to the spilling symbol */
512 sloc->type = copyLinkChain (sym->type);
513 sloc->etype = getSpec (sloc->type);
514 SPEC_SCLS (sloc->etype) = S_DATA;
515 SPEC_EXTR (sloc->etype) = 0;
517 /* we don't allow it to be allocated`
518 onto the external stack since : so we
519 temporarily turn it off ; we also
520 turn off memory model to prevent
521 the spil from going to the external storage
524 useXstack = options.useXstack;
525 model = options.model;
526 /* noOverlay = options.noOverlay; */
527 /* options.noOverlay = 1; */
528 options.model = options.useXstack = 0;
532 options.useXstack = useXstack;
533 options.model = model;
534 /* options.noOverlay = noOverlay; */
535 sloc->isref = 1; /* to prevent compiler warning */
537 /* if it is on the stack then update the stack */
538 if (IN_STACK (sloc->etype))
540 currFunc->stack += getSize (sloc->type);
541 _G.stackExtend += getSize (sloc->type);
544 _G.dataExtend += getSize (sloc->type);
546 /* add it to the _G.stackSpil set */
547 addSetHead (&_G.stackSpil, sloc);
548 sym->usl.spillLoc = sloc;
551 /* add it to the set of itempStack set
552 of the spill location */
553 addSetHead (&sloc->usl.itmpStack, sym);
557 /*-----------------------------------------------------------------*/
558 /* isSpiltOnStack - returns true if the spil location is on stack */
559 /*-----------------------------------------------------------------*/
561 isSpiltOnStack (symbol * sym)
571 /* if (sym->_G.stackSpil) */
574 if (!sym->usl.spillLoc)
577 etype = getSpec (sym->usl.spillLoc->type);
578 if (IN_STACK (etype))
584 /*-----------------------------------------------------------------*/
585 /* spillThis - spils a specific operand */
586 /*-----------------------------------------------------------------*/
588 spillThis (symbol * sym)
591 /* if this is rematerializable or has a spillLocation
592 we are okay, else we need to create a spillLocation
594 if (!(sym->remat || sym->usl.spillLoc))
595 createStackSpil (sym);
598 /* mark it has spilt & put it in the spilt set */
600 _G.spiltSet = bitVectSetBit (_G.spiltSet, sym->key);
602 bitVectUnSetBit (_G.regAssigned, sym->key);
604 for (i = 0; i < sym->nRegs; i++)
608 freeReg (sym->regs[i]);
612 /* if spilt on stack then free up r0 & r1
613 if they could have been assigned to some
615 if (!mcs51_ptrRegReq && isSpiltOnStack (sym))
618 spillLRWithPtrReg (sym);
621 if (sym->usl.spillLoc && !sym->remat)
622 sym->usl.spillLoc->allocreq = 1;
626 /*-----------------------------------------------------------------*/
627 /* selectSpil - select a iTemp to spil : rather a simple procedure */
628 /*-----------------------------------------------------------------*/
630 selectSpil (iCode * ic, eBBlock * ebp, symbol * forSym)
632 bitVect *lrcs = NULL;
636 /* get the spillable live ranges */
637 lrcs = computeSpillable (ic);
639 /* get all live ranges that are rematerizable */
640 if ((selectS = liveRangesWith (lrcs, rematable, ebp, ic)))
643 /* return the least used of these */
644 return leastUsedLR (selectS);
647 /* get live ranges with spillLocations in direct space */
648 if ((selectS = liveRangesWith (lrcs, directSpilLoc, ebp, ic)))
650 sym = leastUsedLR (selectS);
651 strcpy (sym->rname, (sym->usl.spillLoc->rname[0] ?
652 sym->usl.spillLoc->rname :
653 sym->usl.spillLoc->name));
655 /* mark it as allocation required */
656 sym->usl.spillLoc->allocreq = 1;
660 /* if the symbol is local to the block then */
661 if (forSym->liveTo < ebp->lSeq)
664 /* check if there are any live ranges allocated
665 to registers that are not used in this block */
666 if (!_G.blockSpil && (selectS = liveRangesWith (lrcs, notUsedInBlock, ebp, ic)))
668 sym = leastUsedLR (selectS);
669 /* if this is not rematerializable */
678 /* check if there are any live ranges that not
679 used in the remainder of the block */
680 if (!_G.blockSpil && (selectS = liveRangesWith (lrcs, notUsedInRemaining, ebp, ic)))
682 sym = leastUsedLR (selectS);
695 /* find live ranges with spillocation && not used as pointers */
696 if ((selectS = liveRangesWith (lrcs, hasSpilLocnoUptr, ebp, ic)))
699 sym = leastUsedLR (selectS);
700 /* mark this as allocation required */
701 sym->usl.spillLoc->allocreq = 1;
705 /* find live ranges with spillocation */
706 if ((selectS = liveRangesWith (lrcs, hasSpilLoc, ebp, ic)))
709 sym = leastUsedLR (selectS);
710 sym->usl.spillLoc->allocreq = 1;
714 /* couldn't find then we need to create a spil
715 location on the stack , for which one? the least
717 if ((selectS = liveRangesWith (lrcs, noSpilLoc, ebp, ic)))
720 /* return a created spil location */
721 sym = createStackSpil (leastUsedLR (selectS));
722 sym->usl.spillLoc->allocreq = 1;
726 /* this is an extreme situation we will spill
727 this one : happens very rarely but it does happen */
733 /*-----------------------------------------------------------------*/
734 /* spilSomething - spil some variable & mark registers as free */
735 /*-----------------------------------------------------------------*/
737 spilSomething (iCode * ic, eBBlock * ebp, symbol * forSym)
742 /* get something we can spil */
743 ssym = selectSpil (ic, ebp, forSym);
745 /* mark it as spilt */
747 _G.spiltSet = bitVectSetBit (_G.spiltSet, ssym->key);
749 /* mark it as not register assigned &
750 take it away from the set */
751 bitVectUnSetBit (_G.regAssigned, ssym->key);
753 /* mark the registers as free */
754 for (i = 0; i < ssym->nRegs; i++)
756 freeReg (ssym->regs[i]);
758 /* if spilt on stack then free up r0 & r1
759 if they could have been assigned to as gprs */
760 if (!mcs51_ptrRegReq && isSpiltOnStack (ssym))
763 spillLRWithPtrReg (ssym);
766 /* if this was a block level spil then insert push & pop
767 at the start & end of block respectively */
770 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
771 /* add push to the start of the block */
772 addiCodeToeBBlock (ebp, nic, (ebp->sch->op == LABEL ?
773 ebp->sch->next : ebp->sch));
774 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
775 /* add pop to the end of the block */
776 addiCodeToeBBlock (ebp, nic, NULL);
779 /* if spilt because not used in the remainder of the
780 block then add a push before this instruction and
781 a pop at the end of the block */
782 if (ssym->remainSpil)
785 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
786 /* add push just before this instruction */
787 addiCodeToeBBlock (ebp, nic, ic);
789 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
790 /* add pop to the end of the block */
791 addiCodeToeBBlock (ebp, nic, NULL);
800 /*-----------------------------------------------------------------*/
801 /* getRegPtr - will try for PTR if not a GPR type if not spil */
802 /*-----------------------------------------------------------------*/
804 getRegPtr (iCode * ic, eBBlock * ebp, symbol * sym)
809 /* try for a ptr type */
810 if ((reg = allocReg (REG_PTR)))
813 /* try for gpr type */
814 if ((reg = allocReg (REG_GPR)))
817 /* we have to spil */
818 if (!spilSomething (ic, ebp, sym))
821 /* this looks like an infinite loop but
822 in really selectSpil will abort */
826 /*-----------------------------------------------------------------*/
827 /* getRegGpr - will try for GPR if not spil */
828 /*-----------------------------------------------------------------*/
830 getRegGpr (iCode * ic, eBBlock * ebp, symbol * sym)
835 /* try for gpr type */
836 if ((reg = allocReg (REG_GPR)))
839 if (!mcs51_ptrRegReq)
840 if ((reg = allocReg (REG_PTR)))
843 /* we have to spil */
844 if (!spilSomething (ic, ebp, sym))
847 /* this looks like an infinite loop but
848 in really selectSpil will abort */
852 /*-----------------------------------------------------------------*/
853 /* symHasReg - symbol has a given register */
854 /*-----------------------------------------------------------------*/
856 symHasReg (symbol * sym, regs * reg)
860 for (i = 0; i < sym->nRegs; i++)
861 if (sym->regs[i] == reg)
867 /*-----------------------------------------------------------------*/
868 /* deassignLRs - check the live to and if they have registers & are */
869 /* not spilt then free up the registers */
870 /*-----------------------------------------------------------------*/
872 deassignLRs (iCode * ic, eBBlock * ebp)
878 for (sym = hTabFirstItem (liveRanges, &k); sym;
879 sym = hTabNextItem (liveRanges, &k))
883 /* if it does not end here */
884 if (sym->liveTo > ic->seq)
887 /* if it was spilt on stack then we can
888 mark the stack spil location as free */
893 sym->usl.spillLoc->isFree = 1;
899 if (!bitVectBitValue (_G.regAssigned, sym->key))
902 /* special case check if this is an IFX &
903 the privious one was a pop and the
904 previous one was not spilt then keep track
906 if (ic->op == IFX && ic->prev &&
907 ic->prev->op == IPOP &&
908 !ic->prev->parmPush &&
909 !OP_SYMBOL (IC_LEFT (ic->prev))->isspilt)
910 psym = OP_SYMBOL (IC_LEFT (ic->prev));
916 bitVectUnSetBit (_G.regAssigned, sym->key);
918 /* if the result of this one needs registers
919 and does not have it then assign it right
921 if (IC_RESULT (ic) &&
922 !(SKIP_IC2 (ic) || /* not a special icode */
923 ic->op == JUMPTABLE ||
929 (result = OP_SYMBOL (IC_RESULT (ic))) && /* has a result */
930 result->liveTo > ic->seq && /* and will live beyond this */
931 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
932 result->regType == sym->regType && /* same register types */
933 result->nRegs && /* which needs registers */
934 !result->isspilt && /* and does not already have them */
936 !bitVectBitValue (_G.regAssigned, result->key) &&
937 /* the number of free regs + number of regs in this LR
938 can accomodate the what result Needs */
939 ((nfreeRegsType (result->regType) +
940 sym->nRegs) >= result->nRegs)
944 for (i = 0; i < result->nRegs; i++)
946 result->regs[i] = sym->regs[i];
948 result->regs[i] = getRegGpr (ic, ebp, result);
950 _G.regAssigned = bitVectSetBit (_G.regAssigned, result->key);
954 /* free the remaining */
955 for (; i < sym->nRegs; i++)
959 if (!symHasReg (psym, sym->regs[i]))
960 freeReg (sym->regs[i]);
963 freeReg (sym->regs[i]);
970 /*-----------------------------------------------------------------*/
971 /* reassignLR - reassign this to registers */
972 /*-----------------------------------------------------------------*/
974 reassignLR (operand * op)
976 symbol *sym = OP_SYMBOL (op);
979 /* not spilt any more */
980 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
981 bitVectUnSetBit (_G.spiltSet, sym->key);
983 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
987 for (i = 0; i < sym->nRegs; i++)
988 sym->regs[i]->isFree = 0;
991 /*-----------------------------------------------------------------*/
992 /* willCauseSpill - determines if allocating will cause a spill */
993 /*-----------------------------------------------------------------*/
995 willCauseSpill (int nr, int rt)
997 /* first check if there are any avlb registers
998 of te type required */
1001 /* special case for pointer type
1002 if pointer type not avlb then
1003 check for type gpr */
1004 if (nFreeRegs (rt) >= nr)
1006 if (nFreeRegs (REG_GPR) >= nr)
1011 if (mcs51_ptrRegReq)
1013 if (nFreeRegs (rt) >= nr)
1018 if (nFreeRegs (REG_PTR) +
1019 nFreeRegs (REG_GPR) >= nr)
1024 /* it will cause a spil */
1028 /*-----------------------------------------------------------------*/
1029 /* positionRegs - the allocator can allocate same registers to res- */
1030 /* ult and operand, if this happens make sure they are in the same */
1031 /* position as the operand otherwise chaos results */
1032 /*-----------------------------------------------------------------*/
1034 positionRegs (symbol * result, symbol * opsym, int lineno)
1036 int count = min (result->nRegs, opsym->nRegs);
1037 int i, j = 0, shared = 0;
1039 /* if the result has been spilt then cannot share */
1044 /* first make sure that they actually share */
1045 for (i = 0; i < count; i++)
1047 for (j = 0; j < count; j++)
1049 if (result->regs[i] == opsym->regs[j] && i != j)
1059 regs *tmp = result->regs[i];
1060 result->regs[i] = result->regs[j];
1061 result->regs[j] = tmp;
1066 /*-----------------------------------------------------------------*/
1067 /* serialRegAssign - serially allocate registers to the variables */
1068 /*-----------------------------------------------------------------*/
1070 serialRegAssign (eBBlock ** ebbs, int count)
1074 /* for all blocks */
1075 for (i = 0; i < count; i++) {
1079 if (ebbs[i]->noPath &&
1080 (ebbs[i]->entryLabel != entryLabel &&
1081 ebbs[i]->entryLabel != returnLabel))
1084 /* of all instructions do */
1085 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1087 /* if this is an ipop that means some live
1088 range will have to be assigned again */
1090 reassignLR (IC_LEFT (ic));
1092 /* if result is present && is a true symbol */
1093 if (IC_RESULT (ic) && ic->op != IFX &&
1094 IS_TRUE_SYMOP (IC_RESULT (ic)))
1095 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
1097 /* take away registers from live
1098 ranges that end at this instruction */
1099 deassignLRs (ic, ebbs[i]);
1101 /* some don't need registers */
1102 if (SKIP_IC2 (ic) ||
1103 ic->op == JUMPTABLE ||
1107 (IC_RESULT (ic) && POINTER_SET (ic)))
1110 /* now we need to allocate registers
1111 only for the result */
1112 if (IC_RESULT (ic)) {
1113 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1119 /* if it does not need or is spilt
1120 or is already assigned to registers
1121 or will not live beyond this instructions */
1124 bitVectBitValue (_G.regAssigned, sym->key) ||
1125 sym->liveTo <= ic->seq)
1128 /* if some liverange has been spilt at the block level
1129 and this one live beyond this block then spil this
1131 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq) {
1135 /* if trying to allocate this will cause
1136 a spill and there is nothing to spill
1137 or this one is rematerializable then
1139 willCS = willCauseSpill (sym->nRegs, sym->regType);
1140 spillable = computeSpillable (ic);
1141 if (sym->remat || (willCS && bitVectIsZero (spillable))) {
1146 /* if it has a spillocation & is used less than
1147 all other live ranges then spill this */
1149 if (sym->usl.spillLoc) {
1150 symbol *leastUsed = leastUsedLR (liveRangesWith (spillable,
1151 allLRs, ebbs[i], ic));
1152 if (leastUsed && leastUsed->used > sym->used) {
1157 /* if none of the liveRanges have a spillLocation then better
1158 to spill this one than anything else already assigned to registers */
1159 if (liveRangesWith(spillable,noSpilLoc,ebbs[i],ic)) {
1165 /* if we need ptr regs for the right side
1167 if (POINTER_GET (ic) && IS_SYMOP (IC_LEFT (ic))
1168 && getSize (OP_SYMBOL (IC_LEFT (ic))->type) <= (unsigned int) PTRSIZE) {
1172 /* else we assign registers to it */
1173 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1175 for (j = 0; j < sym->nRegs; j++) {
1176 if (sym->regType == REG_PTR)
1177 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1179 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1181 /* if the allocation failed which means
1182 this was spilt then break */
1183 if (!sym->regs[j]) {
1185 fprintf (stderr, "%d reg(s) lost in %s:%d\n",
1186 j, __FILE__,__LINE__);
1192 /* if it shares registers with operands make sure
1193 that they are in the same position */
1194 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1195 OP_SYMBOL (IC_LEFT (ic))->nRegs && ic->op != '=') {
1196 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1197 OP_SYMBOL (IC_LEFT (ic)), ic->lineno);
1199 /* do the same for the right operand */
1200 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)) &&
1201 OP_SYMBOL (IC_RIGHT (ic))->nRegs) {
1202 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1203 OP_SYMBOL (IC_RIGHT (ic)), ic->lineno);
1216 /*-----------------------------------------------------------------*/
1217 /* rUmaskForOp :- returns register mask for an operand */
1218 /*-----------------------------------------------------------------*/
1220 mcs51_rUmaskForOp (operand * op)
1226 /* only temporaries are assigned registers */
1230 sym = OP_SYMBOL (op);
1232 /* if spilt or no registers assigned to it
1234 if (sym->isspilt || !sym->nRegs)
1237 rumask = newBitVect (mcs51_nRegs);
1239 for (j = 0; j < sym->nRegs; j++)
1241 rumask = bitVectSetBit (rumask,
1242 sym->regs[j]->rIdx);
1248 /*-----------------------------------------------------------------*/
1249 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1250 /*-----------------------------------------------------------------*/
1252 regsUsedIniCode (iCode * ic)
1254 bitVect *rmask = newBitVect (mcs51_nRegs);
1256 /* do the special cases first */
1259 rmask = bitVectUnion (rmask,
1260 mcs51_rUmaskForOp (IC_COND (ic)));
1264 /* for the jumptable */
1265 if (ic->op == JUMPTABLE)
1267 rmask = bitVectUnion (rmask,
1268 mcs51_rUmaskForOp (IC_JTCOND (ic)));
1273 /* of all other cases */
1275 rmask = bitVectUnion (rmask,
1276 mcs51_rUmaskForOp (IC_LEFT (ic)));
1280 rmask = bitVectUnion (rmask,
1281 mcs51_rUmaskForOp (IC_RIGHT (ic)));
1284 rmask = bitVectUnion (rmask,
1285 mcs51_rUmaskForOp (IC_RESULT (ic)));
1291 /*-----------------------------------------------------------------*/
1292 /* createRegMask - for each instruction will determine the regsUsed */
1293 /*-----------------------------------------------------------------*/
1295 createRegMask (eBBlock ** ebbs, int count)
1299 /* for all blocks */
1300 for (i = 0; i < count; i++)
1304 if (ebbs[i]->noPath &&
1305 (ebbs[i]->entryLabel != entryLabel &&
1306 ebbs[i]->entryLabel != returnLabel))
1309 /* for all instructions */
1310 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1315 if (SKIP_IC2 (ic) || !ic->rlive)
1318 /* first mark the registers used in this
1320 ic->rUsed = regsUsedIniCode (ic);
1321 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1323 /* now create the register mask for those
1324 registers that are in use : this is a
1325 super set of ic->rUsed */
1326 ic->rMask = newBitVect (mcs51_nRegs + 1);
1328 /* for all live Ranges alive at this point */
1329 for (j = 1; j < ic->rlive->size; j++)
1334 /* if not alive then continue */
1335 if (!bitVectBitValue (ic->rlive, j))
1338 /* find the live range we are interested in */
1339 if (!(sym = hTabItemWithKey (liveRanges, j)))
1341 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
1342 "createRegMask cannot find live range");
1346 /* if no register assigned to it */
1347 if (!sym->nRegs || sym->isspilt)
1350 /* for all the registers allocated to it */
1351 for (k = 0; k < sym->nRegs; k++)
1354 bitVectSetBit (ic->rMask, sym->regs[k]->rIdx);
1360 /*-----------------------------------------------------------------*/
1361 /* rematStr - returns the rematerialized string for a remat var */
1362 /*-----------------------------------------------------------------*/
1364 rematStr (symbol * sym)
1367 iCode *ic = sym->rematiCode;
1372 /* if plus or minus print the right hand side */
1373 if (ic->op == '+' || ic->op == '-')
1375 sprintf (s, "0x%04x %c ", (int) operandLitValue (IC_RIGHT (ic)),
1378 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1382 /* cast then continue */
1383 if (IS_CAST_ICODE(ic)) {
1384 ic = OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
1387 /* we reached the end */
1388 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1395 /*-----------------------------------------------------------------*/
1396 /* regTypeNum - computes the type & number of registers required */
1397 /*-----------------------------------------------------------------*/
1405 /* for each live range do */
1406 for (sym = hTabFirstItem (liveRanges, &k); sym;
1407 sym = hTabNextItem (liveRanges, &k))
1410 /* if used zero times then no registers needed */
1411 if ((sym->liveTo - sym->liveFrom) == 0)
1415 /* if the live range is a temporary */
1419 /* if the type is marked as a conditional */
1420 if (sym->regType == REG_CND)
1423 /* if used in return only then we don't
1425 if (sym->ruonly || sym->accuse)
1427 if (IS_AGGREGATE (sym->type) || sym->isptr)
1428 sym->type = aggrToPtr (sym->type, FALSE);
1432 /* if the symbol has only one definition &
1433 that definition is a get_pointer and the
1434 pointer we are getting is rematerializable and
1437 if (bitVectnBitsOn (sym->defs) == 1 &&
1438 (ic = hTabItemWithKey (iCodehTab,
1439 bitVectFirstBit (sym->defs))) &&
1442 !IS_BITVAR (sym->etype))
1446 /* if remat in data space */
1447 if (OP_SYMBOL (IC_LEFT (ic))->remat &&
1448 !IS_CAST_ICODE(OP_SYMBOL (IC_LEFT (ic))->rematiCode) &&
1449 DCL_TYPE (aggrToPtr (sym->type, FALSE)) == POINTER)
1452 /* create a psuedo symbol & force a spil */
1453 symbol *psym = newSymbol (rematStr (OP_SYMBOL (IC_LEFT (ic))), 1);
1454 psym->type = sym->type;
1455 psym->etype = sym->etype;
1456 strcpy (psym->rname, psym->name);
1458 sym->usl.spillLoc = psym;
1462 /* if in data space or idata space then try to
1463 allocate pointer register */
1467 /* if not then we require registers */
1468 sym->nRegs = ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1469 getSize (sym->type = aggrToPtr (sym->type, FALSE)) :
1470 getSize (sym->type));
1474 fprintf (stderr, "allocated more than 4 or 0 registers for type ");
1475 printTypeChain (sym->type, stderr);
1476 fprintf (stderr, "\n");
1479 /* determine the type of register required */
1480 if (sym->nRegs == 1 &&
1481 IS_PTR (sym->type) &&
1483 sym->regType = REG_PTR;
1485 sym->regType = REG_GPR;
1489 /* for the first run we don't provide */
1490 /* registers for true symbols we will */
1491 /* see how things go */
1497 /*-----------------------------------------------------------------*/
1498 /* freeAllRegs - mark all registers as free */
1499 /*-----------------------------------------------------------------*/
1505 for (i = 0; i < mcs51_nRegs; i++)
1506 regs8051[i].isFree = 1;
1509 /*-----------------------------------------------------------------*/
1510 /* deallocStackSpil - this will set the stack pointer back */
1511 /*-----------------------------------------------------------------*/
1513 DEFSETFUNC (deallocStackSpil)
1521 /*-----------------------------------------------------------------*/
1522 /* farSpacePackable - returns the packable icode for far variables */
1523 /*-----------------------------------------------------------------*/
1525 farSpacePackable (iCode * ic)
1529 /* go thru till we find a definition for the
1530 symbol on the right */
1531 for (dic = ic->prev; dic; dic = dic->prev)
1533 /* if the definition is a call then no */
1534 if ((dic->op == CALL || dic->op == PCALL) &&
1535 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1540 /* if shift by unknown amount then not */
1541 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1542 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1545 /* if pointer get and size > 1 */
1546 if (POINTER_GET (dic) &&
1547 getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) > 1)
1550 if (POINTER_SET (dic) &&
1551 getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)) > 1)
1554 /* if any three is a true symbol in far space */
1555 if (IC_RESULT (dic) &&
1556 IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1557 isOperandInFarSpace (IC_RESULT (dic)))
1560 if (IC_RIGHT (dic) &&
1561 IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
1562 isOperandInFarSpace (IC_RIGHT (dic)) &&
1563 !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
1566 if (IC_LEFT (dic) &&
1567 IS_TRUE_SYMOP (IC_LEFT (dic)) &&
1568 isOperandInFarSpace (IC_LEFT (dic)) &&
1569 !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
1572 if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic)))
1574 if ((dic->op == LEFT_OP ||
1575 dic->op == RIGHT_OP ||
1577 IS_OP_LITERAL (IC_RIGHT (dic)))
1587 /*-----------------------------------------------------------------*/
1588 /* packRegsForAssign - register reduction for assignment */
1589 /*-----------------------------------------------------------------*/
1591 packRegsForAssign (iCode * ic, eBBlock * ebp)
1594 //sym_link *etype = operandType (IC_RIGHT (ic));
1596 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1597 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1598 OP_LIVETO (IC_RIGHT (ic)) > ic->seq
1599 /* why? || IS_BITFIELD (etype) */ )
1604 /* if the true symbol is defined in far space or on stack
1605 then we should not since this will increase register pressure */
1606 if (isOperandInFarSpace(IC_RESULT(ic)) && !farSpacePackable(ic)) {
1610 /* find the definition of iTempNN scanning backwards if we find a
1611 a use of the true symbol in before we find the definition then
1613 for (dic = ic->prev; dic; dic = dic->prev)
1615 /* if there is a function call then don't pack it */
1616 if ((dic->op == CALL || dic->op == PCALL))
1625 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1626 IS_OP_VOLATILE (IC_RESULT (dic)))
1632 if (IS_SYMOP (IC_RESULT (dic)) &&
1633 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1635 if (POINTER_SET (dic))
1641 if (IS_SYMOP (IC_RIGHT (dic)) &&
1642 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1643 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key))
1649 if (IS_SYMOP (IC_LEFT (dic)) &&
1650 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1651 IC_LEFT (dic)->key == IC_RIGHT (ic)->key))
1657 if (POINTER_SET (dic) &&
1658 IC_RESULT (dic)->key == IC_RESULT (ic)->key)
1666 return 0; /* did not find */
1668 /* if assignment then check that right is not a bit */
1669 if (ASSIGNMENT (dic) && !POINTER_SET (dic))
1671 sym_link *etype = operandType (IC_RIGHT (dic));
1672 if (IS_BITFIELD (etype))
1675 /* if the result is on stack or iaccess then it must be
1676 the same atleast one of the operands */
1677 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1678 OP_SYMBOL (IC_RESULT (ic))->iaccess)
1681 /* the operation has only one symbol
1682 operator then we can pack */
1683 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1684 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1687 if (!((IC_LEFT (dic) &&
1688 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1690 IC_RESULT (ic)->key == IC_RIGHT (dic)->key)))
1694 /* found the definition */
1695 /* replace the result with the result of */
1696 /* this assignment and remove this assignment */
1697 IC_RESULT (dic) = IC_RESULT (ic);
1699 if (IS_ITEMP (IC_RESULT (dic)) && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq)
1701 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1703 /* delete from liverange table also
1704 delete from all the points inbetween and the new
1706 for (sic = dic; sic != ic; sic = sic->next)
1708 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1709 if (IS_ITEMP (IC_RESULT (dic)))
1710 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1713 remiCodeFromeBBlock (ebp, ic);
1714 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1715 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
1720 /*-----------------------------------------------------------------*/
1721 /* findAssignToSym : scanning backwards looks for first assig found */
1722 /*-----------------------------------------------------------------*/
1724 findAssignToSym (operand * op, iCode * ic)
1728 for (dic = ic->prev; dic; dic = dic->prev)
1731 /* if definition by assignment */
1732 if (dic->op == '=' &&
1733 !POINTER_SET (dic) &&
1734 IC_RESULT (dic)->key == op->key
1735 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1739 /* we are interested only if defined in far space */
1740 /* or in stack space in case of + & - */
1742 /* if assigned to a non-symbol then return
1744 if (!IS_SYMOP (IC_RIGHT (dic)))
1747 /* if the symbol is in far space then
1749 if (isOperandInFarSpace (IC_RIGHT (dic)))
1752 /* for + & - operations make sure that
1753 if it is on the stack it is the same
1754 as one of the three operands */
1755 if ((ic->op == '+' || ic->op == '-') &&
1756 OP_SYMBOL (IC_RIGHT (dic))->onStack)
1759 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key &&
1760 IC_LEFT (ic)->key != IC_RIGHT (dic)->key &&
1761 IC_RIGHT (ic)->key != IC_RIGHT (dic)->key)
1769 /* if we find an usage then we cannot delete it */
1770 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
1773 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
1776 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
1780 /* now make sure that the right side of dic
1781 is not defined between ic & dic */
1784 iCode *sic = dic->next;
1786 for (; sic != ic; sic = sic->next)
1787 if (IC_RESULT (sic) &&
1788 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
1797 /*-----------------------------------------------------------------*/
1798 /* packRegsForSupport :- reduce some registers for support calls */
1799 /*-----------------------------------------------------------------*/
1801 packRegsForSupport (iCode * ic, eBBlock * ebp)
1806 /* for the left & right operand :- look to see if the
1807 left was assigned a true symbol in far space in that
1808 case replace them */
1810 if (IS_ITEMP (IC_LEFT (ic)) &&
1811 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq)
1813 dic = findAssignToSym (IC_LEFT (ic), ic);
1818 /* found it we need to remove it from the
1820 for (sic = dic; sic != ic; sic = sic->next)
1821 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
1823 OP_SYMBOL(IC_LEFT (ic))=OP_SYMBOL(IC_RIGHT (dic));
1824 IC_LEFT (ic)->key = OP_SYMBOL(IC_RIGHT (dic))->key;
1825 remiCodeFromeBBlock (ebp, dic);
1826 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1830 /* do the same for the right operand */
1833 IS_ITEMP (IC_RIGHT (ic)) &&
1834 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq)
1836 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
1842 /* if this is a subtraction & the result
1843 is a true symbol in far space then don't pack */
1844 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic)))
1846 sym_link *etype = getSpec (operandType (IC_RESULT (dic)));
1847 if (IN_FARSPACE (SPEC_OCLS (etype)))
1850 /* found it we need to remove it from the
1852 for (sic = dic; sic != ic; sic = sic->next)
1853 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
1855 IC_RIGHT (ic)->operand.symOperand =
1856 IC_RIGHT (dic)->operand.symOperand;
1857 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1859 remiCodeFromeBBlock (ebp, dic);
1860 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1867 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1870 /*-----------------------------------------------------------------*/
1871 /* packRegsForOneuse : - will reduce some registers for single Use */
1872 /*-----------------------------------------------------------------*/
1874 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1879 /* if returning a literal then do nothing */
1883 /* only upto 2 bytes since we cannot predict
1884 the usage of b, & acc */
1885 if (getSize (operandType (op)) > (fReturnSizeMCS51 - 2))
1888 if (ic->op != RETURN &&
1890 !POINTER_SET (ic) &&
1894 /* this routine will mark the a symbol as used in one
1895 instruction use only && if the defintion is local
1896 (ie. within the basic block) && has only one definition &&
1897 that definiion is either a return value from a
1898 function or does not contain any variables in
1900 uses = bitVectCopy (OP_USES (op));
1901 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1902 if (!bitVectIsZero (uses)) /* has other uses */
1905 /* if it has only one defintion */
1906 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1907 return NULL; /* has more than one definition */
1909 /* get that definition */
1911 hTabItemWithKey (iCodehTab,
1912 bitVectFirstBit (OP_DEFS (op)))))
1915 /* if that only usage is a cast */
1916 if (dic->op == CAST) {
1917 /* to a bigger type */
1918 if (getSize(OP_SYM_TYPE(IC_RESULT(dic))) >
1919 getSize(OP_SYM_TYPE(IC_RIGHT(dic)))) {
1920 /* than we can not, since we cannot predict the usage of b & acc */
1925 /* found the definition now check if it is local */
1926 if (dic->seq < ebp->fSeq ||
1927 dic->seq > ebp->lSeq)
1928 return NULL; /* non-local */
1930 /* now check if it is the return from
1932 if (dic->op == CALL || dic->op == PCALL)
1934 if (ic->op != SEND && ic->op != RETURN)
1936 OP_SYMBOL (op)->ruonly = 1;
1943 /* otherwise check that the definition does
1944 not contain any symbols in far space */
1945 if (isOperandInFarSpace (IC_LEFT (dic)) ||
1946 isOperandInFarSpace (IC_RIGHT (dic)) ||
1947 IS_OP_RUONLY (IC_LEFT (ic)) ||
1948 IS_OP_RUONLY (IC_RIGHT (ic)))
1953 /* if pointer set then make sure the pointer
1955 if (POINTER_SET (dic) &&
1956 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1959 if (POINTER_GET (dic) &&
1960 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1965 /* also make sure the intervenening instructions
1966 don't have any thing in far space */
1967 for (dic = dic->next; dic && dic != ic && sic != ic; dic = dic->next)
1970 /* if there is an intervening function call then no */
1971 if (dic->op == CALL || dic->op == PCALL)
1973 /* if pointer set then make sure the pointer
1975 if (POINTER_SET (dic) &&
1976 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1979 if (POINTER_GET (dic) &&
1980 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1983 /* if address of & the result is remat the okay */
1984 if (dic->op == ADDRESS_OF &&
1985 OP_SYMBOL (IC_RESULT (dic))->remat)
1988 /* if operand has size of three or more & this
1989 operation is a '*','/' or '%' then 'b' may
1991 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1992 getSize (operandType (op)) >= 3)
1995 /* if left or right or result is in far space */
1996 if (isOperandInFarSpace (IC_LEFT (dic)) ||
1997 isOperandInFarSpace (IC_RIGHT (dic)) ||
1998 isOperandInFarSpace (IC_RESULT (dic)) ||
1999 IS_OP_RUONLY (IC_LEFT (dic)) ||
2000 IS_OP_RUONLY (IC_RIGHT (dic)) ||
2001 IS_OP_RUONLY (IC_RESULT (dic)))
2005 /* if left or right or result is on stack */
2006 if (isOperandOnStack(IC_LEFT(dic)) ||
2007 isOperandOnStack(IC_RIGHT(dic)) ||
2008 isOperandOnStack(IC_RESULT(dic))) {
2013 OP_SYMBOL (op)->ruonly = 1;
2018 /*-----------------------------------------------------------------*/
2019 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
2020 /*-----------------------------------------------------------------*/
2022 isBitwiseOptimizable (iCode * ic)
2024 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
2025 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
2027 /* bitwise operations are considered optimizable
2028 under the following conditions (Jean-Louis VERN)
2040 if (IS_LITERAL(rtype) ||
2041 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
2047 /*-----------------------------------------------------------------*/
2048 /* packRegsForAccUse - pack registers for acc use */
2049 /*-----------------------------------------------------------------*/
2051 packRegsForAccUse (iCode * ic)
2055 /* if + or - then it has to be one byte result */
2056 if ((ic->op == '+' || ic->op == '-')
2057 && getSize (operandType (IC_RESULT (ic))) > 1)
2060 /* if shift operation make sure right side is not a literal */
2061 if (ic->op == RIGHT_OP &&
2062 (isOperandLiteral (IC_RIGHT (ic)) ||
2063 getSize (operandType (IC_RESULT (ic))) > 1))
2066 if (ic->op == LEFT_OP &&
2067 (isOperandLiteral (IC_RIGHT (ic)) ||
2068 getSize (operandType (IC_RESULT (ic))) > 1))
2071 if (IS_BITWISE_OP (ic) &&
2072 getSize (operandType (IC_RESULT (ic))) > 1)
2076 /* has only one definition */
2077 if (bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) > 1)
2080 /* has only one use */
2081 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) > 1)
2084 /* and the usage immediately follows this iCode */
2085 if (!(uic = hTabItemWithKey (iCodehTab,
2086 bitVectFirstBit (OP_USES (IC_RESULT (ic))))))
2089 if (ic->next != uic)
2092 /* if it is a conditional branch then we definitely can */
2096 if (uic->op == JUMPTABLE)
2099 /* if the usage is not is an assignment
2100 or an arithmetic / bitwise / shift operation then not */
2101 if (POINTER_SET (uic) &&
2102 getSize (aggrToPtr (operandType (IC_RESULT (uic)), FALSE)) > 1)
2105 if (uic->op != '=' &&
2106 !IS_ARITHMETIC_OP (uic) &&
2107 !IS_BITWISE_OP (uic) &&
2108 uic->op != LEFT_OP &&
2109 uic->op != RIGHT_OP)
2112 /* if used in ^ operation then make sure right is not a
2114 if (uic->op == '^' && isOperandLiteral (IC_RIGHT (uic)))
2117 /* if shift operation make sure right side is not a literal */
2118 if (uic->op == RIGHT_OP &&
2119 (isOperandLiteral (IC_RIGHT (uic)) ||
2120 getSize (operandType (IC_RESULT (uic))) > 1))
2123 if (uic->op == LEFT_OP &&
2124 (isOperandLiteral (IC_RIGHT (uic)) ||
2125 getSize (operandType (IC_RESULT (uic))) > 1))
2128 /* make sure that the result of this icode is not on the
2129 stack, since acc is used to compute stack offset */
2130 if (IS_TRUE_SYMOP (IC_RESULT (uic)) &&
2131 OP_SYMBOL (IC_RESULT (uic))->onStack)
2134 /* if either one of them in far space then we cannot */
2135 if ((IS_TRUE_SYMOP (IC_LEFT (uic)) &&
2136 isOperandInFarSpace (IC_LEFT (uic))) ||
2137 (IS_TRUE_SYMOP (IC_RIGHT (uic)) &&
2138 isOperandInFarSpace (IC_RIGHT (uic))))
2141 /* if the usage has only one operand then we can */
2142 if (IC_LEFT (uic) == NULL ||
2143 IC_RIGHT (uic) == NULL)
2146 /* make sure this is on the left side if not
2147 a '+' since '+' is commutative */
2148 if (ic->op != '+' &&
2149 IC_LEFT (uic)->key != IC_RESULT (ic)->key)
2153 // this is too dangerous and need further restrictions
2156 /* if one of them is a literal then we can */
2157 if ((IC_LEFT (uic) && IS_OP_LITERAL (IC_LEFT (uic))) ||
2158 (IC_RIGHT (uic) && IS_OP_LITERAL (IC_RIGHT (uic))))
2160 OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2165 /* if the other one is not on stack then we can */
2166 if (IC_LEFT (uic)->key == IC_RESULT (ic)->key &&
2167 (IS_ITEMP (IC_RIGHT (uic)) ||
2168 (IS_TRUE_SYMOP (IC_RIGHT (uic)) &&
2169 !OP_SYMBOL (IC_RIGHT (uic))->onStack)))
2172 if (IC_RIGHT (uic)->key == IC_RESULT (ic)->key &&
2173 (IS_ITEMP (IC_LEFT (uic)) ||
2174 (IS_TRUE_SYMOP (IC_LEFT (uic)) &&
2175 !OP_SYMBOL (IC_LEFT (uic))->onStack)))
2181 OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2186 /*-----------------------------------------------------------------*/
2187 /* packForPush - hueristics to reduce iCode for pushing */
2188 /*-----------------------------------------------------------------*/
2190 packForPush (iCode * ic, eBBlock * ebp)
2195 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
2198 /* must have only definition & one usage */
2199 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
2200 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
2203 /* find the definition */
2204 if (!(dic = hTabItemWithKey (iCodehTab,
2205 bitVectFirstBit (OP_DEFS (IC_LEFT (ic))))))
2208 if (dic->op != '=' || POINTER_SET (dic))
2211 /* make sure the right side does not have any definitions
2213 dbv = OP_DEFS(IC_RIGHT(dic));
2214 for (lic = ic; lic && lic != dic ; lic = lic->prev) {
2215 if (bitVectBitValue(dbv,lic->key))
2218 /* make sure they have the same type */
2220 sym_link *itype=operandType(IC_LEFT(ic));
2221 sym_link *ditype=operandType(IC_RIGHT(dic));
2223 if (SPEC_USIGN(itype)!=SPEC_USIGN(ditype) ||
2224 SPEC_LONG(itype)!=SPEC_LONG(ditype))
2227 /* extend the live range of replaced operand if needed */
2228 if (OP_SYMBOL(IC_RIGHT(dic))->liveTo < ic->seq) {
2229 OP_SYMBOL(IC_RIGHT(dic))->liveTo = ic->seq;
2231 /* we now we know that it has one & only one def & use
2232 and the that the definition is an assignment */
2233 IC_LEFT (ic) = IC_RIGHT (dic);
2235 remiCodeFromeBBlock (ebp, dic);
2236 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
2239 /*-----------------------------------------------------------------*/
2240 /* packRegisters - does some transformations to reduce register */
2242 /*-----------------------------------------------------------------*/
2244 packRegisters (eBBlock * ebp)
2254 /* look for assignments of the form */
2255 /* iTempNN = TRueSym (someoperation) SomeOperand */
2257 /* TrueSym := iTempNN:1 */
2258 for (ic = ebp->sch; ic; ic = ic->next)
2260 /* find assignment of the form TrueSym := iTempNN:1 */
2261 if (ic->op == '=' && !POINTER_SET (ic))
2262 change += packRegsForAssign (ic, ebp);
2269 for (ic = ebp->sch; ic; ic = ic->next)
2271 /* if this is an itemp & result of an address of a true sym
2272 then mark this as rematerialisable */
2273 if (ic->op == ADDRESS_OF &&
2274 IS_ITEMP (IC_RESULT (ic)) &&
2275 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2276 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2277 !OP_SYMBOL (IC_LEFT (ic))->onStack)
2280 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2281 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2282 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2286 /* if straight assignment then carry remat flag if
2287 this is the only definition */
2288 if (ic->op == '=' &&
2289 !POINTER_SET (ic) &&
2290 IS_SYMOP (IC_RIGHT (ic)) &&
2291 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2292 !IS_CAST_ICODE(OP_SYMBOL (IC_RIGHT (ic))->rematiCode) &&
2293 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1)
2296 OP_SYMBOL (IC_RESULT (ic))->remat =
2297 OP_SYMBOL (IC_RIGHT (ic))->remat;
2298 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2299 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2302 /* if cast to a generic pointer & the pointer being
2303 cast is remat, then we can remat this cast as well */
2304 if (ic->op == CAST &&
2305 IS_SYMOP(IC_RIGHT(ic)) &&
2306 OP_SYMBOL(IC_RIGHT(ic))->remat ) {
2307 sym_link *to_type = operandType(IC_LEFT(ic));
2308 sym_link *from_type = operandType(IC_RIGHT(ic));
2309 if (IS_GENPTR(to_type) && IS_PTR(from_type)) {
2310 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2311 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2312 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2316 /* if this is a +/- operation with a rematerizable
2317 then mark this as rematerializable as well */
2318 if ((ic->op == '+' || ic->op == '-') &&
2319 (IS_SYMOP (IC_LEFT (ic)) &&
2320 IS_ITEMP (IC_RESULT (ic)) &&
2321 IS_OP_LITERAL (IC_RIGHT (ic))) &&
2322 OP_SYMBOL (IC_LEFT (ic))->remat &&
2323 (!IS_SYMOP (IC_RIGHT (ic)) || !IS_CAST_ICODE(OP_SYMBOL (IC_RIGHT (ic))->rematiCode)) &&
2324 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1)
2326 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2327 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2328 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2331 /* mark the pointer usages */
2332 if (POINTER_SET (ic))
2333 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2335 if (POINTER_GET (ic))
2336 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2340 /* if we are using a symbol on the stack
2341 then we should say mcs51_ptrRegReq */
2342 if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
2343 mcs51_ptrRegReq += ((OP_SYMBOL (IC_COND (ic))->onStack ||
2344 OP_SYMBOL (IC_COND (ic))->iaccess) ? 1 : 0);
2345 else if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
2346 mcs51_ptrRegReq += ((OP_SYMBOL (IC_JTCOND (ic))->onStack ||
2347 OP_SYMBOL (IC_JTCOND (ic))->iaccess) ? 1 : 0);
2350 if (IS_SYMOP (IC_LEFT (ic)))
2351 mcs51_ptrRegReq += ((OP_SYMBOL (IC_LEFT (ic))->onStack ||
2352 OP_SYMBOL (IC_LEFT (ic))->iaccess) ? 1 : 0);
2353 if (IS_SYMOP (IC_RIGHT (ic)))
2354 mcs51_ptrRegReq += ((OP_SYMBOL (IC_RIGHT (ic))->onStack ||
2355 OP_SYMBOL (IC_RIGHT (ic))->iaccess) ? 1 : 0);
2356 if (IS_SYMOP (IC_RESULT (ic)))
2357 mcs51_ptrRegReq += ((OP_SYMBOL (IC_RESULT (ic))->onStack ||
2358 OP_SYMBOL (IC_RESULT (ic))->iaccess) ? 1 : 0);
2362 /* if the condition of an if instruction
2363 is defined in the previous instruction and
2364 this is the only usage then
2365 mark the itemp as a conditional */
2366 if ((IS_CONDITIONAL (ic) ||
2367 (IS_BITWISE_OP(ic) && isBitwiseOptimizable (ic))) &&
2368 ic->next && ic->next->op == IFX &&
2369 bitVectnBitsOn (OP_USES(IC_RESULT(ic)))==1 &&
2370 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2371 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq)
2373 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2377 /* reduce for support function calls */
2378 if (ic->supportRtn || ic->op == '+' || ic->op == '-')
2379 packRegsForSupport (ic, ebp);
2381 /* some cases the redundant moves can
2382 can be eliminated for return statements */
2383 if ((ic->op == RETURN || ic->op == SEND) &&
2384 !isOperandInFarSpace (IC_LEFT (ic)) &&
2385 options.model == MODEL_SMALL) {
2386 if (0 && options.stackAuto) {
2387 /* we should check here if acc will be clobbered for stack
2388 offset calculations */
2390 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2394 /* if pointer set & left has a size more than
2395 one and right is not in far space */
2396 if (POINTER_SET (ic) &&
2397 !isOperandInFarSpace (IC_RIGHT (ic)) &&
2398 !OP_SYMBOL (IC_RESULT (ic))->remat &&
2399 !IS_OP_RUONLY (IC_RIGHT (ic)) &&
2400 getSize (aggrToPtr (operandType (IC_RESULT (ic)), FALSE)) > 1)
2402 packRegsForOneuse (ic, IC_RESULT (ic), ebp);
2404 /* if pointer get */
2405 if (POINTER_GET (ic) &&
2406 !isOperandInFarSpace (IC_RESULT (ic)) &&
2407 !OP_SYMBOL (IC_LEFT (ic))->remat &&
2408 !IS_OP_RUONLY (IC_RESULT (ic)) &&
2409 getSize (aggrToPtr (operandType (IC_LEFT (ic)), FALSE)) > 1)
2411 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2414 /* if this is cast for intergral promotion then
2415 check if only use of the definition of the
2416 operand being casted/ if yes then replace
2417 the result of that arithmetic operation with
2418 this result and get rid of the cast */
2421 sym_link *fromType = operandType (IC_RIGHT (ic));
2422 sym_link *toType = operandType (IC_LEFT (ic));
2424 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2425 getSize (fromType) != getSize (toType) &&
2426 SPEC_USIGN (fromType) == SPEC_USIGN (toType))
2429 iCode *dic = packRegsForOneuse (ic, IC_RIGHT (ic), ebp);
2432 if (IS_ARITHMETIC_OP (dic))
2434 IC_RESULT (dic) = IC_RESULT (ic);
2435 remiCodeFromeBBlock (ebp, ic);
2436 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2437 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2441 OP_SYMBOL (IC_RIGHT (ic))->ruonly = 0;
2447 /* if the type from and type to are the same
2448 then if this is the only use then packit */
2449 if (compareType (operandType (IC_RIGHT (ic)),
2450 operandType (IC_LEFT (ic))) == 1)
2452 iCode *dic = packRegsForOneuse (ic, IC_RIGHT (ic), ebp);
2455 IC_RESULT (dic) = IC_RESULT (ic);
2456 remiCodeFromeBBlock (ebp, ic);
2457 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2458 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2466 iTempNN := (some variable in farspace) V1
2471 if (ic->op == IPUSH)
2473 packForPush (ic, ebp);
2477 /* pack registers for accumulator use, when the
2478 result of an arithmetic or bit wise operation
2479 has only one use, that use is immediately following
2480 the defintion and the using iCode has only one
2481 operand or has two operands but one is literal &
2482 the result of that operation is not on stack then
2483 we can leave the result of this operation in acc:b
2485 if ((IS_ARITHMETIC_OP (ic)
2486 || IS_CONDITIONAL(ic)
2487 || IS_BITWISE_OP (ic)
2488 || ic->op == LEFT_OP || ic->op == RIGHT_OP || ic->op == CALL
2489 || (ic->op == ADDRESS_OF && isOperandOnStack (IC_LEFT (ic)))
2491 IS_ITEMP (IC_RESULT (ic)) &&
2492 getSize (operandType (IC_RESULT (ic))) <= 2)
2494 packRegsForAccUse (ic);
2498 /*-----------------------------------------------------------------*/
2499 /* assignRegisters - assigns registers to each live range as need */
2500 /*-----------------------------------------------------------------*/
2502 mcs51_assignRegisters (eBBlock ** ebbs, int count)
2507 setToNull ((void *) &_G.funcrUsed);
2508 mcs51_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2511 /* change assignments this will remove some
2512 live ranges reducing some register pressure */
2513 for (i = 0; i < count; i++)
2514 packRegisters (ebbs[i]);
2516 if (options.dump_pack)
2517 dumpEbbsToFileExt (DUMP_PACK, ebbs, count);
2519 /* first determine for each live range the number of
2520 registers & the type of registers required for each */
2523 /* and serially allocate registers */
2524 serialRegAssign (ebbs, count);
2526 /* if stack was extended then tell the user */
2529 /* werror(W_TOOMANY_SPILS,"stack", */
2530 /* _G.stackExtend,currFunc->name,""); */
2536 /* werror(W_TOOMANY_SPILS,"data space", */
2537 /* _G.dataExtend,currFunc->name,""); */
2541 /* after that create the register mask
2542 for each of the instruction */
2543 createRegMask (ebbs, count);
2545 /* redo that offsets for stacked automatic variables */
2546 redoStackOffsets ();
2548 if (options.dump_rassgn)
2550 dumpEbbsToFileExt (DUMP_RASSGN, ebbs, count);
2551 dumpLiveRanges (DUMP_LRANGE, liveRanges);
2554 /* do the overlaysegment stuff SDCCmem.c */
2555 doOverlays (ebbs, count);
2557 /* now get back the chain */
2558 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2562 /* free up any _G.stackSpil locations allocated */
2563 applyToSet (_G.stackSpil, deallocStackSpil);
2565 setToNull ((void **) &_G.stackSpil);
2566 setToNull ((void **) &_G.spiltSet);
2567 /* mark all registers as free */