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 <unordered_set>
16 #include <vector>
17
18 #include "source/instruction.h"
19 #include "source/opcode.h"
20 #include "source/operand.h"
21 #include "source/val/function.h"
22 #include "source/val/validate.h"
23 #include "source/val/validation_state.h"
24 #include "spirv-tools/libspirv.h"
25
26 namespace spvtools {
27 namespace val {
28
UpdateIdUse(ValidationState_t & _,const Instruction * inst)29 spv_result_t UpdateIdUse(ValidationState_t& _, const Instruction* inst) {
30 for (auto& operand : inst->operands()) {
31 const spv_operand_type_t& type = operand.type;
32 const uint32_t operand_id = inst->word(operand.offset);
33 if (spvIsIdType(type) && type != SPV_OPERAND_TYPE_RESULT_ID) {
34 if (auto def = _.FindDef(operand_id))
35 def->RegisterUse(inst, operand.offset);
36 }
37 }
38
39 return SPV_SUCCESS;
40 }
41
42 /// This function checks all ID definitions dominate their use in the CFG.
43 ///
44 /// This function will iterate over all ID definitions that are defined in the
45 /// functions of a module and make sure that the definitions appear in a
46 /// block that dominates their use.
47 ///
48 /// NOTE: This function does NOT check module scoped functions which are
49 /// checked during the initial binary parse in the IdPass below
CheckIdDefinitionDominateUse(ValidationState_t & _)50 spv_result_t CheckIdDefinitionDominateUse(ValidationState_t& _) {
51 std::vector<const Instruction*> phi_instructions;
52 std::unordered_set<uint32_t> phi_ids;
53 for (const auto& inst : _.ordered_instructions()) {
54 if (inst.id() == 0) continue;
55 if (const Function* func = inst.function()) {
56 if (const BasicBlock* block = inst.block()) {
57 // If the Id is defined within a block then make sure all references to
58 // that Id appear in a blocks that are dominated by the defining block
59 for (auto& use_index_pair : inst.uses()) {
60 const Instruction* use = use_index_pair.first;
61 if (const BasicBlock* use_block = use->block()) {
62 if (use_block->reachable() == false) continue;
63 if (use->opcode() == spv::Op::OpPhi) {
64 if (phi_ids.insert(use->id()).second) {
65 phi_instructions.push_back(use);
66 }
67 } else if (!block->dominates(*use->block())) {
68 return _.diag(SPV_ERROR_INVALID_ID, use_block->label())
69 << "ID " << _.getIdName(inst.id()) << " defined in block "
70 << _.getIdName(block->id())
71 << " does not dominate its use in block "
72 << _.getIdName(use_block->id());
73 }
74 }
75 }
76 } else {
77 // If the Ids defined within a function but not in a block(i.e. function
78 // parameters, block ids), then make sure all references to that Id
79 // appear within the same function
80 for (auto use : inst.uses()) {
81 const Instruction* user = use.first;
82 if (user->function() && user->function() != func) {
83 return _.diag(SPV_ERROR_INVALID_ID, _.FindDef(func->id()))
84 << "ID " << _.getIdName(inst.id()) << " used in function "
85 << _.getIdName(user->function()->id())
86 << " is used outside of it's defining function "
87 << _.getIdName(func->id());
88 }
89 }
90 }
91 }
92 // NOTE: Ids defined outside of functions must appear before they are used
93 // This check is being performed in the IdPass function
94 }
95
96 // Check all OpPhi parent blocks are dominated by the variable's defining
97 // blocks
98 for (const Instruction* phi : phi_instructions) {
99 if (phi->block()->reachable() == false) continue;
100 for (size_t i = 3; i < phi->operands().size(); i += 2) {
101 const Instruction* variable = _.FindDef(phi->word(i));
102 const BasicBlock* parent =
103 phi->function()->GetBlock(phi->word(i + 1)).first;
104 if (variable->block() && parent->reachable() &&
105 !variable->block()->dominates(*parent)) {
106 return _.diag(SPV_ERROR_INVALID_ID, phi)
107 << "In OpPhi instruction " << _.getIdName(phi->id()) << ", ID "
108 << _.getIdName(variable->id())
109 << " definition does not dominate its parent "
110 << _.getIdName(parent->id());
111 }
112 }
113 }
114
115 return SPV_SUCCESS;
116 }
117
118 // Performs SSA validation on the IDs of an instruction. The
119 // can_have_forward_declared_ids functor should return true if the
120 // instruction operand's ID can be forward referenced.
IdPass(ValidationState_t & _,Instruction * inst)121 spv_result_t IdPass(ValidationState_t& _, Instruction* inst) {
122 auto can_have_forward_declared_ids =
123 spvIsExtendedInstruction(inst->opcode()) &&
124 spvExtInstIsDebugInfo(inst->ext_inst_type())
125 ? spvDbgInfoExtOperandCanBeForwardDeclaredFunction(
126 inst->opcode(), inst->ext_inst_type(), inst->word(4))
127 : spvOperandCanBeForwardDeclaredFunction(inst->opcode());
128
129 // Keep track of a result id defined by this instruction. 0 means it
130 // does not define an id.
131 uint32_t result_id = 0;
132 bool has_forward_declared_ids = false;
133
134 for (unsigned i = 0; i < inst->operands().size(); i++) {
135 const spv_parsed_operand_t& operand = inst->operand(i);
136 const spv_operand_type_t& type = operand.type;
137 // We only care about Id operands, which are a single word.
138 const uint32_t operand_word = inst->word(operand.offset);
139
140 auto ret = SPV_ERROR_INTERNAL;
141 switch (type) {
142 case SPV_OPERAND_TYPE_RESULT_ID:
143 // NOTE: Multiple Id definitions are being checked by the binary parser.
144 //
145 // Defer undefined-forward-reference removal until after we've analyzed
146 // the remaining operands to this instruction. Deferral only matters
147 // for OpPhi since it's the only case where it defines its own forward
148 // reference. Other instructions that can have forward references
149 // either don't define a value or the forward reference is to a function
150 // Id (and hence defined outside of a function body).
151 result_id = operand_word;
152 // NOTE: The result Id is added (in RegisterInstruction) *after* all of
153 // the other Ids have been checked to avoid premature use in the same
154 // instruction.
155 ret = SPV_SUCCESS;
156 break;
157 case SPV_OPERAND_TYPE_ID:
158 case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
159 case SPV_OPERAND_TYPE_SCOPE_ID:
160 if (const auto def = _.FindDef(operand_word)) {
161 const auto opcode = inst->opcode();
162 if (spvOpcodeGeneratesType(def->opcode()) &&
163 !spvOpcodeGeneratesType(opcode) && !spvOpcodeIsDebug(opcode) &&
164 !inst->IsDebugInfo() && !inst->IsNonSemantic() &&
165 !spvOpcodeIsDecoration(opcode) && opcode != spv::Op::OpFunction &&
166 opcode != spv::Op::OpSizeOf &&
167 opcode != spv::Op::OpCooperativeMatrixLengthNV &&
168 opcode != spv::Op::OpCooperativeMatrixLengthKHR &&
169 !spvOpcodeGeneratesUntypedPointer(opcode) &&
170 opcode != spv::Op::OpUntypedArrayLengthKHR &&
171 !(opcode == spv::Op::OpSpecConstantOp &&
172 (spv::Op(inst->word(3)) ==
173 spv::Op::OpCooperativeMatrixLengthNV ||
174 spv::Op(inst->word(3)) ==
175 spv::Op::OpCooperativeMatrixLengthKHR))) {
176 return _.diag(SPV_ERROR_INVALID_ID, inst)
177 << "Operand " << _.getIdName(operand_word)
178 << " cannot be a type";
179 } else if (def->type_id() == 0 && !spvOpcodeGeneratesType(opcode) &&
180 !spvOpcodeIsDebug(opcode) && !inst->IsDebugInfo() &&
181 !inst->IsNonSemantic() && !spvOpcodeIsDecoration(opcode) &&
182 !spvOpcodeIsBranch(opcode) && opcode != spv::Op::OpPhi &&
183 opcode != spv::Op::OpExtInst &&
184 opcode != spv::Op::OpExtInstWithForwardRefsKHR &&
185 opcode != spv::Op::OpExtInstImport &&
186 opcode != spv::Op::OpSelectionMerge &&
187 opcode != spv::Op::OpLoopMerge &&
188 opcode != spv::Op::OpFunction &&
189 opcode != spv::Op::OpSizeOf &&
190 opcode != spv::Op::OpCooperativeMatrixLengthNV &&
191 opcode != spv::Op::OpCooperativeMatrixLengthKHR &&
192 !spvOpcodeGeneratesUntypedPointer(opcode) &&
193 opcode != spv::Op::OpUntypedArrayLengthKHR &&
194 !(opcode == spv::Op::OpSpecConstantOp &&
195 (spv::Op(inst->word(3)) ==
196 spv::Op::OpCooperativeMatrixLengthNV ||
197 spv::Op(inst->word(3)) ==
198 spv::Op::OpCooperativeMatrixLengthKHR))) {
199 return _.diag(SPV_ERROR_INVALID_ID, inst)
200 << "Operand " << _.getIdName(operand_word)
201 << " requires a type";
202 } else if (def->IsNonSemantic() && !inst->IsNonSemantic()) {
203 return _.diag(SPV_ERROR_INVALID_ID, inst)
204 << "Operand " << _.getIdName(operand_word)
205 << " in semantic instruction cannot be a non-semantic "
206 "instruction";
207 } else {
208 ret = SPV_SUCCESS;
209 }
210 } else if (can_have_forward_declared_ids(i)) {
211 has_forward_declared_ids = true;
212 if (spvOpcodeGeneratesType(inst->opcode()) &&
213 !_.IsForwardPointer(operand_word)) {
214 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
215 << "Operand " << _.getIdName(operand_word)
216 << " requires a previous definition";
217 } else {
218 ret = _.ForwardDeclareId(operand_word);
219 }
220 } else {
221 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
222 << "ID " << _.getIdName(operand_word)
223 << " has not been defined";
224 }
225 break;
226 case SPV_OPERAND_TYPE_TYPE_ID:
227 if (_.IsDefinedId(operand_word)) {
228 auto* def = _.FindDef(operand_word);
229 if (!spvOpcodeGeneratesType(def->opcode())) {
230 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
231 << "ID " << _.getIdName(operand_word) << " is not a type id";
232 } else {
233 ret = SPV_SUCCESS;
234 }
235 } else {
236 ret = _.diag(SPV_ERROR_INVALID_ID, inst)
237 << "ID " << _.getIdName(operand_word)
238 << " has not been defined";
239 }
240 break;
241 case SPV_OPERAND_TYPE_EXTENSION_INSTRUCTION_NUMBER:
242 // Ideally, this check would live in validate_extensions.cpp. But since
243 // forward references are only allowed on non-semantic instructions, and
244 // ID validation is done first, we would fail with a "ID had not been
245 // defined" error before we could give a more helpful message. For this
246 // reason, this test is done here, so we can be more helpful to the
247 // user.
248 if (inst->opcode() == spv::Op::OpExtInstWithForwardRefsKHR &&
249 !inst->IsNonSemantic())
250 return _.diag(SPV_ERROR_INVALID_DATA, inst)
251 << "OpExtInstWithForwardRefsKHR is only allowed with "
252 "non-semantic instructions.";
253 ret = SPV_SUCCESS;
254 break;
255 default:
256 ret = SPV_SUCCESS;
257 break;
258 }
259 if (SPV_SUCCESS != ret) return ret;
260 }
261 const bool must_have_forward_declared_ids =
262 inst->opcode() == spv::Op::OpExtInstWithForwardRefsKHR;
263 if (must_have_forward_declared_ids && !has_forward_declared_ids) {
264 return _.diag(SPV_ERROR_INVALID_ID, inst)
265 << "Opcode OpExtInstWithForwardRefsKHR must have at least one "
266 "forward "
267 "declared ID.";
268 }
269
270 if (result_id) _.RemoveIfForwardDeclared(result_id);
271
272 return SPV_SUCCESS;
273 }
274
275 } // namespace val
276 } // namespace spvtools
277