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