msiglreith
Structured control flow
SPIR-V requires special blocks for the control flow, mainly merge blocks, at which the control flow merges again. More background information can be found in the SPIR-V reference and https://people.freedesktop.org/~cwabbott0/nir-docs/control_flow.html.
MIR doesn't directly output this information, which needs to be reconstructed. A similiar approach is the 'relooper' algorithm used in emscripten as described in 'Emscripten: An LLVM-to-JavaScript Compiler' by Alon Zakai, Section 3.2.
Some more input regarding this topic: We aim for implementing a control flow analysis for the generated basic blocks from MIR. The goal of the analysis is to detect loops, if blocks and switchblocks. These blocks consist of multiple basic blocks enclosing the whole structure (also with the necessary blocks for valid SPIR-V output). Therefore we need several steps to detect the general structures and convert the current MIR generated cfg into valid a valid SPIR-V cfg:
- Generate reducible graph: Using node splitting we want to ensure, that our control flow graph is reducible, which has some neat properties like easy loop detection and transformation. As MIR is generated from structured control flow, we might be able to elide this part for now under the assumption that the MIR graph is already reducible.
- Detect the different control flow strucutres using dominators
- Transform the exisiting cfg to a valid SPIR-V cfg, which follows the definitions from the SPIR-V reference.
Corrode project implemented an algorithm based on Relooper, which solved a similar problem to the one described above (Excellent post: http://jamey.thesharps.us/2017/04/corrode-update-control-flow-translation.html).
Currently, I'm leaning towards an additional MIR pass, converting MIR to an intermediate representation ' MIR-SSA'. The purpose of that IR would be solve the structured control flow issue and transform into a SSA form, simplifying the transition to SPIR-V. This step would have actually priortiy over the refactoring #10 due to switching towards MIR-SSA -> SPIR-V translation.