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 /// ``` 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 /// Gets a list of blocks that is sorted according to dominance. This sort is 108 /// stable. 109 SetVector<Block *> getBlocksSortedByDominance(Region ®ion); 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 118