MLIR  17.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. By default, function boundaries
10 // (FuncOp bbArgs, CallOps, ReturnOps) are treated as "unknown" ops.
11 // OneShotModuleBufferization.cpp is an extension of One-Shot Analysis for
12 // simple call graphs without loops.
13 //
14 // One-Shot Bufferize consists of three phases.
15 //
16 // 1. Analyze ops to decide which OpOperands can bufferize inplace, i.e.,
17 // without inserting buffer copies. The analysis queries op bufferization
18 // semantics via `BufferizableOpInterface`.
19 // 2. Insert copies for OpOperands that were decided to bufferize out-of-place
20 // in tensor land during `TensorCopyInsertion`.
21 // 3. Bufferize ops by calling `BufferizableOpInterface::bufferize`.
22 //
23 // This file contains only the analysis. For convenience, this file also
24 // contains a helper function `runOneShotBufferize` that analyzes an op (and its
25 // nested ops) and then bufferizes it.
26 //
27 // Inplace bufferization decisions are passed from the analysis to the
28 // `TensorCopyInsertion` phase via `AnalysisState`. They can be printed for
29 // debugging purposes with `testAnalysisOnly`.
30 //
31 // Ops that do not implement `BufferizableOpInterface` can be analyzed but are
32 // treated conservatively. E.g., the analysis has to assume that their tensor
33 // OpOperands bufferize to memory writes. While such ops can be analyzed, they
34 // are not bufferized and remain in the IR. to_tensor and to_memref ops are
35 // inserted at the bufferization boundary.
36 //
37 // This analysis caters to high-performance codegen where buffer reuse is deemed
38 // critical: the analysis should fail if the bufferized form of the function
39 // needs to return a buffer, unless `allowReturnAllocs` is enabled.
40 
42 
43 #include <random>
44 #include <optional>
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 
61 
62 // Run mlir-opt with `-debug-only="one-shot-analysis"` for detailed debug
63 // output.
64 #define DEBUG_TYPE "one-shot-analysis"
65 
66 using namespace mlir;
67 using namespace mlir::bufferization;
68 
69 static bool isaTensor(Type t) { return isa<TensorType>(t); }
70 
71 //===----------------------------------------------------------------------===//
72 // Bufferization-specific attribute manipulation.
73 // These are for testing and debugging only. Bufferization information is stored
74 // in OneShotBufferizationState. When run with `testAnalysisOnly`, the IR is
75 // annotated with the results of the analysis, so that they can be checked in
76 // tests.
77 //===----------------------------------------------------------------------===//
78 
79 /// Attribute marker to specify op operands that bufferize in-place.
80 constexpr StringLiteral kInPlaceOperandsAttrName = "__inplace_operands_attr__";
81 
82 constexpr StringLiteral kAliasSetAttrName = "__alias_set_attr__";
83 
84 /// Mark whether OpOperand will be bufferized inplace.
85 static void setInPlaceOpOperand(OpOperand &opOperand, bool inPlace) {
86  Operation *op = opOperand.getOwner();
87  SmallVector<StringRef> inPlaceVector;
88  if (auto attr = op->getAttr(kInPlaceOperandsAttrName)) {
89  inPlaceVector = SmallVector<StringRef>(llvm::to_vector<4>(
90  cast<ArrayAttr>(attr).getAsValueRange<StringAttr>()));
91  } else {
92  inPlaceVector = SmallVector<StringRef>(op->getNumOperands(), "none");
93  for (OpOperand &opOperand : op->getOpOperands())
94  if (isa<TensorType>(opOperand.get().getType()))
95  inPlaceVector[opOperand.getOperandNumber()] = "false";
96  }
97  inPlaceVector[opOperand.getOperandNumber()] = inPlace ? "true" : "false";
99  OpBuilder(op).getStrArrayAttr(inPlaceVector));
100 }
101 
102 //===----------------------------------------------------------------------===//
103 // OneShotAnalysisState
104 //===----------------------------------------------------------------------===//
105 
109  // Set up alias sets.
110  op->walk([&](Operation *op) {
111  for (Value v : op->getResults())
112  if (isa<TensorType>(v.getType()))
114  for (Region &r : op->getRegions())
115  for (Block &b : r.getBlocks())
116  for (auto bbArg : b.getArguments())
117  if (isa<TensorType>(bbArg.getType()))
118  createAliasInfoEntry(bbArg);
119  });
120 
121  // Mark OpOperands in-place that must bufferize in-place.
122  op->walk([&](BufferizableOpInterface bufferizableOp) {
123  if (!options.isOpAllowed(bufferizableOp))
124  return WalkResult::skip();
125  for (OpOperand &opOperand : bufferizableOp->getOpOperands())
126  if (isa<TensorType>(opOperand.get().getType()))
127  if (bufferizableOp.mustBufferizeInPlace(opOperand, *this))
128  bufferizeInPlace(opOperand);
129  return WalkResult::advance();
130  });
131 }
132 
134  Value v, function_ref<void(Value)> fun) const {
135  auto leaderIt = equivalentInfo.findLeader(v);
136  for (auto mit = leaderIt, meit = equivalentInfo.member_end(); mit != meit;
137  ++mit) {
138  fun(*mit);
139  }
140 }
141 
143  function_ref<void(Value)> fun) const {
144  auto leaderIt = aliasInfo.findLeader(v);
145  for (auto mit = leaderIt, meit = aliasInfo.member_end(); mit != meit; ++mit) {
146  fun(*mit);
147  }
148 }
149 
151  Value v2) const {
152  return equivalentInfo.isEquivalent(v1, v2);
153 }
154 
156  Value v2) const {
157  return aliasInfo.isEquivalent(v1, v2);
158 }
159 
161  if (inplaceBufferized.contains(&operand))
162  return;
163  inplaceBufferized.insert(&operand);
164  for (AliasingOpResult alias : getAliasingOpResults(operand))
165  aliasInfo.unionSets(alias.opResult, operand.get());
166  ++statNumTensorInPlace;
167 }
168 
170  assert(!inplaceBufferized.contains(&operand) &&
171  "OpOperand was already decided to bufferize inplace");
172  ++statNumTensorOutOfPlace;
173 }
174 
176  aliasInfo.insert(v);
177  equivalentInfo.insert(v);
178 }
179 
180 // Gather yielded tensors in `yieldedTensors` by querying all aliases. This is
181 // to ensure that such information is available during bufferization time.
182 // Alias information can no longer be queried once we have started modifying
183 // the IR.
185  op->walk([&](Operation *returnOp) {
186  if (!isRegionReturnLike(returnOp) || !getOptions().isOpAllowed(returnOp))
187  return WalkResult::advance();
188 
189  for (OpOperand &returnValOperand : returnOp->getOpOperands()) {
190  Value returnVal = returnValOperand.get();
191  // Skip non-tensor values.
192  if (!isa<TensorType>(returnVal.getType()))
193  continue;
194 
195  // Add all aliases of the returned value. But only the ones that are in
196  // the same block.
197  applyOnAliases(returnVal, [&](Value v) {
198  if (auto bbArg = dyn_cast<BlockArgument>(v)) {
199  if (bbArg.getOwner()->getParentOp() == returnOp->getParentOp())
200  yieldedTensors.insert(bbArg);
201  return;
202  }
203  Operation *definingOp = v.getDefiningOp();
204  if (definingOp->getParentOp() == returnOp->getParentOp())
205  yieldedTensors.insert(v);
206  });
207  }
208 
209  return WalkResult::advance();
210  });
211 }
212 
213 void OneShotAnalysisState::gatherUndefinedTensorUses(Operation *op) {
214  op->walk([&](Operation *op) {
215  // Skip unknown ops.
216  auto bufferizableOp = getOptions().dynCastBufferizableOp(op);
217  if (!bufferizableOp)
218  return WalkResult::skip();
219 
220  // Check all tensor OpResults.
221  for (OpResult opResult : op->getOpResults()) {
222  if (!isa<TensorType>(opResult.getType()))
223  continue;
224 
225  // If there is no preceding definition, the tensor contents are
226  // undefined.
227  if (findDefinitionsCached(opResult).empty())
228  for (OpOperand &use : opResult.getUses())
229  undefinedTensorUses.insert(&use);
230  }
231 
232  return WalkResult::advance();
233  });
234 }
235 
236 bool OneShotAnalysisState::hasUndefinedContents(OpOperand *opOperand) const {
237  return undefinedTensorUses.contains(opOperand);
238 }
239 
240 bool OneShotAnalysisState::isInPlace(OpOperand &opOperand) const {
241  return inplaceBufferized.contains(&opOperand);
242 }
243 
244 bool OneShotAnalysisState::isTensorYielded(Value tensor) const {
245  return yieldedTensors.contains(tensor);
246 }
247 
248 bool OneShotAnalysisState::isValueWritten(Value value) const {
249  bool isWritten = false;
250  applyOnAliases(value, [&](Value val) {
251  for (OpOperand &use : val.getUses())
252  if (isInPlace(use) && bufferizesToMemoryWrite(use))
253  isWritten = true;
254  });
255  return isWritten;
256 }
257 
258 bool OneShotAnalysisState::isWritable(Value value) const {
259  // TODO: Out-of-place bufferized value could be considered writable.
260  if (auto bufferizableOp = getOptions().dynCastBufferizableOp(value))
261  return bufferizableOp.isWritable(value, *this);
262 
263  // Query BufferizableOpInterface to see if the BlockArgument is writable.
264  if (auto bbArg = dyn_cast<BlockArgument>(value))
265  if (auto bufferizableOp =
266  getOptions().dynCastBufferizableOp(bbArg.getOwner()->getParentOp()))
267  return bufferizableOp.isWritable(bbArg, *this);
268 
269  // Not a bufferizable op: The conservative answer is "not writable".
270  return false;
271 }
272 
273 void OneShotAnalysisState::unionAliasSets(Value v1, Value v2) {
274  aliasInfo.unionSets(v1, v2);
275 }
276 
277 void OneShotAnalysisState::unionEquivalenceClasses(Value v1, Value v2) {
278  equivalentInfo.unionSets(v1, v2);
279 }
280 
281 OneShotAnalysisState::Extension::~Extension() = default;
282 
283 //===----------------------------------------------------------------------===//
284 // Bufferization-specific alias analysis.
285 //===----------------------------------------------------------------------===//
286 
287 /// Return true if opOperand has been decided to bufferize in-place.
288 static bool isInplaceMemoryWrite(OpOperand &opOperand,
289  const OneShotAnalysisState &state) {
290  // OpOperands that do not bufferize to a memory write do not write in-place.
291  if (!state.bufferizesToMemoryWrite(opOperand))
292  return false;
293  // Check current bufferization decisions.
294  return state.isInPlace(opOperand);
295 }
296 
297 /// Return true if `a` happens before `b`, i.e., `a` or one of its ancestors
298 /// properly dominates `b` and `b` is not inside `a`.
299 static bool happensBefore(Operation *a, Operation *b,
300  const DominanceInfo &domInfo) {
301  do {
302  // TODO: Instead of isProperAncestor + properlyDominates, we should use
303  // properlyDominatesImpl(a, b, /*enclosingOpOk=*/false)
304  if (a->isProperAncestor(b))
305  return false;
306  if (domInfo.properlyDominates(a, b))
307  return true;
308  } while ((a = a->getParentOp()));
309  return false;
310 }
311 
312 /// Return `true` if op dominance can be used to rule out a read-after-write
313 /// conflicts based on the ordering of ops.
314 ///
315 /// Generalized op dominance can often be used to rule out potential conflicts
316 /// due to "read happens before write". E.g., the following IR is not a RaW
317 /// conflict because the read happens *before* the write.
318 ///
319 /// Example 1:
320 /// %0 = ... : tensor<?xf32> // DEF
321 /// "reading_op"(%0) : tensor<?xf32> // READ
322 /// %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32> // WRITE
323 ///
324 /// This is no longer true inside loops (or repetitive regions). In such cases,
325 /// there may not be a meaningful `happensBefore` relationship because ops
326 /// could be executed multiple times. E.g.:
327 ///
328 /// Example 2:
329 /// %0 = ... : tensor<?xf32> // DEF
330 /// scf.for ... {
331 /// "reading_op"(%0) : tensor<?xf32> // READ
332 /// %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32> // WRITE
333 /// ...
334 /// }
335 ///
336 /// In the above example, reading_op happens before writing_op according to
337 /// op dominance. However, both ops may happen multiple times; in
338 /// particular, the second execution of reading_op happens after the first
339 /// execution of writing_op. This is problematic because the tensor %0 they
340 /// operate on (i.e., the "definition") is defined outside of the loop.
341 ///
342 /// On a high-level, there is a potential RaW in a program if there exists a
343 /// possible program execution such that there is a sequence of DEF, followed
344 /// by WRITE, followed by READ. Each additional DEF resets the sequence.
345 ///
346 /// E.g.:
347 /// No conflict: DEF, WRITE, DEF, READ
348 /// Potential conflict: DEF, READ, WRITE, READ, WRITE
349 ///
350 /// Example 1 has no conflict: DEF, READ, WRITE
351 /// Example 2 has a potential conflict: DEF, (READ, WRITE)*
352 //
353 /// Example 3:
354 /// scf.for ... {
355 /// %0 = ... : tensor<?xf32>
356 /// "reading_op"(%0) : tensor<?xf32>
357 /// %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32>
358 /// ...
359 /// }
360 /// This has no conflict: (DEF, READ, WRITE)*
361 ///
362 /// Example 4:
363 /// %0 = ... : tensor<?xf32>
364 /// scf.for ... {
365 /// scf.for ... { "reading_op"(%0) }
366 /// %1 = "writing_op"(%0)
367 /// }
368 /// This has a potential conflict: DEF, ((READ)*, WRITE)*
369 ///
370 /// Example 5:
371 /// %0 = ... : tensor<?xf32>
372 /// scf.for ... { %1 = "writing_op"(%0) }
373 /// scf.for ... { "reading_op"(%0) }
374 /// This has a potential conflict: DEF, WRITE*, READ*
375 ///
376 /// The following rules are used to rule out RaW conflicts via ordering of ops:
377 ///
378 /// 1. If the closest enclosing repetitive region of DEF is a proper ancestor of
379 /// a repetitive region that enclosing both READ and WRITE, we cannot rule
380 /// out RaW conflict due to the ordering of ops.
381 /// 2. Otherwise: There are no loops that interfere with our analysis; for
382 /// analysis purposes, we can assume that there are no loops/repetitive
383 /// regions. I.e., we can rule out a RaW conflict if READ happensBefore WRITE
384 /// or WRITE happensBefore DEF. (Checked in `hasReadAfterWriteInterference`.)
385 ///
386 bool canUseOpDominance(OpOperand *uRead, OpOperand *uWrite,
387  const SetVector<Value> &definitions,
388  const AnalysisState &state) {
389  const BufferizationOptions &options = state.getOptions();
390  for (Value def : definitions) {
393 
394  // READ and DEF are in the same repetitive region. `happensBefore` can be
395  // used to rule out RaW conflicts due to op ordering.
396  if (rRead == rDef)
397  continue;
398 
399  // Find the enclosing repetitive region of READ that is closest to DEF but
400  // not the repetitive region of DEF itself.
401  while (true) {
402  Region *nextRegion = getNextEnclosingRepetitiveRegion(rRead, options);
403  if (nextRegion == rDef)
404  break;
405  assert(nextRegion && "expected to find another repetitive region");
406  rRead = nextRegion;
407  }
408 
409  // We cannot use op dominance if WRITE is inside the same repetitive region.
410  if (rRead->getParentOp()->isAncestor(uWrite->getOwner()))
411  return false;
412  }
413  return true;
414 }
415 
416 /// Annotate IR with details about the detected RaW conflict.
417 static void annotateConflict(OpOperand *uRead, OpOperand *uConflictingWrite,
418  Value definition) {
419  static uint64_t counter = 0;
420  Operation *readingOp = uRead->getOwner();
421  Operation *conflictingWritingOp = uConflictingWrite->getOwner();
422 
423  OpBuilder b(conflictingWritingOp->getContext());
424  std::string id = "C_" + std::to_string(counter++);
425 
426  std::string conflictingWriteAttr =
427  id +
428  "[CONFL-WRITE: " + std::to_string(uConflictingWrite->getOperandNumber()) +
429  "]";
430  conflictingWritingOp->setAttr(conflictingWriteAttr, b.getUnitAttr());
431 
432  std::string readAttr =
433  id + "[READ: " + std::to_string(uRead->getOperandNumber()) + "]";
434  readingOp->setAttr(readAttr, b.getUnitAttr());
435 
436  if (auto opResult = dyn_cast<OpResult>(definition)) {
437  std::string defAttr =
438  id + "[DEF: result " + std::to_string(opResult.getResultNumber()) + "]";
439  opResult.getDefiningOp()->setAttr(defAttr, b.getUnitAttr());
440  } else {
441  auto bbArg = cast<BlockArgument>(definition);
442  std::string defAttr =
443  id + "[DEF: bbArg " + std::to_string(bbArg.getArgNumber()) + "]";
444  bbArg.getOwner()->getParentOp()->setAttr(defAttr, b.getUnitAttr());
445  }
446 }
447 
448 /// Given sets of uses and writes, return true if there is a RaW conflict under
449 /// the assumption that all given reads/writes alias the same buffer and that
450 /// all given writes bufferize inplace.
451 ///
452 /// A conflict is: According to SSA use-def chains, a read R is supposed to read
453 /// the result of a definition W1. But because of bufferization decisions, R
454 /// actually reads another definition W2.
455 static bool
457  const DenseSet<OpOperand *> &usesWrite,
458  const DominanceInfo &domInfo,
459  OneShotAnalysisState &state) {
460  const BufferizationOptions &options = state.getOptions();
461 
462  for (OpOperand *uRead : usesRead) {
463  Operation *readingOp = uRead->getOwner();
464  LLVM_DEBUG(llvm::dbgs() << "\n- check conflict:\n");
465  LLVM_DEBUG(llvm::dbgs() << " uRead = operand " << uRead->getOperandNumber()
466  << " of " << *readingOp << "\n");
467 
468  // Find the definition of uRead by following the SSA use-def chain.
469  // E.g.:
470  //
471  // %0 = "writing_op"(%t) : tensor<?x32> -> tensor<?xf32>
472  // %1 = "aliasing_op"(%0) : tensor<?x32> -> tensor<?xf32>
473  // %2 = "reading_op"(%1) : : tensor<?x32> -> not_a_tensor_type
474  //
475  // In the above example, if uRead is the OpOperand of reading_op, the
476  // definition is %0. Note that operations that create an alias but do not
477  // bufferize to a memory write (such as ExtractSliceOp) are skipped.
478  const SetVector<Value> &definitions =
479  state.findDefinitionsCached(uRead->get());
480  if (definitions.empty()) {
481  // Fast path: No conflict if there are no definitions.
482  LLVM_DEBUG(llvm::dbgs()
483  << " no conflict: read value has no definitions\n");
484  continue;
485  }
486 
487  // Look for conflicting memory writes. Potential conflicts are writes to an
488  // alias that have been decided to bufferize inplace.
489  for (OpOperand *uConflictingWrite : usesWrite) {
490  LLVM_DEBUG(llvm::dbgs() << " unConflictingWrite = operand "
491  << uConflictingWrite->getOperandNumber() << " of "
492  << *uConflictingWrite->getOwner() << "\n");
493 
494  // Check if op dominance can be used to rule out read-after-write
495  // conflicts.
496  bool useDominance =
497  canUseOpDominance(uRead, uConflictingWrite, definitions, state);
498  LLVM_DEBUG(llvm::dbgs() << "\n- useDominance = " << useDominance << "\n");
499 
500  // Throughout this loop, check for multiple requirements that have to be
501  // met for uConflictingWrite to be an actual conflict.
502  Operation *conflictingWritingOp = uConflictingWrite->getOwner();
503 
504  // Inside of repetitive regions, ops may be executed multiple times and op
505  // dominance cannot be used to rule out conflicts.
506  if (useDominance) {
507  // No conflict if the readingOp dominates conflictingWritingOp, i.e.,
508  // the write is not visible when reading.
509  //
510  // Note: If ops are executed multiple times (e.g., because they are
511  // inside a loop), there may be no meaningful `happensBefore`
512  // relationship.
513  if (happensBefore(readingOp, conflictingWritingOp, domInfo)) {
514  LLVM_DEBUG(llvm::dbgs()
515  << " no conflict: read happens before write\n");
516  continue;
517  }
518 
519  // No conflict if the reading use equals the use of the conflicting
520  // write. A use cannot conflict with itself.
521  //
522  // Note: Just being the same op is not enough. It has to be the same
523  // use.
524  // Note: If the op is executed multiple times (e.g., because it is
525  // inside a loop), it may be conflicting with itself.
526  if (uConflictingWrite == uRead) {
527  LLVM_DEBUG(llvm::dbgs()
528  << " no conflict: read and write are same use\n");
529  continue;
530  }
531 
532  // Ops are not conflicting if they are in mutually exclusive regions.
533  //
534  // Note: If ops are executed multiple times (e.g., because they are
535  // inside a loop), mutually exclusive regions may be executed
536  // multiple times.
537  if (insideMutuallyExclusiveRegions(readingOp, conflictingWritingOp)) {
538  LLVM_DEBUG(llvm::dbgs() << " no conflict: read and write are in "
539  "mutually exclusive regions\n");
540  continue;
541  }
542  }
543 
544  // No conflict if the op interface says so.
545  if (auto bufferizableOp = options.dynCastBufferizableOp(readingOp)) {
546  if (bufferizableOp.isNotConflicting(uRead, uConflictingWrite, state)) {
547  LLVM_DEBUG(llvm::dbgs()
548  << " no conflict: op interace of reading op says 'no'\n");
549  continue;
550  }
551  }
552 
553  if (conflictingWritingOp != readingOp) {
554  if (auto bufferizableOp =
555  options.dynCastBufferizableOp(conflictingWritingOp)) {
556  if (bufferizableOp.isNotConflicting(uRead, uConflictingWrite,
557  state)) {
558  LLVM_DEBUG(
559  llvm::dbgs()
560  << " no conflict: op interace of writing op says 'no'\n");
561  continue;
562  }
563  }
564  }
565 
566  // Check all possible definitions.
567  for (Value definition : definitions) {
568  LLVM_DEBUG(llvm::dbgs() << " * definition = " << definition << "\n");
569 
570  // No conflict if the conflicting write happens before the definition.
571  if (Operation *defOp = definition.getDefiningOp()) {
572  if (happensBefore(conflictingWritingOp, defOp, domInfo)) {
573  // conflictingWritingOp happens before defOp. No conflict.
574  LLVM_DEBUG(llvm::dbgs()
575  << " no conflict: write happens before definition\n");
576  continue;
577  }
578  // No conflict if conflictingWritingOp is contained in defOp.
579  if (defOp->isProperAncestor(conflictingWritingOp)) {
580  LLVM_DEBUG(
581  llvm::dbgs()
582  << " no conflict: write is contained in definition\n");
583  continue;
584  }
585  } else {
586  auto bbArg = cast<BlockArgument>(definition);
587  Block *block = bbArg.getOwner();
588  if (!block->findAncestorOpInBlock(*conflictingWritingOp)) {
589  LLVM_DEBUG(llvm::dbgs() << " no conflict: definition is bbArg "
590  "and write happens outside of block\n");
591  // conflictingWritingOp happens outside of the block. No
592  // conflict.
593  continue;
594  }
595  }
596 
597  // No conflict if the conflicting write and the definition are the same
598  // use.
599  AliasingOpResultList aliases =
600  state.getAliasingOpResults(*uConflictingWrite);
601  if (aliases.getNumAliases() == 1 &&
602  aliases.getAliases()[0].opResult == definition) {
603  LLVM_DEBUG(llvm::dbgs()
604  << " no conflict: definition and write are same\n");
605  continue;
606  }
607 
608  // All requirements are met. Conflict found!
609 
610  if (options.printConflicts)
611  annotateConflict(uRead, uConflictingWrite, definition);
612  LLVM_DEBUG(llvm::dbgs() << " => RaW CONFLICT FOUND\n");
613  return true;
614  }
615  }
616  }
617 
618  return false;
619 }
620 
621 // Helper function to iterate on aliases of `root` and capture the writes.
623  const OneShotAnalysisState &state) {
624  state.applyOnAliases(root, [&](Value alias) {
625  for (auto &use : alias.getUses())
626  // Inplace write to a value that aliases root.
627  if (isInplaceMemoryWrite(use, state))
628  res.insert(&use);
629  });
630 }
631 
632 // Helper function to iterate on aliases of `root` and capture the reads.
634  const OneShotAnalysisState &state) {
635  state.applyOnAliases(root, [&](Value alias) {
636  for (auto &use : alias.getUses()) {
637  // Read of a value that aliases root.
638  if (state.bufferizesToMemoryRead(use)) {
639  res.insert(&use);
640  continue;
641  }
642 
643  // Read of a dependent value in the SSA use-def chain. E.g.:
644  //
645  // %0 = ...
646  // %1 = tensor.extract_slice %0 {not_analyzed_yet}
647  // "read"(%1)
648  //
649  // In the above example, getAliasingReads(%0) includes the first OpOperand
650  // of the tensor.extract_slice op. The extract_slice itself does not read
651  // but its aliasing result is eventually fed into an op that does.
652  //
653  // Note: This is considered a "read" only if the use does not bufferize to
654  // a memory write. (We already ruled out memory reads. In case of a memory
655  // write, the buffer would be entirely overwritten; in the above example
656  // there would then be no flow of data from the extract_slice operand to
657  // its result's uses.)
658  if (!state.bufferizesToMemoryWrite(use)) {
659  AliasingOpResultList aliases = state.getAliasingOpResults(use);
660  if (llvm::any_of(aliases, [&](AliasingOpResult a) {
661  return state.isValueRead(a.opResult);
662  }))
663  res.insert(&use);
664  }
665  }
666  });
667 }
668 
669 /// Return true if bufferizing `operand` inplace would create a conflict. A read
670 /// R and a write W of the same alias set is a conflict if inplace bufferization
671 /// of W changes the value read by R to a value different from the one that
672 /// would be expected by tracing back R's origin through SSA use-def chains.
673 /// A conflict can only be introduced by a new alias and/or an inplace
674 /// bufferization decision.
675 ///
676 /// Example:
677 /// %0 = tensor.extract_slice %t[...][...][1, 1] {inplace?}
678 /// %1 = vector.transfer_write %v1, %t {inplace} : vector<5xf32>, tensor<?xf32>
679 /// %e = tensor.extract_slice %1
680 /// %2 = vector.transfer_write %v2, %0 {inplace} : vector<6xf32>, tensor<?xf32>
681 /// %3 = vector.transfer_read %e, %cst : tensor<?xf32>, vector<7xf32>
682 ///
683 /// In the above example, the two TransferWriteOps have already been decided to
684 /// bufferize inplace. Bufferizing the ExtractSliceOp inplace would create a
685 /// conflict because:
686 /// * According to SSA use-def chains, we expect to read the result of %1.
687 /// * However, adding an alias {%0, %t} would mean that the second
688 /// TransferWriteOp overwrites the result of the first one. Therefore, the
689 /// TransferReadOp would no longer be reading the result of %1.
690 ///
691 /// If `checkConsistencyOnly` is true, this function checks if there is a
692 /// read-after-write conflict without bufferizing `operand` inplace. This would
693 /// indicate a problem with the current inplace bufferization decisions.
694 ///
695 /// Note: If `checkConsistencyOnly`, this function may be called with a null
696 /// OpResult. In that case, only the consistency of bufferization decisions
697 /// involving aliases of the given OpOperand are checked.
699  OpOperand &operand, const DominanceInfo &domInfo,
700  OneShotAnalysisState &state, bool checkConsistencyOnly = false) {
701  // Collect reads and writes of all aliases of OpOperand and OpResult.
702  DenseSet<OpOperand *> usesRead, usesWrite;
703  getAliasingReads(usesRead, operand.get(), state);
704  getAliasingInplaceWrites(usesWrite, operand.get(), state);
705  for (AliasingOpResult alias : state.getAliasingOpResults(operand)) {
706  getAliasingReads(usesRead, alias.opResult, state);
707  getAliasingInplaceWrites(usesWrite, alias.opResult, state);
708  }
709  if (!checkConsistencyOnly && state.bufferizesToMemoryWrite(operand))
710  usesWrite.insert(&operand);
711 
712  return hasReadAfterWriteInterference(usesRead, usesWrite, domInfo, state);
713 }
714 
715 /// Annotate IR with details about the detected non-writability conflict.
716 static void annotateNonWritableTensor(Value value) {
717  static int64_t counter = 0;
718  OpBuilder b(value.getContext());
719  std::string id = "W_" + std::to_string(counter++);
720  if (auto opResult = dyn_cast<OpResult>(value)) {
721  std::string attr = id + "[NOT-WRITABLE: result " +
722  std::to_string(opResult.getResultNumber()) + "]";
723  opResult.getDefiningOp()->setAttr(attr, b.getUnitAttr());
724  } else {
725  auto bbArg = cast<BlockArgument>(value);
726  std::string attr = id + "[NOT-WRITABLE: bbArg " +
727  std::to_string(bbArg.getArgNumber()) + "]";
728  bbArg.getOwner()->getParentOp()->setAttr(attr, b.getUnitAttr());
729  }
730 }
731 
732 /// Return true if bufferizing `operand` inplace would create a write to a
733 /// non-writable buffer.
734 static bool
736  OneShotAnalysisState &state,
737  bool checkConsistencyOnly = false) {
738  bool foundWrite =
739  !checkConsistencyOnly && state.bufferizesToMemoryWrite(operand);
740 
741  if (!foundWrite) {
742  // Collect writes of all aliases of OpOperand and OpResult.
743  DenseSet<OpOperand *> usesWrite;
744  getAliasingInplaceWrites(usesWrite, operand.get(), state);
745  for (AliasingOpResult alias : state.getAliasingOpResults(operand))
746  getAliasingInplaceWrites(usesWrite, alias.opResult, state);
747  foundWrite = !usesWrite.empty();
748  }
749 
750  if (!foundWrite)
751  return false;
752 
753  // Look for a read-only tensor among all aliases.
754  bool foundReadOnly = false;
755  auto checkReadOnly = [&](Value v) {
756  if (!state.isWritable(v)) {
757  foundReadOnly = true;
758  if (state.getOptions().printConflicts)
760  }
761  };
762  state.applyOnAliases(operand.get(), checkReadOnly);
763  for (AliasingOpResult alias : state.getAliasingOpResults(operand))
764  state.applyOnAliases(alias.opResult, checkReadOnly);
765  if (foundReadOnly) {
766  LLVM_DEBUG(llvm::dbgs() << "=> NOT WRITABLE\n");
767  return true;
768  }
769 
770  return false;
771 }
772 
773 //===----------------------------------------------------------------------===//
774 // Bufferization analyses.
775 //===----------------------------------------------------------------------===//
776 
777 // Find the values that define the contents of the given value.
779 OneShotAnalysisState::findDefinitionsCached(Value value) {
780  if (!cachedDefinitions.count(value))
781  cachedDefinitions[value] = findDefinitions(value);
782  return cachedDefinitions[value];
783 }
784 
785 void OneShotAnalysisState::resetCache() { cachedDefinitions.clear(); }
786 
787 /// Determine if `operand` can be bufferized in-place.
788 static LogicalResult
790  const DominanceInfo &domInfo) {
791  LLVM_DEBUG(
792  llvm::dbgs() << "//===-------------------------------------------===//\n"
793  << "Analyzing operand #" << operand.getOperandNumber()
794  << " of " << *operand.getOwner() << "\n");
795 
796  bool foundInterference =
797  wouldCreateWriteToNonWritableBuffer(operand, state) ||
798  wouldCreateReadAfterWriteInterference(operand, domInfo, state);
799 
800  if (foundInterference)
801  state.bufferizeOutOfPlace(operand);
802  else
803  state.bufferizeInPlace(operand);
804 
805  LLVM_DEBUG(llvm::dbgs()
806  << "//===-------------------------------------------===//\n");
807  return success();
808 }
809 
812  const DominanceInfo &domInfo) {
813  for (OpOperand &opOperand : op->getOpOperands())
814  if (isa<TensorType>(opOperand.get().getType()))
815  if (failed(bufferizableInPlaceAnalysisImpl(opOperand, *this, domInfo)))
816  return failure();
817  return success();
818 }
819 
820 /// Return true if the given op has a tensor result or a tensor operand.
821 static bool hasTensorSemantics(Operation *op) {
822  bool hasTensorResult = any_of(op->getResultTypes(), isaTensor);
823  bool hasTensorOperand = any_of(op->getOperandTypes(), isaTensor);
824  return hasTensorResult || hasTensorOperand;
825 }
826 
827 /// Analyze equivalence of tied OpResult/OpOperand pairs of the given ops.
829  OneShotAnalysisState &state) {
830  for (Operation *op : ops) {
831  if (auto bufferizableOp = state.getOptions().dynCastBufferizableOp(op)) {
832  for (OpResult opResult : op->getOpResults()) {
833  if (!isa<TensorType>(opResult.getType()))
834  continue;
835  AliasingOpOperandList aliases = state.getAliasingOpOperands(opResult);
836  if (aliases.getNumAliases() == 0)
837  // Nothing to do if there are no aliasing OpOperands.
838  continue;
839 
840  Value firstOperand = aliases.begin()->opOperand->get();
841  bool allEquivalent = true;
842  for (AliasingOpOperand alias : aliases) {
843  bool isEquiv = alias.relation == BufferRelation::Equivalent;
844  bool isInPlace = state.isInPlace(*alias.opOperand);
845  Value operand = alias.opOperand->get();
846  if (isEquiv && isInPlace && alias.isDefinite) {
847  // Found a definite, equivalent alias. Merge equivalence sets.
848  // There can only be one definite alias, so we can stop here.
849  state.unionEquivalenceClasses(opResult, operand);
850  allEquivalent = false;
851  break;
852  }
853  if (!isEquiv || !isInPlace)
854  allEquivalent = false;
855  if (!state.areEquivalentBufferizedValues(operand, firstOperand))
856  allEquivalent = false;
857  }
858 
859  // If all "maybe" aliases are equivalent and the OpResult is not a new
860  // allocation, it is a definite, equivalent alias. E.g.:
861  //
862  // aliasingOpOperands(%r) = {(%t0, EQUIV, MAYBE), (%t1, EQUIV, MAYBE)}
863  // aliasingOpResults(%t0) = {(%r, EQUIV, MAYBE)}
864  // aliasingOpResults(%t1) = {(%r, EQUIV, MAYBE)}
865  // %r = arith.select %c, %t0, %t1 : tensor<?xf32>
866  //
867  // If %t0 and %t1 are equivalent, it is safe to union the equivalence
868  // classes of %r, %t0 and %t1.
869  if (allEquivalent && !bufferizableOp.bufferizesToAllocation(opResult))
870  state.unionEquivalenceClasses(opResult, firstOperand);
871  }
872  }
873  }
874 }
875 
876 /// Analyze equivalence of tied OpResult/OpOperand pairs of all ops contained
877 /// in `op`.
879  // Traverse ops in PostOrder: Nested ops first, then enclosing ops.
881  op->walk<WalkOrder::PostOrder>([&](Operation *op) {
882  // No tensors => no buffers.
883  if (none_of(op->getResultTypes(), isaTensor))
884  return;
885  ops.push_back(op);
886  });
887 
888  equivalenceAnalysis(ops, state);
889 }
890 
892  const DominanceInfo &domInfo) {
893  // Collect ops so we can build our own reverse traversal.
895  op->walk([&](Operation *op) {
896  // No tensors => no buffers.
897  if (!hasTensorSemantics(op))
898  return;
899  ops.push_back(op);
900  });
901 
902  if (getOptions().analysisFuzzerSeed) {
903  // This is a fuzzer. For testing purposes only. Randomize the order in which
904  // operations are analyzed. The bufferization quality is likely worse, but
905  // we want to make sure that no assertions are triggered anywhere.
906  std::mt19937 g(getOptions().analysisFuzzerSeed);
907  llvm::shuffle(ops.begin(), ops.end(), g);
908  }
909 
913  // Default: Walk ops in reverse for better interference analysis.
914  for (Operation *op : reverse(ops))
915  if (failed(analyzeSingleOp(op, domInfo)))
916  return failure();
917  } else if (heuristic ==
919  for (Operation *op : ops)
920  if (failed(analyzeSingleOp(op, domInfo)))
921  return failure();
922  } else {
923  llvm_unreachable("unsupported heuristic");
924  }
925 
926  equivalenceAnalysis(op, *this);
927  return success();
928 }
929 
930 /// Assert that the current bufferization decisions are consistent.
932  const DominanceInfo &domInfo,
933  OneShotAnalysisState &state) {
934  const BufferizationOptions &options = state.getOptions();
935 
936  WalkResult walkResult = op->walk([&](BufferizableOpInterface op) {
937  // Skip ops that are not in the filter.
938  if (!options.isOpAllowed(op.getOperation()))
939  return WalkResult::advance();
940 
941  // Input IR may not contain any ToMemrefOps. These are not supported because
942  // the analysis cannot follow the data flow through memrefs.
943  if (isa<ToMemrefOp>(op.getOperation())) {
944  op->emitError("to_memref ops are not supported by One-Shot Analysis");
945  return WalkResult::interrupt();
946  }
947 
948  // Input IR may not contain any ToTensorOps without the "restrict"
949  // attribute. Such tensors may alias any other tensor, which is currently
950  // not handled in the analysis.
951  if (auto toTensorOp = dyn_cast<ToTensorOp>(op.getOperation())) {
952  if (!toTensorOp.getRestrict()) {
953  op->emitError("to_tensor ops without `restrict` are not supported by "
954  "One-Shot Analysis");
955  return WalkResult::interrupt();
956  }
957  }
958 
959  for (OpOperand &opOperand : op->getOpOperands()) {
960  if (isa<TensorType>(opOperand.get().getType())) {
961  if (wouldCreateReadAfterWriteInterference(
962  opOperand, domInfo, state,
963  /*checkConsistencyOnly=*/true)) {
964  // This error can happen if certain "mustBufferizeInPlace" interface
965  // methods are implemented incorrectly, such that the IR already has
966  // a RaW conflict before making any bufferization decisions.
967  op->emitError("input IR has RaW conflict");
968  return WalkResult::interrupt();
969  }
970  }
971  }
972 
973  return WalkResult::advance();
974  });
975 
976  return success(!walkResult.wasInterrupted());
977 }
978 
979 /// Annotate the IR with the result of the analysis. For testing/debugging only.
980 static void
982  const OneShotAnalysisState &state) {
983  // Add __inplace_operands_attr__.
984  op->walk([&](Operation *op) {
985  for (OpOperand &opOperand : op->getOpOperands())
986  if (isa<TensorType>(opOperand.get().getType()))
987  setInPlaceOpOperand(opOperand, state.isInPlace(opOperand));
988  });
989 }
990 
992  const OneShotAnalysisState &state) {
993  AsmState asmState(op);
994  Builder b(op->getContext());
995  op->walk([&](Operation *op) {
996  SmallVector<Attribute> aliasSets;
997  for (OpResult opResult : op->getOpResults()) {
998  if (llvm::isa<TensorType>(opResult.getType())) {
999  SmallVector<Attribute> aliases;
1000  state.applyOnAliases(opResult, [&](Value alias) {
1001  std::string buffer;
1002  llvm::raw_string_ostream stream(buffer);
1003  alias.printAsOperand(stream, asmState);
1004  aliases.push_back(b.getStringAttr(stream.str()));
1005  });
1006  aliasSets.push_back(b.getArrayAttr(aliases));
1007  }
1008  }
1009  if (!aliasSets.empty())
1010  op->setAttr(kAliasSetAttrName, b.getArrayAttr(aliasSets));
1011  });
1012 }
1013 
1014 /// Assert that every allocation can be deallocated in the same block. I.e.,
1015 /// every value that is returned or yielded from a block is:
1016 /// * guaranteed to be aliasing a bbArg of that block or a parent block, or
1017 /// * guaranteed to be aliasing an OpResult of a op in a parent block.
1018 ///
1019 /// In that case, buffer deallocation is simple: Every allocated buffer can be
1020 /// deallocated in the same block. Otherwise, the buffer deallocation pass must
1021 /// be run.
1022 ///
1023 /// Note: The current implementation checks for equivalent values instead of
1024 /// aliasing values, which is stricter than needed. We can currently not check
1025 /// for aliasing values because the analysis is a maybe-alias analysis and we
1026 /// need a must-alias analysis here.
1027 ///
1028 /// Example:
1029 /// ```
1030 /// %0 = "some_op" : tensor<?xf32>
1031 /// %1 = scf.if %c -> (tensor<?xf32>) {
1032 /// scf.yield %0 : tensor<?xf32>
1033 /// } else {
1034 /// %t = linalg.alloc_tensor : tensor<?xf32>
1035 /// scf.yield %t : tensor<?xf32>
1036 /// }
1037 /// ```
1038 ///
1039 /// In the above example, the second scf.yield op is problematic because the
1040 /// yielded value %t is defined in the same block as the scf.yield op and
1041 /// and bufferizes to a new allocation.
1042 // TODO: Remove buffer deallocation from One-Shot Bufferize and fix the buffer
1043 // deallocation pass.
1045  const OneShotAnalysisState &state) {
1046  LogicalResult status = success();
1047  DominanceInfo domInfo(op);
1048  op->walk([&](Operation *returnOp) {
1049  if (!isRegionReturnLike(returnOp) ||
1050  !state.getOptions().isOpAllowed(returnOp))
1051  return WalkResult::advance();
1052 
1053  for (OpOperand &returnValOperand : returnOp->getOpOperands()) {
1054  Value returnVal = returnValOperand.get();
1055  // Skip non-tensor values.
1056  if (!isa<TensorType>(returnVal.getType()))
1057  continue;
1058 
1059  bool foundEquivValue = false;
1060  state.applyOnEquivalenceClass(returnVal, [&](Value equivVal) {
1061  if (auto bbArg = dyn_cast<BlockArgument>(equivVal)) {
1062  Operation *definingOp = bbArg.getOwner()->getParentOp();
1063  if (definingOp->isProperAncestor(returnOp))
1064  foundEquivValue = true;
1065  return;
1066  }
1067 
1068  Operation *definingOp = equivVal.getDefiningOp();
1069  if (definingOp->getBlock()->findAncestorOpInBlock(
1070  *returnOp->getParentOp()))
1071  // Skip ops that happen after `returnOp` and parent ops.
1072  if (happensBefore(definingOp, returnOp, domInfo))
1073  foundEquivValue = true;
1074  });
1075 
1076  // Note: Returning/yielding buffer allocations is allowed only if
1077  // `allowReturnAllocs` is set.
1078  if (!foundEquivValue)
1079  status = returnOp->emitError()
1080  << "operand #" << returnValOperand.getOperandNumber()
1081  << " may return/yield a new buffer allocation";
1082  }
1083 
1084  return WalkResult::advance();
1085  });
1086 
1087  return status;
1088 }
1089 
1091  OneShotAnalysisState &state,
1092  BufferizationStatistics *statistics) {
1093  DominanceInfo domInfo(op);
1095 
1096  if (failed(checkAliasInfoConsistency(op, domInfo, state)))
1097  return failure();
1098 
1099  // If the analysis fails, just return.
1100  if (failed(state.analyzeOp(op, domInfo)))
1101  return failure();
1102 
1103  if (statistics) {
1104  statistics->numTensorInPlace = state.getStatNumTensorInPlace();
1105  statistics->numTensorOutOfPlace = state.getStatNumTensorOutOfPlace();
1106  }
1107 
1108  bool failedAnalysis = false;
1109  if (!options.allowReturnAllocs)
1110  failedAnalysis |= failed(assertNoAllocsReturned(op, state));
1111 
1112  // Gather some extra analysis data.
1113  state.gatherYieldedTensors(op);
1114  state.gatherUndefinedTensorUses(op);
1115 
1116  // Analysis verification: After setting up alias/equivalence sets, each op
1117  // can check for expected invariants/limitations and fail the analysis if
1118  // necessary.
1119  op->walk([&](Operation *op) {
1120  if (BufferizableOpInterface bufferizableOp =
1121  options.dynCastBufferizableOp(op))
1122  failedAnalysis |= failed(bufferizableOp.verifyAnalysis(state));
1123  });
1124 
1125  // Annotate operations if we only want to report the analysis.
1126  if (options.testAnalysisOnly)
1128  if (options.dumpAliasSets)
1129  annotateOpsWithAliasSets(op, state);
1130 
1131  return success(!failedAnalysis);
1132 }
1133 
1137  BufferizationStatistics *statistics) {
1138  assert(!(options.copyBeforeWrite && options.testAnalysisOnly) &&
1139  "invalid combination of bufferization flags");
1140  if (!options.copyBeforeWrite) {
1141  // If a buffer is copied before every write, no analysis is needed.
1142  if (failed(insertTensorCopies(op, options, statistics)))
1143  return failure();
1144  }
1145  if (options.testAnalysisOnly)
1146  return success();
1147  return bufferizeOp(op, options, /*copyBeforeWrite=*/options.copyBeforeWrite,
1148  /*opFilter=*/nullptr, statistics);
1149 }
static bool hasReadAfterWriteInterference(const DenseSet< OpOperand * > &usesRead, const DenseSet< OpOperand * > &usesWrite, const DominanceInfo &domInfo, OneShotAnalysisState &state)
Given sets of uses and writes, return true if there is a RaW conflict under the assumption that all g...
static void getAliasingReads(DenseSet< OpOperand * > &res, Value root, const OneShotAnalysisState &state)
static void equivalenceAnalysis(SmallVector< Operation * > &ops, OneShotAnalysisState &state)
Analyze equivalence of tied OpResult/OpOperand pairs of the given ops.
static void setInPlaceOpOperand(OpOperand &opOperand, bool inPlace)
Mark whether OpOperand will be bufferized inplace.
constexpr StringLiteral kInPlaceOperandsAttrName
Attribute marker to specify op operands that bufferize in-place.
static bool isaTensor(Type t)
static bool hasTensorSemantics(Operation *op)
Return true if the given op has a tensor result or a tensor operand.
static void annotateNonWritableTensor(Value value)
Annotate IR with details about the detected non-writability conflict.
constexpr StringLiteral kAliasSetAttrName
static LogicalResult checkAliasInfoConsistency(Operation *op, const DominanceInfo &domInfo, OneShotAnalysisState &state)
Assert that the current bufferization decisions are consistent.
static LogicalResult bufferizableInPlaceAnalysisImpl(OpOperand &operand, OneShotAnalysisState &state, const DominanceInfo &domInfo)
Determine if operand can be bufferized in-place.
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 ...
static bool wouldCreateWriteToNonWritableBuffer(OpOperand &operand, OneShotAnalysisState &state, bool checkConsistencyOnly=false)
Return true if bufferizing operand inplace would create a write to a non-writable buffer.
static void annotateOpsWithAliasSets(Operation *op, const OneShotAnalysisState &state)
static void annotateOpsWithBufferizationMarkers(Operation *op, const OneShotAnalysisState &state)
Annotate the IR with the result of the analysis. For testing/debugging only.
static bool wouldCreateReadAfterWriteInterference(OpOperand &operand, const DominanceInfo &domInfo, OneShotAnalysisState &state, bool checkConsistencyOnly=false)
Return true if bufferizing operand inplace would create a conflict.
bool canUseOpDominance(OpOperand *uRead, OpOperand *uWrite, const SetVector< Value > &definitions, const AnalysisState &state)
Return true if op dominance can be used to rule out a read-after-write conflicts based on the orderin...
static void getAliasingInplaceWrites(DenseSet< OpOperand * > &res, Value root, const OneShotAnalysisState &state)
static LogicalResult assertNoAllocsReturned(Operation *op, const OneShotAnalysisState &state)
Assert that every allocation can be deallocated in the same block.
static void annotateConflict(OpOperand *uRead, OpOperand *uConflictingWrite, Value definition)
Annotate IR with details about the detected RaW conflict.
static bool isInplaceMemoryWrite(OpOperand &opOperand, const OneShotAnalysisState &state)
Return true if opOperand has been decided to bufferize in-place.
static llvm::ManagedStatic< PassManagerOptions > options
#define MLIR_DEFINE_EXPLICIT_TYPE_ID(CLASS_NAME)
Definition: TypeID.h:263
Base class for generic analysis states.
This class provides management for the lifetime of the state used when printing the IR.
Definition: AsmState.h:525
Block represents an ordered list of Operations.
Definition: Block.h:30
Operation * findAncestorOpInBlock(Operation &op)
Returns 'op' if 'op' lies in this block, or otherwise finds the ancestor operation of 'op' that lies ...
Definition: Block.cpp:62
This class is a general helper class for creating context-global objects like types,...
Definition: Builders.h:50
UnitAttr getUnitAttr()
Definition: Builders.cpp:112
ArrayAttr getArrayAttr(ArrayRef< Attribute > value)
Definition: Builders.cpp:260
A class for computing basic dominance information.
Definition: Dominance.h:121
bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const
Return true if operation A properly dominates operation B, i.e.
Definition: Dominance.h:134
IRValueT get() const
Return the current value being used by this operand.
Definition: UseDefLists.h:152
This class helps build Operations.
Definition: Builders.h:202
This class represents an operand of an operation.
Definition: Value.h:261
unsigned getOperandNumber()
Return which operand this is in the OpOperand list of the Operation.
Definition: Value.cpp:217
This is a value defined by a result of an operation.
Definition: Value.h:448
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
Attribute getAttr(StringAttr name)
Return the specified attribute if present, null otherwise.
Definition: Operation.h:495
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:738
MLIRContext * getContext()
Return the context this operation is associated with.
Definition: Operation.h:216
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
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
Definition: Operation.cpp:266
void setAttr(StringAttr name, Attribute value)
If the an attribute exists with the specified name, change it to the new value.
Definition: Operation.h:543
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:638
operand_type_range getOperandTypes()
Definition: Operation.h:392
MutableArrayRef< OpOperand > getOpOperands()
Definition: Operation.h:378
result_type_range getResultTypes()
Definition: Operation.h:423
bool isAncestor(Operation *other)
Return true if this operation is an ancestor of the other operation.
Definition: Operation.h:263
result_range getOpResults()
Definition: Operation.h:415
result_range getResults()
Definition: Operation.h:410
bool isProperAncestor(Operation *other)
Return true if this operation is a proper ancestor of the other operation.
Definition: Operation.cpp:217
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
Operation * getParentOp()
Return the parent operation this region is attached to.
Definition: Region.h:200
This class provides an efficient unique identifier for a specific C++ type.
Definition: TypeID.h:104
Instances of the Type class are uniqued, have an immutable identifier and an optional mutable compone...
Definition: Types.h:74
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:93
MLIRContext * getContext() const
Utility to get the associated MLIRContext that this value is defined in.
Definition: Value.h:125
Type getType() const
Return the type of this value.
Definition: Value.h:122
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Definition: Value.h:206
A utility result that is used to signal how to proceed with an ongoing walk:
Definition: Visitors.h:34
static WalkResult skip()
Definition: Visitors.h:53
static WalkResult advance()
Definition: Visitors.h:52
AnalysisState provides a variety of helper functions for dealing with tensor values.
AliasingOpOperandList getAliasingOpOperands(OpResult result) const
Determine which OpOperand* will alias with result if the op is bufferized in place.
bool bufferizesToMemoryWrite(OpOperand &opOperand) const
Return true if opOperand bufferizes to a memory write.
AliasingOpResultList getAliasingOpResults(OpOperand &opOperand) const
Determine which OpResult will alias with opOperand if the op is bufferized in place.
SetVector< Value > findDefinitions(Value value) const
Find the values that may define the contents of the given value at runtime.
State for analysis-enabled bufferization.
void bufferizeOutOfPlace(OpOperand &operand)
Mark the given OpOperand as out-of-place.
bool isWritable(Value value) const
Return true if the buffer of the given tensor value is writable.
const SetVector< Value > & findDefinitionsCached(Value value)
Find the definitions of the given tensor value or retrieve them from the cache.
bool isInPlace(OpOperand &opOperand) const override
Return true if the given OpResult has been decided to bufferize inplace.
LogicalResult analyzeOp(Operation *op, const DominanceInfo &domInfo)
Analyze the given op and its nested ops.
const OneShotBufferizationOptions & getOptions() const
Return a reference to the BufferizationOptions.
void unionEquivalenceClasses(Value v1, Value v2)
Union the equivalence classes of v1 and v2.
void gatherUndefinedTensorUses(Operation *op)
Find all tensor values in the given operation that have undefined contents and store them in undefine...
LogicalResult analyzeSingleOp(Operation *op, const DominanceInfo &domInfo)
Analyze a single op (without nested ops).
void gatherYieldedTensors(Operation *op)
Find all tensors that are yielded/returned from a block and store them in yieldedTensors.
void applyOnEquivalenceClass(Value v, function_ref< void(Value)> fun) const
Apply fun to all the members of the equivalence class of v.
void resetCache()
Reset cached data structures.
void bufferizeInPlace(OpOperand &operand)
Mark the given OpOperand as in-place and merge the results' and operand's aliasing sets.
void applyOnAliases(Value v, function_ref< void(Value)> fun) const
Apply fun to all aliases of v.
bool areEquivalentBufferizedValues(Value v1, Value v2) const override
Return true if v1 and v2 bufferize to equivalent buffers.
OneShotAnalysisState(Operation *op, const OneShotBufferizationOptions &options)
bool areAliasingBufferizedValues(Value v1, Value v2) const override
Return true if v1 and v2 may bufferize to aliasing buffers.
void createAliasInfoEntry(Value v)
Add a new entry for v in the aliasInfo and equivalentInfo.
Operation * getOwner() const
Return the owner of this operand.
Definition: UseDefLists.h:40
LogicalResult runOneShotBufferize(Operation *op, const OneShotBufferizationOptions &options, BufferizationStatistics *statistics=nullptr)
Run One-Shot Bufferize on the given op: Analysis + Bufferization.
LogicalResult analyzeOp(Operation *op, OneShotAnalysisState &state, BufferizationStatistics *statistics=nullptr)
Analyze op and its nested ops.
LogicalResult bufferizeOp(Operation *op, const BufferizationOptions &options, bool copyBeforeWrite=true, const OpFilter *opFilter=nullptr, BufferizationStatistics *statistics=nullptr)
Bufferize op and its nested ops that implement BufferizableOpInterface.
Definition: Bufferize.cpp:428
LogicalResult insertTensorCopies(Operation *op, const OneShotBufferizationOptions &options, BufferizationStatistics *statistics=nullptr)
Resolve RaW and other conflicts by inserting bufferization.alloc_tensor ops.
Region * getNextEnclosingRepetitiveRegion(Region *region, const BufferizationOptions &options)
Assuming that the given region is repetitive, find the next enclosing repetitive region.
This header declares functions that assit transformations in the MemRef dialect.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
bool insideMutuallyExclusiveRegions(Operation *a, Operation *b)
Return true if a and b are in mutually exclusive regions as per RegionBranchOpInterface.
Region * getEnclosingRepetitiveRegion(Operation *op)
Return the first enclosing region of the given op that may be executed repetitively as per RegionBran...
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
bool isRegionReturnLike(Operation *operation)
Returns true if the given operation is either annotated with the ReturnLike trait or implements the R...
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
Options for BufferizableOpInterface-based bufferization.
BufferizableOpInterface dynCastBufferizableOp(Operation *op) const
Try to cast the given op to BufferizableOpInterface if the op is allow listed.
bool printConflicts
If set to true, the IR is annotated with details about RaW conflicts.
bool isOpAllowed(Operation *op) const
Return true if the given op should be bufferized.
Bufferization statistics for debugging.
Definition: Bufferize.h:34
Options for analysis-enabled bufferization.
AnalysisHeuristic analysisHeuristic
The heuristic controls the order in which ops are traversed during the analysis.