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;
180 if(TARGET_IS_PIC16) {
181 /* normally these functions aren't marked external, so we can use their
182 * _extern field to marked as already added to symbol table */
184 if(!SPEC_EXTR(func->etype)) {
185 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
187 SPEC_EXTR(func->etype) = 1;
188 seg = SPEC_OCLS( func->etype );
189 addSet(&seg->syms, func);
193 addiCodeToeBBlock (ebp, newic, ip);
196 /*-----------------------------------------------------------------*/
197 /* cnvToFloatCast - converts casts to floats to function calls */
198 /*-----------------------------------------------------------------*/
200 cnvToFloatCast (iCode * ic, eBBlock * ebp)
204 sym_link *type = operandType (IC_RIGHT (ic));
205 int linenno = ic->lineno;
210 /* remove it from the iCode */
211 remiCodeFromeBBlock (ebp, ic);
212 /* depending on the type */
213 for (bwd = 0; bwd < 3; bwd++)
215 for (su = 0; su < 2; su++)
217 if (compareType (type, __multypes[bwd][su]) == 1)
219 func = __conv[0][bwd][su];
227 /* if float support routines NOT compiled as reentrant */
228 if (!options.float_rent)
231 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
233 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
234 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
238 newic = newiCode ('=', NULL, IC_RIGHT (ic));
239 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
241 addiCodeToeBBlock (ebp, newic, ip);
242 newic->lineno = linenno;
248 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
249 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
250 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
254 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
256 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
258 addiCodeToeBBlock (ebp, newic, ip);
259 newic->lineno = linenno;
264 newic = newiCode (CALL, operandFromSymbol (func), NULL);
265 IC_RESULT (newic) = IC_RESULT (ic);
266 newic->parmBytes+=bytesPushed;
268 if(TARGET_IS_PIC16) {
269 /* normally these functions aren't marked external, so we can use their
270 * _extern field to marked as already added to symbol table */
272 if(!SPEC_EXTR(func->etype)) {
273 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
275 SPEC_EXTR(func->etype) = 1;
276 seg = SPEC_OCLS( func->etype );
277 addSet(&seg->syms, func);
281 addiCodeToeBBlock (ebp, newic, ip);
282 newic->lineno = linenno;
285 /*-----------------------------------------------------------------*/
286 /* cnvFromFloatCast - converts casts From floats to function calls */
287 /*-----------------------------------------------------------------*/
289 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
293 sym_link *type = operandType (IC_LEFT (ic));
294 int lineno = ic->lineno;
299 /* remove it from the iCode */
300 remiCodeFromeBBlock (ebp, ic);
302 /* depending on the type */
303 for (bwd = 0; bwd < 3; bwd++)
305 for (su = 0; su < 2; su++)
307 if (compareType (type, __multypes[bwd][su]) == 1)
309 func = __conv[1][bwd][su];
317 /* if float support routines NOT compiled as reentrant */
318 if (!options.float_rent)
321 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
322 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
323 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
327 newic = newiCode ('=', NULL, IC_RIGHT (ic));
328 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
330 addiCodeToeBBlock (ebp, newic, ip);
331 newic->lineno = lineno;
338 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
339 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
340 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
344 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
346 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
348 addiCodeToeBBlock (ebp, newic, ip);
349 newic->lineno = lineno;
354 newic = newiCode (CALL, operandFromSymbol (func), NULL);
355 IC_RESULT (newic) = IC_RESULT (ic);
356 newic->parmBytes+=bytesPushed;
358 if(TARGET_IS_PIC16) {
359 /* normally these functions aren't marked external, so we can use their
360 * _extern field to marked as already added to symbol table */
362 if(!SPEC_EXTR(func->etype)) {
363 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
365 SPEC_EXTR(func->etype) = 1;
366 seg = SPEC_OCLS( func->etype );
367 addSet(&seg->syms, func);
371 addiCodeToeBBlock (ebp, newic, ip);
372 newic->lineno = lineno;
375 extern operand *geniCodeRValue (operand *, bool);
377 /*-----------------------------------------------------------------*/
378 /* convilong - converts int or long mults or divs to fcalls */
379 /*-----------------------------------------------------------------*/
381 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
384 iCode *ip = ic->next;
386 int lineno = ic->lineno;
391 // Easy special case which avoids function call: modulo by a literal power
392 // of two can be replaced by a bitwise AND.
393 if (op == '%' && isOperandLiteral(IC_RIGHT(ic)))
395 unsigned litVal = (unsigned)(operandLitValue(IC_RIGHT(ic)));
397 // See if literal value is a power of 2.
398 while (litVal && !(litVal & 1))
404 // discard first high bit set.
411 IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
416 remiCodeFromeBBlock (ebp, ic);
419 /* depending on the type */
420 for (bwd = 0; bwd < 3; bwd++)
422 for (su = 0; su < 2; su++)
424 if (compareType (type, __multypes[bwd][su]) == 1)
427 func = __muldiv[0][bwd][su];
429 func = __muldiv[1][bwd][su];
431 func = __muldiv[2][bwd][su];
433 func = __rlrr[1][bwd][su];
435 func = __rlrr[0][bwd][su];
436 else if (op == RIGHT_OP)
437 func = __rlrr[1][bwd][su];
438 else if (op == LEFT_OP)
439 func = __rlrr[0][bwd][su];
448 /* if int & long support routines NOT compiled as reentrant */
449 if (!options.intlong_rent)
452 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
453 newic = newiCode (SEND, IC_LEFT (ic), NULL);
454 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
458 newic = newiCode ('=', NULL, IC_LEFT (ic));
459 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
461 addiCodeToeBBlock (ebp, newic, ip);
462 newic->lineno = lineno;
465 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
466 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
467 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
471 newic = newiCode ('=', NULL, IC_RIGHT (ic));
472 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
474 addiCodeToeBBlock (ebp, newic, ip);
475 newic->lineno = lineno;
480 /* compiled as reentrant then push */
482 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
484 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
485 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
489 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
492 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
494 addiCodeToeBBlock (ebp, newic, ip);
495 newic->lineno = lineno;
497 /* insert push left */
498 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
500 newic = newiCode (SEND, IC_LEFT (ic), NULL);
501 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
505 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
508 bytesPushed += getSize(operandType(IC_LEFT(ic)));
510 addiCodeToeBBlock (ebp, newic, ip);
511 newic->lineno = lineno;
516 newic = newiCode (CALL, operandFromSymbol (func), NULL);
517 IC_RESULT (newic) = IC_RESULT (ic);
518 newic->lineno = lineno;
519 newic->parmBytes+=bytesPushed; // to clear the stack after the call
521 if(TARGET_IS_PIC16) {
522 /* normally these functions aren't marked external, so we can use their
523 * _extern field to marked as already added to symbol table */
525 if(!SPEC_EXTR(func->etype)) {
526 memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
528 SPEC_EXTR(func->etype) = 1;
529 seg = SPEC_OCLS( func->etype );
530 addSet(&seg->syms, func);
534 addiCodeToeBBlock (ebp, newic, ip);
537 /*-----------------------------------------------------------------*/
538 /* convertToFcall - converts some operations to fcalls */
539 /*-----------------------------------------------------------------*/
541 convertToFcall (eBBlock ** ebbs, int count)
545 /* for all blocks do */
546 for (i = 0; i < count; i++)
550 /* for all instructions in the block do */
551 for (ic = ebbs[i]->sch; ic; ic = ic->next)
554 /* floating point operations are
555 converted to function calls */
556 if ((IS_CONDITIONAL (ic) ||
557 IS_ARITHMETIC_OP (ic)) &&
558 (IS_FLOAT (operandType (IC_RIGHT (ic)))))
561 cnvToFcall (ic, ebbs[i]);
564 /* casting is a little different */
567 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
568 cnvFromFloatCast (ic, ebbs[i]);
569 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
570 cnvToFloatCast (ic, ebbs[i]);
573 /* if long / int mult or divide or mod */
574 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
576 sym_link *leftType = operandType (IC_LEFT (ic));
578 if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
580 sym_link *rightType = operandType (IC_RIGHT (ic));
582 if (port->hasNativeMulFor != NULL &&
583 port->hasNativeMulFor (ic, leftType, rightType))
585 /* Leave as native */
589 convilong (ic, ebbs[i], leftType, ic->op);
594 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
596 sym_link *type = operandType (IC_LEFT (ic));
598 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
600 convilong (ic, ebbs[i], type, ic->op);
607 /*-----------------------------------------------------------------*/
608 /* isLocalWithoutDef - return 1 if sym might be used without a */
610 /*-----------------------------------------------------------------*/
612 isLocalWithoutDef (symbol * sym)
617 if (IS_VOLATILE (sym->type))
623 if (IS_AGGREGATE (sym->type))
632 /*-----------------------------------------------------------------*/
633 /* replaceRegEqv - replace all local variables with their reqv */
634 /*-----------------------------------------------------------------*/
636 replaceRegEqv (eBBlock ** ebbs, int count)
640 /* Update the symbols' def bitvector so we know if there is */
641 /* a defining iCode or not. Only replace a local variable */
642 /* with its register equivalent if there is a defining iCode; */
643 /* otherwise, the port's register allocater may choke. */
644 cseAllBlocks (ebbs, count, TRUE);
646 for (i = 0; i < count; i++)
651 for (ic = ebbs[i]->sch; ic; ic = ic->next)
660 IS_TRUE_SYMOP (IC_COND (ic)) &&
661 isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
663 werrorfl (ic->filename, ic->lineno,
665 OP_SYMBOL (IC_COND (ic))->name);
666 OP_REQV (IC_COND (ic)) = NULL;
667 OP_SYMBOL (IC_COND (ic))->allocreq = 1;
670 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
671 OP_REQV (IC_COND (ic)))
672 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
673 OP_SYMBOL (IC_COND (ic))->defs,
674 OP_SYMBOL (IC_COND (ic))->uses);
680 if (ic->op == JUMPTABLE)
682 if (IC_JTCOND (ic) &&
683 IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
684 isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
686 werrorfl (ic->filename, ic->lineno,
688 OP_SYMBOL (IC_JTCOND (ic))->name);
689 OP_REQV (IC_JTCOND (ic)) = NULL;
690 OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
693 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
694 OP_REQV (IC_JTCOND (ic)))
695 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
696 OP_SYMBOL (IC_JTCOND (ic))->defs,
697 OP_SYMBOL (IC_JTCOND (ic))->uses);
701 if (ic->op == RECEIVE)
703 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
704 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
708 if (IC_RESULT (ic) &&
709 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
710 OP_REQV (IC_RESULT (ic)))
712 if (POINTER_SET (ic))
714 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
715 OP_SYMBOL (IC_RESULT (ic))->defs,
716 OP_SYMBOL (IC_RESULT (ic))->uses);
717 IC_RESULT (ic)->isaddr = 1;
720 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
721 OP_SYMBOL (IC_RESULT (ic))->defs,
722 OP_SYMBOL (IC_RESULT (ic))->uses);
726 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
727 isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
729 werrorfl (ic->filename, ic->lineno,
731 OP_SYMBOL (IC_RIGHT (ic))->name);
732 OP_REQV (IC_RIGHT (ic)) = NULL;
733 OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
737 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
738 OP_REQV (IC_RIGHT (ic)))
740 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
741 OP_SYMBOL (IC_RIGHT (ic))->defs,
742 OP_SYMBOL (IC_RIGHT (ic))->uses);
743 IC_RIGHT (ic)->isaddr = 0;
747 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
748 isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
750 werrorfl (ic->filename, ic->lineno,
752 OP_SYMBOL (IC_LEFT (ic))->name);
753 OP_REQV (IC_LEFT (ic)) = NULL;
754 OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
758 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
759 OP_REQV (IC_LEFT (ic)))
761 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
762 OP_SYMBOL (IC_LEFT (ic))->defs,
763 OP_SYMBOL (IC_LEFT (ic))->uses);
764 IC_LEFT (ic)->isaddr = 0;
770 /*-----------------------------------------------------------------*/
771 /* findReqv - search for a register equivalent */
772 /*-----------------------------------------------------------------*/
774 findReqv (symbol * prereqv, eBBlock ** ebbs, int count)
779 /* for all blocks do */
780 for (i=0; i<count; i++)
782 /* for all instructions in the block do */
783 for (ic = ebbs[i]->sch; ic; ic = ic->next)
787 if (IS_ITEMP (IC_COND (ic))
788 && OP_SYMBOL (IC_COND (ic))->prereqv == prereqv)
791 else if (ic->op == JUMPTABLE)
793 if (IS_ITEMP (IC_JTCOND (ic))
794 && OP_SYMBOL (IC_JTCOND (ic))->prereqv == prereqv)
795 return IC_JTCOND (ic);
799 if (IS_ITEMP (IC_LEFT (ic))
800 && OP_SYMBOL (IC_LEFT (ic))->prereqv == prereqv)
802 if (IS_ITEMP (IC_RIGHT (ic))
803 && OP_SYMBOL (IC_RIGHT (ic))->prereqv == prereqv)
804 return IC_RIGHT (ic);
805 if (IS_ITEMP (IC_RESULT (ic))
806 && OP_SYMBOL (IC_RESULT (ic))->prereqv == prereqv)
807 return IC_RESULT (ic);
815 /*-----------------------------------------------------------------*/
816 /* killDeadCode - eliminates dead assignments */
817 /*-----------------------------------------------------------------*/
819 killDeadCode (eBBlock ** ebbs, int count)
826 /* basic algorithm :- */
827 /* first the exclusion rules :- */
828 /* 1. if result is a global or volatile then skip */
829 /* 2. if assignment and result is a temp & isaddr then skip */
830 /* since this means array & pointer access, will be taken */
831 /* care of by alias analysis. */
832 /* 3. if the result is used in the remainder of the block skip */
833 /* 4. if this definition does not reach the end of the block */
834 /* i.e. the result is not present in the outExprs then KILL */
835 /* 5. if it reaches the end of block & is used by some success */
838 /* this whole process is carried on iteratively till no change */
843 /* for all blocks do */
844 for (i = 0; i < count; i++)
848 /* for all instructions in the block do */
849 for (ic = ebbs[i]->sch; ic; ic = ic->next)
857 ic->op == DUMMY_READ_VOLATILE ||
858 ic->op == CRITICAL ||
859 ic->op == ENDCRITICAL)
862 /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
863 /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are */
866 /* if the result is volatile then continue */
867 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
870 /* if the result is a temp & isaddr then skip */
871 if (IC_RESULT (ic) && POINTER_SET (ic))
874 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
877 /* if the result is used in the remainder of the */
878 /* block then skip */
879 if (usedInRemaining (IC_RESULT (ic), ic->next))
882 /* does this definition reach the end of the block
883 or the usage is zero then we can kill */
884 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
885 kill = 1; /* if not we can kill it */
888 /* if this is a global variable or function parameter */
889 /* we cannot kill anyway */
890 if (isOperandGlobal (IC_RESULT (ic)) ||
891 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
892 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
895 /* if we are sure there are no usages */
896 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
902 /* reset visited flag */
903 for (j = 0; j < count; ebbs[j++]->visited = 0);
905 /* find out if this definition is alive */
906 if (applyToSet (ebbs[i]->succList,
915 /* kill this one if required */
918 bool volLeft = IS_SYMOP (IC_LEFT (ic))
919 && isOperandVolatile (IC_LEFT (ic), FALSE);
920 bool volRight = IS_SYMOP (IC_RIGHT (ic))
921 && isOperandVolatile (IC_RIGHT (ic), FALSE);
923 /* a dead address-of operation should die, even if volatile */
924 if (ic->op == ADDRESS_OF)
927 if (ic->next && ic->seqPoint == ic->next->seqPoint
928 && (ic->next->op == '+' || ic->next->op == '-'))
930 if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
931 || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
933 if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
934 || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
941 /* now delete from defUseSet */
942 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
943 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
945 /* and defset of the block */
946 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
948 /* If this is the last of a register equivalent, */
949 /* look for a successor register equivalent. */
950 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
951 if (IS_ITEMP (IC_RESULT (ic))
952 && OP_SYMBOL (IC_RESULT (ic))->isreqv
953 && bitVectIsZero (OP_DEFS (IC_RESULT (ic))))
955 symbol * resultsym = OP_SYMBOL (IC_RESULT (ic));
956 symbol * prereqv = resultsym->prereqv;
958 if (OP_SYMBOL (prereqv->reqv) == resultsym)
962 IC_RESULT (ic) = NULL;
963 newreqv = findReqv (prereqv, ebbs, count);
966 prereqv->reqv = newreqv;
971 /* delete the result */
972 IC_RESULT (ic) = NULL;
974 if (volLeft || volRight)
976 /* something is volatile, so keep the iCode */
977 /* and change the operator instead */
978 ic->op = DUMMY_READ_VOLATILE;
980 /* keep only the volatile operands */
984 IC_RIGHT (ic) = NULL;
988 /* nothing is volatile, eliminate the iCode */
989 remiCodeFromeBBlock (ebbs[i], ic);
991 /* for the left & right remove the usage */
992 if (IS_SYMOP (IC_LEFT (ic)))
993 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
995 if (IS_SYMOP (IC_RIGHT (ic)))
996 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1000 } /* end of all instructions */
1002 if (!ebbs[i]->sch && !ebbs[i]->noPath)
1003 disconBBlock (ebbs[i], ebbs, count);
1005 } /* end of for all blocks */
1009 } /* end of while(1) */
1014 /*-----------------------------------------------------------------*/
1015 /* printCyclomatic - prints the cyclomatic information */
1016 /*-----------------------------------------------------------------*/
1018 printCyclomatic (eBBlock ** ebbs, int count)
1020 int nEdges = elementsInSet (graphEdges);
1023 for (i = 0; i < count; i++)
1024 nNodes += (!ebbs[i]->noPath);
1026 /* print the information */
1027 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
1030 /*-----------------------------------------------------------------*/
1031 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
1032 /* refer to dead variables. */
1033 /*-----------------------------------------------------------------*/
1035 discardDeadParamReceives (eBBlock ** ebbs, int count)
1041 for (i = 0; i < count; i++)
1043 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1045 if (ic->op == RECEIVE)
1047 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
1048 && !OP_SYMBOL (IC_RESULT (ic))->used)
1051 fprintf (stderr, "discarding dead receive for %s\n",
1052 OP_SYMBOL (IC_RESULT (ic))->name);
1054 dummyIcode.next = ic->next;
1055 remiCodeFromeBBlock (ebbs[i], ic);
1063 /*-----------------------------------------------------------------*/
1064 /* optimizeCastCast - remove unneeded intermediate casts. */
1065 /* Integer promotion may cast (un)signed char to int and then */
1066 /* recast the int to (un)signed long. If the signedness of the */
1067 /* char and long are the same, the cast can be safely performed in */
1068 /* a single step. */
1069 /*-----------------------------------------------------------------*/
1071 optimizeCastCast (eBBlock ** ebbs, int count)
1081 for (i = 0; i < count; i++)
1083 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1086 if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1088 type1 = operandType (IC_RIGHT (ic));
1089 type2 = operandType (IC_RESULT (ic));
1091 /* Look only for a cast from an integer type to an */
1092 /* integer type that has no loss of bits */
1093 if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1095 if (getSize (type2) < getSize (type1))
1098 /* There must be only one use of this first result */
1099 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1102 /* This use must be a second cast */
1103 uic = hTabItemWithKey (iCodehTab,
1104 bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1105 if (!uic || uic->op != CAST)
1108 /* It must be a cast to another integer type that */
1109 /* has no loss of bits */
1110 type3 = operandType (IC_RESULT (uic));
1111 if (!IS_INTEGRAL (type3))
1113 if (getSize (type3) < getSize (type2))
1116 /* The signedness between the first and last types */
1118 if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1121 /* Change the first cast to a simple assignment and */
1122 /* let the second cast do all the work */
1124 IC_LEFT (ic) = NULL;
1125 sym = OP_SYMBOL (IC_RESULT (ic));
1126 sym->type = copyLinkChain (type1);
1127 sym->etype = getSpec (sym->type);
1133 /*-----------------------------------------------------------------*/
1134 /* eBBlockFromiCode - creates extended basic blocks from iCode */
1135 /* will return an array of eBBlock pointers */
1136 /*-----------------------------------------------------------------*/
1138 eBBlockFromiCode (iCode * ic)
1140 eBBlock **ebbs = NULL;
1148 /* if nothing passed then return nothing */
1155 /* optimize the chain for labels & gotos
1156 this will eliminate redundant labels and
1157 will change jump to jumps by jumps */
1158 ic = iCodeLabelOptimize (ic);
1160 /* break it down into basic blocks */
1161 ebbs = iCodeBreakDown (ic, &count);
1164 /* hash the iCode keys so that we can quickly index */
1165 /* them in the rest of the optimization steps */
1166 setToNull ((void *) &iCodehTab);
1167 iCodehTab = newHashTable (iCodeKey);
1168 hashiCodeKeys (ebbs, count);
1170 /* compute the control flow */
1171 computeControlFlow (ebbs, count, 0);
1173 /* dumpraw if asked for */
1174 if (options.dump_raw)
1175 dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
1177 /* replace the local variables with their
1178 register equivalents : the liveRange computation
1179 along with the register allocation will determine
1180 if it finally stays in the registers */
1181 replaceRegEqv (ebbs, count);
1183 /* create loop regions */
1184 loops = createLoopRegions (ebbs, count);
1186 /* dumpraw if asked for */
1187 if (options.dump_raw)
1188 dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
1190 optimizeCastCast (ebbs, saveCount);
1192 /* do common subexpression elimination for each block */
1193 change = cseAllBlocks (ebbs, saveCount, FALSE);
1195 /* dumpraw if asked for */
1196 if (options.dump_raw)
1197 dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
1199 /* compute the data flow */
1200 computeDataFlow (ebbs, saveCount);
1202 /* dumpraw if asked for */
1203 if (options.dump_raw)
1204 dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
1206 /* global common subexpression elimination */
1207 if (optimize.global_cse)
1209 change += cseAllBlocks (ebbs, saveCount, FALSE);
1210 if (options.dump_gcse)
1211 dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
1215 // compute the dataflow only
1216 assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
1218 /* kill dead code */
1219 kchange = killDeadCode (ebbs, saveCount);
1221 if (options.dump_kill)
1222 dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
1224 /* do loop optimizations */
1225 change += (lchange = loopOptimizations (loops, ebbs, count));
1226 if (options.dump_loop)
1227 dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
1229 /* recompute the data flow and apply global cse again
1230 if loops optimizations or dead code caused a change:
1231 loops will brings out of the loop which then may be
1232 available for use in the later blocks: dead code
1233 elimination could potentially disconnect some blocks
1234 conditional flow may be efected so we need to apply
1235 subexpression once more */
1236 if (lchange || kchange)
1238 computeDataFlow (ebbs, saveCount);
1239 change += cseAllBlocks (ebbs, saveCount, FALSE);
1240 if (options.dump_loop)
1241 dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
1243 /* if loop optimizations caused a change then do
1244 dead code elimination once more : this will
1245 get rid of the extra assignments to the induction
1246 variables created during loop optimizations */
1247 killDeadCode (ebbs, saveCount);
1249 if (options.dump_loop)
1250 dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1254 /* sort it back by block number */
1255 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1257 if (!options.lessPedantic) {
1258 // this is a good place to check missing return values
1260 // the user is on his own with naked functions...
1261 if (!IS_VOID(currFunc->etype)
1262 && !FUNC_ISNAKED(currFunc->type)) {
1264 // make sure all predecessors of the last block end in a return
1265 for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1267 bp=setNextItem(ebbs[saveCount-1]->predList)) {
1268 if (bp->ech->op != RETURN) {
1269 werrorfl (bp->ech->filename, bp->ech->lineno,
1270 W_VOID_FUNC, currFunc->name);
1277 /* if cyclomatic info requested then print it */
1278 if (options.cyclomatic)
1279 printCyclomatic (ebbs, saveCount);
1281 /* convert operations with support routines
1282 written in C to function calls : Iam doing
1283 this at this point since I want all the
1284 operations to be as they are for optimzations */
1285 convertToFcall (ebbs, count);
1287 /* compute the live ranges */
1288 computeLiveRanges (ebbs, count);
1290 if (options.dump_range)
1291 dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1293 /* Now that we have the live ranges, discard parameter
1294 * receives for unused parameters.
1296 discardDeadParamReceives (ebbs, count);
1298 /* allocate registers & generate code */
1299 port->assignRegisters (ebbs, count);
1301 /* throw away blocks */
1302 setToNull ((void *) &graphEdges);
1309 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */