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