MLIR  20.0.0git
TopologicalSortUtils.h
Go to the documentation of this file.
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_ANALYSIS_TOPOLOGICALSORTUTILS_H
10 #define MLIR_ANALYSIS_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 /// ```
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.
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.
104  MutableArrayRef<Operation *> ops,
105  function_ref<bool(Value, Operation *)> isOperandReady = nullptr);
106 
107 /// Gets a list of blocks that is sorted according to dominance. This sort is
108 /// stable.
109 SetVector<Block *> getBlocksSortedByDominance(Region &region);
110 
111 /// Sorts all operations in `toSort` topologically while also considering region
112 /// semantics. Does not support multi-sets.
113 SetVector<Operation *> topologicalSort(const SetVector<Operation *> &toSort);
114 
115 } // end namespace mlir
116 
117 #endif // MLIR_ANALYSIS_TOPOLOGICALSORTUTILS_H
Include the generated interface declarations.
llvm::function_ref< Fn > function_ref
Definition: LLVM.h:152
SetVector< Block * > getBlocksSortedByDominance(Region &region)
Gets a list of blocks that is sorted according to dominance.
bool computeTopologicalSorting(MutableArrayRef< Operation * > ops, function_ref< bool(Value, Operation *)> isOperandReady=nullptr)
Compute a topological ordering of the given ops.
bool sortTopologically(Block *block, iterator_range< Block::iterator > ops, function_ref< bool(Value, Operation *)> isOperandReady=nullptr)
Given a block, sort a range operations in said block in topological order.
SetVector< Operation * > topologicalSort(const SetVector< Operation * > &toSort)
Sorts all operations in toSort topologically while also considering region semantics.