MLIR  16.0.0git
OneShotAnalysis.cpp
Go to the documentation of this file.
1 //===- OneShotAnalysis.cpp - One-Shot (Single Pass) Analysis --------------===//
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 // One-Shot Analysis analyzes function bodies. Function boundaries (FuncOp
10 // bbArgs, CallOps, ReturnOps) are treated as "unknown" ops.
11 // ModuleBufferization.cpp is an extension of One-Shot Analysis for simple
12 // call graphs.
13 //
14 // One-Shot Bufferize consists of two phases.
15 //
16 // 1. Analyze ops to decide which OpResults can bufferize inplace, i.e., without
17 // inserting buffer copies. The analysis queries op bufferization semantics
18 // via `BufferizableOpInterface`.
19 // 2. Bufferize ops by calling `BufferizableOpInterface::bufferize`. This
20 // function does not generate buffer copies for OpResults that were decided
21 // to bufferize inplace during the analysis phase.
22 //
23 // This file contains only the analysis. The actual bufferization is implemented
24 // via `bufferizeOp` (Bufferize.h). For convenience, this file also contains a
25 // helper function `runOneShotBufferize` that analyzes an op (and its nested
26 // ops) and then bufferizes it.
27 //
28 // Inplace bufferization decisions are passed from the analysis to the
29 // bufferization phase via `AnalysisState` and `BufferizationAliasInfo`.
30 // They can be printed for debugging purposes with `testAnalysisOnly`.
31 //
32 // Ops that do not implement `BufferizableOpInterface` can be analyzed but are
33 // treated conservatively. E.g., the analysis has to assume that their tensor
34 // OpOperands bufferize to memory writes. While such ops can be analyzed, they
35 // are not bufferized and remain in the IR. to_tensor and to_memref ops are
36 // inserted at the bufferization boundary.
37 //
38 // This analysis caters to high-performance codegen where buffer reuse is deemed
39 // critical: the analysis should fail if the bufferized form of the function
40 // needs to return a buffer, unless `allowReturnAllocs` is enabled.
41 
43 
44 #include <random>
45 
52 #include "mlir/IR/AsmState.h"
53 #include "mlir/IR/Dominance.h"
54 #include "mlir/IR/Operation.h"
55 #include "mlir/IR/TypeUtilities.h"
57 #include "llvm/ADT/DenseSet.h"
58 #include "llvm/ADT/SetVector.h"
59 
60 using namespace mlir;
61 using namespace mlir::bufferization;
62 
63 static bool isaTensor(Type t) { return t.isa<TensorType>(); }
64 
65 //===----------------------------------------------------------------------===//
66 // Bufferization-specific attribute manipulation.
67 // These are for testing and debugging only. Bufferization information is
68 // stored in BufferizationAliasInfo. When run with `testAnalysisOnly`, the IR
69 // is annotated with the results of the analysis (copied from
70 // BufferizationAliasInfo), so that they can be checked in tests.
71 //===----------------------------------------------------------------------===//
72 
73 /// Attribute marker to specify op results that can be bufferized inPlace.
74 constexpr StringLiteral kInPlaceResultsAttrName = "__inplace_operands_attr__";
75 
76 /// Mark whether OpOperand will be bufferized inplace.
77 static void setInPlaceOpOperand(OpOperand &opOperand, bool inPlace) {
78  Operation *op = opOperand.getOwner();
79  auto attr =
81  SmallVector<StringRef> inPlaceVector;
82  if (attr) {
83  inPlaceVector = SmallVector<StringRef>(
84  llvm::to_vector<4>(attr.getAsValueRange<StringAttr>()));
85  } else {
86  inPlaceVector = SmallVector<StringRef>(op->getNumOperands(), "none");
87  for (OpOperand &opOperand : op->getOpOperands())
88  if (opOperand.get().getType().isa<TensorType>())
89  inPlaceVector[opOperand.getOperandNumber()] = "false";
90  }
91 
92  inPlaceVector[opOperand.getOperandNumber()] = inPlace ? "true" : "false";
94  OpBuilder(op).getStrArrayAttr(inPlaceVector));
95 }
96 
97 //===----------------------------------------------------------------------===//
98 // BufferizationAliasInfo
99 //===----------------------------------------------------------------------===//
100 
102  rootOp->walk([&](Operation *op) {
103  for (Value v : op->getResults())
104  if (v.getType().isa<TensorType>())
106  for (Region &r : op->getRegions())
107  for (Block &b : r.getBlocks())
108  for (auto bbArg : b.getArguments())
109  if (bbArg.getType().isa<TensorType>())
110  createAliasInfoEntry(bbArg);
111  });
112 }
113 
114 /// Add a new entry for `v` in the `aliasInfo` and `equivalentInfo`. In the
115 /// beginning the alias and equivalence sets only contain `v` itself.
117  aliasInfo.insert(v);
118  equivalentInfo.insert(v);
119 }
120 
121 /// Insert an info entry for `newValue` and merge its alias set with that of
122 /// `alias`.
124  createAliasInfoEntry(newValue);
125  aliasInfo.unionSets(newValue, alias);
126 }
127 
128 /// Insert an info entry for `newValue` and merge its alias set with that of
129 /// `alias`. Additionally, merge their equivalence classes.
131  Value alias) {
132  insertNewBufferAlias(newValue, alias);
133  equivalentInfo.unionSets(newValue, alias);
134 }
135 
136 /// Return `true` if a value was marked as in-place bufferized.
138  return inplaceBufferized.contains(&operand);
139 }
140 
141 /// Set the inPlace bufferization spec to true.
143  AnalysisState &state) {
144  markInPlace(operand);
145  for (OpResult result : state.getAliasingOpResult(operand))
146  aliasInfo.unionSets(result, operand.get());
147 }
148 
149 /// Set the inPlace bufferization spec to false.
151  assert(!inplaceBufferized.contains(&operand) &&
152  "OpOperand was already decided to bufferize inplace");
153 }
154 
155 /// Apply `fun` to all the members of the equivalence class of `v`.
157  Value v, function_ref<void(Value)> fun) const {
158  auto leaderIt = equivalentInfo.findLeader(v);
159  for (auto mit = leaderIt, meit = equivalentInfo.member_end(); mit != meit;
160  ++mit) {
161  fun(*mit);
162  }
163 }
164 
165 /// Apply `fun` to all aliases of `v`.
167  Value v, function_ref<void(Value)> fun) const {
168  auto leaderIt = aliasInfo.findLeader(v);
169  for (auto mit = leaderIt, meit = aliasInfo.member_end(); mit != meit; ++mit) {
170  fun(*mit);
171  }
172 }
173 
175 BufferizationAliasInfo::getAliases(Value v) const {
176  DenseSet<Value> res;
177  auto it = aliasInfo.findValue(aliasInfo.getLeaderValue(v));
178  for (auto mit = aliasInfo.member_begin(it), meit = aliasInfo.member_end();
179  mit != meit; ++mit) {
180  res.insert(static_cast<Value>(*mit));
181  }
183  aliasInfo.member_begin(it), aliasInfo.member_end());
184 }
185 
186 //===----------------------------------------------------------------------===//
187 // OneShotAnalysisState
188 //===----------------------------------------------------------------------===//
189 
192  : AnalysisState(options), aliasInfo(op) {
193  // Set up alias sets for OpResults that must bufferize in-place. This should
194  // be done before making any other bufferization decisions.
195  op->walk([&](BufferizableOpInterface bufferizableOp) {
196  if (!options.isOpAllowed(bufferizableOp))
197  return WalkResult::skip();
198  for (OpOperand &opOperand : bufferizableOp->getOpOperands()) {
199  if (opOperand.get().getType().isa<TensorType>())
200  if (bufferizableOp.mustBufferizeInPlace(opOperand, *this)) {
201  for (OpResult opResult :
202  bufferizableOp.getAliasingOpResult(opOperand, *this))
203  aliasInfo.unionAliasSets(opOperand.get(), opResult);
204  aliasInfo.markInPlace(opOperand);
205  }
206  }
207  return WalkResult::advance();
208  });
209 }
210 
212  return aliasInfo.isInPlace(opOperand);
213 }
214 
216  Value v2) const {
217  return aliasInfo.areEquivalentBufferizedValues(v1, v2);
218 }
219 
221  Value v2) const {
222  return aliasInfo.areAliasingBufferizedValues(v1, v2);
223 }
224 
225 // Gather yielded tensors in `yieldedTensors` by querying all aliases. This is
226 // to ensure that such information is available during bufferization time.
227 // Alias information can no longer be queried through BufferizationAliasInfo
228 // once we have started modifying the IR.
230  op->walk([&](Operation *returnOp) {
231  if (!isRegionReturnLike(returnOp) || !getOptions().isOpAllowed(returnOp))
232  return WalkResult::advance();
233 
234  for (OpOperand &returnValOperand : returnOp->getOpOperands()) {
235  Value returnVal = returnValOperand.get();
236  // Skip non-tensor values.
237  if (!returnVal.getType().isa<TensorType>())
238  continue;
239 
240  // Add all aliases of the returned value. But only the ones that are in
241  // the same block.
242  aliasInfo.applyOnAliases(returnVal, [&](Value v) {
243  if (auto bbArg = v.dyn_cast<BlockArgument>()) {
244  if (bbArg.getOwner()->getParentOp() == returnOp->getParentOp())
245  yieldedTensors.insert(bbArg);
246  return;
247  }
248  Operation *definingOp = v.getDefiningOp();
249  if (definingOp->getParentOp() == returnOp->getParentOp())
250  yieldedTensors.insert(v);
251  });
252  }
253 
254  return WalkResult::advance();
255  });
256 }
257 
259  op->walk([&](Operation *op) {
260  // Skip unknown ops.
261  auto bufferizableOp = getOptions().dynCastBufferizableOp(op);
262  if (!bufferizableOp)
263  return WalkResult::skip();
264 
265  // Check all tensor OpResults.
266  for (OpResult opResult : op->getOpResults()) {
267  if (!opResult.getType().isa<TensorType>())
268  continue;
269 
270  // If there is no preceding memory write, the tensor contents are
271  // undefined.
272  // Note: If `findLastPrecedingWrite` reaches the end of the reverse SSA
273  // use-def chain, it returns that value, regardless of whether it is a
274  // memory write or not.
275  SetVector<Value> lastWrites = findLastPrecedingWrite(opResult);
276  bool isUndefined = llvm::none_of(lastWrites, [&](Value lastWrite) {
277  if (auto bufferizableOp = getOptions().dynCastBufferizableOp(lastWrite))
278  return bufferizableOp.isMemoryWrite(lastWrite.cast<OpResult>(),
279  *this);
280  return true;
281  });
282  if (isUndefined)
283  for (OpOperand &use : opResult.getUses())
284  undefinedTensorUses.insert(&use);
285  }
286 
287  return WalkResult::advance();
288  });
289 }
290 
292  return undefinedTensorUses.contains(opOperand);
293 }
294 
296  return yieldedTensors.contains(tensor);
297 }
298 
300  bool isWritten = false;
301  aliasInfo.applyOnAliases(value, [&](Value val) {
302  for (OpOperand &use : val.getUses())
303  if (isInPlace(use) && bufferizesToMemoryWrite(use))
304  isWritten = true;
305  });
306  return isWritten;
307 }
308 
310  // TODO: Out-of-place bufferized value could be considered writable.
311  if (auto bufferizableOp = getOptions().dynCastBufferizableOp(value))
312  return bufferizableOp.isWritable(value, *this);
313 
314  // Query BufferizableOpInterface to see if the BlockArgument is writable.
315  if (auto bbArg = value.dyn_cast<BlockArgument>())
316  if (auto bufferizableOp =
317  getOptions().dynCastBufferizableOp(bbArg.getOwner()->getParentOp()))
318  return bufferizableOp.isWritable(bbArg, *this);
319 
320  // Not a bufferizable op: The conservative answer is "not writable".
321  return false;
322 }
323 
324 //===----------------------------------------------------------------------===//
325 // Bufferization-specific alias analysis.
326 //===----------------------------------------------------------------------===//
327 
328 /// Return true if opOperand has been decided to bufferize in-place.
329 static bool isInplaceMemoryWrite(OpOperand &opOperand,
330  const BufferizationAliasInfo &aliasInfo,
331  const AnalysisState &state) {
332  // OpOperands that do not bufferize to a memory write do not write in-place.
333  if (!state.bufferizesToMemoryWrite(opOperand))
334  return false;
335  // Check current bufferization decisions.
336  return aliasInfo.isInPlace(opOperand);
337 }
338 
339 /// Return true if `a` happens before `b`, i.e., `a` or one of its ancestors
340 /// properly dominates `b` and `b` is not inside `a`.
341 static bool happensBefore(Operation *a, Operation *b,
342  const DominanceInfo &domInfo) {
343  do {
344  // TODO: Instead of isProperAncestor + properlyDominates, we should use
345  // properlyDominatesImpl(a, b, /*enclosingOpOk=*/false)
346  if (a->isProperAncestor(b))
347  return false;
348  if (domInfo.properlyDominates(a, b))
349  return true;
350  } while ((a = a->getParentOp()));
351  return false;
352 }
353 
354 static Region *
356  const BufferizationOptions &options) {
357  while (Region *region = op->getParentRegion()) {
358  op = region->getParentOp();
359  if (auto bufferizableOp = options.dynCastBufferizableOp(op))
360  if (bufferizableOp.isRepetitiveRegion(region->getRegionNumber()))
361  return region;
362  }
363  return nullptr;
364 }
365 
366 static Region *
368  Region *region = value.getParentRegion();
369  while (region) {
370  Operation *op = region->getParentOp();
371  if (auto bufferizableOp = options.dynCastBufferizableOp(op))
372  if (bufferizableOp.isRepetitiveRegion(region->getRegionNumber()))
373  return region;
374  region = op->getParentRegion();
375  }
376  return nullptr;
377 }
378 
379 /// For each given value, find the closest enclosing repetitive region. If this
380 /// is the same region for each value, return it. Otherwise return None.
381 /// Note: If there is no enclosing repetitive region, return nullptr.
382 static Optional<Region *>
384  const BufferizationOptions &options) {
385  if (values.empty())
386  return None;
387  Region *r = getEnclosingRepetitiveRegion(values.front(), options);
388  for (Value value : values.drop_front())
390  return None;
391  return r;
392 }
393 
394 /// Return `true` if the given tensor value is a memory write. Most values are
395 /// tensor writes, but ops that define a tensor SSA value without specifying its
396 /// contents (e.g., alloc_tensor) are not.
397 static bool isMemoryWrite(Value value, const AnalysisState &state) {
398  auto opResult = value.dyn_cast<OpResult>();
399  if (!opResult)
400  return true;
401  auto bufferizableOp = state.getOptions().dynCastBufferizableOp(value);
402  if (!bufferizableOp)
403  return true;
404  return bufferizableOp.isMemoryWrite(opResult, state);
405 }
406 
407 /// Annotate IR with details about the detected RaW conflict.
408 static void annotateConflict(OpOperand *uRead, OpOperand *uConflictingWrite,
409  Value lastWrite) {
410  static uint64_t counter = 0;
411  Operation *readingOp = uRead->getOwner();
412  Operation *conflictingWritingOp = uConflictingWrite->getOwner();
413 
414  OpBuilder b(conflictingWritingOp->getContext());
415  std::string id = "C_" + std::to_string(counter++);
416 
417  std::string conflictingWriteAttr =
418  id +
419  "[CONFL-WRITE: " + std::to_string(uConflictingWrite->getOperandNumber()) +
420  "]";
421  conflictingWritingOp->setAttr(conflictingWriteAttr, b.getUnitAttr());
422 
423  std::string readAttr =
424  id + "[READ: " + std::to_string(uRead->getOperandNumber()) + "]";
425  readingOp->setAttr(readAttr, b.getUnitAttr());
426 
427  if (auto opResult = lastWrite.dyn_cast<OpResult>()) {
428  std::string lastWriteAttr = id + "[LAST-WRITE: result " +
429  std::to_string(opResult.getResultNumber()) +
430  "]";
431  opResult.getDefiningOp()->setAttr(lastWriteAttr, b.getUnitAttr());
432  } else {
433  auto bbArg = lastWrite.cast<BlockArgument>();
434  std::string lastWriteAttr =
435  id + "[LAST-WRITE: bbArg " + std::to_string(bbArg.getArgNumber()) + "]";
436  bbArg.getOwner()->getParentOp()->setAttr(lastWriteAttr, b.getUnitAttr());
437  }
438 }
439 
440 /// Given sets of uses and writes, return true if there is a RaW conflict under
441 /// the assumption that all given reads/writes alias the same buffer and that
442 /// all given writes bufferize inplace.
443 ///
444 /// A conflict is: According to SSA use-def chains, a read R is supposed to read
445 /// the result of a write W1. But because of bufferization decisions, R actually
446 /// reads another write W2.
448  const DenseSet<OpOperand *> &usesRead,
449  const DenseSet<OpOperand *> &usesWrite, const DominanceInfo &domInfo,
450  AnalysisState &state, const BufferizationAliasInfo &aliasInfo) {
451  const BufferizationOptions &options = state.getOptions();
452 
453  // Gather all written aliases. Skip over aliases that are not actual writes.
454  SmallVector<Value> writtenAliases;
455  for (OpOperand *uWrite : usesWrite)
456  if (isMemoryWrite(uWrite->get(), state))
457  writtenAliases.push_back(uWrite->get());
458  // Find the inner-most enclosing repetitive region of each alias. If this is
459  // the same region for every alias, save it in `repetitiveRegionOfWrites`.
460  Optional<Region *> repetitiveRegionOfWrites =
461  getCommonEnclosingRepetitiveRegion(writtenAliases, options);
462 
463  for (OpOperand *uRead : usesRead) {
464  Operation *readingOp = uRead->getOwner();
465 
466  // Find most recent writes of uRead by following the SSA use-def chain.
467  // E.g.:
468  //
469  // %0 = "writing_op"(%t) : tensor<?x32> -> tensor<?xf32>
470  // %1 = "aliasing_op"(%0) : tensor<?x32> -> tensor<?xf32>
471  // %2 = "reading_op"(%1) : : tensor<?x32> -> not_a_tensor_type
472  //
473  // In the above example, if uRead is the OpOperand of reading_op, lastWrite
474  // is %0. Note that operations that create an alias but do not write (such
475  // as ExtractSliceOp) are skipped.
476  SetVector<Value> lastWrites = state.findLastPrecedingWrite(uRead->get());
477 
478  // Look for conflicting memory writes. Potential conflicts are writes to an
479  // alias that have been decided to bufferize inplace.
480  for (OpOperand *uConflictingWrite : usesWrite) {
481  // Throughout this loop, check for multiple requirements that have to be
482  // met for uConflictingWrite to be an actual conflict.
483  Operation *conflictingWritingOp = uConflictingWrite->getOwner();
484 
485  // Check if conflictingWritingOp is in the same repetitive region as all
486  // written aliases. If this is not the case, there is no meaningful
487  // `happensBefore` relationship because conflictingWritingOp may be
488  // executed multiple times. E.g.:
489  //
490  // %0 = ... : tensor<?xf32>
491  // scf.for ... {
492  // "reading_op"(%0) : tensor<?xf32>
493  // %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32>
494  // ...
495  // }
496  //
497  // In the above example, reading_op happens before writing_op according to
498  // op dominance. However, both ops may happen multiple times; in
499  // particular, the second execution of reading_op happens after the first
500  // execution of writing_op. This is problematic if the tensor they operate
501  // on (%0) is defined outside of the loop.
502  //
503  // Counter example:
504  //
505  // scf.for ... {
506  // %0 = ... : tensor<?xf32>
507  // "reading_op"(%0) : tensor<?xf32>
508  // %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32>
509  // ...
510  // }
511  //
512  // In this example, %0 is in the same repetitive region as
513  // conflictingWritingOp, so op dominance can be used to compute the
514  // `happensBefore` relationship.
515  //
516  // Note: iter_args of loops are not aliases of their respective block
517  // arguments, so op domanice can be used when analyzing ops that operate
518  // on them.
519  //
520  // Note: If `writtenAliases` is empty, there are no memory writes outside
521  // of the repetitive region of conflictingWritingOp, which means that all
522  // relevant aliases are inside the same repetitive region.
523  bool canUseOpDominance =
524  writtenAliases.empty() ||
525  repetitiveRegionOfWrites ==
526  getEnclosingRepetitiveRegion(conflictingWritingOp, options);
527 
528  // No conflict if the readingOp dominates conflictingWritingOp, i.e., the
529  // write is not visible when reading.
530  //
531  // Note: If ops are executed multiple times (e.g., because they are inside
532  // a loop), there may be no meaningful `happensBefore` relationship.
533  if (canUseOpDominance &&
534  happensBefore(readingOp, conflictingWritingOp, domInfo))
535  continue;
536 
537  // No conflict if the reading use equals the use of the conflicting write.
538  // A use cannot conflict with itself.
539  //
540  // Note: Just being the same op is not enough. It has to be the same use.
541  // Note: If the op is executed multiple times (e.g., because it is inside
542  // a loop), it may be conflicting with itself.
543  if (canUseOpDominance && uConflictingWrite == uRead)
544  continue;
545 
546  // No conflict if the op interface says so.
547  if (auto bufferizableOp = options.dynCastBufferizableOp(readingOp))
548  if (bufferizableOp.isNotConflicting(uRead, uConflictingWrite, state))
549  continue;
550 
551  if (conflictingWritingOp != readingOp)
552  if (auto bufferizableOp =
553  options.dynCastBufferizableOp(conflictingWritingOp))
554  if (bufferizableOp.isNotConflicting(uRead, uConflictingWrite, state))
555  continue;
556 
557  // Ops are not conflicting if they are in mutually exclusive regions.
558  //
559  // Note: If ops are executed multiple times (e.g., because they are inside
560  // a loop), mutually exclusive regions may be executed multiple
561  // times.
562  if (canUseOpDominance &&
563  insideMutuallyExclusiveRegions(readingOp, conflictingWritingOp))
564  continue;
565 
566  // Check all possible last writes.
567  for (Value lastWrite : lastWrites) {
568  // No conflict if the conflicting write happens before the last
569  // write.
570  if (Operation *writingOp = lastWrite.getDefiningOp()) {
571  if (happensBefore(conflictingWritingOp, writingOp, domInfo))
572  // conflictingWritingOp happens before writingOp. No conflict.
573  continue;
574  // No conflict if conflictingWritingOp is contained in writingOp.
575  if (writingOp->isProperAncestor(conflictingWritingOp))
576  continue;
577  } else {
578  auto bbArg = lastWrite.cast<BlockArgument>();
579  Block *block = bbArg.getOwner();
580  if (!block->findAncestorOpInBlock(*conflictingWritingOp))
581  // conflictingWritingOp happens outside of the block. No
582  // conflict.
583  continue;
584  }
585 
586  // No conflict if the conflicting write and the last write are the same
587  // use.
588  SmallVector<OpResult> aliasingOpResult =
589  state.getAliasingOpResult(*uConflictingWrite);
590  if (aliasingOpResult.size() == 1 && aliasingOpResult[0] == lastWrite)
591  continue;
592 
593  // All requirements are met. Conflict found!
594 
595  if (options.printConflicts)
596  annotateConflict(uRead, uConflictingWrite, lastWrite);
597 
598  return true;
599  }
600  }
601  }
602 
603  return false;
604 }
605 
606 // Helper function to iterate on aliases of `root` and capture the writes.
608  const BufferizationAliasInfo &aliasInfo,
609  const AnalysisState &state) {
610  aliasInfo.applyOnAliases(root, [&](Value alias) {
611  for (auto &use : alias.getUses())
612  // Inplace write to a value that aliases root.
613  if (isInplaceMemoryWrite(use, aliasInfo, state))
614  res.insert(&use);
615  });
616 }
617 
618 // Helper function to iterate on aliases of `root` and capture the reads.
620  const BufferizationAliasInfo &aliasInfo,
621  const AnalysisState &state) {
622  aliasInfo.applyOnAliases(root, [&](Value alias) {
623  for (auto &use : alias.getUses())
624  // Read to a value that aliases root.
625  if (state.bufferizesToMemoryRead(use))
626  res.insert(&use);
627  });
628 }
629 
630 /// Return true if bufferizing `operand` inplace would create a conflict. A read
631 /// R and a write W of the same alias set is a conflict if inplace bufferization
632 /// of W changes the value read by R to a value different from the one that
633 /// would be expected by tracing back R's origin through SSA use-def chains.
634 /// A conflict can only be introduced by a new alias and/or an inplace
635 /// bufferization decision.
636 ///
637 /// Example:
638 /// %0 = tensor.extract_slice %t[...][...][1, 1] {inplace?}
639 /// %1 = vector.transfer_write %v1, %t {inplace} : vector<5xf32>, tensor<?xf32>
640 /// %e = tensor.extract_slice %1
641 /// %2 = vector.transfer_write %v2, %0 {inplace} : vector<6xf32>, tensor<?xf32>
642 /// %3 = vector.transfer_read %e, %cst : tensor<?xf32>, vector<7xf32>
643 ///
644 /// In the above example, the two TransferWriteOps have already been decided to
645 /// bufferize inplace. Bufferizing the ExtractSliceOp inplace would create a
646 /// conflict because:
647 /// * According to SSA use-def chains, we expect to read the result of %1.
648 /// * However, adding an alias {%0, %t} would mean that the second
649 /// TransferWriteOp overwrites the first one. Therefore, the TransferReadOp
650 /// would no longer be reading the result of %1.
651 ///
652 /// If `checkConsistencyOnly` is true, this function checks if there is a
653 /// read-after-write conflict without bufferizing `operand` inplace. This would
654 /// indicate a problem with the current inplace bufferization decisions.
655 ///
656 /// Note: If `checkConsistencyOnly`, this function may be called with a null
657 /// OpResult. In that case, only the consistency of bufferization decisions
658 /// involving aliases of the given OpOperand are checked.
660  OpOperand &operand, const DominanceInfo &domInfo, AnalysisState &state,
661  const BufferizationAliasInfo &aliasInfo,
662  bool checkConsistencyOnly = false) {
663  // Collect reads and writes of all aliases of OpOperand and OpResult.
664  DenseSet<OpOperand *> usesRead, usesWrite;
665  getAliasingReads(usesRead, operand.get(), aliasInfo, state);
666  getAliasingInplaceWrites(usesWrite, operand.get(), aliasInfo, state);
667  for (OpResult result : state.getAliasingOpResult(operand)) {
668  getAliasingReads(usesRead, result, aliasInfo, state);
669  getAliasingInplaceWrites(usesWrite, result, aliasInfo, state);
670  }
671  if (!checkConsistencyOnly && state.bufferizesToMemoryWrite(operand))
672  usesWrite.insert(&operand);
673 
674  return hasReadAfterWriteInterference(usesRead, usesWrite, domInfo, state,
675  aliasInfo);
676 }
677 
678 /// Check the reverse SSA use-def chain (following aliasing OpOperands) for
679 /// non-writable tensor values. Stop searching when an out-of-place bufferized
680 /// OpOperand was found (or when the OpOperand was not bufferized yet).
681 /// `currentOpOperand` is assumed to be in-place, even if that decision was not
682 /// materialized in `aliasInfo` yet.
683 static bool
685  const BufferizationAliasInfo &aliasInfo,
686  const OneShotAnalysisState &state) {
687  SmallVector<Value> worklist;
688  worklist.push_back(value);
689  while (!worklist.empty()) {
690  Value nextVal = worklist.pop_back_val();
691  if (!state.isWritable(nextVal))
692  return true;
693 
694  // If `nextVal` is not a BlockArgument: End of use-def chain reached.
695  auto opResult = nextVal.dyn_cast<OpResult>();
696  if (!opResult)
697  continue;
698 
699  // Follow reverse SSA use-def chain.
700  SmallVector<OpOperand *> aliasingOpOperands =
701  state.getAliasingOpOperand(opResult);
702  for (OpOperand *opOperand : aliasingOpOperands)
703  if (aliasInfo.isInPlace(*opOperand) || currentOpOperand == opOperand)
704  worklist.push_back(opOperand->get());
705  }
706  return false;
707 }
708 
709 /// Return true if bufferizing `operand` inplace would create a write to a
710 /// non-writable buffer.
712  OpOperand &operand, const BufferizationAliasInfo &aliasInfo,
713  OneShotAnalysisState &state, bool checkConsistencyOnly = false) {
714  // Collect writes of all aliases of OpOperand and OpResult.
715  DenseSet<OpOperand *> usesWrite;
716  getAliasingInplaceWrites(usesWrite, operand.get(), aliasInfo, state);
717  for (OpResult result : state.getAliasingOpResult(operand)) {
718  getAliasingInplaceWrites(usesWrite, result, aliasInfo, state);
719  }
720  if (!checkConsistencyOnly && state.bufferizesToMemoryWrite(operand))
721  usesWrite.insert(&operand);
722 
723  // Assuming that `operand` bufferizes in-place: For each write (to each
724  // alias), check if there is a non-writable tensor in the reverse SSA use-def
725  // chain.
726  for (OpOperand *uWrite : usesWrite)
727  if (hasPrecedingAliasingNonWritableTensor(uWrite->get(), &operand,
728  aliasInfo, state))
729  return true;
730 
731  return false;
732 }
733 
734 //===----------------------------------------------------------------------===//
735 // Bufferization analyses.
736 //===----------------------------------------------------------------------===//
737 
738 /// Determine if `operand` can be bufferized in-place.
740  OpOperand &operand, BufferizationAliasInfo &aliasInfo,
741  OneShotAnalysisState &state, const DominanceInfo &domInfo) {
742  bool foundInterference =
743  wouldCreateWriteToNonWritableBuffer(operand, aliasInfo, state) ||
744  wouldCreateReadAfterWriteInterference(operand, domInfo, state, aliasInfo);
745 
746  if (foundInterference)
747  aliasInfo.bufferizeOutOfPlace(operand);
748  else
749  aliasInfo.bufferizeInPlace(operand, state);
750 
751  return success();
752 }
753 
754 /// Analyze the `ops` to determine which OpOperands are inplaceable. Walk ops in
755 /// reverse and bufferize ops greedily. This is a good starter heuristic.
756 ///
757 /// Even if an op does not read or write, it may still create an alias when
758 /// bufferized in-place. An example of such ops is tensor.extract_slice.
759 ///
760 /// Rationale for bufferizing `%1 = tensor.extract_slice %0[...]` inplace:
761 ///
762 /// When bufferized out of place, an ExtractSliceOp lowers to alloc + copy. This
763 /// cannot change the flow of information for either the source or the
764 /// result buffers.
765 ///
766 /// When bufferized inplace, an ExtractSliceOp does not by itself create any
767 /// read or write from memory. Instead, it has the effect of merging the alias
768 /// sets of the source and the result buffers.
769 ///
770 /// An analysis is required to ensure inplace bufferization would not result in
771 /// RaW dependence violations.
773  BufferizationAliasInfo &aliasInfo,
774  OneShotAnalysisState &state,
775  const DominanceInfo &domInfo,
776  unsigned analysisFuzzerSeed = 0) {
777  if (analysisFuzzerSeed) {
778  // This is a fuzzer. For testing purposes only. Randomize the order in which
779  // operations are analyzed. The bufferization quality is likely worse, but
780  // we want to make sure that no assertions are triggered anywhere.
781  std::mt19937 g(analysisFuzzerSeed);
782  llvm::shuffle(ops.begin(), ops.end(), g);
783  }
784 
785  // Walk ops in reverse for better interference analysis.
786  for (Operation *op : reverse(ops))
787  for (OpOperand &opOperand : op->getOpOperands())
788  if (opOperand.get().getType().isa<TensorType>())
789  if (auto bufferizableOp = state.getOptions().dynCastBufferizableOp(op))
790  if (failed(bufferizableInPlaceAnalysisImpl(opOperand, aliasInfo,
791  state, domInfo)))
792  return failure();
793 
794  return success();
795 }
796 
797 /// Return true if the given op has a tensor result or a tensor operand.
798 static bool hasTensorSemantics(Operation *op) {
799  bool hasTensorResult = any_of(op->getResultTypes(), isaTensor);
800  bool hasTensorOperand = any_of(op->getOperandTypes(), isaTensor);
801  return hasTensorResult || hasTensorOperand;
802 }
803 
804 /// Analyze all ops that are contained in `op`.
806  BufferizationAliasInfo &aliasInfo,
807  OneShotAnalysisState &state,
808  const DominanceInfo &domInfo,
809  unsigned analysisFuzzerSeed = 0) {
810  // Collect ops so we can build our own reverse traversal.
812  op->walk([&](Operation *op) {
813  // No tensors => no buffers.
814  if (!hasTensorSemantics(op))
815  return;
816  ops.push_back(op);
817  });
818 
819  return inPlaceAnalysis(ops, aliasInfo, state, domInfo, analysisFuzzerSeed);
820 }
821 
822 /// Analyze equivalence of tied OpResult/OpOperand pairs of the given ops.
824  BufferizationAliasInfo &aliasInfo,
825  AnalysisState &state) {
826  for (Operation *op : ops)
827  if (auto bufferizableOp = state.getOptions().dynCastBufferizableOp(op))
828  for (OpResult opResult : op->getOpResults())
829  if (opResult.getType().isa<TensorType>())
830  for (OpOperand *opOperand :
831  bufferizableOp.getAliasingOpOperand(opResult, state))
832  if (state.isInPlace(*opOperand))
833  if (bufferizableOp.bufferRelation(opResult, state) ==
835  aliasInfo.unionEquivalenceClasses(opResult, opOperand->get());
836 }
837 
838 /// Analyze equivalence of tied OpResult/OpOperand pairs of all ops contained
839 /// in `op`.
841  BufferizationAliasInfo &aliasInfo,
842  AnalysisState &state) {
843  // Traverse ops in PostOrder: Nested ops first, then enclosing ops.
845  op->walk<WalkOrder::PostOrder>([&](Operation *op) {
846  // No tensors => no buffers.
847  if (none_of(op->getResultTypes(), isaTensor))
848  return;
849  ops.push_back(op);
850  });
851 
852  equivalenceAnalysis(ops, aliasInfo, state);
853 }
854 
855 /// Assert that the current bufferization decisions are consistent.
856 static LogicalResult
858  AnalysisState &state,
859  const BufferizationAliasInfo &aliasInfo) {
860  const BufferizationOptions &options = state.getOptions();
861 
862  WalkResult walkResult = op->walk([&](BufferizableOpInterface op) {
863  // Skip ops that are not in the filter.
864  if (!options.isOpAllowed(op.getOperation()))
865  return WalkResult::advance();
866 
867  // Input IR may not contain any ToMemrefOps. These are not supported because
868  // the analysis cannot follow the data flow through memrefs.
869  if (isa<ToMemrefOp>(op.getOperation())) {
870  op->emitError("to_memref ops not supported during One-Shot Analysis");
871  return WalkResult::interrupt();
872  }
873 
874  for (OpOperand &opOperand : op->getOpOperands()) {
875  if (opOperand.get().getType().isa<TensorType>()) {
877  opOperand, domInfo, state, aliasInfo,
878  /*checkConsistencyOnly=*/true)) {
879  // This error can happen if certain "mustBufferizeInPlace" interface
880  // methods are implemented incorrectly, such that the IR already has
881  // a RaW conflict before making any bufferization decisions.
882  op->emitError("input IR has RaW conflict");
883  return WalkResult::interrupt();
884  }
885  }
886  }
887 
888  return WalkResult::advance();
889  });
890 
891  return success(!walkResult.wasInterrupted());
892 }
893 
894 /// Annotate the IR with the result of the analysis. For testing/debugging only.
895 static void
897  const BufferizationAliasInfo &aliasInfo,
898  AnalysisState &state) {
899  op->walk([&](Operation *op) {
900  if (auto bufferizableOp = state.getOptions().dynCastBufferizableOp(op))
901  for (OpOperand &opOperand : op->getOpOperands())
902  if (opOperand.get().getType().isa<TensorType>())
903  setInPlaceOpOperand(opOperand, aliasInfo.isInPlace(opOperand));
904  });
905 }
906 
907 /// Assert that IR is in destination-passing style. I.e., every value that is
908 /// returned or yielded from a block is:
909 /// * aliasing a bbArg of that block or a parent block, or
910 /// * aliasing an OpResult of a op in a parent block.
911 ///
912 /// Example:
913 /// ```
914 /// %0 = "some_op" : tensor<?xf32>
915 /// %1 = scf.if %c -> (tensor<?xf32>) {
916 /// scf.yield %0 : tensor<?xf32>
917 /// } else {
918 /// %t = linalg.alloc_tensor : tensor<?xf32>
919 /// scf.yield %t : tensor<?xf32>
920 /// }
921 /// ```
922 /// In the above example, the first scf.yield op satifies destination-passing
923 /// style because the yielded value %0 is defined in the parent block. The
924 /// second scf.yield op does not satisfy destination-passing style because the
925 /// yielded value %t is defined in the same block as the scf.yield op.
926 // TODO: The current implementation checks for equivalent values instead of
927 // aliasing values, which is stricter than needed. We can currently not check
928 // for aliasing values because the analysis is a maybe-alias analysis and we
929 // need a must-alias analysis here.
930 static LogicalResult
932  BufferizationAliasInfo &aliasInfo,
933  SmallVector<Operation *> &newOps) {
934  LogicalResult status = success();
935  DominanceInfo domInfo(op);
936  op->walk([&](Operation *returnOp) {
937  if (!isRegionReturnLike(returnOp) ||
938  !state.getOptions().isOpAllowed(returnOp))
939  return WalkResult::advance();
940 
941  for (OpOperand &returnValOperand : returnOp->getOpOperands()) {
942  Value returnVal = returnValOperand.get();
943  // Skip non-tensor values.
944  if (!returnVal.getType().isa<TensorType>())
945  continue;
946 
947  bool foundEquivValue = false;
948  aliasInfo.applyOnEquivalenceClass(returnVal, [&](Value equivVal) {
949  if (auto bbArg = equivVal.dyn_cast<BlockArgument>()) {
950  Operation *definingOp = bbArg.getOwner()->getParentOp();
951  if (definingOp->isProperAncestor(returnOp))
952  foundEquivValue = true;
953  return;
954  }
955 
956  Operation *definingOp = equivVal.getDefiningOp();
957  if (definingOp->getBlock()->findAncestorOpInBlock(
958  *returnOp->getParentOp()))
959  // Skip ops that happen after `returnOp` and parent ops.
960  if (happensBefore(definingOp, returnOp, domInfo))
961  foundEquivValue = true;
962  });
963 
964  if (!foundEquivValue)
965  status =
966  returnOp->emitError()
967  << "operand #" << returnValOperand.getOperandNumber()
968  << " of ReturnLike op does not satisfy destination passing style";
969  }
970 
971  return WalkResult::advance();
972  });
973 
974  return status;
975 }
976 
978  OneShotAnalysisState &state) {
979  DominanceInfo domInfo(op);
980  BufferizationAliasInfo &aliasInfo = state.getAliasInfo();
981  const auto &options =
982  static_cast<const OneShotBufferizationOptions &>(state.getOptions());
983 
984  // Catch incorrect API usage.
985  assert((state.hasDialectState(func::FuncDialect::getDialectNamespace()) ||
986  !options.bufferizeFunctionBoundaries) &&
987  "must use ModuleBufferize to bufferize function boundaries");
988 
989  if (failed(checkAliasInfoConsistency(op, domInfo, state, aliasInfo)))
990  return failure();
991 
992  // If the analysis fails, just return.
993  if (failed(inPlaceAnalysis(op, aliasInfo, state, domInfo,
994  options.analysisFuzzerSeed)))
995  return failure();
996  equivalenceAnalysis(op, aliasInfo, state);
997 
998  bool failedAnalysis = false;
999  if (!options.allowReturnAllocs) {
1000  SmallVector<Operation *> newOps;
1001  failedAnalysis |=
1002  failed(assertDestinationPassingStyle(op, state, aliasInfo, newOps));
1003  }
1004 
1005  // Gather some extra analysis data.
1006  state.gatherYieldedTensors(op);
1007  state.gatherUndefinedTensorUses(op);
1008 
1009  // Analysis verification: After setting up alias/equivalence sets, each op
1010  // can check for expected invariants/limitations and fail the analysis if
1011  // necessary.
1012  op->walk([&](Operation *op) {
1013  if (BufferizableOpInterface bufferizableOp =
1014  options.dynCastBufferizableOp(op))
1015  failedAnalysis |= failed(bufferizableOp.verifyAnalysis(state));
1016  });
1017 
1018  // Annotate operations if we only want to report the analysis.
1019  if (options.testAnalysisOnly)
1020  annotateOpsWithBufferizationMarkers(op, aliasInfo, state);
1021 
1022  return success(!failedAnalysis);
1023 }
1024 
1027  const OneShotBufferizationOptions &options) {
1028  assert(!(options.copyBeforeWrite && options.testAnalysisOnly) &&
1029  "invalid combination of bufferization flags");
1030  if (!options.copyBeforeWrite) {
1031  // If a buffer is copied before every write, no analysis is needed.
1032  OneShotAnalysisState state(op, options);
1033  if (failed(insertTensorCopies(op, options)))
1034  return failure();
1035  }
1036  if (options.testAnalysisOnly)
1037  return success();
1038  return bufferizeOp(op, options, /*copyBeforeWrite=*/options.copyBeforeWrite);
1039 }
static Optional< Region * > getCommonEnclosingRepetitiveRegion(ArrayRef< Value > values, const BufferizationOptions &options)
For each given value, find the closest enclosing repetitive region.
bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const
Return true if operation A properly dominates operation B, i.e.
Definition: Dominance.h:130
Include the generated interface declarations.
This class contains a list of basic blocks and a link to the parent operation it is attached to...
Definition: Region.h:26
SmallVector< OpResult > getAliasingOpResult(OpOperand &opOperand) const
Determine which OpResult will alias with opOperand if the op is bufferized in place.
LogicalResult analyzeOp(Operation *op, OneShotAnalysisState &state)
Analyze op and its nested ops.
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one)...
Definition: Operation.h:574
SmallVector< OpOperand * > getAliasingOpOperand(OpResult result) const
Determine which OpOperand* will alias with result if the op is bufferized in place.
static bool wouldCreateWriteToNonWritableBuffer(OpOperand &operand, const BufferizationAliasInfo &aliasInfo, OneShotAnalysisState &state, bool checkConsistencyOnly=false)
Return true if bufferizing operand inplace would create a write to a non-writable buffer...
U dyn_cast_or_null() const
Definition: Attributes.h:131
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:480
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
OneShotAnalysisState(Operation *op, const OneShotBufferizationOptions &options)
static bool hasTensorSemantics(Operation *op)
Return true if the given op has a tensor result or a tensor operand.
This is a value defined by a result of an operation.
Definition: Value.h:446
Block represents an ordered list of Operations.
Definition: Block.h:29
bool wasInterrupted() const
Returns true if the walk was interrupted.
Definition: Visitors.h:55
const BufferizationOptions & getOptions() const
Return a reference to the BufferizationOptions.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value...
Definition: LogicalResult.h:72
bool areEquivalentBufferizedValues(Value v1, Value v2) const override
Return true if v1 and v2 bufferize to equivalent buffers.
unsigned getNumOperands()
Definition: Operation.h:263
bool testAnalysisOnly
If set to true, does not modify the IR apart from adding attributes (for checking the results of the ...
static void annotateOpsWithBufferizationMarkers(Operation *op, const BufferizationAliasInfo &aliasInfo, AnalysisState &state)
Annotate the IR with the result of the analysis. For testing/debugging only.
operand_type_range getOperandTypes()
Definition: Operation.h:314
LogicalResult insertTensorCopies(Operation *op, const OneShotBufferizationOptions &options)
bool areEquivalentBufferizedValues(Value v1, Value v2) const
Return true if v1 and v2 bufferize to equivalent buffers.
A class for computing basic dominance information.
Definition: Dominance.h:117
bool hasDialectState(StringRef name) const
Return true if the given dialect state exists.
bool isRegionReturnLike(Operation *operation)
Returns true if the given operation is either annotated with the ReturnLike trait or implements the R...
static LogicalResult inPlaceAnalysis(SmallVector< Operation *> &ops, BufferizationAliasInfo &aliasInfo, OneShotAnalysisState &state, const DominanceInfo &domInfo, unsigned analysisFuzzerSeed=0)
Analyze the ops to determine which OpOperands are inplaceable.
static void equivalenceAnalysis(SmallVector< Operation *> &ops, BufferizationAliasInfo &aliasInfo, AnalysisState &state)
Analyze equivalence of tied OpResult/OpOperand pairs of the given ops.
void unionEquivalenceClasses(Value v1, Value v2)
Union the equivalence classes of v1 and v2.
bool bufferizesToMemoryWrite(OpOperand &opOperand) const
Return true if opOperand bufferizes to a memory write.
static bool wouldCreateReadAfterWriteInterference(OpOperand &operand, const DominanceInfo &domInfo, AnalysisState &state, const BufferizationAliasInfo &aliasInfo, bool checkConsistencyOnly=false)
Return true if bufferizing operand inplace would create a conflict.
The BufferizationAliasInfo class maintains a list of buffer aliases and equivalence classes to suppor...
bool isInPlace(OpOperand &opOperand) const
Return true if a value was marked as in-place bufferized.
bool copyBeforeWrite
If set to true, the analysis is skipped.
void insertNewBufferAlias(Value newValue, Value alias)
Insert an info entry for newValue and merge its alias set with that of alias.
static constexpr const bool value
MLIRContext * getContext()
Return the context this operation is associated with.
Definition: Operation.h:147
Block * getOwner() const
Returns the block that owns this argument.
Definition: Value.h:309
void createAliasInfoEntry(Value v)
Add a new entry for v in the aliasInfo and equivalentInfo.
void gatherYieldedTensors(Operation *op)
Find all tensors that are yielded/returned from a block and store them in yieldedTensors.
MutableArrayRef< OpOperand > getOpOperands()
Definition: Operation.h:300
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
unsigned getOperandNumber()
Return which operand this is in the OpOperand list of the Operation.
Definition: Value.cpp:212
static bool hasPrecedingAliasingNonWritableTensor(Value value, OpOperand *currentOpOperand, const BufferizationAliasInfo &aliasInfo, const OneShotAnalysisState &state)
Check the reverse SSA use-def chain (following aliasing OpOperands) for non-writable tensor values...
AnalysisState provides a variety of helper functions for dealing with tensor values.
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
unsigned getRegionNumber()
Return the number of this region in the parent operation.
Definition: Region.cpp:62
void bufferizeOutOfPlace(OpOperand &operand)
Set the inPlace bufferization spec to false.
static void setInPlaceOpOperand(OpOperand &opOperand, bool inPlace)
Mark whether OpOperand will be bufferized inplace.
Region * getParentRegion()
Return the Region in which this Value is defined.
Definition: Value.cpp:41
void applyOnEquivalenceClass(Value v, function_ref< void(Value)> fun) const
Apply fun to all the members of the equivalence class of v.
static bool hasReadAfterWriteInterference(const DenseSet< OpOperand *> &usesRead, const DenseSet< OpOperand *> &usesWrite, const DominanceInfo &domInfo, AnalysisState &state, const BufferizationAliasInfo &aliasInfo)
Given sets of uses and writes, return true if there is a RaW conflict under the assumption that all g...
bool areAliasingBufferizedValues(Value v1, Value v2) const
Return true if v1 and v2 may bufferize to aliasing buffers.
static LogicalResult checkAliasInfoConsistency(Operation *op, const DominanceInfo &domInfo, AnalysisState &state, const BufferizationAliasInfo &aliasInfo)
Assert that the current bufferization decisions are consistent.
U dyn_cast() const
Definition: Value.h:100
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:165
BufferizableOpInterface dynCastBufferizableOp(Operation *op) const
Try to cast the given op to BufferizableOpInterface if the op is allow listed.
static WalkResult advance()
Definition: Visitors.h:51
void bufferizeInPlace(OpOperand &operand, AnalysisState &state)
Set the inPlace bufferization spec to true.
IRValueT get() const
Return the current value being used by this operand.
Definition: UseDefLists.h:137
bool areAliasingBufferizedValues(Value v1, Value v2) const override
Return true if v1 and v2 may bufferize to aliasing buffers.
static WalkResult interrupt()
Definition: Visitors.h:50
A utility result that is used to signal how to proceed with an ongoing walk:
Definition: Visitors.h:34
This class represents an argument of a Block.
Definition: Value.h:300
void applyOnAliases(Value v, function_ref< void(Value)> fun) const
Apply fun to all aliases of v.
Tensor types represent multi-dimensional arrays, and have two variants: RankedTensorType and Unranked...
Definition: BuiltinTypes.h:76
void insertNewBufferEquivalence(Value newValue, Value alias)
Insert an info entry for newValue and merge its alias set with that of alias.
Options for BufferizableOpInterface-based bufferization.
result_range getOpResults()
Definition: Operation.h:337
Instances of the Type class are uniqued, have an immutable identifier and an optional mutable compone...
Definition: Types.h:74
void markInPlace(OpOperand &o)
Mark a value as in-place bufferized.
Operation * getParentOp()
Return the parent operation this region is attached to.
Definition: Region.h:200
bool isValueWritten(Value value) const
Return true if the buffer of the given tensor value is written to.
static LogicalResult bufferizableInPlaceAnalysisImpl(OpOperand &operand, BufferizationAliasInfo &aliasInfo, OneShotAnalysisState &state, const DominanceInfo &domInfo)
Determine if operand can be bufferized in-place.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
bool hasUndefinedContents(OpOperand *opOperand) const override
Return true if the given tensor has undefined contents.
bool printConflicts
If set to true, the IR is annotated with details about RaW conflicts.
static llvm::ManagedStatic< PassManagerOptions > options
static WalkResult skip()
Definition: Visitors.h:52
LogicalResult runOneShotBufferize(Operation *op, const OneShotBufferizationOptions &options)
Run One-Shot Bufferize on the given op: Analysis + Bufferization.
void setAttr(StringAttr name, Attribute value)
If the an attribute exists with the specified name, change it to the new value.
Definition: Operation.h:395
Type getType() const
Return the type of this value.
Definition: Value.h:118
State for analysis-enabled bufferization.
Operation * getOwner() const
Return the owner of this operand.
Definition: UseDefLists.h:40
static bool isInplaceMemoryWrite(OpOperand &opOperand, const BufferizationAliasInfo &aliasInfo, const AnalysisState &state)
Return true if opOperand has been decided to bufferize in-place.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
void unionAliasSets(Value v1, Value v2)
Union the alias sets of v1 and v2.
This class represents an operand of an operation.
Definition: Value.h:251
static void getAliasingReads(DenseSet< OpOperand *> &res, Value root, const BufferizationAliasInfo &aliasInfo, const AnalysisState &state)
Region * getEnclosingRepetitiveRegion(Operation *op)
Return the first enclosing region of the given op that may be executed repetitively as per RegionBran...
LogicalResult bufferizeOp(Operation *op, const BufferizationOptions &options, bool copyBeforeWrite=true, const OpFilter *opFilter=nullptr)
Bufferize op and its nested ops that implement BufferizableOpInterface.
Definition: Bufferize.cpp:388
U cast() const
Definition: Value.h:108
static bool happensBefore(Operation *a, Operation *b, const DominanceInfo &domInfo)
Return true if a happens before b, i.e., a or one of its ancestors properly dominates b and b is not ...
Region * getParentRegion()
Returns the region to which the instruction belongs.
Definition: Operation.h:161
constexpr StringLiteral kInPlaceResultsAttrName
Attribute marker to specify op results that can be bufferized inPlace.
bool insideMutuallyExclusiveRegions(Operation *a, Operation *b)
Return true if a and b are in mutually exclusive regions as per RegionBranchOpInterface.
BufferizationAliasInfo & getAliasInfo()
Return a reference to the BufferizationAliasInfo.
void gatherUndefinedTensorUses(Operation *op)
Find all tensor values in the given operation that have undefined contents and store them in undefine...
bool isOpAllowed(Operation *op) const
Return true if the given op should be bufferized.
bool isa() const
Definition: Types.h:258
static bool isaTensor(Type t)
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
Definition: Operation.cpp:225
static void annotateConflict(OpOperand *uRead, OpOperand *uConflictingWrite, Value lastWrite)
Annotate IR with details about the detected RaW conflict.
bool isInPlace(OpOperand &opOperand) const override
Return true if the given OpResult has been decided to bufferize inplace.
result_range getResults()
Definition: Operation.h:332
This class helps build Operations.
Definition: Builders.h:196
static bool isMemoryWrite(Value value, const AnalysisState &state)
Return true if the given tensor value is a memory write.
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Definition: Value.h:197
Attribute getAttr(StringAttr name)
Return the specified attribute if present, null otherwise.
Definition: Operation.h:371
static LogicalResult assertDestinationPassingStyle(Operation *op, AnalysisState &state, BufferizationAliasInfo &aliasInfo, SmallVector< Operation *> &newOps)
Assert that IR is in destination-passing style.
result_type_range getResultTypes()
Definition: Operation.h:345
bool isProperAncestor(Operation *other)
Return true if this operation is a proper ancestor of the other operation.
Definition: Operation.cpp:176
SetVector< Value > findLastPrecedingWrite(Value value) const
Find the Values of the last preceding write of a given Value.
bool isTensorYielded(Value tensor) const override
Return true if the given tensor (or an aliasing tensor) is yielded from the containing block...
Options for analysis-enabled bufferization.
bool isWritable(Value value) const
Return true if the buffer of the given tensor value is writable.
static void getAliasingInplaceWrites(DenseSet< OpOperand *> &res, Value root, const BufferizationAliasInfo &aliasInfo, const AnalysisState &state)
Base class for generic analysis states.