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 char lb[MAX_PATTERN_LEN];
714 lineNode *comment = NULL;
716 /* collect all the comment lines in the source */
717 for (cl = *shead; cl != stail; cl = cl->next)
719 if (cl->line && (*cl->line == ';' || cl->isDebug))
721 pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
722 (comment = newLineNode (cl->line)));
723 pl->isDebug = cl->isDebug;
728 /* for all the lines in the replacement pattern do */
729 for (pl = pr->replace; pl; pl = pl->next)
738 /* if the line contains a variable */
739 if (*l == '%' && isdigit (*(l + 1)))
741 v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
744 fprintf (stderr, "used unbound variable in replacement\n");
760 cl = connectLine (cl, newLineNode (lb));
762 lhead = cl = newLineNode (lb);
765 /* add the comments if any to the head of list */
768 lineNode *lc = comment;
777 /* now we need to connect / replace the original chain */
778 /* if there is a prev then change it */
781 (*shead)->prev->next = lhead;
782 lhead->prev = (*shead)->prev;
786 /* now for the tail */
787 if (stail && stail->next)
789 stail->next->prev = cl;
791 cl->next = stail->next;
795 /* Returns TRUE if this line is a label definition.
797 * If so, start will point to the start of the label name,
798 * and len will be it's length.
801 isLabelDefinition (const char *line, const char **start, int *len)
803 const char *cp = line;
805 /* This line is a label if if consists of:
806 * [optional whitespace] followed by identifier chars
807 * (alnum | $ | _ ) followed by a colon.
810 while (*cp && isspace (*cp))
822 while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
827 if ((cp == *start) || (*cp != ':'))
832 *len = (cp - (*start));
836 /* Quick & dirty string hash function. */
838 hashSymbolName (const char *name)
844 hash = (hash << 6) ^ *name;
853 return hash % HTAB_SIZE;
856 /* Build a hash of all labels in the passed set of lines
857 * and how many times they are referenced.
860 buildLabelRefCountHash (lineNode * head)
867 assert (labelHash == NULL);
868 labelHash = newHashTable (HTAB_SIZE);
870 /* First pass: locate all the labels. */
875 if (isLabelDefinition (line->line, &label, &labelLen)
876 && labelLen <= SDCC_NAME_MAX)
878 labelHashEntry *entry;
880 entry = Safe_calloc (1, sizeof (labelHashEntry));
882 memcpy (entry->name, label, labelLen);
883 entry->name[labelLen] = 0;
884 entry->refCount = -1;
886 hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
892 /* Second pass: for each line, note all the referenced labels. */
893 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
897 for (i = 0; i < HTAB_SIZE; i++)
899 labelHashEntry *thisEntry;
901 thisEntry = hTabFirstItemWK (labelHash, i);
905 if (strstr (line->line, thisEntry->name))
907 thisEntry->refCount++;
909 thisEntry = hTabNextItemWK (labelHash);
916 /* Spew the contents of the table. Debugging fun only. */
917 for (i = 0; i < HTAB_SIZE; i++)
919 labelHashEntry *thisEntry;
921 thisEntry = hTabFirstItemWK (labelHash, i);
925 fprintf (stderr, "label: %s ref %d\n",
926 thisEntry->name, thisEntry->refCount);
927 thisEntry = hTabNextItemWK (labelHash);
933 /*-----------------------------------------------------------------*/
934 /* peepHole - matches & substitutes rules */
935 /*-----------------------------------------------------------------*/
937 peepHole (lineNode ** pls)
941 lineNode *mtail = NULL;
945 hTabDeleteAll (labelHash);
951 for (pr = rootRules; pr; pr = pr->next)
954 for (spl = *pls; spl; spl = spl->next)
957 /* if inline assembler then no peep hole */
964 if (matchRule (spl, &mtail, pr, *pls))
969 replaceRule (pls, mtail, pr);
971 replaceRule (&spl, mtail, pr);
973 /* if restart rule type then
974 start at the top again */
983 /*-----------------------------------------------------------------*/
984 /* readFileIntoBuffer - reads a file into a string buffer */
985 /*-----------------------------------------------------------------*/
987 readFileIntoBuffer (char *fname)
993 char lb[MAX_PATTERN_LEN];
995 if (!(f = fopen (fname, "r")))
997 fprintf (stderr, "cannot open peep rule file\n");
1001 while ((ch = fgetc (f)) != EOF)
1005 /* if we maxed out our local buffer */
1006 if (nch >= (MAX_PATTERN_LEN - 2))
1009 /* copy it into allocated buffer */
1012 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1017 rs = Safe_calloc (1, strlen (lb) + 1);
1024 /* if some charaters left over */
1028 /* copy it into allocated buffer */
1031 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1036 rs = Safe_calloc (1, strlen (lb) + 1);
1043 /*-----------------------------------------------------------------*/
1044 /* initPeepHole - initiaises the peep hole optimizer stuff */
1045 /*-----------------------------------------------------------------*/
1051 /* read in the default rules */
1052 readRules (port->peep.default_rules);
1054 /* if we have any additional file read it too */
1055 if (options.peep_file)
1057 readRules (s = readFileIntoBuffer (options.peep_file));
1058 setToNull ((void **) &s);