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