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"
30 peepRule *rootRules = NULL;
31 peepRule *currRule = NULL;
36 char name[SDCC_NAME_MAX + 1];
40 hTab *labelHash = NULL;
42 static int hashSymbolName(const char *name);
43 static void buildLabelRefCountHash(lineNode *head);
45 static bool matchLine (char *, char *, hTab **);
47 #define FBYNAME(x) int x (hTab *vars, lineNode *currPl, lineNode *head, \
50 /*-----------------------------------------------------------------*/
51 /* pcDistance - afinds a label back ward or forward */
52 /*-----------------------------------------------------------------*/
53 int pcDistance (lineNode *cpos, char *lbl, bool back)
56 char buff[MAX_PATTERN_LEN];
59 sprintf(buff,"%s:",lbl);
64 pl->line[strlen(pl->line)-1] != ':' &&
69 if (strncmp(pl->line,buff,strlen(buff)) == 0)
81 /*-----------------------------------------------------------------*/
82 /* flat24bitMode - will check to see if we are in flat24 mode */
83 /*-----------------------------------------------------------------*/
84 FBYNAME(flat24bitMode)
86 return (options.model == MODEL_FLAT24);
89 /*-----------------------------------------------------------------*/
90 /* labelInRange - will check to see if label %5 is within range */
91 /*-----------------------------------------------------------------*/
94 /* assumes that %5 pattern variable has the label name */
95 char *lbl = hTabItemWithKey(vars,5);
101 /* if the previous teo instructions are "ljmp"s then don't
102 do it since it can be part of a jump table */
103 if (currPl->prev && currPl->prev->prev &&
104 strstr(currPl->prev->line,"ljmp") &&
105 strstr(currPl->prev->prev->line,"ljmp"))
108 /* calculate the label distance : the jump for reladdr can be
109 +/- 127 bytes, here Iam assuming that an average 8051
110 instruction is 2 bytes long, so if the label is more than
111 63 intructions away, the label is considered out of range
112 for a relative jump. we could get more precise this will
113 suffice for now since it catches > 90% cases */
114 dist = (pcDistance(currPl,lbl,TRUE) +
115 pcDistance(currPl,lbl,FALSE)) ;
117 /* if (!dist || dist > 45) has produced wrong sjmp */
118 /* 07-Sep-2000 Michael Schmitt */
119 /* FIX for Peephole 132 */
120 /* switch with lots of case can lead to a sjmp with a distance */
121 /* out of the range for sjmp */
122 if (!dist || dist > 43)
128 /*-----------------------------------------------------------------*/
129 /* operandsNotSame - check if %1 & %2 are the same */
130 /*-----------------------------------------------------------------*/
131 FBYNAME(operandsNotSame)
133 char *op1 = hTabItemWithKey(vars,1);
134 char *op2 = hTabItemWithKey(vars,2);
136 if (strcmp(op1,op2) == 0)
144 * takes two parameters: a variable (bound to a label name)
145 * and an expected reference count.
147 * Returns TRUE if that label is defined and referenced exactly
148 * the given number of times.
150 FBYNAME(labelRefCount)
152 int varNumber, expectedRefCount;
155 /* If we don't have the label hash table yet, build it. */
158 buildLabelRefCountHash(head);
161 if (sscanf(cmdLine, "%*[ \t%]%d %d", &varNumber, &expectedRefCount) == 2)
163 char *label = hTabItemWithKey(vars, varNumber);
167 labelHashEntry *entry;
169 entry = hTabFirstItemWK(labelHash, hashSymbolName(label));
173 if (!strcmp(label, entry->name))
177 entry = hTabNextItemWK(labelHash);
183 fprintf(stderr, "labelRefCount: %s has refCount %d, want %d\n",
184 label, entry->refCount, expectedRefCount);
187 rc = (expectedRefCount == entry->refCount);
191 fprintf(stderr, "*** internal error: no label has entry for"
192 " %s in labelRefCount peephole.\n",
198 fprintf(stderr, "*** internal error: var %d not bound"
199 " in peephole labelRefCount rule.\n",
207 "*** internal error: labelRefCount peephole restriction"
208 " malformed: %s\n", cmdLine);
213 /*-----------------------------------------------------------------*/
214 /* callFuncByName - calls a function as defined in the table */
215 /*-----------------------------------------------------------------*/
216 int callFuncByName ( char *fname,
224 int (*func)(hTab *,lineNode *,lineNode *,const char *) ;
227 {"labelInRange", labelInRange },
228 {"operandsNotSame", operandsNotSame },
229 {"24bitMode", flat24bitMode },
230 {"labelRefCount", labelRefCount },
234 for ( i = 0 ; i < ((sizeof (ftab))/(sizeof(struct ftab))); i++)
235 if (strncmp(ftab[i].fname,fname,strlen(ftab[i].fname)) == 0)
237 return (*ftab[i].func)(vars,currPl,head,
238 fname + strlen(ftab[i].fname));
240 fprintf(stderr,"could not find named function in function table\n");
244 /*-----------------------------------------------------------------*/
245 /* printLine - prints a line chain into a given file */
246 /*-----------------------------------------------------------------*/
247 void printLine (lineNode *head, FILE *of)
253 /* don't indent comments & labels */
255 ( *head->line == ';' ||
256 head->line[strlen(head->line)-1] == ':'))
257 fprintf(of,"%s\n",head->line);
259 fprintf(of,"\t%s\n",head->line);
264 /*-----------------------------------------------------------------*/
265 /* newPeepRule - creates a new peeprule and attach it to the root */
266 /*-----------------------------------------------------------------*/
267 peepRule *newPeepRule (lineNode *match ,
274 pr= Safe_calloc(1,sizeof(peepRule));
276 pr->replace= replace;
277 pr->restart = restart;
280 pr->cond = Safe_calloc(1,strlen(cond)+1);
281 strcpy(pr->cond,cond);
285 pr->vars = newHashTable(100);
287 /* if root is empty */
289 rootRules = currRule = pr;
291 currRule = currRule->next = pr;
296 /*-----------------------------------------------------------------*/
297 /* newLineNode - creates a new peep line */
298 /*-----------------------------------------------------------------*/
299 lineNode *newLineNode (char *line)
303 pl = Safe_calloc(1,sizeof(lineNode));
304 pl->line = Safe_calloc(1,strlen(line)+1);
305 strcpy(pl->line,line);
309 /*-----------------------------------------------------------------*/
310 /* connectLine - connects two lines */
311 /*-----------------------------------------------------------------*/
312 lineNode *connectLine (lineNode *pl1, lineNode *pl2)
315 fprintf (stderr,"trying to connect null line\n");
325 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
326 if (!*x) { fprintf(stderr,y); return ; } }
328 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ; \
329 if (!*x) { fprintf(stderr,z); return ; } }
330 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ; \
331 if (!*x) { fprintf(stderr,z); return ; } }
333 /*-----------------------------------------------------------------*/
334 /* getPeepLine - parses the peep lines */
335 /*-----------------------------------------------------------------*/
336 static void getPeepLine (lineNode **head, char **bpp)
338 char lines[MAX_PATTERN_LEN];
341 lineNode *currL = NULL ;
346 fprintf(stderr,"unexpected end of match pattern\n");
352 while (isspace(*bp) ||
361 /* read till end of line */
363 while ((*bp != '\n' && *bp != '}' ) && *bp)
368 *head = currL = newLineNode (lines);
370 currL = connectLine(currL,newLineNode(lines));
376 /*-----------------------------------------------------------------*/
377 /* readRules - reads the rules from a string buffer */
378 /*-----------------------------------------------------------------*/
379 static void readRules (char *bp)
382 char lines[MAX_PATTERN_LEN];
386 lineNode *currL = NULL;
392 /* look for the token "replace" that is the
394 while (*bp && strncmp(bp,"replace",7)) bp++;
400 /* then look for either "restart" or '{' */
401 while (strncmp(bp,"restart",7) &&
402 *bp != '{' && bp ) bp++ ;
406 fprintf(stderr,"expected 'restart' or '{'\n");
413 else { /* must be restart */
415 bp += strlen("restart");
417 EXPECT_CHR(bp,'{',"expected '{'\n");
421 /* skip thru all the blank space */
422 SKIP_SPACE(bp,"unexpected end of rule\n");
424 match = replace = currL = NULL ;
425 /* we are the start of a rule */
426 getPeepLine(&match, &bp);
428 /* now look for by */
429 EXPECT_STR(bp,"by","expected 'by'\n");
431 /* then look for a '{' */
432 EXPECT_CHR(bp,'{',"expected '{'\n");
435 SKIP_SPACE(bp,"unexpected end of rule\n");
436 getPeepLine (&replace, &bp);
438 /* look for a 'if' */
439 while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
441 if (strncmp(bp,"if",2) == 0) {
443 while ((isspace(*bp) || *bp == '\n') && *bp) bp++;
445 fprintf(stderr,"expected condition name\n");
449 /* look for the condition */
451 while (*bp && (*bp != '\n')) {
456 newPeepRule(match,replace,lines,restart);
458 newPeepRule(match,replace,NULL,restart);
463 /*-----------------------------------------------------------------*/
464 /* keyForVar - returns the numeric key for a var */
465 /*-----------------------------------------------------------------*/
466 static int keyForVar (char *d)
470 while (isdigit(*d)) {
478 /*-----------------------------------------------------------------*/
479 /* bindVar - binds a value to a variable in the given hashtable */
480 /*-----------------------------------------------------------------*/
481 static void bindVar (int key, char **s, hTab **vtab)
483 char vval[MAX_PATTERN_LEN];
487 /* first get the value of the variable */
489 /* the value is ended by a ',' or space or newline or null */
496 /* if we find a '(' then we need to balance it */
501 if (*vvx == '(') ubb++;
502 if (*vvx == ')') ubb--;
510 vvx = Safe_calloc(1,strlen(vval)+1);
512 hTabAddItem(vtab,key,vvx);
516 /*-----------------------------------------------------------------*/
517 /* matchLine - matches one line */
518 /*-----------------------------------------------------------------*/
519 static bool matchLine (char *s, char *d, hTab **vars)
527 /* skip white space in both */
528 while (isspace(*s)) s++;
529 while (isspace(*d)) d++;
531 /* if the destination is a var */
532 if (*d == '%' && isdigit(*(d+1))) {
533 char *v = hTabItemWithKey(*vars,keyForVar(d+1));
534 /* if the variable is already bound
535 then it MUST match with dest */
538 if (*v++ != *s++) return FALSE;
540 /* variable not bound we need to
542 bindVar (keyForVar(d+1),&s,vars);
544 /* in either case go past the variable */
546 while (isdigit(*d)) d++;
549 /* they should be an exact match other wise */
551 while (isspace(*s))s++;
552 while (isspace(*d))d++;
559 /* get rid of the trailing spaces
560 in both source & destination */
562 while (isspace(*s)) s++;
565 while (isspace(*d)) d++;
567 /* after all this if only one of them
568 has something left over then no match */
575 /*-----------------------------------------------------------------*/
576 /* matchRule - matches a all the rule lines */
577 /*-----------------------------------------------------------------*/
578 static bool matchRule (lineNode *pl,
583 lineNode *spl ; /* source pl */
584 lineNode *rpl ; /* rule peep line */
586 hTabClearAll(pr->vars);
587 /* setToNull((void **) &pr->vars); */
588 /* pr->vars = newHashTable(100); */
590 /* for all the lines defined in the rule */
595 /* if the source line starts with a ';' then
596 comment line don't process or the source line
597 contains == . debugger information skip it */
599 (*spl->line == ';' || spl->isDebug)) {
604 if (!matchLine(spl->line,rpl->line,&pr->vars))
614 /* if this rule has additional conditions */
616 if (callFuncByName (pr->cond, pr->vars,pl,head) ) {
630 /*-----------------------------------------------------------------*/
631 /* replaceRule - does replacement of a matching pattern */
632 /*-----------------------------------------------------------------*/
633 static void replaceRule (lineNode **shead, lineNode *stail, peepRule *pr)
636 lineNode *pl = NULL , *lhead = NULL;
637 char lb[MAX_PATTERN_LEN];
639 lineNode *comment = NULL;
641 /* collect all the comment lines in the source */
642 for (cl = *shead ; cl != stail ; cl = cl->next) {
643 if (cl->line && ( *cl->line == ';' || cl->isDebug)) {
644 pl = (pl ? connectLine (pl,newLineNode(cl->line)) :
645 (comment = newLineNode(cl->line)));
646 pl->isDebug = cl->isDebug;
651 /* for all the lines in the replacement pattern do */
652 for ( pl = pr->replace ; pl ; pl = pl->next ) {
659 /* if the line contains a variable */
660 if (*l == '%' && isdigit(*(l+1))) {
661 v = hTabItemWithKey(pr->vars,keyForVar(l+1));
663 fprintf(stderr,"used unbound variable in replacement\n");
670 while (isdigit(*l)) l++;
678 cl = connectLine(cl,newLineNode(lb));
680 lhead = cl = newLineNode(lb);
683 /* add the comments if any to the head of list */
685 lineNode *lc = comment;
686 while (lc->next) lc = lc->next;
693 /* now we need to connect / replace the original chain */
694 /* if there is a prev then change it */
695 if ((*shead)->prev) {
696 (*shead)->prev->next = lhead;
697 lhead->prev = (*shead)->prev;
700 /* now for the tail */
701 if (stail && stail->next) {
702 stail->next->prev = cl;
704 cl->next = stail->next;
708 /* Returns TRUE if this line is a label definition.
710 * If so, start will point to the start of the label name,
711 * and len will be it's length.
713 bool isLabelDefinition(const char *line, const char **start, int *len)
715 const char *cp = line;
717 /* This line is a label if if consists of:
718 * [optional whitespace] followed by identifier chars
719 * (alnum | $ | _ ) followed by a colon.
722 while (*cp && isspace(*cp))
734 while (isalnum(*cp) || (*cp == '$') || (*cp == '_'))
739 if ((cp == *start) || (*cp != ':'))
744 *len = (cp - (*start));
748 /* Quick & dirty string hash function. */
749 static int hashSymbolName(const char *name)
755 hash = (hash << 6) ^ *name;
764 return hash % HTAB_SIZE;
767 /* Build a hash of all labels in the passed set of lines
768 * and how many times they are referenced.
770 static void buildLabelRefCountHash(lineNode *head)
777 assert(labelHash == NULL);
778 labelHash = newHashTable(HTAB_SIZE);
780 /* First pass: locate all the labels. */
785 if (isLabelDefinition(line->line, &label, &labelLen)
786 && labelLen <= SDCC_NAME_MAX)
788 labelHashEntry *entry;
790 entry = Safe_calloc(1,sizeof(labelHashEntry));
792 memcpy(entry->name, label, labelLen);
793 entry->name[labelLen] = 0;
794 entry->refCount = -1;
796 hTabAddItem(&labelHash, hashSymbolName(entry->name), entry);
802 /* Second pass: for each line, note all the referenced labels. */
803 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
807 for (i = 0; i < HTAB_SIZE; i++)
809 labelHashEntry *thisEntry;
811 thisEntry = hTabFirstItemWK(labelHash, i);
815 if (strstr(line->line, thisEntry->name))
817 thisEntry->refCount++;
819 thisEntry = hTabNextItemWK(labelHash);
826 /* Spew the contents of the table. Debugging fun only. */
827 for (i = 0; i < HTAB_SIZE; i++)
829 labelHashEntry *thisEntry;
831 thisEntry = hTabFirstItemWK(labelHash, i);
835 fprintf(stderr, "label: %s ref %d\n",
836 thisEntry->name, thisEntry->refCount);
837 thisEntry = hTabNextItemWK(labelHash);
843 /*-----------------------------------------------------------------*/
844 /* peepHole - matches & substitutes rules */
845 /*-----------------------------------------------------------------*/
846 void peepHole (lineNode **pls )
850 lineNode *mtail = NULL;
854 hTabDeleteAll(labelHash);
860 for (pr = rootRules ; pr ; pr = pr->next ) {
862 for (spl = *pls ; spl ; spl = spl->next ) {
864 /* if inline assembler then no peep hole */
871 if (matchRule (spl,&mtail,pr, *pls)) {
875 replaceRule(pls, mtail, pr);
877 replaceRule (&spl, mtail,pr);
879 /* if restart rule type then
880 start at the top again */
889 /*-----------------------------------------------------------------*/
890 /* readFileIntoBuffer - reads a file into a string buffer */
891 /*-----------------------------------------------------------------*/
892 static char *readFileIntoBuffer (char *fname)
898 char lb[MAX_PATTERN_LEN];
900 if (!(f = fopen(fname,"r"))) {
901 fprintf(stderr,"cannot open peep rule file\n");
905 while ((ch = fgetc(f)) != EOF) {
908 /* if we maxed out our local buffer */
909 if (nch >= (MAX_PATTERN_LEN - 2)) {
911 /* copy it into allocated buffer */
913 rs = Safe_realloc(rs,strlen(rs)+strlen(lb)+1);
916 rs = Safe_calloc(1,strlen(lb)+1);
923 /* if some charaters left over */
926 /* copy it into allocated buffer */
928 rs = Safe_realloc(rs,strlen(rs)+strlen(lb)+1);
931 rs = Safe_calloc(1,strlen(lb)+1);
938 /*-----------------------------------------------------------------*/
939 /* initPeepHole - initiaises the peep hole optimizer stuff */
940 /*-----------------------------------------------------------------*/
945 /* read in the default rules */
946 readRules(port->peep.default_rules);
948 /* if we have any additional file read it too */
949 if (options.peep_file) {
950 readRules(s=readFileIntoBuffer(options.peep_file));
951 setToNull((void **) &s);