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

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