Pattern-Matching and Subgraph Transformations

In DaCe, the easiest way to locally modify an SDFG is by data-centric transformations. Transformations are a powerful tool to optimize applications in DaCe. You can go from naive code to state-of-the-art performance using only transformations.

All transformations extend the TransformationBase class. There are three built-in types of transformations in DaCe:

• Pattern-matching Transformations (extending PatternTransformation): Transformations that require a certain subgraph structure to match. Within this abstract class, there are two sub-classes:

  • SingleStateTransformation: Patterns are limited to a single SDFG state.

  • MultiStateTransformation: Patterns are given on a subgraph of an SDFG state machine.

  A pattern-matching must extend at least one of those two classes.

• Subgraph Transformations (extending SubgraphTransformation): Transformations that can operate on arbitrary subgraphs.

• Another form of (implicit) transformation is a Library node expansion (extending ExpandTransformation). It is a class used for tracking when library nodes are expanded, and creating a library node implementation involves extending this class.

Transformations can have properties and those can be used when applying them: for example, tile sizes in MapTiling.

For more information on how to use and author data-centric transformations, see the Using and Creating Transformations tutorial.

Pattern-Matching Transformations

A pattern-matching transformation works on a specific subgraph pattern, and, using the API, can be used to find all instances of that pattern and apply it anywhere. Authoring such a transformation requires extending one of the two subclasses mentioned above (SingleStateTransformation or MultiStateTransformation), add static PatternNode fields to the class to represent the pattern, and implement at least three methods:

• expressions: A method that returns a list of graph patterns that match this transformation.

• can_be_applied: A method that, given a subgraph candidate, checks for additional conditions whether it can be transformed.

• apply: A method that applies the transformation on the given SDFG.

An instance of the transformation class is associated with a specific match, so using the fields in the class relate to a specific subgraph.

For example, the following sample transformation matches an access node connected to a map entry, and changes the map’s label to match the name of that access node:

from dace.sdfg import nodes, SDFG, SDFGState
from dace.sdfg.utils import node_path_graph
from dace.transformation import transformation as xf

class MyTransformation(xf.SingleStateTransformation):
    # Pattern nodes are defined here and can be used in the class
    access = xf.PatternNode(nodes.AccessNode)
    map_node = xf.PatternNode(nodes.MapEntry)

    @classmethod
    def expressions(cls):
        # The pattern to match is ``access -> map_node``. Since this is a
        # class method, accessing ``cls.access`` gets the pattern node.
        return [node_path_graph(cls.access, cls.map_node)]

    # Because this is a Single-State Transformation, the first argument here
    # is ``state``
    def can_be_applied(self, state: SDFGState, expr_index: int, sdfg: SDFG,
                    permissive=False) -> bool:
        # We can now use ``self.access``, which refers to a specific subgraph
        # pattern match
        if self.access.data == 'mydata':
            return True

        # We only match patterns in which the access node is accessing 'mydata'
        return False


    def apply(self, state: SDFGState, sdfg: SDFG) -> nodes.MapEntry:
        # Here we apply the transformation, and can return any object. This
        # is sometimes used when transformations are composed together and
        # need to pass information to each other.
        self.map_node.label = 'mymap'
        return self.map_node

Subgraph Transformations

Subgraph transformations can be applied to any subgraph that returns True for the can_be_applied method. It is used when arbitrary local regions need to be modified, e.g., in SubgraphFusion. The implementation is very similar to pattern-matching transformations, but without the pattern. A simple example with a property would be:

from dace.sdfg import nodes, SDFG
from dace.sdfg.utils import node_path_graph
from dace.transformation import transformation as xf
from dace.sdfg.graph import SubgraphView
from dace.properties import make_properties, Property

@make_properties
class ExampleSubgraphXform(xf.SubgraphTransformation):
    """
    This string describes the transformation and will be shown in the Visual Studio Code plugin.
    """

    # Properties can be defined on Transformation classes as with other objects
    simplify = Property(desc="Simplify SDFG after applying transformation.", dtype=bool, default=False)

    def can_be_applied(self, sdfg: SDFG, subgraph: SubgraphView) -> bool:
        return True

    def apply(self, sdfg: SDFG) -> None:
        # First we obtain the subgraph view from the SDFG we matched in
        subgraph = self.subgraph_view(sdfg)

        # Then we can work on the graph normally
        for node in subgraph.nodes():
            # Do something complex...
            pass

        if self.simplify:
            sdfg.simplify()