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 -------------------------------------------------------------------------*/
32 /*-----------------------------------------------------------------*/
33 /* global variables */
39 /*-----------------------------------------------------------------*/
40 /* printSymName - prints the symbol names */
41 /*-----------------------------------------------------------------*/
43 printSymName (void *vsym)
46 fprintf (stdout, " %s ", sym->name);
50 /*-----------------------------------------------------------------*/
51 /* cnvToFcall - does the actual conversion to function call */
52 /*-----------------------------------------------------------------*/
54 cnvToFcall (iCode * ic, eBBlock * ebp)
61 int lineno = ic->lineno;
64 ip = ic->next; /* insertion point */
65 /* remove it from the iCode */
66 remiCodeFromeBBlock (ebp, ic);
69 right = IC_RIGHT (ic);
72 bitVectUnSetBit (OP_USES (left), ic->key);
74 bitVectUnSetBit (OP_USES (right), ic->key);
76 if (IS_FLOAT (operandType (right))) {
111 if (IS_FIXED16X16 (operandType (right))) {
115 func = __fps16x16_add;
118 func = __fps16x16_sub;
121 func = __fps16x16_div;
124 func = __fps16x16_mul;
127 func = __fps16x16_eq;
130 func = __fps16x16_neq;
133 func = __fps16x16_lt;
136 func = __fps16x16_gt;
139 func = __fps16x16_lteq;
142 func = __fps16x16_gteq;
148 /* if float support routines NOT compiled as reentrant */
149 if (!options.float_rent)
153 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
155 newic = newiCode (SEND, left, NULL);
156 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
160 newic = newiCode ('=', NULL, left);
161 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
164 addiCodeToeBBlock (ebp, newic, ip);
165 newic->lineno = lineno;
167 OP_USES (left) = bitVectSetBit (OP_USES (left), newic->key);
170 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
172 newic = newiCode (SEND, right, NULL);
173 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
177 newic = newiCode ('=', NULL, right);
178 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
180 addiCodeToeBBlock (ebp, newic, ip);
181 newic->lineno = lineno;
182 if (IS_SYMOP (right))
183 OP_USES (right) = bitVectSetBit (OP_USES (right), newic->key);
190 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
192 newic = newiCode (SEND, right, NULL);
193 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
197 newic = newiCode (IPUSH, right, NULL);
199 bytesPushed += getSize(operandType(right));
202 addiCodeToeBBlock (ebp, newic, ip);
203 newic->lineno = lineno;
204 if (IS_SYMOP (right))
205 OP_USES (right) = bitVectSetBit (OP_USES (right), newic->key);
207 /* insert push left */
208 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
210 newic = newiCode (SEND, left, NULL);
211 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
215 newic = newiCode (IPUSH, left, NULL);
217 bytesPushed += getSize(operandType(left));
219 addiCodeToeBBlock (ebp, newic, ip);
220 newic->lineno = lineno;
222 OP_USES (left) = bitVectSetBit (OP_USES (left), newic->key);
225 /* insert the call */
226 newic = newiCode (CALL, operandFromSymbol (func), NULL);
227 IC_RESULT (newic) = IC_RESULT (ic);
228 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
229 OP_USES (IC_RESULT (newic)) = bitVectSetBit (OP_USES (IC_RESULT (newic)), newic->key);
230 newic->lineno = lineno;
231 newic->parmBytes += bytesPushed;
234 FUNC_HASFCALL (currFunc->type) = 1;
236 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
237 /* normally these functions aren't marked external, so we can use their
238 * _extern field to marked as already added to symbol table */
240 if(!SPEC_EXTR(func->etype)) {
241 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
243 SPEC_EXTR(func->etype) = 1;
244 seg = SPEC_OCLS( func->etype );
245 addSet(&seg->syms, func);
249 addiCodeToeBBlock (ebp, newic, ip);
252 /*-----------------------------------------------------------------*/
253 /* cnvToFloatCast - converts casts to floats to function calls */
254 /*-----------------------------------------------------------------*/
256 cnvToFloatCast (iCode * ic, eBBlock * ebp)
260 sym_link *type = operandType (IC_RIGHT (ic));
261 int linenno = ic->lineno;
266 /* remove it from the iCode */
267 remiCodeFromeBBlock (ebp, ic);
268 /* depending on the type */
269 for (bwd = 0; bwd < 3; bwd++)
271 for (su = 0; su < 2; su++)
273 if (compareType (type, __multypes[bwd][su]) == 1)
275 func = __conv[0][bwd][su];
281 if(compareType (type, fixed16x16Type) == 1) {
282 func = __fp16x16conv[0][3][0];
289 /* if float support routines NOT compiled as reentrant */
290 if (!options.float_rent)
293 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
295 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
296 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
300 newic = newiCode ('=', NULL, IC_RIGHT (ic));
301 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
303 addiCodeToeBBlock (ebp, newic, ip);
304 newic->lineno = linenno;
310 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
311 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
312 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
316 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
318 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
320 addiCodeToeBBlock (ebp, newic, ip);
321 newic->lineno = linenno;
326 newic = newiCode (CALL, operandFromSymbol (func), NULL);
327 IC_RESULT (newic) = IC_RESULT (ic);
328 newic->parmBytes+=bytesPushed;
331 FUNC_HASFCALL (currFunc->type) = 1;
333 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
334 /* normally these functions aren't marked external, so we can use their
335 * _extern field to marked as already added to symbol table */
337 if(!SPEC_EXTR(func->etype)) {
338 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
340 SPEC_EXTR(func->etype) = 1;
341 seg = SPEC_OCLS( func->etype );
342 addSet(&seg->syms, func);
346 addiCodeToeBBlock (ebp, newic, ip);
347 newic->lineno = linenno;
350 /*----------------------------------------------------------------------*/
351 /* cnvToFixed16x16Cast - converts casts to fixed16x16 to function calls */
352 /*----------------------------------------------------------------------*/
354 cnvToFixed16x16Cast (iCode * ic, eBBlock * ebp)
358 sym_link *type = operandType (IC_RIGHT (ic));
359 int linenno = ic->lineno;
364 /* remove it from the iCode */
365 remiCodeFromeBBlock (ebp, ic);
366 /* depending on the type */
367 for (bwd = 0; bwd < 3; bwd++)
369 for (su = 0; su < 2; su++)
371 if (compareType (type, __multypes[bwd][su]) == 1)
373 func = __fp16x16conv[0][bwd][su];
381 /* if float support routines NOT compiled as reentrant */
382 if (!options.float_rent)
385 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
387 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
388 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
392 newic = newiCode ('=', NULL, IC_RIGHT (ic));
393 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
395 addiCodeToeBBlock (ebp, newic, ip);
396 newic->lineno = linenno;
402 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
403 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
404 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
408 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
410 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
412 addiCodeToeBBlock (ebp, newic, ip);
413 newic->lineno = linenno;
418 newic = newiCode (CALL, operandFromSymbol (func), NULL);
419 IC_RESULT (newic) = IC_RESULT (ic);
420 newic->parmBytes+=bytesPushed;
423 FUNC_HASFCALL (currFunc->type) = 1;
425 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
426 /* normally these functions aren't marked external, so we can use their
427 * _extern field to marked as already added to symbol table */
429 if(!SPEC_EXTR(func->etype)) {
430 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
432 SPEC_EXTR(func->etype) = 1;
433 seg = SPEC_OCLS( func->etype );
434 addSet(&seg->syms, func);
438 addiCodeToeBBlock (ebp, newic, ip);
439 newic->lineno = linenno;
442 /*-----------------------------------------------------------------*/
443 /* cnvFromFloatCast - converts casts From floats to function calls */
444 /*-----------------------------------------------------------------*/
446 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
450 sym_link *type = operandType (IC_LEFT (ic));
451 int lineno = ic->lineno;
456 /* remove it from the iCode */
457 remiCodeFromeBBlock (ebp, ic);
459 /* depending on the type */
460 for (bwd = 0; bwd < 3; bwd++)
462 for (su = 0; su < 2; su++)
464 if (compareType (type, __multypes[bwd][su]) == 1)
466 func = __conv[1][bwd][su];
474 /* if float support routines NOT compiled as reentrant */
475 if (!options.float_rent)
478 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
479 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
480 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
484 newic = newiCode ('=', NULL, IC_RIGHT (ic));
485 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
487 addiCodeToeBBlock (ebp, newic, ip);
488 newic->lineno = lineno;
495 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
496 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
497 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
501 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
503 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
505 addiCodeToeBBlock (ebp, newic, ip);
506 newic->lineno = lineno;
511 newic = newiCode (CALL, operandFromSymbol (func), NULL);
512 IC_RESULT (newic) = IC_RESULT (ic);
513 newic->parmBytes+=bytesPushed;
516 FUNC_HASFCALL (currFunc->type) = 1;
518 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
519 /* normally these functions aren't marked external, so we can use their
520 * _extern field to marked as already added to symbol table */
522 if(!SPEC_EXTR(func->etype)) {
523 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
525 SPEC_EXTR(func->etype) = 1;
526 seg = SPEC_OCLS( func->etype );
527 addSet(&seg->syms, func);
531 addiCodeToeBBlock (ebp, newic, ip);
532 newic->lineno = lineno;
535 /*--------------------------------------------------------------------------*/
536 /* cnvFromFixed16x16Cast - converts casts from fixed16x16 to function calls */
537 /*--------------------------------------------------------------------------*/
539 cnvFromFixed16x16Cast (iCode * ic, eBBlock * ebp)
543 sym_link *type = operandType (IC_LEFT (ic));
544 int lineno = ic->lineno;
549 /* remove it from the iCode */
550 remiCodeFromeBBlock (ebp, ic);
552 /* depending on the type */
553 for (bwd = 0; bwd < 3; bwd++)
555 for (su = 0; su < 2; su++)
557 if (compareType (type, __multypes[bwd][su]) == 1)
559 func = __fp16x16conv[1][bwd][su];
565 if (compareType (type, floatType) == 1)
567 func = __fp16x16conv[1][3][0];
574 /* if float support routines NOT compiled as reentrant */
575 if (!options.float_rent)
578 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
579 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
580 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
584 newic = newiCode ('=', NULL, IC_RIGHT (ic));
585 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
587 addiCodeToeBBlock (ebp, newic, ip);
588 newic->lineno = lineno;
595 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
596 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
597 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
601 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
603 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
605 addiCodeToeBBlock (ebp, newic, ip);
606 newic->lineno = lineno;
611 newic = newiCode (CALL, operandFromSymbol (func), NULL);
612 IC_RESULT (newic) = IC_RESULT (ic);
613 newic->parmBytes+=bytesPushed;
616 FUNC_HASFCALL (currFunc->type) = 1;
618 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
619 /* normally these functions aren't marked external, so we can use their
620 * _extern field to marked as already added to symbol table */
622 if(!SPEC_EXTR(func->etype)) {
623 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
625 SPEC_EXTR(func->etype) = 1;
626 seg = SPEC_OCLS( func->etype );
627 addSet(&seg->syms, func);
631 addiCodeToeBBlock (ebp, newic, ip);
632 newic->lineno = lineno;
635 extern operand *geniCodeRValue (operand *, bool);
637 /*-----------------------------------------------------------------*/
638 /* convilong - converts int or long mults or divs to fcalls */
639 /*-----------------------------------------------------------------*/
641 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
644 iCode *ip = ic->next;
646 int lineno = ic->lineno;
651 remiCodeFromeBBlock (ebp, ic);
653 /* depending on the type */
654 for (bwd = 0; bwd < 3; bwd++)
656 for (su = 0; su < 2; su++)
658 if (compareType (type, __multypes[bwd][su]) == 1)
661 func = __muldiv[0][bwd][su];
663 func = __muldiv[1][bwd][su];
665 func = __muldiv[2][bwd][su];
667 func = __rlrr[1][bwd][su];
669 func = __rlrr[0][bwd][su];
670 else if (op == RIGHT_OP)
671 func = __rlrr[1][bwd][su];
672 else if (op == LEFT_OP)
673 func = __rlrr[0][bwd][su];
682 /* if int & long support routines NOT compiled as reentrant */
683 if (!options.intlong_rent)
686 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
687 newic = newiCode (SEND, IC_LEFT (ic), NULL);
688 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
692 newic = newiCode ('=', NULL, IC_LEFT (ic));
693 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
695 addiCodeToeBBlock (ebp, newic, ip);
696 newic->lineno = lineno;
699 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
700 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
701 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
705 newic = newiCode ('=', NULL, IC_RIGHT (ic));
706 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
708 addiCodeToeBBlock (ebp, newic, ip);
709 newic->lineno = lineno;
714 /* compiled as reentrant then push */
716 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
718 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
719 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
723 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
726 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
728 addiCodeToeBBlock (ebp, newic, ip);
729 newic->lineno = lineno;
731 /* insert push left */
732 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
734 newic = newiCode (SEND, IC_LEFT (ic), NULL);
735 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
739 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
742 bytesPushed += getSize(operandType(IC_LEFT(ic)));
744 addiCodeToeBBlock (ebp, newic, ip);
745 newic->lineno = lineno;
750 newic = newiCode (CALL, operandFromSymbol (func), NULL);
751 IC_RESULT (newic) = IC_RESULT (ic);
752 newic->lineno = lineno;
753 newic->parmBytes+=bytesPushed; // to clear the stack after the call
756 FUNC_HASFCALL (currFunc->type) = 1;
758 if(TARGET_IS_PIC || TARGET_IS_PIC16) {
759 /* normally these functions aren't marked external, so we can use their
760 * _extern field to marked as already added to symbol table */
762 if(!SPEC_EXTR(func->etype)) {
763 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
765 SPEC_EXTR(func->etype) = 1;
766 seg = SPEC_OCLS( func->etype );
767 addSet(&seg->syms, func);
771 addiCodeToeBBlock (ebp, newic, ip);
774 /*-----------------------------------------------------------------*/
775 /* convertToFcall - converts some operations to fcalls */
776 /*-----------------------------------------------------------------*/
778 convertToFcall (eBBlock ** ebbs, int count)
782 /* for all blocks do */
783 for (i = 0; i < count; i++)
787 /* for all instructions in the block do */
788 for (ic = ebbs[i]->sch; ic; ic = ic->next)
791 /* floating point operations are
792 converted to function calls */
793 if ((IS_CONDITIONAL (ic) ||
794 IS_ARITHMETIC_OP (ic)) &&
795 (IS_FLOAT (operandType (IC_RIGHT (ic))) ||
796 IS_FIXED( operandType (IC_RIGHT (ic)))))
798 cnvToFcall (ic, ebbs[i]);
801 /* casting is a little different */
804 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
805 cnvFromFloatCast (ic, ebbs[i]);
806 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
807 cnvToFloatCast (ic, ebbs[i]);
808 if (IS_FIXED16X16 (operandType (IC_RIGHT (ic))))
809 cnvFromFixed16x16Cast (ic, ebbs[i]);
810 else if (IS_FIXED16X16 (operandType (IC_LEFT (ic))))
811 cnvToFixed16x16Cast (ic, ebbs[i]);
814 // Easy special case which avoids function call: modulo by a literal power
815 // of two can be replaced by a bitwise AND.
816 if (ic->op == '%' && isOperandLiteral(IC_RIGHT(ic)) &&
817 IS_UNSIGNED(operandType(IC_LEFT(ic))))
819 unsigned litVal = abs((unsigned)operandLitValue(IC_RIGHT(ic)));
821 /* modulo by 1: no remainder */
825 IC_RIGHT (ic) = operandFromLit(0);
829 // See if literal value is a power of 2.
830 while (litVal && !(litVal & 1))
836 // discard lowest set bit.
843 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
848 /* if long / int mult or divide or mod */
849 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
851 sym_link *leftType = operandType (IC_LEFT (ic));
853 if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
855 sym_link *rightType = operandType (IC_RIGHT (ic));
857 if (port->hasNativeMulFor != NULL &&
858 port->hasNativeMulFor (ic, leftType, rightType))
860 /* Leave as native */
864 convilong (ic, ebbs[i], leftType, ic->op);
869 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
871 sym_link *type = operandType (IC_LEFT (ic));
873 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
875 convilong (ic, ebbs[i], type, ic->op);
882 /*-----------------------------------------------------------------*/
883 /* isLocalWithoutDef - return 1 if sym might be used without a */
885 /*-----------------------------------------------------------------*/
887 isLocalWithoutDef (symbol * sym)
892 if (IS_VOLATILE (sym->type))
898 if (IS_AGGREGATE (sym->type))
907 /*-----------------------------------------------------------------*/
908 /* replaceRegEqv - replace all local variables with their reqv */
909 /*-----------------------------------------------------------------*/
911 replaceRegEqv (ebbIndex * ebbi)
913 eBBlock ** ebbs = ebbi->bbOrder;
914 int count = ebbi->count;
917 /* Update the symbols' def bitvector so we know if there is */
918 /* a defining iCode or not. Only replace a local variable */
919 /* with its register equivalent if there is a defining iCode; */
920 /* otherwise, the port's register allocater may choke. */
921 cseAllBlocks (ebbi, TRUE);
923 for (i = 0; i < count; i++)
928 for (ic = ebbs[i]->sch; ic; ic = ic->next)
937 IS_TRUE_SYMOP (IC_COND (ic)) &&
938 isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
940 werrorfl (ic->filename, ic->lineno,
942 OP_SYMBOL (IC_COND (ic))->name);
943 OP_REQV (IC_COND (ic)) = NULL;
944 OP_SYMBOL (IC_COND (ic))->allocreq = 1;
947 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
948 OP_REQV (IC_COND (ic)))
949 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
950 OP_SYMBOL (IC_COND (ic))->defs,
951 OP_SYMBOL (IC_COND (ic))->uses);
957 if (ic->op == JUMPTABLE)
959 if (IC_JTCOND (ic) &&
960 IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
961 isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
963 werrorfl (ic->filename, ic->lineno,
965 OP_SYMBOL (IC_JTCOND (ic))->name);
966 OP_REQV (IC_JTCOND (ic)) = NULL;
967 OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
970 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
971 OP_REQV (IC_JTCOND (ic)))
972 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
973 OP_SYMBOL (IC_JTCOND (ic))->defs,
974 OP_SYMBOL (IC_JTCOND (ic))->uses);
978 if (ic->op == RECEIVE)
980 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
981 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
985 if (IC_RESULT (ic) &&
986 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
987 OP_REQV (IC_RESULT (ic)))
989 if (POINTER_SET (ic))
991 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
992 OP_SYMBOL (IC_RESULT (ic))->defs,
993 OP_SYMBOL (IC_RESULT (ic))->uses);
994 IC_RESULT (ic)->isaddr = 1;
997 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
998 OP_SYMBOL (IC_RESULT (ic))->defs,
999 OP_SYMBOL (IC_RESULT (ic))->uses);
1002 if (IC_RIGHT (ic) &&
1003 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
1004 isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
1006 werrorfl (ic->filename, ic->lineno,
1008 OP_SYMBOL (IC_RIGHT (ic))->name);
1009 OP_REQV (IC_RIGHT (ic)) = NULL;
1010 OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
1013 if (IC_RIGHT (ic) &&
1014 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
1015 OP_REQV (IC_RIGHT (ic)))
1017 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
1018 OP_SYMBOL (IC_RIGHT (ic))->defs,
1019 OP_SYMBOL (IC_RIGHT (ic))->uses);
1020 IC_RIGHT (ic)->isaddr = 0;
1024 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
1025 isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
1027 werrorfl (ic->filename, ic->lineno,
1029 OP_SYMBOL (IC_LEFT (ic))->name);
1030 OP_REQV (IC_LEFT (ic)) = NULL;
1031 OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
1035 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
1036 OP_REQV (IC_LEFT (ic)))
1038 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
1039 OP_SYMBOL (IC_LEFT (ic))->defs,
1040 OP_SYMBOL (IC_LEFT (ic))->uses);
1041 IC_LEFT (ic)->isaddr = 0;
1047 /*-----------------------------------------------------------------*/
1048 /* findReqv - search for a register equivalent */
1049 /*-----------------------------------------------------------------*/
1051 findReqv (symbol * prereqv, eBBlock ** ebbs, int count)
1056 /* for all blocks do */
1057 for (i=0; i<count; i++)
1059 /* for all instructions in the block do */
1060 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1064 if (IS_ITEMP (IC_COND (ic))
1065 && OP_SYMBOL (IC_COND (ic))->prereqv == prereqv)
1066 return IC_COND (ic);
1068 else if (ic->op == JUMPTABLE)
1070 if (IS_ITEMP (IC_JTCOND (ic))
1071 && OP_SYMBOL (IC_JTCOND (ic))->prereqv == prereqv)
1072 return IC_JTCOND (ic);
1076 if (IS_ITEMP (IC_LEFT (ic))
1077 && OP_SYMBOL (IC_LEFT (ic))->prereqv == prereqv)
1078 return IC_LEFT (ic);
1079 if (IS_ITEMP (IC_RIGHT (ic))
1080 && OP_SYMBOL (IC_RIGHT (ic))->prereqv == prereqv)
1081 return IC_RIGHT (ic);
1082 if (IS_ITEMP (IC_RESULT (ic))
1083 && OP_SYMBOL (IC_RESULT (ic))->prereqv == prereqv)
1084 return IC_RESULT (ic);
1092 /*-----------------------------------------------------------------*/
1093 /* killDeadCode - eliminates dead assignments */
1094 /*-----------------------------------------------------------------*/
1096 killDeadCode (ebbIndex * ebbi)
1098 eBBlock ** ebbs = ebbi->dfOrder;
1099 int count = ebbi->count;
1105 /* basic algorithm :- */
1106 /* first the exclusion rules :- */
1107 /* 1. if result is a global or volatile then skip */
1108 /* 2. if assignment and result is a temp & isaddr then skip */
1109 /* since this means array & pointer access, will be taken */
1110 /* care of by alias analysis. */
1111 /* 3. if the result is used in the remainder of the block skip */
1112 /* 4. if this definition does not reach the end of the block */
1113 /* i.e. the result is not present in the outExprs then KILL */
1114 /* 5. if it reaches the end of block & is used by some success */
1117 /* this whole process is carried on iteratively till no change */
1122 /* for all blocks do */
1123 for (i = 0; i < count; i++)
1127 /* for all instructions in the block do */
1128 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1136 ic->op == DUMMY_READ_VOLATILE ||
1137 ic->op == CRITICAL ||
1138 ic->op == ENDCRITICAL)
1141 /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
1142 /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are */
1145 /* if the result is volatile then continue */
1146 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
1149 /* if the result is a temp & isaddr then skip */
1150 if (IC_RESULT (ic) && POINTER_SET (ic))
1153 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next)
1154 && !SPIL_LOC (IC_RESULT (ic)))
1157 /* if the result is used in the remainder of the */
1158 /* block then skip */
1159 if (usedInRemaining (IC_RESULT (ic), ic->next))
1162 /* does this definition reach the end of the block
1163 or the usage is zero then we can kill */
1164 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
1165 kill = 1; /* if not we can kill it */
1168 /* if this is a global variable or function parameter */
1169 /* we cannot kill anyway */
1170 if (isOperandGlobal (IC_RESULT (ic)) ||
1171 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1172 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
1175 /* if we are sure there are no usages */
1176 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
1182 /* reset visited flag */
1183 for (j = 0; j < count; ebbs[j++]->visited = 0);
1185 /* find out if this definition is alive */
1186 if (applyToSet (ebbs[i]->succList,
1195 /* kill this one if required */
1198 bool volLeft = IS_SYMOP (IC_LEFT (ic))
1199 && isOperandVolatile (IC_LEFT (ic), FALSE);
1200 bool volRight = IS_SYMOP (IC_RIGHT (ic))
1201 && isOperandVolatile (IC_RIGHT (ic), FALSE);
1203 /* a dead address-of operation should die, even if volatile */
1204 if (ic->op == ADDRESS_OF)
1207 if (ic->next && ic->seqPoint == ic->next->seqPoint
1208 && (ic->next->op == '+' || ic->next->op == '-'))
1210 if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
1211 || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
1213 if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
1214 || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
1218 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
1220 if (SPIL_LOC (IC_RESULT (ic)))
1222 IC_RESULT (ic) = newiTempFromOp (IC_RESULT (ic));
1223 SPIL_LOC (IC_RESULT (ic)) = NULL;
1231 /* now delete from defUseSet */
1232 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
1233 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
1235 /* and defset of the block */
1236 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
1238 /* If this is the last of a register equivalent, */
1239 /* look for a successor register equivalent. */
1240 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1241 if (IS_ITEMP (IC_RESULT (ic))
1242 && OP_SYMBOL (IC_RESULT (ic))->isreqv
1243 && bitVectIsZero (OP_DEFS (IC_RESULT (ic))))
1245 symbol * resultsym = OP_SYMBOL (IC_RESULT (ic));
1246 symbol * prereqv = resultsym->prereqv;
1248 if (prereqv && prereqv->reqv && (OP_SYMBOL (prereqv->reqv) == resultsym))
1252 IC_RESULT (ic) = NULL;
1253 newreqv = findReqv (prereqv, ebbs, count);
1256 prereqv->reqv = newreqv;
1261 /* delete the result */
1262 IC_RESULT (ic) = NULL;
1264 if (volLeft || volRight)
1266 /* something is volatile, so keep the iCode */
1267 /* and change the operator instead */
1268 ic->op = DUMMY_READ_VOLATILE;
1270 /* keep only the volatile operands */
1272 IC_LEFT (ic) = NULL;
1274 IC_RIGHT (ic) = NULL;
1278 /* nothing is volatile, eliminate the iCode */
1279 remiCodeFromeBBlock (ebbs[i], ic);
1281 /* for the left & right remove the usage */
1282 if (IS_SYMOP (IC_LEFT (ic)))
1283 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1285 if (IS_SYMOP (IC_RIGHT (ic)))
1286 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1290 } /* end of all instructions */
1292 if (!ebbs[i]->sch && !ebbs[i]->noPath)
1293 disconBBlock (ebbs[i], ebbi);
1295 } /* end of for all blocks */
1299 } /* end of while(1) */
1304 /*-----------------------------------------------------------------*/
1305 /* printCyclomatic - prints the cyclomatic information */
1306 /*-----------------------------------------------------------------*/
1308 printCyclomatic (eBBlock ** ebbs, int count)
1310 int nEdges = elementsInSet (graphEdges);
1313 for (i = 0; i < count; i++)
1314 nNodes += (!ebbs[i]->noPath);
1316 /* print the information */
1317 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
1320 /*-----------------------------------------------------------------*/
1321 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
1322 /* refer to dead variables. */
1323 /*-----------------------------------------------------------------*/
1325 discardDeadParamReceives (eBBlock ** ebbs, int count)
1331 for (i = 0; i < count; i++)
1333 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1335 if (ic->op == RECEIVE)
1337 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
1338 && !OP_SYMBOL (IC_RESULT (ic))->used)
1341 fprintf (stderr, "discarding dead receive for %s\n",
1342 OP_SYMBOL (IC_RESULT (ic))->name);
1344 dummyIcode.next = ic->next;
1345 remiCodeFromeBBlock (ebbs[i], ic);
1353 /*-----------------------------------------------------------------*/
1354 /* optimizeCastCast - remove unneeded intermediate casts. */
1355 /* Integer promotion may cast (un)signed char to int and then */
1356 /* recast the int to (un)signed long. If the signedness of the */
1357 /* char and long are the same, the cast can be safely performed in */
1358 /* a single step. */
1359 /*-----------------------------------------------------------------*/
1361 optimizeCastCast (eBBlock ** ebbs, int count)
1371 for (i = 0; i < count; i++)
1373 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1376 if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1378 type1 = operandType (IC_RIGHT (ic));
1379 type2 = operandType (IC_RESULT (ic));
1381 /* Look only for a cast from an integer type to an */
1382 /* integer type that has no loss of bits */
1383 if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1385 if (getSize (type2) < getSize (type1))
1388 /* There must be only one use of this first result */
1389 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1392 /* This use must be a second cast */
1393 uic = hTabItemWithKey (iCodehTab,
1394 bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1395 if (!uic || uic->op != CAST)
1398 /* It must be a cast to another integer type that */
1399 /* has no loss of bits */
1400 type3 = operandType (IC_RESULT (uic));
1401 if (!IS_INTEGRAL (type3))
1403 if (getSize (type3) < getSize (type2))
1406 /* The signedness between the first and last types */
1408 if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1411 /* Change the first cast to a simple assignment and */
1412 /* let the second cast do all the work */
1414 IC_LEFT (ic) = NULL;
1415 sym = OP_SYMBOL (IC_RESULT (ic));
1416 sym->type = copyLinkChain (type1);
1417 sym->etype = getSpec (sym->type);
1423 /*-----------------------------------------------------------------*/
1424 /* eBBlockFromiCode - creates extended basic blocks from iCode */
1425 /* will return an array of eBBlock pointers */
1426 /*-----------------------------------------------------------------*/
1428 eBBlockFromiCode (iCode * ic)
1430 ebbIndex *ebbi = NULL;
1436 /* if nothing passed then return nothing */
1442 /* optimize the chain for labels & gotos
1443 this will eliminate redundant labels and
1444 will change jump to jumps by jumps */
1445 ic = iCodeLabelOptimize (ic);
1447 /* break it down into basic blocks */
1448 ebbi = iCodeBreakDown (ic);
1450 /* hash the iCode keys so that we can quickly index */
1451 /* them in the rest of the optimization steps */
1452 setToNull ((void *) &iCodehTab);
1453 iCodehTab = newHashTable (iCodeKey);
1454 hashiCodeKeys (ebbi->bbOrder, ebbi->count);
1456 /* compute the control flow */
1457 computeControlFlow (ebbi);
1459 /* dumpraw if asked for */
1460 if (options.dump_raw)
1461 dumpEbbsToFileExt (DUMP_RAW0, ebbi);
1463 /* replace the local variables with their
1464 register equivalents : the liveRange computation
1465 along with the register allocation will determine
1466 if it finally stays in the registers */
1467 replaceRegEqv (ebbi);
1469 /* create loop regions */
1470 loops = createLoopRegions (ebbi);
1472 /* dumpraw if asked for */
1473 if (options.dump_raw)
1474 dumpEbbsToFileExt (DUMP_RAW1, ebbi);
1476 optimizeCastCast (ebbi->bbOrder, ebbi->count);
1478 /* do common subexpression elimination for each block */
1479 change = cseAllBlocks (ebbi, FALSE);
1481 /* dumpraw if asked for */
1482 if (options.dump_raw)
1483 dumpEbbsToFileExt (DUMP_CSE, ebbi);
1485 /* compute the data flow */
1486 computeDataFlow (ebbi);
1488 /* dumpraw if asked for */
1489 if (options.dump_raw)
1490 dumpEbbsToFileExt (DUMP_DFLOW, ebbi);
1492 /* global common subexpression elimination */
1493 if (optimize.global_cse)
1495 change += cseAllBlocks (ebbi, FALSE);
1496 if (options.dump_gcse)
1497 dumpEbbsToFileExt (DUMP_GCSE, ebbi);
1501 // compute the dataflow only
1502 assert(cseAllBlocks (ebbi, TRUE)==0);
1504 /* kill dead code */
1505 kchange = killDeadCode (ebbi);
1507 if (options.dump_kill)
1508 dumpEbbsToFileExt (DUMP_DEADCODE, ebbi);
1510 /* do loop optimizations */
1511 change += (lchange = loopOptimizations (loops, ebbi));
1512 if (options.dump_loop)
1513 dumpEbbsToFileExt (DUMP_LOOP, ebbi);
1515 /* recompute the data flow and apply global cse again
1516 if loops optimizations or dead code caused a change:
1517 loops will brings out of the loop which then may be
1518 available for use in the later blocks: dead code
1519 elimination could potentially disconnect some blocks
1520 conditional flow may be efected so we need to apply
1521 subexpression once more */
1522 if (lchange || kchange)
1524 computeDataFlow (ebbi);
1525 change += cseAllBlocks (ebbi, FALSE);
1526 if (options.dump_loop)
1527 dumpEbbsToFileExt (DUMP_LOOPG, ebbi);
1529 /* if loop optimizations caused a change then do
1530 dead code elimination once more : this will
1531 get rid of the extra assignments to the induction
1532 variables created during loop optimizations */
1533 killDeadCode (ebbi);
1535 if (options.dump_loop)
1536 dumpEbbsToFileExt (DUMP_LOOPD, ebbi);
1540 /* sort it back by block number */
1541 //qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1543 if (!options.lessPedantic) {
1544 // this is a good place to check missing return values
1546 // the user is on his own with naked functions...
1547 if (!IS_VOID(currFunc->etype)
1548 && !FUNC_ISNAKED(currFunc->type)) {
1550 // make sure all predecessors of the last block end in a return
1551 for (bp=setFirstItem(ebbi->bbOrder[ebbi->count-1]->predList);
1553 bp=setNextItem(ebbi->bbOrder[ebbi->count-1]->predList)) {
1554 if (bp->ech->op != RETURN) {
1555 werrorfl (bp->ech->filename, bp->ech->lineno,
1556 W_VOID_FUNC, currFunc->name);
1563 /* if cyclomatic info requested then print it */
1564 if (options.cyclomatic)
1565 printCyclomatic (ebbi->bbOrder, ebbi->count);
1567 /* convert operations with support routines
1568 written in C to function calls : I am doing
1569 this at this point since I want all the
1570 operations to be as they are for optimizations */
1571 convertToFcall (ebbi->bbOrder, ebbi->count);
1573 /* compute the live ranges */
1574 computeLiveRanges (ebbi->bbOrder, ebbi->count, TRUE);
1576 if (options.dump_range)
1577 dumpEbbsToFileExt (DUMP_RANGE, ebbi);
1579 /* Now that we have the live ranges, discard parameter
1580 * receives for unused parameters.
1582 discardDeadParamReceives (ebbi->bbOrder, ebbi->count);
1584 /* allocate registers & generate code */
1585 port->assignRegisters (ebbi);
1587 /* throw away blocks */
1588 setToNull ((void *) &graphEdges);
1594 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */