1// Copyright (c) 2015-2016 The Khronos Group Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "source/val/validate.h"
16
17#include <cassert>
18
19#include <algorithm>
20#include <iostream>
21#include <iterator>
22#include <stack>
23#include <string>
24#include <unordered_set>
25#include <utility>
26#include <vector>
27
28#include "source/diagnostic.h"
29#include "source/instruction.h"
30#include "source/opcode.h"
31#include "source/operand.h"
32#include "source/spirv_validator_options.h"
33#include "source/val/function.h"
34#include "source/val/validation_state.h"
35#include "spirv-tools/libspirv.h"
36
37namespace spvtools {
38namespace val {
39
40spv_result_t UpdateIdUse(ValidationState_t& _, const Instruction* inst) {
41 for (auto& operand : inst->operands()) {
42 const spv_operand_type_t& type = operand.type;
43 const uint32_t operand_id = inst->word(operand.offset);
44 if (spvIsIdType(type) && type != SPV_OPERAND_TYPE_RESULT_ID) {
45 if (auto def = _.FindDef(operand_id))
46 def->RegisterUse(inst, operand.offset);
47 }
48 }
49
50 return SPV_SUCCESS;
51}
52
53/// This function checks all ID definitions dominate their use in the CFG.
54///
55/// This function will iterate over all ID definitions that are defined in the
56/// functions of a module and make sure that the definitions appear in a
57/// block that dominates their use.
58///
59/// NOTE: This function does NOT check module scoped functions which are
60/// checked during the initial binary parse in the IdPass below
61spv_result_t CheckIdDefinitionDominateUse(ValidationState_t& _) {
62 std::vector<const Instruction*> phi_instructions;
63 std::unordered_set<uint32_t> phi_ids;
64 for (const auto& inst : _.ordered_instructions()) {
65 if (inst.id() == 0) continue;
66 if (const Function* func = inst.function()) {
67 if (const BasicBlock* block = inst.block()) {
68 // If the Id is defined within a block then make sure all references to
69 // that Id appear in a blocks that are dominated by the defining block
70 for (auto& use_index_pair : inst.uses()) {
71 const Instruction* use = use_index_pair.first;
72 if (const BasicBlock* use_block = use->block()) {
73 if (use_block->reachable() == false) continue;
74 if (use->opcode() == SpvOpPhi) {
75 if (phi_ids.insert(use->id()).second) {
76 phi_instructions.push_back(use);
77 }
78 } else if (!block->dominates(*use->block())) {
79 return _.diag(SPV_ERROR_INVALID_ID, use_block->label())
80 << "ID " << _.getIdName(inst.id()) << " defined in block "
81 << _.getIdName(block->id())
82 << " does not dominate its use in block "
83 << _.getIdName(use_block->id());
84 }
85 }
86 }
87 } else {
88 // If the Ids defined within a function but not in a block(i.e. function
89 // parameters, block ids), then make sure all references to that Id
90 // appear within the same function
91 for (auto use : inst.uses()) {
92 const Instruction* user = use.first;
93 if (user->function() && user->function() != func) {
94 return _.diag(SPV_ERROR_INVALID_ID, _.FindDef(func->id()))
95 << "ID " << _.getIdName(inst.id()) << " used in function "
96 << _.getIdName(user->function()->id())
97 << " is used outside of it's defining function "
98 << _.getIdName(func->id());
99 }
100 }
101 }
102 }
103 // NOTE: Ids defined outside of functions must appear before they are used
104 // This check is being performed in the IdPass function
105 }
106
107 // Check all OpPhi parent blocks are dominated by the variable's defining
108 // blocks
109 for (const Instruction* phi : phi_instructions) {
110 if (phi->block()->reachable() == false) continue;
111 for (size_t i = 3; i < phi->operands().size(); i += 2) {
112 const Instruction* variable = _.FindDef(phi->word(i));
113 const BasicBlock* parent =
114 phi->function()->GetBlock(phi->word(i + 1)).first;
115 if (variable->block() && parent->reachable() &&
116 !variable->block()->dominates(*parent)) {
117 return _.diag(SPV_ERROR_INVALID_ID, phi)
118 << "In OpPhi instruction " << _.getIdName(phi->id()) << ", ID "
119 << _.getIdName(variable->id())
120 << " definition does not dominate its parent "
121 << _.getIdName(parent->id());
122 }
123 }
124 }
125
126 return SPV_SUCCESS;
127}
128
129// Performs SSA validation on the IDs of an instruction. The
130// can_have_forward_declared_ids functor should return true if the
131// instruction operand's ID can be forward referenced.
132spv_result_t IdPass(ValidationState_t& _, Instruction* inst) {
133 auto can_have_forward_declared_ids =
134 inst->opcode() == SpvOpExtInst &&
135 spvExtInstIsDebugInfo(inst->ext_inst_type())
136 ? spvDbgInfoExtOperandCanBeForwardDeclaredFunction(
137 inst->ext_inst_type(), inst->word(4))
138 : spvOperandCanBeForwardDeclaredFunction(inst->opcode());
139
140 // Keep track of a result id defined by this instruction. 0 means it
141 // does not define an id.
142 uint32_t result_id = 0;
143
144 for (unsigned i = 0; i < inst->operands().size(); i++) {
145 const spv_parsed_operand_t& operand = inst->operand(i);
146 const spv_operand_type_t& type = operand.type;
147 // We only care about Id operands, which are a single word.
148 const uint32_t operand_word = inst->word(operand.offset);
149
150 auto ret = SPV_ERROR_INTERNAL;
151 switch (type) {
152 case SPV_OPERAND_TYPE_RESULT_ID:
153 // NOTE: Multiple Id definitions are being checked by the binary parser.
154 //
155 // Defer undefined-forward-reference removal until after we've analyzed
156 // the remaining operands to this instruction. Deferral only matters
157 // for OpPhi since it's the only case where it defines its own forward
158 // reference. Other instructions that can have forward references
159 // either don't define a value or the forward reference is to a function
160 // Id (and hence defined outside of a function body).
161 result_id = operand_word;
162 // NOTE: The result Id is added (in RegisterInstruction) *after* all of
163 // the other Ids have been checked to avoid premature use in the same
164 // instruction.
165 ret = SPV_SUCCESS;
166 break;
167 case SPV_OPERAND_TYPE_ID:
168 case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
169 case SPV_OPERAND_TYPE_SCOPE_ID:
170 if (const auto def = _.FindDef(operand_word)) {
171 const auto opcode = inst->opcode();
172 if (spvOpcodeGeneratesType(def->opcode()) &&
173 !spvOpcodeGeneratesType(opcode) && !spvOpcodeIsDebug(opcode) &&
174 !inst->IsDebugInfo() && !inst->IsNonSemantic() &&
175 !spvOpcodeIsDecoration(opcode) && opcode != SpvOpFunction &&
176 opcode != SpvOpCooperativeMatrixLengthNV &&
177 !(opcode == SpvOpSpecConstantOp &&
178 inst->word(3) == SpvOpCooperativeMatrixLengthNV)) {
179 return _.diag(SPV_ERROR_INVALID_ID, inst)
180 << "Operand " << _.getIdName(operand_word)
181 << " cannot be a type";
182 } else if (def->type_id() == 0 && !spvOpcodeGeneratesType(opcode) &&
183 !spvOpcodeIsDebug(opcode) && !inst->IsDebugInfo() &&
184 !inst->IsNonSemantic() && !spvOpcodeIsDecoration(opcode) &&
185 !spvOpcodeIsBranch(opcode) && opcode != SpvOpPhi &&
186 opcode != SpvOpExtInst && opcode != SpvOpExtInstImport &&
187 opcode != SpvOpSelectionMerge &&
188 opcode != SpvOpLoopMerge && opcode != SpvOpFunction &&
189 opcode != SpvOpCooperativeMatrixLengthNV &&
190 !(opcode == SpvOpSpecConstantOp &&
191 inst->word(3) == SpvOpCooperativeMatrixLengthNV)) {
192 return _.diag(SPV_ERROR_INVALID_ID, inst)
193 << "Operand " << _.getIdName(operand_word)
194 << " requires a type";
195 } else if (def->IsNonSemantic() && !inst->IsNonSemantic()) {
196 return _.diag(SPV_ERROR_INVALID_ID, inst)
197 << "Operand " << _.getIdName(operand_word)
198 << " in semantic instruction cannot be a non-semantic "
199 "instruction";
200 } else {
201 ret = SPV_SUCCESS;
202 }
203 } else if (can_have_forward_declared_ids(i)) {
204 if (inst->opcode() == SpvOpTypeStruct &&
205 !_.IsForwardPointer(operand_word)) {
206 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
207 << "Operand " << _.getIdName(operand_word)
208 << " requires a previous definition";
209 } else {
210 ret = _.ForwardDeclareId(operand_word);
211 }
212 } else {
213 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
214 << "ID " << _.getIdName(operand_word)
215 << " has not been defined";
216 }
217 break;
218 case SPV_OPERAND_TYPE_TYPE_ID:
219 if (_.IsDefinedId(operand_word)) {
220 auto* def = _.FindDef(operand_word);
221 if (!spvOpcodeGeneratesType(def->opcode())) {
222 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
223 << "ID " << _.getIdName(operand_word) << " is not a type id";
224 } else {
225 ret = SPV_SUCCESS;
226 }
227 } else {
228 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
229 << "ID " << _.getIdName(operand_word)
230 << " has not been defined";
231 }
232 break;
233 default:
234 ret = SPV_SUCCESS;
235 break;
236 }
237 if (SPV_SUCCESS != ret) return ret;
238 }
239 if (result_id) _.RemoveIfForwardDeclared(result_id);
240
241 return SPV_SUCCESS;
242}
243
244} // namespace val
245} // namespace spvtools
246