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