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(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); 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(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 157 // 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 170 // Return true if this opcode is flow control 171 bool spirvbin_t::isFlowCtrl(spv::Op opCode) const 172 { 173 switch (opCode) { 174 case spv::OpBranchConditional: 175 case spv::OpBranch: 176 case spv::OpSwitch: 177 case spv::OpLoopMerge: 178 case spv::OpSelectionMerge: 179 case spv::OpLabel: 180 case spv::OpFunction: 181 case spv::OpFunctionEnd: return true; 182 default: return false; 183 } 184 } 185 186 // Return true if this opcode defines a type 187 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: 196 case spv::OpTypeImage: 197 case spv::OpTypeSampler: 198 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: 208 case spv::OpTypeSampledImage: 209 case spv::OpTypePipe: return true; 210 default: return false; 211 } 212 } 213 214 // Return true if this opcode defines a constant 215 bool spirvbin_t::isConstOp(spv::Op opCode) const 216 { 217 switch (opCode) { 218 case spv::OpConstantNull: error("unimplemented constant type"); 219 case spv::OpConstantSampler: error("unimplemented constant type"); 220 221 case spv::OpConstantTrue: 222 case spv::OpConstantFalse: 223 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 289 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 302 // 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 328 // Mark debug instructions for stripping 329 void spirvbin_t::stripDebug() 330 { 331 // Strip instructions in the stripOp set: debug info. 332 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 342 // 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; 356 default: 357 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 368 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(); 376 fnCalls.clear(); 377 typeConstPos.clear(); 378 idPosR.clear(); 379 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) { 390 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; 400 401 if (typeId != spv::NoResult) { 402 const unsigned idTypeSize = typeSizeInWords(typeId); 403 404 if (idTypeSize != 0) 405 idTypeSizeMap[resultId] = idTypeSize; 406 } 407 } 408 409 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); 432 } else if (isTypeOp(opCode)) { 433 assert(asId(start + 1) != spv::NoResult); 434 typeConstPos.insert(start); 435 } 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 463 int spirvbin_t::processInstruction(unsigned word, instfn_t instFn, idfn_t idFn) 464 { 465 const auto instructionStart = word; 466 const unsigned wordCount = asWordCount(instructionStart); 467 const int nextInst = word++ + wordCount; 468 spv::Op opCode = asOpCode(instructionStart); 469 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 502 // 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 507 // Store IDs from instruction in our map 508 for (int op = 0; numOperands > 0; ++op, --numOperands) { 509 // 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 521 switch (spv::InstructionDesc[opCode].operands.getClass(op)) { 522 case spv::OperandId: 523 case spv::OperandScope: 524 case spv::OperandMemorySemantics: 525 idBuffer[idBufferPos] = asId(word); 526 idBufferPos = (idBufferPos + 1) % idBufferSize; 527 idFn(asId(word++)); 528 break; 529 530 case spv::OperandVariableIds: 531 for (unsigned i = 0; i < numOperands; ++i) 532 idFn(asId(word++)); 533 return nextInst; 534 535 case spv::OperandVariableLiterals: 536 // for clarity 537 // if (opCode == spv::OpDecorate && asDecoration(word - 1) == spv::DecorationBuiltIn) { 538 // ++word; 539 // --numOperands; 540 // } 541 // word += numOperands; 542 return nextInst; 543 544 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 559 } 560 561 return nextInst; 562 } 563 564 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: 573 return nextInst; 574 575 // Single word operands we simply ignore, as they hold no IDs 576 case spv::OperandLiteralNumber: 577 case spv::OperandSource: 578 case spv::OperandExecutionModel: 579 case spv::OperandAddressing: 580 case spv::OperandMemory: 581 case spv::OperandStorage: 582 case spv::OperandDimensionality: 583 case spv::OperandSamplerAddressingMode: 584 case spv::OperandSamplerFilterMode: 585 case spv::OperandSamplerImageFormat: 586 case spv::OperandImageChannelOrder: 587 case spv::OperandImageChannelDataType: 588 case spv::OperandImageOperands: 589 case spv::OperandFPFastMath: 590 case spv::OperandFPRoundingMode: 591 case spv::OperandLinkageType: 592 case spv::OperandAccessQualifier: 593 case spv::OperandFuncParamAttr: 594 case spv::OperandDecoration: 595 case spv::OperandBuiltIn: 596 case spv::OperandSelect: 597 case spv::OperandLoop: 598 case spv::OperandFunction: 599 case spv::OperandMemoryAccess: 600 case spv::OperandGroupOperation: 601 case spv::OperandKernelEnqueueFlags: 602 case spv::OperandKernelProfilingInfo: 603 case spv::OperandCapability: 604 ++word; 605 break; 606 607 default: 608 assert(0 && "Unhandled Operand Class"); 609 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 670 // Empirical best size from a single data set. TODO: Would be a good tunable. 671 // We essentially perform a little convolution around each instruction, 672 // 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 725 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: 733 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 778 if ((opCode == spv::OpVariable && asWordCount(start) == 4) && 779 (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 805 if ((opCode == spv::OpVariable && asWordCount(start) == 4) && 806 (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 826 // optimize loads and stores 827 void spirvbin_t::optLoadStore() 828 { 829 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 833 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 839 // Count blocks, so we can avoid crossing flow control 840 if (isFlowCtrl(opCode)) 841 ++blockNum; 842 843 // Add local variables to the map 844 if ((opCode == spv::OpVariable && spv[start+3] == spv::StorageClassFunction && asWordCount(start) == 4)) { 845 fnLocalVars.insert(asId(start+2)); 846 return true; 847 } 848 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)); 853 return true; 854 } 855 856 if (opCode == spv::OpLoad && fnLocalVars.count(asId(start+3)) > 0) { 857 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); 863 } 864 865 // don't do for volatile references 866 if (wordCount > 4 && (spv[start+4] & spv::MemoryAccessVolatileMask)) { 867 fnLocalVars.erase(varId); 868 idMap.erase(varId); 869 } 870 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 879 return true; 880 } 881 882 if (opCode == spv::OpStore && fnLocalVars.count(asId(start+1)) > 0) { 883 const spv::Id varId = asId(start+1); 884 885 if (idMap.find(varId) == idMap.end()) { 886 idMap[varId] = asId(start+2); 887 } else { 888 // Remove if it has more than one store to the same pointer 889 fnLocalVars.erase(varId); 890 idMap.erase(varId); 891 } 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 } 898 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 907 return true; 908 } 909 910 return false; 911 }, 912 913 // If local var id used anywhere else, don't eliminate 914 [&](spv::Id& id) { 915 if (fnLocalVars.count(id) > 0) { 916 fnLocalVars.erase(id); 917 idMap.erase(id); 918 } 919 } 920 ); 921 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 930 // 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 944 // 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)) { 950 951 stripInst(start); 952 return true; 953 } 954 955 return false; 956 }, 957 958 [&](spv::Id& id) { 959 if (idMap.find(id) != idMap.end()) id = idMap[id]; 960 } 961 ); 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); 988 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) { 1022 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; 1033 }, 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) { 1041 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 1050 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 1066 // 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(); 1073 1074 // Count total type usage 1075 process(inst_fn_nop, 1076 [&](spv::Id& id) { if (isType[id]) ++typeUseCount[id]; } 1077 ); 1078 1079 // 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 } 1087 } 1088 } 1089 } 1090 1091 #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 1150 // 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 1162 // Return start position in SPV of given Id. error if not found. 1163 unsigned spirvbin_t::idPos(spv::Id id) const 1164 { 1165 const auto tid_it = idPosR.find(id); 1166 if (tid_it == idPosR.end()) 1167 error("ID not found"); 1168 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: 1185 return 6 + hashType(idPos(spv[typeStart+2])) * (spv[typeStart+3] - 1); 1186 case spv::OpTypeMatrix: 1187 return 30 + hashType(idPos(spv[typeStart+2])) * (spv[typeStart+3] - 1); 1188 case spv::OpTypeImage: 1189 return 120 + hashType(idPos(spv[typeStart+2])) + 1190 spv[typeStart+3] + // dimensionality 1191 spv[typeStart+4] * 8 * 16 + // depth 1192 spv[typeStart+5] * 4 * 16 + // arrayed 1193 spv[typeStart+6] * 2 * 16 + // multisampled 1194 spv[typeStart+7] * 1 * 16; // format 1195 case spv::OpTypeSampler: 1196 return 500; 1197 case spv::OpTypeSampledImage: 1198 return 502; 1199 case spv::OpTypeArray: 1200 return 501 + hashType(idPos(spv[typeStart+2])) * spv[typeStart+3]; 1201 case spv::OpTypeRuntimeArray: 1202 return 5000 + hashType(idPos(spv[typeStart+2])); 1203 case spv::OpTypeStruct: 1204 { 1205 std::uint32_t hash = 10000; 1206 for (unsigned w=2; w < wordCount; ++w) 1207 hash += w * hashType(idPos(spv[typeStart+w])); 1208 return hash; 1209 } 1210 1211 case spv::OpTypeOpaque: return 6000 + spv[typeStart+2]; 1212 case spv::OpTypePointer: return 100000 + hashType(idPos(spv[typeStart+3])); 1213 case spv::OpTypeFunction: 1214 { 1215 std::uint32_t hash = 200000; 1216 for (unsigned w=2; w < wordCount; ++w) 1217 hash += w * hashType(idPos(spv[typeStart+w])); 1218 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 1227 case spv::OpConstantNull: return 300005; 1228 case spv::OpConstantSampler: return 300006; 1229 1230 case spv::OpConstantTrue: return 300007; 1231 case spv::OpConstantFalse: return 300008; 1232 case spv::OpConstantComposite: 1233 { 1234 std::uint32_t hash = 300011 + hashType(idPos(spv[typeStart+1])); 1235 for (unsigned w=3; w < wordCount; ++w) 1236 hash += w * hashType(idPos(spv[typeStart+w])); 1237 return hash; 1238 } 1239 case spv::OpConstant: 1240 { 1241 std::uint32_t hash = 400011 + hashType(idPos(spv[typeStart+1])); 1242 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 1271 // 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 1307 validate(); // validate header 1308 buildLocalMaps(); // build ID maps 1309 1310 msg(3, 4, std::string("ID bound: ") + std::to_string(bound())); 1311 1312 if (options & STRIP) stripDebug(); 1313 strip(); // strip out data we decided to eliminate 1314 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(); 1319 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 1323 1324 if (options & MAP_TYPES) mapTypeConst(); 1325 if (options & MAP_NAMES) mapNames(); 1326 if (options & MAP_FUNCS) mapFnBodies(); 1327 1328 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 } 1332 } 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 1346
