Structured control flow

[Jasper-Bekkers]

MIR internally is pretty much completely unstructured which leads to some problems since in the flavour of SPIR-V that we're trying to support the control flow needs to be fully structured. The only flavor that supports unstructured controlflow is for OpenCL.

This requires potentially quite a bit of engineering to solve since the algorithms involved are relatively complex.

• Stackifier: https://medium.com/leaningtech/solving-the-structured-control-flow-problem-once-and-for-all-5123117b1ee2 (upstreamed in LLVM)
• Relooper: https://github.com/kripken/emscripten/raw/master/docs/paper.pdf (part of emscripten, so probably also in LLVM already).

One avenue of exploration could be to see if we can shoehorn the Mesa3d controlflow restructurizer back into our compile chain:

• https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/2401 (the Merge Request on their repo that adds the restructurizer pass)
• https://gitlab.freedesktop.org/mesa/mesa/-/tree/master/src/gallium/drivers/zink/nir_to_spirv (their IL - NIR - to SPIRV back out is also supported in the Zink backend).

Another option would be to implement either Stackifier or Relooper as part of spirv-opt that we run after the fact. We may already need to run spirv-opt to run mem2reg since we'll mostly be emitting OpLoad and OpStore instead of sticking to SSA proper.

Another option is one that @MaikKlein proposed:

There is I think another option that I haven't explored yet, and that is to remove some mir passes. Basically I think if you would remove most of the mir passes between HIR and MIR then the resulting cfg should be fairly easy to work with. I think most of the information will be lost during some of the optimization passes. Recomputing the control flow is fairly easy.

This option would leave the high-level controlflow constructs in tact without ever lowering them to branches/jumps which is a lot more robust then trying to reconstruct the structured controlflow from the jumps.

Some other projects have also run into similar issues:

• SPIRV-LLVM-Translator (translates LLVM to OpenCL style SPIRV) Support Vulkan?  KhronosGroup/SPIRV-LLVM-Translator#30 (comment)
• SPIRV-Cross has an outstanding issue about this: Unstructured control flow KhronosGroup/SPIRV-Cross#889
• @MaikKlein ran into this issue with RLSL as well Fully implement structured control flow MaikKlein/rlsl#8
• DirectXShaderCompiler's SPIR-V backend does work properly in this case, they've decided to emit SPIR-V more or less straight from the AST, which sits at a higher level then what we're currently doing (and are comfortable with). It's unlikely that the rustc team would accept such a change back into their mainline, or that they would support not breaking such a codepath.

[Jasper-Bekkers]

My intuition is the pragmatic fast way to make progress on a few architectures is to drop structured control flow, but the long-term formal way to be portable across a diversity of architectures is to have a robust execution model, which at the moment wants structured control flow

It may be worthwhile to experiment and see if the desktop gpus already support unstructured controlflow in their Vulkan drivers so we can potentially push this problem a little bit ahead of us while we work towards a minimally viable product.

[Jasper-Bekkers]

Our hardware actually has IF, ELSE, ENDIF, and DO, BREAK, and CONT instructions.

From Intel.

waveops make absolutely no sense without structured control flow

Another contribution.

[VZout]

Taking the Relooper approach seems like a good option for now. While not the most efficient, it would be a good start for me to get started with this kind of work and performance is likely not that important for the first prototype.
Here is a tracking issue on my progress:

#24

[repi]

This old issue is partially resolved now right @VZout ?

[VZout]

There is a solution for the problem but not fully implemented yet. Currently only simple conditional branch's work.
We can probably replace it with a tracking issue?

[repi]

Ok np, could either create new one that tracks the progress support around this, or keep this one. up to you

[VZout]

Closing in favor of #97