123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229 |
- // Copyright (c) 2015-2016 The Khronos Group Inc.
- //
- // Licensed under the Apache License, Version 2.0 (the "License");
- // you may not use this file except in compliance with the License.
- // You may obtain a copy of the License at
- //
- // http://www.apache.org/licenses/LICENSE-2.0
- //
- // Unless required by applicable law or agreed to in writing, software
- // distributed under the License is distributed on an "AS IS" BASIS,
- // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- // See the License for the specific language governing permissions and
- // limitations under the License.
- #include "source/val/validate.h"
- #include <cassert>
- #include <algorithm>
- #include <iostream>
- #include <iterator>
- #include <stack>
- #include <string>
- #include <unordered_set>
- #include <utility>
- #include <vector>
- #include "source/diagnostic.h"
- #include "source/instruction.h"
- #include "source/opcode.h"
- #include "source/operand.h"
- #include "source/spirv_validator_options.h"
- #include "source/val/function.h"
- #include "source/val/validation_state.h"
- #include "spirv-tools/libspirv.h"
- namespace spvtools {
- namespace val {
- spv_result_t UpdateIdUse(ValidationState_t& _, const Instruction* inst) {
- for (auto& operand : inst->operands()) {
- const spv_operand_type_t& type = operand.type;
- const uint32_t operand_id = inst->word(operand.offset);
- if (spvIsIdType(type) && type != SPV_OPERAND_TYPE_RESULT_ID) {
- if (auto def = _.FindDef(operand_id))
- def->RegisterUse(inst, operand.offset);
- }
- }
- return SPV_SUCCESS;
- }
- /// This function checks all ID definitions dominate their use in the CFG.
- ///
- /// This function will iterate over all ID definitions that are defined in the
- /// functions of a module and make sure that the definitions appear in a
- /// block that dominates their use.
- ///
- /// NOTE: This function does NOT check module scoped functions which are
- /// checked during the initial binary parse in the IdPass below
- spv_result_t CheckIdDefinitionDominateUse(ValidationState_t& _) {
- std::vector<const Instruction*> phi_instructions;
- std::unordered_set<uint32_t> phi_ids;
- for (const auto& inst : _.ordered_instructions()) {
- if (inst.id() == 0) continue;
- if (const Function* func = inst.function()) {
- if (const BasicBlock* block = inst.block()) {
- // If the Id is defined within a block then make sure all references to
- // that Id appear in a blocks that are dominated by the defining block
- for (auto& use_index_pair : inst.uses()) {
- const Instruction* use = use_index_pair.first;
- if (const BasicBlock* use_block = use->block()) {
- if (use_block->reachable() == false) continue;
- if (use->opcode() == SpvOpPhi) {
- if (phi_ids.insert(use->id()).second) {
- phi_instructions.push_back(use);
- }
- } else if (!block->dominates(*use->block())) {
- return _.diag(SPV_ERROR_INVALID_ID, use_block->label())
- << "ID " << _.getIdName(inst.id()) << " defined in block "
- << _.getIdName(block->id())
- << " does not dominate its use in block "
- << _.getIdName(use_block->id());
- }
- }
- }
- } else {
- // If the Ids defined within a function but not in a block(i.e. function
- // parameters, block ids), then make sure all references to that Id
- // appear within the same function
- for (auto use : inst.uses()) {
- const Instruction* user = use.first;
- if (user->function() && user->function() != func) {
- return _.diag(SPV_ERROR_INVALID_ID, _.FindDef(func->id()))
- << "ID " << _.getIdName(inst.id()) << " used in function "
- << _.getIdName(user->function()->id())
- << " is used outside of it's defining function "
- << _.getIdName(func->id());
- }
- }
- }
- }
- // NOTE: Ids defined outside of functions must appear before they are used
- // This check is being performed in the IdPass function
- }
- // Check all OpPhi parent blocks are dominated by the variable's defining
- // blocks
- for (const Instruction* phi : phi_instructions) {
- if (phi->block()->reachable() == false) continue;
- for (size_t i = 3; i < phi->operands().size(); i += 2) {
- const Instruction* variable = _.FindDef(phi->word(i));
- const BasicBlock* parent =
- phi->function()->GetBlock(phi->word(i + 1)).first;
- if (variable->block() && parent->reachable() &&
- !variable->block()->dominates(*parent)) {
- return _.diag(SPV_ERROR_INVALID_ID, phi)
- << "In OpPhi instruction " << _.getIdName(phi->id()) << ", ID "
- << _.getIdName(variable->id())
- << " definition does not dominate its parent "
- << _.getIdName(parent->id());
- }
- }
- }
- return SPV_SUCCESS;
- }
- // Performs SSA validation on the IDs of an instruction. The
- // can_have_forward_declared_ids functor should return true if the
- // instruction operand's ID can be forward referenced.
- spv_result_t IdPass(ValidationState_t& _, Instruction* inst) {
- auto can_have_forward_declared_ids =
- spvOperandCanBeForwardDeclaredFunction(inst->opcode());
- // Keep track of a result id defined by this instruction. 0 means it
- // does not define an id.
- uint32_t result_id = 0;
- for (unsigned i = 0; i < inst->operands().size(); i++) {
- const spv_parsed_operand_t& operand = inst->operand(i);
- const spv_operand_type_t& type = operand.type;
- // We only care about Id operands, which are a single word.
- const uint32_t operand_word = inst->word(operand.offset);
- auto ret = SPV_ERROR_INTERNAL;
- switch (type) {
- case SPV_OPERAND_TYPE_RESULT_ID:
- // NOTE: Multiple Id definitions are being checked by the binary parser.
- //
- // Defer undefined-forward-reference removal until after we've analyzed
- // the remaining operands to this instruction. Deferral only matters
- // for OpPhi since it's the only case where it defines its own forward
- // reference. Other instructions that can have forward references
- // either don't define a value or the forward reference is to a function
- // Id (and hence defined outside of a function body).
- result_id = operand_word;
- // NOTE: The result Id is added (in RegisterInstruction) *after* all of
- // the other Ids have been checked to avoid premature use in the same
- // instruction.
- ret = SPV_SUCCESS;
- break;
- case SPV_OPERAND_TYPE_ID:
- case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
- case SPV_OPERAND_TYPE_SCOPE_ID:
- if (const auto def = _.FindDef(operand_word)) {
- const auto opcode = inst->opcode();
- if (spvOpcodeGeneratesType(def->opcode()) &&
- !spvOpcodeGeneratesType(opcode) && !spvOpcodeIsDebug(opcode) &&
- !spvOpcodeIsDecoration(opcode) && opcode != SpvOpFunction &&
- opcode != SpvOpCooperativeMatrixLengthNV &&
- !(opcode == SpvOpSpecConstantOp &&
- inst->word(3) == SpvOpCooperativeMatrixLengthNV)) {
- return _.diag(SPV_ERROR_INVALID_ID, inst)
- << "Operand " << _.getIdName(operand_word)
- << " cannot be a type";
- } else if (def->type_id() == 0 && !spvOpcodeGeneratesType(opcode) &&
- !spvOpcodeIsDebug(opcode) &&
- !spvOpcodeIsDecoration(opcode) &&
- !spvOpcodeIsBranch(opcode) && opcode != SpvOpPhi &&
- opcode != SpvOpExtInst && opcode != SpvOpExtInstImport &&
- opcode != SpvOpSelectionMerge &&
- opcode != SpvOpLoopMerge && opcode != SpvOpFunction &&
- opcode != SpvOpCooperativeMatrixLengthNV &&
- !(opcode == SpvOpSpecConstantOp &&
- inst->word(3) == SpvOpCooperativeMatrixLengthNV)) {
- return _.diag(SPV_ERROR_INVALID_ID, inst)
- << "Operand " << _.getIdName(operand_word)
- << " requires a type";
- } else {
- ret = SPV_SUCCESS;
- }
- } else if (can_have_forward_declared_ids(i)) {
- ret = _.ForwardDeclareId(operand_word);
- } else {
- ret = _.diag(SPV_ERROR_INVALID_ID, inst)
- << "ID " << _.getIdName(operand_word)
- << " has not been defined";
- }
- break;
- case SPV_OPERAND_TYPE_TYPE_ID:
- if (_.IsDefinedId(operand_word)) {
- auto* def = _.FindDef(operand_word);
- if (!spvOpcodeGeneratesType(def->opcode())) {
- ret = _.diag(SPV_ERROR_INVALID_ID, inst)
- << "ID " << _.getIdName(operand_word) << " is not a type id";
- } else {
- ret = SPV_SUCCESS;
- }
- } else {
- ret = _.diag(SPV_ERROR_INVALID_ID, inst)
- << "ID " << _.getIdName(operand_word)
- << " has not been defined";
- }
- break;
- default:
- ret = SPV_SUCCESS;
- break;
- }
- if (SPV_SUCCESS != ret) return ret;
- }
- if (result_id) _.RemoveIfForwardDeclared(result_id);
- return SPV_SUCCESS;
- }
- } // namespace val
- } // namespace spvtools
|