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);
303 if ((*opp)&&(SPEC_USIGN(operandType (cop))==SPEC_USIGN(operandType (*opp))))
306 if ((isGlobalInNearSpace (cop) &&
307 !isOperandLiteral (*opp)) ||
308 isOperandVolatile (*opp, FALSE)
315 if (cop->key == (*opp)->key)
321 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP (cop))
323 *opp = operandFromOperand (*opp);
324 (*opp)->isaddr = cop->isaddr;
334 /*-----------------------------------------------------------------*/
335 /* findPointerSet - finds the right side of a pointer set op */
336 /*-----------------------------------------------------------------*/
337 DEFSETFUNC (findPointerSet)
340 V_ARG (operand *, op);
341 V_ARG (operand **, opp);
342 V_ARG (operand *, rop);
344 if (POINTER_SET (cdp->diCode) &&
345 IC_RESULT (cdp->diCode)->key == op->key &&
346 !isOperandVolatile (IC_RESULT (cdp->diCode), TRUE) &&
347 !isOperandVolatile (IC_RIGHT (cdp->diCode), TRUE) &&
348 getSize (operandType (IC_RIGHT (cdp->diCode))) ==
349 getSize (operandType (rop)))
351 *opp = IC_RIGHT (cdp->diCode);
358 /*-----------------------------------------------------------------*/
359 /* findPrevIc - cseBBlock support function will return the iCode */
360 /* which matches the current one */
361 /*-----------------------------------------------------------------*/
362 DEFSETFUNC (findPrevIc)
366 V_ARG (iCode **, icp);
368 /* if already found */
372 /* if the iCodes are the same */
373 if (isiCodeEqual (ic, cdp->diCode) &&
374 isOperandEqual (cdp->sym, IC_RESULT (cdp->diCode)))
380 /* if iCodes are not the same */
381 /* see the operands maybe interchanged */
382 if (ic->op == cdp->diCode->op &&
383 (ic->op == '+' || ic->op == '*') &&
384 isOperandEqual (IC_LEFT (ic), IC_RIGHT (cdp->diCode)) &&
385 isOperandEqual (IC_RIGHT (ic), IC_LEFT (cdp->diCode)))
394 /*-----------------------------------------------------------------*/
395 /* ifDefGlobal - if definition is global */
396 /*-----------------------------------------------------------------*/
397 DEFSETFUNC (ifDefGlobal)
401 return (isOperandGlobal (cdp->sym));
404 /*-----------------------------------------------------------------*/
405 /* ifAnyGetPointer - if get pointer icode */
406 /*-----------------------------------------------------------------*/
407 DEFSETFUNC (ifAnyGetPointer)
411 if (cdp->diCode && POINTER_GET (cdp->diCode))
416 /*-----------------------------------------------------------------*/
417 /* ifOperandsHave - if any of the operand are the same as this */
418 /*-----------------------------------------------------------------*/
419 DEFSETFUNC (ifOperandsHave)
422 V_ARG (operand *, op);
425 if (IC_LEFT (cdp->diCode) &&
426 IS_SYMOP (IC_LEFT (cdp->diCode)) &&
427 IC_LEFT (cdp->diCode)->key == op->key)
430 if (IC_RIGHT (cdp->diCode) &&
431 IS_SYMOP (IC_RIGHT (cdp->diCode)) &&
432 IC_RIGHT (cdp->diCode)->key == op->key)
435 /* or if any of the operands are volatile */
436 if (IC_LEFT (cdp->diCode) &&
437 IS_OP_VOLATILE (IC_LEFT (cdp->diCode)))
440 if (IC_RIGHT (cdp->diCode) &&
441 IS_OP_VOLATILE (IC_RIGHT (cdp->diCode)))
445 if (IC_RESULT (cdp->diCode) &&
446 IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
452 /*-----------------------------------------------------------------*/
453 /* ifDefSymIs - if a definition is found in the set */
454 /*-----------------------------------------------------------------*/
456 ifDefSymIs (set * cseSet, operand * sym)
461 if (!sym || !IS_SYMOP (sym))
463 for (sl = cseSet; sl; sl = sl->next)
466 if (loop->sym->key == sym->key)
473 /*-----------------------------------------------------------------*/
474 /* ifDefSymIsX - will return 1 if the symbols match */
475 /*-----------------------------------------------------------------*/
476 DEFSETFUNC (ifDefSymIsX)
479 V_ARG (operand *, op);
482 return cdp->sym->key == op->key;
484 return (isOperandEqual (cdp->sym, op));
489 /*-----------------------------------------------------------------*/
490 /* ifDiCodeIs - returns truw if diCode is same */
491 /*-----------------------------------------------------------------*/
493 ifDiCodeIs (set * cseSet, iCode * ic)
501 for (sl = cseSet; sl; sl = sl->next)
504 if (loop->diCode == ic)
511 /*-----------------------------------------------------------------*/
512 /* ifPointerGet - returns true if the icode is pointer get sym */
513 /*-----------------------------------------------------------------*/
514 DEFSETFUNC (ifPointerGet)
517 V_ARG (operand *, op);
518 iCode *dic = cdp->diCode;
519 operand *left = IC_LEFT (cdp->diCode);
521 if (POINTER_GET (dic) && left->key == op->key)
527 /*-----------------------------------------------------------------*/
528 /* ifPointerSet - returns true if the icode is pointer set sym */
529 /*-----------------------------------------------------------------*/
530 DEFSETFUNC (ifPointerSet)
533 V_ARG (operand *, op);
535 if (POINTER_SET (cdp->diCode) &&
536 IC_RESULT (cdp->diCode)->key == op->key)
542 /*-----------------------------------------------------------------*/
543 /* ifDiCodeIsX - will return 1 if the symbols match */
544 /*-----------------------------------------------------------------*/
545 DEFSETFUNC (ifDiCodeIsX)
550 return cdp->diCode == ic;
554 /*-----------------------------------------------------------------*/
555 /* algebraicOpts - does some algebraic optimizations */
556 /*-----------------------------------------------------------------*/
558 algebraicOpts (iCode * ic)
560 /* we don't deal with the following iCodes
571 /* if both operands present & ! IFX */
572 /* then if they are both literal we */
573 /* perform the operation right now */
574 if (IC_RESULT (ic) &&
577 IS_OP_LITERAL (IC_LEFT (ic)) &&
578 IS_OP_LITERAL (IC_RIGHT (ic)))
581 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
584 operandType (IC_RESULT (ic)));
587 SET_RESULT_RIGHT (ic);
591 /* if not ifx & only one operand present */
592 if (IC_RESULT (ic) &&
594 IS_OP_LITERAL (IC_LEFT (ic)) &&
598 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
601 operandType (IC_RESULT (ic)));
604 SET_RESULT_RIGHT (ic);
609 /* a special case : or in short a kludgy solution will think
610 about a better solution over a glass of wine someday */
611 if (ic->op == GET_VALUE_AT_ADDRESS)
614 if (IS_ITEMP (IC_RESULT (ic)) &&
615 IS_TRUE_SYMOP (IC_LEFT (ic)))
619 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
620 IC_RIGHT (ic)->isaddr = 0;
622 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
623 IC_RESULT (ic)->isaddr = 0;
624 setOperandType (IC_RESULT (ic), operandType (IC_RIGHT (ic)));
628 if (IS_ITEMP (IC_LEFT (ic)) &&
629 IS_ITEMP (IC_RESULT (ic)) &&
630 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
631 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
632 !IC_LEFT (ic)->isaddr)
635 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
636 IC_RIGHT (ic)->isaddr = 0;
637 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
638 IC_RESULT (ic)->isaddr = 0;
646 /* depending on the operation */
650 /* if adding the same thing change to left shift by 1 */
651 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key &&
652 !IS_FLOAT (operandType (IC_RESULT (ic))))
655 IC_RIGHT (ic) = operandFromLit (1);
658 /* if addition then check if one of them is a zero */
659 /* if yes turn it into assignmnt */
660 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
661 operandLitValue (IC_LEFT (ic)) == 0.0)
666 SET_ISADDR (IC_RESULT (ic), 0);
667 SET_ISADDR (IC_RIGHT (ic), 0);
670 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
671 operandLitValue (IC_RIGHT (ic)) == 0.0)
675 IC_RIGHT (ic) = IC_LEFT (ic);
677 SET_ISADDR (IC_RIGHT (ic), 0);
678 SET_ISADDR (IC_RESULT (ic), 0);
683 /* if subtracting the the same thing then zero */
684 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
687 IC_RIGHT (ic) = operandFromLit (0);
689 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
690 IC_RESULT (ic)->isaddr = 0;
694 /* if subtraction then check if one of the operand */
695 /* is zero then depending on which operand change */
696 /* to assignment or unary minus */
697 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
698 operandLitValue (IC_RIGHT (ic)) == 0.0)
700 /* right size zero change to assignment */
702 IC_RIGHT (ic) = IC_LEFT (ic);
704 SET_ISADDR (IC_RIGHT (ic), 0);
705 SET_ISADDR (IC_RESULT (ic), 0);
708 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
709 operandLitValue (IC_LEFT (ic)) == 0.0)
711 /* left zero turn into an unary minus */
713 IC_LEFT (ic) = IC_RIGHT (ic);
714 IC_RIGHT (ic) = NULL;
718 /* if multiplication then check if either of */
719 /* them is zero then the result is zero */
720 /* if either of them is one then result is */
723 if (IS_OP_LITERAL (IC_LEFT (ic)))
726 if (operandLitValue (IC_LEFT (ic)) == 0.0)
729 IC_RIGHT (ic) = IC_LEFT (ic);
731 SET_RESULT_RIGHT (ic);
734 if (operandLitValue (IC_LEFT (ic)) == 1.0)
738 SET_RESULT_RIGHT (ic);
743 if (IS_OP_LITERAL (IC_RIGHT (ic)))
746 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
750 SET_RESULT_RIGHT (ic);
754 if (operandLitValue (IC_RIGHT (ic)) == 1.0)
757 IC_RIGHT (ic) = IC_LEFT (ic);
759 SET_RESULT_RIGHT (ic);
765 /* if division by self then 1 */
766 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
769 IC_RIGHT (ic) = operandFromLit (1);
771 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
772 IC_RESULT (ic)->isaddr = 0;
774 /* if this is a division then check if right */
775 /* is one then change it to an assignment */
776 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
777 operandLitValue (IC_RIGHT (ic)) == 1.0)
781 IC_RIGHT (ic) = IC_LEFT (ic);
783 SET_RESULT_RIGHT (ic);
787 /* if both are the same for an comparison operators */
791 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
794 IC_RIGHT (ic) = operandFromLit (1);
796 SET_RESULT_RIGHT (ic);
802 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
805 IC_RIGHT (ic) = operandFromLit (0);
807 SET_RESULT_RIGHT (ic);
811 /* if this is a cast of a literal value */
812 if (IS_OP_LITERAL (IC_RIGHT (ic)))
816 operandFromValue (valCastLiteral (operandType (IC_LEFT (ic)),
817 operandLitValue (IC_RIGHT (ic))));
819 SET_ISADDR (IC_RESULT (ic), 0);
821 /* if casting to the same */
822 if (checkType (operandType (IC_RESULT (ic)),
823 operandType (IC_RIGHT (ic))) == 1)
827 SET_ISADDR (IC_RESULT (ic), 0);
831 if (IS_OP_LITERAL (IC_LEFT (ic)))
835 (operandLitValue (IC_LEFT (ic)) == 0 ?
836 operandFromLit (1) : operandFromLit (0));
838 SET_ISADDR (IC_RESULT (ic), 0);
844 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
845 /*-----------------------------------------------------------------*/
846 /* updateSpillLocation - keeps track of register spill location */
847 /*-----------------------------------------------------------------*/
849 updateSpillLocation (iCode * ic)
854 if (POINTER_SET (ic))
860 /* for the form true_symbol := iTempNN */
861 if (ASSIGN_ITEMP_TO_SYM (ic)
862 && !SPIL_LOC (IC_RIGHT (ic)))
865 setype = getSpec (operandType (IC_RESULT (ic)));
867 if (!IC_RIGHT (ic)->noSpilLoc &&
868 !IS_VOLATILE (setype) &&
869 !IN_FARSPACE (SPEC_OCLS (setype)) &&
870 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
872 SPIL_LOC (IC_RIGHT (ic)) =
873 IC_RESULT (ic)->operand.symOperand;
876 if (ASSIGN_ITEMP_TO_ITEMP (ic) &&
877 !SPIL_LOC (IC_RIGHT (ic)) &&
878 !bitVectBitsInCommon (OP_DEFS (IC_RIGHT (ic)), OP_USES (IC_RESULT (ic))) &&
879 OP_SYMBOL (IC_RESULT (ic))->isreqv)
882 setype = getSpec (operandType (IC_RESULT (ic)));
884 if (!IC_RIGHT (ic)->noSpilLoc &&
885 !IS_VOLATILE (setype) &&
886 !IN_FARSPACE (SPEC_OCLS (setype)) &&
887 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
889 SPIL_LOC (IC_RIGHT (ic)) =
890 SPIL_LOC (IC_RESULT (ic));
894 /*-----------------------------------------------------------------*/
895 /* setUsesDef - sets the uses def bitvector for a given operand */
896 /*-----------------------------------------------------------------*/
898 setUsesDefs (operand * op, bitVect * bdefs,
899 bitVect * idefs, bitVect ** oud)
901 /* compute the definitions alive at this point */
902 bitVect *adefs = bitVectUnion (bdefs, idefs);
904 /* of these definitions find the ones that are */
905 /* for this operand */
906 adefs = bitVectIntersect (adefs, OP_DEFS (op));
908 /* these are the definitions that this operand can use */
909 op->usesDefs = adefs;
911 /* the out defs is an union */
912 *oud = bitVectUnion (*oud, adefs);
915 /*-----------------------------------------------------------------*/
916 /* unsetDefsAndUses - clear this operation for the operands */
917 /*-----------------------------------------------------------------*/
919 unsetDefsAndUses (iCode * ic)
921 if (ic->op == JUMPTABLE)
924 /* take away this definition from the def chain of the */
925 /* result & take away from use set of the operands */
928 /* turn off def set */
929 if (IS_SYMOP (IC_RESULT (ic)))
931 if (!POINTER_SET (ic))
932 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
934 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
936 /* turn off the useSet for the operands */
937 if (IS_SYMOP (IC_LEFT (ic)))
938 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
940 if (IS_SYMOP (IC_RIGHT (ic)))
941 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
944 /* must be ifx turn off the use */ if (IS_SYMOP (IC_COND (ic)))
945 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
948 /*-----------------------------------------------------------------*/
949 /* ifxOptimize - changes ifx conditions if it can */
950 /*-----------------------------------------------------------------*/
952 ifxOptimize (iCode * ic, set * cseSet,
954 eBBlock * ebb, int *change,
955 eBBlock ** ebbs, int count)
960 /* if the condition can be replaced */
964 applyToSetFTrue (cseSet, findCheaperOp, IC_COND (ic), &pdop);
972 /* if the conditional is a literal then */
973 if (IS_OP_LITERAL (IC_COND (ic)))
976 if ((operandLitValue (IC_COND (ic)) != 0.0) && IC_TRUE (ic))
979 /* change to a goto */
981 IC_LABEL (ic) = IC_TRUE (ic);
988 if (!operandLitValue (IC_COND (ic)) && IC_FALSE (ic))
991 IC_LABEL (ic) = IC_FALSE (ic);
997 /* then kill this if condition */
998 remiCodeFromeBBlock (ebb, ic);
1002 /* now we need to recompute the control flow */
1003 /* since the control flow has changed */
1004 /* this is very expensive but it does not happen */
1005 /* too often, if it does happen then the user pays */
1007 computeControlFlow (ebbs, count, 1);
1008 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1012 /* if there is only one successor and that successor
1013 is the same one we are conditionally going to then
1014 we can remove this conditional statement */
1015 label = (IC_TRUE (ic) ? IC_TRUE (ic) : IC_FALSE (ic));
1016 if (elementsInSet (ebb->succList) == 1 &&
1017 isinSet (ebb->succList, eBBWithEntryLabel (ebbs, label, count)))
1020 remiCodeFromeBBlock (ebb, ic);
1021 computeControlFlow (ebbs, count, 1);
1022 werror (W_CONTROL_FLOW, ic->filename, ic->lineno);
1027 /* if it remains an IFX the update the use Set */
1028 OP_USES (IC_COND (ic)) = bitVectSetBit (OP_USES (IC_COND (ic)), ic->key);
1029 setUsesDefs (IC_COND (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1033 /*-----------------------------------------------------------------*/
1034 /* diCodeForSym - finds the definiting instruction for a symbol */
1035 /*-----------------------------------------------------------------*/
1036 DEFSETFUNC (diCodeForSym)
1039 V_ARG (operand *, sym);
1040 V_ARG (iCode **, dic);
1042 /* if already found */
1046 /* if not if this is the defining iCode */
1047 if (sym->key == cdp->key)
1056 /*-----------------------------------------------------------------*/
1057 /* constFold - does some constant folding */
1058 /*-----------------------------------------------------------------*/
1060 constFold (iCode * ic, set * cseSet)
1064 /* this routine will change
1070 /* deal with only + & - */
1071 if (ic->op != '+' &&
1075 /* this check is a hueristic to prevent live ranges
1076 from becoming too long */
1077 if (IS_PTR (operandType (IC_RESULT (ic))))
1080 /* check if operation with a literal */
1081 if (!IS_OP_LITERAL (IC_RIGHT (ic)))
1084 /* check if we can find a definition for the
1086 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (ic), &dic)))
1089 /* check that this is also a +/- */
1090 if (dic->op != '+' && dic->op != '-')
1093 /* with a literal */
1094 if (!IS_OP_LITERAL (IC_RIGHT (dic)))
1097 /* find the definition of the left operand
1098 of dic.then check if this defined with a
1099 get_pointer return 0 if the pointer size is
1100 less than 2 (MCS51 specific) */
1101 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (dic), &ldic)))
1104 if (POINTER_GET (ldic) && getSize (operandType (IC_LEFT (ldic))) <= 1)
1107 /* it is if the operations are the same */
1108 /* the literal parts need to be added */
1109 IC_LEFT (ic) = operandFromOperand (IC_LEFT (dic));
1110 if (ic->op == dic->op)
1111 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) +
1112 operandLitValue (IC_RIGHT (dic)));
1114 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) -
1115 operandLitValue (IC_RIGHT (dic)));
1117 if (IS_ITEMP (IC_RESULT (ic)))
1119 SPIL_LOC (IC_RESULT (ic)) = NULL;
1120 IC_RESULT (ic)->noSpilLoc = 1;
1127 /*-----------------------------------------------------------------*/
1128 /* deleteGetPointers - called when a pointer is passed as parm */
1129 /* will delete from cseSet all get pointers computed from this */
1130 /* pointer. A simple ifOperandsHave is not good enough here */
1131 /*-----------------------------------------------------------------*/
1133 deleteGetPointers (set ** cseSet, set ** pss, operand * op, eBBlock * ebb)
1135 set *compItems = NULL;
1140 if (!*cseSet && !*pss)
1143 /* first find all items computed from this operand .
1144 This done fairly simply go thru the list and find
1145 those that are computed by arthimetic with this
1147 for (cdp = setFirstItem (*cseSet); cdp; cdp = setNextItem (*cseSet))
1149 if (IS_ARITHMETIC_OP (cdp->diCode))
1151 if (isOperandEqual (IC_LEFT (cdp->diCode), op) ||
1152 isOperandEqual (IC_RIGHT (cdp->diCode), op))
1154 /* save it in our list of items */
1155 addSet (&compItems, IC_RESULT (cdp->diCode));
1157 /* also check for those computed from our computed
1158 list . This will take care of situations like
1159 iTemp1 = iTemp0 + 8;
1160 iTemp2 = iTemp1 + 8; */
1161 if (isinSetWith (compItems, (void*)IC_LEFT (cdp->diCode),
1162 (void*)isOperandEqual) ||
1163 isinSetWith (compItems, (void*)IC_RIGHT (cdp->diCode),
1164 (void*)isOperandEqual))
1166 addSet (&compItems, IC_RESULT (cdp->diCode));
1171 /* now delete all pointer gets with this op */
1172 deleteItemIf (cseSet, ifPointerGet, op);
1173 deleteItemIf (pss, ifPointerSet, op);
1175 /* set the bit vector used by dataFlow computation later */
1176 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, op->key);
1177 /* now for the computed items */
1178 for (cop = setFirstItem (compItems); cop; cop = setNextItem (compItems))
1180 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, cop->key);
1181 deleteItemIf (cseSet, ifPointerGet, cop);
1182 deleteItemIf (pss, ifPointerSet, cop);
1186 /*-----------------------------------------------------------------*/
1187 /* delGetPointerSucc - delete get pointer from inExprs of succ with */
1188 /* dfnum > supplied */
1189 /*-----------------------------------------------------------------*/
1190 DEFSETFUNC (delGetPointerSucc)
1192 eBBlock *ebp = item;
1193 V_ARG (operand *, op);
1200 if (ebp->dfnum > dfnum)
1202 deleteItemIf (&ebp->inExprs, ifPointerGet, op);
1205 return applyToSet (ebp->succList, delGetPointerSucc, op, dfnum);
1208 /*-----------------------------------------------------------------*/
1209 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1210 /*-----------------------------------------------------------------*/
1212 fixUpTypes (iCode * ic)
1214 sym_link *t1 = operandType (IC_LEFT (ic)), *t2;
1216 if (TARGET_IS_DS390)
1222 /* for pointer_gets if the types of result & left r the
1223 same then change it type of result to next */
1225 checkType (t2 = operandType (IC_RESULT (ic)), t1) == 1)
1227 setOperandType (IC_RESULT (ic), t2->next);
1231 /*-----------------------------------------------------------------*/
1232 /* cseBBlock - common subexpression elimination for basic blocks */
1233 /* this is the hackiest kludgiest routine in the whole */
1234 /* system. also the most important, since almost all */
1235 /* data flow related information is computed by it */
1236 /*-----------------------------------------------------------------*/
1238 cseBBlock (eBBlock * ebb, int computeOnly,
1239 eBBlock ** ebbs, int count)
1245 set *ptrSetSet = NULL;
1247 /* if this block is not reachable */
1251 /* set of common subexpressions */
1252 cseSet = setFromSet (ebb->inExprs);
1254 /* these will be computed by this routine */
1255 setToNull ((void **) &ebb->outDefs);
1256 setToNull ((void **) &ebb->defSet);
1257 setToNull ((void **) &ebb->usesDefs);
1258 setToNull ((void **) &ebb->ptrsSet);
1259 setToNull ((void **) &ebb->addrOf);
1260 setToNull ((void **) &ebb->ldefs);
1262 ebb->outDefs = bitVectCopy (ebb->inDefs);
1263 bitVectDefault = iCodeKey;
1264 ebb->defSet = newBitVect (iCodeKey);
1265 ebb->usesDefs = newBitVect (iCodeKey);
1267 /* for all the instructions in this block do */
1268 for (ic = ebb->sch; ic; ic = ic->next)
1278 /* if this is an assignment from true symbol
1279 to a temp then do pointer post inc/dec optimzation */
1280 if (ic->op == '=' && !POINTER_SET (ic) &&
1281 IS_PTR (operandType (IC_RESULT (ic))))
1283 ptrPostIncDecOpt (ic);
1286 /* clear the def & use chains for the operands involved */
1287 /* in this operation . since it can change due to opts */
1288 unsetDefsAndUses (ic);
1290 if (ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE)
1292 /* add to defSet of the symbol */
1293 OP_DEFS (IC_RESULT (ic)) =
1294 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1295 /* add to the definition set of this block */
1296 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1297 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1298 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1299 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1300 /* delete global variables from the cseSet
1301 since they can be modified by the function call */
1302 deleteItemIf (&cseSet, ifDefGlobal);
1303 /* delete all getpointer iCodes from cseSet, this should
1304 be done only for global arrays & pointers but at this
1305 point we don't know if globals, so to be safe do all */
1306 deleteItemIf (&cseSet, ifAnyGetPointer);
1309 /* for pcall & ipush we need to add to the useSet */
1310 if ((ic->op == PCALL ||
1314 IS_SYMOP (IC_LEFT (ic)))
1317 /* check if they can be replaced */
1321 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1323 IC_LEFT (ic) = pdop;
1325 /* the lookup could have changed it */
1326 if (IS_SYMOP (IC_LEFT (ic)))
1328 OP_USES (IC_LEFT (ic)) =
1329 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1330 setUsesDefs (IC_LEFT (ic), ebb->defSet,
1331 ebb->outDefs, &ebb->usesDefs);
1335 /* if we a sending a pointer as a parameter
1336 then kill all cse since the pointed to item
1337 might be changed in the function being called */
1338 if ((ic->op == IPUSH || ic->op == SEND) &&
1339 IS_PTR (operandType (IC_LEFT (ic))))
1341 deleteGetPointers (&cseSet, &ptrSetSet, IC_LEFT (ic), ebb);
1342 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_LEFT (ic)->key);
1343 for (i = 0; i < count; ebbs[i++]->visited = 0);
1344 applyToSet (ebb->succList, delGetPointerSucc,
1345 IC_LEFT (ic), ebb->dfnum);
1350 /* if jumptable then mark the usage */
1351 if (ic->op == JUMPTABLE)
1353 OP_USES (IC_JTCOND (ic)) =
1354 bitVectSetBit (OP_USES (IC_JTCOND (ic)), ic->key);
1355 setUsesDefs (IC_JTCOND (ic), ebb->defSet,
1356 ebb->outDefs, &ebb->usesDefs);
1363 /* do some algebraic optimizations if possible */
1365 while (constFold (ic, cseSet));
1368 if (POINTER_GET (ic) && !IS_PTR (operandType (IC_LEFT (ic))))
1370 setOperandType (IC_LEFT (ic),
1371 aggrToPtr (operandType (IC_LEFT (ic)), FALSE));
1375 if (POINTER_SET (ic) && !IS_PTR (operandType (IC_RESULT (ic))))
1377 setOperandType (IC_RESULT (ic),
1378 aggrToPtr (operandType (IC_RESULT (ic)), FALSE));
1381 /* if this is a condition statment then */
1382 /* check if the condition can be replaced */
1385 ifxOptimize (ic, cseSet, computeOnly,
1391 /* if the assignment & result is a temp */
1392 /* see if we can replace it */
1396 /* update the spill location for this */
1397 updateSpillLocation (ic);
1399 if (POINTER_SET (ic) &&
1400 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype)))
1403 applyToSetFTrue (cseSet, findCheaperOp, IC_RESULT (ic), &pdop);
1404 if (pdop && IS_ITEMP (pdop) && !computeOnly)
1405 IC_RESULT (ic) = pdop;
1409 /* do the operand lookup i.e. for both the */
1410 /* right & left operand : check the cseSet */
1411 /* to see if they have been replaced if yes */
1412 /* then replace them with those from cseSet */
1414 /* and left is a symbol */
1415 if (IS_SYMOP (IC_LEFT (ic)) &&
1416 !computeOnly && ic->op != ADDRESS_OF)
1420 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop);
1423 if (POINTER_GET (ic))
1425 if (IS_ITEMP (pdop) || IS_OP_LITERAL (pdop))
1427 IC_LEFT (ic) = pdop;
1430 /* check if there is a pointer set
1431 for the same pointer visible if yes
1432 then change this into an assignment */
1434 if (applyToSetFTrue (cseSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic)) &&
1435 !bitVectBitValue (ebb->ptrsSet, pdop->key))
1438 IC_LEFT (ic) = NULL;
1439 IC_RIGHT (ic) = pdop;
1440 SET_ISADDR (IC_RESULT (ic), 0);
1446 IC_LEFT (ic) = pdop;
1453 if (IS_SYMOP (IC_RIGHT (ic)) && !computeOnly)
1457 applyToSetFTrue (cseSet, findCheaperOp, IC_RIGHT (ic), &pdop);
1461 IC_RIGHT (ic) = pdop;
1466 /* if left or right changed then do algebraic */
1470 while (constFold (ic, cseSet));
1473 /* if after all this it becomes a assignment to self
1474 then delete it and continue */
1475 if (ASSIGNMENT_TO_SELF (ic))
1477 remiCodeFromeBBlock (ebb, ic);
1481 /* now we will check to see if the entire */
1482 /* operation has been performed before */
1483 /* and is available */
1484 /* don't do assignments they will be killed */
1485 /* by dead code elimination if required do */
1486 /* it only if result is a temporary */
1488 if (!(POINTER_GET (ic) &&
1489 (IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1490 isOperandVolatile (IC_LEFT (ic), TRUE) ||
1491 bitVectBitValue (ebb->ndompset, IC_LEFT (ic)->key))) &&
1493 IS_ITEMP (IC_RESULT (ic)) &&
1496 applyToSet (cseSet, findPrevIc, ic, &pdic);
1497 if (pdic && checkType (operandType (IC_RESULT (pdic)),
1498 operandType (IC_RESULT (ic))) != 1)
1502 /* if found then eliminate this and add to */
1503 /* to cseSet an element containing result */
1504 /* of this with previous opcode */
1508 if (IS_ITEMP (IC_RESULT (ic)))
1511 /* replace in the remaining of this block */
1512 replaceAllSymBySym (ic->next, IC_RESULT (ic), IC_RESULT (pdic), &ebb->ndompset);
1513 /* remove this iCode from inexpressions of all
1514 its successors, it cannot be in the in expressions
1515 of any of the predecessors */
1516 for (i = 0; i < count; ebbs[i++]->visited = 0);
1517 applyToSet (ebb->succList, removeFromInExprs, ic, IC_RESULT (ic),
1518 IC_RESULT (pdic), ebb);
1520 /* if this was moved from another block */
1521 /* then replace in those blocks too */
1525 for (owner = setFirstItem (ic->movedFrom); owner;
1526 owner = setNextItem (ic->movedFrom))
1527 replaceAllSymBySym (owner->sch, IC_RESULT (ic), IC_RESULT (pdic), &owner->ndompset);
1529 pdic->movedFrom = unionSets (pdic->movedFrom, ic->movedFrom, THROW_NONE);
1532 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), pdic));
1535 /* eliminate this */
1536 remiCodeFromeBBlock (ebb, ic);
1541 if (IS_ITEMP (IC_RESULT (ic)))
1548 /* just add this as a previous expression except in */
1549 /* case of a pointer access in which case this is a */
1550 /* usage not a definition */
1551 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1553 deleteItemIf (&cseSet, ifDefSymIsX, IC_RESULT (ic));
1554 addSetHead (&cseSet, newCseDef (IC_RESULT (ic), ic));
1560 /* if assignment to a parameter which is not
1561 mine and type is a pointer then delete
1562 pointerGets to take care of aliasing */
1563 if (ASSIGNMENT (ic) &&
1564 OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))) &&
1565 IS_PTR (operandType (IC_RESULT (ic))))
1567 deleteGetPointers (&cseSet, &ptrSetSet, IC_RIGHT (ic), ebb);
1568 for (i = 0; i < count; ebbs[i++]->visited = 0);
1569 applyToSet (ebb->succList, delGetPointerSucc, IC_RIGHT (ic), ebb->dfnum);
1570 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RIGHT (ic)->key);
1573 /* if this is a pointerget then see if we can replace
1574 this with a previously assigned pointer value */
1575 if (POINTER_GET (ic) &&
1576 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
1577 isOperandVolatile (IC_LEFT (ic), TRUE)))
1580 applyToSet (ptrSetSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic));
1581 /* if we find it then locally replace all
1582 references to the result with what we assigned */
1585 replaceAllSymBySym (ic->next, IC_RESULT (ic), pdop, &ebb->ndompset);
1589 /* delete from the cseSet anything that has */
1590 /* operands matching the result of this */
1591 /* except in case of pointer access */
1592 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
1594 deleteItemIf (&cseSet, ifOperandsHave, IC_RESULT (ic));
1595 /* delete any previous definitions */
1596 ebb->defSet = bitVectCplAnd (ebb->defSet, OP_DEFS (IC_RESULT (ic)));
1600 /* add the left & right to the defUse set */
1601 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)))
1603 OP_USES (IC_LEFT (ic)) =
1604 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1605 setUsesDefs (IC_LEFT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1609 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)))
1611 OP_USES (IC_RIGHT (ic)) =
1612 bitVectSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1613 setUsesDefs (IC_RIGHT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1617 /* for the result it is special case, put the result */
1618 /* in the defuseSet if it a pointer or array access */
1619 if (POINTER_SET (defic))
1621 OP_USES (IC_RESULT (ic)) =
1622 bitVectSetBit (OP_USES (IC_RESULT (ic)), ic->key);
1623 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1624 deleteItemIf (&cseSet, ifPointerGet, IC_RESULT (ic));
1625 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RESULT (ic)->key);
1626 /* delete from inexpressions of all successors which
1627 have dfNum > than this block */
1628 for (i = 0; i < count; ebbs[i++]->visited = 0);
1629 applyToSet (ebb->succList, delGetPointerSucc, IC_RESULT (ic), ebb->dfnum);
1631 /* delete from cseSet all other pointer sets
1633 deleteItemIf (&ptrSetSet, ifPointerSet, IC_RESULT (ic));
1634 /* add to the local pointerset set */
1635 addSetHead (&ptrSetSet, newCseDef (IC_RESULT (ic), ic));
1638 /* add the result to defintion set */ if (IC_RESULT (ic))
1640 OP_DEFS (IC_RESULT (ic)) =
1641 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1642 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1643 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1644 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1648 /* if this is an addressof instruction then */
1649 /* put the symbol in the address of list & */
1650 /* delete it from the cseSet */
1651 if (defic->op == ADDRESS_OF)
1653 addSetHead (&ebb->addrOf, IC_LEFT (ic));
1654 deleteItemIf (&cseSet, ifDefSymIsX, IC_LEFT (ic));
1658 setToNull ((void **) &ebb->outExprs);
1659 ebb->outExprs = cseSet;
1660 ebb->outDefs = bitVectUnion (ebb->outDefs, ebb->defSet);
1661 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet, ebb->inPtrsSet);
1665 /*-----------------------------------------------------------------*/
1666 /* cseAllBlocks - will sequentially go thru & do cse for all blocks */
1667 /*-----------------------------------------------------------------*/
1669 cseAllBlocks (eBBlock ** ebbs, int count)
1674 /* if optimization turned off */
1676 for (i = 0; i < count; i++)
1677 change += cseBBlock (ebbs[i], FALSE, ebbs, count);