1 /*-------------------------------------------------------------------------
2 SDCCcse.c - source file for Common Subexpressions and other utility
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 In other words, you are welcome to use, share and improve this program.
21 You are forbidden to forbid anyone else to use, share and improve
22 what you give them. Help stamp out software-hoarding!
23 -------------------------------------------------------------------------*/
27 /*-----------------------------------------------------------------*/
28 /* newCseDef - new cseDef */
29 /*-----------------------------------------------------------------*/
30 cseDef *newCseDef (operand *sym, iCode *ic)
35 ALLOC(cdp,sizeof(cseDef));
46 /*-----------------------------------------------------------------*/
47 /* int isCseDefEqual - two definitions are equal */
48 /*-----------------------------------------------------------------*/
49 int isCseDefEqual ( void *vsrc, void *vdest)
57 return (src->key == dest->key &&
58 src->diCode == dest->diCode ) ;
62 /*-----------------------------------------------------------------*/
63 /* pcseDef - in the cseDef */
64 /*-----------------------------------------------------------------*/
65 int pcseDef (void *item, va_list ap)
73 fprintf(stdout,"**null op**");
74 printOperand(cdp->sym,stdout);
75 icTab = getTableEntry(cdp->diCode->op) ;
76 icTab->iCodePrint(stdout,cdp->diCode,icTab->printName);
80 /*-----------------------------------------------------------------*/
81 /* replaceAllSymBySym - replaces all operands by operand in an */
82 /* instruction chain */
83 /*-----------------------------------------------------------------*/
84 void replaceAllSymBySym (iCode *ic, operand *from , operand *to, bitVect **ndpset)
88 for (lic = ic ; lic ; lic = lic->next ) {
91 /* do the special cases first */
94 IC_COND(lic)->key == from->key) {
96 bitVectUnSetBit (OP_USES(from),lic->key);
97 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
98 siaddr = IC_COND(lic)->isaddr ;
99 IC_COND(lic) = operandFromOperand(to);
100 IC_COND(lic)->isaddr = siaddr ;
106 if (lic->op == JUMPTABLE) {
108 IC_JTCOND(lic)->key == from->key) {
110 bitVectUnSetBit (OP_USES(from),lic->key);
111 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
112 siaddr = IC_COND(lic)->isaddr ;
113 IC_JTCOND(lic) = operandFromOperand(to);
114 IC_JTCOND(lic)->isaddr = siaddr ;
120 if (IC_RESULT(lic) && IC_RESULT(lic)->key == from->key ) {
121 /* maintain du chains */
122 if (POINTER_SET(lic)) {
123 bitVectUnSetBit (OP_USES(from),lic->key);
124 OP_USES(to) = bitVectSetBit (OP_USES(to),lic->key);
126 /* also check if the "from" was in the non-dominating
127 pointer sets and replace it with "to" in the bitVector */
128 if (bitVectBitValue(*ndpset,from->key)) {
129 bitVectUnSetBit(*ndpset,from->key);
130 bitVectSetBit(*ndpset,to->key);
135 bitVectUnSetBit (OP_DEFS(from),lic->key);
136 OP_DEFS(to) = bitVectSetBit (OP_DEFS(to),lic->key);
138 siaddr = IC_RESULT(lic)->isaddr ;
139 IC_RESULT(lic) = operandFromOperand(to);
140 IC_RESULT(lic)->isaddr = siaddr ;
144 IC_RIGHT(lic) && IC_RIGHT(lic)->key == from->key ) {
145 bitVectUnSetBit (OP_USES(from),lic->key);
146 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
147 siaddr = IC_RIGHT(lic)->isaddr ;
148 IC_RIGHT(lic) = operandFromOperand(to);
149 IC_RIGHT(lic)->isaddr = siaddr ;
153 IC_LEFT(lic) && IC_LEFT(lic)->key == from->key ) {
154 bitVectUnSetBit (OP_USES(from),lic->key);
155 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
156 siaddr = IC_LEFT(lic)->isaddr ;
157 IC_LEFT(lic) = operandFromOperand(to);
158 IC_LEFT(lic)->isaddr = siaddr ;
163 /*-----------------------------------------------------------------*/
164 /* iCodeKeyIs - if the icode keys match then return 1 */
165 /*-----------------------------------------------------------------*/
166 DEFSETFUNC(iCodeKeyIs)
171 if (cdp->diCode->key == key)
177 /*-----------------------------------------------------------------*/
178 /* removeFromInExprs - removes an icode from inexpressions */
179 /*-----------------------------------------------------------------*/
180 DEFSETFUNC(removeFromInExprs)
184 V_ARG(operand *,from);
186 V_ARG(eBBlock *,cbp);
192 deleteItemIf(&ebp->inExprs,iCodeKeyIs,ic->key);
193 if (ebp != cbp && !bitVectBitValue(cbp->domVect,ebp->bbnum))
194 replaceAllSymBySym(ebp->sch,from,to,&ebp->ndompset);
196 applyToSet(ebp->succList,removeFromInExprs,ic,from,to,cbp);
200 /*-----------------------------------------------------------------*/
201 /* isGlobalInNearSpace - return TRUE if valriable is a globalin data */
202 /*-----------------------------------------------------------------*/
203 static bool isGlobalInNearSpace (operand *op)
205 link *type = getSpec(operandType(op));
206 /* this is 8051 specific: optimization
207 suggested by Jean-Louis VERN, with 8051s we have no
208 advantage of putting variables in near space into
210 if (isOperandGlobal(op) &&
211 IN_DIRSPACE(SPEC_OCLS(type)))
217 /*-----------------------------------------------------------------*/
218 /* findCheaperOp - cseBBlock support routine, will check to see if */
219 /* we have a operand previously defined */
220 /*-----------------------------------------------------------------*/
221 DEFSETFUNC(findCheaperOp)
224 V_ARG(operand *,cop);
225 V_ARG(operand **,opp);
227 /* if we have already found it */
231 /* not found it yet check if this is the one */
232 /* and this is not the defining one */
233 if (cop->key == cdp->key) {
235 /* do a special check this will help in */
236 /* constant propagation & dead code elim*/
237 /* for assignments only */
238 if (cdp->diCode->op == '=') {
239 /* if the result is volatile then return result */
240 if (IS_OP_VOLATILE (IC_RESULT(cdp->diCode)))
241 *opp = IC_RESULT(cdp->diCode);
243 /* if this is a straight assignment and
244 left is a temp then prefer the temporary to the
246 if (!POINTER_SET(cdp->diCode) &&
247 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
248 IS_TRUE_SYMOP(IC_RIGHT(cdp->diCode)))
249 *opp = IC_RESULT(cdp->diCode);
251 /* if straight assignement && and both
252 are temps then prefer the one that
253 will not need extra space to spil, also
254 take into consideration if right side
255 an induction variable
257 if (!POINTER_SET(cdp->diCode) &&
258 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
259 IS_ITEMP(IC_RIGHT(cdp->diCode)) &&
260 !OP_SYMBOL(IC_RIGHT(cdp->diCode))->isind &&
261 ( (!SPIL_LOC(IC_RIGHT(cdp->diCode)) &&
262 SPIL_LOC(IC_RESULT(cdp->diCode))) ||
263 ( SPIL_LOC(IC_RESULT(cdp->diCode)) &&
264 SPIL_LOC(IC_RESULT(cdp->diCode)) ==
265 SPIL_LOC(IC_RIGHT(cdp->diCode))) )
267 *opp = IC_RESULT(cdp->diCode);
269 *opp = IC_RIGHT(cdp->diCode);
272 *opp = IC_RESULT(cdp->diCode) ;
275 /* if this is an assign to a temp. then check
276 if the right side is this then return this */
277 if (IS_TRUE_SYMOP(cop) &&
278 cdp->diCode->op == '=' &&
279 !POINTER_SET(cdp->diCode) &&
280 cop->key == IC_RIGHT(cdp->diCode)->key &&
281 !isGlobalInNearSpace (IC_RIGHT(cdp->diCode)) &&
282 IS_ITEMP(IC_RESULT(cdp->diCode)))
283 *opp = IC_RESULT(cdp->diCode);
287 if ((isGlobalInNearSpace(cop) &&
288 !isOperandLiteral(*opp)) ||
289 isOperandVolatile(*opp,FALSE)
295 if (cop->key == (*opp)->key ) {
300 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP(cop)) {
301 *opp = operandFromOperand(*opp);
302 (*opp)->isaddr = cop->isaddr;
312 /*-----------------------------------------------------------------*/
313 /* findPointerSet - finds the right side of a pointer set op */
314 /*-----------------------------------------------------------------*/
315 DEFSETFUNC(findPointerSet)
319 V_ARG(operand **,opp);
320 V_ARG(operand *,rop);
322 if (POINTER_SET(cdp->diCode) &&
323 IC_RESULT(cdp->diCode)->key == op->key &&
324 !isOperandVolatile(IC_RESULT(cdp->diCode),TRUE) &&
325 !isOperandVolatile(IC_RIGHT(cdp->diCode),TRUE) &&
326 getSize(operandType(IC_RIGHT(cdp->diCode))) ==
327 getSize(operandType(rop))) {
328 *opp = IC_RIGHT(cdp->diCode);
335 /*-----------------------------------------------------------------*/
336 /* findPrevIc - cseBBlock support function will return the iCode */
337 /* which matches the current one */
338 /*-----------------------------------------------------------------*/
339 DEFSETFUNC(findPrevIc)
345 /* if already found */
349 /* if the iCodes are the same */
350 if (isiCodeEqual(ic,cdp->diCode) &&
351 isOperandEqual(cdp->sym,IC_RESULT(cdp->diCode))) {
356 /* if iCodes are not the same */
357 /* see the operands maybe interchanged */
358 if (ic->op == cdp->diCode->op &&
359 ( ic->op == '+' || ic->op == '*' ) &&
360 isOperandEqual(IC_LEFT(ic),IC_RIGHT(cdp->diCode)) &&
361 isOperandEqual(IC_RIGHT(ic),IC_LEFT(cdp->diCode))) {
369 /*-----------------------------------------------------------------*/
370 /* ifDefGlobal - if definition is global */
371 /*-----------------------------------------------------------------*/
372 DEFSETFUNC(ifDefGlobal)
376 return (isOperandGlobal(cdp->sym));
379 /*-----------------------------------------------------------------*/
380 /* ifAnyGetPointer - if get pointer icode */
381 /*-----------------------------------------------------------------*/
382 DEFSETFUNC(ifAnyGetPointer)
386 if (cdp->diCode && POINTER_GET(cdp->diCode)) return 1;
390 /*-----------------------------------------------------------------*/
391 /* ifOperandsHave - if any of the operand are the same as this */
392 /*-----------------------------------------------------------------*/
393 DEFSETFUNC(ifOperandsHave)
399 if (IC_LEFT(cdp->diCode) &&
400 IS_SYMOP(IC_LEFT(cdp->diCode)) &&
401 IC_LEFT(cdp->diCode)->key == op->key)
404 if (IC_RIGHT(cdp->diCode) &&
405 IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
406 IC_RIGHT(cdp->diCode)->key == op->key)
409 /* or if any of the operands are volatile */
410 if (IC_LEFT(cdp->diCode) &&
411 IS_OP_VOLATILE(IC_LEFT(cdp->diCode)))
414 if (IC_RIGHT(cdp->diCode) &&
415 IS_OP_VOLATILE(IC_RIGHT(cdp->diCode)))
419 if (IC_RESULT(cdp->diCode) &&
420 IS_OP_VOLATILE(IC_RESULT(cdp->diCode)))
426 /*-----------------------------------------------------------------*/
427 /* ifDefSymIs - if a definition is found in the set */
428 /*-----------------------------------------------------------------*/
429 int ifDefSymIs (set *cseSet, operand *sym)
434 if (!sym || !IS_SYMOP(sym))
436 for (sl = cseSet ; sl ; sl = sl->next ) {
438 if (loop->sym->key == sym->key )
445 /*-----------------------------------------------------------------*/
446 /* ifDefSymIsX - will return 1 if the symbols match */
447 /*-----------------------------------------------------------------*/
448 DEFSETFUNC(ifDefSymIsX)
454 return cdp->sym->key == op->key ;
456 return ( isOperandEqual(cdp->sym,op) );
461 /*-----------------------------------------------------------------*/
462 /* ifDiCodeIs - returns truw if diCode is same */
463 /*-----------------------------------------------------------------*/
464 int ifDiCodeIs (set *cseSet, iCode *ic)
472 for (sl = cseSet ; sl ; sl = sl->next ) {
474 if (loop->diCode == ic)
481 /*-----------------------------------------------------------------*/
482 /* ifPointerGet - returns true if the icode is pointer get sym */
483 /*-----------------------------------------------------------------*/
484 DEFSETFUNC(ifPointerGet)
488 iCode *dic = cdp->diCode;
489 operand *left = IC_LEFT(cdp->diCode);
491 if (POINTER_GET(dic) && left->key == op->key)
497 /*-----------------------------------------------------------------*/
498 /* ifPointerSet - returns true if the icode is pointer set sym */
499 /*-----------------------------------------------------------------*/
500 DEFSETFUNC(ifPointerSet)
505 if (POINTER_SET(cdp->diCode) &&
506 IC_RESULT(cdp->diCode)->key == op->key)
512 /*-----------------------------------------------------------------*/
513 /* ifDiCodeIsX - will return 1 if the symbols match */
514 /*-----------------------------------------------------------------*/
515 DEFSETFUNC(ifDiCodeIsX)
520 return cdp->diCode == ic;
524 /*-----------------------------------------------------------------*/
525 /* algebraicOpts - does some algebraic optimizations */
526 /*-----------------------------------------------------------------*/
527 void algebraicOpts (iCode *ic)
529 /* we don't deal with the following iCodes
540 /* if both operands present & ! IFX */
541 /* then if they are both literal we */
542 /* perform the operation right now */
546 IS_OP_LITERAL(IC_LEFT(ic)) &&
547 IS_OP_LITERAL(IC_RIGHT(ic))) {
549 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
552 operandType(IC_RESULT(ic)));
555 SET_RESULT_RIGHT(ic);
559 /* if not ifx & only one operand present */
562 IS_OP_LITERAL(IC_LEFT(ic)) &&
565 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
568 operandType(IC_RESULT(ic)));
571 SET_RESULT_RIGHT(ic);
576 /* a special case : or in short a kludgy solution will think
577 about a better solution over a glass of wine someday */
578 if ( ic->op == GET_VALUE_AT_ADDRESS ) {
580 if (IS_ITEMP(IC_RESULT(ic)) &&
581 IS_TRUE_SYMOP(IC_LEFT(ic))) {
584 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
585 IC_RIGHT(ic)->isaddr = 0;
587 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
588 IC_RESULT(ic)->isaddr = 0;
589 setOperandType(IC_RESULT(ic),operandType(IC_RIGHT(ic)));
593 if (IS_ITEMP(IC_LEFT(ic)) &&
594 IS_ITEMP(IC_RESULT(ic)) &&
595 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
596 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
597 !IC_LEFT(ic)->isaddr ) {
599 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
600 IC_RIGHT(ic)->isaddr = 0;
601 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
602 IC_RESULT(ic)->isaddr = 0;
610 /* depending on the operation */
613 /* if adding the same thing change to left shift by 1*/
614 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key &&
615 !IS_FLOAT(operandType(IC_RESULT(ic)))) {
617 IC_RIGHT(ic) = operandFromLit(1);
620 /* if addition then check if one of them is a zero */
621 /* if yes turn it into assignmnt*/
622 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
623 operandLitValue(IC_LEFT(ic)) == 0.0 ) {
627 SET_ISADDR(IC_RESULT(ic),0);
628 SET_ISADDR(IC_RIGHT(ic),0);
631 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
632 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
635 IC_RIGHT(ic) = IC_LEFT(ic) ;
637 SET_ISADDR(IC_RIGHT(ic),0);
638 SET_ISADDR(IC_RESULT(ic),0);
643 /* if subtracting the the same thing then zero */
644 if ( IC_LEFT(ic)->key == IC_RIGHT(ic)->key ) {
646 IC_RIGHT(ic) = operandFromLit(0);
648 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
649 IC_RESULT(ic)->isaddr = 0;
653 /* if subtraction then check if one of the operand */
654 /* is zero then depending on which operand change */
655 /* to assignment or unary minus */
656 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
657 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
658 /* right size zero change to assignment */
660 IC_RIGHT(ic) = IC_LEFT(ic);
662 SET_ISADDR(IC_RIGHT(ic),0);
663 SET_ISADDR(IC_RESULT(ic),0);
666 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
667 operandLitValue (IC_LEFT(ic)) == 0.0) {
668 /* left zero turn into an unary minus */
669 ic->op = UNARYMINUS ;
670 IC_LEFT(ic) = IC_RIGHT(ic);
671 IC_RIGHT(ic) = NULL ;
675 /* if multiplication then check if either of */
676 /* them is zero then the result is zero */
677 /* if either of them is one then result is */
680 if (IS_OP_LITERAL(IC_LEFT(ic))) {
682 if (operandLitValue(IC_LEFT(ic)) == 0.0) {
684 IC_RIGHT(ic) = IC_LEFT(ic);
686 SET_RESULT_RIGHT(ic);
689 if ( operandLitValue(IC_LEFT(ic)) == 1.0) {
692 SET_RESULT_RIGHT(ic);
697 if (IS_OP_LITERAL(IC_RIGHT(ic))) {
699 if (operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
702 SET_RESULT_RIGHT(ic);
706 if (operandLitValue(IC_RIGHT(ic)) == 1.0) {
708 IC_RIGHT(ic) = IC_LEFT(ic);
710 SET_RESULT_RIGHT(ic);
716 /* if division by self then 1 */
717 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key) {
719 IC_RIGHT(ic) = operandFromLit(1);
721 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
722 IC_RESULT(ic)->isaddr = 0;
724 /* if this is a division then check if right */
725 /* is one then change it to an assignment */
726 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
727 operandLitValue(IC_RIGHT(ic)) == 1.0 ) {
730 IC_RIGHT(ic) = IC_LEFT(ic);
732 SET_RESULT_RIGHT(ic);
736 /* if both are the same for an comparison operators */
740 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
742 IC_RIGHT(ic) = operandFromLit(1);
744 SET_RESULT_RIGHT(ic);
750 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
752 IC_RIGHT(ic) = operandFromLit(0);
754 SET_RESULT_RIGHT(ic);
758 /* if this is a cast of a literal value */
759 if ( IS_OP_LITERAL(IC_RIGHT(ic))) {
762 operandFromValue (valCastLiteral(operandType(IC_LEFT(ic)),
763 operandLitValue(IC_RIGHT(ic))));
765 SET_ISADDR(IC_RESULT(ic),0);
767 /* if casting to the same */
768 if ( checkType(operandType(IC_RESULT(ic)),
769 operandType(IC_RIGHT(ic))) == 1) {
772 SET_ISADDR(IC_RESULT(ic),0);
776 if (IS_OP_LITERAL(IC_LEFT(ic))) {
779 (operandLitValue(IC_LEFT(ic)) == 0 ?
780 operandFromLit(1) : operandFromLit(0));
782 SET_ISADDR(IC_RESULT(ic),0);
788 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
789 /*-----------------------------------------------------------------*/
790 /* updateSpillLocation - keeps track of register spill location */
791 /*-----------------------------------------------------------------*/
792 void updateSpillLocation ( iCode *ic)
803 /* for the form true_symbol := iTempNN */
804 if (ASSIGN_ITEMP_TO_SYM(ic)
805 && !SPIL_LOC(IC_RIGHT(ic))) {
807 setype = getSpec(operandType(IC_RESULT(ic)));
809 if (!IC_RIGHT(ic)->noSpilLoc &&
810 !IS_VOLATILE(setype) &&
811 !IN_FARSPACE(SPEC_OCLS(setype)) &&
812 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
814 SPIL_LOC(IC_RIGHT(ic)) =
815 IC_RESULT(ic)->operand.symOperand;
818 if (ASSIGN_ITEMP_TO_ITEMP(ic) &&
819 !SPIL_LOC(IC_RIGHT(ic)) &&
820 !bitVectBitsInCommon(OP_DEFS(IC_RIGHT(ic)),OP_USES(IC_RESULT(ic))) &&
821 OP_SYMBOL(IC_RESULT(ic))->isreqv) {
823 setype = getSpec(operandType(IC_RESULT(ic)));
825 if (!IC_RIGHT(ic)->noSpilLoc &&
826 !IS_VOLATILE(setype) &&
827 !IN_FARSPACE(SPEC_OCLS(setype)) &&
828 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
830 SPIL_LOC(IC_RIGHT(ic)) =
831 SPIL_LOC(IC_RESULT(ic));
835 /*-----------------------------------------------------------------*/
836 /* setUsesDef - sets the uses def bitvector for a given operand */
837 /*-----------------------------------------------------------------*/
838 void setUsesDefs (operand *op, bitVect *bdefs,
839 bitVect *idefs, bitVect **oud)
841 /* compute the definitions alive at this point */
842 bitVect *adefs = bitVectUnion(bdefs,idefs);
844 /* of these definitions find the ones that are */
845 /* for this operand */
846 adefs = bitVectIntersect(adefs,OP_DEFS(op));
848 /* these are the definitions that this operand can use */
849 op->usesDefs = adefs;
851 /* the out defs is an union */
852 *oud = bitVectUnion(*oud,adefs);
855 /*-----------------------------------------------------------------*/
856 /* unsetDefsAndUses - clear this operation for the operands */
857 /*-----------------------------------------------------------------*/
858 void unsetDefsAndUses ( iCode *ic )
860 if ( ic->op == JUMPTABLE)
863 /* take away this definition from the def chain of the */
864 /* result & take away from use set of the operands */
866 /* turn off def set */
867 if (IS_SYMOP(IC_RESULT(ic))) {
868 if ( !POINTER_SET(ic))
869 bitVectUnSetBit(OP_DEFS(IC_RESULT(ic)),ic->key);
871 bitVectUnSetBit(OP_USES(IC_RESULT(ic)),ic->key);
873 /* turn off the useSet for the operands */
874 if (IS_SYMOP(IC_LEFT(ic)))
875 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
877 if (IS_SYMOP(IC_RIGHT(ic)))
878 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
880 else /* must be ifx turn off the use */
881 if (IS_SYMOP(IC_COND(ic)))
882 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
885 /*-----------------------------------------------------------------*/
886 /* ifxOptimize - changes ifx conditions if it can */
887 /*-----------------------------------------------------------------*/
888 void ifxOptimize (iCode *ic, set *cseSet,
890 eBBlock *ebb, int *change,
891 eBBlock **ebbs, int count)
896 /* if the condition can be replaced */
899 applyToSetFTrue (cseSet,findCheaperOp,IC_COND(ic),&pdop);
906 /* if the conditional is a literal then */
907 if (IS_OP_LITERAL(IC_COND(ic))) {
909 if ( (operandLitValue(IC_COND(ic)) != 0.0) && IC_TRUE(ic)) {
911 /* change to a goto */
913 IC_LABEL(ic) = IC_TRUE(ic);
918 if (!operandLitValue(IC_COND(ic)) && IC_FALSE(ic)) {
920 IC_LABEL(ic) = IC_FALSE(ic);
924 /* then kill this if condition */
925 remiCodeFromeBBlock (ebb,ic);
929 /* now we need to recompute the control flow */
930 /* since the control flow has changed */
931 /* this is very expensive but it does not happen */
932 /* too often, if it does happen then the user pays */
934 computeControlFlow (ebbs,count,1);
935 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
939 /* if there is only one successor and that successor
940 is the same one we are conditionally going to then
941 we can remove this conditional statement */
942 label = (IC_TRUE(ic) ? IC_TRUE(ic) : IC_FALSE(ic));
943 if (elementsInSet(ebb->succList) == 1 &&
944 isinSet(ebb->succList,eBBWithEntryLabel(ebbs,label,count))) {
946 remiCodeFromeBBlock(ebb,ic);
947 computeControlFlow (ebbs,count,1);
948 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
953 /* if it remains an IFX the update the use Set */
954 OP_USES(IC_COND(ic)) = bitVectSetBit(OP_USES(IC_COND(ic)),ic->key);
955 setUsesDefs(IC_COND(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
959 /*-----------------------------------------------------------------*/
960 /* diCodeForSym - finds the definiting instruction for a symbol */
961 /*-----------------------------------------------------------------*/
962 DEFSETFUNC(diCodeForSym)
965 V_ARG(operand *,sym);
968 /* if already found */
972 /* if not if this is the defining iCode */
973 if (sym->key == cdp->key) {
981 /*-----------------------------------------------------------------*/
982 /* constFold - does some constant folding */
983 /*-----------------------------------------------------------------*/
984 int constFold (iCode *ic, set *cseSet)
988 /* this routine will change
994 /* deal with only + & - */
999 /* this check is a hueristic to prevent live ranges
1000 from becoming too long */
1001 if (IS_PTR(operandType(IC_RESULT(ic))))
1004 /* check if operation with a literal */
1005 if (!IS_OP_LITERAL(IC_RIGHT(ic)))
1008 /* check if we can find a definition for the
1010 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(ic),&dic)))
1013 /* check that this is also a +/- */
1014 if (dic->op != '+' && dic->op != '-')
1017 /* with a literal */
1018 if (!IS_OP_LITERAL(IC_RIGHT(dic)))
1021 /* find the definition of the left operand
1022 of dic.then check if this defined with a
1023 get_pointer return 0 if the pointer size is
1024 less than 2 (MCS51 specific) */
1025 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(dic),&ldic)))
1028 if (POINTER_GET(ldic) && getSize(operandType(IC_LEFT(ldic))) <= 1)
1031 /* it is if the operations are the same*/
1032 /* the literal parts need to be added */
1033 IC_LEFT(ic) = operandFromOperand(IC_LEFT(dic));
1034 if (ic->op == dic->op )
1035 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic))+
1036 operandLitValue(IC_RIGHT(dic)));
1038 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) -
1039 operandLitValue(IC_RIGHT(dic)));
1041 if (IS_ITEMP(IC_RESULT(ic))) {
1042 SPIL_LOC(IC_RESULT(ic)) = NULL;
1043 IC_RESULT(ic)->noSpilLoc = 1;
1050 /*-----------------------------------------------------------------*/
1051 /* deleteGetPointers - called when a pointer is passed as parm */
1052 /* will delete from cseSet all get pointers computed from this */
1053 /* pointer. A simple ifOperandsHave is not good enough here */
1054 /*-----------------------------------------------------------------*/
1055 static void deleteGetPointers (set **cseSet, set **pss, operand *op,eBBlock *ebb)
1057 set *compItems = NULL;
1062 if (!*cseSet && !*pss)
1065 /* first find all items computed from this operand .
1066 This done fairly simply go thru the list and find
1067 those that are computed by arthimetic with this
1069 for (cdp = setFirstItem(*cseSet); cdp ; cdp = setNextItem(*cseSet)) {
1070 if (IS_ARITHMETIC_OP(cdp->diCode)) {
1071 if (isOperandEqual(IC_LEFT(cdp->diCode),op) ||
1072 isOperandEqual(IC_RIGHT(cdp->diCode),op)) {
1073 /* save it in our list of items */
1074 addSet(&compItems,IC_RESULT(cdp->diCode));
1076 /* also check for those computed from our computed
1077 list . This will take care of situations like
1078 iTemp1 = iTemp0 + 8;
1079 iTemp2 = iTemp1 + 8; */
1080 if (isinSetWith(compItems,IC_LEFT(cdp->diCode),isOperandEqual) ||
1081 isinSetWith(compItems,IC_RIGHT(cdp->diCode),isOperandEqual)) {
1082 addSet(&compItems,IC_RESULT(cdp->diCode));
1087 /* now delete all pointer gets with this op */
1088 deleteItemIf(cseSet,ifPointerGet,op);
1089 deleteItemIf(pss,ifPointerSet,op);
1091 /* set the bit vector used by dataFlow computation later */
1092 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,op->key);
1093 /* now for the computed items */
1094 for (cop = setFirstItem(compItems); cop ; cop = setNextItem(compItems)) {
1095 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,cop->key);
1096 deleteItemIf(cseSet,ifPointerGet,cop);
1097 deleteItemIf(pss,ifPointerSet,cop);
1101 /*-----------------------------------------------------------------*/
1102 /* delGetPointerSucc - delete get pointer from inExprs of succ with*/
1103 /* dfnum > supplied */
1104 /*-----------------------------------------------------------------*/
1105 DEFSETFUNC(delGetPointerSucc)
1107 eBBlock *ebp = item;
1108 V_ARG(operand *,op);
1115 if (ebp->dfnum > dfnum) {
1116 deleteItemIf(&ebp->inExprs,ifPointerGet,op);
1119 return applyToSet(ebp->succList,delGetPointerSucc,op,dfnum);
1122 /*-----------------------------------------------------------------*/
1123 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1124 /*-----------------------------------------------------------------*/
1125 static void fixUpTypes(iCode *ic)
1127 link *t1 = operandType(IC_LEFT(ic)) ,*t2;
1129 extern PORT ds390_port;
1131 if (port == &ds390_port)
1137 /* for pointer_gets if the types of result & left r the
1138 same then change it type of result to next */
1140 checkType(t2=operandType(IC_RESULT(ic)),t1) == 1) {
1141 setOperandType(IC_RESULT(ic),t2->next);
1145 /*-----------------------------------------------------------------*/
1146 /* cseBBlock - common subexpression elimination for basic blocks */
1147 /* this is the hackiest kludgiest routine in the whole */
1148 /* system. also the most important, since almost all */
1149 /* data flow related information is computed by it */
1150 /*-----------------------------------------------------------------*/
1151 int cseBBlock ( eBBlock *ebb, int computeOnly,
1152 eBBlock **ebbs, int count)
1158 set *ptrSetSet = NULL;
1160 /* if this block is not reachable */
1164 /* set of common subexpressions */
1165 cseSet = setFromSet (ebb->inExprs) ;
1167 /* these will be computed by this routine */
1168 setToNull ((void **)&ebb->outDefs);
1169 setToNull ((void **)&ebb->defSet);
1170 setToNull ((void **)&ebb->usesDefs);
1171 setToNull ((void **)&ebb->ptrsSet);
1172 setToNull ((void **)&ebb->addrOf);
1173 setToNull ((void **)&ebb->ldefs);
1175 ebb->outDefs = bitVectCopy (ebb->inDefs);
1176 bitVectDefault = iCodeKey;
1177 ebb->defSet = newBitVect(iCodeKey);
1178 ebb->usesDefs=newBitVect(iCodeKey);
1180 /* for all the instructions in this block do */
1181 for (ic = ebb->sch ; ic ; ic = ic->next ) {
1190 /* if this is an assignment from true symbol
1191 to a temp then do pointer post inc/dec optimzation */
1192 if (ic->op == '=' && !POINTER_SET(ic) &&
1193 IS_PTR(operandType(IC_RESULT(ic)))) {
1194 ptrPostIncDecOpt(ic);
1197 /* clear the def & use chains for the operands involved */
1198 /* in this operation . since it can change due to opts */
1199 unsetDefsAndUses (ic);
1201 if ( ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE) {
1202 /* add to defSet of the symbol */
1203 OP_DEFS(IC_RESULT(ic)) =
1204 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1205 /* add to the definition set of this block */
1206 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1207 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1208 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1209 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1210 /* delete global variables from the cseSet
1211 since they can be modified by the function call */
1212 deleteItemIf(&cseSet,ifDefGlobal);
1213 /* delete all getpointer iCodes from cseSet, this should
1214 be done only for global arrays & pointers but at this
1215 point we don't know if globals, so to be safe do all*/
1216 deleteItemIf(&cseSet,ifAnyGetPointer);
1219 /* for pcall & ipush we need to add to the useSet */
1220 if ((ic->op == PCALL ||
1224 IS_SYMOP(IC_LEFT(ic))) {
1226 /* check if they can be replaced */
1227 if ( !computeOnly ) {
1229 applyToSetFTrue(cseSet,findCheaperOp,IC_LEFT(ic),&pdop);
1231 IC_LEFT(ic) = pdop ;
1233 /* the lookup could have changed it*/
1234 if (IS_SYMOP(IC_LEFT(ic))) {
1235 OP_USES(IC_LEFT(ic)) =
1236 bitVectSetBit(OP_USES(IC_LEFT(ic)),ic->key);
1237 setUsesDefs(IC_LEFT(ic),ebb->defSet,
1238 ebb->outDefs,&ebb->usesDefs);
1242 /* if we a sending a pointer as a parameter
1243 then kill all cse since the pointed to item
1244 might be changed in the function being called */
1245 if ((ic->op == IPUSH || ic->op == SEND) &&
1246 IS_PTR(operandType(IC_LEFT(ic)))) {
1247 deleteGetPointers(&cseSet,&ptrSetSet,IC_LEFT(ic),ebb);
1248 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_LEFT(ic)->key);
1249 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1250 applyToSet(ebb->succList,delGetPointerSucc,
1251 IC_LEFT(ic),ebb->dfnum);
1256 /* if jumptable then mark the usage */
1257 if (ic->op == JUMPTABLE ) {
1258 OP_USES(IC_JTCOND(ic)) =
1259 bitVectSetBit(OP_USES(IC_JTCOND(ic)),ic->key);
1260 setUsesDefs(IC_JTCOND(ic),ebb->defSet,
1261 ebb->outDefs,&ebb->usesDefs);
1268 /* do some algebraic optimizations if possible */
1270 while (constFold(ic,cseSet));
1273 if (POINTER_GET(ic) && !IS_PTR(operandType(IC_LEFT(ic)))) {
1274 setOperandType(IC_LEFT(ic),
1275 aggrToPtr(operandType(IC_LEFT(ic)),FALSE));
1279 if (POINTER_SET(ic) && !IS_PTR(operandType(IC_RESULT(ic)))) {
1280 setOperandType(IC_RESULT(ic),
1281 aggrToPtr(operandType(IC_RESULT(ic)),FALSE));
1284 /* if this is a condition statment then */
1285 /* check if the condition can be replaced */
1286 if (ic->op == IFX ) {
1287 ifxOptimize (ic, cseSet, computeOnly,
1293 /* if the assignment & result is a temp */
1294 /* see if we can replace it */
1295 if (ic->op == '=') {
1297 /* update the spill location for this */
1298 updateSpillLocation (ic);
1300 if (POINTER_SET(ic)) {
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);