1 /*-------------------------------------------------------------------------
2 SDCCpeeph.c - The peep hole optimizer: for interpreting the
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1999)
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
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.
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.
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 -------------------------------------------------------------------------*/
27 #include "SDCCpeeph.h"
29 peepRule *rootRules = NULL;
30 peepRule *currRule = NULL;
32 static bool matchLine (char *, char *, hTab **);
34 #define FBYNAME(x) int x (hTab *vars, lineNode *currPl, lineNode *head)
36 /*-----------------------------------------------------------------*/
37 /* pcDistance - afinds a label back ward or forward */
38 /*-----------------------------------------------------------------*/
39 int pcDistance (lineNode *cpos, char *lbl, bool back)
42 char buff[MAX_PATTERN_LEN];
45 sprintf(buff,"%s:",lbl);
50 pl->line[strlen(pl->line)-1] != ':' &&
55 if (strncmp(pl->line,buff,strlen(buff)) == 0)
67 /*-----------------------------------------------------------------*/
68 /* flat24bitMode - will check to see if we are in flat24 mode */
69 /*-----------------------------------------------------------------*/
70 FBYNAME(flat24bitMode)
72 return (options.model == MODEL_FLAT24);
75 /*-----------------------------------------------------------------*/
76 /* labelInRange - will check to see if label %5 is within range */
77 /*-----------------------------------------------------------------*/
80 /* assumes that %5 pattern variable has the label name */
81 char *lbl = hTabItemWithKey(vars,5);
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"))
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)) ;
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)
114 /*-----------------------------------------------------------------*/
115 /* operandsNotSame - check if %1 & %2 are the same */
116 /*-----------------------------------------------------------------*/
117 FBYNAME(operandsNotSame)
119 char *op1 = hTabItemWithKey(vars,1);
120 char *op2 = hTabItemWithKey(vars,2);
122 if (strcmp(op1,op2) == 0)
128 /*-----------------------------------------------------------------*/
129 /* callFuncByName - calls a function as defined in the table */
130 /*-----------------------------------------------------------------*/
131 int callFuncByName ( char *fname,
138 int (*func)(hTab *,lineNode *,lineNode *) ;
140 {"labelInRange", labelInRange },
141 {"operandsNotSame", operandsNotSame },
142 {"24bitMode", flat24bitMode },
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");
153 /*-----------------------------------------------------------------*/
154 /* printLine - prints a line chain into a given file */
155 /*-----------------------------------------------------------------*/
156 void printLine (lineNode *head, FILE *of)
162 /* don't indent comments & labels */
164 ( *head->line == ';' ||
165 head->line[strlen(head->line)-1] == ':'))
166 fprintf(of,"%s\n",head->line);
168 fprintf(of,"\t%s\n",head->line);
173 /*-----------------------------------------------------------------*/
174 /* newPeepRule - creates a new peeprule and attach it to the root */
175 /*-----------------------------------------------------------------*/
176 peepRule *newPeepRule (lineNode *match ,
183 ALLOC(pr,sizeof(peepRule));
185 pr->replace= replace;
186 pr->restart = restart;
189 ALLOC_ATOMIC(pr->cond,strlen(cond)+1);
190 strcpy(pr->cond,cond);
194 pr->vars = newHashTable(100);
196 /* if root is empty */
198 rootRules = currRule = pr;
200 currRule = currRule->next = pr;
205 /*-----------------------------------------------------------------*/
206 /* newLineNode - creates a new peep line */
207 /*-----------------------------------------------------------------*/
208 lineNode *newLineNode (char *line)
212 ALLOC(pl,sizeof(lineNode));
213 ALLOC_ATOMIC(pl->line,strlen(line)+1);
214 strcpy(pl->line,line);
218 /*-----------------------------------------------------------------*/
219 /* connectLine - connects two lines */
220 /*-----------------------------------------------------------------*/
221 lineNode *connectLine (lineNode *pl1, lineNode *pl2)
224 fprintf (stderr,"trying to connect null line\n");
234 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
235 if (!*x) { fprintf(stderr,y); return ; } }
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 ; } }
242 /*-----------------------------------------------------------------*/
243 /* getPeepLine - parses the peep lines */
244 /*-----------------------------------------------------------------*/
245 static void getPeepLine (lineNode **head, char **bpp)
247 char lines[MAX_PATTERN_LEN];
250 lineNode *currL = NULL ;
255 fprintf(stderr,"unexpected end of match pattern\n");
261 while (isspace(*bp) ||
270 /* read till end of line */
272 while ((*bp != '\n' && *bp != '}' ) && *bp)
277 *head = currL = newLineNode (lines);
279 currL = connectLine(currL,newLineNode(lines));
285 /*-----------------------------------------------------------------*/
286 /* readRules - reads the rules from a string buffer */
287 /*-----------------------------------------------------------------*/
288 static void readRules (char *bp)
291 char lines[MAX_PATTERN_LEN];
295 lineNode *currL = NULL;
301 /* look for the token "replace" that is the
303 while (*bp && strncmp(bp,"replace",7)) bp++;
309 /* then look for either "restart" or '{' */
310 while (strncmp(bp,"restart",7) &&
311 *bp != '{' && bp ) bp++ ;
315 fprintf(stderr,"expected 'restart' or '{'\n");
322 else { /* must be restart */
324 bp += strlen("restart");
326 EXPECT_CHR(bp,'{',"expected '{'\n");
330 /* skip thru all the blank space */
331 SKIP_SPACE(bp,"unexpected end of rule\n");
333 match = replace = currL = NULL ;
334 /* we are the start of a rule */
335 getPeepLine(&match, &bp);
337 /* now look for by */
338 EXPECT_STR(bp,"by","expected 'by'\n");
340 /* then look for a '{' */
341 EXPECT_CHR(bp,'{',"expected '{'\n");
344 SKIP_SPACE(bp,"unexpected end of rule\n");
345 getPeepLine (&replace, &bp);
347 /* look for a 'if' */
348 while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
350 if (strncmp(bp,"if",2) == 0) {
352 while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
354 fprintf(stderr,"expected condition name\n");
358 /* look for the condition */
360 while (isalnum(*bp)) {
365 newPeepRule(match,replace,lines,restart);
367 newPeepRule(match,replace,NULL,restart);
372 /*-----------------------------------------------------------------*/
373 /* keyForVar - returns the numeric key for a var */
374 /*-----------------------------------------------------------------*/
375 static int keyForVar (char *d)
379 while (isdigit(*d)) {
387 /*-----------------------------------------------------------------*/
388 /* bindVar - binds a value to a variable in the given hashtable */
389 /*-----------------------------------------------------------------*/
390 static void bindVar (int key, char **s, hTab **vtab)
392 char vval[MAX_PATTERN_LEN];
396 /* first get the value of the variable */
398 /* the value is ended by a ',' or space or newline or null */
405 /* if we find a '(' then we need to balance it */
410 if (*vvx == '(') ubb++;
411 if (*vvx == ')') ubb--;
419 ALLOC_ATOMIC(vvx,strlen(vval)+1);
421 hTabAddItem(vtab,key,vvx);
425 /*-----------------------------------------------------------------*/
426 /* matchLine - matches one line */
427 /*-----------------------------------------------------------------*/
428 static bool matchLine (char *s, char *d, hTab **vars)
436 /* skip white space in both */
437 while (isspace(*s)) s++;
438 while (isspace(*d)) d++;
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 */
447 if (*v++ != *s++) return FALSE;
449 /* variable not bound we need to
451 bindVar (keyForVar(d+1),&s,vars);
453 /* in either case go past the variable */
455 while (isdigit(*d)) d++;
458 /* they should be an exact match other wise */
460 while (isspace(*s))s++;
461 while (isspace(*d))d++;
468 /* get rid of the trailing spaces
469 in both source & destination */
471 while (isspace(*s)) s++;
474 while (isspace(*d)) d++;
476 /* after all this if only one of them
477 has something left over then no match */
484 /*-----------------------------------------------------------------*/
485 /* matchRule - matches a all the rule lines */
486 /*-----------------------------------------------------------------*/
487 static bool matchRule (lineNode *pl,
492 lineNode *spl ; /* source pl */
493 lineNode *rpl ; /* rule peep line */
495 hTabClearAll(pr->vars);
496 /* setToNull((void **) &pr->vars); */
497 /* pr->vars = newHashTable(100); */
499 /* for all the lines defined in the rule */
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 */
508 (*spl->line == ';' || spl->isDebug)) {
513 if (!matchLine(spl->line,rpl->line,&pr->vars))
523 /* if this rule has additional conditions */
525 if (callFuncByName (pr->cond, pr->vars,pl,head) ) {
539 /*-----------------------------------------------------------------*/
540 /* replaceRule - does replacement of a matching pattern */
541 /*-----------------------------------------------------------------*/
542 static void replaceRule (lineNode **shead, lineNode *stail, peepRule *pr)
545 lineNode *pl = NULL , *lhead = NULL;
546 char lb[MAX_PATTERN_LEN];
548 lineNode *comment = NULL;
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;
560 /* for all the lines in the replacement pattern do */
561 for ( pl = pr->replace ; pl ; pl = pl->next ) {
568 /* if the line contains a variable */
569 if (*l == '%' && isdigit(*(l+1))) {
570 v = hTabItemWithKey(pr->vars,keyForVar(l+1));
572 fprintf(stderr,"used unbound variable in replacement\n");
579 while (isdigit(*l)) l++;
587 cl = connectLine(cl,newLineNode(lb));
589 lhead = cl = newLineNode(lb);
592 /* add the comments if any to the head of list */
594 lineNode *lc = comment;
595 while (lc->next) lc = lc->next;
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;
609 /* now for the tail */
610 if (stail && stail->next) {
611 stail->next->prev = cl;
613 cl->next = stail->next;
617 /*-----------------------------------------------------------------*/
618 /* peepHole - matches & substitutes rules */
619 /*-----------------------------------------------------------------*/
620 void peepHole (lineNode **pls )
624 lineNode *mtail = NULL;
628 for (pr = rootRules ; pr ; pr = pr->next ) {
630 for (spl = *pls ; spl ; spl = spl->next ) {
632 /* if inline assembler then no peep hole */
639 if (matchRule (spl,&mtail,pr, *pls)) {
643 replaceRule(pls, mtail, pr);
645 replaceRule (&spl, mtail,pr);
647 /* if restart rule type then
648 start at the top again */
657 /*-----------------------------------------------------------------*/
658 /* readFileIntoBuffer - reads a file into a string buffer */
659 /*-----------------------------------------------------------------*/
660 static char *readFileIntoBuffer (char *fname)
666 char lb[MAX_PATTERN_LEN];
668 if (!(f = fopen(fname,"r"))) {
669 fprintf(stderr,"cannot open peep rule file\n");
673 while ((ch = fgetc(f)) != EOF) {
676 /* if we maxed out our local buffer */
677 if (nch >= (MAX_PATTERN_LEN - 2)) {
679 /* copy it into allocated buffer */
681 rs = GC_realloc(rs,strlen(rs)+strlen(lb)+1);
684 ALLOC_ATOMIC(rs,strlen(lb)+1);
691 /* if some charaters left over */
694 /* copy it into allocated buffer */
696 rs = GC_realloc(rs,strlen(rs)+strlen(lb)+1);
699 ALLOC_ATOMIC(rs,strlen(lb)+1);
706 /*-----------------------------------------------------------------*/
707 /* initPeepHole - initiaises the peep hole optimizer stuff */
708 /*-----------------------------------------------------------------*/
713 /* read in the default rules */
714 readRules(port->peep.default_rules);
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);