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 /*-----------------------------------------------------------------*/
41 int printSymName (void *vsym)
44 fprintf (stdout, " %s ", sym->name);
48 /*-----------------------------------------------------------------*/
49 /* cnvToFcall - does the actual conversion to function call */
50 /*-----------------------------------------------------------------*/
51 static void cnvToFcall (iCode *ic,eBBlock *ebp)
58 int lineno = ic->lineno;
60 ip = ic->next ; /* insertion point */
61 /* remove it from the iCode */
62 remiCodeFromeBBlock (ebp,ic);
100 /* if float support routines NOT compiled as reentrant */
101 if (! options.float_rent) {
104 if (IS_REGPARM(func->args->etype)) {
105 newic = newiCode(SEND,IC_LEFT(ic),NULL);
107 newic = newiCode('=',NULL,IC_LEFT(ic));
108 IC_RESULT(newic) = operandFromValue(func->args);
111 addiCodeToeBBlock(ebp,newic,ip);
112 newic->lineno = lineno;
115 if (IS_REGPARM(func->args->next->etype)) {
116 newic = newiCode(SEND,IC_LEFT(ic),NULL);
118 newic = newiCode('=',NULL,IC_RIGHT(ic));
119 IC_RESULT(newic) = operandFromValue(func->args->next);
121 addiCodeToeBBlock(ebp,newic,ip);
122 newic->lineno = lineno;
127 if (IS_REGPARM(func->args->next->etype)) {
128 newic = newiCode(SEND,right,NULL);
130 newic = newiCode(IPUSH,right,NULL);
134 addiCodeToeBBlock (ebp,newic,ip);
135 newic->lineno = lineno;
137 /* insert push left */
138 if (IS_REGPARM(func->args->etype)) {
139 newic = newiCode(SEND,left,NULL);
141 newic = newiCode(IPUSH,left,NULL);
144 addiCodeToeBBlock (ebp,newic,ip);
145 newic->lineno = lineno;
147 /* insert the call */
148 newic = newiCode(CALL,operandFromSymbol(func),NULL);
149 IC_RESULT(newic) = IC_RESULT(ic);
150 addiCodeToeBBlock(ebp,newic,ip);
151 newic->lineno = lineno;
154 /*-----------------------------------------------------------------*/
155 /* cnvToFloatCast - converts casts to floats to function calls */
156 /*-----------------------------------------------------------------*/
157 static void cnvToFloatCast (iCode *ic, eBBlock *ebp)
161 link *type = operandType(IC_RIGHT(ic));
162 int linenno = ic->lineno;
166 /* remove it from the iCode */
167 remiCodeFromeBBlock (ebp,ic);
168 /* depending on the type */
169 for (bwd = 0; bwd < 3; bwd++) {
170 for (su = 0; su < 2; su++) {
171 if (checkType(type, __multypes[bwd][su]) == 1) {
172 func = __conv[0][bwd][su];
180 /* if float support routines NOT compiled as reentrant */
181 if (! options.float_rent) {
183 if (IS_REGPARM(func->args->etype))
184 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
186 newic = newiCode('=',NULL,IC_RIGHT(ic));
187 IC_RESULT(newic) = operandFromValue(func->args);
189 addiCodeToeBBlock(ebp,newic,ip);
190 newic->lineno = linenno;
194 if (IS_REGPARM(func->args->etype))
195 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
197 newic = newiCode(IPUSH,IC_RIGHT(ic),NULL);
200 addiCodeToeBBlock(ebp,newic,ip);
201 newic->lineno = linenno;
206 newic = newiCode(CALL,operandFromSymbol(func),NULL);
207 IC_RESULT(newic) = IC_RESULT(ic);
208 addiCodeToeBBlock(ebp,newic,ip);
209 newic->lineno = linenno;
213 /*-----------------------------------------------------------------*/
214 /* cnvFromFloatCast - converts casts From floats to function calls */
215 /*-----------------------------------------------------------------*/
216 static void cnvFromFloatCast (iCode *ic, eBBlock *ebp)
220 link *type = operandType(IC_LEFT(ic));
221 int lineno = ic->lineno ;
225 /* remove it from the iCode */
226 remiCodeFromeBBlock (ebp,ic);
228 /* depending on the type */
229 for (bwd = 0; bwd < 3; bwd++) {
230 for (su = 0; su < 2; su++) {
231 if (checkType(type, __multypes[bwd][su]) == 1) {
232 func = __conv[1][bwd][su];
240 /* if float support routines NOT compiled as reentrant */
241 if (! options.float_rent) {
243 if (IS_REGPARM(func->args->etype))
244 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
246 newic = newiCode('=',NULL,IC_RIGHT(ic));
247 IC_RESULT(newic) = operandFromValue(func->args);
249 addiCodeToeBBlock(ebp,newic,ip);
250 newic->lineno = lineno;
255 if (IS_REGPARM(func->args->etype))
256 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
258 newic = newiCode(IPUSH,IC_RIGHT(ic),NULL);
261 addiCodeToeBBlock(ebp,newic,ip);
262 newic->lineno = lineno;
267 newic = newiCode(CALL,operandFromSymbol(func),NULL);
268 IC_RESULT(newic) = IC_RESULT(ic);
269 addiCodeToeBBlock(ebp,newic,ip);
270 newic->lineno = lineno;
274 /*-----------------------------------------------------------------*/
275 /* convilong - converts int or long mults or divs to fcalls */
276 /*-----------------------------------------------------------------*/
277 static void convilong (iCode *ic, eBBlock *ebp, link *type, int op)
280 iCode *ip = ic->next;
282 int lineno = ic->lineno;
285 remiCodeFromeBBlock (ebp,ic);
287 /* depending on the type */
288 for (bwd = 0; bwd < 3; bwd++) {
289 for (su = 0; su < 2; su++) {
290 if (checkType(type, __multypes[bwd][su]) == 1) {
292 func = __muldiv[0][bwd][su];
294 func = __muldiv[1][bwd][su];
296 func = __muldiv[2][bwd][su];
305 /* if int & long support routines NOT compiled as reentrant */
306 if (! options.intlong_rent) {
308 if (IS_REGPARM(func->args->etype))
309 newic = newiCode(SEND,IC_LEFT(ic),NULL);
311 newic = newiCode('=',NULL,IC_LEFT(ic));
312 IC_RESULT(newic) = operandFromValue(func->args);
314 addiCodeToeBBlock(ebp,newic,ip);
315 newic->lineno = lineno;
318 if (IS_REGPARM(func->args->next->etype))
319 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
321 newic = newiCode('=',NULL,IC_RIGHT(ic));
322 IC_RESULT(newic) = operandFromValue(func->args->next);
324 addiCodeToeBBlock(ebp,newic,ip);
325 newic->lineno = lineno;
330 /* compiled as reentrant then push */
332 if (IS_REGPARM(func->args->next->etype))
333 newic = newiCode(SEND,IC_RIGHT(ic),NULL);
335 newic = newiCode(IPUSH,IC_RIGHT(ic),NULL);
338 addiCodeToeBBlock (ebp,newic,ip);
339 newic->lineno = lineno;
341 /* insert push left */
342 if (IS_REGPARM(func->args->etype))
343 newic = newiCode(SEND,IC_LEFT(ic),NULL);
345 newic = newiCode(IPUSH,IC_LEFT(ic),NULL);
348 addiCodeToeBBlock (ebp,newic,ip);
349 newic->lineno = lineno;
354 newic = newiCode(CALL,operandFromSymbol(func),NULL);
355 IC_RESULT(newic) = IC_RESULT(ic);
356 addiCodeToeBBlock(ebp,newic,ip);
357 newic->lineno = lineno;
361 /*-----------------------------------------------------------------*/
362 /* convertToFcall - converts some operations to fcalls */
363 /*-----------------------------------------------------------------*/
364 static void convertToFcall (eBBlock **ebbs, int count)
368 /* for all blocks do */
369 for (i = 0 ; i < count ; i++ ) {
372 /* for all instructions in the block do */
373 for (ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
375 /* floating point operations are
376 converted to function calls */
377 if ((IS_CONDITIONAL(ic) ||
378 IS_ARITHMETIC_OP(ic) ) &&
379 (IS_FLOAT(operandType(IC_RIGHT(ic))))) {
381 cnvToFcall(ic,ebbs[i]);
384 /* casting is a little different */
385 if (ic->op == CAST ) {
386 if (IS_FLOAT(operandType(IC_RIGHT(ic))))
387 cnvFromFloatCast (ic,ebbs[i]);
389 if (IS_FLOAT(operandType(IC_LEFT(ic))))
390 cnvToFloatCast (ic,ebbs[i]);
393 /* if long / int mult or divide or mod */
394 if (ic->op == '*' || ic->op == '/' || ic->op == '%' ) {
396 link *type = operandType(IC_LEFT(ic));
397 if (IS_INTEGRAL(type) && getSize(type) > port->muldiv.native_below)
398 convilong (ic,ebbs[i],type,ic->op);
404 /*-----------------------------------------------------------------*/
405 /* replaceRegEqv - replace all local variables with their reqv */
406 /*-----------------------------------------------------------------*/
407 static void replaceRegEqv ( eBBlock **ebbs, int count)
411 for (i = 0 ; i < count ; i++ ) {
415 for (ic = ebbs[i]->sch ; ic ; ic = ic->next) {
422 if (IS_TRUE_SYMOP(IC_COND(ic)) &&
423 OP_REQV(IC_COND(ic)))
424 IC_COND(ic) = opFromOpWithDU(OP_REQV(IC_COND(ic)),
425 OP_SYMBOL(IC_COND(ic))->defs,
426 OP_SYMBOL(IC_COND(ic))->uses);
431 if (ic->op == JUMPTABLE) {
432 if (IS_TRUE_SYMOP(IC_JTCOND(ic)) &&
433 OP_REQV(IC_JTCOND(ic)))
434 IC_JTCOND(ic) = opFromOpWithDU(OP_REQV(IC_JTCOND(ic)),
435 OP_SYMBOL(IC_JTCOND(ic))->defs,
436 OP_SYMBOL(IC_JTCOND(ic))->uses);
440 if (ic->op == RECEIVE) {
441 if (OP_SYMBOL(IC_RESULT(ic))->addrtaken)
442 OP_SYMBOL(IC_RESULT(ic))->isspilt = 1;
447 IS_TRUE_SYMOP(IC_RESULT(ic)) &&
448 OP_REQV(IC_RESULT(ic)) ) {
449 if (POINTER_SET(ic)) {
450 IC_RESULT(ic) = opFromOpWithDU(OP_REQV(IC_RESULT(ic)),
451 OP_SYMBOL(IC_RESULT(ic))->defs,
452 OP_SYMBOL(IC_RESULT(ic))->uses);
453 IC_RESULT(ic)->isaddr = 1;
455 IC_RESULT(ic) = opFromOpWithDU(OP_REQV(IC_RESULT(ic)),
456 OP_SYMBOL(IC_RESULT(ic))->defs,
457 OP_SYMBOL(IC_RESULT(ic))->uses);
461 IS_TRUE_SYMOP(IC_RIGHT(ic)) &&
462 OP_REQV(IC_RIGHT(ic)) ) {
463 IC_RIGHT(ic) = opFromOpWithDU(OP_REQV(IC_RIGHT(ic)),
464 OP_SYMBOL(IC_RIGHT(ic))->defs,
465 OP_SYMBOL(IC_RIGHT(ic))->uses);
466 IC_RIGHT(ic)->isaddr = 0;
470 IS_TRUE_SYMOP(IC_LEFT(ic)) &&
471 OP_REQV(IC_LEFT(ic)) ) {
472 IC_LEFT(ic) = opFromOpWithDU(OP_REQV(IC_LEFT(ic)),
473 OP_SYMBOL(IC_LEFT(ic))->defs,
474 OP_SYMBOL(IC_LEFT(ic))->uses);
475 IC_LEFT(ic)->isaddr = 0;
481 /*-----------------------------------------------------------------*/
482 /* killDeadCode - eliminates dead assignments */
483 /*-----------------------------------------------------------------*/
484 int killDeadCode ( eBBlock **ebbs, int count)
491 /* basic algorithm :- */
492 /* first the exclusion rules :- */
493 /* 1. if result is a global or volatile then skip */
494 /* 2. if assignment and result is a temp & isaddr then skip */
495 /* since this means array & pointer access, will be taken */
496 /* care of by alias analysis. */
497 /* 3. if the result is used in the remainder of the block skip*/
498 /* 4. if this definition does not reach the end of the block */
499 /* i.e. the result is not present in the outExprs then KILL*/
500 /* 5. if it reaches the end of block & is used by some success*/
503 /* this whole process is carried on iteratively till no change */
507 /* for all blocks do */
508 for ( i = 0 ; i < count ; i++ ) {
511 /* for all instructions in the block do */
512 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
521 /* if the result is volatile then continue */
522 if (IC_RESULT(ic) && isOperandVolatile(IC_RESULT(ic),FALSE))
525 /* if the result is a temp & isaddr then skip */
526 if (IC_RESULT(ic) && POINTER_SET(ic))
529 /* if the result is used in the remainder of the */
530 /* block then skip */
531 if (usedInRemaining (IC_RESULT(ic),ic->next))
534 /* does this definition reach the end of the block
535 or the usage is zero then we can kill */
536 if (! bitVectBitValue(ebbs[i]->outDefs,ic->key))
537 kill = 1; /* if not we can kill it */
539 /* if this is a global variable or function parameter */
540 /* we cannot kill anyway */
541 if (isOperandGlobal(IC_RESULT(ic)) ||
542 (OP_SYMBOL(IC_RESULT(ic))->_isparm &&
543 !OP_SYMBOL(IC_RESULT(ic))->ismyparm))
546 /* if we are sure there are no usages */
547 if (bitVectIsZero(OP_USES(IC_RESULT(ic)))) {
552 /* reset visited flag */
553 for(j=0; j < count ; ebbs[j++]->visited = 0);
555 /* find out if this definition is alive */
556 if ( applyToSet (ebbs[i]->succList,
565 /* kill this one if required */
570 remiCodeFromeBBlock(ebbs[i],ic);
572 /* now delete from defUseSet */
573 deleteItemIf (&ebbs[i]->outExprs,ifDiCodeIsX,ic);
574 bitVectUnSetBit (ebbs[i]->outDefs,ic->key);
576 /* and defset of the block */
577 bitVectUnSetBit (ebbs[i]->defSet,ic->key);
579 /* for the left & right remove the usage */
580 if (IS_SYMOP(IC_LEFT(ic)))
581 bitVectUnSetBit(OP_USES(IC_LEFT(ic)),ic->key);
583 if (IS_SYMOP(IC_RIGHT(ic)))
584 bitVectUnSetBit(OP_USES(IC_RIGHT(ic)),ic->key);
587 } /* end of all instructions */
589 if (!ebbs[i]->sch && !ebbs[i]->noPath)
590 disconBBlock(ebbs[i],ebbs,count);
592 } /* end of for all blocks */
596 } /* end of while(1) */
601 /*-----------------------------------------------------------------*/
602 /* printCyclomatic - prints the cyclomatic information */
603 /*-----------------------------------------------------------------*/
604 static void printCyclomatic (eBBlock **ebbs, int count)
606 int nEdges = elementsInSet(graphEdges);
609 for (i = 0 ; i < count ; i++)
610 nNodes += (! ebbs[i]->noPath);
612 /* print the information */
613 werror(I_CYCLOMATIC,currFunc->name,nEdges,nNodes, nEdges - nNodes + 2);
616 /*-----------------------------------------------------------------*/
617 /* canOverlayLocals - returns true if the local variables can overlayed */
618 /*-----------------------------------------------------------------*/
619 static bool canOverlayLocals (eBBlock **ebbs, int count)
622 /* if staticAuto is in effect or the current function
623 being compiled is reentrant or the overlay segment
624 is empty or no overlay option is in effect then */
625 if (options.noOverlay ||
628 (IS_RENT(currFunc->etype) ||
629 IS_ISR(currFunc->etype))) ||
630 elementsInSet(overlay->syms) == 0)
634 /* otherwise do thru the blocks and see if there
635 any function calls if found then return false */
636 for (i = 0; i < count ; i++ ) {
639 for (ic = ebbs[i]->sch; ic ; ic = ic->next)
640 if (ic && ( ic->op == CALL || ic->op == PCALL))
644 /* no function calls found return TRUE */
649 /*-----------------------------------------------------------------*/
650 /* eBBlockFromiCode - creates extended basic blocks from iCode */
651 /* will return an array of eBBlock pointers */
652 /*-----------------------------------------------------------------*/
653 eBBlock **eBBlockFromiCode (iCode *ic)
655 eBBlock **ebbs = NULL ;
663 /* if nothing passed then return nothing */
670 /* optimize the chain for labels & gotos
671 this will eliminate redundant labels and
672 will change jump to jumps by jumps */
673 ic = iCodeLabelOptimize (ic);
675 /* break it down into basic blocks */
676 ebbs = iCodeBreakDown (ic,&count);
679 /* compute the control flow */
680 computeControlFlow (ebbs,count,0);
682 /* dumpraw if asked for */
683 if (options.dump_raw)
684 dumpEbbsToFileExt(".dumpraw0",ebbs,count);
686 /* replace the local variables with their
687 register equivalents : the liveRange computation
688 along with the register allocation will determine
689 if it finally stays in the registers */
690 replaceRegEqv (ebbs,count);
692 /* create loop regions */
693 loops = createLoopRegions (ebbs,count);
695 /* dumpraw if asked for */
696 if (options.dump_raw)
697 dumpEbbsToFileExt(".dumpraw1",ebbs,count);
699 /* do common subexpression elimination for each block */
700 change = cseAllBlocks(ebbs,saveCount);
702 /* dumpraw if asked for */
703 if (options.dump_raw)
704 dumpEbbsToFileExt(".dumpcse",ebbs,count);
706 /* compute the data flow */
707 computeDataFlow (ebbs,saveCount);
709 /* dumpraw if asked for */
710 if (options.dump_raw)
711 dumpEbbsToFileExt(".dumpdflow",ebbs,count);
713 /* global common subexpression elimination */
714 if ( optimize.global_cse ) {
715 change += cseAllBlocks(ebbs,saveCount);
716 if (options.dump_gcse)
717 dumpEbbsToFileExt(".dumpgcse",ebbs,saveCount);
720 kchange = killDeadCode (ebbs, saveCount);
722 if (options.dump_kill)
723 dumpEbbsToFileExt(".dumpdeadcode",ebbs,count);
725 /* do loop optimizations */
726 change += (lchange = loopOptimizations (loops,ebbs,count));
727 if (options.dump_loop)
728 dumpEbbsToFileExt(".dumploop",ebbs,count);
730 /* recompute the data flow and apply global cse again
731 if loops optimizations or dead code caused a change:
732 loops will brings out of the loop which then may be
733 available for use in the later blocks: dead code
734 elimination could potentially disconnect some blocks
735 conditional flow may be efected so we need to apply
736 subexpression once more */
737 if ( lchange || kchange ) {
739 computeDataFlow (ebbs,saveCount);
740 change += cseAllBlocks(ebbs,saveCount);
741 if (options.dump_loop)
742 dumpEbbsToFileExt(".dumploopg",ebbs,count);
744 /* if loop optimizations caused a change then do
745 dead code elimination once more : this will
746 get rid of the extra assignments to the induction
747 variables created during loop optimizations */
748 killDeadCode (ebbs, saveCount);
750 if (options.dump_loop)
751 dumpEbbsToFileExt(".dumploopd",ebbs,count);
756 /* sort it back by block number */
757 qsort (ebbs,saveCount,sizeof(eBBlock *),bbNumCompare);
759 /* if cyclomatic info requested then print it */
760 if (options.cyclomatic)
761 printCyclomatic(ebbs,saveCount);
764 /* convert operations with support routines
765 written in C to function calls : Iam doing
766 this at this point since I want all the
767 operations to be as they are for optimzations */
768 convertToFcall (ebbs,count);
770 /* check if the parameters and local variables
771 of this function can be put in the overlay segment
772 This check is essentially to see if the function
773 calls any other functions if yes then we cannot
775 if (canOverlayLocals(ebbs,count))
776 /* if we can then put the parameters &
777 local variables in the overlay set */
780 /* otherwise put them into data where
784 /* compute the live ranges */
785 computeLiveRanges (ebbs,count);
787 if (options.dump_range)
788 dumpEbbsToFileExt(".dumprange",ebbs,count);
790 /* allocate registers & generate code */
791 port->assignRegisters(ebbs,count);
793 /* throw away blocks */
794 setToNull ((void **)&graphEdges);
800 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */