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 -------------------------------------------------------------------------*/
27 /*-----------------------------------------------------------------*/
28 /* newCseDef - new cseDef */
29 /*-----------------------------------------------------------------*/
30 cseDef *newCseDef (operand *sym, iCode *ic)
35 ALLOC(cdp,sizeof(cseDef));
46 /*-----------------------------------------------------------------*/
47 /* int isCseDefEqual - two definitions are equal */
48 /*-----------------------------------------------------------------*/
49 int isCseDefEqual ( void *vsrc, void *vdest)
57 return (src->key == dest->key &&
58 src->diCode == dest->diCode ) ;
62 /*-----------------------------------------------------------------*/
63 /* pcseDef - in the cseDef */
64 /*-----------------------------------------------------------------*/
65 int pcseDef (void *item, va_list ap)
71 fprintf(stdout,"**null op**");
72 printOperand(cdp->sym,stdout);
73 icTab = getTableEntry(cdp->diCode->op) ;
74 icTab->iCodePrint(stdout,cdp->diCode,icTab->printName);
78 /*-----------------------------------------------------------------*/
79 /* replaceAllSymBySym - replaces all operands by operand in an */
80 /* instruction chain */
81 /*-----------------------------------------------------------------*/
82 void replaceAllSymBySym (iCode *ic, operand *from , operand *to)
86 for (lic = ic ; lic ; lic = lic->next ) {
89 if (IC_RESULT(lic) && IC_RESULT(lic)->key == from->key ) {
90 /* maintain du chains */
91 if (POINTER_SET(lic)) {
92 bitVectUnSetBit (OP_USES(from),lic->key);
93 OP_USES(to) = bitVectSetBit (OP_USES(to),lic->key);
96 bitVectUnSetBit (OP_DEFS(from),lic->key);
97 OP_DEFS(to) = bitVectSetBit (OP_DEFS(to),lic->key);
99 siaddr = IC_RESULT(lic)->isaddr ;
100 IC_RESULT(lic) = operandFromOperand(to);
101 IC_RESULT(lic)->isaddr = siaddr ;
104 if (IC_RIGHT(lic) && IC_RIGHT(lic)->key == from->key ) {
105 bitVectUnSetBit (OP_USES(from),lic->key);
106 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
107 siaddr = IC_RIGHT(lic)->isaddr ;
108 IC_RIGHT(lic) = operandFromOperand(to);
109 IC_RIGHT(lic)->isaddr = siaddr ;
112 if (IC_LEFT(lic) && IC_LEFT(lic)->key == from->key ) {
113 bitVectUnSetBit (OP_USES(from),lic->key);
114 OP_USES(to) = bitVectSetBit(OP_USES(to),lic->key);
115 siaddr = IC_LEFT(lic)->isaddr ;
116 IC_LEFT(lic) = operandFromOperand(to);
117 IC_LEFT(lic)->isaddr = siaddr ;
122 /*-----------------------------------------------------------------*/
123 /* iCodeKeyIs - if the icode keys match then return 1 */
124 /*-----------------------------------------------------------------*/
125 DEFSETFUNC(iCodeKeyIs)
130 if (cdp->diCode->key == key)
136 /*-----------------------------------------------------------------*/
137 /* removeFromInExprs - removes an icode from inexpressions */
138 /*-----------------------------------------------------------------*/
139 DEFSETFUNC(removeFromInExprs)
143 V_ARG(operand *,from);
145 V_ARG(eBBlock *,cbp);
151 deleteItemIf(&ebp->inExprs,iCodeKeyIs,ic->key);
152 if (ebp != cbp && !bitVectBitValue(cbp->domVect,ebp->bbnum))
153 replaceAllSymBySym(ebp->sch,from,to);
155 applyToSet(ebp->succList,removeFromInExprs,ic,from,to,cbp);
159 /*-----------------------------------------------------------------*/
160 /* isGlobalInNearSpace - return TRUE if valriable is a globalin data */
161 /*-----------------------------------------------------------------*/
162 static bool isGlobalInNearSpace (operand *op)
164 link *type = getSpec(operandType(op));
165 /* this is 8051 specific: optimization
166 suggested by Jean-Louis VERN, with 8051s we have no
167 advantage of putting variables in near space into
169 if (isOperandGlobal(op) &&
170 IN_DIRSPACE(SPEC_OCLS(type)))
176 /*-----------------------------------------------------------------*/
177 /* findCheaperOp - cseBBlock support routine, will check to see if */
178 /* we have a operand previously defined */
179 /*-----------------------------------------------------------------*/
180 DEFSETFUNC(findCheaperOp)
183 V_ARG(operand *,cop);
184 V_ARG(operand **,opp);
186 /* if we have already found it */
190 /* not found it yet check if this is the one */
191 /* and this is not the defining one */
192 if (cop->key == cdp->key) {
194 /* do a special check this will help in */
195 /* constant propagation & dead code elim*/
196 /* for assignments only */
197 if (cdp->diCode->op == '=') {
198 /* if the result is volatile then return result */
199 if (IS_OP_VOLATILE (IC_RESULT(cdp->diCode)))
200 *opp = IC_RESULT(cdp->diCode);
202 /* if this is a straight assignment and
203 left is a temp then prefer the temporary to the
205 if (!POINTER_SET(cdp->diCode) &&
206 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
207 IS_TRUE_SYMOP(IC_RIGHT(cdp->diCode)))
208 *opp = IC_RESULT(cdp->diCode);
210 /* if straight assignement && and both
211 are temps then prefer the one that
212 will not need extra space to spil, also
213 take into consideration if right side
214 an induction variable
216 if (!POINTER_SET(cdp->diCode) &&
217 IS_ITEMP(IC_RESULT(cdp->diCode)) &&
218 IS_ITEMP(IC_RIGHT(cdp->diCode)) &&
219 !OP_SYMBOL(IC_RIGHT(cdp->diCode))->isind &&
220 ( (!SPIL_LOC(IC_RIGHT(cdp->diCode)) &&
221 SPIL_LOC(IC_RESULT(cdp->diCode))) ||
222 ( SPIL_LOC(IC_RESULT(cdp->diCode)) &&
223 SPIL_LOC(IC_RESULT(cdp->diCode)) ==
224 SPIL_LOC(IC_RIGHT(cdp->diCode))) )
226 *opp = IC_RESULT(cdp->diCode);
228 *opp = IC_RIGHT(cdp->diCode);
231 *opp = IC_RESULT(cdp->diCode) ;
234 /* if this is an assign to a temp. then check
235 if the right side is this then return this */
236 if (IS_TRUE_SYMOP(cop) &&
237 cdp->diCode->op == '=' &&
238 !POINTER_SET(cdp->diCode) &&
239 cop->key == IC_RIGHT(cdp->diCode)->key &&
240 !isGlobalInNearSpace (IC_RIGHT(cdp->diCode)) &&
241 IS_ITEMP(IC_RESULT(cdp->diCode)))
242 *opp = IC_RESULT(cdp->diCode);
246 if ((isGlobalInNearSpace(cop) &&
247 !isOperandLiteral(*opp)) ||
248 isOperandVolatile(*opp,FALSE)
254 if (cop->key == (*opp)->key ) {
259 if ((*opp)->isaddr != cop->isaddr && IS_ITEMP(cop)) {
260 *opp = operandFromOperand(*opp);
261 (*opp)->isaddr = cop->isaddr;
271 /*-----------------------------------------------------------------*/
272 /* findPointerSet - finds the right side of a pointer set op */
273 /*-----------------------------------------------------------------*/
274 DEFSETFUNC(findPointerSet)
278 V_ARG(operand **,opp);
279 V_ARG(operand *,rop);
281 if (POINTER_SET(cdp->diCode) &&
282 IC_RESULT(cdp->diCode)->key == op->key &&
283 !isOperandVolatile(IC_RESULT(cdp->diCode),TRUE) &&
284 !isOperandVolatile(IC_RIGHT(cdp->diCode),TRUE) &&
285 getSize(operandType(IC_RESULT(cdp->diCode))) ==
286 getSize(operandType(rop))) {
287 *opp = IC_RIGHT(cdp->diCode);
294 /*-----------------------------------------------------------------*/
295 /* findPrevIc - cseBBlock support function will return the iCode */
296 /* which matches the current one */
297 /*-----------------------------------------------------------------*/
298 DEFSETFUNC(findPrevIc)
304 /* if already found */
308 /* if the iCodes are the same */
309 if (isiCodeEqual(ic,cdp->diCode) &&
310 isOperandEqual(cdp->sym,IC_RESULT(cdp->diCode))) {
315 /* if iCodes are not the same */
316 /* see the operands maybe interchanged */
317 if (ic->op == cdp->diCode->op &&
318 ( ic->op == '+' || ic->op == '*' ) &&
319 isOperandEqual(IC_LEFT(ic),IC_RIGHT(cdp->diCode)) &&
320 isOperandEqual(IC_RIGHT(ic),IC_LEFT(cdp->diCode))) {
328 /*-----------------------------------------------------------------*/
329 /* ifDefGlobal - if definition is global */
330 /*-----------------------------------------------------------------*/
331 DEFSETFUNC(ifDefGlobal)
335 return (isOperandGlobal(cdp->sym));
338 /*-----------------------------------------------------------------*/
339 /* ifOperandsHave - if any of the operand are the same as this */
340 /*-----------------------------------------------------------------*/
341 DEFSETFUNC(ifOperandsHave)
347 if (IC_LEFT(cdp->diCode) &&
348 IS_SYMOP(IC_LEFT(cdp->diCode)) &&
349 IC_LEFT(cdp->diCode)->key == op->key)
352 if (IC_RIGHT(cdp->diCode) &&
353 IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
354 IC_RIGHT(cdp->diCode)->key == op->key)
357 /* or if any of the operands are volatile */
358 if (IC_LEFT(cdp->diCode) &&
359 IS_OP_VOLATILE(IC_LEFT(cdp->diCode)))
362 if (IC_RIGHT(cdp->diCode) &&
363 IS_OP_VOLATILE(IC_RIGHT(cdp->diCode)))
367 if (IC_RESULT(cdp->diCode) &&
368 IS_OP_VOLATILE(IC_RESULT(cdp->diCode)))
374 /*-----------------------------------------------------------------*/
375 /* ifDefSymIs - if a definition is found in the set */
376 /*-----------------------------------------------------------------*/
377 int ifDefSymIs (set *cseSet, operand *sym)
382 if (!sym || !IS_SYMOP(sym))
384 for (sl = cseSet ; sl ; sl = sl->next ) {
386 if (loop->sym->key == sym->key )
393 /*-----------------------------------------------------------------*/
394 /* ifDefSymIsX - will return 1 if the symbols match */
395 /*-----------------------------------------------------------------*/
396 DEFSETFUNC(ifDefSymIsX)
402 return cdp->sym->key == op->key ;
404 return ( isOperandEqual(cdp->sym,op) );
409 /*-----------------------------------------------------------------*/
410 /* ifDiCodeIs - returns truw if diCode is same */
411 /*-----------------------------------------------------------------*/
412 int ifDiCodeIs (set *cseSet, iCode *ic)
420 for (sl = cseSet ; sl ; sl = sl->next ) {
422 if (loop->diCode == ic)
429 /*-----------------------------------------------------------------*/
430 /* ifPointerGet - returns true if the icode is pointer get sym */
431 /*-----------------------------------------------------------------*/
432 DEFSETFUNC(ifPointerGet)
436 iCode *dic = cdp->diCode;
437 operand *left = IC_LEFT(cdp->diCode);
439 if (POINTER_GET(dic) && left->key == op->key)
445 /*-----------------------------------------------------------------*/
446 /* ifPointerSet - returns true if the icode is pointer set sym */
447 /*-----------------------------------------------------------------*/
448 DEFSETFUNC(ifPointerSet)
453 if (POINTER_SET(cdp->diCode) &&
454 IC_RESULT(cdp->diCode)->key == op->key)
460 /*-----------------------------------------------------------------*/
461 /* ifDiCodeIsX - will return 1 if the symbols match */
462 /*-----------------------------------------------------------------*/
463 DEFSETFUNC(ifDiCodeIsX)
468 return cdp->diCode == ic;
472 /*-----------------------------------------------------------------*/
473 /* algebraicOpts - does some algebraic optimizations */
474 /*-----------------------------------------------------------------*/
475 void algebraicOpts (iCode *ic)
477 /* we don't deal with the following iCodes
488 /* if both operands present & ! IFX */
489 /* then if they are both literal we */
490 /* perform the operation right now */
494 IS_OP_LITERAL(IC_LEFT(ic)) &&
495 IS_OP_LITERAL(IC_RIGHT(ic))) {
497 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
500 operandType(IC_RESULT(ic)));
503 SET_RESULT_RIGHT(ic);
507 /* if not ifx & only one operand present */
510 IS_OP_LITERAL(IC_LEFT(ic)) &&
513 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
516 operandType(IC_RESULT(ic)));
519 SET_RESULT_RIGHT(ic);
524 /* a special case : or in short a kludgy solution will think
525 about a better solution over a glass of wine someday */
526 if ( ic->op == GET_VALUE_AT_ADDRESS ) {
528 if (IS_ITEMP(IC_RESULT(ic)) &&
529 IS_TRUE_SYMOP(IC_LEFT(ic))) {
532 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
533 IC_RIGHT(ic)->isaddr = 0;
535 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
536 IC_RESULT(ic)->isaddr = 0;
537 setOperandType(IC_RESULT(ic),operandType(IC_RIGHT(ic)));
541 if (IS_ITEMP(IC_LEFT(ic)) &&
542 IS_ITEMP(IC_RESULT(ic)) &&
543 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
544 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
545 !IC_LEFT(ic)->isaddr ) {
547 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
548 IC_RIGHT(ic)->isaddr = 0;
549 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
550 IC_RESULT(ic)->isaddr = 0;
558 /* depending on the operation */
561 /* if adding the same thing change to left shift by 1*/
562 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key &&
563 !IS_FLOAT(operandType(IC_RESULT(ic)))) {
565 IC_RIGHT(ic) = operandFromLit(1);
568 /* if addition then check if one of them is a zero */
569 /* if yes turn it into assignmnt*/
570 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
571 operandLitValue(IC_LEFT(ic)) == 0.0 ) {
575 SET_ISADDR(IC_RESULT(ic),0);
576 SET_ISADDR(IC_RIGHT(ic),0);
579 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
580 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
583 IC_RIGHT(ic) = IC_LEFT(ic) ;
585 SET_ISADDR(IC_RIGHT(ic),0);
586 SET_ISADDR(IC_RESULT(ic),0);
591 /* if subtracting the the same thing then zero */
592 if ( IC_LEFT(ic)->key == IC_RIGHT(ic)->key ) {
594 IC_RIGHT(ic) = operandFromLit(0);
596 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
597 IC_RESULT(ic)->isaddr = 0;
601 /* if subtraction then check if one of the operand */
602 /* is zero then depending on which operand change */
603 /* to assignment or unary minus */
604 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
605 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
606 /* right size zero change to assignment */
608 IC_RIGHT(ic) = IC_LEFT(ic);
610 SET_ISADDR(IC_RIGHT(ic),0);
611 SET_ISADDR(IC_RESULT(ic),0);
614 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
615 operandLitValue (IC_LEFT(ic)) == 0.0) {
616 /* left zero turn into an unary minus */
617 ic->op = UNARYMINUS ;
618 IC_LEFT(ic) = IC_RIGHT(ic);
619 IC_RIGHT(ic) = NULL ;
623 /* if multiplication then check if either of */
624 /* them is zero then the result is zero */
625 /* if either of them is one then result is */
628 if (IS_OP_LITERAL(IC_LEFT(ic))) {
630 if (operandLitValue(IC_LEFT(ic)) == 0.0) {
632 IC_RIGHT(ic) = IC_LEFT(ic);
634 SET_RESULT_RIGHT(ic);
637 if ( operandLitValue(IC_LEFT(ic)) == 1.0) {
640 SET_RESULT_RIGHT(ic);
645 if (IS_OP_LITERAL(IC_RIGHT(ic))) {
647 if (operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
650 SET_RESULT_RIGHT(ic);
654 if (operandLitValue(IC_RIGHT(ic)) == 1.0) {
656 IC_RIGHT(ic) = IC_LEFT(ic);
658 SET_RESULT_RIGHT(ic);
664 /* if division by self then 1 */
665 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key) {
667 IC_RIGHT(ic) = operandFromLit(1);
669 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
670 IC_RESULT(ic)->isaddr = 0;
672 /* if this is a division then check if right */
673 /* is one then change it to an assignment */
674 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
675 operandLitValue(IC_RIGHT(ic)) == 1.0 ) {
678 IC_RIGHT(ic) = IC_LEFT(ic);
680 SET_RESULT_RIGHT(ic);
684 /* if both are the same for an comparison operators */
688 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
690 IC_RIGHT(ic) = operandFromLit(1);
692 SET_RESULT_RIGHT(ic);
698 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
700 IC_RIGHT(ic) = operandFromLit(0);
702 SET_RESULT_RIGHT(ic);
706 /* if this is a cast of a literal value */
707 if ( IS_OP_LITERAL(IC_RIGHT(ic))) {
710 operandFromValue (valCastLiteral(operandType(IC_LEFT(ic)),
711 operandLitValue(IC_RIGHT(ic))));
713 SET_ISADDR(IC_RESULT(ic),0);
715 /* if casting to the same */
716 if ( checkType(operandType(IC_RESULT(ic)),
717 operandType(IC_RIGHT(ic))) == 1) {
720 SET_ISADDR(IC_RESULT(ic),0);
724 if (IS_OP_LITERAL(IC_LEFT(ic))) {
727 (operandLitValue(IC_LEFT(ic)) == 0 ?
728 operandFromLit(1) : operandFromLit(0));
730 SET_ISADDR(IC_RESULT(ic),0);
736 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
737 /*-----------------------------------------------------------------*/
738 /* updateSpillLocation - keeps track of register spill location */
739 /*-----------------------------------------------------------------*/
740 void updateSpillLocation ( iCode *ic)
751 /* for the form true_symbol := iTempNN */
752 if (ASSIGN_ITEMP_TO_SYM(ic)
753 && !SPIL_LOC(IC_RIGHT(ic))) {
755 setype = getSpec(operandType(IC_RESULT(ic)));
757 if (!IC_RIGHT(ic)->noSpilLoc &&
758 !IS_VOLATILE(setype) &&
759 !IN_FARSPACE(SPEC_OCLS(setype)) &&
760 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
762 SPIL_LOC(IC_RIGHT(ic)) =
763 IC_RESULT(ic)->operand.symOperand;
766 if (ASSIGN_ITEMP_TO_ITEMP(ic) &&
767 !SPIL_LOC(IC_RIGHT(ic)) &&
768 !bitVectBitsInCommon(OP_DEFS(IC_RIGHT(ic)),OP_USES(IC_RESULT(ic))) &&
769 OP_SYMBOL(IC_RESULT(ic))->isreqv) {
771 setype = getSpec(operandType(IC_RESULT(ic)));
773 if (!IC_RIGHT(ic)->noSpilLoc &&
774 !IS_VOLATILE(setype) &&
775 !IN_FARSPACE(SPEC_OCLS(setype)) &&
776 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
778 SPIL_LOC(IC_RIGHT(ic)) =
779 SPIL_LOC(IC_RESULT(ic));
783 /*-----------------------------------------------------------------*/
784 /* setUsesDef - sets the uses def bitvector for a given operand */
785 /*-----------------------------------------------------------------*/
786 void setUsesDefs (operand *op, bitVect *bdefs,
787 bitVect *idefs, bitVect **oud)
789 /* compute the definitions alive at this point */
790 bitVect *adefs = bitVectUnion(bdefs,idefs);
792 /* of these definitions find the ones that are */
793 /* for this operand */
794 adefs = bitVectIntersect(adefs,OP_DEFS(op));
796 /* these are the definitions that this operand can use */
797 op->usesDefs = adefs;
799 /* the out defs is an union */
800 *oud = bitVectUnion(*oud,adefs);
803 /*-----------------------------------------------------------------*/
804 /* unsetDefsAndUses - clear this operation for the operands */
805 /*-----------------------------------------------------------------*/
806 void unsetDefsAndUses ( iCode *ic )
808 if ( ic->op == JUMPTABLE)
811 /* take away this definition from the def chain of the */
812 /* result & take away from use set of the operands */
814 /* turn off def set */
815 if (IS_SYMOP(IC_RESULT(ic))) {
816 if ( !POINTER_SET(ic))
817 bitVectUnSetBit(OP_DEFS(IC_RESULT(ic)),ic->key);
819 bitVectUnSetBit(OP_USES(IC_RESULT(ic)),ic->key);
821 /* turn off the useSet for the operands */
822 if (IS_SYMOP(IC_LEFT(ic)))
823 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
825 if (IS_SYMOP(IC_RIGHT(ic)))
826 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
828 else /* must be ifx turn off the use */
829 if (IS_SYMOP(IC_COND(ic)))
830 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
833 /*-----------------------------------------------------------------*/
834 /* ifxOptimize - changes ifx conditions if it can */
835 /*-----------------------------------------------------------------*/
836 void ifxOptimize (iCode *ic, set *cseSet,
838 eBBlock *ebb, int *change,
839 eBBlock **ebbs, int count)
844 /* if the condition can be replaced */
847 applyToSetFTrue (cseSet,findCheaperOp,IC_COND(ic),&pdop);
854 /* if the conditional is a literal then */
855 if (IS_OP_LITERAL(IC_COND(ic))) {
857 if ( operandLitValue(IC_COND(ic)) && IC_TRUE(ic)) {
859 /* change to a goto */
861 IC_LABEL(ic) = IC_TRUE(ic);
866 if (!operandLitValue(IC_COND(ic)) && IC_FALSE(ic)) {
868 IC_LABEL(ic) = IC_FALSE(ic);
872 /* then kill this if condition */
873 remiCodeFromeBBlock (ebb,ic);
877 /* now we need to recompute the control flow */
878 /* since the control flow has changed */
879 /* this is very expensive but it does not happen */
880 /* too often, if it does happen then the user pays */
882 computeControlFlow (ebbs,count,1);
883 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
887 /* if there is only one successor and that successor
888 is the same one we are conditionally going to then
889 we can remove this conditional statement */
890 label = (IC_TRUE(ic) ? IC_TRUE(ic) : IC_FALSE(ic));
891 if (elementsInSet(ebb->succList) == 1 &&
892 isinSet(ebb->succList,eBBWithEntryLabel(ebbs,label,count))) {
894 remiCodeFromeBBlock(ebb,ic);
895 computeControlFlow (ebbs,count,1);
896 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
901 /* if it remains an IFX the update the use Set */
902 OP_USES(IC_COND(ic)) = bitVectSetBit(OP_USES(IC_COND(ic)),ic->key);
903 setUsesDefs(IC_COND(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
907 /*-----------------------------------------------------------------*/
908 /* diCodeForSym - finds the definiting instruction for a symbol */
909 /*-----------------------------------------------------------------*/
910 DEFSETFUNC(diCodeForSym)
913 V_ARG(operand *,sym);
916 /* if already found */
920 /* if not if this is the defining iCode */
921 if (sym->key == cdp->key) {
929 /*-----------------------------------------------------------------*/
930 /* constFold - does some constant folding */
931 /*-----------------------------------------------------------------*/
932 int constFold (iCode *ic, set *cseSet)
935 /* this routine will change
941 /* deal with only + & - */
946 /* this check is a hueristic to prevent live ranges
947 from becoming too long */
948 if (IS_PTR(operandType(IC_RESULT(ic))))
951 /* check if operation with a literal */
952 if (!IS_OP_LITERAL(IC_RIGHT(ic)))
955 /* check if we can find a definition for the
957 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(ic),&dic)))
960 /* check that this is also a +/- */
961 if (dic->op != '+' && dic->op != '-')
965 if (!IS_OP_LITERAL(IC_RIGHT(dic)))
968 /* it is if the operations are the same*/
969 /* the literal parts need to be added */
970 IC_LEFT(ic) = operandFromOperand(IC_LEFT(dic));
971 if (ic->op == dic->op )
972 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic))+
973 operandLitValue(IC_RIGHT(dic)));
975 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) -
976 operandLitValue(IC_RIGHT(dic)));
978 if (IS_ITEMP(IC_RESULT(ic))) {
979 SPIL_LOC(IC_RESULT(ic)) = NULL;
980 IC_RESULT(ic)->noSpilLoc = 1;
987 /*-----------------------------------------------------------------*/
988 /* deleteGetPointers - called when a pointer is passed as parm */
989 /* will delete from cseSet all get pointers computed from this */
990 /* pointer. A simple ifOperandsHave is not good enough here */
991 /*-----------------------------------------------------------------*/
992 static void deleteGetPointers (set **cseSet, set **pss, operand *op,eBBlock *ebb)
994 set *compItems = NULL;
999 if (!*cseSet && !*pss)
1002 /* first find all items computed from this operand .
1003 This done fairly simply go thru the list and find
1004 those that are computed by arthimetic with this
1006 for (cdp = setFirstItem(*cseSet); cdp ; cdp = setNextItem(*cseSet)) {
1007 if (IS_ARITHMETIC_OP(cdp->diCode)) {
1008 if (isOperandEqual(IC_LEFT(cdp->diCode),op) ||
1009 isOperandEqual(IC_RIGHT(cdp->diCode),op)) {
1010 /* save it in our list of items */
1011 addSet(&compItems,IC_RESULT(cdp->diCode));
1013 /* also check for those computed from our computed
1014 list . This will take care of situations like
1015 iTemp1 = iTemp0 + 8;
1016 iTemp2 = iTemp1 + 8; */
1017 if (isinSetWith(compItems,IC_LEFT(cdp->diCode),isOperandEqual) ||
1018 isinSetWith(compItems,IC_RIGHT(cdp->diCode),isOperandEqual)) {
1019 addSet(&compItems,IC_RESULT(cdp->diCode));
1024 /* now delete all pointer gets with this op */
1025 deleteItemIf(cseSet,ifPointerGet,op);
1026 deleteItemIf(pss,ifPointerSet,op);
1028 /* set the bit vector used by dataFlow computation later */
1029 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,op->key);
1030 /* now for the computed items */
1031 for (cop = setFirstItem(compItems); cop ; cop = setNextItem(compItems)) {
1032 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,cop->key);
1033 deleteItemIf(cseSet,ifPointerGet,cop);
1034 deleteItemIf(pss,ifPointerSet,cop);
1038 /*-----------------------------------------------------------------*/
1039 /* delGetPointerSucc - delete get pointer from inExprs of succ with*/
1040 /* dfnum > supplied */
1041 /*-----------------------------------------------------------------*/
1042 DEFSETFUNC(delGetPointerSucc)
1044 eBBlock *ebp = item;
1045 V_ARG(operand *,op);
1052 if (ebp->dfnum > dfnum) {
1053 deleteItemIf(&ebp->inExprs,ifPointerGet,op);
1056 return applyToSet(ebp->succList,delGetPointerSucc,op,dfnum);
1059 /*-----------------------------------------------------------------*/
1060 /* cseBBlock - common subexpression elimination for basic blocks */
1061 /* this is the hackiest kludgiest routine in the whole */
1062 /* system. also the most important, since almost all */
1063 /* data flow related information is computed by it */
1064 /*-----------------------------------------------------------------*/
1065 int cseBBlock ( eBBlock *ebb, int computeOnly,
1066 eBBlock **ebbs, int count)
1072 set *ptrSetSet = NULL;
1074 /* if this block is not reachable */
1078 /* set of common subexpressions */
1079 cseSet = setFromSet (ebb->inExprs) ;
1081 /* these will be computed by this routine */
1082 setToNull ((void **)&ebb->outDefs);
1083 setToNull ((void **)&ebb->defSet);
1084 setToNull ((void **)&ebb->usesDefs);
1085 setToNull ((void **)&ebb->ptrsSet);
1086 setToNull ((void **)&ebb->addrOf);
1087 setToNull ((void **)&ebb->ldefs);
1089 ebb->outDefs = bitVectCopy (ebb->inDefs);
1090 bitVectDefault = iCodeKey;
1091 ebb->defSet = newBitVect(iCodeKey);
1092 ebb->usesDefs=newBitVect(iCodeKey);
1094 /* for all the instructions in this block do */
1095 for (ic = ebb->sch ; ic ; ic = ic->next ) {
1104 /* clear the def & use chains for the operands involved */
1105 /* in this operation . since it can change due to opts */
1106 unsetDefsAndUses (ic);
1108 if ( ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE) {
1109 /* add to defSet of the symbol */
1110 OP_DEFS(IC_RESULT(ic)) =
1111 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1112 /* add to the definition set of this block */
1113 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1114 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1115 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1116 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1117 /* delete global variables from the cseSet
1118 since they can be modified by the function call */
1119 deleteItemIf(&cseSet,ifDefGlobal);
1122 /* for pcall & ipush we need to add to the useSet */
1123 if ((ic->op == PCALL ||
1127 IS_SYMOP(IC_LEFT(ic))) {
1129 /* check if they can be replaced */
1130 if ( !computeOnly ) {
1132 applyToSetFTrue(cseSet,findCheaperOp,IC_LEFT(ic),&pdop);
1134 IC_LEFT(ic) = pdop ;
1136 /* the lookup could have changed it*/
1137 if (IS_SYMOP(IC_LEFT(ic))) {
1138 OP_USES(IC_LEFT(ic)) =
1139 bitVectSetBit(OP_USES(IC_LEFT(ic)),ic->key);
1140 setUsesDefs(IC_LEFT(ic),ebb->defSet,
1141 ebb->outDefs,&ebb->usesDefs);
1145 /* if we a sending a pointer as a parameter
1146 then kill all cse since the pointed to item
1147 might be changed in the function being called */
1148 if ((ic->op == IPUSH || ic->op == SEND) &&
1149 IS_PTR(operandType(IC_LEFT(ic)))) {
1150 deleteGetPointers(&cseSet,&ptrSetSet,IC_LEFT(ic),ebb);
1151 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_LEFT(ic)->key);
1152 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1153 applyToSet(ebb->succList,delGetPointerSucc,
1154 IC_LEFT(ic),ebb->dfnum);
1159 /* if jumptable then mark the usage */
1160 if (ic->op == JUMPTABLE ) {
1161 OP_USES(IC_JTCOND(ic)) =
1162 bitVectSetBit(OP_USES(IC_JTCOND(ic)),ic->key);
1163 setUsesDefs(IC_JTCOND(ic),ebb->defSet,
1164 ebb->outDefs,&ebb->usesDefs);
1171 /* do some algebraic optimizations if possible */
1173 while (constFold(ic,cseSet));
1176 if (POINTER_GET(ic) && !IS_PTR(operandType(IC_LEFT(ic)))) {
1177 setOperandType(IC_LEFT(ic),
1178 aggrToPtr(operandType(IC_LEFT(ic)),FALSE));
1180 if (POINTER_SET(ic) && !IS_PTR(operandType(IC_RESULT(ic)))) {
1181 setOperandType(IC_RESULT(ic),
1182 aggrToPtr(operandType(IC_RESULT(ic)),FALSE));
1185 /* if this is a condition statment then */
1186 /* check if the condition can be replaced */
1187 if (ic->op == IFX ) {
1188 ifxOptimize (ic, cseSet, computeOnly,
1194 /* if the assignment & result is a temp */
1195 /* see if we can replace it */
1196 if (ic->op == '=') {
1198 /* update the spill location for this */
1199 updateSpillLocation (ic);
1201 if (POINTER_SET(ic)) {
1203 applyToSetFTrue (cseSet,findCheaperOp,IC_RESULT(ic),&pdop);
1204 if (pdop && IS_ITEMP(pdop) && !computeOnly)
1205 IC_RESULT(ic) = pdop;
1209 /* do the operand lookup i.e. for both the */
1210 /* right & left operand : check the cseSet */
1211 /* to see if they have been replaced if yes*/
1212 /* then replace them with those from cseSet*/
1214 /* and left is a symbol */
1215 if (IS_SYMOP(IC_LEFT(ic)) &&
1216 !computeOnly && ic->op != ADDRESS_OF ) {
1219 applyToSetFTrue (cseSet,findCheaperOp,IC_LEFT(ic),&pdop) ;
1221 if (POINTER_GET(ic)) {
1222 if (IS_ITEMP(pdop) || IS_OP_LITERAL(pdop)) {
1226 /* check if there is a pointer set
1227 for the same pointer visible if yes
1228 then change this into an assignment */
1230 if (applyToSetFTrue(cseSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic)) &&
1231 !bitVectBitValue(ebb->ptrsSet,pdop->key)){
1234 IC_RIGHT(ic) = pdop;
1235 SET_ISADDR(IC_RESULT(ic),0);
1240 IC_LEFT(ic) = pdop ;
1247 if (IS_SYMOP(IC_RIGHT(ic)) && !computeOnly) {
1250 applyToSetFTrue (cseSet,findCheaperOp,IC_RIGHT(ic),&pdop);
1253 IC_RIGHT(ic) = pdop;
1258 /* if left or right changed then do algebraic */
1261 while(constFold(ic,cseSet));
1264 /* if after all this it becomes a assignment to self
1265 then delete it and continue */
1266 if (ASSIGNMENT_TO_SELF(ic)) {
1267 remiCodeFromeBBlock(ebb,ic);
1271 /* now we will check to see if the entire */
1272 /* operation has been performed before */
1273 /* and is available */
1274 /* don't do assignments they will be killed */
1275 /* by dead code elimination if required do */
1276 /* it only if result is a temporary */
1278 if (!( POINTER_GET(ic) &&
1279 (IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1280 isOperandVolatile(IC_LEFT(ic),TRUE))) &&
1282 IS_ITEMP(IC_RESULT(ic)) &&
1284 applyToSet (cseSet,findPrevIc,ic,&pdic);
1287 /* if found then eliminate this and add to*/
1288 /* to cseSet an element containing result */
1289 /* of this with previous opcode */
1292 if (IS_ITEMP(IC_RESULT(ic))) {
1294 /* replace in the remaining of this block */
1295 replaceAllSymBySym(ic->next,IC_RESULT(ic),IC_RESULT(pdic));
1296 /* remove this iCode from inexpressions of all
1297 its successors, it cannot be in the in expressions
1298 of any of the predecessors */
1299 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1300 applyToSet(ebb->succList,removeFromInExprs,ic,IC_RESULT(ic),
1301 IC_RESULT(pdic),ebb);
1303 /* if this was moved from another block */
1304 /* then replace in those blocks too */
1305 if ( ic->movedFrom ) {
1307 for (owner = setFirstItem(ic->movedFrom); owner ;
1308 owner = setNextItem(ic->movedFrom))
1309 replaceAllSymBySym(owner->sch,IC_RESULT(ic),IC_RESULT(pdic));
1311 pdic->movedFrom = unionSets(pdic->movedFrom,ic->movedFrom,THROW_NONE);
1314 addSetHead (&cseSet,newCseDef(IC_RESULT(ic),pdic));
1317 /* eliminate this */
1318 remiCodeFromeBBlock (ebb,ic);
1323 if (IS_ITEMP(IC_RESULT(ic)))
1328 /* just add this as a previous expression except in */
1329 /* case of a pointer access in which case this is a */
1330 /* usage not a definition */
1331 if (! (POINTER_SET(ic)) && IC_RESULT(ic)){
1332 deleteItemIf (&cseSet, ifDefSymIsX,IC_RESULT(ic));
1333 addSetHead(&cseSet,newCseDef(IC_RESULT(ic),ic));
1339 /* if assignment to a parameter which is not
1340 mine and type is a pointer then delete
1341 pointerGets to take care of aliasing */
1342 if (ASSIGNMENT(ic) &&
1343 OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) &&
1344 IS_PTR(operandType(IC_RESULT(ic)))) {
1345 deleteGetPointers(&cseSet,&ptrSetSet,IC_RIGHT(ic),ebb);
1346 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1347 applyToSet(ebb->succList,delGetPointerSucc,IC_RIGHT(ic),ebb->dfnum);
1348 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RIGHT(ic)->key);
1351 /* if this is a pointerget then see if we can replace
1352 this with a previously assigned pointer value */
1353 if (POINTER_GET(ic) &&
1354 !(IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1355 isOperandVolatile(IC_LEFT(ic),TRUE))) {
1357 applyToSet(ptrSetSet,findPointerSet,IC_LEFT(ic),&pdop,IC_RESULT(ic));
1358 /* if we find it then locally replace all
1359 references to the result with what we assigned */
1361 replaceAllSymBySym(ic->next,IC_RESULT(ic),pdop);
1365 /* delete from the cseSet anything that has */
1366 /* operands matching the result of this */
1367 /* except in case of pointer access */
1368 if (!(POINTER_SET(ic)) && IC_RESULT(ic)) {
1369 deleteItemIf (&cseSet,ifOperandsHave,IC_RESULT(ic));
1370 /* delete any previous definitions */
1371 ebb->defSet = bitVectCplAnd (ebb->defSet,OP_DEFS(IC_RESULT(ic)));
1375 /* add the left & right to the defUse set */
1376 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic))) {
1377 OP_USES(IC_LEFT(ic)) =
1378 bitVectSetBit (OP_USES(IC_LEFT(ic)),ic->key);
1379 setUsesDefs(IC_LEFT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1383 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic))) {
1384 OP_USES(IC_RIGHT(ic)) =
1385 bitVectSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
1386 setUsesDefs(IC_RIGHT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1390 /* for the result it is special case, put the result */
1391 /* in the defuseSet if it a pointer or array access */
1392 if ( POINTER_SET(defic) ) {
1393 OP_USES(IC_RESULT(ic)) =
1394 bitVectSetBit (OP_USES(IC_RESULT(ic)),ic->key);
1395 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1396 deleteItemIf(&cseSet,ifPointerGet,IC_RESULT(ic));
1397 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RESULT(ic)->key);
1398 /* delete from inexpressions of all successors which
1399 have dfNum > than this block */
1400 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1401 applyToSet(ebb->succList,delGetPointerSucc,IC_RESULT(ic),ebb->dfnum);
1403 /* delete from cseSet all other pointer sets
1405 deleteItemIf(&ptrSetSet,ifPointerSet,IC_RESULT(ic));
1406 /* add to the local pointerset set */
1407 addSetHead(&ptrSetSet,newCseDef(IC_RESULT(ic),ic));
1409 else /* add the result to defintion set */
1410 if (IC_RESULT(ic)) {
1411 OP_DEFS(IC_RESULT(ic)) =
1412 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1413 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1414 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1415 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1419 /* if this is an addressof instruction then */
1420 /* put the symbol in the address of list & */
1421 /* delete it from the cseSet */
1422 if (defic->op == ADDRESS_OF) {
1423 addSetHead (&ebb->addrOf, IC_LEFT(ic));
1424 deleteItemIf(&cseSet,ifDefSymIsX,IC_LEFT(ic));
1428 setToNull ((void **)&ebb->outExprs);
1429 ebb->outExprs = cseSet;
1430 ebb->outDefs = bitVectUnion (ebb->outDefs,ebb->defSet);
1431 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet,ebb->inPtrsSet);
1435 /*-----------------------------------------------------------------*/
1436 /* cseAllBlocks - will sequentially go thru & do cse for all blocks*/
1437 /*-----------------------------------------------------------------*/
1438 int cseAllBlocks (eBBlock **ebbs,int count)
1443 /* if optimization turned off */
1445 for (i = 0 ; i < count ;i++ )
1446 change += cseBBlock (ebbs[i],FALSE,ebbs,count);