Module: vkd3d
Branch: master
Commit: 51f13391e6117592a4c77bbb457302c8c3bfa606
URL: https://gitlab.winehq.org/wine/vkd3d/-/commit/51f13391e6117592a4c77bbb45730…
Author: Giovanni Mascellani <gmascellani(a)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(-)