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 printf("%s - idx=%d\n",__FUNCTION__,idx);
130 for (i=0;i < pic14_nRegs;i++)
131 if (regspic14[i].rIdx == idx)
132 return ®spic14[i];
134 return ®spic14[0];
136 werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
137 "regWithIdx not found");
141 /*-----------------------------------------------------------------*/
142 /* freeReg - frees a register */
143 /*-----------------------------------------------------------------*/
144 static void freeReg (regs *reg)
150 /*-----------------------------------------------------------------*/
151 /* nFreeRegs - returns number of free registers */
152 /*-----------------------------------------------------------------*/
153 static int nFreeRegs (int type)
158 for (i = 0 ; i < pic14_nRegs; i++ )
159 if (regspic14[i].isFree && regspic14[i].type == type)
164 /*-----------------------------------------------------------------*/
165 /* nfreeRegsType - free registers with type */
166 /*-----------------------------------------------------------------*/
167 static int nfreeRegsType (int type)
170 if (type == REG_PTR) {
171 if ((nfr = nFreeRegs(type)) == 0)
172 return nFreeRegs(REG_GPR);
175 return nFreeRegs(type);
179 /*-----------------------------------------------------------------*/
180 /* allDefsOutOfRange - all definitions are out of a range */
181 /*-----------------------------------------------------------------*/
182 static bool allDefsOutOfRange (bitVect *defs,int fseq, int toseq)
189 for ( i = 0 ;i < defs->size ; i++ ) {
192 if (bitVectBitValue(defs,i) &&
193 (ic = hTabItemWithKey(iCodehTab,i)) &&
194 ( ic->seq >= fseq && ic->seq <= toseq))
203 /*-----------------------------------------------------------------*/
204 /* computeSpillable - given a point find the spillable live ranges */
205 /*-----------------------------------------------------------------*/
206 static bitVect *computeSpillable (iCode *ic)
210 /* spillable live ranges are those that are live at this
211 point . the following categories need to be subtracted
213 a) - those that are already spilt
214 b) - if being used by this one
215 c) - defined by this one */
217 spillable = bitVectCopy(ic->rlive);
219 bitVectCplAnd(spillable,_G.spiltSet); /* those already spilt */
221 bitVectCplAnd(spillable,ic->uses); /* used in this one */
222 bitVectUnSetBit(spillable,ic->defKey);
223 spillable = bitVectIntersect(spillable,_G.regAssigned);
228 /*-----------------------------------------------------------------*/
229 /* noSpilLoc - return true if a variable has no spil location */
230 /*-----------------------------------------------------------------*/
231 static int noSpilLoc (symbol *sym, eBBlock *ebp,iCode *ic)
233 return (sym->usl.spillLoc ? 0 : 1);
236 /*-----------------------------------------------------------------*/
237 /* hasSpilLoc - will return 1 if the symbol has spil location */
238 /*-----------------------------------------------------------------*/
239 static int hasSpilLoc (symbol *sym, eBBlock *ebp, iCode *ic)
241 return (sym->usl.spillLoc ? 1 : 0);
244 /*-----------------------------------------------------------------*/
245 /* directSpilLoc - will return 1 if the splilocation is in direct */
246 /*-----------------------------------------------------------------*/
247 static int directSpilLoc (symbol *sym, eBBlock *ebp, iCode *ic)
249 if ( sym->usl.spillLoc &&
250 (IN_DIRSPACE(SPEC_OCLS(sym->usl.spillLoc->etype))))
256 /*-----------------------------------------------------------------*/
257 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location*/
258 /* but is not used as a pointer */
259 /*-----------------------------------------------------------------*/
260 static int hasSpilLocnoUptr (symbol *sym, eBBlock *ebp, iCode *ic)
262 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
265 /*-----------------------------------------------------------------*/
266 /* rematable - will return 1 if the remat flag is set */
267 /*-----------------------------------------------------------------*/
268 static int rematable (symbol *sym, eBBlock *ebp, iCode *ic)
273 /*-----------------------------------------------------------------*/
274 /* notUsedInBlock - not used in this block */
275 /*-----------------------------------------------------------------*/
276 static int notUsedInBlock (symbol *sym, eBBlock *ebp, iCode *ic)
278 return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs) &&
279 allDefsOutOfRange (sym->defs,ebp->fSeq,ebp->lSeq));
280 /* return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs)); */
283 /*-----------------------------------------------------------------*/
284 /* notUsedInRemaining - not used or defined in remain of the block */
285 /*-----------------------------------------------------------------*/
286 static int notUsedInRemaining (symbol *sym, eBBlock *ebp, iCode *ic)
288 return ((usedInRemaining (operandFromSymbol(sym),ic) ? 0 : 1) &&
289 allDefsOutOfRange (sym->defs,ebp->fSeq,ebp->lSeq));
292 /*-----------------------------------------------------------------*/
293 /* allLRs - return true for all */
294 /*-----------------------------------------------------------------*/
295 static int allLRs (symbol *sym, eBBlock *ebp, iCode *ic)
300 /*-----------------------------------------------------------------*/
301 /* liveRangesWith - applies function to a given set of live range */
302 /*-----------------------------------------------------------------*/
303 static set *liveRangesWith (bitVect *lrs, int (func)(symbol *,eBBlock *, iCode *),
304 eBBlock *ebp, iCode *ic)
309 if (!lrs || !lrs->size)
312 for ( i = 1 ; i < lrs->size ; i++ ) {
314 if (!bitVectBitValue(lrs,i))
317 /* if we don't find it in the live range
318 hash table we are in serious trouble */
319 if (!(sym = hTabItemWithKey(liveRanges,i))) {
320 werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
321 "liveRangesWith could not find liveRange");
325 if (func(sym,ebp,ic) && bitVectBitValue(_G.regAssigned,sym->key))
326 addSetHead(&rset,sym);
333 /*-----------------------------------------------------------------*/
334 /* leastUsedLR - given a set determines which is the least used */
335 /*-----------------------------------------------------------------*/
336 static symbol *leastUsedLR (set *sset)
338 symbol *sym = NULL, *lsym = NULL ;
340 sym = lsym = setFirstItem(sset);
345 for (; lsym; lsym = setNextItem(sset)) {
347 /* if usage is the same then prefer
348 the spill the smaller of the two */
349 if ( lsym->used == sym->used )
350 if (getSize(lsym->type) < getSize(sym->type))
354 if (lsym->used < sym->used )
359 setToNull((void **)&sset);
364 /*-----------------------------------------------------------------*/
365 /* noOverLap - will iterate through the list looking for over lap */
366 /*-----------------------------------------------------------------*/
367 static int noOverLap (set *itmpStack, symbol *fsym)
372 for (sym = setFirstItem(itmpStack); sym;
373 sym = setNextItem(itmpStack)) {
374 if (sym->liveTo > fsym->liveFrom )
382 /*-----------------------------------------------------------------*/
383 /* isFree - will return 1 if the a free spil location is found */
384 /*-----------------------------------------------------------------*/
385 static DEFSETFUNC(isFree)
388 V_ARG(symbol **,sloc);
389 V_ARG(symbol *,fsym);
391 /* if already found */
395 /* if it is free && and the itmp assigned to
396 this does not have any overlapping live ranges
397 with the one currently being assigned and
398 the size can be accomodated */
400 noOverLap(sym->usl.itmpStack,fsym) &&
401 getSize(sym->type) >= getSize(fsym->type)) {
409 /*-----------------------------------------------------------------*/
410 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
411 /*-----------------------------------------------------------------*/
412 static void spillLRWithPtrReg (symbol *forSym)
418 if (!_G.regAssigned ||
419 bitVectIsZero(_G.regAssigned))
422 r0 = pic14_regWithIdx(R0_IDX);
423 r1 = pic14_regWithIdx(R1_IDX);
425 /* for all live ranges */
426 for (lrsym = hTabFirstItem(liveRanges,&k) ; lrsym ;
427 lrsym = hTabNextItem(liveRanges,&k) ) {
430 /* if no registers assigned to it or
432 /* if it does not overlap with this then
433 not need to spill it */
435 if (lrsym->isspilt || !lrsym->nRegs ||
436 (lrsym->liveTo < forSym->liveFrom))
439 /* go thru the registers : if it is either
440 r0 or r1 then spil it */
441 for (j = 0 ; j < lrsym->nRegs ; j++ )
442 if (lrsym->regs[j] == r0 ||
443 lrsym->regs[j] == r1 ) {
451 /*-----------------------------------------------------------------*/
452 /* createStackSpil - create a location on the stack to spil */
453 /*-----------------------------------------------------------------*/
454 static symbol *createStackSpil (symbol *sym)
457 int useXstack, model, noOverlay;
461 /* first go try and find a free one that is already
462 existing on the stack */
463 if (applyToSet(_G.stackSpil,isFree,&sloc, sym)) {
464 /* found a free one : just update & return */
465 sym->usl.spillLoc = sloc;
468 addSetHead(&sloc->usl.itmpStack,sym);
472 /* could not then have to create one , this is the hard part
473 we need to allocate this on the stack : this is really a
474 hack!! but cannot think of anything better at this time */
476 if (sprintf(slocBuffer,"sloc%d",_G.slocNum++) >= sizeof(slocBuffer))
478 fprintf(stderr, "***Internal error: slocBuffer overflowed: %s:%d\n",
483 sloc = newiTemp(slocBuffer);
485 /* set the type to the spilling symbol */
486 sloc->type = copyLinkChain(sym->type);
487 sloc->etype = getSpec(sloc->type);
488 SPEC_SCLS(sloc->etype) = S_DATA ;
489 SPEC_EXTR(sloc->etype) = 0;
491 /* we don't allow it to be allocated`
492 onto the external stack since : so we
493 temporarily turn it off ; we also
494 turn off memory model to prevent
495 the spil from going to the external storage
496 and turn off overlaying
499 useXstack = options.useXstack;
500 model = options.model;
501 noOverlay = options.noOverlay;
502 options.noOverlay = 1;
503 options.model = options.useXstack = 0;
507 options.useXstack = useXstack;
508 options.model = model;
509 options.noOverlay = noOverlay;
510 sloc->isref = 1; /* to prevent compiler warning */
512 /* if it is on the stack then update the stack */
513 if (IN_STACK(sloc->etype)) {
514 currFunc->stack += getSize(sloc->type);
515 _G.stackExtend += getSize(sloc->type);
517 _G.dataExtend += getSize(sloc->type);
519 /* add it to the _G.stackSpil set */
520 addSetHead(&_G.stackSpil,sloc);
521 sym->usl.spillLoc = sloc;
524 /* add it to the set of itempStack set
525 of the spill location */
526 addSetHead(&sloc->usl.itmpStack,sym);
530 /*-----------------------------------------------------------------*/
531 /* isSpiltOnStack - returns true if the spil location is on stack */
532 /*-----------------------------------------------------------------*/
533 static bool isSpiltOnStack (symbol *sym)
543 /* if (sym->_G.stackSpil) */
546 if (!sym->usl.spillLoc)
549 etype = getSpec(sym->usl.spillLoc->type);
556 /*-----------------------------------------------------------------*/
557 /* spillThis - spils a specific operand */
558 /*-----------------------------------------------------------------*/
559 static void spillThis (symbol *sym)
562 /* if this is rematerializable or has a spillLocation
563 we are okay, else we need to create a spillLocation
565 if (!(sym->remat || sym->usl.spillLoc))
566 createStackSpil (sym);
569 /* mark it has spilt & put it in the spilt set */
571 _G.spiltSet = bitVectSetBit(_G.spiltSet,sym->key);
573 bitVectUnSetBit(_G.regAssigned,sym->key);
575 for (i = 0 ; i < sym->nRegs ; i++)
578 freeReg(sym->regs[i]);
582 /* if spilt on stack then free up r0 & r1
583 if they could have been assigned to some
585 if (!pic14_ptrRegReq && isSpiltOnStack(sym)) {
587 spillLRWithPtrReg(sym);
590 if (sym->usl.spillLoc && !sym->remat)
591 sym->usl.spillLoc->allocreq = 1;
595 /*-----------------------------------------------------------------*/
596 /* selectSpil - select a iTemp to spil : rather a simple procedure */
597 /*-----------------------------------------------------------------*/
598 static symbol *selectSpil (iCode *ic, eBBlock *ebp, symbol *forSym)
600 bitVect *lrcs= NULL ;
604 /* get the spillable live ranges */
605 lrcs = computeSpillable (ic);
607 /* get all live ranges that are rematerizable */
608 if ((selectS = liveRangesWith(lrcs,rematable,ebp,ic))) {
610 /* return the least used of these */
611 return leastUsedLR(selectS);
614 /* get live ranges with spillLocations in direct space */
615 if ((selectS = liveRangesWith(lrcs,directSpilLoc,ebp,ic))) {
616 sym = leastUsedLR(selectS);
617 strcpy(sym->rname,(sym->usl.spillLoc->rname[0] ?
618 sym->usl.spillLoc->rname :
619 sym->usl.spillLoc->name));
621 /* mark it as allocation required */
622 sym->usl.spillLoc->allocreq = 1;
626 /* if the symbol is local to the block then */
627 if (forSym->liveTo < ebp->lSeq) {
629 /* check if there are any live ranges allocated
630 to registers that are not used in this block */
631 if (!_G.blockSpil && (selectS = liveRangesWith(lrcs,notUsedInBlock,ebp,ic))) {
632 sym = leastUsedLR(selectS);
633 /* if this is not rematerializable */
641 /* check if there are any live ranges that not
642 used in the remainder of the block */
643 if (!_G.blockSpil && (selectS = liveRangesWith(lrcs,notUsedInRemaining,ebp,ic))) {
644 sym = leastUsedLR (selectS);
653 /* find live ranges with spillocation && not used as pointers */
654 if ((selectS = liveRangesWith(lrcs,hasSpilLocnoUptr,ebp,ic))) {
656 sym = leastUsedLR(selectS);
657 /* mark this as allocation required */
658 sym->usl.spillLoc->allocreq = 1;
662 /* find live ranges with spillocation */
663 if ((selectS = liveRangesWith(lrcs,hasSpilLoc,ebp,ic))) {
665 sym = leastUsedLR(selectS);
666 sym->usl.spillLoc->allocreq = 1;
670 /* couldn't find then we need to create a spil
671 location on the stack , for which one? the least
673 if ((selectS = liveRangesWith(lrcs,noSpilLoc,ebp,ic))) {
675 /* return a created spil location */
676 sym = createStackSpil(leastUsedLR(selectS));
677 sym->usl.spillLoc->allocreq = 1;
681 /* this is an extreme situation we will spill
682 this one : happens very rarely but it does happen */
683 spillThis ( forSym );
688 /*-----------------------------------------------------------------*/
689 /* spilSomething - spil some variable & mark registers as free */
690 /*-----------------------------------------------------------------*/
691 static bool spilSomething (iCode *ic, eBBlock *ebp, symbol *forSym)
696 /* get something we can spil */
697 ssym = selectSpil(ic,ebp,forSym);
699 /* mark it as spilt */
701 _G.spiltSet = bitVectSetBit(_G.spiltSet,ssym->key);
703 /* mark it as not register assigned &
704 take it away from the set */
705 bitVectUnSetBit(_G.regAssigned,ssym->key);
707 /* mark the registers as free */
708 for (i = 0 ; i < ssym->nRegs ;i++ )
710 freeReg(ssym->regs[i]);
712 /* if spilt on stack then free up r0 & r1
713 if they could have been assigned to as gprs */
714 if (!pic14_ptrRegReq && isSpiltOnStack(ssym) ) {
716 spillLRWithPtrReg(ssym);
719 /* if this was a block level spil then insert push & pop
720 at the start & end of block respectively */
721 if (ssym->blockSpil) {
722 iCode *nic = newiCode(IPUSH,operandFromSymbol(ssym),NULL);
723 /* add push to the start of the block */
724 addiCodeToeBBlock(ebp,nic,( ebp->sch->op == LABEL ?
725 ebp->sch->next : ebp->sch));
726 nic = newiCode(IPOP,operandFromSymbol(ssym),NULL);
727 /* add pop to the end of the block */
728 addiCodeToeBBlock(ebp,nic,NULL);
731 /* if spilt because not used in the remainder of the
732 block then add a push before this instruction and
733 a pop at the end of the block */
734 if (ssym->remainSpil) {
736 iCode *nic = newiCode(IPUSH,operandFromSymbol(ssym),NULL);
737 /* add push just before this instruction */
738 addiCodeToeBBlock(ebp,nic,ic);
740 nic = newiCode(IPOP,operandFromSymbol(ssym),NULL);
741 /* add pop to the end of the block */
742 addiCodeToeBBlock(ebp,nic,NULL);
751 /*-----------------------------------------------------------------*/
752 /* getRegPtr - will try for PTR if not a GPR type if not spil */
753 /*-----------------------------------------------------------------*/
754 static regs *getRegPtr (iCode *ic, eBBlock *ebp, symbol *sym)
759 /* try for a ptr type */
760 if ((reg = allocReg(REG_PTR)))
763 /* try for gpr type */
764 if ((reg = allocReg(REG_GPR)))
767 /* we have to spil */
768 if (!spilSomething (ic,ebp,sym))
771 /* this looks like an infinite loop but
772 in really selectSpil will abort */
776 /*-----------------------------------------------------------------*/
777 /* getRegGpr - will try for GPR if not spil */
778 /*-----------------------------------------------------------------*/
779 static regs *getRegGpr (iCode *ic, eBBlock *ebp,symbol *sym)
784 /* try for gpr type */
785 if ((reg = allocReg(REG_GPR)))
788 if (!pic14_ptrRegReq)
789 if ((reg = allocReg(REG_PTR)))
792 /* we have to spil */
793 if (!spilSomething (ic,ebp,sym))
796 /* this looks like an infinite loop but
797 in really selectSpil will abort */
801 /*-----------------------------------------------------------------*/
802 /* symHasReg - symbol has a given register */
803 /*-----------------------------------------------------------------*/
804 static bool symHasReg(symbol *sym,regs *reg)
808 for ( i = 0 ; i < sym->nRegs ; i++)
809 if (sym->regs[i] == reg)
815 /*-----------------------------------------------------------------*/
816 /* deassignLRs - check the live to and if they have registers & are*/
817 /* not spilt then free up the registers */
818 /*-----------------------------------------------------------------*/
819 static void deassignLRs (iCode *ic, eBBlock *ebp)
825 for (sym = hTabFirstItem(liveRanges,&k); sym;
826 sym = hTabNextItem(liveRanges,&k)) {
829 /* if it does not end here */
830 if (sym->liveTo > ic->seq )
833 /* if it was spilt on stack then we can
834 mark the stack spil location as free */
836 if (sym->stackSpil) {
837 sym->usl.spillLoc->isFree = 1;
843 if (!bitVectBitValue(_G.regAssigned,sym->key))
846 /* special case check if this is an IFX &
847 the privious one was a pop and the
848 previous one was not spilt then keep track
850 if (ic->op == IFX && ic->prev &&
851 ic->prev->op == IPOP &&
852 !ic->prev->parmPush &&
853 !OP_SYMBOL(IC_LEFT(ic->prev))->isspilt)
854 psym = OP_SYMBOL(IC_LEFT(ic->prev));
859 bitVectUnSetBit(_G.regAssigned,sym->key);
861 /* if the result of this one needs registers
862 and does not have it then assign it right
865 ! (SKIP_IC2(ic) || /* not a special icode */
866 ic->op == JUMPTABLE ||
872 (result = OP_SYMBOL(IC_RESULT(ic))) && /* has a result */
873 result->liveTo > ic->seq && /* and will live beyond this */
874 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
875 result->regType == sym->regType && /* same register types */
876 result->nRegs && /* which needs registers */
877 ! result->isspilt && /* and does not already have them */
879 ! bitVectBitValue(_G.regAssigned,result->key) &&
880 /* the number of free regs + number of regs in this LR
881 can accomodate the what result Needs */
882 ((nfreeRegsType(result->regType) +
883 sym->nRegs) >= result->nRegs)
886 for (i = 0 ; i < max(sym->nRegs,result->nRegs) ; i++)
888 result->regs[i] = sym->regs[i] ;
890 result->regs[i] = getRegGpr (ic,ebp,result);
892 _G.regAssigned = bitVectSetBit(_G.regAssigned,result->key);
896 /* free the remaining */
897 for (; i < sym->nRegs ; i++) {
899 if (!symHasReg(psym,sym->regs[i]))
900 freeReg(sym->regs[i]);
902 freeReg(sym->regs[i]);
909 /*-----------------------------------------------------------------*/
910 /* reassignLR - reassign this to registers */
911 /*-----------------------------------------------------------------*/
912 static void reassignLR (operand *op)
914 symbol *sym = OP_SYMBOL(op);
917 /* not spilt any more */
918 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
919 bitVectUnSetBit(_G.spiltSet,sym->key);
921 _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
925 for (i=0;i<sym->nRegs;i++)
926 sym->regs[i]->isFree = 0;
929 /*-----------------------------------------------------------------*/
930 /* willCauseSpill - determines if allocating will cause a spill */
931 /*-----------------------------------------------------------------*/
932 static int willCauseSpill ( int nr, int rt)
934 /* first check if there are any avlb registers
935 of te type required */
937 /* special case for pointer type
938 if pointer type not avlb then
939 check for type gpr */
940 if (nFreeRegs(rt) >= nr)
942 if (nFreeRegs(REG_GPR) >= nr)
945 if (pic14_ptrRegReq) {
946 if (nFreeRegs(rt) >= nr)
949 if (nFreeRegs(REG_PTR) +
950 nFreeRegs(REG_GPR) >= nr)
955 /* it will cause a spil */
959 /*-----------------------------------------------------------------*/
960 /* positionRegs - the allocator can allocate same registers to res-*/
961 /* ult and operand, if this happens make sure they are in the same */
962 /* position as the operand otherwise chaos results */
963 /*-----------------------------------------------------------------*/
964 static void positionRegs (symbol *result, symbol *opsym, int lineno)
966 int count = min(result->nRegs,opsym->nRegs);
967 int i , j = 0, shared = 0;
969 /* if the result has been spilt then cannot share */
974 /* first make sure that they actually share */
975 for ( i = 0 ; i < count; i++ ) {
976 for (j = 0 ; j < count ; j++ ) {
977 if (result->regs[i] == opsym->regs[j] && i !=j) {
985 regs *tmp = result->regs[i];
986 result->regs[i] = result->regs[j];
987 result->regs[j] = tmp;
992 /*-----------------------------------------------------------------*/
993 /* serialRegAssign - serially allocate registers to the variables */
994 /*-----------------------------------------------------------------*/
995 static void serialRegAssign (eBBlock **ebbs, int count)
1000 for (i = 0; i < count ; i++ ) {
1004 if (ebbs[i]->noPath &&
1005 (ebbs[i]->entryLabel != entryLabel &&
1006 ebbs[i]->entryLabel != returnLabel ))
1009 /* of all instructions do */
1010 for (ic = ebbs[i]->sch ; ic ; ic = ic->next) {
1012 /* if this is an ipop that means some live
1013 range will have to be assigned again */
1015 reassignLR (IC_LEFT(ic));
1017 /* if result is present && is a true symbol */
1018 if (IC_RESULT(ic) && ic->op != IFX &&
1019 IS_TRUE_SYMOP(IC_RESULT(ic)))
1020 OP_SYMBOL(IC_RESULT(ic))->allocreq = 1;
1022 /* take away registers from live
1023 ranges that end at this instruction */
1024 deassignLRs (ic, ebbs[i]) ;
1026 /* some don't need registers */
1028 ic->op == JUMPTABLE ||
1032 (IC_RESULT(ic) &&POINTER_SET(ic)) )
1035 /* now we need to allocate registers
1036 only for the result */
1037 if (IC_RESULT(ic)) {
1038 symbol *sym = OP_SYMBOL(IC_RESULT(ic));
1044 /* if it does not need or is spilt
1045 or is already assigned to registers
1046 or will not live beyond this instructions */
1049 bitVectBitValue(_G.regAssigned,sym->key) ||
1050 sym->liveTo <= ic->seq)
1053 /* if some liverange has been spilt at the block level
1054 and this one live beyond this block then spil this
1056 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq) {
1060 /* if trying to allocate this will cause
1061 a spill and there is nothing to spill
1062 or this one is rematerializable then
1064 willCS = willCauseSpill(sym->nRegs,sym->regType);
1065 spillable = computeSpillable(ic);
1067 (willCS && bitVectIsZero(spillable) ) ) {
1074 /* if it has a spillocation & is used less than
1075 all other live ranges then spill this */
1076 if ( willCS && sym->usl.spillLoc ) {
1079 leastUsedLR(liveRangesWith (spillable ,
1084 leastUsed->used > sym->used) {
1090 /* if we need ptr regs for the right side
1092 if (POINTER_GET(ic) && getSize(OP_SYMBOL(IC_LEFT(ic))->type)
1098 /* else we assign registers to it */
1099 _G.regAssigned = bitVectSetBit(_G.regAssigned,sym->key);
1101 for (j = 0 ; j < sym->nRegs ;j++ ) {
1102 if (sym->regType == REG_PTR)
1103 sym->regs[j] = getRegPtr(ic,ebbs[i],sym);
1105 sym->regs[j] = getRegGpr(ic,ebbs[i],sym);
1107 /* if the allocation falied which means
1108 this was spilt then break */
1112 /* if it shares registers with operands make sure
1113 that they are in the same position */
1114 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic)) &&
1115 OP_SYMBOL(IC_LEFT(ic))->nRegs && ic->op != '=')
1116 positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1117 OP_SYMBOL(IC_LEFT(ic)),ic->lineno);
1118 /* do the same for the right operand */
1119 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic)) &&
1120 OP_SYMBOL(IC_RIGHT(ic))->nRegs && ic->op != '=')
1121 positionRegs(OP_SYMBOL(IC_RESULT(ic)),
1122 OP_SYMBOL(IC_RIGHT(ic)),ic->lineno);
1134 /*-----------------------------------------------------------------*/
1135 /* rUmaskForOp :- returns register mask for an operand */
1136 /*-----------------------------------------------------------------*/
1137 static bitVect *rUmaskForOp (operand *op)
1143 /* only temporaries are assigned registers */
1147 sym = OP_SYMBOL(op);
1149 /* if spilt or no registers assigned to it
1151 if (sym->isspilt || !sym->nRegs)
1154 rumask = newBitVect(pic14_nRegs);
1156 for (j = 0; j < sym->nRegs; j++) {
1157 rumask = bitVectSetBit(rumask,
1158 sym->regs[j]->rIdx);
1164 /*-----------------------------------------------------------------*/
1165 /* regsUsedIniCode :- returns bit vector of registers used in iCode*/
1166 /*-----------------------------------------------------------------*/
1167 static bitVect *regsUsedIniCode (iCode *ic)
1169 bitVect *rmask = newBitVect(pic14_nRegs);
1171 /* do the special cases first */
1172 if (ic->op == IFX ) {
1173 rmask = bitVectUnion(rmask,
1174 rUmaskForOp(IC_COND(ic)));
1178 /* for the jumptable */
1179 if (ic->op == JUMPTABLE) {
1180 rmask = bitVectUnion(rmask,
1181 rUmaskForOp(IC_JTCOND(ic)));
1186 /* of all other cases */
1188 rmask = bitVectUnion(rmask,
1189 rUmaskForOp(IC_LEFT(ic)));
1193 rmask = bitVectUnion(rmask,
1194 rUmaskForOp(IC_RIGHT(ic)));
1197 rmask = bitVectUnion(rmask,
1198 rUmaskForOp(IC_RESULT(ic)));
1204 /*-----------------------------------------------------------------*/
1205 /* createRegMask - for each instruction will determine the regsUsed*/
1206 /*-----------------------------------------------------------------*/
1207 static void createRegMask (eBBlock **ebbs, int count)
1211 /* for all blocks */
1212 for (i = 0; i < count ; i++ ) {
1215 if ( ebbs[i]->noPath &&
1216 ( ebbs[i]->entryLabel != entryLabel &&
1217 ebbs[i]->entryLabel != returnLabel ))
1220 /* for all instructions */
1221 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
1225 if (SKIP_IC2(ic) || !ic->rlive)
1228 /* first mark the registers used in this
1230 ic->rUsed = regsUsedIniCode(ic);
1231 _G.funcrUsed = bitVectUnion(_G.funcrUsed,ic->rUsed);
1233 /* now create the register mask for those
1234 registers that are in use : this is a
1235 super set of ic->rUsed */
1236 ic->rMask = newBitVect(pic14_nRegs+1);
1238 /* for all live Ranges alive at this point */
1239 for (j = 1; j < ic->rlive->size; j++ ) {
1243 /* if not alive then continue */
1244 if (!bitVectBitValue(ic->rlive,j))
1247 /* find the live range we are interested in */
1248 if (!(sym = hTabItemWithKey(liveRanges,j))) {
1249 werror (E_INTERNAL_ERROR,__FILE__,__LINE__,
1250 "createRegMask cannot find live range");
1254 /* if no register assigned to it */
1255 if (!sym->nRegs || sym->isspilt)
1258 /* for all the registers allocated to it */
1259 for (k = 0 ; k < sym->nRegs ;k++)
1262 bitVectSetBit(ic->rMask,sym->regs[k]->rIdx);
1268 /*-----------------------------------------------------------------*/
1269 /* rematStr - returns the rematerialized string for a remat var */
1270 /*-----------------------------------------------------------------*/
1271 static char *rematStr (symbol *sym)
1274 iCode *ic = sym->rematiCode;
1279 /* if plus or minus print the right hand side */
1281 if (ic->op == '+' || ic->op == '-') {
1282 sprintf(s,"0x%04x %c ",(int) operandLitValue(IC_RIGHT(ic)),
1285 ic = OP_SYMBOL(IC_LEFT(ic))->rematiCode;
1289 if (ic->op == '+' || ic->op == '-') {
1290 iCode *ric = OP_SYMBOL(IC_LEFT(ic))->rematiCode;
1291 sprintf(s,"(%s %c 0x%04x)",
1292 OP_SYMBOL(IC_LEFT(ric))->rname,
1294 (int) operandLitValue(IC_RIGHT(ic)));
1297 //ic = OP_SYMBOL(IC_LEFT(ic))->rematiCode;
1302 /* we reached the end */
1303 sprintf(s,"%s",OP_SYMBOL(IC_LEFT(ic))->rname);
1307 printf("%s\n",buffer);
1311 /*-----------------------------------------------------------------*/
1312 /* regTypeNum - computes the type & number of registers required */
1313 /*-----------------------------------------------------------------*/
1314 static void regTypeNum ()
1320 /* for each live range do */
1321 for ( sym = hTabFirstItem(liveRanges,&k); sym ;
1322 sym = hTabNextItem(liveRanges,&k)) {
1324 /* if used zero times then no registers needed */
1325 if ((sym->liveTo - sym->liveFrom) == 0)
1329 /* if the live range is a temporary */
1332 /* if the type is marked as a conditional */
1333 if (sym->regType == REG_CND)
1336 /* if used in return only then we don't
1338 if (sym->ruonly || sym->accuse) {
1339 if (IS_AGGREGATE(sym->type) || sym->isptr)
1340 sym->type = aggrToPtr(sym->type,FALSE);
1344 /* if the symbol has only one definition &
1345 that definition is a get_pointer and the
1346 pointer we are getting is rematerializable and
1349 if (bitVectnBitsOn(sym->defs) == 1 &&
1350 (ic = hTabItemWithKey(iCodehTab,
1351 bitVectFirstBit(sym->defs))) &&
1353 !IS_BITVAR(sym->etype)) {
1356 /* if remat in data space */
1357 if (OP_SYMBOL(IC_LEFT(ic))->remat &&
1358 DCL_TYPE(aggrToPtr(sym->type,FALSE)) == POINTER) {
1360 /* create a psuedo symbol & force a spil */
1361 symbol *psym = newSymbol(rematStr(OP_SYMBOL(IC_LEFT(ic))),1);
1362 psym->type = sym->type;
1363 psym->etype = sym->etype;
1364 strcpy(psym->rname,psym->name);
1366 sym->usl.spillLoc = psym;
1370 /* if in data space or idata space then try to
1371 allocate pointer register */
1375 /* if not then we require registers */
1376 sym->nRegs = ((IS_AGGREGATE(sym->type) || sym->isptr ) ?
1377 getSize(sym->type = aggrToPtr(sym->type,FALSE)) :
1378 getSize(sym->type));
1380 if (sym->nRegs > 4) {
1381 fprintf(stderr,"allocated more than 4 or 0 registers for type ");
1382 printTypeChain(sym->type,stderr);fprintf(stderr,"\n");
1385 /* determine the type of register required */
1386 if (sym->nRegs == 1 &&
1387 IS_PTR(sym->type) &&
1389 sym->regType = REG_PTR ;
1391 sym->regType = REG_GPR ;
1394 /* for the first run we don't provide */
1395 /* registers for true symbols we will */
1396 /* see how things go */
1402 /*-----------------------------------------------------------------*/
1403 /* freeAllRegs - mark all registers as free */
1404 /*-----------------------------------------------------------------*/
1405 static void freeAllRegs()
1409 for (i=0;i< pic14_nRegs;i++ )
1410 regspic14[i].isFree = 1;
1413 /*-----------------------------------------------------------------*/
1414 /* deallocStackSpil - this will set the stack pointer back */
1415 /*-----------------------------------------------------------------*/
1416 static DEFSETFUNC(deallocStackSpil)
1424 /*-----------------------------------------------------------------*/
1425 /* farSpacePackable - returns the packable icode for far variables */
1426 /*-----------------------------------------------------------------*/
1427 static iCode *farSpacePackable (iCode *ic)
1431 /* go thru till we find a definition for the
1432 symbol on the right */
1433 for ( dic = ic->prev ; dic ; dic = dic->prev) {
1435 /* if the definition is a call then no */
1436 if ((dic->op == CALL || dic->op == PCALL) &&
1437 IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1441 /* if shift by unknown amount then not */
1442 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1443 IC_RESULT(dic)->key == IC_RIGHT(ic)->key)
1446 /* if pointer get and size > 1 */
1447 if (POINTER_GET(dic) &&
1448 getSize(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)) > 1)
1451 if (POINTER_SET(dic) &&
1452 getSize(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)) > 1)
1455 /* if any three is a true symbol in far space */
1456 if (IC_RESULT(dic) &&
1457 IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1458 isOperandInFarSpace(IC_RESULT(dic)))
1461 if (IC_RIGHT(dic) &&
1462 IS_TRUE_SYMOP(IC_RIGHT(dic)) &&
1463 isOperandInFarSpace(IC_RIGHT(dic)) &&
1464 !isOperandEqual(IC_RIGHT(dic),IC_RESULT(ic)))
1468 IS_TRUE_SYMOP(IC_LEFT(dic)) &&
1469 isOperandInFarSpace(IC_LEFT(dic)) &&
1470 !isOperandEqual(IC_LEFT(dic),IC_RESULT(ic)))
1473 if (isOperandEqual(IC_RIGHT(ic),IC_RESULT(dic))) {
1474 if ( (dic->op == LEFT_OP ||
1475 dic->op == RIGHT_OP ||
1477 IS_OP_LITERAL(IC_RIGHT(dic)))
1487 /*-----------------------------------------------------------------*/
1488 /* packRegsForAssign - register reduction for assignment */
1489 /*-----------------------------------------------------------------*/
1490 static int packRegsForAssign (iCode *ic,eBBlock *ebp)
1495 if (!IS_ITEMP(IC_RIGHT(ic)) ||
1496 OP_SYMBOL(IC_RIGHT(ic))->isind ||
1497 OP_LIVETO(IC_RIGHT(ic)) > ic->seq) {
1501 /* if the true symbol is defined in far space or on stack
1502 then we should not since this will increase register pressure */
1503 if (isOperandInFarSpace(IC_RESULT(ic))) {
1504 if ((dic = farSpacePackable(ic)))
1510 /* find the definition of iTempNN scanning backwards if we find a
1511 a use of the true symbol in before we find the definition then
1513 for ( dic = ic->prev ; dic ; dic = dic->prev) {
1515 /* if there is a function call and this is
1516 a parameter & not my parameter then don't pack it */
1517 if ( (dic->op == CALL || dic->op == PCALL) &&
1518 (OP_SYMBOL(IC_RESULT(ic))->_isparm &&
1519 !OP_SYMBOL(IC_RESULT(ic))->ismyparm)) {
1527 if (IS_TRUE_SYMOP(IC_RESULT(dic)) &&
1528 IS_OP_VOLATILE(IC_RESULT(dic))) {
1533 if (IS_SYMOP(IC_RESULT(dic)) &&
1534 IC_RESULT(dic)->key == IC_RIGHT(ic)->key) {
1535 if (POINTER_SET(dic))
1541 if (IS_SYMOP(IC_RIGHT(dic)) &&
1542 (IC_RIGHT(dic)->key == IC_RESULT(ic)->key ||
1543 IC_RIGHT(dic)->key == IC_RIGHT(ic)->key)) {
1548 if (IS_SYMOP(IC_LEFT(dic)) &&
1549 (IC_LEFT(dic)->key == IC_RESULT(ic)->key ||
1550 IC_LEFT(dic)->key == IC_RIGHT(ic)->key)) {
1555 if (POINTER_SET(dic) &&
1556 IC_RESULT(dic)->key == IC_RESULT(ic)->key ) {
1563 return 0 ; /* did not find */
1565 /* if the result is on stack or iaccess then it must be
1566 the same atleast one of the operands */
1567 if (OP_SYMBOL(IC_RESULT(ic))->onStack ||
1568 OP_SYMBOL(IC_RESULT(ic))->iaccess ) {
1570 /* the operation has only one symbol
1571 operator then we can pack */
1572 if ((IC_LEFT(dic) && !IS_SYMOP(IC_LEFT(dic))) ||
1573 (IC_RIGHT(dic) && !IS_SYMOP(IC_RIGHT(dic))))
1576 if (!((IC_LEFT(dic) &&
1577 IC_RESULT(ic)->key == IC_LEFT(dic)->key) ||
1579 IC_RESULT(ic)->key == IC_RIGHT(dic)->key)))
1583 /* found the definition */
1584 /* replace the result with the result of */
1585 /* this assignment and remove this assignment */
1586 IC_RESULT(dic) = IC_RESULT(ic) ;
1588 if (IS_ITEMP(IC_RESULT(dic)) && OP_SYMBOL(IC_RESULT(dic))->liveFrom > dic->seq) {
1589 OP_SYMBOL(IC_RESULT(dic))->liveFrom = dic->seq;
1591 /* delete from liverange table also
1592 delete from all the points inbetween and the new
1594 for ( sic = dic; sic != ic ; sic = sic->next ) {
1595 bitVectUnSetBit(sic->rlive,IC_RESULT(ic)->key);
1596 if (IS_ITEMP(IC_RESULT(dic)))
1597 bitVectSetBit(sic->rlive,IC_RESULT(dic)->key);
1600 remiCodeFromeBBlock(ebp,ic);
1601 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
1602 OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
1608 /*-----------------------------------------------------------------*/
1609 /* findAssignToSym : scanning backwards looks for first assig found*/
1610 /*-----------------------------------------------------------------*/
1611 static iCode *findAssignToSym (operand *op,iCode *ic)
1615 for (dic = ic->prev ; dic ; dic = dic->prev) {
1617 /* if definition by assignment */
1618 if (dic->op == '=' &&
1619 !POINTER_SET(dic) &&
1620 IC_RESULT(dic)->key == op->key
1621 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1624 /* we are interested only if defined in far space */
1625 /* or in stack space in case of + & - */
1627 /* if assigned to a non-symbol then return
1629 if (!IS_SYMOP(IC_RIGHT(dic)))
1632 /* if the symbol is in far space then
1634 if (isOperandInFarSpace(IC_RIGHT(dic)))
1637 /* for + & - operations make sure that
1638 if it is on the stack it is the same
1639 as one of the three operands */
1640 if ((ic->op == '+' || ic->op == '-') &&
1641 OP_SYMBOL(IC_RIGHT(dic))->onStack) {
1643 if ( IC_RESULT(ic)->key != IC_RIGHT(dic)->key &&
1644 IC_LEFT(ic)->key != IC_RIGHT(dic)->key &&
1645 IC_RIGHT(ic)->key != IC_RIGHT(dic)->key)
1653 /* if we find an usage then we cannot delete it */
1654 if (IC_LEFT(dic) && IC_LEFT(dic)->key == op->key)
1657 if (IC_RIGHT(dic) && IC_RIGHT(dic)->key == op->key)
1660 if (POINTER_SET(dic) && IC_RESULT(dic)->key == op->key)
1664 /* now make sure that the right side of dic
1665 is not defined between ic & dic */
1667 iCode *sic = dic->next ;
1669 for (; sic != ic ; sic = sic->next)
1670 if (IC_RESULT(sic) &&
1671 IC_RESULT(sic)->key == IC_RIGHT(dic)->key)
1680 /*-----------------------------------------------------------------*/
1681 /* packRegsForSupport :- reduce some registers for support calls */
1682 /*-----------------------------------------------------------------*/
1683 static int packRegsForSupport (iCode *ic, eBBlock *ebp)
1686 /* for the left & right operand :- look to see if the
1687 left was assigned a true symbol in far space in that
1688 case replace them */
1689 if (IS_ITEMP(IC_LEFT(ic)) &&
1690 OP_SYMBOL(IC_LEFT(ic))->liveTo <= ic->seq) {
1691 iCode *dic = findAssignToSym(IC_LEFT(ic),ic);
1697 /* found it we need to remove it from the
1699 for ( sic = dic; sic != ic ; sic = sic->next )
1700 bitVectUnSetBit(sic->rlive,IC_LEFT(ic)->key);
1702 IC_LEFT(ic)->operand.symOperand =
1703 IC_RIGHT(dic)->operand.symOperand;
1704 IC_LEFT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1705 remiCodeFromeBBlock(ebp,dic);
1706 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1710 /* do the same for the right operand */
1713 IS_ITEMP(IC_RIGHT(ic)) &&
1714 OP_SYMBOL(IC_RIGHT(ic))->liveTo <= ic->seq) {
1715 iCode *dic = findAssignToSym(IC_RIGHT(ic),ic);
1721 /* if this is a subtraction & the result
1722 is a true symbol in far space then don't pack */
1723 if (ic->op == '-' && IS_TRUE_SYMOP(IC_RESULT(dic))) {
1724 sym_link *etype =getSpec(operandType(IC_RESULT(dic)));
1725 if (IN_FARSPACE(SPEC_OCLS(etype)))
1728 /* found it we need to remove it from the
1730 for ( sic = dic; sic != ic ; sic = sic->next )
1731 bitVectUnSetBit(sic->rlive,IC_RIGHT(ic)->key);
1733 IC_RIGHT(ic)->operand.symOperand =
1734 IC_RIGHT(dic)->operand.symOperand;
1735 IC_RIGHT(ic)->key = IC_RIGHT(dic)->operand.symOperand->key;
1737 remiCodeFromeBBlock(ebp,dic);
1738 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
1745 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1748 /*-----------------------------------------------------------------*/
1749 /* packRegsForOneuse : - will reduce some registers for single Use */
1750 /*-----------------------------------------------------------------*/
1751 static iCode *packRegsForOneuse (iCode *ic, operand *op , eBBlock *ebp)
1756 /* if returning a literal then do nothing */
1760 /* only upto 2 bytes since we cannot predict
1761 the usage of b, & acc */
1762 if (getSize(operandType(op)) > (fReturnSize - 2) &&
1767 /* this routine will mark the a symbol as used in one
1768 instruction use only && if the defintion is local
1769 (ie. within the basic block) && has only one definition &&
1770 that definiion is either a return value from a
1771 function or does not contain any variables in
1773 uses = bitVectCopy(OP_USES(op));
1774 bitVectUnSetBit(uses,ic->key); /* take away this iCode */
1775 if (!bitVectIsZero(uses)) /* has other uses */
1778 /* if it has only one defintion */
1779 if (bitVectnBitsOn(OP_DEFS(op)) > 1)
1780 return NULL ; /* has more than one definition */
1782 /* get the that definition */
1784 hTabItemWithKey(iCodehTab,
1785 bitVectFirstBit(OP_DEFS(op)))))
1788 /* found the definition now check if it is local */
1789 if (dic->seq < ebp->fSeq ||
1790 dic->seq > ebp->lSeq)
1791 return NULL ; /* non-local */
1793 /* now check if it is the return from
1795 if (dic->op == CALL || dic->op == PCALL ) {
1796 if (ic->op != SEND && ic->op != RETURN) {
1797 OP_SYMBOL(op)->ruonly = 1;
1804 /* otherwise check that the definition does
1805 not contain any symbols in far space */
1806 if (isOperandInFarSpace(IC_LEFT(dic)) ||
1807 isOperandInFarSpace(IC_RIGHT(dic)) ||
1808 IS_OP_RUONLY(IC_LEFT(ic)) ||
1809 IS_OP_RUONLY(IC_RIGHT(ic)) ) {
1813 /* if pointer set then make sure the pointer
1815 if (POINTER_SET(dic) &&
1816 !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1819 if (POINTER_GET(dic) &&
1820 !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1825 /* also make sure the intervenening instructions
1826 don't have any thing in far space */
1827 for (dic = dic->next ; dic && dic != ic ; dic = dic->next) {
1829 /* if there is an intervening function call then no */
1830 if (dic->op == CALL || dic->op == PCALL)
1832 /* if pointer set then make sure the pointer
1834 if (POINTER_SET(dic) &&
1835 !IS_DATA_PTR(aggrToPtr(operandType(IC_RESULT(dic)),FALSE)))
1838 if (POINTER_GET(dic) &&
1839 !IS_DATA_PTR(aggrToPtr(operandType(IC_LEFT(dic)),FALSE)))
1842 /* if address of & the result is remat the okay */
1843 if (dic->op == ADDRESS_OF &&
1844 OP_SYMBOL(IC_RESULT(dic))->remat)
1847 /* if operand has size of three or more & this
1848 operation is a '*','/' or '%' then 'b' may
1850 if (( dic->op == '%' || dic->op == '/' || dic->op == '*') &&
1851 getSize(operandType(op)) >= 3)
1854 /* if left or right or result is in far space */
1855 if (isOperandInFarSpace(IC_LEFT(dic)) ||
1856 isOperandInFarSpace(IC_RIGHT(dic)) ||
1857 isOperandInFarSpace(IC_RESULT(dic)) ||
1858 IS_OP_RUONLY(IC_LEFT(dic)) ||
1859 IS_OP_RUONLY(IC_RIGHT(dic)) ||
1860 IS_OP_RUONLY(IC_RESULT(dic)) ) {
1865 OP_SYMBOL(op)->ruonly = 1;
1870 /*-----------------------------------------------------------------*/
1871 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1872 /*-----------------------------------------------------------------*/
1873 static bool isBitwiseOptimizable (iCode *ic)
1875 sym_link *ltype = getSpec(operandType(IC_LEFT(ic)));
1876 sym_link *rtype = getSpec(operandType(IC_RIGHT(ic)));
1878 /* bitwise operations are considered optimizable
1879 under the following conditions (Jean-Louis VERN)
1891 if ( IS_LITERAL(rtype) ||
1892 (IS_BITVAR(ltype) && IN_BITSPACE(SPEC_OCLS(ltype))))
1898 /*-----------------------------------------------------------------*/
1899 /* packRegsForAccUse - pack registers for acc use */
1900 /*-----------------------------------------------------------------*/
1901 static void packRegsForAccUse (iCode *ic)
1905 /* if + or - then it has to be one byte result */
1906 if ((ic->op == '+' || ic->op == '-')
1907 && getSize(operandType(IC_RESULT(ic))) > 1)
1910 /* if shift operation make sure right side is not a literal */
1911 if (ic->op == RIGHT_OP &&
1912 ( isOperandLiteral(IC_RIGHT(ic)) ||
1913 getSize(operandType(IC_RESULT(ic))) > 1))
1916 if (ic->op == LEFT_OP &&
1917 ( isOperandLiteral(IC_RIGHT(ic)) ||
1918 getSize(operandType(IC_RESULT(ic))) > 1))
1921 if (IS_BITWISE_OP(ic) &&
1922 getSize(operandType(IC_RESULT(ic))) > 1)
1926 /* has only one definition */
1927 if (bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1)
1930 /* has only one use */
1931 if (bitVectnBitsOn(OP_USES(IC_RESULT(ic))) > 1)
1934 /* and the usage immediately follows this iCode */
1935 if (!(uic = hTabItemWithKey(iCodehTab,
1936 bitVectFirstBit(OP_USES(IC_RESULT(ic))))))
1939 if (ic->next != uic)
1942 /* if it is a conditional branch then we definitely can */
1943 if (uic->op == IFX )
1946 if ( uic->op == JUMPTABLE )
1949 /* if the usage is not is an assignment
1950 or an arithmetic / bitwise / shift operation then not */
1951 if (POINTER_SET(uic) &&
1952 getSize(aggrToPtr(operandType(IC_RESULT(uic)),FALSE)) > 1)
1955 if (uic->op != '=' &&
1956 !IS_ARITHMETIC_OP(uic) &&
1957 !IS_BITWISE_OP(uic) &&
1958 uic->op != LEFT_OP &&
1959 uic->op != RIGHT_OP )
1962 /* if used in ^ operation then make sure right is not a
1964 if (uic->op == '^' && isOperandLiteral(IC_RIGHT(uic)))
1967 /* if shift operation make sure right side is not a literal */
1968 if (uic->op == RIGHT_OP &&
1969 ( isOperandLiteral(IC_RIGHT(uic)) ||
1970 getSize(operandType(IC_RESULT(uic))) > 1))
1973 if (uic->op == LEFT_OP &&
1974 ( isOperandLiteral(IC_RIGHT(uic)) ||
1975 getSize(operandType(IC_RESULT(uic))) > 1))
1978 /* make sure that the result of this icode is not on the
1979 stack, since acc is used to compute stack offset */
1980 if (IS_TRUE_SYMOP(IC_RESULT(uic)) &&
1981 OP_SYMBOL(IC_RESULT(uic))->onStack)
1984 /* if either one of them in far space then we cannot */
1985 if ((IS_TRUE_SYMOP(IC_LEFT(uic)) &&
1986 isOperandInFarSpace(IC_LEFT(uic))) ||
1987 (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
1988 isOperandInFarSpace(IC_RIGHT(uic))))
1991 /* if the usage has only one operand then we can */
1992 if (IC_LEFT(uic) == NULL ||
1993 IC_RIGHT(uic) == NULL)
1996 /* make sure this is on the left side if not
1997 a '+' since '+' is commutative */
1998 if (ic->op != '+' &&
1999 IC_LEFT(uic)->key != IC_RESULT(ic)->key)
2002 /* if one of them is a literal then we can */
2003 if ((IC_LEFT(uic) && IS_OP_LITERAL(IC_LEFT(uic))) ||
2004 (IC_RIGHT(uic) && IS_OP_LITERAL(IC_RIGHT(uic)))) {
2005 OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
2009 /* if the other one is not on stack then we can */
2010 if (IC_LEFT(uic)->key == IC_RESULT(ic)->key &&
2011 (IS_ITEMP(IC_RIGHT(uic)) ||
2012 (IS_TRUE_SYMOP(IC_RIGHT(uic)) &&
2013 !OP_SYMBOL(IC_RIGHT(uic))->onStack)))
2016 if (IC_RIGHT(uic)->key == IC_RESULT(ic)->key &&
2017 (IS_ITEMP(IC_LEFT(uic)) ||
2018 (IS_TRUE_SYMOP(IC_LEFT(uic)) &&
2019 !OP_SYMBOL(IC_LEFT(uic))->onStack)))
2025 OP_SYMBOL(IC_RESULT(ic))->accuse = 1;
2030 /*-----------------------------------------------------------------*/
2031 /* packForPush - hueristics to reduce iCode for pushing */
2032 /*-----------------------------------------------------------------*/
2033 static void packForPush(iCode *ic, eBBlock *ebp)
2037 if (ic->op != IPUSH || !IS_ITEMP(IC_LEFT(ic)))
2040 /* must have only definition & one usage */
2041 if (bitVectnBitsOn(OP_DEFS(IC_LEFT(ic))) != 1 ||
2042 bitVectnBitsOn(OP_USES(IC_LEFT(ic))) != 1 )
2045 /* find the definition */
2046 if (!(dic = hTabItemWithKey(iCodehTab,
2047 bitVectFirstBit(OP_DEFS(IC_LEFT(ic))))))
2050 if (dic->op != '=' || POINTER_SET(dic))
2053 /* we now we know that it has one & only one def & use
2054 and the that the definition is an assignment */
2055 IC_LEFT(ic) = IC_RIGHT(dic);
2057 remiCodeFromeBBlock(ebp,dic);
2058 hTabDeleteItem (&iCodehTab,dic->key,dic,DELETE_ITEM,NULL);
2061 /*-----------------------------------------------------------------*/
2062 /* packRegisters - does some transformations to reduce register */
2064 /*-----------------------------------------------------------------*/
2065 static void packRegisters (eBBlock *ebp)
2074 /* look for assignments of the form */
2075 /* iTempNN = TRueSym (someoperation) SomeOperand */
2077 /* TrueSym := iTempNN:1 */
2078 for ( ic = ebp->sch ; ic ; ic = ic->next ) {
2081 /* find assignment of the form TrueSym := iTempNN:1 */
2082 if (ic->op == '=' && !POINTER_SET(ic))
2083 change += packRegsForAssign(ic,ebp);
2090 for ( ic = ebp->sch ; ic ; ic = ic->next ) {
2092 /* if this is an itemp & result of a address of a true sym
2093 then mark this as rematerialisable */
2094 if (ic->op == ADDRESS_OF &&
2095 IS_ITEMP(IC_RESULT(ic)) &&
2096 IS_TRUE_SYMOP(IC_LEFT(ic)) &&
2097 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2098 !OP_SYMBOL(IC_LEFT(ic))->onStack ) {
2100 OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2101 OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2102 OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2106 /* if straight assignment then carry remat flag if
2107 this is the only definition */
2108 if (ic->op == '=' &&
2110 IS_SYMOP(IC_RIGHT(ic)) &&
2111 OP_SYMBOL(IC_RIGHT(ic))->remat &&
2112 bitVectnBitsOn(OP_SYMBOL(IC_RESULT(ic))->defs) <= 1) {
2114 OP_SYMBOL(IC_RESULT(ic))->remat =
2115 OP_SYMBOL(IC_RIGHT(ic))->remat;
2116 OP_SYMBOL(IC_RESULT(ic))->rematiCode =
2117 OP_SYMBOL(IC_RIGHT(ic))->rematiCode ;
2120 /* if this is a +/- operation with a rematerizable
2121 then mark this as rematerializable as well */
2122 if ((ic->op == '+' || ic->op == '-') &&
2123 (IS_SYMOP(IC_LEFT(ic)) &&
2124 IS_ITEMP(IC_RESULT(ic)) &&
2125 OP_SYMBOL(IC_LEFT(ic))->remat &&
2126 bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) == 1 &&
2127 IS_OP_LITERAL(IC_RIGHT(ic))) ) {
2130 operandLitValue(IC_RIGHT(ic));
2131 OP_SYMBOL(IC_RESULT(ic))->remat = 1;
2132 OP_SYMBOL(IC_RESULT(ic))->rematiCode = ic;
2133 OP_SYMBOL(IC_RESULT(ic))->usl.spillLoc = NULL;
2136 /* mark the pointer usages */
2137 if (POINTER_SET(ic))
2138 OP_SYMBOL(IC_RESULT(ic))->uptr = 1;
2140 if (POINTER_GET(ic))
2141 OP_SYMBOL(IC_LEFT(ic))->uptr = 1;
2143 if (!SKIP_IC2(ic)) {
2144 /* if we are using a symbol on the stack
2145 then we should say pic14_ptrRegReq */
2146 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
2147 pic14_ptrRegReq += ((OP_SYMBOL(IC_COND(ic))->onStack ||
2148 OP_SYMBOL(IC_COND(ic))->iaccess) ? 1 : 0);
2150 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
2151 pic14_ptrRegReq += ((OP_SYMBOL(IC_JTCOND(ic))->onStack ||
2152 OP_SYMBOL(IC_JTCOND(ic))->iaccess) ? 1 : 0);
2154 if (IS_SYMOP(IC_LEFT(ic)))
2155 pic14_ptrRegReq += ((OP_SYMBOL(IC_LEFT(ic))->onStack ||
2156 OP_SYMBOL(IC_LEFT(ic))->iaccess) ? 1 : 0);
2157 if (IS_SYMOP(IC_RIGHT(ic)))
2158 pic14_ptrRegReq += ((OP_SYMBOL(IC_RIGHT(ic))->onStack ||
2159 OP_SYMBOL(IC_RIGHT(ic))->iaccess) ? 1 : 0);
2160 if (IS_SYMOP(IC_RESULT(ic)))
2161 pic14_ptrRegReq += ((OP_SYMBOL(IC_RESULT(ic))->onStack ||
2162 OP_SYMBOL(IC_RESULT(ic))->iaccess) ? 1 : 0);
2166 /* if the condition of an if instruction
2167 is defined in the previous instruction then
2168 mark the itemp as a conditional */
2169 if ((IS_CONDITIONAL(ic) ||
2170 ( ( ic->op == BITWISEAND ||
2173 isBitwiseOptimizable(ic))) &&
2174 ic->next && ic->next->op == IFX &&
2175 isOperandEqual(IC_RESULT(ic),IC_COND(ic->next)) &&
2176 OP_SYMBOL(IC_RESULT(ic))->liveTo <= ic->next->seq) {
2178 OP_SYMBOL(IC_RESULT(ic))->regType = REG_CND;
2182 /* reduce for support function calls */
2183 if (ic->supportRtn || ic->op == '+' || ic->op == '-' )
2184 packRegsForSupport (ic,ebp);
2186 /* some cases the redundant moves can
2187 can be eliminated for return statements */
2188 if ((ic->op == RETURN || ic->op == SEND) &&
2189 !isOperandInFarSpace(IC_LEFT(ic)) &&
2191 packRegsForOneuse (ic,IC_LEFT(ic),ebp);
2193 /* if pointer set & left has a size more than
2194 one and right is not in far space */
2195 if (POINTER_SET(ic) &&
2196 !isOperandInFarSpace(IC_RIGHT(ic)) &&
2197 !OP_SYMBOL(IC_RESULT(ic))->remat &&
2198 !IS_OP_RUONLY(IC_RIGHT(ic)) &&
2199 getSize(aggrToPtr(operandType(IC_RESULT(ic)),FALSE)) > 1 )
2201 packRegsForOneuse (ic,IC_RESULT(ic),ebp);
2203 /* if pointer get */
2204 if (POINTER_GET(ic) &&
2205 !isOperandInFarSpace(IC_RESULT(ic))&&
2206 !OP_SYMBOL(IC_LEFT(ic))->remat &&
2207 !IS_OP_RUONLY(IC_RESULT(ic)) &&
2208 getSize(aggrToPtr(operandType(IC_LEFT(ic)),FALSE)) > 1 )
2210 packRegsForOneuse (ic,IC_LEFT(ic),ebp);
2213 /* if this is cast for intergral promotion then
2214 check if only use of the definition of the
2215 operand being casted/ if yes then replace
2216 the result of that arithmetic operation with
2217 this result and get rid of the cast */
2218 if (ic->op == CAST) {
2219 sym_link *fromType = operandType(IC_RIGHT(ic));
2220 sym_link *toType = operandType(IC_LEFT(ic));
2222 if (IS_INTEGRAL(fromType) && IS_INTEGRAL(toType) &&
2223 getSize(fromType) != getSize(toType) ) {
2225 iCode *dic = packRegsForOneuse(ic,IC_RIGHT(ic),ebp);
2227 if (IS_ARITHMETIC_OP(dic)) {
2228 IC_RESULT(dic) = IC_RESULT(ic);
2229 remiCodeFromeBBlock(ebp,ic);
2230 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2231 OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
2234 OP_SYMBOL(IC_RIGHT(ic))->ruonly = 0;
2238 /* if the type from and type to are the same
2239 then if this is the only use then packit */
2240 if (checkType(operandType(IC_RIGHT(ic)),
2241 operandType(IC_LEFT(ic))) == 1) {
2242 iCode *dic = packRegsForOneuse (ic,IC_RIGHT(ic),ebp);
2244 IC_RESULT(dic) = IC_RESULT(ic);
2245 remiCodeFromeBBlock(ebp,ic);
2246 hTabDeleteItem (&iCodehTab,ic->key,ic,DELETE_ITEM,NULL);
2247 OP_DEFS(IC_RESULT(dic)) = bitVectSetBit(OP_DEFS(IC_RESULT(dic)),dic->key);
2255 iTempNN := (some variable in farspace) V1
2260 if (ic->op == IPUSH ) {
2261 packForPush(ic,ebp);
2265 /* pack registers for accumulator use, when the
2266 result of an arithmetic or bit wise operation
2267 has only one use, that use is immediately following
2268 the defintion and the using iCode has only one
2269 operand or has two operands but one is literal &
2270 the result of that operation is not on stack then
2271 we can leave the result of this operation in acc:b
2273 if ((IS_ARITHMETIC_OP(ic)
2275 || IS_BITWISE_OP(ic)
2277 || ic->op == LEFT_OP || ic->op == RIGHT_OP
2280 IS_ITEMP(IC_RESULT(ic)) &&
2281 getSize(operandType(IC_RESULT(ic))) <= 2)
2283 packRegsForAccUse (ic);
2288 /*-----------------------------------------------------------------*/
2289 /* assignRegisters - assigns registers to each live range as need */
2290 /*-----------------------------------------------------------------*/
2291 void pic14_assignRegisters (eBBlock **ebbs, int count)
2296 fprintf(stderr,"%s:%s",__FILE__,__FUNCTION__);
2298 setToNull((void *)&_G.funcrUsed);
2299 pic14_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2302 /* change assignments this will remove some
2303 live ranges reducing some register pressure */
2304 for (i = 0 ; i < count ;i++ )
2305 packRegisters (ebbs[i]);
2307 if (options.dump_pack)
2308 dumpEbbsToFileExt(".dumppack",ebbs,count);
2310 /* first determine for each live range the number of
2311 registers & the type of registers required for each */
2314 /* and serially allocate registers */
2315 serialRegAssign(ebbs,count);
2317 /* if stack was extended then tell the user */
2318 if (_G.stackExtend) {
2319 /* werror(W_TOOMANY_SPILS,"stack", */
2320 /* _G.stackExtend,currFunc->name,""); */
2321 _G.stackExtend = 0 ;
2324 if (_G.dataExtend) {
2325 /* werror(W_TOOMANY_SPILS,"data space", */
2326 /* _G.dataExtend,currFunc->name,""); */
2330 /* after that create the register mask
2331 for each of the instruction */
2332 createRegMask (ebbs,count);
2334 /* redo that offsets for stacked automatic variables */
2335 redoStackOffsets ();
2337 if (options.dump_rassgn)
2338 dumpEbbsToFileExt(".dumprassgn",ebbs,count);
2340 /* now get back the chain */
2341 ic = iCodeLabelOptimize(iCodeFromeBBlock (ebbs,count));
2346 /* free up any _G.stackSpil locations allocated */
2347 applyToSet(_G.stackSpil,deallocStackSpil);
2349 setToNull((void **)&_G.stackSpil);
2350 setToNull((void **)&_G.spiltSet);
2351 /* mark all registers as free */