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 -------------------------------------------------------------------------*/
28 static peepRule *rootRules = NULL;
29 static peepRule *currRule = NULL;
34 char name[SDCC_NAME_MAX + 1];
39 static hTab *labelHash = NULL;
47 static int hashSymbolName (const char *name);
48 static void buildLabelRefCountHash (lineNode * head);
50 static bool matchLine (char *, char *, hTab **);
52 #define FBYNAME(x) int x (hTab *vars, lineNode *currPl, lineNode *head, \
56 void peepRules2pCode(peepRule *);
59 /*-----------------------------------------------------------------*/
60 /* pcDistance - afinds a label back ward or forward */
61 /*-----------------------------------------------------------------*/
63 pcDistance (lineNode * cpos, char *lbl, bool back)
66 char buff[MAX_PATTERN_LEN];
69 sprintf (buff, "%s:", lbl);
75 pl->line[strlen (pl->line) - 1] != ':' &&
80 if (strncmp (pl->line, buff, strlen (buff)) == 0)
92 /*-----------------------------------------------------------------*/
93 /* flat24bitModeAndPortDS390 - */
94 /*-----------------------------------------------------------------*/
95 FBYNAME (flat24bitModeAndPortDS390)
97 return ((strcmp(port->target,"ds390") == 0) &&
98 (options.model == MODEL_FLAT24));
101 /*-----------------------------------------------------------------*/
102 /* portIsDS390 - return true if port is DS390 */
103 /*-----------------------------------------------------------------*/
104 FBYNAME (portIsDS390)
106 return (strcmp(port->target,"ds390") == 0);
109 /*-----------------------------------------------------------------*/
110 /* flat24bitMode - will check to see if we are in flat24 mode */
111 /*-----------------------------------------------------------------*/
112 FBYNAME (flat24bitMode)
114 return (options.model == MODEL_FLAT24);
117 /*-----------------------------------------------------------------*/
118 /* xramMovcOption - check if using movc to read xram */
119 /*-----------------------------------------------------------------*/
120 FBYNAME (xramMovcOption)
122 return (options.xram_movc && (strcmp(port->target,"mcs51") == 0));
125 /*-----------------------------------------------------------------*/
126 /* labelInRange - will check to see if label %5 is within range */
127 /*-----------------------------------------------------------------*/
128 FBYNAME (labelInRange)
130 /* assumes that %5 pattern variable has the label name */
131 char *lbl = hTabItemWithKey (vars, 5);
137 /* if the previous two instructions are "ljmp"s then don't
138 do it since it can be part of a jump table */
139 if (currPl->prev && currPl->prev->prev &&
140 strstr (currPl->prev->line, "ljmp") &&
141 strstr (currPl->prev->prev->line, "ljmp"))
144 /* calculate the label distance : the jump for reladdr can be
145 +/- 127 bytes, here Iam assuming that an average 8051
146 instruction is 2 bytes long, so if the label is more than
147 63 intructions away, the label is considered out of range
148 for a relative jump. we could get more precise this will
149 suffice for now since it catches > 90% cases */
150 dist = (pcDistance (currPl, lbl, TRUE) +
151 pcDistance (currPl, lbl, FALSE));
153 /* if (!dist || dist > 45) has produced wrong sjmp */
154 /* 07-Sep-2000 Michael Schmitt */
155 /* FIX for Peephole 132 */
156 /* switch with lots of case can lead to a sjmp with a distance */
157 /* out of the range for sjmp */
158 if (!dist || dist > 43)
164 /*-----------------------------------------------------------------*/
165 /* operandsNotSame - check if %1 & %2 are the same */
166 /*-----------------------------------------------------------------*/
167 FBYNAME (operandsNotSame)
169 char *op1 = hTabItemWithKey (vars, 1);
170 char *op2 = hTabItemWithKey (vars, 2);
172 if (strcmp (op1, op2) == 0)
180 * takes two parameters: a variable (bound to a label name)
181 * and an expected reference count.
183 * Returns TRUE if that label is defined and referenced exactly
184 * the given number of times.
186 FBYNAME (labelRefCount)
188 int varNumber, expectedRefCount;
191 /* If we don't have the label hash table yet, build it. */
194 buildLabelRefCountHash (head);
197 if (sscanf (cmdLine, "%*[ \t%]%d %d", &varNumber, &expectedRefCount) == 2)
199 char *label = hTabItemWithKey (vars, varNumber);
203 labelHashEntry *entry;
205 entry = hTabFirstItemWK (labelHash, hashSymbolName (label));
209 if (!strcmp (label, entry->name))
213 entry = hTabNextItemWK (labelHash);
219 fprintf (stderr, "labelRefCount: %s has refCount %d, want %d\n",
220 label, entry->refCount, expectedRefCount);
223 rc = (expectedRefCount == entry->refCount);
227 fprintf (stderr, "*** internal error: no label has entry for"
228 " %s in labelRefCount peephole.\n",
234 fprintf (stderr, "*** internal error: var %d not bound"
235 " in peephole labelRefCount rule.\n",
243 "*** internal error: labelRefCount peephole restriction"
244 " malformed: %s\n", cmdLine);
249 /*-----------------------------------------------------------------*/
250 /* callFuncByName - calls a function as defined in the table */
251 /*-----------------------------------------------------------------*/
253 callFuncByName (char *fname,
261 int (*func) (hTab *, lineNode *, lineNode *, const char *);
266 "labelInRange", labelInRange
270 "operandsNotSame", operandsNotSame
274 "24bitMode", flat24bitMode
278 "xramMovcOption", xramMovcOption
282 "labelRefCount", labelRefCount
286 "portIsDS390", portIsDS390
289 "24bitModeAndPortDS390", flat24bitModeAndPortDS390
294 for (i = 0; i < ((sizeof (ftab)) / (sizeof (struct ftab))); i++)
295 if (strncmp (ftab[i].fname, fname, strlen (ftab[i].fname)) == 0)
297 return (*ftab[i].func) (vars, currPl, head,
298 fname + strlen (ftab[i].fname));
300 fprintf (stderr, "could not find named function in function table\n");
304 /*-----------------------------------------------------------------*/
305 /* printLine - prints a line chain into a given file */
306 /*-----------------------------------------------------------------*/
308 printLine (lineNode * head, FILE * of)
315 /* don't indent comments & labels */
317 (*head->line == ';' ||
318 head->line[strlen (head->line) - 1] == ':')) {
319 fprintf (of, "%s\n", head->line);
321 if (head->isInline && *head->line=='#') {
322 // comment out preprocessor directives in inline asm
325 fprintf (of, "\t%s\n", head->line);
331 /*-----------------------------------------------------------------*/
332 /* newPeepRule - creates a new peeprule and attach it to the root */
333 /*-----------------------------------------------------------------*/
335 newPeepRule (lineNode * match,
342 pr = Safe_alloc ( sizeof (peepRule));
344 pr->replace = replace;
345 pr->restart = restart;
349 pr->cond = Safe_alloc ( strlen (cond) + 1);
350 strcpy (pr->cond, cond);
355 pr->vars = newHashTable (100);
357 /* if root is empty */
359 rootRules = currRule = pr;
361 currRule = currRule->next = pr;
366 /*-----------------------------------------------------------------*/
367 /* newLineNode - creates a new peep line */
368 /*-----------------------------------------------------------------*/
370 newLineNode (char *line)
374 pl = Safe_alloc ( sizeof (lineNode));
375 pl->line = Safe_alloc ( strlen (line) + 1);
376 strcpy (pl->line, line);
380 /*-----------------------------------------------------------------*/
381 /* connectLine - connects two lines */
382 /*-----------------------------------------------------------------*/
384 connectLine (lineNode * pl1, lineNode * pl2)
388 fprintf (stderr, "trying to connect null line\n");
398 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
399 if (!*x) { fprintf(stderr,y); return ; } }
401 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ; \
402 if (!*x) { fprintf(stderr,z); return ; } }
403 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ; \
404 if (!*x) { fprintf(stderr,z); return ; } }
406 /*-----------------------------------------------------------------*/
407 /* getPeepLine - parses the peep lines */
408 /*-----------------------------------------------------------------*/
410 getPeepLine (lineNode ** head, char **bpp)
412 char lines[MAX_PATTERN_LEN];
415 lineNode *currL = NULL;
422 fprintf (stderr, "unexpected end of match pattern\n");
429 while (isspace (*bp) ||
440 /* read till end of line */
442 while ((*bp != '\n' && *bp != '}') && *bp)
447 *head = currL = newLineNode (lines);
449 currL = connectLine (currL, newLineNode (lines));
455 /*-----------------------------------------------------------------*/
456 /* readRules - reads the rules from a string buffer */
457 /*-----------------------------------------------------------------*/
462 char lines[MAX_PATTERN_LEN];
466 lineNode *currL = NULL;
472 /* look for the token "replace" that is the
474 while (*bp && strncmp (bp, "replace", 7))
481 /* then look for either "restart" or '{' */
482 while (strncmp (bp, "restart", 7) &&
489 fprintf (stderr, "expected 'restart' or '{'\n");
497 { /* must be restart */
499 bp += strlen ("restart");
501 EXPECT_CHR (bp, '{', "expected '{'\n");
505 /* skip thru all the blank space */
506 SKIP_SPACE (bp, "unexpected end of rule\n");
508 match = replace = currL = NULL;
509 /* we are the start of a rule */
510 getPeepLine (&match, &bp);
512 /* now look for by */
513 EXPECT_STR (bp, "by", "expected 'by'\n");
515 /* then look for a '{' */
516 EXPECT_CHR (bp, '{', "expected '{'\n");
519 SKIP_SPACE (bp, "unexpected end of rule\n");
520 getPeepLine (&replace, &bp);
522 /* look for a 'if' */
523 while ((isspace (*bp) || *bp == '\n') && *bp)
526 if (strncmp (bp, "if", 2) == 0)
529 while ((isspace (*bp) || *bp == '\n') && *bp)
533 fprintf (stderr, "expected condition name\n");
537 /* look for the condition */
539 while (*bp && (*bp != '\n'))
545 newPeepRule (match, replace, lines, restart);
548 newPeepRule (match, replace, NULL, restart);
553 /*-----------------------------------------------------------------*/
554 /* keyForVar - returns the numeric key for a var */
555 /*-----------------------------------------------------------------*/
570 /*-----------------------------------------------------------------*/
571 /* bindVar - binds a value to a variable in the given hashtable */
572 /*-----------------------------------------------------------------*/
574 bindVar (int key, char **s, hTab ** vtab)
576 char vval[MAX_PATTERN_LEN];
580 /* first get the value of the variable */
582 /* the value is ended by a ',' or space or newline or null or ) */
591 /* if we find a '(' then we need to balance it */
603 // include the trailing ')'
612 vvx = traceAlloc (&_G.values, Safe_alloc(strlen (vval) + 1));
615 hTabAddItem (vtab, key, vvx);
618 /*-----------------------------------------------------------------*/
619 /* matchLine - matches one line */
620 /*-----------------------------------------------------------------*/
622 matchLine (char *s, char *d, hTab ** vars)
631 /* skip white space in both */
637 /* if the destination is a var */
638 if (*d == '%' && isdigit (*(d + 1)))
640 char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
641 /* if the variable is already bound
642 then it MUST match with dest */
650 /* variable not bound we need to
652 bindVar (keyForVar (d + 1), &s, vars);
654 /* in either case go past the variable */
660 /* they should be an exact match other wise */
673 /* get rid of the trailing spaces
674 in both source & destination */
683 /* after all this if only one of them
684 has something left over then no match */
691 /*-----------------------------------------------------------------*/
692 /* matchRule - matches a all the rule lines */
693 /*-----------------------------------------------------------------*/
695 matchRule (lineNode * pl,
700 lineNode *spl; /* source pl */
701 lineNode *rpl; /* rule peep line */
703 /* setToNull((void **) &pr->vars); */
704 /* pr->vars = newHashTable(100); */
706 /* for all the lines defined in the rule */
712 /* if the source line starts with a ';' then
713 comment line don't process or the source line
714 contains == . debugger information skip it */
716 (*spl->line == ';' || spl->isDebug))
722 if (!matchLine (spl->line, rpl->line, &pr->vars))
733 /* if this rule has additional conditions */
736 if (callFuncByName (pr->cond, pr->vars, pl, head))
754 /*-----------------------------------------------------------------*/
755 /* replaceRule - does replacement of a matching pattern */
756 /*-----------------------------------------------------------------*/
758 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
761 lineNode *pl = NULL, *lhead = NULL;
762 /* a long function name and long variable name can evaluate to
763 4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
764 char lb[MAX_PATTERN_LEN*4];
766 lineNode *comment = NULL;
768 /* collect all the comment lines in the source */
769 for (cl = *shead; cl != stail; cl = cl->next)
771 if (cl->line && (*cl->line == ';' || cl->isDebug))
773 pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
774 (comment = newLineNode (cl->line)));
775 pl->isDebug = cl->isDebug;
780 /* for all the lines in the replacement pattern do */
781 for (pl = pr->replace; pl; pl = pl->next)
791 /* if the line contains a variable */
792 if (*l == '%' && isdigit (*(l + 1)))
794 v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
797 fprintf (stderr, "used unbound variable in replacement\n");
805 while (isdigit (*l)) {
815 cl = connectLine (cl, newLineNode (lb));
817 lhead = cl = newLineNode (lb);
820 /* add the comments if any to the head of list */
823 lineNode *lc = comment;
832 /* now we need to connect / replace the original chain */
833 /* if there is a prev then change it */
836 (*shead)->prev->next = lhead;
837 lhead->prev = (*shead)->prev;
840 /* now for the tail */
841 if (stail && stail->next)
843 stail->next->prev = cl;
845 cl->next = stail->next;
849 /* Returns TRUE if this line is a label definition.
851 * If so, start will point to the start of the label name,
852 * and len will be it's length.
855 isLabelDefinition (const char *line, const char **start, int *len)
857 const char *cp = line;
859 /* This line is a label if if consists of:
860 * [optional whitespace] followed by identifier chars
861 * (alnum | $ | _ ) followed by a colon.
864 while (*cp && isspace (*cp))
876 while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
881 if ((cp == *start) || (*cp != ':'))
886 *len = (cp - (*start));
890 /* Quick & dirty string hash function. */
892 hashSymbolName (const char *name)
898 hash = (hash << 6) ^ *name;
907 return hash % HTAB_SIZE;
910 /* Build a hash of all labels in the passed set of lines
911 * and how many times they are referenced.
914 buildLabelRefCountHash (lineNode * head)
921 assert (labelHash == NULL);
922 labelHash = newHashTable (HTAB_SIZE);
924 /* First pass: locate all the labels. */
929 if (isLabelDefinition (line->line, &label, &labelLen)
930 && labelLen <= SDCC_NAME_MAX)
932 labelHashEntry *entry;
934 entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
936 memcpy (entry->name, label, labelLen);
937 entry->name[labelLen] = 0;
938 entry->refCount = -1;
940 hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
946 /* Second pass: for each line, note all the referenced labels. */
947 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
951 for (i = 0; i < HTAB_SIZE; i++)
953 labelHashEntry *thisEntry;
955 thisEntry = hTabFirstItemWK (labelHash, i);
959 if (strstr (line->line, thisEntry->name))
961 thisEntry->refCount++;
963 thisEntry = hTabNextItemWK (labelHash);
970 /* Spew the contents of the table. Debugging fun only. */
971 for (i = 0; i < HTAB_SIZE; i++)
973 labelHashEntry *thisEntry;
975 thisEntry = hTabFirstItemWK (labelHash, i);
979 fprintf (stderr, "label: %s ref %d\n",
980 thisEntry->name, thisEntry->refCount);
981 thisEntry = hTabNextItemWK (labelHash);
987 /* How does this work?
998 Where is stuff allocated?
1002 /*-----------------------------------------------------------------*/
1003 /* peepHole - matches & substitutes rules */
1004 /*-----------------------------------------------------------------*/
1006 peepHole (lineNode ** pls)
1010 lineNode *mtail = NULL;
1013 #if !OPT_DISABLE_PIC
1014 /* The PIC port uses a different peep hole optimizer based on "pCode" */
1019 assert(labelHash == NULL);
1026 for (pr = rootRules; pr; pr = pr->next)
1028 for (spl = *pls; spl; spl = spl->next)
1030 /* if inline assembler then no peep hole */
1036 /* Tidy up any data stored in the hTab */
1039 if (matchRule (spl, &mtail, pr, *pls))
1044 replaceRule (pls, mtail, pr);
1046 replaceRule (&spl, mtail, pr);
1048 /* if restart rule type then
1049 start at the top again */
1058 hTabDeleteAll (pr->vars);
1059 Safe_free (pr->vars);
1063 freeTrace (&_G.values);
1066 } while (restart == TRUE);
1070 hTabDeleteAll (labelHash);
1071 freeTrace (&_G.labels);
1077 /*-----------------------------------------------------------------*/
1078 /* readFileIntoBuffer - reads a file into a string buffer */
1079 /*-----------------------------------------------------------------*/
1081 readFileIntoBuffer (char *fname)
1087 char lb[MAX_PATTERN_LEN];
1089 if (!(f = fopen (fname, "r")))
1091 fprintf (stderr, "cannot open peep rule file\n");
1095 while ((ch = fgetc (f)) != EOF)
1099 /* if we maxed out our local buffer */
1100 if (nch >= (MAX_PATTERN_LEN - 2))
1103 /* copy it into allocated buffer */
1106 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1111 rs = Safe_alloc ( strlen (lb) + 1);
1118 /* if some charaters left over */
1122 /* copy it into allocated buffer */
1125 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1130 rs = Safe_alloc ( strlen (lb) + 1);
1137 /*-----------------------------------------------------------------*/
1138 /* initPeepHole - initialises the peep hole optimizer stuff */
1139 /*-----------------------------------------------------------------*/
1145 /* read in the default rules */
1146 readRules (port->peep.default_rules);
1148 /* if we have any additional file read it too */
1149 if (options.peep_file)
1151 readRules (s = readFileIntoBuffer (options.peep_file));
1152 setToNull ((void **) &s);
1156 #if !OPT_DISABLE_PIC
1157 /* Convert the peep rules into pcode.
1158 NOTE: this is only support in the PIC port (at the moment)
1160 if (TARGET_IS_PIC) {
1161 peepRules2pCode(rootRules);