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 /* findReqv - search for a register equivalent                     */
 775 /*-----------------------------------------------------------------*/
 776 operand *
 777 findReqv (symbol * prereqv, eBBlock ** ebbs, int count)
 778 {
 779   int i;
 780   iCode * ic;
 781
 782   /* for all blocks do */
 783   for (i=0; i<count; i++)
 784     {
 785       /* for all instructions in the block do */
 786       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 787         {
 788           if (ic->op == IFX)
 789             {
 790               if (IS_ITEMP (IC_COND (ic))
 791                   && OP_SYMBOL (IC_COND (ic))->prereqv == prereqv)
 792                 return IC_COND (ic);
 793             }
 794           else if (ic->op == JUMPTABLE)
 795             {
 796               if (IS_ITEMP (IC_JTCOND (ic))
 797                   && OP_SYMBOL (IC_JTCOND (ic))->prereqv == prereqv)
 798                 return IC_JTCOND (ic);
 799             }
 800           else
 801             {
 802               if (IS_ITEMP (IC_LEFT (ic))
 803                   && OP_SYMBOL (IC_LEFT (ic))->prereqv == prereqv)
 804                 return IC_LEFT (ic);
 805               if (IS_ITEMP (IC_RIGHT (ic))
 806                   && OP_SYMBOL (IC_RIGHT (ic))->prereqv == prereqv)
 807                 return IC_RIGHT (ic);
 808               if (IS_ITEMP (IC_RESULT (ic))
 809                   && OP_SYMBOL (IC_RESULT (ic))->prereqv == prereqv)
 810                 return IC_RESULT (ic);
 811             }
 812         }
 813     }
 814
 815   return NULL;
 816 }
 817
 818 /*-----------------------------------------------------------------*/
 819 /* killDeadCode - eliminates dead assignments                      */
 820 /*-----------------------------------------------------------------*/
 821 int
 822 killDeadCode (eBBlock ** ebbs, int count)
 823 {
 824   int change = 1;
 825   int gchange = 0;
 826   int i = 0;
 827
 828
 829   /* basic algorithm :-                                          */
 830   /* first the exclusion rules :-                                */
 831   /*  1. if result is a global or volatile then skip             */
 832   /*  2. if assignment and result is a temp & isaddr  then skip  */
 833   /*     since this means array & pointer access, will be taken  */
 834   /*     care of by alias analysis.                              */
 835   /*  3. if the result is used in the remainder of the block skip */
 836   /*  4. if this definition does not reach the end of the block  */
 837   /*     i.e. the result is not present in the outExprs then KILL */
 838   /*  5. if it reaches the end of block & is used by some success */
 839   /*     or then skip                                            */
 840   /*     else            KILL                                    */
 841   /* this whole process is carried on iteratively till no change */
 842   while (1)
 843     {
 844
 845       change = 0;
 846       /* for all blocks do */
 847       for (i = 0; i < count; i++)
 848         {
 849           iCode *ic;
 850
 851           /* for all instructions in the block do */
 852           for (ic = ebbs[i]->sch; ic; ic = ic->next)
 853             {
 854               int kill, j;
 855               kill = 0;
 856
 857               if (SKIP_IC (ic) ||
 858                   ic->op == IFX ||
 859                   ic->op == RETURN ||
 860                   ic->op == DUMMY_READ_VOLATILE ||
 861                   ic->op == CRITICAL ||
 862                   ic->op == ENDCRITICAL)
 863                 continue;
 864
 865               /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
 866               /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are  */
 867               /* valid. */
 868
 869               /* if the result is volatile then continue */
 870               if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
 871                 continue;
 872
 873               /* if the result is a temp & isaddr then skip */
 874               if (IC_RESULT (ic) && POINTER_SET (ic))
 875                 continue;
 876
 877               if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
 878                 continue;
 879
 880               /* if the result is used in the remainder of the */
 881               /* block then skip */
 882               if (usedInRemaining (IC_RESULT (ic), ic->next))
 883                 continue;
 884
 885               /* does this definition reach the end of the block
 886                  or the usage is zero then we can kill */
 887               if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
 888                 kill = 1;       /* if not we can kill it */
 889               else
 890                 {
 891                   /* if this is a global variable or function parameter */
 892                   /* we cannot kill anyway             */
 893                   if (isOperandGlobal (IC_RESULT (ic)) ||
 894                       (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
 895                        !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
 896                     continue;
 897
 898                   /* if we are sure there are no usages */
 899                   if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
 900                     {
 901                       kill = 1;
 902                       goto kill;
 903                     }
 904
 905                   /* reset visited flag */
 906                   for (j = 0; j < count; ebbs[j++]->visited = 0);
 907
 908                   /* find out if this definition is alive */
 909                   if (applyToSet (ebbs[i]->succList,
 910                                   isDefAlive,
 911                                   ic))
 912                     continue;
 913
 914                   kill = 1;
 915                 }
 916
 917             kill:
 918               /* kill this one if required */
 919               if (kill)
 920                 {
 921                   bool volLeft = IS_SYMOP (IC_LEFT (ic))
 922                                  && isOperandVolatile (IC_LEFT (ic), FALSE);
 923                   bool volRight = IS_SYMOP (IC_RIGHT (ic))
 924                                   && isOperandVolatile (IC_RIGHT (ic), FALSE);
 925
 926                   /* a dead address-of operation should die, even if volatile */
 927                   if (ic->op == ADDRESS_OF)
 928                     volLeft = FALSE;
 929
 930                   if (ic->next && ic->seqPoint == ic->next->seqPoint
 931                       && (ic->next->op == '+' || ic->next->op == '-'))
 932                     {
 933                       if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
 934                           || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
 935                         volLeft = FALSE;
 936                       if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
 937                           || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
 938                         volRight = FALSE;
 939                     }
 940
 941                   change = 1;
 942                   gchange++;
 943
 944                   /* now delete from defUseSet */
 945                   deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
 946                   bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
 947
 948                   /* and defset of the block */
 949                   bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 950
 951                   /* If this is the last of a register equivalent, */
 952                   /* look for a successor register equivalent. */
 953                   bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
 954                   if (IS_ITEMP (IC_RESULT (ic))
 955                       && OP_SYMBOL (IC_RESULT (ic))->isreqv
 956                       && bitVectIsZero (OP_DEFS (IC_RESULT (ic))))
 957                     {
 958                       symbol * resultsym = OP_SYMBOL (IC_RESULT (ic));
 959                       symbol * prereqv = resultsym->prereqv;
 960
 961                       if (OP_SYMBOL (prereqv->reqv) == resultsym)
 962                         {
 963                           operand * newreqv;
 964
 965                           IC_RESULT (ic) = NULL;
 966                           newreqv = findReqv (prereqv, ebbs, count);
 967                           if (newreqv)
 968                             {
 969                               prereqv->reqv = newreqv;
 970                             }
 971                         }
 972                     }
 973
 974                   /* delete the result */
 975                   IC_RESULT (ic) = NULL;
 976
 977                   if (volLeft || volRight)
 978                     {
 979                       /* something is volatile, so keep the iCode */
 980                       /* and change the operator instead */
 981                       ic->op = DUMMY_READ_VOLATILE;
 982
 983                       /* keep only the volatile operands */
 984                       if (!volLeft)
 985                         IC_LEFT (ic) = NULL;
 986                       if (!volRight)
 987                         IC_RIGHT (ic) = NULL;
 988                     }
 989                   else
 990                     {
 991                       /* nothing is volatile, eliminate the iCode */
 992                       remiCodeFromeBBlock (ebbs[i], ic);
 993
 994                       /* for the left & right remove the usage */
 995                       if (IS_SYMOP (IC_LEFT (ic)))
 996                         bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
 997
 998                       if (IS_SYMOP (IC_RIGHT (ic)))
 999                         bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
1000                     }
1001                 }
1002
1003             }                   /* end of all instructions */
1004
1005           if (!ebbs[i]->sch && !ebbs[i]->noPath)
1006             disconBBlock (ebbs[i], ebbs, count);
1007
1008         }                       /* end of for all blocks */
1009
1010       if (!change)
1011         break;
1012     }                           /* end of while(1) */
1013
1014   return gchange;
1015 }
1016
1017 /*-----------------------------------------------------------------*/
1018 /* printCyclomatic - prints the cyclomatic information             */
1019 /*-----------------------------------------------------------------*/
1020 static void
1021 printCyclomatic (eBBlock ** ebbs, int count)
1022 {
1023   int nEdges = elementsInSet (graphEdges);
1024   int i, nNodes = 0;
1025
1026   for (i = 0; i < count; i++)
1027     nNodes += (!ebbs[i]->noPath);
1028
1029   /* print the information */
1030   werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
1031 }
1032
1033 /*-----------------------------------------------------------------*/
1034 /* discardDeadParamReceives - remove any RECEIVE opcodes which     */
1035 /* refer to dead variables.                                        */
1036 /*-----------------------------------------------------------------*/
1037 static void
1038 discardDeadParamReceives (eBBlock ** ebbs, int count)
1039 {
1040   int i;
1041   iCode *ic;
1042   iCode dummyIcode;
1043
1044   for (i = 0; i < count; i++)
1045     {
1046       for (ic = ebbs[i]->sch; ic; ic = ic->next)
1047         {
1048           if (ic->op == RECEIVE)
1049             {
1050               if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
1051                   && !OP_SYMBOL (IC_RESULT (ic))->used)
1052                 {
1053 #if 0
1054                   fprintf (stderr, "discarding dead receive for %s\n",
1055                            OP_SYMBOL (IC_RESULT (ic))->name);
1056 #endif
1057                   dummyIcode.next = ic->next;
1058                   remiCodeFromeBBlock (ebbs[i], ic);
1059                   ic = &dummyIcode;
1060                 }
1061             }
1062         }
1063     }
1064 }
1065
1066 /*-----------------------------------------------------------------*/
1067 /* optimizeCastCast - remove unneeded intermediate casts.          */
1068 /* Integer promotion may cast (un)signed char to int and then      */
1069 /* recast the int to (un)signed long. If the signedness of the     */
1070 /* char and long are the same, the cast can be safely performed in */
1071 /* a single step.                                                  */
1072 /*-----------------------------------------------------------------*/
1073 static void
1074 optimizeCastCast (eBBlock ** ebbs, int count)
1075 {
1076   int i;
1077   iCode *ic;
1078   iCode *uic;
1079   sym_link * type1;
1080   sym_link * type2;
1081   sym_link * type3;
1082   symbol * sym;
1083
1084   for (i = 0; i < count; i++)
1085     {
1086       for (ic = ebbs[i]->sch; ic; ic = ic->next)
1087         {
1088
1089           if (ic->op == CAST && IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)))
1090             {
1091               type1 = operandType (IC_RIGHT (ic));
1092               type2 = operandType (IC_RESULT (ic));
1093
1094               /* Look only for a cast from an integer type to an */
1095               /* integer type that has no loss of bits */
1096               if (!IS_INTEGRAL (type1) || !IS_INTEGRAL (type2))
1097                 continue;
1098               if (getSize (type2) < getSize (type1))
1099                 continue;
1100
1101               /* There must be only one use of this first result */
1102               if (bitVectnBitsOn (OP_USES (IC_RESULT (ic))) != 1)
1103                 continue;
1104
1105               /* This use must be a second cast */
1106               uic = hTabItemWithKey (iCodehTab,
1107                         bitVectFirstBit (OP_USES (IC_RESULT (ic))));
1108               if (!uic || uic->op != CAST)
1109                 continue;
1110
1111               /* It must be a cast to another integer type that */
1112               /* has no loss of bits */
1113               type3 = operandType (IC_RESULT (uic));
1114               if (!IS_INTEGRAL (type3))
1115                  continue;
1116               if (getSize (type3) < getSize (type2))
1117                  continue;
1118
1119               /* The signedness between the first and last types */
1120               /* must match */
1121               if (SPEC_USIGN (type3) != SPEC_USIGN (type1))
1122                  continue;
1123
1124               /* Change the first cast to a simple assignment and */
1125               /* let the second cast do all the work */
1126               ic->op = '=';
1127               IC_LEFT (ic) = NULL;
1128               sym = OP_SYMBOL (IC_RESULT (ic));
1129               sym->type = copyLinkChain (type1);
1130               sym->etype = getSpec (sym->type);
1131             }
1132         }
1133     }
1134 }
1135
1136 /*-----------------------------------------------------------------*/
1137 /* eBBlockFromiCode - creates extended basic blocks from iCode     */
1138 /*                    will return an array of eBBlock pointers     */
1139 /*-----------------------------------------------------------------*/
1140 eBBlock **
1141 eBBlockFromiCode (iCode * ic)
1142 {
1143   eBBlock **ebbs = NULL;
1144   int count = 0;
1145   int saveCount = 0;
1146   int change = 1;
1147   int lchange = 0;
1148   int kchange = 0;
1149   hTab *loops;
1150
1151   /* if nothing passed then return nothing */
1152   if (!ic)
1153     return NULL;
1154
1155   count = 0;
1156   eBBNum = 0;
1157
1158   /* optimize the chain for labels & gotos
1159      this will eliminate redundant labels and
1160      will change jump to jumps by jumps */
1161   ic = iCodeLabelOptimize (ic);
1162
1163   /* break it down into basic blocks */
1164   ebbs = iCodeBreakDown (ic, &count);
1165   saveCount = count;
1166
1167   /* hash the iCode keys so that we can quickly index */
1168   /* them in the rest of the optimization steps */
1169   setToNull ((void *) &iCodehTab);
1170   iCodehTab = newHashTable (iCodeKey);
1171   hashiCodeKeys (ebbs, count);
1172
1173   /* compute the control flow */
1174   computeControlFlow (ebbs, count, 0);
1175
1176   /* dumpraw if asked for */
1177   if (options.dump_raw)
1178     dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
1179
1180   /* replace the local variables with their
1181      register equivalents : the liveRange computation
1182      along with the register allocation will determine
1183      if it finally stays in the registers */
1184   replaceRegEqv (ebbs, count);
1185
1186   /* create loop regions */
1187   loops = createLoopRegions (ebbs, count);
1188
1189   /* dumpraw if asked for */
1190   if (options.dump_raw)
1191     dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
1192
1193   optimizeCastCast (ebbs, saveCount);
1194
1195   /* do common subexpression elimination for each block */
1196   change = cseAllBlocks (ebbs, saveCount, FALSE);
1197
1198   /* dumpraw if asked for */
1199   if (options.dump_raw)
1200     dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
1201
1202   /* compute the data flow */
1203   computeDataFlow (ebbs, saveCount);
1204
1205   /* dumpraw if asked for */
1206   if (options.dump_raw)
1207     dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
1208
1209   /* global common subexpression elimination  */
1210   if (optimize.global_cse)
1211     {
1212       change += cseAllBlocks (ebbs, saveCount, FALSE);
1213       if (options.dump_gcse)
1214         dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
1215     }
1216   else
1217     {
1218       // compute the dataflow only
1219       assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
1220     }
1221   /* kill dead code */
1222   kchange = killDeadCode (ebbs, saveCount);
1223
1224   if (options.dump_kill)
1225     dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
1226
1227   /* do loop optimizations */
1228   change += (lchange = loopOptimizations (loops, ebbs, count));
1229   if (options.dump_loop)
1230     dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
1231
1232   /* recompute the data flow and apply global cse again
1233      if loops optimizations or dead code caused a change:
1234      loops will brings out of the loop which then may be
1235      available for use in the later blocks: dead code
1236      elimination could potentially disconnect some blocks
1237      conditional flow may be efected so we need to apply
1238      subexpression once more */
1239   if (lchange || kchange)
1240     {
1241       computeDataFlow (ebbs, saveCount);
1242       change += cseAllBlocks (ebbs, saveCount, FALSE);
1243       if (options.dump_loop)
1244         dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
1245
1246       /* if loop optimizations caused a change then do
1247          dead code elimination once more : this will
1248          get rid of the extra assignments to the induction
1249          variables created during loop optimizations */
1250       killDeadCode (ebbs, saveCount);
1251
1252       if (options.dump_loop)
1253         dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1254
1255     }
1256
1257   /* sort it back by block number */
1258   qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1259
1260   if (!options.lessPedantic) {
1261     // this is a good place to check missing return values
1262     if (currFunc) {
1263       // the user is on his own with naked functions...
1264       if (!IS_VOID(currFunc->etype)
1265        && !FUNC_ISNAKED(currFunc->type)) {
1266         eBBlock *bp;
1267         // make sure all predecessors of the last block end in a return
1268         for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1269              bp;
1270              bp=setNextItem(ebbs[saveCount-1]->predList)) {
1271           if (bp->ech->op != RETURN) {
1272             werrorfl (bp->ech->filename, bp->ech->lineno,
1273                       W_VOID_FUNC, currFunc->name);
1274           }
1275         }
1276       }
1277     }
1278   }
1279
1280   /* if cyclomatic info requested then print it */
1281   if (options.cyclomatic)
1282     printCyclomatic (ebbs, saveCount);
1283
1284   /* convert operations with support routines
1285      written in C to function calls : Iam doing
1286      this at this point since I want all the
1287      operations to be as they are for optimzations */
1288   convertToFcall (ebbs, count);
1289
1290   /* compute the live ranges */
1291   computeLiveRanges (ebbs, count);
1292
1293   if (options.dump_range)
1294     dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1295
1296   /* Now that we have the live ranges, discard parameter
1297    * receives for unused parameters.
1298    */
1299   discardDeadParamReceives (ebbs, count);
1300
1301   /* allocate registers & generate code */
1302   port->assignRegisters (ebbs, count);
1303
1304   /* throw away blocks */
1305   setToNull ((void *) &graphEdges);
1306   ebbs = NULL;
1307
1308   return NULL;
1309 }
1310
1311
1312 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */