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->etype))
111 newic = newiCode (SEND, IC_LEFT (ic), NULL);
115 newic = newiCode ('=', NULL, IC_LEFT (ic));
116 IC_RESULT (newic) = operandFromValue (func->args);
119 addiCodeToeBBlock (ebp, newic, ip);
120 newic->lineno = lineno;
123 if (IS_REGPARM (func->args->next->etype))
125 newic = newiCode (SEND, IC_LEFT (ic), NULL);
129 newic = newiCode ('=', NULL, IC_RIGHT (ic));
130 IC_RESULT (newic) = operandFromValue (func->args->next);
132 addiCodeToeBBlock (ebp, newic, ip);
133 newic->lineno = lineno;
140 if (IS_REGPARM (func->args->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->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->etype))
211 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
214 newic = newiCode ('=', NULL, IC_RIGHT (ic));
215 IC_RESULT (newic) = operandFromValue (func->args);
217 addiCodeToeBBlock (ebp, newic, ip);
218 newic->lineno = linenno;
224 if (IS_REGPARM (func->args->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->etype))
280 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
283 newic = newiCode ('=', NULL, IC_RIGHT (ic));
284 IC_RESULT (newic) = operandFromValue (func->args);
286 addiCodeToeBBlock (ebp, newic, ip);
287 newic->lineno = lineno;
294 if (IS_REGPARM (func->args->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->etype))
364 newic = newiCode (SEND, IC_LEFT (ic), NULL);
367 newic = newiCode ('=', NULL, IC_LEFT (ic));
368 IC_RESULT (newic) = operandFromValue (func->args);
370 addiCodeToeBBlock (ebp, newic, ip);
371 newic->lineno = lineno;
374 if (IS_REGPARM (func->args->next->etype))
375 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
378 newic = newiCode ('=', NULL, IC_RIGHT (ic));
379 IC_RESULT (newic) = operandFromValue (func->args->next);
381 addiCodeToeBBlock (ebp, newic, ip);
382 newic->lineno = lineno;
387 /* compiled as reentrant then push */
389 if (IS_REGPARM (func->args->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->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 *type = operandType (IC_LEFT (ic));
468 if (IS_INTEGRAL (type) && getSize (type) > port->support.muldiv)
470 convilong (ic, ebbs[i], type, ic->op);
474 if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
476 sym_link *type = operandType (IC_LEFT (ic));
478 if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
480 convilong (ic, ebbs[i], type, ic->op);
487 /*-----------------------------------------------------------------*/
488 /* replaceRegEqv - replace all local variables with their reqv */
489 /*-----------------------------------------------------------------*/
491 replaceRegEqv (eBBlock ** ebbs, int count)
495 for (i = 0; i < count; i++)
500 for (ic = ebbs[i]->sch; ic; ic = ic->next)
509 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
510 OP_REQV (IC_COND (ic)))
511 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
512 OP_SYMBOL (IC_COND (ic))->defs,
513 OP_SYMBOL (IC_COND (ic))->uses);
518 if (ic->op == JUMPTABLE)
520 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
521 OP_REQV (IC_JTCOND (ic)))
522 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
523 OP_SYMBOL (IC_JTCOND (ic))->defs,
524 OP_SYMBOL (IC_JTCOND (ic))->uses);
528 if (ic->op == RECEIVE)
530 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
531 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
535 if (IC_RESULT (ic) &&
536 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
537 OP_REQV (IC_RESULT (ic)))
539 if (POINTER_SET (ic))
541 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
542 OP_SYMBOL (IC_RESULT (ic))->defs,
543 OP_SYMBOL (IC_RESULT (ic))->uses);
544 IC_RESULT (ic)->isaddr = 1;
547 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
548 OP_SYMBOL (IC_RESULT (ic))->defs,
549 OP_SYMBOL (IC_RESULT (ic))->uses);
553 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
554 OP_REQV (IC_RIGHT (ic)))
556 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
557 OP_SYMBOL (IC_RIGHT (ic))->defs,
558 OP_SYMBOL (IC_RIGHT (ic))->uses);
559 IC_RIGHT (ic)->isaddr = 0;
563 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
564 OP_REQV (IC_LEFT (ic)))
566 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
567 OP_SYMBOL (IC_LEFT (ic))->defs,
568 OP_SYMBOL (IC_LEFT (ic))->uses);
569 IC_LEFT (ic)->isaddr = 0;
575 /*-----------------------------------------------------------------*/
576 /* killDeadCode - eliminates dead assignments */
577 /*-----------------------------------------------------------------*/
579 killDeadCode (eBBlock ** ebbs, int count)
586 /* basic algorithm :- */
587 /* first the exclusion rules :- */
588 /* 1. if result is a global or volatile then skip */
589 /* 2. if assignment and result is a temp & isaddr then skip */
590 /* since this means array & pointer access, will be taken */
591 /* care of by alias analysis. */
592 /* 3. if the result is used in the remainder of the block skip */
593 /* 4. if this definition does not reach the end of the block */
594 /* i.e. the result is not present in the outExprs then KILL */
595 /* 5. if it reaches the end of block & is used by some success */
598 /* this whole process is carried on iteratively till no change */
603 /* for all blocks do */
604 for (i = 0; i < count; i++)
608 /* for all instructions in the block do */
609 for (ic = ebbs[i]->sch; ic; ic = ic->next)
619 /* if the result is volatile then continue */
620 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
623 /* if the result is a temp & isaddr then skip */
624 if (IC_RESULT (ic) && POINTER_SET (ic))
627 /* if the result is used in the remainder of the */
628 /* block then skip */
629 if (usedInRemaining (IC_RESULT (ic), ic->next))
632 /* does this definition reach the end of the block
633 or the usage is zero then we can kill */
634 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
635 kill = 1; /* if not we can kill it */
638 /* if this is a global variable or function parameter */
639 /* we cannot kill anyway */
640 if (isOperandGlobal (IC_RESULT (ic)) ||
641 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
642 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
645 /* if we are sure there are no usages */
646 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
652 /* reset visited flag */
653 for (j = 0; j < count; ebbs[j++]->visited = 0);
655 /* find out if this definition is alive */
656 if (applyToSet (ebbs[i]->succList,
665 /* kill this one if required */
671 remiCodeFromeBBlock (ebbs[i], ic);
673 /* now delete from defUseSet */
674 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
675 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
677 /* and defset of the block */
678 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
680 /* for the left & right remove the usage */
681 if (IS_SYMOP (IC_LEFT (ic)))
682 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
684 if (IS_SYMOP (IC_RIGHT (ic)))
685 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
688 } /* end of all instructions */
690 if (!ebbs[i]->sch && !ebbs[i]->noPath)
691 disconBBlock (ebbs[i], ebbs, count);
693 } /* end of for all blocks */
697 } /* end of while(1) */
702 /*-----------------------------------------------------------------*/
703 /* printCyclomatic - prints the cyclomatic information */
704 /*-----------------------------------------------------------------*/
706 printCyclomatic (eBBlock ** ebbs, int count)
708 int nEdges = elementsInSet (graphEdges);
711 for (i = 0; i < count; i++)
712 nNodes += (!ebbs[i]->noPath);
714 /* print the information */
715 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
718 /*-----------------------------------------------------------------*/
719 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
720 /* refer to dead variables. */
721 /*-----------------------------------------------------------------*/
723 discardDeadParamReceives (eBBlock ** ebbs, int count)
729 for (i = 0; i < count; i++)
731 for (ic = ebbs[i]->sch; ic; ic = ic->next)
733 if (ic->op == RECEIVE)
735 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
736 && !OP_SYMBOL (IC_RESULT (ic))->used)
739 fprintf (stderr, "discarding dead receive for %s\n",
740 OP_SYMBOL (IC_RESULT (ic))->name);
742 dummyIcode.next = ic->next;
743 remiCodeFromeBBlock (ebbs[i], ic);
751 /*-----------------------------------------------------------------*/
752 /* eBBlockFromiCode - creates extended basic blocks from iCode */
753 /* will return an array of eBBlock pointers */
754 /*-----------------------------------------------------------------*/
756 eBBlockFromiCode (iCode * ic)
758 eBBlock **ebbs = NULL;
766 /* if nothing passed then return nothing */
773 /* optimize the chain for labels & gotos
774 this will eliminate redundant labels and
775 will change jump to jumps by jumps */
776 ic = iCodeLabelOptimize (ic);
778 /* break it down into basic blocks */
779 ebbs = iCodeBreakDown (ic, &count);
782 /* compute the control flow */
783 computeControlFlow (ebbs, count, 0);
785 /* dumpraw if asked for */
786 if (options.dump_raw)
787 dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
789 /* replace the local variables with their
790 register equivalents : the liveRange computation
791 along with the register allocation will determine
792 if it finally stays in the registers */
793 replaceRegEqv (ebbs, count);
795 /* create loop regions */
796 loops = createLoopRegions (ebbs, count);
798 /* dumpraw if asked for */
799 if (options.dump_raw)
800 dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
802 /* do common subexpression elimination for each block */
803 change = cseAllBlocks (ebbs, saveCount);
805 /* dumpraw if asked for */
806 if (options.dump_raw)
807 dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
809 /* compute the data flow */
810 computeDataFlow (ebbs, saveCount);
812 /* dumpraw if asked for */
813 if (options.dump_raw)
814 dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
816 /* global common subexpression elimination */
817 if (optimize.global_cse)
819 change += cseAllBlocks (ebbs, saveCount);
820 if (options.dump_gcse)
821 dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
824 kchange = killDeadCode (ebbs, saveCount);
826 if (options.dump_kill)
827 dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
829 /* do loop optimizations */
830 change += (lchange = loopOptimizations (loops, ebbs, count));
831 if (options.dump_loop)
832 dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
834 /* recompute the data flow and apply global cse again
835 if loops optimizations or dead code caused a change:
836 loops will brings out of the loop which then may be
837 available for use in the later blocks: dead code
838 elimination could potentially disconnect some blocks
839 conditional flow may be efected so we need to apply
840 subexpression once more */
841 if (lchange || kchange)
843 computeDataFlow (ebbs, saveCount);
844 change += cseAllBlocks (ebbs, saveCount);
845 if (options.dump_loop)
846 dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
848 /* if loop optimizations caused a change then do
849 dead code elimination once more : this will
850 get rid of the extra assignments to the induction
851 variables created during loop optimizations */
852 killDeadCode (ebbs, saveCount);
854 if (options.dump_loop)
855 dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
859 /* sort it back by block number */
860 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
862 /* if cyclomatic info requested then print it */
863 if (options.cyclomatic)
864 printCyclomatic (ebbs, saveCount);
867 /* convert operations with support routines
868 written in C to function calls : Iam doing
869 this at this point since I want all the
870 operations to be as they are for optimzations */
871 convertToFcall (ebbs, count);
874 /* compute the live ranges */
875 computeLiveRanges (ebbs, count);
877 if (options.dump_range)
878 dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
880 /* Now that we have the live ranges, discard parameter
881 * receives for unused parameters.
883 discardDeadParamReceives (ebbs, count);
885 /* allocate registers & generate code */
886 port->assignRegisters (ebbs, count);
888 /* throw away blocks */
889 setToNull ((void **) &graphEdges);
897 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */