git.gag.com Git - fw/sdcc/blob - 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 /* labelIfx - special case Ifx elimination                         */
 100 /*-----------------------------------------------------------------*/
 101 int
 102 labelIfx (iCode * ic)
 103 {
 104   iCode *loop;
 105   int change = 0;
 106
 107
 108   for (loop = ic; loop; loop = loop->next)
 109     {
 110       /*   if  condition  goto label */
 111       /*   goto label                */
 112       /* i.e. the flow is going to the same location
 113          regardless of the condition in this case the
 114          condition can be eliminated with a WARNING ofcource */
 115       if (loop->op == IFX &&
 116           loop->next &&
 117           loop->next->op == GOTO)
 118         {
 119           if (IC_TRUE (loop) &&
 120               IC_TRUE (loop)->key == IC_LABEL (loop->next)->key)
 121             {
 122
 123               /* get rid of this if */
 124               if (!options.lessPedantic) {
 125                 werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
 126               }
 127               loop->prev->next = loop->next;
 128               loop->next->prev = loop->prev;
 129               hTabDeleteItem (&labelRef,
 130                               (IC_TRUE (loop))->key,
 131                               loop, DELETE_ITEM, NULL);
 132               change++;
 133               continue;
 134             }
 135           else
 136             {
 137               if (IC_FALSE (loop) &&
 138                   IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)
 139                 {
 140                   /* get rid of this if */
 141                   if (!options.lessPedantic) {
 142                     werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
 143                   }
 144                   loop->prev->next = loop->next;
 145                   loop->next->prev = loop->prev;
 146                   hTabDeleteItem (&labelRef,
 147                                   (IC_FALSE (loop))->key,
 148                                   loop, DELETE_ITEM, NULL);
 149                   change++;
 150                   continue;
 151                 }
 152             }
 153         }
 154       /* same as above but with a twist */
 155       /* if condition goto label */
 156       /* label:                  */
 157       if (loop->op == IFX &&
 158           loop->next &&
 159           loop->next->op == LABEL &&
 160           ((IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key) ||
 161            (IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)))
 162         {
 163           if (!options.lessPedantic) {
 164             werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
 165           }
 166           loop->prev->next = loop->next;
 167           loop->next->prev = loop->prev;
 168           hTabDeleteItem (&labelRef,
 169                           IC_LABEL (loop->next)->key,
 170                           loop, DELETE_ITEM, NULL);
 171           change++;
 172           continue;
 173         }
 174
 175       /* we will eliminate certain special case situations */
 176       /* of the conditional statement :-                  */
 177       /*       if cond != 0 goto _trueLabel               */
 178       /*       goto _falseLabel                           */
 179       /* _trueLabel :                                     */
 180       /*       ...                                        */
 181       /* in these cases , if this is the only reference   */
 182       /* to the _trueLabel, we can change it to :-        */
 183       /*       if cond == 0 goto _falseLabel              */
 184       /*       ...                                        */
 185       /* similarly if we have a situation like :-         */
 186       /*       if cond == 0 goto _falseLabel              */
 187       /*       goto _someLabel                            */
 188       /* _falseLabel :                                    */
 189       /* we can change this to                            */
 190       /*       if cond != 0 goto _someLabel               */
 191       /*       ...                                        */
 192       if (loop->op == IFX &&
 193           loop->next &&
 194           loop->next->op == GOTO &&
 195           loop->next->next &&
 196           loop->next->next->op == LABEL)
 197         {
 198
 199
 200           /* now check that the last label is the */
 201           /* same as the _trueLabel of this       */
 202           if (IC_TRUE (loop))
 203             if ((IC_TRUE (loop))->key != (IC_LABEL (loop->next->next))->key)
 204               continue;
 205             else;
 206           else if ((IC_FALSE (loop))->key != (IC_LABEL (loop->next->next))->key)
 207             continue;
 208
 209           /* now make sure that this is the only */
 210           /* referenece to the _trueLabel        */
 211           if (IC_TRUE (loop) && hTabItemWithKey (labelRef, (IC_TRUE (loop))->key))
 212             {
 213
 214               /* we just change the falseLabel */
 215               /* to the next goto statement    */
 216               /* unreferenced label will take  */
 217               /* care of removing the label    */
 218               /* delete reference to the true label */
 219
 220               hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
 221               IC_TRUE (loop) = NULL;
 222               IC_FALSE (loop) = IC_LABEL (loop->next);
 223               /* add reference to the LABEL */
 224               hTabAddItem (&labelRef, (IC_FALSE (loop))->key, loop);
 225               /* next remove the goto */
 226               hTabDeleteItem (&labelRef,
 227                (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
 228               loop->next = loop->next->next;
 229               loop->next->prev = loop;
 230               change++;
 231               continue;
 232             }
 233
 234           /* now do the same with the false labels */
 235           if (IC_FALSE (loop) &&
 236               hTabItemWithKey (labelRef, (IC_FALSE (loop))->key))
 237             {
 238
 239               hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
 240               IC_FALSE (loop) = NULL;
 241               IC_TRUE (loop) = IC_LABEL (loop->next);
 242               hTabAddItem (&labelRef, (IC_TRUE (loop))->key, loop);
 243               hTabDeleteItem (&labelRef, (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
 244               loop->next = loop->next->next;
 245               loop->next->prev = loop;
 246               change++;
 247               continue;
 248             }
 249         }
 250     }
 251
 252   return change;
 253 }
 254
 255 /*-----------------------------------------------------------------*/
 256 /* labelGotoGoto - target of a goto is a goto                      */
 257 /*-----------------------------------------------------------------*/
 258 int
 259 labelGotoGoto (iCode * ic)
 260 {
 261   iCode *loop;
 262   int change = 0;
 263
 264   for (loop = ic; loop; loop = loop->next)
 265     {
 266       iCode *stat;
 267       symbol *sLabel = NULL;
 268       stat = NULL;
 269       switch (loop->op)
 270         {
 271         case GOTO:              /* for a goto statement */
 272           stat = hTabItemWithKey (labelDef, (sLabel = IC_LABEL (loop))->key);
 273           break;
 274         case IFX:               /* for a conditional jump */
 275           if (IC_TRUE (loop))
 276             stat = hTabItemWithKey (labelDef, (sLabel = IC_TRUE (loop))->key);
 277           else
 278             stat = hTabItemWithKey (labelDef, (sLabel = IC_FALSE (loop))->key);
 279         }
 280
 281       /* if we have a target statement then check if the next */
 282       /* one is a goto: this means target of goto is a goto   */
 283       if (stat && stat->next &&
 284           (stat->next->op == GOTO ||
 285            stat->next->op == LABEL) &&
 286           stat->next != loop)
 287         {
 288
 289           symbol *repLabel = stat->next->label; /* replace with label */
 290
 291           /* if they are the same then continue */
 292           if (repLabel->key == sLabel->key)
 293             continue;
 294
 295           /* replacement depends on the statement type */
 296           switch (loop->op)
 297             {
 298
 299             case GOTO:          /* for a goto statement */
 300
 301               hTabDeleteItem (&labelRef, (IC_LABEL (loop))->key, loop, DELETE_ITEM, NULL);
 302               loop->label = repLabel;
 303               hTabAddItem (&labelRef, repLabel->key, loop);
 304               break;
 305
 306             case IFX:           /* for a conditional jump */
 307               if (IC_TRUE (loop))
 308                 {
 309
 310                   hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
 311                   IC_TRUE (loop) = repLabel;
 312                 }
 313               else
 314                 {
 315
 316                   hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
 317                   IC_FALSE (loop) = repLabel;
 318                 }
 319               hTabAddItem (&labelRef, repLabel->key, loop);
 320
 321             }
 322           change++;
 323         }
 324     }
 325
 326   return change;
 327 }
 328
 329 /*-----------------------------------------------------------------*/
 330 /* labelUnrefLabel - remove unreferenced labels                    */
 331 /*-----------------------------------------------------------------*/
 332 int
 333 labelUnrefLabel (iCode * ic)
 334 {
 335   iCode *loop;
 336   int change = 0;
 337
 338   for (loop = ic; loop; loop = loop->next)
 339     {
 340
 341       /* if this is a label */
 342       if (loop->op == LABEL)
 343         {
 344           if (((IC_LABEL (loop))->key == returnLabel->key) ||
 345               ((IC_LABEL (loop))->key == entryLabel->key))
 346             continue;
 347
 348           if (hTabItemWithKey (labelRef, (IC_LABEL (loop))->key))
 349             continue;
 350
 351           /* else eliminitate this one */
 352           loop->prev->next = loop->next;        /* get this out of the chain */
 353           loop->next->prev = loop->prev;
 354           change++;
 355         }
 356     }
 357
 358   return change;
 359 }
 360
 361 /*-----------------------------------------------------------------*/
 362 /* labelUnreach - remove unreachable code                          */
 363 /*-----------------------------------------------------------------*/
 364 int
 365 labelUnreach (iCode * ic)
 366 {
 367   iCode *loop;
 368   iCode *tic;
 369   int change = 0;
 370
 371   /* if we hit a return statement or a goto statement */
 372   /* remove all statements till we hit the next label */
 373   for (loop = ic; loop; loop = loop->next)
 374     {
 375       iCode *loop2;
 376
 377       /* found a goto || return && the next */
 378       /* statement is not a label           */
 379       if (loop->op == GOTO || loop->op == RETURN)
 380         {
 381
 382           if (loop->next &&
 383               (loop->next->op == LABEL ||
 384                loop->next->op == ENDFUNCTION))
 385             continue;
 386
 387           /* loop till we find a label */
 388           loop2 = loop->next;
 389           while (loop2 && loop2->op != LABEL)
 390             loop2 = loop2->next;
 391
 392           /* throw away those in between */
 393           for (tic = loop->next; tic && tic != loop2; tic = tic->next)
 394             {
 395               /* remove label references if any */
 396               switch (tic->op)
 397                 {
 398                 case GOTO:
 399                   hTabDeleteItem (&labelRef, IC_LABEL (tic)->key, tic, DELETE_ITEM, NULL);
 400                   break;
 401                 case IFX:
 402                   if (IC_TRUE (tic))
 403                     hTabDeleteItem (&labelRef, IC_TRUE (tic)->key, tic, DELETE_ITEM, NULL);
 404                   else
 405                     hTabDeleteItem (&labelRef, IC_FALSE (tic)->key, tic, DELETE_ITEM, NULL);
 406                   break;
 407
 408                 }
 409             }
 410
 411           /* now set up the pointers */
 412           loop->next = loop2;
 413           if (loop2)
 414             loop2->prev = loop;
 415           change++;
 416         }
 417     }
 418   return change;
 419 }
 420
 421 /*-----------------------------------------------------------------*/
 422 /* iCodeLabelOptimize - some obvious & general optimizations       */
 423 /*-----------------------------------------------------------------*/
 424 iCode *
 425 iCodeLabelOptimize (iCode * ic)
 426 {
 427   if (!optimize.label1 &&
 428       !optimize.label2 &&
 429       !optimize.label3 &&
 430       !optimize.label4)
 431     return ic;
 432
 433   /* build labelreferences */
 434   buildLabelRefTable (ic);
 435
 436   /* the following transformations need to ne done */
 437   /* repeatedly till a fixed point is reached      */
 438   while (1)
 439     {
 440       int change;
 441       change = 0;
 442
 443       /* first eliminate any goto statement */
 444       /* that goes to the next statement    */
 445       if (optimize.label1)
 446         change += labelGotoNext (ic);
 447
 448       if (optimize.label2)
 449         change += labelIfx (ic);
 450
 451       /* target of a goto is a goto then rename this goto */
 452       if (optimize.label3)
 453         change += labelGotoGoto (ic);
 454
 455       /* remove unreference labels */
 456       if (optimize.label4)
 457         change += labelUnrefLabel (ic);
 458
 459       /* remove unreachable code */
 460       change += labelUnreach (ic);
 461
 462       if (!change)              /* fixed point reached */
 463         break;
 464     }
 465
 466   return ic;
 467 }