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 -------------------------------------------------------------------------*/
28 /*-----------------------------------------------------------------*/
29 /* newCseDef - new cseDef */
30 /*-----------------------------------------------------------------*/
31 cseDef *newCseDef (operand *sym, iCode *ic)
36 cdp = Safe_calloc(1,sizeof(cseDef));
47 /*-----------------------------------------------------------------*/
48 /* int isCseDefEqual - two definitions are equal */
49 /*-----------------------------------------------------------------*/
50 int isCseDefEqual ( void *vsrc, void *vdest)
58 return (src->key == dest->key &&
59 src->diCode == dest->diCode ) ;
63 /*-----------------------------------------------------------------*/
64 /* pcseDef - in the cseDef */
65 /*-----------------------------------------------------------------*/
66 int pcseDef (void *item, va_list ap)
74 fprintf(stdout,"**null op**");
75 printOperand(cdp->sym,stdout);
76 icTab = getTableEntry(cdp->diCode->op) ;
77 icTab->iCodePrint(stdout,cdp->diCode,icTab->printName);
81 /*-----------------------------------------------------------------*/
82 /* replaceAllSymBySym - replaces all operands by operand in an */
83 /* instruction chain */
84 /*-----------------------------------------------------------------*/
85 void replaceAllSymBySym (iCode *ic, operand *from , operand *to, bitVect **ndpset)
89 for (lic = ic ; lic ; lic = lic->next ) {
92 /* do the special cases first */
95 IC_COND(lic)->key == from->key) {
97 bitVectUnSetBit (OP_USES(from),lic->key);
98 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
99 siaddr = IC_COND(lic)->isaddr ;
100 IC_COND(lic) = operandFromOperand(to);
101 IC_COND(lic)->isaddr = siaddr ;
107 if (lic->op == JUMPTABLE) {
109 IC_JTCOND(lic)->key == from->key) {
111 bitVectUnSetBit (OP_USES(from),lic->key);
112 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
113 siaddr = IC_COND(lic)->isaddr ;
114 IC_JTCOND(lic) = operandFromOperand(to);
115 IC_JTCOND(lic)->isaddr = siaddr ;
121 if (IC_RESULT(lic) && IC_RESULT(lic)->key == from->key ) {
122 /* maintain du chains */
123 if (POINTER_SET(lic)) {
124 bitVectUnSetBit (OP_USES(from),lic->key);
125 OP_USES(to) = bitVectSetBit (OP_USES(to),lic->key);
127 /* also check if the "from" was in the non-dominating
128 pointer sets and replace it with "to" in the bitVector */
129 if (bitVectBitValue(*ndpset,from->key)) {
130 bitVectUnSetBit(*ndpset,from->key);
131 bitVectSetBit(*ndpset,to->key);
136 bitVectUnSetBit (OP_DEFS(from),lic->key);
137 OP_DEFS(to) = bitVectSetBit (OP_DEFS(to),lic->key);
139 siaddr = IC_RESULT(lic)->isaddr ;
140 IC_RESULT(lic) = operandFromOperand(to);
141 IC_RESULT(lic)->isaddr = siaddr ;
145 IC_RIGHT(lic) && IC_RIGHT(lic)->key == from->key ) {
146 bitVectUnSetBit (OP_USES(from),lic->key);
147 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
148 siaddr = IC_RIGHT(lic)->isaddr ;
149 IC_RIGHT(lic) = operandFromOperand(to);
150 IC_RIGHT(lic)->isaddr = siaddr ;
154 IC_LEFT(lic) && IC_LEFT(lic)->key == from->key ) {
155 bitVectUnSetBit (OP_USES(from),lic->key);
156 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
157 siaddr = IC_LEFT(lic)->isaddr ;
158 IC_LEFT(lic) = operandFromOperand(to);
159 IC_LEFT(lic)->isaddr = siaddr ;
164 /*-----------------------------------------------------------------*/
165 /* iCodeKeyIs - if the icode keys match then return 1 */
166 /*-----------------------------------------------------------------*/
167 DEFSETFUNC(iCodeKeyIs)
172 if (cdp->diCode->key == key)
178 /*-----------------------------------------------------------------*/
179 /* removeFromInExprs - removes an icode from inexpressions */
180 /*-----------------------------------------------------------------*/
181 DEFSETFUNC(removeFromInExprs)
185 V_ARG(operand *,from);
187 V_ARG(eBBlock *,cbp);
193 deleteItemIf(&ebp->inExprs,iCodeKeyIs,ic->key);
194 if (ebp != cbp && !bitVectBitValue(cbp->domVect,ebp->bbnum))
195 replaceAllSymBySym(ebp->sch,from,to,&ebp->ndompset);
197 applyToSet(ebp->succList,removeFromInExprs,ic,from,to,cbp);
201 /*-----------------------------------------------------------------*/
202 /* isGlobalInNearSpace - return TRUE if valriable is a globalin data */
203 /*-----------------------------------------------------------------*/
204 static bool isGlobalInNearSpace (operand *op)
206 sym_link *type = getSpec(operandType(op));
207 /* this is 8051 specific: optimization
208 suggested by Jean-Louis VERN, with 8051s we have no
209 advantage of putting variables in near space into
211 if (isOperandGlobal(op) && !IN_FARSPACE(SPEC_OCLS(type)) &&
212 IN_DIRSPACE(SPEC_OCLS(type)))
218 /*-----------------------------------------------------------------*/
219 /* findCheaperOp - cseBBlock support routine, will check to see if */
220 /* we have a operand previously defined */
221 /*-----------------------------------------------------------------*/
222 DEFSETFUNC(findCheaperOp)
225 V_ARG(operand *,cop);
226 V_ARG(operand **,opp);
228 /* if we have already found it */
232 /* not found it yet check if this is the one */
233 /* and this is not the defining one */
234 if (cop->key == cdp->key) {
236 /* do a special check this will help in */
237 /* constant propagation & dead code elim*/
238 /* for assignments only */
239 if (cdp->diCode->op == '=') {
240 /* if the result is volatile then return result */
241 if (IS_OP_VOLATILE (IC_RESULT(cdp->diCode)))
242 *opp = IC_RESULT(cdp->diCode);
244 /* if this is a straight assignment and
245 left is a temp then prefer the temporary to the
247 if (!POINTER_SET(cdp->diCode) &&
248 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
249 IS_TRUE_SYMOP(IC_RIGHT(cdp->diCode)))
250 *opp = IC_RESULT(cdp->diCode);
252 /* if straight assignement && and both
253 are temps then prefer the one that
254 will not need extra space to spil, also
255 take into consideration if right side
256 an induction variable
258 if (!POINTER_SET(cdp->diCode) &&
259 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
260 IS_ITEMP(IC_RIGHT(cdp->diCode)) &&
261 !OP_SYMBOL(IC_RIGHT(cdp->diCode))->isind &&
262 ( (!SPIL_LOC(IC_RIGHT(cdp->diCode)) &&
263 SPIL_LOC(IC_RESULT(cdp->diCode))) ||
264 ( SPIL_LOC(IC_RESULT(cdp->diCode)) &&
265 SPIL_LOC(IC_RESULT(cdp->diCode)) ==
266 SPIL_LOC(IC_RIGHT(cdp->diCode))) )
268 *opp = IC_RESULT(cdp->diCode);
270 *opp = IC_RIGHT(cdp->diCode);
273 *opp = IC_RESULT(cdp->diCode) ;
276 /* if this is an assign to a temp. then check
277 if the right side is this then return this */
278 if (IS_TRUE_SYMOP(cop) &&
279 cdp->diCode->op == '=' &&
280 !POINTER_SET(cdp->diCode) &&
281 cop->key == IC_RIGHT(cdp->diCode)->key &&
282 !isGlobalInNearSpace (IC_RIGHT(cdp->diCode)) &&
283 IS_ITEMP(IC_RESULT(cdp->diCode)))
284 *opp = IC_RESULT(cdp->diCode);
288 if ((isGlobalInNearSpace(cop) &&
289 !isOperandLiteral(*opp)) ||
290 isOperandVolatile(*opp,FALSE)
296 if (cop->key == (*opp)->key ) {
301 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP(cop)) {
302 *opp = operandFromOperand(*opp);
303 (*opp)->isaddr = cop->isaddr;
313 /*-----------------------------------------------------------------*/
314 /* findPointerSet - finds the right side of a pointer set op */
315 /*-----------------------------------------------------------------*/
316 DEFSETFUNC(findPointerSet)
320 V_ARG(operand **,opp);
321 V_ARG(operand *,rop);
323 if (POINTER_SET(cdp->diCode) &&
324 IC_RESULT(cdp->diCode)->key == op->key &&
325 !isOperandVolatile(IC_RESULT(cdp->diCode),TRUE) &&
326 !isOperandVolatile(IC_RIGHT(cdp->diCode),TRUE) &&
327 getSize(operandType(IC_RIGHT(cdp->diCode))) ==
328 getSize(operandType(rop))) {
329 *opp = IC_RIGHT(cdp->diCode);
336 /*-----------------------------------------------------------------*/
337 /* findPrevIc - cseBBlock support function will return the iCode */
338 /* which matches the current one */
339 /*-----------------------------------------------------------------*/
340 DEFSETFUNC(findPrevIc)
346 /* if already found */
350 /* if the iCodes are the same */
351 if (isiCodeEqual(ic,cdp->diCode) &&
352 isOperandEqual(cdp->sym,IC_RESULT(cdp->diCode))) {
357 /* if iCodes are not the same */
358 /* see the operands maybe interchanged */
359 if (ic->op == cdp->diCode->op &&
360 ( ic->op == '+' || ic->op == '*' ) &&
361 isOperandEqual(IC_LEFT(ic),IC_RIGHT(cdp->diCode)) &&
362 isOperandEqual(IC_RIGHT(ic),IC_LEFT(cdp->diCode))) {
370 /*-----------------------------------------------------------------*/
371 /* ifDefGlobal - if definition is global */
372 /*-----------------------------------------------------------------*/
373 DEFSETFUNC(ifDefGlobal)
377 return (isOperandGlobal(cdp->sym));
380 /*-----------------------------------------------------------------*/
381 /* ifAnyGetPointer - if get pointer icode */
382 /*-----------------------------------------------------------------*/
383 DEFSETFUNC(ifAnyGetPointer)
387 if (cdp->diCode && POINTER_GET(cdp->diCode)) return 1;
391 /*-----------------------------------------------------------------*/
392 /* ifOperandsHave - if any of the operand are the same as this */
393 /*-----------------------------------------------------------------*/
394 DEFSETFUNC(ifOperandsHave)
400 if (IC_LEFT(cdp->diCode) &&
401 IS_SYMOP(IC_LEFT(cdp->diCode)) &&
402 IC_LEFT(cdp->diCode)->key == op->key)
405 if (IC_RIGHT(cdp->diCode) &&
406 IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
407 IC_RIGHT(cdp->diCode)->key == op->key)
410 /* or if any of the operands are volatile */
411 if (IC_LEFT(cdp->diCode) &&
412 IS_OP_VOLATILE(IC_LEFT(cdp->diCode)))
415 if (IC_RIGHT(cdp->diCode) &&
416 IS_OP_VOLATILE(IC_RIGHT(cdp->diCode)))
420 if (IC_RESULT(cdp->diCode) &&
421 IS_OP_VOLATILE(IC_RESULT(cdp->diCode)))
427 /*-----------------------------------------------------------------*/
428 /* ifDefSymIs - if a definition is found in the set */
429 /*-----------------------------------------------------------------*/
430 int ifDefSymIs (set *cseSet, operand *sym)
435 if (!sym || !IS_SYMOP(sym))
437 for (sl = cseSet ; sl ; sl = sl->next ) {
439 if (loop->sym->key == sym->key )
446 /*-----------------------------------------------------------------*/
447 /* ifDefSymIsX - will return 1 if the symbols match */
448 /*-----------------------------------------------------------------*/
449 DEFSETFUNC(ifDefSymIsX)
455 return cdp->sym->key == op->key ;
457 return ( isOperandEqual(cdp->sym,op) );
462 /*-----------------------------------------------------------------*/
463 /* ifDiCodeIs - returns truw if diCode is same */
464 /*-----------------------------------------------------------------*/
465 int ifDiCodeIs (set *cseSet, iCode *ic)
473 for (sl = cseSet ; sl ; sl = sl->next ) {
475 if (loop->diCode == ic)
482 /*-----------------------------------------------------------------*/
483 /* ifPointerGet - returns true if the icode is pointer get sym */
484 /*-----------------------------------------------------------------*/
485 DEFSETFUNC(ifPointerGet)
489 iCode *dic = cdp->diCode;
490 operand *left = IC_LEFT(cdp->diCode);
492 if (POINTER_GET(dic) && left->key == op->key)
498 /*-----------------------------------------------------------------*/
499 /* ifPointerSet - returns true if the icode is pointer set sym */
500 /*-----------------------------------------------------------------*/
501 DEFSETFUNC(ifPointerSet)
506 if (POINTER_SET(cdp->diCode) &&
507 IC_RESULT(cdp->diCode)->key == op->key)
513 /*-----------------------------------------------------------------*/
514 /* ifDiCodeIsX - will return 1 if the symbols match */
515 /*-----------------------------------------------------------------*/
516 DEFSETFUNC(ifDiCodeIsX)
521 return cdp->diCode == ic;
525 /*-----------------------------------------------------------------*/
526 /* algebraicOpts - does some algebraic optimizations */
527 /*-----------------------------------------------------------------*/
528 void algebraicOpts (iCode *ic)
530 /* we don't deal with the following iCodes
541 /* if both operands present & ! IFX */
542 /* then if they are both literal we */
543 /* perform the operation right now */
547 IS_OP_LITERAL(IC_LEFT(ic)) &&
548 IS_OP_LITERAL(IC_RIGHT(ic))) {
550 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
553 operandType(IC_RESULT(ic)));
556 SET_RESULT_RIGHT(ic);
560 /* if not ifx & only one operand present */
563 IS_OP_LITERAL(IC_LEFT(ic)) &&
566 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
569 operandType(IC_RESULT(ic)));
572 SET_RESULT_RIGHT(ic);
577 /* a special case : or in short a kludgy solution will think
578 about a better solution over a glass of wine someday */
579 if ( ic->op == GET_VALUE_AT_ADDRESS ) {
581 if (IS_ITEMP(IC_RESULT(ic)) &&
582 IS_TRUE_SYMOP(IC_LEFT(ic))) {
585 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
586 IC_RIGHT(ic)->isaddr = 0;
588 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
589 IC_RESULT(ic)->isaddr = 0;
590 setOperandType(IC_RESULT(ic),operandType(IC_RIGHT(ic)));
594 if (IS_ITEMP(IC_LEFT(ic)) &&
595 IS_ITEMP(IC_RESULT(ic)) &&
596 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
597 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
598 !IC_LEFT(ic)->isaddr ) {
600 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
601 IC_RIGHT(ic)->isaddr = 0;
602 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
603 IC_RESULT(ic)->isaddr = 0;
611 /* depending on the operation */
614 /* if adding the same thing change to left shift by 1*/
615 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key &&
616 !IS_FLOAT(operandType(IC_RESULT(ic)))) {
618 IC_RIGHT(ic) = operandFromLit(1);
621 /* if addition then check if one of them is a zero */
622 /* if yes turn it into assignmnt*/
623 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
624 operandLitValue(IC_LEFT(ic)) == 0.0 ) {
628 SET_ISADDR(IC_RESULT(ic),0);
629 SET_ISADDR(IC_RIGHT(ic),0);
632 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
633 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
636 IC_RIGHT(ic) = IC_LEFT(ic) ;
638 SET_ISADDR(IC_RIGHT(ic),0);
639 SET_ISADDR(IC_RESULT(ic),0);
644 /* if subtracting the the same thing then zero */
645 if ( IC_LEFT(ic)->key == IC_RIGHT(ic)->key ) {
647 IC_RIGHT(ic) = operandFromLit(0);
649 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
650 IC_RESULT(ic)->isaddr = 0;
654 /* if subtraction then check if one of the operand */
655 /* is zero then depending on which operand change */
656 /* to assignment or unary minus */
657 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
658 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
659 /* right size zero change to assignment */
661 IC_RIGHT(ic) = IC_LEFT(ic);
663 SET_ISADDR(IC_RIGHT(ic),0);
664 SET_ISADDR(IC_RESULT(ic),0);
667 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
668 operandLitValue (IC_LEFT(ic)) == 0.0) {
669 /* left zero turn into an unary minus */
670 ic->op = UNARYMINUS ;
671 IC_LEFT(ic) = IC_RIGHT(ic);
672 IC_RIGHT(ic) = NULL ;
676 /* if multiplication then check if either of */
677 /* them is zero then the result is zero */
678 /* if either of them is one then result is */
681 if (IS_OP_LITERAL(IC_LEFT(ic))) {
683 if (operandLitValue(IC_LEFT(ic)) == 0.0) {
685 IC_RIGHT(ic) = IC_LEFT(ic);
687 SET_RESULT_RIGHT(ic);
690 if ( operandLitValue(IC_LEFT(ic)) == 1.0) {
693 SET_RESULT_RIGHT(ic);
698 if (IS_OP_LITERAL(IC_RIGHT(ic))) {
700 if (operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
703 SET_RESULT_RIGHT(ic);
707 if (operandLitValue(IC_RIGHT(ic)) == 1.0) {
709 IC_RIGHT(ic) = IC_LEFT(ic);
711 SET_RESULT_RIGHT(ic);
717 /* if division by self then 1 */
718 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key) {
720 IC_RIGHT(ic) = operandFromLit(1);
722 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
723 IC_RESULT(ic)->isaddr = 0;
725 /* if this is a division then check if right */
726 /* is one then change it to an assignment */
727 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
728 operandLitValue(IC_RIGHT(ic)) == 1.0 ) {
731 IC_RIGHT(ic) = IC_LEFT(ic);
733 SET_RESULT_RIGHT(ic);
737 /* if both are the same for an comparison operators */
741 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
743 IC_RIGHT(ic) = operandFromLit(1);
745 SET_RESULT_RIGHT(ic);
751 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
753 IC_RIGHT(ic) = operandFromLit(0);
755 SET_RESULT_RIGHT(ic);
759 /* if this is a cast of a literal value */
760 if ( IS_OP_LITERAL(IC_RIGHT(ic))) {
763 operandFromValue (valCastLiteral(operandType(IC_LEFT(ic)),
764 operandLitValue(IC_RIGHT(ic))));
766 SET_ISADDR(IC_RESULT(ic),0);
768 /* if casting to the same */
769 if ( checkType(operandType(IC_RESULT(ic)),
770 operandType(IC_RIGHT(ic))) == 1) {
773 SET_ISADDR(IC_RESULT(ic),0);
777 if (IS_OP_LITERAL(IC_LEFT(ic))) {
780 (operandLitValue(IC_LEFT(ic)) == 0 ?
781 operandFromLit(1) : operandFromLit(0));
783 SET_ISADDR(IC_RESULT(ic),0);
789 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
790 /*-----------------------------------------------------------------*/
791 /* updateSpillLocation - keeps track of register spill location */
792 /*-----------------------------------------------------------------*/
793 void updateSpillLocation ( iCode *ic)
804 /* for the form true_symbol := iTempNN */
805 if (ASSIGN_ITEMP_TO_SYM(ic)
806 && !SPIL_LOC(IC_RIGHT(ic))) {
808 setype = getSpec(operandType(IC_RESULT(ic)));
810 if (!IC_RIGHT(ic)->noSpilLoc &&
811 !IS_VOLATILE(setype) &&
812 !IN_FARSPACE(SPEC_OCLS(setype)) &&
813 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
815 SPIL_LOC(IC_RIGHT(ic)) =
816 IC_RESULT(ic)->operand.symOperand;
819 if (ASSIGN_ITEMP_TO_ITEMP(ic) &&
820 !SPIL_LOC(IC_RIGHT(ic)) &&
821 !bitVectBitsInCommon(OP_DEFS(IC_RIGHT(ic)),OP_USES(IC_RESULT(ic))) &&
822 OP_SYMBOL(IC_RESULT(ic))->isreqv) {
824 setype = getSpec(operandType(IC_RESULT(ic)));
826 if (!IC_RIGHT(ic)->noSpilLoc &&
827 !IS_VOLATILE(setype) &&
828 !IN_FARSPACE(SPEC_OCLS(setype)) &&
829 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
831 SPIL_LOC(IC_RIGHT(ic)) =
832 SPIL_LOC(IC_RESULT(ic));
836 /*-----------------------------------------------------------------*/
837 /* setUsesDef - sets the uses def bitvector for a given operand */
838 /*-----------------------------------------------------------------*/
839 void setUsesDefs (operand *op, bitVect *bdefs,
840 bitVect *idefs, bitVect **oud)
842 /* compute the definitions alive at this point */
843 bitVect *adefs = bitVectUnion(bdefs,idefs);
845 /* of these definitions find the ones that are */
846 /* for this operand */
847 adefs = bitVectIntersect(adefs,OP_DEFS(op));
849 /* these are the definitions that this operand can use */
850 op->usesDefs = adefs;
852 /* the out defs is an union */
853 *oud = bitVectUnion(*oud,adefs);
856 /*-----------------------------------------------------------------*/
857 /* unsetDefsAndUses - clear this operation for the operands */
858 /*-----------------------------------------------------------------*/
859 void unsetDefsAndUses ( iCode *ic )
861 if ( ic->op == JUMPTABLE)
864 /* take away this definition from the def chain of the */
865 /* result & take away from use set of the operands */
867 /* turn off def set */
868 if (IS_SYMOP(IC_RESULT(ic))) {
869 if ( !POINTER_SET(ic))
870 bitVectUnSetBit(OP_DEFS(IC_RESULT(ic)),ic->key);
872 bitVectUnSetBit(OP_USES(IC_RESULT(ic)),ic->key);
874 /* turn off the useSet for the operands */
875 if (IS_SYMOP(IC_LEFT(ic)))
876 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
878 if (IS_SYMOP(IC_RIGHT(ic)))
879 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
881 else /* must be ifx turn off the use */
882 if (IS_SYMOP(IC_COND(ic)))
883 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
886 /*-----------------------------------------------------------------*/
887 /* ifxOptimize - changes ifx conditions if it can */
888 /*-----------------------------------------------------------------*/
889 void ifxOptimize (iCode *ic, set *cseSet,
891 eBBlock *ebb, int *change,
892 eBBlock **ebbs, int count)
897 /* if the condition can be replaced */
900 applyToSetFTrue (cseSet,findCheaperOp,IC_COND(ic),&pdop);
907 /* if the conditional is a literal then */
908 if (IS_OP_LITERAL(IC_COND(ic))) {
910 if ( (operandLitValue(IC_COND(ic)) != 0.0) && IC_TRUE(ic)) {
912 /* change to a goto */
914 IC_LABEL(ic) = IC_TRUE(ic);
919 if (!operandLitValue(IC_COND(ic)) && IC_FALSE(ic)) {
921 IC_LABEL(ic) = IC_FALSE(ic);
925 /* then kill this if condition */
926 remiCodeFromeBBlock (ebb,ic);
930 /* now we need to recompute the control flow */
931 /* since the control flow has changed */
932 /* this is very expensive but it does not happen */
933 /* too often, if it does happen then the user pays */
935 computeControlFlow (ebbs,count,1);
936 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
940 /* if there is only one successor and that successor
941 is the same one we are conditionally going to then
942 we can remove this conditional statement */
943 label = (IC_TRUE(ic) ? IC_TRUE(ic) : IC_FALSE(ic));
944 if (elementsInSet(ebb->succList) == 1 &&
945 isinSet(ebb->succList,eBBWithEntryLabel(ebbs,label,count))) {
947 remiCodeFromeBBlock(ebb,ic);
948 computeControlFlow (ebbs,count,1);
949 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
954 /* if it remains an IFX the update the use Set */
955 OP_USES(IC_COND(ic)) = bitVectSetBit(OP_USES(IC_COND(ic)),ic->key);
956 setUsesDefs(IC_COND(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
960 /*-----------------------------------------------------------------*/
961 /* diCodeForSym - finds the definiting instruction for a symbol */
962 /*-----------------------------------------------------------------*/
963 DEFSETFUNC(diCodeForSym)
966 V_ARG(operand *,sym);
969 /* if already found */
973 /* if not if this is the defining iCode */
974 if (sym->key == cdp->key) {
982 /*-----------------------------------------------------------------*/
983 /* constFold - does some constant folding */
984 /*-----------------------------------------------------------------*/
985 int constFold (iCode *ic, set *cseSet)
989 /* this routine will change
995 /* deal with only + & - */
1000 /* this check is a hueristic to prevent live ranges
1001 from becoming too long */
1002 if (IS_PTR(operandType(IC_RESULT(ic))))
1005 /* check if operation with a literal */
1006 if (!IS_OP_LITERAL(IC_RIGHT(ic)))
1009 /* check if we can find a definition for the
1011 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(ic),&dic)))
1014 /* check that this is also a +/- */
1015 if (dic->op != '+' && dic->op != '-')
1018 /* with a literal */
1019 if (!IS_OP_LITERAL(IC_RIGHT(dic)))
1022 /* find the definition of the left operand
1023 of dic.then check if this defined with a
1024 get_pointer return 0 if the pointer size is
1025 less than 2 (MCS51 specific) */
1026 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(dic),&ldic)))
1029 if (POINTER_GET(ldic) && getSize(operandType(IC_LEFT(ldic))) <= 1)
1032 /* it is if the operations are the same*/
1033 /* the literal parts need to be added */
1034 IC_LEFT(ic) = operandFromOperand(IC_LEFT(dic));
1035 if (ic->op == dic->op )
1036 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic))+
1037 operandLitValue(IC_RIGHT(dic)));
1039 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) -
1040 operandLitValue(IC_RIGHT(dic)));
1042 if (IS_ITEMP(IC_RESULT(ic))) {
1043 SPIL_LOC(IC_RESULT(ic)) = NULL;
1044 IC_RESULT(ic)->noSpilLoc = 1;
1051 /*-----------------------------------------------------------------*/
1052 /* deleteGetPointers - called when a pointer is passed as parm */
1053 /* will delete from cseSet all get pointers computed from this */
1054 /* pointer. A simple ifOperandsHave is not good enough here */
1055 /*-----------------------------------------------------------------*/
1056 static void deleteGetPointers (set **cseSet, set **pss, operand *op,eBBlock *ebb)
1058 set *compItems = NULL;
1063 if (!*cseSet && !*pss)
1066 /* first find all items computed from this operand .
1067 This done fairly simply go thru the list and find
1068 those that are computed by arthimetic with this
1070 for (cdp = setFirstItem(*cseSet); cdp ; cdp = setNextItem(*cseSet)) {
1071 if (IS_ARITHMETIC_OP(cdp->diCode)) {
1072 if (isOperandEqual(IC_LEFT(cdp->diCode),op) ||
1073 isOperandEqual(IC_RIGHT(cdp->diCode),op)) {
1074 /* save it in our list of items */
1075 addSet(&compItems,IC_RESULT(cdp->diCode));
1077 /* also check for those computed from our computed
1078 list . This will take care of situations like
1079 iTemp1 = iTemp0 + 8;
1080 iTemp2 = iTemp1 + 8; */
1081 if (isinSetWith(compItems,IC_LEFT(cdp->diCode),isOperandEqual) ||
1082 isinSetWith(compItems,IC_RIGHT(cdp->diCode),isOperandEqual)) {
1083 addSet(&compItems,IC_RESULT(cdp->diCode));
1088 /* now delete all pointer gets with this op */
1089 deleteItemIf(cseSet,ifPointerGet,op);
1090 deleteItemIf(pss,ifPointerSet,op);
1092 /* set the bit vector used by dataFlow computation later */
1093 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,op->key);
1094 /* now for the computed items */
1095 for (cop = setFirstItem(compItems); cop ; cop = setNextItem(compItems)) {
1096 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,cop->key);
1097 deleteItemIf(cseSet,ifPointerGet,cop);
1098 deleteItemIf(pss,ifPointerSet,cop);
1102 /*-----------------------------------------------------------------*/
1103 /* delGetPointerSucc - delete get pointer from inExprs of succ with*/
1104 /* dfnum > supplied */
1105 /*-----------------------------------------------------------------*/
1106 DEFSETFUNC(delGetPointerSucc)
1108 eBBlock *ebp = item;
1109 V_ARG(operand *,op);
1116 if (ebp->dfnum > dfnum) {
1117 deleteItemIf(&ebp->inExprs,ifPointerGet,op);
1120 return applyToSet(ebp->succList,delGetPointerSucc,op,dfnum);
1123 /*-----------------------------------------------------------------*/
1124 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1125 /*-----------------------------------------------------------------*/
1126 static void fixUpTypes(iCode *ic)
1128 sym_link *t1 = operandType(IC_LEFT(ic)) ,*t2;
1136 /* for pointer_gets if the types of result & left r the
1137 same then change it type of result to next */
1139 checkType(t2=operandType(IC_RESULT(ic)),t1) == 1) {
1140 setOperandType(IC_RESULT(ic),t2->next);
1144 /*-----------------------------------------------------------------*/
1145 /* cseBBlock - common subexpression elimination for basic blocks */
1146 /* this is the hackiest kludgiest routine in the whole */
1147 /* system. also the most important, since almost all */
1148 /* data flow related information is computed by it */
1149 /*-----------------------------------------------------------------*/
1150 int cseBBlock ( eBBlock *ebb, int computeOnly,
1151 eBBlock **ebbs, int count)
1157 set *ptrSetSet = NULL;
1159 /* if this block is not reachable */
1163 /* set of common subexpressions */
1164 cseSet = setFromSet (ebb->inExprs) ;
1166 /* these will be computed by this routine */
1167 setToNull ((void **)&ebb->outDefs);
1168 setToNull ((void **)&ebb->defSet);
1169 setToNull ((void **)&ebb->usesDefs);
1170 setToNull ((void **)&ebb->ptrsSet);
1171 setToNull ((void **)&ebb->addrOf);
1172 setToNull ((void **)&ebb->ldefs);
1174 ebb->outDefs = bitVectCopy (ebb->inDefs);
1175 bitVectDefault = iCodeKey;
1176 ebb->defSet = newBitVect(iCodeKey);
1177 ebb->usesDefs=newBitVect(iCodeKey);
1179 /* for all the instructions in this block do */
1180 for (ic = ebb->sch ; ic ; ic = ic->next ) {
1189 /* if this is an assignment from true symbol
1190 to a temp then do pointer post inc/dec optimzation */
1191 if (ic->op == '=' && !POINTER_SET(ic) &&
1192 IS_PTR(operandType(IC_RESULT(ic)))) {
1193 ptrPostIncDecOpt(ic);
1196 /* clear the def & use chains for the operands involved */
1197 /* in this operation . since it can change due to opts */
1198 unsetDefsAndUses (ic);
1200 if ( ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE) {
1201 /* add to defSet of the symbol */
1202 OP_DEFS(IC_RESULT(ic)) =
1203 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1204 /* add to the definition set of this block */
1205 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1206 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1207 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1208 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1209 /* delete global variables from the cseSet
1210 since they can be modified by the function call */
1211 deleteItemIf(&cseSet,ifDefGlobal);
1212 /* delete all getpointer iCodes from cseSet, this should
1213 be done only for global arrays & pointers but at this
1214 point we don't know if globals, so to be safe do all*/
1215 deleteItemIf(&cseSet,ifAnyGetPointer);
1218 /* for pcall & ipush we need to add to the useSet */
1219 if ((ic->op == PCALL ||
1223 IS_SYMOP(IC_LEFT(ic))) {
1225 /* check if they can be replaced */
1226 if ( !computeOnly ) {
1228 applyToSetFTrue(cseSet,findCheaperOp,IC_LEFT(ic),&pdop);
1230 IC_LEFT(ic) = pdop ;
1232 /* the lookup could have changed it*/
1233 if (IS_SYMOP(IC_LEFT(ic))) {
1234 OP_USES(IC_LEFT(ic)) =
1235 bitVectSetBit(OP_USES(IC_LEFT(ic)),ic->key);
1236 setUsesDefs(IC_LEFT(ic),ebb->defSet,
1237 ebb->outDefs,&ebb->usesDefs);
1241 /* if we a sending a pointer as a parameter
1242 then kill all cse since the pointed to item
1243 might be changed in the function being called */
1244 if ((ic->op == IPUSH || ic->op == SEND) &&
1245 IS_PTR(operandType(IC_LEFT(ic)))) {
1246 deleteGetPointers(&cseSet,&ptrSetSet,IC_LEFT(ic),ebb);
1247 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_LEFT(ic)->key);
1248 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1249 applyToSet(ebb->succList,delGetPointerSucc,
1250 IC_LEFT(ic),ebb->dfnum);
1255 /* if jumptable then mark the usage */
1256 if (ic->op == JUMPTABLE ) {
1257 OP_USES(IC_JTCOND(ic)) =
1258 bitVectSetBit(OP_USES(IC_JTCOND(ic)),ic->key);
1259 setUsesDefs(IC_JTCOND(ic),ebb->defSet,
1260 ebb->outDefs,&ebb->usesDefs);
1267 /* do some algebraic optimizations if possible */
1269 while (constFold(ic,cseSet));
1272 if (POINTER_GET(ic) && !IS_PTR(operandType(IC_LEFT(ic)))) {
1273 setOperandType(IC_LEFT(ic),
1274 aggrToPtr(operandType(IC_LEFT(ic)),FALSE));
1278 if (POINTER_SET(ic) && !IS_PTR(operandType(IC_RESULT(ic)))) {
1279 setOperandType(IC_RESULT(ic),
1280 aggrToPtr(operandType(IC_RESULT(ic)),FALSE));
1283 /* if this is a condition statment then */
1284 /* check if the condition can be replaced */
1285 if (ic->op == IFX ) {
1286 ifxOptimize (ic, cseSet, computeOnly,
1292 /* if the assignment & result is a temp */
1293 /* see if we can replace it */
1294 if (ic->op == '=') {
1296 /* update the spill location for this */
1297 updateSpillLocation (ic);
1299 if (POINTER_SET(ic) &&
1300 !(IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype))) {
1302 applyToSetFTrue (cseSet,findCheaperOp,IC_RESULT(ic),&pdop);
1303 if (pdop && IS_ITEMP(pdop) && !computeOnly)
1304 IC_RESULT(ic) = pdop;
1308 /* do the operand lookup i.e. for both the */
1309 /* right & left operand : check the cseSet */
1310 /* to see if they have been replaced if yes*/
1311 /* then replace them with those from cseSet*/
1313 /* and left is a symbol */
1314 if (IS_SYMOP(IC_LEFT(ic)) &&
1315 !computeOnly && ic->op != ADDRESS_OF ) {
1318 applyToSetFTrue (cseSet,findCheaperOp,IC_LEFT(ic),&pdop) ;
1320 if (POINTER_GET(ic)) {
1321 if (IS_ITEMP(pdop) || IS_OP_LITERAL(pdop)) {
1325 /* check if there is a pointer set
1326 for the same pointer visible if yes
1327 then change this into an assignment */
1329 if (applyToSetFTrue(cseSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic)) &&
1330 !bitVectBitValue(ebb->ptrsSet,pdop->key)){
1333 IC_RIGHT(ic) = pdop;
1334 SET_ISADDR(IC_RESULT(ic),0);
1339 IC_LEFT(ic) = pdop ;
1346 if (IS_SYMOP(IC_RIGHT(ic)) && !computeOnly) {
1349 applyToSetFTrue (cseSet,findCheaperOp,IC_RIGHT(ic),&pdop);
1352 IC_RIGHT(ic) = pdop;
1357 /* if left or right changed then do algebraic */
1360 while(constFold(ic,cseSet));
1363 /* if after all this it becomes a assignment to self
1364 then delete it and continue */
1365 if (ASSIGNMENT_TO_SELF(ic)) {
1366 remiCodeFromeBBlock(ebb,ic);
1370 /* now we will check to see if the entire */
1371 /* operation has been performed before */
1372 /* and is available */
1373 /* don't do assignments they will be killed */
1374 /* by dead code elimination if required do */
1375 /* it only if result is a temporary */
1377 if (!( POINTER_GET(ic) &&
1378 (IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1379 isOperandVolatile(IC_LEFT(ic),TRUE) ||
1380 bitVectBitValue(ebb->ndompset,IC_LEFT(ic)->key))) &&
1382 IS_ITEMP(IC_RESULT(ic)) &&
1384 applyToSet (cseSet,findPrevIc,ic,&pdic);
1385 if (pdic && checkType(operandType(IC_RESULT(pdic)),
1386 operandType(IC_RESULT(ic))) != 1)
1390 /* if found then eliminate this and add to*/
1391 /* to cseSet an element containing result */
1392 /* of this with previous opcode */
1395 if (IS_ITEMP(IC_RESULT(ic))) {
1397 /* replace in the remaining of this block */
1398 replaceAllSymBySym(ic->next,IC_RESULT(ic),IC_RESULT(pdic),&ebb->ndompset);
1399 /* remove this iCode from inexpressions of all
1400 its successors, it cannot be in the in expressions
1401 of any of the predecessors */
1402 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1403 applyToSet(ebb->succList,removeFromInExprs,ic,IC_RESULT(ic),
1404 IC_RESULT(pdic),ebb);
1406 /* if this was moved from another block */
1407 /* then replace in those blocks too */
1408 if ( ic->movedFrom ) {
1410 for (owner = setFirstItem(ic->movedFrom); owner ;
1411 owner = setNextItem(ic->movedFrom))
1412 replaceAllSymBySym(owner->sch,IC_RESULT(ic),IC_RESULT(pdic),&owner->ndompset);
1414 pdic->movedFrom = unionSets(pdic->movedFrom,ic->movedFrom,THROW_NONE);
1417 addSetHead (&cseSet,newCseDef(IC_RESULT(ic),pdic));
1420 /* eliminate this */
1421 remiCodeFromeBBlock (ebb,ic);
1426 if (IS_ITEMP(IC_RESULT(ic)))
1431 /* just add this as a previous expression except in */
1432 /* case of a pointer access in which case this is a */
1433 /* usage not a definition */
1434 if (! (POINTER_SET(ic)) && IC_RESULT(ic)){
1435 deleteItemIf (&cseSet, ifDefSymIsX,IC_RESULT(ic));
1436 addSetHead(&cseSet,newCseDef(IC_RESULT(ic),ic));
1442 /* if assignment to a parameter which is not
1443 mine and type is a pointer then delete
1444 pointerGets to take care of aliasing */
1445 if (ASSIGNMENT(ic) &&
1446 OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) &&
1447 IS_PTR(operandType(IC_RESULT(ic)))) {
1448 deleteGetPointers(&cseSet,&ptrSetSet,IC_RIGHT(ic),ebb);
1449 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1450 applyToSet(ebb->succList,delGetPointerSucc,IC_RIGHT(ic),ebb->dfnum);
1451 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RIGHT(ic)->key);
1454 /* if this is a pointerget then see if we can replace
1455 this with a previously assigned pointer value */
1456 if (POINTER_GET(ic) &&
1457 !(IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1458 isOperandVolatile(IC_LEFT(ic),TRUE))) {
1460 applyToSet(ptrSetSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic));
1461 /* if we find it then locally replace all
1462 references to the result with what we assigned */
1464 replaceAllSymBySym(ic->next,IC_RESULT(ic),pdop,&ebb->ndompset);
1468 /* delete from the cseSet anything that has */
1469 /* operands matching the result of this */
1470 /* except in case of pointer access */
1471 if (!(POINTER_SET(ic)) && IC_RESULT(ic)) {
1472 deleteItemIf (&cseSet,ifOperandsHave,IC_RESULT(ic));
1473 /* delete any previous definitions */
1474 ebb->defSet = bitVectCplAnd (ebb->defSet,OP_DEFS(IC_RESULT(ic)));
1478 /* add the left & right to the defUse set */
1479 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic))) {
1480 OP_USES(IC_LEFT(ic)) =
1481 bitVectSetBit (OP_USES(IC_LEFT(ic)),ic->key);
1482 setUsesDefs(IC_LEFT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1486 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic))) {
1487 OP_USES(IC_RIGHT(ic)) =
1488 bitVectSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
1489 setUsesDefs(IC_RIGHT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1493 /* for the result it is special case, put the result */
1494 /* in the defuseSet if it a pointer or array access */
1495 if ( POINTER_SET(defic) ) {
1496 OP_USES(IC_RESULT(ic)) =
1497 bitVectSetBit (OP_USES(IC_RESULT(ic)),ic->key);
1498 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1499 deleteItemIf(&cseSet,ifPointerGet,IC_RESULT(ic));
1500 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RESULT(ic)->key);
1501 /* delete from inexpressions of all successors which
1502 have dfNum > than this block */
1503 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1504 applyToSet(ebb->succList,delGetPointerSucc,IC_RESULT(ic),ebb->dfnum);
1506 /* delete from cseSet all other pointer sets
1508 deleteItemIf(&ptrSetSet,ifPointerSet,IC_RESULT(ic));
1509 /* add to the local pointerset set */
1510 addSetHead(&ptrSetSet,newCseDef(IC_RESULT(ic),ic));
1512 else /* add the result to defintion set */
1513 if (IC_RESULT(ic)) {
1514 OP_DEFS(IC_RESULT(ic)) =
1515 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1516 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1517 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1518 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1522 /* if this is an addressof instruction then */
1523 /* put the symbol in the address of list & */
1524 /* delete it from the cseSet */
1525 if (defic->op == ADDRESS_OF) {
1526 addSetHead (&ebb->addrOf, IC_LEFT(ic));
1527 deleteItemIf(&cseSet,ifDefSymIsX,IC_LEFT(ic));
1531 setToNull ((void **)&ebb->outExprs);
1532 ebb->outExprs = cseSet;
1533 ebb->outDefs = bitVectUnion (ebb->outDefs,ebb->defSet);
1534 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet,ebb->inPtrsSet);
1538 /*-----------------------------------------------------------------*/
1539 /* cseAllBlocks - will sequentially go thru & do cse for all blocks*/
1540 /*-----------------------------------------------------------------*/
1541 int cseAllBlocks (eBBlock **ebbs,int count)
1546 /* if optimization turned off */
1548 for (i = 0 ; i < count ;i++ )
1549 change += cseBBlock (ebbs[i],FALSE,ebbs,count);