git.gag.com Git - fw/sdcc/blob - src/SDCCpeeph.c

   1 /*-------------------------------------------------------------------------
   2   SDCCpeeph.c - The peep hole optimizer: for interpreting the
   3                 peep hole rules
   4
   5              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1999)
   6
   7    This program is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 2, or (at your option) any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20
  21    In other words, you are welcome to use, share and improve this program.
  22    You are forbidden to forbid anyone else to use, share and improve
  23    what you give them.   Help stamp out software-hoarding!
  24 -------------------------------------------------------------------------*/
  25
  26 #include "common.h"
  27 #include "SDCCpeeph.h"
  28
  29 peepRule *rootRules = NULL;
  30 peepRule *currRule  = NULL;
  31
  32 char *defaultRules =
  33 {
  34 #include "SDCCpeeph.rul"
  35 };
  36
  37 static bool matchLine (char *, char *, hTab **);
  38
  39 #define FBYNAME(x) int x (hTab *vars, lineNode *currPl, lineNode *head)
  40
  41 /*-----------------------------------------------------------------*/
  42 /* pcDistance - afinds a label back ward or forward                */
  43 /*-----------------------------------------------------------------*/
  44 int pcDistance (lineNode *cpos, char *lbl, bool back)
  45 {
  46     lineNode *pl = cpos;
  47     char buff[MAX_PATTERN_LEN];
  48     int dist = 0 ;
  49
  50     sprintf(buff,"%s:",lbl);
  51     while (pl) {
  52
  53         if (pl->line &&
  54             *pl->line != ';' &&
  55             pl->line[strlen(pl->line)-1] != ':' &&
  56             !pl->isDebug)
  57
  58             dist ++;
  59
  60         if (strncmp(pl->line,buff,strlen(buff)) == 0)
  61             return dist;
  62
  63         if (back)
  64             pl = pl->prev;
  65         else
  66             pl = pl->next;
  67
  68     }
  69     return 0;
  70 }
  71
  72 /*-----------------------------------------------------------------*/
  73 /* labelInRange - will check to see if label %5 is within range    */
  74 /*-----------------------------------------------------------------*/
  75 FBYNAME(labelInRange)
  76 {
  77     /* assumes that %5 pattern variable has the label name */
  78     char *lbl = hTabItemWithKey(vars,5);
  79     int dist = 0 ;
  80
  81     if (!lbl)
  82         return FALSE;
  83
  84     /* if the previous teo instructions are "ljmp"s then don't
  85        do it since it can be part of a jump table */
  86     if (currPl->prev && currPl->prev->prev &&
  87         strstr(currPl->prev->line,"ljmp") &&
  88         strstr(currPl->prev->prev->line,"ljmp"))
  89         return FALSE ;
  90
  91     /* calculate the label distance : the jump for reladdr can be
  92        +/- 127 bytes, here Iam assuming that an average 8051
  93        instruction is 2 bytes long, so if the label is more than
  94        63 intructions away, the label is considered out of range
  95        for a relative jump. we could get more precise this will
  96        suffice for now since it catches > 90% cases */
  97     dist = (pcDistance(currPl,lbl,TRUE) +
  98             pcDistance(currPl,lbl,FALSE)) ;
  99
 100     if (!dist || dist > 45)
 101         return FALSE;
 102
 103     return TRUE;
 104 }
 105
 106 /*-----------------------------------------------------------------*/
 107 /* operandsNotSame - check if %1 & %2 are the same                 */
 108 /*-----------------------------------------------------------------*/
 109 FBYNAME(operandsNotSame)
 110 {
 111     char *op1 = hTabItemWithKey(vars,1);
 112     char *op2 = hTabItemWithKey(vars,2);
 113
 114     if (strcmp(op1,op2) == 0)
 115         return FALSE;
 116     else
 117         return TRUE;
 118 }
 119
 120 /*-----------------------------------------------------------------*/
 121 /* callFuncByName - calls a function as defined in the table       */
 122 /*-----------------------------------------------------------------*/
 123 int callFuncByName ( char *fname,
 124                      hTab *vars,
 125                      lineNode *currPl,
 126                      lineNode *head)
 127 {
 128     struct ftab {
 129         char *fname ;
 130         int (*func)(hTab *,lineNode *,lineNode *) ;
 131     }  ftab[] = {
 132         {"labelInRange",   labelInRange },
 133         {"operandsNotSame", operandsNotSame }
 134     };
 135     int i;
 136
 137     for ( i = 0 ; i < ((sizeof (ftab))/(sizeof(struct ftab))); i++)
 138         if (strcmp(ftab[i].fname,fname) == 0)
 139             return (*ftab[i].func)(vars,currPl,head);
 140     fprintf(stderr,"could not find named function in function table\n");
 141     return TRUE;
 142 }
 143
 144 /*-----------------------------------------------------------------*/
 145 /* printLine - prints a line chain into a given file               */
 146 /*-----------------------------------------------------------------*/
 147 void printLine (lineNode *head, FILE *of)
 148 {
 149     if (!of)
 150         of = stdout ;
 151
 152     while (head) {
 153         /* don't indent comments & labels */
 154         if (head->line &&
 155             ( *head->line == ';' ||
 156               head->line[strlen(head->line)-1] == ':'))
 157             fprintf(of,"%s\n",head->line);
 158         else
 159             fprintf(of,"\t%s\n",head->line);
 160         head = head->next;
 161     }
 162 }
 163
 164 /*-----------------------------------------------------------------*/
 165 /* newPeepRule - creates a new peeprule and attach it to the root  */
 166 /*-----------------------------------------------------------------*/
 167 peepRule *newPeepRule (lineNode *match  ,
 168                        lineNode *replace,
 169                        char *cond       ,
 170                        int restart)
 171 {
 172     peepRule *pr ;
 173
 174     ALLOC(pr,sizeof(peepRule));
 175     pr->match = match;
 176     pr->replace= replace;
 177     pr->restart = restart;
 178
 179     if (cond && *cond) {
 180         ALLOC_ATOMIC(pr->cond,strlen(cond)+1);
 181         strcpy(pr->cond,cond);
 182     } else
 183         pr->cond = NULL ;
 184
 185     pr->vars = newHashTable(100);
 186
 187     /* if root is empty */
 188     if (!rootRules)
 189         rootRules = currRule = pr;
 190     else
 191         currRule = currRule->next = pr;
 192
 193     return pr;
 194 }
 195
 196 /*-----------------------------------------------------------------*/
 197 /* newLineNode - creates a new peep line                           */
 198 /*-----------------------------------------------------------------*/
 199 lineNode *newLineNode (char *line)
 200 {
 201     lineNode *pl;
 202
 203     ALLOC(pl,sizeof(lineNode));
 204     ALLOC_ATOMIC(pl->line,strlen(line)+1);
 205     strcpy(pl->line,line);
 206     return pl;
 207 }
 208
 209 /*-----------------------------------------------------------------*/
 210 /* connectLine - connects two lines                                */
 211 /*-----------------------------------------------------------------*/
 212 lineNode *connectLine (lineNode *pl1, lineNode *pl2)
 213 {
 214     if (!pl1 || !pl2) {
 215         fprintf (stderr,"trying to connect null line\n");
 216         return NULL ;
 217     }
 218
 219     pl2->prev = pl1;
 220     pl1->next = pl2;
 221
 222     return pl2;
 223 }
 224
 225 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
 226                          if (!*x) { fprintf(stderr,y); return ; } }
 227
 228 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ;   \
 229                            if (!*x) { fprintf(stderr,z); return ; } }
 230 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ;   \
 231                            if (!*x) { fprintf(stderr,z); return ; } }
 232
 233 /*-----------------------------------------------------------------*/
 234 /* getPeepLine - parses the peep lines                             */
 235 /*-----------------------------------------------------------------*/
 236 static void getPeepLine (lineNode **head, char **bpp)
 237 {
 238     char lines[MAX_PATTERN_LEN];
 239     char *lp;
 240
 241     lineNode *currL = NULL ;
 242     char *bp = *bpp;
 243     while (1) {
 244
 245         if (!*bp) {
 246             fprintf(stderr,"unexpected end of match pattern\n");
 247             return ;
 248         }
 249
 250         if (*bp == '\n') {
 251             bp++ ;
 252             while (isspace(*bp) ||
 253                    *bp == '\n') bp++;
 254         }
 255
 256         if (*bp == '}') {
 257             bp++ ;
 258             break;
 259         }
 260
 261         /* read till end of line */
 262         lp = lines ;
 263         while ((*bp != '\n' && *bp != '}' ) && *bp)
 264             *lp++ = *bp++ ;
 265
 266         *lp = '\0';
 267         if (!currL)
 268             *head = currL = newLineNode (lines);
 269         else
 270             currL = connectLine(currL,newLineNode(lines));
 271     }
 272
 273     *bpp = bp;
 274 }
 275
 276 /*-----------------------------------------------------------------*/
 277 /* readRules - reads the rules from a string buffer                */
 278 /*-----------------------------------------------------------------*/
 279 static void readRules (char *bp)
 280 {
 281     char restart = 0 ;
 282     char lines[MAX_PATTERN_LEN];
 283     char *lp;
 284     lineNode *match;
 285     lineNode *replace;
 286     lineNode *currL = NULL;
 287
 288     if (!bp)
 289         return;
 290  top:
 291     restart = 0;
 292     /* look for the token "replace" that is the
 293        start of a rule */
 294     while (*bp && strncmp(bp,"replace",7)) bp++;
 295
 296     /* if not found */
 297     if (!*bp)
 298         return ;
 299
 300     /* then look for either "restart" or '{' */
 301     while (strncmp(bp,"restart",7) &&
 302            *bp != '{'  && bp ) bp++ ;
 303
 304     /* not found */
 305     if (!*bp) {
 306         fprintf(stderr,"expected 'restart' or '{'\n");
 307         return ;
 308     }
 309
 310     /* if brace */
 311     if (*bp == '{')
 312         bp++ ;
 313     else { /* must be restart */
 314         restart++;
 315         bp += strlen("restart");
 316         /* look for '{' */
 317         EXPECT_CHR(bp,'{',"expected '{'\n");
 318         bp++;
 319     }
 320
 321     /* skip thru all the blank space */
 322     SKIP_SPACE(bp,"unexpected end of rule\n");
 323
 324     match = replace = currL = NULL ;
 325     /* we are the start of a rule */
 326     getPeepLine(&match, &bp);
 327
 328     /* now look for by */
 329     EXPECT_STR(bp,"by","expected 'by'\n");
 330
 331     /* then look for a '{' */
 332     EXPECT_CHR(bp,'{',"expected '{'\n");
 333     bp++ ;
 334
 335     SKIP_SPACE(bp,"unexpected end of rule\n");
 336     getPeepLine (&replace, &bp);
 337
 338     /* look for a 'if' */
 339     while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
 340
 341     if (strncmp(bp,"if",2) == 0) {
 342         bp += 2;
 343         while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
 344         if (!*bp) {
 345             fprintf(stderr,"expected condition name\n");
 346             return;
 347         }
 348
 349         /* look for the condition */
 350         lp = lines;
 351         while (isalnum(*bp)) {
 352             *lp++ = *bp++;
 353         }
 354         *lp = '\0';
 355
 356         newPeepRule(match,replace,lines,restart);
 357     } else
 358         newPeepRule(match,replace,NULL,restart);
 359     goto top;
 360
 361 }
 362
 363 /*-----------------------------------------------------------------*/
 364 /* keyForVar - returns the numeric key for a var                   */
 365 /*-----------------------------------------------------------------*/
 366 static int keyForVar (char *d)
 367 {
 368     int i = 0;
 369
 370     while (isdigit(*d)) {
 371         i *= 10 ;
 372         i += (*d++ - '0') ;
 373     }
 374
 375     return i;
 376 }
 377
 378 /*-----------------------------------------------------------------*/
 379 /* bindVar - binds a value to a variable in the given hashtable    */
 380 /*-----------------------------------------------------------------*/
 381 static void bindVar (int key, char **s, hTab **vtab)
 382 {
 383     char vval[MAX_PATTERN_LEN];
 384     char *vvx;
 385     char *vv = vval;
 386
 387     /* first get the value of the variable */
 388     vvx = *s;
 389     /* the value is ended by a ',' or space or newline or null */
 390     while (*vvx           &&
 391            *vvx != ','    &&
 392            !isspace(*vvx) &&
 393            *vvx != '\n'   &&
 394            *vvx != ':' ) {
 395         char ubb = 0 ;
 396         /* if we find a '(' then we need to balance it */
 397         if (*vvx == '(') {
 398             ubb++ ;
 399             while (ubb) {
 400                 *vv++ = *vvx++ ;
 401                 if (*vvx == '(') ubb++;
 402                 if (*vvx == ')') ubb--;
 403             }
 404         } else
 405             *vv++ = *vvx++ ;
 406     }
 407     *s = vvx ;
 408     *vv = '\0';
 409     /* got value */
 410     ALLOC_ATOMIC(vvx,strlen(vval)+1);
 411     strcpy(vvx,vval);
 412     hTabAddItem(vtab,key,vvx);
 413
 414 }
 415
 416 /*-----------------------------------------------------------------*/
 417 /* matchLine - matches one line                                    */
 418 /*-----------------------------------------------------------------*/
 419 static bool matchLine (char *s, char *d, hTab **vars)
 420 {
 421
 422     if (!s || !(*s))
 423         return FALSE;
 424
 425     while (*s && *d) {
 426
 427         /* skip white space in both */
 428         while (isspace(*s)) s++;
 429         while (isspace(*d)) d++;
 430
 431         /* if the destination is a var */
 432         if (*d == '%' && isdigit(*(d+1))) {
 433             char *v = hTabItemWithKey(*vars,keyForVar(d+1));
 434             /* if the variable is already bound
 435                then it MUST match with dest */
 436             if (v) {
 437                 while (*v)
 438                     if (*v++ != *s++) return FALSE;
 439             } else
 440                 /* variable not bound we need to
 441                    bind it */
 442                 bindVar (keyForVar(d+1),&s,vars);
 443
 444             /* in either case go past the variable */
 445             d++ ;
 446             while (isdigit(*d)) d++;
 447         }
 448
 449         /* they should be an exact match other wise */
 450         if (*s && *d) {
 451             while (isspace(*s))s++;
 452             while (isspace(*d))d++;
 453             if (*s++ != *d++)
 454                 return FALSE;
 455         }
 456
 457     }
 458
 459     /* get rid of the trailing spaces
 460        in both source & destination */
 461     if (*s)
 462         while (isspace(*s)) s++;
 463
 464     if (*d)
 465         while (isspace(*d)) d++;
 466
 467     /* after all this if only one of them
 468        has something left over then no match */
 469     if (*s || *d)
 470         return FALSE ;
 471
 472     return TRUE ;
 473 }
 474
 475 /*-----------------------------------------------------------------*/
 476 /* matchRule - matches a all the rule lines                        */
 477 /*-----------------------------------------------------------------*/
 478 static bool matchRule (lineNode *pl,
 479                        lineNode **mtail,
 480                        peepRule *pr,
 481                        lineNode *head)
 482 {
 483     lineNode *spl ; /* source pl */
 484     lineNode *rpl ; /* rule peep line */
 485
 486     hTabClearAll(pr->vars);
 487 /*     setToNull((void **) &pr->vars);    */
 488 /*     pr->vars = newHashTable(100); */
 489
 490     /* for all the lines defined in the rule */
 491     rpl = pr->match;
 492     spl = pl ;
 493     while (spl && rpl) {
 494
 495         /* if the source line starts with a ';' then
 496            comment line don't process or the source line
 497            contains == . debugger information skip it */
 498         if (spl->line &&
 499             (*spl->line == ';' || spl->isDebug)) {
 500             spl = spl->next;
 501             continue;
 502         }
 503
 504         if (!matchLine(spl->line,rpl->line,&pr->vars))
 505             return FALSE ;
 506
 507         rpl = rpl->next ;
 508         if (rpl)
 509             spl = spl->next ;
 510     }
 511
 512     /* if rules ended */
 513     if (!rpl) {
 514         /* if this rule has additional conditions */
 515         if ( pr->cond) {
 516             if (callFuncByName (pr->cond, pr->vars,pl,head) ) {
 517                 *mtail = spl;
 518                 return TRUE;
 519             } else
 520                 return FALSE;
 521         } else {
 522             *mtail = spl;
 523             return TRUE;
 524         }
 525     }
 526     else
 527         return FALSE;
 528 }
 529
 530 /*-----------------------------------------------------------------*/
 531 /* replaceRule - does replacement of a matching pattern            */
 532 /*-----------------------------------------------------------------*/
 533 static void replaceRule (lineNode **shead, lineNode *stail, peepRule *pr)
 534 {
 535     lineNode *cl = NULL;
 536     lineNode *pl = NULL , *lhead = NULL;
 537     char lb[MAX_PATTERN_LEN];
 538     char *lbp;
 539     lineNode *comment = NULL;
 540
 541     /* collect all the comment lines in the source */
 542     for (cl = *shead ; cl != stail ; cl = cl->next) {
 543         if (cl->line && ( *cl->line == ';' || cl->isDebug)) {
 544             pl = (pl ? connectLine (pl,newLineNode(cl->line)) :
 545                   (comment = newLineNode(cl->line)));
 546             pl->isDebug = cl->isDebug;
 547         }
 548     }
 549     cl = NULL;
 550
 551     /* for all the lines in the replacement pattern do */
 552     for ( pl = pr->replace ; pl ; pl = pl->next ) {
 553         char *v;
 554         char *l;
 555         lbp = lb;
 556
 557         l = pl->line;
 558         while (*l) {
 559             /* if the line contains a variable */
 560             if (*l == '%' && isdigit(*(l+1))) {
 561                 v = hTabItemWithKey(pr->vars,keyForVar(l+1));
 562                 if (!v) {
 563                     fprintf(stderr,"used unbound variable in replacement\n");
 564                     l++;
 565                     continue;
 566                 }
 567                 while (*v)
 568                     *lbp++ = *v++;
 569                 l++;
 570                 while (isdigit(*l)) l++;
 571                 continue ;
 572             }
 573             *lbp++ = *l++;
 574         }
 575
 576         *lbp = '\0';
 577         if (cl)
 578             cl = connectLine(cl,newLineNode(lb));
 579         else
 580             lhead = cl = newLineNode(lb);
 581     }
 582
 583     /* add the comments if any to the head of list */
 584     if (comment) {
 585         lineNode *lc = comment;
 586         while (lc->next) lc = lc->next;
 587         lc->next = lhead;
 588         if (lhead)
 589             lhead->prev = lc;
 590         lhead = comment;
 591     }
 592
 593     /* now we need to connect / replace the original chain */
 594     /* if there is a prev then change it */
 595     if ((*shead)->prev) {
 596         (*shead)->prev->next = lhead;
 597         lhead->prev = (*shead)->prev;
 598     } else
 599         *shead = lhead;
 600     /* now for the tail */
 601     if (stail && stail->next) {
 602         stail->next->prev = cl;
 603         if (cl)
 604             cl->next = stail->next;
 605     }
 606 }
 607
 608 /*-----------------------------------------------------------------*/
 609 /* peepHole - matches & substitutes rules                          */
 610 /*-----------------------------------------------------------------*/
 611 void peepHole (lineNode **pls )
 612 {
 613     lineNode *spl ;
 614     peepRule *pr ;
 615     lineNode *mtail = NULL;
 616
 617  top:
 618     /* for all rules */
 619     for (pr = rootRules ; pr ; pr = pr->next ) {
 620
 621         for (spl = *pls ; spl ; spl = spl->next ) {
 622
 623             /* if inline assembler then no peep hole */
 624             if (spl->isInline)
 625                 continue ;
 626
 627             mtail = NULL ;
 628
 629             /* if it matches */
 630             if (matchRule (spl,&mtail,pr, *pls)) {
 631
 632                 /* then replace */
 633                 if (spl == *pls)
 634                     replaceRule(pls, mtail, pr);
 635                 else
 636                     replaceRule (&spl, mtail,pr);
 637
 638                 /* if it was the start then replace
 639                    the start */
 640
 641                 /* if restart rule type then
 642                    start at the top again */
 643                 if (pr->restart)
 644                     goto top;
 645             }
 646         }
 647     }
 648 }
 649
 650
 651 /*-----------------------------------------------------------------*/
 652 /* readFileIntoBuffer - reads a file into a string buffer          */
 653 /*-----------------------------------------------------------------*/
 654 static char *readFileIntoBuffer (char *fname)
 655 {
 656     FILE *f;
 657     char *rs = NULL;
 658     int nch = 0 ;
 659     int ch;
 660     char lb[MAX_PATTERN_LEN];
 661
 662     if (!(f = fopen(fname,"r"))) {
 663         fprintf(stderr,"cannot open peep rule file\n");
 664         return NULL;
 665     }
 666
 667     while ((ch = fgetc(f)) != EOF) {
 668         lb[nch++] = ch;
 669
 670         /* if we maxed out our local buffer */
 671         if (nch >= (MAX_PATTERN_LEN - 2)) {
 672             lb[nch] = '\0';
 673             /* copy it into allocated buffer */
 674             if (rs) {
 675                 rs = GC_realloc(rs,strlen(rs)+strlen(lb)+1);
 676                 strcat(rs,lb);
 677             } else {
 678                 ALLOC_ATOMIC(rs,strlen(lb)+1);
 679                 strcpy(rs,lb);
 680             }
 681             nch = 0 ;
 682         }
 683     }
 684
 685     /* if some charaters left over */
 686     if (nch) {
 687         lb[nch] = '\0';
 688         /* copy it into allocated buffer */
 689         if (rs) {
 690             rs = GC_realloc(rs,strlen(rs)+strlen(lb)+1);
 691             strcat(rs,lb);
 692         } else {
 693             ALLOC_ATOMIC(rs,strlen(lb)+1);
 694             strcpy(rs,lb);
 695         }
 696     }
 697     return rs;
 698 }
 699
 700 /*-----------------------------------------------------------------*/
 701 /* initPeepHole - initiaises the peep hole optimizer stuff         */
 702 /*-----------------------------------------------------------------*/
 703 void initPeepHole ()
 704 {
 705     char *s;
 706
 707     /* read in the default rules */
 708     readRules(defaultRules);
 709
 710     /* if we have any additional file read it too */
 711     if (options.peep_file) {
 712         readRules(s=readFileIntoBuffer(options.peep_file));
 713         setToNull((void **) &s);
 714     }
 715 }