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