spirv: Rework structured control flow handling
The new code splits the work into a few passes instead of trying to do
everything with a single pass. This helps to apply the new clarified
rules for structured control flow in the SPIR-V specification, in
particular the "exit construct" rules.
First find an appropriate ordering for the blocks, based on the
approach taken by Tint (WebGPU compiler). Then, with those blocks
in order, identify the SPIR-V constructs start and end positions.
Finally, walk the blocks again to emit NIR for each of them, "opening"
and "closing" the necessary NIR constructs as we reach the start and
end positions of the SPIR-V constructs.
There are a couple of interesting choices when mapping the constructs
to NIR:
- NIR doesn't have something like a switch, so like the previous code,
we lower the switch construct to a series of conditionals for each
case.
- And, unlike the previous code, when there's a need to perform a
break from a construct that NIR doesn't directly support (e.g. inside
a case construct, conditionally breaking early from the switch), we
now use a combination of a NIR loop and an NIR if. Extra code is
added to ensure that loop_break and loop_continues are propagated
to the right loop.
This should fix various issues with valid SPIR-V that previously
resulted in "Invalid back or cross-edge in the CFG" errors.
Thanks to Alan Baker and David Neto for their explanations of
ordering the blocks, in the Tint code and in presentations to
the SPIR-V WG.
Thanks to Jack Clark for providing a lot of valuable tests used to
validate this MR.
Closes: #5973, #6369
Reviewed-by: Faith Ekstrand <faith.ekstrand@collabora.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/17922>