* maintains the the lists of hashed patterns
* Functions : addtohashtable() and printhashtable()
*/
-
+
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "misc.h"
+#include "hash.h"
-struct hlist { /* linear list of pattern numbers */
- int h_patno;
- struct hlist *h_next;
+struct hlist
+{ /* linear list of pattern numbers */
+ int h_patno;
+ struct hlist *h_next;
};
-static struct hlist *hashtable[129]; /* an array of ptr's to these lists,
- * the index in the array is the
- * result of hashing
- */
+static struct hlist *hashtable[129]; /* an array of ptr's to these lists,
+ * the index in the array is the
+ * result of hashing
+ */
-static unsigned
-hash(string) char *string; {
+static unsigned hash(char* string)
+{
register char *p;
- register unsigned i,sum;
+ register unsigned i, sum;
- if (strcmp(string,"ANY") == 0) return 128;
- for (sum=i=0,p=string;*p;i += 3)
- sum += (*p++)<<(i&03);
+ if (strcmp(string, "ANY") == 0)
+ return 128;
+ for (sum = i = 0, p = string; *p; i += 3)
+ sum += (*p++) << (i & 03);
return sum % 128;
}
+void addtohashtable(char* s, int n)
+{
+ /*
+ * Add a new pattern number to the hashtable.
+ * s is the key, n the pattern number
+ */
+ unsigned hval;
+ register struct hlist *p;
-addtohashtable(s,n) char *s; {
- /*
- * Add a new pattern number to the hashtable.
- * s is the key, n the pattern number
- */
- unsigned hval;
- register struct hlist *p;
-
- hval = hash(s);
- p = (struct hlist *) malloc(sizeof *p);
- p->h_patno = n;
- /*
- * Now insert in front of the list
- * This way, the list will be sorted from high to low, which is the
- * wrong way around, but easy
- */
- p->h_next = hashtable[hval];
- hashtable[hval] = p;
+ hval = hash(s);
+ p = (struct hlist *) malloc(sizeof *p);
+ p->h_patno = n;
+ /*
+ * Now insert in front of the list
+ * This way, the list will be sorted from high to low, which is the
+ * wrong way around, but easy
+ */
+ p->h_next = hashtable[hval];
+ hashtable[hval] = p;
}
-static
-prhlist(p) struct hlist *p; {
- /*
- * Print a list in reversed order (see comment above)
- */
+static void prhlist(struct hlist *p)
+{
+ /*
+ * Print a list in reversed order (see comment above)
+ */
- if (p) {
- prhlist(p->h_next);
- fprintf(genc,"%d, ",p->h_patno - 1);
- }
+ if (p)
+ {
+ prhlist(p->h_next);
+ fprintf(genc, "%d, ", p->h_patno - 1);
+ }
}
-
-printhashtable() {
- /*
- * Print the linear lists, and also output an array of
- * pointers to them
- */
- register i;
- register struct hlist *p;
- for (i = 1; i <= 128; i++) {
- fprintf(genc,"int hash%d[] = { ",i);
- prhlist(hashtable[i-1]);
- fputs("-1};\n",genc);
- }
- fputs("int hashany[] = { ", genc);
- prhlist(hashtable[128]);
- fputs("-1 };\n",genc);
- fputs("int *hashtab[] = {\n",genc);
- for (i = 1; i <= 128; i++) fprintf(genc,"\thash%d,\n",i);
- fputs("\thashany\n};\n",genc);
+void printhashtable(void)
+{
+ /*
+ * Print the linear lists, and also output an array of
+ * pointers to them
+ */
+ register int i;
+
+ for (i = 1; i <= 128; i++)
+ {
+ fprintf(genc, "int hash%d[] = { ", i);
+ prhlist(hashtable[i - 1]);
+ fputs("-1};\n", genc);
+ }
+ fputs("int hashany[] = { ", genc);
+ prhlist(hashtable[128]);
+ fputs("-1 };\n", genc);
+ fputs("int *hashtab[] = {\n", genc);
+ for (i = 1; i <= 128; i++)
+ fprintf(genc, "\thash%d,\n", i);
+ fputs("\thashany\n};\n", genc);
}
-/* $Id$ */
-/*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
-/* t o p g e n . g
- *
- * Grammar of optimizer description, and some code generation
- */
-
-%token LETTER, DIGIT, OTHER, SPACE;
-%token LINE_TERMINATOR, OPERAND_SEPARATOR, INSTRUCTION_SEPARATOR,
- PATTERN_SEPARATOR, OPEN_BRACKET, CLOSE_BRACKET;
-%lexical LLlex;
-%start LLparse, optim_description;
-
-{
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-#include "token.h"
-#include "symtab.h"
-#include "misc.h"
-
-char idbuf[BUFSIZ], buf[BUFSIZ];
-int countid; /* # of variables */
-int countpat; /* # of patterns */
-static int patlen; /* Maximum number of instructions in pattern */
-static int maxoperand; /* Maximum number of operands of instruction */
-extern FILE *input; /* file descriptor of inputfile */
-}
-
-optim_description
- { struct symtab *p; } :
- SPACE* parameter_line*
- { p = findident("MAXOP",LOOKING,&deftable);
- if (p == 0) maxoperand = 2; /* default */
- else maxoperand = p->s_num;
- }
- separator SPACE* mode_definitions
- separator SPACE* patterns
- separator
- { register int c;
- fprintf(genc, linedir, lineno, inpfile);
- while ((c = getc(input)) != EOF) {
- putc(c,genc);
- }
- }
-;
-
-parameter_line
- { struct symtab *p;} :
- identifier
- { p = findident(idbuf,ENTERING,&deftable);}
- SPACE
- value
- { p->s_num = atoi(buf);}
- /* This action in fact only needed for MAXOP */
- LINE_TERMINATOR
- SPACE*
- { fprintf(genh,"#define %s %s\n",p->s_name,buf);}
-;
-
-value
- { char *p1 = buf;} :
- [
- [ OPEN_BRACKET
- | CLOSE_BRACKET
- | OPERAND_SEPARATOR
- | PATTERN_SEPARATOR
- | INSTRUCTION_SEPARATOR
- | SPACE
- | LETTER
- | DIGIT
- | OTHER
- | '%'
- ]
- { *p1++ = dot.t_attrib;}
- ]*
- { *p1 = '\0';}
-;
-
-mode_definitions
- { int lin; } :
- { fputs("tok_chk(varno) {\n\tint r;\n", genc);
- fputs("\tchar *VAL;\n\n",genc);
- fputs("\tVAL = var[varno].value;\n",genc);
- fputs("\tswitch(varno) {\n",genc);
- }
- [
- token_list
- constraint(&lin)
- { fprintf(genc,linedir,lin,inpfile);
- fprintf(genc,"\t\tr = (%s); break;\n",buf);
- }
- LINE_TERMINATOR
- SPACE*
- ]*
- { fputs("\tdefault :\n\t\tassert(0);\n",genc);
- fputs("\t}\n\treturn r;\n}\n\n",genc);
- }
-;
-
-token_list :
- new_identifier
- SPACE*
- [
- OPERAND_SEPARATOR
- SPACE*
- new_identifier
- SPACE*
- ]*
-;
-
-new_identifier
- { struct symtab *p;} :
- identifier
- { p = findident(idbuf,ENTERING,&idtable);
- p->s_num = ++countid;
- fprintf(genc,"\tcase %d:\n", countid);
- }
-;
-
-constraint (int *lin;)
- { char *p = buf; } :
- OPEN_BRACKET
- { *lin = lineno;}
- [
- [ LINE_TERMINATOR
- | OPERAND_SEPARATOR
- | PATTERN_SEPARATOR
- | INSTRUCTION_SEPARATOR
- | LETTER
- | DIGIT
- | SPACE
- | OTHER
- | '%'
- ]
- { *p++ = dot.t_attrib;}
- ]*
- { *p = '\0';
- if (onlyspace(buf)) strcpy(buf,"TRUE");
- }
- CLOSE_BRACKET
- SPACE*
-;
-
-patterns
- { int lin;
- char *constr;
- int np, nr;
- } :
-[
- { countpat++;
- constr = (char *) 0;
- fprintf(genc,"struct instr_descr pat%d[] = {\n",
- countpat);
- }
- instruction_list(&np)
- { if (np > patlen) patlen = np;
- fputs("\n};\n\n",genc);
- }
- [
- constraint(&lin)
- { /* Save the constraint, we need it later on */
- constr = malloc((unsigned)(strlen(buf)+1));
- strcpy(constr,buf);
- }
- ]?
- PATTERN_SEPARATOR
- { fprintf(genc,"struct instr_descr rep%d[] = {\n",
- countpat);
- }
- replacement(&nr)
- { fputs("\n};\n\n",genc);}
- LINE_TERMINATOR
- SPACE*
- { addpattern(constr,lin,np,nr);}
-]*
- { printhashtable();
- printpatterns();
- fprintf(genh,"#define NRVARS %d\n",countid);
- fprintf(genh,"#define NRPATTERNS %d\n",countpat);
- fprintf(genh,"#define MIN_WINDOW_SIZE %d\n",
- patlen+3);
- fclose(genh);
- }
-;
-
-instruction_list(int *n;) :
- instruction(1)
- { *n = 1;}
- [
- INSTRUCTION_SEPARATOR
- { fputs(",\n",genc);}
- SPACE*
- instruction(0)
- { *n += 1;}
- ]*
-;
-
-instruction(int opt;)
- { int count = 0;} :
- opcode(opt)
- { if (strcmp(buf,"ANY") != 0) {
- fprintf(genc,"\t{\"%s\", {",buf);
- }
- else fputs("\t{(char *) 0, {",genc);
- count = 0;
- }
- [
- operand(' ')
- { count = 1;}
- [
- OPERAND_SEPARATOR
- { count++;}
- SPACE*
- operand(',')
- ]*
- { if (count > maxoperand) {
- error("Too many operands");
- }
- }
- ]?
- { while (count++ < maxoperand) {
- fprintf(genc,"%c{\"\",-1,\"\"}",count == 1 ? ' ' : ',');
- }
- putc('}',genc);
- putc('}',genc);
- }
-;
-
-opcode(int opt;)
- { char *p = buf;} :
- [
- [ LETTER
- | DIGIT
- | OTHER
- ]
- { *p++ = dot.t_attrib;}
- ]+
- SPACE+
- { *p = '\0';
- if (opt) addtohashtable(buf,countpat);
- }
-;
-
-operand(int c;)
- { register struct symtab *p = 0;} :
- { fprintf(genc, "%c{\"", c);}
- [
- identifier
- { if (!p) {
- p = findident(idbuf,LOOKING,&idtable);
- if (p) fprintf(genc,"\",%d,\"",p->s_num);
- else fputs(idbuf,genc);
- }
- else fputs(idbuf,genc);
- }
- | DIGIT
- { putc(dot.t_attrib,genc);}
- | OTHER
- { putc(dot.t_attrib,genc);}
- ]+
- { if (p) fputs("\"}",genc);
- else fputs("\",0,\"\"}",genc);
- }
- SPACE*
-;
-
-replacement (int *n;)
- {register i;} :
- SPACE*
- { *n = 0;}
- [
- instruction(0)
- { *n = 1;}
- [
- INSTRUCTION_SEPARATOR
- { fputs(",\n", genc);}
- SPACE*
- instruction(0)
- { *n += 1;}
- ]*
- | /* empty replacement, but there must be a
- * structure initializer anyway
- */
- { fputs("\t{\"\", {",genc);
- for (i = 0; i < maxoperand; i++) {
- fprintf(genc, "%c{\"\",-1,\"\"}",i?',':' ');
- }
- fputs("}}",genc);
- }
- ]
-;
-
-
-identifier
- { char *p = idbuf; } :
- LETTER
- { *p++ = dot.t_attrib;}
- [ %while (1)
- LETTER { *p++ = dot.t_attrib;}
- | DIGIT { *p++ = dot.t_attrib;}
- ]*
- { *p = '\0';}
-;
-
-separator :
- '%' '%' SPACE* LINE_TERMINATOR
-;
+/* $Id$ */\r
+/*\r
+ * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.\r
+ * See the copyright notice in the ACK home directory, in the file "Copyright".\r
+ */\r
+/* t o p g e n . g\r
+ *\r
+ * Grammar of optimizer description, and some code generation\r
+ */\r
+\r
+%token LETTER, DIGIT, OTHER, SPACE;\r
+%token LINE_TERMINATOR, OPERAND_SEPARATOR, INSTRUCTION_SEPARATOR,\r
+ PATTERN_SEPARATOR, OPEN_BRACKET, CLOSE_BRACKET;\r
+%lexical LLlex;\r
+%start LLparse, optim_description;\r
+\r
+{\r
+#include <stdlib.h>\r
+#include <stdio.h>\r
+#include <string.h>\r
+#include "token.h"\r
+#include "symtab.h"\r
+#include "misc.h"\r
+#include "hash.h"\r
+#include "pattern.h"\r
+\r
+char idbuf[BUFSIZ], buf[BUFSIZ];\r
+int countid; /* # of variables */\r
+int countpat; /* # of patterns */\r
+static int patlen; /* Maximum number of instructions in pattern */\r
+static int maxoperand; /* Maximum number of operands of instruction */\r
+extern FILE *input; /* file descriptor of inputfile */\r
+\r
+\r
+\r
+extern int onlyspace(char* s);\r
+extern void error(char *s, char* s1);\r
+\r
+\r
+}\r
+\r
+optim_description\r
+ { struct symtab *p; } :\r
+ SPACE* parameter_line*\r
+ { p = findident("MAXOP",LOOKING,&deftable);\r
+ if (p == 0) maxoperand = 2; /* default */\r
+ else maxoperand = p->s_num;\r
+ }\r
+ separator SPACE* mode_definitions\r
+ separator SPACE* patterns \r
+ separator \r
+ { register int c;\r
+ fprintf(genc, linedir, lineno, inpfile);\r
+ while ((c = getc(input)) != EOF) {\r
+ putc(c,genc);\r
+ }\r
+ }\r
+;\r
+\r
+parameter_line\r
+ { struct symtab *p;} :\r
+ identifier\r
+ { p = findident(idbuf,ENTERING,&deftable);}\r
+ SPACE\r
+ value\r
+ { p->s_num = atoi(buf);}\r
+ /* This action in fact only needed for MAXOP */\r
+ LINE_TERMINATOR\r
+ SPACE*\r
+ { fprintf(genh,"#define %s %s\n",p->s_name,buf);}\r
+;\r
+\r
+value\r
+ { char *p1 = buf;} :\r
+ [\r
+ [ OPEN_BRACKET\r
+ | CLOSE_BRACKET\r
+ | OPERAND_SEPARATOR\r
+ | PATTERN_SEPARATOR\r
+ | INSTRUCTION_SEPARATOR\r
+ | SPACE\r
+ | LETTER\r
+ | DIGIT\r
+ | OTHER\r
+ | '%'\r
+ ]\r
+ { *p1++ = dot.t_attrib;}\r
+ ]*\r
+ { *p1 = '\0';}\r
+;\r
+\r
+mode_definitions\r
+ { int lin; } :\r
+ { fputs("tok_chk(varno) {\n\tint r;\n", genc);\r
+ fputs("\tchar *VAL;\n\n",genc);\r
+ fputs("\tVAL = var[varno].value;\n",genc);\r
+ fputs("\tswitch(varno) {\n",genc);\r
+ }\r
+ [\r
+ token_list\r
+ constraint(&lin)\r
+ { fprintf(genc,linedir,lin,inpfile);\r
+ fprintf(genc,"\t\tr = (%s); break;\n",buf);\r
+ }\r
+ LINE_TERMINATOR\r
+ SPACE*\r
+ ]*\r
+ { fputs("\tdefault :\n\t\tassert(0);\n",genc);\r
+ fputs("\t}\n\treturn r;\n}\n\n",genc);\r
+ }\r
+;\r
+\r
+token_list :\r
+ new_identifier\r
+ SPACE*\r
+ [\r
+ OPERAND_SEPARATOR\r
+ SPACE*\r
+ new_identifier\r
+ SPACE*\r
+ ]*\r
+;\r
+\r
+new_identifier\r
+ { struct symtab *p;} :\r
+ identifier\r
+ { p = findident(idbuf,ENTERING,&idtable);\r
+ p->s_num = ++countid;\r
+ fprintf(genc,"\tcase %d:\n", countid);\r
+ }\r
+;\r
+\r
+constraint (int *lin;)\r
+ { char *p = buf; } :\r
+ OPEN_BRACKET\r
+ { *lin = lineno;}\r
+ [\r
+ [ LINE_TERMINATOR\r
+ | OPERAND_SEPARATOR\r
+ | PATTERN_SEPARATOR\r
+ | INSTRUCTION_SEPARATOR\r
+ | LETTER\r
+ | DIGIT\r
+ | SPACE\r
+ | OTHER\r
+ | '%'\r
+ ]\r
+ { *p++ = dot.t_attrib;}\r
+ ]*\r
+ { *p = '\0';\r
+ if (onlyspace(buf)) strcpy(buf,"TRUE");\r
+ }\r
+ CLOSE_BRACKET\r
+ SPACE*\r
+;\r
+\r
+patterns\r
+ { int lin;\r
+ char *constr; \r
+ int np, nr;\r
+ } :\r
+[\r
+ { countpat++;\r
+ constr = (char *) 0;\r
+ fprintf(genc,"struct instr_descr pat%d[] = {\n",\r
+ countpat);\r
+ }\r
+ instruction_list(&np)\r
+ { if (np > patlen) patlen = np;\r
+ fputs("\n};\n\n",genc);\r
+ }\r
+ [\r
+ constraint(&lin)\r
+ { /* Save the constraint, we need it later on */\r
+ constr = malloc((unsigned)(strlen(buf)+1));\r
+ strcpy(constr,buf);\r
+ }\r
+ ]?\r
+ PATTERN_SEPARATOR\r
+ { fprintf(genc,"struct instr_descr rep%d[] = {\n",\r
+ countpat);\r
+ }\r
+ replacement(&nr)\r
+ { fputs("\n};\n\n",genc);}\r
+ LINE_TERMINATOR\r
+ SPACE*\r
+ { addpattern(constr,lin,np,nr);}\r
+]*\r
+ { printhashtable();\r
+ printpatterns();\r
+ fprintf(genh,"#define NRVARS %d\n",countid);\r
+ fprintf(genh,"#define NRPATTERNS %d\n",countpat);\r
+ fprintf(genh,"#define MIN_WINDOW_SIZE %d\n",\r
+ patlen+3);\r
+ fclose(genh);\r
+ }\r
+;\r
+\r
+instruction_list(int *n;) :\r
+ instruction(1)\r
+ { *n = 1;}\r
+ [\r
+ INSTRUCTION_SEPARATOR\r
+ { fputs(",\n",genc);}\r
+ SPACE*\r
+ instruction(0)\r
+ { *n += 1;}\r
+ ]*\r
+;\r
+\r
+instruction(int opt;)\r
+ { int count = 0;} :\r
+ opcode(opt)\r
+ { if (strcmp(buf,"ANY") != 0) {\r
+ fprintf(genc,"\t{\"%s\", {",buf);\r
+ }\r
+ else fputs("\t{(char *) 0, {",genc);\r
+ count = 0;\r
+ }\r
+ [\r
+ operand(' ')\r
+ { count = 1;}\r
+ [\r
+ OPERAND_SEPARATOR\r
+ { count++;}\r
+ SPACE*\r
+ operand(',')\r
+ ]*\r
+ { if (count > maxoperand) {\r
+ error("Too many operands","");\r
+ }\r
+ }\r
+ ]?\r
+ { while (count++ < maxoperand) {\r
+ fprintf(genc,"%c{\"\",-1,\"\"}",count == 1 ? ' ' : ',');\r
+ }\r
+ putc('}',genc);\r
+ putc('}',genc);\r
+ }\r
+;\r
+\r
+opcode(int opt;)\r
+ { char *p = buf;} :\r
+ [\r
+ [ LETTER\r
+ | DIGIT\r
+ | OTHER\r
+ ]\r
+ { *p++ = dot.t_attrib;}\r
+ ]+\r
+ SPACE+\r
+ { *p = '\0';\r
+ if (opt) addtohashtable(buf,countpat);\r
+ }\r
+;\r
+\r
+operand(int c;)\r
+ { register struct symtab *p = 0;} :\r
+ { fprintf(genc, "%c{\"", c);}\r
+ [\r
+ identifier\r
+ { if (!p) {\r
+ p = findident(idbuf,LOOKING,&idtable);\r
+ if (p) fprintf(genc,"\",%d,\"",p->s_num);\r
+ else fputs(idbuf,genc);\r
+ }\r
+ else fputs(idbuf,genc);\r
+ }\r
+ | DIGIT\r
+ { putc(dot.t_attrib,genc);}\r
+ | OTHER\r
+ { putc(dot.t_attrib,genc);}\r
+ ]+\r
+ { if (p) fputs("\"}",genc);\r
+ else fputs("\",0,\"\"}",genc);\r
+ }\r
+ SPACE*\r
+;\r
+\r
+replacement (int *n;)\r
+ {register int i;} :\r
+ SPACE*\r
+ { *n = 0;}\r
+ [\r
+ instruction(0)\r
+ { *n = 1;}\r
+ [\r
+ INSTRUCTION_SEPARATOR\r
+ { fputs(",\n", genc);}\r
+ SPACE*\r
+ instruction(0)\r
+ { *n += 1;}\r
+ ]*\r
+ | /* empty replacement, but there must be a\r
+ * structure initializer anyway\r
+ */\r
+ { fputs("\t{\"\", {",genc);\r
+ for (i = 0; i < maxoperand; i++) {\r
+ fprintf(genc, "%c{\"\",-1,\"\"}",i?',':' ');\r
+ }\r
+ fputs("}}",genc);\r
+ }\r
+ ]\r
+;\r
+\r
+\r
+identifier\r
+ { char *p = idbuf; } :\r
+ LETTER\r
+ { *p++ = dot.t_attrib;}\r
+ [ %while (1)\r
+ LETTER { *p++ = dot.t_attrib;}\r
+ | DIGIT { *p++ = dot.t_attrib;}\r
+ ]*\r
+ { *p = '\0';}\r
+;\r
+\r
+separator :\r
+ '%' '%' SPACE* LINE_TERMINATOR\r
+;\r