Giovanni Mascellani : vkd3d-shader/ir: Introduce a simple control flow graph structurizer.

[Alexandre Julliard]

Module: vkd3d
Branch: master
Commit: 51f13391e6117592a4c77bbb457302c8c3bfa606
URL:    https://gitlab.winehq.org/wine/vkd3d/-/commit/51f13391e6117592a4c77bbb457302...

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(-)