1 /*-------------------------------------------------------------------------
2 SDCCopt.c - calls all the optimizations routines and does some of the
3 hackier transformations, these include translating iCodes
4 to function calls and replacing local variables with their
5 register equivalents etc. Also contains the driver routine
6 for dead code elimination
8 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
10 This program is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 2, or (at your option) any
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
24 In other words, you are welcome to use, share and improve this program.
25 You are forbidden to forbid anyone else to use, share and improve
26 what you give them. Help stamp out software-hoarding!
27 -------------------------------------------------------------------------*/
31 /*-----------------------------------------------------------------*/
32 /* global variables */
38 /*-----------------------------------------------------------------*/
39 /* printSymName - prints the symbol names */
40 /*-----------------------------------------------------------------*/
42 printSymName (void *vsym)
45 fprintf (stdout, " %s ", sym->name);
49 /*-----------------------------------------------------------------*/
50 /* cnvToFcall - does the actual conversion to function call */
51 /*-----------------------------------------------------------------*/
53 cnvToFcall (iCode * ic, eBBlock * ebp)
60 int lineno = ic->lineno;
63 ip = ic->next; /* insertion point */
64 /* remove it from the iCode */
65 remiCodeFromeBBlock (ebp, ic);
68 right = IC_RIGHT (ic);
104 /* if float support routines NOT compiled as reentrant */
105 if (!options.float_rent)
109 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
111 newic = newiCode (SEND, IC_LEFT (ic), NULL);
112 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
116 newic = newiCode ('=', NULL, IC_LEFT (ic));
117 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
120 addiCodeToeBBlock (ebp, newic, ip);
121 newic->lineno = lineno;
124 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
126 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
127 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
131 newic = newiCode ('=', NULL, IC_RIGHT (ic));
132 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
134 addiCodeToeBBlock (ebp, newic, ip);
135 newic->lineno = lineno;
142 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
144 newic = newiCode (SEND, right, NULL);
145 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
149 newic = newiCode (IPUSH, right, NULL);
152 bytesPushed += getSize(operandType(right));
155 addiCodeToeBBlock (ebp, newic, ip);
156 newic->lineno = lineno;
158 /* insert push left */
159 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
161 newic = newiCode (SEND, left, NULL);
162 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
166 newic = newiCode (IPUSH, left, NULL);
169 bytesPushed += getSize(operandType(left));
171 addiCodeToeBBlock (ebp, newic, ip);
172 newic->lineno = lineno;
174 /* insert the call */
175 newic = newiCode (CALL, operandFromSymbol (func), NULL);
176 IC_RESULT (newic) = IC_RESULT (ic);
177 newic->lineno = lineno;
178 newic->parmBytes+=bytesPushed;
181 FUNC_HASFCALL (currFunc->type) = 1;
183 if(TARGET_IS_PIC16) {
184 /* normally these functions aren't marked external, so we can use their
185 * _extern field to marked as already added to symbol table */
187 if(!SPEC_EXTR(func->etype)) {
188 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
190 SPEC_EXTR(func->etype) = 1;
191 seg = SPEC_OCLS( func->etype );
192 addSet(&seg->syms, func);
196 addiCodeToeBBlock (ebp, newic, ip);
199 /*-----------------------------------------------------------------*/
200 /* cnvToFloatCast - converts casts to floats to function calls */
201 /*-----------------------------------------------------------------*/
203 cnvToFloatCast (iCode * ic, eBBlock * ebp)
207 sym_link *type = operandType (IC_RIGHT (ic));
208 int linenno = ic->lineno;
213 /* remove it from the iCode */
214 remiCodeFromeBBlock (ebp, ic);
215 /* depending on the type */
216 for (bwd = 0; bwd < 3; bwd++)
218 for (su = 0; su < 2; su++)
220 if (compareType (type, __multypes[bwd][su]) == 1)
222 func = __conv[0][bwd][su];
230 /* if float support routines NOT compiled as reentrant */
231 if (!options.float_rent)
234 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
236 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
237 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
241 newic = newiCode ('=', NULL, IC_RIGHT (ic));
242 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
244 addiCodeToeBBlock (ebp, newic, ip);
245 newic->lineno = linenno;
251 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
252 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
253 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
257 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
259 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
261 addiCodeToeBBlock (ebp, newic, ip);
262 newic->lineno = linenno;
267 newic = newiCode (CALL, operandFromSymbol (func), NULL);
268 IC_RESULT (newic) = IC_RESULT (ic);
269 newic->parmBytes+=bytesPushed;
272 FUNC_HASFCALL (currFunc->type) = 1;
274 if(TARGET_IS_PIC16) {
275 /* normally these functions aren't marked external, so we can use their
276 * _extern field to marked as already added to symbol table */
278 if(!SPEC_EXTR(func->etype)) {
279 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
281 SPEC_EXTR(func->etype) = 1;
282 seg = SPEC_OCLS( func->etype );
283 addSet(&seg->syms, func);
287 addiCodeToeBBlock (ebp, newic, ip);
288 newic->lineno = linenno;
291 /*-----------------------------------------------------------------*/
292 /* cnvFromFloatCast - converts casts From floats to function calls */
293 /*-----------------------------------------------------------------*/
295 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
299 sym_link *type = operandType (IC_LEFT (ic));
300 int lineno = ic->lineno;
305 /* remove it from the iCode */
306 remiCodeFromeBBlock (ebp, ic);
308 /* depending on the type */
309 for (bwd = 0; bwd < 3; bwd++)
311 for (su = 0; su < 2; su++)
313 if (compareType (type, __multypes[bwd][su]) == 1)
315 func = __conv[1][bwd][su];
323 /* if float support routines NOT compiled as reentrant */
324 if (!options.float_rent)
327 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
328 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
329 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
333 newic = newiCode ('=', NULL, IC_RIGHT (ic));
334 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
336 addiCodeToeBBlock (ebp, newic, ip);
337 newic->lineno = lineno;
344 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
345 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
346 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
350 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
352 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
354 addiCodeToeBBlock (ebp, newic, ip);
355 newic->lineno = lineno;
360 newic = newiCode (CALL, operandFromSymbol (func), NULL);
361 IC_RESULT (newic) = IC_RESULT (ic);
362 newic->parmBytes+=bytesPushed;
365 FUNC_HASFCALL (currFunc->type) = 1;
367 if(TARGET_IS_PIC16) {
368 /* normally these functions aren't marked external, so we can use their
369 * _extern field to marked as already added to symbol table */
371 if(!SPEC_EXTR(func->etype)) {
372 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
374 SPEC_EXTR(func->etype) = 1;
375 seg = SPEC_OCLS( func->etype );
376 addSet(&seg->syms, func);
380 addiCodeToeBBlock (ebp, newic, ip);
381 newic->lineno = lineno;
384 extern operand *geniCodeRValue (operand *, bool);
386 /*-----------------------------------------------------------------*/
387 /* convilong - converts int or long mults or divs to fcalls */
388 /*-----------------------------------------------------------------*/
390 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
393 iCode *ip = ic->next;
395 int lineno = ic->lineno;
400 remiCodeFromeBBlock (ebp, ic);
402 /* depending on the type */
403 for (bwd = 0; bwd < 3; bwd++)
405 for (su = 0; su < 2; su++)
407 if (compareType (type, __multypes[bwd][su]) == 1)
410 func = __muldiv[0][bwd][su];
412 func = __muldiv[1][bwd][su];
414 func = __muldiv[2][bwd][su];
416 func = __rlrr[1][bwd][su];
418 func = __rlrr[0][bwd][su];
419 else if (op == RIGHT_OP)
420 func = __rlrr[1][bwd][su];
421 else if (op == LEFT_OP)
422 func = __rlrr[0][bwd][su];
431 /* if int & long support routines NOT compiled as reentrant */
432 if (!options.intlong_rent)
435 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
436 newic = newiCode (SEND, IC_LEFT (ic), NULL);
437 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
441 newic = newiCode ('=', NULL, IC_LEFT (ic));
442 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
444 addiCodeToeBBlock (ebp, newic, ip);
445 newic->lineno = lineno;
448 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
449 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
450 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
454 newic = newiCode ('=', NULL, IC_RIGHT (ic));
455 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
457 addiCodeToeBBlock (ebp, newic, ip);
458 newic->lineno = lineno;
463 /* compiled as reentrant then push */
465 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
467 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
468 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
472 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
475 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
477 addiCodeToeBBlock (ebp, newic, ip);
478 newic->lineno = lineno;
480 /* insert push left */
481 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
483 newic = newiCode (SEND, IC_LEFT (ic), NULL);
484 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
488 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
491 bytesPushed += getSize(operandType(IC_LEFT(ic)));
493 addiCodeToeBBlock (ebp, newic, ip);
494 newic->lineno = lineno;
499 newic = newiCode (CALL, operandFromSymbol (func), NULL);
500 IC_RESULT (newic) = IC_RESULT (ic);
501 newic->lineno = lineno;
502 newic->parmBytes+=bytesPushed; // to clear the stack after the call
505 FUNC_HASFCALL (currFunc->type) = 1;
507 if(TARGET_IS_PIC16) {
508 /* normally these functions aren't marked external, so we can use their
509 * _extern field to marked as already added to symbol table */
511 if(!SPEC_EXTR(func->etype)) {
512 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
514 SPEC_EXTR(func->etype) = 1;
515 seg = SPEC_OCLS( func->etype );
516 addSet(&seg->syms, func);
520 addiCodeToeBBlock (ebp, newic, ip);
523 /*-----------------------------------------------------------------*/
524 /* convertToFcall - converts some operations to fcalls */
525 /*-----------------------------------------------------------------*/
527 convertToFcall (eBBlock ** ebbs, int count)
531 /* for all blocks do */
532 for (i = 0; i < count; i++)
536 /* for all instructions in the block do */
537 for (ic = ebbs[i]->sch; ic; ic = ic->next)
540 /* floating point operations are
541 converted to function calls */
542 if ((IS_CONDITIONAL (ic) ||
543 IS_ARITHMETIC_OP (ic)) &&
544 (IS_FLOAT (operandType (IC_RIGHT (ic)))))
547 cnvToFcall (ic, ebbs[i]);
550 /* casting is a little different */
553 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
554 cnvFromFloatCast (ic, ebbs[i]);
555 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
556 cnvToFloatCast (ic, ebbs[i]);
559 // Easy special case which avoids function call: modulo by a literal power
560 // of two can be replaced by a bitwise AND.
561 if (ic->op == '%' && isOperandLiteral(IC_RIGHT(ic)) &&
562 IS_UNSIGNED(operandType(IC_LEFT(ic))))
564 unsigned litVal = abs(operandLitValue(IC_RIGHT(ic)));
566 // See if literal value is a power of 2.
567 while (litVal && !(litVal & 1))
573 // discard lowest set bit.
580 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
585 /* if long / int mult or divide or mod */
586 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
588 sym_link *leftType = operandType (IC_LEFT (ic));
590 if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
592 sym_link *rightType = operandType (IC_RIGHT (ic));
594 if (port->hasNativeMulFor != NULL &&
595 port->hasNativeMulFor (ic, leftType, rightType))
597 /* Leave as native */
601 convilong (ic, ebbs[i], leftType, ic->op);
606 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
608 sym_link *type = operandType (IC_LEFT (ic));
610 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
612 convilong (ic, ebbs[i], type, ic->op);
619 /*-----------------------------------------------------------------*/
620 /* isLocalWithoutDef - return 1 if sym might be used without a */
622 /*-----------------------------------------------------------------*/
624 isLocalWithoutDef (symbol * sym)
629 if (IS_VOLATILE (sym->type))
635 if (IS_AGGREGATE (sym->type))
644 /*-----------------------------------------------------------------*/
645 /* replaceRegEqv - replace all local variables with their reqv */
646 /*-----------------------------------------------------------------*/
648 replaceRegEqv (eBBlock ** ebbs, int count)
652 /* Update the symbols' def bitvector so we know if there is */
653 /* a defining iCode or not. Only replace a local variable */
654 /* with its register equivalent if there is a defining iCode; */
655 /* otherwise, the port's register allocater may choke. */
656 cseAllBlocks (ebbs, count, TRUE);
658 for (i = 0; i < count; i++)
663 for (ic = ebbs[i]->sch; ic; ic = ic->next)
672 IS_TRUE_SYMOP (IC_COND (ic)) &&
673 isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
675 werrorfl (ic->filename, ic->lineno,
677 OP_SYMBOL (IC_COND (ic))->name);
678 OP_REQV (IC_COND (ic)) = NULL;
679 OP_SYMBOL (IC_COND (ic))->allocreq = 1;
682 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
683 OP_REQV (IC_COND (ic)))
684 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
685 OP_SYMBOL (IC_COND (ic))->defs,
686 OP_SYMBOL (IC_COND (ic))->uses);
692 if (ic->op == JUMPTABLE)
694 if (IC_JTCOND (ic) &&
695 IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
696 isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
698 werrorfl (ic->filename, ic->lineno,
700 OP_SYMBOL (IC_JTCOND (ic))->name);
701 OP_REQV (IC_JTCOND (ic)) = NULL;
702 OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
705 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
706 OP_REQV (IC_JTCOND (ic)))
707 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
708 OP_SYMBOL (IC_JTCOND (ic))->defs,
709 OP_SYMBOL (IC_JTCOND (ic))->uses);
713 if (ic->op == RECEIVE)
715 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
716 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
720 if (IC_RESULT (ic) &&
721 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
722 OP_REQV (IC_RESULT (ic)))
724 if (POINTER_SET (ic))
726 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
727 OP_SYMBOL (IC_RESULT (ic))->defs,
728 OP_SYMBOL (IC_RESULT (ic))->uses);
729 IC_RESULT (ic)->isaddr = 1;
732 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
733 OP_SYMBOL (IC_RESULT (ic))->defs,
734 OP_SYMBOL (IC_RESULT (ic))->uses);
738 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
739 isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
741 werrorfl (ic->filename, ic->lineno,
743 OP_SYMBOL (IC_RIGHT (ic))->name);
744 OP_REQV (IC_RIGHT (ic)) = NULL;
745 OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
749 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
750 OP_REQV (IC_RIGHT (ic)))
752 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
753 OP_SYMBOL (IC_RIGHT (ic))->defs,
754 OP_SYMBOL (IC_RIGHT (ic))->uses);
755 IC_RIGHT (ic)->isaddr = 0;
759 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
760 isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
762 werrorfl (ic->filename, ic->lineno,
764 OP_SYMBOL (IC_LEFT (ic))->name);
765 OP_REQV (IC_LEFT (ic)) = NULL;
766 OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
770 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
771 OP_REQV (IC_LEFT (ic)))
773 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
774 OP_SYMBOL (IC_LEFT (ic))->defs,
775 OP_SYMBOL (IC_LEFT (ic))->uses);
776 IC_LEFT (ic)->isaddr = 0;
782 /*-----------------------------------------------------------------*/
783 /* findReqv - search for a register equivalent */
784 /*-----------------------------------------------------------------*/
786 findReqv (symbol * prereqv, eBBlock ** ebbs, int count)
791 /* for all blocks do */
792 for (i=0; i<count; i++)
794 /* for all instructions in the block do */
795 for (ic = ebbs[i]->sch; ic; ic = ic->next)
799 if (IS_ITEMP (IC_COND (ic))
800 && OP_SYMBOL (IC_COND (ic))->prereqv == prereqv)
803 else if (ic->op == JUMPTABLE)
805 if (IS_ITEMP (IC_JTCOND (ic))
806 && OP_SYMBOL (IC_JTCOND (ic))->prereqv == prereqv)
807 return IC_JTCOND (ic);
811 if (IS_ITEMP (IC_LEFT (ic))
812 && OP_SYMBOL (IC_LEFT (ic))->prereqv == prereqv)
814 if (IS_ITEMP (IC_RIGHT (ic))
815 && OP_SYMBOL (IC_RIGHT (ic))->prereqv == prereqv)
816 return IC_RIGHT (ic);
817 if (IS_ITEMP (IC_RESULT (ic))
818 && OP_SYMBOL (IC_RESULT (ic))->prereqv == prereqv)
819 return IC_RESULT (ic);
827 /*-----------------------------------------------------------------*/
828 /* killDeadCode - eliminates dead assignments */
829 /*-----------------------------------------------------------------*/
831 killDeadCode (eBBlock ** ebbs, int count)
838 /* basic algorithm :- */
839 /* first the exclusion rules :- */
840 /* 1. if result is a global or volatile then skip */
841 /* 2. if assignment and result is a temp & isaddr then skip */
842 /* since this means array & pointer access, will be taken */
843 /* care of by alias analysis. */
844 /* 3. if the result is used in the remainder of the block skip */
845 /* 4. if this definition does not reach the end of the block */
846 /* i.e. the result is not present in the outExprs then KILL */
847 /* 5. if it reaches the end of block & is used by some success */
850 /* this whole process is carried on iteratively till no change */
855 /* for all blocks do */
856 for (i = 0; i < count; i++)
860 /* for all instructions in the block do */
861 for (ic = ebbs[i]->sch; ic; ic = ic->next)
869 ic->op == DUMMY_READ_VOLATILE ||
870 ic->op == CRITICAL ||
871 ic->op == ENDCRITICAL)
874 /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
875 /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are */
878 /* if the result is volatile then continue */
879 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
882 /* We also cannot remove the iCode, when an operand is volatile. */
883 /* Even read access can cause side effects on some hardware registers! */
885 /* if the left operand is volatile then continue */
886 if (IC_LEFT(ic) && isOperandVolatile (IC_LEFT (ic), TRUE))
889 /* if the right operand is volatile then continue */
890 if (IC_RIGHT(ic) && isOperandVolatile (IC_RIGHT (ic), TRUE))
894 /* if the result is a temp & isaddr then skip */
895 if (IC_RESULT (ic) && POINTER_SET (ic))
898 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next)
899 && !SPIL_LOC (IC_RESULT (ic)))
902 /* if the result is used in the remainder of the */
903 /* block then skip */
904 if (usedInRemaining (IC_RESULT (ic), ic->next))
907 /* does this definition reach the end of the block
908 or the usage is zero then we can kill */
909 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
910 kill = 1; /* if not we can kill it */
913 /* if this is a global variable or function parameter */
914 /* we cannot kill anyway */
915 if (isOperandGlobal (IC_RESULT (ic)) ||
916 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
917 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
920 /* if we are sure there are no usages */
921 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
927 /* reset visited flag */
928 for (j = 0; j < count; ebbs[j++]->visited = 0);
930 /* find out if this definition is alive */
931 if (applyToSet (ebbs[i]->succList,
940 /* kill this one if required */
943 bool volLeft = IS_SYMOP (IC_LEFT (ic))
944 && isOperandVolatile (IC_LEFT (ic), FALSE);
945 bool volRight = IS_SYMOP (IC_RIGHT (ic))
946 && isOperandVolatile (IC_RIGHT (ic), FALSE);
948 /* a dead address-of operation should die, even if volatile */
949 if (ic->op == ADDRESS_OF)
952 if (ic->next && ic->seqPoint == ic->next->seqPoint
953 && (ic->next->op == '+' || ic->next->op == '-'))
955 if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
956 || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
958 if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
959 || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
963 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
965 if (SPIL_LOC (IC_RESULT (ic)))
967 IC_RESULT (ic) = newiTempFromOp (IC_RESULT (ic));
968 SPIL_LOC (IC_RESULT (ic)) = NULL;
976 /* now delete from defUseSet */
977 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
978 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
980 /* and defset of the block */
981 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
983 /* If this is the last of a register equivalent, */
984 /* look for a successor register equivalent. */
985 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
986 if (IS_ITEMP (IC_RESULT (ic))
987 && OP_SYMBOL (IC_RESULT (ic))->isreqv
988 && bitVectIsZero (OP_DEFS (IC_RESULT (ic))))
990 symbol * resultsym = OP_SYMBOL (IC_RESULT (ic));
991 symbol * prereqv = resultsym->prereqv;
993 if (OP_SYMBOL (prereqv->reqv) == resultsym)
997 IC_RESULT (ic) = NULL;
998 newreqv = findReqv (prereqv, ebbs, count);
1001 prereqv->reqv = newreqv;
1006 /* delete the result */
1007 IC_RESULT (ic) = NULL;
1009 if (volLeft || volRight)
1011 /* something is volatile, so keep the iCode */
1012 /* and change the operator instead */
1013 ic->op = DUMMY_READ_VOLATILE;
1015 /* keep only the volatile operands */
1017 IC_LEFT (ic) = NULL;
1019 IC_RIGHT (ic) = NULL;
1023 /* nothing is volatile, eliminate the iCode */
1024 remiCodeFromeBBlock (ebbs[i], ic);
1026 /* for the left & right remove the usage */
1027 if (IS_SYMOP (IC_LEFT (ic)))
1028 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1030 if (IS_SYMOP (IC_RIGHT (ic)))
1031 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1035 } /* end of all instructions */
1037 if (!ebbs[i]->sch && !ebbs[i]->noPath)
1038 disconBBlock (ebbs[i], ebbs, count);
1040 } /* end of for all blocks */
1044 } /* end of while(1) */
1049 /*-----------------------------------------------------------------*/
1050 /* printCyclomatic - prints the cyclomatic information */
1051 /*-----------------------------------------------------------------*/
1053 printCyclomatic (eBBlock ** ebbs, int count)
1055 int nEdges = elementsInSet (graphEdges);
1058 for (i = 0; i < count; i++)
1059 nNodes += (!ebbs[i]->noPath);
1061 /* print the information */
1062 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
1065 /*-----------------------------------------------------------------*/
1066 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
1067 /* refer to dead variables. */
1068 /*-----------------------------------------------------------------*/
1070 discardDeadParamReceives (eBBlock ** ebbs, int count)
1076 for (i = 0; i < count; i++)
1078 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1080 if (ic->op == RECEIVE)
1082 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
1083 && !OP_SYMBOL (IC_RESULT (ic))->used)
1086 fprintf (stderr, "discarding dead receive for %s\n",
1087 OP_SYMBOL (IC_RESULT (ic))->name);
1089 dummyIcode.next = ic->next;
1090 remiCodeFromeBBlock (ebbs[i], ic);
1098 /*-----------------------------------------------------------------*/
1099 /* optimizeCastCast - remove unneeded intermediate casts. */
1100 /* Integer promotion may cast (un)signed char to int and then */
1101 /* recast the int to (un)signed long. If the signedness of the */
1102 /* char and long are the same, the cast can be safely performed in */
1103 /* a single step. */
1104 /*-----------------------------------------------------------------*/
1106 optimizeCastCast (eBBlock ** ebbs, int count)
1116 for (i = 0; i < count; i++)
1118 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1121 if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1123 type1 = operandType (IC_RIGHT (ic));
1124 type2 = operandType (IC_RESULT (ic));
1126 /* Look only for a cast from an integer type to an */
1127 /* integer type that has no loss of bits */
1128 if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1130 if (getSize (type2) < getSize (type1))
1133 /* There must be only one use of this first result */
1134 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1137 /* This use must be a second cast */
1138 uic = hTabItemWithKey (iCodehTab,
1139 bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1140 if (!uic || uic->op != CAST)
1143 /* It must be a cast to another integer type that */
1144 /* has no loss of bits */
1145 type3 = operandType (IC_RESULT (uic));
1146 if (!IS_INTEGRAL (type3))
1148 if (getSize (type3) < getSize (type2))
1151 /* The signedness between the first and last types */
1153 if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1156 /* Change the first cast to a simple assignment and */
1157 /* let the second cast do all the work */
1159 IC_LEFT (ic) = NULL;
1160 sym = OP_SYMBOL (IC_RESULT (ic));
1161 sym->type = copyLinkChain (type1);
1162 sym->etype = getSpec (sym->type);
1168 /*-----------------------------------------------------------------*/
1169 /* eBBlockFromiCode - creates extended basic blocks from iCode */
1170 /* will return an array of eBBlock pointers */
1171 /*-----------------------------------------------------------------*/
1173 eBBlockFromiCode (iCode * ic)
1175 eBBlock **ebbs = NULL;
1183 /* if nothing passed then return nothing */
1190 /* optimize the chain for labels & gotos
1191 this will eliminate redundant labels and
1192 will change jump to jumps by jumps */
1193 ic = iCodeLabelOptimize (ic);
1195 /* break it down into basic blocks */
1196 ebbs = iCodeBreakDown (ic, &count);
1199 /* hash the iCode keys so that we can quickly index */
1200 /* them in the rest of the optimization steps */
1201 setToNull ((void *) &iCodehTab);
1202 iCodehTab = newHashTable (iCodeKey);
1203 hashiCodeKeys (ebbs, count);
1205 /* compute the control flow */
1206 computeControlFlow (ebbs, count, 0);
1208 /* dumpraw if asked for */
1209 if (options.dump_raw)
1210 dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
1212 /* replace the local variables with their
1213 register equivalents : the liveRange computation
1214 along with the register allocation will determine
1215 if it finally stays in the registers */
1216 replaceRegEqv (ebbs, count);
1218 /* create loop regions */
1219 loops = createLoopRegions (ebbs, count);
1221 /* dumpraw if asked for */
1222 if (options.dump_raw)
1223 dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
1225 optimizeCastCast (ebbs, saveCount);
1227 /* do common subexpression elimination for each block */
1228 change = cseAllBlocks (ebbs, saveCount, FALSE);
1230 /* dumpraw if asked for */
1231 if (options.dump_raw)
1232 dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
1234 /* compute the data flow */
1235 computeDataFlow (ebbs, saveCount);
1237 /* dumpraw if asked for */
1238 if (options.dump_raw)
1239 dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
1241 /* global common subexpression elimination */
1242 if (optimize.global_cse)
1244 change += cseAllBlocks (ebbs, saveCount, FALSE);
1245 if (options.dump_gcse)
1246 dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
1250 // compute the dataflow only
1251 assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
1253 /* kill dead code */
1254 kchange = killDeadCode (ebbs, saveCount);
1256 if (options.dump_kill)
1257 dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
1259 /* do loop optimizations */
1260 change += (lchange = loopOptimizations (loops, ebbs, count));
1261 if (options.dump_loop)
1262 dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
1264 /* recompute the data flow and apply global cse again
1265 if loops optimizations or dead code caused a change:
1266 loops will brings out of the loop which then may be
1267 available for use in the later blocks: dead code
1268 elimination could potentially disconnect some blocks
1269 conditional flow may be efected so we need to apply
1270 subexpression once more */
1271 if (lchange || kchange)
1273 computeDataFlow (ebbs, saveCount);
1274 change += cseAllBlocks (ebbs, saveCount, FALSE);
1275 if (options.dump_loop)
1276 dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
1278 /* if loop optimizations caused a change then do
1279 dead code elimination once more : this will
1280 get rid of the extra assignments to the induction
1281 variables created during loop optimizations */
1282 killDeadCode (ebbs, saveCount);
1284 if (options.dump_loop)
1285 dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1289 /* sort it back by block number */
1290 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1292 if (!options.lessPedantic) {
1293 // this is a good place to check missing return values
1295 // the user is on his own with naked functions...
1296 if (!IS_VOID(currFunc->etype)
1297 && !FUNC_ISNAKED(currFunc->type)) {
1299 // make sure all predecessors of the last block end in a return
1300 for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1302 bp=setNextItem(ebbs[saveCount-1]->predList)) {
1303 if (bp->ech->op != RETURN) {
1304 werrorfl (bp->ech->filename, bp->ech->lineno,
1305 W_VOID_FUNC, currFunc->name);
1312 /* if cyclomatic info requested then print it */
1313 if (options.cyclomatic)
1314 printCyclomatic (ebbs, saveCount);
1316 /* convert operations with support routines
1317 written in C to function calls : Iam doing
1318 this at this point since I want all the
1319 operations to be as they are for optimzations */
1320 convertToFcall (ebbs, count);
1322 /* compute the live ranges */
1323 computeLiveRanges (ebbs, count);
1325 if (options.dump_range)
1326 dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1328 /* Now that we have the live ranges, discard parameter
1329 * receives for unused parameters.
1331 discardDeadParamReceives (ebbs, count);
1333 /* allocate registers & generate code */
1334 port->assignRegisters (ebbs, count);
1336 /* throw away blocks */
1337 setToNull ((void *) &graphEdges);
1344 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */