[SPIRV] Don't lower switch statements to OpSwitch

[llvm-beanz]

Description
OpSwitch even as defined with SPV_KHR_maximal_reconvergence, doesn't require converging on switch cases that have fall through.

The only way to get SPIR-V to implement switch statements that converge correctly is with OpBranch instead.

Steps to Reproduce

Given the following HLSL:

RWBuffer<int> value;

[numthreads(4, 1, 1)]
void main(uint3 threadID : SV_DispatchThreadID) {
  uint sum = 0;
  switch (value[threadID.x]) {
    case 0:
      sum += WaveActiveSum(1);
    default:
      sum += WaveActiveSum(10);
      break;
  }
  value[threadID.x] = sum;
}

CE

If given the input [ 0, 0, 1, 2], the computed output should be [ 42, 42, 40, 40 ].

Actual Behavior

Even with the KHR maximal reconvergence extension the OpSwitch is not guaranteed to converge the tangles between case 0 and the default case.

However, if instead these were generated as a chain of OpBranch statements, the control flow would converge at each new OpBranch, which would result in the correct tangle grouping.

The HLSL example above does not compile in Clang today due to missing features, a Clang example that is closer to compiling is https://godbolt.org/z/nbhbd8fdK.

Any switch with fallthrough cases that have behavior dependent on participating lanes converging will be undefined behavior if the SPIRV OpSwitch instruction is used, so we should just not generate it ever for HLSL.

[llvm-beanz]

Just to capture a thought here to guide work. @s-perron mentioned over on the DXC issue a possible expansion that could implement this behavior.

I want to propose a slightly different expansion. Given this source:

switch(selector) {
  default:
    something();
  case 1:
  case 3:
    somethingElse();
    break;
  case 2:
    anotherThing();
    break;
}

It should be accurate to expand it to:

do {
  if (!(selector == 1 && selector == 2 && selector == 3)) {
    something();
    selector = 1; // This case falls through so we now need to execute case 1.
  }
  if (selector == 1) {
    somethingElse();
    break; // breaks can still be breaks;
  }
  if (selector == 2) {
    anotherThing();
    break;
  }
} while(false)

The advantage of this over the other expansion is that we don't rely on OpSwitch at all. This does produce duplicate conditional checks, but I expect LLVM's CSE will clean that up where it can. This should also be pretty simple to generate directly from Clang which might just be a good across the board approach for HLSL & OpenCL.

[llvm-beanz]

Added the OpenCL label because I believe this SPIR-V bug also impacts correct code generation for OpenCL.

[llvmbot]

@llvm/issue-subscribers-opencl

Author: Chris B (llvm-beanz)

**Description** `OpSwitch` even as defined with [SPV_KHR_maximal_reconvergence](https://github.com/KhronosGroup/SPIRV-Registry/blob/main/extensions/KHR/SPV_KHR_maximal_reconvergence.asciidoc#divergence), doesn't require converging on switch cases that have fall through.

The only way to get SPIR-V to implement switch statements that converge correctly is with OpBranch instead.

Steps to Reproduce

Given the following HLSL:

RWBuffer<int> value;

[numthreads(4, 1, 1)]
void main(uint3 threadID : SV_DispatchThreadID) {
  uint sum = 0;
  switch (value[threadID.x]) {
    case 0:
      sum += WaveActiveSum(1);
    default:
      sum += WaveActiveSum(10);
      break;
  }
  value[threadID.x] = sum;
}

CE

If given the input [ 0, 0, 1, 2], the computed output should be [ 42, 42, 40, 40 ].

Actual Behavior

Even with the KHR maximal reconvergence extension the OpSwitch is not guaranteed to converge the tangles between case 0 and the default case.

However, if instead these were generated as a chain of OpBranch statements, the control flow would converge at each new OpBranch, which would result in the correct tangle grouping.

The HLSL example above does not compile in Clang today due to missing features, a Clang example that is closer to compiling is https://godbolt.org/z/nbhbd8fdK.

Any switch with fallthrough cases that have behavior dependent on participating lanes converging will be undefined behavior if the SPIRV OpSwitch instruction is used, so we should just not generate it ever for HLSL.