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 char *filename = ic->filename;
62 int lineno = ic->lineno;
65 ip = ic->next; /* insertion point */
66 /* remove it from the iCode */
67 remiCodeFromeBBlock (ebp, ic);
70 right = IC_RIGHT (ic);
73 bitVectUnSetBit (OP_USES (left), ic->key);
75 bitVectUnSetBit (OP_USES (right), ic->key);
77 if (IS_FLOAT (operandType (right))) {
112 if (IS_FIXED16X16 (operandType (right))) {
116 func = __fps16x16_add;
119 func = __fps16x16_sub;
122 func = __fps16x16_div;
125 func = __fps16x16_mul;
128 func = __fps16x16_eq;
131 func = __fps16x16_neq;
134 func = __fps16x16_lt;
137 func = __fps16x16_gt;
140 func = __fps16x16_lteq;
143 func = __fps16x16_gteq;
149 /* if float support routines NOT compiled as reentrant */
150 if (!options.float_rent)
154 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
156 newic = newiCode (SEND, left, NULL);
157 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
161 newic = newiCode ('=', NULL, left);
162 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
165 addiCodeToeBBlock (ebp, newic, ip);
166 newic->filename = filename;
167 newic->lineno = lineno;
169 OP_USES (left) = bitVectSetBit (OP_USES (left), newic->key);
172 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
174 newic = newiCode (SEND, right, NULL);
175 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
179 newic = newiCode ('=', NULL, right);
180 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
182 addiCodeToeBBlock (ebp, newic, ip);
183 newic->filename = filename;
184 newic->lineno = lineno;
185 if (IS_SYMOP (right))
186 OP_USES (right) = bitVectSetBit (OP_USES (right), newic->key);
193 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
195 newic = newiCode (SEND, right, NULL);
196 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
200 newic = newiCode (IPUSH, right, NULL);
202 bytesPushed += getSize(operandType(right));
205 addiCodeToeBBlock (ebp, newic, ip);
206 newic->filename = filename;
207 newic->lineno = lineno;
208 if (IS_SYMOP (right))
209 OP_USES (right) = bitVectSetBit (OP_USES (right), newic->key);
211 /* insert push left */
212 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
214 newic = newiCode (SEND, left, NULL);
215 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
219 newic = newiCode (IPUSH, left, NULL);
221 bytesPushed += getSize(operandType(left));
223 addiCodeToeBBlock (ebp, newic, ip);
224 newic->filename = filename;
225 newic->lineno = lineno;
227 OP_USES (left) = bitVectSetBit (OP_USES (left), newic->key);
230 /* insert the call */
231 newic = newiCode (CALL, operandFromSymbol (func), NULL);
232 IC_RESULT (newic) = IC_RESULT (ic);
233 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
234 OP_USES (IC_RESULT (newic)) = bitVectSetBit (OP_USES (IC_RESULT (newic)), newic->key);
235 newic->filename = filename;
236 newic->lineno = lineno;
237 newic->parmBytes += bytesPushed;
240 FUNC_HASFCALL (currFunc->type) = 1;
242 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
243 /* normally these functions aren't marked external, so we can use their
244 * _extern field to marked as already added to symbol table */
246 if(!SPEC_EXTR(func->etype)) {
247 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
249 SPEC_EXTR(func->etype) = 1;
250 seg = SPEC_OCLS( func->etype );
251 addSet(&seg->syms, func);
255 addiCodeToeBBlock (ebp, newic, ip);
258 /*-----------------------------------------------------------------*/
259 /* cnvToFloatCast - converts casts to floats to function calls */
260 /*-----------------------------------------------------------------*/
262 cnvToFloatCast (iCode * ic, eBBlock * ebp)
266 sym_link *type = operandType (IC_RIGHT (ic));
267 int linenno = ic->lineno;
272 /* remove it from the iCode */
273 remiCodeFromeBBlock (ebp, ic);
274 /* depending on the type */
275 for (bwd = 0; bwd < 3; bwd++)
277 for (su = 0; su < 2; su++)
279 if (compareType (type, __multypes[bwd][su]) == 1)
281 func = __conv[0][bwd][su];
287 if(compareType (type, fixed16x16Type) == 1) {
288 func = __fp16x16conv[0][3][0];
295 /* if float support routines NOT compiled as reentrant */
296 if (!options.float_rent)
299 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
301 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
302 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
306 newic = newiCode ('=', NULL, IC_RIGHT (ic));
307 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
309 addiCodeToeBBlock (ebp, newic, ip);
310 newic->filename = filename;
311 newic->lineno = linenno;
317 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
318 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
319 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
323 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
325 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
327 addiCodeToeBBlock (ebp, newic, ip);
328 newic->filename = filename;
329 newic->lineno = linenno;
333 newic = newiCode (CALL, operandFromSymbol (func), NULL);
334 IC_RESULT (newic) = IC_RESULT (ic);
335 newic->parmBytes+=bytesPushed;
338 FUNC_HASFCALL (currFunc->type) = 1;
340 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
341 /* normally these functions aren't marked external, so we can use their
342 * _extern field to marked as already added to symbol table */
344 if(!SPEC_EXTR(func->etype)) {
345 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
347 SPEC_EXTR(func->etype) = 1;
348 seg = SPEC_OCLS( func->etype );
349 addSet(&seg->syms, func);
353 addiCodeToeBBlock (ebp, newic, ip);
354 newic->filename = filename;
355 newic->lineno = linenno;
358 /*----------------------------------------------------------------------*/
359 /* cnvToFixed16x16Cast - converts casts to fixed16x16 to function calls */
360 /*----------------------------------------------------------------------*/
362 cnvToFixed16x16Cast (iCode * ic, eBBlock * ebp)
366 sym_link *type = operandType (IC_RIGHT (ic));
367 int linenno = ic->lineno;
372 /* remove it from the iCode */
373 remiCodeFromeBBlock (ebp, ic);
374 /* depending on the type */
375 for (bwd = 0; bwd < 3; bwd++)
377 for (su = 0; su < 2; su++)
379 if (compareType (type, __multypes[bwd][su]) == 1)
381 func = __fp16x16conv[0][bwd][su];
389 /* if float support routines NOT compiled as reentrant */
390 if (!options.float_rent)
393 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
395 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
396 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
400 newic = newiCode ('=', NULL, IC_RIGHT (ic));
401 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
403 addiCodeToeBBlock (ebp, newic, ip);
404 newic->filename = filename;
405 newic->lineno = linenno;
411 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
412 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
413 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
417 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
419 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
421 addiCodeToeBBlock (ebp, newic, ip);
422 newic->filename = filename;
423 newic->lineno = linenno;
427 newic = newiCode (CALL, operandFromSymbol (func), NULL);
428 IC_RESULT (newic) = IC_RESULT (ic);
429 newic->parmBytes+=bytesPushed;
432 FUNC_HASFCALL (currFunc->type) = 1;
434 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
435 /* normally these functions aren't marked external, so we can use their
436 * _extern field to marked as already added to symbol table */
438 if(!SPEC_EXTR(func->etype)) {
439 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
441 SPEC_EXTR(func->etype) = 1;
442 seg = SPEC_OCLS( func->etype );
443 addSet(&seg->syms, func);
447 addiCodeToeBBlock (ebp, newic, ip);
448 newic->filename = filename;
449 newic->lineno = linenno;
452 /*-----------------------------------------------------------------*/
453 /* cnvFromFloatCast - converts casts From floats to function calls */
454 /*-----------------------------------------------------------------*/
456 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
460 sym_link *type = operandType (IC_LEFT (ic));
461 char *filename = ic->filename;
462 int lineno = ic->lineno;
467 /* remove it from the iCode */
468 remiCodeFromeBBlock (ebp, ic);
470 /* depending on the type */
471 for (bwd = 0; bwd < 3; bwd++)
473 for (su = 0; su < 2; su++)
475 if (compareType (type, __multypes[bwd][su]) == 1)
477 func = __conv[1][bwd][su];
485 /* if float support routines NOT compiled as reentrant */
486 if (!options.float_rent)
489 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
490 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
491 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
495 newic = newiCode ('=', NULL, IC_RIGHT (ic));
496 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
498 addiCodeToeBBlock (ebp, newic, ip);
499 newic->filename = filename;
500 newic->lineno = lineno;
507 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
508 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
509 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
513 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
515 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
517 addiCodeToeBBlock (ebp, newic, ip);
518 newic->filename = filename;
519 newic->lineno = lineno;
524 newic = newiCode (CALL, operandFromSymbol (func), NULL);
525 IC_RESULT (newic) = IC_RESULT (ic);
526 newic->parmBytes+=bytesPushed;
529 FUNC_HASFCALL (currFunc->type) = 1;
531 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
532 /* normally these functions aren't marked external, so we can use their
533 * _extern field to marked as already added to symbol table */
535 if(!SPEC_EXTR(func->etype)) {
536 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
538 SPEC_EXTR(func->etype) = 1;
539 seg = SPEC_OCLS( func->etype );
540 addSet(&seg->syms, func);
544 addiCodeToeBBlock (ebp, newic, ip);
545 newic->filename = filename;
546 newic->lineno = lineno;
549 /*--------------------------------------------------------------------------*/
550 /* cnvFromFixed16x16Cast - converts casts from fixed16x16 to function calls */
551 /*--------------------------------------------------------------------------*/
553 cnvFromFixed16x16Cast (iCode * ic, eBBlock * ebp)
557 sym_link *type = operandType (IC_LEFT (ic));
558 char *filename = ic->filename;
559 int lineno = ic->lineno;
564 /* remove it from the iCode */
565 remiCodeFromeBBlock (ebp, ic);
567 /* depending on the type */
568 for (bwd = 0; bwd < 3; bwd++)
570 for (su = 0; su < 2; su++)
572 if (compareType (type, __multypes[bwd][su]) == 1)
574 func = __fp16x16conv[1][bwd][su];
580 if (compareType (type, floatType) == 1)
582 func = __fp16x16conv[1][3][0];
589 /* if float support routines NOT compiled as reentrant */
590 if (!options.float_rent)
593 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
594 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
595 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
599 newic = newiCode ('=', NULL, IC_RIGHT (ic));
600 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
602 addiCodeToeBBlock (ebp, newic, ip);
603 newic->filename = filename;
604 newic->lineno = lineno;
610 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
611 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
612 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
616 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
618 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
620 addiCodeToeBBlock (ebp, newic, ip);
621 newic->filename = filename;
622 newic->lineno = lineno;
626 newic = newiCode (CALL, operandFromSymbol (func), NULL);
627 IC_RESULT (newic) = IC_RESULT (ic);
628 newic->parmBytes+=bytesPushed;
631 FUNC_HASFCALL (currFunc->type) = 1;
633 if(TARGET_IS_PIC16 || TARGET_IS_PIC) {
634 /* normally these functions aren't marked external, so we can use their
635 * _extern field to marked as already added to symbol table */
637 if(!SPEC_EXTR(func->etype)) {
638 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
640 SPEC_EXTR(func->etype) = 1;
641 seg = SPEC_OCLS( func->etype );
642 addSet(&seg->syms, func);
646 addiCodeToeBBlock (ebp, newic, ip);
647 newic->filename = filename;
648 newic->lineno = lineno;
651 extern operand *geniCodeRValue (operand *, bool);
653 /*-----------------------------------------------------------------*/
654 /* convilong - converts int or long mults or divs to fcalls */
655 /*-----------------------------------------------------------------*/
657 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
660 iCode *ip = ic->next;
662 char *filename = ic->filename;
663 int lineno = ic->lineno;
668 remiCodeFromeBBlock (ebp, ic);
670 /* depending on the type */
671 for (bwd = 0; bwd < 3; bwd++)
673 for (su = 0; su < 2; su++)
675 if (compareType (type, __multypes[bwd][su]) == 1)
678 func = __muldiv[0][bwd][su];
680 func = __muldiv[1][bwd][su];
682 func = __muldiv[2][bwd][su];
684 func = __rlrr[1][bwd][su];
686 func = __rlrr[0][bwd][su];
687 else if (op == RIGHT_OP)
688 func = __rlrr[1][bwd][su];
689 else if (op == LEFT_OP)
690 func = __rlrr[0][bwd][su];
699 /* if int & long support routines NOT compiled as reentrant */
700 if (!options.intlong_rent)
703 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
704 newic = newiCode (SEND, IC_LEFT (ic), NULL);
705 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
709 newic = newiCode ('=', NULL, IC_LEFT (ic));
710 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
712 addiCodeToeBBlock (ebp, newic, ip);
713 newic->filename = filename;
714 newic->lineno = lineno;
717 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 ('=', NULL, IC_RIGHT (ic));
724 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
726 addiCodeToeBBlock (ebp, newic, ip);
727 newic->filename = filename;
728 newic->lineno = lineno;
733 /* compiled as reentrant then push */
735 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
737 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
738 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
742 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
745 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
747 addiCodeToeBBlock (ebp, newic, ip);
748 newic->filename = filename;
749 newic->lineno = lineno;
751 /* insert push left */
752 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
754 newic = newiCode (SEND, IC_LEFT (ic), NULL);
755 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
759 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
762 bytesPushed += getSize(operandType(IC_LEFT(ic)));
764 addiCodeToeBBlock (ebp, newic, ip);
765 newic->filename = filename;
766 newic->lineno = lineno;
771 newic = newiCode (CALL, operandFromSymbol (func), NULL);
772 IC_RESULT (newic) = IC_RESULT (ic);
773 newic->filename = filename;
774 newic->lineno = lineno;
775 newic->parmBytes+=bytesPushed; // to clear the stack after the call
778 FUNC_HASFCALL (currFunc->type) = 1;
780 if(TARGET_IS_PIC || TARGET_IS_PIC16) {
781 /* normally these functions aren't marked external, so we can use their
782 * _extern field to marked as already added to symbol table */
784 if(!SPEC_EXTR(func->etype)) {
785 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
787 SPEC_EXTR(func->etype) = 1;
788 seg = SPEC_OCLS( func->etype );
789 addSet(&seg->syms, func);
793 addiCodeToeBBlock (ebp, newic, ip);
796 /*-----------------------------------------------------------------*/
797 /* convertToFcall - converts some operations to fcalls */
798 /*-----------------------------------------------------------------*/
800 convertToFcall (eBBlock ** ebbs, int count)
804 /* for all blocks do */
805 for (i = 0; i < count; i++)
809 /* for all instructions in the block do */
810 for (ic = ebbs[i]->sch; ic; ic = ic->next)
813 /* floating point operations are
814 converted to function calls */
815 if ((IS_CONDITIONAL (ic) ||
816 IS_ARITHMETIC_OP (ic)) &&
817 (IS_FLOAT (operandType (IC_RIGHT (ic))) ||
818 IS_FIXED( operandType (IC_RIGHT (ic)))))
820 cnvToFcall (ic, ebbs[i]);
823 /* casting is a little different */
826 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
827 cnvFromFloatCast (ic, ebbs[i]);
828 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
829 cnvToFloatCast (ic, ebbs[i]);
830 if (IS_FIXED16X16 (operandType (IC_RIGHT (ic))))
831 cnvFromFixed16x16Cast (ic, ebbs[i]);
832 else if (IS_FIXED16X16 (operandType (IC_LEFT (ic))))
833 cnvToFixed16x16Cast (ic, ebbs[i]);
836 // Easy special case which avoids function call: modulo by a literal power
837 // of two can be replaced by a bitwise AND.
838 if (ic->op == '%' && isOperandLiteral(IC_RIGHT(ic)) &&
839 IS_UNSIGNED(operandType(IC_LEFT(ic))))
841 unsigned litVal = abs((unsigned) double2ul (operandLitValue(IC_RIGHT(ic))));
843 /* modulo by 1: no remainder */
847 IC_RIGHT (ic) = operandFromLit(0);
851 // See if literal value is a power of 2.
852 while (litVal && !(litVal & 1))
858 // discard lowest set bit.
865 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
870 /* if long / int mult or divide or mod */
871 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
873 sym_link *leftType = operandType (IC_LEFT (ic));
875 if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
877 sym_link *rightType = operandType (IC_RIGHT (ic));
879 if (port->hasNativeMulFor != NULL &&
880 port->hasNativeMulFor (ic, leftType, rightType))
882 /* Leave as native */
886 convilong (ic, ebbs[i], leftType, ic->op);
891 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
893 sym_link *type = operandType (IC_LEFT (ic));
895 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
897 convilong (ic, ebbs[i], type, ic->op);
904 /*-----------------------------------------------------------------*/
905 /* isLocalWithoutDef - return 1 if sym might be used without a */
907 /*-----------------------------------------------------------------*/
909 isLocalWithoutDef (symbol * sym)
914 if (IS_VOLATILE (sym->type))
920 if (IS_AGGREGATE (sym->type))
929 /*-----------------------------------------------------------------*/
930 /* replaceRegEqv - replace all local variables with their reqv */
931 /*-----------------------------------------------------------------*/
933 replaceRegEqv (ebbIndex * ebbi)
935 eBBlock ** ebbs = ebbi->bbOrder;
936 int count = ebbi->count;
939 /* Update the symbols' def bitvector so we know if there is */
940 /* a defining iCode or not. Only replace a local variable */
941 /* with its register equivalent if there is a defining iCode; */
942 /* otherwise, the port's register allocater may choke. */
943 cseAllBlocks (ebbi, TRUE);
945 for (i = 0; i < count; i++)
950 for (ic = ebbs[i]->sch; ic; ic = ic->next)
959 IS_TRUE_SYMOP (IC_COND (ic)) &&
960 isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
962 werrorfl (ic->filename, ic->lineno,
964 OP_SYMBOL (IC_COND (ic))->name);
965 OP_REQV (IC_COND (ic)) = NULL;
966 OP_SYMBOL (IC_COND (ic))->allocreq = 1;
969 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
970 OP_REQV (IC_COND (ic)))
971 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
972 OP_SYMBOL (IC_COND (ic))->defs,
973 OP_SYMBOL (IC_COND (ic))->uses);
979 if (ic->op == JUMPTABLE)
981 if (IC_JTCOND (ic) &&
982 IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
983 isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
985 werrorfl (ic->filename, ic->lineno,
987 OP_SYMBOL (IC_JTCOND (ic))->name);
988 OP_REQV (IC_JTCOND (ic)) = NULL;
989 OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
992 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
993 OP_REQV (IC_JTCOND (ic)))
994 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
995 OP_SYMBOL (IC_JTCOND (ic))->defs,
996 OP_SYMBOL (IC_JTCOND (ic))->uses);
1000 if (ic->op == RECEIVE)
1002 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
1003 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
1007 if (IC_RESULT (ic) &&
1008 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
1009 OP_REQV (IC_RESULT (ic)))
1011 if (POINTER_SET (ic))
1013 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
1014 OP_SYMBOL (IC_RESULT (ic))->defs,
1015 OP_SYMBOL (IC_RESULT (ic))->uses);
1016 IC_RESULT (ic)->isaddr = 1;
1019 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
1020 OP_SYMBOL (IC_RESULT (ic))->defs,
1021 OP_SYMBOL (IC_RESULT (ic))->uses);
1024 if (IC_RIGHT (ic) &&
1025 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
1026 isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
1028 werrorfl (ic->filename, ic->lineno,
1030 OP_SYMBOL (IC_RIGHT (ic))->name);
1031 OP_REQV (IC_RIGHT (ic)) = NULL;
1032 OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
1035 if (IC_RIGHT (ic) &&
1036 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
1037 OP_REQV (IC_RIGHT (ic)))
1039 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
1040 OP_SYMBOL (IC_RIGHT (ic))->defs,
1041 OP_SYMBOL (IC_RIGHT (ic))->uses);
1042 IC_RIGHT (ic)->isaddr = 0;
1046 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
1047 isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
1049 werrorfl (ic->filename, ic->lineno,
1051 OP_SYMBOL (IC_LEFT (ic))->name);
1052 OP_REQV (IC_LEFT (ic)) = NULL;
1053 OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
1057 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
1058 OP_REQV (IC_LEFT (ic)))
1060 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
1061 OP_SYMBOL (IC_LEFT (ic))->defs,
1062 OP_SYMBOL (IC_LEFT (ic))->uses);
1063 IC_LEFT (ic)->isaddr = 0;
1069 /*-----------------------------------------------------------------*/
1070 /* findReqv - search for a register equivalent */
1071 /*-----------------------------------------------------------------*/
1073 findReqv (symbol * prereqv, eBBlock ** ebbs, int count)
1078 /* for all blocks do */
1079 for (i=0; i<count; i++)
1081 /* for all instructions in the block do */
1082 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1086 if (IS_ITEMP (IC_COND (ic))
1087 && OP_SYMBOL (IC_COND (ic))->prereqv == prereqv)
1088 return IC_COND (ic);
1090 else if (ic->op == JUMPTABLE)
1092 if (IS_ITEMP (IC_JTCOND (ic))
1093 && OP_SYMBOL (IC_JTCOND (ic))->prereqv == prereqv)
1094 return IC_JTCOND (ic);
1098 if (IS_ITEMP (IC_LEFT (ic))
1099 && OP_SYMBOL (IC_LEFT (ic))->prereqv == prereqv)
1100 return IC_LEFT (ic);
1101 if (IS_ITEMP (IC_RIGHT (ic))
1102 && OP_SYMBOL (IC_RIGHT (ic))->prereqv == prereqv)
1103 return IC_RIGHT (ic);
1104 if (IS_ITEMP (IC_RESULT (ic))
1105 && OP_SYMBOL (IC_RESULT (ic))->prereqv == prereqv)
1106 return IC_RESULT (ic);
1114 /*-----------------------------------------------------------------*/
1115 /* killDeadCode - eliminates dead assignments */
1116 /*-----------------------------------------------------------------*/
1118 killDeadCode (ebbIndex * ebbi)
1120 eBBlock ** ebbs = ebbi->dfOrder;
1121 int count = ebbi->count;
1127 /* basic algorithm :- */
1128 /* first the exclusion rules :- */
1129 /* 1. if result is a global or volatile then skip */
1130 /* 2. if assignment and result is a temp & isaddr then skip */
1131 /* since this means array & pointer access, will be taken */
1132 /* care of by alias analysis. */
1133 /* 3. if the result is used in the remainder of the block skip */
1134 /* 4. if this definition does not reach the end of the block */
1135 /* i.e. the result is not present in the outExprs then KILL */
1136 /* 5. if it reaches the end of block & is used by some success */
1139 /* this whole process is carried on iteratively till no change */
1144 /* for all blocks do */
1145 for (i = 0; i < count; i++)
1149 /* for all instructions in the block do */
1150 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1158 ic->op == DUMMY_READ_VOLATILE ||
1159 ic->op == CRITICAL ||
1160 ic->op == ENDCRITICAL)
1163 /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
1164 /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are */
1167 /* if the result is volatile then continue */
1168 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
1171 /* if the result is a temp & isaddr then skip */
1172 if (IC_RESULT (ic) && POINTER_SET (ic))
1175 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next)
1176 && !SPIL_LOC (IC_RESULT (ic)))
1179 /* if the result is used in the remainder of the */
1180 /* block then skip */
1181 if (usedInRemaining (IC_RESULT (ic), ic->next))
1184 /* does this definition reach the end of the block
1185 or the usage is zero then we can kill */
1186 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
1187 kill = 1; /* if not we can kill it */
1190 /* if this is a global variable or function parameter */
1191 /* we cannot kill anyway */
1192 if (isOperandGlobal (IC_RESULT (ic)) ||
1193 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1194 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
1197 /* if we are sure there are no usages */
1198 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
1204 /* reset visited flag */
1205 for (j = 0; j < count; ebbs[j++]->visited = 0);
1207 /* find out if this definition is alive */
1208 if (applyToSet (ebbs[i]->succList,
1217 /* kill this one if required */
1220 bool volLeft = IS_SYMOP (IC_LEFT (ic))
1221 && isOperandVolatile (IC_LEFT (ic), FALSE);
1222 bool volRight = IS_SYMOP (IC_RIGHT (ic))
1223 && isOperandVolatile (IC_RIGHT (ic), FALSE);
1225 /* a dead address-of operation should die, even if volatile */
1226 if (ic->op == ADDRESS_OF)
1229 if (ic->next && ic->seqPoint == ic->next->seqPoint
1230 && (ic->next->op == '+' || ic->next->op == '-'))
1232 if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
1233 || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
1235 if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
1236 || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
1240 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
1242 if (SPIL_LOC (IC_RESULT (ic)))
1244 IC_RESULT (ic) = newiTempFromOp (IC_RESULT (ic));
1245 SPIL_LOC (IC_RESULT (ic)) = NULL;
1253 /* now delete from defUseSet */
1254 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
1255 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
1257 /* and defset of the block */
1258 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
1260 /* If this is the last of a register equivalent, */
1261 /* look for a successor register equivalent. */
1262 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1263 if (IS_ITEMP (IC_RESULT (ic))
1264 && OP_SYMBOL (IC_RESULT (ic))->isreqv
1265 && bitVectIsZero (OP_DEFS (IC_RESULT (ic))))
1267 symbol * resultsym = OP_SYMBOL (IC_RESULT (ic));
1268 symbol * prereqv = resultsym->prereqv;
1270 if (prereqv && prereqv->reqv && (OP_SYMBOL (prereqv->reqv) == resultsym))
1274 IC_RESULT (ic) = NULL;
1275 newreqv = findReqv (prereqv, ebbs, count);
1278 prereqv->reqv = newreqv;
1283 /* delete the result */
1284 IC_RESULT (ic) = NULL;
1286 if (volLeft || volRight)
1288 /* something is volatile, so keep the iCode */
1289 /* and change the operator instead */
1290 ic->op = DUMMY_READ_VOLATILE;
1292 /* keep only the volatile operands */
1294 IC_LEFT (ic) = NULL;
1296 IC_RIGHT (ic) = NULL;
1300 /* nothing is volatile, eliminate the iCode */
1301 remiCodeFromeBBlock (ebbs[i], ic);
1303 /* for the left & right remove the usage */
1304 if (IS_SYMOP (IC_LEFT (ic)))
1305 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1307 if (IS_SYMOP (IC_RIGHT (ic)))
1308 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1312 } /* end of all instructions */
1314 if (!ebbs[i]->sch && !ebbs[i]->noPath)
1315 disconBBlock (ebbs[i], ebbi);
1317 } /* end of for all blocks */
1321 } /* end of while(1) */
1326 /*-----------------------------------------------------------------*/
1327 /* printCyclomatic - prints the cyclomatic information */
1328 /*-----------------------------------------------------------------*/
1330 printCyclomatic (eBBlock ** ebbs, int count)
1332 int nEdges = elementsInSet (graphEdges);
1335 for (i = 0; i < count; i++)
1336 nNodes += (!ebbs[i]->noPath);
1338 /* print the information */
1339 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
1342 /*-----------------------------------------------------------------*/
1343 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
1344 /* refer to dead variables. */
1345 /*-----------------------------------------------------------------*/
1347 discardDeadParamReceives (eBBlock ** ebbs, int count)
1353 for (i = 0; i < count; i++)
1355 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1357 if (ic->op == RECEIVE)
1359 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
1360 && !OP_SYMBOL (IC_RESULT (ic))->used)
1363 fprintf (stderr, "discarding dead receive for %s\n",
1364 OP_SYMBOL (IC_RESULT (ic))->name);
1366 dummyIcode.next = ic->next;
1367 remiCodeFromeBBlock (ebbs[i], ic);
1375 /*-----------------------------------------------------------------*/
1376 /* optimizeCastCast - remove unneeded intermediate casts. */
1377 /* Integer promotion may cast (un)signed char to int and then */
1378 /* recast the int to (un)signed long. If the signedness of the */
1379 /* char and long are the same, the cast can be safely performed in */
1380 /* a single step. */
1381 /*-----------------------------------------------------------------*/
1383 optimizeCastCast (eBBlock ** ebbs, int count)
1393 for (i = 0; i < count; i++)
1395 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1398 if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1400 type1 = operandType (IC_RIGHT (ic));
1401 type2 = operandType (IC_RESULT (ic));
1403 /* Look only for a cast from an integer type to an */
1404 /* integer type that has no loss of bits */
1405 if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1407 if (getSize (type2) < getSize (type1))
1410 /* There must be only one use of this first result */
1411 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1414 /* This use must be a second cast */
1415 uic = hTabItemWithKey (iCodehTab,
1416 bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1417 if (!uic || uic->op != CAST)
1420 /* It must be a cast to another integer type that */
1421 /* has no loss of bits */
1422 type3 = operandType (IC_RESULT (uic));
1423 if (!IS_INTEGRAL (type3))
1425 if (getSize (type3) < getSize (type2))
1428 /* The signedness between the first and last types */
1430 if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1433 /* Change the first cast to a simple assignment and */
1434 /* let the second cast do all the work */
1436 IC_LEFT (ic) = NULL;
1437 sym = OP_SYMBOL (IC_RESULT (ic));
1438 sym->type = copyLinkChain (type1);
1439 sym->etype = getSpec (sym->type);
1445 /*-----------------------------------------------------------------*/
1446 /* eBBlockFromiCode - creates extended basic blocks from iCode */
1447 /* will return an array of eBBlock pointers */
1448 /*-----------------------------------------------------------------*/
1450 eBBlockFromiCode (iCode * ic)
1452 ebbIndex *ebbi = NULL;
1458 /* if nothing passed then return nothing */
1464 /* optimize the chain for labels & gotos
1465 this will eliminate redundant labels and
1466 will change jump to jumps by jumps */
1467 ic = iCodeLabelOptimize (ic);
1469 /* break it down into basic blocks */
1470 ebbi = iCodeBreakDown (ic);
1472 /* hash the iCode keys so that we can quickly index */
1473 /* them in the rest of the optimization steps */
1474 setToNull ((void *) &iCodehTab);
1475 iCodehTab = newHashTable (iCodeKey);
1476 hashiCodeKeys (ebbi->bbOrder, ebbi->count);
1478 /* compute the control flow */
1479 computeControlFlow (ebbi);
1481 /* dumpraw if asked for */
1482 if (options.dump_raw)
1483 dumpEbbsToFileExt (DUMP_RAW0, ebbi);
1485 /* replace the local variables with their
1486 register equivalents : the liveRange computation
1487 along with the register allocation will determine
1488 if it finally stays in the registers */
1489 replaceRegEqv (ebbi);
1491 /* create loop regions */
1492 loops = createLoopRegions (ebbi);
1494 /* dumpraw if asked for */
1495 if (options.dump_raw)
1496 dumpEbbsToFileExt (DUMP_RAW1, ebbi);
1498 optimizeCastCast (ebbi->bbOrder, ebbi->count);
1500 /* do common subexpression elimination for each block */
1501 change = cseAllBlocks (ebbi, FALSE);
1503 /* dumpraw if asked for */
1504 if (options.dump_raw)
1505 dumpEbbsToFileExt (DUMP_CSE, ebbi);
1507 /* compute the data flow */
1508 computeDataFlow (ebbi);
1510 /* dumpraw if asked for */
1511 if (options.dump_raw)
1512 dumpEbbsToFileExt (DUMP_DFLOW, ebbi);
1514 /* global common subexpression elimination */
1515 if (optimize.global_cse)
1517 change += cseAllBlocks (ebbi, FALSE);
1518 if (options.dump_gcse)
1519 dumpEbbsToFileExt (DUMP_GCSE, ebbi);
1523 // compute the dataflow only
1524 assert(cseAllBlocks (ebbi, TRUE)==0);
1526 /* kill dead code */
1527 kchange = killDeadCode (ebbi);
1529 if (options.dump_kill)
1530 dumpEbbsToFileExt (DUMP_DEADCODE, ebbi);
1532 /* do loop optimizations */
1533 change += (lchange = loopOptimizations (loops, ebbi));
1534 if (options.dump_loop)
1535 dumpEbbsToFileExt (DUMP_LOOP, ebbi);
1537 /* recompute the data flow and apply global cse again
1538 if loops optimizations or dead code caused a change:
1539 loops will brings out of the loop which then may be
1540 available for use in the later blocks: dead code
1541 elimination could potentially disconnect some blocks
1542 conditional flow may be efected so we need to apply
1543 subexpression once more */
1544 if (lchange || kchange)
1546 computeDataFlow (ebbi);
1547 change += cseAllBlocks (ebbi, FALSE);
1548 if (options.dump_loop)
1549 dumpEbbsToFileExt (DUMP_LOOPG, ebbi);
1551 /* if loop optimizations caused a change then do
1552 dead code elimination once more : this will
1553 get rid of the extra assignments to the induction
1554 variables created during loop optimizations */
1555 killDeadCode (ebbi);
1557 if (options.dump_loop)
1558 dumpEbbsToFileExt (DUMP_LOOPD, ebbi);
1562 /* sort it back by block number */
1563 //qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1565 if (!options.lessPedantic) {
1566 // this is a good place to check missing return values
1568 // the user is on his own with naked functions...
1569 if (!IS_VOID(currFunc->etype)
1570 && !FUNC_ISNAKED(currFunc->type)) {
1572 // make sure all predecessors of the last block end in a return
1573 for (bp=setFirstItem(ebbi->bbOrder[ebbi->count-1]->predList);
1575 bp=setNextItem(ebbi->bbOrder[ebbi->count-1]->predList)) {
1576 if (bp->ech->op != RETURN) {
1577 werrorfl (bp->ech->filename, bp->ech->lineno,
1578 W_VOID_FUNC, currFunc->name);
1585 /* if cyclomatic info requested then print it */
1586 if (options.cyclomatic)
1587 printCyclomatic (ebbi->bbOrder, ebbi->count);
1589 /* convert operations with support routines
1590 written in C to function calls : I am doing
1591 this at this point since I want all the
1592 operations to be as they are for optimizations */
1593 convertToFcall (ebbi->bbOrder, ebbi->count);
1595 /* compute the live ranges */
1596 computeLiveRanges (ebbi->bbOrder, ebbi->count, TRUE);
1598 if (options.dump_range)
1599 dumpEbbsToFileExt (DUMP_RANGE, ebbi);
1601 /* Now that we have the live ranges, discard parameter
1602 * receives for unused parameters.
1604 discardDeadParamReceives (ebbi->bbOrder, ebbi->count);
1606 /* allocate registers & generate code */
1607 port->assignRegisters (ebbi);
1609 /* throw away blocks */
1610 setToNull ((void *) &graphEdges);
1616 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */