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 /*-----------------------------------------------------------------*/
618 /* eBBlockFromiCode - creates extended basic blocks from iCode */
619 /* will return an array of eBBlock pointers */
620 /*-----------------------------------------------------------------*/
621 eBBlock **eBBlockFromiCode (iCode *ic)
623 eBBlock **ebbs = NULL ;
631 /* if nothing passed then return nothing */
638 /* optimize the chain for labels & gotos
639 this will eliminate redundant labels and
640 will change jump to jumps by jumps */
641 ic = iCodeLabelOptimize (ic);
643 /* break it down into basic blocks */
644 ebbs = iCodeBreakDown (ic,&count);
647 /* compute the control flow */
648 computeControlFlow (ebbs,count,0);
650 /* dumpraw if asked for */
651 if (options.dump_raw)
652 dumpEbbsToFileExt(".dumpraw0",ebbs,count);
654 /* replace the local variables with their
655 register equivalents : the liveRange computation
656 along with the register allocation will determine
657 if it finally stays in the registers */
658 replaceRegEqv (ebbs,count);
660 /* create loop regions */
661 loops = createLoopRegions (ebbs,count);
663 /* dumpraw if asked for */
664 if (options.dump_raw)
665 dumpEbbsToFileExt(".dumpraw1",ebbs,count);
667 /* do common subexpression elimination for each block */
668 change = cseAllBlocks(ebbs,saveCount);
670 /* dumpraw if asked for */
671 if (options.dump_raw)
672 dumpEbbsToFileExt(".dumpcse",ebbs,count);
674 /* compute the data flow */
675 computeDataFlow (ebbs,saveCount);
677 /* dumpraw if asked for */
678 if (options.dump_raw)
679 dumpEbbsToFileExt(".dumpdflow",ebbs,count);
681 /* global common subexpression elimination */
682 if ( optimize.global_cse ) {
683 change += cseAllBlocks(ebbs,saveCount);
684 if (options.dump_gcse)
685 dumpEbbsToFileExt(".dumpgcse",ebbs,saveCount);
688 kchange = killDeadCode (ebbs, saveCount);
690 if (options.dump_kill)
691 dumpEbbsToFileExt(".dumpdeadcode",ebbs,count);
693 /* do loop optimizations */
694 change += (lchange = loopOptimizations (loops,ebbs,count));
695 if (options.dump_loop)
696 dumpEbbsToFileExt(".dumploop",ebbs,count);
698 /* recompute the data flow and apply global cse again
699 if loops optimizations or dead code caused a change:
700 loops will brings out of the loop which then may be
701 available for use in the later blocks: dead code
702 elimination could potentially disconnect some blocks
703 conditional flow may be efected so we need to apply
704 subexpression once more */
705 if ( lchange || kchange ) {
707 computeDataFlow (ebbs,saveCount);
708 change += cseAllBlocks(ebbs,saveCount);
709 if (options.dump_loop)
710 dumpEbbsToFileExt(".dumploopg",ebbs,count);
712 /* if loop optimizations caused a change then do
713 dead code elimination once more : this will
714 get rid of the extra assignments to the induction
715 variables created during loop optimizations */
716 killDeadCode (ebbs, saveCount);
718 if (options.dump_loop)
719 dumpEbbsToFileExt(".dumploopd",ebbs,count);
724 /* sort it back by block number */
725 qsort (ebbs,saveCount,sizeof(eBBlock *),bbNumCompare);
727 /* if cyclomatic info requested then print it */
728 if (options.cyclomatic)
729 printCyclomatic(ebbs,saveCount);
732 /* convert operations with support routines
733 written in C to function calls : Iam doing
734 this at this point since I want all the
735 operations to be as they are for optimzations */
736 convertToFcall (ebbs,count);
739 /* compute the live ranges */
740 computeLiveRanges (ebbs,count);
742 if (options.dump_range)
743 dumpEbbsToFileExt(".dumprange",ebbs,count);
745 /* allocate registers & generate code */
746 port->assignRegisters(ebbs,count);
748 /* throw away blocks */
749 setToNull ((void **)&graphEdges);
757 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */