// 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) {
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) {
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