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
276 #if SomeOneUnderStandsThis
277 /* This causes the bug:
279 void test (unsigned u) {
280 // the following cast is ignored
281 for (; (int) u >= 0;)
286 where casts are ignored */
288 if (!POINTER_SET (cdp->diCode) &&
289 IS_ITEMP (IC_RESULT (cdp->diCode)) &&
290 IS_ITEMP (IC_RIGHT (cdp->diCode)) &&
291 !OP_SYMBOL (IC_RIGHT (cdp->diCode))->isind &&
292 ((!SPIL_LOC (IC_RIGHT (cdp->diCode)) &&
293 SPIL_LOC (IC_RESULT (cdp->diCode))) ||
294 (SPIL_LOC (IC_RESULT (cdp->diCode)) &&
295 SPIL_LOC (IC_RESULT (cdp->diCode)) ==
296 SPIL_LOC (IC_RIGHT (cdp->diCode)))))
297 *opp = IC_RESULT (cdp->diCode);
299 *opp = IC_RIGHT (cdp->diCode);
304 *opp = IC_RESULT (cdp->diCode);
307 /* if this is an assign to a temp. then check
308 if the right side is this then return this */
309 if (IS_TRUE_SYMOP (cop) &&
310 cdp->diCode->op == '=' &&
311 !POINTER_SET (cdp->diCode) &&
312 cop->key == IC_RIGHT (cdp->diCode)->key &&
313 !isGlobalInNearSpace (IC_RIGHT (cdp->diCode)) &&
314 IS_ITEMP (IC_RESULT (cdp->diCode)))
315 *opp = IC_RESULT (cdp->diCode);
320 if ((isGlobalInNearSpace (cop) &&
321 !isOperandLiteral (*opp)) ||
322 isOperandVolatile (*opp, FALSE)
329 if (cop->key == (*opp)->key)
335 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP (cop))
337 *opp = operandFromOperand (*opp);
338 (*opp)->isaddr = cop->isaddr;
348 /*-----------------------------------------------------------------*/
349 /* findPointerSet - finds the right side of a pointer set op */
350 /*-----------------------------------------------------------------*/
351 DEFSETFUNC (findPointerSet)
354 V_ARG (operand *, op);
355 V_ARG (operand **, opp);
356 V_ARG (operand *, rop);
358 if (POINTER_SET (cdp->diCode) &&
359 IC_RESULT (cdp->diCode)->key == op->key &&
360 !isOperandVolatile (IC_RESULT (cdp->diCode), TRUE) &&
361 !isOperandVolatile (IC_RIGHT (cdp->diCode), TRUE) &&
362 getSize (operandType (IC_RIGHT (cdp->diCode))) ==
363 getSize (operandType (rop)))
365 *opp = IC_RIGHT (cdp->diCode);
372 /*-----------------------------------------------------------------*/
373 /* findPrevIc - cseBBlock support function will return the iCode */
374 /* which matches the current one */
375 /*-----------------------------------------------------------------*/
376 DEFSETFUNC (findPrevIc)
380 V_ARG (iCode **, icp);
382 /* if already found */
386 /* if the iCodes are the same */
387 if (isiCodeEqual (ic, cdp->diCode) &&
388 isOperandEqual (cdp->sym, IC_RESULT (cdp->diCode)))
394 /* if iCodes are not the same */
395 /* see the operands maybe interchanged */
396 if (ic->op == cdp->diCode->op &&
397 (ic->op == '+' || ic->op == '*') &&
398 isOperandEqual (IC_LEFT (ic), IC_RIGHT (cdp->diCode)) &&
399 isOperandEqual (IC_RIGHT (ic), IC_LEFT (cdp->diCode)))
408 /*-----------------------------------------------------------------*/
409 /* ifDefGlobal - if definition is global */
410 /*-----------------------------------------------------------------*/
411 DEFSETFUNC (ifDefGlobal)
415 return (isOperandGlobal (cdp->sym));
418 /*-----------------------------------------------------------------*/
419 /* ifAnyGetPointer - if get pointer icode */
420 /*-----------------------------------------------------------------*/
421 DEFSETFUNC (ifAnyGetPointer)
425 if (cdp->diCode && POINTER_GET (cdp->diCode))
430 /*-----------------------------------------------------------------*/
431 /* ifOperandsHave - if any of the operand are the same as this */
432 /*-----------------------------------------------------------------*/
433 DEFSETFUNC (ifOperandsHave)
436 V_ARG (operand *, op);
439 if (IC_LEFT (cdp->diCode) &&
440 IS_SYMOP (IC_LEFT (cdp->diCode)) &&
441 IC_LEFT (cdp->diCode)->key == op->key)
444 if (IC_RIGHT (cdp->diCode) &&
445 IS_SYMOP (IC_RIGHT (cdp->diCode)) &&
446 IC_RIGHT (cdp->diCode)->key == op->key)
449 /* or if any of the operands are volatile */
450 if (IC_LEFT (cdp->diCode) &&
451 IS_OP_VOLATILE (IC_LEFT (cdp->diCode)))
454 if (IC_RIGHT (cdp->diCode) &&
455 IS_OP_VOLATILE (IC_RIGHT (cdp->diCode)))
459 if (IC_RESULT (cdp->diCode) &&
460 IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
466 /*-----------------------------------------------------------------*/
467 /* ifDefSymIs - if a definition is found in the set */
468 /*-----------------------------------------------------------------*/
470 ifDefSymIs (set * cseSet, operand * sym)
475 if (!sym || !IS_SYMOP (sym))
477 for (sl = cseSet; sl; sl = sl->next)
480 if (loop->sym->key == sym->key)
487 /*-----------------------------------------------------------------*/
488 /* ifDefSymIsX - will return 1 if the symbols match */
489 /*-----------------------------------------------------------------*/
490 DEFSETFUNC (ifDefSymIsX)
493 V_ARG (operand *, op);
496 return cdp->sym->key == op->key;
498 return (isOperandEqual (cdp->sym, op));
503 /*-----------------------------------------------------------------*/
504 /* ifDiCodeIs - returns truw if diCode is same */
505 /*-----------------------------------------------------------------*/
507 ifDiCodeIs (set * cseSet, iCode * ic)
515 for (sl = cseSet; sl; sl = sl->next)
518 if (loop->diCode == ic)
525 /*-----------------------------------------------------------------*/
526 /* ifPointerGet - returns true if the icode is pointer get sym */
527 /*-----------------------------------------------------------------*/
528 DEFSETFUNC (ifPointerGet)
531 V_ARG (operand *, op);
532 iCode *dic = cdp->diCode;
533 operand *left = IC_LEFT (cdp->diCode);
535 if (POINTER_GET (dic) && left->key == op->key)
541 /*-----------------------------------------------------------------*/
542 /* ifPointerSet - returns true if the icode is pointer set sym */
543 /*-----------------------------------------------------------------*/
544 DEFSETFUNC (ifPointerSet)
547 V_ARG (operand *, op);
549 if (POINTER_SET (cdp->diCode) &&
550 IC_RESULT (cdp->diCode)->key == op->key)
556 /*-----------------------------------------------------------------*/
557 /* ifDiCodeIsX - will return 1 if the symbols match */
558 /*-----------------------------------------------------------------*/
559 DEFSETFUNC (ifDiCodeIsX)
564 return cdp->diCode == ic;
568 /*-----------------------------------------------------------------*/
569 /* algebraicOpts - does some algebraic optimizations */
570 /*-----------------------------------------------------------------*/
572 algebraicOpts (iCode * ic)
574 /* we don't deal with the following iCodes
585 /* if both operands present & ! IFX */
586 /* then if they are both literal we */
587 /* perform the operation right now */
588 if (IC_RESULT (ic) &&
591 IS_OP_LITERAL (IC_LEFT (ic)) &&
592 IS_OP_LITERAL (IC_RIGHT (ic)))
595 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
598 operandType (IC_RESULT (ic)));
601 SET_RESULT_RIGHT (ic);
605 /* if not ifx & only one operand present */
606 if (IC_RESULT (ic) &&
608 IS_OP_LITERAL (IC_LEFT (ic)) &&
612 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
615 operandType (IC_RESULT (ic)));
618 SET_RESULT_RIGHT (ic);
623 /* a special case : or in short a kludgy solution will think
624 about a better solution over a glass of wine someday */
625 if (ic->op == GET_VALUE_AT_ADDRESS)
628 if (IS_ITEMP (IC_RESULT (ic)) &&
629 IS_TRUE_SYMOP (IC_LEFT (ic)))
633 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
634 IC_RIGHT (ic)->isaddr = 0;
636 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
637 IC_RESULT (ic)->isaddr = 0;
638 setOperandType (IC_RESULT (ic), operandType (IC_RIGHT (ic)));
642 if (IS_ITEMP (IC_LEFT (ic)) &&
643 IS_ITEMP (IC_RESULT (ic)) &&
644 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
645 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
646 !IC_LEFT (ic)->isaddr)
649 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
650 IC_RIGHT (ic)->isaddr = 0;
651 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
652 IC_RESULT (ic)->isaddr = 0;
660 /* depending on the operation */
664 /* if adding the same thing change to left shift by 1 */
665 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key &&
666 !IS_FLOAT (operandType (IC_RESULT (ic))))
669 IC_RIGHT (ic) = operandFromLit (1);
672 /* if addition then check if one of them is a zero */
673 /* if yes turn it into assignmnt */
674 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
675 operandLitValue (IC_LEFT (ic)) == 0.0)
680 SET_ISADDR (IC_RESULT (ic), 0);
681 SET_ISADDR (IC_RIGHT (ic), 0);
684 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
685 operandLitValue (IC_RIGHT (ic)) == 0.0)
689 IC_RIGHT (ic) = IC_LEFT (ic);
691 SET_ISADDR (IC_RIGHT (ic), 0);
692 SET_ISADDR (IC_RESULT (ic), 0);
697 /* if subtracting the the same thing then zero */
698 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
701 IC_RIGHT (ic) = operandFromLit (0);
703 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
704 IC_RESULT (ic)->isaddr = 0;
708 /* if subtraction then check if one of the operand */
709 /* is zero then depending on which operand change */
710 /* to assignment or unary minus */
711 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
712 operandLitValue (IC_RIGHT (ic)) == 0.0)
714 /* right size zero change to assignment */
716 IC_RIGHT (ic) = IC_LEFT (ic);
718 SET_ISADDR (IC_RIGHT (ic), 0);
719 SET_ISADDR (IC_RESULT (ic), 0);
722 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
723 operandLitValue (IC_LEFT (ic)) == 0.0)
725 /* left zero turn into an unary minus */
727 IC_LEFT (ic) = IC_RIGHT (ic);
728 IC_RIGHT (ic) = NULL;
732 /* if multiplication then check if either of */
733 /* them is zero then the result is zero */
734 /* if either of them is one then result is */
737 if (IS_OP_LITERAL (IC_LEFT (ic)))
740 if (operandLitValue (IC_LEFT (ic)) == 0.0)
743 IC_RIGHT (ic) = IC_LEFT (ic);
745 SET_RESULT_RIGHT (ic);
748 if (operandLitValue (IC_LEFT (ic)) == 1.0)
752 SET_RESULT_RIGHT (ic);
757 if (IS_OP_LITERAL (IC_RIGHT (ic)))
760 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
764 SET_RESULT_RIGHT (ic);
768 if (operandLitValue (IC_RIGHT (ic)) == 1.0)
771 IC_RIGHT (ic) = IC_LEFT (ic);
773 SET_RESULT_RIGHT (ic);
779 /* if division by self then 1 */
780 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
783 IC_RIGHT (ic) = operandFromLit (1);
785 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
786 IC_RESULT (ic)->isaddr = 0;
788 /* if this is a division then check if right */
789 /* is one then change it to an assignment */
790 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
791 operandLitValue (IC_RIGHT (ic)) == 1.0)
795 IC_RIGHT (ic) = IC_LEFT (ic);
797 SET_RESULT_RIGHT (ic);
801 /* if both are the same for an comparison operators */
805 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
808 IC_RIGHT (ic) = operandFromLit (1);
810 SET_RESULT_RIGHT (ic);
816 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
819 IC_RIGHT (ic) = operandFromLit (0);
821 SET_RESULT_RIGHT (ic);
825 /* if this is a cast of a literal value */
826 if (IS_OP_LITERAL (IC_RIGHT (ic)))
830 operandFromValue (valCastLiteral (operandType (IC_LEFT (ic)),
831 operandLitValue (IC_RIGHT (ic))));
833 SET_ISADDR (IC_RESULT (ic), 0);
835 /* if casting to the same */
836 if (checkType (operandType (IC_RESULT (ic)),
837 operandType (IC_RIGHT (ic))) == 1)
841 SET_ISADDR (IC_RESULT (ic), 0);
845 if (IS_OP_LITERAL (IC_LEFT (ic)))
849 (operandLitValue (IC_LEFT (ic)) == 0 ?
850 operandFromLit (1) : operandFromLit (0));
852 SET_ISADDR (IC_RESULT (ic), 0);
858 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
859 /*-----------------------------------------------------------------*/
860 /* updateSpillLocation - keeps track of register spill location */
861 /*-----------------------------------------------------------------*/
863 updateSpillLocation (iCode * ic)
868 if (POINTER_SET (ic))
874 /* for the form true_symbol := iTempNN */
875 if (ASSIGN_ITEMP_TO_SYM (ic)
876 && !SPIL_LOC (IC_RIGHT (ic)))
879 setype = getSpec (operandType (IC_RESULT (ic)));
881 if (!IC_RIGHT (ic)->noSpilLoc &&
882 !IS_VOLATILE (setype) &&
883 !IN_FARSPACE (SPEC_OCLS (setype)) &&
884 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
886 SPIL_LOC (IC_RIGHT (ic)) =
887 IC_RESULT (ic)->operand.symOperand;
890 if (ASSIGN_ITEMP_TO_ITEMP (ic) &&
891 !SPIL_LOC (IC_RIGHT (ic)) &&
892 !bitVectBitsInCommon (OP_DEFS (IC_RIGHT (ic)), OP_USES (IC_RESULT (ic))) &&
893 OP_SYMBOL (IC_RESULT (ic))->isreqv)
896 setype = getSpec (operandType (IC_RESULT (ic)));
898 if (!IC_RIGHT (ic)->noSpilLoc &&
899 !IS_VOLATILE (setype) &&
900 !IN_FARSPACE (SPEC_OCLS (setype)) &&
901 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
903 SPIL_LOC (IC_RIGHT (ic)) =
904 SPIL_LOC (IC_RESULT (ic));
908 /*-----------------------------------------------------------------*/
909 /* setUsesDef - sets the uses def bitvector for a given operand */
910 /*-----------------------------------------------------------------*/
912 setUsesDefs (operand * op, bitVect * bdefs,
913 bitVect * idefs, bitVect ** oud)
915 /* compute the definitions alive at this point */
916 bitVect *adefs = bitVectUnion (bdefs, idefs);
918 /* of these definitions find the ones that are */
919 /* for this operand */
920 adefs = bitVectIntersect (adefs, OP_DEFS (op));
922 /* these are the definitions that this operand can use */
923 op->usesDefs = adefs;
925 /* the out defs is an union */
926 *oud = bitVectUnion (*oud, adefs);
929 /*-----------------------------------------------------------------*/
930 /* unsetDefsAndUses - clear this operation for the operands */
931 /*-----------------------------------------------------------------*/
933 unsetDefsAndUses (iCode * ic)
935 if (ic->op == JUMPTABLE)
938 /* take away this definition from the def chain of the */
939 /* result & take away from use set of the operands */
942 /* turn off def set */
943 if (IS_SYMOP (IC_RESULT (ic)))
945 if (!POINTER_SET (ic))
946 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
948 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
950 /* turn off the useSet for the operands */
951 if (IS_SYMOP (IC_LEFT (ic)))
952 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
954 if (IS_SYMOP (IC_RIGHT (ic)))
955 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
958 /* must be ifx turn off the use */ if (IS_SYMOP (IC_COND (ic)))
959 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
962 /*-----------------------------------------------------------------*/
963 /* ifxOptimize - changes ifx conditions if it can */
964 /*-----------------------------------------------------------------*/
966 ifxOptimize (iCode * ic, set * cseSet,
968 eBBlock * ebb, int *change,
969 eBBlock ** ebbs, int count)
974 /* if the condition can be replaced */
978 applyToSetFTrue (cseSet, findCheaperOp, IC_COND (ic), &pdop);
986 /* if the conditional is a literal then */
987 if (IS_OP_LITERAL (IC_COND (ic)))
990 if ((operandLitValue (IC_COND (ic)) != 0.0) && IC_TRUE (ic))
993 /* change to a goto */
995 IC_LABEL (ic) = IC_TRUE (ic);
1002 if (!operandLitValue (IC_COND (ic)) && IC_FALSE (ic))
1005 IC_LABEL (ic) = IC_FALSE (ic);
1011 /* then kill this if condition */
1012 remiCodeFromeBBlock (ebb, ic);
1016 /* now we need to recompute the control flow */
1017 /* since the control flow has changed */
1018 /* this is very expensive but it does not happen */
1019 /* too often, if it does happen then the user pays */
1021 computeControlFlow (ebbs, count, 1);
1022 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1026 /* if there is only one successor and that successor
1027 is the same one we are conditionally going to then
1028 we can remove this conditional statement */
1029 label = (IC_TRUE (ic) ? IC_TRUE (ic) : IC_FALSE (ic));
1030 if (elementsInSet (ebb->succList) == 1 &&
1031 isinSet (ebb->succList, eBBWithEntryLabel (ebbs, label, count)))
1034 remiCodeFromeBBlock (ebb, ic);
1035 computeControlFlow (ebbs, count, 1);
1036 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1041 /* if it remains an IFX the update the use Set */
1042 OP_USES (IC_COND (ic)) = bitVectSetBit (OP_USES (IC_COND (ic)), ic->key);
1043 setUsesDefs (IC_COND (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1047 /*-----------------------------------------------------------------*/
1048 /* diCodeForSym - finds the definiting instruction for a symbol */
1049 /*-----------------------------------------------------------------*/
1050 DEFSETFUNC (diCodeForSym)
1053 V_ARG (operand *, sym);
1054 V_ARG (iCode **, dic);
1056 /* if already found */
1060 /* if not if this is the defining iCode */
1061 if (sym->key == cdp->key)
1070 /*-----------------------------------------------------------------*/
1071 /* constFold - does some constant folding */
1072 /*-----------------------------------------------------------------*/
1074 constFold (iCode * ic, set * cseSet)
1078 /* this routine will change
1084 /* deal with only + & - */
1085 if (ic->op != '+' &&
1089 /* this check is a hueristic to prevent live ranges
1090 from becoming too long */
1091 if (IS_PTR (operandType (IC_RESULT (ic))))
1094 /* check if operation with a literal */
1095 if (!IS_OP_LITERAL (IC_RIGHT (ic)))
1098 /* check if we can find a definition for the
1100 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (ic), &dic)))
1103 /* check that this is also a +/- */
1104 if (dic->op != '+' && dic->op != '-')
1107 /* with a literal */
1108 if (!IS_OP_LITERAL (IC_RIGHT (dic)))
1111 /* find the definition of the left operand
1112 of dic.then check if this defined with a
1113 get_pointer return 0 if the pointer size is
1114 less than 2 (MCS51 specific) */
1115 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (dic), &ldic)))
1118 if (POINTER_GET (ldic) && getSize (operandType (IC_LEFT (ldic))) <= 1)
1121 /* it is if the operations are the same */
1122 /* the literal parts need to be added */
1123 IC_LEFT (ic) = operandFromOperand (IC_LEFT (dic));
1124 if (ic->op == dic->op)
1125 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) +
1126 operandLitValue (IC_RIGHT (dic)));
1128 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) -
1129 operandLitValue (IC_RIGHT (dic)));
1131 if (IS_ITEMP (IC_RESULT (ic)))
1133 SPIL_LOC (IC_RESULT (ic)) = NULL;
1134 IC_RESULT (ic)->noSpilLoc = 1;
1141 /*-----------------------------------------------------------------*/
1142 /* deleteGetPointers - called when a pointer is passed as parm */
1143 /* will delete from cseSet all get pointers computed from this */
1144 /* pointer. A simple ifOperandsHave is not good enough here */
1145 /*-----------------------------------------------------------------*/
1147 deleteGetPointers (set ** cseSet, set ** pss, operand * op, eBBlock * ebb)
1149 set *compItems = NULL;
1154 if (!*cseSet && !*pss)
1157 /* first find all items computed from this operand .
1158 This done fairly simply go thru the list and find
1159 those that are computed by arthimetic with this
1161 for (cdp = setFirstItem (*cseSet); cdp; cdp = setNextItem (*cseSet))
1163 if (IS_ARITHMETIC_OP (cdp->diCode))
1165 if (isOperandEqual (IC_LEFT (cdp->diCode), op) ||
1166 isOperandEqual (IC_RIGHT (cdp->diCode), op))
1168 /* save it in our list of items */
1169 addSet (&compItems, IC_RESULT (cdp->diCode));
1171 /* also check for those computed from our computed
1172 list . This will take care of situations like
1173 iTemp1 = iTemp0 + 8;
1174 iTemp2 = iTemp1 + 8; */
1175 if (isinSetWith (compItems, (void*)IC_LEFT (cdp->diCode),
1176 (void*)isOperandEqual) ||
1177 isinSetWith (compItems, (void*)IC_RIGHT (cdp->diCode),
1178 (void*)isOperandEqual))
1180 addSet (&compItems, IC_RESULT (cdp->diCode));
1185 /* now delete all pointer gets with this op */
1186 deleteItemIf (cseSet, ifPointerGet, op);
1187 deleteItemIf (pss, ifPointerSet, op);
1189 /* set the bit vector used by dataFlow computation later */
1190 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, op->key);
1191 /* now for the computed items */
1192 for (cop = setFirstItem (compItems); cop; cop = setNextItem (compItems))
1194 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, cop->key);
1195 deleteItemIf (cseSet, ifPointerGet, cop);
1196 deleteItemIf (pss, ifPointerSet, cop);
1200 /*-----------------------------------------------------------------*/
1201 /* delGetPointerSucc - delete get pointer from inExprs of succ with */
1202 /* dfnum > supplied */
1203 /*-----------------------------------------------------------------*/
1204 DEFSETFUNC (delGetPointerSucc)
1206 eBBlock *ebp = item;
1207 V_ARG (operand *, op);
1214 if (ebp->dfnum > dfnum)
1216 deleteItemIf (&ebp->inExprs, ifPointerGet, op);
1219 return applyToSet (ebp->succList, delGetPointerSucc, op, dfnum);
1222 /*-----------------------------------------------------------------*/
1223 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1224 /*-----------------------------------------------------------------*/
1226 fixUpTypes (iCode * ic)
1228 sym_link *t1 = operandType (IC_LEFT (ic)), *t2;
1230 if (TARGET_IS_DS390)
1236 /* for pointer_gets if the types of result & left r the
1237 same then change it type of result to next */
1239 checkType (t2 = operandType (IC_RESULT (ic)), t1) == 1)
1241 setOperandType (IC_RESULT (ic), t2->next);
1245 /*-----------------------------------------------------------------*/
1246 /* cseBBlock - common subexpression elimination for basic blocks */
1247 /* this is the hackiest kludgiest routine in the whole */
1248 /* system. also the most important, since almost all */
1249 /* data flow related information is computed by it */
1250 /*-----------------------------------------------------------------*/
1252 cseBBlock (eBBlock * ebb, int computeOnly,
1253 eBBlock ** ebbs, int count)
1259 set *ptrSetSet = NULL;
1261 /* if this block is not reachable */
1265 /* set of common subexpressions */
1266 cseSet = setFromSet (ebb->inExprs);
1268 /* these will be computed by this routine */
1269 setToNull ((void **) &ebb->outDefs);
1270 setToNull ((void **) &ebb->defSet);
1271 setToNull ((void **) &ebb->usesDefs);
1272 setToNull ((void **) &ebb->ptrsSet);
1273 setToNull ((void **) &ebb->addrOf);
1274 setToNull ((void **) &ebb->ldefs);
1276 ebb->outDefs = bitVectCopy (ebb->inDefs);
1277 bitVectDefault = iCodeKey;
1278 ebb->defSet = newBitVect (iCodeKey);
1279 ebb->usesDefs = newBitVect (iCodeKey);
1281 /* for all the instructions in this block do */
1282 for (ic = ebb->sch; ic; ic = ic->next)
1292 /* if this is an assignment from true symbol
1293 to a temp then do pointer post inc/dec optimzation */
1294 if (ic->op == '=' && !POINTER_SET (ic) &&
1295 IS_PTR (operandType (IC_RESULT (ic))))
1297 ptrPostIncDecOpt (ic);
1300 /* clear the def & use chains for the operands involved */
1301 /* in this operation . since it can change due to opts */
1302 unsetDefsAndUses (ic);
1304 if (ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE)
1306 /* add to defSet of the symbol */
1307 OP_DEFS (IC_RESULT (ic)) =
1308 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1309 /* add to the definition set of this block */
1310 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1311 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1312 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1313 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1314 /* delete global variables from the cseSet
1315 since they can be modified by the function call */
1316 deleteItemIf (&cseSet, ifDefGlobal);
1317 /* delete all getpointer iCodes from cseSet, this should
1318 be done only for global arrays & pointers but at this
1319 point we don't know if globals, so to be safe do all */
1320 deleteItemIf (&cseSet, ifAnyGetPointer);
1323 /* for pcall & ipush we need to add to the useSet */
1324 if ((ic->op == PCALL ||
1328 IS_SYMOP (IC_LEFT (ic)))
1331 /* check if they can be replaced */
1335 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1337 IC_LEFT (ic) = pdop;
1339 /* the lookup could have changed it */
1340 if (IS_SYMOP (IC_LEFT (ic)))
1342 OP_USES (IC_LEFT (ic)) =
1343 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1344 setUsesDefs (IC_LEFT (ic), ebb->defSet,
1345 ebb->outDefs, &ebb->usesDefs);
1349 /* if we a sending a pointer as a parameter
1350 then kill all cse since the pointed to item
1351 might be changed in the function being called */
1352 if ((ic->op == IPUSH || ic->op == SEND) &&
1353 IS_PTR (operandType (IC_LEFT (ic))))
1355 deleteGetPointers (&cseSet, &ptrSetSet, IC_LEFT (ic), ebb);
1356 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_LEFT (ic)->key);
1357 for (i = 0; i < count; ebbs[i++]->visited = 0);
1358 applyToSet (ebb->succList, delGetPointerSucc,
1359 IC_LEFT (ic), ebb->dfnum);
1364 /* if jumptable then mark the usage */
1365 if (ic->op == JUMPTABLE)
1367 OP_USES (IC_JTCOND (ic)) =
1368 bitVectSetBit (OP_USES (IC_JTCOND (ic)), ic->key);
1369 setUsesDefs (IC_JTCOND (ic), ebb->defSet,
1370 ebb->outDefs, &ebb->usesDefs);
1377 /* do some algebraic optimizations if possible */
1379 while (constFold (ic, cseSet));
1382 if (POINTER_GET (ic) && !IS_PTR (operandType (IC_LEFT (ic))))
1384 setOperandType (IC_LEFT (ic),
1385 aggrToPtr (operandType (IC_LEFT (ic)), FALSE));
1389 if (POINTER_SET (ic) && !IS_PTR (operandType (IC_RESULT (ic))))
1391 setOperandType (IC_RESULT (ic),
1392 aggrToPtr (operandType (IC_RESULT (ic)), FALSE));
1395 /* if this is a condition statment then */
1396 /* check if the condition can be replaced */
1399 ifxOptimize (ic, cseSet, computeOnly,
1405 /* if the assignment & result is a temp */
1406 /* see if we can replace it */
1410 /* update the spill location for this */
1411 updateSpillLocation (ic);
1413 if (POINTER_SET (ic) &&
1414 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype)))
1417 applyToSetFTrue (cseSet, findCheaperOp, IC_RESULT (ic), &pdop);
1418 if (pdop && IS_ITEMP (pdop) && !computeOnly)
1419 IC_RESULT (ic) = pdop;
1423 /* do the operand lookup i.e. for both the */
1424 /* right & left operand : check the cseSet */
1425 /* to see if they have been replaced if yes */
1426 /* then replace them with those from cseSet */
1428 /* and left is a symbol */
1429 if (IS_SYMOP (IC_LEFT (ic)) &&
1430 !computeOnly && ic->op != ADDRESS_OF)
1434 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1437 if (POINTER_GET (ic))
1439 if (IS_ITEMP (pdop) || IS_OP_LITERAL (pdop))
1441 IC_LEFT (ic) = pdop;
1444 /* check if there is a pointer set
1445 for the same pointer visible if yes
1446 then change this into an assignment */
1448 if (applyToSetFTrue (cseSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic)) &&
1449 !bitVectBitValue (ebb->ptrsSet, pdop->key))
1452 IC_LEFT (ic) = NULL;
1453 IC_RIGHT (ic) = pdop;
1454 SET_ISADDR (IC_RESULT (ic), 0);
1460 IC_LEFT (ic) = pdop;
1467 if (IS_SYMOP (IC_RIGHT (ic)) && !computeOnly)
1471 applyToSetFTrue (cseSet, findCheaperOp, IC_RIGHT (ic), &pdop);
1475 IC_RIGHT (ic) = pdop;
1480 /* if left or right changed then do algebraic */
1484 while (constFold (ic, cseSet));
1487 /* if after all this it becomes a assignment to self
1488 then delete it and continue */
1489 if (ASSIGNMENT_TO_SELF (ic))
1491 remiCodeFromeBBlock (ebb, ic);
1495 /* now we will check to see if the entire */
1496 /* operation has been performed before */
1497 /* and is available */
1498 /* don't do assignments they will be killed */
1499 /* by dead code elimination if required do */
1500 /* it only if result is a temporary */
1502 if (!(POINTER_GET (ic) &&
1503 (IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1504 isOperandVolatile (IC_LEFT (ic), TRUE) ||
1505 bitVectBitValue (ebb->ndompset, IC_LEFT (ic)->key))) &&
1507 IS_ITEMP (IC_RESULT (ic)) &&
1510 applyToSet (cseSet, findPrevIc, ic, &pdic);
1511 if (pdic && checkType (operandType (IC_RESULT (pdic)),
1512 operandType (IC_RESULT (ic))) != 1)
1516 /* if found then eliminate this and add to */
1517 /* to cseSet an element containing result */
1518 /* of this with previous opcode */
1522 if (IS_ITEMP (IC_RESULT (ic)))
1525 /* replace in the remaining of this block */
1526 replaceAllSymBySym (ic->next, IC_RESULT (ic), IC_RESULT (pdic), &ebb->ndompset);
1527 /* remove this iCode from inexpressions of all
1528 its successors, it cannot be in the in expressions
1529 of any of the predecessors */
1530 for (i = 0; i < count; ebbs[i++]->visited = 0);
1531 applyToSet (ebb->succList, removeFromInExprs, ic, IC_RESULT (ic),
1532 IC_RESULT (pdic), ebb);
1534 /* if this was moved from another block */
1535 /* then replace in those blocks too */
1539 for (owner = setFirstItem (ic->movedFrom); owner;
1540 owner = setNextItem (ic->movedFrom))
1541 replaceAllSymBySym (owner->sch, IC_RESULT (ic), IC_RESULT (pdic), &owner->ndompset);
1543 pdic->movedFrom = unionSets (pdic->movedFrom, ic->movedFrom, THROW_NONE);
1546 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), pdic));
1549 /* eliminate this */
1550 remiCodeFromeBBlock (ebb, ic);
1555 if (IS_ITEMP (IC_RESULT (ic)))
1562 /* just add this as a previous expression except in */
1563 /* case of a pointer access in which case this is a */
1564 /* usage not a definition */
1565 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1567 deleteItemIf (&cseSet, ifDefSymIsX, IC_RESULT (ic));
1568 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), ic));
1574 /* if assignment to a parameter which is not
1575 mine and type is a pointer then delete
1576 pointerGets to take care of aliasing */
1577 if (ASSIGNMENT (ic) &&
1578 OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))) &&
1579 IS_PTR (operandType (IC_RESULT (ic))))
1581 deleteGetPointers (&cseSet, &ptrSetSet, IC_RIGHT (ic), ebb);
1582 for (i = 0; i < count; ebbs[i++]->visited = 0);
1583 applyToSet (ebb->succList, delGetPointerSucc, IC_RIGHT (ic), ebb->dfnum);
1584 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RIGHT (ic)->key);
1587 /* if this is a pointerget then see if we can replace
1588 this with a previously assigned pointer value */
1589 if (POINTER_GET (ic) &&
1590 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1591 isOperandVolatile (IC_LEFT (ic), TRUE)))
1594 applyToSet (ptrSetSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic));
1595 /* if we find it then locally replace all
1596 references to the result with what we assigned */
1599 replaceAllSymBySym (ic->next, IC_RESULT (ic), pdop, &ebb->ndompset);
1603 /* delete from the cseSet anything that has */
1604 /* operands matching the result of this */
1605 /* except in case of pointer access */
1606 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1608 deleteItemIf (&cseSet, ifOperandsHave, IC_RESULT (ic));
1609 /* delete any previous definitions */
1610 ebb->defSet = bitVectCplAnd (ebb->defSet, OP_DEFS (IC_RESULT (ic)));
1614 /* add the left & right to the defUse set */
1615 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)))
1617 OP_USES (IC_LEFT (ic)) =
1618 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1619 setUsesDefs (IC_LEFT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1623 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)))
1625 OP_USES (IC_RIGHT (ic)) =
1626 bitVectSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1627 setUsesDefs (IC_RIGHT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1631 /* for the result it is special case, put the result */
1632 /* in the defuseSet if it a pointer or array access */
1633 if (POINTER_SET (defic))
1635 OP_USES (IC_RESULT (ic)) =
1636 bitVectSetBit (OP_USES (IC_RESULT (ic)), ic->key);
1637 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1638 deleteItemIf (&cseSet, ifPointerGet, IC_RESULT (ic));
1639 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RESULT (ic)->key);
1640 /* delete from inexpressions of all successors which
1641 have dfNum > than this block */
1642 for (i = 0; i < count; ebbs[i++]->visited = 0);
1643 applyToSet (ebb->succList, delGetPointerSucc, IC_RESULT (ic), ebb->dfnum);
1645 /* delete from cseSet all other pointer sets
1647 deleteItemIf (&ptrSetSet, ifPointerSet, IC_RESULT (ic));
1648 /* add to the local pointerset set */
1649 addSetHead (&ptrSetSet, newCseDef (IC_RESULT (ic), ic));
1652 /* add the result to defintion set */ if (IC_RESULT (ic))
1654 OP_DEFS (IC_RESULT (ic)) =
1655 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1656 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1657 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1658 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1662 /* if this is an addressof instruction then */
1663 /* put the symbol in the address of list & */
1664 /* delete it from the cseSet */
1665 if (defic->op == ADDRESS_OF)
1667 addSetHead (&ebb->addrOf, IC_LEFT (ic));
1668 deleteItemIf (&cseSet, ifDefSymIsX, IC_LEFT (ic));
1672 setToNull ((void **) &ebb->outExprs);
1673 ebb->outExprs = cseSet;
1674 ebb->outDefs = bitVectUnion (ebb->outDefs, ebb->defSet);
1675 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet, ebb->inPtrsSet);
1679 /*-----------------------------------------------------------------*/
1680 /* cseAllBlocks - will sequentially go thru & do cse for all blocks */
1681 /*-----------------------------------------------------------------*/
1683 cseAllBlocks (eBBlock ** ebbs, int count)
1688 /* if optimization turned off */
1690 for (i = 0; i < count; i++)
1691 change += cseBBlock (ebbs[i], FALSE, ebbs, count);