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;
34 #include "SDCCpeeph.rul"
37 static bool matchLine (char *, char *, hTab **);
39 #define FBYNAME(x) int x (hTab *vars, lineNode *currPl, lineNode *head)
41 /*-----------------------------------------------------------------*/
42 /* pcDistance - afinds a label back ward or forward */
43 /*-----------------------------------------------------------------*/
44 int pcDistance (lineNode *cpos, char *lbl, bool back)
47 char buff[MAX_PATTERN_LEN];
50 sprintf(buff,"%s:",lbl);
55 pl->line[strlen(pl->line)-1] != ':' &&
60 if (strncmp(pl->line,buff,strlen(buff)) == 0)
72 /*-----------------------------------------------------------------*/
73 /* labelInRange - will check to see if label %5 is within range */
74 /*-----------------------------------------------------------------*/
77 /* assumes that %5 pattern variable has the label name */
78 char *lbl = hTabItemWithKey(vars,5);
84 /* if the previous teo instructions are "ljmp"s then don't
85 do it since it can be part of a jump table */
86 if (currPl->prev && currPl->prev->prev &&
87 strstr(currPl->prev->line,"ljmp") &&
88 strstr(currPl->prev->prev->line,"ljmp"))
91 /* calculate the label distance : the jump for reladdr can be
92 +/- 127 bytes, here Iam assuming that an average 8051
93 instruction is 2 bytes long, so if the label is more than
94 63 intructions away, the label is considered out of range
95 for a relative jump. we could get more precise this will
96 suffice for now since it catches > 90% cases */
97 dist = (pcDistance(currPl,lbl,TRUE) +
98 pcDistance(currPl,lbl,FALSE)) ;
100 if (!dist || dist > 45)
106 /*-----------------------------------------------------------------*/
107 /* operandsNotSame - check if %1 & %2 are the same */
108 /*-----------------------------------------------------------------*/
109 FBYNAME(operandsNotSame)
111 char *op1 = hTabItemWithKey(vars,1);
112 char *op2 = hTabItemWithKey(vars,2);
114 if (strcmp(op1,op2) == 0)
120 /*-----------------------------------------------------------------*/
121 /* callFuncByName - calls a function as defined in the table */
122 /*-----------------------------------------------------------------*/
123 int callFuncByName ( char *fname,
130 int (*func)(hTab *,lineNode *,lineNode *) ;
132 {"labelInRange", labelInRange },
133 {"operandsNotSame", operandsNotSame }
137 for ( i = 0 ; i < ((sizeof (ftab))/(sizeof(struct ftab))); i++)
138 if (strcmp(ftab[i].fname,fname) == 0)
139 return (*ftab[i].func)(vars,currPl,head);
140 fprintf(stderr,"could not find named function in function table\n");
144 /*-----------------------------------------------------------------*/
145 /* printLine - prints a line chain into a given file */
146 /*-----------------------------------------------------------------*/
147 void printLine (lineNode *head, FILE *of)
153 /* don't indent comments & labels */
155 ( *head->line == ';' ||
156 head->line[strlen(head->line)-1] == ':'))
157 fprintf(of,"%s\n",head->line);
159 fprintf(of,"\t%s\n",head->line);
164 /*-----------------------------------------------------------------*/
165 /* newPeepRule - creates a new peeprule and attach it to the root */
166 /*-----------------------------------------------------------------*/
167 peepRule *newPeepRule (lineNode *match ,
174 ALLOC(pr,sizeof(peepRule));
176 pr->replace= replace;
177 pr->restart = restart;
180 ALLOC_ATOMIC(pr->cond,strlen(cond)+1);
181 strcpy(pr->cond,cond);
185 pr->vars = newHashTable(100);
187 /* if root is empty */
189 rootRules = currRule = pr;
191 currRule = currRule->next = pr;
196 /*-----------------------------------------------------------------*/
197 /* newLineNode - creates a new peep line */
198 /*-----------------------------------------------------------------*/
199 lineNode *newLineNode (char *line)
203 ALLOC(pl,sizeof(lineNode));
204 ALLOC_ATOMIC(pl->line,strlen(line)+1);
205 strcpy(pl->line,line);
209 /*-----------------------------------------------------------------*/
210 /* connectLine - connects two lines */
211 /*-----------------------------------------------------------------*/
212 lineNode *connectLine (lineNode *pl1, lineNode *pl2)
215 fprintf (stderr,"trying to connect null line\n");
225 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
226 if (!*x) { fprintf(stderr,y); return ; } }
228 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ; \
229 if (!*x) { fprintf(stderr,z); return ; } }
230 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ; \
231 if (!*x) { fprintf(stderr,z); return ; } }
233 /*-----------------------------------------------------------------*/
234 /* getPeepLine - parses the peep lines */
235 /*-----------------------------------------------------------------*/
236 static void getPeepLine (lineNode **head, char **bpp)
238 char lines[MAX_PATTERN_LEN];
241 lineNode *currL = NULL ;
246 fprintf(stderr,"unexpected end of match pattern\n");
252 while (isspace(*bp) ||
261 /* read till end of line */
263 while ((*bp != '\n' && *bp != '}' ) && *bp)
268 *head = currL = newLineNode (lines);
270 currL = connectLine(currL,newLineNode(lines));
276 /*-----------------------------------------------------------------*/
277 /* readRules - reads the rules from a string buffer */
278 /*-----------------------------------------------------------------*/
279 static void readRules (char *bp)
282 char lines[MAX_PATTERN_LEN];
286 lineNode *currL = NULL;
292 /* look for the token "replace" that is the
294 while (*bp && strncmp(bp,"replace",7)) bp++;
300 /* then look for either "restart" or '{' */
301 while (strncmp(bp,"restart",7) &&
302 *bp != '{' && bp ) bp++ ;
306 fprintf(stderr,"expected 'restart' or '{'\n");
313 else { /* must be restart */
315 bp += strlen("restart");
317 EXPECT_CHR(bp,'{',"expected '{'\n");
321 /* skip thru all the blank space */
322 SKIP_SPACE(bp,"unexpected end of rule\n");
324 match = replace = currL = NULL ;
325 /* we are the start of a rule */
326 getPeepLine(&match, &bp);
328 /* now look for by */
329 EXPECT_STR(bp,"by","expected 'by'\n");
331 /* then look for a '{' */
332 EXPECT_CHR(bp,'{',"expected '{'\n");
335 SKIP_SPACE(bp,"unexpected end of rule\n");
336 getPeepLine (&replace, &bp);
338 /* look for a 'if' */
339 while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
341 if (strncmp(bp,"if",2) == 0) {
343 while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
345 fprintf(stderr,"expected condition name\n");
349 /* look for the condition */
351 while (isalnum(*bp)) {
356 newPeepRule(match,replace,lines,restart);
358 newPeepRule(match,replace,NULL,restart);
363 /*-----------------------------------------------------------------*/
364 /* keyForVar - returns the numeric key for a var */
365 /*-----------------------------------------------------------------*/
366 static int keyForVar (char *d)
370 while (isdigit(*d)) {
378 /*-----------------------------------------------------------------*/
379 /* bindVar - binds a value to a variable in the given hashtable */
380 /*-----------------------------------------------------------------*/
381 static void bindVar (int key, char **s, hTab **vtab)
383 char vval[MAX_PATTERN_LEN];
387 /* first get the value of the variable */
389 /* the value is ended by a ',' or space or newline or null */
396 /* if we find a '(' then we need to balance it */
401 if (*vvx == '(') ubb++;
402 if (*vvx == ')') ubb--;
410 ALLOC_ATOMIC(vvx,strlen(vval)+1);
412 hTabAddItem(vtab,key,vvx);
416 /*-----------------------------------------------------------------*/
417 /* matchLine - matches one line */
418 /*-----------------------------------------------------------------*/
419 static bool matchLine (char *s, char *d, hTab **vars)
427 /* skip white space in both */
428 while (isspace(*s)) s++;
429 while (isspace(*d)) d++;
431 /* if the destination is a var */
432 if (*d == '%' && isdigit(*(d+1))) {
433 char *v = hTabItemWithKey(*vars,keyForVar(d+1));
434 /* if the variable is already bound
435 then it MUST match with dest */
438 if (*v++ != *s++) return FALSE;
440 /* variable not bound we need to
442 bindVar (keyForVar(d+1),&s,vars);
444 /* in either case go past the variable */
446 while (isdigit(*d)) d++;
449 /* they should be an exact match other wise */
451 while (isspace(*s))s++;
452 while (isspace(*d))d++;
459 /* get rid of the trailing spaces
460 in both source & destination */
462 while (isspace(*s)) s++;
465 while (isspace(*d)) d++;
467 /* after all this if only one of them
468 has something left over then no match */
475 /*-----------------------------------------------------------------*/
476 /* matchRule - matches a all the rule lines */
477 /*-----------------------------------------------------------------*/
478 static bool matchRule (lineNode *pl,
483 lineNode *spl ; /* source pl */
484 lineNode *rpl ; /* rule peep line */
486 hTabClearAll(pr->vars);
487 /* setToNull((void **) &pr->vars); */
488 /* pr->vars = newHashTable(100); */
490 /* for all the lines defined in the rule */
495 /* if the source line starts with a ';' then
496 comment line don't process or the source line
497 contains == . debugger information skip it */
499 (*spl->line == ';' || spl->isDebug)) {
504 if (!matchLine(spl->line,rpl->line,&pr->vars))
514 /* if this rule has additional conditions */
516 if (callFuncByName (pr->cond, pr->vars,pl,head) ) {
530 /*-----------------------------------------------------------------*/
531 /* replaceRule - does replacement of a matching pattern */
532 /*-----------------------------------------------------------------*/
533 static void replaceRule (lineNode **shead, lineNode *stail, peepRule *pr)
536 lineNode *pl = NULL , *lhead = NULL;
537 char lb[MAX_PATTERN_LEN];
539 lineNode *comment = NULL;
541 /* collect all the comment lines in the source */
542 for (cl = *shead ; cl != stail ; cl = cl->next) {
543 if (cl->line && ( *cl->line == ';' || cl->isDebug)) {
544 pl = (pl ? connectLine (pl,newLineNode(cl->line)) :
545 (comment = newLineNode(cl->line)));
546 pl->isDebug = cl->isDebug;
551 /* for all the lines in the replacement pattern do */
552 for ( pl = pr->replace ; pl ; pl = pl->next ) {
559 /* if the line contains a variable */
560 if (*l == '%' && isdigit(*(l+1))) {
561 v = hTabItemWithKey(pr->vars,keyForVar(l+1));
563 fprintf(stderr,"used unbound variable in replacement\n");
570 while (isdigit(*l)) l++;
578 cl = connectLine(cl,newLineNode(lb));
580 lhead = cl = newLineNode(lb);
583 /* add the comments if any to the head of list */
585 lineNode *lc = comment;
586 while (lc->next) lc = lc->next;
593 /* now we need to connect / replace the original chain */
594 /* if there is a prev then change it */
595 if ((*shead)->prev) {
596 (*shead)->prev->next = lhead;
597 lhead->prev = (*shead)->prev;
600 /* now for the tail */
601 if (stail && stail->next) {
602 stail->next->prev = cl;
604 cl->next = stail->next;
608 /*-----------------------------------------------------------------*/
609 /* peepHole - matches & substitutes rules */
610 /*-----------------------------------------------------------------*/
611 void peepHole (lineNode **pls )
615 lineNode *mtail = NULL;
619 for (pr = rootRules ; pr ; pr = pr->next ) {
621 for (spl = *pls ; spl ; spl = spl->next ) {
623 /* if inline assembler then no peep hole */
630 if (matchRule (spl,&mtail,pr, *pls)) {
634 replaceRule(pls, mtail, pr);
636 replaceRule (&spl, mtail,pr);
638 /* if it was the start then replace
641 /* if restart rule type then
642 start at the top again */
651 /*-----------------------------------------------------------------*/
652 /* readFileIntoBuffer - reads a file into a string buffer */
653 /*-----------------------------------------------------------------*/
654 static char *readFileIntoBuffer (char *fname)
660 char lb[MAX_PATTERN_LEN];
662 if (!(f = fopen(fname,"r"))) {
663 fprintf(stderr,"cannot open peep rule file\n");
667 while ((ch = fgetc(f)) != EOF) {
670 /* if we maxed out our local buffer */
671 if (nch >= (MAX_PATTERN_LEN - 2)) {
673 /* copy it into allocated buffer */
675 rs = GC_realloc(rs,strlen(rs)+strlen(lb)+1);
678 ALLOC_ATOMIC(rs,strlen(lb)+1);
685 /* if some charaters left over */
688 /* copy it into allocated buffer */
690 rs = GC_realloc(rs,strlen(rs)+strlen(lb)+1);
693 ALLOC_ATOMIC(rs,strlen(lb)+1);
700 /*-----------------------------------------------------------------*/
701 /* initPeepHole - initiaises the peep hole optimizer stuff */
702 /*-----------------------------------------------------------------*/
707 /* read in the default rules */
708 readRules(defaultRules);
710 /* if we have any additional file read it too */
711 if (options.peep_file) {
712 readRules(s=readFileIntoBuffer(options.peep_file));
713 setToNull((void **) &s);