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 21 class Operation; 22 23 /// Type of the condition to limit the propagation of transitive use-defs. 24 /// This can be used in particular to limit the propagation to a given Scope or 25 /// to avoid passing through certain types of operation in a configurable 26 /// manner. 27 using TransitiveFilter = std::function<bool(Operation *)>; 28 29 /// Fills `forwardSlice` with the computed forward slice (i.e. all 30 /// the transitive uses of op), **without** including that operation. 31 /// 32 /// This additionally takes a TransitiveFilter which acts as a frontier: 33 /// when looking at uses transitively, an operation that does not pass the 34 /// filter is never propagated through. This allows in particular to carve out 35 /// the scope within a ForInst or the scope within an IfInst. 36 /// 37 /// The implementation traverses the use chains in postorder traversal for 38 /// efficiency reasons: if an operation is already in `forwardSlice`, no 39 /// need to traverse its uses again. Since use-def chains form a DAG, this 40 /// terminates. 41 /// 42 /// Upon return to the root call, `forwardSlice` is filled with a 43 /// postorder list of uses (i.e. a reverse topological order). To get a proper 44 /// topological order, we just just reverse the order in `forwardSlice` before 45 /// returning. 46 /// 47 /// Example starting from node 0 48 /// ============================ 49 /// 50 /// 0 51 /// ___________|___________ 52 /// 1 2 3 4 53 /// |_______| |______| 54 /// | | | 55 /// | 5 6 56 /// |___|_____________| 57 /// | | 58 /// 7 8 59 /// |_______________| 60 /// | 61 /// 9 62 /// 63 /// Assuming all local orders match the numbering order: 64 /// 1. after getting back to the root getForwardSlice, `forwardSlice` may 65 /// contain: 66 /// {9, 7, 8, 5, 1, 2, 6, 3, 4} 67 /// 2. reversing the result of 1. gives: 68 /// {4, 3, 6, 2, 1, 5, 8, 7, 9} 69 /// 70 void getForwardSlice( 71 Operation *op, llvm::SetVector<Operation *> *forwardSlice, 72 TransitiveFilter filter = /* pass-through*/ 73 [](Operation *) { return true; }); 74 75 /// Fills `backwardSlice` with the computed backward slice (i.e. 76 /// all the transitive defs of op), **without** including that operation. 77 /// 78 /// This additionally takes a TransitiveFilter which acts as a frontier: 79 /// when looking at defs transitively, an operation that does not pass the 80 /// filter is never propagated through. This allows in particular to carve out 81 /// the scope within a ForInst or the scope within an IfInst. 82 /// 83 /// The implementation traverses the def chains in postorder traversal for 84 /// efficiency reasons: if an operation is already in `backwardSlice`, no 85 /// need to traverse its definitions again. Since useuse-def chains form a DAG, 86 /// this terminates. 87 /// 88 /// Upon return to the root call, `backwardSlice` is filled with a 89 /// postorder list of defs. This happens to be a topological order, from the 90 /// point of view of the use-def chains. 91 /// 92 /// Example starting from node 8 93 /// ============================ 94 /// 95 /// 1 2 3 4 96 /// |_______| |______| 97 /// | | | 98 /// | 5 6 99 /// |___|_____________| 100 /// | | 101 /// 7 8 102 /// |_______________| 103 /// | 104 /// 9 105 /// 106 /// Assuming all local orders match the numbering order: 107 /// {1, 2, 5, 3, 4, 6} 108 /// 109 void getBackwardSlice( 110 Operation *op, llvm::SetVector<Operation *> *backwardSlice, 111 TransitiveFilter filter = /* pass-through*/ 112 [](Operation *) { return true; }); 113 114 /// Iteratively computes backward slices and forward slices until 115 /// a fixed point is reached. Returns an `llvm::SetVector<Operation *>` which 116 /// **includes** the original operation. 117 /// 118 /// This allows building a slice (i.e. multi-root DAG where everything 119 /// that is reachable from an Value in forward and backward direction is 120 /// contained in the slice). 121 /// This is the abstraction we need to materialize all the operations for 122 /// supervectorization without worrying about orderings and Value 123 /// replacements. 124 /// 125 /// Example starting from any node 126 /// ============================== 127 /// 128 /// 1 2 3 4 129 /// |_______| |______| 130 /// | | | | 131 /// | 5 6___| 132 /// |___|_____________| | 133 /// | | | 134 /// 7 8 | 135 /// |_______________| | 136 /// | | 137 /// 9 10 138 /// 139 /// Return the whole DAG in some topological order. 140 /// 141 /// The implementation works by just filling up a worklist with iterative 142 /// alternate calls to `getBackwardSlice` and `getForwardSlice`. 143 /// 144 /// The following section describes some additional implementation 145 /// considerations for a potentially more efficient implementation but they are 146 /// just an intuition without proof, we still use a worklist for now. 147 /// 148 /// Additional implementation considerations 149 /// ======================================== 150 /// Consider the defs-op-uses hourglass. 151 /// ____ 152 /// \ / defs (in some topological order) 153 /// \/ 154 /// op 155 /// /\ 156 /// / \ uses (in some topological order) 157 /// /____\ 158 /// 159 /// We want to iteratively apply `getSlice` to construct the whole 160 /// list of Operation that are reachable by (use|def)+ from op. 161 /// We want the resulting slice in topological order. 162 /// Ideally we would like the ordering to be maintained in-place to avoid 163 /// copying Operation at each step. Keeping this ordering by construction 164 /// seems very unclear, so we list invariants in the hope of seeing whether 165 /// useful properties pop up. 166 /// 167 /// In the following: 168 /// we use |= for set inclusion; 169 /// we use << for set topological ordering (i.e. each pair is ordered). 170 /// 171 /// Assumption: 172 /// =========== 173 /// We wish to maintain the following property by a recursive argument: 174 /// """ 175 /// defs << {op} <<uses are in topological order. 176 /// """ 177 /// The property clearly holds for 0 and 1-sized uses and defs; 178 /// 179 /// Invariants: 180 /// 2. defs and uses are in topological order internally, by construction; 181 /// 3. for any {x} |= defs, defs(x) |= defs; because all go through op 182 /// 4. for any {x} |= uses, defs |= defs(x); because all go through op 183 /// 5. for any {x} |= defs, uses |= uses(x); because all go through op 184 /// 6. for any {x} |= uses, uses(x) |= uses; because all go through op 185 /// 186 /// Intuitively, we should be able to recurse like: 187 /// preorder(defs) - op - postorder(uses) 188 /// and keep things ordered but this is still hand-wavy and not worth the 189 /// trouble for now: punt to a simple worklist-based solution. 190 /// 191 llvm::SetVector<Operation *> getSlice( 192 Operation *op, 193 TransitiveFilter backwardFilter = /* pass-through*/ 194 [](Operation *) { return true; }, 195 TransitiveFilter forwardFilter = /* pass-through*/ 196 [](Operation *) { return true; }); 197 198 /// Multi-root DAG topological sort. 199 /// Performs a topological sort of the Operation in the `toSort` SetVector. 200 /// Returns a topologically sorted SetVector. 201 llvm::SetVector<Operation *> 202 topologicalSort(const llvm::SetVector<Operation *> &toSort); 203 204 } // end namespace mlir 205 206 #endif // MLIR_ANALYSIS_SLICEANALYSIS_H_ 207