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);
115 newic = newiCode ('=', NULL, IC_LEFT (ic));
116 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
119 addiCodeToeBBlock (ebp, newic, ip);
120 newic->lineno = lineno;
123 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
125 newic = newiCode (SEND, IC_LEFT (ic), NULL);
129 newic = newiCode ('=', NULL, IC_RIGHT (ic));
130 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
132 addiCodeToeBBlock (ebp, newic, ip);
133 newic->lineno = lineno;
140 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
142 newic = newiCode (SEND, right, NULL);
146 newic = newiCode (IPUSH, right, NULL);
151 addiCodeToeBBlock (ebp, newic, ip);
152 newic->lineno = lineno;
154 /* insert push left */
155 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
157 newic = newiCode (SEND, left, NULL);
161 newic = newiCode (IPUSH, left, NULL);
165 addiCodeToeBBlock (ebp, newic, ip);
166 newic->lineno = lineno;
168 /* insert the call */
169 newic = newiCode (CALL, operandFromSymbol (func), NULL);
170 IC_RESULT (newic) = IC_RESULT (ic);
171 newic->lineno = lineno;
172 newic->parmBytes+=bytesPushed;
173 addiCodeToeBBlock (ebp, newic, ip);
176 /*-----------------------------------------------------------------*/
177 /* cnvToFloatCast - converts casts to floats to function calls */
178 /*-----------------------------------------------------------------*/
180 cnvToFloatCast (iCode * ic, eBBlock * ebp)
184 sym_link *type = operandType (IC_RIGHT (ic));
185 int linenno = ic->lineno;
189 /* remove it from the iCode */
190 remiCodeFromeBBlock (ebp, ic);
191 /* depending on the type */
192 for (bwd = 0; bwd < 3; bwd++)
194 for (su = 0; su < 2; su++)
196 if (compareType (type, __multypes[bwd][su]) == 1)
198 func = __conv[0][bwd][su];
206 /* if float support routines NOT compiled as reentrant */
207 if (!options.float_rent)
210 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
211 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
214 newic = newiCode ('=', NULL, IC_RIGHT (ic));
215 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
217 addiCodeToeBBlock (ebp, newic, ip);
218 newic->lineno = linenno;
224 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
225 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
228 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
231 addiCodeToeBBlock (ebp, newic, ip);
232 newic->lineno = linenno;
237 newic = newiCode (CALL, operandFromSymbol (func), NULL);
238 IC_RESULT (newic) = IC_RESULT (ic);
239 addiCodeToeBBlock (ebp, newic, ip);
240 newic->lineno = linenno;
244 /*-----------------------------------------------------------------*/
245 /* cnvFromFloatCast - converts casts From floats to function calls */
246 /*-----------------------------------------------------------------*/
248 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
252 sym_link *type = operandType (IC_LEFT (ic));
253 int lineno = ic->lineno;
257 /* remove it from the iCode */
258 remiCodeFromeBBlock (ebp, ic);
260 /* depending on the type */
261 for (bwd = 0; bwd < 3; bwd++)
263 for (su = 0; su < 2; su++)
265 if (compareType (type, __multypes[bwd][su]) == 1)
267 func = __conv[1][bwd][su];
275 /* if float support routines NOT compiled as reentrant */
276 if (!options.float_rent)
279 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
280 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
283 newic = newiCode ('=', NULL, IC_RIGHT (ic));
284 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
286 addiCodeToeBBlock (ebp, newic, ip);
287 newic->lineno = lineno;
294 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
295 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
298 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
301 addiCodeToeBBlock (ebp, newic, ip);
302 newic->lineno = lineno;
307 newic = newiCode (CALL, operandFromSymbol (func), NULL);
308 IC_RESULT (newic) = IC_RESULT (ic);
309 addiCodeToeBBlock (ebp, newic, ip);
310 newic->lineno = lineno;
314 /*-----------------------------------------------------------------*/
315 /* convilong - converts int or long mults or divs to fcalls */
316 /*-----------------------------------------------------------------*/
318 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
321 iCode *ip = ic->next;
323 int lineno = ic->lineno;
328 remiCodeFromeBBlock (ebp, ic);
330 /* depending on the type */
331 for (bwd = 0; bwd < 3; bwd++)
333 for (su = 0; su < 2; su++)
335 if (compareType (type, __multypes[bwd][su]) == 1)
338 func = __muldiv[0][bwd][su];
340 func = __muldiv[1][bwd][su];
342 func = __muldiv[2][bwd][su];
344 func = __rlrr[1][bwd][su];
346 func = __rlrr[0][bwd][su];
347 else if (op == RIGHT_OP)
348 func = __rlrr[1][bwd][su];
349 else if (op == LEFT_OP)
350 func = __rlrr[0][bwd][su];
359 /* if int & long support routines NOT compiled as reentrant */
360 if (!options.intlong_rent)
363 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
364 newic = newiCode (SEND, IC_LEFT (ic), NULL);
367 newic = newiCode ('=', NULL, IC_LEFT (ic));
368 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
370 addiCodeToeBBlock (ebp, newic, ip);
371 newic->lineno = lineno;
374 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
375 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
378 newic = newiCode ('=', NULL, IC_RIGHT (ic));
379 IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
381 addiCodeToeBBlock (ebp, newic, ip);
382 newic->lineno = lineno;
387 /* compiled as reentrant then push */
389 if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
391 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
395 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
398 bytesPushed += getSize(operandType(IC_RIGHT(ic)));
400 addiCodeToeBBlock (ebp, newic, ip);
401 newic->lineno = lineno;
403 /* insert push left */
404 if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
406 newic = newiCode (SEND, IC_LEFT (ic), NULL);
410 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
413 bytesPushed += getSize(operandType(IC_LEFT(ic)));
415 addiCodeToeBBlock (ebp, newic, ip);
416 newic->lineno = lineno;
421 newic = newiCode (CALL, operandFromSymbol (func), NULL);
422 IC_RESULT (newic) = IC_RESULT (ic);
423 newic->lineno = lineno;
424 newic->parmBytes+=bytesPushed; // to clear the stack after the call
425 addiCodeToeBBlock (ebp, newic, ip);
428 /*-----------------------------------------------------------------*/
429 /* convertToFcall - converts some operations to fcalls */
430 /*-----------------------------------------------------------------*/
432 convertToFcall (eBBlock ** ebbs, int count)
436 /* for all blocks do */
437 for (i = 0; i < count; i++)
441 /* for all instructions in the block do */
442 for (ic = ebbs[i]->sch; ic; ic = ic->next)
445 /* floating point operations are
446 converted to function calls */
447 if ((IS_CONDITIONAL (ic) ||
448 IS_ARITHMETIC_OP (ic)) &&
449 (IS_FLOAT (operandType (IC_RIGHT (ic)))))
452 cnvToFcall (ic, ebbs[i]);
455 /* casting is a little different */
458 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
459 cnvFromFloatCast (ic, ebbs[i]);
460 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
461 cnvToFloatCast (ic, ebbs[i]);
464 /* if long / int mult or divide or mod */
465 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
467 sym_link *leftType = operandType (IC_LEFT (ic));
469 if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
471 sym_link *rightType = operandType (IC_RIGHT (ic));
473 if (port->hasNativeMulFor != NULL &&
474 port->hasNativeMulFor (ic, leftType, rightType))
476 /* Leave as native */
480 convilong (ic, ebbs[i], leftType, ic->op);
485 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
487 sym_link *type = operandType (IC_LEFT (ic));
489 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
491 convilong (ic, ebbs[i], type, ic->op);
498 /*-----------------------------------------------------------------*/
499 /* replaceRegEqv - replace all local variables with their reqv */
500 /*-----------------------------------------------------------------*/
502 replaceRegEqv (eBBlock ** ebbs, int count)
506 for (i = 0; i < count; i++)
511 for (ic = ebbs[i]->sch; ic; ic = ic->next)
520 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
521 OP_REQV (IC_COND (ic)))
522 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
523 OP_SYMBOL (IC_COND (ic))->defs,
524 OP_SYMBOL (IC_COND (ic))->uses);
529 if (ic->op == JUMPTABLE)
531 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
532 OP_REQV (IC_JTCOND (ic)))
533 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
534 OP_SYMBOL (IC_JTCOND (ic))->defs,
535 OP_SYMBOL (IC_JTCOND (ic))->uses);
539 if (ic->op == RECEIVE)
541 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
542 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
546 if (IC_RESULT (ic) &&
547 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
548 OP_REQV (IC_RESULT (ic)))
550 if (POINTER_SET (ic))
552 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
553 OP_SYMBOL (IC_RESULT (ic))->defs,
554 OP_SYMBOL (IC_RESULT (ic))->uses);
555 IC_RESULT (ic)->isaddr = 1;
558 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
559 OP_SYMBOL (IC_RESULT (ic))->defs,
560 OP_SYMBOL (IC_RESULT (ic))->uses);
564 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
565 OP_REQV (IC_RIGHT (ic)))
567 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
568 OP_SYMBOL (IC_RIGHT (ic))->defs,
569 OP_SYMBOL (IC_RIGHT (ic))->uses);
570 IC_RIGHT (ic)->isaddr = 0;
574 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
575 OP_REQV (IC_LEFT (ic)))
577 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
578 OP_SYMBOL (IC_LEFT (ic))->defs,
579 OP_SYMBOL (IC_LEFT (ic))->uses);
580 IC_LEFT (ic)->isaddr = 0;
586 /*-----------------------------------------------------------------*/
587 /* killDeadCode - eliminates dead assignments */
588 /*-----------------------------------------------------------------*/
590 killDeadCode (eBBlock ** ebbs, int count)
597 /* basic algorithm :- */
598 /* first the exclusion rules :- */
599 /* 1. if result is a global or volatile then skip */
600 /* 2. if assignment and result is a temp & isaddr then skip */
601 /* since this means array & pointer access, will be taken */
602 /* care of by alias analysis. */
603 /* 3. if the result is used in the remainder of the block skip */
604 /* 4. if this definition does not reach the end of the block */
605 /* i.e. the result is not present in the outExprs then KILL */
606 /* 5. if it reaches the end of block & is used by some success */
609 /* this whole process is carried on iteratively till no change */
614 /* for all blocks do */
615 for (i = 0; i < count; i++)
619 /* for all instructions in the block do */
620 for (ic = ebbs[i]->sch; ic; ic = ic->next)
630 /* if the result is volatile then continue */
631 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
634 /* if the result is a temp & isaddr then skip */
635 if (IC_RESULT (ic) && POINTER_SET (ic))
638 /* if the result is used in the remainder of the */
639 /* block then skip */
640 if (usedInRemaining (IC_RESULT (ic), ic->next))
643 /* does this definition reach the end of the block
644 or the usage is zero then we can kill */
645 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
646 kill = 1; /* if not we can kill it */
649 /* if this is a global variable or function parameter */
650 /* we cannot kill anyway */
651 if (isOperandGlobal (IC_RESULT (ic)) ||
652 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
653 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
656 /* if we are sure there are no usages */
657 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
663 /* reset visited flag */
664 for (j = 0; j < count; ebbs[j++]->visited = 0);
666 /* find out if this definition is alive */
667 if (applyToSet (ebbs[i]->succList,
676 /* kill this one if required */
682 remiCodeFromeBBlock (ebbs[i], ic);
684 /* now delete from defUseSet */
685 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
686 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
688 /* and defset of the block */
689 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
691 /* for the left & right remove the usage */
692 if (IS_SYMOP (IC_LEFT (ic)))
693 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
695 if (IS_SYMOP (IC_RIGHT (ic)))
696 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
699 } /* end of all instructions */
701 if (!ebbs[i]->sch && !ebbs[i]->noPath)
702 disconBBlock (ebbs[i], ebbs, count);
704 } /* end of for all blocks */
708 } /* end of while(1) */
713 /*-----------------------------------------------------------------*/
714 /* printCyclomatic - prints the cyclomatic information */
715 /*-----------------------------------------------------------------*/
717 printCyclomatic (eBBlock ** ebbs, int count)
719 int nEdges = elementsInSet (graphEdges);
722 for (i = 0; i < count; i++)
723 nNodes += (!ebbs[i]->noPath);
725 /* print the information */
726 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
729 /*-----------------------------------------------------------------*/
730 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
731 /* refer to dead variables. */
732 /*-----------------------------------------------------------------*/
734 discardDeadParamReceives (eBBlock ** ebbs, int count)
740 for (i = 0; i < count; i++)
742 for (ic = ebbs[i]->sch; ic; ic = ic->next)
744 if (ic->op == RECEIVE)
746 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
747 && !OP_SYMBOL (IC_RESULT (ic))->used)
750 fprintf (stderr, "discarding dead receive for %s\n",
751 OP_SYMBOL (IC_RESULT (ic))->name);
753 dummyIcode.next = ic->next;
754 remiCodeFromeBBlock (ebbs[i], ic);
762 /*-----------------------------------------------------------------*/
763 /* eBBlockFromiCode - creates extended basic blocks from iCode */
764 /* will return an array of eBBlock pointers */
765 /*-----------------------------------------------------------------*/
767 eBBlockFromiCode (iCode * ic)
769 eBBlock **ebbs = NULL;
777 /* if nothing passed then return nothing */
784 /* optimize the chain for labels & gotos
785 this will eliminate redundant labels and
786 will change jump to jumps by jumps */
787 ic = iCodeLabelOptimize (ic);
789 /* break it down into basic blocks */
790 ebbs = iCodeBreakDown (ic, &count);
793 /* compute the control flow */
794 computeControlFlow (ebbs, count, 0);
796 /* dumpraw if asked for */
797 if (options.dump_raw)
798 dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
800 /* replace the local variables with their
801 register equivalents : the liveRange computation
802 along with the register allocation will determine
803 if it finally stays in the registers */
804 replaceRegEqv (ebbs, count);
806 /* create loop regions */
807 loops = createLoopRegions (ebbs, count);
809 /* dumpraw if asked for */
810 if (options.dump_raw)
811 dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
813 /* do common subexpression elimination for each block */
814 change = cseAllBlocks (ebbs, saveCount);
816 /* dumpraw if asked for */
817 if (options.dump_raw)
818 dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
820 /* compute the data flow */
821 computeDataFlow (ebbs, saveCount);
823 /* dumpraw if asked for */
824 if (options.dump_raw)
825 dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
827 /* global common subexpression elimination */
828 if (optimize.global_cse)
830 change += cseAllBlocks (ebbs, saveCount);
831 if (options.dump_gcse)
832 dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
835 kchange = killDeadCode (ebbs, saveCount);
837 if (options.dump_kill)
838 dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
840 /* do loop optimizations */
841 change += (lchange = loopOptimizations (loops, ebbs, count));
842 if (options.dump_loop)
843 dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
845 /* recompute the data flow and apply global cse again
846 if loops optimizations or dead code caused a change:
847 loops will brings out of the loop which then may be
848 available for use in the later blocks: dead code
849 elimination could potentially disconnect some blocks
850 conditional flow may be efected so we need to apply
851 subexpression once more */
852 if (lchange || kchange)
854 computeDataFlow (ebbs, saveCount);
855 change += cseAllBlocks (ebbs, saveCount);
856 if (options.dump_loop)
857 dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
859 /* if loop optimizations caused a change then do
860 dead code elimination once more : this will
861 get rid of the extra assignments to the induction
862 variables created during loop optimizations */
863 killDeadCode (ebbs, saveCount);
865 if (options.dump_loop)
866 dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
870 /* sort it back by block number */
871 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
873 /* if cyclomatic info requested then print it */
874 if (options.cyclomatic)
875 printCyclomatic (ebbs, saveCount);
877 /* convert operations with support routines
878 written in C to function calls : Iam doing
879 this at this point since I want all the
880 operations to be as they are for optimzations */
881 convertToFcall (ebbs, count);
883 /* compute the live ranges */
884 computeLiveRanges (ebbs, count);
886 if (options.dump_range)
887 dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
889 /* Now that we have the live ranges, discard parameter
890 * receives for unused parameters.
892 discardDeadParamReceives (ebbs, count);
894 /* allocate registers & generate code */
895 port->assignRegisters (ebbs, count);
897 /* throw away blocks */
898 setToNull ((void **) &graphEdges);
905 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */