1 /*------------------------------------------------------------------------
3 SDCCralloc.c - source file for register allocation. (ATMEL AVR) 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 genAVRCode (iCode *);
48 bitVect *funcrUsed; /* registers used in a function */
53 /* Shared with gen.c */
54 int avr_ptrRegReq; /* pointer register required */
58 {REG_GPR|REG_PAIR, R0_IDX, REG_GPR|REG_PAIR, "r0", "r0", "", 0, 0, 0}, /* scratch */
59 {REG_GPR, R1_IDX, REG_GPR , "r1", "r1", "", 0, 0, 0}, /* scratch */
60 {REG_GPR|REG_PAIR, R2_IDX, REG_GPR|REG_PAIR, "r2", "r2", "", 0, 1, 1}, /* gpr */
61 {REG_GPR, R3_IDX, REG_GPR , "r3", "r3", "", 0, 1, 1}, /* gpr */
62 {REG_GPR|REG_PAIR, R4_IDX, REG_GPR|REG_PAIR, "r4", "r4", "", 0, 1, 1}, /* gpr */
63 {REG_GPR, R5_IDX, REG_GPR , "r5", "r5", "", 0, 1, 1}, /* gpr */
64 {REG_GPR|REG_PAIR, R6_IDX, REG_GPR|REG_PAIR, "r6", "r6", "", 0, 1, 1}, /* gpr */
65 {REG_GPR, R7_IDX, REG_GPR , "r7", "r7", "", 0, 1, 1}, /* gpr */
66 {REG_GPR|REG_PAIR, R8_IDX, REG_GPR|REG_PAIR, "r8", "r8", "", 0, 1, 1}, /* gpr */
67 {REG_GPR, R9_IDX, REG_GPR , "r9", "r9", "", 0, 1, 1}, /* gpr */
68 {REG_GPR|REG_PAIR, R10_IDX,REG_GPR|REG_PAIR, "r10", "r10","",0, 1, 1}, /* gpr */
69 {REG_GPR, R11_IDX,REG_GPR , "r11", "r11","",0, 1, 1}, /* gpr */
70 {REG_GPR|REG_PAIR, R12_IDX,REG_GPR|REG_PAIR, "r12", "r12","",0, 1, 1}, /* gpr */
71 {REG_GPR, R13_IDX,REG_GPR , "r13", "r13","",0, 1, 1}, /* gpr */
72 {REG_GPR|REG_PAIR, R14_IDX,REG_GPR|REG_PAIR, "r14", "r14","",0, 1, 1}, /* gpr */
73 {REG_GPR, R15_IDX,REG_GPR , "r15", "r15","",0, 1, 1}, /* gpr */
74 {REG_GPR|REG_PAIR, R16_IDX,REG_GPR|REG_PAIR, "r16", "r16","",0, 1, 0}, /* parm/gpr */
75 {REG_GPR, R17_IDX,REG_GPR , "r17", "r17","",0, 1, 0}, /* parm/gpr */
76 {REG_GPR|REG_PAIR, R18_IDX,REG_GPR|REG_PAIR, "r18", "r18","",0, 1, 0}, /* parm/gpr */
77 {REG_GPR, R19_IDX,REG_GPR , "r19", "r19","",0, 1, 0}, /* parm/gpr */
78 {REG_GPR|REG_PAIR, R20_IDX,REG_GPR|REG_PAIR, "r20", "r20","",0, 1, 0}, /* parm/gpr */
79 {REG_GPR, R21_IDX,REG_GPR , "r21", "r21","",0, 1, 0}, /* parm/gpr */
80 {REG_GPR|REG_PAIR, R22_IDX,REG_GPR|REG_PAIR, "r22", "r22","",0, 1, 0}, /* parm/gpr */
81 {REG_GPR, R23_IDX,REG_GPR , "r23", "r23","",0, 1, 0}, /* parm/gpr */
82 {REG_GPR|REG_PAIR, R24_IDX,REG_GPR|REG_PAIR, "r24", "r24","",0, 0, 0}, /* scratch */
83 {REG_GPR, R25_IDX,REG_GPR , "r25", "r25","",0, 0, 0}, /* scratch */
84 {REG_GPR|REG_PAIR, R26_IDX,REG_GPR|REG_PAIR, "r26", "r26","",0, 1, 1}, /* used as pointer reg X */
85 {REG_GPR, R27_IDX,REG_GPR , "r27", "r27","",0, 1, 1}, /* used as pointer reg X */
86 {REG_GPR|REG_PAIR, R28_IDX,REG_GPR|REG_PAIR, "r28", "r28","",0, 1, 0}, /* stack frame Y */
87 {REG_GPR, R29_IDX,REG_GPR , "r29", "r29","",0, 1, 0}, /* stack frame Y */
88 {REG_GPR|REG_PAIR, R30_IDX,REG_GPR|REG_PAIR, "r30", "r30","",0, 1, 1}, /* used as pointer reg Z */
89 {REG_GPR, R31_IDX,REG_GPR , "r31", "r31","",0, 1, 1}, /* used as pointer reg Z */
90 {REG_PTR, X_IDX, REG_PTR, "X", "X", "", 0, 1, 0},
91 {REG_PTR, Z_IDX, REG_PTR, "Z", "Z", "", 0, 1, 0},
94 int avr_fReg = 0; /* first allocatable register */
96 static void spillThis (symbol *);
100 /*-----------------------------------------------------------------*/
101 /* findAssignToSym : scanning backwards looks for first assig found */
102 /*-----------------------------------------------------------------*/
104 findAssignToSym (operand * op, iCode * ic)
108 for (dic = ic->prev; dic; dic = dic->prev) {
110 /* if definition by assignment */
111 if (dic->op == '=' &&
112 !POINTER_SET (dic) && IC_RESULT (dic)->key == op->key
113 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
116 /* we are interested only if defined in far space */
117 /* or in stack space in case of + & - */
119 /* if assigned to a non-symbol then return
121 if (!IS_SYMOP (IC_RIGHT (dic)))
124 /* if the symbol is in far space then
126 if (isOperandInFarSpace (IC_RIGHT (dic)))
129 /* for + & - operations make sure that
130 if it is on the stack it is the same
131 as one of the three operands */
132 if ((ic->op == '+' || ic->op == '-') &&
133 OP_SYMBOL (IC_RIGHT (dic))->onStack) {
135 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key
136 && IC_LEFT (ic)->key !=
138 && IC_RIGHT (ic)->key !=
139 IC_RIGHT (dic)->key) return NULL;
146 /* if we find an usage then we cannot delete it */
147 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
150 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
153 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
157 /* now make sure that the right side of dic
158 is not defined between ic & dic */
160 iCode *sic = dic->next;
162 for (; sic != ic; sic = sic->next)
163 if (IC_RESULT (sic) &&
164 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
173 /*-----------------------------------------------------------------*/
174 /* packForPush - hueristics to reduce iCode for pushing */
175 /*-----------------------------------------------------------------*/
177 packForPush (iCode * ic, eBBlock * ebp)
181 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
184 /* must have only definition & one usage */
185 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
186 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
189 /* find the definition */
190 if (!(dic = hTabItemWithKey (iCodehTab,
191 bitVectFirstBit (OP_DEFS
195 if (dic->op != '=' || POINTER_SET (dic))
198 /* we now we know that it has one & only one def & use
199 and the that the definition is an assignment */
200 IC_LEFT (ic) = IC_RIGHT (dic);
202 remiCodeFromeBBlock (ebp, dic);
203 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
206 /*-----------------------------------------------------------------*/
207 /* packRegsForSupport :- reduce some registers for support calls */
208 /*-----------------------------------------------------------------*/
210 packRegsForSupport (iCode * ic, eBBlock * ebp)
213 /* for the left & right operand :- look to see if the
214 left was assigned a true symbol in far space in that
216 if (IS_ITEMP (IC_LEFT (ic)) &&
217 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq) {
218 iCode *dic = findAssignToSym (IC_LEFT (ic), ic);
224 /* found it we need to remove it from the
226 for (sic = dic; sic != ic; sic = sic->next)
227 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
229 IC_LEFT (ic)->operand.symOperand =
230 IC_RIGHT (dic)->operand.symOperand;
231 IC_LEFT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
232 remiCodeFromeBBlock (ebp, dic);
233 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
237 /* do the same for the right operand */
240 IS_ITEMP (IC_RIGHT (ic)) &&
241 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq) {
242 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
248 /* if this is a subtraction & the result
249 is a true symbol in far space then don't pack */
250 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic))) {
252 getSpec (operandType (IC_RESULT (dic)));
253 if (IN_FARSPACE (SPEC_OCLS (etype)))
256 /* found it we need to remove it from the
258 for (sic = dic; sic != ic; sic = sic->next)
259 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
261 IC_RIGHT (ic)->operand.symOperand =
262 IC_RIGHT (dic)->operand.symOperand;
263 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
265 remiCodeFromeBBlock (ebp, dic);
266 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
273 /*-----------------------------------------------------------------*/
274 /* farSpacePackable - returns the packable icode for far variables */
275 /*-----------------------------------------------------------------*/
277 farSpacePackable (iCode * ic)
281 /* go thru till we find a definition for the
282 symbol on the right */
283 for (dic = ic->prev; dic; dic = dic->prev) {
285 /* if the definition is a call then no */
286 if ((dic->op == CALL || dic->op == PCALL) &&
287 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
291 /* if shift by unknown amount then not */
292 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
293 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
296 /* if pointer get and size > 1 */
297 if (POINTER_GET (dic) &&
298 getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) >
301 if (POINTER_SET (dic) &&
302 getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE))
306 /* if any three is a true symbol in far space */
307 if (IC_RESULT (dic) &&
308 IS_TRUE_SYMOP (IC_RESULT (dic)) &&
309 isOperandInFarSpace (IC_RESULT (dic)))
312 if (IC_RIGHT (dic) &&
313 IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
314 isOperandInFarSpace (IC_RIGHT (dic)) &&
315 !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
319 IS_TRUE_SYMOP (IC_LEFT (dic)) &&
320 isOperandInFarSpace (IC_LEFT (dic)) &&
321 !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
324 if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic))) {
325 if ((dic->op == LEFT_OP ||
326 dic->op == RIGHT_OP ||
328 IS_OP_LITERAL (IC_RIGHT (dic))) return NULL;
337 /*-----------------------------------------------------------------*/
338 /* rematStr - returns the rematerialized string for a remat var */
339 /*-----------------------------------------------------------------*/
341 rematStr (symbol * sym)
344 iCode *ic = sym->rematiCode;
348 /* if plus or minus print the right hand side */
349 if (ic->op == '+' || ic->op == '-') {
350 sprintf (s, "0x%04x %c ",
351 (int) operandLitValue (IC_RIGHT (ic)),
354 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
358 /* we reached the end */
359 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
366 /*-----------------------------------------------------------------*/
367 /* isSpiltOnStack - returns true if the spil location is on stack */
368 /*-----------------------------------------------------------------*/
370 isSpiltOnStack (symbol * sym)
381 if (!sym->usl.spillLoc)
384 etype = getSpec (sym->usl.spillLoc->type);
385 if (IN_STACK (etype))
391 /*-----------------------------------------------------------------*/
392 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
393 /*-----------------------------------------------------------------*/
395 spillLRWithPtrReg (symbol * forSym)
398 regs *X, *Z, *X1, *Z1;
401 if (!_G.regAssigned || bitVectIsZero (_G.regAssigned))
404 X = avr_regWithIdx (R26_IDX);
405 X1= avr_regWithIdx (R27_IDX);
406 Z = avr_regWithIdx (R30_IDX);
407 Z1= avr_regWithIdx (R31_IDX);
409 /* for all live ranges */
410 for (lrsym = hTabFirstItem (liveRanges, &k); lrsym;
411 lrsym = hTabNextItem (liveRanges, &k)) {
414 /* if no registers assigned to it or
416 /* if it does not overlap with this then
417 not need to spill it */
419 if (lrsym->isspilt || !lrsym->nRegs ||
420 (lrsym->liveTo < forSym->liveFrom)) continue;
422 /* go thru the registers : if it is either
423 r0 or r1 then spil it */
424 for (j = 0; j < lrsym->nRegs; j++)
425 if (lrsym->regs[j] == X || lrsym->regs[j] == Z ||
426 lrsym->regs[j] == X1 || lrsym->regs[j] == Z1) {
435 /*-----------------------------------------------------------------*/
436 /* allocReg - allocates register of given type */
437 /*-----------------------------------------------------------------*/
439 allocReg (short type)
443 for (i = avr_fReg; i < avr_nRegs; i++) {
445 /* if type is given as 0 then any
446 free register will do */
447 if (!type && regsAVR[i].isFree) {
448 regsAVR[i].isFree = 0;
451 bitVectSetBit (currFunc->regsUsed, i);
455 /* other wise look for specific type
457 if (regsAVR[i].isFree && (regsAVR[i].type & type)) {
458 regsAVR[i].isFree = 0;
461 bitVectSetBit (currFunc->regsUsed, i);
468 /*-----------------------------------------------------------------*/
469 /* allocRegPair - allocates register pair of given */
470 /*-----------------------------------------------------------------*/
472 allocRegPair (short type)
476 for (i = avr_fReg; i < avr_nRegs; i++) {
478 /* look for specific type of register pair */
479 if (regsAVR[i].isFree && (regsAVR[i].type & type)
480 && (regsAVR[i].type & REG_PAIR) && regsAVR[i+1].isFree) {
482 regsAVR[i].isFree = 0;
483 regsAVR[i+1].isFree = 0;
486 bitVectSetBit (currFunc->regsUsed, i);
488 bitVectSetBit (currFunc->regsUsed, i+1);
496 /*-----------------------------------------------------------------*/
497 /* avr_regWithIdx - returns pointer to register wit index number */
498 /*-----------------------------------------------------------------*/
500 avr_regWithIdx (int idx)
504 for (i = 0; i < avr_nRegs; i++)
505 if (regsAVR[i].rIdx == idx)
508 werror (E_INTERNAL_ERROR, __FILE__, __LINE__, "regWithIdx not found");
512 /*-----------------------------------------------------------------*/
513 /* freeReg - frees a register */
514 /*-----------------------------------------------------------------*/
522 /*-----------------------------------------------------------------*/
523 /* nFreeRegs - returns number of free registers */
524 /*-----------------------------------------------------------------*/
531 for (i = avr_fReg; i < avr_nRegs; i++)
532 if (regsAVR[i].isFree && regsAVR[i].type & type)
537 /*-----------------------------------------------------------------*/
538 /* nfreeRegsType - free registers with type */
539 /*-----------------------------------------------------------------*/
541 nfreeRegsType (int type)
544 if (type == REG_PTR) {
545 if ((nfr = nFreeRegs (type)) == 0)
546 return nFreeRegs (REG_GPR);
549 return nFreeRegs (type);
553 /*-----------------------------------------------------------------*/
554 /* allDefsOutOfRange - all definitions are out of a range */
555 /*-----------------------------------------------------------------*/
557 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
564 for (i = 0; i < defs->size; i++) {
567 if (bitVectBitValue (defs, i) &&
568 (ic = hTabItemWithKey (iCodehTab, i)) &&
569 (ic->seq >= fseq && ic->seq <= toseq))
577 /*-----------------------------------------------------------------*/
578 /* computeSpillable - given a point find the spillable live ranges */
579 /*-----------------------------------------------------------------*/
581 computeSpillable (iCode * ic)
585 /* spillable live ranges are those that are live at this
586 point . the following categories need to be subtracted
588 a) - those that are already spilt
589 b) - if being used by this one
590 c) - defined by this one */
592 spillable = bitVectCopy (ic->rlive);
593 spillable = bitVectCplAnd (spillable, _G.spiltSet); /* those already spilt */
594 spillable = bitVectCplAnd (spillable, ic->uses); /* used in this one */
595 bitVectUnSetBit (spillable, ic->defKey);
596 spillable = bitVectIntersect (spillable, _G.regAssigned);
601 /*-----------------------------------------------------------------*/
602 /* noSpilLoc - return true if a variable has no spil location */
603 /*-----------------------------------------------------------------*/
605 noSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
607 return (sym->usl.spillLoc ? 0 : 1);
610 /*-----------------------------------------------------------------*/
611 /* hasSpilLoc - will return 1 if the symbol has spil location */
612 /*-----------------------------------------------------------------*/
614 hasSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
616 return (sym->usl.spillLoc ? 1 : 0);
619 /*-----------------------------------------------------------------*/
620 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location */
621 /* but is not used as a pointer */
622 /*-----------------------------------------------------------------*/
624 hasSpilLocnoUptr (symbol * sym, eBBlock * ebp, iCode * ic)
626 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
629 /*-----------------------------------------------------------------*/
630 /* rematable - will return 1 if the remat flag is set */
631 /*-----------------------------------------------------------------*/
633 rematable (symbol * sym, eBBlock * ebp, iCode * ic)
638 /*-----------------------------------------------------------------*/
639 /* notUsedInBlock - not used in this block */
640 /*-----------------------------------------------------------------*/
642 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode * ic)
644 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
645 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq));
648 /*-----------------------------------------------------------------*/
649 /* notUsedInRemaining - not used or defined in remain of the block */
650 /*-----------------------------------------------------------------*/
652 notUsedInRemaining (symbol * sym, eBBlock * ebp, iCode * ic)
654 return ((usedInRemaining (operandFromSymbol (sym), ic) ? 0 : 1) &&
655 allDefsOutOfRange (sym->defs, ic->seq, ebp->lSeq));
658 /*-----------------------------------------------------------------*/
659 /* allLRs - return true for all */
660 /*-----------------------------------------------------------------*/
662 allLRs (symbol * sym, eBBlock * ebp, iCode * ic)
667 /*-----------------------------------------------------------------*/
668 /* liveRangesWith - applies function to a given set of live range */
669 /*-----------------------------------------------------------------*/
671 liveRangesWith (bitVect * lrs,
672 int (func) (symbol *, eBBlock *, iCode *),
673 eBBlock * ebp, iCode * ic)
678 if (!lrs || !lrs->size)
681 for (i = 1; i < lrs->size; i++) {
683 if (!bitVectBitValue (lrs, i))
686 /* if we don't find it in the live range
687 hash table we are in serious trouble */
688 if (!(sym = hTabItemWithKey (liveRanges, i))) {
689 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
690 "liveRangesWith could not find liveRange");
694 if (func (sym, ebp, ic)
695 && bitVectBitValue (_G.regAssigned,
696 sym->key)) addSetHead (&rset, sym);
703 /*-----------------------------------------------------------------*/
704 /* leastUsedLR - given a set determines which is the least used */
705 /*-----------------------------------------------------------------*/
707 leastUsedLR (set * sset)
709 symbol *sym = NULL, *lsym = NULL;
711 sym = lsym = setFirstItem (sset);
716 for (; lsym; lsym = setNextItem (sset)) {
718 /* if usage is the same then prefer
719 the spill the smaller of the two */
720 if (lsym->used == sym->used)
721 if (getSize (lsym->type) < getSize (sym->type))
725 if (lsym->used < sym->used)
730 setToNull ((void **) &sset);
735 /*-----------------------------------------------------------------*/
736 /* noOverLap - will iterate through the list looking for over lap */
737 /*-----------------------------------------------------------------*/
739 noOverLap (set * itmpStack, symbol * fsym)
744 for (sym = setFirstItem (itmpStack); sym;
745 sym = setNextItem (itmpStack)) {
746 if (sym->liveTo > fsym->liveFrom)
754 /*-----------------------------------------------------------------*/
755 /* isFree - will return 1 if the a free spil location is found */
756 /*-----------------------------------------------------------------*/
761 V_ARG (symbol **, sloc);
762 V_ARG (symbol *, fsym);
764 /* if already found */
768 /* if it is free && and the itmp assigned to
769 this does not have any overlapping live ranges
770 with the one currently being assigned and
771 the size can be accomodated */
773 noOverLap (sym->usl.itmpStack, fsym) &&
774 getSize (sym->type) >= getSize (fsym->type)) {
782 /*-----------------------------------------------------------------*/
783 /* createStackSpil - create a location on the stack to spil */
784 /*-----------------------------------------------------------------*/
786 createStackSpil (symbol * sym)
789 int useXstack, model, noOverlay;
794 /* first go try and find a free one that is already
795 existing on the stack */
796 if (applyToSet (_G.stackSpil, isFree, &sloc, sym)) {
797 /* found a free one : just update & return */
798 sym->usl.spillLoc = sloc;
801 addSetHead (&sloc->usl.itmpStack, sym);
805 /* could not then have to create one , this is the hard part
806 we need to allocate this on the stack : this is really a
807 hack!! but cannot think of anything better at this time */
809 if (sprintf (slocBuffer, "sloc%d", _G.slocNum++) >=
810 sizeof (slocBuffer)) {
812 "***Internal error: slocBuffer overflowed: %s:%d\n",
817 sloc = newiTemp (slocBuffer);
819 /* set the type to the spilling symbol */
820 sloc->type = copyLinkChain (sym->type);
821 sloc->etype = getSpec (sloc->type);
822 SPEC_SCLS (sloc->etype) = S_AUTO;
823 SPEC_EXTR (sloc->etype) = 0;
825 /* we don't allow it to be allocated`
826 onto the external stack since : so we
827 temporarily turn it off ; we also
828 turn off memory model to prevent
829 the spil from going to the external storage
830 and turn off overlaying
833 useXstack = options.useXstack;
834 model = options.model;
835 noOverlay = options.noOverlay;
836 stackAuto = options.stackAuto;
837 options.noOverlay = 1;
838 options.model = options.useXstack = 0;
842 options.useXstack = useXstack;
843 options.model = model;
844 options.noOverlay = noOverlay;
845 options.stackAuto = stackAuto;
846 sloc->isref = 1; /* to prevent compiler warning */
848 /* if it is on the stack then update the stack */
849 if (IN_STACK (sloc->etype)) {
850 currFunc->stack += getSize (sloc->type);
851 _G.stackExtend += getSize (sloc->type);
854 _G.dataExtend += getSize (sloc->type);
856 /* add it to the _G.stackSpil set */
857 addSetHead (&_G.stackSpil, sloc);
858 sym->usl.spillLoc = sloc;
861 /* add it to the set of itempStack set
862 of the spill location */
863 addSetHead (&sloc->usl.itmpStack, sym);
867 /*-----------------------------------------------------------------*/
868 /* spillThis - spils a specific operand */
869 /*-----------------------------------------------------------------*/
871 spillThis (symbol * sym)
874 /* if this is rematerializable or has a spillLocation
875 we are okay, else we need to create a spillLocation
877 if (!(sym->remat || sym->usl.spillLoc))
878 createStackSpil (sym);
881 /* mark it has spilt & put it in the spilt set */
883 _G.spiltSet = bitVectSetBit (_G.spiltSet, sym->key);
885 bitVectUnSetBit (_G.regAssigned, sym->key);
887 for (i = 0; i < sym->nRegs; i++)
890 freeReg (sym->regs[i]);
894 if (sym->usl.spillLoc && !sym->remat)
895 sym->usl.spillLoc->allocreq = 1;
899 /*-----------------------------------------------------------------*/
900 /* selectSpil - select a iTemp to spil : rather a simple procedure */
901 /*-----------------------------------------------------------------*/
903 selectSpil (iCode * ic, eBBlock * ebp, symbol * forSym)
905 bitVect *lrcs = NULL;
909 /* get the spillable live ranges */
910 lrcs = computeSpillable (ic);
912 /* get all live ranges that are rematerizable */
913 if ((selectS = liveRangesWith (lrcs, rematable, ebp, ic))) {
915 /* return the least used of these */
916 return leastUsedLR (selectS);
919 /* if the symbol is local to the block then */
920 if (forSym->liveTo < ebp->lSeq) {
922 /* check if there are any live ranges allocated
923 to registers that are not used in this block */
926 liveRangesWith (lrcs, notUsedInBlock, ebp, ic))) {
927 sym = leastUsedLR (selectS);
928 /* if this is not rematerializable */
936 /* check if there are any live ranges that not
937 used in the remainder of the block */
940 liveRangesWith (lrcs, notUsedInRemaining, ebp, ic))) {
941 sym = leastUsedLR (selectS);
952 /* find live ranges with spillocation && not used as pointers */
953 if ((selectS = liveRangesWith (lrcs, hasSpilLocnoUptr, ebp, ic))) {
955 sym = leastUsedLR (selectS);
956 /* mark this as allocation required */
957 sym->usl.spillLoc->allocreq = 1;
961 /* find live ranges with spillocation */
962 if ((selectS = liveRangesWith (lrcs, hasSpilLoc, ebp, ic))) {
964 sym = leastUsedLR (selectS);
965 sym->usl.spillLoc->allocreq = 1;
969 /* couldn't find then we need to create a spil
970 location on the stack , for which one? the least
972 if ((selectS = liveRangesWith (lrcs, noSpilLoc, ebp, ic))) {
974 /* return a created spil location */
975 sym = createStackSpil (leastUsedLR (selectS));
976 sym->usl.spillLoc->allocreq = 1;
980 /* this is an extreme situation we will spill
981 this one : happens very rarely but it does happen */
987 /*-----------------------------------------------------------------*/
988 /* spilSomething - spil some variable & mark registers as free */
989 /*-----------------------------------------------------------------*/
991 spilSomething (iCode * ic, eBBlock * ebp, symbol * forSym)
996 /* get something we can spil */
997 ssym = selectSpil (ic, ebp, forSym);
999 /* mark it as spilt */
1001 _G.spiltSet = bitVectSetBit (_G.spiltSet, ssym->key);
1003 /* mark it as not register assigned &
1004 take it away from the set */
1005 bitVectUnSetBit (_G.regAssigned, ssym->key);
1007 /* mark the registers as free */
1008 for (i = 0; i < ssym->nRegs; i++)
1010 freeReg (ssym->regs[i]);
1012 /* if this was a block level spil then insert push & pop
1013 at the start & end of block respectively */
1014 if (ssym->blockSpil) {
1015 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
1016 /* add push to the start of the block */
1017 addiCodeToeBBlock (ebp, nic, (ebp->sch->op == LABEL ?
1018 ebp->sch->next : ebp->sch));
1019 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
1020 /* add pop to the end of the block */
1021 addiCodeToeBBlock (ebp, nic, NULL);
1024 /* if spilt because not used in the remainder of the
1025 block then add a push before this instruction and
1026 a pop at the end of the block */
1027 if (ssym->remainSpil) {
1029 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
1030 /* add push just before this instruction */
1031 addiCodeToeBBlock (ebp, nic, ic);
1033 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
1034 /* add pop to the end of the block */
1035 addiCodeToeBBlock (ebp, nic, NULL);
1044 /*-----------------------------------------------------------------*/
1045 /* getRegPtr - will try for PTR if not a GPR type if not spil */
1046 /*-----------------------------------------------------------------*/
1048 getRegPtr (iCode * ic, eBBlock * ebp, symbol * sym)
1053 /* try for a ptr type */
1054 if ((reg = allocReg (REG_PTR|REG_PAIR)))
1057 /* try for gpr type / pair */
1058 if ((reg = allocReg (REG_GPR|REG_PAIR)))
1061 /* try for gpr type */
1062 if ((reg = allocReg (REG_GPR)))
1065 /* we have to spil */
1066 if (!spilSomething (ic, ebp, sym))
1069 /* this looks like an infinite loop but
1070 in reality selectSpil will abort */
1074 /*-----------------------------------------------------------------*/
1075 /* getRegScr - will try for SCR if not a GPR type if not spil */
1076 /*-----------------------------------------------------------------*/
1078 getRegScr (iCode * ic, eBBlock * ebp, symbol * sym)
1084 /* try for a scratch non-pair */
1085 if ((reg = allocReg (REG_SCR)))
1088 if ((reg = allocReg (REG_GPR)))
1091 /* we have to spil */
1092 if (!spilSomething (ic, ebp, sym))
1095 /* this looks like an infinite loop but
1096 in really selectSpil will abort */
1100 /*-----------------------------------------------------------------*/
1101 /* getRegGpr - will try for GPR if not spil */
1102 /*-----------------------------------------------------------------*/
1104 getRegGpr (iCode * ic, eBBlock * ebp, symbol * sym )
1109 /* try for gpr type */
1110 if ((reg = allocReg (REG_GPR)))
1114 if ((reg = allocReg (REG_PTR)))
1117 /* we have to spil */
1118 if (!spilSomething (ic, ebp, sym))
1121 /* this looks like an infinite loop but
1122 in reality selectSpil will abort */
1126 /*-----------------------------------------------------------------*/
1127 /* symHasReg - symbol has a given register */
1128 /*-----------------------------------------------------------------*/
1130 symHasReg (symbol * sym, regs * reg)
1134 for (i = 0; i < sym->nRegs; i++)
1135 if (sym->regs[i] == reg)
1141 /*-----------------------------------------------------------------*/
1142 /* deassignLRs - check the live to and if they have registers & are */
1143 /* not spilt then free up the registers */
1144 /*-----------------------------------------------------------------*/
1146 deassignLRs (iCode * ic, eBBlock * ebp)
1152 for (sym = hTabFirstItem (liveRanges, &k); sym;
1153 sym = hTabNextItem (liveRanges, &k)) {
1155 symbol *psym = NULL;
1156 /* if it does not end here */
1157 if (sym->liveTo > ic->seq)
1160 /* if it was spilt on stack then we can
1161 mark the stack spil location as free */
1163 if (sym->stackSpil) {
1164 sym->usl.spillLoc->isFree = 1;
1170 if (!bitVectBitValue (_G.regAssigned, sym->key))
1173 /* special case check if this is an IFX &
1174 the privious one was a pop and the
1175 previous one was not spilt then keep track
1177 if (ic->op == IFX && ic->prev &&
1178 ic->prev->op == IPOP &&
1179 !ic->prev->parmPush &&
1180 !OP_SYMBOL (IC_LEFT (ic->prev))->isspilt)
1181 psym = OP_SYMBOL (IC_LEFT (ic->prev));
1186 bitVectUnSetBit (_G.regAssigned, sym->key);
1188 /* if the result of this one needs registers
1189 and does not have it then assign it right
1191 if (IC_RESULT (ic) && !(SKIP_IC2 (ic) || /* not a special icode */
1192 ic->op == JUMPTABLE ||
1197 POINTER_SET (ic)) &&
1198 (result = OP_SYMBOL (IC_RESULT (ic))) && /* has a result */
1199 result->liveTo > ic->seq && /* and will live beyond this */
1200 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
1201 result->regType == sym->regType && /* same register types */
1202 result->nRegs && /* which needs registers */
1203 !result->isspilt && /* and does not already have them */
1205 !bitVectBitValue (_G.regAssigned, result->key) &&
1206 /* the number of free regs + number of regs in this LR
1207 can accomodate the what result Needs */
1208 ((nfreeRegsType (result->regType) + sym->nRegs) >= result->nRegs)) {
1210 for (i = 0; i < result->nRegs; i++) {
1212 result->regs[i] = sym->regs[i];
1213 else if (result->regType == REG_SCR)
1214 result->regs[i] = getRegScr (ic, ebp, result);
1216 result->regs[i] = getRegGpr (ic, ebp, result);
1218 _G.regAssigned = bitVectSetBit (_G.regAssigned, result->key);
1222 /* free the remaining */
1223 for (; i < sym->nRegs; i++) {
1225 if (!symHasReg (psym, sym->regs[i]))
1226 freeReg (sym->regs[i]);
1228 else freeReg (sym->regs[i]);
1235 /*-----------------------------------------------------------------*/
1236 /* reassignLR - reassign this to registers */
1237 /*-----------------------------------------------------------------*/
1239 reassignLR (operand * op)
1241 symbol *sym = OP_SYMBOL (op);
1244 /* not spilt any more */
1245 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
1246 bitVectUnSetBit (_G.spiltSet, sym->key);
1248 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1252 for (i = 0; i < sym->nRegs; i++)
1253 sym->regs[i]->isFree = 0;
1256 /*-----------------------------------------------------------------*/
1257 /* willCauseSpill - determines if allocating will cause a spill */
1258 /*-----------------------------------------------------------------*/
1260 willCauseSpill (int nr, int rt)
1262 /* first check if there are any avlb registers
1263 of te type required */
1264 if (rt == REG_PTR) {
1265 /* special case for pointer type
1266 if pointer type not avlb then
1267 check for type gpr */
1268 if (nFreeRegs (rt) >= nr)
1270 if (nFreeRegs (REG_GPR) >= nr)
1274 if (avr_ptrRegReq) {
1275 if (nFreeRegs (rt) >= nr)
1279 if (nFreeRegs (REG_PTR) + nFreeRegs (REG_GPR) >= nr)
1284 /* it will cause a spil */
1288 /*-----------------------------------------------------------------*/
1289 /* positionRegs - the allocator can allocate same registers to res- */
1290 /* ult and operand, if this happens make sure they are in the same */
1291 /* position as the operand otherwise chaos results */
1292 /*-----------------------------------------------------------------*/
1294 positionRegs (symbol * result, symbol * opsym, int lineno)
1296 int count = min (result->nRegs, opsym->nRegs);
1297 int i, j = 0, shared = 0;
1299 /* if the result has been spilt then cannot share */
1304 /* first make sure that they actually share */
1305 for (i = 0; i < count; i++) {
1306 for (j = 0; j < count; j++) {
1307 if (result->regs[i] == opsym->regs[j] && i != j) {
1315 regs *tmp = result->regs[i];
1316 result->regs[i] = result->regs[j];
1317 result->regs[j] = tmp;
1322 /*-----------------------------------------------------------------*/
1323 /* needsPair - heuristic to determine if a pair would be good */
1324 /*-----------------------------------------------------------------*/
1325 static int needsPair (iCode *ic)
1327 symbol *sym = OP_SYMBOL(IC_RESULT(ic));
1328 bitVect *uses_defs =
1329 bitVectUnion(OP_USES (IC_RESULT(ic)),OP_DEFS(IC_RESULT(ic)));
1331 /* if size is less than 2 then NO */
1332 if (sym->nRegs < 2) return 0;
1333 /* if type Pointer then YES */
1334 if (IS_PTR(sym->type)) return 1;
1336 /* go thru the usages of this operand if used with
1337 a constant then yes */
1338 while (!bitVectIsZero(uses_defs)) {
1339 int ikey = bitVectFirstBit(uses_defs);
1340 iCode *uic = hTabItemWithKey(iCodehTab,ikey);
1341 sym_link *otype = NULL;
1342 bitVectUnSetBit(uses_defs,ikey);
1344 otype = (IC_RIGHT(uic) ? operandType(IC_RIGHT(uic)) : NULL);
1345 if (otype && IS_LITERAL(otype)) return 1;
1350 /*-----------------------------------------------------------------*/
1351 /* serialRegAssign - serially allocate registers to the variables */
1352 /*-----------------------------------------------------------------*/
1354 serialRegAssign (eBBlock ** ebbs, int count)
1358 /* for all blocks */
1359 for (i = 0; i < count; i++) {
1363 if (ebbs[i]->noPath &&
1364 (ebbs[i]->entryLabel != entryLabel &&
1365 ebbs[i]->entryLabel != returnLabel))
1368 /* of all instructions do */
1369 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1371 /* if this is an ipop that means some live
1372 range will have to be assigned again */
1374 reassignLR (IC_LEFT (ic));
1376 /* if result is present && is a true symbol */
1377 if (IC_RESULT (ic) && ic->op != IFX &&
1378 IS_TRUE_SYMOP (IC_RESULT (ic)))
1379 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
1381 /* take away registers from live
1382 ranges that end at this instruction */
1383 deassignLRs (ic, ebbs[i]);
1385 /* some don't need registers */
1386 if (SKIP_IC2 (ic) ||
1387 ic->op == JUMPTABLE ||
1391 (IC_RESULT (ic) && POINTER_SET (ic))) continue;
1393 /* now we need to allocate registers
1394 only for the result */
1395 if (IC_RESULT (ic)) {
1396 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1401 /* if it does not need or is spilt
1402 or is already assigned to registers
1403 or will not live beyond this instructions */
1406 bitVectBitValue (_G.regAssigned, sym->key)
1407 || sym->liveTo <= ic->seq)
1410 /* if some liverange has been spilt at the block level
1411 and this one live beyond this block then spil this
1414 && sym->liveTo > ebbs[i]->lSeq) {
1418 /* if trying to allocate this will cause
1419 a spill and there is nothing to spill
1420 or this one is rematerializable then
1423 willCauseSpill (sym->nRegs,
1425 spillable = computeSpillable (ic);
1426 if (sym->remat || (willCS && bitVectIsZero (spillable))) {
1431 /* if it has a spillocation & is used less than
1432 all other live ranges then spill this */
1434 if (sym->usl.spillLoc) {
1435 symbol *leastUsed = leastUsedLR (liveRangesWith (spillable,
1436 allLRs, ebbs[i], ic));
1437 if (leastUsed && leastUsed->used > sym->used) {
1442 /* if none of the liveRanges have a spillLocation then better
1443 to spill this one than anything else already assigned to registers */
1444 if (liveRangesWith(spillable,noSpilLoc,ebbs[i],ic)) {
1451 /* we assign registers to it */
1452 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1453 if (needsPair(ic)) {
1456 if (sym->regType == REG_PTR) regtype = REG_PTR;
1457 else if (sym->regType == REG_SCR) regtype = REG_SCR;
1458 else regtype = REG_GPR;
1459 preg = allocRegPair(regtype);
1461 sym->regs[j++] = preg;
1462 sym->regs[j++] = ®sAVR[preg->rIdx+1];
1465 for (; j < sym->nRegs; j++) {
1466 if (sym->regType == REG_PTR)
1467 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1468 else if (sym->regType == REG_SCR)
1469 sym->regs[j] = getRegScr (ic, ebbs[i], sym);
1471 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1472 /* if the allocation falied which means
1473 this was spilt then break */
1474 if (!sym->regs[j]) break;
1477 /* if it shares registers with operands make sure
1478 that they are in the same position */
1479 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1480 OP_SYMBOL (IC_LEFT (ic))->nRegs
1482 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1483 OP_SYMBOL (IC_LEFT (ic)), ic->lineno);
1484 /* do the same for the right operand */
1485 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))
1486 && OP_SYMBOL (IC_RIGHT (ic))->nRegs)
1487 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1488 OP_SYMBOL (IC_RIGHT (ic)), ic->lineno);
1495 /*-----------------------------------------------------------------*/
1496 /* rUmaskForOp :- returns register mask for an operand */
1497 /*-----------------------------------------------------------------*/
1499 rUmaskForOp (operand * op)
1505 /* only temporaries are assigned registers */
1509 sym = OP_SYMBOL (op);
1511 /* if spilt or no registers assigned to it
1513 if (sym->isspilt || !sym->nRegs)
1516 rumask = newBitVect (avr_nRegs);
1518 for (j = 0; j < sym->nRegs; j++) {
1519 rumask = bitVectSetBit (rumask, sym->regs[j]->rIdx);
1525 /*-----------------------------------------------------------------*/
1526 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1527 /*-----------------------------------------------------------------*/
1529 regsUsedIniCode (iCode * ic)
1531 bitVect *rmask = newBitVect (avr_nRegs);
1533 /* do the special cases first */
1534 if (ic->op == IFX) {
1535 rmask = bitVectUnion (rmask, rUmaskForOp (IC_COND (ic)));
1539 /* for the jumptable */
1540 if (ic->op == JUMPTABLE) {
1541 rmask = bitVectUnion (rmask, rUmaskForOp (IC_JTCOND (ic)));
1546 /* of all other cases */
1548 rmask = bitVectUnion (rmask, rUmaskForOp (IC_LEFT (ic)));
1552 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RIGHT (ic)));
1555 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RESULT (ic)));
1561 /*-----------------------------------------------------------------*/
1562 /* createRegMask - for each instruction will determine the regsUsed */
1563 /*-----------------------------------------------------------------*/
1565 createRegMask (eBBlock ** ebbs, int count)
1569 /* for all blocks */
1570 for (i = 0; i < count; i++) {
1573 if (ebbs[i]->noPath &&
1574 (ebbs[i]->entryLabel != entryLabel &&
1575 ebbs[i]->entryLabel != returnLabel))
1578 /* for all instructions */
1579 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1583 if (SKIP_IC2 (ic) || !ic->rlive)
1586 /* first mark the registers used in this
1588 ic->rUsed = regsUsedIniCode (ic);
1589 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1591 /* now create the register mask for those
1592 registers that are in use : this is a
1593 super set of ic->rUsed */
1594 ic->rMask = newBitVect (avr_nRegs + 1);
1596 /* for all live Ranges alive at this point */
1597 for (j = 1; j < ic->rlive->size; j++) {
1601 /* if not alive then continue */
1602 if (!bitVectBitValue (ic->rlive, j))
1605 /* find the live range we are interested in */
1606 if (!(sym = hTabItemWithKey (liveRanges, j))) {
1607 werror (E_INTERNAL_ERROR, __FILE__,
1609 "createRegMask cannot find live range");
1613 /* if no register assigned to it */
1614 if (!sym->nRegs || sym->isspilt)
1617 /* for all the registers allocated to it */
1618 for (k = 0; k < sym->nRegs; k++) {
1620 int rIdx = sym->regs[k]->rIdx;
1621 ic->rMask = bitVectSetBit (ic-> rMask,rIdx);
1622 /* special case for X & Z registers */
1623 if (rIdx == R26_IDX || rIdx == R27_IDX)
1624 ic->rMask = bitVectSetBit (ic->rMask, X_IDX);
1625 if (rIdx == R30_IDX || rIdx == R31_IDX)
1626 ic->rMask = bitVectSetBit (ic->rMask, Z_IDX);
1635 /*-----------------------------------------------------------------*/
1636 /* regTypeNum - computes the type & number of registers required */
1637 /*-----------------------------------------------------------------*/
1645 /* for each live range do */
1646 for (sym = hTabFirstItem (liveRanges, &k); sym;
1647 sym = hTabNextItem (liveRanges, &k)) {
1649 /* if used zero times then no registers needed */
1650 if ((sym->liveTo - sym->liveFrom) == 0)
1654 /* if the live range is a temporary */
1657 /* if the type is marked as a conditional */
1658 if (sym->regType == REG_CND)
1661 /* if used in return only then we don't
1663 if (sym->ruonly || sym->accuse) {
1664 if (IS_AGGREGATE (sym->type) || sym->isptr)
1666 aggrToPtr (sym->type, FALSE);
1670 /* if the symbol has only one definition &
1671 that definition is a get_pointer and the
1672 pointer we are getting is rematerializable and
1675 if (bitVectnBitsOn (sym->defs) == 1 &&
1676 (ic = hTabItemWithKey (iCodehTab, bitVectFirstBit (sym-> defs)))
1677 && POINTER_GET (ic) && !IS_BITVAR (sym->etype)) {
1679 /* if in data space or idata space then try to
1680 allocate pointer register */
1684 /* if not then we require registers */
1686 ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1687 getSize (sym->type =
1688 aggrToPtr (sym->type,
1689 FALSE)) : getSize (sym->
1692 if (sym->nRegs > 4) {
1694 "allocated more than 4 or 0 registers for type ");
1695 printTypeChain (sym->type, stderr);
1696 fprintf (stderr, "\n");
1699 /* determine the type of register required */
1700 if (sym->nRegs == 2 && /* size is two */
1701 IS_PTR (sym->type) && /* is a pointer */
1702 sym->uptr) { /* has pointer usage i.e. get/set pointer */
1703 sym->regType = REG_PTR;
1707 /* live accross a function call then gpr else scratch */
1708 if (sym->isLiveFcall)
1709 sym->regType = REG_GPR;
1711 sym->regType = REG_SCR;
1715 /* for the first run we don't provide */
1716 /* registers for true symbols we will */
1717 /* see how things go */
1723 /*-----------------------------------------------------------------*/
1724 /* deallocStackSpil - this will set the stack pointer back */
1725 /*-----------------------------------------------------------------*/
1727 DEFSETFUNC (deallocStackSpil)
1735 /*-----------------------------------------------------------------*/
1736 /* packRegsForAssign - register reduction for assignment */
1737 /*-----------------------------------------------------------------*/
1739 packRegsForAssign (iCode * ic, eBBlock * ebp)
1743 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1744 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1745 OP_LIVETO (IC_RIGHT (ic)) > ic->seq) {
1749 /* find the definition of iTempNN scanning backwards if we find a
1750 a use of the true symbol in before we find the definition then
1752 for (dic = ic->prev; dic; dic = dic->prev) {
1754 /* if there is a function call and this is
1755 a parameter & not my parameter then don't pack it */
1756 if ((dic->op == CALL || dic->op == PCALL) &&
1757 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1758 !OP_SYMBOL (IC_RESULT (ic))->ismyparm)) {
1766 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1767 IS_OP_VOLATILE (IC_RESULT (dic))) {
1772 if (IS_SYMOP (IC_RESULT (dic)) &&
1773 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1774 if (POINTER_SET (dic))
1780 if (IS_SYMOP (IC_RIGHT (dic)) &&
1781 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1782 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key)) {
1787 if (IS_SYMOP (IC_LEFT (dic)) &&
1788 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1789 IC_LEFT (dic)->key == IC_RIGHT (ic)->key)) {
1794 if (POINTER_SET (dic) &&
1795 IC_RESULT (dic)->key == IC_RESULT (ic)->key) {
1802 return 0; /* did not find */
1804 /* if the result is on stack or iaccess then it must be
1805 the same atleast one of the operands */
1806 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1807 OP_SYMBOL (IC_RESULT (ic))->iaccess) {
1809 /* the operation has only one symbol
1810 operator then we can pack */
1811 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1812 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1815 if (!((IC_LEFT (dic) &&
1816 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1818 IC_RESULT (ic)->key == IC_RIGHT (dic)->key))) return 0;
1821 /* if in far space & tru symbol then don't */
1822 if ((IS_TRUE_SYMOP (IC_RESULT (ic)))
1823 && isOperandInFarSpace (IC_RESULT (ic))) return 0;
1824 /* found the definition */
1825 /* replace the result with the result of */
1826 /* this assignment and remove this assignment */
1827 IC_RESULT (dic) = IC_RESULT (ic);
1829 if (IS_ITEMP (IC_RESULT (dic))
1830 && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq) {
1831 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1833 /* delete from liverange table also
1834 delete from all the points inbetween and the new
1836 for (sic = dic; sic != ic; sic = sic->next) {
1837 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1838 if (IS_ITEMP (IC_RESULT (dic)))
1839 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1842 remiCodeFromeBBlock (ebp, ic);
1843 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1848 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1851 /*-----------------------------------------------------------------*/
1852 /* packRegsForOneuse : - will reduce some registers for single Use */
1853 /*-----------------------------------------------------------------*/
1855 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1860 /* if returning a literal then do nothing */
1865 if (ic->op != RETURN)
1868 /* this routine will mark the a symbol as used in one
1869 instruction use only && if the defintion is local
1870 (ie. within the basic block) && has only one definition &&
1871 that definiion is either a return value from a
1872 function or does not contain any variables in
1874 uses = bitVectCopy (OP_USES (op));
1875 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1876 if (!bitVectIsZero (uses)) /* has other uses */
1879 /* if it has only one defintion */
1880 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1881 return NULL; /* has more than one definition */
1883 /* get the that definition */
1885 hTabItemWithKey (iCodehTab,
1886 bitVectFirstBit (OP_DEFS (op))))) return NULL;
1888 /* found the definition now check if it is local */
1889 if (dic->seq < ebp->fSeq || dic->seq > ebp->lSeq)
1890 return NULL; /* non-local */
1892 /* now check if it is the return from
1894 if (dic->op == CALL || dic->op == PCALL) {
1895 if (ic->op != SEND && ic->op != RETURN) {
1896 OP_SYMBOL (op)->ruonly = 1;
1903 /* otherwise check that the definition does
1904 not contain any symbols in far space */
1905 if (IS_OP_RUONLY (IC_LEFT (ic)) || IS_OP_RUONLY (IC_RIGHT (ic))) {
1909 /* if pointer set then make sure the pointer
1911 if (POINTER_SET (dic) &&
1912 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1915 if (POINTER_GET (dic) &&
1916 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1921 /* also make sure the intervenening instructions
1922 don't have any thing in far space */
1923 for (dic = dic->next; dic && dic != ic; dic = dic->next) {
1925 /* if there is an intervening function call then no */
1926 if (dic->op == CALL || dic->op == PCALL)
1928 /* if pointer set then make sure the pointer
1930 if (POINTER_SET (dic) &&
1931 !IS_DATA_PTR (aggrToPtr
1932 (operandType (IC_RESULT (dic)),
1933 FALSE))) return NULL;
1935 if (POINTER_GET (dic) &&
1936 !IS_DATA_PTR (aggrToPtr
1937 (operandType (IC_LEFT (dic)),
1938 FALSE))) return NULL;
1940 /* if address of & the result is remat the okay */
1941 if (dic->op == ADDRESS_OF &&
1942 OP_SYMBOL (IC_RESULT (dic))->remat) continue;
1944 /* if operand has size of three or more & this
1945 operation is a '*','/' or '%' then 'b' may
1947 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1948 getSize (operandType (op)) >= 3)
1951 /* if left or right or result is in far space */
1952 if (IS_OP_RUONLY (IC_LEFT (dic)) ||
1953 IS_OP_RUONLY (IC_RIGHT (dic)) ||
1954 IS_OP_RUONLY (IC_RESULT (dic))) {
1959 OP_SYMBOL (op)->ruonly = 1;
1964 /*-----------------------------------------------------------------*/
1965 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1966 /*-----------------------------------------------------------------*/
1968 isBitwiseOptimizable (iCode * ic)
1970 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
1971 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
1973 /* bitwise operations are considered optimizable
1974 under the following conditions (Jean-Louis VERN)
1986 if (IS_LITERAL (rtype) ||
1987 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
1993 /*-----------------------------------------------------------------*/
1994 /* packRegisters - does some transformations to reduce register */
1996 /*-----------------------------------------------------------------*/
1998 packRegisters (eBBlock * ebp)
2007 /* look for assignments of the form */
2008 /* iTempNN = TRueSym (someoperation) SomeOperand */
2010 /* TrueSym := iTempNN:1 */
2011 for (ic = ebp->sch; ic; ic = ic->next) {
2014 /* find assignment of the form TrueSym := iTempNN:1 */
2015 if (ic->op == '=' && !POINTER_SET (ic))
2016 change += packRegsForAssign (ic, ebp);
2023 for (ic = ebp->sch; ic; ic = ic->next) {
2025 /* if this is an itemp & result of a address of a true sym
2026 then mark this as rematerialisable */
2027 if (ic->op == ADDRESS_OF &&
2028 IS_ITEMP (IC_RESULT (ic)) &&
2029 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2030 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2031 !OP_SYMBOL (IC_LEFT (ic))->onStack) {
2033 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2034 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2035 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2039 /* if straight assignment then carry remat flag if
2040 this is the only definition */
2041 if (ic->op == '=' &&
2042 !POINTER_SET (ic) &&
2043 IS_SYMOP (IC_RIGHT (ic)) &&
2044 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2045 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1) {
2047 OP_SYMBOL (IC_RESULT (ic))->remat =
2048 OP_SYMBOL (IC_RIGHT (ic))->remat;
2049 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2050 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2053 /* if this is a +/- operation with a rematerizable
2054 then mark this as rematerializable as well only
2055 if the literal value is within the range -255 and + 255
2056 the assembler cannot handle it other wise */
2057 if ((ic->op == '+' || ic->op == '-') &&
2058 (IS_SYMOP (IC_LEFT (ic)) &&
2059 IS_ITEMP (IC_RESULT (ic)) &&
2060 OP_SYMBOL (IC_LEFT (ic))->remat &&
2061 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2062 IS_OP_LITERAL (IC_RIGHT (ic)))) {
2064 int i = (int) operandLitValue (IC_RIGHT (ic));
2065 if (i < 255 && i > -255) {
2066 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2067 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2068 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc =
2073 /* mark the pointer usages */
2074 if (POINTER_SET (ic))
2075 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2077 if (POINTER_GET (ic)) {
2078 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2079 if (OP_SYMBOL (IC_LEFT(ic))->remat)
2080 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2083 /* if the condition of an if instruction
2084 is defined in the previous instruction then
2085 mark the itemp as a conditional */
2086 if ((IS_CONDITIONAL (ic) ||
2087 ((ic->op == BITWISEAND ||
2090 isBitwiseOptimizable (ic))) &&
2091 ic->next && ic->next->op == IFX &&
2092 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2093 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq) {
2095 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2099 /* some cases the redundant moves can
2100 can be eliminated for return statements */
2101 if ((ic->op == RETURN || ic->op == SEND))
2102 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2104 /* if this is cast for intergral promotion then
2105 check if only use of the definition of the
2106 operand being casted/ if yes then replace
2107 the result of that arithmetic operation with
2108 this result and get rid of the cast */
2109 if (ic->op == CAST) {
2110 sym_link *fromType = operandType (IC_RIGHT (ic));
2111 sym_link *toType = operandType (IC_LEFT (ic));
2113 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2114 getSize (fromType) != getSize (toType) &&
2115 SPEC_USIGN (fromType) == SPEC_USIGN (toType)) {
2118 packRegsForOneuse (ic, IC_RIGHT (ic),
2121 if (IS_ARITHMETIC_OP (dic)) {
2124 remiCodeFromeBBlock (ebp, ic);
2125 hTabDeleteItem (&iCodehTab,
2132 OP_SYMBOL (IC_RIGHT (ic))->
2138 /* if the type from and type to are the same
2139 then if this is the only use then packit */
2140 if (compareType (operandType (IC_RIGHT (ic)),
2141 operandType (IC_LEFT (ic))) ==
2144 packRegsForOneuse (ic,
2150 remiCodeFromeBBlock (ebp, ic);
2151 hTabDeleteItem (&iCodehTab,
2163 /*-----------------------------------------------------------------*/
2164 /* preAssignParms - we have a leaf function preassign registers */
2165 /*-----------------------------------------------------------------*/
2167 preAssignParms (iCode * ic)
2170 /* look for receives and assign registers
2171 to the result of the receives */
2173 /* if it is a receive */
2174 if (ic->op == RECEIVE) {
2175 symbol *r = OP_SYMBOL (IC_RESULT (ic));
2176 int size = getSize (r->type);
2177 if (r->regType == REG_GPR || r->regType == REG_SCR) {
2180 r->regs[j++] = ®sAVR[i++];
2181 regsAVR[i - 1].isFree = 0;
2183 /* put in the regassigned vector */
2185 bitVectSetBit (_G.regAssigned,
2189 /* not a GPR then we should mark as free */
2191 regsAVR[i++].isFree = 1;
2197 /* mark anything remaining as free */
2198 while (i <= R23_IDX)
2199 regsAVR[i++].isFree = 1;
2202 /*-----------------------------------------------------------------*/
2203 /* setdefaultRegs - do setup stuff for register allocation */
2204 /*-----------------------------------------------------------------*/
2206 setDefaultRegs (eBBlock ** ebbs, int count)
2210 /* if no pointer registers required in this function
2211 then mark r26-27 & r30-r31 as GPR & free */
2212 regsAVR[R26_IDX].isFree =
2213 regsAVR[R27_IDX].isFree =
2214 regsAVR[R30_IDX].isFree = regsAVR[R31_IDX].isFree = 1;
2216 if (!avr_ptrRegReq) {
2217 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_GPR;
2218 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_GPR;
2219 regsAVR[R28_IDX].type = (regsAVR[R28_IDX].type & ~REG_MASK) | REG_GPR;
2220 regsAVR[R29_IDX].type = (regsAVR[R29_IDX].type & ~REG_MASK) | REG_GPR;
2223 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_PTR;
2224 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_PTR;
2225 regsAVR[R30_IDX].type = (regsAVR[R30_IDX].type & ~REG_MASK) | REG_PTR;
2226 regsAVR[R31_IDX].type = (regsAVR[R31_IDX].type & ~REG_MASK) | REG_PTR;
2229 /* registers 0-1 / 24-25 used as scratch */
2230 regsAVR[R0_IDX].isFree =
2231 regsAVR[R1_IDX].isFree =
2232 regsAVR[R24_IDX].isFree = regsAVR[R25_IDX].isFree = 0;
2234 /* if this has no function calls then we need
2235 to do something special
2236 a) pre-assign registers to parameters RECEIVE
2237 b) mark the remaining parameter regs as free */
2238 /* mark the parameter regs as SCRACH */
2239 for (i = R16_IDX; i <= R23_IDX; i++) {
2240 regsAVR[i].type = (regsAVR[i].type & ~REG_MASK) | REG_SCR;
2241 regsAVR[i].isFree = 1;
2243 if (!IFFUNC_HASFCALL(currFunc->type)) {
2244 preAssignParms (ebbs[0]->sch);
2246 /* Y - is not allocated (it is the stack frame) */
2247 regsAVR[R28_IDX].isFree = regsAVR[R28_IDX].isFree = 0;
2250 /*-----------------------------------------------------------------*/
2251 /* assignRegisters - assigns registers to each live range as need */
2252 /*-----------------------------------------------------------------*/
2254 avr_assignRegisters (eBBlock ** ebbs, int count)
2259 setToNull ((void *) &_G.funcrUsed);
2260 avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2262 /* change assignments this will remove some
2263 live ranges reducing some register pressure */
2264 for (i = 0; i < count; i++)
2265 packRegisters (ebbs[i]);
2267 if (options.dump_pack)
2268 dumpEbbsToFileExt (DUMP_PACK, ebbs, count);
2270 /* first determine for each live range the number of
2271 registers & the type of registers required for each */
2274 /* setup the default registers */
2275 setDefaultRegs (ebbs, count);
2277 /* and serially allocate registers */
2278 serialRegAssign (ebbs, count);
2280 /* if stack was extended then tell the user */
2281 if (_G.stackExtend) {
2282 /* werror(W_TOOMANY_SPILS,"stack", */
2283 /* _G.stackExtend,currFunc->name,""); */
2287 if (_G.dataExtend) {
2288 /* werror(W_TOOMANY_SPILS,"data space", */
2289 /* _G.dataExtend,currFunc->name,""); */
2293 /* after that create the register mask
2294 for each of the instruction */
2295 createRegMask (ebbs, count);
2297 /* redo that offsets for stacked automatic variables */
2298 redoStackOffsets ();
2300 if (options.dump_rassgn)
2301 dumpEbbsToFileExt (DUMP_RASSGN, ebbs, count);
2303 /* now get back the chain */
2304 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2308 /* for (; ic ; ic = ic->next) */
2309 /* piCode(ic,stdout); */
2310 /* free up any _G.stackSpil locations allocated */
2311 applyToSet (_G.stackSpil, deallocStackSpil);
2313 setToNull ((void **) &_G.stackSpil);
2314 setToNull ((void **) &_G.spiltSet);
2315 /* mark all registers as free */