Mercurial

comparison third_party/luajit/src/host/buildvm_fold.c @ 186:8cf4ec5e2191 hg-web

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