git.gag.com Git - fw/sdcc/blob - src/SDCCopt.c

   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
   7
   8              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
   9
  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
  13    later version.
  14
  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.
  19
  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.
  23
  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 -------------------------------------------------------------------------*/
  28
  29 #include "common.h"
  30
  31 /*-----------------------------------------------------------------*/
  32 /* global variables */
  33 int cseDefNum = 0;
  34
  35 char flowChanged = 0;
  36
  37
  38 /*-----------------------------------------------------------------*/
  39 /* printSymName - prints the symbol names                          */
  40 /*-----------------------------------------------------------------*/
  41 int
  42 printSymName (void *vsym)
  43 {
  44   symbol *sym = vsym;
  45   fprintf (stdout, " %s ", sym->name);
  46   return 0;
  47 }
  48
  49 /*-----------------------------------------------------------------*/
  50 /* cnvToFcall - does the actual conversion to function call        */
  51 /*-----------------------------------------------------------------*/
  52 static void
  53 cnvToFcall (iCode * ic, eBBlock * ebp)
  54 {
  55   iCode *ip;
  56   iCode *newic;
  57   operand *left;
  58   operand *right;
  59   symbol *func = NULL;
  60   int lineno = ic->lineno;
  61   int bytesPushed=0;
  62
  63   ip = ic->next;                /* insertion point */
  64   /* remove it from the iCode */
  65   remiCodeFromeBBlock (ebp, ic);
  66
  67   left = IC_LEFT (ic);
  68   right = IC_RIGHT (ic);
  69
  70   switch (ic->op)
  71     {
  72     case '+':
  73       func = __fsadd;
  74       break;
  75     case '-':
  76       func = __fssub;
  77       break;
  78     case '/':
  79       func = __fsdiv;
  80       break;
  81     case '*':
  82       func = __fsmul;
  83       break;
  84     case EQ_OP:
  85       func = __fseq;
  86       break;
  87     case NE_OP:
  88       func = __fsneq;
  89       break;
  90     case '<':
  91       func = __fslt;
  92       break;
  93     case '>':
  94       func = __fsgt;
  95       break;
  96     case LE_OP:
  97       func = __fslteq;
  98       break;
  99     case GE_OP:
 100       func = __fsgteq;
 101       break;
 102     }
 103
 104   /* if float support routines NOT compiled as reentrant */
 105   if (!options.float_rent)
 106     {
 107
 108       /* first one */
 109       if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 110         {
 111           newic = newiCode (SEND, IC_LEFT (ic), NULL);
 112           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 113         }
 114       else
 115         {
 116           newic = newiCode ('=', NULL, IC_LEFT (ic));
 117           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 118         }
 119
 120       addiCodeToeBBlock (ebp, newic, ip);
 121       newic->lineno = lineno;
 122
 123       /* second one */
 124       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
 125         {
 126           newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 127           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 128         }
 129       else
 130         {
 131           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 132           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
 133         }
 134       addiCodeToeBBlock (ebp, newic, ip);
 135       newic->lineno = lineno;
 136
 137     }
 138   else
 139     {
 140
 141       /* push right */
 142       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
 143         {
 144           newic = newiCode (SEND, right, NULL);
 145           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 146         }
 147       else
 148         {
 149           newic = newiCode (IPUSH, right, NULL);
 150           newic->parmPush = 1;
 151           //bytesPushed+=4;
 152           bytesPushed += getSize(operandType(right));
 153         }
 154
 155       addiCodeToeBBlock (ebp, newic, ip);
 156       newic->lineno = lineno;
 157
 158       /* insert push left */
 159       if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 160         {
 161           newic = newiCode (SEND, left, NULL);
 162           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 163         }
 164       else
 165         {
 166           newic = newiCode (IPUSH, left, NULL);
 167           newic->parmPush = 1;
 168           //bytesPushed+=4;
 169           bytesPushed += getSize(operandType(left));
 170         }
 171       addiCodeToeBBlock (ebp, newic, ip);
 172       newic->lineno = lineno;
 173     }
 174   /* insert the call */
 175   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 176   IC_RESULT (newic) = IC_RESULT (ic);
 177   newic->lineno = lineno;
 178   newic->parmBytes+=bytesPushed;
 179
 180   if(TARGET_IS_PIC16) {
 181         /* normally these functions aren't marked external, so we can use their
 182          * _extern field to marked as already added to symbol table */
 183
 184         if(!SPEC_EXTR(func->etype)) {
 185             memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
 186
 187                 SPEC_EXTR(func->etype) = 1;
 188                 seg = SPEC_OCLS( func->etype );
 189                 addSet(&seg->syms, func);
 190         }
 191   }
 192
 193   addiCodeToeBBlock (ebp, newic, ip);
 194 }
 195
 196 /*-----------------------------------------------------------------*/
 197 /* cnvToFloatCast - converts casts to floats to function calls     */
 198 /*-----------------------------------------------------------------*/
 199 static void
 200 cnvToFloatCast (iCode * ic, eBBlock * ebp)
 201 {
 202   iCode *ip, *newic;
 203   symbol *func = NULL;
 204   sym_link *type = operandType (IC_RIGHT (ic));
 205   int linenno = ic->lineno;
 206   int bwd, su;
 207   int bytesPushed=0;
 208
 209   ip = ic->next;
 210   /* remove it from the iCode */
 211   remiCodeFromeBBlock (ebp, ic);
 212   /* depending on the type */
 213   for (bwd = 0; bwd < 3; bwd++)
 214     {
 215       for (su = 0; su < 2; su++)
 216         {
 217           if (compareType (type, __multypes[bwd][su]) == 1)
 218             {
 219               func = __conv[0][bwd][su];
 220               goto found;
 221             }
 222         }
 223     }
 224   assert (0);
 225 found:
 226
 227   /* if float support routines NOT compiled as reentrant */
 228   if (!options.float_rent)
 229     {
 230       /* first one */
 231         if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 232             {
 233                 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 234                 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 235             }
 236       else
 237         {
 238           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 239           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 240         }
 241       addiCodeToeBBlock (ebp, newic, ip);
 242       newic->lineno = linenno;
 243
 244     }
 245   else
 246     {
 247       /* push the left */
 248         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 249             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 250             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 251         }
 252       else
 253         {
 254           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 255           newic->parmPush = 1;
 256           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 257         }
 258       addiCodeToeBBlock (ebp, newic, ip);
 259       newic->lineno = linenno;
 260
 261     }
 262
 263   /* make the call */
 264   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 265   IC_RESULT (newic) = IC_RESULT (ic);
 266   newic->parmBytes+=bytesPushed;
 267
 268   if(TARGET_IS_PIC16) {
 269         /* normally these functions aren't marked external, so we can use their
 270          * _extern field to marked as already added to symbol table */
 271
 272         if(!SPEC_EXTR(func->etype)) {
 273             memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
 274
 275                 SPEC_EXTR(func->etype) = 1;
 276                 seg = SPEC_OCLS( func->etype );
 277                 addSet(&seg->syms, func);
 278         }
 279   }
 280
 281   addiCodeToeBBlock (ebp, newic, ip);
 282   newic->lineno = linenno;
 283 }
 284
 285 /*-----------------------------------------------------------------*/
 286 /* cnvFromFloatCast - converts casts From floats to function calls */
 287 /*-----------------------------------------------------------------*/
 288 static void
 289 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
 290 {
 291   iCode *ip, *newic;
 292   symbol *func = NULL;
 293   sym_link *type = operandType (IC_LEFT (ic));
 294   int lineno = ic->lineno;
 295   int bwd, su;
 296   int bytesPushed=0;
 297
 298   ip = ic->next;
 299   /* remove it from the iCode */
 300   remiCodeFromeBBlock (ebp, ic);
 301
 302   /* depending on the type */
 303   for (bwd = 0; bwd < 3; bwd++)
 304     {
 305       for (su = 0; su < 2; su++)
 306         {
 307           if (compareType (type, __multypes[bwd][su]) == 1)
 308             {
 309               func = __conv[1][bwd][su];
 310               goto found;
 311             }
 312         }
 313     }
 314   assert (0);
 315 found:
 316
 317   /* if float support routines NOT compiled as reentrant */
 318   if (!options.float_rent)
 319     {
 320       /* first one */
 321         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 322             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 323             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 324         }
 325       else
 326         {
 327           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 328           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 329         }
 330       addiCodeToeBBlock (ebp, newic, ip);
 331       newic->lineno = lineno;
 332
 333     }
 334   else
 335     {
 336
 337       /* push the left */
 338         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 339             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 340             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 341         }
 342       else
 343         {
 344           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 345           newic->parmPush = 1;
 346           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 347         }
 348       addiCodeToeBBlock (ebp, newic, ip);
 349       newic->lineno = lineno;
 350
 351     }
 352
 353   /* make the call */
 354   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 355   IC_RESULT (newic) = IC_RESULT (ic);
 356   newic->parmBytes+=bytesPushed;
 357
 358   if(TARGET_IS_PIC16) {
 359         /* normally these functions aren't marked external, so we can use their
 360          * _extern field to marked as already added to symbol table */
 361
 362         if(!SPEC_EXTR(func->etype)) {
 363             memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
 364
 365                 SPEC_EXTR(func->etype) = 1;
 366                 seg = SPEC_OCLS( func->etype );
 367                 addSet(&seg->syms, func);
 368         }
 369   }
 370
 371   addiCodeToeBBlock (ebp, newic, ip);
 372   newic->lineno = lineno;
 373 }
 374
 375 extern operand *geniCodeRValue (operand *, bool);
 376
 377 /*-----------------------------------------------------------------*/
 378 /* convilong - converts int or long mults or divs to fcalls        */
 379 /*-----------------------------------------------------------------*/
 380 static void
 381 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
 382 {
 383   symbol *func = NULL;
 384   iCode *ip = ic->next;
 385   iCode *newic;
 386   int lineno = ic->lineno;
 387   int bwd;
 388   int su;
 389   int bytesPushed=0;
 390
 391   // Easy special case which avoids function call: modulo by a literal power
 392   // of two can be replaced by a bitwise AND.
 393   if (op == '%' && isOperandLiteral(IC_RIGHT(ic)))
 394   {
 395       unsigned litVal = (unsigned)(operandLitValue(IC_RIGHT(ic)));
 396
 397       // See if literal value is a power of 2.
 398       while (litVal && !(litVal & 1))
 399       {
 400           litVal >>= 1;
 401       }
 402       if (litVal)
 403       {
 404           // discard first high bit set.
 405           litVal >>= 1;
 406       }
 407
 408       if (!litVal)
 409       {
 410           ic->op = BITWISEAND;
 411           IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
 412           return;
 413       }
 414   }
 415
 416   remiCodeFromeBBlock (ebp, ic);
 417
 418
 419   /* depending on the type */
 420   for (bwd = 0; bwd < 3; bwd++)
 421     {
 422       for (su = 0; su < 2; su++)
 423         {
 424           if (compareType (type, __multypes[bwd][su]) == 1)
 425             {
 426               if (op == '*')
 427                 func = __muldiv[0][bwd][su];
 428               else if (op == '/')
 429                 func = __muldiv[1][bwd][su];
 430               else if (op == '%')
 431                 func = __muldiv[2][bwd][su];
 432               else if (op == RRC)
 433                 func = __rlrr[1][bwd][su];
 434               else if (op == RLC)
 435                 func = __rlrr[0][bwd][su];
 436               else if (op == RIGHT_OP)
 437                 func = __rlrr[1][bwd][su];
 438               else if (op == LEFT_OP)
 439                 func = __rlrr[0][bwd][su];
 440               else
 441                 assert (0);
 442               goto found;
 443             }
 444         }
 445     }
 446   assert (0);
 447 found:
 448   /* if int & long support routines NOT compiled as reentrant */
 449   if (!options.intlong_rent)
 450     {
 451       /* first one */
 452         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 453             newic = newiCode (SEND, IC_LEFT (ic), NULL);
 454             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 455         }
 456       else
 457         {
 458           newic = newiCode ('=', NULL, IC_LEFT (ic));
 459           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 460         }
 461       addiCodeToeBBlock (ebp, newic, ip);
 462       newic->lineno = lineno;
 463
 464       /* second one */
 465       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
 466           newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 467           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 468       }
 469       else
 470         {
 471           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 472           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
 473         }
 474       addiCodeToeBBlock (ebp, newic, ip);
 475       newic->lineno = lineno;
 476
 477     }
 478   else
 479     {
 480       /* compiled as reentrant then push */
 481       /* push right */
 482       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
 483         {
 484           newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 485           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 486         }
 487       else
 488         {
 489           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 490           newic->parmPush = 1;
 491
 492           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 493         }
 494       addiCodeToeBBlock (ebp, newic, ip);
 495       newic->lineno = lineno;
 496
 497       /* insert push left */
 498       if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 499         {
 500           newic = newiCode (SEND, IC_LEFT (ic), NULL);
 501           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 502         }
 503       else
 504         {
 505           newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
 506           newic->parmPush = 1;
 507
 508           bytesPushed += getSize(operandType(IC_LEFT(ic)));
 509         }
 510       addiCodeToeBBlock (ebp, newic, ip);
 511       newic->lineno = lineno;
 512
 513     }
 514
 515   /* for the result */
 516   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 517   IC_RESULT (newic) = IC_RESULT (ic);
 518   newic->lineno = lineno;
 519   newic->parmBytes+=bytesPushed; // to clear the stack after the call
 520
 521   if(TARGET_IS_PIC16) {
 522         /* normally these functions aren't marked external, so we can use their
 523          * _extern field to marked as already added to symbol table */
 524
 525         if(!SPEC_EXTR(func->etype)) {
 526             memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
 527
 528                 SPEC_EXTR(func->etype) = 1;
 529                 seg = SPEC_OCLS( func->etype );
 530                 addSet(&seg->syms, func);
 531         }
 532   }
 533
 534   addiCodeToeBBlock (ebp, newic, ip);
 535 }
 536
 537 /*-----------------------------------------------------------------*/
 538 /* convertToFcall - converts some operations to fcalls             */
 539 /*-----------------------------------------------------------------*/
 540 static void
 541 convertToFcall (eBBlock ** ebbs, int count)
 542 {
 543   int i;
 544
 545   /* for all blocks do */
 546   for (i = 0; i < count; i++)
 547     {
 548       iCode *ic;
 549
 550       /* for all instructions in the block do */
 551       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 552         {
 553
 554           /* floating point operations are
 555              converted to function calls */
 556           if ((IS_CONDITIONAL (ic) ||
 557                IS_ARITHMETIC_OP (ic)) &&
 558               (IS_FLOAT (operandType (IC_RIGHT (ic)))))
 559             {
 560
 561               cnvToFcall (ic, ebbs[i]);
 562             }
 563
 564           /* casting is a little different */
 565           if (ic->op == CAST)
 566             {
 567               if (IS_FLOAT (operandType (IC_RIGHT (ic))))
 568                 cnvFromFloatCast (ic, ebbs[i]);
 569               else if (IS_FLOAT (operandType (IC_LEFT (ic))))
 570                 cnvToFloatCast (ic, ebbs[i]);
 571             }
 572
 573           /* if long / int mult or divide or mod */
 574           if (ic->op == '*' || ic->op == '/' || ic->op == '%')
 575             {
 576               sym_link *leftType = operandType (IC_LEFT (ic));
 577
 578               if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
 579                 {
 580                   sym_link *rightType = operandType (IC_RIGHT (ic));
 581
 582                   if (port->hasNativeMulFor != NULL &&
 583                       port->hasNativeMulFor (ic, leftType, rightType))
 584                     {
 585                       /* Leave as native */
 586                     }
 587                   else
 588                     {
 589                       convilong (ic, ebbs[i], leftType, ic->op);
 590                     }
 591                 }
 592             }
 593
 594           if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
 595             {
 596               sym_link *type = operandType (IC_LEFT (ic));
 597
 598               if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
 599                 {
 600                   convilong (ic, ebbs[i], type, ic->op);
 601                 }
 602             }
 603         }
 604     }
 605 }
 606
 607 /*-----------------------------------------------------------------*/
 608 /* isLocalWithoutDef - return 1 if sym might be used without a     */
 609 /*                     defining iCode                              */
 610 /*-----------------------------------------------------------------*/
 611 static int
 612 isLocalWithoutDef (symbol * sym)
 613 {
 614   if (!sym->level)
 615     return 0;
 616
 617   if (IS_STATIC (sym->etype))
 618     return 0;
 619
 620   if (IS_VOLATILE (sym->type))
 621     return 0;
 622
 623   if (sym->_isparm)
 624     return 0;
 625
 626   if (IS_AGGREGATE (sym->type))
 627     return 0;
 628
 629   if (sym->addrtaken)
 630     return 0;
 631
 632   return !sym->defs;
 633 }
 634
 635 /*-----------------------------------------------------------------*/
 636 /* replaceRegEqv - replace all local variables with their reqv     */
 637 /*-----------------------------------------------------------------*/
 638 static void
 639 replaceRegEqv (eBBlock ** ebbs, int count)
 640 {
 641   int i;
 642
 643   /* Update the symbols' def bitvector so we know if there is   */
 644   /* a defining iCode or not. Only replace a local variable     */
 645   /* with its register equivalent if there is a defining iCode; */
 646   /* otherwise, the port's register allocater may choke.        */
 647   cseAllBlocks (ebbs, count, TRUE);
 648
 649   for (i = 0; i < count; i++)
 650     {
 651
 652       iCode *ic;
 653
 654       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 655         {
 656
 657           if (SKIP_IC2 (ic))
 658             continue;
 659
 660           if (ic->op == IFX)
 661             {
 662               if (IC_COND (ic) &&
 663                   IS_TRUE_SYMOP (IC_COND (ic)) &&
 664                   isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
 665                 {
 666                   werrorfl (ic->filename, ic->lineno,
 667                           W_LOCAL_NOINIT,
 668                           OP_SYMBOL (IC_COND (ic))->name);
 669                   OP_REQV (IC_COND (ic)) = NULL;
 670                   OP_SYMBOL (IC_COND (ic))->allocreq = 1;
 671                 }
 672
 673               if (IS_TRUE_SYMOP (IC_COND (ic)) &&
 674                   OP_REQV (IC_COND (ic)))
 675                 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
 676                                              OP_SYMBOL (IC_COND (ic))->defs,
 677                                             OP_SYMBOL (IC_COND (ic))->uses);
 678
 679               continue;
 680             }
 681
 682
 683           if (ic->op == JUMPTABLE)
 684             {
 685               if (IC_JTCOND (ic) &&
 686                   IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
 687                   isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
 688                 {
 689                   werrorfl (ic->filename, ic->lineno,
 690                           W_LOCAL_NOINIT,
 691                           OP_SYMBOL (IC_JTCOND (ic))->name);
 692                   OP_REQV (IC_JTCOND (ic)) = NULL;
 693                   OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
 694                 }
 695
 696               if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
 697                   OP_REQV (IC_JTCOND (ic)))
 698                 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
 699                                            OP_SYMBOL (IC_JTCOND (ic))->defs,
 700                                           OP_SYMBOL (IC_JTCOND (ic))->uses);
 701               continue;
 702             }
 703
 704           if (ic->op == RECEIVE)
 705             {
 706               if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
 707                 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
 708             }
 709
 710           /* general case */
 711           if (IC_RESULT (ic) &&
 712               IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 713               OP_REQV (IC_RESULT (ic)))
 714             {
 715               if (POINTER_SET (ic))
 716                 {
 717                   IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
 718                                            OP_SYMBOL (IC_RESULT (ic))->defs,
 719                                           OP_SYMBOL (IC_RESULT (ic))->uses);
 720                   IC_RESULT (ic)->isaddr = 1;
 721                 }
 722               else
 723                 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
 724                                            OP_SYMBOL (IC_RESULT (ic))->defs,
 725                                           OP_SYMBOL (IC_RESULT (ic))->uses);
 726             }
 727
 728           if (IC_RIGHT (ic) &&
 729               IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
 730               isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
 731             {
 732               werrorfl (ic->filename, ic->lineno,
 733                         W_LOCAL_NOINIT,
 734                         OP_SYMBOL (IC_RIGHT (ic))->name);
 735               OP_REQV (IC_RIGHT (ic)) = NULL;
 736               OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
 737             }
 738
 739           if (IC_RIGHT (ic) &&
 740               IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
 741               OP_REQV (IC_RIGHT (ic)))
 742             {
 743               IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
 744                                             OP_SYMBOL (IC_RIGHT (ic))->defs,
 745                                            OP_SYMBOL (IC_RIGHT (ic))->uses);
 746               IC_RIGHT (ic)->isaddr = 0;
 747             }
 748
 749           if (IC_LEFT (ic) &&
 750               IS_TRUE_SYMOP (IC_LEFT (ic)) &&
 751               isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
 752             {
 753               werrorfl (ic->filename, ic->lineno,
 754                         W_LOCAL_NOINIT,
 755                         OP_SYMBOL (IC_LEFT (ic))->name);
 756               OP_REQV (IC_LEFT (ic)) = NULL;
 757               OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
 758             }
 759
 760           if (IC_LEFT (ic) &&
 761               IS_TRUE_SYMOP (IC_LEFT (ic)) &&
 762               OP_REQV (IC_LEFT (ic)))
 763             {
 764               IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
 765                                              OP_SYMBOL (IC_LEFT (ic))->defs,
 766                                              OP_SYMBOL (IC_LEFT (ic))->uses);
 767               IC_LEFT (ic)->isaddr = 0;
 768             }
 769         }
 770     }
 771 }
 772
 773 /*-----------------------------------------------------------------*/
 774 /* killDeadCode - eliminates dead assignments                      */
 775 /*-----------------------------------------------------------------*/
 776 int
 777 killDeadCode (eBBlock ** ebbs, int count)
 778 {
 779   int change = 1;
 780   int gchange = 0;
 781   int i = 0;
 782
 783
 784   /* basic algorithm :-                                          */
 785   /* first the exclusion rules :-                                */
 786   /*  1. if result is a global or volatile then skip             */
 787   /*  2. if assignment and result is a temp & isaddr  then skip  */
 788   /*     since this means array & pointer access, will be taken  */
 789   /*     care of by alias analysis.                              */
 790   /*  3. if the result is used in the remainder of the block skip */
 791   /*  4. if this definition does not reach the end of the block  */
 792   /*     i.e. the result is not present in the outExprs then KILL */
 793   /*  5. if it reaches the end of block & is used by some success */
 794   /*     or then skip                                            */
 795   /*     else            KILL                                    */
 796   /* this whole process is carried on iteratively till no change */
 797   while (1)
 798     {
 799
 800       change = 0;
 801       /* for all blocks do */
 802       for (i = 0; i < count; i++)
 803         {
 804           iCode *ic;
 805
 806           /* for all instructions in the block do */
 807           for (ic = ebbs[i]->sch; ic; ic = ic->next)
 808             {
 809               int kill, j;
 810               kill = 0;
 811
 812               if (SKIP_IC (ic) ||
 813                   ic->op == IFX ||
 814                   ic->op == RETURN ||
 815                   ic->op == DUMMY_READ_VOLATILE ||
 816                   ic->op == CRITICAL ||
 817                   ic->op == ENDCRITICAL)
 818                 continue;
 819
 820               /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
 821               /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are  */
 822               /* valid. */
 823
 824               /* if the result is volatile then continue */
 825               if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
 826                 continue;
 827
 828               /* if the result is a temp & isaddr then skip */
 829               if (IC_RESULT (ic) && POINTER_SET (ic))
 830                 continue;
 831
 832               if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
 833                 continue;
 834
 835               /* if the result is used in the remainder of the */
 836               /* block then skip */
 837               if (usedInRemaining (IC_RESULT (ic), ic->next))
 838                 continue;
 839
 840               /* does this definition reach the end of the block
 841                  or the usage is zero then we can kill */
 842               if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
 843                 kill = 1;       /* if not we can kill it */
 844               else
 845                 {
 846                   /* if this is a global variable or function parameter */
 847                   /* we cannot kill anyway             */
 848                   if (isOperandGlobal (IC_RESULT (ic)) ||
 849                       (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
 850                        !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
 851                     continue;
 852
 853                   /* if we are sure there are no usages */
 854                   if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
 855                     {
 856                       kill = 1;
 857                       goto kill;
 858                     }
 859
 860                   /* reset visited flag */
 861                   for (j = 0; j < count; ebbs[j++]->visited = 0);
 862
 863                   /* find out if this definition is alive */
 864                   if (applyToSet (ebbs[i]->succList,
 865                                   isDefAlive,
 866                                   ic))
 867                     continue;
 868
 869                   kill = 1;
 870                 }
 871
 872             kill:
 873               /* kill this one if required */
 874               if (kill)
 875                 {
 876                   bool volLeft = IS_SYMOP (IC_LEFT (ic))
 877                                  && isOperandVolatile (IC_LEFT (ic), FALSE);
 878                   bool volRight = IS_SYMOP (IC_RIGHT (ic))
 879                                   && isOperandVolatile (IC_RIGHT (ic), FALSE);
 880
 881                   /* a dead address-of operation should die, even if volatile */
 882                   if (ic->op == ADDRESS_OF)
 883                     volLeft = FALSE;
 884
 885                   if (ic->next && ic->seqPoint == ic->next->seqPoint
 886                       && (ic->next->op == '+' || ic->next->op == '-'))
 887                     {
 888                       if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
 889                           || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
 890                         volLeft = FALSE;
 891                       if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
 892                           || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
 893                         volRight = FALSE;
 894                     }
 895
 896                   change = 1;
 897                   gchange++;
 898
 899                   /* now delete from defUseSet */
 900                   deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
 901                   bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
 902
 903                   /* and defset of the block */
 904                   bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 905
 906                   /* delete the result */
 907                   IC_RESULT (ic) = NULL;
 908
 909                   if (volLeft || volRight)
 910                     {
 911                       /* something is volatile, so keep the iCode */
 912                       /* and change the operator instead */
 913                       ic->op = DUMMY_READ_VOLATILE;
 914
 915                       /* keep only the volatile operands */
 916                       if (!volLeft)
 917                         IC_LEFT (ic) = NULL;
 918                       if (!volRight)
 919                         IC_RIGHT (ic) = NULL;
 920                     }
 921                   else
 922                     {
 923                       /* nothing is volatile, eliminate the iCode */
 924                       remiCodeFromeBBlock (ebbs[i], ic);
 925
 926                       /* for the left & right remove the usage */
 927                       if (IS_SYMOP (IC_LEFT (ic)))
 928                         bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
 929
 930                       if (IS_SYMOP (IC_RIGHT (ic)))
 931                         bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
 932                     }
 933                 }
 934
 935             }                   /* end of all instructions */
 936
 937           if (!ebbs[i]->sch && !ebbs[i]->noPath)
 938             disconBBlock (ebbs[i], ebbs, count);
 939
 940         }                       /* end of for all blocks */
 941
 942       if (!change)
 943         break;
 944     }                           /* end of while(1) */
 945
 946   return gchange;
 947 }
 948
 949 /*-----------------------------------------------------------------*/
 950 /* printCyclomatic - prints the cyclomatic information             */
 951 /*-----------------------------------------------------------------*/
 952 static void
 953 printCyclomatic (eBBlock ** ebbs, int count)
 954 {
 955   int nEdges = elementsInSet (graphEdges);
 956   int i, nNodes = 0;
 957
 958   for (i = 0; i < count; i++)
 959     nNodes += (!ebbs[i]->noPath);
 960
 961   /* print the information */
 962   werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
 963 }
 964
 965 /*-----------------------------------------------------------------*/
 966 /* discardDeadParamReceives - remove any RECEIVE opcodes which     */
 967 /* refer to dead variables.                                        */
 968 /*-----------------------------------------------------------------*/
 969 static void
 970 discardDeadParamReceives (eBBlock ** ebbs, int count)
 971 {
 972   int i;
 973   iCode *ic;
 974   iCode dummyIcode;
 975
 976   for (i = 0; i < count; i++)
 977     {
 978       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 979         {
 980           if (ic->op == RECEIVE)
 981             {
 982               if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
 983                   && !OP_SYMBOL (IC_RESULT (ic))->used)
 984                 {
 985 #if 0
 986                   fprintf (stderr, "discarding dead receive for %s\n",
 987                            OP_SYMBOL (IC_RESULT (ic))->name);
 988 #endif
 989                   dummyIcode.next = ic->next;
 990                   remiCodeFromeBBlock (ebbs[i], ic);
 991                   ic = &dummyIcode;
 992                 }
 993             }
 994         }
 995     }
 996 }
 997
 998 /*-----------------------------------------------------------------*/
 999 /* optimizeCastCast - remove unneeded intermediate casts.          */
1000 /* Integer promotion may cast (un)signed char to int and then      */
1001 /* recast the int to (un)signed long. If the signedness of the     */
1002 /* char and long are the same, the cast can be safely performed in */
1003 /* a single step.                                                  */
1004 /*-----------------------------------------------------------------*/
1005 static void
1006 optimizeCastCast (eBBlock ** ebbs, int count)
1007 {
1008   int i;
1009   iCode *ic;
1010   iCode *uic;
1011   sym_link * type1;
1012   sym_link * type2;
1013   sym_link * type3;
1014   symbol * sym;
1015
1016   for (i = 0; i < count; i++)
1017     {
1018       for (ic = ebbs[i]->sch; ic; ic = ic->next)
1019         {
1020
1021           if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1022             {
1023               type1 = operandType (IC_RIGHT (ic));
1024               type2 = operandType (IC_RESULT (ic));
1025
1026               /* Look only for a cast from an integer type to an */
1027               /* integer type that has no loss of bits */
1028               if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1029                 continue;
1030               if (getSize (type2) < getSize (type1))
1031                 continue;
1032
1033               /* There must be only one use of this first result */
1034               if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1035                 continue;
1036
1037               /* This use must be a second cast */
1038               uic = hTabItemWithKey (iCodehTab,
1039                         bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1040               if (!uic || uic->op != CAST)
1041                 continue;
1042
1043               /* It must be a cast to another integer type that */
1044               /* has no loss of bits */
1045               type3 = operandType (IC_RESULT (uic));
1046               if (!IS_INTEGRAL (type3))
1047                  continue;
1048               if (getSize (type3) < getSize (type2))
1049                  continue;
1050
1051               /* The signedness between the first and last types */
1052               /* must match */
1053               if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1054                  continue;
1055
1056               /* Change the first cast to a simple assignment and */
1057               /* let the second cast do all the work */
1058               ic->op = '=';
1059               IC_LEFT (ic) = NULL;
1060               sym = OP_SYMBOL (IC_RESULT (ic));
1061               sym->type = copyLinkChain (type1);
1062               sym->etype = getSpec (sym->type);
1063             }
1064         }
1065     }
1066 }
1067
1068 /*-----------------------------------------------------------------*/
1069 /* eBBlockFromiCode - creates extended basic blocks from iCode     */
1070 /*                    will return an array of eBBlock pointers     */
1071 /*-----------------------------------------------------------------*/
1072 eBBlock **
1073 eBBlockFromiCode (iCode * ic)
1074 {
1075   eBBlock **ebbs = NULL;
1076   int count = 0;
1077   int saveCount = 0;
1078   int change = 1;
1079   int lchange = 0;
1080   int kchange = 0;
1081   hTab *loops;
1082
1083   /* if nothing passed then return nothing */
1084   if (!ic)
1085     return NULL;
1086
1087   count = 0;
1088   eBBNum = 0;
1089
1090   /* optimize the chain for labels & gotos
1091      this will eliminate redundant labels and
1092      will change jump to jumps by jumps */
1093   ic = iCodeLabelOptimize (ic);
1094
1095   /* break it down into basic blocks */
1096   ebbs = iCodeBreakDown (ic, &count);
1097   saveCount = count;
1098
1099   /* hash the iCode keys so that we can quickly index */
1100   /* them in the rest of the optimization steps */
1101   setToNull ((void *) &iCodehTab);
1102   iCodehTab = newHashTable (iCodeKey);
1103   hashiCodeKeys (ebbs, count);
1104
1105   /* compute the control flow */
1106   computeControlFlow (ebbs, count, 0);
1107
1108   /* dumpraw if asked for */
1109   if (options.dump_raw)
1110     dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
1111
1112   /* replace the local variables with their
1113      register equivalents : the liveRange computation
1114      along with the register allocation will determine
1115      if it finally stays in the registers */
1116   replaceRegEqv (ebbs, count);
1117
1118   /* create loop regions */
1119   loops = createLoopRegions (ebbs, count);
1120
1121   /* dumpraw if asked for */
1122   if (options.dump_raw)
1123     dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
1124
1125   optimizeCastCast (ebbs, saveCount);
1126
1127   /* do common subexpression elimination for each block */
1128   change = cseAllBlocks (ebbs, saveCount, FALSE);
1129
1130   /* dumpraw if asked for */
1131   if (options.dump_raw)
1132     dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
1133
1134   /* compute the data flow */
1135   computeDataFlow (ebbs, saveCount);
1136
1137   /* dumpraw if asked for */
1138   if (options.dump_raw)
1139     dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
1140
1141   /* global common subexpression elimination  */
1142   if (optimize.global_cse)
1143     {
1144       change += cseAllBlocks (ebbs, saveCount, FALSE);
1145       if (options.dump_gcse)
1146         dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
1147     }
1148   else
1149     {
1150       // compute the dataflow only
1151       assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
1152     }
1153   /* kill dead code */
1154   kchange = killDeadCode (ebbs, saveCount);
1155
1156   if (options.dump_kill)
1157     dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
1158
1159   /* do loop optimizations */
1160   change += (lchange = loopOptimizations (loops, ebbs, count));
1161   if (options.dump_loop)
1162     dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
1163
1164   /* recompute the data flow and apply global cse again
1165      if loops optimizations or dead code caused a change:
1166      loops will brings out of the loop which then may be
1167      available for use in the later blocks: dead code
1168      elimination could potentially disconnect some blocks
1169      conditional flow may be efected so we need to apply
1170      subexpression once more */
1171   if (lchange || kchange)
1172     {
1173       computeDataFlow (ebbs, saveCount);
1174       change += cseAllBlocks (ebbs, saveCount, FALSE);
1175       if (options.dump_loop)
1176         dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
1177
1178       /* if loop optimizations caused a change then do
1179          dead code elimination once more : this will
1180          get rid of the extra assignments to the induction
1181          variables created during loop optimizations */
1182       killDeadCode (ebbs, saveCount);
1183
1184       if (options.dump_loop)
1185         dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1186
1187     }
1188
1189   /* sort it back by block number */
1190   qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1191
1192   if (!options.lessPedantic) {
1193     // this is a good place to check missing return values
1194     if (currFunc) {
1195       // the user is on his own with naked functions...
1196       if (!IS_VOID(currFunc->etype)
1197        && !FUNC_ISNAKED(currFunc->type)) {
1198         eBBlock *bp;
1199         // make sure all predecessors of the last block end in a return
1200         for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1201              bp;
1202              bp=setNextItem(ebbs[saveCount-1]->predList)) {
1203           if (bp->ech->op != RETURN) {
1204             werrorfl (bp->ech->filename, bp->ech->lineno,
1205                       W_VOID_FUNC, currFunc->name);
1206           }
1207         }
1208       }
1209     }
1210   }
1211
1212   /* if cyclomatic info requested then print it */
1213   if (options.cyclomatic)
1214     printCyclomatic (ebbs, saveCount);
1215
1216   /* convert operations with support routines
1217      written in C to function calls : Iam doing
1218      this at this point since I want all the
1219      operations to be as they are for optimzations */
1220   convertToFcall (ebbs, count);
1221
1222   /* compute the live ranges */
1223   computeLiveRanges (ebbs, count);
1224
1225   if (options.dump_range)
1226     dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1227
1228   /* Now that we have the live ranges, discard parameter
1229    * receives for unused parameters.
1230    */
1231   discardDeadParamReceives (ebbs, count);
1232
1233   /* allocate registers & generate code */
1234   port->assignRegisters (ebbs, count);
1235
1236   /* throw away blocks */
1237   setToNull ((void *) &graphEdges);
1238   ebbs = NULL;
1239
1240   return NULL;
1241 }
1242
1243
1244 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */