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   addiCodeToeBBlock (ebp, newic, ip);
 180 }
 181
 182 /*-----------------------------------------------------------------*/
 183 /* cnvToFloatCast - converts casts to floats to function calls     */
 184 /*-----------------------------------------------------------------*/
 185 static void
 186 cnvToFloatCast (iCode * ic, eBBlock * ebp)
 187 {
 188   iCode *ip, *newic;
 189   symbol *func = NULL;
 190   sym_link *type = operandType (IC_RIGHT (ic));
 191   int linenno = ic->lineno;
 192   int bwd, su;
 193   int bytesPushed=0;
 194
 195   ip = ic->next;
 196   /* remove it from the iCode */
 197   remiCodeFromeBBlock (ebp, ic);
 198   /* depending on the type */
 199   for (bwd = 0; bwd < 3; bwd++)
 200     {
 201       for (su = 0; su < 2; su++)
 202         {
 203           if (compareType (type, __multypes[bwd][su]) == 1)
 204             {
 205               func = __conv[0][bwd][su];
 206               goto found;
 207             }
 208         }
 209     }
 210   assert (0);
 211 found:
 212
 213   /* if float support routines NOT compiled as reentrant */
 214   if (!options.float_rent)
 215     {
 216       /* first one */
 217         if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 218             {
 219                 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 220                 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 221             }
 222       else
 223         {
 224           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 225           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 226         }
 227       addiCodeToeBBlock (ebp, newic, ip);
 228       newic->lineno = linenno;
 229
 230     }
 231   else
 232     {
 233       /* push the left */
 234         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 235             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 236             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 237         }
 238       else
 239         {
 240           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 241           newic->parmPush = 1;
 242           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 243         }
 244       addiCodeToeBBlock (ebp, newic, ip);
 245       newic->lineno = linenno;
 246
 247     }
 248
 249   /* make the call */
 250   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 251   IC_RESULT (newic) = IC_RESULT (ic);
 252   newic->parmBytes+=bytesPushed;
 253   addiCodeToeBBlock (ebp, newic, ip);
 254   newic->lineno = linenno;
 255
 256 }
 257
 258 /*-----------------------------------------------------------------*/
 259 /* cnvFromFloatCast - converts casts From floats to function calls */
 260 /*-----------------------------------------------------------------*/
 261 static void
 262 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
 263 {
 264   iCode *ip, *newic;
 265   symbol *func = NULL;
 266   sym_link *type = operandType (IC_LEFT (ic));
 267   int lineno = ic->lineno;
 268   int bwd, su;
 269   int bytesPushed=0;
 270
 271   ip = ic->next;
 272   /* remove it from the iCode */
 273   remiCodeFromeBBlock (ebp, ic);
 274
 275   /* depending on the type */
 276   for (bwd = 0; bwd < 3; bwd++)
 277     {
 278       for (su = 0; su < 2; su++)
 279         {
 280           if (compareType (type, __multypes[bwd][su]) == 1)
 281             {
 282               func = __conv[1][bwd][su];
 283               goto found;
 284             }
 285         }
 286     }
 287   assert (0);
 288 found:
 289
 290   /* if float support routines NOT compiled as reentrant */
 291   if (!options.float_rent)
 292     {
 293       /* first one */
 294         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 295             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 296             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 297         }
 298       else
 299         {
 300           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 301           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 302         }
 303       addiCodeToeBBlock (ebp, newic, ip);
 304       newic->lineno = lineno;
 305
 306     }
 307   else
 308     {
 309
 310       /* push the left */
 311         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 312             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 313             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 314         }
 315       else
 316         {
 317           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 318           newic->parmPush = 1;
 319           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 320         }
 321       addiCodeToeBBlock (ebp, newic, ip);
 322       newic->lineno = lineno;
 323
 324     }
 325
 326   /* make the call */
 327   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 328   IC_RESULT (newic) = IC_RESULT (ic);
 329   newic->parmBytes+=bytesPushed;
 330   addiCodeToeBBlock (ebp, newic, ip);
 331   newic->lineno = lineno;
 332
 333 }
 334
 335 extern operand *geniCodeRValue (operand *, bool);
 336
 337 /*-----------------------------------------------------------------*/
 338 /* convilong - converts int or long mults or divs to fcalls        */
 339 /*-----------------------------------------------------------------*/
 340 static void
 341 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
 342 {
 343   symbol *func = NULL;
 344   iCode *ip = ic->next;
 345   iCode *newic;
 346   int lineno = ic->lineno;
 347   int bwd;
 348   int su;
 349   int bytesPushed=0;
 350
 351   // Easy special case which avoids function call: modulo by a literal power
 352   // of two can be replaced by a bitwise AND.
 353   if (op == '%' && isOperandLiteral(IC_RIGHT(ic)))
 354   {
 355       unsigned litVal = (unsigned)(operandLitValue(IC_RIGHT(ic)));
 356
 357       // See if literal value is a power of 2.
 358       while (litVal && !(litVal & 1))
 359       {
 360           litVal >>= 1;
 361       }
 362       if (litVal)
 363       {
 364           // discard first high bit set.
 365           litVal >>= 1;
 366       }
 367
 368       if (!litVal)
 369       {
 370           ic->op = BITWISEAND;
 371           IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
 372           return;
 373       }
 374   }
 375
 376   remiCodeFromeBBlock (ebp, ic);
 377
 378
 379   /* depending on the type */
 380   for (bwd = 0; bwd < 3; bwd++)
 381     {
 382       for (su = 0; su < 2; su++)
 383         {
 384           if (compareType (type, __multypes[bwd][su]) == 1)
 385             {
 386               if (op == '*')
 387                 func = __muldiv[0][bwd][su];
 388               else if (op == '/')
 389                 func = __muldiv[1][bwd][su];
 390               else if (op == '%')
 391                 func = __muldiv[2][bwd][su];
 392               else if (op == RRC)
 393                 func = __rlrr[1][bwd][su];
 394               else if (op == RLC)
 395                 func = __rlrr[0][bwd][su];
 396               else if (op == RIGHT_OP)
 397                 func = __rlrr[1][bwd][su];
 398               else if (op == LEFT_OP)
 399                 func = __rlrr[0][bwd][su];
 400               else
 401                 assert (0);
 402               goto found;
 403             }
 404         }
 405     }
 406   assert (0);
 407 found:
 408   /* if int & long support routines NOT compiled as reentrant */
 409   if (!options.intlong_rent)
 410     {
 411       /* first one */
 412         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 413             newic = newiCode (SEND, IC_LEFT (ic), NULL);
 414             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 415         }
 416       else
 417         {
 418           newic = newiCode ('=', NULL, IC_LEFT (ic));
 419           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 420         }
 421       addiCodeToeBBlock (ebp, newic, ip);
 422       newic->lineno = lineno;
 423
 424       /* second one */
 425       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
 426           newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 427           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 428       }
 429       else
 430         {
 431           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 432           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
 433         }
 434       addiCodeToeBBlock (ebp, newic, ip);
 435       newic->lineno = lineno;
 436
 437     }
 438   else
 439     {
 440       /* compiled as reentrant then push */
 441       /* push right */
 442       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
 443         {
 444           newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 445           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 446         }
 447       else
 448         {
 449           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 450           newic->parmPush = 1;
 451
 452           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 453         }
 454       addiCodeToeBBlock (ebp, newic, ip);
 455       newic->lineno = lineno;
 456
 457       /* insert push left */
 458       if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 459         {
 460           newic = newiCode (SEND, IC_LEFT (ic), NULL);
 461           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 462         }
 463       else
 464         {
 465           newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
 466           newic->parmPush = 1;
 467
 468           bytesPushed += getSize(operandType(IC_LEFT(ic)));
 469         }
 470       addiCodeToeBBlock (ebp, newic, ip);
 471       newic->lineno = lineno;
 472
 473     }
 474
 475   /* for the result */
 476   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 477   IC_RESULT (newic) = IC_RESULT (ic);
 478   newic->lineno = lineno;
 479   newic->parmBytes+=bytesPushed; // to clear the stack after the call
 480   addiCodeToeBBlock (ebp, newic, ip);
 481 }
 482
 483 /*-----------------------------------------------------------------*/
 484 /* convertToFcall - converts some operations to fcalls             */
 485 /*-----------------------------------------------------------------*/
 486 static void
 487 convertToFcall (eBBlock ** ebbs, int count)
 488 {
 489   int i;
 490
 491   /* for all blocks do */
 492   for (i = 0; i < count; i++)
 493     {
 494       iCode *ic;
 495
 496       /* for all instructions in the block do */
 497       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 498         {
 499
 500           /* floating point operations are
 501              converted to function calls */
 502           if ((IS_CONDITIONAL (ic) ||
 503                IS_ARITHMETIC_OP (ic)) &&
 504               (IS_FLOAT (operandType (IC_RIGHT (ic)))))
 505             {
 506
 507               cnvToFcall (ic, ebbs[i]);
 508             }
 509
 510           /* casting is a little different */
 511           if (ic->op == CAST)
 512             {
 513               if (IS_FLOAT (operandType (IC_RIGHT (ic))))
 514                 cnvFromFloatCast (ic, ebbs[i]);
 515               else if (IS_FLOAT (operandType (IC_LEFT (ic))))
 516                 cnvToFloatCast (ic, ebbs[i]);
 517             }
 518
 519           /* if long / int mult or divide or mod */
 520           if (ic->op == '*' || ic->op == '/' || ic->op == '%')
 521             {
 522               sym_link *leftType = operandType (IC_LEFT (ic));
 523
 524               if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
 525                 {
 526                   sym_link *rightType = operandType (IC_RIGHT (ic));
 527
 528                   if (port->hasNativeMulFor != NULL &&
 529                       port->hasNativeMulFor (ic, leftType, rightType))
 530                     {
 531                       /* Leave as native */
 532                     }
 533                   else
 534                     {
 535                       convilong (ic, ebbs[i], leftType, ic->op);
 536                     }
 537                 }
 538             }
 539
 540           if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
 541             {
 542               sym_link *type = operandType (IC_LEFT (ic));
 543
 544               if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
 545                 {
 546                   convilong (ic, ebbs[i], type, ic->op);
 547                 }
 548             }
 549         }
 550     }
 551 }
 552
 553 /*-----------------------------------------------------------------*/
 554 /* isLocalWithoutDef - return 1 if sym might be used without a     */
 555 /*                     defining iCode                              */
 556 /*-----------------------------------------------------------------*/
 557 static int
 558 isLocalWithoutDef (symbol * sym)
 559 {
 560   if (!sym->level)
 561     return 0;
 562
 563   if (IS_STATIC (sym->etype))
 564     return 0;
 565
 566   if (IS_VOLATILE (sym->type))
 567     return 0;
 568
 569   if (sym->_isparm)
 570     return 0;
 571
 572   if (IS_AGGREGATE (sym->type))
 573     return 0;
 574
 575   if (sym->addrtaken)
 576     return 0;
 577
 578   return !sym->defs;
 579 }
 580
 581 /*-----------------------------------------------------------------*/
 582 /* replaceRegEqv - replace all local variables with their reqv     */
 583 /*-----------------------------------------------------------------*/
 584 static void
 585 replaceRegEqv (eBBlock ** ebbs, int count)
 586 {
 587   int i;
 588
 589   /* Update the symbols' def bitvector so we know if there is   */
 590   /* a defining iCode or not. Only replace a local variable     */
 591   /* with its register equivalent if there is a defining iCode; */
 592   /* otherwise, the port's register allocater may choke.        */
 593   cseAllBlocks (ebbs, count, TRUE);
 594
 595   for (i = 0; i < count; i++)
 596     {
 597
 598       iCode *ic;
 599
 600       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 601         {
 602
 603           if (SKIP_IC2 (ic))
 604             continue;
 605
 606           if (ic->op == IFX)
 607             {
 608               if (IC_COND (ic) &&
 609                   IS_TRUE_SYMOP (IC_COND (ic)) &&
 610                   isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
 611                 {
 612                   werrorfl (ic->filename, ic->lineno,
 613                           W_LOCAL_NOINIT,
 614                           OP_SYMBOL (IC_COND (ic))->name);
 615                   OP_REQV (IC_COND (ic)) = NULL;
 616                   OP_SYMBOL (IC_COND (ic))->allocreq = 1;
 617                 }
 618
 619               if (IS_TRUE_SYMOP (IC_COND (ic)) &&
 620                   OP_REQV (IC_COND (ic)))
 621                 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
 622                                              OP_SYMBOL (IC_COND (ic))->defs,
 623                                             OP_SYMBOL (IC_COND (ic))->uses);
 624
 625               continue;
 626             }
 627
 628
 629           if (ic->op == JUMPTABLE)
 630             {
 631               if (IC_JTCOND (ic) &&
 632                   IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
 633                   isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
 634                 {
 635                   werrorfl (ic->filename, ic->lineno,
 636                           W_LOCAL_NOINIT,
 637                           OP_SYMBOL (IC_JTCOND (ic))->name);
 638                   OP_REQV (IC_JTCOND (ic)) = NULL;
 639                   OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
 640                 }
 641
 642               if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
 643                   OP_REQV (IC_JTCOND (ic)))
 644                 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
 645                                            OP_SYMBOL (IC_JTCOND (ic))->defs,
 646                                           OP_SYMBOL (IC_JTCOND (ic))->uses);
 647               continue;
 648             }
 649
 650           if (ic->op == RECEIVE)
 651             {
 652               if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
 653                 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
 654             }
 655
 656           /* general case */
 657           if (IC_RESULT (ic) &&
 658               IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 659               OP_REQV (IC_RESULT (ic)))
 660             {
 661               if (POINTER_SET (ic))
 662                 {
 663                   IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
 664                                            OP_SYMBOL (IC_RESULT (ic))->defs,
 665                                           OP_SYMBOL (IC_RESULT (ic))->uses);
 666                   IC_RESULT (ic)->isaddr = 1;
 667                 }
 668               else
 669                 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
 670                                            OP_SYMBOL (IC_RESULT (ic))->defs,
 671                                           OP_SYMBOL (IC_RESULT (ic))->uses);
 672             }
 673
 674           if (IC_RIGHT (ic) &&
 675               IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
 676               isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
 677             {
 678               werrorfl (ic->filename, ic->lineno,
 679                         W_LOCAL_NOINIT,
 680                         OP_SYMBOL (IC_RIGHT (ic))->name);
 681               OP_REQV (IC_RIGHT (ic)) = NULL;
 682               OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
 683             }
 684
 685           if (IC_RIGHT (ic) &&
 686               IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
 687               OP_REQV (IC_RIGHT (ic)))
 688             {
 689               IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
 690                                             OP_SYMBOL (IC_RIGHT (ic))->defs,
 691                                            OP_SYMBOL (IC_RIGHT (ic))->uses);
 692               IC_RIGHT (ic)->isaddr = 0;
 693             }
 694
 695           if (IC_LEFT (ic) &&
 696               IS_TRUE_SYMOP (IC_LEFT (ic)) &&
 697               isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
 698             {
 699               werrorfl (ic->filename, ic->lineno,
 700                         W_LOCAL_NOINIT,
 701                         OP_SYMBOL (IC_LEFT (ic))->name);
 702               OP_REQV (IC_LEFT (ic)) = NULL;
 703               OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
 704             }
 705
 706           if (IC_LEFT (ic) &&
 707               IS_TRUE_SYMOP (IC_LEFT (ic)) &&
 708               OP_REQV (IC_LEFT (ic)))
 709             {
 710               IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
 711                                              OP_SYMBOL (IC_LEFT (ic))->defs,
 712                                              OP_SYMBOL (IC_LEFT (ic))->uses);
 713               IC_LEFT (ic)->isaddr = 0;
 714             }
 715         }
 716     }
 717 }
 718
 719 /*-----------------------------------------------------------------*/
 720 /* killDeadCode - eliminates dead assignments                      */
 721 /*-----------------------------------------------------------------*/
 722 int
 723 killDeadCode (eBBlock ** ebbs, int count)
 724 {
 725   int change = 1;
 726   int gchange = 0;
 727   int i = 0;
 728
 729
 730   /* basic algorithm :-                                          */
 731   /* first the exclusion rules :-                                */
 732   /*  1. if result is a global or volatile then skip             */
 733   /*  2. if assignment and result is a temp & isaddr  then skip  */
 734   /*     since this means array & pointer access, will be taken  */
 735   /*     care of by alias analysis.                              */
 736   /*  3. if the result is used in the remainder of the block skip */
 737   /*  4. if this definition does not reach the end of the block  */
 738   /*     i.e. the result is not present in the outExprs then KILL */
 739   /*  5. if it reaches the end of block & is used by some success */
 740   /*     or then skip                                            */
 741   /*     else            KILL                                    */
 742   /* this whole process is carried on iteratively till no change */
 743   while (1)
 744     {
 745
 746       change = 0;
 747       /* for all blocks do */
 748       for (i = 0; i < count; i++)
 749         {
 750           iCode *ic;
 751
 752           /* for all instructions in the block do */
 753           for (ic = ebbs[i]->sch; ic; ic = ic->next)
 754             {
 755               int kill, j;
 756               kill = 0;
 757
 758               if (SKIP_IC (ic) ||
 759                   ic->op == IFX ||
 760                   ic->op == RETURN ||
 761                   ic->op == DUMMY_READ_VOLATILE ||
 762                   ic->op == CRITICAL ||
 763                   ic->op == ENDCRITICAL)
 764                 continue;
 765
 766               /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
 767               /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are  */
 768               /* valid. */
 769
 770               /* if the result is volatile then continue */
 771               if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
 772                 continue;
 773
 774               /* if the result is a temp & isaddr then skip */
 775               if (IC_RESULT (ic) && POINTER_SET (ic))
 776                 continue;
 777
 778               if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
 779                 continue;
 780
 781               /* if the result is used in the remainder of the */
 782               /* block then skip */
 783               if (usedInRemaining (IC_RESULT (ic), ic->next))
 784                 continue;
 785
 786               /* does this definition reach the end of the block
 787                  or the usage is zero then we can kill */
 788               if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
 789                 kill = 1;       /* if not we can kill it */
 790               else
 791                 {
 792                   /* if this is a global variable or function parameter */
 793                   /* we cannot kill anyway             */
 794                   if (isOperandGlobal (IC_RESULT (ic)) ||
 795                       (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
 796                        !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
 797                     continue;
 798
 799                   /* if we are sure there are no usages */
 800                   if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
 801                     {
 802                       kill = 1;
 803                       goto kill;
 804                     }
 805
 806                   /* reset visited flag */
 807                   for (j = 0; j < count; ebbs[j++]->visited = 0);
 808
 809                   /* find out if this definition is alive */
 810                   if (applyToSet (ebbs[i]->succList,
 811                                   isDefAlive,
 812                                   ic))
 813                     continue;
 814
 815                   kill = 1;
 816                 }
 817
 818             kill:
 819               /* kill this one if required */
 820               if (kill)
 821                 {
 822                   bool volLeft = IS_SYMOP (IC_LEFT (ic))
 823                                  && isOperandVolatile (IC_LEFT (ic), FALSE);
 824                   bool volRight = IS_SYMOP (IC_RIGHT (ic))
 825                                   && isOperandVolatile (IC_RIGHT (ic), FALSE);
 826
 827                   change = 1;
 828                   gchange++;
 829
 830                   /* now delete from defUseSet */
 831                   deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
 832                   bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
 833
 834                   /* and defset of the block */
 835                   bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 836
 837                   /* delete the result */
 838                   IC_RESULT (ic) = NULL;
 839
 840                   if (volLeft || volRight)
 841                     {
 842                       /* something is volatile, so keep the iCode */
 843                       /* and change the operator instead */
 844                       ic->op = DUMMY_READ_VOLATILE;
 845
 846                       /* keep only the volatile operands */
 847                       if (!volLeft)
 848                         IC_LEFT (ic) = NULL;
 849                       if (!volRight)
 850                         IC_RIGHT (ic) = NULL;
 851                     }
 852                   else
 853                     {
 854                       /* nothing is volatile, eliminate the iCode */
 855                       remiCodeFromeBBlock (ebbs[i], ic);
 856
 857                       /* for the left & right remove the usage */
 858                       if (IS_SYMOP (IC_LEFT (ic)))
 859                         bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
 860
 861                       if (IS_SYMOP (IC_RIGHT (ic)))
 862                         bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
 863                     }
 864                 }
 865
 866             }                   /* end of all instructions */
 867
 868           if (!ebbs[i]->sch && !ebbs[i]->noPath)
 869             disconBBlock (ebbs[i], ebbs, count);
 870
 871         }                       /* end of for all blocks */
 872
 873       if (!change)
 874         break;
 875     }                           /* end of while(1) */
 876
 877   return gchange;
 878 }
 879
 880 /*-----------------------------------------------------------------*/
 881 /* printCyclomatic - prints the cyclomatic information             */
 882 /*-----------------------------------------------------------------*/
 883 static void
 884 printCyclomatic (eBBlock ** ebbs, int count)
 885 {
 886   int nEdges = elementsInSet (graphEdges);
 887   int i, nNodes = 0;
 888
 889   for (i = 0; i < count; i++)
 890     nNodes += (!ebbs[i]->noPath);
 891
 892   /* print the information */
 893   werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
 894 }
 895
 896 /*-----------------------------------------------------------------*/
 897 /* discardDeadParamReceives - remove any RECEIVE opcodes which     */
 898 /* refer to dead variables.                                        */
 899 /*-----------------------------------------------------------------*/
 900 static void
 901 discardDeadParamReceives (eBBlock ** ebbs, int count)
 902 {
 903   int i;
 904   iCode *ic;
 905   iCode dummyIcode;
 906
 907   for (i = 0; i < count; i++)
 908     {
 909       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 910         {
 911           if (ic->op == RECEIVE)
 912             {
 913               if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
 914                   && !OP_SYMBOL (IC_RESULT (ic))->used)
 915                 {
 916 #if 0
 917                   fprintf (stderr, "discarding dead receive for %s\n",
 918                            OP_SYMBOL (IC_RESULT (ic))->name);
 919 #endif
 920                   dummyIcode.next = ic->next;
 921                   remiCodeFromeBBlock (ebbs[i], ic);
 922                   ic = &dummyIcode;
 923                 }
 924             }
 925         }
 926     }
 927 }
 928
 929 /*-----------------------------------------------------------------*/
 930 /* eBBlockFromiCode - creates extended basic blocks from iCode     */
 931 /*                    will return an array of eBBlock pointers     */
 932 /*-----------------------------------------------------------------*/
 933 eBBlock **
 934 eBBlockFromiCode (iCode * ic)
 935 {
 936   eBBlock **ebbs = NULL;
 937   int count = 0;
 938   int saveCount = 0;
 939   int change = 1;
 940   int lchange = 0;
 941   int kchange = 0;
 942   hTab *loops;
 943
 944   /* if nothing passed then return nothing */
 945   if (!ic)
 946     return NULL;
 947
 948   count = 0;
 949   eBBNum = 0;
 950
 951   /* optimize the chain for labels & gotos
 952      this will eliminate redundant labels and
 953      will change jump to jumps by jumps */
 954   ic = iCodeLabelOptimize (ic);
 955
 956   /* break it down into basic blocks */
 957   ebbs = iCodeBreakDown (ic, &count);
 958   saveCount = count;
 959
 960   /* hash the iCode keys so that we can quickly index */
 961   /* them in the rest of the optimization steps */
 962   setToNull ((void *) &iCodehTab);
 963   iCodehTab = newHashTable (iCodeKey);
 964   hashiCodeKeys (ebbs, count);
 965
 966   /* compute the control flow */
 967   computeControlFlow (ebbs, count, 0);
 968
 969   /* dumpraw if asked for */
 970   if (options.dump_raw)
 971     dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
 972
 973   /* replace the local variables with their
 974      register equivalents : the liveRange computation
 975      along with the register allocation will determine
 976      if it finally stays in the registers */
 977   replaceRegEqv (ebbs, count);
 978
 979   /* create loop regions */
 980   loops = createLoopRegions (ebbs, count);
 981
 982   /* dumpraw if asked for */
 983   if (options.dump_raw)
 984     dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
 985
 986   /* do common subexpression elimination for each block */
 987   change = cseAllBlocks (ebbs, saveCount, FALSE);
 988
 989   /* dumpraw if asked for */
 990   if (options.dump_raw)
 991     dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
 992
 993   /* compute the data flow */
 994   computeDataFlow (ebbs, saveCount);
 995
 996   /* dumpraw if asked for */
 997   if (options.dump_raw)
 998     dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
 999
1000   /* global common subexpression elimination  */
1001   if (optimize.global_cse)
1002     {
1003       change += cseAllBlocks (ebbs, saveCount, FALSE);
1004       if (options.dump_gcse)
1005         dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
1006     }
1007   else
1008     {
1009       // compute the dataflow only
1010       assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
1011     }
1012   /* kill dead code */
1013   kchange = killDeadCode (ebbs, saveCount);
1014
1015   if (options.dump_kill)
1016     dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
1017
1018   /* do loop optimizations */
1019   change += (lchange = loopOptimizations (loops, ebbs, count));
1020   if (options.dump_loop)
1021     dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
1022
1023   /* recompute the data flow and apply global cse again
1024      if loops optimizations or dead code caused a change:
1025      loops will brings out of the loop which then may be
1026      available for use in the later blocks: dead code
1027      elimination could potentially disconnect some blocks
1028      conditional flow may be efected so we need to apply
1029      subexpression once more */
1030   if (lchange || kchange)
1031     {
1032       computeDataFlow (ebbs, saveCount);
1033       change += cseAllBlocks (ebbs, saveCount, FALSE);
1034       if (options.dump_loop)
1035         dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
1036
1037       /* if loop optimizations caused a change then do
1038          dead code elimination once more : this will
1039          get rid of the extra assignments to the induction
1040          variables created during loop optimizations */
1041       killDeadCode (ebbs, saveCount);
1042
1043       if (options.dump_loop)
1044         dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1045
1046     }
1047
1048   /* sort it back by block number */
1049   qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1050
1051   if (!options.lessPedantic) {
1052     // this is a good place to check missing return values
1053     if (currFunc) {
1054       // the user is on his own with naked functions...
1055       if (!IS_VOID(currFunc->etype)
1056        && !FUNC_ISNAKED(currFunc->type)) {
1057         eBBlock *bp;
1058         // make sure all predecessors of the last block end in a return
1059         for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1060              bp;
1061              bp=setNextItem(ebbs[saveCount-1]->predList)) {
1062           if (bp->ech->op != RETURN) {
1063             werrorfl (bp->ech->filename, bp->ech->lineno,
1064                       W_VOID_FUNC, currFunc->name);
1065           }
1066         }
1067       }
1068     }
1069   }
1070
1071   /* if cyclomatic info requested then print it */
1072   if (options.cyclomatic)
1073     printCyclomatic (ebbs, saveCount);
1074
1075   /* convert operations with support routines
1076      written in C to function calls : Iam doing
1077      this at this point since I want all the
1078      operations to be as they are for optimzations */
1079   convertToFcall (ebbs, count);
1080
1081   /* compute the live ranges */
1082   computeLiveRanges (ebbs, count);
1083
1084   if (options.dump_range)
1085     dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1086
1087   /* Now that we have the live ranges, discard parameter
1088    * receives for unused parameters.
1089    */
1090   discardDeadParamReceives (ebbs, count);
1091
1092   /* allocate registers & generate code */
1093   port->assignRegisters (ebbs, count);
1094
1095   /* throw away blocks */
1096   setToNull ((void *) &graphEdges);
1097   ebbs = NULL;
1098
1099   return NULL;
1100 }
1101
1102
1103 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */