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)
109 /*-----------------------------------------------------------------*/
110 /* operandsNotSame - check if %1 & %2 are the same */
111 /*-----------------------------------------------------------------*/
112 FBYNAME(operandsNotSame)
114 char *op1 = hTabItemWithKey(vars,1);
115 char *op2 = hTabItemWithKey(vars,2);
117 if (strcmp(op1,op2) == 0)
123 /*-----------------------------------------------------------------*/
124 /* callFuncByName - calls a function as defined in the table */
125 /*-----------------------------------------------------------------*/
126 int callFuncByName ( char *fname,
133 int (*func)(hTab *,lineNode *,lineNode *) ;
135 {"labelInRange", labelInRange },
136 {"operandsNotSame", operandsNotSame },
137 {"24bitMode", flat24bitMode },
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");
148 /*-----------------------------------------------------------------*/
149 /* printLine - prints a line chain into a given file */
150 /*-----------------------------------------------------------------*/
151 void printLine (lineNode *head, FILE *of)
157 /* don't indent comments & labels */
159 ( *head->line == ';' ||
160 head->line[strlen(head->line)-1] == ':'))
161 fprintf(of,"%s\n",head->line);
163 fprintf(of,"\t%s\n",head->line);
168 /*-----------------------------------------------------------------*/
169 /* newPeepRule - creates a new peeprule and attach it to the root */
170 /*-----------------------------------------------------------------*/
171 peepRule *newPeepRule (lineNode *match ,
178 ALLOC(pr,sizeof(peepRule));
180 pr->replace= replace;
181 pr->restart = restart;
184 ALLOC_ATOMIC(pr->cond,strlen(cond)+1);
185 strcpy(pr->cond,cond);
189 pr->vars = newHashTable(100);
191 /* if root is empty */
193 rootRules = currRule = pr;
195 currRule = currRule->next = pr;
200 /*-----------------------------------------------------------------*/
201 /* newLineNode - creates a new peep line */
202 /*-----------------------------------------------------------------*/
203 lineNode *newLineNode (char *line)
207 ALLOC(pl,sizeof(lineNode));
208 ALLOC_ATOMIC(pl->line,strlen(line)+1);
209 strcpy(pl->line,line);
213 /*-----------------------------------------------------------------*/
214 /* connectLine - connects two lines */
215 /*-----------------------------------------------------------------*/
216 lineNode *connectLine (lineNode *pl1, lineNode *pl2)
219 fprintf (stderr,"trying to connect null line\n");
229 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
230 if (!*x) { fprintf(stderr,y); return ; } }
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 ; } }
237 /*-----------------------------------------------------------------*/
238 /* getPeepLine - parses the peep lines */
239 /*-----------------------------------------------------------------*/
240 static void getPeepLine (lineNode **head, char **bpp)
242 char lines[MAX_PATTERN_LEN];
245 lineNode *currL = NULL ;
250 fprintf(stderr,"unexpected end of match pattern\n");
256 while (isspace(*bp) ||
265 /* read till end of line */
267 while ((*bp != '\n' && *bp != '}' ) && *bp)
272 *head = currL = newLineNode (lines);
274 currL = connectLine(currL,newLineNode(lines));
280 /*-----------------------------------------------------------------*/
281 /* readRules - reads the rules from a string buffer */
282 /*-----------------------------------------------------------------*/
283 static void readRules (char *bp)
286 char lines[MAX_PATTERN_LEN];
290 lineNode *currL = NULL;
296 /* look for the token "replace" that is the
298 while (*bp && strncmp(bp,"replace",7)) bp++;
304 /* then look for either "restart" or '{' */
305 while (strncmp(bp,"restart",7) &&
306 *bp != '{' && bp ) bp++ ;
310 fprintf(stderr,"expected 'restart' or '{'\n");
317 else { /* must be restart */
319 bp += strlen("restart");
321 EXPECT_CHR(bp,'{',"expected '{'\n");
325 /* skip thru all the blank space */
326 SKIP_SPACE(bp,"unexpected end of rule\n");
328 match = replace = currL = NULL ;
329 /* we are the start of a rule */
330 getPeepLine(&match, &bp);
332 /* now look for by */
333 EXPECT_STR(bp,"by","expected 'by'\n");
335 /* then look for a '{' */
336 EXPECT_CHR(bp,'{',"expected '{'\n");
339 SKIP_SPACE(bp,"unexpected end of rule\n");
340 getPeepLine (&replace, &bp);
342 /* look for a 'if' */
343 while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
345 if (strncmp(bp,"if",2) == 0) {
347 while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
349 fprintf(stderr,"expected condition name\n");
353 /* look for the condition */
355 while (isalnum(*bp)) {
360 newPeepRule(match,replace,lines,restart);
362 newPeepRule(match,replace,NULL,restart);
367 /*-----------------------------------------------------------------*/
368 /* keyForVar - returns the numeric key for a var */
369 /*-----------------------------------------------------------------*/
370 static int keyForVar (char *d)
374 while (isdigit(*d)) {
382 /*-----------------------------------------------------------------*/
383 /* bindVar - binds a value to a variable in the given hashtable */
384 /*-----------------------------------------------------------------*/
385 static void bindVar (int key, char **s, hTab **vtab)
387 char vval[MAX_PATTERN_LEN];
391 /* first get the value of the variable */
393 /* the value is ended by a ',' or space or newline or null */
400 /* if we find a '(' then we need to balance it */
405 if (*vvx == '(') ubb++;
406 if (*vvx == ')') ubb--;
414 ALLOC_ATOMIC(vvx,strlen(vval)+1);
416 hTabAddItem(vtab,key,vvx);
420 /*-----------------------------------------------------------------*/
421 /* matchLine - matches one line */
422 /*-----------------------------------------------------------------*/
423 static bool matchLine (char *s, char *d, hTab **vars)
431 /* skip white space in both */
432 while (isspace(*s)) s++;
433 while (isspace(*d)) d++;
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 */
442 if (*v++ != *s++) return FALSE;
444 /* variable not bound we need to
446 bindVar (keyForVar(d+1),&s,vars);
448 /* in either case go past the variable */
450 while (isdigit(*d)) d++;
453 /* they should be an exact match other wise */
455 while (isspace(*s))s++;
456 while (isspace(*d))d++;
463 /* get rid of the trailing spaces
464 in both source & destination */
466 while (isspace(*s)) s++;
469 while (isspace(*d)) d++;
471 /* after all this if only one of them
472 has something left over then no match */
479 /*-----------------------------------------------------------------*/
480 /* matchRule - matches a all the rule lines */
481 /*-----------------------------------------------------------------*/
482 static bool matchRule (lineNode *pl,
487 lineNode *spl ; /* source pl */
488 lineNode *rpl ; /* rule peep line */
490 hTabClearAll(pr->vars);
491 /* setToNull((void **) &pr->vars); */
492 /* pr->vars = newHashTable(100); */
494 /* for all the lines defined in the rule */
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 */
503 (*spl->line == ';' || spl->isDebug)) {
508 if (!matchLine(spl->line,rpl->line,&pr->vars))
518 /* if this rule has additional conditions */
520 if (callFuncByName (pr->cond, pr->vars,pl,head) ) {
534 /*-----------------------------------------------------------------*/
535 /* replaceRule - does replacement of a matching pattern */
536 /*-----------------------------------------------------------------*/
537 static void replaceRule (lineNode **shead, lineNode *stail, peepRule *pr)
540 lineNode *pl = NULL , *lhead = NULL;
541 char lb[MAX_PATTERN_LEN];
543 lineNode *comment = NULL;
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;
555 /* for all the lines in the replacement pattern do */
556 for ( pl = pr->replace ; pl ; pl = pl->next ) {
563 /* if the line contains a variable */
564 if (*l == '%' && isdigit(*(l+1))) {
565 v = hTabItemWithKey(pr->vars,keyForVar(l+1));
567 fprintf(stderr,"used unbound variable in replacement\n");
574 while (isdigit(*l)) l++;
582 cl = connectLine(cl,newLineNode(lb));
584 lhead = cl = newLineNode(lb);
587 /* add the comments if any to the head of list */
589 lineNode *lc = comment;
590 while (lc->next) lc = lc->next;
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;
604 /* now for the tail */
605 if (stail && stail->next) {
606 stail->next->prev = cl;
608 cl->next = stail->next;
612 /*-----------------------------------------------------------------*/
613 /* peepHole - matches & substitutes rules */
614 /*-----------------------------------------------------------------*/
615 void peepHole (lineNode **pls )
619 lineNode *mtail = NULL;
623 for (pr = rootRules ; pr ; pr = pr->next ) {
625 for (spl = *pls ; spl ; spl = spl->next ) {
627 /* if inline assembler then no peep hole */
634 if (matchRule (spl,&mtail,pr, *pls)) {
638 replaceRule(pls, mtail, pr);
640 replaceRule (&spl, mtail,pr);
642 /* if restart rule type then
643 start at the top again */
652 /*-----------------------------------------------------------------*/
653 /* readFileIntoBuffer - reads a file into a string buffer */
654 /*-----------------------------------------------------------------*/
655 static char *readFileIntoBuffer (char *fname)
661 char lb[MAX_PATTERN_LEN];
663 if (!(f = fopen(fname,"r"))) {
664 fprintf(stderr,"cannot open peep rule file\n");
668 while ((ch = fgetc(f)) != EOF) {
671 /* if we maxed out our local buffer */
672 if (nch >= (MAX_PATTERN_LEN - 2)) {
674 /* copy it into allocated buffer */
676 rs = GC_realloc(rs,strlen(rs)+strlen(lb)+1);
679 ALLOC_ATOMIC(rs,strlen(lb)+1);
686 /* if some charaters left over */
689 /* copy it into allocated buffer */
691 rs = GC_realloc(rs,strlen(rs)+strlen(lb)+1);
694 ALLOC_ATOMIC(rs,strlen(lb)+1);
701 /*-----------------------------------------------------------------*/
702 /* initPeepHole - initiaises the peep hole optimizer stuff */
703 /*-----------------------------------------------------------------*/
708 /* read in the default rules */
709 readRules(port->peep.default_rules);
711 /* if we have any additional file read it too */
712 if (options.peep_file) {
713 readRules(s=readFileIntoBuffer(options.peep_file));
714 setToNull((void **) &s);