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   return !sym->defs;
 576 }
 577
 578 /*-----------------------------------------------------------------*/
 579 /* replaceRegEqv - replace all local variables with their reqv     */
 580 /*-----------------------------------------------------------------*/
 581 static void
 582 replaceRegEqv (eBBlock ** ebbs, int count)
 583 {
 584   int i;
 585
 586   /* Update the symbols' def bitvector so we know if there is   */
 587   /* a defining iCode or not. Only replace a local variable     */
 588   /* with its register equivalent if there is a defining iCode; */
 589   /* otherwise, the port's register allocater may choke.        */
 590   cseAllBlocks (ebbs, count, TRUE);
 591
 592   for (i = 0; i < count; i++)
 593     {
 594
 595       iCode *ic;
 596
 597       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 598         {
 599
 600           if (SKIP_IC2 (ic))
 601             continue;
 602
 603           if (ic->op == IFX)
 604             {
 605               if (IC_COND (ic) &&
 606                   IS_TRUE_SYMOP (IC_COND (ic)) &&
 607                   isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
 608                 {
 609                   werror (W_LOCAL_NOINIT,
 610                           OP_SYMBOL (IC_COND (ic))->name,
 611                           ic->filename, ic->lineno);
 612                   OP_REQV (IC_COND (ic)) = NULL;
 613                   OP_SYMBOL (IC_COND (ic))->allocreq = 1;
 614                 }
 615
 616               if (IS_TRUE_SYMOP (IC_COND (ic)) &&
 617                   OP_REQV (IC_COND (ic)))
 618                 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
 619                                              OP_SYMBOL (IC_COND (ic))->defs,
 620                                             OP_SYMBOL (IC_COND (ic))->uses);
 621
 622               continue;
 623             }
 624
 625
 626           if (ic->op == JUMPTABLE)
 627             {
 628               if (IC_JTCOND (ic) &&
 629                   IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
 630                   isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
 631                 {
 632                   werror (W_LOCAL_NOINIT,
 633                           OP_SYMBOL (IC_JTCOND (ic))->name,
 634                           ic->filename, ic->lineno);
 635                   OP_REQV (IC_JTCOND (ic)) = NULL;
 636                   OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
 637                 }
 638
 639               if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
 640                   OP_REQV (IC_JTCOND (ic)))
 641                 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
 642                                            OP_SYMBOL (IC_JTCOND (ic))->defs,
 643                                           OP_SYMBOL (IC_JTCOND (ic))->uses);
 644               continue;
 645             }
 646
 647           if (ic->op == RECEIVE)
 648             {
 649               if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
 650                 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
 651             }
 652
 653           /* general case */
 654           if (IC_RESULT (ic) &&
 655               IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 656               OP_REQV (IC_RESULT (ic)))
 657             {
 658               if (POINTER_SET (ic))
 659                 {
 660                   IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
 661                                            OP_SYMBOL (IC_RESULT (ic))->defs,
 662                                           OP_SYMBOL (IC_RESULT (ic))->uses);
 663                   IC_RESULT (ic)->isaddr = 1;
 664                 }
 665               else
 666                 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
 667                                            OP_SYMBOL (IC_RESULT (ic))->defs,
 668                                           OP_SYMBOL (IC_RESULT (ic))->uses);
 669             }
 670
 671           if (IC_RIGHT (ic) &&
 672               IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
 673               isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
 674             {
 675               werror (W_LOCAL_NOINIT,
 676                       OP_SYMBOL (IC_RIGHT (ic))->name,
 677                       ic->filename, ic->lineno);
 678               OP_REQV (IC_RIGHT (ic)) = NULL;
 679               OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
 680             }
 681
 682           if (IC_RIGHT (ic) &&
 683               IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
 684               OP_REQV (IC_RIGHT (ic)))
 685             {
 686               IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
 687                                             OP_SYMBOL (IC_RIGHT (ic))->defs,
 688                                            OP_SYMBOL (IC_RIGHT (ic))->uses);
 689               IC_RIGHT (ic)->isaddr = 0;
 690             }
 691
 692           if (IC_LEFT (ic) &&
 693               IS_TRUE_SYMOP (IC_LEFT (ic)) &&
 694               isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
 695             {
 696               werror (W_LOCAL_NOINIT,
 697                       OP_SYMBOL (IC_LEFT (ic))->name,
 698                       ic->filename, ic->lineno);
 699               OP_REQV (IC_LEFT (ic)) = NULL;
 700               OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
 701             }
 702
 703           if (IC_LEFT (ic) &&
 704               IS_TRUE_SYMOP (IC_LEFT (ic)) &&
 705               OP_REQV (IC_LEFT (ic)))
 706             {
 707               IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
 708                                              OP_SYMBOL (IC_LEFT (ic))->defs,
 709                                              OP_SYMBOL (IC_LEFT (ic))->uses);
 710               IC_LEFT (ic)->isaddr = 0;
 711             }
 712         }
 713     }
 714 }
 715
 716 /*-----------------------------------------------------------------*/
 717 /* killDeadCode - eliminates dead assignments                      */
 718 /*-----------------------------------------------------------------*/
 719 int
 720 killDeadCode (eBBlock ** ebbs, int count)
 721 {
 722   int change = 1;
 723   int gchange = 0;
 724   int i = 0;
 725
 726
 727   /* basic algorithm :-                                          */
 728   /* first the exclusion rules :-                                */
 729   /*  1. if result is a global or volatile then skip             */
 730   /*  2. if assignment and result is a temp & isaddr  then skip  */
 731   /*     since this means array & pointer access, will be taken  */
 732   /*     care of by alias analysis.                              */
 733   /*  3. if the result is used in the remainder of the block skip */
 734   /*  4. if this definition does not reach the end of the block  */
 735   /*     i.e. the result is not present in the outExprs then KILL */
 736   /*  5. if it reaches the end of block & is used by some success */
 737   /*     or then skip                                            */
 738   /*     else            KILL                                    */
 739   /* this whole process is carried on iteratively till no change */
 740   while (1)
 741     {
 742
 743       change = 0;
 744       /* for all blocks do */
 745       for (i = 0; i < count; i++)
 746         {
 747           iCode *ic;
 748
 749           /* for all instructions in the block do */
 750           for (ic = ebbs[i]->sch; ic; ic = ic->next)
 751             {
 752               int kill, j;
 753               kill = 0;
 754
 755               if (SKIP_IC (ic) ||
 756                   ic->op == IFX ||
 757                   ic->op == RETURN ||
 758                   ic->op == DUMMY_READ_VOLATILE ||
 759                   ic->op == CRITICAL ||
 760                   ic->op == ENDCRITICAL)
 761                 continue;
 762
 763               /* if the result is volatile then continue */
 764               if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
 765                 continue;
 766
 767               /* if the result is a temp & isaddr then skip */
 768               if (IC_RESULT (ic) && POINTER_SET (ic))
 769                 continue;
 770
 771               if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
 772                 continue;
 773
 774               /* if the result is used in the remainder of the */
 775               /* block then skip */
 776               if (usedInRemaining (IC_RESULT (ic), ic->next))
 777                 continue;
 778
 779               /* does this definition reach the end of the block
 780                  or the usage is zero then we can kill */
 781               if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
 782                 kill = 1;       /* if not we can kill it */
 783               else
 784                 {
 785                   /* if this is a global variable or function parameter */
 786                   /* we cannot kill anyway             */
 787                   if (isOperandGlobal (IC_RESULT (ic)) ||
 788                       (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
 789                        !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
 790                     continue;
 791
 792                   /* if we are sure there are no usages */
 793                   if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
 794                     {
 795                       kill = 1;
 796                       goto kill;
 797                     }
 798
 799                   /* reset visited flag */
 800                   for (j = 0; j < count; ebbs[j++]->visited = 0);
 801
 802                   /* find out if this definition is alive */
 803                   if (applyToSet (ebbs[i]->succList,
 804                                   isDefAlive,
 805                                   ic))
 806                     continue;
 807
 808                   kill = 1;
 809                 }
 810
 811             kill:
 812               /* kill this one if required */
 813               if (kill)
 814                 {
 815                   change = 1;
 816                   gchange++;
 817                   /* eliminate this */
 818                   remiCodeFromeBBlock (ebbs[i], ic);
 819
 820                   /* now delete from defUseSet */
 821                   deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
 822                   bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
 823
 824                   /* and defset of the block */
 825                   bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 826
 827                   /* for the left & right remove the usage */
 828                   if (IS_SYMOP (IC_LEFT (ic)))
 829                     bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
 830
 831                   if (IS_SYMOP (IC_RIGHT (ic)))
 832                     bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
 833                 }
 834
 835             }                   /* end of all instructions */
 836
 837           if (!ebbs[i]->sch && !ebbs[i]->noPath)
 838             disconBBlock (ebbs[i], ebbs, count);
 839
 840         }                       /* end of for all blocks */
 841
 842       if (!change)
 843         break;
 844     }                           /* end of while(1) */
 845
 846   return gchange;
 847 }
 848
 849 /*-----------------------------------------------------------------*/
 850 /* printCyclomatic - prints the cyclomatic information             */
 851 /*-----------------------------------------------------------------*/
 852 static void
 853 printCyclomatic (eBBlock ** ebbs, int count)
 854 {
 855   int nEdges = elementsInSet (graphEdges);
 856   int i, nNodes = 0;
 857
 858   for (i = 0; i < count; i++)
 859     nNodes += (!ebbs[i]->noPath);
 860
 861   /* print the information */
 862   werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
 863 }
 864
 865 /*-----------------------------------------------------------------*/
 866 /* discardDeadParamReceives - remove any RECEIVE opcodes which     */
 867 /* refer to dead variables.                                        */
 868 /*-----------------------------------------------------------------*/
 869 static void
 870 discardDeadParamReceives (eBBlock ** ebbs, int count)
 871 {
 872   int i;
 873   iCode *ic;
 874   iCode dummyIcode;
 875
 876   for (i = 0; i < count; i++)
 877     {
 878       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 879         {
 880           if (ic->op == RECEIVE)
 881             {
 882               if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
 883                   && !OP_SYMBOL (IC_RESULT (ic))->used)
 884                 {
 885 #if 0
 886                   fprintf (stderr, "discarding dead receive for %s\n",
 887                            OP_SYMBOL (IC_RESULT (ic))->name);
 888 #endif
 889                   dummyIcode.next = ic->next;
 890                   remiCodeFromeBBlock (ebbs[i], ic);
 891                   ic = &dummyIcode;
 892                 }
 893             }
 894         }
 895     }
 896 }
 897
 898 /*-----------------------------------------------------------------*/
 899 /* eBBlockFromiCode - creates extended basic blocks from iCode     */
 900 /*                    will return an array of eBBlock pointers     */
 901 /*-----------------------------------------------------------------*/
 902 eBBlock **
 903 eBBlockFromiCode (iCode * ic)
 904 {
 905   eBBlock **ebbs = NULL;
 906   int count = 0;
 907   int saveCount = 0;
 908   int change = 1;
 909   int lchange = 0;
 910   int kchange = 0;
 911   hTab *loops;
 912
 913   /* if nothing passed then return nothing */
 914   if (!ic)
 915     return NULL;
 916
 917   count = 0;
 918   eBBNum = 0;
 919
 920   /* optimize the chain for labels & gotos
 921      this will eliminate redundant labels and
 922      will change jump to jumps by jumps */
 923   ic = iCodeLabelOptimize (ic);
 924
 925   /* break it down into basic blocks */
 926   ebbs = iCodeBreakDown (ic, &count);
 927   saveCount = count;
 928
 929   /* hash the iCode keys so that we can quickly index */
 930   /* them in the rest of the optimization steps */
 931   setToNull ((void *) &iCodehTab);
 932   iCodehTab = newHashTable (iCodeKey);
 933   hashiCodeKeys (ebbs, count);
 934
 935   /* compute the control flow */
 936   computeControlFlow (ebbs, count, 0);
 937
 938   /* dumpraw if asked for */
 939   if (options.dump_raw)
 940     dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
 941
 942   /* replace the local variables with their
 943      register equivalents : the liveRange computation
 944      along with the register allocation will determine
 945      if it finally stays in the registers */
 946   replaceRegEqv (ebbs, count);
 947
 948   /* create loop regions */
 949   loops = createLoopRegions (ebbs, count);
 950
 951   /* dumpraw if asked for */
 952   if (options.dump_raw)
 953     dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
 954
 955   /* do common subexpression elimination for each block */
 956   change = cseAllBlocks (ebbs, saveCount, FALSE);
 957
 958   /* dumpraw if asked for */
 959   if (options.dump_raw)
 960     dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
 961
 962   /* compute the data flow */
 963   computeDataFlow (ebbs, saveCount);
 964
 965   /* dumpraw if asked for */
 966   if (options.dump_raw)
 967     dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
 968
 969   /* global common subexpression elimination  */
 970   if (optimize.global_cse)
 971     {
 972       change += cseAllBlocks (ebbs, saveCount, FALSE);
 973       if (options.dump_gcse)
 974         dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
 975     }
 976   else
 977     {
 978       // compute the dataflow only
 979       assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
 980     }
 981   /* kill dead code */
 982   kchange = killDeadCode (ebbs, saveCount);
 983
 984   if (options.dump_kill)
 985     dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
 986
 987   /* do loop optimizations */
 988   change += (lchange = loopOptimizations (loops, ebbs, count));
 989   if (options.dump_loop)
 990     dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
 991
 992   /* recompute the data flow and apply global cse again
 993      if loops optimizations or dead code caused a change:
 994      loops will brings out of the loop which then may be
 995      available for use in the later blocks: dead code
 996      elimination could potentially disconnect some blocks
 997      conditional flow may be efected so we need to apply
 998      subexpression once more */
 999   if (lchange || kchange)
1000     {
1001       computeDataFlow (ebbs, saveCount);
1002       change += cseAllBlocks (ebbs, saveCount, FALSE);
1003       if (options.dump_loop)
1004         dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
1005
1006       /* if loop optimizations caused a change then do
1007          dead code elimination once more : this will
1008          get rid of the extra assignments to the induction
1009          variables created during loop optimizations */
1010       killDeadCode (ebbs, saveCount);
1011
1012       if (options.dump_loop)
1013         dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1014
1015     }
1016
1017   /* sort it back by block number */
1018   qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1019
1020   if (!options.lessPedantic) {
1021     // this is a good place to check missing return values
1022     if (currFunc) {
1023       // the user is on his own with naked functions...
1024       if (!IS_VOID(currFunc->etype)
1025        && !FUNC_ISNAKED(currFunc->type)) {
1026         eBBlock *bp;
1027         // make sure all predecessors of the last block end in a return
1028         for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1029              bp;
1030              bp=setNextItem(ebbs[saveCount-1]->predList)) {
1031           if (bp->ech->op != RETURN) {
1032             werror (W_VOID_FUNC, currFunc->name);
1033           }
1034         }
1035       }
1036     }
1037   }
1038
1039   /* if cyclomatic info requested then print it */
1040   if (options.cyclomatic)
1041     printCyclomatic (ebbs, saveCount);
1042
1043   /* convert operations with support routines
1044      written in C to function calls : Iam doing
1045      this at this point since I want all the
1046      operations to be as they are for optimzations */
1047   convertToFcall (ebbs, count);
1048
1049   /* compute the live ranges */
1050   computeLiveRanges (ebbs, count);
1051
1052   if (options.dump_range)
1053     dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1054
1055   /* Now that we have the live ranges, discard parameter
1056    * receives for unused parameters.
1057    */
1058   discardDeadParamReceives (ebbs, count);
1059
1060   /* allocate registers & generate code */
1061   port->assignRegisters (ebbs, count);
1062
1063   /* throw away blocks */
1064   setToNull ((void *) &graphEdges);
1065   ebbs = NULL;
1066
1067   return NULL;
1068 }
1069
1070
1071 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */