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 really 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 /* positionRegs - the allocator can allocate same registers to res- */
997 /* ult and operand, if this happens make sure they are in the same */
998 /* position as the operand otherwise chaos results */
999 /*-----------------------------------------------------------------*/
1001 positionRegs (symbol * result, symbol * opsym, int lineno)
1003 int count = min (result->nRegs, opsym->nRegs);
1004 int i, j = 0, shared = 0;
1006 /* if the result has been spilt then cannot share */
1011 /* first make sure that they actually share */
1012 for (i = 0; i < count; i++) {
1013 for (j = 0; j < count; j++) {
1014 if (result->regs[i] == opsym->regs[j] && i != j) {
1022 regs *tmp = result->regs[i];
1023 result->regs[i] = result->regs[j];
1024 result->regs[j] = tmp;
1029 /*-----------------------------------------------------------------*/
1030 /* serialRegAssign - serially allocate registers to the variables */
1031 /*-----------------------------------------------------------------*/
1033 serialRegAssign (eBBlock ** ebbs, int count)
1037 /* for all blocks */
1038 for (i = 0; i < count; i++) {
1042 if (ebbs[i]->noPath &&
1043 (ebbs[i]->entryLabel != entryLabel &&
1044 ebbs[i]->entryLabel != returnLabel))
1047 /* of all instructions do */
1048 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1050 /* if this is an ipop that means some live
1051 range will have to be assigned again */
1053 reassignLR (IC_LEFT (ic));
1055 /* if result is present && is a true symbol */
1056 if (IC_RESULT (ic) && ic->op != IFX &&
1057 IS_TRUE_SYMOP (IC_RESULT (ic)))
1058 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
1060 /* take away registers from live
1061 ranges that end at this instruction */
1062 deassignLRs (ic, ebbs[i]);
1064 /* some don't need registers */
1065 if (SKIP_IC2 (ic) ||
1066 ic->op == JUMPTABLE ||
1070 (IC_RESULT (ic) && POINTER_SET (ic))) continue;
1072 /* now we need to allocate registers
1073 only for the result */
1074 if (IC_RESULT (ic)) {
1075 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1080 /* if it does not need or is spilt
1081 or is already assigned to registers
1082 or will not live beyond this instructions */
1085 bitVectBitValue (_G.regAssigned, sym->key)
1086 || sym->liveTo <= ic->seq)
1089 /* if some liverange has been spilt at the block level
1090 and this one live beyond this block then spil this
1093 && sym->liveTo > ebbs[i]->lSeq) {
1097 /* if trying to allocate this will cause
1098 a spill and there is nothing to spill
1099 or this one is rematerializable then
1102 willCauseSpill (sym->nRegs,
1104 spillable = computeSpillable (ic);
1106 (willCS && bitVectIsZero (spillable))) {
1113 /* if it has a spillocation & is used less than
1114 all other live ranges then spill this */
1115 if (willCS && sym->usl.spillLoc) {
1118 leastUsedLR (liveRangesWith
1124 leastUsed->used > sym->used) {
1130 /* we assign registers to it */
1131 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1133 for (j = 0; j < sym->nRegs; j++) {
1134 if (sym->regType == REG_PTR)
1135 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1136 else if (sym->regType == REG_SCR)
1137 sym->regs[j] = getRegScr (ic, ebbs[i], sym);
1139 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1141 /* if the allocation falied which means
1142 this was spilt then break */
1146 /* if it shares registers with operands make sure
1147 that they are in the same position */
1148 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1149 OP_SYMBOL (IC_LEFT (ic))->nRegs
1151 positionRegs (OP_SYMBOL
1156 /* do the same for the right operand */
1157 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))
1158 && OP_SYMBOL (IC_RIGHT (ic))->nRegs)
1159 positionRegs (OP_SYMBOL
1170 /*-----------------------------------------------------------------*/
1171 /* rUmaskForOp :- returns register mask for an operand */
1172 /*-----------------------------------------------------------------*/
1174 rUmaskForOp (operand * op)
1180 /* only temporaries are assigned registers */
1184 sym = OP_SYMBOL (op);
1186 /* if spilt or no registers assigned to it
1188 if (sym->isspilt || !sym->nRegs)
1191 rumask = newBitVect (avr_nRegs);
1193 for (j = 0; j < sym->nRegs; j++) {
1194 rumask = bitVectSetBit (rumask, sym->regs[j]->rIdx);
1200 /*-----------------------------------------------------------------*/
1201 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1202 /*-----------------------------------------------------------------*/
1204 regsUsedIniCode (iCode * ic)
1206 bitVect *rmask = newBitVect (avr_nRegs);
1208 /* do the special cases first */
1209 if (ic->op == IFX) {
1210 rmask = bitVectUnion (rmask, rUmaskForOp (IC_COND (ic)));
1214 /* for the jumptable */
1215 if (ic->op == JUMPTABLE) {
1216 rmask = bitVectUnion (rmask, rUmaskForOp (IC_JTCOND (ic)));
1221 /* of all other cases */
1223 rmask = bitVectUnion (rmask, rUmaskForOp (IC_LEFT (ic)));
1227 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RIGHT (ic)));
1230 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RESULT (ic)));
1236 /*-----------------------------------------------------------------*/
1237 /* createRegMask - for each instruction will determine the regsUsed */
1238 /*-----------------------------------------------------------------*/
1240 createRegMask (eBBlock ** ebbs, int count)
1244 /* for all blocks */
1245 for (i = 0; i < count; i++) {
1248 if (ebbs[i]->noPath &&
1249 (ebbs[i]->entryLabel != entryLabel &&
1250 ebbs[i]->entryLabel != returnLabel))
1253 /* for all instructions */
1254 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1258 if (SKIP_IC2 (ic) || !ic->rlive)
1261 /* first mark the registers used in this
1263 ic->rUsed = regsUsedIniCode (ic);
1264 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1266 /* now create the register mask for those
1267 registers that are in use : this is a
1268 super set of ic->rUsed */
1269 ic->rMask = newBitVect (avr_nRegs + 1);
1271 /* for all live Ranges alive at this point */
1272 for (j = 1; j < ic->rlive->size; j++) {
1276 /* if not alive then continue */
1277 if (!bitVectBitValue (ic->rlive, j))
1280 /* find the live range we are interested in */
1281 if (!(sym = hTabItemWithKey (liveRanges, j))) {
1282 werror (E_INTERNAL_ERROR, __FILE__,
1284 "createRegMask cannot find live range");
1288 /* if no register assigned to it */
1289 if (!sym->nRegs || sym->isspilt)
1292 /* for all the registers allocated to it */
1293 for (k = 0; k < sym->nRegs; k++) {
1295 ic->rMask = bitVectSetBit (ic-> rMask, sym->regs[k]->rIdx);
1296 /* special case for X & Z registers */
1297 if (k == R26_IDX || k == R27_IDX)
1298 ic->rMask = bitVectSetBit (ic->rMask, X_IDX);
1299 if (k == R30_IDX || k == R31_IDX)
1300 ic->rMask = bitVectSetBit (ic->rMask, Z_IDX);
1308 /*-----------------------------------------------------------------*/
1309 /* rematStr - returns the rematerialized string for a remat var */
1310 /*-----------------------------------------------------------------*/
1312 rematStr (symbol * sym)
1315 iCode *ic = sym->rematiCode;
1319 /* if plus or minus print the right hand side */
1320 if (ic->op == '+' || ic->op == '-') {
1321 sprintf (s, "0x%04x %c ",
1322 (int) operandLitValue (IC_RIGHT (ic)),
1325 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1329 /* we reached the end */
1330 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1337 /*-----------------------------------------------------------------*/
1338 /* regTypeNum - computes the type & number of registers required */
1339 /*-----------------------------------------------------------------*/
1347 /* for each live range do */
1348 for (sym = hTabFirstItem (liveRanges, &k); sym;
1349 sym = hTabNextItem (liveRanges, &k)) {
1351 /* if used zero times then no registers needed */
1352 if ((sym->liveTo - sym->liveFrom) == 0)
1356 /* if the live range is a temporary */
1359 /* if the type is marked as a conditional */
1360 if (sym->regType == REG_CND)
1363 /* if used in return only then we don't
1365 if (sym->ruonly || sym->accuse) {
1366 if (IS_AGGREGATE (sym->type) || sym->isptr)
1368 aggrToPtr (sym->type, FALSE);
1372 /* if the symbol has only one definition &
1373 that definition is a get_pointer and the
1374 pointer we are getting is rematerializable and
1377 if (bitVectnBitsOn (sym->defs) == 1 &&
1378 (ic = hTabItemWithKey (iCodehTab,
1379 bitVectFirstBit (sym->
1381 && POINTER_GET (ic) && !IS_BITVAR (sym->etype)) {
1383 /* if in data space or idata space then try to
1384 allocate pointer register */
1388 /* if not then we require registers */
1390 ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1391 getSize (sym->type =
1392 aggrToPtr (sym->type,
1393 FALSE)) : getSize (sym->
1396 if (sym->nRegs > 4) {
1398 "allocated more than 4 or 0 registers for type ");
1399 printTypeChain (sym->type, stderr);
1400 fprintf (stderr, "\n");
1403 /* determine the type of register required */
1404 if (sym->nRegs == 2 && /* size is two */
1405 IS_PTR (sym->type) && /* is a pointer */
1406 sym->uptr) { /* has pointer usage i.e. get/set pointer */
1407 sym->regType = REG_PTR;
1411 /* live accross a function call then gpr else scratch */
1412 if (sym->isLiveFcall)
1413 sym->regType = REG_GPR;
1415 sym->regType = REG_SCR;
1419 /* for the first run we don't provide */
1420 /* registers for true symbols we will */
1421 /* see how things go */
1427 /*-----------------------------------------------------------------*/
1428 /* deallocStackSpil - this will set the stack pointer back */
1429 /*-----------------------------------------------------------------*/
1431 DEFSETFUNC (deallocStackSpil)
1439 /*-----------------------------------------------------------------*/
1440 /* farSpacePackable - returns the packable icode for far variables */
1441 /*-----------------------------------------------------------------*/
1443 farSpacePackable (iCode * ic)
1447 /* go thru till we find a definition for the
1448 symbol on the right */
1449 for (dic = ic->prev; dic; dic = dic->prev) {
1451 /* if the definition is a call then no */
1452 if ((dic->op == CALL || dic->op == PCALL) &&
1453 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1457 /* if shift by unknown amount then not */
1458 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1459 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1462 /* if pointer get and size > 1 */
1463 if (POINTER_GET (dic) &&
1464 getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) >
1467 if (POINTER_SET (dic) &&
1468 getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE))
1472 /* if any three is a true symbol in far space */
1473 if (IC_RESULT (dic) &&
1474 IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1475 isOperandInFarSpace (IC_RESULT (dic)))
1478 if (IC_RIGHT (dic) &&
1479 IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
1480 isOperandInFarSpace (IC_RIGHT (dic)) &&
1481 !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
1484 if (IC_LEFT (dic) &&
1485 IS_TRUE_SYMOP (IC_LEFT (dic)) &&
1486 isOperandInFarSpace (IC_LEFT (dic)) &&
1487 !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
1490 if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic))) {
1491 if ((dic->op == LEFT_OP ||
1492 dic->op == RIGHT_OP ||
1494 IS_OP_LITERAL (IC_RIGHT (dic))) return NULL;
1503 /*-----------------------------------------------------------------*/
1504 /* packRegsForAssign - register reduction for assignment */
1505 /*-----------------------------------------------------------------*/
1507 packRegsForAssign (iCode * ic, eBBlock * ebp)
1511 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1512 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1513 OP_LIVETO (IC_RIGHT (ic)) > ic->seq) {
1517 /* find the definition of iTempNN scanning backwards if we find a
1518 a use of the true symbol in before we find the definition then
1520 for (dic = ic->prev; dic; dic = dic->prev) {
1522 /* if there is a function call and this is
1523 a parameter & not my parameter then don't pack it */
1524 if ((dic->op == CALL || dic->op == PCALL) &&
1525 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1526 !OP_SYMBOL (IC_RESULT (ic))->ismyparm)) {
1534 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1535 IS_OP_VOLATILE (IC_RESULT (dic))) {
1540 if (IS_SYMOP (IC_RESULT (dic)) &&
1541 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1542 if (POINTER_SET (dic))
1548 if (IS_SYMOP (IC_RIGHT (dic)) &&
1549 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1550 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key)) {
1555 if (IS_SYMOP (IC_LEFT (dic)) &&
1556 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1557 IC_LEFT (dic)->key == IC_RIGHT (ic)->key)) {
1562 if (POINTER_SET (dic) &&
1563 IC_RESULT (dic)->key == IC_RESULT (ic)->key) {
1570 return 0; /* did not find */
1572 /* if the result is on stack or iaccess then it must be
1573 the same atleast one of the operands */
1574 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1575 OP_SYMBOL (IC_RESULT (ic))->iaccess) {
1577 /* the operation has only one symbol
1578 operator then we can pack */
1579 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1580 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1583 if (!((IC_LEFT (dic) &&
1584 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1586 IC_RESULT (ic)->key == IC_RIGHT (dic)->key))) return 0;
1589 /* if in far space & tru symbol then don't */
1590 if ((IS_TRUE_SYMOP (IC_RESULT (ic)))
1591 && isOperandInFarSpace (IC_RESULT (ic))) return 0;
1592 /* found the definition */
1593 /* replace the result with the result of */
1594 /* this assignment and remove this assignment */
1595 IC_RESULT (dic) = IC_RESULT (ic);
1597 if (IS_ITEMP (IC_RESULT (dic))
1598 && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq) {
1599 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1601 /* delete from liverange table also
1602 delete from all the points inbetween and the new
1604 for (sic = dic; sic != ic; sic = sic->next) {
1605 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1606 if (IS_ITEMP (IC_RESULT (dic)))
1607 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1610 remiCodeFromeBBlock (ebp, ic);
1611 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1616 /*-----------------------------------------------------------------*/
1617 /* findAssignToSym : scanning backwards looks for first assig found */
1618 /*-----------------------------------------------------------------*/
1620 findAssignToSym (operand * op, iCode * ic)
1624 for (dic = ic->prev; dic; dic = dic->prev) {
1626 /* if definition by assignment */
1627 if (dic->op == '=' &&
1628 !POINTER_SET (dic) && IC_RESULT (dic)->key == op->key
1629 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1632 /* we are interested only if defined in far space */
1633 /* or in stack space in case of + & - */
1635 /* if assigned to a non-symbol then return
1637 if (!IS_SYMOP (IC_RIGHT (dic)))
1640 /* if the symbol is in far space then
1642 if (isOperandInFarSpace (IC_RIGHT (dic)))
1645 /* for + & - operations make sure that
1646 if it is on the stack it is the same
1647 as one of the three operands */
1648 if ((ic->op == '+' || ic->op == '-') &&
1649 OP_SYMBOL (IC_RIGHT (dic))->onStack) {
1651 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key
1652 && IC_LEFT (ic)->key !=
1654 && IC_RIGHT (ic)->key !=
1655 IC_RIGHT (dic)->key) return NULL;
1662 /* if we find an usage then we cannot delete it */
1663 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
1666 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
1669 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
1673 /* now make sure that the right side of dic
1674 is not defined between ic & dic */
1676 iCode *sic = dic->next;
1678 for (; sic != ic; sic = sic->next)
1679 if (IC_RESULT (sic) &&
1680 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
1689 /*-----------------------------------------------------------------*/
1690 /* packRegsForSupport :- reduce some registers for support calls */
1691 /*-----------------------------------------------------------------*/
1693 packRegsForSupport (iCode * ic, eBBlock * ebp)
1696 /* for the left & right operand :- look to see if the
1697 left was assigned a true symbol in far space in that
1698 case replace them */
1699 if (IS_ITEMP (IC_LEFT (ic)) &&
1700 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq) {
1701 iCode *dic = findAssignToSym (IC_LEFT (ic), ic);
1707 /* found it we need to remove it from the
1709 for (sic = dic; sic != ic; sic = sic->next)
1710 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
1712 IC_LEFT (ic)->operand.symOperand =
1713 IC_RIGHT (dic)->operand.symOperand;
1714 IC_LEFT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1715 remiCodeFromeBBlock (ebp, dic);
1716 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1720 /* do the same for the right operand */
1723 IS_ITEMP (IC_RIGHT (ic)) &&
1724 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq) {
1725 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
1731 /* if this is a subtraction & the result
1732 is a true symbol in far space then don't pack */
1733 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic))) {
1735 getSpec (operandType (IC_RESULT (dic)));
1736 if (IN_FARSPACE (SPEC_OCLS (etype)))
1739 /* found it we need to remove it from the
1741 for (sic = dic; sic != ic; sic = sic->next)
1742 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
1744 IC_RIGHT (ic)->operand.symOperand =
1745 IC_RIGHT (dic)->operand.symOperand;
1746 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1748 remiCodeFromeBBlock (ebp, dic);
1749 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1756 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1759 /*-----------------------------------------------------------------*/
1760 /* packRegsForOneuse : - will reduce some registers for single Use */
1761 /*-----------------------------------------------------------------*/
1763 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1768 /* if returning a literal then do nothing */
1773 if (ic->op != RETURN)
1776 /* this routine will mark the a symbol as used in one
1777 instruction use only && if the defintion is local
1778 (ie. within the basic block) && has only one definition &&
1779 that definiion is either a return value from a
1780 function or does not contain any variables in
1782 uses = bitVectCopy (OP_USES (op));
1783 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1784 if (!bitVectIsZero (uses)) /* has other uses */
1787 /* if it has only one defintion */
1788 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1789 return NULL; /* has more than one definition */
1791 /* get the that definition */
1793 hTabItemWithKey (iCodehTab,
1794 bitVectFirstBit (OP_DEFS (op))))) return NULL;
1796 /* found the definition now check if it is local */
1797 if (dic->seq < ebp->fSeq || dic->seq > ebp->lSeq)
1798 return NULL; /* non-local */
1800 /* now check if it is the return from
1802 if (dic->op == CALL || dic->op == PCALL) {
1803 if (ic->op != SEND && ic->op != RETURN) {
1804 OP_SYMBOL (op)->ruonly = 1;
1811 /* otherwise check that the definition does
1812 not contain any symbols in far space */
1813 if (IS_OP_RUONLY (IC_LEFT (ic)) || IS_OP_RUONLY (IC_RIGHT (ic))) {
1817 /* if pointer set then make sure the pointer
1819 if (POINTER_SET (dic) &&
1820 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1823 if (POINTER_GET (dic) &&
1824 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1829 /* also make sure the intervenening instructions
1830 don't have any thing in far space */
1831 for (dic = dic->next; dic && dic != ic; dic = dic->next) {
1833 /* if there is an intervening function call then no */
1834 if (dic->op == CALL || dic->op == PCALL)
1836 /* if pointer set then make sure the pointer
1838 if (POINTER_SET (dic) &&
1839 !IS_DATA_PTR (aggrToPtr
1840 (operandType (IC_RESULT (dic)),
1841 FALSE))) return NULL;
1843 if (POINTER_GET (dic) &&
1844 !IS_DATA_PTR (aggrToPtr
1845 (operandType (IC_LEFT (dic)),
1846 FALSE))) return NULL;
1848 /* if address of & the result is remat the okay */
1849 if (dic->op == ADDRESS_OF &&
1850 OP_SYMBOL (IC_RESULT (dic))->remat) continue;
1852 /* if operand has size of three or more & this
1853 operation is a '*','/' or '%' then 'b' may
1855 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1856 getSize (operandType (op)) >= 3)
1859 /* if left or right or result is in far space */
1860 if (IS_OP_RUONLY (IC_LEFT (dic)) ||
1861 IS_OP_RUONLY (IC_RIGHT (dic)) ||
1862 IS_OP_RUONLY (IC_RESULT (dic))) {
1867 OP_SYMBOL (op)->ruonly = 1;
1872 /*-----------------------------------------------------------------*/
1873 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1874 /*-----------------------------------------------------------------*/
1876 isBitwiseOptimizable (iCode * ic)
1878 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
1879 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
1881 /* bitwise operations are considered optimizable
1882 under the following conditions (Jean-Louis VERN)
1894 if (IS_LITERAL (rtype) ||
1895 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
1901 /*-----------------------------------------------------------------*/
1902 /* packForPush - hueristics to reduce iCode for pushing */
1903 /*-----------------------------------------------------------------*/
1905 packForPush (iCode * ic, eBBlock * ebp)
1909 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
1912 /* must have only definition & one usage */
1913 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
1914 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
1917 /* find the definition */
1918 if (!(dic = hTabItemWithKey (iCodehTab,
1919 bitVectFirstBit (OP_DEFS
1923 if (dic->op != '=' || POINTER_SET (dic))
1926 /* we now we know that it has one & only one def & use
1927 and the that the definition is an assignment */
1928 IC_LEFT (ic) = IC_RIGHT (dic);
1930 remiCodeFromeBBlock (ebp, dic);
1931 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1934 /*-----------------------------------------------------------------*/
1935 /* packRegisters - does some transformations to reduce register */
1937 /*-----------------------------------------------------------------*/
1939 packRegisters (eBBlock * ebp)
1948 /* look for assignments of the form */
1949 /* iTempNN = TRueSym (someoperation) SomeOperand */
1951 /* TrueSym := iTempNN:1 */
1952 for (ic = ebp->sch; ic; ic = ic->next) {
1955 /* find assignment of the form TrueSym := iTempNN:1 */
1956 if (ic->op == '=' && !POINTER_SET (ic))
1957 change += packRegsForAssign (ic, ebp);
1964 for (ic = ebp->sch; ic; ic = ic->next) {
1966 /* if this is an itemp & result of a address of a true sym
1967 then mark this as rematerialisable */
1968 if (ic->op == ADDRESS_OF &&
1969 IS_ITEMP (IC_RESULT (ic)) &&
1970 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
1971 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
1972 !OP_SYMBOL (IC_LEFT (ic))->onStack) {
1974 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
1975 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
1976 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
1980 /* if straight assignment then carry remat flag if
1981 this is the only definition */
1982 if (ic->op == '=' &&
1983 !POINTER_SET (ic) &&
1984 IS_SYMOP (IC_RIGHT (ic)) &&
1985 OP_SYMBOL (IC_RIGHT (ic))->remat &&
1986 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1) {
1988 OP_SYMBOL (IC_RESULT (ic))->remat =
1989 OP_SYMBOL (IC_RIGHT (ic))->remat;
1990 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
1991 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
1994 /* if this is a +/- operation with a rematerizable
1995 then mark this as rematerializable as well only
1996 if the literal value is within the range -255 and + 255
1997 the assembler cannot handle it other wise */
1998 if ((ic->op == '+' || ic->op == '-') &&
1999 (IS_SYMOP (IC_LEFT (ic)) &&
2000 IS_ITEMP (IC_RESULT (ic)) &&
2001 OP_SYMBOL (IC_LEFT (ic))->remat &&
2002 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2003 IS_OP_LITERAL (IC_RIGHT (ic)))) {
2005 int i = (int) operandLitValue (IC_RIGHT (ic));
2006 if (i < 255 && i > -255) {
2007 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2008 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2009 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc =
2014 /* mark the pointer usages */
2015 if (POINTER_SET (ic))
2016 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2018 if (POINTER_GET (ic))
2019 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2021 /* if the condition of an if instruction
2022 is defined in the previous instruction then
2023 mark the itemp as a conditional */
2024 if ((IS_CONDITIONAL (ic) ||
2025 ((ic->op == BITWISEAND ||
2028 isBitwiseOptimizable (ic))) &&
2029 ic->next && ic->next->op == IFX &&
2030 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2031 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq) {
2033 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2037 /* some cases the redundant moves can
2038 can be eliminated for return statements */
2039 if ((ic->op == RETURN || ic->op == SEND))
2040 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2042 /* if this is cast for intergral promotion then
2043 check if only use of the definition of the
2044 operand being casted/ if yes then replace
2045 the result of that arithmetic operation with
2046 this result and get rid of the cast */
2047 if (ic->op == CAST) {
2048 sym_link *fromType = operandType (IC_RIGHT (ic));
2049 sym_link *toType = operandType (IC_LEFT (ic));
2051 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2052 getSize (fromType) != getSize (toType) &&
2053 SPEC_USIGN (fromType) == SPEC_USIGN (toType)) {
2056 packRegsForOneuse (ic, IC_RIGHT (ic),
2059 if (IS_ARITHMETIC_OP (dic)) {
2062 remiCodeFromeBBlock (ebp, ic);
2063 hTabDeleteItem (&iCodehTab,
2070 OP_SYMBOL (IC_RIGHT (ic))->
2076 /* if the type from and type to are the same
2077 then if this is the only use then packit */
2078 if (checkType (operandType (IC_RIGHT (ic)),
2079 operandType (IC_LEFT (ic))) ==
2082 packRegsForOneuse (ic,
2088 remiCodeFromeBBlock (ebp, ic);
2089 hTabDeleteItem (&iCodehTab,
2101 /*-----------------------------------------------------------------*/
2102 /* preAssignParms - we have a leaf function preassign registers */
2103 /*-----------------------------------------------------------------*/
2105 preAssignParms (iCode * ic)
2108 /* look for receives and assign registers
2109 to the result of the receives */
2111 /* if it is a receive */
2112 if (ic->op == RECEIVE) {
2113 symbol *r = OP_SYMBOL (IC_RESULT (ic));
2114 int size = getSize (r->type);
2115 if (r->regType == REG_GPR || r->regType == REG_SCR) {
2118 r->regs[j++] = ®sAVR[i++];
2119 regsAVR[i - 1].isFree = 0;
2121 /* put in the regassigned vector */
2123 bitVectSetBit (_G.regAssigned,
2127 /* not a GPR then we should mark as free */
2129 regsAVR[i++].isFree = 1;
2135 /* mark anything remaining as free */
2136 while (i <= R23_IDX)
2137 regsAVR[i++].isFree = 1;
2140 /*-----------------------------------------------------------------*/
2141 /* setdefaultRegs - do setup stuff for register allocation */
2142 /*-----------------------------------------------------------------*/
2144 setDefaultRegs (eBBlock ** ebbs, int count)
2148 /* if no pointer registers required in this function
2149 then mark r26-27 & r30-r31 as GPR & free */
2150 regsAVR[R26_IDX].isFree =
2151 regsAVR[R27_IDX].isFree =
2152 regsAVR[R30_IDX].isFree = regsAVR[R31_IDX].isFree = 1;
2154 if (!avr_ptrRegReq) {
2155 regsAVR[R26_IDX].type =
2156 regsAVR[R27_IDX].type =
2157 regsAVR[R30_IDX].type =
2158 regsAVR[R31_IDX].type = REG_GPR;
2161 regsAVR[R26_IDX].type =
2162 regsAVR[R27_IDX].type =
2163 regsAVR[R30_IDX].type =
2164 regsAVR[R31_IDX].type = REG_PTR;
2167 /* registers 0-1 / 24-25 used as scratch */
2168 regsAVR[R0_IDX].isFree =
2169 regsAVR[R1_IDX].isFree =
2170 regsAVR[R24_IDX].isFree = regsAVR[R25_IDX].isFree = 0;
2172 /* if this has no function calls then we need
2173 to do something special
2174 a) pre-assign registers to parameters RECEIVE
2175 b) mark the remaining parameter regs as free */
2176 if (!currFunc->hasFcall) {
2177 /* mark the parameter regs as GPR */
2178 for (i = R16_IDX; i <= R23_IDX; i++) {
2179 regsAVR[i].type = REG_SCR;
2180 regsAVR[i].isFree = 1;
2182 preAssignParms (ebbs[0]->sch);
2186 /* otherwise mark them as free scratch */
2187 for (i = R16_IDX; i <= R23_IDX; i++) {
2188 regsAVR[i].type = REG_SCR;
2189 regsAVR[i].isFree = 1;
2193 /* Y - is not allocated (it is the stack frame) */
2194 regsAVR[R28_IDX].isFree = regsAVR[R28_IDX].isFree = 0;
2197 /*-----------------------------------------------------------------*/
2198 /* assignRegisters - assigns registers to each live range as need */
2199 /*-----------------------------------------------------------------*/
2201 avr_assignRegisters (eBBlock ** ebbs, int count)
2206 setToNull ((void *) &_G.funcrUsed);
2207 avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2209 /* change assignments this will remove some
2210 live ranges reducing some register pressure */
2211 for (i = 0; i < count; i++)
2212 packRegisters (ebbs[i]);
2214 if (options.dump_pack)
2215 dumpEbbsToFileExt (".dumppack", ebbs, count);
2217 /* first determine for each live range the number of
2218 registers & the type of registers required for each */
2221 /* setup the default registers */
2222 setDefaultRegs (ebbs, count);
2224 /* and serially allocate registers */
2225 serialRegAssign (ebbs, count);
2227 /* if stack was extended then tell the user */
2228 if (_G.stackExtend) {
2229 /* werror(W_TOOMANY_SPILS,"stack", */
2230 /* _G.stackExtend,currFunc->name,""); */
2234 if (_G.dataExtend) {
2235 /* werror(W_TOOMANY_SPILS,"data space", */
2236 /* _G.dataExtend,currFunc->name,""); */
2240 /* after that create the register mask
2241 for each of the instruction */
2242 createRegMask (ebbs, count);
2244 /* redo that offsets for stacked automatic variables */
2245 redoStackOffsets ();
2247 if (options.dump_rassgn)
2248 dumpEbbsToFileExt (".dumprassgn", ebbs, count);
2250 /* now get back the chain */
2251 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2255 /* for (; ic ; ic = ic->next) */
2256 /* piCode(ic,stdout); */
2257 /* free up any _G.stackSpil locations allocated */
2258 applyToSet (_G.stackSpil, deallocStackSpil);
2260 setToNull ((void **) &_G.stackSpil);
2261 setToNull ((void **) &_G.spiltSet);
2262 /* mark all registers as free */