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);
154 addiCodeToeBBlock (ebp, newic, ip);
155 newic->lineno = lineno;
157 /* insert push left */
158 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
160 newic = newiCode (SEND, left, NULL);
161 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
165 newic = newiCode (IPUSH, left, NULL);
169 addiCodeToeBBlock (ebp, newic, ip);
170 newic->lineno = lineno;
172 /* insert the call */
173 newic = newiCode (CALL, operandFromSymbol (func), NULL);
174 IC_RESULT (newic) = IC_RESULT (ic);
175 newic->lineno = lineno;
176 newic->parmBytes+=bytesPushed;
177 addiCodeToeBBlock (ebp, newic, ip);
180 /*-----------------------------------------------------------------*/
181 /* cnvToFloatCast - converts casts to floats to function calls */
182 /*-----------------------------------------------------------------*/
184 cnvToFloatCast (iCode * ic, eBBlock * ebp)
188 sym_link *type = operandType (IC_RIGHT (ic));
189 int linenno = ic->lineno;
193 /* remove it from the iCode */
194 remiCodeFromeBBlock (ebp, ic);
195 /* depending on the type */
196 for (bwd = 0; bwd < 3; bwd++)
198 for (su = 0; su < 2; su++)
200 if (compareType (type, __multypes[bwd][su]) == 1)
202 func = __conv[0][bwd][su];
210 /* if float support routines NOT compiled as reentrant */
211 if (!options.float_rent)
214 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
216 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
217 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
221 newic = newiCode ('=', NULL, IC_RIGHT (ic));
222 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
224 addiCodeToeBBlock (ebp, newic, ip);
225 newic->lineno = linenno;
231 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
232 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
233 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
237 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
240 addiCodeToeBBlock (ebp, newic, ip);
241 newic->lineno = linenno;
246 newic = newiCode (CALL, operandFromSymbol (func), NULL);
247 IC_RESULT (newic) = IC_RESULT (ic);
248 addiCodeToeBBlock (ebp, newic, ip);
249 newic->lineno = linenno;
253 /*-----------------------------------------------------------------*/
254 /* cnvFromFloatCast - converts casts From floats to function calls */
255 /*-----------------------------------------------------------------*/
257 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
261 sym_link *type = operandType (IC_LEFT (ic));
262 int lineno = ic->lineno;
266 /* remove it from the iCode */
267 remiCodeFromeBBlock (ebp, ic);
269 /* depending on the type */
270 for (bwd = 0; bwd < 3; bwd++)
272 for (su = 0; su < 2; su++)
274 if (compareType (type, __multypes[bwd][su]) == 1)
276 func = __conv[1][bwd][su];
284 /* if float support routines NOT compiled as reentrant */
285 if (!options.float_rent)
288 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
289 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
290 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
294 newic = newiCode ('=', NULL, IC_RIGHT (ic));
295 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
297 addiCodeToeBBlock (ebp, newic, ip);
298 newic->lineno = lineno;
305 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
306 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
307 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
311 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
314 addiCodeToeBBlock (ebp, newic, ip);
315 newic->lineno = lineno;
320 newic = newiCode (CALL, operandFromSymbol (func), NULL);
321 IC_RESULT (newic) = IC_RESULT (ic);
322 addiCodeToeBBlock (ebp, newic, ip);
323 newic->lineno = lineno;
327 /*-----------------------------------------------------------------*/
328 /* convilong - converts int or long mults or divs to fcalls */
329 /*-----------------------------------------------------------------*/
331 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
334 iCode *ip = ic->next;
336 int lineno = ic->lineno;
341 remiCodeFromeBBlock (ebp, ic);
343 /* depending on the type */
344 for (bwd = 0; bwd < 3; bwd++)
346 for (su = 0; su < 2; su++)
348 if (compareType (type, __multypes[bwd][su]) == 1)
351 func = __muldiv[0][bwd][su];
353 func = __muldiv[1][bwd][su];
355 func = __muldiv[2][bwd][su];
357 func = __rlrr[1][bwd][su];
359 func = __rlrr[0][bwd][su];
360 else if (op == RIGHT_OP)
361 func = __rlrr[1][bwd][su];
362 else if (op == LEFT_OP)
363 func = __rlrr[0][bwd][su];
372 /* if int & long support routines NOT compiled as reentrant */
373 if (!options.intlong_rent)
376 if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
377 newic = newiCode (SEND, IC_LEFT (ic), NULL);
378 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
382 newic = newiCode ('=', NULL, IC_LEFT (ic));
383 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
385 addiCodeToeBBlock (ebp, newic, ip);
386 newic->lineno = lineno;
389 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
390 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
391 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
395 newic = newiCode ('=', NULL, IC_RIGHT (ic));
396 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
398 addiCodeToeBBlock (ebp, newic, ip);
399 newic->lineno = lineno;
404 /* compiled as reentrant then push */
406 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
408 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
409 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
413 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
416 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
418 addiCodeToeBBlock (ebp, newic, ip);
419 newic->lineno = lineno;
421 /* insert push left */
422 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
424 newic = newiCode (SEND, IC_LEFT (ic), NULL);
425 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
429 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
432 bytesPushed += getSize(operandType(IC_LEFT(ic)));
434 addiCodeToeBBlock (ebp, newic, ip);
435 newic->lineno = lineno;
440 newic = newiCode (CALL, operandFromSymbol (func), NULL);
441 IC_RESULT (newic) = IC_RESULT (ic);
442 newic->lineno = lineno;
443 newic->parmBytes+=bytesPushed; // to clear the stack after the call
444 addiCodeToeBBlock (ebp, newic, ip);
447 /*-----------------------------------------------------------------*/
448 /* convertToFcall - converts some operations to fcalls */
449 /*-----------------------------------------------------------------*/
451 convertToFcall (eBBlock ** ebbs, int count)
455 /* for all blocks do */
456 for (i = 0; i < count; i++)
460 /* for all instructions in the block do */
461 for (ic = ebbs[i]->sch; ic; ic = ic->next)
464 /* floating point operations are
465 converted to function calls */
466 if ((IS_CONDITIONAL (ic) ||
467 IS_ARITHMETIC_OP (ic)) &&
468 (IS_FLOAT (operandType (IC_RIGHT (ic)))))
471 cnvToFcall (ic, ebbs[i]);
474 /* casting is a little different */
477 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
478 cnvFromFloatCast (ic, ebbs[i]);
479 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
480 cnvToFloatCast (ic, ebbs[i]);
483 /* if long / int mult or divide or mod */
484 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
486 sym_link *leftType = operandType (IC_LEFT (ic));
488 if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
490 sym_link *rightType = operandType (IC_RIGHT (ic));
492 if (port->hasNativeMulFor != NULL &&
493 port->hasNativeMulFor (ic, leftType, rightType))
495 /* Leave as native */
499 convilong (ic, ebbs[i], leftType, ic->op);
504 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
506 sym_link *type = operandType (IC_LEFT (ic));
508 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
510 convilong (ic, ebbs[i], type, ic->op);
517 /*-----------------------------------------------------------------*/
518 /* replaceRegEqv - replace all local variables with their reqv */
519 /*-----------------------------------------------------------------*/
521 replaceRegEqv (eBBlock ** ebbs, int count)
525 for (i = 0; i < count; i++)
530 for (ic = ebbs[i]->sch; ic; ic = ic->next)
539 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
540 OP_REQV (IC_COND (ic)))
541 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
542 OP_SYMBOL (IC_COND (ic))->defs,
543 OP_SYMBOL (IC_COND (ic))->uses);
548 if (ic->op == JUMPTABLE)
550 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
551 OP_REQV (IC_JTCOND (ic)))
552 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
553 OP_SYMBOL (IC_JTCOND (ic))->defs,
554 OP_SYMBOL (IC_JTCOND (ic))->uses);
558 if (ic->op == RECEIVE)
560 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
561 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
565 if (IC_RESULT (ic) &&
566 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
567 OP_REQV (IC_RESULT (ic)))
569 if (POINTER_SET (ic))
571 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
572 OP_SYMBOL (IC_RESULT (ic))->defs,
573 OP_SYMBOL (IC_RESULT (ic))->uses);
574 IC_RESULT (ic)->isaddr = 1;
577 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
578 OP_SYMBOL (IC_RESULT (ic))->defs,
579 OP_SYMBOL (IC_RESULT (ic))->uses);
583 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
584 OP_REQV (IC_RIGHT (ic)))
586 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
587 OP_SYMBOL (IC_RIGHT (ic))->defs,
588 OP_SYMBOL (IC_RIGHT (ic))->uses);
589 IC_RIGHT (ic)->isaddr = 0;
593 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
594 OP_REQV (IC_LEFT (ic)))
596 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
597 OP_SYMBOL (IC_LEFT (ic))->defs,
598 OP_SYMBOL (IC_LEFT (ic))->uses);
599 IC_LEFT (ic)->isaddr = 0;
605 /*-----------------------------------------------------------------*/
606 /* killDeadCode - eliminates dead assignments */
607 /*-----------------------------------------------------------------*/
609 killDeadCode (eBBlock ** ebbs, int count)
616 /* basic algorithm :- */
617 /* first the exclusion rules :- */
618 /* 1. if result is a global or volatile then skip */
619 /* 2. if assignment and result is a temp & isaddr then skip */
620 /* since this means array & pointer access, will be taken */
621 /* care of by alias analysis. */
622 /* 3. if the result is used in the remainder of the block skip */
623 /* 4. if this definition does not reach the end of the block */
624 /* i.e. the result is not present in the outExprs then KILL */
625 /* 5. if it reaches the end of block & is used by some success */
628 /* this whole process is carried on iteratively till no change */
633 /* for all blocks do */
634 for (i = 0; i < count; i++)
638 /* for all instructions in the block do */
639 for (ic = ebbs[i]->sch; ic; ic = ic->next)
649 /* if the result is volatile then continue */
650 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
653 /* if the result is a temp & isaddr then skip */
654 if (IC_RESULT (ic) && POINTER_SET (ic))
657 /* if the result is used in the remainder of the */
658 /* block then skip */
659 if (usedInRemaining (IC_RESULT (ic), ic->next))
662 /* does this definition reach the end of the block
663 or the usage is zero then we can kill */
664 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
665 kill = 1; /* if not we can kill it */
668 /* if this is a global variable or function parameter */
669 /* we cannot kill anyway */
670 if (isOperandGlobal (IC_RESULT (ic)) ||
671 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
672 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
675 /* if we are sure there are no usages */
676 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
682 /* reset visited flag */
683 for (j = 0; j < count; ebbs[j++]->visited = 0);
685 /* find out if this definition is alive */
686 if (applyToSet (ebbs[i]->succList,
695 /* kill this one if required */
701 remiCodeFromeBBlock (ebbs[i], ic);
703 /* now delete from defUseSet */
704 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
705 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
707 /* and defset of the block */
708 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
710 /* for the left & right remove the usage */
711 if (IS_SYMOP (IC_LEFT (ic)))
712 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
714 if (IS_SYMOP (IC_RIGHT (ic)))
715 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
718 } /* end of all instructions */
720 if (!ebbs[i]->sch && !ebbs[i]->noPath)
721 disconBBlock (ebbs[i], ebbs, count);
723 } /* end of for all blocks */
727 } /* end of while(1) */
732 /*-----------------------------------------------------------------*/
733 /* printCyclomatic - prints the cyclomatic information */
734 /*-----------------------------------------------------------------*/
736 printCyclomatic (eBBlock ** ebbs, int count)
738 int nEdges = elementsInSet (graphEdges);
741 for (i = 0; i < count; i++)
742 nNodes += (!ebbs[i]->noPath);
744 /* print the information */
745 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
748 /*-----------------------------------------------------------------*/
749 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
750 /* refer to dead variables. */
751 /*-----------------------------------------------------------------*/
753 discardDeadParamReceives (eBBlock ** ebbs, int count)
759 for (i = 0; i < count; i++)
761 for (ic = ebbs[i]->sch; ic; ic = ic->next)
763 if (ic->op == RECEIVE)
765 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
766 && !OP_SYMBOL (IC_RESULT (ic))->used)
769 fprintf (stderr, "discarding dead receive for %s\n",
770 OP_SYMBOL (IC_RESULT (ic))->name);
772 dummyIcode.next = ic->next;
773 remiCodeFromeBBlock (ebbs[i], ic);
781 /*-----------------------------------------------------------------*/
782 /* eBBlockFromiCode - creates extended basic blocks from iCode */
783 /* will return an array of eBBlock pointers */
784 /*-----------------------------------------------------------------*/
786 eBBlockFromiCode (iCode * ic)
788 eBBlock **ebbs = NULL;
796 /* if nothing passed then return nothing */
803 /* optimize the chain for labels & gotos
804 this will eliminate redundant labels and
805 will change jump to jumps by jumps */
806 ic = iCodeLabelOptimize (ic);
808 /* break it down into basic blocks */
809 ebbs = iCodeBreakDown (ic, &count);
812 /* compute the control flow */
813 computeControlFlow (ebbs, count, 0);
815 /* dumpraw if asked for */
816 if (options.dump_raw)
817 dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
819 /* replace the local variables with their
820 register equivalents : the liveRange computation
821 along with the register allocation will determine
822 if it finally stays in the registers */
823 replaceRegEqv (ebbs, count);
825 /* create loop regions */
826 loops = createLoopRegions (ebbs, count);
828 /* dumpraw if asked for */
829 if (options.dump_raw)
830 dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
832 /* do common subexpression elimination for each block */
833 change = cseAllBlocks (ebbs, saveCount);
835 /* dumpraw if asked for */
836 if (options.dump_raw)
837 dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
839 /* compute the data flow */
840 computeDataFlow (ebbs, saveCount);
842 /* dumpraw if asked for */
843 if (options.dump_raw)
844 dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
846 /* global common subexpression elimination */
847 if (optimize.global_cse)
849 change += cseAllBlocks (ebbs, saveCount);
850 if (options.dump_gcse)
851 dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
854 kchange = killDeadCode (ebbs, saveCount);
856 if (options.dump_kill)
857 dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
859 /* do loop optimizations */
860 change += (lchange = loopOptimizations (loops, ebbs, count));
861 if (options.dump_loop)
862 dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
864 /* recompute the data flow and apply global cse again
865 if loops optimizations or dead code caused a change:
866 loops will brings out of the loop which then may be
867 available for use in the later blocks: dead code
868 elimination could potentially disconnect some blocks
869 conditional flow may be efected so we need to apply
870 subexpression once more */
871 if (lchange || kchange)
873 computeDataFlow (ebbs, saveCount);
874 change += cseAllBlocks (ebbs, saveCount);
875 if (options.dump_loop)
876 dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
878 /* if loop optimizations caused a change then do
879 dead code elimination once more : this will
880 get rid of the extra assignments to the induction
881 variables created during loop optimizations */
882 killDeadCode (ebbs, saveCount);
884 if (options.dump_loop)
885 dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
889 /* sort it back by block number */
890 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
892 /* if cyclomatic info requested then print it */
893 if (options.cyclomatic)
894 printCyclomatic (ebbs, saveCount);
896 /* convert operations with support routines
897 written in C to function calls : Iam doing
898 this at this point since I want all the
899 operations to be as they are for optimzations */
900 convertToFcall (ebbs, count);
902 /* compute the live ranges */
903 computeLiveRanges (ebbs, count);
905 if (options.dump_range)
906 dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
908 /* Now that we have the live ranges, discard parameter
909 * receives for unused parameters.
911 discardDeadParamReceives (ebbs, count);
913 /* allocate registers & generate code */
914 port->assignRegisters (ebbs, count);
916 /* throw away blocks */
917 setToNull ((void **) &graphEdges);
924 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */