1 /*------------------------------------------------------------------------
3 SDCCralloc.c - source file for register allocation. (ATMEL AVR) specific
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
7 This program is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 In other words, you are welcome to use, share and improve this program.
22 You are forbidden to forbid anyone else to use, share and improve
23 what you give them. Help stamp out software-hoarding!
24 -------------------------------------------------------------------------*/
30 /*-----------------------------------------------------------------*/
31 /* At this point we start getting processor specific although */
32 /* some routines are non-processor specific & can be reused when */
33 /* targetting other processors. The decision for this will have */
34 /* to be made on a routine by routine basis */
35 /* routines used to pack registers are most definitely not reusable */
36 /* since the pack the registers depending strictly on the MCU */
37 /*-----------------------------------------------------------------*/
39 extern void genAVRCode (iCode *);
48 bitVect *funcrUsed; /* registers used in a function */
53 /* Shared with gen.c */
54 int avr_ptrRegReq; /* pointer register required */
58 {REG_GPR|REG_PAIR, R0_IDX, REG_GPR|REG_PAIR, "r0", "r0", "", 0, 0, 0}, /* scratch */
59 {REG_GPR, R1_IDX, REG_GPR , "r1", "r1", "", 0, 0, 0}, /* scratch */
60 {REG_GPR|REG_PAIR, R2_IDX, REG_GPR|REG_PAIR, "r2", "r2", "", 0, 1, 1}, /* gpr */
61 {REG_GPR, R3_IDX, REG_GPR , "r3", "r3", "", 0, 1, 1}, /* gpr */
62 {REG_GPR|REG_PAIR, R4_IDX, REG_GPR|REG_PAIR, "r4", "r4", "", 0, 1, 1}, /* gpr */
63 {REG_GPR, R5_IDX, REG_GPR , "r5", "r5", "", 0, 1, 1}, /* gpr */
64 {REG_GPR|REG_PAIR, R6_IDX, REG_GPR|REG_PAIR, "r6", "r6", "", 0, 1, 1}, /* gpr */
65 {REG_GPR, R7_IDX, REG_GPR , "r7", "r7", "", 0, 1, 1}, /* gpr */
66 {REG_GPR|REG_PAIR, R8_IDX, REG_GPR|REG_PAIR, "r8", "r8", "", 0, 1, 1}, /* gpr */
67 {REG_GPR, R9_IDX, REG_GPR , "r9", "r9", "", 0, 1, 1}, /* gpr */
68 {REG_GPR|REG_PAIR, R10_IDX,REG_GPR|REG_PAIR, "r10", "r10","",0, 1, 1}, /* gpr */
69 {REG_GPR, R11_IDX,REG_GPR , "r11", "r11","",0, 1, 1}, /* gpr */
70 {REG_GPR|REG_PAIR, R12_IDX,REG_GPR|REG_PAIR, "r12", "r12","",0, 1, 1}, /* gpr */
71 {REG_GPR, R13_IDX,REG_GPR , "r13", "r13","",0, 1, 1}, /* gpr */
72 {REG_GPR|REG_PAIR, R14_IDX,REG_GPR|REG_PAIR, "r14", "r14","",0, 1, 1}, /* gpr */
73 {REG_GPR, R15_IDX,REG_GPR , "r15", "r15","",0, 1, 1}, /* gpr */
74 {REG_GPR|REG_PAIR, R16_IDX,REG_GPR|REG_PAIR, "r16", "r16","",0, 1, 0}, /* parm/gpr */
75 {REG_GPR, R17_IDX,REG_GPR , "r17", "r17","",0, 1, 0}, /* parm/gpr */
76 {REG_GPR|REG_PAIR, R18_IDX,REG_GPR|REG_PAIR, "r18", "r18","",0, 1, 0}, /* parm/gpr */
77 {REG_GPR, R19_IDX,REG_GPR , "r19", "r19","",0, 1, 0}, /* parm/gpr */
78 {REG_GPR|REG_PAIR, R20_IDX,REG_GPR|REG_PAIR, "r20", "r20","",0, 1, 0}, /* parm/gpr */
79 {REG_GPR, R21_IDX,REG_GPR , "r21", "r21","",0, 1, 0}, /* parm/gpr */
80 {REG_GPR|REG_PAIR, R22_IDX,REG_GPR|REG_PAIR, "r22", "r22","",0, 1, 0}, /* parm/gpr */
81 {REG_GPR, R23_IDX,REG_GPR , "r23", "r23","",0, 1, 0}, /* parm/gpr */
82 {REG_GPR|REG_PAIR, R24_IDX,REG_GPR|REG_PAIR, "r24", "r24","",0, 0, 0}, /* scratch */
83 {REG_GPR, R25_IDX,REG_GPR , "r25", "r25","",0, 0, 0}, /* scratch */
84 {REG_GPR|REG_PAIR, R26_IDX,REG_GPR|REG_PAIR, "r26", "r26","",0, 1, 1}, /* used as pointer reg X */
85 {REG_GPR, R27_IDX,REG_GPR , "r27", "r27","",0, 1, 1}, /* used as pointer reg X */
86 {REG_GPR|REG_PAIR, R28_IDX,REG_GPR|REG_PAIR, "r28", "r28","",0, 1, 0}, /* stack frame Y */
87 {REG_GPR, R29_IDX,REG_GPR , "r29", "r29","",0, 1, 0}, /* stack frame Y */
88 {REG_GPR|REG_PAIR, R30_IDX,REG_GPR|REG_PAIR, "r30", "r30","",0, 1, 1}, /* used as pointer reg Z */
89 {REG_GPR, R31_IDX,REG_GPR , "r31", "r31","",0, 1, 1}, /* used as pointer reg Z */
90 {REG_PTR, X_IDX, REG_PTR, "X", "X", "", 0, 1, 0},
91 {REG_PTR, Z_IDX, REG_PTR, "Z", "Z", "", 0, 1, 0},
94 int avr_fReg = 0; /* first allocatable register */
96 static void spillThis (symbol *);
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);
118 /* other wise look for specific type
120 if (regsAVR[i].isFree && (regsAVR[i].type & type)) {
121 regsAVR[i].isFree = 0;
124 bitVectSetBit (currFunc->regsUsed, i);
131 /*-----------------------------------------------------------------*/
132 /* allocRegPair - allocates register pair of given */
133 /*-----------------------------------------------------------------*/
135 allocRegPair (short type)
139 for (i = avr_fReg; i < avr_nRegs; i++) {
141 /* look for specific type of register pair */
142 if (regsAVR[i].isFree && (regsAVR[i].type & type)
143 && (regsAVR[i].type & REG_PAIR) && regsAVR[i+1].isFree) {
145 regsAVR[i].isFree = 0;
146 regsAVR[i+1].isFree = 0;
149 bitVectSetBit (currFunc->regsUsed, i);
151 bitVectSetBit (currFunc->regsUsed, i+1);
159 /*-----------------------------------------------------------------*/
160 /* avr_regWithIdx - returns pointer to register wit index number */
161 /*-----------------------------------------------------------------*/
163 avr_regWithIdx (int idx)
167 for (i = 0; i < avr_nRegs; i++)
168 if (regsAVR[i].rIdx == idx)
171 werror (E_INTERNAL_ERROR, __FILE__, __LINE__, "regWithIdx not found");
175 /*-----------------------------------------------------------------*/
176 /* freeReg - frees a register */
177 /*-----------------------------------------------------------------*/
185 /*-----------------------------------------------------------------*/
186 /* nFreeRegs - returns number of free registers */
187 /*-----------------------------------------------------------------*/
194 for (i = avr_fReg; i < avr_nRegs; i++)
195 if (regsAVR[i].isFree && regsAVR[i].type & type)
200 /*-----------------------------------------------------------------*/
201 /* nfreeRegsType - free registers with type */
202 /*-----------------------------------------------------------------*/
204 nfreeRegsType (int type)
207 if (type == REG_PTR) {
208 if ((nfr = nFreeRegs (type)) == 0)
209 return nFreeRegs (REG_GPR);
212 return nFreeRegs (type);
216 /*-----------------------------------------------------------------*/
217 /* allDefsOutOfRange - all definitions are out of a range */
218 /*-----------------------------------------------------------------*/
220 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
227 for (i = 0; i < defs->size; i++) {
230 if (bitVectBitValue (defs, i) &&
231 (ic = hTabItemWithKey (iCodehTab, i)) &&
232 (ic->seq >= fseq && ic->seq <= toseq))
240 /*-----------------------------------------------------------------*/
241 /* computeSpillable - given a point find the spillable live ranges */
242 /*-----------------------------------------------------------------*/
244 computeSpillable (iCode * ic)
248 /* spillable live ranges are those that are live at this
249 point . the following categories need to be subtracted
251 a) - those that are already spilt
252 b) - if being used by this one
253 c) - defined by this one */
255 spillable = bitVectCopy (ic->rlive);
256 spillable = bitVectCplAnd (spillable, _G.spiltSet); /* those already spilt */
257 spillable = bitVectCplAnd (spillable, ic->uses); /* used in this one */
258 bitVectUnSetBit (spillable, ic->defKey);
259 spillable = bitVectIntersect (spillable, _G.regAssigned);
264 /*-----------------------------------------------------------------*/
265 /* noSpilLoc - return true if a variable has no spil location */
266 /*-----------------------------------------------------------------*/
268 noSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
270 return (sym->usl.spillLoc ? 0 : 1);
273 /*-----------------------------------------------------------------*/
274 /* hasSpilLoc - will return 1 if the symbol has spil location */
275 /*-----------------------------------------------------------------*/
277 hasSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
279 return (sym->usl.spillLoc ? 1 : 0);
282 /*-----------------------------------------------------------------*/
283 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location */
284 /* but is not used as a pointer */
285 /*-----------------------------------------------------------------*/
287 hasSpilLocnoUptr (symbol * sym, eBBlock * ebp, iCode * ic)
289 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
292 /*-----------------------------------------------------------------*/
293 /* rematable - will return 1 if the remat flag is set */
294 /*-----------------------------------------------------------------*/
296 rematable (symbol * sym, eBBlock * ebp, iCode * ic)
301 /*-----------------------------------------------------------------*/
302 /* notUsedInBlock - not used in this block */
303 /*-----------------------------------------------------------------*/
305 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode * ic)
307 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
308 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq));
311 /*-----------------------------------------------------------------*/
312 /* notUsedInRemaining - not used or defined in remain of the block */
313 /*-----------------------------------------------------------------*/
315 notUsedInRemaining (symbol * sym, eBBlock * ebp, iCode * ic)
317 return ((usedInRemaining (operandFromSymbol (sym), ic) ? 0 : 1) &&
318 allDefsOutOfRange (sym->defs, ic->seq, ebp->lSeq));
321 /*-----------------------------------------------------------------*/
322 /* allLRs - return true for all */
323 /*-----------------------------------------------------------------*/
325 allLRs (symbol * sym, eBBlock * ebp, iCode * ic)
330 /*-----------------------------------------------------------------*/
331 /* liveRangesWith - applies function to a given set of live range */
332 /*-----------------------------------------------------------------*/
334 liveRangesWith (bitVect * lrs,
335 int (func) (symbol *, eBBlock *, iCode *),
336 eBBlock * ebp, iCode * ic)
341 if (!lrs || !lrs->size)
344 for (i = 1; i < lrs->size; i++) {
346 if (!bitVectBitValue (lrs, i))
349 /* if we don't find it in the live range
350 hash table we are in serious trouble */
351 if (!(sym = hTabItemWithKey (liveRanges, i))) {
352 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
353 "liveRangesWith could not find liveRange");
357 if (func (sym, ebp, ic)
358 && bitVectBitValue (_G.regAssigned,
359 sym->key)) addSetHead (&rset, sym);
366 /*-----------------------------------------------------------------*/
367 /* leastUsedLR - given a set determines which is the least used */
368 /*-----------------------------------------------------------------*/
370 leastUsedLR (set * sset)
372 symbol *sym = NULL, *lsym = NULL;
374 sym = lsym = setFirstItem (sset);
379 for (; lsym; lsym = setNextItem (sset)) {
381 /* if usage is the same then prefer
382 the spill the smaller of the two */
383 if (lsym->used == sym->used)
384 if (getSize (lsym->type) < getSize (sym->type))
388 if (lsym->used < sym->used)
393 setToNull ((void **) &sset);
398 /*-----------------------------------------------------------------*/
399 /* noOverLap - will iterate through the list looking for over lap */
400 /*-----------------------------------------------------------------*/
402 noOverLap (set * itmpStack, symbol * fsym)
407 for (sym = setFirstItem (itmpStack); sym;
408 sym = setNextItem (itmpStack)) {
409 if (sym->liveTo > fsym->liveFrom)
417 /*-----------------------------------------------------------------*/
418 /* isFree - will return 1 if the a free spil location is found */
419 /*-----------------------------------------------------------------*/
424 V_ARG (symbol **, sloc);
425 V_ARG (symbol *, fsym);
427 /* if already found */
431 /* if it is free && and the itmp assigned to
432 this does not have any overlapping live ranges
433 with the one currently being assigned and
434 the size can be accomodated */
436 noOverLap (sym->usl.itmpStack, fsym) &&
437 getSize (sym->type) >= getSize (fsym->type)) {
445 /*-----------------------------------------------------------------*/
446 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
447 /*-----------------------------------------------------------------*/
449 spillLRWithPtrReg (symbol * forSym)
452 regs *X, *Z, *X1, *Z1;
455 if (!_G.regAssigned || bitVectIsZero (_G.regAssigned))
458 X = avr_regWithIdx (R26_IDX);
459 X1= avr_regWithIdx (R27_IDX);
460 Z = avr_regWithIdx (R30_IDX);
461 Z1= avr_regWithIdx (R31_IDX);
463 /* for all live ranges */
464 for (lrsym = hTabFirstItem (liveRanges, &k); lrsym;
465 lrsym = hTabNextItem (liveRanges, &k)) {
468 /* if no registers assigned to it or
470 /* if it does not overlap with this then
471 not need to spill it */
473 if (lrsym->isspilt || !lrsym->nRegs ||
474 (lrsym->liveTo < forSym->liveFrom)) continue;
476 /* go thru the registers : if it is either
477 r0 or r1 then spil it */
478 for (j = 0; j < lrsym->nRegs; j++)
479 if (lrsym->regs[j] == X || lrsym->regs[j] == Z ||
480 lrsym->regs[j] == X1 || lrsym->regs[j] == Z1) {
488 /*-----------------------------------------------------------------*/
489 /* createStackSpil - create a location on the stack to spil */
490 /*-----------------------------------------------------------------*/
492 createStackSpil (symbol * sym)
495 int useXstack, model, noOverlay;
500 /* first go try and find a free one that is already
501 existing on the stack */
502 if (applyToSet (_G.stackSpil, isFree, &sloc, sym)) {
503 /* found a free one : just update & return */
504 sym->usl.spillLoc = sloc;
507 addSetHead (&sloc->usl.itmpStack, sym);
511 /* could not then have to create one , this is the hard part
512 we need to allocate this on the stack : this is really a
513 hack!! but cannot think of anything better at this time */
515 if (sprintf (slocBuffer, "sloc%d", _G.slocNum++) >=
516 sizeof (slocBuffer)) {
518 "***Internal error: slocBuffer overflowed: %s:%d\n",
523 sloc = newiTemp (slocBuffer);
525 /* set the type to the spilling symbol */
526 sloc->type = copyLinkChain (sym->type);
527 sloc->etype = getSpec (sloc->type);
528 SPEC_SCLS (sloc->etype) = S_AUTO;
529 SPEC_EXTR (sloc->etype) = 0;
531 /* we don't allow it to be allocated`
532 onto the external stack since : so we
533 temporarily turn it off ; we also
534 turn off memory model to prevent
535 the spil from going to the external storage
536 and turn off overlaying
539 useXstack = options.useXstack;
540 model = options.model;
541 noOverlay = options.noOverlay;
542 stackAuto = options.stackAuto;
543 options.noOverlay = 1;
544 options.model = options.useXstack = 0;
548 options.useXstack = useXstack;
549 options.model = model;
550 options.noOverlay = noOverlay;
551 options.stackAuto = stackAuto;
552 sloc->isref = 1; /* to prevent compiler warning */
554 /* if it is on the stack then update the stack */
555 if (IN_STACK (sloc->etype)) {
556 currFunc->stack += getSize (sloc->type);
557 _G.stackExtend += getSize (sloc->type);
560 _G.dataExtend += getSize (sloc->type);
562 /* add it to the _G.stackSpil set */
563 addSetHead (&_G.stackSpil, sloc);
564 sym->usl.spillLoc = sloc;
567 /* add it to the set of itempStack set
568 of the spill location */
569 addSetHead (&sloc->usl.itmpStack, sym);
573 /*-----------------------------------------------------------------*/
574 /* isSpiltOnStack - returns true if the spil location is on stack */
575 /*-----------------------------------------------------------------*/
577 isSpiltOnStack (symbol * sym)
588 if (!sym->usl.spillLoc)
591 etype = getSpec (sym->usl.spillLoc->type);
592 if (IN_STACK (etype))
598 /*-----------------------------------------------------------------*/
599 /* spillThis - spils a specific operand */
600 /*-----------------------------------------------------------------*/
602 spillThis (symbol * sym)
605 /* if this is rematerializable or has a spillLocation
606 we are okay, else we need to create a spillLocation
608 if (!(sym->remat || sym->usl.spillLoc))
609 createStackSpil (sym);
612 /* mark it has spilt & put it in the spilt set */
614 _G.spiltSet = bitVectSetBit (_G.spiltSet, sym->key);
616 bitVectUnSetBit (_G.regAssigned, sym->key);
618 for (i = 0; i < sym->nRegs; i++)
621 freeReg (sym->regs[i]);
625 if (sym->usl.spillLoc && !sym->remat)
626 sym->usl.spillLoc->allocreq = 1;
630 /*-----------------------------------------------------------------*/
631 /* selectSpil - select a iTemp to spil : rather a simple procedure */
632 /*-----------------------------------------------------------------*/
634 selectSpil (iCode * ic, eBBlock * ebp, symbol * forSym)
636 bitVect *lrcs = NULL;
640 /* get the spillable live ranges */
641 lrcs = computeSpillable (ic);
643 /* get all live ranges that are rematerizable */
644 if ((selectS = liveRangesWith (lrcs, rematable, ebp, ic))) {
646 /* return the least used of these */
647 return leastUsedLR (selectS);
650 /* if the symbol is local to the block then */
651 if (forSym->liveTo < ebp->lSeq) {
653 /* check if there are any live ranges allocated
654 to registers that are not used in this block */
657 liveRangesWith (lrcs, notUsedInBlock, ebp, ic))) {
658 sym = leastUsedLR (selectS);
659 /* if this is not rematerializable */
667 /* check if there are any live ranges that not
668 used in the remainder of the block */
671 liveRangesWith (lrcs, notUsedInRemaining, ebp, ic))) {
672 sym = leastUsedLR (selectS);
683 /* find live ranges with spillocation && not used as pointers */
684 if ((selectS = liveRangesWith (lrcs, hasSpilLocnoUptr, ebp, ic))) {
686 sym = leastUsedLR (selectS);
687 /* mark this as allocation required */
688 sym->usl.spillLoc->allocreq = 1;
692 /* find live ranges with spillocation */
693 if ((selectS = liveRangesWith (lrcs, hasSpilLoc, ebp, ic))) {
695 sym = leastUsedLR (selectS);
696 sym->usl.spillLoc->allocreq = 1;
700 /* couldn't find then we need to create a spil
701 location on the stack , for which one? the least
703 if ((selectS = liveRangesWith (lrcs, noSpilLoc, ebp, ic))) {
705 /* return a created spil location */
706 sym = createStackSpil (leastUsedLR (selectS));
707 sym->usl.spillLoc->allocreq = 1;
711 /* this is an extreme situation we will spill
712 this one : happens very rarely but it does happen */
718 /*-----------------------------------------------------------------*/
719 /* spilSomething - spil some variable & mark registers as free */
720 /*-----------------------------------------------------------------*/
722 spilSomething (iCode * ic, eBBlock * ebp, symbol * forSym)
727 /* get something we can spil */
728 ssym = selectSpil (ic, ebp, forSym);
730 /* mark it as spilt */
732 _G.spiltSet = bitVectSetBit (_G.spiltSet, ssym->key);
734 /* mark it as not register assigned &
735 take it away from the set */
736 bitVectUnSetBit (_G.regAssigned, ssym->key);
738 /* mark the registers as free */
739 for (i = 0; i < ssym->nRegs; i++)
741 freeReg (ssym->regs[i]);
743 /* if this was a block level spil then insert push & pop
744 at the start & end of block respectively */
745 if (ssym->blockSpil) {
746 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
747 /* add push to the start of the block */
748 addiCodeToeBBlock (ebp, nic, (ebp->sch->op == LABEL ?
749 ebp->sch->next : ebp->sch));
750 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
751 /* add pop to the end of the block */
752 addiCodeToeBBlock (ebp, nic, NULL);
755 /* if spilt because not used in the remainder of the
756 block then add a push before this instruction and
757 a pop at the end of the block */
758 if (ssym->remainSpil) {
760 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
761 /* add push just before this instruction */
762 addiCodeToeBBlock (ebp, nic, ic);
764 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
765 /* add pop to the end of the block */
766 addiCodeToeBBlock (ebp, nic, NULL);
775 /*-----------------------------------------------------------------*/
776 /* getRegPtr - will try for PTR if not a GPR type if not spil */
777 /*-----------------------------------------------------------------*/
779 getRegPtr (iCode * ic, eBBlock * ebp, symbol * sym)
784 /* try for a ptr type */
785 if ((reg = allocReg (REG_PTR|REG_PAIR)))
788 /* try for gpr type / pair */
789 if ((reg = allocReg (REG_GPR|REG_PAIR)))
792 /* try for gpr type */
793 if ((reg = allocReg (REG_GPR)))
796 /* we have to spil */
797 if (!spilSomething (ic, ebp, sym))
800 /* this looks like an infinite loop but
801 in reality selectSpil will abort */
805 /*-----------------------------------------------------------------*/
806 /* getRegScr - will try for SCR if not a GPR type if not spil */
807 /*-----------------------------------------------------------------*/
809 getRegScr (iCode * ic, eBBlock * ebp, symbol * sym)
815 /* try for a scratch non-pair */
816 if ((reg = allocReg (REG_SCR)))
819 if ((reg = allocReg (REG_GPR)))
822 /* we have to spil */
823 if (!spilSomething (ic, ebp, sym))
826 /* this looks like an infinite loop but
827 in really selectSpil will abort */
831 /*-----------------------------------------------------------------*/
832 /* getRegGpr - will try for GPR if not spil */
833 /*-----------------------------------------------------------------*/
835 getRegGpr (iCode * ic, eBBlock * ebp, symbol * sym )
840 /* try for gpr type */
841 if ((reg = allocReg (REG_GPR)))
845 if ((reg = allocReg (REG_PTR)))
848 /* we have to spil */
849 if (!spilSomething (ic, ebp, sym))
852 /* this looks like an infinite loop but
853 in reality selectSpil will abort */
857 /*-----------------------------------------------------------------*/
858 /* symHasReg - symbol has a given register */
859 /*-----------------------------------------------------------------*/
861 symHasReg (symbol * sym, regs * reg)
865 for (i = 0; i < sym->nRegs; i++)
866 if (sym->regs[i] == reg)
872 /*-----------------------------------------------------------------*/
873 /* deassignLRs - check the live to and if they have registers & are */
874 /* not spilt then free up the registers */
875 /*-----------------------------------------------------------------*/
877 deassignLRs (iCode * ic, eBBlock * ebp)
883 for (sym = hTabFirstItem (liveRanges, &k); sym;
884 sym = hTabNextItem (liveRanges, &k)) {
887 /* if it does not end here */
888 if (sym->liveTo > ic->seq)
891 /* if it was spilt on stack then we can
892 mark the stack spil location as free */
894 if (sym->stackSpil) {
895 sym->usl.spillLoc->isFree = 1;
901 if (!bitVectBitValue (_G.regAssigned, sym->key))
904 /* special case check if this is an IFX &
905 the privious one was a pop and the
906 previous one was not spilt then keep track
908 if (ic->op == IFX && ic->prev &&
909 ic->prev->op == IPOP &&
910 !ic->prev->parmPush &&
911 !OP_SYMBOL (IC_LEFT (ic->prev))->isspilt)
912 psym = OP_SYMBOL (IC_LEFT (ic->prev));
917 bitVectUnSetBit (_G.regAssigned, sym->key);
919 /* if the result of this one needs registers
920 and does not have it then assign it right
922 if (IC_RESULT (ic) && !(SKIP_IC2 (ic) || /* not a special icode */
923 ic->op == JUMPTABLE ||
929 (result = OP_SYMBOL (IC_RESULT (ic))) && /* has a result */
930 result->liveTo > ic->seq && /* and will live beyond this */
931 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
932 result->regType == sym->regType && /* same register types */
933 result->nRegs && /* which needs registers */
934 !result->isspilt && /* and does not already have them */
936 !bitVectBitValue (_G.regAssigned, result->key) &&
937 /* the number of free regs + number of regs in this LR
938 can accomodate the what result Needs */
939 ((nfreeRegsType (result->regType) + sym->nRegs) >= result->nRegs)) {
941 for (i = 0; i < result->nRegs; i++) {
943 result->regs[i] = sym->regs[i];
944 else if (result->regType == REG_SCR)
945 result->regs[i] = getRegScr (ic, ebp, result);
947 result->regs[i] = getRegGpr (ic, ebp, result);
949 _G.regAssigned = bitVectSetBit (_G.regAssigned, result->key);
953 /* free the remaining */
954 for (; i < sym->nRegs; i++) {
956 if (!symHasReg (psym, sym->regs[i]))
957 freeReg (sym->regs[i]);
959 else freeReg (sym->regs[i]);
966 /*-----------------------------------------------------------------*/
967 /* reassignLR - reassign this to registers */
968 /*-----------------------------------------------------------------*/
970 reassignLR (operand * op)
972 symbol *sym = OP_SYMBOL (op);
975 /* not spilt any more */
976 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
977 bitVectUnSetBit (_G.spiltSet, sym->key);
979 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
983 for (i = 0; i < sym->nRegs; i++)
984 sym->regs[i]->isFree = 0;
987 /*-----------------------------------------------------------------*/
988 /* willCauseSpill - determines if allocating will cause a spill */
989 /*-----------------------------------------------------------------*/
991 willCauseSpill (int nr, int rt)
993 /* first check if there are any avlb registers
994 of te type required */
996 /* special case for pointer type
997 if pointer type not avlb then
998 check for type gpr */
999 if (nFreeRegs (rt) >= nr)
1001 if (nFreeRegs (REG_GPR) >= nr)
1005 if (avr_ptrRegReq) {
1006 if (nFreeRegs (rt) >= nr)
1010 if (nFreeRegs (REG_PTR) + nFreeRegs (REG_GPR) >= nr)
1015 /* it will cause a spil */
1019 /*-----------------------------------------------------------------*/
1020 /* positionRegs - the allocator can allocate same registers to res- */
1021 /* ult and operand, if this happens make sure they are in the same */
1022 /* position as the operand otherwise chaos results */
1023 /*-----------------------------------------------------------------*/
1025 positionRegs (symbol * result, symbol * opsym, int lineno)
1027 int count = min (result->nRegs, opsym->nRegs);
1028 int i, j = 0, shared = 0;
1030 /* if the result has been spilt then cannot share */
1035 /* first make sure that they actually share */
1036 for (i = 0; i < count; i++) {
1037 for (j = 0; j < count; j++) {
1038 if (result->regs[i] == opsym->regs[j] && i != j) {
1046 regs *tmp = result->regs[i];
1047 result->regs[i] = result->regs[j];
1048 result->regs[j] = tmp;
1053 /*-----------------------------------------------------------------*/
1054 /* needsPair - heuristic to determine if a pair would be good */
1055 /*-----------------------------------------------------------------*/
1056 static int needsPair (iCode *ic)
1058 symbol *sym = OP_SYMBOL(IC_RESULT(ic));
1059 bitVect *uses_defs =
1060 bitVectUnion(OP_USES (IC_RESULT(ic)),OP_DEFS(IC_RESULT(ic)));
1062 /* if size is less than 2 then NO */
1063 if (sym->nRegs < 2) return 0;
1064 /* if type Pointer then YES */
1065 if (IS_PTR(sym->type)) return 1;
1067 /* go thru the usages of this operand if used with
1068 a constant then yes */
1069 while (!bitVectIsZero(uses_defs)) {
1070 int ikey = bitVectFirstBit(uses_defs);
1071 iCode *uic = hTabItemWithKey(iCodehTab,ikey);
1072 sym_link *otype = NULL;
1074 otype = (IC_RIGHT(uic) ? operandType(IC_RIGHT(uic)) : NULL);
1075 if (otype && IS_LITERAL(otype)) return 1;
1076 bitVectUnSetBit(uses_defs,ikey);
1081 /*-----------------------------------------------------------------*/
1082 /* serialRegAssign - serially allocate registers to the variables */
1083 /*-----------------------------------------------------------------*/
1085 serialRegAssign (eBBlock ** ebbs, int count)
1089 /* for all blocks */
1090 for (i = 0; i < count; i++) {
1094 if (ebbs[i]->noPath &&
1095 (ebbs[i]->entryLabel != entryLabel &&
1096 ebbs[i]->entryLabel != returnLabel))
1099 /* of all instructions do */
1100 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1102 /* if this is an ipop that means some live
1103 range will have to be assigned again */
1105 reassignLR (IC_LEFT (ic));
1107 /* if result is present && is a true symbol */
1108 if (IC_RESULT (ic) && ic->op != IFX &&
1109 IS_TRUE_SYMOP (IC_RESULT (ic)))
1110 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
1112 /* take away registers from live
1113 ranges that end at this instruction */
1114 deassignLRs (ic, ebbs[i]);
1116 /* some don't need registers */
1117 if (SKIP_IC2 (ic) ||
1118 ic->op == JUMPTABLE ||
1122 (IC_RESULT (ic) && POINTER_SET (ic))) continue;
1124 /* now we need to allocate registers
1125 only for the result */
1126 if (IC_RESULT (ic)) {
1127 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1132 /* if it does not need or is spilt
1133 or is already assigned to registers
1134 or will not live beyond this instructions */
1137 bitVectBitValue (_G.regAssigned, sym->key)
1138 || sym->liveTo <= ic->seq)
1141 /* if some liverange has been spilt at the block level
1142 and this one live beyond this block then spil this
1145 && sym->liveTo > ebbs[i]->lSeq) {
1149 /* if trying to allocate this will cause
1150 a spill and there is nothing to spill
1151 or this one is rematerializable then
1154 willCauseSpill (sym->nRegs,
1156 spillable = computeSpillable (ic);
1157 if (sym->remat || (willCS && bitVectIsZero (spillable))) {
1162 /* if it has a spillocation & is used less than
1163 all other live ranges then spill this */
1165 if (sym->usl.spillLoc) {
1166 symbol *leastUsed = leastUsedLR (liveRangesWith (spillable,
1167 allLRs, ebbs[i], ic));
1168 if (leastUsed && leastUsed->used > sym->used) {
1173 /* if none of the liveRanges have a spillLocation then better
1174 to spill this one than anything else already assigned to registers */
1175 if (liveRangesWith(spillable,noSpilLoc,ebbs[i],ic)) {
1182 /* we assign registers to it */
1183 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1184 if (needsPair(ic)) {
1187 if (sym->regType == REG_PTR) regtype = REG_PTR;
1188 else if (sym->regType == REG_SCR) regtype = REG_SCR;
1189 else regtype = REG_GPR;
1190 preg = allocRegPair(regtype);
1192 sym->regs[j++] = preg;
1193 sym->regs[j++] = ®sAVR[preg->rIdx+1];
1196 for (; j < sym->nRegs; j++) {
1197 if (sym->regType == REG_PTR)
1198 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1199 else if (sym->regType == REG_SCR)
1200 sym->regs[j] = getRegScr (ic, ebbs[i], sym);
1202 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1203 /* if the allocation falied which means
1204 this was spilt then break */
1205 if (!sym->regs[j]) break;
1208 /* if it shares registers with operands make sure
1209 that they are in the same position */
1210 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1211 OP_SYMBOL (IC_LEFT (ic))->nRegs
1213 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1214 OP_SYMBOL (IC_LEFT (ic)), ic->lineno);
1215 /* do the same for the right operand */
1216 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))
1217 && OP_SYMBOL (IC_RIGHT (ic))->nRegs)
1218 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1219 OP_SYMBOL (IC_RIGHT (ic)), ic->lineno);
1226 /*-----------------------------------------------------------------*/
1227 /* rUmaskForOp :- returns register mask for an operand */
1228 /*-----------------------------------------------------------------*/
1230 rUmaskForOp (operand * op)
1236 /* only temporaries are assigned registers */
1240 sym = OP_SYMBOL (op);
1242 /* if spilt or no registers assigned to it
1244 if (sym->isspilt || !sym->nRegs)
1247 rumask = newBitVect (avr_nRegs);
1249 for (j = 0; j < sym->nRegs; j++) {
1250 rumask = bitVectSetBit (rumask, sym->regs[j]->rIdx);
1256 /*-----------------------------------------------------------------*/
1257 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1258 /*-----------------------------------------------------------------*/
1260 regsUsedIniCode (iCode * ic)
1262 bitVect *rmask = newBitVect (avr_nRegs);
1264 /* do the special cases first */
1265 if (ic->op == IFX) {
1266 rmask = bitVectUnion (rmask, rUmaskForOp (IC_COND (ic)));
1270 /* for the jumptable */
1271 if (ic->op == JUMPTABLE) {
1272 rmask = bitVectUnion (rmask, rUmaskForOp (IC_JTCOND (ic)));
1277 /* of all other cases */
1279 rmask = bitVectUnion (rmask, rUmaskForOp (IC_LEFT (ic)));
1283 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RIGHT (ic)));
1286 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RESULT (ic)));
1292 /*-----------------------------------------------------------------*/
1293 /* createRegMask - for each instruction will determine the regsUsed */
1294 /*-----------------------------------------------------------------*/
1296 createRegMask (eBBlock ** ebbs, int count)
1300 /* for all blocks */
1301 for (i = 0; i < count; i++) {
1304 if (ebbs[i]->noPath &&
1305 (ebbs[i]->entryLabel != entryLabel &&
1306 ebbs[i]->entryLabel != returnLabel))
1309 /* for all instructions */
1310 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1314 if (SKIP_IC2 (ic) || !ic->rlive)
1317 /* first mark the registers used in this
1319 ic->rUsed = regsUsedIniCode (ic);
1320 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1322 /* now create the register mask for those
1323 registers that are in use : this is a
1324 super set of ic->rUsed */
1325 ic->rMask = newBitVect (avr_nRegs + 1);
1327 /* for all live Ranges alive at this point */
1328 for (j = 1; j < ic->rlive->size; j++) {
1332 /* if not alive then continue */
1333 if (!bitVectBitValue (ic->rlive, j))
1336 /* find the live range we are interested in */
1337 if (!(sym = hTabItemWithKey (liveRanges, j))) {
1338 werror (E_INTERNAL_ERROR, __FILE__,
1340 "createRegMask cannot find live range");
1344 /* if no register assigned to it */
1345 if (!sym->nRegs || sym->isspilt)
1348 /* for all the registers allocated to it */
1349 for (k = 0; k < sym->nRegs; k++) {
1351 ic->rMask = bitVectSetBit (ic-> rMask, sym->regs[k]->rIdx);
1352 /* special case for X & Z registers */
1353 if (k == R26_IDX || k == R27_IDX)
1354 ic->rMask = bitVectSetBit (ic->rMask, X_IDX);
1355 if (k == R30_IDX || k == R31_IDX)
1356 ic->rMask = bitVectSetBit (ic->rMask, Z_IDX);
1364 /*-----------------------------------------------------------------*/
1365 /* rematStr - returns the rematerialized string for a remat var */
1366 /*-----------------------------------------------------------------*/
1368 rematStr (symbol * sym)
1371 iCode *ic = sym->rematiCode;
1375 /* if plus or minus print the right hand side */
1376 if (ic->op == '+' || ic->op == '-') {
1377 sprintf (s, "0x%04x %c ",
1378 (int) operandLitValue (IC_RIGHT (ic)),
1381 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1385 /* we reached the end */
1386 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1393 /*-----------------------------------------------------------------*/
1394 /* regTypeNum - computes the type & number of registers required */
1395 /*-----------------------------------------------------------------*/
1403 /* for each live range do */
1404 for (sym = hTabFirstItem (liveRanges, &k); sym;
1405 sym = hTabNextItem (liveRanges, &k)) {
1407 /* if used zero times then no registers needed */
1408 if ((sym->liveTo - sym->liveFrom) == 0)
1412 /* if the live range is a temporary */
1415 /* if the type is marked as a conditional */
1416 if (sym->regType == REG_CND)
1419 /* if used in return only then we don't
1421 if (sym->ruonly || sym->accuse) {
1422 if (IS_AGGREGATE (sym->type) || sym->isptr)
1424 aggrToPtr (sym->type, FALSE);
1428 /* if the symbol has only one definition &
1429 that definition is a get_pointer and the
1430 pointer we are getting is rematerializable and
1433 if (bitVectnBitsOn (sym->defs) == 1 &&
1434 (ic = hTabItemWithKey (iCodehTab, bitVectFirstBit (sym-> defs)))
1435 && POINTER_GET (ic) && !IS_BITVAR (sym->etype)) {
1437 /* if in data space or idata space then try to
1438 allocate pointer register */
1442 /* if not then we require registers */
1444 ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1445 getSize (sym->type =
1446 aggrToPtr (sym->type,
1447 FALSE)) : getSize (sym->
1450 if (sym->nRegs > 4) {
1452 "allocated more than 4 or 0 registers for type ");
1453 printTypeChain (sym->type, stderr);
1454 fprintf (stderr, "\n");
1457 /* determine the type of register required */
1458 if (sym->nRegs == 2 && /* size is two */
1459 IS_PTR (sym->type) && /* is a pointer */
1460 sym->uptr) { /* has pointer usage i.e. get/set pointer */
1461 sym->regType = REG_PTR;
1465 /* live accross a function call then gpr else scratch */
1466 if (sym->isLiveFcall)
1467 sym->regType = REG_GPR;
1469 sym->regType = REG_SCR;
1473 /* for the first run we don't provide */
1474 /* registers for true symbols we will */
1475 /* see how things go */
1481 /*-----------------------------------------------------------------*/
1482 /* deallocStackSpil - this will set the stack pointer back */
1483 /*-----------------------------------------------------------------*/
1485 DEFSETFUNC (deallocStackSpil)
1493 /*-----------------------------------------------------------------*/
1494 /* farSpacePackable - returns the packable icode for far variables */
1495 /*-----------------------------------------------------------------*/
1497 farSpacePackable (iCode * ic)
1501 /* go thru till we find a definition for the
1502 symbol on the right */
1503 for (dic = ic->prev; dic; dic = dic->prev) {
1505 /* if the definition is a call then no */
1506 if ((dic->op == CALL || dic->op == PCALL) &&
1507 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1511 /* if shift by unknown amount then not */
1512 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1513 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1516 /* if pointer get and size > 1 */
1517 if (POINTER_GET (dic) &&
1518 getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) >
1521 if (POINTER_SET (dic) &&
1522 getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE))
1526 /* if any three is a true symbol in far space */
1527 if (IC_RESULT (dic) &&
1528 IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1529 isOperandInFarSpace (IC_RESULT (dic)))
1532 if (IC_RIGHT (dic) &&
1533 IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
1534 isOperandInFarSpace (IC_RIGHT (dic)) &&
1535 !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
1538 if (IC_LEFT (dic) &&
1539 IS_TRUE_SYMOP (IC_LEFT (dic)) &&
1540 isOperandInFarSpace (IC_LEFT (dic)) &&
1541 !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
1544 if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic))) {
1545 if ((dic->op == LEFT_OP ||
1546 dic->op == RIGHT_OP ||
1548 IS_OP_LITERAL (IC_RIGHT (dic))) return NULL;
1557 /*-----------------------------------------------------------------*/
1558 /* packRegsForAssign - register reduction for assignment */
1559 /*-----------------------------------------------------------------*/
1561 packRegsForAssign (iCode * ic, eBBlock * ebp)
1565 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1566 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1567 OP_LIVETO (IC_RIGHT (ic)) > ic->seq) {
1571 /* find the definition of iTempNN scanning backwards if we find a
1572 a use of the true symbol in before we find the definition then
1574 for (dic = ic->prev; dic; dic = dic->prev) {
1576 /* if there is a function call and this is
1577 a parameter & not my parameter then don't pack it */
1578 if ((dic->op == CALL || dic->op == PCALL) &&
1579 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1580 !OP_SYMBOL (IC_RESULT (ic))->ismyparm)) {
1588 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1589 IS_OP_VOLATILE (IC_RESULT (dic))) {
1594 if (IS_SYMOP (IC_RESULT (dic)) &&
1595 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1596 if (POINTER_SET (dic))
1602 if (IS_SYMOP (IC_RIGHT (dic)) &&
1603 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1604 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key)) {
1609 if (IS_SYMOP (IC_LEFT (dic)) &&
1610 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1611 IC_LEFT (dic)->key == IC_RIGHT (ic)->key)) {
1616 if (POINTER_SET (dic) &&
1617 IC_RESULT (dic)->key == IC_RESULT (ic)->key) {
1624 return 0; /* did not find */
1626 /* if the result is on stack or iaccess then it must be
1627 the same atleast one of the operands */
1628 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1629 OP_SYMBOL (IC_RESULT (ic))->iaccess) {
1631 /* the operation has only one symbol
1632 operator then we can pack */
1633 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1634 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1637 if (!((IC_LEFT (dic) &&
1638 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1640 IC_RESULT (ic)->key == IC_RIGHT (dic)->key))) return 0;
1643 /* if in far space & tru symbol then don't */
1644 if ((IS_TRUE_SYMOP (IC_RESULT (ic)))
1645 && isOperandInFarSpace (IC_RESULT (ic))) return 0;
1646 /* found the definition */
1647 /* replace the result with the result of */
1648 /* this assignment and remove this assignment */
1649 IC_RESULT (dic) = IC_RESULT (ic);
1651 if (IS_ITEMP (IC_RESULT (dic))
1652 && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq) {
1653 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1655 /* delete from liverange table also
1656 delete from all the points inbetween and the new
1658 for (sic = dic; sic != ic; sic = sic->next) {
1659 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1660 if (IS_ITEMP (IC_RESULT (dic)))
1661 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1664 remiCodeFromeBBlock (ebp, ic);
1665 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1670 /*-----------------------------------------------------------------*/
1671 /* findAssignToSym : scanning backwards looks for first assig found */
1672 /*-----------------------------------------------------------------*/
1674 findAssignToSym (operand * op, iCode * ic)
1678 for (dic = ic->prev; dic; dic = dic->prev) {
1680 /* if definition by assignment */
1681 if (dic->op == '=' &&
1682 !POINTER_SET (dic) && IC_RESULT (dic)->key == op->key
1683 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1686 /* we are interested only if defined in far space */
1687 /* or in stack space in case of + & - */
1689 /* if assigned to a non-symbol then return
1691 if (!IS_SYMOP (IC_RIGHT (dic)))
1694 /* if the symbol is in far space then
1696 if (isOperandInFarSpace (IC_RIGHT (dic)))
1699 /* for + & - operations make sure that
1700 if it is on the stack it is the same
1701 as one of the three operands */
1702 if ((ic->op == '+' || ic->op == '-') &&
1703 OP_SYMBOL (IC_RIGHT (dic))->onStack) {
1705 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key
1706 && IC_LEFT (ic)->key !=
1708 && IC_RIGHT (ic)->key !=
1709 IC_RIGHT (dic)->key) return NULL;
1716 /* if we find an usage then we cannot delete it */
1717 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
1720 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
1723 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
1727 /* now make sure that the right side of dic
1728 is not defined between ic & dic */
1730 iCode *sic = dic->next;
1732 for (; sic != ic; sic = sic->next)
1733 if (IC_RESULT (sic) &&
1734 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
1743 /*-----------------------------------------------------------------*/
1744 /* packRegsForSupport :- reduce some registers for support calls */
1745 /*-----------------------------------------------------------------*/
1747 packRegsForSupport (iCode * ic, eBBlock * ebp)
1750 /* for the left & right operand :- look to see if the
1751 left was assigned a true symbol in far space in that
1752 case replace them */
1753 if (IS_ITEMP (IC_LEFT (ic)) &&
1754 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq) {
1755 iCode *dic = findAssignToSym (IC_LEFT (ic), ic);
1761 /* found it we need to remove it from the
1763 for (sic = dic; sic != ic; sic = sic->next)
1764 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
1766 IC_LEFT (ic)->operand.symOperand =
1767 IC_RIGHT (dic)->operand.symOperand;
1768 IC_LEFT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1769 remiCodeFromeBBlock (ebp, dic);
1770 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1774 /* do the same for the right operand */
1777 IS_ITEMP (IC_RIGHT (ic)) &&
1778 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq) {
1779 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
1785 /* if this is a subtraction & the result
1786 is a true symbol in far space then don't pack */
1787 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic))) {
1789 getSpec (operandType (IC_RESULT (dic)));
1790 if (IN_FARSPACE (SPEC_OCLS (etype)))
1793 /* found it we need to remove it from the
1795 for (sic = dic; sic != ic; sic = sic->next)
1796 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
1798 IC_RIGHT (ic)->operand.symOperand =
1799 IC_RIGHT (dic)->operand.symOperand;
1800 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1802 remiCodeFromeBBlock (ebp, dic);
1803 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1810 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1813 /*-----------------------------------------------------------------*/
1814 /* packRegsForOneuse : - will reduce some registers for single Use */
1815 /*-----------------------------------------------------------------*/
1817 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1822 /* if returning a literal then do nothing */
1827 if (ic->op != RETURN)
1830 /* this routine will mark the a symbol as used in one
1831 instruction use only && if the defintion is local
1832 (ie. within the basic block) && has only one definition &&
1833 that definiion is either a return value from a
1834 function or does not contain any variables in
1836 uses = bitVectCopy (OP_USES (op));
1837 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1838 if (!bitVectIsZero (uses)) /* has other uses */
1841 /* if it has only one defintion */
1842 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1843 return NULL; /* has more than one definition */
1845 /* get the that definition */
1847 hTabItemWithKey (iCodehTab,
1848 bitVectFirstBit (OP_DEFS (op))))) return NULL;
1850 /* found the definition now check if it is local */
1851 if (dic->seq < ebp->fSeq || dic->seq > ebp->lSeq)
1852 return NULL; /* non-local */
1854 /* now check if it is the return from
1856 if (dic->op == CALL || dic->op == PCALL) {
1857 if (ic->op != SEND && ic->op != RETURN) {
1858 OP_SYMBOL (op)->ruonly = 1;
1865 /* otherwise check that the definition does
1866 not contain any symbols in far space */
1867 if (IS_OP_RUONLY (IC_LEFT (ic)) || IS_OP_RUONLY (IC_RIGHT (ic))) {
1871 /* if pointer set then make sure the pointer
1873 if (POINTER_SET (dic) &&
1874 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1877 if (POINTER_GET (dic) &&
1878 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1883 /* also make sure the intervenening instructions
1884 don't have any thing in far space */
1885 for (dic = dic->next; dic && dic != ic; dic = dic->next) {
1887 /* if there is an intervening function call then no */
1888 if (dic->op == CALL || dic->op == PCALL)
1890 /* if pointer set then make sure the pointer
1892 if (POINTER_SET (dic) &&
1893 !IS_DATA_PTR (aggrToPtr
1894 (operandType (IC_RESULT (dic)),
1895 FALSE))) return NULL;
1897 if (POINTER_GET (dic) &&
1898 !IS_DATA_PTR (aggrToPtr
1899 (operandType (IC_LEFT (dic)),
1900 FALSE))) return NULL;
1902 /* if address of & the result is remat the okay */
1903 if (dic->op == ADDRESS_OF &&
1904 OP_SYMBOL (IC_RESULT (dic))->remat) continue;
1906 /* if operand has size of three or more & this
1907 operation is a '*','/' or '%' then 'b' may
1909 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1910 getSize (operandType (op)) >= 3)
1913 /* if left or right or result is in far space */
1914 if (IS_OP_RUONLY (IC_LEFT (dic)) ||
1915 IS_OP_RUONLY (IC_RIGHT (dic)) ||
1916 IS_OP_RUONLY (IC_RESULT (dic))) {
1921 OP_SYMBOL (op)->ruonly = 1;
1926 /*-----------------------------------------------------------------*/
1927 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1928 /*-----------------------------------------------------------------*/
1930 isBitwiseOptimizable (iCode * ic)
1932 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
1933 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
1935 /* bitwise operations are considered optimizable
1936 under the following conditions (Jean-Louis VERN)
1948 if (IS_LITERAL (rtype) ||
1949 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
1955 /*-----------------------------------------------------------------*/
1956 /* packForPush - hueristics to reduce iCode for pushing */
1957 /*-----------------------------------------------------------------*/
1959 packForPush (iCode * ic, eBBlock * ebp)
1963 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
1966 /* must have only definition & one usage */
1967 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
1968 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
1971 /* find the definition */
1972 if (!(dic = hTabItemWithKey (iCodehTab,
1973 bitVectFirstBit (OP_DEFS
1977 if (dic->op != '=' || POINTER_SET (dic))
1980 /* we now we know that it has one & only one def & use
1981 and the that the definition is an assignment */
1982 IC_LEFT (ic) = IC_RIGHT (dic);
1984 remiCodeFromeBBlock (ebp, dic);
1985 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1988 /*-----------------------------------------------------------------*/
1989 /* packRegisters - does some transformations to reduce register */
1991 /*-----------------------------------------------------------------*/
1993 packRegisters (eBBlock * ebp)
2002 /* look for assignments of the form */
2003 /* iTempNN = TRueSym (someoperation) SomeOperand */
2005 /* TrueSym := iTempNN:1 */
2006 for (ic = ebp->sch; ic; ic = ic->next) {
2009 /* find assignment of the form TrueSym := iTempNN:1 */
2010 if (ic->op == '=' && !POINTER_SET (ic))
2011 change += packRegsForAssign (ic, ebp);
2018 for (ic = ebp->sch; ic; ic = ic->next) {
2020 /* if this is an itemp & result of a address of a true sym
2021 then mark this as rematerialisable */
2022 if (ic->op == ADDRESS_OF &&
2023 IS_ITEMP (IC_RESULT (ic)) &&
2024 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2025 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2026 !OP_SYMBOL (IC_LEFT (ic))->onStack) {
2028 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2029 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2030 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2034 /* if straight assignment then carry remat flag if
2035 this is the only definition */
2036 if (ic->op == '=' &&
2037 !POINTER_SET (ic) &&
2038 IS_SYMOP (IC_RIGHT (ic)) &&
2039 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2040 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1) {
2042 OP_SYMBOL (IC_RESULT (ic))->remat =
2043 OP_SYMBOL (IC_RIGHT (ic))->remat;
2044 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2045 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2048 /* if this is a +/- operation with a rematerizable
2049 then mark this as rematerializable as well only
2050 if the literal value is within the range -255 and + 255
2051 the assembler cannot handle it other wise */
2052 if ((ic->op == '+' || ic->op == '-') &&
2053 (IS_SYMOP (IC_LEFT (ic)) &&
2054 IS_ITEMP (IC_RESULT (ic)) &&
2055 OP_SYMBOL (IC_LEFT (ic))->remat &&
2056 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2057 IS_OP_LITERAL (IC_RIGHT (ic)))) {
2059 int i = (int) operandLitValue (IC_RIGHT (ic));
2060 if (i < 255 && i > -255) {
2061 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2062 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2063 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc =
2068 /* mark the pointer usages */
2069 if (POINTER_SET (ic))
2070 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2072 if (POINTER_GET (ic))
2073 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2075 /* if the condition of an if instruction
2076 is defined in the previous instruction then
2077 mark the itemp as a conditional */
2078 if ((IS_CONDITIONAL (ic) ||
2079 ((ic->op == BITWISEAND ||
2082 isBitwiseOptimizable (ic))) &&
2083 ic->next && ic->next->op == IFX &&
2084 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2085 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq) {
2087 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2091 /* some cases the redundant moves can
2092 can be eliminated for return statements */
2093 if ((ic->op == RETURN || ic->op == SEND))
2094 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2096 /* if this is cast for intergral promotion then
2097 check if only use of the definition of the
2098 operand being casted/ if yes then replace
2099 the result of that arithmetic operation with
2100 this result and get rid of the cast */
2101 if (ic->op == CAST) {
2102 sym_link *fromType = operandType (IC_RIGHT (ic));
2103 sym_link *toType = operandType (IC_LEFT (ic));
2105 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2106 getSize (fromType) != getSize (toType) &&
2107 SPEC_USIGN (fromType) == SPEC_USIGN (toType)) {
2110 packRegsForOneuse (ic, IC_RIGHT (ic),
2113 if (IS_ARITHMETIC_OP (dic)) {
2116 remiCodeFromeBBlock (ebp, ic);
2117 hTabDeleteItem (&iCodehTab,
2124 OP_SYMBOL (IC_RIGHT (ic))->
2130 /* if the type from and type to are the same
2131 then if this is the only use then packit */
2132 if (checkType (operandType (IC_RIGHT (ic)),
2133 operandType (IC_LEFT (ic))) ==
2136 packRegsForOneuse (ic,
2142 remiCodeFromeBBlock (ebp, ic);
2143 hTabDeleteItem (&iCodehTab,
2155 /*-----------------------------------------------------------------*/
2156 /* preAssignParms - we have a leaf function preassign registers */
2157 /*-----------------------------------------------------------------*/
2159 preAssignParms (iCode * ic)
2162 /* look for receives and assign registers
2163 to the result of the receives */
2165 /* if it is a receive */
2166 if (ic->op == RECEIVE) {
2167 symbol *r = OP_SYMBOL (IC_RESULT (ic));
2168 int size = getSize (r->type);
2169 if (r->regType == REG_GPR || r->regType == REG_SCR) {
2172 r->regs[j++] = ®sAVR[i++];
2173 regsAVR[i - 1].isFree = 0;
2175 /* put in the regassigned vector */
2177 bitVectSetBit (_G.regAssigned,
2181 /* not a GPR then we should mark as free */
2183 regsAVR[i++].isFree = 1;
2189 /* mark anything remaining as free */
2190 while (i <= R23_IDX)
2191 regsAVR[i++].isFree = 1;
2194 /*-----------------------------------------------------------------*/
2195 /* setdefaultRegs - do setup stuff for register allocation */
2196 /*-----------------------------------------------------------------*/
2198 setDefaultRegs (eBBlock ** ebbs, int count)
2202 /* if no pointer registers required in this function
2203 then mark r26-27 & r30-r31 as GPR & free */
2204 regsAVR[R26_IDX].isFree =
2205 regsAVR[R27_IDX].isFree =
2206 regsAVR[R30_IDX].isFree = regsAVR[R31_IDX].isFree = 1;
2208 if (!avr_ptrRegReq) {
2209 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_GPR;
2210 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_GPR;
2211 regsAVR[R28_IDX].type = (regsAVR[R28_IDX].type & ~REG_MASK) | REG_GPR;
2212 regsAVR[R29_IDX].type = (regsAVR[R29_IDX].type & ~REG_MASK) | REG_GPR;
2215 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_PTR;
2216 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_PTR;
2217 regsAVR[R28_IDX].type = (regsAVR[R28_IDX].type & ~REG_MASK) | REG_PTR;
2218 regsAVR[R29_IDX].type = (regsAVR[R29_IDX].type & ~REG_MASK) | REG_PTR;
2221 /* registers 0-1 / 24-25 used as scratch */
2222 regsAVR[R0_IDX].isFree =
2223 regsAVR[R1_IDX].isFree =
2224 regsAVR[R24_IDX].isFree = regsAVR[R25_IDX].isFree = 0;
2226 /* if this has no function calls then we need
2227 to do something special
2228 a) pre-assign registers to parameters RECEIVE
2229 b) mark the remaining parameter regs as free */
2230 /* mark the parameter regs as SCRACH */
2231 for (i = R16_IDX; i <= R23_IDX; i++) {
2232 regsAVR[i].type = (regsAVR[i].type & ~REG_MASK) | REG_SCR;
2233 regsAVR[i].isFree = 1;
2235 if (!currFunc->hasFcall) {
2236 preAssignParms (ebbs[0]->sch);
2238 /* Y - is not allocated (it is the stack frame) */
2239 regsAVR[R28_IDX].isFree = regsAVR[R28_IDX].isFree = 0;
2242 /*-----------------------------------------------------------------*/
2243 /* assignRegisters - assigns registers to each live range as need */
2244 /*-----------------------------------------------------------------*/
2246 avr_assignRegisters (eBBlock ** ebbs, int count)
2251 setToNull ((void *) &_G.funcrUsed);
2252 avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2254 /* change assignments this will remove some
2255 live ranges reducing some register pressure */
2256 for (i = 0; i < count; i++)
2257 packRegisters (ebbs[i]);
2259 if (options.dump_pack)
2260 dumpEbbsToFileExt (".dumppack", ebbs, count);
2262 /* first determine for each live range the number of
2263 registers & the type of registers required for each */
2266 /* setup the default registers */
2267 setDefaultRegs (ebbs, count);
2269 /* and serially allocate registers */
2270 serialRegAssign (ebbs, count);
2272 /* if stack was extended then tell the user */
2273 if (_G.stackExtend) {
2274 /* werror(W_TOOMANY_SPILS,"stack", */
2275 /* _G.stackExtend,currFunc->name,""); */
2279 if (_G.dataExtend) {
2280 /* werror(W_TOOMANY_SPILS,"data space", */
2281 /* _G.dataExtend,currFunc->name,""); */
2285 /* after that create the register mask
2286 for each of the instruction */
2287 createRegMask (ebbs, count);
2289 /* redo that offsets for stacked automatic variables */
2290 redoStackOffsets ();
2292 if (options.dump_rassgn)
2293 dumpEbbsToFileExt (".dumprassgn", ebbs, count);
2295 /* now get back the chain */
2296 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2300 /* for (; ic ; ic = ic->next) */
2301 /* piCode(ic,stdout); */
2302 /* free up any _G.stackSpil locations allocated */
2303 applyToSet (_G.stackSpil, deallocStackSpil);
2305 setToNull ((void **) &_G.stackSpil);
2306 setToNull ((void **) &_G.spiltSet);
2307 /* mark all registers as free */