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