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