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