1//===- TopologicalSortUtils.h - Topological sort utilities ------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef MLIR_TRANSFORMS_TOPOLOGICALSORTUTILS_H
10#define MLIR_TRANSFORMS_TOPOLOGICALSORTUTILS_H
11
12#include "mlir/IR/Block.h"
13
14namespace mlir {
15
16/// Given a block, sort a range operations in said block in topological order.
17/// The main purpose is readability of graph regions, potentially faster
18/// processing of certain transformations and analyses, or fixing the SSA
19/// dominance of blocks that require it after transformations. The function
20/// sorts the given operations such that, as much as possible, all users appear
21/// after their producers.
22///
23/// For example:
24///
25/// ```mlir
26/// %0 = test.foo
27/// %1 = test.bar %0, %2
28/// %2 = test.baz
29/// ```
30///
31/// Will become:
32///
33/// ```mlir
34/// %0 = test.foo
35/// %1 = test.baz
36/// %2 = test.bar %0, %1
37/// ```
38///
39/// The sort also works on operations with regions and implicit captures. For
40/// example:
41///
42/// ```mlir
43/// %0 = test.foo {
44/// test.baz %1
45/// %1 = test.bar %2
46/// }
47/// %2 = test.foo
48/// ```
49///
50/// Will become:
51///
52/// ```mlir
53/// %0 = test.foo
54/// %1 = test.foo {
55/// test.baz %2
56/// %2 = test.bar %0
57/// }
58/// ```
59///
60/// Note that the sort is not recursive on nested regions. This sort is stable;
61/// if the operations are already topologically sorted, nothing changes.
62///
63/// Operations that form cycles are moved to the end of the block in order. If
64/// the sort is left with only operations that form a cycle, it breaks the cycle
65/// by marking the first encountered operation as ready and moving on.
66///
67/// The function optionally accepts a callback that can be provided by users to
68/// virtually break cycles early. It is called on top-level operations in the
69/// block with value uses at or below those operations. The function should
70/// return true to mark that value as ready to be scheduled.
71///
72/// For example, if `isOperandReady` is set to always mark edges from `foo.A` to
73/// `foo.B` as ready, these operations:
74///
75/// ```mlir
76/// %0 = foo.B(%1)
77/// %1 = foo.C(%2)
78/// %2 = foo.A(%0)
79/// ```
80///
81/// Are sorted as:
82///
83/// ```mlir
84/// %0 = foo.A(%2)
85/// %1 = foo.C(%0)
86/// %2 = foo.B(%1)
87/// ```
88bool sortTopologically(
89 Block *block, iterator_range<Block::iterator> ops,
90 function_ref<bool(Value, Operation *)> isOperandReady = nullptr);
91
92/// Given a block, sort its operations in topological order, excluding its
93/// terminator if it has one. This sort is stable.
94bool sortTopologically(
95 Block *block,
96 function_ref<bool(Value, Operation *)> isOperandReady = nullptr);
97
98/// Compute a topological ordering of the given ops. This sort is not stable.
99///
100/// Note: If the specified ops contain incomplete/interrupted SSA use-def
101/// chains, the result may not actually be a topological sorting with respect to
102/// the entire program.
103bool computeTopologicalSorting(
104 MutableArrayRef<Operation *> ops,
105 function_ref<bool(Value, Operation *)> isOperandReady = nullptr);
106
107} // end namespace mlir
108
109#endif // MLIR_TRANSFORMS_TOPOLOGICALSORTUTILS_H
110

source code of mlir/include/mlir/Transforms/TopologicalSortUtils.h