msiglreith
commented
7 years ago 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.
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.