Dialect conversion: pre-order traversal

Hello!

I am currently working on a conversion between an AST-like graph-based dialect - where all ops are laid out on a single block inside a graph-region - into a standard nested dialect. For example, consider this:

// Dialect foo
%x = foo.op1 ...
%y = foo.op2 ...
%root = foo.parentOp %x, %y

I would like to convert dialect foo into a dialect bar as follows:

// Dialect bar
%root = bar.parentOp {
  %x = bar.op1 ...
  %y = bar.op2 ...
} ...

The dialect conversion employs a post-order traversal so %x and %y will be converted before we visit %root. That makes things a bit weird because now I find myself having to “move” the converted ops inside bar.parentOp.

Question: Is this normal ? Would it make more sense to write my own “top-down”/pre-order traversal ? I wonder if there is a trick/customization that I am missing ?

Thank you in advance!

Thanasis.

1 Like

Yes, moving ops around is quite normal when patterns involve ops with regions.

It feels weird that I need to move these ops AND all their dependencies. For example:

// Dialect foo
%x = foo.op1 %x1, %x2, ...
%y = foo.op2 %y1, %y2, ...
%root = foo.parentOp %x, %y
foo.program %root, ... 

Notice how I would have to move the entire tree below %x and %y. Are there any tools for such operations that I missed ?
If I write my own pre-order traversal I can start from foo.program and when I get to foo.parentOp I can simply set the builder to be inside my block and that’s it.
However, I’ve never seen this scenario anywhere … so I don’t know …

It’s O(1) to move all preceding ops in a block into a region, so not out of the question to have each op construct its region and move all preceding ops into the region.

It sounds like the conversion you are trying to do is quite specific, and if this use-def chain → enclosing region transformation is the key part of it, then doing it outside the dialect conversion framework would make sense to me as well.

I think splicing ops from one block to another is O(n): each operation needs to have its parent pointer updated.

Yes - mlir::getForwardSlice.

I don’t see what the issue/weirdness with moving is. I assume you want the whole block go to bar.parentOp and so you have to move the block as opposed to individual ops. Even if it’s the latter (a subset of ops), they’ll have to anyway move.

If I’m not mistaken, dialect conversion uses pre-order (current upstream) and not post order. Also, within a block it’s top down so that defs are seen before uses. Please see OperationConverter::convertOperations in DialectConversion.cpp.

I see. In my scenario, I am using MLIR as a tree-like thing (with a graph-based region) which is why I had this skewed perspective on the visiting order where defs are the “children” of the “user” node and thus since they are converted first … we have a post-order in that sense, right?

In terms of SliceAnalysis, I didn’t know that, Thanks for pointing it out!
P.S.: What really worked for me though was the mlir::getBackwordSlice