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