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 (sym->liveTo > fsym->liveFrom)
404 /*-----------------------------------------------------------------*/
405 /* isFree - will return 1 if the a free spil location is found */
406 /*-----------------------------------------------------------------*/
411 V_ARG (symbol **, sloc);
412 V_ARG (symbol *, fsym);
414 /* if already found */
418 /* if it is free && and the itmp assigned to
419 this does not have any overlapping live ranges
420 with the one currently being assigned and
421 the size can be accomodated */
423 noOverLap (sym->usl.itmpStack, fsym) &&
424 getSize (sym->type) >= getSize (fsym->type))
433 /*-----------------------------------------------------------------*/
434 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
435 /*-----------------------------------------------------------------*/
437 spillLRWithPtrReg (symbol * forSym)
443 if (!_G.regAssigned ||
444 bitVectIsZero (_G.regAssigned))
447 r0 = mcs51_regWithIdx (R0_IDX);
448 r1 = mcs51_regWithIdx (R1_IDX);
450 /* for all live ranges */
451 for (lrsym = hTabFirstItem (liveRanges, &k); lrsym;
452 lrsym = hTabNextItem (liveRanges, &k))
456 /* if no registers assigned to it or
458 /* if it does not overlap with this then
459 not need to spill it */
461 if (lrsym->isspilt || !lrsym->nRegs ||
462 (lrsym->liveTo < forSym->liveFrom))
465 /* go thru the registers : if it is either
466 r0 or r1 then spil it */
467 for (j = 0; j < lrsym->nRegs; j++)
468 if (lrsym->regs[j] == r0 ||
469 lrsym->regs[j] == r1)
478 /*-----------------------------------------------------------------*/
479 /* createStackSpil - create a location on the stack to spil */
480 /*-----------------------------------------------------------------*/
482 createStackSpil (symbol * sym)
485 int useXstack, model;
489 /* first go try and find a free one that is already
490 existing on the stack */
491 if (applyToSet (_G.stackSpil, isFree, &sloc, sym))
493 /* found a free one : just update & return */
494 sym->usl.spillLoc = sloc;
497 addSetHead (&sloc->usl.itmpStack, sym);
501 /* could not then have to create one , this is the hard part
502 we need to allocate this on the stack : this is really a
503 hack!! but cannot think of anything better at this time */
505 if (sprintf (slocBuffer, "sloc%d", _G.slocNum++) >= sizeof (slocBuffer))
507 fprintf (stderr, "***Internal error: slocBuffer overflowed: %s:%d\n",
512 sloc = newiTemp (slocBuffer);
514 /* set the type to the spilling symbol */
515 sloc->type = copyLinkChain (sym->type);
516 sloc->etype = getSpec (sloc->type);
517 SPEC_SCLS (sloc->etype) = S_DATA;
518 SPEC_EXTR (sloc->etype) = 0;
520 /* we don't allow it to be allocated`
521 onto the external stack since : so we
522 temporarily turn it off ; we also
523 turn off memory model to prevent
524 the spil from going to the external storage
527 useXstack = options.useXstack;
528 model = options.model;
529 /* noOverlay = options.noOverlay; */
530 /* options.noOverlay = 1; */
531 options.model = options.useXstack = 0;
535 options.useXstack = useXstack;
536 options.model = model;
537 /* options.noOverlay = noOverlay; */
538 sloc->isref = 1; /* to prevent compiler warning */
540 /* if it is on the stack then update the stack */
541 if (IN_STACK (sloc->etype))
543 currFunc->stack += getSize (sloc->type);
544 _G.stackExtend += getSize (sloc->type);
547 _G.dataExtend += getSize (sloc->type);
549 /* add it to the _G.stackSpil set */
550 addSetHead (&_G.stackSpil, sloc);
551 sym->usl.spillLoc = sloc;
554 /* add it to the set of itempStack set
555 of the spill location */
556 addSetHead (&sloc->usl.itmpStack, sym);
560 /*-----------------------------------------------------------------*/
561 /* isSpiltOnStack - returns true if the spil location is on stack */
562 /*-----------------------------------------------------------------*/
564 isSpiltOnStack (symbol * sym)
574 /* if (sym->_G.stackSpil) */
577 if (!sym->usl.spillLoc)
580 etype = getSpec (sym->usl.spillLoc->type);
581 if (IN_STACK (etype))
587 /*-----------------------------------------------------------------*/
588 /* spillThis - spils a specific operand */
589 /*-----------------------------------------------------------------*/
591 spillThis (symbol * sym)
594 /* if this is rematerializable or has a spillLocation
595 we are okay, else we need to create a spillLocation
597 if (!(sym->remat || sym->usl.spillLoc))
598 createStackSpil (sym);
601 /* mark it has spilt & put it in the spilt set */
603 _G.spiltSet = bitVectSetBit (_G.spiltSet, sym->key);
605 bitVectUnSetBit (_G.regAssigned, sym->key);
607 for (i = 0; i < sym->nRegs; i++)
611 freeReg (sym->regs[i]);
615 /* if spilt on stack then free up r0 & r1
616 if they could have been assigned to some
618 if (!mcs51_ptrRegReq && isSpiltOnStack (sym))
621 spillLRWithPtrReg (sym);
624 if (sym->usl.spillLoc && !sym->remat)
625 sym->usl.spillLoc->allocreq = 1;
629 /*-----------------------------------------------------------------*/
630 /* selectSpil - select a iTemp to spil : rather a simple procedure */
631 /*-----------------------------------------------------------------*/
633 selectSpil (iCode * ic, eBBlock * ebp, symbol * forSym)
635 bitVect *lrcs = NULL;
639 /* get the spillable live ranges */
640 lrcs = computeSpillable (ic);
642 /* get all live ranges that are rematerizable */
643 if ((selectS = liveRangesWith (lrcs, rematable, ebp, ic)))
646 /* return the least used of these */
647 return leastUsedLR (selectS);
650 /* get live ranges with spillLocations in direct space */
651 if ((selectS = liveRangesWith (lrcs, directSpilLoc, ebp, ic)))
653 sym = leastUsedLR (selectS);
654 strcpy (sym->rname, (sym->usl.spillLoc->rname[0] ?
655 sym->usl.spillLoc->rname :
656 sym->usl.spillLoc->name));
658 /* mark it as allocation required */
659 sym->usl.spillLoc->allocreq = 1;
663 /* if the symbol is local to the block then */
664 if (forSym->liveTo < ebp->lSeq)
667 /* check if there are any live ranges allocated
668 to registers that are not used in this block */
669 if (!_G.blockSpil && (selectS = liveRangesWith (lrcs, notUsedInBlock, ebp, ic)))
671 sym = leastUsedLR (selectS);
672 /* if this is not rematerializable */
681 /* check if there are any live ranges that not
682 used in the remainder of the block */
683 if (!_G.blockSpil && (selectS = liveRangesWith (lrcs, notUsedInRemaining, ebp, ic)))
685 sym = leastUsedLR (selectS);
698 /* find live ranges with spillocation && not used as pointers */
699 if ((selectS = liveRangesWith (lrcs, hasSpilLocnoUptr, ebp, ic)))
702 sym = leastUsedLR (selectS);
703 /* mark this as allocation required */
704 sym->usl.spillLoc->allocreq = 1;
708 /* find live ranges with spillocation */
709 if ((selectS = liveRangesWith (lrcs, hasSpilLoc, ebp, ic)))
712 sym = leastUsedLR (selectS);
713 sym->usl.spillLoc->allocreq = 1;
717 /* couldn't find then we need to create a spil
718 location on the stack , for which one? the least
720 if ((selectS = liveRangesWith (lrcs, noSpilLoc, ebp, ic)))
723 /* return a created spil location */
724 sym = createStackSpil (leastUsedLR (selectS));
725 sym->usl.spillLoc->allocreq = 1;
729 /* this is an extreme situation we will spill
730 this one : happens very rarely but it does happen */
736 /*-----------------------------------------------------------------*/
737 /* spilSomething - spil some variable & mark registers as free */
738 /*-----------------------------------------------------------------*/
740 spilSomething (iCode * ic, eBBlock * ebp, symbol * forSym)
745 /* get something we can spil */
746 ssym = selectSpil (ic, ebp, forSym);
748 /* mark it as spilt */
750 _G.spiltSet = bitVectSetBit (_G.spiltSet, ssym->key);
752 /* mark it as not register assigned &
753 take it away from the set */
754 bitVectUnSetBit (_G.regAssigned, ssym->key);
756 /* mark the registers as free */
757 for (i = 0; i < ssym->nRegs; i++)
759 freeReg (ssym->regs[i]);
761 /* if spilt on stack then free up r0 & r1
762 if they could have been assigned to as gprs */
763 if (!mcs51_ptrRegReq && isSpiltOnStack (ssym))
766 spillLRWithPtrReg (ssym);
769 /* if this was a block level spil then insert push & pop
770 at the start & end of block respectively */
773 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
774 /* add push to the start of the block */
775 addiCodeToeBBlock (ebp, nic, (ebp->sch->op == LABEL ?
776 ebp->sch->next : ebp->sch));
777 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
778 /* add pop to the end of the block */
779 addiCodeToeBBlock (ebp, nic, NULL);
782 /* if spilt because not used in the remainder of the
783 block then add a push before this instruction and
784 a pop at the end of the block */
785 if (ssym->remainSpil)
788 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
789 /* add push just before this instruction */
790 addiCodeToeBBlock (ebp, nic, ic);
792 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
793 /* add pop to the end of the block */
794 addiCodeToeBBlock (ebp, nic, NULL);
803 /*-----------------------------------------------------------------*/
804 /* getRegPtr - will try for PTR if not a GPR type if not spil */
805 /*-----------------------------------------------------------------*/
807 getRegPtr (iCode * ic, eBBlock * ebp, symbol * sym)
812 /* try for a ptr type */
813 if ((reg = allocReg (REG_PTR)))
816 /* try for gpr type */
817 if ((reg = allocReg (REG_GPR)))
820 /* we have to spil */
821 if (!spilSomething (ic, ebp, sym))
824 /* this looks like an infinite loop but
825 in really selectSpil will abort */
829 /*-----------------------------------------------------------------*/
830 /* getRegGpr - will try for GPR if not spil */
831 /*-----------------------------------------------------------------*/
833 getRegGpr (iCode * ic, eBBlock * ebp, symbol * sym)
838 /* try for gpr type */
839 if ((reg = allocReg (REG_GPR)))
842 if (!mcs51_ptrRegReq)
843 if ((reg = allocReg (REG_PTR)))
846 /* we have to spil */
847 if (!spilSomething (ic, ebp, sym))
850 /* this looks like an infinite loop but
851 in really selectSpil will abort */
855 /*-----------------------------------------------------------------*/
856 /* symHasReg - symbol has a given register */
857 /*-----------------------------------------------------------------*/
859 symHasReg (symbol * sym, regs * reg)
863 for (i = 0; i < sym->nRegs; i++)
864 if (sym->regs[i] == reg)
870 /*-----------------------------------------------------------------*/
871 /* deassignLRs - check the live to and if they have registers & are */
872 /* not spilt then free up the registers */
873 /*-----------------------------------------------------------------*/
875 deassignLRs (iCode * ic, eBBlock * ebp)
881 for (sym = hTabFirstItem (liveRanges, &k); sym;
882 sym = hTabNextItem (liveRanges, &k))
886 /* if it does not end here */
887 if (sym->liveTo > ic->seq)
890 /* if it was spilt on stack then we can
891 mark the stack spil location as free */
896 sym->usl.spillLoc->isFree = 1;
902 if (!bitVectBitValue (_G.regAssigned, sym->key))
905 /* special case check if this is an IFX &
906 the privious one was a pop and the
907 previous one was not spilt then keep track
909 if (ic->op == IFX && ic->prev &&
910 ic->prev->op == IPOP &&
911 !ic->prev->parmPush &&
912 !OP_SYMBOL (IC_LEFT (ic->prev))->isspilt)
913 psym = OP_SYMBOL (IC_LEFT (ic->prev));
919 bitVectUnSetBit (_G.regAssigned, sym->key);
921 /* if the result of this one needs registers
922 and does not have it then assign it right
924 if (IC_RESULT (ic) &&
925 !(SKIP_IC2 (ic) || /* not a special icode */
926 ic->op == JUMPTABLE ||
932 (result = OP_SYMBOL (IC_RESULT (ic))) && /* has a result */
933 result->liveTo > ic->seq && /* and will live beyond this */
934 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
935 result->regType == sym->regType && /* same register types */
936 result->nRegs && /* which needs registers */
937 !result->isspilt && /* and does not already have them */
939 !bitVectBitValue (_G.regAssigned, result->key) &&
940 /* the number of free regs + number of regs in this LR
941 can accomodate the what result Needs */
942 ((nfreeRegsType (result->regType) +
943 sym->nRegs) >= result->nRegs)
947 for (i = 0; i < result->nRegs; i++)
949 result->regs[i] = sym->regs[i];
951 result->regs[i] = getRegGpr (ic, ebp, result);
953 _G.regAssigned = bitVectSetBit (_G.regAssigned, result->key);
957 /* free the remaining */
958 for (; i < sym->nRegs; i++)
962 if (!symHasReg (psym, sym->regs[i]))
963 freeReg (sym->regs[i]);
966 freeReg (sym->regs[i]);
973 /*-----------------------------------------------------------------*/
974 /* reassignLR - reassign this to registers */
975 /*-----------------------------------------------------------------*/
977 reassignLR (operand * op)
979 symbol *sym = OP_SYMBOL (op);
982 /* not spilt any more */
983 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
984 bitVectUnSetBit (_G.spiltSet, sym->key);
986 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
990 for (i = 0; i < sym->nRegs; i++)
991 sym->regs[i]->isFree = 0;
994 /*-----------------------------------------------------------------*/
995 /* willCauseSpill - determines if allocating will cause a spill */
996 /*-----------------------------------------------------------------*/
998 willCauseSpill (int nr, int rt)
1000 /* first check if there are any avlb registers
1001 of te type required */
1004 /* special case for pointer type
1005 if pointer type not avlb then
1006 check for type gpr */
1007 if (nFreeRegs (rt) >= nr)
1009 if (nFreeRegs (REG_GPR) >= nr)
1014 if (mcs51_ptrRegReq)
1016 if (nFreeRegs (rt) >= nr)
1021 if (nFreeRegs (REG_PTR) +
1022 nFreeRegs (REG_GPR) >= nr)
1027 /* it will cause a spil */
1031 /*-----------------------------------------------------------------*/
1032 /* positionRegs - the allocator can allocate same registers to res- */
1033 /* ult and operand, if this happens make sure they are in the same */
1034 /* position as the operand otherwise chaos results */
1035 /*-----------------------------------------------------------------*/
1037 positionRegs (symbol * result, symbol * opsym, int lineno)
1039 int count = min (result->nRegs, opsym->nRegs);
1040 int i, j = 0, shared = 0;
1042 /* if the result has been spilt then cannot share */
1047 /* first make sure that they actually share */
1048 for (i = 0; i < count; i++)
1050 for (j = 0; j < count; j++)
1052 if (result->regs[i] == opsym->regs[j] && i != j)
1062 regs *tmp = result->regs[i];
1063 result->regs[i] = result->regs[j];
1064 result->regs[j] = tmp;
1069 /*-----------------------------------------------------------------*/
1070 /* serialRegAssign - serially allocate registers to the variables */
1071 /*-----------------------------------------------------------------*/
1073 serialRegAssign (eBBlock ** ebbs, int count)
1077 /* for all blocks */
1078 for (i = 0; i < count; i++)
1083 if (ebbs[i]->noPath &&
1084 (ebbs[i]->entryLabel != entryLabel &&
1085 ebbs[i]->entryLabel != returnLabel))
1088 /* of all instructions do */
1089 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1092 /* if this is an ipop that means some live
1093 range will have to be assigned again */
1095 reassignLR (IC_LEFT (ic));
1097 /* if result is present && is a true symbol */
1098 if (IC_RESULT (ic) && ic->op != IFX &&
1099 IS_TRUE_SYMOP (IC_RESULT (ic)))
1100 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
1102 /* take away registers from live
1103 ranges that end at this instruction */
1104 deassignLRs (ic, ebbs[i]);
1106 /* some don't need registers */
1107 if (SKIP_IC2 (ic) ||
1108 ic->op == JUMPTABLE ||
1112 (IC_RESULT (ic) && POINTER_SET (ic)))
1115 /* now we need to allocate registers
1116 only for the result */
1119 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1125 /* if it does not need or is spilt
1126 or is already assigned to registers
1127 or will not live beyond this instructions */
1130 bitVectBitValue (_G.regAssigned, sym->key) ||
1131 sym->liveTo <= ic->seq)
1134 /* if some liverange has been spilt at the block level
1135 and this one live beyond this block then spil this
1137 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq)
1142 /* if trying to allocate this will cause
1143 a spill and there is nothing to spill
1144 or this one is rematerializable then
1146 willCS = willCauseSpill (sym->nRegs, sym->regType);
1147 spillable = computeSpillable (ic);
1149 (willCS && bitVectIsZero (spillable)))
1157 /* if it has a spillocation & is used less than
1158 all other live ranges then spill this */
1159 if (willCS && sym->usl.spillLoc)
1163 leastUsedLR (liveRangesWith (spillable,
1168 leastUsed->used > sym->used)
1175 /* if we need ptr regs for the right side
1177 if (POINTER_GET (ic) && IS_SYMOP (IC_LEFT (ic))
1178 && getSize (OP_SYMBOL (IC_LEFT (ic))->type)
1184 /* else we assign registers to it */
1185 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1187 for (j = 0; j < sym->nRegs; j++)
1189 if (sym->regType == REG_PTR)
1190 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1192 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1194 /* if the allocation falied which means
1195 this was spilt then break */
1199 /* if it shares registers with operands make sure
1200 that they are in the same position */
1201 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1202 OP_SYMBOL (IC_LEFT (ic))->nRegs && ic->op != '=')
1203 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1204 OP_SYMBOL (IC_LEFT (ic)), ic->lineno);
1205 /* do the same for the right operand */
1206 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)) &&
1207 OP_SYMBOL (IC_RIGHT (ic))->nRegs)
1208 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1209 OP_SYMBOL (IC_RIGHT (ic)), ic->lineno);
1222 /*-----------------------------------------------------------------*/
1223 /* rUmaskForOp :- returns register mask for an operand */
1224 /*-----------------------------------------------------------------*/
1226 rUmaskForOp (operand * op)
1232 /* only temporaries are assigned registers */
1236 sym = OP_SYMBOL (op);
1238 /* if spilt or no registers assigned to it
1240 if (sym->isspilt || !sym->nRegs)
1243 rumask = newBitVect (mcs51_nRegs);
1245 for (j = 0; j < sym->nRegs; j++)
1247 rumask = bitVectSetBit (rumask,
1248 sym->regs[j]->rIdx);
1254 /*-----------------------------------------------------------------*/
1255 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1256 /*-----------------------------------------------------------------*/
1258 regsUsedIniCode (iCode * ic)
1260 bitVect *rmask = newBitVect (mcs51_nRegs);
1262 /* do the special cases first */
1265 rmask = bitVectUnion (rmask,
1266 rUmaskForOp (IC_COND (ic)));
1270 /* for the jumptable */
1271 if (ic->op == JUMPTABLE)
1273 rmask = bitVectUnion (rmask,
1274 rUmaskForOp (IC_JTCOND (ic)));
1279 /* of all other cases */
1281 rmask = bitVectUnion (rmask,
1282 rUmaskForOp (IC_LEFT (ic)));
1286 rmask = bitVectUnion (rmask,
1287 rUmaskForOp (IC_RIGHT (ic)));
1290 rmask = bitVectUnion (rmask,
1291 rUmaskForOp (IC_RESULT (ic)));
1297 /*-----------------------------------------------------------------*/
1298 /* createRegMask - for each instruction will determine the regsUsed */
1299 /*-----------------------------------------------------------------*/
1301 createRegMask (eBBlock ** ebbs, int count)
1305 /* for all blocks */
1306 for (i = 0; i < count; i++)
1310 if (ebbs[i]->noPath &&
1311 (ebbs[i]->entryLabel != entryLabel &&
1312 ebbs[i]->entryLabel != returnLabel))
1315 /* for all instructions */
1316 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1321 if (SKIP_IC2 (ic) || !ic->rlive)
1324 /* first mark the registers used in this
1326 ic->rUsed = regsUsedIniCode (ic);
1327 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1329 /* now create the register mask for those
1330 registers that are in use : this is a
1331 super set of ic->rUsed */
1332 ic->rMask = newBitVect (mcs51_nRegs + 1);
1334 /* for all live Ranges alive at this point */
1335 for (j = 1; j < ic->rlive->size; j++)
1340 /* if not alive then continue */
1341 if (!bitVectBitValue (ic->rlive, j))
1344 /* find the live range we are interested in */
1345 if (!(sym = hTabItemWithKey (liveRanges, j)))
1347 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
1348 "createRegMask cannot find live range");
1352 /* if no register assigned to it */
1353 if (!sym->nRegs || sym->isspilt)
1356 /* for all the registers allocated to it */
1357 for (k = 0; k < sym->nRegs; k++)
1360 bitVectSetBit (ic->rMask, sym->regs[k]->rIdx);
1366 /*-----------------------------------------------------------------*/
1367 /* rematStr - returns the rematerialized string for a remat var */
1368 /*-----------------------------------------------------------------*/
1370 rematStr (symbol * sym)
1373 iCode *ic = sym->rematiCode;
1378 /* if plus or minus print the right hand side */
1379 if (ic->op == '+' || ic->op == '-')
1381 sprintf (s, "0x%04x %c ", (int) operandLitValue (IC_RIGHT (ic)),
1384 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1388 /* we reached the end */
1389 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1396 /*-----------------------------------------------------------------*/
1397 /* regTypeNum - computes the type & number of registers required */
1398 /*-----------------------------------------------------------------*/
1406 /* for each live range do */
1407 for (sym = hTabFirstItem (liveRanges, &k); sym;
1408 sym = hTabNextItem (liveRanges, &k))
1411 /* if used zero times then no registers needed */
1412 if ((sym->liveTo - sym->liveFrom) == 0)
1416 /* if the live range is a temporary */
1420 /* if the type is marked as a conditional */
1421 if (sym->regType == REG_CND)
1424 /* if used in return only then we don't
1426 if (sym->ruonly || sym->accuse)
1428 if (IS_AGGREGATE (sym->type) || sym->isptr)
1429 sym->type = aggrToPtr (sym->type, FALSE);
1433 /* if the symbol has only one definition &
1434 that definition is a get_pointer and the
1435 pointer we are getting is rematerializable and
1438 if (bitVectnBitsOn (sym->defs) == 1 &&
1439 (ic = hTabItemWithKey (iCodehTab,
1440 bitVectFirstBit (sym->defs))) &&
1442 !IS_BITVAR (sym->etype))
1446 /* if remat in data space */
1447 if (OP_SYMBOL (IC_LEFT (ic))->remat &&
1448 DCL_TYPE (aggrToPtr (sym->type, FALSE)) == POINTER)
1451 /* create a psuedo symbol & force a spil */
1452 symbol *psym = newSymbol (rematStr (OP_SYMBOL (IC_LEFT (ic))), 1);
1453 psym->type = sym->type;
1454 psym->etype = sym->etype;
1455 strcpy (psym->rname, psym->name);
1457 sym->usl.spillLoc = psym;
1461 /* if in data space or idata space then try to
1462 allocate pointer register */
1466 /* if not then we require registers */
1467 sym->nRegs = ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1468 getSize (sym->type = aggrToPtr (sym->type, FALSE)) :
1469 getSize (sym->type));
1473 fprintf (stderr, "allocated more than 4 or 0 registers for type ");
1474 printTypeChain (sym->type, stderr);
1475 fprintf (stderr, "\n");
1478 /* determine the type of register required */
1479 if (sym->nRegs == 1 &&
1480 IS_PTR (sym->type) &&
1482 sym->regType = REG_PTR;
1484 sym->regType = REG_GPR;
1488 /* for the first run we don't provide */
1489 /* registers for true symbols we will */
1490 /* see how things go */
1496 /*-----------------------------------------------------------------*/
1497 /* freeAllRegs - mark all registers as free */
1498 /*-----------------------------------------------------------------*/
1504 for (i = 0; i < mcs51_nRegs; i++)
1505 regs8051[i].isFree = 1;
1508 /*-----------------------------------------------------------------*/
1509 /* deallocStackSpil - this will set the stack pointer back */
1510 /*-----------------------------------------------------------------*/
1512 DEFSETFUNC (deallocStackSpil)
1520 /*-----------------------------------------------------------------*/
1521 /* farSpacePackable - returns the packable icode for far variables */
1522 /*-----------------------------------------------------------------*/
1524 farSpacePackable (iCode * ic)
1528 /* go thru till we find a definition for the
1529 symbol on the right */
1530 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 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)))
1608 if ((dic = farSpacePackable (ic)))
1614 /* find the definition of iTempNN scanning backwards if we find a
1615 a use of the true symbol in before we find the definition then
1617 for (dic = ic->prev; dic; dic = dic->prev)
1620 /* if there is a function call and this is
1621 a parameter & not my parameter then don't pack it */
1622 if ((dic->op == CALL || dic->op == PCALL) &&
1623 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1624 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
1633 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1634 IS_OP_VOLATILE (IC_RESULT (dic)))
1640 if (IS_SYMOP (IC_RESULT (dic)) &&
1641 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1643 if (POINTER_SET (dic))
1649 if (IS_SYMOP (IC_RIGHT (dic)) &&
1650 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1651 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key))
1657 if (IS_SYMOP (IC_LEFT (dic)) &&
1658 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1659 IC_LEFT (dic)->key == IC_RIGHT (ic)->key))
1665 if (POINTER_SET (dic) &&
1666 IC_RESULT (dic)->key == IC_RESULT (ic)->key)
1674 return 0; /* did not find */
1676 /* if assignment then check that right is not a bit */
1677 if (ASSIGNMENT (dic) && !POINTER_SET (dic))
1679 sym_link *etype = operandType (IC_RIGHT (dic));
1680 if (IS_BITFIELD (etype))
1683 /* if the result is on stack or iaccess then it must be
1684 the same atleast one of the operands */
1685 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1686 OP_SYMBOL (IC_RESULT (ic))->iaccess)
1689 /* the operation has only one symbol
1690 operator then we can pack */
1691 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1692 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1695 if (!((IC_LEFT (dic) &&
1696 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1698 IC_RESULT (ic)->key == IC_RIGHT (dic)->key)))
1702 /* found the definition */
1703 /* replace the result with the result of */
1704 /* this assignment and remove this assignment */
1705 IC_RESULT (dic) = IC_RESULT (ic);
1707 if (IS_ITEMP (IC_RESULT (dic)) && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq)
1709 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1711 /* delete from liverange table also
1712 delete from all the points inbetween and the new
1714 for (sic = dic; sic != ic; sic = sic->next)
1716 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1717 if (IS_ITEMP (IC_RESULT (dic)))
1718 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1721 remiCodeFromeBBlock (ebp, ic);
1722 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1723 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
1728 /*-----------------------------------------------------------------*/
1729 /* findAssignToSym : scanning backwards looks for first assig found */
1730 /*-----------------------------------------------------------------*/
1732 findAssignToSym (operand * op, iCode * ic)
1736 for (dic = ic->prev; dic; dic = dic->prev)
1739 /* if definition by assignment */
1740 if (dic->op == '=' &&
1741 !POINTER_SET (dic) &&
1742 IC_RESULT (dic)->key == op->key
1743 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1747 /* we are interested only if defined in far space */
1748 /* or in stack space in case of + & - */
1750 /* if assigned to a non-symbol then return
1752 if (!IS_SYMOP (IC_RIGHT (dic)))
1755 /* if the symbol is in far space then
1757 if (isOperandInFarSpace (IC_RIGHT (dic)))
1760 /* for + & - operations make sure that
1761 if it is on the stack it is the same
1762 as one of the three operands */
1763 if ((ic->op == '+' || ic->op == '-') &&
1764 OP_SYMBOL (IC_RIGHT (dic))->onStack)
1767 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key &&
1768 IC_LEFT (ic)->key != IC_RIGHT (dic)->key &&
1769 IC_RIGHT (ic)->key != IC_RIGHT (dic)->key)
1777 /* if we find an usage then we cannot delete it */
1778 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
1781 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
1784 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
1788 /* now make sure that the right side of dic
1789 is not defined between ic & dic */
1792 iCode *sic = dic->next;
1794 for (; sic != ic; sic = sic->next)
1795 if (IC_RESULT (sic) &&
1796 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
1805 /*-----------------------------------------------------------------*/
1806 /* packRegsForSupport :- reduce some registers for support calls */
1807 /*-----------------------------------------------------------------*/
1809 packRegsForSupport (iCode * ic, eBBlock * ebp)
1812 /* for the left & right operand :- look to see if the
1813 left was assigned a true symbol in far space in that
1814 case replace them */
1815 if (IS_ITEMP (IC_LEFT (ic)) &&
1816 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq)
1818 iCode *dic = findAssignToSym (IC_LEFT (ic), ic);
1824 /* found it we need to remove it from the
1826 for (sic = dic; sic != ic; sic = sic->next)
1827 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
1829 IC_LEFT (ic)->operand.symOperand =
1830 IC_RIGHT (dic)->operand.symOperand;
1831 IC_LEFT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1832 remiCodeFromeBBlock (ebp, dic);
1833 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1837 /* do the same for the right operand */
1840 IS_ITEMP (IC_RIGHT (ic)) &&
1841 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq)
1843 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
1849 /* if this is a subtraction & the result
1850 is a true symbol in far space then don't pack */
1851 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic)))
1853 sym_link *etype = getSpec (operandType (IC_RESULT (dic)));
1854 if (IN_FARSPACE (SPEC_OCLS (etype)))
1857 /* found it we need to remove it from the
1859 for (sic = dic; sic != ic; sic = sic->next)
1860 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
1862 IC_RIGHT (ic)->operand.symOperand =
1863 IC_RIGHT (dic)->operand.symOperand;
1864 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1866 remiCodeFromeBBlock (ebp, dic);
1867 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1874 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1877 /*-----------------------------------------------------------------*/
1878 /* packRegsForOneuse : - will reduce some registers for single Use */
1879 /*-----------------------------------------------------------------*/
1881 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1886 /* if returning a literal then do nothing */
1890 /* only upto 2 bytes since we cannot predict
1891 the usage of b, & acc */
1892 if (getSize (operandType (op)) > (fReturnSize - 2) &&
1895 !POINTER_SET (ic) &&
1899 /* this routine will mark the a symbol as used in one
1900 instruction use only && if the defintion is local
1901 (ie. within the basic block) && has only one definition &&
1902 that definiion is either a return value from a
1903 function or does not contain any variables in
1905 uses = bitVectCopy (OP_USES (op));
1906 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1907 if (!bitVectIsZero (uses)) /* has other uses */
1910 /* if it has only one defintion */
1911 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1912 return NULL; /* has more than one definition */
1914 /* get the that definition */
1916 hTabItemWithKey (iCodehTab,
1917 bitVectFirstBit (OP_DEFS (op)))))
1920 /* found the definition now check if it is local */
1921 if (dic->seq < ebp->fSeq ||
1922 dic->seq > ebp->lSeq)
1923 return NULL; /* non-local */
1925 /* now check if it is the return from
1927 if (dic->op == CALL || dic->op == PCALL)
1929 if (ic->op != SEND && ic->op != RETURN)
1931 OP_SYMBOL (op)->ruonly = 1;
1938 /* otherwise check that the definition does
1939 not contain any symbols in far space */
1940 if (isOperandInFarSpace (IC_LEFT (dic)) ||
1941 isOperandInFarSpace (IC_RIGHT (dic)) ||
1942 IS_OP_RUONLY (IC_LEFT (ic)) ||
1943 IS_OP_RUONLY (IC_RIGHT (ic)))
1948 /* if pointer set then make sure the pointer
1950 if (POINTER_SET (dic) &&
1951 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1954 if (POINTER_GET (dic) &&
1955 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1960 /* also make sure the intervenening instructions
1961 don't have any thing in far space */
1962 for (dic = dic->next; dic && dic != ic && sic != ic; dic = dic->next)
1965 /* if there is an intervening function call then no */
1966 if (dic->op == CALL || dic->op == PCALL)
1968 /* if pointer set then make sure the pointer
1970 if (POINTER_SET (dic) &&
1971 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1974 if (POINTER_GET (dic) &&
1975 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1978 /* if address of & the result is remat the okay */
1979 if (dic->op == ADDRESS_OF &&
1980 OP_SYMBOL (IC_RESULT (dic))->remat)
1983 /* if operand has size of three or more & this
1984 operation is a '*','/' or '%' then 'b' may
1986 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1987 getSize (operandType (op)) >= 3)
1990 /* if left or right or result is in far space */
1991 if (isOperandInFarSpace (IC_LEFT (dic)) ||
1992 isOperandInFarSpace (IC_RIGHT (dic)) ||
1993 isOperandInFarSpace (IC_RESULT (dic)) ||
1994 IS_OP_RUONLY (IC_LEFT (dic)) ||
1995 IS_OP_RUONLY (IC_RIGHT (dic)) ||
1996 IS_OP_RUONLY (IC_RESULT (dic)))
2002 OP_SYMBOL (op)->ruonly = 1;
2007 /*-----------------------------------------------------------------*/
2008 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
2009 /*-----------------------------------------------------------------*/
2011 isBitwiseOptimizable (iCode * ic)
2013 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
2014 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
2016 /* bitwise operations are considered optimizable
2017 under the following conditions (Jean-Louis VERN)
2029 if (IS_LITERAL (rtype) ||
2030 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
2036 /*-----------------------------------------------------------------*/
2037 /* packRegsForAccUse - pack registers for acc use */
2038 /*-----------------------------------------------------------------*/
2040 packRegsForAccUse (iCode * ic)
2044 /* if + or - then it has to be one byte result */
2045 if ((ic->op == '+' || ic->op == '-')
2046 && getSize (operandType (IC_RESULT (ic))) > 1)
2049 /* if shift operation make sure right side is not a literal */
2050 if (ic->op == RIGHT_OP &&
2051 (isOperandLiteral (IC_RIGHT (ic)) ||
2052 getSize (operandType (IC_RESULT (ic))) > 1))
2055 if (ic->op == LEFT_OP &&
2056 (isOperandLiteral (IC_RIGHT (ic)) ||
2057 getSize (operandType (IC_RESULT (ic))) > 1))
2060 if (IS_BITWISE_OP (ic) &&
2061 getSize (operandType (IC_RESULT (ic))) > 1)
2065 /* has only one definition */
2066 if (bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) > 1)
2069 /* has only one use */
2070 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) > 1)
2073 /* and the usage immediately follows this iCode */
2074 if (!(uic = hTabItemWithKey (iCodehTab,
2075 bitVectFirstBit (OP_USES (IC_RESULT (ic))))))
2078 if (ic->next != uic)
2081 /* if it is a conditional branch then we definitely can */
2085 if (uic->op == JUMPTABLE)
2088 /* if the usage is not is an assignment
2089 or an arithmetic / bitwise / shift operation then not */
2090 if (POINTER_SET (uic) &&
2091 getSize (aggrToPtr (operandType (IC_RESULT (uic)), FALSE)) > 1)
2094 if (uic->op != '=' &&
2095 !IS_ARITHMETIC_OP (uic) &&
2096 !IS_BITWISE_OP (uic) &&
2097 uic->op != LEFT_OP &&
2098 uic->op != RIGHT_OP)
2101 /* if used in ^ operation then make sure right is not a
2103 if (uic->op == '^' && isOperandLiteral (IC_RIGHT (uic)))
2106 /* if shift operation make sure right side is not a literal */
2107 if (uic->op == RIGHT_OP &&
2108 (isOperandLiteral (IC_RIGHT (uic)) ||
2109 getSize (operandType (IC_RESULT (uic))) > 1))
2112 if (uic->op == LEFT_OP &&
2113 (isOperandLiteral (IC_RIGHT (uic)) ||
2114 getSize (operandType (IC_RESULT (uic))) > 1))
2117 /* make sure that the result of this icode is not on the
2118 stack, since acc is used to compute stack offset */
2119 if (IS_TRUE_SYMOP (IC_RESULT (uic)) &&
2120 OP_SYMBOL (IC_RESULT (uic))->onStack)
2123 /* if either one of them in far space then we cannot */
2124 if ((IS_TRUE_SYMOP (IC_LEFT (uic)) &&
2125 isOperandInFarSpace (IC_LEFT (uic))) ||
2126 (IS_TRUE_SYMOP (IC_RIGHT (uic)) &&
2127 isOperandInFarSpace (IC_RIGHT (uic))))
2130 /* if the usage has only one operand then we can */
2131 if (IC_LEFT (uic) == NULL ||
2132 IC_RIGHT (uic) == NULL)
2135 /* make sure this is on the left side if not
2136 a '+' since '+' is commutative */
2137 if (ic->op != '+' &&
2138 IC_LEFT (uic)->key != IC_RESULT (ic)->key)
2141 /* if one of them is a literal then we can */
2142 if ((IC_LEFT (uic) && IS_OP_LITERAL (IC_LEFT (uic))) ||
2143 (IC_RIGHT (uic) && IS_OP_LITERAL (IC_RIGHT (uic))))
2145 OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2149 /* if the other one is not on stack then we can */
2150 if (IC_LEFT (uic)->key == IC_RESULT (ic)->key &&
2151 (IS_ITEMP (IC_RIGHT (uic)) ||
2152 (IS_TRUE_SYMOP (IC_RIGHT (uic)) &&
2153 !OP_SYMBOL (IC_RIGHT (uic))->onStack)))
2156 if (IC_RIGHT (uic)->key == IC_RESULT (ic)->key &&
2157 (IS_ITEMP (IC_LEFT (uic)) ||
2158 (IS_TRUE_SYMOP (IC_LEFT (uic)) &&
2159 !OP_SYMBOL (IC_LEFT (uic))->onStack)))
2165 OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2170 /*-----------------------------------------------------------------*/
2171 /* packForPush - hueristics to reduce iCode for pushing */
2172 /*-----------------------------------------------------------------*/
2174 packForPush (iCode * ic, eBBlock * ebp)
2178 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
2181 /* must have only definition & one usage */
2182 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
2183 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
2186 /* find the definition */
2187 if (!(dic = hTabItemWithKey (iCodehTab,
2188 bitVectFirstBit (OP_DEFS (IC_LEFT (ic))))))
2191 if (dic->op != '=' || POINTER_SET (dic))
2194 /* we now we know that it has one & only one def & use
2195 and the that the definition is an assignment */
2196 IC_LEFT (ic) = IC_RIGHT (dic);
2198 remiCodeFromeBBlock (ebp, dic);
2199 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
2202 /*-----------------------------------------------------------------*/
2203 /* packRegisters - does some transformations to reduce register */
2205 /*-----------------------------------------------------------------*/
2207 packRegisters (eBBlock * ebp)
2217 /* look for assignments of the form */
2218 /* iTempNN = TRueSym (someoperation) SomeOperand */
2220 /* TrueSym := iTempNN:1 */
2221 for (ic = ebp->sch; ic; ic = ic->next)
2225 /* find assignment of the form TrueSym := iTempNN:1 */
2226 if (ic->op == '=' && !POINTER_SET (ic))
2227 change += packRegsForAssign (ic, ebp);
2234 for (ic = ebp->sch; ic; ic = ic->next)
2237 /* if this is an itemp & result of a address of a true sym
2238 then mark this as rematerialisable */
2239 if (ic->op == ADDRESS_OF &&
2240 IS_ITEMP (IC_RESULT (ic)) &&
2241 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2242 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2243 !OP_SYMBOL (IC_LEFT (ic))->onStack)
2246 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2247 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2248 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2252 /* if straight assignment then carry remat flag if
2253 this is the only definition */
2254 if (ic->op == '=' &&
2255 !POINTER_SET (ic) &&
2256 IS_SYMOP (IC_RIGHT (ic)) &&
2257 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2258 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1)
2261 OP_SYMBOL (IC_RESULT (ic))->remat =
2262 OP_SYMBOL (IC_RIGHT (ic))->remat;
2263 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2264 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2267 /* if this is a +/- operation with a rematerizable
2268 then mark this as rematerializable as well */
2269 if ((ic->op == '+' || ic->op == '-') &&
2270 (IS_SYMOP (IC_LEFT (ic)) &&
2271 IS_ITEMP (IC_RESULT (ic)) &&
2272 OP_SYMBOL (IC_LEFT (ic))->remat &&
2273 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2274 IS_OP_LITERAL (IC_RIGHT (ic))))
2277 //int i = operandLitValue (IC_RIGHT (ic));
2278 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2279 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2280 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2283 /* mark the pointer usages */
2284 if (POINTER_SET (ic))
2285 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2287 if (POINTER_GET (ic))
2288 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2292 /* if we are using a symbol on the stack
2293 then we should say mcs51_ptrRegReq */
2294 if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
2295 mcs51_ptrRegReq += ((OP_SYMBOL (IC_COND (ic))->onStack ||
2296 OP_SYMBOL (IC_COND (ic))->iaccess) ? 1 : 0);
2297 else if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
2298 mcs51_ptrRegReq += ((OP_SYMBOL (IC_JTCOND (ic))->onStack ||
2299 OP_SYMBOL (IC_JTCOND (ic))->iaccess) ? 1 : 0);
2302 if (IS_SYMOP (IC_LEFT (ic)))
2303 mcs51_ptrRegReq += ((OP_SYMBOL (IC_LEFT (ic))->onStack ||
2304 OP_SYMBOL (IC_LEFT (ic))->iaccess) ? 1 : 0);
2305 if (IS_SYMOP (IC_RIGHT (ic)))
2306 mcs51_ptrRegReq += ((OP_SYMBOL (IC_RIGHT (ic))->onStack ||
2307 OP_SYMBOL (IC_RIGHT (ic))->iaccess) ? 1 : 0);
2308 if (IS_SYMOP (IC_RESULT (ic)))
2309 mcs51_ptrRegReq += ((OP_SYMBOL (IC_RESULT (ic))->onStack ||
2310 OP_SYMBOL (IC_RESULT (ic))->iaccess) ? 1 : 0);
2314 /* if the condition of an if instruction
2315 is defined in the previous instruction then
2316 mark the itemp as a conditional */
2317 if ((IS_CONDITIONAL (ic) ||
2318 ((ic->op == BITWISEAND ||
2321 isBitwiseOptimizable (ic))) &&
2322 ic->next && ic->next->op == IFX &&
2323 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2324 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq)
2327 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2331 /* reduce for support function calls */
2332 if (ic->supportRtn || ic->op == '+' || ic->op == '-')
2333 packRegsForSupport (ic, ebp);
2335 /* some cases the redundant moves can
2336 can be eliminated for return statements */
2337 if ((ic->op == RETURN || ic->op == SEND) &&
2338 !isOperandInFarSpace (IC_LEFT (ic)) &&
2339 options.model == MODEL_SMALL)
2340 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2342 /* if pointer set & left has a size more than
2343 one and right is not in far space */
2344 if (POINTER_SET (ic) &&
2345 !isOperandInFarSpace (IC_RIGHT (ic)) &&
2346 !OP_SYMBOL (IC_RESULT (ic))->remat &&
2347 !IS_OP_RUONLY (IC_RIGHT (ic)) &&
2348 getSize (aggrToPtr (operandType (IC_RESULT (ic)), FALSE)) > 1)
2350 packRegsForOneuse (ic, IC_RESULT (ic), ebp);
2352 /* if pointer get */
2353 if (POINTER_GET (ic) &&
2354 !isOperandInFarSpace (IC_RESULT (ic)) &&
2355 !OP_SYMBOL (IC_LEFT (ic))->remat &&
2356 !IS_OP_RUONLY (IC_RESULT (ic)) &&
2357 getSize (aggrToPtr (operandType (IC_LEFT (ic)), FALSE)) > 1)
2359 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2362 /* if this is cast for intergral promotion then
2363 check if only use of the definition of the
2364 operand being casted/ if yes then replace
2365 the result of that arithmetic operation with
2366 this result and get rid of the cast */
2369 sym_link *fromType = operandType (IC_RIGHT (ic));
2370 sym_link *toType = operandType (IC_LEFT (ic));
2372 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2373 getSize (fromType) != getSize (toType) &&
2374 SPEC_USIGN (fromType) == SPEC_USIGN (toType))
2377 iCode *dic = packRegsForOneuse (ic, IC_RIGHT (ic), ebp);
2380 if (IS_ARITHMETIC_OP (dic))
2382 IC_RESULT (dic) = IC_RESULT (ic);
2383 remiCodeFromeBBlock (ebp, ic);
2384 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2385 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2389 OP_SYMBOL (IC_RIGHT (ic))->ruonly = 0;
2395 /* if the type from and type to are the same
2396 then if this is the only use then packit */
2397 if (checkType (operandType (IC_RIGHT (ic)),
2398 operandType (IC_LEFT (ic))) == 1)
2400 iCode *dic = packRegsForOneuse (ic, IC_RIGHT (ic), ebp);
2403 IC_RESULT (dic) = IC_RESULT (ic);
2404 remiCodeFromeBBlock (ebp, ic);
2405 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2406 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2414 iTempNN := (some variable in farspace) V1
2419 if (ic->op == IPUSH)
2421 packForPush (ic, ebp);
2425 /* pack registers for accumulator use, when the
2426 result of an arithmetic or bit wise operation
2427 has only one use, that use is immediately following
2428 the defintion and the using iCode has only one
2429 operand or has two operands but one is literal &
2430 the result of that operation is not on stack then
2431 we can leave the result of this operation in acc:b
2433 if ((IS_ARITHMETIC_OP (ic)
2434 || IS_BITWISE_OP (ic)
2435 || ic->op == LEFT_OP || ic->op == RIGHT_OP
2436 || (ic->op == ADDRESS_OF && isOperandOnStack (IC_LEFT (ic)))
2438 IS_ITEMP (IC_RESULT (ic)) &&
2439 getSize (operandType (IC_RESULT (ic))) <= 2)
2441 packRegsForAccUse (ic);
2446 /*-----------------------------------------------------------------*/
2447 /* assignRegisters - assigns registers to each live range as need */
2448 /*-----------------------------------------------------------------*/
2450 mcs51_assignRegisters (eBBlock ** ebbs, int count)
2455 setToNull ((void *) &_G.funcrUsed);
2456 mcs51_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2457 /* if not register extentions then reduce number
2459 if (options.regExtend)
2464 /* change assignments this will remove some
2465 live ranges reducing some register pressure */
2466 for (i = 0; i < count; i++)
2467 packRegisters (ebbs[i]);
2469 if (options.dump_pack)
2470 dumpEbbsToFileExt (".dumppack", ebbs, count);
2472 /* first determine for each live range the number of
2473 registers & the type of registers required for each */
2476 /* and serially allocate registers */
2477 serialRegAssign (ebbs, count);
2479 /* if stack was extended then tell the user */
2482 /* werror(W_TOOMANY_SPILS,"stack", */
2483 /* _G.stackExtend,currFunc->name,""); */
2489 /* werror(W_TOOMANY_SPILS,"data space", */
2490 /* _G.dataExtend,currFunc->name,""); */
2494 /* after that create the register mask
2495 for each of the instruction */
2496 createRegMask (ebbs, count);
2498 /* redo that offsets for stacked automatic variables */
2499 redoStackOffsets ();
2501 if (options.dump_rassgn)
2503 dumpEbbsToFileExt (".dumprassgn", ebbs, count);
2504 dumpLiveRanges (".lrange", liveRanges);
2507 /* do the overlaysegment stuff SDCCmem.c */
2508 doOverlays (ebbs, count);
2510 /* now get back the chain */
2511 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2516 /* free up any _G.stackSpil locations allocated */
2517 applyToSet (_G.stackSpil, deallocStackSpil);
2519 setToNull ((void **) &_G.stackSpil);
2520 setToNull ((void **) &_G.spiltSet);
2521 /* mark all registers as free */