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 buildLabelRefTable (iCode *ic)
  34 {
  35     iCode *lic;
  36
  37     setToNull ((void **)&labelRef);
  38     setToNull ((void **)&labelDef);
  39     labelRef = newHashTable(labelKey + 1);
  40     labelDef = newHashTable(labelKey + 1);
  41
  42     for (lic = ic ; lic ; lic = lic->next ) {
  43         if ( lic->op == GOTO )
  44             hTabAddItem (&labelRef, (IC_LABEL(lic))->key, lic);
  45
  46         if ( lic->op == JUMPTABLE ) {
  47             symbol *lbl ;
  48             for (lbl = setFirstItem(IC_JTLABELS(lic)); lbl;
  49                  lbl = setNextItem(IC_JTLABELS(lic))) {
  50                 hTabAddItem(&labelRef,lbl->key,lic);
  51             }
  52         }
  53
  54         if (lic->op == IFX ) {
  55             if (IC_TRUE(lic))
  56                 hTabAddItem(&labelRef,(IC_TRUE(lic))->key, lic);
  57             else
  58                 hTabAddItem(&labelRef,(IC_FALSE(lic))->key, lic);
  59         }
  60         if ( lic->op == LABEL )
  61             hTabAddItem (&labelDef,(IC_LABEL(lic))->key, lic);
  62
  63     }
  64 }
  65
  66 /*-----------------------------------------------------------------*/
  67 /* labelGotoNext - kills gotos to next statement                   */
  68 /*-----------------------------------------------------------------*/
  69 int labelGotoNext (iCode *ic)
  70 {
  71     iCode *loop;
  72     int change = 0 ;
  73
  74     for ( loop = ic ; loop ; loop = loop->next) {
  75
  76         if (loop->op == GOTO &&              /* if this is a goto */
  77             loop->next       &&              /* and we have a next one */
  78             loop->next->op == LABEL &&       /* next one is a label */
  79             loop->next->argLabel.label->key == loop->argLabel.label->key)  /* same label */
  80             {
  81                 loop->prev->next = loop->next ;  /* get this out of the chain */
  82                 loop->next->prev = loop->prev ;
  83                 hTabDeleteItem (&labelRef,(IC_LABEL(loop))->key, loop, DELETE_ITEM, NULL);
  84                 change++ ;
  85             }
  86     }
  87
  88     return change ;
  89 }
  90
  91 /*-----------------------------------------------------------------*/
  92 /* labelIfx - special case Ifx elimination                         */
  93 /*-----------------------------------------------------------------*/
  94 int labelIfx ( iCode *ic)
  95 {
  96     iCode *loop ;
  97     int change = 0;
  98
  99
 100     for ( loop = ic ; loop ; loop = loop->next ) {
 101         /*   if  condition  goto label */
 102         /*   goto label                */
 103         /* i.e. the flow is going to the same location
 104            regardless of the condition in this case the
 105            condition can be eliminated with a WARNING ofcource */
 106         if ( loop->op == IFX         &&
 107              loop->next              &&
 108              loop->next->op == GOTO  ) {
 109             if (IC_TRUE(loop) &&
 110                 IC_TRUE(loop)->key == IC_LABEL(loop->next)->key) {
 111
 112                 /* get rid of this if */
 113                 werror(W_CONTROL_FLOW,loop->filename,loop->lineno);
 114                 loop->prev->next = loop->next;
 115                 loop->next->prev = loop->prev;
 116                 hTabDeleteItem(&labelRef,
 117                                (IC_TRUE(loop))->key,
 118                                loop, DELETE_ITEM,NULL);
 119                 change++ ;
 120                 continue ;
 121             }
 122             else {
 123                 if (IC_FALSE(loop) &&
 124                     IC_FALSE(loop)->key == IC_LABEL(loop->next)->key){
 125                     /* get rid of this if */
 126                     werror(W_CONTROL_FLOW,loop->filename,loop->lineno);
 127                     loop->prev->next = loop->next;
 128                     loop->next->prev = loop->prev;
 129                     hTabDeleteItem(&labelRef,
 130                                    (IC_FALSE(loop))->key,
 131                                    loop, DELETE_ITEM,NULL);
 132                     change++;
 133                     continue ;
 134                 }
 135             }
 136         }
 137         /* same as above but with a twist */
 138         /* if condition goto label */
 139         /* label:                  */
 140         if (loop->op == IFX &&
 141             loop->next      &&
 142             loop->next->op == LABEL &&
 143             ((IC_TRUE(loop) && IC_TRUE(loop)->key == IC_LABEL(loop->next)->key) ||
 144              (IC_FALSE(loop) && IC_FALSE(loop)->key == IC_LABEL(loop->next)->key))) {
 145
 146             werror(W_CONTROL_FLOW,loop->filename,loop->lineno);
 147             loop->prev->next = loop->next;
 148             loop->next->prev = loop->prev;
 149             hTabDeleteItem(&labelRef,
 150                            IC_LABEL(loop->next)->key,
 151                            loop, DELETE_ITEM,NULL);
 152             change++;
 153             continue ;
 154         }
 155
 156         /* we will eliminate certain special case situations*/
 157         /* of the conditional statement :-                  */
 158         /*       if cond != 0 goto _trueLabel               */
 159         /*       goto _falseLabel                           */
 160         /* _trueLabel :                                     */
 161         /*       ...                                        */
 162         /* in these cases , if this is the only reference   */
 163         /* to the _trueLabel, we can change it to :-        */
 164         /*       if cond == 0 goto _falseLabel              */
 165         /*       ...                                        */
 166         /* similarly if we have a situation like :-         */
 167         /*       if cond == 0 goto _falseLabel              */
 168         /*       goto _someLabel                            */
 169         /* _falseLabel :                                    */
 170         /* we can change this to                            */
 171         /*       if cond != 0 goto _someLabel               */
 172         /*       ...                                        */
 173         if (loop->op == IFX        &&
 174             loop->next             &&
 175             loop->next->op == GOTO &&
 176             loop->next->next       &&
 177             loop->next->next->op == LABEL ) {
 178
 179
 180             /* now check that the last label is the */
 181             /* same as the _trueLabel of this       */
 182             if (IC_TRUE(loop))
 183                 if ( (IC_TRUE(loop))->key != (IC_LABEL(loop->next->next))->key )
 184                     continue ;
 185                 else ;
 186             else
 187                 if ( (IC_FALSE(loop))->key != (IC_LABEL(loop->next->next))->key )
 188                     continue;
 189
 190             /* now make sure that this is the only */
 191             /* referenece to the _trueLabel        */
 192             if ( IC_TRUE(loop) && hTabItemWithKey(labelRef,(IC_TRUE(loop))->key) ) {
 193
 194                 /* we just change the falseLabel */
 195                 /* to the next goto statement    */
 196                 /* unreferenced label will take  */
 197                 /* care of removing the label    */
 198                 /* delete reference to the true label */
 199
 200                 hTabDeleteItem(&labelRef, (IC_TRUE(loop))->key, loop, DELETE_ITEM,NULL);
 201                 IC_TRUE(loop) = NULL ;
 202                 IC_FALSE(loop) = IC_LABEL(loop->next);
 203                 /* add reference to the LABEL */
 204                 hTabAddItem (&labelRef,(IC_FALSE(loop))->key,loop);
 205                 /* next remove the goto */
 206                 hTabDeleteItem(&labelRef,
 207                                (IC_LABEL(loop->next))->key,loop->next,DELETE_ITEM,NULL);
 208                 loop->next = loop->next->next ;
 209                 loop->next->prev = loop ;
 210                 change++;
 211                 continue ;
 212             }
 213
 214             /* now do the same with the false labels */
 215             if (IC_FALSE(loop) &&
 216                 hTabItemWithKey(labelRef,(IC_FALSE(loop))->key)) {
 217
 218                 hTabDeleteItem(&labelRef, (IC_FALSE(loop))->key, loop, DELETE_ITEM,NULL);
 219                 IC_FALSE(loop) = NULL ;
 220                 IC_TRUE(loop) = IC_LABEL(loop->next);
 221                 hTabAddItem (&labelRef,(IC_TRUE(loop))->key,loop);
 222                 hTabDeleteItem(&labelRef,(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     }
 230
 231     return change ;
 232 }
 233
 234 /*-----------------------------------------------------------------*/
 235 /* labelGotoGoto - target of a goto is a goto                      */
 236 /*-----------------------------------------------------------------*/
 237 int labelGotoGoto (iCode *ic)
 238 {
 239     iCode *loop;
 240     int change = 0 ;
 241
 242     for ( loop = ic ; loop ; loop = loop->next ) {
 243         iCode *stat ;
 244         symbol *sLabel = NULL;
 245         stat = NULL ;
 246         switch (loop->op) {
 247         case GOTO: /* for a goto statement */
 248             stat = hTabItemWithKey(labelDef,(sLabel = IC_LABEL(loop))->key) ;
 249             break ;
 250         case IFX : /* for a conditional jump */
 251             if (IC_TRUE(loop))
 252                 stat = hTabItemWithKey(labelDef,(sLabel = IC_TRUE(loop))->key);
 253             else
 254                 stat = hTabItemWithKey (labelDef,(sLabel = IC_FALSE(loop))->key);
 255         }
 256
 257         /* if we have a target statement then check if the next */
 258         /* one is a goto: this means target of goto is a goto   */
 259         if ( stat && stat->next &&
 260              ( stat->next->op == GOTO ||
 261                stat->next->op == LABEL) &&
 262              stat->next != loop ) {
 263
 264             symbol *repLabel = stat->next->argLabel.label ; /* replace with label */
 265
 266             /* if they are the same then continue */
 267             if (repLabel->key == sLabel->key)
 268                 continue ;
 269
 270             /* replacement depends on the statement type */
 271             switch (loop->op)  {
 272
 273             case GOTO: /* for a goto statement */
 274
 275                 hTabDeleteItem (&labelRef, (IC_LABEL(loop))->key, loop,DELETE_ITEM,NULL);
 276                 loop->argLabel.label = repLabel ;
 277                 hTabAddItem (&labelRef, repLabel->key, loop);
 278                 break ;
 279
 280             case IFX : /* for a conditional jump */
 281                 if (IC_TRUE(loop)) {
 282
 283                     hTabDeleteItem (&labelRef, (IC_TRUE(loop))->key, loop,DELETE_ITEM,NULL);
 284                     IC_TRUE(loop) = repLabel ;
 285                 }
 286                 else {
 287
 288                     hTabDeleteItem (&labelRef, (IC_FALSE(loop))->key, loop,DELETE_ITEM,NULL);
 289                     IC_FALSE(loop) = repLabel;
 290                 }
 291                 hTabAddItem (&labelRef, repLabel->key, loop);
 292
 293             }
 294             change++ ;
 295         }
 296     }
 297
 298     return change ;
 299 }
 300
 301 /*-----------------------------------------------------------------*/
 302 /* labelUnrefLabel - remove unreferneced labels                    */
 303 /*-----------------------------------------------------------------*/
 304 int labelUnrefLabel (iCode *ic)
 305 {
 306     iCode *loop;
 307     int change = 0 ;
 308
 309     for ( loop = ic ; loop ; loop = loop->next) {
 310
 311         /* if this is a label */
 312         if (loop->op == LABEL) {
 313             set *refs ;
 314
 315             refs = NULL ;
 316             if ( ( (IC_LABEL(loop))->key == returnLabel->key ) ||
 317                  ( (IC_LABEL(loop))->key == entryLabel->key ) )
 318                 continue ;
 319
 320             if (hTabItemWithKey(labelRef,(IC_LABEL(loop))->key) )
 321                 continue ;
 322
 323             /* else eliminitate this one */
 324             loop->prev->next = loop->next ;  /* get this out of the chain */
 325             loop->next->prev = loop->prev ;
 326             change ++ ;
 327         }
 328     }
 329
 330     return change ;
 331 }
 332
 333 /*-----------------------------------------------------------------*/
 334 /* labelUnreach - remove unreachable code                          */
 335 /*-----------------------------------------------------------------*/
 336 int labelUnreach (iCode *ic)
 337 {
 338     iCode *loop;
 339     iCode *tic;
 340     int change = 0 ;
 341
 342     /* if we hit a return statement or a goto statement */
 343     /* remove all statements till we hit the next label */
 344     for (loop = ic ; loop ; loop = loop->next) {
 345         iCode *loop2 ;
 346
 347         /* found a goto || return && the next */
 348         /* statement is not a label           */
 349         if (loop->op == GOTO || loop->op == RETURN ) {
 350
 351             if (loop->next &&
 352                 (loop->next->op == LABEL ||
 353                  loop->next->op == ENDFUNCTION ))
 354                 continue ;
 355
 356             /* loop till we find a label */
 357             loop2 = loop->next ;
 358             while (loop2 && loop2->op != LABEL)
 359                 loop2 = loop2->next;
 360
 361             /* throw away those in between */
 362             for (tic = loop->next ; tic && tic != loop2 ; tic=tic->next) {
 363                 /* remove label references if any */
 364                 switch (tic->op) {
 365                 case GOTO :
 366                     hTabDeleteItem (&labelRef,IC_LABEL(tic)->key,tic,DELETE_ITEM,NULL);
 367                     break;
 368                 case IFX :
 369                     if (IC_TRUE(tic))
 370                         hTabDeleteItem (&labelRef,IC_TRUE(tic)->key,tic,DELETE_ITEM,NULL);
 371                     else
 372                         hTabDeleteItem (&labelRef,IC_FALSE(tic)->key,tic,DELETE_ITEM,NULL);
 373                     break;
 374
 375                 }
 376             }
 377
 378             /* now set up the pointers */
 379             loop->next = loop2;
 380             if (loop2)
 381                 loop2->prev = loop ;
 382             change++;
 383         }
 384     }
 385     return change ;
 386 }
 387
 388 /*-----------------------------------------------------------------*/
 389 /* iCodeLabelOptimize - some obvious & general optimizations       */
 390 /*-----------------------------------------------------------------*/
 391 iCode *iCodeLabelOptimize (iCode *ic)
 392 {
 393     if (!optimize.label1 &&
 394         !optimize.label2 &&
 395         !optimize.label3 &&
 396         !optimize.label4 )
 397         return ic;
 398
 399     /* build labelreferences */
 400     buildLabelRefTable (ic);
 401
 402     /* the following transformations need to ne done */
 403     /* repeatedly till a fixed point is reached      */
 404     while (1) {
 405         int change ;
 406         change = 0 ;
 407
 408         /* first eliminate any goto statement */
 409         /* that goes to the next statement    */
 410         if (optimize.label1)
 411             change += labelGotoNext (ic);
 412
 413         if ( optimize.label2 )
 414             change += labelIfx (ic);
 415
 416         /* target of a goto is a goto then rename this goto */
 417         if (optimize.label3 )
 418             change += labelGotoGoto (ic);
 419
 420         /* remove unreference labels */
 421         if (optimize.label4)
 422             change += labelUnrefLabel (ic);
 423
 424         /* remove unreachable code */
 425         change += labelUnreach (ic);
 426
 427         if (!change) /* fixed point reached */
 428             break;
 429     }
 430
 431     return ic;
 432 }