1 /*------------------------------------------------------------------------
3 SDCCralloc.c - source file for register allocation. (8051) specific
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
6 Added Pic Port T.scott Dattalo scott@dattalo.com (2000)
8 This program is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 2, or (at your option) any
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 In other words, you are welcome to use, share and improve this program.
23 You are forbidden to forbid anyone else to use, share and improve
24 what you give them. Help stamp out software-hoarding!
25 -------------------------------------------------------------------------*/
31 /*-----------------------------------------------------------------*/
32 /* At this point we start getting processor specific although */
33 /* some routines are non-processor specific & can be reused when */
34 /* targetting other processors. The decision for this will have */
35 /* to be made on a routine by routine basis */
36 /* routines used to pack registers are most definitely not reusable*/
37 /* since the pack the registers depending strictly on the MCU */
38 /*-----------------------------------------------------------------*/
40 extern void genpic14Code(iCode *);
49 bitVect *funcrUsed; /* registers used in a function */
54 /* Shared with gen.c */
55 int pic14_ptrRegReq; /* one byte pointer register required */
61 {PIC_INDF, 0, "INDF", "INDR", "0", 0, 1},
62 {PIC_GPR, 0, "r0x0C", "r0x0C", "0x0C", 0x0C, 1},
63 {PIC_GPR, 0, "r0x0D", "r0x0C", "0x0D", 0x0D, 1},
64 {PIC_GPR, 0, "r0x0E", "r0x0C", "0x0E", 0x0E, 1},
65 {PIC_GPR, 0, "r0x0F", "r0x0C", "0x0F", 0x0F, 1},
66 {PIC_GPR, 0, "r0x10", "r0x10", "0x10", 0x10, 1},
67 {PIC_GPR, 0, "r0x11", "r0x11", "0x11", 0x11, 1},
68 {PIC_GPR, 0, "r0x12", "r0x12", "0x12", 0x12, 1},
69 {PIC_GPR, 0, "r0x13", "r0x13", "0x13", 0x13, 1},
70 {PIC_GPR, 0, "r0x14", "r0x14", "0x14", 0x14, 1},
71 {PIC_GPR, 0, "r0x15", "r0x15", "0x15", 0x15, 1},
72 {PIC_GPR, 0, "r0x16", "r0x16", "0x16", 0x16, 1},
73 {PIC_GPR, 0, "r0x17", "r0x17", "0x17", 0x17, 1},
74 {PIC_GPR, 0, "r0x18", "r0x18", "0x18", 0x18, 1},
75 {PIC_GPR, 0, "r0x19", "r0x19", "0x19", 0x19, 1},
76 {PIC_GPR, 0, "r0x1A", "r0x1A", "0x1A", 0x1A, 1},
77 {PIC_GPR, 0, "r0x1B", "r0x1B", "0x1B", 0x1B, 1},
78 {PIC_GPR, 0, "r0x1C", "r0x1C", "0x1C", 0x1C, 1},
79 {PIC_GPR, 0, "r0x1D", "r0x1D", "0x1D", 0x1D, 1},
80 {PIC_GPR, 0, "r0x1E", "r0x1E", "0x1E", 0x1E, 1},
81 {PIC_GPR, 0, "r0x1F", "r0x1F", "0x1F", 0x1F, 1},
85 int pic14_nRegs = sizeof(regspic14) / sizeof(regs);
86 static void spillThis (symbol *);
88 /*-----------------------------------------------------------------*/
89 /* allocReg - allocates register of given type */
90 /*-----------------------------------------------------------------*/
91 static regs *allocReg (short type)
95 for ( i = 0 ; i < pic14_nRegs ; i++ ) {
97 /* if type is given as 0 then any
98 free register will do */
100 regspic14[i].isFree ) {
101 regspic14[i].isFree = 0;
104 bitVectSetBit(currFunc->regsUsed,i);
105 return ®spic14[i];
107 /* other wise look for specific type
109 if (regspic14[i].isFree &&
110 regspic14[i].type == type) {
111 regspic14[i].isFree = 0;
114 bitVectSetBit(currFunc->regsUsed,i);
115 return ®spic14[i];
121 /*-----------------------------------------------------------------*/
122 /* pic14_regWithIdx - returns pointer to register wit index number */
123 /*-----------------------------------------------------------------*/
124 regs *pic14_regWithIdx (int idx)
128 for (i=0;i < pic14_nRegs;i++)
129 if (regspic14[i].rIdx == idx)
130 return ®spic14[i];
132 werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
133 "regWithIdx not found");
137 /*-----------------------------------------------------------------*/
138 /* freeReg - frees a register */
139 /*-----------------------------------------------------------------*/
140 static void freeReg (regs *reg)
146 /*-----------------------------------------------------------------*/
147 /* nFreeRegs - returns number of free registers */
148 /*-----------------------------------------------------------------*/
149 static int nFreeRegs (int type)
154 for (i = 0 ; i < pic14_nRegs; i++ )
155 if (regspic14[i].isFree && regspic14[i].type == type)
160 /*-----------------------------------------------------------------*/
161 /* nfreeRegsType - free registers with type */
162 /*-----------------------------------------------------------------*/
163 static int nfreeRegsType (int type)
166 if (type == REG_PTR) {
167 if ((nfr = nFreeRegs(type)) == 0)
168 return nFreeRegs(REG_GPR);
171 return nFreeRegs(type);
175 /*-----------------------------------------------------------------*/
176 /* allDefsOutOfRange - all definitions are out of a range */
177 /*-----------------------------------------------------------------*/
178 static bool allDefsOutOfRange (bitVect *defs,int fseq, int toseq)
185 for ( i = 0 ;i < defs->size ; i++ ) {
188 if (bitVectBitValue(defs,i) &&
189 (ic = hTabItemWithKey(iCodehTab,i)) &&
190 ( ic->seq >= fseq && ic->seq <= toseq))
199 /*-----------------------------------------------------------------*/
200 /* computeSpillable - given a point find the spillable live ranges */
201 /*-----------------------------------------------------------------*/
202 static bitVect *computeSpillable (iCode *ic)
206 /* spillable live ranges are those that are live at this
207 point . the following categories need to be subtracted
209 a) - those that are already spilt
210 b) - if being used by this one
211 c) - defined by this one */
213 spillable = bitVectCopy(ic->rlive);
215 bitVectCplAnd(spillable,_G.spiltSet); /* those already spilt */
217 bitVectCplAnd(spillable,ic->uses); /* used in this one */
218 bitVectUnSetBit(spillable,ic->defKey);
219 spillable = bitVectIntersect(spillable,_G.regAssigned);
224 /*-----------------------------------------------------------------*/
225 /* noSpilLoc - return true if a variable has no spil location */
226 /*-----------------------------------------------------------------*/
227 static int noSpilLoc (symbol *sym, eBBlock *ebp,iCode *ic)
229 return (sym->usl.spillLoc ? 0 : 1);
232 /*-----------------------------------------------------------------*/
233 /* hasSpilLoc - will return 1 if the symbol has spil location */
234 /*-----------------------------------------------------------------*/
235 static int hasSpilLoc (symbol *sym, eBBlock *ebp, iCode *ic)
237 return (sym->usl.spillLoc ? 1 : 0);
240 /*-----------------------------------------------------------------*/
241 /* directSpilLoc - will return 1 if the splilocation is in direct */
242 /*-----------------------------------------------------------------*/
243 static int directSpilLoc (symbol *sym, eBBlock *ebp, iCode *ic)
245 if ( sym->usl.spillLoc &&
246 (IN_DIRSPACE(SPEC_OCLS(sym->usl.spillLoc->etype))))
252 /*-----------------------------------------------------------------*/
253 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location*/
254 /* but is not used as a pointer */
255 /*-----------------------------------------------------------------*/
256 static int hasSpilLocnoUptr (symbol *sym, eBBlock *ebp, iCode *ic)
258 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
261 /*-----------------------------------------------------------------*/
262 /* rematable - will return 1 if the remat flag is set */
263 /*-----------------------------------------------------------------*/
264 static int rematable (symbol *sym, eBBlock *ebp, iCode *ic)
269 /*-----------------------------------------------------------------*/
270 /* notUsedInBlock - not used in this block */
271 /*-----------------------------------------------------------------*/
272 static int notUsedInBlock (symbol *sym, eBBlock *ebp, iCode *ic)
274 return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs) &&
275 allDefsOutOfRange (sym->defs,ebp->fSeq,ebp->lSeq));
276 /* return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs)); */
279 /*-----------------------------------------------------------------*/
280 /* notUsedInRemaining - not used or defined in remain of the block */
281 /*-----------------------------------------------------------------*/
282 static int notUsedInRemaining (symbol *sym, eBBlock *ebp, iCode *ic)
284 return ((usedInRemaining (operandFromSymbol(sym),ic) ? 0 : 1) &&
285 allDefsOutOfRange (sym->defs,ebp->fSeq,ebp->lSeq));
288 /*-----------------------------------------------------------------*/
289 /* allLRs - return true for all */
290 /*-----------------------------------------------------------------*/
291 static int allLRs (symbol *sym, eBBlock *ebp, iCode *ic)
296 /*-----------------------------------------------------------------*/
297 /* liveRangesWith - applies function to a given set of live range */
298 /*-----------------------------------------------------------------*/
299 static set *liveRangesWith (bitVect *lrs, int (func)(symbol *,eBBlock *, iCode *),
300 eBBlock *ebp, iCode *ic)
305 if (!lrs || !lrs->size)
308 for ( i = 1 ; i < lrs->size ; i++ ) {
310 if (!bitVectBitValue(lrs,i))
313 /* if we don't find it in the live range
314 hash table we are in serious trouble */
315 if (!(sym = hTabItemWithKey(liveRanges,i))) {
316 werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
317 "liveRangesWith could not find liveRange");
321 if (func(sym,ebp,ic) && bitVectBitValue(_G.regAssigned,sym->key))
322 addSetHead(&rset,sym);
329 /*-----------------------------------------------------------------*/
330 /* leastUsedLR - given a set determines which is the least used */
331 /*-----------------------------------------------------------------*/
332 static symbol *leastUsedLR (set *sset)
334 symbol *sym = NULL, *lsym = NULL ;
336 sym = lsym = setFirstItem(sset);
341 for (; lsym; lsym = setNextItem(sset)) {
343 /* if usage is the same then prefer
344 the spill the smaller of the two */
345 if ( lsym->used == sym->used )
346 if (getSize(lsym->type) < getSize(sym->type))
350 if (lsym->used < sym->used )
355 setToNull((void **)&sset);
360 /*-----------------------------------------------------------------*/
361 /* noOverLap - will iterate through the list looking for over lap */
362 /*-----------------------------------------------------------------*/
363 static int noOverLap (set *itmpStack, symbol *fsym)
368 for (sym = setFirstItem(itmpStack); sym;
369 sym = setNextItem(itmpStack)) {
370 if (sym->liveTo > fsym->liveFrom )
378 /*-----------------------------------------------------------------*/
379 /* isFree - will return 1 if the a free spil location is found */
380 /*-----------------------------------------------------------------*/
381 static DEFSETFUNC(isFree)
384 V_ARG(symbol **,sloc);
385 V_ARG(symbol *,fsym);
387 /* if already found */
391 /* if it is free && and the itmp assigned to
392 this does not have any overlapping live ranges
393 with the one currently being assigned and
394 the size can be accomodated */
396 noOverLap(sym->usl.itmpStack,fsym) &&
397 getSize(sym->type) >= getSize(fsym->type)) {
405 /*-----------------------------------------------------------------*/
406 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
407 /*-----------------------------------------------------------------*/
408 static void spillLRWithPtrReg (symbol *forSym)
414 if (!_G.regAssigned ||
415 bitVectIsZero(_G.regAssigned))
418 r0 = pic14_regWithIdx(R0_IDX);
419 r1 = pic14_regWithIdx(R1_IDX);
421 /* for all live ranges */
422 for (lrsym = hTabFirstItem(liveRanges,&k) ; lrsym ;
423 lrsym = hTabNextItem(liveRanges,&k) ) {
426 /* if no registers assigned to it or
428 /* if it does not overlap with this then
429 not need to spill it */
431 if (lrsym->isspilt || !lrsym->nRegs ||
432 (lrsym->liveTo < forSym->liveFrom))
435 /* go thru the registers : if it is either
436 r0 or r1 then spil it */
437 for (j = 0 ; j < lrsym->nRegs ; j++ )
438 if (lrsym->regs[j] == r0 ||
439 lrsym->regs[j] == r1 ) {
447 /*-----------------------------------------------------------------*/
448 /* createStackSpil - create a location on the stack to spil */
449 /*-----------------------------------------------------------------*/
450 static symbol *createStackSpil (symbol *sym)
453 int useXstack, model, noOverlay;
457 /* first go try and find a free one that is already
458 existing on the stack */
459 if (applyToSet(_G.stackSpil,isFree,&sloc, sym)) {
460 /* found a free one : just update & return */
461 sym->usl.spillLoc = sloc;
464 addSetHead(&sloc->usl.itmpStack,sym);
468 /* could not then have to create one , this is the hard part
469 we need to allocate this on the stack : this is really a
470 hack!! but cannot think of anything better at this time */
472 if (sprintf(slocBuffer,"sloc%d",_G.slocNum++) >= sizeof(slocBuffer))
474 fprintf(stderr, "***Internal error: slocBuffer overflowed: %s:%d\n",
479 sloc = newiTemp(slocBuffer);
481 /* set the type to the spilling symbol */
482 sloc->type = copyLinkChain(sym->type);
483 sloc->etype = getSpec(sloc->type);
484 SPEC_SCLS(sloc->etype) = S_DATA ;
485 SPEC_EXTR(sloc->etype) = 0;
487 /* we don't allow it to be allocated`
488 onto the external stack since : so we
489 temporarily turn it off ; we also
490 turn off memory model to prevent
491 the spil from going to the external storage
492 and turn off overlaying
495 useXstack = options.useXstack;
496 model = options.model;
497 noOverlay = options.noOverlay;
498 options.noOverlay = 1;
499 options.model = options.useXstack = 0;
503 options.useXstack = useXstack;
504 options.model = model;
505 options.noOverlay = noOverlay;
506 sloc->isref = 1; /* to prevent compiler warning */
508 /* if it is on the stack then update the stack */
509 if (IN_STACK(sloc->etype)) {
510 currFunc->stack += getSize(sloc->type);
511 _G.stackExtend += getSize(sloc->type);
513 _G.dataExtend += getSize(sloc->type);
515 /* add it to the _G.stackSpil set */
516 addSetHead(&_G.stackSpil,sloc);
517 sym->usl.spillLoc = sloc;
520 /* add it to the set of itempStack set
521 of the spill location */
522 addSetHead(&sloc->usl.itmpStack,sym);
526 /*-----------------------------------------------------------------*/
527 /* isSpiltOnStack - returns true if the spil location is on stack */
528 /*-----------------------------------------------------------------*/
529 static bool isSpiltOnStack (symbol *sym)
539 /* if (sym->_G.stackSpil) */
542 if (!sym->usl.spillLoc)
545 etype = getSpec(sym->usl.spillLoc->type);
552 /*-----------------------------------------------------------------*/
553 /* spillThis - spils a specific operand */
554 /*-----------------------------------------------------------------*/
555 static void spillThis (symbol *sym)
558 /* if this is rematerializable or has a spillLocation
559 we are okay, else we need to create a spillLocation
561 if (!(sym->remat || sym->usl.spillLoc))
562 createStackSpil (sym);
565 /* mark it has spilt & put it in the spilt set */
567 _G.spiltSet = bitVectSetBit(_G.spiltSet,sym->key);
569 bitVectUnSetBit(_G.regAssigned,sym->key);
571 for (i = 0 ; i < sym->nRegs ; i++)
574 freeReg(sym->regs[i]);
578 /* if spilt on stack then free up r0 & r1
579 if they could have been assigned to some
581 if (!pic14_ptrRegReq && isSpiltOnStack(sym)) {
583 spillLRWithPtrReg(sym);
586 if (sym->usl.spillLoc && !sym->remat)
587 sym->usl.spillLoc->allocreq = 1;
591 /*-----------------------------------------------------------------*/
592 /* selectSpil - select a iTemp to spil : rather a simple procedure */
593 /*-----------------------------------------------------------------*/
594 static symbol *selectSpil (iCode *ic, eBBlock *ebp, symbol *forSym)
596 bitVect *lrcs= NULL ;
600 /* get the spillable live ranges */
601 lrcs = computeSpillable (ic);
603 /* get all live ranges that are rematerizable */
604 if ((selectS = liveRangesWith(lrcs,rematable,ebp,ic))) {
606 /* return the least used of these */
607 return leastUsedLR(selectS);
610 /* get live ranges with spillLocations in direct space */
611 if ((selectS = liveRangesWith(lrcs,directSpilLoc,ebp,ic))) {
612 sym = leastUsedLR(selectS);
613 strcpy(sym->rname,(sym->usl.spillLoc->rname[0] ?
614 sym->usl.spillLoc->rname :
615 sym->usl.spillLoc->name));
617 /* mark it as allocation required */
618 sym->usl.spillLoc->allocreq = 1;
622 /* if the symbol is local to the block then */
623 if (forSym->liveTo < ebp->lSeq) {
625 /* check if there are any live ranges allocated
626 to registers that are not used in this block */
627 if (!_G.blockSpil && (selectS = liveRangesWith(lrcs,notUsedInBlock,ebp,ic))) {
628 sym = leastUsedLR(selectS);
629 /* if this is not rematerializable */
637 /* check if there are any live ranges that not
638 used in the remainder of the block */
639 if (!_G.blockSpil && (selectS = liveRangesWith(lrcs,notUsedInRemaining,ebp,ic))) {
640 sym = leastUsedLR (selectS);
649 /* find live ranges with spillocation && not used as pointers */
650 if ((selectS = liveRangesWith(lrcs,hasSpilLocnoUptr,ebp,ic))) {
652 sym = leastUsedLR(selectS);
653 /* mark this as allocation required */
654 sym->usl.spillLoc->allocreq = 1;
658 /* find live ranges with spillocation */
659 if ((selectS = liveRangesWith(lrcs,hasSpilLoc,ebp,ic))) {
661 sym = leastUsedLR(selectS);
662 sym->usl.spillLoc->allocreq = 1;
666 /* couldn't find then we need to create a spil
667 location on the stack , for which one? the least
669 if ((selectS = liveRangesWith(lrcs,noSpilLoc,ebp,ic))) {
671 /* return a created spil location */
672 sym = createStackSpil(leastUsedLR(selectS));
673 sym->usl.spillLoc->allocreq = 1;
677 /* this is an extreme situation we will spill
678 this one : happens very rarely but it does happen */
679 spillThis ( forSym );
684 /*-----------------------------------------------------------------*/
685 /* spilSomething - spil some variable & mark registers as free */
686 /*-----------------------------------------------------------------*/
687 static bool spilSomething (iCode *ic, eBBlock *ebp, symbol *forSym)
692 /* get something we can spil */
693 ssym = selectSpil(ic,ebp,forSym);
695 /* mark it as spilt */
697 _G.spiltSet = bitVectSetBit(_G.spiltSet,ssym->key);
699 /* mark it as not register assigned &
700 take it away from the set */
701 bitVectUnSetBit(_G.regAssigned,ssym->key);
703 /* mark the registers as free */
704 for (i = 0 ; i < ssym->nRegs ;i++ )
706 freeReg(ssym->regs[i]);
708 /* if spilt on stack then free up r0 & r1
709 if they could have been assigned to as gprs */
710 if (!pic14_ptrRegReq && isSpiltOnStack(ssym) ) {
712 spillLRWithPtrReg(ssym);
715 /* if this was a block level spil then insert push & pop
716 at the start & end of block respectively */
717 if (ssym->blockSpil) {
718 iCode *nic = newiCode(IPUSH,operandFromSymbol(ssym),NULL);
719 /* add push to the start of the block */
720 addiCodeToeBBlock(ebp,nic,( ebp->sch->op == LABEL ?
721 ebp->sch->next : ebp->sch));
722 nic = newiCode(IPOP,operandFromSymbol(ssym),NULL);
723 /* add pop to the end of the block */
724 addiCodeToeBBlock(ebp,nic,NULL);
727 /* if spilt because not used in the remainder of the
728 block then add a push before this instruction and
729 a pop at the end of the block */
730 if (ssym->remainSpil) {
732 iCode *nic = newiCode(IPUSH,operandFromSymbol(ssym),NULL);
733 /* add push just before this instruction */
734 addiCodeToeBBlock(ebp,nic,ic);
736 nic = newiCode(IPOP,operandFromSymbol(ssym),NULL);
737 /* add pop to the end of the block */
738 addiCodeToeBBlock(ebp,nic,NULL);
747 /*-----------------------------------------------------------------*/
748 /* getRegPtr - will try for PTR if not a GPR type if not spil */
749 /*-----------------------------------------------------------------*/
750 static regs *getRegPtr (iCode *ic, eBBlock *ebp, symbol *sym)
755 /* try for a ptr type */
756 if ((reg = allocReg(REG_PTR)))
759 /* try for gpr type */
760 if ((reg = allocReg(REG_GPR)))
763 /* we have to spil */
764 if (!spilSomething (ic,ebp,sym))
767 /* this looks like an infinite loop but
768 in really selectSpil will abort */
772 /*-----------------------------------------------------------------*/
773 /* getRegGpr - will try for GPR if not spil */
774 /*-----------------------------------------------------------------*/
775 static regs *getRegGpr (iCode *ic, eBBlock *ebp,symbol *sym)
780 /* try for gpr type */
781 if ((reg = allocReg(REG_GPR)))
784 if (!pic14_ptrRegReq)
785 if ((reg = allocReg(REG_PTR)))
788 /* we have to spil */
789 if (!spilSomething (ic,ebp,sym))
792 /* this looks like an infinite loop but
793 in really selectSpil will abort */
797 /*-----------------------------------------------------------------*/
798 /* symHasReg - symbol has a given register */
799 /*-----------------------------------------------------------------*/
800 static bool symHasReg(symbol *sym,regs *reg)
804 for ( i = 0 ; i < sym->nRegs ; i++)
805 if (sym->regs[i] == reg)
811 /*-----------------------------------------------------------------*/
812 /* deassignLRs - check the live to and if they have registers & are*/
813 /* not spilt then free up the registers */
814 /*-----------------------------------------------------------------*/
815 static void deassignLRs (iCode *ic, eBBlock *ebp)
821 for (sym = hTabFirstItem(liveRanges,&k); sym;
822 sym = hTabNextItem(liveRanges,&k)) {
825 /* if it does not end here */
826 if (sym->liveTo > ic->seq )
829 /* if it was spilt on stack then we can
830 mark the stack spil location as free */
832 if (sym->stackSpil) {
833 sym->usl.spillLoc->isFree = 1;
839 if (!bitVectBitValue(_G.regAssigned,sym->key))
842 /* special case check if this is an IFX &
843 the privious one was a pop and the
844 previous one was not spilt then keep track
846 if (ic->op == IFX && ic->prev &&
847 ic->prev->op == IPOP &&
848 !ic->prev->parmPush &&
849 !OP_SYMBOL(IC_LEFT(ic->prev))->isspilt)
850 psym = OP_SYMBOL(IC_LEFT(ic->prev));
855 bitVectUnSetBit(_G.regAssigned,sym->key);
857 /* if the result of this one needs registers
858 and does not have it then assign it right
861 ! (SKIP_IC2(ic) || /* not a special icode */
862 ic->op == JUMPTABLE ||
868 (result = OP_SYMBOL(IC_RESULT(ic))) && /* has a result */
869 result->liveTo > ic->seq && /* and will live beyond this */
870 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
871 result->regType == sym->regType && /* same register types */
872 result->nRegs && /* which needs registers */
873 ! result->isspilt && /* and does not already have them */
875 ! bitVectBitValue(_G.regAssigned,result->key) &&
876 /* the number of free regs + number of regs in this LR
877 can accomodate the what result Needs */
878 ((nfreeRegsType(result->regType) +
879 sym->nRegs) >= result->nRegs)
882 for (i = 0 ; i < max(sym->nRegs,result->nRegs) ; i++)
884 result->regs[i] = sym->regs[i] ;
886 result->regs[i] = getRegGpr (ic,ebp,result);
888 _G.regAssigned = bitVectSetBit(_G.regAssigned,result->key);
892 /* free the remaining */
893 for (; i < sym->nRegs ; i++) {
895 if (!symHasReg(psym,sym->regs[i]))
896 freeReg(sym->regs[i]);
898 freeReg(sym->regs[i]);
905 /*-----------------------------------------------------------------*/
906 /* reassignLR - reassign this to registers */
907 /*-----------------------------------------------------------------*/
908 static void reassignLR (operand *op)
910 symbol *sym = OP_SYMBOL(op);
913 /* not spilt any more */
914 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
915 bitVectUnSetBit(_G.spiltSet,sym->key);
917 _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
921 for (i=0;i<sym->nRegs;i++)
922 sym->regs[i]->isFree = 0;
925 /*-----------------------------------------------------------------*/
926 /* willCauseSpill - determines if allocating will cause a spill */
927 /*-----------------------------------------------------------------*/
928 static int willCauseSpill ( int nr, int rt)
930 /* first check if there are any avlb registers
931 of te type required */
933 /* special case for pointer type
934 if pointer type not avlb then
935 check for type gpr */
936 if (nFreeRegs(rt) >= nr)
938 if (nFreeRegs(REG_GPR) >= nr)
941 if (pic14_ptrRegReq) {
942 if (nFreeRegs(rt) >= nr)
945 if (nFreeRegs(REG_PTR) +
946 nFreeRegs(REG_GPR) >= nr)
951 /* it will cause a spil */
955 /*-----------------------------------------------------------------*/
956 /* positionRegs - the allocator can allocate same registers to res-*/
957 /* ult and operand, if this happens make sure they are in the same */
958 /* position as the operand otherwise chaos results */
959 /*-----------------------------------------------------------------*/
960 static void positionRegs (symbol *result, symbol *opsym, int lineno)
962 int count = min(result->nRegs,opsym->nRegs);
963 int i , j = 0, shared = 0;
965 /* if the result has been spilt then cannot share */
970 /* first make sure that they actually share */
971 for ( i = 0 ; i < count; i++ ) {
972 for (j = 0 ; j < count ; j++ ) {
973 if (result->regs[i] == opsym->regs[j] && i !=j) {
981 regs *tmp = result->regs[i];
982 result->regs[i] = result->regs[j];
983 result->regs[j] = tmp;
988 /*-----------------------------------------------------------------*/
989 /* serialRegAssign - serially allocate registers to the variables */
990 /*-----------------------------------------------------------------*/
991 static void serialRegAssign (eBBlock **ebbs, int count)
996 for (i = 0; i < count ; i++ ) {
1000 if (ebbs[i]->noPath &&
1001 (ebbs[i]->entryLabel != entryLabel &&
1002 ebbs[i]->entryLabel != returnLabel ))
1005 /* of all instructions do */
1006 for (ic = ebbs[i]->sch ; ic ; ic = ic->next) {
1008 /* if this is an ipop that means some live
1009 range will have to be assigned again */
1011 reassignLR (IC_LEFT(ic));
1013 /* if result is present && is a true symbol */
1014 if (IC_RESULT(ic) && ic->op != IFX &&
1015 IS_TRUE_SYMOP(IC_RESULT(ic)))
1016 OP_SYMBOL(IC_RESULT(ic))->allocreq = 1;
1018 /* take away registers from live
1019 ranges that end at this instruction */
1020 deassignLRs (ic, ebbs[i]) ;
1022 /* some don't need registers */
1024 ic->op == JUMPTABLE ||
1028 (IC_RESULT(ic) &&POINTER_SET(ic)) )
1031 /* now we need to allocate registers
1032 only for the result */
1033 if (IC_RESULT(ic)) {
1034 symbol *sym = OP_SYMBOL(IC_RESULT(ic));
1040 /* if it does not need or is spilt
1041 or is already assigned to registers
1042 or will not live beyond this instructions */
1045 bitVectBitValue(_G.regAssigned,sym->key) ||
1046 sym->liveTo <= ic->seq)
1049 /* if some liverange has been spilt at the block level
1050 and this one live beyond this block then spil this
1052 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq) {
1056 /* if trying to allocate this will cause
1057 a spill and there is nothing to spill
1058 or this one is rematerializable then
1060 willCS = willCauseSpill(sym->nRegs,sym->regType);
1061 spillable = computeSpillable(ic);
1063 (willCS && bitVectIsZero(spillable) ) ) {
1070 /* if it has a spillocation & is used less than
1071 all other live ranges then spill this */
1072 if ( willCS && sym->usl.spillLoc ) {
1075 leastUsedLR(liveRangesWith (spillable ,
1080 leastUsed->used > sym->used) {
1086 /* if we need ptr regs for the right side
1088 if (POINTER_GET(ic) && getSize(OP_SYMBOL(IC_LEFT(ic))->type)
1094 /* else we assign registers to it */
1095 _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
1097 for (j = 0 ; j < sym->nRegs ;j++ ) {
1098 if (sym->regType == REG_PTR)
1099 sym->regs[j] = getRegPtr(ic,ebbs[i],sym);
1101 sym->regs[j] = getRegGpr(ic,ebbs[i],sym);
1103 /* if the allocation falied which means
1104 this was spilt then break */
1108 /* if it shares registers with operands make sure
1109 that they are in the same position */
1110 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic)) &&
1111 OP_SYMBOL(IC_LEFT(ic))->nRegs && ic->op != '=')
1112 positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1113 OP_SYMBOL(IC_LEFT(ic)),ic->lineno);
1114 /* do the same for the right operand */
1115 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic)) &&
1116 OP_SYMBOL(IC_RIGHT(ic))->nRegs && ic->op != '=')
1117 positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1118 OP_SYMBOL(IC_RIGHT(ic)),ic->lineno);
1130 /*-----------------------------------------------------------------*/
1131 /* rUmaskForOp :- returns register mask for an operand */
1132 /*-----------------------------------------------------------------*/
1133 static bitVect *rUmaskForOp (operand *op)
1139 /* only temporaries are assigned registers */
1143 sym = OP_SYMBOL(op);
1145 /* if spilt or no registers assigned to it
1147 if (sym->isspilt || !sym->nRegs)
1150 rumask = newBitVect(pic14_nRegs);
1152 for (j = 0; j < sym->nRegs; j++) {
1153 rumask = bitVectSetBit(rumask,
1154 sym->regs[j]->rIdx);
1160 /*-----------------------------------------------------------------*/
1161 /* regsUsedIniCode :- returns bit vector of registers used in iCode*/
1162 /*-----------------------------------------------------------------*/
1163 static bitVect *regsUsedIniCode (iCode *ic)
1165 bitVect *rmask = newBitVect(pic14_nRegs);
1167 /* do the special cases first */
1168 if (ic->op == IFX ) {
1169 rmask = bitVectUnion(rmask,
1170 rUmaskForOp(IC_COND(ic)));
1174 /* for the jumptable */
1175 if (ic->op == JUMPTABLE) {
1176 rmask = bitVectUnion(rmask,
1177 rUmaskForOp(IC_JTCOND(ic)));
1182 /* of all other cases */
1184 rmask = bitVectUnion(rmask,
1185 rUmaskForOp(IC_LEFT(ic)));
1189 rmask = bitVectUnion(rmask,
1190 rUmaskForOp(IC_RIGHT(ic)));
1193 rmask = bitVectUnion(rmask,
1194 rUmaskForOp(IC_RESULT(ic)));
1200 /*-----------------------------------------------------------------*/
1201 /* createRegMask - for each instruction will determine the regsUsed*/
1202 /*-----------------------------------------------------------------*/
1203 static void createRegMask (eBBlock **ebbs, int count)
1207 /* for all blocks */
1208 for (i = 0; i < count ; i++ ) {
1211 if ( ebbs[i]->noPath &&
1212 ( ebbs[i]->entryLabel != entryLabel &&
1213 ebbs[i]->entryLabel != returnLabel ))
1216 /* for all instructions */
1217 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
1221 if (SKIP_IC2(ic) || !ic->rlive)
1224 /* first mark the registers used in this
1226 ic->rUsed = regsUsedIniCode(ic);
1227 _G.funcrUsed = bitVectUnion(_G.funcrUsed,ic->rUsed);
1229 /* now create the register mask for those
1230 registers that are in use : this is a
1231 super set of ic->rUsed */
1232 ic->rMask = newBitVect(pic14_nRegs+1);
1234 /* for all live Ranges alive at this point */
1235 for (j = 1; j < ic->rlive->size; j++ ) {
1239 /* if not alive then continue */
1240 if (!bitVectBitValue(ic->rlive,j))
1243 /* find the live range we are interested in */
1244 if (!(sym = hTabItemWithKey(liveRanges,j))) {
1245 werror (E_INTERNAL_ERROR,__FILE__,__LINE__,
1246 "createRegMask cannot find live range");
1250 /* if no register assigned to it */
1251 if (!sym->nRegs || sym->isspilt)
1254 /* for all the registers allocated to it */
1255 for (k = 0 ; k < sym->nRegs ;k++)
1258 bitVectSetBit(ic->rMask,sym->regs[k]->rIdx);
1264 /*-----------------------------------------------------------------*/
1265 /* rematStr - returns the rematerialized string for a remat var */
1266 /*-----------------------------------------------------------------*/
1267 static char *rematStr (symbol *sym)
1270 iCode *ic = sym->rematiCode;
1274 /* if plus or minus print the right hand side */
1275 if (ic->op == '+' || ic->op == '-') {
1276 sprintf(s,"0x%04x %c ",(int) operandLitValue(IC_RIGHT(ic)),
1279 ic = OP_SYMBOL(IC_LEFT(ic))->rematiCode;
1283 /* we reached the end */
1284 sprintf(s,"%s",OP_SYMBOL(IC_LEFT(ic))->rname);
1291 /*-----------------------------------------------------------------*/
1292 /* regTypeNum - computes the type & number of registers required */
1293 /*-----------------------------------------------------------------*/
1294 static void regTypeNum ()
1300 /* for each live range do */
1301 for ( sym = hTabFirstItem(liveRanges,&k); sym ;
1302 sym = hTabNextItem(liveRanges,&k)) {
1304 /* if used zero times then no registers needed */
1305 if ((sym->liveTo - sym->liveFrom) == 0)
1309 /* if the live range is a temporary */
1312 /* if the type is marked as a conditional */
1313 if (sym->regType == REG_CND)
1316 /* if used in return only then we don't
1318 if (sym->ruonly || sym->accuse) {
1319 if (IS_AGGREGATE(sym->type) || sym->isptr)
1320 sym->type = aggrToPtr(sym->type,FALSE);
1324 /* if the symbol has only one definition &
1325 that definition is a get_pointer and the
1326 pointer we are getting is rematerializable and
1329 if (bitVectnBitsOn(sym->defs) == 1 &&
1330 (ic = hTabItemWithKey(iCodehTab,
1331 bitVectFirstBit(sym->defs))) &&
1333 !IS_BITVAR(sym->etype)) {
1336 /* if remat in data space */
1337 if (OP_SYMBOL(IC_LEFT(ic))->remat &&
1338 DCL_TYPE(aggrToPtr(sym->type,FALSE)) == POINTER) {
1340 /* create a psuedo symbol & force a spil */
1341 symbol *psym = newSymbol(rematStr(OP_SYMBOL(IC_LEFT(ic))),1);
1342 psym->type = sym->type;
1343 psym->etype = sym->etype;
1344 strcpy(psym->rname,psym->name);
1346 sym->usl.spillLoc = psym;
1350 /* if in data space or idata space then try to
1351 allocate pointer register */
1355 /* if not then we require registers */
1356 sym->nRegs = ((IS_AGGREGATE(sym->type) || sym->isptr ) ?
1357 getSize(sym->type = aggrToPtr(sym->type,FALSE)) :
1358 getSize(sym->type));
1360 if (sym->nRegs > 4) {
1361 fprintf(stderr,"allocated more than 4 or 0 registers for type ");
1362 printTypeChain(sym->type,stderr);fprintf(stderr,"\n");
1365 /* determine the type of register required */
1366 if (sym->nRegs == 1 &&
1367 IS_PTR(sym->type) &&
1369 sym->regType = REG_PTR ;
1371 sym->regType = REG_GPR ;
1374 /* for the first run we don't provide */
1375 /* registers for true symbols we will */
1376 /* see how things go */
1382 /*-----------------------------------------------------------------*/
1383 /* freeAllRegs - mark all registers as free */
1384 /*-----------------------------------------------------------------*/
1385 static void freeAllRegs()
1389 for (i=0;i< pic14_nRegs;i++ )
1390 regspic14[i].isFree = 1;
1393 /*-----------------------------------------------------------------*/
1394 /* deallocStackSpil - this will set the stack pointer back */
1395 /*-----------------------------------------------------------------*/
1396 static DEFSETFUNC(deallocStackSpil)
1404 /*-----------------------------------------------------------------*/
1405 /* farSpacePackable - returns the packable icode for far variables */
1406 /*-----------------------------------------------------------------*/
1407 static iCode *farSpacePackable (iCode *ic)
1411 /* go thru till we find a definition for the
1412 symbol on the right */
1413 for ( dic = ic->prev ; dic ; dic = dic->prev) {
1415 /* if the definition is a call then no */
1416 if ((dic->op == CALL || dic->op == PCALL) &&
1417 IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1421 /* if shift by unknown amount then not */
1422 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1423 IC_RESULT(dic)->key == IC_RIGHT(ic)->key)
1426 /* if pointer get and size > 1 */
1427 if (POINTER_GET(dic) &&
1428 getSize(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)) > 1)
1431 if (POINTER_SET(dic) &&
1432 getSize(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)) > 1)
1435 /* if any three is a true symbol in far space */
1436 if (IC_RESULT(dic) &&
1437 IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1438 isOperandInFarSpace(IC_RESULT(dic)))
1441 if (IC_RIGHT(dic) &&
1442 IS_TRUE_SYMOP(IC_RIGHT(dic)) &&
1443 isOperandInFarSpace(IC_RIGHT(dic)) &&
1444 !isOperandEqual(IC_RIGHT(dic),IC_RESULT(ic)))
1448 IS_TRUE_SYMOP(IC_LEFT(dic)) &&
1449 isOperandInFarSpace(IC_LEFT(dic)) &&
1450 !isOperandEqual(IC_LEFT(dic),IC_RESULT(ic)))
1453 if (isOperandEqual(IC_RIGHT(ic),IC_RESULT(dic))) {
1454 if ( (dic->op == LEFT_OP ||
1455 dic->op == RIGHT_OP ||
1457 IS_OP_LITERAL(IC_RIGHT(dic)))
1467 /*-----------------------------------------------------------------*/
1468 /* packRegsForAssign - register reduction for assignment */
1469 /*-----------------------------------------------------------------*/
1470 static int packRegsForAssign (iCode *ic,eBBlock *ebp)
1475 if (!IS_ITEMP(IC_RIGHT(ic)) ||
1476 OP_SYMBOL(IC_RIGHT(ic))->isind ||
1477 OP_LIVETO(IC_RIGHT(ic)) > ic->seq) {
1481 /* if the true symbol is defined in far space or on stack
1482 then we should not since this will increase register pressure */
1483 if (isOperandInFarSpace(IC_RESULT(ic))) {
1484 if ((dic = farSpacePackable(ic)))
1490 /* find the definition of iTempNN scanning backwards if we find a
1491 a use of the true symbol in before we find the definition then
1493 for ( dic = ic->prev ; dic ; dic = dic->prev) {
1495 /* if there is a function call and this is
1496 a parameter & not my parameter then don't pack it */
1497 if ( (dic->op == CALL || dic->op == PCALL) &&
1498 (OP_SYMBOL(IC_RESULT(ic))->_isparm &&
1499 !OP_SYMBOL(IC_RESULT(ic))->ismyparm)) {
1507 if (IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1508 IS_OP_VOLATILE(IC_RESULT(dic))) {
1513 if (IS_SYMOP(IC_RESULT(dic)) &&
1514 IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1515 if (POINTER_SET(dic))
1521 if (IS_SYMOP(IC_RIGHT(dic)) &&
1522 (IC_RIGHT(dic)->key == IC_RESULT(ic)->key ||
1523 IC_RIGHT(dic)->key == IC_RIGHT(ic)->key)) {
1528 if (IS_SYMOP(IC_LEFT(dic)) &&
1529 (IC_LEFT(dic)->key == IC_RESULT(ic)->key ||
1530 IC_LEFT(dic)->key == IC_RIGHT(ic)->key)) {
1535 if (POINTER_SET(dic) &&
1536 IC_RESULT(dic)->key == IC_RESULT(ic)->key ) {
1543 return 0 ; /* did not find */
1545 /* if the result is on stack or iaccess then it must be
1546 the same atleast one of the operands */
1547 if (OP_SYMBOL(IC_RESULT(ic))->onStack ||
1548 OP_SYMBOL(IC_RESULT(ic))->iaccess ) {
1550 /* the operation has only one symbol
1551 operator then we can pack */
1552 if ((IC_LEFT(dic) && !IS_SYMOP(IC_LEFT(dic))) ||
1553 (IC_RIGHT(dic) && !IS_SYMOP(IC_RIGHT(dic))))
1556 if (!((IC_LEFT(dic) &&
1557 IC_RESULT(ic)->key == IC_LEFT(dic)->key) ||
1559 IC_RESULT(ic)->key == IC_RIGHT(dic)->key)))
1563 /* found the definition */
1564 /* replace the result with the result of */
1565 /* this assignment and remove this assignment */
1566 IC_RESULT(dic) = IC_RESULT(ic) ;
1568 if (IS_ITEMP(IC_RESULT(dic)) && OP_SYMBOL(IC_RESULT(dic))->liveFrom > dic->seq) {
1569 OP_SYMBOL(IC_RESULT(dic))->liveFrom = dic->seq;
1571 /* delete from liverange table also
1572 delete from all the points inbetween and the new
1574 for ( sic = dic; sic != ic ; sic = sic->next ) {
1575 bitVectUnSetBit(sic->rlive,IC_RESULT(ic)->key);
1576 if (IS_ITEMP(IC_RESULT(dic)))
1577 bitVectSetBit(sic->rlive,IC_RESULT(dic)->key);
1580 remiCodeFromeBBlock(ebp,ic);
1581 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
1582 OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
1588 /*-----------------------------------------------------------------*/
1589 /* findAssignToSym : scanning backwards looks for first assig found*/
1590 /*-----------------------------------------------------------------*/
1591 static iCode *findAssignToSym (operand *op,iCode *ic)
1595 for (dic = ic->prev ; dic ; dic = dic->prev) {
1597 /* if definition by assignment */
1598 if (dic->op == '=' &&
1599 !POINTER_SET(dic) &&
1600 IC_RESULT(dic)->key == op->key
1601 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1604 /* we are interested only if defined in far space */
1605 /* or in stack space in case of + & - */
1607 /* if assigned to a non-symbol then return
1609 if (!IS_SYMOP(IC_RIGHT(dic)))
1612 /* if the symbol is in far space then
1614 if (isOperandInFarSpace(IC_RIGHT(dic)))
1617 /* for + & - operations make sure that
1618 if it is on the stack it is the same
1619 as one of the three operands */
1620 if ((ic->op == '+' || ic->op == '-') &&
1621 OP_SYMBOL(IC_RIGHT(dic))->onStack) {
1623 if ( IC_RESULT(ic)->key != IC_RIGHT(dic)->key &&
1624 IC_LEFT(ic)->key != IC_RIGHT(dic)->key &&
1625 IC_RIGHT(ic)->key != IC_RIGHT(dic)->key)
1633 /* if we find an usage then we cannot delete it */
1634 if (IC_LEFT(dic) && IC_LEFT(dic)->key == op->key)
1637 if (IC_RIGHT(dic) && IC_RIGHT(dic)->key == op->key)
1640 if (POINTER_SET(dic) && IC_RESULT(dic)->key == op->key)
1644 /* now make sure that the right side of dic
1645 is not defined between ic & dic */
1647 iCode *sic = dic->next ;
1649 for (; sic != ic ; sic = sic->next)
1650 if (IC_RESULT(sic) &&
1651 IC_RESULT(sic)->key == IC_RIGHT(dic)->key)
1660 /*-----------------------------------------------------------------*/
1661 /* packRegsForSupport :- reduce some registers for support calls */
1662 /*-----------------------------------------------------------------*/
1663 static int packRegsForSupport (iCode *ic, eBBlock *ebp)
1666 /* for the left & right operand :- look to see if the
1667 left was assigned a true symbol in far space in that
1668 case replace them */
1669 if (IS_ITEMP(IC_LEFT(ic)) &&
1670 OP_SYMBOL(IC_LEFT(ic))->liveTo <= ic->seq) {
1671 iCode *dic = findAssignToSym(IC_LEFT(ic),ic);
1677 /* found it we need to remove it from the
1679 for ( sic = dic; sic != ic ; sic = sic->next )
1680 bitVectUnSetBit(sic->rlive,IC_LEFT(ic)->key);
1682 IC_LEFT(ic)->operand.symOperand =
1683 IC_RIGHT(dic)->operand.symOperand;
1684 IC_LEFT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1685 remiCodeFromeBBlock(ebp,dic);
1686 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1690 /* do the same for the right operand */
1693 IS_ITEMP(IC_RIGHT(ic)) &&
1694 OP_SYMBOL(IC_RIGHT(ic))->liveTo <= ic->seq) {
1695 iCode *dic = findAssignToSym(IC_RIGHT(ic),ic);
1701 /* if this is a subtraction & the result
1702 is a true symbol in far space then don't pack */
1703 if (ic->op == '-' && IS_TRUE_SYMOP(IC_RESULT(dic))) {
1704 link *etype =getSpec(operandType(IC_RESULT(dic)));
1705 if (IN_FARSPACE(SPEC_OCLS(etype)))
1708 /* found it we need to remove it from the
1710 for ( sic = dic; sic != ic ; sic = sic->next )
1711 bitVectUnSetBit(sic->rlive,IC_RIGHT(ic)->key);
1713 IC_RIGHT(ic)->operand.symOperand =
1714 IC_RIGHT(dic)->operand.symOperand;
1715 IC_RIGHT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1717 remiCodeFromeBBlock(ebp,dic);
1718 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1725 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1728 /*-----------------------------------------------------------------*/
1729 /* packRegsForOneuse : - will reduce some registers for single Use */
1730 /*-----------------------------------------------------------------*/
1731 static iCode *packRegsForOneuse (iCode *ic, operand *op , eBBlock *ebp)
1736 /* if returning a literal then do nothing */
1740 /* only upto 2 bytes since we cannot predict
1741 the usage of b, & acc */
1742 if (getSize(operandType(op)) > (fReturnSize - 2) &&
1747 /* this routine will mark the a symbol as used in one
1748 instruction use only && if the defintion is local
1749 (ie. within the basic block) && has only one definition &&
1750 that definiion is either a return value from a
1751 function or does not contain any variables in
1753 uses = bitVectCopy(OP_USES(op));
1754 bitVectUnSetBit(uses,ic->key); /* take away this iCode */
1755 if (!bitVectIsZero(uses)) /* has other uses */
1758 /* if it has only one defintion */
1759 if (bitVectnBitsOn(OP_DEFS(op)) > 1)
1760 return NULL ; /* has more than one definition */
1762 /* get the that definition */
1764 hTabItemWithKey(iCodehTab,
1765 bitVectFirstBit(OP_DEFS(op)))))
1768 /* found the definition now check if it is local */
1769 if (dic->seq < ebp->fSeq ||
1770 dic->seq > ebp->lSeq)
1771 return NULL ; /* non-local */
1773 /* now check if it is the return from
1775 if (dic->op == CALL || dic->op == PCALL ) {
1776 if (ic->op != SEND && ic->op != RETURN) {
1777 OP_SYMBOL(op)->ruonly = 1;
1784 /* otherwise check that the definition does
1785 not contain any symbols in far space */
1786 if (isOperandInFarSpace(IC_LEFT(dic)) ||
1787 isOperandInFarSpace(IC_RIGHT(dic)) ||
1788 IS_OP_RUONLY(IC_LEFT(ic)) ||
1789 IS_OP_RUONLY(IC_RIGHT(ic)) ) {
1793 /* if pointer set then make sure the pointer
1795 if (POINTER_SET(dic) &&
1796 !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1799 if (POINTER_GET(dic) &&
1800 !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1805 /* also make sure the intervenening instructions
1806 don't have any thing in far space */
1807 for (dic = dic->next ; dic && dic != ic ; dic = dic->next) {
1809 /* if there is an intervening function call then no */
1810 if (dic->op == CALL || dic->op == PCALL)
1812 /* if pointer set then make sure the pointer
1814 if (POINTER_SET(dic) &&
1815 !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1818 if (POINTER_GET(dic) &&
1819 !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1822 /* if address of & the result is remat the okay */
1823 if (dic->op == ADDRESS_OF &&
1824 OP_SYMBOL(IC_RESULT(dic))->remat)
1827 /* if operand has size of three or more & this
1828 operation is a '*','/' or '%' then 'b' may
1830 if (( dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1831 getSize(operandType(op)) >= 3)
1834 /* if left or right or result is in far space */
1835 if (isOperandInFarSpace(IC_LEFT(dic)) ||
1836 isOperandInFarSpace(IC_RIGHT(dic)) ||
1837 isOperandInFarSpace(IC_RESULT(dic)) ||
1838 IS_OP_RUONLY(IC_LEFT(dic)) ||
1839 IS_OP_RUONLY(IC_RIGHT(dic)) ||
1840 IS_OP_RUONLY(IC_RESULT(dic)) ) {
1845 OP_SYMBOL(op)->ruonly = 1;
1850 /*-----------------------------------------------------------------*/
1851 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1852 /*-----------------------------------------------------------------*/
1853 static bool isBitwiseOptimizable (iCode *ic)
1855 link *ltype = getSpec(operandType(IC_LEFT(ic)));
1856 link *rtype = getSpec(operandType(IC_RIGHT(ic)));
1858 /* bitwise operations are considered optimizable
1859 under the following conditions (Jean-Louis VERN)
1871 if ( IS_LITERAL(rtype) ||
1872 (IS_BITVAR(ltype) && IN_BITSPACE(SPEC_OCLS(ltype))))
1878 /*-----------------------------------------------------------------*/
1879 /* packRegsForAccUse - pack registers for acc use */
1880 /*-----------------------------------------------------------------*/
1881 static void packRegsForAccUse (iCode *ic)
1885 /* if + or - then it has to be one byte result */
1886 if ((ic->op == '+' || ic->op == '-')
1887 && getSize(operandType(IC_RESULT(ic))) > 1)
1890 /* if shift operation make sure right side is not a literal */
1891 if (ic->op == RIGHT_OP &&
1892 ( isOperandLiteral(IC_RIGHT(ic)) ||
1893 getSize(operandType(IC_RESULT(ic))) > 1))
1896 if (ic->op == LEFT_OP &&
1897 ( isOperandLiteral(IC_RIGHT(ic)) ||
1898 getSize(operandType(IC_RESULT(ic))) > 1))
1901 if (IS_BITWISE_OP(ic) &&
1902 getSize(operandType(IC_RESULT(ic))) > 1)
1906 /* has only one definition */
1907 if (bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1)
1910 /* has only one use */
1911 if (bitVectnBitsOn(OP_USES(IC_RESULT(ic))) > 1)
1914 /* and the usage immediately follows this iCode */
1915 if (!(uic = hTabItemWithKey(iCodehTab,
1916 bitVectFirstBit(OP_USES(IC_RESULT(ic))))))
1919 if (ic->next != uic)
1922 /* if it is a conditional branch then we definitely can */
1923 if (uic->op == IFX )
1926 if ( uic->op == JUMPTABLE )
1929 /* if the usage is not is an assignment
1930 or an arithmetic / bitwise / shift operation then not */
1931 if (POINTER_SET(uic) &&
1932 getSize(aggrToPtr(operandType(IC_RESULT(uic)),FALSE)) > 1)
1935 if (uic->op != '=' &&
1936 !IS_ARITHMETIC_OP(uic) &&
1937 !IS_BITWISE_OP(uic) &&
1938 uic->op != LEFT_OP &&
1939 uic->op != RIGHT_OP )
1942 /* if used in ^ operation then make sure right is not a
1944 if (uic->op == '^' && isOperandLiteral(IC_RIGHT(uic)))
1947 /* if shift operation make sure right side is not a literal */
1948 if (uic->op == RIGHT_OP &&
1949 ( isOperandLiteral(IC_RIGHT(uic)) ||
1950 getSize(operandType(IC_RESULT(uic))) > 1))
1953 if (uic->op == LEFT_OP &&
1954 ( isOperandLiteral(IC_RIGHT(uic)) ||
1955 getSize(operandType(IC_RESULT(uic))) > 1))
1958 /* make sure that the result of this icode is not on the
1959 stack, since acc is used to compute stack offset */
1960 if (IS_TRUE_SYMOP(IC_RESULT(uic)) &&
1961 OP_SYMBOL(IC_RESULT(uic))->onStack)
1964 /* if either one of them in far space then we cannot */
1965 if ((IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1966 isOperandInFarSpace(IC_LEFT(uic))) ||
1967 (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1968 isOperandInFarSpace(IC_RIGHT(uic))))
1971 /* if the usage has only one operand then we can */
1972 if (IC_LEFT(uic) == NULL ||
1973 IC_RIGHT(uic) == NULL)
1976 /* make sure this is on the left side if not
1977 a '+' since '+' is commutative */
1978 if (ic->op != '+' &&
1979 IC_LEFT(uic)->key != IC_RESULT(ic)->key)
1982 /* if one of them is a literal then we can */
1983 if ((IC_LEFT(uic) && IS_OP_LITERAL(IC_LEFT(uic))) ||
1984 (IC_RIGHT(uic) && IS_OP_LITERAL(IC_RIGHT(uic)))) {
1985 OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
1989 /* if the other one is not on stack then we can */
1990 if (IC_LEFT(uic)->key == IC_RESULT(ic)->key &&
1991 (IS_ITEMP(IC_RIGHT(uic)) ||
1992 (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1993 !OP_SYMBOL(IC_RIGHT(uic))->onStack)))
1996 if (IC_RIGHT(uic)->key == IC_RESULT(ic)->key &&
1997 (IS_ITEMP(IC_LEFT(uic)) ||
1998 (IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1999 !OP_SYMBOL(IC_LEFT(uic))->onStack)))
2005 OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
2010 /*-----------------------------------------------------------------*/
2011 /* packForPush - hueristics to reduce iCode for pushing */
2012 /*-----------------------------------------------------------------*/
2013 static void packForPush(iCode *ic, eBBlock *ebp)
2017 if (ic->op != IPUSH || !IS_ITEMP(IC_LEFT(ic)))
2020 /* must have only definition & one usage */
2021 if (bitVectnBitsOn(OP_DEFS(IC_LEFT(ic))) != 1 ||
2022 bitVectnBitsOn(OP_USES(IC_LEFT(ic))) != 1 )
2025 /* find the definition */
2026 if (!(dic = hTabItemWithKey(iCodehTab,
2027 bitVectFirstBit(OP_DEFS(IC_LEFT(ic))))))
2030 if (dic->op != '=' || POINTER_SET(dic))
2033 /* we now we know that it has one & only one def & use
2034 and the that the definition is an assignment */
2035 IC_LEFT(ic) = IC_RIGHT(dic);
2037 remiCodeFromeBBlock(ebp,dic);
2038 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
2041 /*-----------------------------------------------------------------*/
2042 /* packRegisters - does some transformations to reduce register */
2044 /*-----------------------------------------------------------------*/
2045 static void packRegisters (eBBlock *ebp)
2054 /* look for assignments of the form */
2055 /* iTempNN = TRueSym (someoperation) SomeOperand */
2057 /* TrueSym := iTempNN:1 */
2058 for ( ic = ebp->sch ; ic ; ic = ic->next ) {
2061 /* find assignment of the form TrueSym := iTempNN:1 */
2062 if (ic->op == '=' && !POINTER_SET(ic))
2063 change += packRegsForAssign(ic,ebp);
2070 for ( ic = ebp->sch ; ic ; ic = ic->next ) {
2072 /* if this is an itemp & result of a address of a true sym
2073 then mark this as rematerialisable */
2074 if (ic->op == ADDRESS_OF &&
2075 IS_ITEMP(IC_RESULT(ic)) &&
2076 IS_TRUE_SYMOP(IC_LEFT(ic)) &&
2077 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2078 !OP_SYMBOL(IC_LEFT(ic))->onStack ) {
2080 OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2081 OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2082 OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2086 /* if straight assignment then carry remat flag if
2087 this is the only definition */
2088 if (ic->op == '=' &&
2090 IS_SYMOP(IC_RIGHT(ic)) &&
2091 OP_SYMBOL(IC_RIGHT(ic))->remat &&
2092 bitVectnBitsOn(OP_SYMBOL(IC_RESULT(ic))->defs) <= 1) {
2094 OP_SYMBOL(IC_RESULT(ic))->remat =
2095 OP_SYMBOL(IC_RIGHT(ic))->remat;
2096 OP_SYMBOL(IC_RESULT(ic))->rematiCode =
2097 OP_SYMBOL(IC_RIGHT(ic))->rematiCode ;
2100 /* if this is a +/- operation with a rematerizable
2101 then mark this as rematerializable as well */
2102 if ((ic->op == '+' || ic->op == '-') &&
2103 (IS_SYMOP(IC_LEFT(ic)) &&
2104 IS_ITEMP(IC_RESULT(ic)) &&
2105 OP_SYMBOL(IC_LEFT(ic))->remat &&
2106 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2107 IS_OP_LITERAL(IC_RIGHT(ic))) ) {
2110 operandLitValue(IC_RIGHT(ic));
2111 OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2112 OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2113 OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2116 /* mark the pointer usages */
2117 if (POINTER_SET(ic))
2118 OP_SYMBOL(IC_RESULT(ic))->uptr = 1;
2120 if (POINTER_GET(ic))
2121 OP_SYMBOL(IC_LEFT(ic))->uptr = 1;
2123 if (!SKIP_IC2(ic)) {
2124 /* if we are using a symbol on the stack
2125 then we should say pic14_ptrRegReq */
2126 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
2127 pic14_ptrRegReq += ((OP_SYMBOL(IC_COND(ic))->onStack ||
2128 OP_SYMBOL(IC_COND(ic))->iaccess) ? 1 : 0);
2130 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
2131 pic14_ptrRegReq += ((OP_SYMBOL(IC_JTCOND(ic))->onStack ||
2132 OP_SYMBOL(IC_JTCOND(ic))->iaccess) ? 1 : 0);
2134 if (IS_SYMOP(IC_LEFT(ic)))
2135 pic14_ptrRegReq += ((OP_SYMBOL(IC_LEFT(ic))->onStack ||
2136 OP_SYMBOL(IC_LEFT(ic))->iaccess) ? 1 : 0);
2137 if (IS_SYMOP(IC_RIGHT(ic)))
2138 pic14_ptrRegReq += ((OP_SYMBOL(IC_RIGHT(ic))->onStack ||
2139 OP_SYMBOL(IC_RIGHT(ic))->iaccess) ? 1 : 0);
2140 if (IS_SYMOP(IC_RESULT(ic)))
2141 pic14_ptrRegReq += ((OP_SYMBOL(IC_RESULT(ic))->onStack ||
2142 OP_SYMBOL(IC_RESULT(ic))->iaccess) ? 1 : 0);
2146 /* if the condition of an if instruction
2147 is defined in the previous instruction then
2148 mark the itemp as a conditional */
2149 if ((IS_CONDITIONAL(ic) ||
2150 ( ( ic->op == BITWISEAND ||
2153 isBitwiseOptimizable(ic))) &&
2154 ic->next && ic->next->op == IFX &&
2155 isOperandEqual(IC_RESULT(ic),IC_COND(ic->next)) &&
2156 OP_SYMBOL(IC_RESULT(ic))->liveTo <= ic->next->seq) {
2158 OP_SYMBOL(IC_RESULT(ic))->regType = REG_CND;
2162 /* reduce for support function calls */
2163 if (ic->supportRtn || ic->op == '+' || ic->op == '-' )
2164 packRegsForSupport (ic,ebp);
2166 /* some cases the redundant moves can
2167 can be eliminated for return statements */
2168 if ((ic->op == RETURN || ic->op == SEND) &&
2169 !isOperandInFarSpace(IC_LEFT(ic)) &&
2171 packRegsForOneuse (ic,IC_LEFT(ic),ebp);
2173 /* if pointer set & left has a size more than
2174 one and right is not in far space */
2175 if (POINTER_SET(ic) &&
2176 !isOperandInFarSpace(IC_RIGHT(ic)) &&
2177 !OP_SYMBOL(IC_RESULT(ic))->remat &&
2178 !IS_OP_RUONLY(IC_RIGHT(ic)) &&
2179 getSize(aggrToPtr(operandType(IC_RESULT(ic)),FALSE)) > 1 )
2181 packRegsForOneuse (ic,IC_RESULT(ic),ebp);
2183 /* if pointer get */
2184 if (POINTER_GET(ic) &&
2185 !isOperandInFarSpace(IC_RESULT(ic))&&
2186 !OP_SYMBOL(IC_LEFT(ic))->remat &&
2187 !IS_OP_RUONLY(IC_RESULT(ic)) &&
2188 getSize(aggrToPtr(operandType(IC_LEFT(ic)),FALSE)) > 1 )
2190 packRegsForOneuse (ic,IC_LEFT(ic),ebp);
2193 /* if this is cast for intergral promotion then
2194 check if only use of the definition of the
2195 operand being casted/ if yes then replace
2196 the result of that arithmetic operation with
2197 this result and get rid of the cast */
2198 if (ic->op == CAST) {
2199 link *fromType = operandType(IC_RIGHT(ic));
2200 link *toType = operandType(IC_LEFT(ic));
2202 if (IS_INTEGRAL(fromType) && IS_INTEGRAL(toType) &&
2203 getSize(fromType) != getSize(toType) ) {
2205 iCode *dic = packRegsForOneuse(ic,IC_RIGHT(ic),ebp);
2207 if (IS_ARITHMETIC_OP(dic)) {
2208 IC_RESULT(dic) = IC_RESULT(ic);
2209 remiCodeFromeBBlock(ebp,ic);
2210 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2211 OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
2214 OP_SYMBOL(IC_RIGHT(ic))->ruonly = 0;
2218 /* if the type from and type to are the same
2219 then if this is the only use then packit */
2220 if (checkType(operandType(IC_RIGHT(ic)),
2221 operandType(IC_LEFT(ic))) == 1) {
2222 iCode *dic = packRegsForOneuse (ic,IC_RIGHT(ic),ebp);
2224 IC_RESULT(dic) = IC_RESULT(ic);
2225 remiCodeFromeBBlock(ebp,ic);
2226 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2227 OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
2235 iTempNN := (some variable in farspace) V1
2240 if (ic->op == IPUSH ) {
2241 packForPush(ic,ebp);
2245 /* pack registers for accumulator use, when the
2246 result of an arithmetic or bit wise operation
2247 has only one use, that use is immediately following
2248 the defintion and the using iCode has only one
2249 operand or has two operands but one is literal &
2250 the result of that operation is not on stack then
2251 we can leave the result of this operation in acc:b
2253 if ((IS_ARITHMETIC_OP(ic)
2255 || IS_BITWISE_OP(ic)
2257 || ic->op == LEFT_OP || ic->op == RIGHT_OP
2260 IS_ITEMP(IC_RESULT(ic)) &&
2261 getSize(operandType(IC_RESULT(ic))) <= 2)
2263 packRegsForAccUse (ic);
2268 /*-----------------------------------------------------------------*/
2269 /* assignRegisters - assigns registers to each live range as need */
2270 /*-----------------------------------------------------------------*/
2271 void pic14_assignRegisters (eBBlock **ebbs, int count)
2276 setToNull((void *)&_G.funcrUsed);
2277 pic14_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2280 /* change assignments this will remove some
2281 live ranges reducing some register pressure */
2282 for (i = 0 ; i < count ;i++ )
2283 packRegisters (ebbs[i]);
2285 if (options.dump_pack)
2286 dumpEbbsToFileExt(".dumppack",ebbs,count);
2288 /* first determine for each live range the number of
2289 registers & the type of registers required for each */
2292 /* and serially allocate registers */
2293 serialRegAssign(ebbs,count);
2295 /* if stack was extended then tell the user */
2296 if (_G.stackExtend) {
2297 /* werror(W_TOOMANY_SPILS,"stack", */
2298 /* _G.stackExtend,currFunc->name,""); */
2299 _G.stackExtend = 0 ;
2302 if (_G.dataExtend) {
2303 /* werror(W_TOOMANY_SPILS,"data space", */
2304 /* _G.dataExtend,currFunc->name,""); */
2308 /* after that create the register mask
2309 for each of the instruction */
2310 createRegMask (ebbs,count);
2312 /* redo that offsets for stacked automatic variables */
2313 redoStackOffsets ();
2315 if (options.dump_rassgn)
2316 dumpEbbsToFileExt(".dumprassgn",ebbs,count);
2318 /* now get back the chain */
2319 ic = iCodeLabelOptimize(iCodeFromeBBlock (ebbs,count));
2324 /* free up any _G.stackSpil locations allocated */
2325 applyToSet(_G.stackSpil,deallocStackSpil);
2327 setToNull((void **)&_G.stackSpil);
2328 setToNull((void **)&_G.spiltSet);
2329 /* mark all registers as free */