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// Validation tests for Control Flow Graph
16
17#include <array>
18#include <functional>
19#include <sstream>
20#include <string>
21#include <utility>
22#include <vector>
23
24#include "gmock/gmock.h"
25#include "source/spirv_target_env.h"
26#include "source/val/validate.h"
27#include "test/test_fixture.h"
28#include "test/unit_spirv.h"
29#include "test/val/val_fixtures.h"
30
31namespace spvtools {
32namespace val {
33namespace {
34
35using ::testing::HasSubstr;
36using ::testing::MatchesRegex;
37
38using ValidateCFG = spvtest::ValidateBase<spv::Capability>;
39using spvtest::ScopedContext;
40
41std::string nameOps() { return ""; }
42
43template <typename... Args>
44std::string nameOps(std::pair<std::string, std::string> head, Args... names) {
45  return "OpName %" + head.first + " \"" + head.second + "\"\n" +
46         nameOps(names...);
47}
48
49template <typename... Args>
50std::string nameOps(std::string head, Args... names) {
51  return "OpName %" + head + " \"" + head + "\"\n" + nameOps(names...);
52}
53
54/// This class allows the easy creation of complex control flow without writing
55/// SPIR-V. This class is used in the test cases below.
56class Block {
57  std::string label_;
58  std::string body_;
59  spv::Op type_;
60  std::vector<Block> successors_;
61
62 public:
63  /// Creates a Block with a given label
64  ///
65  /// @param[in]: label the label id of the block
66  /// @param[in]: type the branch instruction that ends the block
67  explicit Block(std::string label, spv::Op type = spv::Op::OpBranch)
68      : label_(label), body_(), type_(type), successors_() {}
69
70  /// Sets the instructions which will appear in the body of the block
71  Block& SetBody(std::string body) {
72    body_ = body;
73    return *this;
74  }
75
76  Block& AppendBody(std::string body) {
77    body_ += body;
78    return *this;
79  }
80
81  /// Converts the block into a SPIR-V string
82  operator std::string() {
83    std::stringstream out;
84    out << std::setw(8) << "%" + label_ + "  = OpLabel \n";
85    if (!body_.empty()) {
86      out << body_;
87    }
88
89    switch (type_) {
90      case spv::Op::OpBranchConditional:
91        out << "OpBranchConditional %cond ";
92        for (Block& b : successors_) {
93          out << "%" + b.label_ + " ";
94        }
95        break;
96      case spv::Op::OpSwitch: {
97        out << "OpSwitch %one %" + successors_.front().label_;
98        std::stringstream ss;
99        for (size_t i = 1; i < successors_.size(); i++) {
100          ss << " " << i << " %" << successors_[i].label_;
101        }
102        out << ss.str();
103      } break;
104      case spv::Op::OpLoopMerge: {
105        assert(successors_.size() == 2);
106        out << "OpLoopMerge %" + successors_[0].label_ + " %" +
107                   successors_[0].label_ + "None";
108      } break;
109
110      case spv::Op::OpReturn:
111        assert(successors_.size() == 0);
112        out << "OpReturn\n";
113        break;
114      case spv::Op::OpUnreachable:
115        assert(successors_.size() == 0);
116        out << "OpUnreachable\n";
117        break;
118      case spv::Op::OpBranch:
119        assert(successors_.size() == 1);
120        out << "OpBranch %" + successors_.front().label_;
121        break;
122      case spv::Op::OpKill:
123        assert(successors_.size() == 0);
124        out << "OpKill\n";
125        break;
126      default:
127        assert(1 == 0 && "Unhandled");
128    }
129    out << "\n";
130
131    return out.str();
132  }
133  friend Block& operator>>(Block& curr, std::vector<Block> successors);
134  friend Block& operator>>(Block& lhs, Block& successor);
135};
136
137/// Assigns the successors for the Block on the lhs
138Block& operator>>(Block& lhs, std::vector<Block> successors) {
139  if (lhs.type_ == spv::Op::OpBranchConditional) {
140    assert(successors.size() == 2);
141  } else if (lhs.type_ == spv::Op::OpSwitch) {
142    assert(successors.size() > 1);
143  }
144  lhs.successors_ = successors;
145  return lhs;
146}
147
148/// Assigns the successor for the Block on the lhs
149Block& operator>>(Block& lhs, Block& successor) {
150  assert(lhs.type_ == spv::Op::OpBranch);
151  lhs.successors_.push_back(successor);
152  return lhs;
153}
154
155const std::string& GetDefaultHeader(spv::Capability cap) {
156  static const std::string shader_header =
157      "OpCapability Shader\n"
158      "OpCapability Linkage\n"
159      "OpMemoryModel Logical GLSL450\n";
160
161  static const std::string kernel_header =
162      "OpCapability Kernel\n"
163      "OpCapability Linkage\n"
164      "OpMemoryModel Logical OpenCL\n";
165
166  return (cap == spv::Capability::Shader) ? shader_header : kernel_header;
167}
168
169const std::string& types_consts() {
170  static const std::string types =
171      "%voidt   = OpTypeVoid\n"
172      "%boolt   = OpTypeBool\n"
173      "%intt    = OpTypeInt 32 0\n"
174      "%one     = OpConstant %intt 1\n"
175      "%two     = OpConstant %intt 2\n"
176      "%ptrt    = OpTypePointer Function %intt\n"
177      "%funct   = OpTypeFunction %voidt\n";
178  return types;
179}
180
181INSTANTIATE_TEST_SUITE_P(StructuredControlFlow, ValidateCFG,
182                         ::testing::Values(spv::Capability::Shader,
183                                           spv::Capability::Kernel));
184
185TEST_P(ValidateCFG, LoopReachableFromEntryButNeverLeadingToReturn) {
186  // In this case, the loop is reachable from a node without a predecessor,
187  // but never reaches a node with a return.
188  //
189  // This motivates the need for the pseudo-exit node to have a node
190  // from a cycle in its predecessors list.  Otherwise the validator's
191  // post-dominance calculation will go into an infinite loop.
192  //
193  // For more motivation, see
194  // https://github.com/KhronosGroup/SPIRV-Tools/issues/279
195  std::string str = R"(
196           OpCapability Shader
197           OpCapability Linkage
198           OpMemoryModel Logical GLSL450
199
200           OpName %entry "entry"
201           OpName %loop "loop"
202           OpName %exit "exit"
203
204%voidt   = OpTypeVoid
205%funct   = OpTypeFunction %voidt
206
207%main    = OpFunction %voidt None %funct
208%entry   = OpLabel
209           OpBranch %loop
210%loop    = OpLabel
211           OpLoopMerge %exit %loop None
212           OpBranch %loop
213%exit    = OpLabel
214           OpReturn
215           OpFunctionEnd
216  )";
217  CompileSuccessfully(str);
218  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()) << str;
219}
220
221TEST_P(ValidateCFG, LoopUnreachableFromEntryButLeadingToReturn) {
222  // In this case, the loop is not reachable from a node without a
223  // predecessor, but eventually reaches a node with a return.
224  //
225  // This motivates the need for the pseudo-entry node to have a node
226  // from a cycle in its successors list.  Otherwise the validator's
227  // dominance calculation will go into an infinite loop.
228  //
229  // For more motivation, see
230  // https://github.com/KhronosGroup/SPIRV-Tools/issues/279
231  // Before that fix, we'd have an infinite loop when calculating
232  // post-dominators.
233  std::string str = R"(
234           OpCapability Shader
235           OpCapability Linkage
236           OpMemoryModel Logical GLSL450
237
238           OpName %entry "entry"
239           OpName %loop "loop"
240           OpName %cont "cont"
241           OpName %exit "exit"
242
243%voidt   = OpTypeVoid
244%funct   = OpTypeFunction %voidt
245%boolt   = OpTypeBool
246%false   = OpConstantFalse %boolt
247
248%main    = OpFunction %voidt None %funct
249%entry   = OpLabel
250           OpReturn
251
252%loop    = OpLabel
253           OpLoopMerge %exit %cont None
254           OpBranch %cont
255
256%cont    = OpLabel
257           OpBranchConditional %false %loop %exit
258
259%exit    = OpLabel
260           OpReturn
261           OpFunctionEnd
262  )";
263  CompileSuccessfully(str);
264  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions())
265      << str << getDiagnosticString();
266}
267
268TEST_P(ValidateCFG, Simple) {
269  bool is_shader = GetParam() == spv::Capability::Shader;
270  Block entry("entry");
271  Block loop("loop", spv::Op::OpBranchConditional);
272  Block cont("cont");
273  Block merge("merge", spv::Op::OpReturn);
274
275  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
276  if (is_shader) {
277    loop.SetBody("OpLoopMerge %merge %cont None\n");
278  }
279
280  std::string str = GetDefaultHeader(GetParam()) +
281                    nameOps("loop", "entry", "cont", "merge",
282                            std::make_pair("func", "Main")) +
283                    types_consts() +
284                    "%func    = OpFunction %voidt None %funct\n";
285
286  str += entry >> loop;
287  str += loop >> std::vector<Block>({cont, merge});
288  str += cont >> loop;
289  str += merge;
290  str += "OpFunctionEnd\n";
291
292  CompileSuccessfully(str);
293  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
294}
295
296TEST_P(ValidateCFG, Variable) {
297  Block entry("entry");
298  Block cont("cont");
299  Block exit("exit", spv::Op::OpReturn);
300
301  entry.SetBody("%var = OpVariable %ptrt Function\n");
302
303  std::string str = GetDefaultHeader(GetParam()) +
304                    nameOps(std::make_pair("func", "Main")) + types_consts() +
305                    " %func    = OpFunction %voidt None %funct\n";
306  str += entry >> cont;
307  str += cont >> exit;
308  str += exit;
309  str += "OpFunctionEnd\n";
310
311  CompileSuccessfully(str);
312  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
313}
314
315TEST_P(ValidateCFG, VariableNotInFirstBlockBad) {
316  Block entry("entry");
317  Block cont("cont");
318  Block exit("exit", spv::Op::OpReturn);
319
320  // This operation should only be performed in the entry block
321  cont.SetBody("%var = OpVariable %ptrt Function\n");
322
323  std::string str = GetDefaultHeader(GetParam()) +
324                    nameOps(std::make_pair("func", "Main")) + types_consts() +
325                    " %func    = OpFunction %voidt None %funct\n";
326
327  str += entry >> cont;
328  str += cont >> exit;
329  str += exit;
330  str += "OpFunctionEnd\n";
331
332  CompileSuccessfully(str);
333  ASSERT_EQ(SPV_ERROR_INVALID_DATA, ValidateInstructions());
334  EXPECT_THAT(getDiagnosticString(),
335              HasSubstr("All OpVariable instructions in a function must be the "
336                        "first instructions in the first block"));
337}
338
339TEST_P(ValidateCFG, BlockSelfLoopIsOk) {
340  bool is_shader = GetParam() == spv::Capability::Shader;
341  Block entry("entry");
342  Block loop("loop", spv::Op::OpBranchConditional);
343  Block merge("merge", spv::Op::OpReturn);
344
345  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
346  if (is_shader) loop.SetBody("OpLoopMerge %merge %loop None\n");
347
348  std::string str = GetDefaultHeader(GetParam()) +
349                    nameOps("loop", "merge", std::make_pair("func", "Main")) +
350                    types_consts() +
351                    "%func    = OpFunction %voidt None %funct\n";
352
353  str += entry >> loop;
354  // loop branches to itself, but does not trigger an error.
355  str += loop >> std::vector<Block>({merge, loop});
356  str += merge;
357  str += "OpFunctionEnd\n";
358
359  CompileSuccessfully(str);
360  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()) << getDiagnosticString();
361}
362
363TEST_P(ValidateCFG, BlockAppearsBeforeDominatorBad) {
364  bool is_shader = GetParam() == spv::Capability::Shader;
365  Block entry("entry");
366  Block cont("cont");
367  Block branch("branch", spv::Op::OpBranchConditional);
368  Block merge("merge", spv::Op::OpReturn);
369
370  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
371  if (is_shader) branch.SetBody("OpSelectionMerge %merge None\n");
372
373  std::string str = GetDefaultHeader(GetParam()) +
374                    nameOps("cont", "branch", std::make_pair("func", "Main")) +
375                    types_consts() +
376                    "%func    = OpFunction %voidt None %funct\n";
377
378  str += entry >> branch;
379  str += cont >> merge;  // cont appears before its dominator
380  str += branch >> std::vector<Block>({cont, merge});
381  str += merge;
382  str += "OpFunctionEnd\n";
383
384  CompileSuccessfully(str);
385  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
386  EXPECT_THAT(getDiagnosticString(),
387              MatchesRegex("Block '.\\[%cont\\]' appears in the binary "
388                           "before its dominator '.\\[%branch\\]'\n"
389                           "  %branch = OpLabel\n"));
390}
391
392TEST_P(ValidateCFG, MergeBlockTargetedByMultipleHeaderBlocksBad) {
393  bool is_shader = GetParam() == spv::Capability::Shader;
394  Block entry("entry");
395  Block loop("loop");
396  Block selection("selection", spv::Op::OpBranchConditional);
397  Block merge("merge", spv::Op::OpReturn);
398
399  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
400  if (is_shader) loop.SetBody(" OpLoopMerge %merge %loop None\n");
401
402  // cannot share the same merge
403  if (is_shader) selection.SetBody("OpSelectionMerge %merge None\n");
404
405  std::string str = GetDefaultHeader(GetParam()) +
406                    nameOps("merge", std::make_pair("func", "Main")) +
407                    types_consts() +
408                    "%func    = OpFunction %voidt None %funct\n";
409
410  str += entry >> loop;
411  str += loop >> selection;
412  str += selection >> std::vector<Block>({loop, merge});
413  str += merge;
414  str += "OpFunctionEnd\n";
415
416  CompileSuccessfully(str);
417  if (is_shader) {
418    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
419    EXPECT_THAT(getDiagnosticString(),
420                MatchesRegex("Block '.\\[%merge\\]' is already a merge block "
421                             "for another header\n"
422                             "  %Main = OpFunction %void None %9\n"));
423  } else {
424    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
425  }
426}
427
428TEST_P(ValidateCFG, MergeBlockTargetedByMultipleHeaderBlocksSelectionBad) {
429  bool is_shader = GetParam() == spv::Capability::Shader;
430  Block entry("entry");
431  Block loop("loop", spv::Op::OpBranchConditional);
432  Block selection("selection", spv::Op::OpBranchConditional);
433  Block merge("merge", spv::Op::OpReturn);
434
435  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
436  if (is_shader) selection.SetBody(" OpSelectionMerge %merge None\n");
437
438  // cannot share the same merge
439  if (is_shader) loop.SetBody(" OpLoopMerge %merge %loop None\n");
440
441  std::string str = GetDefaultHeader(GetParam()) +
442                    nameOps("merge", std::make_pair("func", "Main")) +
443                    types_consts() +
444                    "%func    = OpFunction %voidt None %funct\n";
445
446  str += entry >> selection;
447  str += selection >> std::vector<Block>({merge, loop});
448  str += loop >> std::vector<Block>({loop, merge});
449  str += merge;
450  str += "OpFunctionEnd\n";
451
452  CompileSuccessfully(str);
453  if (is_shader) {
454    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
455    EXPECT_THAT(getDiagnosticString(),
456                MatchesRegex("Block '.\\[%merge\\]' is already a merge block "
457                             "for another header\n"
458                             "  %Main = OpFunction %void None %9\n"));
459  } else {
460    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
461  }
462}
463
464TEST_P(ValidateCFG, BranchTargetFirstBlockBadSinceEntryBlock) {
465  Block entry("entry");
466  Block bad("bad");
467  Block end("end", spv::Op::OpReturn);
468  std::string str = GetDefaultHeader(GetParam()) +
469                    nameOps("entry", "bad", std::make_pair("func", "Main")) +
470                    types_consts() +
471                    "%func    = OpFunction %voidt None %funct\n";
472
473  str += entry >> bad;
474  str += bad >> entry;  // Cannot target entry block
475  str += end;
476  str += "OpFunctionEnd\n";
477
478  CompileSuccessfully(str);
479  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
480  EXPECT_THAT(getDiagnosticString(),
481              MatchesRegex("First block '.\\[%entry\\]' of function "
482                           "'.\\[%Main\\]' is targeted by block '.\\[%bad\\]'\n"
483                           "  %Main = OpFunction %void None %10\n"));
484}
485
486TEST_P(ValidateCFG, BranchTargetFirstBlockBadSinceValue) {
487  Block entry("entry");
488  entry.SetBody("%undef = OpUndef %boolt\n");
489  Block bad("bad");
490  Block end("end", spv::Op::OpReturn);
491  Block badvalue("undef");  // This references the OpUndef.
492  std::string str = GetDefaultHeader(GetParam()) +
493                    nameOps("entry", "bad", std::make_pair("func", "Main")) +
494                    types_consts() +
495                    "%func    = OpFunction %voidt None %funct\n";
496
497  str += entry >> bad;
498  str +=
499      bad >> badvalue;  // Check branch to a function value (it's not a block!)
500  str += end;
501  str += "OpFunctionEnd\n";
502
503  CompileSuccessfully(str);
504  ASSERT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
505  EXPECT_THAT(getDiagnosticString(),
506              HasSubstr("'Target Label' operands for OpBranch must "
507                        "be the ID of an OpLabel instruction"));
508}
509
510TEST_P(ValidateCFG, BranchConditionalTrueTargetFirstBlockBad) {
511  Block entry("entry");
512  Block bad("bad", spv::Op::OpBranchConditional);
513  Block exit("exit", spv::Op::OpReturn);
514
515  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
516  bad.SetBody(" OpLoopMerge %entry %exit None\n");
517
518  std::string str = GetDefaultHeader(GetParam()) +
519                    nameOps("entry", "bad", std::make_pair("func", "Main")) +
520                    types_consts() +
521                    "%func    = OpFunction %voidt None %funct\n";
522
523  str += entry >> bad;
524  str += bad >> std::vector<Block>({entry, exit});  // cannot target entry block
525  str += exit;
526  str += "OpFunctionEnd\n";
527
528  CompileSuccessfully(str);
529  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
530  EXPECT_THAT(
531      getDiagnosticString(),
532      MatchesRegex("First block '.\\[%entry\\]' of function '.\\[%Main\\]' "
533                   "is targeted by block '.\\[%bad\\]'\n"
534                   "  %Main = OpFunction %void None %10\n"));
535}
536
537TEST_P(ValidateCFG, BranchConditionalFalseTargetFirstBlockBad) {
538  Block entry("entry");
539  Block bad("bad", spv::Op::OpBranchConditional);
540  Block t("t");
541  Block merge("merge");
542  Block end("end", spv::Op::OpReturn);
543
544  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
545  bad.SetBody("OpLoopMerge %merge %cont None\n");
546
547  std::string str = GetDefaultHeader(GetParam()) +
548                    nameOps("entry", "bad", std::make_pair("func", "Main")) +
549                    types_consts() +
550                    "%func    = OpFunction %voidt None %funct\n";
551
552  str += entry >> bad;
553  str += bad >> std::vector<Block>({t, entry});
554  str += merge >> end;
555  str += end;
556  str += "OpFunctionEnd\n";
557
558  CompileSuccessfully(str);
559  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
560  EXPECT_THAT(
561      getDiagnosticString(),
562      MatchesRegex("First block '.\\[%entry\\]' of function '.\\[%Main\\]' "
563                   "is targeted by block '.\\[%bad\\]'\n"
564                   "  %Main = OpFunction %void None %10\n"));
565}
566
567TEST_P(ValidateCFG, SwitchTargetFirstBlockBad) {
568  Block entry("entry");
569  Block bad("bad", spv::Op::OpSwitch);
570  Block block1("block1");
571  Block block2("block2");
572  Block block3("block3");
573  Block def("def");  // default block
574  Block merge("merge");
575  Block end("end", spv::Op::OpReturn);
576
577  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
578  bad.SetBody("OpSelectionMerge %merge None\n");
579
580  std::string str = GetDefaultHeader(GetParam()) +
581                    nameOps("entry", "bad", std::make_pair("func", "Main")) +
582                    types_consts() +
583                    "%func    = OpFunction %voidt None %funct\n";
584
585  str += entry >> bad;
586  str += bad >> std::vector<Block>({def, block1, block2, block3, entry});
587  str += def >> merge;
588  str += block1 >> merge;
589  str += block2 >> merge;
590  str += block3 >> merge;
591  str += merge >> end;
592  str += end;
593  str += "OpFunctionEnd\n";
594
595  CompileSuccessfully(str);
596  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
597  EXPECT_THAT(
598      getDiagnosticString(),
599      MatchesRegex("First block '.\\[%entry\\]' of function '.\\[%Main\\]' "
600                   "is targeted by block '.\\[%bad\\]'\n"
601                   "  %Main = OpFunction %void None %10\n"));
602}
603
604TEST_P(ValidateCFG, BranchToBlockInOtherFunctionBad) {
605  Block entry("entry");
606  Block middle("middle", spv::Op::OpBranchConditional);
607  Block end("end", spv::Op::OpReturn);
608
609  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
610  middle.SetBody("OpSelectionMerge %end None\n");
611
612  Block entry2("entry2");
613  Block middle2("middle2");
614  Block end2("end2", spv::Op::OpReturn);
615
616  std::string str = GetDefaultHeader(GetParam()) +
617                    nameOps("middle2", std::make_pair("func", "Main")) +
618                    types_consts() +
619                    "%func    = OpFunction %voidt None %funct\n";
620
621  str += entry >> middle;
622  str += middle >> std::vector<Block>({end, middle2});
623  str += end;
624  str += "OpFunctionEnd\n";
625
626  str += "%func2    = OpFunction %voidt None %funct\n";
627  str += entry2 >> middle2;
628  str += middle2 >> end2;
629  str += end2;
630  str += "OpFunctionEnd\n";
631
632  CompileSuccessfully(str);
633  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
634  EXPECT_THAT(getDiagnosticString(),
635              MatchesRegex(
636                  "Block\\(s\\) \\{'.\\[%middle2\\]'\\} are referenced but not "
637                  "defined in function '.\\[%Main\\]'\n"
638                  "  %Main = OpFunction %void None %9\n"));
639}
640
641TEST_P(ValidateCFG, HeaderDoesntStrictlyDominateMergeBad) {
642  // If a merge block is reachable, then it must be strictly dominated by
643  // its header block.
644  bool is_shader = GetParam() == spv::Capability::Shader;
645  Block head("head", spv::Op::OpBranchConditional);
646  Block exit("exit", spv::Op::OpReturn);
647
648  head.SetBody("%cond = OpSLessThan %boolt %one %two\n");
649
650  if (is_shader) head.AppendBody("OpSelectionMerge %head None\n");
651
652  std::string str = GetDefaultHeader(GetParam()) +
653                    nameOps("head", "exit", std::make_pair("func", "Main")) +
654                    types_consts() +
655                    "%func    = OpFunction %voidt None %funct\n";
656
657  str += head >> std::vector<Block>({exit, exit});
658  str += exit;
659  str += "OpFunctionEnd\n";
660
661  CompileSuccessfully(str);
662  if (is_shader) {
663    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
664    EXPECT_THAT(
665        getDiagnosticString(),
666        MatchesRegex(
667            "The selection construct with the selection header "
668            "'.\\[%head\\]' does not strictly structurally dominate the "
669            "merge block "
670            "'.\\[%head\\]'\n  %head = OpLabel\n"));
671  } else {
672    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()) << str;
673  }
674}
675
676std::string GetUnreachableMergeNoMergeInst(spv::Capability cap) {
677  std::string header = GetDefaultHeader(cap);
678  Block entry("entry");
679  Block branch("branch", spv::Op::OpBranchConditional);
680  Block t("t", spv::Op::OpReturn);
681  Block f("f", spv::Op::OpReturn);
682  Block merge("merge", spv::Op::OpReturn);
683
684  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
685  if (cap == spv::Capability::Shader)
686    branch.AppendBody("OpSelectionMerge %merge None\n");
687
688  std::string str = header;
689  str += nameOps("branch", "merge", std::make_pair("func", "Main"));
690  str += types_consts() + "%func    = OpFunction %voidt None %funct\n";
691  str += entry >> branch;
692  str += branch >> std::vector<Block>({t, f});
693  str += t;
694  str += f;
695  str += merge;
696  str += "OpFunctionEnd\n";
697
698  return str;
699}
700
701TEST_P(ValidateCFG, UnreachableMergeNoMergeInst) {
702  CompileSuccessfully(GetUnreachableMergeNoMergeInst(GetParam()));
703  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
704}
705
706std::string GetUnreachableMergeTerminatedBy(spv::Capability cap, spv::Op op) {
707  std::string header = GetDefaultHeader(cap);
708
709  Block entry("entry");
710  Block branch("branch", spv::Op::OpBranchConditional);
711  Block t("t", spv::Op::OpReturn);
712  Block f("f", spv::Op::OpReturn);
713  Block merge("merge", op);
714
715  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
716  std::string str = header;
717  if (cap == spv::Capability::Shader)
718    branch.AppendBody("OpSelectionMerge %merge None\n");
719
720  str += nameOps("branch", "merge", std::make_pair("func", "Main"));
721  str += types_consts();
722  str += "%func    = OpFunction %voidt None %funct\n";
723  str += entry >> branch;
724  str += branch >> std::vector<Block>({t, f});
725  str += t;
726  str += f;
727  str += merge;
728  str += "OpFunctionEnd\n";
729
730  return str;
731}
732
733TEST_P(ValidateCFG, UnreachableMergeTerminatedByOpUnreachable) {
734  CompileSuccessfully(
735      GetUnreachableMergeTerminatedBy(GetParam(), spv::Op::OpUnreachable));
736  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
737}
738
739TEST_F(ValidateCFG, UnreachableMergeTerminatedByOpKill) {
740  CompileSuccessfully(GetUnreachableMergeTerminatedBy(spv::Capability::Shader,
741                                                      spv::Op::OpKill));
742  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
743}
744
745TEST_P(ValidateCFG, UnreachableMergeTerminatedByOpReturn) {
746  CompileSuccessfully(
747      GetUnreachableMergeTerminatedBy(GetParam(), spv::Op::OpReturn));
748  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
749}
750
751std::string GetUnreachableContinueTerminatedBy(spv::Capability cap,
752                                               spv::Op op) {
753  std::string header = GetDefaultHeader(cap);
754
755  Block entry("entry");
756  Block branch("branch", spv::Op::OpBranch);
757  Block merge("merge", spv::Op::OpReturn);
758  Block target("target", op);
759
760  if (op == spv::Op::OpBranch) target >> branch;
761
762  std::string str = header;
763  if (cap == spv::Capability::Shader)
764    branch.AppendBody("OpLoopMerge %merge %target None\n");
765
766  str += nameOps("branch", "merge", "target", std::make_pair("func", "Main"));
767  str += types_consts();
768  str += "%func    = OpFunction %voidt None %funct\n";
769  str += entry >> branch;
770  str += branch >> std::vector<Block>({merge});
771  str += merge;
772  str += target;
773  str += "OpFunctionEnd\n";
774
775  return str;
776}
777
778TEST_P(ValidateCFG, UnreachableContinueTerminatedByOpUnreachable) {
779  CompileSuccessfully(
780      GetUnreachableContinueTerminatedBy(GetParam(), spv::Op::OpUnreachable));
781  if (GetParam() == spv::Capability::Shader) {
782    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
783    EXPECT_THAT(getDiagnosticString(),
784                HasSubstr("targeted by 0 back-edge blocks"));
785  } else {
786    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
787  }
788}
789
790TEST_F(ValidateCFG, UnreachableContinueTerminatedByOpKill) {
791  CompileSuccessfully(GetUnreachableContinueTerminatedBy(
792      spv::Capability::Shader, spv::Op::OpKill));
793  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
794  EXPECT_THAT(getDiagnosticString(),
795              HasSubstr("targeted by 0 back-edge blocks"));
796}
797
798TEST_P(ValidateCFG, UnreachableContinueTerminatedByOpReturn) {
799  CompileSuccessfully(
800      GetUnreachableContinueTerminatedBy(GetParam(), spv::Op::OpReturn));
801  if (GetParam() == spv::Capability::Shader) {
802    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
803    EXPECT_THAT(getDiagnosticString(),
804                HasSubstr("targeted by 0 back-edge blocks"));
805  } else {
806    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
807  }
808}
809
810TEST_P(ValidateCFG, UnreachableContinueTerminatedByOpBranch) {
811  CompileSuccessfully(
812      GetUnreachableContinueTerminatedBy(GetParam(), spv::Op::OpBranch));
813  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
814}
815
816std::string GetUnreachableMergeUnreachableMergeInst(spv::Capability cap) {
817  std::string header = GetDefaultHeader(cap);
818
819  Block body("body", spv::Op::OpReturn);
820  Block entry("entry");
821  Block branch("branch", spv::Op::OpBranchConditional);
822  Block t("t", spv::Op::OpReturn);
823  Block f("f", spv::Op::OpReturn);
824  Block merge("merge", spv::Op::OpUnreachable);
825
826  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
827  std::string str = header;
828  if (cap == spv::Capability::Shader)
829    branch.AppendBody("OpSelectionMerge %merge None\n");
830
831  str += nameOps("branch", "merge", std::make_pair("func", "Main"));
832  str += types_consts();
833  str += "%func    = OpFunction %voidt None %funct\n";
834  str += body;
835  str += merge;
836  str += entry >> branch;
837  str += branch >> std::vector<Block>({t, f});
838  str += t;
839  str += f;
840  str += "OpFunctionEnd\n";
841
842  return str;
843}
844
845TEST_P(ValidateCFG, UnreachableMergeUnreachableMergeInst) {
846  CompileSuccessfully(GetUnreachableMergeUnreachableMergeInst(GetParam()));
847  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
848}
849
850std::string GetUnreachableContinueUnreachableLoopInst(spv::Capability cap) {
851  std::string header = GetDefaultHeader(cap);
852
853  Block body("body", spv::Op::OpReturn);
854  Block entry("entry");
855  Block branch("branch", spv::Op::OpBranch);
856  Block merge("merge", spv::Op::OpReturn);
857  Block target("target", spv::Op::OpBranch);
858
859  target >> branch;
860
861  std::string str = header;
862  if (cap == spv::Capability::Shader)
863    branch.AppendBody("OpLoopMerge %merge %target None\n");
864
865  str += nameOps("branch", "merge", "target", std::make_pair("func", "Main"));
866  str += types_consts();
867  str += "%func    = OpFunction %voidt None %funct\n";
868  str += body;
869  str += target;
870  str += merge;
871  str += entry >> branch;
872  str += branch >> std::vector<Block>({merge});
873  str += "OpFunctionEnd\n";
874
875  return str;
876}
877
878TEST_P(ValidateCFG, UnreachableContinueUnreachableLoopInst) {
879  CompileSuccessfully(GetUnreachableContinueUnreachableLoopInst(GetParam()));
880  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
881}
882
883std::string GetUnreachableMergeWithComplexBody(spv::Capability cap) {
884  std::string header = GetDefaultHeader(cap);
885
886  Block entry("entry");
887  Block branch("branch", spv::Op::OpBranchConditional);
888  Block t("t", spv::Op::OpReturn);
889  Block f("f", spv::Op::OpReturn);
890  Block merge("merge", spv::Op::OpUnreachable);
891
892  entry.AppendBody("%placeholder   = OpVariable %intptrt Function\n");
893  entry.AppendBody("%cond    = OpSLessThan %boolt %one %two\n");
894  merge.AppendBody("OpStore %placeholder %one\n");
895
896  std::string str = header;
897  if (cap == spv::Capability::Shader)
898    branch.AppendBody("OpSelectionMerge %merge None\n");
899
900  str += nameOps("branch", "merge", std::make_pair("func", "Main"));
901  str += types_consts();
902  str += "%intptrt = OpTypePointer Function %intt\n";
903  str += "%func    = OpFunction %voidt None %funct\n";
904  str += entry >> branch;
905  str += branch >> std::vector<Block>({t, f});
906  str += t;
907  str += f;
908  str += merge;
909  str += "OpFunctionEnd\n";
910
911  return str;
912}
913
914TEST_P(ValidateCFG, UnreachableMergeWithComplexBody) {
915  CompileSuccessfully(GetUnreachableMergeWithComplexBody(GetParam()));
916  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
917}
918
919std::string GetUnreachableContinueWithComplexBody(spv::Capability cap) {
920  std::string header = GetDefaultHeader(cap);
921
922  Block entry("entry");
923  Block branch("branch", spv::Op::OpBranch);
924  Block merge("merge", spv::Op::OpReturn);
925  Block target("target", spv::Op::OpBranch);
926
927  target >> branch;
928
929  entry.AppendBody("%placeholder   = OpVariable %intptrt Function\n");
930  target.AppendBody("OpStore %placeholder %one\n");
931
932  std::string str = header;
933  if (cap == spv::Capability::Shader)
934    branch.AppendBody("OpLoopMerge %merge %target None\n");
935
936  str += nameOps("branch", "merge", "target", std::make_pair("func", "Main"));
937  str += types_consts();
938  str += "%intptrt = OpTypePointer Function %intt\n";
939  str += "%func    = OpFunction %voidt None %funct\n";
940  str += entry >> branch;
941  str += branch >> std::vector<Block>({merge});
942  str += merge;
943  str += target;
944  str += "OpFunctionEnd\n";
945
946  return str;
947}
948
949TEST_P(ValidateCFG, UnreachableContinueWithComplexBody) {
950  CompileSuccessfully(GetUnreachableContinueWithComplexBody(GetParam()));
951  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
952}
953
954std::string GetUnreachableMergeWithBranchUse(spv::Capability cap) {
955  std::string header = GetDefaultHeader(cap);
956
957  Block entry("entry");
958  Block branch("branch", spv::Op::OpBranchConditional);
959  Block t("t", spv::Op::OpBranch);
960  Block f("f", spv::Op::OpReturn);
961  Block merge("merge", spv::Op::OpUnreachable);
962
963  entry.AppendBody("%cond    = OpSLessThan %boolt %one %two\n");
964
965  std::string str = header;
966  if (cap == spv::Capability::Shader)
967    branch.AppendBody("OpSelectionMerge %merge None\n");
968
969  str += nameOps("branch", "merge", std::make_pair("func", "Main"));
970  str += types_consts();
971  str += "%func    = OpFunction %voidt None %funct\n";
972  str += entry >> branch;
973  str += branch >> std::vector<Block>({t, f});
974  str += t >> merge;
975  str += f;
976  str += merge;
977  str += "OpFunctionEnd\n";
978
979  return str;
980}
981
982TEST_P(ValidateCFG, UnreachableMergeWithBranchUse) {
983  CompileSuccessfully(GetUnreachableMergeWithBranchUse(GetParam()));
984  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
985}
986
987std::string GetUnreachableMergeWithMultipleUses(spv::Capability cap) {
988  std::string header = GetDefaultHeader(cap);
989
990  Block entry("entry");
991  Block branch("branch", spv::Op::OpBranchConditional);
992  Block t("t", spv::Op::OpReturn);
993  Block f("f", spv::Op::OpReturn);
994  Block merge("merge", spv::Op::OpUnreachable);
995  Block duplicate("duplicate", spv::Op::OpBranchConditional);
996
997  entry.AppendBody("%cond    = OpSLessThan %boolt %one %two\n");
998
999  std::string str = header;
1000  if (cap == spv::Capability::Shader) {
1001    branch.AppendBody("OpSelectionMerge %merge None\n");
1002    duplicate.AppendBody("OpSelectionMerge %merge None\n");
1003  }
1004
1005  str += nameOps("branch", "merge", std::make_pair("func", "Main"));
1006  str += types_consts();
1007  str += "%func    = OpFunction %voidt None %funct\n";
1008  str += entry >> branch;
1009  str += branch >> std::vector<Block>({t, f});
1010  str += duplicate >> std::vector<Block>({t, f});
1011  str += t;
1012  str += f;
1013  str += merge;
1014  str += "OpFunctionEnd\n";
1015
1016  return str;
1017}
1018
1019TEST_P(ValidateCFG, UnreachableMergeWithMultipleUses) {
1020  CompileSuccessfully(GetUnreachableMergeWithMultipleUses(GetParam()));
1021  if (GetParam() == spv::Capability::Shader) {
1022    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1023    EXPECT_THAT(getDiagnosticString(),
1024                HasSubstr("is already a merge block for another header"));
1025  } else {
1026    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1027  }
1028}
1029
1030std::string GetUnreachableContinueWithBranchUse(spv::Capability cap) {
1031  std::string header = GetDefaultHeader(cap);
1032
1033  Block entry("entry");
1034  Block branch("branch", spv::Op::OpBranch);
1035  Block merge("merge", spv::Op::OpReturn);
1036  Block target("target", spv::Op::OpBranch);
1037
1038  target >> branch;
1039
1040  entry.AppendBody("%placeholder   = OpVariable %intptrt Function\n");
1041
1042  std::string str = header;
1043  if (cap == spv::Capability::Shader)
1044    branch.AppendBody("OpLoopMerge %merge %target None\n");
1045
1046  str += nameOps("branch", "merge", "target", std::make_pair("func", "Main"));
1047  str += types_consts();
1048  str += "%intptrt = OpTypePointer Function %intt\n";
1049  str += "%func    = OpFunction %voidt None %funct\n";
1050  str += entry >> branch;
1051  str += branch >> std::vector<Block>({merge});
1052  str += merge;
1053  str += target;
1054  str += "OpFunctionEnd\n";
1055
1056  return str;
1057}
1058
1059TEST_P(ValidateCFG, UnreachableContinueWithBranchUse) {
1060  CompileSuccessfully(GetUnreachableContinueWithBranchUse(GetParam()));
1061  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1062}
1063
1064std::string GetReachableMergeAndContinue(spv::Capability cap) {
1065  std::string header = GetDefaultHeader(cap);
1066
1067  Block entry("entry");
1068  Block branch("branch", spv::Op::OpBranch);
1069  Block merge("merge", spv::Op::OpReturn);
1070  Block target("target", spv::Op::OpBranch);
1071  Block body("body", spv::Op::OpBranchConditional);
1072  Block t("t", spv::Op::OpBranch);
1073  Block f("f", spv::Op::OpBranch);
1074
1075  target >> branch;
1076  body.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1077  t >> merge;
1078  f >> target;
1079
1080  std::string str = header;
1081  if (cap == spv::Capability::Shader) {
1082    branch.AppendBody("OpLoopMerge %merge %target None\n");
1083    body.AppendBody("OpSelectionMerge %f None\n");
1084  }
1085
1086  str += nameOps("branch", "merge", "target", "body", "t", "f",
1087                 std::make_pair("func", "Main"));
1088  str += types_consts();
1089  str += "%func    = OpFunction %voidt None %funct\n";
1090  str += entry >> branch;
1091  str += branch >> std::vector<Block>({body});
1092  str += body >> std::vector<Block>({t, f});
1093  str += t;
1094  str += f;
1095  str += merge;
1096  str += target;
1097  str += "OpFunctionEnd\n";
1098
1099  return str;
1100}
1101
1102TEST_P(ValidateCFG, ReachableMergeAndContinue) {
1103  CompileSuccessfully(GetReachableMergeAndContinue(GetParam()));
1104  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1105}
1106
1107std::string GetUnreachableMergeAndContinue(spv::Capability cap) {
1108  std::string header = GetDefaultHeader(cap);
1109
1110  Block entry("entry");
1111  Block branch("branch", spv::Op::OpBranch);
1112  Block merge("merge", spv::Op::OpReturn);
1113  Block target("target", spv::Op::OpBranch);
1114  Block body("body", spv::Op::OpBranchConditional);
1115  Block t("t", spv::Op::OpReturn);
1116  Block f("f", spv::Op::OpReturn);
1117  Block pre_target("pre_target", spv::Op::OpBranch);
1118
1119  target >> branch;
1120  body.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1121
1122  std::string str = header;
1123  if (cap == spv::Capability::Shader) {
1124    branch.AppendBody("OpLoopMerge %merge %target None\n");
1125    body.AppendBody("OpSelectionMerge %pre_target None\n");
1126  }
1127
1128  str += nameOps("branch", "merge", "pre_target", "target", "body", "t", "f",
1129                 std::make_pair("func", "Main"));
1130  str += types_consts();
1131  str += "%func    = OpFunction %voidt None %funct\n";
1132  str += entry >> branch;
1133  str += branch >> std::vector<Block>({body});
1134  str += body >> std::vector<Block>({t, f});
1135  str += t;
1136  str += f;
1137  str += merge;
1138  str += pre_target >> target;
1139  str += target;
1140  str += "OpFunctionEnd\n";
1141
1142  return str;
1143}
1144
1145TEST_P(ValidateCFG, UnreachableMergeAndContinue) {
1146  CompileSuccessfully(GetUnreachableMergeAndContinue(GetParam()));
1147  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1148}
1149
1150std::string GetUnreachableBlock(spv::Capability cap) {
1151  std::string header = GetDefaultHeader(cap);
1152
1153  Block entry("entry");
1154  Block unreachable("unreachable");
1155  Block exit("exit", spv::Op::OpReturn);
1156
1157  std::string str = header;
1158  str += nameOps("unreachable", "exit", std::make_pair("func", "Main"));
1159  str += types_consts();
1160  str += "%func    = OpFunction %voidt None %funct\n";
1161  str += entry >> exit;
1162  str += unreachable >> exit;
1163  str += exit;
1164  str += "OpFunctionEnd\n";
1165
1166  return str;
1167}
1168
1169TEST_P(ValidateCFG, UnreachableBlock) {
1170  CompileSuccessfully(GetUnreachableBlock(GetParam()));
1171  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1172}
1173
1174std::string GetUnreachableBranch(spv::Capability cap) {
1175  std::string header = GetDefaultHeader(cap);
1176
1177  Block entry("entry");
1178  Block unreachable("unreachable", spv::Op::OpBranchConditional);
1179  Block unreachablechildt("unreachablechildt");
1180  Block unreachablechildf("unreachablechildf");
1181  Block merge("merge");
1182  Block exit("exit", spv::Op::OpReturn);
1183
1184  unreachable.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1185  if (cap == spv::Capability::Shader)
1186    unreachable.AppendBody("OpSelectionMerge %merge None\n");
1187
1188  std::string str = header;
1189  str += nameOps("unreachable", "exit", std::make_pair("func", "Main"));
1190  str += types_consts();
1191  str += "%func    = OpFunction %voidt None %funct\n";
1192
1193  str += entry >> exit;
1194  str +=
1195      unreachable >> std::vector<Block>({unreachablechildt, unreachablechildf});
1196  str += unreachablechildt >> merge;
1197  str += unreachablechildf >> merge;
1198  str += merge >> exit;
1199  str += exit;
1200  str += "OpFunctionEnd\n";
1201
1202  return str;
1203}
1204
1205TEST_P(ValidateCFG, UnreachableBranch) {
1206  CompileSuccessfully(GetUnreachableBranch(GetParam()));
1207  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1208}
1209
1210TEST_P(ValidateCFG, EmptyFunction) {
1211  std::string str = GetDefaultHeader(GetParam()) + std::string(types_consts()) +
1212                    R"(%func    = OpFunction %voidt None %funct
1213                  %l = OpLabel
1214                  OpReturn
1215                  OpFunctionEnd)";
1216
1217  CompileSuccessfully(str);
1218  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1219}
1220
1221TEST_P(ValidateCFG, SingleBlockLoop) {
1222  bool is_shader = GetParam() == spv::Capability::Shader;
1223  Block entry("entry");
1224  Block loop("loop", spv::Op::OpBranchConditional);
1225  Block exit("exit", spv::Op::OpReturn);
1226
1227  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1228  if (is_shader) loop.AppendBody("OpLoopMerge %exit %loop None\n");
1229
1230  std::string str = GetDefaultHeader(GetParam()) + std::string(types_consts()) +
1231                    "%func    = OpFunction %voidt None %funct\n";
1232
1233  str += entry >> loop;
1234  str += loop >> std::vector<Block>({loop, exit});
1235  str += exit;
1236  str += "OpFunctionEnd";
1237
1238  CompileSuccessfully(str);
1239  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1240}
1241
1242TEST_P(ValidateCFG, NestedLoops) {
1243  bool is_shader = GetParam() == spv::Capability::Shader;
1244  Block entry("entry");
1245  Block loop1("loop1");
1246  Block loop1_cont_break_block("loop1_cont_break_block",
1247                               spv::Op::OpBranchConditional);
1248  Block loop2("loop2", spv::Op::OpBranchConditional);
1249  Block loop2_merge("loop2_merge");
1250  Block loop1_merge("loop1_merge");
1251  Block exit("exit", spv::Op::OpReturn);
1252
1253  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1254  if (is_shader) {
1255    loop1.SetBody("OpLoopMerge %loop1_merge %loop2 None\n");
1256    loop2.SetBody("OpLoopMerge %loop2_merge %loop2 None\n");
1257  }
1258
1259  std::string str =
1260      GetDefaultHeader(GetParam()) +
1261      nameOps("loop1", "loop1_cont_break_block", "loop2", "loop2_merge") +
1262      types_consts() + "%func    = OpFunction %voidt None %funct\n";
1263
1264  str += entry >> loop1;
1265  str += loop1 >> loop1_cont_break_block;
1266  str += loop1_cont_break_block >> std::vector<Block>({loop1_merge, loop2});
1267  str += loop2 >> std::vector<Block>({loop2, loop2_merge});
1268  str += loop2_merge >> loop1;
1269  str += loop1_merge >> exit;
1270  str += exit;
1271  str += "OpFunctionEnd";
1272
1273  CompileSuccessfully(str);
1274  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1275}
1276
1277TEST_P(ValidateCFG, NestedSelection) {
1278  bool is_shader = GetParam() == spv::Capability::Shader;
1279  Block entry("entry");
1280  const int N = 256;
1281  std::vector<Block> if_blocks;
1282  std::vector<Block> merge_blocks;
1283  Block inner("inner");
1284
1285  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1286
1287  if_blocks.emplace_back("if0", spv::Op::OpBranchConditional);
1288
1289  if (is_shader) if_blocks[0].SetBody("OpSelectionMerge %if_merge0 None\n");
1290  merge_blocks.emplace_back("if_merge0", spv::Op::OpReturn);
1291
1292  for (int i = 1; i < N; i++) {
1293    std::stringstream ss;
1294    ss << i;
1295    if_blocks.emplace_back("if" + ss.str(), spv::Op::OpBranchConditional);
1296    if (is_shader)
1297      if_blocks[i].SetBody("OpSelectionMerge %if_merge" + ss.str() + " None\n");
1298    merge_blocks.emplace_back("if_merge" + ss.str(), spv::Op::OpBranch);
1299  }
1300  std::string str = GetDefaultHeader(GetParam()) + std::string(types_consts()) +
1301                    "%func    = OpFunction %voidt None %funct\n";
1302
1303  str += entry >> if_blocks[0];
1304  for (int i = 0; i < N - 1; i++) {
1305    str +=
1306        if_blocks[i] >> std::vector<Block>({if_blocks[i + 1], merge_blocks[i]});
1307  }
1308  str += if_blocks.back() >> std::vector<Block>({inner, merge_blocks.back()});
1309  str += inner >> merge_blocks.back();
1310  for (int i = N - 1; i > 0; i--) {
1311    str += merge_blocks[i] >> merge_blocks[i - 1];
1312  }
1313  str += merge_blocks[0];
1314  str += "OpFunctionEnd";
1315
1316  CompileSuccessfully(str);
1317  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1318}
1319
1320TEST_P(ValidateCFG, BackEdgeBlockDoesntPostDominateContinueTargetBad) {
1321  bool is_shader = GetParam() == spv::Capability::Shader;
1322  Block entry("entry");
1323  Block loop1("loop1", spv::Op::OpBranchConditional);
1324  Block loop2("loop2", spv::Op::OpBranchConditional);
1325  Block loop2_merge("loop2_merge");
1326  Block loop1_cont("loop1_cont", spv::Op::OpBranchConditional);
1327  Block be_block("be_block");
1328  Block exit("exit", spv::Op::OpReturn);
1329
1330  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1331  if (is_shader) {
1332    loop1.SetBody("OpLoopMerge %exit %loop1_cont None\n");
1333    loop2.SetBody("OpLoopMerge %loop2_merge %loop2 None\n");
1334  }
1335
1336  std::string str =
1337      GetDefaultHeader(GetParam()) +
1338      nameOps("loop1", "loop2", "be_block", "loop1_cont", "loop2_merge") +
1339      types_consts() + "%func    = OpFunction %voidt None %funct\n";
1340
1341  str += entry >> loop1;
1342  str += loop1 >> std::vector<Block>({loop2, exit});
1343  str += loop2 >> std::vector<Block>({loop2, loop2_merge});
1344  str += loop2_merge >> loop1_cont;
1345  str += loop1_cont >> std::vector<Block>({be_block, exit});
1346  str += be_block >> loop1;
1347  str += exit;
1348  str += "OpFunctionEnd";
1349
1350  CompileSuccessfully(str);
1351  if (GetParam() == spv::Capability::Shader) {
1352    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1353    EXPECT_THAT(
1354        getDiagnosticString(),
1355        MatchesRegex(
1356            "The continue construct with the continue target "
1357            "'.\\[%loop1_cont\\]' is not structurally post dominated by the "
1358            "back-edge block '.\\[%be_block\\]'\n"
1359            "  %be_block = OpLabel\n"));
1360  } else {
1361    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1362  }
1363}
1364
1365TEST_P(ValidateCFG, BranchingToNonLoopHeaderBlockBad) {
1366  bool is_shader = GetParam() == spv::Capability::Shader;
1367  Block entry("entry");
1368  Block split("split", spv::Op::OpBranchConditional);
1369  Block t("t");
1370  Block f("f");
1371  Block exit("exit", spv::Op::OpReturn);
1372
1373  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1374  if (is_shader) split.SetBody("OpSelectionMerge %exit None\n");
1375
1376  std::string str = GetDefaultHeader(GetParam()) + nameOps("split", "f") +
1377                    types_consts() +
1378                    "%func    = OpFunction %voidt None %funct\n";
1379
1380  str += entry >> split;
1381  str += split >> std::vector<Block>({t, f});
1382  str += t >> exit;
1383  str += f >> split;
1384  str += exit;
1385  str += "OpFunctionEnd";
1386
1387  CompileSuccessfully(str);
1388  if (is_shader) {
1389    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1390    EXPECT_THAT(
1391        getDiagnosticString(),
1392        MatchesRegex("Back-edges \\('.\\[%f\\]' -> '.\\[%split\\]'\\) can only "
1393                     "be formed between a block and a loop header.\n"
1394                     "  %f = OpLabel\n"));
1395  } else {
1396    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1397  }
1398}
1399
1400TEST_P(ValidateCFG, BranchingToSameNonLoopHeaderBlockBad) {
1401  bool is_shader = GetParam() == spv::Capability::Shader;
1402  Block entry("entry");
1403  Block split("split", spv::Op::OpBranchConditional);
1404  Block exit("exit", spv::Op::OpReturn);
1405
1406  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1407  if (is_shader) split.SetBody("OpSelectionMerge %exit None\n");
1408
1409  std::string str = GetDefaultHeader(GetParam()) + nameOps("split") +
1410                    types_consts() +
1411                    "%func    = OpFunction %voidt None %funct\n";
1412
1413  str += entry >> split;
1414  str += split >> std::vector<Block>({split, exit});
1415  str += exit;
1416  str += "OpFunctionEnd";
1417
1418  CompileSuccessfully(str);
1419  if (is_shader) {
1420    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1421    EXPECT_THAT(
1422        getDiagnosticString(),
1423        MatchesRegex(
1424            "Back-edges \\('.\\[%split\\]' -> '.\\[%split\\]'\\) can only be "
1425            "formed between a block and a loop header.\n  %split = OpLabel\n"));
1426  } else {
1427    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1428  }
1429}
1430
1431TEST_P(ValidateCFG, MultipleBackEdgeBlocksToLoopHeaderBad) {
1432  bool is_shader = GetParam() == spv::Capability::Shader;
1433  Block entry("entry");
1434  Block loop("loop", spv::Op::OpBranchConditional);
1435  Block back0("back0");
1436  Block back1("back1");
1437  Block merge("merge", spv::Op::OpReturn);
1438
1439  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1440  if (is_shader) loop.SetBody("OpLoopMerge %merge %back0 None\n");
1441
1442  std::string str = GetDefaultHeader(GetParam()) +
1443                    nameOps("loop", "back0", "back1") + types_consts() +
1444                    "%func    = OpFunction %voidt None %funct\n";
1445
1446  str += entry >> loop;
1447  str += loop >> std::vector<Block>({back0, back1});
1448  str += back0 >> loop;
1449  str += back1 >> loop;
1450  str += merge;
1451  str += "OpFunctionEnd";
1452
1453  CompileSuccessfully(str);
1454  if (is_shader) {
1455    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1456    EXPECT_THAT(
1457        getDiagnosticString(),
1458        MatchesRegex(
1459            "Loop header '.\\[%loop\\]' is targeted by 2 back-edge blocks but "
1460            "the standard requires exactly one\n  %loop = OpLabel\n"))
1461        << str;
1462  } else {
1463    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1464  }
1465}
1466
1467TEST_P(ValidateCFG, ContinueTargetMustBePostDominatedByBackEdge) {
1468  bool is_shader = GetParam() == spv::Capability::Shader;
1469  Block entry("entry");
1470  Block loop("loop", spv::Op::OpBranchConditional);
1471  Block cheader("cheader", spv::Op::OpBranchConditional);
1472  Block be_block("be_block");
1473  Block merge("merge", spv::Op::OpReturn);
1474  Block exit("exit", spv::Op::OpReturn);
1475
1476  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1477  if (is_shader) loop.SetBody("OpLoopMerge %merge %cheader None\n");
1478
1479  std::string str = GetDefaultHeader(GetParam()) +
1480                    nameOps("cheader", "be_block") + types_consts() +
1481                    "%func    = OpFunction %voidt None %funct\n";
1482
1483  str += entry >> loop;
1484  str += loop >> std::vector<Block>({cheader, merge});
1485  str += cheader >> std::vector<Block>({exit, be_block});
1486  str += exit;  //  Branches out of a continue construct
1487  str += be_block >> loop;
1488  str += merge;
1489  str += "OpFunctionEnd";
1490
1491  CompileSuccessfully(str);
1492  if (is_shader) {
1493    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1494    EXPECT_THAT(
1495        getDiagnosticString(),
1496        MatchesRegex(
1497            "The continue construct with the continue target "
1498            "'.\\[%cheader\\]' is not structurally post dominated by the "
1499            "back-edge block '.\\[%be_block\\]'\n"
1500            "  %be_block = OpLabel\n"));
1501  } else {
1502    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1503  }
1504}
1505
1506TEST_P(ValidateCFG, BranchOutOfConstructToMergeBad) {
1507  bool is_shader = GetParam() == spv::Capability::Shader;
1508  Block entry("entry");
1509  Block loop("loop", spv::Op::OpBranchConditional);
1510  Block cont("cont", spv::Op::OpBranchConditional);
1511  Block merge("merge", spv::Op::OpReturn);
1512
1513  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1514  if (is_shader) loop.SetBody("OpLoopMerge %merge %loop None\n");
1515
1516  std::string str = GetDefaultHeader(GetParam()) + nameOps("cont", "loop") +
1517                    types_consts() +
1518                    "%func    = OpFunction %voidt None %funct\n";
1519
1520  str += entry >> loop;
1521  str += loop >> std::vector<Block>({cont, merge});
1522  str += cont >> std::vector<Block>({loop, merge});
1523  str += merge;
1524  str += "OpFunctionEnd";
1525
1526  CompileSuccessfully(str);
1527  if (is_shader) {
1528    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1529    EXPECT_THAT(
1530        getDiagnosticString(),
1531        MatchesRegex("The continue construct with the continue target "
1532                     "'.\\[%loop\\]' is not structurally post dominated by the "
1533                     "back-edge block '.\\[%cont\\]'\n"
1534                     "  %cont = OpLabel\n"))
1535        << str;
1536  } else {
1537    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1538  }
1539}
1540
1541TEST_P(ValidateCFG, BranchOutOfConstructBad) {
1542  bool is_shader = GetParam() == spv::Capability::Shader;
1543  Block entry("entry");
1544  Block loop("loop", spv::Op::OpBranchConditional);
1545  Block cont("cont", spv::Op::OpBranchConditional);
1546  Block merge("merge");
1547  Block exit("exit", spv::Op::OpReturn);
1548
1549  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1550  if (is_shader) loop.SetBody("OpLoopMerge %merge %loop None\n");
1551
1552  std::string str = GetDefaultHeader(GetParam()) + nameOps("cont", "loop") +
1553                    types_consts() +
1554                    "%func    = OpFunction %voidt None %funct\n";
1555
1556  str += entry >> loop;
1557  str += loop >> std::vector<Block>({cont, merge});
1558  str += cont >> std::vector<Block>({loop, exit});
1559  str += merge >> exit;
1560  str += exit;
1561  str += "OpFunctionEnd";
1562
1563  CompileSuccessfully(str);
1564  if (is_shader) {
1565    ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1566    EXPECT_THAT(
1567        getDiagnosticString(),
1568        MatchesRegex("The continue construct with the continue target "
1569                     "'.\\[%loop\\]' is not structurally post dominated by the "
1570                     "back-edge block '.\\[%cont\\]'\n"
1571                     "  %cont = OpLabel\n"));
1572  } else {
1573    ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1574  }
1575}
1576
1577TEST_F(ValidateCFG, OpSwitchToUnreachableBlock) {
1578  Block entry("entry", spv::Op::OpSwitch);
1579  Block case0("case0");
1580  Block case1("case1");
1581  Block case2("case2");
1582  Block def("default", spv::Op::OpUnreachable);
1583  Block phi("phi", spv::Op::OpReturn);
1584
1585  std::string str = R"(
1586OpCapability Shader
1587OpMemoryModel Logical GLSL450
1588OpEntryPoint GLCompute %main "main" %id
1589OpExecutionMode %main LocalSize 1 1 1
1590OpSource GLSL 430
1591OpName %main "main"
1592OpDecorate %id BuiltIn GlobalInvocationId
1593%void      = OpTypeVoid
1594%voidf     = OpTypeFunction %void
1595%u32       = OpTypeInt 32 0
1596%f32       = OpTypeFloat 32
1597%uvec3     = OpTypeVector %u32 3
1598%fvec3     = OpTypeVector %f32 3
1599%uvec3ptr  = OpTypePointer Input %uvec3
1600%id        = OpVariable %uvec3ptr Input
1601%one       = OpConstant %u32 1
1602%three     = OpConstant %u32 3
1603%main      = OpFunction %void None %voidf
1604)";
1605
1606  entry.SetBody(
1607      "%idval    = OpLoad %uvec3 %id\n"
1608      "%x        = OpCompositeExtract %u32 %idval 0\n"
1609      "%selector = OpUMod %u32 %x %three\n"
1610      "OpSelectionMerge %phi None\n");
1611  str += entry >> std::vector<Block>({def, case0, case1, case2});
1612  str += case1 >> phi;
1613  str += def;
1614  str += phi;
1615  str += case0 >> phi;
1616  str += case2 >> phi;
1617  str += "OpFunctionEnd";
1618
1619  CompileSuccessfully(str);
1620  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
1621}
1622
1623TEST_F(ValidateCFG, LoopWithZeroBackEdgesBad) {
1624  std::string str = R"(
1625           OpCapability Shader
1626           OpMemoryModel Logical GLSL450
1627           OpEntryPoint Fragment %main "main"
1628           OpExecutionMode %main OriginUpperLeft
1629           OpName %loop "loop"
1630%voidt   = OpTypeVoid
1631%funct   = OpTypeFunction %voidt
1632%main    = OpFunction %voidt None %funct
1633%loop    = OpLabel
1634           OpLoopMerge %exit %loop None
1635           OpBranch %exit
1636%exit    = OpLabel
1637           OpReturn
1638           OpFunctionEnd
1639)";
1640  CompileSuccessfully(str);
1641  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1642  EXPECT_THAT(
1643      getDiagnosticString(),
1644      MatchesRegex("Loop header '.\\[%loop\\]' is targeted by "
1645                   "0 back-edge blocks but the standard requires exactly "
1646                   "one\n  %loop = OpLabel\n"));
1647}
1648
1649TEST_F(ValidateCFG, LoopWithBackEdgeFromUnreachableContinueConstructGood) {
1650  std::string str = R"(
1651           OpCapability Shader
1652           OpMemoryModel Logical GLSL450
1653           OpEntryPoint Fragment %main "main"
1654           OpExecutionMode %main OriginUpperLeft
1655           OpName %loop "loop"
1656%voidt   = OpTypeVoid
1657%funct   = OpTypeFunction %voidt
1658%floatt  = OpTypeFloat 32
1659%boolt   = OpTypeBool
1660%one     = OpConstant %floatt 1
1661%two     = OpConstant %floatt 2
1662%main    = OpFunction %voidt None %funct
1663%entry   = OpLabel
1664           OpBranch %loop
1665%loop    = OpLabel
1666           OpLoopMerge %exit %cont None
1667           OpBranch %16
1668%16      = OpLabel
1669%cond    = OpFOrdLessThan %boolt %one %two
1670           OpBranchConditional %cond %body %exit
1671%body    = OpLabel
1672           OpReturn
1673%cont    = OpLabel   ; Reachable only from OpLoopMerge ContinueTarget parameter
1674           OpBranch %loop ; Should be considered a back-edge
1675%exit    = OpLabel
1676           OpReturn
1677           OpFunctionEnd
1678)";
1679
1680  CompileSuccessfully(str);
1681  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()) << getDiagnosticString();
1682}
1683
1684TEST_P(ValidateCFG,
1685       NestedConstructWithUnreachableMergeBlockBranchingToOuterMergeBlock) {
1686  // Test for https://github.com/KhronosGroup/SPIRV-Tools/issues/297
1687  // The nested construct has an unreachable merge block.  In the
1688  // augmented CFG that merge block
1689  // we still determine that the
1690  bool is_shader = GetParam() == spv::Capability::Shader;
1691  Block entry("entry", spv::Op::OpBranchConditional);
1692  Block inner_head("inner_head", spv::Op::OpBranchConditional);
1693  Block inner_true("inner_true", spv::Op::OpReturn);
1694  Block inner_false("inner_false", spv::Op::OpReturn);
1695  Block inner_merge("inner_merge");
1696  Block exit("exit", spv::Op::OpReturn);
1697
1698  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1699  if (is_shader) {
1700    entry.AppendBody("OpSelectionMerge %exit None\n");
1701    inner_head.SetBody("OpSelectionMerge %inner_merge None\n");
1702  }
1703
1704  std::string str = GetDefaultHeader(GetParam()) +
1705                    nameOps("entry", "inner_merge", "exit") + types_consts() +
1706                    "%func    = OpFunction %voidt None %funct\n";
1707
1708  str += entry >> std::vector<Block>({inner_head, exit});
1709  str += inner_head >> std::vector<Block>({inner_true, inner_false});
1710  str += inner_true;
1711  str += inner_false;
1712  str += inner_merge >> exit;
1713  str += exit;
1714  str += "OpFunctionEnd";
1715
1716  CompileSuccessfully(str);
1717  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()) << getDiagnosticString();
1718}
1719
1720TEST_P(ValidateCFG, ContinueTargetCanBeMergeBlockForNestedStructure) {
1721  // The continue construct cannot be the merge target of a nested selection
1722  // because the loop construct must contain "if_merge" because it contains
1723  // "if_head".
1724  bool is_shader = GetParam() == spv::Capability::Shader;
1725  Block entry("entry");
1726  Block loop("loop");
1727  Block if_head("if_head", spv::Op::OpBranchConditional);
1728  Block if_true("if_true");
1729  Block if_merge("if_merge", spv::Op::OpBranchConditional);
1730  Block merge("merge", spv::Op::OpReturn);
1731
1732  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1733  if (is_shader) {
1734    loop.SetBody("OpLoopMerge %merge %if_merge None\n");
1735    if_head.SetBody("OpSelectionMerge %if_merge None\n");
1736  }
1737
1738  std::string str =
1739      GetDefaultHeader(GetParam()) +
1740      nameOps("entry", "loop", "if_head", "if_true", "if_merge", "merge") +
1741      types_consts() + "%func    = OpFunction %voidt None %funct\n";
1742
1743  str += entry >> loop;
1744  str += loop >> if_head;
1745  str += if_head >> std::vector<Block>({if_true, if_merge});
1746  str += if_true >> if_merge;
1747  str += if_merge >> std::vector<Block>({loop, merge});
1748  str += merge;
1749  str += "OpFunctionEnd";
1750
1751  CompileSuccessfully(str);
1752  if (is_shader) {
1753    EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1754    EXPECT_THAT(
1755        getDiagnosticString(),
1756        HasSubstr(
1757            "Header block '3[%if_head]' is contained in the loop construct "
1758            "headed "
1759            "by '2[%loop]', but its merge block '5[%if_merge]' is not"));
1760  } else {
1761    EXPECT_THAT(SPV_SUCCESS, ValidateInstructions());
1762  }
1763}
1764
1765TEST_P(ValidateCFG, SingleLatchBlockMultipleBranchesToLoopHeader) {
1766  // This test case ensures we allow both branches of a loop latch block
1767  // to go back to the loop header.  It still counts as a single back edge.
1768  bool is_shader = GetParam() == spv::Capability::Shader;
1769  Block entry("entry");
1770  Block loop("loop", spv::Op::OpBranchConditional);
1771  Block latch("latch", spv::Op::OpBranchConditional);
1772  Block merge("merge", spv::Op::OpReturn);
1773
1774  entry.SetBody("%cond    = OpSLessThan %boolt %one %two\n");
1775  if (is_shader) {
1776    loop.SetBody("OpLoopMerge %merge %latch None\n");
1777  }
1778
1779  std::string str = GetDefaultHeader(GetParam()) +
1780                    nameOps("entry", "loop", "latch", "merge") +
1781                    types_consts() +
1782                    "%func    = OpFunction %voidt None %funct\n";
1783
1784  str += entry >> loop;
1785  str += loop >> std::vector<Block>({latch, merge});
1786  str += latch >> std::vector<Block>({loop, loop});  // This is the key
1787  str += merge;
1788  str += "OpFunctionEnd";
1789
1790  CompileSuccessfully(str);
1791  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions())
1792      << str << getDiagnosticString();
1793}
1794
1795// Unit test to check the case where a basic block is the entry block of 2
1796// different constructs. In this case, the basic block is the entry block of a
1797// continue construct as well as a selection construct. See issue# 517 for more
1798// details.
1799TEST_F(ValidateCFG, BasicBlockIsEntryBlockOfTwoConstructsGood) {
1800  std::string spirv = R"(
1801               OpCapability Shader
1802               OpCapability Linkage
1803               OpMemoryModel Logical GLSL450
1804       %void = OpTypeVoid
1805       %bool = OpTypeBool
1806        %int = OpTypeInt 32 1
1807  %void_func = OpTypeFunction %void
1808      %int_0 = OpConstant %int 0
1809    %testfun = OpFunction %void None %void_func
1810    %label_1 = OpLabel
1811               OpBranch %start
1812      %start = OpLabel
1813       %cond = OpSLessThan %bool %int_0 %int_0
1814       ;
1815       ; Note: In this case, the "target" block is both the entry block of
1816       ;       the continue construct of the loop as well as the entry block of
1817       ;       the selection construct.
1818       ;
1819               OpLoopMerge %loop_merge %target None
1820               OpBranchConditional %cond %target %loop_merge
1821 %loop_merge = OpLabel
1822               OpReturn
1823     %target = OpLabel
1824               OpSelectionMerge %selection_merge None
1825               OpBranchConditional %cond %do_stuff %do_other_stuff
1826     %do_other_stuff = OpLabel
1827               OpBranch %selection_merge
1828     %selection_merge = OpLabel
1829               OpBranch %start
1830         %do_stuff = OpLabel
1831               OpBranch %selection_merge
1832               OpFunctionEnd
1833  )";
1834  CompileSuccessfully(spirv);
1835  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
1836}
1837
1838TEST_F(ValidateCFG, OpReturnInNonVoidFunc) {
1839  std::string spirv = R"(
1840               OpCapability Shader
1841               OpCapability Linkage
1842               OpMemoryModel Logical GLSL450
1843        %int = OpTypeInt 32 1
1844   %int_func = OpTypeFunction %int
1845    %testfun = OpFunction %int None %int_func
1846    %label_1 = OpLabel
1847               OpReturn
1848               OpFunctionEnd
1849  )";
1850  CompileSuccessfully(spirv);
1851  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1852  EXPECT_THAT(
1853      getDiagnosticString(),
1854      HasSubstr(
1855          "OpReturn can only be called from a function with void return type.\n"
1856          "  OpReturn"));
1857}
1858
1859TEST_F(ValidateCFG, StructuredCFGBranchIntoSelectionBody) {
1860  std::string spirv = R"(
1861OpCapability Shader
1862OpMemoryModel Logical GLSL450
1863OpEntryPoint Fragment %func "func"
1864OpExecutionMode %func OriginUpperLeft
1865%void = OpTypeVoid
1866%bool = OpTypeBool
1867%true = OpConstantTrue %bool
1868%functy = OpTypeFunction %void
1869%func = OpFunction %void None %functy
1870%entry = OpLabel
1871OpSelectionMerge %merge None
1872OpBranchConditional %true %then %merge
1873%merge = OpLabel
1874OpBranch %then
1875%then = OpLabel
1876OpReturn
1877OpFunctionEnd
1878)";
1879
1880  CompileSuccessfully(spirv);
1881  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1882  EXPECT_THAT(getDiagnosticString(),
1883              HasSubstr("branches to the selection construct, but not to the "
1884                        "selection header <ID> 6\n  %7 = OpLabel"));
1885}
1886
1887TEST_F(ValidateCFG, SwitchDefaultOnly) {
1888  std::string text = R"(
1889OpCapability Shader
1890OpCapability Linkage
1891OpMemoryModel Logical GLSL450
1892%1 = OpTypeVoid
1893%2 = OpTypeInt 32 0
1894%3 = OpConstant %2 0
1895%4 = OpTypeFunction %1
1896%5 = OpFunction %1 None %4
1897%6 = OpLabel
1898OpSelectionMerge %7 None
1899OpSwitch %3 %7
1900%7 = OpLabel
1901OpReturn
1902OpFunctionEnd
1903)";
1904
1905  CompileSuccessfully(text);
1906  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1907}
1908
1909TEST_F(ValidateCFG, SwitchSingleCase) {
1910  std::string text = R"(
1911OpCapability Shader
1912OpCapability Linkage
1913OpMemoryModel Logical GLSL450
1914%1 = OpTypeVoid
1915%2 = OpTypeInt 32 0
1916%3 = OpConstant %2 0
1917%4 = OpTypeFunction %1
1918%5 = OpFunction %1 None %4
1919%6 = OpLabel
1920OpSelectionMerge %7 None
1921OpSwitch %3 %7 0 %8
1922%8 = OpLabel
1923OpBranch %7
1924%7 = OpLabel
1925OpReturn
1926OpFunctionEnd
1927)";
1928
1929  CompileSuccessfully(text);
1930  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
1931}
1932
1933TEST_F(ValidateCFG, MultipleFallThroughBlocks) {
1934  std::string text = R"(
1935OpCapability Shader
1936OpCapability Linkage
1937OpMemoryModel Logical GLSL450
1938%1 = OpTypeVoid
1939%2 = OpTypeInt 32 0
1940%3 = OpConstant %2 0
1941%4 = OpTypeFunction %1
1942%5 = OpTypeBool
1943%6 = OpConstantTrue %5
1944%7 = OpFunction %1 None %4
1945%8 = OpLabel
1946OpSelectionMerge %9 None
1947OpSwitch %3 %10 0 %11 1 %12
1948%10 = OpLabel
1949OpBranchConditional %6 %11 %12
1950%11 = OpLabel
1951OpBranch %9
1952%12 = OpLabel
1953OpBranch %9
1954%9 = OpLabel
1955OpReturn
1956OpFunctionEnd
1957)";
1958
1959  CompileSuccessfully(text);
1960  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1961  EXPECT_THAT(
1962      getDiagnosticString(),
1963      HasSubstr(
1964          "Case construct that targets '10[%10]' has branches to multiple "
1965          "other "
1966          "case construct targets '12[%12]' and '11[%11]'\n  %10 = OpLabel"));
1967}
1968
1969TEST_F(ValidateCFG, MultipleFallThroughToDefault) {
1970  std::string text = R"(
1971OpCapability Shader
1972OpCapability Linkage
1973OpMemoryModel Logical GLSL450
1974%1 = OpTypeVoid
1975%2 = OpTypeInt 32 0
1976%3 = OpConstant %2 0
1977%4 = OpTypeFunction %1
1978%5 = OpTypeBool
1979%6 = OpConstantTrue %5
1980%7 = OpFunction %1 None %4
1981%8 = OpLabel
1982OpSelectionMerge %9 None
1983OpSwitch %3 %10 0 %11 1 %12
1984%10 = OpLabel
1985OpBranch %9
1986%11 = OpLabel
1987OpBranch %10
1988%12 = OpLabel
1989OpBranch %10
1990%9 = OpLabel
1991OpReturn
1992OpFunctionEnd
1993)";
1994
1995  CompileSuccessfully(text);
1996  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
1997  EXPECT_THAT(
1998      getDiagnosticString(),
1999      HasSubstr("Multiple case constructs have branches to the case construct "
2000                "that targets '10[%10]'\n  %10 = OpLabel"));
2001}
2002
2003TEST_F(ValidateCFG, MultipleFallThroughToNonDefault) {
2004  std::string text = R"(
2005OpCapability Shader
2006OpCapability Linkage
2007OpMemoryModel Logical GLSL450
2008%1 = OpTypeVoid
2009%2 = OpTypeInt 32 0
2010%3 = OpConstant %2 0
2011%4 = OpTypeFunction %1
2012%5 = OpTypeBool
2013%6 = OpConstantTrue %5
2014%7 = OpFunction %1 None %4
2015%8 = OpLabel
2016OpSelectionMerge %9 None
2017OpSwitch %3 %10 0 %11 1 %12
2018%10 = OpLabel
2019OpBranch %12
2020%11 = OpLabel
2021OpBranch %12
2022%12 = OpLabel
2023OpBranch %9
2024%9 = OpLabel
2025OpReturn
2026OpFunctionEnd
2027)";
2028
2029  CompileSuccessfully(text);
2030  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2031  EXPECT_THAT(
2032      getDiagnosticString(),
2033      HasSubstr("Multiple case constructs have branches to the case construct "
2034                "that targets '12[%12]'\n  %12 = OpLabel"));
2035}
2036
2037TEST_F(ValidateCFG, DuplicateTargetWithFallThrough) {
2038  std::string text = R"(
2039OpCapability Shader
2040OpCapability Linkage
2041OpMemoryModel Logical GLSL450
2042%1 = OpTypeVoid
2043%2 = OpTypeInt 32 0
2044%3 = OpConstant %2 0
2045%4 = OpTypeFunction %1
2046%5 = OpTypeBool
2047%6 = OpConstantTrue %5
2048%7 = OpFunction %1 None %4
2049%8 = OpLabel
2050OpSelectionMerge %9 None
2051OpSwitch %3 %10 0 %10 1 %11
2052%10 = OpLabel
2053OpBranch %11
2054%11 = OpLabel
2055OpBranch %9
2056%9 = OpLabel
2057OpReturn
2058OpFunctionEnd
2059)";
2060
2061  CompileSuccessfully(text);
2062  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
2063}
2064
2065TEST_F(ValidateCFG, OpSwitchTargetCannotBeOuterLoopMergeBlock) {
2066  std::string text = R"(
2067OpCapability Shader
2068OpCapability Linkage
2069OpMemoryModel Logical GLSL450
2070
2071%1 = OpTypeVoid
2072%2 = OpTypeFunction %1
2073%3 = OpTypeBool
2074%4 = OpUndef %3
2075%5 = OpTypeInt 32 0
2076%6 = OpConstant %5 0
2077
2078%7 = OpFunction %1 None %2
2079
2080%8 = OpLabel
2081OpBranch %9
2082
2083%9 = OpLabel
2084OpLoopMerge %10 %11 None
2085OpBranch %12
2086
2087%12 = OpLabel
2088OpSelectionMerge %13 None
2089OpSwitch %6 %13 0 %10 1 %14
2090
2091%14 = OpLabel
2092OpBranch %13
2093
2094%13 = OpLabel
2095OpBranch %11
2096
2097%11 = OpLabel
2098OpBranch %9
2099
2100%10 = OpLabel
2101OpReturn
2102
2103OpFunctionEnd
2104)";
2105
2106  CompileSuccessfully(text);
2107  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2108  EXPECT_THAT(
2109      getDiagnosticString(),
2110      HasSubstr(
2111          "Switch header '12[%12]' does not structurally dominate its case construct '10[%10]'\n"
2112          "  %12 = OpLabel"));
2113}
2114
2115TEST_F(ValidateCFG, OpSwitchTargetCannotBeOuterLoopContinueBlock) {
2116  std::string text = R"(
2117OpCapability Shader
2118OpCapability Linkage
2119OpMemoryModel Logical GLSL450
2120
2121%1 = OpTypeVoid
2122%2 = OpTypeFunction %1
2123%3 = OpTypeBool
2124%4 = OpUndef %3
2125%5 = OpTypeInt 32 0
2126%6 = OpConstant %5 0
2127
2128%7 = OpFunction %1 None %2
2129
2130%8 = OpLabel
2131OpBranch %9
2132
2133%9 = OpLabel
2134OpLoopMerge %10 %11 None
2135OpBranch %12
2136
2137%12 = OpLabel
2138OpSelectionMerge %13 None
2139OpSwitch %6 %13 0 %11 1 %14
2140
2141%14 = OpLabel
2142OpBranch %13
2143
2144%13 = OpLabel
2145OpBranch %11
2146
2147%11 = OpLabel
2148OpBranch %9
2149
2150%10 = OpLabel
2151OpReturn
2152
2153OpFunctionEnd
2154)";
2155
2156  CompileSuccessfully(text);
2157  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2158  EXPECT_THAT(
2159      getDiagnosticString(),
2160      HasSubstr(
2161          "Switch header '12[%12]' does not structurally dominate its case construct '11[%11]'\n"
2162          "  %12 = OpLabel"));
2163}
2164
2165TEST_F(ValidateCFG, WrongOperandList) {
2166  std::string text = R"(
2167OpCapability Shader
2168OpCapability Linkage
2169OpMemoryModel Logical GLSL450
2170%1 = OpTypeVoid
2171%2 = OpTypeInt 32 0
2172%3 = OpConstant %2 0
2173%4 = OpTypeFunction %1
2174%5 = OpTypeBool
2175%6 = OpConstantTrue %5
2176%7 = OpFunction %1 None %4
2177%8 = OpLabel
2178OpSelectionMerge %9 None
2179OpSwitch %3 %10 0 %11 1 %12
2180%10 = OpLabel
2181OpBranch %9
2182%12 = OpLabel
2183OpBranch %11
2184%11 = OpLabel
2185OpBranch %9
2186%9 = OpLabel
2187OpReturn
2188OpFunctionEnd
2189)";
2190
2191  CompileSuccessfully(text);
2192  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2193  EXPECT_THAT(
2194      getDiagnosticString(),
2195      HasSubstr(
2196          "Case construct that targets '12[%12]' has branches to the case "
2197          "construct that targets '11[%11]', but does not immediately "
2198          "precede it in the OpSwitch's target list\n"
2199          "  OpSwitch %uint_0 %10 0 %11 1 %12"));
2200}
2201
2202TEST_F(ValidateCFG, WrongOperandListThroughDefault) {
2203  std::string text = R"(
2204OpCapability Shader
2205OpCapability Linkage
2206OpMemoryModel Logical GLSL450
2207%1 = OpTypeVoid
2208%2 = OpTypeInt 32 0
2209%3 = OpConstant %2 0
2210%4 = OpTypeFunction %1
2211%5 = OpTypeBool
2212%6 = OpConstantTrue %5
2213%7 = OpFunction %1 None %4
2214%8 = OpLabel
2215OpSelectionMerge %9 None
2216OpSwitch %3 %10 0 %11 1 %12
2217%10 = OpLabel
2218OpBranch %11
2219%12 = OpLabel
2220OpBranch %10
2221%11 = OpLabel
2222OpBranch %9
2223%9 = OpLabel
2224OpReturn
2225OpFunctionEnd
2226)";
2227
2228  CompileSuccessfully(text);
2229  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2230  EXPECT_THAT(
2231      getDiagnosticString(),
2232      HasSubstr(
2233          "Case construct that targets '12[%12]' has branches to the case "
2234          "construct that targets '11[%11]', but does not immediately "
2235          "precede it in the OpSwitch's target list\n"
2236          "  OpSwitch %uint_0 %10 0 %11 1 %12"));
2237}
2238
2239TEST_F(ValidateCFG, WrongOperandListNotLast) {
2240  std::string text = R"(
2241OpCapability Shader
2242OpCapability Linkage
2243OpMemoryModel Logical GLSL450
2244%1 = OpTypeVoid
2245%2 = OpTypeInt 32 0
2246%3 = OpConstant %2 0
2247%4 = OpTypeFunction %1
2248%5 = OpTypeBool
2249%6 = OpConstantTrue %5
2250%7 = OpFunction %1 None %4
2251%8 = OpLabel
2252OpSelectionMerge %9 None
2253OpSwitch %3 %10 0 %11 1 %12 2 %13
2254%10 = OpLabel
2255OpBranch %9
2256%12 = OpLabel
2257OpBranch %11
2258%11 = OpLabel
2259OpBranch %9
2260%13 = OpLabel
2261OpBranch %9
2262%9 = OpLabel
2263OpReturn
2264OpFunctionEnd
2265)";
2266
2267  CompileSuccessfully(text);
2268  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2269  EXPECT_THAT(
2270      getDiagnosticString(),
2271      HasSubstr(
2272          "Case construct that targets '12[%12]' has branches to the case "
2273          "construct that targets '11[%11]', but does not immediately "
2274          "precede it in the OpSwitch's target list\n"
2275          "  OpSwitch %uint_0 %10 0 %11 1 %12 2 %13"));
2276}
2277
2278TEST_F(ValidateCFG, GoodUnreachableSwitch) {
2279  const std::string text = R"(
2280OpCapability Shader
2281OpMemoryModel Logical GLSL450
2282OpEntryPoint Fragment %2 "main"
2283OpExecutionMode %2 OriginUpperLeft
2284%3 = OpTypeVoid
2285%4 = OpTypeFunction %3
2286%5 = OpTypeBool
2287%6 = OpConstantTrue %5
2288%7 = OpTypeInt 32 1
2289%9 = OpConstant %7 0
2290%2 = OpFunction %3 None %4
2291%10 = OpLabel
2292OpSelectionMerge %11 None
2293OpBranchConditional %6 %12 %13
2294%12 = OpLabel
2295OpReturn
2296%13 = OpLabel
2297OpReturn
2298%11 = OpLabel
2299OpSelectionMerge %14 None
2300OpSwitch %9 %14 0 %15
2301%15 = OpLabel
2302OpBranch %14
2303%14 = OpLabel
2304OpReturn
2305OpFunctionEnd
2306)";
2307
2308  CompileSuccessfully(text);
2309  EXPECT_THAT(SPV_SUCCESS, ValidateInstructions());
2310}
2311
2312TEST_F(ValidateCFG, InvalidCaseExit) {
2313  const std::string text = R"(
2314OpCapability Shader
2315OpMemoryModel Logical GLSL450
2316OpEntryPoint Fragment %1 "func"
2317OpExecutionMode %1 OriginUpperLeft
2318%2 = OpTypeVoid
2319%3 = OpTypeInt 32 0
2320%4 = OpTypeFunction %2
2321%5 = OpConstant %3 0
2322%1 = OpFunction %2 None %4
2323%6 = OpLabel
2324OpSelectionMerge %7 None
2325OpSwitch %5 %7 0 %8 1 %9
2326%8 = OpLabel
2327OpBranch %10
2328%9 = OpLabel
2329OpBranch %10
2330%10 = OpLabel
2331OpReturn
2332%7 = OpLabel
2333OpReturn
2334OpFunctionEnd
2335)";
2336
2337  CompileSuccessfully(text);
2338  ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2339  EXPECT_THAT(
2340      getDiagnosticString(),
2341      HasSubstr("Case construct that targets '8[%8]' has invalid branch "
2342                "to block '10[%10]' (not another case construct, "
2343                "corresponding merge, outer loop merge or outer loop "
2344                "continue)"));
2345}
2346
2347TEST_F(ValidateCFG, GoodCaseExitsToOuterConstructs) {
2348  const std::string text = R"(
2349OpCapability Shader
2350OpMemoryModel Logical GLSL450
2351OpEntryPoint Fragment %func "func"
2352OpExecutionMode %func OriginUpperLeft
2353%void = OpTypeVoid
2354%bool = OpTypeBool
2355%true = OpConstantTrue %bool
2356%int = OpTypeInt 32 0
2357%int0 = OpConstant %int 0
2358%func_ty = OpTypeFunction %void
2359%func = OpFunction %void None %func_ty
2360%1 = OpLabel
2361OpBranch %2
2362%2 = OpLabel
2363OpLoopMerge %7 %6 None
2364OpBranch %3
2365%3 = OpLabel
2366OpSelectionMerge %5 None
2367OpSwitch %int0 %5 0 %4
2368%4 = OpLabel
2369OpBranchConditional %true %6 %7
2370%5 = OpLabel
2371OpBranchConditional %true %6 %7
2372%6 = OpLabel
2373OpBranch %2
2374%7 = OpLabel
2375OpReturn
2376OpFunctionEnd
2377)";
2378
2379  CompileSuccessfully(text);
2380  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
2381}
2382
2383TEST_F(ValidateCFG, SwitchCaseOrderingBad1) {
2384  const std::string text = R"(
2385OpCapability Shader
2386OpCapability Linkage
2387OpMemoryModel Logical GLSL450
2388OpName %default "default"
2389OpName %other "other"
2390%void = OpTypeVoid
2391%int = OpTypeInt 32 0
2392%undef = OpUndef %int
2393%void_fn = OpTypeFunction %void
2394%func = OpFunction %void None %void_fn
2395%entry = OpLabel
2396OpSelectionMerge %merge None
2397OpSwitch %undef %default 0 %other 1 %default
2398%default = OpLabel
2399OpBranch %other
2400%other = OpLabel
2401OpBranch %merge
2402%merge = OpLabel
2403OpReturn
2404OpFunctionEnd
2405)";
2406
2407  CompileSuccessfully(text);
2408  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2409  EXPECT_THAT(
2410      getDiagnosticString(),
2411      HasSubstr("Case construct that targets '1[%default]' has branches to the "
2412                "case construct that targets '2[%other]', but does not "
2413                "immediately precede it in the OpSwitch's target list"));
2414}
2415
2416TEST_F(ValidateCFG, SwitchCaseOrderingBad2) {
2417  const std::string text = R"(
2418OpCapability Shader
2419OpCapability Linkage
2420OpMemoryModel Logical GLSL450
2421OpName %default "default"
2422OpName %other "other"
2423%void = OpTypeVoid
2424%int = OpTypeInt 32 0
2425%undef = OpUndef %int
2426%void_fn = OpTypeFunction %void
2427%func = OpFunction %void None %void_fn
2428%entry = OpLabel
2429OpSelectionMerge %merge None
2430OpSwitch %undef %default 0 %default 1 %other
2431%other = OpLabel
2432OpBranch %default
2433%default = OpLabel
2434OpBranch %merge
2435%merge = OpLabel
2436OpReturn
2437OpFunctionEnd
2438)";
2439
2440  CompileSuccessfully(text);
2441  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2442  EXPECT_THAT(
2443      getDiagnosticString(),
2444      HasSubstr("Case construct that targets '2[%other]' has branches to the "
2445                "case construct that targets '1[%default]', but does not "
2446                "immediately precede it in the OpSwitch's target list"));
2447}
2448
2449TEST_F(ValidateCFG, SwitchMultipleDefaultWithFallThroughGood) {
2450  const std::string text = R"(
2451OpCapability Shader
2452OpCapability Linkage
2453OpMemoryModel Logical GLSL450
2454OpName %first "first"
2455OpName %second "second"
2456OpName %third "third"
2457%void = OpTypeVoid
2458%int = OpTypeInt 32 0
2459%undef = OpUndef %int
2460%void_fn = OpTypeFunction %void
2461%func = OpFunction %void None %void_fn
2462%entry = OpLabel
2463OpSelectionMerge %merge None
2464OpSwitch %undef %second 0 %first 1 %second 2 %third
2465%first = OpLabel
2466OpBranch %second
2467%second = OpLabel
2468OpBranch %third
2469%third = OpLabel
2470OpBranch %merge
2471%merge = OpLabel
2472OpReturn
2473OpFunctionEnd
2474)";
2475
2476  CompileSuccessfully(text);
2477  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2478}
2479
2480TEST_F(ValidateCFG, SwitchMultipleDefaultWithFallThroughBad) {
2481  const std::string text = R"(
2482OpCapability Shader
2483OpCapability Linkage
2484OpMemoryModel Logical GLSL450
2485OpName %first "first"
2486OpName %second "second"
2487OpName %third "third"
2488%void = OpTypeVoid
2489%int = OpTypeInt 32 0
2490%undef = OpUndef %int
2491%void_fn = OpTypeFunction %void
2492%func = OpFunction %void None %void_fn
2493%entry = OpLabel
2494OpSelectionMerge %merge None
2495OpSwitch %undef %second 0 %second 1 %first 2 %third
2496%first = OpLabel
2497OpBranch %second
2498%second = OpLabel
2499OpBranch %third
2500%third = OpLabel
2501OpBranch %merge
2502%merge = OpLabel
2503OpReturn
2504OpFunctionEnd
2505)";
2506
2507  CompileSuccessfully(text);
2508  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2509}
2510
2511TEST_F(ValidateCFG, GoodUnreachableSelection) {
2512  const std::string text = R"(
2513OpCapability Shader
2514%1 = OpExtInstImport "GLSL.std.450"
2515OpMemoryModel Logical GLSL450
2516OpEntryPoint Fragment %main "main"
2517OpExecutionMode %main OriginUpperLeft
2518%void = OpTypeVoid
2519%8 = OpTypeFunction %void
2520%bool = OpTypeBool
2521%false = OpConstantFalse %bool
2522%main = OpFunction %void None %8
2523%15 = OpLabel
2524OpBranch %16
2525%16 = OpLabel
2526OpLoopMerge %17 %18 None
2527OpBranch %19
2528%19 = OpLabel
2529OpBranchConditional %false %21 %17
2530%21 = OpLabel
2531OpSelectionMerge %22 None
2532OpBranchConditional %false %23 %22
2533%23 = OpLabel
2534OpBranch %24
2535%24 = OpLabel
2536OpLoopMerge %25 %26 None
2537OpBranch %27
2538%27 = OpLabel
2539OpReturn
2540%26 = OpLabel
2541OpBranchConditional %false %24 %25
2542%25 = OpLabel
2543OpSelectionMerge %28 None
2544OpBranchConditional %false %18 %28
2545%28 = OpLabel
2546OpBranch %22
2547%22 = OpLabel
2548OpBranch %18
2549%18 = OpLabel
2550OpBranch %16
2551%17 = OpLabel
2552OpReturn
2553OpFunctionEnd
2554)";
2555
2556  CompileSuccessfully(text);
2557  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
2558}
2559
2560TEST_F(ValidateCFG, ShaderWithPhiPtr) {
2561  const std::string text = R"(
2562               OpCapability Shader
2563               OpMemoryModel Logical GLSL450
2564               OpEntryPoint GLCompute %1 "main"
2565               OpExecutionMode %1 LocalSize 1 1 1
2566               OpSource HLSL 600
2567       %bool = OpTypeBool
2568%_ptr_Function_bool = OpTypePointer Function %bool
2569       %void = OpTypeVoid
2570          %5 = OpTypeFunction %void
2571          %1 = OpFunction %void None %5
2572          %6 = OpLabel
2573          %7 = OpVariable %_ptr_Function_bool Function
2574          %8 = OpVariable %_ptr_Function_bool Function
2575          %9 = OpUndef %bool
2576               OpSelectionMerge %10 None
2577               OpBranchConditional %9 %11 %10
2578         %11 = OpLabel
2579               OpBranch %10
2580         %10 = OpLabel
2581         %12 = OpPhi %_ptr_Function_bool %7 %6 %8 %11
2582               OpReturn
2583               OpFunctionEnd
2584)";
2585
2586  CompileSuccessfully(text);
2587  EXPECT_EQ(SPV_ERROR_INVALID_DATA, ValidateInstructions());
2588  EXPECT_THAT(getDiagnosticString(),
2589              HasSubstr("Using pointers with OpPhi requires capability "
2590                        "VariablePointers or VariablePointersStorageBuffer"));
2591}
2592
2593TEST_F(ValidateCFG, VarPtrShaderWithPhiPtr) {
2594  const std::string text = R"(
2595               OpCapability Shader
2596               OpCapability VariablePointers
2597               OpExtension "SPV_KHR_variable_pointers"
2598               OpMemoryModel Logical GLSL450
2599               OpEntryPoint GLCompute %1 "main"
2600               OpExecutionMode %1 LocalSize 1 1 1
2601               OpSource HLSL 600
2602       %bool = OpTypeBool
2603%_ptr_Function_bool = OpTypePointer Function %bool
2604       %void = OpTypeVoid
2605          %5 = OpTypeFunction %void
2606          %1 = OpFunction %void None %5
2607          %6 = OpLabel
2608          %7 = OpVariable %_ptr_Function_bool Function
2609          %8 = OpVariable %_ptr_Function_bool Function
2610          %9 = OpUndef %bool
2611               OpSelectionMerge %10 None
2612               OpBranchConditional %9 %11 %10
2613         %11 = OpLabel
2614               OpBranch %10
2615         %10 = OpLabel
2616         %12 = OpPhi %_ptr_Function_bool %7 %6 %8 %11
2617               OpReturn
2618               OpFunctionEnd
2619)";
2620
2621  CompileSuccessfully(text);
2622  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2623}
2624
2625TEST_F(ValidateCFG, VarPtrStgBufShaderWithPhiStgBufPtr) {
2626  const std::string text = R"(
2627               OpCapability Shader
2628               OpCapability VariablePointersStorageBuffer
2629               OpExtension "SPV_KHR_variable_pointers"
2630               OpMemoryModel Logical GLSL450
2631               OpEntryPoint GLCompute %1 "main"
2632               OpExecutionMode %1 LocalSize 1 1 1
2633               OpSource HLSL 600
2634       %bool = OpTypeBool
2635       %float = OpTypeFloat 32
2636%_ptr_StorageBuffer_float = OpTypePointer StorageBuffer %float
2637          %7 = OpVariable %_ptr_StorageBuffer_float StorageBuffer
2638          %8 = OpVariable %_ptr_StorageBuffer_float StorageBuffer
2639       %void = OpTypeVoid
2640          %5 = OpTypeFunction %void
2641          %1 = OpFunction %void None %5
2642          %6 = OpLabel
2643          %9 = OpUndef %bool
2644               OpSelectionMerge %10 None
2645               OpBranchConditional %9 %11 %10
2646         %11 = OpLabel
2647               OpBranch %10
2648         %10 = OpLabel
2649         %12 = OpPhi %_ptr_StorageBuffer_float %7 %6 %8 %11
2650               OpReturn
2651               OpFunctionEnd
2652)";
2653
2654  CompileSuccessfully(text);
2655  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2656}
2657
2658TEST_F(ValidateCFG, KernelWithPhiPtr) {
2659  const std::string text = R"(
2660               OpCapability Kernel
2661               OpCapability Addresses
2662               OpMemoryModel Physical32 OpenCL
2663               OpEntryPoint Kernel %1 "main"
2664               OpExecutionMode %1 LocalSize 1 1 1
2665               OpSource HLSL 600
2666       %bool = OpTypeBool
2667%_ptr_Function_bool = OpTypePointer Function %bool
2668       %void = OpTypeVoid
2669          %5 = OpTypeFunction %void
2670          %1 = OpFunction %void None %5
2671          %6 = OpLabel
2672          %7 = OpVariable %_ptr_Function_bool Function
2673          %8 = OpVariable %_ptr_Function_bool Function
2674          %9 = OpUndef %bool
2675               OpSelectionMerge %10 None
2676               OpBranchConditional %9 %11 %10
2677         %11 = OpLabel
2678               OpBranch %10
2679         %10 = OpLabel
2680         %12 = OpPhi %_ptr_Function_bool %7 %6 %8 %11
2681               OpReturn
2682               OpFunctionEnd
2683)";
2684
2685  CompileSuccessfully(text);
2686  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2687}
2688
2689TEST_F(ValidateCFG, SwitchTargetMustBeLabel) {
2690  const std::string text = R"(
2691               OpCapability Shader
2692               OpMemoryModel Logical GLSL450
2693               OpEntryPoint GLCompute %1 "foo"
2694       %uint = OpTypeInt 32 0
2695     %uint_0 = OpConstant %uint 0
2696       %void = OpTypeVoid
2697          %5 = OpTypeFunction %void
2698          %1 = OpFunction %void None %5
2699          %6 = OpLabel
2700          %7 = OpCopyObject %uint %uint_0
2701               OpSelectionMerge %8 None
2702               OpSwitch %uint_0 %8 0 %7
2703          %8 = OpLabel
2704               OpReturn
2705               OpFunctionEnd
2706)";
2707
2708  CompileSuccessfully(text);
2709  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
2710  EXPECT_THAT(getDiagnosticString(),
2711              HasSubstr("'Target Label' operands for OpSwitch must "
2712                        "be IDs of an OpLabel instruction"));
2713}
2714
2715TEST_F(ValidateCFG, BranchTargetMustBeLabel) {
2716  const std::string text = R"(
2717               OpCapability Shader
2718               OpMemoryModel Logical GLSL450
2719               OpEntryPoint GLCompute %1 "foo"
2720       %uint = OpTypeInt 32 0
2721     %uint_0 = OpConstant %uint 0
2722       %void = OpTypeVoid
2723          %5 = OpTypeFunction %void
2724          %1 = OpFunction %void None %5
2725          %2 = OpLabel
2726          %7 = OpCopyObject %uint %uint_0
2727               OpBranch %7
2728          %8 = OpLabel
2729               OpReturn
2730               OpFunctionEnd
2731)";
2732
2733  CompileSuccessfully(text);
2734  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
2735  EXPECT_THAT(getDiagnosticString(),
2736              HasSubstr("'Target Label' operands for OpBranch must "
2737                        "be the ID of an OpLabel instruction"));
2738}
2739
2740TEST_F(ValidateCFG, ReachableOpUnreachableOneBlock) {
2741  const std::string text = R"(
2742OpCapability Shader
2743OpCapability Linkage
2744OpMemoryModel Logical GLSL450
2745%void = OpTypeVoid
2746%void_fn = OpTypeFunction %void
2747%func = OpFunction %void None %void_fn
2748%entry = OpLabel
2749OpUnreachable
2750OpFunctionEnd
2751)";
2752
2753  CompileSuccessfully(text);
2754  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2755}
2756
2757TEST_F(ValidateCFG, ReachableOpUnreachableOpBranch) {
2758  const std::string text = R"(
2759OpCapability Shader
2760OpCapability Linkage
2761OpMemoryModel Logical GLSL450
2762%void = OpTypeVoid
2763%void_fn = OpTypeFunction %void
2764%func = OpFunction %void None %void_fn
2765%entry = OpLabel
2766OpBranch %block
2767%block = OpLabel
2768OpUnreachable
2769OpFunctionEnd
2770)";
2771
2772  CompileSuccessfully(text);
2773  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2774}
2775
2776TEST_F(ValidateCFG, ReachableOpUnreachableOpBranchConditional) {
2777  const std::string text = R"(
2778OpCapability Shader
2779OpCapability Linkage
2780OpMemoryModel Logical GLSL450
2781%void = OpTypeVoid
2782%void_fn = OpTypeFunction %void
2783%bool = OpTypeBool
2784%undef = OpUndef %bool
2785%func = OpFunction %void None %void_fn
2786%entry = OpLabel
2787OpSelectionMerge %block None
2788OpBranchConditional %undef %block %unreachable
2789%block = OpLabel
2790OpReturn
2791%unreachable = OpLabel
2792OpUnreachable
2793OpFunctionEnd
2794)";
2795
2796  CompileSuccessfully(text);
2797  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2798}
2799
2800TEST_F(ValidateCFG, ReachableOpUnreachableOpSwitch) {
2801  const std::string text = R"(
2802OpCapability Shader
2803OpCapability Linkage
2804OpMemoryModel Logical GLSL450
2805%void = OpTypeVoid
2806%void_fn = OpTypeFunction %void
2807%int = OpTypeInt 32 0
2808%undef = OpUndef %int
2809%func = OpFunction %void None %void_fn
2810%entry = OpLabel
2811OpSelectionMerge %block1 None
2812OpSwitch %undef %block1 0 %unreachable 1 %block2
2813%block1 = OpLabel
2814OpReturn
2815%unreachable = OpLabel
2816OpUnreachable
2817%block2 = OpLabel
2818OpReturn
2819OpFunctionEnd
2820)";
2821
2822  CompileSuccessfully(text);
2823  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2824}
2825
2826TEST_F(ValidateCFG, ReachableOpUnreachableLoop) {
2827  const std::string text = R"(
2828OpCapability Shader
2829OpCapability Linkage
2830OpMemoryModel Logical GLSL450
2831%void = OpTypeVoid
2832%void_fn = OpTypeFunction %void
2833%bool = OpTypeBool
2834%undef = OpUndef %bool
2835%func = OpFunction %void None %void_fn
2836%entry = OpLabel
2837OpBranch %loop
2838%loop = OpLabel
2839OpLoopMerge %unreachable %loop None
2840OpBranchConditional %undef %loop %unreachable
2841%unreachable = OpLabel
2842OpUnreachable
2843OpFunctionEnd
2844)";
2845
2846  CompileSuccessfully(text);
2847  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2848}
2849
2850TEST_F(ValidateCFG, UnreachableLoopBadBackedge) {
2851  const std::string text = R"(
2852OpCapability Shader
2853OpMemoryModel Logical GLSL450
2854OpEntryPoint Fragment %2 "main"
2855OpExecutionMode %2 OriginUpperLeft
2856%4 = OpTypeVoid
2857%5 = OpTypeFunction %4
2858%8 = OpTypeBool
2859%13 = OpConstantTrue %8
2860%2 = OpFunction %4 None %5
2861%14 = OpLabel
2862OpSelectionMerge %15 None
2863OpBranchConditional %13 %15 %15
2864%16 = OpLabel
2865OpLoopMerge %17 %18 None
2866OpBranch %17
2867%18 = OpLabel
2868OpBranch %17
2869%17 = OpLabel
2870OpBranch %15
2871%15 = OpLabel
2872OpReturn
2873OpFunctionEnd
2874)";
2875
2876  // The back-edge in this test is bad, but the validator fails to identify it
2877  // because it is in an entirely unreachable section of code. Prior to #2488
2878  // this code failed an assert in Construct::blocks().
2879  CompileSuccessfully(text);
2880  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
2881}
2882
2883TEST_F(ValidateCFG, OneContinueTwoBackedges) {
2884  const std::string text = R"(
2885OpCapability Shader
2886OpMemoryModel Logical GLSL450
2887OpEntryPoint GLCompute %1 "main"
2888OpExecutionMode %1 LocalSize 1 1 1
2889%void = OpTypeVoid
2890%bool = OpTypeBool
2891%true = OpConstantTrue %bool
2892%5 = OpTypeFunction %void
2893%1 = OpFunction %void None %5
2894%6 = OpLabel
2895OpBranch %7
2896%7 = OpLabel
2897OpLoopMerge %8 %9 None
2898OpBranch %10
2899%10 = OpLabel
2900OpLoopMerge %11 %9 None
2901OpBranchConditional %true %11 %9
2902%9 = OpLabel
2903OpBranchConditional %true %10 %7
2904%11 = OpLabel
2905OpBranch %8
2906%8 = OpLabel
2907OpReturn
2908OpFunctionEnd
2909)";
2910
2911  CompileSuccessfully(text);
2912  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
2913  EXPECT_THAT(getDiagnosticString(),
2914              HasSubstr("Back-edges ('10[%10]' -> '9[%9]') can only be formed "
2915                        "between a block and a loop header"));
2916}
2917
2918TEST_F(ValidateCFG, LoopMergeMergeBlockNotLabel) {
2919  const std::string text = R"(
2920OpCapability Shader
2921OpCapability Linkage
2922OpMemoryModel Logical GLSL450
2923OpName %undef "undef"
2924%void = OpTypeVoid
2925%bool = OpTypeBool
2926%undef = OpUndef %bool
2927%void_fn = OpTypeFunction %void
2928%func = OpFunction %void None %void_fn
2929%1 = OpLabel
2930OpLoopMerge %undef %2 None
2931OpBranchConditional %undef %2 %2
2932%2 = OpLabel
2933OpReturn
2934OpFunctionEnd
2935)";
2936
2937  CompileSuccessfully(text);
2938  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
2939  EXPECT_THAT(getDiagnosticString(),
2940              HasSubstr("Merge Block '1[%undef]' must be an OpLabel"));
2941}
2942
2943TEST_F(ValidateCFG, LoopMergeContinueTargetNotLabel) {
2944  const std::string text = R"(
2945OpCapability Shader
2946OpCapability Linkage
2947OpMemoryModel Logical GLSL450
2948OpName %undef "undef"
2949%void = OpTypeVoid
2950%bool = OpTypeBool
2951%undef = OpUndef %bool
2952%void_fn = OpTypeFunction %void
2953%func = OpFunction %void None %void_fn
2954%1 = OpLabel
2955OpLoopMerge %2 %undef None
2956OpBranchConditional %undef %2 %2
2957%2 = OpLabel
2958OpReturn
2959OpFunctionEnd
2960)";
2961
2962  CompileSuccessfully(text);
2963  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
2964  EXPECT_THAT(getDiagnosticString(),
2965              HasSubstr("Continue Target '1[%undef]' must be an OpLabel"));
2966}
2967
2968TEST_F(ValidateCFG, LoopMergeMergeBlockContinueTargetSameLabel) {
2969  const std::string text = R"(
2970OpCapability Shader
2971OpCapability Linkage
2972OpMemoryModel Logical GLSL450
2973OpName %undef "undef"
2974%void = OpTypeVoid
2975%bool = OpTypeBool
2976%undef = OpUndef %bool
2977%void_fn = OpTypeFunction %void
2978%func = OpFunction %void None %void_fn
2979%1 = OpLabel
2980OpLoopMerge %2 %2 None
2981OpBranchConditional %undef %2 %2
2982%2 = OpLabel
2983OpReturn
2984OpFunctionEnd
2985)";
2986
2987  CompileSuccessfully(text);
2988  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
2989  EXPECT_THAT(
2990      getDiagnosticString(),
2991      HasSubstr("Merge Block and Continue Target must be different ids"));
2992}
2993
2994TEST_F(ValidateCFG, LoopMergeUnrollAndDontUnroll) {
2995  const std::string text = R"(
2996OpCapability Shader
2997OpCapability Linkage
2998OpMemoryModel Logical GLSL450
2999OpName %undef "undef"
3000%void = OpTypeVoid
3001%bool = OpTypeBool
3002%undef = OpUndef %bool
3003%void_fn = OpTypeFunction %void
3004%func = OpFunction %void None %void_fn
3005%5 = OpLabel
3006OpBranch %1
3007%1 = OpLabel
3008OpLoopMerge %2 %3 Unroll|DontUnroll
3009OpBranchConditional %undef %2 %3
3010%3 = OpLabel
3011OpBranch %1
3012%2 = OpLabel
3013OpReturn
3014OpFunctionEnd
3015)";
3016
3017  CompileSuccessfully(text);
3018  EXPECT_EQ(SPV_ERROR_INVALID_DATA, ValidateInstructions());
3019  EXPECT_THAT(
3020      getDiagnosticString(),
3021      HasSubstr(
3022          "Unroll and DontUnroll loop controls must not both be specified"));
3023}
3024
3025TEST_F(ValidateCFG, LoopMergePeelCountAndDontUnroll) {
3026  const std::string text = R"(
3027OpCapability Shader
3028OpCapability Linkage
3029OpMemoryModel Logical GLSL450
3030OpName %undef "undef"
3031%void = OpTypeVoid
3032%bool = OpTypeBool
3033%undef = OpUndef %bool
3034%void_fn = OpTypeFunction %void
3035%func = OpFunction %void None %void_fn
3036%5 = OpLabel
3037OpBranch %1
3038%1 = OpLabel
3039OpLoopMerge %2 %3 DontUnroll|PeelCount 1
3040OpBranchConditional %undef %2 %3
3041%3 = OpLabel
3042OpBranch %1
3043%2 = OpLabel
3044OpReturn
3045OpFunctionEnd
3046)";
3047
3048  CompileSuccessfully(text, SPV_ENV_UNIVERSAL_1_4);
3049  EXPECT_EQ(SPV_ERROR_INVALID_DATA,
3050            ValidateInstructions(SPV_ENV_UNIVERSAL_1_4));
3051  EXPECT_THAT(
3052      getDiagnosticString(),
3053      HasSubstr(
3054          "PeelCount and DontUnroll loop controls must not both be specified"));
3055}
3056
3057TEST_F(ValidateCFG, LoopMergePartialCountAndDontUnroll) {
3058  const std::string text = R"(
3059OpCapability Shader
3060OpCapability Linkage
3061OpMemoryModel Logical GLSL450
3062OpName %undef "undef"
3063%void = OpTypeVoid
3064%bool = OpTypeBool
3065%undef = OpUndef %bool
3066%void_fn = OpTypeFunction %void
3067%func = OpFunction %void None %void_fn
3068%5 = OpLabel
3069OpBranch %1
3070%1 = OpLabel
3071OpLoopMerge %2 %3 DontUnroll|PartialCount 1
3072OpBranchConditional %undef %2 %3
3073%3 = OpLabel
3074OpBranch %1
3075%2 = OpLabel
3076OpReturn
3077OpFunctionEnd
3078)";
3079
3080  CompileSuccessfully(text, SPV_ENV_UNIVERSAL_1_4);
3081  EXPECT_EQ(SPV_ERROR_INVALID_DATA,
3082            ValidateInstructions(SPV_ENV_UNIVERSAL_1_4));
3083  EXPECT_THAT(getDiagnosticString(),
3084              HasSubstr("PartialCount and DontUnroll loop controls must not "
3085                        "both be specified"));
3086}
3087
3088TEST_F(ValidateCFG, LoopMergeIterationMultipleZero) {
3089  const std::string text = R"(
3090OpCapability Shader
3091OpCapability Linkage
3092OpMemoryModel Logical GLSL450
3093OpName %undef "undef"
3094%void = OpTypeVoid
3095%bool = OpTypeBool
3096%undef = OpUndef %bool
3097%void_fn = OpTypeFunction %void
3098%func = OpFunction %void None %void_fn
3099%5 = OpLabel
3100OpBranch %1
3101%1 = OpLabel
3102OpLoopMerge %2 %3 IterationMultiple 0
3103OpBranchConditional %undef %2 %3
3104%3 = OpLabel
3105OpBranch %1
3106%2 = OpLabel
3107OpReturn
3108OpFunctionEnd
3109)";
3110
3111  CompileSuccessfully(text, SPV_ENV_UNIVERSAL_1_4);
3112  EXPECT_EQ(SPV_ERROR_INVALID_DATA,
3113            ValidateInstructions(SPV_ENV_UNIVERSAL_1_4));
3114  EXPECT_THAT(
3115      getDiagnosticString(),
3116      HasSubstr(
3117          "IterationMultiple loop control operand must be greater than zero"));
3118}
3119
3120TEST_F(ValidateCFG, LoopMergeIterationMultipleZeroMoreOperands) {
3121  const std::string text = R"(
3122OpCapability Shader
3123OpCapability Linkage
3124OpMemoryModel Logical GLSL450
3125OpName %undef "undef"
3126%void = OpTypeVoid
3127%bool = OpTypeBool
3128%undef = OpUndef %bool
3129%void_fn = OpTypeFunction %void
3130%func = OpFunction %void None %void_fn
3131%5 = OpLabel
3132OpBranch %1
3133%1 = OpLabel
3134OpLoopMerge %2 %3 MaxIterations|IterationMultiple 4 0
3135OpBranchConditional %undef %2 %3
3136%3 = OpLabel
3137OpBranch %1
3138%2 = OpLabel
3139OpReturn
3140OpFunctionEnd
3141)";
3142
3143  CompileSuccessfully(text, SPV_ENV_UNIVERSAL_1_4);
3144  EXPECT_EQ(SPV_ERROR_INVALID_DATA,
3145            ValidateInstructions(SPV_ENV_UNIVERSAL_1_4));
3146  EXPECT_THAT(
3147      getDiagnosticString(),
3148      HasSubstr(
3149          "IterationMultiple loop control operand must be greater than zero"));
3150}
3151
3152TEST_F(ValidateCFG, LoopMergeTargetsHeader) {
3153  const std::string text = R"(
3154OpCapability Shader
3155OpCapability Linkage
3156OpMemoryModel Logical GLSL450
3157%void = OpTypeVoid
3158%bool = OpTypeBool
3159%undef = OpUndef %bool
3160%void_fn = OpTypeFunction %void
3161%fn = OpFunction %void None %void_fn
3162%entry = OpLabel
3163OpBranch %loop
3164%loop = OpLabel
3165OpLoopMerge %loop %continue None
3166OpBranch %body
3167%continue = OpLabel
3168OpBranch %loop
3169%body = OpLabel
3170OpReturn
3171OpFunctionEnd
3172)";
3173
3174  CompileSuccessfully(text);
3175  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
3176  EXPECT_THAT(
3177      getDiagnosticString(),
3178      HasSubstr("Merge Block may not be the block containing the OpLoopMerge"));
3179}
3180
3181TEST_F(ValidateCFG, InvalidSelectionExit) {
3182  const std::string text = R"(
3183OpCapability Shader
3184OpMemoryModel Logical GLSL450
3185OpEntryPoint Fragment %1 "main"
3186OpExecutionMode %1 OriginUpperLeft
3187%2 = OpTypeVoid
3188%3 = OpTypeBool
3189%4 = OpConstantTrue %3
3190%5 = OpTypeFunction %2
3191%1 = OpFunction %2 None %5
3192%6 = OpLabel
3193OpSelectionMerge %7 None
3194OpBranchConditional %4 %7 %8
3195%8 = OpLabel
3196OpSelectionMerge %9 None
3197OpBranchConditional %4 %10 %9
3198%10 = OpLabel
3199OpBranch %7
3200%9 = OpLabel
3201OpBranch %7
3202%7 = OpLabel
3203OpReturn
3204OpFunctionEnd
3205)";
3206
3207  CompileSuccessfully(text);
3208  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3209  EXPECT_THAT(
3210      getDiagnosticString(),
3211      HasSubstr("block <ID> '10[%10]' exits the selection headed by <ID> "
3212                "'8[%8]', but not via a structured exit"));
3213}
3214
3215TEST_F(ValidateCFG, InvalidLoopExit) {
3216  const std::string text = R"(
3217OpCapability Shader
3218OpMemoryModel Logical GLSL450
3219OpEntryPoint Fragment %1 "main"
3220OpExecutionMode %1 OriginUpperLeft
3221%2 = OpTypeVoid
3222%3 = OpTypeBool
3223%4 = OpConstantTrue %3
3224%5 = OpTypeFunction %2
3225%1 = OpFunction %2 None %5
3226%6 = OpLabel
3227OpSelectionMerge %7 None
3228OpBranchConditional %4 %7 %8
3229%8 = OpLabel
3230OpLoopMerge %9 %10 None
3231OpBranchConditional %4 %9 %11
3232%11 = OpLabel
3233OpBranchConditional %4 %7 %10
3234%10 = OpLabel
3235OpBranch %8
3236%9 = OpLabel
3237OpBranch %7
3238%7 = OpLabel
3239OpReturn
3240OpFunctionEnd
3241)";
3242
3243  CompileSuccessfully(text);
3244  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3245  EXPECT_THAT(getDiagnosticString(),
3246              HasSubstr("block <ID> '11[%11]' exits the loop headed by <ID> "
3247                        "'8[%8]', but not via a structured exit"));
3248}
3249
3250TEST_F(ValidateCFG, InvalidContinueExit) {
3251  const std::string text = R"(
3252OpCapability Shader
3253OpMemoryModel Logical GLSL450
3254OpEntryPoint Fragment %1 "main"
3255OpExecutionMode %1 OriginUpperLeft
3256%2 = OpTypeVoid
3257%3 = OpTypeBool
3258%4 = OpConstantTrue %3
3259%5 = OpTypeFunction %2
3260%1 = OpFunction %2 None %5
3261%6 = OpLabel
3262OpSelectionMerge %7 None
3263OpBranchConditional %4 %7 %8
3264%8 = OpLabel
3265OpLoopMerge %9 %10 None
3266OpBranchConditional %4 %9 %10
3267%10 = OpLabel
3268OpBranch %11
3269%11 = OpLabel
3270OpBranchConditional %4 %8 %7
3271%9 = OpLabel
3272OpBranch %7
3273%7 = OpLabel
3274OpReturn
3275OpFunctionEnd
3276)";
3277
3278  CompileSuccessfully(text);
3279  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3280  EXPECT_THAT(
3281      getDiagnosticString(),
3282      HasSubstr("block <ID> '11[%11]' exits the continue headed by <ID> "
3283                "'10[%10]', but not via a structured exit"));
3284}
3285
3286TEST_F(ValidateCFG, InvalidSelectionExitBackedge) {
3287  const std::string text = R"(
3288OpCapability Shader
3289OpCapability Linkage
3290OpMemoryModel Logical GLSL450
3291%1 = OpTypeVoid
3292%2 = OpTypeBool
3293%3 = OpUndef %2
3294%4 = OpTypeFunction %1
3295%5 = OpFunction %1 None %4
3296%6 = OpLabel
3297OpBranch %7
3298%7 = OpLabel
3299OpLoopMerge %8 %9 None
3300OpBranchConditional %3 %8 %9
3301%9 = OpLabel
3302OpSelectionMerge %10 None
3303OpBranchConditional %3 %11 %12
3304%11 = OpLabel
3305OpBranch %13
3306%12 = OpLabel
3307OpBranch %13
3308%13 = OpLabel
3309OpBranch %7
3310%10 = OpLabel
3311OpUnreachable
3312%8 = OpLabel
3313OpReturn
3314OpFunctionEnd
3315)";
3316
3317  CompileSuccessfully(text);
3318  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3319  EXPECT_THAT(
3320      getDiagnosticString(),
3321      HasSubstr(
3322          "The continue construct with the continue target '9[%9]' is not "
3323          "structurally post dominated by the back-edge block '13[%13]'"));
3324}
3325
3326TEST_F(ValidateCFG, BreakFromSwitch) {
3327  const std::string text = R"(
3328OpCapability Shader
3329OpCapability Linkage
3330OpMemoryModel Logical GLSL450
3331%1 = OpTypeVoid
3332%2 = OpTypeBool
3333%3 = OpTypeInt 32 0
3334%4 = OpUndef %2
3335%5 = OpUndef %3
3336%6 = OpTypeFunction %1
3337%7 = OpFunction %1 None %6
3338%8 = OpLabel
3339OpSelectionMerge %9 None
3340OpSwitch %5 %9 0 %10
3341%10 = OpLabel
3342OpSelectionMerge %11 None
3343OpBranchConditional %4 %11 %12
3344%12 = OpLabel
3345OpBranch %9
3346%11 = OpLabel
3347OpBranch %9
3348%9 = OpLabel
3349OpReturn
3350OpFunctionEnd
3351)";
3352
3353  CompileSuccessfully(text);
3354  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
3355}
3356
3357TEST_F(ValidateCFG, InvalidBreakFromSwitch) {
3358  const std::string text = R"(
3359OpCapability Shader
3360OpCapability Linkage
3361OpMemoryModel Logical GLSL450
3362%1 = OpTypeVoid
3363%2 = OpTypeBool
3364%3 = OpTypeInt 32 0
3365%4 = OpUndef %2
3366%5 = OpUndef %3
3367%6 = OpTypeFunction %1
3368%7 = OpFunction %1 None %6
3369%8 = OpLabel
3370OpSelectionMerge %9 None
3371OpSwitch %5 %9 0 %10
3372%10 = OpLabel
3373OpSelectionMerge %11 None
3374OpSwitch %5 %11 0 %12
3375%12 = OpLabel
3376OpBranch %9
3377%11 = OpLabel
3378OpBranch %9
3379%9 = OpLabel
3380OpReturn
3381OpFunctionEnd
3382)";
3383
3384  CompileSuccessfully(text);
3385  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3386  EXPECT_THAT(
3387      getDiagnosticString(),
3388      HasSubstr("block <ID> '12[%12]' exits the selection headed by <ID> "
3389                "'10[%10]', but not via a structured exit"));
3390}
3391
3392TEST_F(ValidateCFG, BreakToOuterSwitch) {
3393  const std::string text = R"(
3394OpCapability Shader
3395OpCapability Linkage
3396OpMemoryModel Logical GLSL450
3397%1 = OpTypeVoid
3398%2 = OpTypeBool
3399%3 = OpTypeInt 32 0
3400%4 = OpUndef %2
3401%5 = OpUndef %3
3402%6 = OpTypeFunction %1
3403%7 = OpFunction %1 None %6
3404%8 = OpLabel
3405OpSelectionMerge %9 None
3406OpSwitch %5 %9 0 %10
3407%10 = OpLabel
3408OpSelectionMerge %11 None
3409OpSwitch %5 %11 0 %12
3410%12 = OpLabel
3411OpSelectionMerge %13 None
3412OpBranchConditional %4 %13 %14
3413%14 = OpLabel
3414OpBranch %9
3415%13 = OpLabel
3416OpBranch %11
3417%11 = OpLabel
3418OpBranch %9
3419%9 = OpLabel
3420OpReturn
3421OpFunctionEnd
3422)";
3423
3424  CompileSuccessfully(text);
3425  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3426  EXPECT_THAT(
3427      getDiagnosticString(),
3428      HasSubstr("block <ID> '14[%14]' exits the selection headed by <ID> "
3429                "'10[%10]', but not via a structured exit"));
3430}
3431
3432TEST_F(ValidateCFG, BreakToOuterLoop) {
3433  const std::string text = R"(
3434OpCapability Shader
3435OpCapability Linkage
3436OpMemoryModel Logical GLSL450
3437%1 = OpTypeVoid
3438%2 = OpTypeBool
3439%3 = OpUndef %2
3440%4 = OpTypeFunction %1
3441%5 = OpFunction %1 None %4
3442%6 = OpLabel
3443OpBranch %7
3444%7 = OpLabel
3445OpLoopMerge %8 %9 None
3446OpBranch %10
3447%10 = OpLabel
3448OpLoopMerge %11 %12 None
3449OpBranch %13
3450%13 = OpLabel
3451OpSelectionMerge %14 None
3452OpBranchConditional %3 %14 %15
3453%15 = OpLabel
3454OpBranch %8
3455%14 = OpLabel
3456OpBranch %12
3457%12 = OpLabel
3458OpBranchConditional %3 %10 %11
3459%11 = OpLabel
3460OpBranch %9
3461%9 = OpLabel
3462OpBranchConditional %3 %7 %8
3463%8 = OpLabel
3464OpReturn
3465OpFunctionEnd
3466)";
3467
3468  CompileSuccessfully(text);
3469  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3470  EXPECT_THAT(getDiagnosticString(),
3471              HasSubstr("block <ID> '15[%15]' exits the loop headed by <ID> "
3472                        "'10[%10]', but not via a structured exit"));
3473}
3474
3475TEST_F(ValidateCFG, ContinueFromNestedSelection) {
3476  const std::string text = R"(
3477OpCapability Shader
3478OpCapability Linkage
3479OpMemoryModel Logical GLSL450
3480%void = OpTypeVoid
3481%void_fn = OpTypeFunction %void
3482%bool = OpTypeBool
3483%undef = OpUndef %bool
3484%4 = OpFunction %void None %void_fn
3485%5 = OpLabel
3486OpBranch %48
3487%48 = OpLabel
3488OpLoopMerge %47 %50 None
3489OpBranch %10
3490%10 = OpLabel
3491OpLoopMerge %12 %37 None
3492OpBranchConditional %undef %11 %12
3493%11 = OpLabel
3494OpSelectionMerge %31 None
3495OpBranchConditional %undef %30 %31
3496%30 = OpLabel
3497OpSelectionMerge %38 None
3498OpBranchConditional %undef %36 %38
3499%36 = OpLabel
3500OpBranch %38
3501%38 = OpLabel
3502OpBranch %37
3503%37 = OpLabel
3504OpBranch %10
3505%31 = OpLabel
3506OpBranch %12
3507%12 = OpLabel
3508OpSelectionMerge %55 None
3509OpBranchConditional %undef %47 %55
3510%55 = OpLabel
3511OpBranch %47
3512%50 = OpLabel
3513OpBranch %48
3514%47 = OpLabel
3515OpReturn
3516OpFunctionEnd
3517)";
3518
3519  CompileSuccessfully(text);
3520  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
3521}
3522
3523TEST_F(ValidateCFG, MissingMergeConditionalBranchBad) {
3524  const std::string text = R"(
3525OpCapability Shader
3526OpCapability Linkage
3527OpMemoryModel Logical GLSL450
3528%void = OpTypeVoid
3529%void_fn = OpTypeFunction %void
3530%bool = OpTypeBool
3531%undef = OpUndef %bool
3532%func = OpFunction %void None %void_fn
3533%entry = OpLabel
3534OpBranchConditional %undef %then %else
3535%then = OpLabel
3536OpReturn
3537%else = OpLabel
3538OpReturn
3539OpFunctionEnd
3540)";
3541
3542  CompileSuccessfully(text);
3543  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3544  EXPECT_THAT(getDiagnosticString(), HasSubstr("Selection must be structured"));
3545}
3546
3547TEST_F(ValidateCFG, LoopConditionalBranchWithoutExitBad) {
3548  const std::string text = R"(
3549OpCapability Shader
3550OpCapability Linkage
3551OpMemoryModel Logical GLSL450
3552%void = OpTypeVoid
3553%void_fn = OpTypeFunction %void
3554%bool = OpTypeBool
3555%undef = OpUndef %bool
3556%func = OpFunction %void None %void_fn
3557%entry = OpLabel
3558OpBranch %loop
3559%loop = OpLabel
3560OpLoopMerge %exit %continue None
3561OpBranchConditional %undef %then %else
3562%then = OpLabel
3563OpBranch %continue
3564%else = OpLabel
3565OpBranch %exit
3566%continue = OpLabel
3567OpBranch %loop
3568%exit = OpLabel
3569OpReturn
3570OpFunctionEnd
3571)";
3572
3573  CompileSuccessfully(text);
3574  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3575  EXPECT_THAT(getDiagnosticString(), HasSubstr("Selection must be structured"));
3576}
3577
3578TEST_F(ValidateCFG, MissingMergeSwitchBad) {
3579  const std::string text = R"(
3580OpCapability Shader
3581OpCapability Linkage
3582OpMemoryModel Logical GLSL450
3583%void = OpTypeVoid
3584%void_fn = OpTypeFunction %void
3585%int = OpTypeInt 32 0
3586%undef = OpUndef %int
3587%func = OpFunction %void None %void_fn
3588%entry = OpLabel
3589OpSwitch %undef %then 0 %else
3590%then = OpLabel
3591OpReturn
3592%else = OpLabel
3593OpReturn
3594OpFunctionEnd
3595)";
3596
3597  CompileSuccessfully(text);
3598  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3599  EXPECT_THAT(
3600      getDiagnosticString(),
3601      HasSubstr(
3602          "OpSwitch must be preceded by an OpSelectionMerge instruction"));
3603}
3604
3605TEST_F(ValidateCFG, MissingMergeSwitchBad2) {
3606  const std::string text = R"(
3607OpCapability Shader
3608OpCapability Linkage
3609OpMemoryModel Logical GLSL450
3610%void = OpTypeVoid
3611%void_fn = OpTypeFunction %void
3612%int = OpTypeInt 32 0
3613%undef = OpUndef %int
3614%func = OpFunction %void None %void_fn
3615%entry = OpLabel
3616OpSwitch %undef %then 0 %then 1 %then 2 %else
3617%then = OpLabel
3618OpReturn
3619%else = OpLabel
3620OpReturn
3621OpFunctionEnd
3622)";
3623
3624  CompileSuccessfully(text);
3625  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3626  EXPECT_THAT(
3627      getDiagnosticString(),
3628      HasSubstr(
3629          "OpSwitch must be preceded by an OpSelectionMerge instruction"));
3630}
3631
3632TEST_F(ValidateCFG, MissingMergeOneBranchToMergeGood) {
3633  const std::string text = R"(
3634OpCapability Shader
3635OpCapability Linkage
3636OpMemoryModel Logical GLSL450
3637%void = OpTypeVoid
3638%void_fn = OpTypeFunction %void
3639%bool = OpTypeBool
3640%undef = OpUndef %bool
3641%func = OpFunction %void None %void_fn
3642%entry = OpLabel
3643OpSelectionMerge %b3 None
3644OpBranchConditional %undef %b1 %b2
3645%b1 = OpLabel
3646OpBranchConditional %undef %b2 %b3
3647%b2 = OpLabel
3648OpBranch %b3
3649%b3 = OpLabel
3650OpReturn
3651OpFunctionEnd
3652)";
3653
3654  CompileSuccessfully(text);
3655  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
3656}
3657
3658TEST_F(ValidateCFG, MissingMergeSameTargetConditionalBranchGood) {
3659  const std::string text = R"(
3660OpCapability Shader
3661OpCapability Linkage
3662OpMemoryModel Logical GLSL450
3663%void = OpTypeVoid
3664%void_fn = OpTypeFunction %void
3665%bool = OpTypeBool
3666%undef = OpUndef %bool
3667%func = OpFunction %void None %void_fn
3668%entry = OpLabel
3669OpBranchConditional %undef %then %then
3670%then = OpLabel
3671OpReturn
3672OpFunctionEnd
3673)";
3674
3675  CompileSuccessfully(text);
3676  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
3677}
3678
3679TEST_F(ValidateCFG, MissingMergeOneTargetSwitchBad) {
3680  const std::string text = R"(
3681OpCapability Shader
3682OpCapability Linkage
3683OpMemoryModel Logical GLSL450
3684%void = OpTypeVoid
3685%void_fn = OpTypeFunction %void
3686%int = OpTypeInt 32 0
3687%undef = OpUndef %int
3688%func = OpFunction %void None %void_fn
3689%entry = OpLabel
3690OpSwitch %undef %then 0 %then 1 %then
3691%then = OpLabel
3692OpReturn
3693OpFunctionEnd
3694)";
3695
3696  CompileSuccessfully(text);
3697  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3698  EXPECT_THAT(
3699      getDiagnosticString(),
3700      HasSubstr(
3701          "OpSwitch must be preceded by an OpSelectionMerge instruction"));
3702}
3703
3704TEST_F(ValidateCFG, MissingMergeOneUnseenTargetSwitchBad) {
3705  const std::string text = R"(
3706OpCapability Shader
3707OpCapability Linkage
3708OpMemoryModel Logical GLSL450
3709%void = OpTypeVoid
3710%void_fn = OpTypeFunction %void
3711%int = OpTypeInt 32 0
3712%undef_int = OpUndef %int
3713%bool = OpTypeBool
3714%undef_bool = OpUndef %bool
3715%func = OpFunction %void None %void_fn
3716%entry = OpLabel
3717OpSelectionMerge %merge None
3718OpBranchConditional %undef_bool %merge %b1
3719%b1 = OpLabel
3720OpSwitch %undef_int %b2 0 %b2 1 %merge 2 %b2
3721%b2 = OpLabel
3722OpBranch %merge
3723%merge = OpLabel
3724OpReturn
3725OpFunctionEnd
3726)";
3727
3728  CompileSuccessfully(text);
3729  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3730  EXPECT_THAT(
3731      getDiagnosticString(),
3732      HasSubstr(
3733          "OpSwitch must be preceded by an OpSelectionMerge instruction"));
3734}
3735
3736TEST_F(ValidateCFG, MissingMergeLoopBreakGood) {
3737  const std::string text = R"(
3738OpCapability Shader
3739OpCapability Linkage
3740OpMemoryModel Logical GLSL450
3741%void = OpTypeVoid
3742%void_fn = OpTypeFunction %void
3743%bool = OpTypeBool
3744%undef = OpUndef %bool
3745%func = OpFunction %void None %void_fn
3746%entry = OpLabel
3747OpBranch %loop
3748%loop = OpLabel
3749OpLoopMerge %exit %continue None
3750OpBranch %body
3751%body = OpLabel
3752OpBranchConditional %undef %body2 %exit
3753%body2 = OpLabel
3754OpBranch %continue
3755%continue = OpLabel
3756OpBranch %loop
3757%exit = OpLabel
3758OpReturn
3759OpFunctionEnd
3760)";
3761
3762  CompileSuccessfully(text);
3763  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
3764}
3765
3766TEST_F(ValidateCFG, MissingMergeLoopContinueGood) {
3767  const std::string text = R"(
3768OpCapability Shader
3769OpCapability Linkage
3770OpMemoryModel Logical GLSL450
3771%void = OpTypeVoid
3772%void_fn = OpTypeFunction %void
3773%bool = OpTypeBool
3774%undef = OpUndef %bool
3775%func = OpFunction %void None %void_fn
3776%entry = OpLabel
3777OpBranch %loop
3778%loop = OpLabel
3779OpLoopMerge %exit %continue None
3780OpBranch %body
3781%body = OpLabel
3782OpBranchConditional %undef %body2 %continue
3783%body2 = OpLabel
3784OpBranch %continue
3785%continue = OpLabel
3786OpBranch %loop
3787%exit = OpLabel
3788OpReturn
3789OpFunctionEnd
3790)";
3791
3792  CompileSuccessfully(text);
3793  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
3794}
3795
3796TEST_F(ValidateCFG, MissingMergeSwitchBreakGood) {
3797  const std::string text = R"(
3798OpCapability Shader
3799OpCapability Linkage
3800OpMemoryModel Logical GLSL450
3801%void = OpTypeVoid
3802%void_fn = OpTypeFunction %void
3803%bool = OpTypeBool
3804%undef = OpUndef %bool
3805%int = OpTypeInt 32 0
3806%int_0 = OpConstant %int 0
3807%func = OpFunction %void None %void_fn
3808%entry = OpLabel
3809OpSelectionMerge %merge None
3810OpSwitch %int_0 %merge 1 %b1
3811%b1 = OpLabel
3812OpBranchConditional %undef %merge %b2
3813%b2 = OpLabel
3814OpBranch %merge
3815%merge = OpLabel
3816OpReturn
3817OpFunctionEnd
3818)";
3819
3820  CompileSuccessfully(text);
3821  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
3822}
3823
3824TEST_F(ValidateCFG, MissingMergeSwitchFallThroughGood) {
3825  const std::string text = R"(
3826OpCapability Shader
3827OpCapability Linkage
3828OpMemoryModel Logical GLSL450
3829%void = OpTypeVoid
3830%void_fn = OpTypeFunction %void
3831%bool = OpTypeBool
3832%undef = OpUndef %bool
3833%int = OpTypeInt 32 0
3834%int_0 = OpConstant %int 0
3835%func = OpFunction %void None %void_fn
3836%entry = OpLabel
3837OpSelectionMerge %merge None
3838OpSwitch %int_0 %b1 1 %b2
3839%b1 = OpLabel
3840OpBranchConditional %undef %b3 %b2
3841%b2 = OpLabel
3842OpBranch %merge
3843%b3 = OpLabel
3844OpBranch %merge
3845%merge = OpLabel
3846OpReturn
3847OpFunctionEnd
3848)";
3849
3850  CompileSuccessfully(text);
3851  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
3852}
3853
3854TEST_F(ValidateCFG, MissingMergeInALoopBad) {
3855  const std::string text = R"(
3856OpCapability Shader
3857OpCapability Linkage
3858OpMemoryModel Logical GLSL450
3859%void = OpTypeVoid
3860%void_fn = OpTypeFunction %void
3861%bool = OpTypeBool
3862%undef = OpUndef %bool
3863%func = OpFunction %void None %void_fn
3864%entry = OpLabel
3865OpBranch %loop
3866%loop = OpLabel
3867OpLoopMerge %exit %continue None
3868OpBranch %body
3869%body = OpLabel
3870OpBranchConditional %undef %b1 %b2
3871%b1 = OpLabel
3872OpBranch %exit
3873%b2 = OpLabel
3874OpBranch %continue
3875%continue = OpLabel
3876OpBranch %loop
3877%exit = OpLabel
3878OpReturn
3879OpFunctionEnd
3880)";
3881
3882  CompileSuccessfully(text);
3883  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3884  EXPECT_THAT(getDiagnosticString(), HasSubstr("Selection must be structured"));
3885}
3886
3887TEST_F(ValidateCFG, MissingMergeCrissCrossBad) {
3888  const std::string text = R"(
3889OpCapability Shader
3890OpCapability Linkage
3891OpMemoryModel Logical GLSL450
3892%void = OpTypeVoid
3893%void_fn = OpTypeFunction %void
3894%bool = OpTypeBool
3895%undef = OpUndef %bool
3896%func = OpFunction %void None %void_fn
3897%entry = OpLabel
3898OpSelectionMerge %merge None
3899OpBranchConditional %undef %b1 %b2
3900%b1 = OpLabel
3901OpBranchConditional %undef %b3 %b4
3902%b2 = OpLabel
3903OpBranchConditional %undef %b3 %b4
3904%b3 = OpLabel
3905OpBranch %merge
3906%b4 = OpLabel
3907OpBranch %merge
3908%merge = OpLabel
3909OpReturn
3910OpFunctionEnd
3911)";
3912
3913  CompileSuccessfully(text);
3914  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3915  EXPECT_THAT(getDiagnosticString(), HasSubstr("Selection must be structured"));
3916}
3917
3918TEST_F(ValidateCFG, ContinueCannotBeSelectionMergeTarget) {
3919  const std::string text = R"(
3920OpCapability Shader
3921OpCapability Linkage
3922OpMemoryModel Logical GLSL450
3923OpName %loop "loop"
3924OpName %continue "continue"
3925OpName %body "body"
3926%void = OpTypeVoid
3927%void_fn = OpTypeFunction %void
3928%bool = OpTypeBool
3929%undef = OpUndef %bool
3930%func = OpFunction %void None %void_fn
3931%entry = OpLabel
3932OpBranch %loop
3933%loop = OpLabel
3934OpLoopMerge %exit %continue None
3935OpBranch %body
3936%body = OpLabel
3937OpSelectionMerge %continue None
3938OpBranchConditional %undef %exit %continue
3939%continue = OpLabel
3940OpBranch %loop
3941%exit = OpLabel
3942OpReturn
3943OpFunctionEnd
3944)";
3945
3946  CompileSuccessfully(text);
3947  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3948  EXPECT_THAT(
3949      getDiagnosticString(),
3950      HasSubstr("Header block '3[%body]' is contained in the loop construct "
3951                "headed by "
3952                "'1[%loop]', but its merge block '2[%continue]' is not"));
3953}
3954
3955TEST_F(ValidateCFG, ContinueCannotBeLoopMergeTarget) {
3956  const std::string text = R"(
3957OpCapability Shader
3958OpCapability Linkage
3959OpMemoryModel Logical GLSL450
3960OpName %loop "loop"
3961OpName %continue "continue"
3962OpName %inner "inner"
3963%void = OpTypeVoid
3964%void_fn = OpTypeFunction %void
3965%bool = OpTypeBool
3966%undef = OpUndef %bool
3967%func = OpFunction %void None %void_fn
3968%entry = OpLabel
3969OpBranch %loop
3970%loop = OpLabel
3971OpLoopMerge %exit %continue None
3972OpBranchConditional %undef %exit %inner
3973%inner = OpLabel
3974OpLoopMerge %continue %inner None
3975OpBranchConditional %undef %inner %continue
3976%continue = OpLabel
3977OpBranch %loop
3978%exit = OpLabel
3979OpReturn
3980OpFunctionEnd
3981)";
3982
3983  CompileSuccessfully(text);
3984  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
3985  EXPECT_THAT(
3986      getDiagnosticString(),
3987      HasSubstr("Header block '3[%inner]' is contained in the loop construct "
3988                "headed by "
3989                "'1[%loop]', but its merge block '2[%continue]' is not"));
3990}
3991
3992TEST_F(ValidateCFG, ExitFromConstructWhoseHeaderIsAMerge) {
3993  const std::string text = R"(
3994OpCapability Shader
3995OpCapability Linkage
3996OpMemoryModel Logical GLSL450
3997%void = OpTypeVoid
3998%2 = OpTypeFunction %void
3999%int = OpTypeInt 32 1
4000%4 = OpUndef %int
4001%bool = OpTypeBool
4002%6 = OpUndef %bool
4003%7 = OpFunction %void None %2
4004%8 = OpLabel
4005OpSelectionMerge %9 None
4006OpSwitch %4 %10 0 %11
4007%10 = OpLabel
4008OpBranch %9
4009%11 = OpLabel
4010OpBranch %12
4011%12 = OpLabel
4012OpLoopMerge %13 %14 None
4013OpBranch %15
4014%15 = OpLabel
4015OpSelectionMerge %16 None
4016OpSwitch %4 %17 1 %18 2 %19
4017%17 = OpLabel
4018OpBranch %16
4019%18 = OpLabel
4020OpBranch %14
4021%19 = OpLabel
4022OpBranch %16
4023%16 = OpLabel
4024OpBranch %14
4025%14 = OpLabel
4026OpBranchConditional %6 %12 %13
4027%13 = OpLabel
4028OpSelectionMerge %20 None
4029OpBranchConditional %6 %21 %20
4030%21 = OpLabel
4031OpBranch %9
4032%20 = OpLabel
4033OpBranch %10
4034%9 = OpLabel
4035OpReturn
4036OpFunctionEnd
4037)";
4038
4039  CompileSuccessfully(text);
4040  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
4041}
4042
4043TEST_F(ValidateCFG, ExitFromConstructWhoseHeaderIsAMerge2) {
4044  const std::string text = R"(
4045               OpCapability Shader
4046          %1 = OpExtInstImport "GLSL.std.450"
4047               OpMemoryModel Logical GLSL450
4048               OpEntryPoint Fragment %2 "main"
4049               OpExecutionMode %2 OriginUpperLeft
4050       %void = OpTypeVoid
4051          %4 = OpTypeFunction %void
4052        %int = OpTypeInt 32 1
4053          %6 = OpUndef %int
4054       %bool = OpTypeBool
4055          %8 = OpUndef %bool
4056          %2 = OpFunction %void None %4
4057          %9 = OpLabel
4058               OpSelectionMerge %10 None
4059               OpSwitch %6 %11 0 %12
4060         %11 = OpLabel
4061               OpBranch %10
4062         %12 = OpLabel
4063               OpBranch %13
4064         %13 = OpLabel
4065               OpLoopMerge %14 %15 None
4066               OpBranch %16
4067         %16 = OpLabel
4068               OpSelectionMerge %17 None
4069               OpSwitch %6 %18 1 %19 2 %20
4070         %18 = OpLabel
4071               OpBranch %17
4072         %19 = OpLabel
4073               OpBranch %15
4074         %20 = OpLabel
4075               OpBranch %17
4076         %17 = OpLabel
4077               OpBranch %15
4078         %15 = OpLabel
4079               OpBranchConditional %8 %13 %14
4080         %14 = OpLabel
4081               OpSelectionMerge %21 None
4082               OpBranchConditional %8 %22 %21
4083         %22 = OpLabel
4084               OpSelectionMerge %23 None
4085               OpBranchConditional %8 %24 %23
4086         %24 = OpLabel
4087               OpBranch %10
4088         %23 = OpLabel
4089               OpBranch %21
4090         %21 = OpLabel
4091               OpBranch %11
4092         %10 = OpLabel
4093               OpReturn
4094               OpFunctionEnd
4095)";
4096
4097  CompileSuccessfully(text);
4098  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions());
4099}
4100
4101TEST_F(ValidateCFG, PhiResultInvalidSampler) {
4102  const std::string text = R"(
4103OpCapability Shader
4104OpCapability Linkage
4105OpMemoryModel Logical GLSL450
4106%void = OpTypeVoid
4107%bool = OpTypeBool
4108%f32 = OpTypeFloat 32
4109%sampler = OpTypeSampler
4110%ptr_uc_sampler = OpTypePointer UniformConstant %sampler
4111%sampler_var = OpVariable %ptr_uc_sampler UniformConstant
4112%undef_bool = OpUndef %bool
4113%undef_sampler = OpUndef %sampler
4114%void_fn = OpTypeFunction %void
4115%fn = OpFunction %void None %void_fn
4116%entry = OpLabel
4117%ld_sampler = OpLoad %sampler %sampler_var
4118OpBranch %loop
4119%loop = OpLabel
4120%phi = OpPhi %sampler %undef_sampler %entry %ld_sampler %loop
4121OpLoopMerge %exit %loop None
4122OpBranchConditional %undef_bool %exit %loop
4123%exit = OpLabel
4124OpReturn
4125OpFunctionEnd
4126)";
4127
4128  CompileSuccessfully(text);
4129  ASSERT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
4130  EXPECT_THAT(getDiagnosticString(),
4131              HasSubstr("Result type cannot be OpTypeSampler"));
4132}
4133
4134TEST_F(ValidateCFG, PhiResultInvalidImage) {
4135  const std::string text = R"(
4136OpCapability Shader
4137OpCapability Linkage
4138OpMemoryModel Logical GLSL450
4139%void = OpTypeVoid
4140%bool = OpTypeBool
4141%f32 = OpTypeFloat 32
4142%image = OpTypeImage %f32 2D 0 0 0 1 Rgba32f
4143%ptr_uc_image = OpTypePointer UniformConstant %image
4144%image_var = OpVariable %ptr_uc_image UniformConstant
4145%undef_bool = OpUndef %bool
4146%undef_image = OpUndef %image
4147%void_fn = OpTypeFunction %void
4148%fn = OpFunction %void None %void_fn
4149%entry = OpLabel
4150%ld_image = OpLoad %image %image_var
4151OpBranch %loop
4152%loop = OpLabel
4153%phi = OpPhi %image %undef_image %entry %ld_image %loop
4154OpLoopMerge %exit %loop None
4155OpBranchConditional %undef_bool %exit %loop
4156%exit = OpLabel
4157OpReturn
4158OpFunctionEnd
4159)";
4160
4161  CompileSuccessfully(text);
4162  ASSERT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
4163  EXPECT_THAT(getDiagnosticString(),
4164              HasSubstr("Result type cannot be OpTypeImage"));
4165}
4166
4167TEST_F(ValidateCFG, PhiResultInvalidSampledImage) {
4168  const std::string text = R"(
4169OpCapability Shader
4170OpCapability Linkage
4171OpMemoryModel Logical GLSL450
4172%void = OpTypeVoid
4173%bool = OpTypeBool
4174%f32 = OpTypeFloat 32
4175%sampler = OpTypeSampler
4176%ptr_uc_sampler = OpTypePointer UniformConstant %sampler
4177%sampler_var = OpVariable %ptr_uc_sampler UniformConstant
4178%image = OpTypeImage %f32 2D 0 0 0 1 Rgba32f
4179%ptr_uc_image = OpTypePointer UniformConstant %image
4180%image_var = OpVariable %ptr_uc_image UniformConstant
4181%sampled_image = OpTypeSampledImage %image
4182%undef_bool = OpUndef %bool
4183%undef_sampled_image = OpUndef %sampled_image
4184%void_fn = OpTypeFunction %void
4185%fn = OpFunction %void None %void_fn
4186%entry = OpLabel
4187%ld_image = OpLoad %image %image_var
4188%ld_sampler = OpLoad %sampler %sampler_var
4189OpBranch %loop
4190%loop = OpLabel
4191%phi = OpPhi %sampled_image %undef_sampled_image %entry %sample %loop
4192%sample = OpSampledImage %sampled_image %ld_image %ld_sampler
4193OpLoopMerge %exit %loop None
4194OpBranchConditional %undef_bool %exit %loop
4195%exit = OpLabel
4196OpReturn
4197OpFunctionEnd
4198)";
4199
4200  CompileSuccessfully(text);
4201  ASSERT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
4202  EXPECT_THAT(getDiagnosticString(),
4203              HasSubstr("Result type cannot be OpTypeSampledImage"));
4204}
4205
4206TEST_F(ValidateCFG, PhiResultValidPreLegalizationSampler) {
4207  const std::string text = R"(
4208OpCapability Shader
4209OpCapability Linkage
4210OpMemoryModel Logical GLSL450
4211%void = OpTypeVoid
4212%bool = OpTypeBool
4213%f32 = OpTypeFloat 32
4214%sampler = OpTypeSampler
4215%ptr_uc_sampler = OpTypePointer UniformConstant %sampler
4216%sampler_var = OpVariable %ptr_uc_sampler UniformConstant
4217%undef_bool = OpUndef %bool
4218%undef_sampler = OpUndef %sampler
4219%void_fn = OpTypeFunction %void
4220%fn = OpFunction %void None %void_fn
4221%entry = OpLabel
4222%ld_sampler = OpLoad %sampler %sampler_var
4223OpBranch %loop
4224%loop = OpLabel
4225%phi = OpPhi %sampler %undef_sampler %entry %ld_sampler %loop
4226OpLoopMerge %exit %loop None
4227OpBranchConditional %undef_bool %exit %loop
4228%exit = OpLabel
4229OpReturn
4230OpFunctionEnd
4231)";
4232
4233  options_->before_hlsl_legalization = true;
4234  CompileSuccessfully(text);
4235  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
4236}
4237
4238TEST_F(ValidateCFG, PhiResultValidPreLegalizationImage) {
4239  const std::string text = R"(
4240OpCapability Shader
4241OpCapability Linkage
4242OpMemoryModel Logical GLSL450
4243%void = OpTypeVoid
4244%bool = OpTypeBool
4245%f32 = OpTypeFloat 32
4246%image = OpTypeImage %f32 2D 0 0 0 1 Rgba32f
4247%ptr_uc_image = OpTypePointer UniformConstant %image
4248%image_var = OpVariable %ptr_uc_image UniformConstant
4249%undef_bool = OpUndef %bool
4250%undef_image = OpUndef %image
4251%void_fn = OpTypeFunction %void
4252%fn = OpFunction %void None %void_fn
4253%entry = OpLabel
4254%ld_image = OpLoad %image %image_var
4255OpBranch %loop
4256%loop = OpLabel
4257%phi = OpPhi %image %undef_image %entry %ld_image %loop
4258OpLoopMerge %exit %loop None
4259OpBranchConditional %undef_bool %exit %loop
4260%exit = OpLabel
4261OpReturn
4262OpFunctionEnd
4263)";
4264
4265  options_->before_hlsl_legalization = true;
4266  CompileSuccessfully(text);
4267  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
4268}
4269
4270TEST_F(ValidateCFG, PhiResultValidPreLegalizationSampledImage) {
4271  const std::string text = R"(
4272OpCapability Shader
4273OpCapability Linkage
4274OpMemoryModel Logical GLSL450
4275%void = OpTypeVoid
4276%bool = OpTypeBool
4277%f32 = OpTypeFloat 32
4278%sampler = OpTypeSampler
4279%ptr_uc_sampler = OpTypePointer UniformConstant %sampler
4280%sampler_var = OpVariable %ptr_uc_sampler UniformConstant
4281%image = OpTypeImage %f32 2D 0 0 0 1 Rgba32f
4282%ptr_uc_image = OpTypePointer UniformConstant %image
4283%image_var = OpVariable %ptr_uc_image UniformConstant
4284%sampled_image = OpTypeSampledImage %image
4285%undef_bool = OpUndef %bool
4286%undef_sampled_image = OpUndef %sampled_image
4287%void_fn = OpTypeFunction %void
4288%fn = OpFunction %void None %void_fn
4289%entry = OpLabel
4290%ld_image = OpLoad %image %image_var
4291%ld_sampler = OpLoad %sampler %sampler_var
4292OpBranch %loop
4293%loop = OpLabel
4294%phi = OpPhi %sampled_image %undef_sampled_image %entry %sample %loop
4295%sample = OpSampledImage %sampled_image %ld_image %ld_sampler
4296OpLoopMerge %exit %loop None
4297OpBranchConditional %undef_bool %exit %loop
4298%exit = OpLabel
4299OpReturn
4300OpFunctionEnd
4301)";
4302
4303  options_->before_hlsl_legalization = true;
4304  CompileSuccessfully(text);
4305  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
4306}
4307
4308TEST_F(ValidateCFG, StructuredSelections_RegisterBothTrueAndFalse) {
4309  // In this test, we try to make a case where the false branches
4310  // to %20 and %60 from blocks %10 and %50 must be registered
4311  // during the validity check for sturctured selections.
4312  // However, an error is caught earlier in the flow, that the
4313  // branches from %100 to %20 and %60 violate dominance.
4314  const std::string text = R"(
4315    OpCapability Shader
4316    OpMemoryModel Logical Simple
4317    OpEntryPoint Fragment %main "main"
4318    OpExecutionMode %main OriginUpperLeft
4319
4320    %void    = OpTypeVoid
4321    %void_fn = OpTypeFunction %void
4322
4323    %bool = OpTypeBool
4324    %cond = OpUndef %bool
4325
4326    %main = OpFunction %void None %void_fn
4327
4328    %1 = OpLabel
4329    OpSelectionMerge %999 None
4330    OpBranchConditional %cond %10 %100
4331
4332    %10 = OpLabel
4333    OpSelectionMerge %30 None  ; force registration of %30
4334    OpBranchConditional %cond %30 %20 ; %20 should be registered too
4335
4336    %20 = OpLabel
4337    OpBranch %30
4338
4339    %30 = OpLabel ; merge for first if
4340    OpBranch %50
4341
4342
4343    %50 = OpLabel
4344    OpSelectionMerge %70 None  ; force registration of %70
4345    OpBranchConditional %cond %70 %60 ; %60 should be registered
4346
4347    %60 = OpLabel
4348    OpBranch %70
4349
4350    %70 = OpLabel ; merge for second if
4351    OpBranch %999
4352
4353    %100 = OpLabel
4354    OpBranchConditional %cond %20 %60 ; should require a merge
4355
4356    %999 = OpLabel
4357    OpReturn
4358
4359    OpFunctionEnd
4360)";
4361
4362  CompileSuccessfully(text);
4363  EXPECT_NE(SPV_SUCCESS, ValidateInstructions());
4364  EXPECT_THAT(getDiagnosticString(),
4365              HasSubstr("The selection construct with the selection header "
4366                        "'8[%8]' does not structurally dominate the merge "
4367                        "block '10[%10]'\n"));
4368}
4369
4370TEST_F(ValidateCFG, UnreachableIsStaticallyReachable) {
4371  const std::string text = R"(
4372OpCapability Shader
4373OpCapability Linkage
4374OpMemoryModel Logical GLSL450
4375%1 = OpTypeVoid
4376%2 = OpTypeFunction %1
4377%3 = OpFunction %1 None %2
4378%4 = OpLabel
4379OpBranch %5
4380%5 = OpLabel
4381OpUnreachable
4382OpFunctionEnd
4383)";
4384
4385  CompileSuccessfully(text);
4386  EXPECT_EQ(SPV_SUCCESS, ValidateAndRetrieveValidationState());
4387
4388  auto f = vstate_->function(3);
4389  auto entry = f->GetBlock(4).first;
4390  ASSERT_TRUE(entry->reachable());
4391  auto end = f->GetBlock(5).first;
4392  ASSERT_TRUE(end->reachable());
4393}
4394
4395TEST_F(ValidateCFG, BlockOrderDoesNotAffectReachability) {
4396  const std::string text = R"(
4397OpCapability Shader
4398OpCapability Linkage
4399OpMemoryModel Logical GLSL450
4400%1 = OpTypeVoid
4401%2 = OpTypeFunction %1
4402%3 = OpTypeBool
4403%4 = OpUndef %3
4404%5 = OpFunction %1 None %2
4405%6 = OpLabel
4406OpBranch %7
4407%7 = OpLabel
4408OpSelectionMerge %8 None
4409OpBranchConditional %4 %9 %10
4410%8 = OpLabel
4411OpReturn
4412%9 = OpLabel
4413OpBranch %8
4414%10 = OpLabel
4415OpBranch %8
4416%11 = OpLabel
4417OpUnreachable
4418OpFunctionEnd
4419)";
4420
4421  CompileSuccessfully(text);
4422  EXPECT_EQ(SPV_SUCCESS, ValidateAndRetrieveValidationState());
4423
4424  auto f = vstate_->function(5);
4425  auto b6 = f->GetBlock(6).first;
4426  auto b7 = f->GetBlock(7).first;
4427  auto b8 = f->GetBlock(8).first;
4428  auto b9 = f->GetBlock(9).first;
4429  auto b10 = f->GetBlock(10).first;
4430  auto b11 = f->GetBlock(11).first;
4431
4432  ASSERT_TRUE(b6->reachable());
4433  ASSERT_TRUE(b7->reachable());
4434  ASSERT_TRUE(b8->reachable());
4435  ASSERT_TRUE(b9->reachable());
4436  ASSERT_TRUE(b10->reachable());
4437  ASSERT_FALSE(b11->reachable());
4438}
4439
4440TEST_F(ValidateCFG, PhiInstructionWithDuplicateIncomingEdges) {
4441  const std::string text = R"(
4442               OpCapability Shader
4443          %1 = OpExtInstImport "GLSL.std.450"
4444               OpMemoryModel Logical GLSL450
4445               OpEntryPoint Fragment %4 "main"
4446               OpExecutionMode %4 OriginUpperLeft
4447               OpSource ESSL 320
4448          %2 = OpTypeVoid
4449          %3 = OpTypeFunction %2
4450          %6 = OpTypeBool
4451          %7 = OpConstantTrue %6
4452          %4 = OpFunction %2 None %3
4453          %5 = OpLabel
4454               OpSelectionMerge %10 None
4455               OpBranchConditional %7 %8 %9
4456          %8 = OpLabel
4457               OpBranch %10
4458          %9 = OpLabel
4459	       OpBranch %10
4460         %10 = OpLabel
4461	 %11 = OpPhi %6 %7 %8 %7 %8
4462               OpReturn
4463               OpFunctionEnd
4464)";
4465
4466  CompileSuccessfully(text);
4467  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
4468  EXPECT_THAT(getDiagnosticString(),
4469              HasSubstr("OpPhi references incoming basic block <id> "));
4470  EXPECT_THAT(getDiagnosticString(), HasSubstr("multiple times."));
4471}
4472
4473TEST_F(ValidateCFG, PhiOnVoid) {
4474  const std::string text = R"(
4475               OpCapability Shader
4476          %1 = OpExtInstImport "GLSL.std.450"
4477               OpMemoryModel Logical GLSL450
4478               OpEntryPoint Fragment %4 "main"
4479               OpExecutionMode %4 OriginUpperLeft
4480               OpSource ESSL 320
4481               OpName %4 "main"
4482               OpName %6 "foo("
4483          %2 = OpTypeVoid
4484          %3 = OpTypeFunction %2
4485          %4 = OpFunction %2 None %3
4486          %5 = OpLabel
4487          %8 = OpFunctionCall %2 %6
4488               OpBranch %20
4489         %20 = OpLabel
4490         %21 = OpPhi %2 %8 %20
4491               OpReturn
4492               OpFunctionEnd
4493          %6 = OpFunction %2 None %3
4494          %7 = OpLabel
4495               OpReturn
4496               OpFunctionEnd
4497)";
4498
4499  CompileSuccessfully(text);
4500  EXPECT_EQ(SPV_ERROR_INVALID_DATA, ValidateInstructions());
4501  EXPECT_THAT(getDiagnosticString(),
4502              HasSubstr("OpPhi must not have void result type"));
4503}
4504
4505TEST_F(ValidateCFG, InvalidExitSingleBlockLoop) {
4506  const std::string text = R"(
4507OpCapability Shader
4508OpCapability Linkage
4509OpMemoryModel Logical GLSL450
4510OpName %5 "BAD"
4511%void = OpTypeVoid
4512%bool = OpTypeBool
4513%undef = OpUndef %bool
4514%void_fn = OpTypeFunction %void
4515%fn = OpFunction %void None %void_fn
4516%1 = OpLabel
4517OpBranch %2
4518%2 = OpLabel
4519OpLoopMerge %3 %4 None
4520OpBranchConditional %undef %3 %5
4521%5 = OpLabel
4522OpLoopMerge %6 %5 None
4523OpBranchConditional %undef %5 %4
4524%6 = OpLabel
4525OpReturn
4526%4 = OpLabel
4527OpBranch %2
4528%3 = OpLabel
4529OpReturn
4530OpFunctionEnd
4531)";
4532
4533  CompileSuccessfully(text);
4534  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
4535  EXPECT_THAT(
4536      getDiagnosticString(),
4537      HasSubstr("block <ID> '1[%BAD]' exits the continue headed by <ID> "
4538                "'1[%BAD]', but not via a structured exit"));
4539}
4540
4541TEST_F(ValidateCFG, SwitchSelectorNotAnInt) {
4542  const std::string spirv = R"(
4543OpCapability Shader
4544OpMemoryModel Logical GLSL450
4545OpEntryPoint GLCompute %main "main"
4546OpExecutionMode %main LocalSize 1 1 1
4547%void = OpTypeVoid
4548%float = OpTypeFloat 32
4549%float_1 = OpConstant %float 1
4550%void_fn = OpTypeFunction %void
4551%main = OpFunction %void None %void_fn
4552%entry = OpLabel
4553OpSelectionMerge %default None
4554OpSwitch %float_1 %default
4555%default = OpLabel
4556OpReturn
4557OpFunctionEnd
4558)";
4559
4560  CompileSuccessfully(spirv);
4561  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
4562  EXPECT_THAT(getDiagnosticString(),
4563              HasSubstr("Selector type must be OpTypeInt"));
4564}
4565
4566TEST_F(ValidateCFG, SwitchDefaultNotALabel) {
4567  const std::string spirv = R"(
4568OpCapability Shader
4569OpMemoryModel Logical GLSL450
4570OpEntryPoint GLCompute %main "main"
4571OpExecutionMode %main LocalSize 1 1 1
4572%void = OpTypeVoid
4573%int = OpTypeInt 32 0
4574%int_1 = OpConstant %int 1
4575%void_fn = OpTypeFunction %void
4576%main = OpFunction %void None %void_fn
4577%entry = OpLabel
4578OpSelectionMerge %default None
4579OpSwitch %int_1 %int_1
4580%default = OpLabel
4581OpReturn
4582OpFunctionEnd
4583)";
4584
4585  CompileSuccessfully(spirv);
4586  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
4587  EXPECT_THAT(getDiagnosticString(),
4588              HasSubstr("Default must be an OpLabel instruction"));
4589}
4590
4591TEST_F(ValidateCFG, BlockDepthRecursion) {
4592  const std::string text = R"(
4593OpCapability Shader
4594OpMemoryModel Logical GLSL450
4595OpEntryPoint GLCompute %main "main"
4596%void = OpTypeVoid
4597%bool = OpTypeBool
4598%undef = OpUndef %bool
4599%void_fn = OpTypeFunction %void
4600%main = OpFunction %void None %void_fn
4601%1 = OpLabel
4602OpBranch %2
4603%2 = OpLabel
4604OpLoopMerge %3 %4 None
4605OpBranchConditional %undef %3 %4
4606%4 = OpLabel
4607OpBranch %2
4608%3 = OpLabel
4609OpBranch %5
4610%5 = OpLabel
4611OpSelectionMerge %2 None
4612OpBranchConditional %undef %6 %7
4613%6 = OpLabel
4614OpReturn
4615%7 = OpLabel
4616OpReturn
4617OpFunctionEnd
4618)";
4619
4620  CompileSuccessfully(text);
4621  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
4622}
4623
4624TEST_F(ValidateCFG, BadStructuredExitBackwardsMerge) {
4625  const std::string spirv = R"(
4626OpCapability Shader
4627OpMemoryModel Logical GLSL450
4628OpEntryPoint GLCompute %main "main"
4629%void = OpTypeVoid
4630%bool = OpTypeBool
4631%undef = OpUndef %bool
4632%void_fn = OpTypeFunction %void
4633%main = OpFunction %void None %void_fn
4634%1 = OpLabel
4635OpBranch %2
4636%2 = OpLabel
4637OpLoopMerge %4 %5 None
4638OpBranchConditional %undef %4 %6
4639%6 = OpLabel
4640OpSelectionMerge %7 None
4641OpBranchConditional %undef %8 %9
4642%7 = OpLabel
4643OpReturn
4644%8 = OpLabel
4645OpBranch %5
4646%9 = OpLabel
4647OpSelectionMerge %6 None
4648OpBranchConditional %undef %5 %5
4649%5 = OpLabel
4650OpBranch %2
4651%4 = OpLabel
4652OpReturn
4653OpFunctionEnd
4654)";
4655
4656  CompileSuccessfully(spirv);
4657  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
4658}
4659
4660TEST_F(ValidateCFG, BranchConditionalDifferentTargetsPre1p6) {
4661  const std::string text = R"(
4662OpCapability Shader
4663OpCapability Linkage
4664OpMemoryModel Logical GLSL450
4665%void = OpTypeVoid
4666%bool = OpTypeBool
4667%undef = OpUndef %bool
4668%void_fn = OpTypeFunction %void
4669%func = OpFunction %void None %void_fn
4670%entry = OpLabel
4671OpBranchConditional %undef %target %target
4672%target = OpLabel
4673OpReturn
4674OpFunctionEnd
4675)";
4676
4677  CompileSuccessfully(text, SPV_ENV_UNIVERSAL_1_5);
4678  EXPECT_EQ(SPV_SUCCESS, ValidateInstructions(SPV_ENV_UNIVERSAL_1_5));
4679}
4680
4681TEST_F(ValidateCFG, BranchConditionalDifferentTargetsPost1p6) {
4682  const std::string text = R"(
4683OpCapability Shader
4684OpCapability Linkage
4685OpMemoryModel Logical GLSL450
4686%void = OpTypeVoid
4687%bool = OpTypeBool
4688%undef = OpUndef %bool
4689%void_fn = OpTypeFunction %void
4690%func = OpFunction %void None %void_fn
4691%entry = OpLabel
4692OpBranchConditional %undef %target %target
4693%target = OpLabel
4694OpReturn
4695OpFunctionEnd
4696)";
4697
4698  CompileSuccessfully(text, SPV_ENV_UNIVERSAL_1_6);
4699  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions(SPV_ENV_UNIVERSAL_1_6));
4700  EXPECT_THAT(getDiagnosticString(),
4701              HasSubstr("In SPIR-V 1.6 or later, True Label and False Label "
4702                        "must be different labels"));
4703}
4704
4705TEST_F(ValidateCFG, BadBackEdgeUnreachableContinue) {
4706  const std::string text = R"(
4707OpCapability Shader
4708OpCapability Linkage
4709OpMemoryModel Logical GLSL450
4710%1 = OpTypeVoid
4711%2 = OpTypeFunction %1
4712%3 = OpFunction %1 None %2
4713%4 = OpLabel
4714OpBranch %5
4715%5 = OpLabel
4716OpLoopMerge %6 %7 None
4717OpBranch %8
4718%8 = OpLabel
4719OpBranch %5
4720%7 = OpLabel
4721OpUnreachable
4722%6 = OpLabel
4723OpUnreachable
4724OpFunctionEnd
4725)";
4726
4727  CompileSuccessfully(text);
4728  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
4729  EXPECT_THAT(
4730      getDiagnosticString(),
4731      HasSubstr("The continue construct with the continue target '7[%7]' "
4732                "does not structurally dominate the back-edge block '8[%8]'"));
4733}
4734
4735TEST_F(ValidateCFG, BadLoop) {
4736  const std::string text = R"(
4737OpCapability Shader
4738OpMemoryModel Logical Simple
4739OpEntryPoint Fragment %2 "           "
4740OpExecutionMode %2 OriginUpperLeft
4741OpName %49 "loop"
4742%void = OpTypeVoid
4743%12 = OpTypeFunction %void
4744%2 = OpFunction %void None %12
4745%33 = OpLabel
4746OpBranch %49
4747%50 = OpLabel
4748OpBranch %49
4749%49 = OpLabel
4750OpLoopMerge %33 %50 Unroll
4751OpBranch %49
4752OpFunctionEnd
4753)";
4754
4755  CompileSuccessfully(text);
4756  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
4757  EXPECT_THAT(getDiagnosticString(),
4758              HasSubstr("Loop header '2[%loop]' is targeted by 2 back-edge "
4759                        "blocks but the standard requires exactly one"));
4760}
4761
4762TEST_F(ValidateCFG, BadSwitch) {
4763  const std::string text = R"(
4764               OpCapability StorageImageExtendedFormats
4765               OpMemoryModel Logical GLSL450
4766               OpEntryPoint Fragment %2 "blah" %58
4767               OpExecutionMode %2 OriginUpperLeft
4768               OpName %BAD "BAD"
4769         %11 = OpTypeVoid
4770         %12 = OpTypeFunction %11
4771         %19 = OpTypeInt 32 1
4772         %21 = OpConstant %19 555758549
4773          %2 = OpFunction %11 None %12
4774          %4 = OpLabel
4775               OpBranch %33
4776         %33 = OpLabel
4777               OpLoopMerge %34 %35 None
4778               OpBranch %55
4779        %BAD = OpLabel
4780               OpSelectionMerge %53 None
4781               OpSwitch %21 %34 196153896 %53 20856160 %34 33570306 %34 593494531 %52
4782         %55 = OpLabel
4783               OpLoopMerge %52 %58 DontUnroll
4784               OpBranch %35
4785         %58 = OpLabel
4786               OpSelectionMerge %58 None
4787               OpSwitch %21 %52 178168 %55 608223677 %34 604111047 %34 -553516825 %34 -106432813 %BAD 6946864 %55 1257373689 %55 973090296 %35 -113180668 %55 537002232 %BAD 13762553 %BAD 1030172152 %35 -553516825 %55 -262137 %35 -1091822332 %BAD 131320 %52 131321 %35 131320 %52 131321 %35 -1091822332 %BAD
4788         %53 = OpLabel
4789               OpBranch %35
4790         %52 = OpLabel
4791               OpBranch %34
4792         %35 = OpLabel
4793               OpBranch %33
4794         %34 = OpLabel
4795               OpKill
4796               OpFunctionEnd
4797)";
4798
4799  CompileSuccessfully(text);
4800  EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
4801  EXPECT_THAT(getDiagnosticString(),
4802              HasSubstr("exits the selection headed by <ID> '3[%BAD]', but not "
4803                        "via a structured exit"));
4804}
4805
4806}  // namespace
4807}  // namespace val
4808}  // namespace spvtools
4809