1 /*-------------------------------------------------------------------------
2 SDCCcse.c - source file for Common Subexpressions and other utility
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 In other words, you are welcome to use, share and improve this program.
21 You are forbidden to forbid anyone else to use, share and improve
22 what you give them. Help stamp out software-hoarding!
23 -------------------------------------------------------------------------*/
27 /*-----------------------------------------------------------------*/
28 /* newCseDef - new cseDef */
29 /*-----------------------------------------------------------------*/
30 cseDef *newCseDef (operand *sym, iCode *ic)
35 ALLOC(cdp,sizeof(cseDef));
46 /*-----------------------------------------------------------------*/
47 /* int isCseDefEqual - two definitions are equal */
48 /*-----------------------------------------------------------------*/
49 int isCseDefEqual ( void *vsrc, void *vdest)
57 return (src->key == dest->key &&
58 src->diCode == dest->diCode ) ;
62 /*-----------------------------------------------------------------*/
63 /* pcseDef - in the cseDef */
64 /*-----------------------------------------------------------------*/
65 int pcseDef (void *item, va_list ap)
73 fprintf(stdout,"**null op**");
74 printOperand(cdp->sym,stdout);
75 icTab = getTableEntry(cdp->diCode->op) ;
76 icTab->iCodePrint(stdout,cdp->diCode,icTab->printName);
80 /*-----------------------------------------------------------------*/
81 /* replaceAllSymBySym - replaces all operands by operand in an */
82 /* instruction chain */
83 /*-----------------------------------------------------------------*/
84 void replaceAllSymBySym (iCode *ic, operand *from , operand *to, bitVect **ndpset)
88 for (lic = ic ; lic ; lic = lic->next ) {
91 /* do the special cases first */
94 IC_COND(lic)->key == from->key) {
96 bitVectUnSetBit (OP_USES(from),lic->key);
97 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
98 siaddr = IC_COND(lic)->isaddr ;
99 IC_COND(lic) = operandFromOperand(to);
100 IC_COND(lic)->isaddr = siaddr ;
106 if (lic->op == JUMPTABLE) {
108 IC_JTCOND(lic)->key == from->key) {
110 bitVectUnSetBit (OP_USES(from),lic->key);
111 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
112 siaddr = IC_COND(lic)->isaddr ;
113 IC_JTCOND(lic) = operandFromOperand(to);
114 IC_JTCOND(lic)->isaddr = siaddr ;
120 if (IC_RESULT(lic) && IC_RESULT(lic)->key == from->key ) {
121 /* maintain du chains */
122 if (POINTER_SET(lic)) {
123 bitVectUnSetBit (OP_USES(from),lic->key);
124 OP_USES(to) = bitVectSetBit (OP_USES(to),lic->key);
126 /* also check if the "from" was in the non-dominating
127 pointer sets and replace it with "to" in the bitVector */
128 if (bitVectBitValue(*ndpset,from->key)) {
129 bitVectUnSetBit(*ndpset,from->key);
130 bitVectSetBit(*ndpset,to->key);
135 bitVectUnSetBit (OP_DEFS(from),lic->key);
136 OP_DEFS(to) = bitVectSetBit (OP_DEFS(to),lic->key);
138 siaddr = IC_RESULT(lic)->isaddr ;
139 IC_RESULT(lic) = operandFromOperand(to);
140 IC_RESULT(lic)->isaddr = siaddr ;
144 IC_RIGHT(lic) && IC_RIGHT(lic)->key == from->key ) {
145 bitVectUnSetBit (OP_USES(from),lic->key);
146 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
147 siaddr = IC_RIGHT(lic)->isaddr ;
148 IC_RIGHT(lic) = operandFromOperand(to);
149 IC_RIGHT(lic)->isaddr = siaddr ;
153 IC_LEFT(lic) && IC_LEFT(lic)->key == from->key ) {
154 bitVectUnSetBit (OP_USES(from),lic->key);
155 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
156 siaddr = IC_LEFT(lic)->isaddr ;
157 IC_LEFT(lic) = operandFromOperand(to);
158 IC_LEFT(lic)->isaddr = siaddr ;
163 /*-----------------------------------------------------------------*/
164 /* iCodeKeyIs - if the icode keys match then return 1 */
165 /*-----------------------------------------------------------------*/
166 DEFSETFUNC(iCodeKeyIs)
171 if (cdp->diCode->key == key)
177 /*-----------------------------------------------------------------*/
178 /* removeFromInExprs - removes an icode from inexpressions */
179 /*-----------------------------------------------------------------*/
180 DEFSETFUNC(removeFromInExprs)
184 V_ARG(operand *,from);
186 V_ARG(eBBlock *,cbp);
192 deleteItemIf(&ebp->inExprs,iCodeKeyIs,ic->key);
193 if (ebp != cbp && !bitVectBitValue(cbp->domVect,ebp->bbnum))
194 replaceAllSymBySym(ebp->sch,from,to,&ebp->ndompset);
196 applyToSet(ebp->succList,removeFromInExprs,ic,from,to,cbp);
200 /*-----------------------------------------------------------------*/
201 /* isGlobalInNearSpace - return TRUE if valriable is a globalin data */
202 /*-----------------------------------------------------------------*/
203 static bool isGlobalInNearSpace (operand *op)
205 link *type = getSpec(operandType(op));
206 /* this is 8051 specific: optimization
207 suggested by Jean-Louis VERN, with 8051s we have no
208 advantage of putting variables in near space into
210 if (isOperandGlobal(op) &&
211 IN_DIRSPACE(SPEC_OCLS(type)))
217 /*-----------------------------------------------------------------*/
218 /* findCheaperOp - cseBBlock support routine, will check to see if */
219 /* we have a operand previously defined */
220 /*-----------------------------------------------------------------*/
221 DEFSETFUNC(findCheaperOp)
224 V_ARG(operand *,cop);
225 V_ARG(operand **,opp);
227 /* if we have already found it */
231 /* not found it yet check if this is the one */
232 /* and this is not the defining one */
233 if (cop->key == cdp->key) {
235 /* do a special check this will help in */
236 /* constant propagation & dead code elim*/
237 /* for assignments only */
238 if (cdp->diCode->op == '=') {
239 /* if the result is volatile then return result */
240 if (IS_OP_VOLATILE (IC_RESULT(cdp->diCode)))
241 *opp = IC_RESULT(cdp->diCode);
243 /* if this is a straight assignment and
244 left is a temp then prefer the temporary to the
246 if (!POINTER_SET(cdp->diCode) &&
247 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
248 IS_TRUE_SYMOP(IC_RIGHT(cdp->diCode)))
249 *opp = IC_RESULT(cdp->diCode);
251 /* if straight assignement && and both
252 are temps then prefer the one that
253 will not need extra space to spil, also
254 take into consideration if right side
255 an induction variable
257 if (!POINTER_SET(cdp->diCode) &&
258 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
259 IS_ITEMP(IC_RIGHT(cdp->diCode)) &&
260 !OP_SYMBOL(IC_RIGHT(cdp->diCode))->isind &&
261 ( (!SPIL_LOC(IC_RIGHT(cdp->diCode)) &&
262 SPIL_LOC(IC_RESULT(cdp->diCode))) ||
263 ( SPIL_LOC(IC_RESULT(cdp->diCode)) &&
264 SPIL_LOC(IC_RESULT(cdp->diCode)) ==
265 SPIL_LOC(IC_RIGHT(cdp->diCode))) )
267 *opp = IC_RESULT(cdp->diCode);
269 *opp = IC_RIGHT(cdp->diCode);
272 *opp = IC_RESULT(cdp->diCode) ;
275 /* if this is an assign to a temp. then check
276 if the right side is this then return this */
277 if (IS_TRUE_SYMOP(cop) &&
278 cdp->diCode->op == '=' &&
279 !POINTER_SET(cdp->diCode) &&
280 cop->key == IC_RIGHT(cdp->diCode)->key &&
281 !isGlobalInNearSpace (IC_RIGHT(cdp->diCode)) &&
282 IS_ITEMP(IC_RESULT(cdp->diCode)))
283 *opp = IC_RESULT(cdp->diCode);
287 if ((isGlobalInNearSpace(cop) &&
288 !isOperandLiteral(*opp)) ||
289 isOperandVolatile(*opp,FALSE)
295 if (cop->key == (*opp)->key ) {
300 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP(cop)) {
301 *opp = operandFromOperand(*opp);
302 (*opp)->isaddr = cop->isaddr;
312 /*-----------------------------------------------------------------*/
313 /* findPointerSet - finds the right side of a pointer set op */
314 /*-----------------------------------------------------------------*/
315 DEFSETFUNC(findPointerSet)
319 V_ARG(operand **,opp);
320 V_ARG(operand *,rop);
322 if (POINTER_SET(cdp->diCode) &&
323 IC_RESULT(cdp->diCode)->key == op->key &&
324 !isOperandVolatile(IC_RESULT(cdp->diCode),TRUE) &&
325 !isOperandVolatile(IC_RIGHT(cdp->diCode),TRUE) &&
326 getSize(operandType(IC_RIGHT(cdp->diCode))) ==
327 getSize(operandType(rop))) {
328 *opp = IC_RIGHT(cdp->diCode);
335 /*-----------------------------------------------------------------*/
336 /* findPrevIc - cseBBlock support function will return the iCode */
337 /* which matches the current one */
338 /*-----------------------------------------------------------------*/
339 DEFSETFUNC(findPrevIc)
345 /* if already found */
349 /* if the iCodes are the same */
350 if (isiCodeEqual(ic,cdp->diCode) &&
351 isOperandEqual(cdp->sym,IC_RESULT(cdp->diCode))) {
356 /* if iCodes are not the same */
357 /* see the operands maybe interchanged */
358 if (ic->op == cdp->diCode->op &&
359 ( ic->op == '+' || ic->op == '*' ) &&
360 isOperandEqual(IC_LEFT(ic),IC_RIGHT(cdp->diCode)) &&
361 isOperandEqual(IC_RIGHT(ic),IC_LEFT(cdp->diCode))) {
369 /*-----------------------------------------------------------------*/
370 /* ifDefGlobal - if definition is global */
371 /*-----------------------------------------------------------------*/
372 DEFSETFUNC(ifDefGlobal)
376 return (isOperandGlobal(cdp->sym));
379 /*-----------------------------------------------------------------*/
380 /* ifOperandsHave - if any of the operand are the same as this */
381 /*-----------------------------------------------------------------*/
382 DEFSETFUNC(ifOperandsHave)
388 if (IC_LEFT(cdp->diCode) &&
389 IS_SYMOP(IC_LEFT(cdp->diCode)) &&
390 IC_LEFT(cdp->diCode)->key == op->key)
393 if (IC_RIGHT(cdp->diCode) &&
394 IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
395 IC_RIGHT(cdp->diCode)->key == op->key)
398 /* or if any of the operands are volatile */
399 if (IC_LEFT(cdp->diCode) &&
400 IS_OP_VOLATILE(IC_LEFT(cdp->diCode)))
403 if (IC_RIGHT(cdp->diCode) &&
404 IS_OP_VOLATILE(IC_RIGHT(cdp->diCode)))
408 if (IC_RESULT(cdp->diCode) &&
409 IS_OP_VOLATILE(IC_RESULT(cdp->diCode)))
415 /*-----------------------------------------------------------------*/
416 /* ifDefSymIs - if a definition is found in the set */
417 /*-----------------------------------------------------------------*/
418 int ifDefSymIs (set *cseSet, operand *sym)
423 if (!sym || !IS_SYMOP(sym))
425 for (sl = cseSet ; sl ; sl = sl->next ) {
427 if (loop->sym->key == sym->key )
434 /*-----------------------------------------------------------------*/
435 /* ifDefSymIsX - will return 1 if the symbols match */
436 /*-----------------------------------------------------------------*/
437 DEFSETFUNC(ifDefSymIsX)
443 return cdp->sym->key == op->key ;
445 return ( isOperandEqual(cdp->sym,op) );
450 /*-----------------------------------------------------------------*/
451 /* ifDiCodeIs - returns truw if diCode is same */
452 /*-----------------------------------------------------------------*/
453 int ifDiCodeIs (set *cseSet, iCode *ic)
461 for (sl = cseSet ; sl ; sl = sl->next ) {
463 if (loop->diCode == ic)
470 /*-----------------------------------------------------------------*/
471 /* ifPointerGet - returns true if the icode is pointer get sym */
472 /*-----------------------------------------------------------------*/
473 DEFSETFUNC(ifPointerGet)
477 iCode *dic = cdp->diCode;
478 operand *left = IC_LEFT(cdp->diCode);
480 if (POINTER_GET(dic) && left->key == op->key)
486 /*-----------------------------------------------------------------*/
487 /* ifPointerSet - returns true if the icode is pointer set sym */
488 /*-----------------------------------------------------------------*/
489 DEFSETFUNC(ifPointerSet)
494 if (POINTER_SET(cdp->diCode) &&
495 IC_RESULT(cdp->diCode)->key == op->key)
501 /*-----------------------------------------------------------------*/
502 /* ifDiCodeIsX - will return 1 if the symbols match */
503 /*-----------------------------------------------------------------*/
504 DEFSETFUNC(ifDiCodeIsX)
509 return cdp->diCode == ic;
513 /*-----------------------------------------------------------------*/
514 /* algebraicOpts - does some algebraic optimizations */
515 /*-----------------------------------------------------------------*/
516 void algebraicOpts (iCode *ic)
518 /* we don't deal with the following iCodes
529 /* if both operands present & ! IFX */
530 /* then if they are both literal we */
531 /* perform the operation right now */
535 IS_OP_LITERAL(IC_LEFT(ic)) &&
536 IS_OP_LITERAL(IC_RIGHT(ic))) {
538 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
541 operandType(IC_RESULT(ic)));
544 SET_RESULT_RIGHT(ic);
548 /* if not ifx & only one operand present */
551 IS_OP_LITERAL(IC_LEFT(ic)) &&
554 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
557 operandType(IC_RESULT(ic)));
560 SET_RESULT_RIGHT(ic);
565 /* a special case : or in short a kludgy solution will think
566 about a better solution over a glass of wine someday */
567 if ( ic->op == GET_VALUE_AT_ADDRESS ) {
569 if (IS_ITEMP(IC_RESULT(ic)) &&
570 IS_TRUE_SYMOP(IC_LEFT(ic))) {
573 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
574 IC_RIGHT(ic)->isaddr = 0;
576 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
577 IC_RESULT(ic)->isaddr = 0;
578 setOperandType(IC_RESULT(ic),operandType(IC_RIGHT(ic)));
582 if (IS_ITEMP(IC_LEFT(ic)) &&
583 IS_ITEMP(IC_RESULT(ic)) &&
584 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
585 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
586 !IC_LEFT(ic)->isaddr ) {
588 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
589 IC_RIGHT(ic)->isaddr = 0;
590 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
591 IC_RESULT(ic)->isaddr = 0;
599 /* depending on the operation */
602 /* if adding the same thing change to left shift by 1*/
603 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key &&
604 !IS_FLOAT(operandType(IC_RESULT(ic)))) {
606 IC_RIGHT(ic) = operandFromLit(1);
609 /* if addition then check if one of them is a zero */
610 /* if yes turn it into assignmnt*/
611 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
612 operandLitValue(IC_LEFT(ic)) == 0.0 ) {
616 SET_ISADDR(IC_RESULT(ic),0);
617 SET_ISADDR(IC_RIGHT(ic),0);
620 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
621 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
624 IC_RIGHT(ic) = IC_LEFT(ic) ;
626 SET_ISADDR(IC_RIGHT(ic),0);
627 SET_ISADDR(IC_RESULT(ic),0);
632 /* if subtracting the the same thing then zero */
633 if ( IC_LEFT(ic)->key == IC_RIGHT(ic)->key ) {
635 IC_RIGHT(ic) = operandFromLit(0);
637 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
638 IC_RESULT(ic)->isaddr = 0;
642 /* if subtraction then check if one of the operand */
643 /* is zero then depending on which operand change */
644 /* to assignment or unary minus */
645 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
646 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
647 /* right size zero change to assignment */
649 IC_RIGHT(ic) = IC_LEFT(ic);
651 SET_ISADDR(IC_RIGHT(ic),0);
652 SET_ISADDR(IC_RESULT(ic),0);
655 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
656 operandLitValue (IC_LEFT(ic)) == 0.0) {
657 /* left zero turn into an unary minus */
658 ic->op = UNARYMINUS ;
659 IC_LEFT(ic) = IC_RIGHT(ic);
660 IC_RIGHT(ic) = NULL ;
664 /* if multiplication then check if either of */
665 /* them is zero then the result is zero */
666 /* if either of them is one then result is */
669 if (IS_OP_LITERAL(IC_LEFT(ic))) {
671 if (operandLitValue(IC_LEFT(ic)) == 0.0) {
673 IC_RIGHT(ic) = IC_LEFT(ic);
675 SET_RESULT_RIGHT(ic);
678 if ( operandLitValue(IC_LEFT(ic)) == 1.0) {
681 SET_RESULT_RIGHT(ic);
686 if (IS_OP_LITERAL(IC_RIGHT(ic))) {
688 if (operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
691 SET_RESULT_RIGHT(ic);
695 if (operandLitValue(IC_RIGHT(ic)) == 1.0) {
697 IC_RIGHT(ic) = IC_LEFT(ic);
699 SET_RESULT_RIGHT(ic);
705 /* if division by self then 1 */
706 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key) {
708 IC_RIGHT(ic) = operandFromLit(1);
710 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
711 IC_RESULT(ic)->isaddr = 0;
713 /* if this is a division then check if right */
714 /* is one then change it to an assignment */
715 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
716 operandLitValue(IC_RIGHT(ic)) == 1.0 ) {
719 IC_RIGHT(ic) = IC_LEFT(ic);
721 SET_RESULT_RIGHT(ic);
725 /* if both are the same for an comparison operators */
729 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
731 IC_RIGHT(ic) = operandFromLit(1);
733 SET_RESULT_RIGHT(ic);
739 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
741 IC_RIGHT(ic) = operandFromLit(0);
743 SET_RESULT_RIGHT(ic);
747 /* if this is a cast of a literal value */
748 if ( IS_OP_LITERAL(IC_RIGHT(ic))) {
751 operandFromValue (valCastLiteral(operandType(IC_LEFT(ic)),
752 operandLitValue(IC_RIGHT(ic))));
754 SET_ISADDR(IC_RESULT(ic),0);
756 /* if casting to the same */
757 if ( checkType(operandType(IC_RESULT(ic)),
758 operandType(IC_RIGHT(ic))) == 1) {
761 SET_ISADDR(IC_RESULT(ic),0);
765 if (IS_OP_LITERAL(IC_LEFT(ic))) {
768 (operandLitValue(IC_LEFT(ic)) == 0 ?
769 operandFromLit(1) : operandFromLit(0));
771 SET_ISADDR(IC_RESULT(ic),0);
777 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
778 /*-----------------------------------------------------------------*/
779 /* updateSpillLocation - keeps track of register spill location */
780 /*-----------------------------------------------------------------*/
781 void updateSpillLocation ( iCode *ic)
792 /* for the form true_symbol := iTempNN */
793 if (ASSIGN_ITEMP_TO_SYM(ic)
794 && !SPIL_LOC(IC_RIGHT(ic))) {
796 setype = getSpec(operandType(IC_RESULT(ic)));
798 if (!IC_RIGHT(ic)->noSpilLoc &&
799 !IS_VOLATILE(setype) &&
800 !IN_FARSPACE(SPEC_OCLS(setype)) &&
801 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
803 SPIL_LOC(IC_RIGHT(ic)) =
804 IC_RESULT(ic)->operand.symOperand;
807 if (ASSIGN_ITEMP_TO_ITEMP(ic) &&
808 !SPIL_LOC(IC_RIGHT(ic)) &&
809 !bitVectBitsInCommon(OP_DEFS(IC_RIGHT(ic)),OP_USES(IC_RESULT(ic))) &&
810 OP_SYMBOL(IC_RESULT(ic))->isreqv) {
812 setype = getSpec(operandType(IC_RESULT(ic)));
814 if (!IC_RIGHT(ic)->noSpilLoc &&
815 !IS_VOLATILE(setype) &&
816 !IN_FARSPACE(SPEC_OCLS(setype)) &&
817 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
819 SPIL_LOC(IC_RIGHT(ic)) =
820 SPIL_LOC(IC_RESULT(ic));
824 /*-----------------------------------------------------------------*/
825 /* setUsesDef - sets the uses def bitvector for a given operand */
826 /*-----------------------------------------------------------------*/
827 void setUsesDefs (operand *op, bitVect *bdefs,
828 bitVect *idefs, bitVect **oud)
830 /* compute the definitions alive at this point */
831 bitVect *adefs = bitVectUnion(bdefs,idefs);
833 /* of these definitions find the ones that are */
834 /* for this operand */
835 adefs = bitVectIntersect(adefs,OP_DEFS(op));
837 /* these are the definitions that this operand can use */
838 op->usesDefs = adefs;
840 /* the out defs is an union */
841 *oud = bitVectUnion(*oud,adefs);
844 /*-----------------------------------------------------------------*/
845 /* unsetDefsAndUses - clear this operation for the operands */
846 /*-----------------------------------------------------------------*/
847 void unsetDefsAndUses ( iCode *ic )
849 if ( ic->op == JUMPTABLE)
852 /* take away this definition from the def chain of the */
853 /* result & take away from use set of the operands */
855 /* turn off def set */
856 if (IS_SYMOP(IC_RESULT(ic))) {
857 if ( !POINTER_SET(ic))
858 bitVectUnSetBit(OP_DEFS(IC_RESULT(ic)),ic->key);
860 bitVectUnSetBit(OP_USES(IC_RESULT(ic)),ic->key);
862 /* turn off the useSet for the operands */
863 if (IS_SYMOP(IC_LEFT(ic)))
864 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
866 if (IS_SYMOP(IC_RIGHT(ic)))
867 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
869 else /* must be ifx turn off the use */
870 if (IS_SYMOP(IC_COND(ic)))
871 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
874 /*-----------------------------------------------------------------*/
875 /* ifxOptimize - changes ifx conditions if it can */
876 /*-----------------------------------------------------------------*/
877 void ifxOptimize (iCode *ic, set *cseSet,
879 eBBlock *ebb, int *change,
880 eBBlock **ebbs, int count)
885 /* if the condition can be replaced */
888 applyToSetFTrue (cseSet,findCheaperOp,IC_COND(ic),&pdop);
895 /* if the conditional is a literal then */
896 if (IS_OP_LITERAL(IC_COND(ic))) {
898 if ( (operandLitValue(IC_COND(ic)) != 0.0) && IC_TRUE(ic)) {
900 /* change to a goto */
902 IC_LABEL(ic) = IC_TRUE(ic);
907 if (!operandLitValue(IC_COND(ic)) && IC_FALSE(ic)) {
909 IC_LABEL(ic) = IC_FALSE(ic);
913 /* then kill this if condition */
914 remiCodeFromeBBlock (ebb,ic);
918 /* now we need to recompute the control flow */
919 /* since the control flow has changed */
920 /* this is very expensive but it does not happen */
921 /* too often, if it does happen then the user pays */
923 computeControlFlow (ebbs,count,1);
924 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
928 /* if there is only one successor and that successor
929 is the same one we are conditionally going to then
930 we can remove this conditional statement */
931 label = (IC_TRUE(ic) ? IC_TRUE(ic) : IC_FALSE(ic));
932 if (elementsInSet(ebb->succList) == 1 &&
933 isinSet(ebb->succList,eBBWithEntryLabel(ebbs,label,count))) {
935 remiCodeFromeBBlock(ebb,ic);
936 computeControlFlow (ebbs,count,1);
937 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
942 /* if it remains an IFX the update the use Set */
943 OP_USES(IC_COND(ic)) = bitVectSetBit(OP_USES(IC_COND(ic)),ic->key);
944 setUsesDefs(IC_COND(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
948 /*-----------------------------------------------------------------*/
949 /* diCodeForSym - finds the definiting instruction for a symbol */
950 /*-----------------------------------------------------------------*/
951 DEFSETFUNC(diCodeForSym)
954 V_ARG(operand *,sym);
957 /* if already found */
961 /* if not if this is the defining iCode */
962 if (sym->key == cdp->key) {
970 /*-----------------------------------------------------------------*/
971 /* constFold - does some constant folding */
972 /*-----------------------------------------------------------------*/
973 int constFold (iCode *ic, set *cseSet)
977 /* this routine will change
983 /* deal with only + & - */
988 /* this check is a hueristic to prevent live ranges
989 from becoming too long */
990 if (IS_PTR(operandType(IC_RESULT(ic))))
993 /* check if operation with a literal */
994 if (!IS_OP_LITERAL(IC_RIGHT(ic)))
997 /* check if we can find a definition for the
999 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(ic),&dic)))
1002 /* check that this is also a +/- */
1003 if (dic->op != '+' && dic->op != '-')
1006 /* with a literal */
1007 if (!IS_OP_LITERAL(IC_RIGHT(dic)))
1010 /* find the definition of the left operand
1011 of dic.then check if this defined with a
1012 get_pointer return 0 if the pointer size is
1013 less than 2 (MCS51 specific) */
1014 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(dic),&ldic)))
1017 if (POINTER_GET(ldic) && getSize(operandType(IC_LEFT(ldic))) <= 1)
1020 /* it is if the operations are the same*/
1021 /* the literal parts need to be added */
1022 IC_LEFT(ic) = operandFromOperand(IC_LEFT(dic));
1023 if (ic->op == dic->op )
1024 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic))+
1025 operandLitValue(IC_RIGHT(dic)));
1027 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) -
1028 operandLitValue(IC_RIGHT(dic)));
1030 if (IS_ITEMP(IC_RESULT(ic))) {
1031 SPIL_LOC(IC_RESULT(ic)) = NULL;
1032 IC_RESULT(ic)->noSpilLoc = 1;
1039 /*-----------------------------------------------------------------*/
1040 /* deleteGetPointers - called when a pointer is passed as parm */
1041 /* will delete from cseSet all get pointers computed from this */
1042 /* pointer. A simple ifOperandsHave is not good enough here */
1043 /*-----------------------------------------------------------------*/
1044 static void deleteGetPointers (set **cseSet, set **pss, operand *op,eBBlock *ebb)
1046 set *compItems = NULL;
1051 if (!*cseSet && !*pss)
1054 /* first find all items computed from this operand .
1055 This done fairly simply go thru the list and find
1056 those that are computed by arthimetic with this
1058 for (cdp = setFirstItem(*cseSet); cdp ; cdp = setNextItem(*cseSet)) {
1059 if (IS_ARITHMETIC_OP(cdp->diCode)) {
1060 if (isOperandEqual(IC_LEFT(cdp->diCode),op) ||
1061 isOperandEqual(IC_RIGHT(cdp->diCode),op)) {
1062 /* save it in our list of items */
1063 addSet(&compItems,IC_RESULT(cdp->diCode));
1065 /* also check for those computed from our computed
1066 list . This will take care of situations like
1067 iTemp1 = iTemp0 + 8;
1068 iTemp2 = iTemp1 + 8; */
1069 if (isinSetWith(compItems,IC_LEFT(cdp->diCode),isOperandEqual) ||
1070 isinSetWith(compItems,IC_RIGHT(cdp->diCode),isOperandEqual)) {
1071 addSet(&compItems,IC_RESULT(cdp->diCode));
1076 /* now delete all pointer gets with this op */
1077 deleteItemIf(cseSet,ifPointerGet,op);
1078 deleteItemIf(pss,ifPointerSet,op);
1080 /* set the bit vector used by dataFlow computation later */
1081 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,op->key);
1082 /* now for the computed items */
1083 for (cop = setFirstItem(compItems); cop ; cop = setNextItem(compItems)) {
1084 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,cop->key);
1085 deleteItemIf(cseSet,ifPointerGet,cop);
1086 deleteItemIf(pss,ifPointerSet,cop);
1090 /*-----------------------------------------------------------------*/
1091 /* delGetPointerSucc - delete get pointer from inExprs of succ with*/
1092 /* dfnum > supplied */
1093 /*-----------------------------------------------------------------*/
1094 DEFSETFUNC(delGetPointerSucc)
1096 eBBlock *ebp = item;
1097 V_ARG(operand *,op);
1104 if (ebp->dfnum > dfnum) {
1105 deleteItemIf(&ebp->inExprs,ifPointerGet,op);
1108 return applyToSet(ebp->succList,delGetPointerSucc,op,dfnum);
1111 /*-----------------------------------------------------------------*/
1112 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1113 /*-----------------------------------------------------------------*/
1114 static void fixUpTypes(iCode *ic)
1116 link *t1 = operandType(IC_LEFT(ic)) ,*t2;
1118 extern PORT ds390_port;
1120 if (port == &ds390_port)
1126 /* for pointer_gets if the types of result & left r the
1127 same then change it type of result to next */
1129 checkType(t2=operandType(IC_RESULT(ic)),t1) == 1) {
1130 setOperandType(IC_RESULT(ic),t2->next);
1134 /*-----------------------------------------------------------------*/
1135 /* cseBBlock - common subexpression elimination for basic blocks */
1136 /* this is the hackiest kludgiest routine in the whole */
1137 /* system. also the most important, since almost all */
1138 /* data flow related information is computed by it */
1139 /*-----------------------------------------------------------------*/
1140 int cseBBlock ( eBBlock *ebb, int computeOnly,
1141 eBBlock **ebbs, int count)
1147 set *ptrSetSet = NULL;
1149 /* if this block is not reachable */
1153 /* set of common subexpressions */
1154 cseSet = setFromSet (ebb->inExprs) ;
1156 /* these will be computed by this routine */
1157 setToNull ((void **)&ebb->outDefs);
1158 setToNull ((void **)&ebb->defSet);
1159 setToNull ((void **)&ebb->usesDefs);
1160 setToNull ((void **)&ebb->ptrsSet);
1161 setToNull ((void **)&ebb->addrOf);
1162 setToNull ((void **)&ebb->ldefs);
1164 ebb->outDefs = bitVectCopy (ebb->inDefs);
1165 bitVectDefault = iCodeKey;
1166 ebb->defSet = newBitVect(iCodeKey);
1167 ebb->usesDefs=newBitVect(iCodeKey);
1169 /* for all the instructions in this block do */
1170 for (ic = ebb->sch ; ic ; ic = ic->next ) {
1179 /* if this is an assignment from true symbol
1180 to a temp then do pointer post inc/dec optimzation */
1181 if (ic->op == '=' && !POINTER_SET(ic) &&
1182 IS_PTR(operandType(IC_RESULT(ic)))) {
1183 ptrPostIncDecOpt(ic);
1186 /* clear the def & use chains for the operands involved */
1187 /* in this operation . since it can change due to opts */
1188 unsetDefsAndUses (ic);
1190 if ( ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE) {
1191 /* add to defSet of the symbol */
1192 OP_DEFS(IC_RESULT(ic)) =
1193 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1194 /* add to the definition set of this block */
1195 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1196 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1197 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1198 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1199 /* delete global variables from the cseSet
1200 since they can be modified by the function call */
1201 deleteItemIf(&cseSet,ifDefGlobal);
1204 /* for pcall & ipush we need to add to the useSet */
1205 if ((ic->op == PCALL ||
1209 IS_SYMOP(IC_LEFT(ic))) {
1211 /* check if they can be replaced */
1212 if ( !computeOnly ) {
1214 applyToSetFTrue(cseSet,findCheaperOp,IC_LEFT(ic),&pdop);
1216 IC_LEFT(ic) = pdop ;
1218 /* the lookup could have changed it*/
1219 if (IS_SYMOP(IC_LEFT(ic))) {
1220 OP_USES(IC_LEFT(ic)) =
1221 bitVectSetBit(OP_USES(IC_LEFT(ic)),ic->key);
1222 setUsesDefs(IC_LEFT(ic),ebb->defSet,
1223 ebb->outDefs,&ebb->usesDefs);
1227 /* if we a sending a pointer as a parameter
1228 then kill all cse since the pointed to item
1229 might be changed in the function being called */
1230 if ((ic->op == IPUSH || ic->op == SEND) &&
1231 IS_PTR(operandType(IC_LEFT(ic)))) {
1232 deleteGetPointers(&cseSet,&ptrSetSet,IC_LEFT(ic),ebb);
1233 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_LEFT(ic)->key);
1234 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1235 applyToSet(ebb->succList,delGetPointerSucc,
1236 IC_LEFT(ic),ebb->dfnum);
1241 /* if jumptable then mark the usage */
1242 if (ic->op == JUMPTABLE ) {
1243 OP_USES(IC_JTCOND(ic)) =
1244 bitVectSetBit(OP_USES(IC_JTCOND(ic)),ic->key);
1245 setUsesDefs(IC_JTCOND(ic),ebb->defSet,
1246 ebb->outDefs,&ebb->usesDefs);
1253 /* do some algebraic optimizations if possible */
1255 while (constFold(ic,cseSet));
1258 if (POINTER_GET(ic) && !IS_PTR(operandType(IC_LEFT(ic)))) {
1259 setOperandType(IC_LEFT(ic),
1260 aggrToPtr(operandType(IC_LEFT(ic)),FALSE));
1264 if (POINTER_SET(ic) && !IS_PTR(operandType(IC_RESULT(ic)))) {
1265 setOperandType(IC_RESULT(ic),
1266 aggrToPtr(operandType(IC_RESULT(ic)),FALSE));
1269 /* if this is a condition statment then */
1270 /* check if the condition can be replaced */
1271 if (ic->op == IFX ) {
1272 ifxOptimize (ic, cseSet, computeOnly,
1278 /* if the assignment & result is a temp */
1279 /* see if we can replace it */
1280 if (ic->op == '=') {
1282 /* update the spill location for this */
1283 updateSpillLocation (ic);
1285 if (POINTER_SET(ic)) {
1287 applyToSetFTrue (cseSet,findCheaperOp,IC_RESULT(ic),&pdop);
1288 if (pdop && IS_ITEMP(pdop) && !computeOnly)
1289 IC_RESULT(ic) = pdop;
1293 /* do the operand lookup i.e. for both the */
1294 /* right & left operand : check the cseSet */
1295 /* to see if they have been replaced if yes*/
1296 /* then replace them with those from cseSet*/
1298 /* and left is a symbol */
1299 if (IS_SYMOP(IC_LEFT(ic)) &&
1300 !computeOnly && ic->op != ADDRESS_OF ) {
1303 applyToSetFTrue (cseSet,findCheaperOp,IC_LEFT(ic),&pdop) ;
1305 if (POINTER_GET(ic)) {
1306 if (IS_ITEMP(pdop) || IS_OP_LITERAL(pdop)) {
1310 /* check if there is a pointer set
1311 for the same pointer visible if yes
1312 then change this into an assignment */
1314 if (applyToSetFTrue(cseSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic)) &&
1315 !bitVectBitValue(ebb->ptrsSet,pdop->key)){
1318 IC_RIGHT(ic) = pdop;
1319 SET_ISADDR(IC_RESULT(ic),0);
1324 IC_LEFT(ic) = pdop ;
1331 if (IS_SYMOP(IC_RIGHT(ic)) && !computeOnly) {
1334 applyToSetFTrue (cseSet,findCheaperOp,IC_RIGHT(ic),&pdop);
1337 IC_RIGHT(ic) = pdop;
1342 /* if left or right changed then do algebraic */
1345 while(constFold(ic,cseSet));
1348 /* if after all this it becomes a assignment to self
1349 then delete it and continue */
1350 if (ASSIGNMENT_TO_SELF(ic)) {
1351 remiCodeFromeBBlock(ebb,ic);
1355 /* now we will check to see if the entire */
1356 /* operation has been performed before */
1357 /* and is available */
1358 /* don't do assignments they will be killed */
1359 /* by dead code elimination if required do */
1360 /* it only if result is a temporary */
1362 if (!( POINTER_GET(ic) &&
1363 (IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1364 isOperandVolatile(IC_LEFT(ic),TRUE) ||
1365 bitVectBitValue(ebb->ndompset,IC_LEFT(ic)->key))) &&
1367 IS_ITEMP(IC_RESULT(ic)) &&
1369 applyToSet (cseSet,findPrevIc,ic,&pdic);
1370 if (pdic && checkType(operandType(IC_RESULT(pdic)),
1371 operandType(IC_RESULT(ic))) != 1)
1375 /* if found then eliminate this and add to*/
1376 /* to cseSet an element containing result */
1377 /* of this with previous opcode */
1380 if (IS_ITEMP(IC_RESULT(ic))) {
1382 /* replace in the remaining of this block */
1383 replaceAllSymBySym(ic->next,IC_RESULT(ic),IC_RESULT(pdic),&ebb->ndompset);
1384 /* remove this iCode from inexpressions of all
1385 its successors, it cannot be in the in expressions
1386 of any of the predecessors */
1387 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1388 applyToSet(ebb->succList,removeFromInExprs,ic,IC_RESULT(ic),
1389 IC_RESULT(pdic),ebb);
1391 /* if this was moved from another block */
1392 /* then replace in those blocks too */
1393 if ( ic->movedFrom ) {
1395 for (owner = setFirstItem(ic->movedFrom); owner ;
1396 owner = setNextItem(ic->movedFrom))
1397 replaceAllSymBySym(owner->sch,IC_RESULT(ic),IC_RESULT(pdic),&owner->ndompset);
1399 pdic->movedFrom = unionSets(pdic->movedFrom,ic->movedFrom,THROW_NONE);
1402 addSetHead (&cseSet,newCseDef(IC_RESULT(ic),pdic));
1405 /* eliminate this */
1406 remiCodeFromeBBlock (ebb,ic);
1411 if (IS_ITEMP(IC_RESULT(ic)))
1416 /* just add this as a previous expression except in */
1417 /* case of a pointer access in which case this is a */
1418 /* usage not a definition */
1419 if (! (POINTER_SET(ic)) && IC_RESULT(ic)){
1420 deleteItemIf (&cseSet, ifDefSymIsX,IC_RESULT(ic));
1421 addSetHead(&cseSet,newCseDef(IC_RESULT(ic),ic));
1427 /* if assignment to a parameter which is not
1428 mine and type is a pointer then delete
1429 pointerGets to take care of aliasing */
1430 if (ASSIGNMENT(ic) &&
1431 OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) &&
1432 IS_PTR(operandType(IC_RESULT(ic)))) {
1433 deleteGetPointers(&cseSet,&ptrSetSet,IC_RIGHT(ic),ebb);
1434 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1435 applyToSet(ebb->succList,delGetPointerSucc,IC_RIGHT(ic),ebb->dfnum);
1436 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RIGHT(ic)->key);
1439 /* if this is a pointerget then see if we can replace
1440 this with a previously assigned pointer value */
1441 if (POINTER_GET(ic) &&
1442 !(IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1443 isOperandVolatile(IC_LEFT(ic),TRUE))) {
1445 applyToSet(ptrSetSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic));
1446 /* if we find it then locally replace all
1447 references to the result with what we assigned */
1449 replaceAllSymBySym(ic->next,IC_RESULT(ic),pdop,&ebb->ndompset);
1453 /* delete from the cseSet anything that has */
1454 /* operands matching the result of this */
1455 /* except in case of pointer access */
1456 if (!(POINTER_SET(ic)) && IC_RESULT(ic)) {
1457 deleteItemIf (&cseSet,ifOperandsHave,IC_RESULT(ic));
1458 /* delete any previous definitions */
1459 ebb->defSet = bitVectCplAnd (ebb->defSet,OP_DEFS(IC_RESULT(ic)));
1463 /* add the left & right to the defUse set */
1464 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic))) {
1465 OP_USES(IC_LEFT(ic)) =
1466 bitVectSetBit (OP_USES(IC_LEFT(ic)),ic->key);
1467 setUsesDefs(IC_LEFT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1471 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic))) {
1472 OP_USES(IC_RIGHT(ic)) =
1473 bitVectSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
1474 setUsesDefs(IC_RIGHT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1478 /* for the result it is special case, put the result */
1479 /* in the defuseSet if it a pointer or array access */
1480 if ( POINTER_SET(defic) ) {
1481 OP_USES(IC_RESULT(ic)) =
1482 bitVectSetBit (OP_USES(IC_RESULT(ic)),ic->key);
1483 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1484 deleteItemIf(&cseSet,ifPointerGet,IC_RESULT(ic));
1485 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RESULT(ic)->key);
1486 /* delete from inexpressions of all successors which
1487 have dfNum > than this block */
1488 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1489 applyToSet(ebb->succList,delGetPointerSucc,IC_RESULT(ic),ebb->dfnum);
1491 /* delete from cseSet all other pointer sets
1493 deleteItemIf(&ptrSetSet,ifPointerSet,IC_RESULT(ic));
1494 /* add to the local pointerset set */
1495 addSetHead(&ptrSetSet,newCseDef(IC_RESULT(ic),ic));
1497 else /* add the result to defintion set */
1498 if (IC_RESULT(ic)) {
1499 OP_DEFS(IC_RESULT(ic)) =
1500 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1501 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1502 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1503 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1507 /* if this is an addressof instruction then */
1508 /* put the symbol in the address of list & */
1509 /* delete it from the cseSet */
1510 if (defic->op == ADDRESS_OF) {
1511 addSetHead (&ebb->addrOf, IC_LEFT(ic));
1512 deleteItemIf(&cseSet,ifDefSymIsX,IC_LEFT(ic));
1516 setToNull ((void **)&ebb->outExprs);
1517 ebb->outExprs = cseSet;
1518 ebb->outDefs = bitVectUnion (ebb->outDefs,ebb->defSet);
1519 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet,ebb->inPtrsSet);
1523 /*-----------------------------------------------------------------*/
1524 /* cseAllBlocks - will sequentially go thru & do cse for all blocks*/
1525 /*-----------------------------------------------------------------*/
1526 int cseAllBlocks (eBBlock **ebbs,int count)
1531 /* if optimization turned off */
1533 for (i = 0 ; i < count ;i++ )
1534 change += cseBBlock (ebbs[i],FALSE,ebbs,count);