Module: vkd3d Branch: master Commit: 51f13391e6117592a4c77bbb457302c8c3bfa606 URL: https://gitlab.winehq.org/wine/vkd3d/-/commit/51f13391e6117592a4c77bbb457302...
Author: Giovanni Mascellani gmascellani@codeweavers.com Date: Tue Jan 16 23:56:43 2024 +0100
vkd3d-shader/ir: Introduce a simple control flow graph structurizer.
The structurizer is implemented along the lines of what is usually called the "structured program theorem": the control flow is completely virtualized by mean of an additional TEMP register which stores the block index which is currently running. The whole program is then converted to a huge switch construction enclosed in a loop, executing at each iteration the appropriate block and updating the register depending on block jump instruction.
The algorithm's generality is also its major weakness: it accepts any input program, even if its CFG is not reducible, but the output program lacks any useful convergence information. It satisfies the letter of the SPIR-V requirements, but it is expected that it will be very inefficient to run on a GPU (unless a downstream compiler is able to devirtualize the control flow and do a proper convergence analysis pass). The algorithm is however very simple, and good enough to at least pass tests, enabling further development. A better alternative is expected to be upstreamed incrementally.
Side note: the structured program theorem is often called the Böhm-Jacopini theorem; Böhm and Jacopini did indeed prove a variation of it, but their algorithm is different from what is commontly attributed to them and implemented here, so I opted for not using their name.
---
libs/vkd3d-shader/ir.c | 147 ++++++++++++++++++++++++++++++++- tests/hlsl/conditional.shader_test | 2 +- tests/hlsl/for.shader_test | 2 +- tests/hlsl/function-return.shader_test | 44 +++++----- tests/hlsl/loop.shader_test | 6 +- tests/hlsl/return.shader_test | 32 +++---- tests/hlsl/sm6-ternary.shader_test | 4 +- tests/hlsl/switch.shader_test | 40 ++++----- 8 files changed, 209 insertions(+), 68 deletions(-)