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 referneces   */
  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->argLabel.label->key == loop->argLabel.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->argLabel.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->argLabel.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 unreferneced 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           set *refs;
 345
 346           refs = NULL;
 347           if (((IC_LABEL (loop))->key == returnLabel->key) ||
 348               ((IC_LABEL (loop))->key == entryLabel->key))
 349             continue;
 350
 351           if (hTabItemWithKey (labelRef, (IC_LABEL (loop))->key))
 352             continue;
 353
 354           /* else eliminitate this one */
 355           loop->prev->next = loop->next;        /* get this out of the chain */
 356           loop->next->prev = loop->prev;
 357           change++;
 358         }
 359     }
 360
 361   return change;
 362 }
 363
 364 /*-----------------------------------------------------------------*/
 365 /* labelUnreach - remove unreachable code                          */
 366 /*-----------------------------------------------------------------*/
 367 int
 368 labelUnreach (iCode * ic)
 369 {
 370   iCode *loop;
 371   iCode *tic;
 372   int change = 0;
 373
 374   /* if we hit a return statement or a goto statement */
 375   /* remove all statements till we hit the next label */
 376   for (loop = ic; loop; loop = loop->next)
 377     {
 378       iCode *loop2;
 379
 380       /* found a goto || return && the next */
 381       /* statement is not a label           */
 382       if (loop->op == GOTO || loop->op == RETURN)
 383         {
 384
 385           if (loop->next &&
 386               (loop->next->op == LABEL ||
 387                loop->next->op == ENDFUNCTION))
 388             continue;
 389
 390           /* loop till we find a label */
 391           loop2 = loop->next;
 392           while (loop2 && loop2->op != LABEL)
 393             loop2 = loop2->next;
 394
 395           /* throw away those in between */
 396           for (tic = loop->next; tic && tic != loop2; tic = tic->next)
 397             {
 398               /* remove label references if any */
 399               switch (tic->op)
 400                 {
 401                 case GOTO:
 402                   hTabDeleteItem (&labelRef, IC_LABEL (tic)->key, tic, DELETE_ITEM, NULL);
 403                   break;
 404                 case IFX:
 405                   if (IC_TRUE (tic))
 406                     hTabDeleteItem (&labelRef, IC_TRUE (tic)->key, tic, DELETE_ITEM, NULL);
 407                   else
 408                     hTabDeleteItem (&labelRef, IC_FALSE (tic)->key, tic, DELETE_ITEM, NULL);
 409                   break;
 410
 411                 }
 412             }
 413
 414           /* now set up the pointers */
 415           loop->next = loop2;
 416           if (loop2)
 417             loop2->prev = loop;
 418           change++;
 419         }
 420     }
 421   return change;
 422 }
 423
 424 /*-----------------------------------------------------------------*/
 425 /* iCodeLabelOptimize - some obvious & general optimizations       */
 426 /*-----------------------------------------------------------------*/
 427 iCode *
 428 iCodeLabelOptimize (iCode * ic)
 429 {
 430   if (!optimize.label1 &&
 431       !optimize.label2 &&
 432       !optimize.label3 &&
 433       !optimize.label4)
 434     return ic;
 435
 436   /* build labelreferences */
 437   buildLabelRefTable (ic);
 438
 439   /* the following transformations need to ne done */
 440   /* repeatedly till a fixed point is reached      */
 441   while (1)
 442     {
 443       int change;
 444       change = 0;
 445
 446       /* first eliminate any goto statement */
 447       /* that goes to the next statement    */
 448       if (optimize.label1)
 449         change += labelGotoNext (ic);
 450
 451       if (optimize.label2)
 452         change += labelIfx (ic);
 453
 454       /* target of a goto is a goto then rename this goto */
 455       if (optimize.label3)
 456         change += labelGotoGoto (ic);
 457
 458       /* remove unreference labels */
 459       if (optimize.label4)
 460         change += labelUnrefLabel (ic);
 461
 462       /* remove unreachable code */
 463       change += labelUnreach (ic);
 464
 465       if (!change)              /* fixed point reached */
 466         break;
 467     }
 468
 469   return ic;
 470 }