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