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 if (head->isInline && *head->line=='#') {
279 // comment out preprocessor directives in inline asm
282 fprintf (of, "\t%s\n", head->line);
288 /*-----------------------------------------------------------------*/
289 /* newPeepRule - creates a new peeprule and attach it to the root */
290 /*-----------------------------------------------------------------*/
292 newPeepRule (lineNode * match,
299 pr = Safe_calloc (1, sizeof (peepRule));
301 pr->replace = replace;
302 pr->restart = restart;
306 pr->cond = Safe_calloc (1, strlen (cond) + 1);
307 strcpy (pr->cond, cond);
312 pr->vars = newHashTable (100);
314 /* if root is empty */
316 rootRules = currRule = pr;
318 currRule = currRule->next = pr;
323 /*-----------------------------------------------------------------*/
324 /* newLineNode - creates a new peep line */
325 /*-----------------------------------------------------------------*/
327 newLineNode (char *line)
331 pl = Safe_calloc (1, sizeof (lineNode));
332 pl->line = Safe_calloc (1, strlen (line) + 1);
333 strcpy (pl->line, line);
337 /*-----------------------------------------------------------------*/
338 /* connectLine - connects two lines */
339 /*-----------------------------------------------------------------*/
341 connectLine (lineNode * pl1, lineNode * pl2)
345 fprintf (stderr, "trying to connect null line\n");
355 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
356 if (!*x) { fprintf(stderr,y); return ; } }
358 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ; \
359 if (!*x) { fprintf(stderr,z); return ; } }
360 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ; \
361 if (!*x) { fprintf(stderr,z); return ; } }
363 /*-----------------------------------------------------------------*/
364 /* getPeepLine - parses the peep lines */
365 /*-----------------------------------------------------------------*/
367 getPeepLine (lineNode ** head, char **bpp)
369 char lines[MAX_PATTERN_LEN];
372 lineNode *currL = NULL;
379 fprintf (stderr, "unexpected end of match pattern\n");
386 while (isspace (*bp) ||
397 /* read till end of line */
399 while ((*bp != '\n' && *bp != '}') && *bp)
404 *head = currL = newLineNode (lines);
406 currL = connectLine (currL, newLineNode (lines));
412 /*-----------------------------------------------------------------*/
413 /* readRules - reads the rules from a string buffer */
414 /*-----------------------------------------------------------------*/
419 char lines[MAX_PATTERN_LEN];
423 lineNode *currL = NULL;
429 /* look for the token "replace" that is the
431 while (*bp && strncmp (bp, "replace", 7))
438 /* then look for either "restart" or '{' */
439 while (strncmp (bp, "restart", 7) &&
446 fprintf (stderr, "expected 'restart' or '{'\n");
454 { /* must be restart */
456 bp += strlen ("restart");
458 EXPECT_CHR (bp, '{', "expected '{'\n");
462 /* skip thru all the blank space */
463 SKIP_SPACE (bp, "unexpected end of rule\n");
465 match = replace = currL = NULL;
466 /* we are the start of a rule */
467 getPeepLine (&match, &bp);
469 /* now look for by */
470 EXPECT_STR (bp, "by", "expected 'by'\n");
472 /* then look for a '{' */
473 EXPECT_CHR (bp, '{', "expected '{'\n");
476 SKIP_SPACE (bp, "unexpected end of rule\n");
477 getPeepLine (&replace, &bp);
479 /* look for a 'if' */
480 while ((isspace (*bp) || *bp == '\n') && *bp)
483 if (strncmp (bp, "if", 2) == 0)
486 while ((isspace (*bp) || *bp == '\n') && *bp)
490 fprintf (stderr, "expected condition name\n");
494 /* look for the condition */
496 while (*bp && (*bp != '\n'))
502 newPeepRule (match, replace, lines, restart);
505 newPeepRule (match, replace, NULL, restart);
510 /*-----------------------------------------------------------------*/
511 /* keyForVar - returns the numeric key for a var */
512 /*-----------------------------------------------------------------*/
527 /*-----------------------------------------------------------------*/
528 /* bindVar - binds a value to a variable in the given hashtable */
529 /*-----------------------------------------------------------------*/
531 bindVar (int key, char **s, hTab ** vtab)
533 char vval[MAX_PATTERN_LEN];
537 /* first get the value of the variable */
539 /* the value is ended by a ',' or space or newline or null or ) */
548 /* if we find a '(' then we need to balance it */
567 vvx = Safe_calloc (1, strlen (vval) + 1);
569 hTabAddItem (vtab, key, vvx);
573 /*-----------------------------------------------------------------*/
574 /* matchLine - matches one line */
575 /*-----------------------------------------------------------------*/
577 matchLine (char *s, char *d, hTab ** vars)
586 /* skip white space in both */
592 /* if the destination is a var */
593 if (*d == '%' && isdigit (*(d + 1)))
595 char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
596 /* if the variable is already bound
597 then it MUST match with dest */
605 /* variable not bound we need to
607 bindVar (keyForVar (d + 1), &s, vars);
609 /* in either case go past the variable */
615 /* they should be an exact match other wise */
628 /* get rid of the trailing spaces
629 in both source & destination */
638 /* after all this if only one of them
639 has something left over then no match */
646 /*-----------------------------------------------------------------*/
647 /* matchRule - matches a all the rule lines */
648 /*-----------------------------------------------------------------*/
650 matchRule (lineNode * pl,
655 lineNode *spl; /* source pl */
656 lineNode *rpl; /* rule peep line */
658 hTabClearAll (pr->vars);
659 /* setToNull((void **) &pr->vars); */
660 /* pr->vars = newHashTable(100); */
662 /* for all the lines defined in the rule */
668 /* if the source line starts with a ';' then
669 comment line don't process or the source line
670 contains == . debugger information skip it */
672 (*spl->line == ';' || spl->isDebug))
678 if (!matchLine (spl->line, rpl->line, &pr->vars))
689 /* if this rule has additional conditions */
692 if (callFuncByName (pr->cond, pr->vars, pl, head))
710 /*-----------------------------------------------------------------*/
711 /* replaceRule - does replacement of a matching pattern */
712 /*-----------------------------------------------------------------*/
714 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
717 lineNode *pl = NULL, *lhead = NULL;
718 /* a long function name and long variable name can evaluate to
719 4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
720 char lb[MAX_PATTERN_LEN*4];
722 lineNode *comment = NULL;
724 /* collect all the comment lines in the source */
725 for (cl = *shead; cl != stail; cl = cl->next)
727 if (cl->line && (*cl->line == ';' || cl->isDebug))
729 pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
730 (comment = newLineNode (cl->line)));
731 pl->isDebug = cl->isDebug;
736 /* for all the lines in the replacement pattern do */
737 for (pl = pr->replace; pl; pl = pl->next)
746 /* if the line contains a variable */
747 if (*l == '%' && isdigit (*(l + 1)))
749 v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
752 fprintf (stderr, "used unbound variable in replacement\n");
760 while (isdigit (*l)) {
770 cl = connectLine (cl, newLineNode (lb));
772 lhead = cl = newLineNode (lb);
775 /* add the comments if any to the head of list */
778 lineNode *lc = comment;
787 /* now we need to connect / replace the original chain */
788 /* if there is a prev then change it */
791 (*shead)->prev->next = lhead;
792 lhead->prev = (*shead)->prev;
796 /* now for the tail */
797 if (stail && stail->next)
799 stail->next->prev = cl;
801 cl->next = stail->next;
805 /* Returns TRUE if this line is a label definition.
807 * If so, start will point to the start of the label name,
808 * and len will be it's length.
811 isLabelDefinition (const char *line, const char **start, int *len)
813 const char *cp = line;
815 /* This line is a label if if consists of:
816 * [optional whitespace] followed by identifier chars
817 * (alnum | $ | _ ) followed by a colon.
820 while (*cp && isspace (*cp))
832 while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
837 if ((cp == *start) || (*cp != ':'))
842 *len = (cp - (*start));
846 /* Quick & dirty string hash function. */
848 hashSymbolName (const char *name)
854 hash = (hash << 6) ^ *name;
863 return hash % HTAB_SIZE;
866 /* Build a hash of all labels in the passed set of lines
867 * and how many times they are referenced.
870 buildLabelRefCountHash (lineNode * head)
877 assert (labelHash == NULL);
878 labelHash = newHashTable (HTAB_SIZE);
880 /* First pass: locate all the labels. */
885 if (isLabelDefinition (line->line, &label, &labelLen)
886 && labelLen <= SDCC_NAME_MAX)
888 labelHashEntry *entry;
890 entry = Safe_calloc (1, sizeof (labelHashEntry));
892 memcpy (entry->name, label, labelLen);
893 entry->name[labelLen] = 0;
894 entry->refCount = -1;
896 hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
902 /* Second pass: for each line, note all the referenced labels. */
903 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
907 for (i = 0; i < HTAB_SIZE; i++)
909 labelHashEntry *thisEntry;
911 thisEntry = hTabFirstItemWK (labelHash, i);
915 if (strstr (line->line, thisEntry->name))
917 thisEntry->refCount++;
919 thisEntry = hTabNextItemWK (labelHash);
926 /* Spew the contents of the table. Debugging fun only. */
927 for (i = 0; i < HTAB_SIZE; i++)
929 labelHashEntry *thisEntry;
931 thisEntry = hTabFirstItemWK (labelHash, i);
935 fprintf (stderr, "label: %s ref %d\n",
936 thisEntry->name, thisEntry->refCount);
937 thisEntry = hTabNextItemWK (labelHash);
943 /*-----------------------------------------------------------------*/
944 /* peepHole - matches & substitutes rules */
945 /*-----------------------------------------------------------------*/
947 peepHole (lineNode ** pls)
951 lineNode *mtail = NULL;
955 hTabDeleteAll (labelHash);
961 for (pr = rootRules; pr; pr = pr->next)
964 for (spl = *pls; spl; spl = spl->next)
966 /* if inline assembler then no peep hole */
973 if (matchRule (spl, &mtail, pr, *pls))
978 replaceRule (pls, mtail, pr);
980 replaceRule (&spl, mtail, pr);
982 /* if restart rule type then
983 start at the top again */
992 /*-----------------------------------------------------------------*/
993 /* readFileIntoBuffer - reads a file into a string buffer */
994 /*-----------------------------------------------------------------*/
996 readFileIntoBuffer (char *fname)
1002 char lb[MAX_PATTERN_LEN];
1004 if (!(f = fopen (fname, "r")))
1006 fprintf (stderr, "cannot open peep rule file\n");
1010 while ((ch = fgetc (f)) != EOF)
1014 /* if we maxed out our local buffer */
1015 if (nch >= (MAX_PATTERN_LEN - 2))
1018 /* copy it into allocated buffer */
1021 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1026 rs = Safe_calloc (1, strlen (lb) + 1);
1033 /* if some charaters left over */
1037 /* copy it into allocated buffer */
1040 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1045 rs = Safe_calloc (1, strlen (lb) + 1);
1052 /*-----------------------------------------------------------------*/
1053 /* initPeepHole - initiaises the peep hole optimizer stuff */
1054 /*-----------------------------------------------------------------*/
1060 /* read in the default rules */
1061 readRules (port->peep.default_rules);
1063 /* if we have any additional file read it too */
1064 if (options.peep_file)
1066 readRules (s = readFileIntoBuffer (options.peep_file));
1067 setToNull ((void **) &s);