Repository: KhronosGroup/SPIRV-Tools (language: python)

Issue:
Optimizer: Invalid CFG generated for odd switch break pattern
This SPIR-V:

```
; SPIR-V
; Version: 1.0
; Generator: Khronos SPIR-V Tools Assembler; 0
; Bound: 44
; Schema: 0
               OpCapability Shader
          %1 = OpExtInstImport "GLSL.std.450"
               OpMemoryModel Logical GLSL450
               OpEntryPoint GLCompute %main "main"
               OpExecutionMode %main LocalSize 1 1 1
               OpSource GLSL 450
               OpName %main "main"
               OpName %c "c"
               OpName %BUF "BUF"
               OpMemberName %BUF 0 "a"
               OpMemberName %BUF 1 "b"
               OpMemberName %BUF 2 "d"
               OpName %o "o"
               OpName %a "a"
               OpMemberDecorate %BUF 0 Offset 0
               OpMemberDecorate %BUF 1 Offset 4
               OpMemberDecorate %BUF 2 Offset 8
               OpDecorate %BUF BufferBlock
               OpDecorate %o DescriptorSet 0
               OpDecorate %o Binding 0
       %void = OpTypeVoid
          %8 = OpTypeFunction %void
        %int = OpTypeInt 32 1
%_ptr_Function_int = OpTypePointer Function %int
        %BUF = OpTypeStruct %int %int %int
%_ptr_Uniform_BUF = OpTypePointer Uniform %BUF
          %o = OpVariable %_ptr_Uniform_BUF Uniform
      %int_0 = OpConstant %int 0
%_ptr_Uniform_int = OpTypePointer Uniform %int
      %int_2 = OpConstant %int 2
      %int_1 = OpConstant %int 1
       %main = OpFunction %void None %8
         %16 = OpLabel
          %c = OpVariable %_ptr_Function_int Function
          %a = OpVariable %_ptr_Function_int Function
         %17 = OpAccessChain %_ptr_Uniform_int %o %int_0
         %18 = OpLoad %int %17
               OpStore %c %18
               OpBranch %19
         %19 = OpLabel
               OpLoopMerge %20 %21 None
               OpBranch %22
         %22 = OpLabel
         %23 = OpLoad %int %c
               OpSelectionMerge %24 None
               OpSwitch %23 %24 5 %25 1 %26 2 %26 3 %26
         %25 = OpLabel
               OpBranch %27
         %27 = OpLabel
               OpLoopMerge %28 %29 None
               OpBranch %30
         %30 = OpLabel
         %31 = OpAccessChain %_ptr_Uniform_int %o %int_2
         %32 = OpLoad %int %31
               OpSelectionMerge %33 None
               OpSwitch %32 %34 10 %35 20 %35
         %34 = OpLabel
               OpBranch %29
         %35 = OpLabel
         %36 = OpLoad %int %c
         %37 = OpLoad %int %c
         %38 = OpIAdd %int %37 %36
               OpStore %c %38
               OpBranch %28
         %33 = OpLabel
               OpUnreachable
         %29 = OpLabel
               OpBranch %27
         %28 = OpLabel
               OpBranch %24
         %26 = OpLabel
         %39 = OpLoad %int %c
               OpStore %a %39
               OpBranch %20
         %24 = OpLabel
         %40 = OpLoad %int %c
         %41 = OpIAdd %int %40 %int_1
               OpStore %c %41
               OpBranch %21
         %21 = OpLabel
               OpBranch %19
         %20 = OpLabel
         %42 = OpLoad %int %a
         %43 = OpAccessChain %_ptr_Uniform_int %o %int_1
               OpStore %43 %42
               OpReturn
               OpFunctionEnd
```

is optimized into with `spirv-opt -O -o opt.spv test.spv`:

```
; SPIR-V
; Version: 1.0
; Generator: Khronos SPIR-V Tools Assembler; 0
; Bound: 49
; Schema: 0
               OpCapability Shader
          %1 = OpExtInstImport "GLSL.std.450"
               OpMemoryModel Logical GLSL450
               OpEntryPoint GLCompute %main "main"
               OpExecutionMode %main LocalSize 1 1 1
               OpSource GLSL 450
               OpName %main "main"
               OpName %BUF "BUF"
               OpMemberName %BUF 0 "a"
               OpMemberName %BUF 1 "b"
               OpMemberName %BUF 2 "d"
               OpName %o "o"
               OpMemberDecorate %BUF 0 Offset 0
               OpMemberDecorate %BUF 1 Offset 4
               OpMemberDecorate %BUF 2 Offset 8
               OpDecorate %BUF BufferBlock
               OpDecorate %o DescriptorSet 0
               OpDecorate %o Binding 0
       %void = OpTypeVoid
          %8 = OpTypeFunction %void
        %int = OpTypeInt 32 1
        %BUF = OpTypeStruct %int %int %int
%_ptr_Uniform_BUF = OpTypePointer Uniform %BUF
          %o = OpVariable %_ptr_Uniform_BUF Uniform
      %int_0 = OpConstant %int 0
%_ptr_Uniform_int = OpTypePointer Uniform %int
      %int_2 = OpConstant %int 2
      %int_1 = OpConstant %int 1
       %main = OpFunction %void None %8
         %16 = OpLabel
         %17 = OpAccessChain %_ptr_Uniform_int %o %int_0
         %18 = OpLoad %int %17
               OpBranch %19
         %19 = OpLabel
         %44 = OpPhi %int %18 %16 %41 %21
               OpLoopMerge %26 %21 None
               OpBranch %22
         %22 = OpLabel
               OpSelectionMerge %24 None
               OpSwitch %44 %24 5 %25 1 %26 2 %26 3 %26
         %25 = OpLabel
               OpBranch %27
         %27 = OpLabel
               OpLoopMerge %35 %34 None
               OpBranch %30
         %30 = OpLabel
         %31 = OpAccessChain %_ptr_Uniform_int %o %int_2
         %32 = OpLoad %int %31
               OpSelectionMerge %33 None
               OpSwitch %32 %34 10 %35 20 %35
         %34 = OpLabel
               OpBranch %27
         %35 = OpLabel
         %38 = OpIAdd %int %44 %44
               OpBranch %24
         %33 = OpLabel
               OpUnreachable
         %26 = OpLabel
         %43 = OpAccessChain %_ptr_Uniform_int %o %int_1
               OpStore %43 %44
               OpReturn
         %24 = OpLabel
         %48 = OpPhi %int %44 %22 %38 %35
         %41 = OpIAdd %int %48 %int_1
               OpBranch %21
         %21 = OpLabel
               OpBranch %19
               OpFunctionEnd
```

which reports:

```
error: line 38: Selection header 22[%22] does not structurally dominate its case construct 26[%26]
  %22 = OpLabel
```

![cfg](https://user-images.githubusercontent.com/17786731/188141926-d8d7743b-8926-478f-8543-51da3836108b.png)

The 22 switch header is breaking directly out of the loop, which is not allowed without an intermediate break block I believe.



Discussion / hints:
The merge blocks pass is breaking this example.
Here is a smaller example:
```
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint GLCompute %func "func"
OpExecutionMode %func LocalSize 1 1 1
OpName %entry "entry";
OpName %loop "loop"
OpName %loop_merge "loop_merge"
OpName %loop_cont "loop_cont"
OpName %switch "switch"
OpName %switch_merge "switch_merge"
%void = OpTypeVoid
%bool = OpTypeBool
%int = OpTypeInt 32 0
%void_fn = OpTypeFunction %void
%bool_undef = OpUndef %bool
%int_undef = OpUndef %int
%func = OpFunction %void None %void_fn
%entry = OpLabel
OpBranch %loop
%loop = OpLabel
OpLoopMerge %loop_merge %loop_cont None
OpBranch %switch
%switch = OpLabel
OpSelectionMerge %switch_merge None
OpSwitch %int_undef %switch_merge 0 %break 1 %break
%break = OpLabel
OpBranch %loop_merge
%switch_merge = OpLabel
OpBranch %loop_cont
%loop_cont = OpLabel
OpBranch %loop
%loop_merge = OpLabel
OpReturn
OpFunctionEnd
```

The block merge pass isn't accounting for switches to structurally dominate their case constructs.

Fix patch:
diff --git a/source/opt/block_merge_util.cpp b/source/opt/block_merge_util.cpp
index 8ae8020a58..83c702ca3b 100644
--- a/source/opt/block_merge_util.cpp
+++ b/source/opt/block_merge_util.cpp
@@ -125,6 +125,26 @@ bool CanMergeWithSuccessor(IRContext* context, BasicBlock* block) {
       return false;
     }
   }
+
+  if (succ_is_merge || IsContinue(context, lab_id)) {
+    auto* struct_cfg = context->GetStructuredCFGAnalysis();
+    auto switch_block_id = struct_cfg->ContainingSwitch(block->id());
+    if (switch_block_id) {
+      auto switch_merge_id = struct_cfg->SwitchMergeBlock(switch_block_id);
+      const auto* switch_inst =
+          &*block->GetParent()->FindBlock(switch_block_id)->tail();
+      for (uint32_t i = 1; i < switch_inst->NumInOperands(); i += 2) {
+        auto target_id = switch_inst->GetSingleWordInOperand(i);
+        if (target_id == block->id() && target_id != switch_merge_id) {
+          // Case constructs must be structurally dominated by the OpSwitch.
+          // Since the successor is the merge/continue for another construct,
+          // merging the blocks would break that requirement.
+          return false;
+        }
+      }
+    }
+  }
+
   return true;
 }
 


Test patch:
diff --git a/test/opt/block_merge_test.cpp b/test/opt/block_merge_test.cpp
index 9698fed23d..6129bb2730 100644
--- a/test/opt/block_merge_test.cpp
+++ b/test/opt/block_merge_test.cpp
@@ -1201,6 +1201,92 @@ OpFunctionEnd
   SinglePassRunAndMatch<BlockMergePass>(text, true);
 }
 
+TEST_F(BlockMergeTest, DontLoseCaseConstruct) {
+  const std::string text = R"(
+OpCapability Shader
+OpMemoryModel Logical GLSL450
+OpEntryPoint GLCompute %func "func"
+OpExecutionMode %func LocalSize 1 1 1
+OpName %entry "entry";
+OpName %loop "loop"
+OpName %loop_merge "loop_merge"
+OpName %loop_cont "loop_cont"
+OpName %switch "switch"
+OpName %switch_merge "switch_merge"
+%void = OpTypeVoid
+%bool = OpTypeBool
+%int = OpTypeInt 32 0
+%void_fn = OpTypeFunction %void
+%bool_undef = OpUndef %bool
+%int_undef = OpUndef %int
+%func = OpFunction %void None %void_fn
+%entry = OpLabel
+OpBranch %loop
+%loop = OpLabel
+OpLoopMerge %loop_merge %loop_cont None
+OpBranch %switch
+%switch = OpLabel
+OpSelectionMerge %switch_merge None
+OpSwitch %int_undef %switch_merge 0 %break 1 %break
+%break = OpLabel
+OpBranch %loop_merge
+%switch_merge = OpLabel
+OpBranch %loop_cont
+%loop_cont = OpLabel
+OpBranch %loop
+%loop_merge = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+  auto result = SinglePassRunAndDisassemble<opt::BlockMergePass>(
+      text, /* skip_nop = */ true, /* do_validation = */ true);
+  EXPECT_EQ(opt::Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(BlockMergeTest, DontLoseDefaultCaseConstruct) {
+  const std::string text = R"(
+OpCapability Shader
+OpMemoryModel Logical GLSL450
+OpEntryPoint GLCompute %func "func"
+OpExecutionMode %func LocalSize 1 1 1
+OpName %entry "entry";
+OpName %loop "loop"
+OpName %loop_merge "loop_merge"
+OpName %loop_cont "loop_cont"
+OpName %switch "switch"
+OpName %switch_merge "switch_merge"
+%void = OpTypeVoid
+%bool = OpTypeBool
+%int = OpTypeInt 32 0
+%void_fn = OpTypeFunction %void
+%bool_undef = OpUndef %bool
+%int_undef = OpUndef %int
+%func = OpFunction %void None %void_fn
+%entry = OpLabel
+OpBranch %loop
+%loop = OpLabel
+OpLoopMerge %loop_merge %loop_cont None
+OpBranch %switch
+%switch = OpLabel
+OpSelectionMerge %switch_merge None
+OpSwitch %int_undef %cont 0 %switch_merge 1 %switch_merge
+%cont = OpLabel
+OpBranch %loop_cont
+%switch_merge = OpLabel
+OpBranch %loop_merge
+%loop_cont = OpLabel
+OpBranch %loop
+%loop_merge = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+  auto result = SinglePassRunAndDisassemble<opt::BlockMergePass>(
+      text, /* skip_nop = */ true, /* do_validation = */ true);
+  EXPECT_EQ(opt::Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
 // TODO(greg-lunarg): Add tests to verify handling of these cases:
 //
 //    More complex control flow