Expand description
Tools for working with control-flow graphs that contain SSA dataflow
(often abbreviated to CFG<SSA> or similar).
The defining characteristic of SSA dataflow in a control-flow graph is that SSA definitions (of values, e.g. the result of an instruction) are “visible” from all the CFG locations they dominate (i.e. the locations that can only be reached by passing through the definition first), and can therefore be directly used arbitrarily far away in the CFG with no annotations required anywhere in the CFG between the definition and its uses.
While “def dominates use” is sufficient to ensure the value can traverse
the necessary paths (between def and use) in the CFG, a lot of care must
be taken to preserve the correctness of such implicit dataflow across all
transformations, and it’s overall far more fragile than the local dataflow
of e.g. phi nodes (or their alternative “block arguments”), or in SPIR-T’s
case, ControlRegion inputs and ControlNode outputs (inspired by RVSDG,
which has even stricter isolation/locality in its regions).
Structs§
- All blocks and ddefinitions they contain, which have to be computed first, and remain immutable, because where a value is defined (or whether it’s at all part of the function itself) can have non-monotonic effects elsewhere.
- Incremental tracker for definition uses (and CFG edges between blocks), accumulating the complete set of transitive uses for each block, also known as the SSA “live set” (corresponding to the starting position of each block).