tree 15d869b3facbdcb15f23466d680dad693507b4c5
parent 8cf3f0413178cdf45b1570eb5dff44cf6e97a8b5
author Nathan Gauër <brioche@google.com> 1706894534 +0100
committer Copybara-Service <copybara-worker@google.com> 1706894930 -0800

[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.

GitOrigin-RevId: 7b08b4360b488b35428c97132b3f9d2a777bd770