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, \
51 /*-----------------------------------------------------------------*/
52 /* pcDistance - afinds a label back ward or forward */
53 /*-----------------------------------------------------------------*/
55 pcDistance (lineNode * cpos, char *lbl, bool back)
58 char buff[MAX_PATTERN_LEN];
61 sprintf (buff, "%s:", lbl);
67 pl->line[strlen (pl->line) - 1] != ':' &&
72 if (strncmp (pl->line, buff, strlen (buff)) == 0)
84 /*-----------------------------------------------------------------*/
85 /* flat24bitMode - will check to see if we are in flat24 mode */
86 /*-----------------------------------------------------------------*/
87 FBYNAME (flat24bitMode)
89 return (options.model == MODEL_FLAT24);
92 /*-----------------------------------------------------------------*/
93 /* labelInRange - will check to see if label %5 is within range */
94 /*-----------------------------------------------------------------*/
95 FBYNAME (labelInRange)
97 /* assumes that %5 pattern variable has the label name */
98 char *lbl = hTabItemWithKey (vars, 5);
104 /* if the previous teo instructions are "ljmp"s then don't
105 do it since it can be part of a jump table */
106 if (currPl->prev && currPl->prev->prev &&
107 strstr (currPl->prev->line, "ljmp") &&
108 strstr (currPl->prev->prev->line, "ljmp"))
111 /* calculate the label distance : the jump for reladdr can be
112 +/- 127 bytes, here Iam assuming that an average 8051
113 instruction is 2 bytes long, so if the label is more than
114 63 intructions away, the label is considered out of range
115 for a relative jump. we could get more precise this will
116 suffice for now since it catches > 90% cases */
117 dist = (pcDistance (currPl, lbl, TRUE) +
118 pcDistance (currPl, lbl, FALSE));
120 /* if (!dist || dist > 45) has produced wrong sjmp */
121 /* 07-Sep-2000 Michael Schmitt */
122 /* FIX for Peephole 132 */
123 /* switch with lots of case can lead to a sjmp with a distance */
124 /* out of the range for sjmp */
125 if (!dist || dist > 43)
131 /*-----------------------------------------------------------------*/
132 /* operandsNotSame - check if %1 & %2 are the same */
133 /*-----------------------------------------------------------------*/
134 FBYNAME (operandsNotSame)
136 char *op1 = hTabItemWithKey (vars, 1);
137 char *op2 = hTabItemWithKey (vars, 2);
139 if (strcmp (op1, op2) == 0)
147 * takes two parameters: a variable (bound to a label name)
148 * and an expected reference count.
150 * Returns TRUE if that label is defined and referenced exactly
151 * the given number of times.
153 FBYNAME (labelRefCount)
155 int varNumber, expectedRefCount;
158 /* If we don't have the label hash table yet, build it. */
161 buildLabelRefCountHash (head);
164 if (sscanf (cmdLine, "%*[ \t%]%d %d", &varNumber, &expectedRefCount) == 2)
166 char *label = hTabItemWithKey (vars, varNumber);
170 labelHashEntry *entry;
172 entry = hTabFirstItemWK (labelHash, hashSymbolName (label));
176 if (!strcmp (label, entry->name))
180 entry = hTabNextItemWK (labelHash);
186 fprintf (stderr, "labelRefCount: %s has refCount %d, want %d\n",
187 label, entry->refCount, expectedRefCount);
190 rc = (expectedRefCount == entry->refCount);
194 fprintf (stderr, "*** internal error: no label has entry for"
195 " %s in labelRefCount peephole.\n",
201 fprintf (stderr, "*** internal error: var %d not bound"
202 " in peephole labelRefCount rule.\n",
210 "*** internal error: labelRefCount peephole restriction"
211 " malformed: %s\n", cmdLine);
216 /*-----------------------------------------------------------------*/
217 /* callFuncByName - calls a function as defined in the table */
218 /*-----------------------------------------------------------------*/
220 callFuncByName (char *fname,
228 int (*func) (hTab *, lineNode *, lineNode *, const char *);
233 "labelInRange", labelInRange
237 "operandsNotSame", operandsNotSame
241 "24bitMode", flat24bitMode
245 "labelRefCount", labelRefCount
251 for (i = 0; i < ((sizeof (ftab)) / (sizeof (struct ftab))); i++)
252 if (strncmp (ftab[i].fname, fname, strlen (ftab[i].fname)) == 0)
254 return (*ftab[i].func) (vars, currPl, head,
255 fname + strlen (ftab[i].fname));
257 fprintf (stderr, "could not find named function in function table\n");
261 /*-----------------------------------------------------------------*/
262 /* printLine - prints a line chain into a given file */
263 /*-----------------------------------------------------------------*/
265 printLine (lineNode * head, FILE * of)
272 /* don't indent comments & labels */
274 (*head->line == ';' ||
275 head->line[strlen (head->line) - 1] == ':'))
276 fprintf (of, "%s\n", head->line);
278 fprintf (of, "\t%s\n", head->line);
283 /*-----------------------------------------------------------------*/
284 /* newPeepRule - creates a new peeprule and attach it to the root */
285 /*-----------------------------------------------------------------*/
287 newPeepRule (lineNode * match,
294 pr = Safe_calloc (1, sizeof (peepRule));
296 pr->replace = replace;
297 pr->restart = restart;
301 pr->cond = Safe_calloc (1, strlen (cond) + 1);
302 strcpy (pr->cond, cond);
307 pr->vars = newHashTable (100);
309 /* if root is empty */
311 rootRules = currRule = pr;
313 currRule = currRule->next = pr;
318 /*-----------------------------------------------------------------*/
319 /* newLineNode - creates a new peep line */
320 /*-----------------------------------------------------------------*/
322 newLineNode (char *line)
326 pl = Safe_calloc (1, sizeof (lineNode));
327 pl->line = Safe_calloc (1, strlen (line) + 1);
328 strcpy (pl->line, line);
332 /*-----------------------------------------------------------------*/
333 /* connectLine - connects two lines */
334 /*-----------------------------------------------------------------*/
336 connectLine (lineNode * pl1, lineNode * pl2)
340 fprintf (stderr, "trying to connect null line\n");
350 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
351 if (!*x) { fprintf(stderr,y); return ; } }
353 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ; \
354 if (!*x) { fprintf(stderr,z); return ; } }
355 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ; \
356 if (!*x) { fprintf(stderr,z); return ; } }
358 /*-----------------------------------------------------------------*/
359 /* getPeepLine - parses the peep lines */
360 /*-----------------------------------------------------------------*/
362 getPeepLine (lineNode ** head, char **bpp)
364 char lines[MAX_PATTERN_LEN];
367 lineNode *currL = NULL;
374 fprintf (stderr, "unexpected end of match pattern\n");
381 while (isspace (*bp) ||
392 /* read till end of line */
394 while ((*bp != '\n' && *bp != '}') && *bp)
399 *head = currL = newLineNode (lines);
401 currL = connectLine (currL, newLineNode (lines));
407 /*-----------------------------------------------------------------*/
408 /* readRules - reads the rules from a string buffer */
409 /*-----------------------------------------------------------------*/
414 char lines[MAX_PATTERN_LEN];
418 lineNode *currL = NULL;
424 /* look for the token "replace" that is the
426 while (*bp && strncmp (bp, "replace", 7))
433 /* then look for either "restart" or '{' */
434 while (strncmp (bp, "restart", 7) &&
441 fprintf (stderr, "expected 'restart' or '{'\n");
449 { /* must be restart */
451 bp += strlen ("restart");
453 EXPECT_CHR (bp, '{', "expected '{'\n");
457 /* skip thru all the blank space */
458 SKIP_SPACE (bp, "unexpected end of rule\n");
460 match = replace = currL = NULL;
461 /* we are the start of a rule */
462 getPeepLine (&match, &bp);
464 /* now look for by */
465 EXPECT_STR (bp, "by", "expected 'by'\n");
467 /* then look for a '{' */
468 EXPECT_CHR (bp, '{', "expected '{'\n");
471 SKIP_SPACE (bp, "unexpected end of rule\n");
472 getPeepLine (&replace, &bp);
474 /* look for a 'if' */
475 while ((isspace (*bp) || *bp == '\n') && *bp)
478 if (strncmp (bp, "if", 2) == 0)
481 while ((isspace (*bp) || *bp == '\n') && *bp)
485 fprintf (stderr, "expected condition name\n");
489 /* look for the condition */
491 while (*bp && (*bp != '\n'))
497 newPeepRule (match, replace, lines, restart);
500 newPeepRule (match, replace, NULL, restart);
505 /*-----------------------------------------------------------------*/
506 /* keyForVar - returns the numeric key for a var */
507 /*-----------------------------------------------------------------*/
522 /*-----------------------------------------------------------------*/
523 /* bindVar - binds a value to a variable in the given hashtable */
524 /*-----------------------------------------------------------------*/
526 bindVar (int key, char **s, hTab ** vtab)
528 char vval[MAX_PATTERN_LEN];
532 /* first get the value of the variable */
534 /* the value is ended by a ',' or space or newline or null */
542 /* if we find a '(' then we need to balance it */
561 vvx = Safe_calloc (1, strlen (vval) + 1);
563 hTabAddItem (vtab, key, vvx);
567 /*-----------------------------------------------------------------*/
568 /* matchLine - matches one line */
569 /*-----------------------------------------------------------------*/
571 matchLine (char *s, char *d, hTab ** vars)
580 /* skip white space in both */
586 /* if the destination is a var */
587 if (*d == '%' && isdigit (*(d + 1)))
589 char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
590 /* if the variable is already bound
591 then it MUST match with dest */
599 /* variable not bound we need to
601 bindVar (keyForVar (d + 1), &s, vars);
603 /* in either case go past the variable */
609 /* they should be an exact match other wise */
622 /* get rid of the trailing spaces
623 in both source & destination */
632 /* after all this if only one of them
633 has something left over then no match */
640 /*-----------------------------------------------------------------*/
641 /* matchRule - matches a all the rule lines */
642 /*-----------------------------------------------------------------*/
644 matchRule (lineNode * pl,
649 lineNode *spl; /* source pl */
650 lineNode *rpl; /* rule peep line */
652 hTabClearAll (pr->vars);
653 /* setToNull((void **) &pr->vars); */
654 /* pr->vars = newHashTable(100); */
656 /* for all the lines defined in the rule */
662 /* if the source line starts with a ';' then
663 comment line don't process or the source line
664 contains == . debugger information skip it */
666 (*spl->line == ';' || spl->isDebug))
672 if (!matchLine (spl->line, rpl->line, &pr->vars))
683 /* if this rule has additional conditions */
686 if (callFuncByName (pr->cond, pr->vars, pl, head))
704 /*-----------------------------------------------------------------*/
705 /* replaceRule - does replacement of a matching pattern */
706 /*-----------------------------------------------------------------*/
708 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
711 lineNode *pl = NULL, *lhead = NULL;
712 /* a long function name and long variable name can evaluate to
713 4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
714 char lb[MAX_PATTERN_LEN*4];
716 lineNode *comment = NULL;
718 /* collect all the comment lines in the source */
719 for (cl = *shead; cl != stail; cl = cl->next)
721 if (cl->line && (*cl->line == ';' || cl->isDebug))
723 pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
724 (comment = newLineNode (cl->line)));
725 pl->isDebug = cl->isDebug;
730 /* for all the lines in the replacement pattern do */
731 for (pl = pr->replace; pl; pl = pl->next)
740 /* if the line contains a variable */
741 if (*l == '%' && isdigit (*(l + 1)))
743 v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
746 fprintf (stderr, "used unbound variable in replacement\n");
754 while (isdigit (*l)) {
764 cl = connectLine (cl, newLineNode (lb));
766 lhead = cl = newLineNode (lb);
769 /* add the comments if any to the head of list */
772 lineNode *lc = comment;
781 /* now we need to connect / replace the original chain */
782 /* if there is a prev then change it */
785 (*shead)->prev->next = lhead;
786 lhead->prev = (*shead)->prev;
790 /* now for the tail */
791 if (stail && stail->next)
793 stail->next->prev = cl;
795 cl->next = stail->next;
799 /* Returns TRUE if this line is a label definition.
801 * If so, start will point to the start of the label name,
802 * and len will be it's length.
805 isLabelDefinition (const char *line, const char **start, int *len)
807 const char *cp = line;
809 /* This line is a label if if consists of:
810 * [optional whitespace] followed by identifier chars
811 * (alnum | $ | _ ) followed by a colon.
814 while (*cp && isspace (*cp))
826 while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
831 if ((cp == *start) || (*cp != ':'))
836 *len = (cp - (*start));
840 /* Quick & dirty string hash function. */
842 hashSymbolName (const char *name)
848 hash = (hash << 6) ^ *name;
857 return hash % HTAB_SIZE;
860 /* Build a hash of all labels in the passed set of lines
861 * and how many times they are referenced.
864 buildLabelRefCountHash (lineNode * head)
871 assert (labelHash == NULL);
872 labelHash = newHashTable (HTAB_SIZE);
874 /* First pass: locate all the labels. */
879 if (isLabelDefinition (line->line, &label, &labelLen)
880 && labelLen <= SDCC_NAME_MAX)
882 labelHashEntry *entry;
884 entry = Safe_calloc (1, sizeof (labelHashEntry));
886 memcpy (entry->name, label, labelLen);
887 entry->name[labelLen] = 0;
888 entry->refCount = -1;
890 hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
896 /* Second pass: for each line, note all the referenced labels. */
897 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
901 for (i = 0; i < HTAB_SIZE; i++)
903 labelHashEntry *thisEntry;
905 thisEntry = hTabFirstItemWK (labelHash, i);
909 if (strstr (line->line, thisEntry->name))
911 thisEntry->refCount++;
913 thisEntry = hTabNextItemWK (labelHash);
920 /* Spew the contents of the table. Debugging fun only. */
921 for (i = 0; i < HTAB_SIZE; i++)
923 labelHashEntry *thisEntry;
925 thisEntry = hTabFirstItemWK (labelHash, i);
929 fprintf (stderr, "label: %s ref %d\n",
930 thisEntry->name, thisEntry->refCount);
931 thisEntry = hTabNextItemWK (labelHash);
937 /*-----------------------------------------------------------------*/
938 /* peepHole - matches & substitutes rules */
939 /*-----------------------------------------------------------------*/
941 peepHole (lineNode ** pls)
945 lineNode *mtail = NULL;
949 hTabDeleteAll (labelHash);
955 for (pr = rootRules; pr; pr = pr->next)
958 for (spl = *pls; spl; spl = spl->next)
960 /* if inline assembler then no peep hole */
967 if (matchRule (spl, &mtail, pr, *pls))
972 replaceRule (pls, mtail, pr);
974 replaceRule (&spl, mtail, pr);
976 /* if restart rule type then
977 start at the top again */
986 /*-----------------------------------------------------------------*/
987 /* readFileIntoBuffer - reads a file into a string buffer */
988 /*-----------------------------------------------------------------*/
990 readFileIntoBuffer (char *fname)
996 char lb[MAX_PATTERN_LEN];
998 if (!(f = fopen (fname, "r")))
1000 fprintf (stderr, "cannot open peep rule file\n");
1004 while ((ch = fgetc (f)) != EOF)
1008 /* if we maxed out our local buffer */
1009 if (nch >= (MAX_PATTERN_LEN - 2))
1012 /* copy it into allocated buffer */
1015 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1020 rs = Safe_calloc (1, strlen (lb) + 1);
1027 /* if some charaters left over */
1031 /* copy it into allocated buffer */
1034 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1039 rs = Safe_calloc (1, strlen (lb) + 1);
1046 /*-----------------------------------------------------------------*/
1047 /* initPeepHole - initiaises the peep hole optimizer stuff */
1048 /*-----------------------------------------------------------------*/
1054 /* read in the default rules */
1055 readRules (port->peep.default_rules);
1057 /* if we have any additional file read it too */
1058 if (options.peep_file)
1060 readRules (s = readFileIntoBuffer (options.peep_file));
1061 setToNull ((void **) &s);