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 */
59 { REG_GPR ,R0_IDX , REG_GPR , "r0", "r0" , "" , 0, 0, 0 }, /* used as scratch */
60 { REG_GPR ,R1_IDX , REG_GPR , "r1", "r1" , "" , 0, 0, 0 }, /* used as scratch */
61 { REG_GPR ,R2_IDX , REG_GPR , "r2", "r2" , "" , 0, 1, 1 }, /* gpr */
62 { REG_GPR ,R3_IDX , REG_GPR , "r3", "r3" , "" , 0, 1, 1 }, /* gpr */
63 { REG_GPR ,R4_IDX , REG_GPR , "r4", "r4" , "" , 0, 1, 1 }, /* gpr */
64 { REG_GPR ,R5_IDX , REG_GPR , "r5", "r5" , "" , 0, 1, 1 }, /* gpr */
65 { REG_GPR ,R6_IDX , REG_GPR , "r6", "r6" , "" , 0, 1, 1 }, /* gpr */
66 { REG_GPR ,R7_IDX , REG_GPR , "r7", "r7" , "" , 0, 1, 1 }, /* gpr */
67 { REG_GPR ,R8_IDX , REG_GPR , "r8", "r8" , "" , 0, 1, 1 }, /* gpr */
68 { REG_GPR ,R9_IDX , REG_GPR , "r9", "r9" , "" , 0, 1, 1 }, /* gpr */
69 { REG_GPR ,R10_IDX, REG_GPR , "r10", "r10", "" , 0, 1, 1 }, /* gpr */
70 { REG_GPR ,R11_IDX, REG_GPR , "r11", "r11", "" , 0, 1, 1 }, /* gpr */
71 { REG_GPR ,R12_IDX, REG_GPR , "r12", "r12", "" , 0, 1, 1 }, /* gpr */
72 { REG_GPR ,R13_IDX, REG_GPR , "r13", "r13", "" , 0, 1, 1 }, /* gpr */
73 { REG_GPR ,R14_IDX, REG_GPR , "r14", "r14", "" , 0, 1, 1 }, /* gpr */
74 { REG_GPR ,R15_IDX, REG_GPR , "r15", "r15", "" , 0, 1, 1 }, /* gpr */
75 { REG_GPR ,R16_IDX, REG_GPR , "r16", "r16", "" , 0, 1, 0 }, /* parm/gpr */
76 { REG_GPR ,R17_IDX, REG_GPR , "r17", "r17", "" , 0, 1, 0 }, /* parm/gpr */
77 { REG_GPR ,R18_IDX, REG_GPR , "r18", "r18", "" , 0, 1, 0 }, /* parm/gpr */
78 { REG_GPR ,R19_IDX, REG_GPR , "r19", "r19", "" , 0, 1, 0 }, /* parm/gpr */
79 { REG_GPR ,R20_IDX, REG_GPR , "r20", "r20", "" , 0, 1, 0 }, /* parm/gpr */
80 { REG_GPR ,R21_IDX, REG_GPR , "r21", "r21", "" , 0, 1, 0 }, /* parm/gpr */
81 { REG_GPR ,R22_IDX, REG_GPR , "r22", "r22", "" , 0, 1, 0 }, /* parm/gpr */
82 { REG_GPR ,R23_IDX, REG_GPR , "r23", "r23", "" , 0, 1, 0 }, /* parm/gpr */
83 { REG_GPR ,R24_IDX, REG_GPR , "r24", "r24", "" , 0, 0, 0 }, /* scratch */
84 { REG_GPR ,R25_IDX, REG_GPR , "r25", "r25", "" , 0, 0, 0 }, /* scratch */
85 { REG_GPR ,R26_IDX, REG_GPR , "r26", "r26", "" , 0, 1, 1 }, /* used as pointer reg X */
86 { REG_GPR ,R27_IDX, REG_GPR , "r27", "r27", "" , 0, 1, 1 }, /* used as pointer reg X */
87 { REG_GPR ,R28_IDX, REG_GPR , "r28", "r28", "" , 0, 1, 0 }, /* stack frame Y */
88 { REG_GPR ,R29_IDX, REG_GPR , "r29", "r29", "" , 0, 1, 0 }, /* stack frame Y */
89 { REG_GPR ,R30_IDX, REG_GPR , "r30", "r30", "" , 0, 1, 1 }, /* used as pointer reg Z */
90 { REG_GPR ,R31_IDX, REG_GPR , "r31", "r31", "" , 0, 1, 1 }, /* used as pointer reg Z */
91 { REG_PTR ,X_IDX , REG_PTR , "X" , "X" , "" , 0, 1, 0 },
92 { REG_PTR ,Z_IDX , REG_PTR , "Z" , "Z" , "" , 0, 1, 0 },
95 int avr_fReg = 0; /* first allocatable register */
97 static void spillThis (symbol *);
99 /*-----------------------------------------------------------------*/
100 /* allocReg - allocates register of given type */
101 /*-----------------------------------------------------------------*/
102 static regs *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 */
111 regsAVR[i].isFree ) {
112 regsAVR[i].isFree = 0;
115 bitVectSetBit(currFunc->regsUsed,i);
118 /* other wise look for specific type
120 if (regsAVR[i].isFree &&
121 regsAVR[i].type == type) {
122 regsAVR[i].isFree = 0;
125 bitVectSetBit(currFunc->regsUsed,i);
132 /*-----------------------------------------------------------------*/
133 /* avr_regWithIdx - returns pointer to register wit index number */
134 /*-----------------------------------------------------------------*/
135 regs *avr_regWithIdx (int idx)
139 for (i=0 ; i < avr_nRegs;i++)
140 if (regsAVR[i].rIdx == idx)
143 werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
144 "regWithIdx not found");
148 /*-----------------------------------------------------------------*/
149 /* freeReg - frees a register */
150 /*-----------------------------------------------------------------*/
151 static void freeReg (regs *reg)
157 /*-----------------------------------------------------------------*/
158 /* nFreeRegs - returns number of free registers */
159 /*-----------------------------------------------------------------*/
160 static int nFreeRegs (int type)
165 for (i = avr_fReg ; i < avr_nRegs; i++ )
166 if (regsAVR[i].isFree && regsAVR[i].type == type)
171 /*-----------------------------------------------------------------*/
172 /* nfreeRegsType - free registers with type */
173 /*-----------------------------------------------------------------*/
174 static int nfreeRegsType (int type)
177 if (type == REG_PTR) {
178 if ((nfr = nFreeRegs(type)) == 0)
179 return nFreeRegs(REG_GPR);
182 return nFreeRegs(type);
186 /*-----------------------------------------------------------------*/
187 /* allDefsOutOfRange - all definitions are out of a range */
188 /*-----------------------------------------------------------------*/
189 static bool allDefsOutOfRange (bitVect *defs,int fseq, int toseq)
196 for ( i = 0 ;i < defs->size ; i++ ) {
199 if (bitVectBitValue(defs,i) &&
200 (ic = hTabItemWithKey(iCodehTab,i)) &&
201 ( ic->seq >= fseq && ic->seq <= toseq))
210 /*-----------------------------------------------------------------*/
211 /* computeSpillable - given a point find the spillable live ranges */
212 /*-----------------------------------------------------------------*/
213 static bitVect *computeSpillable (iCode *ic)
217 /* spillable live ranges are those that are live at this
218 point . the following categories need to be subtracted
220 a) - those that are already spilt
221 b) - if being used by this one
222 c) - defined by this one */
224 spillable = bitVectCopy(ic->rlive);
226 bitVectCplAnd(spillable,_G.spiltSet); /* those already spilt */
228 bitVectCplAnd(spillable,ic->uses); /* used in this one */
229 bitVectUnSetBit(spillable,ic->defKey);
230 spillable = bitVectIntersect(spillable,_G.regAssigned);
235 /*-----------------------------------------------------------------*/
236 /* noSpilLoc - return true if a variable has no spil location */
237 /*-----------------------------------------------------------------*/
238 static int noSpilLoc (symbol *sym, eBBlock *ebp,iCode *ic)
240 return (sym->usl.spillLoc ? 0 : 1);
243 /*-----------------------------------------------------------------*/
244 /* hasSpilLoc - will return 1 if the symbol has spil location */
245 /*-----------------------------------------------------------------*/
246 static int hasSpilLoc (symbol *sym, eBBlock *ebp, iCode *ic)
248 return (sym->usl.spillLoc ? 1 : 0);
251 /*-----------------------------------------------------------------*/
252 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location*/
253 /* but is not used as a pointer */
254 /*-----------------------------------------------------------------*/
255 static int hasSpilLocnoUptr (symbol *sym, eBBlock *ebp, iCode *ic)
257 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
260 /*-----------------------------------------------------------------*/
261 /* rematable - will return 1 if the remat flag is set */
262 /*-----------------------------------------------------------------*/
263 static int rematable (symbol *sym, eBBlock *ebp, iCode *ic)
268 /*-----------------------------------------------------------------*/
269 /* notUsedInBlock - not used in this block */
270 /*-----------------------------------------------------------------*/
271 static int notUsedInBlock (symbol *sym, eBBlock *ebp, iCode *ic)
273 return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs) &&
274 allDefsOutOfRange (sym->defs,ebp->fSeq,ebp->lSeq));
277 /*-----------------------------------------------------------------*/
278 /* notUsedInRemaining - not used or defined in remain of the block */
279 /*-----------------------------------------------------------------*/
280 static int notUsedInRemaining (symbol *sym, eBBlock *ebp, iCode *ic)
282 return ((usedInRemaining (operandFromSymbol(sym),ic) ? 0 : 1) &&
283 allDefsOutOfRange (sym->defs,ic->seq,ebp->lSeq));
286 /*-----------------------------------------------------------------*/
287 /* allLRs - return true for all */
288 /*-----------------------------------------------------------------*/
289 static int allLRs (symbol *sym, eBBlock *ebp, iCode *ic)
294 /*-----------------------------------------------------------------*/
295 /* liveRangesWith - applies function to a given set of live range */
296 /*-----------------------------------------------------------------*/
297 static set *liveRangesWith (bitVect *lrs,
298 int (func)(symbol *,eBBlock *, iCode *),
299 eBBlock *ebp, iCode *ic)
304 if (!lrs || !lrs->size)
307 for ( i = 1 ; i < lrs->size ; i++ ) {
309 if (!bitVectBitValue(lrs,i))
312 /* if we don't find it in the live range
313 hash table we are in serious trouble */
314 if (!(sym = hTabItemWithKey(liveRanges,i))) {
315 werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
316 "liveRangesWith could not find liveRange");
320 if (func(sym,ebp,ic) && bitVectBitValue(_G.regAssigned,sym->key))
321 addSetHead(&rset,sym);
328 /*-----------------------------------------------------------------*/
329 /* leastUsedLR - given a set determines which is the least used */
330 /*-----------------------------------------------------------------*/
331 static symbol *leastUsedLR (set *sset)
333 symbol *sym = NULL, *lsym = NULL ;
335 sym = lsym = setFirstItem(sset);
340 for (; lsym; lsym = setNextItem(sset)) {
342 /* if usage is the same then prefer
343 the spill the smaller of the two */
344 if ( lsym->used == sym->used )
345 if (getSize(lsym->type) < getSize(sym->type))
349 if (lsym->used < sym->used )
354 setToNull((void **)&sset);
359 /*-----------------------------------------------------------------*/
360 /* noOverLap - will iterate through the list looking for over lap */
361 /*-----------------------------------------------------------------*/
362 static int noOverLap (set *itmpStack, symbol *fsym)
367 for (sym = setFirstItem(itmpStack); sym;
368 sym = setNextItem(itmpStack)) {
369 if (sym->liveTo > fsym->liveFrom )
377 /*-----------------------------------------------------------------*/
378 /* isFree - will return 1 if the a free spil location is found */
379 /*-----------------------------------------------------------------*/
380 static DEFSETFUNC(isFree)
383 V_ARG(symbol **,sloc);
384 V_ARG(symbol *,fsym);
386 /* if already found */
390 /* if it is free && and the itmp assigned to
391 this does not have any overlapping live ranges
392 with the one currently being assigned and
393 the size can be accomodated */
395 noOverLap(sym->usl.itmpStack,fsym) &&
396 getSize(sym->type) >= getSize(fsym->type)) {
404 /*-----------------------------------------------------------------*/
405 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
406 /*-----------------------------------------------------------------*/
407 static void spillLRWithPtrReg (symbol *forSym)
413 if (!_G.regAssigned ||
414 bitVectIsZero(_G.regAssigned))
417 X = avr_regWithIdx(X_IDX);
418 Z = avr_regWithIdx(Z_IDX);
420 /* for all live ranges */
421 for (lrsym = hTabFirstItem(liveRanges,&k) ; lrsym ;
422 lrsym = hTabNextItem(liveRanges,&k) ) {
425 /* if no registers assigned to it or
427 /* if it does not overlap with this then
428 not need to spill it */
430 if (lrsym->isspilt || !lrsym->nRegs ||
431 (lrsym->liveTo < forSym->liveFrom))
434 /* go thru the registers : if it is either
435 r0 or r1 then spil it */
436 for (j = 0 ; j < lrsym->nRegs ; j++ )
437 if (lrsym->regs[j] == X || lrsym->regs[j] == Z ) {
445 /*-----------------------------------------------------------------*/
446 /* createStackSpil - create a location on the stack to spil */
447 /*-----------------------------------------------------------------*/
448 static symbol *createStackSpil (symbol *sym)
451 int useXstack, model, noOverlay;
456 /* first go try and find a free one that is already
457 existing on the stack */
458 if (applyToSet(_G.stackSpil,isFree,&sloc, sym)) {
459 /* found a free one : just update & return */
460 sym->usl.spillLoc = sloc;
463 addSetHead(&sloc->usl.itmpStack,sym);
467 /* could not then have to create one , this is the hard part
468 we need to allocate this on the stack : this is really a
469 hack!! but cannot think of anything better at this time */
471 if (sprintf(slocBuffer,"sloc%d",_G.slocNum++) >= sizeof(slocBuffer))
473 fprintf(stderr, "***Internal error: slocBuffer overflowed: %s:%d\n",
478 sloc = newiTemp(slocBuffer);
480 /* set the type to the spilling symbol */
481 sloc->type = copyLinkChain(sym->type);
482 sloc->etype = getSpec(sloc->type);
483 SPEC_SCLS(sloc->etype) = S_AUTO ;
484 SPEC_EXTR(sloc->etype) = 0;
486 /* we don't allow it to be allocated`
487 onto the external stack since : so we
488 temporarily turn it off ; we also
489 turn off memory model to prevent
490 the spil from going to the external storage
491 and turn off overlaying
494 useXstack = options.useXstack;
495 model = options.model;
496 noOverlay = options.noOverlay;
497 stackAuto = options.stackAuto;
498 options.noOverlay = 1;
499 options.model = options.useXstack = 0;
503 options.useXstack = useXstack;
504 options.model = model;
505 options.noOverlay = noOverlay;
506 options.stackAuto = stackAuto;
507 sloc->isref = 1; /* to prevent compiler warning */
509 /* if it is on the stack then update the stack */
510 if (IN_STACK(sloc->etype)) {
511 currFunc->stack += getSize(sloc->type);
512 _G.stackExtend += getSize(sloc->type);
514 _G.dataExtend += getSize(sloc->type);
516 /* add it to the _G.stackSpil set */
517 addSetHead(&_G.stackSpil,sloc);
518 sym->usl.spillLoc = sloc;
521 /* add it to the set of itempStack set
522 of the spill location */
523 addSetHead(&sloc->usl.itmpStack,sym);
527 /*-----------------------------------------------------------------*/
528 /* isSpiltOnStack - returns true if the spil location is on stack */
529 /*-----------------------------------------------------------------*/
530 static bool isSpiltOnStack (symbol *sym)
541 if (!sym->usl.spillLoc)
544 etype = getSpec(sym->usl.spillLoc->type);
551 /*-----------------------------------------------------------------*/
552 /* spillThis - spils a specific operand */
553 /*-----------------------------------------------------------------*/
554 static void spillThis (symbol *sym)
557 /* if this is rematerializable or has a spillLocation
558 we are okay, else we need to create a spillLocation
560 if (!(sym->remat || sym->usl.spillLoc))
561 createStackSpil (sym);
564 /* mark it has spilt & put it in the spilt set */
566 _G.spiltSet = bitVectSetBit(_G.spiltSet,sym->key);
568 bitVectUnSetBit(_G.regAssigned,sym->key);
570 for (i = 0 ; i < sym->nRegs ; i++)
573 freeReg(sym->regs[i]);
577 if (sym->usl.spillLoc && !sym->remat)
578 sym->usl.spillLoc->allocreq = 1;
582 /*-----------------------------------------------------------------*/
583 /* selectSpil - select a iTemp to spil : rather a simple procedure */
584 /*-----------------------------------------------------------------*/
585 static symbol *selectSpil (iCode *ic, eBBlock *ebp, symbol *forSym)
587 bitVect *lrcs= NULL ;
591 /* get the spillable live ranges */
592 lrcs = computeSpillable (ic);
594 /* get all live ranges that are rematerizable */
595 if ((selectS = liveRangesWith(lrcs,rematable,ebp,ic))) {
597 /* return the least used of these */
598 return leastUsedLR(selectS);
601 /* if the symbol is local to the block then */
602 if (forSym->liveTo < ebp->lSeq ) {
604 /* check if there are any live ranges allocated
605 to registers that are not used in this block */
607 (selectS = liveRangesWith(lrcs,notUsedInBlock,ebp,ic))) {
608 sym = leastUsedLR(selectS);
609 /* if this is not rematerializable */
617 /* check if there are any live ranges that not
618 used in the remainder of the block */
620 (selectS = liveRangesWith(lrcs,notUsedInRemaining,ebp,ic))) {
621 sym = leastUsedLR (selectS);
630 /* find live ranges with spillocation && not used as pointers */
631 if ((selectS = liveRangesWith(lrcs,hasSpilLocnoUptr,ebp,ic))) {
633 sym = leastUsedLR(selectS);
634 /* mark this as allocation required */
635 sym->usl.spillLoc->allocreq = 1;
639 /* find live ranges with spillocation */
640 if ((selectS = liveRangesWith(lrcs,hasSpilLoc,ebp,ic))) {
642 sym = leastUsedLR(selectS);
643 sym->usl.spillLoc->allocreq = 1;
647 /* couldn't find then we need to create a spil
648 location on the stack , for which one? the least
650 if ((selectS = liveRangesWith(lrcs,noSpilLoc,ebp,ic))) {
652 /* return a created spil location */
653 sym = createStackSpil(leastUsedLR(selectS));
654 sym->usl.spillLoc->allocreq = 1;
658 /* this is an extreme situation we will spill
659 this one : happens very rarely but it does happen */
660 spillThis ( forSym );
665 /*-----------------------------------------------------------------*/
666 /* spilSomething - spil some variable & mark registers as free */
667 /*-----------------------------------------------------------------*/
668 static bool spilSomething (iCode *ic, eBBlock *ebp, symbol *forSym)
673 /* get something we can spil */
674 ssym = selectSpil(ic,ebp,forSym);
676 /* mark it as spilt */
678 _G.spiltSet = bitVectSetBit(_G.spiltSet,ssym->key);
680 /* mark it as not register assigned &
681 take it away from the set */
682 bitVectUnSetBit(_G.regAssigned,ssym->key);
684 /* mark the registers as free */
685 for (i = 0 ; i < ssym->nRegs ;i++ )
687 freeReg(ssym->regs[i]);
689 /* if this was a block level spil then insert push & pop
690 at the start & end of block respectively */
691 if (ssym->blockSpil) {
692 iCode *nic = newiCode(IPUSH,operandFromSymbol(ssym),NULL);
693 /* add push to the start of the block */
694 addiCodeToeBBlock(ebp,nic,( ebp->sch->op == LABEL ?
695 ebp->sch->next : ebp->sch));
696 nic = newiCode(IPOP,operandFromSymbol(ssym),NULL);
697 /* add pop to the end of the block */
698 addiCodeToeBBlock(ebp,nic,NULL);
701 /* if spilt because not used in the remainder of the
702 block then add a push before this instruction and
703 a pop at the end of the block */
704 if (ssym->remainSpil) {
706 iCode *nic = newiCode(IPUSH,operandFromSymbol(ssym),NULL);
707 /* add push just before this instruction */
708 addiCodeToeBBlock(ebp,nic,ic);
710 nic = newiCode(IPOP,operandFromSymbol(ssym),NULL);
711 /* add pop to the end of the block */
712 addiCodeToeBBlock(ebp,nic,NULL);
721 /*-----------------------------------------------------------------*/
722 /* getRegPtr - will try for PTR if not a GPR type if not spil */
723 /*-----------------------------------------------------------------*/
724 static regs *getRegPtr (iCode *ic, eBBlock *ebp, symbol *sym)
729 /* try for a ptr type */
730 if ((reg = allocReg(REG_PTR)))
733 /* try for gpr type */
734 if ((reg = allocReg(REG_GPR)))
737 /* we have to spil */
738 if (!spilSomething (ic,ebp,sym))
741 /* this looks like an infinite loop but
742 in really selectSpil will abort */
746 /*-----------------------------------------------------------------*/
747 /* getRegGpr - will try for GPR if not spil */
748 /*-----------------------------------------------------------------*/
749 static regs *getRegGpr (iCode *ic, eBBlock *ebp,symbol *sym)
754 /* try for gpr type */
755 if ((reg = allocReg(REG_GPR)))
759 if ((reg = allocReg(REG_PTR)))
762 /* we have to spil */
763 if (!spilSomething (ic,ebp,sym))
766 /* this looks like an infinite loop but
767 in reality selectSpil will abort */
771 /*-----------------------------------------------------------------*/
772 /* symHasReg - symbol has a given register */
773 /*-----------------------------------------------------------------*/
774 static bool symHasReg(symbol *sym,regs *reg)
778 for ( i = 0 ; i < sym->nRegs ; i++)
779 if (sym->regs[i] == reg)
785 /*-----------------------------------------------------------------*/
786 /* deassignLRs - check the live to and if they have registers & are*/
787 /* not spilt then free up the registers */
788 /*-----------------------------------------------------------------*/
789 static void deassignLRs (iCode *ic, eBBlock *ebp)
795 for (sym = hTabFirstItem(liveRanges,&k); sym;
796 sym = hTabNextItem(liveRanges,&k)) {
799 /* if it does not end here */
800 if (sym->liveTo > ic->seq )
803 /* if it was spilt on stack then we can
804 mark the stack spil location as free */
806 if (sym->stackSpil) {
807 sym->usl.spillLoc->isFree = 1;
813 if (!bitVectBitValue(_G.regAssigned,sym->key))
816 /* special case check if this is an IFX &
817 the privious one was a pop and the
818 previous one was not spilt then keep track
820 if (ic->op == IFX && ic->prev &&
821 ic->prev->op == IPOP &&
822 !ic->prev->parmPush &&
823 !OP_SYMBOL(IC_LEFT(ic->prev))->isspilt)
824 psym = OP_SYMBOL(IC_LEFT(ic->prev));
829 bitVectUnSetBit(_G.regAssigned,sym->key);
831 /* if the result of this one needs registers
832 and does not have it then assign it right
835 ! (SKIP_IC2(ic) || /* not a special icode */
836 ic->op == JUMPTABLE ||
842 (result = OP_SYMBOL(IC_RESULT(ic))) && /* has a result */
843 result->liveTo > ic->seq && /* and will live beyond this */
844 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
845 result->regType == sym->regType && /* same register types */
846 result->nRegs && /* which needs registers */
847 ! result->isspilt && /* and does not already have them */
849 ! bitVectBitValue(_G.regAssigned,result->key) &&
850 /* the number of free regs + number of regs in this LR
851 can accomodate the what result Needs */
852 ((nfreeRegsType(result->regType) +
853 sym->nRegs) >= result->nRegs)
856 for (i = 0 ; i < max(sym->nRegs,result->nRegs) ; i++)
858 result->regs[i] = sym->regs[i] ;
860 result->regs[i] = getRegGpr (ic,ebp,result);
862 _G.regAssigned = bitVectSetBit(_G.regAssigned,result->key);
866 /* free the remaining */
867 for (; i < sym->nRegs ; i++) {
869 if (!symHasReg(psym,sym->regs[i]))
870 freeReg(sym->regs[i]);
872 freeReg(sym->regs[i]);
879 /*-----------------------------------------------------------------*/
880 /* reassignLR - reassign this to registers */
881 /*-----------------------------------------------------------------*/
882 static void reassignLR (operand *op)
884 symbol *sym = OP_SYMBOL(op);
887 /* not spilt any more */
888 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
889 bitVectUnSetBit(_G.spiltSet,sym->key);
891 _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
895 for (i=0;i<sym->nRegs;i++)
896 sym->regs[i]->isFree = 0;
899 /*-----------------------------------------------------------------*/
900 /* willCauseSpill - determines if allocating will cause a spill */
901 /*-----------------------------------------------------------------*/
902 static int willCauseSpill ( int nr, int rt)
904 /* first check if there are any avlb registers
905 of te type required */
907 /* special case for pointer type
908 if pointer type not avlb then
909 check for type gpr */
910 if (nFreeRegs(rt) >= nr)
912 if (nFreeRegs(REG_GPR) >= nr)
916 if (nFreeRegs(rt) >= nr)
919 if (nFreeRegs(REG_PTR) +
920 nFreeRegs(REG_GPR) >= nr)
925 /* it will cause a spil */
929 /*-----------------------------------------------------------------*/
930 /* positionRegs - the allocator can allocate same registers to res-*/
931 /* ult and operand, if this happens make sure they are in the same */
932 /* position as the operand otherwise chaos results */
933 /*-----------------------------------------------------------------*/
934 static void positionRegs (symbol *result, symbol *opsym, int lineno)
936 int count = min(result->nRegs,opsym->nRegs);
937 int i , j = 0, shared = 0;
939 /* if the result has been spilt then cannot share */
944 /* first make sure that they actually share */
945 for ( i = 0 ; i < count; i++ ) {
946 for (j = 0 ; j < count ; j++ ) {
947 if (result->regs[i] == opsym->regs[j] && i !=j) {
955 regs *tmp = result->regs[i];
956 result->regs[i] = result->regs[j];
957 result->regs[j] = tmp;
962 /*-----------------------------------------------------------------*/
963 /* serialRegAssign - serially allocate registers to the variables */
964 /*-----------------------------------------------------------------*/
965 static void serialRegAssign (eBBlock **ebbs, int count)
970 for (i = 0; i < count ; i++ ) {
974 if (ebbs[i]->noPath &&
975 (ebbs[i]->entryLabel != entryLabel &&
976 ebbs[i]->entryLabel != returnLabel ))
979 /* of all instructions do */
980 for (ic = ebbs[i]->sch ; ic ; ic = ic->next) {
982 /* if this is an ipop that means some live
983 range will have to be assigned again */
985 reassignLR (IC_LEFT(ic));
987 /* if result is present && is a true symbol */
988 if (IC_RESULT(ic) && ic->op != IFX &&
989 IS_TRUE_SYMOP(IC_RESULT(ic)))
990 OP_SYMBOL(IC_RESULT(ic))->allocreq = 1;
992 /* take away registers from live
993 ranges that end at this instruction */
994 deassignLRs (ic, ebbs[i]) ;
996 /* some don't need registers */
998 ic->op == JUMPTABLE ||
1002 (IC_RESULT(ic) &&POINTER_SET(ic)) )
1005 /* now we need to allocate registers
1006 only for the result */
1007 if (IC_RESULT(ic)) {
1008 symbol *sym = OP_SYMBOL(IC_RESULT(ic));
1013 /* if it does not need or is spilt
1014 or is already assigned to registers
1015 or will not live beyond this instructions */
1018 bitVectBitValue(_G.regAssigned,sym->key) ||
1019 sym->liveTo <= ic->seq)
1022 /* if some liverange has been spilt at the block level
1023 and this one live beyond this block then spil this
1025 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq) {
1029 /* if trying to allocate this will cause
1030 a spill and there is nothing to spill
1031 or this one is rematerializable then
1033 willCS = willCauseSpill(sym->nRegs,sym->regType);
1034 spillable = computeSpillable(ic);
1036 (willCS && bitVectIsZero(spillable) ) ) {
1043 /* if it has a spillocation & is used less than
1044 all other live ranges then spill this */
1045 if ( willCS && sym->usl.spillLoc ) {
1048 leastUsedLR(liveRangesWith (spillable ,
1053 leastUsed->used > sym->used) {
1059 /* we assign registers to it */
1060 _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
1062 for (j = 0 ; j < sym->nRegs ;j++ ) {
1063 if (sym->regType == REG_PTR)
1064 sym->regs[j] = getRegPtr(ic,ebbs[i],sym);
1066 sym->regs[j] = getRegGpr(ic,ebbs[i],sym);
1068 /* if the allocation falied which means
1069 this was spilt then break */
1073 /* if it shares registers with operands make sure
1074 that they are in the same position */
1075 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic)) &&
1076 OP_SYMBOL(IC_LEFT(ic))->nRegs && ic->op != '=')
1077 positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1078 OP_SYMBOL(IC_LEFT(ic)),ic->lineno);
1079 /* do the same for the right operand */
1080 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic)) &&
1081 OP_SYMBOL(IC_RIGHT(ic))->nRegs && ic->op != '=')
1082 positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1083 OP_SYMBOL(IC_RIGHT(ic)),ic->lineno);
1090 /*-----------------------------------------------------------------*/
1091 /* rUmaskForOp :- returns register mask for an operand */
1092 /*-----------------------------------------------------------------*/
1093 static bitVect *rUmaskForOp (operand *op)
1099 /* only temporaries are assigned registers */
1103 sym = OP_SYMBOL(op);
1105 /* if spilt or no registers assigned to it
1107 if (sym->isspilt || !sym->nRegs)
1110 rumask = newBitVect(avr_nRegs);
1112 for (j = 0; j < sym->nRegs; j++) {
1113 rumask = bitVectSetBit(rumask,
1114 sym->regs[j]->rIdx);
1120 /*-----------------------------------------------------------------*/
1121 /* regsUsedIniCode :- returns bit vector of registers used in iCode*/
1122 /*-----------------------------------------------------------------*/
1123 static bitVect *regsUsedIniCode (iCode *ic)
1125 bitVect *rmask = newBitVect(avr_nRegs);
1127 /* do the special cases first */
1128 if (ic->op == IFX ) {
1129 rmask = bitVectUnion(rmask,
1130 rUmaskForOp(IC_COND(ic)));
1134 /* for the jumptable */
1135 if (ic->op == JUMPTABLE) {
1136 rmask = bitVectUnion(rmask,
1137 rUmaskForOp(IC_JTCOND(ic)));
1142 /* of all other cases */
1144 rmask = bitVectUnion(rmask,
1145 rUmaskForOp(IC_LEFT(ic)));
1149 rmask = bitVectUnion(rmask,
1150 rUmaskForOp(IC_RIGHT(ic)));
1153 rmask = bitVectUnion(rmask,
1154 rUmaskForOp(IC_RESULT(ic)));
1160 /*-----------------------------------------------------------------*/
1161 /* createRegMask - for each instruction will determine the regsUsed*/
1162 /*-----------------------------------------------------------------*/
1163 static void createRegMask (eBBlock **ebbs, int count)
1167 /* for all blocks */
1168 for (i = 0; i < count ; i++ ) {
1171 if ( ebbs[i]->noPath &&
1172 ( ebbs[i]->entryLabel != entryLabel &&
1173 ebbs[i]->entryLabel != returnLabel ))
1176 /* for all instructions */
1177 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
1181 if (SKIP_IC2(ic) || !ic->rlive)
1184 /* first mark the registers used in this
1186 ic->rUsed = regsUsedIniCode(ic);
1187 _G.funcrUsed = bitVectUnion(_G.funcrUsed,ic->rUsed);
1189 /* now create the register mask for those
1190 registers that are in use : this is a
1191 super set of ic->rUsed */
1192 ic->rMask = newBitVect(avr_nRegs+1);
1194 /* for all live Ranges alive at this point */
1195 for (j = 1; j < ic->rlive->size; j++ ) {
1199 /* if not alive then continue */
1200 if (!bitVectBitValue(ic->rlive,j))
1203 /* find the live range we are interested in */
1204 if (!(sym = hTabItemWithKey(liveRanges,j))) {
1205 werror (E_INTERNAL_ERROR,__FILE__,__LINE__,
1206 "createRegMask cannot find live range");
1210 /* if no register assigned to it */
1211 if (!sym->nRegs || sym->isspilt)
1214 /* for all the registers allocated to it */
1215 for (k = 0 ; k < sym->nRegs ;k++)
1218 bitVectSetBit(ic->rMask,sym->regs[k]->rIdx);
1224 /*-----------------------------------------------------------------*/
1225 /* rematStr - returns the rematerialized string for a remat var */
1226 /*-----------------------------------------------------------------*/
1227 static char *rematStr (symbol *sym)
1230 iCode *ic = sym->rematiCode;
1234 /* if plus or minus print the right hand side */
1235 if (ic->op == '+' || ic->op == '-') {
1236 sprintf(s,"0x%04x %c ",(int) operandLitValue(IC_RIGHT(ic)),
1239 ic = OP_SYMBOL(IC_LEFT(ic))->rematiCode;
1243 /* we reached the end */
1244 sprintf(s,"%s",OP_SYMBOL(IC_LEFT(ic))->rname);
1251 /*-----------------------------------------------------------------*/
1252 /* regTypeNum - computes the type & number of registers required */
1253 /*-----------------------------------------------------------------*/
1254 static void regTypeNum ()
1260 /* for each live range do */
1261 for ( sym = hTabFirstItem(liveRanges,&k); sym ;
1262 sym = hTabNextItem(liveRanges,&k)) {
1264 /* if used zero times then no registers needed */
1265 if ((sym->liveTo - sym->liveFrom) == 0)
1269 /* if the live range is a temporary */
1272 /* if the type is marked as a conditional */
1273 if (sym->regType == REG_CND)
1276 /* if used in return only then we don't
1278 if (sym->ruonly || sym->accuse) {
1279 if (IS_AGGREGATE(sym->type) || sym->isptr)
1280 sym->type = aggrToPtr(sym->type,FALSE);
1284 /* if the symbol has only one definition &
1285 that definition is a get_pointer and the
1286 pointer we are getting is rematerializable and
1289 if (bitVectnBitsOn(sym->defs) == 1 &&
1290 (ic = hTabItemWithKey(iCodehTab,
1291 bitVectFirstBit(sym->defs))) &&
1293 !IS_BITVAR(sym->etype)) {
1295 /* if in data space or idata space then try to
1296 allocate pointer register */
1300 /* if not then we require registers */
1301 sym->nRegs = ((IS_AGGREGATE(sym->type) || sym->isptr ) ?
1302 getSize(sym->type = aggrToPtr(sym->type,FALSE)) :
1303 getSize(sym->type));
1305 if (sym->nRegs > 4) {
1306 fprintf(stderr,"allocated more than 4 or 0 registers for type ");
1307 printTypeChain(sym->type,stderr);fprintf(stderr,"\n");
1310 /* determine the type of register required */
1311 if (sym->nRegs == 2 && /* size is two */
1312 IS_PTR(sym->type) && /* is a pointer */
1313 sym->uptr) { /* has has pointer usage i.e. get/set pointer */
1314 sym->regType = REG_PTR ;
1318 sym->regType = REG_GPR ;
1321 /* for the first run we don't provide */
1322 /* registers for true symbols we will */
1323 /* see how things go */
1329 /*-----------------------------------------------------------------*/
1330 /* deallocStackSpil - this will set the stack pointer back */
1331 /*-----------------------------------------------------------------*/
1332 static DEFSETFUNC(deallocStackSpil)
1340 /*-----------------------------------------------------------------*/
1341 /* farSpacePackable - returns the packable icode for far variables */
1342 /*-----------------------------------------------------------------*/
1343 static iCode *farSpacePackable (iCode *ic)
1347 /* go thru till we find a definition for the
1348 symbol on the right */
1349 for ( dic = ic->prev ; dic ; dic = dic->prev) {
1351 /* if the definition is a call then no */
1352 if ((dic->op == CALL || dic->op == PCALL) &&
1353 IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1357 /* if shift by unknown amount then not */
1358 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1359 IC_RESULT(dic)->key == IC_RIGHT(ic)->key)
1362 /* if pointer get and size > 1 */
1363 if (POINTER_GET(dic) &&
1364 getSize(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)) > 1)
1367 if (POINTER_SET(dic) &&
1368 getSize(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)) > 1)
1371 /* if any three is a true symbol in far space */
1372 if (IC_RESULT(dic) &&
1373 IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1374 isOperandInFarSpace(IC_RESULT(dic)))
1377 if (IC_RIGHT(dic) &&
1378 IS_TRUE_SYMOP(IC_RIGHT(dic)) &&
1379 isOperandInFarSpace(IC_RIGHT(dic)) &&
1380 !isOperandEqual(IC_RIGHT(dic),IC_RESULT(ic)))
1384 IS_TRUE_SYMOP(IC_LEFT(dic)) &&
1385 isOperandInFarSpace(IC_LEFT(dic)) &&
1386 !isOperandEqual(IC_LEFT(dic),IC_RESULT(ic)))
1389 if (isOperandEqual(IC_RIGHT(ic),IC_RESULT(dic))) {
1390 if ( (dic->op == LEFT_OP ||
1391 dic->op == RIGHT_OP ||
1393 IS_OP_LITERAL(IC_RIGHT(dic)))
1403 /*-----------------------------------------------------------------*/
1404 /* packRegsForAssign - register reduction for assignment */
1405 /*-----------------------------------------------------------------*/
1406 static int packRegsForAssign (iCode *ic,eBBlock *ebp)
1410 if (!IS_ITEMP(IC_RIGHT(ic)) ||
1411 OP_SYMBOL(IC_RIGHT(ic))->isind ||
1412 OP_LIVETO(IC_RIGHT(ic)) > ic->seq) {
1416 /* find the definition of iTempNN scanning backwards if we find a
1417 a use of the true symbol in before we find the definition then
1419 for ( dic = ic->prev ; dic ; dic = dic->prev) {
1421 /* if there is a function call and this is
1422 a parameter & not my parameter then don't pack it */
1423 if ( (dic->op == CALL || dic->op == PCALL) &&
1424 (OP_SYMBOL(IC_RESULT(ic))->_isparm &&
1425 !OP_SYMBOL(IC_RESULT(ic))->ismyparm)) {
1433 if (IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1434 IS_OP_VOLATILE(IC_RESULT(dic))) {
1439 if (IS_SYMOP(IC_RESULT(dic)) &&
1440 IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1441 if (POINTER_SET(dic))
1447 if (IS_SYMOP(IC_RIGHT(dic)) &&
1448 (IC_RIGHT(dic)->key == IC_RESULT(ic)->key ||
1449 IC_RIGHT(dic)->key == IC_RIGHT(ic)->key)) {
1454 if (IS_SYMOP(IC_LEFT(dic)) &&
1455 (IC_LEFT(dic)->key == IC_RESULT(ic)->key ||
1456 IC_LEFT(dic)->key == IC_RIGHT(ic)->key)) {
1461 if (POINTER_SET(dic) &&
1462 IC_RESULT(dic)->key == IC_RESULT(ic)->key ) {
1469 return 0 ; /* did not find */
1471 /* if the result is on stack or iaccess then it must be
1472 the same atleast one of the operands */
1473 if (OP_SYMBOL(IC_RESULT(ic))->onStack ||
1474 OP_SYMBOL(IC_RESULT(ic))->iaccess ) {
1476 /* the operation has only one symbol
1477 operator then we can pack */
1478 if ((IC_LEFT(dic) && !IS_SYMOP(IC_LEFT(dic))) ||
1479 (IC_RIGHT(dic) && !IS_SYMOP(IC_RIGHT(dic))))
1482 if (!((IC_LEFT(dic) &&
1483 IC_RESULT(ic)->key == IC_LEFT(dic)->key) ||
1485 IC_RESULT(ic)->key == IC_RIGHT(dic)->key)))
1489 /* found the definition */
1490 /* replace the result with the result of */
1491 /* this assignment and remove this assignment */
1492 IC_RESULT(dic) = IC_RESULT(ic) ;
1494 if (IS_ITEMP(IC_RESULT(dic)) && OP_SYMBOL(IC_RESULT(dic))->liveFrom > dic->seq) {
1495 OP_SYMBOL(IC_RESULT(dic))->liveFrom = dic->seq;
1497 /* delete from liverange table also
1498 delete from all the points inbetween and the new
1500 for ( sic = dic; sic != ic ; sic = sic->next ) {
1501 bitVectUnSetBit(sic->rlive,IC_RESULT(ic)->key);
1502 if (IS_ITEMP(IC_RESULT(dic)))
1503 bitVectSetBit(sic->rlive,IC_RESULT(dic)->key);
1506 remiCodeFromeBBlock(ebp,ic);
1507 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
1512 /*-----------------------------------------------------------------*/
1513 /* findAssignToSym : scanning backwards looks for first assig found*/
1514 /*-----------------------------------------------------------------*/
1515 static iCode *findAssignToSym (operand *op,iCode *ic)
1519 for (dic = ic->prev ; dic ; dic = dic->prev) {
1521 /* if definition by assignment */
1522 if (dic->op == '=' &&
1523 !POINTER_SET(dic) &&
1524 IC_RESULT(dic)->key == op->key
1525 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1528 /* we are interested only if defined in far space */
1529 /* or in stack space in case of + & - */
1531 /* if assigned to a non-symbol then return
1533 if (!IS_SYMOP(IC_RIGHT(dic)))
1536 /* if the symbol is in far space then
1538 if (isOperandInFarSpace(IC_RIGHT(dic)))
1541 /* for + & - operations make sure that
1542 if it is on the stack it is the same
1543 as one of the three operands */
1544 if ((ic->op == '+' || ic->op == '-') &&
1545 OP_SYMBOL(IC_RIGHT(dic))->onStack) {
1547 if ( IC_RESULT(ic)->key != IC_RIGHT(dic)->key &&
1548 IC_LEFT(ic)->key != IC_RIGHT(dic)->key &&
1549 IC_RIGHT(ic)->key != IC_RIGHT(dic)->key)
1557 /* if we find an usage then we cannot delete it */
1558 if (IC_LEFT(dic) && IC_LEFT(dic)->key == op->key)
1561 if (IC_RIGHT(dic) && IC_RIGHT(dic)->key == op->key)
1564 if (POINTER_SET(dic) && IC_RESULT(dic)->key == op->key)
1568 /* now make sure that the right side of dic
1569 is not defined between ic & dic */
1571 iCode *sic = dic->next ;
1573 for (; sic != ic ; sic = sic->next)
1574 if (IC_RESULT(sic) &&
1575 IC_RESULT(sic)->key == IC_RIGHT(dic)->key)
1584 /*-----------------------------------------------------------------*/
1585 /* packRegsForSupport :- reduce some registers for support calls */
1586 /*-----------------------------------------------------------------*/
1587 static int packRegsForSupport (iCode *ic, eBBlock *ebp)
1590 /* for the left & right operand :- look to see if the
1591 left was assigned a true symbol in far space in that
1592 case replace them */
1593 if (IS_ITEMP(IC_LEFT(ic)) &&
1594 OP_SYMBOL(IC_LEFT(ic))->liveTo <= ic->seq) {
1595 iCode *dic = findAssignToSym(IC_LEFT(ic),ic);
1601 /* found it we need to remove it from the
1603 for ( sic = dic; sic != ic ; sic = sic->next )
1604 bitVectUnSetBit(sic->rlive,IC_LEFT(ic)->key);
1606 IC_LEFT(ic)->operand.symOperand =
1607 IC_RIGHT(dic)->operand.symOperand;
1608 IC_LEFT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1609 remiCodeFromeBBlock(ebp,dic);
1610 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1614 /* do the same for the right operand */
1617 IS_ITEMP(IC_RIGHT(ic)) &&
1618 OP_SYMBOL(IC_RIGHT(ic))->liveTo <= ic->seq) {
1619 iCode *dic = findAssignToSym(IC_RIGHT(ic),ic);
1625 /* if this is a subtraction & the result
1626 is a true symbol in far space then don't pack */
1627 if (ic->op == '-' && IS_TRUE_SYMOP(IC_RESULT(dic))) {
1628 link *etype =getSpec(operandType(IC_RESULT(dic)));
1629 if (IN_FARSPACE(SPEC_OCLS(etype)))
1632 /* found it we need to remove it from the
1634 for ( sic = dic; sic != ic ; sic = sic->next )
1635 bitVectUnSetBit(sic->rlive,IC_RIGHT(ic)->key);
1637 IC_RIGHT(ic)->operand.symOperand =
1638 IC_RIGHT(dic)->operand.symOperand;
1639 IC_RIGHT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1641 remiCodeFromeBBlock(ebp,dic);
1642 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1649 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1652 /*-----------------------------------------------------------------*/
1653 /* packRegsForOneuse : - will reduce some registers for single Use */
1654 /*-----------------------------------------------------------------*/
1655 static iCode *packRegsForOneuse (iCode *ic, operand *op , eBBlock *ebp)
1660 /* if returning a literal then do nothing */
1664 /* only upto 2 bytes since we cannot predict
1665 the usage of b, & acc */
1666 if (getSize(operandType(op)) > (fReturnSize - 2) &&
1671 /* this routine will mark the a symbol as used in one
1672 instruction use only && if the defintion is local
1673 (ie. within the basic block) && has only one definition &&
1674 that definiion is either a return value from a
1675 function or does not contain any variables in
1677 uses = bitVectCopy(OP_USES(op));
1678 bitVectUnSetBit(uses,ic->key); /* take away this iCode */
1679 if (!bitVectIsZero(uses)) /* has other uses */
1682 /* if it has only one defintion */
1683 if (bitVectnBitsOn(OP_DEFS(op)) > 1)
1684 return NULL ; /* has more than one definition */
1686 /* get the that definition */
1688 hTabItemWithKey(iCodehTab,
1689 bitVectFirstBit(OP_DEFS(op)))))
1692 /* found the definition now check if it is local */
1693 if (dic->seq < ebp->fSeq ||
1694 dic->seq > ebp->lSeq)
1695 return NULL ; /* non-local */
1697 /* now check if it is the return from
1699 if (dic->op == CALL || dic->op == PCALL ) {
1700 if (ic->op != SEND && ic->op != RETURN) {
1701 /* OP_SYMBOL(op)->ruonly = 1; */
1708 /* otherwise check that the definition does
1709 not contain any symbols in far space */
1710 if (isOperandInFarSpace(IC_LEFT(dic)) ||
1711 isOperandInFarSpace(IC_RIGHT(dic)) ||
1712 IS_OP_RUONLY(IC_LEFT(ic)) ||
1713 IS_OP_RUONLY(IC_RIGHT(ic)) ) {
1717 /* if pointer set then make sure the pointer
1719 if (POINTER_SET(dic) &&
1720 !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1723 if (POINTER_GET(dic) &&
1724 !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1729 /* also make sure the intervenening instructions
1730 don't have any thing in far space */
1731 for (dic = dic->next ; dic && dic != ic ; dic = dic->next) {
1733 /* if there is an intervening function call then no */
1734 if (dic->op == CALL || dic->op == PCALL)
1736 /* if pointer set then make sure the pointer
1738 if (POINTER_SET(dic) &&
1739 !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1742 if (POINTER_GET(dic) &&
1743 !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1746 /* if address of & the result is remat the okay */
1747 if (dic->op == ADDRESS_OF &&
1748 OP_SYMBOL(IC_RESULT(dic))->remat)
1751 /* if operand has size of three or more & this
1752 operation is a '*','/' or '%' then 'b' may
1754 if (( dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1755 getSize(operandType(op)) >= 3)
1758 /* if left or right or result is in far space */
1759 if (isOperandInFarSpace(IC_LEFT(dic)) ||
1760 isOperandInFarSpace(IC_RIGHT(dic)) ||
1761 isOperandInFarSpace(IC_RESULT(dic)) ||
1762 IS_OP_RUONLY(IC_LEFT(dic)) ||
1763 IS_OP_RUONLY(IC_RIGHT(dic)) ||
1764 IS_OP_RUONLY(IC_RESULT(dic)) ) {
1769 /* OP_SYMBOL(op)->ruonly = 1; */
1774 /*-----------------------------------------------------------------*/
1775 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1776 /*-----------------------------------------------------------------*/
1777 static bool isBitwiseOptimizable (iCode *ic)
1779 link *ltype = getSpec(operandType(IC_LEFT(ic)));
1780 link *rtype = getSpec(operandType(IC_RIGHT(ic)));
1782 /* bitwise operations are considered optimizable
1783 under the following conditions (Jean-Louis VERN)
1795 if ( IS_LITERAL(rtype) ||
1796 (IS_BITVAR(ltype) && IN_BITSPACE(SPEC_OCLS(ltype))))
1802 /*-----------------------------------------------------------------*/
1803 /* packRegsForAccUse - pack registers for acc use */
1804 /*-----------------------------------------------------------------*/
1805 static void packRegsForAccUse (iCode *ic)
1809 /* if + or - then it has to be one byte result */
1810 if ((ic->op == '+' || ic->op == '-')
1811 && getSize(operandType(IC_RESULT(ic))) > 1)
1814 /* if shift operation make sure right side is not a literal */
1815 if (ic->op == RIGHT_OP &&
1816 ( isOperandLiteral(IC_RIGHT(ic)) ||
1817 getSize(operandType(IC_RESULT(ic))) > 1))
1820 if (ic->op == LEFT_OP &&
1821 ( isOperandLiteral(IC_RIGHT(ic)) ||
1822 getSize(operandType(IC_RESULT(ic))) > 1))
1825 if (IS_BITWISE_OP(ic) &&
1826 getSize(operandType(IC_RESULT(ic))) > 1)
1830 /* has only one definition */
1831 if (bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1)
1834 /* has only one use */
1835 if (bitVectnBitsOn(OP_USES(IC_RESULT(ic))) > 1)
1838 /* and the usage immediately follows this iCode */
1839 if (!(uic = hTabItemWithKey(iCodehTab,
1840 bitVectFirstBit(OP_USES(IC_RESULT(ic))))))
1843 if (ic->next != uic)
1846 /* if it is a conditional branch then we definitely can */
1847 if (uic->op == IFX )
1850 if ( uic->op == JUMPTABLE )
1853 /* if the usage is not is an assignment
1854 or an arithmetic / bitwise / shift operation then not */
1855 if (POINTER_SET(uic) &&
1856 getSize(aggrToPtr(operandType(IC_RESULT(uic)),FALSE)) > 1)
1859 if (uic->op != '=' &&
1860 !IS_ARITHMETIC_OP(uic) &&
1861 !IS_BITWISE_OP(uic) &&
1862 uic->op != LEFT_OP &&
1863 uic->op != RIGHT_OP )
1866 /* if used in ^ operation then make sure right is not a
1868 if (uic->op == '^' && isOperandLiteral(IC_RIGHT(uic)))
1871 /* if shift operation make sure right side is not a literal */
1872 if (uic->op == RIGHT_OP &&
1873 ( isOperandLiteral(IC_RIGHT(uic)) ||
1874 getSize(operandType(IC_RESULT(uic))) > 1))
1877 if (uic->op == LEFT_OP &&
1878 ( isOperandLiteral(IC_RIGHT(uic)) ||
1879 getSize(operandType(IC_RESULT(uic))) > 1))
1882 /* make sure that the result of this icode is not on the
1883 stack, since acc is used to compute stack offset */
1884 if (IS_TRUE_SYMOP(IC_RESULT(uic)) &&
1885 OP_SYMBOL(IC_RESULT(uic))->onStack)
1888 /* if either one of them in far space then we cannot */
1889 if ((IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1890 isOperandInFarSpace(IC_LEFT(uic))) ||
1891 (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1892 isOperandInFarSpace(IC_RIGHT(uic))))
1895 /* if the usage has only one operand then we can */
1896 if (IC_LEFT(uic) == NULL ||
1897 IC_RIGHT(uic) == NULL)
1900 /* make sure this is on the left side if not
1901 a '+' since '+' is commutative */
1902 if (ic->op != '+' &&
1903 IC_LEFT(uic)->key != IC_RESULT(ic)->key)
1906 /* if one of them is a literal then we can */
1907 if ((IC_LEFT(uic) && IS_OP_LITERAL(IC_LEFT(uic))) ||
1908 (IC_RIGHT(uic) && IS_OP_LITERAL(IC_RIGHT(uic)))) {
1909 OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
1913 /* if the other one is not on stack then we can */
1914 if (IC_LEFT(uic)->key == IC_RESULT(ic)->key &&
1915 (IS_ITEMP(IC_RIGHT(uic)) ||
1916 (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1917 !OP_SYMBOL(IC_RIGHT(uic))->onStack)))
1920 if (IC_RIGHT(uic)->key == IC_RESULT(ic)->key &&
1921 (IS_ITEMP(IC_LEFT(uic)) ||
1922 (IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1923 !OP_SYMBOL(IC_LEFT(uic))->onStack)))
1929 OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
1934 /*-----------------------------------------------------------------*/
1935 /* packForPush - hueristics to reduce iCode for pushing */
1936 /*-----------------------------------------------------------------*/
1937 static void packForPush(iCode *ic, eBBlock *ebp)
1941 if (ic->op != IPUSH || !IS_ITEMP(IC_LEFT(ic)))
1944 /* must have only definition & one usage */
1945 if (bitVectnBitsOn(OP_DEFS(IC_LEFT(ic))) != 1 ||
1946 bitVectnBitsOn(OP_USES(IC_LEFT(ic))) != 1 )
1949 /* find the definition */
1950 if (!(dic = hTabItemWithKey(iCodehTab,
1951 bitVectFirstBit(OP_DEFS(IC_LEFT(ic))))))
1954 if (dic->op != '=' || POINTER_SET(dic))
1957 /* we now we know that it has one & only one def & use
1958 and the that the definition is an assignment */
1959 IC_LEFT(ic) = IC_RIGHT(dic);
1961 remiCodeFromeBBlock(ebp,dic);
1962 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1965 /*-----------------------------------------------------------------*/
1966 /* packRegisters - does some transformations to reduce register */
1968 /*-----------------------------------------------------------------*/
1969 static void packRegisters (eBBlock *ebp)
1978 /* look for assignments of the form */
1979 /* iTempNN = TRueSym (someoperation) SomeOperand */
1981 /* TrueSym := iTempNN:1 */
1982 for ( ic = ebp->sch ; ic ; ic = ic->next ) {
1985 /* find assignment of the form TrueSym := iTempNN:1 */
1986 if (ic->op == '=' && !POINTER_SET(ic))
1987 change += packRegsForAssign(ic,ebp);
1994 for ( ic = ebp->sch ; ic ; ic = ic->next ) {
1996 /* if this is an itemp & result of a address of a true sym
1997 then mark this as rematerialisable */
1998 if (ic->op == ADDRESS_OF &&
1999 IS_ITEMP(IC_RESULT(ic)) &&
2000 IS_TRUE_SYMOP(IC_LEFT(ic)) &&
2001 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2002 !OP_SYMBOL(IC_LEFT(ic))->onStack ) {
2004 OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2005 OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2006 OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2010 /* if straight assignment then carry remat flag if
2011 this is the only definition */
2012 if (ic->op == '=' &&
2014 IS_SYMOP(IC_RIGHT(ic)) &&
2015 OP_SYMBOL(IC_RIGHT(ic))->remat &&
2016 bitVectnBitsOn(OP_SYMBOL(IC_RESULT(ic))->defs) <= 1) {
2018 OP_SYMBOL(IC_RESULT(ic))->remat =
2019 OP_SYMBOL(IC_RIGHT(ic))->remat;
2020 OP_SYMBOL(IC_RESULT(ic))->rematiCode =
2021 OP_SYMBOL(IC_RIGHT(ic))->rematiCode ;
2024 /* if this is a +/- operation with a rematerizable
2025 then mark this as rematerializable as well only
2026 if the literal value is within the range -255 and + 255
2027 the assembler cannot handle it other wise */
2028 if ((ic->op == '+' || ic->op == '-') &&
2030 (IS_SYMOP(IC_LEFT(ic)) &&
2031 IS_ITEMP(IC_RESULT(ic)) &&
2032 OP_SYMBOL(IC_LEFT(ic))->remat &&
2033 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2034 IS_OP_LITERAL(IC_RIGHT(ic))) ) {
2036 int i = operandLitValue(IC_RIGHT(ic));
2037 if ( i < 255 && i > -255) {
2038 OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2039 OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2040 OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2044 /* mark the pointer usages */
2045 if (POINTER_SET(ic))
2046 OP_SYMBOL(IC_RESULT(ic))->uptr = 1;
2048 if (POINTER_GET(ic))
2049 OP_SYMBOL(IC_LEFT(ic))->uptr = 1;
2051 /* if the condition of an if instruction
2052 is defined in the previous instruction then
2053 mark the itemp as a conditional */
2054 if ((IS_CONDITIONAL(ic) ||
2055 ( ( ic->op == BITWISEAND ||
2058 isBitwiseOptimizable(ic))) &&
2059 ic->next && ic->next->op == IFX &&
2060 isOperandEqual(IC_RESULT(ic),IC_COND(ic->next)) &&
2061 OP_SYMBOL(IC_RESULT(ic))->liveTo <= ic->next->seq) {
2063 OP_SYMBOL(IC_RESULT(ic))->regType = REG_CND;
2067 /* reduce for support function calls */
2068 /* if (ic->supportRtn || ic->op == '+' || ic->op == '-' ) */
2069 /* packRegsForSupport (ic,ebp); */
2071 /* some cases the redundant moves can
2072 can be eliminated for return statements */
2073 /* if ((ic->op == RETURN || ic->op == SEND) && */
2074 /* !isOperandInFarSpace(IC_LEFT(ic)) && */
2075 /* !options.model) */
2076 /* packRegsForOneuse (ic,IC_LEFT(ic),ebp); */
2078 /* if pointer set & left has a size more than
2079 one and right is not in far space */
2080 /* if (POINTER_SET(ic) && */
2081 /* !isOperandInFarSpace(IC_RIGHT(ic)) && */
2082 /* !OP_SYMBOL(IC_RESULT(ic))->remat && */
2083 /* !IS_OP_RUONLY(IC_RIGHT(ic)) && */
2084 /* getSize(aggrToPtr(operandType(IC_RESULT(ic)),FALSE)) > 1 ) */
2086 /* packRegsForOneuse (ic,IC_RESULT(ic),ebp); */
2088 /* if pointer get */
2089 /* if (POINTER_GET(ic) && */
2090 /* !isOperandInFarSpace(IC_RESULT(ic))&& */
2091 /* !OP_SYMBOL(IC_LEFT(ic))->remat && */
2092 /* !IS_OP_RUONLY(IC_RESULT(ic)) && */
2093 /* getSize(aggrToPtr(operandType(IC_LEFT(ic)),FALSE)) > 1 ) */
2095 /* packRegsForOneuse (ic,IC_LEFT(ic),ebp); */
2098 /* if this is cast for intergral promotion then
2099 check if only use of the definition of the
2100 operand being casted/ if yes then replace
2101 the result of that arithmetic operation with
2102 this result and get rid of the cast */
2103 if (ic->op == CAST) {
2104 link *fromType = operandType(IC_RIGHT(ic));
2105 link *toType = operandType(IC_LEFT(ic));
2107 if (IS_INTEGRAL(fromType) && IS_INTEGRAL(toType) &&
2108 getSize(fromType) != getSize(toType) ) {
2110 iCode *dic = packRegsForOneuse(ic,IC_RIGHT(ic),ebp);
2112 if (IS_ARITHMETIC_OP(dic)) {
2113 IC_RESULT(dic) = IC_RESULT(ic);
2114 remiCodeFromeBBlock(ebp,ic);
2115 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2118 OP_SYMBOL(IC_RIGHT(ic))->ruonly = 0;
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))) == 1) {
2126 iCode *dic = packRegsForOneuse (ic,IC_RIGHT(ic),ebp);
2128 IC_RESULT(dic) = IC_RESULT(ic);
2129 remiCodeFromeBBlock(ebp,ic);
2130 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2138 iTempNN := (some variable in farspace) V1
2143 /* if (ic->op == IPUSH ) { */
2144 /* packForPush(ic,ebp); */
2148 /* pack registers for accumulator use, when the
2149 result of an arithmetic or bit wise operation
2150 has only one use, that use is immediately following
2151 the defintion and the using iCode has only one
2152 operand or has two operands but one is literal &
2153 the result of that operation is not on stack then
2154 we can leave the result of this operation in acc:b
2156 /* if ((IS_ARITHMETIC_OP(ic) */
2158 /* || IS_BITWISE_OP(ic) */
2160 /* || ic->op == LEFT_OP || ic->op == RIGHT_OP */
2163 /* IS_ITEMP(IC_RESULT(ic)) && */
2164 /* getSize(operandType(IC_RESULT(ic))) <= 2) */
2166 /* packRegsForAccUse (ic); */
2171 /*-----------------------------------------------------------------*/
2172 /* preAssignParms - we have a leaf function preassign registers */
2173 /*-----------------------------------------------------------------*/
2174 static void preAssignParms (iCode *ic)
2177 /* look for receives and assign registers
2178 to the result of the receives */
2180 /* if it is a receive */
2181 if (ic->op == RECEIVE) {
2182 symbol *r = OP_SYMBOL(IC_RESULT(ic));
2183 int size = getSize(r->type);
2184 if (r->regType == REG_GPR) {
2187 r->regs[j++] = ®sAVR[i++];
2188 regsAVR[i-1].isFree = 0;
2190 /* put in the regassigned vector */
2191 _G.regAssigned = bitVectSetBit(_G.regAssigned,r->key);
2193 /* not a GPR then we should mark as free */
2195 regsAVR[i++].isFree =1;
2201 /* mark anything remaining as free */
2202 while (i <= R23_IDX)
2203 regsAVR[i++].isFree =1;
2206 /*-----------------------------------------------------------------*/
2207 /* setdefaultRegs - do setup stuff for register allocation */
2208 /*-----------------------------------------------------------------*/
2209 static void setDefaultRegs(eBBlock **ebbs,int count)
2212 /* if no pointer registers required in this function
2213 then mark r26-27 & r30-r31 as GPR & free */
2214 if (!avr_ptrRegReq) {
2215 regsAVR[R26_IDX].isFree =
2216 regsAVR[R27_IDX].isFree =
2217 regsAVR[R30_IDX].isFree =
2218 regsAVR[R31_IDX].isFree = 1;
2219 regsAVR[R26_IDX].type =
2220 regsAVR[R27_IDX].type =
2221 regsAVR[R30_IDX].type =
2222 regsAVR[R31_IDX].type = REG_GPR ;
2224 regsAVR[R26_IDX].isFree =
2225 regsAVR[R27_IDX].isFree =
2226 regsAVR[R30_IDX].isFree =
2227 regsAVR[R31_IDX].isFree = 1;
2228 regsAVR[R26_IDX].type =
2229 regsAVR[R27_IDX].type =
2230 regsAVR[R30_IDX].type =
2231 regsAVR[R31_IDX].type = REG_PTR ;
2234 /* registers 0-1 / 24-25 used as scratch */
2235 regsAVR[R0_IDX].isFree =
2236 regsAVR[R1_IDX].isFree =
2237 regsAVR[R24_IDX].isFree =
2238 regsAVR[R25_IDX].isFree = 0;
2240 /* if this has no function calls then we need
2241 to do something special
2242 a) pre-assign registers to parameters RECEIVE
2243 b) mark the remaining parameter regs as free */
2244 if (!currFunc->hasFcall) {
2245 preAssignParms(ebbs[0]->sch);
2248 for (i= R16_IDX ; i <= R23_IDX ;i++)
2249 regsAVR[i].isFree = 0;
2252 /* Y - is not allocated (it is the stack frame) */
2253 regsAVR[R28_IDX].isFree =
2254 regsAVR[R28_IDX].isFree =0;
2257 /*-----------------------------------------------------------------*/
2258 /* assignRegisters - assigns registers to each live range as need */
2259 /*-----------------------------------------------------------------*/
2260 void avr_assignRegisters (eBBlock **ebbs, int count)
2265 setToNull((void *)&_G.funcrUsed);
2266 avr_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2268 /* setup other default register allocation */
2269 /* change assignments this will remove some
2270 live ranges reducing some register pressure */
2271 for (i = 0 ; i < count ;i++ )
2272 packRegisters (ebbs[i]);
2274 if (options.dump_pack)
2275 dumpEbbsToFileExt(".dumppack",ebbs,count);
2277 /* first determine for each live range the number of
2278 registers & the type of registers required for each */
2281 /* setup the default registers */
2282 setDefaultRegs(ebbs,count);
2284 /* and serially allocate registers */
2285 serialRegAssign(ebbs,count);
2287 /* if stack was extended then tell the user */
2288 if (_G.stackExtend) {
2289 /* werror(W_TOOMANY_SPILS,"stack", */
2290 /* _G.stackExtend,currFunc->name,""); */
2291 _G.stackExtend = 0 ;
2294 if (_G.dataExtend) {
2295 /* werror(W_TOOMANY_SPILS,"data space", */
2296 /* _G.dataExtend,currFunc->name,""); */
2300 /* after that create the register mask
2301 for each of the instruction */
2302 createRegMask (ebbs,count);
2304 /* redo that offsets for stacked automatic variables */
2305 redoStackOffsets ();
2307 if (options.dump_rassgn)
2308 dumpEbbsToFileExt(".dumprassgn",ebbs,count);
2310 /* now get back the chain */
2311 ic = iCodeLabelOptimize(iCodeFromeBBlock (ebbs,count));
2316 /* free up any _G.stackSpil locations allocated */
2317 applyToSet(_G.stackSpil,deallocStackSpil);
2319 setToNull((void **)&_G.stackSpil);
2320 setToNull((void **)&_G.spiltSet);
2321 /* mark all registers as free */