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)
661 iCode *ip = ic->next;
663 char *filename = ic->filename;
664 int lineno = ic->lineno;
668 sym_link *leftType = operandType (IC_LEFT (ic));
669 sym_link *rightType = operandType (IC_RIGHT (ic));
671 remiCodeFromeBBlock (ebp, ic);
673 if (getSize (leftType) == 1 && getSize (rightType) == 1)
686 for (su = 0; su < 4 && muldivmod >= 0; su++)
688 if ((compareType (leftType, __multypes[0][su%2]) == 1) &&
689 (compareType (rightType, __multypes[0][su/2]) == 1))
691 func = __muldiv[muldivmod][0][su];
697 /* depending on the type */
698 for (bwd = 0; bwd < 3; bwd++)
700 for (su = 0; su < 2; su++)
702 if (compareType (leftType, __multypes[bwd][su]) == 1)
704 if ((op=='*' || op=='/' || op=='%') &&
705 compareType (rightType, __multypes[bwd][su]) != 1)
711 func = __muldiv[0][bwd][su];
713 func = __muldiv[1][bwd][su];
715 func = __muldiv[2][bwd][su];
717 func = __rlrr[1][bwd][su];
719 func = __rlrr[0][bwd][su];
720 else if (op == RIGHT_OP)
721 func = __rlrr[1][bwd][su];
722 else if (op == LEFT_OP)
723 func = __rlrr[0][bwd][su];
732 /* if int & long support routines NOT compiled as reentrant */
733 if (!options.intlong_rent)
736 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
737 newic = newiCode (SEND, IC_LEFT (ic), NULL);
738 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
742 newic = newiCode ('=', NULL, IC_LEFT (ic));
743 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
745 addiCodeToeBBlock (ebp, newic, ip);
746 newic->filename = filename;
747 newic->lineno = lineno;
750 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
751 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
752 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
756 newic = newiCode ('=', NULL, IC_RIGHT (ic));
757 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
759 addiCodeToeBBlock (ebp, newic, ip);
760 newic->filename = filename;
761 newic->lineno = lineno;
766 /* compiled as reentrant then push */
768 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
770 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
771 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
775 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
778 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
780 addiCodeToeBBlock (ebp, newic, ip);
781 newic->filename = filename;
782 newic->lineno = lineno;
784 /* insert push left */
785 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
787 newic = newiCode (SEND, IC_LEFT (ic), NULL);
788 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
792 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
795 bytesPushed += getSize(operandType(IC_LEFT(ic)));
797 addiCodeToeBBlock (ebp, newic, ip);
798 newic->filename = filename;
799 newic->lineno = lineno;
804 newic = newiCode (CALL, operandFromSymbol (func), NULL);
805 IC_RESULT (newic) = IC_RESULT (ic);
806 newic->filename = filename;
807 newic->lineno = lineno;
808 newic->parmBytes+=bytesPushed; // to clear the stack after the call
811 FUNC_HASFCALL (currFunc->type) = 1;
813 if(TARGET_IS_PIC || TARGET_IS_PIC16) {
814 /* normally these functions aren't marked external, so we can use their
815 * _extern field to marked as already added to symbol table */
817 if(!SPEC_EXTR(func->etype)) {
818 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
820 SPEC_EXTR(func->etype) = 1;
821 seg = SPEC_OCLS( func->etype );
822 addSet(&seg->syms, func);
826 addiCodeToeBBlock (ebp, newic, ip);
829 /*-----------------------------------------------------------------*/
830 /* convertToFcall - converts some operations to fcalls */
831 /*-----------------------------------------------------------------*/
833 convertToFcall (eBBlock ** ebbs, int count)
837 /* for all blocks do */
838 for (i = 0; i < count; i++)
842 /* for all instructions in the block do */
843 for (ic = ebbs[i]->sch; ic; ic = ic->next)
846 /* floating point operations are
847 converted to function calls */
848 if ((IS_CONDITIONAL (ic) ||
849 IS_ARITHMETIC_OP (ic)) &&
850 (IS_FLOAT (operandType (IC_RIGHT (ic))) ||
851 IS_FIXED( operandType (IC_RIGHT (ic)))))
853 cnvToFcall (ic, ebbs[i]);
856 /* casting is a little different */
859 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
860 cnvFromFloatCast (ic, ebbs[i]);
861 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
862 cnvToFloatCast (ic, ebbs[i]);
863 if (IS_FIXED16X16 (operandType (IC_RIGHT (ic))))
864 cnvFromFixed16x16Cast (ic, ebbs[i]);
865 else if (IS_FIXED16X16 (operandType (IC_LEFT (ic))))
866 cnvToFixed16x16Cast (ic, ebbs[i]);
869 // Easy special case which avoids function call: modulo by a literal power
870 // of two can be replaced by a bitwise AND.
871 if (ic->op == '%' && isOperandLiteral(IC_RIGHT(ic)) &&
872 IS_UNSIGNED(operandType(IC_LEFT(ic))))
874 unsigned litVal = abs((unsigned) double2ul (operandLitValue(IC_RIGHT(ic))));
876 /* modulo by 1: no remainder */
880 IC_RIGHT (ic) = operandFromLit(0);
884 // See if literal value is a power of 2.
885 while (litVal && !(litVal & 1))
891 // discard lowest set bit.
898 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
903 /* if long / int mult or divide or mod */
904 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
906 sym_link *leftType = operandType (IC_LEFT (ic));
908 if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
910 sym_link *rightType = operandType (IC_RIGHT (ic));
912 if (port->hasNativeMulFor != NULL &&
913 port->hasNativeMulFor (ic, leftType, rightType))
915 /* Leave as native */
919 convilong (ic, ebbs[i]);
924 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
926 sym_link *type = operandType (IC_LEFT (ic));
928 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
930 convilong (ic, ebbs[i]);
937 /*-----------------------------------------------------------------*/
938 /* isLocalWithoutDef - return 1 if sym might be used without a */
940 /*-----------------------------------------------------------------*/
942 isLocalWithoutDef (symbol * sym)
947 if (IS_VOLATILE (sym->type))
953 if (IS_AGGREGATE (sym->type))
962 /*-----------------------------------------------------------------*/
963 /* replaceRegEqv - replace all local variables with their reqv */
964 /*-----------------------------------------------------------------*/
966 replaceRegEqv (ebbIndex * ebbi)
968 eBBlock ** ebbs = ebbi->bbOrder;
969 int count = ebbi->count;
972 /* Update the symbols' def bitvector so we know if there is */
973 /* a defining iCode or not. Only replace a local variable */
974 /* with its register equivalent if there is a defining iCode; */
975 /* otherwise, the port's register allocater may choke. */
976 cseAllBlocks (ebbi, TRUE);
978 for (i = 0; i < count; i++)
983 for (ic = ebbs[i]->sch; ic; ic = ic->next)
992 IS_TRUE_SYMOP (IC_COND (ic)) &&
993 isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
995 werrorfl (ic->filename, ic->lineno,
997 OP_SYMBOL (IC_COND (ic))->name);
998 OP_REQV (IC_COND (ic)) = NULL;
999 OP_SYMBOL (IC_COND (ic))->allocreq = 1;
1002 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
1003 OP_REQV (IC_COND (ic)))
1004 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
1005 OP_SYMBOL (IC_COND (ic))->defs,
1006 OP_SYMBOL (IC_COND (ic))->uses);
1012 if (ic->op == JUMPTABLE)
1014 if (IC_JTCOND (ic) &&
1015 IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
1016 isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
1018 werrorfl (ic->filename, ic->lineno,
1020 OP_SYMBOL (IC_JTCOND (ic))->name);
1021 OP_REQV (IC_JTCOND (ic)) = NULL;
1022 OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
1025 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
1026 OP_REQV (IC_JTCOND (ic)))
1027 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
1028 OP_SYMBOL (IC_JTCOND (ic))->defs,
1029 OP_SYMBOL (IC_JTCOND (ic))->uses);
1033 if (ic->op == RECEIVE)
1035 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
1036 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
1040 if (IC_RESULT (ic) &&
1041 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
1042 OP_REQV (IC_RESULT (ic)))
1044 if (POINTER_SET (ic))
1046 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
1047 OP_SYMBOL (IC_RESULT (ic))->defs,
1048 OP_SYMBOL (IC_RESULT (ic))->uses);
1049 IC_RESULT (ic)->isaddr = 1;
1052 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
1053 OP_SYMBOL (IC_RESULT (ic))->defs,
1054 OP_SYMBOL (IC_RESULT (ic))->uses);
1057 if (IC_RIGHT (ic) &&
1058 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
1059 isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
1061 werrorfl (ic->filename, ic->lineno,
1063 OP_SYMBOL (IC_RIGHT (ic))->name);
1064 OP_REQV (IC_RIGHT (ic)) = NULL;
1065 OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
1068 if (IC_RIGHT (ic) &&
1069 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
1070 OP_REQV (IC_RIGHT (ic)))
1072 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
1073 OP_SYMBOL (IC_RIGHT (ic))->defs,
1074 OP_SYMBOL (IC_RIGHT (ic))->uses);
1075 IC_RIGHT (ic)->isaddr = 0;
1079 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
1080 isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
1082 werrorfl (ic->filename, ic->lineno,
1084 OP_SYMBOL (IC_LEFT (ic))->name);
1085 OP_REQV (IC_LEFT (ic)) = NULL;
1086 OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
1090 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
1091 OP_REQV (IC_LEFT (ic)))
1093 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
1094 OP_SYMBOL (IC_LEFT (ic))->defs,
1095 OP_SYMBOL (IC_LEFT (ic))->uses);
1096 IC_LEFT (ic)->isaddr = 0;
1102 /*-----------------------------------------------------------------*/
1103 /* findReqv - search for a register equivalent */
1104 /*-----------------------------------------------------------------*/
1106 findReqv (symbol * prereqv, eBBlock ** ebbs, int count)
1111 /* for all blocks do */
1112 for (i=0; i<count; i++)
1114 /* for all instructions in the block do */
1115 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1119 if (IS_ITEMP (IC_COND (ic))
1120 && OP_SYMBOL (IC_COND (ic))->prereqv == prereqv)
1121 return IC_COND (ic);
1123 else if (ic->op == JUMPTABLE)
1125 if (IS_ITEMP (IC_JTCOND (ic))
1126 && OP_SYMBOL (IC_JTCOND (ic))->prereqv == prereqv)
1127 return IC_JTCOND (ic);
1131 if (IS_ITEMP (IC_LEFT (ic))
1132 && OP_SYMBOL (IC_LEFT (ic))->prereqv == prereqv)
1133 return IC_LEFT (ic);
1134 if (IS_ITEMP (IC_RIGHT (ic))
1135 && OP_SYMBOL (IC_RIGHT (ic))->prereqv == prereqv)
1136 return IC_RIGHT (ic);
1137 if (IS_ITEMP (IC_RESULT (ic))
1138 && OP_SYMBOL (IC_RESULT (ic))->prereqv == prereqv)
1139 return IC_RESULT (ic);
1147 /*-----------------------------------------------------------------*/
1148 /* killDeadCode - eliminates dead assignments */
1149 /*-----------------------------------------------------------------*/
1151 killDeadCode (ebbIndex * ebbi)
1153 eBBlock ** ebbs = ebbi->dfOrder;
1154 int count = ebbi->count;
1160 /* basic algorithm :- */
1161 /* first the exclusion rules :- */
1162 /* 1. if result is a global or volatile then skip */
1163 /* 2. if assignment and result is a temp & isaddr then skip */
1164 /* since this means array & pointer access, will be taken */
1165 /* care of by alias analysis. */
1166 /* 3. if the result is used in the remainder of the block skip */
1167 /* 4. if this definition does not reach the end of the block */
1168 /* i.e. the result is not present in the outExprs then KILL */
1169 /* 5. if it reaches the end of block & is used by some success */
1172 /* this whole process is carried on iteratively till no change */
1177 /* for all blocks do */
1178 for (i = 0; i < count; i++)
1182 /* for all instructions in the block do */
1183 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1191 ic->op == DUMMY_READ_VOLATILE ||
1192 ic->op == CRITICAL ||
1193 ic->op == ENDCRITICAL)
1196 /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
1197 /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are */
1200 /* if the result is volatile then continue */
1201 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
1204 /* if the result is a temp & isaddr then skip */
1205 if (IC_RESULT (ic) && POINTER_SET (ic))
1208 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next)
1209 && !SPIL_LOC (IC_RESULT (ic)))
1212 /* if the result is used in the remainder of the */
1213 /* block then skip */
1214 if (usedInRemaining (IC_RESULT (ic), ic->next))
1217 /* does this definition reach the end of the block
1218 or the usage is zero then we can kill */
1219 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
1220 kill = 1; /* if not we can kill it */
1223 /* if this is a global variable or function parameter */
1224 /* we cannot kill anyway */
1225 if (isOperandGlobal (IC_RESULT (ic)) ||
1226 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
1227 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
1230 /* if we are sure there are no usages */
1231 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
1237 /* reset visited flag */
1238 for (j = 0; j < count; ebbs[j++]->visited = 0);
1240 /* find out if this definition is alive */
1241 if (applyToSet (ebbs[i]->succList,
1250 /* kill this one if required */
1253 bool volLeft = IS_SYMOP (IC_LEFT (ic))
1254 && isOperandVolatile (IC_LEFT (ic), FALSE);
1255 bool volRight = IS_SYMOP (IC_RIGHT (ic))
1256 && isOperandVolatile (IC_RIGHT (ic), FALSE);
1258 /* a dead address-of operation should die, even if volatile */
1259 if (ic->op == ADDRESS_OF)
1262 if (ic->next && ic->seqPoint == ic->next->seqPoint
1263 && (ic->next->op == '+' || ic->next->op == '-'))
1265 if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
1266 || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
1268 if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
1269 || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
1273 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
1275 if (SPIL_LOC (IC_RESULT (ic)))
1277 IC_RESULT (ic) = newiTempFromOp (IC_RESULT (ic));
1278 SPIL_LOC (IC_RESULT (ic)) = NULL;
1286 /* now delete from defUseSet */
1287 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
1288 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
1290 /* and defset of the block */
1291 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
1293 /* If this is the last of a register equivalent, */
1294 /* look for a successor register equivalent. */
1295 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1296 if (IS_ITEMP (IC_RESULT (ic))
1297 && OP_SYMBOL (IC_RESULT (ic))->isreqv
1298 && bitVectIsZero (OP_DEFS (IC_RESULT (ic))))
1300 symbol * resultsym = OP_SYMBOL (IC_RESULT (ic));
1301 symbol * prereqv = resultsym->prereqv;
1303 if (prereqv && prereqv->reqv && (OP_SYMBOL (prereqv->reqv) == resultsym))
1307 IC_RESULT (ic) = NULL;
1308 newreqv = findReqv (prereqv, ebbs, count);
1311 prereqv->reqv = newreqv;
1316 /* delete the result */
1317 IC_RESULT (ic) = NULL;
1319 if (volLeft || volRight)
1321 /* something is volatile, so keep the iCode */
1322 /* and change the operator instead */
1323 ic->op = DUMMY_READ_VOLATILE;
1325 /* keep only the volatile operands */
1327 IC_LEFT (ic) = NULL;
1329 IC_RIGHT (ic) = NULL;
1333 /* nothing is volatile, eliminate the iCode */
1334 remiCodeFromeBBlock (ebbs[i], ic);
1336 /* for the left & right remove the usage */
1337 if (IS_SYMOP (IC_LEFT (ic)))
1338 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1340 if (IS_SYMOP (IC_RIGHT (ic)))
1341 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1345 } /* end of all instructions */
1347 if (!ebbs[i]->sch && !ebbs[i]->noPath)
1348 disconBBlock (ebbs[i], ebbi);
1350 } /* end of for all blocks */
1354 } /* end of while(1) */
1359 /*-----------------------------------------------------------------*/
1360 /* printCyclomatic - prints the cyclomatic information */
1361 /*-----------------------------------------------------------------*/
1363 printCyclomatic (eBBlock ** ebbs, int count)
1365 int nEdges = elementsInSet (graphEdges);
1368 for (i = 0; i < count; i++)
1369 nNodes += (!ebbs[i]->noPath);
1371 /* print the information */
1372 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
1375 /*-----------------------------------------------------------------*/
1376 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
1377 /* refer to dead variables. */
1378 /*-----------------------------------------------------------------*/
1380 discardDeadParamReceives (eBBlock ** ebbs, int count)
1386 for (i = 0; i < count; i++)
1388 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1390 if (ic->op == RECEIVE)
1392 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
1393 && !OP_SYMBOL (IC_RESULT (ic))->used)
1396 fprintf (stderr, "discarding dead receive for %s\n",
1397 OP_SYMBOL (IC_RESULT (ic))->name);
1399 dummyIcode.next = ic->next;
1400 remiCodeFromeBBlock (ebbs[i], ic);
1408 /*-----------------------------------------------------------------*/
1409 /* optimizeCastCast - remove unneeded intermediate casts. */
1410 /* Integer promotion may cast (un)signed char to int and then */
1411 /* recast the int to (un)signed long. If the signedness of the */
1412 /* char and long are the same, the cast can be safely performed in */
1413 /* a single step. */
1414 /*-----------------------------------------------------------------*/
1416 optimizeCastCast (eBBlock ** ebbs, int count)
1426 for (i = 0; i < count; i++)
1428 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1431 if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1433 type1 = operandType (IC_RIGHT (ic));
1434 type2 = operandType (IC_RESULT (ic));
1436 /* Look only for a cast from an integer type to an */
1437 /* integer type that has no loss of bits */
1438 if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1440 if (getSize (type2) < getSize (type1))
1443 /* There must be only one use of this first result */
1444 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1447 /* This use must be a second cast */
1448 uic = hTabItemWithKey (iCodehTab,
1449 bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1450 if (!uic || uic->op != CAST)
1453 /* It must be a cast to another integer type that */
1454 /* has no loss of bits */
1455 type3 = operandType (IC_RESULT (uic));
1456 if (!IS_INTEGRAL (type3))
1458 if (getSize (type3) < getSize (type2))
1461 /* The signedness between the first and last types */
1463 if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1466 /* Change the first cast to a simple assignment and */
1467 /* let the second cast do all the work */
1469 IC_LEFT (ic) = NULL;
1470 sym = OP_SYMBOL (IC_RESULT (ic));
1471 sym->type = copyLinkChain (type1);
1472 sym->etype = getSpec (sym->type);
1478 /*-----------------------------------------------------------------*/
1479 /* eBBlockFromiCode - creates extended basic blocks from iCode */
1480 /* will return an array of eBBlock pointers */
1481 /*-----------------------------------------------------------------*/
1483 eBBlockFromiCode (iCode * ic)
1485 ebbIndex *ebbi = NULL;
1491 /* if nothing passed then return nothing */
1497 /* optimize the chain for labels & gotos
1498 this will eliminate redundant labels and
1499 will change jump to jumps by jumps */
1500 ic = iCodeLabelOptimize (ic);
1502 /* break it down into basic blocks */
1503 ebbi = iCodeBreakDown (ic);
1505 /* hash the iCode keys so that we can quickly index */
1506 /* them in the rest of the optimization steps */
1507 setToNull ((void *) &iCodehTab);
1508 iCodehTab = newHashTable (iCodeKey);
1509 hashiCodeKeys (ebbi->bbOrder, ebbi->count);
1511 /* compute the control flow */
1512 computeControlFlow (ebbi);
1514 /* dumpraw if asked for */
1515 if (options.dump_raw)
1516 dumpEbbsToFileExt (DUMP_RAW0, ebbi);
1518 /* replace the local variables with their
1519 register equivalents : the liveRange computation
1520 along with the register allocation will determine
1521 if it finally stays in the registers */
1522 replaceRegEqv (ebbi);
1524 /* create loop regions */
1525 loops = createLoopRegions (ebbi);
1527 /* dumpraw if asked for */
1528 if (options.dump_raw)
1529 dumpEbbsToFileExt (DUMP_RAW1, ebbi);
1531 optimizeCastCast (ebbi->bbOrder, ebbi->count);
1533 /* do common subexpression elimination for each block */
1534 change = cseAllBlocks (ebbi, FALSE);
1536 /* dumpraw if asked for */
1537 if (options.dump_raw)
1538 dumpEbbsToFileExt (DUMP_CSE, ebbi);
1540 /* compute the data flow */
1541 computeDataFlow (ebbi);
1543 /* dumpraw if asked for */
1544 if (options.dump_raw)
1545 dumpEbbsToFileExt (DUMP_DFLOW, ebbi);
1547 /* global common subexpression elimination */
1548 if (optimize.global_cse)
1550 change += cseAllBlocks (ebbi, FALSE);
1551 if (options.dump_gcse)
1552 dumpEbbsToFileExt (DUMP_GCSE, ebbi);
1556 // compute the dataflow only
1557 assert(cseAllBlocks (ebbi, TRUE)==0);
1559 /* kill dead code */
1560 kchange = killDeadCode (ebbi);
1562 if (options.dump_kill)
1563 dumpEbbsToFileExt (DUMP_DEADCODE, ebbi);
1565 /* do loop optimizations */
1566 change += (lchange = loopOptimizations (loops, ebbi));
1567 if (options.dump_loop)
1568 dumpEbbsToFileExt (DUMP_LOOP, ebbi);
1570 /* recompute the data flow and apply global cse again
1571 if loops optimizations or dead code caused a change:
1572 loops will brings out of the loop which then may be
1573 available for use in the later blocks: dead code
1574 elimination could potentially disconnect some blocks
1575 conditional flow may be efected so we need to apply
1576 subexpression once more */
1577 if (lchange || kchange)
1579 computeDataFlow (ebbi);
1580 change += cseAllBlocks (ebbi, FALSE);
1581 if (options.dump_loop)
1582 dumpEbbsToFileExt (DUMP_LOOPG, ebbi);
1584 /* if loop optimizations caused a change then do
1585 dead code elimination once more : this will
1586 get rid of the extra assignments to the induction
1587 variables created during loop optimizations */
1588 killDeadCode (ebbi);
1590 if (options.dump_loop)
1591 dumpEbbsToFileExt (DUMP_LOOPD, ebbi);
1595 /* sort it back by block number */
1596 //qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1598 if (!options.lessPedantic) {
1599 // this is a good place to check missing return values
1601 // the user is on his own with naked functions...
1602 if (!IS_VOID(currFunc->etype)
1603 && !FUNC_ISNAKED(currFunc->type)) {
1605 // make sure all predecessors of the last block end in a return
1606 for (bp=setFirstItem(ebbi->bbOrder[ebbi->count-1]->predList);
1608 bp=setNextItem(ebbi->bbOrder[ebbi->count-1]->predList)) {
1609 if (bp->ech->op != RETURN) {
1610 werrorfl (bp->ech->filename, bp->ech->lineno,
1611 W_VOID_FUNC, currFunc->name);
1618 /* if cyclomatic info requested then print it */
1619 if (options.cyclomatic)
1620 printCyclomatic (ebbi->bbOrder, ebbi->count);
1622 /* convert operations with support routines
1623 written in C to function calls : I am doing
1624 this at this point since I want all the
1625 operations to be as they are for optimizations */
1626 convertToFcall (ebbi->bbOrder, ebbi->count);
1628 /* compute the live ranges */
1629 computeLiveRanges (ebbi->bbOrder, ebbi->count, TRUE);
1631 if (options.dump_range)
1632 dumpEbbsToFileExt (DUMP_RANGE, ebbi);
1634 /* Now that we have the live ranges, discard parameter
1635 * receives for unused parameters.
1637 discardDeadParamReceives (ebbi->bbOrder, ebbi->count);
1639 /* allocate registers & generate code */
1640 port->assignRegisters (ebbi);
1642 /* throw away blocks */
1643 setToNull ((void *) &graphEdges);
1649 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */