1 /*-------------------------------------------------------------------------
2 SDCCopt.c - calls all the optimizations routines and does some of the
3 hackier transformations, these include translating iCodes
4 to function calls and replacing local variables with their
5 register equivalents etc. Also contains the driver routine
6 for dead code elimination
8 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
10 This program is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 2, or (at your option) any
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
24 In other words, you are welcome to use, share and improve this program.
25 You are forbidden to forbid anyone else to use, share and improve
26 what you give them. Help stamp out software-hoarding!
27 -------------------------------------------------------------------------*/
31 /*-----------------------------------------------------------------*/
32 /* global variables */
38 /*-----------------------------------------------------------------*/
39 /* printSymName - prints the symbol names */
40 /*-----------------------------------------------------------------*/
42 printSymName (void *vsym)
45 fprintf (stdout, " %s ", sym->name);
49 /*-----------------------------------------------------------------*/
50 /* cnvToFcall - does the actual conversion to function call */
51 /*-----------------------------------------------------------------*/
53 cnvToFcall (iCode * ic, eBBlock * ebp)
60 int lineno = ic->lineno;
63 ip = ic->next; /* insertion point */
64 /* remove it from the iCode */
65 remiCodeFromeBBlock (ebp, ic);
68 right = IC_RIGHT (ic);
104 /* if float support routines NOT compiled as reentrant */
105 if (!options.float_rent)
109 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
111 newic = newiCode (SEND, IC_LEFT (ic), NULL);
112 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
116 newic = newiCode ('=', NULL, IC_LEFT (ic));
117 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
120 addiCodeToeBBlock (ebp, newic, ip);
121 newic->lineno = lineno;
124 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
126 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
127 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
131 newic = newiCode ('=', NULL, IC_RIGHT (ic));
132 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
134 addiCodeToeBBlock (ebp, newic, ip);
135 newic->lineno = lineno;
142 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
144 newic = newiCode (SEND, right, NULL);
145 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
149 newic = newiCode (IPUSH, right, NULL);
152 bytesPushed += getSize(operandType(right));
155 addiCodeToeBBlock (ebp, newic, ip);
156 newic->lineno = lineno;
158 /* insert push left */
159 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
161 newic = newiCode (SEND, left, NULL);
162 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
166 newic = newiCode (IPUSH, left, NULL);
169 bytesPushed += getSize(operandType(left));
171 addiCodeToeBBlock (ebp, newic, ip);
172 newic->lineno = lineno;
174 /* insert the call */
175 newic = newiCode (CALL, operandFromSymbol (func), NULL);
176 IC_RESULT (newic) = IC_RESULT (ic);
177 newic->lineno = lineno;
178 newic->parmBytes+=bytesPushed;
181 FUNC_HASFCALL (currFunc->type) = 1;
183 if(TARGET_IS_PIC16) {
184 /* normally these functions aren't marked external, so we can use their
185 * _extern field to marked as already added to symbol table */
187 if(!SPEC_EXTR(func->etype)) {
188 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
190 SPEC_EXTR(func->etype) = 1;
191 seg = SPEC_OCLS( func->etype );
192 addSet(&seg->syms, func);
196 addiCodeToeBBlock (ebp, newic, ip);
199 /*-----------------------------------------------------------------*/
200 /* cnvToFloatCast - converts casts to floats to function calls */
201 /*-----------------------------------------------------------------*/
203 cnvToFloatCast (iCode * ic, eBBlock * ebp)
207 sym_link *type = operandType (IC_RIGHT (ic));
208 int linenno = ic->lineno;
213 /* remove it from the iCode */
214 remiCodeFromeBBlock (ebp, ic);
215 /* depending on the type */
216 for (bwd = 0; bwd < 3; bwd++)
218 for (su = 0; su < 2; su++)
220 if (compareType (type, __multypes[bwd][su]) == 1)
222 func = __conv[0][bwd][su];
230 /* if float support routines NOT compiled as reentrant */
231 if (!options.float_rent)
234 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
236 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
237 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
241 newic = newiCode ('=', NULL, IC_RIGHT (ic));
242 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
244 addiCodeToeBBlock (ebp, newic, ip);
245 newic->lineno = linenno;
251 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
252 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
253 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
257 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
259 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
261 addiCodeToeBBlock (ebp, newic, ip);
262 newic->lineno = linenno;
267 newic = newiCode (CALL, operandFromSymbol (func), NULL);
268 IC_RESULT (newic) = IC_RESULT (ic);
269 newic->parmBytes+=bytesPushed;
272 FUNC_HASFCALL (currFunc->type) = 1;
274 if(TARGET_IS_PIC16) {
275 /* normally these functions aren't marked external, so we can use their
276 * _extern field to marked as already added to symbol table */
278 if(!SPEC_EXTR(func->etype)) {
279 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
281 SPEC_EXTR(func->etype) = 1;
282 seg = SPEC_OCLS( func->etype );
283 addSet(&seg->syms, func);
287 addiCodeToeBBlock (ebp, newic, ip);
288 newic->lineno = linenno;
291 /*-----------------------------------------------------------------*/
292 /* cnvFromFloatCast - converts casts From floats to function calls */
293 /*-----------------------------------------------------------------*/
295 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
299 sym_link *type = operandType (IC_LEFT (ic));
300 int lineno = ic->lineno;
305 /* remove it from the iCode */
306 remiCodeFromeBBlock (ebp, ic);
308 /* depending on the type */
309 for (bwd = 0; bwd < 3; bwd++)
311 for (su = 0; su < 2; su++)
313 if (compareType (type, __multypes[bwd][su]) == 1)
315 func = __conv[1][bwd][su];
323 /* if float support routines NOT compiled as reentrant */
324 if (!options.float_rent)
327 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
328 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
329 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
333 newic = newiCode ('=', NULL, IC_RIGHT (ic));
334 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
336 addiCodeToeBBlock (ebp, newic, ip);
337 newic->lineno = lineno;
344 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
345 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
346 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
350 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
352 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
354 addiCodeToeBBlock (ebp, newic, ip);
355 newic->lineno = lineno;
360 newic = newiCode (CALL, operandFromSymbol (func), NULL);
361 IC_RESULT (newic) = IC_RESULT (ic);
362 newic->parmBytes+=bytesPushed;
365 FUNC_HASFCALL (currFunc->type) = 1;
367 if(TARGET_IS_PIC16) {
368 /* normally these functions aren't marked external, so we can use their
369 * _extern field to marked as already added to symbol table */
371 if(!SPEC_EXTR(func->etype)) {
372 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
374 SPEC_EXTR(func->etype) = 1;
375 seg = SPEC_OCLS( func->etype );
376 addSet(&seg->syms, func);
380 addiCodeToeBBlock (ebp, newic, ip);
381 newic->lineno = lineno;
384 extern operand *geniCodeRValue (operand *, bool);
386 /*-----------------------------------------------------------------*/
387 /* convilong - converts int or long mults or divs to fcalls */
388 /*-----------------------------------------------------------------*/
390 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
393 iCode *ip = ic->next;
395 int lineno = ic->lineno;
400 remiCodeFromeBBlock (ebp, ic);
402 /* depending on the type */
403 for (bwd = 0; bwd < 3; bwd++)
405 for (su = 0; su < 2; su++)
407 if (compareType (type, __multypes[bwd][su]) == 1)
410 func = __muldiv[0][bwd][su];
412 func = __muldiv[1][bwd][su];
414 func = __muldiv[2][bwd][su];
416 func = __rlrr[1][bwd][su];
418 func = __rlrr[0][bwd][su];
419 else if (op == RIGHT_OP)
420 func = __rlrr[1][bwd][su];
421 else if (op == LEFT_OP)
422 func = __rlrr[0][bwd][su];
431 /* if int & long support routines NOT compiled as reentrant */
432 if (!options.intlong_rent)
435 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
436 newic = newiCode (SEND, IC_LEFT (ic), NULL);
437 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
441 newic = newiCode ('=', NULL, IC_LEFT (ic));
442 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
444 addiCodeToeBBlock (ebp, newic, ip);
445 newic->lineno = lineno;
448 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
449 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
450 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
454 newic = newiCode ('=', NULL, IC_RIGHT (ic));
455 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
457 addiCodeToeBBlock (ebp, newic, ip);
458 newic->lineno = lineno;
463 /* compiled as reentrant then push */
465 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
467 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
468 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
472 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
475 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
477 addiCodeToeBBlock (ebp, newic, ip);
478 newic->lineno = lineno;
480 /* insert push left */
481 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
483 newic = newiCode (SEND, IC_LEFT (ic), NULL);
484 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
488 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
491 bytesPushed += getSize(operandType(IC_LEFT(ic)));
493 addiCodeToeBBlock (ebp, newic, ip);
494 newic->lineno = lineno;
499 newic = newiCode (CALL, operandFromSymbol (func), NULL);
500 IC_RESULT (newic) = IC_RESULT (ic);
501 newic->lineno = lineno;
502 newic->parmBytes+=bytesPushed; // to clear the stack after the call
505 FUNC_HASFCALL (currFunc->type) = 1;
507 if(TARGET_IS_PIC16) {
508 /* normally these functions aren't marked external, so we can use their
509 * _extern field to marked as already added to symbol table */
511 if(!SPEC_EXTR(func->etype)) {
512 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
514 SPEC_EXTR(func->etype) = 1;
515 seg = SPEC_OCLS( func->etype );
516 addSet(&seg->syms, func);
520 addiCodeToeBBlock (ebp, newic, ip);
523 /*-----------------------------------------------------------------*/
524 /* convertToFcall - converts some operations to fcalls */
525 /*-----------------------------------------------------------------*/
527 convertToFcall (eBBlock ** ebbs, int count)
531 /* for all blocks do */
532 for (i = 0; i < count; i++)
536 /* for all instructions in the block do */
537 for (ic = ebbs[i]->sch; ic; ic = ic->next)
540 /* floating point operations are
541 converted to function calls */
542 if ((IS_CONDITIONAL (ic) ||
543 IS_ARITHMETIC_OP (ic)) &&
544 (IS_FLOAT (operandType (IC_RIGHT (ic)))))
547 cnvToFcall (ic, ebbs[i]);
550 /* casting is a little different */
553 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
554 cnvFromFloatCast (ic, ebbs[i]);
555 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
556 cnvToFloatCast (ic, ebbs[i]);
559 // Easy special case which avoids function call: modulo by a literal power
560 // of two can be replaced by a bitwise AND.
561 if (ic->op == '%' && isOperandLiteral(IC_RIGHT(ic)) &&
562 IS_UNSIGNED(operandType(IC_LEFT(ic))))
564 unsigned litVal = abs((int)operandLitValue(IC_RIGHT(ic)));
566 // See if literal value is a power of 2.
567 while (litVal && !(litVal & 1))
573 // discard lowest set bit.
580 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
585 /* if long / int mult or divide or mod */
586 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
588 sym_link *leftType = operandType (IC_LEFT (ic));
590 if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
592 sym_link *rightType = operandType (IC_RIGHT (ic));
594 if (port->hasNativeMulFor != NULL &&
595 port->hasNativeMulFor (ic, leftType, rightType))
597 /* Leave as native */
601 convilong (ic, ebbs[i], leftType, ic->op);
606 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
608 sym_link *type = operandType (IC_LEFT (ic));
610 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
612 convilong (ic, ebbs[i], type, ic->op);
619 /*-----------------------------------------------------------------*/
620 /* isLocalWithoutDef - return 1 if sym might be used without a */
622 /*-----------------------------------------------------------------*/
624 isLocalWithoutDef (symbol * sym)
629 if (IS_VOLATILE (sym->type))
635 if (IS_AGGREGATE (sym->type))
644 /*-----------------------------------------------------------------*/
645 /* replaceRegEqv - replace all local variables with their reqv */
646 /*-----------------------------------------------------------------*/
648 replaceRegEqv (ebbIndex * ebbi)
650 eBBlock ** ebbs = ebbi->bbOrder;
651 int count = ebbi->count;
654 /* Update the symbols' def bitvector so we know if there is */
655 /* a defining iCode or not. Only replace a local variable */
656 /* with its register equivalent if there is a defining iCode; */
657 /* otherwise, the port's register allocater may choke. */
658 cseAllBlocks (ebbi, TRUE);
660 for (i = 0; i < count; i++)
665 for (ic = ebbs[i]->sch; ic; ic = ic->next)
674 IS_TRUE_SYMOP (IC_COND (ic)) &&
675 isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
677 werrorfl (ic->filename, ic->lineno,
679 OP_SYMBOL (IC_COND (ic))->name);
680 OP_REQV (IC_COND (ic)) = NULL;
681 OP_SYMBOL (IC_COND (ic))->allocreq = 1;
684 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
685 OP_REQV (IC_COND (ic)))
686 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
687 OP_SYMBOL (IC_COND (ic))->defs,
688 OP_SYMBOL (IC_COND (ic))->uses);
694 if (ic->op == JUMPTABLE)
696 if (IC_JTCOND (ic) &&
697 IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
698 isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
700 werrorfl (ic->filename, ic->lineno,
702 OP_SYMBOL (IC_JTCOND (ic))->name);
703 OP_REQV (IC_JTCOND (ic)) = NULL;
704 OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
707 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
708 OP_REQV (IC_JTCOND (ic)))
709 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
710 OP_SYMBOL (IC_JTCOND (ic))->defs,
711 OP_SYMBOL (IC_JTCOND (ic))->uses);
715 if (ic->op == RECEIVE)
717 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
718 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
722 if (IC_RESULT (ic) &&
723 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
724 OP_REQV (IC_RESULT (ic)))
726 if (POINTER_SET (ic))
728 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
729 OP_SYMBOL (IC_RESULT (ic))->defs,
730 OP_SYMBOL (IC_RESULT (ic))->uses);
731 IC_RESULT (ic)->isaddr = 1;
734 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
735 OP_SYMBOL (IC_RESULT (ic))->defs,
736 OP_SYMBOL (IC_RESULT (ic))->uses);
740 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
741 isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
743 werrorfl (ic->filename, ic->lineno,
745 OP_SYMBOL (IC_RIGHT (ic))->name);
746 OP_REQV (IC_RIGHT (ic)) = NULL;
747 OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
751 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
752 OP_REQV (IC_RIGHT (ic)))
754 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
755 OP_SYMBOL (IC_RIGHT (ic))->defs,
756 OP_SYMBOL (IC_RIGHT (ic))->uses);
757 IC_RIGHT (ic)->isaddr = 0;
761 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
762 isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
764 werrorfl (ic->filename, ic->lineno,
766 OP_SYMBOL (IC_LEFT (ic))->name);
767 OP_REQV (IC_LEFT (ic)) = NULL;
768 OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
772 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
773 OP_REQV (IC_LEFT (ic)))
775 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
776 OP_SYMBOL (IC_LEFT (ic))->defs,
777 OP_SYMBOL (IC_LEFT (ic))->uses);
778 IC_LEFT (ic)->isaddr = 0;
784 /*-----------------------------------------------------------------*/
785 /* findReqv - search for a register equivalent */
786 /*-----------------------------------------------------------------*/
788 findReqv (symbol * prereqv, eBBlock ** ebbs, int count)
793 /* for all blocks do */
794 for (i=0; i<count; i++)
796 /* for all instructions in the block do */
797 for (ic = ebbs[i]->sch; ic; ic = ic->next)
801 if (IS_ITEMP (IC_COND (ic))
802 && OP_SYMBOL (IC_COND (ic))->prereqv == prereqv)
805 else if (ic->op == JUMPTABLE)
807 if (IS_ITEMP (IC_JTCOND (ic))
808 && OP_SYMBOL (IC_JTCOND (ic))->prereqv == prereqv)
809 return IC_JTCOND (ic);
813 if (IS_ITEMP (IC_LEFT (ic))
814 && OP_SYMBOL (IC_LEFT (ic))->prereqv == prereqv)
816 if (IS_ITEMP (IC_RIGHT (ic))
817 && OP_SYMBOL (IC_RIGHT (ic))->prereqv == prereqv)
818 return IC_RIGHT (ic);
819 if (IS_ITEMP (IC_RESULT (ic))
820 && OP_SYMBOL (IC_RESULT (ic))->prereqv == prereqv)
821 return IC_RESULT (ic);
829 /*-----------------------------------------------------------------*/
830 /* killDeadCode - eliminates dead assignments */
831 /*-----------------------------------------------------------------*/
833 killDeadCode (ebbIndex * ebbi)
835 eBBlock ** ebbs = ebbi->dfOrder;
836 int count = ebbi->count;
842 /* basic algorithm :- */
843 /* first the exclusion rules :- */
844 /* 1. if result is a global or volatile then skip */
845 /* 2. if assignment and result is a temp & isaddr then skip */
846 /* since this means array & pointer access, will be taken */
847 /* care of by alias analysis. */
848 /* 3. if the result is used in the remainder of the block skip */
849 /* 4. if this definition does not reach the end of the block */
850 /* i.e. the result is not present in the outExprs then KILL */
851 /* 5. if it reaches the end of block & is used by some success */
854 /* this whole process is carried on iteratively till no change */
859 /* for all blocks do */
860 for (i = 0; i < count; i++)
864 /* for all instructions in the block do */
865 for (ic = ebbs[i]->sch; ic; ic = ic->next)
873 ic->op == DUMMY_READ_VOLATILE ||
874 ic->op == CRITICAL ||
875 ic->op == ENDCRITICAL)
878 /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
879 /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are */
882 /* if the result is volatile then continue */
883 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
886 /* if the result is a temp & isaddr then skip */
887 if (IC_RESULT (ic) && POINTER_SET (ic))
890 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next)
891 && !SPIL_LOC (IC_RESULT (ic)))
894 /* if the result is used in the remainder of the */
895 /* block then skip */
896 if (usedInRemaining (IC_RESULT (ic), ic->next))
899 /* does this definition reach the end of the block
900 or the usage is zero then we can kill */
901 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
902 kill = 1; /* if not we can kill it */
905 /* if this is a global variable or function parameter */
906 /* we cannot kill anyway */
907 if (isOperandGlobal (IC_RESULT (ic)) ||
908 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
909 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
912 /* if we are sure there are no usages */
913 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
919 /* reset visited flag */
920 for (j = 0; j < count; ebbs[j++]->visited = 0);
922 /* find out if this definition is alive */
923 if (applyToSet (ebbs[i]->succList,
932 /* kill this one if required */
935 bool volLeft = IS_SYMOP (IC_LEFT (ic))
936 && isOperandVolatile (IC_LEFT (ic), FALSE);
937 bool volRight = IS_SYMOP (IC_RIGHT (ic))
938 && isOperandVolatile (IC_RIGHT (ic), FALSE);
940 /* a dead address-of operation should die, even if volatile */
941 if (ic->op == ADDRESS_OF)
944 if (ic->next && ic->seqPoint == ic->next->seqPoint
945 && (ic->next->op == '+' || ic->next->op == '-'))
947 if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
948 || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
950 if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
951 || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
955 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
957 if (SPIL_LOC (IC_RESULT (ic)))
959 IC_RESULT (ic) = newiTempFromOp (IC_RESULT (ic));
960 SPIL_LOC (IC_RESULT (ic)) = NULL;
968 /* now delete from defUseSet */
969 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
970 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
972 /* and defset of the block */
973 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
975 /* If this is the last of a register equivalent, */
976 /* look for a successor register equivalent. */
977 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
978 if (IS_ITEMP (IC_RESULT (ic))
979 && OP_SYMBOL (IC_RESULT (ic))->isreqv
980 && bitVectIsZero (OP_DEFS (IC_RESULT (ic))))
982 symbol * resultsym = OP_SYMBOL (IC_RESULT (ic));
983 symbol * prereqv = resultsym->prereqv;
985 if (prereqv && prereqv->reqv && (OP_SYMBOL (prereqv->reqv) == resultsym))
989 IC_RESULT (ic) = NULL;
990 newreqv = findReqv (prereqv, ebbs, count);
993 prereqv->reqv = newreqv;
998 /* delete the result */
999 IC_RESULT (ic) = NULL;
1001 if (volLeft || volRight)
1003 /* something is volatile, so keep the iCode */
1004 /* and change the operator instead */
1005 ic->op = DUMMY_READ_VOLATILE;
1007 /* keep only the volatile operands */
1009 IC_LEFT (ic) = NULL;
1011 IC_RIGHT (ic) = NULL;
1015 /* nothing is volatile, eliminate the iCode */
1016 remiCodeFromeBBlock (ebbs[i], ic);
1018 /* for the left & right remove the usage */
1019 if (IS_SYMOP (IC_LEFT (ic)))
1020 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1022 if (IS_SYMOP (IC_RIGHT (ic)))
1023 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1027 } /* end of all instructions */
1029 if (!ebbs[i]->sch && !ebbs[i]->noPath)
1030 disconBBlock (ebbs[i], ebbi);
1032 } /* end of for all blocks */
1036 } /* end of while(1) */
1041 /*-----------------------------------------------------------------*/
1042 /* printCyclomatic - prints the cyclomatic information */
1043 /*-----------------------------------------------------------------*/
1045 printCyclomatic (eBBlock ** ebbs, int count)
1047 int nEdges = elementsInSet (graphEdges);
1050 for (i = 0; i < count; i++)
1051 nNodes += (!ebbs[i]->noPath);
1053 /* print the information */
1054 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
1057 /*-----------------------------------------------------------------*/
1058 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
1059 /* refer to dead variables. */
1060 /*-----------------------------------------------------------------*/
1062 discardDeadParamReceives (eBBlock ** ebbs, int count)
1068 for (i = 0; i < count; i++)
1070 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1072 if (ic->op == RECEIVE)
1074 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
1075 && !OP_SYMBOL (IC_RESULT (ic))->used)
1078 fprintf (stderr, "discarding dead receive for %s\n",
1079 OP_SYMBOL (IC_RESULT (ic))->name);
1081 dummyIcode.next = ic->next;
1082 remiCodeFromeBBlock (ebbs[i], ic);
1090 /*-----------------------------------------------------------------*/
1091 /* optimizeCastCast - remove unneeded intermediate casts. */
1092 /* Integer promotion may cast (un)signed char to int and then */
1093 /* recast the int to (un)signed long. If the signedness of the */
1094 /* char and long are the same, the cast can be safely performed in */
1095 /* a single step. */
1096 /*-----------------------------------------------------------------*/
1098 optimizeCastCast (eBBlock ** ebbs, int count)
1108 for (i = 0; i < count; i++)
1110 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1113 if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1115 type1 = operandType (IC_RIGHT (ic));
1116 type2 = operandType (IC_RESULT (ic));
1118 /* Look only for a cast from an integer type to an */
1119 /* integer type that has no loss of bits */
1120 if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1122 if (getSize (type2) < getSize (type1))
1125 /* There must be only one use of this first result */
1126 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1129 /* This use must be a second cast */
1130 uic = hTabItemWithKey (iCodehTab,
1131 bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1132 if (!uic || uic->op != CAST)
1135 /* It must be a cast to another integer type that */
1136 /* has no loss of bits */
1137 type3 = operandType (IC_RESULT (uic));
1138 if (!IS_INTEGRAL (type3))
1140 if (getSize (type3) < getSize (type2))
1143 /* The signedness between the first and last types */
1145 if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1148 /* Change the first cast to a simple assignment and */
1149 /* let the second cast do all the work */
1151 IC_LEFT (ic) = NULL;
1152 sym = OP_SYMBOL (IC_RESULT (ic));
1153 sym->type = copyLinkChain (type1);
1154 sym->etype = getSpec (sym->type);
1160 /*-----------------------------------------------------------------*/
1161 /* eBBlockFromiCode - creates extended basic blocks from iCode */
1162 /* will return an array of eBBlock pointers */
1163 /*-----------------------------------------------------------------*/
1165 eBBlockFromiCode (iCode * ic)
1167 ebbIndex *ebbi = NULL;
1173 /* if nothing passed then return nothing */
1179 /* optimize the chain for labels & gotos
1180 this will eliminate redundant labels and
1181 will change jump to jumps by jumps */
1182 ic = iCodeLabelOptimize (ic);
1184 /* break it down into basic blocks */
1185 ebbi = iCodeBreakDown (ic);
1187 /* hash the iCode keys so that we can quickly index */
1188 /* them in the rest of the optimization steps */
1189 setToNull ((void *) &iCodehTab);
1190 iCodehTab = newHashTable (iCodeKey);
1191 hashiCodeKeys (ebbi->bbOrder, ebbi->count);
1193 /* compute the control flow */
1194 computeControlFlow (ebbi);
1196 /* dumpraw if asked for */
1197 if (options.dump_raw)
1198 dumpEbbsToFileExt (DUMP_RAW0, ebbi);
1200 /* replace the local variables with their
1201 register equivalents : the liveRange computation
1202 along with the register allocation will determine
1203 if it finally stays in the registers */
1204 replaceRegEqv (ebbi);
1206 /* create loop regions */
1207 loops = createLoopRegions (ebbi);
1209 /* dumpraw if asked for */
1210 if (options.dump_raw)
1211 dumpEbbsToFileExt (DUMP_RAW1, ebbi);
1213 optimizeCastCast (ebbi->bbOrder, ebbi->count);
1215 /* do common subexpression elimination for each block */
1216 change = cseAllBlocks (ebbi, FALSE);
1218 /* dumpraw if asked for */
1219 if (options.dump_raw)
1220 dumpEbbsToFileExt (DUMP_CSE, ebbi);
1222 /* compute the data flow */
1223 computeDataFlow (ebbi);
1225 /* dumpraw if asked for */
1226 if (options.dump_raw)
1227 dumpEbbsToFileExt (DUMP_DFLOW, ebbi);
1229 /* global common subexpression elimination */
1230 if (optimize.global_cse)
1232 change += cseAllBlocks (ebbi, FALSE);
1233 if (options.dump_gcse)
1234 dumpEbbsToFileExt (DUMP_GCSE, ebbi);
1238 // compute the dataflow only
1239 assert(cseAllBlocks (ebbi, TRUE)==0);
1241 /* kill dead code */
1242 kchange = killDeadCode (ebbi);
1244 if (options.dump_kill)
1245 dumpEbbsToFileExt (DUMP_DEADCODE, ebbi);
1247 /* do loop optimizations */
1248 change += (lchange = loopOptimizations (loops, ebbi));
1249 if (options.dump_loop)
1250 dumpEbbsToFileExt (DUMP_LOOP, ebbi);
1252 /* recompute the data flow and apply global cse again
1253 if loops optimizations or dead code caused a change:
1254 loops will brings out of the loop which then may be
1255 available for use in the later blocks: dead code
1256 elimination could potentially disconnect some blocks
1257 conditional flow may be efected so we need to apply
1258 subexpression once more */
1259 if (lchange || kchange)
1261 computeDataFlow (ebbi);
1262 change += cseAllBlocks (ebbi, FALSE);
1263 if (options.dump_loop)
1264 dumpEbbsToFileExt (DUMP_LOOPG, ebbi);
1266 /* if loop optimizations caused a change then do
1267 dead code elimination once more : this will
1268 get rid of the extra assignments to the induction
1269 variables created during loop optimizations */
1270 killDeadCode (ebbi);
1272 if (options.dump_loop)
1273 dumpEbbsToFileExt (DUMP_LOOPD, ebbi);
1277 /* sort it back by block number */
1278 //qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1280 if (!options.lessPedantic) {
1281 // this is a good place to check missing return values
1283 // the user is on his own with naked functions...
1284 if (!IS_VOID(currFunc->etype)
1285 && !FUNC_ISNAKED(currFunc->type)) {
1287 // make sure all predecessors of the last block end in a return
1288 for (bp=setFirstItem(ebbi->bbOrder[ebbi->count-1]->predList);
1290 bp=setNextItem(ebbi->bbOrder[ebbi->count-1]->predList)) {
1291 if (bp->ech->op != RETURN) {
1292 werrorfl (bp->ech->filename, bp->ech->lineno,
1293 W_VOID_FUNC, currFunc->name);
1300 /* if cyclomatic info requested then print it */
1301 if (options.cyclomatic)
1302 printCyclomatic (ebbi->bbOrder, ebbi->count);
1304 /* convert operations with support routines
1305 written in C to function calls : Iam doing
1306 this at this point since I want all the
1307 operations to be as they are for optimzations */
1308 convertToFcall (ebbi->bbOrder, ebbi->count);
1310 /* compute the live ranges */
1311 computeLiveRanges (ebbi->bbOrder, ebbi->count);
1313 if (options.dump_range)
1314 dumpEbbsToFileExt (DUMP_RANGE, ebbi);
1316 /* Now that we have the live ranges, discard parameter
1317 * receives for unused parameters.
1319 discardDeadParamReceives (ebbi->bbOrder, ebbi->count);
1321 /* allocate registers & generate code */
1322 port->assignRegisters (ebbi);
1324 /* throw away blocks */
1325 setToNull ((void *) &graphEdges);
1331 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */