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           int warn = 0;
 388
 389           if (loop->next &&
 390               (loop->next->op == LABEL ||
 391                loop->next->op == ENDFUNCTION))
 392             continue;
 393
 394           /* loop till we find a label */
 395           loop2 = loop->next;
 396           while (loop2 && loop2->op != LABEL)
 397             loop2 = loop2->next;
 398
 399           /* throw away those in between */
 400           for (tic = loop->next; tic && tic != loop2; tic = tic->next)
 401             {
 402               /* remove label references if any */
 403               switch (tic->op)
 404                 {
 405                 case GOTO:
 406                   hTabDeleteItem (&labelRef, IC_LABEL (tic)->key, tic, DELETE_ITEM, NULL);
 407                   break;
 408                 case IFX:
 409                   warn = 1;
 410                   if (IC_TRUE (tic))
 411                     hTabDeleteItem (&labelRef, IC_TRUE (tic)->key, tic, DELETE_ITEM, NULL);
 412                   else
 413                     hTabDeleteItem (&labelRef, IC_FALSE (tic)->key, tic, DELETE_ITEM, NULL);
 414                   break;
 415                 default:
 416                   warn = 1;
 417
 418                 }
 419             }
 420
 421           if (warn)
 422             werrorfl (loop->next->filename, loop->next->lineno,
 423                       W_CODE_UNREACH);
 424
 425           /* now set up the pointers */
 426           loop->next = loop2;
 427           if (loop2)
 428             loop2->prev = loop;
 429           change++;
 430         }
 431     }
 432   return change;
 433 }
 434
 435 /*-----------------------------------------------------------------*/
 436 /* iCodeLabelOptimize - some obvious & general optimizations       */
 437 /*-----------------------------------------------------------------*/
 438 iCode *
 439 iCodeLabelOptimize (iCode * ic)
 440 {
 441   if (!optimize.label1 &&
 442       !optimize.label2 &&
 443       !optimize.label3 &&
 444       !optimize.label4)
 445     return ic;
 446
 447   /* build labelreferences */
 448   buildLabelRefTable (ic);
 449
 450   /* the following transformations need to ne done */
 451   /* repeatedly till a fixed point is reached      */
 452   while (1)
 453     {
 454       int change;
 455       change = 0;
 456
 457       /* first eliminate any goto statement */
 458       /* that goes to the next statement    */
 459       if (optimize.label1)
 460         change += labelGotoNext (ic);
 461
 462       if (optimize.label2)
 463         change += labelIfx (ic);
 464
 465       /* target of a goto is a goto then rename this goto */
 466       if (optimize.label3)
 467         change += labelGotoGoto (ic);
 468
 469       /* remove unreference labels */
 470       if (optimize.label4)
 471         change += labelUnrefLabel (ic);
 472
 473       /* remove unreachable code */
 474       change += labelUnreach (ic);
 475
 476       if (!change)              /* fixed point reached */
 477         break;
 478     }
 479
 480   return ic;
 481 }