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 | |
14 | namespace 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 | /// ``` |
88 | bool 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. |
94 | bool 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. |
103 | bool 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 | |