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)
88 for (lic = ic ; lic ; lic = lic->next ) {
91 if (IC_RESULT(lic) && IC_RESULT(lic)->key == from->key ) {
92 /* maintain du chains */
93 if (POINTER_SET(lic)) {
94 bitVectUnSetBit (OP_USES(from),lic->key);
95 OP_USES(to) = bitVectSetBit (OP_USES(to),lic->key);
98 bitVectUnSetBit (OP_DEFS(from),lic->key);
99 OP_DEFS(to) = bitVectSetBit (OP_DEFS(to),lic->key);
101 siaddr = IC_RESULT(lic)->isaddr ;
102 IC_RESULT(lic) = operandFromOperand(to);
103 IC_RESULT(lic)->isaddr = siaddr ;
107 IC_RIGHT(lic) && IC_RIGHT(lic)->key == from->key ) {
108 bitVectUnSetBit (OP_USES(from),lic->key);
109 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
110 siaddr = IC_RIGHT(lic)->isaddr ;
111 IC_RIGHT(lic) = operandFromOperand(to);
112 IC_RIGHT(lic)->isaddr = siaddr ;
116 IC_LEFT(lic) && IC_LEFT(lic)->key == from->key ) {
117 bitVectUnSetBit (OP_USES(from),lic->key);
118 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
119 siaddr = IC_LEFT(lic)->isaddr ;
120 IC_LEFT(lic) = operandFromOperand(to);
121 IC_LEFT(lic)->isaddr = siaddr ;
126 /*-----------------------------------------------------------------*/
127 /* iCodeKeyIs - if the icode keys match then return 1 */
128 /*-----------------------------------------------------------------*/
129 DEFSETFUNC(iCodeKeyIs)
134 if (cdp->diCode->key == key)
140 /*-----------------------------------------------------------------*/
141 /* removeFromInExprs - removes an icode from inexpressions */
142 /*-----------------------------------------------------------------*/
143 DEFSETFUNC(removeFromInExprs)
147 V_ARG(operand *,from);
149 V_ARG(eBBlock *,cbp);
155 deleteItemIf(&ebp->inExprs,iCodeKeyIs,ic->key);
156 if (ebp != cbp && !bitVectBitValue(cbp->domVect,ebp->bbnum))
157 replaceAllSymBySym(ebp->sch,from,to);
159 applyToSet(ebp->succList,removeFromInExprs,ic,from,to,cbp);
163 /*-----------------------------------------------------------------*/
164 /* isGlobalInNearSpace - return TRUE if valriable is a globalin data */
165 /*-----------------------------------------------------------------*/
166 static bool isGlobalInNearSpace (operand *op)
168 link *type = getSpec(operandType(op));
169 /* this is 8051 specific: optimization
170 suggested by Jean-Louis VERN, with 8051s we have no
171 advantage of putting variables in near space into
173 if (isOperandGlobal(op) &&
174 IN_DIRSPACE(SPEC_OCLS(type)))
180 /*-----------------------------------------------------------------*/
181 /* findCheaperOp - cseBBlock support routine, will check to see if */
182 /* we have a operand previously defined */
183 /*-----------------------------------------------------------------*/
184 DEFSETFUNC(findCheaperOp)
187 V_ARG(operand *,cop);
188 V_ARG(operand **,opp);
190 /* if we have already found it */
194 /* not found it yet check if this is the one */
195 /* and this is not the defining one */
196 if (cop->key == cdp->key) {
198 /* do a special check this will help in */
199 /* constant propagation & dead code elim*/
200 /* for assignments only */
201 if (cdp->diCode->op == '=') {
202 /* if the result is volatile then return result */
203 if (IS_OP_VOLATILE (IC_RESULT(cdp->diCode)))
204 *opp = IC_RESULT(cdp->diCode);
206 /* if this is a straight assignment and
207 left is a temp then prefer the temporary to the
209 if (!POINTER_SET(cdp->diCode) &&
210 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
211 IS_TRUE_SYMOP(IC_RIGHT(cdp->diCode)))
212 *opp = IC_RESULT(cdp->diCode);
214 /* if straight assignement && and both
215 are temps then prefer the one that
216 will not need extra space to spil, also
217 take into consideration if right side
218 an induction variable
220 if (!POINTER_SET(cdp->diCode) &&
221 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
222 IS_ITEMP(IC_RIGHT(cdp->diCode)) &&
223 !OP_SYMBOL(IC_RIGHT(cdp->diCode))->isind &&
224 ( (!SPIL_LOC(IC_RIGHT(cdp->diCode)) &&
225 SPIL_LOC(IC_RESULT(cdp->diCode))) ||
226 ( SPIL_LOC(IC_RESULT(cdp->diCode)) &&
227 SPIL_LOC(IC_RESULT(cdp->diCode)) ==
228 SPIL_LOC(IC_RIGHT(cdp->diCode))) )
230 *opp = IC_RESULT(cdp->diCode);
232 *opp = IC_RIGHT(cdp->diCode);
235 *opp = IC_RESULT(cdp->diCode) ;
238 /* if this is an assign to a temp. then check
239 if the right side is this then return this */
240 if (IS_TRUE_SYMOP(cop) &&
241 cdp->diCode->op == '=' &&
242 !POINTER_SET(cdp->diCode) &&
243 cop->key == IC_RIGHT(cdp->diCode)->key &&
244 !isGlobalInNearSpace (IC_RIGHT(cdp->diCode)) &&
245 IS_ITEMP(IC_RESULT(cdp->diCode)))
246 *opp = IC_RESULT(cdp->diCode);
250 if ((isGlobalInNearSpace(cop) &&
251 !isOperandLiteral(*opp)) ||
252 isOperandVolatile(*opp,FALSE)
258 if (cop->key == (*opp)->key ) {
263 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP(cop)) {
264 *opp = operandFromOperand(*opp);
265 (*opp)->isaddr = cop->isaddr;
275 /*-----------------------------------------------------------------*/
276 /* findPointerSet - finds the right side of a pointer set op */
277 /*-----------------------------------------------------------------*/
278 DEFSETFUNC(findPointerSet)
282 V_ARG(operand **,opp);
283 V_ARG(operand *,rop);
285 if (POINTER_SET(cdp->diCode) &&
286 IC_RESULT(cdp->diCode)->key == op->key &&
287 !isOperandVolatile(IC_RESULT(cdp->diCode),TRUE) &&
288 !isOperandVolatile(IC_RIGHT(cdp->diCode),TRUE) &&
289 getSize(operandType(IC_RIGHT(cdp->diCode))) ==
290 getSize(operandType(rop))) {
291 *opp = IC_RIGHT(cdp->diCode);
298 /*-----------------------------------------------------------------*/
299 /* findPrevIc - cseBBlock support function will return the iCode */
300 /* which matches the current one */
301 /*-----------------------------------------------------------------*/
302 DEFSETFUNC(findPrevIc)
308 /* if already found */
312 /* if the iCodes are the same */
313 if (isiCodeEqual(ic,cdp->diCode) &&
314 isOperandEqual(cdp->sym,IC_RESULT(cdp->diCode))) {
319 /* if iCodes are not the same */
320 /* see the operands maybe interchanged */
321 if (ic->op == cdp->diCode->op &&
322 ( ic->op == '+' || ic->op == '*' ) &&
323 isOperandEqual(IC_LEFT(ic),IC_RIGHT(cdp->diCode)) &&
324 isOperandEqual(IC_RIGHT(ic),IC_LEFT(cdp->diCode))) {
332 /*-----------------------------------------------------------------*/
333 /* ifDefGlobal - if definition is global */
334 /*-----------------------------------------------------------------*/
335 DEFSETFUNC(ifDefGlobal)
339 return (isOperandGlobal(cdp->sym));
342 /*-----------------------------------------------------------------*/
343 /* ifOperandsHave - if any of the operand are the same as this */
344 /*-----------------------------------------------------------------*/
345 DEFSETFUNC(ifOperandsHave)
351 if (IC_LEFT(cdp->diCode) &&
352 IS_SYMOP(IC_LEFT(cdp->diCode)) &&
353 IC_LEFT(cdp->diCode)->key == op->key)
356 if (IC_RIGHT(cdp->diCode) &&
357 IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
358 IC_RIGHT(cdp->diCode)->key == op->key)
361 /* or if any of the operands are volatile */
362 if (IC_LEFT(cdp->diCode) &&
363 IS_OP_VOLATILE(IC_LEFT(cdp->diCode)))
366 if (IC_RIGHT(cdp->diCode) &&
367 IS_OP_VOLATILE(IC_RIGHT(cdp->diCode)))
371 if (IC_RESULT(cdp->diCode) &&
372 IS_OP_VOLATILE(IC_RESULT(cdp->diCode)))
378 /*-----------------------------------------------------------------*/
379 /* ifDefSymIs - if a definition is found in the set */
380 /*-----------------------------------------------------------------*/
381 int ifDefSymIs (set *cseSet, operand *sym)
386 if (!sym || !IS_SYMOP(sym))
388 for (sl = cseSet ; sl ; sl = sl->next ) {
390 if (loop->sym->key == sym->key )
397 /*-----------------------------------------------------------------*/
398 /* ifDefSymIsX - will return 1 if the symbols match */
399 /*-----------------------------------------------------------------*/
400 DEFSETFUNC(ifDefSymIsX)
406 return cdp->sym->key == op->key ;
408 return ( isOperandEqual(cdp->sym,op) );
413 /*-----------------------------------------------------------------*/
414 /* ifDiCodeIs - returns truw if diCode is same */
415 /*-----------------------------------------------------------------*/
416 int ifDiCodeIs (set *cseSet, iCode *ic)
424 for (sl = cseSet ; sl ; sl = sl->next ) {
426 if (loop->diCode == ic)
433 /*-----------------------------------------------------------------*/
434 /* ifPointerGet - returns true if the icode is pointer get sym */
435 /*-----------------------------------------------------------------*/
436 DEFSETFUNC(ifPointerGet)
440 iCode *dic = cdp->diCode;
441 operand *left = IC_LEFT(cdp->diCode);
443 if (POINTER_GET(dic) && left->key == op->key)
449 /*-----------------------------------------------------------------*/
450 /* ifPointerSet - returns true if the icode is pointer set sym */
451 /*-----------------------------------------------------------------*/
452 DEFSETFUNC(ifPointerSet)
457 if (POINTER_SET(cdp->diCode) &&
458 IC_RESULT(cdp->diCode)->key == op->key)
464 /*-----------------------------------------------------------------*/
465 /* ifDiCodeIsX - will return 1 if the symbols match */
466 /*-----------------------------------------------------------------*/
467 DEFSETFUNC(ifDiCodeIsX)
472 return cdp->diCode == ic;
476 /*-----------------------------------------------------------------*/
477 /* algebraicOpts - does some algebraic optimizations */
478 /*-----------------------------------------------------------------*/
479 void algebraicOpts (iCode *ic)
481 /* we don't deal with the following iCodes
492 /* if both operands present & ! IFX */
493 /* then if they are both literal we */
494 /* perform the operation right now */
498 IS_OP_LITERAL(IC_LEFT(ic)) &&
499 IS_OP_LITERAL(IC_RIGHT(ic))) {
501 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
504 operandType(IC_RESULT(ic)));
507 SET_RESULT_RIGHT(ic);
511 /* if not ifx & only one operand present */
514 IS_OP_LITERAL(IC_LEFT(ic)) &&
517 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
520 operandType(IC_RESULT(ic)));
523 SET_RESULT_RIGHT(ic);
528 /* a special case : or in short a kludgy solution will think
529 about a better solution over a glass of wine someday */
530 if ( ic->op == GET_VALUE_AT_ADDRESS ) {
532 if (IS_ITEMP(IC_RESULT(ic)) &&
533 IS_TRUE_SYMOP(IC_LEFT(ic))) {
536 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
537 IC_RIGHT(ic)->isaddr = 0;
539 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
540 IC_RESULT(ic)->isaddr = 0;
541 setOperandType(IC_RESULT(ic),operandType(IC_RIGHT(ic)));
545 if (IS_ITEMP(IC_LEFT(ic)) &&
546 IS_ITEMP(IC_RESULT(ic)) &&
547 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
548 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
549 !IC_LEFT(ic)->isaddr ) {
551 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
552 IC_RIGHT(ic)->isaddr = 0;
553 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
554 IC_RESULT(ic)->isaddr = 0;
562 /* depending on the operation */
565 /* if adding the same thing change to left shift by 1*/
566 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key &&
567 !IS_FLOAT(operandType(IC_RESULT(ic)))) {
569 IC_RIGHT(ic) = operandFromLit(1);
572 /* if addition then check if one of them is a zero */
573 /* if yes turn it into assignmnt*/
574 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
575 operandLitValue(IC_LEFT(ic)) == 0.0 ) {
579 SET_ISADDR(IC_RESULT(ic),0);
580 SET_ISADDR(IC_RIGHT(ic),0);
583 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
584 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
587 IC_RIGHT(ic) = IC_LEFT(ic) ;
589 SET_ISADDR(IC_RIGHT(ic),0);
590 SET_ISADDR(IC_RESULT(ic),0);
595 /* if subtracting the the same thing then zero */
596 if ( IC_LEFT(ic)->key == IC_RIGHT(ic)->key ) {
598 IC_RIGHT(ic) = operandFromLit(0);
600 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
601 IC_RESULT(ic)->isaddr = 0;
605 /* if subtraction then check if one of the operand */
606 /* is zero then depending on which operand change */
607 /* to assignment or unary minus */
608 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
609 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
610 /* right size zero change to assignment */
612 IC_RIGHT(ic) = IC_LEFT(ic);
614 SET_ISADDR(IC_RIGHT(ic),0);
615 SET_ISADDR(IC_RESULT(ic),0);
618 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
619 operandLitValue (IC_LEFT(ic)) == 0.0) {
620 /* left zero turn into an unary minus */
621 ic->op = UNARYMINUS ;
622 IC_LEFT(ic) = IC_RIGHT(ic);
623 IC_RIGHT(ic) = NULL ;
627 /* if multiplication then check if either of */
628 /* them is zero then the result is zero */
629 /* if either of them is one then result is */
632 if (IS_OP_LITERAL(IC_LEFT(ic))) {
634 if (operandLitValue(IC_LEFT(ic)) == 0.0) {
636 IC_RIGHT(ic) = IC_LEFT(ic);
638 SET_RESULT_RIGHT(ic);
641 if ( operandLitValue(IC_LEFT(ic)) == 1.0) {
644 SET_RESULT_RIGHT(ic);
649 if (IS_OP_LITERAL(IC_RIGHT(ic))) {
651 if (operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
654 SET_RESULT_RIGHT(ic);
658 if (operandLitValue(IC_RIGHT(ic)) == 1.0) {
660 IC_RIGHT(ic) = IC_LEFT(ic);
662 SET_RESULT_RIGHT(ic);
668 /* if division by self then 1 */
669 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key) {
671 IC_RIGHT(ic) = operandFromLit(1);
673 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
674 IC_RESULT(ic)->isaddr = 0;
676 /* if this is a division then check if right */
677 /* is one then change it to an assignment */
678 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
679 operandLitValue(IC_RIGHT(ic)) == 1.0 ) {
682 IC_RIGHT(ic) = IC_LEFT(ic);
684 SET_RESULT_RIGHT(ic);
688 /* if both are the same for an comparison operators */
692 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
694 IC_RIGHT(ic) = operandFromLit(1);
696 SET_RESULT_RIGHT(ic);
702 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
704 IC_RIGHT(ic) = operandFromLit(0);
706 SET_RESULT_RIGHT(ic);
710 /* if this is a cast of a literal value */
711 if ( IS_OP_LITERAL(IC_RIGHT(ic))) {
714 operandFromValue (valCastLiteral(operandType(IC_LEFT(ic)),
715 operandLitValue(IC_RIGHT(ic))));
717 SET_ISADDR(IC_RESULT(ic),0);
719 /* if casting to the same */
720 if ( checkType(operandType(IC_RESULT(ic)),
721 operandType(IC_RIGHT(ic))) == 1) {
724 SET_ISADDR(IC_RESULT(ic),0);
728 if (IS_OP_LITERAL(IC_LEFT(ic))) {
731 (operandLitValue(IC_LEFT(ic)) == 0 ?
732 operandFromLit(1) : operandFromLit(0));
734 SET_ISADDR(IC_RESULT(ic),0);
740 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
741 /*-----------------------------------------------------------------*/
742 /* updateSpillLocation - keeps track of register spill location */
743 /*-----------------------------------------------------------------*/
744 void updateSpillLocation ( iCode *ic)
755 /* for the form true_symbol := iTempNN */
756 if (ASSIGN_ITEMP_TO_SYM(ic)
757 && !SPIL_LOC(IC_RIGHT(ic))) {
759 setype = getSpec(operandType(IC_RESULT(ic)));
761 if (!IC_RIGHT(ic)->noSpilLoc &&
762 !IS_VOLATILE(setype) &&
763 !IN_FARSPACE(SPEC_OCLS(setype)) &&
764 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
766 SPIL_LOC(IC_RIGHT(ic)) =
767 IC_RESULT(ic)->operand.symOperand;
770 if (ASSIGN_ITEMP_TO_ITEMP(ic) &&
771 !SPIL_LOC(IC_RIGHT(ic)) &&
772 !bitVectBitsInCommon(OP_DEFS(IC_RIGHT(ic)),OP_USES(IC_RESULT(ic))) &&
773 OP_SYMBOL(IC_RESULT(ic))->isreqv) {
775 setype = getSpec(operandType(IC_RESULT(ic)));
777 if (!IC_RIGHT(ic)->noSpilLoc &&
778 !IS_VOLATILE(setype) &&
779 !IN_FARSPACE(SPEC_OCLS(setype)) &&
780 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
782 SPIL_LOC(IC_RIGHT(ic)) =
783 SPIL_LOC(IC_RESULT(ic));
787 /*-----------------------------------------------------------------*/
788 /* setUsesDef - sets the uses def bitvector for a given operand */
789 /*-----------------------------------------------------------------*/
790 void setUsesDefs (operand *op, bitVect *bdefs,
791 bitVect *idefs, bitVect **oud)
793 /* compute the definitions alive at this point */
794 bitVect *adefs = bitVectUnion(bdefs,idefs);
796 /* of these definitions find the ones that are */
797 /* for this operand */
798 adefs = bitVectIntersect(adefs,OP_DEFS(op));
800 /* these are the definitions that this operand can use */
801 op->usesDefs = adefs;
803 /* the out defs is an union */
804 *oud = bitVectUnion(*oud,adefs);
807 /*-----------------------------------------------------------------*/
808 /* unsetDefsAndUses - clear this operation for the operands */
809 /*-----------------------------------------------------------------*/
810 void unsetDefsAndUses ( iCode *ic )
812 if ( ic->op == JUMPTABLE)
815 /* take away this definition from the def chain of the */
816 /* result & take away from use set of the operands */
818 /* turn off def set */
819 if (IS_SYMOP(IC_RESULT(ic))) {
820 if ( !POINTER_SET(ic))
821 bitVectUnSetBit(OP_DEFS(IC_RESULT(ic)),ic->key);
823 bitVectUnSetBit(OP_USES(IC_RESULT(ic)),ic->key);
825 /* turn off the useSet for the operands */
826 if (IS_SYMOP(IC_LEFT(ic)))
827 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
829 if (IS_SYMOP(IC_RIGHT(ic)))
830 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
832 else /* must be ifx turn off the use */
833 if (IS_SYMOP(IC_COND(ic)))
834 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
837 /*-----------------------------------------------------------------*/
838 /* ifxOptimize - changes ifx conditions if it can */
839 /*-----------------------------------------------------------------*/
840 void ifxOptimize (iCode *ic, set *cseSet,
842 eBBlock *ebb, int *change,
843 eBBlock **ebbs, int count)
848 /* if the condition can be replaced */
851 applyToSetFTrue (cseSet,findCheaperOp,IC_COND(ic),&pdop);
858 /* if the conditional is a literal then */
859 if (IS_OP_LITERAL(IC_COND(ic))) {
861 if ( (operandLitValue(IC_COND(ic)) != 0.0) && IC_TRUE(ic)) {
863 /* change to a goto */
865 IC_LABEL(ic) = IC_TRUE(ic);
870 if (!operandLitValue(IC_COND(ic)) && IC_FALSE(ic)) {
872 IC_LABEL(ic) = IC_FALSE(ic);
876 /* then kill this if condition */
877 remiCodeFromeBBlock (ebb,ic);
881 /* now we need to recompute the control flow */
882 /* since the control flow has changed */
883 /* this is very expensive but it does not happen */
884 /* too often, if it does happen then the user pays */
886 computeControlFlow (ebbs,count,1);
887 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
891 /* if there is only one successor and that successor
892 is the same one we are conditionally going to then
893 we can remove this conditional statement */
894 label = (IC_TRUE(ic) ? IC_TRUE(ic) : IC_FALSE(ic));
895 if (elementsInSet(ebb->succList) == 1 &&
896 isinSet(ebb->succList,eBBWithEntryLabel(ebbs,label,count))) {
898 remiCodeFromeBBlock(ebb,ic);
899 computeControlFlow (ebbs,count,1);
900 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
905 /* if it remains an IFX the update the use Set */
906 OP_USES(IC_COND(ic)) = bitVectSetBit(OP_USES(IC_COND(ic)),ic->key);
907 setUsesDefs(IC_COND(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
911 /*-----------------------------------------------------------------*/
912 /* diCodeForSym - finds the definiting instruction for a symbol */
913 /*-----------------------------------------------------------------*/
914 DEFSETFUNC(diCodeForSym)
917 V_ARG(operand *,sym);
920 /* if already found */
924 /* if not if this is the defining iCode */
925 if (sym->key == cdp->key) {
933 /*-----------------------------------------------------------------*/
934 /* constFold - does some constant folding */
935 /*-----------------------------------------------------------------*/
936 int constFold (iCode *ic, set *cseSet)
939 /* this routine will change
945 /* deal with only + & - */
950 /* this check is a hueristic to prevent live ranges
951 from becoming too long */
952 if (IS_PTR(operandType(IC_RESULT(ic))))
955 /* check if operation with a literal */
956 if (!IS_OP_LITERAL(IC_RIGHT(ic)))
959 /* check if we can find a definition for the
961 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(ic),&dic)))
964 /* check that this is also a +/- */
965 if (dic->op != '+' && dic->op != '-')
969 if (!IS_OP_LITERAL(IC_RIGHT(dic)))
972 /* it is if the operations are the same*/
973 /* the literal parts need to be added */
974 IC_LEFT(ic) = operandFromOperand(IC_LEFT(dic));
975 if (ic->op == dic->op )
976 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic))+
977 operandLitValue(IC_RIGHT(dic)));
979 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) -
980 operandLitValue(IC_RIGHT(dic)));
982 if (IS_ITEMP(IC_RESULT(ic))) {
983 SPIL_LOC(IC_RESULT(ic)) = NULL;
984 IC_RESULT(ic)->noSpilLoc = 1;
991 /*-----------------------------------------------------------------*/
992 /* deleteGetPointers - called when a pointer is passed as parm */
993 /* will delete from cseSet all get pointers computed from this */
994 /* pointer. A simple ifOperandsHave is not good enough here */
995 /*-----------------------------------------------------------------*/
996 static void deleteGetPointers (set **cseSet, set **pss, operand *op,eBBlock *ebb)
998 set *compItems = NULL;
1003 if (!*cseSet && !*pss)
1006 /* first find all items computed from this operand .
1007 This done fairly simply go thru the list and find
1008 those that are computed by arthimetic with this
1010 for (cdp = setFirstItem(*cseSet); cdp ; cdp = setNextItem(*cseSet)) {
1011 if (IS_ARITHMETIC_OP(cdp->diCode)) {
1012 if (isOperandEqual(IC_LEFT(cdp->diCode),op) ||
1013 isOperandEqual(IC_RIGHT(cdp->diCode),op)) {
1014 /* save it in our list of items */
1015 addSet(&compItems,IC_RESULT(cdp->diCode));
1017 /* also check for those computed from our computed
1018 list . This will take care of situations like
1019 iTemp1 = iTemp0 + 8;
1020 iTemp2 = iTemp1 + 8; */
1021 if (isinSetWith(compItems,IC_LEFT(cdp->diCode),isOperandEqual) ||
1022 isinSetWith(compItems,IC_RIGHT(cdp->diCode),isOperandEqual)) {
1023 addSet(&compItems,IC_RESULT(cdp->diCode));
1028 /* now delete all pointer gets with this op */
1029 deleteItemIf(cseSet,ifPointerGet,op);
1030 deleteItemIf(pss,ifPointerSet,op);
1032 /* set the bit vector used by dataFlow computation later */
1033 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,op->key);
1034 /* now for the computed items */
1035 for (cop = setFirstItem(compItems); cop ; cop = setNextItem(compItems)) {
1036 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,cop->key);
1037 deleteItemIf(cseSet,ifPointerGet,cop);
1038 deleteItemIf(pss,ifPointerSet,cop);
1042 /*-----------------------------------------------------------------*/
1043 /* delGetPointerSucc - delete get pointer from inExprs of succ with*/
1044 /* dfnum > supplied */
1045 /*-----------------------------------------------------------------*/
1046 DEFSETFUNC(delGetPointerSucc)
1048 eBBlock *ebp = item;
1049 V_ARG(operand *,op);
1056 if (ebp->dfnum > dfnum) {
1057 deleteItemIf(&ebp->inExprs,ifPointerGet,op);
1060 return applyToSet(ebp->succList,delGetPointerSucc,op,dfnum);
1063 /*-----------------------------------------------------------------*/
1064 /* cseBBlock - common subexpression elimination for basic blocks */
1065 /* this is the hackiest kludgiest routine in the whole */
1066 /* system. also the most important, since almost all */
1067 /* data flow related information is computed by it */
1068 /*-----------------------------------------------------------------*/
1069 int cseBBlock ( eBBlock *ebb, int computeOnly,
1070 eBBlock **ebbs, int count)
1076 set *ptrSetSet = NULL;
1078 /* if this block is not reachable */
1082 /* set of common subexpressions */
1083 cseSet = setFromSet (ebb->inExprs) ;
1085 /* these will be computed by this routine */
1086 setToNull ((void **)&ebb->outDefs);
1087 setToNull ((void **)&ebb->defSet);
1088 setToNull ((void **)&ebb->usesDefs);
1089 setToNull ((void **)&ebb->ptrsSet);
1090 setToNull ((void **)&ebb->addrOf);
1091 setToNull ((void **)&ebb->ldefs);
1093 ebb->outDefs = bitVectCopy (ebb->inDefs);
1094 bitVectDefault = iCodeKey;
1095 ebb->defSet = newBitVect(iCodeKey);
1096 ebb->usesDefs=newBitVect(iCodeKey);
1098 /* for all the instructions in this block do */
1099 for (ic = ebb->sch ; ic ; ic = ic->next ) {
1108 /* clear the def & use chains for the operands involved */
1109 /* in this operation . since it can change due to opts */
1110 unsetDefsAndUses (ic);
1112 if ( ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE) {
1113 /* add to defSet of the symbol */
1114 OP_DEFS(IC_RESULT(ic)) =
1115 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1116 /* add to the definition set of this block */
1117 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1118 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1119 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1120 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1121 /* delete global variables from the cseSet
1122 since they can be modified by the function call */
1123 deleteItemIf(&cseSet,ifDefGlobal);
1126 /* for pcall & ipush we need to add to the useSet */
1127 if ((ic->op == PCALL ||
1131 IS_SYMOP(IC_LEFT(ic))) {
1133 /* check if they can be replaced */
1134 if ( !computeOnly ) {
1136 applyToSetFTrue(cseSet,findCheaperOp,IC_LEFT(ic),&pdop);
1138 IC_LEFT(ic) = pdop ;
1140 /* the lookup could have changed it*/
1141 if (IS_SYMOP(IC_LEFT(ic))) {
1142 OP_USES(IC_LEFT(ic)) =
1143 bitVectSetBit(OP_USES(IC_LEFT(ic)),ic->key);
1144 setUsesDefs(IC_LEFT(ic),ebb->defSet,
1145 ebb->outDefs,&ebb->usesDefs);
1149 /* if we a sending a pointer as a parameter
1150 then kill all cse since the pointed to item
1151 might be changed in the function being called */
1152 if ((ic->op == IPUSH || ic->op == SEND) &&
1153 IS_PTR(operandType(IC_LEFT(ic)))) {
1154 deleteGetPointers(&cseSet,&ptrSetSet,IC_LEFT(ic),ebb);
1155 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_LEFT(ic)->key);
1156 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1157 applyToSet(ebb->succList,delGetPointerSucc,
1158 IC_LEFT(ic),ebb->dfnum);
1163 /* if jumptable then mark the usage */
1164 if (ic->op == JUMPTABLE ) {
1165 OP_USES(IC_JTCOND(ic)) =
1166 bitVectSetBit(OP_USES(IC_JTCOND(ic)),ic->key);
1167 setUsesDefs(IC_JTCOND(ic),ebb->defSet,
1168 ebb->outDefs,&ebb->usesDefs);
1175 /* do some algebraic optimizations if possible */
1177 while (constFold(ic,cseSet));
1180 if (POINTER_GET(ic) && !IS_PTR(operandType(IC_LEFT(ic)))) {
1181 setOperandType(IC_LEFT(ic),
1182 aggrToPtr(operandType(IC_LEFT(ic)),FALSE));
1184 if (POINTER_SET(ic) && !IS_PTR(operandType(IC_RESULT(ic)))) {
1185 setOperandType(IC_RESULT(ic),
1186 aggrToPtr(operandType(IC_RESULT(ic)),FALSE));
1189 /* if this is a condition statment then */
1190 /* check if the condition can be replaced */
1191 if (ic->op == IFX ) {
1192 ifxOptimize (ic, cseSet, computeOnly,
1198 /* if the assignment & result is a temp */
1199 /* see if we can replace it */
1200 if (ic->op == '=') {
1202 /* update the spill location for this */
1203 updateSpillLocation (ic);
1205 if (POINTER_SET(ic)) {
1207 applyToSetFTrue (cseSet,findCheaperOp,IC_RESULT(ic),&pdop);
1208 if (pdop && IS_ITEMP(pdop) && !computeOnly)
1209 IC_RESULT(ic) = pdop;
1213 /* do the operand lookup i.e. for both the */
1214 /* right & left operand : check the cseSet */
1215 /* to see if they have been replaced if yes*/
1216 /* then replace them with those from cseSet*/
1218 /* and left is a symbol */
1219 if (IS_SYMOP(IC_LEFT(ic)) &&
1220 !computeOnly && ic->op != ADDRESS_OF ) {
1223 applyToSetFTrue (cseSet,findCheaperOp,IC_LEFT(ic),&pdop) ;
1225 if (POINTER_GET(ic)) {
1226 if (IS_ITEMP(pdop) || IS_OP_LITERAL(pdop)) {
1230 /* check if there is a pointer set
1231 for the same pointer visible if yes
1232 then change this into an assignment */
1234 if (applyToSetFTrue(cseSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic)) &&
1235 !bitVectBitValue(ebb->ptrsSet,pdop->key)){
1238 IC_RIGHT(ic) = pdop;
1239 SET_ISADDR(IC_RESULT(ic),0);
1244 IC_LEFT(ic) = pdop ;
1251 if (IS_SYMOP(IC_RIGHT(ic)) && !computeOnly) {
1254 applyToSetFTrue (cseSet,findCheaperOp,IC_RIGHT(ic),&pdop);
1257 IC_RIGHT(ic) = pdop;
1262 /* if left or right changed then do algebraic */
1265 while(constFold(ic,cseSet));
1268 /* if after all this it becomes a assignment to self
1269 then delete it and continue */
1270 if (ASSIGNMENT_TO_SELF(ic)) {
1271 remiCodeFromeBBlock(ebb,ic);
1275 /* now we will check to see if the entire */
1276 /* operation has been performed before */
1277 /* and is available */
1278 /* don't do assignments they will be killed */
1279 /* by dead code elimination if required do */
1280 /* it only if result is a temporary */
1282 if (!( POINTER_GET(ic) &&
1283 (IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1284 isOperandVolatile(IC_LEFT(ic),TRUE))) &&
1286 IS_ITEMP(IC_RESULT(ic)) &&
1288 applyToSet (cseSet,findPrevIc,ic,&pdic);
1291 /* if found then eliminate this and add to*/
1292 /* to cseSet an element containing result */
1293 /* of this with previous opcode */
1296 if (IS_ITEMP(IC_RESULT(ic))) {
1298 /* replace in the remaining of this block */
1299 replaceAllSymBySym(ic->next,IC_RESULT(ic),IC_RESULT(pdic));
1300 /* remove this iCode from inexpressions of all
1301 its successors, it cannot be in the in expressions
1302 of any of the predecessors */
1303 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1304 applyToSet(ebb->succList,removeFromInExprs,ic,IC_RESULT(ic),
1305 IC_RESULT(pdic),ebb);
1307 /* if this was moved from another block */
1308 /* then replace in those blocks too */
1309 if ( ic->movedFrom ) {
1311 for (owner = setFirstItem(ic->movedFrom); owner ;
1312 owner = setNextItem(ic->movedFrom))
1313 replaceAllSymBySym(owner->sch,IC_RESULT(ic),IC_RESULT(pdic));
1315 pdic->movedFrom = unionSets(pdic->movedFrom,ic->movedFrom,THROW_NONE);
1318 addSetHead (&cseSet,newCseDef(IC_RESULT(ic),pdic));
1321 /* eliminate this */
1322 remiCodeFromeBBlock (ebb,ic);
1327 if (IS_ITEMP(IC_RESULT(ic)))
1332 /* just add this as a previous expression except in */
1333 /* case of a pointer access in which case this is a */
1334 /* usage not a definition */
1335 if (! (POINTER_SET(ic)) && IC_RESULT(ic)){
1336 deleteItemIf (&cseSet, ifDefSymIsX,IC_RESULT(ic));
1337 addSetHead(&cseSet,newCseDef(IC_RESULT(ic),ic));
1343 /* if assignment to a parameter which is not
1344 mine and type is a pointer then delete
1345 pointerGets to take care of aliasing */
1346 if (ASSIGNMENT(ic) &&
1347 OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) &&
1348 IS_PTR(operandType(IC_RESULT(ic)))) {
1349 deleteGetPointers(&cseSet,&ptrSetSet,IC_RIGHT(ic),ebb);
1350 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1351 applyToSet(ebb->succList,delGetPointerSucc,IC_RIGHT(ic),ebb->dfnum);
1352 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RIGHT(ic)->key);
1355 /* if this is a pointerget then see if we can replace
1356 this with a previously assigned pointer value */
1357 if (POINTER_GET(ic) &&
1358 !(IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1359 isOperandVolatile(IC_LEFT(ic),TRUE))) {
1361 applyToSet(ptrSetSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic));
1362 /* if we find it then locally replace all
1363 references to the result with what we assigned */
1365 replaceAllSymBySym(ic->next,IC_RESULT(ic),pdop);
1369 /* delete from the cseSet anything that has */
1370 /* operands matching the result of this */
1371 /* except in case of pointer access */
1372 if (!(POINTER_SET(ic)) && IC_RESULT(ic)) {
1373 deleteItemIf (&cseSet,ifOperandsHave,IC_RESULT(ic));
1374 /* delete any previous definitions */
1375 ebb->defSet = bitVectCplAnd (ebb->defSet,OP_DEFS(IC_RESULT(ic)));
1379 /* add the left & right to the defUse set */
1380 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic))) {
1381 OP_USES(IC_LEFT(ic)) =
1382 bitVectSetBit (OP_USES(IC_LEFT(ic)),ic->key);
1383 setUsesDefs(IC_LEFT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1387 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic))) {
1388 OP_USES(IC_RIGHT(ic)) =
1389 bitVectSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
1390 setUsesDefs(IC_RIGHT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1394 /* for the result it is special case, put the result */
1395 /* in the defuseSet if it a pointer or array access */
1396 if ( POINTER_SET(defic) ) {
1397 OP_USES(IC_RESULT(ic)) =
1398 bitVectSetBit (OP_USES(IC_RESULT(ic)),ic->key);
1399 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1400 deleteItemIf(&cseSet,ifPointerGet,IC_RESULT(ic));
1401 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RESULT(ic)->key);
1402 /* delete from inexpressions of all successors which
1403 have dfNum > than this block */
1404 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1405 applyToSet(ebb->succList,delGetPointerSucc,IC_RESULT(ic),ebb->dfnum);
1407 /* delete from cseSet all other pointer sets
1409 deleteItemIf(&ptrSetSet,ifPointerSet,IC_RESULT(ic));
1410 /* add to the local pointerset set */
1411 addSetHead(&ptrSetSet,newCseDef(IC_RESULT(ic),ic));
1413 else /* add the result to defintion set */
1414 if (IC_RESULT(ic)) {
1415 OP_DEFS(IC_RESULT(ic)) =
1416 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1417 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1418 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1419 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1423 /* if this is an addressof instruction then */
1424 /* put the symbol in the address of list & */
1425 /* delete it from the cseSet */
1426 if (defic->op == ADDRESS_OF) {
1427 addSetHead (&ebb->addrOf, IC_LEFT(ic));
1428 deleteItemIf(&cseSet,ifDefSymIsX,IC_LEFT(ic));
1432 setToNull ((void **)&ebb->outExprs);
1433 ebb->outExprs = cseSet;
1434 ebb->outDefs = bitVectUnion (ebb->outDefs,ebb->defSet);
1435 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet,ebb->inPtrsSet);
1439 /*-----------------------------------------------------------------*/
1440 /* cseAllBlocks - will sequentially go thru & do cse for all blocks*/
1441 /*-----------------------------------------------------------------*/
1442 int cseAllBlocks (eBBlock **ebbs,int count)
1447 /* if optimization turned off */
1449 for (i = 0 ; i < count ;i++ )
1450 change += cseBBlock (ebbs[i],FALSE,ebbs,count);