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 <algorithm>
16#include <cassert>
17#include <functional>
18#include <iostream>
19#include <iterator>
20#include <map>
21#include <string>
22#include <tuple>
23#include <unordered_map>
24#include <unordered_set>
25#include <utility>
26#include <vector>
27
28#include "source/cfa.h"
29#include "source/opcode.h"
30#include "source/spirv_target_env.h"
31#include "source/spirv_validator_options.h"
32#include "source/val/basic_block.h"
33#include "source/val/construct.h"
34#include "source/val/function.h"
35#include "source/val/validate.h"
36#include "source/val/validation_state.h"
37
38namespace spvtools {
39namespace val {
40namespace {
41
42spv_result_t ValidatePhi(ValidationState_t& _, const Instruction* inst) {
43 auto block = inst->block();
44 size_t num_in_ops = inst->words().size() - 3;
45 if (num_in_ops % 2 != 0) {
46 return _.diag(SPV_ERROR_INVALID_ID, inst)
47 << "OpPhi does not have an equal number of incoming values and "
48 "basic blocks.";
49 }
50
51 const Instruction* type_inst = _.FindDef(inst->type_id());
52 assert(type_inst);
53
54 const SpvOp type_opcode = type_inst->opcode();
55 if (type_opcode == SpvOpTypePointer &&
56 _.addressing_model() == SpvAddressingModelLogical) {
57 if (!_.features().variable_pointers &&
58 !_.features().variable_pointers_storage_buffer) {
59 return _.diag(SPV_ERROR_INVALID_DATA, inst)
60 << "Using pointers with OpPhi requires capability "
61 << "VariablePointers or VariablePointersStorageBuffer";
62 }
63 }
64
65 if (!_.options()->before_hlsl_legalization) {
66 if (type_opcode == SpvOpTypeSampledImage ||
67 (_.HasCapability(SpvCapabilityShader) &&
68 (type_opcode == SpvOpTypeImage || type_opcode == SpvOpTypeSampler))) {
69 return _.diag(SPV_ERROR_INVALID_ID, inst)
70 << "Result type cannot be Op" << spvOpcodeString(type_opcode);
71 }
72 }
73
74 // Create a uniqued vector of predecessor ids for comparison against
75 // incoming values. OpBranchConditional %cond %label %label produces two
76 // predecessors in the CFG.
77 std::vector<uint32_t> pred_ids;
78 std::transform(block->predecessors()->begin(), block->predecessors()->end(),
79 std::back_inserter(pred_ids),
80 [](const BasicBlock* b) { return b->id(); });
81 std::sort(pred_ids.begin(), pred_ids.end());
82 pred_ids.erase(std::unique(pred_ids.begin(), pred_ids.end()), pred_ids.end());
83
84 size_t num_edges = num_in_ops / 2;
85 if (num_edges != pred_ids.size()) {
86 return _.diag(SPV_ERROR_INVALID_ID, inst)
87 << "OpPhi's number of incoming blocks (" << num_edges
88 << ") does not match block's predecessor count ("
89 << block->predecessors()->size() << ").";
90 }
91
92 for (size_t i = 3; i < inst->words().size(); ++i) {
93 auto inc_id = inst->word(i);
94 if (i % 2 == 1) {
95 // Incoming value type must match the phi result type.
96 auto inc_type_id = _.GetTypeId(inc_id);
97 if (inst->type_id() != inc_type_id) {
98 return _.diag(SPV_ERROR_INVALID_ID, inst)
99 << "OpPhi's result type <id> " << _.getIdName(inst->type_id())
100 << " does not match incoming value <id> " << _.getIdName(inc_id)
101 << " type <id> " << _.getIdName(inc_type_id) << ".";
102 }
103 } else {
104 if (_.GetIdOpcode(inc_id) != SpvOpLabel) {
105 return _.diag(SPV_ERROR_INVALID_ID, inst)
106 << "OpPhi's incoming basic block <id> " << _.getIdName(inc_id)
107 << " is not an OpLabel.";
108 }
109
110 // Incoming basic block must be an immediate predecessor of the phi's
111 // block.
112 if (!std::binary_search(pred_ids.begin(), pred_ids.end(), inc_id)) {
113 return _.diag(SPV_ERROR_INVALID_ID, inst)
114 << "OpPhi's incoming basic block <id> " << _.getIdName(inc_id)
115 << " is not a predecessor of <id> " << _.getIdName(block->id())
116 << ".";
117 }
118 }
119 }
120
121 return SPV_SUCCESS;
122}
123
124spv_result_t ValidateBranch(ValidationState_t& _, const Instruction* inst) {
125 // target operands must be OpLabel
126 const auto id = inst->GetOperandAs<uint32_t>(0);
127 const auto target = _.FindDef(id);
128 if (!target || SpvOpLabel != target->opcode()) {
129 return _.diag(SPV_ERROR_INVALID_ID, inst)
130 << "'Target Label' operands for OpBranch must be the ID "
131 "of an OpLabel instruction";
132 }
133
134 return SPV_SUCCESS;
135}
136
137spv_result_t ValidateBranchConditional(ValidationState_t& _,
138 const Instruction* inst) {
139 // num_operands is either 3 or 5 --- if 5, the last two need to be literal
140 // integers
141 const auto num_operands = inst->operands().size();
142 if (num_operands != 3 && num_operands != 5) {
143 return _.diag(SPV_ERROR_INVALID_ID, inst)
144 << "OpBranchConditional requires either 3 or 5 parameters";
145 }
146
147 // grab the condition operand and check that it is a bool
148 const auto cond_id = inst->GetOperandAs<uint32_t>(0);
149 const auto cond_op = _.FindDef(cond_id);
150 if (!cond_op || !cond_op->type_id() ||
151 !_.IsBoolScalarType(cond_op->type_id())) {
152 return _.diag(SPV_ERROR_INVALID_ID, inst) << "Condition operand for "
153 "OpBranchConditional must be "
154 "of boolean type";
155 }
156
157 // target operands must be OpLabel
158 // note that we don't need to check that the target labels are in the same
159 // function,
160 // PerformCfgChecks already checks for that
161 const auto true_id = inst->GetOperandAs<uint32_t>(1);
162 const auto true_target = _.FindDef(true_id);
163 if (!true_target || SpvOpLabel != true_target->opcode()) {
164 return _.diag(SPV_ERROR_INVALID_ID, inst)
165 << "The 'True Label' operand for OpBranchConditional must be the "
166 "ID of an OpLabel instruction";
167 }
168
169 const auto false_id = inst->GetOperandAs<uint32_t>(2);
170 const auto false_target = _.FindDef(false_id);
171 if (!false_target || SpvOpLabel != false_target->opcode()) {
172 return _.diag(SPV_ERROR_INVALID_ID, inst)
173 << "The 'False Label' operand for OpBranchConditional must be the "
174 "ID of an OpLabel instruction";
175 }
176
177 return SPV_SUCCESS;
178}
179
180spv_result_t ValidateSwitch(ValidationState_t& _, const Instruction* inst) {
181 const auto num_operands = inst->operands().size();
182 // At least two operands (selector, default), any more than that are
183 // literal/target.
184
185 // target operands must be OpLabel
186 for (size_t i = 2; i < num_operands; i += 2) {
187 // literal, id
188 const auto id = inst->GetOperandAs<uint32_t>(i + 1);
189 const auto target = _.FindDef(id);
190 if (!target || SpvOpLabel != target->opcode()) {
191 return _.diag(SPV_ERROR_INVALID_ID, inst)
192 << "'Target Label' operands for OpSwitch must be IDs of an "
193 "OpLabel instruction";
194 }
195 }
196
197 return SPV_SUCCESS;
198}
199
200spv_result_t ValidateReturnValue(ValidationState_t& _,
201 const Instruction* inst) {
202 const auto value_id = inst->GetOperandAs<uint32_t>(0);
203 const auto value = _.FindDef(value_id);
204 if (!value || !value->type_id()) {
205 return _.diag(SPV_ERROR_INVALID_ID, inst)
206 << "OpReturnValue Value <id> '" << _.getIdName(value_id)
207 << "' does not represent a value.";
208 }
209 auto value_type = _.FindDef(value->type_id());
210 if (!value_type || SpvOpTypeVoid == value_type->opcode()) {
211 return _.diag(SPV_ERROR_INVALID_ID, inst)
212 << "OpReturnValue value's type <id> '"
213 << _.getIdName(value->type_id()) << "' is missing or void.";
214 }
215
216 const bool uses_variable_pointer =
217 _.features().variable_pointers ||
218 _.features().variable_pointers_storage_buffer;
219
220 if (_.addressing_model() == SpvAddressingModelLogical &&
221 SpvOpTypePointer == value_type->opcode() && !uses_variable_pointer &&
222 !_.options()->relax_logical_pointer) {
223 return _.diag(SPV_ERROR_INVALID_ID, inst)
224 << "OpReturnValue value's type <id> '"
225 << _.getIdName(value->type_id())
226 << "' is a pointer, which is invalid in the Logical addressing "
227 "model.";
228 }
229
230 const auto function = inst->function();
231 const auto return_type = _.FindDef(function->GetResultTypeId());
232 if (!return_type || return_type->id() != value_type->id()) {
233 return _.diag(SPV_ERROR_INVALID_ID, inst)
234 << "OpReturnValue Value <id> '" << _.getIdName(value_id)
235 << "'s type does not match OpFunction's return type.";
236 }
237
238 return SPV_SUCCESS;
239}
240
241spv_result_t ValidateLoopMerge(ValidationState_t& _, const Instruction* inst) {
242 const auto merge_id = inst->GetOperandAs<uint32_t>(0);
243 const auto merge = _.FindDef(merge_id);
244 if (!merge || merge->opcode() != SpvOpLabel) {
245 return _.diag(SPV_ERROR_INVALID_ID, inst)
246 << "Merge Block " << _.getIdName(merge_id) << " must be an OpLabel";
247 }
248 if (merge_id == inst->block()->id()) {
249 return _.diag(SPV_ERROR_INVALID_ID, inst)
250 << "Merge Block may not be the block containing the OpLoopMerge\n";
251 }
252
253 const auto continue_id = inst->GetOperandAs<uint32_t>(1);
254 const auto continue_target = _.FindDef(continue_id);
255 if (!continue_target || continue_target->opcode() != SpvOpLabel) {
256 return _.diag(SPV_ERROR_INVALID_ID, inst)
257 << "Continue Target " << _.getIdName(continue_id)
258 << " must be an OpLabel";
259 }
260
261 if (merge_id == continue_id) {
262 return _.diag(SPV_ERROR_INVALID_ID, inst)
263 << "Merge Block and Continue Target must be different ids";
264 }
265
266 const auto loop_control = inst->GetOperandAs<uint32_t>(2);
267 if ((loop_control >> SpvLoopControlUnrollShift) & 0x1 &&
268 (loop_control >> SpvLoopControlDontUnrollShift) & 0x1) {
269 return _.diag(SPV_ERROR_INVALID_DATA, inst)
270 << "Unroll and DontUnroll loop controls must not both be specified";
271 }
272 if ((loop_control >> SpvLoopControlDontUnrollShift) & 0x1 &&
273 (loop_control >> SpvLoopControlPeelCountShift) & 0x1) {
274 return _.diag(SPV_ERROR_INVALID_DATA, inst) << "PeelCount and DontUnroll "
275 "loop controls must not "
276 "both be specified";
277 }
278 if ((loop_control >> SpvLoopControlDontUnrollShift) & 0x1 &&
279 (loop_control >> SpvLoopControlPartialCountShift) & 0x1) {
280 return _.diag(SPV_ERROR_INVALID_DATA, inst) << "PartialCount and "
281 "DontUnroll loop controls "
282 "must not both be specified";
283 }
284
285 uint32_t operand = 3;
286 if ((loop_control >> SpvLoopControlDependencyLengthShift) & 0x1) {
287 ++operand;
288 }
289 if ((loop_control >> SpvLoopControlMinIterationsShift) & 0x1) {
290 ++operand;
291 }
292 if ((loop_control >> SpvLoopControlMaxIterationsShift) & 0x1) {
293 ++operand;
294 }
295 if ((loop_control >> SpvLoopControlIterationMultipleShift) & 0x1) {
296 if (inst->operands().size() < operand ||
297 inst->GetOperandAs<uint32_t>(operand) == 0) {
298 return _.diag(SPV_ERROR_INVALID_DATA, inst) << "IterationMultiple loop "
299 "control operand must be "
300 "greater than zero";
301 }
302 ++operand;
303 }
304 if ((loop_control >> SpvLoopControlPeelCountShift) & 0x1) {
305 ++operand;
306 }
307 if ((loop_control >> SpvLoopControlPartialCountShift) & 0x1) {
308 ++operand;
309 }
310
311 // That the right number of operands is present is checked by the parser. The
312 // above code tracks operands for expanded validation checking in the future.
313
314 return SPV_SUCCESS;
315}
316
317} // namespace
318
319void printDominatorList(const BasicBlock& b) {
320 std::cout << b.id() << " is dominated by: ";
321 const BasicBlock* bb = &b;
322 while (bb->immediate_dominator() != bb) {
323 bb = bb->immediate_dominator();
324 std::cout << bb->id() << " ";
325 }
326}
327
328#define CFG_ASSERT(ASSERT_FUNC, TARGET) \
329 if (spv_result_t rcode = ASSERT_FUNC(_, TARGET)) return rcode
330
331spv_result_t FirstBlockAssert(ValidationState_t& _, uint32_t target) {
332 if (_.current_function().IsFirstBlock(target)) {
333 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(_.current_function().id()))
334 << "First block " << _.getIdName(target) << " of function "
335 << _.getIdName(_.current_function().id()) << " is targeted by block "
336 << _.getIdName(_.current_function().current_block()->id());
337 }
338 return SPV_SUCCESS;
339}
340
341spv_result_t MergeBlockAssert(ValidationState_t& _, uint32_t merge_block) {
342 if (_.current_function().IsBlockType(merge_block, kBlockTypeMerge)) {
343 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(_.current_function().id()))
344 << "Block " << _.getIdName(merge_block)
345 << " is already a merge block for another header";
346 }
347 return SPV_SUCCESS;
348}
349
350/// Update the continue construct's exit blocks once the backedge blocks are
351/// identified in the CFG.
352void UpdateContinueConstructExitBlocks(
353 Function& function,
354 const std::vector<std::pair<uint32_t, uint32_t>>& back_edges) {
355 auto& constructs = function.constructs();
356 // TODO(umar): Think of a faster way to do this
357 for (auto& edge : back_edges) {
358 uint32_t back_edge_block_id;
359 uint32_t loop_header_block_id;
360 std::tie(back_edge_block_id, loop_header_block_id) = edge;
361 auto is_this_header = [=](Construct& c) {
362 return c.type() == ConstructType::kLoop &&
363 c.entry_block()->id() == loop_header_block_id;
364 };
365
366 for (auto construct : constructs) {
367 if (is_this_header(construct)) {
368 Construct* continue_construct =
369 construct.corresponding_constructs().back();
370 assert(continue_construct->type() == ConstructType::kContinue);
371
372 BasicBlock* back_edge_block;
373 std::tie(back_edge_block, std::ignore) =
374 function.GetBlock(back_edge_block_id);
375 continue_construct->set_exit(back_edge_block);
376 }
377 }
378 }
379}
380
381std::tuple<std::string, std::string, std::string> ConstructNames(
382 ConstructType type) {
383 std::string construct_name, header_name, exit_name;
384
385 switch (type) {
386 case ConstructType::kSelection:
387 construct_name = "selection";
388 header_name = "selection header";
389 exit_name = "merge block";
390 break;
391 case ConstructType::kLoop:
392 construct_name = "loop";
393 header_name = "loop header";
394 exit_name = "merge block";
395 break;
396 case ConstructType::kContinue:
397 construct_name = "continue";
398 header_name = "continue target";
399 exit_name = "back-edge block";
400 break;
401 case ConstructType::kCase:
402 construct_name = "case";
403 header_name = "case entry block";
404 exit_name = "case exit block";
405 break;
406 default:
407 assert(1 == 0 && "Not defined type");
408 }
409
410 return std::make_tuple(construct_name, header_name, exit_name);
411}
412
413/// Constructs an error message for construct validation errors
414std::string ConstructErrorString(const Construct& construct,
415 const std::string& header_string,
416 const std::string& exit_string,
417 const std::string& dominate_text) {
418 std::string construct_name, header_name, exit_name;
419 std::tie(construct_name, header_name, exit_name) =
420 ConstructNames(construct.type());
421
422 // TODO(umar): Add header block for continue constructs to error message
423 return "The " + construct_name + " construct with the " + header_name + " " +
424 header_string + " " + dominate_text + " the " + exit_name + " " +
425 exit_string;
426}
427
428// Finds the fall through case construct of |target_block| and records it in
429// |case_fall_through|. Returns SPV_ERROR_INVALID_CFG if the case construct
430// headed by |target_block| branches to multiple case constructs.
431spv_result_t FindCaseFallThrough(
432 ValidationState_t& _, BasicBlock* target_block, uint32_t* case_fall_through,
433 const BasicBlock* merge, const std::unordered_set<uint32_t>& case_targets,
434 Function* function) {
435 std::vector<BasicBlock*> stack;
436 stack.push_back(target_block);
437 std::unordered_set<const BasicBlock*> visited;
438 bool target_reachable = target_block->reachable();
439 int target_depth = function->GetBlockDepth(target_block);
440 while (!stack.empty()) {
441 auto block = stack.back();
442 stack.pop_back();
443
444 if (block == merge) continue;
445
446 if (!visited.insert(block).second) continue;
447
448 if (target_reachable && block->reachable() &&
449 target_block->dominates(*block)) {
450 // Still in the case construct.
451 for (auto successor : *block->successors()) {
452 stack.push_back(successor);
453 }
454 } else {
455 // Exiting the case construct to non-merge block.
456 if (!case_targets.count(block->id())) {
457 int depth = function->GetBlockDepth(block);
458 if ((depth < target_depth) ||
459 (depth == target_depth && block->is_type(kBlockTypeContinue))) {
460 continue;
461 }
462
463 return _.diag(SPV_ERROR_INVALID_CFG, target_block->label())
464 << "Case construct that targets "
465 << _.getIdName(target_block->id())
466 << " has invalid branch to block " << _.getIdName(block->id())
467 << " (not another case construct, corresponding merge, outer "
468 "loop merge or outer loop continue)";
469 }
470
471 if (*case_fall_through == 0u) {
472 if (target_block != block) {
473 *case_fall_through = block->id();
474 }
475 } else if (*case_fall_through != block->id()) {
476 // Case construct has at most one branch to another case construct.
477 return _.diag(SPV_ERROR_INVALID_CFG, target_block->label())
478 << "Case construct that targets "
479 << _.getIdName(target_block->id())
480 << " has branches to multiple other case construct targets "
481 << _.getIdName(*case_fall_through) << " and "
482 << _.getIdName(block->id());
483 }
484 }
485 }
486
487 return SPV_SUCCESS;
488}
489
490spv_result_t StructuredSwitchChecks(ValidationState_t& _, Function* function,
491 const Instruction* switch_inst,
492 const BasicBlock* header,
493 const BasicBlock* merge) {
494 std::unordered_set<uint32_t> case_targets;
495 for (uint32_t i = 1; i < switch_inst->operands().size(); i += 2) {
496 uint32_t target = switch_inst->GetOperandAs<uint32_t>(i);
497 if (target != merge->id()) case_targets.insert(target);
498 }
499 // Tracks how many times each case construct is targeted by another case
500 // construct.
501 std::map<uint32_t, uint32_t> num_fall_through_targeted;
502 uint32_t default_case_fall_through = 0u;
503 uint32_t default_target = switch_inst->GetOperandAs<uint32_t>(1u);
504 bool default_appears_multiple_times = false;
505 for (uint32_t i = 3; i < switch_inst->operands().size(); i += 2) {
506 if (default_target == switch_inst->GetOperandAs<uint32_t>(i)) {
507 default_appears_multiple_times = true;
508 break;
509 }
510 }
511 std::unordered_map<uint32_t, uint32_t> seen_to_fall_through;
512 for (uint32_t i = 1; i < switch_inst->operands().size(); i += 2) {
513 uint32_t target = switch_inst->GetOperandAs<uint32_t>(i);
514 if (target == merge->id()) continue;
515
516 uint32_t case_fall_through = 0u;
517 auto seen_iter = seen_to_fall_through.find(target);
518 if (seen_iter == seen_to_fall_through.end()) {
519 const auto target_block = function->GetBlock(target).first;
520 // OpSwitch must dominate all its case constructs.
521 if (header->reachable() && target_block->reachable() &&
522 !header->dominates(*target_block)) {
523 return _.diag(SPV_ERROR_INVALID_CFG, header->label())
524 << "Selection header " << _.getIdName(header->id())
525 << " does not dominate its case construct "
526 << _.getIdName(target);
527 }
528
529 if (auto error = FindCaseFallThrough(_, target_block, &case_fall_through,
530 merge, case_targets, function)) {
531 return error;
532 }
533
534 // Track how many time the fall through case has been targeted.
535 if (case_fall_through != 0u) {
536 auto where = num_fall_through_targeted.lower_bound(case_fall_through);
537 if (where == num_fall_through_targeted.end() ||
538 where->first != case_fall_through) {
539 num_fall_through_targeted.insert(
540 where, std::make_pair(case_fall_through, 1));
541 } else {
542 where->second++;
543 }
544 }
545 seen_to_fall_through.insert(std::make_pair(target, case_fall_through));
546 } else {
547 case_fall_through = seen_iter->second;
548 }
549
550 if (case_fall_through == default_target &&
551 !default_appears_multiple_times) {
552 case_fall_through = default_case_fall_through;
553 }
554 if (case_fall_through != 0u) {
555 bool is_default = i == 1;
556 if (is_default) {
557 default_case_fall_through = case_fall_through;
558 } else {
559 // Allow code like:
560 // case x:
561 // case y:
562 // ...
563 // case z:
564 //
565 // Where x and y target the same block and fall through to z.
566 uint32_t j = i;
567 while ((j + 2 < switch_inst->operands().size()) &&
568 target == switch_inst->GetOperandAs<uint32_t>(j + 2)) {
569 j += 2;
570 }
571 // If Target T1 branches to Target T2, or if Target T1 branches to the
572 // Default target and the Default target branches to Target T2, then T1
573 // must immediately precede T2 in the list of OpSwitch Target operands.
574 if ((switch_inst->operands().size() < j + 2) ||
575 (case_fall_through != switch_inst->GetOperandAs<uint32_t>(j + 2))) {
576 return _.diag(SPV_ERROR_INVALID_CFG, switch_inst)
577 << "Case construct that targets " << _.getIdName(target)
578 << " has branches to the case construct that targets "
579 << _.getIdName(case_fall_through)
580 << ", but does not immediately precede it in the "
581 "OpSwitch's target list";
582 }
583 }
584 }
585 }
586
587 // Each case construct must be branched to by at most one other case
588 // construct.
589 for (const auto& pair : num_fall_through_targeted) {
590 if (pair.second > 1) {
591 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(pair.first))
592 << "Multiple case constructs have branches to the case construct "
593 "that targets "
594 << _.getIdName(pair.first);
595 }
596 }
597
598 return SPV_SUCCESS;
599}
600
601// Validates that all CFG divergences (i.e. conditional branch or switch) are
602// structured correctly. Either divergence is preceded by a merge instruction
603// or the divergence introduces at most one unseen label.
604spv_result_t ValidateStructuredSelections(
605 ValidationState_t& _, const std::vector<const BasicBlock*>& postorder) {
606 std::unordered_set<uint32_t> seen;
607 for (auto iter = postorder.rbegin(); iter != postorder.rend(); ++iter) {
608 const auto* block = *iter;
609 const auto* terminator = block->terminator();
610 if (!terminator) continue;
611 const auto index = terminator - &_.ordered_instructions()[0];
612 auto* merge = &_.ordered_instructions()[index - 1];
613 // Marks merges and continues as seen.
614 if (merge->opcode() == SpvOpSelectionMerge) {
615 seen.insert(merge->GetOperandAs<uint32_t>(0));
616 } else if (merge->opcode() == SpvOpLoopMerge) {
617 seen.insert(merge->GetOperandAs<uint32_t>(0));
618 seen.insert(merge->GetOperandAs<uint32_t>(1));
619 } else {
620 // Only track the pointer if it is a merge instruction.
621 merge = nullptr;
622 }
623
624 // Skip unreachable blocks.
625 if (!block->reachable()) continue;
626
627 if (terminator->opcode() == SpvOpBranchConditional) {
628 const auto true_label = terminator->GetOperandAs<uint32_t>(1);
629 const auto false_label = terminator->GetOperandAs<uint32_t>(2);
630 // Mark the upcoming blocks as seen now, but only error out if this block
631 // was missing a merge instruction and both labels hadn't been seen
632 // previously.
633 const bool both_unseen =
634 seen.insert(true_label).second && seen.insert(false_label).second;
635 if (!merge && both_unseen) {
636 return _.diag(SPV_ERROR_INVALID_CFG, terminator)
637 << "Selection must be structured";
638 }
639 } else if (terminator->opcode() == SpvOpSwitch) {
640 uint32_t count = 0;
641 // Mark the targets as seen now, but only error out if this block was
642 // missing a merge instruction and there were multiple unseen labels.
643 for (uint32_t i = 1; i < terminator->operands().size(); i += 2) {
644 const auto target = terminator->GetOperandAs<uint32_t>(i);
645 if (seen.insert(target).second) {
646 count++;
647 }
648 }
649 if (!merge && count > 1) {
650 return _.diag(SPV_ERROR_INVALID_CFG, terminator)
651 << "Selection must be structured";
652 }
653 }
654 }
655
656 return SPV_SUCCESS;
657}
658
659spv_result_t StructuredControlFlowChecks(
660 ValidationState_t& _, Function* function,
661 const std::vector<std::pair<uint32_t, uint32_t>>& back_edges,
662 const std::vector<const BasicBlock*>& postorder) {
663 /// Check all backedges target only loop headers and have exactly one
664 /// back-edge branching to it
665
666 // Map a loop header to blocks with back-edges to the loop header.
667 std::map<uint32_t, std::unordered_set<uint32_t>> loop_latch_blocks;
668 for (auto back_edge : back_edges) {
669 uint32_t back_edge_block;
670 uint32_t header_block;
671 std::tie(back_edge_block, header_block) = back_edge;
672 if (!function->IsBlockType(header_block, kBlockTypeLoop)) {
673 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(back_edge_block))
674 << "Back-edges (" << _.getIdName(back_edge_block) << " -> "
675 << _.getIdName(header_block)
676 << ") can only be formed between a block and a loop header.";
677 }
678 loop_latch_blocks[header_block].insert(back_edge_block);
679 }
680
681 // Check the loop headers have exactly one back-edge branching to it
682 for (BasicBlock* loop_header : function->ordered_blocks()) {
683 if (!loop_header->reachable()) continue;
684 if (!loop_header->is_type(kBlockTypeLoop)) continue;
685 auto loop_header_id = loop_header->id();
686 auto num_latch_blocks = loop_latch_blocks[loop_header_id].size();
687 if (num_latch_blocks != 1) {
688 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(loop_header_id))
689 << "Loop header " << _.getIdName(loop_header_id)
690 << " is targeted by " << num_latch_blocks
691 << " back-edge blocks but the standard requires exactly one";
692 }
693 }
694
695 // Check construct rules
696 for (const Construct& construct : function->constructs()) {
697 auto header = construct.entry_block();
698 auto merge = construct.exit_block();
699
700 if (header->reachable() && !merge) {
701 std::string construct_name, header_name, exit_name;
702 std::tie(construct_name, header_name, exit_name) =
703 ConstructNames(construct.type());
704 return _.diag(SPV_ERROR_INTERNAL, _.FindDef(header->id()))
705 << "Construct " + construct_name + " with " + header_name + " " +
706 _.getIdName(header->id()) + " does not have a " +
707 exit_name + ". This may be a bug in the validator.";
708 }
709
710 // If the exit block is reachable then it's dominated by the
711 // header.
712 if (merge && merge->reachable()) {
713 if (!header->dominates(*merge)) {
714 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
715 << ConstructErrorString(construct, _.getIdName(header->id()),
716 _.getIdName(merge->id()),
717 "does not dominate");
718 }
719 // If it's really a merge block for a selection or loop, then it must be
720 // *strictly* dominated by the header.
721 if (construct.ExitBlockIsMergeBlock() && (header == merge)) {
722 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
723 << ConstructErrorString(construct, _.getIdName(header->id()),
724 _.getIdName(merge->id()),
725 "does not strictly dominate");
726 }
727 }
728 // Check post-dominance for continue constructs. But dominance and
729 // post-dominance only make sense when the construct is reachable.
730 if (header->reachable() && construct.type() == ConstructType::kContinue) {
731 if (!merge->postdominates(*header)) {
732 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
733 << ConstructErrorString(construct, _.getIdName(header->id()),
734 _.getIdName(merge->id()),
735 "is not post dominated by");
736 }
737 }
738
739 Construct::ConstructBlockSet construct_blocks = construct.blocks(function);
740 std::string construct_name, header_name, exit_name;
741 std::tie(construct_name, header_name, exit_name) =
742 ConstructNames(construct.type());
743 for (auto block : construct_blocks) {
744 // Check that all exits from the construct are via structured exits.
745 for (auto succ : *block->successors()) {
746 if (block->reachable() && !construct_blocks.count(succ) &&
747 !construct.IsStructuredExit(_, succ)) {
748 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
749 << "block <ID> " << _.getIdName(block->id()) << " exits the "
750 << construct_name << " headed by <ID> "
751 << _.getIdName(header->id())
752 << ", but not via a structured exit";
753 }
754 }
755 if (block == header) continue;
756 // Check that for all non-header blocks, all predecessors are within this
757 // construct.
758 for (auto pred : *block->predecessors()) {
759 if (pred->reachable() && !construct_blocks.count(pred)) {
760 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(pred->id()))
761 << "block <ID> " << pred->id() << " branches to the "
762 << construct_name << " construct, but not to the "
763 << header_name << " <ID> " << header->id();
764 }
765 }
766
767 if (block->is_type(BlockType::kBlockTypeSelection) ||
768 block->is_type(BlockType::kBlockTypeLoop)) {
769 size_t index = (block->terminator() - &_.ordered_instructions()[0]) - 1;
770 const auto& merge_inst = _.ordered_instructions()[index];
771 if (merge_inst.opcode() == SpvOpSelectionMerge ||
772 merge_inst.opcode() == SpvOpLoopMerge) {
773 uint32_t merge_id = merge_inst.GetOperandAs<uint32_t>(0);
774 auto merge_block = function->GetBlock(merge_id).first;
775 if (merge_block->reachable() &&
776 !construct_blocks.count(merge_block)) {
777 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
778 << "Header block " << _.getIdName(block->id())
779 << " is contained in the " << construct_name
780 << " construct headed by " << _.getIdName(header->id())
781 << ", but its merge block " << _.getIdName(merge_id)
782 << " is not";
783 }
784 }
785 }
786 }
787
788 // Checks rules for case constructs.
789 if (construct.type() == ConstructType::kSelection &&
790 header->terminator()->opcode() == SpvOpSwitch) {
791 const auto terminator = header->terminator();
792 if (auto error =
793 StructuredSwitchChecks(_, function, terminator, header, merge)) {
794 return error;
795 }
796 }
797 }
798
799 if (auto error = ValidateStructuredSelections(_, postorder)) {
800 return error;
801 }
802
803 return SPV_SUCCESS;
804}
805
806spv_result_t PerformWebGPUCfgChecks(ValidationState_t& _, Function* function) {
807 for (auto& block : function->ordered_blocks()) {
808 if (block->reachable()) continue;
809 if (block->is_type(kBlockTypeMerge)) {
810 // 1. Find the referencing merge and confirm that it is reachable.
811 BasicBlock* merge_header = function->GetMergeHeader(block);
812 assert(merge_header != nullptr);
813 if (!merge_header->reachable()) {
814 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
815 << "For WebGPU, unreachable merge-blocks must be referenced by "
816 "a reachable merge instruction.";
817 }
818
819 // 2. Check that the only instructions are OpLabel and OpUnreachable.
820 auto* label_inst = block->label();
821 auto* terminator_inst = block->terminator();
822 assert(label_inst != nullptr);
823 assert(terminator_inst != nullptr);
824
825 if (terminator_inst->opcode() != SpvOpUnreachable) {
826 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
827 << "For WebGPU, unreachable merge-blocks must terminate with "
828 "OpUnreachable.";
829 }
830
831 auto label_idx = label_inst - &_.ordered_instructions()[0];
832 auto terminator_idx = terminator_inst - &_.ordered_instructions()[0];
833 if (label_idx + 1 != terminator_idx) {
834 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
835 << "For WebGPU, unreachable merge-blocks must only contain an "
836 "OpLabel and OpUnreachable instruction.";
837 }
838
839 // 3. Use label instruction to confirm there is no uses by branches.
840 for (auto use : label_inst->uses()) {
841 const auto* use_inst = use.first;
842 if (spvOpcodeIsBranch(use_inst->opcode())) {
843 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
844 << "For WebGPU, unreachable merge-blocks cannot be the target "
845 "of a branch.";
846 }
847 }
848 } else if (block->is_type(kBlockTypeContinue)) {
849 // 1. Find referencing loop and confirm that it is reachable.
850 std::vector<BasicBlock*> continue_headers =
851 function->GetContinueHeaders(block);
852 if (continue_headers.empty()) {
853 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
854 << "For WebGPU, unreachable continue-target must be referenced "
855 "by a loop instruction.";
856 }
857
858 std::vector<BasicBlock*> reachable_headers(continue_headers.size());
859 auto iter =
860 std::copy_if(continue_headers.begin(), continue_headers.end(),
861 reachable_headers.begin(),
862 [](BasicBlock* header) { return header->reachable(); });
863 reachable_headers.resize(std::distance(reachable_headers.begin(), iter));
864
865 if (reachable_headers.empty()) {
866 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
867 << "For WebGPU, unreachable continue-target must be referenced "
868 "by a reachable loop instruction.";
869 }
870
871 // 2. Check that the only instructions are OpLabel and OpBranch.
872 auto* label_inst = block->label();
873 auto* terminator_inst = block->terminator();
874 assert(label_inst != nullptr);
875 assert(terminator_inst != nullptr);
876
877 if (terminator_inst->opcode() != SpvOpBranch) {
878 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
879 << "For WebGPU, unreachable continue-target must terminate with "
880 "OpBranch.";
881 }
882
883 auto label_idx = label_inst - &_.ordered_instructions()[0];
884 auto terminator_idx = terminator_inst - &_.ordered_instructions()[0];
885 if (label_idx + 1 != terminator_idx) {
886 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
887 << "For WebGPU, unreachable continue-target must only contain "
888 "an OpLabel and an OpBranch instruction.";
889 }
890
891 // 3. Use label instruction to confirm there is no uses by branches.
892 for (auto use : label_inst->uses()) {
893 const auto* use_inst = use.first;
894 if (spvOpcodeIsBranch(use_inst->opcode())) {
895 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
896 << "For WebGPU, unreachable continue-target cannot be the "
897 "target of a branch.";
898 }
899 }
900
901 // 4. Confirm that continue-target has a back edge to a reachable loop
902 // header block.
903 auto branch_target = terminator_inst->GetOperandAs<uint32_t>(0);
904 for (auto* continue_header : reachable_headers) {
905 if (branch_target != continue_header->id()) {
906 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
907 << "For WebGPU, unreachable continue-target must only have a "
908 "back edge to a single reachable loop instruction.";
909 }
910 }
911 } else {
912 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
913 << "For WebGPU, all blocks must be reachable, unless they are "
914 << "degenerate cases of merge-block or continue-target.";
915 }
916 }
917 return SPV_SUCCESS;
918}
919
920spv_result_t PerformCfgChecks(ValidationState_t& _) {
921 for (auto& function : _.functions()) {
922 // Check all referenced blocks are defined within a function
923 if (function.undefined_block_count() != 0) {
924 std::string undef_blocks("{");
925 bool first = true;
926 for (auto undefined_block : function.undefined_blocks()) {
927 undef_blocks += _.getIdName(undefined_block);
928 if (!first) {
929 undef_blocks += " ";
930 }
931 first = false;
932 }
933 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(function.id()))
934 << "Block(s) " << undef_blocks << "}"
935 << " are referenced but not defined in function "
936 << _.getIdName(function.id());
937 }
938
939 // Set each block's immediate dominator and immediate postdominator,
940 // and find all back-edges.
941 //
942 // We want to analyze all the blocks in the function, even in degenerate
943 // control flow cases including unreachable blocks. So use the augmented
944 // CFG to ensure we cover all the blocks.
945 std::vector<const BasicBlock*> postorder;
946 std::vector<const BasicBlock*> postdom_postorder;
947 std::vector<std::pair<uint32_t, uint32_t>> back_edges;
948 auto ignore_block = [](const BasicBlock*) {};
949 auto ignore_edge = [](const BasicBlock*, const BasicBlock*) {};
950 if (!function.ordered_blocks().empty()) {
951 /// calculate dominators
952 CFA<BasicBlock>::DepthFirstTraversal(
953 function.first_block(), function.AugmentedCFGSuccessorsFunction(),
954 ignore_block, [&](const BasicBlock* b) { postorder.push_back(b); },
955 ignore_edge);
956 auto edges = CFA<BasicBlock>::CalculateDominators(
957 postorder, function.AugmentedCFGPredecessorsFunction());
958 for (auto edge : edges) {
959 if (edge.first != edge.second)
960 edge.first->SetImmediateDominator(edge.second);
961 }
962
963 /// calculate post dominators
964 CFA<BasicBlock>::DepthFirstTraversal(
965 function.pseudo_exit_block(),
966 function.AugmentedCFGPredecessorsFunction(), ignore_block,
967 [&](const BasicBlock* b) { postdom_postorder.push_back(b); },
968 ignore_edge);
969 auto postdom_edges = CFA<BasicBlock>::CalculateDominators(
970 postdom_postorder, function.AugmentedCFGSuccessorsFunction());
971 for (auto edge : postdom_edges) {
972 edge.first->SetImmediatePostDominator(edge.second);
973 }
974 /// calculate back edges.
975 CFA<BasicBlock>::DepthFirstTraversal(
976 function.pseudo_entry_block(),
977 function
978 .AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge(),
979 ignore_block, ignore_block,
980 [&](const BasicBlock* from, const BasicBlock* to) {
981 back_edges.emplace_back(from->id(), to->id());
982 });
983 }
984 UpdateContinueConstructExitBlocks(function, back_edges);
985
986 auto& blocks = function.ordered_blocks();
987 if (!blocks.empty()) {
988 // Check if the order of blocks in the binary appear before the blocks
989 // they dominate
990 for (auto block = begin(blocks) + 1; block != end(blocks); ++block) {
991 if (auto idom = (*block)->immediate_dominator()) {
992 if (idom != function.pseudo_entry_block() &&
993 block == std::find(begin(blocks), block, idom)) {
994 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(idom->id()))
995 << "Block " << _.getIdName((*block)->id())
996 << " appears in the binary before its dominator "
997 << _.getIdName(idom->id());
998 }
999 }
1000
1001 // For WebGPU check that all unreachable blocks are degenerate cases for
1002 // merge-block or continue-target.
1003 if (spvIsWebGPUEnv(_.context()->target_env)) {
1004 spv_result_t result = PerformWebGPUCfgChecks(_, &function);
1005 if (result != SPV_SUCCESS) return result;
1006 }
1007 }
1008 // If we have structed control flow, check that no block has a control
1009 // flow nesting depth larger than the limit.
1010 if (_.HasCapability(SpvCapabilityShader)) {
1011 const int control_flow_nesting_depth_limit =
1012 _.options()->universal_limits_.max_control_flow_nesting_depth;
1013 for (auto block = begin(blocks); block != end(blocks); ++block) {
1014 if (function.GetBlockDepth(*block) >
1015 control_flow_nesting_depth_limit) {
1016 return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef((*block)->id()))
1017 << "Maximum Control Flow nesting depth exceeded.";
1018 }
1019 }
1020 }
1021 }
1022
1023 /// Structured control flow checks are only required for shader capabilities
1024 if (_.HasCapability(SpvCapabilityShader)) {
1025 if (auto error =
1026 StructuredControlFlowChecks(_, &function, back_edges, postorder))
1027 return error;
1028 }
1029 }
1030 return SPV_SUCCESS;
1031}
1032
1033spv_result_t CfgPass(ValidationState_t& _, const Instruction* inst) {
1034 SpvOp opcode = inst->opcode();
1035 switch (opcode) {
1036 case SpvOpLabel:
1037 if (auto error = _.current_function().RegisterBlock(inst->id()))
1038 return error;
1039
1040 // TODO(github:1661) This should be done in the
1041 // ValidationState::RegisterInstruction method but because of the order of
1042 // passes the OpLabel ends up not being part of the basic block it starts.
1043 _.current_function().current_block()->set_label(inst);
1044 break;
1045 case SpvOpLoopMerge: {
1046 uint32_t merge_block = inst->GetOperandAs<uint32_t>(0);
1047 uint32_t continue_block = inst->GetOperandAs<uint32_t>(1);
1048 CFG_ASSERT(MergeBlockAssert, merge_block);
1049
1050 if (auto error = _.current_function().RegisterLoopMerge(merge_block,
1051 continue_block))
1052 return error;
1053 } break;
1054 case SpvOpSelectionMerge: {
1055 uint32_t merge_block = inst->GetOperandAs<uint32_t>(0);
1056 CFG_ASSERT(MergeBlockAssert, merge_block);
1057
1058 if (auto error = _.current_function().RegisterSelectionMerge(merge_block))
1059 return error;
1060 } break;
1061 case SpvOpBranch: {
1062 uint32_t target = inst->GetOperandAs<uint32_t>(0);
1063 CFG_ASSERT(FirstBlockAssert, target);
1064
1065 _.current_function().RegisterBlockEnd({target}, opcode);
1066 } break;
1067 case SpvOpBranchConditional: {
1068 uint32_t tlabel = inst->GetOperandAs<uint32_t>(1);
1069 uint32_t flabel = inst->GetOperandAs<uint32_t>(2);
1070 CFG_ASSERT(FirstBlockAssert, tlabel);
1071 CFG_ASSERT(FirstBlockAssert, flabel);
1072
1073 _.current_function().RegisterBlockEnd({tlabel, flabel}, opcode);
1074 } break;
1075
1076 case SpvOpSwitch: {
1077 std::vector<uint32_t> cases;
1078 for (size_t i = 1; i < inst->operands().size(); i += 2) {
1079 uint32_t target = inst->GetOperandAs<uint32_t>(i);
1080 CFG_ASSERT(FirstBlockAssert, target);
1081 cases.push_back(target);
1082 }
1083 _.current_function().RegisterBlockEnd({cases}, opcode);
1084 } break;
1085 case SpvOpReturn: {
1086 const uint32_t return_type = _.current_function().GetResultTypeId();
1087 const Instruction* return_type_inst = _.FindDef(return_type);
1088 assert(return_type_inst);
1089 if (return_type_inst->opcode() != SpvOpTypeVoid)
1090 return _.diag(SPV_ERROR_INVALID_CFG, inst)
1091 << "OpReturn can only be called from a function with void "
1092 << "return type.";
1093 }
1094 // Fallthrough.
1095 case SpvOpKill:
1096 case SpvOpReturnValue:
1097 case SpvOpUnreachable:
1098 _.current_function().RegisterBlockEnd(std::vector<uint32_t>(), opcode);
1099 if (opcode == SpvOpKill) {
1100 _.current_function().RegisterExecutionModelLimitation(
1101 SpvExecutionModelFragment,
1102 "OpKill requires Fragment execution model");
1103 }
1104 break;
1105 default:
1106 break;
1107 }
1108 return SPV_SUCCESS;
1109}
1110
1111spv_result_t ControlFlowPass(ValidationState_t& _, const Instruction* inst) {
1112 switch (inst->opcode()) {
1113 case SpvOpPhi:
1114 if (auto error = ValidatePhi(_, inst)) return error;
1115 break;
1116 case SpvOpBranch:
1117 if (auto error = ValidateBranch(_, inst)) return error;
1118 break;
1119 case SpvOpBranchConditional:
1120 if (auto error = ValidateBranchConditional(_, inst)) return error;
1121 break;
1122 case SpvOpReturnValue:
1123 if (auto error = ValidateReturnValue(_, inst)) return error;
1124 break;
1125 case SpvOpSwitch:
1126 if (auto error = ValidateSwitch(_, inst)) return error;
1127 break;
1128 case SpvOpLoopMerge:
1129 if (auto error = ValidateLoopMerge(_, inst)) return error;
1130 break;
1131 default:
1132 break;
1133 }
1134
1135 return SPV_SUCCESS;
1136}
1137
1138} // namespace val
1139} // namespace spvtools
1140