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, R0_IDX, REG_GPR, "r0", "r0", "", 0, 0, 0}, /* scratch */
59 {REG_GPR, R1_IDX, REG_GPR, "r1", "r1", "", 0, 0, 0}, /* scratch */
60 {REG_GPR, R2_IDX, REG_GPR, "r2", "r2", "", 0, 1, 1}, /* gpr */
61 {REG_GPR, R3_IDX, REG_GPR, "r3", "r3", "", 0, 1, 1}, /* gpr */
62 {REG_GPR, R4_IDX, REG_GPR, "r4", "r4", "", 0, 1, 1}, /* gpr */
63 {REG_GPR, R5_IDX, REG_GPR, "r5", "r5", "", 0, 1, 1}, /* gpr */
64 {REG_GPR, R6_IDX, REG_GPR, "r6", "r6", "", 0, 1, 1}, /* gpr */
65 {REG_GPR, R7_IDX, REG_GPR, "r7", "r7", "", 0, 1, 1}, /* gpr */
66 {REG_GPR, R8_IDX, REG_GPR, "r8", "r8", "", 0, 1, 1}, /* gpr */
67 {REG_GPR, R9_IDX, REG_GPR, "r9", "r9", "", 0, 1, 1}, /* gpr */
68 {REG_GPR, R10_IDX, REG_GPR, "r10", "r10", "", 0, 1, 1}, /* gpr */
69 {REG_GPR, R11_IDX, REG_GPR, "r11", "r11", "", 0, 1, 1}, /* gpr */
70 {REG_GPR, R12_IDX, REG_GPR, "r12", "r12", "", 0, 1, 1}, /* gpr */
71 {REG_GPR, R13_IDX, REG_GPR, "r13", "r13", "", 0, 1, 1}, /* gpr */
72 {REG_GPR, R14_IDX, REG_GPR, "r14", "r14", "", 0, 1, 1}, /* gpr */
73 {REG_GPR, R15_IDX, REG_GPR, "r15", "r15", "", 0, 1, 1}, /* gpr */
74 {REG_GPR, R16_IDX, REG_GPR, "r16", "r16", "", 0, 1, 0}, /* parm/gpr */
75 {REG_GPR, R17_IDX, REG_GPR, "r17", "r17", "", 0, 1, 0}, /* parm/gpr */
76 {REG_GPR, R18_IDX, REG_GPR, "r18", "r18", "", 0, 1, 0}, /* parm/gpr */
77 {REG_GPR, R19_IDX, REG_GPR, "r19", "r19", "", 0, 1, 0}, /* parm/gpr */
78 {REG_GPR, R20_IDX, REG_GPR, "r20", "r20", "", 0, 1, 0}, /* parm/gpr */
79 {REG_GPR, R21_IDX, REG_GPR, "r21", "r21", "", 0, 1, 0}, /* parm/gpr */
80 {REG_GPR, R22_IDX, REG_GPR, "r22", "r22", "", 0, 1, 0}, /* parm/gpr */
81 {REG_GPR, R23_IDX, REG_GPR, "r23", "r23", "", 0, 1, 0}, /* parm/gpr */
82 {REG_GPR, R24_IDX, REG_GPR, "r24", "r24", "", 0, 0, 0}, /* scratch */
83 {REG_GPR, R25_IDX, REG_GPR, "r25", "r25", "", 0, 0, 0}, /* scratch */
84 {REG_GPR, R26_IDX, REG_GPR, "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, R28_IDX, REG_GPR, "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, R30_IDX, REG_GPR, "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 *);
98 /*-----------------------------------------------------------------*/
99 /* allocReg - allocates register of given type */
100 /*-----------------------------------------------------------------*/
102 allocReg (short type)
106 for (i = avr_fReg; i < avr_nRegs; i++) {
108 /* if type is given as 0 then any
109 free register will do */
110 if (!type && regsAVR[i].isFree) {
111 regsAVR[i].isFree = 0;
114 bitVectSetBit (currFunc->regsUsed, i);
117 /* other wise look for specific type
119 if (regsAVR[i].isFree && regsAVR[i].type == type) {
120 regsAVR[i].isFree = 0;
123 bitVectSetBit (currFunc->regsUsed, i);
130 /*-----------------------------------------------------------------*/
131 /* avr_regWithIdx - returns pointer to register wit index number */
132 /*-----------------------------------------------------------------*/
134 avr_regWithIdx (int idx)
138 for (i = 0; i < avr_nRegs; i++)
139 if (regsAVR[i].rIdx == idx)
142 werror (E_INTERNAL_ERROR, __FILE__, __LINE__, "regWithIdx not found");
146 /*-----------------------------------------------------------------*/
147 /* freeReg - frees a register */
148 /*-----------------------------------------------------------------*/
156 /*-----------------------------------------------------------------*/
157 /* nFreeRegs - returns number of free registers */
158 /*-----------------------------------------------------------------*/
165 for (i = avr_fReg; i < avr_nRegs; i++)
166 if (regsAVR[i].isFree && regsAVR[i].type == type)
171 /*-----------------------------------------------------------------*/
172 /* nfreeRegsType - free registers with type */
173 /*-----------------------------------------------------------------*/
175 nfreeRegsType (int type)
178 if (type == REG_PTR) {
179 if ((nfr = nFreeRegs (type)) == 0)
180 return nFreeRegs (REG_GPR);
183 return nFreeRegs (type);
187 /*-----------------------------------------------------------------*/
188 /* allDefsOutOfRange - all definitions are out of a range */
189 /*-----------------------------------------------------------------*/
191 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
198 for (i = 0; i < defs->size; i++) {
201 if (bitVectBitValue (defs, i) &&
202 (ic = hTabItemWithKey (iCodehTab, i)) &&
203 (ic->seq >= fseq && ic->seq <= toseq))
211 /*-----------------------------------------------------------------*/
212 /* computeSpillable - given a point find the spillable live ranges */
213 /*-----------------------------------------------------------------*/
215 computeSpillable (iCode * ic)
219 /* spillable live ranges are those that are live at this
220 point . the following categories need to be subtracted
222 a) - those that are already spilt
223 b) - if being used by this one
224 c) - defined by this one */
226 spillable = bitVectCopy (ic->rlive);
227 spillable = bitVectCplAnd (spillable, _G.spiltSet); /* those already spilt */
228 spillable = bitVectCplAnd (spillable, ic->uses); /* used in this one */
229 bitVectUnSetBit (spillable, ic->defKey);
230 spillable = bitVectIntersect (spillable, _G.regAssigned);
235 /*-----------------------------------------------------------------*/
236 /* noSpilLoc - return true if a variable has no spil location */
237 /*-----------------------------------------------------------------*/
239 noSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
241 return (sym->usl.spillLoc ? 0 : 1);
244 /*-----------------------------------------------------------------*/
245 /* hasSpilLoc - will return 1 if the symbol has spil location */
246 /*-----------------------------------------------------------------*/
248 hasSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
250 return (sym->usl.spillLoc ? 1 : 0);
253 /*-----------------------------------------------------------------*/
254 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location */
255 /* but is not used as a pointer */
256 /*-----------------------------------------------------------------*/
258 hasSpilLocnoUptr (symbol * sym, eBBlock * ebp, iCode * ic)
260 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
263 /*-----------------------------------------------------------------*/
264 /* rematable - will return 1 if the remat flag is set */
265 /*-----------------------------------------------------------------*/
267 rematable (symbol * sym, eBBlock * ebp, iCode * ic)
272 /*-----------------------------------------------------------------*/
273 /* notUsedInBlock - not used in this block */
274 /*-----------------------------------------------------------------*/
276 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode * ic)
278 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
279 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq));
282 /*-----------------------------------------------------------------*/
283 /* notUsedInRemaining - not used or defined in remain of the block */
284 /*-----------------------------------------------------------------*/
286 notUsedInRemaining (symbol * sym, eBBlock * ebp, iCode * ic)
288 return ((usedInRemaining (operandFromSymbol (sym), ic) ? 0 : 1) &&
289 allDefsOutOfRange (sym->defs, ic->seq, ebp->lSeq));
292 /*-----------------------------------------------------------------*/
293 /* allLRs - return true for all */
294 /*-----------------------------------------------------------------*/
296 allLRs (symbol * sym, eBBlock * ebp, iCode * ic)
301 /*-----------------------------------------------------------------*/
302 /* liveRangesWith - applies function to a given set of live range */
303 /*-----------------------------------------------------------------*/
305 liveRangesWith (bitVect * lrs,
306 int (func) (symbol *, eBBlock *, iCode *),
307 eBBlock * ebp, iCode * ic)
312 if (!lrs || !lrs->size)
315 for (i = 1; i < lrs->size; i++) {
317 if (!bitVectBitValue (lrs, i))
320 /* if we don't find it in the live range
321 hash table we are in serious trouble */
322 if (!(sym = hTabItemWithKey (liveRanges, i))) {
323 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
324 "liveRangesWith could not find liveRange");
328 if (func (sym, ebp, ic)
329 && bitVectBitValue (_G.regAssigned,
330 sym->key)) addSetHead (&rset, sym);
337 /*-----------------------------------------------------------------*/
338 /* leastUsedLR - given a set determines which is the least used */
339 /*-----------------------------------------------------------------*/
341 leastUsedLR (set * sset)
343 symbol *sym = NULL, *lsym = NULL;
345 sym = lsym = setFirstItem (sset);
350 for (; lsym; lsym = setNextItem (sset)) {
352 /* if usage is the same then prefer
353 the spill the smaller of the two */
354 if (lsym->used == sym->used)
355 if (getSize (lsym->type) < getSize (sym->type))
359 if (lsym->used < sym->used)
364 setToNull ((void **) &sset);
369 /*-----------------------------------------------------------------*/
370 /* noOverLap - will iterate through the list looking for over lap */
371 /*-----------------------------------------------------------------*/
373 noOverLap (set * itmpStack, symbol * fsym)
378 for (sym = setFirstItem (itmpStack); sym;
379 sym = setNextItem (itmpStack)) {
380 if (sym->liveTo > fsym->liveFrom)
388 /*-----------------------------------------------------------------*/
389 /* isFree - will return 1 if the a free spil location is found */
390 /*-----------------------------------------------------------------*/
395 V_ARG (symbol **, sloc);
396 V_ARG (symbol *, fsym);
398 /* if already found */
402 /* if it is free && and the itmp assigned to
403 this does not have any overlapping live ranges
404 with the one currently being assigned and
405 the size can be accomodated */
407 noOverLap (sym->usl.itmpStack, fsym) &&
408 getSize (sym->type) >= getSize (fsym->type)) {
416 /*-----------------------------------------------------------------*/
417 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
418 /*-----------------------------------------------------------------*/
420 spillLRWithPtrReg (symbol * forSym)
423 regs *X, *Z, *X1, *Z1;
426 if (!_G.regAssigned || bitVectIsZero (_G.regAssigned))
429 X = avr_regWithIdx (R26_IDX);
430 X1= avr_regWithIdx (R27_IDX);
431 Z = avr_regWithIdx (R30_IDX);
432 Z1= avr_regWithIdx (R31_IDX);
434 /* for all live ranges */
435 for (lrsym = hTabFirstItem (liveRanges, &k); lrsym;
436 lrsym = hTabNextItem (liveRanges, &k)) {
439 /* if no registers assigned to it or
441 /* if it does not overlap with this then
442 not need to spill it */
444 if (lrsym->isspilt || !lrsym->nRegs ||
445 (lrsym->liveTo < forSym->liveFrom)) continue;
447 /* go thru the registers : if it is either
448 r0 or r1 then spil it */
449 for (j = 0; j < lrsym->nRegs; j++)
450 if (lrsym->regs[j] == X || lrsym->regs[j] == Z ||
451 lrsym->regs[j] == X1 || lrsym->regs[j] == Z1) {
459 /*-----------------------------------------------------------------*/
460 /* createStackSpil - create a location on the stack to spil */
461 /*-----------------------------------------------------------------*/
463 createStackSpil (symbol * sym)
466 int useXstack, model, noOverlay;
471 /* first go try and find a free one that is already
472 existing on the stack */
473 if (applyToSet (_G.stackSpil, isFree, &sloc, sym)) {
474 /* found a free one : just update & return */
475 sym->usl.spillLoc = sloc;
478 addSetHead (&sloc->usl.itmpStack, sym);
482 /* could not then have to create one , this is the hard part
483 we need to allocate this on the stack : this is really a
484 hack!! but cannot think of anything better at this time */
486 if (sprintf (slocBuffer, "sloc%d", _G.slocNum++) >=
487 sizeof (slocBuffer)) {
489 "***Internal error: slocBuffer overflowed: %s:%d\n",
494 sloc = newiTemp (slocBuffer);
496 /* set the type to the spilling symbol */
497 sloc->type = copyLinkChain (sym->type);
498 sloc->etype = getSpec (sloc->type);
499 SPEC_SCLS (sloc->etype) = S_AUTO;
500 SPEC_EXTR (sloc->etype) = 0;
502 /* we don't allow it to be allocated`
503 onto the external stack since : so we
504 temporarily turn it off ; we also
505 turn off memory model to prevent
506 the spil from going to the external storage
507 and turn off overlaying
510 useXstack = options.useXstack;
511 model = options.model;
512 noOverlay = options.noOverlay;
513 stackAuto = options.stackAuto;
514 options.noOverlay = 1;
515 options.model = options.useXstack = 0;
519 options.useXstack = useXstack;
520 options.model = model;
521 options.noOverlay = noOverlay;
522 options.stackAuto = stackAuto;
523 sloc->isref = 1; /* to prevent compiler warning */
525 /* if it is on the stack then update the stack */
526 if (IN_STACK (sloc->etype)) {
527 currFunc->stack += getSize (sloc->type);
528 _G.stackExtend += getSize (sloc->type);
531 _G.dataExtend += getSize (sloc->type);
533 /* add it to the _G.stackSpil set */
534 addSetHead (&_G.stackSpil, sloc);
535 sym->usl.spillLoc = sloc;
538 /* add it to the set of itempStack set
539 of the spill location */
540 addSetHead (&sloc->usl.itmpStack, sym);
544 /*-----------------------------------------------------------------*/
545 /* isSpiltOnStack - returns true if the spil location is on stack */
546 /*-----------------------------------------------------------------*/
548 isSpiltOnStack (symbol * sym)
559 if (!sym->usl.spillLoc)
562 etype = getSpec (sym->usl.spillLoc->type);
563 if (IN_STACK (etype))
569 /*-----------------------------------------------------------------*/
570 /* spillThis - spils a specific operand */
571 /*-----------------------------------------------------------------*/
573 spillThis (symbol * sym)
576 /* if this is rematerializable or has a spillLocation
577 we are okay, else we need to create a spillLocation
579 if (!(sym->remat || sym->usl.spillLoc))
580 createStackSpil (sym);
583 /* mark it has spilt & put it in the spilt set */
585 _G.spiltSet = bitVectSetBit (_G.spiltSet, sym->key);
587 bitVectUnSetBit (_G.regAssigned, sym->key);
589 for (i = 0; i < sym->nRegs; i++)
592 freeReg (sym->regs[i]);
596 if (sym->usl.spillLoc && !sym->remat)
597 sym->usl.spillLoc->allocreq = 1;
601 /*-----------------------------------------------------------------*/
602 /* selectSpil - select a iTemp to spil : rather a simple procedure */
603 /*-----------------------------------------------------------------*/
605 selectSpil (iCode * ic, eBBlock * ebp, symbol * forSym)
607 bitVect *lrcs = NULL;
611 /* get the spillable live ranges */
612 lrcs = computeSpillable (ic);
614 /* get all live ranges that are rematerizable */
615 if ((selectS = liveRangesWith (lrcs, rematable, ebp, ic))) {
617 /* return the least used of these */
618 return leastUsedLR (selectS);
621 /* if the symbol is local to the block then */
622 if (forSym->liveTo < ebp->lSeq) {
624 /* check if there are any live ranges allocated
625 to registers that are not used in this block */
628 liveRangesWith (lrcs, notUsedInBlock, ebp, ic))) {
629 sym = leastUsedLR (selectS);
630 /* if this is not rematerializable */
638 /* check if there are any live ranges that not
639 used in the remainder of the block */
642 liveRangesWith (lrcs, notUsedInRemaining, ebp, ic))) {
643 sym = leastUsedLR (selectS);
654 /* find live ranges with spillocation && not used as pointers */
655 if ((selectS = liveRangesWith (lrcs, hasSpilLocnoUptr, ebp, ic))) {
657 sym = leastUsedLR (selectS);
658 /* mark this as allocation required */
659 sym->usl.spillLoc->allocreq = 1;
663 /* find live ranges with spillocation */
664 if ((selectS = liveRangesWith (lrcs, hasSpilLoc, ebp, ic))) {
666 sym = leastUsedLR (selectS);
667 sym->usl.spillLoc->allocreq = 1;
671 /* couldn't find then we need to create a spil
672 location on the stack , for which one? the least
674 if ((selectS = liveRangesWith (lrcs, noSpilLoc, ebp, ic))) {
676 /* return a created spil location */
677 sym = createStackSpil (leastUsedLR (selectS));
678 sym->usl.spillLoc->allocreq = 1;
682 /* this is an extreme situation we will spill
683 this one : happens very rarely but it does happen */
689 /*-----------------------------------------------------------------*/
690 /* spilSomething - spil some variable & mark registers as free */
691 /*-----------------------------------------------------------------*/
693 spilSomething (iCode * ic, eBBlock * ebp, symbol * forSym)
698 /* get something we can spil */
699 ssym = selectSpil (ic, ebp, forSym);
701 /* mark it as spilt */
703 _G.spiltSet = bitVectSetBit (_G.spiltSet, ssym->key);
705 /* mark it as not register assigned &
706 take it away from the set */
707 bitVectUnSetBit (_G.regAssigned, ssym->key);
709 /* mark the registers as free */
710 for (i = 0; i < ssym->nRegs; i++)
712 freeReg (ssym->regs[i]);
714 /* if this was a block level spil then insert push & pop
715 at the start & end of block respectively */
716 if (ssym->blockSpil) {
717 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
718 /* add push to the start of the block */
719 addiCodeToeBBlock (ebp, nic, (ebp->sch->op == LABEL ?
720 ebp->sch->next : ebp->sch));
721 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
722 /* add pop to the end of the block */
723 addiCodeToeBBlock (ebp, nic, NULL);
726 /* if spilt because not used in the remainder of the
727 block then add a push before this instruction and
728 a pop at the end of the block */
729 if (ssym->remainSpil) {
731 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
732 /* add push just before this instruction */
733 addiCodeToeBBlock (ebp, nic, ic);
735 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
736 /* add pop to the end of the block */
737 addiCodeToeBBlock (ebp, nic, NULL);
746 /*-----------------------------------------------------------------*/
747 /* getRegPtr - will try for PTR if not a GPR type if not spil */
748 /*-----------------------------------------------------------------*/
750 getRegPtr (iCode * ic, eBBlock * ebp, symbol * sym)
755 /* try for a ptr type */
756 if ((reg = allocReg (REG_PTR)))
759 /* try for gpr type */
760 if ((reg = allocReg (REG_GPR)))
763 /* we have to spil */
764 if (!spilSomething (ic, ebp, sym))
767 /* this looks like an infinite loop but
768 in reality selectSpil will abort */
772 /*-----------------------------------------------------------------*/
773 /* getRegScr - will try for SCR if not a GPR type if not spil */
774 /*-----------------------------------------------------------------*/
776 getRegScr (iCode * ic, eBBlock * ebp, symbol * sym)
781 /* try for a ptr type */
782 if ((reg = allocReg (REG_SCR)))
785 /* try for gpr type */
786 if ((reg = allocReg (REG_GPR)))
789 /* we have to spil */
790 if (!spilSomething (ic, ebp, sym))
793 /* this looks like an infinite loop but
794 in really selectSpil will abort */
798 /*-----------------------------------------------------------------*/
799 /* getRegGpr - will try for GPR if not spil */
800 /*-----------------------------------------------------------------*/
802 getRegGpr (iCode * ic, eBBlock * ebp, symbol * sym)
807 /* try for gpr type */
808 if ((reg = allocReg (REG_GPR)))
812 if ((reg = allocReg (REG_PTR)))
815 /* we have to spil */
816 if (!spilSomething (ic, ebp, sym))
819 /* this looks like an infinite loop but
820 in reality selectSpil will abort */
824 /*-----------------------------------------------------------------*/
825 /* symHasReg - symbol has a given register */
826 /*-----------------------------------------------------------------*/
828 symHasReg (symbol * sym, regs * reg)
832 for (i = 0; i < sym->nRegs; i++)
833 if (sym->regs[i] == reg)
839 /*-----------------------------------------------------------------*/
840 /* deassignLRs - check the live to and if they have registers & are */
841 /* not spilt then free up the registers */
842 /*-----------------------------------------------------------------*/
844 deassignLRs (iCode * ic, eBBlock * ebp)
850 for (sym = hTabFirstItem (liveRanges, &k); sym;
851 sym = hTabNextItem (liveRanges, &k)) {
854 /* if it does not end here */
855 if (sym->liveTo > ic->seq)
858 /* if it was spilt on stack then we can
859 mark the stack spil location as free */
861 if (sym->stackSpil) {
862 sym->usl.spillLoc->isFree = 1;
868 if (!bitVectBitValue (_G.regAssigned, sym->key))
871 /* special case check if this is an IFX &
872 the privious one was a pop and the
873 previous one was not spilt then keep track
875 if (ic->op == IFX && ic->prev &&
876 ic->prev->op == IPOP &&
877 !ic->prev->parmPush &&
878 !OP_SYMBOL (IC_LEFT (ic->prev))->isspilt)
879 psym = OP_SYMBOL (IC_LEFT (ic->prev));
884 bitVectUnSetBit (_G.regAssigned, sym->key);
886 /* if the result of this one needs registers
887 and does not have it then assign it right
889 if (IC_RESULT (ic) && !(SKIP_IC2 (ic) || /* not a special icode */
890 ic->op == JUMPTABLE ||
896 (result = OP_SYMBOL (IC_RESULT (ic))) && /* has a result */
897 result->liveTo > ic->seq && /* and will live beyond this */
898 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
899 result->regType == sym->regType && /* same register types */
900 result->nRegs && /* which needs registers */
901 !result->isspilt && /* and does not already have them */
903 !bitVectBitValue (_G.regAssigned, result->key) &&
904 /* the number of free regs + number of regs in this LR
905 can accomodate the what result Needs */
906 ((nfreeRegsType (result->regType) +
907 sym->nRegs) >= result->nRegs)) {
909 for (i = 0; i < result->nRegs; i++)
913 else if (result->regType == REG_SCR)
923 bitVectSetBit (_G.regAssigned,
928 /* free the remaining */
929 for (; i < sym->nRegs; i++) {
931 if (!symHasReg (psym, sym->regs[i]))
932 freeReg (sym->regs[i]);
935 freeReg (sym->regs[i]);
942 /*-----------------------------------------------------------------*/
943 /* reassignLR - reassign this to registers */
944 /*-----------------------------------------------------------------*/
946 reassignLR (operand * op)
948 symbol *sym = OP_SYMBOL (op);
951 /* not spilt any more */
952 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
953 bitVectUnSetBit (_G.spiltSet, sym->key);
955 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
959 for (i = 0; i < sym->nRegs; i++)
960 sym->regs[i]->isFree = 0;
963 /*-----------------------------------------------------------------*/
964 /* willCauseSpill - determines if allocating will cause a spill */
965 /*-----------------------------------------------------------------*/
967 willCauseSpill (int nr, int rt)
969 /* first check if there are any avlb registers
970 of te type required */
972 /* special case for pointer type
973 if pointer type not avlb then
974 check for type gpr */
975 if (nFreeRegs (rt) >= nr)
977 if (nFreeRegs (REG_GPR) >= nr)
982 if (nFreeRegs (rt) >= nr)
986 if (nFreeRegs (REG_PTR) + nFreeRegs (REG_GPR) >= nr)
991 /* it will cause a spil */
995 /*-----------------------------------------------------------------*/
996 /* makeRegPair - if two registers then try to make a pair */
997 /*-----------------------------------------------------------------*/
998 static void makeRegPair (operand *op)
1000 symbol *opsym = OP_SYMBOL(op);
1002 if (opsym->isspilt || opsym->nRegs != 2)
1004 if ((opsym->regs[0] - opsym->regs[1]) == 1) {
1005 regs *tmp = opsym->regs[0];
1006 opsym->regs[0] = opsym->regs[1];
1007 opsym->regs[1] = tmp;
1011 /*-----------------------------------------------------------------*/
1012 /* positionRegs - the allocator can allocate same registers to res- */
1013 /* ult and operand, if this happens make sure they are in the same */
1014 /* position as the operand otherwise chaos results */
1015 /*-----------------------------------------------------------------*/
1017 positionRegs (symbol * result, symbol * opsym, int lineno)
1019 int count = min (result->nRegs, opsym->nRegs);
1020 int i, j = 0, shared = 0;
1022 /* if the result has been spilt then cannot share */
1027 /* first make sure that they actually share */
1028 for (i = 0; i < count; i++) {
1029 for (j = 0; j < count; j++) {
1030 if (result->regs[i] == opsym->regs[j] && i != j) {
1038 regs *tmp = result->regs[i];
1039 result->regs[i] = result->regs[j];
1040 result->regs[j] = tmp;
1045 /*-----------------------------------------------------------------*/
1046 /* serialRegAssign - serially allocate registers to the variables */
1047 /*-----------------------------------------------------------------*/
1049 serialRegAssign (eBBlock ** ebbs, int count)
1053 /* for all blocks */
1054 for (i = 0; i < count; i++) {
1058 if (ebbs[i]->noPath &&
1059 (ebbs[i]->entryLabel != entryLabel &&
1060 ebbs[i]->entryLabel != returnLabel))
1063 /* of all instructions do */
1064 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1066 /* if this is an ipop that means some live
1067 range will have to be assigned again */
1069 reassignLR (IC_LEFT (ic));
1071 /* if result is present && is a true symbol */
1072 if (IC_RESULT (ic) && ic->op != IFX &&
1073 IS_TRUE_SYMOP (IC_RESULT (ic)))
1074 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
1076 /* take away registers from live
1077 ranges that end at this instruction */
1078 deassignLRs (ic, ebbs[i]);
1080 /* some don't need registers */
1081 if (SKIP_IC2 (ic) ||
1082 ic->op == JUMPTABLE ||
1086 (IC_RESULT (ic) && POINTER_SET (ic))) continue;
1088 /* now we need to allocate registers
1089 only for the result */
1090 if (IC_RESULT (ic)) {
1091 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1096 /* if it does not need or is spilt
1097 or is already assigned to registers
1098 or will not live beyond this instructions */
1101 bitVectBitValue (_G.regAssigned, sym->key)
1102 || sym->liveTo <= ic->seq)
1105 /* if some liverange has been spilt at the block level
1106 and this one live beyond this block then spil this
1109 && sym->liveTo > ebbs[i]->lSeq) {
1113 /* if trying to allocate this will cause
1114 a spill and there is nothing to spill
1115 or this one is rematerializable then
1118 willCauseSpill (sym->nRegs,
1120 spillable = computeSpillable (ic);
1122 (willCS && bitVectIsZero (spillable))) {
1129 /* if it has a spillocation & is used less than
1130 all other live ranges then spill this */
1131 if (willCS && sym->usl.spillLoc) {
1134 leastUsedLR (liveRangesWith
1140 leastUsed->used > sym->used) {
1146 /* we assign registers to it */
1147 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1149 for (j = 0; j < sym->nRegs; j++) {
1150 if (sym->regType == REG_PTR)
1151 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1152 else if (sym->regType == REG_SCR)
1153 sym->regs[j] = getRegScr (ic, ebbs[i], sym);
1155 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1157 /* if the allocation falied which means
1158 this was spilt then break */
1162 /* make the registers a pair */
1163 makeRegPair(IC_RESULT(ic));
1165 /* if it shares registers with operands make sure
1166 that they are in the same position */
1167 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1168 OP_SYMBOL (IC_LEFT (ic))->nRegs
1170 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1174 /* do the same for the right operand */
1175 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))
1176 && OP_SYMBOL (IC_RIGHT (ic))->nRegs)
1177 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1187 /*-----------------------------------------------------------------*/
1188 /* rUmaskForOp :- returns register mask for an operand */
1189 /*-----------------------------------------------------------------*/
1191 rUmaskForOp (operand * op)
1197 /* only temporaries are assigned registers */
1201 sym = OP_SYMBOL (op);
1203 /* if spilt or no registers assigned to it
1205 if (sym->isspilt || !sym->nRegs)
1208 rumask = newBitVect (avr_nRegs);
1210 for (j = 0; j < sym->nRegs; j++) {
1211 rumask = bitVectSetBit (rumask, sym->regs[j]->rIdx);
1217 /*-----------------------------------------------------------------*/
1218 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1219 /*-----------------------------------------------------------------*/
1221 regsUsedIniCode (iCode * ic)
1223 bitVect *rmask = newBitVect (avr_nRegs);
1225 /* do the special cases first */
1226 if (ic->op == IFX) {
1227 rmask = bitVectUnion (rmask, rUmaskForOp (IC_COND (ic)));
1231 /* for the jumptable */
1232 if (ic->op == JUMPTABLE) {
1233 rmask = bitVectUnion (rmask, rUmaskForOp (IC_JTCOND (ic)));
1238 /* of all other cases */
1240 rmask = bitVectUnion (rmask, rUmaskForOp (IC_LEFT (ic)));
1244 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RIGHT (ic)));
1247 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RESULT (ic)));
1253 /*-----------------------------------------------------------------*/
1254 /* createRegMask - for each instruction will determine the regsUsed */
1255 /*-----------------------------------------------------------------*/
1257 createRegMask (eBBlock ** ebbs, int count)
1261 /* for all blocks */
1262 for (i = 0; i < count; i++) {
1265 if (ebbs[i]->noPath &&
1266 (ebbs[i]->entryLabel != entryLabel &&
1267 ebbs[i]->entryLabel != returnLabel))
1270 /* for all instructions */
1271 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1275 if (SKIP_IC2 (ic) || !ic->rlive)
1278 /* first mark the registers used in this
1280 ic->rUsed = regsUsedIniCode (ic);
1281 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1283 /* now create the register mask for those
1284 registers that are in use : this is a
1285 super set of ic->rUsed */
1286 ic->rMask = newBitVect (avr_nRegs + 1);
1288 /* for all live Ranges alive at this point */
1289 for (j = 1; j < ic->rlive->size; j++) {
1293 /* if not alive then continue */
1294 if (!bitVectBitValue (ic->rlive, j))
1297 /* find the live range we are interested in */
1298 if (!(sym = hTabItemWithKey (liveRanges, j))) {
1299 werror (E_INTERNAL_ERROR, __FILE__,
1301 "createRegMask cannot find live range");
1305 /* if no register assigned to it */
1306 if (!sym->nRegs || sym->isspilt)
1309 /* for all the registers allocated to it */
1310 for (k = 0; k < sym->nRegs; k++) {
1312 ic->rMask = bitVectSetBit (ic-> rMask, sym->regs[k]->rIdx);
1313 /* special case for X & Z registers */
1314 if (k == R26_IDX || k == R27_IDX)
1315 ic->rMask = bitVectSetBit (ic->rMask, X_IDX);
1316 if (k == R30_IDX || k == R31_IDX)
1317 ic->rMask = bitVectSetBit (ic->rMask, Z_IDX);
1325 /*-----------------------------------------------------------------*/
1326 /* rematStr - returns the rematerialized string for a remat var */
1327 /*-----------------------------------------------------------------*/
1329 rematStr (symbol * sym)
1332 iCode *ic = sym->rematiCode;
1336 /* if plus or minus print the right hand side */
1337 if (ic->op == '+' || ic->op == '-') {
1338 sprintf (s, "0x%04x %c ",
1339 (int) operandLitValue (IC_RIGHT (ic)),
1342 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1346 /* we reached the end */
1347 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1354 /*-----------------------------------------------------------------*/
1355 /* regTypeNum - computes the type & number of registers required */
1356 /*-----------------------------------------------------------------*/
1364 /* for each live range do */
1365 for (sym = hTabFirstItem (liveRanges, &k); sym;
1366 sym = hTabNextItem (liveRanges, &k)) {
1368 /* if used zero times then no registers needed */
1369 if ((sym->liveTo - sym->liveFrom) == 0)
1373 /* if the live range is a temporary */
1376 /* if the type is marked as a conditional */
1377 if (sym->regType == REG_CND)
1380 /* if used in return only then we don't
1382 if (sym->ruonly || sym->accuse) {
1383 if (IS_AGGREGATE (sym->type) || sym->isptr)
1385 aggrToPtr (sym->type, FALSE);
1389 /* if the symbol has only one definition &
1390 that definition is a get_pointer and the
1391 pointer we are getting is rematerializable and
1394 if (bitVectnBitsOn (sym->defs) == 1 &&
1395 (ic = hTabItemWithKey (iCodehTab,
1396 bitVectFirstBit (sym->
1398 && POINTER_GET (ic) && !IS_BITVAR (sym->etype)) {
1400 /* if in data space or idata space then try to
1401 allocate pointer register */
1405 /* if not then we require registers */
1407 ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1408 getSize (sym->type =
1409 aggrToPtr (sym->type,
1410 FALSE)) : getSize (sym->
1413 if (sym->nRegs > 4) {
1415 "allocated more than 4 or 0 registers for type ");
1416 printTypeChain (sym->type, stderr);
1417 fprintf (stderr, "\n");
1420 /* determine the type of register required */
1421 if (sym->nRegs == 2 && /* size is two */
1422 IS_PTR (sym->type) && /* is a pointer */
1423 sym->uptr) { /* has pointer usage i.e. get/set pointer */
1424 sym->regType = REG_PTR;
1428 /* live accross a function call then gpr else scratch */
1429 if (sym->isLiveFcall)
1430 sym->regType = REG_GPR;
1432 sym->regType = REG_SCR;
1436 /* for the first run we don't provide */
1437 /* registers for true symbols we will */
1438 /* see how things go */
1444 /*-----------------------------------------------------------------*/
1445 /* deallocStackSpil - this will set the stack pointer back */
1446 /*-----------------------------------------------------------------*/
1448 DEFSETFUNC (deallocStackSpil)
1456 /*-----------------------------------------------------------------*/
1457 /* farSpacePackable - returns the packable icode for far variables */
1458 /*-----------------------------------------------------------------*/
1460 farSpacePackable (iCode * ic)
1464 /* go thru till we find a definition for the
1465 symbol on the right */
1466 for (dic = ic->prev; dic; dic = dic->prev) {
1468 /* if the definition is a call then no */
1469 if ((dic->op == CALL || dic->op == PCALL) &&
1470 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1474 /* if shift by unknown amount then not */
1475 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1476 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1479 /* if pointer get and size > 1 */
1480 if (POINTER_GET (dic) &&
1481 getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) >
1484 if (POINTER_SET (dic) &&
1485 getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE))
1489 /* if any three is a true symbol in far space */
1490 if (IC_RESULT (dic) &&
1491 IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1492 isOperandInFarSpace (IC_RESULT (dic)))
1495 if (IC_RIGHT (dic) &&
1496 IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
1497 isOperandInFarSpace (IC_RIGHT (dic)) &&
1498 !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
1501 if (IC_LEFT (dic) &&
1502 IS_TRUE_SYMOP (IC_LEFT (dic)) &&
1503 isOperandInFarSpace (IC_LEFT (dic)) &&
1504 !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
1507 if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic))) {
1508 if ((dic->op == LEFT_OP ||
1509 dic->op == RIGHT_OP ||
1511 IS_OP_LITERAL (IC_RIGHT (dic))) return NULL;
1520 /*-----------------------------------------------------------------*/
1521 /* packRegsForAssign - register reduction for assignment */
1522 /*-----------------------------------------------------------------*/
1524 packRegsForAssign (iCode * ic, eBBlock * ebp)
1528 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1529 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1530 OP_LIVETO (IC_RIGHT (ic)) > ic->seq) {
1534 /* find the definition of iTempNN scanning backwards if we find a
1535 a use of the true symbol in before we find the definition then
1537 for (dic = ic->prev; dic; dic = dic->prev) {
1539 /* if there is a function call and this is
1540 a parameter & not my parameter then don't pack it */
1541 if ((dic->op == CALL || dic->op == PCALL) &&
1542 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1543 !OP_SYMBOL (IC_RESULT (ic))->ismyparm)) {
1551 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1552 IS_OP_VOLATILE (IC_RESULT (dic))) {
1557 if (IS_SYMOP (IC_RESULT (dic)) &&
1558 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1559 if (POINTER_SET (dic))
1565 if (IS_SYMOP (IC_RIGHT (dic)) &&
1566 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1567 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key)) {
1572 if (IS_SYMOP (IC_LEFT (dic)) &&
1573 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1574 IC_LEFT (dic)->key == IC_RIGHT (ic)->key)) {
1579 if (POINTER_SET (dic) &&
1580 IC_RESULT (dic)->key == IC_RESULT (ic)->key) {
1587 return 0; /* did not find */
1589 /* if the result is on stack or iaccess then it must be
1590 the same atleast one of the operands */
1591 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1592 OP_SYMBOL (IC_RESULT (ic))->iaccess) {
1594 /* the operation has only one symbol
1595 operator then we can pack */
1596 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1597 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1600 if (!((IC_LEFT (dic) &&
1601 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1603 IC_RESULT (ic)->key == IC_RIGHT (dic)->key))) return 0;
1606 /* if in far space & tru symbol then don't */
1607 if ((IS_TRUE_SYMOP (IC_RESULT (ic)))
1608 && isOperandInFarSpace (IC_RESULT (ic))) return 0;
1609 /* found the definition */
1610 /* replace the result with the result of */
1611 /* this assignment and remove this assignment */
1612 IC_RESULT (dic) = IC_RESULT (ic);
1614 if (IS_ITEMP (IC_RESULT (dic))
1615 && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq) {
1616 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1618 /* delete from liverange table also
1619 delete from all the points inbetween and the new
1621 for (sic = dic; sic != ic; sic = sic->next) {
1622 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1623 if (IS_ITEMP (IC_RESULT (dic)))
1624 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1627 remiCodeFromeBBlock (ebp, ic);
1628 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1633 /*-----------------------------------------------------------------*/
1634 /* findAssignToSym : scanning backwards looks for first assig found */
1635 /*-----------------------------------------------------------------*/
1637 findAssignToSym (operand * op, iCode * ic)
1641 for (dic = ic->prev; dic; dic = dic->prev) {
1643 /* if definition by assignment */
1644 if (dic->op == '=' &&
1645 !POINTER_SET (dic) && IC_RESULT (dic)->key == op->key
1646 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1649 /* we are interested only if defined in far space */
1650 /* or in stack space in case of + & - */
1652 /* if assigned to a non-symbol then return
1654 if (!IS_SYMOP (IC_RIGHT (dic)))
1657 /* if the symbol is in far space then
1659 if (isOperandInFarSpace (IC_RIGHT (dic)))
1662 /* for + & - operations make sure that
1663 if it is on the stack it is the same
1664 as one of the three operands */
1665 if ((ic->op == '+' || ic->op == '-') &&
1666 OP_SYMBOL (IC_RIGHT (dic))->onStack) {
1668 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key
1669 && IC_LEFT (ic)->key !=
1671 && IC_RIGHT (ic)->key !=
1672 IC_RIGHT (dic)->key) return NULL;
1679 /* if we find an usage then we cannot delete it */
1680 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
1683 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
1686 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
1690 /* now make sure that the right side of dic
1691 is not defined between ic & dic */
1693 iCode *sic = dic->next;
1695 for (; sic != ic; sic = sic->next)
1696 if (IC_RESULT (sic) &&
1697 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
1706 /*-----------------------------------------------------------------*/
1707 /* packRegsForSupport :- reduce some registers for support calls */
1708 /*-----------------------------------------------------------------*/
1710 packRegsForSupport (iCode * ic, eBBlock * ebp)
1713 /* for the left & right operand :- look to see if the
1714 left was assigned a true symbol in far space in that
1715 case replace them */
1716 if (IS_ITEMP (IC_LEFT (ic)) &&
1717 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq) {
1718 iCode *dic = findAssignToSym (IC_LEFT (ic), ic);
1724 /* found it we need to remove it from the
1726 for (sic = dic; sic != ic; sic = sic->next)
1727 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
1729 IC_LEFT (ic)->operand.symOperand =
1730 IC_RIGHT (dic)->operand.symOperand;
1731 IC_LEFT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1732 remiCodeFromeBBlock (ebp, dic);
1733 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1737 /* do the same for the right operand */
1740 IS_ITEMP (IC_RIGHT (ic)) &&
1741 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq) {
1742 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
1748 /* if this is a subtraction & the result
1749 is a true symbol in far space then don't pack */
1750 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic))) {
1752 getSpec (operandType (IC_RESULT (dic)));
1753 if (IN_FARSPACE (SPEC_OCLS (etype)))
1756 /* found it we need to remove it from the
1758 for (sic = dic; sic != ic; sic = sic->next)
1759 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
1761 IC_RIGHT (ic)->operand.symOperand =
1762 IC_RIGHT (dic)->operand.symOperand;
1763 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1765 remiCodeFromeBBlock (ebp, dic);
1766 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1773 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1776 /*-----------------------------------------------------------------*/
1777 /* packRegsForOneuse : - will reduce some registers for single Use */
1778 /*-----------------------------------------------------------------*/
1780 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1785 /* if returning a literal then do nothing */
1790 if (ic->op != RETURN)
1793 /* this routine will mark the a symbol as used in one
1794 instruction use only && if the defintion is local
1795 (ie. within the basic block) && has only one definition &&
1796 that definiion is either a return value from a
1797 function or does not contain any variables in
1799 uses = bitVectCopy (OP_USES (op));
1800 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1801 if (!bitVectIsZero (uses)) /* has other uses */
1804 /* if it has only one defintion */
1805 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1806 return NULL; /* has more than one definition */
1808 /* get the that definition */
1810 hTabItemWithKey (iCodehTab,
1811 bitVectFirstBit (OP_DEFS (op))))) return NULL;
1813 /* found the definition now check if it is local */
1814 if (dic->seq < ebp->fSeq || dic->seq > ebp->lSeq)
1815 return NULL; /* non-local */
1817 /* now check if it is the return from
1819 if (dic->op == CALL || dic->op == PCALL) {
1820 if (ic->op != SEND && ic->op != RETURN) {
1821 OP_SYMBOL (op)->ruonly = 1;
1828 /* otherwise check that the definition does
1829 not contain any symbols in far space */
1830 if (IS_OP_RUONLY (IC_LEFT (ic)) || IS_OP_RUONLY (IC_RIGHT (ic))) {
1834 /* if pointer set then make sure the pointer
1836 if (POINTER_SET (dic) &&
1837 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1840 if (POINTER_GET (dic) &&
1841 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1846 /* also make sure the intervenening instructions
1847 don't have any thing in far space */
1848 for (dic = dic->next; dic && dic != ic; dic = dic->next) {
1850 /* if there is an intervening function call then no */
1851 if (dic->op == CALL || dic->op == PCALL)
1853 /* if pointer set then make sure the pointer
1855 if (POINTER_SET (dic) &&
1856 !IS_DATA_PTR (aggrToPtr
1857 (operandType (IC_RESULT (dic)),
1858 FALSE))) return NULL;
1860 if (POINTER_GET (dic) &&
1861 !IS_DATA_PTR (aggrToPtr
1862 (operandType (IC_LEFT (dic)),
1863 FALSE))) return NULL;
1865 /* if address of & the result is remat the okay */
1866 if (dic->op == ADDRESS_OF &&
1867 OP_SYMBOL (IC_RESULT (dic))->remat) continue;
1869 /* if operand has size of three or more & this
1870 operation is a '*','/' or '%' then 'b' may
1872 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1873 getSize (operandType (op)) >= 3)
1876 /* if left or right or result is in far space */
1877 if (IS_OP_RUONLY (IC_LEFT (dic)) ||
1878 IS_OP_RUONLY (IC_RIGHT (dic)) ||
1879 IS_OP_RUONLY (IC_RESULT (dic))) {
1884 OP_SYMBOL (op)->ruonly = 1;
1889 /*-----------------------------------------------------------------*/
1890 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1891 /*-----------------------------------------------------------------*/
1893 isBitwiseOptimizable (iCode * ic)
1895 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
1896 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
1898 /* bitwise operations are considered optimizable
1899 under the following conditions (Jean-Louis VERN)
1911 if (IS_LITERAL (rtype) ||
1912 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
1918 /*-----------------------------------------------------------------*/
1919 /* packForPush - hueristics to reduce iCode for pushing */
1920 /*-----------------------------------------------------------------*/
1922 packForPush (iCode * ic, eBBlock * ebp)
1926 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
1929 /* must have only definition & one usage */
1930 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
1931 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
1934 /* find the definition */
1935 if (!(dic = hTabItemWithKey (iCodehTab,
1936 bitVectFirstBit (OP_DEFS
1940 if (dic->op != '=' || POINTER_SET (dic))
1943 /* we now we know that it has one & only one def & use
1944 and the that the definition is an assignment */
1945 IC_LEFT (ic) = IC_RIGHT (dic);
1947 remiCodeFromeBBlock (ebp, dic);
1948 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1951 /*-----------------------------------------------------------------*/
1952 /* packRegisters - does some transformations to reduce register */
1954 /*-----------------------------------------------------------------*/
1956 packRegisters (eBBlock * ebp)
1965 /* look for assignments of the form */
1966 /* iTempNN = TRueSym (someoperation) SomeOperand */
1968 /* TrueSym := iTempNN:1 */
1969 for (ic = ebp->sch; ic; ic = ic->next) {
1972 /* find assignment of the form TrueSym := iTempNN:1 */
1973 if (ic->op == '=' && !POINTER_SET (ic))
1974 change += packRegsForAssign (ic, ebp);
1981 for (ic = ebp->sch; ic; ic = ic->next) {
1983 /* if this is an itemp & result of a address of a true sym
1984 then mark this as rematerialisable */
1985 if (ic->op == ADDRESS_OF &&
1986 IS_ITEMP (IC_RESULT (ic)) &&
1987 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
1988 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
1989 !OP_SYMBOL (IC_LEFT (ic))->onStack) {
1991 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
1992 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
1993 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
1997 /* if straight assignment then carry remat flag if
1998 this is the only definition */
1999 if (ic->op == '=' &&
2000 !POINTER_SET (ic) &&
2001 IS_SYMOP (IC_RIGHT (ic)) &&
2002 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2003 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1) {
2005 OP_SYMBOL (IC_RESULT (ic))->remat =
2006 OP_SYMBOL (IC_RIGHT (ic))->remat;
2007 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2008 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2011 /* if this is a +/- operation with a rematerizable
2012 then mark this as rematerializable as well only
2013 if the literal value is within the range -255 and + 255
2014 the assembler cannot handle it other wise */
2015 if ((ic->op == '+' || ic->op == '-') &&
2016 (IS_SYMOP (IC_LEFT (ic)) &&
2017 IS_ITEMP (IC_RESULT (ic)) &&
2018 OP_SYMBOL (IC_LEFT (ic))->remat &&
2019 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2020 IS_OP_LITERAL (IC_RIGHT (ic)))) {
2022 int i = (int) operandLitValue (IC_RIGHT (ic));
2023 if (i < 255 && i > -255) {
2024 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2025 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2026 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc =
2031 /* mark the pointer usages */
2032 if (POINTER_SET (ic))
2033 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2035 if (POINTER_GET (ic))
2036 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2038 /* if the condition of an if instruction
2039 is defined in the previous instruction then
2040 mark the itemp as a conditional */
2041 if ((IS_CONDITIONAL (ic) ||
2042 ((ic->op == BITWISEAND ||
2045 isBitwiseOptimizable (ic))) &&
2046 ic->next && ic->next->op == IFX &&
2047 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2048 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq) {
2050 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2054 /* some cases the redundant moves can
2055 can be eliminated for return statements */
2056 if ((ic->op == RETURN || ic->op == SEND))
2057 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2059 /* if this is cast for intergral promotion then
2060 check if only use of the definition of the
2061 operand being casted/ if yes then replace
2062 the result of that arithmetic operation with
2063 this result and get rid of the cast */
2064 if (ic->op == CAST) {
2065 sym_link *fromType = operandType (IC_RIGHT (ic));
2066 sym_link *toType = operandType (IC_LEFT (ic));
2068 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2069 getSize (fromType) != getSize (toType) &&
2070 SPEC_USIGN (fromType) == SPEC_USIGN (toType)) {
2073 packRegsForOneuse (ic, IC_RIGHT (ic),
2076 if (IS_ARITHMETIC_OP (dic)) {
2079 remiCodeFromeBBlock (ebp, ic);
2080 hTabDeleteItem (&iCodehTab,
2087 OP_SYMBOL (IC_RIGHT (ic))->
2093 /* if the type from and type to are the same
2094 then if this is the only use then packit */
2095 if (checkType (operandType (IC_RIGHT (ic)),
2096 operandType (IC_LEFT (ic))) ==
2099 packRegsForOneuse (ic,
2105 remiCodeFromeBBlock (ebp, ic);
2106 hTabDeleteItem (&iCodehTab,
2118 /*-----------------------------------------------------------------*/
2119 /* preAssignParms - we have a leaf function preassign registers */
2120 /*-----------------------------------------------------------------*/
2122 preAssignParms (iCode * ic)
2125 /* look for receives and assign registers
2126 to the result of the receives */
2128 /* if it is a receive */
2129 if (ic->op == RECEIVE) {
2130 symbol *r = OP_SYMBOL (IC_RESULT (ic));
2131 int size = getSize (r->type);
2132 if (r->regType == REG_GPR || r->regType == REG_SCR) {
2135 r->regs[j++] = ®sAVR[i++];
2136 regsAVR[i - 1].isFree = 0;
2138 /* put in the regassigned vector */
2140 bitVectSetBit (_G.regAssigned,
2144 /* not a GPR then we should mark as free */
2146 regsAVR[i++].isFree = 1;
2152 /* mark anything remaining as free */
2153 while (i <= R23_IDX)
2154 regsAVR[i++].isFree = 1;
2157 /*-----------------------------------------------------------------*/
2158 /* setdefaultRegs - do setup stuff for register allocation */
2159 /*-----------------------------------------------------------------*/
2161 setDefaultRegs (eBBlock ** ebbs, int count)
2165 /* if no pointer registers required in this function
2166 then mark r26-27 & r30-r31 as GPR & free */
2167 regsAVR[R26_IDX].isFree =
2168 regsAVR[R27_IDX].isFree =
2169 regsAVR[R30_IDX].isFree = regsAVR[R31_IDX].isFree = 1;
2171 if (!avr_ptrRegReq) {
2172 regsAVR[R26_IDX].type =
2173 regsAVR[R27_IDX].type =
2174 regsAVR[R30_IDX].type =
2175 regsAVR[R31_IDX].type = REG_GPR;
2178 regsAVR[R26_IDX].type =
2179 regsAVR[R27_IDX].type =
2180 regsAVR[R30_IDX].type =
2181 regsAVR[R31_IDX].type = REG_PTR;
2184 /* registers 0-1 / 24-25 used as scratch */
2185 regsAVR[R0_IDX].isFree =
2186 regsAVR[R1_IDX].isFree =
2187 regsAVR[R24_IDX].isFree = regsAVR[R25_IDX].isFree = 0;
2189 /* if this has no function calls then we need
2190 to do something special
2191 a) pre-assign registers to parameters RECEIVE
2192 b) mark the remaining parameter regs as free */
2193 if (!currFunc->hasFcall) {
2194 /* mark the parameter regs as GPR */
2195 for (i = R16_IDX; i <= R23_IDX; i++) {
2196 regsAVR[i].type = REG_SCR;
2197 regsAVR[i].isFree = 1;
2199 preAssignParms (ebbs[0]->sch);
2203 /* otherwise mark them as free scratch */
2204 for (i = R16_IDX; i <= R23_IDX; i++) {
2205 regsAVR[i].type = REG_SCR;
2206 regsAVR[i].isFree = 1;
2210 /* Y - is not allocated (it is the stack frame) */
2211 regsAVR[R28_IDX].isFree = regsAVR[R28_IDX].isFree = 0;
2214 /*-----------------------------------------------------------------*/
2215 /* assignRegisters - assigns registers to each live range as need */
2216 /*-----------------------------------------------------------------*/
2218 avr_assignRegisters (eBBlock ** ebbs, int count)
2223 setToNull ((void *) &_G.funcrUsed);
2224 avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2226 /* change assignments this will remove some
2227 live ranges reducing some register pressure */
2228 for (i = 0; i < count; i++)
2229 packRegisters (ebbs[i]);
2231 if (options.dump_pack)
2232 dumpEbbsToFileExt (".dumppack", ebbs, count);
2234 /* first determine for each live range the number of
2235 registers & the type of registers required for each */
2238 /* setup the default registers */
2239 setDefaultRegs (ebbs, count);
2241 /* and serially allocate registers */
2242 serialRegAssign (ebbs, count);
2244 /* if stack was extended then tell the user */
2245 if (_G.stackExtend) {
2246 /* werror(W_TOOMANY_SPILS,"stack", */
2247 /* _G.stackExtend,currFunc->name,""); */
2251 if (_G.dataExtend) {
2252 /* werror(W_TOOMANY_SPILS,"data space", */
2253 /* _G.dataExtend,currFunc->name,""); */
2257 /* after that create the register mask
2258 for each of the instruction */
2259 createRegMask (ebbs, count);
2261 /* redo that offsets for stacked automatic variables */
2262 redoStackOffsets ();
2264 if (options.dump_rassgn)
2265 dumpEbbsToFileExt (".dumprassgn", ebbs, count);
2267 /* now get back the chain */
2268 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2272 /* for (; ic ; ic = ic->next) */
2273 /* piCode(ic,stdout); */
2274 /* free up any _G.stackSpil locations allocated */
2275 applyToSet (_G.stackSpil, deallocStackSpil);
2277 setToNull ((void **) &_G.stackSpil);
2278 setToNull ((void **) &_G.spiltSet);
2279 /* mark all registers as free */