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;
1343 otype = (IC_RIGHT(uic) ? operandType(IC_RIGHT(uic)) : NULL);
1344 if (otype && IS_LITERAL(otype)) return 1;
1345 bitVectUnSetBit(uses_defs,ikey);
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 ic->rMask = bitVectSetBit (ic-> rMask, sym->regs[k]->rIdx);
1621 /* special case for X & Z registers */
1622 if (k == R26_IDX || k == R27_IDX)
1623 ic->rMask = bitVectSetBit (ic->rMask, X_IDX);
1624 if (k == R30_IDX || k == R31_IDX)
1625 ic->rMask = bitVectSetBit (ic->rMask, Z_IDX);
1634 /*-----------------------------------------------------------------*/
1635 /* regTypeNum - computes the type & number of registers required */
1636 /*-----------------------------------------------------------------*/
1644 /* for each live range do */
1645 for (sym = hTabFirstItem (liveRanges, &k); sym;
1646 sym = hTabNextItem (liveRanges, &k)) {
1648 /* if used zero times then no registers needed */
1649 if ((sym->liveTo - sym->liveFrom) == 0)
1653 /* if the live range is a temporary */
1656 /* if the type is marked as a conditional */
1657 if (sym->regType == REG_CND)
1660 /* if used in return only then we don't
1662 if (sym->ruonly || sym->accuse) {
1663 if (IS_AGGREGATE (sym->type) || sym->isptr)
1665 aggrToPtr (sym->type, FALSE);
1669 /* if the symbol has only one definition &
1670 that definition is a get_pointer and the
1671 pointer we are getting is rematerializable and
1674 if (bitVectnBitsOn (sym->defs) == 1 &&
1675 (ic = hTabItemWithKey (iCodehTab, bitVectFirstBit (sym-> defs)))
1676 && POINTER_GET (ic) && !IS_BITVAR (sym->etype)) {
1678 /* if in data space or idata space then try to
1679 allocate pointer register */
1683 /* if not then we require registers */
1685 ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1686 getSize (sym->type =
1687 aggrToPtr (sym->type,
1688 FALSE)) : getSize (sym->
1691 if (sym->nRegs > 4) {
1693 "allocated more than 4 or 0 registers for type ");
1694 printTypeChain (sym->type, stderr);
1695 fprintf (stderr, "\n");
1698 /* determine the type of register required */
1699 if (sym->nRegs == 2 && /* size is two */
1700 IS_PTR (sym->type) && /* is a pointer */
1701 sym->uptr) { /* has pointer usage i.e. get/set pointer */
1702 sym->regType = REG_PTR;
1706 /* live accross a function call then gpr else scratch */
1707 if (sym->isLiveFcall)
1708 sym->regType = REG_GPR;
1710 sym->regType = REG_SCR;
1714 /* for the first run we don't provide */
1715 /* registers for true symbols we will */
1716 /* see how things go */
1722 /*-----------------------------------------------------------------*/
1723 /* deallocStackSpil - this will set the stack pointer back */
1724 /*-----------------------------------------------------------------*/
1726 DEFSETFUNC (deallocStackSpil)
1734 /*-----------------------------------------------------------------*/
1735 /* packRegsForAssign - register reduction for assignment */
1736 /*-----------------------------------------------------------------*/
1738 packRegsForAssign (iCode * ic, eBBlock * ebp)
1742 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1743 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1744 OP_LIVETO (IC_RIGHT (ic)) > ic->seq) {
1748 /* find the definition of iTempNN scanning backwards if we find a
1749 a use of the true symbol in before we find the definition then
1751 for (dic = ic->prev; dic; dic = dic->prev) {
1753 /* if there is a function call and this is
1754 a parameter & not my parameter then don't pack it */
1755 if ((dic->op == CALL || dic->op == PCALL) &&
1756 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1757 !OP_SYMBOL (IC_RESULT (ic))->ismyparm)) {
1765 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1766 IS_OP_VOLATILE (IC_RESULT (dic))) {
1771 if (IS_SYMOP (IC_RESULT (dic)) &&
1772 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1773 if (POINTER_SET (dic))
1779 if (IS_SYMOP (IC_RIGHT (dic)) &&
1780 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1781 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key)) {
1786 if (IS_SYMOP (IC_LEFT (dic)) &&
1787 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1788 IC_LEFT (dic)->key == IC_RIGHT (ic)->key)) {
1793 if (POINTER_SET (dic) &&
1794 IC_RESULT (dic)->key == IC_RESULT (ic)->key) {
1801 return 0; /* did not find */
1803 /* if the result is on stack or iaccess then it must be
1804 the same atleast one of the operands */
1805 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1806 OP_SYMBOL (IC_RESULT (ic))->iaccess) {
1808 /* the operation has only one symbol
1809 operator then we can pack */
1810 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1811 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1814 if (!((IC_LEFT (dic) &&
1815 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1817 IC_RESULT (ic)->key == IC_RIGHT (dic)->key))) return 0;
1820 /* if in far space & tru symbol then don't */
1821 if ((IS_TRUE_SYMOP (IC_RESULT (ic)))
1822 && isOperandInFarSpace (IC_RESULT (ic))) return 0;
1823 /* found the definition */
1824 /* replace the result with the result of */
1825 /* this assignment and remove this assignment */
1826 IC_RESULT (dic) = IC_RESULT (ic);
1828 if (IS_ITEMP (IC_RESULT (dic))
1829 && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq) {
1830 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1832 /* delete from liverange table also
1833 delete from all the points inbetween and the new
1835 for (sic = dic; sic != ic; sic = sic->next) {
1836 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1837 if (IS_ITEMP (IC_RESULT (dic)))
1838 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1841 remiCodeFromeBBlock (ebp, ic);
1842 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1847 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1850 /*-----------------------------------------------------------------*/
1851 /* packRegsForOneuse : - will reduce some registers for single Use */
1852 /*-----------------------------------------------------------------*/
1854 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1859 /* if returning a literal then do nothing */
1864 if (ic->op != RETURN)
1867 /* this routine will mark the a symbol as used in one
1868 instruction use only && if the defintion is local
1869 (ie. within the basic block) && has only one definition &&
1870 that definiion is either a return value from a
1871 function or does not contain any variables in
1873 uses = bitVectCopy (OP_USES (op));
1874 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1875 if (!bitVectIsZero (uses)) /* has other uses */
1878 /* if it has only one defintion */
1879 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1880 return NULL; /* has more than one definition */
1882 /* get the that definition */
1884 hTabItemWithKey (iCodehTab,
1885 bitVectFirstBit (OP_DEFS (op))))) return NULL;
1887 /* found the definition now check if it is local */
1888 if (dic->seq < ebp->fSeq || dic->seq > ebp->lSeq)
1889 return NULL; /* non-local */
1891 /* now check if it is the return from
1893 if (dic->op == CALL || dic->op == PCALL) {
1894 if (ic->op != SEND && ic->op != RETURN) {
1895 OP_SYMBOL (op)->ruonly = 1;
1902 /* otherwise check that the definition does
1903 not contain any symbols in far space */
1904 if (IS_OP_RUONLY (IC_LEFT (ic)) || IS_OP_RUONLY (IC_RIGHT (ic))) {
1908 /* if pointer set then make sure the pointer
1910 if (POINTER_SET (dic) &&
1911 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1914 if (POINTER_GET (dic) &&
1915 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1920 /* also make sure the intervenening instructions
1921 don't have any thing in far space */
1922 for (dic = dic->next; dic && dic != ic; dic = dic->next) {
1924 /* if there is an intervening function call then no */
1925 if (dic->op == CALL || dic->op == PCALL)
1927 /* if pointer set then make sure the pointer
1929 if (POINTER_SET (dic) &&
1930 !IS_DATA_PTR (aggrToPtr
1931 (operandType (IC_RESULT (dic)),
1932 FALSE))) return NULL;
1934 if (POINTER_GET (dic) &&
1935 !IS_DATA_PTR (aggrToPtr
1936 (operandType (IC_LEFT (dic)),
1937 FALSE))) return NULL;
1939 /* if address of & the result is remat the okay */
1940 if (dic->op == ADDRESS_OF &&
1941 OP_SYMBOL (IC_RESULT (dic))->remat) continue;
1943 /* if operand has size of three or more & this
1944 operation is a '*','/' or '%' then 'b' may
1946 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1947 getSize (operandType (op)) >= 3)
1950 /* if left or right or result is in far space */
1951 if (IS_OP_RUONLY (IC_LEFT (dic)) ||
1952 IS_OP_RUONLY (IC_RIGHT (dic)) ||
1953 IS_OP_RUONLY (IC_RESULT (dic))) {
1958 OP_SYMBOL (op)->ruonly = 1;
1963 /*-----------------------------------------------------------------*/
1964 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1965 /*-----------------------------------------------------------------*/
1967 isBitwiseOptimizable (iCode * ic)
1969 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
1970 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
1972 /* bitwise operations are considered optimizable
1973 under the following conditions (Jean-Louis VERN)
1985 if (IS_LITERAL (rtype) ||
1986 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
1992 /*-----------------------------------------------------------------*/
1993 /* packRegisters - does some transformations to reduce register */
1995 /*-----------------------------------------------------------------*/
1997 packRegisters (eBBlock * ebp)
2006 /* look for assignments of the form */
2007 /* iTempNN = TRueSym (someoperation) SomeOperand */
2009 /* TrueSym := iTempNN:1 */
2010 for (ic = ebp->sch; ic; ic = ic->next) {
2013 /* find assignment of the form TrueSym := iTempNN:1 */
2014 if (ic->op == '=' && !POINTER_SET (ic))
2015 change += packRegsForAssign (ic, ebp);
2022 for (ic = ebp->sch; ic; ic = ic->next) {
2024 /* if this is an itemp & result of a address of a true sym
2025 then mark this as rematerialisable */
2026 if (ic->op == ADDRESS_OF &&
2027 IS_ITEMP (IC_RESULT (ic)) &&
2028 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2029 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2030 !OP_SYMBOL (IC_LEFT (ic))->onStack) {
2032 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2033 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2034 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2038 /* if straight assignment then carry remat flag if
2039 this is the only definition */
2040 if (ic->op == '=' &&
2041 !POINTER_SET (ic) &&
2042 IS_SYMOP (IC_RIGHT (ic)) &&
2043 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2044 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1) {
2046 OP_SYMBOL (IC_RESULT (ic))->remat =
2047 OP_SYMBOL (IC_RIGHT (ic))->remat;
2048 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2049 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2052 /* if this is a +/- operation with a rematerizable
2053 then mark this as rematerializable as well only
2054 if the literal value is within the range -255 and + 255
2055 the assembler cannot handle it other wise */
2056 if ((ic->op == '+' || ic->op == '-') &&
2057 (IS_SYMOP (IC_LEFT (ic)) &&
2058 IS_ITEMP (IC_RESULT (ic)) &&
2059 OP_SYMBOL (IC_LEFT (ic))->remat &&
2060 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2061 IS_OP_LITERAL (IC_RIGHT (ic)))) {
2063 int i = (int) operandLitValue (IC_RIGHT (ic));
2064 if (i < 255 && i > -255) {
2065 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2066 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2067 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc =
2072 /* mark the pointer usages */
2073 if (POINTER_SET (ic))
2074 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2076 if (POINTER_GET (ic)) {
2077 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2078 if (OP_SYMBOL (IC_LEFT(ic))->remat)
2079 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2082 /* if the condition of an if instruction
2083 is defined in the previous instruction then
2084 mark the itemp as a conditional */
2085 if ((IS_CONDITIONAL (ic) ||
2086 ((ic->op == BITWISEAND ||
2089 isBitwiseOptimizable (ic))) &&
2090 ic->next && ic->next->op == IFX &&
2091 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2092 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq) {
2094 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2098 /* some cases the redundant moves can
2099 can be eliminated for return statements */
2100 if ((ic->op == RETURN || ic->op == SEND))
2101 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2103 /* if this is cast for intergral promotion then
2104 check if only use of the definition of the
2105 operand being casted/ if yes then replace
2106 the result of that arithmetic operation with
2107 this result and get rid of the cast */
2108 if (ic->op == CAST) {
2109 sym_link *fromType = operandType (IC_RIGHT (ic));
2110 sym_link *toType = operandType (IC_LEFT (ic));
2112 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2113 getSize (fromType) != getSize (toType) &&
2114 SPEC_USIGN (fromType) == SPEC_USIGN (toType)) {
2117 packRegsForOneuse (ic, IC_RIGHT (ic),
2120 if (IS_ARITHMETIC_OP (dic)) {
2123 remiCodeFromeBBlock (ebp, ic);
2124 hTabDeleteItem (&iCodehTab,
2131 OP_SYMBOL (IC_RIGHT (ic))->
2137 /* if the type from and type to are the same
2138 then if this is the only use then packit */
2139 if (compareType (operandType (IC_RIGHT (ic)),
2140 operandType (IC_LEFT (ic))) ==
2143 packRegsForOneuse (ic,
2149 remiCodeFromeBBlock (ebp, ic);
2150 hTabDeleteItem (&iCodehTab,
2162 /*-----------------------------------------------------------------*/
2163 /* preAssignParms - we have a leaf function preassign registers */
2164 /*-----------------------------------------------------------------*/
2166 preAssignParms (iCode * ic)
2169 /* look for receives and assign registers
2170 to the result of the receives */
2172 /* if it is a receive */
2173 if (ic->op == RECEIVE) {
2174 symbol *r = OP_SYMBOL (IC_RESULT (ic));
2175 int size = getSize (r->type);
2176 if (r->regType == REG_GPR || r->regType == REG_SCR) {
2179 r->regs[j++] = ®sAVR[i++];
2180 regsAVR[i - 1].isFree = 0;
2182 /* put in the regassigned vector */
2184 bitVectSetBit (_G.regAssigned,
2188 /* not a GPR then we should mark as free */
2190 regsAVR[i++].isFree = 1;
2196 /* mark anything remaining as free */
2197 while (i <= R23_IDX)
2198 regsAVR[i++].isFree = 1;
2201 /*-----------------------------------------------------------------*/
2202 /* setdefaultRegs - do setup stuff for register allocation */
2203 /*-----------------------------------------------------------------*/
2205 setDefaultRegs (eBBlock ** ebbs, int count)
2209 /* if no pointer registers required in this function
2210 then mark r26-27 & r30-r31 as GPR & free */
2211 regsAVR[R26_IDX].isFree =
2212 regsAVR[R27_IDX].isFree =
2213 regsAVR[R30_IDX].isFree = regsAVR[R31_IDX].isFree = 1;
2215 if (!avr_ptrRegReq) {
2216 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_GPR;
2217 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_GPR;
2218 regsAVR[R28_IDX].type = (regsAVR[R28_IDX].type & ~REG_MASK) | REG_GPR;
2219 regsAVR[R29_IDX].type = (regsAVR[R29_IDX].type & ~REG_MASK) | REG_GPR;
2222 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_PTR;
2223 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_PTR;
2224 regsAVR[R30_IDX].type = (regsAVR[R30_IDX].type & ~REG_MASK) | REG_PTR;
2225 regsAVR[R31_IDX].type = (regsAVR[R31_IDX].type & ~REG_MASK) | REG_PTR;
2228 /* registers 0-1 / 24-25 used as scratch */
2229 regsAVR[R0_IDX].isFree =
2230 regsAVR[R1_IDX].isFree =
2231 regsAVR[R24_IDX].isFree = regsAVR[R25_IDX].isFree = 0;
2233 /* if this has no function calls then we need
2234 to do something special
2235 a) pre-assign registers to parameters RECEIVE
2236 b) mark the remaining parameter regs as free */
2237 /* mark the parameter regs as SCRACH */
2238 for (i = R16_IDX; i <= R23_IDX; i++) {
2239 regsAVR[i].type = (regsAVR[i].type & ~REG_MASK) | REG_SCR;
2240 regsAVR[i].isFree = 1;
2242 if (!currFunc->hasFcall) {
2243 preAssignParms (ebbs[0]->sch);
2245 /* Y - is not allocated (it is the stack frame) */
2246 regsAVR[R28_IDX].isFree = regsAVR[R28_IDX].isFree = 0;
2249 /*-----------------------------------------------------------------*/
2250 /* assignRegisters - assigns registers to each live range as need */
2251 /*-----------------------------------------------------------------*/
2253 avr_assignRegisters (eBBlock ** ebbs, int count)
2258 setToNull ((void *) &_G.funcrUsed);
2259 avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2261 /* change assignments this will remove some
2262 live ranges reducing some register pressure */
2263 for (i = 0; i < count; i++)
2264 packRegisters (ebbs[i]);
2266 if (options.dump_pack)
2267 dumpEbbsToFileExt (DUMP_PACK, ebbs, count);
2269 /* first determine for each live range the number of
2270 registers & the type of registers required for each */
2273 /* setup the default registers */
2274 setDefaultRegs (ebbs, count);
2276 /* and serially allocate registers */
2277 serialRegAssign (ebbs, count);
2279 /* if stack was extended then tell the user */
2280 if (_G.stackExtend) {
2281 /* werror(W_TOOMANY_SPILS,"stack", */
2282 /* _G.stackExtend,currFunc->name,""); */
2286 if (_G.dataExtend) {
2287 /* werror(W_TOOMANY_SPILS,"data space", */
2288 /* _G.dataExtend,currFunc->name,""); */
2292 /* after that create the register mask
2293 for each of the instruction */
2294 createRegMask (ebbs, count);
2296 /* redo that offsets for stacked automatic variables */
2297 redoStackOffsets ();
2299 if (options.dump_rassgn)
2300 dumpEbbsToFileExt (DUMP_RASSGN, ebbs, count);
2302 /* now get back the chain */
2303 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2307 /* for (; ic ; ic = ic->next) */
2308 /* piCode(ic,stdout); */
2309 /* free up any _G.stackSpil locations allocated */
2310 applyToSet (_G.stackSpil, deallocStackSpil);
2312 setToNull ((void **) &_G.stackSpil);
2313 setToNull ((void **) &_G.spiltSet);
2314 /* mark all registers as free */