[SPIRV] convergence anchor intrinsic does not have a parent token (#122230)

[SPIR-V] Add SPIR-V structurizer (#107408)

This commit adds an initial SPIR-V structurizer.
It leverages the previously merged passes, and the convergence region
analysis to determine the correct

[SPIR-V] Add SPIR-V structurizer (#107408)

This commit adds an initial SPIR-V structurizer.
It leverages the previously merged passes, and the convergence region
analysis to determine the correct merge and continue blocks for SPIR-V.

The first part does a branch cleanup (simplifying switches, and
legalizing them), then merge instructions are added to cycles,
convergent and later divergent blocks.
Then comes the important part: splitting critical edges, and making sure
the divergent construct boundaries don't cross.

- we split blocks with multiple headers into 2 blocks.
- we split blocks that are a merge blocks for 2 or more constructs:
SPIR-V spec disallow a merge block to be shared by 2
loop/switch/condition construct.
- we split merge & continue blocks: SPIR-V spec disallow a basic block
to be both a continue block, and a merge block.
- we remove superfluous headers: when a header doesn't bring more info
than the parent on the divergence state, it must be removed.

This PR leverages the merged SPIR-V simulator for testing, as long as
spirv-val. For now, most DXC structurization tests are passing. The
unsupported ones are either caused by unsupported features like switches
on boolean types, or switches in region exits, because the MergeExit
pass doesn't support those yet (there is a FIXME).

This PR is quite large, and the addition not trivial, so I tried to keep
it simple. E.G: as soon as the CFG changes, I recompute the dominator
trees and other structures instead of updating them.

---------

Signed-off-by: Nathan Gauër <brioche@google.com>

show more ...

[SPIRV] Silence unused variable warnings (#95492)

This change marks a few variable declarations as [[maybe_unused]] to
silence unused variable warnings.

[SPIR-V] add convergence region analysis (#78456)

This new analysis returns a hierarchical view of the convergence regions
in the given function.
This will allow our passes to query which basic bl

[SPIR-V] add convergence region analysis (#78456)

This new analysis returns a hierarchical view of the convergence regions
in the given function.
This will allow our passes to query which basic block belongs to which
convergence region, and structurize the code in consequence.

Definition
----------

A convergence region is a CFG with:
- a single entry node.
- one or multiple exit nodes (different from LLVM's regions).
- one back-edge
- zero or more subregions.

Excluding sub-regions nodes, the nodes of a region can only reference a
single convergence token. A subregion uses a different convergence
token.

Algorithm
---------

This algorithm assumes all loops are in the Simplify form.

Create an initial convergence region for the whole function.
- the convergence token is the function entry token.
- the entry is the function entrypoint.
- Exits are all the basic blocks terminating with a return instruction.

Take the function CFG, and process it in DAG order (ignoring
back-edges). If a basic block is a loop header:
- Create a new region.
- The parent region is the parent's loop region if any, otherwise, the
top level region.
- The region blocks are all the blocks belonging to this loop.
- For each loop exit: - visit the rest of the CFG in DAG order (ignore
back-edges). - if the region's convergence token is found, add all the
blocks dominated by the exit from which the token is reachable to the
region.
- continue the algorithm with the loop headers successors.

show more ...