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 <algorithm>
18#include <cassert>
19#include <cstdio>
20#include <functional>
21#include <iterator>
22#include <memory>
23#include <sstream>
24#include <string>
25#include <vector>
26
27#include "source/binary.h"
28#include "source/diagnostic.h"
29#include "source/enum_string_mapping.h"
30#include "source/extensions.h"
31#include "source/instruction.h"
32#include "source/opcode.h"
33#include "source/operand.h"
34#include "source/spirv_constant.h"
35#include "source/spirv_endian.h"
36#include "source/spirv_target_env.h"
37#include "source/spirv_validator_options.h"
38#include "source/val/construct.h"
39#include "source/val/function.h"
40#include "source/val/instruction.h"
41#include "source/val/validation_state.h"
42#include "spirv-tools/libspirv.h"
43
44namespace {
45// TODO(issue 1950): The validator only returns a single message anyway, so no
46// point in generating more than 1 warning.
47static uint32_t kDefaultMaxNumOfWarnings = 1;
48} // namespace
49
50namespace spvtools {
51namespace val {
52namespace {
53
54// Parses OpExtension instruction and registers extension.
55void RegisterExtension(ValidationState_t& _,
56 const spv_parsed_instruction_t* inst) {
57 const std::string extension_str = spvtools::GetExtensionString(inst);
58 Extension extension;
59 if (!GetExtensionFromString(extension_str.c_str(), &extension)) {
60 // The error will be logged in the ProcessInstruction pass.
61 return;
62 }
63
64 _.RegisterExtension(extension);
65}
66
67// Parses the beginning of the module searching for OpExtension instructions.
68// Registers extensions if recognized. Returns SPV_REQUESTED_TERMINATION
69// once an instruction which is not SpvOpCapability and SpvOpExtension is
70// encountered. According to the SPIR-V spec extensions are declared after
71// capabilities and before everything else.
72spv_result_t ProcessExtensions(void* user_data,
73 const spv_parsed_instruction_t* inst) {
74 const SpvOp opcode = static_cast<SpvOp>(inst->opcode);
75 if (opcode == SpvOpCapability) return SPV_SUCCESS;
76
77 if (opcode == SpvOpExtension) {
78 ValidationState_t& _ = *(reinterpret_cast<ValidationState_t*>(user_data));
79 RegisterExtension(_, inst);
80 return SPV_SUCCESS;
81 }
82
83 // OpExtension block is finished, requesting termination.
84 return SPV_REQUESTED_TERMINATION;
85}
86
87spv_result_t ProcessInstruction(void* user_data,
88 const spv_parsed_instruction_t* inst) {
89 ValidationState_t& _ = *(reinterpret_cast<ValidationState_t*>(user_data));
90
91 auto* instruction = _.AddOrderedInstruction(inst);
92 _.RegisterDebugInstruction(instruction);
93
94 return SPV_SUCCESS;
95}
96
97spv_result_t ValidateForwardDecls(ValidationState_t& _) {
98 if (_.unresolved_forward_id_count() == 0) return SPV_SUCCESS;
99
100 std::stringstream ss;
101 std::vector<uint32_t> ids = _.UnresolvedForwardIds();
102
103 std::transform(
104 std::begin(ids), std::end(ids),
105 std::ostream_iterator<std::string>(ss, " "),
106 bind(&ValidationState_t::getIdName, std::ref(_), std::placeholders::_1));
107
108 auto id_str = ss.str();
109 return _.diag(SPV_ERROR_INVALID_ID, nullptr)
110 << "The following forward referenced IDs have not been defined:\n"
111 << id_str.substr(0, id_str.size() - 1);
112}
113
114std::vector<std::string> CalculateNamesForEntryPoint(ValidationState_t& _,
115 const uint32_t id) {
116 auto id_descriptions = _.entry_point_descriptions(id);
117 auto id_names = std::vector<std::string>();
118 id_names.reserve((id_descriptions.size()));
119
120 for (auto description : id_descriptions) id_names.push_back(description.name);
121
122 return id_names;
123}
124
125spv_result_t ValidateEntryPointNameUnique(ValidationState_t& _,
126 const uint32_t id) {
127 auto id_names = CalculateNamesForEntryPoint(_, id);
128 const auto names =
129 std::unordered_set<std::string>(id_names.begin(), id_names.end());
130
131 if (id_names.size() != names.size()) {
132 std::sort(id_names.begin(), id_names.end());
133 for (size_t i = 0; i < id_names.size() - 1; i++) {
134 if (id_names[i] == id_names[i + 1]) {
135 return _.diag(SPV_ERROR_INVALID_BINARY, _.FindDef(id))
136 << "Entry point name \"" << id_names[i]
137 << "\" is not unique, which is not allow in WebGPU env.";
138 }
139 }
140 }
141
142 for (const auto other_id : _.entry_points()) {
143 if (other_id == id) continue;
144 const auto other_id_names = CalculateNamesForEntryPoint(_, other_id);
145 for (const auto& other_id_name : other_id_names) {
146 if (names.find(other_id_name) != names.end()) {
147 return _.diag(SPV_ERROR_INVALID_BINARY, _.FindDef(id))
148 << "Entry point name \"" << other_id_name
149 << "\" is not unique, which is not allow in WebGPU env.";
150 }
151 }
152 }
153
154 return SPV_SUCCESS;
155}
156
157spv_result_t ValidateEntryPointNamesUnique(ValidationState_t& _) {
158 for (const auto id : _.entry_points()) {
159 auto result = ValidateEntryPointNameUnique(_, id);
160 if (result != SPV_SUCCESS) return result;
161 }
162 return SPV_SUCCESS;
163}
164
165// Entry point validation. Based on 2.16.1 (Universal Validation Rules) of the
166// SPIRV spec:
167// * There is at least one OpEntryPoint instruction, unless the Linkage
168// capability is being used.
169// * No function can be targeted by both an OpEntryPoint instruction and an
170// OpFunctionCall instruction.
171//
172// Additionally enforces that entry points for Vulkan and WebGPU should not have
173// recursion. And that entry names should be unique for WebGPU.
174spv_result_t ValidateEntryPoints(ValidationState_t& _) {
175 _.ComputeFunctionToEntryPointMapping();
176 _.ComputeRecursiveEntryPoints();
177
178 if (_.entry_points().empty() && !_.HasCapability(SpvCapabilityLinkage)) {
179 return _.diag(SPV_ERROR_INVALID_BINARY, nullptr)
180 << "No OpEntryPoint instruction was found. This is only allowed if "
181 "the Linkage capability is being used.";
182 }
183
184 for (const auto& entry_point : _.entry_points()) {
185 if (_.IsFunctionCallTarget(entry_point)) {
186 return _.diag(SPV_ERROR_INVALID_BINARY, _.FindDef(entry_point))
187 << "A function (" << entry_point
188 << ") may not be targeted by both an OpEntryPoint instruction and "
189 "an OpFunctionCall instruction.";
190 }
191
192 // For Vulkan and WebGPU, the static function-call graph for an entry point
193 // must not contain cycles.
194 if (spvIsVulkanOrWebGPUEnv(_.context()->target_env)) {
195 if (_.recursive_entry_points().find(entry_point) !=
196 _.recursive_entry_points().end()) {
197 return _.diag(SPV_ERROR_INVALID_BINARY, _.FindDef(entry_point))
198 << "Entry points may not have a call graph with cycles.";
199 }
200 }
201
202 // For WebGPU all entry point names must be unique.
203 if (spvIsWebGPUEnv(_.context()->target_env)) {
204 const auto result = ValidateEntryPointNamesUnique(_);
205 if (result != SPV_SUCCESS) return result;
206 }
207 }
208
209 return SPV_SUCCESS;
210}
211
212spv_result_t ValidateBinaryUsingContextAndValidationState(
213 const spv_context_t& context, const uint32_t* words, const size_t num_words,
214 spv_diagnostic* pDiagnostic, ValidationState_t* vstate) {
215 auto binary = std::unique_ptr<spv_const_binary_t>(
216 new spv_const_binary_t{words, num_words});
217
218 spv_endianness_t endian;
219 spv_position_t position = {};
220 if (spvBinaryEndianness(binary.get(), &endian)) {
221 return DiagnosticStream(position, context.consumer, "",
222 SPV_ERROR_INVALID_BINARY)
223 << "Invalid SPIR-V magic number.";
224 }
225
226 if (spvIsWebGPUEnv(context.target_env) && endian != SPV_ENDIANNESS_LITTLE) {
227 return DiagnosticStream(position, context.consumer, "",
228 SPV_ERROR_INVALID_BINARY)
229 << "WebGPU requires SPIR-V to be little endian.";
230 }
231
232 spv_header_t header;
233 if (spvBinaryHeaderGet(binary.get(), endian, &header)) {
234 return DiagnosticStream(position, context.consumer, "",
235 SPV_ERROR_INVALID_BINARY)
236 << "Invalid SPIR-V header.";
237 }
238
239 if (header.version > spvVersionForTargetEnv(context.target_env)) {
240 return DiagnosticStream(position, context.consumer, "",
241 SPV_ERROR_WRONG_VERSION)
242 << "Invalid SPIR-V binary version "
243 << SPV_SPIRV_VERSION_MAJOR_PART(header.version) << "."
244 << SPV_SPIRV_VERSION_MINOR_PART(header.version)
245 << " for target environment "
246 << spvTargetEnvDescription(context.target_env) << ".";
247 }
248
249 if (header.bound > vstate->options()->universal_limits_.max_id_bound) {
250 return DiagnosticStream(position, context.consumer, "",
251 SPV_ERROR_INVALID_BINARY)
252 << "Invalid SPIR-V. The id bound is larger than the max id bound "
253 << vstate->options()->universal_limits_.max_id_bound << ".";
254 }
255
256 // Look for OpExtension instructions and register extensions.
257 // This parse should not produce any error messages. Hijack the context and
258 // replace the message consumer so that we do not pollute any state in input
259 // consumer.
260 spv_context_t hijacked_context = context;
261 hijacked_context.consumer = [](spv_message_level_t, const char*,
262 const spv_position_t&, const char*) {};
263 spvBinaryParse(&hijacked_context, vstate, words, num_words,
264 /* parsed_header = */ nullptr, ProcessExtensions,
265 /* diagnostic = */ nullptr);
266
267 // Parse the module and perform inline validation checks. These checks do
268 // not require the the knowledge of the whole module.
269 if (auto error = spvBinaryParse(&context, vstate, words, num_words,
270 /*parsed_header =*/nullptr,
271 ProcessInstruction, pDiagnostic)) {
272 return error;
273 }
274
275 std::vector<Instruction*> visited_entry_points;
276 for (auto& instruction : vstate->ordered_instructions()) {
277 {
278 // In order to do this work outside of Process Instruction we need to be
279 // able to, briefly, de-const the instruction.
280 Instruction* inst = const_cast<Instruction*>(&instruction);
281
282 if (inst->opcode() == SpvOpEntryPoint) {
283 const auto entry_point = inst->GetOperandAs<uint32_t>(1);
284 const auto execution_model = inst->GetOperandAs<SpvExecutionModel>(0);
285 const char* str = reinterpret_cast<const char*>(
286 inst->words().data() + inst->operand(2).offset);
287
288 ValidationState_t::EntryPointDescription desc;
289 desc.name = str;
290
291 std::vector<uint32_t> interfaces;
292 for (size_t j = 3; j < inst->operands().size(); ++j)
293 desc.interfaces.push_back(inst->word(inst->operand(j).offset));
294
295 vstate->RegisterEntryPoint(entry_point, execution_model,
296 std::move(desc));
297
298 if (visited_entry_points.size() > 0) {
299 for (const Instruction* check_inst : visited_entry_points) {
300 const auto check_execution_model =
301 check_inst->GetOperandAs<SpvExecutionModel>(0);
302 const char* check_str = reinterpret_cast<const char*>(
303 check_inst->words().data() + inst->operand(2).offset);
304 const std::string check_name(check_str);
305
306 if (desc.name == check_name &&
307 execution_model == check_execution_model) {
308 return vstate->diag(SPV_ERROR_INVALID_DATA, inst)
309 << "2 Entry points cannot share the same name and "
310 "ExecutionMode.";
311 }
312 }
313 }
314 visited_entry_points.push_back(inst);
315 }
316 if (inst->opcode() == SpvOpFunctionCall) {
317 if (!vstate->in_function_body()) {
318 return vstate->diag(SPV_ERROR_INVALID_LAYOUT, &instruction)
319 << "A FunctionCall must happen within a function body.";
320 }
321
322 const auto called_id = inst->GetOperandAs<uint32_t>(2);
323 if (spvIsWebGPUEnv(context.target_env) &&
324 !vstate->IsFunctionCallDefined(called_id)) {
325 return vstate->diag(SPV_ERROR_INVALID_LAYOUT, &instruction)
326 << "For WebGPU, functions need to be defined before being "
327 "called.";
328 }
329
330 vstate->AddFunctionCallTarget(called_id);
331 }
332
333 if (vstate->in_function_body()) {
334 inst->set_function(&(vstate->current_function()));
335 inst->set_block(vstate->current_function().current_block());
336
337 if (vstate->in_block() && spvOpcodeIsBlockTerminator(inst->opcode())) {
338 vstate->current_function().current_block()->set_terminator(inst);
339 }
340 }
341
342 if (auto error = IdPass(*vstate, inst)) return error;
343 }
344
345 if (auto error = CapabilityPass(*vstate, &instruction)) return error;
346 if (auto error = ModuleLayoutPass(*vstate, &instruction)) return error;
347 if (auto error = CfgPass(*vstate, &instruction)) return error;
348 if (auto error = InstructionPass(*vstate, &instruction)) return error;
349
350 // Now that all of the checks are done, update the state.
351 {
352 Instruction* inst = const_cast<Instruction*>(&instruction);
353 vstate->RegisterInstruction(inst);
354 if (inst->opcode() == SpvOpTypeForwardPointer) {
355 vstate->RegisterForwardPointer(inst->GetOperandAs<uint32_t>(0));
356 }
357 }
358 }
359
360 if (!vstate->has_memory_model_specified())
361 return vstate->diag(SPV_ERROR_INVALID_LAYOUT, nullptr)
362 << "Missing required OpMemoryModel instruction.";
363
364 if (vstate->in_function_body())
365 return vstate->diag(SPV_ERROR_INVALID_LAYOUT, nullptr)
366 << "Missing OpFunctionEnd at end of module.";
367
368 // Catch undefined forward references before performing further checks.
369 if (auto error = ValidateForwardDecls(*vstate)) return error;
370
371 // ID usage needs be handled in its own iteration of the instructions,
372 // between the two others. It depends on the first loop to have been
373 // finished, so that all instructions have been registered. And the following
374 // loop depends on all of the usage data being populated. Thus it cannot live
375 // in either of those iterations.
376 // It should also live after the forward declaration check, since it will
377 // have problems with missing forward declarations, but give less useful error
378 // messages.
379 for (size_t i = 0; i < vstate->ordered_instructions().size(); ++i) {
380 auto& instruction = vstate->ordered_instructions()[i];
381 if (auto error = UpdateIdUse(*vstate, &instruction)) return error;
382 }
383
384 // Validate individual opcodes.
385 for (size_t i = 0; i < vstate->ordered_instructions().size(); ++i) {
386 auto& instruction = vstate->ordered_instructions()[i];
387
388 // Keep these passes in the order they appear in the SPIR-V specification
389 // sections to maintain test consistency.
390 if (auto error = MiscPass(*vstate, &instruction)) return error;
391 if (auto error = DebugPass(*vstate, &instruction)) return error;
392 if (auto error = AnnotationPass(*vstate, &instruction)) return error;
393 if (auto error = ExtensionPass(*vstate, &instruction)) return error;
394 if (auto error = ModeSettingPass(*vstate, &instruction)) return error;
395 if (auto error = TypePass(*vstate, &instruction)) return error;
396 if (auto error = ConstantPass(*vstate, &instruction)) return error;
397 if (auto error = MemoryPass(*vstate, &instruction)) return error;
398 if (auto error = FunctionPass(*vstate, &instruction)) return error;
399 if (auto error = ImagePass(*vstate, &instruction)) return error;
400 if (auto error = ConversionPass(*vstate, &instruction)) return error;
401 if (auto error = CompositesPass(*vstate, &instruction)) return error;
402 if (auto error = ArithmeticsPass(*vstate, &instruction)) return error;
403 if (auto error = BitwisePass(*vstate, &instruction)) return error;
404 if (auto error = LogicalsPass(*vstate, &instruction)) return error;
405 if (auto error = ControlFlowPass(*vstate, &instruction)) return error;
406 if (auto error = DerivativesPass(*vstate, &instruction)) return error;
407 if (auto error = AtomicsPass(*vstate, &instruction)) return error;
408 if (auto error = PrimitivesPass(*vstate, &instruction)) return error;
409 if (auto error = BarriersPass(*vstate, &instruction)) return error;
410 // Group
411 // Device-Side Enqueue
412 // Pipe
413 if (auto error = NonUniformPass(*vstate, &instruction)) return error;
414
415 if (auto error = LiteralsPass(*vstate, &instruction)) return error;
416 }
417
418 // Validate the preconditions involving adjacent instructions. e.g. SpvOpPhi
419 // must only be preceeded by SpvOpLabel, SpvOpPhi, or SpvOpLine.
420 if (auto error = ValidateAdjacency(*vstate)) return error;
421
422 if (auto error = ValidateEntryPoints(*vstate)) return error;
423 // CFG checks are performed after the binary has been parsed
424 // and the CFGPass has collected information about the control flow
425 if (auto error = PerformCfgChecks(*vstate)) return error;
426 if (auto error = CheckIdDefinitionDominateUse(*vstate)) return error;
427 if (auto error = ValidateDecorations(*vstate)) return error;
428 if (auto error = ValidateInterfaces(*vstate)) return error;
429 // TODO(dsinclair): Restructure ValidateBuiltins so we can move into the
430 // for() above as it loops over all ordered_instructions internally.
431 if (auto error = ValidateBuiltIns(*vstate)) return error;
432 // These checks must be performed after individual opcode checks because
433 // those checks register the limitation checked here.
434 for (const auto& inst : vstate->ordered_instructions()) {
435 if (auto error = ValidateExecutionLimitations(*vstate, &inst)) return error;
436 if (auto error = ValidateSmallTypeUses(*vstate, &inst)) return error;
437 }
438
439 return SPV_SUCCESS;
440}
441
442} // namespace
443
444spv_result_t ValidateBinaryAndKeepValidationState(
445 const spv_const_context context, spv_const_validator_options options,
446 const uint32_t* words, const size_t num_words, spv_diagnostic* pDiagnostic,
447 std::unique_ptr<ValidationState_t>* vstate) {
448 spv_context_t hijack_context = *context;
449 if (pDiagnostic) {
450 *pDiagnostic = nullptr;
451 UseDiagnosticAsMessageConsumer(&hijack_context, pDiagnostic);
452 }
453
454 vstate->reset(new ValidationState_t(&hijack_context, options, words,
455 num_words, kDefaultMaxNumOfWarnings));
456
457 return ValidateBinaryUsingContextAndValidationState(
458 hijack_context, words, num_words, pDiagnostic, vstate->get());
459}
460
461} // namespace val
462} // namespace spvtools
463
464spv_result_t spvValidate(const spv_const_context context,
465 const spv_const_binary binary,
466 spv_diagnostic* pDiagnostic) {
467 return spvValidateBinary(context, binary->code, binary->wordCount,
468 pDiagnostic);
469}
470
471spv_result_t spvValidateBinary(const spv_const_context context,
472 const uint32_t* words, const size_t num_words,
473 spv_diagnostic* pDiagnostic) {
474 spv_context_t hijack_context = *context;
475 if (pDiagnostic) {
476 *pDiagnostic = nullptr;
477 spvtools::UseDiagnosticAsMessageConsumer(&hijack_context, pDiagnostic);
478 }
479
480 // This interface is used for default command line options.
481 spv_validator_options default_options = spvValidatorOptionsCreate();
482
483 // Create the ValidationState using the context and default options.
484 spvtools::val::ValidationState_t vstate(&hijack_context, default_options,
485 words, num_words,
486 kDefaultMaxNumOfWarnings);
487
488 spv_result_t result =
489 spvtools::val::ValidateBinaryUsingContextAndValidationState(
490 hijack_context, words, num_words, pDiagnostic, &vstate);
491
492 spvValidatorOptionsDestroy(default_options);
493 return result;
494}
495
496spv_result_t spvValidateWithOptions(const spv_const_context context,
497 spv_const_validator_options options,
498 const spv_const_binary binary,
499 spv_diagnostic* pDiagnostic) {
500 spv_context_t hijack_context = *context;
501 if (pDiagnostic) {
502 *pDiagnostic = nullptr;
503 spvtools::UseDiagnosticAsMessageConsumer(&hijack_context, pDiagnostic);
504 }
505
506 // Create the ValidationState using the context.
507 spvtools::val::ValidationState_t vstate(&hijack_context, options,
508 binary->code, binary->wordCount,
509 kDefaultMaxNumOfWarnings);
510
511 return spvtools::val::ValidateBinaryUsingContextAndValidationState(
512 hijack_context, binary->code, binary->wordCount, pDiagnostic, &vstate);
513}
514