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 /* 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);
127 bitVectUnSetBit (OP_DEFS(from),lic->key);
128 OP_DEFS(to) = bitVectSetBit (OP_DEFS(to),lic->key);
130 siaddr = IC_RESULT(lic)->isaddr ;
131 IC_RESULT(lic) = operandFromOperand(to);
132 IC_RESULT(lic)->isaddr = siaddr ;
136 IC_RIGHT(lic) && IC_RIGHT(lic)->key == from->key ) {
137 bitVectUnSetBit (OP_USES(from),lic->key);
138 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
139 siaddr = IC_RIGHT(lic)->isaddr ;
140 IC_RIGHT(lic) = operandFromOperand(to);
141 IC_RIGHT(lic)->isaddr = siaddr ;
145 IC_LEFT(lic) && IC_LEFT(lic)->key == from->key ) {
146 bitVectUnSetBit (OP_USES(from),lic->key);
147 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
148 siaddr = IC_LEFT(lic)->isaddr ;
149 IC_LEFT(lic) = operandFromOperand(to);
150 IC_LEFT(lic)->isaddr = siaddr ;
155 /*-----------------------------------------------------------------*/
156 /* iCodeKeyIs - if the icode keys match then return 1 */
157 /*-----------------------------------------------------------------*/
158 DEFSETFUNC(iCodeKeyIs)
163 if (cdp->diCode->key == key)
169 /*-----------------------------------------------------------------*/
170 /* removeFromInExprs - removes an icode from inexpressions */
171 /*-----------------------------------------------------------------*/
172 DEFSETFUNC(removeFromInExprs)
176 V_ARG(operand *,from);
178 V_ARG(eBBlock *,cbp);
184 deleteItemIf(&ebp->inExprs,iCodeKeyIs,ic->key);
185 if (ebp != cbp && !bitVectBitValue(cbp->domVect,ebp->bbnum))
186 replaceAllSymBySym(ebp->sch,from,to);
188 applyToSet(ebp->succList,removeFromInExprs,ic,from,to,cbp);
192 /*-----------------------------------------------------------------*/
193 /* isGlobalInNearSpace - return TRUE if valriable is a globalin data */
194 /*-----------------------------------------------------------------*/
195 static bool isGlobalInNearSpace (operand *op)
197 link *type = getSpec(operandType(op));
198 /* this is 8051 specific: optimization
199 suggested by Jean-Louis VERN, with 8051s we have no
200 advantage of putting variables in near space into
202 if (isOperandGlobal(op) &&
203 IN_DIRSPACE(SPEC_OCLS(type)))
209 /*-----------------------------------------------------------------*/
210 /* findCheaperOp - cseBBlock support routine, will check to see if */
211 /* we have a operand previously defined */
212 /*-----------------------------------------------------------------*/
213 DEFSETFUNC(findCheaperOp)
216 V_ARG(operand *,cop);
217 V_ARG(operand **,opp);
219 /* if we have already found it */
223 /* not found it yet check if this is the one */
224 /* and this is not the defining one */
225 if (cop->key == cdp->key) {
227 /* do a special check this will help in */
228 /* constant propagation & dead code elim*/
229 /* for assignments only */
230 if (cdp->diCode->op == '=') {
231 /* if the result is volatile then return result */
232 if (IS_OP_VOLATILE (IC_RESULT(cdp->diCode)))
233 *opp = IC_RESULT(cdp->diCode);
235 /* if this is a straight assignment and
236 left is a temp then prefer the temporary to the
238 if (!POINTER_SET(cdp->diCode) &&
239 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
240 IS_TRUE_SYMOP(IC_RIGHT(cdp->diCode)))
241 *opp = IC_RESULT(cdp->diCode);
243 /* if straight assignement && and both
244 are temps then prefer the one that
245 will not need extra space to spil, also
246 take into consideration if right side
247 an induction variable
249 if (!POINTER_SET(cdp->diCode) &&
250 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
251 IS_ITEMP(IC_RIGHT(cdp->diCode)) &&
252 !OP_SYMBOL(IC_RIGHT(cdp->diCode))->isind &&
253 ( (!SPIL_LOC(IC_RIGHT(cdp->diCode)) &&
254 SPIL_LOC(IC_RESULT(cdp->diCode))) ||
255 ( SPIL_LOC(IC_RESULT(cdp->diCode)) &&
256 SPIL_LOC(IC_RESULT(cdp->diCode)) ==
257 SPIL_LOC(IC_RIGHT(cdp->diCode))) )
259 *opp = IC_RESULT(cdp->diCode);
261 *opp = IC_RIGHT(cdp->diCode);
264 *opp = IC_RESULT(cdp->diCode) ;
267 /* if this is an assign to a temp. then check
268 if the right side is this then return this */
269 if (IS_TRUE_SYMOP(cop) &&
270 cdp->diCode->op == '=' &&
271 !POINTER_SET(cdp->diCode) &&
272 cop->key == IC_RIGHT(cdp->diCode)->key &&
273 !isGlobalInNearSpace (IC_RIGHT(cdp->diCode)) &&
274 IS_ITEMP(IC_RESULT(cdp->diCode)))
275 *opp = IC_RESULT(cdp->diCode);
279 if ((isGlobalInNearSpace(cop) &&
280 !isOperandLiteral(*opp)) ||
281 isOperandVolatile(*opp,FALSE)
287 if (cop->key == (*opp)->key ) {
292 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP(cop)) {
293 *opp = operandFromOperand(*opp);
294 (*opp)->isaddr = cop->isaddr;
304 /*-----------------------------------------------------------------*/
305 /* findPointerSet - finds the right side of a pointer set op */
306 /*-----------------------------------------------------------------*/
307 DEFSETFUNC(findPointerSet)
311 V_ARG(operand **,opp);
312 V_ARG(operand *,rop);
314 if (POINTER_SET(cdp->diCode) &&
315 IC_RESULT(cdp->diCode)->key == op->key &&
316 !isOperandVolatile(IC_RESULT(cdp->diCode),TRUE) &&
317 !isOperandVolatile(IC_RIGHT(cdp->diCode),TRUE) &&
318 getSize(operandType(IC_RIGHT(cdp->diCode))) ==
319 getSize(operandType(rop))) {
320 *opp = IC_RIGHT(cdp->diCode);
327 /*-----------------------------------------------------------------*/
328 /* findPrevIc - cseBBlock support function will return the iCode */
329 /* which matches the current one */
330 /*-----------------------------------------------------------------*/
331 DEFSETFUNC(findPrevIc)
337 /* if already found */
341 /* if the iCodes are the same */
342 if (isiCodeEqual(ic,cdp->diCode) &&
343 isOperandEqual(cdp->sym,IC_RESULT(cdp->diCode))) {
348 /* if iCodes are not the same */
349 /* see the operands maybe interchanged */
350 if (ic->op == cdp->diCode->op &&
351 ( ic->op == '+' || ic->op == '*' ) &&
352 isOperandEqual(IC_LEFT(ic),IC_RIGHT(cdp->diCode)) &&
353 isOperandEqual(IC_RIGHT(ic),IC_LEFT(cdp->diCode))) {
361 /*-----------------------------------------------------------------*/
362 /* ifDefGlobal - if definition is global */
363 /*-----------------------------------------------------------------*/
364 DEFSETFUNC(ifDefGlobal)
368 return (isOperandGlobal(cdp->sym));
371 /*-----------------------------------------------------------------*/
372 /* ifOperandsHave - if any of the operand are the same as this */
373 /*-----------------------------------------------------------------*/
374 DEFSETFUNC(ifOperandsHave)
380 if (IC_LEFT(cdp->diCode) &&
381 IS_SYMOP(IC_LEFT(cdp->diCode)) &&
382 IC_LEFT(cdp->diCode)->key == op->key)
385 if (IC_RIGHT(cdp->diCode) &&
386 IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
387 IC_RIGHT(cdp->diCode)->key == op->key)
390 /* or if any of the operands are volatile */
391 if (IC_LEFT(cdp->diCode) &&
392 IS_OP_VOLATILE(IC_LEFT(cdp->diCode)))
395 if (IC_RIGHT(cdp->diCode) &&
396 IS_OP_VOLATILE(IC_RIGHT(cdp->diCode)))
400 if (IC_RESULT(cdp->diCode) &&
401 IS_OP_VOLATILE(IC_RESULT(cdp->diCode)))
407 /*-----------------------------------------------------------------*/
408 /* ifDefSymIs - if a definition is found in the set */
409 /*-----------------------------------------------------------------*/
410 int ifDefSymIs (set *cseSet, operand *sym)
415 if (!sym || !IS_SYMOP(sym))
417 for (sl = cseSet ; sl ; sl = sl->next ) {
419 if (loop->sym->key == sym->key )
426 /*-----------------------------------------------------------------*/
427 /* ifDefSymIsX - will return 1 if the symbols match */
428 /*-----------------------------------------------------------------*/
429 DEFSETFUNC(ifDefSymIsX)
435 return cdp->sym->key == op->key ;
437 return ( isOperandEqual(cdp->sym,op) );
442 /*-----------------------------------------------------------------*/
443 /* ifDiCodeIs - returns truw if diCode is same */
444 /*-----------------------------------------------------------------*/
445 int ifDiCodeIs (set *cseSet, iCode *ic)
453 for (sl = cseSet ; sl ; sl = sl->next ) {
455 if (loop->diCode == ic)
462 /*-----------------------------------------------------------------*/
463 /* ifPointerGet - returns true if the icode is pointer get sym */
464 /*-----------------------------------------------------------------*/
465 DEFSETFUNC(ifPointerGet)
469 iCode *dic = cdp->diCode;
470 operand *left = IC_LEFT(cdp->diCode);
472 if (POINTER_GET(dic) && left->key == op->key)
478 /*-----------------------------------------------------------------*/
479 /* ifPointerSet - returns true if the icode is pointer set sym */
480 /*-----------------------------------------------------------------*/
481 DEFSETFUNC(ifPointerSet)
486 if (POINTER_SET(cdp->diCode) &&
487 IC_RESULT(cdp->diCode)->key == op->key)
493 /*-----------------------------------------------------------------*/
494 /* ifDiCodeIsX - will return 1 if the symbols match */
495 /*-----------------------------------------------------------------*/
496 DEFSETFUNC(ifDiCodeIsX)
501 return cdp->diCode == ic;
505 /*-----------------------------------------------------------------*/
506 /* algebraicOpts - does some algebraic optimizations */
507 /*-----------------------------------------------------------------*/
508 void algebraicOpts (iCode *ic)
510 /* we don't deal with the following iCodes
521 /* if both operands present & ! IFX */
522 /* then if they are both literal we */
523 /* perform the operation right now */
527 IS_OP_LITERAL(IC_LEFT(ic)) &&
528 IS_OP_LITERAL(IC_RIGHT(ic))) {
530 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
533 operandType(IC_RESULT(ic)));
536 SET_RESULT_RIGHT(ic);
540 /* if not ifx & only one operand present */
543 IS_OP_LITERAL(IC_LEFT(ic)) &&
546 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
549 operandType(IC_RESULT(ic)));
552 SET_RESULT_RIGHT(ic);
557 /* a special case : or in short a kludgy solution will think
558 about a better solution over a glass of wine someday */
559 if ( ic->op == GET_VALUE_AT_ADDRESS ) {
561 if (IS_ITEMP(IC_RESULT(ic)) &&
562 IS_TRUE_SYMOP(IC_LEFT(ic))) {
565 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
566 IC_RIGHT(ic)->isaddr = 0;
568 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
569 IC_RESULT(ic)->isaddr = 0;
570 setOperandType(IC_RESULT(ic),operandType(IC_RIGHT(ic)));
574 if (IS_ITEMP(IC_LEFT(ic)) &&
575 IS_ITEMP(IC_RESULT(ic)) &&
576 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
577 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
578 !IC_LEFT(ic)->isaddr ) {
580 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
581 IC_RIGHT(ic)->isaddr = 0;
582 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
583 IC_RESULT(ic)->isaddr = 0;
591 /* depending on the operation */
594 /* if adding the same thing change to left shift by 1*/
595 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key &&
596 !IS_FLOAT(operandType(IC_RESULT(ic)))) {
598 IC_RIGHT(ic) = operandFromLit(1);
601 /* if addition then check if one of them is a zero */
602 /* if yes turn it into assignmnt*/
603 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
604 operandLitValue(IC_LEFT(ic)) == 0.0 ) {
608 SET_ISADDR(IC_RESULT(ic),0);
609 SET_ISADDR(IC_RIGHT(ic),0);
612 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
613 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
616 IC_RIGHT(ic) = IC_LEFT(ic) ;
618 SET_ISADDR(IC_RIGHT(ic),0);
619 SET_ISADDR(IC_RESULT(ic),0);
624 /* if subtracting the the same thing then zero */
625 if ( IC_LEFT(ic)->key == IC_RIGHT(ic)->key ) {
627 IC_RIGHT(ic) = operandFromLit(0);
629 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
630 IC_RESULT(ic)->isaddr = 0;
634 /* if subtraction then check if one of the operand */
635 /* is zero then depending on which operand change */
636 /* to assignment or unary minus */
637 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
638 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
639 /* right size zero change to assignment */
641 IC_RIGHT(ic) = IC_LEFT(ic);
643 SET_ISADDR(IC_RIGHT(ic),0);
644 SET_ISADDR(IC_RESULT(ic),0);
647 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
648 operandLitValue (IC_LEFT(ic)) == 0.0) {
649 /* left zero turn into an unary minus */
650 ic->op = UNARYMINUS ;
651 IC_LEFT(ic) = IC_RIGHT(ic);
652 IC_RIGHT(ic) = NULL ;
656 /* if multiplication then check if either of */
657 /* them is zero then the result is zero */
658 /* if either of them is one then result is */
661 if (IS_OP_LITERAL(IC_LEFT(ic))) {
663 if (operandLitValue(IC_LEFT(ic)) == 0.0) {
665 IC_RIGHT(ic) = IC_LEFT(ic);
667 SET_RESULT_RIGHT(ic);
670 if ( operandLitValue(IC_LEFT(ic)) == 1.0) {
673 SET_RESULT_RIGHT(ic);
678 if (IS_OP_LITERAL(IC_RIGHT(ic))) {
680 if (operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
683 SET_RESULT_RIGHT(ic);
687 if (operandLitValue(IC_RIGHT(ic)) == 1.0) {
689 IC_RIGHT(ic) = IC_LEFT(ic);
691 SET_RESULT_RIGHT(ic);
697 /* if division by self then 1 */
698 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key) {
700 IC_RIGHT(ic) = operandFromLit(1);
702 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
703 IC_RESULT(ic)->isaddr = 0;
705 /* if this is a division then check if right */
706 /* is one then change it to an assignment */
707 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
708 operandLitValue(IC_RIGHT(ic)) == 1.0 ) {
711 IC_RIGHT(ic) = IC_LEFT(ic);
713 SET_RESULT_RIGHT(ic);
717 /* if both are the same for an comparison operators */
721 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
723 IC_RIGHT(ic) = operandFromLit(1);
725 SET_RESULT_RIGHT(ic);
731 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
733 IC_RIGHT(ic) = operandFromLit(0);
735 SET_RESULT_RIGHT(ic);
739 /* if this is a cast of a literal value */
740 if ( IS_OP_LITERAL(IC_RIGHT(ic))) {
743 operandFromValue (valCastLiteral(operandType(IC_LEFT(ic)),
744 operandLitValue(IC_RIGHT(ic))));
746 SET_ISADDR(IC_RESULT(ic),0);
748 /* if casting to the same */
749 if ( checkType(operandType(IC_RESULT(ic)),
750 operandType(IC_RIGHT(ic))) == 1) {
753 SET_ISADDR(IC_RESULT(ic),0);
757 if (IS_OP_LITERAL(IC_LEFT(ic))) {
760 (operandLitValue(IC_LEFT(ic)) == 0 ?
761 operandFromLit(1) : operandFromLit(0));
763 SET_ISADDR(IC_RESULT(ic),0);
769 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
770 /*-----------------------------------------------------------------*/
771 /* updateSpillLocation - keeps track of register spill location */
772 /*-----------------------------------------------------------------*/
773 void updateSpillLocation ( iCode *ic)
784 /* for the form true_symbol := iTempNN */
785 if (ASSIGN_ITEMP_TO_SYM(ic)
786 && !SPIL_LOC(IC_RIGHT(ic))) {
788 setype = getSpec(operandType(IC_RESULT(ic)));
790 if (!IC_RIGHT(ic)->noSpilLoc &&
791 !IS_VOLATILE(setype) &&
792 !IN_FARSPACE(SPEC_OCLS(setype)) &&
793 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
795 SPIL_LOC(IC_RIGHT(ic)) =
796 IC_RESULT(ic)->operand.symOperand;
799 if (ASSIGN_ITEMP_TO_ITEMP(ic) &&
800 !SPIL_LOC(IC_RIGHT(ic)) &&
801 !bitVectBitsInCommon(OP_DEFS(IC_RIGHT(ic)),OP_USES(IC_RESULT(ic))) &&
802 OP_SYMBOL(IC_RESULT(ic))->isreqv) {
804 setype = getSpec(operandType(IC_RESULT(ic)));
806 if (!IC_RIGHT(ic)->noSpilLoc &&
807 !IS_VOLATILE(setype) &&
808 !IN_FARSPACE(SPEC_OCLS(setype)) &&
809 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
811 SPIL_LOC(IC_RIGHT(ic)) =
812 SPIL_LOC(IC_RESULT(ic));
816 /*-----------------------------------------------------------------*/
817 /* setUsesDef - sets the uses def bitvector for a given operand */
818 /*-----------------------------------------------------------------*/
819 void setUsesDefs (operand *op, bitVect *bdefs,
820 bitVect *idefs, bitVect **oud)
822 /* compute the definitions alive at this point */
823 bitVect *adefs = bitVectUnion(bdefs,idefs);
825 /* of these definitions find the ones that are */
826 /* for this operand */
827 adefs = bitVectIntersect(adefs,OP_DEFS(op));
829 /* these are the definitions that this operand can use */
830 op->usesDefs = adefs;
832 /* the out defs is an union */
833 *oud = bitVectUnion(*oud,adefs);
836 /*-----------------------------------------------------------------*/
837 /* unsetDefsAndUses - clear this operation for the operands */
838 /*-----------------------------------------------------------------*/
839 void unsetDefsAndUses ( iCode *ic )
841 if ( ic->op == JUMPTABLE)
844 /* take away this definition from the def chain of the */
845 /* result & take away from use set of the operands */
847 /* turn off def set */
848 if (IS_SYMOP(IC_RESULT(ic))) {
849 if ( !POINTER_SET(ic))
850 bitVectUnSetBit(OP_DEFS(IC_RESULT(ic)),ic->key);
852 bitVectUnSetBit(OP_USES(IC_RESULT(ic)),ic->key);
854 /* turn off the useSet for the operands */
855 if (IS_SYMOP(IC_LEFT(ic)))
856 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
858 if (IS_SYMOP(IC_RIGHT(ic)))
859 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
861 else /* must be ifx turn off the use */
862 if (IS_SYMOP(IC_COND(ic)))
863 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
866 /*-----------------------------------------------------------------*/
867 /* ifxOptimize - changes ifx conditions if it can */
868 /*-----------------------------------------------------------------*/
869 void ifxOptimize (iCode *ic, set *cseSet,
871 eBBlock *ebb, int *change,
872 eBBlock **ebbs, int count)
877 /* if the condition can be replaced */
880 applyToSetFTrue (cseSet,findCheaperOp,IC_COND(ic),&pdop);
887 /* if the conditional is a literal then */
888 if (IS_OP_LITERAL(IC_COND(ic))) {
890 if ( (operandLitValue(IC_COND(ic)) != 0.0) && IC_TRUE(ic)) {
892 /* change to a goto */
894 IC_LABEL(ic) = IC_TRUE(ic);
899 if (!operandLitValue(IC_COND(ic)) && IC_FALSE(ic)) {
901 IC_LABEL(ic) = IC_FALSE(ic);
905 /* then kill this if condition */
906 remiCodeFromeBBlock (ebb,ic);
910 /* now we need to recompute the control flow */
911 /* since the control flow has changed */
912 /* this is very expensive but it does not happen */
913 /* too often, if it does happen then the user pays */
915 computeControlFlow (ebbs,count,1);
916 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
920 /* if there is only one successor and that successor
921 is the same one we are conditionally going to then
922 we can remove this conditional statement */
923 label = (IC_TRUE(ic) ? IC_TRUE(ic) : IC_FALSE(ic));
924 if (elementsInSet(ebb->succList) == 1 &&
925 isinSet(ebb->succList,eBBWithEntryLabel(ebbs,label,count))) {
927 remiCodeFromeBBlock(ebb,ic);
928 computeControlFlow (ebbs,count,1);
929 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
934 /* if it remains an IFX the update the use Set */
935 OP_USES(IC_COND(ic)) = bitVectSetBit(OP_USES(IC_COND(ic)),ic->key);
936 setUsesDefs(IC_COND(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
940 /*-----------------------------------------------------------------*/
941 /* diCodeForSym - finds the definiting instruction for a symbol */
942 /*-----------------------------------------------------------------*/
943 DEFSETFUNC(diCodeForSym)
946 V_ARG(operand *,sym);
949 /* if already found */
953 /* if not if this is the defining iCode */
954 if (sym->key == cdp->key) {
962 /*-----------------------------------------------------------------*/
963 /* constFold - does some constant folding */
964 /*-----------------------------------------------------------------*/
965 int constFold (iCode *ic, set *cseSet)
968 /* this routine will change
974 /* deal with only + & - */
979 /* this check is a hueristic to prevent live ranges
980 from becoming too long */
981 if (IS_PTR(operandType(IC_RESULT(ic))))
984 /* check if operation with a literal */
985 if (!IS_OP_LITERAL(IC_RIGHT(ic)))
988 /* check if we can find a definition for the
990 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(ic),&dic)))
993 /* check that this is also a +/- */
994 if (dic->op != '+' && dic->op != '-')
998 if (!IS_OP_LITERAL(IC_RIGHT(dic)))
1001 /* it is if the operations are the same*/
1002 /* the literal parts need to be added */
1003 IC_LEFT(ic) = operandFromOperand(IC_LEFT(dic));
1004 if (ic->op == dic->op )
1005 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic))+
1006 operandLitValue(IC_RIGHT(dic)));
1008 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) -
1009 operandLitValue(IC_RIGHT(dic)));
1011 if (IS_ITEMP(IC_RESULT(ic))) {
1012 SPIL_LOC(IC_RESULT(ic)) = NULL;
1013 IC_RESULT(ic)->noSpilLoc = 1;
1020 /*-----------------------------------------------------------------*/
1021 /* deleteGetPointers - called when a pointer is passed as parm */
1022 /* will delete from cseSet all get pointers computed from this */
1023 /* pointer. A simple ifOperandsHave is not good enough here */
1024 /*-----------------------------------------------------------------*/
1025 static void deleteGetPointers (set **cseSet, set **pss, operand *op,eBBlock *ebb)
1027 set *compItems = NULL;
1032 if (!*cseSet && !*pss)
1035 /* first find all items computed from this operand .
1036 This done fairly simply go thru the list and find
1037 those that are computed by arthimetic with this
1039 for (cdp = setFirstItem(*cseSet); cdp ; cdp = setNextItem(*cseSet)) {
1040 if (IS_ARITHMETIC_OP(cdp->diCode)) {
1041 if (isOperandEqual(IC_LEFT(cdp->diCode),op) ||
1042 isOperandEqual(IC_RIGHT(cdp->diCode),op)) {
1043 /* save it in our list of items */
1044 addSet(&compItems,IC_RESULT(cdp->diCode));
1046 /* also check for those computed from our computed
1047 list . This will take care of situations like
1048 iTemp1 = iTemp0 + 8;
1049 iTemp2 = iTemp1 + 8; */
1050 if (isinSetWith(compItems,IC_LEFT(cdp->diCode),isOperandEqual) ||
1051 isinSetWith(compItems,IC_RIGHT(cdp->diCode),isOperandEqual)) {
1052 addSet(&compItems,IC_RESULT(cdp->diCode));
1057 /* now delete all pointer gets with this op */
1058 deleteItemIf(cseSet,ifPointerGet,op);
1059 deleteItemIf(pss,ifPointerSet,op);
1061 /* set the bit vector used by dataFlow computation later */
1062 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,op->key);
1063 /* now for the computed items */
1064 for (cop = setFirstItem(compItems); cop ; cop = setNextItem(compItems)) {
1065 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,cop->key);
1066 deleteItemIf(cseSet,ifPointerGet,cop);
1067 deleteItemIf(pss,ifPointerSet,cop);
1071 /*-----------------------------------------------------------------*/
1072 /* delGetPointerSucc - delete get pointer from inExprs of succ with*/
1073 /* dfnum > supplied */
1074 /*-----------------------------------------------------------------*/
1075 DEFSETFUNC(delGetPointerSucc)
1077 eBBlock *ebp = item;
1078 V_ARG(operand *,op);
1085 if (ebp->dfnum > dfnum) {
1086 deleteItemIf(&ebp->inExprs,ifPointerGet,op);
1089 return applyToSet(ebp->succList,delGetPointerSucc,op,dfnum);
1092 /*-----------------------------------------------------------------*/
1093 /* cseBBlock - common subexpression elimination for basic blocks */
1094 /* this is the hackiest kludgiest routine in the whole */
1095 /* system. also the most important, since almost all */
1096 /* data flow related information is computed by it */
1097 /*-----------------------------------------------------------------*/
1098 int cseBBlock ( eBBlock *ebb, int computeOnly,
1099 eBBlock **ebbs, int count)
1105 set *ptrSetSet = NULL;
1107 /* if this block is not reachable */
1111 /* set of common subexpressions */
1112 cseSet = setFromSet (ebb->inExprs) ;
1114 /* these will be computed by this routine */
1115 setToNull ((void **)&ebb->outDefs);
1116 setToNull ((void **)&ebb->defSet);
1117 setToNull ((void **)&ebb->usesDefs);
1118 setToNull ((void **)&ebb->ptrsSet);
1119 setToNull ((void **)&ebb->addrOf);
1120 setToNull ((void **)&ebb->ldefs);
1122 ebb->outDefs = bitVectCopy (ebb->inDefs);
1123 bitVectDefault = iCodeKey;
1124 ebb->defSet = newBitVect(iCodeKey);
1125 ebb->usesDefs=newBitVect(iCodeKey);
1127 /* for all the instructions in this block do */
1128 for (ic = ebb->sch ; ic ; ic = ic->next ) {
1137 /* if this is an assignment from true symbol
1138 to a temp then do pointer post inc/dec optimzation */
1139 if (ic->op == '=' && !POINTER_SET(ic) &&
1140 IS_TRUE_SYMOP(IC_RIGHT(ic)) && IS_ITEMP(IC_RESULT(ic)) &&
1141 IS_PTR(operandType(IC_RESULT(ic)))) {
1142 ptrPostIncDecOpt(ic);
1145 /* clear the def & use chains for the operands involved */
1146 /* in this operation . since it can change due to opts */
1147 unsetDefsAndUses (ic);
1149 if ( ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE) {
1150 /* add to defSet of the symbol */
1151 OP_DEFS(IC_RESULT(ic)) =
1152 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1153 /* add to the definition set of this block */
1154 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1155 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1156 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1157 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1158 /* delete global variables from the cseSet
1159 since they can be modified by the function call */
1160 deleteItemIf(&cseSet,ifDefGlobal);
1163 /* for pcall & ipush we need to add to the useSet */
1164 if ((ic->op == PCALL ||
1168 IS_SYMOP(IC_LEFT(ic))) {
1170 /* check if they can be replaced */
1171 if ( !computeOnly ) {
1173 applyToSetFTrue(cseSet,findCheaperOp,IC_LEFT(ic),&pdop);
1175 IC_LEFT(ic) = pdop ;
1177 /* the lookup could have changed it*/
1178 if (IS_SYMOP(IC_LEFT(ic))) {
1179 OP_USES(IC_LEFT(ic)) =
1180 bitVectSetBit(OP_USES(IC_LEFT(ic)),ic->key);
1181 setUsesDefs(IC_LEFT(ic),ebb->defSet,
1182 ebb->outDefs,&ebb->usesDefs);
1186 /* if we a sending a pointer as a parameter
1187 then kill all cse since the pointed to item
1188 might be changed in the function being called */
1189 if ((ic->op == IPUSH || ic->op == SEND) &&
1190 IS_PTR(operandType(IC_LEFT(ic)))) {
1191 deleteGetPointers(&cseSet,&ptrSetSet,IC_LEFT(ic),ebb);
1192 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_LEFT(ic)->key);
1193 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1194 applyToSet(ebb->succList,delGetPointerSucc,
1195 IC_LEFT(ic),ebb->dfnum);
1200 /* if jumptable then mark the usage */
1201 if (ic->op == JUMPTABLE ) {
1202 OP_USES(IC_JTCOND(ic)) =
1203 bitVectSetBit(OP_USES(IC_JTCOND(ic)),ic->key);
1204 setUsesDefs(IC_JTCOND(ic),ebb->defSet,
1205 ebb->outDefs,&ebb->usesDefs);
1212 /* do some algebraic optimizations if possible */
1214 while (constFold(ic,cseSet));
1217 if (POINTER_GET(ic) && !IS_PTR(operandType(IC_LEFT(ic)))) {
1218 setOperandType(IC_LEFT(ic),
1219 aggrToPtr(operandType(IC_LEFT(ic)),FALSE));
1221 if (POINTER_SET(ic) && !IS_PTR(operandType(IC_RESULT(ic)))) {
1222 setOperandType(IC_RESULT(ic),
1223 aggrToPtr(operandType(IC_RESULT(ic)),FALSE));
1226 /* if this is a condition statment then */
1227 /* check if the condition can be replaced */
1228 if (ic->op == IFX ) {
1229 ifxOptimize (ic, cseSet, computeOnly,
1235 /* if the assignment & result is a temp */
1236 /* see if we can replace it */
1237 if (ic->op == '=') {
1239 /* update the spill location for this */
1240 updateSpillLocation (ic);
1242 if (POINTER_SET(ic)) {
1244 applyToSetFTrue (cseSet,findCheaperOp,IC_RESULT(ic),&pdop);
1245 if (pdop && IS_ITEMP(pdop) && !computeOnly)
1246 IC_RESULT(ic) = pdop;
1250 /* do the operand lookup i.e. for both the */
1251 /* right & left operand : check the cseSet */
1252 /* to see if they have been replaced if yes*/
1253 /* then replace them with those from cseSet*/
1255 /* and left is a symbol */
1256 if (IS_SYMOP(IC_LEFT(ic)) &&
1257 !computeOnly && ic->op != ADDRESS_OF ) {
1260 applyToSetFTrue (cseSet,findCheaperOp,IC_LEFT(ic),&pdop) ;
1262 if (POINTER_GET(ic)) {
1263 if (IS_ITEMP(pdop) || IS_OP_LITERAL(pdop)) {
1267 /* check if there is a pointer set
1268 for the same pointer visible if yes
1269 then change this into an assignment */
1271 if (applyToSetFTrue(cseSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic)) &&
1272 !bitVectBitValue(ebb->ptrsSet,pdop->key)){
1275 IC_RIGHT(ic) = pdop;
1276 SET_ISADDR(IC_RESULT(ic),0);
1281 IC_LEFT(ic) = pdop ;
1288 if (IS_SYMOP(IC_RIGHT(ic)) && !computeOnly) {
1291 applyToSetFTrue (cseSet,findCheaperOp,IC_RIGHT(ic),&pdop);
1294 IC_RIGHT(ic) = pdop;
1299 /* if left or right changed then do algebraic */
1302 while(constFold(ic,cseSet));
1305 /* if after all this it becomes a assignment to self
1306 then delete it and continue */
1307 if (ASSIGNMENT_TO_SELF(ic)) {
1308 remiCodeFromeBBlock(ebb,ic);
1312 /* now we will check to see if the entire */
1313 /* operation has been performed before */
1314 /* and is available */
1315 /* don't do assignments they will be killed */
1316 /* by dead code elimination if required do */
1317 /* it only if result is a temporary */
1319 if (!( POINTER_GET(ic) &&
1320 (IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1321 isOperandVolatile(IC_LEFT(ic),TRUE))) &&
1323 IS_ITEMP(IC_RESULT(ic)) &&
1325 applyToSet (cseSet,findPrevIc,ic,&pdic);
1328 /* if found then eliminate this and add to*/
1329 /* to cseSet an element containing result */
1330 /* of this with previous opcode */
1333 if (IS_ITEMP(IC_RESULT(ic))) {
1335 /* replace in the remaining of this block */
1336 replaceAllSymBySym(ic->next,IC_RESULT(ic),IC_RESULT(pdic));
1337 /* remove this iCode from inexpressions of all
1338 its successors, it cannot be in the in expressions
1339 of any of the predecessors */
1340 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1341 applyToSet(ebb->succList,removeFromInExprs,ic,IC_RESULT(ic),
1342 IC_RESULT(pdic),ebb);
1344 /* if this was moved from another block */
1345 /* then replace in those blocks too */
1346 if ( ic->movedFrom ) {
1348 for (owner = setFirstItem(ic->movedFrom); owner ;
1349 owner = setNextItem(ic->movedFrom))
1350 replaceAllSymBySym(owner->sch,IC_RESULT(ic),IC_RESULT(pdic));
1352 pdic->movedFrom = unionSets(pdic->movedFrom,ic->movedFrom,THROW_NONE);
1355 addSetHead (&cseSet,newCseDef(IC_RESULT(ic),pdic));
1358 /* eliminate this */
1359 remiCodeFromeBBlock (ebb,ic);
1364 if (IS_ITEMP(IC_RESULT(ic)))
1369 /* just add this as a previous expression except in */
1370 /* case of a pointer access in which case this is a */
1371 /* usage not a definition */
1372 if (! (POINTER_SET(ic)) && IC_RESULT(ic)){
1373 deleteItemIf (&cseSet, ifDefSymIsX,IC_RESULT(ic));
1374 addSetHead(&cseSet,newCseDef(IC_RESULT(ic),ic));
1380 /* if assignment to a parameter which is not
1381 mine and type is a pointer then delete
1382 pointerGets to take care of aliasing */
1383 if (ASSIGNMENT(ic) &&
1384 OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) &&
1385 IS_PTR(operandType(IC_RESULT(ic)))) {
1386 deleteGetPointers(&cseSet,&ptrSetSet,IC_RIGHT(ic),ebb);
1387 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1388 applyToSet(ebb->succList,delGetPointerSucc,IC_RIGHT(ic),ebb->dfnum);
1389 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RIGHT(ic)->key);
1392 /* if this is a pointerget then see if we can replace
1393 this with a previously assigned pointer value */
1394 if (POINTER_GET(ic) &&
1395 !(IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1396 isOperandVolatile(IC_LEFT(ic),TRUE))) {
1398 applyToSet(ptrSetSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic));
1399 /* if we find it then locally replace all
1400 references to the result with what we assigned */
1402 replaceAllSymBySym(ic->next,IC_RESULT(ic),pdop);
1406 /* delete from the cseSet anything that has */
1407 /* operands matching the result of this */
1408 /* except in case of pointer access */
1409 if (!(POINTER_SET(ic)) && IC_RESULT(ic)) {
1410 deleteItemIf (&cseSet,ifOperandsHave,IC_RESULT(ic));
1411 /* delete any previous definitions */
1412 ebb->defSet = bitVectCplAnd (ebb->defSet,OP_DEFS(IC_RESULT(ic)));
1416 /* add the left & right to the defUse set */
1417 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic))) {
1418 OP_USES(IC_LEFT(ic)) =
1419 bitVectSetBit (OP_USES(IC_LEFT(ic)),ic->key);
1420 setUsesDefs(IC_LEFT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1424 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic))) {
1425 OP_USES(IC_RIGHT(ic)) =
1426 bitVectSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
1427 setUsesDefs(IC_RIGHT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1431 /* for the result it is special case, put the result */
1432 /* in the defuseSet if it a pointer or array access */
1433 if ( POINTER_SET(defic) ) {
1434 OP_USES(IC_RESULT(ic)) =
1435 bitVectSetBit (OP_USES(IC_RESULT(ic)),ic->key);
1436 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1437 deleteItemIf(&cseSet,ifPointerGet,IC_RESULT(ic));
1438 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RESULT(ic)->key);
1439 /* delete from inexpressions of all successors which
1440 have dfNum > than this block */
1441 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1442 applyToSet(ebb->succList,delGetPointerSucc,IC_RESULT(ic),ebb->dfnum);
1444 /* delete from cseSet all other pointer sets
1446 deleteItemIf(&ptrSetSet,ifPointerSet,IC_RESULT(ic));
1447 /* add to the local pointerset set */
1448 addSetHead(&ptrSetSet,newCseDef(IC_RESULT(ic),ic));
1450 else /* add the result to defintion set */
1451 if (IC_RESULT(ic)) {
1452 OP_DEFS(IC_RESULT(ic)) =
1453 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1454 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1455 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1456 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1460 /* if this is an addressof instruction then */
1461 /* put the symbol in the address of list & */
1462 /* delete it from the cseSet */
1463 if (defic->op == ADDRESS_OF) {
1464 addSetHead (&ebb->addrOf, IC_LEFT(ic));
1465 deleteItemIf(&cseSet,ifDefSymIsX,IC_LEFT(ic));
1469 setToNull ((void **)&ebb->outExprs);
1470 ebb->outExprs = cseSet;
1471 ebb->outDefs = bitVectUnion (ebb->outDefs,ebb->defSet);
1472 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet,ebb->inPtrsSet);
1476 /*-----------------------------------------------------------------*/
1477 /* cseAllBlocks - will sequentially go thru & do cse for all blocks*/
1478 /*-----------------------------------------------------------------*/
1479 int cseAllBlocks (eBBlock **ebbs,int count)
1484 /* if optimization turned off */
1486 for (i = 0 ; i < count ;i++ )
1487 change += cseBBlock (ebbs[i],FALSE,ebbs,count);