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