1/*
2** LuaJIT VM builder: IR folding hash table generator.
3** Copyright (C) 2005-2021 Mike Pall. See Copyright Notice in luajit.h
4*/
5
6#include "buildvm.h"
7#include "lj_obj.h"
8#include "lj_ir.h"
9
10/* Context for the folding hash table generator. */
11static int lineno;
12static uint32_t funcidx;
13static uint32_t foldkeys[BUILD_MAX_FOLD];
14static uint32_t nkeys;
15
16/* Try to fill the hash table with keys using the hash parameters. */
17static int tryhash(uint32_t *htab, uint32_t sz, uint32_t r, int dorol)
18{
19 uint32_t i;
20 if (dorol && ((r & 31) == 0 || (r>>5) == 0))
21 return 0; /* Avoid zero rotates. */
22 memset(htab, 0xff, (sz+1)*sizeof(uint32_t));
23 for (i = 0; i < nkeys; i++) {
24 uint32_t key = foldkeys[i];
25 uint32_t k = key & 0xffffff;
26 uint32_t h = (dorol ? lj_rol(lj_rol(k, r>>5) - k, r&31) :
27 (((k << (r>>5)) - k) << (r&31))) % sz;
28 if (htab[h] != 0xffffffff) { /* Collision on primary slot. */
29 if (htab[h+1] != 0xffffffff) { /* Collision on secondary slot. */
30 /* Try to move the colliding key, if possible. */
31 if (h < sz-1 && htab[h+2] == 0xffffffff) {
32 uint32_t k2 = htab[h+1] & 0xffffff;
33 uint32_t h2 = (dorol ? lj_rol(lj_rol(k2, r>>5) - k2, r&31) :
34 (((k2 << (r>>5)) - k2) << (r&31))) % sz;
35 if (h2 != h+1) return 0; /* Cannot resolve collision. */
36 htab[h+2] = htab[h+1]; /* Move colliding key to secondary slot. */
37 } else {
38 return 0; /* Collision. */
39 }
40 }
41 htab[h+1] = key;
42 } else {
43 htab[h] = key;
44 }
45 }
46 return 1; /* Success, all keys could be stored. */
47}
48
49/* Print the generated hash table. */
50static void printhash(BuildCtx *ctx, uint32_t *htab, uint32_t sz)
51{
52 uint32_t i;
53 fprintf(ctx->fp, "static const uint32_t fold_hash[%d] = {\n0x%08x",
54 sz+1, htab[0]);
55 for (i = 1; i < sz+1; i++)
56 fprintf(ctx->fp, ",\n0x%08x", htab[i]);
57 fprintf(ctx->fp, "\n};\n\n");
58}
59
60/* Exhaustive search for the shortest semi-perfect hash table. */
61static void makehash(BuildCtx *ctx)
62{
63 uint32_t htab[BUILD_MAX_FOLD*2+1];
64 uint32_t sz, r;
65 /* Search for the smallest hash table with an odd size. */
66 for (sz = (nkeys|1); sz < BUILD_MAX_FOLD*2; sz += 2) {
67 /* First try all shift hash combinations. */
68 for (r = 0; r < 32*32; r++) {
69 if (tryhash(htab, sz, r, 0)) {
70 printhash(ctx, htab, sz);
71 fprintf(ctx->fp,
72 "#define fold_hashkey(k)\t(((((k)<<%u)-(k))<<%u)%%%u)\n\n",
73 r>>5, r&31, sz);
74 return;
75 }
76 }
77 /* Then try all rotate hash combinations. */
78 for (r = 0; r < 32*32; r++) {
79 if (tryhash(htab, sz, r, 1)) {
80 printhash(ctx, htab, sz);
81 fprintf(ctx->fp,
82 "#define fold_hashkey(k)\t(lj_rol(lj_rol((k),%u)-(k),%u)%%%u)\n\n",
83 r>>5, r&31, sz);
84 return;
85 }
86 }
87 }
88 fprintf(stderr, "Error: search for perfect hash failed\n");
89 exit(1);
90}
91
92/* Parse one token of a fold rule. */
93static uint32_t nexttoken(char **pp, int allowlit, int allowany)
94{
95 char *p = *pp;
96 if (p) {
97 uint32_t i;
98 char *q = strchr(p, ' ');
99 if (q) *q++ = '\0';
100 *pp = q;
101 if (allowlit && !strncmp(p, "IRFPM_", 6)) {
102 for (i = 0; irfpm_names[i]; i++)
103 if (!strcmp(irfpm_names[i], p+6))
104 return i;
105 } else if (allowlit && !strncmp(p, "IRFL_", 5)) {
106 for (i = 0; irfield_names[i]; i++)
107 if (!strcmp(irfield_names[i], p+5))
108 return i;
109 } else if (allowlit && !strncmp(p, "IRCALL_", 7)) {
110 for (i = 0; ircall_names[i]; i++)
111 if (!strcmp(ircall_names[i], p+7))
112 return i;
113 } else if (allowlit && !strncmp(p, "IRCONV_", 7)) {
114 for (i = 0; irt_names[i]; i++) {
115 const char *r = strchr(p+7, '_');
116 if (r && !strncmp(irt_names[i], p+7, r-(p+7))) {
117 uint32_t j;
118 for (j = 0; irt_names[j]; j++)
119 if (!strcmp(irt_names[j], r+1))
120 return (i << 5) + j;
121 }
122 }
123 } else if (allowlit && *p >= '0' && *p <= '9') {
124 for (i = 0; *p >= '0' && *p <= '9'; p++)
125 i = i*10 + (*p - '0');
126 if (*p == '\0')
127 return i;
128 } else if (allowany && !strcmp("any", p)) {
129 return allowany;
130 } else {
131 for (i = 0; ir_names[i]; i++)
132 if (!strcmp(ir_names[i], p))
133 return i;
134 }
135 fprintf(stderr, "Error: bad fold definition token \"%s\" at line %d\n", p, lineno);
136 exit(1);
137 }
138 return 0;
139}
140
141/* Parse a fold rule. */
142static void foldrule(char *p)
143{
144 uint32_t op = nexttoken(&p, 0, 0);
145 uint32_t left = nexttoken(&p, 0, 0x7f);
146 uint32_t right = nexttoken(&p, 1, 0x3ff);
147 uint32_t key = (funcidx << 24) | (op << 17) | (left << 10) | right;
148 uint32_t i;
149 if (nkeys >= BUILD_MAX_FOLD) {
150 fprintf(stderr, "Error: too many fold rules, increase BUILD_MAX_FOLD.\n");
151 exit(1);
152 }
153 /* Simple insertion sort to detect duplicates. */
154 for (i = nkeys; i > 0; i--) {
155 if ((foldkeys[i-1]&0xffffff) < (key & 0xffffff))
156 break;
157 if ((foldkeys[i-1]&0xffffff) == (key & 0xffffff)) {
158 fprintf(stderr, "Error: duplicate fold definition at line %d\n", lineno);
159 exit(1);
160 }
161 foldkeys[i] = foldkeys[i-1];
162 }
163 foldkeys[i] = key;
164 nkeys++;
165}
166
167/* Emit C source code for IR folding hash table. */
168void emit_fold(BuildCtx *ctx)
169{
170 char buf[256]; /* We don't care about analyzing lines longer than that. */
171 const char *fname = ctx->args[0];
172 FILE *fp;
173
174 if (fname == NULL) {
175 fprintf(stderr, "Error: missing input filename\n");
176 exit(1);
177 }
178
179 if (fname[0] == '-' && fname[1] == '\0') {
180 fp = stdin;
181 } else {
182 fp = fopen(fname, "r");
183 if (!fp) {
184 fprintf(stderr, "Error: cannot open input file '%s': %s\n",
185 fname, strerror(errno));
186 exit(1);
187 }
188 }
189
190 fprintf(ctx->fp, "/* This is a generated file. DO NOT EDIT! */\n\n");
191 fprintf(ctx->fp, "static const FoldFunc fold_func[] = {\n");
192
193 lineno = 0;
194 funcidx = 0;
195 nkeys = 0;
196 while (fgets(buf, sizeof(buf), fp) != NULL) {
197 lineno++;
198 /* The prefix must be at the start of a line, otherwise it's ignored. */
199 if (!strncmp(buf, FOLDDEF_PREFIX, sizeof(FOLDDEF_PREFIX)-1)) {
200 char *p = buf+sizeof(FOLDDEF_PREFIX)-1;
201 char *q = strchr(p, ')');
202 if (p[0] == '(' && q) {
203 p++;
204 *q = '\0';
205 foldrule(p);
206 } else if ((p[0] == 'F' || p[0] == 'X') && p[1] == '(' && q) {
207 p += 2;
208 *q = '\0';
209 if (funcidx)
210 fprintf(ctx->fp, ",\n");
211 if (p[-2] == 'X')
212 fprintf(ctx->fp, " %s", p);
213 else
214 fprintf(ctx->fp, " fold_%s", p);
215 funcidx++;
216 } else {
217 buf[strlen(buf)-1] = '\0';
218 fprintf(stderr, "Error: unknown fold definition tag %s%s at line %d\n",
219 FOLDDEF_PREFIX, p, lineno);
220 exit(1);
221 }
222 }
223 }
224 fclose(fp);
225 fprintf(ctx->fp, "\n};\n\n");
226
227 makehash(ctx);
228}
229
230