How to model subdivision and divisibility?

[atyshka]

I'm interested in applying E-Graphs for generating GPU kernels. For GPU computation, you need to subdivide your input data into chunks that will be processed by a GPU core. I'm wondering how this "chunking" could be performed in an E-Graph.

Simply put, how could I express a rewrite rule for rewriting a large matrix as a concatenation of smaller matrices? For simplification let's assume division by two. So for any matrix A with even dimensions, I could express that as a rewrite of A<x, y> => concat(A[0...x/2,0...y], A[x/2...x,0...y] ). But how do I express that this rewrite is only valid for even dimensioned A? I haven't seen any model of divisibility in the examples for EGG.

The best idea I could come up with is a bottom-up approach, where the E-graph starts with the data subdivided as much as possible, and then the E-graph applies merge rules instead of division rules. But I think a top-down approach would be more elegant, so I'm wondering if there's a way to model this subdivision in the E-Graph.

[mwillsey]

We don't have support for those kinds of rules in egg, at least not using the built in syntactic rewrites. You can probably create dynamic rewrites that can accomplish this though. As the documentation shows, a Rewrite consists of a Searcher and an Applier, both of which are traits you can implement yourself. The docs have an example of a custom applier, but I don't think we have one for a custom Searcher.

[yihozhang]

Maybe consider defining a dimension analysis for your e-graph and using a conditional applier only applies a rule when the dimension of the given matrix is divisible? See here for an example of how to use conditional applier.