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;
841 /* now for the tail */
842 if (stail && stail->next)
844 stail->next->prev = cl;
846 cl->next = stail->next;
850 /* Returns TRUE if this line is a label definition.
852 * If so, start will point to the start of the label name,
853 * and len will be it's length.
856 isLabelDefinition (const char *line, const char **start, int *len)
858 const char *cp = line;
860 /* This line is a label if if consists of:
861 * [optional whitespace] followed by identifier chars
862 * (alnum | $ | _ ) followed by a colon.
865 while (*cp && isspace (*cp))
877 while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
882 if ((cp == *start) || (*cp != ':'))
887 *len = (cp - (*start));
891 /* Quick & dirty string hash function. */
893 hashSymbolName (const char *name)
899 hash = (hash << 6) ^ *name;
908 return hash % HTAB_SIZE;
911 /* Build a hash of all labels in the passed set of lines
912 * and how many times they are referenced.
915 buildLabelRefCountHash (lineNode * head)
922 assert (labelHash == NULL);
923 labelHash = newHashTable (HTAB_SIZE);
925 /* First pass: locate all the labels. */
930 if (isLabelDefinition (line->line, &label, &labelLen)
931 && labelLen <= SDCC_NAME_MAX)
933 labelHashEntry *entry;
935 entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
937 memcpy (entry->name, label, labelLen);
938 entry->name[labelLen] = 0;
939 entry->refCount = -1;
941 hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
947 /* Second pass: for each line, note all the referenced labels. */
948 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
952 for (i = 0; i < HTAB_SIZE; i++)
954 labelHashEntry *thisEntry;
956 thisEntry = hTabFirstItemWK (labelHash, i);
960 if (strstr (line->line, thisEntry->name))
962 thisEntry->refCount++;
964 thisEntry = hTabNextItemWK (labelHash);
971 /* Spew the contents of the table. Debugging fun only. */
972 for (i = 0; i < HTAB_SIZE; i++)
974 labelHashEntry *thisEntry;
976 thisEntry = hTabFirstItemWK (labelHash, i);
980 fprintf (stderr, "label: %s ref %d\n",
981 thisEntry->name, thisEntry->refCount);
982 thisEntry = hTabNextItemWK (labelHash);
988 /* How does this work?
999 Where is stuff allocated?
1003 /*-----------------------------------------------------------------*/
1004 /* peepHole - matches & substitutes rules */
1005 /*-----------------------------------------------------------------*/
1007 peepHole (lineNode ** pls)
1011 lineNode *mtail = NULL;
1014 assert(labelHash == NULL);
1021 for (pr = rootRules; pr; pr = pr->next)
1023 for (spl = *pls; spl; spl = spl->next)
1025 /* if inline assembler then no peep hole */
1031 /* Tidy up any data stored in the hTab */
1034 if (matchRule (spl, &mtail, pr, *pls))
1039 replaceRule (pls, mtail, pr);
1041 replaceRule (&spl, mtail, pr);
1043 /* if restart rule type then
1044 start at the top again */
1053 hTabDeleteAll (pr->vars);
1054 Safe_free (pr->vars);
1058 freeTrace (&_G.values);
1061 } while (restart == TRUE);
1065 hTabDeleteAll (labelHash);
1066 freeTrace (&_G.labels);
1072 /*-----------------------------------------------------------------*/
1073 /* readFileIntoBuffer - reads a file into a string buffer */
1074 /*-----------------------------------------------------------------*/
1076 readFileIntoBuffer (char *fname)
1082 char lb[MAX_PATTERN_LEN];
1084 if (!(f = fopen (fname, "r")))
1086 fprintf (stderr, "cannot open peep rule file\n");
1090 while ((ch = fgetc (f)) != EOF)
1094 /* if we maxed out our local buffer */
1095 if (nch >= (MAX_PATTERN_LEN - 2))
1098 /* copy it into allocated buffer */
1101 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1106 rs = Safe_alloc ( strlen (lb) + 1);
1113 /* if some charaters left over */
1117 /* copy it into allocated buffer */
1120 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1125 rs = Safe_alloc ( strlen (lb) + 1);
1132 /*-----------------------------------------------------------------*/
1133 /* initPeepHole - initialises the peep hole optimizer stuff */
1134 /*-----------------------------------------------------------------*/
1140 /* read in the default rules */
1141 readRules (port->peep.default_rules);
1143 /* if we have any additional file read it too */
1144 if (options.peep_file)
1146 readRules (s = readFileIntoBuffer (options.peep_file));
1147 setToNull ((void **) &s);
1151 #if !OPT_DISABLE_PIC
1152 /* Convert the peep rules into pcode.
1153 NOTE: this is only support in the PIC port (at the moment)
1155 if (TARGET_IS_PIC) {
1156 peepRules2pCode(rootRules);