sdcc/src/SDCClabel.c

   1 /*-----------------------------------------------------------------
   2     SDCClabel.c - label optimizations on iCode (intermediate code)
   3
   4     Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
   5
   6     This program is free software; you can redistribute it and/or modify it
   7     under the terms of the GNU General Public License as published by the
   8     Free Software Foundation; either version 2, or (at your option) any
   9     later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19
  20     In other words, you are welcome to use, share and improve this program.
  21     You are forbidden to forbid anyone else to use, share and improve
  22     what you give them.   Help stamp out software-hoarding!
  23 -------------------------------------------------------------------------*/
  24
  25 #include "common.h"
  26
  27 hTab *labelRef = NULL;
  28 hTab *labelDef = NULL;
  29
  30 /*-----------------------------------------------------------------*/
  31 /* buildLabelRefTable - creates an hashTable of label references   */
  32 /*-----------------------------------------------------------------*/
  33 void
  34 buildLabelRefTable (iCode * ic)
  35 {
  36   iCode *lic;
  37
  38   setToNull ((void *) &labelRef);
  39   setToNull ((void *) &labelDef);
  40   labelRef = newHashTable (labelKey + 1);
  41   labelDef = newHashTable (labelKey + 1);
  42
  43   for (lic = ic; lic; lic = lic->next)
  44     {
  45       if (lic->op == GOTO)
  46         hTabAddItem (&labelRef, (IC_LABEL (lic))->key, lic);
  47
  48       if (lic->op == JUMPTABLE)
  49         {
  50           symbol *lbl;
  51           for (lbl = setFirstItem (IC_JTLABELS (lic)); lbl;
  52                lbl = setNextItem (IC_JTLABELS (lic)))
  53             {
  54               hTabAddItem (&labelRef, lbl->key, lic);
  55             }
  56         }
  57
  58       if (lic->op == IFX)
  59         {
  60           if (IC_TRUE (lic))
  61             hTabAddItem (&labelRef, (IC_TRUE (lic))->key, lic);
  62           else
  63             hTabAddItem (&labelRef, (IC_FALSE (lic))->key, lic);
  64         }
  65       if (lic->op == LABEL)
  66         hTabAddItem (&labelDef, (IC_LABEL (lic))->key, lic);
  67
  68     }
  69 }
  70
  71 /*-----------------------------------------------------------------*/
  72 /* labelGotoNext - kills gotos to next statement                   */
  73 /*-----------------------------------------------------------------*/
  74 int
  75 labelGotoNext (iCode * ic)
  76 {
  77   iCode *loop;
  78   int change = 0;
  79
  80   for (loop = ic; loop; loop = loop->next)
  81     {
  82
  83       if (loop->op == GOTO &&   /* if this is a goto */
  84           loop->next &&         /* and we have a next one */
  85           loop->next->op == LABEL &&    /* next one is a label */
  86           loop->next->label->key == loop->label->key)   /* same label */
  87         {
  88           loop->prev->next = loop->next;        /* get this out of the chain */
  89           loop->next->prev = loop->prev;
  90           hTabDeleteItem (&labelRef, (IC_LABEL (loop))->key, loop, DELETE_ITEM, NULL);
  91           change++;
  92         }
  93     }
  94
  95   return change;
  96 }
  97
  98 /*-------------------------------------------------------------------*/
  99 /* deleteIfx - delete an IFX iCode or convert to DUMMY_READ_VOLATILE */
 100 /*-------------------------------------------------------------------*/
 101 static void
 102 deleteIfx (iCode * loop, int key)
 103 {
 104   if (!loop->inlined)
 105     werrorfl (loop->filename, loop->lineno, W_CONTROL_FLOW);
 106   hTabDeleteItem (&labelRef, key, loop, DELETE_ITEM, NULL);
 107
 108   /* If the condition was volatile, convert IFX to */
 109   /* DUMMY_READ_VOLATILE. Otherwise just delete the */
 110   /* IFX iCode */
 111   if (IS_OP_VOLATILE (IC_COND (loop)))
 112     {
 113       IC_RIGHT (loop) = IC_COND (loop);
 114       IC_LEFT (loop) = NULL;
 115       IC_RESULT (loop) = NULL;
 116       loop->op = DUMMY_READ_VOLATILE;
 117     }
 118   else
 119     {
 120       loop->prev->next = loop->next;
 121       loop->next->prev = loop->prev;
 122     }
 123 }
 124
 125
 126 /*-----------------------------------------------------------------*/
 127 /* labelIfx - special case Ifx elimination                         */
 128 /*-----------------------------------------------------------------*/
 129 int
 130 labelIfx (iCode * ic)
 131 {
 132   iCode *loop;
 133   iCode *stat;
 134   int change = 0;
 135
 136   for (loop = ic; loop; loop = loop->next)
 137     {
 138       /*   if  condition  goto label */
 139       /*   goto label                */
 140       /* i.e. the flow is going to the same location
 141          regardless of the condition in this case the
 142          condition can be eliminated with a WARNING of course */
 143       if (loop->op == IFX &&
 144             loop->next &&
 145         loop->next->op == GOTO)
 146         {
 147           if (IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key)
 148             {
 149               deleteIfx (loop, IC_TRUE (loop)->key);
 150               change++;
 151               continue;
 152             }
 153           else
 154             {
 155               if (IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)
 156                 {
 157                   deleteIfx (loop, IC_FALSE (loop)->key);
 158                   change++;
 159                   continue;
 160                 }
 161             }
 162         }
 163       /* same as above but with a twist */
 164       /* if condition goto label */
 165       /* label:                  */
 166       if (loop->op == IFX &&
 167           loop->next &&
 168           loop->next->op == LABEL &&
 169           ((IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key) ||
 170            (IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)))
 171         {
 172           deleteIfx (loop, IC_LABEL (loop->next)->key);
 173           change++;
 174           continue;
 175         }
 176
 177       /* we will eliminate certain special case situations */
 178       /* of the conditional statement :-                  */
 179       /*       if cond != 0 goto _trueLabel               */
 180       /*       goto _falseLabel                           */
 181       /* _trueLabel :                                     */
 182       /*       ...                                        */
 183       /* in these cases we can change it to :-            */
 184       /*       if cond == 0 goto _falseLabel              */
 185       /* _trueLabel :                                     */
 186       /*       ...                                        */
 187       /* similarly if we have a situation like :-         */
 188       /*       if cond == 0 goto _falseLabel              */
 189       /*       goto _someLabel                            */
 190       /* _falseLabel :                                    */
 191       /* we can change this to                            */
 192       /*       if cond != 0 goto _someLabel               */
 193       /* _falseLabel :                                    */
 194       /*       ...                                        */
 195       if (loop->op == IFX && loop->next && loop->next->op == GOTO &&
 196             loop->next->next && loop->next->next->op == LABEL)
 197         {
 198           if (IC_TRUE (loop) && (IC_TRUE (loop))->key != (IC_LABEL (loop->next->next))->key ||
 199             (IC_FALSE (loop) && (IC_FALSE (loop))->key != (IC_LABEL (loop->next->next))->key))
 200             continue;
 201
 202           /* now make sure that this is the only */
 203           /* reference to the _trueLabel        */
 204           if (IC_TRUE (loop) && hTabItemWithKey (labelRef, (IC_TRUE (loop))->key))
 205             {
 206               /* we just change the falseLabel */
 207               /* to the next goto statement    */
 208               /* unreferenced label will take  */
 209               /* care of removing the label    */
 210               /* delete reference to the true label */
 211
 212               hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
 213               IC_TRUE (loop) = NULL;
 214               IC_FALSE (loop) = IC_LABEL (loop->next);
 215               /* add reference to the LABEL */
 216               hTabAddItem (&labelRef, (IC_FALSE (loop))->key, loop);
 217               /* next remove the goto */
 218               hTabDeleteItem (&labelRef,
 219                (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
 220               loop->next = loop->next->next;
 221               loop->next->prev = loop;
 222               change++;
 223               continue;
 224             }
 225
 226           /* now do the same with the false labels */
 227           if (IC_FALSE (loop) && hTabItemWithKey (labelRef, (IC_FALSE (loop))->key))
 228             {
 229               hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
 230               IC_FALSE (loop) = NULL;
 231               IC_TRUE (loop) = IC_LABEL (loop->next);
 232               hTabAddItem (&labelRef, (IC_TRUE (loop))->key, loop);
 233               hTabDeleteItem (&labelRef, (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
 234               loop->next = loop->next->next;
 235               loop->next->prev = loop;
 236               change++;
 237               continue;
 238             }
 239         }
 240
 241       /* Optimize hidden jump-to-jump:
 242          Simplify
 243            v = 1;              stat->prev
 244            goto l1;            stat
 245          l0:
 246            v = 0;              loop->prev
 247          l1:                   loop
 248            if (v) goto l3;     loop->next
 249          Into
 250            v = 1;
 251            goto l3;
 252          l0:
 253            v = 0;
 254          l1: */
 255       if (loop->op == LABEL &&
 256           loop->next && loop->next->op == IFX &&
 257           (stat = hTabFirstItemWK (labelRef, (IC_LABEL (loop))->key)) &&
 258           !hTabNextItemWK (labelRef) &&
 259           stat && stat->op == GOTO &&
 260           stat->prev && stat->prev->op == '=' && IS_OP_LITERAL (IC_RIGHT (stat->prev)) &&
 261           loop->prev && loop->prev->op == '=' && IS_OP_LITERAL (IC_RIGHT (loop->prev)) &&
 262           IC_RESULT (stat->prev)->key == IC_COND (loop->next)->key &&
 263           IC_RESULT (loop->prev)->key == IC_COND (loop->next)->key &&
 264           !IS_OP_VOLATILE (IC_COND (loop->next)) &&
 265           (!operandLitValue (IC_RIGHT (stat->prev)) ^ !operandLitValue (IC_RIGHT (loop->prev))))
 266         {
 267           if (IC_FALSE (loop->next) && !operandLitValue (IC_RIGHT (loop->prev)) ||
 268               IC_TRUE (loop->next)  && operandLitValue (IC_RIGHT (loop->prev)))
 269             /* Complicated case: Insert goto, remove conditional jump. */
 270             {
 271               /* Change IFX to GOTO. */
 272               stat = loop->next;
 273               IC_LABEL (stat) = IC_TRUE (stat) ? IC_TRUE (stat) : IC_FALSE (stat);
 274               stat->op = GOTO;
 275
 276              /* Move to desired location. */
 277               if (loop->next->next)
 278                 loop->next->next->prev = loop;
 279               loop->next = loop->next->next;
 280               stat->prev = loop->prev;
 281               stat->prev->next = stat;
 282               stat->next = loop;
 283               loop->prev = stat;
 284               change++;
 285               continue;
 286             }
 287           else /* Simple case: Redirect goto, remove conditional jump. */
 288             {
 289               hTabDeleteItem (&labelRef, (IC_LABEL (stat))->key, stat, DELETE_ITEM, NULL);
 290               IC_LABEL (stat) = IC_TRUE (loop->next) ? IC_TRUE (loop->next) : IC_FALSE (loop->next);
 291               hTabAddItem (&labelRef, (IC_LABEL (stat))->key, stat);
 292               hTabDeleteItem (&labelRef, IC_LABEL (stat)->key, loop->next, DELETE_ITEM, NULL);
 293               if (loop->next->next)
 294                 loop->next->next->prev = loop;
 295               loop->next = loop->next->next;
 296               change++;
 297               continue;
 298             }
 299         }
 300     }
 301
 302   return change;
 303 }
 304
 305 /*-----------------------------------------------------------------*/
 306 /* labelJumptable - eliminate or simplify jump tables              */
 307 /*-----------------------------------------------------------------*/
 308 int
 309 labelJumptable (iCode * ic)
 310 {
 311   iCode *loop;
 312   int change = 0;
 313
 314   for (loop = ic; loop; loop = loop->next)
 315     {
 316       /* Jump table with constant can be replace with GOTO */
 317       if (loop->op == JUMPTABLE &&
 318           isOperandLiteral (IC_JTCOND (loop)))
 319         {
 320           symbol *lbl, *caselbl = NULL;
 321           int casenum, constcasenum;
 322
 323           constcasenum = operandLitValue (IC_JTCOND (loop));
 324           if (!loop->inlined)
 325             werrorfl (loop->filename, loop->lineno, W_CONTROL_FLOW);
 326
 327           /* Delete all the references except for the one that we keep */
 328           for (casenum = 0, lbl = setFirstItem (IC_JTLABELS (loop)); lbl;
 329                casenum++, lbl = setNextItem (IC_JTLABELS (loop)))
 330             {
 331               if (constcasenum == casenum)
 332                 caselbl = lbl; /* keep this reference, remember this label */
 333               else
 334                 hTabDeleteItem (&labelRef, lbl->key, loop, DELETE_ITEM, NULL);
 335             }
 336
 337           loop->op = GOTO;
 338           loop->label = caselbl;
 339           IC_LEFT (loop) = NULL;
 340           IC_RIGHT (loop) = NULL;
 341           IC_RESULT (loop) = NULL;
 342           change++;
 343         }
 344
 345     }
 346
 347   return change;
 348 }
 349
 350 /*-----------------------------------------------------------------*/
 351 /* replaceGotoGoto - find new target for jump                      */
 352 /* if we have a target statement then check if the next            */
 353 /* one is a goto: this means target of goto is a goto              */
 354 /*-----------------------------------------------------------------*/
 355 static symbol *
 356 replaceGotoGoto (const iCode *ic, const symbol *sLabel, const iCode *target)
 357 {
 358   if (!target || !target->next)
 359     return 0;
 360
 361   if (target->next->op != GOTO && target->next->op != LABEL || target->next == ic)
 362     return 0;
 363
 364   symbol *repLabel = target->next->label;
 365
 366   if (repLabel == sLabel)
 367     return 0;
 368
 369   return repLabel;
 370 }
 371
 372
 373 /*-----------------------------------------------------------------*/
 374 /* labelGotoGoto - target of a goto is a goto                      */
 375 /*-----------------------------------------------------------------*/
 376 int
 377 labelGotoGoto (iCode *ic)
 378 {
 379   iCode *loop;
 380   int change = 0;
 381
 382   for (loop = ic; loop; loop = loop->next)
 383     {
 384       iCode *stat;
 385       symbol *sLabel = NULL;
 386       symbol *repLabel;
 387       stat = NULL;
 388       switch (loop->op)
 389         {
 390         case GOTO:              /* for a goto statement */
 391
 392           stat = hTabItemWithKey (labelDef, (sLabel = IC_LABEL (loop))->key);
 393
 394           if (repLabel = replaceGotoGoto (loop, sLabel, stat))
 395             {
 396               hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
 397               loop->label = repLabel;
 398               hTabAddItem (&labelRef, repLabel->key, loop);
 399               change++;
 400             }
 401           break;
 402
 403         case IFX:               /* for a conditional jump */
 404
 405           if (IC_TRUE (loop))
 406             stat = hTabItemWithKey (labelDef, (sLabel = IC_TRUE (loop))->key);
 407           else
 408             stat = hTabItemWithKey (labelDef, (sLabel = IC_FALSE (loop))->key);
 409
 410           if (repLabel = replaceGotoGoto (loop, sLabel, stat))
 411             {
 412               if (IC_TRUE (loop))
 413                 {
 414                   hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
 415                   IC_TRUE (loop) = repLabel;
 416                 }
 417               else
 418                 {
 419                   hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
 420                   IC_FALSE (loop) = repLabel;
 421                 }
 422               hTabAddItem (&labelRef, repLabel->key, loop);
 423               stat->mergedElsewhere = 1;
 424               stat->next->mergedElsewhere = 1;
 425               change++;
 426             }
 427           break;
 428
 429         case JUMPTABLE:
 430
 431           for (sLabel = setFirstItem (IC_JTLABELS (loop)); sLabel; sLabel = setNextItem (IC_JTLABELS (loop)))
 432             {
 433               stat = hTabItemWithKey (labelDef, sLabel->key);
 434               if (repLabel = replaceGotoGoto (loop, sLabel, stat))
 435                 {
 436                   hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
 437                   replaceSetItem (IC_JTLABELS (loop), sLabel, repLabel);
 438                   hTabAddItem (&labelRef, repLabel->key, loop);
 439                   stat->mergedElsewhere = 1;
 440                   stat->next->mergedElsewhere = 1;
 441                   change++;
 442                 }
 443             }
 444         }
 445     }
 446
 447   return change;
 448 }
 449
 450 /*-----------------------------------------------------------------*/
 451 /* labelUnrefLabel - remove unreferenced labels                    */
 452 /*-----------------------------------------------------------------*/
 453 int
 454 labelUnrefLabel (iCode * ic)
 455 {
 456   iCode *loop;
 457   int change = 0;
 458
 459   for (loop = ic; loop; loop = loop->next)
 460     {
 461
 462       /* if this is a label */
 463       if (loop->op == LABEL)
 464         {
 465           if (((IC_LABEL (loop))->key == returnLabel->key) ||
 466               ((IC_LABEL (loop))->key == entryLabel->key))
 467             continue;
 468
 469           if (hTabItemWithKey (labelRef, (IC_LABEL (loop))->key))
 470             continue;
 471
 472           /* else eliminate this one */
 473           loop->prev->next = loop->next;        /* get this out of the chain */
 474           loop->next->prev = loop->prev;
 475           change++;
 476         }
 477     }
 478
 479   return change;
 480 }
 481
 482 /*-----------------------------------------------------------------*/
 483 /* labelUnreach - remove unreachable code                          */
 484 /*-----------------------------------------------------------------*/
 485 int
 486 labelUnreach (iCode *ic)
 487 {
 488   iCode *loop;
 489   iCode *tic;
 490   int change = 0;
 491
 492   /* if we hit a return statement or a goto statement */
 493   /* remove all statements till we hit the next label */
 494   for (loop = ic; loop; loop = loop->next)
 495     {
 496       iCode *loop2;
 497
 498       /* found a goto || return && the next */
 499       /* statement is not a label           */
 500       if (loop->op == GOTO || loop->op == RETURN ||
 501         loop->op == CALL && IFFUNC_ISNORETURN (operandType (IC_LEFT (loop))))
 502         {
 503           if (loop->next &&
 504               (loop->next->op == LABEL || loop->next->op == ENDFUNCTION))
 505             continue;
 506
 507           /* loop till we find a label */
 508           loop2 = loop->next;
 509           while (loop2 && loop2->op != LABEL)
 510             loop2 = loop2->next;
 511
 512           /* throw away those in between */
 513           for (tic = loop->next; tic && tic != loop2; tic = tic->next)
 514             {
 515               symbol *lbl;
 516               if (tic->op != GOTO && !tic->inlined && !tic->mergedElsewhere)
 517                 werrorfl (tic->filename, tic->lineno, W_CODE_UNREACH);
 518               /* remove label references if any */
 519               switch (tic->op)
 520                 {
 521                 case GOTO:
 522                   hTabDeleteItem (&labelRef, IC_LABEL (tic)->key, tic, DELETE_ITEM, NULL);
 523                   break;
 524                 case IFX:
 525                   if (IC_TRUE (tic))
 526                     hTabDeleteItem (&labelRef, IC_TRUE (tic)->key, tic, DELETE_ITEM, NULL);
 527                   else
 528                     hTabDeleteItem (&labelRef, IC_FALSE (tic)->key, tic, DELETE_ITEM, NULL);
 529                   if (IS_SYMOP (IC_COND (tic)) && OP_USES (IC_COND (tic)))
 530                     bitVectUnSetBit (OP_USES (IC_COND (tic)), tic->key);
 531                   break;
 532                 case JUMPTABLE:
 533                   for (lbl = setFirstItem (IC_JTLABELS (tic)); lbl;
 534                        lbl = setNextItem (IC_JTLABELS (tic)))
 535                     {
 536                       hTabDeleteItem (&labelRef, lbl->key, tic, DELETE_ITEM, NULL);
 537                     }
 538                   if (IS_SYMOP (IC_JTCOND (tic)) && OP_USES (IC_JTCOND (tic)))
 539                     bitVectUnSetBit (OP_USES (IC_JTCOND (tic)), tic->key);
 540                   break;
 541                 default:
 542                   if (IS_SYMOP (tic->left))
 543                     {
 544                       if (OP_SYMBOL (tic->left)->isstrlit)
 545                         freeStringSymbol (OP_SYMBOL (tic->left));
 546                       if (OP_USES (tic->left))
 547                         bitVectUnSetBit (OP_USES (tic->left), tic->key);
 548                     }
 549                   if (IS_SYMOP (tic->right))
 550                     {
 551                       if (OP_SYMBOL (tic->right)->isstrlit)
 552                         freeStringSymbol (OP_SYMBOL (tic->right));
 553                       if (OP_USES (tic->right))
 554                         bitVectUnSetBit (OP_USES (tic->right), tic->key);
 555                     }
 556                   if (POINTER_SET (tic))
 557                     {
 558                       if (IS_SYMOP (IC_RESULT (tic)) && OP_USES (IC_RESULT (tic)))
 559                         bitVectUnSetBit (OP_DEFS (IC_RESULT (tic)), tic->key);
 560                     }
 561                   else
 562                     {
 563                       if (IS_SYMOP (IC_RESULT (tic)) && OP_DEFS (IC_RESULT (tic)))
 564                         bitVectUnSetBit (OP_DEFS (IC_RESULT (tic)), tic->key);
 565                     }
 566                 }
 567             }
 568
 569           /* now set up the pointers */
 570           loop->next = loop2;
 571           if (loop2)
 572             loop2->prev = loop;
 573           change++;
 574         }
 575     }
 576   return change;
 577 }
 578
 579 /*-----------------------------------------------------------------*/
 580 /* iCodeLabelOptimize - some obvious & general optimizations       */
 581 /*-----------------------------------------------------------------*/
 582 iCode *
 583 iCodeLabelOptimize (iCode * ic)
 584 {
 585   if (!optimize.label1 &&
 586       !optimize.label2 &&
 587       !optimize.label3 &&
 588       !optimize.label4)
 589     return ic;
 590
 591   /* build labelreferences */
 592   buildLabelRefTable (ic);
 593
 594   /* the following transformations need to ne done */
 595   /* repeatedly till a fixed point is reached      */
 596   while (1)
 597     {
 598       int change;
 599       change = 0;
 600
 601       /* first eliminate any goto statement */
 602       /* that goes to the next statement    */
 603       if (optimize.label1)
 604         change += labelGotoNext (ic);
 605
 606       if (optimize.label2)
 607         change += labelIfx (ic);
 608       if (optimize.label2)
 609         change += labelJumptable (ic);
 610
 611       /* target of a goto is a goto then rename this goto */
 612       if (optimize.label3)
 613         change += labelGotoGoto (ic);
 614
 615       /* remove unreference labels */
 616       if (optimize.label4)
 617         change += labelUnrefLabel (ic);
 618
 619       /* remove unreachable code */
 620       change += labelUnreach (ic);
 621
 622       if (!change)              /* fixed point reached */
 623         break;
 624     }
 625
 626   return ic;
 627 }