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 */
610 vvx = traceAlloc (&_G.values, Safe_alloc(strlen (vval) + 1));
613 hTabAddItem (vtab, key, vvx);
616 /*-----------------------------------------------------------------*/
617 /* matchLine - matches one line */
618 /*-----------------------------------------------------------------*/
620 matchLine (char *s, char *d, hTab ** vars)
629 /* skip white space in both */
635 /* if the destination is a var */
636 if (*d == '%' && isdigit (*(d + 1)))
638 char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
639 /* if the variable is already bound
640 then it MUST match with dest */
648 /* variable not bound we need to
650 bindVar (keyForVar (d + 1), &s, vars);
652 /* in either case go past the variable */
658 /* they should be an exact match other wise */
671 /* get rid of the trailing spaces
672 in both source & destination */
681 /* after all this if only one of them
682 has something left over then no match */
689 /*-----------------------------------------------------------------*/
690 /* matchRule - matches a all the rule lines */
691 /*-----------------------------------------------------------------*/
693 matchRule (lineNode * pl,
698 lineNode *spl; /* source pl */
699 lineNode *rpl; /* rule peep line */
701 /* setToNull((void **) &pr->vars); */
702 /* pr->vars = newHashTable(100); */
704 /* for all the lines defined in the rule */
710 /* if the source line starts with a ';' then
711 comment line don't process or the source line
712 contains == . debugger information skip it */
714 (*spl->line == ';' || spl->isDebug))
720 if (!matchLine (spl->line, rpl->line, &pr->vars))
731 /* if this rule has additional conditions */
734 if (callFuncByName (pr->cond, pr->vars, pl, head))
752 /*-----------------------------------------------------------------*/
753 /* replaceRule - does replacement of a matching pattern */
754 /*-----------------------------------------------------------------*/
756 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
759 lineNode *pl = NULL, *lhead = NULL;
760 /* a long function name and long variable name can evaluate to
761 4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
762 char lb[MAX_PATTERN_LEN*4];
764 lineNode *comment = NULL;
766 /* collect all the comment lines in the source */
767 for (cl = *shead; cl != stail; cl = cl->next)
769 if (cl->line && (*cl->line == ';' || cl->isDebug))
771 pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
772 (comment = newLineNode (cl->line)));
773 pl->isDebug = cl->isDebug;
778 /* for all the lines in the replacement pattern do */
779 for (pl = pr->replace; pl; pl = pl->next)
789 /* if the line contains a variable */
790 if (*l == '%' && isdigit (*(l + 1)))
792 v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
795 fprintf (stderr, "used unbound variable in replacement\n");
803 while (isdigit (*l)) {
813 cl = connectLine (cl, newLineNode (lb));
815 lhead = cl = newLineNode (lb);
818 /* add the comments if any to the head of list */
821 lineNode *lc = comment;
830 /* now we need to connect / replace the original chain */
831 /* if there is a prev then change it */
834 (*shead)->prev->next = lhead;
835 lhead->prev = (*shead)->prev;
839 /* now for the tail */
840 if (stail && stail->next)
842 stail->next->prev = cl;
844 cl->next = stail->next;
848 /* Returns TRUE if this line is a label definition.
850 * If so, start will point to the start of the label name,
851 * and len will be it's length.
854 isLabelDefinition (const char *line, const char **start, int *len)
856 const char *cp = line;
858 /* This line is a label if if consists of:
859 * [optional whitespace] followed by identifier chars
860 * (alnum | $ | _ ) followed by a colon.
863 while (*cp && isspace (*cp))
875 while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
880 if ((cp == *start) || (*cp != ':'))
885 *len = (cp - (*start));
889 /* Quick & dirty string hash function. */
891 hashSymbolName (const char *name)
897 hash = (hash << 6) ^ *name;
906 return hash % HTAB_SIZE;
909 /* Build a hash of all labels in the passed set of lines
910 * and how many times they are referenced.
913 buildLabelRefCountHash (lineNode * head)
920 assert (labelHash == NULL);
921 labelHash = newHashTable (HTAB_SIZE);
923 /* First pass: locate all the labels. */
928 if (isLabelDefinition (line->line, &label, &labelLen)
929 && labelLen <= SDCC_NAME_MAX)
931 labelHashEntry *entry;
933 entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
935 memcpy (entry->name, label, labelLen);
936 entry->name[labelLen] = 0;
937 entry->refCount = -1;
939 hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
945 /* Second pass: for each line, note all the referenced labels. */
946 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
950 for (i = 0; i < HTAB_SIZE; i++)
952 labelHashEntry *thisEntry;
954 thisEntry = hTabFirstItemWK (labelHash, i);
958 if (strstr (line->line, thisEntry->name))
960 thisEntry->refCount++;
962 thisEntry = hTabNextItemWK (labelHash);
969 /* Spew the contents of the table. Debugging fun only. */
970 for (i = 0; i < HTAB_SIZE; i++)
972 labelHashEntry *thisEntry;
974 thisEntry = hTabFirstItemWK (labelHash, i);
978 fprintf (stderr, "label: %s ref %d\n",
979 thisEntry->name, thisEntry->refCount);
980 thisEntry = hTabNextItemWK (labelHash);
986 /* How does this work?
997 Where is stuff allocated?
1001 /*-----------------------------------------------------------------*/
1002 /* peepHole - matches & substitutes rules */
1003 /*-----------------------------------------------------------------*/
1005 peepHole (lineNode ** pls)
1009 lineNode *mtail = NULL;
1012 assert(labelHash == NULL);
1019 for (pr = rootRules; pr; pr = pr->next)
1021 for (spl = *pls; spl; spl = spl->next)
1023 /* if inline assembler then no peep hole */
1029 /* Tidy up any data stored in the hTab */
1032 if (matchRule (spl, &mtail, pr, *pls))
1037 replaceRule (pls, mtail, pr);
1039 replaceRule (&spl, mtail, pr);
1041 /* if restart rule type then
1042 start at the top again */
1051 hTabDeleteAll (pr->vars);
1052 Safe_free (pr->vars);
1056 freeTrace (&_G.values);
1059 } while (restart == TRUE);
1063 hTabDeleteAll (labelHash);
1064 freeTrace (&_G.labels);
1070 /*-----------------------------------------------------------------*/
1071 /* readFileIntoBuffer - reads a file into a string buffer */
1072 /*-----------------------------------------------------------------*/
1074 readFileIntoBuffer (char *fname)
1080 char lb[MAX_PATTERN_LEN];
1082 if (!(f = fopen (fname, "r")))
1084 fprintf (stderr, "cannot open peep rule file\n");
1088 while ((ch = fgetc (f)) != EOF)
1092 /* if we maxed out our local buffer */
1093 if (nch >= (MAX_PATTERN_LEN - 2))
1096 /* copy it into allocated buffer */
1099 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1104 rs = Safe_alloc ( strlen (lb) + 1);
1111 /* if some charaters left over */
1115 /* copy it into allocated buffer */
1118 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1123 rs = Safe_alloc ( strlen (lb) + 1);
1130 /*-----------------------------------------------------------------*/
1131 /* initPeepHole - initialises the peep hole optimizer stuff */
1132 /*-----------------------------------------------------------------*/
1138 /* read in the default rules */
1139 readRules (port->peep.default_rules);
1141 /* if we have any additional file read it too */
1142 if (options.peep_file)
1144 readRules (s = readFileIntoBuffer (options.peep_file));
1145 setToNull ((void **) &s);
1149 #if !OPT_DISABLE_PIC
1150 /* Convert the peep rules into pcode.
1151 NOTE: this is only support in the PIC port (at the moment)
1153 if (TARGET_IS_PIC) {
1154 peepRules2pCode(rootRules);