==> src/lower.c <==1/* One pass over a validated body: instructions out, branches patched as their targets appear. */
2#include "wasm/lower.h"
3
4#include "wasm/instr.h"
5#include "wasm/reader.h"
6
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10
11/* A patch names an instruction's `a` or, with this bit, a br-table entry's target. */
12#define PATCH_ENTRY 0x80000000u
13
14typedef struct {
15 uint32_t op; /* block, loop, if, or 0: the function */
16 uint32_t height; /* operand height where the block's values start */
17 uint32_t nparams, nresults;
18 uint32_t start; /* loop: its label's target */
19 uint32_t *patches;
20 uint32_t npatches, cap;
21 int64_t else_patch; /* the if's BR_UNLESS, or -1 */
22 bool unreachable; /* the rest of this frame's current branch is dead */
23 bool dead; /* entered from dead code: nothing in it is emitted */
24} lframe;
25
26typedef struct {
27 const wasm_module *m;
28 wasm_fn_code *out;
29 uint32_t cap, brcap;
30 lframe *ctl;
31 uint32_t nctl, ccap;
32 uint32_t h, max_h;
33 bool oom;
34} L;
35
36static uint32_t emit(L *l, uint16_t op, uint32_t a, uint64_t b) {
37 wasm_fn_code *c = l->out;
38 if (c->ncode == l->cap) {
39 uint32_t cap = l->cap ? l->cap * 2 : 64;
40 wasm_ins *p = realloc(c->code, cap * sizeof *p);
41 if (!p) {
42 l->oom = true;
43 return 0;
44 }
45 c->code = p;
46 l->cap = cap;
47 }
48 c->code[c->ncode] = (wasm_ins){op, 0, a, b};
49 return c->ncode++;
50}
51
52static void patch_later(L *l, lframe *f, uint32_t p) {
53 if (f->npatches == f->cap) {
54 uint32_t cap = f->cap ? f->cap * 2 : 4;
55 uint32_t *q = realloc(f->patches, cap * sizeof *q);
56 if (!q) {
57 l->oom = true;
58 return;
59 }
60 f->patches = q;
61 f->cap = cap;
62 }
63 f->patches[f->npatches++] = p;
64}
65
66static void set_h(L *l, uint32_t h) {
67 l->h = h;
68 if (h > l->max_h) l->max_h = h;
69}
70
71static void push_frame(L *l, uint32_t op, uint32_t nparams, uint32_t nresults, bool dead) {
72 if (l->nctl == l->ccap) {
73 uint32_t cap = l->ccap ? l->ccap * 2 : 16;
74 lframe *p = realloc(l->ctl, cap * sizeof *p);
75 if (!p) {
76 l->oom = true;
77 return;
78 }
79 l->ctl = p;
80 l->ccap = cap;
81 }
82 lframe *f = &l->ctl[l->nctl++];
83 memset(f, 0, sizeof *f);
84 f->op = op;
85 f->nparams = nparams;
86 f->nresults = nresults;
87 f->height = dead ? 0 : l->h - nparams;
88 f->else_patch = -1;
89 f->dead = dead;
90}
91
92static void block_arity(const wasm_module *m, const wasm_instr *in, uint32_t *np, uint32_t *nr) {
93 if (in->blocktype >= 0) {
94 *np = m->types[in->blocktype].nparams;
95 *nr = m->types[in->blocktype].nresults;
96 } else {
97 *np = 0;
98 *nr = in->blocktype == WASM_BT_EMPTY ? 0 : 1;
99 }
100}
101
102/* A branch to the frame `depth` levels out: its target (now, or patched at its end), the height
103 * its values move to, how many. */
104static void branch(L *l, uint16_t op, uint32_t depth) {
105 lframe *f = &l->ctl[l->nctl - 1 - depth];
106 bool loop = f->op == WASM_OP_LOOP;
107 uint32_t values = loop ? f->nparams : f->nresults;
108 uint64_t b = (uint64_t)(l->out->nlocals + f->height) << 32 | values;
109 uint32_t i = emit(l, op, loop ? f->start : 0, b);
110 if (!loop) patch_later(l, f, i);
111}
112
113static void br_table(L *l, const wasm_instr *in) {
114 wasm_fn_code *c = l->out;
115 uint32_t n = in->ntargets + 1;
116 uint32_t *t = malloc(n * sizeof *t);
117 if (!t || c->nbrs + n < c->nbrs) {
118 free(t);
119 l->oom = true;
120 return;
121 }
122 wasm_instr_targets(in, t);
123 if (c->nbrs + n > l->brcap) {
124 uint32_t cap = l->brcap ? l->brcap : 16;
125 while (cap < c->nbrs + n) cap *= 2;
126 wasm_br_entry *p = realloc(c->brs, cap * sizeof *p);
127 if (!p) {
128 free(t);
129 l->oom = true;
130 return;
131 }
132 c->brs = p;
133 l->brcap = cap;
134 }
135 uint32_t first = c->nbrs;
136 for (uint32_t k = 0; k < n; k++) {
137 lframe *f = &l->ctl[l->nctl - 1 - t[k]];
138 bool loop = f->op == WASM_OP_LOOP;
139 c->brs[first + k] = (wasm_br_entry){loop ? f->start : 0, c->nlocals + f->height, loop ? f->nparams : f->nresults};
140 if (!loop) patch_later(l, f, PATCH_ENTRY | (first + k));
141 }
142 c->nbrs += n;
143 free(t);
144 emit(l, WASM_INS_BR_TABLE, first, n);
145}
146
147static void resolve(L *l, lframe *f, uint32_t target) {
148 for (uint32_t k = 0; k < f->npatches; k++) {
149 uint32_t p = f->patches[k];
150 if (p & PATCH_ENTRY) l->out->brs[p & ~PATCH_ENTRY].target = target;
151 else l->out->code[p].a = target;
152 }
153 f->npatches = 0;
154}
155
156/* Pops and pushes of a plain instruction, from its signature. */
157static void sig_effect(const char *sig, uint32_t *pops, uint32_t *pushes) {
158 const char *gt = strchr(sig, '>');
159 *pops = (uint32_t)(gt - sig);
160 *pushes = (uint32_t)strlen(gt + 1);
161}
162
163static bool instr(L *l, const wasm_instr *in) {
164 const wasm_module *m = l->m;
165 lframe *f = &l->ctl[l->nctl - 1];
166 uint32_t np, nr;
167 /* Dead code: only the block structure is followed. */
168 if (f->dead || f->unreachable) {
169 switch (in->op) {
170 case WASM_OP_BLOCK:
171 case WASM_OP_LOOP:
172 case WASM_OP_IF: push_frame(l, in->op, 0, 0, true); return true;
173 case WASM_OP_ELSE:
174 case WASM_OP_END:
175 if (f->dead) {
176 if (in->op == WASM_OP_END) l->nctl--;
177 return true;
178 }
179 break; /* a live frame's dead branch ends: handled below */
180 default: return true;
181 }
182 }
183 if (in->info.sig && in->op != WASM_OP_MEMORY_SIZE && in->op != WASM_OP_MEMORY_GROW) {
184 uint32_t pops, pushes;
185 sig_effect(in->info.sig, &pops, &pushes);
186 uint64_t b = 0;
187 switch (in->info.imm) {
188 case WASM_IMM_MEMARG: b = in->moffset; break;
189 case WASM_IMM_I32: b = (uint32_t)in->i; break;
190 case WASM_IMM_I64: b = (uint64_t)in->i; break;
191 case WASM_IMM_F32: b = in->f32; break;
192 case WASM_IMM_F64: b = in->f64; break;
193 default: break;
194 }
195 uint16_t op = in->op > 0xff ? (uint16_t)(WASM_INS_FC + (in->op & 0xffff)) : (uint16_t)in->op;
196 emit(l, op, 0, b);
197 set_h(l, l->h - pops + pushes);
198 return true;
199 }
200 switch (in->op) {
201 case WASM_OP_UNREACHABLE:
202 emit(l, 0x00, 0, 0);
203 f->unreachable = true;
204 return true;
205 case WASM_OP_NOP: return true;
206 case WASM_OP_BLOCK:
207 block_arity(m, in, &np, &nr);
208 push_frame(l, WASM_OP_BLOCK, np, nr, false);
209 return true;
210 case WASM_OP_LOOP:
211 block_arity(m, in, &np, &nr);
212 push_frame(l, WASM_OP_LOOP, np, nr, false);
213 if (!l->oom) l->ctl[l->nctl - 1].start = emit(l, WASM_INS_INTERRUPT, 0, 0);
214 return true;
215 case WASM_OP_IF: {
216 block_arity(m, in, &np, &nr);
217 set_h(l, l->h - 1);
218 uint32_t i = emit(l, WASM_INS_BR_UNLESS, 0, 0);
219 push_frame(l, WASM_OP_IF, np, nr, false);
220 if (!l->oom) l->ctl[l->nctl - 1].else_patch = i;
221 return true;
222 }
223 case WASM_OP_ELSE:
224 if (!f->unreachable) patch_later(l, f, emit(l, WASM_INS_JUMP, 0, 0));
225 if (f->else_patch >= 0) l->out->code[f->else_patch].a = l->out->ncode;
226 f->else_patch = -1;
227 f->unreachable = false;
228 set_h(l, f->height + f->nparams);
229 return true;
230 case WASM_OP_END: {
231 uint32_t here = l->out->ncode;
232 if (f->else_patch >= 0) l->out->code[f->else_patch].a = here;
233 resolve(l, f, here);
234 if (f->op == 0) emit(l, WASM_INS_RETURN, f->nresults, 0);
235 set_h(l, f->height + f->nresults);
236 free(f->patches);
237 l->nctl--;
238 return true;
239 }
240 case WASM_OP_BR:
241 branch(l, WASM_INS_BR, in->a);
242 f->unreachable = true;
243 return true;
244 case WASM_OP_BR_IF:
245 set_h(l, l->h - 1);
246 branch(l, WASM_INS_BR_IF, in->a);
247 return true;
248 case WASM_OP_BR_TABLE:
249 set_h(l, l->h - 1);
250 br_table(l, in);
251 f->unreachable = true;
252 return true;
253 case WASM_OP_RETURN:
254 emit(l, WASM_INS_RETURN, l->out->nresults, 0);
255 f->unreachable = true;
256 return true;
257 case WASM_OP_CALL: {
258 const wasm_functype *t = wasm_func_type(m, in->a);
259 emit(l, WASM_INS_CALL, in->a, 0);
260 set_h(l, l->h - t->nparams + t->nresults);
261 return true;
262 }
263 case WASM_OP_CALL_INDIRECT: {
264 const wasm_functype *t = &m->types[in->a];
265 emit(l, WASM_INS_CALL_INDIRECT, in->a, in->b);
266 set_h(l, l->h - 1 - t->nparams + t->nresults);
267 return true;
268 }
269 case WASM_OP_DROP:
270 emit(l, WASM_OP_DROP, 0, 0);
271 set_h(l, l->h - 1);
272 return true;
273 case WASM_OP_SELECT:
274 case WASM_OP_SELECT_T:
275 emit(l, WASM_OP_SELECT, 0, 0);
276 set_h(l, l->h - 2);
277 return true;
278 case WASM_OP_LOCAL_GET:
279 emit(l, WASM_OP_LOCAL_GET, in->a, 0);
280 set_h(l, l->h + 1);
281 return true;
282 case WASM_OP_LOCAL_SET:
283 emit(l, WASM_OP_LOCAL_SET, in->a, 0);
284 set_h(l, l->h - 1);
285 return true;
286 case WASM_OP_LOCAL_TEE: emit(l, WASM_OP_LOCAL_TEE, in->a, 0); return true;
287 case WASM_OP_GLOBAL_GET:
288 emit(l, WASM_OP_GLOBAL_GET, in->a, 0);
289 set_h(l, l->h + 1);
290 return true;
291 case WASM_OP_GLOBAL_SET:
292 emit(l, WASM_OP_GLOBAL_SET, in->a, 0);
293 set_h(l, l->h - 1);
294 return true;
295 case WASM_OP_TABLE_GET: emit(l, WASM_OP_TABLE_GET, in->a, 0); return true;
296 case WASM_OP_TABLE_SET:
297 emit(l, WASM_OP_TABLE_SET, in->a, 0);
298 set_h(l, l->h - 2);
299 return true;
300 case WASM_OP_MEMORY_SIZE:
301 emit(l, WASM_OP_MEMORY_SIZE, 0, 0);
302 set_h(l, l->h + 1);
303 return true;
304 case WASM_OP_MEMORY_GROW: emit(l, WASM_OP_MEMORY_GROW, 0, 0); return true;
305 case WASM_OP_REF_NULL:
306 emit(l, WASM_OP_REF_NULL, 0, 0);
307 set_h(l, l->h + 1);
308 return true;
309 case WASM_OP_REF_IS_NULL: emit(l, WASM_OP_REF_IS_NULL, 0, 0); return true;
310 case WASM_OP_REF_FUNC:
311 emit(l, WASM_OP_REF_FUNC, in->a, 0);
312 set_h(l, l->h + 1);
313 return true;
314 case WASM_OP_MEMORY_INIT:
315 emit(l, WASM_INS_FC + 8, in->a, 0);
316 set_h(l, l->h - 3);
317 return true;
318 case WASM_OP_DATA_DROP: emit(l, WASM_INS_FC + 9, in->a, 0); return true;
319 case WASM_OP_MEMORY_COPY:
320 case WASM_OP_MEMORY_FILL:
321 emit(l, (uint16_t)(WASM_INS_FC + (in->op & 0xffff)), 0, 0);
322 set_h(l, l->h - 3);
323 return true;
324 case WASM_OP_TABLE_INIT:
325 case WASM_OP_TABLE_COPY:
326 emit(l, (uint16_t)(WASM_INS_FC + (in->op & 0xffff)), in->a, in->b);
327 set_h(l, l->h - 3);
328 return true;
329 case WASM_OP_ELEM_DROP: emit(l, WASM_INS_FC + 13, in->a, 0); return true;
330 case WASM_OP_TABLE_GROW:
331 emit(l, WASM_INS_FC + 15, in->a, 0);
332 set_h(l, l->h - 1);
333 return true;
334 case WASM_OP_TABLE_SIZE:
335 emit(l, WASM_INS_FC + 16, in->a, 0);
336 set_h(l, l->h + 1);
337 return true;
338 case WASM_OP_TABLE_FILL:
339 emit(l, WASM_INS_FC + 17, in->a, 0);
340 set_h(l, l->h - 3);
341 return true;
342 default: return false;
343 }
344}
345
346bool wasm_lower(const wasm_module *m, uint32_t func, wasm_fn_code *out, char *err, size_t errlen) {
347 memset(out, 0, sizeof *out);
348 if (err && errlen) err[0] = 0;
349 const wasm_code *code = &m->codes[func - m->nfunc_imports];
350 const wasm_functype *t = wasm_func_type(m, func);
351 out->nparams = t->nparams;
352 out->nresults = t->nresults;
353 out->nlocals = (uint32_t)(t->nparams + code->nlocals);
354 L l = {0};
355 l.m = m;
356 l.out = out;
357 wasm_reader r = wasm_reader_at(m->bytes, code->body.start, code->body.start + code->body.len, err, errlen);
358 push_frame(&l, 0, 0, t->nresults, false);
359 wasm_instr in;
360 bool ok = true;
361 while (ok && l.nctl > 0 && !l.oom) {
362 if (!wasm_rd_instr(&r, &in)) {
363 ok = false;
364 break;
365 }
366 if (in.info.feature & (WASM_F_SIMD | WASM_F_RELAXED_SIMD | WASM_F_THREADS)) {
367 ok = wasm_rd_fail_at(&r, in.offset, "%s is not supported by this executor (alpha-c-mesh's wasm interpreter)",
368 in.info.feature == WASM_F_THREADS ? "threads" : "SIMD");
369 break;
370 }
371 if (!instr(&l, &in)) ok = wasm_rd_fail_at(&r, in.offset, "%s is not supported by this executor", in.info.name);
372 }
373 if (l.oom && ok) ok = wasm_rd_fail_at(&r, code->offset, "out of memory");
374 for (uint32_t k = 0; k < l.nctl; k++) free(l.ctl[k].patches);
375 free(l.ctl);
376 out->frame_slots = out->nlocals + l.max_h + 1;
377 if (!ok) wasm_fn_code_free(out);
378 return ok;
379}
380
381void wasm_fn_code_free(wasm_fn_code *c) {
382 free(c->code);
383 free(c->brs);
384 memset(c, 0, sizeof *c);
385}
386
387uint32_t *wasm_canonical_types(const wasm_module *m) {
388 uint32_t *canon = malloc((m->ntypes ? m->ntypes : 1) * sizeof *canon);
389 if (!canon) return NULL;
390 for (uint32_t i = 0; i < m->ntypes; i++) {
391 canon[i] = i;
392 const wasm_functype *a = &m->types[i];
393 for (uint32_t j = 0; j < i; j++) {
394 const wasm_functype *b = &m->types[j];
395 if (a->nparams == b->nparams && a->nresults == b->nresults &&
396 (!a->nparams || memcmp(a->params, b->params, a->nparams) == 0) &&
397 (!a->nresults || memcmp(a->results, b->results, a->nresults) == 0)) {
398 canon[i] = canon[j];
399 break;
400 }
401 }
402 }
403 return canon;
404}