MLIR  16.0.0git
SliceAnalysis.cpp
Go to the documentation of this file.
1 //===- UseDefAnalysis.cpp - Analysis for Transitive UseDef chains ---------===//
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 // This file implements Analysis functions specific to slicing in Function.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "mlir/IR/BuiltinOps.h"
15 #include "mlir/IR/Operation.h"
17 #include "mlir/Support/LLVM.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 
21 ///
22 /// Implements Analysis functions specific to slicing in Function.
23 ///
24 
25 using namespace mlir;
26 
28  SetVector<Operation *> *forwardSlice,
29  TransitiveFilter filter) {
30  if (!op)
31  return;
32 
33  // Evaluate whether we should keep this use.
34  // This is useful in particular to implement scoping; i.e. return the
35  // transitive forwardSlice in the current scope.
36  if (filter && !filter(op))
37  return;
38 
39  for (Region &region : op->getRegions())
40  for (Block &block : region)
41  for (Operation &blockOp : block)
42  if (forwardSlice->count(&blockOp) == 0)
43  getForwardSliceImpl(&blockOp, forwardSlice, filter);
44  for (Value result : op->getResults()) {
45  for (Operation *userOp : result.getUsers())
46  if (forwardSlice->count(userOp) == 0)
47  getForwardSliceImpl(userOp, forwardSlice, filter);
48  }
49 
50  forwardSlice->insert(op);
51 }
52 
54  TransitiveFilter filter) {
55  getForwardSliceImpl(op, forwardSlice, filter);
56  // Don't insert the top level operation, we just queried on it and don't
57  // want it in the results.
58  forwardSlice->remove(op);
59 
60  // Reverse to get back the actual topological order.
61  // std::reverse does not work out of the box on SetVector and I want an
62  // in-place swap based thing (the real std::reverse, not the LLVM adapter).
63  std::vector<Operation *> v(forwardSlice->takeVector());
64  forwardSlice->insert(v.rbegin(), v.rend());
65 }
66 
68  TransitiveFilter filter) {
69  for (Operation *user : root.getUsers())
70  getForwardSliceImpl(user, forwardSlice, filter);
71 
72  // Reverse to get back the actual topological order.
73  // std::reverse does not work out of the box on SetVector and I want an
74  // in-place swap based thing (the real std::reverse, not the LLVM adapter).
75  std::vector<Operation *> v(forwardSlice->takeVector());
76  forwardSlice->insert(v.rbegin(), v.rend());
77 }
78 
80  SetVector<Operation *> *backwardSlice,
81  TransitiveFilter filter) {
82  if (!op || op->hasTrait<OpTrait::IsIsolatedFromAbove>())
83  return;
84 
85  // Evaluate whether we should keep this def.
86  // This is useful in particular to implement scoping; i.e. return the
87  // transitive backwardSlice in the current scope.
88  if (filter && !filter(op))
89  return;
90 
91  for (const auto &en : llvm::enumerate(op->getOperands())) {
92  auto operand = en.value();
93  if (auto *definingOp = operand.getDefiningOp()) {
94  if (backwardSlice->count(definingOp) == 0)
95  getBackwardSliceImpl(definingOp, backwardSlice, filter);
96  } else if (auto blockArg = operand.dyn_cast<BlockArgument>()) {
97  Block *block = blockArg.getOwner();
98  Operation *parentOp = block->getParentOp();
99  // TODO: determine whether we want to recurse backward into the other
100  // blocks of parentOp, which are not technically backward unless they flow
101  // into us. For now, just bail.
102  if (parentOp && backwardSlice->count(parentOp) == 0) {
103  assert(parentOp->getNumRegions() == 1 &&
104  parentOp->getRegion(0).getBlocks().size() == 1);
105  getBackwardSliceImpl(parentOp, backwardSlice, filter);
106  }
107  } else {
108  llvm_unreachable("No definingOp and not a block argument.");
109  }
110  }
111 
112  backwardSlice->insert(op);
113 }
114 
116  SetVector<Operation *> *backwardSlice,
117  TransitiveFilter filter) {
118  getBackwardSliceImpl(op, backwardSlice, filter);
119 
120  // Don't insert the top level operation, we just queried on it and don't
121  // want it in the results.
122  backwardSlice->remove(op);
123 }
124 
126  TransitiveFilter filter) {
127  if (Operation *definingOp = root.getDefiningOp()) {
128  getBackwardSlice(definingOp, backwardSlice, filter);
129  return;
130  }
131  Operation *bbAargOwner = root.cast<BlockArgument>().getOwner()->getParentOp();
132  getBackwardSlice(bbAargOwner, backwardSlice, filter);
133 }
134 
136  TransitiveFilter backwardFilter,
137  TransitiveFilter forwardFilter) {
139  slice.insert(op);
140 
141  unsigned currentIndex = 0;
142  SetVector<Operation *> backwardSlice;
143  SetVector<Operation *> forwardSlice;
144  while (currentIndex != slice.size()) {
145  auto *currentOp = (slice)[currentIndex];
146  // Compute and insert the backwardSlice starting from currentOp.
147  backwardSlice.clear();
148  getBackwardSlice(currentOp, &backwardSlice, backwardFilter);
149  slice.insert(backwardSlice.begin(), backwardSlice.end());
150 
151  // Compute and insert the forwardSlice starting from currentOp.
152  forwardSlice.clear();
153  getForwardSlice(currentOp, &forwardSlice, forwardFilter);
154  slice.insert(forwardSlice.begin(), forwardSlice.end());
155  ++currentIndex;
156  }
157  return topologicalSort(slice);
158 }
159 
160 namespace {
161 /// DFS post-order implementation that maintains a global count to work across
162 /// multiple invocations, to help implement topological sort on multi-root DAGs.
163 /// We traverse all operations but only record the ones that appear in
164 /// `toSort` for the final result.
165 struct DFSState {
166  DFSState(const SetVector<Operation *> &set) : toSort(set), seen() {}
167  const SetVector<Operation *> &toSort;
168  SmallVector<Operation *, 16> topologicalCounts;
170 };
171 } // namespace
172 
173 static void dfsPostorder(Operation *root, DFSState *state) {
174  SmallVector<Operation *> queue(1, root);
175  std::vector<Operation *> ops;
176  while (!queue.empty()) {
177  Operation *current = queue.pop_back_val();
178  ops.push_back(current);
179  for (Value result : current->getResults()) {
180  for (Operation *op : result.getUsers())
181  queue.push_back(op);
182  }
183  for (Region &region : current->getRegions()) {
184  for (Operation &op : region.getOps())
185  queue.push_back(&op);
186  }
187  }
188 
189  for (Operation *op : llvm::reverse(ops)) {
190  if (state->seen.insert(op).second && state->toSort.count(op) > 0)
191  state->topologicalCounts.push_back(op);
192  }
193 }
194 
197  if (toSort.empty()) {
198  return toSort;
199  }
200 
201  // Run from each root with global count and `seen` set.
202  DFSState state(toSort);
203  for (auto *s : toSort) {
204  assert(toSort.count(s) == 1 && "NYI: multi-sets not supported");
205  dfsPostorder(s, &state);
206  }
207 
208  // Reorder and return.
210  for (auto it = state.topologicalCounts.rbegin(),
211  eit = state.topologicalCounts.rend();
212  it != eit; ++it) {
213  res.insert(*it);
214  }
215  return res;
216 }
217 
218 /// Returns true if `value` (transitively) depends on iteration-carried values
219 /// of the given `ancestorOp`.
221  ArrayRef<BlockArgument> iterCarriedArgs,
222  Operation *ancestorOp) {
223  // Compute the backward slice of the value.
225  getBackwardSlice(value, &slice,
226  [&](Operation *op) { return !ancestorOp->isAncestor(op); });
227 
228  // Check that none of the operands of the operations in the backward slice are
229  // loop iteration arguments, and neither is the value itself.
230  SmallPtrSet<Value, 8> iterCarriedValSet(iterCarriedArgs.begin(),
231  iterCarriedArgs.end());
232  if (iterCarriedValSet.contains(value))
233  return true;
234 
235  for (Operation *op : slice)
236  for (Value operand : op->getOperands())
237  if (iterCarriedValSet.contains(operand))
238  return true;
239 
240  return false;
241 }
242 
243 /// Utility to match a generic reduction given a list of iteration-carried
244 /// arguments, `iterCarriedArgs` and the position of the potential reduction
245 /// argument within the list, `redPos`. If a reduction is matched, returns the
246 /// reduced value and the topologically-sorted list of combiner operations
247 /// involved in the reduction. Otherwise, returns a null value.
248 ///
249 /// The matching algorithm relies on the following invariants, which are subject
250 /// to change:
251 /// 1. The first combiner operation must be a binary operation with the
252 /// iteration-carried value and the reduced value as operands.
253 /// 2. The iteration-carried value and combiner operations must be side
254 /// effect-free, have single result and a single use.
255 /// 3. Combiner operations must be immediately nested in the region op
256 /// performing the reduction.
257 /// 4. Reduction def-use chain must end in a terminator op that yields the
258 /// next iteration/output values in the same order as the iteration-carried
259 /// values in `iterCarriedArgs`.
260 /// 5. `iterCarriedArgs` must contain all the iteration-carried/output values
261 /// of the region op performing the reduction.
262 ///
263 /// This utility is generic enough to detect reductions involving multiple
264 /// combiner operations (disabled for now) across multiple dialects, including
265 /// Linalg, Affine and SCF. For the sake of genericity, it does not return
266 /// specific enum values for the combiner operations since its goal is also
267 /// matching reductions without pre-defined semantics in core MLIR. It's up to
268 /// each client to make sense out of the list of combiner operations. It's also
269 /// up to each client to check for additional invariants on the expected
270 /// reductions not covered by this generic matching.
272  unsigned redPos,
273  SmallVectorImpl<Operation *> &combinerOps) {
274  assert(redPos < iterCarriedArgs.size() && "'redPos' is out of bounds");
275 
276  BlockArgument redCarriedVal = iterCarriedArgs[redPos];
277  if (!redCarriedVal.hasOneUse())
278  return nullptr;
279 
280  // For now, the first combiner op must be a binary op.
281  Operation *combinerOp = *redCarriedVal.getUsers().begin();
282  if (combinerOp->getNumOperands() != 2)
283  return nullptr;
284  Value reducedVal = combinerOp->getOperand(0) == redCarriedVal
285  ? combinerOp->getOperand(1)
286  : combinerOp->getOperand(0);
287 
288  Operation *redRegionOp =
289  iterCarriedArgs.front().getOwner()->getParent()->getParentOp();
290  if (dependsOnCarriedVals(reducedVal, iterCarriedArgs, redRegionOp))
291  return nullptr;
292 
293  // Traverse the def-use chain starting from the first combiner op until a
294  // terminator is found. Gather all the combiner ops along the way in
295  // topological order.
296  while (!combinerOp->mightHaveTrait<OpTrait::IsTerminator>()) {
297  if (!isMemoryEffectFree(combinerOp) || combinerOp->getNumResults() != 1 ||
298  !combinerOp->hasOneUse() || combinerOp->getParentOp() != redRegionOp)
299  return nullptr;
300 
301  combinerOps.push_back(combinerOp);
302  combinerOp = *combinerOp->getUsers().begin();
303  }
304 
305  // Limit matching to single combiner op until we can properly test reductions
306  // involving multiple combiners.
307  if (combinerOps.size() != 1)
308  return nullptr;
309 
310  // Check that the yielded value is in the same position as in
311  // `iterCarriedArgs`.
312  Operation *terminatorOp = combinerOp;
313  if (terminatorOp->getOperand(redPos) != combinerOps.back()->getResults()[0])
314  return nullptr;
315 
316  return reducedVal;
317 }
static constexpr const bool value
static void getForwardSliceImpl(Operation *op, SetVector< Operation * > *forwardSlice, TransitiveFilter filter)
static bool dependsOnCarriedVals(Value value, ArrayRef< BlockArgument > iterCarriedArgs, Operation *ancestorOp)
Returns true if value (transitively) depends on iteration-carried values of the given ancestorOp.
static void getBackwardSliceImpl(Operation *op, SetVector< Operation * > *backwardSlice, TransitiveFilter filter)
static void dfsPostorder(Operation *root, DFSState *state)
This class represents an argument of a Block.
Definition: Value.h:296
Block represents an ordered list of Operations.
Definition: Block.h:30
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
This class provides the API for ops that are known to be isolated from above.
This class provides the API for ops that are known to be terminators.
Definition: OpDefinition.h:701
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:31
Value getOperand(unsigned idx)
Definition: Operation.h:267
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:528
bool mightHaveTrait()
Returns true if the operation might have the provided trait.
Definition: Operation.h:536
bool hasOneUse()
Returns true if this operation has exactly one use.
Definition: Operation.h:626
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition: Operation.h:477
unsigned getNumOperands()
Definition: Operation.h:263
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:165
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
Definition: Operation.h:486
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:480
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:295
bool isAncestor(Operation *other)
Return true if this operation is an ancestor of the other operation.
Definition: Operation.h:194
user_range getUsers()
Returns a range of all users.
Definition: Operation.h:650
result_range getResults()
Definition: Operation.h:332
unsigned getNumResults()
Return the number of results held by this operation.
Definition: Operation.h:321
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
BlockListType & getBlocks()
Definition: Region.h:45
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
U cast() const
Definition: Value.h:105
user_range getUsers() const
Definition: Value.h:209
bool hasOneUse() const
Returns true if this value has exactly one use.
Definition: Value.h:196
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:230
Include the generated interface declarations.
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
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.