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)
620 if (IS_STATIC (sym->etype))
623 if (IS_VOLATILE (sym->type))
629 if (IS_AGGREGATE (sym->type))
638 /*-----------------------------------------------------------------*/
639 /* replaceRegEqv - replace all local variables with their reqv */
640 /*-----------------------------------------------------------------*/
642 replaceRegEqv (eBBlock ** ebbs, int count)
646 /* Update the symbols' def bitvector so we know if there is */
647 /* a defining iCode or not. Only replace a local variable */
648 /* with its register equivalent if there is a defining iCode; */
649 /* otherwise, the port's register allocater may choke. */
650 cseAllBlocks (ebbs, count, TRUE);
652 for (i = 0; i < count; i++)
657 for (ic = ebbs[i]->sch; ic; ic = ic->next)
666 IS_TRUE_SYMOP (IC_COND (ic)) &&
667 isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
669 werrorfl (ic->filename, ic->lineno,
671 OP_SYMBOL (IC_COND (ic))->name);
672 OP_REQV (IC_COND (ic)) = NULL;
673 OP_SYMBOL (IC_COND (ic))->allocreq = 1;
676 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
677 OP_REQV (IC_COND (ic)))
678 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
679 OP_SYMBOL (IC_COND (ic))->defs,
680 OP_SYMBOL (IC_COND (ic))->uses);
686 if (ic->op == JUMPTABLE)
688 if (IC_JTCOND (ic) &&
689 IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
690 isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
692 werrorfl (ic->filename, ic->lineno,
694 OP_SYMBOL (IC_JTCOND (ic))->name);
695 OP_REQV (IC_JTCOND (ic)) = NULL;
696 OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
699 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
700 OP_REQV (IC_JTCOND (ic)))
701 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
702 OP_SYMBOL (IC_JTCOND (ic))->defs,
703 OP_SYMBOL (IC_JTCOND (ic))->uses);
707 if (ic->op == RECEIVE)
709 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
710 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
714 if (IC_RESULT (ic) &&
715 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
716 OP_REQV (IC_RESULT (ic)))
718 if (POINTER_SET (ic))
720 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
721 OP_SYMBOL (IC_RESULT (ic))->defs,
722 OP_SYMBOL (IC_RESULT (ic))->uses);
723 IC_RESULT (ic)->isaddr = 1;
726 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
727 OP_SYMBOL (IC_RESULT (ic))->defs,
728 OP_SYMBOL (IC_RESULT (ic))->uses);
732 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
733 isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
735 werrorfl (ic->filename, ic->lineno,
737 OP_SYMBOL (IC_RIGHT (ic))->name);
738 OP_REQV (IC_RIGHT (ic)) = NULL;
739 OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
743 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
744 OP_REQV (IC_RIGHT (ic)))
746 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
747 OP_SYMBOL (IC_RIGHT (ic))->defs,
748 OP_SYMBOL (IC_RIGHT (ic))->uses);
749 IC_RIGHT (ic)->isaddr = 0;
753 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
754 isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
756 werrorfl (ic->filename, ic->lineno,
758 OP_SYMBOL (IC_LEFT (ic))->name);
759 OP_REQV (IC_LEFT (ic)) = NULL;
760 OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
764 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
765 OP_REQV (IC_LEFT (ic)))
767 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
768 OP_SYMBOL (IC_LEFT (ic))->defs,
769 OP_SYMBOL (IC_LEFT (ic))->uses);
770 IC_LEFT (ic)->isaddr = 0;
776 /*-----------------------------------------------------------------*/
777 /* findReqv - search for a register equivalent */
778 /*-----------------------------------------------------------------*/
780 findReqv (symbol * prereqv, eBBlock ** ebbs, int count)
785 /* for all blocks do */
786 for (i=0; i<count; i++)
788 /* for all instructions in the block do */
789 for (ic = ebbs[i]->sch; ic; ic = ic->next)
793 if (IS_ITEMP (IC_COND (ic))
794 && OP_SYMBOL (IC_COND (ic))->prereqv == prereqv)
797 else if (ic->op == JUMPTABLE)
799 if (IS_ITEMP (IC_JTCOND (ic))
800 && OP_SYMBOL (IC_JTCOND (ic))->prereqv == prereqv)
801 return IC_JTCOND (ic);
805 if (IS_ITEMP (IC_LEFT (ic))
806 && OP_SYMBOL (IC_LEFT (ic))->prereqv == prereqv)
808 if (IS_ITEMP (IC_RIGHT (ic))
809 && OP_SYMBOL (IC_RIGHT (ic))->prereqv == prereqv)
810 return IC_RIGHT (ic);
811 if (IS_ITEMP (IC_RESULT (ic))
812 && OP_SYMBOL (IC_RESULT (ic))->prereqv == prereqv)
813 return IC_RESULT (ic);
821 /*-----------------------------------------------------------------*/
822 /* killDeadCode - eliminates dead assignments */
823 /*-----------------------------------------------------------------*/
825 killDeadCode (eBBlock ** ebbs, int count)
832 /* basic algorithm :- */
833 /* first the exclusion rules :- */
834 /* 1. if result is a global or volatile then skip */
835 /* 2. if assignment and result is a temp & isaddr then skip */
836 /* since this means array & pointer access, will be taken */
837 /* care of by alias analysis. */
838 /* 3. if the result is used in the remainder of the block skip */
839 /* 4. if this definition does not reach the end of the block */
840 /* i.e. the result is not present in the outExprs then KILL */
841 /* 5. if it reaches the end of block & is used by some success */
844 /* this whole process is carried on iteratively till no change */
849 /* for all blocks do */
850 for (i = 0; i < count; i++)
854 /* for all instructions in the block do */
855 for (ic = ebbs[i]->sch; ic; ic = ic->next)
863 ic->op == DUMMY_READ_VOLATILE ||
864 ic->op == CRITICAL ||
865 ic->op == ENDCRITICAL)
868 /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
869 /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are */
872 /* if the result is volatile then continue */
873 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
876 /* if the result is a temp & isaddr then skip */
877 if (IC_RESULT (ic) && POINTER_SET (ic))
880 if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
883 /* if the result is used in the remainder of the */
884 /* block then skip */
885 if (usedInRemaining (IC_RESULT (ic), ic->next))
888 /* does this definition reach the end of the block
889 or the usage is zero then we can kill */
890 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
891 kill = 1; /* if not we can kill it */
894 /* if this is a global variable or function parameter */
895 /* we cannot kill anyway */
896 if (isOperandGlobal (IC_RESULT (ic)) ||
897 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
898 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
901 /* if we are sure there are no usages */
902 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
908 /* reset visited flag */
909 for (j = 0; j < count; ebbs[j++]->visited = 0);
911 /* find out if this definition is alive */
912 if (applyToSet (ebbs[i]->succList,
921 /* kill this one if required */
924 bool volLeft = IS_SYMOP (IC_LEFT (ic))
925 && isOperandVolatile (IC_LEFT (ic), FALSE);
926 bool volRight = IS_SYMOP (IC_RIGHT (ic))
927 && isOperandVolatile (IC_RIGHT (ic), FALSE);
929 /* a dead address-of operation should die, even if volatile */
930 if (ic->op == ADDRESS_OF)
933 if (ic->next && ic->seqPoint == ic->next->seqPoint
934 && (ic->next->op == '+' || ic->next->op == '-'))
936 if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
937 || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
939 if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
940 || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
947 /* now delete from defUseSet */
948 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
949 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
951 /* and defset of the block */
952 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
954 /* If this is the last of a register equivalent, */
955 /* look for a successor register equivalent. */
956 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
957 if (IS_ITEMP (IC_RESULT (ic))
958 && OP_SYMBOL (IC_RESULT (ic))->isreqv
959 && bitVectIsZero (OP_DEFS (IC_RESULT (ic))))
961 symbol * resultsym = OP_SYMBOL (IC_RESULT (ic));
962 symbol * prereqv = resultsym->prereqv;
964 if (OP_SYMBOL (prereqv->reqv) == resultsym)
968 IC_RESULT (ic) = NULL;
969 newreqv = findReqv (prereqv, ebbs, count);
972 prereqv->reqv = newreqv;
977 /* delete the result */
978 IC_RESULT (ic) = NULL;
980 if (volLeft || volRight)
982 /* something is volatile, so keep the iCode */
983 /* and change the operator instead */
984 ic->op = DUMMY_READ_VOLATILE;
986 /* keep only the volatile operands */
990 IC_RIGHT (ic) = NULL;
994 /* nothing is volatile, eliminate the iCode */
995 remiCodeFromeBBlock (ebbs[i], ic);
997 /* for the left & right remove the usage */
998 if (IS_SYMOP (IC_LEFT (ic)))
999 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
1001 if (IS_SYMOP (IC_RIGHT (ic)))
1002 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1006 } /* end of all instructions */
1008 if (!ebbs[i]->sch && !ebbs[i]->noPath)
1009 disconBBlock (ebbs[i], ebbs, count);
1011 } /* end of for all blocks */
1015 } /* end of while(1) */
1020 /*-----------------------------------------------------------------*/
1021 /* printCyclomatic - prints the cyclomatic information */
1022 /*-----------------------------------------------------------------*/
1024 printCyclomatic (eBBlock ** ebbs, int count)
1026 int nEdges = elementsInSet (graphEdges);
1029 for (i = 0; i < count; i++)
1030 nNodes += (!ebbs[i]->noPath);
1032 /* print the information */
1033 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
1036 /*-----------------------------------------------------------------*/
1037 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
1038 /* refer to dead variables. */
1039 /*-----------------------------------------------------------------*/
1041 discardDeadParamReceives (eBBlock ** ebbs, int count)
1047 for (i = 0; i < count; i++)
1049 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1051 if (ic->op == RECEIVE)
1053 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
1054 && !OP_SYMBOL (IC_RESULT (ic))->used)
1057 fprintf (stderr, "discarding dead receive for %s\n",
1058 OP_SYMBOL (IC_RESULT (ic))->name);
1060 dummyIcode.next = ic->next;
1061 remiCodeFromeBBlock (ebbs[i], ic);
1069 /*-----------------------------------------------------------------*/
1070 /* optimizeCastCast - remove unneeded intermediate casts. */
1071 /* Integer promotion may cast (un)signed char to int and then */
1072 /* recast the int to (un)signed long. If the signedness of the */
1073 /* char and long are the same, the cast can be safely performed in */
1074 /* a single step. */
1075 /*-----------------------------------------------------------------*/
1077 optimizeCastCast (eBBlock ** ebbs, int count)
1087 for (i = 0; i < count; i++)
1089 for (ic = ebbs[i]->sch; ic; ic = ic->next)
1092 if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1094 type1 = operandType (IC_RIGHT (ic));
1095 type2 = operandType (IC_RESULT (ic));
1097 /* Look only for a cast from an integer type to an */
1098 /* integer type that has no loss of bits */
1099 if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1101 if (getSize (type2) < getSize (type1))
1104 /* There must be only one use of this first result */
1105 if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1108 /* This use must be a second cast */
1109 uic = hTabItemWithKey (iCodehTab,
1110 bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1111 if (!uic || uic->op != CAST)
1114 /* It must be a cast to another integer type that */
1115 /* has no loss of bits */
1116 type3 = operandType (IC_RESULT (uic));
1117 if (!IS_INTEGRAL (type3))
1119 if (getSize (type3) < getSize (type2))
1122 /* The signedness between the first and last types */
1124 if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1127 /* Change the first cast to a simple assignment and */
1128 /* let the second cast do all the work */
1130 IC_LEFT (ic) = NULL;
1131 sym = OP_SYMBOL (IC_RESULT (ic));
1132 sym->type = copyLinkChain (type1);
1133 sym->etype = getSpec (sym->type);
1139 /*-----------------------------------------------------------------*/
1140 /* eBBlockFromiCode - creates extended basic blocks from iCode */
1141 /* will return an array of eBBlock pointers */
1142 /*-----------------------------------------------------------------*/
1144 eBBlockFromiCode (iCode * ic)
1146 eBBlock **ebbs = NULL;
1154 /* if nothing passed then return nothing */
1161 /* optimize the chain for labels & gotos
1162 this will eliminate redundant labels and
1163 will change jump to jumps by jumps */
1164 ic = iCodeLabelOptimize (ic);
1166 /* break it down into basic blocks */
1167 ebbs = iCodeBreakDown (ic, &count);
1170 /* hash the iCode keys so that we can quickly index */
1171 /* them in the rest of the optimization steps */
1172 setToNull ((void *) &iCodehTab);
1173 iCodehTab = newHashTable (iCodeKey);
1174 hashiCodeKeys (ebbs, count);
1176 /* compute the control flow */
1177 computeControlFlow (ebbs, count, 0);
1179 /* dumpraw if asked for */
1180 if (options.dump_raw)
1181 dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
1183 /* replace the local variables with their
1184 register equivalents : the liveRange computation
1185 along with the register allocation will determine
1186 if it finally stays in the registers */
1187 replaceRegEqv (ebbs, count);
1189 /* create loop regions */
1190 loops = createLoopRegions (ebbs, count);
1192 /* dumpraw if asked for */
1193 if (options.dump_raw)
1194 dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
1196 optimizeCastCast (ebbs, saveCount);
1198 /* do common subexpression elimination for each block */
1199 change = cseAllBlocks (ebbs, saveCount, FALSE);
1201 /* dumpraw if asked for */
1202 if (options.dump_raw)
1203 dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
1205 /* compute the data flow */
1206 computeDataFlow (ebbs, saveCount);
1208 /* dumpraw if asked for */
1209 if (options.dump_raw)
1210 dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
1212 /* global common subexpression elimination */
1213 if (optimize.global_cse)
1215 change += cseAllBlocks (ebbs, saveCount, FALSE);
1216 if (options.dump_gcse)
1217 dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
1221 // compute the dataflow only
1222 assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
1224 /* kill dead code */
1225 kchange = killDeadCode (ebbs, saveCount);
1227 if (options.dump_kill)
1228 dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
1230 /* do loop optimizations */
1231 change += (lchange = loopOptimizations (loops, ebbs, count));
1232 if (options.dump_loop)
1233 dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
1235 /* recompute the data flow and apply global cse again
1236 if loops optimizations or dead code caused a change:
1237 loops will brings out of the loop which then may be
1238 available for use in the later blocks: dead code
1239 elimination could potentially disconnect some blocks
1240 conditional flow may be efected so we need to apply
1241 subexpression once more */
1242 if (lchange || kchange)
1244 computeDataFlow (ebbs, saveCount);
1245 change += cseAllBlocks (ebbs, saveCount, FALSE);
1246 if (options.dump_loop)
1247 dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
1249 /* if loop optimizations caused a change then do
1250 dead code elimination once more : this will
1251 get rid of the extra assignments to the induction
1252 variables created during loop optimizations */
1253 killDeadCode (ebbs, saveCount);
1255 if (options.dump_loop)
1256 dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1260 /* sort it back by block number */
1261 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1263 if (!options.lessPedantic) {
1264 // this is a good place to check missing return values
1266 // the user is on his own with naked functions...
1267 if (!IS_VOID(currFunc->etype)
1268 && !FUNC_ISNAKED(currFunc->type)) {
1270 // make sure all predecessors of the last block end in a return
1271 for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1273 bp=setNextItem(ebbs[saveCount-1]->predList)) {
1274 if (bp->ech->op != RETURN) {
1275 werrorfl (bp->ech->filename, bp->ech->lineno,
1276 W_VOID_FUNC, currFunc->name);
1283 /* if cyclomatic info requested then print it */
1284 if (options.cyclomatic)
1285 printCyclomatic (ebbs, saveCount);
1287 /* convert operations with support routines
1288 written in C to function calls : Iam doing
1289 this at this point since I want all the
1290 operations to be as they are for optimzations */
1291 convertToFcall (ebbs, count);
1293 /* compute the live ranges */
1294 computeLiveRanges (ebbs, count);
1296 if (options.dump_range)
1297 dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1299 /* Now that we have the live ranges, discard parameter
1300 * receives for unused parameters.
1302 discardDeadParamReceives (ebbs, count);
1304 /* allocate registers & generate code */
1305 port->assignRegisters (ebbs, count);
1307 /* throw away blocks */
1308 setToNull ((void *) &graphEdges);
1315 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */