blob: e8031d0229babafe238466abf7784c6afea2ab7c [file] [log] [blame]
John Kessenich140f3df2015-06-26 16:58:36 -06001//
John Kessenich927608b2017-01-06 12:34:14 -07002// Copyright (C) 2015 LunarG, Inc.
John Kessenich140f3df2015-06-26 16:58:36 -06003//
John Kessenich927608b2017-01-06 12:34:14 -07004// All rights reserved.
John Kessenich140f3df2015-06-26 16:58:36 -06005//
John Kessenich927608b2017-01-06 12:34:14 -07006// Redistribution and use in source and binary forms, with or without
7// modification, are permitted provided that the following conditions
8// are met:
John Kessenich140f3df2015-06-26 16:58:36 -06009//
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//
John Kessenich927608b2017-01-06 12:34:14 -070022// 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.
John Kessenich140f3df2015-06-26 16:58:36 -060034//
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>
Andrew Woloszyn8b64fa52015-08-17 11:39:38 -040045#include "../glslang/Include/Common.h"
John Kessenich140f3df2015-06-26 16:58:36 -060046
47namespace 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(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 + 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);
John Kessenich5e4b1242015-08-06 22:53:06 -060086 // TODO: case spv::OpTypeImage:
87 // TODO: case spv::OpTypeSampledImage:
John Kessenich140f3df2015-06-26 16:58:36 -060088 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
John Kessenichecba76f2017-01-06 00:34:48 -0700106 case spv::OpTypeMatrix: // ...
107 case spv::OpTypeSampler: // ...
108 case spv::OpTypeArray: // ...
109 case spv::OpTypeRuntimeArray: // ...
John Kessenich140f3df2015-06-26 16:58:36 -0600110 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
steve-lunarg811d9f42016-08-17 08:33:49 -0600130 // 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(typeStart);
137
138 switch (opCode) {
139 case spv::OpTypeInt: // fall through...
140 case spv::OpTypeFloat: return (spv[typeStart+2]+31)/32;
141 default:
142 return 0;
143 }
144 }
145
146 // Looks up the type of a given const or variable ID, and
147 // returns its size in 32-bit words.
148 unsigned spirvbin_t::idTypeSizeInWords(spv::Id id) const
149 {
150 const auto tid_it = idTypeSizeMap.find(id);
151 if (tid_it == idTypeSizeMap.end())
152 error("type size for ID not found");
153
154 return tid_it->second;
155 }
156
John Kessenich140f3df2015-06-26 16:58:36 -0600157 // Is this an opcode we should remove when using --strip?
158 bool spirvbin_t::isStripOp(spv::Op opCode) const
159 {
160 switch (opCode) {
161 case spv::OpSource:
162 case spv::OpSourceExtension:
163 case spv::OpName:
164 case spv::OpMemberName:
165 case spv::OpLine: return true;
166 default: return false;
167 }
168 }
169
steve-lunarg811d9f42016-08-17 08:33:49 -0600170 // Return true if this opcode is flow control
GregF8548bab2016-02-01 16:44:57 -0700171 bool spirvbin_t::isFlowCtrl(spv::Op opCode) const
John Kessenich140f3df2015-06-26 16:58:36 -0600172 {
173 switch (opCode) {
174 case spv::OpBranchConditional:
GregF8548bab2016-02-01 16:44:57 -0700175 case spv::OpBranch:
176 case spv::OpSwitch:
John Kessenich140f3df2015-06-26 16:58:36 -0600177 case spv::OpLoopMerge:
GregF8548bab2016-02-01 16:44:57 -0700178 case spv::OpSelectionMerge:
179 case spv::OpLabel:
180 case spv::OpFunction:
181 case spv::OpFunctionEnd: return true;
John Kessenich140f3df2015-06-26 16:58:36 -0600182 default: return false;
183 }
184 }
185
steve-lunarg811d9f42016-08-17 08:33:49 -0600186 // Return true if this opcode defines a type
John Kessenich140f3df2015-06-26 16:58:36 -0600187 bool spirvbin_t::isTypeOp(spv::Op opCode) const
188 {
189 switch (opCode) {
190 case spv::OpTypeVoid:
191 case spv::OpTypeBool:
192 case spv::OpTypeInt:
193 case spv::OpTypeFloat:
194 case spv::OpTypeVector:
195 case spv::OpTypeMatrix:
John Kessenich5e4b1242015-08-06 22:53:06 -0600196 case spv::OpTypeImage:
John Kessenich140f3df2015-06-26 16:58:36 -0600197 case spv::OpTypeSampler:
John Kessenich140f3df2015-06-26 16:58:36 -0600198 case spv::OpTypeArray:
199 case spv::OpTypeRuntimeArray:
200 case spv::OpTypeStruct:
201 case spv::OpTypeOpaque:
202 case spv::OpTypePointer:
203 case spv::OpTypeFunction:
204 case spv::OpTypeEvent:
205 case spv::OpTypeDeviceEvent:
206 case spv::OpTypeReserveId:
207 case spv::OpTypeQueue:
Steve3573f2e2015-08-11 09:20:14 -0600208 case spv::OpTypeSampledImage:
John Kessenich140f3df2015-06-26 16:58:36 -0600209 case spv::OpTypePipe: return true;
210 default: return false;
211 }
212 }
213
steve-lunarg811d9f42016-08-17 08:33:49 -0600214 // Return true if this opcode defines a constant
John Kessenich140f3df2015-06-26 16:58:36 -0600215 bool spirvbin_t::isConstOp(spv::Op opCode) const
216 {
217 switch (opCode) {
John Kessenich5e4b1242015-08-06 22:53:06 -0600218 case spv::OpConstantNull: error("unimplemented constant type");
John Kessenich140f3df2015-06-26 16:58:36 -0600219 case spv::OpConstantSampler: error("unimplemented constant type");
220
221 case spv::OpConstantTrue:
222 case spv::OpConstantFalse:
John Kessenich140f3df2015-06-26 16:58:36 -0600223 case spv::OpConstantComposite:
224 case spv::OpConstant: return true;
225 default: return false;
226 }
227 }
228
229 const auto inst_fn_nop = [](spv::Op, unsigned) { return false; };
230 const auto op_fn_nop = [](spv::Id&) { };
231
232 // g++ doesn't like these defined in the class proper in an anonymous namespace.
233 // Dunno why. Also MSVC doesn't like the constexpr keyword. Also dunno why.
234 // Defining them externally seems to please both compilers, so, here they are.
235 const spv::Id spirvbin_t::unmapped = spv::Id(-10000);
236 const spv::Id spirvbin_t::unused = spv::Id(-10001);
237 const int spirvbin_t::header_size = 5;
238
239 spv::Id spirvbin_t::nextUnusedId(spv::Id id)
240 {
241 while (isNewIdMapped(id)) // search for an unused ID
242 ++id;
243
244 return id;
245 }
246
247 spv::Id spirvbin_t::localId(spv::Id id, spv::Id newId)
248 {
249 assert(id != spv::NoResult && newId != spv::NoResult);
250
251 if (id >= idMapL.size())
252 idMapL.resize(id+1, unused);
253
254 if (newId != unmapped && newId != unused) {
255 if (isOldIdUnused(id))
256 error(std::string("ID unused in module: ") + std::to_string(id));
257
258 if (!isOldIdUnmapped(id))
259 error(std::string("ID already mapped: ") + std::to_string(id) + " -> "
260 + std::to_string(localId(id)));
261
262 if (isNewIdMapped(newId))
263 error(std::string("ID already used in module: ") + std::to_string(newId));
264
265 msg(4, 4, std::string("map: ") + std::to_string(id) + " -> " + std::to_string(newId));
266 setMapped(newId);
267 largestNewId = std::max(largestNewId, newId);
268 }
269
270 return idMapL[id] = newId;
271 }
272
273 // Parse a literal string from the SPIR binary and return it as an std::string
274 // Due to C++11 RValue references, this doesn't copy the result string.
275 std::string spirvbin_t::literalString(unsigned word) const
276 {
277 std::string literal;
278
279 literal.reserve(16);
280
281 const char* bytes = reinterpret_cast<const char*>(spv.data() + word);
282
283 while (bytes && *bytes)
284 literal += *bytes++;
285
286 return literal;
287 }
288
John Kessenich140f3df2015-06-26 16:58:36 -0600289 void spirvbin_t::applyMap()
290 {
291 msg(3, 2, std::string("Applying map: "));
292
293 // Map local IDs through the ID map
294 process(inst_fn_nop, // ignore instructions
295 [this](spv::Id& id) {
296 id = localId(id);
297 assert(id != unused && id != unmapped);
298 }
299 );
300 }
301
John Kessenich140f3df2015-06-26 16:58:36 -0600302 // Find free IDs for anything we haven't mapped
303 void spirvbin_t::mapRemainder()
304 {
305 msg(3, 2, std::string("Remapping remainder: "));
306
307 spv::Id unusedId = 1; // can't use 0: that's NoResult
308 spirword_t maxBound = 0;
309
310 for (spv::Id id = 0; id < idMapL.size(); ++id) {
311 if (isOldIdUnused(id))
312 continue;
313
314 // Find a new mapping for any used but unmapped IDs
315 if (isOldIdUnmapped(id))
316 localId(id, unusedId = nextUnusedId(unusedId));
317
318 if (isOldIdUnmapped(id))
319 error(std::string("old ID not mapped: ") + std::to_string(id));
320
321 // Track max bound
322 maxBound = std::max(maxBound, localId(id) + 1);
323 }
324
325 bound(maxBound); // reset header ID bound to as big as it now needs to be
326 }
327
steve-lunarg297754c2016-12-09 11:13:23 -0700328 // Mark debug instructions for stripping
John Kessenich140f3df2015-06-26 16:58:36 -0600329 void spirvbin_t::stripDebug()
330 {
steve-lunarg297754c2016-12-09 11:13:23 -0700331 // Strip instructions in the stripOp set: debug info.
John Kessenich140f3df2015-06-26 16:58:36 -0600332 process(
333 [&](spv::Op opCode, unsigned start) {
334 // remember opcodes we want to strip later
335 if (isStripOp(opCode))
336 stripInst(start);
337 return true;
338 },
339 op_fn_nop);
340 }
341
steve-lunarg297754c2016-12-09 11:13:23 -0700342 // Mark instructions that refer to now-removed IDs for stripping
343 void spirvbin_t::stripDeadRefs()
344 {
345 process(
346 [&](spv::Op opCode, unsigned start) {
347 // strip opcodes pointing to removed data
348 switch (opCode) {
349 case spv::OpName:
350 case spv::OpMemberName:
351 case spv::OpDecorate:
352 case spv::OpMemberDecorate:
353 if (idPosR.find(asId(start+1)) == idPosR.end())
354 stripInst(start);
355 break;
John Kessenichecba76f2017-01-06 00:34:48 -0700356 default:
steve-lunarg297754c2016-12-09 11:13:23 -0700357 break; // leave it alone
358 }
359
360 return true;
361 },
362 op_fn_nop);
363
364 strip();
365 }
366
367 // Update local maps of ID, type, etc positions
John Kessenich140f3df2015-06-26 16:58:36 -0600368 void spirvbin_t::buildLocalMaps()
369 {
370 msg(2, 2, std::string("build local maps: "));
371
372 mapped.clear();
373 idMapL.clear();
374// preserve nameMap, so we don't clear that.
375 fnPos.clear();
John Kessenich140f3df2015-06-26 16:58:36 -0600376 fnCalls.clear();
377 typeConstPos.clear();
steve-lunarg811d9f42016-08-17 08:33:49 -0600378 idPosR.clear();
John Kessenich140f3df2015-06-26 16:58:36 -0600379 entryPoint = spv::NoResult;
380 largestNewId = 0;
381
382 idMapL.resize(bound(), unused);
383
384 int fnStart = 0;
385 spv::Id fnRes = spv::NoResult;
386
387 // build local Id and name maps
388 process(
389 [&](spv::Op opCode, unsigned start) {
steve-lunarg811d9f42016-08-17 08:33:49 -0600390 unsigned word = start+1;
391 spv::Id typeId = spv::NoResult;
392
393 if (spv::InstructionDesc[opCode].hasType())
394 typeId = asId(word++);
395
396 // If there's a result ID, remember the size of its type
397 if (spv::InstructionDesc[opCode].hasResult()) {
398 const spv::Id resultId = asId(word++);
399 idPosR[resultId] = start;
John Kessenichecba76f2017-01-06 00:34:48 -0700400
steve-lunarg811d9f42016-08-17 08:33:49 -0600401 if (typeId != spv::NoResult) {
402 const unsigned idTypeSize = typeSizeInWords(typeId);
403
404 if (idTypeSize != 0)
405 idTypeSizeMap[resultId] = idTypeSize;
406 }
407 }
408
John Kessenich140f3df2015-06-26 16:58:36 -0600409 if (opCode == spv::Op::OpName) {
410 const spv::Id target = asId(start+1);
411 const std::string name = literalString(start+2);
412 nameMap[name] = target;
413
414 } else if (opCode == spv::Op::OpFunctionCall) {
415 ++fnCalls[asId(start + 3)];
416 } else if (opCode == spv::Op::OpEntryPoint) {
417 entryPoint = asId(start + 2);
418 } else if (opCode == spv::Op::OpFunction) {
419 if (fnStart != 0)
420 error("nested function found");
421 fnStart = start;
422 fnRes = asId(start + 2);
423 } else if (opCode == spv::Op::OpFunctionEnd) {
424 assert(fnRes != spv::NoResult);
425 if (fnStart == 0)
426 error("function end without function start");
427 fnPos[fnRes] = range_t(fnStart, start + asWordCount(start));
428 fnStart = 0;
429 } else if (isConstOp(opCode)) {
430 assert(asId(start + 2) != spv::NoResult);
431 typeConstPos.insert(start);
John Kessenich140f3df2015-06-26 16:58:36 -0600432 } else if (isTypeOp(opCode)) {
433 assert(asId(start + 1) != spv::NoResult);
434 typeConstPos.insert(start);
John Kessenich140f3df2015-06-26 16:58:36 -0600435 }
436
437 return false;
438 },
439
440 [this](spv::Id& id) { localId(id, unmapped); }
441 );
442 }
443
444 // Validate the SPIR header
445 void spirvbin_t::validate() const
446 {
447 msg(2, 2, std::string("validating: "));
448
449 if (spv.size() < header_size)
450 error("file too short: ");
451
452 if (magic() != spv::MagicNumber)
453 error("bad magic number");
454
455 // field 1 = version
456 // field 2 = generator magic
457 // field 3 = result <id> bound
458
459 if (schemaNum() != 0)
460 error("bad schema, must be 0");
461 }
462
John Kessenich140f3df2015-06-26 16:58:36 -0600463 int spirvbin_t::processInstruction(unsigned word, instfn_t instFn, idfn_t idFn)
464 {
465 const auto instructionStart = word;
466 const unsigned wordCount = asWordCount(instructionStart);
John Kessenich140f3df2015-06-26 16:58:36 -0600467 const int nextInst = word++ + wordCount;
LoopDawg65c2eed2017-05-18 16:13:04 -0600468 spv::Op opCode = asOpCode(instructionStart);
John Kessenich140f3df2015-06-26 16:58:36 -0600469
470 if (nextInst > int(spv.size()))
471 error("spir instruction terminated too early");
472
473 // Base for computing number of operands; will be updated as more is learned
474 unsigned numOperands = wordCount - 1;
475
476 if (instFn(opCode, instructionStart))
477 return nextInst;
478
479 // Read type and result ID from instruction desc table
480 if (spv::InstructionDesc[opCode].hasType()) {
481 idFn(asId(word++));
482 --numOperands;
483 }
484
485 if (spv::InstructionDesc[opCode].hasResult()) {
486 idFn(asId(word++));
487 --numOperands;
488 }
489
490 // Extended instructions: currently, assume everything is an ID.
491 // TODO: add whatever data we need for exceptions to that
492 if (opCode == spv::OpExtInst) {
493 word += 2; // instruction set, and instruction from set
494 numOperands -= 2;
495
496 for (unsigned op=0; op < numOperands; ++op)
497 idFn(asId(word++)); // ID
498
499 return nextInst;
500 }
501
steve-lunarg811d9f42016-08-17 08:33:49 -0600502 // Circular buffer so we can look back at previous unmapped values during the mapping pass.
503 static const unsigned idBufferSize = 4;
504 spv::Id idBuffer[idBufferSize];
505 unsigned idBufferPos = 0;
506
John Kessenich140f3df2015-06-26 16:58:36 -0600507 // Store IDs from instruction in our map
John Kessenich6c292d32016-02-15 20:58:50 -0700508 for (int op = 0; numOperands > 0; ++op, --numOperands) {
LoopDawg65c2eed2017-05-18 16:13:04 -0600509 // SpecConstantOp is special: it includes the operands of another opcode which is
510 // given as a literal in the 3rd word. We will switch over to pretending that the
511 // opcode being processed is the literal opcode value of the SpecConstantOp. See the
512 // SPIRV spec for details. This way we will handle IDs and literals as appropriate for
513 // the embedded op.
514 if (opCode == spv::OpSpecConstantOp) {
515 if (op == 0) {
516 opCode = asOpCode(word++); // this is the opcode embedded in the SpecConstantOp.
517 --numOperands;
518 }
519 }
520
John Kessenich140f3df2015-06-26 16:58:36 -0600521 switch (spv::InstructionDesc[opCode].operands.getClass(op)) {
522 case spv::OperandId:
Pyry Haulosb93e3a32016-07-22 09:57:28 -0700523 case spv::OperandScope:
524 case spv::OperandMemorySemantics:
steve-lunarg811d9f42016-08-17 08:33:49 -0600525 idBuffer[idBufferPos] = asId(word);
526 idBufferPos = (idBufferPos + 1) % idBufferSize;
John Kessenich140f3df2015-06-26 16:58:36 -0600527 idFn(asId(word++));
528 break;
529
John Kessenich140f3df2015-06-26 16:58:36 -0600530 case spv::OperandVariableIds:
531 for (unsigned i = 0; i < numOperands; ++i)
532 idFn(asId(word++));
533 return nextInst;
534
535 case spv::OperandVariableLiterals:
Steve465a1462015-07-15 14:34:35 -0600536 // for clarity
537 // if (opCode == spv::OpDecorate && asDecoration(word - 1) == spv::DecorationBuiltIn) {
538 // ++word;
539 // --numOperands;
540 // }
541 // word += numOperands;
John Kessenich140f3df2015-06-26 16:58:36 -0600542 return nextInst;
543
steve-lunarg811d9f42016-08-17 08:33:49 -0600544 case spv::OperandVariableLiteralId: {
545 if (opCode == OpSwitch) {
546 // word-2 is the position of the selector ID. OpSwitch Literals match its type.
547 // In case the IDs are currently being remapped, we get the word[-2] ID from
548 // the circular idBuffer.
549 const unsigned literalSizePos = (idBufferPos+idBufferSize-2) % idBufferSize;
550 const unsigned literalSize = idTypeSizeInWords(idBuffer[literalSizePos]);
551 const unsigned numLiteralIdPairs = (nextInst-word) / (1+literalSize);
552
553 for (unsigned arg=0; arg<numLiteralIdPairs; ++arg) {
554 word += literalSize; // literal
555 idFn(asId(word++)); // label
556 }
557 } else {
558 assert(0); // currentely, only OpSwitch uses OperandVariableLiteralId
John Kessenich140f3df2015-06-26 16:58:36 -0600559 }
steve-lunarg811d9f42016-08-17 08:33:49 -0600560
John Kessenich140f3df2015-06-26 16:58:36 -0600561 return nextInst;
steve-lunarg811d9f42016-08-17 08:33:49 -0600562 }
John Kessenich140f3df2015-06-26 16:58:36 -0600563
GregF8548bab2016-02-01 16:44:57 -0700564 case spv::OperandLiteralString: {
565 const int stringWordCount = literalStringWords(literalString(word));
566 word += stringWordCount;
567 numOperands -= (stringWordCount-1); // -1 because for() header post-decrements
568 break;
569 }
570
571 // Execution mode might have extra literal operands. Skip them.
572 case spv::OperandExecutionMode:
John Kessenich140f3df2015-06-26 16:58:36 -0600573 return nextInst;
574
GregF8548bab2016-02-01 16:44:57 -0700575 // Single word operands we simply ignore, as they hold no IDs
John Kessenich140f3df2015-06-26 16:58:36 -0600576 case spv::OperandLiteralNumber:
577 case spv::OperandSource:
578 case spv::OperandExecutionModel:
579 case spv::OperandAddressing:
580 case spv::OperandMemory:
John Kessenich140f3df2015-06-26 16:58:36 -0600581 case spv::OperandStorage:
582 case spv::OperandDimensionality:
GregF8548bab2016-02-01 16:44:57 -0700583 case spv::OperandSamplerAddressingMode:
584 case spv::OperandSamplerFilterMode:
585 case spv::OperandSamplerImageFormat:
586 case spv::OperandImageChannelOrder:
587 case spv::OperandImageChannelDataType:
GregF3bb040b2016-01-05 08:41:59 -0700588 case spv::OperandImageOperands:
GregF8548bab2016-02-01 16:44:57 -0700589 case spv::OperandFPFastMath:
590 case spv::OperandFPRoundingMode:
591 case spv::OperandLinkageType:
592 case spv::OperandAccessQualifier:
593 case spv::OperandFuncParamAttr:
John Kessenich140f3df2015-06-26 16:58:36 -0600594 case spv::OperandDecoration:
595 case spv::OperandBuiltIn:
596 case spv::OperandSelect:
597 case spv::OperandLoop:
598 case spv::OperandFunction:
John Kessenich140f3df2015-06-26 16:58:36 -0600599 case spv::OperandMemoryAccess:
John Kessenich140f3df2015-06-26 16:58:36 -0600600 case spv::OperandGroupOperation:
601 case spv::OperandKernelEnqueueFlags:
602 case spv::OperandKernelProfilingInfo:
GregF8548bab2016-02-01 16:44:57 -0700603 case spv::OperandCapability:
John Kessenich140f3df2015-06-26 16:58:36 -0600604 ++word;
605 break;
606
607 default:
GregF036a7942016-01-05 16:41:29 -0700608 assert(0 && "Unhandled Operand Class");
John Kessenich140f3df2015-06-26 16:58:36 -0600609 break;
610 }
611 }
612
613 return nextInst;
614 }
615
616 // Make a pass over all the instructions and process them given appropriate functions
617 spirvbin_t& spirvbin_t::process(instfn_t instFn, idfn_t idFn, unsigned begin, unsigned end)
618 {
619 // For efficiency, reserve name map space. It can grow if needed.
620 nameMap.reserve(32);
621
622 // If begin or end == 0, use defaults
623 begin = (begin == 0 ? header_size : begin);
624 end = (end == 0 ? unsigned(spv.size()) : end);
625
626 // basic parsing and InstructionDesc table borrowed from SpvDisassemble.cpp...
627 unsigned nextInst = unsigned(spv.size());
628
629 for (unsigned word = begin; word < end; word = nextInst)
630 nextInst = processInstruction(word, instFn, idFn);
631
632 return *this;
633 }
634
635 // Apply global name mapping to a single module
636 void spirvbin_t::mapNames()
637 {
638 static const std::uint32_t softTypeIdLimit = 3011; // small prime. TODO: get from options
639 static const std::uint32_t firstMappedID = 3019; // offset into ID space
640
641 for (const auto& name : nameMap) {
642 std::uint32_t hashval = 1911;
643 for (const char c : name.first)
644 hashval = hashval * 1009 + c;
645
646 if (isOldIdUnmapped(name.second))
647 localId(name.second, nextUnusedId(hashval % softTypeIdLimit + firstMappedID));
648 }
649 }
650
651 // Map fn contents to IDs of similar functions in other modules
652 void spirvbin_t::mapFnBodies()
653 {
654 static const std::uint32_t softTypeIdLimit = 19071; // small prime. TODO: get from options
655 static const std::uint32_t firstMappedID = 6203; // offset into ID space
656
657 // Initial approach: go through some high priority opcodes first and assign them
658 // hash values.
659
660 spv::Id fnId = spv::NoResult;
661 std::vector<unsigned> instPos;
662 instPos.reserve(unsigned(spv.size()) / 16); // initial estimate; can grow if needed.
663
664 // Build local table of instruction start positions
665 process(
666 [&](spv::Op, unsigned start) { instPos.push_back(start); return true; },
667 op_fn_nop);
668
669 // Window size for context-sensitive canonicalization values
Eric Engestrom6a6d6dd2016-04-03 01:17:13 +0100670 // Empirical best size from a single data set. TODO: Would be a good tunable.
GregF8548bab2016-02-01 16:44:57 -0700671 // We essentially perform a little convolution around each instruction,
John Kessenich140f3df2015-06-26 16:58:36 -0600672 // to capture the flavor of nearby code, to hopefully match to similar
673 // code in other modules.
674 static const unsigned windowSize = 2;
675
676 for (unsigned entry = 0; entry < unsigned(instPos.size()); ++entry) {
677 const unsigned start = instPos[entry];
678 const spv::Op opCode = asOpCode(start);
679
680 if (opCode == spv::OpFunction)
681 fnId = asId(start + 2);
682
683 if (opCode == spv::OpFunctionEnd)
684 fnId = spv::NoResult;
685
686 if (fnId != spv::NoResult) { // if inside a function
687 if (spv::InstructionDesc[opCode].hasResult()) {
688 const unsigned word = start + (spv::InstructionDesc[opCode].hasType() ? 2 : 1);
689 const spv::Id resId = asId(word);
690 std::uint32_t hashval = fnId * 17; // small prime
691
692 for (unsigned i = entry-1; i >= entry-windowSize; --i) {
693 if (asOpCode(instPos[i]) == spv::OpFunction)
694 break;
695 hashval = hashval * 30103 + asOpCodeHash(instPos[i]); // 30103 = semiarbitrary prime
696 }
697
698 for (unsigned i = entry; i <= entry + windowSize; ++i) {
699 if (asOpCode(instPos[i]) == spv::OpFunctionEnd)
700 break;
701 hashval = hashval * 30103 + asOpCodeHash(instPos[i]); // 30103 = semiarbitrary prime
702 }
703
704 if (isOldIdUnmapped(resId))
705 localId(resId, nextUnusedId(hashval % softTypeIdLimit + firstMappedID));
706 }
707 }
708 }
709
710 spv::Op thisOpCode(spv::OpNop);
711 std::unordered_map<int, int> opCounter;
712 int idCounter(0);
713 fnId = spv::NoResult;
714
715 process(
716 [&](spv::Op opCode, unsigned start) {
717 switch (opCode) {
718 case spv::OpFunction:
719 // Reset counters at each function
720 idCounter = 0;
721 opCounter.clear();
722 fnId = asId(start + 2);
723 break;
724
John Kessenich5e4b1242015-08-06 22:53:06 -0600725 case spv::OpImageSampleImplicitLod:
726 case spv::OpImageSampleExplicitLod:
727 case spv::OpImageSampleDrefImplicitLod:
728 case spv::OpImageSampleDrefExplicitLod:
729 case spv::OpImageSampleProjImplicitLod:
730 case spv::OpImageSampleProjExplicitLod:
731 case spv::OpImageSampleProjDrefImplicitLod:
732 case spv::OpImageSampleProjDrefExplicitLod:
John Kessenich140f3df2015-06-26 16:58:36 -0600733 case spv::OpDot:
734 case spv::OpCompositeExtract:
735 case spv::OpCompositeInsert:
736 case spv::OpVectorShuffle:
737 case spv::OpLabel:
738 case spv::OpVariable:
739
740 case spv::OpAccessChain:
741 case spv::OpLoad:
742 case spv::OpStore:
743 case spv::OpCompositeConstruct:
744 case spv::OpFunctionCall:
745 ++opCounter[opCode];
746 idCounter = 0;
747 thisOpCode = opCode;
748 break;
749 default:
750 thisOpCode = spv::OpNop;
751 }
752
753 return false;
754 },
755
756 [&](spv::Id& id) {
757 if (thisOpCode != spv::OpNop) {
758 ++idCounter;
759 const std::uint32_t hashval = opCounter[thisOpCode] * thisOpCode * 50047 + idCounter + fnId * 117;
760
761 if (isOldIdUnmapped(id))
762 localId(id, nextUnusedId(hashval % softTypeIdLimit + firstMappedID));
763 }
764 });
765 }
766
767 // EXPERIMENTAL: forward IO and uniform load/stores into operands
768 // This produces invalid Schema-0 SPIRV
769 void spirvbin_t::forwardLoadStores()
770 {
771 idset_t fnLocalVars; // set of function local vars
772 idmap_t idMap; // Map of load result IDs to what they load
773
774 // EXPERIMENTAL: Forward input and access chain loads into consumptions
775 process(
776 [&](spv::Op opCode, unsigned start) {
777 // Add inputs and uniforms to the map
John Kessenich5e4b1242015-08-06 22:53:06 -0600778 if ((opCode == spv::OpVariable && asWordCount(start) == 4) &&
John Kessenich140f3df2015-06-26 16:58:36 -0600779 (spv[start+3] == spv::StorageClassUniform ||
780 spv[start+3] == spv::StorageClassUniformConstant ||
781 spv[start+3] == spv::StorageClassInput))
782 fnLocalVars.insert(asId(start+2));
783
784 if (opCode == spv::OpAccessChain && fnLocalVars.count(asId(start+3)) > 0)
785 fnLocalVars.insert(asId(start+2));
786
787 if (opCode == spv::OpLoad && fnLocalVars.count(asId(start+3)) > 0) {
788 idMap[asId(start+2)] = asId(start+3);
789 stripInst(start);
790 }
791
792 return false;
793 },
794
795 [&](spv::Id& id) { if (idMap.find(id) != idMap.end()) id = idMap[id]; }
796 );
797
798 // EXPERIMENTAL: Implicit output stores
799 fnLocalVars.clear();
800 idMap.clear();
801
802 process(
803 [&](spv::Op opCode, unsigned start) {
804 // Add inputs and uniforms to the map
John Kessenich5e4b1242015-08-06 22:53:06 -0600805 if ((opCode == spv::OpVariable && asWordCount(start) == 4) &&
John Kessenich140f3df2015-06-26 16:58:36 -0600806 (spv[start+3] == spv::StorageClassOutput))
807 fnLocalVars.insert(asId(start+2));
808
809 if (opCode == spv::OpStore && fnLocalVars.count(asId(start+1)) > 0) {
810 idMap[asId(start+2)] = asId(start+1);
811 stripInst(start);
812 }
813
814 return false;
815 },
816 op_fn_nop);
817
818 process(
819 inst_fn_nop,
820 [&](spv::Id& id) { if (idMap.find(id) != idMap.end()) id = idMap[id]; }
821 );
822
823 strip(); // strip out data we decided to eliminate
824 }
825
GregF8548bab2016-02-01 16:44:57 -0700826 // optimize loads and stores
John Kessenich140f3df2015-06-26 16:58:36 -0600827 void spirvbin_t::optLoadStore()
828 {
GregF8548bab2016-02-01 16:44:57 -0700829 idset_t fnLocalVars; // candidates for removal (only locals)
830 idmap_t idMap; // Map of load result IDs to what they load
831 blockmap_t blockMap; // Map of IDs to blocks they first appear in
832 int blockNum = 0; // block count, to avoid crossing flow control
John Kessenich140f3df2015-06-26 16:58:36 -0600833
834 // Find all the function local pointers stored at most once, and not via access chains
835 process(
836 [&](spv::Op opCode, unsigned start) {
837 const int wordCount = asWordCount(start);
838
GregF8548bab2016-02-01 16:44:57 -0700839 // Count blocks, so we can avoid crossing flow control
840 if (isFlowCtrl(opCode))
841 ++blockNum;
842
John Kessenich140f3df2015-06-26 16:58:36 -0600843 // Add local variables to the map
GregF796e15a2016-01-05 13:00:04 -0700844 if ((opCode == spv::OpVariable && spv[start+3] == spv::StorageClassFunction && asWordCount(start) == 4)) {
John Kessenich140f3df2015-06-26 16:58:36 -0600845 fnLocalVars.insert(asId(start+2));
GregF796e15a2016-01-05 13:00:04 -0700846 return true;
847 }
John Kessenich140f3df2015-06-26 16:58:36 -0600848
849 // Ignore process vars referenced via access chain
850 if ((opCode == spv::OpAccessChain || opCode == spv::OpInBoundsAccessChain) && fnLocalVars.count(asId(start+3)) > 0) {
851 fnLocalVars.erase(asId(start+3));
852 idMap.erase(asId(start+3));
GregF796e15a2016-01-05 13:00:04 -0700853 return true;
John Kessenich140f3df2015-06-26 16:58:36 -0600854 }
855
856 if (opCode == spv::OpLoad && fnLocalVars.count(asId(start+3)) > 0) {
GregF8548bab2016-02-01 16:44:57 -0700857 const spv::Id varId = asId(start+3);
858
859 // Avoid loads before stores
860 if (idMap.find(varId) == idMap.end()) {
861 fnLocalVars.erase(varId);
862 idMap.erase(varId);
John Kessenich140f3df2015-06-26 16:58:36 -0600863 }
864
865 // don't do for volatile references
866 if (wordCount > 4 && (spv[start+4] & spv::MemoryAccessVolatileMask)) {
GregF8548bab2016-02-01 16:44:57 -0700867 fnLocalVars.erase(varId);
868 idMap.erase(varId);
John Kessenich140f3df2015-06-26 16:58:36 -0600869 }
GregF8548bab2016-02-01 16:44:57 -0700870
871 // Handle flow control
872 if (blockMap.find(varId) == blockMap.end()) {
873 blockMap[varId] = blockNum; // track block we found it in.
874 } else if (blockMap[varId] != blockNum) {
875 fnLocalVars.erase(varId); // Ignore if crosses flow control
876 idMap.erase(varId);
877 }
878
GregF796e15a2016-01-05 13:00:04 -0700879 return true;
John Kessenich140f3df2015-06-26 16:58:36 -0600880 }
881
882 if (opCode == spv::OpStore && fnLocalVars.count(asId(start+1)) > 0) {
GregF8548bab2016-02-01 16:44:57 -0700883 const spv::Id varId = asId(start+1);
884
885 if (idMap.find(varId) == idMap.end()) {
886 idMap[varId] = asId(start+2);
John Kessenich140f3df2015-06-26 16:58:36 -0600887 } else {
888 // Remove if it has more than one store to the same pointer
GregF8548bab2016-02-01 16:44:57 -0700889 fnLocalVars.erase(varId);
890 idMap.erase(varId);
John Kessenich140f3df2015-06-26 16:58:36 -0600891 }
892
893 // don't do for volatile references
894 if (wordCount > 3 && (spv[start+3] & spv::MemoryAccessVolatileMask)) {
895 fnLocalVars.erase(asId(start+3));
896 idMap.erase(asId(start+3));
897 }
GregF8548bab2016-02-01 16:44:57 -0700898
899 // Handle flow control
900 if (blockMap.find(varId) == blockMap.end()) {
901 blockMap[varId] = blockNum; // track block we found it in.
902 } else if (blockMap[varId] != blockNum) {
903 fnLocalVars.erase(varId); // Ignore if crosses flow control
904 idMap.erase(varId);
905 }
906
GregF796e15a2016-01-05 13:00:04 -0700907 return true;
John Kessenich140f3df2015-06-26 16:58:36 -0600908 }
909
GregF796e15a2016-01-05 13:00:04 -0700910 return false;
John Kessenich140f3df2015-06-26 16:58:36 -0600911 },
GregF796e15a2016-01-05 13:00:04 -0700912
913 // If local var id used anywhere else, don't eliminate
John Kessenichecba76f2017-01-06 00:34:48 -0700914 [&](spv::Id& id) {
GregF796e15a2016-01-05 13:00:04 -0700915 if (fnLocalVars.count(id) > 0) {
916 fnLocalVars.erase(id);
917 idMap.erase(id);
918 }
919 }
920 );
John Kessenich140f3df2015-06-26 16:58:36 -0600921
922 process(
923 [&](spv::Op opCode, unsigned start) {
924 if (opCode == spv::OpLoad && fnLocalVars.count(asId(start+3)) > 0)
925 idMap[asId(start+2)] = idMap[asId(start+3)];
926 return false;
927 },
928 op_fn_nop);
929
GregF8548bab2016-02-01 16:44:57 -0700930 // Chase replacements to their origins, in case there is a chain such as:
931 // 2 = store 1
932 // 3 = load 2
933 // 4 = store 3
934 // 5 = load 4
935 // We want to replace uses of 5 with 1.
936 for (const auto& idPair : idMap) {
937 spv::Id id = idPair.first;
938 while (idMap.find(id) != idMap.end()) // Chase to end of chain
939 id = idMap[id];
940
941 idMap[idPair.first] = id; // replace with final result
942 }
943
John Kessenich140f3df2015-06-26 16:58:36 -0600944 // Remove the load/store/variables for the ones we've discovered
945 process(
946 [&](spv::Op opCode, unsigned start) {
947 if ((opCode == spv::OpLoad && fnLocalVars.count(asId(start+3)) > 0) ||
948 (opCode == spv::OpStore && fnLocalVars.count(asId(start+1)) > 0) ||
949 (opCode == spv::OpVariable && fnLocalVars.count(asId(start+2)) > 0)) {
GregF8548bab2016-02-01 16:44:57 -0700950
John Kessenich140f3df2015-06-26 16:58:36 -0600951 stripInst(start);
952 return true;
953 }
954
955 return false;
956 },
957
GregF8548bab2016-02-01 16:44:57 -0700958 [&](spv::Id& id) {
959 if (idMap.find(id) != idMap.end()) id = idMap[id];
960 }
John Kessenich140f3df2015-06-26 16:58:36 -0600961 );
962
963 strip(); // strip out data we decided to eliminate
964 }
965
966 // remove bodies of uncalled functions
967 void spirvbin_t::dceFuncs()
968 {
969 msg(3, 2, std::string("Removing Dead Functions: "));
970
971 // TODO: There are more efficient ways to do this.
972 bool changed = true;
973
974 while (changed) {
975 changed = false;
976
977 for (auto fn = fnPos.begin(); fn != fnPos.end(); ) {
978 if (fn->first == entryPoint) { // don't DCE away the entry point!
979 ++fn;
980 continue;
981 }
982
983 const auto call_it = fnCalls.find(fn->first);
984
985 if (call_it == fnCalls.end() || call_it->second == 0) {
986 changed = true;
987 stripRange.push_back(fn->second);
John Kessenich140f3df2015-06-26 16:58:36 -0600988
989 // decrease counts of called functions
990 process(
991 [&](spv::Op opCode, unsigned start) {
992 if (opCode == spv::Op::OpFunctionCall) {
993 const auto call_it = fnCalls.find(asId(start + 3));
994 if (call_it != fnCalls.end()) {
995 if (--call_it->second <= 0)
996 fnCalls.erase(call_it);
997 }
998 }
999
1000 return true;
1001 },
1002 op_fn_nop,
1003 fn->second.first,
1004 fn->second.second);
1005
1006 fn = fnPos.erase(fn);
1007 } else ++fn;
1008 }
1009 }
1010 }
1011
1012 // remove unused function variables + decorations
1013 void spirvbin_t::dceVars()
1014 {
1015 msg(3, 2, std::string("DCE Vars: "));
1016
1017 std::unordered_map<spv::Id, int> varUseCount;
1018
1019 // Count function variable use
1020 process(
1021 [&](spv::Op opCode, unsigned start) {
GregF39d5e712016-06-03 09:53:47 -06001022 if (opCode == spv::OpVariable) {
1023 ++varUseCount[asId(start+2)];
1024 return true;
1025 } else if (opCode == spv::OpEntryPoint) {
1026 const int wordCount = asWordCount(start);
1027 for (int i = 4; i < wordCount; i++) {
1028 ++varUseCount[asId(start+i)];
1029 }
1030 return true;
1031 } else
1032 return false;
John Kessenich140f3df2015-06-26 16:58:36 -06001033 },
1034
1035 [&](spv::Id& id) { if (varUseCount[id]) ++varUseCount[id]; }
1036 );
1037
1038 // Remove single-use function variables + associated decorations and names
1039 process(
1040 [&](spv::Op opCode, unsigned start) {
steve-lunarg297754c2016-12-09 11:13:23 -07001041 spv::Id id = spv::NoResult;
1042 if (opCode == spv::OpVariable)
1043 id = asId(start+2);
1044 if (opCode == spv::OpDecorate || opCode == spv::OpName)
1045 id = asId(start+1);
1046
1047 if (id != spv::NoResult && varUseCount[id] == 1)
1048 stripInst(start);
1049
John Kessenich140f3df2015-06-26 16:58:36 -06001050 return true;
1051 },
1052 op_fn_nop);
1053 }
1054
1055 // remove unused types
1056 void spirvbin_t::dceTypes()
1057 {
1058 std::vector<bool> isType(bound(), false);
1059
1060 // for speed, make O(1) way to get to type query (map is log(n))
1061 for (const auto typeStart : typeConstPos)
1062 isType[asTypeConstId(typeStart)] = true;
1063
1064 std::unordered_map<spv::Id, int> typeUseCount;
1065
steve-lunarg811d9f42016-08-17 08:33:49 -06001066 // This is not the most efficient algorithm, but this is an offline tool, and
1067 // it's easy to write this way. Can be improved opportunistically if needed.
1068 bool changed = true;
1069 while (changed) {
1070 changed = false;
1071 strip();
1072 typeUseCount.clear();
John Kessenich140f3df2015-06-26 16:58:36 -06001073
steve-lunarg811d9f42016-08-17 08:33:49 -06001074 // Count total type usage
John Kessenich140f3df2015-06-26 16:58:36 -06001075 process(inst_fn_nop,
steve-lunarg811d9f42016-08-17 08:33:49 -06001076 [&](spv::Id& id) { if (isType[id]) ++typeUseCount[id]; }
1077 );
John Kessenich140f3df2015-06-26 16:58:36 -06001078
steve-lunarg811d9f42016-08-17 08:33:49 -06001079 // Remove single reference types
1080 for (const auto typeStart : typeConstPos) {
1081 const spv::Id typeId = asTypeConstId(typeStart);
1082 if (typeUseCount[typeId] == 1) {
1083 changed = true;
1084 --typeUseCount[typeId];
1085 stripInst(typeStart);
1086 }
John Kessenich140f3df2015-06-26 16:58:36 -06001087 }
1088 }
1089 }
1090
John Kessenich140f3df2015-06-26 16:58:36 -06001091#ifdef NOTDEF
1092 bool spirvbin_t::matchType(const spirvbin_t::globaltypes_t& globalTypes, spv::Id lt, spv::Id gt) const
1093 {
1094 // Find the local type id "lt" and global type id "gt"
1095 const auto lt_it = typeConstPosR.find(lt);
1096 if (lt_it == typeConstPosR.end())
1097 return false;
1098
1099 const auto typeStart = lt_it->second;
1100
1101 // Search for entry in global table
1102 const auto gtype = globalTypes.find(gt);
1103 if (gtype == globalTypes.end())
1104 return false;
1105
1106 const auto& gdata = gtype->second;
1107
1108 // local wordcount and opcode
1109 const int wordCount = asWordCount(typeStart);
1110 const spv::Op opCode = asOpCode(typeStart);
1111
1112 // no type match if opcodes don't match, or operand count doesn't match
1113 if (opCode != opOpCode(gdata[0]) || wordCount != opWordCount(gdata[0]))
1114 return false;
1115
1116 const unsigned numOperands = wordCount - 2; // all types have a result
1117
1118 const auto cmpIdRange = [&](range_t range) {
1119 for (int x=range.first; x<std::min(range.second, wordCount); ++x)
1120 if (!matchType(globalTypes, asId(typeStart+x), gdata[x]))
1121 return false;
1122 return true;
1123 };
1124
1125 const auto cmpConst = [&]() { return cmpIdRange(constRange(opCode)); };
1126 const auto cmpSubType = [&]() { return cmpIdRange(typeRange(opCode)); };
1127
1128 // Compare literals in range [start,end)
1129 const auto cmpLiteral = [&]() {
1130 const auto range = literalRange(opCode);
1131 return std::equal(spir.begin() + typeStart + range.first,
1132 spir.begin() + typeStart + std::min(range.second, wordCount),
1133 gdata.begin() + range.first);
1134 };
1135
1136 assert(isTypeOp(opCode) || isConstOp(opCode));
1137
1138 switch (opCode) {
1139 case spv::OpTypeOpaque: // TODO: disable until we compare the literal strings.
1140 case spv::OpTypeQueue: return false;
1141 case spv::OpTypeEvent: // fall through...
1142 case spv::OpTypeDeviceEvent: // ...
1143 case spv::OpTypeReserveId: return false;
1144 // for samplers, we don't handle the optional parameters yet
1145 case spv::OpTypeSampler: return cmpLiteral() && cmpConst() && cmpSubType() && wordCount == 8;
1146 default: return cmpLiteral() && cmpConst() && cmpSubType();
1147 }
1148 }
1149
John Kessenich140f3df2015-06-26 16:58:36 -06001150 // Look for an equivalent type in the globalTypes map
1151 spv::Id spirvbin_t::findType(const spirvbin_t::globaltypes_t& globalTypes, spv::Id lt) const
1152 {
1153 // Try a recursive type match on each in turn, and return a match if we find one
1154 for (const auto& gt : globalTypes)
1155 if (matchType(globalTypes, lt, gt.first))
1156 return gt.first;
1157
1158 return spv::NoType;
1159 }
1160#endif // NOTDEF
1161
steve-lunarg811d9f42016-08-17 08:33:49 -06001162 // Return start position in SPV of given Id. error if not found.
1163 unsigned spirvbin_t::idPos(spv::Id id) const
John Kessenich140f3df2015-06-26 16:58:36 -06001164 {
steve-lunarg811d9f42016-08-17 08:33:49 -06001165 const auto tid_it = idPosR.find(id);
1166 if (tid_it == idPosR.end())
1167 error("ID not found");
John Kessenich140f3df2015-06-26 16:58:36 -06001168
1169 return tid_it->second;
1170 }
1171
1172 // Hash types to canonical values. This can return ID collisions (it's a bit
1173 // inevitable): it's up to the caller to handle that gracefully.
1174 std::uint32_t spirvbin_t::hashType(unsigned typeStart) const
1175 {
1176 const unsigned wordCount = asWordCount(typeStart);
1177 const spv::Op opCode = asOpCode(typeStart);
1178
1179 switch (opCode) {
1180 case spv::OpTypeVoid: return 0;
1181 case spv::OpTypeBool: return 1;
1182 case spv::OpTypeInt: return 3 + (spv[typeStart+3]);
1183 case spv::OpTypeFloat: return 5;
1184 case spv::OpTypeVector:
steve-lunarg811d9f42016-08-17 08:33:49 -06001185 return 6 + hashType(idPos(spv[typeStart+2])) * (spv[typeStart+3] - 1);
John Kessenich140f3df2015-06-26 16:58:36 -06001186 case spv::OpTypeMatrix:
steve-lunarg811d9f42016-08-17 08:33:49 -06001187 return 30 + hashType(idPos(spv[typeStart+2])) * (spv[typeStart+3] - 1);
John Kessenich5e4b1242015-08-06 22:53:06 -06001188 case spv::OpTypeImage:
steve-lunarg811d9f42016-08-17 08:33:49 -06001189 return 120 + hashType(idPos(spv[typeStart+2])) +
John Kessenich140f3df2015-06-26 16:58:36 -06001190 spv[typeStart+3] + // dimensionality
John Kessenich5e4b1242015-08-06 22:53:06 -06001191 spv[typeStart+4] * 8 * 16 + // depth
John Kessenich140f3df2015-06-26 16:58:36 -06001192 spv[typeStart+5] * 4 * 16 + // arrayed
John Kessenich5e4b1242015-08-06 22:53:06 -06001193 spv[typeStart+6] * 2 * 16 + // multisampled
1194 spv[typeStart+7] * 1 * 16; // format
1195 case spv::OpTypeSampler:
John Kessenich140f3df2015-06-26 16:58:36 -06001196 return 500;
Steve3573f2e2015-08-11 09:20:14 -06001197 case spv::OpTypeSampledImage:
1198 return 502;
John Kessenich140f3df2015-06-26 16:58:36 -06001199 case spv::OpTypeArray:
steve-lunarg811d9f42016-08-17 08:33:49 -06001200 return 501 + hashType(idPos(spv[typeStart+2])) * spv[typeStart+3];
John Kessenich140f3df2015-06-26 16:58:36 -06001201 case spv::OpTypeRuntimeArray:
steve-lunarg811d9f42016-08-17 08:33:49 -06001202 return 5000 + hashType(idPos(spv[typeStart+2]));
John Kessenich140f3df2015-06-26 16:58:36 -06001203 case spv::OpTypeStruct:
1204 {
1205 std::uint32_t hash = 10000;
1206 for (unsigned w=2; w < wordCount; ++w)
steve-lunarg811d9f42016-08-17 08:33:49 -06001207 hash += w * hashType(idPos(spv[typeStart+w]));
John Kessenich140f3df2015-06-26 16:58:36 -06001208 return hash;
1209 }
1210
1211 case spv::OpTypeOpaque: return 6000 + spv[typeStart+2];
steve-lunarg811d9f42016-08-17 08:33:49 -06001212 case spv::OpTypePointer: return 100000 + hashType(idPos(spv[typeStart+3]));
John Kessenich140f3df2015-06-26 16:58:36 -06001213 case spv::OpTypeFunction:
1214 {
1215 std::uint32_t hash = 200000;
1216 for (unsigned w=2; w < wordCount; ++w)
steve-lunarg811d9f42016-08-17 08:33:49 -06001217 hash += w * hashType(idPos(spv[typeStart+w]));
John Kessenich140f3df2015-06-26 16:58:36 -06001218 return hash;
1219 }
1220
1221 case spv::OpTypeEvent: return 300000;
1222 case spv::OpTypeDeviceEvent: return 300001;
1223 case spv::OpTypeReserveId: return 300002;
1224 case spv::OpTypeQueue: return 300003;
1225 case spv::OpTypePipe: return 300004;
1226
John Kessenich5e4b1242015-08-06 22:53:06 -06001227 case spv::OpConstantNull: return 300005;
John Kessenich140f3df2015-06-26 16:58:36 -06001228 case spv::OpConstantSampler: return 300006;
1229
1230 case spv::OpConstantTrue: return 300007;
1231 case spv::OpConstantFalse: return 300008;
John Kessenich140f3df2015-06-26 16:58:36 -06001232 case spv::OpConstantComposite:
1233 {
steve-lunarg811d9f42016-08-17 08:33:49 -06001234 std::uint32_t hash = 300011 + hashType(idPos(spv[typeStart+1]));
John Kessenich140f3df2015-06-26 16:58:36 -06001235 for (unsigned w=3; w < wordCount; ++w)
steve-lunarg811d9f42016-08-17 08:33:49 -06001236 hash += w * hashType(idPos(spv[typeStart+w]));
John Kessenich140f3df2015-06-26 16:58:36 -06001237 return hash;
1238 }
1239 case spv::OpConstant:
1240 {
steve-lunarg811d9f42016-08-17 08:33:49 -06001241 std::uint32_t hash = 400011 + hashType(idPos(spv[typeStart+1]));
John Kessenich140f3df2015-06-26 16:58:36 -06001242 for (unsigned w=3; w < wordCount; ++w)
1243 hash += w * spv[typeStart+w];
1244 return hash;
1245 }
1246
1247 default:
1248 error("unknown type opcode");
1249 return 0;
1250 }
1251 }
1252
1253 void spirvbin_t::mapTypeConst()
1254 {
1255 globaltypes_t globalTypeMap;
1256
1257 msg(3, 2, std::string("Remapping Consts & Types: "));
1258
1259 static const std::uint32_t softTypeIdLimit = 3011; // small prime. TODO: get from options
1260 static const std::uint32_t firstMappedID = 8; // offset into ID space
1261
1262 for (auto& typeStart : typeConstPos) {
1263 const spv::Id resId = asTypeConstId(typeStart);
1264 const std::uint32_t hashval = hashType(typeStart);
1265
1266 if (isOldIdUnmapped(resId))
1267 localId(resId, nextUnusedId(hashval % softTypeIdLimit + firstMappedID));
1268 }
1269 }
1270
John Kessenich140f3df2015-06-26 16:58:36 -06001271 // Strip a single binary by removing ranges given in stripRange
1272 void spirvbin_t::strip()
1273 {
1274 if (stripRange.empty()) // nothing to do
1275 return;
1276
1277 // Sort strip ranges in order of traversal
1278 std::sort(stripRange.begin(), stripRange.end());
1279
1280 // Allocate a new binary big enough to hold old binary
1281 // We'll step this iterator through the strip ranges as we go through the binary
1282 auto strip_it = stripRange.begin();
1283
1284 int strippedPos = 0;
1285 for (unsigned word = 0; word < unsigned(spv.size()); ++word) {
1286 if (strip_it != stripRange.end() && word >= strip_it->second)
1287 ++strip_it;
1288
1289 if (strip_it == stripRange.end() || word < strip_it->first || word >= strip_it->second)
1290 spv[strippedPos++] = spv[word];
1291 }
1292
1293 spv.resize(strippedPos);
1294 stripRange.clear();
1295
1296 buildLocalMaps();
1297 }
1298
1299 // Strip a single binary by removing ranges given in stripRange
1300 void spirvbin_t::remap(std::uint32_t opts)
1301 {
1302 options = opts;
1303
1304 // Set up opcode tables from SpvDoc
1305 spv::Parameterize();
1306
steve-lunarg297754c2016-12-09 11:13:23 -07001307 validate(); // validate header
1308 buildLocalMaps(); // build ID maps
John Kessenich140f3df2015-06-26 16:58:36 -06001309
1310 msg(3, 4, std::string("ID bound: ") + std::to_string(bound()));
1311
steve-lunarg297754c2016-12-09 11:13:23 -07001312 if (options & STRIP) stripDebug();
John Kessenich140f3df2015-06-26 16:58:36 -06001313 strip(); // strip out data we decided to eliminate
John Kessenich140f3df2015-06-26 16:58:36 -06001314 if (options & OPT_LOADSTORE) optLoadStore();
1315 if (options & OPT_FWD_LS) forwardLoadStores();
1316 if (options & DCE_FUNCS) dceFuncs();
1317 if (options & DCE_VARS) dceVars();
1318 if (options & DCE_TYPES) dceTypes();
steve-lunarg297754c2016-12-09 11:13:23 -07001319
1320 strip(); // strip out data we decided to eliminate
1321 stripDeadRefs(); // remove references to things we DCEed
1322 // after the last strip, we must clean any debug info referring to now-deleted data
steve-lunarg811d9f42016-08-17 08:33:49 -06001323
John Kessenich140f3df2015-06-26 16:58:36 -06001324 if (options & MAP_TYPES) mapTypeConst();
1325 if (options & MAP_NAMES) mapNames();
1326 if (options & MAP_FUNCS) mapFnBodies();
1327
steve-lunarg297754c2016-12-09 11:13:23 -07001328 if (options & MAP_ALL) {
1329 mapRemainder(); // map any unmapped IDs
1330 applyMap(); // Now remap each shader to the new IDs we've come up with
1331 }
John Kessenich140f3df2015-06-26 16:58:36 -06001332 }
1333
1334 // remap from a memory image
1335 void spirvbin_t::remap(std::vector<std::uint32_t>& in_spv, std::uint32_t opts)
1336 {
1337 spv.swap(in_spv);
1338 remap(opts);
1339 spv.swap(in_spv);
1340 }
1341
1342} // namespace SPV
1343
1344#endif // defined (use_cpp11)
1345