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