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];
41 hTab *labelHash = NULL;
43 static int hashSymbolName (const char *name);
44 static void buildLabelRefCountHash (lineNode * head);
46 static bool matchLine (char *, char *, hTab **);
48 #define FBYNAME(x) int x (hTab *vars, lineNode *currPl, lineNode *head, \
52 void peepRules2pCode(peepRule *);
55 /*-----------------------------------------------------------------*/
56 /* pcDistance - afinds a label back ward or forward */
57 /*-----------------------------------------------------------------*/
59 pcDistance (lineNode * cpos, char *lbl, bool back)
62 char buff[MAX_PATTERN_LEN];
65 sprintf (buff, "%s:", lbl);
71 pl->line[strlen (pl->line) - 1] != ':' &&
76 if (strncmp (pl->line, buff, strlen (buff)) == 0)
88 /*-----------------------------------------------------------------*/
89 /* flat24bitMode - will check to see if we are in flat24 mode */
90 /*-----------------------------------------------------------------*/
91 FBYNAME (flat24bitMode)
93 return (options.model == MODEL_FLAT24);
96 /*-----------------------------------------------------------------*/
97 /* labelInRange - will check to see if label %5 is within range */
98 /*-----------------------------------------------------------------*/
99 FBYNAME (labelInRange)
101 /* assumes that %5 pattern variable has the label name */
102 char *lbl = hTabItemWithKey (vars, 5);
108 /* if the previous teo instructions are "ljmp"s then don't
109 do it since it can be part of a jump table */
110 if (currPl->prev && currPl->prev->prev &&
111 strstr (currPl->prev->line, "ljmp") &&
112 strstr (currPl->prev->prev->line, "ljmp"))
115 /* calculate the label distance : the jump for reladdr can be
116 +/- 127 bytes, here Iam assuming that an average 8051
117 instruction is 2 bytes long, so if the label is more than
118 63 intructions away, the label is considered out of range
119 for a relative jump. we could get more precise this will
120 suffice for now since it catches > 90% cases */
121 dist = (pcDistance (currPl, lbl, TRUE) +
122 pcDistance (currPl, lbl, FALSE));
124 /* if (!dist || dist > 45) has produced wrong sjmp */
125 /* 07-Sep-2000 Michael Schmitt */
126 /* FIX for Peephole 132 */
127 /* switch with lots of case can lead to a sjmp with a distance */
128 /* out of the range for sjmp */
129 if (!dist || dist > 43)
135 /*-----------------------------------------------------------------*/
136 /* operandsNotSame - check if %1 & %2 are the same */
137 /*-----------------------------------------------------------------*/
138 FBYNAME (operandsNotSame)
140 char *op1 = hTabItemWithKey (vars, 1);
141 char *op2 = hTabItemWithKey (vars, 2);
143 if (strcmp (op1, op2) == 0)
151 * takes two parameters: a variable (bound to a label name)
152 * and an expected reference count.
154 * Returns TRUE if that label is defined and referenced exactly
155 * the given number of times.
157 FBYNAME (labelRefCount)
159 int varNumber, expectedRefCount;
162 /* If we don't have the label hash table yet, build it. */
165 buildLabelRefCountHash (head);
168 if (sscanf (cmdLine, "%*[ \t%]%d %d", &varNumber, &expectedRefCount) == 2)
170 char *label = hTabItemWithKey (vars, varNumber);
174 labelHashEntry *entry;
176 entry = hTabFirstItemWK (labelHash, hashSymbolName (label));
180 if (!strcmp (label, entry->name))
184 entry = hTabNextItemWK (labelHash);
190 fprintf (stderr, "labelRefCount: %s has refCount %d, want %d\n",
191 label, entry->refCount, expectedRefCount);
194 rc = (expectedRefCount == entry->refCount);
198 fprintf (stderr, "*** internal error: no label has entry for"
199 " %s in labelRefCount peephole.\n",
205 fprintf (stderr, "*** internal error: var %d not bound"
206 " in peephole labelRefCount rule.\n",
214 "*** internal error: labelRefCount peephole restriction"
215 " malformed: %s\n", cmdLine);
220 /*-----------------------------------------------------------------*/
221 /* callFuncByName - calls a function as defined in the table */
222 /*-----------------------------------------------------------------*/
224 callFuncByName (char *fname,
232 int (*func) (hTab *, lineNode *, lineNode *, const char *);
237 "labelInRange", labelInRange
241 "operandsNotSame", operandsNotSame
245 "24bitMode", flat24bitMode
249 "labelRefCount", labelRefCount
255 for (i = 0; i < ((sizeof (ftab)) / (sizeof (struct ftab))); i++)
256 if (strncmp (ftab[i].fname, fname, strlen (ftab[i].fname)) == 0)
258 return (*ftab[i].func) (vars, currPl, head,
259 fname + strlen (ftab[i].fname));
261 fprintf (stderr, "could not find named function in function table\n");
265 /*-----------------------------------------------------------------*/
266 /* printLine - prints a line chain into a given file */
267 /*-----------------------------------------------------------------*/
269 printLine (lineNode * head, FILE * of)
276 /* don't indent comments & labels */
278 (*head->line == ';' ||
279 head->line[strlen (head->line) - 1] == ':')) {
280 fprintf (of, "%s\n", head->line);
282 if (head->isInline && *head->line=='#') {
283 // comment out preprocessor directives in inline asm
286 fprintf (of, "\t%s\n", head->line);
292 /*-----------------------------------------------------------------*/
293 /* newPeepRule - creates a new peeprule and attach it to the root */
294 /*-----------------------------------------------------------------*/
296 newPeepRule (lineNode * match,
303 pr = Safe_calloc (1, sizeof (peepRule));
305 pr->replace = replace;
306 pr->restart = restart;
310 pr->cond = Safe_calloc (1, strlen (cond) + 1);
311 strcpy (pr->cond, cond);
316 pr->vars = newHashTable (100);
318 /* if root is empty */
320 rootRules = currRule = pr;
322 currRule = currRule->next = pr;
327 /*-----------------------------------------------------------------*/
328 /* newLineNode - creates a new peep line */
329 /*-----------------------------------------------------------------*/
331 newLineNode (char *line)
335 pl = Safe_calloc (1, sizeof (lineNode));
336 pl->line = Safe_calloc (1, strlen (line) + 1);
337 strcpy (pl->line, line);
341 /*-----------------------------------------------------------------*/
342 /* connectLine - connects two lines */
343 /*-----------------------------------------------------------------*/
345 connectLine (lineNode * pl1, lineNode * pl2)
349 fprintf (stderr, "trying to connect null line\n");
359 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
360 if (!*x) { fprintf(stderr,y); return ; } }
362 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ; \
363 if (!*x) { fprintf(stderr,z); return ; } }
364 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ; \
365 if (!*x) { fprintf(stderr,z); return ; } }
367 /*-----------------------------------------------------------------*/
368 /* getPeepLine - parses the peep lines */
369 /*-----------------------------------------------------------------*/
371 getPeepLine (lineNode ** head, char **bpp)
373 char lines[MAX_PATTERN_LEN];
376 lineNode *currL = NULL;
383 fprintf (stderr, "unexpected end of match pattern\n");
390 while (isspace (*bp) ||
401 /* read till end of line */
403 while ((*bp != '\n' && *bp != '}') && *bp)
408 *head = currL = newLineNode (lines);
410 currL = connectLine (currL, newLineNode (lines));
416 /*-----------------------------------------------------------------*/
417 /* readRules - reads the rules from a string buffer */
418 /*-----------------------------------------------------------------*/
423 char lines[MAX_PATTERN_LEN];
427 lineNode *currL = NULL;
433 /* look for the token "replace" that is the
435 while (*bp && strncmp (bp, "replace", 7))
442 /* then look for either "restart" or '{' */
443 while (strncmp (bp, "restart", 7) &&
450 fprintf (stderr, "expected 'restart' or '{'\n");
458 { /* must be restart */
460 bp += strlen ("restart");
462 EXPECT_CHR (bp, '{', "expected '{'\n");
466 /* skip thru all the blank space */
467 SKIP_SPACE (bp, "unexpected end of rule\n");
469 match = replace = currL = NULL;
470 /* we are the start of a rule */
471 getPeepLine (&match, &bp);
473 /* now look for by */
474 EXPECT_STR (bp, "by", "expected 'by'\n");
476 /* then look for a '{' */
477 EXPECT_CHR (bp, '{', "expected '{'\n");
480 SKIP_SPACE (bp, "unexpected end of rule\n");
481 getPeepLine (&replace, &bp);
483 /* look for a 'if' */
484 while ((isspace (*bp) || *bp == '\n') && *bp)
487 if (strncmp (bp, "if", 2) == 0)
490 while ((isspace (*bp) || *bp == '\n') && *bp)
494 fprintf (stderr, "expected condition name\n");
498 /* look for the condition */
500 while (*bp && (*bp != '\n'))
506 newPeepRule (match, replace, lines, restart);
509 newPeepRule (match, replace, NULL, restart);
514 /*-----------------------------------------------------------------*/
515 /* keyForVar - returns the numeric key for a var */
516 /*-----------------------------------------------------------------*/
531 /*-----------------------------------------------------------------*/
532 /* bindVar - binds a value to a variable in the given hashtable */
533 /*-----------------------------------------------------------------*/
535 bindVar (int key, char **s, hTab ** vtab)
537 char vval[MAX_PATTERN_LEN];
541 /* first get the value of the variable */
543 /* the value is ended by a ',' or space or newline or null or ) */
552 /* if we find a '(' then we need to balance it */
571 vvx = Safe_calloc (1, strlen (vval) + 1);
573 hTabAddItem (vtab, key, vvx);
577 /*-----------------------------------------------------------------*/
578 /* matchLine - matches one line */
579 /*-----------------------------------------------------------------*/
581 matchLine (char *s, char *d, hTab ** vars)
590 /* skip white space in both */
596 /* if the destination is a var */
597 if (*d == '%' && isdigit (*(d + 1)))
599 char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
600 /* if the variable is already bound
601 then it MUST match with dest */
609 /* variable not bound we need to
611 bindVar (keyForVar (d + 1), &s, vars);
613 /* in either case go past the variable */
619 /* they should be an exact match other wise */
632 /* get rid of the trailing spaces
633 in both source & destination */
642 /* after all this if only one of them
643 has something left over then no match */
650 /*-----------------------------------------------------------------*/
651 /* matchRule - matches a all the rule lines */
652 /*-----------------------------------------------------------------*/
654 matchRule (lineNode * pl,
659 lineNode *spl; /* source pl */
660 lineNode *rpl; /* rule peep line */
662 hTabClearAll (pr->vars);
663 /* setToNull((void **) &pr->vars); */
664 /* pr->vars = newHashTable(100); */
666 /* for all the lines defined in the rule */
672 /* if the source line starts with a ';' then
673 comment line don't process or the source line
674 contains == . debugger information skip it */
676 (*spl->line == ';' || spl->isDebug))
682 if (!matchLine (spl->line, rpl->line, &pr->vars))
693 /* if this rule has additional conditions */
696 if (callFuncByName (pr->cond, pr->vars, pl, head))
714 /*-----------------------------------------------------------------*/
715 /* replaceRule - does replacement of a matching pattern */
716 /*-----------------------------------------------------------------*/
718 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
721 lineNode *pl = NULL, *lhead = NULL;
722 /* a long function name and long variable name can evaluate to
723 4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
724 char lb[MAX_PATTERN_LEN*4];
726 lineNode *comment = NULL;
728 /* collect all the comment lines in the source */
729 for (cl = *shead; cl != stail; cl = cl->next)
731 if (cl->line && (*cl->line == ';' || cl->isDebug))
733 pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
734 (comment = newLineNode (cl->line)));
735 pl->isDebug = cl->isDebug;
740 /* for all the lines in the replacement pattern do */
741 for (pl = pr->replace; pl; pl = pl->next)
750 /* if the line contains a variable */
751 if (*l == '%' && isdigit (*(l + 1)))
753 v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
756 fprintf (stderr, "used unbound variable in replacement\n");
764 while (isdigit (*l)) {
774 cl = connectLine (cl, newLineNode (lb));
776 lhead = cl = newLineNode (lb);
779 /* add the comments if any to the head of list */
782 lineNode *lc = comment;
791 /* now we need to connect / replace the original chain */
792 /* if there is a prev then change it */
795 (*shead)->prev->next = lhead;
796 lhead->prev = (*shead)->prev;
800 /* now for the tail */
801 if (stail && stail->next)
803 stail->next->prev = cl;
805 cl->next = stail->next;
809 /* Returns TRUE if this line is a label definition.
811 * If so, start will point to the start of the label name,
812 * and len will be it's length.
815 isLabelDefinition (const char *line, const char **start, int *len)
817 const char *cp = line;
819 /* This line is a label if if consists of:
820 * [optional whitespace] followed by identifier chars
821 * (alnum | $ | _ ) followed by a colon.
824 while (*cp && isspace (*cp))
836 while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
841 if ((cp == *start) || (*cp != ':'))
846 *len = (cp - (*start));
850 /* Quick & dirty string hash function. */
852 hashSymbolName (const char *name)
858 hash = (hash << 6) ^ *name;
867 return hash % HTAB_SIZE;
870 /* Build a hash of all labels in the passed set of lines
871 * and how many times they are referenced.
874 buildLabelRefCountHash (lineNode * head)
881 assert (labelHash == NULL);
882 labelHash = newHashTable (HTAB_SIZE);
884 /* First pass: locate all the labels. */
889 if (isLabelDefinition (line->line, &label, &labelLen)
890 && labelLen <= SDCC_NAME_MAX)
892 labelHashEntry *entry;
894 entry = Safe_calloc (1, sizeof (labelHashEntry));
896 memcpy (entry->name, label, labelLen);
897 entry->name[labelLen] = 0;
898 entry->refCount = -1;
900 hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
906 /* Second pass: for each line, note all the referenced labels. */
907 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
911 for (i = 0; i < HTAB_SIZE; i++)
913 labelHashEntry *thisEntry;
915 thisEntry = hTabFirstItemWK (labelHash, i);
919 if (strstr (line->line, thisEntry->name))
921 thisEntry->refCount++;
923 thisEntry = hTabNextItemWK (labelHash);
930 /* Spew the contents of the table. Debugging fun only. */
931 for (i = 0; i < HTAB_SIZE; i++)
933 labelHashEntry *thisEntry;
935 thisEntry = hTabFirstItemWK (labelHash, i);
939 fprintf (stderr, "label: %s ref %d\n",
940 thisEntry->name, thisEntry->refCount);
941 thisEntry = hTabNextItemWK (labelHash);
947 /*-----------------------------------------------------------------*/
948 /* peepHole - matches & substitutes rules */
949 /*-----------------------------------------------------------------*/
951 peepHole (lineNode ** pls)
955 lineNode *mtail = NULL;
959 hTabDeleteAll (labelHash);
965 for (pr = rootRules; pr; pr = pr->next)
968 for (spl = *pls; spl; spl = spl->next)
970 /* if inline assembler then no peep hole */
977 if (matchRule (spl, &mtail, pr, *pls))
982 replaceRule (pls, mtail, pr);
984 replaceRule (&spl, mtail, pr);
986 /* if restart rule type then
987 start at the top again */
996 /*-----------------------------------------------------------------*/
997 /* readFileIntoBuffer - reads a file into a string buffer */
998 /*-----------------------------------------------------------------*/
1000 readFileIntoBuffer (char *fname)
1006 char lb[MAX_PATTERN_LEN];
1008 if (!(f = fopen (fname, "r")))
1010 fprintf (stderr, "cannot open peep rule file\n");
1014 while ((ch = fgetc (f)) != EOF)
1018 /* if we maxed out our local buffer */
1019 if (nch >= (MAX_PATTERN_LEN - 2))
1022 /* copy it into allocated buffer */
1025 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1030 rs = Safe_calloc (1, strlen (lb) + 1);
1037 /* if some charaters left over */
1041 /* copy it into allocated buffer */
1044 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1049 rs = Safe_calloc (1, strlen (lb) + 1);
1056 /*-----------------------------------------------------------------*/
1057 /* initPeepHole - initialises the peep hole optimizer stuff */
1058 /*-----------------------------------------------------------------*/
1064 /* read in the default rules */
1065 readRules (port->peep.default_rules);
1067 /* if we have any additional file read it too */
1068 if (options.peep_file)
1070 readRules (s = readFileIntoBuffer (options.peep_file));
1071 setToNull ((void **) &s);
1075 #if !OPT_DISABLE_PIC
1076 /* Convert the peep rules into pcode.
1077 NOTE: this is only support in the PIC port (at the moment)
1079 if (TARGET_IS_PIC) {
1080 peepRules2pCode(rootRules);