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