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