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