1	/*
2	* Copyright 2015 WebAssembly Community Group participants
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16
17	//
18	// Parses and emits WebAssembly binary code
19	//
20
21	#ifndef wasm_wasm_binary_h
22	#define wasm_wasm_binary_h
23
24	#include <cassert>
25	#include <ostream>
26	#include <type_traits>
27
28	#include "ir/import-utils.h"
29	#include "ir/module-utils.h"
30	#include "parsing.h"
31	#include "support/debug.h"
32	#include "wasm-builder.h"
33	#include "wasm-traversal.h"
34	#include "wasm-validator.h"
35	#include "wasm.h"
36
37	#define DEBUG_TYPE "binary"
38
39	namespace wasm {
40
41	enum {
42	// the maximum amount of bytes we emit per LEB
43	MaxLEB32Bytes = 5,
44	};
45
46	// wasm VMs on the web have decided to impose some limits on what they
47	// accept
48	enum WebLimitations : uint32_t {
49	MaxDataSegments = 100 * 1000,
50	MaxFunctionBodySize = 128 * 1024,
51	MaxFunctionLocals = 50 * 1000,
52	MaxFunctionParams = 1000
53	};
54
55	template<typename T, typename MiniT> struct LEB {
56	static_assert(sizeof(MiniT) == 1, "MiniT must be a byte");
57
58	T value;
59
60	LEB() = default;
61	LEB(T value) : value(value) {}
62
63	bool hasMore(T temp, MiniT byte) {
64	// for signed, we must ensure the last bit has the right sign, as it will
65	// zero extend
66	return std::is_signed<T>::value
67	? (temp != 0 && temp != T(-1)) || (value >= 0 && (byte & 64)) ||
68	(value < 0 && !(byte & 64))
69	: (temp != 0);
70	}
71
72	void write(std::vector<uint8_t>* out) {
73	T temp = value;
74	bool more;
75	do {
76	uint8_t byte = temp & 127;
77	temp >>= 7;
78	more = hasMore(temp, byte);
79	if (more) {
80	byte = byte | 128;
81	}
82	out->push_back(byte);
83	} while (more);
84	}
85
86	// @minimum: a minimum number of bytes to write, padding as necessary
87	// returns the number of bytes written
88	size_t writeAt(std::vector<uint8_t>* out, size_t at, size_t minimum = 0) {
89	T temp = value;
90	size_t offset = 0;
91	bool more;
92	do {
93	uint8_t byte = temp & 127;
94	temp >>= 7;
95	more = hasMore(temp, byte) || offset + 1 < minimum;
96	if (more) {
97	byte = byte | 128;
98	}
99	(*out)[at + offset] = byte;
100	offset++;
101	} while (more);
102	return offset;
103	}
104
105	LEB<T, MiniT>& read(std::function<MiniT()> get) {
106	value = 0;
107	T shift = 0;
108	MiniT byte;
109	while (1) {
110	byte = get();
111	bool last = !(byte & 128);
112	T payload = byte & 127;
113	using mask_type = typename std::make_unsigned<T>::type;
114	auto shift_mask = 0 == shift
115	? ~mask_type(0)
116	: ((mask_type(1) << (sizeof(T) * 8 - shift)) - 1u);
117	T significant_payload = payload & shift_mask;
118	if (significant_payload != payload) {
119	if (!(std::is_signed<T>::value && last)) {
120	throw ParseException("LEB dropped bits only valid for signed LEB");
121	}
122	}
123	value |= significant_payload << shift;
124	if (last) {
125	break;
126	}
127	shift += 7;
128	if (size_t(shift) >= sizeof(T) * 8) {
129	throw ParseException("LEB overflow");
130	}
131	}
132	// If signed LEB, then we might need to sign-extend. (compile should
133	// optimize this out if not needed).
134	if (std::is_signed<T>::value) {
135	shift += 7;
136	if ((byte & 64) && size_t(shift) < 8 * sizeof(T)) {
137	size_t sext_bits = 8 * sizeof(T) - size_t(shift);
138	value <<= sext_bits;
139	value >>= sext_bits;
140	if (value >= 0) {
141	throw ParseException(
142	" LEBsign-extend should produce a negative value");
143	}
144	}
145	}
146	return *this;
147	}
148	};
149
150	using U32LEB = LEB<uint32_t, uint8_t>;
151	using U64LEB = LEB<uint64_t, uint8_t>;
152	using S32LEB = LEB<int32_t, int8_t>;
153	using S64LEB = LEB<int64_t, int8_t>;
154
155	//
156	// We mostly stream into a buffer as we create the binary format, however,
157	// sometimes we need to backtrack and write to a location behind us - wasm
158	// is optimized for reading, not writing.
159	//
160	class BufferWithRandomAccess : public std::vector<uint8_t> {
161	public:
162	BufferWithRandomAccess() = default;
163
164	BufferWithRandomAccess& operator<<(int8_t x) {
165	BYN_TRACE("writeInt8: " << (int)(uint8_t)x << " (at " << size() << ")\n");
166	push_back(x);
167	return *this;
168	}
169	BufferWithRandomAccess& operator<<(int16_t x) {
170	BYN_TRACE("writeInt16: " << x << " (at " << size() << ")\n");
171	push_back(x & 0xff);
172	push_back(x >> 8);
173	return *this;
174	}
175	BufferWithRandomAccess& operator<<(int32_t x) {
176	BYN_TRACE("writeInt32: " << x << " (at " << size() << ")\n");
177	push_back(x & 0xff);
178	x >>= 8;
179	push_back(x & 0xff);
180	x >>= 8;
181	push_back(x & 0xff);
182	x >>= 8;
183	push_back(x & 0xff);
184	return *this;
185	}
186	BufferWithRandomAccess& operator<<(int64_t x) {
187	BYN_TRACE("writeInt64: " << x << " (at " << size() << ")\n");
188	push_back(x & 0xff);
189	x >>= 8;
190	push_back(x & 0xff);
191	x >>= 8;
192	push_back(x & 0xff);
193	x >>= 8;
194	push_back(x & 0xff);
195	x >>= 8;
196	push_back(x & 0xff);
197	x >>= 8;
198	push_back(x & 0xff);
199	x >>= 8;
200	push_back(x & 0xff);
201	x >>= 8;
202	push_back(x & 0xff);
203	return *this;
204	}
205	BufferWithRandomAccess& operator<<(U32LEB x) {
206	[[maybe_unused]] size_t before = -1;
207	BYN_DEBUG(before = size(); std::cerr << "writeU32LEB: " << x.value
208	<< " (at " << before << ")"
209	<< std::endl;);
210	x.write(this);
211	BYN_DEBUG(for (size_t i = before; i < size(); i++) {
212	std::cerr << " " << (int)at(i) << " (at " << i << ")\n";
213	});
214	return *this;
215	}
216	BufferWithRandomAccess& operator<<(U64LEB x) {
217	[[maybe_unused]] size_t before = -1;
218	BYN_DEBUG(before = size(); std::cerr << "writeU64LEB: " << x.value
219	<< " (at " << before << ")"
220	<< std::endl;);
221	x.write(this);
222	BYN_DEBUG(for (size_t i = before; i < size(); i++) {
223	std::cerr << " " << (int)at(i) << " (at " << i << ")\n";
224	});
225	return *this;
226	}
227	BufferWithRandomAccess& operator<<(S32LEB x) {
228	[[maybe_unused]] size_t before = -1;
229	BYN_DEBUG(before = size(); std::cerr << "writeS32LEB: " << x.value
230	<< " (at " << before << ")"
231	<< std::endl;);
232	x.write(this);
233	BYN_DEBUG(for (size_t i = before; i < size(); i++) {
234	std::cerr << " " << (int)at(i) << " (at " << i << ")\n";
235	});
236	return *this;
237	}
238	BufferWithRandomAccess& operator<<(S64LEB x) {
239	[[maybe_unused]] size_t before = -1;
240	BYN_DEBUG(before = size(); std::cerr << "writeS64LEB: " << x.value
241	<< " (at " << before << ")"
242	<< std::endl;);
243	x.write(this);
244	BYN_DEBUG(for (size_t i = before; i < size(); i++) {
245	std::cerr << " " << (int)at(i) << " (at " << i << ")\n";
246	});
247	return *this;
248	}
249
250	BufferWithRandomAccess& operator<<(uint8_t x) { return *this << (int8_t)x; }
251	BufferWithRandomAccess& operator<<(uint16_t x) { return *this << (int16_t)x; }
252	BufferWithRandomAccess& operator<<(uint32_t x) { return *this << (int32_t)x; }
253	BufferWithRandomAccess& operator<<(uint64_t x) { return *this << (int64_t)x; }
254
255	BufferWithRandomAccess& operator<<(float x) {
256	BYN_TRACE("writeFloat32: " << x << " (at " << size() << ")\n");
257	return *this << Literal(x).reinterpreti32();
258	}
259	BufferWithRandomAccess& operator<<(double x) {
260	BYN_TRACE("writeFloat64: " << x << " (at " << size() << ")\n");
261	return *this << Literal(x).reinterpreti64();
262	}
263
264	void writeAt(size_t i, uint16_t x) {
265	BYN_TRACE("backpatchInt16: " << x << " (at " << i << ")\n");
266	(*this)[i] = x & 0xff;
267	(*this)[i + 1] = x >> 8;
268	}
269	void writeAt(size_t i, uint32_t x) {
270	BYN_TRACE("backpatchInt32: " << x << " (at " << i << ")\n");
271	(*this)[i] = x & 0xff;
272	x >>= 8;
273	(*this)[i + 1] = x & 0xff;
274	x >>= 8;
275	(*this)[i + 2] = x & 0xff;
276	x >>= 8;
277	(*this)[i + 3] = x & 0xff;
278	}
279
280	// writes out an LEB to an arbitrary location. this writes the LEB as a full
281	// 5 bytes, the fixed amount that can easily be set aside ahead of time
282	void writeAtFullFixedSize(size_t i, U32LEB x) {
283	BYN_TRACE("backpatchU32LEB: " << x.value << " (at " << i << ")\n");
284	// fill all 5 bytes, we have to do this when backpatching
285	x.writeAt(this, i, MaxLEB32Bytes);
286	}
287	// writes out an LEB of normal size
288	// returns how many bytes were written
289	size_t writeAt(size_t i, U32LEB x) {
290	BYN_TRACE("writeAtU32LEB: " << x.value << " (at " << i << ")\n");
291	return x.writeAt(this, i);
292	}
293
294	template<typename T> void writeTo(T& o) {
295	for (auto c : *this) {
296	o << c;
297	}
298	}
299
300	std::vector<char> getAsChars() {
301	std::vector<char> ret;
302	ret.resize(size());
303	std::copy(begin(), end(), ret.begin());
304	return ret;
305	}
306	};
307
308	namespace BinaryConsts {
309
310	enum Meta { Magic = 0x6d736100, Version = 0x01 };
311
312	enum Section {
313	Custom = 0,
314	Type = 1,
315	Import = 2,
316	Function = 3,
317	Table = 4,
318	Memory = 5,
319	Global = 6,
320	Export = 7,
321	Start = 8,
322	Element = 9,
323	Code = 10,
324	Data = 11,
325	DataCount = 12,
326	Tag = 13,
327	Strings = 14,
328	};
329
330	// A passive segment is a segment that will not be automatically copied into a
331	// memory or table on instantiation, and must instead be applied manually
332	// using the instructions memory.init or table.init.
333	// An active segment is equivalent to a passive segment, but with an implicit
334	// memory.init followed by a data.drop (or table.init followed by a elem.drop)
335	// that is prepended to the module's start function.
336	// A declarative element segment is not available at runtime but merely serves
337	// to forward-declare references that are formed in code with instructions
338	// like ref.func.
339	enum SegmentFlag {
340	// Bit 0: 0 = active, 1 = passive
341	IsPassive = 1 << 0,
342	// Bit 1 if passive: 0 = passive, 1 = declarative
343	IsDeclarative = 1 << 1,
344	// Bit 1 if active: 0 = index 0, 1 = index given
345	HasIndex = 1 << 1,
346	// Table element segments only:
347	// Bit 2: 0 = elemType is funcref and a vector of func indexes given
348	// 1 = elemType is given and a vector of ref expressions is given
349	UsesExpressions = 1 << 2
350	};
351
352	enum EncodedType {
353	// value_type
354	i32 = -0x1, // 0x7f
355	i64 = -0x2, // 0x7e
356	f32 = -0x3, // 0x7d
357	f64 = -0x4, // 0x7c
358	v128 = -0x5, // 0x7b
359	i8 = -0x6, // 0x7a
360	i16 = -0x7, // 0x79
361	// function reference type
362	funcref = -0x10, // 0x70
363	// external (host) references
364	externref = -0x11, // 0x6f
365	// top type of references to non-function Wasm data.
366	anyref = -0x12, // 0x6e
367	// comparable reference type
368	eqref = -0x13, // 0x6d
369	// nullable typed function reference type, with parameter
370	nullable = -0x14, // 0x6c
371	// non-nullable typed function reference type, with parameter
372	nonnullable = -0x15, // 0x6b
373	// integer reference type
374	i31ref = -0x16, // 0x6a
375	// gc and string reference types
376	structref = -0x19, // 0x67
377	arrayref = -0x1a, // 0x66
378	stringref = -0x1c, // 0x64
379	stringview_wtf8 = -0x1d, // 0x63
380	stringview_wtf16 = -0x1e, // 0x62
381	stringview_iter = -0x1f, // 0x61
382	// bottom types
383	nullexternref = -0x17, // 0x69
384	nullfuncref = -0x18, // 0x68
385	nullref = -0x1b, // 0x65
386	// type forms
387	Func = -0x20, // 0x60
388	Struct = -0x21, // 0x5f
389	Array = -0x22, // 0x5e
390	Sub = -0x30, // 0x50
391	SubFinal = -0x32, // 0x4e
392	// prototype nominal forms we still parse
393	FuncSubtype = -0x23, // 0x5d
394	StructSubtype = -0x24, // 0x5c
395	ArraySubtype = -0x25, // 0x5b
396	// isorecursive recursion groups
397	Rec = -0x31, // 0x4f
398	// block_type
399	Empty = -0x40 // 0x40
400	};
401
402	enum EncodedHeapType {
403	func = -0x10, // 0x70
404	ext = -0x11, // 0x6f
405	any = -0x12, // 0x6e
406	eq = -0x13, // 0x6d
407	i31 = -0x16, // 0x6a
408	struct_ = -0x19, // 0x67
409	array = -0x1a, // 0x66
410	string = -0x1c, // 0x64
411	// stringview/iter constants are identical to type, and cannot be duplicated
412	// here as that would be a compiler error, so add _heap suffixes. See
413	// https://github.com/WebAssembly/stringref/issues/12
414	stringview_wtf8_heap = -0x1d, // 0x63
415	stringview_wtf16_heap = -0x1e, // 0x62
416	stringview_iter_heap = -0x1f, // 0x61
417	// bottom types
418	noext = -0x17, // 0x69
419	nofunc = -0x18, // 0x68
420	none = -0x1b, // 0x65
421	};
422
423	namespace CustomSections {
424	extern const char* Name;
425	extern const char* SourceMapUrl;
426	extern const char* Dylink;
427	extern const char* Dylink0;
428	extern const char* Linking;
429	extern const char* Producers;
430	extern const char* TargetFeatures;
431
432	extern const char* AtomicsFeature;
433	extern const char* BulkMemoryFeature;
434	extern const char* ExceptionHandlingFeature;
435	extern const char* MutableGlobalsFeature;
436	extern const char* TruncSatFeature;
437	extern const char* SignExtFeature;
438	extern const char* SIMD128Feature;
439	extern const char* ExceptionHandlingFeature;
440	extern const char* TailCallFeature;
441	extern const char* ReferenceTypesFeature;
442	extern const char* MultivalueFeature;
443	extern const char* GCFeature;
444	extern const char* Memory64Feature;
445	extern const char* RelaxedSIMDFeature;
446	extern const char* ExtendedConstFeature;
447	extern const char* StringsFeature;
448	extern const char* MultiMemoriesFeature;
449
450	enum Subsection {
451	NameModule = 0,
452	NameFunction = 1,
453	NameLocal = 2,
454	// see: https://github.com/WebAssembly/extended-name-section
455	NameLabel = 3,
456	NameType = 4,
457	NameTable = 5,
458	NameMemory = 6,
459	NameGlobal = 7,
460	NameElem = 8,
461	NameData = 9,
462	// see: https://github.com/WebAssembly/gc/issues/193
463	NameField = 10,
464	NameTag = 11,
465
466	DylinkMemInfo = 1,
467	DylinkNeeded = 2,
468	};
469
470	} // namespace CustomSections
471
472	enum ASTNodes {
473	Unreachable = 0x00,
474	Nop = 0x01,
475	Block = 0x02,
476	Loop = 0x03,
477	If = 0x04,
478	Else = 0x05,
479
480	End = 0x0b,
481	Br = 0x0c,
482	BrIf = 0x0d,
483	BrTable = 0x0e,
484	Return = 0x0f,
485
486	CallFunction = 0x10,
487	CallIndirect = 0x11,
488	RetCallFunction = 0x12,
489	RetCallIndirect = 0x13,
490
491	Drop = 0x1a,
492	Select = 0x1b,
493	SelectWithType = 0x1c, // added in reference types proposal
494
495	LocalGet = 0x20,
496	LocalSet = 0x21,
497	LocalTee = 0x22,
498	GlobalGet = 0x23,
499	GlobalSet = 0x24,
500
501	TableGet = 0x25,
502	TableSet = 0x26,
503
504	I32LoadMem = 0x28,
505	I64LoadMem = 0x29,
506	F32LoadMem = 0x2a,
507	F64LoadMem = 0x2b,
508
509	I32LoadMem8S = 0x2c,
510	I32LoadMem8U = 0x2d,
511	I32LoadMem16S = 0x2e,
512	I32LoadMem16U = 0x2f,
513	I64LoadMem8S = 0x30,
514	I64LoadMem8U = 0x31,
515	I64LoadMem16S = 0x32,
516	I64LoadMem16U = 0x33,
517	I64LoadMem32S = 0x34,
518	I64LoadMem32U = 0x35,
519
520	I32StoreMem = 0x36,
521	I64StoreMem = 0x37,
522	F32StoreMem = 0x38,
523	F64StoreMem = 0x39,
524
525	I32StoreMem8 = 0x3a,
526	I32StoreMem16 = 0x3b,
527	I64StoreMem8 = 0x3c,
528	I64StoreMem16 = 0x3d,
529	I64StoreMem32 = 0x3e,
530
531	MemorySize = 0x3f,
532	MemoryGrow = 0x40,
533
534	I32Const = 0x41,
535	I64Const = 0x42,
536	F32Const = 0x43,
537	F64Const = 0x44,
538
539	I32EqZ = 0x45,
540	I32Eq = 0x46,
541	I32Ne = 0x47,
542	I32LtS = 0x48,
543	I32LtU = 0x49,
544	I32GtS = 0x4a,
545	I32GtU = 0x4b,
546	I32LeS = 0x4c,
547	I32LeU = 0x4d,
548	I32GeS = 0x4e,
549	I32GeU = 0x4f,
550	I64EqZ = 0x50,
551	I64Eq = 0x51,
552	I64Ne = 0x52,
553	I64LtS = 0x53,
554	I64LtU = 0x54,
555	I64GtS = 0x55,
556	I64GtU = 0x56,
557	I64LeS = 0x57,
558	I64LeU = 0x58,
559	I64GeS = 0x59,
560	I64GeU = 0x5a,
561	F32Eq = 0x5b,
562	F32Ne = 0x5c,
563	F32Lt = 0x5d,
564	F32Gt = 0x5e,
565	F32Le = 0x5f,
566	F32Ge = 0x60,
567	F64Eq = 0x61,
568	F64Ne = 0x62,
569	F64Lt = 0x63,
570	F64Gt = 0x64,
571	F64Le = 0x65,
572	F64Ge = 0x66,
573
574	I32Clz = 0x67,
575	I32Ctz = 0x68,
576	I32Popcnt = 0x69,
577	I32Add = 0x6a,
578	I32Sub = 0x6b,
579	I32Mul = 0x6c,
580	I32DivS = 0x6d,
581	I32DivU = 0x6e,
582	I32RemS = 0x6f,
583	I32RemU = 0x70,
584	I32And = 0x71,
585	I32Or = 0x72,
586	I32Xor = 0x73,
587	I32Shl = 0x74,
588	I32ShrS = 0x75,
589	I32ShrU = 0x76,
590	I32RotL = 0x77,
591	I32RotR = 0x78,
592
593	I64Clz = 0x79,
594	I64Ctz = 0x7a,
595	I64Popcnt = 0x7b,
596	I64Add = 0x7c,
597	I64Sub = 0x7d,
598	I64Mul = 0x7e,
599	I64DivS = 0x7f,
600	I64DivU = 0x80,
601	I64RemS = 0x81,
602	I64RemU = 0x82,
603	I64And = 0x83,
604	I64Or = 0x84,
605	I64Xor = 0x85,
606	I64Shl = 0x86,
607	I64ShrS = 0x87,
608	I64ShrU = 0x88,
609	I64RotL = 0x89,
610	I64RotR = 0x8a,
611
612	F32Abs = 0x8b,
613	F32Neg = 0x8c,
614	F32Ceil = 0x8d,
615	F32Floor = 0x8e,
616	F32Trunc = 0x8f,
617	F32NearestInt = 0x90,
618	F32Sqrt = 0x91,
619	F32Add = 0x92,
620	F32Sub = 0x93,
621	F32Mul = 0x94,
622	F32Div = 0x95,
623	F32Min = 0x96,
624	F32Max = 0x97,
625	F32CopySign = 0x98,
626
627	F64Abs = 0x99,
628	F64Neg = 0x9a,
629	F64Ceil = 0x9b,
630	F64Floor = 0x9c,
631	F64Trunc = 0x9d,
632	F64NearestInt = 0x9e,
633	F64Sqrt = 0x9f,
634	F64Add = 0xa0,
635	F64Sub = 0xa1,
636	F64Mul = 0xa2,
637	F64Div = 0xa3,
638	F64Min = 0xa4,
639	F64Max = 0xa5,
640	F64CopySign = 0xa6,
641
642	I32WrapI64 = 0xa7,
643	I32STruncF32 = 0xa8,
644	I32UTruncF32 = 0xa9,
645	I32STruncF64 = 0xaa,
646	I32UTruncF64 = 0xab,
647	I64SExtendI32 = 0xac,
648	I64UExtendI32 = 0xad,
649	I64STruncF32 = 0xae,
650	I64UTruncF32 = 0xaf,
651	I64STruncF64 = 0xb0,
652	I64UTruncF64 = 0xb1,
653	F32SConvertI32 = 0xb2,
654	F32UConvertI32 = 0xb3,
655	F32SConvertI64 = 0xb4,
656	F32UConvertI64 = 0xb5,
657	F32DemoteI64 = 0xb6,
658	F64SConvertI32 = 0xb7,
659	F64UConvertI32 = 0xb8,
660	F64SConvertI64 = 0xb9,
661	F64UConvertI64 = 0xba,
662	F64PromoteF32 = 0xbb,
663
664	I32ReinterpretF32 = 0xbc,
665	I64ReinterpretF64 = 0xbd,
666	F32ReinterpretI32 = 0xbe,
667	F64ReinterpretI64 = 0xbf,
668
669	I32ExtendS8 = 0xc0,
670	I32ExtendS16 = 0xc1,
671	I64ExtendS8 = 0xc2,
672	I64ExtendS16 = 0xc3,
673	I64ExtendS32 = 0xc4,
674
675	// prefixes
676
677	GCPrefix = 0xfb,
678	MiscPrefix = 0xfc,
679	SIMDPrefix = 0xfd,
680	AtomicPrefix = 0xfe,
681
682	// atomic opcodes
683
684	AtomicNotify = 0x00,
685	I32AtomicWait = 0x01,
686	I64AtomicWait = 0x02,
687	AtomicFence = 0x03,
688
689	I32AtomicLoad = 0x10,
690	I64AtomicLoad = 0x11,
691	I32AtomicLoad8U = 0x12,
692	I32AtomicLoad16U = 0x13,
693	I64AtomicLoad8U = 0x14,
694	I64AtomicLoad16U = 0x15,
695	I64AtomicLoad32U = 0x16,
696	I32AtomicStore = 0x17,
697	I64AtomicStore = 0x18,
698	I32AtomicStore8 = 0x19,
699	I32AtomicStore16 = 0x1a,
700	I64AtomicStore8 = 0x1b,
701	I64AtomicStore16 = 0x1c,
702	I64AtomicStore32 = 0x1d,
703
704	AtomicRMWOps_Begin = 0x1e,
705	I32AtomicRMWAdd = 0x1e,
706	I64AtomicRMWAdd = 0x1f,
707	I32AtomicRMWAdd8U = 0x20,
708	I32AtomicRMWAdd16U = 0x21,
709	I64AtomicRMWAdd8U = 0x22,
710	I64AtomicRMWAdd16U = 0x23,
711	I64AtomicRMWAdd32U = 0x24,
712	I32AtomicRMWSub = 0x25,
713	I64AtomicRMWSub = 0x26,
714	I32AtomicRMWSub8U = 0x27,
715	I32AtomicRMWSub16U = 0x28,
716	I64AtomicRMWSub8U = 0x29,
717	I64AtomicRMWSub16U = 0x2a,
718	I64AtomicRMWSub32U = 0x2b,
719	I32AtomicRMWAnd = 0x2c,
720	I64AtomicRMWAnd = 0x2d,
721	I32AtomicRMWAnd8U = 0x2e,
722	I32AtomicRMWAnd16U = 0x2f,
723	I64AtomicRMWAnd8U = 0x30,
724	I64AtomicRMWAnd16U = 0x31,
725	I64AtomicRMWAnd32U = 0x32,
726	I32AtomicRMWOr = 0x33,
727	I64AtomicRMWOr = 0x34,
728	I32AtomicRMWOr8U = 0x35,
729	I32AtomicRMWOr16U = 0x36,
730	I64AtomicRMWOr8U = 0x37,
731	I64AtomicRMWOr16U = 0x38,
732	I64AtomicRMWOr32U = 0x39,
733	I32AtomicRMWXor = 0x3a,
734	I64AtomicRMWXor = 0x3b,
735	I32AtomicRMWXor8U = 0x3c,
736	I32AtomicRMWXor16U = 0x3d,
737	I64AtomicRMWXor8U = 0x3e,
738	I64AtomicRMWXor16U = 0x3f,
739	I64AtomicRMWXor32U = 0x40,
740	I32AtomicRMWXchg = 0x41,
741	I64AtomicRMWXchg = 0x42,
742	I32AtomicRMWXchg8U = 0x43,
743	I32AtomicRMWXchg16U = 0x44,
744	I64AtomicRMWXchg8U = 0x45,
745	I64AtomicRMWXchg16U = 0x46,
746	I64AtomicRMWXchg32U = 0x47,
747	AtomicRMWOps_End = 0x47,
748
749	AtomicCmpxchgOps_Begin = 0x48,
750	I32AtomicCmpxchg = 0x48,
751	I64AtomicCmpxchg = 0x49,
752	I32AtomicCmpxchg8U = 0x4a,
753	I32AtomicCmpxchg16U = 0x4b,
754	I64AtomicCmpxchg8U = 0x4c,
755	I64AtomicCmpxchg16U = 0x4d,
756	I64AtomicCmpxchg32U = 0x4e,
757	AtomicCmpxchgOps_End = 0x4e,
758
759	// truncsat opcodes
760
761	I32STruncSatF32 = 0x00,
762	I32UTruncSatF32 = 0x01,
763	I32STruncSatF64 = 0x02,
764	I32UTruncSatF64 = 0x03,
765	I64STruncSatF32 = 0x04,
766	I64UTruncSatF32 = 0x05,
767	I64STruncSatF64 = 0x06,
768	I64UTruncSatF64 = 0x07,
769
770	// SIMD opcodes
771
772	V128Load = 0x00,
773	V128Load8x8S = 0x01,
774	V128Load8x8U = 0x02,
775	V128Load16x4S = 0x03,
776	V128Load16x4U = 0x04,
777	V128Load32x2S = 0x05,
778	V128Load32x2U = 0x06,
779	V128Load8Splat = 0x07,
780	V128Load16Splat = 0x08,
781	V128Load32Splat = 0x09,
782	V128Load64Splat = 0x0a,
783	V128Store = 0x0b,
784
785	V128Const = 0x0c,
786	I8x16Shuffle = 0x0d,
787	I8x16Swizzle = 0x0e,
788
789	I8x16Splat = 0x0f,
790	I16x8Splat = 0x10,
791	I32x4Splat = 0x11,
792	I64x2Splat = 0x12,
793	F32x4Splat = 0x13,
794	F64x2Splat = 0x14,
795
796	I8x16ExtractLaneS = 0x15,
797	I8x16ExtractLaneU = 0x16,
798	I8x16ReplaceLane = 0x17,
799	I16x8ExtractLaneS = 0x18,
800	I16x8ExtractLaneU = 0x19,
801	I16x8ReplaceLane = 0x1a,
802	I32x4ExtractLane = 0x1b,
803	I32x4ReplaceLane = 0x1c,
804	I64x2ExtractLane = 0x1d,
805	I64x2ReplaceLane = 0x1e,
806	F32x4ExtractLane = 0x1f,
807	F32x4ReplaceLane = 0x20,
808	F64x2ExtractLane = 0x21,
809	F64x2ReplaceLane = 0x22,
810
811	I8x16Eq = 0x23,
812	I8x16Ne = 0x24,
813	I8x16LtS = 0x25,
814	I8x16LtU = 0x26,
815	I8x16GtS = 0x27,
816	I8x16GtU = 0x28,
817	I8x16LeS = 0x29,
818	I8x16LeU = 0x2a,
819	I8x16GeS = 0x2b,
820	I8x16GeU = 0x2c,
821	I16x8Eq = 0x2d,
822	I16x8Ne = 0x2e,
823	I16x8LtS = 0x2f,
824	I16x8LtU = 0x30,
825	I16x8GtS = 0x31,
826	I16x8GtU = 0x32,
827	I16x8LeS = 0x33,
828	I16x8LeU = 0x34,
829	I16x8GeS = 0x35,
830	I16x8GeU = 0x36,
831	I32x4Eq = 0x37,
832	I32x4Ne = 0x38,
833	I32x4LtS = 0x39,
834	I32x4LtU = 0x3a,
835	I32x4GtS = 0x3b,
836	I32x4GtU = 0x3c,
837	I32x4LeS = 0x3d,
838	I32x4LeU = 0x3e,
839	I32x4GeS = 0x3f,
840	I32x4GeU = 0x40,
841	F32x4Eq = 0x41,
842	F32x4Ne = 0x42,
843	F32x4Lt = 0x43,
844	F32x4Gt = 0x44,
845	F32x4Le = 0x45,
846	F32x4Ge = 0x46,
847	F64x2Eq = 0x47,
848	F64x2Ne = 0x48,
849	F64x2Lt = 0x49,
850	F64x2Gt = 0x4a,
851	F64x2Le = 0x4b,
852	F64x2Ge = 0x4c,
853
854	V128Not = 0x4d,
855	V128And = 0x4e,
856	V128Andnot = 0x4f,
857	V128Or = 0x50,
858	V128Xor = 0x51,
859	V128Bitselect = 0x52,
860	V128AnyTrue = 0x53,
861
862	V128Load8Lane = 0x54,
863	V128Load16Lane = 0x55,
864	V128Load32Lane = 0x56,
865	V128Load64Lane = 0x57,
866	V128Store8Lane = 0x58,
867	V128Store16Lane = 0x59,
868	V128Store32Lane = 0x5a,
869	V128Store64Lane = 0x5b,
870	V128Load32Zero = 0x5c,
871	V128Load64Zero = 0x5d,
872
873	F32x4DemoteF64x2Zero = 0x5e,
874	F64x2PromoteLowF32x4 = 0x5f,
875
876	I8x16Abs = 0x60,
877	I8x16Neg = 0x61,
878	I8x16Popcnt = 0x62,
879	I8x16AllTrue = 0x63,
880	I8x16Bitmask = 0x64,
881	I8x16NarrowI16x8S = 0x65,
882	I8x16NarrowI16x8U = 0x66,
883	F32x4Ceil = 0x67,
884	F32x4Floor = 0x68,
885	F32x4Trunc = 0x69,
886	F32x4Nearest = 0x6a,
887	I8x16Shl = 0x6b,
888	I8x16ShrS = 0x6c,
889	I8x16ShrU = 0x6d,
890	I8x16Add = 0x6e,
891	I8x16AddSatS = 0x6f,
892	I8x16AddSatU = 0x70,
893	I8x16Sub = 0x71,
894	I8x16SubSatS = 0x72,
895	I8x16SubSatU = 0x73,
896	F64x2Ceil = 0x74,
897	F64x2Floor = 0x75,
898	I8x16MinS = 0x76,
899	I8x16MinU = 0x77,
900	I8x16MaxS = 0x78,
901	I8x16MaxU = 0x79,
902	F64x2Trunc = 0x7a,
903	I8x16AvgrU = 0x7b,
904	I16x8ExtaddPairwiseI8x16S = 0x7c,
905	I16x8ExtaddPairwiseI8x16U = 0x7d,
906	I32x4ExtaddPairwiseI16x8S = 0x7e,
907	I32x4ExtaddPairwiseI16x8U = 0x7f,
908
909	I16x8Abs = 0x80,
910	I16x8Neg = 0x81,
911	I16x8Q15MulrSatS = 0x82,
912	I16x8AllTrue = 0x83,
913	I16x8Bitmask = 0x84,
914	I16x8NarrowI32x4S = 0x85,
915	I16x8NarrowI32x4U = 0x86,
916	I16x8ExtendLowI8x16S = 0x87,
917	I16x8ExtendHighI8x16S = 0x88,
918	I16x8ExtendLowI8x16U = 0x89,
919	I16x8ExtendHighI8x16U = 0x8a,
920	I16x8Shl = 0x8b,
921	I16x8ShrS = 0x8c,
922	I16x8ShrU = 0x8d,
923	I16x8Add = 0x8e,
924	I16x8AddSatS = 0x8f,
925	I16x8AddSatU = 0x90,
926	I16x8Sub = 0x91,
927	I16x8SubSatS = 0x92,
928	I16x8SubSatU = 0x93,
929	F64x2Nearest = 0x94,
930	I16x8Mul = 0x95,
931	I16x8MinS = 0x96,
932	I16x8MinU = 0x97,
933	I16x8MaxS = 0x98,
934	I16x8MaxU = 0x99,
935	// 0x9a unused
936	I16x8AvgrU = 0x9b,
937	I16x8ExtmulLowI8x16S = 0x9c,
938	I16x8ExtmulHighI8x16S = 0x9d,
939	I16x8ExtmulLowI8x16U = 0x9e,
940	I16x8ExtmulHighI8x16U = 0x9f,
941
942	I32x4Abs = 0xa0,
943	I32x4Neg = 0xa1,
944	// 0xa2 unused
945	I32x4AllTrue = 0xa3,
946	I32x4Bitmask = 0xa4,
947	// 0xa5 unused
948	// 0xa6 unused
949	I32x4ExtendLowI16x8S = 0xa7,
950	I32x4ExtendHighI16x8S = 0xa8,
951	I32x4ExtendLowI16x8U = 0xa9,
952	I32x4ExtendHighI16x8U = 0xaa,
953	I32x4Shl = 0xab,
954	I32x4ShrS = 0xac,
955	I32x4ShrU = 0xad,
956	I32x4Add = 0xae,
957	// 0xaf unused
958	// 0xb0 unused
959	I32x4Sub = 0xb1,
960	// 0xb2 unused
961	// 0xb3 unused
962	// 0xb4 unused
963	I32x4Mul = 0xb5,
964	I32x4MinS = 0xb6,
965	I32x4MinU = 0xb7,
966	I32x4MaxS = 0xb8,
967	I32x4MaxU = 0xb9,
968	I32x4DotI16x8S = 0xba,
969	// 0xbb unused
970	I32x4ExtmulLowI16x8S = 0xbc,
971	I32x4ExtmulHighI16x8S = 0xbd,
972	I32x4ExtmulLowI16x8U = 0xbe,
973	I32x4ExtmulHighI16x8U = 0xbf,
974
975	I64x2Abs = 0xc0,
976	I64x2Neg = 0xc1,
977	// 0xc2 unused
978	I64x2AllTrue = 0xc3,
979	I64x2Bitmask = 0xc4,
980	// 0xc5 unused
981	// 0xc6 unused
982	I64x2ExtendLowI32x4S = 0xc7,
983	I64x2ExtendHighI32x4S = 0xc8,
984	I64x2ExtendLowI32x4U = 0xc9,
985	I64x2ExtendHighI32x4U = 0xca,
986	I64x2Shl = 0xcb,
987	I64x2ShrS = 0xcc,
988	I64x2ShrU = 0xcd,
989	I64x2Add = 0xce,
990	// 0xcf unused
991	// 0xd0 unused
992	I64x2Sub = 0xd1,
993	// 0xd2 unused
994	// 0xd3 unused
995	// 0xd4 unused
996	I64x2Mul = 0xd5,
997	I64x2Eq = 0xd6,
998	I64x2Ne = 0xd7,
999	I64x2LtS = 0xd8,
1000	I64x2GtS = 0xd9,
1001	I64x2LeS = 0xda,
1002	I64x2GeS = 0xdb,
1003	I64x2ExtmulLowI32x4S = 0xdc,
1004	I64x2ExtmulHighI32x4S = 0xdd,
1005	I64x2ExtmulLowI32x4U = 0xde,
1006	I64x2ExtmulHighI32x4U = 0xdf,
1007
1008	F32x4Abs = 0xe0,
1009	F32x4Neg = 0xe1,
1010	// 0xe2 unused
1011	F32x4Sqrt = 0xe3,
1012	F32x4Add = 0xe4,
1013	F32x4Sub = 0xe5,
1014	F32x4Mul = 0xe6,
1015	F32x4Div = 0xe7,
1016	F32x4Min = 0xe8,
1017	F32x4Max = 0xe9,
1018	F32x4Pmin = 0xea,
1019	F32x4Pmax = 0xeb,
1020
1021	F64x2Abs = 0xec,
1022	F64x2Neg = 0xed,
1023	// 0xee unused
1024	F64x2Sqrt = 0xef,
1025	F64x2Add = 0xf0,
1026	F64x2Sub = 0xf1,
1027	F64x2Mul = 0xf2,
1028	F64x2Div = 0xf3,
1029	F64x2Min = 0xf4,
1030	F64x2Max = 0xf5,
1031	F64x2Pmin = 0xf6,
1032	F64x2Pmax = 0xf7,
1033
1034	I32x4TruncSatF32x4S = 0xf8,
1035	I32x4TruncSatF32x4U = 0xf9,
1036	F32x4ConvertI32x4S = 0xfa,
1037	F32x4ConvertI32x4U = 0xfb,
1038	I32x4TruncSatF64x2SZero = 0xfc,
1039	I32x4TruncSatF64x2UZero = 0xfd,
1040	F64x2ConvertLowI32x4S = 0xfe,
1041	F64x2ConvertLowI32x4U = 0xff,
1042
1043	// relaxed SIMD opcodes
1044	I8x16RelaxedSwizzle = 0x100,
1045	I32x4RelaxedTruncF32x4S = 0x101,
1046	I32x4RelaxedTruncF32x4U = 0x102,
1047	I32x4RelaxedTruncF64x2SZero = 0x103,
1048	I32x4RelaxedTruncF64x2UZero = 0x104,
1049	F32x4RelaxedFma = 0x105,
1050	F32x4RelaxedFms = 0x106,
1051	F64x2RelaxedFma = 0x107,
1052	F64x2RelaxedFms = 0x108,
1053	I8x16Laneselect = 0x109,
1054	I16x8Laneselect = 0x10a,
1055	I32x4Laneselect = 0x10b,
1056	I64x2Laneselect = 0x10c,
1057	F32x4RelaxedMin = 0x10d,
1058	F32x4RelaxedMax = 0x10e,
1059	F64x2RelaxedMin = 0x10f,
1060	F64x2RelaxedMax = 0x110,
1061	I16x8RelaxedQ15MulrS = 0x111,
1062	I16x8DotI8x16I7x16S = 0x112,
1063	I32x4DotI8x16I7x16AddS = 0x113,
1064
1065	// bulk memory opcodes
1066
1067	MemoryInit = 0x08,
1068	DataDrop = 0x09,
1069	MemoryCopy = 0x0a,
1070	MemoryFill = 0x0b,
1071
1072	// reference types opcodes
1073
1074	TableGrow = 0x0f,
1075	TableSize = 0x10,
1076	RefNull = 0xd0,
1077	RefIsNull = 0xd1,
1078	RefFunc = 0xd2,
1079	RefAsNonNull = 0xd3,
1080	BrOnNull = 0xd4,
1081	BrOnNonNull = 0xd6,
1082
1083	// exception handling opcodes
1084
1085	Try = 0x06,
1086	Catch = 0x07,
1087	CatchAll = 0x19,
1088	Delegate = 0x18,
1089	Throw = 0x08,
1090	Rethrow = 0x09,
1091
1092	// typed function references opcodes
1093
1094	CallRef = 0x14,
1095	RetCallRef = 0x15,
1096
1097	// gc opcodes
1098
1099	RefEq = 0xd5,
1100	StructGet = 0x03,
1101	StructGetS = 0x04,
1102	StructGetU = 0x05,
1103	StructSet = 0x06,
1104	StructNew = 0x07,
1105	StructNewDefault = 0x08,
1106	ArrayNewElem = 0x10,
1107	ArrayGet = 0x13,
1108	ArrayGetS = 0x14,
1109	ArrayGetU = 0x15,
1110	ArraySet = 0x16,
1111	ArrayLenAnnotated = 0x17,
1112	ArrayCopy = 0x18,
1113	ArrayLen = 0x19,
1114	ArrayNewFixed = 0x1a,
1115	ArrayNew = 0x1b,
1116	ArrayNewDefault = 0x1c,
1117	ArrayNewData = 0x1d,
1118	I31New = 0x20,
1119	I31GetS = 0x21,
1120	I31GetU = 0x22,
1121	RefTest = 0x40,
1122	RefCast = 0x41,
1123	BrOnCastLegacy = 0x42,
1124	BrOnCastFailLegacy = 0x43,
1125	BrOnCastNullLegacy = 0x4a,
1126	BrOnCastFailNullLegacy = 0x4b,
1127	BrOnCast = 0x4e,
1128	BrOnCastFail = 0x4f,
1129	RefTestStatic = 0x44,
1130	RefCastStatic = 0x45,
1131	RefTestNull = 0x48,
1132	RefCastNull = 0x49,
1133	RefCastNop = 0x4c,
1134	RefAsFunc = 0x58,
1135	RefAsI31 = 0x5a,
1136	BrOnFunc = 0x60,
1137	BrOnI31 = 0x62,
1138	BrOnNonFunc = 0x63,
1139	BrOnNonI31 = 0x65,
1140	ExternInternalize = 0x70,
1141	ExternExternalize = 0x71,
1142	ArrayFill = 0x0f,
1143	ArrayInitData = 0x54,
1144	ArrayInitElem = 0x55,
1145	StringNewUTF8 = 0x80,
1146	StringNewWTF16 = 0x81,
1147	StringConst = 0x82,
1148	StringMeasureUTF8 = 0x83,
1149	StringMeasureWTF8 = 0x84,
1150	StringMeasureWTF16 = 0x85,
1151	StringEncodeUTF8 = 0x86,
1152	StringEncodeWTF16 = 0x87,
1153	StringConcat = 0x88,
1154	StringEq = 0x89,
1155	StringIsUSV = 0x8a,
1156	StringNewLossyUTF8 = 0x8b,
1157	StringNewWTF8 = 0x8c,
1158	StringEncodeLossyUTF8 = 0x8d,
1159	StringEncodeWTF8 = 0x8e,
1160	StringNewUTF8Try = 0x8f,
1161	StringAsWTF8 = 0x90,
1162	StringViewWTF8Advance = 0x91,
1163	StringViewWTF8Slice = 0x93,
1164	StringAsWTF16 = 0x98,
1165	StringViewWTF16Length = 0x99,
1166	StringViewWTF16GetCodePoint = 0x9a,
1167	StringViewWTF16Slice = 0x9c,
1168	StringAsIter = 0xa0,
1169	StringViewIterNext = 0xa1,
1170	StringViewIterAdvance = 0xa2,
1171	StringViewIterRewind = 0xa3,
1172	StringViewIterSlice = 0xa4,
1173	StringCompare = 0xa8,
1174	StringFromCodePoint = 0xa9,
1175	StringHash = 0xaa,
1176	StringNewUTF8Array = 0xb0,
1177	StringNewWTF16Array = 0xb1,
1178	StringEncodeUTF8Array = 0xb2,
1179	StringEncodeWTF16Array = 0xb3,
1180	StringNewLossyUTF8Array = 0xb4,
1181	StringNewWTF8Array = 0xb5,
1182	StringEncodeLossyUTF8Array = 0xb6,
1183	StringEncodeWTF8Array = 0xb7,
1184	StringNewUTF8ArrayTry = 0xb8,
1185	};
1186
1187	enum MemoryAccess {
1188	Offset = 0x10, // bit 4
1189	Alignment = 0x80, // bit 7
1190	NaturalAlignment = 0
1191	};
1192
1193	enum MemoryFlags { HasMaximum = 1 << 0, IsShared = 1 << 1, Is64 = 1 << 2 };
1194
1195	enum FeaturePrefix {
1196	FeatureUsed = '+',
1197	FeatureRequired = '=',
1198	FeatureDisallowed = '-'
1199	};
1200
1201	} // namespace BinaryConsts
1202
1203	// (local index in IR, tuple index) => binary local index
1204	using MappedLocals = std::unordered_map<std::pair<Index, Index>, size_t>;
1205
1206	// Writes out wasm to the binary format
1207
1208	class WasmBinaryWriter {
1209	// Computes the indexes in a wasm binary, i.e., with function imports
1210	// and function implementations sharing a single index space, etc.,
1211	// and with the imports first (the Module's functions and globals
1212	// arrays are not assumed to be in a particular order, so we can't
1213	// just use them directly).
1214	struct BinaryIndexes {
1215	std::unordered_map<Name, Index> functionIndexes;
1216	std::unordered_map<Name, Index> tagIndexes;
1217	std::unordered_map<Name, Index> globalIndexes;
1218	std::unordered_map<Name, Index> tableIndexes;
1219	std::unordered_map<Name, Index> elemIndexes;
1220	std::unordered_map<Name, Index> memoryIndexes;
1221	std::unordered_map<Name, Index> dataIndexes;
1222
1223	BinaryIndexes(Module& wasm) {
1224	auto addIndexes = [&](auto& source, auto& indexes) {
1225	auto addIndex = [&](auto* curr) {
1226	auto index = indexes.size();
1227	indexes[curr->name] = index;
1228	};
1229	for (auto& curr : source) {
1230	if (curr->imported()) {
1231	addIndex(curr.get());
1232	}
1233	}
1234	for (auto& curr : source) {
1235	if (!curr->imported()) {
1236	addIndex(curr.get());
1237	}
1238	}
1239	};
1240	addIndexes(wasm.functions, functionIndexes);
1241	addIndexes(wasm.tags, tagIndexes);
1242	addIndexes(wasm.tables, tableIndexes);
1243	addIndexes(wasm.memories, memoryIndexes);
1244
1245	for (auto& curr : wasm.elementSegments) {
1246	auto index = elemIndexes.size();
1247	elemIndexes[curr->name] = index;
1248	}
1249
1250	for (auto& curr : wasm.dataSegments) {
1251	auto index = dataIndexes.size();
1252	dataIndexes[curr->name] = index;
1253	}
1254
1255	// Globals may have tuple types in the IR, in which case they lower to
1256	// multiple globals, one for each tuple element, in the binary. Tuple
1257	// globals therefore occupy multiple binary indices, and we have to take
1258	// that into account when calculating indices.
1259	Index globalCount = 0;
1260	auto addGlobal = [&](auto* curr) {
1261	globalIndexes[curr->name] = globalCount;
1262	globalCount += curr->type.size();
1263	};
1264	for (auto& curr : wasm.globals) {
1265	if (curr->imported()) {
1266	addGlobal(curr.get());
1267	}
1268	}
1269	for (auto& curr : wasm.globals) {
1270	if (!curr->imported()) {
1271	addGlobal(curr.get());
1272	}
1273	}
1274	}
1275	};
1276
1277	public:
1278	WasmBinaryWriter(Module* input, BufferWithRandomAccess& o)
1279	: wasm(input), o(o), indexes(*input) {
1280	prepare();
1281	}
1282
1283	// locations in the output binary for the various parts of the module
1284	struct TableOfContents {
1285	struct Entry {
1286	Name name;
1287	size_t offset; // where the entry starts
1288	size_t size; // the size of the entry
1289	Entry(Name name, size_t offset, size_t size)
1290	: name(name), offset(offset), size(size) {}
1291	};
1292	std::vector<Entry> functionBodies;
1293	} tableOfContents;
1294
1295	void setNamesSection(bool set) {
1296	debugInfo = set;
1297	emitModuleName = set;
1298	}
1299	void setEmitModuleName(bool set) { emitModuleName = set; }
1300	void setSourceMap(std::ostream* set, std::string url) {
1301	sourceMap = set;
1302	sourceMapUrl = url;
1303	}
1304	void setSymbolMap(std::string set) { symbolMap = set; }
1305
1306	void write();
1307	void writeHeader();
1308	int32_t writeU32LEBPlaceholder();
1309	void writeResizableLimits(
1310	Address initial, Address maximum, bool hasMaximum, bool shared, bool is64);
1311	template<typename T> int32_t startSection(T code);
1312	void finishSection(int32_t start);
1313	int32_t startSubsection(BinaryConsts::CustomSections::Subsection code);
1314	void finishSubsection(int32_t start);
1315	void writeStart();
1316	void writeMemories();
1317	void writeTypes();
1318	void writeImports();
1319
1320	void writeFunctionSignatures();
1321	void writeExpression(Expression* curr);
1322	void writeFunctions();
1323	void writeStrings();
1324	void writeGlobals();
1325	void writeExports();
1326	void writeDataCount();
1327	void writeDataSegments();
1328	void writeTags();
1329
1330	uint32_t getFunctionIndex(Name name) const;
1331	uint32_t getTableIndex(Name name) const;
1332	uint32_t getMemoryIndex(Name name) const;
1333	uint32_t getGlobalIndex(Name name) const;
1334	uint32_t getTagIndex(Name name) const;
1335	uint32_t getDataSegmentIndex(Name name) const;
1336	uint32_t getElementSegmentIndex(Name name) const;
1337	uint32_t getTypeIndex(HeapType type) const;
1338	uint32_t getStringIndex(Name string) const;
1339
1340	void writeTableDeclarations();
1341	void writeElementSegments();
1342	void writeNames();
1343	void writeSourceMapUrl();
1344	void writeSymbolMap();
1345	void writeLateCustomSections();
1346	void writeCustomSection(const CustomSection& section);
1347	void writeFeaturesSection();
1348	void writeDylinkSection();
1349	void writeLegacyDylinkSection();
1350
1351	void initializeDebugInfo();
1352	void writeSourceMapProlog();
1353	void writeSourceMapEpilog();
1354	void writeDebugLocation(const Function::DebugLocation& loc);
1355	void writeDebugLocation(Expression* curr, Function* func);
1356	void writeDebugLocationEnd(Expression* curr, Function* func);
1357	void writeExtraDebugLocation(Expression* curr, Function* func, size_t id);
1358
1359	// helpers
1360	void writeInlineString(std::string_view name);
1361	void writeEscapedName(std::string_view name);
1362	void writeInlineBuffer(const char* data, size_t size);
1363	void writeData(const char* data, size_t size);
1364
1365	struct Buffer {
1366	const char* data;
1367	size_t size;
1368	size_t pointerLocation;
1369	Buffer(const char* data, size_t size, size_t pointerLocation)
1370	: data(data), size(size), pointerLocation(pointerLocation) {}
1371	};
1372
1373	Module* getModule() { return wasm; }
1374
1375	void writeType(Type type);
1376
1377	// Writes an arbitrary heap type, which may be indexed or one of the
1378	// basic types like funcref.
1379	void writeHeapType(HeapType type);
1380	// Writes an indexed heap type. Note that this is encoded differently than a
1381	// general heap type because it does not allow negative values for basic heap
1382	// types.
1383	void writeIndexedHeapType(HeapType type);
1384
1385	void writeField(const Field& field);
1386
1387	private:
1388	Module* wasm;
1389	BufferWithRandomAccess& o;
1390	BinaryIndexes indexes;
1391	ModuleUtils::IndexedHeapTypes indexedTypes;
1392
1393	bool debugInfo = true;
1394
1395	// TODO: Remove `emitModuleName` in the future once there are better ways to
1396	// ensure modules have meaningful names in stack traces.For example, using
1397	// ObjectURLs works in FireFox, but not Chrome. See
1398	// https://bugs.chromium.org/p/v8/issues/detail?id=11808.
1399	bool emitModuleName = true;
1400
1401	std::ostream* sourceMap = nullptr;
1402	std::string sourceMapUrl;
1403	std::string symbolMap;
1404
1405	MixedArena allocator;
1406
1407	// storage of source map locations until the section is placed at its final
1408	// location (shrinking LEBs may cause changes there)
1409	std::vector<std::pair<size_t, const Function::DebugLocation*>>
1410	sourceMapLocations;
1411	size_t sourceMapLocationsSizeAtSectionStart;
1412	Function::DebugLocation lastDebugLocation;
1413
1414	std::unique_ptr<ImportInfo> importInfo;
1415
1416	// General debugging info: track locations as we write.
1417	BinaryLocations binaryLocations;
1418	size_t binaryLocationsSizeAtSectionStart;
1419	// Track the expressions that we added for the current function being
1420	// written, so that we can update those specific binary locations when
1421	// the function is written out.
1422	std::vector<Expression*> binaryLocationTrackedExpressionsForFunc;
1423
1424	// Maps function names to their mapped locals. This is used when we emit the
1425	// local names section: we map the locals when writing the function, save that
1426	// info here, and then use it when writing the names.
1427	std::unordered_map<Name, MappedLocals> funcMappedLocals;
1428
1429	// Indexes in the string literal section of each StringConst in the wasm.
1430	std::unordered_map<Name, Index> stringIndexes;
1431
1432	void prepare();
1433	};
1434
1435	class WasmBinaryReader {
1436	Module& wasm;
1437	MixedArena& allocator;
1438	const std::vector<char>& input;
1439	std::istream* sourceMap;
1440	struct NextDebugLocation {
1441	uint32_t availablePos;
1442	uint32_t previousPos;
1443	Function::DebugLocation next;
1444	};
1445	NextDebugLocation nextDebugLocation;
1446	bool debugInfo = true;
1447	bool DWARF = false;
1448	bool skipFunctionBodies = false;
1449
1450	size_t pos = 0;
1451	Index startIndex = -1;
1452	std::set<Function::DebugLocation> debugLocation;
1453	size_t codeSectionLocation;
1454
1455	std::set<BinaryConsts::Section> seenSections;
1456
1457	// All types defined in the type section
1458	std::vector<HeapType> types;
1459
1460	public:
1461	WasmBinaryReader(Module& wasm,
1462	FeatureSet features,
1463	const std::vector<char>& input);
1464
1465	void setDebugInfo(bool value) { debugInfo = value; }
1466	void setDWARF(bool value) { DWARF = value; }
1467	void setSkipFunctionBodies(bool skipFunctionBodies_) {
1468	skipFunctionBodies = skipFunctionBodies_;
1469	}
1470	void read();
1471	void readCustomSection(size_t payloadLen);
1472
1473	bool more() { return pos < input.size(); }
1474
1475	std::string_view getByteView(size_t size);
1476	uint8_t getInt8();
1477	uint16_t getInt16();
1478	uint32_t getInt32();
1479	uint64_t getInt64();
1480	uint8_t getLaneIndex(size_t lanes);
1481	// it is unsafe to return a float directly, due to ABI issues with the
1482	// signalling bit
1483	Literal getFloat32Literal();
1484	Literal getFloat64Literal();
1485	Literal getVec128Literal();
1486	uint32_t getU32LEB();
1487	uint64_t getU64LEB();
1488	int32_t getS32LEB();
1489	int64_t getS64LEB();
1490	uint64_t getUPtrLEB();
1491
1492	bool getBasicType(int32_t code, Type& out);
1493	bool getBasicHeapType(int64_t code, HeapType& out);
1494	// Read a value and get a type for it.
1495	Type getType();
1496	// Get a type given the initial S32LEB has already been read, and is provided.
1497	Type getType(int initial);
1498	HeapType getHeapType();
1499	HeapType getIndexedHeapType();
1500
1501	Type getConcreteType();
1502	Name getInlineString();
1503	void verifyInt8(int8_t x);
1504	void verifyInt16(int16_t x);
1505	void verifyInt32(int32_t x);
1506	void verifyInt64(int64_t x);
1507	void readHeader();
1508	void readStart();
1509	void readMemories();
1510	void readTypes();
1511
1512	// gets a name in the combined import+defined space
1513	Name getFunctionName(Index index);
1514	Name getTableName(Index index);
1515	Name getMemoryName(Index index);
1516	Name getGlobalName(Index index);
1517	Name getTagName(Index index);
1518	Name getDataName(Index index);
1519	Name getElemName(Index index);
1520
1521	// gets a memory in the combined import+defined space
1522	Memory* getMemory(Index index);
1523
1524	void getResizableLimits(Address& initial,
1525	Address& max,
1526	bool& shared,
1527	Type& indexType,
1528	Address defaultIfNoMax);
1529	void readImports();
1530
1531	// The signatures of each function, including imported functions, given in the
1532	// import and function sections. Store HeapTypes instead of Signatures because
1533	// reconstructing the HeapTypes from the Signatures is expensive.
1534	std::vector<HeapType> functionTypes;
1535
1536	void readFunctionSignatures();
1537	HeapType getTypeByIndex(Index index);
1538	HeapType getTypeByFunctionIndex(Index index);
1539	Signature getSignatureByTypeIndex(Index index);
1540	Signature getSignatureByFunctionIndex(Index index);
1541
1542	size_t nextLabel;
1543
1544	Name getNextLabel();
1545
1546	// We read functions and globals before we know their names, so we need to
1547	// backpatch the names later
1548
1549	// at index i we have all refs to the function i
1550	std::map<Index, std::vector<Name*>> functionRefs;
1551	Function* currFunction = nullptr;
1552	// before we see a function (like global init expressions), there is no end of
1553	// function to check
1554	Index endOfFunction = -1;
1555
1556	// at index i we have all references to the table i
1557	std::map<Index, std::vector<Name*>> tableRefs;
1558
1559	std::map<Index, Name> elemTables;
1560
1561	// at index i we have all references to the memory i
1562	std::map<Index, std::vector<wasm::Name*>> memoryRefs;
1563
1564	// at index i we have all refs to the global i
1565	std::map<Index, std::vector<Name*>> globalRefs;
1566
1567	// at index i we have all refs to the tag i
1568	std::map<Index, std::vector<Name*>> tagRefs;
1569
1570	// at index i we have all refs to the data segment i
1571	std::map<Index, std::vector<Name*>> dataRefs;
1572
1573	// at index i we have all refs to the element segment i
1574	std::map<Index, std::vector<Name*>> elemRefs;
1575
1576	// Throws a parsing error if we are not in a function context
1577	void requireFunctionContext(const char* error);
1578
1579	void readFunctions();
1580	void readVars();
1581
1582	std::map<Export*, Index> exportIndices;
1583	std::vector<Export*> exportOrder;
1584	void readExports();
1585
1586	// The strings in the strings section (which are referred to by StringConst).
1587	std::vector<Name> strings;
1588	void readStrings();
1589
1590	Expression* readExpression();
1591	void readGlobals();
1592
1593	struct BreakTarget {
1594	Name name;
1595	Type type;
1596	BreakTarget(Name name, Type type) : name(name), type(type) {}
1597	};
1598	std::vector<BreakTarget> breakStack;
1599	// the names that breaks target. this lets us know if a block has breaks to it
1600	// or not.
1601	std::unordered_set<Name> breakTargetNames;
1602	// the names that delegates target.
1603	std::unordered_set<Name> exceptionTargetNames;
1604
1605	std::vector<Expression*> expressionStack;
1606
1607	// Control flow structure parsing: these have not just the normal binary
1608	// data for an instruction, but also some bytes later on like "end" or "else".
1609	// We must be aware of the connection between those things, for debug info.
1610	std::vector<Expression*> controlFlowStack;
1611
1612	// Called when we parse the beginning of a control flow structure.
1613	void startControlFlow(Expression* curr);
1614
1615	// set when we know code is unreachable in the sense of the wasm spec: we are
1616	// in a block and after an unreachable element. this helps parse stacky wasm
1617	// code, which can be unsuitable for our IR when unreachable.
1618	bool unreachableInTheWasmSense;
1619
1620	// set when the current code being processed will not be emitted in the
1621	// output, which is the case when it is literally unreachable, for example,
1622	// (block $a
1623	// (unreachable)
1624	// (block $b
1625	// ;; code here is reachable in the wasm sense, even though $b as a whole
1626	// ;; is not
1627	// (unreachable)
1628	// ;; code here is unreachable in the wasm sense
1629	// )
1630	// )
1631	bool willBeIgnored;
1632
1633	BinaryConsts::ASTNodes lastSeparator = BinaryConsts::End;
1634
1635	// process a block-type scope, until an end or else marker, or the end of the
1636	// function
1637	void processExpressions();
1638	void skipUnreachableCode();
1639
1640	void pushExpression(Expression* curr);
1641	Expression* popExpression();
1642	Expression* popNonVoidExpression();
1643	Expression* popTuple(size_t numElems);
1644	Expression* popTypedExpression(Type type);
1645
1646	void validateBinary(); // validations that cannot be performed on the Module
1647	void processNames();
1648
1649	size_t dataCount = 0;
1650	bool hasDataCount = false;
1651
1652	void readDataSegments();
1653	void readDataSegmentCount();
1654
1655	void readTableDeclarations();
1656	void readElementSegments();
1657
1658	void readTags();
1659
1660	static Name escape(Name name);
1661	void readNames(size_t);
1662	void readFeatures(size_t);
1663	void readDylink(size_t);
1664	void readDylink0(size_t);
1665
1666	// Debug information reading helpers
1667	void setDebugLocations(std::istream* sourceMap_) { sourceMap = sourceMap_; }
1668	std::unordered_map<std::string, Index> debugInfoFileIndices;
1669	void readNextDebugLocation();
1670	void readSourceMapHeader();
1671
1672	// AST reading
1673	int depth = 0; // only for debugging
1674
1675	BinaryConsts::ASTNodes readExpression(Expression*& curr);
1676	void pushBlockElements(Block* curr, Type type, size_t start);
1677	void visitBlock(Block* curr);
1678
1679	// Gets a block of expressions. If it's just one, return that singleton.
1680	Expression* getBlockOrSingleton(Type type);
1681
1682	BreakTarget getBreakTarget(int32_t offset);
1683	Name getExceptionTargetName(int32_t offset);
1684
1685	Index readMemoryAccess(Address& alignment, Address& offset);
1686
1687	void visitIf(If* curr);
1688	void visitLoop(Loop* curr);
1689	void visitBreak(Break* curr, uint8_t code);
1690	void visitSwitch(Switch* curr);
1691	void visitCall(Call* curr);
1692	void visitCallIndirect(CallIndirect* curr);
1693	void visitLocalGet(LocalGet* curr);
1694	void visitLocalSet(LocalSet* curr, uint8_t code);
1695	void visitGlobalGet(GlobalGet* curr);
1696	void visitGlobalSet(GlobalSet* curr);
1697	bool maybeVisitLoad(Expression*& out, uint8_t code, bool isAtomic);
1698	bool maybeVisitStore(Expression*& out, uint8_t code, bool isAtomic);
1699	bool maybeVisitNontrappingTrunc(Expression*& out, uint32_t code);
1700	bool maybeVisitAtomicRMW(Expression*& out, uint8_t code);
1701	bool maybeVisitAtomicCmpxchg(Expression*& out, uint8_t code);
1702	bool maybeVisitAtomicWait(Expression*& out, uint8_t code);
1703	bool maybeVisitAtomicNotify(Expression*& out, uint8_t code);
1704	bool maybeVisitAtomicFence(Expression*& out, uint8_t code);
1705	bool maybeVisitConst(Expression*& out, uint8_t code);
1706	bool maybeVisitUnary(Expression*& out, uint8_t code);
1707	bool maybeVisitBinary(Expression*& out, uint8_t code);
1708	bool maybeVisitTruncSat(Expression*& out, uint32_t code);
1709	bool maybeVisitSIMDBinary(Expression*& out, uint32_t code);
1710	bool maybeVisitSIMDUnary(Expression*& out, uint32_t code);
1711	bool maybeVisitSIMDConst(Expression*& out, uint32_t code);
1712	bool maybeVisitSIMDStore(Expression*& out, uint32_t code);
1713	bool maybeVisitSIMDExtract(Expression*& out, uint32_t code);
1714	bool maybeVisitSIMDReplace(Expression*& out, uint32_t code);
1715	bool maybeVisitSIMDShuffle(Expression*& out, uint32_t code);
1716	bool maybeVisitSIMDTernary(Expression*& out, uint32_t code);
1717	bool maybeVisitSIMDShift(Expression*& out, uint32_t code);
1718	bool maybeVisitSIMDLoad(Expression*& out, uint32_t code);
1719	bool maybeVisitSIMDLoadStoreLane(Expression*& out, uint32_t code);
1720	bool maybeVisitMemoryInit(Expression*& out, uint32_t code);
1721	bool maybeVisitDataDrop(Expression*& out, uint32_t code);
1722	bool maybeVisitMemoryCopy(Expression*& out, uint32_t code);
1723	bool maybeVisitMemoryFill(Expression*& out, uint32_t code);
1724	bool maybeVisitTableSize(Expression*& out, uint32_t code);
1725	bool maybeVisitTableGrow(Expression*& out, uint32_t code);
1726	bool maybeVisitI31New(Expression*& out, uint32_t code);
1727	bool maybeVisitI31Get(Expression*& out, uint32_t code);
1728	bool maybeVisitRefTest(Expression*& out, uint32_t code);
1729	bool maybeVisitRefCast(Expression*& out, uint32_t code);
1730	bool maybeVisitBrOn(Expression*& out, uint32_t code);
1731	bool maybeVisitStructNew(Expression*& out, uint32_t code);
1732	bool maybeVisitStructGet(Expression*& out, uint32_t code);
1733	bool maybeVisitStructSet(Expression*& out, uint32_t code);
1734	bool maybeVisitArrayNewData(Expression*& out, uint32_t code);
1735	bool maybeVisitArrayNewElem(Expression*& out, uint32_t code);
1736	bool maybeVisitArrayNewFixed(Expression*& out, uint32_t code);
1737	bool maybeVisitArrayGet(Expression*& out, uint32_t code);
1738	bool maybeVisitArraySet(Expression*& out, uint32_t code);
1739	bool maybeVisitArrayLen(Expression*& out, uint32_t code);
1740	bool maybeVisitArrayCopy(Expression*& out, uint32_t code);
1741	bool maybeVisitArrayFill(Expression*& out, uint32_t code);
1742	bool maybeVisitArrayInit(Expression*& out, uint32_t code);
1743	bool maybeVisitStringNew(Expression*& out, uint32_t code);
1744	bool maybeVisitStringConst(Expression*& out, uint32_t code);
1745	bool maybeVisitStringMeasure(Expression*& out, uint32_t code);
1746	bool maybeVisitStringEncode(Expression*& out, uint32_t code);
1747	bool maybeVisitStringConcat(Expression*& out, uint32_t code);
1748	bool maybeVisitStringEq(Expression*& out, uint32_t code);
1749	bool maybeVisitStringAs(Expression*& out, uint32_t code);
1750	bool maybeVisitStringWTF8Advance(Expression*& out, uint32_t code);
1751	bool maybeVisitStringWTF16Get(Expression*& out, uint32_t code);
1752	bool maybeVisitStringIterNext(Expression*& out, uint32_t code);
1753	bool maybeVisitStringIterMove(Expression*& out, uint32_t code);
1754	bool maybeVisitStringSliceWTF(Expression*& out, uint32_t code);
1755	bool maybeVisitStringSliceIter(Expression*& out, uint32_t code);
1756	void visitSelect(Select* curr, uint8_t code);
1757	void visitReturn(Return* curr);
1758	void visitMemorySize(MemorySize* curr);
1759	void visitMemoryGrow(MemoryGrow* curr);
1760	void visitNop(Nop* curr);
1761	void visitUnreachable(Unreachable* curr);
1762	void visitDrop(Drop* curr);
1763	void visitRefNull(RefNull* curr);
1764	void visitRefIsNull(RefIsNull* curr);
1765	void visitRefFunc(RefFunc* curr);
1766	void visitRefEq(RefEq* curr);
1767	void visitTableGet(TableGet* curr);
1768	void visitTableSet(TableSet* curr);
1769	void visitTryOrTryInBlock(Expression*& out);
1770	void visitThrow(Throw* curr);
1771	void visitRethrow(Rethrow* curr);
1772	void visitCallRef(CallRef* curr);
1773	void visitRefAsCast(RefCast* curr, uint32_t code);
1774	void visitRefAs(RefAs* curr, uint8_t code);
1775
1776	[[noreturn]] void throwError(std::string text);
1777
1778	// Struct/Array instructions have an unnecessary heap type that is just for
1779	// validation (except for the case of unreachability, but that's not a problem
1780	// anyhow, we can ignore it there). That is, we also have a reference typed
1781	// child from which we can infer the type anyhow, and we just need to check
1782	// that type is the same.
1783	void validateHeapTypeUsingChild(Expression* child, HeapType heapType);
1784
1785	private:
1786	bool hasDWARFSections();
1787	};
1788
1789	} // namespace wasm
1790
1791	#undef DEBUG_TYPE
1792
1793	#endif // wasm_wasm_binary_h
1794