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 -------------------------------------------------------------------------*/
29 /*-----------------------------------------------------------------*/
30 /* newCseDef - new cseDef */
31 /*-----------------------------------------------------------------*/
33 newCseDef (operand * sym, iCode * ic)
38 cdp = Safe_alloc (sizeof (cseDef));
43 cdp->ancestors = newBitVect(iCodeKey);
45 cdp->fromAddrTaken = 0;
47 if (ic->op!=IF && ic->op!=JUMPTABLE)
49 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)))
51 bitVectSetBit (cdp->ancestors, IC_LEFT (ic)->key);
52 cdp->fromGlobal |= isOperandGlobal (IC_LEFT (ic));
53 cdp->fromAddrTaken |= OP_SYMBOL (IC_LEFT (ic))->addrtaken;
55 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)))
57 bitVectSetBit (cdp->ancestors, IC_RIGHT (ic)->key);
58 cdp->fromGlobal |= isOperandGlobal (IC_RIGHT (ic));
59 cdp->fromAddrTaken |= OP_SYMBOL (IC_RIGHT (ic))->addrtaken;
67 updateCseDefAncestors(cseDef *cdp, set * cseSet)
71 iCode *ic = cdp->diCode;
73 if (ic->op!=IF && ic->op!=JUMPTABLE)
75 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)))
77 bitVectSetBit (cdp->ancestors, IC_LEFT (ic)->key);
78 for (sl = cseSet; sl; sl = sl->next)
81 if (loop->sym->key == IC_LEFT (ic)->key)
83 cdp->ancestors = bitVectUnion (cdp->ancestors, loop->ancestors);
84 cdp->fromGlobal |= loop->fromGlobal;
85 cdp->fromAddrTaken |= loop->fromAddrTaken;
90 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)))
92 bitVectSetBit (cdp->ancestors, IC_RIGHT (ic)->key);
93 for (sl = cseSet; sl; sl = sl->next)
96 if (loop->sym->key == IC_RIGHT (ic)->key)
98 cdp->ancestors = bitVectUnion (cdp->ancestors, loop->ancestors);
99 cdp->fromGlobal |= loop->fromGlobal;
100 cdp->fromAddrTaken |= loop->fromAddrTaken;
109 /*-----------------------------------------------------------------*/
110 /* int isCseDefEqual - two definitions are equal */
111 /*-----------------------------------------------------------------*/
113 isCseDefEqual (void *vsrc, void *vdest)
116 cseDef *dest = vdest;
121 return (src->key == dest->key &&
122 src->diCode == dest->diCode);
126 /*-----------------------------------------------------------------*/
127 /* pcseDef - in the cseDef */
128 /*-----------------------------------------------------------------*/
130 pcseDef (void *item, va_list ap)
138 fprintf (stdout, "**null op**");
139 printOperand (cdp->sym, stdout);
140 icTab = getTableEntry (cdp->diCode->op);
141 icTab->iCodePrint (stdout, cdp->diCode, icTab->printName);
145 void ReplaceOpWithCheaperOp(operand **op, operand *cop) {
147 printf ("ReplaceOpWithCheaperOp %s with %s: ",
148 IS_SYMOP((*op)) ? OP_SYMBOL((*op))->name : "!SYM",
149 IS_SYMOP(cop) ? OP_SYMBOL(cop)->name : "!SYM");
150 // if op is a register equivalent
151 if (IS_ITEMP(cop) && OP_SYMBOL((*op))->isreqv) {
152 operand **rop = &OP_SYMBOL((*op))->usl.spillLoc->reqv;
153 if (isOperandEqual(*rop, *op)) {
156 OP_SYMBOL((*op))->isreqv=0;
157 OP_SYMBOL(cop)->isreqv=1;
167 /*-----------------------------------------------------------------*/
168 /* replaceAllSymBySym - replaces all operands by operand in an */
169 /* instruction chain */
170 /*-----------------------------------------------------------------*/
172 replaceAllSymBySym (iCode * ic, operand * from, operand * to, bitVect ** ndpset)
176 for (lic = ic; lic; lic = lic->next)
180 /* do the special cases first */
184 IC_COND (lic)->key == from->key)
187 bitVectUnSetBit (OP_USES (from), lic->key);
188 OP_USES(to)=bitVectSetBit (OP_USES (to), lic->key);
189 siaddr = IC_COND (lic)->isaddr;
190 IC_COND (lic) = operandFromOperand (to);
191 IC_COND (lic)->isaddr = siaddr;
197 if (lic->op == JUMPTABLE)
200 IC_JTCOND (lic)->key == from->key)
203 bitVectUnSetBit (OP_USES (from), lic->key);
204 OP_USES(to)=bitVectSetBit (OP_USES (to), lic->key);
205 siaddr = IC_COND (lic)->isaddr;
206 IC_JTCOND (lic) = operandFromOperand (to);
207 IC_JTCOND (lic)->isaddr = siaddr;
214 IC_RESULT (lic) && IC_RESULT (lic)->key == from->key)
216 /* maintain du chains */
217 if (POINTER_SET (lic))
219 bitVectUnSetBit (OP_USES (from), lic->key);
220 OP_USES(to)=bitVectSetBit (OP_USES (to), lic->key);
222 /* also check if the "from" was in the non-dominating
223 pointer sets and replace it with "to" in the bitVector */
224 if (bitVectBitValue (*ndpset, from->key))
226 bitVectUnSetBit (*ndpset, from->key);
227 bitVectSetBit (*ndpset, to->key);
233 bitVectUnSetBit (OP_DEFS (from), lic->key);
234 OP_DEFS(to)=bitVectSetBit (OP_DEFS (to), lic->key);
236 siaddr = IC_RESULT (lic)->isaddr;
237 IC_RESULT (lic) = operandFromOperand (to);
238 IC_RESULT (lic)->isaddr = siaddr;
242 IC_RIGHT (lic) && IC_RIGHT (lic)->key == from->key)
244 bitVectUnSetBit (OP_USES (from), lic->key);
245 OP_USES(to)=bitVectSetBit (OP_USES (to), lic->key);
246 siaddr = IC_RIGHT (lic)->isaddr;
247 IC_RIGHT (lic) = operandFromOperand (to);
248 IC_RIGHT (lic)->isaddr = siaddr;
252 IC_LEFT (lic) && IC_LEFT (lic)->key == from->key)
254 bitVectUnSetBit (OP_USES (from), lic->key);
255 OP_USES(to)=bitVectSetBit (OP_USES (to), lic->key);
256 siaddr = IC_LEFT (lic)->isaddr;
257 IC_LEFT (lic) = operandFromOperand (to);
258 IC_LEFT (lic)->isaddr = siaddr;
263 /*-----------------------------------------------------------------*/
264 /* iCodeKeyIs - if the icode keys match then return 1 */
265 /*-----------------------------------------------------------------*/
266 DEFSETFUNC (iCodeKeyIs)
271 if (cdp->diCode->key == key)
277 /*-----------------------------------------------------------------*/
278 /* removeFromInExprs - removes an icode from inexpressions */
279 /*-----------------------------------------------------------------*/
280 DEFSETFUNC (removeFromInExprs)
284 V_ARG (operand *, from);
285 V_ARG (operand *, to);
286 V_ARG (eBBlock *, cbp);
292 deleteItemIf (&ebp->inExprs, iCodeKeyIs, ic->key);
293 if (ebp != cbp && !bitVectBitValue (cbp->domVect, ebp->bbnum))
294 replaceAllSymBySym (ebp->sch, from, to, &ebp->ndompset);
296 applyToSet (ebp->succList, removeFromInExprs, ic, from, to, cbp);
300 /*-----------------------------------------------------------------*/
301 /* isGlobalInNearSpace - return TRUE if valriable is a globalin data */
302 /*-----------------------------------------------------------------*/
304 isGlobalInNearSpace (operand * op)
306 sym_link *type = getSpec (operandType (op));
307 /* this is 8051 specific: optimization
308 suggested by Jean-Louis VERN, with 8051s we have no
309 advantage of putting variables in near space into
311 if (isOperandGlobal (op) && !IN_FARSPACE (SPEC_OCLS (type)) &&
312 IN_DIRSPACE (SPEC_OCLS (type)))
318 /*-----------------------------------------------------------------*/
319 /* findCheaperOp - cseBBlock support routine, will check to see if */
320 /* we have a operand previously defined */
321 /*-----------------------------------------------------------------*/
322 DEFSETFUNC (findCheaperOp)
325 V_ARG (operand *, cop);
326 V_ARG (operand **, opp);
327 V_ARG (int, checkSign);
329 /* if we have already found it */
333 /* not found it yet check if this is the one */
334 /* and this is not the defining one */
335 if (cop->key == cdp->key)
338 /* do a special check this will help in */
339 /* constant propagation & dead code elim */
340 /* for assignments only */
341 if (cdp->diCode->op == '=') {
342 /* if the result is volatile then return result */
343 if (IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
344 *opp = IC_RESULT (cdp->diCode);
346 /* if this is a straight assignment and
347 left is a temp then prefer the temporary to the
349 if (!POINTER_SET (cdp->diCode) &&
350 IS_ITEMP (IC_RESULT (cdp->diCode)) &&
351 IS_TRUE_SYMOP (IC_RIGHT (cdp->diCode)))
352 *opp = IC_RESULT (cdp->diCode);
354 /* if straight assignement && and both
355 are temps then prefer the one that
356 will not need extra space to spil, also
357 take into consideration if right side
358 an induction variable
360 if (!POINTER_SET (cdp->diCode) &&
361 IS_ITEMP (IC_RESULT (cdp->diCode)) &&
362 IS_ITEMP (IC_RIGHT (cdp->diCode)) &&
363 !OP_SYMBOL (IC_RIGHT (cdp->diCode))->isind &&
364 !OP_SYMBOL(IC_RIGHT (cdp->diCode))->isreqv &&
365 ((!SPIL_LOC (IC_RIGHT (cdp->diCode)) &&
366 SPIL_LOC (IC_RESULT (cdp->diCode))) ||
367 (SPIL_LOC (IC_RESULT (cdp->diCode)) &&
368 SPIL_LOC (IC_RESULT (cdp->diCode)) ==
369 SPIL_LOC (IC_RIGHT (cdp->diCode)))))
370 *opp = IC_RESULT (cdp->diCode);
372 *opp = IC_RIGHT (cdp->diCode);
376 *opp = IC_RESULT (cdp->diCode);
379 /* if this is an assign to a temp. then check
380 if the right side is this then return this */
381 if (IS_TRUE_SYMOP (cop) &&
382 cdp->diCode->op == '=' &&
383 !POINTER_SET (cdp->diCode) &&
384 cop->key == IC_RIGHT (cdp->diCode)->key &&
385 !isGlobalInNearSpace (IC_RIGHT (cdp->diCode)) &&
386 IS_ITEMP (IC_RESULT (cdp->diCode)))
387 *opp = IC_RESULT (cdp->diCode);
390 (isOperandLiteral(*opp) || !checkSign ||
392 IS_SPEC(operandType (cop)) && IS_SPEC(operandType (*opp)) &&
393 (SPEC_USIGN(operandType (cop))==SPEC_USIGN(operandType (*opp)) &&
394 (SPEC_LONG(operandType (cop))==SPEC_LONG(operandType (*opp)))))))
397 if ((isGlobalInNearSpace (cop) &&
398 !isOperandLiteral (*opp)) ||
399 isOperandVolatile (*opp, FALSE)
406 if (cop->key == (*opp)->key)
412 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP (cop))
414 *opp = operandFromOperand (*opp);
415 (*opp)->isaddr = cop->isaddr;
418 if (IS_SPEC(operandType (cop)) && IS_SPEC(operandType (*opp)) &&
419 SPEC_NOUN(operandType(cop)) != SPEC_NOUN(operandType(*opp)))
421 // special case: we can make an unsigned char literal
422 // into an int literal with no cost.
423 if (isOperandLiteral(*opp)
424 && SPEC_NOUN(operandType(*opp)) == V_CHAR
425 && SPEC_NOUN(operandType(cop)) == V_INT)
427 *opp = operandFromOperand (*opp);
428 SPEC_NOUN(operandType(*opp)) = V_INT;
446 /*-----------------------------------------------------------------*/
447 /* findPointerSet - finds the right side of a pointer set op */
448 /*-----------------------------------------------------------------*/
449 DEFSETFUNC (findPointerSet)
452 V_ARG (operand *, op);
453 V_ARG (operand **, opp);
454 V_ARG (operand *, rop);
456 if (POINTER_SET (cdp->diCode) &&
457 IC_RESULT (cdp->diCode)->key == op->key &&
458 !isOperandVolatile (IC_RESULT (cdp->diCode), TRUE) &&
459 !isOperandVolatile (IC_RIGHT (cdp->diCode), TRUE) &&
460 getSize (operandType (IC_RIGHT (cdp->diCode))) ==
461 getSize (operandType (rop)))
463 *opp = IC_RIGHT (cdp->diCode);
470 /*-----------------------------------------------------------------*/
471 /* findPrevIc - cseBBlock support function will return the iCode */
472 /* which matches the current one */
473 /*-----------------------------------------------------------------*/
474 DEFSETFUNC (findPrevIc)
478 V_ARG (iCode **, icp);
480 /* if already found */
484 /* if the iCodes are the same */
485 if (isiCodeEqual (ic, cdp->diCode) &&
486 isOperandEqual (cdp->sym, IC_RESULT (cdp->diCode)))
492 /* if iCodes are not the same */
493 /* see the operands maybe interchanged */
494 if (ic->op == cdp->diCode->op &&
495 IS_ASSOCIATIVE(ic) &&
496 isOperandEqual (IC_LEFT (ic), IC_RIGHT (cdp->diCode)) &&
497 isOperandEqual (IC_RIGHT (ic), IC_LEFT (cdp->diCode)))
506 /*-------------------------------------------------------------------*/
507 /* ifAssignedFromGlobal - if definition is an assignment from global */
508 /*-------------------------------------------------------------------*/
509 DEFSETFUNC (ifAssignedFromGlobal)
512 iCode *dic=cdp->diCode;
514 if (dic->op=='=' && isOperandGlobal(IC_RIGHT(dic))) {
520 /*-------------------------------------------------------------------*/
521 /* ifFromGlobal - if definition is derived from global */
522 /*-------------------------------------------------------------------*/
523 DEFSETFUNC (ifFromGlobal)
527 return cdp->fromGlobal;
530 /*-----------------------------------------------------------------*/
531 /* ifDefGlobal - if definition is global */
532 /*-----------------------------------------------------------------*/
533 DEFSETFUNC (ifDefGlobal)
537 return (isOperandGlobal (cdp->sym));
540 /*-------------------------------------------------------------------*/
541 /* ifFromAddrTaken - if definition is derived from a symbol whose */
542 /* address was taken */
543 /*-------------------------------------------------------------------*/
544 DEFSETFUNC (ifFromAddrTaken)
548 return cdp->fromAddrTaken;
552 /*-----------------------------------------------------------------*/
553 /* ifAnyGetPointer - if get pointer icode */
554 /*-----------------------------------------------------------------*/
555 DEFSETFUNC (ifAnyGetPointer)
559 if (cdp->diCode && POINTER_GET (cdp->diCode))
564 /*-----------------------------------------------------------------*/
565 /* ifOperandsHave - if any of the operand are the same as this */
566 /*-----------------------------------------------------------------*/
567 DEFSETFUNC (ifOperandsHave)
570 V_ARG (operand *, op);
572 if (bitVectBitValue(cdp->ancestors, op->key))
575 if (IC_LEFT (cdp->diCode) &&
576 IS_SYMOP (IC_LEFT (cdp->diCode)) &&
577 IC_LEFT (cdp->diCode)->key == op->key)
580 if (IC_RIGHT (cdp->diCode) &&
581 IS_SYMOP (IC_RIGHT (cdp->diCode)) &&
582 IC_RIGHT (cdp->diCode)->key == op->key)
585 /* or if any of the operands are volatile */
586 if (IC_LEFT (cdp->diCode) &&
587 IS_OP_VOLATILE (IC_LEFT (cdp->diCode)))
590 if (IC_RIGHT (cdp->diCode) &&
591 IS_OP_VOLATILE (IC_RIGHT (cdp->diCode)))
595 if (IC_RESULT (cdp->diCode) &&
596 IS_OP_VOLATILE (IC_RESULT (cdp->diCode)))
602 /*-----------------------------------------------------------------*/
603 /* ifDefSymIs - if a definition is found in the set */
604 /*-----------------------------------------------------------------*/
606 ifDefSymIs (set * cseSet, operand * sym)
611 if (!sym || !IS_SYMOP (sym))
613 for (sl = cseSet; sl; sl = sl->next)
616 if (loop->sym->key == sym->key)
623 /*-----------------------------------------------------------------*/
624 /* ifDefSymIsX - will return 1 if the symbols match */
625 /*-----------------------------------------------------------------*/
626 DEFSETFUNC (ifDefSymIsX)
629 V_ARG (operand *, op);
633 match = cdp->sym->key == op->key;
635 match = (isOperandEqual (cdp->sym, op));
638 printf("%s ",OP_SYMBOL(cdp->sym)->name);
644 /*-----------------------------------------------------------------*/
645 /* ifDiCodeIs - returns true if diCode is same */
646 /*-----------------------------------------------------------------*/
648 ifDiCodeIs (set * cseSet, iCode * ic)
656 for (sl = cseSet; sl; sl = sl->next)
659 if (loop->diCode == ic)
666 /*-----------------------------------------------------------------*/
667 /* ifPointerGet - returns true if the icode is pointer get sym */
668 /*-----------------------------------------------------------------*/
669 DEFSETFUNC (ifPointerGet)
672 V_ARG (operand *, op);
673 iCode *dic = cdp->diCode;
674 operand *left = IC_LEFT (cdp->diCode);
676 if (POINTER_GET (dic) && left->key == op->key)
682 /*-----------------------------------------------------------------*/
683 /* ifPointerSet - returns true if the icode is pointer set sym */
684 /*-----------------------------------------------------------------*/
685 DEFSETFUNC (ifPointerSet)
688 V_ARG (operand *, op);
690 if (POINTER_SET (cdp->diCode) &&
691 IC_RESULT (cdp->diCode)->key == op->key)
697 /*-----------------------------------------------------------------*/
698 /* ifDiCodeIsX - will return 1 if the symbols match */
699 /*-----------------------------------------------------------------*/
700 DEFSETFUNC (ifDiCodeIsX)
705 return cdp->diCode == ic;
709 /*-----------------------------------------------------------------*/
710 /* findBackwardDef - scan backwards to find deinition of operand */
711 /*-----------------------------------------------------------------*/
712 iCode *findBackwardDef(operand *op,iCode *ic)
716 for (lic = ic; lic ; lic = lic->prev) {
717 if (IC_RESULT(lic) && isOperandEqual(op,IC_RESULT(lic)))
723 /*-----------------------------------------------------------------*/
724 /* algebraicOpts - does some algebraic optimizations */
725 /*-----------------------------------------------------------------*/
727 algebraicOpts (iCode * ic, eBBlock * ebp)
729 /* we don't deal with the following iCodes
740 /* if both operands present & ! IFX */
741 /* then if they are both literal we */
742 /* perform the operation right now */
743 if (IC_RESULT (ic) &&
746 IS_OP_LITERAL (IC_LEFT (ic)) &&
747 IS_OP_LITERAL (IC_RIGHT (ic)))
750 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
753 operandType (IC_RESULT (ic)));
756 SET_RESULT_RIGHT (ic);
760 /* if not ifx & only one operand present */
761 if (IC_RESULT (ic) &&
763 IS_OP_LITERAL (IC_LEFT (ic)) &&
767 IC_RIGHT (ic) = operandOperation (IC_LEFT (ic),
770 operandType (IC_RESULT (ic)));
773 SET_RESULT_RIGHT (ic);
778 /* a special case : or in short a kludgy solution will think
779 about a better solution over a glass of wine someday */
780 if (ic->op == GET_VALUE_AT_ADDRESS)
783 if (IS_ITEMP (IC_RESULT (ic)) &&
784 IS_TRUE_SYMOP (IC_LEFT (ic)))
788 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
789 IC_RIGHT (ic)->isaddr = 0;
791 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
792 IC_RESULT (ic)->isaddr = 0;
793 setOperandType (IC_RESULT (ic), operandType (IC_RIGHT (ic)));
797 if (IS_ITEMP (IC_LEFT (ic)) &&
798 IS_ITEMP (IC_RESULT (ic)) &&
799 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
800 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
801 !IC_LEFT (ic)->isaddr)
804 IC_RIGHT (ic) = operandFromOperand (IC_LEFT (ic));
805 IC_RIGHT (ic)->isaddr = 0;
806 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
807 IC_RESULT (ic)->isaddr = 0;
815 /* depending on the operation */
819 /* if adding the same thing change to left shift by 1 */
820 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key &&
821 !(IS_FLOAT (operandType (IC_RESULT (ic)))
822 || IS_FIXED(operandType (IC_RESULT (ic)))))
825 IC_RIGHT (ic) = operandFromLit (1);
828 /* if addition then check if one of them is a zero */
829 /* if yes turn it into assignmnt or cast */
830 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
831 operandLitValue (IC_LEFT (ic)) == 0.0)
834 typematch = compareType (operandType (IC_RESULT (ic)),
835 operandType (IC_RIGHT (ic)));
839 IC_LEFT (ic) = operandFromLink (operandType (IC_RESULT (ic)));
847 /* for completely different types, preserve the source type */
848 IC_RIGHT (ic) = operandFromOperand (IC_RIGHT (ic));
849 setOperandType (IC_RIGHT (ic), operandType (IC_RESULT (ic)));
852 SET_ISADDR (IC_RESULT (ic), 0);
853 SET_ISADDR (IC_RIGHT (ic), 0);
856 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
857 operandLitValue (IC_RIGHT (ic)) == 0.0)
860 typematch = compareType (operandType (IC_RESULT (ic)),
861 operandType (IC_LEFT (ic)));
865 IC_RIGHT (ic) = IC_LEFT (ic);
866 IC_LEFT (ic) = operandFromLink (operandType (IC_RESULT (ic)));
871 IC_RIGHT (ic) = IC_LEFT (ic);
875 /* for completely different types, preserve the source type */
876 IC_RIGHT (ic) = operandFromOperand (IC_RIGHT (ic));
877 setOperandType (IC_RIGHT (ic), operandType (IC_RESULT (ic)));
880 SET_ISADDR (IC_RIGHT (ic), 0);
881 SET_ISADDR (IC_RESULT (ic), 0);
886 /* if subtracting the the same thing then zero */
887 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
890 IC_RIGHT (ic) = operandFromLit (0);
892 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
893 IC_RESULT (ic)->isaddr = 0;
897 /* if subtraction then check if one of the operand */
898 /* is zero then depending on which operand change */
899 /* to assignment or unary minus */
900 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
901 operandLitValue (IC_RIGHT (ic)) == 0.0)
903 /* right size zero change to assignment */
905 IC_RIGHT (ic) = IC_LEFT (ic);
907 SET_ISADDR (IC_RIGHT (ic), 0);
908 SET_ISADDR (IC_RESULT (ic), 0);
911 if (IS_OP_LITERAL (IC_LEFT (ic)) &&
912 operandLitValue (IC_LEFT (ic)) == 0.0)
914 /* left zero turn into an unary minus */
916 IC_LEFT (ic) = IC_RIGHT (ic);
917 IC_RIGHT (ic) = NULL;
921 /* if multiplication then check if either of */
922 /* them is zero then the result is zero */
923 /* if either of them is one then result is */
926 if (IS_OP_LITERAL (IC_LEFT (ic)))
929 if (operandLitValue (IC_LEFT (ic)) == 0.0)
932 IC_RIGHT (ic) = IC_LEFT (ic);
934 SET_RESULT_RIGHT (ic);
937 if (operandLitValue (IC_LEFT (ic)) == 1.0)
939 /* '*' can have two unsigned chars as operands */
940 /* and an unsigned int as result. */
941 if (compareType (operandType (IC_RESULT (ic)),
942 operandType (IC_RIGHT (ic))) == 1)
946 SET_RESULT_RIGHT (ic);
951 IC_LEFT (ic) = operandFromOperand (IC_LEFT (ic));
952 IC_LEFT (ic)->type = TYPE;
953 IC_LEFT (ic)->isLiteral = 0;
954 setOperandType (IC_LEFT (ic), operandType (IC_RESULT (ic)));
960 if (IS_OP_LITERAL (IC_RIGHT (ic)))
963 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
967 SET_RESULT_RIGHT (ic);
971 if (operandLitValue (IC_RIGHT (ic)) == 1.0)
973 /* '*' can have two unsigned chars as operands */
974 /* and an unsigned int as result. */
975 if (compareType (operandType (IC_RESULT (ic)),
976 operandType (IC_LEFT (ic))) == 1)
979 IC_RIGHT (ic) = IC_LEFT (ic);
981 SET_RESULT_RIGHT (ic);
989 IC_RIGHT (ic) = IC_LEFT (ic);
990 IC_LEFT (ic) = operandFromOperand (op);
991 IC_LEFT (ic)->type = TYPE;
992 IC_LEFT (ic)->isLiteral = 0;
993 setOperandType (IC_LEFT (ic), operandType (IC_RESULT (ic)));
1000 /* if division by self then 1 */
1001 if (IC_LEFT (ic)->key == IC_RIGHT (ic)->key)
1004 IC_RIGHT (ic) = operandFromLit (1);
1005 IC_LEFT (ic) = NULL;
1006 IC_RESULT (ic) = operandFromOperand (IC_RESULT (ic));
1007 IC_RESULT (ic)->isaddr = 0;
1010 /* if this is a division then check if right */
1011 /* is one then change it to an assignment */
1012 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
1013 operandLitValue (IC_RIGHT (ic)) == 1.0)
1017 IC_RIGHT (ic) = IC_LEFT (ic);
1018 IC_LEFT (ic) = NULL;
1019 SET_RESULT_RIGHT (ic);
1023 /* if both are the same for an comparison operators */
1027 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
1030 IC_RIGHT (ic) = operandFromLit (1);
1031 IC_LEFT (ic) = NULL;
1032 SET_RESULT_RIGHT (ic);
1038 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
1041 IC_RIGHT (ic) = operandFromLit (0);
1042 IC_LEFT (ic) = NULL;
1043 SET_RESULT_RIGHT (ic);
1048 sym_link *otype = operandType(IC_RIGHT(ic));
1049 sym_link *ctype = operandType(IC_LEFT(ic));
1050 /* if this is a cast of a literal value */
1051 if (IS_OP_LITERAL (IC_RIGHT (ic)) &&
1052 !(IS_GENPTR(ctype) && (IS_PTR(otype) && !IS_GENPTR(otype)))) {
1055 operandFromValue (valCastLiteral (operandType (IC_LEFT (ic)),
1056 operandLitValue (IC_RIGHT (ic))));
1057 IC_LEFT (ic) = NULL;
1058 SET_ISADDR (IC_RESULT (ic), 0);
1060 /* if casting to the same */
1061 if (compareType (operandType (IC_RESULT (ic)),
1062 operandType (IC_RIGHT (ic))) == 1) {
1064 IC_LEFT (ic) = NULL;
1065 SET_ISADDR (IC_RESULT (ic), 0);
1070 if (IS_OP_LITERAL (IC_LEFT (ic)))
1074 (operandLitValue (IC_LEFT (ic)) == 0 ?
1075 operandFromLit (1) : operandFromLit (0));
1076 IC_LEFT (ic) = NULL;
1077 SET_ISADDR (IC_RESULT (ic), 0);
1081 /* if both operands are equal */
1082 /* if yes turn it into assignment */
1083 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
1085 if (IS_OP_VOLATILE (IC_LEFT (ic)))
1087 iCode *newic = newiCode (DUMMY_READ_VOLATILE, NULL, IC_LEFT (ic));
1088 IC_RESULT (newic) = IC_LEFT (ic);
1089 newic->lineno = ic->lineno;
1090 addiCodeToeBBlock (ebp, newic, ic->next);
1093 IC_LEFT (ic) = NULL;
1094 SET_RESULT_RIGHT (ic);
1097 /* swap literal to right ic */
1098 if (IS_OP_LITERAL (IC_LEFT (ic)))
1103 IC_LEFT (ic) = IC_RIGHT (ic);
1106 if (IS_OP_LITERAL (IC_RIGHT (ic)))
1108 /* if BITWISEAND then check if one of them is a zero */
1109 /* if yes turn it into 0 assignment */
1110 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
1112 if (IS_OP_VOLATILE (IC_LEFT (ic)))
1114 iCode *newic = newiCode (DUMMY_READ_VOLATILE, NULL, IC_LEFT (ic));
1115 IC_RESULT (newic) = IC_LEFT (ic);
1116 newic->lineno = ic->lineno;
1117 addiCodeToeBBlock (ebp, newic, ic->next);
1120 IC_LEFT (ic) = NULL;
1121 SET_RESULT_RIGHT (ic);
1124 /* if BITWISEAND then check if one of them is 0xff... */
1125 /* if yes turn it into assignment */
1129 switch (getSize (operandType (IC_RIGHT (ic))))
1143 if (((unsigned) operandLitValue (IC_RIGHT (ic)) & val) == val)
1146 IC_RIGHT (ic) = IC_LEFT (ic);
1147 IC_LEFT (ic) = NULL;
1148 SET_RESULT_RIGHT (ic);
1155 /* if both operands are equal */
1156 /* if yes turn it into assignment */
1157 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
1159 if (IS_OP_VOLATILE (IC_LEFT (ic)))
1161 iCode *newic = newiCode (DUMMY_READ_VOLATILE, NULL, IC_LEFT (ic));
1162 IC_RESULT (newic) = IC_LEFT (ic);
1163 newic->lineno = ic->lineno;
1164 addiCodeToeBBlock (ebp, newic, ic->next);
1167 IC_LEFT (ic) = NULL;
1168 SET_RESULT_RIGHT (ic);
1171 /* swap literal to right ic */
1172 if (IS_OP_LITERAL (IC_LEFT (ic)))
1177 IC_LEFT (ic) = IC_RIGHT (ic);
1180 if (IS_OP_LITERAL (IC_RIGHT (ic)))
1182 /* if BITWISEOR then check if one of them is a zero */
1183 /* if yes turn it into assignment */
1184 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
1187 IC_RIGHT (ic) = IC_LEFT (ic);
1188 IC_LEFT (ic) = NULL;
1189 SET_RESULT_RIGHT (ic);
1192 /* if BITWISEOR then check if one of them is 0xff... */
1193 /* if yes turn it into 0xff... assignment */
1197 switch (getSize (operandType (IC_RIGHT (ic))))
1211 if (((unsigned) operandLitValue (IC_RIGHT (ic)) & val) == val)
1213 if (IS_OP_VOLATILE (IC_LEFT (ic)))
1215 iCode *newic = newiCode (DUMMY_READ_VOLATILE, NULL, IC_LEFT (ic));
1216 IC_RESULT (newic) = IC_LEFT (ic);
1217 newic->lineno = ic->lineno;
1218 addiCodeToeBBlock (ebp, newic, ic->next);
1221 IC_LEFT (ic) = NULL;
1222 SET_RESULT_RIGHT (ic);
1229 /* if both operands are equal */
1230 /* if yes turn it into 0 assignment */
1231 if (isOperandEqual (IC_LEFT (ic), IC_RIGHT (ic)))
1233 if (IS_OP_VOLATILE (IC_LEFT (ic)))
1235 iCode *newic = newiCode (DUMMY_READ_VOLATILE, NULL, IC_LEFT (ic));
1236 IC_RESULT (newic) = IC_LEFT (ic);
1237 newic->lineno = ic->lineno;
1238 addiCodeToeBBlock (ebp, newic, ic->next);
1240 newic = newiCode (DUMMY_READ_VOLATILE, NULL, IC_LEFT (ic));
1241 IC_RESULT (newic) = IC_LEFT (ic);
1242 newic->lineno = ic->lineno;
1243 addiCodeToeBBlock (ebp, newic, ic->next);
1246 IC_RIGHT (ic) = operandFromLit (0);
1247 IC_LEFT (ic) = NULL;
1248 SET_RESULT_RIGHT (ic);
1251 /* swap literal to right ic */
1252 if (IS_OP_LITERAL (IC_LEFT (ic)))
1257 IC_LEFT (ic) = IC_RIGHT (ic);
1260 /* if XOR then check if one of them is a zero */
1261 /* if yes turn it into assignment */
1262 if (IS_OP_LITERAL (IC_RIGHT (ic)))
1264 if (operandLitValue (IC_RIGHT (ic)) == 0.0)
1267 IC_RIGHT (ic) = IC_LEFT (ic);
1268 IC_LEFT (ic) = NULL;
1269 SET_RESULT_RIGHT (ic);
1278 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
1279 /*-----------------------------------------------------------------*/
1280 /* updateSpillLocation - keeps track of register spill location */
1281 /*-----------------------------------------------------------------*/
1283 updateSpillLocation (iCode * ic, int induction)
1287 if (POINTER_SET (ic))
1294 /* for the form true_symbol := iTempNN */
1295 if (ASSIGN_ITEMP_TO_SYM (ic) &&
1296 !SPIL_LOC (IC_RIGHT (ic))) {
1298 setype = getSpec (operandType (IC_RESULT (ic)));
1300 if (!OP_SYMBOL(IC_RIGHT (ic))->noSpilLoc &&
1301 !IS_VOLATILE (setype) &&
1302 !IN_FARSPACE (SPEC_OCLS (setype)) &&
1303 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))))
1305 wassert(IS_SYMOP(IC_RESULT (ic)));
1306 wassert(IS_SYMOP(IC_RIGHT (ic)));
1307 SPIL_LOC (IC_RIGHT (ic)) =
1308 IC_RESULT (ic)->operand.symOperand;
1314 #if 0 /* this needs furthur investigation can save a lot of code */
1315 if (ASSIGN_SYM_TO_ITEMP(ic) &&
1316 !SPIL_LOC(IC_RESULT(ic))) {
1317 if (!OTHERS_PARM (OP_SYMBOL (IC_RIGHT (ic))))
1318 SPIL_LOC (IC_RESULT (ic)) =
1319 IC_RIGHT (ic)->operand.symOperand;
1322 if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
1324 if (!SPIL_LOC (IC_RIGHT (ic)) &&
1325 !bitVectBitsInCommon (OP_DEFS (IC_RIGHT (ic)), OP_USES (IC_RESULT (ic))) &&
1326 OP_SYMBOL (IC_RESULT (ic))->isreqv) {
1328 setype = getSpec (operandType (IC_RESULT (ic)));
1330 if (!OP_SYMBOL(IC_RIGHT (ic))->noSpilLoc &&
1331 !IS_VOLATILE (setype) &&
1332 !IN_FARSPACE (SPEC_OCLS (setype)) &&
1333 !OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic)))) {
1335 SPIL_LOC (IC_RIGHT (ic)) =
1336 SPIL_LOC (IC_RESULT (ic));
1337 OP_SYMBOL (IC_RIGHT (ic))->prereqv =
1338 OP_SYMBOL (IC_RESULT (ic))->prereqv;
1341 /* special case for inductions */
1343 OP_SYMBOL(IC_RIGHT(ic))->isreqv &&
1344 !OP_SYMBOL(IC_RESULT (ic))->noSpilLoc &&
1345 !SPIL_LOC(IC_RESULT(ic))) {
1346 SPIL_LOC (IC_RESULT (ic)) = SPIL_LOC (IC_RIGHT (ic));
1347 OP_SYMBOL (IC_RESULT (ic))->prereqv =
1348 OP_SYMBOL (IC_RIGHT (ic))->prereqv;
1352 /*-----------------------------------------------------------------*/
1353 /* setUsesDef - sets the uses def bitvector for a given operand */
1354 /*-----------------------------------------------------------------*/
1356 setUsesDefs (operand * op, bitVect * bdefs,
1357 bitVect * idefs, bitVect ** oud)
1359 /* compute the definitions alive at this point */
1360 bitVect *adefs = bitVectUnion (bdefs, idefs);
1362 /* of these definitions find the ones that are */
1363 /* for this operand */
1364 adefs = bitVectIntersect (adefs, OP_DEFS (op));
1366 /* these are the definitions that this operand can use */
1367 op->usesDefs = adefs;
1369 /* the out defs is an union */
1370 *oud = bitVectUnion (*oud, adefs);
1373 /*-----------------------------------------------------------------*/
1374 /* unsetDefsAndUses - clear this operation for the operands */
1375 /*-----------------------------------------------------------------*/
1377 unsetDefsAndUses (iCode * ic)
1379 if (ic->op == JUMPTABLE)
1382 /* take away this definition from the def chain of the */
1383 /* result & take away from use set of the operands */
1386 /* turn off def set */
1387 if (IS_SYMOP (IC_RESULT (ic)))
1389 if (!POINTER_SET (ic))
1390 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1392 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
1394 /* turn off the useSet for the operands */
1395 if (IS_SYMOP (IC_LEFT (ic)))
1396 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1398 if (IS_SYMOP (IC_RIGHT (ic)))
1399 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1402 /* must be ifx turn off the use */ if (IS_SYMOP (IC_COND (ic)))
1403 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
1406 /*-----------------------------------------------------------------*/
1407 /* ifxOptimize - changes ifx conditions if it can */
1408 /*-----------------------------------------------------------------*/
1410 ifxOptimize (iCode * ic, set * cseSet,
1412 eBBlock * ebb, int *change,
1418 /* if the condition can be replaced */
1422 applyToSetFTrue (cseSet, findCheaperOp, IC_COND (ic), &pdop, 0);
1425 ReplaceOpWithCheaperOp(&IC_COND (ic), pdop);
1430 /* if the conditional is a literal then */
1431 if (IS_OP_LITERAL (IC_COND (ic)))
1434 if ((operandLitValue (IC_COND (ic)) != 0.0) && IC_TRUE (ic))
1437 /* change to a goto */
1439 IC_LABEL (ic) = IC_TRUE (ic);
1446 if (!operandLitValue (IC_COND (ic)) && IC_FALSE (ic))
1449 IC_LABEL (ic) = IC_FALSE (ic);
1455 /* then kill this if condition */
1456 remiCodeFromeBBlock (ebb, ic);
1460 /* now we need to recompute the control flow */
1461 /* since the control flow has changed */
1462 /* this is very expensive but it does not happen */
1463 /* too often, if it does happen then the user pays */
1465 computeControlFlow (ebbi);
1466 if (!options.lessPedantic) {
1467 werrorfl (ic->filename, ic->lineno, W_CONTROL_FLOW);
1472 /* if there is only one successor and that successor
1473 is the same one we are conditionally going to then
1474 we can remove this conditional statement */
1475 label = (IC_TRUE (ic) ? IC_TRUE (ic) : IC_FALSE (ic));
1476 if (elementsInSet (ebb->succList) == 1 &&
1477 isinSet (ebb->succList, eBBWithEntryLabel (ebbi, label)))
1480 if (!options.lessPedantic) {
1481 werrorfl (ic->filename, ic->lineno, W_CONTROL_FLOW);
1483 if (IS_OP_VOLATILE (IC_COND (ic)))
1485 IC_RIGHT (ic) = IC_COND (ic);
1486 IC_LEFT (ic) = NULL;
1487 IC_RESULT (ic) = NULL;
1488 ic->op = DUMMY_READ_VOLATILE;
1492 remiCodeFromeBBlock (ebb, ic);
1493 computeControlFlow (ebbi);
1499 /* if it remains an IFX the update the use Set */
1502 OP_USES(IC_COND (ic))=bitVectSetBit (OP_USES (IC_COND (ic)), ic->key);
1503 setUsesDefs (IC_COND (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1505 else if (ic->op == DUMMY_READ_VOLATILE)
1507 OP_USES(IC_RIGHT (ic))=bitVectSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1508 setUsesDefs (IC_RIGHT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1513 /*-----------------------------------------------------------------*/
1514 /* diCodeForSym - finds the definiting instruction for a symbol */
1515 /*-----------------------------------------------------------------*/
1516 DEFSETFUNC (diCodeForSym)
1519 V_ARG (operand *, sym);
1520 V_ARG (iCode **, dic);
1522 /* if already found */
1526 /* if not if this is the defining iCode */
1527 if (sym->key == cdp->key)
1536 /*-----------------------------------------------------------------*/
1537 /* constFold - does some constant folding */
1538 /*-----------------------------------------------------------------*/
1540 constFold (iCode * ic, set * cseSet)
1544 /* this routine will change
1550 /* deal with only + & - */
1551 if (ic->op != '+' &&
1555 /* this check is a heuristic to prevent live ranges
1556 from becoming too long */
1557 if (IS_PTR (operandType (IC_RESULT (ic))))
1560 /* check if operation with a literal */
1561 if (!IS_OP_LITERAL (IC_RIGHT (ic)))
1564 /* check if we can find a definition for the
1566 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (ic), &dic)))
1569 /* check that this is also a +/- */
1570 if (dic->op != '+' && dic->op != '-')
1573 /* with a literal */
1574 if (!IS_OP_LITERAL (IC_RIGHT (dic)))
1577 /* find the definition of the left operand
1578 of dic.then check if this defined with a
1579 get_pointer return 0 if the pointer size is
1580 less than 2 (MCS51 specific) */
1581 if (!(applyToSet (cseSet, diCodeForSym, IC_LEFT (dic), &ldic)))
1584 if (POINTER_GET (ldic) && getSize (operandType (IC_LEFT (ldic))) <= 1)
1587 /* it is if the operations are the same */
1588 /* the literal parts need to be added */
1589 IC_LEFT (ic) = operandFromOperand (IC_LEFT (dic));
1590 if (ic->op == dic->op)
1591 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) +
1592 operandLitValue (IC_RIGHT (dic)));
1594 IC_RIGHT (ic) = operandFromLit (operandLitValue (IC_RIGHT (ic)) -
1595 operandLitValue (IC_RIGHT (dic)));
1597 if (IS_ITEMP (IC_RESULT (ic)))
1599 SPIL_LOC (IC_RESULT (ic)) = NULL;
1600 OP_SYMBOL(IC_RESULT (ic))->noSpilLoc = 1;
1607 /*-----------------------------------------------------------------*/
1608 /* deleteGetPointers - called when a pointer is passed as parm */
1609 /* will delete from cseSet all get pointers computed from this */
1610 /* pointer. A simple ifOperandsHave is not good enough here */
1611 /*-----------------------------------------------------------------*/
1613 deleteGetPointers (set ** cseSet, set ** pss, operand * op, eBBlock * ebb)
1615 set *compItems = NULL;
1621 if (!*cseSet && !*pss)
1624 addSet (&compItems, op);
1626 /* Recursively find all items computed from this operand .
1627 This done fairly simply go thru the list and find
1628 those that are computed by arthimetic with these
1630 /* Also check for those computed from our computed
1631 list . This will take care of situations like
1632 iTemp1 = iTemp0 + 8;
1633 iTemp2 = iTemp1 + 8; */
1637 for (cdp = setFirstItem (*cseSet); cdp; cdp = setNextItem (*cseSet))
1639 if (IS_ARITHMETIC_OP (cdp->diCode) || POINTER_GET(cdp->diCode))
1641 if (isinSetWith (compItems, (void*)IC_LEFT (cdp->diCode),
1642 (insetwithFunc)isOperandEqual) ||
1643 isinSetWith (compItems, (void*)IC_RIGHT (cdp->diCode),
1644 (insetwithFunc)isOperandEqual))
1646 if (!isinSetWith (compItems, (void*)IC_RESULT (cdp->diCode),
1647 (insetwithFunc)isOperandEqual))
1649 addSet (&compItems, IC_RESULT (cdp->diCode));
1658 /* now for the computed items */
1659 for (cop = setFirstItem (compItems); cop; cop = setNextItem (compItems))
1661 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, cop->key);
1662 deleteItemIf (cseSet, ifPointerGet, cop);
1663 deleteItemIf (cseSet, ifDefSymIsX, cop);
1664 deleteItemIf (pss, ifPointerSet, cop);
1668 /*-----------------------------------------------------------------*/
1669 /* delGetPointerSucc - delete get pointer from inExprs of succ with */
1670 /* dfnum > supplied */
1671 /*-----------------------------------------------------------------*/
1672 DEFSETFUNC (delGetPointerSucc)
1674 eBBlock *ebp = item;
1675 V_ARG (operand *, op);
1682 if (ebp->dfnum > dfnum)
1684 deleteItemIf (&ebp->inExprs, ifPointerGet, op);
1687 return applyToSet (ebp->succList, delGetPointerSucc, op, dfnum);
1690 /*-----------------------------------------------------------------*/
1691 /* fixUpTypes - KLUGE HACK fixup a lowering problem */
1692 /*-----------------------------------------------------------------*/
1694 fixUpTypes (iCode * ic)
1696 sym_link *t1 = operandType (IC_LEFT (ic)), *t2;
1698 /* if (TARGET_IS_DS390) */
1699 if (options.model == MODEL_FLAT24)
1705 /* for pointer_gets if the types of result & left r the
1706 same then change it type of result to next */
1708 compareType (t2 = operandType (IC_RESULT (ic)), t1) == 1)
1710 setOperandType (IC_RESULT (ic), t2->next);
1714 /*-----------------------------------------------------------------*/
1715 /* isSignedOp - will return 1 if sign is important to operation */
1716 /*-----------------------------------------------------------------*/
1717 static int isSignedOp (iCode *ic)
1738 case GET_VALUE_AT_ADDRESS:
1769 dumpCseSet(set *cseSet)
1773 cseDef *item=cseSet->item;
1775 printOperand (item->sym, NULL);
1777 piCode (item->diCode, NULL);
1778 cseSet = cseSet->next;
1783 /*-----------------------------------------------------------------*/
1784 /* cseBBlock - common subexpression elimination for basic blocks */
1785 /* this is the hackiest kludgiest routine in the whole */
1786 /* system. also the most important, since almost all */
1787 /* data flow related information is computed by it */
1788 /*-----------------------------------------------------------------*/
1790 cseBBlock (eBBlock * ebb, int computeOnly,
1793 eBBlock ** ebbs = ebbi->bbOrder;
1794 int count = ebbi->count;
1799 set *ptrSetSet = NULL;
1802 /* if this block is not reachable */
1806 /* set of common subexpressions */
1807 cseSet = setFromSet (ebb->inExprs);
1809 /* these will be computed by this routine */
1810 setToNull ((void *) &ebb->outDefs);
1811 setToNull ((void *) &ebb->defSet);
1812 setToNull ((void *) &ebb->usesDefs);
1813 setToNull ((void *) &ebb->ptrsSet);
1814 setToNull ((void *) &ebb->addrOf);
1815 setToNull ((void *) &ebb->ldefs);
1817 ebb->outDefs = bitVectCopy (ebb->inDefs);
1818 bitVectDefault = iCodeKey;
1819 ebb->defSet = newBitVect (iCodeKey);
1820 ebb->usesDefs = newBitVect (iCodeKey);
1822 /* for all the instructions in this block do */
1823 for (ic = ebb->sch; ic; ic = ic->next)
1830 ic->eBBlockNum = ebb->bbnum;
1835 /* if this is an assignment from true symbol
1836 to a temp then do pointer post inc/dec optimzation */
1837 if (ic->op == '=' && !POINTER_SET (ic) &&
1838 IS_PTR (operandType (IC_RESULT (ic))))
1840 ptrPostIncDecOpt (ic);
1843 /* clear the def & use chains for the operands involved */
1844 /* in this operation . since it can change due to opts */
1845 unsetDefsAndUses (ic);
1847 if (ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE)
1849 /* add to defSet of the symbol */
1850 OP_DEFS(IC_RESULT (ic))=
1851 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1852 /* add to the definition set of this block */
1853 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
1854 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
1855 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
1856 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
1857 /* delete global variables from the cseSet
1858 since they can be modified by the function call */
1859 deleteItemIf (&cseSet, ifDefGlobal);
1861 /* and also iTemps derived from globals */
1862 deleteItemIf (&cseSet, ifFromGlobal);
1864 /* Delete iTemps derived from symbols whose address */
1865 /* has been taken */
1866 deleteItemIf (&cseSet, ifFromAddrTaken);
1868 /* delete all getpointer iCodes from cseSet, this should
1869 be done only for global arrays & pointers but at this
1870 point we don't know if globals, so to be safe do all */
1871 deleteItemIf (&cseSet, ifAnyGetPointer);
1873 /* can't cache pointer set/get operations across a call */
1874 deleteSet (&ptrSetSet);
1877 /* for pcall & ipush we need to add to the useSet */
1878 if ((ic->op == PCALL ||
1882 IS_SYMOP (IC_LEFT (ic)))
1885 /* check if they can be replaced */
1889 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop, 0);
1891 ReplaceOpWithCheaperOp(&IC_LEFT(ic), pdop);
1893 /* the lookup could have changed it */
1894 if (IS_SYMOP (IC_LEFT (ic)))
1896 OP_USES(IC_LEFT (ic))=
1897 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1898 setUsesDefs (IC_LEFT (ic), ebb->defSet,
1899 ebb->outDefs, &ebb->usesDefs);
1903 /* if we a sending a pointer as a parameter
1904 then kill all cse since the pointed to item
1905 might be changed in the function being called */
1906 if ((ic->op == IPUSH || ic->op == SEND) &&
1907 IS_PTR (operandType (IC_LEFT (ic))))
1909 deleteGetPointers (&cseSet, &ptrSetSet, IC_LEFT (ic), ebb);
1910 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_LEFT (ic)->key);
1911 for (i = 0; i < count; ebbs[i++]->visited = 0);
1912 applyToSet (ebb->succList, delGetPointerSucc,
1913 IC_LEFT (ic), ebb->dfnum);
1918 /* if jumptable then mark the usage */
1919 if (ic->op == JUMPTABLE)
1921 if (IS_SYMOP (IC_JTCOND (ic)))
1923 OP_USES(IC_JTCOND (ic)) =
1924 bitVectSetBit (OP_USES (IC_JTCOND (ic)), ic->key);
1925 setUsesDefs (IC_JTCOND (ic), ebb->defSet,
1926 ebb->outDefs, &ebb->usesDefs);
1936 /* do some algebraic optimizations if possible */
1937 algebraicOpts (ic, ebb);
1938 while (constFold (ic, cseSet));
1942 if (POINTER_GET (ic))
1944 if (!IS_PTR (operandType (IC_LEFT (ic))))
1946 setOperandType (IC_LEFT (ic),
1947 aggrToPtr (operandType (IC_LEFT (ic)), FALSE));
1948 IC_LEFT (ic)->aggr2ptr = 0;
1951 else if (IC_LEFT (ic)->aggr2ptr)
1952 {/* band aid for kludge */
1953 setOperandType (IC_LEFT (ic),
1954 aggrToPtr (operandType (IC_LEFT (ic)), TRUE));
1955 IC_LEFT (ic)->aggr2ptr = 0;
1960 if (POINTER_SET (ic))
1962 if (!IS_PTR (operandType (IC_RESULT (ic))))
1964 setOperandType (IC_RESULT (ic),
1965 aggrToPtr (operandType (IC_RESULT (ic)), FALSE));
1966 IC_RESULT (ic)->aggr2ptr = 0;
1968 else if (IC_RESULT (ic)->aggr2ptr)
1969 {/* band aid for kludge */
1970 setOperandType (IC_RESULT (ic),
1971 aggrToPtr (operandType (IC_RESULT (ic)), TRUE));
1972 IC_RESULT (ic)->aggr2ptr = 0;
1976 /* if this is a condition statement then */
1977 /* check if the condition can be replaced */
1980 ifxOptimize (ic, cseSet, computeOnly,
1986 /* if the assignment & result is a temp */
1987 /* see if we can replace it */
1988 if (!computeOnly && ic->op == '=')
1991 /* update the spill location for this */
1992 updateSpillLocation (ic,0);
1994 if (POINTER_SET (ic) &&
1995 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype)))
1998 applyToSetFTrue (cseSet, findCheaperOp, IC_RESULT (ic), &pdop, 0);
1999 if (pdop && !computeOnly && IS_ITEMP (pdop))
2001 ReplaceOpWithCheaperOp (&IC_RESULT(ic), pdop);
2002 if (!IS_PTR (operandType (IC_RESULT (ic))))
2004 setOperandType (IC_RESULT (ic),
2005 aggrToPtr (operandType (IC_RESULT (ic)), FALSE));
2011 checkSign = isSignedOp(ic);
2013 /* do the operand lookup i.e. for both the */
2014 /* right & left operand : check the cseSet */
2015 /* to see if they have been replaced if yes */
2016 /* then replace them with those from cseSet */
2018 /* and left is a symbol */
2019 if (IS_SYMOP (IC_LEFT (ic)) &&
2020 !IS_BITFIELD (OP_SYM_ETYPE (IC_LEFT (ic))) &&
2021 !computeOnly && ic->op != ADDRESS_OF)
2025 applyToSetFTrue (cseSet, findCheaperOp, IC_LEFT (ic), &pdop, checkSign);
2028 if (POINTER_GET (ic))
2030 if (IS_ITEMP (pdop) || IS_OP_LITERAL (pdop))
2032 /* some non dominating block does POINTER_SET with
2033 this variable .. unsafe to remove any POINTER_GETs */
2034 if (bitVectBitValue(ebb->ndompset,IC_LEFT(ic)->key))
2035 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,pdop->key);
2036 ReplaceOpWithCheaperOp(&IC_LEFT(ic), pdop);
2039 /* check if there is a pointer set
2040 for the same pointer visible if yes
2041 then change this into an assignment */
2043 if (applyToSetFTrue (cseSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic)) &&
2044 !bitVectBitValue (ebb->ptrsSet, pdop->key))
2047 IC_LEFT (ic) = NULL;
2048 ReplaceOpWithCheaperOp(&IC_RIGHT(ic), pdop);
2049 SET_ISADDR (IC_RESULT (ic), 0);
2055 ReplaceOpWithCheaperOp(&IC_LEFT(ic), pdop);
2062 if (IS_SYMOP (IC_RIGHT (ic)) && !computeOnly)
2066 applyToSetFTrue (cseSet, findCheaperOp, IC_RIGHT (ic), &pdop, checkSign);
2068 ReplaceOpWithCheaperOp(&IC_RIGHT(ic), pdop);
2073 /* if left or right changed then do algebraic */
2074 if (!computeOnly && change)
2076 algebraicOpts (ic, ebb);
2077 while (constFold (ic, cseSet));
2080 /* if after all this it becomes an assignment to self
2081 then delete it and continue */
2082 if (ASSIGNMENT_TO_SELF (ic) && !isOperandVolatile (IC_RIGHT(ic), FALSE))
2084 remiCodeFromeBBlock (ebb, ic);
2088 /* now we will check to see if the entire */
2089 /* operation has been performed before */
2090 /* and is available */
2091 /* don't do assignments they will be killed */
2092 /* by dead code elimination if required do */
2093 /* it only if result is a temporary */
2095 if (!(POINTER_GET (ic) &&
2096 (IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
2097 isOperandVolatile (IC_LEFT (ic), TRUE) ||
2098 bitVectBitValue (ebb->ndompset, IC_LEFT (ic)->key))) &&
2100 IS_ITEMP (IC_RESULT (ic)) &&
2103 applyToSet (cseSet, findPrevIc, ic, &pdic);
2104 if (pdic && compareType (operandType (IC_RESULT (pdic)),
2105 operandType (IC_RESULT (ic))) != 1)
2107 if (pdic && port->cseOk && (*port->cseOk)(ic,pdic) == 0)
2111 /* Alternate code */
2112 if (pdic && IS_ITEMP(IC_RESULT(ic))) {
2113 if (POINTER_GET(ic) && bitVectBitValue(ebb->ptrsSet,IC_LEFT(ic)->key)) {
2114 /* Mmm, found an equivalent pointer get at a lower level.
2115 This could be a loop however with the same pointer set
2118 /* if previous definition found change this to an assignment */
2121 IC_RIGHT(ic) = operandFromOperand(IC_RESULT(pdic));
2122 SET_ISADDR(IC_RESULT(ic),0);
2123 SET_ISADDR(IC_RIGHT (ic),0);
2127 if (!(POINTER_SET (ic)) && IC_RESULT (ic)) {
2129 deleteItemIf (&cseSet, ifDefSymIsX, IC_RESULT (ic));
2130 csed = newCseDef (IC_RESULT (ic), ic);
2131 updateCseDefAncestors (csed, cseSet);
2132 addSetHead (&cseSet, csed);
2136 /* if assignment to a parameter which is not
2137 mine and type is a pointer then delete
2138 pointerGets to take care of aliasing */
2139 if (ASSIGNMENT (ic) &&
2140 OTHERS_PARM (OP_SYMBOL (IC_RESULT (ic))) &&
2141 IS_PTR (operandType (IC_RESULT (ic))))
2143 deleteGetPointers (&cseSet, &ptrSetSet, IC_RIGHT (ic), ebb);
2144 for (i = 0; i < count; ebbs[i++]->visited = 0);
2145 applyToSet (ebb->succList, delGetPointerSucc, IC_RIGHT (ic), ebb->dfnum);
2146 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RIGHT (ic)->key);
2149 /* if this is a pointerget then see if we can replace
2150 this with a previously assigned pointer value */
2151 if (POINTER_GET (ic) &&
2152 !(IS_BITFIELD (OP_SYMBOL (IC_RESULT (ic))->etype) ||
2153 isOperandVolatile (IC_LEFT (ic), TRUE)))
2156 applyToSet (ptrSetSet, findPointerSet, IC_LEFT (ic), &pdop, IC_RESULT (ic));
2157 /* if we find it then locally replace all
2158 references to the result with what we assigned */
2161 replaceAllSymBySym (ic->next, IC_RESULT (ic), pdop, &ebb->ndompset);
2165 /* delete from the cseSet anything that has */
2166 /* operands matching the result of this */
2167 /* except in case of pointer access */
2168 if (!(POINTER_SET (ic)) && IC_RESULT (ic))
2170 deleteItemIf (&cseSet, ifOperandsHave, IC_RESULT (ic));
2171 /* delete any previous definitions */
2172 ebb->defSet = bitVectCplAnd (ebb->defSet, OP_DEFS (IC_RESULT (ic)));
2176 /* add the left & right to the defUse set */
2177 if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic)))
2179 OP_USES(IC_LEFT (ic))=
2180 bitVectSetBit (OP_USES (IC_LEFT (ic)), ic->key);
2181 setUsesDefs (IC_LEFT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
2185 if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic)))
2187 OP_USES(IC_RIGHT (ic))=
2188 bitVectSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
2189 setUsesDefs (IC_RIGHT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
2193 /* for the result it is special case, put the result */
2194 /* in the defuseSet if it a pointer or array access */
2195 if (POINTER_SET (defic))
2197 OP_USES(IC_RESULT (ic))=
2198 bitVectSetBit (OP_USES (IC_RESULT (ic)), ic->key);
2199 setUsesDefs (IC_RESULT (ic), ebb->defSet, ebb->outDefs, &ebb->usesDefs);
2200 deleteItemIf (&cseSet, ifPointerGet, IC_RESULT (ic));
2201 ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, IC_RESULT (ic)->key);
2202 /* delete from inexpressions of all successors which
2203 have dfNum > than this block */
2204 for (i = 0; i < count; ebbs[i++]->visited = 0);
2205 applyToSet (ebb->succList, delGetPointerSucc, IC_RESULT (ic), ebb->dfnum);
2207 /* delete from cseSet all other pointer sets
2209 deleteItemIf (&ptrSetSet, ifPointerSet, IC_RESULT (ic));
2210 /* add to the local pointerset set */
2211 addSetHead (&ptrSetSet, newCseDef (IC_RESULT (ic), ic));
2214 /* add the result to defintion set */ if (IC_RESULT (ic))
2216 OP_DEFS(IC_RESULT (ic))=
2217 bitVectSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
2218 ebb->defSet = bitVectSetBit (ebb->defSet, ic->key);
2219 ebb->outDefs = bitVectCplAnd (ebb->outDefs, OP_DEFS (IC_RESULT (ic)));
2220 ebb->ldefs = bitVectSetBit (ebb->ldefs, ic->key);
2224 /* if this is an addressof instruction then */
2225 /* put the symbol in the address of list & */
2226 /* delete it from the cseSet */
2227 if (defic->op == ADDRESS_OF)
2229 addSetHead (&ebb->addrOf, IC_LEFT (ic));
2230 deleteItemIf (&cseSet, ifDefSymIsX, IC_LEFT (ic));
2234 for (expr=setFirstItem (ebb->inExprs); expr; expr=setNextItem (ebb->inExprs))
2235 if (!isinSetWith (cseSet, expr, isCseDefEqual) &&
2236 !isinSetWith (ebb->killedExprs, expr, isCseDefEqual)) {
2237 addSetHead (&ebb->killedExprs, expr);
2239 setToNull ((void *) &ebb->outExprs);
2240 ebb->outExprs = cseSet;
2241 ebb->outDefs = bitVectUnion (ebb->outDefs, ebb->defSet);
2242 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet, ebb->inPtrsSet);
2246 /*-----------------------------------------------------------------*/
2247 /* cseAllBlocks - will sequentially go thru & do cse for all blocks */
2248 /*-----------------------------------------------------------------*/
2250 cseAllBlocks (ebbIndex * ebbi, int computeOnly)
2252 eBBlock ** ebbs = ebbi->dfOrder;
2253 int count = ebbi->count;
2257 /* if optimization turned off */
2259 for (i = 0; i < count; i++)
2260 change += cseBBlock (ebbs[i], computeOnly, ebbi);