Experimental Control Flow Blocks
SDFGs have long been able to express complex control flow through the use of state machines that wrap dataflow. Even having control flow within dataflow is possible through the use of nested SDFGs.
However, increasingly large programs also lead to a lot of complex control flow. With DaCe's main goal of analyzing and optimizing the dataflow, this level of control flow can make analysis and optimization unnecessarily difficult.
To address this, DaCe 0.15 introduced a new and experimental concept of nested ControlFlowRegions. Here, the idea is that groups of nodes and edges in a control flow graph can be bundled together into a region, which can be nested into a different control flow graph where it is expressed as a single node. The main goal of this is to simplify control flow graph analysis passes.
In DaCe 0.15.1, this concept was extended to a special type of ControlFlowRegion, a LoopRegion, which is a control flow region with additional semantics that allow it to represent a control flow loop with a single element. These loop regions are documented here, and an example use case expressing a naive 2D matrix-matrix multiplication with 3 nested for-loops can be seen below:
From DaCe > 0.16.1 onwards, these loop regions can be automatically generated from the Python and Fortran frontends when a program is annotated with a special use_experimental_cfg_blocks flag. An example can be seen below:
import dace
import numpy
N = dace.symbol('N')
@dace.program(use_experimental_cfg_blocks=True):
def mat_mult(A: dace.float64[N, N], B: dace.float64[N, N]):
return A @ B
# OR:
mat_mult.use_experimental_cfg_blocks = True
sdfg = mat_mult.to_sdfg()If this flag is set to false or lacking entirely, control flow regions are inlined in the frontend and the generated SDFG contains a single-level, traditional state machine, which is a graph with the only node type being SDFGStates.
If the flag is set, the generated SDFG represents a graph where edges are InterstateEdges, as usual, but nodes are of a general type ControlFlowBlock. Each ControlFlowBlock can be an SDFGState, which represents a basic block in the dataflow context, a special control flow instruction such as a ContinueBlock, BreakBlock, or ReturnBlock, or can itself represent an entire other ControlFlowRegion, as is the case with a LoopRegion.
This of course represents a significant change in the structure of an SDFG, and many passes and transformations need to adapt a different way of handling an SDFG as a result of this.
To help with backwards compatibility, our pattern matching infrastructure and most pipelines (such as SDFG.simplify()) by default assume a pass or transformation is incompatible with this new, hierarchical control flow representation, and will not apply it or check applicability with its can_be_applied method, in the case of transformations. Instead, a warning is generated, indicating that compatibility is not given and the pass or transformation was thus skipped. SDFGs are similarly annotated with a property using_experimental_blocks if they contain such hierarchical control flow. If this hierarchical control flow is first inlined, using_experimental_blocks can be set to False and incompatible transformations may be applied.
To indicate to our infrastructure that a pass or transformation has been adapted, the @dace.transformation.experimental_cfg_block_compatible decorator can be placed on top of a pass or transformation. If annotated with this decorator, pattern matching and pipelines recognize compatibility and will apply transformations and passes accordingly.
To ensure further robustness, known incompatible transformations can be decorated with the @dace.transformation.transformation.single_level_sdfg_only decorator, which wraps all of their external API methods in safety checks that only apply these methods if an SDFG without experimental CFG blocks is given and prints warnings otherwise.
Note that this decorator is optional to provide added safety. In most cases, the absence of any decorator and thus inaction will not cause issues even when using experimental Control Flow Blocks.