Is there a ready-made interface or reference code to realize topological sorting of funcOp?

Is there a ready-made interface or reference code to realize topological sorting of funcOp?

There isn’t anything readily available for a FuncOp but you can see mlir::topologicalSort in include/mlir/Analysis/SliceAnalysis.h. I think this method should be renamed to be more descriptive.

Thank you very much. The mlir::topologicalSort function contains the algorithm of topological sorting. but I want to know how to resort the block’s operations in place. I have known the “splice” interface can transfer an operation to another block, but I want to know how to move an operation to another position in the same block. I don’t know if I describe what I mean.

I think most uses of llvm’s ilist types just construct a new list. If you want to move an operation inside of the same list though, you can presumably just remove followed by insert.

1 Like

you can presumably just remove followed by insert .

The Operation class has convenient API for this: void moveBefore(Operation *existingOp); and void moveBefore(Block *block, llvm::iplist<Operation>::iterator iterator); (and the same with moveAfter instead)

Is there a ready-made interface or reference code to realize topological sorting of funcOp?

The question is a bit ambiguous:

  • you may want to topologically sort operations in blocks (but they are already when it is in a FuncOp otherwise the IR is invalid!
  • You may want to sort blocks inside a function.
  • You may want to sort Functions in a module according to the calligraph.

I see, thank you very much.

I think that method could use some more mileage on it too: a few of us have found it to have some quite bad behavior with more than trivial numbers of ops (ie . Allocating gb of memory, etc) when I hit this I didn’t have a reduced repro.

1 Like

Oh wow indeed: the interface in this method is quite heavy. I suspect most users don’t need to sort across blocks for example, which I suspect could lead to a much faster implementation. It also does not document the behavior with respect to cycles in the SSA graph.

Yeah that function was implemented at the time of MLFuncs, pre-regions and pre-‘s/instruction/operation/g’ for the specific purpose of ordering the results of forward and backward slice computation so they can be traversed in proper def-use order.

We definitely want a new version.

I tried to add an assertion that we’re only sorting inside a block, but it fails: the affine super vectorizer seems to use this for nested loops right now.

I’m not sure what’s the best algorithm right now, but I’m also not sure what is the desired behavior. For example with:

%A = A()
%Aprime = if (...) {
   yield %a
}
B(%Aprime)

If provided with operations A and B as inputs, are we supposed to consider that there is an edge between them here?

(maybe think about moving this to affine or otherwise commenting about its limitations? Multiple of us have found it and stubbed toes on it at this point)