Structured control flow #9

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.