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_SHORT(operandType (cop))==SPEC_SHORT(operandType (*opp))) &&
306 (SPEC_LONG(operandType (cop))==SPEC_LONG(operandType (*opp))))
309 if ((isGlobalInNearSpace (cop) &&
310 !isOperandLiteral (*opp)) ||
311 isOperandVolatile (*opp, FALSE)
318 if (cop->key == (*opp)->key)
324 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP (cop))
326 *opp = operandFromOperand (*opp);
327 (*opp)->isaddr = cop->isaddr;
337 /*-----------------------------------------------------------------*/
338 /* findPointerSet - finds the right side of a pointer set op */
339 /*-----------------------------------------------------------------*/
340 DEFSETFUNC (findPointerSet)
343 V_ARG (operand *, op);
344 V_ARG (operand **, opp);
345 V_ARG (operand *, rop);
347 if (POINTER_SET (cdp->diCode) &&
348 IC_RESULT (cdp->diCode)->key == op->key &&
349 !isOperandVolatile (IC_RESULT (cdp->diCode), TRUE) &&
350 !isOperandVolatile (IC_RIGHT (cdp->diCode), TRUE) &&
351 getSize (operandType (IC_RIGHT (cdp->diCode))) ==
352 getSize (operandType (rop)))
354 *opp = IC_RIGHT (cdp->diCode);
361 /*-----------------------------------------------------------------*/
362 /* findPrevIc - cseBBlock support function will return the iCode */
363 /* which matches the current one */
364 /*-----------------------------------------------------------------*/
365 DEFSETFUNC (findPrevIc)
369 V_ARG (iCode **, icp);
371 /* if already found */
375 /* if the iCodes are the same */
376 if (isiCodeEqual (ic, cdp->diCode) &&
377 isOperandEqual (cdp->sym, IC_RESULT (cdp->diCode)))
383 /* if iCodes are not the same */
384 /* see the operands maybe interchanged */
385 if (ic->op == cdp->diCode->op &&
386 (ic->op == '+' || ic->op == '*') &&
387 isOperandEqual (IC_LEFT (ic), IC_RIGHT (cdp->diCode)) &&
388 isOperandEqual (IC_RIGHT (ic), IC_LEFT (cdp->diCode)))
397 /*-----------------------------------------------------------------*/
398 /* ifDefGlobal - if definition is global */
399 /*-----------------------------------------------------------------*/
400 DEFSETFUNC (ifDefGlobal)
404 return (isOperandGlobal (cdp->sym));
407 /*-----------------------------------------------------------------*/
408 /* ifAnyGetPointer - if get pointer icode */
409 /*-----------------------------------------------------------------*/
410 DEFSETFUNC (ifAnyGetPointer)
414 if (cdp->diCode && POINTER_GET (cdp->diCode))
419 /*-----------------------------------------------------------------*/
420 /* ifOperandsHave - if any of the operand are the same as this */
421 /*-----------------------------------------------------------------*/
422 DEFSETFUNC (ifOperandsHave)
425 V_ARG (operand *, op);
428 if (IC_LEFT (cdp->diCode) &&
429 IS_SYMOP (IC_LEFT (cdp->diCode)) &&
430 IC_LEFT (cdp->diCode)->key == op->key)
433 if (IC_RIGHT (cdp->diCode) &&
434 IS_SYMOP (IC_RIGHT (cdp->diCode)) &&
435 IC_RIGHT (cdp->diCode)->key == op->key)
438 /* or if any of the operands are volatile */
439 if (IC_LEFT (cdp->diCode) &&
440 IS_OP_VOLATILE (IC_LEFT (cdp->diCode)))
443 if (IC_RIGHT (cdp->diCode) &&
444 IS_OP_VOLATILE (IC_RIGHT (cdp->diCode)))
448 if (IC_RESULT (cdp->diCode) &&
449 IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
455 /*-----------------------------------------------------------------*/
456 /* ifDefSymIs - if a definition is found in the set */
457 /*-----------------------------------------------------------------*/
459 ifDefSymIs (set * cseSet, operand * sym)
464 if (!sym || !IS_SYMOP (sym))
466 for (sl = cseSet; sl; sl = sl->next)
469 if (loop->sym->key == sym->key)
476 /*-----------------------------------------------------------------*/
477 /* ifDefSymIsX - will return 1 if the symbols match */
478 /*-----------------------------------------------------------------*/
479 DEFSETFUNC (ifDefSymIsX)
482 V_ARG (operand *, op);
485 return cdp->sym->key == op->key;
487 return (isOperandEqual (cdp->sym, op));
492 /*-----------------------------------------------------------------*/
493 /* ifDiCodeIs - returns truw if diCode is same */
494 /*-----------------------------------------------------------------*/
496 ifDiCodeIs (set * cseSet, iCode * ic)
504 for (sl = cseSet; sl; sl = sl->next)
507 if (loop->diCode == ic)
514 /*-----------------------------------------------------------------*/
515 /* ifPointerGet - returns true if the icode is pointer get sym */
516 /*-----------------------------------------------------------------*/
517 DEFSETFUNC (ifPointerGet)
520 V_ARG (operand *, op);
521 iCode *dic = cdp->diCode;
522 operand *left = IC_LEFT (cdp->diCode);
524 if (POINTER_GET (dic) && left->key == op->key)
530 /*-----------------------------------------------------------------*/
531 /* ifPointerSet - returns true if the icode is pointer set sym */
532 /*-----------------------------------------------------------------*/
533 DEFSETFUNC (ifPointerSet)
536 V_ARG (operand *, op);
538 if (POINTER_SET (cdp->diCode) &&
539 IC_RESULT (cdp->diCode)->key == op->key)
545 /*-----------------------------------------------------------------*/
546 /* ifDiCodeIsX - will return 1 if the symbols match */
547 /*-----------------------------------------------------------------*/
548 DEFSETFUNC (ifDiCodeIsX)
553 return cdp->diCode == ic;
557 /*-----------------------------------------------------------------*/
558 /* algebraicOpts - does some algebraic optimizations */
559 /*-----------------------------------------------------------------*/
561 algebraicOpts (iCode * ic)
563 /* we don't deal with the following iCodes
574 /* if both operands present & ! IFX */
575 /* then if they are both literal we */
576 /* perform the operation right now */
577 if (IC_RESULT (ic) &&
580 IS_OP_LITERAL (IC_LEFT (ic)) &&
581 IS_OP_LITERAL (IC_RIGHT (ic)))
584 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
587 operandType (IC_RESULT (ic)));
590 SET_RESULT_RIGHT (ic);
594 /* if not ifx & only one operand present */
595 if (IC_RESULT (ic) &&
597 IS_OP_LITERAL (IC_LEFT (ic)) &&
601 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
604 operandType (IC_RESULT (ic)));
607 SET_RESULT_RIGHT (ic);
612 /* a special case : or in short a kludgy solution will think
613 about a better solution over a glass of wine someday */
614 if (ic->op == GET_VALUE_AT_ADDRESS)
617 if (IS_ITEMP (IC_RESULT (ic)) &&
618 IS_TRUE_SYMOP (IC_LEFT (ic)))
622 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
623 IC_RIGHT (ic)->isaddr = 0;
625 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
626 IC_RESULT (ic)->isaddr = 0;
627 setOperandType (IC_RESULT (ic), operandType (IC_RIGHT (ic)));
631 if (IS_ITEMP (IC_LEFT (ic)) &&
632 IS_ITEMP (IC_RESULT (ic)) &&
633 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
634 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
635 !IC_LEFT (ic)->isaddr)
638 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
639 IC_RIGHT (ic)->isaddr = 0;
640 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
641 IC_RESULT (ic)->isaddr = 0;
649 /* depending on the operation */
653 /* if adding the same thing change to left shift by 1 */
654 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key &&
655 !IS_FLOAT (operandType (IC_RESULT (ic))))
658 IC_RIGHT (ic) = operandFromLit (1);
661 /* if addition then check if one of them is a zero */
662 /* if yes turn it into assignmnt */
663 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
664 operandLitValue (IC_LEFT (ic)) == 0.0)
669 SET_ISADDR (IC_RESULT (ic), 0);
670 SET_ISADDR (IC_RIGHT (ic), 0);
673 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
674 operandLitValue (IC_RIGHT (ic)) == 0.0)
678 IC_RIGHT (ic) = IC_LEFT (ic);
680 SET_ISADDR (IC_RIGHT (ic), 0);
681 SET_ISADDR (IC_RESULT (ic), 0);
686 /* if subtracting the the same thing then zero */
687 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
690 IC_RIGHT (ic) = operandFromLit (0);
692 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
693 IC_RESULT (ic)->isaddr = 0;
697 /* if subtraction then check if one of the operand */
698 /* is zero then depending on which operand change */
699 /* to assignment or unary minus */
700 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
701 operandLitValue (IC_RIGHT (ic)) == 0.0)
703 /* right size zero change to assignment */
705 IC_RIGHT (ic) = IC_LEFT (ic);
707 SET_ISADDR (IC_RIGHT (ic), 0);
708 SET_ISADDR (IC_RESULT (ic), 0);
711 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
712 operandLitValue (IC_LEFT (ic)) == 0.0)
714 /* left zero turn into an unary minus */
716 IC_LEFT (ic) = IC_RIGHT (ic);
717 IC_RIGHT (ic) = NULL;
721 /* if multiplication then check if either of */
722 /* them is zero then the result is zero */
723 /* if either of them is one then result is */
726 if (IS_OP_LITERAL (IC_LEFT (ic)))
729 if (operandLitValue (IC_LEFT (ic)) == 0.0)
732 IC_RIGHT (ic) = IC_LEFT (ic);
734 SET_RESULT_RIGHT (ic);
737 if (operandLitValue (IC_LEFT (ic)) == 1.0)
741 SET_RESULT_RIGHT (ic);
746 if (IS_OP_LITERAL (IC_RIGHT (ic)))
749 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
753 SET_RESULT_RIGHT (ic);
757 if (operandLitValue (IC_RIGHT (ic)) == 1.0)
760 IC_RIGHT (ic) = IC_LEFT (ic);
762 SET_RESULT_RIGHT (ic);
768 /* if division by self then 1 */
769 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
772 IC_RIGHT (ic) = operandFromLit (1);
774 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
775 IC_RESULT (ic)->isaddr = 0;
777 /* if this is a division then check if right */
778 /* is one then change it to an assignment */
779 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
780 operandLitValue (IC_RIGHT (ic)) == 1.0)
784 IC_RIGHT (ic) = IC_LEFT (ic);
786 SET_RESULT_RIGHT (ic);
790 /* if both are the same for an comparison operators */
794 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
797 IC_RIGHT (ic) = operandFromLit (1);
799 SET_RESULT_RIGHT (ic);
805 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
808 IC_RIGHT (ic) = operandFromLit (0);
810 SET_RESULT_RIGHT (ic);
814 /* if this is a cast of a literal value */
815 if (IS_OP_LITERAL (IC_RIGHT (ic)))
819 operandFromValue (valCastLiteral (operandType (IC_LEFT (ic)),
820 operandLitValue (IC_RIGHT (ic))));
822 SET_ISADDR (IC_RESULT (ic), 0);
824 /* if casting to the same */
825 if (checkType (operandType (IC_RESULT (ic)),
826 operandType (IC_RIGHT (ic))) == 1)
830 SET_ISADDR (IC_RESULT (ic), 0);
834 if (IS_OP_LITERAL (IC_LEFT (ic)))
838 (operandLitValue (IC_LEFT (ic)) == 0 ?
839 operandFromLit (1) : operandFromLit (0));
841 SET_ISADDR (IC_RESULT (ic), 0);
847 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
848 /*-----------------------------------------------------------------*/
849 /* updateSpillLocation - keeps track of register spill location */
850 /*-----------------------------------------------------------------*/
852 updateSpillLocation (iCode * ic)
857 if (POINTER_SET (ic))
863 /* for the form true_symbol := iTempNN */
864 if (ASSIGN_ITEMP_TO_SYM (ic)
865 && !SPIL_LOC (IC_RIGHT (ic)))
868 setype = getSpec (operandType (IC_RESULT (ic)));
870 if (!IC_RIGHT (ic)->noSpilLoc &&
871 !IS_VOLATILE (setype) &&
872 !IN_FARSPACE (SPEC_OCLS (setype)) &&
873 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
875 SPIL_LOC (IC_RIGHT (ic)) =
876 IC_RESULT (ic)->operand.symOperand;
879 if (ASSIGN_ITEMP_TO_ITEMP (ic) &&
880 !SPIL_LOC (IC_RIGHT (ic)) &&
881 !bitVectBitsInCommon (OP_DEFS (IC_RIGHT (ic)), OP_USES (IC_RESULT (ic))) &&
882 OP_SYMBOL (IC_RESULT (ic))->isreqv)
885 setype = getSpec (operandType (IC_RESULT (ic)));
887 if (!IC_RIGHT (ic)->noSpilLoc &&
888 !IS_VOLATILE (setype) &&
889 !IN_FARSPACE (SPEC_OCLS (setype)) &&
890 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
892 SPIL_LOC (IC_RIGHT (ic)) =
893 SPIL_LOC (IC_RESULT (ic));
897 /*-----------------------------------------------------------------*/
898 /* setUsesDef - sets the uses def bitvector for a given operand */
899 /*-----------------------------------------------------------------*/
901 setUsesDefs (operand * op, bitVect * bdefs,
902 bitVect * idefs, bitVect ** oud)
904 /* compute the definitions alive at this point */
905 bitVect *adefs = bitVectUnion (bdefs, idefs);
907 /* of these definitions find the ones that are */
908 /* for this operand */
909 adefs = bitVectIntersect (adefs, OP_DEFS (op));
911 /* these are the definitions that this operand can use */
912 op->usesDefs = adefs;
914 /* the out defs is an union */
915 *oud = bitVectUnion (*oud, adefs);
918 /*-----------------------------------------------------------------*/
919 /* unsetDefsAndUses - clear this operation for the operands */
920 /*-----------------------------------------------------------------*/
922 unsetDefsAndUses (iCode * ic)
924 if (ic->op == JUMPTABLE)
927 /* take away this definition from the def chain of the */
928 /* result & take away from use set of the operands */
931 /* turn off def set */
932 if (IS_SYMOP (IC_RESULT (ic)))
934 if (!POINTER_SET (ic))
935 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
937 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
939 /* turn off the useSet for the operands */
940 if (IS_SYMOP (IC_LEFT (ic)))
941 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
943 if (IS_SYMOP (IC_RIGHT (ic)))
944 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
947 /* must be ifx turn off the use */ if (IS_SYMOP (IC_COND (ic)))
948 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
951 /*-----------------------------------------------------------------*/
952 /* ifxOptimize - changes ifx conditions if it can */
953 /*-----------------------------------------------------------------*/
955 ifxOptimize (iCode * ic, set * cseSet,
957 eBBlock * ebb, int *change,
958 eBBlock ** ebbs, int count)
963 /* if the condition can be replaced */
967 applyToSetFTrue (cseSet, findCheaperOp, IC_COND (ic), &pdop);
975 /* if the conditional is a literal then */
976 if (IS_OP_LITERAL (IC_COND (ic)))
979 if ((operandLitValue (IC_COND (ic)) != 0.0) && IC_TRUE (ic))
982 /* change to a goto */
984 IC_LABEL (ic) = IC_TRUE (ic);
991 if (!operandLitValue (IC_COND (ic)) && IC_FALSE (ic))
994 IC_LABEL (ic) = IC_FALSE (ic);
1000 /* then kill this if condition */
1001 remiCodeFromeBBlock (ebb, ic);
1005 /* now we need to recompute the control flow */
1006 /* since the control flow has changed */
1007 /* this is very expensive but it does not happen */
1008 /* too often, if it does happen then the user pays */
1010 computeControlFlow (ebbs, count, 1);
1011 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1015 /* if there is only one successor and that successor
1016 is the same one we are conditionally going to then
1017 we can remove this conditional statement */
1018 label = (IC_TRUE (ic) ? IC_TRUE (ic) : IC_FALSE (ic));
1019 if (elementsInSet (ebb->succList) == 1 &&
1020 isinSet (ebb->succList, eBBWithEntryLabel (ebbs, label, count)))
1023 remiCodeFromeBBlock (ebb, ic);
1024 computeControlFlow (ebbs, count, 1);
1025 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1030 /* if it remains an IFX the update the use Set */
1031 OP_USES (IC_COND (ic)) = bitVectSetBit (OP_USES (IC_COND (ic)), ic->key);
1032 setUsesDefs (IC_COND (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1036 /*-----------------------------------------------------------------*/
1037 /* diCodeForSym - finds the definiting instruction for a symbol */
1038 /*-----------------------------------------------------------------*/
1039 DEFSETFUNC (diCodeForSym)
1042 V_ARG (operand *, sym);
1043 V_ARG (iCode **, dic);
1045 /* if already found */
1049 /* if not if this is the defining iCode */
1050 if (sym->key == cdp->key)
1059 /*-----------------------------------------------------------------*/
1060 /* constFold - does some constant folding */
1061 /*-----------------------------------------------------------------*/
1063 constFold (iCode * ic, set * cseSet)
1067 /* this routine will change
1073 /* deal with only + & - */
1074 if (ic->op != '+' &&
1078 /* this check is a hueristic to prevent live ranges
1079 from becoming too long */
1080 if (IS_PTR (operandType (IC_RESULT (ic))))
1083 /* check if operation with a literal */
1084 if (!IS_OP_LITERAL (IC_RIGHT (ic)))
1087 /* check if we can find a definition for the
1089 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (ic), &dic)))
1092 /* check that this is also a +/- */
1093 if (dic->op != '+' && dic->op != '-')
1096 /* with a literal */
1097 if (!IS_OP_LITERAL (IC_RIGHT (dic)))
1100 /* find the definition of the left operand
1101 of dic.then check if this defined with a
1102 get_pointer return 0 if the pointer size is
1103 less than 2 (MCS51 specific) */
1104 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (dic), &ldic)))
1107 if (POINTER_GET (ldic) && getSize (operandType (IC_LEFT (ldic))) <= 1)
1110 /* it is if the operations are the same */
1111 /* the literal parts need to be added */
1112 IC_LEFT (ic) = operandFromOperand (IC_LEFT (dic));
1113 if (ic->op == dic->op)
1114 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) +
1115 operandLitValue (IC_RIGHT (dic)));
1117 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) -
1118 operandLitValue (IC_RIGHT (dic)));
1120 if (IS_ITEMP (IC_RESULT (ic)))
1122 SPIL_LOC (IC_RESULT (ic)) = NULL;
1123 IC_RESULT (ic)->noSpilLoc = 1;
1130 /*-----------------------------------------------------------------*/
1131 /* deleteGetPointers - called when a pointer is passed as parm */
1132 /* will delete from cseSet all get pointers computed from this */
1133 /* pointer. A simple ifOperandsHave is not good enough here */
1134 /*-----------------------------------------------------------------*/
1136 deleteGetPointers (set ** cseSet, set ** pss, operand * op, eBBlock * ebb)
1138 set *compItems = NULL;
1143 if (!*cseSet && !*pss)
1146 /* first find all items computed from this operand .
1147 This done fairly simply go thru the list and find
1148 those that are computed by arthimetic with this
1150 for (cdp = setFirstItem (*cseSet); cdp; cdp = setNextItem (*cseSet))
1152 if (IS_ARITHMETIC_OP (cdp->diCode))
1154 if (isOperandEqual (IC_LEFT (cdp->diCode), op) ||
1155 isOperandEqual (IC_RIGHT (cdp->diCode), op))
1157 /* save it in our list of items */
1158 addSet (&compItems, IC_RESULT (cdp->diCode));
1160 /* also check for those computed from our computed
1161 list . This will take care of situations like
1162 iTemp1 = iTemp0 + 8;
1163 iTemp2 = iTemp1 + 8; */
1164 if (isinSetWith (compItems, (void*)IC_LEFT (cdp->diCode),
1165 (void*)isOperandEqual) ||
1166 isinSetWith (compItems, (void*)IC_RIGHT (cdp->diCode),
1167 (void*)isOperandEqual))
1169 addSet (&compItems, IC_RESULT (cdp->diCode));
1174 /* now delete all pointer gets with this op */
1175 deleteItemIf (cseSet, ifPointerGet, op);
1176 deleteItemIf (pss, ifPointerSet, op);
1178 /* set the bit vector used by dataFlow computation later */
1179 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, op->key);
1180 /* now for the computed items */
1181 for (cop = setFirstItem (compItems); cop; cop = setNextItem (compItems))
1183 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, cop->key);
1184 deleteItemIf (cseSet, ifPointerGet, cop);
1185 deleteItemIf (pss, ifPointerSet, cop);
1189 /*-----------------------------------------------------------------*/
1190 /* delGetPointerSucc - delete get pointer from inExprs of succ with */
1191 /* dfnum > supplied */
1192 /*-----------------------------------------------------------------*/
1193 DEFSETFUNC (delGetPointerSucc)
1195 eBBlock *ebp = item;
1196 V_ARG (operand *, op);
1203 if (ebp->dfnum > dfnum)
1205 deleteItemIf (&ebp->inExprs, ifPointerGet, op);
1208 return applyToSet (ebp->succList, delGetPointerSucc, op, dfnum);
1211 /*-----------------------------------------------------------------*/
1212 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1213 /*-----------------------------------------------------------------*/
1215 fixUpTypes (iCode * ic)
1217 sym_link *t1 = operandType (IC_LEFT (ic)), *t2;
1219 if (TARGET_IS_DS390)
1225 /* for pointer_gets if the types of result & left r the
1226 same then change it type of result to next */
1228 checkType (t2 = operandType (IC_RESULT (ic)), t1) == 1)
1230 setOperandType (IC_RESULT (ic), t2->next);
1234 /*-----------------------------------------------------------------*/
1235 /* cseBBlock - common subexpression elimination for basic blocks */
1236 /* this is the hackiest kludgiest routine in the whole */
1237 /* system. also the most important, since almost all */
1238 /* data flow related information is computed by it */
1239 /*-----------------------------------------------------------------*/
1241 cseBBlock (eBBlock * ebb, int computeOnly,
1242 eBBlock ** ebbs, int count)
1248 set *ptrSetSet = NULL;
1250 /* if this block is not reachable */
1254 /* set of common subexpressions */
1255 cseSet = setFromSet (ebb->inExprs);
1257 /* these will be computed by this routine */
1258 setToNull ((void **) &ebb->outDefs);
1259 setToNull ((void **) &ebb->defSet);
1260 setToNull ((void **) &ebb->usesDefs);
1261 setToNull ((void **) &ebb->ptrsSet);
1262 setToNull ((void **) &ebb->addrOf);
1263 setToNull ((void **) &ebb->ldefs);
1265 ebb->outDefs = bitVectCopy (ebb->inDefs);
1266 bitVectDefault = iCodeKey;
1267 ebb->defSet = newBitVect (iCodeKey);
1268 ebb->usesDefs = newBitVect (iCodeKey);
1270 /* for all the instructions in this block do */
1271 for (ic = ebb->sch; ic; ic = ic->next)
1281 /* if this is an assignment from true symbol
1282 to a temp then do pointer post inc/dec optimzation */
1283 if (ic->op == '=' && !POINTER_SET (ic) &&
1284 IS_PTR (operandType (IC_RESULT (ic))))
1286 ptrPostIncDecOpt (ic);
1289 /* clear the def & use chains for the operands involved */
1290 /* in this operation . since it can change due to opts */
1291 unsetDefsAndUses (ic);
1293 if (ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE)
1295 /* add to defSet of the symbol */
1296 OP_DEFS (IC_RESULT (ic)) =
1297 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1298 /* add to the definition set of this block */
1299 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1300 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1301 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1302 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1303 /* delete global variables from the cseSet
1304 since they can be modified by the function call */
1305 deleteItemIf (&cseSet, ifDefGlobal);
1306 /* delete all getpointer iCodes from cseSet, this should
1307 be done only for global arrays & pointers but at this
1308 point we don't know if globals, so to be safe do all */
1309 deleteItemIf (&cseSet, ifAnyGetPointer);
1312 /* for pcall & ipush we need to add to the useSet */
1313 if ((ic->op == PCALL ||
1317 IS_SYMOP (IC_LEFT (ic)))
1320 /* check if they can be replaced */
1324 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1326 IC_LEFT (ic) = pdop;
1328 /* the lookup could have changed it */
1329 if (IS_SYMOP (IC_LEFT (ic)))
1331 OP_USES (IC_LEFT (ic)) =
1332 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1333 setUsesDefs (IC_LEFT (ic), ebb->defSet,
1334 ebb->outDefs, &ebb->usesDefs);
1338 /* if we a sending a pointer as a parameter
1339 then kill all cse since the pointed to item
1340 might be changed in the function being called */
1341 if ((ic->op == IPUSH || ic->op == SEND) &&
1342 IS_PTR (operandType (IC_LEFT (ic))))
1344 deleteGetPointers (&cseSet, &ptrSetSet, IC_LEFT (ic), ebb);
1345 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_LEFT (ic)->key);
1346 for (i = 0; i < count; ebbs[i++]->visited = 0);
1347 applyToSet (ebb->succList, delGetPointerSucc,
1348 IC_LEFT (ic), ebb->dfnum);
1353 /* if jumptable then mark the usage */
1354 if (ic->op == JUMPTABLE)
1356 OP_USES (IC_JTCOND (ic)) =
1357 bitVectSetBit (OP_USES (IC_JTCOND (ic)), ic->key);
1358 setUsesDefs (IC_JTCOND (ic), ebb->defSet,
1359 ebb->outDefs, &ebb->usesDefs);
1366 /* do some algebraic optimizations if possible */
1368 while (constFold (ic, cseSet));
1371 if (POINTER_GET (ic) && !IS_PTR (operandType (IC_LEFT (ic))))
1373 setOperandType (IC_LEFT (ic),
1374 aggrToPtr (operandType (IC_LEFT (ic)), FALSE));
1378 if (POINTER_SET (ic) && !IS_PTR (operandType (IC_RESULT (ic))))
1380 setOperandType (IC_RESULT (ic),
1381 aggrToPtr (operandType (IC_RESULT (ic)), FALSE));
1384 /* if this is a condition statment then */
1385 /* check if the condition can be replaced */
1388 ifxOptimize (ic, cseSet, computeOnly,
1394 /* if the assignment & result is a temp */
1395 /* see if we can replace it */
1399 /* update the spill location for this */
1400 updateSpillLocation (ic);
1402 if (POINTER_SET (ic) &&
1403 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype)))
1406 applyToSetFTrue (cseSet, findCheaperOp, IC_RESULT (ic), &pdop);
1407 if (pdop && IS_ITEMP (pdop) && !computeOnly)
1408 IC_RESULT (ic) = pdop;
1412 /* do the operand lookup i.e. for both the */
1413 /* right & left operand : check the cseSet */
1414 /* to see if they have been replaced if yes */
1415 /* then replace them with those from cseSet */
1417 /* and left is a symbol */
1418 if (IS_SYMOP (IC_LEFT (ic)) &&
1419 !computeOnly && ic->op != ADDRESS_OF)
1423 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1426 if (POINTER_GET (ic))
1428 if (IS_ITEMP (pdop) || IS_OP_LITERAL (pdop))
1430 IC_LEFT (ic) = pdop;
1433 /* check if there is a pointer set
1434 for the same pointer visible if yes
1435 then change this into an assignment */
1437 if (applyToSetFTrue (cseSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic)) &&
1438 !bitVectBitValue (ebb->ptrsSet, pdop->key))
1441 IC_LEFT (ic) = NULL;
1442 IC_RIGHT (ic) = pdop;
1443 SET_ISADDR (IC_RESULT (ic), 0);
1449 IC_LEFT (ic) = pdop;
1456 if (IS_SYMOP (IC_RIGHT (ic)) && !computeOnly)
1460 applyToSetFTrue (cseSet, findCheaperOp, IC_RIGHT (ic), &pdop);
1464 IC_RIGHT (ic) = pdop;
1469 /* if left or right changed then do algebraic */
1473 while (constFold (ic, cseSet));
1476 /* if after all this it becomes a assignment to self
1477 then delete it and continue */
1478 if (ASSIGNMENT_TO_SELF (ic))
1480 remiCodeFromeBBlock (ebb, ic);
1484 /* now we will check to see if the entire */
1485 /* operation has been performed before */
1486 /* and is available */
1487 /* don't do assignments they will be killed */
1488 /* by dead code elimination if required do */
1489 /* it only if result is a temporary */
1491 if (!(POINTER_GET (ic) &&
1492 (IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1493 isOperandVolatile (IC_LEFT (ic), TRUE) ||
1494 bitVectBitValue (ebb->ndompset, IC_LEFT (ic)->key))) &&
1496 IS_ITEMP (IC_RESULT (ic)) &&
1499 applyToSet (cseSet, findPrevIc, ic, &pdic);
1500 if (pdic && checkType (operandType (IC_RESULT (pdic)),
1501 operandType (IC_RESULT (ic))) != 1)
1505 /* if found then eliminate this and add to */
1506 /* to cseSet an element containing result */
1507 /* of this with previous opcode */
1511 if (IS_ITEMP (IC_RESULT (ic)))
1514 /* replace in the remaining of this block */
1515 replaceAllSymBySym (ic->next, IC_RESULT (ic), IC_RESULT (pdic), &ebb->ndompset);
1516 /* remove this iCode from inexpressions of all
1517 its successors, it cannot be in the in expressions
1518 of any of the predecessors */
1519 for (i = 0; i < count; ebbs[i++]->visited = 0);
1520 applyToSet (ebb->succList, removeFromInExprs, ic, IC_RESULT (ic),
1521 IC_RESULT (pdic), ebb);
1523 /* if this was moved from another block */
1524 /* then replace in those blocks too */
1528 for (owner = setFirstItem (ic->movedFrom); owner;
1529 owner = setNextItem (ic->movedFrom))
1530 replaceAllSymBySym (owner->sch, IC_RESULT (ic), IC_RESULT (pdic), &owner->ndompset);
1532 pdic->movedFrom = unionSets (pdic->movedFrom, ic->movedFrom, THROW_NONE);
1535 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), pdic));
1538 /* eliminate this */
1539 remiCodeFromeBBlock (ebb, ic);
1544 if (IS_ITEMP (IC_RESULT (ic)))
1551 /* just add this as a previous expression except in */
1552 /* case of a pointer access in which case this is a */
1553 /* usage not a definition */
1554 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1556 deleteItemIf (&cseSet, ifDefSymIsX, IC_RESULT (ic));
1557 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), ic));
1563 /* if assignment to a parameter which is not
1564 mine and type is a pointer then delete
1565 pointerGets to take care of aliasing */
1566 if (ASSIGNMENT (ic) &&
1567 OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))) &&
1568 IS_PTR (operandType (IC_RESULT (ic))))
1570 deleteGetPointers (&cseSet, &ptrSetSet, IC_RIGHT (ic), ebb);
1571 for (i = 0; i < count; ebbs[i++]->visited = 0);
1572 applyToSet (ebb->succList, delGetPointerSucc, IC_RIGHT (ic), ebb->dfnum);
1573 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RIGHT (ic)->key);
1576 /* if this is a pointerget then see if we can replace
1577 this with a previously assigned pointer value */
1578 if (POINTER_GET (ic) &&
1579 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1580 isOperandVolatile (IC_LEFT (ic), TRUE)))
1583 applyToSet (ptrSetSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic));
1584 /* if we find it then locally replace all
1585 references to the result with what we assigned */
1588 replaceAllSymBySym (ic->next, IC_RESULT (ic), pdop, &ebb->ndompset);
1592 /* delete from the cseSet anything that has */
1593 /* operands matching the result of this */
1594 /* except in case of pointer access */
1595 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1597 deleteItemIf (&cseSet, ifOperandsHave, IC_RESULT (ic));
1598 /* delete any previous definitions */
1599 ebb->defSet = bitVectCplAnd (ebb->defSet, OP_DEFS (IC_RESULT (ic)));
1603 /* add the left & right to the defUse set */
1604 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)))
1606 OP_USES (IC_LEFT (ic)) =
1607 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1608 setUsesDefs (IC_LEFT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1612 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)))
1614 OP_USES (IC_RIGHT (ic)) =
1615 bitVectSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1616 setUsesDefs (IC_RIGHT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1620 /* for the result it is special case, put the result */
1621 /* in the defuseSet if it a pointer or array access */
1622 if (POINTER_SET (defic))
1624 OP_USES (IC_RESULT (ic)) =
1625 bitVectSetBit (OP_USES (IC_RESULT (ic)), ic->key);
1626 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1627 deleteItemIf (&cseSet, ifPointerGet, IC_RESULT (ic));
1628 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RESULT (ic)->key);
1629 /* delete from inexpressions of all successors which
1630 have dfNum > than this block */
1631 for (i = 0; i < count; ebbs[i++]->visited = 0);
1632 applyToSet (ebb->succList, delGetPointerSucc, IC_RESULT (ic), ebb->dfnum);
1634 /* delete from cseSet all other pointer sets
1636 deleteItemIf (&ptrSetSet, ifPointerSet, IC_RESULT (ic));
1637 /* add to the local pointerset set */
1638 addSetHead (&ptrSetSet, newCseDef (IC_RESULT (ic), ic));
1641 /* add the result to defintion set */ if (IC_RESULT (ic))
1643 OP_DEFS (IC_RESULT (ic)) =
1644 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1645 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1646 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1647 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1651 /* if this is an addressof instruction then */
1652 /* put the symbol in the address of list & */
1653 /* delete it from the cseSet */
1654 if (defic->op == ADDRESS_OF)
1656 addSetHead (&ebb->addrOf, IC_LEFT (ic));
1657 deleteItemIf (&cseSet, ifDefSymIsX, IC_LEFT (ic));
1661 setToNull ((void **) &ebb->outExprs);
1662 ebb->outExprs = cseSet;
1663 ebb->outDefs = bitVectUnion (ebb->outDefs, ebb->defSet);
1664 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet, ebb->inPtrsSet);
1668 /*-----------------------------------------------------------------*/
1669 /* cseAllBlocks - will sequentially go thru & do cse for all blocks */
1670 /*-----------------------------------------------------------------*/
1672 cseAllBlocks (eBBlock ** ebbs, int count)
1677 /* if optimization turned off */
1679 for (i = 0; i < count; i++)
1680 change += cseBBlock (ebbs[i], FALSE, ebbs, count);