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 -------------------------------------------------------------------------*/
30 #include "SDCCglobl.h"
34 #include "SDCChasht.h"
37 #include "SDCCicode.h"
38 #include "SDCClabel.h"
39 #include "SDCCBBlock.h"
42 #include "SDCCcflow.h"
43 #include "SDCCdflow.h"
44 #include "SDCClrange.h"
45 #include "SDCCralloc.h"
46 #include "SDCCptropt.h"
50 /*-----------------------------------------------------------------*/
51 /* global variables */
57 /*-----------------------------------------------------------------*/
58 /* printSymName - prints the symbol names */
59 /*-----------------------------------------------------------------*/
60 int printSymName (void *vsym)
63 fprintf (stdout, " %s ", sym->name);
67 /*-----------------------------------------------------------------*/
68 /* cnvToFcall - does the actual conversion to function call */
69 /*-----------------------------------------------------------------*/
70 static void cnvToFcall (iCode *ic,eBBlock *ebp)
77 int lineno = ic->lineno;
79 ip = ic->next ; /* insertion point */
80 /* remove it from the iCode */
81 remiCodeFromeBBlock (ebp,ic);
119 /* if float support routines NOT compiled as reentrant */
120 if (! options.float_rent) {
123 if (IS_REGPARM(func->args->etype)) {
124 newic = newiCode(SEND,IC_LEFT(ic),NULL);
126 newic = newiCode('=',NULL,IC_LEFT(ic));
127 IC_RESULT(newic) = operandFromValue(func->args);
130 addiCodeToeBBlock(ebp,newic,ip);
131 newic->lineno = lineno;
134 if (IS_REGPARM(func->args->next->etype)) {
135 newic = newiCode(SEND,IC_LEFT(ic),NULL);
137 newic = newiCode('=',NULL,IC_RIGHT(ic));
138 IC_RESULT(newic) = operandFromValue(func->args->next);
140 addiCodeToeBBlock(ebp,newic,ip);
141 newic->lineno = lineno;
146 if (IS_REGPARM(func->args->next->etype)) {
147 newic = newiCode(SEND,right,NULL);
149 newic = newiCode(IPUSH,right,NULL);
153 addiCodeToeBBlock (ebp,newic,ip);
154 newic->lineno = lineno;
156 /* insert push left */
157 if (IS_REGPARM(func->args->etype)) {
158 newic = newiCode(SEND,left,NULL);
160 newic = newiCode(IPUSH,left,NULL);
163 addiCodeToeBBlock (ebp,newic,ip);
164 newic->lineno = lineno;
166 /* insert the call */
167 newic = newiCode(CALL,operandFromSymbol(func),NULL);
168 IC_RESULT(newic) = IC_RESULT(ic);
169 addiCodeToeBBlock(ebp,newic,ip);
170 newic->lineno = lineno;
173 /*-----------------------------------------------------------------*/
174 /* cnvToFloatCast - converts casts to floats to function calls */
175 /*-----------------------------------------------------------------*/
176 static void cnvToFloatCast (iCode *ic, eBBlock *ebp)
180 link *type = operandType(IC_RIGHT(ic));
181 int linenno = ic->lineno;
184 /* remove it from the iCode */
185 remiCodeFromeBBlock (ebp,ic);
186 /* depending on the type */
187 if (checkType(type,charType) == 1)
190 if (checkType(type,ucharType) == 1)
193 if (checkType(type,intType) == 1)
196 if (checkType(type,uintType) == 1)
199 if (checkType(type,longType) == 1)
204 /* if float support routines NOT compiled as reentrant */
205 if (! options.float_rent) {
207 if (IS_REGPARM(func->args->etype))
208 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;
218 if (IS_REGPARM(func->args->etype))
219 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
221 newic = newiCode(IPUSH,IC_RIGHT(ic),NULL);
224 addiCodeToeBBlock(ebp,newic,ip);
225 newic->lineno = linenno;
230 newic = newiCode(CALL,operandFromSymbol(func),NULL);
231 IC_RESULT(newic) = IC_RESULT(ic);
232 addiCodeToeBBlock(ebp,newic,ip);
233 newic->lineno = linenno;
237 /*-----------------------------------------------------------------*/
238 /* cnvFromFloatCast - converts casts From floats to function calls */
239 /*-----------------------------------------------------------------*/
240 static void cnvFromFloatCast (iCode *ic, eBBlock *ebp)
244 link *type = operandType(IC_LEFT(ic));
245 int lineno = ic->lineno ;
248 /* remove it from the iCode */
249 remiCodeFromeBBlock (ebp,ic);
251 /* depending on the type */
252 if (checkType(type,charType) == 1)
255 if (checkType(type,ucharType) == 1)
258 if (checkType(type,intType) == 1)
261 if (checkType(type,uintType) == 1)
264 if (checkType(type,longType) == 1)
269 /* if float support routines NOT compiled as reentrant */
270 if (! options.float_rent) {
272 if (IS_REGPARM(func->args->etype))
273 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
275 newic = newiCode('=',NULL,IC_RIGHT(ic));
276 IC_RESULT(newic) = operandFromValue(func->args);
278 addiCodeToeBBlock(ebp,newic,ip);
279 newic->lineno = lineno;
284 if (IS_REGPARM(func->args->etype))
285 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
287 newic = newiCode(IPUSH,IC_RIGHT(ic),NULL);
290 addiCodeToeBBlock(ebp,newic,ip);
291 newic->lineno = lineno;
296 newic = newiCode(CALL,operandFromSymbol(func),NULL);
297 IC_RESULT(newic) = IC_RESULT(ic);
298 addiCodeToeBBlock(ebp,newic,ip);
299 newic->lineno = lineno;
303 /*-----------------------------------------------------------------*/
304 /* convilong - converts int or long mults or divs to fcalls */
305 /*-----------------------------------------------------------------*/
306 static void convilong (iCode *ic, eBBlock *ebp, link *type, int op)
309 iCode *ip = ic->next;
311 int lineno = ic->lineno;
313 remiCodeFromeBBlock (ebp,ic);
315 /* depending on the type */
316 if (checkType(type,intType) == 1)
317 func = (op == '*' ? __mulsint :
318 (op == '%' ? __modsint :__divsint));
320 if (checkType(type,uintType) == 1)
321 func = (op == '*' ? __muluint :
322 (op == '%' ? __moduint : __divuint));
324 if (checkType(type,longType) == 1)
325 func = (op == '*' ? __mulslong :
326 (op == '%' ? __modslong : __divslong));
328 func = (op == '*'? __mululong :
329 (op == '%' ? __modulong : __divulong));
331 /* if int & long support routines NOT compiled as reentrant */
332 if (! options.intlong_rent) {
334 if (IS_REGPARM(func->args->etype))
335 newic = newiCode(SEND,IC_LEFT(ic),NULL);
337 newic = newiCode('=',NULL,IC_LEFT(ic));
338 IC_RESULT(newic) = operandFromValue(func->args);
340 addiCodeToeBBlock(ebp,newic,ip);
341 newic->lineno = lineno;
344 if (IS_REGPARM(func->args->next->etype))
345 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
347 newic = newiCode('=',NULL,IC_RIGHT(ic));
348 IC_RESULT(newic) = operandFromValue(func->args->next);
350 addiCodeToeBBlock(ebp,newic,ip);
351 newic->lineno = lineno;
356 /* compiled as reentrant then push */
358 if (IS_REGPARM(func->args->next->etype))
359 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
361 newic = newiCode(IPUSH,IC_RIGHT(ic),NULL);
364 addiCodeToeBBlock (ebp,newic,ip);
365 newic->lineno = lineno;
367 /* insert push left */
368 if (IS_REGPARM(func->args->etype))
369 newic = newiCode(SEND,IC_LEFT(ic),NULL);
371 newic = newiCode(IPUSH,IC_LEFT(ic),NULL);
374 addiCodeToeBBlock (ebp,newic,ip);
375 newic->lineno = lineno;
380 newic = newiCode(CALL,operandFromSymbol(func),NULL);
381 IC_RESULT(newic) = IC_RESULT(ic);
382 addiCodeToeBBlock(ebp,newic,ip);
383 newic->lineno = lineno;
387 /*-----------------------------------------------------------------*/
388 /* convertToFcall - converts some operations to fcalls */
389 /*-----------------------------------------------------------------*/
390 static void convertToFcall (eBBlock **ebbs, int count)
394 /* for all blocks do */
395 for (i = 0 ; i < count ; i++ ) {
398 /* for all instructions in the block do */
399 for (ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
401 /* floating point operations are
402 converted to function calls */
403 if ((IS_CONDITIONAL(ic) ||
404 IS_ARITHMETIC_OP(ic) ) &&
405 (IS_FLOAT(operandType(IC_RIGHT(ic))))) {
407 cnvToFcall(ic,ebbs[i]);
410 /* casting is a little different */
411 if (ic->op == CAST ) {
412 if (IS_FLOAT(operandType(IC_RIGHT(ic))))
413 cnvFromFloatCast (ic,ebbs[i]);
415 if (IS_FLOAT(operandType(IC_LEFT(ic))))
416 cnvToFloatCast (ic,ebbs[i]);
419 /* if long / int mult or divide or mod */
420 if (ic->op == '*' || ic->op == '/' || ic->op == '%' ) {
422 link *type = operandType(IC_LEFT(ic));
423 if (IS_INTEGRAL(type) && getSize(type) > 1)
424 convilong (ic,ebbs[i],type,ic->op);
430 /*-----------------------------------------------------------------*/
431 /* replaceRegEqv - replace all local variables with their reqv */
432 /*-----------------------------------------------------------------*/
433 static void replaceRegEqv ( eBBlock **ebbs, int count)
437 for (i = 0 ; i < count ; i++ ) {
441 for (ic = ebbs[i]->sch ; ic ; ic = ic->next) {
448 if (IS_TRUE_SYMOP(IC_COND(ic)) &&
449 OP_REQV(IC_COND(ic)))
450 IC_COND(ic) = opFromOpWithDU(OP_REQV(IC_COND(ic)),
451 OP_SYMBOL(IC_COND(ic))->defs,
452 OP_SYMBOL(IC_COND(ic))->uses);
457 if (ic->op == JUMPTABLE) {
458 if (IS_TRUE_SYMOP(IC_JTCOND(ic)) &&
459 OP_REQV(IC_JTCOND(ic)))
460 IC_JTCOND(ic) = opFromOpWithDU(OP_REQV(IC_JTCOND(ic)),
461 OP_SYMBOL(IC_JTCOND(ic))->defs,
462 OP_SYMBOL(IC_JTCOND(ic))->uses);
466 if (ic->op == RECEIVE) {
467 if (OP_SYMBOL(IC_RESULT(ic))->addrtaken)
468 OP_SYMBOL(IC_RESULT(ic))->isspilt = 1;
473 IS_TRUE_SYMOP(IC_RESULT(ic)) &&
474 OP_REQV(IC_RESULT(ic)) ) {
475 if (POINTER_SET(ic)) {
476 IC_RESULT(ic) = opFromOpWithDU(OP_REQV(IC_RESULT(ic)),
477 OP_SYMBOL(IC_RESULT(ic))->defs,
478 OP_SYMBOL(IC_RESULT(ic))->uses);
479 IC_RESULT(ic)->isaddr = 1;
481 IC_RESULT(ic) = opFromOpWithDU(OP_REQV(IC_RESULT(ic)),
482 OP_SYMBOL(IC_RESULT(ic))->defs,
483 OP_SYMBOL(IC_RESULT(ic))->uses);
487 IS_TRUE_SYMOP(IC_RIGHT(ic)) &&
488 OP_REQV(IC_RIGHT(ic)) ) {
489 IC_RIGHT(ic) = opFromOpWithDU(OP_REQV(IC_RIGHT(ic)),
490 OP_SYMBOL(IC_RIGHT(ic))->defs,
491 OP_SYMBOL(IC_RIGHT(ic))->uses);
492 IC_RIGHT(ic)->isaddr = 0;
496 IS_TRUE_SYMOP(IC_LEFT(ic)) &&
497 OP_REQV(IC_LEFT(ic)) ) {
498 IC_LEFT(ic) = opFromOpWithDU(OP_REQV(IC_LEFT(ic)),
499 OP_SYMBOL(IC_LEFT(ic))->defs,
500 OP_SYMBOL(IC_LEFT(ic))->uses);
501 IC_LEFT(ic)->isaddr = 0;
507 /*-----------------------------------------------------------------*/
508 /* killDeadCode - eliminates dead assignments */
509 /*-----------------------------------------------------------------*/
510 int killDeadCode ( eBBlock **ebbs, int count)
517 /* basic algorithm :- */
518 /* first the exclusion rules :- */
519 /* 1. if result is a global or volatile then skip */
520 /* 2. if assignment and result is a temp & isaddr then skip */
521 /* since this means array & pointer access, will be taken */
522 /* care of by alias analysis. */
523 /* 3. if the result is used in the remainder of the block skip*/
524 /* 4. if this definition does not reach the end of the block */
525 /* i.e. the result is not present in the outExprs then KILL*/
526 /* 5. if it reaches the end of block & is used by some success*/
529 /* this whole process is carried on iteratively till no change */
533 /* for all blocks do */
534 for ( i = 0 ; i < count ; i++ ) {
537 /* for all instructions in the block do */
538 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
547 /* if the result is volatile then continue */
548 if (IC_RESULT(ic) && isOperandVolatile(IC_RESULT(ic),FALSE))
551 /* if the result is a temp & isaddr then skip */
552 if (IC_RESULT(ic) && POINTER_SET(ic))
555 /* if the result is used in the remainder of the */
556 /* block then skip */
557 if (usedInRemaining (IC_RESULT(ic),ic->next))
560 /* does this definition reach the end of the block
561 or the usage is zero then we can kill */
562 if (! bitVectBitValue(ebbs[i]->outDefs,ic->key))
563 kill = 1; /* if not we can kill it */
565 /* if this is a global variable or function parameter */
566 /* we cannot kill anyway */
567 if (isOperandGlobal(IC_RESULT(ic)) ||
568 (OP_SYMBOL(IC_RESULT(ic))->_isparm &&
569 !OP_SYMBOL(IC_RESULT(ic))->ismyparm))
572 /* if we are sure there are no usages */
573 if (bitVectIsZero(OP_USES(IC_RESULT(ic)))) {
578 /* reset visited flag */
579 for(j=0; j < count ; ebbs[j++]->visited = 0);
581 /* find out if this definition is alive */
582 if ( applyToSet (ebbs[i]->succList,
591 /* kill this one if required */
596 remiCodeFromeBBlock(ebbs[i],ic);
598 /* now delete from defUseSet */
599 deleteItemIf (&ebbs[i]->outExprs,ifDiCodeIsX,ic);
600 bitVectUnSetBit (ebbs[i]->outDefs,ic->key);
602 /* and defset of the block */
603 bitVectUnSetBit (ebbs[i]->defSet,ic->key);
605 /* for the left & right remove the usage */
606 if (IS_SYMOP(IC_LEFT(ic)))
607 bitVectUnSetBit(OP_USES(IC_LEFT(ic)),ic->key);
609 if (IS_SYMOP(IC_RIGHT(ic)))
610 bitVectUnSetBit(OP_USES(IC_RIGHT(ic)),ic->key);
613 } /* end of all instructions */
615 if (!ebbs[i]->sch && !ebbs[i]->noPath)
616 disconBBlock(ebbs[i],ebbs,count);
618 } /* end of for all blocks */
622 } /* end of while(1) */
627 /*-----------------------------------------------------------------*/
628 /* printCyclomatic - prints the cyclomatic information */
629 /*-----------------------------------------------------------------*/
630 static void printCyclomatic (eBBlock **ebbs, int count)
632 int nEdges = elementsInSet(graphEdges);
635 for (i = 0 ; i < count ; i++)
636 nNodes += (! ebbs[i]->noPath);
638 /* print the information */
639 werror(I_CYCLOMATIC,currFunc->name,nEdges,nNodes, nEdges - nNodes + 2);
642 /*-----------------------------------------------------------------*/
643 /* canOverlayLocals - returns true if the local variables can overlayed */
644 /*-----------------------------------------------------------------*/
645 static bool canOverlayLocals (eBBlock **ebbs, int count)
648 /* if staticAuto is in effect or the current function
649 being compiled is reentrant or the overlay segment
650 is empty or no overlay option is in effect then */
651 if (options.noOverlay ||
654 (IS_RENT(currFunc->etype) ||
655 IS_ISR(currFunc->etype))) ||
656 elementsInSet(overlay->syms) == 0)
660 /* otherwise do thru the blocks and see if there
661 any function calls if found then return false */
662 for (i = 0; i < count ; i++ ) {
665 for (ic = ebbs[i]->sch; ic ; ic = ic->next)
666 if (ic && ( ic->op == CALL || ic->op == PCALL))
670 /* no function calls found return TRUE */
675 /*-----------------------------------------------------------------*/
676 /* eBBlockFromiCode - creates extended basic blocks from iCode */
677 /* will return an array of eBBlock pointers */
678 /*-----------------------------------------------------------------*/
679 eBBlock **eBBlockFromiCode (iCode *ic)
681 eBBlock **ebbs = NULL ;
689 /* if nothing passed then return nothing */
696 /* optimize the chain for labels & gotos
697 this will eliminate redundant labels and
698 will change jump to jumps by jumps */
699 ic = iCodeLabelOptimize (ic);
701 /* break it down into basic blocks */
702 ebbs = iCodeBreakDown (ic,&count);
705 /* compute the control flow */
706 computeControlFlow (ebbs,count,0);
708 /* dumpraw if asked for */
709 if (options.dump_raw)
710 dumpEbbsToFileExt(".dumpraw0",ebbs,count);
712 /* replace the local variables with their
713 register equivalents : the liveRange computation
714 along with the register allocation will determine
715 if it finally stays in the registers */
716 replaceRegEqv (ebbs,count);
718 /* create loop regions */
719 loops = createLoopRegions (ebbs,count);
721 /* dumpraw if asked for */
722 if (options.dump_raw)
723 dumpEbbsToFileExt(".dumpraw1",ebbs,count);
725 /* do common subexpression elimination for each block */
726 change = cseAllBlocks(ebbs,saveCount);
728 /* dumpraw if asked for */
729 if (options.dump_raw)
730 dumpEbbsToFileExt(".dumpcse",ebbs,count);
732 /* compute the data flow */
733 computeDataFlow (ebbs,saveCount);
735 /* dumpraw if asked for */
736 if (options.dump_raw)
737 dumpEbbsToFileExt(".dumpdflow",ebbs,count);
739 /* global common subexpression elimination */
740 if ( optimize.global_cse ) {
741 change += cseAllBlocks(ebbs,saveCount);
742 if (options.dump_gcse)
743 dumpEbbsToFileExt(".dumpgcse",ebbs,saveCount);
746 kchange = killDeadCode (ebbs, saveCount);
748 if (options.dump_kill)
749 dumpEbbsToFileExt(".dumpdeadcode",ebbs,count);
751 /* do loop optimizations */
752 change += (lchange = loopOptimizations (loops,ebbs,count));
753 if (options.dump_loop)
754 dumpEbbsToFileExt(".dumploop",ebbs,count);
756 /* recompute the data flow and apply global cse again
757 if loops optimizations or dead code caused a change:
758 loops will brings out of the loop which then may be
759 available for use in the later blocks: dead code
760 elimination could potentially disconnect some blocks
761 conditional flow may be efected so we need to apply
762 subexpression once more */
763 if ( lchange || kchange ) {
765 computeDataFlow (ebbs,saveCount);
766 change += cseAllBlocks(ebbs,saveCount);
767 if (options.dump_loop)
768 dumpEbbsToFileExt(".dumploopg",ebbs,count);
770 /* if loop optimizations caused a change then do
771 dead code elimination once more : this will
772 get rid of the extra assignments to the induction
773 variables created during loop optimizations */
774 killDeadCode (ebbs, saveCount);
776 if (options.dump_loop)
777 dumpEbbsToFileExt(".dumploopd",ebbs,count);
782 /* sort it back by block number */
783 qsort (ebbs,saveCount,sizeof(eBBlock *),bbNumCompare);
785 /* if cyclomatic info requested then print it */
786 if (options.cyclomatic)
787 printCyclomatic(ebbs,saveCount);
790 /* convert operations with support routines
791 written in C to function calls : Iam doing
792 this at this point since I want all the
793 operations to be as they are for optimzations */
794 convertToFcall (ebbs,count);
796 /* check if the parameters and local variables
797 of this function can be put in the overlay segment
798 This check is essentially to see if the function
799 calls any other functions if yes then we cannot
801 if (canOverlayLocals(ebbs,count))
802 /* if we can then put the parameters &
803 local variables in the overlay set */
806 /* otherwise put them into data where
810 /* compute the live ranges */
811 computeLiveRanges (ebbs,count);
813 if (options.dump_range)
814 dumpEbbsToFileExt(".dumprange",ebbs,count);
816 /* allocate registers & generate code */
817 assignRegisters (ebbs,count);
819 /* throw away blocks */
820 setToNull ((void **)&graphEdges);
826 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */