1 /*-------------------------------------------------------------------------
2 SDCCcse.c - source file for Common Subexpressions and other utility
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 In other words, you are welcome to use, share and improve this program.
21 You are forbidden to forbid anyone else to use, share and improve
22 what you give them. Help stamp out software-hoarding!
23 -------------------------------------------------------------------------*/
28 /*-----------------------------------------------------------------*/
29 /* newCseDef - new cseDef */
30 /*-----------------------------------------------------------------*/
32 newCseDef (operand * sym, iCode * ic)
37 cdp = Safe_calloc (1, sizeof (cseDef));
48 /*-----------------------------------------------------------------*/
49 /* int isCseDefEqual - two definitions are equal */
50 /*-----------------------------------------------------------------*/
52 isCseDefEqual (void *vsrc, void *vdest)
60 return (src->key == dest->key &&
61 src->diCode == dest->diCode);
65 /*-----------------------------------------------------------------*/
66 /* pcseDef - in the cseDef */
67 /*-----------------------------------------------------------------*/
69 pcseDef (void *item, va_list ap)
77 fprintf (stdout, "**null op**");
78 printOperand (cdp->sym, stdout);
79 icTab = getTableEntry (cdp->diCode->op);
80 icTab->iCodePrint (stdout, cdp->diCode, icTab->printName);
84 /*-----------------------------------------------------------------*/
85 /* replaceAllSymBySym - replaces all operands by operand in an */
86 /* instruction chain */
87 /*-----------------------------------------------------------------*/
89 replaceAllSymBySym (iCode * ic, operand * from, operand * to, bitVect ** ndpset)
93 for (lic = ic; lic; lic = lic->next)
97 /* do the special cases first */
101 IC_COND (lic)->key == from->key)
104 bitVectUnSetBit (OP_USES (from), lic->key);
105 OP_USES (to) = bitVectSetBit (OP_USES (to), lic->key);
106 siaddr = IC_COND (lic)->isaddr;
107 IC_COND (lic) = operandFromOperand (to);
108 IC_COND (lic)->isaddr = siaddr;
114 if (lic->op == JUMPTABLE)
117 IC_JTCOND (lic)->key == from->key)
120 bitVectUnSetBit (OP_USES (from), lic->key);
121 OP_USES (to) = bitVectSetBit (OP_USES (to), lic->key);
122 siaddr = IC_COND (lic)->isaddr;
123 IC_JTCOND (lic) = operandFromOperand (to);
124 IC_JTCOND (lic)->isaddr = siaddr;
130 if (IC_RESULT (lic) && IC_RESULT (lic)->key == from->key)
132 /* maintain du chains */
133 if (POINTER_SET (lic))
135 bitVectUnSetBit (OP_USES (from), lic->key);
136 OP_USES (to) = bitVectSetBit (OP_USES (to), lic->key);
138 /* also check if the "from" was in the non-dominating
139 pointer sets and replace it with "to" in the bitVector */
140 if (bitVectBitValue (*ndpset, from->key))
142 bitVectUnSetBit (*ndpset, from->key);
143 bitVectSetBit (*ndpset, to->key);
149 bitVectUnSetBit (OP_DEFS (from), lic->key);
150 OP_DEFS (to) = bitVectSetBit (OP_DEFS (to), lic->key);
152 siaddr = IC_RESULT (lic)->isaddr;
153 IC_RESULT (lic) = operandFromOperand (to);
154 IC_RESULT (lic)->isaddr = siaddr;
158 IC_RIGHT (lic) && IC_RIGHT (lic)->key == from->key)
160 bitVectUnSetBit (OP_USES (from), lic->key);
161 OP_USES (to) = bitVectSetBit (OP_USES (to), lic->key);
162 siaddr = IC_RIGHT (lic)->isaddr;
163 IC_RIGHT (lic) = operandFromOperand (to);
164 IC_RIGHT (lic)->isaddr = siaddr;
168 IC_LEFT (lic) && IC_LEFT (lic)->key == from->key)
170 bitVectUnSetBit (OP_USES (from), lic->key);
171 OP_USES (to) = bitVectSetBit (OP_USES (to), lic->key);
172 siaddr = IC_LEFT (lic)->isaddr;
173 IC_LEFT (lic) = operandFromOperand (to);
174 IC_LEFT (lic)->isaddr = siaddr;
179 /*-----------------------------------------------------------------*/
180 /* iCodeKeyIs - if the icode keys match then return 1 */
181 /*-----------------------------------------------------------------*/
182 DEFSETFUNC (iCodeKeyIs)
187 if (cdp->diCode->key == key)
193 /*-----------------------------------------------------------------*/
194 /* removeFromInExprs - removes an icode from inexpressions */
195 /*-----------------------------------------------------------------*/
196 DEFSETFUNC (removeFromInExprs)
200 V_ARG (operand *, from);
201 V_ARG (operand *, to);
202 V_ARG (eBBlock *, cbp);
208 deleteItemIf (&ebp->inExprs, iCodeKeyIs, ic->key);
209 if (ebp != cbp && !bitVectBitValue (cbp->domVect, ebp->bbnum))
210 replaceAllSymBySym (ebp->sch, from, to, &ebp->ndompset);
212 applyToSet (ebp->succList, removeFromInExprs, ic, from, to, cbp);
216 /*-----------------------------------------------------------------*/
217 /* isGlobalInNearSpace - return TRUE if valriable is a globalin data */
218 /*-----------------------------------------------------------------*/
220 isGlobalInNearSpace (operand * op)
222 sym_link *type = getSpec (operandType (op));
223 /* this is 8051 specific: optimization
224 suggested by Jean-Louis VERN, with 8051s we have no
225 advantage of putting variables in near space into
227 if (isOperandGlobal (op) && !IN_FARSPACE (SPEC_OCLS (type)) &&
228 IN_DIRSPACE (SPEC_OCLS (type)))
234 /*-----------------------------------------------------------------*/
235 /* findCheaperOp - cseBBlock support routine, will check to see if */
236 /* we have a operand previously defined */
237 /*-----------------------------------------------------------------*/
238 DEFSETFUNC (findCheaperOp)
241 V_ARG (operand *, cop);
242 V_ARG (operand **, opp);
244 /* if we have already found it */
248 /* not found it yet check if this is the one */
249 /* and this is not the defining one */
250 if (cop->key == cdp->key)
253 /* do a special check this will help in */
254 /* constant propagation & dead code elim */
255 /* for assignments only */
256 if (cdp->diCode->op == '=') {
257 /* if the result is volatile then return result */
258 if (IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
259 *opp = IC_RESULT (cdp->diCode);
261 /* if this is a straight assignment and
262 left is a temp then prefer the temporary to the
264 if (!POINTER_SET (cdp->diCode) &&
265 IS_ITEMP (IC_RESULT (cdp->diCode)) &&
266 IS_TRUE_SYMOP (IC_RIGHT (cdp->diCode)))
267 *opp = IC_RESULT (cdp->diCode);
269 /* if straight assignement && and both
270 are temps then prefer the one that
271 will not need extra space to spil, also
272 take into consideration if right side
273 an induction variable
275 if (!POINTER_SET (cdp->diCode) &&
276 IS_ITEMP (IC_RESULT (cdp->diCode)) &&
277 IS_ITEMP (IC_RIGHT (cdp->diCode)) &&
278 !OP_SYMBOL (IC_RIGHT (cdp->diCode))->isind &&
279 ((!SPIL_LOC (IC_RIGHT (cdp->diCode)) &&
280 SPIL_LOC (IC_RESULT (cdp->diCode))) ||
281 (SPIL_LOC (IC_RESULT (cdp->diCode)) &&
282 SPIL_LOC (IC_RESULT (cdp->diCode)) ==
283 SPIL_LOC (IC_RIGHT (cdp->diCode)))))
284 *opp = IC_RESULT (cdp->diCode);
286 *opp = IC_RIGHT (cdp->diCode);
290 *opp = IC_RESULT (cdp->diCode);
293 /* if this is an assign to a temp. then check
294 if the right side is this then return this */
295 if (IS_TRUE_SYMOP (cop) &&
296 cdp->diCode->op == '=' &&
297 !POINTER_SET (cdp->diCode) &&
298 cop->key == IC_RIGHT (cdp->diCode)->key &&
299 !isGlobalInNearSpace (IC_RIGHT (cdp->diCode)) &&
300 IS_ITEMP (IC_RESULT (cdp->diCode)))
301 *opp = IC_RESULT (cdp->diCode);
304 (SPEC_USIGN(operandType (cop))==SPEC_USIGN(operandType (*opp))) &&
305 (SPEC_LONG(operandType (cop))==SPEC_LONG(operandType (*opp))))
308 if ((isGlobalInNearSpace (cop) &&
309 !isOperandLiteral (*opp)) ||
310 isOperandVolatile (*opp, FALSE)
317 if (cop->key == (*opp)->key)
323 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP (cop))
325 *opp = operandFromOperand (*opp);
326 (*opp)->isaddr = cop->isaddr;
336 /*-----------------------------------------------------------------*/
337 /* findPointerSet - finds the right side of a pointer set op */
338 /*-----------------------------------------------------------------*/
339 DEFSETFUNC (findPointerSet)
342 V_ARG (operand *, op);
343 V_ARG (operand **, opp);
344 V_ARG (operand *, rop);
346 if (POINTER_SET (cdp->diCode) &&
347 IC_RESULT (cdp->diCode)->key == op->key &&
348 !isOperandVolatile (IC_RESULT (cdp->diCode), TRUE) &&
349 !isOperandVolatile (IC_RIGHT (cdp->diCode), TRUE) &&
350 getSize (operandType (IC_RIGHT (cdp->diCode))) ==
351 getSize (operandType (rop)))
353 *opp = IC_RIGHT (cdp->diCode);
360 /*-----------------------------------------------------------------*/
361 /* findPrevIc - cseBBlock support function will return the iCode */
362 /* which matches the current one */
363 /*-----------------------------------------------------------------*/
364 DEFSETFUNC (findPrevIc)
368 V_ARG (iCode **, icp);
370 /* if already found */
374 /* if the iCodes are the same */
375 if (isiCodeEqual (ic, cdp->diCode) &&
376 isOperandEqual (cdp->sym, IC_RESULT (cdp->diCode)))
382 /* if iCodes are not the same */
383 /* see the operands maybe interchanged */
384 if (ic->op == cdp->diCode->op &&
385 (ic->op == '+' || ic->op == '*') &&
386 isOperandEqual (IC_LEFT (ic), IC_RIGHT (cdp->diCode)) &&
387 isOperandEqual (IC_RIGHT (ic), IC_LEFT (cdp->diCode)))
396 /*-----------------------------------------------------------------*/
397 /* ifDefGlobal - if definition is global */
398 /*-----------------------------------------------------------------*/
399 DEFSETFUNC (ifDefGlobal)
403 return (isOperandGlobal (cdp->sym));
406 /*-----------------------------------------------------------------*/
407 /* ifAnyGetPointer - if get pointer icode */
408 /*-----------------------------------------------------------------*/
409 DEFSETFUNC (ifAnyGetPointer)
413 if (cdp->diCode && POINTER_GET (cdp->diCode))
418 /*-----------------------------------------------------------------*/
419 /* ifOperandsHave - if any of the operand are the same as this */
420 /*-----------------------------------------------------------------*/
421 DEFSETFUNC (ifOperandsHave)
424 V_ARG (operand *, op);
427 if (IC_LEFT (cdp->diCode) &&
428 IS_SYMOP (IC_LEFT (cdp->diCode)) &&
429 IC_LEFT (cdp->diCode)->key == op->key)
432 if (IC_RIGHT (cdp->diCode) &&
433 IS_SYMOP (IC_RIGHT (cdp->diCode)) &&
434 IC_RIGHT (cdp->diCode)->key == op->key)
437 /* or if any of the operands are volatile */
438 if (IC_LEFT (cdp->diCode) &&
439 IS_OP_VOLATILE (IC_LEFT (cdp->diCode)))
442 if (IC_RIGHT (cdp->diCode) &&
443 IS_OP_VOLATILE (IC_RIGHT (cdp->diCode)))
447 if (IC_RESULT (cdp->diCode) &&
448 IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
454 /*-----------------------------------------------------------------*/
455 /* ifDefSymIs - if a definition is found in the set */
456 /*-----------------------------------------------------------------*/
458 ifDefSymIs (set * cseSet, operand * sym)
463 if (!sym || !IS_SYMOP (sym))
465 for (sl = cseSet; sl; sl = sl->next)
468 if (loop->sym->key == sym->key)
475 /*-----------------------------------------------------------------*/
476 /* ifDefSymIsX - will return 1 if the symbols match */
477 /*-----------------------------------------------------------------*/
478 DEFSETFUNC (ifDefSymIsX)
481 V_ARG (operand *, op);
484 return cdp->sym->key == op->key;
486 return (isOperandEqual (cdp->sym, op));
491 /*-----------------------------------------------------------------*/
492 /* ifDiCodeIs - returns truw if diCode is same */
493 /*-----------------------------------------------------------------*/
495 ifDiCodeIs (set * cseSet, iCode * ic)
503 for (sl = cseSet; sl; sl = sl->next)
506 if (loop->diCode == ic)
513 /*-----------------------------------------------------------------*/
514 /* ifPointerGet - returns true if the icode is pointer get sym */
515 /*-----------------------------------------------------------------*/
516 DEFSETFUNC (ifPointerGet)
519 V_ARG (operand *, op);
520 iCode *dic = cdp->diCode;
521 operand *left = IC_LEFT (cdp->diCode);
523 if (POINTER_GET (dic) && left->key == op->key)
529 /*-----------------------------------------------------------------*/
530 /* ifPointerSet - returns true if the icode is pointer set sym */
531 /*-----------------------------------------------------------------*/
532 DEFSETFUNC (ifPointerSet)
535 V_ARG (operand *, op);
537 if (POINTER_SET (cdp->diCode) &&
538 IC_RESULT (cdp->diCode)->key == op->key)
544 /*-----------------------------------------------------------------*/
545 /* ifDiCodeIsX - will return 1 if the symbols match */
546 /*-----------------------------------------------------------------*/
547 DEFSETFUNC (ifDiCodeIsX)
552 return cdp->diCode == ic;
556 /*-----------------------------------------------------------------*/
557 /* algebraicOpts - does some algebraic optimizations */
558 /*-----------------------------------------------------------------*/
560 algebraicOpts (iCode * ic)
562 /* we don't deal with the following iCodes
573 /* if both operands present & ! IFX */
574 /* then if they are both literal we */
575 /* perform the operation right now */
576 if (IC_RESULT (ic) &&
579 IS_OP_LITERAL (IC_LEFT (ic)) &&
580 IS_OP_LITERAL (IC_RIGHT (ic)))
583 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
586 operandType (IC_RESULT (ic)));
589 SET_RESULT_RIGHT (ic);
593 /* if not ifx & only one operand present */
594 if (IC_RESULT (ic) &&
596 IS_OP_LITERAL (IC_LEFT (ic)) &&
600 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
603 operandType (IC_RESULT (ic)));
606 SET_RESULT_RIGHT (ic);
611 /* a special case : or in short a kludgy solution will think
612 about a better solution over a glass of wine someday */
613 if (ic->op == GET_VALUE_AT_ADDRESS)
616 if (IS_ITEMP (IC_RESULT (ic)) &&
617 IS_TRUE_SYMOP (IC_LEFT (ic)))
621 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
622 IC_RIGHT (ic)->isaddr = 0;
624 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
625 IC_RESULT (ic)->isaddr = 0;
626 setOperandType (IC_RESULT (ic), operandType (IC_RIGHT (ic)));
630 if (IS_ITEMP (IC_LEFT (ic)) &&
631 IS_ITEMP (IC_RESULT (ic)) &&
632 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
633 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
634 !IC_LEFT (ic)->isaddr)
637 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
638 IC_RIGHT (ic)->isaddr = 0;
639 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
640 IC_RESULT (ic)->isaddr = 0;
648 /* depending on the operation */
652 /* if adding the same thing change to left shift by 1 */
653 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key &&
654 !IS_FLOAT (operandType (IC_RESULT (ic))))
657 IC_RIGHT (ic) = operandFromLit (1);
660 /* if addition then check if one of them is a zero */
661 /* if yes turn it into assignmnt */
662 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
663 operandLitValue (IC_LEFT (ic)) == 0.0)
668 SET_ISADDR (IC_RESULT (ic), 0);
669 SET_ISADDR (IC_RIGHT (ic), 0);
672 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
673 operandLitValue (IC_RIGHT (ic)) == 0.0)
677 IC_RIGHT (ic) = IC_LEFT (ic);
679 SET_ISADDR (IC_RIGHT (ic), 0);
680 SET_ISADDR (IC_RESULT (ic), 0);
685 /* if subtracting the the same thing then zero */
686 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
689 IC_RIGHT (ic) = operandFromLit (0);
691 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
692 IC_RESULT (ic)->isaddr = 0;
696 /* if subtraction then check if one of the operand */
697 /* is zero then depending on which operand change */
698 /* to assignment or unary minus */
699 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
700 operandLitValue (IC_RIGHT (ic)) == 0.0)
702 /* right size zero change to assignment */
704 IC_RIGHT (ic) = IC_LEFT (ic);
706 SET_ISADDR (IC_RIGHT (ic), 0);
707 SET_ISADDR (IC_RESULT (ic), 0);
710 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
711 operandLitValue (IC_LEFT (ic)) == 0.0)
713 /* left zero turn into an unary minus */
715 IC_LEFT (ic) = IC_RIGHT (ic);
716 IC_RIGHT (ic) = NULL;
720 /* if multiplication then check if either of */
721 /* them is zero then the result is zero */
722 /* if either of them is one then result is */
725 if (IS_OP_LITERAL (IC_LEFT (ic)))
728 if (operandLitValue (IC_LEFT (ic)) == 0.0)
731 IC_RIGHT (ic) = IC_LEFT (ic);
733 SET_RESULT_RIGHT (ic);
736 if (operandLitValue (IC_LEFT (ic)) == 1.0)
740 SET_RESULT_RIGHT (ic);
745 if (IS_OP_LITERAL (IC_RIGHT (ic)))
748 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
752 SET_RESULT_RIGHT (ic);
756 if (operandLitValue (IC_RIGHT (ic)) == 1.0)
759 IC_RIGHT (ic) = IC_LEFT (ic);
761 SET_RESULT_RIGHT (ic);
767 /* if division by self then 1 */
768 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
771 IC_RIGHT (ic) = operandFromLit (1);
773 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
774 IC_RESULT (ic)->isaddr = 0;
776 /* if this is a division then check if right */
777 /* is one then change it to an assignment */
778 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
779 operandLitValue (IC_RIGHT (ic)) == 1.0)
783 IC_RIGHT (ic) = IC_LEFT (ic);
785 SET_RESULT_RIGHT (ic);
789 /* if both are the same for an comparison operators */
793 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
796 IC_RIGHT (ic) = operandFromLit (1);
798 SET_RESULT_RIGHT (ic);
804 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
807 IC_RIGHT (ic) = operandFromLit (0);
809 SET_RESULT_RIGHT (ic);
813 /* if this is a cast of a literal value */
814 if (IS_OP_LITERAL (IC_RIGHT (ic)))
818 operandFromValue (valCastLiteral (operandType (IC_LEFT (ic)),
819 operandLitValue (IC_RIGHT (ic))));
821 SET_ISADDR (IC_RESULT (ic), 0);
823 /* if casting to the same */
824 if (compareType (operandType (IC_RESULT (ic)),
825 operandType (IC_RIGHT (ic))) == 1)
829 SET_ISADDR (IC_RESULT (ic), 0);
833 if (IS_OP_LITERAL (IC_LEFT (ic)))
837 (operandLitValue (IC_LEFT (ic)) == 0 ?
838 operandFromLit (1) : operandFromLit (0));
840 SET_ISADDR (IC_RESULT (ic), 0);
846 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
847 /*-----------------------------------------------------------------*/
848 /* updateSpillLocation - keeps track of register spill location */
849 /*-----------------------------------------------------------------*/
851 updateSpillLocation (iCode * ic, int induction)
856 if (POINTER_SET (ic))
862 /* for the form true_symbol := iTempNN */
863 if (ASSIGN_ITEMP_TO_SYM (ic) &&
864 !SPIL_LOC (IC_RIGHT (ic))) {
866 setype = getSpec (operandType (IC_RESULT (ic)));
868 if (!OP_SYMBOL(IC_RIGHT (ic))->noSpilLoc &&
869 !IS_VOLATILE (setype) &&
870 !IN_FARSPACE (SPEC_OCLS (setype)) &&
871 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
873 SPIL_LOC (IC_RIGHT (ic)) =
874 IC_RESULT (ic)->operand.symOperand;
877 if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
879 if (!SPIL_LOC (IC_RIGHT (ic)) &&
880 !bitVectBitsInCommon (OP_DEFS (IC_RIGHT (ic)), OP_USES (IC_RESULT (ic))) &&
881 OP_SYMBOL (IC_RESULT (ic))->isreqv) {
883 setype = getSpec (operandType (IC_RESULT (ic)));
885 if (!OP_SYMBOL(IC_RIGHT (ic))->noSpilLoc &&
886 !IS_VOLATILE (setype) &&
887 !IN_FARSPACE (SPEC_OCLS (setype)) &&
888 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
890 SPIL_LOC (IC_RIGHT (ic)) =
891 SPIL_LOC (IC_RESULT (ic));
893 /* special case for inductions */
895 OP_SYMBOL(IC_RIGHT(ic))->isreqv &&
896 !SPIL_LOC(IC_RESULT(ic))) {
897 SPIL_LOC (IC_RESULT (ic)) = SPIL_LOC (IC_RIGHT (ic));
901 /*-----------------------------------------------------------------*/
902 /* setUsesDef - sets the uses def bitvector for a given operand */
903 /*-----------------------------------------------------------------*/
905 setUsesDefs (operand * op, bitVect * bdefs,
906 bitVect * idefs, bitVect ** oud)
908 /* compute the definitions alive at this point */
909 bitVect *adefs = bitVectUnion (bdefs, idefs);
911 /* of these definitions find the ones that are */
912 /* for this operand */
913 adefs = bitVectIntersect (adefs, OP_DEFS (op));
915 /* these are the definitions that this operand can use */
916 op->usesDefs = adefs;
918 /* the out defs is an union */
919 *oud = bitVectUnion (*oud, adefs);
922 /*-----------------------------------------------------------------*/
923 /* unsetDefsAndUses - clear this operation for the operands */
924 /*-----------------------------------------------------------------*/
926 unsetDefsAndUses (iCode * ic)
928 if (ic->op == JUMPTABLE)
931 /* take away this definition from the def chain of the */
932 /* result & take away from use set of the operands */
935 /* turn off def set */
936 if (IS_SYMOP (IC_RESULT (ic)))
938 if (!POINTER_SET (ic))
939 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
941 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
943 /* turn off the useSet for the operands */
944 if (IS_SYMOP (IC_LEFT (ic)))
945 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
947 if (IS_SYMOP (IC_RIGHT (ic)))
948 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
951 /* must be ifx turn off the use */ if (IS_SYMOP (IC_COND (ic)))
952 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
955 /*-----------------------------------------------------------------*/
956 /* ifxOptimize - changes ifx conditions if it can */
957 /*-----------------------------------------------------------------*/
959 ifxOptimize (iCode * ic, set * cseSet,
961 eBBlock * ebb, int *change,
962 eBBlock ** ebbs, int count)
967 /* if the condition can be replaced */
971 applyToSetFTrue (cseSet, findCheaperOp, IC_COND (ic), &pdop);
979 /* if the conditional is a literal then */
980 if (IS_OP_LITERAL (IC_COND (ic)))
983 if ((operandLitValue (IC_COND (ic)) != 0.0) && IC_TRUE (ic))
986 /* change to a goto */
988 IC_LABEL (ic) = IC_TRUE (ic);
995 if (!operandLitValue (IC_COND (ic)) && IC_FALSE (ic))
998 IC_LABEL (ic) = IC_FALSE (ic);
1004 /* then kill this if condition */
1005 remiCodeFromeBBlock (ebb, ic);
1009 /* now we need to recompute the control flow */
1010 /* since the control flow has changed */
1011 /* this is very expensive but it does not happen */
1012 /* too often, if it does happen then the user pays */
1014 computeControlFlow (ebbs, count, 1);
1015 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1019 /* if there is only one successor and that successor
1020 is the same one we are conditionally going to then
1021 we can remove this conditional statement */
1022 label = (IC_TRUE (ic) ? IC_TRUE (ic) : IC_FALSE (ic));
1023 if (elementsInSet (ebb->succList) == 1 &&
1024 isinSet (ebb->succList, eBBWithEntryLabel (ebbs, label, count)))
1027 remiCodeFromeBBlock (ebb, ic);
1028 computeControlFlow (ebbs, count, 1);
1029 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1034 /* if it remains an IFX the update the use Set */
1035 OP_USES (IC_COND (ic)) = bitVectSetBit (OP_USES (IC_COND (ic)), ic->key);
1036 setUsesDefs (IC_COND (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1040 /*-----------------------------------------------------------------*/
1041 /* diCodeForSym - finds the definiting instruction for a symbol */
1042 /*-----------------------------------------------------------------*/
1043 DEFSETFUNC (diCodeForSym)
1046 V_ARG (operand *, sym);
1047 V_ARG (iCode **, dic);
1049 /* if already found */
1053 /* if not if this is the defining iCode */
1054 if (sym->key == cdp->key)
1063 /*-----------------------------------------------------------------*/
1064 /* constFold - does some constant folding */
1065 /*-----------------------------------------------------------------*/
1067 constFold (iCode * ic, set * cseSet)
1071 /* this routine will change
1077 /* deal with only + & - */
1078 if (ic->op != '+' &&
1082 /* this check is a hueristic to prevent live ranges
1083 from becoming too long */
1084 if (IS_PTR (operandType (IC_RESULT (ic))))
1087 /* check if operation with a literal */
1088 if (!IS_OP_LITERAL (IC_RIGHT (ic)))
1091 /* check if we can find a definition for the
1093 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (ic), &dic)))
1096 /* check that this is also a +/- */
1097 if (dic->op != '+' && dic->op != '-')
1100 /* with a literal */
1101 if (!IS_OP_LITERAL (IC_RIGHT (dic)))
1104 /* find the definition of the left operand
1105 of dic.then check if this defined with a
1106 get_pointer return 0 if the pointer size is
1107 less than 2 (MCS51 specific) */
1108 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (dic), &ldic)))
1111 if (POINTER_GET (ldic) && getSize (operandType (IC_LEFT (ldic))) <= 1)
1114 /* it is if the operations are the same */
1115 /* the literal parts need to be added */
1116 IC_LEFT (ic) = operandFromOperand (IC_LEFT (dic));
1117 if (ic->op == dic->op)
1118 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) +
1119 operandLitValue (IC_RIGHT (dic)));
1121 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) -
1122 operandLitValue (IC_RIGHT (dic)));
1124 if (IS_ITEMP (IC_RESULT (ic)))
1126 SPIL_LOC (IC_RESULT (ic)) = NULL;
1127 OP_SYMBOL(IC_RESULT (ic))->noSpilLoc = 1;
1134 /*-----------------------------------------------------------------*/
1135 /* deleteGetPointers - called when a pointer is passed as parm */
1136 /* will delete from cseSet all get pointers computed from this */
1137 /* pointer. A simple ifOperandsHave is not good enough here */
1138 /*-----------------------------------------------------------------*/
1140 deleteGetPointers (set ** cseSet, set ** pss, operand * op, eBBlock * ebb)
1142 set *compItems = NULL;
1147 if (!*cseSet && !*pss)
1150 /* first find all items computed from this operand .
1151 This done fairly simply go thru the list and find
1152 those that are computed by arthimetic with this
1154 for (cdp = setFirstItem (*cseSet); cdp; cdp = setNextItem (*cseSet))
1156 if (IS_ARITHMETIC_OP (cdp->diCode))
1158 if (isOperandEqual (IC_LEFT (cdp->diCode), op) ||
1159 isOperandEqual (IC_RIGHT (cdp->diCode), op))
1161 /* save it in our list of items */
1162 addSet (&compItems, IC_RESULT (cdp->diCode));
1164 /* also check for those computed from our computed
1165 list . This will take care of situations like
1166 iTemp1 = iTemp0 + 8;
1167 iTemp2 = iTemp1 + 8; */
1168 if (isinSetWith (compItems, (void*)IC_LEFT (cdp->diCode),
1169 (insetwithFunc)isOperandEqual) ||
1170 isinSetWith (compItems, (void*)IC_RIGHT (cdp->diCode),
1171 (insetwithFunc)isOperandEqual))
1173 addSet (&compItems, IC_RESULT (cdp->diCode));
1178 /* now delete all pointer gets with this op */
1179 deleteItemIf (cseSet, ifPointerGet, op);
1180 deleteItemIf (pss, ifPointerSet, op);
1182 /* set the bit vector used by dataFlow computation later */
1183 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, op->key);
1184 /* now for the computed items */
1185 for (cop = setFirstItem (compItems); cop; cop = setNextItem (compItems))
1187 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, cop->key);
1188 deleteItemIf (cseSet, ifPointerGet, cop);
1189 deleteItemIf (pss, ifPointerSet, cop);
1193 /*-----------------------------------------------------------------*/
1194 /* delGetPointerSucc - delete get pointer from inExprs of succ with */
1195 /* dfnum > supplied */
1196 /*-----------------------------------------------------------------*/
1197 DEFSETFUNC (delGetPointerSucc)
1199 eBBlock *ebp = item;
1200 V_ARG (operand *, op);
1207 if (ebp->dfnum > dfnum)
1209 deleteItemIf (&ebp->inExprs, ifPointerGet, op);
1212 return applyToSet (ebp->succList, delGetPointerSucc, op, dfnum);
1215 /*-----------------------------------------------------------------*/
1216 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1217 /*-----------------------------------------------------------------*/
1219 fixUpTypes (iCode * ic)
1221 sym_link *t1 = operandType (IC_LEFT (ic)), *t2;
1223 if (TARGET_IS_DS390)
1229 /* for pointer_gets if the types of result & left r the
1230 same then change it type of result to next */
1232 compareType (t2 = operandType (IC_RESULT (ic)), t1) == 1)
1234 setOperandType (IC_RESULT (ic), t2->next);
1238 /*-----------------------------------------------------------------*/
1239 /* cseBBlock - common subexpression elimination for basic blocks */
1240 /* this is the hackiest kludgiest routine in the whole */
1241 /* system. also the most important, since almost all */
1242 /* data flow related information is computed by it */
1243 /*-----------------------------------------------------------------*/
1245 cseBBlock (eBBlock * ebb, int computeOnly,
1246 eBBlock ** ebbs, int count)
1252 set *ptrSetSet = NULL;
1254 /* if this block is not reachable */
1258 /* set of common subexpressions */
1259 cseSet = setFromSet (ebb->inExprs);
1261 /* these will be computed by this routine */
1262 setToNull ((void **) &ebb->outDefs);
1263 setToNull ((void **) &ebb->defSet);
1264 setToNull ((void **) &ebb->usesDefs);
1265 setToNull ((void **) &ebb->ptrsSet);
1266 setToNull ((void **) &ebb->addrOf);
1267 setToNull ((void **) &ebb->ldefs);
1269 ebb->outDefs = bitVectCopy (ebb->inDefs);
1270 bitVectDefault = iCodeKey;
1271 ebb->defSet = newBitVect (iCodeKey);
1272 ebb->usesDefs = newBitVect (iCodeKey);
1274 /* for all the instructions in this block do */
1275 for (ic = ebb->sch; ic; ic = ic->next)
1285 /* if this is an assignment from true symbol
1286 to a temp then do pointer post inc/dec optimzation */
1287 if (ic->op == '=' && !POINTER_SET (ic) &&
1288 IS_PTR (operandType (IC_RESULT (ic))))
1290 ptrPostIncDecOpt (ic);
1293 /* clear the def & use chains for the operands involved */
1294 /* in this operation . since it can change due to opts */
1295 unsetDefsAndUses (ic);
1297 if (ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE)
1299 /* add to defSet of the symbol */
1300 OP_DEFS (IC_RESULT (ic)) =
1301 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1302 /* add to the definition set of this block */
1303 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1304 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1305 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1306 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1307 /* delete global variables from the cseSet
1308 since they can be modified by the function call */
1309 deleteItemIf (&cseSet, ifDefGlobal);
1310 /* delete all getpointer iCodes from cseSet, this should
1311 be done only for global arrays & pointers but at this
1312 point we don't know if globals, so to be safe do all */
1313 deleteItemIf (&cseSet, ifAnyGetPointer);
1316 /* for pcall & ipush we need to add to the useSet */
1317 if ((ic->op == PCALL ||
1321 IS_SYMOP (IC_LEFT (ic)))
1324 /* check if they can be replaced */
1328 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1330 IC_LEFT (ic) = pdop;
1332 /* the lookup could have changed it */
1333 if (IS_SYMOP (IC_LEFT (ic)))
1335 OP_USES (IC_LEFT (ic)) =
1336 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1337 setUsesDefs (IC_LEFT (ic), ebb->defSet,
1338 ebb->outDefs, &ebb->usesDefs);
1342 /* if we a sending a pointer as a parameter
1343 then kill all cse since the pointed to item
1344 might be changed in the function being called */
1345 if ((ic->op == IPUSH || ic->op == SEND) &&
1346 IS_PTR (operandType (IC_LEFT (ic))))
1348 deleteGetPointers (&cseSet, &ptrSetSet, IC_LEFT (ic), ebb);
1349 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_LEFT (ic)->key);
1350 for (i = 0; i < count; ebbs[i++]->visited = 0);
1351 applyToSet (ebb->succList, delGetPointerSucc,
1352 IC_LEFT (ic), ebb->dfnum);
1357 /* if jumptable then mark the usage */
1358 if (ic->op == JUMPTABLE)
1360 OP_USES (IC_JTCOND (ic)) =
1361 bitVectSetBit (OP_USES (IC_JTCOND (ic)), ic->key);
1362 setUsesDefs (IC_JTCOND (ic), ebb->defSet,
1363 ebb->outDefs, &ebb->usesDefs);
1370 /* do some algebraic optimizations if possible */
1372 while (constFold (ic, cseSet));
1375 if (POINTER_GET (ic) && !IS_PTR (operandType (IC_LEFT (ic))))
1377 setOperandType (IC_LEFT (ic),
1378 aggrToPtr (operandType (IC_LEFT (ic)), FALSE));
1382 if (POINTER_SET (ic) && !IS_PTR (operandType (IC_RESULT (ic))))
1384 setOperandType (IC_RESULT (ic),
1385 aggrToPtr (operandType (IC_RESULT (ic)), FALSE));
1388 /* if this is a condition statment then */
1389 /* check if the condition can be replaced */
1392 ifxOptimize (ic, cseSet, computeOnly,
1398 /* if the assignment & result is a temp */
1399 /* see if we can replace it */
1403 /* update the spill location for this */
1404 updateSpillLocation (ic,1);
1406 if (POINTER_SET (ic) &&
1407 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype)))
1410 applyToSetFTrue (cseSet, findCheaperOp, IC_RESULT (ic), &pdop);
1411 if (pdop && IS_ITEMP (pdop) && !computeOnly)
1412 IC_RESULT (ic) = pdop;
1416 /* do the operand lookup i.e. for both the */
1417 /* right & left operand : check the cseSet */
1418 /* to see if they have been replaced if yes */
1419 /* then replace them with those from cseSet */
1421 /* and left is a symbol */
1422 if (IS_SYMOP (IC_LEFT (ic)) &&
1423 !computeOnly && ic->op != ADDRESS_OF)
1427 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1430 if (POINTER_GET (ic))
1432 if (IS_ITEMP (pdop) || IS_OP_LITERAL (pdop))
1434 IC_LEFT (ic) = pdop;
1437 /* check if there is a pointer set
1438 for the same pointer visible if yes
1439 then change this into an assignment */
1441 if (applyToSetFTrue (cseSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic)) &&
1442 !bitVectBitValue (ebb->ptrsSet, pdop->key))
1445 IC_LEFT (ic) = NULL;
1446 IC_RIGHT (ic) = pdop;
1447 SET_ISADDR (IC_RESULT (ic), 0);
1453 IC_LEFT (ic) = pdop;
1460 if (IS_SYMOP (IC_RIGHT (ic)) && !computeOnly)
1464 applyToSetFTrue (cseSet, findCheaperOp, IC_RIGHT (ic), &pdop);
1468 IC_RIGHT (ic) = pdop;
1473 /* if left or right changed then do algebraic */
1477 while (constFold (ic, cseSet));
1480 /* if after all this it becomes a assignment to self
1481 then delete it and continue */
1482 if (ASSIGNMENT_TO_SELF (ic))
1484 remiCodeFromeBBlock (ebb, ic);
1488 /* now we will check to see if the entire */
1489 /* operation has been performed before */
1490 /* and is available */
1491 /* don't do assignments they will be killed */
1492 /* by dead code elimination if required do */
1493 /* it only if result is a temporary */
1495 if (!(POINTER_GET (ic) &&
1496 (IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1497 isOperandVolatile (IC_LEFT (ic), TRUE) ||
1498 bitVectBitValue (ebb->ndompset, IC_LEFT (ic)->key))) &&
1500 IS_ITEMP (IC_RESULT (ic)) &&
1503 applyToSet (cseSet, findPrevIc, ic, &pdic);
1504 if (pdic && compareType (operandType (IC_RESULT (pdic)),
1505 operandType (IC_RESULT (ic))) != 1)
1509 /* if found then eliminate this and add to */
1510 /* to cseSet an element containing result */
1511 /* of this with previous opcode */
1515 if (IS_ITEMP (IC_RESULT (ic)))
1518 /* replace in the remaining of this block */
1519 replaceAllSymBySym (ic->next, IC_RESULT (ic), IC_RESULT (pdic), &ebb->ndompset);
1520 /* remove this iCode from inexpressions of all
1521 its successors, it cannot be in the in expressions
1522 of any of the predecessors */
1523 for (i = 0; i < count; ebbs[i++]->visited = 0);
1524 applyToSet (ebb->succList, removeFromInExprs, ic, IC_RESULT (ic),
1525 IC_RESULT (pdic), ebb);
1527 /* if this was moved from another block */
1528 /* then replace in those blocks too */
1532 for (owner = setFirstItem (ic->movedFrom); owner;
1533 owner = setNextItem (ic->movedFrom))
1534 replaceAllSymBySym (owner->sch, IC_RESULT (ic), IC_RESULT (pdic), &owner->ndompset);
1536 pdic->movedFrom = unionSets (pdic->movedFrom, ic->movedFrom, THROW_NONE);
1539 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), pdic));
1542 /* eliminate this */
1543 remiCodeFromeBBlock (ebb, ic);
1548 if (IS_ITEMP (IC_RESULT (ic)))
1555 /* just add this as a previous expression except in */
1556 /* case of a pointer access in which case this is a */
1557 /* usage not a definition */
1558 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1560 deleteItemIf (&cseSet, ifDefSymIsX, IC_RESULT (ic));
1561 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), ic));
1567 /* if assignment to a parameter which is not
1568 mine and type is a pointer then delete
1569 pointerGets to take care of aliasing */
1570 if (ASSIGNMENT (ic) &&
1571 OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))) &&
1572 IS_PTR (operandType (IC_RESULT (ic))))
1574 deleteGetPointers (&cseSet, &ptrSetSet, IC_RIGHT (ic), ebb);
1575 for (i = 0; i < count; ebbs[i++]->visited = 0);
1576 applyToSet (ebb->succList, delGetPointerSucc, IC_RIGHT (ic), ebb->dfnum);
1577 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RIGHT (ic)->key);
1580 /* if this is a pointerget then see if we can replace
1581 this with a previously assigned pointer value */
1582 if (POINTER_GET (ic) &&
1583 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1584 isOperandVolatile (IC_LEFT (ic), TRUE)))
1587 applyToSet (ptrSetSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic));
1588 /* if we find it then locally replace all
1589 references to the result with what we assigned */
1592 replaceAllSymBySym (ic->next, IC_RESULT (ic), pdop, &ebb->ndompset);
1596 /* delete from the cseSet anything that has */
1597 /* operands matching the result of this */
1598 /* except in case of pointer access */
1599 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1601 deleteItemIf (&cseSet, ifOperandsHave, IC_RESULT (ic));
1602 /* delete any previous definitions */
1603 ebb->defSet = bitVectCplAnd (ebb->defSet, OP_DEFS (IC_RESULT (ic)));
1607 /* add the left & right to the defUse set */
1608 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)))
1610 OP_USES (IC_LEFT (ic)) =
1611 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1612 setUsesDefs (IC_LEFT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1616 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)))
1618 OP_USES (IC_RIGHT (ic)) =
1619 bitVectSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1620 setUsesDefs (IC_RIGHT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1624 /* for the result it is special case, put the result */
1625 /* in the defuseSet if it a pointer or array access */
1626 if (POINTER_SET (defic))
1628 OP_USES (IC_RESULT (ic)) =
1629 bitVectSetBit (OP_USES (IC_RESULT (ic)), ic->key);
1630 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1631 deleteItemIf (&cseSet, ifPointerGet, IC_RESULT (ic));
1632 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RESULT (ic)->key);
1633 /* delete from inexpressions of all successors which
1634 have dfNum > than this block */
1635 for (i = 0; i < count; ebbs[i++]->visited = 0);
1636 applyToSet (ebb->succList, delGetPointerSucc, IC_RESULT (ic), ebb->dfnum);
1638 /* delete from cseSet all other pointer sets
1640 deleteItemIf (&ptrSetSet, ifPointerSet, IC_RESULT (ic));
1641 /* add to the local pointerset set */
1642 addSetHead (&ptrSetSet, newCseDef (IC_RESULT (ic), ic));
1645 /* add the result to defintion set */ if (IC_RESULT (ic))
1647 OP_DEFS (IC_RESULT (ic)) =
1648 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1649 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1650 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1651 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1655 /* if this is an addressof instruction then */
1656 /* put the symbol in the address of list & */
1657 /* delete it from the cseSet */
1658 if (defic->op == ADDRESS_OF)
1660 addSetHead (&ebb->addrOf, IC_LEFT (ic));
1661 deleteItemIf (&cseSet, ifDefSymIsX, IC_LEFT (ic));
1665 setToNull ((void **) &ebb->outExprs);
1666 ebb->outExprs = cseSet;
1667 ebb->outDefs = bitVectUnion (ebb->outDefs, ebb->defSet);
1668 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet, ebb->inPtrsSet);
1672 /*-----------------------------------------------------------------*/
1673 /* cseAllBlocks - will sequentially go thru & do cse for all blocks */
1674 /*-----------------------------------------------------------------*/
1676 cseAllBlocks (eBBlock ** ebbs, int count)
1681 /* if optimization turned off */
1683 for (i = 0; i < count; i++)
1684 change += cseBBlock (ebbs[i], FALSE, ebbs, count);