[SPIR-V] Structurize SPIR-V for graphics

[Keenuts]

The current backend mostly supports OpenCL's SPIR-V. For graphical SPIR-V, one crucial step needs to be added: the structurizer.

The spec defining what a structured control-flow means for SPIR-V is here: https://registry.khronos.org/SPIR-V/specs/unified1/SPIRV.html#_structured_control_flow

The current method we'd like to pursue would be relying on convergent intrinsics in the LLVM IR. The frontend (only HLSL so far) will have to generate the correct convergent instructions around loops, and wave operations.

Once we have those operations, we believe the IR can be structured in 7 steps:

• adding pre-headers to all the loops
• split basic-blocks with different convergent operations. (Each basic block shall be linked to at most 1 convergent token)
• merge back-edges for loops with multiple back edges.
• identify convergence regions (regions sharing the same convergence token).

• merge exit blocks for convergence region with multiple exits.

  At this point, we shall have a hierarchy of SESE regions, each associated with a convergence token. This should ensure we don't yoyo across convergence regions.

  Once those initial 5 steps done, we can add the SPIR-V instructions to determine merge/continue nodes.

• Adding OpLoopMerge instructions to loop constructs.
• Adding OpSelectionMerge to selection constructs

The last 2 steps will be slightly more complex, as we shall make sure no header share multiple OpSelectionMerge/OpLoopMerge, and no branch breaks out of multiple selection/loop constructs. But those are merely fixup steps once we have the initial 5 steps implemented.

[VyacheslavLevytskyy]

@Keenuts I have a very quick side question about spirv structurizer in general, including recent PR 107408. We have one pretty ancient and evidently non-completed piece of code with a copypasted description that I'd guess is taken from lib/Target/ARC/ARCInstrInfo.cpp -- it is Branch Folding and If Conversion implementation in our https://github.com/llvm/llvm-project/blob/432ba353d8fcd68721203e1d0eb1fb983485f568/llvm/lib/Target/SPIRV/SPIRVInstrInfo.cpp#L155

I've hit this code when running tests with -O3, and would like to fix/complete/rework/remove it. So the question is, whether this logic in SPIRVInstrInfo.cpp:::analyzeBranch() is somehow related to your spirv structurizer work and/or may benefit from the fact that you've added a lot of logic in PR 107408? Before doing anything with SPIRVInstrInfo.cpp:::analyzeBranch() I just want to be sure that I don't invent a bicycle here and in the worst case overlap with something that you've done or have plans to do. Please advise, what do you think about SPIRVInstrInfo.cpp:::analyzeBranch() from the perspective of your expertise with branching in spirv?

UPD: It looks not as complicated as I anticipated, so I've just added missing implementations in https://github.com/llvm/llvm-project/pull/110653

[Keenuts]

lated to your spirv structurizer work and/or may benefit from the fact that you've added a lot of logic in PR 107408? Before

Hi!

I haven't relied on this for the structurizer, since it works at the IR level. Looking at the comment, the main thing I wouldn't expect for the SPIR-V backend are fallthrough: IR doesn't have those, and since SPIR-V doesn't support them, I expect we should never remove unconditional branches.