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);
280 if (POINTER_SET(cdp->diCode) &&
281 IC_RESULT(cdp->diCode)->key == op->key &&
282 !isOperandVolatile(IC_RESULT(cdp->diCode),TRUE) &&
283 !isOperandVolatile(IC_RIGHT(cdp->diCode),TRUE)) {
284 *opp = IC_RIGHT(cdp->diCode);
291 /*-----------------------------------------------------------------*/
292 /* findPrevIc - cseBBlock support function will return the iCode */
293 /* which matches the current one */
294 /*-----------------------------------------------------------------*/
295 DEFSETFUNC(findPrevIc)
301 /* if already found */
305 /* if the iCodes are the same */
306 if (isiCodeEqual(ic,cdp->diCode) &&
307 isOperandEqual(cdp->sym,IC_RESULT(cdp->diCode))) {
312 /* if iCodes are not the same */
313 /* see the operands maybe interchanged */
314 if (ic->op == cdp->diCode->op &&
315 ( ic->op == '+' || ic->op == '*' ) &&
316 isOperandEqual(IC_LEFT(ic),IC_RIGHT(cdp->diCode)) &&
317 isOperandEqual(IC_RIGHT(ic),IC_LEFT(cdp->diCode))) {
325 /*-----------------------------------------------------------------*/
326 /* ifDefGlobal - if definition is global */
327 /*-----------------------------------------------------------------*/
328 DEFSETFUNC(ifDefGlobal)
332 return (isOperandGlobal(cdp->sym));
335 /*-----------------------------------------------------------------*/
336 /* ifOperandsHave - if any of the operand are the same as this */
337 /*-----------------------------------------------------------------*/
338 DEFSETFUNC(ifOperandsHave)
344 if (IC_LEFT(cdp->diCode) &&
345 IS_SYMOP(IC_LEFT(cdp->diCode)) &&
346 IC_LEFT(cdp->diCode)->key == op->key)
349 if (IC_RIGHT(cdp->diCode) &&
350 IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
351 IC_RIGHT(cdp->diCode)->key == op->key)
354 /* or if any of the operands are volatile */
355 if (IC_LEFT(cdp->diCode) &&
356 IS_OP_VOLATILE(IC_LEFT(cdp->diCode)))
359 if (IC_RIGHT(cdp->diCode) &&
360 IS_OP_VOLATILE(IC_RIGHT(cdp->diCode)))
364 if (IC_RESULT(cdp->diCode) &&
365 IS_OP_VOLATILE(IC_RESULT(cdp->diCode)))
371 /*-----------------------------------------------------------------*/
372 /* ifDefSymIs - if a definition is found in the set */
373 /*-----------------------------------------------------------------*/
374 int ifDefSymIs (set *cseSet, operand *sym)
379 if (!sym || !IS_SYMOP(sym))
381 for (sl = cseSet ; sl ; sl = sl->next ) {
383 if (loop->sym->key == sym->key )
390 /*-----------------------------------------------------------------*/
391 /* ifDefSymIsX - will return 1 if the symbols match */
392 /*-----------------------------------------------------------------*/
393 DEFSETFUNC(ifDefSymIsX)
399 return cdp->sym->key == op->key ;
401 return ( isOperandEqual(cdp->sym,op) );
406 /*-----------------------------------------------------------------*/
407 /* ifDiCodeIs - returns truw if diCode is same */
408 /*-----------------------------------------------------------------*/
409 int ifDiCodeIs (set *cseSet, iCode *ic)
417 for (sl = cseSet ; sl ; sl = sl->next ) {
419 if (loop->diCode == ic)
426 /*-----------------------------------------------------------------*/
427 /* ifPointerGet - returns true if the icode is pointer get sym */
428 /*-----------------------------------------------------------------*/
429 DEFSETFUNC(ifPointerGet)
433 iCode *dic = cdp->diCode;
434 operand *left = IC_LEFT(cdp->diCode);
436 if (POINTER_GET(dic) && left->key == op->key)
442 /*-----------------------------------------------------------------*/
443 /* ifPointerSet - returns true if the icode is pointer set sym */
444 /*-----------------------------------------------------------------*/
445 DEFSETFUNC(ifPointerSet)
450 if (POINTER_SET(cdp->diCode) &&
451 IC_RESULT(cdp->diCode)->key == op->key)
457 /*-----------------------------------------------------------------*/
458 /* ifDiCodeIsX - will return 1 if the symbols match */
459 /*-----------------------------------------------------------------*/
460 DEFSETFUNC(ifDiCodeIsX)
465 return cdp->diCode == ic;
469 /*-----------------------------------------------------------------*/
470 /* algebraicOpts - does some algebraic optimizations */
471 /*-----------------------------------------------------------------*/
472 void algebraicOpts (iCode *ic)
474 /* we don't deal with the following iCodes
485 /* if both operands present & ! IFX */
486 /* then if they are both literal we */
487 /* perform the operation right now */
491 IS_OP_LITERAL(IC_LEFT(ic)) &&
492 IS_OP_LITERAL(IC_RIGHT(ic))) {
494 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
497 operandType(IC_RESULT(ic)));
500 SET_RESULT_RIGHT(ic);
504 /* if not ifx & only one operand present */
507 IS_OP_LITERAL(IC_LEFT(ic)) &&
510 IC_RIGHT(ic) = operandOperation (IC_LEFT(ic),
513 operandType(IC_RESULT(ic)));
516 SET_RESULT_RIGHT(ic);
521 /* a special case : or in short a kludgy solution will think
522 about a better solution over a glass of wine someday */
523 if ( ic->op == GET_VALUE_AT_ADDRESS ) {
525 if (IS_ITEMP(IC_RESULT(ic)) &&
526 IS_TRUE_SYMOP(IC_LEFT(ic))) {
529 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
530 IC_RIGHT(ic)->isaddr = 0;
532 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
533 IC_RESULT(ic)->isaddr = 0;
534 setOperandType(IC_RESULT(ic),operandType(IC_RIGHT(ic)));
538 if (IS_ITEMP(IC_LEFT(ic)) &&
539 IS_ITEMP(IC_RESULT(ic)) &&
540 /* !OP_SYMBOL(IC_RESULT(ic))->isreqv && */
541 /* !OP_SYMBOL(IC_LEFT(ic))->isreqv && */
542 !IC_LEFT(ic)->isaddr ) {
544 IC_RIGHT(ic) = operandFromOperand(IC_LEFT(ic));
545 IC_RIGHT(ic)->isaddr = 0;
546 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
547 IC_RESULT(ic)->isaddr = 0;
555 /* depending on the operation */
558 /* if adding the same thing change to left shift by 1*/
559 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key &&
560 !IS_FLOAT(operandType(IC_RESULT(ic)))) {
562 IC_RIGHT(ic) = operandFromLit(1);
565 /* if addition then check if one of them is a zero */
566 /* if yes turn it into assignmnt*/
567 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
568 operandLitValue(IC_LEFT(ic)) == 0.0 ) {
572 SET_ISADDR(IC_RESULT(ic),0);
573 SET_ISADDR(IC_RIGHT(ic),0);
576 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
577 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
580 IC_RIGHT(ic) = IC_LEFT(ic) ;
582 SET_ISADDR(IC_RIGHT(ic),0);
583 SET_ISADDR(IC_RESULT(ic),0);
588 /* if subtracting the the same thing then zero */
589 if ( IC_LEFT(ic)->key == IC_RIGHT(ic)->key ) {
591 IC_RIGHT(ic) = operandFromLit(0);
593 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
594 IC_RESULT(ic)->isaddr = 0;
598 /* if subtraction then check if one of the operand */
599 /* is zero then depending on which operand change */
600 /* to assignment or unary minus */
601 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
602 operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
603 /* right size zero change to assignment */
605 IC_RIGHT(ic) = IC_LEFT(ic);
607 SET_ISADDR(IC_RIGHT(ic),0);
608 SET_ISADDR(IC_RESULT(ic),0);
611 if (IS_OP_LITERAL(IC_LEFT(ic)) &&
612 operandLitValue (IC_LEFT(ic)) == 0.0) {
613 /* left zero turn into an unary minus */
614 ic->op = UNARYMINUS ;
615 IC_LEFT(ic) = IC_RIGHT(ic);
616 IC_RIGHT(ic) = NULL ;
620 /* if multiplication then check if either of */
621 /* them is zero then the result is zero */
622 /* if either of them is one then result is */
625 if (IS_OP_LITERAL(IC_LEFT(ic))) {
627 if (operandLitValue(IC_LEFT(ic)) == 0.0) {
629 IC_RIGHT(ic) = IC_LEFT(ic);
631 SET_RESULT_RIGHT(ic);
634 if ( operandLitValue(IC_LEFT(ic)) == 1.0) {
637 SET_RESULT_RIGHT(ic);
642 if (IS_OP_LITERAL(IC_RIGHT(ic))) {
644 if (operandLitValue(IC_RIGHT(ic)) == 0.0 ) {
647 SET_RESULT_RIGHT(ic);
651 if (operandLitValue(IC_RIGHT(ic)) == 1.0) {
653 IC_RIGHT(ic) = IC_LEFT(ic);
655 SET_RESULT_RIGHT(ic);
661 /* if division by self then 1 */
662 if (IC_LEFT(ic)->key == IC_RIGHT(ic)->key) {
664 IC_RIGHT(ic) = operandFromLit(1);
666 IC_RESULT(ic) = operandFromOperand(IC_RESULT(ic));
667 IC_RESULT(ic)->isaddr = 0;
669 /* if this is a division then check if right */
670 /* is one then change it to an assignment */
671 if (IS_OP_LITERAL(IC_RIGHT(ic)) &&
672 operandLitValue(IC_RIGHT(ic)) == 1.0 ) {
675 IC_RIGHT(ic) = IC_LEFT(ic);
677 SET_RESULT_RIGHT(ic);
681 /* if both are the same for an comparison operators */
685 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
687 IC_RIGHT(ic) = operandFromLit(1);
689 SET_RESULT_RIGHT(ic);
695 if (isOperandEqual(IC_LEFT(ic),IC_RIGHT(ic))) {
697 IC_RIGHT(ic) = operandFromLit(0);
699 SET_RESULT_RIGHT(ic);
703 /* if this is a cast of a literal value */
704 if ( IS_OP_LITERAL(IC_RIGHT(ic))) {
707 operandFromValue (valCastLiteral(operandType(IC_LEFT(ic)),
708 operandLitValue(IC_RIGHT(ic))));
710 SET_ISADDR(IC_RESULT(ic),0);
712 /* if casting to the same */
713 if ( checkType(operandType(IC_RESULT(ic)),
714 operandType(IC_RIGHT(ic))) == 1) {
717 SET_ISADDR(IC_RESULT(ic),0);
721 if (IS_OP_LITERAL(IC_LEFT(ic))) {
724 (operandLitValue(IC_LEFT(ic)) == 0 ?
725 operandFromLit(1) : operandFromLit(0));
727 SET_ISADDR(IC_RESULT(ic),0);
733 #define OTHERS_PARM(s) (s->_isparm && !s->ismyparm)
734 /*-----------------------------------------------------------------*/
735 /* updateSpillLocation - keeps track of register spill location */
736 /*-----------------------------------------------------------------*/
737 void updateSpillLocation ( iCode *ic)
748 /* for the form true_symbol := iTempNN */
749 if (ASSIGN_ITEMP_TO_SYM(ic)
750 && !SPIL_LOC(IC_RIGHT(ic))) {
752 setype = getSpec(operandType(IC_RESULT(ic)));
754 if (!IC_RIGHT(ic)->noSpilLoc &&
755 !IS_VOLATILE(setype) &&
756 !IN_FARSPACE(SPEC_OCLS(setype)) &&
757 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
759 SPIL_LOC(IC_RIGHT(ic)) =
760 IC_RESULT(ic)->operand.symOperand;
763 if (ASSIGN_ITEMP_TO_ITEMP(ic) &&
764 !SPIL_LOC(IC_RIGHT(ic)) &&
765 bitVectnBitsOn(OP_USES(IC_RIGHT(ic))) == 0 &&
766 OP_SYMBOL(IC_RESULT(ic))->isreqv) {
768 setype = getSpec(operandType(IC_RESULT(ic)));
770 if (!IC_RIGHT(ic)->noSpilLoc &&
771 !IS_VOLATILE(setype) &&
772 !IN_FARSPACE(SPEC_OCLS(setype)) &&
773 !OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) )
775 SPIL_LOC(IC_RIGHT(ic)) =
776 SPIL_LOC(IC_RESULT(ic));
780 /*-----------------------------------------------------------------*/
781 /* setUsesDef - sets the uses def bitvector for a given operand */
782 /*-----------------------------------------------------------------*/
783 void setUsesDefs (operand *op, bitVect *bdefs,
784 bitVect *idefs, bitVect **oud)
786 /* compute the definitions alive at this point */
787 bitVect *adefs = bitVectUnion(bdefs,idefs);
789 /* of these definitions find the ones that are */
790 /* for this operand */
791 adefs = bitVectIntersect(adefs,OP_DEFS(op));
793 /* these are the definitions that this operand can use */
794 op->usesDefs = adefs;
796 /* the out defs is an union */
797 *oud = bitVectUnion(*oud,adefs);
800 /*-----------------------------------------------------------------*/
801 /* unsetDefsAndUses - clear this operation for the operands */
802 /*-----------------------------------------------------------------*/
803 void unsetDefsAndUses ( iCode *ic )
805 if ( ic->op == JUMPTABLE)
808 /* take away this definition from the def chain of the */
809 /* result & take away from use set of the operands */
811 /* turn off def set */
812 if (IS_SYMOP(IC_RESULT(ic))) {
813 if ( !POINTER_SET(ic))
814 bitVectUnSetBit(OP_DEFS(IC_RESULT(ic)),ic->key);
816 bitVectUnSetBit(OP_USES(IC_RESULT(ic)),ic->key);
818 /* turn off the useSet for the operands */
819 if (IS_SYMOP(IC_LEFT(ic)))
820 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
822 if (IS_SYMOP(IC_RIGHT(ic)))
823 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
825 else /* must be ifx turn off the use */
826 if (IS_SYMOP(IC_COND(ic)))
827 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
830 /*-----------------------------------------------------------------*/
831 /* ifxOptimize - changes ifx conditions if it can */
832 /*-----------------------------------------------------------------*/
833 void ifxOptimize (iCode *ic, set *cseSet,
835 eBBlock *ebb, int *change,
836 eBBlock **ebbs, int count)
841 /* if the condition can be replaced */
844 applyToSetFTrue (cseSet,findCheaperOp,IC_COND(ic),&pdop);
851 /* if the conditional is a literal then */
852 if (IS_OP_LITERAL(IC_COND(ic))) {
854 if ( operandLitValue(IC_COND(ic)) && IC_TRUE(ic)) {
856 /* change to a goto */
858 IC_LABEL(ic) = IC_TRUE(ic);
863 if (!operandLitValue(IC_COND(ic)) && IC_FALSE(ic)) {
865 IC_LABEL(ic) = IC_FALSE(ic);
869 /* then kill this if condition */
870 remiCodeFromeBBlock (ebb,ic);
874 /* now we need to recompute the control flow */
875 /* since the control flow has changed */
876 /* this is very expensive but it does not happen */
877 /* too often, if it does happen then the user pays */
879 computeControlFlow (ebbs,count,1);
880 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
884 /* if there is only one successor and that successor
885 is the same one we are conditionally going to then
886 we can remove this conditional statement */
887 label = (IC_TRUE(ic) ? IC_TRUE(ic) : IC_FALSE(ic));
888 if (elementsInSet(ebb->succList) == 1 &&
889 isinSet(ebb->succList,eBBWithEntryLabel(ebbs,label,count))) {
891 remiCodeFromeBBlock(ebb,ic);
892 computeControlFlow (ebbs,count,1);
893 werror (W_CONTROL_FLOW,ic->filename,ic->lineno);
898 /* if it remains an IFX the update the use Set */
899 OP_USES(IC_COND(ic)) = bitVectSetBit(OP_USES(IC_COND(ic)),ic->key);
900 setUsesDefs(IC_COND(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
904 /*-----------------------------------------------------------------*/
905 /* diCodeForSym - finds the definiting instruction for a symbol */
906 /*-----------------------------------------------------------------*/
907 DEFSETFUNC(diCodeForSym)
910 V_ARG(operand *,sym);
913 /* if already found */
917 /* if not if this is the defining iCode */
918 if (sym->key == cdp->key) {
926 /*-----------------------------------------------------------------*/
927 /* constFold - does some constant folding */
928 /*-----------------------------------------------------------------*/
929 int constFold (iCode *ic, set *cseSet)
932 /* this routine will change
938 /* deal with only + & - */
943 /* this check is a hueristic to prevent live ranges
944 from becoming too long */
945 if (IS_PTR(operandType(IC_RESULT(ic))))
948 /* check if operation with a literal */
949 if (!IS_OP_LITERAL(IC_RIGHT(ic)))
952 /* check if we can find a definition for the
954 if (!(applyToSet(cseSet,diCodeForSym,IC_LEFT(ic),&dic)))
957 /* check that this is also a +/- */
958 if (dic->op != '+' && dic->op != '-')
962 if (!IS_OP_LITERAL(IC_RIGHT(dic)))
965 /* it is if the operations are the same*/
966 /* the literal parts need to be added */
967 IC_LEFT(ic) = operandFromOperand(IC_LEFT(dic));
968 if (ic->op == dic->op )
969 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic))+
970 operandLitValue(IC_RIGHT(dic)));
972 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) -
973 operandLitValue(IC_RIGHT(dic)));
975 if (IS_ITEMP(IC_RESULT(ic))) {
976 SPIL_LOC(IC_RESULT(ic)) = NULL;
977 IC_RESULT(ic)->noSpilLoc = 1;
984 /*-----------------------------------------------------------------*/
985 /* deleteGetPointers - called when a pointer is passed as parm */
986 /* will delete from cseSet all get pointers computed from this */
987 /* pointer. A simple ifOperandsHave is not good enough here */
988 /*-----------------------------------------------------------------*/
989 static void deleteGetPointers (set **cseSet, set **pss, operand *op,eBBlock *ebb)
991 set *compItems = NULL;
996 if (!*cseSet && !*pss)
999 /* first find all items computed from this operand .
1000 This done fairly simply go thru the list and find
1001 those that are computed by arthimetic with this
1003 for (cdp = setFirstItem(*cseSet); cdp ; cdp = setNextItem(*cseSet)) {
1004 if (IS_ARITHMETIC_OP(cdp->diCode)) {
1005 if (isOperandEqual(IC_LEFT(cdp->diCode),op) ||
1006 isOperandEqual(IC_RIGHT(cdp->diCode),op)) {
1007 /* save it in our list of items */
1008 addSet(&compItems,IC_RESULT(cdp->diCode));
1010 /* also check for those computed from our computed
1011 list . This will take care of situations like
1012 iTemp1 = iTemp0 + 8;
1013 iTemp2 = iTemp1 + 8; */
1014 if (isinSetWith(compItems,IC_LEFT(cdp->diCode),isOperandEqual) ||
1015 isinSetWith(compItems,IC_RIGHT(cdp->diCode),isOperandEqual)) {
1016 addSet(&compItems,IC_RESULT(cdp->diCode));
1021 /* now delete all pointer gets with this op */
1022 deleteItemIf(cseSet,ifPointerGet,op);
1023 deleteItemIf(pss,ifPointerSet,op);
1025 /* set the bit vector used by dataFlow computation later */
1026 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,op->key);
1027 /* now for the computed items */
1028 for (cop = setFirstItem(compItems); cop ; cop = setNextItem(compItems)) {
1029 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,cop->key);
1030 deleteItemIf(cseSet,ifPointerGet,cop);
1031 deleteItemIf(pss,ifPointerSet,cop);
1035 /*-----------------------------------------------------------------*/
1036 /* delGetPointerSucc - delete get pointer from inExprs of succ with*/
1037 /* dfnum > supplied */
1038 /*-----------------------------------------------------------------*/
1039 DEFSETFUNC(delGetPointerSucc)
1041 eBBlock *ebp = item;
1042 V_ARG(operand *,op);
1049 if (ebp->dfnum > dfnum) {
1050 deleteItemIf(&ebp->inExprs,ifPointerGet,op);
1053 return applyToSet(ebp->succList,delGetPointerSucc,op,dfnum);
1056 /*-----------------------------------------------------------------*/
1057 /* cseBBlock - common subexpression elimination for basic blocks */
1058 /* this is the hackiest kludgiest routine in the whole */
1059 /* system. also the most important, since almost all */
1060 /* data flow related information is computed by it */
1061 /*-----------------------------------------------------------------*/
1062 int cseBBlock ( eBBlock *ebb, int computeOnly,
1063 eBBlock **ebbs, int count)
1069 set *ptrSetSet = NULL;
1071 /* if this block is not reachable */
1075 /* set of common subexpressions */
1076 cseSet = setFromSet (ebb->inExprs) ;
1078 /* these will be computed by this routine */
1079 setToNull ((void **)&ebb->outDefs);
1080 setToNull ((void **)&ebb->defSet);
1081 setToNull ((void **)&ebb->usesDefs);
1082 setToNull ((void **)&ebb->ptrsSet);
1083 setToNull ((void **)&ebb->addrOf);
1084 setToNull ((void **)&ebb->ldefs);
1086 ebb->outDefs = bitVectCopy (ebb->inDefs);
1087 bitVectDefault = iCodeKey;
1088 ebb->defSet = newBitVect(iCodeKey);
1089 ebb->usesDefs=newBitVect(iCodeKey);
1091 /* for all the instructions in this block do */
1092 for (ic = ebb->sch ; ic ; ic = ic->next ) {
1101 /* clear the def & use chains for the operands involved */
1102 /* in this operation . since it can change due to opts */
1103 unsetDefsAndUses (ic);
1105 if ( ic->op == PCALL || ic->op == CALL || ic->op == RECEIVE) {
1106 /* add to defSet of the symbol */
1107 OP_DEFS(IC_RESULT(ic)) =
1108 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1109 /* add to the definition set of this block */
1110 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1111 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1112 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1113 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1114 /* delete global variables from the cseSet
1115 since they can be modified by the function call */
1116 deleteItemIf(&cseSet,ifDefGlobal);
1119 /* for pcall & ipush we need to add to the useSet */
1120 if ((ic->op == PCALL ||
1124 IS_SYMOP(IC_LEFT(ic))) {
1126 /* check if they can be replaced */
1127 if ( !computeOnly ) {
1129 applyToSetFTrue(cseSet,findCheaperOp,IC_LEFT(ic),&pdop);
1131 IC_LEFT(ic) = pdop ;
1133 /* the lookup could have changed it*/
1134 if (IS_SYMOP(IC_LEFT(ic))) {
1135 OP_USES(IC_LEFT(ic)) =
1136 bitVectSetBit(OP_USES(IC_LEFT(ic)),ic->key);
1137 setUsesDefs(IC_LEFT(ic),ebb->defSet,
1138 ebb->outDefs,&ebb->usesDefs);
1142 /* if we a sending a pointer as a parameter
1143 then kill all cse since the pointed to item
1144 might be changed in the function being called */
1145 if ((ic->op == IPUSH || ic->op == SEND) &&
1146 IS_PTR(operandType(IC_LEFT(ic)))) {
1147 deleteGetPointers(&cseSet,&ptrSetSet,IC_LEFT(ic),ebb);
1148 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_LEFT(ic)->key);
1149 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1150 applyToSet(ebb->succList,delGetPointerSucc,
1151 IC_LEFT(ic),ebb->dfnum);
1156 /* if jumptable then mark the usage */
1157 if (ic->op == JUMPTABLE ) {
1158 OP_USES(IC_JTCOND(ic)) =
1159 bitVectSetBit(OP_USES(IC_JTCOND(ic)),ic->key);
1160 setUsesDefs(IC_JTCOND(ic),ebb->defSet,
1161 ebb->outDefs,&ebb->usesDefs);
1168 /* do some algebraic optimizations if possible */
1170 while (constFold(ic,cseSet));
1173 if (POINTER_GET(ic) && !IS_PTR(operandType(IC_LEFT(ic)))) {
1174 setOperandType(IC_LEFT(ic),
1175 aggrToPtr(operandType(IC_LEFT(ic)),FALSE));
1177 if (POINTER_SET(ic) && !IS_PTR(operandType(IC_RESULT(ic)))) {
1178 setOperandType(IC_RESULT(ic),
1179 aggrToPtr(operandType(IC_RESULT(ic)),FALSE));
1182 /* if this is a condition statment then */
1183 /* check if the condition can be replaced */
1184 if (ic->op == IFX ) {
1185 ifxOptimize (ic, cseSet, computeOnly,
1191 /* if the assignment & result is a temp */
1192 /* see if we can replace it */
1193 if (ic->op == '=') {
1195 /* update the spill location for this */
1196 updateSpillLocation (ic);
1198 if (POINTER_SET(ic)) {
1200 applyToSetFTrue (cseSet,findCheaperOp,IC_RESULT(ic),&pdop);
1201 if (pdop && IS_ITEMP(pdop) && !computeOnly)
1202 IC_RESULT(ic) = pdop;
1206 /* do the operand lookup i.e. for both the */
1207 /* right & left operand : check the cseSet */
1208 /* to see if they have been replaced if yes*/
1209 /* then replace them with those from cseSet*/
1211 /* and left is a symbol */
1212 if (IS_SYMOP(IC_LEFT(ic)) &&
1213 !computeOnly && ic->op != ADDRESS_OF ) {
1216 applyToSetFTrue (cseSet,findCheaperOp,IC_LEFT(ic),&pdop) ;
1218 if (POINTER_GET(ic)) {
1219 if (IS_ITEMP(pdop) || IS_OP_LITERAL(pdop)) {
1223 /* check if there is a pointer set
1224 for the same pointer visible if yes
1225 then change this into an assignment */
1227 if (applyToSetFTrue(cseSet,findPointerSet,IC_LEFT(ic),&pdop) &&
1228 !bitVectBitValue(ebb->ptrsSet,pdop->key)){
1231 IC_RIGHT(ic) = pdop;
1232 SET_ISADDR(IC_RESULT(ic),0);
1237 IC_LEFT(ic) = pdop ;
1244 if (IS_SYMOP(IC_RIGHT(ic)) && !computeOnly) {
1247 applyToSetFTrue (cseSet,findCheaperOp,IC_RIGHT(ic),&pdop);
1250 IC_RIGHT(ic) = pdop;
1255 /* if left or right changed then do algebraic */
1258 while(constFold(ic,cseSet));
1261 /* if after all this it becomes a assignment to self
1262 then delete it and continue */
1263 if (ASSIGNMENT_TO_SELF(ic)) {
1264 remiCodeFromeBBlock(ebb,ic);
1268 /* now we will check to see if the entire */
1269 /* operation has been performed before */
1270 /* and is available */
1271 /* don't do assignments they will be killed */
1272 /* by dead code elimination if required do */
1273 /* it only if result is a temporary */
1275 if (!( POINTER_GET(ic) &&
1276 (IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1277 isOperandVolatile(IC_LEFT(ic),TRUE))) &&
1279 IS_ITEMP(IC_RESULT(ic)) &&
1281 applyToSet (cseSet,findPrevIc,ic,&pdic);
1284 /* if found then eliminate this and add to*/
1285 /* to cseSet an element containing result */
1286 /* of this with previous opcode */
1289 if (IS_ITEMP(IC_RESULT(ic))) {
1291 /* replace in the remaining of this block */
1292 replaceAllSymBySym(ic->next,IC_RESULT(ic),IC_RESULT(pdic));
1293 /* remove this iCode from inexpressions of all
1294 its successors, it cannot be in the in expressions
1295 of any of the predecessors */
1296 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1297 applyToSet(ebb->succList,removeFromInExprs,ic,IC_RESULT(ic),
1298 IC_RESULT(pdic),ebb);
1300 /* if this was moved from another block */
1301 /* then replace in those blocks too */
1302 if ( ic->movedFrom ) {
1304 for (owner = setFirstItem(ic->movedFrom); owner ;
1305 owner = setNextItem(ic->movedFrom))
1306 replaceAllSymBySym(owner->sch,IC_RESULT(ic),IC_RESULT(pdic));
1308 pdic->movedFrom = unionSets(pdic->movedFrom,ic->movedFrom,THROW_NONE);
1311 addSetHead (&cseSet,newCseDef(IC_RESULT(ic),pdic));
1314 /* eliminate this */
1315 remiCodeFromeBBlock (ebb,ic);
1320 if (IS_ITEMP(IC_RESULT(ic)))
1325 /* just add this as a previous expression except in */
1326 /* case of a pointer access in which case this is a */
1327 /* usage not a definition */
1328 if (! (POINTER_SET(ic)) && IC_RESULT(ic)){
1329 deleteItemIf (&cseSet, ifDefSymIsX,IC_RESULT(ic));
1330 addSetHead(&cseSet,newCseDef(IC_RESULT(ic),ic));
1336 /* if assignment to a parameter which is not
1337 mine and type is a pointer then delete
1338 pointerGets to take care of aliasing */
1339 if (ASSIGNMENT(ic) &&
1340 OTHERS_PARM(OP_SYMBOL(IC_RESULT(ic))) &&
1341 IS_PTR(operandType(IC_RESULT(ic)))) {
1342 deleteGetPointers(&cseSet,&ptrSetSet,IC_RIGHT(ic),ebb);
1343 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1344 applyToSet(ebb->succList,delGetPointerSucc,IC_RIGHT(ic),ebb->dfnum);
1345 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RIGHT(ic)->key);
1348 /* if this is a pointerget then see if we can replace
1349 this with a previously assigned pointer value */
1350 if (POINTER_GET(ic) &&
1351 !(IS_BITFIELD(OP_SYMBOL(IC_RESULT(ic))->etype) ||
1352 isOperandVolatile(IC_LEFT(ic),TRUE))) {
1354 applyToSet(ptrSetSet,findPointerSet,IC_LEFT(ic),&pdop);
1355 /* if we find it then locally replace all
1356 references to the result with what we assigned */
1358 replaceAllSymBySym(ic->next,IC_RESULT(ic),pdop);
1362 /* delete from the cseSet anything that has */
1363 /* operands matching the result of this */
1364 /* except in case of pointer access */
1365 if (!(POINTER_SET(ic)) && IC_RESULT(ic)) {
1366 deleteItemIf (&cseSet,ifOperandsHave,IC_RESULT(ic));
1367 /* delete any previous definitions */
1368 ebb->defSet = bitVectCplAnd (ebb->defSet,OP_DEFS(IC_RESULT(ic)));
1372 /* add the left & right to the defUse set */
1373 if (IC_LEFT(ic) && IS_SYMOP(IC_LEFT(ic))) {
1374 OP_USES(IC_LEFT(ic)) =
1375 bitVectSetBit (OP_USES(IC_LEFT(ic)),ic->key);
1376 setUsesDefs(IC_LEFT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1380 if (IC_RIGHT(ic) && IS_SYMOP(IC_RIGHT(ic))) {
1381 OP_USES(IC_RIGHT(ic)) =
1382 bitVectSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
1383 setUsesDefs(IC_RIGHT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1387 /* for the result it is special case, put the result */
1388 /* in the defuseSet if it a pointer or array access */
1389 if ( POINTER_SET(defic) ) {
1390 OP_USES(IC_RESULT(ic)) =
1391 bitVectSetBit (OP_USES(IC_RESULT(ic)),ic->key);
1392 setUsesDefs(IC_RESULT(ic),ebb->defSet,ebb->outDefs,&ebb->usesDefs);
1393 deleteItemIf(&cseSet,ifPointerGet,IC_RESULT(ic));
1394 ebb->ptrsSet = bitVectSetBit(ebb->ptrsSet,IC_RESULT(ic)->key);
1395 /* delete from inexpressions of all successors which
1396 have dfNum > than this block */
1397 for (i = 0 ; i < count ;ebbs[i++]->visited = 0);
1398 applyToSet(ebb->succList,delGetPointerSucc,IC_RESULT(ic),ebb->dfnum);
1400 /* delete from cseSet all other pointer sets
1402 deleteItemIf(&ptrSetSet,ifPointerSet,IC_RESULT(ic));
1403 /* add to the local pointerset set */
1404 addSetHead(&ptrSetSet,newCseDef(IC_RESULT(ic),ic));
1406 else /* add the result to defintion set */
1407 if (IC_RESULT(ic)) {
1408 OP_DEFS(IC_RESULT(ic)) =
1409 bitVectSetBit (OP_DEFS(IC_RESULT(ic)),ic->key);
1410 ebb->defSet = bitVectSetBit (ebb->defSet,ic->key);
1411 ebb->outDefs= bitVectCplAnd (ebb->outDefs,OP_DEFS(IC_RESULT(ic)));
1412 ebb->ldefs = bitVectSetBit (ebb->ldefs,ic->key);
1416 /* if this is an addressof instruction then */
1417 /* put the symbol in the address of list & */
1418 /* delete it from the cseSet */
1419 if (defic->op == ADDRESS_OF) {
1420 addSetHead (&ebb->addrOf, IC_LEFT(ic));
1421 deleteItemIf(&cseSet,ifDefSymIsX,IC_LEFT(ic));
1425 setToNull ((void **)&ebb->outExprs);
1426 ebb->outExprs = cseSet;
1427 ebb->outDefs = bitVectUnion (ebb->outDefs,ebb->defSet);
1428 ebb->ptrsSet = bitVectUnion (ebb->ptrsSet,ebb->inPtrsSet);
1432 /*-----------------------------------------------------------------*/
1433 /* cseAllBlocks - will sequentially go thru & do cse for all blocks*/
1434 /*-----------------------------------------------------------------*/
1435 int cseAllBlocks (eBBlock **ebbs,int count)
1440 /* if optimization turned off */
1442 for (i = 0 ; i < count ;i++ )
1443 change += cseBBlock (ebbs[i],FALSE,ebbs,count);