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);
552 /*-----------------------------------------------------------------*/
553 /* computeSpillable - given a point find the spillable live ranges */
554 /*-----------------------------------------------------------------*/
556 computeSpillable (iCode * ic)
560 /* spillable live ranges are those that are live at this
561 point . the following categories need to be subtracted
563 a) - those that are already spilt
564 b) - if being used by this one
565 c) - defined by this one */
567 spillable = bitVectCopy (ic->rlive);
568 spillable = bitVectCplAnd (spillable, _G.spiltSet); /* those already spilt */
569 spillable = bitVectCplAnd (spillable, ic->uses); /* used in this one */
570 bitVectUnSetBit (spillable, ic->defKey);
571 spillable = bitVectIntersect (spillable, _G.regAssigned);
576 /*-----------------------------------------------------------------*/
577 /* noSpilLoc - return true if a variable has no spil location */
578 /*-----------------------------------------------------------------*/
580 noSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
582 return (sym->usl.spillLoc ? 0 : 1);
585 /*-----------------------------------------------------------------*/
586 /* hasSpilLoc - will return 1 if the symbol has spil location */
587 /*-----------------------------------------------------------------*/
589 hasSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
591 return (sym->usl.spillLoc ? 1 : 0);
594 /*-----------------------------------------------------------------*/
595 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location */
596 /* but is not used as a pointer */
597 /*-----------------------------------------------------------------*/
599 hasSpilLocnoUptr (symbol * sym, eBBlock * ebp, iCode * ic)
601 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
604 /*-----------------------------------------------------------------*/
605 /* rematable - will return 1 if the remat flag is set */
606 /*-----------------------------------------------------------------*/
608 rematable (symbol * sym, eBBlock * ebp, iCode * ic)
613 /*-----------------------------------------------------------------*/
614 /* notUsedInRemaining - not used or defined in remain of the block */
615 /*-----------------------------------------------------------------*/
617 notUsedInRemaining (symbol * sym, eBBlock * ebp, iCode * ic)
619 return ((usedInRemaining (operandFromSymbol (sym), ic) ? 0 : 1) &&
620 allDefsOutOfRange (sym->defs, ic->seq, ebp->lSeq));
623 /*-----------------------------------------------------------------*/
624 /* allLRs - return true for all */
625 /*-----------------------------------------------------------------*/
627 allLRs (symbol * sym, eBBlock * ebp, iCode * ic)
632 /*-----------------------------------------------------------------*/
633 /* liveRangesWith - applies function to a given set of live range */
634 /*-----------------------------------------------------------------*/
636 liveRangesWith (bitVect * lrs,
637 int (func) (symbol *, eBBlock *, iCode *),
638 eBBlock * ebp, iCode * ic)
643 if (!lrs || !lrs->size)
646 for (i = 1; i < lrs->size; i++) {
648 if (!bitVectBitValue (lrs, i))
651 /* if we don't find it in the live range
652 hash table we are in serious trouble */
653 if (!(sym = hTabItemWithKey (liveRanges, i))) {
654 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
655 "liveRangesWith could not find liveRange");
659 if (func (sym, ebp, ic)
660 && bitVectBitValue (_G.regAssigned,
661 sym->key)) addSetHead (&rset, sym);
668 /*-----------------------------------------------------------------*/
669 /* leastUsedLR - given a set determines which is the least used */
670 /*-----------------------------------------------------------------*/
672 leastUsedLR (set * sset)
674 symbol *sym = NULL, *lsym = NULL;
676 sym = lsym = setFirstItem (sset);
681 for (; lsym; lsym = setNextItem (sset)) {
683 /* if usage is the same then prefer
684 the spill the smaller of the two */
685 if (lsym->used == sym->used)
686 if (getSize (lsym->type) < getSize (sym->type))
690 if (lsym->used < sym->used)
695 setToNull ((void *) &sset);
700 /*-----------------------------------------------------------------*/
701 /* noOverLap - will iterate through the list looking for over lap */
702 /*-----------------------------------------------------------------*/
704 noOverLap (set * itmpStack, symbol * fsym)
709 for (sym = setFirstItem (itmpStack); sym;
710 sym = setNextItem (itmpStack)) {
711 if (sym->liveTo > fsym->liveFrom)
719 /*-----------------------------------------------------------------*/
720 /* isFree - will return 1 if the a free spil location is found */
721 /*-----------------------------------------------------------------*/
726 V_ARG (symbol **, sloc);
727 V_ARG (symbol *, fsym);
729 /* if already found */
733 /* if it is free && and the itmp assigned to
734 this does not have any overlapping live ranges
735 with the one currently being assigned and
736 the size can be accomodated */
738 noOverLap (sym->usl.itmpStack, fsym) &&
739 getSize (sym->type) >= getSize (fsym->type)) {
747 /*-----------------------------------------------------------------*/
748 /* createStackSpil - create a location on the stack to spil */
749 /*-----------------------------------------------------------------*/
751 createStackSpil (symbol * sym)
754 int useXstack, model, noOverlay;
759 /* first go try and find a free one that is already
760 existing on the stack */
761 if (applyToSet (_G.stackSpil, isFree, &sloc, sym)) {
762 /* found a free one : just update & return */
763 sym->usl.spillLoc = sloc;
766 addSetHead (&sloc->usl.itmpStack, sym);
770 /* could not then have to create one , this is the hard part
771 we need to allocate this on the stack : this is really a
772 hack!! but cannot think of anything better at this time */
774 if (sprintf (slocBuffer, "sloc%d", _G.slocNum++) >=
775 sizeof (slocBuffer)) {
777 "***Internal error: slocBuffer overflowed: %s:%d\n",
782 sloc = newiTemp (slocBuffer);
784 /* set the type to the spilling symbol */
785 sloc->type = copyLinkChain (sym->type);
786 sloc->etype = getSpec (sloc->type);
787 SPEC_SCLS (sloc->etype) = S_AUTO;
788 SPEC_EXTR (sloc->etype) = 0;
790 /* we don't allow it to be allocated`
791 onto the external stack since : so we
792 temporarily turn it off ; we also
793 turn off memory model to prevent
794 the spil from going to the external storage
795 and turn off overlaying
798 useXstack = options.useXstack;
799 model = options.model;
800 noOverlay = options.noOverlay;
801 stackAuto = options.stackAuto;
802 options.noOverlay = 1;
803 options.model = options.useXstack = 0;
807 options.useXstack = useXstack;
808 options.model = model;
809 options.noOverlay = noOverlay;
810 options.stackAuto = stackAuto;
811 sloc->isref = 1; /* to prevent compiler warning */
813 /* if it is on the stack then update the stack */
814 if (IN_STACK (sloc->etype)) {
815 currFunc->stack += getSize (sloc->type);
816 _G.stackExtend += getSize (sloc->type);
819 _G.dataExtend += getSize (sloc->type);
821 /* add it to the _G.stackSpil set */
822 addSetHead (&_G.stackSpil, sloc);
823 sym->usl.spillLoc = sloc;
826 /* add it to the set of itempStack set
827 of the spill location */
828 addSetHead (&sloc->usl.itmpStack, sym);
832 /*-----------------------------------------------------------------*/
833 /* spillThis - spils a specific operand */
834 /*-----------------------------------------------------------------*/
836 spillThis (symbol * sym)
839 /* if this is rematerializable or has a spillLocation
840 we are okay, else we need to create a spillLocation
842 if (!(sym->remat || sym->usl.spillLoc))
843 createStackSpil (sym);
846 /* mark it has spilt & put it in the spilt set */
848 _G.spiltSet = bitVectSetBit (_G.spiltSet, sym->key);
850 bitVectUnSetBit (_G.regAssigned, sym->key);
852 for (i = 0; i < sym->nRegs; i++)
855 freeReg (sym->regs[i]);
859 if (sym->usl.spillLoc && !sym->remat)
860 sym->usl.spillLoc->allocreq = 1;
864 /*-----------------------------------------------------------------*/
865 /* selectSpil - select a iTemp to spil : rather a simple procedure */
866 /*-----------------------------------------------------------------*/
868 selectSpil (iCode * ic, eBBlock * ebp, symbol * forSym)
870 bitVect *lrcs = NULL;
874 /* get the spillable live ranges */
875 lrcs = computeSpillable (ic);
877 /* get all live ranges that are rematerizable */
878 if ((selectS = liveRangesWith (lrcs, rematable, ebp, ic))) {
880 /* return the least used of these */
881 return leastUsedLR (selectS);
884 /* if the symbol is local to the block then */
885 if (forSym->liveTo < ebp->lSeq) {
887 /* check if there are any live ranges allocated
888 to registers that are not used in this block */
891 liveRangesWith (lrcs, notUsedInBlock, ebp, ic))) {
892 sym = leastUsedLR (selectS);
893 /* if this is not rematerializable */
901 /* check if there are any live ranges that not
902 used in the remainder of the block */
904 !isiCodeInFunctionCall (ic) &&
906 liveRangesWith (lrcs, notUsedInRemaining, ebp, ic))) {
907 sym = leastUsedLR (selectS);
918 /* find live ranges with spillocation && not used as pointers */
919 if ((selectS = liveRangesWith (lrcs, hasSpilLocnoUptr, ebp, ic))) {
921 sym = leastUsedLR (selectS);
922 /* mark this as allocation required */
923 sym->usl.spillLoc->allocreq = 1;
927 /* find live ranges with spillocation */
928 if ((selectS = liveRangesWith (lrcs, hasSpilLoc, ebp, ic))) {
930 sym = leastUsedLR (selectS);
931 sym->usl.spillLoc->allocreq = 1;
935 /* couldn't find then we need to create a spil
936 location on the stack , for which one? the least
938 if ((selectS = liveRangesWith (lrcs, noSpilLoc, ebp, ic))) {
940 /* return a created spil location */
941 sym = createStackSpil (leastUsedLR (selectS));
942 sym->usl.spillLoc->allocreq = 1;
946 /* this is an extreme situation we will spill
947 this one : happens very rarely but it does happen */
953 /*-----------------------------------------------------------------*/
954 /* spilSomething - spil some variable & mark registers as free */
955 /*-----------------------------------------------------------------*/
957 spilSomething (iCode * ic, eBBlock * ebp, symbol * forSym)
962 /* get something we can spil */
963 ssym = selectSpil (ic, ebp, forSym);
965 /* mark it as spilt */
967 _G.spiltSet = bitVectSetBit (_G.spiltSet, ssym->key);
969 /* mark it as not register assigned &
970 take it away from the set */
971 bitVectUnSetBit (_G.regAssigned, ssym->key);
973 /* mark the registers as free */
974 for (i = 0; i < ssym->nRegs; i++)
976 freeReg (ssym->regs[i]);
978 /* if this was a block level spil then insert push & pop
979 at the start & end of block respectively */
980 if (ssym->blockSpil) {
981 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
982 /* add push to the start of the block */
983 addiCodeToeBBlock (ebp, nic, (ebp->sch->op == LABEL ?
984 ebp->sch->next : ebp->sch));
985 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
986 /* add pop to the end of the block */
987 addiCodeToeBBlock (ebp, nic, NULL);
990 /* if spilt because not used in the remainder of the
991 block then add a push before this instruction and
992 a pop at the end of the block */
993 if (ssym->remainSpil) {
995 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
996 /* add push just before this instruction */
997 addiCodeToeBBlock (ebp, nic, ic);
999 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
1000 /* add pop to the end of the block */
1001 addiCodeToeBBlock (ebp, nic, NULL);
1010 /*-----------------------------------------------------------------*/
1011 /* getRegPtr - will try for PTR if not a GPR type if not spil */
1012 /*-----------------------------------------------------------------*/
1014 getRegPtr (iCode * ic, eBBlock * ebp, symbol * sym)
1019 /* try for a ptr type */
1020 if ((reg = allocReg (REG_PTR|REG_PAIR)))
1023 /* try for gpr type / pair */
1024 if ((reg = allocReg (REG_GPR|REG_PAIR)))
1027 /* try for gpr type */
1028 if ((reg = allocReg (REG_GPR)))
1031 /* we have to spil */
1032 if (!spilSomething (ic, ebp, sym))
1035 /* this looks like an infinite loop but
1036 in reality selectSpil will abort */
1040 /*-----------------------------------------------------------------*/
1041 /* getRegScr - will try for SCR if not a GPR type if not spil */
1042 /*-----------------------------------------------------------------*/
1044 getRegScr (iCode * ic, eBBlock * ebp, symbol * sym)
1050 /* try for a scratch non-pair */
1051 if ((reg = allocReg (REG_SCR)))
1054 if ((reg = allocReg (REG_GPR)))
1057 /* we have to spil */
1058 if (!spilSomething (ic, ebp, sym))
1061 /* this looks like an infinite loop but
1062 in really selectSpil will abort */
1066 /*-----------------------------------------------------------------*/
1067 /* getRegGpr - will try for GPR if not spil */
1068 /*-----------------------------------------------------------------*/
1070 getRegGpr (iCode * ic, eBBlock * ebp, symbol * sym )
1075 /* try for gpr type */
1076 if ((reg = allocReg (REG_GPR)))
1080 if ((reg = allocReg (REG_PTR)))
1083 /* we have to spil */
1084 if (!spilSomething (ic, ebp, sym))
1087 /* this looks like an infinite loop but
1088 in reality selectSpil will abort */
1092 /*-----------------------------------------------------------------*/
1093 /* symHasReg - symbol has a given register */
1094 /*-----------------------------------------------------------------*/
1096 symHasReg (symbol * sym, regs * reg)
1100 for (i = 0; i < sym->nRegs; i++)
1101 if (sym->regs[i] == reg)
1107 /*-----------------------------------------------------------------*/
1108 /* deassignLRs - check the live to and if they have registers & are */
1109 /* not spilt then free up the registers */
1110 /*-----------------------------------------------------------------*/
1112 deassignLRs (iCode * ic, eBBlock * ebp)
1118 for (sym = hTabFirstItem (liveRanges, &k); sym;
1119 sym = hTabNextItem (liveRanges, &k)) {
1121 symbol *psym = NULL;
1122 /* if it does not end here */
1123 if (sym->liveTo > ic->seq)
1126 /* if it was spilt on stack then we can
1127 mark the stack spil location as free */
1129 if (sym->stackSpil) {
1130 sym->usl.spillLoc->isFree = 1;
1136 if (!bitVectBitValue (_G.regAssigned, sym->key))
1139 /* special case check if this is an IFX &
1140 the privious one was a pop and the
1141 previous one was not spilt then keep track
1143 if (ic->op == IFX && ic->prev &&
1144 ic->prev->op == IPOP &&
1145 !ic->prev->parmPush &&
1146 !OP_SYMBOL (IC_LEFT (ic->prev))->isspilt)
1147 psym = OP_SYMBOL (IC_LEFT (ic->prev));
1152 bitVectUnSetBit (_G.regAssigned, sym->key);
1154 /* if the result of this one needs registers
1155 and does not have it then assign it right
1157 if (IC_RESULT (ic) && !(SKIP_IC2 (ic) || /* not a special icode */
1158 ic->op == JUMPTABLE ||
1163 POINTER_SET (ic)) &&
1164 (result = OP_SYMBOL (IC_RESULT (ic))) && /* has a result */
1165 result->liveTo > ic->seq && /* and will live beyond this */
1166 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
1167 result->liveFrom == ic->seq && /* does not start before here */
1168 result->regType == sym->regType && /* same register types */
1169 result->nRegs && /* which needs registers */
1170 !result->isspilt && /* and does not already have them */
1172 !bitVectBitValue (_G.regAssigned, result->key) &&
1173 /* the number of free regs + number of regs in this LR
1174 can accomodate the what result Needs */
1175 ((nfreeRegsType (result->regType) + sym->nRegs) >= result->nRegs)) {
1177 for (i = 0; i < result->nRegs; i++) {
1179 result->regs[i] = sym->regs[i];
1180 else if (result->regType == REG_SCR)
1181 result->regs[i] = getRegScr (ic, ebp, result);
1183 result->regs[i] = getRegGpr (ic, ebp, result);
1185 _G.regAssigned = bitVectSetBit (_G.regAssigned, result->key);
1189 /* free the remaining */
1190 for (; i < sym->nRegs; i++) {
1192 if (!symHasReg (psym, sym->regs[i]))
1193 freeReg (sym->regs[i]);
1195 else freeReg (sym->regs[i]);
1202 /*-----------------------------------------------------------------*/
1203 /* reassignLR - reassign this to registers */
1204 /*-----------------------------------------------------------------*/
1206 reassignLR (operand * op)
1208 symbol *sym = OP_SYMBOL (op);
1211 /* not spilt any more */
1212 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
1213 bitVectUnSetBit (_G.spiltSet, sym->key);
1215 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1219 for (i = 0; i < sym->nRegs; i++)
1220 sym->regs[i]->isFree = 0;
1223 /*-----------------------------------------------------------------*/
1224 /* willCauseSpill - determines if allocating will cause a spill */
1225 /*-----------------------------------------------------------------*/
1227 willCauseSpill (int nr, int rt)
1229 /* first check if there are any avlb registers
1230 of te type required */
1231 if (rt == REG_PTR) {
1232 /* special case for pointer type
1233 if pointer type not avlb then
1234 check for type gpr */
1235 if (nFreeRegs (rt) >= nr)
1237 if (nFreeRegs (REG_GPR) >= nr)
1241 if (avr_ptrRegReq) {
1242 if (nFreeRegs (rt) >= nr)
1246 if (nFreeRegs (REG_PTR) + nFreeRegs (REG_GPR) >= nr)
1251 /* it will cause a spil */
1255 /*-----------------------------------------------------------------*/
1256 /* positionRegs - the allocator can allocate same registers to res- */
1257 /* ult and operand, if this happens make sure they are in the same */
1258 /* position as the operand otherwise chaos results */
1259 /*-----------------------------------------------------------------*/
1261 positionRegs (symbol * result, symbol * opsym, int lineno)
1263 int count = min (result->nRegs, opsym->nRegs);
1264 int i, j = 0, shared = 0;
1266 /* if the result has been spilt then cannot share */
1271 /* first make sure that they actually share */
1272 for (i = 0; i < count; i++) {
1273 for (j = 0; j < count; j++) {
1274 if (result->regs[i] == opsym->regs[j] && i != j) {
1282 regs *tmp = result->regs[i];
1283 result->regs[i] = result->regs[j];
1284 result->regs[j] = tmp;
1289 /*-----------------------------------------------------------------*/
1290 /* needsPair - heuristic to determine if a pair would be good */
1291 /*-----------------------------------------------------------------*/
1292 static int needsPair (iCode *ic)
1294 symbol *sym = OP_SYMBOL(IC_RESULT(ic));
1295 bitVect *uses_defs =
1296 bitVectUnion(OP_USES (IC_RESULT(ic)),OP_DEFS(IC_RESULT(ic)));
1298 /* if size is less than 2 then NO */
1299 if (sym->nRegs < 2) return 0;
1300 /* if type Pointer then YES */
1301 if (IS_PTR(sym->type)) return 1;
1303 /* go thru the usages of this operand if used with
1304 a constant then yes */
1305 while (!bitVectIsZero(uses_defs)) {
1306 int ikey = bitVectFirstBit(uses_defs);
1307 iCode *uic = hTabItemWithKey(iCodehTab,ikey);
1308 sym_link *otype = NULL;
1309 bitVectUnSetBit(uses_defs,ikey);
1311 otype = (IC_RIGHT(uic) ? operandType(IC_RIGHT(uic)) : NULL);
1312 if (otype && IS_LITERAL(otype)) return 1;
1317 /*-----------------------------------------------------------------*/
1318 /* serialRegAssign - serially allocate registers to the variables */
1319 /*-----------------------------------------------------------------*/
1321 serialRegAssign (eBBlock ** ebbs, int count)
1325 /* for all blocks */
1326 for (i = 0; i < count; i++) {
1330 if (ebbs[i]->noPath &&
1331 (ebbs[i]->entryLabel != entryLabel &&
1332 ebbs[i]->entryLabel != returnLabel))
1335 /* of all instructions do */
1336 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1338 /* if this is an ipop that means some live
1339 range will have to be assigned again */
1341 reassignLR (IC_LEFT (ic));
1343 /* if result is present && is a true symbol */
1344 if (IC_RESULT (ic) && ic->op != IFX &&
1345 IS_TRUE_SYMOP (IC_RESULT (ic)))
1346 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
1348 /* take away registers from live
1349 ranges that end at this instruction */
1350 deassignLRs (ic, ebbs[i]);
1352 /* some don't need registers */
1353 if (SKIP_IC2 (ic) ||
1354 ic->op == JUMPTABLE ||
1358 (IC_RESULT (ic) && POINTER_SET (ic))) continue;
1360 /* now we need to allocate registers
1361 only for the result */
1362 if (IC_RESULT (ic)) {
1363 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1368 /* Make sure any spill location is definately allocated */
1369 if (sym->isspilt && !sym->remat && sym->usl.spillLoc &&
1370 !sym->usl.spillLoc->allocreq) {
1371 sym->usl.spillLoc->allocreq++;
1374 /* if it does not need or is spilt
1375 or is already assigned to registers
1376 or will not live beyond this instructions */
1379 bitVectBitValue (_G.regAssigned, sym->key)
1380 || sym->liveTo <= ic->seq)
1383 /* if some liverange has been spilt at the block level
1384 and this one live beyond this block then spil this
1387 && sym->liveTo > ebbs[i]->lSeq) {
1391 /* if trying to allocate this will cause
1392 a spill and there is nothing to spill
1393 or this one is rematerializable then
1396 willCauseSpill (sym->nRegs,
1398 spillable = computeSpillable (ic);
1399 if (sym->remat || (willCS && bitVectIsZero (spillable))) {
1404 /* If the live range preceeds the point of definition
1405 then ideally we must take into account registers that
1406 have been allocated after sym->liveFrom but freed
1407 before ic->seq. This is complicated, so spill this
1408 symbol instead and let fillGaps handle the allocation. */
1409 if (sym->liveFrom < ic->seq)
1415 /* if it has a spillocation & is used less than
1416 all other live ranges then spill this */
1418 if (sym->usl.spillLoc) {
1419 symbol *leastUsed = leastUsedLR (liveRangesWith (spillable,
1420 allLRs, ebbs[i], ic));
1421 if (leastUsed && leastUsed->used > sym->used) {
1426 /* if none of the liveRanges have a spillLocation then better
1427 to spill this one than anything else already assigned to registers */
1428 if (liveRangesWith(spillable,noSpilLoc,ebbs[i],ic)) {
1435 /* we assign registers to it */
1436 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1437 if (needsPair(ic)) {
1440 if (sym->regType == REG_PTR) regtype = REG_PTR;
1441 else if (sym->regType == REG_SCR) regtype = REG_SCR;
1442 else regtype = REG_GPR;
1443 preg = allocRegPair(regtype);
1445 sym->regs[j++] = preg;
1446 sym->regs[j++] = ®sAVR[preg->rIdx+1];
1449 for (; j < sym->nRegs; j++) {
1450 if (sym->regType == REG_PTR)
1451 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1452 else if (sym->regType == REG_SCR)
1453 sym->regs[j] = getRegScr (ic, ebbs[i], sym);
1455 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1456 /* if the allocation falied which means
1457 this was spilt then break */
1458 if (!sym->regs[j]) break;
1461 /* if it shares registers with operands make sure
1462 that they are in the same position */
1463 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1464 OP_SYMBOL (IC_LEFT (ic))->nRegs
1466 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1467 OP_SYMBOL (IC_LEFT (ic)), ic->lineno);
1468 /* do the same for the right operand */
1469 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))
1470 && OP_SYMBOL (IC_RIGHT (ic))->nRegs)
1471 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1472 OP_SYMBOL (IC_RIGHT (ic)), ic->lineno);
1479 /*-----------------------------------------------------------------*/
1480 /* rUmaskForOp :- returns register mask for an operand */
1481 /*-----------------------------------------------------------------*/
1483 rUmaskForOp (operand * op)
1489 /* only temporaries are assigned registers */
1493 sym = OP_SYMBOL (op);
1495 /* if spilt or no registers assigned to it
1497 if (sym->isspilt || !sym->nRegs)
1500 rumask = newBitVect (avr_nRegs);
1502 for (j = 0; j < sym->nRegs; j++) {
1503 rumask = bitVectSetBit (rumask, sym->regs[j]->rIdx);
1509 /*-----------------------------------------------------------------*/
1510 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1511 /*-----------------------------------------------------------------*/
1513 regsUsedIniCode (iCode * ic)
1515 bitVect *rmask = newBitVect (avr_nRegs);
1517 /* do the special cases first */
1518 if (ic->op == IFX) {
1519 rmask = bitVectUnion (rmask, rUmaskForOp (IC_COND (ic)));
1523 /* for the jumptable */
1524 if (ic->op == JUMPTABLE) {
1525 rmask = bitVectUnion (rmask, rUmaskForOp (IC_JTCOND (ic)));
1530 /* of all other cases */
1532 rmask = bitVectUnion (rmask, rUmaskForOp (IC_LEFT (ic)));
1536 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RIGHT (ic)));
1539 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RESULT (ic)));
1545 /*-----------------------------------------------------------------*/
1546 /* createRegMask - for each instruction will determine the regsUsed */
1547 /*-----------------------------------------------------------------*/
1549 createRegMask (eBBlock ** ebbs, int count)
1553 /* for all blocks */
1554 for (i = 0; i < count; i++) {
1557 if (ebbs[i]->noPath &&
1558 (ebbs[i]->entryLabel != entryLabel &&
1559 ebbs[i]->entryLabel != returnLabel))
1562 /* for all instructions */
1563 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1567 if (SKIP_IC2 (ic) || !ic->rlive)
1570 /* first mark the registers used in this
1572 ic->rUsed = regsUsedIniCode (ic);
1573 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1575 /* now create the register mask for those
1576 registers that are in use : this is a
1577 super set of ic->rUsed */
1578 ic->rMask = newBitVect (avr_nRegs + 1);
1580 /* for all live Ranges alive at this point */
1581 for (j = 1; j < ic->rlive->size; j++) {
1585 /* if not alive then continue */
1586 if (!bitVectBitValue (ic->rlive, j))
1589 /* find the live range we are interested in */
1590 if (!(sym = hTabItemWithKey (liveRanges, j))) {
1591 werror (E_INTERNAL_ERROR, __FILE__,
1593 "createRegMask cannot find live range");
1597 /* if no register assigned to it */
1598 if (!sym->nRegs || sym->isspilt)
1601 /* for all the registers allocated to it */
1602 for (k = 0; k < sym->nRegs; k++) {
1604 int rIdx = sym->regs[k]->rIdx;
1605 ic->rMask = bitVectSetBit (ic-> rMask,rIdx);
1606 /* special case for X & Z registers */
1607 if (rIdx == R26_IDX || rIdx == R27_IDX)
1608 ic->rMask = bitVectSetBit (ic->rMask, X_IDX);
1609 if (rIdx == R30_IDX || rIdx == R31_IDX)
1610 ic->rMask = bitVectSetBit (ic->rMask, Z_IDX);
1619 /*-----------------------------------------------------------------*/
1620 /* regTypeNum - computes the type & number of registers required */
1621 /*-----------------------------------------------------------------*/
1629 /* for each live range do */
1630 for (sym = hTabFirstItem (liveRanges, &k); sym;
1631 sym = hTabNextItem (liveRanges, &k)) {
1633 /* if used zero times then no registers needed */
1634 if ((sym->liveTo - sym->liveFrom) == 0)
1638 /* if the live range is a temporary */
1641 /* if the type is marked as a conditional */
1642 if (sym->regType == REG_CND)
1645 /* if used in return only then we don't
1647 if (sym->ruonly || sym->accuse) {
1648 if (IS_AGGREGATE (sym->type) || sym->isptr)
1650 aggrToPtr (sym->type, FALSE);
1654 /* if the symbol has only one definition &
1655 that definition is a get_pointer and the
1656 pointer we are getting is rematerializable and
1659 if (bitVectnBitsOn (sym->defs) == 1 &&
1660 (ic = hTabItemWithKey (iCodehTab, bitVectFirstBit (sym-> defs)))
1661 && POINTER_GET (ic) && !IS_BITVAR (sym->etype)) {
1663 /* if in data space or idata space then try to
1664 allocate pointer register */
1668 /* if not then we require registers */
1670 ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1671 getSize (sym->type =
1672 aggrToPtr (sym->type,
1673 FALSE)) : getSize (sym->
1676 if (sym->nRegs > 4) {
1678 "allocated more than 4 or 0 registers for type ");
1679 printTypeChain (sym->type, stderr);
1680 fprintf (stderr, "\n");
1683 /* determine the type of register required */
1684 if (sym->nRegs == 2 && /* size is two */
1685 IS_PTR (sym->type) && /* is a pointer */
1686 sym->uptr) { /* has pointer usage i.e. get/set pointer */
1687 sym->regType = REG_PTR;
1691 /* live accross a function call then gpr else scratch */
1692 if (sym->isLiveFcall)
1693 sym->regType = REG_GPR;
1695 sym->regType = REG_SCR;
1699 /* for the first run we don't provide */
1700 /* registers for true symbols we will */
1701 /* see how things go */
1707 /*-----------------------------------------------------------------*/
1708 /* deallocStackSpil - this will set the stack pointer back */
1709 /*-----------------------------------------------------------------*/
1711 DEFSETFUNC (deallocStackSpil)
1719 /*-----------------------------------------------------------------*/
1720 /* packRegsForAssign - register reduction for assignment */
1721 /*-----------------------------------------------------------------*/
1723 packRegsForAssign (iCode * ic, eBBlock * ebp)
1727 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1728 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1729 OP_LIVETO (IC_RIGHT (ic)) > ic->seq) {
1733 /* find the definition of iTempNN scanning backwards if we find a
1734 a use of the true symbol in before we find the definition then
1736 for (dic = ic->prev; dic; dic = dic->prev) {
1738 /* if there is a function call and this is
1739 a parameter & not my parameter then don't pack it */
1740 if ((dic->op == CALL || dic->op == PCALL) &&
1741 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1742 !OP_SYMBOL (IC_RESULT (ic))->ismyparm)) {
1750 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1751 IS_OP_VOLATILE (IC_RESULT (dic))) {
1756 if (IS_SYMOP (IC_RESULT (dic)) &&
1757 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1758 if (POINTER_SET (dic))
1764 if (IS_SYMOP (IC_RIGHT (dic)) &&
1765 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1766 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key)) {
1771 if (IS_SYMOP (IC_LEFT (dic)) &&
1772 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1773 IC_LEFT (dic)->key == IC_RIGHT (ic)->key)) {
1778 if (POINTER_SET (dic) &&
1779 IC_RESULT (dic)->key == IC_RESULT (ic)->key) {
1786 return 0; /* did not find */
1788 /* if the result is on stack or iaccess then it must be
1789 the same atleast one of the operands */
1790 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1791 OP_SYMBOL (IC_RESULT (ic))->iaccess) {
1793 /* the operation has only one symbol
1794 operator then we can pack */
1795 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1796 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1799 if (!((IC_LEFT (dic) &&
1800 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1802 IC_RESULT (ic)->key == IC_RIGHT (dic)->key))) return 0;
1805 /* if in far space & tru symbol then don't */
1806 if ((IS_TRUE_SYMOP (IC_RESULT (ic)))
1807 && isOperandInFarSpace (IC_RESULT (ic))) return 0;
1808 /* found the definition */
1809 /* replace the result with the result of */
1810 /* this assignment and remove this assignment */
1811 IC_RESULT (dic) = IC_RESULT (ic);
1813 if (IS_ITEMP (IC_RESULT (dic))
1814 && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq) {
1815 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1817 /* delete from liverange table also
1818 delete from all the points inbetween and the new
1820 for (sic = dic; sic != ic; sic = sic->next) {
1821 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1822 if (IS_ITEMP (IC_RESULT (dic)))
1823 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1826 remiCodeFromeBBlock (ebp, ic);
1827 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1832 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1835 /*-----------------------------------------------------------------*/
1836 /* packRegsForOneuse : - will reduce some registers for single Use */
1837 /*-----------------------------------------------------------------*/
1839 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1844 /* if returning a literal then do nothing */
1849 if (ic->op != RETURN)
1852 /* this routine will mark the a symbol as used in one
1853 instruction use only && if the defintion is local
1854 (ie. within the basic block) && has only one definition &&
1855 that definiion is either a return value from a
1856 function or does not contain any variables in
1858 uses = bitVectCopy (OP_USES (op));
1859 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1860 if (!bitVectIsZero (uses)) /* has other uses */
1863 /* if it has only one defintion */
1864 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1865 return NULL; /* has more than one definition */
1867 /* get the that definition */
1869 hTabItemWithKey (iCodehTab,
1870 bitVectFirstBit (OP_DEFS (op))))) return NULL;
1872 /* found the definition now check if it is local */
1873 if (dic->seq < ebp->fSeq || dic->seq > ebp->lSeq)
1874 return NULL; /* non-local */
1876 /* now check if it is the return from
1878 if (dic->op == CALL || dic->op == PCALL) {
1879 if (ic->op != SEND && ic->op != RETURN &&
1880 !POINTER_SET(ic) && !POINTER_GET(ic)) {
1881 OP_SYMBOL (op)->ruonly = 1;
1888 /* otherwise check that the definition does
1889 not contain any symbols in far space */
1890 if (IS_OP_RUONLY (IC_LEFT (ic)) || IS_OP_RUONLY (IC_RIGHT (ic))) {
1894 /* if pointer set then make sure the pointer
1896 if (POINTER_SET (dic) &&
1897 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1900 if (POINTER_GET (dic) &&
1901 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1906 /* also make sure the intervenening instructions
1907 don't have any thing in far space */
1908 for (dic = dic->next; dic && dic != ic; dic = dic->next) {
1910 /* if there is an intervening function call then no */
1911 if (dic->op == CALL || dic->op == PCALL)
1913 /* if pointer set then make sure the pointer
1915 if (POINTER_SET (dic) &&
1916 !IS_DATA_PTR (aggrToPtr
1917 (operandType (IC_RESULT (dic)),
1918 FALSE))) return NULL;
1920 if (POINTER_GET (dic) &&
1921 !IS_DATA_PTR (aggrToPtr
1922 (operandType (IC_LEFT (dic)),
1923 FALSE))) return NULL;
1925 /* if address of & the result is remat the okay */
1926 if (dic->op == ADDRESS_OF &&
1927 OP_SYMBOL (IC_RESULT (dic))->remat) continue;
1929 /* if operand has size of three or more & this
1930 operation is a '*','/' or '%' then 'b' may
1932 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1933 getSize (operandType (op)) >= 3)
1936 /* if left or right or result is in far space */
1937 if (IS_OP_RUONLY (IC_LEFT (dic)) ||
1938 IS_OP_RUONLY (IC_RIGHT (dic)) ||
1939 IS_OP_RUONLY (IC_RESULT (dic))) {
1944 OP_SYMBOL (op)->ruonly = 1;
1949 /*-----------------------------------------------------------------*/
1950 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1951 /*-----------------------------------------------------------------*/
1953 isBitwiseOptimizable (iCode * ic)
1955 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
1956 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
1958 /* bitwise operations are considered optimizable
1959 under the following conditions (Jean-Louis VERN)
1971 if (IS_LITERAL (rtype) ||
1972 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
1978 /*-----------------------------------------------------------------*/
1979 /* packRegisters - does some transformations to reduce register */
1981 /*-----------------------------------------------------------------*/
1983 packRegisters (eBBlock * ebp)
1992 /* look for assignments of the form */
1993 /* iTempNN = TRueSym (someoperation) SomeOperand */
1995 /* TrueSym := iTempNN:1 */
1996 for (ic = ebp->sch; ic; ic = ic->next) {
1999 /* find assignment of the form TrueSym := iTempNN:1 */
2000 if (ic->op == '=' && !POINTER_SET (ic))
2001 change += packRegsForAssign (ic, ebp);
2008 for (ic = ebp->sch; ic; ic = ic->next) {
2010 /* if this is an itemp & result of a address of a true sym
2011 then mark this as rematerialisable */
2012 if (ic->op == ADDRESS_OF &&
2013 IS_ITEMP (IC_RESULT (ic)) &&
2014 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2015 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2016 !OP_SYMBOL (IC_LEFT (ic))->onStack) {
2018 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2019 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2020 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2024 /* if straight assignment then carry remat flag if
2025 this is the only definition */
2026 if (ic->op == '=' &&
2027 !POINTER_SET (ic) &&
2028 IS_SYMOP (IC_RIGHT (ic)) &&
2029 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2030 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1) {
2032 OP_SYMBOL (IC_RESULT (ic))->remat =
2033 OP_SYMBOL (IC_RIGHT (ic))->remat;
2034 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2035 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2038 /* if this is a +/- operation with a rematerizable
2039 then mark this as rematerializable as well only
2040 if the literal value is within the range -255 and + 255
2041 the assembler cannot handle it other wise */
2042 if ((ic->op == '+' || ic->op == '-') &&
2043 (IS_SYMOP (IC_LEFT (ic)) &&
2044 IS_ITEMP (IC_RESULT (ic)) &&
2045 OP_SYMBOL (IC_LEFT (ic))->remat &&
2046 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2047 IS_OP_LITERAL (IC_RIGHT (ic)))) {
2049 int i = (int) operandLitValue (IC_RIGHT (ic));
2050 if (i < 255 && i > -255) {
2051 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2052 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2053 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc =
2058 /* mark the pointer usages */
2059 if (POINTER_SET (ic))
2060 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2062 if (POINTER_GET (ic)) {
2063 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2064 if (OP_SYMBOL (IC_LEFT(ic))->remat)
2065 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2068 /* if the condition of an if instruction
2069 is defined in the previous instruction then
2070 mark the itemp as a conditional */
2071 if ((IS_CONDITIONAL (ic) ||
2072 ((ic->op == BITWISEAND ||
2075 isBitwiseOptimizable (ic))) &&
2076 ic->next && ic->next->op == IFX &&
2077 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2078 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq) {
2080 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2084 /* some cases the redundant moves can
2085 can be eliminated for return statements */
2086 if ((ic->op == RETURN || ic->op == SEND))
2087 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2089 /* if this is cast for intergral promotion then
2090 check if only use of the definition of the
2091 operand being casted/ if yes then replace
2092 the result of that arithmetic operation with
2093 this result and get rid of the cast */
2094 if (ic->op == CAST) {
2095 sym_link *fromType = operandType (IC_RIGHT (ic));
2096 sym_link *toType = operandType (IC_LEFT (ic));
2098 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2099 getSize (fromType) != getSize (toType) &&
2100 SPEC_USIGN (fromType) == SPEC_USIGN (toType)) {
2103 packRegsForOneuse (ic, IC_RIGHT (ic),
2106 if (IS_ARITHMETIC_OP (dic)) {
2109 remiCodeFromeBBlock (ebp, ic);
2110 hTabDeleteItem (&iCodehTab,
2117 OP_SYMBOL (IC_RIGHT (ic))->
2123 /* if the type from and type to are the same
2124 then if this is the only use then packit */
2125 if (compareType (operandType (IC_RIGHT (ic)),
2126 operandType (IC_LEFT (ic))) ==
2129 packRegsForOneuse (ic,
2135 remiCodeFromeBBlock (ebp, ic);
2136 hTabDeleteItem (&iCodehTab,
2148 /*-----------------------------------------------------------------*/
2149 /* preAssignParms - we have a leaf function preassign registers */
2150 /*-----------------------------------------------------------------*/
2152 preAssignParms (iCode * ic)
2155 /* look for receives and assign registers
2156 to the result of the receives */
2158 /* if it is a receive */
2159 if (ic->op == RECEIVE) {
2160 symbol *r = OP_SYMBOL (IC_RESULT (ic));
2161 int size = getSize (r->type);
2162 if (r->regType == REG_GPR || r->regType == REG_SCR) {
2165 r->regs[j++] = ®sAVR[i++];
2166 regsAVR[i - 1].isFree = 0;
2168 /* put in the regassigned vector */
2170 bitVectSetBit (_G.regAssigned,
2174 /* not a GPR then we should mark as free */
2176 regsAVR[i++].isFree = 1;
2182 /* mark anything remaining as free */
2183 while (i <= R23_IDX)
2184 regsAVR[i++].isFree = 1;
2187 /*-----------------------------------------------------------------*/
2188 /* setdefaultRegs - do setup stuff for register allocation */
2189 /*-----------------------------------------------------------------*/
2191 setDefaultRegs (eBBlock ** ebbs, int count)
2195 /* if no pointer registers required in this function
2196 then mark r26-27 & r30-r31 as GPR & free */
2197 regsAVR[R26_IDX].isFree =
2198 regsAVR[R27_IDX].isFree =
2199 regsAVR[R30_IDX].isFree = regsAVR[R31_IDX].isFree = 1;
2201 if (!avr_ptrRegReq) {
2202 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_GPR;
2203 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_GPR;
2204 regsAVR[R28_IDX].type = (regsAVR[R28_IDX].type & ~REG_MASK) | REG_GPR;
2205 regsAVR[R29_IDX].type = (regsAVR[R29_IDX].type & ~REG_MASK) | REG_GPR;
2208 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_PTR;
2209 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_PTR;
2210 regsAVR[R30_IDX].type = (regsAVR[R30_IDX].type & ~REG_MASK) | REG_PTR;
2211 regsAVR[R31_IDX].type = (regsAVR[R31_IDX].type & ~REG_MASK) | REG_PTR;
2214 /* registers 0-1 / 24-25 used as scratch */
2215 regsAVR[R0_IDX].isFree =
2216 regsAVR[R1_IDX].isFree =
2217 regsAVR[R24_IDX].isFree = regsAVR[R25_IDX].isFree = 0;
2219 /* if this has no function calls then we need
2220 to do something special
2221 a) pre-assign registers to parameters RECEIVE
2222 b) mark the remaining parameter regs as free */
2223 /* mark the parameter regs as SCRACH */
2224 for (i = R16_IDX; i <= R23_IDX; i++) {
2225 regsAVR[i].type = (regsAVR[i].type & ~REG_MASK) | REG_SCR;
2226 regsAVR[i].isFree = 1;
2228 if (!IFFUNC_HASFCALL(currFunc->type)) {
2229 preAssignParms (ebbs[0]->sch);
2231 /* Y - is not allocated (it is the stack frame) */
2232 regsAVR[R28_IDX].isFree = regsAVR[R28_IDX].isFree = 0;
2235 /*-----------------------------------------------------------------*/
2236 /* assignRegisters - assigns registers to each live range as need */
2237 /*-----------------------------------------------------------------*/
2239 avr_assignRegisters (ebbIndex * ebbi)
2241 eBBlock ** ebbs = ebbi->bbOrder;
2242 int count = ebbi->count;
2246 setToNull ((void *) &_G.funcrUsed);
2247 avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2249 /* change assignments this will remove some
2250 live ranges reducing some register pressure */
2251 for (i = 0; i < count; i++)
2252 packRegisters (ebbs[i]);
2254 /* liveranges probably changed by register packing
2255 so we compute them again */
2256 recomputeLiveRanges (ebbs, count);
2258 if (options.dump_pack)
2259 dumpEbbsToFileExt (DUMP_PACK, ebbi);
2261 /* first determine for each live range the number of
2262 registers & the type of registers required for each */
2265 /* setup the default registers */
2266 setDefaultRegs (ebbs, count);
2268 /* and serially allocate registers */
2269 serialRegAssign (ebbs, count);
2271 /* if stack was extended then tell the user */
2272 if (_G.stackExtend) {
2273 /* werror(W_TOOMANY_SPILS,"stack", */
2274 /* _G.stackExtend,currFunc->name,""); */
2278 if (_G.dataExtend) {
2279 /* werror(W_TOOMANY_SPILS,"data space", */
2280 /* _G.dataExtend,currFunc->name,""); */
2284 /* after that create the register mask
2285 for each of the instruction */
2286 createRegMask (ebbs, count);
2288 /* redo that offsets for stacked automatic variables */
2289 redoStackOffsets ();
2291 if (options.dump_rassgn)
2292 dumpEbbsToFileExt (DUMP_RASSGN, ebbi);
2294 /* now get back the chain */
2295 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2299 /* for (; ic ; ic = ic->next) */
2300 /* piCode(ic,stdout); */
2301 /* free up any _G.stackSpil locations allocated */
2302 applyToSet (_G.stackSpil, deallocStackSpil);
2304 setToNull ((void *) &_G.stackSpil);
2305 setToNull ((void *) &_G.spiltSet);
2306 /* mark all registers as free */