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);
617 /* Turn this on when it's safe to destablize */
618 /*-----------------------------------------------------------------*/
619 /* discardDeadParamReceives - remove any RECEIVE opcodes which */
620 /* refer to dead variables. */
621 /*-----------------------------------------------------------------*/
622 static void discardDeadParamReceives(eBBlock **ebbs, int count)
628 for (i = 0 ; i < count ; i++)
630 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next )
632 if (ic->op == RECEIVE)
634 if (IC_RESULT(ic) && OP_SYMBOL(IC_RESULT(ic))
635 && !OP_SYMBOL(IC_RESULT(ic))->used)
638 fprintf(stderr, "discarding dead receive for %s\n",
639 OP_SYMBOL(IC_RESULT(ic))->name);
641 dummyIcode.next = ic->next;
642 remiCodeFromeBBlock(ebbs[i], ic);
651 /*-----------------------------------------------------------------*/
652 /* eBBlockFromiCode - creates extended basic blocks from iCode */
653 /* will return an array of eBBlock pointers */
654 /*-----------------------------------------------------------------*/
655 eBBlock **eBBlockFromiCode (iCode *ic)
657 eBBlock **ebbs = NULL ;
665 /* if nothing passed then return nothing */
672 /* optimize the chain for labels & gotos
673 this will eliminate redundant labels and
674 will change jump to jumps by jumps */
675 ic = iCodeLabelOptimize (ic);
677 /* break it down into basic blocks */
678 ebbs = iCodeBreakDown (ic,&count);
681 /* compute the control flow */
682 computeControlFlow (ebbs,count,0);
684 /* dumpraw if asked for */
685 if (options.dump_raw)
686 dumpEbbsToFileExt(".dumpraw0",ebbs,count);
688 /* replace the local variables with their
689 register equivalents : the liveRange computation
690 along with the register allocation will determine
691 if it finally stays in the registers */
692 replaceRegEqv (ebbs,count);
694 /* create loop regions */
695 loops = createLoopRegions (ebbs,count);
697 /* dumpraw if asked for */
698 if (options.dump_raw)
699 dumpEbbsToFileExt(".dumpraw1",ebbs,count);
701 /* do common subexpression elimination for each block */
702 change = cseAllBlocks(ebbs,saveCount);
704 /* dumpraw if asked for */
705 if (options.dump_raw)
706 dumpEbbsToFileExt(".dumpcse",ebbs,count);
708 /* compute the data flow */
709 computeDataFlow (ebbs,saveCount);
711 /* dumpraw if asked for */
712 if (options.dump_raw)
713 dumpEbbsToFileExt(".dumpdflow",ebbs,count);
715 /* global common subexpression elimination */
716 if ( optimize.global_cse ) {
717 change += cseAllBlocks(ebbs,saveCount);
718 if (options.dump_gcse)
719 dumpEbbsToFileExt(".dumpgcse",ebbs,saveCount);
722 kchange = killDeadCode (ebbs, saveCount);
724 if (options.dump_kill)
725 dumpEbbsToFileExt(".dumpdeadcode",ebbs,count);
727 /* do loop optimizations */
728 change += (lchange = loopOptimizations (loops,ebbs,count));
729 if (options.dump_loop)
730 dumpEbbsToFileExt(".dumploop",ebbs,count);
732 /* recompute the data flow and apply global cse again
733 if loops optimizations or dead code caused a change:
734 loops will brings out of the loop which then may be
735 available for use in the later blocks: dead code
736 elimination could potentially disconnect some blocks
737 conditional flow may be efected so we need to apply
738 subexpression once more */
739 if ( lchange || kchange ) {
741 computeDataFlow (ebbs,saveCount);
742 change += cseAllBlocks(ebbs,saveCount);
743 if (options.dump_loop)
744 dumpEbbsToFileExt(".dumploopg",ebbs,count);
746 /* if loop optimizations caused a change then do
747 dead code elimination once more : this will
748 get rid of the extra assignments to the induction
749 variables created during loop optimizations */
750 killDeadCode (ebbs, saveCount);
752 if (options.dump_loop)
753 dumpEbbsToFileExt(".dumploopd",ebbs,count);
758 /* sort it back by block number */
759 qsort (ebbs,saveCount,sizeof(eBBlock *),bbNumCompare);
761 /* if cyclomatic info requested then print it */
762 if (options.cyclomatic)
763 printCyclomatic(ebbs,saveCount);
766 /* convert operations with support routines
767 written in C to function calls : Iam doing
768 this at this point since I want all the
769 operations to be as they are for optimzations */
770 convertToFcall (ebbs,count);
773 /* compute the live ranges */
774 computeLiveRanges (ebbs,count);
776 if (options.dump_range)
777 dumpEbbsToFileExt(".dumprange",ebbs,count);
780 /* Turn this on when it's safe to destablize */
781 /* Now that we have the live ranges, discard parameter
782 * receives for unused parameters.
784 discardDeadParamReceives(ebbs,count);
787 /* allocate registers & generate code */
788 port->assignRegisters(ebbs,count);
790 /* throw away blocks */
791 setToNull ((void **)&graphEdges);
799 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */