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   /* compute the control flow */
 930   computeControlFlow (ebbs, count, 0);
 931
 932   /* dumpraw if asked for */
 933   if (options.dump_raw)
 934     dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
 935
 936   /* replace the local variables with their
 937      register equivalents : the liveRange computation
 938      along with the register allocation will determine
 939      if it finally stays in the registers */
 940   replaceRegEqv (ebbs, count);
 941
 942   /* create loop regions */
 943   loops = createLoopRegions (ebbs, count);
 944
 945   /* dumpraw if asked for */
 946   if (options.dump_raw)
 947     dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
 948
 949   /* do common subexpression elimination for each block */
 950   change = cseAllBlocks (ebbs, saveCount, FALSE);
 951
 952   /* dumpraw if asked for */
 953   if (options.dump_raw)
 954     dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
 955
 956   /* compute the data flow */
 957   computeDataFlow (ebbs, saveCount);
 958
 959   /* dumpraw if asked for */
 960   if (options.dump_raw)
 961     dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
 962
 963   /* global common subexpression elimination  */
 964   if (optimize.global_cse)
 965     {
 966       change += cseAllBlocks (ebbs, saveCount, FALSE);
 967       if (options.dump_gcse)
 968         dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
 969     }
 970   else
 971     {
 972       // compute the dataflow only
 973       assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
 974     }
 975   /* kill dead code */
 976   kchange = killDeadCode (ebbs, saveCount);
 977
 978   if (options.dump_kill)
 979     dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
 980
 981   /* do loop optimizations */
 982   change += (lchange = loopOptimizations (loops, ebbs, count));
 983   if (options.dump_loop)
 984     dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
 985
 986   /* recompute the data flow and apply global cse again
 987      if loops optimizations or dead code caused a change:
 988      loops will brings out of the loop which then may be
 989      available for use in the later blocks: dead code
 990      elimination could potentially disconnect some blocks
 991      conditional flow may be efected so we need to apply
 992      subexpression once more */
 993   if (lchange || kchange)
 994     {
 995       computeDataFlow (ebbs, saveCount);
 996       change += cseAllBlocks (ebbs, saveCount, FALSE);
 997       if (options.dump_loop)
 998         dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
 999
1000       /* if loop optimizations caused a change then do
1001          dead code elimination once more : this will
1002          get rid of the extra assignments to the induction
1003          variables created during loop optimizations */
1004       killDeadCode (ebbs, saveCount);
1005
1006       if (options.dump_loop)
1007         dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1008
1009     }
1010
1011   /* sort it back by block number */
1012   qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1013
1014   if (!options.lessPedantic) {
1015     // this is a good place to check missing return values
1016     if (currFunc) {
1017       // the user is on his own with naked functions...
1018       if (!IS_VOID(currFunc->etype)
1019        && !FUNC_ISNAKED(currFunc->type)) {
1020         eBBlock *bp;
1021         // make sure all predecessors of the last block end in a return
1022         for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1023              bp;
1024              bp=setNextItem(ebbs[saveCount-1]->predList)) {
1025           if (bp->ech->op != RETURN) {
1026             werror (W_VOID_FUNC, currFunc->name);
1027           }
1028         }
1029       }
1030     }
1031   }
1032
1033   /* if cyclomatic info requested then print it */
1034   if (options.cyclomatic)
1035     printCyclomatic (ebbs, saveCount);
1036
1037   /* convert operations with support routines
1038      written in C to function calls : Iam doing
1039      this at this point since I want all the
1040      operations to be as they are for optimzations */
1041   convertToFcall (ebbs, count);
1042
1043   /* compute the live ranges */
1044   computeLiveRanges (ebbs, count);
1045
1046   if (options.dump_range)
1047     dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1048
1049   /* Now that we have the live ranges, discard parameter
1050    * receives for unused parameters.
1051    */
1052   discardDeadParamReceives (ebbs, count);
1053
1054   /* allocate registers & generate code */
1055   port->assignRegisters (ebbs, count);
1056
1057   /* throw away blocks */
1058   setToNull ((void *) &graphEdges);
1059   ebbs = NULL;
1060
1061   return NULL;
1062 }
1063
1064
1065 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */