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 /* flat24bitMode - will check to see if we are in flat24 mode */
94 /*-----------------------------------------------------------------*/
95 FBYNAME (flat24bitMode)
97 return (options.model == MODEL_FLAT24);
100 /*-----------------------------------------------------------------*/
101 /* labelInRange - will check to see if label %5 is within range */
102 /*-----------------------------------------------------------------*/
103 FBYNAME (labelInRange)
105 /* assumes that %5 pattern variable has the label name */
106 char *lbl = hTabItemWithKey (vars, 5);
112 /* if the previous two instructions are "ljmp"s then don't
113 do it since it can be part of a jump table */
114 if (currPl->prev && currPl->prev->prev &&
115 strstr (currPl->prev->line, "ljmp") &&
116 strstr (currPl->prev->prev->line, "ljmp"))
119 /* calculate the label distance : the jump for reladdr can be
120 +/- 127 bytes, here Iam assuming that an average 8051
121 instruction is 2 bytes long, so if the label is more than
122 63 intructions away, the label is considered out of range
123 for a relative jump. we could get more precise this will
124 suffice for now since it catches > 90% cases */
125 dist = (pcDistance (currPl, lbl, TRUE) +
126 pcDistance (currPl, lbl, FALSE));
128 /* if (!dist || dist > 45) has produced wrong sjmp */
129 /* 07-Sep-2000 Michael Schmitt */
130 /* FIX for Peephole 132 */
131 /* switch with lots of case can lead to a sjmp with a distance */
132 /* out of the range for sjmp */
133 if (!dist || dist > 43)
139 /*-----------------------------------------------------------------*/
140 /* operandsNotSame - check if %1 & %2 are the same */
141 /*-----------------------------------------------------------------*/
142 FBYNAME (operandsNotSame)
144 char *op1 = hTabItemWithKey (vars, 1);
145 char *op2 = hTabItemWithKey (vars, 2);
147 if (strcmp (op1, op2) == 0)
155 * takes two parameters: a variable (bound to a label name)
156 * and an expected reference count.
158 * Returns TRUE if that label is defined and referenced exactly
159 * the given number of times.
161 FBYNAME (labelRefCount)
163 int varNumber, expectedRefCount;
166 /* If we don't have the label hash table yet, build it. */
169 buildLabelRefCountHash (head);
172 if (sscanf (cmdLine, "%*[ \t%]%d %d", &varNumber, &expectedRefCount) == 2)
174 char *label = hTabItemWithKey (vars, varNumber);
178 labelHashEntry *entry;
180 entry = hTabFirstItemWK (labelHash, hashSymbolName (label));
184 if (!strcmp (label, entry->name))
188 entry = hTabNextItemWK (labelHash);
194 fprintf (stderr, "labelRefCount: %s has refCount %d, want %d\n",
195 label, entry->refCount, expectedRefCount);
198 rc = (expectedRefCount == entry->refCount);
202 fprintf (stderr, "*** internal error: no label has entry for"
203 " %s in labelRefCount peephole.\n",
209 fprintf (stderr, "*** internal error: var %d not bound"
210 " in peephole labelRefCount rule.\n",
218 "*** internal error: labelRefCount peephole restriction"
219 " malformed: %s\n", cmdLine);
224 /*-----------------------------------------------------------------*/
225 /* callFuncByName - calls a function as defined in the table */
226 /*-----------------------------------------------------------------*/
228 callFuncByName (char *fname,
236 int (*func) (hTab *, lineNode *, lineNode *, const char *);
241 "labelInRange", labelInRange
245 "operandsNotSame", operandsNotSame
249 "24bitMode", flat24bitMode
253 "labelRefCount", labelRefCount
259 for (i = 0; i < ((sizeof (ftab)) / (sizeof (struct ftab))); i++)
260 if (strncmp (ftab[i].fname, fname, strlen (ftab[i].fname)) == 0)
262 return (*ftab[i].func) (vars, currPl, head,
263 fname + strlen (ftab[i].fname));
265 fprintf (stderr, "could not find named function in function table\n");
269 /*-----------------------------------------------------------------*/
270 /* printLine - prints a line chain into a given file */
271 /*-----------------------------------------------------------------*/
273 printLine (lineNode * head, FILE * of)
280 /* don't indent comments & labels */
282 (*head->line == ';' ||
283 head->line[strlen (head->line) - 1] == ':')) {
284 fprintf (of, "%s\n", head->line);
286 if (head->isInline && *head->line=='#') {
287 // comment out preprocessor directives in inline asm
290 fprintf (of, "\t%s\n", head->line);
296 /*-----------------------------------------------------------------*/
297 /* newPeepRule - creates a new peeprule and attach it to the root */
298 /*-----------------------------------------------------------------*/
300 newPeepRule (lineNode * match,
307 pr = Safe_alloc ( sizeof (peepRule));
309 pr->replace = replace;
310 pr->restart = restart;
314 pr->cond = Safe_alloc ( strlen (cond) + 1);
315 strcpy (pr->cond, cond);
320 pr->vars = newHashTable (100);
322 /* if root is empty */
324 rootRules = currRule = pr;
326 currRule = currRule->next = pr;
331 /*-----------------------------------------------------------------*/
332 /* newLineNode - creates a new peep line */
333 /*-----------------------------------------------------------------*/
335 newLineNode (char *line)
339 pl = Safe_alloc ( sizeof (lineNode));
340 pl->line = Safe_alloc ( strlen (line) + 1);
341 strcpy (pl->line, line);
345 /*-----------------------------------------------------------------*/
346 /* connectLine - connects two lines */
347 /*-----------------------------------------------------------------*/
349 connectLine (lineNode * pl1, lineNode * pl2)
353 fprintf (stderr, "trying to connect null line\n");
363 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
364 if (!*x) { fprintf(stderr,y); return ; } }
366 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ; \
367 if (!*x) { fprintf(stderr,z); return ; } }
368 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ; \
369 if (!*x) { fprintf(stderr,z); return ; } }
371 /*-----------------------------------------------------------------*/
372 /* getPeepLine - parses the peep lines */
373 /*-----------------------------------------------------------------*/
375 getPeepLine (lineNode ** head, char **bpp)
377 char lines[MAX_PATTERN_LEN];
380 lineNode *currL = NULL;
387 fprintf (stderr, "unexpected end of match pattern\n");
394 while (isspace (*bp) ||
405 /* read till end of line */
407 while ((*bp != '\n' && *bp != '}') && *bp)
412 *head = currL = newLineNode (lines);
414 currL = connectLine (currL, newLineNode (lines));
420 /*-----------------------------------------------------------------*/
421 /* readRules - reads the rules from a string buffer */
422 /*-----------------------------------------------------------------*/
427 char lines[MAX_PATTERN_LEN];
431 lineNode *currL = NULL;
437 /* look for the token "replace" that is the
439 while (*bp && strncmp (bp, "replace", 7))
446 /* then look for either "restart" or '{' */
447 while (strncmp (bp, "restart", 7) &&
454 fprintf (stderr, "expected 'restart' or '{'\n");
462 { /* must be restart */
464 bp += strlen ("restart");
466 EXPECT_CHR (bp, '{', "expected '{'\n");
470 /* skip thru all the blank space */
471 SKIP_SPACE (bp, "unexpected end of rule\n");
473 match = replace = currL = NULL;
474 /* we are the start of a rule */
475 getPeepLine (&match, &bp);
477 /* now look for by */
478 EXPECT_STR (bp, "by", "expected 'by'\n");
480 /* then look for a '{' */
481 EXPECT_CHR (bp, '{', "expected '{'\n");
484 SKIP_SPACE (bp, "unexpected end of rule\n");
485 getPeepLine (&replace, &bp);
487 /* look for a 'if' */
488 while ((isspace (*bp) || *bp == '\n') && *bp)
491 if (strncmp (bp, "if", 2) == 0)
494 while ((isspace (*bp) || *bp == '\n') && *bp)
498 fprintf (stderr, "expected condition name\n");
502 /* look for the condition */
504 while (*bp && (*bp != '\n'))
510 newPeepRule (match, replace, lines, restart);
513 newPeepRule (match, replace, NULL, restart);
518 /*-----------------------------------------------------------------*/
519 /* keyForVar - returns the numeric key for a var */
520 /*-----------------------------------------------------------------*/
535 /*-----------------------------------------------------------------*/
536 /* bindVar - binds a value to a variable in the given hashtable */
537 /*-----------------------------------------------------------------*/
539 bindVar (int key, char **s, hTab ** vtab)
541 char vval[MAX_PATTERN_LEN];
545 /* first get the value of the variable */
547 /* the value is ended by a ',' or space or newline or null or ) */
556 /* if we find a '(' then we need to balance it */
575 vvx = traceAlloc (&_G.values, Safe_alloc(strlen (vval) + 1));
578 hTabAddItem (vtab, key, vvx);
581 /*-----------------------------------------------------------------*/
582 /* matchLine - matches one line */
583 /*-----------------------------------------------------------------*/
585 matchLine (char *s, char *d, hTab ** vars)
594 /* skip white space in both */
600 /* if the destination is a var */
601 if (*d == '%' && isdigit (*(d + 1)))
603 char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
604 /* if the variable is already bound
605 then it MUST match with dest */
613 /* variable not bound we need to
615 bindVar (keyForVar (d + 1), &s, vars);
617 /* in either case go past the variable */
623 /* they should be an exact match other wise */
636 /* get rid of the trailing spaces
637 in both source & destination */
646 /* after all this if only one of them
647 has something left over then no match */
654 /*-----------------------------------------------------------------*/
655 /* matchRule - matches a all the rule lines */
656 /*-----------------------------------------------------------------*/
658 matchRule (lineNode * pl,
663 lineNode *spl; /* source pl */
664 lineNode *rpl; /* rule peep line */
666 /* setToNull((void **) &pr->vars); */
667 /* pr->vars = newHashTable(100); */
669 /* for all the lines defined in the rule */
675 /* if the source line starts with a ';' then
676 comment line don't process or the source line
677 contains == . debugger information skip it */
679 (*spl->line == ';' || spl->isDebug))
685 if (!matchLine (spl->line, rpl->line, &pr->vars))
696 /* if this rule has additional conditions */
699 if (callFuncByName (pr->cond, pr->vars, pl, head))
717 /*-----------------------------------------------------------------*/
718 /* replaceRule - does replacement of a matching pattern */
719 /*-----------------------------------------------------------------*/
721 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
724 lineNode *pl = NULL, *lhead = NULL;
725 /* a long function name and long variable name can evaluate to
726 4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
727 char lb[MAX_PATTERN_LEN*4];
729 lineNode *comment = NULL;
731 /* collect all the comment lines in the source */
732 for (cl = *shead; cl != stail; cl = cl->next)
734 if (cl->line && (*cl->line == ';' || cl->isDebug))
736 pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
737 (comment = newLineNode (cl->line)));
738 pl->isDebug = cl->isDebug;
743 /* for all the lines in the replacement pattern do */
744 for (pl = pr->replace; pl; pl = pl->next)
754 /* if the line contains a variable */
755 if (*l == '%' && isdigit (*(l + 1)))
757 v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
760 fprintf (stderr, "used unbound variable in replacement\n");
768 while (isdigit (*l)) {
778 cl = connectLine (cl, newLineNode (lb));
780 lhead = cl = newLineNode (lb);
783 /* add the comments if any to the head of list */
786 lineNode *lc = comment;
795 /* now we need to connect / replace the original chain */
796 /* if there is a prev then change it */
799 (*shead)->prev->next = lhead;
800 lhead->prev = (*shead)->prev;
804 /* now for the tail */
805 if (stail && stail->next)
807 stail->next->prev = cl;
809 cl->next = stail->next;
813 /* Returns TRUE if this line is a label definition.
815 * If so, start will point to the start of the label name,
816 * and len will be it's length.
819 isLabelDefinition (const char *line, const char **start, int *len)
821 const char *cp = line;
823 /* This line is a label if if consists of:
824 * [optional whitespace] followed by identifier chars
825 * (alnum | $ | _ ) followed by a colon.
828 while (*cp && isspace (*cp))
840 while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
845 if ((cp == *start) || (*cp != ':'))
850 *len = (cp - (*start));
854 /* Quick & dirty string hash function. */
856 hashSymbolName (const char *name)
862 hash = (hash << 6) ^ *name;
871 return hash % HTAB_SIZE;
874 /* Build a hash of all labels in the passed set of lines
875 * and how many times they are referenced.
878 buildLabelRefCountHash (lineNode * head)
885 assert (labelHash == NULL);
886 labelHash = newHashTable (HTAB_SIZE);
888 /* First pass: locate all the labels. */
893 if (isLabelDefinition (line->line, &label, &labelLen)
894 && labelLen <= SDCC_NAME_MAX)
896 labelHashEntry *entry;
898 entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
900 memcpy (entry->name, label, labelLen);
901 entry->name[labelLen] = 0;
902 entry->refCount = -1;
904 hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
910 /* Second pass: for each line, note all the referenced labels. */
911 /* This is ugly, O(N^2) stuff. Optimizations welcome... */
915 for (i = 0; i < HTAB_SIZE; i++)
917 labelHashEntry *thisEntry;
919 thisEntry = hTabFirstItemWK (labelHash, i);
923 if (strstr (line->line, thisEntry->name))
925 thisEntry->refCount++;
927 thisEntry = hTabNextItemWK (labelHash);
934 /* Spew the contents of the table. Debugging fun only. */
935 for (i = 0; i < HTAB_SIZE; i++)
937 labelHashEntry *thisEntry;
939 thisEntry = hTabFirstItemWK (labelHash, i);
943 fprintf (stderr, "label: %s ref %d\n",
944 thisEntry->name, thisEntry->refCount);
945 thisEntry = hTabNextItemWK (labelHash);
951 /* How does this work?
962 Where is stuff allocated?
966 /*-----------------------------------------------------------------*/
967 /* peepHole - matches & substitutes rules */
968 /*-----------------------------------------------------------------*/
970 peepHole (lineNode ** pls)
974 lineNode *mtail = NULL;
977 assert(labelHash == NULL);
984 for (pr = rootRules; pr; pr = pr->next)
986 for (spl = *pls; spl; spl = spl->next)
988 /* if inline assembler then no peep hole */
994 /* Tidy up any data stored in the hTab */
997 if (matchRule (spl, &mtail, pr, *pls))
1002 replaceRule (pls, mtail, pr);
1004 replaceRule (&spl, mtail, pr);
1006 /* if restart rule type then
1007 start at the top again */
1016 hTabDeleteAll (pr->vars);
1017 Safe_free (pr->vars);
1021 freeTrace (&_G.values);
1024 } while (restart == TRUE);
1028 hTabDeleteAll (labelHash);
1029 freeTrace (&_G.labels);
1035 /*-----------------------------------------------------------------*/
1036 /* readFileIntoBuffer - reads a file into a string buffer */
1037 /*-----------------------------------------------------------------*/
1039 readFileIntoBuffer (char *fname)
1045 char lb[MAX_PATTERN_LEN];
1047 if (!(f = fopen (fname, "r")))
1049 fprintf (stderr, "cannot open peep rule file\n");
1053 while ((ch = fgetc (f)) != EOF)
1057 /* if we maxed out our local buffer */
1058 if (nch >= (MAX_PATTERN_LEN - 2))
1061 /* copy it into allocated buffer */
1064 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1069 rs = Safe_alloc ( strlen (lb) + 1);
1076 /* if some charaters left over */
1080 /* copy it into allocated buffer */
1083 rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1088 rs = Safe_alloc ( strlen (lb) + 1);
1095 /*-----------------------------------------------------------------*/
1096 /* initPeepHole - initialises the peep hole optimizer stuff */
1097 /*-----------------------------------------------------------------*/
1103 /* read in the default rules */
1104 readRules (port->peep.default_rules);
1106 /* if we have any additional file read it too */
1107 if (options.peep_file)
1109 readRules (s = readFileIntoBuffer (options.peep_file));
1110 setToNull ((void **) &s);
1114 #if !OPT_DISABLE_PIC
1115 /* Convert the peep rules into pcode.
1116 NOTE: this is only support in the PIC port (at the moment)
1118 if (TARGET_IS_PIC) {
1119 peepRules2pCode(rootRules);