Struct LoopFinder

struct LoopFinder<'a> {
    cfg: &'a ControlFlowGraph,
    loop_header_to_exit_targets: IndexMap<ControlRegion, IndexSet<ControlRegion, BuildHasherDefault<FxHasher>>, BuildHasherDefault<FxHasher>>,
    scc_stack: Vec<ControlRegion>,
    scc_state: EntityOrientedDenseMap<ControlRegion, SccState>,
}

Minimal loop analysis, based on Tarjan’s SCC (strongly connected components) algorithm, applied recursively (for every level of loop nesting).

Here “minimal” means that each loops is the smallest CFG subgraph possible (excluding any control-flow paths that cannot reach a backedge and cycle), i.e. each loop is a CFG SCC (strongly connected component).

These “minimal loops” contrast with the “maximal loops” that the greedy architecture of the structurizer would naively produce, with the main impact of the difference being where loop exits (breaks) “merge” (or “reconverge”), which SPIR-V encodes via OpLoopMerge, and is significant for almost anything where shared memory and/or subgroup ops can allow observing when invocations “wait for others in the subgroup to exit the loop” (or when they fail to wait).

This analysis was added to because of two observations wrt “reconvergence”:

1. syntactic loops (from some high-level language), when truly structured (i.e. only using while/do-while exit conditions, not break etc.), always map to “minimal loops” on a CFG, as the only loop exit edge is built-in, and no part of the syntactic “loop body” can be its successor
2. more pragmatically, compiling shader languages to SPIR-V seems to (almost?) always either fully preserve syntactic loops (via SPIR-V OpLoopMerge), or structurize CFGs in a way that produces “minimal loops”, which can be misleading with explicit breaks (moving user code from just before the break to after the loop), but is less impactful than “maximal loops”

Fields

cfg: &'a ControlFlowGraph

loop_header_to_exit_targets: IndexMap<ControlRegion, IndexSet<ControlRegion, BuildHasherDefault<FxHasher>>, BuildHasherDefault<FxHasher>>

scc_stack: Vec<ControlRegion>

SCC accumulation stack, where CFG nodes collect during the depth-first traversal, and are only popped when their “SCC root” (loop header) is (note that multiple SCCs on the stack does not indicate SCC nesting, but rather a path between two SCCs, i.e. a loop following another).

scc_state: EntityOrientedDenseMap<ControlRegion, SccState>

Per-CFG-node traversal state (often just pointing to a scc_stack slot).

Implementations

impl<'a> LoopFinder<'a>

fn new(cfg: &'a ControlFlowGraph) -> Self

fn find_earliest_scc_root_of( &mut self, node: ControlRegion, ) -> (Option<SccStackIdx>, EventualCfgExits)

Tarjan’s SCC algorithm works by computing the “earliest” reachable node, from every node (often using the name lowlink), which will be equal to the origin node itself iff that node is an “SCC root” (loop header), and always point to an “earlier” node if a cycle (via loop backedge) was found from somewhere else in the SCC (i.e. from inside the loop body).

Here we track stack indices (as the stack order is the traversal order), and distinguish the acyclic case to avoid treating most nodes as self-loops.