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 == '=')
258 /* if the result is volatile then return result */
259 if (IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
260 *opp = IC_RESULT (cdp->diCode);
262 /* if this is a straight assignment and
263 left is a temp then prefer the temporary to the
265 if (!POINTER_SET (cdp->diCode) &&
266 IS_ITEMP (IC_RESULT (cdp->diCode)) &&
267 IS_TRUE_SYMOP (IC_RIGHT (cdp->diCode)))
268 *opp = IC_RESULT (cdp->diCode);
270 /* if straight assignement && and both
271 are temps then prefer the one that
272 will not need extra space to spil, also
273 take into consideration if right side
274 an induction variable
276 if (!POINTER_SET (cdp->diCode) &&
277 IS_ITEMP (IC_RESULT (cdp->diCode)) &&
278 IS_ITEMP (IC_RIGHT (cdp->diCode)) &&
279 !OP_SYMBOL (IC_RIGHT (cdp->diCode))->isind &&
280 ((!SPIL_LOC (IC_RIGHT (cdp->diCode)) &&
281 SPIL_LOC (IC_RESULT (cdp->diCode))) ||
282 (SPIL_LOC (IC_RESULT (cdp->diCode)) &&
283 SPIL_LOC (IC_RESULT (cdp->diCode)) ==
284 SPIL_LOC (IC_RIGHT (cdp->diCode))))
286 *opp = IC_RESULT (cdp->diCode);
288 *opp = IC_RIGHT (cdp->diCode);
291 *opp = IC_RESULT (cdp->diCode);
294 /* if this is an assign to a temp. then check
295 if the right side is this then return this */
296 if (IS_TRUE_SYMOP (cop) &&
297 cdp->diCode->op == '=' &&
298 !POINTER_SET (cdp->diCode) &&
299 cop->key == IC_RIGHT (cdp->diCode)->key &&
300 !isGlobalInNearSpace (IC_RIGHT (cdp->diCode)) &&
301 IS_ITEMP (IC_RESULT (cdp->diCode)))
302 *opp = IC_RESULT (cdp->diCode);
307 if ((isGlobalInNearSpace (cop) &&
308 !isOperandLiteral (*opp)) ||
309 isOperandVolatile (*opp, FALSE)
316 if (cop->key == (*opp)->key)
322 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP (cop))
324 *opp = operandFromOperand (*opp);
325 (*opp)->isaddr = cop->isaddr;
335 /*-----------------------------------------------------------------*/
336 /* findPointerSet - finds the right side of a pointer set op */
337 /*-----------------------------------------------------------------*/
338 DEFSETFUNC (findPointerSet)
341 V_ARG (operand *, op);
342 V_ARG (operand **, opp);
343 V_ARG (operand *, rop);
345 if (POINTER_SET (cdp->diCode) &&
346 IC_RESULT (cdp->diCode)->key == op->key &&
347 !isOperandVolatile (IC_RESULT (cdp->diCode), TRUE) &&
348 !isOperandVolatile (IC_RIGHT (cdp->diCode), TRUE) &&
349 getSize (operandType (IC_RIGHT (cdp->diCode))) ==
350 getSize (operandType (rop)))
352 *opp = IC_RIGHT (cdp->diCode);
359 /*-----------------------------------------------------------------*/
360 /* findPrevIc - cseBBlock support function will return the iCode */
361 /* which matches the current one */
362 /*-----------------------------------------------------------------*/
363 DEFSETFUNC (findPrevIc)
367 V_ARG (iCode **, icp);
369 /* if already found */
373 /* if the iCodes are the same */
374 if (isiCodeEqual (ic, cdp->diCode) &&
375 isOperandEqual (cdp->sym, IC_RESULT (cdp->diCode)))
381 /* if iCodes are not the same */
382 /* see the operands maybe interchanged */
383 if (ic->op == cdp->diCode->op &&
384 (ic->op == '+' || ic->op == '*') &&
385 isOperandEqual (IC_LEFT (ic), IC_RIGHT (cdp->diCode)) &&
386 isOperandEqual (IC_RIGHT (ic), IC_LEFT (cdp->diCode)))
395 /*-----------------------------------------------------------------*/
396 /* ifDefGlobal - if definition is global */
397 /*-----------------------------------------------------------------*/
398 DEFSETFUNC (ifDefGlobal)
402 return (isOperandGlobal (cdp->sym));
405 /*-----------------------------------------------------------------*/
406 /* ifAnyGetPointer - if get pointer icode */
407 /*-----------------------------------------------------------------*/
408 DEFSETFUNC (ifAnyGetPointer)
412 if (cdp->diCode && POINTER_GET (cdp->diCode))
417 /*-----------------------------------------------------------------*/
418 /* ifOperandsHave - if any of the operand are the same as this */
419 /*-----------------------------------------------------------------*/
420 DEFSETFUNC (ifOperandsHave)
423 V_ARG (operand *, op);
426 if (IC_LEFT (cdp->diCode) &&
427 IS_SYMOP (IC_LEFT (cdp->diCode)) &&
428 IC_LEFT (cdp->diCode)->key == op->key)
431 if (IC_RIGHT (cdp->diCode) &&
432 IS_SYMOP (IC_RIGHT (cdp->diCode)) &&
433 IC_RIGHT (cdp->diCode)->key == op->key)
436 /* or if any of the operands are volatile */
437 if (IC_LEFT (cdp->diCode) &&
438 IS_OP_VOLATILE (IC_LEFT (cdp->diCode)))
441 if (IC_RIGHT (cdp->diCode) &&
442 IS_OP_VOLATILE (IC_RIGHT (cdp->diCode)))
446 if (IC_RESULT (cdp->diCode) &&
447 IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
453 /*-----------------------------------------------------------------*/
454 /* ifDefSymIs - if a definition is found in the set */
455 /*-----------------------------------------------------------------*/
457 ifDefSymIs (set * cseSet, operand * sym)
462 if (!sym || !IS_SYMOP (sym))
464 for (sl = cseSet; sl; sl = sl->next)
467 if (loop->sym->key == sym->key)
474 /*-----------------------------------------------------------------*/
475 /* ifDefSymIsX - will return 1 if the symbols match */
476 /*-----------------------------------------------------------------*/
477 DEFSETFUNC (ifDefSymIsX)
480 V_ARG (operand *, op);
483 return cdp->sym->key == op->key;
485 return (isOperandEqual (cdp->sym, op));
490 /*-----------------------------------------------------------------*/
491 /* ifDiCodeIs - returns truw if diCode is same */
492 /*-----------------------------------------------------------------*/
494 ifDiCodeIs (set * cseSet, iCode * ic)
502 for (sl = cseSet; sl; sl = sl->next)
505 if (loop->diCode == ic)
512 /*-----------------------------------------------------------------*/
513 /* ifPointerGet - returns true if the icode is pointer get sym */
514 /*-----------------------------------------------------------------*/
515 DEFSETFUNC (ifPointerGet)
518 V_ARG (operand *, op);
519 iCode *dic = cdp->diCode;
520 operand *left = IC_LEFT (cdp->diCode);
522 if (POINTER_GET (dic) && left->key == op->key)
528 /*-----------------------------------------------------------------*/
529 /* ifPointerSet - returns true if the icode is pointer set sym */
530 /*-----------------------------------------------------------------*/
531 DEFSETFUNC (ifPointerSet)
534 V_ARG (operand *, op);
536 if (POINTER_SET (cdp->diCode) &&
537 IC_RESULT (cdp->diCode)->key == op->key)
543 /*-----------------------------------------------------------------*/
544 /* ifDiCodeIsX - will return 1 if the symbols match */
545 /*-----------------------------------------------------------------*/
546 DEFSETFUNC (ifDiCodeIsX)
551 return cdp->diCode == ic;
555 /*-----------------------------------------------------------------*/
556 /* algebraicOpts - does some algebraic optimizations */
557 /*-----------------------------------------------------------------*/
559 algebraicOpts (iCode * ic)
561 /* we don't deal with the following iCodes
572 /* if both operands present & ! IFX */
573 /* then if they are both literal we */
574 /* perform the operation right now */
575 if (IC_RESULT (ic) &&
578 IS_OP_LITERAL (IC_LEFT (ic)) &&
579 IS_OP_LITERAL (IC_RIGHT (ic)))
582 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
585 operandType (IC_RESULT (ic)));
588 SET_RESULT_RIGHT (ic);
592 /* if not ifx & only one operand present */
593 if (IC_RESULT (ic) &&
595 IS_OP_LITERAL (IC_LEFT (ic)) &&
599 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
602 operandType (IC_RESULT (ic)));
605 SET_RESULT_RIGHT (ic);
610 /* a special case : or in short a kludgy solution will think
611 about a better solution over a glass of wine someday */
612 if (ic->op == GET_VALUE_AT_ADDRESS)
615 if (IS_ITEMP (IC_RESULT (ic)) &&
616 IS_TRUE_SYMOP (IC_LEFT (ic)))
620 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
621 IC_RIGHT (ic)->isaddr = 0;
623 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
624 IC_RESULT (ic)->isaddr = 0;
625 setOperandType (IC_RESULT (ic), operandType (IC_RIGHT (ic)));
629 if (IS_ITEMP (IC_LEFT (ic)) &&
630 IS_ITEMP (IC_RESULT (ic)) &&
631 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
632 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
633 !IC_LEFT (ic)->isaddr)
636 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
637 IC_RIGHT (ic)->isaddr = 0;
638 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
639 IC_RESULT (ic)->isaddr = 0;
647 /* depending on the operation */
651 /* if adding the same thing change to left shift by 1 */
652 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key &&
653 !IS_FLOAT (operandType (IC_RESULT (ic))))
656 IC_RIGHT (ic) = operandFromLit (1);
659 /* if addition then check if one of them is a zero */
660 /* if yes turn it into assignmnt */
661 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
662 operandLitValue (IC_LEFT (ic)) == 0.0)
667 SET_ISADDR (IC_RESULT (ic), 0);
668 SET_ISADDR (IC_RIGHT (ic), 0);
671 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
672 operandLitValue (IC_RIGHT (ic)) == 0.0)
676 IC_RIGHT (ic) = IC_LEFT (ic);
678 SET_ISADDR (IC_RIGHT (ic), 0);
679 SET_ISADDR (IC_RESULT (ic), 0);
684 /* if subtracting the the same thing then zero */
685 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
688 IC_RIGHT (ic) = operandFromLit (0);
690 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
691 IC_RESULT (ic)->isaddr = 0;
695 /* if subtraction then check if one of the operand */
696 /* is zero then depending on which operand change */
697 /* to assignment or unary minus */
698 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
699 operandLitValue (IC_RIGHT (ic)) == 0.0)
701 /* right size zero change to assignment */
703 IC_RIGHT (ic) = IC_LEFT (ic);
705 SET_ISADDR (IC_RIGHT (ic), 0);
706 SET_ISADDR (IC_RESULT (ic), 0);
709 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
710 operandLitValue (IC_LEFT (ic)) == 0.0)
712 /* left zero turn into an unary minus */
714 IC_LEFT (ic) = IC_RIGHT (ic);
715 IC_RIGHT (ic) = NULL;
719 /* if multiplication then check if either of */
720 /* them is zero then the result is zero */
721 /* if either of them is one then result is */
724 if (IS_OP_LITERAL (IC_LEFT (ic)))
727 if (operandLitValue (IC_LEFT (ic)) == 0.0)
730 IC_RIGHT (ic) = IC_LEFT (ic);
732 SET_RESULT_RIGHT (ic);
735 if (operandLitValue (IC_LEFT (ic)) == 1.0)
739 SET_RESULT_RIGHT (ic);
744 if (IS_OP_LITERAL (IC_RIGHT (ic)))
747 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
751 SET_RESULT_RIGHT (ic);
755 if (operandLitValue (IC_RIGHT (ic)) == 1.0)
758 IC_RIGHT (ic) = IC_LEFT (ic);
760 SET_RESULT_RIGHT (ic);
766 /* if division by self then 1 */
767 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
770 IC_RIGHT (ic) = operandFromLit (1);
772 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
773 IC_RESULT (ic)->isaddr = 0;
775 /* if this is a division then check if right */
776 /* is one then change it to an assignment */
777 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
778 operandLitValue (IC_RIGHT (ic)) == 1.0)
782 IC_RIGHT (ic) = IC_LEFT (ic);
784 SET_RESULT_RIGHT (ic);
788 /* if both are the same for an comparison operators */
792 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
795 IC_RIGHT (ic) = operandFromLit (1);
797 SET_RESULT_RIGHT (ic);
803 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
806 IC_RIGHT (ic) = operandFromLit (0);
808 SET_RESULT_RIGHT (ic);
812 /* if this is a cast of a literal value */
813 if (IS_OP_LITERAL (IC_RIGHT (ic)))
817 operandFromValue (valCastLiteral (operandType (IC_LEFT (ic)),
818 operandLitValue (IC_RIGHT (ic))));
820 SET_ISADDR (IC_RESULT (ic), 0);
822 /* if casting to the same */
823 if (checkType (operandType (IC_RESULT (ic)),
824 operandType (IC_RIGHT (ic))) == 1)
828 SET_ISADDR (IC_RESULT (ic), 0);
832 if (IS_OP_LITERAL (IC_LEFT (ic)))
836 (operandLitValue (IC_LEFT (ic)) == 0 ?
837 operandFromLit (1) : operandFromLit (0));
839 SET_ISADDR (IC_RESULT (ic), 0);
845 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
846 /*-----------------------------------------------------------------*/
847 /* updateSpillLocation - keeps track of register spill location */
848 /*-----------------------------------------------------------------*/
850 updateSpillLocation (iCode * ic)
855 if (POINTER_SET (ic))
861 /* for the form true_symbol := iTempNN */
862 if (ASSIGN_ITEMP_TO_SYM (ic)
863 && !SPIL_LOC (IC_RIGHT (ic)))
866 setype = getSpec (operandType (IC_RESULT (ic)));
868 if (!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) &&
878 !SPIL_LOC (IC_RIGHT (ic)) &&
879 !bitVectBitsInCommon (OP_DEFS (IC_RIGHT (ic)), OP_USES (IC_RESULT (ic))) &&
880 OP_SYMBOL (IC_RESULT (ic))->isreqv)
883 setype = getSpec (operandType (IC_RESULT (ic)));
885 if (!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));
895 /*-----------------------------------------------------------------*/
896 /* setUsesDef - sets the uses def bitvector for a given operand */
897 /*-----------------------------------------------------------------*/
899 setUsesDefs (operand * op, bitVect * bdefs,
900 bitVect * idefs, bitVect ** oud)
902 /* compute the definitions alive at this point */
903 bitVect *adefs = bitVectUnion (bdefs, idefs);
905 /* of these definitions find the ones that are */
906 /* for this operand */
907 adefs = bitVectIntersect (adefs, OP_DEFS (op));
909 /* these are the definitions that this operand can use */
910 op->usesDefs = adefs;
912 /* the out defs is an union */
913 *oud = bitVectUnion (*oud, adefs);
916 /*-----------------------------------------------------------------*/
917 /* unsetDefsAndUses - clear this operation for the operands */
918 /*-----------------------------------------------------------------*/
920 unsetDefsAndUses (iCode * ic)
922 if (ic->op == JUMPTABLE)
925 /* take away this definition from the def chain of the */
926 /* result & take away from use set of the operands */
929 /* turn off def set */
930 if (IS_SYMOP (IC_RESULT (ic)))
932 if (!POINTER_SET (ic))
933 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
935 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
937 /* turn off the useSet for the operands */
938 if (IS_SYMOP (IC_LEFT (ic)))
939 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
941 if (IS_SYMOP (IC_RIGHT (ic)))
942 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
945 /* must be ifx turn off the use */ if (IS_SYMOP (IC_COND (ic)))
946 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
949 /*-----------------------------------------------------------------*/
950 /* ifxOptimize - changes ifx conditions if it can */
951 /*-----------------------------------------------------------------*/
953 ifxOptimize (iCode * ic, set * cseSet,
955 eBBlock * ebb, int *change,
956 eBBlock ** ebbs, int count)
961 /* if the condition can be replaced */
965 applyToSetFTrue (cseSet, findCheaperOp, IC_COND (ic), &pdop);
973 /* if the conditional is a literal then */
974 if (IS_OP_LITERAL (IC_COND (ic)))
977 if ((operandLitValue (IC_COND (ic)) != 0.0) && IC_TRUE (ic))
980 /* change to a goto */
982 IC_LABEL (ic) = IC_TRUE (ic);
989 if (!operandLitValue (IC_COND (ic)) && IC_FALSE (ic))
992 IC_LABEL (ic) = IC_FALSE (ic);
998 /* then kill this if condition */
999 remiCodeFromeBBlock (ebb, ic);
1003 /* now we need to recompute the control flow */
1004 /* since the control flow has changed */
1005 /* this is very expensive but it does not happen */
1006 /* too often, if it does happen then the user pays */
1008 computeControlFlow (ebbs, count, 1);
1009 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1013 /* if there is only one successor and that successor
1014 is the same one we are conditionally going to then
1015 we can remove this conditional statement */
1016 label = (IC_TRUE (ic) ? IC_TRUE (ic) : IC_FALSE (ic));
1017 if (elementsInSet (ebb->succList) == 1 &&
1018 isinSet (ebb->succList, eBBWithEntryLabel (ebbs, label, count)))
1021 remiCodeFromeBBlock (ebb, ic);
1022 computeControlFlow (ebbs, count, 1);
1023 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1028 /* if it remains an IFX the update the use Set */
1029 OP_USES (IC_COND (ic)) = bitVectSetBit (OP_USES (IC_COND (ic)), ic->key);
1030 setUsesDefs (IC_COND (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1034 /*-----------------------------------------------------------------*/
1035 /* diCodeForSym - finds the definiting instruction for a symbol */
1036 /*-----------------------------------------------------------------*/
1037 DEFSETFUNC (diCodeForSym)
1040 V_ARG (operand *, sym);
1041 V_ARG (iCode **, dic);
1043 /* if already found */
1047 /* if not if this is the defining iCode */
1048 if (sym->key == cdp->key)
1057 /*-----------------------------------------------------------------*/
1058 /* constFold - does some constant folding */
1059 /*-----------------------------------------------------------------*/
1061 constFold (iCode * ic, set * cseSet)
1065 /* this routine will change
1071 /* deal with only + & - */
1072 if (ic->op != '+' &&
1076 /* this check is a hueristic to prevent live ranges
1077 from becoming too long */
1078 if (IS_PTR (operandType (IC_RESULT (ic))))
1081 /* check if operation with a literal */
1082 if (!IS_OP_LITERAL (IC_RIGHT (ic)))
1085 /* check if we can find a definition for the
1087 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (ic), &dic)))
1090 /* check that this is also a +/- */
1091 if (dic->op != '+' && dic->op != '-')
1094 /* with a literal */
1095 if (!IS_OP_LITERAL (IC_RIGHT (dic)))
1098 /* find the definition of the left operand
1099 of dic.then check if this defined with a
1100 get_pointer return 0 if the pointer size is
1101 less than 2 (MCS51 specific) */
1102 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (dic), &ldic)))
1105 if (POINTER_GET (ldic) && getSize (operandType (IC_LEFT (ldic))) <= 1)
1108 /* it is if the operations are the same */
1109 /* the literal parts need to be added */
1110 IC_LEFT (ic) = operandFromOperand (IC_LEFT (dic));
1111 if (ic->op == dic->op)
1112 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) +
1113 operandLitValue (IC_RIGHT (dic)));
1115 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) -
1116 operandLitValue (IC_RIGHT (dic)));
1118 if (IS_ITEMP (IC_RESULT (ic)))
1120 SPIL_LOC (IC_RESULT (ic)) = NULL;
1121 IC_RESULT (ic)->noSpilLoc = 1;
1128 /*-----------------------------------------------------------------*/
1129 /* deleteGetPointers - called when a pointer is passed as parm */
1130 /* will delete from cseSet all get pointers computed from this */
1131 /* pointer. A simple ifOperandsHave is not good enough here */
1132 /*-----------------------------------------------------------------*/
1134 deleteGetPointers (set ** cseSet, set ** pss, operand * op, eBBlock * ebb)
1136 set *compItems = NULL;
1141 if (!*cseSet && !*pss)
1144 /* first find all items computed from this operand .
1145 This done fairly simply go thru the list and find
1146 those that are computed by arthimetic with this
1148 for (cdp = setFirstItem (*cseSet); cdp; cdp = setNextItem (*cseSet))
1150 if (IS_ARITHMETIC_OP (cdp->diCode))
1152 if (isOperandEqual (IC_LEFT (cdp->diCode), op) ||
1153 isOperandEqual (IC_RIGHT (cdp->diCode), op))
1155 /* save it in our list of items */
1156 addSet (&compItems, IC_RESULT (cdp->diCode));
1158 /* also check for those computed from our computed
1159 list . This will take care of situations like
1160 iTemp1 = iTemp0 + 8;
1161 iTemp2 = iTemp1 + 8; */
1162 if (isinSetWith (compItems, (void*)IC_LEFT (cdp->diCode),
1163 (void*)isOperandEqual) ||
1164 isinSetWith (compItems, (void*)IC_RIGHT (cdp->diCode),
1165 (void*)isOperandEqual))
1167 addSet (&compItems, IC_RESULT (cdp->diCode));
1172 /* now delete all pointer gets with this op */
1173 deleteItemIf (cseSet, ifPointerGet, op);
1174 deleteItemIf (pss, ifPointerSet, op);
1176 /* set the bit vector used by dataFlow computation later */
1177 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, op->key);
1178 /* now for the computed items */
1179 for (cop = setFirstItem (compItems); cop; cop = setNextItem (compItems))
1181 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, cop->key);
1182 deleteItemIf (cseSet, ifPointerGet, cop);
1183 deleteItemIf (pss, ifPointerSet, cop);
1187 /*-----------------------------------------------------------------*/
1188 /* delGetPointerSucc - delete get pointer from inExprs of succ with */
1189 /* dfnum > supplied */
1190 /*-----------------------------------------------------------------*/
1191 DEFSETFUNC (delGetPointerSucc)
1193 eBBlock *ebp = item;
1194 V_ARG (operand *, op);
1201 if (ebp->dfnum > dfnum)
1203 deleteItemIf (&ebp->inExprs, ifPointerGet, op);
1206 return applyToSet (ebp->succList, delGetPointerSucc, op, dfnum);
1209 /*-----------------------------------------------------------------*/
1210 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1211 /*-----------------------------------------------------------------*/
1213 fixUpTypes (iCode * ic)
1215 sym_link *t1 = operandType (IC_LEFT (ic)), *t2;
1217 if (TARGET_IS_DS390)
1223 /* for pointer_gets if the types of result & left r the
1224 same then change it type of result to next */
1226 checkType (t2 = operandType (IC_RESULT (ic)), t1) == 1)
1228 setOperandType (IC_RESULT (ic), t2->next);
1232 /*-----------------------------------------------------------------*/
1233 /* cseBBlock - common subexpression elimination for basic blocks */
1234 /* this is the hackiest kludgiest routine in the whole */
1235 /* system. also the most important, since almost all */
1236 /* data flow related information is computed by it */
1237 /*-----------------------------------------------------------------*/
1239 cseBBlock (eBBlock * ebb, int computeOnly,
1240 eBBlock ** ebbs, int count)
1246 set *ptrSetSet = NULL;
1248 /* if this block is not reachable */
1252 /* set of common subexpressions */
1253 cseSet = setFromSet (ebb->inExprs);
1255 /* these will be computed by this routine */
1256 setToNull ((void **) &ebb->outDefs);
1257 setToNull ((void **) &ebb->defSet);
1258 setToNull ((void **) &ebb->usesDefs);
1259 setToNull ((void **) &ebb->ptrsSet);
1260 setToNull ((void **) &ebb->addrOf);
1261 setToNull ((void **) &ebb->ldefs);
1263 ebb->outDefs = bitVectCopy (ebb->inDefs);
1264 bitVectDefault = iCodeKey;
1265 ebb->defSet = newBitVect (iCodeKey);
1266 ebb->usesDefs = newBitVect (iCodeKey);
1268 /* for all the instructions in this block do */
1269 for (ic = ebb->sch; ic; ic = ic->next)
1279 /* if this is an assignment from true symbol
1280 to a temp then do pointer post inc/dec optimzation */
1281 if (ic->op == '=' && !POINTER_SET (ic) &&
1282 IS_PTR (operandType (IC_RESULT (ic))))
1284 ptrPostIncDecOpt (ic);
1287 /* clear the def & use chains for the operands involved */
1288 /* in this operation . since it can change due to opts */
1289 unsetDefsAndUses (ic);
1291 if (ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE)
1293 /* add to defSet of the symbol */
1294 OP_DEFS (IC_RESULT (ic)) =
1295 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1296 /* add to the definition set of this block */
1297 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1298 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1299 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1300 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1301 /* delete global variables from the cseSet
1302 since they can be modified by the function call */
1303 deleteItemIf (&cseSet, ifDefGlobal);
1304 /* delete all getpointer iCodes from cseSet, this should
1305 be done only for global arrays & pointers but at this
1306 point we don't know if globals, so to be safe do all */
1307 deleteItemIf (&cseSet, ifAnyGetPointer);
1310 /* for pcall & ipush we need to add to the useSet */
1311 if ((ic->op == PCALL ||
1315 IS_SYMOP (IC_LEFT (ic)))
1318 /* check if they can be replaced */
1322 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1324 IC_LEFT (ic) = pdop;
1326 /* the lookup could have changed it */
1327 if (IS_SYMOP (IC_LEFT (ic)))
1329 OP_USES (IC_LEFT (ic)) =
1330 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1331 setUsesDefs (IC_LEFT (ic), ebb->defSet,
1332 ebb->outDefs, &ebb->usesDefs);
1336 /* if we a sending a pointer as a parameter
1337 then kill all cse since the pointed to item
1338 might be changed in the function being called */
1339 if ((ic->op == IPUSH || ic->op == SEND) &&
1340 IS_PTR (operandType (IC_LEFT (ic))))
1342 deleteGetPointers (&cseSet, &ptrSetSet, IC_LEFT (ic), ebb);
1343 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_LEFT (ic)->key);
1344 for (i = 0; i < count; ebbs[i++]->visited = 0);
1345 applyToSet (ebb->succList, delGetPointerSucc,
1346 IC_LEFT (ic), ebb->dfnum);
1351 /* if jumptable then mark the usage */
1352 if (ic->op == JUMPTABLE)
1354 OP_USES (IC_JTCOND (ic)) =
1355 bitVectSetBit (OP_USES (IC_JTCOND (ic)), ic->key);
1356 setUsesDefs (IC_JTCOND (ic), ebb->defSet,
1357 ebb->outDefs, &ebb->usesDefs);
1364 /* do some algebraic optimizations if possible */
1366 while (constFold (ic, cseSet));
1369 if (POINTER_GET (ic) && !IS_PTR (operandType (IC_LEFT (ic))))
1371 setOperandType (IC_LEFT (ic),
1372 aggrToPtr (operandType (IC_LEFT (ic)), FALSE));
1376 if (POINTER_SET (ic) && !IS_PTR (operandType (IC_RESULT (ic))))
1378 setOperandType (IC_RESULT (ic),
1379 aggrToPtr (operandType (IC_RESULT (ic)), FALSE));
1382 /* if this is a condition statment then */
1383 /* check if the condition can be replaced */
1386 ifxOptimize (ic, cseSet, computeOnly,
1392 /* if the assignment & result is a temp */
1393 /* see if we can replace it */
1397 /* update the spill location for this */
1398 updateSpillLocation (ic);
1400 if (POINTER_SET (ic) &&
1401 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype)))
1404 applyToSetFTrue (cseSet, findCheaperOp, IC_RESULT (ic), &pdop);
1405 if (pdop && IS_ITEMP (pdop) && !computeOnly)
1406 IC_RESULT (ic) = pdop;
1410 /* do the operand lookup i.e. for both the */
1411 /* right & left operand : check the cseSet */
1412 /* to see if they have been replaced if yes */
1413 /* then replace them with those from cseSet */
1415 /* and left is a symbol */
1416 if (IS_SYMOP (IC_LEFT (ic)) &&
1417 !computeOnly && ic->op != ADDRESS_OF)
1421 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1424 if (POINTER_GET (ic))
1426 if (IS_ITEMP (pdop) || IS_OP_LITERAL (pdop))
1428 IC_LEFT (ic) = pdop;
1431 /* check if there is a pointer set
1432 for the same pointer visible if yes
1433 then change this into an assignment */
1435 if (applyToSetFTrue (cseSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic)) &&
1436 !bitVectBitValue (ebb->ptrsSet, pdop->key))
1439 IC_LEFT (ic) = NULL;
1440 IC_RIGHT (ic) = pdop;
1441 SET_ISADDR (IC_RESULT (ic), 0);
1447 IC_LEFT (ic) = pdop;
1454 if (IS_SYMOP (IC_RIGHT (ic)) && !computeOnly)
1458 applyToSetFTrue (cseSet, findCheaperOp, IC_RIGHT (ic), &pdop);
1462 IC_RIGHT (ic) = pdop;
1467 /* if left or right changed then do algebraic */
1471 while (constFold (ic, cseSet));
1474 /* if after all this it becomes a assignment to self
1475 then delete it and continue */
1476 if (ASSIGNMENT_TO_SELF (ic))
1478 remiCodeFromeBBlock (ebb, ic);
1482 /* now we will check to see if the entire */
1483 /* operation has been performed before */
1484 /* and is available */
1485 /* don't do assignments they will be killed */
1486 /* by dead code elimination if required do */
1487 /* it only if result is a temporary */
1489 if (!(POINTER_GET (ic) &&
1490 (IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1491 isOperandVolatile (IC_LEFT (ic), TRUE) ||
1492 bitVectBitValue (ebb->ndompset, IC_LEFT (ic)->key))) &&
1494 IS_ITEMP (IC_RESULT (ic)) &&
1497 applyToSet (cseSet, findPrevIc, ic, &pdic);
1498 if (pdic && checkType (operandType (IC_RESULT (pdic)),
1499 operandType (IC_RESULT (ic))) != 1)
1503 /* if found then eliminate this and add to */
1504 /* to cseSet an element containing result */
1505 /* of this with previous opcode */
1509 if (IS_ITEMP (IC_RESULT (ic)))
1512 /* replace in the remaining of this block */
1513 replaceAllSymBySym (ic->next, IC_RESULT (ic), IC_RESULT (pdic), &ebb->ndompset);
1514 /* remove this iCode from inexpressions of all
1515 its successors, it cannot be in the in expressions
1516 of any of the predecessors */
1517 for (i = 0; i < count; ebbs[i++]->visited = 0);
1518 applyToSet (ebb->succList, removeFromInExprs, ic, IC_RESULT (ic),
1519 IC_RESULT (pdic), ebb);
1521 /* if this was moved from another block */
1522 /* then replace in those blocks too */
1526 for (owner = setFirstItem (ic->movedFrom); owner;
1527 owner = setNextItem (ic->movedFrom))
1528 replaceAllSymBySym (owner->sch, IC_RESULT (ic), IC_RESULT (pdic), &owner->ndompset);
1530 pdic->movedFrom = unionSets (pdic->movedFrom, ic->movedFrom, THROW_NONE);
1533 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), pdic));
1536 /* eliminate this */
1537 remiCodeFromeBBlock (ebb, ic);
1542 if (IS_ITEMP (IC_RESULT (ic)))
1549 /* just add this as a previous expression except in */
1550 /* case of a pointer access in which case this is a */
1551 /* usage not a definition */
1552 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1554 deleteItemIf (&cseSet, ifDefSymIsX, IC_RESULT (ic));
1555 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), ic));
1561 /* if assignment to a parameter which is not
1562 mine and type is a pointer then delete
1563 pointerGets to take care of aliasing */
1564 if (ASSIGNMENT (ic) &&
1565 OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))) &&
1566 IS_PTR (operandType (IC_RESULT (ic))))
1568 deleteGetPointers (&cseSet, &ptrSetSet, IC_RIGHT (ic), ebb);
1569 for (i = 0; i < count; ebbs[i++]->visited = 0);
1570 applyToSet (ebb->succList, delGetPointerSucc, IC_RIGHT (ic), ebb->dfnum);
1571 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RIGHT (ic)->key);
1574 /* if this is a pointerget then see if we can replace
1575 this with a previously assigned pointer value */
1576 if (POINTER_GET (ic) &&
1577 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1578 isOperandVolatile (IC_LEFT (ic), TRUE)))
1581 applyToSet (ptrSetSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic));
1582 /* if we find it then locally replace all
1583 references to the result with what we assigned */
1586 replaceAllSymBySym (ic->next, IC_RESULT (ic), pdop, &ebb->ndompset);
1590 /* delete from the cseSet anything that has */
1591 /* operands matching the result of this */
1592 /* except in case of pointer access */
1593 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1595 deleteItemIf (&cseSet, ifOperandsHave, IC_RESULT (ic));
1596 /* delete any previous definitions */
1597 ebb->defSet = bitVectCplAnd (ebb->defSet, OP_DEFS (IC_RESULT (ic)));
1601 /* add the left & right to the defUse set */
1602 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)))
1604 OP_USES (IC_LEFT (ic)) =
1605 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1606 setUsesDefs (IC_LEFT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1610 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)))
1612 OP_USES (IC_RIGHT (ic)) =
1613 bitVectSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1614 setUsesDefs (IC_RIGHT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1618 /* for the result it is special case, put the result */
1619 /* in the defuseSet if it a pointer or array access */
1620 if (POINTER_SET (defic))
1622 OP_USES (IC_RESULT (ic)) =
1623 bitVectSetBit (OP_USES (IC_RESULT (ic)), ic->key);
1624 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1625 deleteItemIf (&cseSet, ifPointerGet, IC_RESULT (ic));
1626 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RESULT (ic)->key);
1627 /* delete from inexpressions of all successors which
1628 have dfNum > than this block */
1629 for (i = 0; i < count; ebbs[i++]->visited = 0);
1630 applyToSet (ebb->succList, delGetPointerSucc, IC_RESULT (ic), ebb->dfnum);
1632 /* delete from cseSet all other pointer sets
1634 deleteItemIf (&ptrSetSet, ifPointerSet, IC_RESULT (ic));
1635 /* add to the local pointerset set */
1636 addSetHead (&ptrSetSet, newCseDef (IC_RESULT (ic), ic));
1639 /* add the result to defintion set */ if (IC_RESULT (ic))
1641 OP_DEFS (IC_RESULT (ic)) =
1642 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1643 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1644 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1645 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1649 /* if this is an addressof instruction then */
1650 /* put the symbol in the address of list & */
1651 /* delete it from the cseSet */
1652 if (defic->op == ADDRESS_OF)
1654 addSetHead (&ebb->addrOf, IC_LEFT (ic));
1655 deleteItemIf (&cseSet, ifDefSymIsX, IC_LEFT (ic));
1659 setToNull ((void **) &ebb->outExprs);
1660 ebb->outExprs = cseSet;
1661 ebb->outDefs = bitVectUnion (ebb->outDefs, ebb->defSet);
1662 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet, ebb->inPtrsSet);
1666 /*-----------------------------------------------------------------*/
1667 /* cseAllBlocks - will sequentially go thru & do cse for all blocks */
1668 /*-----------------------------------------------------------------*/
1670 cseAllBlocks (eBBlock ** ebbs, int count)
1675 /* if optimization turned off */
1677 for (i = 0; i < count; i++)
1678 change += cseBBlock (ebbs[i], FALSE, ebbs, count);