1 /*------------------------------------------------------------------------
3 SDCCralloc.c - source file for register allocation. (8051) specific
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
7 This program is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 In other words, you are welcome to use, share and improve this program.
22 You are forbidden to forbid anyone else to use, share and improve
23 what you give them. Help stamp out software-hoarding!
24 -------------------------------------------------------------------------*/
30 /*-----------------------------------------------------------------*/
31 /* At this point we start getting processor specific although */
32 /* some routines are non-processor specific & can be reused when */
33 /* targetting other processors. The decision for this will have */
34 /* to be made on a routine by routine basis */
35 /* routines used to pack registers are most definitely not reusable */
36 /* since the pack the registers depending strictly on the MCU */
37 /*-----------------------------------------------------------------*/
47 bitVect *funcrUsed; /* registers used in a function */
53 /* Shared with gen.c */
54 int ds390_ptrRegReq; /* one byte pointer register required */
60 {REG_GPR, R2_IDX, REG_GPR, "r2", "ar2", "0", 2, 1},
61 {REG_GPR, R3_IDX, REG_GPR, "r3", "ar3", "0", 3, 1},
62 {REG_GPR, R4_IDX, REG_GPR, "r4", "ar4", "0", 4, 1},
63 {REG_GPR, R5_IDX, REG_GPR, "r5", "ar5", "0", 5, 1},
64 {REG_GPR, R6_IDX, REG_GPR, "r6", "ar6", "0", 6, 1},
65 {REG_GPR, R7_IDX, REG_GPR, "r7", "ar7", "0", 7, 1},
66 {REG_PTR, R0_IDX, REG_PTR, "r0", "ar0", "0", 0, 1},
67 {REG_PTR, R1_IDX, REG_PTR, "r1", "ar1", "0", 1, 1},
68 {REG_GPR, X8_IDX, REG_GPR, "x8", "x8", "xreg", 0, 0},
69 {REG_GPR, X9_IDX, REG_GPR, "x9", "x9", "xreg", 1, 0},
70 {REG_GPR, X10_IDX, REG_GPR, "x10", "x10", "xreg", 2, 0},
71 {REG_GPR, X11_IDX, REG_GPR, "x11", "x11", "xreg", 3, 0},
72 {REG_GPR, X12_IDX, REG_GPR, "x12", "x12", "xreg", 4, 0},
73 {REG_CND, CND_IDX, REG_GPR, "C", "C", "xreg", 0, 0},
74 {REG_GPR, DPL_IDX, REG_GPR, "dpl", "dpl", "dpl", 0, 0},
75 {REG_GPR, DPH_IDX, REG_GPR, "dph", "dph", "dph", 0, 0},
76 {REG_GPR, DPX_IDX, REG_GPR, "dpx", "dpx", "dpx", 0, 0},
77 {REG_GPR, B_IDX, REG_GPR, "b", "b", "b", 0, 0},
80 static void spillThis (symbol *);
82 /*-----------------------------------------------------------------*/
83 /* allocReg - allocates register of given type */
84 /*-----------------------------------------------------------------*/
90 for (i = 0; i < ds390_nRegs; i++)
93 /* if type is given as 0 then any
94 free register will do */
98 regs390[i].isFree = 0;
101 bitVectSetBit (currFunc->regsUsed, i);
104 /* other wise look for specific type
106 if (regs390[i].isFree &&
107 regs390[i].type == type)
109 regs390[i].isFree = 0;
112 bitVectSetBit (currFunc->regsUsed, i);
119 /*-----------------------------------------------------------------*/
120 /* ds390_regWithIdx - returns pointer to register wit index number */
121 /*-----------------------------------------------------------------*/
123 ds390_regWithIdx (int idx)
127 for (i = 0; i < ds390_nRegs; i++)
128 if (regs390[i].rIdx == idx)
131 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
132 "regWithIdx not found");
136 /*-----------------------------------------------------------------*/
137 /* freeReg - frees a register */
138 /*-----------------------------------------------------------------*/
146 /*-----------------------------------------------------------------*/
147 /* nFreeRegs - returns number of free registers */
148 /*-----------------------------------------------------------------*/
155 for (i = 0; i < ds390_nRegs; i++)
156 if (regs390[i].isFree && regs390[i].type == type)
161 /*-----------------------------------------------------------------*/
162 /* nfreeRegsType - free registers with type */
163 /*-----------------------------------------------------------------*/
165 nfreeRegsType (int type)
170 if ((nfr = nFreeRegs (type)) == 0)
171 return nFreeRegs (REG_GPR);
174 return nFreeRegs (type);
178 /*-----------------------------------------------------------------*/
179 /* allDefsOutOfRange - all definitions are out of a range */
180 /*-----------------------------------------------------------------*/
182 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
189 for (i = 0; i < defs->size; i++)
193 if (bitVectBitValue (defs, i) &&
194 (ic = hTabItemWithKey (iCodehTab, i)) &&
195 (ic->seq >= fseq && ic->seq <= toseq))
204 /*-----------------------------------------------------------------*/
205 /* computeSpillable - given a point find the spillable live ranges */
206 /*-----------------------------------------------------------------*/
208 computeSpillable (iCode * ic)
212 /* spillable live ranges are those that are live at this
213 point . the following categories need to be subtracted
215 a) - those that are already spilt
216 b) - if being used by this one
217 c) - defined by this one */
219 spillable = bitVectCopy (ic->rlive);
221 bitVectCplAnd (spillable, _G.spiltSet); /* those already spilt */
223 bitVectCplAnd (spillable, ic->uses); /* used in this one */
224 bitVectUnSetBit (spillable, ic->defKey);
225 spillable = bitVectIntersect (spillable, _G.regAssigned);
230 /*-----------------------------------------------------------------*/
231 /* noSpilLoc - return true if a variable has no spil location */
232 /*-----------------------------------------------------------------*/
234 noSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
236 return (sym->usl.spillLoc ? 0 : 1);
239 /*-----------------------------------------------------------------*/
240 /* hasSpilLoc - will return 1 if the symbol has spil location */
241 /*-----------------------------------------------------------------*/
243 hasSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
245 return (sym->usl.spillLoc ? 1 : 0);
248 /*-----------------------------------------------------------------*/
249 /* directSpilLoc - will return 1 if the splilocation is in direct */
250 /*-----------------------------------------------------------------*/
252 directSpilLoc (symbol * sym, eBBlock * ebp, iCode * ic)
254 if (sym->usl.spillLoc &&
255 (IN_DIRSPACE (SPEC_OCLS (sym->usl.spillLoc->etype))))
261 /*-----------------------------------------------------------------*/
262 /* hasSpilLocnoUptr - will return 1 if the symbol has spil location */
263 /* but is not used as a pointer */
264 /*-----------------------------------------------------------------*/
266 hasSpilLocnoUptr (symbol * sym, eBBlock * ebp, iCode * ic)
268 return ((sym->usl.spillLoc && !sym->uptr) ? 1 : 0);
271 /*-----------------------------------------------------------------*/
272 /* rematable - will return 1 if the remat flag is set */
273 /*-----------------------------------------------------------------*/
275 rematable (symbol * sym, eBBlock * ebp, iCode * ic)
280 /*-----------------------------------------------------------------*/
281 /* notUsedInBlock - not used in this block */
282 /*-----------------------------------------------------------------*/
284 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode * ic)
286 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
287 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq));
288 /* return (!bitVectBitsInCommon(sym->defs,ebp->usesDefs)); */
291 /*-----------------------------------------------------------------*/
292 /* notUsedInRemaining - not used or defined in remain of the block */
293 /*-----------------------------------------------------------------*/
295 notUsedInRemaining (symbol * sym, eBBlock * ebp, iCode * ic)
297 return ((usedInRemaining (operandFromSymbol (sym), ic) ? 0 : 1) &&
298 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq));
301 /*-----------------------------------------------------------------*/
302 /* allLRs - return true for all */
303 /*-----------------------------------------------------------------*/
305 allLRs (symbol * sym, eBBlock * ebp, iCode * ic)
310 /*-----------------------------------------------------------------*/
311 /* liveRangesWith - applies function to a given set of live range */
312 /*-----------------------------------------------------------------*/
314 liveRangesWith (bitVect * lrs, int (func) (symbol *, eBBlock *, iCode *),
315 eBBlock * ebp, iCode * ic)
320 if (!lrs || !lrs->size)
323 for (i = 1; i < lrs->size; i++)
326 if (!bitVectBitValue (lrs, i))
329 /* if we don't find it in the live range
330 hash table we are in serious trouble */
331 if (!(sym = hTabItemWithKey (liveRanges, i)))
333 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
334 "liveRangesWith could not find liveRange");
338 if (func (sym, ebp, ic) && bitVectBitValue (_G.regAssigned, sym->key))
339 addSetHead (&rset, sym);
346 /*-----------------------------------------------------------------*/
347 /* leastUsedLR - given a set determines which is the least used */
348 /*-----------------------------------------------------------------*/
350 leastUsedLR (set * sset)
352 symbol *sym = NULL, *lsym = NULL;
354 sym = lsym = setFirstItem (sset);
359 for (; lsym; lsym = setNextItem (sset))
362 /* if usage is the same then prefer
363 the spill the smaller of the two */
364 if (lsym->used == sym->used)
365 if (getSize (lsym->type) < getSize (sym->type))
369 if (lsym->used < sym->used)
374 setToNull ((void **) &sset);
379 /*-----------------------------------------------------------------*/
380 /* noOverLap - will iterate through the list looking for over lap */
381 /*-----------------------------------------------------------------*/
383 noOverLap (set * itmpStack, symbol * fsym)
387 for (sym = setFirstItem (itmpStack); sym;
388 sym = setNextItem (itmpStack))
390 if (bitVectBitValue(sym->clashes,fsym->key)) return 0;
395 /*-----------------------------------------------------------------*/
396 /* isFree - will return 1 if the a free spil location is found */
397 /*-----------------------------------------------------------------*/
402 V_ARG (symbol **, sloc);
403 V_ARG (symbol *, fsym);
405 /* if already found */
409 /* if it is free && and the itmp assigned to
410 this does not have any overlapping live ranges
411 with the one currently being assigned and
412 the size can be accomodated */
414 noOverLap (sym->usl.itmpStack, fsym) &&
415 getSize (sym->type) >= getSize (fsym->type))
424 /*-----------------------------------------------------------------*/
425 /* spillLRWithPtrReg :- will spil those live ranges which use PTR */
426 /*-----------------------------------------------------------------*/
428 spillLRWithPtrReg (symbol * forSym)
434 if (!_G.regAssigned ||
435 bitVectIsZero (_G.regAssigned))
438 r0 = ds390_regWithIdx (R0_IDX);
439 r1 = ds390_regWithIdx (R1_IDX);
441 /* for all live ranges */
442 for (lrsym = hTabFirstItem (liveRanges, &k); lrsym;
443 lrsym = hTabNextItem (liveRanges, &k))
447 /* if no registers assigned to it or
449 /* if it does not overlap with this then
450 not need to spill it */
452 if (lrsym->isspilt || !lrsym->nRegs ||
453 (lrsym->liveTo < forSym->liveFrom))
456 /* go thru the registers : if it is either
457 r0 or r1 then spil it */
458 for (j = 0; j < lrsym->nRegs; j++)
459 if (lrsym->regs[j] == r0 ||
460 lrsym->regs[j] == r1)
469 /*-----------------------------------------------------------------*/
470 /* createStackSpil - create a location on the stack to spil */
471 /*-----------------------------------------------------------------*/
473 createStackSpil (symbol * sym)
476 int useXstack, model, noOverlay;
480 /* first go try and find a free one that is already
481 existing on the stack */
482 if (applyToSet (_G.stackSpil, isFree, &sloc, sym))
484 /* found a free one : just update & return */
485 sym->usl.spillLoc = sloc;
488 addSetHead (&sloc->usl.itmpStack, sym);
492 /* could not then have to create one , this is the hard part
493 we need to allocate this on the stack : this is really a
494 hack!! but cannot think of anything better at this time */
496 if (sprintf (slocBuffer, "sloc%d", _G.slocNum++) >= sizeof (slocBuffer))
498 fprintf (stderr, "***Internal error: slocBuffer overflowed: %s:%d\n",
503 sloc = newiTemp (slocBuffer);
505 /* set the type to the spilling symbol */
506 sloc->type = copyLinkChain (sym->type);
507 sloc->etype = getSpec (sloc->type);
508 if (options.model == MODEL_SMALL) {
509 SPEC_SCLS (sloc->etype) = S_DATA;
511 SPEC_SCLS (sloc->etype) = S_XDATA;
513 SPEC_EXTR (sloc->etype) = 0;
515 /* we don't allow it to be allocated`
516 onto the external stack since : so we
517 temporarily turn it off ; we also
518 turn off memory model to prevent
519 the spil from going to the external storage
520 and turn off overlaying
523 useXstack = options.useXstack;
524 model = options.model;
525 noOverlay = options.noOverlay;
526 options.noOverlay = 1;
528 /* options.model = options.useXstack = 0; */
532 options.useXstack = useXstack;
533 options.model = model;
534 options.noOverlay = noOverlay;
535 sloc->isref = 1; /* to prevent compiler warning */
537 /* if it is on the stack then update the stack */
538 if (IN_STACK (sloc->etype))
540 currFunc->stack += getSize (sloc->type);
541 _G.stackExtend += getSize (sloc->type);
544 _G.dataExtend += getSize (sloc->type);
546 /* add it to the _G.stackSpil set */
547 addSetHead (&_G.stackSpil, sloc);
548 sym->usl.spillLoc = sloc;
551 /* add it to the set of itempStack set
552 of the spill location */
553 addSetHead (&sloc->usl.itmpStack, sym);
557 /*-----------------------------------------------------------------*/
558 /* isSpiltOnStack - returns true if the spil location is on stack */
559 /*-----------------------------------------------------------------*/
561 isSpiltOnStack (symbol * sym)
571 /* if (sym->_G.stackSpil) */
574 if (!sym->usl.spillLoc)
577 etype = getSpec (sym->usl.spillLoc->type);
578 if (IN_STACK (etype))
584 /*-----------------------------------------------------------------*/
585 /* spillThis - spils a specific operand */
586 /*-----------------------------------------------------------------*/
588 spillThis (symbol * sym)
591 /* if this is rematerializable or has a spillLocation
592 we are okay, else we need to create a spillLocation
594 if (!(sym->remat || sym->usl.spillLoc))
595 createStackSpil (sym);
598 /* mark it has spilt & put it in the spilt set */
600 _G.spiltSet = bitVectSetBit (_G.spiltSet, sym->key);
602 bitVectUnSetBit (_G.regAssigned, sym->key);
604 for (i = 0; i < sym->nRegs; i++)
608 freeReg (sym->regs[i]);
612 /* if spilt on stack then free up r0 & r1
613 if they could have been assigned to some
615 if (!ds390_ptrRegReq && isSpiltOnStack (sym))
617 ds390_ptrRegReq += !options.stack10bit;
618 spillLRWithPtrReg (sym);
621 if (sym->usl.spillLoc && !sym->remat)
622 sym->usl.spillLoc->allocreq = 1;
626 /*-----------------------------------------------------------------*/
627 /* selectSpil - select a iTemp to spil : rather a simple procedure */
628 /*-----------------------------------------------------------------*/
630 selectSpil (iCode * ic, eBBlock * ebp, symbol * forSym)
632 bitVect *lrcs = NULL;
636 /* get the spillable live ranges */
637 lrcs = computeSpillable (ic);
639 /* get all live ranges that are rematerizable */
640 if ((selectS = liveRangesWith (lrcs, rematable, ebp, ic)))
643 /* return the least used of these */
644 return leastUsedLR (selectS);
647 /* get live ranges with spillLocations in direct space */
648 if ((selectS = liveRangesWith (lrcs, directSpilLoc, ebp, ic)))
650 sym = leastUsedLR (selectS);
651 strcpy (sym->rname, (sym->usl.spillLoc->rname[0] ?
652 sym->usl.spillLoc->rname :
653 sym->usl.spillLoc->name));
655 /* mark it as allocation required */
656 sym->usl.spillLoc->allocreq = 1;
660 /* if the symbol is local to the block then */
661 if (forSym->liveTo < ebp->lSeq)
664 /* check if there are any live ranges allocated
665 to registers that are not used in this block */
666 if (!_G.blockSpil && (selectS = liveRangesWith (lrcs, notUsedInBlock, ebp, ic)))
668 sym = leastUsedLR (selectS);
669 /* if this is not rematerializable */
678 /* check if there are any live ranges that not
679 used in the remainder of the block */
680 if (!_G.blockSpil && (selectS = liveRangesWith (lrcs, notUsedInRemaining, ebp, ic)))
682 sym = leastUsedLR (selectS);
695 /* find live ranges with spillocation && not used as pointers */
696 if ((selectS = liveRangesWith (lrcs, hasSpilLocnoUptr, ebp, ic)))
699 sym = leastUsedLR (selectS);
700 /* mark this as allocation required */
701 sym->usl.spillLoc->allocreq = 1;
705 /* find live ranges with spillocation */
706 if ((selectS = liveRangesWith (lrcs, hasSpilLoc, ebp, ic)))
709 sym = leastUsedLR (selectS);
710 sym->usl.spillLoc->allocreq = 1;
714 /* couldn't find then we need to create a spil
715 location on the stack , for which one? the least
717 if ((selectS = liveRangesWith (lrcs, noSpilLoc, ebp, ic)))
720 /* return a created spil location */
721 sym = createStackSpil (leastUsedLR (selectS));
722 sym->usl.spillLoc->allocreq = 1;
726 /* this is an extreme situation we will spill
727 this one : happens very rarely but it does happen */
733 /*-----------------------------------------------------------------*/
734 /* spilSomething - spil some variable & mark registers as free */
735 /*-----------------------------------------------------------------*/
737 spilSomething (iCode * ic, eBBlock * ebp, symbol * forSym)
742 /* get something we can spil */
743 ssym = selectSpil (ic, ebp, forSym);
745 /* mark it as spilt */
747 _G.spiltSet = bitVectSetBit (_G.spiltSet, ssym->key);
749 /* mark it as not register assigned &
750 take it away from the set */
751 bitVectUnSetBit (_G.regAssigned, ssym->key);
753 /* mark the registers as free */
754 for (i = 0; i < ssym->nRegs; i++)
756 freeReg (ssym->regs[i]);
758 /* if spilt on stack then free up r0 & r1
759 if they could have been assigned to as gprs */
760 if (!ds390_ptrRegReq && isSpiltOnStack (ssym) && !options.stack10bit)
763 spillLRWithPtrReg (ssym);
766 /* if this was a block level spil then insert push & pop
767 at the start & end of block respectively */
770 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
771 /* add push to the start of the block */
772 addiCodeToeBBlock (ebp, nic, (ebp->sch->op == LABEL ?
773 ebp->sch->next : ebp->sch));
774 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
775 /* add pop to the end of the block */
776 addiCodeToeBBlock (ebp, nic, NULL);
779 /* if spilt because not used in the remainder of the
780 block then add a push before this instruction and
781 a pop at the end of the block */
782 if (ssym->remainSpil)
785 iCode *nic = newiCode (IPUSH, operandFromSymbol (ssym), NULL);
786 /* add push just before this instruction */
787 addiCodeToeBBlock (ebp, nic, ic);
789 nic = newiCode (IPOP, operandFromSymbol (ssym), NULL);
790 /* add pop to the end of the block */
791 addiCodeToeBBlock (ebp, nic, NULL);
800 /*-----------------------------------------------------------------*/
801 /* getRegPtr - will try for PTR if not a GPR type if not spil */
802 /*-----------------------------------------------------------------*/
804 getRegPtr (iCode * ic, eBBlock * ebp, symbol * sym)
809 /* try for a ptr type */
810 if ((reg = allocReg (REG_PTR)))
813 /* try for gpr type */
814 if ((reg = allocReg (REG_GPR)))
817 /* we have to spil */
818 if (!spilSomething (ic, ebp, sym))
821 /* this looks like an infinite loop but
822 in really selectSpil will abort */
826 /*-----------------------------------------------------------------*/
827 /* getRegGpr - will try for GPR if not spil */
828 /*-----------------------------------------------------------------*/
830 getRegGpr (iCode * ic, eBBlock * ebp, symbol * sym)
835 /* try for gpr type */
836 if ((reg = allocReg (REG_GPR)))
839 if (!ds390_ptrRegReq)
840 if ((reg = allocReg (REG_PTR)))
843 /* we have to spil */
844 if (!spilSomething (ic, ebp, sym))
847 /* this looks like an infinite loop but
848 in really selectSpil will abort */
852 /*-----------------------------------------------------------------*/
853 /* symHasReg - symbol has a given register */
854 /*-----------------------------------------------------------------*/
856 symHasReg (symbol * sym, regs * reg)
860 for (i = 0; i < sym->nRegs; i++)
861 if (sym->regs[i] == reg)
867 /*-----------------------------------------------------------------*/
868 /* deassignLRs - check the live to and if they have registers & are */
869 /* not spilt then free up the registers */
870 /*-----------------------------------------------------------------*/
872 deassignLRs (iCode * ic, eBBlock * ebp)
878 for (sym = hTabFirstItem (liveRanges, &k); sym;
879 sym = hTabNextItem (liveRanges, &k))
883 /* if it does not end here */
884 if (sym->liveTo > ic->seq)
887 /* if it was spilt on stack then we can
888 mark the stack spil location as free */
893 sym->usl.spillLoc->isFree = 1;
899 if (!bitVectBitValue (_G.regAssigned, sym->key))
902 /* special case check if this is an IFX &
903 the privious one was a pop and the
904 previous one was not spilt then keep track
906 if (ic->op == IFX && ic->prev &&
907 ic->prev->op == IPOP &&
908 !ic->prev->parmPush &&
909 !OP_SYMBOL (IC_LEFT (ic->prev))->isspilt)
910 psym = OP_SYMBOL (IC_LEFT (ic->prev));
916 bitVectUnSetBit (_G.regAssigned, sym->key);
918 /* if the result of this one needs registers
919 and does not have it then assign it right
921 if (IC_RESULT (ic) &&
922 !(SKIP_IC2 (ic) || /* not a special icode */
923 ic->op == JUMPTABLE ||
929 (result = OP_SYMBOL (IC_RESULT (ic))) && /* has a result */
930 result->liveTo > ic->seq && /* and will live beyond this */
931 result->liveTo <= ebp->lSeq && /* does not go beyond this block */
932 result->regType == sym->regType && /* same register types */
933 result->nRegs && /* which needs registers */
934 !result->isspilt && /* and does not already have them */
936 !bitVectBitValue (_G.regAssigned, result->key) &&
937 /* the number of free regs + number of regs in this LR
938 can accomodate the what result Needs */
939 ((nfreeRegsType (result->regType) +
940 sym->nRegs) >= result->nRegs)
944 for (i = 0; i < result->nRegs; i++)
946 result->regs[i] = sym->regs[i];
948 result->regs[i] = getRegGpr (ic, ebp, result);
950 _G.regAssigned = bitVectSetBit (_G.regAssigned, result->key);
954 /* free the remaining */
955 for (; i < sym->nRegs; i++)
959 if (!symHasReg (psym, sym->regs[i]))
960 freeReg (sym->regs[i]);
963 freeReg (sym->regs[i]);
970 /*-----------------------------------------------------------------*/
971 /* reassignLR - reassign this to registers */
972 /*-----------------------------------------------------------------*/
974 reassignLR (operand * op)
976 symbol *sym = OP_SYMBOL (op);
979 /* not spilt any more */
980 sym->isspilt = sym->blockSpil = sym->remainSpil = 0;
981 bitVectUnSetBit (_G.spiltSet, sym->key);
983 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
987 for (i = 0; i < sym->nRegs; i++)
988 sym->regs[i]->isFree = 0;
991 /*-----------------------------------------------------------------*/
992 /* willCauseSpill - determines if allocating will cause a spill */
993 /*-----------------------------------------------------------------*/
995 willCauseSpill (int nr, int rt)
997 /* first check if there are any avlb registers
998 of te type required */
1001 /* special case for pointer type
1002 if pointer type not avlb then
1003 check for type gpr */
1004 if (nFreeRegs (rt) >= nr)
1006 if (nFreeRegs (REG_GPR) >= nr)
1011 if (ds390_ptrRegReq)
1013 if (nFreeRegs (rt) >= nr)
1018 if (nFreeRegs (REG_PTR) +
1019 nFreeRegs (REG_GPR) >= nr)
1024 /* it will cause a spil */
1028 /*-----------------------------------------------------------------*/
1029 /* positionRegs - the allocator can allocate same registers to res- */
1030 /* ult and operand, if this happens make sure they are in the same */
1031 /* position as the operand otherwise chaos results */
1032 /*-----------------------------------------------------------------*/
1034 positionRegs (symbol * result, symbol * opsym, int lineno)
1036 int count = min (result->nRegs, opsym->nRegs);
1037 int i, j = 0, shared = 0;
1039 /* if the result has been spilt then cannot share */
1044 /* first make sure that they actually share */
1045 for (i = 0; i < count; i++)
1047 for (j = 0; j < count; j++)
1049 if (result->regs[i] == opsym->regs[j] && i != j)
1059 regs *tmp = result->regs[i];
1060 result->regs[i] = result->regs[j];
1061 result->regs[j] = tmp;
1066 /*-----------------------------------------------------------------*/
1067 /* serialRegAssign - serially allocate registers to the variables */
1068 /*-----------------------------------------------------------------*/
1070 serialRegAssign (eBBlock ** ebbs, int count)
1074 /* for all blocks */
1075 for (i = 0; i < count; i++)
1080 if (ebbs[i]->noPath &&
1081 (ebbs[i]->entryLabel != entryLabel &&
1082 ebbs[i]->entryLabel != returnLabel))
1085 /* of all instructions do */
1086 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1089 /* if this is an ipop that means some live
1090 range will have to be assigned again */
1092 reassignLR (IC_LEFT (ic));
1094 /* if result is present && is a true symbol */
1095 if (IC_RESULT (ic) && ic->op != IFX &&
1096 IS_TRUE_SYMOP (IC_RESULT (ic)))
1097 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
1099 /* take away registers from live
1100 ranges that end at this instruction */
1101 deassignLRs (ic, ebbs[i]);
1103 /* some don't need registers */
1104 if (SKIP_IC2 (ic) ||
1105 ic->op == JUMPTABLE ||
1109 (IC_RESULT (ic) && POINTER_SET (ic)))
1112 /* now we need to allocate registers
1113 only for the result */
1116 symbol *sym = OP_SYMBOL (IC_RESULT (ic));
1122 /* if it does not need or is spilt
1123 or is already assigned to registers
1124 or will not live beyond this instructions */
1127 bitVectBitValue (_G.regAssigned, sym->key) ||
1128 sym->liveTo <= ic->seq)
1131 /* if some liverange has been spilt at the block level
1132 and this one live beyond this block then spil this
1134 if (_G.blockSpil && sym->liveTo > ebbs[i]->lSeq)
1139 /* if trying to allocate this will cause
1140 a spill and there is nothing to spill
1141 or this one is rematerializable then
1143 willCS = willCauseSpill (sym->nRegs, sym->regType);
1144 spillable = computeSpillable (ic);
1146 (willCS && bitVectIsZero (spillable)))
1154 /* if it has a spillocation & is used less than
1155 all other live ranges then spill this */
1157 if (sym->usl.spillLoc) {
1158 symbol *leastUsed = leastUsedLR (liveRangesWith (spillable,
1159 allLRs, ebbs[i], ic));
1160 if (leastUsed && leastUsed->used > sym->used) {
1165 /* if none of the liveRanges have a spillLocation then better
1166 to spill this one than anything else already assigned to registers */
1167 if (liveRangesWith(spillable,noSpilLoc,ebbs[i],ic)) {
1174 /* if we need ptr regs for the right side
1176 if (POINTER_GET (ic) && IS_SYMOP (IC_LEFT (ic))
1177 && getSize (OP_SYMBOL (IC_LEFT (ic))->type)
1178 <= (unsigned) PTRSIZE)
1183 /* else we assign registers to it */
1184 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
1186 for (j = 0; j < sym->nRegs; j++)
1188 if (sym->regType == REG_PTR)
1189 sym->regs[j] = getRegPtr (ic, ebbs[i], sym);
1191 sym->regs[j] = getRegGpr (ic, ebbs[i], sym);
1193 /* if the allocation falied which means
1194 this was spilt then break */
1198 /* if it shares registers with operands make sure
1199 that they are in the same position */
1200 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)) &&
1201 OP_SYMBOL (IC_LEFT (ic))->nRegs && ic->op != '=')
1202 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1203 OP_SYMBOL (IC_LEFT (ic)), ic->lineno);
1204 /* do the same for the right operand */
1205 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)) &&
1206 OP_SYMBOL (IC_RIGHT (ic))->nRegs)
1207 positionRegs (OP_SYMBOL (IC_RESULT (ic)),
1208 OP_SYMBOL (IC_RIGHT (ic)), ic->lineno);
1221 /*-----------------------------------------------------------------*/
1222 /* rUmaskForOp :- returns register mask for an operand */
1223 /*-----------------------------------------------------------------*/
1225 rUmaskForOp (operand * op)
1231 /* only temporaries are assigned registers */
1235 sym = OP_SYMBOL (op);
1237 /* if spilt or no registers assigned to it
1239 if (sym->isspilt || !sym->nRegs)
1242 rumask = newBitVect (ds390_nRegs);
1244 for (j = 0; j < sym->nRegs; j++)
1246 rumask = bitVectSetBit (rumask,
1247 sym->regs[j]->rIdx);
1253 /*-----------------------------------------------------------------*/
1254 /* regsUsedIniCode :- returns bit vector of registers used in iCode */
1255 /*-----------------------------------------------------------------*/
1257 regsUsedIniCode (iCode * ic)
1259 bitVect *rmask = newBitVect (ds390_nRegs);
1261 /* do the special cases first */
1264 rmask = bitVectUnion (rmask,
1265 rUmaskForOp (IC_COND (ic)));
1269 /* for the jumptable */
1270 if (ic->op == JUMPTABLE)
1272 rmask = bitVectUnion (rmask,
1273 rUmaskForOp (IC_JTCOND (ic)));
1278 /* of all other cases */
1280 rmask = bitVectUnion (rmask,
1281 rUmaskForOp (IC_LEFT (ic)));
1285 rmask = bitVectUnion (rmask,
1286 rUmaskForOp (IC_RIGHT (ic)));
1289 rmask = bitVectUnion (rmask,
1290 rUmaskForOp (IC_RESULT (ic)));
1296 /*-----------------------------------------------------------------*/
1297 /* createRegMask - for each instruction will determine the regsUsed */
1298 /*-----------------------------------------------------------------*/
1300 createRegMask (eBBlock ** ebbs, int count)
1304 /* for all blocks */
1305 for (i = 0; i < count; i++)
1309 if (ebbs[i]->noPath &&
1310 (ebbs[i]->entryLabel != entryLabel &&
1311 ebbs[i]->entryLabel != returnLabel))
1314 /* for all instructions */
1315 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1320 if (SKIP_IC2 (ic) || !ic->rlive)
1323 /* first mark the registers used in this
1325 ic->rUsed = regsUsedIniCode (ic);
1326 _G.funcrUsed = bitVectUnion (_G.funcrUsed, ic->rUsed);
1328 /* now create the register mask for those
1329 registers that are in use : this is a
1330 super set of ic->rUsed */
1331 ic->rMask = newBitVect (ds390_nRegs + 1);
1333 /* for all live Ranges alive at this point */
1334 for (j = 1; j < ic->rlive->size; j++)
1339 /* if not alive then continue */
1340 if (!bitVectBitValue (ic->rlive, j))
1343 /* find the live range we are interested in */
1344 if (!(sym = hTabItemWithKey (liveRanges, j)))
1346 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
1347 "createRegMask cannot find live range");
1351 /* if no register assigned to it */
1352 if (!sym->nRegs || sym->isspilt)
1355 /* for all the registers allocated to it */
1356 for (k = 0; k < sym->nRegs; k++)
1359 bitVectSetBit (ic->rMask, sym->regs[k]->rIdx);
1365 /*-----------------------------------------------------------------*/
1366 /* rematStr - returns the rematerialized string for a remat var */
1367 /*-----------------------------------------------------------------*/
1369 rematStr (symbol * sym)
1372 iCode *ic = sym->rematiCode;
1377 /* if plus or minus print the right hand side */
1378 if (ic->op == '+' || ic->op == '-')
1380 sprintf (s, "0x%04x %c ", (int) operandLitValue (IC_RIGHT (ic)),
1383 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1386 /* cast then continue */
1387 if (IS_CAST_ICODE(ic)) {
1388 ic = OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
1391 /* we reached the end */
1392 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1399 /*-----------------------------------------------------------------*/
1400 /* regTypeNum - computes the type & number of registers required */
1401 /*-----------------------------------------------------------------*/
1409 /* for each live range do */
1410 for (sym = hTabFirstItem (liveRanges, &k); sym;
1411 sym = hTabNextItem (liveRanges, &k))
1414 /* if used zero times then no registers needed */
1415 if ((sym->liveTo - sym->liveFrom) == 0)
1419 /* if the live range is a temporary */
1423 /* if the type is marked as a conditional */
1424 if (sym->regType == REG_CND)
1427 /* if used in return only then we don't
1429 if (sym->ruonly || sym->accuse)
1431 if (IS_AGGREGATE (sym->type) || sym->isptr)
1432 sym->type = aggrToPtr (sym->type, FALSE);
1436 /* if the symbol has only one definition &
1437 that definition is a get_pointer and the
1438 pointer we are getting is rematerializable and
1441 if (bitVectnBitsOn (sym->defs) == 1 &&
1442 (ic = hTabItemWithKey (iCodehTab,
1443 bitVectFirstBit (sym->defs))) &&
1446 !IS_BITVAR (sym->etype))
1450 /* if remat in data space */
1451 if (OP_SYMBOL (IC_LEFT (ic))->remat &&
1452 !IS_CAST_ICODE(OP_SYMBOL (IC_LEFT (ic))->rematiCode) &&
1453 DCL_TYPE (aggrToPtr (sym->type, FALSE)) == POINTER)
1456 /* create a psuedo symbol & force a spil */
1457 symbol *psym = newSymbol (rematStr (OP_SYMBOL (IC_LEFT (ic))), 1);
1458 psym->type = sym->type;
1459 psym->etype = sym->etype;
1460 strcpy (psym->rname, psym->name);
1462 sym->usl.spillLoc = psym;
1466 /* if in data space or idata space then try to
1467 allocate pointer register */
1471 /* if not then we require registers */
1472 sym->nRegs = ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1473 getSize (sym->type = aggrToPtr (sym->type, FALSE)) :
1474 getSize (sym->type));
1478 fprintf (stderr, "allocated more than 4 or 0 registers for type ");
1479 printTypeChain (sym->type, stderr);
1480 fprintf (stderr, "\n");
1483 /* determine the type of register required */
1484 if (sym->nRegs == 1 &&
1485 IS_PTR (sym->type) &&
1487 sym->regType = REG_PTR;
1489 sym->regType = REG_GPR;
1493 /* for the first run we don't provide */
1494 /* registers for true symbols we will */
1495 /* see how things go */
1501 /*-----------------------------------------------------------------*/
1502 /* freeAllRegs - mark all registers as free */
1503 /*-----------------------------------------------------------------*/
1509 for (i = 0; i < ds390_nRegs; i++)
1510 regs390[i].isFree = 1;
1513 /*-----------------------------------------------------------------*/
1514 /* deallocStackSpil - this will set the stack pointer back */
1515 /*-----------------------------------------------------------------*/
1517 DEFSETFUNC (deallocStackSpil)
1525 /*-----------------------------------------------------------------*/
1526 /* farSpacePackable - returns the packable icode for far variables */
1527 /*-----------------------------------------------------------------*/
1529 farSpacePackable (iCode * ic)
1533 /* go thru till we find a definition for the
1534 symbol on the right */
1535 for (dic = ic->prev; dic; dic = dic->prev)
1538 /* if the definition is a call then no */
1539 if ((dic->op == CALL || dic->op == PCALL) &&
1540 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1545 /* if shift by unknown amount then not */
1546 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1547 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1550 /* if pointer get and size > 1 */
1551 if (POINTER_GET (dic) &&
1552 getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) > 1)
1555 if (POINTER_SET (dic) &&
1556 getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)) > 1)
1559 /* if any three is a true symbol in far space */
1560 if (IC_RESULT (dic) &&
1561 IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1562 isOperandInFarSpace (IC_RESULT (dic)))
1565 if (IC_RIGHT (dic) &&
1566 IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
1567 isOperandInFarSpace (IC_RIGHT (dic)) &&
1568 !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
1571 if (IC_LEFT (dic) &&
1572 IS_TRUE_SYMOP (IC_LEFT (dic)) &&
1573 isOperandInFarSpace (IC_LEFT (dic)) &&
1574 !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
1577 if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic)))
1579 if ((dic->op == LEFT_OP ||
1580 dic->op == RIGHT_OP ||
1582 IS_OP_LITERAL (IC_RIGHT (dic)))
1592 /*-----------------------------------------------------------------*/
1593 /* packRegsForAssign - register reduction for assignment */
1594 /*-----------------------------------------------------------------*/
1596 packRegsForAssign (iCode * ic, eBBlock * ebp)
1600 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1601 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1602 OP_LIVETO (IC_RIGHT (ic)) > ic->seq)
1607 /* if the true symbol is defined in far space or on stack
1608 then we should not since this will increase register pressure */
1610 if (isOperandInFarSpace (IC_RESULT (ic)))
1612 if ((dic = farSpacePackable (ic)))
1618 if (isOperandInFarSpace(IC_RESULT(ic)) && !farSpacePackable(ic)) {
1623 /* find the definition of iTempNN scanning backwards if we find a
1624 a use of the true symbol in before we find the definition then
1626 for (dic = ic->prev; dic; dic = dic->prev)
1628 /* if there is a function call then don't pack it */
1629 if ((dic->op == CALL || dic->op == PCALL))
1638 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1639 IS_OP_VOLATILE (IC_RESULT (dic)))
1645 if (IS_SYMOP (IC_RESULT (dic)) &&
1646 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1648 if (POINTER_SET (dic))
1654 if (IS_SYMOP (IC_RIGHT (dic)) &&
1655 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1656 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key))
1662 if (IS_SYMOP (IC_LEFT (dic)) &&
1663 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1664 IC_LEFT (dic)->key == IC_RIGHT (ic)->key))
1670 if (POINTER_SET (dic) &&
1671 IC_RESULT (dic)->key == IC_RESULT (ic)->key)
1679 return 0; /* did not find */
1681 /* if the result is on stack or iaccess then it must be
1682 the same atleast one of the operands */
1683 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1684 OP_SYMBOL (IC_RESULT (ic))->iaccess)
1687 /* the operation has only one symbol
1688 operator then we can pack */
1689 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1690 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1693 if (!((IC_LEFT (dic) &&
1694 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1696 IC_RESULT (ic)->key == IC_RIGHT (dic)->key)))
1700 /* found the definition */
1701 /* replace the result with the result of */
1702 /* this assignment and remove this assignment */
1703 IC_RESULT (dic) = IC_RESULT (ic);
1705 if (IS_ITEMP (IC_RESULT (dic)) && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq)
1707 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1709 /* delete from liverange table also
1710 delete from all the points inbetween and the new
1712 for (sic = dic; sic != ic; sic = sic->next)
1714 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1715 if (IS_ITEMP (IC_RESULT (dic)))
1716 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1719 remiCodeFromeBBlock (ebp, ic);
1720 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1721 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
1726 /*-----------------------------------------------------------------*/
1727 /* findAssignToSym : scanning backwards looks for first assig found */
1728 /*-----------------------------------------------------------------*/
1730 findAssignToSym (operand * op, iCode * ic)
1734 for (dic = ic->prev; dic; dic = dic->prev)
1737 /* if definition by assignment */
1738 if (dic->op == '=' &&
1739 !POINTER_SET (dic) &&
1740 IC_RESULT (dic)->key == op->key
1741 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1745 /* we are interested only if defined in far space */
1746 /* or in stack space in case of + & - */
1748 /* if assigned to a non-symbol then return
1750 if (!IS_SYMOP (IC_RIGHT (dic)))
1753 /* if the symbol is in far space then
1755 if (isOperandInFarSpace (IC_RIGHT (dic)))
1758 /* for + & - operations make sure that
1759 if it is on the stack it is the same
1760 as one of the three operands */
1761 if ((ic->op == '+' || ic->op == '-') &&
1762 OP_SYMBOL (IC_RIGHT (dic))->onStack)
1765 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key &&
1766 IC_LEFT (ic)->key != IC_RIGHT (dic)->key &&
1767 IC_RIGHT (ic)->key != IC_RIGHT (dic)->key)
1775 /* if we find an usage then we cannot delete it */
1776 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
1779 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
1782 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
1786 /* now make sure that the right side of dic
1787 is not defined between ic & dic */
1790 iCode *sic = dic->next;
1792 for (; sic != ic; sic = sic->next)
1793 if (IC_RESULT (sic) &&
1794 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
1803 /*-----------------------------------------------------------------*/
1804 /* packRegsForSupport :- reduce some registers for support calls */
1805 /*-----------------------------------------------------------------*/
1807 packRegsForSupport (iCode * ic, eBBlock * ebp)
1810 /* for the left & right operand :- look to see if the
1811 left was assigned a true symbol in far space in that
1812 case replace them */
1813 if (IS_ITEMP (IC_LEFT (ic)) &&
1814 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq)
1816 iCode *dic = findAssignToSym (IC_LEFT (ic), ic);
1822 /* found it we need to remove it from the
1824 for (sic = dic; sic != ic; sic = sic->next)
1825 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
1827 IC_LEFT (ic)->operand.symOperand =
1828 IC_RIGHT (dic)->operand.symOperand;
1829 IC_LEFT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1830 remiCodeFromeBBlock (ebp, dic);
1831 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1835 /* do the same for the right operand */
1838 IS_ITEMP (IC_RIGHT (ic)) &&
1839 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq)
1841 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
1847 /* if this is a subtraction & the result
1848 is a true symbol in far space then don't pack */
1849 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic)))
1851 sym_link *etype = getSpec (operandType (IC_RESULT (dic)));
1852 if (IN_FARSPACE (SPEC_OCLS (etype)))
1855 /* found it we need to remove it from the
1857 for (sic = dic; sic != ic; sic = sic->next)
1858 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
1860 IC_RIGHT (ic)->operand.symOperand =
1861 IC_RIGHT (dic)->operand.symOperand;
1862 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1864 remiCodeFromeBBlock (ebp, dic);
1865 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1872 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1875 /*-----------------------------------------------------------------*/
1876 /* packRegsForOneuse : - will reduce some registers for single Use */
1877 /*-----------------------------------------------------------------*/
1879 packRegsForOneuse (iCode * ic, operand * op, eBBlock * ebp)
1883 /* I can't figure out how to make this safe yet. */
1884 if ((int)ic+(int)op+(int)ebp) {
1895 /* if returning a literal then do nothing */
1899 /* only upto 2 bytes since we cannot predict
1900 the usage of b, & acc */
1901 if (getSize (operandType (op)) > (fReturnSizeDS390 - 2))
1904 if (ic->op != RETURN &&
1906 !POINTER_SET (ic) &&
1910 /* this routine will mark the a symbol as used in one
1911 instruction use only && if the defintion is local
1912 (ie. within the basic block) && has only one definition &&
1913 that definiion is either a return value from a
1914 function or does not contain any variables in
1916 uses = bitVectCopy (OP_USES (op));
1917 bitVectUnSetBit (uses, ic->key); /* take away this iCode */
1918 if (!bitVectIsZero (uses)) /* has other uses */
1921 /* if it has only one defintion */
1922 if (bitVectnBitsOn (OP_DEFS (op)) > 1)
1923 return NULL; /* has more than one definition */
1925 /* get the that definition */
1927 hTabItemWithKey (iCodehTab,
1928 bitVectFirstBit (OP_DEFS (op)))))
1931 /* if that only usage is a cast */
1932 if (dic->op == CAST) {
1933 /* to a bigger type */
1934 if (getSize(OP_SYM_TYPE(IC_RESULT(dic))) >
1935 getSize(OP_SYM_TYPE(IC_RIGHT(dic)))) {
1936 /* than we can not, since we cannot predict the usage of b & acc */
1941 /* found the definition now check if it is local */
1942 if (dic->seq < ebp->fSeq ||
1943 dic->seq > ebp->lSeq)
1944 return NULL; /* non-local */
1946 /* now check if it is the return from
1948 if (dic->op == CALL || dic->op == PCALL)
1950 if (ic->op != SEND && ic->op != RETURN)
1952 OP_SYMBOL (op)->ruonly = 1;
1959 /* otherwise check that the definition does
1960 not contain any symbols in far space */
1961 if (isOperandInFarSpace (IC_LEFT (dic)) ||
1962 isOperandInFarSpace (IC_RIGHT (dic)) ||
1963 IS_OP_RUONLY (IC_LEFT (ic)) ||
1964 IS_OP_RUONLY (IC_RIGHT (ic)))
1969 /* if pointer set then make sure the pointer
1971 if (POINTER_SET (dic) &&
1972 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1975 if (POINTER_GET (dic) &&
1976 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1981 /* also make sure the intervenening instructions
1982 don't have any thing in far space */
1983 for (dic = dic->next; dic && dic != ic; dic = dic->next)
1986 /* if there is an intervening function call then no */
1987 if (dic->op == CALL || dic->op == PCALL)
1989 /* if pointer set then make sure the pointer
1991 if (POINTER_SET (dic) &&
1992 !IS_DATA_PTR (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)))
1995 if (POINTER_GET (dic) &&
1996 !IS_DATA_PTR (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)))
1999 /* if address of & the result is remat the okay */
2000 if (dic->op == ADDRESS_OF &&
2001 OP_SYMBOL (IC_RESULT (dic))->remat)
2004 /* if operand has size of three or more & this
2005 operation is a '*','/' or '%' then 'b' may
2007 if ((dic->op == '%' || dic->op == '/' || dic->op == '*') &&
2008 getSize (operandType (op)) >= 3)
2011 /* if left or right or result is in far space */
2012 if (isOperandInFarSpace (IC_LEFT (dic)) ||
2013 isOperandInFarSpace (IC_RIGHT (dic)) ||
2014 isOperandInFarSpace (IC_RESULT (dic)) ||
2015 IS_OP_RUONLY (IC_LEFT (dic)) ||
2016 IS_OP_RUONLY (IC_RIGHT (dic)) ||
2017 IS_OP_RUONLY (IC_RESULT (dic)))
2023 OP_SYMBOL (op)->ruonly = 1;
2028 /*-----------------------------------------------------------------*/
2029 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
2030 /*-----------------------------------------------------------------*/
2032 isBitwiseOptimizable (iCode * ic)
2034 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
2035 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
2037 /* bitwise operations are considered optimizable
2038 under the following conditions (Jean-Louis VERN)
2050 if ( IS_LITERAL (rtype) ||
2051 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
2057 /*-----------------------------------------------------------------*/
2058 /* packRegsForAccUse - pack registers for acc use */
2059 /*-----------------------------------------------------------------*/
2061 packRegsForAccUse (iCode * ic)
2065 /* if + or - then it has to be one byte result */
2066 if ((ic->op == '+' || ic->op == '-')
2067 && getSize (operandType (IC_RESULT (ic))) > 1)
2070 /* if shift operation make sure right side is not a literal */
2071 if (ic->op == RIGHT_OP &&
2072 (isOperandLiteral (IC_RIGHT (ic)) ||
2073 getSize (operandType (IC_RESULT (ic))) > 1))
2076 if (ic->op == LEFT_OP &&
2077 (isOperandLiteral (IC_RIGHT (ic)) ||
2078 getSize (operandType (IC_RESULT (ic))) > 1))
2081 if (IS_BITWISE_OP (ic) &&
2082 getSize (operandType (IC_RESULT (ic))) > 1)
2086 /* has only one definition */
2087 if (bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) > 1)
2090 /* has only one use */
2091 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) > 1)
2094 /* and the usage immediately follows this iCode */
2095 if (!(uic = hTabItemWithKey (iCodehTab,
2096 bitVectFirstBit (OP_USES (IC_RESULT (ic))))))
2099 if (ic->next != uic)
2102 /* if it is a conditional branch then we definitely can */
2106 if (uic->op == JUMPTABLE)
2109 /* if the usage is not is an assignment
2110 or an arithmetic / bitwise / shift operation then not */
2111 if (POINTER_SET (uic) &&
2112 getSize (aggrToPtr (operandType (IC_RESULT (uic)), FALSE)) > 1)
2115 if (uic->op != '=' &&
2116 !IS_ARITHMETIC_OP (uic) &&
2117 !IS_BITWISE_OP (uic) &&
2118 uic->op != LEFT_OP &&
2119 uic->op != RIGHT_OP)
2122 /* if used in ^ operation then make sure right is not a
2124 if (uic->op == '^' && isOperandLiteral (IC_RIGHT (uic)))
2127 /* if shift operation make sure right side is not a literal */
2128 if (uic->op == RIGHT_OP &&
2129 (isOperandLiteral (IC_RIGHT (uic)) ||
2130 getSize (operandType (IC_RESULT (uic))) > 1))
2133 if (uic->op == LEFT_OP &&
2134 (isOperandLiteral (IC_RIGHT (uic)) ||
2135 getSize (operandType (IC_RESULT (uic))) > 1))
2138 /* make sure that the result of this icode is not on the
2139 stack, since acc is used to compute stack offset */
2140 if (IS_TRUE_SYMOP (IC_RESULT (uic)) &&
2141 OP_SYMBOL (IC_RESULT (uic))->onStack)
2144 /* if either one of them in far space then we cannot */
2145 if ((IS_TRUE_SYMOP (IC_LEFT (uic)) &&
2146 isOperandInFarSpace (IC_LEFT (uic))) ||
2147 (IS_TRUE_SYMOP (IC_RIGHT (uic)) &&
2148 isOperandInFarSpace (IC_RIGHT (uic))))
2151 /* if the usage has only one operand then we can */
2152 if (IC_LEFT (uic) == NULL ||
2153 IC_RIGHT (uic) == NULL)
2156 /* make sure this is on the left side if not
2157 a '+' since '+' is commutative */
2158 if (ic->op != '+' &&
2159 IC_LEFT (uic)->key != IC_RESULT (ic)->key)
2163 // this is too dangerous and need further restrictions
2166 /* if one of them is a literal then we can */
2167 if ((IC_LEFT (uic) && IS_OP_LITERAL (IC_LEFT (uic))) ||
2168 (IC_RIGHT (uic) && IS_OP_LITERAL (IC_RIGHT (uic))))
2170 OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2175 /* if the other one is not on stack then we can */
2176 if (IC_LEFT (uic)->key == IC_RESULT (ic)->key &&
2177 (IS_ITEMP (IC_RIGHT (uic)) ||
2178 (IS_TRUE_SYMOP (IC_RIGHT (uic)) &&
2179 !OP_SYMBOL (IC_RIGHT (uic))->onStack)))
2182 if (IC_RIGHT (uic)->key == IC_RESULT (ic)->key &&
2183 (IS_ITEMP (IC_LEFT (uic)) ||
2184 (IS_TRUE_SYMOP (IC_LEFT (uic)) &&
2185 !OP_SYMBOL (IC_LEFT (uic))->onStack)))
2191 OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2196 /*-----------------------------------------------------------------*/
2197 /* packForPush - hueristics to reduce iCode for pushing */
2198 /*-----------------------------------------------------------------*/
2200 packForPush (iCode * ic, eBBlock * ebp)
2205 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
2208 /* must have only definition & one usage */
2209 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
2210 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
2213 /* find the definition */
2214 if (!(dic = hTabItemWithKey (iCodehTab,
2215 bitVectFirstBit (OP_DEFS (IC_LEFT (ic))))))
2218 if (dic->op != '=' || POINTER_SET (dic))
2221 /* make sure the right side does not have any definitions
2223 dbv = OP_DEFS(IC_RIGHT(dic));
2224 for (lic = ic; lic && lic != dic ; lic = lic->prev) {
2225 if (bitVectBitValue(dbv,lic->key)) return ;
2227 /* make sure they have the same type */
2229 sym_link *itype=operandType(IC_LEFT(ic));
2230 sym_link *ditype=operandType(IC_RIGHT(dic));
2232 if (SPEC_USIGN(itype)!=SPEC_USIGN(ditype) ||
2233 SPEC_LONG(itype)!=SPEC_LONG(ditype))
2236 /* extend the live range of replaced operand if needed */
2237 if (OP_SYMBOL(IC_RIGHT(dic))->liveTo < ic->seq) {
2238 OP_SYMBOL(IC_RIGHT(dic))->liveTo = ic->seq;
2240 /* we now we know that it has one & only one def & use
2241 and the that the definition is an assignment */
2242 IC_LEFT (ic) = IC_RIGHT (dic);
2244 remiCodeFromeBBlock (ebp, dic);
2245 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
2248 /*-----------------------------------------------------------------*/
2249 /* packRegisters - does some transformations to reduce register */
2251 /*-----------------------------------------------------------------*/
2253 packRegisters (eBBlock * ebp)
2263 /* look for assignments of the form */
2264 /* iTempNN = TRueSym (someoperation) SomeOperand */
2266 /* TrueSym := iTempNN:1 */
2267 for (ic = ebp->sch; ic; ic = ic->next)
2271 /* find assignment of the form TrueSym := iTempNN:1 */
2272 if (ic->op == '=' && !POINTER_SET (ic))
2273 change += packRegsForAssign (ic, ebp);
2280 for (ic = ebp->sch; ic; ic = ic->next)
2283 /* if this is an itemp & result of a address of a true sym
2284 then mark this as rematerialisable */
2285 if (ic->op == ADDRESS_OF &&
2286 IS_ITEMP (IC_RESULT (ic)) &&
2287 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2288 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2289 !OP_SYMBOL (IC_LEFT (ic))->onStack)
2292 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2293 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2294 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2298 /* if straight assignment then carry remat flag if
2299 this is the only definition */
2300 if (ic->op == '=' &&
2301 !POINTER_SET (ic) &&
2302 IS_SYMOP (IC_RIGHT (ic)) &&
2303 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2304 !IS_CAST_ICODE(OP_SYMBOL (IC_RIGHT (ic))->rematiCode) &&
2305 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1)
2308 OP_SYMBOL (IC_RESULT (ic))->remat =
2309 OP_SYMBOL (IC_RIGHT (ic))->remat;
2310 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2311 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2314 /* if cast to a generic pointer & the pointer being
2315 cast is remat, then we can remat this cast as well */
2316 if (ic->op == CAST &&
2317 IS_SYMOP(IC_RIGHT(ic)) &&
2318 OP_SYMBOL(IC_RIGHT(ic))->remat ) {
2319 sym_link *to_type = operandType(IC_LEFT(ic));
2320 sym_link *from_type = operandType(IC_RIGHT(ic));
2321 if (IS_GENPTR(to_type) && IS_PTR(from_type)) {
2322 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2323 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2324 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2328 /* if this is a +/- operation with a rematerizable
2329 then mark this as rematerializable as well */
2330 if ((ic->op == '+' || ic->op == '-') &&
2331 (IS_SYMOP (IC_LEFT (ic)) &&
2332 IS_ITEMP (IC_RESULT (ic)) &&
2333 OP_SYMBOL (IC_LEFT (ic))->remat &&
2334 (!IS_SYMOP (IC_RIGHT (ic)) || !IS_CAST_ICODE(OP_SYMBOL (IC_RIGHT (ic))->rematiCode)) &&
2335 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2336 IS_OP_LITERAL (IC_RIGHT (ic))))
2339 //int i = operandLitValue(IC_RIGHT(ic));
2340 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2341 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2342 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2345 /* mark the pointer usages */
2346 if (POINTER_SET (ic))
2347 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2349 if (POINTER_GET (ic))
2350 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2354 /* if we are using a symbol on the stack
2355 then we should say ds390_ptrRegReq */
2356 if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
2357 ds390_ptrRegReq += ((OP_SYMBOL (IC_COND (ic))->onStack ? !options.stack10bit : 0) +
2358 OP_SYMBOL (IC_COND (ic))->iaccess);
2359 else if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
2360 ds390_ptrRegReq += ((OP_SYMBOL (IC_JTCOND (ic))->onStack ? !options.stack10bit : 0) +
2361 OP_SYMBOL (IC_JTCOND (ic))->iaccess);
2364 if (IS_SYMOP (IC_LEFT (ic)))
2365 ds390_ptrRegReq += ((OP_SYMBOL (IC_LEFT (ic))->onStack ? !options.stack10bit : 0) +
2366 OP_SYMBOL (IC_LEFT (ic))->iaccess);
2367 if (IS_SYMOP (IC_RIGHT (ic)))
2368 ds390_ptrRegReq += ((OP_SYMBOL (IC_RIGHT (ic))->onStack ? !options.stack10bit : 0) +
2369 OP_SYMBOL (IC_RIGHT (ic))->iaccess);
2370 if (IS_SYMOP (IC_RESULT (ic)))
2371 ds390_ptrRegReq += ((OP_SYMBOL (IC_RESULT (ic))->onStack ? !options.stack10bit : 0) +
2372 OP_SYMBOL (IC_RESULT (ic))->iaccess);
2377 /* if the condition of an if instruction
2378 is defined in the previous instruction then
2379 mark the itemp as a conditional */
2380 if ((IS_CONDITIONAL (ic) ||
2381 (IS_BITWISE_OP(ic) && isBitwiseOptimizable(ic))) &&
2382 ic->next && ic->next->op == IFX &&
2383 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2384 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq)
2387 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2391 /* if the condition of an if instruction
2392 is defined in the previous instruction and
2393 this is the only usage then
2394 mark the itemp as a conditional */
2395 if ((IS_CONDITIONAL (ic) ||
2396 (IS_BITWISE_OP(ic) && isBitwiseOptimizable (ic))) &&
2397 ic->next && ic->next->op == IFX &&
2398 bitVectnBitsOn (OP_USES(IC_RESULT(ic)))==1 &&
2399 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2400 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq)
2402 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2407 /* reduce for support function calls */
2408 if (ic->supportRtn || ic->op == '+' || ic->op == '-')
2409 packRegsForSupport (ic, ebp);
2411 /* some cases the redundant moves can
2412 can be eliminated for return statements */
2413 if ((ic->op == RETURN || ic->op == SEND) &&
2414 !isOperandInFarSpace (IC_LEFT (ic)) &&
2416 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2418 /* if pointer set & left has a size more than
2419 one and right is not in far space */
2420 if (POINTER_SET (ic) &&
2421 !isOperandInFarSpace (IC_RIGHT (ic)) &&
2422 !OP_SYMBOL (IC_RESULT (ic))->remat &&
2423 !IS_OP_RUONLY (IC_RIGHT (ic)) &&
2424 getSize (aggrToPtr (operandType (IC_RESULT (ic)), FALSE)) > 1)
2426 packRegsForOneuse (ic, IC_RESULT (ic), ebp);
2428 /* if pointer get */
2429 if (POINTER_GET (ic) &&
2430 !isOperandInFarSpace (IC_RESULT (ic)) &&
2431 !OP_SYMBOL (IC_LEFT (ic))->remat &&
2432 !IS_OP_RUONLY (IC_RESULT (ic)) &&
2433 getSize (aggrToPtr (operandType (IC_LEFT (ic)), FALSE)) > 1)
2435 packRegsForOneuse (ic, IC_LEFT (ic), ebp);
2438 /* if this is cast for intergral promotion then
2439 check if only use of the definition of the
2440 operand being casted/ if yes then replace
2441 the result of that arithmetic operation with
2442 this result and get rid of the cast */
2445 sym_link *fromType = operandType (IC_RIGHT (ic));
2446 sym_link *toType = operandType (IC_LEFT (ic));
2448 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2449 getSize (fromType) != getSize (toType) &&
2450 SPEC_USIGN (fromType) == SPEC_USIGN (toType))
2453 iCode *dic = packRegsForOneuse (ic, IC_RIGHT (ic), ebp);
2456 if (IS_ARITHMETIC_OP (dic))
2458 IC_RESULT (dic) = IC_RESULT (ic);
2459 remiCodeFromeBBlock (ebp, ic);
2460 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2461 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2465 OP_SYMBOL (IC_RIGHT (ic))->ruonly = 0;
2471 /* if the type from and type to are the same
2472 then if this is the only use then packit */
2473 if (compareType (operandType (IC_RIGHT (ic)),
2474 operandType (IC_LEFT (ic))) == 1)
2476 iCode *dic = packRegsForOneuse (ic, IC_RIGHT (ic), ebp);
2479 IC_RESULT (dic) = IC_RESULT (ic);
2480 remiCodeFromeBBlock (ebp, ic);
2481 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2482 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2490 iTempNN := (some variable in farspace) V1
2495 if (ic->op == IPUSH)
2497 packForPush (ic, ebp);
2501 /* pack registers for accumulator use, when the
2502 result of an arithmetic or bit wise operation
2503 has only one use, that use is immediately following
2504 the defintion and the using iCode has only one
2505 operand or has two operands but one is literal &
2506 the result of that operation is not on stack then
2507 we can leave the result of this operation in acc:b
2509 if ((IS_ARITHMETIC_OP (ic)
2510 || IS_CONDITIONAL(ic)
2511 || IS_BITWISE_OP (ic)
2512 || ic->op == LEFT_OP || ic->op == RIGHT_OP
2513 || (ic->op == ADDRESS_OF && isOperandOnStack (IC_LEFT (ic)))
2515 IS_ITEMP (IC_RESULT (ic)) &&
2516 getSize (operandType (IC_RESULT (ic))) <= 2)
2518 packRegsForAccUse (ic);
2523 /*-----------------------------------------------------------------*/
2524 /* assignRegisters - assigns registers to each live range as need */
2525 /*-----------------------------------------------------------------*/
2527 ds390_assignRegisters (eBBlock ** ebbs, int count)
2532 setToNull ((void *) &_G.funcrUsed);
2533 ds390_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2535 if (options.model != MODEL_FLAT24) options.stack10bit = 0;
2536 /* change assignments this will remove some
2537 live ranges reducing some register pressure */
2538 for (i = 0; i < count; i++)
2539 packRegisters (ebbs[i]);
2541 if (options.dump_pack)
2542 dumpEbbsToFileExt (DUMP_PACK, ebbs, count);
2544 /* first determine for each live range the number of
2545 registers & the type of registers required for each */
2548 /* and serially allocate registers */
2549 serialRegAssign (ebbs, count);
2551 /* if stack was extended then tell the user */
2554 /* werror(W_TOOMANY_SPILS,"stack", */
2555 /* _G.stackExtend,currFunc->name,""); */
2561 /* werror(W_TOOMANY_SPILS,"data space", */
2562 /* _G.dataExtend,currFunc->name,""); */
2566 /* after that create the register mask
2567 for each of the instruction */
2568 createRegMask (ebbs, count);
2570 /* redo that offsets for stacked automatic variables */
2571 redoStackOffsets ();
2573 if (options.dump_rassgn) {
2574 dumpEbbsToFileExt (DUMP_RASSGN, ebbs, count);
2575 dumpLiveRanges (DUMP_LRANGE, liveRanges);
2578 /* do the overlaysegment stuff SDCCmem.c */
2579 doOverlays (ebbs, count);
2581 /* now get back the chain */
2582 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2587 /* free up any _G.stackSpil locations allocated */
2588 applyToSet (_G.stackSpil, deallocStackSpil);
2590 setToNull ((void **) &_G.stackSpil);
2591 setToNull ((void **) &_G.spiltSet);
2592 /* mark all registers as free */