git.gag.com Git - fw/sdcc/blob - src/SDCCopt.c

   1 /*-------------------------------------------------------------------------
   2   SDCCopt.c - calls all the optimizations routines and does some of the
   3               hackier transformations, these include translating iCodes
   4               to function calls and replacing local variables with their
   5               register equivalents etc. Also contains the driver routine
   6               for dead code elimination
   7
   8              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
   9
  10    This program is free software; you can redistribute it and/or modify it
  11    under the terms of the GNU General Public License as published by the
  12    Free Software Foundation; either version 2, or (at your option) any
  13    later version.
  14
  15    This program is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18    GNU General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23
  24    In other words, you are welcome to use, share and improve this program.
  25    You are forbidden to forbid anyone else to use, share and improve
  26    what you give them.   Help stamp out software-hoarding!
  27 -------------------------------------------------------------------------*/
  28
  29 #include "common.h"
  30
  31 /*-----------------------------------------------------------------*/
  32 /* global variables */
  33 int cseDefNum = 0;
  34
  35 char flowChanged = 0;
  36
  37
  38 /*-----------------------------------------------------------------*/
  39 /* printSymName - prints the symbol names                          */
  40 /*-----------------------------------------------------------------*/
  41 int
  42 printSymName (void *vsym)
  43 {
  44   symbol *sym = vsym;
  45   fprintf (stdout, " %s ", sym->name);
  46   return 0;
  47 }
  48
  49 /*-----------------------------------------------------------------*/
  50 /* cnvToFcall - does the actual conversion to function call        */
  51 /*-----------------------------------------------------------------*/
  52 static void
  53 cnvToFcall (iCode * ic, eBBlock * ebp)
  54 {
  55   iCode *ip;
  56   iCode *newic;
  57   operand *left;
  58   operand *right;
  59   symbol *func = NULL;
  60   int lineno = ic->lineno;
  61   int bytesPushed=0;
  62
  63   ip = ic->next;                /* insertion point */
  64   /* remove it from the iCode */
  65   remiCodeFromeBBlock (ebp, ic);
  66
  67   left = IC_LEFT (ic);
  68   right = IC_RIGHT (ic);
  69
  70   switch (ic->op)
  71     {
  72     case '+':
  73       func = __fsadd;
  74       break;
  75     case '-':
  76       func = __fssub;
  77       break;
  78     case '/':
  79       func = __fsdiv;
  80       break;
  81     case '*':
  82       func = __fsmul;
  83       break;
  84     case EQ_OP:
  85       func = __fseq;
  86       break;
  87     case NE_OP:
  88       func = __fsneq;
  89       break;
  90     case '<':
  91       func = __fslt;
  92       break;
  93     case '>':
  94       func = __fsgt;
  95       break;
  96     case LE_OP:
  97       func = __fslteq;
  98       break;
  99     case GE_OP:
 100       func = __fsgteq;
 101       break;
 102     }
 103
 104   /* if float support routines NOT compiled as reentrant */
 105   if (!options.float_rent)
 106     {
 107
 108       /* first one */
 109       if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 110         {
 111           newic = newiCode (SEND, IC_LEFT (ic), NULL);
 112           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 113         }
 114       else
 115         {
 116           newic = newiCode ('=', NULL, IC_LEFT (ic));
 117           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 118         }
 119
 120       addiCodeToeBBlock (ebp, newic, ip);
 121       newic->lineno = lineno;
 122
 123       /* second one */
 124       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
 125         {
 126           newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 127           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 128         }
 129       else
 130         {
 131           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 132           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
 133         }
 134       addiCodeToeBBlock (ebp, newic, ip);
 135       newic->lineno = lineno;
 136
 137     }
 138   else
 139     {
 140
 141       /* push right */
 142       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
 143         {
 144           newic = newiCode (SEND, right, NULL);
 145           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 146         }
 147       else
 148         {
 149           newic = newiCode (IPUSH, right, NULL);
 150           newic->parmPush = 1;
 151           //bytesPushed+=4;
 152           bytesPushed += getSize(operandType(right));
 153         }
 154
 155       addiCodeToeBBlock (ebp, newic, ip);
 156       newic->lineno = lineno;
 157
 158       /* insert push left */
 159       if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 160         {
 161           newic = newiCode (SEND, left, NULL);
 162           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 163         }
 164       else
 165         {
 166           newic = newiCode (IPUSH, left, NULL);
 167           newic->parmPush = 1;
 168           //bytesPushed+=4;
 169           bytesPushed += getSize(operandType(left));
 170         }
 171       addiCodeToeBBlock (ebp, newic, ip);
 172       newic->lineno = lineno;
 173     }
 174   /* insert the call */
 175   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 176   IC_RESULT (newic) = IC_RESULT (ic);
 177   newic->lineno = lineno;
 178   newic->parmBytes+=bytesPushed;
 179
 180   if(TARGET_IS_PIC16) {
 181         /* normally these functions aren't marked external, so we can use their
 182          * _extern field to marked as already added to symbol table */
 183
 184         if(!SPEC_EXTR(func->etype)) {
 185             memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
 186
 187                 SPEC_EXTR(func->etype) = 1;
 188                 seg = SPEC_OCLS( func->etype );
 189                 addSet(&seg->syms, func);
 190         }
 191   }
 192
 193   addiCodeToeBBlock (ebp, newic, ip);
 194 }
 195
 196 /*-----------------------------------------------------------------*/
 197 /* cnvToFloatCast - converts casts to floats to function calls     */
 198 /*-----------------------------------------------------------------*/
 199 static void
 200 cnvToFloatCast (iCode * ic, eBBlock * ebp)
 201 {
 202   iCode *ip, *newic;
 203   symbol *func = NULL;
 204   sym_link *type = operandType (IC_RIGHT (ic));
 205   int linenno = ic->lineno;
 206   int bwd, su;
 207   int bytesPushed=0;
 208
 209   ip = ic->next;
 210   /* remove it from the iCode */
 211   remiCodeFromeBBlock (ebp, ic);
 212   /* depending on the type */
 213   for (bwd = 0; bwd < 3; bwd++)
 214     {
 215       for (su = 0; su < 2; su++)
 216         {
 217           if (compareType (type, __multypes[bwd][su]) == 1)
 218             {
 219               func = __conv[0][bwd][su];
 220               goto found;
 221             }
 222         }
 223     }
 224   assert (0);
 225 found:
 226
 227   /* if float support routines NOT compiled as reentrant */
 228   if (!options.float_rent)
 229     {
 230       /* first one */
 231         if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 232             {
 233                 newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 234                 newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 235             }
 236       else
 237         {
 238           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 239           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 240         }
 241       addiCodeToeBBlock (ebp, newic, ip);
 242       newic->lineno = linenno;
 243
 244     }
 245   else
 246     {
 247       /* push the left */
 248         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 249             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 250             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 251         }
 252       else
 253         {
 254           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 255           newic->parmPush = 1;
 256           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 257         }
 258       addiCodeToeBBlock (ebp, newic, ip);
 259       newic->lineno = linenno;
 260
 261     }
 262
 263   /* make the call */
 264   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 265   IC_RESULT (newic) = IC_RESULT (ic);
 266   newic->parmBytes+=bytesPushed;
 267
 268   if(TARGET_IS_PIC16) {
 269         /* normally these functions aren't marked external, so we can use their
 270          * _extern field to marked as already added to symbol table */
 271
 272         if(!SPEC_EXTR(func->etype)) {
 273             memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
 274
 275                 SPEC_EXTR(func->etype) = 1;
 276                 seg = SPEC_OCLS( func->etype );
 277                 addSet(&seg->syms, func);
 278         }
 279   }
 280
 281   addiCodeToeBBlock (ebp, newic, ip);
 282   newic->lineno = linenno;
 283 }
 284
 285 /*-----------------------------------------------------------------*/
 286 /* cnvFromFloatCast - converts casts From floats to function calls */
 287 /*-----------------------------------------------------------------*/
 288 static void
 289 cnvFromFloatCast (iCode * ic, eBBlock * ebp)
 290 {
 291   iCode *ip, *newic;
 292   symbol *func = NULL;
 293   sym_link *type = operandType (IC_LEFT (ic));
 294   int lineno = ic->lineno;
 295   int bwd, su;
 296   int bytesPushed=0;
 297
 298   ip = ic->next;
 299   /* remove it from the iCode */
 300   remiCodeFromeBBlock (ebp, ic);
 301
 302   /* depending on the type */
 303   for (bwd = 0; bwd < 3; bwd++)
 304     {
 305       for (su = 0; su < 2; su++)
 306         {
 307           if (compareType (type, __multypes[bwd][su]) == 1)
 308             {
 309               func = __conv[1][bwd][su];
 310               goto found;
 311             }
 312         }
 313     }
 314   assert (0);
 315 found:
 316
 317   /* if float support routines NOT compiled as reentrant */
 318   if (!options.float_rent)
 319     {
 320       /* first one */
 321         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 322             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 323             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 324         }
 325       else
 326         {
 327           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 328           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 329         }
 330       addiCodeToeBBlock (ebp, newic, ip);
 331       newic->lineno = lineno;
 332
 333     }
 334   else
 335     {
 336
 337       /* push the left */
 338         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 339             newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 340             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 341         }
 342       else
 343         {
 344           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 345           newic->parmPush = 1;
 346           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 347         }
 348       addiCodeToeBBlock (ebp, newic, ip);
 349       newic->lineno = lineno;
 350
 351     }
 352
 353   /* make the call */
 354   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 355   IC_RESULT (newic) = IC_RESULT (ic);
 356   newic->parmBytes+=bytesPushed;
 357
 358   if(TARGET_IS_PIC16) {
 359         /* normally these functions aren't marked external, so we can use their
 360          * _extern field to marked as already added to symbol table */
 361
 362         if(!SPEC_EXTR(func->etype)) {
 363             memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
 364
 365                 SPEC_EXTR(func->etype) = 1;
 366                 seg = SPEC_OCLS( func->etype );
 367                 addSet(&seg->syms, func);
 368         }
 369   }
 370
 371   addiCodeToeBBlock (ebp, newic, ip);
 372   newic->lineno = lineno;
 373 }
 374
 375 extern operand *geniCodeRValue (operand *, bool);
 376
 377 /*-----------------------------------------------------------------*/
 378 /* convilong - converts int or long mults or divs to fcalls        */
 379 /*-----------------------------------------------------------------*/
 380 static void
 381 convilong (iCode * ic, eBBlock * ebp, sym_link * type, int op)
 382 {
 383   symbol *func = NULL;
 384   iCode *ip = ic->next;
 385   iCode *newic;
 386   int lineno = ic->lineno;
 387   int bwd;
 388   int su;
 389   int bytesPushed=0;
 390
 391   // Easy special case which avoids function call: modulo by a literal power
 392   // of two can be replaced by a bitwise AND.
 393   if (op == '%' && isOperandLiteral(IC_RIGHT(ic)))
 394   {
 395       unsigned litVal = (unsigned)(operandLitValue(IC_RIGHT(ic)));
 396
 397       // See if literal value is a power of 2.
 398       while (litVal && !(litVal & 1))
 399       {
 400           litVal >>= 1;
 401       }
 402       if (litVal)
 403       {
 404           // discard first high bit set.
 405           litVal >>= 1;
 406       }
 407
 408       if (!litVal)
 409       {
 410           ic->op = BITWISEAND;
 411           IC_RIGHT(ic) = operandFromLit(operandLitValue(IC_RIGHT(ic)) - 1);
 412           return;
 413       }
 414   }
 415
 416   remiCodeFromeBBlock (ebp, ic);
 417
 418
 419   /* depending on the type */
 420   for (bwd = 0; bwd < 3; bwd++)
 421     {
 422       for (su = 0; su < 2; su++)
 423         {
 424           if (compareType (type, __multypes[bwd][su]) == 1)
 425             {
 426               if (op == '*')
 427                 func = __muldiv[0][bwd][su];
 428               else if (op == '/')
 429                 func = __muldiv[1][bwd][su];
 430               else if (op == '%')
 431                 func = __muldiv[2][bwd][su];
 432               else if (op == RRC)
 433                 func = __rlrr[1][bwd][su];
 434               else if (op == RLC)
 435                 func = __rlrr[0][bwd][su];
 436               else if (op == RIGHT_OP)
 437                 func = __rlrr[1][bwd][su];
 438               else if (op == LEFT_OP)
 439                 func = __rlrr[0][bwd][su];
 440               else
 441                 assert (0);
 442               goto found;
 443             }
 444         }
 445     }
 446   assert (0);
 447 found:
 448   /* if int & long support routines NOT compiled as reentrant */
 449   if (!options.intlong_rent)
 450     {
 451       /* first one */
 452         if (IS_REGPARM (FUNC_ARGS(func->type)->etype)) {
 453             newic = newiCode (SEND, IC_LEFT (ic), NULL);
 454             newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 455         }
 456       else
 457         {
 458           newic = newiCode ('=', NULL, IC_LEFT (ic));
 459           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type));
 460         }
 461       addiCodeToeBBlock (ebp, newic, ip);
 462       newic->lineno = lineno;
 463
 464       /* second one */
 465       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype)) {
 466           newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 467           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 468       }
 469       else
 470         {
 471           newic = newiCode ('=', NULL, IC_RIGHT (ic));
 472           IC_RESULT (newic) = operandFromValue (FUNC_ARGS(func->type)->next);
 473         }
 474       addiCodeToeBBlock (ebp, newic, ip);
 475       newic->lineno = lineno;
 476
 477     }
 478   else
 479     {
 480       /* compiled as reentrant then push */
 481       /* push right */
 482       if (IS_REGPARM (FUNC_ARGS(func->type)->next->etype))
 483         {
 484           newic = newiCode (SEND, IC_RIGHT (ic), NULL);
 485           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->next->etype);
 486         }
 487       else
 488         {
 489           newic = newiCode (IPUSH, IC_RIGHT (ic), NULL);
 490           newic->parmPush = 1;
 491
 492           bytesPushed += getSize(operandType(IC_RIGHT(ic)));
 493         }
 494       addiCodeToeBBlock (ebp, newic, ip);
 495       newic->lineno = lineno;
 496
 497       /* insert push left */
 498       if (IS_REGPARM (FUNC_ARGS(func->type)->etype))
 499         {
 500           newic = newiCode (SEND, IC_LEFT (ic), NULL);
 501           newic->argreg = SPEC_ARGREG(FUNC_ARGS(func->type)->etype);
 502         }
 503       else
 504         {
 505           newic = newiCode (IPUSH, IC_LEFT (ic), NULL);
 506           newic->parmPush = 1;
 507
 508           bytesPushed += getSize(operandType(IC_LEFT(ic)));
 509         }
 510       addiCodeToeBBlock (ebp, newic, ip);
 511       newic->lineno = lineno;
 512
 513     }
 514
 515   /* for the result */
 516   newic = newiCode (CALL, operandFromSymbol (func), NULL);
 517   IC_RESULT (newic) = IC_RESULT (ic);
 518   newic->lineno = lineno;
 519   newic->parmBytes+=bytesPushed; // to clear the stack after the call
 520
 521   if(TARGET_IS_PIC16) {
 522         /* normally these functions aren't marked external, so we can use their
 523          * _extern field to marked as already added to symbol table */
 524
 525         if(!SPEC_EXTR(func->etype)) {
 526             memmap *seg = SPEC_OCLS(OP_SYMBOL(IC_LEFT(newic))->etype);
 527
 528                 SPEC_EXTR(func->etype) = 1;
 529                 seg = SPEC_OCLS( func->etype );
 530                 addSet(&seg->syms, func);
 531         }
 532   }
 533
 534   addiCodeToeBBlock (ebp, newic, ip);
 535 }
 536
 537 /*-----------------------------------------------------------------*/
 538 /* convertToFcall - converts some operations to fcalls             */
 539 /*-----------------------------------------------------------------*/
 540 static void
 541 convertToFcall (eBBlock ** ebbs, int count)
 542 {
 543   int i;
 544
 545   /* for all blocks do */
 546   for (i = 0; i < count; i++)
 547     {
 548       iCode *ic;
 549
 550       /* for all instructions in the block do */
 551       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 552         {
 553
 554           /* floating point operations are
 555              converted to function calls */
 556           if ((IS_CONDITIONAL (ic) ||
 557                IS_ARITHMETIC_OP (ic)) &&
 558               (IS_FLOAT (operandType (IC_RIGHT (ic)))))
 559             {
 560
 561               cnvToFcall (ic, ebbs[i]);
 562             }
 563
 564           /* casting is a little different */
 565           if (ic->op == CAST)
 566             {
 567               if (IS_FLOAT (operandType (IC_RIGHT (ic))))
 568                 cnvFromFloatCast (ic, ebbs[i]);
 569               else if (IS_FLOAT (operandType (IC_LEFT (ic))))
 570                 cnvToFloatCast (ic, ebbs[i]);
 571             }
 572
 573           /* if long / int mult or divide or mod */
 574           if (ic->op == '*' || ic->op == '/' || ic->op == '%')
 575             {
 576               sym_link *leftType = operandType (IC_LEFT (ic));
 577
 578               if (IS_INTEGRAL (leftType) && getSize (leftType) > port->support.muldiv)
 579                 {
 580                   sym_link *rightType = operandType (IC_RIGHT (ic));
 581
 582                   if (port->hasNativeMulFor != NULL &&
 583                       port->hasNativeMulFor (ic, leftType, rightType))
 584                     {
 585                       /* Leave as native */
 586                     }
 587                   else
 588                     {
 589                       convilong (ic, ebbs[i], leftType, ic->op);
 590                     }
 591                 }
 592             }
 593
 594           if (ic->op == RRC || ic->op == RLC || ic->op == LEFT_OP || ic->op == RIGHT_OP)
 595             {
 596               sym_link *type = operandType (IC_LEFT (ic));
 597
 598               if (IS_INTEGRAL (type) && getSize (type) > port->support.shift && port->support.shift >= 0)
 599                 {
 600                   convilong (ic, ebbs[i], type, ic->op);
 601                 }
 602             }
 603         }
 604     }
 605 }
 606
 607 /*-----------------------------------------------------------------*/
 608 /* isLocalWithoutDef - return 1 if sym might be used without a     */
 609 /*                     defining iCode                              */
 610 /*-----------------------------------------------------------------*/
 611 static int
 612 isLocalWithoutDef (symbol * sym)
 613 {
 614   if (!sym->level)
 615     return 0;
 616
 617   if (IS_STATIC (sym->etype))
 618     return 0;
 619
 620   if (IS_VOLATILE (sym->type))
 621     return 0;
 622
 623   if (sym->_isparm)
 624     return 0;
 625
 626   if (IS_AGGREGATE (sym->type))
 627     return 0;
 628
 629   if (sym->addrtaken)
 630     return 0;
 631
 632   return !sym->defs;
 633 }
 634
 635 /*-----------------------------------------------------------------*/
 636 /* replaceRegEqv - replace all local variables with their reqv     */
 637 /*-----------------------------------------------------------------*/
 638 static void
 639 replaceRegEqv (eBBlock ** ebbs, int count)
 640 {
 641   int i;
 642
 643   /* Update the symbols' def bitvector so we know if there is   */
 644   /* a defining iCode or not. Only replace a local variable     */
 645   /* with its register equivalent if there is a defining iCode; */
 646   /* otherwise, the port's register allocater may choke.        */
 647   cseAllBlocks (ebbs, count, TRUE);
 648
 649   for (i = 0; i < count; i++)
 650     {
 651
 652       iCode *ic;
 653
 654       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 655         {
 656
 657           if (SKIP_IC2 (ic))
 658             continue;
 659
 660           if (ic->op == IFX)
 661             {
 662               if (IC_COND (ic) &&
 663                   IS_TRUE_SYMOP (IC_COND (ic)) &&
 664                   isLocalWithoutDef (OP_SYMBOL (IC_COND (ic))))
 665                 {
 666                   werrorfl (ic->filename, ic->lineno,
 667                           W_LOCAL_NOINIT,
 668                           OP_SYMBOL (IC_COND (ic))->name);
 669                   OP_REQV (IC_COND (ic)) = NULL;
 670                   OP_SYMBOL (IC_COND (ic))->allocreq = 1;
 671                 }
 672
 673               if (IS_TRUE_SYMOP (IC_COND (ic)) &&
 674                   OP_REQV (IC_COND (ic)))
 675                 IC_COND (ic) = opFromOpWithDU (OP_REQV (IC_COND (ic)),
 676                                              OP_SYMBOL (IC_COND (ic))->defs,
 677                                             OP_SYMBOL (IC_COND (ic))->uses);
 678
 679               continue;
 680             }
 681
 682
 683           if (ic->op == JUMPTABLE)
 684             {
 685               if (IC_JTCOND (ic) &&
 686                   IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
 687                   isLocalWithoutDef (OP_SYMBOL (IC_JTCOND (ic))))
 688                 {
 689                   werrorfl (ic->filename, ic->lineno,
 690                           W_LOCAL_NOINIT,
 691                           OP_SYMBOL (IC_JTCOND (ic))->name);
 692                   OP_REQV (IC_JTCOND (ic)) = NULL;
 693                   OP_SYMBOL (IC_JTCOND (ic))->allocreq = 1;
 694                 }
 695
 696               if (IS_TRUE_SYMOP (IC_JTCOND (ic)) &&
 697                   OP_REQV (IC_JTCOND (ic)))
 698                 IC_JTCOND (ic) = opFromOpWithDU (OP_REQV (IC_JTCOND (ic)),
 699                                            OP_SYMBOL (IC_JTCOND (ic))->defs,
 700                                           OP_SYMBOL (IC_JTCOND (ic))->uses);
 701               continue;
 702             }
 703
 704           if (ic->op == RECEIVE)
 705             {
 706               if (OP_SYMBOL (IC_RESULT (ic))->addrtaken)
 707                 OP_SYMBOL (IC_RESULT (ic))->isspilt = 1;
 708             }
 709
 710           /* general case */
 711           if (IC_RESULT (ic) &&
 712               IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 713               OP_REQV (IC_RESULT (ic)))
 714             {
 715               if (POINTER_SET (ic))
 716                 {
 717                   IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
 718                                            OP_SYMBOL (IC_RESULT (ic))->defs,
 719                                           OP_SYMBOL (IC_RESULT (ic))->uses);
 720                   IC_RESULT (ic)->isaddr = 1;
 721                 }
 722               else
 723                 IC_RESULT (ic) = opFromOpWithDU (OP_REQV (IC_RESULT (ic)),
 724                                            OP_SYMBOL (IC_RESULT (ic))->defs,
 725                                           OP_SYMBOL (IC_RESULT (ic))->uses);
 726             }
 727
 728           if (IC_RIGHT (ic) &&
 729               IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
 730               isLocalWithoutDef (OP_SYMBOL (IC_RIGHT (ic))))
 731             {
 732               werrorfl (ic->filename, ic->lineno,
 733                         W_LOCAL_NOINIT,
 734                         OP_SYMBOL (IC_RIGHT (ic))->name);
 735               OP_REQV (IC_RIGHT (ic)) = NULL;
 736               OP_SYMBOL (IC_RIGHT (ic))->allocreq = 1;
 737             }
 738
 739           if (IC_RIGHT (ic) &&
 740               IS_TRUE_SYMOP (IC_RIGHT (ic)) &&
 741               OP_REQV (IC_RIGHT (ic)))
 742             {
 743               IC_RIGHT (ic) = opFromOpWithDU (OP_REQV (IC_RIGHT (ic)),
 744                                             OP_SYMBOL (IC_RIGHT (ic))->defs,
 745                                            OP_SYMBOL (IC_RIGHT (ic))->uses);
 746               IC_RIGHT (ic)->isaddr = 0;
 747             }
 748
 749           if (IC_LEFT (ic) &&
 750               IS_TRUE_SYMOP (IC_LEFT (ic)) &&
 751               isLocalWithoutDef (OP_SYMBOL (IC_LEFT (ic))))
 752             {
 753               werrorfl (ic->filename, ic->lineno,
 754                         W_LOCAL_NOINIT,
 755                         OP_SYMBOL (IC_LEFT (ic))->name);
 756               OP_REQV (IC_LEFT (ic)) = NULL;
 757               OP_SYMBOL (IC_LEFT (ic))->allocreq = 1;
 758             }
 759
 760           if (IC_LEFT (ic) &&
 761               IS_TRUE_SYMOP (IC_LEFT (ic)) &&
 762               OP_REQV (IC_LEFT (ic)))
 763             {
 764               IC_LEFT (ic) = opFromOpWithDU (OP_REQV (IC_LEFT (ic)),
 765                                              OP_SYMBOL (IC_LEFT (ic))->defs,
 766                                              OP_SYMBOL (IC_LEFT (ic))->uses);
 767               IC_LEFT (ic)->isaddr = 0;
 768             }
 769         }
 770     }
 771 }
 772
 773 /*-----------------------------------------------------------------*/
 774 /* killDeadCode - eliminates dead assignments                      */
 775 /*-----------------------------------------------------------------*/
 776 int
 777 killDeadCode (eBBlock ** ebbs, int count)
 778 {
 779   int change = 1;
 780   int gchange = 0;
 781   int i = 0;
 782
 783
 784   /* basic algorithm :-                                          */
 785   /* first the exclusion rules :-                                */
 786   /*  1. if result is a global or volatile then skip             */
 787   /*  2. if assignment and result is a temp & isaddr  then skip  */
 788   /*     since this means array & pointer access, will be taken  */
 789   /*     care of by alias analysis.                              */
 790   /*  3. if the result is used in the remainder of the block skip */
 791   /*  4. if this definition does not reach the end of the block  */
 792   /*     i.e. the result is not present in the outExprs then KILL */
 793   /*  5. if it reaches the end of block & is used by some success */
 794   /*     or then skip                                            */
 795   /*     else            KILL                                    */
 796   /* this whole process is carried on iteratively till no change */
 797   while (1)
 798     {
 799
 800       change = 0;
 801       /* for all blocks do */
 802       for (i = 0; i < count; i++)
 803         {
 804           iCode *ic;
 805
 806           /* for all instructions in the block do */
 807           for (ic = ebbs[i]->sch; ic; ic = ic->next)
 808             {
 809               int kill, j;
 810               kill = 0;
 811
 812               if (SKIP_IC (ic) ||
 813                   ic->op == IFX ||
 814                   ic->op == RETURN ||
 815                   ic->op == DUMMY_READ_VOLATILE ||
 816                   ic->op == CRITICAL ||
 817                   ic->op == ENDCRITICAL)
 818                 continue;
 819
 820               /* Since both IFX & JUMPTABLE (in SKIP_IC) have been tested for */
 821               /* it is now safe to assume IC_LEFT, IC_RIGHT, & IC_RESULT are  */
 822               /* valid. */
 823
 824               /* if the result is volatile then continue */
 825               if (IC_RESULT (ic) && isOperandVolatile (IC_RESULT (ic), FALSE))
 826                 continue;
 827
 828               /* if the result is a temp & isaddr then skip */
 829               if (IC_RESULT (ic) && POINTER_SET (ic))
 830                 continue;
 831
 832               if (POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT (ic))->next))
 833                 continue;
 834
 835               /* if the result is used in the remainder of the */
 836               /* block then skip */
 837               if (usedInRemaining (IC_RESULT (ic), ic->next))
 838                 continue;
 839
 840               /* does this definition reach the end of the block
 841                  or the usage is zero then we can kill */
 842               if (!bitVectBitValue (ebbs[i]->outDefs, ic->key))
 843                 kill = 1;       /* if not we can kill it */
 844               else
 845                 {
 846                   /* if this is a global variable or function parameter */
 847                   /* we cannot kill anyway             */
 848                   if (isOperandGlobal (IC_RESULT (ic)) ||
 849                       (OP_SYMBOL (IC_RESULT (ic))->_isparm &&
 850                        !OP_SYMBOL (IC_RESULT (ic))->ismyparm))
 851                     continue;
 852
 853                   /* if we are sure there are no usages */
 854                   if (bitVectIsZero (OP_USES (IC_RESULT (ic))))
 855                     {
 856                       kill = 1;
 857                       goto kill;
 858                     }
 859
 860                   /* reset visited flag */
 861                   for (j = 0; j < count; ebbs[j++]->visited = 0);
 862
 863                   /* find out if this definition is alive */
 864                   if (applyToSet (ebbs[i]->succList,
 865                                   isDefAlive,
 866                                   ic))
 867                     continue;
 868
 869                   kill = 1;
 870                 }
 871
 872             kill:
 873               /* kill this one if required */
 874               if (kill)
 875                 {
 876                   bool volLeft = IS_SYMOP (IC_LEFT (ic))
 877                                  && isOperandVolatile (IC_LEFT (ic), FALSE);
 878                   bool volRight = IS_SYMOP (IC_RIGHT (ic))
 879                                   && isOperandVolatile (IC_RIGHT (ic), FALSE);
 880
 881                   /* a dead address-of operation should die, even if volatile */
 882                   if (ic->op == ADDRESS_OF)
 883                     volLeft = FALSE;
 884
 885                   if (ic->next && ic->seqPoint == ic->next->seqPoint
 886                       && (ic->next->op == '+' || ic->next->op == '-'))
 887                     {
 888                       if (isOperandEqual (IC_LEFT(ic), IC_LEFT(ic->next))
 889                           || isOperandEqual (IC_LEFT(ic), IC_RIGHT(ic->next)))
 890                         volLeft = FALSE;
 891                       if (isOperandEqual (IC_RIGHT(ic), IC_LEFT(ic->next))
 892                           || isOperandEqual (IC_RIGHT(ic), IC_RIGHT(ic->next)))
 893                         volRight = FALSE;
 894                     }
 895
 896                   change = 1;
 897                   gchange++;
 898
 899                   /* now delete from defUseSet */
 900                   deleteItemIf (&ebbs[i]->outExprs, ifDiCodeIsX, ic);
 901                   bitVectUnSetBit (ebbs[i]->outDefs, ic->key);
 902
 903                   /* and defset of the block */
 904                   bitVectUnSetBit (ebbs[i]->defSet, ic->key);
 905
 906                   /* delete the result */
 907                   IC_RESULT (ic) = NULL;
 908
 909                   if (volLeft || volRight)
 910                     {
 911                       /* something is volatile, so keep the iCode */
 912                       /* and change the operator instead */
 913                       ic->op = DUMMY_READ_VOLATILE;
 914
 915                       /* keep only the volatile operands */
 916                       if (!volLeft)
 917                         IC_LEFT (ic) = NULL;
 918                       if (!volRight)
 919                         IC_RIGHT (ic) = NULL;
 920                     }
 921                   else
 922                     {
 923                       /* nothing is volatile, eliminate the iCode */
 924                       remiCodeFromeBBlock (ebbs[i], ic);
 925
 926                       /* for the left & right remove the usage */
 927                       if (IS_SYMOP (IC_LEFT (ic)))
 928                         bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
 929
 930                       if (IS_SYMOP (IC_RIGHT (ic)))
 931                         bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
 932                     }
 933                 }
 934
 935             }                   /* end of all instructions */
 936
 937           if (!ebbs[i]->sch && !ebbs[i]->noPath)
 938             disconBBlock (ebbs[i], ebbs, count);
 939
 940         }                       /* end of for all blocks */
 941
 942       if (!change)
 943         break;
 944     }                           /* end of while(1) */
 945
 946   return gchange;
 947 }
 948
 949 /*-----------------------------------------------------------------*/
 950 /* printCyclomatic - prints the cyclomatic information             */
 951 /*-----------------------------------------------------------------*/
 952 static void
 953 printCyclomatic (eBBlock ** ebbs, int count)
 954 {
 955   int nEdges = elementsInSet (graphEdges);
 956   int i, nNodes = 0;
 957
 958   for (i = 0; i < count; i++)
 959     nNodes += (!ebbs[i]->noPath);
 960
 961   /* print the information */
 962   werror (I_CYCLOMATIC, currFunc->name, nEdges, nNodes, nEdges - nNodes + 2);
 963 }
 964
 965 /*-----------------------------------------------------------------*/
 966 /* discardDeadParamReceives - remove any RECEIVE opcodes which     */
 967 /* refer to dead variables.                                        */
 968 /*-----------------------------------------------------------------*/
 969 static void
 970 discardDeadParamReceives (eBBlock ** ebbs, int count)
 971 {
 972   int i;
 973   iCode *ic;
 974   iCode dummyIcode;
 975
 976   for (i = 0; i < count; i++)
 977     {
 978       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 979         {
 980           if (ic->op == RECEIVE)
 981             {
 982               if (IC_RESULT (ic) && OP_SYMBOL (IC_RESULT (ic))
 983                   && !OP_SYMBOL (IC_RESULT (ic))->used)
 984                 {
 985 #if 0
 986                   fprintf (stderr, "discarding dead receive for %s\n",
 987                            OP_SYMBOL (IC_RESULT (ic))->name);
 988 #endif
 989                   dummyIcode.next = ic->next;
 990                   remiCodeFromeBBlock (ebbs[i], ic);
 991                   ic = &dummyIcode;
 992                 }
 993             }
 994         }
 995     }
 996 }
 997
 998 /*-----------------------------------------------------------------*/
 999 /* eBBlockFromiCode - creates extended basic blocks from iCode     */
1000 /*                    will return an array of eBBlock pointers     */
1001 /*-----------------------------------------------------------------*/
1002 eBBlock **
1003 eBBlockFromiCode (iCode * ic)
1004 {
1005   eBBlock **ebbs = NULL;
1006   int count = 0;
1007   int saveCount = 0;
1008   int change = 1;
1009   int lchange = 0;
1010   int kchange = 0;
1011   hTab *loops;
1012
1013   /* if nothing passed then return nothing */
1014   if (!ic)
1015     return NULL;
1016
1017   count = 0;
1018   eBBNum = 0;
1019
1020   /* optimize the chain for labels & gotos
1021      this will eliminate redundant labels and
1022      will change jump to jumps by jumps */
1023   ic = iCodeLabelOptimize (ic);
1024
1025   /* break it down into basic blocks */
1026   ebbs = iCodeBreakDown (ic, &count);
1027   saveCount = count;
1028
1029   /* hash the iCode keys so that we can quickly index */
1030   /* them in the rest of the optimization steps */
1031   setToNull ((void *) &iCodehTab);
1032   iCodehTab = newHashTable (iCodeKey);
1033   hashiCodeKeys (ebbs, count);
1034
1035   /* compute the control flow */
1036   computeControlFlow (ebbs, count, 0);
1037
1038   /* dumpraw if asked for */
1039   if (options.dump_raw)
1040     dumpEbbsToFileExt (DUMP_RAW0, ebbs, count);
1041
1042   /* replace the local variables with their
1043      register equivalents : the liveRange computation
1044      along with the register allocation will determine
1045      if it finally stays in the registers */
1046   replaceRegEqv (ebbs, count);
1047
1048   /* create loop regions */
1049   loops = createLoopRegions (ebbs, count);
1050
1051   /* dumpraw if asked for */
1052   if (options.dump_raw)
1053     dumpEbbsToFileExt (DUMP_RAW1, ebbs, count);
1054
1055   /* do common subexpression elimination for each block */
1056   change = cseAllBlocks (ebbs, saveCount, FALSE);
1057
1058   /* dumpraw if asked for */
1059   if (options.dump_raw)
1060     dumpEbbsToFileExt (DUMP_CSE, ebbs, count);
1061
1062   /* compute the data flow */
1063   computeDataFlow (ebbs, saveCount);
1064
1065   /* dumpraw if asked for */
1066   if (options.dump_raw)
1067     dumpEbbsToFileExt (DUMP_DFLOW, ebbs, count);
1068
1069   /* global common subexpression elimination  */
1070   if (optimize.global_cse)
1071     {
1072       change += cseAllBlocks (ebbs, saveCount, FALSE);
1073       if (options.dump_gcse)
1074         dumpEbbsToFileExt (DUMP_GCSE, ebbs, saveCount);
1075     }
1076   else
1077     {
1078       // compute the dataflow only
1079       assert(cseAllBlocks (ebbs, saveCount, TRUE)==0);
1080     }
1081   /* kill dead code */
1082   kchange = killDeadCode (ebbs, saveCount);
1083
1084   if (options.dump_kill)
1085     dumpEbbsToFileExt (DUMP_DEADCODE, ebbs, count);
1086
1087   /* do loop optimizations */
1088   change += (lchange = loopOptimizations (loops, ebbs, count));
1089   if (options.dump_loop)
1090     dumpEbbsToFileExt (DUMP_LOOP, ebbs, count);
1091
1092   /* recompute the data flow and apply global cse again
1093      if loops optimizations or dead code caused a change:
1094      loops will brings out of the loop which then may be
1095      available for use in the later blocks: dead code
1096      elimination could potentially disconnect some blocks
1097      conditional flow may be efected so we need to apply
1098      subexpression once more */
1099   if (lchange || kchange)
1100     {
1101       computeDataFlow (ebbs, saveCount);
1102       change += cseAllBlocks (ebbs, saveCount, FALSE);
1103       if (options.dump_loop)
1104         dumpEbbsToFileExt (DUMP_LOOPG, ebbs, count);
1105
1106       /* if loop optimizations caused a change then do
1107          dead code elimination once more : this will
1108          get rid of the extra assignments to the induction
1109          variables created during loop optimizations */
1110       killDeadCode (ebbs, saveCount);
1111
1112       if (options.dump_loop)
1113         dumpEbbsToFileExt (DUMP_LOOPD, ebbs, count);
1114
1115     }
1116
1117   /* sort it back by block number */
1118   qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
1119
1120   if (!options.lessPedantic) {
1121     // this is a good place to check missing return values
1122     if (currFunc) {
1123       // the user is on his own with naked functions...
1124       if (!IS_VOID(currFunc->etype)
1125        && !FUNC_ISNAKED(currFunc->type)) {
1126         eBBlock *bp;
1127         // make sure all predecessors of the last block end in a return
1128         for (bp=setFirstItem(ebbs[saveCount-1]->predList);
1129              bp;
1130              bp=setNextItem(ebbs[saveCount-1]->predList)) {
1131           if (bp->ech->op != RETURN) {
1132             werrorfl (bp->ech->filename, bp->ech->lineno,
1133                       W_VOID_FUNC, currFunc->name);
1134           }
1135         }
1136       }
1137     }
1138   }
1139
1140   /* if cyclomatic info requested then print it */
1141   if (options.cyclomatic)
1142     printCyclomatic (ebbs, saveCount);
1143
1144   /* convert operations with support routines
1145      written in C to function calls : Iam doing
1146      this at this point since I want all the
1147      operations to be as they are for optimzations */
1148   convertToFcall (ebbs, count);
1149
1150   /* compute the live ranges */
1151   computeLiveRanges (ebbs, count);
1152
1153   if (options.dump_range)
1154     dumpEbbsToFileExt (DUMP_RANGE, ebbs, count);
1155
1156   /* Now that we have the live ranges, discard parameter
1157    * receives for unused parameters.
1158    */
1159   discardDeadParamReceives (ebbs, count);
1160
1161   /* allocate registers & generate code */
1162   port->assignRegisters (ebbs, count);
1163
1164   /* throw away blocks */
1165   setToNull ((void *) &graphEdges);
1166   ebbs = NULL;
1167
1168   return NULL;
1169 }
1170
1171
1172 /* (add-hook 'c-mode-hook (lambda () (setq c-basic-offset 4))) */