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 (checkType (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 (checkType (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 (checkType (type, __multypes[bwd][su]) == 1)
338 func = __muldiv[0][bwd][su];
340 func = __muldiv[1][bwd][su];
342 func = __muldiv[2][bwd][su];
351 /* if int & long support routines NOT compiled as reentrant */
352 if (!options.intlong_rent)
355 if (IS_REGPARM (func->args->etype))
356 newic = newiCode (SEND, IC_LEFT (ic), NULL);
359 newic = newiCode ('=', NULL, IC_LEFT (ic));
360 IC_RESULT (newic) = operandFromValue (func->args);
362 addiCodeToeBBlock (ebp, newic, ip);
363 newic->lineno = lineno;
366 if (IS_REGPARM (func->args->next->etype))
367 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
370 newic = newiCode ('=', NULL, IC_RIGHT (ic));
371 IC_RESULT (newic) = operandFromValue (func->args->next);
373 addiCodeToeBBlock (ebp, newic, ip);
374 newic->lineno = lineno;
381 /* compiled as reentrant then push */
383 if (IS_REGPARM (func->args->next->etype))
384 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
387 newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
389 bytesPushed=getSize(type);
391 addiCodeToeBBlock (ebp, newic, ip);
392 newic->lineno = lineno;
394 /* insert push left */
395 if (IS_REGPARM (func->args->etype))
396 newic = newiCode (SEND, IC_LEFT (ic), NULL);
399 newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
401 bytesPushed=getSize(type);
403 addiCodeToeBBlock (ebp, newic, ip);
404 newic->lineno = lineno;
409 newic = newiCode (CALL, operandFromSymbol (func), NULL);
410 IC_RESULT (newic) = IC_RESULT (ic);
411 newic->lineno = lineno;
412 newic->parmBytes+=bytesPushed; // to clear the stack after the call
413 addiCodeToeBBlock (ebp, newic, ip);
416 /*-----------------------------------------------------------------*/
417 /* convertToFcall - converts some operations to fcalls */
418 /*-----------------------------------------------------------------*/
420 convertToFcall (eBBlock ** ebbs, int count)
424 /* for all blocks do */
425 for (i = 0; i < count; i++)
429 /* for all instructions in the block do */
430 for (ic = ebbs[i]->sch; ic; ic = ic->next)
433 /* floating point operations are
434 converted to function calls */
435 if ((IS_CONDITIONAL (ic) ||
436 IS_ARITHMETIC_OP (ic)) &&
437 (IS_FLOAT (operandType (IC_RIGHT (ic)))))
440 cnvToFcall (ic, ebbs[i]);
443 /* casting is a little different */
446 if (IS_FLOAT (operandType (IC_RIGHT (ic))))
447 cnvFromFloatCast (ic, ebbs[i]);
448 else if (IS_FLOAT (operandType (IC_LEFT (ic))))
449 cnvToFloatCast (ic, ebbs[i]);
452 /* if long / int mult or divide or mod */
453 if (ic->op == '*' || ic->op == '/' || ic->op == '%')
456 sym_link *type = operandType (IC_LEFT (ic));
457 if (IS_INTEGRAL (type) && getSize (type) > port->muldiv.native_below)
458 convilong (ic, ebbs[i], type, ic->op);
464 /*-----------------------------------------------------------------*/
465 /* replaceRegEqv - replace all local variables with their reqv */
466 /*-----------------------------------------------------------------*/
468 replaceRegEqv (eBBlock ** ebbs, int count)
472 for (i = 0; i < count; i++)
477 for (ic = ebbs[i]->sch; ic; ic = ic->next)
486 if (IS_TRUE_SYMOP (IC_COND (ic)) &&
487 OP_REQV (IC_COND (ic)))
488 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
489 OP_SYMBOL (IC_COND (ic))->defs,
490 OP_SYMBOL (IC_COND (ic))->uses);
495 if (ic->op == JUMPTABLE)
497 if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
498 OP_REQV (IC_JTCOND (ic)))
499 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
500 OP_SYMBOL (IC_JTCOND (ic))->defs,
501 OP_SYMBOL (IC_JTCOND (ic))->uses);
505 if (ic->op == RECEIVE)
507 if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
508 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
512 if (IC_RESULT (ic) &&
513 IS_TRUE_SYMOP (IC_RESULT (ic)) &&
514 OP_REQV (IC_RESULT (ic)))
516 if (POINTER_SET (ic))
518 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
519 OP_SYMBOL (IC_RESULT (ic))->defs,
520 OP_SYMBOL (IC_RESULT (ic))->uses);
521 IC_RESULT (ic)->isaddr = 1;
524 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
525 OP_SYMBOL (IC_RESULT (ic))->defs,
526 OP_SYMBOL (IC_RESULT (ic))->uses);
530 IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
531 OP_REQV (IC_RIGHT (ic)))
533 IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
534 OP_SYMBOL (IC_RIGHT (ic))->defs,
535 OP_SYMBOL (IC_RIGHT (ic))->uses);
536 IC_RIGHT (ic)->isaddr = 0;
540 IS_TRUE_SYMOP (IC_LEFT (ic)) &&
541 OP_REQV (IC_LEFT (ic)))
543 IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
544 OP_SYMBOL (IC_LEFT (ic))->defs,
545 OP_SYMBOL (IC_LEFT (ic))->uses);
546 IC_LEFT (ic)->isaddr = 0;
552 /*-----------------------------------------------------------------*/
553 /* killDeadCode - eliminates dead assignments */
554 /*-----------------------------------------------------------------*/
556 killDeadCode (eBBlock ** ebbs, int count)
563 /* basic algorithm :- */
564 /* first the exclusion rules :- */
565 /* 1. if result is a global or volatile then skip */
566 /* 2. if assignment and result is a temp & isaddr then skip */
567 /* since this means array & pointer access, will be taken */
568 /* care of by alias analysis. */
569 /* 3. if the result is used in the remainder of the block skip */
570 /* 4. if this definition does not reach the end of the block */
571 /* i.e. the result is not present in the outExprs then KILL */
572 /* 5. if it reaches the end of block & is used by some success */
575 /* this whole process is carried on iteratively till no change */
580 /* for all blocks do */
581 for (i = 0; i < count; i++)
585 /* for all instructions in the block do */
586 for (ic = ebbs[i]->sch; ic; ic = ic->next)
596 /* if the result is volatile then continue */
597 if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
600 /* if the result is a temp & isaddr then skip */
601 if (IC_RESULT (ic) && POINTER_SET (ic))
604 /* if the result is used in the remainder of the */
605 /* block then skip */
606 if (usedInRemaining (IC_RESULT (ic), ic->next))
609 /* does this definition reach the end of the block
610 or the usage is zero then we can kill */
611 if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
612 kill = 1; /* if not we can kill it */
615 /* if this is a global variable or function parameter */
616 /* we cannot kill anyway */
617 if (isOperandGlobal (IC_RESULT (ic)) ||
618 (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
619 !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
622 /* if we are sure there are no usages */
623 if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
629 /* reset visited flag */
630 for (j = 0; j < count; ebbs[j++]->visited = 0);
632 /* find out if this definition is alive */
633 if (applyToSet (ebbs[i]->succList,
642 /* kill this one if required */
648 remiCodeFromeBBlock (ebbs[i], ic);
650 /* now delete from defUseSet */
651 deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
652 bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
654 /* and defset of the block */
655 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
657 /* for the left & right remove the usage */
658 if (IS_SYMOP (IC_LEFT (ic)))
659 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
661 if (IS_SYMOP (IC_RIGHT (ic)))
662 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
665 } /* end of all instructions */
667 if (!ebbs[i]->sch && !ebbs[i]->noPath)
668 disconBBlock (ebbs[i], ebbs, count);
670 } /* end of for all blocks */
674 } /* end of while(1) */
679 /*-----------------------------------------------------------------*/
680 /* printCyclomatic - prints the cyclomatic information */
681 /*-----------------------------------------------------------------*/
683 printCyclomatic (eBBlock ** ebbs, int count)
685 int nEdges = elementsInSet (graphEdges);
688 for (i = 0; i < count; i++)
689 nNodes += (!ebbs[i]->noPath);
691 /* print the information */
692 werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
695 /*-----------------------------------------------------------------*/
696 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
697 /* refer to dead variables. */
698 /*-----------------------------------------------------------------*/
700 discardDeadParamReceives (eBBlock ** ebbs, int count)
706 for (i = 0; i < count; i++)
708 for (ic = ebbs[i]->sch; ic; ic = ic->next)
710 if (ic->op == RECEIVE)
712 if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
713 && !OP_SYMBOL (IC_RESULT (ic))->used)
716 fprintf (stderr, "discarding dead receive for %s\n",
717 OP_SYMBOL (IC_RESULT (ic))->name);
719 dummyIcode.next = ic->next;
720 remiCodeFromeBBlock (ebbs[i], ic);
728 /*-----------------------------------------------------------------*/
729 /* eBBlockFromiCode - creates extended basic blocks from iCode */
730 /* will return an array of eBBlock pointers */
731 /*-----------------------------------------------------------------*/
733 eBBlockFromiCode (iCode * ic)
735 eBBlock **ebbs = NULL;
743 /* if nothing passed then return nothing */
750 /* optimize the chain for labels & gotos
751 this will eliminate redundant labels and
752 will change jump to jumps by jumps */
753 ic = iCodeLabelOptimize (ic);
755 /* break it down into basic blocks */
756 ebbs = iCodeBreakDown (ic, &count);
759 /* compute the control flow */
760 computeControlFlow (ebbs, count, 0);
762 /* dumpraw if asked for */
763 if (options.dump_raw)
764 dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
766 /* replace the local variables with their
767 register equivalents : the liveRange computation
768 along with the register allocation will determine
769 if it finally stays in the registers */
770 replaceRegEqv (ebbs, count);
772 /* create loop regions */
773 loops = createLoopRegions (ebbs, count);
775 /* dumpraw if asked for */
776 if (options.dump_raw)
777 dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
779 /* do common subexpression elimination for each block */
780 change = cseAllBlocks (ebbs, saveCount);
782 /* dumpraw if asked for */
783 if (options.dump_raw)
784 dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
786 /* compute the data flow */
787 computeDataFlow (ebbs, saveCount);
789 /* dumpraw if asked for */
790 if (options.dump_raw)
791 dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
793 /* global common subexpression elimination */
794 if (optimize.global_cse)
796 change += cseAllBlocks (ebbs, saveCount);
797 if (options.dump_gcse)
798 dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
801 kchange = killDeadCode (ebbs, saveCount);
803 if (options.dump_kill)
804 dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
806 /* do loop optimizations */
807 change += (lchange = loopOptimizations (loops, ebbs, count));
808 if (options.dump_loop)
809 dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
811 /* recompute the data flow and apply global cse again
812 if loops optimizations or dead code caused a change:
813 loops will brings out of the loop which then may be
814 available for use in the later blocks: dead code
815 elimination could potentially disconnect some blocks
816 conditional flow may be efected so we need to apply
817 subexpression once more */
818 if (lchange || kchange)
821 computeDataFlow (ebbs, saveCount);
822 change += cseAllBlocks (ebbs, saveCount);
823 if (options.dump_loop)
824 dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
826 /* if loop optimizations caused a change then do
827 dead code elimination once more : this will
828 get rid of the extra assignments to the induction
829 variables created during loop optimizations */
830 killDeadCode (ebbs, saveCount);
832 if (options.dump_loop)
833 dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
838 /* sort it back by block number */
839 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
841 /* if cyclomatic info requested then print it */
842 if (options.cyclomatic)
843 printCyclomatic (ebbs, saveCount);
846 /* convert operations with support routines
847 written in C to function calls : Iam doing
848 this at this point since I want all the
849 operations to be as they are for optimzations */
850 convertToFcall (ebbs, count);
853 /* compute the live ranges */
854 computeLiveRanges (ebbs, count);
856 if (options.dump_range)
857 dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
859 /* Now that we have the live ranges, discard parameter
860 * receives for unused parameters.
862 discardDeadParamReceives (ebbs, count);
864 /* allocate registers & generate code */
865 port->assignRegisters (ebbs, count);
867 /* throw away blocks */
868 setToNull ((void **) &graphEdges);
876 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */