This is an archive of the discontinued LLVM Phabricator instance.

[mlir][transforms] Add a topological sort utility and pass
ClosedPublic

Authored by Mogball on May 5 2022, 6:41 PM.

Details

Summary

This patch adds a topological sort utility and pass. A topological sort reorders
the operations in a block without SSA dominance such that, as much as possible,
users of values come after their producers.

The utility function sorts topologically the operation range in a given block
with an optional user-provided callback that can be used to virtually break cycles.
The toposort pass itself recursively sorts graph regions under the target op.

Diff Detail

Event Timeline

Mogball created this revision.May 5 2022, 6:41 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 5 2022, 6:41 PM
Mogball requested review of this revision.May 5 2022, 6:41 PM

Context: this pass was sitting around internally and since it's not anything specific, thought I'd upstream it

rriddle added inline comments.May 5 2022, 8:26 PM
mlir/test/lib/Dialect/Test/TestDialect.cpp
725 ↗(On Diff #427506)

Can you split this out into an NFC and submit separately?

There is also the pre-existing mlir::topologicalSort which we should either rename or make private (given that it isn't great).

mlir/include/mlir/Transforms/TopologicalSortUtils.h
17

The missing SSA dominance is fairly significant of a limitation. I feel like a lot of people are going to want to use this, and then get burned immediately. We should either rename this, or add proper asserts before executing.

Also, this seems to completely disregard side effects?

mlir/lib/Transforms/TopologicalSort.cpp
17–27

Honestly I'd just inline this function into the single use.

mehdi_amini added inline comments.May 5 2022, 10:19 PM
mlir/include/mlir/Transforms/Passes.td
270

Please document that this is a stable sort (nothing changes if the block is already topo-sorted right?) and the behavior for cycles.

mlir/include/mlir/Transforms/TopologicalSortUtils.h
17

Should we say "Given a block in a Graph Region" instead of "without SSA dominance"?

Also, this seems to completely disregard side effects?

In a Graph-region there is no implicit ordering, am I missing something?

70

Can you document the callback?
Also function_ref can be "null", would it be an OK default and handling it in the code instead of calling it?

70

Also what is the use-case for the callback?

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

This isn't handling ops with region and implicit captures I believe.

rriddle added inline comments.May 5 2022, 10:22 PM
mlir/include/mlir/Transforms/TopologicalSortUtils.h
17

You're right, I forgot that we explicitly codified that operations can be freely reordered.

Mogball added inline comments.May 6 2022, 9:19 AM
mlir/include/mlir/Transforms/TopologicalSortUtils.h
17

Is there a difference in meaning to say "Block in a Graph Region" vs. "without SSA dominance"?

70

The sort will break cycles once all other ops have been scheduled and will break the cycle at the first op it encounters (top-down) in the cycle. This callback allows cycles to be broken early in special cases (e.g. NextIteration into Merge)

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

Can you elaborate on the particular case that isn't handled?

I added two tests below, one which is implicit capture of an SSA value from a predecessor block and another is implicit capture of values defined above the region.

mehdi_amini added inline comments.May 6 2022, 12:33 PM
mlir/include/mlir/Transforms/TopologicalSortUtils.h
17

Better naming positively (what it is) than negatively (what it isn't) and Graph Region is the name used in the doc: https://mlir.llvm.org/docs/LangRef/#graph-regions

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

should be ok indeed

Mogball updated this revision to Diff 428856.May 11 2022, 9:51 PM

split out TestOps change as NFC

Mogball added inline comments.May 11 2022, 10:04 PM
mlir/include/mlir/Transforms/TopologicalSortUtils.h
17

What would be the purpose of running this on a block with SSA dominance?

mehdi_amini added inline comments.May 12 2022, 1:33 AM
mlir/include/mlir/Transforms/TopologicalSortUtils.h
17

I had such need once though where I would perform a transform (I don't remember what) and it what more convenient to just append always to the block and toposort later.

Mogball added inline comments.May 13 2022, 10:07 AM
mlir/include/mlir/Transforms/TopologicalSortUtils.h
17

Ah, interesting. There's no actual restriction that the block be in a graph region so I can drop that requirement from the documentation.

Mogball updated this revision to Diff 429398.May 13 2022, 6:30 PM
Mogball marked 11 inline comments as done.

review comments, and drop requirement that blocks need to not have SSA dominance

mehdi_amini accepted this revision.May 16 2022, 8:13 AM
This revision is now accepted and ready to land.May 16 2022, 8:13 AM
Mogball updated this revision to Diff 429838.May 16 2022, 1:47 PM

fix cmake build

This revision was landed with ongoing or failed builds.May 16 2022, 1:47 PM
This revision was automatically updated to reflect the committed changes.
rriddle added inline comments.May 16 2022, 1:56 PM
mlir/lib/Transforms/Utils/TopologicalSortUtils.cpp
15

nit: Can you drop the llvm:: here?

31

nit: Drop the const here.