Struct spirt::ControlRegion

source ·

pub struct ControlRegion(/* private fields */);

Expand description

Entity handle for a ControlRegionDef (a control-flow region).

A ControlRegion (“control-flow region”) is a linear chain of ControlNodes, describing a single-entry single-exit (SESE) control-flow “region” (subgraph) in a function’s control-flow graph (CFG).

Control-flow

In SPIR-T, two forms of control-flow are used:

“structured”: ControlRegions and ControlNodes in a “mutual tree”
- i.e. each such ControlRegion can only appear in exactly one ControlNode, and each ControlNode can only appear in exactly one ControlRegion
- a region is either the function’s body, or used as part of ControlNode (e.g. the “then” case of an if-else), itself part of a larger region
- when inside a region, reaching any other part of the function (or any other function on call stack) requires leaving through the region’s single exit (also called “merge”) point, i.e. its execution is either:
  - “convergent”: the region completes and continues into its parent ControlNode, or function (the latter being a “structured return”)
  - “divergent”: execution gets stuck in the region (an infinite loop), or is aborted (e.g. OpTerminateInvocation from SPIR-V)
“unstructured”: ControlRegions which connect to other ControlRegions using cfg::ControlInsts (as described by a cfg::ControlFlowGraph)

When a function’s entire body can be described by a single ControlRegion, that function is said to have (entirely) “structured control-flow”.

Mixing “structured” and “unstructured” control-flow is supported because:

during structurization, it allows structured subgraphs to remain connected by the same CFG edges that were connecting smaller ControlRegions before
structurization doesn’t have to fail in the cases it doesn’t fully support yet, but can instead result in a “maximally structured” function

Other IRs may use different “structured control-flow” definitions, notably:

SPIR-V uses a laxer definition, that corresponds more to the constraints of the GLSL language, and is single-entry multiple-exit (SEME) with “alternate exits” consisting of breaks out of switches and loops, and returns (making it non-trivial to inline one function into another)
RVSDG inspired SPIR-T’s design, but its regions are (acyclic) graphs, it makes no distinction between control-flow and “computational” nodes, and its execution order is determined by value/state dependencies alone (SPIR-T may get closer to it in the future, but the initial compromise was chosen to limit the effort of lowering/lifting from/to SPIR-V)

Data-flow interactions

SPIR-T Values follow “single static assignment” (SSA), just like SPIR-V:

inside a function, any new value is produced (or “defined”) as an output of DataInst/ControlNode, and “uses” of that value are Values variants which refer to the defining DataInst/ControlNode directly (guaranteeing the “single” and “static” of “SSA”, by construction)
the definition of a value must “dominate” all of its uses (i.e. in all possible execution paths, the definition precedes all uses)

But unlike SPIR-V, SPIR-T’s structured control-flow has implications for SSA:

dominance is simpler, so values defined in a ControlRegion can be used:
- later in that region, including in the region’s outputs (which allows “exporting” values out to the rest of the function)
- outside that region, but only if the parent ControlNode only has exactly one child region (i.e. a single-case Select, or a Loop)
  - this is an “emergent” property, stemming from the region having to execute (at least once) before the parent ControlNode can complete, but is not is not ideal (especially for reasoning about loops) and should eventually be replaced with passing all such values through the region outputs (or by inlining the region, in the Select case)
instead of φ (“phi”) nodes, SPIR-T uses region outputs to merge values coming from separate control-flow paths (i.e. the cases of a Select), and region inputs for passing values back along loop backedges (additionally, the body’s inputs are used for function parameters)
- like the “block arguments” alternative to SSA phi nodes (which some other SSA IRs use), this has the advantage of keeping the uses of the “source” values in their respective paths (where they’re dominated), instead of in the merge (where phi nodes require special-casing, as their “uses” of all the “source” values would normally be illegal)
- in unstructured control-flow, region inputs are additionally used for phi nodes, as cfg::ControlInsts passing values to their target regions