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, 1},
61 {REG_GPR, R3_IDX, REG_GPR, "r3", "ar3", "0", 3, 1, 1},
62 {REG_GPR, R4_IDX, REG_GPR, "r4", "ar4", "0", 4, 1, 1},
63 {REG_GPR, R5_IDX, REG_GPR, "r5", "ar5", "0", 5, 1, 1},
64 {REG_GPR, R6_IDX, REG_GPR, "r6", "ar6", "0", 6, 1, 1},
65 {REG_GPR, R7_IDX, REG_GPR, "r7", "ar7", "0", 7, 1, 1},
66 {REG_PTR, R0_IDX, REG_PTR, "r0", "ar0", "0", 0, 1, 1},
67 {REG_PTR, R1_IDX, REG_PTR, "r1", "ar1", "0", 1, 1, 1},
68 {REG_GPR, X8_IDX, REG_GPR, "x8", "x8", "xreg", 0, 0, 0},
69 {REG_GPR, X9_IDX, REG_GPR, "x9", "x9", "xreg", 1, 0, 0},
70 {REG_GPR, X10_IDX, REG_GPR, "x10", "x10", "xreg", 2, 0, 0},
71 {REG_GPR, X11_IDX, REG_GPR, "x11", "x11", "xreg", 3, 0, 0},
72 {REG_GPR, X12_IDX, REG_GPR, "x12", "x12", "xreg", 4, 0, 0},
73 {REG_CND, CND_IDX, REG_GPR, "C", "C", "xreg", 0, 0, 0},
74 {REG_GPR, DPL_IDX, REG_GPR, "dpl", "dpl", "dpl", 0, 0, 0},
75 {REG_GPR, DPH_IDX, REG_GPR, "dph", "dph", "dph", 0, 0, 0},
76 {REG_GPR, DPX_IDX, REG_GPR, "dpx", "dpx", "dpx", 0, 0, 0},
77 {REG_GPR, B_IDX, REG_GPR, "b", "b", "b", 0, 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 /* special case for ruonly */
1353 int size = getSize(sym->type);
1355 for (k = 0 ; k < size; k++ )
1356 ic->rMask = bitVectSetBit (ic->rMask, j++);
1359 /* if no register assigned to it */
1360 if (!sym->nRegs || sym->isspilt)
1363 /* for all the registers allocated to it */
1364 for (k = 0; k < sym->nRegs; k++)
1367 bitVectSetBit (ic->rMask, sym->regs[k]->rIdx);
1373 /*-----------------------------------------------------------------*/
1374 /* rematStr - returns the rematerialized string for a remat var */
1375 /*-----------------------------------------------------------------*/
1377 rematStr (symbol * sym)
1380 iCode *ic = sym->rematiCode;
1385 /* if plus or minus print the right hand side */
1386 if (ic->op == '+' || ic->op == '-')
1388 sprintf (s, "0x%04x %c ", (int) operandLitValue (IC_RIGHT (ic)),
1391 ic = OP_SYMBOL (IC_LEFT (ic))->rematiCode;
1394 /* cast then continue */
1395 if (IS_CAST_ICODE(ic)) {
1396 ic = OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
1399 /* we reached the end */
1400 sprintf (s, "%s", OP_SYMBOL (IC_LEFT (ic))->rname);
1407 /*-----------------------------------------------------------------*/
1408 /* regTypeNum - computes the type & number of registers required */
1409 /*-----------------------------------------------------------------*/
1417 /* for each live range do */
1418 for (sym = hTabFirstItem (liveRanges, &k); sym;
1419 sym = hTabNextItem (liveRanges, &k))
1422 /* if used zero times then no registers needed */
1423 if ((sym->liveTo - sym->liveFrom) == 0)
1427 /* if the live range is a temporary */
1431 /* if the type is marked as a conditional */
1432 if (sym->regType == REG_CND)
1435 /* if used in return only then we don't
1437 if (sym->ruonly || sym->accuse)
1439 if (IS_AGGREGATE (sym->type) || sym->isptr)
1440 sym->type = aggrToPtr (sym->type, FALSE);
1444 /* if the symbol has only one definition &
1445 that definition is a get_pointer and the
1446 pointer we are getting is rematerializable and
1449 if (bitVectnBitsOn (sym->defs) == 1 &&
1450 (ic = hTabItemWithKey (iCodehTab,
1451 bitVectFirstBit (sym->defs))) &&
1454 !IS_BITVAR (sym->etype))
1458 /* if remat in data space */
1459 if (OP_SYMBOL (IC_LEFT (ic))->remat &&
1460 !IS_CAST_ICODE(OP_SYMBOL (IC_LEFT (ic))->rematiCode) &&
1461 DCL_TYPE (aggrToPtr (sym->type, FALSE)) == POINTER)
1464 /* create a psuedo symbol & force a spil */
1465 symbol *psym = newSymbol (rematStr (OP_SYMBOL (IC_LEFT (ic))), 1);
1466 psym->type = sym->type;
1467 psym->etype = sym->etype;
1468 strcpy (psym->rname, psym->name);
1470 sym->usl.spillLoc = psym;
1474 /* if in data space or idata space then try to
1475 allocate pointer register */
1479 /* if not then we require registers */
1480 sym->nRegs = ((IS_AGGREGATE (sym->type) || sym->isptr) ?
1481 getSize (sym->type = aggrToPtr (sym->type, FALSE)) :
1482 getSize (sym->type));
1486 fprintf (stderr, "allocated more than 4 or 0 registers for type ");
1487 printTypeChain (sym->type, stderr);
1488 fprintf (stderr, "\n");
1491 /* determine the type of register required */
1492 if (sym->nRegs == 1 &&
1493 IS_PTR (sym->type) &&
1495 sym->regType = REG_PTR;
1497 sym->regType = REG_GPR;
1501 /* for the first run we don't provide */
1502 /* registers for true symbols we will */
1503 /* see how things go */
1509 /*-----------------------------------------------------------------*/
1510 /* freeAllRegs - mark all registers as free */
1511 /*-----------------------------------------------------------------*/
1517 for (i = 0; i < ds390_nRegs; i++)
1518 regs390[i].isFree = 1;
1521 /*-----------------------------------------------------------------*/
1522 /* deallocStackSpil - this will set the stack pointer back */
1523 /*-----------------------------------------------------------------*/
1525 DEFSETFUNC (deallocStackSpil)
1533 /*-----------------------------------------------------------------*/
1534 /* farSpacePackable - returns the packable icode for far variables */
1535 /*-----------------------------------------------------------------*/
1537 farSpacePackable (iCode * ic)
1541 /* go thru till we find a definition for the
1542 symbol on the right */
1543 for (dic = ic->prev; dic; dic = dic->prev)
1546 /* if the definition is a call then no */
1547 if ((dic->op == CALL || dic->op == PCALL) &&
1548 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1553 /* if shift by unknown amount then not */
1554 if ((dic->op == LEFT_OP || dic->op == RIGHT_OP) &&
1555 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1558 /* if pointer get and size > 1 */
1559 if (POINTER_GET (dic) &&
1560 getSize (aggrToPtr (operandType (IC_LEFT (dic)), FALSE)) > 1)
1563 if (POINTER_SET (dic) &&
1564 getSize (aggrToPtr (operandType (IC_RESULT (dic)), FALSE)) > 1)
1567 /* if any three is a true symbol in far space */
1568 if (IC_RESULT (dic) &&
1569 IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1570 isOperandInFarSpace (IC_RESULT (dic)))
1573 if (IC_RIGHT (dic) &&
1574 IS_TRUE_SYMOP (IC_RIGHT (dic)) &&
1575 isOperandInFarSpace (IC_RIGHT (dic)) &&
1576 !isOperandEqual (IC_RIGHT (dic), IC_RESULT (ic)))
1579 if (IC_LEFT (dic) &&
1580 IS_TRUE_SYMOP (IC_LEFT (dic)) &&
1581 isOperandInFarSpace (IC_LEFT (dic)) &&
1582 !isOperandEqual (IC_LEFT (dic), IC_RESULT (ic)))
1585 if (isOperandEqual (IC_RIGHT (ic), IC_RESULT (dic)))
1587 if ((dic->op == LEFT_OP ||
1588 dic->op == RIGHT_OP ||
1590 IS_OP_LITERAL (IC_RIGHT (dic)))
1600 /*-----------------------------------------------------------------*/
1601 /* packRegsForAssign - register reduction for assignment */
1602 /*-----------------------------------------------------------------*/
1604 packRegsForAssign (iCode * ic, eBBlock * ebp)
1608 if (!IS_ITEMP (IC_RIGHT (ic)) ||
1609 OP_SYMBOL (IC_RIGHT (ic))->isind ||
1610 OP_LIVETO (IC_RIGHT (ic)) > ic->seq)
1615 /* if the true symbol is defined in far space or on stack
1616 then we should not since this will increase register pressure */
1618 if (isOperandInFarSpace (IC_RESULT (ic)))
1620 if ((dic = farSpacePackable (ic)))
1626 if (isOperandInFarSpace(IC_RESULT(ic)) && !farSpacePackable(ic)) {
1631 /* find the definition of iTempNN scanning backwards if we find a
1632 a use of the true symbol in before we find the definition then
1634 for (dic = ic->prev; dic; dic = dic->prev)
1636 /* if there is a function call then don't pack it */
1637 if ((dic->op == CALL || dic->op == PCALL))
1646 if (IS_TRUE_SYMOP (IC_RESULT (dic)) &&
1647 IS_OP_VOLATILE (IC_RESULT (dic)))
1653 if (IS_SYMOP (IC_RESULT (dic)) &&
1654 IC_RESULT (dic)->key == IC_RIGHT (ic)->key)
1656 if (POINTER_SET (dic))
1662 if (IS_SYMOP (IC_RIGHT (dic)) &&
1663 (IC_RIGHT (dic)->key == IC_RESULT (ic)->key ||
1664 IC_RIGHT (dic)->key == IC_RIGHT (ic)->key))
1670 if (IS_SYMOP (IC_LEFT (dic)) &&
1671 (IC_LEFT (dic)->key == IC_RESULT (ic)->key ||
1672 IC_LEFT (dic)->key == IC_RIGHT (ic)->key))
1678 if (POINTER_SET (dic) &&
1679 IC_RESULT (dic)->key == IC_RESULT (ic)->key)
1687 return 0; /* did not find */
1689 /* if the result is on stack or iaccess then it must be
1690 the same atleast one of the operands */
1691 if (OP_SYMBOL (IC_RESULT (ic))->onStack ||
1692 OP_SYMBOL (IC_RESULT (ic))->iaccess)
1695 /* the operation has only one symbol
1696 operator then we can pack */
1697 if ((IC_LEFT (dic) && !IS_SYMOP (IC_LEFT (dic))) ||
1698 (IC_RIGHT (dic) && !IS_SYMOP (IC_RIGHT (dic))))
1701 if (!((IC_LEFT (dic) &&
1702 IC_RESULT (ic)->key == IC_LEFT (dic)->key) ||
1704 IC_RESULT (ic)->key == IC_RIGHT (dic)->key)))
1708 /* found the definition */
1709 /* replace the result with the result of */
1710 /* this assignment and remove this assignment */
1711 IC_RESULT (dic) = IC_RESULT (ic);
1713 if (IS_ITEMP (IC_RESULT (dic)) && OP_SYMBOL (IC_RESULT (dic))->liveFrom > dic->seq)
1715 OP_SYMBOL (IC_RESULT (dic))->liveFrom = dic->seq;
1717 /* delete from liverange table also
1718 delete from all the points inbetween and the new
1720 for (sic = dic; sic != ic; sic = sic->next)
1722 bitVectUnSetBit (sic->rlive, IC_RESULT (ic)->key);
1723 if (IS_ITEMP (IC_RESULT (dic)))
1724 bitVectSetBit (sic->rlive, IC_RESULT (dic)->key);
1727 remiCodeFromeBBlock (ebp, ic);
1728 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
1729 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
1734 /*-----------------------------------------------------------------*/
1735 /* findAssignToSym : scanning backwards looks for first assig found */
1736 /*-----------------------------------------------------------------*/
1738 findAssignToSym (operand * op, iCode * ic)
1742 for (dic = ic->prev; dic; dic = dic->prev)
1745 /* if definition by assignment */
1746 if (dic->op == '=' &&
1747 !POINTER_SET (dic) &&
1748 IC_RESULT (dic)->key == op->key
1749 /* && IS_TRUE_SYMOP(IC_RIGHT(dic)) */
1753 /* we are interested only if defined in far space */
1754 /* or in stack space in case of + & - */
1756 /* if assigned to a non-symbol then return
1758 if (!IS_SYMOP (IC_RIGHT (dic)))
1761 /* if the symbol is in far space then
1763 if (isOperandInFarSpace (IC_RIGHT (dic)))
1766 /* for + & - operations make sure that
1767 if it is on the stack it is the same
1768 as one of the three operands */
1769 if ((ic->op == '+' || ic->op == '-') &&
1770 OP_SYMBOL (IC_RIGHT (dic))->onStack)
1773 if (IC_RESULT (ic)->key != IC_RIGHT (dic)->key &&
1774 IC_LEFT (ic)->key != IC_RIGHT (dic)->key &&
1775 IC_RIGHT (ic)->key != IC_RIGHT (dic)->key)
1783 /* if we find an usage then we cannot delete it */
1784 if (IC_LEFT (dic) && IC_LEFT (dic)->key == op->key)
1787 if (IC_RIGHT (dic) && IC_RIGHT (dic)->key == op->key)
1790 if (POINTER_SET (dic) && IC_RESULT (dic)->key == op->key)
1794 /* now make sure that the right side of dic
1795 is not defined between ic & dic */
1798 iCode *sic = dic->next;
1800 for (; sic != ic; sic = sic->next)
1801 if (IC_RESULT (sic) &&
1802 IC_RESULT (sic)->key == IC_RIGHT (dic)->key)
1811 /*-----------------------------------------------------------------*/
1812 /* packRegsForSupport :- reduce some registers for support calls */
1813 /*-----------------------------------------------------------------*/
1815 packRegsForSupport (iCode * ic, eBBlock * ebp)
1818 /* for the left & right operand :- look to see if the
1819 left was assigned a true symbol in far space in that
1820 case replace them */
1821 if (IS_ITEMP (IC_LEFT (ic)) &&
1822 OP_SYMBOL (IC_LEFT (ic))->liveTo <= ic->seq)
1824 iCode *dic = findAssignToSym (IC_LEFT (ic), ic);
1830 /* found it we need to remove it from the
1832 for (sic = dic; sic != ic; sic = sic->next)
1833 bitVectUnSetBit (sic->rlive, IC_LEFT (ic)->key);
1835 IC_LEFT (ic)->operand.symOperand =
1836 IC_RIGHT (dic)->operand.symOperand;
1837 IC_LEFT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1838 remiCodeFromeBBlock (ebp, dic);
1839 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1843 /* do the same for the right operand */
1846 IS_ITEMP (IC_RIGHT (ic)) &&
1847 OP_SYMBOL (IC_RIGHT (ic))->liveTo <= ic->seq)
1849 iCode *dic = findAssignToSym (IC_RIGHT (ic), ic);
1855 /* if this is a subtraction & the result
1856 is a true symbol in far space then don't pack */
1857 if (ic->op == '-' && IS_TRUE_SYMOP (IC_RESULT (dic)))
1859 sym_link *etype = getSpec (operandType (IC_RESULT (dic)));
1860 if (IN_FARSPACE (SPEC_OCLS (etype)))
1863 /* found it we need to remove it from the
1865 for (sic = dic; sic != ic; sic = sic->next)
1866 bitVectUnSetBit (sic->rlive, IC_RIGHT (ic)->key);
1868 IC_RIGHT (ic)->operand.symOperand =
1869 IC_RIGHT (dic)->operand.symOperand;
1870 IC_RIGHT (ic)->key = IC_RIGHT (dic)->operand.symOperand->key;
1872 remiCodeFromeBBlock (ebp, dic);
1873 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
1880 #define IS_OP_RUONLY(x) (x && IS_SYMOP(x) && OP_SYMBOL(x)->ruonly)
1883 /*-----------------------------------------------------------------*/
1884 /* packRegsDPTRuse : - will reduce some registers for single Use */
1885 /*-----------------------------------------------------------------*/
1887 packRegsDPTRuse (iCode * lic, operand * op, eBBlock * ebp)
1889 /* go thru entire liveRange of this variable & check for
1890 other possible usage of DPTR , if we don't find it the
1891 assign this to DPTR (ruonly)
1896 sym_link *type, *etype;
1898 if (!IS_SYMOP(op)) return NULL;
1899 if (OP_SYMBOL(op)->remat) return NULL;
1901 /* first check if any overlapping liverange has already been
1903 if (OP_SYMBOL(op)->clashes) {
1904 for (i = 0 ; i < OP_SYMBOL(op)->clashes->size ; i++ ) {
1905 if (bitVectBitValue(OP_SYMBOL(op)->clashes,i)) {
1906 sym = hTabItemWithKey(liveRanges,i);
1907 if (sym->ruonly) return NULL ;
1912 /* no then go thru this guys live range */
1913 dic = ic = hTabFirstItemWK(iCodeSeqhTab,OP_SYMBOL(op)->liveFrom);
1914 for (; ic && ic->seq <= OP_SYMBOL(op)->liveTo;
1915 ic = hTabNextItem(iCodeSeqhTab,&key)) {
1917 /* if PCALL cannot be sure give up */
1918 if (ic->op == PCALL) return NULL;
1920 /* if CALL then make sure it is VOID || return value not used */
1921 if (ic->op == CALL) {
1922 if (OP_SYMBOL(IC_RESULT(ic))->liveTo ==
1923 OP_SYMBOL(IC_RESULT(ic))->liveFrom) continue ;
1924 etype = getSpec(type = operandType(IC_RESULT(ic)));
1925 if (getSize(type) == 0) continue ;
1929 /* special case of add with a [remat] */
1930 if (ic->op == '+' &&
1931 OP_SYMBOL(IC_LEFT(ic))->remat ) continue ;
1934 if (IC_RESULT(ic) && IS_SYMOP(IC_RESULT(ic)) &&
1935 !isOperandEqual(IC_RESULT(ic),op) &&
1936 (isOperandInFarSpace(IC_RESULT(ic)) ||
1937 OP_SYMBOL(IC_RESULT(ic))->onStack)) return NULL;
1939 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic)) &&
1940 !isOperandEqual(IC_RIGHT(ic),op) &&
1941 (OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->seq ||
1942 IS_TRUE_SYMOP(IC_RIGHT(ic))) &&
1943 (isOperandInFarSpace(IC_RIGHT(ic)) ||
1944 OP_SYMBOL(IC_RIGHT(ic))->onStack)) return NULL;
1946 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic)) &&
1947 !isOperandEqual(IC_LEFT(ic),op) &&
1948 (OP_SYMBOL(IC_LEFT(ic))->liveTo > ic->seq ||
1949 IS_TRUE_SYMOP(IC_LEFT(ic)))&&
1950 (isOperandInFarSpace(IC_LEFT(ic)) ||
1951 OP_SYMBOL(IC_LEFT(ic))->onStack)) return NULL;
1954 OP_SYMBOL(op)->ruonly = 1;
1958 /*-----------------------------------------------------------------*/
1959 /* isBitwiseOptimizable - requirements of JEAN LOUIS VERN */
1960 /*-----------------------------------------------------------------*/
1962 isBitwiseOptimizable (iCode * ic)
1964 sym_link *ltype = getSpec (operandType (IC_LEFT (ic)));
1965 sym_link *rtype = getSpec (operandType (IC_RIGHT (ic)));
1967 /* bitwise operations are considered optimizable
1968 under the following conditions (Jean-Louis VERN)
1980 if ( IS_LITERAL (rtype) ||
1981 (IS_BITVAR (ltype) && IN_BITSPACE (SPEC_OCLS (ltype))))
1987 /*-----------------------------------------------------------------*/
1988 /* packRegsForAccUse - pack registers for acc use */
1989 /*-----------------------------------------------------------------*/
1991 packRegsForAccUse (iCode * ic)
1995 /* if + or - then it has to be one byte result */
1996 if ((ic->op == '+' || ic->op == '-')
1997 && getSize (operandType (IC_RESULT (ic))) > 1)
2000 /* if shift operation make sure right side is not a literal */
2001 if (ic->op == RIGHT_OP &&
2002 (isOperandLiteral (IC_RIGHT (ic)) ||
2003 getSize (operandType (IC_RESULT (ic))) > 1))
2006 if (ic->op == LEFT_OP &&
2007 (isOperandLiteral (IC_RIGHT (ic)) ||
2008 getSize (operandType (IC_RESULT (ic))) > 1))
2011 if (IS_BITWISE_OP (ic) &&
2012 getSize (operandType (IC_RESULT (ic))) > 1)
2016 /* has only one definition */
2017 if (bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) > 1)
2020 /* has only one use */
2021 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) > 1)
2024 /* and the usage immediately follows this iCode */
2025 if (!(uic = hTabItemWithKey (iCodehTab,
2026 bitVectFirstBit (OP_USES (IC_RESULT (ic))))))
2029 if (ic->next != uic)
2032 /* if it is a conditional branch then we definitely can */
2036 if (uic->op == JUMPTABLE)
2039 /* if the usage is not is an assignment
2040 or an arithmetic / bitwise / shift operation then not */
2041 if (POINTER_SET (uic) &&
2042 getSize (aggrToPtr (operandType (IC_RESULT (uic)), FALSE)) > 1)
2045 if (uic->op != '=' &&
2046 !IS_ARITHMETIC_OP (uic) &&
2047 !IS_BITWISE_OP (uic) &&
2048 uic->op != LEFT_OP &&
2049 uic->op != RIGHT_OP)
2052 /* if used in ^ operation then make sure right is not a
2054 if (uic->op == '^' && isOperandLiteral (IC_RIGHT (uic)))
2057 /* if shift operation make sure right side is not a literal */
2058 if (uic->op == RIGHT_OP &&
2059 (isOperandLiteral (IC_RIGHT (uic)) ||
2060 getSize (operandType (IC_RESULT (uic))) > 1))
2063 if (uic->op == LEFT_OP &&
2064 (isOperandLiteral (IC_RIGHT (uic)) ||
2065 getSize (operandType (IC_RESULT (uic))) > 1))
2068 /* make sure that the result of this icode is not on the
2069 stack, since acc is used to compute stack offset */
2070 if (IS_TRUE_SYMOP (IC_RESULT (uic)) &&
2071 OP_SYMBOL (IC_RESULT (uic))->onStack)
2074 /* if either one of them in far space then we cannot */
2075 if ((IS_TRUE_SYMOP (IC_LEFT (uic)) &&
2076 isOperandInFarSpace (IC_LEFT (uic))) ||
2077 (IS_TRUE_SYMOP (IC_RIGHT (uic)) &&
2078 isOperandInFarSpace (IC_RIGHT (uic))))
2081 /* if the usage has only one operand then we can */
2082 if (IC_LEFT (uic) == NULL ||
2083 IC_RIGHT (uic) == NULL)
2086 /* make sure this is on the left side if not
2087 a '+' since '+' is commutative */
2088 if (ic->op != '+' &&
2089 IC_LEFT (uic)->key != IC_RESULT (ic)->key)
2093 // this is too dangerous and need further restrictions
2096 /* if one of them is a literal then we can */
2097 if ((IC_LEFT (uic) && IS_OP_LITERAL (IC_LEFT (uic))) ||
2098 (IC_RIGHT (uic) && IS_OP_LITERAL (IC_RIGHT (uic))))
2100 OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2105 /* if the other one is not on stack then we can */
2106 if (IC_LEFT (uic)->key == IC_RESULT (ic)->key &&
2107 (IS_ITEMP (IC_RIGHT (uic)) ||
2108 (IS_TRUE_SYMOP (IC_RIGHT (uic)) &&
2109 !OP_SYMBOL (IC_RIGHT (uic))->onStack)))
2112 if (IC_RIGHT (uic)->key == IC_RESULT (ic)->key &&
2113 (IS_ITEMP (IC_LEFT (uic)) ||
2114 (IS_TRUE_SYMOP (IC_LEFT (uic)) &&
2115 !OP_SYMBOL (IC_LEFT (uic))->onStack)))
2121 OP_SYMBOL (IC_RESULT (ic))->accuse = 1;
2126 /*-----------------------------------------------------------------*/
2127 /* packForPush - hueristics to reduce iCode for pushing */
2128 /*-----------------------------------------------------------------*/
2130 packForPush (iCode * ic, eBBlock * ebp)
2135 if (ic->op != IPUSH || !IS_ITEMP (IC_LEFT (ic)))
2138 /* must have only definition & one usage */
2139 if (bitVectnBitsOn (OP_DEFS (IC_LEFT (ic))) != 1 ||
2140 bitVectnBitsOn (OP_USES (IC_LEFT (ic))) != 1)
2143 /* find the definition */
2144 if (!(dic = hTabItemWithKey (iCodehTab,
2145 bitVectFirstBit (OP_DEFS (IC_LEFT (ic))))))
2148 if (dic->op != '=' || POINTER_SET (dic))
2151 /* make sure the right side does not have any definitions
2153 dbv = OP_DEFS(IC_RIGHT(dic));
2154 for (lic = ic; lic && lic != dic ; lic = lic->prev) {
2155 if (bitVectBitValue(dbv,lic->key)) return ;
2157 /* make sure they have the same type */
2159 sym_link *itype=operandType(IC_LEFT(ic));
2160 sym_link *ditype=operandType(IC_RIGHT(dic));
2162 if (SPEC_USIGN(itype)!=SPEC_USIGN(ditype) ||
2163 SPEC_LONG(itype)!=SPEC_LONG(ditype))
2166 /* extend the live range of replaced operand if needed */
2167 if (OP_SYMBOL(IC_RIGHT(dic))->liveTo < ic->seq) {
2168 OP_SYMBOL(IC_RIGHT(dic))->liveTo = ic->seq;
2170 /* we now we know that it has one & only one def & use
2171 and the that the definition is an assignment */
2172 IC_LEFT (ic) = IC_RIGHT (dic);
2174 remiCodeFromeBBlock (ebp, dic);
2175 hTabDeleteItem (&iCodehTab, dic->key, dic, DELETE_ITEM, NULL);
2178 /*-----------------------------------------------------------------*/
2179 /* packRegisters - does some transformations to reduce register */
2181 /*-----------------------------------------------------------------*/
2183 packRegisters (eBBlock * ebp)
2193 /* look for assignments of the form */
2194 /* iTempNN = TRueSym (someoperation) SomeOperand */
2196 /* TrueSym := iTempNN:1 */
2197 for (ic = ebp->sch; ic; ic = ic->next)
2201 /* find assignment of the form TrueSym := iTempNN:1 */
2202 if (ic->op == '=' && !POINTER_SET (ic))
2203 change += packRegsForAssign (ic, ebp);
2210 for (ic = ebp->sch; ic; ic = ic->next)
2213 /* if this is an itemp & result of a address of a true sym
2214 then mark this as rematerialisable */
2215 if (ic->op == ADDRESS_OF &&
2216 IS_ITEMP (IC_RESULT (ic)) &&
2217 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
2218 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2219 !OP_SYMBOL (IC_LEFT (ic))->onStack)
2222 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2223 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2224 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2228 /* if straight assignment then carry remat flag if
2229 this is the only definition */
2230 if (ic->op == '=' &&
2231 !POINTER_SET (ic) &&
2232 IS_SYMOP (IC_RIGHT (ic)) &&
2233 OP_SYMBOL (IC_RIGHT (ic))->remat &&
2234 !IS_CAST_ICODE(OP_SYMBOL (IC_RIGHT (ic))->rematiCode) &&
2235 bitVectnBitsOn (OP_SYMBOL (IC_RESULT (ic))->defs) <= 1)
2238 OP_SYMBOL (IC_RESULT (ic))->remat =
2239 OP_SYMBOL (IC_RIGHT (ic))->remat;
2240 OP_SYMBOL (IC_RESULT (ic))->rematiCode =
2241 OP_SYMBOL (IC_RIGHT (ic))->rematiCode;
2244 /* if cast to a generic pointer & the pointer being
2245 cast is remat, then we can remat this cast as well */
2246 if (ic->op == CAST &&
2247 IS_SYMOP(IC_RIGHT(ic)) &&
2248 OP_SYMBOL(IC_RIGHT(ic))->remat ) {
2249 sym_link *to_type = operandType(IC_LEFT(ic));
2250 sym_link *from_type = operandType(IC_RIGHT(ic));
2251 if (IS_GENPTR(to_type) && IS_PTR(from_type)) {
2252 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2253 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2254 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2258 /* if this is a +/- operation with a rematerizable
2259 then mark this as rematerializable as well */
2260 if ((ic->op == '+' || ic->op == '-') &&
2261 (IS_SYMOP (IC_LEFT (ic)) &&
2262 IS_ITEMP (IC_RESULT (ic)) &&
2263 OP_SYMBOL (IC_LEFT (ic))->remat &&
2264 (!IS_SYMOP (IC_RIGHT (ic)) || !IS_CAST_ICODE(OP_SYMBOL (IC_RIGHT (ic))->rematiCode)) &&
2265 bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) == 1 &&
2266 IS_OP_LITERAL (IC_RIGHT (ic))))
2269 //int i = operandLitValue(IC_RIGHT(ic));
2270 OP_SYMBOL (IC_RESULT (ic))->remat = 1;
2271 OP_SYMBOL (IC_RESULT (ic))->rematiCode = ic;
2272 OP_SYMBOL (IC_RESULT (ic))->usl.spillLoc = NULL;
2275 /* mark the pointer usages */
2276 if (POINTER_SET (ic))
2277 OP_SYMBOL (IC_RESULT (ic))->uptr = 1;
2279 if (POINTER_GET (ic))
2280 OP_SYMBOL (IC_LEFT (ic))->uptr = 1;
2284 /* if we are using a symbol on the stack
2285 then we should say ds390_ptrRegReq */
2286 if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
2287 ds390_ptrRegReq += ((OP_SYMBOL (IC_COND (ic))->onStack ? !options.stack10bit : 0) +
2288 OP_SYMBOL (IC_COND (ic))->iaccess);
2289 else if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
2290 ds390_ptrRegReq += ((OP_SYMBOL (IC_JTCOND (ic))->onStack ? !options.stack10bit : 0) +
2291 OP_SYMBOL (IC_JTCOND (ic))->iaccess);
2294 if (IS_SYMOP (IC_LEFT (ic)))
2295 ds390_ptrRegReq += ((OP_SYMBOL (IC_LEFT (ic))->onStack ? !options.stack10bit : 0) +
2296 OP_SYMBOL (IC_LEFT (ic))->iaccess);
2297 if (IS_SYMOP (IC_RIGHT (ic)))
2298 ds390_ptrRegReq += ((OP_SYMBOL (IC_RIGHT (ic))->onStack ? !options.stack10bit : 0) +
2299 OP_SYMBOL (IC_RIGHT (ic))->iaccess);
2300 if (IS_SYMOP (IC_RESULT (ic)))
2301 ds390_ptrRegReq += ((OP_SYMBOL (IC_RESULT (ic))->onStack ? !options.stack10bit : 0) +
2302 OP_SYMBOL (IC_RESULT (ic))->iaccess);
2307 /* if the condition of an if instruction
2308 is defined in the previous instruction then
2309 mark the itemp as a conditional */
2310 if ((IS_CONDITIONAL (ic) ||
2311 (IS_BITWISE_OP(ic) && isBitwiseOptimizable(ic))) &&
2312 ic->next && ic->next->op == IFX &&
2313 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2314 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq)
2317 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2321 /* if the condition of an if instruction
2322 is defined in the previous instruction and
2323 this is the only usage then
2324 mark the itemp as a conditional */
2325 if ((IS_CONDITIONAL (ic) ||
2326 (IS_BITWISE_OP(ic) && isBitwiseOptimizable (ic))) &&
2327 ic->next && ic->next->op == IFX &&
2328 bitVectnBitsOn (OP_USES(IC_RESULT(ic)))==1 &&
2329 isOperandEqual (IC_RESULT (ic), IC_COND (ic->next)) &&
2330 OP_SYMBOL (IC_RESULT (ic))->liveTo <= ic->next->seq)
2332 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
2337 /* reduce for support function calls */
2338 if (ic->supportRtn || ic->op == '+' || ic->op == '-')
2339 packRegsForSupport (ic, ebp);
2341 /* some cases the redundant moves can
2342 can be eliminated for return statements */
2343 if ((ic->op == RETURN || ic->op == SEND) &&
2344 !isOperandInFarSpace (IC_LEFT (ic)) &&
2347 packRegsDPTRuse (ic, IC_LEFT (ic), ebp);
2350 /* if pointer set & left has a size more than
2351 one and right is not in far space */
2352 if (POINTER_SET (ic) &&
2353 !isOperandInFarSpace (IC_RIGHT (ic)) &&
2354 !OP_SYMBOL (IC_RESULT (ic))->remat &&
2355 !IS_OP_RUONLY (IC_RIGHT (ic)) &&
2356 getSize (aggrToPtr (operandType (IC_RESULT (ic)), FALSE)) > 1) {
2358 packRegsDPTRuse (ic, IC_RESULT (ic), ebp);
2361 /* if pointer get */
2362 if (POINTER_GET (ic) &&
2363 !isOperandInFarSpace (IC_RESULT (ic)) &&
2364 !OP_SYMBOL (IC_LEFT (ic))->remat &&
2365 !IS_OP_RUONLY (IC_RESULT (ic)) &&
2366 getSize (aggrToPtr (operandType (IC_LEFT (ic)), FALSE)) > 1) {
2368 packRegsDPTRuse (ic, IC_LEFT (ic), ebp);
2371 /* if this is cast for intergral promotion then
2372 check if only use of the definition of the
2373 operand being casted/ if yes then replace
2374 the result of that arithmetic operation with
2375 this result and get rid of the cast */
2378 sym_link *fromType = operandType (IC_RIGHT (ic));
2379 sym_link *toType = operandType (IC_LEFT (ic));
2381 if (IS_INTEGRAL (fromType) && IS_INTEGRAL (toType) &&
2382 getSize (fromType) != getSize (toType) &&
2383 SPEC_USIGN (fromType) == SPEC_USIGN (toType))
2386 iCode *dic = packRegsDPTRuse (ic, IC_RIGHT (ic), ebp);
2389 if (IS_ARITHMETIC_OP (dic))
2391 IC_RESULT (dic) = IC_RESULT (ic);
2392 remiCodeFromeBBlock (ebp, ic);
2393 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2394 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2398 OP_SYMBOL (IC_RIGHT (ic))->ruonly = 0;
2404 /* if the type from and type to are the same
2405 then if this is the only use then packit */
2406 if (compareType (operandType (IC_RIGHT (ic)),
2407 operandType (IC_LEFT (ic))) == 1)
2409 iCode *dic = packRegsDPTRuse (ic, IC_RIGHT (ic), ebp);
2412 IC_RESULT (dic) = IC_RESULT (ic);
2413 remiCodeFromeBBlock (ebp, ic);
2414 hTabDeleteItem (&iCodehTab, ic->key, ic, DELETE_ITEM, NULL);
2415 OP_DEFS (IC_RESULT (dic)) = bitVectSetBit (OP_DEFS (IC_RESULT (dic)), dic->key);
2423 iTempNN := (some variable in farspace) V1
2428 if (ic->op == IPUSH)
2430 packForPush (ic, ebp);
2434 /* pack registers for accumulator use, when the
2435 result of an arithmetic or bit wise operation
2436 has only one use, that use is immediately following
2437 the defintion and the using iCode has only one
2438 operand or has two operands but one is literal &
2439 the result of that operation is not on stack then
2440 we can leave the result of this operation in acc:b
2442 if ((IS_ARITHMETIC_OP (ic)
2443 || IS_CONDITIONAL(ic)
2444 || IS_BITWISE_OP (ic)
2445 || ic->op == LEFT_OP || ic->op == RIGHT_OP || ic->op == CALL
2446 || (ic->op == ADDRESS_OF && isOperandOnStack (IC_LEFT (ic)))
2448 IS_ITEMP (IC_RESULT (ic)) &&
2449 getSize (operandType (IC_RESULT (ic))) <= 2)
2451 packRegsForAccUse (ic);
2456 /*-----------------------------------------------------------------*/
2457 /* assignRegisters - assigns registers to each live range as need */
2458 /*-----------------------------------------------------------------*/
2460 ds390_assignRegisters (eBBlock ** ebbs, int count)
2465 setToNull ((void *) &_G.funcrUsed);
2466 ds390_ptrRegReq = _G.stackExtend = _G.dataExtend = 0;
2468 if (options.model != MODEL_FLAT24) options.stack10bit = 0;
2469 /* change assignments this will remove some
2470 live ranges reducing some register pressure */
2471 for (i = 0; i < count; i++)
2472 packRegisters (ebbs[i]);
2474 if (options.dump_pack)
2475 dumpEbbsToFileExt (DUMP_PACK, ebbs, count);
2477 /* first determine for each live range the number of
2478 registers & the type of registers required for each */
2481 /* and serially allocate registers */
2482 serialRegAssign (ebbs, count);
2484 /* if stack was extended then tell the user */
2487 /* werror(W_TOOMANY_SPILS,"stack", */
2488 /* _G.stackExtend,currFunc->name,""); */
2494 /* werror(W_TOOMANY_SPILS,"data space", */
2495 /* _G.dataExtend,currFunc->name,""); */
2499 /* after that create the register mask
2500 for each of the instruction */
2501 createRegMask (ebbs, count);
2503 /* redo that offsets for stacked automatic variables */
2504 redoStackOffsets ();
2506 if (options.dump_rassgn) {
2507 dumpEbbsToFileExt (DUMP_RASSGN, ebbs, count);
2508 dumpLiveRanges (DUMP_LRANGE, liveRanges);
2511 /* do the overlaysegment stuff SDCCmem.c */
2512 doOverlays (ebbs, count);
2514 /* now get back the chain */
2515 ic = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
2520 /* free up any _G.stackSpil locations allocated */
2521 applyToSet (_G.stackSpil, deallocStackSpil);
2523 setToNull ((void **) &_G.stackSpil);
2524 setToNull ((void **) &_G.spiltSet);
2525 /* mark all registers as free */