MLIR  16.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 
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 ///
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.
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_
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:31
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
Include the generated interface declarations.
void getBackwardSlice(Operation *op, SetVector< Operation * > *backwardSlice, TransitiveFilter filter=nullptr)
Fills backwardSlice with the computed backward slice (i.e.
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...
void getForwardSlice(Operation *op, SetVector< Operation * > *forwardSlice, TransitiveFilter filter=nullptr)
Fills forwardSlice with the computed forward slice (i.e.
SetVector< Operation * > getSlice(Operation *op, TransitiveFilter backwardFilter=nullptr, TransitiveFilter forwardFilter=nullptr)
Iteratively computes backward slices and forward slices until a fixed point is reached.
SetVector< Operation * > topologicalSort(const SetVector< Operation * > &toSort)
Multi-root DAG topological sort.