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;
62 ip = ic->next; /* insertion point */
63 /* remove it from the iCode */
64 remiCodeFromeBBlock (ebp, ic);
67 right = IC_RIGHT (ic);
103 /* if float support routines NOT compiled as reentrant */
104 if (!options.float_rent)
108 if (IS_REGPARM (func->args->etype))
110 newic = newiCode (SEND, IC_LEFT (ic), NULL);
114 newic = newiCode ('=', NULL, IC_LEFT (ic));
115 IC_RESULT (newic) = operandFromValue (func->args);
118 addiCodeToeBBlock (ebp, newic, ip);
119 newic->lineno = lineno;
122 if (IS_REGPARM (func->args->next->etype))
124 newic = newiCode (SEND, IC_LEFT (ic), NULL);
128 newic = newiCode ('=', NULL, IC_RIGHT (ic));
129 IC_RESULT (newic) = operandFromValue (func->args->next);
131 addiCodeToeBBlock (ebp, newic, ip);
132 newic->lineno = lineno;
139 if (IS_REGPARM (func->args->next->etype))
141 newic = newiCode (SEND, right, NULL);
145 newic = newiCode (IPUSH, right, NULL);
149 addiCodeToeBBlock (ebp, newic, ip);
150 newic->lineno = lineno;
152 /* insert push left */
153 if (IS_REGPARM (func->args->etype))
155 newic = newiCode (SEND, left, NULL);
159 newic = newiCode (IPUSH, left, NULL);
162 addiCodeToeBBlock (ebp, newic, ip);
163 newic->lineno = lineno;
165 /* insert the call */
166 newic = newiCode (CALL, operandFromSymbol (func), NULL);
167 IC_RESULT (newic) = IC_RESULT (ic);
168 addiCodeToeBBlock (ebp, newic, ip);
169 newic->lineno = lineno;
172 /*-----------------------------------------------------------------*/
173 /* cnvToFloatCast - converts casts to floats to function calls */
174 /*-----------------------------------------------------------------*/
176 cnvToFloatCast (iCode * ic, eBBlock * ebp)
180 sym_link *type = operandType (IC_RIGHT (ic));
181 int linenno = ic->lineno;
185 /* remove it from the iCode */
186 remiCodeFromeBBlock (ebp, ic);
187 /* depending on the type */
188 for (bwd = 0; bwd < 3; bwd++)
190 for (su = 0; su < 2; su++)
192 if (checkType (type, __multypes[bwd][su]) == 1)
194 func = __conv[0][bwd][su];
202 /* if float support routines NOT compiled as reentrant */
203 if (!options.float_rent)
206 if (IS_REGPARM (func->args->etype))
207 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
210 newic = newiCode ('=', NULL, IC_RIGHT (ic));
211 IC_RESULT (newic) = operandFromValue (func->args);
213 addiCodeToeBBlock (ebp, newic, ip);
214 newic->lineno = linenno;
220 if (IS_REGPARM (func->args->etype))
221 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
224 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
227 addiCodeToeBBlock (ebp, newic, ip);
228 newic->lineno = linenno;
233 newic = newiCode (CALL, operandFromSymbol (func), NULL);
234 IC_RESULT (newic) = IC_RESULT (ic);
235 addiCodeToeBBlock (ebp, newic, ip);
236 newic->lineno = linenno;
240 /*-----------------------------------------------------------------*/
241 /* cnvFromFloatCast - converts casts From floats to function calls */
242 /*-----------------------------------------------------------------*/
244 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
248 sym_link *type = operandType (IC_LEFT (ic));
249 int lineno = ic->lineno;
253 /* remove it from the iCode */
254 remiCodeFromeBBlock (ebp, ic);
256 /* depending on the type */
257 for (bwd = 0; bwd < 3; bwd++)
259 for (su = 0; su < 2; su++)
261 if (checkType (type, __multypes[bwd][su]) == 1)
263 func = __conv[1][bwd][su];
271 /* if float support routines NOT compiled as reentrant */
272 if (!options.float_rent)
275 if (IS_REGPARM (func->args->etype))
276 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
279 newic = newiCode ('=', NULL, IC_RIGHT (ic));
280 IC_RESULT (newic) = operandFromValue (func->args);
282 addiCodeToeBBlock (ebp, newic, ip);
283 newic->lineno = lineno;
290 if (IS_REGPARM (func->args->etype))
291 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
294 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
297 addiCodeToeBBlock (ebp, newic, ip);
298 newic->lineno = lineno;
303 newic = newiCode (CALL, operandFromSymbol (func), NULL);
304 IC_RESULT (newic) = IC_RESULT (ic);
305 addiCodeToeBBlock (ebp, newic, ip);
306 newic->lineno = lineno;
310 /*-----------------------------------------------------------------*/
311 /* convilong - converts int or long mults or divs to fcalls */
312 /*-----------------------------------------------------------------*/
314 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
317 iCode *ip = ic->next;
319 int lineno = ic->lineno;
322 remiCodeFromeBBlock (ebp, ic);
324 /* depending on the type */
325 for (bwd = 0; bwd < 3; bwd++)
327 for (su = 0; su < 2; su++)
329 if (checkType (type, __multypes[bwd][su]) == 1)
332 func = __muldiv[0][bwd][su];
334 func = __muldiv[1][bwd][su];
336 func = __muldiv[2][bwd][su];
345 /* if int & long support routines NOT compiled as reentrant */
346 if (!options.intlong_rent)
349 if (IS_REGPARM (func->args->etype))
350 newic = newiCode (SEND, IC_LEFT (ic), NULL);
353 newic = newiCode ('=', NULL, IC_LEFT (ic));
354 IC_RESULT (newic) = operandFromValue (func->args);
356 addiCodeToeBBlock (ebp, newic, ip);
357 newic->lineno = lineno;
360 if (IS_REGPARM (func->args->next->etype))
361 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
364 newic = newiCode ('=', NULL, IC_RIGHT (ic));
365 IC_RESULT (newic) = operandFromValue (func->args->next);
367 addiCodeToeBBlock (ebp, newic, ip);
368 newic->lineno = lineno;
375 /* compiled as reentrant then push */
377 if (IS_REGPARM (func->args->next->etype))
378 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
381 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
384 addiCodeToeBBlock (ebp, newic, ip);
385 newic->lineno = lineno;
387 /* insert push left */
388 if (IS_REGPARM (func->args->etype))
389 newic = newiCode (SEND, IC_LEFT (ic), NULL);
392 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
395 addiCodeToeBBlock (ebp, newic, ip);
396 newic->lineno = lineno;
401 newic = newiCode (CALL, operandFromSymbol (func), NULL);
402 IC_RESULT (newic) = IC_RESULT (ic);
403 addiCodeToeBBlock (ebp, newic, ip);
404 newic->lineno = lineno;
408 /*-----------------------------------------------------------------*/
409 /* convertToFcall - converts some operations to fcalls */
410 /*-----------------------------------------------------------------*/
412 convertToFcall (eBBlock ** ebbs, int count)
416 /* for all blocks do */
417 for (i = 0; i < count; i++)
421 /* for all instructions in the block do */
422 for (ic = ebbs[i]->sch; ic; ic = ic->next)
425 /* floating point operations are
426 converted to function calls */
427 if ((IS_CONDITIONAL (ic) ||
428 IS_ARITHMETIC_OP (ic)) &&
429 (IS_FLOAT (operandType (IC_RIGHT (ic)))))
432 cnvToFcall (ic, ebbs[i]);
435 /* casting is a little different */
438 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
439 cnvFromFloatCast (ic, ebbs[i]);
440 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
441 cnvToFloatCast (ic, ebbs[i]);
444 /* if long / int mult or divide or mod */
445 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
448 sym_link *type = operandType (IC_LEFT (ic));
449 if (IS_INTEGRAL (type) && getSize (type) > port->muldiv.native_below)
450 convilong (ic, ebbs[i], type, ic->op);
456 /*-----------------------------------------------------------------*/
457 /* replaceRegEqv - replace all local variables with their reqv */
458 /*-----------------------------------------------------------------*/
460 replaceRegEqv (eBBlock ** ebbs, int count)
464 for (i = 0; i < count; i++)
469 for (ic = ebbs[i]->sch; ic; ic = ic->next)
478 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
479 OP_REQV (IC_COND (ic)))
480 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
481 OP_SYMBOL (IC_COND (ic))->defs,
482 OP_SYMBOL (IC_COND (ic))->uses);
487 if (ic->op == JUMPTABLE)
489 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
490 OP_REQV (IC_JTCOND (ic)))
491 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
492 OP_SYMBOL (IC_JTCOND (ic))->defs,
493 OP_SYMBOL (IC_JTCOND (ic))->uses);
497 if (ic->op == RECEIVE)
499 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
500 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
504 if (IC_RESULT (ic) &&
505 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
506 OP_REQV (IC_RESULT (ic)))
508 if (POINTER_SET (ic))
510 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
511 OP_SYMBOL (IC_RESULT (ic))->defs,
512 OP_SYMBOL (IC_RESULT (ic))->uses);
513 IC_RESULT (ic)->isaddr = 1;
516 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
517 OP_SYMBOL (IC_RESULT (ic))->defs,
518 OP_SYMBOL (IC_RESULT (ic))->uses);
522 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
523 OP_REQV (IC_RIGHT (ic)))
525 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
526 OP_SYMBOL (IC_RIGHT (ic))->defs,
527 OP_SYMBOL (IC_RIGHT (ic))->uses);
528 IC_RIGHT (ic)->isaddr = 0;
532 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
533 OP_REQV (IC_LEFT (ic)))
535 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
536 OP_SYMBOL (IC_LEFT (ic))->defs,
537 OP_SYMBOL (IC_LEFT (ic))->uses);
538 IC_LEFT (ic)->isaddr = 0;
544 /*-----------------------------------------------------------------*/
545 /* killDeadCode - eliminates dead assignments */
546 /*-----------------------------------------------------------------*/
548 killDeadCode (eBBlock ** ebbs, int count)
555 /* basic algorithm :- */
556 /* first the exclusion rules :- */
557 /* 1. if result is a global or volatile then skip */
558 /* 2. if assignment and result is a temp & isaddr then skip */
559 /* since this means array & pointer access, will be taken */
560 /* care of by alias analysis. */
561 /* 3. if the result is used in the remainder of the block skip */
562 /* 4. if this definition does not reach the end of the block */
563 /* i.e. the result is not present in the outExprs then KILL */
564 /* 5. if it reaches the end of block & is used by some success */
567 /* this whole process is carried on iteratively till no change */
572 /* for all blocks do */
573 for (i = 0; i < count; i++)
577 /* for all instructions in the block do */
578 for (ic = ebbs[i]->sch; ic; ic = ic->next)
588 /* if the result is volatile then continue */
589 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
592 /* if the result is a temp & isaddr then skip */
593 if (IC_RESULT (ic) && POINTER_SET (ic))
596 /* if the result is used in the remainder of the */
597 /* block then skip */
598 if (usedInRemaining (IC_RESULT (ic), ic->next))
601 /* does this definition reach the end of the block
602 or the usage is zero then we can kill */
603 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
604 kill = 1; /* if not we can kill it */
607 /* if this is a global variable or function parameter */
608 /* we cannot kill anyway */
609 if (isOperandGlobal (IC_RESULT (ic)) ||
610 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
611 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
614 /* if we are sure there are no usages */
615 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
621 /* reset visited flag */
622 for (j = 0; j < count; ebbs[j++]->visited = 0);
624 /* find out if this definition is alive */
625 if (applyToSet (ebbs[i]->succList,
634 /* kill this one if required */
640 remiCodeFromeBBlock (ebbs[i], ic);
642 /* now delete from defUseSet */
643 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
644 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
646 /* and defset of the block */
647 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
649 /* for the left & right remove the usage */
650 if (IS_SYMOP (IC_LEFT (ic)))
651 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
653 if (IS_SYMOP (IC_RIGHT (ic)))
654 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
657 } /* end of all instructions */
659 if (!ebbs[i]->sch && !ebbs[i]->noPath)
660 disconBBlock (ebbs[i], ebbs, count);
662 } /* end of for all blocks */
666 } /* end of while(1) */
671 /*-----------------------------------------------------------------*/
672 /* printCyclomatic - prints the cyclomatic information */
673 /*-----------------------------------------------------------------*/
675 printCyclomatic (eBBlock ** ebbs, int count)
677 int nEdges = elementsInSet (graphEdges);
680 for (i = 0; i < count; i++)
681 nNodes += (!ebbs[i]->noPath);
683 /* print the information */
684 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
687 /*-----------------------------------------------------------------*/
688 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
689 /* refer to dead variables. */
690 /*-----------------------------------------------------------------*/
692 discardDeadParamReceives (eBBlock ** ebbs, int count)
698 for (i = 0; i < count; i++)
700 for (ic = ebbs[i]->sch; ic; ic = ic->next)
702 if (ic->op == RECEIVE)
704 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
705 && !OP_SYMBOL (IC_RESULT (ic))->used)
708 fprintf (stderr, "discarding dead receive for %s\n",
709 OP_SYMBOL (IC_RESULT (ic))->name);
711 dummyIcode.next = ic->next;
712 remiCodeFromeBBlock (ebbs[i], ic);
720 /*-----------------------------------------------------------------*/
721 /* eBBlockFromiCode - creates extended basic blocks from iCode */
722 /* will return an array of eBBlock pointers */
723 /*-----------------------------------------------------------------*/
725 eBBlockFromiCode (iCode * ic)
727 eBBlock **ebbs = NULL;
735 /* if nothing passed then return nothing */
742 /* optimize the chain for labels & gotos
743 this will eliminate redundant labels and
744 will change jump to jumps by jumps */
745 ic = iCodeLabelOptimize (ic);
747 /* break it down into basic blocks */
748 ebbs = iCodeBreakDown (ic, &count);
751 /* compute the control flow */
752 computeControlFlow (ebbs, count, 0);
754 /* dumpraw if asked for */
755 if (options.dump_raw)
756 dumpEbbsToFileExt (".dumpraw0", ebbs, count);
758 /* replace the local variables with their
759 register equivalents : the liveRange computation
760 along with the register allocation will determine
761 if it finally stays in the registers */
762 replaceRegEqv (ebbs, count);
764 /* create loop regions */
765 loops = createLoopRegions (ebbs, count);
767 /* dumpraw if asked for */
768 if (options.dump_raw)
769 dumpEbbsToFileExt (".dumpraw1", ebbs, count);
771 /* do common subexpression elimination for each block */
772 change = cseAllBlocks (ebbs, saveCount);
774 /* dumpraw if asked for */
775 if (options.dump_raw)
776 dumpEbbsToFileExt (".dumpcse", ebbs, count);
778 /* compute the data flow */
779 computeDataFlow (ebbs, saveCount);
781 /* dumpraw if asked for */
782 if (options.dump_raw)
783 dumpEbbsToFileExt (".dumpdflow", ebbs, count);
785 /* global common subexpression elimination */
786 if (optimize.global_cse)
788 change += cseAllBlocks (ebbs, saveCount);
789 if (options.dump_gcse)
790 dumpEbbsToFileExt (".dumpgcse", ebbs, saveCount);
793 kchange = killDeadCode (ebbs, saveCount);
795 if (options.dump_kill)
796 dumpEbbsToFileExt (".dumpdeadcode", ebbs, count);
798 /* do loop optimizations */
799 change += (lchange = loopOptimizations (loops, ebbs, count));
800 if (options.dump_loop)
801 dumpEbbsToFileExt (".dumploop", ebbs, count);
803 /* recompute the data flow and apply global cse again
804 if loops optimizations or dead code caused a change:
805 loops will brings out of the loop which then may be
806 available for use in the later blocks: dead code
807 elimination could potentially disconnect some blocks
808 conditional flow may be efected so we need to apply
809 subexpression once more */
810 if (lchange || kchange)
813 computeDataFlow (ebbs, saveCount);
814 change += cseAllBlocks (ebbs, saveCount);
815 if (options.dump_loop)
816 dumpEbbsToFileExt (".dumploopg", ebbs, count);
818 /* if loop optimizations caused a change then do
819 dead code elimination once more : this will
820 get rid of the extra assignments to the induction
821 variables created during loop optimizations */
822 killDeadCode (ebbs, saveCount);
824 if (options.dump_loop)
825 dumpEbbsToFileExt (".dumploopd", ebbs, count);
830 /* sort it back by block number */
831 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
833 /* if cyclomatic info requested then print it */
834 if (options.cyclomatic)
835 printCyclomatic (ebbs, saveCount);
838 /* convert operations with support routines
839 written in C to function calls : Iam doing
840 this at this point since I want all the
841 operations to be as they are for optimzations */
842 convertToFcall (ebbs, count);
845 /* compute the live ranges */
846 computeLiveRanges (ebbs, count);
848 if (options.dump_range)
849 dumpEbbsToFileExt (".dumprange", ebbs, count);
851 /* Now that we have the live ranges, discard parameter
852 * receives for unused parameters.
854 discardDeadParamReceives (ebbs, count);
856 /* allocate registers & generate code */
857 port->assignRegisters (ebbs, count);
859 /* throw away blocks */
860 setToNull ((void **) &graphEdges);
868 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */