[mlir][transforms] Add a topological sort utility and pass
authorMogball <jeffniu22@gmail.com>
Mon, 16 May 2022 20:45:24 +0000 (20:45 +0000)
committerMogball <jeffniu22@gmail.com>
Mon, 16 May 2022 20:47:30 +0000 (20:47 +0000)
commitc8457eb5323ca99361c1748a22a16edb3160ae5f
treecc09238842505b1faacdca934067a9a3cb16d7fe
parentc38ef550de81631641cb1485e0641d1d2227dce4
[mlir][transforms] Add a topological sort utility and pass

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.

Reviewed By: mehdi_amini

Differential Revision: https://reviews.llvm.org/D125063
mlir/include/mlir/Transforms/Passes.h
mlir/include/mlir/Transforms/Passes.td
mlir/include/mlir/Transforms/TopologicalSortUtils.h [new file with mode: 0644]
mlir/lib/Transforms/CMakeLists.txt
mlir/lib/Transforms/TopologicalSort.cpp [new file with mode: 0644]
mlir/lib/Transforms/Utils/CMakeLists.txt
mlir/lib/Transforms/Utils/TopologicalSortUtils.cpp [new file with mode: 0644]
mlir/test/Transforms/test-toposort.mlir [new file with mode: 0644]