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