1 //===- SliceAnalysis.h - Analysis for Transitive UseDef chains --*- 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_SLICEANALYSIS_H_ 10 #define MLIR_ANALYSIS_SLICEANALYSIS_H_ 11 12 #include <functional> 13 #include <vector> 14 15 #include "mlir/Support/LLVM.h" 16 17 #include "llvm/ADT/SetVector.h" 18 19 namespace mlir { 20 class BlockArgument; 21 class Operation; 22 class Value; 23 24 /// Type of the condition to limit the propagation of transitive use-defs. 25 /// This can be used in particular to limit the propagation to a given Scope or 26 /// to avoid passing through certain types of operation in a configurable 27 /// manner. 28 using TransitiveFilter = llvm::function_ref<bool(Operation *)>; 29 30 /// Fills `forwardSlice` with the computed forward slice (i.e. all 31 /// the transitive uses of op), **without** including that operation. 32 /// 33 /// This additionally takes a TransitiveFilter which acts as a frontier: 34 /// when looking at uses transitively, an operation that does not pass the 35 /// filter is never propagated through. This allows in particular to carve out 36 /// the scope within a ForOp or the scope within an IfOp. 37 /// 38 /// The implementation traverses the use chains in postorder traversal for 39 /// efficiency reasons: if an operation is already in `forwardSlice`, no 40 /// need to traverse its uses again. Since use-def chains form a DAG, this 41 /// terminates. 42 /// 43 /// Upon return to the root call, `forwardSlice` is filled with a 44 /// postorder list of uses (i.e. a reverse topological order). To get a proper 45 /// topological order, we just just reverse the order in `forwardSlice` before 46 /// returning. 47 /// 48 /// Example starting from node 0 49 /// ============================ 50 /// 51 /// 0 52 /// ___________|___________ 53 /// 1 2 3 4 54 /// |_______| |______| 55 /// | | | 56 /// | 5 6 57 /// |___|_____________| 58 /// | | 59 /// 7 8 60 /// |_______________| 61 /// | 62 /// 9 63 /// 64 /// Assuming all local orders match the numbering order: 65 /// 1. after getting back to the root getForwardSlice, `forwardSlice` may 66 /// contain: 67 /// {9, 7, 8, 5, 1, 2, 6, 3, 4} 68 /// 2. reversing the result of 1. gives: 69 /// {4, 3, 6, 2, 1, 5, 8, 7, 9} 70 /// 71 void getForwardSlice(Operation *op, SetVector<Operation *> *forwardSlice, 72 TransitiveFilter filter = nullptr /* pass-through*/); 73 74 /// Value-rooted version of `getForwardSlice`. Return the union of all forward 75 /// slices for the uses of the value `root`. 76 void getForwardSlice(Value root, SetVector<Operation *> *forwardSlice, 77 TransitiveFilter filter = nullptr /* pass-through*/); 78 79 /// Fills `backwardSlice` with the computed backward slice (i.e. 80 /// all the transitive defs of op), **without** including that operation. 81 /// 82 /// This additionally takes a TransitiveFilter which acts as a frontier: 83 /// when looking at defs transitively, an operation that does not pass the 84 /// filter is never propagated through. This allows in particular to carve out 85 /// the scope within a ForOp or the scope within an IfOp. 86 /// 87 /// The implementation traverses the def chains in postorder traversal for 88 /// efficiency reasons: if an operation is already in `backwardSlice`, no 89 /// need to traverse its definitions again. Since useuse-def chains form a DAG, 90 /// this terminates. 91 /// 92 /// Upon return to the root call, `backwardSlice` is filled with a 93 /// postorder list of defs. This happens to be a topological order, from the 94 /// point of view of the use-def chains. 95 /// 96 /// Example starting from node 8 97 /// ============================ 98 /// 99 /// 1 2 3 4 100 /// |_______| |______| 101 /// | | | 102 /// | 5 6 103 /// |___|_____________| 104 /// | | 105 /// 7 8 106 /// |_______________| 107 /// | 108 /// 9 109 /// 110 /// Assuming all local orders match the numbering order: 111 /// {1, 2, 5, 3, 4, 6} 112 /// 113 void getBackwardSlice(Operation *op, SetVector<Operation *> *backwardSlice, 114 TransitiveFilter filter = nullptr /* pass-through*/); 115 116 /// Value-rooted version of `getBackwardSlice`. Return the union of all backward 117 /// slices for the op defining or owning the value `root`. 118 void getBackwardSlice(Value root, SetVector<Operation *> *backwardSlice, 119 TransitiveFilter filter = nullptr /* pass-through*/); 120 121 /// Iteratively computes backward slices and forward slices until 122 /// a fixed point is reached. Returns an `SetVector<Operation *>` which 123 /// **includes** the original operation. 124 /// 125 /// This allows building a slice (i.e. multi-root DAG where everything 126 /// that is reachable from an Value in forward and backward direction is 127 /// contained in the slice). 128 /// This is the abstraction we need to materialize all the operations for 129 /// supervectorization without worrying about orderings and Value 130 /// replacements. 131 /// 132 /// Example starting from any node 133 /// ============================== 134 /// 135 /// 1 2 3 4 136 /// |_______| |______| 137 /// | | | | 138 /// | 5 6___| 139 /// |___|_____________| | 140 /// | | | 141 /// 7 8 | 142 /// |_______________| | 143 /// | | 144 /// 9 10 145 /// 146 /// Return the whole DAG in some topological order. 147 /// 148 /// The implementation works by just filling up a worklist with iterative 149 /// alternate calls to `getBackwardSlice` and `getForwardSlice`. 150 /// 151 /// The following section describes some additional implementation 152 /// considerations for a potentially more efficient implementation but they are 153 /// just an intuition without proof, we still use a worklist for now. 154 /// 155 /// Additional implementation considerations 156 /// ======================================== 157 /// Consider the defs-op-uses hourglass. 158 /// ____ 159 /// \ / defs (in some topological order) 160 /// \/ 161 /// op 162 /// /\ 163 /// / \ uses (in some topological order) 164 /// /____\ 165 /// 166 /// We want to iteratively apply `getSlice` to construct the whole 167 /// list of Operation that are reachable by (use|def)+ from op. 168 /// We want the resulting slice in topological order. 169 /// Ideally we would like the ordering to be maintained in-place to avoid 170 /// copying Operation at each step. Keeping this ordering by construction 171 /// seems very unclear, so we list invariants in the hope of seeing whether 172 /// useful properties pop up. 173 /// 174 /// In the following: 175 /// we use |= for set inclusion; 176 /// we use << for set topological ordering (i.e. each pair is ordered). 177 /// 178 /// Assumption: 179 /// =========== 180 /// We wish to maintain the following property by a recursive argument: 181 /// """ 182 /// defs << {op} <<uses are in topological order. 183 /// """ 184 /// The property clearly holds for 0 and 1-sized uses and defs; 185 /// 186 /// Invariants: 187 /// 2. defs and uses are in topological order internally, by construction; 188 /// 3. for any {x} |= defs, defs(x) |= defs; because all go through op 189 /// 4. for any {x} |= uses, defs |= defs(x); because all go through op 190 /// 5. for any {x} |= defs, uses |= uses(x); because all go through op 191 /// 6. for any {x} |= uses, uses(x) |= uses; because all go through op 192 /// 193 /// Intuitively, we should be able to recurse like: 194 /// preorder(defs) - op - postorder(uses) 195 /// and keep things ordered but this is still hand-wavy and not worth the 196 /// trouble for now: punt to a simple worklist-based solution. 197 /// 198 SetVector<Operation *> 199 getSlice(Operation *op, 200 TransitiveFilter backwardFilter = nullptr /* pass-through*/, 201 TransitiveFilter forwardFilter = nullptr /* pass-through*/); 202 203 /// Multi-root DAG topological sort. 204 /// Performs a topological sort of the Operation in the `toSort` SetVector. 205 /// Returns a topologically sorted SetVector. 206 SetVector<Operation *> topologicalSort(const SetVector<Operation *> &toSort); 207 208 /// Utility to match a generic reduction given a list of iteration-carried 209 /// arguments, `iterCarriedArgs` and the position of the potential reduction 210 /// argument within the list, `redPos`. If a reduction is matched, returns the 211 /// reduced value and the topologically-sorted list of combiner operations 212 /// involved in the reduction. Otherwise, returns a null value. 213 /// 214 /// The matching algorithm relies on the following invariants, which are subject 215 /// to change: 216 /// 1. The first combiner operation must be a binary operation with the 217 /// iteration-carried value and the reduced value as operands. 218 /// 2. The iteration-carried value and combiner operations must be side 219 /// effect-free, have single result and a single use. 220 /// 3. Combiner operations must be immediately nested in the region op 221 /// performing the reduction. 222 /// 4. Reduction def-use chain must end in a terminator op that yields the 223 /// next iteration/output values in the same order as the iteration-carried 224 /// values in `iterCarriedArgs`. 225 /// 5. `iterCarriedArgs` must contain all the iteration-carried/output values 226 /// of the region op performing the reduction. 227 /// 228 /// This utility is generic enough to detect reductions involving multiple 229 /// combiner operations (disabled for now) across multiple dialects, including 230 /// Linalg, Affine and SCF. For the sake of genericity, it does not return 231 /// specific enum values for the combiner operations since its goal is also 232 /// matching reductions without pre-defined semantics in core MLIR. It's up to 233 /// each client to make sense out of the list of combiner operations. It's also 234 /// up to each client to check for additional invariants on the expected 235 /// reductions not covered by this generic matching. 236 Value matchReduction(ArrayRef<BlockArgument> iterCarriedArgs, unsigned redPos, 237 SmallVectorImpl<Operation *> &combinerOps); 238 239 } // namespace mlir 240 241 #endif // MLIR_ANALYSIS_SLICEANALYSIS_H_ 242