Dense IR Graphs with Extension Attributes

Continuing work on Tapestry, and contrasting with previous explorations of edge-reified graphs as discussed in a previous post; I’ve been exploring a graph IR form with dense nodes, with extension attributes.

When working with extensions, we need namespaces, so I introduced an XMLNS style type, ScopedName, containing:

• a scope (probably a web domain); and
• a name in that scope.

And given this, a handful of basic nodes:

• Tensor Nodes
  • shape attribute
  • dtype attributes
• Operation Nodes
  • signature link
  • input tensor reference map
  • result tensor reference map
• OpSignature Nodes
  • scoped name (with namespace and name)
  • an is-external property

This is sufficient to describe a lowerable graph, but it lacks things needed to describe a schedule (what machine is a thing on), the happens-before links of io nodes (based upon the is-external property), or any information needed to rewrite the graph.

The assumption is that the rewrite rules operate on namespaced properties, and may need new attributes attached to a node to enable novel rewrite rules; so I’m exploring namespaced extension attributes. We can slot the polyhedral type signature into this format, but potentially other information needed for rewrite rules; and it potentially plays nice with xpath/jquery style graph query rules.

At present, this is just a sketch. But it explores ideas of separating core-semantics (tensors, operations, sequencing) from extension semantics (rewrite type information, scheduling constraints).

One thing that’s become clear is that the shape signature of block operations, with their polyhedral projections, is very different from fusion operations like concat; and it’s possible there are yet more special forms needed; rather than force a common form for all operations, or construct an operation hierarchy zoo, it seems profitable to permit namespaced extension attributes, and handle the various forms in purpose-built graph rewrite rules for the given forms.