This is an archive of the discontinued LLVM Phabricator instance.

[mlir][transforms] Add topological sort analysis
ClosedPublic

Authored by springerm on Aug 11 2022, 4:49 AM.

Details

Summary

This change add a helper function for computing a topological sorting of a list of ops. E.g. this can be useful in transforms where a subset of ops should be cloned without dominance errors.

The analysis reuses the existing implementation in TopologicalSortUtils.cpp.

Diff Detail

Event Timeline

springerm created this revision.Aug 11 2022, 4:49 AM
springerm requested review of this revision.Aug 11 2022, 4:49 AM
Mogball requested changes to this revision.Aug 11 2022, 9:01 AM
Mogball added inline comments.
mlir/include/mlir/Transforms/TopologicalSortUtils.h
101–103

?

Otherwise, I'm not able to understand the comment.

104

I wouldn't use SmallVector if the number of ops being sorted is potentially large (is it)?

mlir/lib/Transforms/Utils/TopologicalSortUtils.cpp
58

Is ops expected to be small? If so, can you use SetVector<Operation *, SmallVector<Operation *>, SmallPtrSet<Operation *>>. Otherwise, it's fine as it is.

80

Erasing from a set vector is linear time

88

It seems like instead of using a SetVector and maintaining a separate list of sorted ops, you can use a DenseSet (like before) and accept a MutableArrayRef<Operation *> and swap sorted operations to the start of the list like in the other implementation.

96

nit: can you swap the definition of this function to be before the other? To match the header file.

mlir/test/Transforms/test-toposort.mlir
15

Can you add a test where a subrange of ops are sorted,or even a subset?

This revision now requires changes to proceed.Aug 11 2022, 9:01 AM
springerm updated this revision to Diff 452122.Aug 12 2022, 3:00 AM
springerm marked 7 inline comments as done.

address comments

mlir/lib/Transforms/Utils/TopologicalSortUtils.cpp
88

Switched to MutableArrayRef. The sort may no longer be stable though. (That's not a property that I need.) It's an array, not a linked list where I can move stuff around in a cheap way. Also mentioning that in the docs.

mlir/test/Transforms/test-toposort.mlir
15

I added a test with a subrange. Due to the swapping, the sort is no longer stable. Although if it's already sorted, nothing should change. (But it's not a property that is mentioned in the docs.) Should I add a test for that as well?

rriddle added inline comments.Aug 12 2022, 1:58 PM
mlir/test/lib/Transforms/TestTopologicalSort.cpp
10

This looks off.

address comments

springerm marked an inline comment as done.Aug 15 2022, 12:59 AM
Mogball added inline comments.Aug 15 2022, 10:15 AM
mlir/include/mlir/Transforms/TopologicalSortUtils.h
101

Can you clarify that the above sorts are stable?

mlir/test/Transforms/test-toposort.mlir
17

Can you remove the underscores from these attribute names? They aren't conflicting with anything

Mogball accepted this revision.Aug 15 2022, 11:03 AM

LGTM overall. If you don't need the sort to be stable, that's fine, but please make sure it's obvious that the other sorts are stable.

This revision is now accepted and ready to land.Aug 15 2022, 11:03 AM
springerm marked an inline comment as done.Aug 15 2022, 12:04 PM
springerm added inline comments.
mlir/include/mlir/Transforms/TopologicalSortUtils.h
101

Added a comment to one of the above functions (the other one already had one).

springerm marked an inline comment as done.

address comments

This revision was landed with ongoing or failed builds.Aug 15 2022, 12:10 PM
This revision was automatically updated to reflect the committed changes.