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 */
1164 if (willCS && sym->usl.spillLoc) {
1166 symbol *leastUsed = leastUsedLR (liveRangesWith (spillable,
1167 allLRs, ebbs[i], ic));
1168 if (leastUsed && leastUsed->used > sym->used) {
1174 /* we assign registers to it */
1175 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1176 if (needsPair(ic)) {
1179 if (sym->regType == REG_PTR) regtype = REG_PTR;
1180 else if (sym->regType == REG_SCR) regtype = REG_SCR;
1181 else regtype = REG_GPR;
1182 preg = allocRegPair(regtype);
1184 sym->regs[j++] = preg;
1185 sym->regs[j++] = ®sAVR[preg->rIdx+1];
1188 for (; j < sym->nRegs; j++) {
1189 if (sym->regType == REG_PTR)
1190 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1191 else if (sym->regType == REG_SCR)
1192 sym->regs[j] = getRegScr (ic, ebbs[i], sym);
1194 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1195 /* if the allocation falied which means
1196 this was spilt then break */
1197 if (!sym->regs[j]) break;
1200 /* if it shares registers with operands make sure
1201 that they are in the same position */
1202 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1203 OP_SYMBOL (IC_LEFT (ic))->nRegs
1205 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1206 OP_SYMBOL (IC_LEFT (ic)), ic->lineno);
1207 /* do the same for the right operand */
1208 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))
1209 && OP_SYMBOL (IC_RIGHT (ic))->nRegs)
1210 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1211 OP_SYMBOL (IC_RIGHT (ic)), ic->lineno);
1218 /*-----------------------------------------------------------------*/
1219 /* rUmaskForOp :- returns register mask for an operand */
1220 /*-----------------------------------------------------------------*/
1222 rUmaskForOp (operand * op)
1228 /* only temporaries are assigned registers */
1232 sym = OP_SYMBOL (op);
1234 /* if spilt or no registers assigned to it
1236 if (sym->isspilt || !sym->nRegs)
1239 rumask = newBitVect (avr_nRegs);
1241 for (j = 0; j < sym->nRegs; j++) {
1242 rumask = bitVectSetBit (rumask, sym->regs[j]->rIdx);
1248 /*-----------------------------------------------------------------*/
1249 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1250 /*-----------------------------------------------------------------*/
1252 regsUsedIniCode (iCode * ic)
1254 bitVect *rmask = newBitVect (avr_nRegs);
1256 /* do the special cases first */
1257 if (ic->op == IFX) {
1258 rmask = bitVectUnion (rmask, rUmaskForOp (IC_COND (ic)));
1262 /* for the jumptable */
1263 if (ic->op == JUMPTABLE) {
1264 rmask = bitVectUnion (rmask, rUmaskForOp (IC_JTCOND (ic)));
1269 /* of all other cases */
1271 rmask = bitVectUnion (rmask, rUmaskForOp (IC_LEFT (ic)));
1275 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RIGHT (ic)));
1278 rmask = bitVectUnion (rmask, rUmaskForOp (IC_RESULT (ic)));
1284 /*-----------------------------------------------------------------*/
1285 /* createRegMask - for each instruction will determine the regsUsed */
1286 /*-----------------------------------------------------------------*/
1288 createRegMask (eBBlock ** ebbs, int count)
1292 /* for all blocks */
1293 for (i = 0; i < count; i++) {
1296 if (ebbs[i]->noPath &&
1297 (ebbs[i]->entryLabel != entryLabel &&
1298 ebbs[i]->entryLabel != returnLabel))
1301 /* for all instructions */
1302 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
1306 if (SKIP_IC2 (ic) || !ic->rlive)
1309 /* first mark the registers used in this
1311 ic->rUsed = regsUsedIniCode (ic);
1312 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1314 /* now create the register mask for those
1315 registers that are in use : this is a
1316 super set of ic->rUsed */
1317 ic->rMask = newBitVect (avr_nRegs + 1);
1319 /* for all live Ranges alive at this point */
1320 for (j = 1; j < ic->rlive->size; j++) {
1324 /* if not alive then continue */
1325 if (!bitVectBitValue (ic->rlive, j))
1328 /* find the live range we are interested in */
1329 if (!(sym = hTabItemWithKey (liveRanges, j))) {
1330 werror (E_INTERNAL_ERROR, __FILE__,
1332 "createRegMask cannot find live range");
1336 /* if no register assigned to it */
1337 if (!sym->nRegs || sym->isspilt)
1340 /* for all the registers allocated to it */
1341 for (k = 0; k < sym->nRegs; k++) {
1343 ic->rMask = bitVectSetBit (ic-> rMask, sym->regs[k]->rIdx);
1344 /* special case for X & Z registers */
1345 if (k == R26_IDX || k == R27_IDX)
1346 ic->rMask = bitVectSetBit (ic->rMask, X_IDX);
1347 if (k == R30_IDX || k == R31_IDX)
1348 ic->rMask = bitVectSetBit (ic->rMask, Z_IDX);
1356 /*-----------------------------------------------------------------*/
1357 /* rematStr - returns the rematerialized string for a remat var */
1358 /*-----------------------------------------------------------------*/
1360 rematStr (symbol * sym)
1363 iCode *ic = sym->rematiCode;
1367 /* if plus or minus print the right hand side */
1368 if (ic->op == '+' || ic->op == '-') {
1369 sprintf (s, "0x%04x %c ",
1370 (int) operandLitValue (IC_RIGHT (ic)),
1373 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1377 /* we reached the end */
1378 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1385 /*-----------------------------------------------------------------*/
1386 /* regTypeNum - computes the type & number of registers required */
1387 /*-----------------------------------------------------------------*/
1395 /* for each live range do */
1396 for (sym = hTabFirstItem (liveRanges, &k); sym;
1397 sym = hTabNextItem (liveRanges, &k)) {
1399 /* if used zero times then no registers needed */
1400 if ((sym->liveTo - sym->liveFrom) == 0)
1404 /* if the live range is a temporary */
1407 /* if the type is marked as a conditional */
1408 if (sym->regType == REG_CND)
1411 /* if used in return only then we don't
1413 if (sym->ruonly || sym->accuse) {
1414 if (IS_AGGREGATE (sym->type) || sym->isptr)
1416 aggrToPtr (sym->type, FALSE);
1420 /* if the symbol has only one definition &
1421 that definition is a get_pointer and the
1422 pointer we are getting is rematerializable and
1425 if (bitVectnBitsOn (sym->defs) == 1 &&
1426 (ic = hTabItemWithKey (iCodehTab, bitVectFirstBit (sym-> defs)))
1427 && POINTER_GET (ic) && !IS_BITVAR (sym->etype)) {
1429 /* if in data space or idata space then try to
1430 allocate pointer register */
1434 /* if not then we require registers */
1436 ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1437 getSize (sym->type =
1438 aggrToPtr (sym->type,
1439 FALSE)) : getSize (sym->
1442 if (sym->nRegs > 4) {
1444 "allocated more than 4 or 0 registers for type ");
1445 printTypeChain (sym->type, stderr);
1446 fprintf (stderr, "\n");
1449 /* determine the type of register required */
1450 if (sym->nRegs == 2 && /* size is two */
1451 IS_PTR (sym->type) && /* is a pointer */
1452 sym->uptr) { /* has pointer usage i.e. get/set pointer */
1453 sym->regType = REG_PTR;
1457 /* live accross a function call then gpr else scratch */
1458 if (sym->isLiveFcall)
1459 sym->regType = REG_GPR;
1461 sym->regType = REG_SCR;
1465 /* for the first run we don't provide */
1466 /* registers for true symbols we will */
1467 /* see how things go */
1473 /*-----------------------------------------------------------------*/
1474 /* deallocStackSpil - this will set the stack pointer back */
1475 /*-----------------------------------------------------------------*/
1477 DEFSETFUNC (deallocStackSpil)
1485 /*-----------------------------------------------------------------*/
1486 /* farSpacePackable - returns the packable icode for far variables */
1487 /*-----------------------------------------------------------------*/
1489 farSpacePackable (iCode * ic)
1493 /* go thru till we find a definition for the
1494 symbol on the right */
1495 for (dic = ic->prev; dic; dic = dic->prev) {
1497 /* if the definition is a call then no */
1498 if ((dic->op == CALL || dic->op == PCALL) &&
1499 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1503 /* if shift by unknown amount then not */
1504 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1505 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1508 /* if pointer get and size > 1 */
1509 if (POINTER_GET (dic) &&
1510 getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) >
1513 if (POINTER_SET (dic) &&
1514 getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE))
1518 /* if any three is a true symbol in far space */
1519 if (IC_RESULT (dic) &&
1520 IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1521 isOperandInFarSpace (IC_RESULT (dic)))
1524 if (IC_RIGHT (dic) &&
1525 IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
1526 isOperandInFarSpace (IC_RIGHT (dic)) &&
1527 !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
1530 if (IC_LEFT (dic) &&
1531 IS_TRUE_SYMOP (IC_LEFT (dic)) &&
1532 isOperandInFarSpace (IC_LEFT (dic)) &&
1533 !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
1536 if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic))) {
1537 if ((dic->op == LEFT_OP ||
1538 dic->op == RIGHT_OP ||
1540 IS_OP_LITERAL (IC_RIGHT (dic))) return NULL;
1549 /*-----------------------------------------------------------------*/
1550 /* packRegsForAssign - register reduction for assignment */
1551 /*-----------------------------------------------------------------*/
1553 packRegsForAssign (iCode * ic, eBBlock * ebp)
1557 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1558 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1559 OP_LIVETO (IC_RIGHT (ic)) > ic->seq) {
1563 /* find the definition of iTempNN scanning backwards if we find a
1564 a use of the true symbol in before we find the definition then
1566 for (dic = ic->prev; dic; dic = dic->prev) {
1568 /* if there is a function call and this is
1569 a parameter & not my parameter then don't pack it */
1570 if ((dic->op == CALL || dic->op == PCALL) &&
1571 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1572 !OP_SYMBOL (IC_RESULT (ic))->ismyparm)) {
1580 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1581 IS_OP_VOLATILE (IC_RESULT (dic))) {
1586 if (IS_SYMOP (IC_RESULT (dic)) &&
1587 IC_RESULT (dic)->key == IC_RIGHT (ic)->key) {
1588 if (POINTER_SET (dic))
1594 if (IS_SYMOP (IC_RIGHT (dic)) &&
1595 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1596 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key)) {
1601 if (IS_SYMOP (IC_LEFT (dic)) &&
1602 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1603 IC_LEFT (dic)->key == IC_RIGHT (ic)->key)) {
1608 if (POINTER_SET (dic) &&
1609 IC_RESULT (dic)->key == IC_RESULT (ic)->key) {
1616 return 0; /* did not find */
1618 /* if the result is on stack or iaccess then it must be
1619 the same atleast one of the operands */
1620 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1621 OP_SYMBOL (IC_RESULT (ic))->iaccess) {
1623 /* the operation has only one symbol
1624 operator then we can pack */
1625 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1626 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1629 if (!((IC_LEFT (dic) &&
1630 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1632 IC_RESULT (ic)->key == IC_RIGHT (dic)->key))) return 0;
1635 /* if in far space & tru symbol then don't */
1636 if ((IS_TRUE_SYMOP (IC_RESULT (ic)))
1637 && isOperandInFarSpace (IC_RESULT (ic))) return 0;
1638 /* found the definition */
1639 /* replace the result with the result of */
1640 /* this assignment and remove this assignment */
1641 IC_RESULT (dic) = IC_RESULT (ic);
1643 if (IS_ITEMP (IC_RESULT (dic))
1644 && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq) {
1645 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1647 /* delete from liverange table also
1648 delete from all the points inbetween and the new
1650 for (sic = dic; sic != ic; sic = sic->next) {
1651 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1652 if (IS_ITEMP (IC_RESULT (dic)))
1653 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1656 remiCodeFromeBBlock (ebp, ic);
1657 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1662 /*-----------------------------------------------------------------*/
1663 /* findAssignToSym : scanning backwards looks for first assig found */
1664 /*-----------------------------------------------------------------*/
1666 findAssignToSym (operand * op, iCode * ic)
1670 for (dic = ic->prev; dic; dic = dic->prev) {
1672 /* if definition by assignment */
1673 if (dic->op == '=' &&
1674 !POINTER_SET (dic) && IC_RESULT (dic)->key == op->key
1675 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1678 /* we are interested only if defined in far space */
1679 /* or in stack space in case of + & - */
1681 /* if assigned to a non-symbol then return
1683 if (!IS_SYMOP (IC_RIGHT (dic)))
1686 /* if the symbol is in far space then
1688 if (isOperandInFarSpace (IC_RIGHT (dic)))
1691 /* for + & - operations make sure that
1692 if it is on the stack it is the same
1693 as one of the three operands */
1694 if ((ic->op == '+' || ic->op == '-') &&
1695 OP_SYMBOL (IC_RIGHT (dic))->onStack) {
1697 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key
1698 && IC_LEFT (ic)->key !=
1700 && IC_RIGHT (ic)->key !=
1701 IC_RIGHT (dic)->key) return NULL;
1708 /* if we find an usage then we cannot delete it */
1709 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
1712 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
1715 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
1719 /* now make sure that the right side of dic
1720 is not defined between ic & dic */
1722 iCode *sic = dic->next;
1724 for (; sic != ic; sic = sic->next)
1725 if (IC_RESULT (sic) &&
1726 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
1735 /*-----------------------------------------------------------------*/
1736 /* packRegsForSupport :- reduce some registers for support calls */
1737 /*-----------------------------------------------------------------*/
1739 packRegsForSupport (iCode * ic, eBBlock * ebp)
1742 /* for the left & right operand :- look to see if the
1743 left was assigned a true symbol in far space in that
1744 case replace them */
1745 if (IS_ITEMP (IC_LEFT (ic)) &&
1746 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq) {
1747 iCode *dic = findAssignToSym (IC_LEFT (ic), ic);
1753 /* found it we need to remove it from the
1755 for (sic = dic; sic != ic; sic = sic->next)
1756 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
1758 IC_LEFT (ic)->operand.symOperand =
1759 IC_RIGHT (dic)->operand.symOperand;
1760 IC_LEFT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1761 remiCodeFromeBBlock (ebp, dic);
1762 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1766 /* do the same for the right operand */
1769 IS_ITEMP (IC_RIGHT (ic)) &&
1770 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq) {
1771 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
1777 /* if this is a subtraction & the result
1778 is a true symbol in far space then don't pack */
1779 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic))) {
1781 getSpec (operandType (IC_RESULT (dic)));
1782 if (IN_FARSPACE (SPEC_OCLS (etype)))
1785 /* found it we need to remove it from the
1787 for (sic = dic; sic != ic; sic = sic->next)
1788 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
1790 IC_RIGHT (ic)->operand.symOperand =
1791 IC_RIGHT (dic)->operand.symOperand;
1792 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1794 remiCodeFromeBBlock (ebp, dic);
1795 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1802 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1805 /*-----------------------------------------------------------------*/
1806 /* packRegsForOneuse : - will reduce some registers for single Use */
1807 /*-----------------------------------------------------------------*/
1809 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1814 /* if returning a literal then do nothing */
1819 if (ic->op != RETURN)
1822 /* this routine will mark the a symbol as used in one
1823 instruction use only && if the defintion is local
1824 (ie. within the basic block) && has only one definition &&
1825 that definiion is either a return value from a
1826 function or does not contain any variables in
1828 uses = bitVectCopy (OP_USES (op));
1829 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1830 if (!bitVectIsZero (uses)) /* has other uses */
1833 /* if it has only one defintion */
1834 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1835 return NULL; /* has more than one definition */
1837 /* get the that definition */
1839 hTabItemWithKey (iCodehTab,
1840 bitVectFirstBit (OP_DEFS (op))))) return NULL;
1842 /* found the definition now check if it is local */
1843 if (dic->seq < ebp->fSeq || dic->seq > ebp->lSeq)
1844 return NULL; /* non-local */
1846 /* now check if it is the return from
1848 if (dic->op == CALL || dic->op == PCALL) {
1849 if (ic->op != SEND && ic->op != RETURN) {
1850 OP_SYMBOL (op)->ruonly = 1;
1857 /* otherwise check that the definition does
1858 not contain any symbols in far space */
1859 if (IS_OP_RUONLY (IC_LEFT (ic)) || IS_OP_RUONLY (IC_RIGHT (ic))) {
1863 /* if pointer set then make sure the pointer
1865 if (POINTER_SET (dic) &&
1866 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1869 if (POINTER_GET (dic) &&
1870 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1875 /* also make sure the intervenening instructions
1876 don't have any thing in far space */
1877 for (dic = dic->next; dic && dic != ic; dic = dic->next) {
1879 /* if there is an intervening function call then no */
1880 if (dic->op == CALL || dic->op == PCALL)
1882 /* if pointer set then make sure the pointer
1884 if (POINTER_SET (dic) &&
1885 !IS_DATA_PTR (aggrToPtr
1886 (operandType (IC_RESULT (dic)),
1887 FALSE))) return NULL;
1889 if (POINTER_GET (dic) &&
1890 !IS_DATA_PTR (aggrToPtr
1891 (operandType (IC_LEFT (dic)),
1892 FALSE))) return NULL;
1894 /* if address of & the result is remat the okay */
1895 if (dic->op == ADDRESS_OF &&
1896 OP_SYMBOL (IC_RESULT (dic))->remat) continue;
1898 /* if operand has size of three or more & this
1899 operation is a '*','/' or '%' then 'b' may
1901 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1902 getSize (operandType (op)) >= 3)
1905 /* if left or right or result is in far space */
1906 if (IS_OP_RUONLY (IC_LEFT (dic)) ||
1907 IS_OP_RUONLY (IC_RIGHT (dic)) ||
1908 IS_OP_RUONLY (IC_RESULT (dic))) {
1913 OP_SYMBOL (op)->ruonly = 1;
1918 /*-----------------------------------------------------------------*/
1919 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1920 /*-----------------------------------------------------------------*/
1922 isBitwiseOptimizable (iCode * ic)
1924 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
1925 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
1927 /* bitwise operations are considered optimizable
1928 under the following conditions (Jean-Louis VERN)
1940 if (IS_LITERAL (rtype) ||
1941 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
1947 /*-----------------------------------------------------------------*/
1948 /* packForPush - hueristics to reduce iCode for pushing */
1949 /*-----------------------------------------------------------------*/
1951 packForPush (iCode * ic, eBBlock * ebp)
1955 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
1958 /* must have only definition & one usage */
1959 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
1960 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
1963 /* find the definition */
1964 if (!(dic = hTabItemWithKey (iCodehTab,
1965 bitVectFirstBit (OP_DEFS
1969 if (dic->op != '=' || POINTER_SET (dic))
1972 /* we now we know that it has one & only one def & use
1973 and the that the definition is an assignment */
1974 IC_LEFT (ic) = IC_RIGHT (dic);
1976 remiCodeFromeBBlock (ebp, dic);
1977 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1980 /*-----------------------------------------------------------------*/
1981 /* packRegisters - does some transformations to reduce register */
1983 /*-----------------------------------------------------------------*/
1985 packRegisters (eBBlock * ebp)
1994 /* look for assignments of the form */
1995 /* iTempNN = TRueSym (someoperation) SomeOperand */
1997 /* TrueSym := iTempNN:1 */
1998 for (ic = ebp->sch; ic; ic = ic->next) {
2001 /* find assignment of the form TrueSym := iTempNN:1 */
2002 if (ic->op == '=' && !POINTER_SET (ic))
2003 change += packRegsForAssign (ic, ebp);
2010 for (ic = ebp->sch; ic; ic = ic->next) {
2012 /* if this is an itemp & result of a address of a true sym
2013 then mark this as rematerialisable */
2014 if (ic->op == ADDRESS_OF &&
2015 IS_ITEMP (IC_RESULT (ic)) &&
2016 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2017 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2018 !OP_SYMBOL (IC_LEFT (ic))->onStack) {
2020 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2021 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2022 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2026 /* if straight assignment then carry remat flag if
2027 this is the only definition */
2028 if (ic->op == '=' &&
2029 !POINTER_SET (ic) &&
2030 IS_SYMOP (IC_RIGHT (ic)) &&
2031 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2032 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1) {
2034 OP_SYMBOL (IC_RESULT (ic))->remat =
2035 OP_SYMBOL (IC_RIGHT (ic))->remat;
2036 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2037 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2040 /* if this is a +/- operation with a rematerizable
2041 then mark this as rematerializable as well only
2042 if the literal value is within the range -255 and + 255
2043 the assembler cannot handle it other wise */
2044 if ((ic->op == '+' || ic->op == '-') &&
2045 (IS_SYMOP (IC_LEFT (ic)) &&
2046 IS_ITEMP (IC_RESULT (ic)) &&
2047 OP_SYMBOL (IC_LEFT (ic))->remat &&
2048 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2049 IS_OP_LITERAL (IC_RIGHT (ic)))) {
2051 int i = (int) operandLitValue (IC_RIGHT (ic));
2052 if (i < 255 && i > -255) {
2053 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2054 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2055 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc =
2060 /* mark the pointer usages */
2061 if (POINTER_SET (ic))
2062 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2064 if (POINTER_GET (ic))
2065 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2067 /* if the condition of an if instruction
2068 is defined in the previous instruction then
2069 mark the itemp as a conditional */
2070 if ((IS_CONDITIONAL (ic) ||
2071 ((ic->op == BITWISEAND ||
2074 isBitwiseOptimizable (ic))) &&
2075 ic->next && ic->next->op == IFX &&
2076 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2077 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq) {
2079 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2083 /* some cases the redundant moves can
2084 can be eliminated for return statements */
2085 if ((ic->op == RETURN || ic->op == SEND))
2086 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2088 /* if this is cast for intergral promotion then
2089 check if only use of the definition of the
2090 operand being casted/ if yes then replace
2091 the result of that arithmetic operation with
2092 this result and get rid of the cast */
2093 if (ic->op == CAST) {
2094 sym_link *fromType = operandType (IC_RIGHT (ic));
2095 sym_link *toType = operandType (IC_LEFT (ic));
2097 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2098 getSize (fromType) != getSize (toType) &&
2099 SPEC_USIGN (fromType) == SPEC_USIGN (toType)) {
2102 packRegsForOneuse (ic, IC_RIGHT (ic),
2105 if (IS_ARITHMETIC_OP (dic)) {
2108 remiCodeFromeBBlock (ebp, ic);
2109 hTabDeleteItem (&iCodehTab,
2116 OP_SYMBOL (IC_RIGHT (ic))->
2122 /* if the type from and type to are the same
2123 then if this is the only use then packit */
2124 if (checkType (operandType (IC_RIGHT (ic)),
2125 operandType (IC_LEFT (ic))) ==
2128 packRegsForOneuse (ic,
2134 remiCodeFromeBBlock (ebp, ic);
2135 hTabDeleteItem (&iCodehTab,
2147 /*-----------------------------------------------------------------*/
2148 /* preAssignParms - we have a leaf function preassign registers */
2149 /*-----------------------------------------------------------------*/
2151 preAssignParms (iCode * ic)
2154 /* look for receives and assign registers
2155 to the result of the receives */
2157 /* if it is a receive */
2158 if (ic->op == RECEIVE) {
2159 symbol *r = OP_SYMBOL (IC_RESULT (ic));
2160 int size = getSize (r->type);
2161 if (r->regType == REG_GPR || r->regType == REG_SCR) {
2164 r->regs[j++] = ®sAVR[i++];
2165 regsAVR[i - 1].isFree = 0;
2167 /* put in the regassigned vector */
2169 bitVectSetBit (_G.regAssigned,
2173 /* not a GPR then we should mark as free */
2175 regsAVR[i++].isFree = 1;
2181 /* mark anything remaining as free */
2182 while (i <= R23_IDX)
2183 regsAVR[i++].isFree = 1;
2186 /*-----------------------------------------------------------------*/
2187 /* setdefaultRegs - do setup stuff for register allocation */
2188 /*-----------------------------------------------------------------*/
2190 setDefaultRegs (eBBlock ** ebbs, int count)
2194 /* if no pointer registers required in this function
2195 then mark r26-27 & r30-r31 as GPR & free */
2196 regsAVR[R26_IDX].isFree =
2197 regsAVR[R27_IDX].isFree =
2198 regsAVR[R30_IDX].isFree = regsAVR[R31_IDX].isFree = 1;
2200 if (!avr_ptrRegReq) {
2201 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_GPR;
2202 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_GPR;
2203 regsAVR[R28_IDX].type = (regsAVR[R28_IDX].type & ~REG_MASK) | REG_GPR;
2204 regsAVR[R29_IDX].type = (regsAVR[R29_IDX].type & ~REG_MASK) | REG_GPR;
2207 regsAVR[R26_IDX].type = (regsAVR[R26_IDX].type & ~REG_MASK) | REG_PTR;
2208 regsAVR[R27_IDX].type = (regsAVR[R27_IDX].type & ~REG_MASK) | REG_PTR;
2209 regsAVR[R28_IDX].type = (regsAVR[R28_IDX].type & ~REG_MASK) | REG_PTR;
2210 regsAVR[R29_IDX].type = (regsAVR[R29_IDX].type & ~REG_MASK) | REG_PTR;
2213 /* registers 0-1 / 24-25 used as scratch */
2214 regsAVR[R0_IDX].isFree =
2215 regsAVR[R1_IDX].isFree =
2216 regsAVR[R24_IDX].isFree = regsAVR[R25_IDX].isFree = 0;
2218 /* if this has no function calls then we need
2219 to do something special
2220 a) pre-assign registers to parameters RECEIVE
2221 b) mark the remaining parameter regs as free */
2222 /* mark the parameter regs as SCRACH */
2223 for (i = R16_IDX; i <= R23_IDX; i++) {
2224 regsAVR[i].type = (regsAVR[i].type & ~REG_MASK) | REG_SCR;
2225 regsAVR[i].isFree = 1;
2227 if (!currFunc->hasFcall) {
2228 preAssignParms (ebbs[0]->sch);
2230 /* Y - is not allocated (it is the stack frame) */
2231 regsAVR[R28_IDX].isFree = regsAVR[R28_IDX].isFree = 0;
2234 /*-----------------------------------------------------------------*/
2235 /* assignRegisters - assigns registers to each live range as need */
2236 /*-----------------------------------------------------------------*/
2238 avr_assignRegisters (eBBlock ** ebbs, int count)
2243 setToNull ((void *) &_G.funcrUsed);
2244 avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2246 /* change assignments this will remove some
2247 live ranges reducing some register pressure */
2248 for (i = 0; i < count; i++)
2249 packRegisters (ebbs[i]);
2251 if (options.dump_pack)
2252 dumpEbbsToFileExt (".dumppack", ebbs, count);
2254 /* first determine for each live range the number of
2255 registers & the type of registers required for each */
2258 /* setup the default registers */
2259 setDefaultRegs (ebbs, count);
2261 /* and serially allocate registers */
2262 serialRegAssign (ebbs, count);
2264 /* if stack was extended then tell the user */
2265 if (_G.stackExtend) {
2266 /* werror(W_TOOMANY_SPILS,"stack", */
2267 /* _G.stackExtend,currFunc->name,""); */
2271 if (_G.dataExtend) {
2272 /* werror(W_TOOMANY_SPILS,"data space", */
2273 /* _G.dataExtend,currFunc->name,""); */
2277 /* after that create the register mask
2278 for each of the instruction */
2279 createRegMask (ebbs, count);
2281 /* redo that offsets for stacked automatic variables */
2282 redoStackOffsets ();
2284 if (options.dump_rassgn)
2285 dumpEbbsToFileExt (".dumprassgn", ebbs, count);
2287 /* now get back the chain */
2288 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2292 /* for (; ic ; ic = ic->next) */
2293 /* piCode(ic,stdout); */
2294 /* free up any _G.stackSpil locations allocated */
2295 applyToSet (_G.stackSpil, deallocStackSpil);
2297 setToNull ((void **) &_G.stackSpil);
2298 setToNull ((void **) &_G.spiltSet);
2299 /* mark all registers as free */