MLIR  19.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 
15 #include "mlir/IR/Block.h"
16 #include "mlir/IR/Operation.h"
18 #include "mlir/Support/LLVM.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 
22 ///
23 /// Implements Analysis functions specific to slicing in Function.
24 ///
25 
26 using namespace mlir;
27 
28 static void
30  const SliceOptions::TransitiveFilter &filter = nullptr) {
31  if (!op)
32  return;
33 
34  // Evaluate whether we should keep this use.
35  // This is useful in particular to implement scoping; i.e. return the
36  // transitive forwardSlice in the current scope.
37  if (filter && !filter(op))
38  return;
39 
40  for (Region &region : op->getRegions())
41  for (Block &block : region)
42  for (Operation &blockOp : block)
43  if (forwardSlice->count(&blockOp) == 0)
44  getForwardSliceImpl(&blockOp, forwardSlice, filter);
45  for (Value result : op->getResults()) {
46  for (Operation *userOp : result.getUsers())
47  if (forwardSlice->count(userOp) == 0)
48  getForwardSliceImpl(userOp, forwardSlice, filter);
49  }
50 
51  forwardSlice->insert(op);
52 }
53 
56  getForwardSliceImpl(op, forwardSlice, options.filter);
57  if (!options.inclusive) {
58  // Don't insert the top level operation, we just queried on it and don't
59  // want it in the results.
60  forwardSlice->remove(op);
61  }
62 
63  // Reverse to get back the actual topological order.
64  // std::reverse does not work out of the box on SetVector and I want an
65  // in-place swap based thing (the real std::reverse, not the LLVM adapter).
66  SmallVector<Operation *, 0> v(forwardSlice->takeVector());
67  forwardSlice->insert(v.rbegin(), v.rend());
68 }
69 
71  const SliceOptions &options) {
72  for (Operation *user : root.getUsers())
73  getForwardSliceImpl(user, forwardSlice, options.filter);
74 
75  // Reverse to get back the actual topological order.
76  // std::reverse does not work out of the box on SetVector and I want an
77  // in-place swap based thing (the real std::reverse, not the LLVM adapter).
78  SmallVector<Operation *, 0> v(forwardSlice->takeVector());
79  forwardSlice->insert(v.rbegin(), v.rend());
80 }
81 
83  SetVector<Operation *> *backwardSlice,
85  if (!op || op->hasTrait<OpTrait::IsIsolatedFromAbove>())
86  return;
87 
88  // Evaluate whether we should keep this def.
89  // This is useful in particular to implement scoping; i.e. return the
90  // transitive backwardSlice in the current scope.
91  if (options.filter && !options.filter(op))
92  return;
93 
94  for (const auto &en : llvm::enumerate(op->getOperands())) {
95  auto operand = en.value();
96  if (auto *definingOp = operand.getDefiningOp()) {
97  if (backwardSlice->count(definingOp) == 0)
98  getBackwardSliceImpl(definingOp, backwardSlice, options);
99  } else if (auto blockArg = dyn_cast<BlockArgument>(operand)) {
100  if (options.omitBlockArguments)
101  continue;
102 
103  Block *block = blockArg.getOwner();
104  Operation *parentOp = block->getParentOp();
105  // TODO: determine whether we want to recurse backward into the other
106  // blocks of parentOp, which are not technically backward unless they flow
107  // into us. For now, just bail.
108  if (parentOp && backwardSlice->count(parentOp) == 0) {
109  assert(parentOp->getNumRegions() == 1 &&
110  parentOp->getRegion(0).getBlocks().size() == 1);
111  getBackwardSliceImpl(parentOp, backwardSlice, options);
112  }
113  } else {
114  llvm_unreachable("No definingOp and not a block argument.");
115  }
116  }
117 
118  backwardSlice->insert(op);
119 }
120 
122  SetVector<Operation *> *backwardSlice,
123  const BackwardSliceOptions &options) {
124  getBackwardSliceImpl(op, backwardSlice, options);
125 
126  if (!options.inclusive) {
127  // Don't insert the top level operation, we just queried on it and don't
128  // want it in the results.
129  backwardSlice->remove(op);
130  }
131 }
132 
134  const BackwardSliceOptions &options) {
135  if (Operation *definingOp = root.getDefiningOp()) {
136  getBackwardSlice(definingOp, backwardSlice, options);
137  return;
138  }
139  Operation *bbAargOwner = cast<BlockArgument>(root).getOwner()->getParentOp();
140  getBackwardSlice(bbAargOwner, backwardSlice, options);
141 }
142 
144 mlir::getSlice(Operation *op, const BackwardSliceOptions &backwardSliceOptions,
145  const ForwardSliceOptions &forwardSliceOptions) {
147  slice.insert(op);
148 
149  unsigned currentIndex = 0;
150  SetVector<Operation *> backwardSlice;
151  SetVector<Operation *> forwardSlice;
152  while (currentIndex != slice.size()) {
153  auto *currentOp = (slice)[currentIndex];
154  // Compute and insert the backwardSlice starting from currentOp.
155  backwardSlice.clear();
156  getBackwardSlice(currentOp, &backwardSlice, backwardSliceOptions);
157  slice.insert(backwardSlice.begin(), backwardSlice.end());
158 
159  // Compute and insert the forwardSlice starting from currentOp.
160  forwardSlice.clear();
161  getForwardSlice(currentOp, &forwardSlice, forwardSliceOptions);
162  slice.insert(forwardSlice.begin(), forwardSlice.end());
163  ++currentIndex;
164  }
165  return topologicalSort(slice);
166 }
167 
168 /// Returns true if `value` (transitively) depends on iteration-carried values
169 /// of the given `ancestorOp`.
170 static bool dependsOnCarriedVals(Value value,
171  ArrayRef<BlockArgument> iterCarriedArgs,
172  Operation *ancestorOp) {
173  // Compute the backward slice of the value.
175  BackwardSliceOptions sliceOptions;
176  sliceOptions.filter = [&](Operation *op) {
177  return !ancestorOp->isAncestor(op);
178  };
179  getBackwardSlice(value, &slice, sliceOptions);
180 
181  // Check that none of the operands of the operations in the backward slice are
182  // loop iteration arguments, and neither is the value itself.
183  SmallPtrSet<Value, 8> iterCarriedValSet(iterCarriedArgs.begin(),
184  iterCarriedArgs.end());
185  if (iterCarriedValSet.contains(value))
186  return true;
187 
188  for (Operation *op : slice)
189  for (Value operand : op->getOperands())
190  if (iterCarriedValSet.contains(operand))
191  return true;
192 
193  return false;
194 }
195 
196 /// Utility to match a generic reduction given a list of iteration-carried
197 /// arguments, `iterCarriedArgs` and the position of the potential reduction
198 /// argument within the list, `redPos`. If a reduction is matched, returns the
199 /// reduced value and the topologically-sorted list of combiner operations
200 /// involved in the reduction. Otherwise, returns a null value.
201 ///
202 /// The matching algorithm relies on the following invariants, which are subject
203 /// to change:
204 /// 1. The first combiner operation must be a binary operation with the
205 /// iteration-carried value and the reduced value as operands.
206 /// 2. The iteration-carried value and combiner operations must be side
207 /// effect-free, have single result and a single use.
208 /// 3. Combiner operations must be immediately nested in the region op
209 /// performing the reduction.
210 /// 4. Reduction def-use chain must end in a terminator op that yields the
211 /// next iteration/output values in the same order as the iteration-carried
212 /// values in `iterCarriedArgs`.
213 /// 5. `iterCarriedArgs` must contain all the iteration-carried/output values
214 /// of the region op performing the reduction.
215 ///
216 /// This utility is generic enough to detect reductions involving multiple
217 /// combiner operations (disabled for now) across multiple dialects, including
218 /// Linalg, Affine and SCF. For the sake of genericity, it does not return
219 /// specific enum values for the combiner operations since its goal is also
220 /// matching reductions without pre-defined semantics in core MLIR. It's up to
221 /// each client to make sense out of the list of combiner operations. It's also
222 /// up to each client to check for additional invariants on the expected
223 /// reductions not covered by this generic matching.
225  unsigned redPos,
226  SmallVectorImpl<Operation *> &combinerOps) {
227  assert(redPos < iterCarriedArgs.size() && "'redPos' is out of bounds");
228 
229  BlockArgument redCarriedVal = iterCarriedArgs[redPos];
230  if (!redCarriedVal.hasOneUse())
231  return nullptr;
232 
233  // For now, the first combiner op must be a binary op.
234  Operation *combinerOp = *redCarriedVal.getUsers().begin();
235  if (combinerOp->getNumOperands() != 2)
236  return nullptr;
237  Value reducedVal = combinerOp->getOperand(0) == redCarriedVal
238  ? combinerOp->getOperand(1)
239  : combinerOp->getOperand(0);
240 
241  Operation *redRegionOp =
242  iterCarriedArgs.front().getOwner()->getParent()->getParentOp();
243  if (dependsOnCarriedVals(reducedVal, iterCarriedArgs, redRegionOp))
244  return nullptr;
245 
246  // Traverse the def-use chain starting from the first combiner op until a
247  // terminator is found. Gather all the combiner ops along the way in
248  // topological order.
249  while (!combinerOp->mightHaveTrait<OpTrait::IsTerminator>()) {
250  if (!isMemoryEffectFree(combinerOp) || combinerOp->getNumResults() != 1 ||
251  !combinerOp->hasOneUse() || combinerOp->getParentOp() != redRegionOp)
252  return nullptr;
253 
254  combinerOps.push_back(combinerOp);
255  combinerOp = *combinerOp->getUsers().begin();
256  }
257 
258  // Limit matching to single combiner op until we can properly test reductions
259  // involving multiple combiners.
260  if (combinerOps.size() != 1)
261  return nullptr;
262 
263  // Check that the yielded value is in the same position as in
264  // `iterCarriedArgs`.
265  Operation *terminatorOp = combinerOp;
266  if (terminatorOp->getOperand(redPos) != combinerOps.back()->getResults()[0])
267  return nullptr;
268 
269  return reducedVal;
270 }
static llvm::ManagedStatic< PassManagerOptions > options
static void getForwardSliceImpl(Operation *op, SetVector< Operation * > *forwardSlice, const SliceOptions::TransitiveFilter &filter=nullptr)
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, const BackwardSliceOptions &options)
This class represents an argument of a Block.
Definition: Value.h:319
Block represents an ordered list of Operations.
Definition: Block.h:31
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:764
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
Value getOperand(unsigned idx)
Definition: Operation.h:345
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:745
bool mightHaveTrait()
Returns true if the operation might have the provided trait.
Definition: Operation.h:753
bool hasOneUse()
Returns true if this operation has exactly one use.
Definition: Operation.h:845
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition: Operation.h:669
unsigned getNumOperands()
Definition: Operation.h:341
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:234
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
Definition: Operation.h:682
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:672
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:373
bool isAncestor(Operation *other)
Return true if this operation is an ancestor of the other operation.
Definition: Operation.h:263
user_range getUsers()
Returns a range of all users.
Definition: Operation.h:869
result_range getResults()
Definition: Operation.h:410
unsigned getNumResults()
Return the number of results held by this operation.
Definition: Operation.h:399
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:96
user_range getUsers() const
Definition: Value.h:228
bool hasOneUse() const
Returns true if this value has exactly one use.
Definition: Value.h:215
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:285
Include the generated interface declarations.
void getBackwardSlice(Operation *op, SetVector< Operation * > *backwardSlice, const BackwardSliceOptions &options={})
Fills backwardSlice with the computed backward slice (i.e.
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
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.
SetVector< Operation * > topologicalSort(const SetVector< Operation * > &toSort)
Sorts all operations in toSort topologically while also considering region semantics.
void getForwardSlice(Operation *op, SetVector< Operation * > *forwardSlice, const ForwardSliceOptions &options={})
Fills forwardSlice with the computed forward slice (i.e.
std::function< bool(Operation *)> TransitiveFilter
Type of the condition to limit the propagation of transitive use-defs.
Definition: SliceAnalysis.h:29
TransitiveFilter filter
Definition: SliceAnalysis.h:30