1	//
2	// Copyright (C) 2015 LunarG, Inc.
3	//
4	// All rights reserved.
5	//
6	// Redistribution and use in source and binary forms, with or without
7	// modification, are permitted provided that the following conditions
8	// are met:
9	//
10	// Redistributions of source code must retain the above copyright
11	// notice, this list of conditions and the following disclaimer.
12	//
13	// Redistributions in binary form must reproduce the above
14	// copyright notice, this list of conditions and the following
15	// disclaimer in the documentation and/or other materials provided
16	// with the distribution.
17	//
18	// Neither the name of 3Dlabs Inc. Ltd. nor the names of its
19	// contributors may be used to endorse or promote products derived
20	// from this software without specific prior written permission.
21	//
22	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23	// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24	// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25	// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26	// COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27	// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28	// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29	// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30	// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31	// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32	// ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33	// POSSIBILITY OF SUCH DAMAGE.
34	//
35
36	#include "SPVRemapper.h"
37	#include "doc.h"
38
39	#include <algorithm>
40	#include <cassert>
41
42	namespace spv {
43
44	// By default, just abort on error. Can be overridden via RegisterErrorHandler
45	spirvbin_t::errorfn_t spirvbin_t::errorHandler = [](const std::string&) { exit(status: 5); };
46	// By default, eat log messages. Can be overridden via RegisterLogHandler
47	spirvbin_t::logfn_t spirvbin_t::logHandler = [](const std::string&) { };
48
49	// This can be overridden to provide other message behavior if needed
50	void spirvbin_t::msg(int minVerbosity, int indent, const std::string& txt) const
51	{
52	if (verbose >= minVerbosity)
53	logHandler(std::string(indent, ' ') + txt);
54	}
55
56	// hash opcode, with special handling for OpExtInst
57	std::uint32_t spirvbin_t::asOpCodeHash(unsigned word)
58	{
59	const spv::Op opCode = asOpCode(word);
60
61	std::uint32_t offset = 0;
62
63	switch (opCode) {
64	case spv::OpExtInst:
65	offset += asId(word: word + 4); break;
66	default:
67	break;
68	}
69
70	return opCode * 19 + offset; // 19 = small prime
71	}
72
73	spirvbin_t::range_t spirvbin_t::literalRange(spv::Op opCode) const
74	{
75	static const int maxCount = 1<<30;
76
77	switch (opCode) {
78	case spv::OpTypeFloat: // fall through...
79	case spv::OpTypePointer: return range_t(2, 3);
80	case spv::OpTypeInt: return range_t(2, 4);
81	// TODO: case spv::OpTypeImage:
82	// TODO: case spv::OpTypeSampledImage:
83	case spv::OpTypeSampler: return range_t(3, 8);
84	case spv::OpTypeVector: // fall through
85	case spv::OpTypeMatrix: // ...
86	case spv::OpTypePipe: return range_t(3, 4);
87	case spv::OpConstant: return range_t(3, maxCount);
88	default: return range_t(0, 0);
89	}
90	}
91
92	spirvbin_t::range_t spirvbin_t::typeRange(spv::Op opCode) const
93	{
94	static const int maxCount = 1<<30;
95
96	if (isConstOp(opCode))
97	return range_t(1, 2);
98
99	switch (opCode) {
100	case spv::OpTypeVector: // fall through
101	case spv::OpTypeMatrix: // ...
102	case spv::OpTypeSampler: // ...
103	case spv::OpTypeArray: // ...
104	case spv::OpTypeRuntimeArray: // ...
105	case spv::OpTypePipe: return range_t(2, 3);
106	case spv::OpTypeStruct: // fall through
107	case spv::OpTypeFunction: return range_t(2, maxCount);
108	case spv::OpTypePointer: return range_t(3, 4);
109	default: return range_t(0, 0);
110	}
111	}
112
113	spirvbin_t::range_t spirvbin_t::constRange(spv::Op opCode) const
114	{
115	static const int maxCount = 1<<30;
116
117	switch (opCode) {
118	case spv::OpTypeArray: // fall through...
119	case spv::OpTypeRuntimeArray: return range_t(3, 4);
120	case spv::OpConstantComposite: return range_t(3, maxCount);
121	default: return range_t(0, 0);
122	}
123	}
124
125	// Return the size of a type in 32-bit words. This currently only
126	// handles ints and floats, and is only invoked by queries which must be
127	// integer types. If ever needed, it can be generalized.
128	unsigned spirvbin_t::typeSizeInWords(spv::Id id) const
129	{
130	const unsigned typeStart = idPos(id);
131	const spv::Op opCode = asOpCode(word: typeStart);
132
133	if (errorLatch)
134	return 0;
135
136	switch (opCode) {
137	case spv::OpTypeInt: // fall through...
138	case spv::OpTypeFloat: return (spv[typeStart+2]+31)/32;
139	default:
140	return 0;
141	}
142	}
143
144	// Looks up the type of a given const or variable ID, and
145	// returns its size in 32-bit words.
146	unsigned spirvbin_t::idTypeSizeInWords(spv::Id id) const
147	{
148	const auto tid_it = idTypeSizeMap.find(x: id);
149	if (tid_it == idTypeSizeMap.end()) {
150	error(txt: "type size for ID not found");
151	return 0;
152	}
153
154	return tid_it->second;
155	}
156
157	// Is this an opcode we should remove when using --strip?
158	bool spirvbin_t::isStripOp(spv::Op opCode, unsigned start) const
159	{
160	switch (opCode) {
161	case spv::OpSource:
162	case spv::OpSourceExtension:
163	case spv::OpName:
164	case spv::OpMemberName:
165	case spv::OpLine :
166	{
167	const std::string name = literalString(word: start + 2);
168
169	std::vector<std::string>::const_iterator it;
170	for (it = stripWhiteList.begin(); it < stripWhiteList.end(); it++)
171	{
172	if (name.find(str: *it) != std::string::npos) {
173	return false;
174	}
175	}
176
177	return true;
178	}
179	default :
180	return false;
181	}
182	}
183
184	// Return true if this opcode is flow control
185	bool spirvbin_t::isFlowCtrl(spv::Op opCode) const
186	{
187	switch (opCode) {
188	case spv::OpBranchConditional:
189	case spv::OpBranch:
190	case spv::OpSwitch:
191	case spv::OpLoopMerge:
192	case spv::OpSelectionMerge:
193	case spv::OpLabel:
194	case spv::OpFunction:
195	case spv::OpFunctionEnd: return true;
196	default: return false;
197	}
198	}
199
200	// Return true if this opcode defines a type
201	bool spirvbin_t::isTypeOp(spv::Op opCode) const
202	{
203	switch (opCode) {
204	case spv::OpTypeVoid:
205	case spv::OpTypeBool:
206	case spv::OpTypeInt:
207	case spv::OpTypeFloat:
208	case spv::OpTypeVector:
209	case spv::OpTypeMatrix:
210	case spv::OpTypeImage:
211	case spv::OpTypeSampler:
212	case spv::OpTypeArray:
213	case spv::OpTypeRuntimeArray:
214	case spv::OpTypeStruct:
215	case spv::OpTypeOpaque:
216	case spv::OpTypePointer:
217	case spv::OpTypeFunction:
218	case spv::OpTypeEvent:
219	case spv::OpTypeDeviceEvent:
220	case spv::OpTypeReserveId:
221	case spv::OpTypeQueue:
222	case spv::OpTypeSampledImage:
223	case spv::OpTypePipe: return true;
224	default: return false;
225	}
226	}
227
228	// Return true if this opcode defines a constant
229	bool spirvbin_t::isConstOp(spv::Op opCode) const
230	{
231	switch (opCode) {
232	case spv::OpConstantSampler:
233	error(txt: "unimplemented constant type");
234	return true;
235
236	case spv::OpConstantNull:
237	case spv::OpConstantTrue:
238	case spv::OpConstantFalse:
239	case spv::OpConstantComposite:
240	case spv::OpConstant:
241	return true;
242
243	default:
244	return false;
245	}
246	}
247
248	const auto inst_fn_nop = [](spv::Op, unsigned) { return false; };
249	const auto op_fn_nop = [](spv::Id&) { };
250
251	// g++ doesn't like these defined in the class proper in an anonymous namespace.
252	// Dunno why. Also MSVC doesn't like the constexpr keyword. Also dunno why.
253	// Defining them externally seems to please both compilers, so, here they are.
254	const spv::Id spirvbin_t::unmapped = spv::Id(-10000);
255	const spv::Id spirvbin_t::unused = spv::Id(-10001);
256	const int spirvbin_t::header_size = 5;
257
258	spv::Id spirvbin_t::nextUnusedId(spv::Id id)
259	{
260	while (isNewIdMapped(newId: id)) // search for an unused ID
261	++id;
262
263	return id;
264	}
265
266	spv::Id spirvbin_t::localId(spv::Id id, spv::Id newId)
267	{
268	//assert(id != spv::NoResult && newId != spv::NoResult);
269
270	if (id > bound()) {
271	error(txt: std::string("ID out of range: ") + std::to_string(val: id));
272	return spirvbin_t::unused;
273	}
274
275	if (id >= idMapL.size())
276	idMapL.resize(new_size: id+1, x: unused);
277
278	if (newId != unmapped && newId != unused) {
279	if (isOldIdUnused(oldId: id)) {
280	error(txt: std::string("ID unused in module: ") + std::to_string(val: id));
281	return spirvbin_t::unused;
282	}
283
284	if (!isOldIdUnmapped(oldId: id)) {
285	error(txt: std::string("ID already mapped: ") + std::to_string(val: id) + " -> "
286	+ std::to_string(val: localId(id)));
287
288	return spirvbin_t::unused;
289	}
290
291	if (isNewIdMapped(newId)) {
292	error(txt: std::string("ID already used in module: ") + std::to_string(val: newId));
293	return spirvbin_t::unused;
294	}
295
296	msg(minVerbosity: 4, indent: 4, txt: std::string("map: ") + std::to_string(val: id) + " -> " + std::to_string(val: newId));
297	setMapped(newId);
298	largestNewId = std::max(a: largestNewId, b: newId);
299	}
300
301	return idMapL[id] = newId;
302	}
303
304	// Parse a literal string from the SPIR binary and return it as an std::string
305	// Due to C++11 RValue references, this doesn't copy the result string.
306	std::string spirvbin_t::literalString(unsigned word) const
307	{
308	std::string literal;
309	const spirword_t * pos = spv.data() + word;
310
311	literal.reserve(res: 16);
312
313	do {
314	spirword_t word = *pos;
315	for (int i = 0; i < 4; i++) {
316	char c = word & 0xff;
317	if (c == '\0')
318	return literal;
319	literal += c;
320	word >>= 8;
321	}
322	pos++;
323	} while (true);
324	}
325
326	void spirvbin_t::applyMap()
327	{
328	msg(minVerbosity: 3, indent: 2, txt: std::string("Applying map: "));
329
330	// Map local IDs through the ID map
331	process(inst_fn_nop, // ignore instructions
332	[this](spv::Id& id) {
333	id = localId(id);
334
335	if (errorLatch)
336	return;
337
338	assert(id != unused && id != unmapped);
339	}
340	);
341	}
342
343	// Find free IDs for anything we haven't mapped
344	void spirvbin_t::mapRemainder()
345	{
346	msg(minVerbosity: 3, indent: 2, txt: std::string("Remapping remainder: "));
347
348	spv::Id unusedId = 1; // can't use 0: that's NoResult
349	spirword_t maxBound = 0;
350
351	for (spv::Id id = 0; id < idMapL.size(); ++id) {
352	if (isOldIdUnused(oldId: id))
353	continue;
354
355	// Find a new mapping for any used but unmapped IDs
356	if (isOldIdUnmapped(oldId: id)) {
357	localId(id, newId: unusedId = nextUnusedId(id: unusedId));
358	if (errorLatch)
359	return;
360	}
361
362	if (isOldIdUnmapped(oldId: id)) {
363	error(txt: std::string("old ID not mapped: ") + std::to_string(val: id));
364	return;
365	}
366
367	// Track max bound
368	maxBound = std::max(a: maxBound, b: localId(id) + 1);
369
370	if (errorLatch)
371	return;
372	}
373
374	bound(b: maxBound); // reset header ID bound to as big as it now needs to be
375	}
376
377	// Mark debug instructions for stripping
378	void spirvbin_t::stripDebug()
379	{
380	// Strip instructions in the stripOp set: debug info.
381	process(
382	[&](spv::Op opCode, unsigned start) {
383	// remember opcodes we want to strip later
384	if (isStripOp(opCode, start))
385	stripInst(start);
386	return true;
387	},
388	op_fn_nop);
389	}
390
391	// Mark instructions that refer to now-removed IDs for stripping
392	void spirvbin_t::stripDeadRefs()
393	{
394	process(
395	[&](spv::Op opCode, unsigned start) {
396	// strip opcodes pointing to removed data
397	switch (opCode) {
398	case spv::OpName:
399	case spv::OpMemberName:
400	case spv::OpDecorate:
401	case spv::OpMemberDecorate:
402	if (idPosR.find(x: asId(word: start+1)) == idPosR.end())
403	stripInst(start);
404	break;
405	default:
406	break; // leave it alone
407	}
408
409	return true;
410	},
411	op_fn_nop);
412
413	strip();
414	}
415
416	// Update local maps of ID, type, etc positions
417	void spirvbin_t::buildLocalMaps()
418	{
419	msg(minVerbosity: 2, indent: 2, txt: std::string("build local maps: "));
420
421	mapped.clear();
422	idMapL.clear();
423	// preserve nameMap, so we don't clear that.
424	fnPos.clear();
425	fnCalls.clear();
426	typeConstPos.clear();
427	idPosR.clear();
428	entryPoint = spv::NoResult;
429	largestNewId = 0;
430
431	idMapL.resize(new_size: bound(), x: unused);
432
433	int fnStart = 0;
434	spv::Id fnRes = spv::NoResult;
435
436	// build local Id and name maps
437	process(
438	[&](spv::Op opCode, unsigned start) {
439	unsigned word = start+1;
440	spv::Id typeId = spv::NoResult;
441
442	if (spv::InstructionDesc[opCode].hasType())
443	typeId = asId(word: word++);
444
445	// If there's a result ID, remember the size of its type
446	if (spv::InstructionDesc[opCode].hasResult()) {
447	const spv::Id resultId = asId(word: word++);
448	idPosR[resultId] = start;
449
450	if (typeId != spv::NoResult) {
451	const unsigned idTypeSize = typeSizeInWords(id: typeId);
452
453	if (errorLatch)
454	return false;
455
456	if (idTypeSize != 0)
457	idTypeSizeMap[resultId] = idTypeSize;
458	}
459	}
460
461	if (opCode == spv::Op::OpName) {
462	const spv::Id target = asId(word: start+1);
463	const std::string name = literalString(word: start+2);
464	nameMap[name] = target;
465
466	} else if (opCode == spv::Op::OpFunctionCall) {
467	++fnCalls[asId(word: start + 3)];
468	} else if (opCode == spv::Op::OpEntryPoint) {
469	entryPoint = asId(word: start + 2);
470	} else if (opCode == spv::Op::OpFunction) {
471	if (fnStart != 0) {
472	error(txt: "nested function found");
473	return false;
474	}
475
476	fnStart = start;
477	fnRes = asId(word: start + 2);
478	} else if (opCode == spv::Op::OpFunctionEnd) {
479	assert(fnRes != spv::NoResult);
480	if (fnStart == 0) {
481	error(txt: "function end without function start");
482	return false;
483	}
484
485	fnPos[fnRes] = range_t(fnStart, start + asWordCount(word: start));
486	fnStart = 0;
487	} else if (isConstOp(opCode)) {
488	if (errorLatch)
489	return false;
490
491	assert(asId(start + 2) != spv::NoResult);
492	typeConstPos.insert(x: start);
493	} else if (isTypeOp(opCode)) {
494	assert(asId(start + 1) != spv::NoResult);
495	typeConstPos.insert(x: start);
496	}
497
498	return false;
499	},
500
501	[this](spv::Id& id) { localId(id, newId: unmapped); }
502	);
503	}
504
505	// Validate the SPIR header
506	void spirvbin_t::validate() const
507	{
508	msg(minVerbosity: 2, indent: 2, txt: std::string("validating: "));
509
510	if (spv.size() < header_size) {
511	error(txt: "file too short: ");
512	return;
513	}
514
515	if (magic() != spv::MagicNumber) {
516	error(txt: "bad magic number");
517	return;
518	}
519
520	// field 1 = version
521	// field 2 = generator magic
522	// field 3 = result <id> bound
523
524	if (schemaNum() != 0) {
525	error(txt: "bad schema, must be 0");
526	return;
527	}
528	}
529
530	int spirvbin_t::processInstruction(unsigned word, instfn_t instFn, idfn_t idFn)
531	{
532	const auto instructionStart = word;
533	const unsigned wordCount = asWordCount(word: instructionStart);
534	const int nextInst = word++ + wordCount;
535	spv::Op opCode = asOpCode(word: instructionStart);
536
537	if (nextInst > int(spv.size())) {
538	error(txt: "spir instruction terminated too early");
539	return -1;
540	}
541
542	// Base for computing number of operands; will be updated as more is learned
543	unsigned numOperands = wordCount - 1;
544
545	if (instFn(opCode, instructionStart))
546	return nextInst;
547
548	// Read type and result ID from instruction desc table
549	if (spv::InstructionDesc[opCode].hasType()) {
550	idFn(asId(word: word++));
551	--numOperands;
552	}
553
554	if (spv::InstructionDesc[opCode].hasResult()) {
555	idFn(asId(word: word++));
556	--numOperands;
557	}
558
559	// Extended instructions: currently, assume everything is an ID.
560	// TODO: add whatever data we need for exceptions to that
561	if (opCode == spv::OpExtInst) {
562
563	idFn(asId(word)); // Instruction set is an ID that also needs to be mapped
564
565	word += 2; // instruction set, and instruction from set
566	numOperands -= 2;
567
568	for (unsigned op=0; op < numOperands; ++op)
569	idFn(asId(word: word++)); // ID
570
571	return nextInst;
572	}
573
574	// Circular buffer so we can look back at previous unmapped values during the mapping pass.
575	static const unsigned idBufferSize = 4;
576	spv::Id idBuffer[idBufferSize];
577	unsigned idBufferPos = 0;
578
579	// Store IDs from instruction in our map
580	for (int op = 0; numOperands > 0; ++op, --numOperands) {
581	// SpecConstantOp is special: it includes the operands of another opcode which is
582	// given as a literal in the 3rd word. We will switch over to pretending that the
583	// opcode being processed is the literal opcode value of the SpecConstantOp. See the
584	// SPIRV spec for details. This way we will handle IDs and literals as appropriate for
585	// the embedded op.
586	if (opCode == spv::OpSpecConstantOp) {
587	if (op == 0) {
588	opCode = asOpCode(word: word++); // this is the opcode embedded in the SpecConstantOp.
589	--numOperands;
590	}
591	}
592
593	switch (spv::InstructionDesc[opCode].operands.getClass(op)) {
594	case spv::OperandId:
595	case spv::OperandScope:
596	case spv::OperandMemorySemantics:
597	idBuffer[idBufferPos] = asId(word);
598	idBufferPos = (idBufferPos + 1) % idBufferSize;
599	idFn(asId(word: word++));
600	break;
601
602	case spv::OperandVariableIds:
603	for (unsigned i = 0; i < numOperands; ++i)
604	idFn(asId(word: word++));
605	return nextInst;
606
607	case spv::OperandVariableLiterals:
608	// for clarity
609	// if (opCode == spv::OpDecorate && asDecoration(word - 1) == spv::DecorationBuiltIn) {
610	// ++word;
611	// --numOperands;
612	// }
613	// word += numOperands;
614	return nextInst;
615
616	case spv::OperandVariableLiteralId: {
617	if (opCode == OpSwitch) {
618	// word-2 is the position of the selector ID. OpSwitch Literals match its type.
619	// In case the IDs are currently being remapped, we get the word[-2] ID from
620	// the circular idBuffer.
621	const unsigned literalSizePos = (idBufferPos+idBufferSize-2) % idBufferSize;
622	const unsigned literalSize = idTypeSizeInWords(id: idBuffer[literalSizePos]);
623	const unsigned numLiteralIdPairs = (nextInst-word) / (1+literalSize);
624
625	if (errorLatch)
626	return -1;
627
628	for (unsigned arg=0; arg<numLiteralIdPairs; ++arg) {
629	word += literalSize; // literal
630	idFn(asId(word: word++)); // label
631	}
632	} else {
633	assert(0); // currentely, only OpSwitch uses OperandVariableLiteralId
634	}
635
636	return nextInst;
637	}
638
639	case spv::OperandLiteralString: {
640	const int stringWordCount = literalStringWords(str: literalString(word));
641	word += stringWordCount;
642	numOperands -= (stringWordCount-1); // -1 because for() header post-decrements
643	break;
644	}
645
646	case spv::OperandVariableLiteralStrings:
647	return nextInst;
648
649	// Execution mode might have extra literal operands. Skip them.
650	case spv::OperandExecutionMode:
651	return nextInst;
652
653	case spv::OperandMemoryAccess:
654	{
655	uint32_t mask = spv[word];
656	if (mask & uint32_t(spv::MemoryAccessMask::MemoryAccessAlignedMask)) {
657	++word;
658	--numOperands;
659	}
660	if (mask & uint32_t(spv::MemoryAccessMask::MemoryAccessMakePointerAvailableMask |
661	spv::MemoryAccessMask::MemoryAccessMakePointerVisibleMask)) {
662	idFn(asId(word: word+1));
663	++word;
664	--numOperands;
665	}
666	++word;
667	}
668	break;
669
670	case spv::OperandTensorAddressingOperands:
671	{
672	uint32_t mask = spv[word];
673	if (mask & uint32_t(spv::TensorAddressingOperandsMask::TensorAddressingOperandsTensorViewMask)) {
674	idFn(asId(word: word+1));
675	++word;
676	--numOperands;
677	}
678	if (mask & uint32_t(spv::TensorAddressingOperandsMask::TensorAddressingOperandsDecodeFuncMask)) {
679	idFn(asId(word: word+1));
680	++word;
681	--numOperands;
682	}
683	++word;
684	}
685	break;
686
687	// Single word operands we simply ignore, as they hold no IDs
688	case spv::OperandLiteralNumber:
689	case spv::OperandSource:
690	case spv::OperandExecutionModel:
691	case spv::OperandAddressing:
692	case spv::OperandMemory:
693	case spv::OperandStorage:
694	case spv::OperandDimensionality:
695	case spv::OperandSamplerAddressingMode:
696	case spv::OperandSamplerFilterMode:
697	case spv::OperandSamplerImageFormat:
698	case spv::OperandImageChannelOrder:
699	case spv::OperandImageChannelDataType:
700	case spv::OperandImageOperands:
701	case spv::OperandFPFastMath:
702	case spv::OperandFPRoundingMode:
703	case spv::OperandLinkageType:
704	case spv::OperandAccessQualifier:
705	case spv::OperandFuncParamAttr:
706	case spv::OperandDecoration:
707	case spv::OperandBuiltIn:
708	case spv::OperandSelect:
709	case spv::OperandLoop:
710	case spv::OperandFunction:
711	case spv::OperandGroupOperation:
712	case spv::OperandKernelEnqueueFlags:
713	case spv::OperandKernelProfilingInfo:
714	case spv::OperandCapability:
715	case spv::OperandCooperativeMatrixOperands:
716	++word;
717	break;
718
719	default:
720	assert(0 && "Unhandled Operand Class");
721	break;
722	}
723	}
724
725	return nextInst;
726	}
727
728	// Make a pass over all the instructions and process them given appropriate functions
729	spirvbin_t& spirvbin_t::process(instfn_t instFn, idfn_t idFn, unsigned begin, unsigned end)
730	{
731	// For efficiency, reserve name map space. It can grow if needed.
732	nameMap.reserve(n: 32);
733
734	// If begin or end == 0, use defaults
735	begin = (begin == 0 ? header_size : begin);
736	end = (end == 0 ? unsigned(spv.size()) : end);
737
738	// basic parsing and InstructionDesc table borrowed from SpvDisassemble.cpp...
739	unsigned nextInst = unsigned(spv.size());
740
741	for (unsigned word = begin; word < end; word = nextInst) {
742	nextInst = processInstruction(word, instFn, idFn);
743
744	if (errorLatch)
745	return *this;
746	}
747
748	return *this;
749	}
750
751	// Apply global name mapping to a single module
752	void spirvbin_t::mapNames()
753	{
754	static const std::uint32_t softTypeIdLimit = 3011; // small prime. TODO: get from options
755	static const std::uint32_t firstMappedID = 3019; // offset into ID space
756
757	for (const auto& name : nameMap) {
758	std::uint32_t hashval = 1911;
759	for (const char c : name.first)
760	hashval = hashval * 1009 + c;
761
762	if (isOldIdUnmapped(oldId: name.second)) {
763	localId(id: name.second, newId: nextUnusedId(id: hashval % softTypeIdLimit + firstMappedID));
764	if (errorLatch)
765	return;
766	}
767	}
768	}
769
770	// Map fn contents to IDs of similar functions in other modules
771	void spirvbin_t::mapFnBodies()
772	{
773	static const std::uint32_t softTypeIdLimit = 19071; // small prime. TODO: get from options
774	static const std::uint32_t firstMappedID = 6203; // offset into ID space
775
776	// Initial approach: go through some high priority opcodes first and assign them
777	// hash values.
778
779	spv::Id fnId = spv::NoResult;
780	std::vector<unsigned> instPos;
781	instPos.reserve(n: unsigned(spv.size()) / 16); // initial estimate; can grow if needed.
782
783	// Build local table of instruction start positions
784	process(
785	instFn: [&](spv::Op, unsigned start) { instPos.push_back(x: start); return true; },
786	idFn: op_fn_nop);
787
788	if (errorLatch)
789	return;
790
791	// Window size for context-sensitive canonicalization values
792	// Empirical best size from a single data set. TODO: Would be a good tunable.
793	// We essentially perform a little convolution around each instruction,
794	// to capture the flavor of nearby code, to hopefully match to similar
795	// code in other modules.
796	static const unsigned windowSize = 2;
797
798	for (unsigned entry = 0; entry < unsigned(instPos.size()); ++entry) {
799	const unsigned start = instPos[entry];
800	const spv::Op opCode = asOpCode(word: start);
801
802	if (opCode == spv::OpFunction)
803	fnId = asId(word: start + 2);
804
805	if (opCode == spv::OpFunctionEnd)
806	fnId = spv::NoResult;
807
808	if (fnId != spv::NoResult) { // if inside a function
809	if (spv::InstructionDesc[opCode].hasResult()) {
810	const unsigned word = start + (spv::InstructionDesc[opCode].hasType() ? 2 : 1);
811	const spv::Id resId = asId(word);
812	std::uint32_t hashval = fnId * 17; // small prime
813
814	for (unsigned i = entry-1; i >= entry-windowSize; --i) {
815	if (asOpCode(word: instPos[i]) == spv::OpFunction)
816	break;
817	hashval = hashval * 30103 + asOpCodeHash(word: instPos[i]); // 30103 = semiarbitrary prime
818	}
819
820	for (unsigned i = entry; i <= entry + windowSize; ++i) {
821	if (asOpCode(word: instPos[i]) == spv::OpFunctionEnd)
822	break;
823	hashval = hashval * 30103 + asOpCodeHash(word: instPos[i]); // 30103 = semiarbitrary prime
824	}
825
826	if (isOldIdUnmapped(oldId: resId)) {
827	localId(id: resId, newId: nextUnusedId(id: hashval % softTypeIdLimit + firstMappedID));
828	if (errorLatch)
829	return;
830	}
831
832	}
833	}
834	}
835
836	spv::Op thisOpCode(spv::OpNop);
837	std::unordered_map<int, int> opCounter;
838	int idCounter(0);
839	fnId = spv::NoResult;
840
841	process(
842	instFn: [&](spv::Op opCode, unsigned start) {
843	switch (opCode) {
844	case spv::OpFunction:
845	// Reset counters at each function
846	idCounter = 0;
847	opCounter.clear();
848	fnId = asId(word: start + 2);
849	break;
850
851	case spv::OpImageSampleImplicitLod:
852	case spv::OpImageSampleExplicitLod:
853	case spv::OpImageSampleDrefImplicitLod:
854	case spv::OpImageSampleDrefExplicitLod:
855	case spv::OpImageSampleProjImplicitLod:
856	case spv::OpImageSampleProjExplicitLod:
857	case spv::OpImageSampleProjDrefImplicitLod:
858	case spv::OpImageSampleProjDrefExplicitLod:
859	case spv::OpDot:
860	case spv::OpCompositeExtract:
861	case spv::OpCompositeInsert:
862	case spv::OpVectorShuffle:
863	case spv::OpLabel:
864	case spv::OpVariable:
865
866	case spv::OpAccessChain:
867	case spv::OpLoad:
868	case spv::OpStore:
869	case spv::OpCompositeConstruct:
870	case spv::OpFunctionCall:
871	++opCounter[opCode];
872	idCounter = 0;
873	thisOpCode = opCode;
874	break;
875	default:
876	thisOpCode = spv::OpNop;
877	}
878
879	return false;
880	},
881
882	idFn: [&](spv::Id& id) {
883	if (thisOpCode != spv::OpNop) {
884	++idCounter;
885	const std::uint32_t hashval =
886	// Explicitly cast operands to unsigned int to avoid integer
887	// promotion to signed int followed by integer overflow,
888	// which would result in undefined behavior.
889	static_cast<unsigned int>(opCounter[thisOpCode])
890	* thisOpCode
891	* 50047
892	+ idCounter
893	+ static_cast<unsigned int>(fnId) * 117;
894
895	if (isOldIdUnmapped(oldId: id))
896	localId(id, newId: nextUnusedId(id: hashval % softTypeIdLimit + firstMappedID));
897	}
898	});
899	}
900
901	// EXPERIMENTAL: forward IO and uniform load/stores into operands
902	// This produces invalid Schema-0 SPIRV
903	void spirvbin_t::forwardLoadStores()
904	{
905	idset_t fnLocalVars; // set of function local vars
906	idmap_t idMap; // Map of load result IDs to what they load
907
908	// EXPERIMENTAL: Forward input and access chain loads into consumptions
909	process(
910	instFn: [&](spv::Op opCode, unsigned start) {
911	// Add inputs and uniforms to the map
912	if ((opCode == spv::OpVariable && asWordCount(word: start) == 4) &&
913	(spv[start+3] == spv::StorageClassUniform ||
914	spv[start+3] == spv::StorageClassUniformConstant ||
915	spv[start+3] == spv::StorageClassInput))
916	fnLocalVars.insert(x: asId(word: start+2));
917
918	if (opCode == spv::OpAccessChain && fnLocalVars.count(x: asId(word: start+3)) > 0)
919	fnLocalVars.insert(x: asId(word: start+2));
920
921	if (opCode == spv::OpLoad && fnLocalVars.count(x: asId(word: start+3)) > 0) {
922	idMap[asId(word: start+2)] = asId(word: start+3);
923	stripInst(start);
924	}
925
926	return false;
927	},
928
929	idFn: [&](spv::Id& id) { if (idMap.find(x: id) != idMap.end()) id = idMap[id]; }
930	);
931
932	if (errorLatch)
933	return;
934
935	// EXPERIMENTAL: Implicit output stores
936	fnLocalVars.clear();
937	idMap.clear();
938
939	process(
940	instFn: [&](spv::Op opCode, unsigned start) {
941	// Add inputs and uniforms to the map
942	if ((opCode == spv::OpVariable && asWordCount(word: start) == 4) &&
943	(spv[start+3] == spv::StorageClassOutput))
944	fnLocalVars.insert(x: asId(word: start+2));
945
946	if (opCode == spv::OpStore && fnLocalVars.count(x: asId(word: start+1)) > 0) {
947	idMap[asId(word: start+2)] = asId(word: start+1);
948	stripInst(start);
949	}
950
951	return false;
952	},
953	idFn: op_fn_nop);
954
955	if (errorLatch)
956	return;
957
958	process(
959	instFn: inst_fn_nop,
960	idFn: [&](spv::Id& id) { if (idMap.find(x: id) != idMap.end()) id = idMap[id]; }
961	);
962
963	if (errorLatch)
964	return;
965
966	strip(); // strip out data we decided to eliminate
967	}
968
969	// optimize loads and stores
970	void spirvbin_t::optLoadStore()
971	{
972	idset_t fnLocalVars; // candidates for removal (only locals)
973	idmap_t idMap; // Map of load result IDs to what they load
974	blockmap_t blockMap; // Map of IDs to blocks they first appear in
975	int blockNum = 0; // block count, to avoid crossing flow control
976
977	// Find all the function local pointers stored at most once, and not via access chains
978	process(
979	instFn: [&](spv::Op opCode, unsigned start) {
980	const int wordCount = asWordCount(word: start);
981
982	// Count blocks, so we can avoid crossing flow control
983	if (isFlowCtrl(opCode))
984	++blockNum;
985
986	// Add local variables to the map
987	if ((opCode == spv::OpVariable && spv[start+3] == spv::StorageClassFunction && asWordCount(word: start) == 4)) {
988	fnLocalVars.insert(x: asId(word: start+2));
989	return true;
990	}
991
992	// Ignore process vars referenced via access chain
993	if ((opCode == spv::OpAccessChain || opCode == spv::OpInBoundsAccessChain) && fnLocalVars.count(x: asId(word: start+3)) > 0) {
994	fnLocalVars.erase(x: asId(word: start+3));
995	idMap.erase(x: asId(word: start+3));
996	return true;
997	}
998
999	if (opCode == spv::OpLoad && fnLocalVars.count(x: asId(word: start+3)) > 0) {
1000	const spv::Id varId = asId(word: start+3);
1001
1002	// Avoid loads before stores
1003	if (idMap.find(x: varId) == idMap.end()) {
1004	fnLocalVars.erase(x: varId);
1005	idMap.erase(x: varId);
1006	}
1007
1008	// don't do for volatile references
1009	if (wordCount > 4 && (spv[start+4] & spv::MemoryAccessVolatileMask)) {
1010	fnLocalVars.erase(x: varId);
1011	idMap.erase(x: varId);
1012	}
1013
1014	// Handle flow control
1015	if (blockMap.find(x: varId) == blockMap.end()) {
1016	blockMap[varId] = blockNum; // track block we found it in.
1017	} else if (blockMap[varId] != blockNum) {
1018	fnLocalVars.erase(x: varId); // Ignore if crosses flow control
1019	idMap.erase(x: varId);
1020	}
1021
1022	return true;
1023	}
1024
1025	if (opCode == spv::OpStore && fnLocalVars.count(x: asId(word: start+1)) > 0) {
1026	const spv::Id varId = asId(word: start+1);
1027
1028	if (idMap.find(x: varId) == idMap.end()) {
1029	idMap[varId] = asId(word: start+2);
1030	} else {
1031	// Remove if it has more than one store to the same pointer
1032	fnLocalVars.erase(x: varId);
1033	idMap.erase(x: varId);
1034	}
1035
1036	// don't do for volatile references
1037	if (wordCount > 3 && (spv[start+3] & spv::MemoryAccessVolatileMask)) {
1038	fnLocalVars.erase(x: asId(word: start+3));
1039	idMap.erase(x: asId(word: start+3));
1040	}
1041
1042	// Handle flow control
1043	if (blockMap.find(x: varId) == blockMap.end()) {
1044	blockMap[varId] = blockNum; // track block we found it in.
1045	} else if (blockMap[varId] != blockNum) {
1046	fnLocalVars.erase(x: varId); // Ignore if crosses flow control
1047	idMap.erase(x: varId);
1048	}
1049
1050	return true;
1051	}
1052
1053	return false;
1054	},
1055
1056	// If local var id used anywhere else, don't eliminate
1057	idFn: [&](spv::Id& id) {
1058	if (fnLocalVars.count(x: id) > 0) {
1059	fnLocalVars.erase(x: id);
1060	idMap.erase(x: id);
1061	}
1062	}
1063	);
1064
1065	if (errorLatch)
1066	return;
1067
1068	process(
1069	instFn: [&](spv::Op opCode, unsigned start) {
1070	if (opCode == spv::OpLoad && fnLocalVars.count(x: asId(word: start+3)) > 0)
1071	idMap[asId(word: start+2)] = idMap[asId(word: start+3)];
1072	return false;
1073	},
1074	idFn: op_fn_nop);
1075
1076	if (errorLatch)
1077	return;
1078
1079	// Chase replacements to their origins, in case there is a chain such as:
1080	// 2 = store 1
1081	// 3 = load 2
1082	// 4 = store 3
1083	// 5 = load 4
1084	// We want to replace uses of 5 with 1.
1085	for (const auto& idPair : idMap) {
1086	spv::Id id = idPair.first;
1087	while (idMap.find(x: id) != idMap.end()) // Chase to end of chain
1088	id = idMap[id];
1089
1090	idMap[idPair.first] = id; // replace with final result
1091	}
1092
1093	// Remove the load/store/variables for the ones we've discovered
1094	process(
1095	instFn: [&](spv::Op opCode, unsigned start) {
1096	if ((opCode == spv::OpLoad && fnLocalVars.count(x: asId(word: start+3)) > 0) ||
1097	(opCode == spv::OpStore && fnLocalVars.count(x: asId(word: start+1)) > 0) ||
1098	(opCode == spv::OpVariable && fnLocalVars.count(x: asId(word: start+2)) > 0)) {
1099
1100	stripInst(start);
1101	return true;
1102	}
1103
1104	return false;
1105	},
1106
1107	idFn: [&](spv::Id& id) {
1108	if (idMap.find(x: id) != idMap.end()) id = idMap[id];
1109	}
1110	);
1111
1112	if (errorLatch)
1113	return;
1114
1115	strip(); // strip out data we decided to eliminate
1116	}
1117
1118	// remove bodies of uncalled functions
1119	void spirvbin_t::dceFuncs()
1120	{
1121	msg(minVerbosity: 3, indent: 2, txt: std::string("Removing Dead Functions: "));
1122
1123	// TODO: There are more efficient ways to do this.
1124	bool changed = true;
1125
1126	while (changed) {
1127	changed = false;
1128
1129	for (auto fn = fnPos.begin(); fn != fnPos.end(); ) {
1130	if (fn->first == entryPoint) { // don't DCE away the entry point!
1131	++fn;
1132	continue;
1133	}
1134
1135	const auto call_it = fnCalls.find(x: fn->first);
1136
1137	if (call_it == fnCalls.end() || call_it->second == 0) {
1138	changed = true;
1139	stripRange.push_back(x: fn->second);
1140
1141	// decrease counts of called functions
1142	process(
1143	instFn: [&](spv::Op opCode, unsigned start) {
1144	if (opCode == spv::Op::OpFunctionCall) {
1145	const auto call_it = fnCalls.find(x: asId(word: start + 3));
1146	if (call_it != fnCalls.end()) {
1147	if (--call_it->second <= 0)
1148	fnCalls.erase(position: call_it);
1149	}
1150	}
1151
1152	return true;
1153	},
1154	idFn: op_fn_nop,
1155	begin: fn->second.first,
1156	end: fn->second.second);
1157
1158	if (errorLatch)
1159	return;
1160
1161	fn = fnPos.erase(position: fn);
1162	} else ++fn;
1163	}
1164	}
1165	}
1166
1167	// remove unused function variables + decorations
1168	void spirvbin_t::dceVars()
1169	{
1170	msg(minVerbosity: 3, indent: 2, txt: std::string("DCE Vars: "));
1171
1172	std::unordered_map<spv::Id, int> varUseCount;
1173
1174	// Count function variable use
1175	process(
1176	instFn: [&](spv::Op opCode, unsigned start) {
1177	if (opCode == spv::OpVariable) {
1178	++varUseCount[asId(word: start+2)];
1179	return true;
1180	} else if (opCode == spv::OpEntryPoint) {
1181	const int wordCount = asWordCount(word: start);
1182	for (int i = 4; i < wordCount; i++) {
1183	++varUseCount[asId(word: start+i)];
1184	}
1185	return true;
1186	} else
1187	return false;
1188	},
1189
1190	idFn: [&](spv::Id& id) { if (varUseCount[id]) ++varUseCount[id]; }
1191	);
1192
1193	if (errorLatch)
1194	return;
1195
1196	// Remove single-use function variables + associated decorations and names
1197	process(
1198	instFn: [&](spv::Op opCode, unsigned start) {
1199	spv::Id id = spv::NoResult;
1200	if (opCode == spv::OpVariable)
1201	id = asId(word: start+2);
1202	if (opCode == spv::OpDecorate || opCode == spv::OpName)
1203	id = asId(word: start+1);
1204
1205	if (id != spv::NoResult && varUseCount[id] == 1)
1206	stripInst(start);
1207
1208	return true;
1209	},
1210	idFn: op_fn_nop);
1211	}
1212
1213	// remove unused types
1214	void spirvbin_t::dceTypes()
1215	{
1216	std::vector<bool> isType(bound(), false);
1217
1218	// for speed, make O(1) way to get to type query (map is log(n))
1219	for (const auto typeStart : typeConstPos)
1220	isType[asTypeConstId(word: typeStart)] = true;
1221
1222	std::unordered_map<spv::Id, int> typeUseCount;
1223
1224	// This is not the most efficient algorithm, but this is an offline tool, and
1225	// it's easy to write this way. Can be improved opportunistically if needed.
1226	bool changed = true;
1227	while (changed) {
1228	changed = false;
1229	strip();
1230	typeUseCount.clear();
1231
1232	// Count total type usage
1233	process(instFn: inst_fn_nop,
1234	idFn: [&](spv::Id& id) { if (isType[id]) ++typeUseCount[id]; }
1235	);
1236
1237	if (errorLatch)
1238	return;
1239
1240	// Remove single reference types
1241	for (const auto typeStart : typeConstPos) {
1242	const spv::Id typeId = asTypeConstId(word: typeStart);
1243	if (typeUseCount[typeId] == 1) {
1244	changed = true;
1245	--typeUseCount[typeId];
1246	stripInst(start: typeStart);
1247	}
1248	}
1249
1250	if (errorLatch)
1251	return;
1252	}
1253	}
1254
1255	#ifdef NOTDEF
1256	bool spirvbin_t::matchType(const spirvbin_t::globaltypes_t& globalTypes, spv::Id lt, spv::Id gt) const
1257	{
1258	// Find the local type id "lt" and global type id "gt"
1259	const auto lt_it = typeConstPosR.find(lt);
1260	if (lt_it == typeConstPosR.end())
1261	return false;
1262
1263	const auto typeStart = lt_it->second;
1264
1265	// Search for entry in global table
1266	const auto gtype = globalTypes.find(gt);
1267	if (gtype == globalTypes.end())
1268	return false;
1269
1270	const auto& gdata = gtype->second;
1271
1272	// local wordcount and opcode
1273	const int wordCount = asWordCount(typeStart);
1274	const spv::Op opCode = asOpCode(typeStart);
1275
1276	// no type match if opcodes don't match, or operand count doesn't match
1277	if (opCode != opOpCode(gdata[0]) || wordCount != opWordCount(gdata[0]))
1278	return false;
1279
1280	const unsigned numOperands = wordCount - 2; // all types have a result
1281
1282	const auto cmpIdRange = [&](range_t range) {
1283	for (int x=range.first; x<std::min(range.second, wordCount); ++x)
1284	if (!matchType(globalTypes, asId(typeStart+x), gdata[x]))
1285	return false;
1286	return true;
1287	};
1288
1289	const auto cmpConst = [&]() { return cmpIdRange(constRange(opCode)); };
1290	const auto cmpSubType = [&]() { return cmpIdRange(typeRange(opCode)); };
1291
1292	// Compare literals in range [start,end)
1293	const auto cmpLiteral = [&]() {
1294	const auto range = literalRange(opCode);
1295	return std::equal(spir.begin() + typeStart + range.first,
1296	spir.begin() + typeStart + std::min(range.second, wordCount),
1297	gdata.begin() + range.first);
1298	};
1299
1300	assert(isTypeOp(opCode) || isConstOp(opCode));
1301
1302	switch (opCode) {
1303	case spv::OpTypeOpaque: // TODO: disable until we compare the literal strings.
1304	case spv::OpTypeQueue: return false;
1305	case spv::OpTypeEvent: // fall through...
1306	case spv::OpTypeDeviceEvent: // ...
1307	case spv::OpTypeReserveId: return false;
1308	// for samplers, we don't handle the optional parameters yet
1309	case spv::OpTypeSampler: return cmpLiteral() && cmpConst() && cmpSubType() && wordCount == 8;
1310	default: return cmpLiteral() && cmpConst() && cmpSubType();
1311	}
1312	}
1313
1314	// Look for an equivalent type in the globalTypes map
1315	spv::Id spirvbin_t::findType(const spirvbin_t::globaltypes_t& globalTypes, spv::Id lt) const
1316	{
1317	// Try a recursive type match on each in turn, and return a match if we find one
1318	for (const auto& gt : globalTypes)
1319	if (matchType(globalTypes, lt, gt.first))
1320	return gt.first;
1321
1322	return spv::NoType;
1323	}
1324	#endif // NOTDEF
1325
1326	// Return start position in SPV of given Id. error if not found.
1327	unsigned spirvbin_t::idPos(spv::Id id) const
1328	{
1329	const auto tid_it = idPosR.find(x: id);
1330	if (tid_it == idPosR.end()) {
1331	error(txt: "ID not found");
1332	return 0;
1333	}
1334
1335	return tid_it->second;
1336	}
1337
1338	// Hash types to canonical values. This can return ID collisions (it's a bit
1339	// inevitable): it's up to the caller to handle that gracefully.
1340	std::uint32_t spirvbin_t::hashType(unsigned typeStart) const
1341	{
1342	const unsigned wordCount = asWordCount(word: typeStart);
1343	const spv::Op opCode = asOpCode(word: typeStart);
1344
1345	switch (opCode) {
1346	case spv::OpTypeVoid: return 0;
1347	case spv::OpTypeBool: return 1;
1348	case spv::OpTypeInt: return 3 + (spv[typeStart+3]);
1349	case spv::OpTypeFloat: return 5;
1350	case spv::OpTypeVector:
1351	return 6 + hashType(typeStart: idPos(id: spv[typeStart+2])) * (spv[typeStart+3] - 1);
1352	case spv::OpTypeMatrix:
1353	return 30 + hashType(typeStart: idPos(id: spv[typeStart+2])) * (spv[typeStart+3] - 1);
1354	case spv::OpTypeImage:
1355	return 120 + hashType(typeStart: idPos(id: spv[typeStart+2])) +
1356	spv[typeStart+3] + // dimensionality
1357	spv[typeStart+4] * 8 * 16 + // depth
1358	spv[typeStart+5] * 4 * 16 + // arrayed
1359	spv[typeStart+6] * 2 * 16 + // multisampled
1360	spv[typeStart+7] * 1 * 16; // format
1361	case spv::OpTypeSampler:
1362	return 500;
1363	case spv::OpTypeSampledImage:
1364	return 502;
1365	case spv::OpTypeArray:
1366	return 501 + hashType(typeStart: idPos(id: spv[typeStart+2])) * spv[typeStart+3];
1367	case spv::OpTypeRuntimeArray:
1368	return 5000 + hashType(typeStart: idPos(id: spv[typeStart+2]));
1369	case spv::OpTypeStruct:
1370	{
1371	std::uint32_t hash = 10000;
1372	for (unsigned w=2; w < wordCount; ++w)
1373	hash += w * hashType(typeStart: idPos(id: spv[typeStart+w]));
1374	return hash;
1375	}
1376
1377	case spv::OpTypeOpaque: return 6000 + spv[typeStart+2];
1378	case spv::OpTypePointer: return 100000 + hashType(typeStart: idPos(id: spv[typeStart+3]));
1379	case spv::OpTypeFunction:
1380	{
1381	std::uint32_t hash = 200000;
1382	for (unsigned w=2; w < wordCount; ++w)
1383	hash += w * hashType(typeStart: idPos(id: spv[typeStart+w]));
1384	return hash;
1385	}
1386
1387	case spv::OpTypeEvent: return 300000;
1388	case spv::OpTypeDeviceEvent: return 300001;
1389	case spv::OpTypeReserveId: return 300002;
1390	case spv::OpTypeQueue: return 300003;
1391	case spv::OpTypePipe: return 300004;
1392	case spv::OpConstantTrue: return 300007;
1393	case spv::OpConstantFalse: return 300008;
1394	case spv::OpConstantComposite:
1395	{
1396	std::uint32_t hash = 300011 + hashType(typeStart: idPos(id: spv[typeStart+1]));
1397	for (unsigned w=3; w < wordCount; ++w)
1398	hash += w * hashType(typeStart: idPos(id: spv[typeStart+w]));
1399	return hash;
1400	}
1401	case spv::OpConstant:
1402	{
1403	std::uint32_t hash = 400011 + hashType(typeStart: idPos(id: spv[typeStart+1]));
1404	for (unsigned w=3; w < wordCount; ++w)
1405	hash += w * spv[typeStart+w];
1406	return hash;
1407	}
1408	case spv::OpConstantNull:
1409	{
1410	std::uint32_t hash = 500009 + hashType(typeStart: idPos(id: spv[typeStart+1]));
1411	return hash;
1412	}
1413	case spv::OpConstantSampler:
1414	{
1415	std::uint32_t hash = 600011 + hashType(typeStart: idPos(id: spv[typeStart+1]));
1416	for (unsigned w=3; w < wordCount; ++w)
1417	hash += w * spv[typeStart+w];
1418	return hash;
1419	}
1420
1421	default:
1422	error(txt: "unknown type opcode");
1423	return 0;
1424	}
1425	}
1426
1427	void spirvbin_t::mapTypeConst()
1428	{
1429	globaltypes_t globalTypeMap;
1430
1431	msg(minVerbosity: 3, indent: 2, txt: std::string("Remapping Consts & Types: "));
1432
1433	static const std::uint32_t softTypeIdLimit = 3011; // small prime. TODO: get from options
1434	static const std::uint32_t firstMappedID = 8; // offset into ID space
1435
1436	for (auto& typeStart : typeConstPos) {
1437	const spv::Id resId = asTypeConstId(word: typeStart);
1438	const std::uint32_t hashval = hashType(typeStart);
1439
1440	if (errorLatch)
1441	return;
1442
1443	if (isOldIdUnmapped(oldId: resId)) {
1444	localId(id: resId, newId: nextUnusedId(id: hashval % softTypeIdLimit + firstMappedID));
1445	if (errorLatch)
1446	return;
1447	}
1448	}
1449	}
1450
1451	// Strip a single binary by removing ranges given in stripRange
1452	void spirvbin_t::strip()
1453	{
1454	if (stripRange.empty()) // nothing to do
1455	return;
1456
1457	// Sort strip ranges in order of traversal
1458	std::sort(first: stripRange.begin(), last: stripRange.end());
1459
1460	// Allocate a new binary big enough to hold old binary
1461	// We'll step this iterator through the strip ranges as we go through the binary
1462	auto strip_it = stripRange.begin();
1463
1464	int strippedPos = 0;
1465	for (unsigned word = 0; word < unsigned(spv.size()); ++word) {
1466	while (strip_it != stripRange.end() && word >= strip_it->second)
1467	++strip_it;
1468
1469	if (strip_it == stripRange.end() || word < strip_it->first || word >= strip_it->second)
1470	spv[strippedPos++] = spv[word];
1471	}
1472
1473	spv.resize(new_size: strippedPos);
1474	stripRange.clear();
1475
1476	buildLocalMaps();
1477	}
1478
1479	// Strip a single binary by removing ranges given in stripRange
1480	void spirvbin_t::remap(std::uint32_t opts)
1481	{
1482	options = opts;
1483
1484	// Set up opcode tables from SpvDoc
1485	spv::Parameterize();
1486
1487	validate(); // validate header
1488	buildLocalMaps(); // build ID maps
1489
1490	msg(minVerbosity: 3, indent: 4, txt: std::string("ID bound: ") + std::to_string(val: bound()));
1491
1492	if (options & STRIP) stripDebug();
1493	if (errorLatch) return;
1494
1495	strip(); // strip out data we decided to eliminate
1496	if (errorLatch) return;
1497
1498	if (options & OPT_LOADSTORE) optLoadStore();
1499	if (errorLatch) return;
1500
1501	if (options & OPT_FWD_LS) forwardLoadStores();
1502	if (errorLatch) return;
1503
1504	if (options & DCE_FUNCS) dceFuncs();
1505	if (errorLatch) return;
1506
1507	if (options & DCE_VARS) dceVars();
1508	if (errorLatch) return;
1509
1510	if (options & DCE_TYPES) dceTypes();
1511	if (errorLatch) return;
1512
1513	strip(); // strip out data we decided to eliminate
1514	if (errorLatch) return;
1515
1516	stripDeadRefs(); // remove references to things we DCEed
1517	if (errorLatch) return;
1518
1519	// after the last strip, we must clean any debug info referring to now-deleted data
1520
1521	if (options & MAP_TYPES) mapTypeConst();
1522	if (errorLatch) return;
1523
1524	if (options & MAP_NAMES) mapNames();
1525	if (errorLatch) return;
1526
1527	if (options & MAP_FUNCS) mapFnBodies();
1528	if (errorLatch) return;
1529
1530	if (options & MAP_ALL) {
1531	mapRemainder(); // map any unmapped IDs
1532	if (errorLatch) return;
1533
1534	applyMap(); // Now remap each shader to the new IDs we've come up with
1535	if (errorLatch) return;
1536	}
1537	}
1538
1539	// remap from a memory image
1540	void spirvbin_t::remap(std::vector<std::uint32_t>& in_spv, const std::vector<std::string>& whiteListStrings,
1541	std::uint32_t opts)
1542	{
1543	stripWhiteList = whiteListStrings;
1544	spv.swap(x&: in_spv);
1545	remap(opts);
1546	spv.swap(x&: in_spv);
1547	}
1548
1549	// remap from a memory image - legacy interface without white list
1550	void spirvbin_t::remap(std::vector<std::uint32_t>& in_spv, std::uint32_t opts)
1551	{
1552	stripWhiteList.clear();
1553	spv.swap(x&: in_spv);
1554	remap(opts);
1555	spv.swap(x&: in_spv);
1556	}
1557
1558	} // namespace SPV
1559
1560