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_buffer 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
41#include "mlir/Dialect/Bufferization/Transforms/OneShotAnalysis.h"
42
43#include <random>
44#include <tuple>
45
46#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
47#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
48#include "mlir/Dialect/Bufferization/Transforms/Bufferize.h"
49#include "mlir/Dialect/Bufferization/Transforms/Transforms.h"
50#include "mlir/Dialect/MemRef/IR/MemRef.h"
51#include "mlir/IR/AsmState.h"
52#include "mlir/IR/Dominance.h"
53#include "mlir/IR/Iterators.h"
54#include "mlir/IR/Operation.h"
55#include "mlir/IR/TypeUtilities.h"
56#include "mlir/Interfaces/ControlFlowInterfaces.h"
57#include "mlir/Interfaces/SubsetOpInterface.h"
58#include "llvm/ADT/DenseMap.h"
59#include "llvm/ADT/DenseSet.h"
60#include "llvm/ADT/STLExtras.h"
61#include "llvm/ADT/SetVector.h"
62#include "llvm/ADT/SmallPtrSet.h"
63#include "llvm/ADT/SmallVector.h"
64#include "llvm/Support/DebugLog.h"
65
66MLIR_DEFINE_EXPLICIT_TYPE_ID(mlir::bufferization::OneShotAnalysisState)
67
68// Run mlir-opt with `-debug-only="one-shot-analysis"` for detailed debug
69// output.
70#define DEBUG_TYPE "one-shot-analysis"
71
72using namespace mlir;
73using namespace mlir::bufferization;
74
75static bool isaTensor(Type t) { return isa<TensorLikeType>(Val: t); }
76
77//===----------------------------------------------------------------------===//
78// Bufferization-specific attribute manipulation.
79// These are for testing and debugging only. Bufferization information is stored
80// in OneShotBufferizationState. When run with `testAnalysisOnly`, the IR is
81// annotated with the results of the analysis, so that they can be checked in
82// tests.
83//===----------------------------------------------------------------------===//
84
85/// Attribute marker to specify op operands that bufferize in-place.
86constexpr StringLiteral kInPlaceOperandsAttrName = "__inplace_operands_attr__";
87
88constexpr StringLiteral kOpResultAliasSetAttrName =
89 "__opresult_alias_set_attr__";
90
91constexpr StringLiteral kBbArgAliasSetAttrName = "__bbarg_alias_set_attr__";
92
93/// Mark whether OpOperand will be bufferized inplace.
94static void setInPlaceOpOperand(OpOperand &opOperand, bool inPlace) {
95 Operation *op = opOperand.getOwner();
96 SmallVector<StringRef> inPlaceVector;
97 if (auto attr = op->getDiscardableAttr(name: kInPlaceOperandsAttrName)) {
98 inPlaceVector = SmallVector<StringRef>(llvm::to_vector<4>(
99 Range: cast<ArrayAttr>(Val&: attr).getAsValueRange<StringAttr>()));
100 // The existing attribute may have fewer entries than the current operand
101 // count (e.g., when user-provided annotations are inconsistent with the
102 // op's actual operand count). Resize to avoid an out-of-bounds access.
103 if (inPlaceVector.size() < op->getNumOperands())
104 inPlaceVector.resize(N: op->getNumOperands(), NV: "none");
105 } else {
106 inPlaceVector = SmallVector<StringRef>(op->getNumOperands(), "none");
107 for (OpOperand &opOperand : op->getOpOperands())
108 if (isa<TensorLikeType>(Val: opOperand.get().getType()))
109 inPlaceVector[opOperand.getOperandNumber()] = "false";
110 }
111 inPlaceVector[opOperand.getOperandNumber()] = inPlace ? "true" : "false";
112 op->setDiscardableAttr(name: kInPlaceOperandsAttrName,
113 value: OpBuilder(op).getStrArrayAttr(values: inPlaceVector));
114}
115
116//===----------------------------------------------------------------------===//
117// OneShotAnalysisState
118//===----------------------------------------------------------------------===//
119
120/// A region with more than one block is unstructured control flow. Single-block
121/// regions, including structured loops, are not.
122static bool detectUnstructuredControlFlow(Operation *op) {
123 WalkResult walkRes = op->walk(callback: [&](Operation *nested) {
124 for (Region &region : nested->getRegions()) {
125 if (region.getBlocks().size() > 1) {
126 return WalkResult::interrupt();
127 }
128 }
129 return WalkResult::advance();
130 });
131 return walkRes.wasInterrupted();
132}
133
134/// Return "true" if any allowed op has a parallel region.
135static bool detectParallelRegions(Operation *op,
136 const BufferizationOptions &options) {
137 WalkResult walkRes =
138 op->walk(callback: [&](BufferizableOpInterface bufferizableOp) -> WalkResult {
139 if (!options.isOpAllowed(op: bufferizableOp))
140 return WalkResult::skip();
141 for (Region &region : bufferizableOp->getRegions()) {
142 if (bufferizableOp.isParallelRegion(index: region.getRegionNumber()))
143 return WalkResult::interrupt();
144 }
145 return WalkResult::advance();
146 });
147 return walkRes.wasInterrupted();
148}
149
150OneShotAnalysisState::OneShotAnalysisState(
151 Operation *op, const OneShotBufferizationOptions &options)
152 : AnalysisState(options, TypeID::get<OneShotAnalysisState>()) {
153 mayHaveUnstructuredCF = options.mayHaveUnstructuredControlFlow.value_or(
154 u: detectUnstructuredControlFlow(op));
155 if (!options.mayHaveParallelRegions.has_value()) {
156 mayHaveParallelRegionsFlag = detectParallelRegions(op, options);
157 } else {
158 mayHaveParallelRegionsFlag = *options.mayHaveParallelRegions;
159 }
160
161 // Set up alias sets.
162 op->walk(callback: [&](Operation *op) {
163 for (Value v : op->getResults())
164 if (isa<TensorLikeType>(Val: v.getType()))
165 createAliasInfoEntry(v);
166 for (Region &r : op->getRegions())
167 for (Block &b : r.getBlocks())
168 for (auto bbArg : b.getArguments())
169 if (isa<TensorLikeType>(Val: bbArg.getType()))
170 createAliasInfoEntry(v: bbArg);
171 });
172
173 // Mark OpOperands in-place that must bufferize in-place.
174 op->walk(callback: [&](BufferizableOpInterface bufferizableOp) {
175 if (!options.isOpAllowed(op: bufferizableOp))
176 return WalkResult::skip();
177
178 for (OpOperand &opOperand : bufferizableOp->getOpOperands())
179 if (isa<TensorLikeType>(Val: opOperand.get().getType()))
180 if (bufferizableOp.mustBufferizeInPlace(opOperand, state: *this))
181 bufferizeInPlace(operand&: opOperand);
182 return WalkResult::advance();
183 });
184}
185
186void OneShotAnalysisState::applyOnEquivalenceClass(
187 Value v, function_ref<void(Value)> fun) const {
188 auto leaderIt = equivalentInfo.findLeader(V: v);
189 for (auto mit = leaderIt, meit = equivalentInfo.member_end(); mit != meit;
190 ++mit) {
191 fun(*mit);
192 }
193}
194
195void OneShotAnalysisState::applyOnAliases(Value v,
196 function_ref<void(Value)> fun) const {
197 auto leaderIt = aliasInfo.findLeader(V: v);
198 for (auto mit = leaderIt, meit = aliasInfo.member_end(); mit != meit; ++mit) {
199 fun(*mit);
200 }
201}
202
203bool OneShotAnalysisState::areEquivalentBufferizedValues(Value v1,
204 Value v2) const {
205 return equivalentInfo.isEquivalent(V1: v1, V2: v2);
206}
207
208bool OneShotAnalysisState::areAliasingBufferizedValues(Value v1,
209 Value v2) const {
210 return aliasInfo.isEquivalent(V1: v1, V2: v2);
211}
212
213void OneShotAnalysisState::bufferizeInPlace(OpOperand &operand) {
214 if (inplaceBufferized.contains(V: &operand))
215 return;
216 inplaceBufferized.insert(V: &operand);
217 for (AliasingValue alias : getAliasingValues(opOperand&: operand))
218 aliasInfo.unionSets(V1: alias.value, V2: operand.get());
219 ++statNumTensorInPlace;
220}
221
222void OneShotAnalysisState::bufferizeOutOfPlace(OpOperand &operand) {
223 assert(!inplaceBufferized.contains(&operand) &&
224 "OpOperand was already decided to bufferize inplace");
225 ++statNumTensorOutOfPlace;
226}
227
228void OneShotAnalysisState::createAliasInfoEntry(Value v) {
229 aliasInfo.insert(Data: v);
230 equivalentInfo.insert(Data: v);
231}
232
233void OneShotAnalysisState::gatherUndefinedTensorUses(Operation *op) {
234 op->walk(callback: [&](Operation *op) {
235 // Skip unknown ops.
236 auto bufferizableOp = getOptions().dynCastBufferizableOp(op);
237 if (!bufferizableOp)
238 return WalkResult::skip();
239
240 // Check all tensor OpResults.
241 for (OpResult opResult : op->getOpResults()) {
242 if (!isa<TensorLikeType>(Val: opResult.getType()))
243 continue;
244
245 // If there is no preceding definition, the tensor contents are
246 // undefined.
247 if (opResult.getUses().empty())
248 continue;
249 // It does not really matter which use to take to search about
250 // the value's definitions.
251 OpOperand *opOperand = &(*opResult.getUses().begin());
252 if (findDefinitionsCached(opOperand).empty())
253 for (OpOperand &use : opResult.getUses())
254 undefinedTensorUses.insert(V: &use);
255 }
256
257 return WalkResult::advance();
258 });
259}
260
261bool OneShotAnalysisState::hasUndefinedContents(OpOperand *opOperand) const {
262 return undefinedTensorUses.contains(V: opOperand);
263}
264
265bool OneShotAnalysisState::isInPlace(OpOperand &opOperand) const {
266 return inplaceBufferized.contains(V: &opOperand);
267}
268
269bool OneShotAnalysisState::isValueWritten(Value value) const {
270 bool isWritten = false;
271 applyOnAliases(v: value, fun: [&](Value val) {
272 for (OpOperand &use : val.getUses())
273 if (isInPlace(opOperand&: use) && bufferizesToMemoryWrite(opOperand&: use))
274 isWritten = true;
275 });
276 return isWritten;
277}
278
279bool OneShotAnalysisState::isWritable(Value value) const {
280 // TODO: Out-of-place bufferized value could be considered writable.
281 // Query BufferizableOpInterface to see if the BlockArgument is writable.
282 if (auto bufferizableOp =
283 getOptions().dynCastBufferizableOp(op: getOwnerOfValue(value)))
284 return bufferizableOp.isWritable(value, state: *this);
285
286 // Not a bufferizable op: The conservative answer is "not writable".
287 return false;
288}
289
290void OneShotAnalysisState::unionAliasSets(Value v1, Value v2) {
291 aliasInfo.unionSets(V1: v1, V2: v2);
292}
293
294void OneShotAnalysisState::unionEquivalenceClasses(Value v1, Value v2) {
295 equivalentInfo.unionSets(V1: v1, V2: v2);
296}
297
298OneShotAnalysisState::Extension::~Extension() = default;
299
300//===----------------------------------------------------------------------===//
301// Bufferization-specific alias analysis.
302//===----------------------------------------------------------------------===//
303
304/// Return true if opOperand has been decided to bufferize in-place.
305static bool isInplaceMemoryWrite(OpOperand &opOperand,
306 const OneShotAnalysisState &state) {
307 // OpOperands that do not bufferize to a memory write do not write in-place.
308 if (!state.bufferizesToMemoryWrite(opOperand))
309 return false;
310 // Check current bufferization decisions.
311 return state.isInPlace(opOperand);
312}
313
314/// Cached CFG reachability to avoid repeated linear BFS traversals from
315/// `Block->isReachable`.
316class OneShotAnalysisState::CFGReachabilityCache {
317public:
318 bool isReachable(Block *from, Block *to,
319 const SmallPtrSetImpl<Block *> *barriers = nullptr) {
320 assert(from->getParent() == to->getParent() && "expected same region");
321
322 SmallPtrSet<Block *, 16> except;
323 BarrierKey sortedBarriers;
324 if (barriers && !barriers->empty()) {
325 except.insert(I: barriers->begin(), E: barriers->end());
326 sortedBarriers.append(in_start: barriers->begin(), in_end: barriers->end());
327 llvm::sort(C&: sortedBarriers);
328 }
329
330 ReachableByBarriers &inner = cached[from];
331 if (auto it = inner.find(Val: sortedBarriers); it != inner.end())
332 return it->second.contains(Ptr: to);
333
334 // Same traversal as `Block::isReachable`: `except` is both the barrier set
335 // and the visited set.
336 ReachableSet reachable;
337 SmallVector<Block *> worklist(from->succ_begin(), from->succ_end());
338 while (!worklist.empty()) {
339 Block *next = worklist.pop_back_val();
340 if (!except.insert(Ptr: next).second)
341 continue;
342 reachable.insert(Ptr: next);
343 worklist.append(in_start: next->succ_begin(), in_end: next->succ_end());
344 }
345 bool result = reachable.contains(Ptr: to);
346 inner.try_emplace(Key: std::move(sortedBarriers), Args: std::move(reachable));
347 return result;
348 }
349
350 void clear() { cached.clear(); }
351
352private:
353 using ReachableSet = SmallPtrSet<Block *, 16>;
354 /// Sorted extra-barrier blocks for one query. Empty means no extra barriers.
355 using BarrierKey = SmallVector<Block *, 8>;
356 /// Sorted barrier list -> blocks reachable from `from` without crossing those
357 /// barriers.
358 using ReachableByBarriers = DenseMap<BarrierKey, ReachableSet>;
359 /// `from` block -> reachable-set keyed by sorted extra-barrier blocks.
360 DenseMap<Block *, ReachableByBarriers> cached;
361};
362
363/// `canUseOpDominanceDueToBlocks` walks enclosing regions and queries CFG
364/// reachability, but the answer is a property of blocks: every op in a block
365/// has the same parent chain, and a definition contributes only its block as
366/// a reachability barrier. One entry per (read block, write block, def blocks)
367/// therefore covers every operand pair in those blocks.
368class OneShotAnalysisState::OpDominanceBlockCache {
369public:
370 bool getOrCompute(Block *readBlock, Block *writeBlock,
371 ArrayRef<Block *> sortedDefBlocks,
372 function_ref<bool()> compute) {
373 if (sortedDefBlocks.size() == 1) {
374 auto key =
375 std::make_tuple(args&: readBlock, args&: writeBlock, args: sortedDefBlocks.front());
376 if (auto it = singleDef.find(Val: key); it != singleDef.end())
377 return it->second;
378 bool result = compute();
379 singleDef.try_emplace(Key: key, Args&: result);
380 return result;
381 }
382
383 DefKey key(sortedDefBlocks.begin(), sortedDefBlocks.end());
384 auto &byDefs = manyDefs[std::make_pair(x&: readBlock, y&: writeBlock)];
385 if (auto it = byDefs.find(Val: key); it != byDefs.end())
386 return it->second;
387 bool result = compute();
388 byDefs.try_emplace(Key: std::move(key), Args&: result);
389 return result;
390 }
391
392 void clear() {
393 singleDef.clear();
394 manyDefs.clear();
395 }
396
397private:
398 using DefKey = SmallVector<Block *, 4>;
399 /// Common case: a single definition block.
400 DenseMap<std::tuple<Block *, Block *, Block *>, bool> singleDef;
401 /// Sorted unique definition blocks, for reads with several definitions.
402 DenseMap<std::pair<Block *, Block *>, DenseMap<DefKey, bool>> manyDefs;
403};
404
405OneShotAnalysisState::~OneShotAnalysisState() = default;
406
407/// Return true if `a` cannot happen after `b`.
408/// True if `a` properly dominates `b` and `b` is not inside `a`, or if they
409/// are in the same region with no CFG path from `b` to `a`.
410/// Dominance is sufficient but not necessary. E.g.:
411///
412/// ^bb0:
413/// cf.cond_br %c, ^bb1, ^bb2
414/// ^bb1:
415/// "op_a"(%t)
416/// cf.br ^bb3
417/// ^bb2:
418/// "op_b"(%t)
419/// cf.br ^bb3
420/// ^bb3:
421///
422/// `op_a` does not dominate `op_b`, but there is no CFG path from `op_b` to
423/// `op_a`, so `op_a` cannot happen after `op_b`.
424///
425/// `extraBarriers` are extra blocks a CFG path from `b` to `a` must not cross.
426static bool cannotHappenAfter(Operation *a, Operation *b,
427 const DominanceInfo &domInfo,
428 OneShotAnalysisState &state,
429 SmallPtrSet<Block *, 16> extraBarriers = {}) {
430 do {
431 // TODO: Instead of isProperAncestor + properlyDominates, we should use
432 // properlyDominatesImpl(a, b, /*enclosingOpOk=*/false)
433 if (a->isProperAncestor(other: b))
434 return false;
435 // Dominance is a stronger condition than reachability. Prefer using it
436 // since it is cached and works within a single block.
437 if (domInfo.properlyDominates(a, b))
438 return true;
439 // Distinct blocks in the same region only exist with unstructured control
440 // flow. Dominance is a complete ordering otherwise.
441 if (state.mayHaveUnstructuredControlFlow()) {
442 Block *aBlock = a->getBlock();
443 Block *bBlock = b->getBlock();
444 if (aBlock != bBlock && aBlock->getParent() == bBlock->getParent() &&
445 !state.isReachableCached(from: bBlock, to: aBlock, barriers: &extraBarriers))
446 return true;
447 }
448 } while ((a = a->getParentOp()));
449 return false;
450}
451
452/// Return `true` if op dominance can be used to rule out a read-after-write
453/// conflicts based on the ordering of ops. Returns `false` if op dominance
454/// cannot be used to due region-based loops.
455///
456/// Generalized op dominance can often be used to rule out potential conflicts
457/// due to "read happens before write". E.g., the following IR is not a RaW
458/// conflict because the read happens *before* the write.
459///
460/// Example 1:
461/// %0 = ... : tensor<?xf32> // DEF
462/// "reading_op"(%0) : tensor<?xf32> // READ
463/// %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32> // WRITE
464///
465/// This is no longer true inside loops (or repetitive regions). In such cases,
466/// there may not be a meaningful `cannotHappenAfter` relationship because ops
467/// could be executed multiple times. E.g.:
468///
469/// Example 2:
470/// %0 = ... : tensor<?xf32> // DEF
471/// scf.for ... {
472/// "reading_op"(%0) : tensor<?xf32> // READ
473/// %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32> // WRITE
474/// ...
475/// }
476///
477/// In the above example, reading_op happens before writing_op according to
478/// op dominance. However, both ops may happen multiple times; in
479/// particular, the second execution of reading_op happens after the first
480/// execution of writing_op. This is problematic because the tensor %0 they
481/// operate on (i.e., the "definition") is defined outside of the loop.
482///
483/// On a high-level, there is a potential RaW in a program if there exists a
484/// possible program execution such that there is a sequence of DEF, followed
485/// by WRITE, followed by READ. Each additional DEF resets the sequence.
486///
487/// E.g.:
488/// No conflict: DEF, WRITE, DEF, READ
489/// Potential conflict: DEF, READ, WRITE, READ, WRITE
490///
491/// Example 1 has no conflict: DEF, READ, WRITE
492/// Example 2 has a potential conflict: DEF, (READ, WRITE)*
493//
494/// Example 3:
495/// scf.for ... {
496/// %0 = ... : tensor<?xf32>
497/// "reading_op"(%0) : tensor<?xf32>
498/// %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32>
499/// ...
500/// }
501/// This has no conflict: (DEF, READ, WRITE)*
502///
503/// Example 4:
504/// %0 = ... : tensor<?xf32>
505/// scf.for ... {
506/// scf.for ... { "reading_op"(%0) }
507/// %1 = "writing_op"(%0)
508/// }
509/// This has a potential conflict: DEF, ((READ)*, WRITE)*
510///
511/// Example 5:
512/// %0 = ... : tensor<?xf32>
513/// scf.for ... { %1 = "writing_op"(%0) }
514/// scf.for ... { "reading_op"(%0) }
515/// This has a potential conflict: DEF, WRITE*, READ*
516///
517/// The following rules are used to rule out RaW conflicts via ordering of ops:
518///
519/// 1. If the closest enclosing repetitive region of DEF is a proper ancestor of
520/// a repetitive region that enclosing both READ and WRITE, we cannot rule
521/// out RaW conflict due to the ordering of ops.
522/// 2. Otherwise: There are no loops that interfere with our analysis; for
523/// analysis purposes, we can assume that there are no loops/repetitive
524/// regions. I.e., we can rule out a RaW conflict if READ cannot happen after
525/// WRITE or WRITE cannot happen after DEF. (Checked in
526/// `hasReadAfterWriteInterference`.)
527///
528static bool canUseOpDominanceDueToRegions(OpOperand *uRead, OpOperand *uWrite,
529 const SetVector<Value> &definitions,
530 AnalysisState &state) {
531 const BufferizationOptions &options = state.getOptions();
532 for (Value def : definitions) {
533 Region *rRead =
534 state.getEnclosingRepetitiveRegion(op: uRead->getOwner(), options);
535 Region *rDef = state.getEnclosingRepetitiveRegion(value: def, options);
536
537 // READ and DEF are in the same repetitive region. `cannotHappenAfter` can
538 // be used to rule out RaW conflicts due to op ordering.
539 if (rRead == rDef)
540 continue;
541
542 // Find the enclosing repetitive region of READ that is closest to DEF but
543 // not the repetitive region of DEF itself.
544 while (true) {
545 Region *nextRegion = getNextEnclosingRepetitiveRegion(region: rRead, options);
546 if (nextRegion == rDef)
547 break;
548 assert(nextRegion && "expected to find another repetitive region");
549 rRead = nextRegion;
550 }
551
552 // We cannot use op dominance if WRITE is inside the same repetitive region.
553 if (rRead->getParentOp()->isAncestor(other: uWrite->getOwner()))
554 return false;
555 }
556
557 return true;
558}
559
560/// Return `true` if op dominance can be used to rule out a read-after-write
561/// conflicts based on the ordering of ops. Returns `false` if op dominance
562/// cannot be used to due block-based loops within a region.
563///
564/// Refer to the `canUseOpDominanceDueToRegions` documentation for details on
565/// how op domiance is used during RaW conflict detection.
566///
567/// On a high-level, there is a potential RaW in a program if there exists a
568/// possible program execution such that there is a sequence of DEF, followed
569/// by WRITE, followed by READ. Each additional DEF resets the sequence.
570///
571/// Op dominance cannot be used if there is a path from block(READ) to
572/// block(WRITE) and a path from block(WRITE) to block(READ). block(DEF) should
573/// not appear on that path. Walk from the uses up through enclosing regions
574/// and stop at the definition region(s): SSA dominance means a cycle that
575/// skips DEF cannot live above DEF.
576static bool
577computeCanUseOpDominanceDueToBlocks(OpOperand *uRead, OpOperand *uWrite,
578 const SetVector<Value> &definitions,
579 OneShotAnalysisState &state) {
580 // Outermost region that contains a definition. SSA dominance means a cycle
581 // that skips DEF cannot live above this.
582 assert(!definitions.empty() && "expected at least one definition");
583 Region *outermostDefRegion = nullptr;
584 for (Value def : definitions) {
585 Region *defRegion = def.getParentRegion();
586 if (!outermostDefRegion || defRegion->isAncestor(other: outermostDefRegion))
587 outermostDefRegion = defRegion;
588 }
589 assert(outermostDefRegion && "expected a definition region");
590
591 for (Operation *readOp = uRead->getOwner(); readOp != nullptr;
592 readOp = readOp->getParentOp()) {
593 Region *region = readOp->getParentRegion();
594 if (!region)
595 continue;
596
597 Operation *writeOp = region->findAncestorOpInRegion(op&: *uWrite->getOwner());
598 if (!writeOp)
599 continue;
600
601 Block *readBlock = readOp->getBlock();
602 Block *writeBlock = writeOp->getBlock();
603 for (Value def : definitions) {
604 SmallPtrSet<Block *, 16> except = {def.getParentBlock()};
605 if (state.isReachableCached(from: readBlock, to: writeBlock, barriers: &except) &&
606 state.isReachableCached(from: writeBlock, to: readBlock, barriers: &except))
607 return false;
608 }
609 if (region == outermostDefRegion)
610 break;
611 }
612 return true;
613}
614
615static bool canUseOpDominanceDueToBlocks(OpOperand *uRead, OpOperand *uWrite,
616 const SetVector<Value> &definitions,
617 OneShotAnalysisState &state) {
618 // No multi-block region means no block-based cycle for dominance to miss.
619 if (!state.mayHaveUnstructuredControlFlow())
620 return true;
621
622 assert(!definitions.empty() && "expected at least one definition");
623 Block *readBlock = uRead->getOwner()->getBlock();
624 Block *writeBlock = uWrite->getOwner()->getBlock();
625
626 SmallVector<Block *> defBlocks;
627 defBlocks.reserve(N: definitions.size());
628 for (Value def : definitions)
629 defBlocks.push_back(Elt: def.getParentBlock());
630 llvm::sort(C&: defBlocks);
631 defBlocks.erase(CS: llvm::unique(R&: defBlocks), CE: defBlocks.end());
632
633 return state.canUseOpDominanceDueToBlocksCached(
634 readBlock, writeBlock, defBlocks, compute: [&] {
635 return computeCanUseOpDominanceDueToBlocks(uRead, uWrite, definitions,
636 state);
637 });
638}
639
640static bool canUseOpDominance(OpOperand *uRead, OpOperand *uWrite,
641 const SetVector<Value> &definitions,
642 OneShotAnalysisState &state) {
643 return canUseOpDominanceDueToRegions(uRead, uWrite, definitions, state) &&
644 canUseOpDominanceDueToBlocks(uRead, uWrite, definitions, state);
645}
646
647/// Annotate IR with details about the detected RaW conflict.
648static void annotateConflict(OpOperand *uRead, OpOperand *uConflictingWrite,
649 Value definition) {
650 static uint64_t counter = 0;
651 Operation *readingOp = uRead->getOwner();
652 Operation *conflictingWritingOp = uConflictingWrite->getOwner();
653
654 OpBuilder b(conflictingWritingOp->getContext());
655 std::string id = "C_" + std::to_string(val: counter++);
656
657 std::string conflictingWriteAttr =
658 id +
659 "[CONFL-WRITE: " + std::to_string(val: uConflictingWrite->getOperandNumber()) +
660 "]";
661 conflictingWritingOp->setDiscardableAttr(name: conflictingWriteAttr,
662 value: b.getUnitAttr());
663
664 std::string readAttr =
665 id + "[READ: " + std::to_string(val: uRead->getOperandNumber()) + "]";
666 readingOp->setDiscardableAttr(name: readAttr, value: b.getUnitAttr());
667
668 if (auto opResult = dyn_cast<OpResult>(Val&: definition)) {
669 std::string defAttr =
670 id + "[DEF: result " + std::to_string(val: opResult.getResultNumber()) + "]";
671 opResult.getDefiningOp()->setDiscardableAttr(name: defAttr, value: b.getUnitAttr());
672 } else {
673 auto bbArg = cast<BlockArgument>(Val&: definition);
674 std::string defAttr =
675 id + "[DEF: bbArg " + std::to_string(val: bbArg.getArgNumber()) + "]";
676 bbArg.getOwner()->getParentOp()->setDiscardableAttr(name: defAttr,
677 value: b.getUnitAttr());
678 }
679}
680
681/// Return 'true' if a tensor that is equivalent to `other` can be found in the
682/// reverse use-def chain of `start`. Note: If an OpOperand bufferizes out of
683/// place along that use-def chain, the two tensors may not materialize as
684/// equivalent buffers (but separate allocations).
685///
686/// Note: This function also requires that the two tensors have equivalent
687/// indexing. I.e., the tensor types do not change along the use-def chain,
688/// apart from static <-> dynamic dim casts.
689static bool hasEquivalentValueInReverseUseDefChain(AnalysisState &state,
690 OpOperand *start,
691 Value other) {
692 TraversalConfig config;
693 config.followEquivalentOnly = true;
694 config.alwaysIncludeLeaves = false;
695 config.followSameTypeOrCastsOnly = true;
696 return !state
697 .findValueInReverseUseDefChain(
698 opOperand: start, condition: [&](Value v) { return v == other; }, config)
699 .empty();
700}
701
702/// Return "true" if the given operand's value is originating from a subset
703/// that is equivalent to the subset that `subsetOp` inserts into.
704static bool matchesInsertDestination(const AnalysisState &state,
705 OpOperand *opOperand,
706 SubsetInsertionOpInterface subsetOp) {
707 auto matchingSubset = [&](Value val) {
708 if (auto opResult = dyn_cast<OpResult>(Val&: val))
709 if (subsetOp.isEquivalentSubset(candidate: opResult, equivalenceFn: [&](Value v1, Value v2) {
710 return state.areEquivalentBufferizedValues(v1, v2);
711 }))
712 return true;
713 return false;
714 };
715 // There may be multiple leaves at which the reverse SSA use-def chain lookup
716 // terminates. All of them must be equivalent subsets.
717 SetVector<Value> backwardSlice =
718 state.findValueInReverseUseDefChain(opOperand, condition: matchingSubset);
719 return llvm::all_of(Range&: backwardSlice, P: matchingSubset);
720}
721
722/// Return "true" if the given "read" and potentially conflicting "write" are
723/// not conflicting due to their subset relationship. The comments in this
724/// function are expressed in terms of tensor.extract_slice/tensor.insert_slice
725/// pairs, but apply to any subset ops that implement the
726/// `SubsetInsertionOpInterface`.
727static bool areNonConflictingSubsets(OpOperand *uRead,
728 OpOperand *uConflictingWrite,
729 const AnalysisState &state) {
730 Operation *readingOp = uRead->getOwner();
731 Operation *conflictingWritingOp = uConflictingWrite->getOwner();
732
733 // Special rules for matching ExtractSliceOp/InsertSliceOp pairs. If
734 // uRead is an InsertSliceOp...
735 if (auto subsetOp = dyn_cast<SubsetInsertionOpInterface>(Val: readingOp)) {
736 // As an example, consider the following IR.
737 //
738 // %0 = tensor.extract_slice %t[%a, %b][%c, %d][1, 1] {inplace = [true] }
739 // %1 = linalg.fill %cst, %0 {inplace= [true] }
740 // %2 = tensor.insert_slice %1 into %t[%a, %b][%c, %d][1, 1]
741 // {inplace= [true] }
742
743 if (uRead == &subsetOp.getDestinationOperand() &&
744 matchesInsertDestination(state, opOperand: uConflictingWrite, subsetOp))
745 // Case 1: The main insight is that InsertSliceOp reads only part of
746 // the destination tensor. The overwritten area is not read. If
747 // uConflictingWrite writes into exactly the memory location that is
748 // being read by uRead, this is not a conflict.
749 //
750 // In the above example:
751 // uRead = OpOperand 1 (%t) of tensor.insert_slice
752 // uConflictingWrite = OpOperand 1 (%0) of linalg.fill
753 //
754 // The read of %t does not conflict with the write of the FillOp
755 // (same aliases!) because the area that the FillOp operates on is
756 // exactly the one that is *not* read via %t.
757 return true;
758
759 if (uRead == &subsetOp.getSourceOperand() &&
760 uConflictingWrite == &subsetOp.getDestinationOperand() &&
761 matchesInsertDestination(state, opOperand: uRead, subsetOp))
762 // Case 2: The read of the source tensor and the write to the dest
763 // tensor via an InsertSliceOp is not a conflict if the read is
764 // reading exactly that part of an equivalent tensor that the
765 // InsertSliceOp is writing.
766 //
767 // In the above example:
768 // uRead = OpOperand 0 (%1) of tensor.insert_slice
769 // uConflictingWrite = OpOperand 1 (%t) of tensor.insert_slice
770 return true;
771 }
772
773 // If uConflictingWrite is an InsertSliceOp...
774 if (auto subsetOp =
775 dyn_cast<SubsetInsertionOpInterface>(Val: conflictingWritingOp)) {
776 if (uConflictingWrite == &subsetOp.getDestinationOperand()) {
777 auto writtenSubset = cast<SubsetOpInterface>(Val: conflictingWritingOp);
778 auto isDisjointSubset = [&](SubsetOpInterface readSubset) {
779 return readSubset.operatesOnDisjointSubset(
780 candidate: writtenSubset, equivalenceFn: [&](Value v1, Value v2) {
781 return state.areEquivalentBufferizedValues(v1, v2);
782 });
783 };
784 auto isDisjointExtraction = [&](Value value) {
785 auto extraction = value.getDefiningOp<SubsetExtractionOpInterface>();
786 return extraction && isDisjointSubset(cast<SubsetOpInterface>(
787 Val: extraction.getOperation()));
788 };
789
790 // Example:
791 //
792 // %0 = tensor.insert_slice %s into %t[0][4][1]
793 // %1 = vector.transfer_read %t[%c4], %cst
794 //
795 // A read from a subset does not conflict with a write to a disjoint
796 // subset of an equivalent tensor. Check the operand roles explicitly
797 // because not every subset extraction bufferizes to a memory read.
798 if (auto extraction = dyn_cast<SubsetExtractionOpInterface>(Val: readingOp)) {
799 if (uRead == &extraction.getSourceOperand() &&
800 isDisjointSubset(cast<SubsetOpInterface>(Val: readingOp)))
801 return true;
802 }
803
804 // Example:
805 //
806 // %0 = tensor.insert_slice %s into %t[0][4][1]
807 // %1 = tensor.extract_slice %t[4][4][1]
808 // return %0, %1
809 //
810 // The actual read may be further down the aliasing use-def chain. E.g.,
811 // tensor.extract_slice is an alias-only op and the read is attributed to
812 // a return or another consumer of its result. Trace such reads back to
813 // their subset extractions. Every origin must be a disjoint subset; a
814 // non-subset leaf or an extraction that may overlap keeps the analysis
815 // conservative.
816 SetVector<Value> readOrigins =
817 state.findValueInReverseUseDefChain(opOperand: uRead, condition: isDisjointExtraction);
818 if (!readOrigins.empty() &&
819 llvm::all_of(Range&: readOrigins, P: isDisjointExtraction))
820 return true;
821 }
822
823 // As an example, consider the following IR.
824 //
825 // %0 = tensor.extract_slice %t[%a, %b][%c, %d][1, 1] {inplace = [true] }
826 // %1 = linalg.fill %cst, %0 {inplace= [true] }
827 // %2 = tensor.insert_slice %1 into %t[%a, %b][%c, %d][1, 1]
828 // {inplace= [true] }
829 // %3 = vector.transfer_read %1, %cst
830 //
831 // In the above example:
832 // uRead = OpOperand 0 (%1) of vector.transfer_read
833 // uConflictingWrite = OpOperand 1 (%t) of tensor.insert_slice
834 // definition = %1
835 //
836 // This is not a conflict because the InsertSliceOp overwrites the
837 // memory segment of %1 with the exact same data. (Effectively, there
838 // is no memory write here.)
839 if (uConflictingWrite == &subsetOp.getDestinationOperand() &&
840 state.areEquivalentBufferizedValues(
841 v1: uRead->get(), v2: subsetOp.getSourceOperand().get()) &&
842 matchesInsertDestination(state, opOperand: &subsetOp.getSourceOperand(), subsetOp))
843 return true;
844 }
845
846 return false;
847}
848
849/// Given sets of uses and writes, return true if there is a RaW conflict under
850/// the assumption that all given reads/writes alias the same buffer and that
851/// all given writes bufferize inplace.
852///
853/// A conflict is: According to SSA use-def chains, a read R is supposed to read
854/// the result of a definition W1. But because of bufferization decisions, R
855/// actually reads another definition W2.
856static bool
857hasReadAfterWriteInterference(const DenseSet<OpOperand *> &usesRead,
858 const DenseSet<OpOperand *> &usesWrite,
859 const DominanceInfo &domInfo,
860 OneShotAnalysisState &state) {
861 const BufferizationOptions &options = state.getOptions();
862
863 // Before going through the main RaW analysis, find cases where a buffer must
864 // be privatized due to parallelism. If the result of a write is never read,
865 // privatization is not necessary (and large parts of the IR are likely dead).
866 if (state.mayHaveParallelRegions() && !usesRead.empty()) {
867 for (OpOperand *uConflictingWrite : usesWrite) {
868 // Find the allocation point or last write (definition) of the buffer.
869 // Note: In contrast to `findDefinitions`, this also returns results of
870 // ops that do not bufferize to memory write when no other definition
871 // could be found. E.g., "bufferization.alloc_tensor" would be included,
872 // even though that op just bufferizes to an allocation but does define
873 // the contents of the buffer.
874 SetVector<Value> definitionsOrLeaves =
875 state.findValueInReverseUseDefChain(opOperand: uConflictingWrite, condition: [&](Value v) {
876 return state.bufferizesToMemoryWrite(value: v);
877 });
878 assert(!definitionsOrLeaves.empty() &&
879 "expected at least one definition or leaf");
880
881 // The writing op must bufferize out-of-place if the definition is in a
882 // different parallel region than this write.
883 Region *writeParallelRegion = getParallelRegion(
884 region: uConflictingWrite->getOwner()->getParentRegion(), options);
885 for (Value def : definitionsOrLeaves) {
886 if (getParallelRegion(region: def.getParentRegion(), options) !=
887 writeParallelRegion) {
888 LDBG() << "\n- bufferizes out-of-place due to parallel region:\n"
889 << " unConflictingWrite = operand "
890 << uConflictingWrite->getOperandNumber() << " of "
891 << OpWithFlags(uConflictingWrite->getOwner(),
892 OpPrintingFlags().skipRegions());
893 return true;
894 }
895 }
896 }
897 }
898
899 for (OpOperand *uRead : usesRead) {
900 Operation *readingOp = uRead->getOwner();
901 LDBG() << "\n- check conflict:\n"
902 << " uRead = operand " << uRead->getOperandNumber() << " of "
903 << OpWithFlags(readingOp, OpPrintingFlags().skipRegions());
904
905 // Find the definition of uRead by following the SSA use-def chain.
906 // E.g.:
907 //
908 // %0 = "writing_op"(%t) : tensor<?x32> -> tensor<?xf32>
909 // %1 = "aliasing_op"(%0) : tensor<?x32> -> tensor<?xf32>
910 // %2 = "reading_op"(%1) : : tensor<?x32> -> not_a_tensor_type
911 //
912 // In the above example, if uRead is the OpOperand of reading_op, the
913 // definition is %0. Note that operations that create an alias but do not
914 // bufferize to a memory write (such as ExtractSliceOp) are skipped.
915 const SetVector<Value> &definitions = state.findDefinitionsCached(opOperand: uRead);
916 if (definitions.empty()) {
917 // Fast path: No conflict if there are no definitions.
918 LDBG() << " no conflict: read value has no definitions";
919 continue;
920 }
921
922 // If `useDominance` is true below, then for CFG regions we know that we can
923 // rule out blocks containing DEFs of block args for the reachability check
924 // in `cannotHappenAfter`. See the conditions in
925 // `canUseOpDominanceDueToBlocks`. E.g.:
926 //
927 // ^h(%t: tensor<?xf32>): // DEF
928 // cf.cond_br %c, ^exit, ^body
929 // ^body:
930 // %w = "writing_op"(%t) // WRITE
931 // cf.br ^h(%w)
932 // ^exit:
933 // "reading_op"(%t) // READ
934 //
935 // The only CFG path from WRITE to READ is ^body -> ^h -> ^exit, so READ
936 // cannot happen after WRITE without going through the DEF in ^h, and
937 // therefore there is no conflict.
938 SmallPtrSet<Block *, 16> bbArgDefBlocks;
939 for (Value def : definitions)
940 if (isa<BlockArgument>(Val: def))
941 bbArgDefBlocks.insert(Ptr: def.getParentBlock());
942
943 // Look for conflicting memory writes. Potential conflicts are writes to an
944 // alias that have been decided to bufferize inplace.
945 for (OpOperand *uConflictingWrite : usesWrite) {
946 LDBG() << " unConflictingWrite = operand "
947 << uConflictingWrite->getOperandNumber() << " of "
948 << OpWithFlags(uConflictingWrite->getOwner(),
949 OpPrintingFlags().skipRegions());
950
951 // Check if op dominance can be used to rule out read-after-write
952 // conflicts.
953 bool useDominance =
954 canUseOpDominance(uRead, uWrite: uConflictingWrite, definitions, state);
955 LDBG() << "\n- useDominance = " << useDominance;
956
957 // Throughout this loop, check for multiple requirements that have to be
958 // met for uConflictingWrite to be an actual conflict.
959 Operation *conflictingWritingOp = uConflictingWrite->getOwner();
960
961 // Inside of repetitive regions, ops may be executed multiple times and op
962 // dominance cannot be used to rule out conflicts.
963 if (useDominance) {
964 // No conflict if the readingOp cannot happen after
965 // conflictingWritingOp, i.e., the write is not visible when reading.
966 //
967 // Note: If ops are executed multiple times (e.g., because they are
968 // inside a loop), there may be no meaningful `cannotHappenAfter`
969 // relationship.
970 if (cannotHappenAfter(a: readingOp, b: conflictingWritingOp, domInfo, state,
971 extraBarriers: bbArgDefBlocks)) {
972 LDBG() << " no conflict: read cannot happen after write";
973 continue;
974 }
975
976 // No conflict if the reading use equals the use of the conflicting
977 // write. A use cannot conflict with itself.
978 //
979 // Note: Just being the same op is not enough. It has to be the same
980 // use.
981 // Note: If the op is executed multiple times (e.g., because it is
982 // inside a loop), it may be conflicting with itself.
983 if (uConflictingWrite == uRead) {
984 LDBG() << " no conflict: read and write are same use";
985 continue;
986 }
987
988 // Ops are not conflicting if they are in mutually exclusive regions.
989 //
990 // Note: If ops are executed multiple times (e.g., because they are
991 // inside a loop), mutually exclusive regions may be executed
992 // multiple times.
993 if (state.insideMutuallyExclusiveRegions(op0: readingOp,
994 op1: conflictingWritingOp)) {
995 LDBG() << " no conflict: read and write are in "
996 "mutually exclusive regions";
997 continue;
998 }
999
1000 // Two equivalent operands of the same op are not conflicting if the op
1001 // bufferizes to element-wise access. I.e., all loads at a position
1002 // happen before all stores to the same position.
1003 if (conflictingWritingOp == readingOp) {
1004 if (auto bufferizableOp = options.dynCastBufferizableOp(op: readingOp)) {
1005 if (bufferizableOp.bufferizesToElementwiseAccess(
1006 state, opOperands: {uRead, uConflictingWrite})) {
1007 if (hasEquivalentValueInReverseUseDefChain(
1008 state, start: uRead, other: uConflictingWrite->get()) ||
1009 hasEquivalentValueInReverseUseDefChain(
1010 state, start: uConflictingWrite, other: uRead->get())) {
1011 LDBG() << " no conflict: op bufferizes to element-wise access";
1012 continue;
1013 }
1014 }
1015 }
1016 }
1017 }
1018
1019 // No conflict if the operands are non-conflicting subsets.
1020 if (state.areNonConflictingSubsetsCached(uRead, uConflictingWrite)) {
1021 LDBG() << " no conflict: non-conflicting subsets";
1022 continue;
1023 }
1024
1025 // No conflict if the op interface says so.
1026 if (auto bufferizableOp = options.dynCastBufferizableOp(op: readingOp)) {
1027 if (bufferizableOp.isNotConflicting(uRead, uWrite: uConflictingWrite, state)) {
1028 LDBG() << " no conflict: op interace of reading op says 'no'";
1029 continue;
1030 }
1031 }
1032
1033 if (conflictingWritingOp != readingOp) {
1034 if (auto bufferizableOp =
1035 options.dynCastBufferizableOp(op: conflictingWritingOp)) {
1036 if (bufferizableOp.isNotConflicting(uRead, uWrite: uConflictingWrite,
1037 state)) {
1038 LDBG() << " no conflict: op interace of writing op says 'no'";
1039 continue;
1040 }
1041 }
1042 }
1043
1044 // Check all possible definitions.
1045 for (Value definition : definitions) {
1046 LDBG() << " * definition = " << definition;
1047
1048 // No conflict if the conflicting write cannot happen after the
1049 // definition.
1050 if (Operation *defOp = definition.getDefiningOp()) {
1051 if (cannotHappenAfter(a: conflictingWritingOp, b: defOp, domInfo, state)) {
1052 LDBG() << " no conflict: write cannot happen after definition";
1053 continue;
1054 }
1055 // No conflict if conflictingWritingOp is contained in defOp.
1056 if (defOp->isProperAncestor(other: conflictingWritingOp)) {
1057 LDBG() << " no conflict: write is contained in definition";
1058 continue;
1059 }
1060 } else {
1061 // A bbArg is defined at block entry. The write happens after that
1062 // only if it is in the same block or in a reachable block (e.g. a
1063 // successor).
1064 Block *defBlock = cast<BlockArgument>(Val&: definition).getOwner();
1065 Operation *writeOp = defBlock->getParent()->findAncestorOpInRegion(
1066 op&: *conflictingWritingOp);
1067 if (!writeOp ||
1068 (writeOp->getBlock() != defBlock &&
1069 !state.isReachableCached(from: defBlock, to: writeOp->getBlock()))) {
1070 LDBG() << " no conflict: definition is bbArg and write cannot "
1071 "happen after def";
1072 continue;
1073 }
1074 }
1075
1076 // No conflict if the conflicting write and the definition are the same
1077 // use.
1078 AliasingValueList aliases = state.getAliasingValues(opOperand&: *uConflictingWrite);
1079 if (aliases.getNumAliases() == 1 &&
1080 aliases.getAliases()[0].value == definition) {
1081 LDBG() << " no conflict: definition and write are same";
1082 continue;
1083 }
1084
1085 // All requirements are met. Conflict found!
1086
1087 if (options.printConflicts)
1088 annotateConflict(uRead, uConflictingWrite, definition);
1089 LDBG() << " => RaW CONFLICT FOUND";
1090 return true;
1091 }
1092 }
1093 }
1094
1095 return false;
1096}
1097
1098// Helper function to iterate on aliases of `root` and capture the writes.
1099static void getAliasingInplaceWrites(DenseSet<OpOperand *> &res, Value root,
1100 const OneShotAnalysisState &state) {
1101 state.applyOnAliases(v: root, fun: [&](Value alias) {
1102 for (auto &use : alias.getUses())
1103 // Inplace write to a value that aliases root.
1104 if (isInplaceMemoryWrite(opOperand&: use, state))
1105 res.insert(V: &use);
1106 });
1107}
1108
1109// Helper function to iterate on aliases of `root` and capture the reads.
1110static void getAliasingReads(DenseSet<OpOperand *> &res, Value root,
1111 const OneShotAnalysisState &state) {
1112 state.applyOnAliases(v: root, fun: [&](Value alias) {
1113 for (auto &use : alias.getUses()) {
1114 // Read of a value that aliases root.
1115 if (state.bufferizesToMemoryRead(opOperand&: use)) {
1116 res.insert(V: &use);
1117 continue;
1118 }
1119
1120 // Read of a dependent value in the SSA use-def chain. E.g.:
1121 //
1122 // %0 = ...
1123 // %1 = tensor.extract_slice %0 {not_analyzed_yet}
1124 // "read"(%1)
1125 //
1126 // In the above example, getAliasingReads(%0) includes the first OpOperand
1127 // of the tensor.extract_slice op. The extract_slice itself does not read
1128 // but its aliasing result is eventually fed into an op that does.
1129 //
1130 // Note: This is considered a "read" only if the use does not bufferize to
1131 // a memory write. (We already ruled out memory reads. In case of a memory
1132 // write, the buffer would be entirely overwritten; in the above example
1133 // there would then be no flow of data from the extract_slice operand to
1134 // its result's uses.)
1135 if (!state.bufferizesToMemoryWrite(opOperand&: use)) {
1136 AliasingValueList aliases = state.getAliasingValues(opOperand&: use);
1137 if (llvm::any_of(Range&: aliases, P: [&](AliasingValue a) {
1138 return state.isValueRead(value: a.value);
1139 }))
1140 res.insert(V: &use);
1141 }
1142 }
1143 });
1144}
1145
1146/// Return true if bufferizing `operand` inplace would create a conflict. A read
1147/// R and a write W of the same alias set is a conflict if inplace bufferization
1148/// of W changes the value read by R to a value different from the one that
1149/// would be expected by tracing back R's origin through SSA use-def chains.
1150/// A conflict can only be introduced by a new alias and/or an inplace
1151/// bufferization decision.
1152///
1153/// Example:
1154/// %0 = tensor.extract_slice %t[...][...][1, 1] {inplace?}
1155/// %1 = vector.transfer_write %v1, %t {inplace} : vector<5xf32>, tensor<?xf32>
1156/// %e = tensor.extract_slice %1
1157/// %2 = vector.transfer_write %v2, %0 {inplace} : vector<6xf32>, tensor<?xf32>
1158/// %3 = vector.transfer_read %e, %cst : tensor<?xf32>, vector<7xf32>
1159///
1160/// In the above example, the two TransferWriteOps have already been decided to
1161/// bufferize inplace. Bufferizing the ExtractSliceOp inplace would create a
1162/// conflict because:
1163/// * According to SSA use-def chains, we expect to read the result of %1.
1164/// * However, adding an alias {%0, %t} would mean that the second
1165/// TransferWriteOp overwrites the result of the first one. Therefore, the
1166/// TransferReadOp would no longer be reading the result of %1.
1167///
1168/// If `checkConsistencyOnly` is true, this function checks if there is a
1169/// read-after-write conflict without bufferizing `operand` inplace. This would
1170/// indicate a problem with the current inplace bufferization decisions.
1171///
1172/// Note: If `checkConsistencyOnly`, this function may be called with a null
1173/// OpResult. In that case, only the consistency of bufferization decisions
1174/// involving aliases of the given OpOperand are checked.
1175static bool wouldCreateReadAfterWriteInterference(
1176 OpOperand &operand, const DominanceInfo &domInfo,
1177 OneShotAnalysisState &state, bool checkConsistencyOnly = false) {
1178 // Collect reads and writes of all aliases of OpOperand and OpResult.
1179 // Collect writes before reads: without a write, there can be no conflict.
1180 DenseSet<OpOperand *> usesWrite;
1181 getAliasingInplaceWrites(res&: usesWrite, root: operand.get(), state);
1182 AliasingValueList aliases = state.getAliasingValues(opOperand&: operand);
1183 for (AliasingValue alias : aliases)
1184 getAliasingInplaceWrites(res&: usesWrite, root: alias.value, state);
1185 if (!checkConsistencyOnly && state.bufferizesToMemoryWrite(opOperand&: operand))
1186 usesWrite.insert(V: &operand);
1187 if (usesWrite.empty())
1188 return false;
1189
1190 DenseSet<OpOperand *> usesRead;
1191 getAliasingReads(res&: usesRead, root: operand.get(), state);
1192 for (AliasingValue alias : aliases)
1193 getAliasingReads(res&: usesRead, root: alias.value, state);
1194
1195 return hasReadAfterWriteInterference(usesRead, usesWrite, domInfo, state);
1196}
1197
1198/// Annotate IR with details about the detected non-writability conflict.
1199static void annotateNonWritableTensor(Value value) {
1200 static int64_t counter = 0;
1201 OpBuilder b(value.getContext());
1202 std::string id = "W_" + std::to_string(val: counter++);
1203 if (auto opResult = dyn_cast<OpResult>(Val&: value)) {
1204 std::string attr = id + "[NOT-WRITABLE: result " +
1205 std::to_string(val: opResult.getResultNumber()) + "]";
1206 opResult.getDefiningOp()->setDiscardableAttr(name: attr, value: b.getUnitAttr());
1207 } else {
1208 auto bbArg = cast<BlockArgument>(Val&: value);
1209 std::string attr = id + "[NOT-WRITABLE: bbArg " +
1210 std::to_string(val: bbArg.getArgNumber()) + "]";
1211 bbArg.getOwner()->getParentOp()->setDiscardableAttr(name: attr, value: b.getUnitAttr());
1212 }
1213}
1214
1215/// Return true if bufferizing `operand` inplace would create a write to a
1216/// non-writable buffer.
1217static bool
1218wouldCreateWriteToNonWritableBuffer(OpOperand &operand,
1219 OneShotAnalysisState &state,
1220 bool checkConsistencyOnly = false) {
1221 bool foundWrite =
1222 !checkConsistencyOnly && state.bufferizesToMemoryWrite(opOperand&: operand);
1223
1224 if (!foundWrite) {
1225 // Collect writes of all aliases of OpOperand and OpResult.
1226 DenseSet<OpOperand *> usesWrite;
1227 getAliasingInplaceWrites(res&: usesWrite, root: operand.get(), state);
1228 for (AliasingValue alias : state.getAliasingValues(opOperand&: operand))
1229 getAliasingInplaceWrites(res&: usesWrite, root: alias.value, state);
1230 foundWrite = !usesWrite.empty();
1231 }
1232
1233 if (!foundWrite)
1234 return false;
1235
1236 // Look for a read-only tensor among all aliases.
1237 bool foundReadOnly = false;
1238 auto checkReadOnly = [&](Value v) {
1239 if (!state.isWritable(value: v)) {
1240 foundReadOnly = true;
1241 if (state.getOptions().printConflicts)
1242 annotateNonWritableTensor(value: v);
1243 }
1244 };
1245 state.applyOnAliases(v: operand.get(), fun: checkReadOnly);
1246 for (AliasingValue alias : state.getAliasingValues(opOperand&: operand))
1247 state.applyOnAliases(v: alias.value, fun: checkReadOnly);
1248 if (foundReadOnly) {
1249 LDBG() << "=> NOT WRITABLE";
1250 return true;
1251 }
1252
1253 return false;
1254}
1255
1256//===----------------------------------------------------------------------===//
1257// Bufferization analyses.
1258//===----------------------------------------------------------------------===//
1259
1260// Find the values that define the contents of the given operand's value.
1261const llvm::SetVector<Value> &
1262OneShotAnalysisState::findDefinitionsCached(OpOperand *opOperand) {
1263 Value value = opOperand->get();
1264 if (!cachedDefinitions.count(Val: value))
1265 cachedDefinitions[value] = findDefinitions(opOperand);
1266 return cachedDefinitions[value];
1267}
1268
1269bool OneShotAnalysisState::isReachableCached(
1270 Block *from, Block *to, const SmallPtrSetImpl<Block *> *barriers) {
1271 if (!cfgReachabilityCache)
1272 cfgReachabilityCache = std::make_unique<CFGReachabilityCache>();
1273 return cfgReachabilityCache->isReachable(from, to, barriers);
1274}
1275
1276bool OneShotAnalysisState::canUseOpDominanceDueToBlocksCached(
1277 Block *readBlock, Block *writeBlock, ArrayRef<Block *> defBlocks,
1278 function_ref<bool()> compute) {
1279 if (!opDominanceBlockCache)
1280 opDominanceBlockCache = std::make_unique<OpDominanceBlockCache>();
1281 return opDominanceBlockCache->getOrCompute(readBlock, writeBlock, sortedDefBlocks: defBlocks,
1282 compute);
1283}
1284
1285bool OneShotAnalysisState::areNonConflictingSubsetsCached(
1286 OpOperand *uRead, OpOperand *uConflictingWrite) {
1287 auto key = std::make_pair(x&: uRead, y&: uConflictingWrite);
1288 auto [it, inserted] = nonConflictingSubsetCache.try_emplace(Key: key, Args: false);
1289 if (inserted)
1290 it->second = areNonConflictingSubsets(uRead, uConflictingWrite, state: *this);
1291 return it->second;
1292}
1293
1294void OneShotAnalysisState::resetCache() {
1295 AnalysisState::resetCache();
1296 cachedDefinitions.clear();
1297 nonConflictingSubsetCache.clear();
1298 if (cfgReachabilityCache)
1299 cfgReachabilityCache->clear();
1300 if (opDominanceBlockCache)
1301 opDominanceBlockCache->clear();
1302}
1303
1304/// Determine if `operand` can be bufferized in-place.
1305static LogicalResult
1306bufferizableInPlaceAnalysisImpl(OpOperand &operand, OneShotAnalysisState &state,
1307 const DominanceInfo &domInfo) {
1308 LDBG() << "//===-------------------------------------------===//\n"
1309 << "Analyzing operand #" << operand.getOperandNumber() << " of "
1310 << OpWithFlags(operand.getOwner(), OpPrintingFlags().skipRegions());
1311
1312 bool foundInterference =
1313 wouldCreateWriteToNonWritableBuffer(operand, state) ||
1314 wouldCreateReadAfterWriteInterference(operand, domInfo, state);
1315
1316 if (foundInterference)
1317 state.bufferizeOutOfPlace(operand);
1318 else
1319 state.bufferizeInPlace(operand);
1320
1321 LDBG() << "//===-------------------------------------------===//";
1322 return success();
1323}
1324
1325LogicalResult
1326OneShotAnalysisState::analyzeSingleOp(Operation *op,
1327 const DominanceInfo &domInfo) {
1328 for (OpOperand &opOperand : op->getOpOperands())
1329 if (isa<TensorLikeType>(Val: opOperand.get().getType()))
1330 if (failed(Result: bufferizableInPlaceAnalysisImpl(operand&: opOperand, state&: *this, domInfo)))
1331 return failure();
1332 return success();
1333}
1334
1335/// Analyze equivalence of tied OpResult/OpOperand pairs of the given ops.
1336static void equivalenceAnalysis(SmallVector<Operation *> &ops,
1337 OneShotAnalysisState &state) {
1338 for (Operation *op : ops) {
1339 if (auto bufferizableOp = state.getOptions().dynCastBufferizableOp(op)) {
1340 for (OpResult opResult : op->getOpResults()) {
1341 if (!isa<TensorLikeType>(Val: opResult.getType()))
1342 continue;
1343 AliasingOpOperandList aliases = state.getAliasingOpOperands(value: opResult);
1344 if (aliases.getNumAliases() == 0)
1345 // Nothing to do if there are no aliasing OpOperands.
1346 continue;
1347
1348 Value firstOperand = aliases.begin()->opOperand->get();
1349 bool allEquivalent = true;
1350 for (AliasingOpOperand alias : aliases) {
1351 bool isEquiv = alias.relation == BufferRelation::Equivalent;
1352 bool isInPlace = state.isInPlace(opOperand&: *alias.opOperand);
1353 Value operand = alias.opOperand->get();
1354 if (isEquiv && isInPlace && alias.isDefinite) {
1355 // Found a definite, equivalent alias. Merge equivalence sets.
1356 // There can only be one definite alias, so we can stop here.
1357 state.unionEquivalenceClasses(v1: opResult, v2: operand);
1358 allEquivalent = false;
1359 break;
1360 }
1361 if (!isEquiv || !isInPlace)
1362 allEquivalent = false;
1363 if (!state.areEquivalentBufferizedValues(v1: operand, v2: firstOperand))
1364 allEquivalent = false;
1365 }
1366
1367 // If all "maybe" aliases are equivalent and the OpResult is not a new
1368 // allocation, it is a definite, equivalent alias. E.g.:
1369 //
1370 // aliasingOpOperands(%r) = {(%t0, EQUIV, MAYBE), (%t1, EQUIV, MAYBE)}
1371 // aliasingValues(%t0) = {(%r, EQUIV, MAYBE)}
1372 // aliasingValues(%t1) = {(%r, EQUIV, MAYBE)}
1373 // %r = arith.select %c, %t0, %t1 : tensor<?xf32>
1374 //
1375 // If %t0 and %t1 are equivalent, it is safe to union the equivalence
1376 // classes of %r, %t0 and %t1.
1377 if (allEquivalent && !bufferizableOp.bufferizesToAllocation(value: opResult))
1378 state.unionEquivalenceClasses(v1: opResult, v2: firstOperand);
1379 }
1380 }
1381 }
1382}
1383
1384/// Analyze equivalence of tied OpResult/OpOperand pairs of all ops contained
1385/// in `op`.
1386static void equivalenceAnalysis(Operation *op, OneShotAnalysisState &state) {
1387 // Traverse ops in PostOrder: Nested ops first, then enclosing ops.
1388 SmallVector<Operation *> ops;
1389 op->walk<WalkOrder::PostOrder>(callback: [&](Operation *op) {
1390 // No tensors => no buffers.
1391 if (none_of(Range: op->getResultTypes(), P: isaTensor))
1392 return;
1393 ops.push_back(Elt: op);
1394 });
1395
1396 equivalenceAnalysis(ops, state);
1397}
1398
1399/// "Bottom-up from terminators" heuristic.
1400static SmallVector<Operation *>
1401bottomUpFromTerminatorsHeuristic(Operation *op,
1402 const OneShotAnalysisState &state) {
1403 SetVector<Operation *> traversedOps;
1404
1405 // Find region terminators.
1406 op->walk<WalkOrder::PostOrder>(callback: [&](RegionBranchTerminatorOpInterface term) {
1407 if (!traversedOps.insert(X: term))
1408 return;
1409 // Follow the reverse SSA use-def chain from each yielded value as long as
1410 // we stay within the same region.
1411 SmallVector<OpResult> worklist;
1412 for (Value v : term->getOperands()) {
1413 if (!isa<TensorLikeType>(Val: v.getType()))
1414 continue;
1415 auto opResult = dyn_cast<OpResult>(Val&: v);
1416 if (!opResult)
1417 continue;
1418 worklist.push_back(Elt: opResult);
1419 }
1420 while (!worklist.empty()) {
1421 OpResult opResult = worklist.pop_back_val();
1422 Operation *defOp = opResult.getDefiningOp();
1423 if (!traversedOps.insert(X: defOp))
1424 continue;
1425 if (!term->getParentRegion()->findAncestorOpInRegion(op&: *defOp))
1426 continue;
1427 AliasingOpOperandList aliases = state.getAliasingOpOperands(value: opResult);
1428 for (auto alias : aliases) {
1429 Value v = alias.opOperand->get();
1430 if (!isa<TensorLikeType>(Val: v.getType()))
1431 continue;
1432 auto opResult = dyn_cast<OpResult>(Val&: v);
1433 if (!opResult)
1434 continue;
1435 worklist.push_back(Elt: opResult);
1436 }
1437 }
1438 });
1439
1440 // Analyze traversed ops, then all remaining ops.
1441 SmallVector<Operation *> result(traversedOps.begin(), traversedOps.end());
1442 op->walk<WalkOrder::PostOrder, ReverseIterator>(callback: [&](Operation *op) {
1443 if (!traversedOps.contains(key: op) && hasTensorSemantics(op))
1444 result.push_back(Elt: op);
1445 });
1446 return result;
1447}
1448
1449LogicalResult OneShotAnalysisState::analyzeOp(Operation *op,
1450 const DominanceInfo &domInfo) {
1451 OneShotBufferizationOptions::AnalysisHeuristic heuristic =
1452 getOptions().analysisHeuristic;
1453
1454 SmallVector<Operation *> orderedOps;
1455 if (heuristic ==
1456 OneShotBufferizationOptions::AnalysisHeuristic::BottomUpFromTerminators) {
1457 orderedOps = bottomUpFromTerminatorsHeuristic(op, state: *this);
1458 } else {
1459 op->walk(callback: [&](Operation *op) {
1460 // No tensors => no buffers.
1461 if (!hasTensorSemantics(op))
1462 return;
1463 orderedOps.push_back(Elt: op);
1464 });
1465 switch (heuristic) {
1466 case OneShotBufferizationOptions::AnalysisHeuristic::BottomUp: {
1467 // Default: Walk ops in reverse for better interference analysis.
1468 std::reverse(first: orderedOps.begin(), last: orderedOps.end());
1469 break;
1470 }
1471 case OneShotBufferizationOptions::AnalysisHeuristic::TopDown: {
1472 // Ops are already sorted top-down in `orderedOps`.
1473 break;
1474 }
1475 case OneShotBufferizationOptions::AnalysisHeuristic::Fuzzer: {
1476 assert(getOptions().analysisFuzzerSeed &&
1477 "expected that fuzzer seed it set");
1478 // This is a fuzzer. For testing purposes only. Randomize the order in
1479 // which operations are analyzed. The bufferization quality is likely
1480 // worse, but we want to make sure that no assertions are triggered
1481 // anywhere.
1482 std::mt19937 g(getOptions().analysisFuzzerSeed);
1483 llvm::shuffle(first: orderedOps.begin(), last: orderedOps.end(), g);
1484 break;
1485 }
1486 default: {
1487 llvm_unreachable("unsupported heuristic");
1488 }
1489 }
1490 }
1491
1492 // Analyze ops in the computed order.
1493 for (Operation *op : orderedOps)
1494 if (failed(Result: analyzeSingleOp(op, domInfo)))
1495 return failure();
1496
1497 equivalenceAnalysis(op, state&: *this);
1498 return success();
1499}
1500
1501LogicalResult bufferization::checkPreBufferizationAssumptions(
1502 Operation *op, const DominanceInfo &domInfo, OneShotAnalysisState &state) {
1503 const BufferizationOptions &options = state.getOptions();
1504
1505 // Note: This walk cannot be combined with the one below because interface
1506 // methods of invalid/unsupported ops may be called during the second walk.
1507 // (On ops different from `op`.)
1508 WalkResult walkResult = op->walk(callback: [&](BufferizableOpInterface op) {
1509 // Skip ops that are not in the filter.
1510 if (!options.isOpAllowed(op: op.getOperation()))
1511 return WalkResult::advance();
1512
1513 // Check for unsupported unstructured control flow.
1514 if (!op.supportsUnstructuredControlFlow()) {
1515 for (Region &r : op->getRegions()) {
1516 if (r.getBlocks().size() > 1) {
1517 op->emitOpError(message: "op or BufferizableOpInterface implementation does "
1518 "not support unstructured control flow, but at least "
1519 "one region has multiple blocks");
1520 return WalkResult::interrupt();
1521 }
1522 }
1523 }
1524
1525 return WalkResult::advance();
1526 });
1527 if (walkResult.wasInterrupted())
1528 return failure();
1529
1530 walkResult = op->walk(callback: [&](BufferizableOpInterface op) {
1531 // Skip ops that are not in the filter.
1532 if (!options.isOpAllowed(op: op.getOperation()))
1533 return WalkResult::advance();
1534
1535 // Input IR may not contain any ToTensorOps without the "restrict"
1536 // attribute. Such tensors may alias any other tensor, which is currently
1537 // not handled in the analysis.
1538 if (auto toTensorOp = dyn_cast<ToTensorOp>(Val: op.getOperation())) {
1539 if (!toTensorOp.getRestrict() && !toTensorOp->getUses().empty()) {
1540 op->emitOpError(message: "to_tensor ops without `restrict` are not supported by "
1541 "One-Shot Analysis");
1542 return WalkResult::interrupt();
1543 }
1544 }
1545
1546 for (OpOperand &opOperand : op->getOpOperands()) {
1547 if (isa<TensorLikeType>(Val: opOperand.get().getType())) {
1548 if (wouldCreateReadAfterWriteInterference(
1549 operand&: opOperand, domInfo, state,
1550 /*checkConsistencyOnly=*/true)) {
1551 // This error can happen if certain "mustBufferizeInPlace" interface
1552 // methods are implemented incorrectly, such that the IR already has
1553 // a RaW conflict before making any bufferization decisions. It can
1554 // also happen if the bufferization.materialize_in_destination is used
1555 // in such a way that a RaW conflict is not avoidable.
1556 op->emitOpError(message: "not bufferizable under the given constraints: "
1557 "cannot avoid RaW conflict");
1558 return WalkResult::interrupt();
1559 }
1560
1561 if (state.isInPlace(opOperand) &&
1562 wouldCreateWriteToNonWritableBuffer(
1563 operand&: opOperand, state, /*checkConsistencyOnly=*/true)) {
1564 op->emitOpError(message: "not bufferizable under the given constraints: would "
1565 "write to read-only buffer");
1566 return WalkResult::interrupt();
1567 }
1568 }
1569 }
1570
1571 return WalkResult::advance();
1572 });
1573
1574 return success(IsSuccess: !walkResult.wasInterrupted());
1575}
1576
1577/// Annotate the IR with the result of the analysis. For testing/debugging only.
1578static void
1579annotateOpsWithBufferizationMarkers(Operation *op,
1580 const OneShotAnalysisState &state) {
1581 // Add __inplace_operands_attr__.
1582 op->walk(callback: [&](Operation *op) {
1583 for (OpOperand &opOperand : op->getOpOperands())
1584 if (isa<TensorLikeType>(Val: opOperand.get().getType()))
1585 setInPlaceOpOperand(opOperand, inPlace: state.isInPlace(opOperand));
1586 });
1587}
1588
1589static void annotateOpsWithAliasSets(Operation *op,
1590 const OneShotAnalysisState &state) {
1591 AsmState asmState(op);
1592 Builder b(op->getContext());
1593 // Helper function to build an array attribute of aliasing SSA value strings.
1594 auto buildAliasesArray = [&](Value v) {
1595 SmallVector<Attribute> aliases;
1596 state.applyOnAliases(v, fun: [&](Value alias) {
1597 std::string buffer;
1598 llvm::raw_string_ostream stream(buffer);
1599 alias.printAsOperand(os&: stream, state&: asmState);
1600 aliases.push_back(Elt: b.getStringAttr(bytes: buffer));
1601 });
1602 return b.getArrayAttr(value: aliases);
1603 };
1604
1605 op->walk(callback: [&](Operation *op) {
1606 // Build alias set array for every OpResult.
1607 SmallVector<Attribute> opResultAliasSets;
1608 for (OpResult opResult : op->getOpResults()) {
1609 if (llvm::isa<TensorLikeType>(Val: opResult.getType())) {
1610 opResultAliasSets.push_back(Elt: buildAliasesArray(opResult));
1611 }
1612 }
1613 if (!opResultAliasSets.empty())
1614 op->setDiscardableAttr(name: kOpResultAliasSetAttrName,
1615 value: b.getArrayAttr(value: opResultAliasSets));
1616
1617 // Build alias set array for every BlockArgument.
1618 SmallVector<Attribute> regionAliasSets;
1619 bool hasTensorBbArg = false;
1620 for (Region &r : op->getRegions()) {
1621 SmallVector<Attribute> blockAliasSets;
1622 for (Block &block : r.getBlocks()) {
1623 SmallVector<Attribute> bbArgAliasSets;
1624 for (BlockArgument bbArg : block.getArguments()) {
1625 if (llvm::isa<TensorLikeType>(Val: bbArg.getType())) {
1626 bbArgAliasSets.push_back(Elt: buildAliasesArray(bbArg));
1627 hasTensorBbArg = true;
1628 }
1629 }
1630 blockAliasSets.push_back(Elt: b.getArrayAttr(value: bbArgAliasSets));
1631 }
1632 regionAliasSets.push_back(Elt: b.getArrayAttr(value: blockAliasSets));
1633 }
1634 if (hasTensorBbArg)
1635 op->setDiscardableAttr(name: kBbArgAliasSetAttrName,
1636 value: b.getArrayAttr(value: regionAliasSets));
1637 });
1638}
1639
1640LogicalResult bufferization::analyzeOp(Operation *op,
1641 OneShotAnalysisState &state,
1642 BufferizationStatistics *statistics) {
1643 DominanceInfo domInfo(op);
1644 const OneShotBufferizationOptions &options = state.getOptions();
1645
1646 if (failed(Result: checkPreBufferizationAssumptions(op, domInfo, state)))
1647 return failure();
1648
1649 // If the analysis fails, just return.
1650 if (failed(Result: state.analyzeOp(op, domInfo)))
1651 return failure();
1652
1653 if (statistics) {
1654 statistics->numTensorInPlace = state.getStatNumTensorInPlace();
1655 statistics->numTensorOutOfPlace = state.getStatNumTensorOutOfPlace();
1656 }
1657
1658 bool failedAnalysis = false;
1659
1660 // Gather some extra analysis data.
1661 state.gatherUndefinedTensorUses(op);
1662
1663 // Analysis verification: After setting up alias/equivalence sets, each op
1664 // can check for expected invariants/limitations and fail the analysis if
1665 // necessary.
1666 op->walk(callback: [&](Operation *op) {
1667 if (BufferizableOpInterface bufferizableOp =
1668 options.dynCastBufferizableOp(op))
1669 failedAnalysis |= failed(Result: bufferizableOp.verifyAnalysis(state));
1670 });
1671
1672 // Annotate operations if we only want to report the analysis.
1673 if (options.testAnalysisOnly)
1674 annotateOpsWithBufferizationMarkers(op, state);
1675 if (options.dumpAliasSets)
1676 annotateOpsWithAliasSets(op, state);
1677
1678 return success(IsSuccess: !failedAnalysis);
1679}
1680
1681LogicalResult bufferization::runOneShotBufferize(
1682 Operation *op, const OneShotBufferizationOptions &options,
1683 BufferizationState &state, BufferizationStatistics *statistics) {
1684 // copy-before-write deactivates the analysis. It cannot be used together with
1685 // test-analysis-only.
1686 assert(!(options.copyBeforeWrite && options.testAnalysisOnly) &&
1687 "invalid combination of bufferization flags");
1688
1689 if (options.copyBeforeWrite) {
1690 // Copy buffer before each write. No analysis is needed.
1691 } else {
1692 // Run One-Shot Analysis and insert buffer copies (on the tensor level)
1693 // only where needed. This is the default and much more efficient than
1694 // copy-before-write.
1695 if (failed(Result: insertTensorCopies(op, options, bufferizationState: state, statistics)))
1696 return failure();
1697
1698 // If test-analysis-only is set, the IR was annotated with RaW conflict
1699 // markers (attributes) during One-Shot Analysis.
1700 if (options.testAnalysisOnly)
1701 return success();
1702 }
1703
1704 // Bufferize the op and its nested ops. If options.copyBeforeWrite is set,
1705 // a new buffer copy is allocated every time a buffer is written to.
1706 return bufferizeOp(op, options, bufferizationState&: state, statistics);
1707}
1708